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

   1 /* =============================================================================
   2  *
   3  * computeGraph.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 ComputeGraph {
  48   public Graph GPtr;
  49   public GraphSDG SDGdataPtr;
  50
  51   public int[] global_p;
  52   public int global_maxNumVertices;
  53   public int global_outVertexListSize;
  54   public int[] global_impliedEdgeList;
  55   public int[][] global_auxArr;
  56
  57   public ComputeGraph() {
  58     global_p                 = null;
  59     global_maxNumVertices    = 0;
  60     global_outVertexListSize = 0;
  61     global_impliedEdgeList   = null;
  62     global_auxArr            = null;
  63   }
  64
  65   public int NOSHARE(int x) {
  66     x = x << 7;
  67     return x;
  68   }
  69
  70   /* =============================================================================
  71    * prefix_sums
  72    * =============================================================================
  73    */
  74   public void
  75     prefix_sums (int myId, int numThread, int[] result, int[] input, int arraySize)
  76     {
  77       int[]  p;
  78       if (myId == 0) {
  79         p = new int[NOSHARE(numThread)];
  80         global_p = p;
  81       }
  82
  83       Barrier.enterBarrier();
  84
  85       p = global_p;
  86
  87       int start;
  88       int end;
  89
  90       int r = arraySize / numThread;
  91       start = myId * r + 1;
  92       end = (myId + 1) * r;
  93       if (myId == (numThread - 1)) {
  94         end = arraySize;
  95       }
  96
  97       for (int j =  start; j <  end; j++) {
  98         result[j] = input[j-1] + result[j-1];
  99       }
 100
 101       p[NOSHARE(myId)] = result[end-1];
 102
 103       Barrier.enterBarrier();
 104
 105       if (myId == 0) {
 106         for (int j = 1; j < numThread; j++) {
 107           p[NOSHARE(j)] += p[NOSHARE(j-1)];
 108         }
 109       }
 110
 111       Barrier.enterBarrier();
 112
 113       if (myId > 0) {
 114         int add_value = p[NOSHARE(myId-1)];
 115         for (j = start-1; j < end; j++) {
 116           result[j] += add_value;
 117         }
 118       }
 119
 120       Barrier.enterBarrier();
 121
 122       if (myId == 0) {
 123         p = null;
 124       }
 125     }
 126
 127
 128   /* =============================================================================
 129    * computeGraph
 130    * =============================================================================
 131    */
 132   public static void
 133     computeGraph (int myId, int numThread, Globals glb, ComputeGraph computeGraphArgs)
 134
 135     {
 136       Barrier.enterBarrier();
 137
 138       //Graph GPtr = computeGraphArgs.GPtr;
 139       //GraphSDG SDGdataPtr = computeGraphArgs.SDGdata;
 140
 141       int j;
 142       int maxNumVertices = 0;
 143       int numEdgesPlaced = computeGraphArgs.SDGdataPtr.numEdgesPlaced;
 144
 145       /*
 146        * First determine the number of vertices by scanning the tuple
 147        * startVertex list
 148        */
 149       LocalStartStop lss = new LocalStartStop();
 150       CreatePartition.createPartition(0, numEdgesPlaced, myId, numThread, lss);
 151
 152       for (int i = lss.i_start; i < lss.i_stop; i++) {
 153         if (computeGraphArgs.SDGdataPtr.startVertex[i] > maxNumVertices) {
 154           maxNumVertices = computeGraphArgs.SDGdataPtr.startVertex[i];
 155         }
 156       }
 157
 158       atomic {
 159         int tmp_maxNumVertices = global_maxNumVertices;
 160         int new_maxNumVertices = CreatePartition.MAX( tmp_maxNumVertices, maxNumVertices) + 1;
 161         global_maxNumVertices = new_maxNumVertices;
 162       }
 163
 164       Barrier.enterBarrier();
 165
 166       maxNumVertices = global_maxNumVertices;
 167
 168       if (myId == 0) {
 169
 170         computeGraphArgs.GPtr.numVertices = maxNumVertices;
 171         computeGraphArgs.GPtr.numEdges    = numEdgesPlaced;
 172         computeGraphArgs.GPtr.intWeight   = computeGraphArgs.SDGdataPtr.intWeight;
 173         computeGraphArgs.GPtr.strWeight   = computeGraphArgs.SDGdataPtr.strWeight;
 174
 175         for (int i = 0; i < numEdgesPlaced; i++) {
 176           if (computeGraphArgs.GPtr.intWeight[numEdgesPlaced-i-1] < 0) {
 177             computeGraphArgs.GPtr.numStrEdges = -(computeGraphArgs.GPtr.intWeight[numEdgesPlaced-i-1]) + 1;
 178             computeGraphArgs.GPtr.numIntEdges = numEdgesPlaced - computeGraphArgs.GPtr.numStrEdges;
 179             break;
 180           }
 181         }
 182
 183         computeGraphArgs.GPtr.outDegree = new int[computeGraphArgs.GPtr.numVertices];
 184
 185         computeGraphArgs.GPtr.outVertexIndex = new int[computeGraphArgs.GPtr.numVertices];
 186       }
 187
 188       Barrier.enterBarrier();
 189
 190       CreatePartition.createPartition(0, computeGraphArgs.GPtr.numVertices, myId, numThread, lss);
 191
 192       for (i = lss.i_start; i < lss.i_stop; i++) {
 193         computeGraphArgs.GPtr.outDegree[i] = 0;
 194         computeGraphArgs.GPtr.outVertexIndex[i] = 0;
 195       }
 196
 197       int outVertexListSize = 0;
 198
 199       Barrier.enterBarrier();
 200
 201       int i0 = -1;
 202
 203       for (int i = lss.i_start; i < lss.i_stop; i++) {
 204         int k = i;
 205         if ((outVertexListSize == 0) && (k != 0)) {
 206           while (i0 == -1) {
 207             for (int j = 0; j < numEdgesPlaced; j++) {
 208               if (k == computeGraphArgs.SDGdataPtr.startVertex[j]) {
 209                 i0 = j;
 210                 break;
 211               }
 212
 213             }
 214             k--;
 215           }
 216         }
 217
 218         if ((outVertexListSize == 0) && (k == 0)) {
 219           i0 = 0;
 220         }
 221
 222         for (int j = i0; j < numEdgesPlaced; j++) {
 223           if (i == computeGraphArgs.GPtr.numVertices-1) {
 224             break;
 225           }
 226           if ((i != computeGraphArgs.SDGdataPtr.startVertex[j])) {
 227             if ((j > 0) && (i == computeGraphArgs.SDGdataPtr.startVertex[j-1])) {
 228               if (j-i0 >= 1) {
 229                 outVertexListSize++;
 230                 computeGraphArgs.GPtr.outDegree[i]++;
 231                 for (int t = (i0+1); t < j; t++) {
 232                   if (computeGraphArgs.SDGdataPtr.endVertex[t] !=
 233                       computeGraphArgs.SDGdataPtr.endVertex[t-1])
 234                   {
 235                     outVertexListSize++;
 236                     computeGraphArgs.GPtr.outDegree[i] = computeGraphArgs.GPtr.outDegree[i]+1;
 237                   }
 238                 }
 239               }
 240             }
 241             i0 = j;
 242             break;
 243           }
 244         }
 245
 246         if (i == computeGraphArgs.GPtr.numVertices-1) {
 247           if (numEdgesPlaced-i0 >= 0) {
 248             outVertexListSize++;
 249             computeGraphArgs.GPtr.outDegree[i]++;
 250             for (int t =  (i0+1); t < numEdgesPlaced; t++) {
 251               if (computeGraphArgs.SDGdataPtr.endVertex[t] != computeGraphArgs.SDGdataPtr.endVertex[t-1]) {
 252                 outVertexListSize++;
 253                 computeGraphArgs.GPtr.outDegree[i]++;
 254               }
 255             }
 256           }
 257         }
 258
 259       } /* for i */
 260
 261       Barrier.enterBarrier();
 262
 263       prefix_sums(myId, numThread, computeGraphArgs.GPtr.outVertexIndex, computeGraphArgs.GPtr.outDegree, computeGraphArgs.GPtr.numVertices);
 264
 265       Barrier.enterBarrier();
 266
 267       atomic {
 268         global_outVertexListSize = global_outVertexListSize + outVertexListSize;
 269       }
 270
 271       Barrier.enterBarrier();
 272
 273       outVertexListSize = global_outVertexListSize;
 274
 275       if (myId == 0) {
 276         computeGraphArgs.GPtr.numDirectedEdges = outVertexListSize;
 277         computeGraphArgs.GPtr.outVertexList = new int[outVertexListSize];
 278         computeGraphArgs.GPtr.paralEdgeIndex = new int[outVertexListSize];
 279         computeGraphArgs.GPtr.outVertexList[0] = computeGraphArgs.SDGdataPtr.endVertex[0];
 280       }
 281
 282       Barrier.enterBarrier();
 283
 284       /*
 285        * Evaluate outVertexList
 286        */
 287
 288       i0 = -1;
 289
 290       for (int i = lss.i_start; i < lss.i_stop; i++) {
 291
 292         int k =  i;
 293         while ((i0 == -1) && (k != 0)) {
 294           for (int j = 0; j < numEdgesPlaced; j++) {
 295             if (k == computeGraphArgs.SDGdataPtr.startVertex[j]) {
 296               i0 = j;
 297               break;
 298             }
 299           }
 300           k--;
 301         }
 302
 303         if ((i0 == -1) && (k == 0)) {
 304           i0 = 0;
 305         }
 306
 307         for (int j = i0; j < numEdgesPlaced; j++) {
 308           if (i == computeGraphArgs.GPtr.numVertices-1) {
 309             break;
 310           }
 311           if (i != computeGraphArgs.SDGdataPtr.startVertex[j]) {
 312             if ((j > 0) && (i == computeGraphArgs.SDGdataPtr.startVertex[j-1])) {
 313               if (j-i0 >= 1) {
 314                 int ii =  (computeGraphArgs.GPtr.outVertexIndex[i]);
 315                 int r = 0;
 316                 computeGraphArgs.GPtr.paralEdgeIndex[ii] = i0;
 317                 computeGraphArgs.GPtr.outVertexList[ii] = computeGraphArgs.SDGdataPtr.endVertex[ i0];
 318                 r++;
 319                 for (int t =  (i0+1); t < j; t++) {
 320                   if (computeGraphArgs.SDGdataPtr.endVertex[t] !=
 321                       computeGraphArgs.SDGdataPtr.endVertex[t-1])
 322                   {
 323                     computeGraphArgs.GPtr.paralEdgeIndex[ii+r] = t;
 324                     computeGraphArgs.GPtr.outVertexList[ii+r] = computeGraphArgs.SDGdataPtr.endVertex[t];
 325                     r++;
 326                   }
 327                 }
 328
 329               }
 330             }
 331             i0 = j;
 332             break;
 333           }
 334         } /* for j */
 335
 336         if (i == computeGraphArgs.GPtr.numVertices-1) {
 337           int r = 0;
 338           if (numEdgesPlaced-i0 >= 0) {
 339             int ii = computeGraphArgs.GPtr.outVertexIndex[i];
 340             computeGraphArgs.GPtr.paralEdgeIndex[ii+r] = i0;
 341             computeGraphArgs.GPtr.outVertexList[ii+r] = computeGraphArgs.SDGdataPtr.endVertex[i0];
 342             r++;
 343             for (int t = i0+1; t < numEdgesPlaced; t++) {
 344               if (computeGraphArgs.SDGdataPtr.endVertex[t] != computeGraphArgs.SDGdataPtr.endVertex[t-1]) {
 345                 computeGraphArgs.GPtr.paralEdgeIndex[ii+r] = t;
 346                 computeGraphArgs.GPtr.outVertexList[ii+r] = computeGraphArgs.SDGdataPtr.endVertex[t];
 347                 r++;
 348               }
 349             }
 350           }
 351         }
 352
 353       } /* for i */
 354
 355       Barrier.enterBarrier();
 356
 357       if (myId == 0) {
 358         computeGraphArgs.SDGdataPtr.startVertex = null;
 359         computeGraphArgs.SDGdataPtr.endVertex = null;
 360         computeGraphArgs.GPtr.inDegree = new int[computeGraphArgs.GPtr.numVertices];
 361         computeGraphArgs.GPtr.inVertexIndex = new int[computeGraphArgs.GPtr.numVertices];
 362       }
 363
 364       Barrier.enterBarrier();
 365
 366       for (int i = lss.i_start; i < lss.i_stop; i++) {
 367         computeGraphArgs.GPtr.inDegree[i] = 0;
 368         computeGraphArgs.GPtr.inVertexIndex[i] = 0;
 369       }
 370
 371       /* A temp. array to store the inplied edges */
 372       int[] impliedEdgeList;
 373
 374       if (myId == 0) {
 375         impliedEdgeList = new int[computeGraphArgs.GPtr.numVertices * glb.MAX_CLUSTER_SIZE];
 376         global_impliedEdgeList = impliedEdgeList;
 377       }
 378
 379       Barrier.enterBarrier();
 380
 381       impliedEdgeList = global_impliedEdgeList;
 382
 383       CreatePartition.createPartition(0,
 384           (computeGraphArgs.GPtr.numVertices * glb.MAX_CLUSTER_SIZE),
 385           myId,
 386           numThread,
 387           lss);
 388
 389       for (int i = lss.i_start; i < lss.i_stop; i++) {
 390         impliedEdgeList[i] = 0;
 391       }
 392
 393       /*
 394        * An auxiliary array to store implied edges, in case we overshoot
 395        * MAX_CLUSTER_SIZE
 396        */
 397
 398       int[][] auxArr;
 399       if (myId == 0) {
 400         auxArr = new int[computeGraphArgs.GPtr.numVertices][glb.MAX_CLUSTER_SIZE];
 401         global_auxArr = auxArr;
 402       }
 403
 404       Barrier.enterBarrier();
 405
 406       auxArr = global_auxArr;
 407
 408       CreatePartition.createPartition(0, computeGraphArgs.GPtr.numVertices, myId, numThread, lss);
 409
 410       for (int i = lss.i_start; i < lss.i_stop; i++) {
 411         /* Inspect adjacency list of vertex i */
 412         for (j = computeGraphArgs.GPtr.outVertexIndex[i];
 413             j < (computeGraphArgs.GPtr.outVertexIndex[i] + computeGraphArgs.GPtr.outDegree[i]);
 414             j++)
 415         {
 416           int v =  (computeGraphArgs.GPtr.outVertexList[j]);
 417           int k;
 418           for (k = computeGraphArgs.GPtr.outVertexIndex[v];
 419               k < (computeGraphArgs.GPtr.outVertexIndex[v] + computeGraphArgs.GPtr.outDegree[v]);
 420               k++)
 421           {
 422             if (computeGraphArgs.GPtr.outVertexList[k] == i) {
 423               break;
 424             }
 425           }
 426           if (k == computeGraphArgs.GPtr.outVertexIndex[v]+computeGraphArgs.GPtr.outDegree[v]) {
 427             atomic {
 428               /* Add i to the impliedEdgeList of v */
 429               int inDegree = computeGraphArgs.GPtr.inDegree[v];
 430               computeGraphArgs.GPtr.inDegree[v] =  (inDegree + 1);
 431               if ( inDegree < glb.MAX_CLUSTER_SIZE) {
 432                 impliedEdgeList[v*glb.MAX_CLUSTER_SIZE+inDegree] = i
 433               } else {
 434                 /* Use auxiliary array to store the implied edge */
 435                 /* Create an array if it's not present already */
 436                 int[] a = null;
 437                 if ((inDegree % glb.MAX_CLUSTER_SIZE) == 0) {
 438                   a = new int[glb.MAX_CLUSTER_SIZE];
 439                   auxArr[v] = a;
 440                 } else {
 441                   a = auxArr[v];
 442                 }
 443                 a[inDegree % MAX_CLUSTER_SIZE] = i;
 444               }
 445             }
 446           }
 447         }
 448       } /* for i */
 449
 450       Barrier.enterBarrier();
 451
 452       prefix_sums(myId, numThread, computeGraphArgs.GPtr.inVertexIndex, computeGraphArgs.GPtr.inDegree, computeGraphArgs.GPtr.numVertices);
 453
 454       if (myId == 0) {
 455         computeGraphArgs.GPtr.numUndirectedEdges = computeGraphArgs.GPtr.inVertexIndex[computeGraphArgs.GPtr.numVertices-1]
 456           + computeGraphArgs.GPtr.inDegree[computeGraphArgs.GPtr.numVertices-1];
 457         computeGraphArgs.GPtr.inVertexList = new int[computeGraphArgs.GPtr.numUndirectedEdges];
 458       }
 459
 460       Barrier.enterBarrier();
 461
 462       /*
 463        * Create the inVertex List
 464        */
 465
 466       for (int i = lss.i_start; i < lss.i_stop; i++) {
 467         for (int j = computeGraphArgs.GPtr.inVertexIndex[i];
 468             j < (computeGraphArgs.GPtr.inVertexIndex[i] + computeGraphArgs.GPtr.inDegree[i]);
 469             j++)
 470         {
 471           if ((j - computeGraphArgs.GPtr.inVertexIndex[i]) < glb.MAX_CLUSTER_SIZE) {
 472             computeGraphArgs.GPtr.inVertexList[j] =
 473               impliedEdgeList[i*glb.MAX_CLUSTER_SIZE+j-computeGraphArgs.GPtr.inVertexIndex[i]];
 474           } else {
 475             computeGraphArgs.GPtr.inVertexList[j] =
 476               auxArr[i][(j-computeGraphArgs.GPtr.inVertexIndex[i]) % glb.MAX_CLUSTER_SIZE];
 477           }
 478         }
 479       }
 480
 481       Barrier.enterBarrier();
 482
 483       if (myId == 0) {
 484         impliedEdgeList = null;
 485       }
 486
 487       for (i = i_start; i < i_stop; i++) {
 488         if (computeGraphArgs.GPtr.inDegree[i] > MAX_CLUSTER_SIZE) {
 489           auxArr[i] = null;
 490         }
 491       }
 492
 493       Barrier.enterBarrier();
 494
 495       if (myId == 0) {
 496         auxArr = null
 497       }
 498
 499     }
 500 }
 501
 502 /* =============================================================================
 503  *
 504  * End of computeGraph.java
 505  *
 506  * =============================================================================
 507  */