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         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 static Node[] fillTable(int size, int degree, Random r)
  67     {
  68         Node[] table = global new Node[size];
  69
  70         Node prevNode = global new Node(degree, r);
  71         table[0] = prevNode;
  72         for (int i = 1; i < size; i++) {
  73             Node curNode = global 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==false); 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      * Allocate the right number of FromNodes for this node. This
 122      * step can only happen once we know the right number of from nodes
 123      * to allocate. Can be done after unique neighbors are created and known.
 124      *
 125      * It also initializes random coefficients on the edges.
 126      **/
 127     public void makeFromNodes()
 128     {
 129         fromNodes = global new Node[fromCount]; // nodes fill be filled in later
 130         coeffs = global new double[fromCount];
 131     }
 132
 133     /**
 134      * Fill in the fromNode field in "other" nodes which are pointed to
 135      * by this node.
 136      **/
 137     public void updateFromNodes(Random rand)
 138     {
 139         for (int i = 0; i < toNodes.length; i++) {
 140             Node otherNode = toNodes[i];
 141             int count = otherNode.fromLength++;
 142             otherNode.fromNodes[count] = this;
 143             otherNode.coeffs[count] = rand.nextDouble();
 144         }
 145     }
 146
 147     /**
 148      * Get the new value of the current node based on its neighboring
 149      * from_nodes and coefficients.
 150      **/
 151
 152     /*
 153     public void computeNewValue()
 154     {
 155         for (int i = 0; i < fromCount; i++) {
 156             value -= coeffs[i] * fromNodes[i].value;
 157         }
 158     }
 159     */
 160
 161     /**
 162      * Override the toString method to return the value of the node.
 163      * @return the value of the node.
 164      **/
 165     public String toString()
 166     {
 167         String returnString;
 168         returnString = "value " + (long)value + ", from_count " + fromCount;
 169         //return "value " + value + ", from_count " + fromCount;
 170     }
 171
 172 }