Robust/src/Benchmarks/Prefetch/Em3d/dsm/Node.java

   1 /**
   2  * This class implements nodes (both E- and H-nodes) of the EM graph. Sets
   3  * up random neighbors and propagates field values among neighbors.
   4  */
   5 public class Node {
   6   /**
   7    * The value of the node.
   8    **/
   9   double value;
  10   /**
  11    * The next node in the list.
  12    **/
  13   protected Node next;
  14   /**
  15    * Array of nodes to which we send our value.
  16    **/
  17   Node[] toNodes;
  18   /**
  19    * Array of nodes from which we receive values.
  20    **/
  21   Node[] fromNodes;
  22   /**
  23    * Coefficients on the fromNodes edges
  24    **/
  25   double[] coeffs;
  26   /**
  27    * The number of fromNodes edges
  28    **/
  29   int fromCount;
  30   /**
  31    * Used to create the fromEdges - keeps track of the number of edges that have
  32    * been added
  33    **/
  34   int fromLength;
  35
  36   public Node() {
  37
  38   }
  39
  40   /**
  41    * Constructor for a node with given `degree'.   The value of the
  42    * node is initialized to a random value.
  43    **/
  44   public Node(int degree, Random r)
  45   {
  46     value = r.nextDouble();
  47     // create empty array for holding toNodes
  48     toNodes = global new Node[degree];
  49   }
  50
  51   /**
  52    * Create the linked list of E or H nodes.  We create a table which is used
  53    * later to create links among the nodes.
  54    * @param size the no. of nodes to create
  55    * @param degree the out degree of each node
  56    * @return a table containing all the nodes.
  57    **/
  58   public static Node[] fillTable(int size, int degree, Random r)
  59   {
  60     Node[] table;
  61     Node prevNode;
  62     table = global new Node[size];
  63     prevNode = global new Node(degree, r);
  64     table[0] = prevNode;
  65     for (int i = 1; i < size; i++) {
  66         Node curNode = global new Node(degree, r);
  67         table[i] = curNode;
  68         prevNode.next = curNode;
  69         prevNode = curNode;
  70     }
  71     return table;
  72   }
  73
  74   /**
  75    * Create unique `degree' neighbors from the nodes given in nodeTable.
  76    * We do this by selecting a random node from the give nodeTable to
  77    * be neighbor. If this neighbor has been previously selected, then
  78    * a different random neighbor is chosen.
  79    * @param nodeTable the list of nodes to choose from.
  80    **/
  81   public void makeUniqueNeighbors(Node[] nodeTable, Random rand)
  82   {
  83     for (int filled = 0; filled < toNodes.length; filled++) {
  84       int k;
  85       Node otherNode;
  86
  87       do {
  88         boolean isBreak = false;
  89         // generate a random number in the correct range
  90         int index = rand.nextInt();
  91         if (index < 0) index = -index;
  92         index = index % nodeTable.length;
  93
  94         // find a node with the random index in the given table
  95         otherNode = nodeTable[index];
  96
  97         for (k = 0; (k < filled) && (isBreak==false); k++) {
  98           if (otherNode == toNodes[filled])
  99             isBreak = true;
 100         }
 101       } while (k < filled);
 102
 103       // other node is definitely unique among "filled" toNodes
 104       toNodes[filled] = otherNode;
 105
 106       // update fromCount for the other node
 107       otherNode.fromCount++;
 108     }
 109   }
 110
 111   /**
 112    * Allocate the right number of FromNodes for this node. This
 113    * step can only happen once we know the right number of from nodes
 114    * to allocate. Can be done after unique neighbors are created and known.
 115    *
 116    * It also initializes random coefficients on the edges.
 117    **/
 118   public void makeFromNodes()
 119   {
 120     fromNodes = global new Node[fromCount]; // nodes fill be filled in later
 121     coeffs = global new double[fromCount];
 122   }
 123
 124   /**
 125    * Fill in the fromNode field in "other" nodes which are pointed to
 126    * by this node.
 127    **/
 128   public void updateFromNodes(Random rand)
 129   {
 130     for (int i = 0; i < toNodes.length; i++) {
 131       Node otherNode = toNodes[i];
 132       int count = otherNode.fromLength++;
 133       otherNode.fromNodes[count] = this;
 134       otherNode.coeffs[count] = rand.nextDouble();
 135     }
 136   }
 137
 138   /**
 139    * Override the toString method to return the value of the node.
 140    * @return the value of the node.
 141    **/
 142   public String toString()
 143   {
 144     String returnString;
 145     returnString = "value " + (long)value + ", from_count " + fromCount;
 146   }
 147
 148 }