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