source/blog/posts/2010/08/14-memory-allocation/em3d.d

   1 /**
   2  * Java implementation of the <tt>em3d</tt> Olden benchmark.  This Olden
   3  * benchmark models the propagation of electromagnetic waves through
   4  * objects in 3 dimensions. It is a simple computation on an irregular
   5  * bipartite graph containing nodes representing electric and magnetic
   6  * field values.
   7  *
   8  * <p><cite>
   9  * D. Culler, A. Dusseau, S. Goldstein, A. Krishnamurthy, S. Lumetta, T. von
  10  * Eicken and K. Yelick. "Parallel Programming in Split-C".  Supercomputing
  11  * 1993, pages 262-273.
  12  * </cite>
  13  *
  14  * Java code converted to D by leonardo maffi, V.1.0, Oct 25 2009.
  15  *
  16  * Removed output unless an option is passed by Leandro Lucarella, 2010-08-04.
  17  * Downloaded from http://www.fantascienza.net/leonardo/js/
  18  *                 http://www.fantascienza.net/leonardo/js/dolden_em3d.zip
  19  **/
  20
  21
  22 version (Tango) {
  23     import tango.stdc.stdio: printf, sprintf;
  24     import tango.stdc.stdlib: exit;
  25     import tango.stdc.time: CLOCKS_PER_SEC, clock;
  26
  27     import Integer = tango.text.convert.Integer;
  28     alias Integer.parse toInt;
  29 } else {
  30     import std.c.stdio: printf, sprintf;
  31     import std.c.stdlib: exit;
  32     import std.c.time: CLOCKS_PER_SEC, clock;
  33
  34     version (D_Version2) {
  35         import std.conv: to;
  36         alias to!(int, char[]) toInt;
  37     } else {
  38         import std.conv: toInt;
  39     }
  40 }
  41
  42
  43 double myclock() {
  44     return clock() / cast(double)CLOCKS_PER_SEC;
  45 }
  46
  47
  48 /**
  49 Basic uniform random generator: Minimal Standard in Park and
  50 Miller (1988): "Random Number Generators: Good Ones Are Hard to
  51 Find", Comm. of the ACM, 31, 1192-1201.
  52 Parameters: m = 2^31-1, a=48271.
  53
  54 Adapted from Pascal code by Jesper Lund:
  55 http://www.gnu-pascal.de/crystal/gpc/en/mail1390.html
  56 */
  57 final class Random {
  58     const int m = int.max;
  59     const int a = 48_271;
  60     const int q = m / a;
  61     const int r = m % a;
  62     public int seed;
  63
  64     this(int the_seed) {
  65         this.seed = the_seed;
  66     }
  67
  68     public double nextDouble() {
  69         int k = seed / q;
  70         seed = a * (seed - k * q) - r * k;
  71         if (seed < 1)
  72             seed += m;
  73         return cast(double)seed / m;
  74     }
  75
  76     public int nextInt(int max) {
  77         int n = max + 1;
  78         int k = cast(int)(n * this.nextDouble());
  79         return (k == n) ? k - 1 : k;
  80     }
  81 }
  82
  83
  84 /**
  85  * This class implements nodes (both E- and H-nodes) of the EM graph. Sets
  86  * up random neighbors and propagates field values among neighbors.
  87  */
  88 final class Node
  89 {
  90   /**
  91    * The value of the node.
  92    **/
  93   double value;
  94   /**
  95    * The next node in the list.
  96    **/
  97   private Node next;
  98   /**
  99    * Array of nodes to which we send our value.
 100    **/
 101   Node[] toNodes;
 102   /**
 103    * Array of nodes from which we receive values.
 104    **/
 105   Node[] fromNodes;
 106   /**
 107    * Coefficients on the fromNodes edges
 108    **/
 109   double[] coeffs;
 110   /**
 111    * The number of fromNodes edges
 112    **/
 113   int fromCount;
 114   /**
 115    * Used to create the fromEdges - keeps track of the number of edges that have
 116    * been added
 117    **/
 118   int fromLength;
 119
 120   /**
 121    * A random number generator.
 122    **/
 123   private static Random rand;
 124
 125   /**
 126    * Initialize the random number generator
 127    **/
 128   public static void initSeed(long seed)
 129   {
 130     rand = new Random(seed);
 131   }
 132
 133   /**
 134    * Constructor for a node with given `degree'.   The value of the
 135    * node is initialized to a random value.
 136    **/
 137   this(int degree)
 138   {
 139     value = rand.nextDouble();
 140     // create empty array for holding toNodes
 141     toNodes = new Node[degree];
 142
 143     next = null;
 144     fromNodes = null;
 145     coeffs = null;
 146     fromCount = 0;
 147     fromLength = 0;
 148   }
 149
 150   /**
 151    * Create the linked list of E or H nodes.  We create a table which is used
 152    * later to create links among the nodes.
 153    * @param size the no. of nodes to create
 154    * @param degree the out degree of each node
 155    * @return a table containing all the nodes.
 156    **/
 157   static Node[] fillTable(int size, int degree)
 158   {
 159     Node[] table = new Node[size];
 160
 161     Node prevNode = new Node(degree);
 162     table[0] = prevNode;
 163     for (int i = 1; i < size; i++) {
 164       Node curNode = new Node(degree);
 165       table[i] = curNode;
 166       prevNode.next = curNode;
 167       prevNode = curNode;
 168     }
 169     return table;
 170   }
 171
 172   /**
 173    * Create unique `degree' neighbors from the nodes given in nodeTable.
 174    * We do this by selecting a random node from the give nodeTable to
 175    * be neighbor. If this neighbor has been previously selected, then
 176    * a different random neighbor is chosen.
 177    * @param nodeTable the list of nodes to choose from.
 178    **/
 179   void makeUniqueNeighbors(Node[] nodeTable)
 180   {
 181     for (int filled = 0; filled < toNodes.length; filled++) {
 182       int k;
 183       Node otherNode;
 184
 185       do {
 186     // generate a random number in the correct range
 187     int index = rand.nextInt(nodeTable.length - 1);
 188
 189     // find a node with the random index in the given table
 190     otherNode = nodeTable[index];
 191
 192     for (k = 0; k < filled; k++) {
 193       if (otherNode == toNodes[k]) break; // fixed a bug of the original Java code
 194     }
 195       } while (k < filled);
 196
 197       // other node is definitely unique among "filled" toNodes
 198       toNodes[filled] = otherNode;
 199
 200       // update fromCount for the other node
 201       otherNode.fromCount++;
 202     }
 203   }
 204
 205   /**
 206    * Allocate the right number of FromNodes for this node. This
 207    * step can only happen once we know the right number of from nodes
 208    * to allocate. Can be done after unique neighbors are created and known.
 209    *
 210    * It also initializes random coefficients on the edges.
 211    **/
 212   void makeFromNodes()
 213   {
 214     fromNodes = new Node[fromCount]; // nodes fill be filled in later
 215     coeffs = new double[fromCount];
 216   }
 217
 218   /**
 219    * Fill in the fromNode field in "other" nodes which are pointed to
 220    * by this node.
 221    **/
 222   void updateFromNodes()
 223   {
 224     for (int i = 0; i < toNodes.length; i++) {
 225       Node otherNode = toNodes[i];
 226       int count = otherNode.fromLength++;
 227       otherNode.fromNodes[count] = this;
 228       otherNode.coeffs[count] = rand.nextDouble();
 229     }
 230   }
 231
 232   /**
 233    * Get the new value of the current node based on its neighboring
 234    * from_nodes and coefficients.
 235    **/
 236   void computeNewValue()
 237   {
 238     for (int i = 0; i < fromCount; i++) {
 239       value -= coeffs[i] * fromNodes[i].value;
 240     }
 241   }
 242
 243   int opApply(int delegate(ref Node) dg) {
 244     int result;
 245     for (Node current = this; current !is null; current = current.next) {
 246       result = dg(current);
 247       if (result)
 248         break;
 249     }
 250     return result;
 251   }
 252
 253   public char* toCString()
 254   {
 255     static char[256] repr;
 256     sprintf(repr.ptr, "value %.17f, from_count %d", value, fromCount);
 257     return repr.ptr;
 258   }
 259 }
 260
 261
 262 /**
 263  * A class that represents the irregular bipartite graph used in
 264  * EM3D.  The graph contains two linked structures that represent the
 265  * E nodes and the N nodes in the application.
 266  **/
 267 final class BiGraph
 268 {
 269   /**
 270    * Nodes that represent the electrical field.
 271    **/
 272   Node eNodes;
 273   /**
 274    * Nodes that representhe the magnetic field.
 275    **/
 276   Node hNodes;
 277
 278   /**
 279    * Construct the bipartite graph.
 280    * @param e the nodes representing the electric fields
 281    * @param h the nodes representing the magnetic fields
 282    **/
 283   this(Node e, Node h)
 284   {
 285     eNodes = e;
 286     hNodes = h;
 287   }
 288
 289   /**
 290    * Create the bi graph that contains the linked list of
 291    * e and h nodes.
 292    * @param numNodes the number of nodes to create
 293    * @param numDegree the out-degree of each node
 294    * @param verbose should we print out runtime messages
 295    * @return the bi graph that we've created.
 296    **/
 297   static BiGraph create(int numNodes, int numDegree, bool verbose)
 298   {
 299     Node.initSeed(783);
 300
 301     // making nodes (we create a table)
 302     if (verbose) printf("making nodes (tables in orig. version)\n");
 303     Node[] hTable = Node.fillTable(numNodes, numDegree);
 304     Node[] eTable = Node.fillTable(numNodes, numDegree);
 305
 306     // making neighbors
 307     if (verbose) printf("updating from and coeffs\n");
 308     foreach (n; hTable[0])
 309       n.makeUniqueNeighbors(eTable);
 310     foreach (n; eTable[0])
 311       n.makeUniqueNeighbors(hTable);
 312
 313     // Create the fromNodes and coeff field
 314     if (verbose) printf("filling from fields\n");
 315     foreach (n; hTable[0])
 316       n.makeFromNodes();
 317     foreach (n; eTable[0])
 318       n.makeFromNodes();
 319
 320     // Update the fromNodes
 321     foreach (n; hTable[0])
 322       n.updateFromNodes();
 323     foreach (n; eTable[0])
 324       n.updateFromNodes();
 325
 326     BiGraph g = new BiGraph(eTable[0], hTable[0]);
 327     return g;
 328   }
 329
 330   /**
 331   * Update the field values of e-nodes based on the values of
 332   * neighboring h-nodes and vice-versa.
 333   **/
 334   void compute() {
 335     foreach (n; eNodes)
 336       n.computeNewValue();
 337     foreach (n; hNodes)
 338       n.computeNewValue();
 339   }
 340
 341   /**
 342   * Print out the values of the e and h nodes.
 343   **/
 344   public void print() {
 345     foreach (n; eNodes)
 346       printf("E: %s\n", n.toCString());
 347     foreach (n; hNodes)
 348       printf("H: %s\n", n.toCString());
 349     printf("\n");
 350   }
 351 }
 352
 353 public class Em3d1
 354 {
 355   /**
 356    * The number of nodes (E and H)
 357    **/
 358   private static int numNodes = 0;
 359   /**
 360    * The out-degree of each node.
 361    **/
 362   private static int numDegree = 0;
 363   /**
 364    * The number of compute iterations
 365    **/
 366   private static int numIter = 1;
 367   /**
 368    * Should we print the results and other runtime messages
 369    **/
 370   private static bool printResult = false;
 371   /**
 372    * Print information messages?
 373    **/
 374   private static bool printMsgs = false;
 375
 376   /**
 377    * The main roitine that creates the irregular, linked data structure
 378    * that represents the electric and magnetic fields and propagates the
 379    * waves through the graph.
 380    * @param args the command line arguments
 381    **/
 382   public static final void main(char[] args[])
 383   {
 384     parseCmdLine(args);
 385
 386     if (printMsgs)
 387       printf("Initializing em3d random graph...\n");
 388     auto start0 = myclock();
 389     BiGraph graph = BiGraph.create(numNodes, numDegree, printResult);
 390     auto end0 = myclock();
 391
 392     // compute a single iteration of electro-magnetic propagation
 393     if (printMsgs)
 394       printf("Propagating field values for %d iteration(s)...\n", numIter);
 395     auto start1 = myclock();
 396     for (int i = 0; i < numIter; i++) {
 397       graph.compute();
 398     }
 399     auto end1 = myclock();
 400
 401     // print current field values
 402     if (printResult)
 403       graph.print();
 404
 405     if (printMsgs) {
 406       printf("EM3D build time %.2f\n", end0 - start0);
 407       printf("EM3D compute time %.2f\n", end1 - start1);
 408       printf("EM3D total time %.2f\n", end1 - start0);
 409       printf("Done!\n");
 410     }
 411   }
 412
 413
 414   /**
 415    * Parse the command line options.
 416    * @param args the command line options.
 417    **/
 418   private static final void parseCmdLine(char[] args[])
 419   {
 420     int i = 1;
 421     char[] arg;
 422
 423     while (i < args.length && args[i][0] == '-') {
 424       arg = args[i++];
 425
 426       // check for options that require arguments
 427       if (arg == "-n") {
 428         if (i < args.length) {
 429           numNodes = toInt(args[i++]);
 430         } else throw new Exception("-n requires the number of nodes");
 431       } else if (arg == "-d") {
 432     if (i < args.length) {
 433       numDegree = toInt(args[i++]);
 434     } else throw new Exception("-d requires the out degree");
 435       } else if (arg == "-i") {
 436     if (i < args.length) {
 437       numIter = toInt(args[i++]);
 438     } else throw new Exception("-i requires the number of iterations");
 439       } else if (arg == "-p") {
 440         printResult = true;
 441       } else if (arg == "-m") {
 442         printMsgs = true;
 443       } else if (arg == "-h") {
 444     usage();
 445       }
 446     }
 447     if (numNodes == 0 || numDegree == 0) usage();
 448   }
 449
 450   /**
 451   * The usage routine which describes the program options.
 452   **/
 453     private static final void usage() {
 454     printf("usage: em3d -n <nodes> -d <degree> [-p] [-m] [-h]\n");
 455     printf("    -n the number of nodes\n");
 456     printf("    -d the out-degree of each node\n");
 457     printf("    -i the number of iterations\n");
 458     printf("    -p (print detailed results)\n");
 459     printf("    -m (print informative messages)\n");
 460     printf("    -h (this message)\n");
 461     exit(0);
 462   }
 463 }
 464
 465
 466 void main(char[][] args) {
 467     Em3d1.main(args);
 468 }