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