ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/loops/TorusSpanningTree.java

Comparing jsr166/src/test/loops/TorusSpanningTree.java (file contents):
Revision 1.1 by dl, Mon Nov 2 14:08:38 2009 UTC vs.
Revision 1.9 by dl, Sat Sep 12 20:24:33 2015 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		//import jsr166y.*;
#	Line 14 | Line 14 | import java.util.concurrent.atomic.*;
14		* paper: Guojing Cong, Sreedhar Kodali, Sriram Krishnamoorty, Doug
15		* Lea, Vijay Saraswat and Tong Wen, "Solving irregular graph problems
16		* using adaptive work-stealing", ICPP, 2008.
17	<	*
17	>	*
18		* It runs the main batching algorithm discussed there for spanning
19		* trees, for a simple regular torus graph, where each node is
20		* connected to its left. right, up, and down neighbors.
#	Line 22 | Line 22 | import java.util.concurrent.atomic.*;
22		public class TorusSpanningTree {
23		static final int NCPUS = Runtime.getRuntime().availableProcessors();
24
25	<	// Dimensions for test runs.
25	>	// Dimensions for test runs.
26		// graphs have side*side nodes, each with 4 neighbors
27		static final int MIN_SIDE = 1000;
28		static final int MAX_SIDE = 3000;
#	Line 42 | Line 42 | public class TorusSpanningTree {
42		System.out.println("Number of threads: " + procs);
43		System.out.println("Printing nanosec per edge across replications");
44		System.out.print("for Toruses with side lengths");
45	<	System.out.printf(" from %5d to %5d step %5d\n",
45	>	System.out.printf(" from %5d to %5d step %5d\n",
46		MIN_SIDE, MAX_SIDE, SIDE_STEP);
47		ForkJoinPool pool = new ForkJoinPool(procs);
48
49	+	boolean checked = false;
50		for (int side = MIN_SIDE; side <= MAX_SIDE; side += SIDE_STEP) {
51		int n = side * side;
52		Node[] graph = makeGraph(side);
#	Line 55 | Line 56 | public class TorusSpanningTree {
56		long start = System.nanoTime();
57		pool.invoke(new Driver(root));
58		long elapsed = System.nanoTime() - start;
59	<	double nanosPerEdge = (double)elapsed / (4 * n);
60	<	System.out.printf(" %7.2f", nanosPerEdge);
61	<	if (j == 0)
59	>	double nanosPerEdge = (double) elapsed / (4 * n);
60	>	System.out.printf(" %7.2f", nanosPerEdge);
61	>	if (!checked) {
62	>	checked = true;
63		checkSpanningTree(graph, root);
64	<	resetAll(graph);
64	>	}
65	>	pool.invoke(new Resetter(graph, 0, graph.length));
66		}
67	+	graph = null;
68		System.out.println();
69	<	}
70	<	pool.shutdown();
69	>	}
70	>	System.out.println(pool);
71	>	pool.shutdown();
72		}
73
74		static final class Node extends ForkJoinTask<Void> {
75	<	final Node[] neighbors;
75	>	final Node[] neighbors;
76		Node parent;
77		Node next;
78	<	volatile int mark;
74	<
78	>
79		Node(Node[] nbrs) {
80		neighbors = nbrs;
81		parent = this;
82		}
83
80	–	static final AtomicIntegerFieldUpdater<Node> markUpdater =
81	–	AtomicIntegerFieldUpdater.newUpdater(Node.class, "mark");
82	–
83	–	boolean tryMark() {
84	–	return mark == 0 && markUpdater.compareAndSet(this, 0, 1);
85	–	}
86	–	void setMark() { mark = 1; }
87	–
84		/*
85		* Traverse the list ("oldList") embedded across .next fields,
86		* starting at this node, placing newly discovered neighboring
#	Line 113 | Line 109 | public class TorusSpanningTree {
109		int nedges = edges.length;
110		for (int k = 0; k < nedges; ++k) {
111		Node e = edges[k];
112	<	if (e != null && e.tryMark()) {
112	>	if (e != null &&
113	>	e.compareAndSetForkJoinTaskTag((short)0, (short)1)) {
114		e.parent = par;
115		e.next = newList;
116		newList = e;
117		if (batchSize == 0) {
118		int s = getQueuedTaskCount();
119	<	batchSize = ((s >= LOG_MAX_BATCH_SIZE)?
119	>	batchSize = ((s >= LOG_MAX_BATCH_SIZE) ?
120		(1 << LOG_MAX_BATCH_SIZE) :
121		(1 << s));
122		}
#	Line 151 | Line 148 | public class TorusSpanningTree {
148		reinitialize();
149		parent = this;
150		next = null;
154	–	mark = 0;
151		}
152
153		}
154
155		static final class Driver extends RecursiveAction {
156		final Node root;
157	<	Driver(Node root) {
157	>	Driver(Node root) {
158		this.root = root;
159		}
160		public void compute() {
161	<	root.setMark();
161	>	root.setForkJoinTaskTag((short)1);
162		root.fork();
163		helpQuiesce();
164		}
#	Line 177 | Line 173 | public class TorusSpanningTree {
173		// connect each node to left, right, up, down neighbors
174		int maxcol = n - sideLength;
175		int col = 0;
176	<	for(int i = 0; i < sideLength; ++i) {
177	<	for(int j = 0; j < sideLength; ++j) {
176	>	for (int i = 0; i < sideLength; ++i) {
177	>	for (int j = 0; j < sideLength; ++j) {
178		Node[] a = vs[col + j].neighbors;
179	<	a[0] = vs[col + ((j < sideLength-1)? (j+1) : 0)];
180	<	a[1] = vs[col + ((j != 0)? (j-1) : (sideLength-1))];
181	<	a[2] = vs[j + ((i < sideLength-1)? (col + sideLength) : 0)];
182	<	a[3] = vs[j + ((i != 0)? (col - sideLength) : maxcol)];
179	>	a[0] = vs[col + ((j < sideLength-1) ? (j+1) : 0)];
180	>	a[1] = vs[col + ((j != 0) ? (j-1) : (sideLength-1))];
181	>	a[2] = vs[j + ((i < sideLength-1) ? (col + sideLength) : 0)];
182	>	a[3] = vs[j + ((i != 0) ? (col - sideLength) : maxcol)];
183		}
184		col += sideLength;
185		}
#	Line 212 | Line 208 | public class TorusSpanningTree {
208		v.parent = root;
209		}
210		}
215	–
216	–	}
211
212	+	static final class Resetter extends RecursiveAction {
213	+	final Node[] g;
214	+	final int lo, hi;
215	+	Resetter(Node[] g, int lo, int hi) {
216	+	this.g = g; this.lo = lo; this.hi = hi;
217	+	}
218	+	public void compute() {
219	+	int mid = (lo + hi) >>> 1;
220	+	if (mid == lo || getSurplusQueuedTaskCount() > 3) {
221	+	for (int i = lo; i < hi; ++i)
222	+	g[i].reset();
223	+	}
224	+	else
225	+	invokeAll(new Resetter(g, lo, mid), new Resetter(g, mid, hi));
226	+	}
227	+	}
228	+	}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines