From 40a6fc47815746d763fca23b8495798ed2a4baa9 Mon Sep 17 00:00:00 2001
From: jjenista <jjenista>
Date: Wed, 7 May 2008 22:28:42 +0000
Subject: [PATCH] Update benchmark to allocate nodes into global array along
 the same partition that the workload is split to aid prefetching.

---
 .../Prefetch/Em3d/dsm/BiGraphN.java           | 148 ++++++++---
 .../Benchmarks/Prefetch/Em3d/dsm/Em3dN.java   | 251 ++++++++++++++++--
 .../Benchmarks/Prefetch/Em3d/dsm/Node.java    |   2 +-
 3 files changed, 335 insertions(+), 66 deletions(-)

diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraphN.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraphN.java
index 9c5a8f69..19793c1d 100644
--- a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraphN.java
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraphN.java
@@ -36,52 +36,124 @@ public class BiGraph
    * @return the bi graph that we've created.
    **/
 
-  static BiGraph create(int numNodes, int numDegree, boolean verbose, Random r)
+  static BiGraph create(int numNodes, int degree, boolean verbose, Random r)
   {
-
     // making nodes (we create a table)
     //if (verbose) System.printString("making nodes (tables in orig. version)");
-    Node [] eTable=Node.fillTable(numNodes, numDegree, r);
-    Node [] hTable=Node.fillTable(numNodes, numDegree, r);
-
-    // making neighbors
-    //if (verbose) System.printString("updating from and coeffs");
-    for(int i = 0; i< numNodes; i++) {
-      Node n = hTable[i];
-      n.makeUniqueNeighbors(eTable, r);
-    }
-
-    for (int i = 0; i < numNodes; i++) {
-      Node n = eTable[i];
-      n.makeUniqueNeighbors(hTable, r);
-    }
-
-    // Create the fromNodes and coeff field
-    //if (verbose) System.printString("filling from fields");
-    for(int i = 0; i< numNodes; i++) {
-      Node n = hTable[i];
-      n.makeFromNodes();
-    }
-
-    for (int i = 0; i < numNodes; i++) {
-      Node n = eTable[i];
-      n.makeFromNodes();
-    }
-
-    // Update the fromNodes
-    for (int i = 0; i < numNodes; i++) {
-      Node n = hTable[i];
-      n.updateFromNodes(r);
-    }
-    for (int i = 0; i < numNodes; i++) {
-      Node n = eTable[i];
-      n.updateFromNodes(r);
-    }
+    //Node [] eTable=Node.fillTable(numNodes, numDegree, r);
+    //Node [] hTable=Node.fillTable(numNodes, numDegree, r);
+
+    Node [] eTable = global new Node[numNodes];
+    Node [] hTable = global new Node[numNodes];
 
+    eTable[0] = global new Node(degree, r);
+    hTable[0] = global new Node(degree, r);
+      
     BiGraph g = global new BiGraph(eTable, hTable);
+
     return g;
   }
 
