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.5 by jsr166, Wed Sep 1 07:20:36 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  
# Line 55 | Line 55 | public class TorusSpanningTree {
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);
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();
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;
# Line 119 | Line 119 | public class TorusSpanningTree {
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                          }
# Line 158 | Line 158 | public class TorusSpanningTree {
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() {
# Line 177 | Line 177 | public class TorusSpanningTree {
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) {
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)];
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          }
# Line 212 | Line 212 | public class TorusSpanningTree {
212              v.parent = root;
213          }
214      }
215 –    
216 – }
215  
216 + }

Diff Legend

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