Robust/src/Benchmarks/SingleTM/SSCA2/Alg_Radix_Smp.java

   1 /* =============================================================================
   2  *
   3  * alg_radix_smp.java
   4  *
   5  * =============================================================================
   6  *
   7  * For the license of ssca2, please see ssca2/COPYRIGHT
   8  *
   9  * ------------------------------------------------------------------------
  10  *
  11  * Unless otherwise noted, the following license applies to STAMP files:
  12  *
  13  * Copyright (c) 2007, Stanford University
  14  * All rights reserved.
  15  *
  16  * Redistribution and use in source and binary forms, with or without
  17  * modification, are permitted provided that the following conditions are
  18  * met:
  19  *
  20  *     * Redistributions of source code must retain the above copyright
  21  *       notice, this list of conditions and the following disclaimer.
  22  *
  23  *     * Redistributions in binary form must reproduce the above copyright
  24  *       notice, this list of conditions and the following disclaimer in
  25  *       the documentation and/or other materials provided with the
  26  *       distribution.
  27  *
  28  *     * Neither the name of Stanford University nor the names of its
  29  *       contributors may be used to endorse or promote products derived
  30  *       from this software without specific prior written permission.
  31  *
  32  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  33  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  34  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  35  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  36  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  37  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  38  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  39  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  40  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  41  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  42  * THE POSSIBILITY OF SUCH DAMAGE.
  43  *
  44  * =============================================================================
  45  */
  46
  47 public class Alg_Radix_Smp {
  48   public int[] global_myHisto;
  49   public int[] global_psHisto;
  50   public int[] global_lTemp;
  51   public int[] global_lTemp2;
  52
  53   public Alg_Radix_Smp() {
  54     global_myHisto = null;
  55     global_psHisto = null;
  56     global_lTemp   = null;
  57     global_lTemp2  = null;
  58   }
  59
  60   public int BITS(int x, int k, int j) {
  61     int retval = ((x>>k) & ~(~0<<j));
  62     return retval;
  63   }
  64
  65   /* =============================================================================
  66    * all_countsort_node
  67    *
  68    * R (range)      must be a multiple of NODES
  69    * q (elems/proc) must be a multiple of NODES
  70    * =============================================================================
  71    */
  72   /*
  73   public void
  74     all_countsort_node (
  75         int q,
  76         int[] lKey,
  77         int[] lSorted,
  78         int R,
  79         int bitOff,
  80         int m)
  81     {
  82       int[] myHisto = null;
  83       int[] psHisto = null;
  84
  85       if (myId == 0) {
  86         myHisto = new int[numThread*R];
  87         global_myHisto = myHisto;
  88         psHisto = new int[numThread*R];
  89         global_psHisto = psHisto;
  90       }
  91
  92       Barrier.enterBarrier();
  93
  94       myHisto = global_myHisto;
  95       psHisto = global_psHisto;
  96
  97       int index = myId * R;
  98
  99       for (int k =  index; k < index+R; k++) {
 100         myHisto[k] = 0;
 101       }
 102
 103       LocalStartStop lss = new LocalStartStop();
 104       CreatePartition.createPartition(0, q, myId, numThread, lss);
 105
 106       for (int k = lss.i_start; k < lss.i_stop; k++) {
 107         myHisto[(myId * R) + BITS(lKey[k],bitOff,m)]++;
 108       }
 109
 110       Barrier.enterBarrier();
 111
 112       CreatePartition.createPartition(0, R, myId, numThread, lss);
 113
 114       int last;
 115       for (int k = lss.i_start; k < lss.i_stop; k++) {
 116         last = psHisto[k] = myHisto[k];
 117         for (int j = 1; j < numThread; j++) {
 118           int temp = psHisto[(j*R) + k] = last + myHisto[(j*R) + k];
 119           last = temp;
 120         }
 121       }
 122
 123       Barrier.enterBarrier();
 124
 125       int offset = 0;
 126
 127       for (int k = 0; k < R; k++) {
 128         myHisto[(myId * R) + k] = (psHisto[(myId * R) + k] - myHisto[(myId * R) + k]) + offset;
 129         offset += psHisto[((numThread - 1) * R) + k];
 130       }
 131
 132       Barrier.enterBarrier();
 133
 134       CreatePartition.createPartition(0, q, myId, numThread, lss);
 135
 136       for (int k = lss.i_start; k < lss.i_stop; k++) {
 137         int j = BITS(lKey[k],bitOff,m);
 138         lSorted[myHisto[(myId * R) + j]] = lKey[k];
 139         myHisto[(myId * R) + j]++;
 140       }
 141
 142       Barrier.enterBarrier();
 143
 144       if (myId == 0) {
 145         psHisto = null;
 146         myHisto = null;
 147       }
 148     }
 149 */
 150
 151
 152   /* =============================================================================
 153    * all_countsort_node_aux_seq
 154    *
 155    * R (range)      must be a multiple of NODES
 156    * q (elems/proc) must be a multiple of NODES
 157    * =============================================================================
 158    */
 159   /*
 160   public void
 161     all_countsort_node_aux_seq (int q,
 162         int[] lKey,
 163         int[] lSorted,
 164         int[] auxKey,
 165         int[] auxSorted,
 166         int R,
 167         int bitOff,
 168         int m)
 169     {
 170       int[] myHisto = new int[ R];
 171       int[] psHisto = new int[ R];
 172
 173       for (int k = 0; k < R; k++) {
 174         myHisto[k] = 0;
 175       }
 176
 177       for (int k = 0; k < q; k++) {
 178         myHisto[BITS(lKey[k],bitOff,m)]++;
 179       }
 180
 181       int last;
 182       for (int k = 0; k < R; k++) {
 183         last = psHisto[k] = myHisto[k];
 184       }
 185
 186       int offset = 0;
 187
 188       for (int k = 0; k < R; k++) {
 189         myHisto[k] = (psHisto[k] - myHisto[k]) + offset;
 190         offset += psHisto[k];
 191       }
 192
 193       for (int k = 0; k <  q; k++) {
 194         int j = BITS(lKey[k], bitOff, m);
 195         lSorted[myHisto[j]] = lKey[k];
 196         auxSorted[myHisto[j]] = lKey[k];
 197         myHisto[j]++;
 198
 199         //
 200         //lSorted[mhp[j]] = lKey[k];
 201         //auxSorted[mhp[j]] = auxKey[k];
 202         //mhp[j]++;
 203
 204       }
 205
 206       psHisto = null;
 207       myHisto = null;
 208     }
 209 */
 210
 211
 212   /* =============================================================================
 213    * all_countsort_node_aux
 214    *
 215    * R (range)      must be a multiple of NODES
 216    * q (elems/proc) must be a multiple of NODES
 217    * =============================================================================
 218    */
 219   public void
 220     all_countsort_node_aux (int myId,
 221         int numThread,
 222         int q,
 223         int[] lKey,
 224         int[] lSorted,
 225         int[] auxKey,
 226         int[] auxSorted,
 227         int R,
 228         int bitOff,
 229         int m,
 230         Alg_Radix_Smp rdxsort)
 231     {
 232       int[] myHisto = null;
 233       int[] psHisto = null;
 234
 235       if (myId == 0) {
 236         myHisto = new int[numThread * R];
 237         rdxsort.global_myHisto = myHisto;
 238         psHisto = new int[numThread * R];
 239         rdxsort.global_psHisto = psHisto;
 240       }
 241
 242       Barrier.enterBarrier();
 243
 244       myHisto = rdxsort.global_myHisto;
 245       psHisto = rdxsort.global_psHisto;
 246
 247       for (int k = 0; k <  R; k++) {
 248         myHisto[((myId*R) + k)] = 0;
 249       }
 250
 251       LocalStartStop lss = new LocalStartStop();
 252       CreatePartition.createPartition(0, q, myId, numThread, lss);
 253
 254       for (int k = lss.i_start; k < lss.i_stop; k++) {
 255         myHisto[(myId*R) + BITS(lKey[k],bitOff,m)]++;
 256       }
 257
 258       Barrier.enterBarrier();
 259
 260       CreatePartition.createPartition(0, R, myId, numThread, lss);
 261
 262       int last;
 263       for (int k = lss.i_start; k < lss.i_stop; k++) {
 264         last = psHisto[k] = myHisto[k];
 265         for (int j = 1; j < numThread; j++) {
 266           int temp = psHisto[(j*R + k)] = last + myHisto[ (j*R + k)];
 267           last = temp;
 268         }
 269       }
 270
 271       Barrier.enterBarrier();
 272
 273       int offset = 0;
 274
 275       for (int k = 0; k < R; k++) {
 276         myHisto[(myId*R)+k] = (psHisto[(myId*R) + k] - myHisto[(myId*R) +k]) + offset;
 277         offset += psHisto[((numThread -1) * R) + k];
 278       }
 279
 280       Barrier.enterBarrier();
 281
 282       CreatePartition.createPartition(0, q, myId, numThread, lss);
 283
 284       for (int k = lss.i_start; k < lss.i_stop; k++) {
 285         int j = BITS(lKey[k], bitOff, m);
 286         lSorted[myHisto[(myId*R) +j]] = lKey[k];
 287         auxSorted[myHisto[(myId*R) +j]] = auxKey[k];
 288         myHisto[(myId*R) +j]++;
 289       }
 290
 291       Barrier.enterBarrier();
 292
 293       if (myId == 0) {
 294         psHisto = null;
 295         myHisto = null;
 296       }
 297     }
 298
 299
 300   /* =============================================================================
 301    * all_radixsort_node_s3
 302    *
 303    * q (elems/proc) must be a multiple of NODES
 304    * =============================================================================
 305    */
 306   /*
 307   public void
 308     all_radixsort_node_s3 (int q,
 309         int[] lKeys,
 310         int[] lSorted)
 311     {
 312
 313       int[] lTemp = null;
 314
 315       if (myId == 0) {
 316         lTemp = new int[ q];
 317         global_lTemp = lTemp;
 318       }
 319
 320       Barrier.enterBarrier();
 321
 322       lTemp = global_lTemp;
 323
 324       all_countsort_node(q, lKeys,   lSorted, (1<<11),  0, 11);
 325       all_countsort_node(q, lSorted, lTemp,   (1<<11), 11, 11);
 326       all_countsort_node(q, lTemp,   lSorted, (1<<10), 22, 10);
 327
 328       Barrier.enterBarrier();
 329
 330       if (myId == 0) {
 331         lTemp = null;
 332       }
 333     }
 334     */
 335
 336
 337   /* =============================================================================
 338    * all_radixsort_node_s2
 339    *
 340    * q (elems/proc) must be a multiple of NODES
 341    * =============================================================================
 342    */
 343   /*
 344   public void
 345     all_radixsort_node_s2 (int q,
 346         int[] lKeys,
 347         int[] lSorted)
 348     {
 349
 350       int[] lTemp = null;
 351
 352       if (myId == 0) {
 353         lTemp = new int[ q];
 354         global_lTemp = lTemp;
 355       }
 356
 357       Barrier.enterBarrier();
 358
 359       lTemp = global_lTemp;
 360
 361       all_countsort_node(q, lKeys, lTemp,   (1<<16),  0, 16);
 362       all_countsort_node(q, lTemp, lSorted, (1<<16), 16, 16);
 363
 364       Barrier.enterBarrier();
 365
 366       if (myId == 0) {
 367         lTemp = null;
 368       }
 369     }
 370     */
 371
 372
 373   /* =============================================================================
 374    * all_radixsort_node_aux_s3_seq
 375    *
 376    * q (elems/proc) must be a multiple of NODES
 377    * =============================================================================
 378    */
 379   /*
 380   public void
 381     all_radixsort_node_aux_s3_seq (int q,
 382         int[] lKeys,
 383         int[] lSorted,
 384         int[] auxKey,
 385         int[] auxSorted)
 386     {
 387       int[] lTemp  = null;
 388       int[] lTemp2 = null;
 389
 390       lTemp = new int[ q];
 391       lTemp2 = new int[ q];
 392
 393       all_countsort_node_aux_seq(q, lKeys, lSorted, auxKey, auxSorted, (1<<11),  0, 11);
 394       all_countsort_node_aux_seq(q, lSorted, lTemp, auxSorted, lTemp2, (1<<11), 11, 11);
 395       all_countsort_node_aux_seq(q, lTemp, lSorted, lTemp2, auxSorted, (1<<10), 22, 10);
 396
 397       lTemp = null;
 398       lTemp2 = null;
 399     }
 400     */
 401
 402
 403   /* =============================================================================
 404    * all_radixsort_node_aux_s3
 405    *
 406    * q (elems/proc) must be a multiple of NODES
 407    * =============================================================================
 408    */
 409   public static void
 410     all_radixsort_node_aux_s3 (int myId,
 411         int numThread,
 412         int q,
 413         int[] lKeys,
 414         int[] lSorted,
 415         int[] auxKey,
 416         int[] auxSorted,
 417         Alg_Radix_Smp rdxsort)
 418     {
 419       int[] lTemp  = null;
 420       int[] lTemp2 = null;
 421
 422       if (myId == 0) {
 423         lTemp = new int[ q];
 424         rdxsort.global_lTemp = lTemp;
 425         lTemp2 = new int[ q];
 426         rdxsort.global_lTemp2 = lTemp2;
 427       }
 428
 429       Barrier.enterBarrier();
 430
 431       lTemp  = rdxsort.global_lTemp;
 432       lTemp2 = rdxsort.global_lTemp2;
 433
 434       rdxsort.all_countsort_node_aux(myId, numThread, q, lKeys, lSorted, auxKey, auxSorted, (1<<11),  0, 11, rdxsort);
 435       rdxsort.all_countsort_node_aux(myId, numThread, q, lSorted, lTemp, auxSorted, lTemp2, (1<<11), 11, 11, rdxsort);
 436       rdxsort.all_countsort_node_aux(myId, numThread, q, lTemp, lSorted, lTemp2, auxSorted, (1<<10), 22, 10, rdxsort);
 437
 438       Barrier.enterBarrier();
 439
 440       if(myId == 0) {
 441         lTemp = null;
 442         lTemp2 = null;
 443       }
 444     }
 445 }
 446
 447 /* =============================================================================
 448  *
 449  * End of alg_radix_smp.java
 450  *
 451  * =============================================================================
 452  */
 453