+    
+  /**
+   * 
+   *
+   * @return 
+   **/
+  public void allocate( int indexBegin, int indexEnd, int degree, Random r )
+  { 
+      Node prevNodeE = global new Node(degree, r);
+      Node prevNodeH = global new Node(degree, r);
+
+      eNodes[indexBegin] = prevNodeE;
+      hNodes[indexBegin] = prevNodeH;
+
+      for( int i = indexBegin + 1; i < indexEnd; i++ ) {
+	  Node curNodeE = global new Node(degree, r);
+	  Node curNodeH = global new Node(degree, r);
+
+	  eNodes[i] = curNodeE;
+	  hNodes[i] = curNodeH;
+
+	  prevNodeE.next = curNodeE;
+	  prevNodeH.next = curNodeH;
+
+	  prevNodeE = curNodeE;
+	  prevNodeH = curNodeH;
+      }
+  }
+
+  
+  public void linkSegments( int index ) {
+      eNodes[index - 1].next = eNodes[index];
+      hNodes[index - 1].next = hNodes[index];
+  }
+
+
+  /**
+   * 
+   *
+   * @return 
+   **/
+  public void makeNeighbors( int indexBegin, int indexEnd, Random r )
+  {
+      System.printString( "Making unique neighbors for hNodes...\n" );
+
+      // making neighbors
+      //if (verbose) System.printString("updating from and coeffs");
+      for(int i = indexBegin; i < indexEnd; i++) {
+	  Node n = hNodes[i];
+	  n.makeUniqueNeighbors(eNodes, r);
+      }
+
+      System.printString( "Making unique neighbors for eNodes...\n" );
+
+      for (int i = indexBegin; i < indexEnd; i++) {
+	  Node n = eNodes[i];
+	  n.makeUniqueNeighbors(hNodes, r);
+      }
+  }
+
+
+  public void makeFromNodes( int indexBegin, int indexEnd )
+  {
+      System.printString( "Making h fromNodes...\n" );
+
+      // Create the fromNodes and coeff field
+      //if (verbose) System.printString("filling from fields");
+      for(int i = indexBegin; i < indexEnd; i++) {
+	  Node n = hNodes[i];
+	  n.makeFromNodes();
+      }
+      
+      System.printString( "Making e fromNodes...\n" );
+
+      for(int i = indexBegin; i < indexEnd; i++) {
+	  Node n = eNodes[i];
+	  n.makeFromNodes();
+      }   
+  }
+
+
+  public void makeFromLinks( int indexBegin, int indexEnd, Random r )
+  {
+      System.printString( "Updating h fromNodes...\n" );
+
+      // Update the fromNodes
+      for(int i = indexBegin; i < indexEnd; i++) {
+	  Node n = hNodes[i];
+	  n.updateFromNodes(r);
+      }
+
+      System.printString( "Updating e fromNodes...\n" );
+
+      for(int i = indexBegin; i < indexEnd; i++) {
+	  Node n = eNodes[i];
+	  n.updateFromNodes(r);
+      }      
+  }
+
+
   /**
    * Override the toString method to print out the values of the e and h nodes.
    * @return a string contain the values of the e and h nodes.
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3dN.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3dN.java
index daf334ef..b90711c6 100644
--- a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3dN.java
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3dN.java
@@ -44,57 +44,111 @@ public class Em3d extends Thread
   int lowerlimit;
   Barrier mybarr;
 
+  Random r;
+
+  // yipes! static members are not supported so
+  // using the following constants:
+  // runMode == 1 is RUNMODE_ALLOC
+  // runMode == 2 is RUNMODE_NEIGHBORS
+  // runMode == 3 is RUNMODE_MAKEFROM
+  // runMode == 4 is RUNMODE_FROMLINKS
+  // runMode == 5 is RUNMODE_WORK
+  int runMode;
+
+
   public Em3d() {
     numNodes = 0;
     numDegree = 0;
     numIter = 1;
     printResult = false;
     printMsgs = false;
+    runMode = 0;
   }
 
-  public Em3d(BiGraph bg, int lowerlimit, int upperlimit, int numIter, Barrier mybarr) {
+  public Em3d(BiGraph bg, int lowerlimit, int upperlimit, int numIter, Barrier mybarr, int numDegree, Random r, int runMode) {
     this.bg = bg;
     this.lowerlimit = lowerlimit;
     this.upperlimit = upperlimit;
     this.numIter = numIter;
     this.mybarr = mybarr;
+    this.runMode = runMode;
+    this.numDegree = numDegree;
+    this.r = r;
   }
 
   public void run() {
     int iteration;
     Barrier barr;
+    int degree;
+    Random random;
+    int mode;
 
     atomic {
       iteration = numIter;
       barr=mybarr;
+      degree = numDegree;
+      random = r;
+      mode = runMode;
     }
 
-    for (int i = 0; i < iteration; i++) {
-	/* for  eNodes */
+    if( mode == 1 ) {
 	atomic {
-	    for(int j = lowerlimit; j<upperlimit; j++) {
-		Node n = bg.eNodes[j];
-		
-		for (int k = 0; k < n.fromCount; k++) {
-		    n.value -= n.coeffs[k] * n.fromNodes[k].value;
-		}
-	    }
+	    bg.allocate( lowerlimit, upperlimit, degree, r );
 	}
-	
 	Barrier.enterBarrier(barr);
 	System.clearPrefetchCache();
 
-	/* for  hNodes */
+    } else if( mode == 2 ) {
 	atomic {
-	    for(int j = lowerlimit; j<upperlimit; j++) {
-		Node n = bg.hNodes[j];
-		for (int k = 0; k < n.fromCount; k++) {
-		    n.value -= n.coeffs[k] * n.fromNodes[k].value;
-		}
-	    }
+	    bg.makeNeighbors( lowerlimit, upperlimit, r );
+	}
+	Barrier.enterBarrier(barr);
+	System.clearPrefetchCache();
+
+    } else if( mode == 3 ) {
+	atomic {
+	    bg.makeFromNodes( lowerlimit, upperlimit );
+	}
+	Barrier.enterBarrier(barr);
+	System.clearPrefetchCache();
+
+    } else if( mode == 4 ) {
+	atomic {
+	    bg.makeFromLinks( lowerlimit, upperlimit, r );
 	}
 	Barrier.enterBarrier(barr);
 	System.clearPrefetchCache();
+
+    } else if( mode == 5 ) {
+
+	for (int i = 0; i < iteration; i++) {
+	    /* for  eNodes */
+	    atomic {
+		for(int j = lowerlimit; j<upperlimit; j++) {
+		    Node n = bg.eNodes[j];
+		    
+		    for (int k = 0; k < n.fromCount; k++) {
+			n.value -= n.coeffs[k] * n.fromNodes[k].value;
+		    }
+		}
+	    }
+	    
+	    Barrier.enterBarrier(barr);
+	    System.clearPrefetchCache();
+	    
+	    /* for  hNodes */
+	    atomic {
+		for(int j = lowerlimit; j<upperlimit; j++) {
+		    Node n = bg.hNodes[j];
+		    for (int k = 0; k < n.fromCount; k++) {
+			n.value -= n.coeffs[k] * n.fromNodes[k].value;
+		    }
+		}
+	    }
+	    Barrier.enterBarrier(barr);
+	    System.clearPrefetchCache();
+	}
+	
     }
   }
 
