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 |
|
|
62 |
|
resetAll(graph); |
63 |
|
} |
64 |
|
System.out.println(); |
65 |
< |
} |
66 |
< |
pool.shutdown(); |
65 |
> |
} |
66 |
> |
pool.shutdown(); |
67 |
|
} |
68 |
|
|
69 |
|
static final class Node extends ForkJoinTask<Void> { |
70 |
< |
final Node[] neighbors; |
70 |
> |
final Node[] neighbors; |
71 |
|
Node parent; |
72 |
|
Node next; |
73 |
|
volatile int mark; |
74 |
< |
|
74 |
> |
|
75 |
|
Node(Node[] nbrs) { |
76 |
|
neighbors = nbrs; |
77 |
|
parent = this; |
119 |
|
newList = e; |
120 |
|
if (batchSize == 0) { |
121 |
|
int s = getQueuedTaskCount(); |
122 |
< |
batchSize = ((s >= LOG_MAX_BATCH_SIZE)? |
122 |
> |
batchSize = ((s >= LOG_MAX_BATCH_SIZE)? |
123 |
|
(1 << LOG_MAX_BATCH_SIZE) : |
124 |
|
(1 << s)); |
125 |
|
} |
158 |
|
|
159 |
|
static final class Driver extends RecursiveAction { |
160 |
|
final Node root; |
161 |
< |
Driver(Node root) { |
161 |
> |
Driver(Node root) { |
162 |
|
this.root = root; |
163 |
|
} |
164 |
|
public void compute() { |
212 |
|
v.parent = root; |
213 |
|
} |
214 |
|
} |
215 |
– |
|
216 |
– |
} |
215 |
|
|
216 |
+ |
} |