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

   1 /* =============================================================================
   2  *
   3  * genScalData.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 GenScalData {
  48
  49   public int[] global_permV;
  50   public int[] global_cliqueSizes;
  51   public int global_totCliques;
  52   public int[] global_firstVsInCliques;
  53   public int[] global_lastVsInCliques;
  54   public int[] global_i_edgeStartCounter;
  55   public int[] global_i_edgeEndCounter;
  56   public int global_edgeNum;
  57   public int global_numStrWtEdges;
  58   public int[] global_startVertex;
  59   public int[] global_endVertex;
  60   public int[] global_tempIndex;
  61
  62   /**
  63    * Constructor
  64    **/
  65   public GenScalData() {
  66     global_permV;              = null;
  67     global_cliqueSizes        = null;
  68     global_totCliques         = 0;
  69     global_firstVsInCliques   = null;
  70     global_lastVsInCliques    = null;
  71     global_i_edgeStartCounter = null;
  72     global_i_edgeEndCounter   = null;
  73     global_edgeNum            = 0;
  74     global_numStrWtEdges      = 0;
  75     global_startVertex        = null;
  76     global_endVertex          = null;
  77     global_tempIndex          = null;
  78   }
  79
  80
  81   /**
  82    * =============================================================================
  83    *      genScalData_seq
  84    * =============================================================================
  85    **/
  86   void
  87     genScalData_seq (GraphSDG SDGdataPtr)
  88     {
  89       System.out.println("Call to genScalData_seq(), Unimplemented: TODO\n");
  90       System.exit(0);
  91     }
  92
  93
  94   /**
  95    * =============================================================================
  96    *       genScalData
  97    * =============================================================================
  98    */
  99
 100   public static void
 101     genScalData (int myId, int numThread, Globals glb, GraphSDG SDGdataPtr)
 102     {
 103       /*
 104        * STEP 0: Create the permutations required to randomize the vertices
 105        */
 106
 107       Random randomPtr = new Random();
 108       randomPtr = randomPtr.random_alloc();
 109       randomPtr.random_seed(myId);
 110
 111       int[] permV;
 112
 113       if (myId == 0) {
 114         permV = new int[glb.TOT_VERTICES];
 115         global_permV = permV;
 116       }
 117
 118       Barrier.enterBarrier();
 119
 120       permV = global_permV;
 121
 122       LocalStartStop lss = new LocalStartStop();
 123       CreatePartition cp = new CreatePartition();
 124       cp.createPartition(0, glb.TOT_VERTICES, myId, numThread, lss);
 125
 126       /* Initialize the array */
 127       for (int i = lss.i_start; i < lss.i_stop; i++) {
 128         permV[i] = i;
 129       }
 130
 131       Barrier.enterBarrier();
 132
 133       for (int i = i_start; i < i_stop; i++) {
 134         int t1 = randomPtr.random_generate();
 135         int t = i + t1 % (glb.TOT_VERTICES - i);
 136         if (t != i) {
 137           atomic {
 138             int t2 = permV[t];
 139             permV[t] = permV[i];
 140             permV[i] = t2;
 141           }
 142         }
 143       }
 144
 145       /*
 146        * STEP 1: Create Cliques
 147        */
 148
 149       int[] cliqueSizes;
 150
 151       int estTotCliques = (int)(Math.ceil(1.5d * glb.TOT_VERTICES / ((1+glb.MAX_CLIQUE_SIZE)/2)));
 152
 153       /*
 154        * Allocate mem for Clique array
 155        * Estimate number of clique required and pad by 50%
 156        */
 157       if (myId == 0) {
 158         cliqueSizes = new int[estTotCliques];
 159         global_cliqueSizes = cliqueSizes;
 160       }
 161
 162       Barrier.enterBarrier();
 163
 164       cliqueSizes = global_cliqueSizes;
 165
 166       cp.createPartition(0, estTotCliques, myId, numThread, lss);
 167
 168       /* Generate random clique sizes. */
 169       for (int i = lss.i_start; i < lss.i_stop; i++) {
 170         cliqueSizes[i] = 1 + (randomPtr.random_generate() % glb.MAX_CLIQUE_SIZE);
 171       }
 172
 173       Barrier.enterBarrier();
 174
 175       int totCliques = 0;
 176
 177       /*
 178        * Allocate memory for cliqueList
 179        */
 180
 181       int[] firstVsInCliques;
 182       int[] firstVsInCliques;
 183
 184       if (myId == 0) {
 185         lastVsInCliques = new int[estTotCliques];
 186         global_lastVsInCliques = lastVsInCliques;
 187         firstVsInCliques = new int[estTotCliques];
 188         global_firstVsInCliques = firstVsInCliques;
 189
 190         /*
 191          * Sum up vertices in each clique to determine the lastVsInCliques array
 192          */
 193
 194         lastVsInCliques[0] = cliqueSizes[0] - 1;
 195         int i;
 196         for (i = 1; i < estTotCliques; i++) {
 197           lastVsInCliques[i] = cliqueSizes[i] + lastVsInCliques[i-1];
 198           if (lastVsInCliques[i] >= glb.TOT_VERTICES-1) {
 199             break;
 200           }
 201         }
 202         totCliques = i + 1;
 203
 204         global_totCliques = totCliques;
 205
 206         /*
 207          * Fix the size of the last clique
 208          */
 209         cliqueSizes[(totCliques-1)] =
 210           glb.TOT_VERTICES - lastVsInCliques[(totCliques-2)] - 1;
 211         lastVsInCliques[totCliques-1] = glb.TOT_VERTICES - 1;
 212
 213         firstVsInCliques[0] = 0;
 214
 215       }
 216
 217       Barrier.enterBarrier();
 218
 219       lastVsInCliques  = global_lastVsInCliques;
 220       firstVsInCliques = global_firstVsInCliques;
 221       totCliques = global_totCliques;
 222
 223       /* Compute start Vertices in cliques. */
 224       cp.createPartition(1, totCliques, myId, numThread, lss);
 225       for (int i = i_start; i < i_stop; i++) {
 226         firstVsInCliques[i] = lastVsInCliques[i-1] + 1;
 227       }
 228
 229       /* TODO : if required
 230
 231 #ifdef WRITE_RESULT_FILES
 232 Barrier.enterBarrier();
 233
 234       // Write the generated cliques to file for comparison with Kernel 4
 235       if (myId == 0) {
 236       FILE* outfp = fopen("cliques.txt", "w");
 237       fSystem.out.println(outfp, "No. of cliques - %lu\n", totCliques);
 238       for (i = 0; i < totCliques; i++) {
 239       fSystem.out.println(outfp, "Clq %lu - ", i);
 240       int j;
 241       for (j = firstVsInCliques[i]; j <= lastVsInCliques[i]; j++) {
 242       fSystem.out.println(outfp, "%lu ", permV[j]);
 243       }
 244       fSystem.out.println(outfp, "\n");
 245       }
 246       fclose(outfp);
 247       }
 248
 249       Barrier.enterBarrier();
 250 #endif
 251 */
 252
 253       /*
 254        * STEP 2: Create the edges within the cliques
 255        */
 256
 257       /*
 258        * Estimate number of edges - using an empirical measure
 259        */
 260       int estTotEdges;
 261       if (glb.SCALE >= 12) {
 262         estTotEdges = (int) (Math.ceil(1.0d *((glb.MAX_CLIQUE_SIZE-1) * glb.TOT_VERTICES)));
 263       } else {
 264         estTotEdges = (int) (Math.ceil(1.2d * (((glb.MAX_CLIQUE_SIZE-1)*glb.TOT_VERTICES)
 265                 * ((1 + glb.MAX_PARAL_EDGES)/2) + glb.TOT_VERTICES*2)));
 266       }
 267
 268       /*
 269        * Initialize edge counter
 270        */
 271       int i_edgePtr = 0;
 272       float p = glb.PROB_UNIDIRECTIONAL;
 273
 274       /*
 275        * Partial edgeLists
 276        */
 277
 278       int[] startV;
 279       int[] endV;
 280
 281       if (numThread > 3) {
 282         int numByte = 1.5 * (estTotEdges/numThread);
 283         startV = new int[numByte];
 284         endV = new int[numByte];
 285       } else  {
 286         int numByte = (estTotEdges/numThread);
 287         startV = new int[numByte];
 288         endV = new int[numByte];
 289       }
 290
 291       /*
 292        * Tmp array to keep track of the no. of parallel edges in each direction
 293        */
 294       int[][] tmpEdgeCounter = new int[glb.MAX_CLIQUE_SIZE][glb.MAX_CLIQUE_SIZE];
 295
 296       /*
 297        * Create edges in parallel
 298        */
 299       //int i_clique;
 300       cp.createPartition(0, totCliques, myId, numThread, lss);
 301
 302       for (int i_clique = lss.i_start; i_clique < lss.i_stop; i_clique++) {
 303
 304         /*
 305          * Get current clique parameters
 306          */
 307
 308         int i_cliqueSize = cliqueSizes[i_clique];
 309         int i_firstVsInClique = firstVsInCliques[i_clique];
 310
 311         /*
 312          * First create at least one edge between two vetices in a clique
 313          */
 314
 315         for (int i = 0; i < i_cliqueSize; i++) {
 316           for (int j = 0; j < i; j++) {
 317             float r = (float)(randomPtr.random_generate() % 1000) / (float)1000;
 318             if (r >= p) {
 319
 320               startV[i_edgePtr] = i + i_firstVsInClique;
 321               endV[i_edgePtr] = j + i_firstVsInClique;
 322               i_edgePtr++;
 323               tmpEdgeCounter[i][j] = 1;
 324
 325               startV[i_edgePtr] = j + i_firstVsInClique;
 326               endV[i_edgePtr] = i + i_firstVsInClique;
 327               i_edgePtr++;
 328               tmpEdgeCounter[j][i] = 1;
 329
 330             } else  if (r >= 0.5) {
 331
 332               startV[i_edgePtr] = i + i_firstVsInClique;
 333               endV[i_edgePtr] = j + i_firstVsInClique;
 334               i_edgePtr++;
 335               tmpEdgeCounter[i][j] = 1;
 336               tmpEdgeCounter[j][i] = 0;
 337
 338             } else {
 339
 340               startV[i_edgePtr] = j + i_firstVsInClique;
 341               endV[i_edgePtr] = i + i_firstVsInClique;
 342               i_edgePtr++;
 343               tmpEdgeCounter[j][i] = 1;
 344               tmpEdgeCounter[i][j] = 0;
 345
 346             }
 347
 348           } /* for j */
 349         } /* for i */
 350
 351         if (i_cliqueSize != 1) {
 352           int randNumEdges = randomPtr.random_generate() % (2*i_cliqueSize*glb.MAX_PARAL_EDGES);
 353           //int i_paralEdge;
 354           for (int i_paralEdge = 0; i_paralEdge < randNumEdges; i_paralEdge++) {
 355             int i = (int) (randomPtr.random_generate() % i_cliqueSize);
 356             int j = (int) (randomPtr.random_generate() % i_cliqueSize);
 357             if ((i != j) && (tmpEdgeCounter[i][j] < glb.MAX_PARAL_EDGES)) {
 358               float r = (float)(randomPtr.random_generate() % 1000) / (float)1000;
 359               if (r >= p) {
 360                 /* Copy to edge structure. */
 361                 startV[i_edgePtr] = i + i_firstVsInClique;
 362                 endV[i_edgePtr] = j + i_firstVsInClique;
 363                 i_edgePtr++;
 364                 tmpEdgeCounter[i][j]++;
 365               }
 366             }
 367           }
 368         }
 369
 370       } /* for i_clique */
 371
 372       tmpEdgeCounter = null;
 373
 374       /*
 375        * Merge partial edge lists
 376        */
 377
 378       int[] i_edgeStartCounter;
 379       int[] i_edgeEndCounter;
 380
 381       if (myId == 0) {
 382         i_edgeStartCounter = new int[ numThread];
 383         global_i_edgeStartCounter = i_edgeStartCounter;
 384         i_edgeEndCounter = new int[numThread];
 385         global_i_edgeEndCounter = i_edgeEndCounter;
 386       }
 387
 388       Barrier.enterBarrier();
 389
 390       i_edgeStartCounter = global_i_edgeStartCounter;
 391       i_edgeEndCounter   = global_i_edgeEndCounter;
 392
 393       i_edgeEndCounter[myId] = i_edgePtr;
 394       i_edgeStartCounter[myId] = 0;
 395
 396       Barrier.enterBarrier();
 397
 398       if (myId == 0) {
 399         for (int i = 1; i < numThread; i++) {
 400           i_edgeEndCounter[i] = i_edgeEndCounter[i-1] + i_edgeEndCounter[i];
 401           i_edgeStartCounter[i] = i_edgeEndCounter[i-1];
 402         }
 403       }
 404
 405       atomic {
 406         global_edgeNum = global_edgeNum + i_edgePtr;
 407       }
 408
 409       Barrier.enterBarrier();
 410
 411       int edgeNum = global_edgeNum;
 412
 413       /*
 414        * Initialize edge list arrays
 415        */
 416
 417       int[] startVertex;
 418       int[] endVertex;
 419
 420       if (myId == 0) {
 421         if (glb.SCALE < 10) {
 422           int numByte = 2 * edgeNum;
 423           startVertex = new int[numByte];
 424           endVertex = new int[numByte];
 425         } else {
 426           int numByte = (edgeNum + glb.MAX_PARAL_EDGES * glb.TOT_VERTICES);
 427           startVertex = new int[numByte];
 428           endVertex = new int[numByte];
 429         }
 430         global_startVertex = startVertex;
 431         global_endVertex = endVertex;
 432       }
 433
 434       Barrier.enterBarrier();
 435
 436       startVertex = global_startVertex;
 437       endVertex = global_endVertex;
 438
 439       for (int i =  i_edgeStartCounter[myId]; i <  i_edgeEndCounter[myId]; i++) {
 440         startVertex[i] = startV[i-i_edgeStartCounter[myId]];
 441         endVertex[i] = endV[i-i_edgeStartCounter[myId]];
 442       }
 443
 444       int numEdgesPlacedInCliques = edgeNum;
 445
 446       Barrier.enterBarrier();
 447
 448       /*
 449        * STEP 3: Connect the cliques
 450        */
 451
 452       i_edgePtr = 0;
 453       p = PROB_INTERCL_EDGES;
 454
 455       /*
 456        * Generating inter-clique edges as given in the specs
 457        */
 458
 459       cp.createPartition(0, glb.TOT_VERTICES, myId, numThread, lss);
 460
 461       for (int i = lss.i_start; i < lss.i_stop; i++) {
 462         int tempVertex1 = i;
 463         int h = totCliques;
 464         int l = 0;
 465         int t = -1;
 466         while (h - l > 1) {
 467           int m =  ((h + l) / 2);
 468           if (tempVertex1 >= firstVsInCliques[m]) {
 469             l = m;
 470           } else {
 471             if ((tempVertex1 < firstVsInCliques[m]) && (m > 0)) {
 472               if (tempVertex1 >= firstVsInCliques[m-1]) {
 473                 t = m - 1;
 474                 break;
 475               } else {
 476                 h = m;
 477               }
 478             }
 479           }
 480         }
 481
 482         if (t == -1) {
 483           int m;
 484           for (m = (l + 1); m < h; m++) {
 485             if (tempVertex1<firstVsInCliques[m]) {
 486               break;
 487             }
 488           }
 489           t = m-1;
 490         }
 491
 492         int t1 = firstVsInCliques[t];
 493
 494         //int d;
 495         for (int d = 1, p = glb.PROB_INTERCL_EDGES; d < glb.TOT_VERTICES; d *= 2, p /= 2) {
 496
 497           float r = (float)(randomPtr.random_generate() % 1000) / (float)1000;
 498
 499           if (r <= p) {
 500
 501             int tempVertex2 =  ((i+d) % glb.TOT_VERTICES);
 502
 503             h = totCliques;
 504             l = 0;
 505             t = -1;
 506             while (h - l > 1) {
 507               int m = (((h + l) / 2);
 508               if (tempVertex2 >= firstVsInCliques[m]) {
 509                 l = m;
 510               } else {
 511                 if ((tempVertex2 < firstVsInCliques[m]) && (m > 0)) {
 512                   if (firstVsInCliques[m-1] <= tempVertex2) {
 513                     t = m - 1;
 514                     break;
 515                   } else {
 516                     h = m;
 517                   }
 518                 }
 519               }
 520             }
 521
 522             if (t == -1) {
 523               //int m;
 524               int m;
 525               for (m = (l + 1); m < h; m++) {
 526                 if (tempVertex2 < firstVsInCliques[m]) {
 527                   break;
 528                 }
 529               }
 530               t = m - 1;
 531             }
 532
 533             int t2 = firstVsInCliques[t];
 534
 535             if (t1 != t2) {
 536               int randNumEdges =
 537                 randomPtr.random_generate() % glb.MAX_PARAL_EDGES + 1;
 538               //int j;
 539               for (int j = 0; j < randNumEdges; j++) {
 540                 startV[i_edgePtr] = tempVertex1;
 541                 endV[i_edgePtr] = tempVertex2;
 542                 i_edgePtr++;
 543               }
 544             }
 545
 546           } /* r <= p */
 547
 548           float r0 = (float)(randomPtr.random_generate() % 1000) / (float)1000;
 549
 550           if ((r0 <= p) && (i-d>=0)) {
 551             int tempVertex2 = (i - d) % glb.TOT_VERTICES;
 552
 553             h = totCliques;
 554             l = 0;
 555             t = -1;
 556             while (h - l > 1) {
 557               int m = ((h + l) / 2);
 558               if (tempVertex2 >= firstVsInCliques[m]) {
 559                 l = m;
 560               } else {
 561                 if ((tempVertex2 < firstVsInCliques[m]) && (m > 0)) {
 562                   if (firstVsInCliques[m-1] <= tempVertex2) {
 563                     t = m - 1;
 564                     break;
 565                   } else {
 566                     h = m;
 567                   }
 568                 }
 569               }
 570             }
 571
 572             if (t == -1) {
 573               int m;
 574               for (m =  (l + 1); m <  h; m++) {
 575                 if (tempVertex2 < firstVsInCliques[m]) {
 576                   break;
 577                 }
 578               }
 579               t = m - 1;
 580             }
 581
 582             int t2 = firstVsInCliques[t];
 583
 584             if (t1 != t2) {
 585               int randNumEdges =
 586                 randomPtr.random_generate() % glb.MAX_PARAL_EDGES + 1;
 587               for (int j = 0; j <  randNumEdges; j++) {
 588                 startV[i_edgePtr] = tempVertex1;
 589                 endV[i_edgePtr] = tempVertex2;
 590                 i_edgePtr++;
 591               }
 592             }
 593
 594           } /* r0 <= p && (i-d) > 0 */
 595
 596         } /* for d, p */
 597
 598       } /* for i */
 599
 600
 601       i_edgeEndCounter[myId] = i_edgePtr;
 602       i_edgeStartCounter[myId] = 0;
 603
 604       if (myId == 0) {
 605         global_edgeNum = 0;
 606       }
 607
 608       Barrier.enterBarrier();
 609
 610       if (myId == 0) {
 611         for (int i = 1; i <  numThread; i++) {
 612           i_edgeEndCounter[i] = i_edgeEndCounter[i-1] + i_edgeEndCounter[i];
 613           i_edgeStartCounter[i] = i_edgeEndCounter[i-1];
 614         }
 615       }
 616
 617       atomic {
 618         global_edgeNum = global_edgeNum + i_edgePtr;
 619       }
 620
 621       Barrier.enterBarrier();
 622
 623       edgeNum = global_edgeNum;
 624       int numEdgesPlacedOutside = global_edgeNum;
 625
 626       for (int i = (i_edgeStartCounter[myId]; i <  i_edgeEndCounter[myId]; i++) {
 627         startVertex[i+numEdgesPlacedInCliques] = startV[i-i_edgeStartCounter[myId]];
 628         endVertex[i+numEdgesPlacedInCliques] = endV[i-i_edgeStartCounter[myId]];
 629       }
 630
 631       Barrier.enterBarrier();
 632
 633       int numEdgesPlaced = numEdgesPlacedInCliques + numEdgesPlacedOutside;
 634
 635       if (myId == 0) {
 636         SDGdataPtr.numEdgesPlaced =  numEdgesPlaced;
 637
 638         System.out.println("Finished generating edges");
 639         System.out.println("No. of intra-clique edges - " + numEdgesPlacedInCliques);
 640         System.out.println("No. of inter-clique edges - " + numEdgesPlacedOutside);
 641         System.out.println("Total no. of edges        - " + numEdgesPlaced);
 642       }
 643
 644       Barrier.enterBarrier();
 645
 646       /*
 647        * STEP 4: Generate edge weights
 648        */
 649
 650       if (myId == 0) {
 651         SDGdataPtr.intWeight = new int[numEdgesPlaced];
 652       }
 653
 654       Barrier.enterBarrier();
 655
 656       p = glb.PERC_INT_WEIGHTS;
 657       int numStrWtEdges  = 0;
 658
 659       cp.createPartition(0, numEdgesPlaced, myId, numThread, lss);
 660
 661       for (int i = lss.i_start; i < lss.i_stop; i++) {
 662         float r = (float)(randomPtr.random_generate() % 1000) / (float)1000;
 663         if (r <= p) {
 664           SDGdataPtr.intWeight[i] =
 665             1 + (randomPtr.random_generate() % (MAX_INT_WEIGHT-1));
 666         } else {
 667           SDGdataPtr.intWeight[i] = -1;
 668           numStrWtEdges++;
 669         }
 670       }
 671
 672       Barrier.enterBarrier();
 673
 674       if (myId == 0) {
 675         int t = 0;
 676         for (int i = 0; i < numEdgesPlaced; i++) {
 677           if (SDGdataPtr.intWeight[i] < 0) {
 678             SDGdataPtr.intWeight[i] = -t;
 679             t++;
 680           }
 681         }
 682       }
 683
 684       atomic {
 685         global_numStrWtEdges = global_numStrWtEdges + numStrWtEdges;
 686       }
 687
 688       Barrier.enterBarrier();
 689
 690       numStrWtEdges = global_numStrWtEdges;
 691
 692       if (myId == 0) {
 693         SDGdataPtr.strWeight = new char[numStrWtEdges * glb.MAX_STRLEN];
 694       }
 695
 696       Barrier.enterBarrier();
 697
 698       cp.createPartition(0, numEdgesPlaced, myId, numThread, lss);
 699
 700       for (int i = lss.i_start; i < lss.i_stop; i++) {
 701         if (SDGdataPtr.intWeight[i] <= 0) {
 702           for (int j = 0; j < glb.MAX_STRLEN; j++) {
 703             SDGdataPtr.strWeight[(-SDGdataPtr.intWeight[i])*glb.MAX_STRLEN+j] =
 704               //     (char) (1 + PRANDOM_GENERATE(stream) % 127);
 705               //FIXME
 706               (char) (1 + (randomPtr.random_generate() % 127));
 707           }
 708         }
 709       }
 710
 711       /*
 712        * Choose SOUGHT STRING randomly if not assigned
 713        */
 714
 715       if (myId == 0) {
 716
 717         if (SOUGHT_STRING.length != glb.MAX_STRLEN) {
 718           glb.SOUGHT_STRING = new char[MAX_STRLEN];
 719         }
 720
 721         int t = randomPtr.random_generate() % numStrWtEdges;
 722         for (int j = 0; j < glb.MAX_STRLEN; j++) {
 723           //FIXME
 724           SOUGHT_STRING[j] =
 725             (char) (SDGdataPtr.strWeight[(t*glb.MAX_STRLEN+j)]);
 726         }
 727
 728       }
 729
 730       Barrier.enterBarrier();
 731
 732       /*
 733        * STEP 5: Permute Vertices
 734        */
 735
 736       for (int i = lss.i_start; i < lss.i_stop; i++) {
 737         startVertex[i] = permV[(startVertex[i])];
 738         endVertex[i] = permV[(endVertex[i])];
 739       }
 740
 741       Barrier.enterBarrier();
 742
 743       /*
 744        * STEP 6: Sort Vertices
 745        */
 746
 747       /*
 748        * Radix sort with StartVertex as primary key
 749        */
 750
 751       if (myId == 0) {
 752         int numByte = numEdgesPlaced;
 753         SDGdataPtr.startVertex = new int[numByte];
 754         SDGdataPtr.endVertex = new int[numByte];
 755       }
 756
 757       Barrier.enterBarrier();
 758
 759       Alg_Radix_Smp.all_radixsort_node_aux_s3(numEdgesPlaced,
 760           startVertex,
 761           SDGdataPtr.startVertex,
 762           endVertex,
 763           SDGdataPtr.endVertex);
 764
 765       Barrier.enterBarrier();
 766
 767       if (glb.SCALE < 12) {
 768
 769         /*
 770          * Sort with endVertex as secondary key
 771          */
 772
 773         if (myId == 0) {
 774
 775           int i0 = 0;
 776           int i1 = 0;
 777           int i = 0;
 778
 779           while (i < numEdgesPlaced) {
 780
 781             for (i = i0; i < numEdgesPlaced; i++) {
 782               if (SDGdataPtr.startVertex[i] !=
 783                   SDGdataPtr.startVertex[i1])
 784               {
 785                 i1 = i;
 786                 break;
 787               }
 788             }
 789
 790             //int j;
 791             for (int j = i0; j < i1; j++) {
 792               //int k;
 793               for (int k = j+1; k < i1; k++) {
 794                 if (SDGdataPtr.endVertex[k] <
 795                     SDGdataPtr.endVertex[j])
 796                 {
 797                   int t = SDGdataPtr.endVertex[j];
 798                   SDGdataPtr.endVertex[j] = SDGdataPtr.endVertex[k];
 799                   SDGdataPtr.endVertex[k] = t;
 800                 }
 801               }
 802             }
 803
 804             if (SDGdataPtr.startVertex[i0] != glb.TOT_VERTICES-1) {
 805               i0 = i1;
 806             } else {
 807               //int j;
 808               for (int j=i0; j<numEdgesPlaced; j++) {
 809                 //int k;
 810                 for (int k=j+1; k<numEdgesPlaced; k++) {
 811                   if (SDGdataPtr.endVertex[k] <
 812                       SDGdataPtr.endVertex[j])
 813                   {
 814                     int t = SDGdataPtr.endVertex[j];
 815                     SDGdataPtr.endVertex[j] = SDGdataPtr.endVertex[k];
 816                     SDGdataPtr.endVertex[k] = t;
 817                   }
 818                 }
 819               }
 820             }
 821
 822           } /* while i < numEdgesPlaced */
 823
 824         }
 825
 826       } else {
 827
 828         int[] tempIndex;
 829
 830         if (myId == 0) {
 831
 832           tempIndex = new int[glb.TOT_VERTICES + 1];
 833           global_tempIndex = tempIndex;
 834
 835           /*
 836            * Update degree of each vertex
 837            */
 838
 839           tempIndex[0] = 0;
 840           tempIndex[glb.TOT_VERTICES] = numEdgesPlaced;
 841           int i0 = 0;
 842
 843           for (int i=0; i < glb.TOT_VERTICES; i++) {
 844             tempIndex[i+1] = tempIndex[i];
 845             //int j;
 846             for (int j = i0; j <  numEdgesPlaced; j++) {
 847               if (SDGdataPtr.startVertex[j] !=
 848                   SDGdataPtr.startVertex[i0])
 849               {
 850                 if (SDGdataPtr.startVertex[i0] == i) {
 851                   tempIndex[i+1] = j;
 852                   i0 = j;
 853                   break;
 854                 }
 855               }
 856             }
 857           }
 858         }
 859
 860         Barrier.enterBarrier();
 861
 862         tempIndex = global_tempIndex;
 863
 864         /*
 865          * Insertion sort for now, replace with something better later on
 866          */
 867
 868
 869         if (myId == 0) {
 870           for (int i = 0; i < glb.TOT_VERTICES; i++) {
 871             for (int j =  tempIndex[i]; j <  tempIndex[i+1]; j++) {
 872               for (int k = (j + 1); k < tempIndex[i+1]; k++) {
 873                 if (SDGdataPtr.endVertex[k] <
 874                     SDGdataPtr.endVertex[j])
 875                 {
 876                   int t = SDGdataPtr.endVertex[j];
 877                   SDGdataPtr.endVertex[j] = SDGdataPtr.endVertex[k];
 878                   SDGdataPtr.endVertex[k] = t;
 879                 }
 880               }
 881             }
 882           }
 883         }
 884
 885       } /* SCALE >= 12 */
 886
 887     }
 888 }
 889
 890 /* =============================================================================
 891  *
 892  * End of genScalData.java
 893  *
 894  * =============================================================================
 895  */