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   int[] global_myHisto;
  49   int[] global_psHisto;
  50   int[] global_lTemp;
  51   int[] global_lTemp2;
  52   int myId;
  53   int numThread;
  54
  55   public class Alg_Radix_Smp(int myId, int numThread) {
  56     global_myHisto = null;
  57     global_psHisto = null;
  58     global_lTemp   = null;
  59     global_lTemp2  = null;
  60     this.myId = myId;
  61     this.numThread = numThread;
  62   }
  63
  64   public int BITS(x, k, j) {
  65     int retval = ((x>>k) & ~(~0<<j));
  66     return retval;
  67   }
  68
  69   /* =============================================================================
  70    * all_countsort_node
  71    *
  72    * R (range)      must be a multiple of NODES
  73    * q (elems/proc) must be a multiple of NODES
  74    * =============================================================================
  75    */
  76   void
  77     all_countsort_node (int q,
  78         int[] lKey,
  79         int[] lSorted,
  80         int R,
  81         int bitOff,
  82         int m,
  83         )
  84     {
  85       int[] myHisto = null;
  86       int[] psHisto = null;
  87
  88       if (myId == 0) {
  89         myHisto = new int[numThread*R];
  90         global_myHisto = myHisto;
  91         psHisto = new int[numThread*R];
  92         global_psHisto = psHisto;
  93       }
  94
  95       Barrier.enterBarrier();
  96
  97       myHisto = global_myHisto;
  98       psHisto = global_psHisto;
  99
 100       int index = myId * R;
 101
 102       for (int k =  index; k < index+R; k++) {
 103         myHisto[k] = 0;
 104       }
 105
 106       LocalStartStop lss = new LocalStartStop();
 107       CreatePartition.createPartition(0, q, myId, numThread, lss);
 108
 109       for (int k = lss.i_start; k < i_stop; k++) {
 110         myHisto[(myId * R) + BITS(lKey[k],bitOff,m)]++;
 111       }
 112
 113       Barrier.enterBarrier();
 114
 115       CreatePartition.createPartition(0, R, myId, numThread, lss);
 116
 117       int last;
 118       for (int k = lss.i_start; k < lss.i_stop; k++) {
 119         last = psHisto[k] = myHisto[k];
 120         for (int j = 1; j < numThread; j++) {
 121           int temp = psHisto[(j*R) + k] = last + myHisto[(j*R) + k];
 122           last = temp;
 123         }
 124       }
 125
 126       Barrier.enterBarrier();
 127
 128       int offset = 0;
 129
 130       for (k = 0; k < R; k++) {
 131         myHisto[(myId * R) + k] = (psHisto[(myId * R) + k] - myHisto[(myId * R) + k]) + offset;
 132         offset += psHisto[((numThread - 1) * R) + k];
 133       }
 134
 135       Barrier.enterBarrier();
 136
 137       CreatePartition.createPartition(0, q, myId, numThread, lss);
 138
 139       for (int k = lss.i_start; k < lss.i_stop; k++) {
 140         int j = BITS(lKey[k],bitOff,m);
 141         lSorted[myHisto[(myId * R) + j]] = lKey[k];
 142         myHisto[(myId * R) + j]++;
 143       }
 144
 145       Barrier.enterBarrier();
 146
 147       if (myId == 0) {
 148         psHisto = null;
 149         myHisto = null;
 150       }
 151     }
 152
 153
 154   /* =============================================================================
 155    * all_countsort_node_aux_seq
 156    *
 157    * R (range)      must be a multiple of NODES
 158    * q (elems/proc) must be a multiple of NODES
 159    * =============================================================================
 160    */
 161   void
 162     all_countsort_node_aux_seq (int q,
 163         int[] lKey,
 164         int[] lSorted,
 165         int[] auxKey,
 166         int[] auxSorted,
 167         int R,
 168         int bitOff,
 169         int m)
 170     {
 171       int[] myHisto = new int[ R];
 172       int[] psHisto = new int[ R];
 173
 174       for (int k = 0; k < R; k++) {
 175         myHisto[k] = 0;
 176       }
 177
 178       for (int k = 0; k < q; k++) {
 179         myHisto[BITS(lKey[k],bitOff,m)]++;
 180       }
 181
 182       int last;
 183       for (int k = 0; k < R; k++) {
 184         last = psHisto[k] = myHisto[k];
 185       }
 186
 187       int offset = 0;
 188
 189       for (int k = 0; k < R; k++) {
 190         myHisto[k] = (psHisto[k] - myHisto[k]) + offset;
 191         offset += psHisto[k];
 192       }
 193
 194       for (int k = 0; k <  q; k++) {
 195         int j = BITS(lKey[k], bitOff, m);
 196         lSorted[myHisto[j]] = lKey[k];
 197         auxSorted[myHisto[j]] = lKey[k];
 198         myHisto[j]++;
 199
 200         /*
 201         lSorted[mhp[j]] = lKey[k];
 202         auxSorted[mhp[j]] = auxKey[k];
 203         mhp[j]++;
 204         */
 205       }
 206
 207       psHisto = null;
 208       myHisto = null;
 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   void
 220     all_countsort_node_aux (int q,
 221         int[] lKey,
 222         int[] lSorted,
 223         int[] auxKey,
 224         int[] auxSorted,
 225         int R,
 226         int bitOff,
 227         int m)
 228     {
 229       int[] myHisto = null;
 230       int[] psHisto = null;
 231
 232       if (myId == 0) {
 233         myHisto = new int[numThread * R];
 234         global_myHisto = myHisto;
 235         psHisto = new int[numThread * R];
 236         global_psHisto = psHisto;
 237       }
 238
 239       Barrier.enterBarrier();
 240
 241       myHisto = global_myHisto;
 242       psHisto = global_psHisto;
 243
 244       for (int k = 0; k <  R; k++) {
 245         myHisto[((myId*R) + k)] = 0;
 246       }
 247
 248       LocalStartStop lss = new LocalStartStop();
 249       CreatePartition.createPartition(0, q, myId, numThread, lss);
 250
 251       for (int k = lss.i_start; k < lss.i_stop; k++) {
 252         myHisto[(myId*R) + BITS(lKey[k],bitOff,m)]++;
 253       }
 254
 255       Barrier.enterBarrier();
 256
 257       CreatePartition.createPartition(0, R, myId, numThread, lss);
 258
 259       int last;
 260       for (int k = lss.i_start; k < lss.i_stop; k++) {
 261         last = psHisto[k] = myHisto[k];
 262         for (int j = 1; j < numThread; j++) {
 263           int temp = psHisto[(j*R + k)] = last + myHisto[ (j*R + k)];
 264           last = temp;
 265         }
 266       }
 267
 268       Barrier.enterBarrier();
 269
 270       int offset = 0;
 271
 272       for (int k = 0; k < R; k++) {
 273         myHisto[(myId*R) +k] = (psHisto[ ((myId*R) + k)] - myHisto[ ((myId*R) +k])) + offset;
 274         offset += psHisto[((numThread -1) * R) + k];
 275       }
 276
 277       Barrier.enterBarrier();
 278
 279       CreatePartition.createPartition(0, q, myId, numThread, lss);
 280
 281       for (int k = lss.i_start; k < lss.i_stop; k++) {
 282         int j = BITS(lKey[k], bitOff, m);
 283         lSorted[myHisto[(myId*R) +j]] = lKey[k];
 284         auxSorted[myHisto[(myId*R) +j]] = auxKey[k];
 285         myHisto[(myId*R) +j]++;
 286       }
 287
 288       Barrier.enterBarrier();
 289
 290       if (myId == 0) {
 291         psHisto = null;
 292         myHisto = null;
 293       }
 294     }
 295
 296
 297   /* =============================================================================
 298    * all_radixsort_node_s3
 299    *
 300    * q (elems/proc) must be a multiple of NODES
 301    * =============================================================================
 302    */
 303   void
 304     all_radixsort_node_s3 (int q,
 305         int[] lKeys,
 306         int[] lSorted)
 307     {
 308
 309       int[] lTemp = null;
 310
 311       if (myId == 0) {
 312         lTemp = new int[ q];
 313         global_lTemp = lTemp;
 314       }
 315
 316       Barrier.enterBarrier();
 317
 318       lTemp = global_lTemp;
 319
 320       all_countsort_node(q, lKeys,   lSorted, (1<<11),  0, 11);
 321       all_countsort_node(q, lSorted, lTemp,   (1<<11), 11, 11);
 322       all_countsort_node(q, lTemp,   lSorted, (1<<10), 22, 10);
 323
 324       Barrier.enterBarrier();
 325
 326       if (myId == 0) {
 327         lTemp = null
 328       }
 329     }
 330
 331
 332   /* =============================================================================
 333    * all_radixsort_node_s2
 334    *
 335    * q (elems/proc) must be a multiple of NODES
 336    * =============================================================================
 337    */
 338   void
 339     all_radixsort_node_s2 (int q,
 340         int[] lKeys,
 341         int[] lSorted)
 342     {
 343
 344       int[] lTemp = null;
 345
 346       if (myId == 0) {
 347         lTemp = new int[ q];
 348         global_lTemp = lTemp;
 349       }
 350
 351       Barrier.enterBarrier();
 352
 353       lTemp = global_lTemp;
 354
 355       all_countsort_node(q, lKeys, lTemp,   (1<<16),  0, 16);
 356       all_countsort_node(q, lTemp, lSorted, (1<<16), 16, 16);
 357
 358       Barrier.enterBarrier();
 359
 360       if (myId == 0) {
 361         lTemp = null;
 362       }
 363     }
 364
 365
 366   /* =============================================================================
 367    * all_radixsort_node_aux_s3_seq
 368    *
 369    * q (elems/proc) must be a multiple of NODES
 370    * =============================================================================
 371    */
 372   void
 373     all_radixsort_node_aux_s3_seq (int q,
 374         int[] lKeys,
 375         int[] lSorted,
 376         int[] auxKey,
 377         int[] auxSorted)
 378     {
 379       int[] lTemp  = null;
 380       int[] lTemp2 = null;
 381
 382       lTemp = new int[ q];
 383       lTemp2 = new int[ q];
 384
 385       all_countsort_node_aux_seq(q, lKeys, lSorted, auxKey, auxSorted, (1<<11),  0, 11);
 386       all_countsort_node_aux_seq(q, lSorted, lTemp, auxSorted, lTemp2, (1<<11), 11, 11);
 387       all_countsort_node_aux_seq(q, lTemp, lSorted, lTemp2, auxSorted, (1<<10), 22, 10);
 388
 389       lTemp = null;
 390       lTemp2 = null;
 391     }
 392
 393
 394   /* =============================================================================
 395    * all_radixsort_node_aux_s3
 396    *
 397    * q (elems/proc) must be a multiple of NODES
 398    * =============================================================================
 399    */
 400   public static void
 401     all_radixsort_node_aux_s3 (int q,
 402         int[] lKeys,
 403         int[] lSorted,
 404         int[] auxKey,
 405         int[] auxSorted)
 406     {
 407       int[] lTemp  = null;
 408       int[] lTemp2 = null;
 409
 410       if (myId == 0) {
 411         lTemp = new int[ q];
 412         global_lTemp = lTemp;
 413         lTemp2 = new int[ q];
 414         global_lTemp2 = lTemp2;
 415       }
 416
 417       Barrier.enterBarrier();
 418
 419       lTemp  = global_lTemp;
 420       lTemp2 = global_lTemp2;
 421
 422       all_countsort_node_aux(q, lKeys, lSorted, auxKey, auxSorted, (1<<11),  0, 11);
 423       all_countsort_node_aux(q, lSorted, lTemp, auxSorted, lTemp2, (1<<11), 11, 11);
 424       all_countsort_node_aux(q, lTemp, lSorted, lTemp2, auxSorted, (1<<10), 22, 10);
 425
 426       Barrier.enterBarrier();
 427
 428       if(myId = 0) {
 429         lTemp = null;
 430         lTemp2 = null;
 431       }
 432     }
 433 }
 434
 435 /* =============================================================================
 436  *
 437  * End of alg_radix_smp.java
 438  *
 439  * =============================================================================
 440  */
 441