ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/loops/TorusSpanningTree.java
(Generate patch)

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.7 by jsr166, Mon Sep 20 20:44:17 2010 UTC

# 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              System.out.println();
68 <        }  
69 <        pool.shutdown();
68 >        }
69 >        System.out.println(pool);
70 >        pool.shutdown();
71      }
72  
73      static final class Node extends ForkJoinTask<Void> {
74 <        final Node[] neighbors;
74 >        final Node[] neighbors;
75          Node parent;
76          Node next;
77          volatile int mark;
78 <        
78 >
79          Node(Node[] nbrs) {
80              neighbors = nbrs;
81              parent = this;
# Line 119 | Line 123 | public class TorusSpanningTree {
123                          newList = e;
124                          if (batchSize == 0) {
125                              int s = getQueuedTaskCount();
126 <                            batchSize = ((s >= LOG_MAX_BATCH_SIZE)?
126 >                            batchSize = ((s >= LOG_MAX_BATCH_SIZE) ?
127                                           (1 << LOG_MAX_BATCH_SIZE) :
128                                           (1 << s));
129                          }
# Line 158 | Line 162 | public class TorusSpanningTree {
162  
163      static final class Driver extends RecursiveAction {
164          final Node root;
165 <        Driver(Node root) {
165 >        Driver(Node root) {
166              this.root = root;
167          }
168          public void compute() {
# Line 177 | Line 181 | public class TorusSpanningTree {
181          // connect each node to left, right, up, down neighbors
182          int maxcol = n - sideLength;
183          int col = 0;
184 <        for(int i = 0; i < sideLength; ++i) {
185 <            for(int j = 0; j < sideLength; ++j) {
184 >        for (int i = 0; i < sideLength; ++i) {
185 >            for (int j = 0; j < sideLength; ++j) {
186                  Node[] a = vs[col + j].neighbors;
187 <                a[0] = vs[col + ((j < sideLength-1)? (j+1) : 0)];
188 <                a[1] = vs[col + ((j != 0)? (j-1) : (sideLength-1))];
189 <                a[2] = vs[j + ((i < sideLength-1)? (col + sideLength) : 0)];
190 <                a[3] = vs[j + ((i != 0)? (col - sideLength) : maxcol)];
187 >                a[0] = vs[col + ((j < sideLength-1) ? (j+1) : 0)];
188 >                a[1] = vs[col + ((j != 0) ? (j-1) : (sideLength-1))];
189 >                a[2] = vs[j + ((i < sideLength-1) ? (col + sideLength) : 0)];
190 >                a[3] = vs[j + ((i != 0) ? (col - sideLength) : maxcol)];
191              }
192              col += sideLength;
193          }
# Line 212 | Line 216 | public class TorusSpanningTree {
216              v.parent = root;
217          }
218      }
215 –    
216 – }
219  
220 +    static final class Resetter extends RecursiveAction {
221 +        final Node[] g;
222 +        final int lo, hi;
223 +        Resetter(Node[] g, int lo, int hi) {
224 +            this.g = g; this.lo = lo; this.hi = hi;
225 +        }
226 +        public void compute() {
227 +            int mid = (lo + hi) >>> 1;
228 +            if (mid == lo || getSurplusQueuedTaskCount() > 3) {
229 +                for (int i = lo; i < hi; ++i)
230 +                    g[i].reset();
231 +            }
232 +            else
233 +                invokeAll(new Resetter(g, lo, mid), new Resetter(g, mid, hi));
234 +        }
235 +    }
236 + }

Diff Legend

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