From 78f86fad39a1ea1361bdef1bcb68d5f14d341098 Mon Sep 17 00:00:00 2001
From: adash <adash>
Date: Mon, 27 Oct 2008 19:55:34 +0000
Subject: [PATCH] Java non transactional version for Em3d

---
 .../Em3d/javasingle/BarrierNonDSM.java        |  50 ++++
 .../Prefetch/Em3d/javasingle/BiGraph2.java    | 107 ++++++++
 .../Prefetch/Em3d/javasingle/EVector.java     |  83 ++++++
 .../Prefetch/Em3d/javasingle/Em3d2.java       | 249 ++++++++++++++++++
 .../Prefetch/Em3d/javasingle/Em3dWrap.java    |   9 +
 .../Prefetch/Em3d/javasingle/Node2.java       | 122 +++++++++
 .../Prefetch/Em3d/javasingle/makefile         |  13 +
 7 files changed, 633 insertions(+)
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/javasingle/BarrierNonDSM.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/javasingle/BiGraph2.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/javasingle/EVector.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Em3d2.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Em3dWrap.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Node2.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/javasingle/makefile

diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/BarrierNonDSM.java b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/BarrierNonDSM.java
new file mode 100644
index 00000000..db27fbb5
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/BarrierNonDSM.java
@@ -0,0 +1,50 @@
+public class BarrierServer {
+  int numthreads;
+  boolean done;
+
+  public BarrierServer(int n) {
+    numthreads=n;
+    done=false;
+  }
+
+  public void run() {
+    int n;
+    ServerSocket ss=new ServerSocket(2000);
+    n=numthreads;
+    done=true;
+    Socket ar[]=new Socket[n];
+    for(int i=0; i<n; i++) {
+      ar[i]=ss.accept();
+    }
+
+    while(true) {
+      for(int j=0; j<n; j++) {
+        Socket s=ar[j];
+        byte b[]=new byte[1];
+        while(s.read(b)!=1) {
+          ;
+        }
+      }
+      byte b[]=new byte[1];
+      b[0]= (byte) 'A';
+      for(int j=0; j<n; j++)
+        ar[j].write(b);
+    }
+  }
+}
+
+public class Barrier {
+  Socket s;
+  public Barrier(String name) {
+    s=new Socket(name, 2000);
+  }
+
+  public static void enterBarrier(Barrier barr) {
+    byte b[]=new byte[1];
+    b[0]=(byte)'A';
+    barr.s.write(b);
+    while(barr.s.read(b)!=1) {
+      ;
+    }
+  }
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/BiGraph2.java b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/BiGraph2.java
new file mode 100644
index 00000000..fc9776e6
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/BiGraph2.java
@@ -0,0 +1,107 @@
+/** 
+ * 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 [][] ereversetable;
+    EVector [][] hreversetable;
+    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 = new Node[numNodes];
+	Node [] hTable = new Node[numNodes];
+	BiGraph g = new BiGraph(eTable, hTable);
+	g.numNodes=numNodes;
+	g.ereversetable=new EVector[numThreads][];
+	g.hreversetable=new EVector[numThreads][];
+	return g;
+    }
+    
+    
+    /**
+     * 
+     *
+     * @return 
+     **/
+    public void allocateNodes( int indexBegin, int indexEnd, int threadIndex) { 
+	for(int i = indexBegin; i < indexEnd; i++ ) {
+	    eNodes[i]=new Node();
+	    hNodes[i]=new Node();
+	}
+	ereversetable[threadIndex]=new EVector[numNodes];
+	hreversetable[threadIndex]=new EVector[numNodes];
+    }
+    
+    public void initializeNodes(Node[] fromnodes, Node[] tonodes, EVector[][] reversetable, 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, EVector reversetable[][], 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=new Node[count];
+	    n.coeffs=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/javasingle/EVector.java b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/EVector.java
new file mode 100644
index 00000000..b646d592
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/EVector.java
@@ -0,0 +1,83 @@
+public class EVector {
+    Object[] array;
+    int size;
+    int capacityIncrement;
+
+    public EVector() {
+	capacityIncrement=0;
+	size=0;
+	array=new Object[10];
+    }
+
+    public void clear() {
+	size=0;
+	array=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=new Object[newsize];
+	    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/javasingle/Em3d2.java b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Em3d2.java
new file mode 100644
index 00000000..0abfad2b
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Em3d2.java
@@ -0,0 +1,249 @@
+/** 
+ *
+ *
+ * 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 {
+
+  /**
+   * 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;
+  public Em3d() {
+  }
+
+  public Em3d(BiGraph bg, int lowerlimit, int upperlimit, int numIter, int numDegree, int threadindex) {
+    this.bg = bg;
+    this.lowerlimit = lowerlimit;
+    this.upperlimit = upperlimit;
+    this.numIter = numIter;
+    this.numDegree = numDegree;
+    this.threadindex=threadindex;
+  }
+
+  public void run() {
+    int iteration;
+    //Barrier barr;
+    int degree;
+    Random random;
+    String hname;
+
+    //barr = new Barrier("128.195.175.84");
+    iteration = numIter;
+    degree = numDegree;
+    random = new Random(lowerlimit);
+
+    //This is going to conflict badly...Minimize work here
+    bg.allocateNodes ( lowerlimit, upperlimit, threadindex);
+    //Barrier.enterBarrier(barr);
+
+
+    //initialize the eNodes
+    bg.initializeNodes(bg.eNodes, bg.hNodes, bg.hreversetable, lowerlimit, upperlimit, degree, random, threadindex);
+    //Barrier.enterBarrier(barr);
+
+    //initialize the hNodes
+    bg.initializeNodes(bg.hNodes, bg.eNodes, bg.ereversetable, lowerlimit, upperlimit, degree, random, threadindex);
+    //Barrier.enterBarrier(barr);
+
+    bg.makeFromNodes(bg.hNodes, bg.hreversetable, lowerlimit, upperlimit, random);
+    //Barrier.enterBarrier(barr);
+
+    bg.makeFromNodes(bg.eNodes, bg.ereversetable, lowerlimit, upperlimit, random);
+    //Barrier.enterBarrier(barr);
+
+    //Do the computation
+    for (int i = 0; i < iteration; i++) {
+      /* for  eNodes */
+      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 */
+      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[8];
+    mid[0] = (128<<24)|(195<<16)|(175<<8)|84;//dw-10
+    mid[1] = (128<<24)|(195<<16)|(175<<8)|85;//dw-11
+    mid[2] = (128<<24)|(195<<16)|(175<<8)|86;//dw-12
+    mid[3] = (128<<24)|(195<<16)|(175<<8)|87;//dw-13
+    mid[4] = (128<<24)|(195<<16)|(175<<8)|88;//dw-14
+    mid[5] = (128<<24)|(195<<16)|(175<<8)|89;//dw-15
+    mid[6] = (128<<24)|(195<<16)|(175<<8)|90;//dw-16
+    mid[7] = (128<<24)|(195<<16)|(175<<8)|91;//dw-17
+    */
+
+    System.printString("DEBUG -> numThreads = " + numThreads+"\n");
+    //BarrierServer mybarr;
+    BiGraph graph;
+
+
+    // initialization step 1: allocate BiGraph
+    // System.printString( "Allocating BiGraph.\n" );
+
+    //mybarr = new BarrierServer(numThreads);
+    graph =  BiGraph.create(em.numNodes, em.numDegree, numThreads);
+    //mybarr.run();
+    //mybarr.start(mid[0]);
+
+
+    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" );
+
+    int base=0;
+    for(int i=0;i<numThreads;i++) {
+      Em3d tmp;
+      if ((i+1)==numThreads)
+        tmp = new Em3d(graph, base, em.numNodes, em.numIter, em.numDegree, i);
+      else
+        tmp = new Em3d(graph, base, base+increment, em.numIter, em.numDegree, i);
+      em3d[i]=new Em3dWrap(tmp);
+      base+=increment;
+    }
+
+/*
+    boolean waitfordone=true;
+    while(waitfordone) {
+      if (mybarr.done)
+        waitfordone=false;
+    }
+    */
+
+    //System.printString("Starting Barrier run\n");
+    for(int i = 0; i<numThreads; i++) {
+      //em3d[i].em3d.start(mid[i]);
+      em3d[i].em3d.run();
+    }
+    /*
+    for(int i = 0; i<numThreads; i++) {
+      em3d[i].em3d.join();
+    }
+    */
+    System.printString("Done!"+ "\n");
+  }
+
+
+  /**
+   * 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/javasingle/Em3dWrap.java b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Em3dWrap.java
new file mode 100644
index 00000000..18fdfc60
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Em3dWrap.java
@@ -0,0 +1,9 @@
+public class Em3dWrap {
+    public Em3d em3d;
+    public Em3dWrap() {
+    }
+
+    public Em3dWrap(Em3d e) {
+	em3d=e;
+    }
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Node2.java b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Node2.java
new file mode 100644
index 00000000..07152b2e
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/Node2.java
@@ -0,0 +1,122 @@
+/** 
+ * 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 = 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) {
+	int len=toNodes.length;
+	for (int filled = 0; filled < len; 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 (filled<(len/4))
+		    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]=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 = new Node[fromCount]; // nodes fill be filled in later
+	coeffs = 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;
+    }
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/makefile b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/makefile
new file mode 100644
index 00000000..9242ab44
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/javasingle/makefile
@@ -0,0 +1,13 @@
+MAINCLASS=Em3d
+SRC=${MAINCLASS}2.java \
+	${MAINCLASS}Wrap.java \
+	BiGraph2.java \
+	Node2.java \
+	EVector.java \
+	BarrierNonDSM.java
+default:
+	../../../../buildscript -optimize -mainclass ${MAINCLASS} ${SRC} -o ${MAINCLASS}
+
+clean:
+	rm -rf tmpbuilddirectory
+	rm *.bin
-- 
2.34.1