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

   1 import java.util.Random;
   2 /**
   3  * This class implements nodes (both E- and H-nodes) of the EM graph. Sets
   4  * up random neighbors and propagates field values among neighbors.
   5  */
   6 public class Node {
   7     /**
   8      * The value of the node.
   9      **/
  10     double value;
  11     /**
  12      * The next node in the list.
  13      **/
  14     protected Node next;
  15     /**
  16      * Array of nodes to which we send our value.
  17      **/
  18     Node[] toNodes;
  19     /**
  20      * Array of nodes from which we receive values.
  21      **/
  22     Node[] fromNodes;
  23     /**
  24      * Coefficients on the fromNodes edges
  25      **/
  26     double[] coeffs;
  27     /**
  28      * The number of fromNodes edges
  29      **/
  30     int fromCount;
  31     /**
  32      * Used to create the fromEdges - keeps track of the number of edges that have
  33      * been added
  34      **/
  35     int fromLength;
  36
  37     public Node() {
  38
  39     }
  40
  41     /**
  42      * Constructor for a node with given `degree'.   The value of the
  43      * node is initialized to a random value.
  44      **/
  45     public Node(int degree, Random r)
  46     {
  47         value = r.nextDouble();
  48         // create empty array for holding toNodes
  49         toNodes = new Node[degree];
  50
  51         next = null;
  52         for (int i = 0; i<fromCount; i++) {
  53             fromNodes[i] = null;
  54             coeffs[i] = 0.0;
  55         }
  56
  57         //coeffs = null;
  58         fromCount = 0;
  59         fromLength = 0;
  60     }
  61
  62     /**
  63      * Create the linked list of E or H nodes.  We create a table which is used
  64      * later to create links among the nodes.
  65      * @param size the no. of nodes to create
  66      * @param degree the out degree of each node
  67      * @return a table containing all the nodes.
  68      **/
  69     public static Node[] fillTable(int size, int degree, Random r)
  70     {
  71         Node[] table = new Node[size];
  72
  73         Node prevNode = new Node(degree, r);
  74         table[0] = prevNode;
  75         for (int i = 1; i < size; i++) {
  76             Node curNode = new Node(degree, r);
  77             table[i] = curNode;
  78             prevNode.next = curNode;
  79             prevNode = curNode;
  80         }
  81         return table;
  82     }
  83
  84     /**
  85      * Create unique `degree' neighbors from the nodes given in nodeTable.
  86      * We do this by selecting a random node from the give nodeTable to
  87      * be neighbor. If this neighbor has been previously selected, then
  88      * a different random neighbor is chosen.
  89      * @param nodeTable the list of nodes to choose from.
  90      **/
  91     public void makeUniqueNeighbors(Node[] nodeTable, Random rand)
  92     {
  93         for (int filled = 0; filled < toNodes.length; filled++) {
  94             int k;
  95             Node otherNode;
  96
  97             do {
  98                 // generate a random number in the correct range
  99                 int index = rand.nextInt();
 100                 if (index < 0) index = -index;
 101                 index = index % nodeTable.length;
 102
 103                 // find a node with the random index in the given table
 104                 otherNode = nodeTable[index];
 105
 106                 for (k = 0; k < filled; k++) {
 107                     if (otherNode == toNodes[filled])
 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     public void makeUniqueNeighborsThread(Node[] nodeTable, Random rand, int l, int u)
 121     {
 122         for (int filled = 0; filled < toNodes.length; filled++) {
 123             int k;
 124             Node otherNode;
 125
 126             do {
 127                 // generate a random number in the correct range
 128                 int index = rand.nextInt();
 129                 if (index < 0) index = -index;
 130                 index = index % nodeTable.length;
 131
 132                 // find a node with the random index in the given table
 133                 otherNode = nodeTable[index];
 134
 135                 for (k = 0; k < filled; k++) {
 136                     if (otherNode == toNodes[filled])
 137                         break;
 138                 }
 139             } while (k < filled);
 140
 141             // other node is definitely unique among "filled" toNodes
 142             toNodes[filled] = otherNode;
 143
 144             // update fromCount for the other node
 145             otherNode.fromCount++;
 146         }
 147     }
 148
 149
 150     /**
 151      * Allocate the right number of FromNodes for this node. This
 152      * step can only happen once we know the right number of from nodes
 153      * to allocate. Can be done after unique neighbors are created and known.
 154      *
 155      * It also initializes random coefficients on the edges.
 156      **/
 157     public void makeFromNodes()
 158     {
 159         fromNodes = new Node[fromCount]; // nodes fill be filled in later
 160         coeffs = new double[fromCount];
 161     }
 162
 163     /**
 164      * Fill in the fromNode field in "other" nodes which are pointed to
 165      * by this node.
 166      **/
 167     public void updateFromNodes(Random rand)
 168     {
 169         for (int i = 0; i < toNodes.length; i++) {
 170             Node otherNode = toNodes[i];
 171             int count = otherNode.fromLength++;
 172             otherNode.fromNodes[count] = this;
 173             otherNode.coeffs[count] = rand.nextDouble();
 174         }
 175     }
 176
 177     /**
 178      * Get the new value of the current node based on its neighboring
 179      * from_nodes and coefficients.
 180      **/
 181     /*
 182     public void run() {
 183         Node tmp = this;
 184         while(tmp!= null) {
 185             Node n = tmp;
 186             for (int i = 0; i < n.fromCount; i++) {
 187                 n.value -= n.coeffs[i] * n.fromNodes[i].value;
 188             }
 189             tmp = tmp.next;
 190         }
 191     }
 192     */
 193
 194     public void computeNewValue()
 195     {
 196         for (int i = 0; i < fromCount; i++) {
 197             value -= coeffs[i] * fromNodes[i].value;
 198         }
 199     }
 200
 201     /**
 202      * Override the toString method to return the value of the node.
 203      * @return the value of the node.
 204      **/
 205     public String toString()
 206     {
 207         return "value " + value + ", from_count " + fromCount;
 208     }
 209
 210 }