@@ -112,43 +166,186 @@ public class Em3d extends Thread
     long start0 = System.currentTimeMillis();
     int numThreads = em.numThreads;
     int[] mid = new int[4];
-    mid[0] = (128<<24)|(195<<16)|(175<<8)|69;
-    mid[1] = (128<<24)|(195<<16)|(175<<8)|80;
+    mid[0] = (128<<24)|(195<<16)|(175<<8)|69;//dw-1
+    mid[1] = (128<<24)|(195<<16)|(175<<8)|70;//dw-2
     mid[2] = (128<<24)|(195<<16)|(175<<8)|73;
     mid[3] = (128<<24)|(195<<16)|(175<<8)|78;
     System.printString("DEBUG -> numThreads = " + numThreads+"\n");
     Barrier mybarr;
     BiGraph graph;
-    Random rand = new Random(783);
+    Random rand;
+
+    
+    // initialization step 1: allocate BiGraph
+    System.printString( "Allocating BiGraph.\n" );
 
     atomic {
       mybarr = global new Barrier(numThreads);
+      rand = global new Random(783);
       graph =  BiGraph.create(em.numNodes, em.numDegree, em.printResult, rand);
     }
 
+    Em3d[] em3d;    
+    Em3d tmp;
+    int base;
+    int increment;
+
+
+	increment = em.numNodes/numThreads;
+
+
+    // initialization step 2: divide work of allocating nodes
+    System.printString( "Launching distributed allocation of nodes.\n" );
+
+    atomic {
+      em3d = global new Em3d[numThreads];
+      base=0;
+      for(int i=0;i<numThreads;i++) {
+	  if ((i+1)==numThreads)
+	      em3d[i] = global new Em3d(graph, base, em.numNodes, em.numIter, mybarr, em.numDegree, rand, 1);
+	  else
+	      em3d[i] = global new Em3d(graph, base, base+increment, em.numIter, mybarr, em.numDegree, rand, 1);
+	  base+=increment;
+      }
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic {
+        tmp = em3d[i];
+      }
+      tmp.start(mid[i]);
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic { 
+        tmp = em3d[i];
+      }
+      tmp.join();
+    }
+
+    // initialization step 3: link together the ends of segments
+    // that were allocated and internally linked in step 2
+    System.printString( "Linking together allocated segments.\n" );
+
+    base = 0;
+    for(int i = 0; i < numThreads - 1; i++) {
+	atomic {
+	    graph.linkSegments( base + increment );
+	    base += increment;   	    
+	}
+    }    
+
+    // initialization step 4: divide work of making links
+    System.printString( "Launching distributed neighbor initialization.\n" );
+
+    atomic {
+      em3d = global new Em3d[numThreads];
+      base=0;
+      for(int i=0;i<numThreads;i++) {
+	  if ((i+1)==numThreads)
+	      em3d[i] = global new Em3d(graph, base, em.numNodes, em.numIter, mybarr, em.numDegree, rand, 2);
+	  else
+	      em3d[i] = global new Em3d(graph, base, base+increment, em.numIter, mybarr, em.numDegree, rand, 2);
+	  base+=increment;
+      }
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic {
+        tmp = em3d[i];
+      }
+      tmp.start(mid[i]);
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic { 
+        tmp = em3d[i];
+      }
+      tmp.join();
+    }
+
+    // initialization step 5: divide work of making from links
+    System.printString( "Launching distributed makeFromNodes initialization.\n" );
+
+    atomic {
+      em3d = global new Em3d[numThreads];
+      base=0;
+      for(int i=0;i<numThreads;i++) {
+	  if ((i+1)==numThreads)
+	      em3d[i] = global new Em3d(graph, base, em.numNodes, em.numIter, mybarr, em.numDegree, rand, 3);
+	  else
+	      em3d[i] = global new Em3d(graph, base, base+increment, em.numIter, mybarr, em.numDegree, rand, 3);
+	  base+=increment;
+      }
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic {
+        tmp = em3d[i];
+      }
+      tmp.start(mid[i]);
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic { 
+        tmp = em3d[i];
+      }
+      tmp.join();
+    }
+
+    // initialization step 6: divide work of making from links
+    System.printString( "Launching distributed fromLink initialization.\n" );
+
+    atomic {
+      em3d = global new Em3d[numThreads];
+      base=0;
+      for(int i=0;i<numThreads;i++) {
+	  if ((i+1)==numThreads)
+	      em3d[i] = global new Em3d(graph, base, em.numNodes, em.numIter, mybarr, em.numDegree, rand, 4);
+	  else
+	      em3d[i] = global new Em3d(graph, base, base+increment, em.numIter, mybarr, em.numDegree, rand, 4);
+	  base+=increment;
+      }
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic {
+        tmp = em3d[i];
+      }
+      tmp.start(mid[i]);
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic { 
+        tmp = em3d[i];
+      }
+      tmp.join();
+    }
+
+    // initialization complete
+    System.printString( "Initialization complete.\n" );
+
     long end0 = System.currentTimeMillis();
 
