From d3c0cee296c6c1588a8fb43dd4ed3f1d64bc34c4 Mon Sep 17 00:00:00 2001 From: adash Date: Thu, 21 May 2009 23:43:44 +0000 Subject: [PATCH] Working version of SSCA2 benchmark for kernel 1 -singleTM flag problems for more than 1 thread still exists, some problem in TRANSREAD, Amem_cpy() --- Robust/src/Benchmarks/SingleTM/KMeans/README | 4 +- .../SingleTM/SSCA2/Alg_Radix_Smp.java | 102 +++-- .../SingleTM/SSCA2/ComputeGraph.java | 40 +- .../SingleTM/SSCA2/CreatePartition.java | 5 +- .../SingleTM/SSCA2/FindSubGraphs0_arg_t.java | 13 + .../SingleTM/SSCA2/GenScalData.java | 155 ++++--- .../SingleTM/SSCA2/GetUserParameters.java | 58 ++- .../Benchmarks/SingleTM/SSCA2/Globals.java | 1 - .../src/Benchmarks/SingleTM/SSCA2/Graph.java | 6 +- .../SingleTM/SSCA2/LocalStartStop.java | 9 +- Robust/src/Benchmarks/SingleTM/SSCA2/README | 14 +- .../src/Benchmarks/SingleTM/SSCA2/SSCA2.java | 385 ++++++++++++++++++ .../src/Benchmarks/SingleTM/SSCA2/VList.java | 5 +- .../Benchmarks/SingleTM/common/Random.java | 92 +++++ Robust/src/ClassLibrary/Integer.java | 4 + Robust/src/IR/Flat/BuildCode.java | 6 +- 16 files changed, 709 insertions(+), 190 deletions(-) create mode 100644 Robust/src/Benchmarks/SingleTM/SSCA2/FindSubGraphs0_arg_t.java create mode 100644 Robust/src/Benchmarks/SingleTM/SSCA2/SSCA2.java create mode 100644 Robust/src/Benchmarks/SingleTM/common/Random.java diff --git a/Robust/src/Benchmarks/SingleTM/KMeans/README b/Robust/src/Benchmarks/SingleTM/KMeans/README index 7b051e2f..b25fc24d 100644 --- a/Robust/src/Benchmarks/SingleTM/KMeans/README +++ b/Robust/src/Benchmarks/SingleTM/KMeans/README @@ -26,10 +26,10 @@ To build the application, simply run: make -By default, this produces an executable named "kmeans", which can then be +By default, this produces an executable named "KMeans.bin", which can then be run in the following manner: - ./kmeans -m \ + ./KMeans.bin -m \ -n \ -t \ -i \ diff --git a/Robust/src/Benchmarks/SingleTM/SSCA2/Alg_Radix_Smp.java b/Robust/src/Benchmarks/SingleTM/SSCA2/Alg_Radix_Smp.java index 2e21f242..cd48fba1 100644 --- a/Robust/src/Benchmarks/SingleTM/SSCA2/Alg_Radix_Smp.java +++ b/Robust/src/Benchmarks/SingleTM/SSCA2/Alg_Radix_Smp.java @@ -45,23 +45,19 @@ */ public class Alg_Radix_Smp { - int[] global_myHisto; - int[] global_psHisto; - int[] global_lTemp; - int[] global_lTemp2; - int myId; - int numThread; - - public class Alg_Radix_Smp(int myId, int numThread) { + public int[] global_myHisto; + public int[] global_psHisto; + public int[] global_lTemp; + public int[] global_lTemp2; + + public Alg_Radix_Smp() { global_myHisto = null; global_psHisto = null; global_lTemp = null; global_lTemp2 = null; - this.myId = myId; - this.numThread = numThread; } - public int BITS(x, k, j) { + public int BITS(int x, int k, int j) { int retval = ((x>>k) & ~(~0< 0) { int add_value = p[NOSHARE(myId-1)]; - for (j = start-1; j < end; j++) { + for (int j = start-1; j < end; j++) { result[j] += add_value; } } @@ -138,7 +138,7 @@ public class ComputeGraph { //Graph GPtr = computeGraphArgs.GPtr; //GraphSDG SDGdataPtr = computeGraphArgs.SDGdata; - int j; + //int j; int maxNumVertices = 0; int numEdgesPlaced = computeGraphArgs.SDGdataPtr.numEdgesPlaced; @@ -156,14 +156,14 @@ public class ComputeGraph { } atomic { - int tmp_maxNumVertices = global_maxNumVertices; + int tmp_maxNumVertices = computeGraphArgs.global_maxNumVertices; int new_maxNumVertices = CreatePartition.MAX( tmp_maxNumVertices, maxNumVertices) + 1; - global_maxNumVertices = new_maxNumVertices; + computeGraphArgs.global_maxNumVertices = new_maxNumVertices; } Barrier.enterBarrier(); - maxNumVertices = global_maxNumVertices; + maxNumVertices = computeGraphArgs.global_maxNumVertices; if (myId == 0) { @@ -189,7 +189,7 @@ public class ComputeGraph { CreatePartition.createPartition(0, computeGraphArgs.GPtr.numVertices, myId, numThread, lss); - for (i = lss.i_start; i < lss.i_stop; i++) { + for (int i = lss.i_start; i < lss.i_stop; i++) { computeGraphArgs.GPtr.outDegree[i] = 0; computeGraphArgs.GPtr.outVertexIndex[i] = 0; } @@ -260,17 +260,17 @@ public class ComputeGraph { Barrier.enterBarrier(); - prefix_sums(myId, numThread, computeGraphArgs.GPtr.outVertexIndex, computeGraphArgs.GPtr.outDegree, computeGraphArgs.GPtr.numVertices); + computeGraphArgs.prefix_sums(myId, numThread, computeGraphArgs.GPtr.outVertexIndex, computeGraphArgs.GPtr.outDegree, computeGraphArgs.GPtr.numVertices); Barrier.enterBarrier(); atomic { - global_outVertexListSize = global_outVertexListSize + outVertexListSize; + computeGraphArgs.global_outVertexListSize = computeGraphArgs.global_outVertexListSize + outVertexListSize; } Barrier.enterBarrier(); - outVertexListSize = global_outVertexListSize; + outVertexListSize = computeGraphArgs.global_outVertexListSize; if (myId == 0) { computeGraphArgs.GPtr.numDirectedEdges = outVertexListSize; @@ -373,12 +373,12 @@ public class ComputeGraph { if (myId == 0) { impliedEdgeList = new int[computeGraphArgs.GPtr.numVertices * glb.MAX_CLUSTER_SIZE]; - global_impliedEdgeList = impliedEdgeList; + computeGraphArgs.global_impliedEdgeList = impliedEdgeList; } Barrier.enterBarrier(); - impliedEdgeList = global_impliedEdgeList; + impliedEdgeList = computeGraphArgs.global_impliedEdgeList; CreatePartition.createPartition(0, (computeGraphArgs.GPtr.numVertices * glb.MAX_CLUSTER_SIZE), @@ -398,18 +398,18 @@ public class ComputeGraph { int[][] auxArr; if (myId == 0) { auxArr = new int[computeGraphArgs.GPtr.numVertices][glb.MAX_CLUSTER_SIZE]; - global_auxArr = auxArr; + computeGraphArgs.global_auxArr = auxArr; } Barrier.enterBarrier(); - auxArr = global_auxArr; + auxArr = computeGraphArgs.global_auxArr; CreatePartition.createPartition(0, computeGraphArgs.GPtr.numVertices, myId, numThread, lss); for (int i = lss.i_start; i < lss.i_stop; i++) { /* Inspect adjacency list of vertex i */ - for (j = computeGraphArgs.GPtr.outVertexIndex[i]; + for (int j = computeGraphArgs.GPtr.outVertexIndex[i]; j < (computeGraphArgs.GPtr.outVertexIndex[i] + computeGraphArgs.GPtr.outDegree[i]); j++) { @@ -429,7 +429,7 @@ public class ComputeGraph { int inDegree = computeGraphArgs.GPtr.inDegree[v]; computeGraphArgs.GPtr.inDegree[v] = (inDegree + 1); if ( inDegree < glb.MAX_CLUSTER_SIZE) { - impliedEdgeList[v*glb.MAX_CLUSTER_SIZE+inDegree] = i + impliedEdgeList[v*glb.MAX_CLUSTER_SIZE+inDegree] = i; } else { /* Use auxiliary array to store the implied edge */ /* Create an array if it's not present already */ @@ -440,7 +440,7 @@ public class ComputeGraph { } else { a = auxArr[v]; } - a[inDegree % MAX_CLUSTER_SIZE] = i; + a[inDegree % glb.MAX_CLUSTER_SIZE] = i; } } } @@ -449,7 +449,7 @@ public class ComputeGraph { Barrier.enterBarrier(); - prefix_sums(myId, numThread, computeGraphArgs.GPtr.inVertexIndex, computeGraphArgs.GPtr.inDegree, computeGraphArgs.GPtr.numVertices); + computeGraphArgs.prefix_sums(myId, numThread, computeGraphArgs.GPtr.inVertexIndex, computeGraphArgs.GPtr.inDegree, computeGraphArgs.GPtr.numVertices); if (myId == 0) { computeGraphArgs.GPtr.numUndirectedEdges = computeGraphArgs.GPtr.inVertexIndex[computeGraphArgs.GPtr.numVertices-1] @@ -484,8 +484,8 @@ public class ComputeGraph { impliedEdgeList = null; } - for (i = i_start; i < i_stop; i++) { - if (computeGraphArgs.GPtr.inDegree[i] > MAX_CLUSTER_SIZE) { + for (int i = lss.i_start; i < lss.i_stop; i++) { + if (computeGraphArgs.GPtr.inDegree[i] > glb.MAX_CLUSTER_SIZE) { auxArr[i] = null; } } @@ -493,7 +493,7 @@ public class ComputeGraph { Barrier.enterBarrier(); if (myId == 0) { - auxArr = null + auxArr = null; } } diff --git a/Robust/src/Benchmarks/SingleTM/SSCA2/CreatePartition.java b/Robust/src/Benchmarks/SingleTM/SSCA2/CreatePartition.java index f83f9d56..bc7a6b93 100644 --- a/Robust/src/Benchmarks/SingleTM/SSCA2/CreatePartition.java +++ b/Robust/src/Benchmarks/SingleTM/SSCA2/CreatePartition.java @@ -54,6 +54,7 @@ public class CreatePartition { public static void createPartition (int min, int max, int id, int n, LocalStartStop lss) { + //System.out.println("Inside createPartition() \n"); int range = max - min; int chunk = MAX(1, ((range + n/2) / n)); /* rounded */ int start = min + chunk * id; @@ -64,8 +65,8 @@ public class CreatePartition { stop = MIN(max, (start + chunk)); } - lss.start = start; - lss.stop = stop; + lss.i_start = start; + lss.i_stop = stop; } public static int MAX(int a, int b) { diff --git a/Robust/src/Benchmarks/SingleTM/SSCA2/FindSubGraphs0_arg_t.java b/Robust/src/Benchmarks/SingleTM/SSCA2/FindSubGraphs0_arg_t.java new file mode 100644 index 00000000..17339052 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/SSCA2/FindSubGraphs0_arg_t.java @@ -0,0 +1,13 @@ +public class FindSubGraphs0_arg_t { + Graph GPtr; + VList intWtVList; + VList strWtVList; + Edge maxIntWtList; + int maxIntWtListSize; + Edge soughtStrWtList; + int soughtStrWtListSize; + + public FindSubGraphs0_arg_t() { + + } +} diff --git a/Robust/src/Benchmarks/SingleTM/SSCA2/GenScalData.java b/Robust/src/Benchmarks/SingleTM/SSCA2/GenScalData.java index 0f98b576..15a3f1bf 100644 --- a/Robust/src/Benchmarks/SingleTM/SSCA2/GenScalData.java +++ b/Robust/src/Benchmarks/SingleTM/SSCA2/GenScalData.java @@ -63,7 +63,7 @@ public class GenScalData { * Constructor **/ public GenScalData() { - global_permV; = null; + global_permV = null; global_cliqueSizes = null; global_totCliques = 0; global_firstVsInCliques = null; @@ -98,30 +98,30 @@ public class GenScalData { */ public static void - genScalData (int myId, int numThread, Globals glb, GraphSDG SDGdataPtr) + genScalData (int myId, int numThread, Globals glb, GraphSDG SDGdataPtr, GenScalData gsd, Alg_Radix_Smp radixsort) { /* * STEP 0: Create the permutations required to randomize the vertices */ Random randomPtr = new Random(); - randomPtr = randomPtr.random_alloc(); + randomPtr.random_alloc(); randomPtr.random_seed(myId); int[] permV; if (myId == 0) { permV = new int[glb.TOT_VERTICES]; - global_permV = permV; + gsd.global_permV = permV; } Barrier.enterBarrier(); - permV = global_permV; + permV = gsd.global_permV; LocalStartStop lss = new LocalStartStop(); - CreatePartition cp = new CreatePartition(); - cp.createPartition(0, glb.TOT_VERTICES, myId, numThread, lss); + //CreatePartition cp = new CreatePartition(); + CreatePartition.createPartition(0, glb.TOT_VERTICES, myId, numThread, lss); /* Initialize the array */ for (int i = lss.i_start; i < lss.i_stop; i++) { @@ -130,8 +130,10 @@ public class GenScalData { Barrier.enterBarrier(); - for (int i = i_start; i < i_stop; i++) { - int t1 = randomPtr.random_generate(); + for (int i = lss.i_start; i < lss.i_stop; i++) { + int t1 = (int) (randomPtr.random_generate()); + if(t1 < 0) + t1*=(-1); int t = i + t1 % (glb.TOT_VERTICES - i); if (t != i) { atomic { @@ -148,7 +150,7 @@ public class GenScalData { int[] cliqueSizes; - int estTotCliques = (int)(Math.ceil(1.5d * glb.TOT_VERTICES / ((1+glb.MAX_CLIQUE_SIZE)/2))); + int estTotCliques = (int)(Math.ceil(1.5 * glb.TOT_VERTICES / ((1+glb.MAX_CLIQUE_SIZE)/2))); /* * Allocate mem for Clique array @@ -156,18 +158,20 @@ public class GenScalData { */ if (myId == 0) { cliqueSizes = new int[estTotCliques]; - global_cliqueSizes = cliqueSizes; + gsd.global_cliqueSizes = cliqueSizes; } Barrier.enterBarrier(); - cliqueSizes = global_cliqueSizes; + cliqueSizes = gsd.global_cliqueSizes; - cp.createPartition(0, estTotCliques, myId, numThread, lss); + CreatePartition.createPartition(0, estTotCliques, myId, numThread, lss); /* Generate random clique sizes. */ for (int i = lss.i_start; i < lss.i_stop; i++) { - cliqueSizes[i] = 1 + (randomPtr.random_generate() % glb.MAX_CLIQUE_SIZE); + cliqueSizes[i] = (int) ( 1 + (randomPtr.random_generate() % glb.MAX_CLIQUE_SIZE)); + if(cliqueSizes[i] < 0) + cliqueSizes[i] *= -1; //TODO fix the long->int casting error that creates negative numbers for randomPtr } Barrier.enterBarrier(); @@ -178,14 +182,14 @@ public class GenScalData { * Allocate memory for cliqueList */ - int[] firstVsInCliques; + int[] lastVsInCliques; int[] firstVsInCliques; if (myId == 0) { lastVsInCliques = new int[estTotCliques]; - global_lastVsInCliques = lastVsInCliques; + gsd.global_lastVsInCliques = lastVsInCliques; firstVsInCliques = new int[estTotCliques]; - global_firstVsInCliques = firstVsInCliques; + gsd.global_firstVsInCliques = firstVsInCliques; /* * Sum up vertices in each clique to determine the lastVsInCliques array @@ -201,7 +205,7 @@ public class GenScalData { } totCliques = i + 1; - global_totCliques = totCliques; + gsd.global_totCliques = totCliques; /* * Fix the size of the last clique @@ -216,13 +220,13 @@ public class GenScalData { Barrier.enterBarrier(); - lastVsInCliques = global_lastVsInCliques; - firstVsInCliques = global_firstVsInCliques; - totCliques = global_totCliques; + lastVsInCliques = gsd.global_lastVsInCliques; + firstVsInCliques = gsd.global_firstVsInCliques; + totCliques = gsd.global_totCliques; /* Compute start Vertices in cliques. */ - cp.createPartition(1, totCliques, myId, numThread, lss); - for (int i = i_start; i < i_stop; i++) { + CreatePartition.createPartition(1, totCliques, myId, numThread, lss); + for (int i = lss.i_start; i < lss.i_stop; i++) { firstVsInCliques[i] = lastVsInCliques[i-1] + 1; } @@ -279,7 +283,7 @@ Barrier.enterBarrier(); int[] endV; if (numThread > 3) { - int numByte = 1.5 * (estTotEdges/numThread); + int numByte = (int) (1.5 * (estTotEdges/numThread)); startV = new int[numByte]; endV = new int[numByte]; } else { @@ -297,10 +301,10 @@ Barrier.enterBarrier(); * Create edges in parallel */ //int i_clique; - cp.createPartition(0, totCliques, myId, numThread, lss); + CreatePartition.createPartition(0, totCliques, myId, numThread, lss); for (int i_clique = lss.i_start; i_clique < lss.i_stop; i_clique++) { - + /* * Get current clique parameters */ @@ -349,11 +353,17 @@ Barrier.enterBarrier(); } /* for i */ if (i_cliqueSize != 1) { - int randNumEdges = randomPtr.random_generate() % (2*i_cliqueSize*glb.MAX_PARAL_EDGES); + int randNumEdges = (int) (randomPtr.random_generate() % (2*i_cliqueSize*glb.MAX_PARAL_EDGES)); + if(randNumEdges < 0) + randNumEdges *= -1; //TODO fix the long->int casting error that creates negative numbers for randomPtr //int i_paralEdge; for (int i_paralEdge = 0; i_paralEdge < randNumEdges; i_paralEdge++) { int i = (int) (randomPtr.random_generate() % i_cliqueSize); + if(i < 0) + i *= -1; //TODO fix the long->int casting error that creates negative numbers for randomPtr int j = (int) (randomPtr.random_generate() % i_cliqueSize); + if(j < 0) + j *= -1; //TODO fix the long->int casting error that creates negative numbers for randomPtr if ((i != j) && (tmpEdgeCounter[i][j] < glb.MAX_PARAL_EDGES)) { float r = (float)(randomPtr.random_generate() % 1000) / (float)1000; if (r >= p) { @@ -379,16 +389,16 @@ Barrier.enterBarrier(); int[] i_edgeEndCounter; if (myId == 0) { - i_edgeStartCounter = new int[ numThread]; - global_i_edgeStartCounter = i_edgeStartCounter; + i_edgeStartCounter = new int[numThread]; + gsd.global_i_edgeStartCounter = i_edgeStartCounter; i_edgeEndCounter = new int[numThread]; - global_i_edgeEndCounter = i_edgeEndCounter; + gsd.global_i_edgeEndCounter = i_edgeEndCounter; } Barrier.enterBarrier(); - i_edgeStartCounter = global_i_edgeStartCounter; - i_edgeEndCounter = global_i_edgeEndCounter; + i_edgeStartCounter = gsd.global_i_edgeStartCounter; + i_edgeEndCounter = gsd.global_i_edgeEndCounter; i_edgeEndCounter[myId] = i_edgePtr; i_edgeStartCounter[myId] = 0; @@ -403,12 +413,12 @@ Barrier.enterBarrier(); } atomic { - global_edgeNum = global_edgeNum + i_edgePtr; + gsd.global_edgeNum = gsd.global_edgeNum + i_edgePtr; } Barrier.enterBarrier(); - int edgeNum = global_edgeNum; + int edgeNum = gsd.global_edgeNum; /* * Initialize edge list arrays @@ -427,14 +437,14 @@ Barrier.enterBarrier(); startVertex = new int[numByte]; endVertex = new int[numByte]; } - global_startVertex = startVertex; - global_endVertex = endVertex; + gsd.global_startVertex = startVertex; + gsd.global_endVertex = endVertex; } Barrier.enterBarrier(); - startVertex = global_startVertex; - endVertex = global_endVertex; + startVertex = gsd.global_startVertex; + endVertex = gsd.global_endVertex; for (int i = i_edgeStartCounter[myId]; i < i_edgeEndCounter[myId]; i++) { startVertex[i] = startV[i-i_edgeStartCounter[myId]]; @@ -450,13 +460,13 @@ Barrier.enterBarrier(); */ i_edgePtr = 0; - p = PROB_INTERCL_EDGES; + p = glb.PROB_INTERCL_EDGES; /* * Generating inter-clique edges as given in the specs */ - cp.createPartition(0, glb.TOT_VERTICES, myId, numThread, lss); + CreatePartition.createPartition(0, glb.TOT_VERTICES, myId, numThread, lss); for (int i = lss.i_start; i < lss.i_stop; i++) { int tempVertex1 = i; @@ -492,7 +502,8 @@ Barrier.enterBarrier(); int t1 = firstVsInCliques[t]; //int d; - for (int d = 1, p = glb.PROB_INTERCL_EDGES; d < glb.TOT_VERTICES; d *= 2, p /= 2) { + p = glb.PROB_INTERCL_EDGES; + for (int d = 1; d < glb.TOT_VERTICES; d *= 2, p /= 2) { float r = (float)(randomPtr.random_generate() % 1000) / (float)1000; @@ -504,7 +515,7 @@ Barrier.enterBarrier(); l = 0; t = -1; while (h - l > 1) { - int m = (((h + l) / 2); + int m = (h + l) / 2; if (tempVertex2 >= firstVsInCliques[m]) { l = m; } else { @@ -534,7 +545,9 @@ Barrier.enterBarrier(); if (t1 != t2) { int randNumEdges = - randomPtr.random_generate() % glb.MAX_PARAL_EDGES + 1; + (int) (randomPtr.random_generate() % glb.MAX_PARAL_EDGES + 1); + if(randNumEdges < 0) + randNumEdges *= -1; //TODO fix the long->int casting error that creates negative numbers for randomPtr //int j; for (int j = 0; j < randNumEdges; j++) { startV[i_edgePtr] = tempVertex1; @@ -583,7 +596,9 @@ Barrier.enterBarrier(); if (t1 != t2) { int randNumEdges = - randomPtr.random_generate() % glb.MAX_PARAL_EDGES + 1; + (int) (randomPtr.random_generate() % glb.MAX_PARAL_EDGES + 1); + if(randNumEdges < 0) + randNumEdges *= -1; //TODO fix the long->int casting error that creates negative numbers for randomPtr for (int j = 0; j < randNumEdges; j++) { startV[i_edgePtr] = tempVertex1; endV[i_edgePtr] = tempVertex2; @@ -602,7 +617,7 @@ Barrier.enterBarrier(); i_edgeStartCounter[myId] = 0; if (myId == 0) { - global_edgeNum = 0; + gsd.global_edgeNum = 0; } Barrier.enterBarrier(); @@ -615,15 +630,15 @@ Barrier.enterBarrier(); } atomic { - global_edgeNum = global_edgeNum + i_edgePtr; + gsd.global_edgeNum = gsd.global_edgeNum + i_edgePtr; } Barrier.enterBarrier(); - edgeNum = global_edgeNum; - int numEdgesPlacedOutside = global_edgeNum; + edgeNum = gsd.global_edgeNum; + int numEdgesPlacedOutside = gsd.global_edgeNum; - for (int i = (i_edgeStartCounter[myId]; i < i_edgeEndCounter[myId]; i++) { + for (int i = i_edgeStartCounter[myId]; i < i_edgeEndCounter[myId]; i++) { startVertex[i+numEdgesPlacedInCliques] = startV[i-i_edgeStartCounter[myId]]; endVertex[i+numEdgesPlacedInCliques] = endV[i-i_edgeStartCounter[myId]]; } @@ -656,13 +671,15 @@ Barrier.enterBarrier(); p = glb.PERC_INT_WEIGHTS; int numStrWtEdges = 0; - cp.createPartition(0, numEdgesPlaced, myId, numThread, lss); + CreatePartition.createPartition(0, numEdgesPlaced, myId, numThread, lss); for (int i = lss.i_start; i < lss.i_stop; i++) { float r = (float)(randomPtr.random_generate() % 1000) / (float)1000; if (r <= p) { SDGdataPtr.intWeight[i] = - 1 + (randomPtr.random_generate() % (MAX_INT_WEIGHT-1)); + (int) (1 + (randomPtr.random_generate() % (glb.MAX_INT_WEIGHT-1))); + if(SDGdataPtr.intWeight[i] < 0) + SDGdataPtr.intWeight[i] *= -1; //TODO fix the long->int casting error that creates negative numbers for randomPtr } else { SDGdataPtr.intWeight[i] = -1; numStrWtEdges++; @@ -682,12 +699,12 @@ Barrier.enterBarrier(); } atomic { - global_numStrWtEdges = global_numStrWtEdges + numStrWtEdges; + gsd.global_numStrWtEdges = gsd.global_numStrWtEdges + numStrWtEdges; } Barrier.enterBarrier(); - numStrWtEdges = global_numStrWtEdges; + numStrWtEdges = gsd.global_numStrWtEdges; if (myId == 0) { SDGdataPtr.strWeight = new char[numStrWtEdges * glb.MAX_STRLEN]; @@ -695,7 +712,7 @@ Barrier.enterBarrier(); Barrier.enterBarrier(); - cp.createPartition(0, numEdgesPlaced, myId, numThread, lss); + CreatePartition.createPartition(0, numEdgesPlaced, myId, numThread, lss); for (int i = lss.i_start; i < lss.i_stop; i++) { if (SDGdataPtr.intWeight[i] <= 0) { @@ -714,15 +731,18 @@ Barrier.enterBarrier(); if (myId == 0) { - if (SOUGHT_STRING.length != glb.MAX_STRLEN) { - glb.SOUGHT_STRING = new char[MAX_STRLEN]; + if (glb.SOUGHT_STRING.length != glb.MAX_STRLEN) { + glb.SOUGHT_STRING = new char[glb.MAX_STRLEN]; + //glb.SOUGHT_STRING = new String(MAX_STRLEN); } - int t = randomPtr.random_generate() % numStrWtEdges; + int t = (int) (randomPtr.random_generate() % numStrWtEdges); + if (t < 0) + t *= -1; //TODO fix the long->int casting error that creates negative numbers for randomPtr for (int j = 0; j < glb.MAX_STRLEN; j++) { //FIXME - SOUGHT_STRING[j] = - (char) (SDGdataPtr.strWeight[(t*glb.MAX_STRLEN+j)]); + glb.SOUGHT_STRING[j] = + SDGdataPtr.strWeight[(t*glb.MAX_STRLEN+j)]; } } @@ -734,8 +754,8 @@ Barrier.enterBarrier(); */ for (int i = lss.i_start; i < lss.i_stop; i++) { - startVertex[i] = permV[(startVertex[i])]; - endVertex[i] = permV[(endVertex[i])]; + startVertex[i] = permV[startVertex[i]]; + endVertex[i] = permV[endVertex[i]]; } Barrier.enterBarrier(); @@ -756,11 +776,16 @@ Barrier.enterBarrier(); Barrier.enterBarrier(); - Alg_Radix_Smp.all_radixsort_node_aux_s3(numEdgesPlaced, + //Alg_Radix_Smp radixsort = new Alg_Radix_Smp(myId, numThread); + //radixsort.all_radixsort_node_aux_s3(numEdgesPlaced, + Alg_Radix_Smp.all_radixsort_node_aux_s3(myId, + numThread, + numEdgesPlaced, startVertex, SDGdataPtr.startVertex, endVertex, - SDGdataPtr.endVertex); + SDGdataPtr.endVertex, + radixsort); Barrier.enterBarrier(); @@ -830,7 +855,7 @@ Barrier.enterBarrier(); if (myId == 0) { tempIndex = new int[glb.TOT_VERTICES + 1]; - global_tempIndex = tempIndex; + gsd.global_tempIndex = tempIndex; /* * Update degree of each vertex @@ -859,7 +884,7 @@ Barrier.enterBarrier(); Barrier.enterBarrier(); - tempIndex = global_tempIndex; + tempIndex = gsd.global_tempIndex; /* * Insertion sort for now, replace with something better later on diff --git a/Robust/src/Benchmarks/SingleTM/SSCA2/GetUserParameters.java b/Robust/src/Benchmarks/SingleTM/SSCA2/GetUserParameters.java index c74f3e48..8402cfd8 100644 --- a/Robust/src/Benchmarks/SingleTM/SSCA2/GetUserParameters.java +++ b/Robust/src/Benchmarks/SingleTM/SSCA2/GetUserParameters.java @@ -50,20 +50,16 @@ */ public class GetUserParameters { - Globals glb; - public GetUserParameters(Globals glb) { - this.glb = glb; - /* * Scalable Data Generator parameters - defaults */ glb.THREADS = 1; glb.SCALE = 20; /* binary scaling heuristic */ glb.MAX_PARAL_EDGES = 3; /* between vertices. */ - glb.PERC_INT_WEIGHTS = 0.6; /* % int (vs. string) edge weights */ - glb.PROB_UNIDIRECTIONAL = 0.1; - glb.PROB_INTERCL_EDGES = 0.5; /* Init probability link between cliques */ + glb.PERC_INT_WEIGHTS = (float) 0.6f; /* % int (vs. string) edge weights */ + glb.PROB_UNIDIRECTIONAL = (float) 0.1f; + glb.PROB_INTERCL_EDGES = (float) 0.5f; /* Init probability link between cliques */ glb.SUBGR_EDGE_LENGTH = 3; /* Kernel 3: max. path length, */ /* measured by num edges in subgraph */ @@ -76,24 +72,24 @@ public class GetUserParameters { glb.K3_DS = 2; /* 0 - Array */ /* 1 - Linked List */ /* 2 - Dynamic Array */ - } + /* ============================================================================= * displayUsage * ============================================================================= */ - static void + public static void displayUsage () { - System.out.println("Usage: ./SSCA.bin [options]\n"); - System.out.println(" i Probability [i]nter-clique (%f)\n", PROB_INTERCL_EDGES); - System.out.println(" k [k]ind: 0=array 1=list 2=vector (%li)\n", K3_DS); - System.out.println(" l Max path [l]ength (%li)\n", SUBGR_EDGE_LENGTH); - System.out.println(" p Max [p]arallel edges (%li)\n", MAX_PARAL_EDGES); - System.out.println(" s Problem [s]cale (%li)\n", SCALE); - System.out.println(" t Number of [t]hreads (%li)\n", THREADS); - System.out.println(" u Probability [u]nidirectional (%f)\n", PROB_UNIDIRECTIONAL); - System.out.println(" w Fraction integer [w]eights (%f)\n", PERC_INT_WEIGHTS); + System.out.println("Usage: ./SSCA.bin [options]"); + System.out.println(" i Probability [i]nter-clique "); + System.out.println(" k [k]ind: 0=array 1=list 2=vector "); + System.out.println(" l Max path [l]ength "); + System.out.println(" p Max [p]arallel edges "); + System.out.println(" s Problem [s]cale "); + System.out.println(" t Number of [t]hreads "); + System.out.println(" u Probability [u]nidirectional "); + System.out.println(" w Fraction integer [w]eights "); System.exit(-1); } @@ -102,8 +98,8 @@ public class GetUserParameters { * parseArgs * ============================================================================= */ - public static void - parseArgs(String[] args) + public void + parseArgs(String[] args, Globals glb) { int i = 0; String arg; @@ -112,13 +108,13 @@ public class GetUserParameters { //check options if(arg.equals("-i")) { if(i < args.length) { - glb.PROB_INTERCL_EDGES = new Integer(args[i++]).doubleValue(); + glb.PROB_INTERCL_EDGES = new Integer(args[i++]).floatValue(); } } else if(arg.equals("-k")) { if(i < args.length) { glb.K3_DS = new Integer(args[i++]).intValue(); } - if(!(glb.K3_DS >=0 && K3_DS <=2)) + if(!(glb.K3_DS >=0 && glb.K3_DS <=2)) System.out.println("Input a valid number for -k option between >=0 and <= 2"); } else if(arg.equals("-l")) { if(i < args.length) { @@ -138,11 +134,11 @@ public class GetUserParameters { } } else if(arg.equals("-u")) { if(i < args.length) { - glb.PROB_UNIDIRECTIONAL = new Integer(args[i++]).doubleValue(); + glb.PROB_UNIDIRECTIONAL = new Integer(args[i++]).floatValue(); } } else if(arg.equals("-w")) { if(i < args.length) { - glb.PERC_INT_WEIGHTS = new Integer(args[i++]).doubleValue(); + glb.PERC_INT_WEIGHTS = new Integer(args[i++]).floatValue(); } } else if(arg.equals("-h")) { displayUsage(); @@ -157,8 +153,8 @@ public class GetUserParameters { * getUserParameters * ============================================================================= */ - static void - getUserParameters (String[] argv) + public void + getUserParameters (String[] argv, Globals glb) { /* * Scalable Data Generator parameters - defaults @@ -167,9 +163,9 @@ public class GetUserParameters { glb.THREADS = 1; glb.SCALE = 20; /* binary scaling heuristic */ glb.MAX_PARAL_EDGES = 3; /* between vertices. */ - glb.PERC_INT_WEIGHTS = 0.6; /* % int (vs. string) edge weights */ - glb.PROB_UNIDIRECTIONAL = 0.1; - glb.PROB_INTERCL_EDGES = 0.5; /* Init probability link between cliques */ + glb.PERC_INT_WEIGHTS = (float)0.6; /* % int (vs. string) edge weights */ + glb.PROB_UNIDIRECTIONAL = (float)0.1; + glb.PROB_INTERCL_EDGES = (float)0.5; /* Init probability link between cliques */ glb.SUBGR_EDGE_LENGTH = 3; /* Kernel 3: max. path length, */ /* measured by num edges in subgraph */ @@ -184,7 +180,7 @@ public class GetUserParameters { /* 1 - Linked List */ /* 2 - Dynamic Array */ - parseArgs(argv); /* overrides default values set above */ + parseArgs(argv, glb); /* overrides default values set above */ glb.TOT_VERTICES = (1< + make -in the source directory. For example, for the sequential flavor, run: - - make -f Makefile.seq - -By default, this produces an executable named "yada", which can then be +By default, this produces an executable named "SSCA2.bin", which can then be run in the following manner: - ./ssca2 -i \ + ./SSCA2.bin -i \ -k \ -l \ -p \ @@ -45,11 +41,11 @@ run in the following manner: The following arguments are recommended for simulated runs: - -s13 -i1.0 -u1.0 -l3 -p3 + -s 13 -i 1.0 -u 1.0 -l 3 -p 3 -t 1 For non-simulator runs, a larger input can be used: - -s20 -i1.0 -u1.0 -l3 -p3 + -s 20 -i 1.0 -u 1.0 -l 3 -p 3 -t 1 References diff --git a/Robust/src/Benchmarks/SingleTM/SSCA2/SSCA2.java b/Robust/src/Benchmarks/SingleTM/SSCA2/SSCA2.java new file mode 100644 index 00000000..b8a20f12 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/SSCA2/SSCA2.java @@ -0,0 +1,385 @@ +/* ============================================================================= + * + * ssca2.java + * + * ============================================================================= + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford University nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + * + * ============================================================================= + */ + +public class SSCA2 extends Thread { + /* + * Tuple for Scalable Data Generation + * stores startVertex, endVertex, long weight and other info + */ + GraphSDG SDGdata; + + /** + * The graph data structure for this benchmark - see defs.h + **/ + Graph G; + + /** + * + */ + ComputeGraph computeGraphArgs; + + /** + * thread id + **/ + int threadid; + + /** + * Total number of threads + **/ + int numThread; + + /** + * Global Arguments + **/ + Globals glb; + + + /** + * Gen scalable data + **/ + GenScalData gsd; + + /** + ** + **/ + GetStartLists getStartListsArg; + + + Alg_Radix_Smp radixsort; + + public SSCA2(int myId, int numThread, Globals glb, ComputeGraph computeGraphArgs, + GenScalData gsd, GetStartLists getStartListsArg, Alg_Radix_Smp radixsort) { + this.threadid = myId; + this.numThread = numThread; + this.glb = glb; + this.computeGraphArgs = computeGraphArgs; + this.G = computeGraphArgs.GPtr; + this.SDGdata = computeGraphArgs.SDGdataPtr; + this.gsd = gsd; + this. getStartListsArg = getStartListsArg; + this.radixsort = radixsort; + } + + public void run() { + +#ifdef ENABLE_KERNEL1 + /* Generate Scaldata */ + Barrier.enterBarrier(); + GenScalData.genScalData(threadid, numThread, glb, SDGdata, gsd, radixsort); + Barrier.enterBarrier(); + + /* Kernel 1 */ + Barrier.enterBarrier(); + ComputeGraph.computeGraph(threadid, numThread, glb, computeGraphArgs); + Barrier.enterBarrier(); +#endif /* Enable Kernel1 */ + +#ifdef ENABLE_KERNEL2 + /* Kernel 2 */ + Barrier.enterBarrier(); + GetStartLists.getStartLists(threadid, numThread, glb, getStartListsArg); + Barrier.enterBarrier(); +#endif /* Enable Kernel2 */ + } + + /* ============================================================================= + * main + * ============================================================================= + */ + public static void main(String[] args) { + /* + * Tuple for Scalable Data Generation + * stores startVertex, endVertex, long weight and other info + */ + GraphSDG SDGdata = new GraphSDG(); + + /* + * The graph data structure for this benchmark - see defs.h + */ + Graph G = new Graph(); + + /* + * The Global arguments + */ + ComputeGraph computeGraphArgs = new ComputeGraph(); + + computeGraphArgs.GPtr = G; + computeGraphArgs.SDGdataPtr = SDGdata; + /* ------------------------------------------------------------------------- + * Preamble + * ------------------------------------------------------------------------- + */ + + /* + * User Interface: Configurable parameters, and global program control + */ + + System.out.println("\nHPCS SSCA #2 Graph Analysis Executable Specification:"); + System.out.println("\nRunning...\n\n"); + + Globals glb = new Globals(); + + GetUserParameters gup = new GetUserParameters(glb); + gup.getUserParameters(args, glb); + + System.out.println("Number of processors: " + glb.THREADS); + System.out.println("Problem Scale: " + glb.SCALE); + System.out.println("Max parallel edges: " + glb.MAX_PARAL_EDGES); + System.out.println("Percent int weights: " + glb.PERC_INT_WEIGHTS); + System.out.println("Probability unidirectional: " + glb.PROB_UNIDIRECTIONAL); + System.out.println("Probability inter-clique: " + glb.PROB_INTERCL_EDGES); + System.out.println("Subgraph edge length: " + glb.SUBGR_EDGE_LENGTH); + System.out.println("Kernel 3 data structure: " + glb.K3_DS); + + /* Initiate Barriers */ + Barrier.setBarrier(glb.THREADS); + + SSCA2[] ssca = new SSCA2[glb.THREADS]; + int nthreads = glb.THREADS; + + GenScalData gsd = new GenScalData(); + + Alg_Radix_Smp radixsort = new Alg_Radix_Smp(); + + GetStartLists getStartListsArg = new GetStartLists(); + getStartListsArg.GPtr = G; + + /* Create and Start Threads */ + for(int i = 1; i> 30)) + mti); + /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ + /* In the previous versions, MSBs of the seed affect */ + /* only MSBs of the array mt[]. */ + /* 2002/01/09 modified by Makoto Matsumoto */ + mt[mti] &= 0xFFFFFFFFL; + /* for >32 bit machines */ + } + this.mti=mti; + } + + public void random_seed(long seed) { + init_genrand(seed); + } + + public long random_generate() { + return genrand_int32(); + } + + public long genrand_int32() { + long y; + long[] mag01= new long[2]; + mag01[0] = 0x0L; + mag01[1] = MATRIX_A; + int mti = this.mti; + + /* mag01[x] = x * MATRIX_A for x=0,1 */ + + if (mti >= N) { /* generate N words at one time */ + int kk; + + if (mti == N+1) /* if init_genrand() has not been called, */ + init_genrand(5489L); /* a default initial seed is used */ + + for (kk=0;kk> 1) ^ mag01[(int)(y & 0x1L)]; + } + for (;kk> 1) ^ mag01[(int)(y & 0x1L)]; + } + y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK); + mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[(int)(y & 0x1L)]; + + mti = 0; + } + + y = mt[mti++]; + + /* Tempering */ + y ^= (y >> 11); + y ^= (y << 7) & 0x9d2c5680L; + y ^= (y << 15) & 0xefc60000L; + y ^= (y >> 18); + + this.mti = mti; + + return y; + } +} diff --git a/Robust/src/ClassLibrary/Integer.java b/Robust/src/ClassLibrary/Integer.java index 7bb38585..39f76d25 100644 --- a/Robust/src/ClassLibrary/Integer.java +++ b/Robust/src/ClassLibrary/Integer.java @@ -17,6 +17,10 @@ public class Integer { return (double)value; } + public float floatValue() { + return (float)value; + } + public byte[] intToByteArray() { byte[] b = new byte[4]; for (int i = 0; i < 4; i++) { diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index 8cced846..fab702ae 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -1653,7 +1653,7 @@ public class BuildCode { FlatSESEExitNode stop, PrintWriter output) { - System.out.println( "generating code, stop="+stop ); + //System.out.println( "generating code, stop="+stop ); /* Assign labels to FlatNode's if necessary.*/ Hashtable nodetolabel=assignLabels(first, stop); @@ -1673,7 +1673,7 @@ public class BuildCode { visited.add(current_node); if (nodetolabel.containsKey(current_node)) { - System.out.println( " *"+current_node+" preceeded with label "+nodetolabel.get(current_node) ); + //System.out.println( " *"+current_node+" preceeded with label "+nodetolabel.get(current_node) ); output.println("L"+nodetolabel.get(current_node)+":"); } @@ -1762,9 +1762,11 @@ public class BuildCode { } + /* if( nodetolabel.get(nn) != null ) { System.out.println( " "+nn+" has label "+nodetolabel.get(nn) ); } + */ } } -- 2.34.1