From b6e4cdc7983f36eecbdd72b86e7608b5a1f92204 Mon Sep 17 00:00:00 2001
From: adash <adash>
Date: Sun, 13 Apr 2008 04:11:39 +0000
Subject: [PATCH] New benchmark

---
 .../Benchmarks/Prefetch/Em3d/dsm/Barrier.java |  52 ++++
 .../Benchmarks/Prefetch/Em3d/dsm/BiGraph.java | 108 ++++++++
 .../Benchmarks/Prefetch/Em3d/dsm/Em3d.java    | 252 ++++++++++++++++++
 .../Benchmarks/Prefetch/Em3d/dsm/Node.java    | 217 +++++++++++++++
 .../src/Benchmarks/Prefetch/Em3d/dsm/makefile |  15 ++
 5 files changed, 644 insertions(+)
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/Barrier.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraph.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3d.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java
 create mode 100644 Robust/src/Benchmarks/Prefetch/Em3d/dsm/makefile

diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Barrier.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Barrier.java
new file mode 100644
index 00000000..482b695a
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Barrier.java
@@ -0,0 +1,52 @@
+public class Barrier {
+  int numthreads;
+  int entercount;
+  boolean cleared;
+
+  public Barrier(int n) {
+    numthreads=n;
+    cleared = false;
+    entercount = 0;
+  }
+
+  public Barrier() {
+  }
+
+  public void reset() {
+    cleared = false;
+    entercount = 0;
+  }
+
+  public static void enterBarrier(Barrier b) {
+    int tmp;
+    boolean retry=true;
+
+    do {
+      atomic {
+        if (!b.cleared) {
+          b.entercount++;
+          tmp = b.entercount;
+          if (tmp==b.numthreads) {
+            if(b.numthreads > 1)
+              b.cleared=true;
+            b.entercount--;
+            return;
+          }
+          retry=false;
+        }
+      }
+    } while(retry);
+
+    while(true) {
+      atomic {
+        if (b.cleared) {
+          b.entercount--;
+          int count = b.entercount;
+          if (count==0)
+            b.cleared=false;
+          return;
+        }
+      }
+    }
+  }
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraph.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraph.java
new file mode 100644
index 00000000..f952f7e2
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/BiGraph.java
@@ -0,0 +1,108 @@
+/** 
+ * 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;
+
+  /**
+   * 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.
+   **/
+
+  BiGraph create(int numNodes, int numDegree, boolean verbose, Random r)
+  {
+    Node newnode = new Node();
+
+    // making nodes (we create a table)
+    //if (verbose) System.printString("making nodes (tables in orig. version)");
+    Node[] hTable = newnode.fillTable(numNodes, numDegree, r);
+    Node[] eTable = newnode.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);
+    }
+
+    BiGraph g = new BiGraph(eTable[0], hTable[0]);
+    return g;
+  }
+
+  /**
+   * 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.
+   **/
+  public String toString()
+  {
+      StringBuffer retval = new StringBuffer();
+      Node tmp = eNodes;
+      while(tmp!=null) {
+          Node n = tmp;
+          retval.append("E: " + n + "\n");
+          tmp = tmp.next;
+      }
+      tmp = hNodes;
+      while(tmp!=null) {
+          Node n = tmp;
+          retval.append("H: " + n + "\n");
+          tmp = tmp.next;
+      }
+      return retval.toString();
+  }
+
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3d.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3d.java
new file mode 100644
index 00000000..28ffe641
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Em3d.java
@@ -0,0 +1,252 @@
+/** 
+ *
+ *
+ * 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;
+
+  BiGraph bg;
+  int upperlimit;
+  int lowerlimit;
+  //Random rand;
+  Barrier mybarr;
+
+  public Em3d() {
+    numNodes = 0;
+    numDegree = 0;
+    numIter = 1;
+    printResult = false;
+    printMsgs = false;
+  }
+
+  public Em3d(BiGraph bg, int lowerlimit, int upperlimit, int numIter, Barrier mybarr) {
+    this.bg = bg;
+    this.lowerlimit = lowerlimit;
+    this.upperlimit = upperlimit;
+    this.numIter = numIter;
+    this.mybarr = mybarr;
+  }
+
+  public void run() {
+    int iteration;
+    atomic {
+      iteration = numIter;
+    }
+
+    for (int i = 0; i < iteration; i++) {
+      Barrier runBarrier = new Barrier();
+      /* for  eNodes */
+      Node prev, curr;
+      atomic {
+        prev = bg.eNodes;
+        curr = null;
+        for(int j = 0; j<lowerlimit; j++){
+          curr = prev;
+          prev = prev.next;
+        }
+        for(int j = lowerlimit; j<=upperlimit; j++) {
+          Node n = curr;
+          for (int k = 0; k < n.fromCount; k++) {
+            n.value -= n.coeffs[k] * n.fromNodes[k].value;
+          }
+          curr = curr.next;
+        }
+        runBarrier.enterBarrier(mybarr);
+        //mybarr.reset();
+      }
+
+      /* for  hNodes */
+      atomic {
+        prev = bg.hNodes;
+        curr = null;
+        for(int j = 0; j<lowerlimit; j++){
+          curr = prev;
+          prev = prev.next;
+        }
+        for(int j = lowerlimit; j<=upperlimit; j++) {
+          Node n = curr;
+          for (int k = 0; k < n.fromCount; k++) {
+            n.value -= n.coeffs[k] * n.fromNodes[k].value;
+          }
+          curr = curr.next;
+        }
+        runBarrier.enterBarrier(mybarr);
+        //mybarr.reset();
+      }
+    }
+  }
+
+  /**
+   * 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[])
+  {
+    Random rand = new Random(783);
+    Em3d em;
+    atomic {
+      em = global new Em3d();
+      em.parseCmdLine(args, em);
+    }
+    boolean printMsgs, printResult;
+    int numIter;
+    atomic {
+      printMsgs = em.printMsgs;
+      numIter = em.numIter;
+      printResult = em.printResult;
+    }
+    if (printMsgs) 
+      System.printString("Initializing em3d random graph...");
+    long start0 = System.currentTimeMillis();
+    int numThreads = 2;
+    System.printString("DEBUG -> numThreads = " + numThreads);
+    Barrier mybarr;
+    atomic {
+      mybarr = global new Barrier(numThreads);
+    }
+    BiGraph graph;
+    BiGraph graph1;
+    atomic {
+      graph1 = global new BiGraph();
+      graph = global new BiGraph();
+      graph =  graph1.create(em.numNodes, em.numDegree, em.printResult, rand);
+    }
+
+    long end0 = System.currentTimeMillis();
+
+    // compute a single iteration of electro-magnetic propagation
+    if (printMsgs) 
+      System.printString("Propagating field values for " + numIter + 
+          " iteration(s)...");
+    long start1 = System.currentTimeMillis();
+    Em3d[] em3d;
+    atomic {
+      em3d = global new Em3d[numThreads];
+    }
+
+    atomic {
+      em3d[0] = global new Em3d(graph, 1, em.numNodes/2, em.numIter, mybarr);
+      em3d[1] = global new Em3d(graph, (em.numNodes/2)+1, em.numNodes, em.numIter, mybarr);
+    }
+
+    int mid = (128<<24)|(195<<16)|(175<<8)|73;
+    Em3d tmp;
+    for(int i = 0; i<numThreads; i++) {
+      atomic {
+        tmp = em3d[i];
+      }
+      tmp.start(mid);
+    }
+
+    for(int i = 0; i<numThreads; i++) {
+      atomic { 
+        tmp = em3d[i];
+      }
+      tmp.join();
+    }
+    long end1 = System.currentTimeMillis();
+
+    // print current field values
+    if (printResult) {
+      //System.printString(graph);
+    }
+
+    if (printMsgs) {
+      System.printString("EM3D build time "+ (long)((end0 - start0)/1000.0));
+      System.printString("EM3D compute time " + (long)((end1 - start1)/1000.0));
+      System.printString("EM3D total time " + (long)((end1 - start0)/1000.0));
+    }
+    System.printString("Done!");
+  }
+
+
+  /**
+   * Parse the command line options.
+   * @param args the command line options.
+   **/
+
+  public 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("-d")) {
+        if (i < args.length) {
+          em.numDegree = new Integer(args[i++]).intValue();
+        }
+      } else if (arg.equals("-i")) {
+        if (i < args.length) {
+          atomic {
+            em.numIter = global 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 -n <nodes> -d <degree> [-p] [-m] [-h]");
+    System.printString("    -n the number of nodes");
+    System.printString("    -d the out-degree of each node");
+    System.printString("    -i the number of iterations");
+    System.printString("    -p (print detailed results)");
+    System.printString("    -m (print informative messages)");
+    System.printString("    -h (this message)");
+  }
+
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java
new file mode 100644
index 00000000..6c5095b5
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java
@@ -0,0 +1,217 @@
+/** 
+ * 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;
+    /**
+     * The next node in the list.
+     **/
+    protected Node next;
+    /**
+     * 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;
+
+    public Node() {
+
+    }
+
+    /** 
+     * Constructor for a node with given `degree'.   The value of the
+     * node is initialized to a random value.
+     **/
+    public Node(int degree, Random r) 
+    {
+        value = r.nextDouble();
+        // create empty array for holding toNodes
+        toNodes = new Node[degree];
+
+        next = null;
+        for (int i = 0; i<fromCount; i++) {
+            fromNodes[i] = null;
+            coeffs[i] = 0.0;
+        }
+        fromCount = 0;
+        fromLength = 0;
+    }
+
+    /**
+     * Create the linked list of E or H nodes.  We create a table which is used
+     * later to create links among the nodes.
+     * @param size the no. of nodes to create
+     * @param degree the out degree of each node
+     * @return a table containing all the nodes.
+     **/
+    public Node[] fillTable(int size, int degree, Random r)
+    {
+        Node[] table = new Node[size];
+
+        Node prevNode = new Node(degree, r);
+        table[0] = prevNode;
+        for (int i = 1; i < size; i++) {
+            Node curNode = new Node(degree, r);
+            table[i] = curNode;
+            prevNode.next = curNode;
+            prevNode = curNode;
+        }
+        return table;
+    }
+
+    /** 
+     * 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(Node[] nodeTable, Random rand)
+    {
+        for (int filled = 0; filled < toNodes.length; filled++) {
+            int k;
+            Node otherNode;
+            boolean isBreak;
+
+            do {
+                isBreak = false;
+                // generate a random number in the correct range
+                int index = rand.nextInt();
+                if (index < 0) index = -index;
+                index = index % nodeTable.length;
+
+                // find a node with the random index in the given table
+                otherNode = nodeTable[index];
+
+                for (k = 0; (k < filled) && (!isBreak); k++) {
+                    if (otherNode == toNodes[filled]) 
+                        isBreak = true;
+                        //break;
+                }
+            } while (k < filled);
+
+            // other node is definitely unique among "filled" toNodes
+            toNodes[filled] = otherNode;
+
+            // update fromCount for the other node
+            otherNode.fromCount++;
+        }
+    }
+
+    /*
+    public void makeUniqueNeighborsThread(Node[] nodeTable, Random rand, int l, int u)
+    {
+        for (int filled = 0; filled < toNodes.length; filled++) {
+            int k;
+            Node otherNode;
+            boolean isBreak;
+
+            do {
+                isBreak = false;
+                // generate a random number in the correct range
+                int index = rand.nextInt();
+                if (index < 0) index = -index;
+                index = index % nodeTable.length;
+
+                // find a node with the random index in the given table
+                otherNode = nodeTable[index];
+
+                for (k = 0; (k < filled) && (!isBreak); k++) {
+                    if (otherNode == toNodes[filled]) 
+                        isBreak = true;
+                        //break;
+                }
+            } while (k < filled);
+
+            // other node is definitely unique among "filled" toNodes
+            toNodes[filled] = otherNode;
+
+            // update fromCount for the other node
+            otherNode.fromCount++;
+        }
+    }
+    */
+
+
+    /** 
+     * 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();
+        }
+    }
+
+    /** 
+     * Get the new value of the current node based on its neighboring
+     * from_nodes and coefficients.
+     **/
+    /*
+    public void run() {
+        Node tmp = this;
+        while(tmp!= null) {
+            Node n = tmp;
+            for (int i = 0; i < n.fromCount; i++) {
+                n.value -= n.coeffs[i] * n.fromNodes[i].value;
+            }
+            tmp = tmp.next;
+        }
+    }
+
+    public void computeNewValue()
+    {
+        for (int i = 0; i < fromCount; i++) {
+            value -= coeffs[i] * fromNodes[i].value;
+        }
+    }
+    */
+
+    /**
+     * 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;
+        //return "value " + value + ", from_count " + fromCount;
+    }
+
+}
diff --git a/Robust/src/Benchmarks/Prefetch/Em3d/dsm/makefile b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/makefile
new file mode 100644
index 00000000..014098e1
--- /dev/null
+++ b/Robust/src/Benchmarks/Prefetch/Em3d/dsm/makefile
@@ -0,0 +1,15 @@
+MAINCLASS=Em3d
+SRC=${MAINCLASS}.java \
+	BiGraph.java \
+	Node.java \
+	Barrier.java
+FLAGS=-dsm -prefetch -optimize -profile -debug -mainclass ${MAINCLASS} -o ${MAINCLASS}
+FLAGS2=-dsm -optimize -printflat -profile -debug -mainclass ${MAINCLASS} -o ${MAINCLASS}NP
+
+default:
+	../../../../buildscript ${FLAGS2} ${SRC}
+	../../../../buildscript ${FLAGS} ${SRC}
+
+clean:
+	rm -rf tmpbuilddirectory
+	rm *.bin
-- 
2.34.1