+
     // compute a single iteration of electro-magnetic propagation
     if (em.printMsgs) 
       System.printString("Propagating field values for " + em.numIter + 
           " iteration(s)...\n");
     long start1 = System.currentTimeMillis();
-    Em3d[] em3d;
 
     atomic {
       em3d = global new Em3d[numThreads];
-      int increment=em.numNodes/numThreads;
-      int base=0;
+      base=0;
       for(int i=0;i<numThreads;i++) {
 	  if ((i+1)==numThreads)
-	      em3d[i] = global new Em3d(graph, base, em.numNodes, em.numIter, mybarr);
+	      em3d[i] = global new Em3d(graph, base, em.numNodes, em.numIter, mybarr, em.numDegree, rand, 5);
 	  else
-	      em3d[i] = global new Em3d(graph, base, base+increment, em.numIter, mybarr);
+	      em3d[i] = global new Em3d(graph, base, base+increment, em.numIter, mybarr, em.numDegree, rand, 5);
 	  base+=increment;
       }
     }
 
-    Em3d tmp;
     for(int i = 0; i<numThreads; i++) {
       atomic {
         tmp = em3d[i];
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java
index a699e75b..5e3aca6c 100644
--- a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java
@@ -122,7 +122,7 @@ public class Node {
    * by this node.
    **/
   public void updateFromNodes(Random rand)
-  {
+  { 
     for (int i = 0; i < toNodes.length; i++) {
       Node otherNode = toNodes[i];
       int count = otherNode.fromLength++;
-- 
2.34.1