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