micro/bisort.d

   1 /*
   2 A Java implementation of the bisort Olden benchmark.
   3 The Olden benchmark implements a Bitonic Sort as described in:
   4
   5 G. Bilardi and A. Nicolau, "Adaptive Bitonic Sorting: An optimal parallel
   6 algorithm for shared-memory machines." SIAM J. Comput. 18(2):216-228, 1998.
   7
   8 The benchmarks sorts N numbers where N is a power of 2. If the user provides
   9 an input value that is not a power of 2, then we use the nearest power of
  10 2 value that is less than the input value.
  11
  12 Converted to D and obtimized by leonardo maffi, V.1.0, Oct 31 2009.
  13
  14 Removed output unless an option is passed by Leandro Lucarella, 2010-08-04.
  15 Downloaded from http://www.fantascienza.net/leonardo/js/
  16                 http://www.fantascienza.net/leonardo/js/dolden_bisort.zip
  17 */
  18
  19 version (Tango) {
  20     import tango.stdc.stdio: printf, fprintf, stderr;
  21     import tango.stdc.stdlib: exit;
  22     import Integer = tango.text.convert.Integer;
  23     alias Integer.parse toInt;
  24     import tango.stdc.time: CLOCKS_PER_SEC, clock;
  25 } else {
  26     import std.c.stdio: printf, fprintf, stderr;
  27     import std.c.stdlib: exit;
  28     import std.conv: toInt;
  29     import std.c.time: CLOCKS_PER_SEC, clock;
  30 }
  31
  32
  33 double myclock() {
  34     return clock() / cast(float)CLOCKS_PER_SEC;
  35 }
  36
  37
  38 /**
  39  * A class that represents a value to be sorted by the <tt>BiSort</tt>
  40  * algorithm.    We represents a values as a node in a binary tree.
  41  **/
  42 final class Value {
  43     private int value;
  44     private Value left, right;
  45
  46     const bool FORWARD = false;
  47     const bool BACKWARD = true;
  48
  49     // These are used by the Olden benchmark random no. generator
  50     private const int CONST_m1 = 10000;
  51     private const int CONST_b = 31415821;
  52     const int RANGE = 100;
  53
  54     /**
  55      * Constructor for a node representing a value in the bitonic sort tree.
  56      * @param v the integer value which is the sort key
  57      **/
  58     this(int v) {
  59         value = v;
  60         left = right = null;
  61     }
  62
  63
  64     /**
  65      * Create a random tree of value to be sorted using the bitonic sorting algorithm.
  66      *
  67      * @param size the number of values to create.
  68      * @param seed a random number generator seed value
  69      * @return the root of the (sub) tree.
  70      **/
  71     static Value createTree(int size, int seed) {
  72         if (size > 1) {
  73             seed = random(seed);
  74             int next_val = seed % RANGE;
  75
  76             Value retval = new Value(next_val);
  77             retval.left = createTree(size/2, seed);
  78             retval.right = createTree(size/2, skiprand(seed, size+1));
  79             return retval;
  80         } else {
  81             return null;
  82         }
  83     }
  84
  85
  86     /**
  87      * Perform a bitonic sort based upon the Bilardi and Nicolau algorithm.
  88      *
  89      * @param spr_val the "spare" value in the algorithm.
  90      * @param direction the direction of the sort (forward or backward)
  91      * @return the new "spare" value.
  92      **/
  93     int bisort(int spr_val, bool direction) {
  94         if (left is null) {
  95             if ((value > spr_val) ^ direction) {
  96                 int tmpval = spr_val;
  97                 spr_val = value;
  98                 value = tmpval;
  99             }
 100         } else {
 101             int val = value;
 102             value = left.bisort(val, direction);
 103             bool ndir = !direction;
 104             spr_val = right.bisort(spr_val, ndir);
 105             spr_val = bimerge(spr_val, direction);
 106         }
 107         return spr_val;
 108     }
 109
 110
 111     /**
 112      * Perform the merge part of the bitonic sort. The merge part does
 113      * the actualy sorting.
 114      * @param spr_val the "spare" value in the algorithm.
 115      * @param direction the direction of the sort (forward or backward)
 116      * @return the new "spare" value
 117      **/
 118     int bimerge(int spr_val, bool direction) {
 119         int rv = value;
 120         Value pl = left;
 121         Value pr = right;
 122
 123         bool rightexchange = (rv > spr_val) ^ direction;
 124         if (rightexchange) {
 125             value = spr_val;
 126             spr_val = rv;
 127         }
 128
 129         while (pl !is null) {
 130             int lv = pl.value;
 131             Value pll = pl.left;
 132             Value plr = pl.right;
 133             rv = pr.value;
 134             Value prl = pr.left;
 135             Value prr = pr.right;
 136
 137             bool elementexchange = (lv > rv) ^ direction;
 138             if (rightexchange) {
 139                 if (elementexchange) {
 140                     pl.swapValRight(pr);
 141                     pl = pll;
 142                     pr = prl;
 143                 } else {
 144                     pl = plr;
 145                     pr = prr;
 146                 }
 147             } else {
 148                 if (elementexchange) {
 149                     pl.swapValLeft(pr);
 150                     pl = plr;
 151                     pr = prr;
 152                 } else {
 153                     pl = pll;
 154                     pr = prl;
 155                 }
 156             }
 157         }
 158
 159         if (left !is null) {
 160             value = left.bimerge(value, direction);
 161             spr_val = right.bimerge(spr_val, direction);
 162         }
 163         return spr_val;
 164     }
 165
 166
 167     /**
 168      * Swap the values and the right subtrees.
 169      * @param n the other subtree involved in the swap.
 170      **/
 171     void swapValRight(Value n) {
 172         int tmpv = n.value;
 173         Value tmpr = n.right;
 174
 175         n.value = value;
 176         n.right = right;
 177
 178         value = tmpv;
 179         right = tmpr;
 180     }
 181
 182
 183     /**
 184      * Swap the values and the left subtrees.
 185      * @param n the other subtree involved in the swap.
 186      **/
 187     void swapValLeft(Value n) {
 188         int tmpv = n.value;
 189         Value tmpl = n.left;
 190
 191         n.value = value;
 192         n.left = left;
 193
 194         value = tmpv;
 195         left = tmpl;
 196     }
 197
 198
 199     /**
 200      * Print out the nodes in the binary tree in infix order.
 201      **/
 202     void inOrder() {
 203         if (left !is null)
 204             left.inOrder();
 205         printf("%d\n", value);
 206         if (right !is null)
 207             right.inOrder();
 208     }
 209
 210
 211     /**
 212      * A random generator.    The original Olden benchmark uses its
 213      * own random generator.    We use the same one in the Java version.
 214      * @return the next random number in the sequence.
 215      **/
 216     private static int mult(int p, int q) {
 217         int p1 = p / CONST_m1;
 218         int p0 = p % CONST_m1;
 219         int q1 = q / CONST_m1;
 220         int q0 = q % CONST_m1;
 221         return ((p0 * q1 + p1 * q0) % CONST_m1) * CONST_m1 + p0 * q0;
 222     }
 223
 224
 225     /**
 226      * A routine to skip the next <i>n</i> random numbers.
 227      * @param seed the current random no. seed
 228      * @param n the number of numbers to skip
 229      **/
 230     private static int skiprand(int seed, int n) {
 231         for (; n != 0; n--)
 232             seed = random(seed);
 233         return seed;
 234     }
 235
 236
 237     /**
 238      * Return a random number based upon the seed value.
 239      * @param seed the random number seed value
 240      * @return a random number based upon the seed value.
 241      **/
 242     static int random(int seed) {
 243         int tmp = mult(seed, CONST_b) + 1;
 244         return tmp;
 245     }
 246 }
 247
 248
 249 final public class BiSort {
 250     private static int size = 0; // The number of values to sort.
 251     private static bool printMsgs = false; // Print information messages
 252     private static bool printResults = false; // Print the tree after each step
 253
 254
 255     /**
 256      * The main routine which creates a tree and sorts it a couple of times.
 257      * @param args the command line arguments
 258      **/
 259     public static final void main(char[][] args) {
 260         parseCmdLine(args);
 261
 262         if (printMsgs)
 263             printf("Bisort with %d values\n", nextPow2(size+1) - 1);
 264
 265         auto start2 = myclock();
 266         Value tree = Value.createTree(size, 12345768);
 267         auto end2 = myclock();
 268         int sval = Value.random(245867) % Value.RANGE;
 269
 270         if (printResults) {
 271             tree.inOrder();
 272             printf("%d\n", sval);
 273         }
 274
 275         if (printMsgs)
 276             printf("Beginning bitonic sort\n");
 277
 278         auto start0 = myclock();
 279         sval = tree.bisort(sval, Value.FORWARD);
 280         auto end0 = myclock();
 281
 282         if (printResults) {
 283             tree.inOrder();
 284             printf("%d\n", sval);
 285         }
 286
 287         auto start1 = myclock();
 288         sval = tree.bisort(sval, Value.BACKWARD);
 289         auto end1 = myclock();
 290
 291         if (printResults) {
 292             tree.inOrder();
 293             printf("%d\n", sval);
 294         }
 295
 296         if (printMsgs) {
 297             printf("Creation time: %f\n", end2 - start2);
 298             printf("Time to sort forward = %f\n", end0 - start0);
 299             printf("Time to sort backward = %f\n", end1 - start1);
 300             printf("Total: %f\n", end1 - start0);
 301             printf("Done!\n");
 302         }
 303     }
 304
 305
 306     /**
 307      * Parse the command line options.
 308      * @param args the command line options.
 309      **/
 310     private static final void parseCmdLine(char[][] args) {
 311         int i = 1;
 312         char[] arg;
 313
 314         while (i < args.length && args[i][0] == '-') {
 315             arg = args[i++];
 316
 317             // check for options that require arguments
 318             if (arg == "-s") {
 319                 if (i < args.length) {
 320                     size = toInt(args[i++]);
 321                 } else {
 322                     throw new Exception("-l requires the number of levels");
 323                 }
 324             } else if (arg == "-m") {
 325                 printMsgs = true;
 326             } else if (arg == "-p") {
 327                 printResults = true;
 328             } else if (arg == "-h") {
 329                 usage();
 330             }
 331         }
 332         if (size == 0)
 333             usage();
 334     }
 335
 336
 337     /**
 338      * The usage routine which describes the program options.
 339      **/
 340     private static final void usage() {
 341         fprintf(stderr, "usage: bisort_d -s <size> [-p] [-i] [-h]\n");
 342         fprintf(stderr, "  -s the number of values to sort\n");
 343         fprintf(stderr, "  -m (print informative messages)\n");
 344         fprintf(stderr, "  -p (print the binary tree after each step)\n");
 345         fprintf(stderr, "  -h (print this message)\n");
 346         exit(0);
 347     }
 348
 349
 350     private static /*unsigned*/ int nextPow2(/*unsigned*/ int x) {
 351         if (x < 0)
 352             throw new Exception("x must be >= 0");
 353         x -= 1;
 354         x |= x >>  1;
 355         x |= x >>  2;
 356         x |= x >>  4;
 357         x |= x >>  8;
 358         x |= x >> 16;
 359         return x + 1;
 360     }
 361 }
 362
 363
 364 void main(char[][] args) {
 365     BiSort.main(args);
 366 }