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.*; |
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. |
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; |
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); |
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 |
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 |
|
} |
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 |
|
} |
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 |
|
} |
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 |
+ |
} |