1 |
dl |
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 |
5 |
|
|
*/ |
6 |
|
|
|
7 |
|
|
//import jsr166y.*; |
8 |
|
|
import java.util.*; |
9 |
|
|
import java.util.concurrent.*; |
10 |
|
|
import java.util.concurrent.atomic.*; |
11 |
|
|
|
12 |
|
|
/** |
13 |
|
|
* This is reworked version of one of the tests reported on in the |
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 |
|
|
* |
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. |
21 |
|
|
*/ |
22 |
|
|
public class TorusSpanningTree { |
23 |
|
|
static final int NCPUS = Runtime.getRuntime().availableProcessors(); |
24 |
|
|
|
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; |
29 |
|
|
static final int SIDE_STEP = 500; |
30 |
|
|
|
31 |
|
|
public static void main(String[] args) throws Exception { |
32 |
|
|
Random rng = new Random(); |
33 |
|
|
int procs = NCPUS; |
34 |
|
|
try { |
35 |
|
|
if (args.length > 0) |
36 |
|
|
procs = Integer.parseInt(args[0]); |
37 |
|
|
} |
38 |
|
|
catch (Exception e) { |
39 |
|
|
System.out.println("Usage: java TorusSpanningTree <threads>"); |
40 |
|
|
return; |
41 |
|
|
} |
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", |
46 |
|
|
MIN_SIDE, MAX_SIDE, SIDE_STEP); |
47 |
|
|
ForkJoinPool pool = new ForkJoinPool(procs); |
48 |
|
|
|
49 |
|
|
for (int side = MIN_SIDE; side <= MAX_SIDE; side += SIDE_STEP) { |
50 |
|
|
int n = side * side; |
51 |
|
|
Node[] graph = makeGraph(side); |
52 |
|
|
System.out.printf( "N:%9d", n); |
53 |
|
|
for (int j = 0; j < 8; ++j) { |
54 |
|
|
Node root = graph[rng.nextInt(n)]; |
55 |
|
|
long start = System.nanoTime(); |
56 |
|
|
pool.invoke(new Driver(root)); |
57 |
|
|
long elapsed = System.nanoTime() - start; |
58 |
|
|
double nanosPerEdge = (double)elapsed / (4 * n); |
59 |
|
|
System.out.printf(" %7.2f", nanosPerEdge); |
60 |
|
|
if (j == 0) |
61 |
|
|
checkSpanningTree(graph, root); |
62 |
|
|
resetAll(graph); |
63 |
|
|
} |
64 |
|
|
System.out.println(); |
65 |
|
|
} |
66 |
|
|
pool.shutdown(); |
67 |
|
|
} |
68 |
|
|
|
69 |
|
|
static final class Node extends ForkJoinTask<Void> { |
70 |
|
|
final Node[] neighbors; |
71 |
|
|
Node parent; |
72 |
|
|
Node next; |
73 |
|
|
volatile int mark; |
74 |
|
|
|
75 |
|
|
Node(Node[] nbrs) { |
76 |
|
|
neighbors = nbrs; |
77 |
|
|
parent = this; |
78 |
|
|
} |
79 |
|
|
|
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 |
|
|
|
88 |
|
|
/* |
89 |
|
|
* Traverse the list ("oldList") embedded across .next fields, |
90 |
|
|
* starting at this node, placing newly discovered neighboring |
91 |
|
|
* nodes in newList. If the oldList becomes exhausted, swap in |
92 |
|
|
* newList and continue. Otherwise, whenever the length of |
93 |
|
|
* newList exceeds current number of tasks in work-stealing |
94 |
|
|
* queue, push list onto queue. |
95 |
|
|
*/ |
96 |
|
|
|
97 |
|
|
static final int LOG_MAX_BATCH_SIZE = 7; |
98 |
|
|
|
99 |
|
|
/** |
100 |
|
|
* Since tasks are never joined, we bypass Recursive{Action,Task} |
101 |
|
|
* and just directly implement exec |
102 |
|
|
*/ |
103 |
|
|
public boolean exec() { |
104 |
|
|
int batchSize = 0; // computed lazily |
105 |
|
|
Node newList = null; |
106 |
|
|
int newLength = 0; |
107 |
|
|
Node oldList = this; |
108 |
|
|
Node par = parent; |
109 |
|
|
do { |
110 |
|
|
Node v = oldList; |
111 |
|
|
Node[] edges = v.neighbors; |
112 |
|
|
oldList = v.next; |
113 |
|
|
int nedges = edges.length; |
114 |
|
|
for (int k = 0; k < nedges; ++k) { |
115 |
|
|
Node e = edges[k]; |
116 |
|
|
if (e != null && e.tryMark()) { |
117 |
|
|
e.parent = par; |
118 |
|
|
e.next = newList; |
119 |
|
|
newList = e; |
120 |
|
|
if (batchSize == 0) { |
121 |
|
|
int s = getQueuedTaskCount(); |
122 |
|
|
batchSize = ((s >= LOG_MAX_BATCH_SIZE)? |
123 |
|
|
(1 << LOG_MAX_BATCH_SIZE) : |
124 |
|
|
(1 << s)); |
125 |
|
|
} |
126 |
|
|
if (++newLength >= batchSize) { |
127 |
|
|
newLength = 0; |
128 |
|
|
batchSize = 0; |
129 |
|
|
if (oldList == null) |
130 |
|
|
oldList = newList; |
131 |
|
|
else |
132 |
|
|
newList.fork(); |
133 |
|
|
newList = null; |
134 |
|
|
} |
135 |
|
|
} |
136 |
|
|
} |
137 |
|
|
if (oldList == null) { |
138 |
|
|
oldList = newList; |
139 |
|
|
newList = null; |
140 |
|
|
newLength = 0; |
141 |
|
|
} |
142 |
|
|
} while (oldList != null); |
143 |
|
|
return false; |
144 |
|
|
} |
145 |
|
|
|
146 |
|
|
// required abstract implementations for ForkJoinTask |
147 |
|
|
public final Void getRawResult() { return null; } |
148 |
|
|
protected final void setRawResult(Void mustBeNull) { } |
149 |
|
|
|
150 |
|
|
public void reset() { |
151 |
|
|
reinitialize(); |
152 |
|
|
parent = this; |
153 |
|
|
next = null; |
154 |
|
|
mark = 0; |
155 |
|
|
} |
156 |
|
|
|
157 |
|
|
} |
158 |
|
|
|
159 |
|
|
static final class Driver extends RecursiveAction { |
160 |
|
|
final Node root; |
161 |
|
|
Driver(Node root) { |
162 |
|
|
this.root = root; |
163 |
|
|
} |
164 |
|
|
public void compute() { |
165 |
|
|
root.setMark(); |
166 |
|
|
root.fork(); |
167 |
|
|
helpQuiesce(); |
168 |
|
|
} |
169 |
|
|
} |
170 |
|
|
|
171 |
|
|
static Node[] makeGraph(int sideLength) { |
172 |
|
|
int n = sideLength * sideLength; |
173 |
|
|
Node[] vs = new Node[n]; |
174 |
|
|
for (int i = 0; i < n; ++i) |
175 |
|
|
vs[i] = new Node(new Node[4]); |
176 |
|
|
|
177 |
|
|
// connect each node to left, right, up, down neighbors |
178 |
|
|
int maxcol = n - sideLength; |
179 |
|
|
int col = 0; |
180 |
|
|
for(int i = 0; i < sideLength; ++i) { |
181 |
|
|
for(int j = 0; j < sideLength; ++j) { |
182 |
|
|
Node[] a = vs[col + j].neighbors; |
183 |
|
|
a[0] = vs[col + ((j < sideLength-1)? (j+1) : 0)]; |
184 |
|
|
a[1] = vs[col + ((j != 0)? (j-1) : (sideLength-1))]; |
185 |
|
|
a[2] = vs[j + ((i < sideLength-1)? (col + sideLength) : 0)]; |
186 |
|
|
a[3] = vs[j + ((i != 0)? (col - sideLength) : maxcol)]; |
187 |
|
|
} |
188 |
|
|
col += sideLength; |
189 |
|
|
} |
190 |
|
|
return vs; |
191 |
|
|
} |
192 |
|
|
|
193 |
|
|
static void resetAll(Node[] g) { |
194 |
|
|
for (int i = 0; i < g.length; ++i) |
195 |
|
|
g[i].reset(); |
196 |
|
|
} |
197 |
|
|
|
198 |
|
|
// check that all nodes have parents, and no cycles |
199 |
|
|
static void checkSpanningTree(Node[] g, Node root) { |
200 |
|
|
int n = g.length; |
201 |
|
|
for (int i = 0; i < n; ++i) { |
202 |
|
|
Node v = g[i]; |
203 |
|
|
Node p = v; |
204 |
|
|
int k = n; |
205 |
|
|
while (p != root) { |
206 |
|
|
if (p == null) |
207 |
|
|
throw new RuntimeException("null parent"); |
208 |
|
|
if (--k <= 0) |
209 |
|
|
throw new RuntimeException("cycle"); |
210 |
|
|
p = p.parent; |
211 |
|
|
} |
212 |
|
|
v.parent = root; |
213 |
|
|
} |
214 |
|
|
} |
215 |
|
|
|
216 |
|
|
} |
217 |
|
|
|