From 59eb7b9101e2858f0be784e8da8bf46407cfb53f Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Mon, 4 Aug 2008 07:59:19 +0000
Subject: [PATCH] Parallelized Version...Haven't tested

---
 .../Prefetch/Em3d/dsm/BiGraph2.java           | 104 ++++++++
 .../Benchmarks/Prefetch/Em3d/dsm/EVector.java |  83 ++++++
 .../Benchmarks/Prefetch/Em3d/dsm/Em3d2.java   | 247 ++++++++++++++++++
 .../Prefetch/Em3d/dsm/Em3dWrap.java           |   9 +
 .../Benchmarks/Prefetch/Em3d/dsm/Node2.java   | 121 +++++++++
 5 files changed, 564 insertions(+)
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraph2.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/EVector.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3d2.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3dWrap.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node2.java

diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraph2.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraph2.java
new file mode 100644
index 00000000..d183880d
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraph2.java
@@ -0,0 +1,104 @@
+/** 
+ * A class that represents the irregular bipartite graph used in
+ * EM3D.  The graph contains two linked structures that represent the
+ * E nodes and the N nodes in the application.
+ **/
+public class BiGraph {
+    public BiGraph() {
+    }
+    /**
+     * Nodes that represent the electrical field.
+     **/
+    Node[] eNodes;
+    /**
+     * Nodes that representhe the magnetic field.
+     **/
+    Node[] hNodes;
+    
+    EVector [][] reversetable;
+    int numNodes;
+
+    /**
+     * Construct the bipartite graph.
+     * @param e the nodes representing the electric fields
+     * @param h the nodes representing the magnetic fields
+     **/ 
+    BiGraph(Node[] e, Node[] h) {
+	eNodes = e;
+	hNodes = h;
+    }
+    
+    /**
+     * Create the bi graph that contains the linked list of
+     * e and h nodes.
+     * @param numNodes the number of nodes to create
+     * @param numDegree the out-degree of each node
+     * @param verbose should we print out runtime messages
+     * @return the bi graph that we've created.
+     **/
+    
+    static BiGraph create(int numNodes, int degree, int numThreads) {
+	// making nodes (we create a table)
+	Node [] eTable = global new Node[numNodes];
+	Node [] hTable = global new Node[numNodes];
+	BiGraph g = global new BiGraph(eTable, hTable);
+	g.numNodes=numNodes;
+	g.reversetable=global new EVector[numThreads][];
+	return g;
+    }
+    
+    
+    /**
+     * 
+     *
+     * @return 
+     **/
+    public void allocateNodes( int indexBegin, int indexEnd, int threadIndex) { 
+	for(int i = indexBegin; i < indexEnd; i++ ) {
+	    eNodes[i]=global new Node();
+	    hNodes[i]=global new Node();
+	}
+	reversetable[threadIndex]=global new EVector[numNodes];
+    }
+    
+    public void initializeNodes(Node[] fromnodes, Node[] tonodes, int begin, int end, int degree, Random r, int threadIndex) {
+	for(int i = begin; i < end; i++ ) {
+	    Node n=fromnodes[i];
+	    n.init(degree, r.nextDouble());
+	    n.makeUniqueNeighbors(reversetable[threadIndex], tonodes, r, begin, end);
+	}
+    }
+    
+    /**
+     * 
+     *
+     * @return 
+     **/
+    
+    public void makeFromNodes(Node[] nodes, int indexBegin, int indexEnd, Random r) {
+	// Create the fromNodes and coeff field
+	int numthreads=reversetable.length;
+	for(int i = indexBegin; i < indexEnd; i++) {
+	    Node n = nodes[i];
+	    int count=0;
+	    for(int j=0;j<numthreads;j++) {
+		EVector v=reversetable[j][i];
+		if(v!=null)
+		    count+=v.size();
+	    }
+	    n.fromCount=count;
+	    n.fromNodes=global new Node[count];
+	    n.coeffs=global new double[count];
+	    count=0;
+	    for(int j=0;j<numthreads;j++) {
+		EVector v=reversetable[j][i];
+		if(v!=null) {
+		    for(int k=0;k<v.size();k++) {
+			n.fromNodes[count]=(Node)v.elementAt(k);
+			n.coeffs[count++]=r.nextDouble();
+		    }
+		}
+	    }
+	}
+    }
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/EVector.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/EVector.java
new file mode 100644
index 00000000..5e0496d5
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/EVector.java
@@ -0,0 +1,83 @@
+public class EVector {
+    Object[] array;
+    int size;
+    int capacityIncrement;
+
+    public EVector() {
+	capacityIncrement=0;
+	size=0;
+	array=global new Object[10];
+    }
+
+    public void clear() {
+	size=0;
+	array=global new Object[10];
+    }
+
+    public int indexOf(Object elem) {
+	return indexOf(elem, 0);
+    }
+
+    public int indexOf(Object elem, int index) {
+	for(int i=index;i<size;i++) {
+	    if (elem.equals(array[i]))
+		return i;
+	}
+	return -1;
+    }
+
+    public Object elementAt(int index) {
+	if (index<0 || index >=size) {
+	    System.printString("Illegal Vector.elementAt");
+	    return null;
+	}
+	return array[index];
+    }
+
+    public void setElementAt(Object obj, int index) {
+	if (index>=0 && index <size)
+	    array[index]=obj;
+	else
+	    System.printString("Illegal setElementAt");
+    }
+
+    private ensureCapacity(int minCapacity) {
+	if (minCapacity>array.length) {
+	    int newsize;
+	    if (capacityIncrement<=0)
+		newsize=array.length*2;
+	    else
+		newsize=array.length+capacityIncrement;
+	    if (newsize<minCapacity)
+		newsize=minCapacity;
+	    Object [] newarray=global new Object[minCapacity];
+	    for(int i=0;i<size;i++)
+		newarray[i]=array[i];
+	    array=newarray;
+	}
+    }
+
+    public int size() {
+	return size;
+    }
+
+    public Enumeration elements() {
+	System.printString("Vector.elements not implemented");
+    }
+
+    public void addElement(Object obj) {
+	if (size==array.length) {
+	    ensureCapacity(size+1);
+	}
+	array[size++]=obj;
+    }
+
+    public void removeElementAt(int index) {
+	if (index<0||index>=size)
+	    System.printString("Illegal remove");
+	for(int i=index;i<(size-1);i++) {
+	    array[i]=array[i+1];
+	}
+	size--;
+    }
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3d2.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3d2.java
new file mode 100644
index 00000000..2263e0f5
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3d2.java
@@ -0,0 +1,247 @@
+/** 
+ *
+ *
+ * Java implementation of the <tt>em3d</tt> Olden benchmark.  This Olden
+ * benchmark models the propagation of electromagnetic waves through
+ * objects in 3 dimensions. It is a simple computation on an irregular
+ * bipartite graph containing nodes representing electric and magnetic
+ * field values.
+ *
+ * <p><cite>
+ * D. Culler, A. Dusseau, S. Goldstein, A. Krishnamurthy, S. Lumetta, T. von 
+ * Eicken and K. Yelick. "Parallel Programming in Split-C".  Supercomputing
+ * 1993, pages 262-273.
+ * </cite>
+ **/
+public class Em3d extends Thread {
+
+  /**
+   * The number of nodes (E and H) 
+   **/
+  private int numNodes;
+  /**
+   * The out-degree of each node.
+   **/
+  private int numDegree;
+  /**
+   * The number of compute iterations 
+   **/
+  private int numIter;
+  /**
+   * Should we print the results and other runtime messages
+   **/
+  private boolean printResult;
+    /**
+     * Print information messages?
+     **/
+  private boolean printMsgs;
+
+    int threadindex;
+    int numThreads;
+
+  BiGraph bg;
+  int upperlimit;
+  int lowerlimit;
+  Barrier mybarr;
+    public Em3d() {
+    }
+
+    public Em3d(BiGraph bg, int lowerlimit, int upperlimit, int numIter, Barrier mybarr, int numDegree, int threadindex) {
+    this.bg = bg;
+    this.lowerlimit = lowerlimit;
+    this.upperlimit = upperlimit;
+    this.numIter = numIter;
+    this.mybarr = mybarr;
+    this.numDegree = numDegree;
+    this.threadindex=threadindex;
+  }
+
+  public void run() {
+    int iteration;
+    Barrier barr;
+    int degree;
+    Random random;
+
+    atomic {
+	iteration = numIter;
+	barr=mybarr;
+	degree = numDegree;
+	random = new Random(lowerlimit);
+    }
+
+    atomic {
+	//This is going to conflict badly...Minimize work here
+	bg.allocateNodes( lowerlimit, upperlimit, threadindex);
+    }
+    Barrier.enterBarrier(barr);
+
+    atomic {
+	//initialize the eNodes
+	bg.initializeNodes(bg.eNodes, bg.hNodes, lowerlimit, upperlimit, degree, random, threadindex);
+    }
+    Barrier.enterBarrier(barr);
+
+    atomic {
+	//initialize the hNodes
+	bg.initializeNodes(bg.hNodes, bg.eNodes, lowerlimit, upperlimit, degree, random, threadindex);
+    }
+    Barrier.enterBarrier(barr);
+
+    atomic {
+	bg.makeFromNodes(bg.hNodes, lowerlimit, upperlimit, random);
+    }
+    Barrier.enterBarrier(barr);
+
+    atomic {
+	bg.makeFromNodes(bg.eNodes, lowerlimit, upperlimit, random);
+    }
+    Barrier.enterBarrier(barr);
+
+    //Do the computation
+    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);
+	
+	/* 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);
+    }
+  }
+
+  /**
+   * The main roitine that creates the irregular, linked data structure
+   * that represents the electric and magnetic fields and propagates the
+   * waves through the graph.
+   * @param args the command line arguments
+   **/
+  public static void main(String args[]) {
+    Em3d em = new Em3d();
+    Em3d.parseCmdLine(args, em);
+    if (em.printMsgs) 
+      System.printString("Initializing em3d random graph...\n");
+    long start0 = System.currentTimeMillis();
+    int numThreads = em.numThreads;
+    int[] mid = new int[4];
+    mid[0] = (128<<24)|(195<<16)|(175<<8)|79;//dw-1
+    mid[1] = (128<<24)|(195<<16)|(175<<8)|80;//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;
+
+    
+    // initialization step 1: allocate BiGraph
+   // System.printString( "Allocating BiGraph.\n" );
+
+    atomic {
+      mybarr = global new Barrier(numThreads);
+      graph =  BiGraph.create(em.numNodes, em.numDegree, numThreads);
+    }
+
+    Em3dWrap[] em3d=new Em3dWrap[numThreads];    
+    int increment = em.numNodes/numThreads;
+
+
+    // initialization step 2: divide work of allocating nodes
+    // System.printString( "Launching distributed allocation of nodes.\n" );
+    
+    atomic {
+      int base=0;
+      for(int i=0;i<numThreads;i++) {
+	  Em3d tmp;
+	  if ((i+1)==numThreads)
+	      tmp = global new Em3d(graph, base, em.numNodes, em.numIter, mybarr, em.numDegree, 1);
+	  else
+	      tmp = global new Em3d(graph, base, base+increment, em.numIter, mybarr, em.numDegree, 1);
+	  em3d[i]=new Em3dWrap(tmp);
+	  base+=increment;
+      }
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+	em3d[i].em3d.start(mid[i]);
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+	em3d[i].em3d.join();
+    }
+  }
+
+
+  /**
+   * Parse the command line options.
+   * @param args the command line options.
+   **/
+
+  public static void parseCmdLine(String args[], Em3d em)
+  {
+    int i = 0;
+    String arg;
+
+    while (i < args.length && args[i].startsWith("-")) {
+      arg = args[i++];
+
+      // check for options that require arguments
+      if (arg.equals("-N")) {
+        if (i < args.length) {
+		em.numNodes = new Integer(args[i++]).intValue();
+        }
+      } else if (arg.equals("-T")) {
+        if (i < args.length) {
+		em.numThreads = new Integer(args[i++]).intValue();
+        }
+      } else if (arg.equals("-d")) {
+        if (i < args.length) {
+		em.numDegree = new Integer(args[i++]).intValue();
+        }
+      } else if (arg.equals("-i")) {
+        if (i < args.length) {
+            em.numIter = new Integer(args[i++]).intValue();
+        }
+      } else if (arg.equals("-p")) {
+	      em.printResult = true;
+      } else if (arg.equals("-m")) {
+	      em.printMsgs = true;
+      } else if (arg.equals("-h")) {
+        em.usage();
+      }
+    }
+
+    if (em.numNodes == 0 || em.numDegree == 0) 
+      em.usage();
+  }
+
+  /**
+   * The usage routine which describes the program options.
+   **/
+  public void usage()
+  {
+    System.printString("usage: java Em3d -T <threads> -N <nodes> -d <degree> [-p] [-m] [-h]\n");
+    System.printString("    -N the number of nodes\n");
+    System.printString("    -T the number of threads\n");
+    System.printString("    -d the out-degree of each node\n");
+    System.printString("    -i the number of iterations\n");
+    System.printString("    -p (print detailed results\n)");
+    System.printString("    -m (print informative messages)\n");
+    System.printString("    -h (this message)\n");
+  }
+
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3dWrap.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3dWrap.java
new file mode 100644
index 00000000..e6cf62a1
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3dWrap.java
@@ -0,0 +1,9 @@
+public class Em3dWrap {
+    public global Em3d em3d;
+    public Em3dWrap() {
+    }
+
+    public Em3dWrap(Em3d e) {
+	em3d=e;
+    }
+}
\ No newline at end of file
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node2.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node2.java
new file mode 100644
index 00000000..528ffb67
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node2.java
@@ -0,0 +1,121 @@
+/** 
+ * This class implements nodes (both E- and H-nodes) of the EM graph. Sets
+ * up random neighbors and propagates field values among neighbors.
+ */
+public class Node {
+    /**
+     * The value of the node.
+     **/
+    double value;
+    /**
+     * Array of nodes to which we send our value.
+     **/
+    Node[] toNodes;
+    /**
+     * Array of nodes from which we receive values.
+     **/
+    Node[] fromNodes;
+    /**
+     * Coefficients on the fromNodes edges
+     **/
+    double[] coeffs;
+    /**
+     * The number of fromNodes edges
+     **/
+    int fromCount;
+    /**
+     * Used to create the fromEdges - keeps track of the number of edges that have
+     * been added
+     **/
+    int fromLength;
+    
+    /** 
+     * Constructor for a node with given `degree'.   The value of the
+     * node is initialized to a random value.
+     **/
+    public Node() {
+    }
+    
+    public void init(int degree, double val) {
+	this.value=val;
+	// create empty array for holding toNodes
+	toNodes = global new Node[degree];
+    }
+    
+    /** 
+     * Create unique `degree' neighbors from the nodes given in nodeTable.
+     * We do this by selecting a random node from the give nodeTable to
+     * be neighbor. If this neighbor has been previously selected, then
+     * a different random neighbor is chosen.
+     * @param nodeTable the list of nodes to choose from.
+     **/
+    public void makeUniqueNeighbors(EVector[] reversetable,Node[] nodeTable, Random rand, int begin, int end) {
+	for (int filled = 0; filled < toNodes.length; filled++) {
+	    int k;
+	    Node otherNode;
+	    int index;
+	    do {
+		boolean isBreak = false;
+		// generate a random number in the correct range
+		index = rand.nextInt();
+		if (index < 0) index = -index;
+		//local vs remote from em3d benchmark
+		if ((rand.nextInt()%4)==0)
+		    index=index%nodeTable.length;
+		else
+		    index=begin+(index%(end-begin));
+		
+		// find a node with the random index in the given table
+		otherNode = nodeTable[index];
+		
+		for (k = 0; (k < filled) && (isBreak==false); k++) {
+		    if (otherNode == toNodes[k]) 
+			isBreak = true;
+		}
+	    } while (k < filled);
+	    
+	    // other node is definitely unique among "filled" toNodes
+	    toNodes[filled] = otherNode;
+	    
+	    // update fromCount for the other node
+	    if (reversetable[index]==null)
+		reversetable[index]=global new EVector();
+	    reversetable[index].addElement(this);
+	}
+    }
+
+    /** 
+     * Allocate the right number of FromNodes for this node. This
+     * step can only happen once we know the right number of from nodes
+     * to allocate. Can be done after unique neighbors are created and known.
+     *
+     * It also initializes random coefficients on the edges.
+     **/
+
+    public void makeFromNodes() {
+	fromNodes = global new Node[fromCount]; // nodes fill be filled in later
+	coeffs = global new double[fromCount];
+    }
+
+    /**
+     * Fill in the fromNode field in "other" nodes which are pointed to
+     * by this node.
+     **/
+    public void updateFromNodes(Random rand) { 
+	for (int i = 0; i < toNodes.length; i++) {
+	    Node otherNode = toNodes[i];
+	    int count = otherNode.fromLength++;
+	    otherNode.fromNodes[count] = this;
+	    otherNode.coeffs[count] = rand.nextDouble();
+	}
+    }
+    
+    /**
+     * Override the toString method to return the value of the node.
+     * @return the value of the node.
+     **/
+    public String toString() {
+	String returnString;
+	returnString = "value " + (long)value + ", from_count " + fromCount;
+    }
+}
-- 
2.34.1