From e58fa6a9e80fa733682045ad96a18813d9a10cf8 Mon Sep 17 00:00:00 2001 From: afedward Date: Fri, 15 May 2009 22:15:47 +0000 Subject: [PATCH] Checking in changes. Genome still not functional, but getting close. SingleTM error is revealed in Sequencer.java. Sequencer.run() function reveals transactional errors in atomic blocks, especially as it applies to lines 251-271. --- .../SingleTM/genome/java/Bitmap.java | 49 +- .../SingleTM/genome/java/Bitmap.java~ | 49 +- .../Benchmarks/SingleTM/genome/java/Gene.java | 29 +- .../SingleTM/genome/java/Gene.java~ | 30 +- .../SingleTM/genome/java/Genome.java | 213 ++++--- .../SingleTM/genome/java/Genome.java~ | 214 ++++--- .../SingleTM/genome/java/Segments.java | 40 +- .../SingleTM/genome/java/Segments.java~ | 41 +- .../SingleTM/genome/java/Sequencer.java | 533 ++++++++++-------- .../SingleTM/genome/java/Sequencer.java~ | 528 +++++++++-------- .../SingleTM/genome/java/Table.java | 33 +- .../SingleTM/genome/java/Table.java~ | 33 +- 12 files changed, 1027 insertions(+), 765 deletions(-) diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Bitmap.java b/Robust/src/Benchmarks/SingleTM/genome/java/Bitmap.java index 0e437075..20c639c7 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Bitmap.java +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Bitmap.java @@ -3,8 +3,8 @@ public class Bitmap { public long numWord; public long bits[]; - private static NUM_BIT_PER_BYTE = 8; - private static NUM_BIT_PER_WORD = (8) * NUM_BIT_PER_BYTE) + public int NUM_BIT_PER_BYTE; + public int NUM_BIT_PER_WORD; /* ============================================================================= @@ -14,6 +14,9 @@ public class Bitmap { */ Bitmap(long myNumBit) { + NUM_BIT_PER_BYTE = 8; + NUM_BIT_PER_WORD = ((8) * NUM_BIT_PER_BYTE); + numBit = myNumBit; numWord = DIVIDE_AND_ROUND_UP(numBit, NUM_BIT_PER_WORD); @@ -26,6 +29,10 @@ public class Bitmap { } Bitmap(Bitmap myBitMap) { + NUM_BIT_PER_BYTE = 8; + NUM_BIT_PER_WORD = ((8) * NUM_BIT_PER_BYTE); + + numBit = myBitMap.numBit; numWord = myBitMap.numWord; bits = new long[numWord]; @@ -65,12 +72,12 @@ public class Bitmap { */ boolean set (long i) { if ((i < 0) || (i >= numBit)) { - return FALSE; + return false; } - bits[i/NUM_BIT_PER_WORD] |= (1 << (i % NUM_BIT_PER_WORD)); + bits[((int)i)/NUM_BIT_PER_WORD] |= (1 << (i % NUM_BIT_PER_WORD)); - return TRUE; + return true; } @@ -82,12 +89,12 @@ public class Bitmap { */ boolean clear (long i) { if ((i < 0) || (i >= numBit)) { - return FALSE; + return false; } - bits[i/NUM_BIT_PER_WORD] &= ~(1 << (i % NUM_BIT_PER_WORD)); + bits[((int)i)/NUM_BIT_PER_WORD] &= ~(1 << (i % NUM_BIT_PER_WORD)); - return TRUE; + return true; } @@ -109,13 +116,16 @@ public class Bitmap { * -- Returns TRUE if ith bit is set, else FALSE * ============================================================================= */ - boolean isSet (long i) { - if ((i >= 0) && (i < numBit) && - (bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD)))) { - return TRUE; + boolean isSet (int i) { + int tempB = (int)bits[((int)i)/NUM_BIT_PER_WORD]; + int tempC = (1 << (((int)i) % NUM_BIT_PER_WORD)); + boolean tempbool = ((tempB & tempC) > 0) ? true:false; + //tempB /*bits[((int)i)/NUM_BIT_PER_WORD]*/ & tempC /*(1 << (i % NUM_BIT_PER_WORD))*/ + if ((i >= 0) && (i < (int)numBit) && tempbool) { + return true; } - return FALSE; + return false; } @@ -128,9 +138,9 @@ public class Bitmap { */ long findClear (long startIndex) { long i; - + boolean tempbool = ((bits[((int)i)/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD))) > 0) ? true:false; for (i = MAX(startIndex, 0); i < numBit; i++) { - if (!(bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD)))) { + if (!tempbool) { return i; } } @@ -149,7 +159,8 @@ public class Bitmap { long i; for (i = MAX(startIndex, 0); i < numBit; i++) { - if (bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD))) { + boolean tempbool = ((int)bits[((int)i)/NUM_BIT_PER_WORD] & (1 << ((int)i % NUM_BIT_PER_WORD)) > 0) ? true:false; + if (tempbool) { return i; } } @@ -174,9 +185,9 @@ public class Bitmap { long getNumSet () { long i; long count = 0; - for (i = 0; i < numBit; i++) { - if (bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD))) { + boolean tempbool = ((int)bits[((int)i)/NUM_BIT_PER_WORD] & (1 << ((int)i % NUM_BIT_PER_WORD)) > 0) ? true:false; + if (tempbool) { count++; } } @@ -198,7 +209,7 @@ public class Bitmap { void toggleAll () { long w; for (w = 0; w < numWord; w++) { - bits[w] ^= -1L; + bits[(int)w] ^= -1L; } } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Bitmap.java~ b/Robust/src/Benchmarks/SingleTM/genome/java/Bitmap.java~ index 0e437075..bdd93eaa 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Bitmap.java~ +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Bitmap.java~ @@ -3,8 +3,8 @@ public class Bitmap { public long numWord; public long bits[]; - private static NUM_BIT_PER_BYTE = 8; - private static NUM_BIT_PER_WORD = (8) * NUM_BIT_PER_BYTE) + public int NUM_BIT_PER_BYTE; + public int NUM_BIT_PER_WORD; /* ============================================================================= @@ -14,6 +14,9 @@ public class Bitmap { */ Bitmap(long myNumBit) { + NUM_BIT_PER_BYTE = 8; + NUM_BIT_PER_WORD = ((8) * NUM_BIT_PER_BYTE); + numBit = myNumBit; numWord = DIVIDE_AND_ROUND_UP(numBit, NUM_BIT_PER_WORD); @@ -26,6 +29,10 @@ public class Bitmap { } Bitmap(Bitmap myBitMap) { + NUM_BIT_PER_BYTE = 8; + NUM_BIT_PER_WORD = ((8) * NUM_BIT_PER_BYTE); + + numBit = myBitMap.numBit; numWord = myBitMap.numWord; bits = new long[numWord]; @@ -65,12 +72,12 @@ public class Bitmap { */ boolean set (long i) { if ((i < 0) || (i >= numBit)) { - return FALSE; + return false; } - bits[i/NUM_BIT_PER_WORD] |= (1 << (i % NUM_BIT_PER_WORD)); + bits[((int)i)/NUM_BIT_PER_WORD] |= (1 << (i % NUM_BIT_PER_WORD)); - return TRUE; + return true; } @@ -82,12 +89,12 @@ public class Bitmap { */ boolean clear (long i) { if ((i < 0) || (i >= numBit)) { - return FALSE; + return false; } - bits[i/NUM_BIT_PER_WORD] &= ~(1 << (i % NUM_BIT_PER_WORD)); + bits[((int)i)/NUM_BIT_PER_WORD] &= ~(1 << (i % NUM_BIT_PER_WORD)); - return TRUE; + return true; } @@ -109,13 +116,16 @@ public class Bitmap { * -- Returns TRUE if ith bit is set, else FALSE * ============================================================================= */ - boolean isSet (long i) { - if ((i >= 0) && (i < numBit) && - (bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD)))) { - return TRUE; + boolean isSet (int i) { + int tempB = (int)bits[((int)i)/NUM_BIT_PER_WORD]; + int tempC = (1 << (((int)i) % NUM_BIT_PER_WORD)); + boolean tempbool = ((tempB & tempC) > 0) ? true:false; + //tempB /*bits[((int)i)/NUM_BIT_PER_WORD]*/ & tempC /*(1 << (i % NUM_BIT_PER_WORD))*/ + if ((i >= 0) && (i < (int)numBit) && tempbool) { + return true; } - return FALSE; + return false; } @@ -128,9 +138,9 @@ public class Bitmap { */ long findClear (long startIndex) { long i; - + boolean tempbool = ((bits[((int)i)/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD))) > 0) ? true:false; for (i = MAX(startIndex, 0); i < numBit; i++) { - if (!(bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD)))) { + if (!tempbool) { return i; } } @@ -149,7 +159,8 @@ public class Bitmap { long i; for (i = MAX(startIndex, 0); i < numBit; i++) { - if (bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD))) { + boolean tempbool = (bits[((int)i)/NUM_BIT_PER_WORD] & (1 << ((int)i % NUM_BIT_PER_WORD)) > 0) ? true:false; + if (tempbool) { return i; } } @@ -174,9 +185,9 @@ public class Bitmap { long getNumSet () { long i; long count = 0; - for (i = 0; i < numBit; i++) { - if (bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD))) { + boolean tempbool = ((int)bits[((int)i)/NUM_BIT_PER_WORD] & (1 << ((int)i % NUM_BIT_PER_WORD)) > 0) ? true:false; + if (tempbool) { count++; } } @@ -198,7 +209,7 @@ public class Bitmap { void toggleAll () { long w; for (w = 0; w < numWord; w++) { - bits[w] ^= -1L; + bits[(int)w] ^= -1L; } } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Gene.java b/Robust/src/Benchmarks/SingleTM/genome/java/Gene.java index df2f306d..8c5dacae 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Gene.java +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Gene.java @@ -6,7 +6,7 @@ public class Gene { Gene(long myLength) { length = myLength; contents = ""; - startBitmapPtr = new BitMap(length); + startBitmapPtr = new Bitmap(length); } @@ -16,16 +16,27 @@ public class Gene { * ============================================================================= */ void create (Random randomObj) { - long i; - char nucleotides[] = { - NUCLEOTIDE_ADENINE, - NUCLEOTIDE_CYTOSINE, - NUCLEOTIDE_GUANINE, - NUCLEOTIDE_THYMINE, - }; + int i; + char[] nucleotides = new char[4]; + char[] arrayContents = new char[length]; + nucleotides[0] = 'a'; + nucleotides[1] = 'c'; + nucleotides[2] = 'g'; + nucleotides[3] = 't'; + +// System.out.println("length: " + length); for (i = 0; i < length; i++) { - contents[i] = nucleotides[(random_generate(randomObj)% NUCLEOTIDE_NUM_TYPE)]; + int legitimateNumber = (int)randomObj.random_generate(randomObj); + if(legitimateNumber < 0) { + legitimateNumber *= -1; + } +// System.out.println("legitNum: " + legitimateNumber + ":" + (legitimateNumber % 4)); + arrayContents[i] = nucleotides[legitimateNumber % 4]; +// System.out.println("arrayContents[" + i + "]: " + arrayContents[i]); } + + contents = new String(arrayContents); +// System.out.println("contents: " + contents); } } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Gene.java~ b/Robust/src/Benchmarks/SingleTM/genome/java/Gene.java~ index c78c495b..1d9929ad 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Gene.java~ +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Gene.java~ @@ -6,7 +6,7 @@ public class Gene { Gene(long myLength) { length = myLength; contents = ""; - startBitmapPtr = new BitMap(length); + startBitmapPtr = new Bitmap(length); } @@ -16,17 +16,27 @@ public class Gene { * ============================================================================= */ void create (Random randomObj) { - long i; - char nucleotides[] = { - NUCLEOTIDE_ADENINE, - NUCLEOTIDE_CYTOSINE, - NUCLEOTIDE_GUANINE, - NUCLEOTIDE_THYMINE, - }; + int i; + char[] nucleotides = new char[4]; + char[] arrayContents = new char[length]; + nucleotides[0] = 'a'; + nucleotides[1] = 'c'; + nucleotides[2] = 'g'; + nucleotides[3] = 't'; + + System.out.println("length: " + length); for (i = 0; i < length; i++) { - contents[i] = - nucleotides[(random_generate(randomObj)% NUCLEOTIDE_NUM_TYPE)]; + int legitimateNumber = (int)randomObj.random_generate(randomObj); + if(legitimateNumber < 0) { + legitimateNumber *= -1; + } +// System.out.println("legitNum: " + legitimateNumber + ":" + (legitimateNumber % 4)); + arrayContents[i] = nucleotides[legitimateNumber % 4]; + System.out.println("arrayContents[" + i + "]: " + arrayContents[i]); } + + contents = new String(arrayContents); + System.out.println("contents: " + contents); } } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Genome.java b/Robust/src/Benchmarks/SingleTM/genome/java/Genome.java index 610f8838..8cb8cc03 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Genome.java +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Genome.java @@ -11,14 +11,96 @@ */ -public class Genome { +public class Genome extends Thread { long geneLength; long segmentLength; long minNumSegment; long numThread; + GlobalArgs g_args; + int threadid; + + // add segments, random, etc to member variables + // include in constructor + // allows for passing in thread run function + Random randomPtr; + Gene genePtr; + Segments segmentsPtr; + Sequencer sequencerPtr; + Genome(String x[]) { parseCmdLine(x); + if(numThread == 0) { + numThread = 1; + } + + randomPtr = new Random(); + randomPtr.random_alloc(randomPtr); + randomPtr.random_seed(randomPtr, 0); + + System.out.println(""); + System.out.println("INFO: "); + System.out.println("GeneLength: " + geneLength); + System.out.println("SegmentLength: " + segmentLength); + System.out.println("MinNumSegment: " + minNumSegment); + System.out.println("NumThread: " + numThread); + + genePtr = new Gene(geneLength); + genePtr.create(randomPtr); + + segmentsPtr = new Segments(segmentLength, minNumSegment); + segmentsPtr.create(genePtr, randomPtr); + + sequencerPtr = new Sequencer(geneLength, segmentLength, segmentsPtr); + + } + + Genome(int myThreadid, long myGeneLength, long mySegLength, long myMinNumSegs, long myNumThread, Random myRandomPtr, Gene myGenePtr, Segments mySegmentsPtr, Sequencer mySequencerPtr) { + threadid = myThreadid; + geneLength = myGeneLength; + segmentLength = mySegLength; + minNumSegment = myMinNumSegs; + numThread = myNumThread; + + randomPtr = myRandomPtr; + genePtr = myGenePtr; + segmentsPtr = mySegmentsPtr; + sequencerPtr = mySequencerPtr; + } + + public void parseCmdLine(String args[]) { + int i = 0; + String arg; + while (i < args.length && args[i].startsWith("-")) { + arg = args[i++]; + //check options + if(arg.equals("-g")) { + if(i < args.length) { + this.geneLength = new Integer(args[i++]).intValue(); + } + } else if(arg.equals("-s")) { + if(i < args.length) { + this.segmentLength = new Integer(args[i++]).intValue(); + } + } else if(arg.equals("-n")) { + if(i < args.length) { + this.minNumSegment = new Integer(args[i++]).intValue(); + } + } else if(arg.equals("-t")) { + if(i < args.length) { + this.numThread = new Integer(args[i++]).intValue(); + } + } + } + + } + + public void run() { + while(true) { + Barrier.enterBarrier(); + Sequencer.run(threadid, numThread, randomPtr, sequencerPtr); + Barrier.enterBarrier(); + } } public static void main(String x[]){ @@ -29,41 +111,51 @@ public class Genome { /* GOTO_REAL(); */ /* Initialization */ -/* parseArgs(argc, (char** const)argv); */ +// parseArgs(); /* SIM_GET_NUM_CPU(global_params[PARAM_THREAD]); */ System.out.print("Creating gene and segments... "); Genome g = new Genome(x); + System.out.println("done."); + System.out.println("Gene length = " + g.genePtr.length); + System.out.println("Segment length = " + g.segmentsPtr.length); + System.out.println("Number segments = " + g.segmentsPtr.contentsPtr.size()); + + + Barrier.setBarrier((int)g.numThread); /* TM_STARTUP(numThread); */ /* P_MEMORY_STARTUP(numThread); */ /* thread_startup(numThread); */ - Random randomPtr = new Random(); - random_alloc(randomPtr); - random_seed(randomPtr, 0); +/* Create and Start Threads */ - Gene genePtr = new Gene(geneLength); - genePtr.create(randomPtr); - String gene = genePtr.contents; + String gene = g.genePtr.contents; - Segments segmentsPtr = new Segments(segmentLength, minNumSegment); - segmentsPtr.create(genePtr, randomPtr); - sequencer_t* sequencerPtr = sequencer_alloc(geneLength, segmentLength, segmentsPtr); - assert(sequencerPtr != NULL); + Genome[] gn = new Genome[g.numThread]; + + + for(int i = 0; ilength); - printf("Segment length = %li\n", segmentsPtr->length); - printf("Number segments = %li\n", vector_getSize(segmentsPtr->contentsPtr)); - fflush(stdout); +// fflush(stdout); /* Benchmark */ - printf("Sequencing gene... "); - fflush(stdout); - TIMER_READ(start); - GOTO_SIM(); + +// fflush(stdout); +// TIMER_READ(start); +// GOTO_SIM(); + +/* #ifdef OTM #pragma omp parallel { @@ -72,76 +164,41 @@ public class Genome { #else thread_start(sequencer_run, (void*)sequencerPtr); #endif - GOTO_REAL(); - TIMER_READ(stop); - puts("done."); - printf("Time = %lf\n", TIMER_DIFF_SECONDS(start, stop)); - fflush(stdout); +// GOTO_REAL(); +// TIMER_READ(stop); +*/ + + //sequencer_run(threadId); + + System.out.println("done."); /* Check result */ { - char* sequence = sequencerPtr->sequence; - int result = strcmp(gene, sequence); - printf("Sequence matches gene: %s\n", (result ? "no" : "yes")); + String sequence = g.sequencerPtr.sequence; + System.out.println("gene: " + gene); + System.out.println("sequence: " + sequence); + boolean result = (gene.compareTo(sequence) == 0) ? true:false; + System.out.println("result: " + result); + System.out.println("Sequence matches gene: " + (result ? "no" : "yes")); if (result) { - printf("gene = %s\n", gene); - printf("sequence = %s\n", sequence); + System.out.println("gene = " + gene); + System.out.println("sequence = " + sequence); } - fflush(stdout); - assert(strlen(sequence) >= strlen(gene)); +// fflush(stdout); +// assert(strlen(sequence) >= strlen(gene)); } /* Clean up */ - printf("Deallocating memory... "); - fflush(stdout); - sequencer_free(sequencerPtr); - segments_free(segmentsPtr); - gene_free(genePtr); - random_free(randomPtr); - puts("done."); - fflush(stdout); - - TM_SHUTDOWN(); - P_MEMORY_SHUTDOWN(); - GOTO_SIM(); +// TM_SHUTDOWN(); +// P_MEMORY_SHUTDOWN(); - thread_shutdown(); +// GOTO_SIM(); +// thread_shutdown(); - MAIN_RETURN(0); +// MAIN_RETURN(0); } - public static void parseCmdLine(String args[]) { - int i = 0; - String arg; - while (i < args.length && args[i].startsWith("-")) { - arg = args[i++]; - //check options - if(arg.equals("-g")) { - if(i < args.length) { - geneLength = new Integer(args[i++]).intValue(); - } - } else if(arg.equals("-s")) { - if(i < args.length) { - segmentLength = new Integer(args[i++]).intValue(); - } - } else if(arg.equals("-n")) { - if(i < args.length) { - minNumSegment = new Integer(args[i++]).intValue(); - } - } else if(arg.equals("-t")) { - if(i < args.length) { - numThread = new Integer(args[i++]).intValue(); - } - } - } - } -} -public enum param_types { - PARAM_GENE /*= (unsigned char)'g'*/, - PARAM_NUMBER /*= (unsigned char)'n'*/, - PARAM_SEGMENT /*= (unsigned char)'s'*/, - PARAM_THREAD /*= (unsigned char)'t',*/ } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Genome.java~ b/Robust/src/Benchmarks/SingleTM/genome/java/Genome.java~ index 40e407e3..4ae14464 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Genome.java~ +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Genome.java~ @@ -11,14 +11,96 @@ */ -public class Genome { +public class Genome extends Thread { long geneLength; long segmentLength; long minNumSegment; long numThread; + GlobalArgs g_args; + int threadid; + + // add segments, random, etc to member variables + // include in constructor + // allows for passing in thread run function + Random randomPtr; + Gene genePtr; + Segments segmentsPtr; + Sequencer sequencerPtr; + Genome(String x[]) { parseCmdLine(x); + if(numThread == 0) { + numThread = 1; + } + + randomPtr = new Random(); + randomPtr.random_alloc(randomPtr); + randomPtr.random_seed(randomPtr, 0); + + System.out.println(""); + System.out.println("INFO: "); + System.out.println("GeneLength: " + geneLength); + System.out.println("SegmentLength: " + segmentLength); + System.out.println("MinNumSegment: " + minNumSegment); + System.out.println("NumThread: " + numThread); + + genePtr = new Gene(geneLength); + genePtr.create(randomPtr); + + segmentsPtr = new Segments(segmentLength, minNumSegment); + segmentsPtr.create(genePtr, randomPtr); + + sequencerPtr = new Sequencer(geneLength, segmentLength, segmentsPtr); + + } + + Genome(int myThreadid, long myGeneLength, long mySegLength, long myMinNumSegs, long myNumThread, Random myRandomPtr, Gene myGenePtr, Segments mySegmentsPtr, Sequencer mySequencerPtr) { + threadid = myThreadid; + geneLength = myGeneLength; + segmentLength = mySegLength; + minNumSegment = myMinNumSegs; + numThread = myNumThread; + + randomPtr = myRandomPtr; + genePtr = myGenePtr; + segmentsPtr = mySegmentsPtr; + sequencerPtr = mySequencerPtr; + } + + public void parseCmdLine(String args[]) { + int i = 0; + String arg; + while (i < args.length && args[i].startsWith("-")) { + arg = args[i++]; + //check options + if(arg.equals("-g")) { + if(i < args.length) { + this.geneLength = new Integer(args[i++]).intValue(); + } + } else if(arg.equals("-s")) { + if(i < args.length) { + this.segmentLength = new Integer(args[i++]).intValue(); + } + } else if(arg.equals("-n")) { + if(i < args.length) { + this.minNumSegment = new Integer(args[i++]).intValue(); + } + } else if(arg.equals("-t")) { + if(i < args.length) { + this.numThread = new Integer(args[i++]).intValue(); + } + } + } + + } + + public void run() { + while(true) { + Barrier.enterBarrier(); + Sequencer.run(threadid, numThread, randomPtr, sequencerPtr); + Barrier.enterBarrier(); + } } public static void main(String x[]){ @@ -29,42 +111,51 @@ public class Genome { /* GOTO_REAL(); */ /* Initialization */ -/* parseArgs(argc, (char** const)argv); */ +// parseArgs(); /* SIM_GET_NUM_CPU(global_params[PARAM_THREAD]); */ System.out.print("Creating gene and segments... "); Genome g = new Genome(x); + System.out.println("done."); + System.out.println("Gene length = " + g.genePtr.length); + System.out.println("Segment length = " + g.segmentsPtr.length); + System.out.println("Number segments = " + g.segmentsPtr.contentsPtr.size()); + + + Barrier.setBarrier((int)g.numThread); /* TM_STARTUP(numThread); */ /* P_MEMORY_STARTUP(numThread); */ /* thread_startup(numThread); */ - Random randomPtr = new Random(); - random_alloc(randomPtr); - random_seed(randomPtr, 0); +/* Create and Start Threads */ - Gene genePtr = new Gene(geneLength); - genePtr.create(randomPtr); - String gene = genePtr.contents; + String gene = g.genePtr.contents; + + Genome[] gn = new Genome[g.numThread]; + + + for(int i = 0; ilength); - printf("Segment length = %li\n", segmentsPtr->length); - printf("Number segments = %li\n", vector_getSize(segmentsPtr->contentsPtr)); - fflush(stdout); +// fflush(stdout); /* Benchmark */ - printf("Sequencing gene... "); - fflush(stdout); - TIMER_READ(start); - GOTO_SIM(); + System.out.print("Sequencing gene... "); +// fflush(stdout); +// TIMER_READ(start); +// GOTO_SIM(); + +/* #ifdef OTM #pragma omp parallel { @@ -73,76 +164,41 @@ public class Genome { #else thread_start(sequencer_run, (void*)sequencerPtr); #endif - GOTO_REAL(); - TIMER_READ(stop); - puts("done."); - printf("Time = %lf\n", TIMER_DIFF_SECONDS(start, stop)); - fflush(stdout); +// GOTO_REAL(); +// TIMER_READ(stop); +*/ + + //sequencer_run(threadId); + + System.out.println("done."); /* Check result */ { - char* sequence = sequencerPtr->sequence; - int result = strcmp(gene, sequence); - printf("Sequence matches gene: %s\n", (result ? "no" : "yes")); + String sequence = g.sequencerPtr.sequence; + System.out.println("gene: " + gene); + System.out.println("sequence: " + sequence); + boolean result = (gene.compareTo(sequence) == 0) ? true:false; + System.out.println("result: " + result); + System.out.println("Sequence matches gene: " + (result ? "no" : "yes")); if (result) { - printf("gene = %s\n", gene); - printf("sequence = %s\n", sequence); + System.out.println("gene = " + gene); + System.out.println("sequence = " + sequence); } - fflush(stdout); - assert(strlen(sequence) >= strlen(gene)); +// fflush(stdout); +// assert(strlen(sequence) >= strlen(gene)); } /* Clean up */ - printf("Deallocating memory... "); - fflush(stdout); - sequencer_free(sequencerPtr); - segments_free(segmentsPtr); - gene_free(genePtr); - random_free(randomPtr); - puts("done."); - fflush(stdout); - TM_SHUTDOWN(); - P_MEMORY_SHUTDOWN(); +// TM_SHUTDOWN(); +// P_MEMORY_SHUTDOWN(); - GOTO_SIM(); +// GOTO_SIM(); +// thread_shutdown(); - thread_shutdown(); - - MAIN_RETURN(0); +// MAIN_RETURN(0); } - public static void parseCmdLine(String args[]) { - int i = 0; - String arg; - while (i < args.length && args[i].startsWith("-")) { - arg = args[i++]; - //check options - if(arg.equals("-g")) { - if(i < args.length) { - geneLength = new Integer(args[i++]).intValue(); - } - } else if(arg.equals("-s")) { - if(i < args.length) { - segmentLength = new Integer(args[i++]).intValue(); - } - } else if(arg.equals("-n")) { - if(i < args.length) { - minNumSegment = new Integer(args[i++]).intValue(); - } - } else if(arg.equals("-t")) { - if(i < args.length) { - numThread = new Integer(args[i++]).intValue(); - } - } - } - } -} -public enum param_types { - PARAM_GENE /*= (unsigned char)'g'*/, - PARAM_NUMBER /*= (unsigned char)'n'*/, - PARAM_SEGMENT /*= (unsigned char)'s'*/, - PARAM_THREAD /*= (unsigned char)'t',*/ } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Segments.java b/Robust/src/Benchmarks/SingleTM/genome/java/Segments.java index d685eef4..83447e29 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Segments.java +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Segments.java @@ -8,9 +8,9 @@ public class Segments { Segments (long myLength, long myMinNum) { minNum = myMinNum; length = myLength; - - contentsPtr = new Vector(minNum); - + + strings = new String[(int)minNum]; + contentsPtr = new Vector((int)minNum); } @@ -24,35 +24,38 @@ public class Segments { long geneLength; Bitmap startBitmapPtr; long numStart; - long i; + int i; long maxZeroRunLength; geneString = genePtr.contents; geneLength = genePtr.length; startBitmapPtr = genePtr.startBitmapPtr; - numStart = geneLength - segmentLength + 1; - + numStart = geneLength - length + 1; + + System.out.println("minNum: " + minNum); /* Pick some random segments to start */ - for (i = 0; i < minNumSegment; i++) { - long j = (long)(random_generate(randomPtr) % numStart); + for (i = 0; i < minNum; i++) { + int j = (int)(randomPtr.random_generate(randomPtr) % numStart); boolean status = startBitmapPtr.set(j); - strings[i] = geneString[j]; - segmentsContentsPtr.add(strings[i]); + strings[i] = geneString.substring((int)j, (int)(j+length)); + contentsPtr.addElement(strings[i]); } + + /* Make sure segment covers start */ i = 0; if (!startBitmapPtr.isSet(i)) { String string; - string = geneString[i]; - segmentsContentsPtr.add(string); + string = geneString.subString((int)i, (int)(i+length)); + contentsPtr.addElement(string); startBitmapPtr.set(i); } /* Add extra segments to fill holes and ensure overlap */ maxZeroRunLength = length - 1; for (i = 0; i < numStart; i++) { - long i_stop = MIN((i+maxZeroRunLength), numStart); + long i_stop = (long)Math.imin((int)(i+maxZeroRunLength), (int)numStart); for ( /* continue */; i < i_stop; i++) { if (startBitmapPtr.isSet(i)) { break; @@ -61,10 +64,17 @@ public class Segments { if (i == i_stop) { /* Found big enough hole */ i = i - 1; - String string = geneString[i]; - segmentsContentsPtr.add(string); + String string = geneString.subString((int)i, (int)(i+length)); + contentsPtr.addElement(string); startBitmapPtr.set(i); } } + + System.out.println("gene: " + geneString); + for(i = 0; i < contentsPtr.size(); i++) { + System.out.print(" " + contentsPtr.array[i]); + } + System.out.println(""); + } } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Segments.java~ b/Robust/src/Benchmarks/SingleTM/genome/java/Segments.java~ index accbdcb3..5deb9238 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Segments.java~ +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Segments.java~ @@ -8,9 +8,9 @@ public class Segments { Segments (long myLength, long myMinNum) { minNum = myMinNum; length = myLength; - - contentsPtr = new Vector(minNum); - + + strings = new String[(int)minNum]; + contentsPtr = new Vector((int)minNum); } @@ -24,35 +24,38 @@ public class Segments { long geneLength; Bitmap startBitmapPtr; long numStart; - long i; + int i; long maxZeroRunLength; geneString = genePtr.contents; geneLength = genePtr.length; startBitmapPtr = genePtr.startBitmapPtr; - numStart = geneLength - segmentLength + 1; - + numStart = geneLength - length + 1; + + System.out.println("minNum: " + minNum); /* Pick some random segments to start */ - for (i = 0; i < minNumSegment; i++) { - long j = (long)(random_generate(randomPtr) % numStart); + for (i = 0; i < minNum; i++) { + int j = (int)(randomPtr.random_generate(randomPtr) % numStart); boolean status = startBitmapPtr.set(j); - strings[i] = geneString[j]; - segmentsContentsPtr.add(strings[i]); + strings[i] = geneString.substring((int)j, (int)(j+length)); + contentsPtr.addElement(strings[i]); } + + /* Make sure segment covers start */ i = 0; if (!startBitmapPtr.isSet(i)) { String string; - string = geneString[i]; - segmentsContentsPtr.add(string); + string = geneString.subString((int)i, (int)(i+length)); + contentsPtr.addElement(string); startBitmapPtr.set(i); } /* Add extra segments to fill holes and ensure overlap */ maxZeroRunLength = length - 1; for (i = 0; i < numStart; i++) { - long i_stop = MIN((i+maxZeroRunLength), numStart); + long i_stop = (long)Math.imin((int)(i+maxZeroRunLength), (int)numStart); for ( /* continue */; i < i_stop; i++) { if (startBitmapPtr.isSet(i)) { break; @@ -61,11 +64,17 @@ public class Segments { if (i == i_stop) { /* Found big enough hole */ i = i - 1; - String string = geneString[i]; - segmentsContentsPtr.add(string); + String string = geneString.subString((int)i, (int)(i+length)); + contentsPtr.addElement(string); startBitmapPtr.set(i); - assert(status); } } + + System.out.println("gene: " + geneString); + for(i = 0; i < contentsPtr.size(); i++) { + System.out.print(" " + contentsPtr.array[i]); + } + System.out.println(); + } } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Sequencer.java b/Robust/src/Benchmarks/SingleTM/genome/java/Sequencer.java index a8c81b9f..d0510eb2 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Sequencer.java +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Sequencer.java @@ -1,11 +1,11 @@ public class Sequencer { - public char* sequence; + public String sequence; public Segments segmentsPtr; /* For removing duplicate segments */ - Hashmap uniqueSegmentsPtr; + HashMap uniqueSegmentsPtr; /* For matching segments */ endInfoEntry endInfoEntries[]; @@ -25,18 +25,18 @@ public class Sequencer { * ============================================================================= */ Sequencer (long myGeneLength, long mySegmentLength, Segments mySegmentsPtr) { - + long maxNumUniqueSegment = myGeneLength - mySegmentLength + 1; - long i; + int i; - uniqueSegmentsPtr = new Hashmap(myGeneLength); + uniqueSegmentsPtr = new HashMap((int)myGeneLength); /* For finding a matching entry */ endInfoEntries = new endInfoEntry[maxNumUniqueSegment]; for (i = 0; i < maxNumUniqueSegment; i++) { - endInfoEntries[i].isEnd = TRUE; - endInfoEntries[i].jumpToNext = 1; + endInfoEntries[i] = new endInfoEntry(true, 1); } + startHashToConstructEntryTables = new Table[mySegmentLength]; for (i = 1; i < mySegmentLength; i++) { /* 0 is dummy entry */ startHashToConstructEntryTables[i] = new Table(myGeneLength); @@ -44,22 +44,15 @@ public class Sequencer { segmentLength = mySegmentLength; /* For constructing sequence */ - constructEntries = new ContructEntry[maxNumUniqueSegment]; + constructEntries = new constructEntry[maxNumUniqueSegment]; for (i= 0; i < maxNumUniqueSegment; i++) { - constructEntries[i].isStart = TRUE; - constructEntries[i].segment = NULL; - constructEntries[i].endHash = 0; - constructEntries[i].startPtr = constructEntries[i]; - constructEntries[i].nextPtr = NULL; - constructEntries[i].endPtr = constructEntries[i]; - constructEntries[i].overlap = 0; - constructEntries[i].length = segmentLength; + constructEntries[i] = new constructEntry(null, true, 0, constructEntries[i], null, constructEntries[i], 0, segmentLength); } - hashToConstructEntryTable = new Table(geneLength); + hashToConstructEntryTable = new Table(myGeneLength); segmentsPtr = mySegmentsPtr; - } + } /* ============================================================================= @@ -67,19 +60,23 @@ public class Sequencer { * ============================================================================= */ - void run () { + public static void run (long threadNum, long numOfThreads, Random randomPtr, Sequencer sequencerPtr) { //TM_THREAD_ENTER(); - long threadId = thread_getId(); +// long threadId = thread_getId(); + + long threadId = threadNum; + + Segments segmentsPtr = sequencerPtr.segmentsPtr; //Sequencer sequencerPtr = (sequencer_t*)argPtr; - Hashmap uniqueSegmentsPtr; - endInfoEntry endInfoEntries[]; - Hashmap startHashToConstructEntryTables[]; - constructEntry constructEntries[]; - Hashmap hashToConstructEntryTable; + HashMap uniqueSegmentsPtr = sequencerPtr.uniqueSegmentsPtr; + endInfoEntry endInfoEntries[] = sequencerPtr.endInfoEntries; + Table startHashToConstructEntryTables[] = sequencerPtr.startHashToConstructEntryTables; + constructEntry constructEntries[] = sequencerPtr.constructEntries; + Table hashToConstructEntryTable = sequencerPtr.hashToConstructEntryTable; Vector segmentsContentsPtr = segmentsPtr.contentsPtr; long numSegment = segmentsContentsPtr.size(); @@ -92,12 +89,14 @@ public class Sequencer { long numUniqueSegment; long substringLength; long entryIndex; + + int CHUNK_STEP1 = 12; /* * Step 1: Remove duplicate segments */ -#if defined(HTM) || defined(STM) - long numThread = thread_getNumThread(); +//#if defined(HTM) || defined(STM) + long numThread = numOfThreads; { /* Choose disjoint segments [i_start,i_stop) for each thread */ long partitionSize = (numSegment + numThread/2) / numThread; /* with rounding */ @@ -108,27 +107,35 @@ public class Sequencer { i_stop = i_start + partitionSize; } } -#else /* !(HTM || STM) */ - i_start = 0; - i_stop = numSegment; -#endif /* !(HTM || STM) */ +//#else /* !(HTM || STM) */ +// i_start = 0; +// i_stop = numSegment; +//#endif /* !(HTM || STM) */ for (i = i_start; i < i_stop; i+=CHUNK_STEP1) { - TM_BEGIN(); - { +// TM_BEGIN(); + atomic { long ii; - long ii_stop = MIN(i_stop, (i+CHUNK_STEP1)); + long ii_stop = Math.imin((int)i_stop, (int)(i+CHUNK_STEP1)); for (ii = i; ii < ii_stop; ii++) { - string segment = segmentsContentsPtr.get(ii); - TMHASHTABLE_INSERT(uniqueSegmentsPtr, - segment, - segment); + String segment = (String)segmentsContentsPtr.elementAt((int)ii); +// TMHASHTABLE_INSERT(uniqueSegmentsPtr, segment, segment); + System.out.print("Placing: " + segment + " into uniqueSegmentsPtr..."); + if(uniqueSegmentsPtr.put(segment, segment) == null) { + System.out.println("success!"); + } else { + System.out.println("fail, double entry."); + } } /* ii */ } - TM_END(); +// TM_END(); } - thread_barrier_wait(); - +// thread_barrier_wait(); + Barrier.enterBarrier(); + + + + /* * Step 2a: Iterate over unique segments and compute hashes. * @@ -150,13 +157,14 @@ public class Sequencer { */ /* uniqueSegmentsPtr is constant now */ - numUniqueSegment = hashtable_getSize(uniqueSegmentsPtr); + numUniqueSegment = uniqueSegmentsPtr.size(); entryIndex = 0; -#if defined(HTM) || defined(STM) +//#if defined(HTM) || defined(STM) { /* Choose disjoint segments [i_start,i_stop) for each thread */ - long num = uniqueSegmentsPtr->numBucket; + long num = uniqueSegmentsPtr.size(); + System.out.println("num: " + num); long partitionSize = (num + numThread/2) / numThread; /* with rounding */ i_start = threadId * partitionSize; if (threadId == (numThread - 1)) { @@ -165,97 +173,152 @@ public class Sequencer { i_stop = i_start + partitionSize; } } + { /* Approximate disjoint segments of element allocation in constructEntries */ long partitionSize = (numUniqueSegment + numThread/2) / numThread; /* with rounding */ entryIndex = threadId * partitionSize; } -#else /* !(HTM || STM) */ - i_start = 0; - i_stop = uniqueSegmentsPtr->numBucket; - entryIndex = 0; -#endif /* !(HTM || STM) */ +//#else /* !(HTM || STM) */ +// i_start = 0; +// i_stop = uniqueSegmentsPtr.size(); +// entryIndex = 0; +//#endif /* !(HTM || STM) */ + + String uniqueArray[] = new String[uniqueSegmentsPtr.size()]; + int ind = 0; + HashMapIterator iterarian = uniqueSegmentsPtr.iterator(1); + String roar; + System.out.println("uniqueSegmentsPtr contents: "); + while(iterarian.hasNext()) { + roar = (String)iterarian.next(); + uniqueArray[ind++] = roar; + System.out.println(" " + roar); + } + + i_stop = Math.imin(ind, (int)i_stop); for (i = i_start; i < i_stop; i++) { + String segment = uniqueArray[(int)i]; + System.out.println("segment[" + i + "]: " + segment); + // list_iter_t it; + // list_iter_reset(&it, chainPtr); - list_t* chainPtr = uniqueSegmentsPtr->buckets[i]; - list_iter_t it; - list_iter_reset(&it, chainPtr); + // while (list_iter_hasNext(&it, chainPtr)) { - while (list_iter_hasNext(&it, chainPtr)) { + // char* segment = (char*)((pair_t*)list_iter_next(&it, chainPtr))->firstPtr; - char* segment = - (char*)((pair_t*)list_iter_next(&it, chainPtr))->firstPtr; - constructEntry_t* constructEntryPtr; - long j; - ulong_t startHash; - bool_t status; + long newj; + long startHash; + boolean status; - /* Find an empty constructEntries entry */ - TM_BEGIN(); - while (((void*)TM_SHARED_READ_P(constructEntries[entryIndex].segment)) != NULL) { - entryIndex = (entryIndex + 1) % numUniqueSegment; /* look for empty */ - } - constructEntryPtr = &constructEntries[entryIndex]; - TM_SHARED_WRITE_P(constructEntryPtr->segment, segment); - TM_END(); - entryIndex = (entryIndex + 1) % numUniqueSegment; - - /* - * Save hashes (sdbm algorithm) of segment substrings - * - * endHashes will be computed for shorter substrings after matches - * have been made (in the next phase of the code). This will reduce - * the number of substrings for which hashes need to be computed. - * - * Since we can compute startHashes incrementally, we go ahead - * and compute all of them here. - */ - /* constructEntryPtr is local now */ - constructEntryPtr->endHash = (ulong_t)hashString(&segment[1]); - - startHash = 0; - for (j = 1; j < segmentLength; j++) { - startHash = (ulong_t)segment[j-1] + - (startHash << 6) + (startHash << 16) - startHash; - TM_BEGIN(); - status = TMTABLE_INSERT(startHashToConstructEntryTables[j], - (ulong_t)startHash, - (void*)constructEntryPtr ); - TM_END(); - assert(status); - } + /* Find an empty constructEntries entry */ + atomic { +// TM_BEGIN(); +// while (((void*)TM_SHARED_READ_P(constructEntries[entryIndex].segment)) != NULL) { + while(constructEntries[(int)entryIndex].segment != null) { + entryIndex = (entryIndex + 1) % numUniqueSegment; /* look for empty */ + } +// constructEntryPtr = &constructEntries[entryIndex]; +// TM_SHARED_WRITE_P(constructEntryPtr->segment, segment); + constructEntries[(int)entryIndex].segment = segment; + System.out.println("constructEntries[" + entryIndex + "]: " + constructEntries[(int)entryIndex].segment); +// TM_END(); + } + + constructEntry constructEntryPtr = constructEntries[(int)entryIndex]; + + entryIndex = (entryIndex + 1) % numUniqueSegment; + + + + /* + * Save hashes (sdbm algorithm) of segment substrings + * + * endHashes will be computed for shorter substrings after matches + * have been made (in the next phase of the code). This will reduce + * the number of substrings for which hashes need to be computed. + * + * Since we can compute startHashes incrementally, we go ahead + * and compute all of them here. + */ + /* constructEntryPtr is local now */ + constructEntryPtr.endHash = hashString(segment.substring(1)); + + System.out.println("constructEntryPtr.segment: " + constructEntryPtr.segment); + System.out.println("constructentryPtr.hash: " + constructEntryPtr.endHash); + + startHash = 0; + for (newj = 1; newj < segmentLength; newj++) { + startHash = segment.charAt((int)newj-1) + (startHash << 6) + (startHash << 16) - startHash; + atomic { +// TM_BEGIN(); +// status = TMTABLE_INSERT(startHashToConstructEntryTables[j], (ulong_t)startHash, (void*)constructEntryPtr ); + System.out.println("BEFORE INSERTION INTO TABLE"); + System.out.println("constructEntryPtr.segment: " + constructEntryPtr.segment); + System.out.println("constructentryPtr.hash: " + constructEntryPtr.endHash); + + boolean check = startHashToConstructEntryTables[(int)newj].table_insert(startHash, constructEntryPtr); + System.out.println("check: " + check); +// TM_END(); + } +// assert(status); + System.out.println("AFTER INSERTION INTO TABLE"); + System.out.println("constructEntryPtr.segment: " + constructEntryPtr.segment); + System.out.println("constructentryPtr.hash: " + constructEntryPtr.endHash); + + + } + + System.out.println("OUTSIDE INTO TABLE"); + System.out.println("constructEntryPtr.segment: " + constructEntryPtr.segment); + System.out.println("constructentryPtr.hash: " + constructEntryPtr.endHash); + + + int tempi; + for(tempi = 0; tempi < 4; tempi++) { + System.out.println("centries[" + tempi + "]: " + constructEntries[tempi].segment); + } - /* - * For looking up construct entries quickly - */ - startHash = (ulong_t)segment[j-1] + - (startHash << 6) + (startHash << 16) - startHash; - TM_BEGIN(); - status = TMTABLE_INSERT(hashToConstructEntryTable, - (ulong_t)startHash, - (void*)constructEntryPtr); - TM_END(); - assert(status); + /* + * For looking up construct entries quickly + */ + startHash = segment.charAt((int)newj-1) + (startHash << 6) + (startHash << 16) - startHash; + atomic { +// TM_BEGIN(); +// status = TMTABLE_INSERT(hashToConstructEntryTable, (ulong_t)startHash, (void*)constructEntryPtr); + hashToConstructEntryTable.table_insert(startHash, constructEntryPtr); +// TM_END(); } +// assert(status); + } + + int tempi; + for(tempi = 0; tempi < 4; tempi++) { + System.out.println("centries[" + tempi + "]: " + constructEntries[tempi].segment); + } + + System.out.println("out of for"); - thread_barrier_wait(); - +// thread_barrier_wait(); + Barrier.enterBarrier(); + /* * Step 2b: Match ends to starts by using hash-based string comparison. */ for (substringLength = segmentLength-1; substringLength > 0; substringLength--) { - table_t* startHashToConstructEntryTablePtr = - startHashToConstructEntryTables[substringLength]; - list_t** buckets = startHashToConstructEntryTablePtr->buckets; - long numBucket = startHashToConstructEntryTablePtr->numBucket; + Table startHashToConstructEntryTablePtr = startHashToConstructEntryTables[(int)substringLength]; + LinkedList buckets[] = startHashToConstructEntryTablePtr.buckets; + long numBucket = startHashToConstructEntryTablePtr.numBucket; + + System.out.println("Retrieved the buckets."); long index_start; long index_stop; -#if defined(HTM) || defined(STM) +//#if defined(HTM) || defined(STM) { /* Choose disjoint segments [index_start,index_stop) for each thread */ long partitionSize = (numUniqueSegment + numThread/2) / numThread; /* with rounding */ @@ -266,88 +329,109 @@ public class Sequencer { index_stop = index_start + partitionSize; } } -#else /* !(HTM || STM) */ - index_start = 0; - index_stop = numUniqueSegment; -#endif /* !(HTM || STM) */ +//#else /* !(HTM || STM) */ +// index_start = 0; +// index_stop = numUniqueSegment; +//#endif /* !(HTM || STM) */ + + index_stop = Math.imin(ind, (int)index_stop); + + System.out.println("index_start: " + index_start); + System.out.println("index_stop: " + index_stop); + + System.out.println("endSegment: " + constructEntries[(int)index_start].segment); /* Iterating over disjoint itervals in the range [0, numUniqueSegment) */ for (entryIndex = index_start; entryIndex < index_stop; - entryIndex += endInfoEntries[entryIndex].jumpToNext) + entryIndex += endInfoEntries[(int)entryIndex].jumpToNext) { - if (!endInfoEntries[entryIndex].isEnd) { + if (!endInfoEntries[(int)entryIndex].isEnd) { continue; } /* ConstructEntries[entryIndex] is local data */ - constructEntry_t* endConstructEntryPtr = - &constructEntries[entryIndex]; - char* endSegment = endConstructEntryPtr->segment; - ulong_t endHash = endConstructEntryPtr->endHash; - - list_t* chainPtr = buckets[endHash % numBucket]; /* buckets: constant data */ - list_iter_t it; - list_iter_reset(&it, chainPtr); + constructEntry endConstructEntryPtr = constructEntries[(int)entryIndex]; + System.out.println("Retrieved constructEntry[" + entryIndex + "]."); + String endSegment = endConstructEntryPtr.segment; + System.out.println("pyah."); + System.out.println("endSegment: " + constructEntries[(int)entryIndex].segment); + long endHash = endConstructEntryPtr.endHash; + System.out.println("endHash: " + endHash); + + LinkedList chainPtr = buckets[(int)(endHash % numBucket)]; /* buckets: constant data */ + LinkedListIterator it = (LinkedListIterator)chainPtr.iterator(); +// list_iter_reset(&it, chainPtr); /* Linked list at chainPtr is constant */ - while (list_iter_hasNext(&it, chainPtr)) { + while (it.hasNext()) { - constructEntry_t* startConstructEntryPtr = - (constructEntry_t*)list_iter_next(&it, chainPtr); - char* startSegment = startConstructEntryPtr->segment; + constructEntry startConstructEntryPtr = (constructEntry)it.next(); + String startSegment = startConstructEntryPtr.segment; long newLength = 0; /* endConstructEntryPtr is local except for properties startPtr/endPtr/length */ - TM_BEGIN(); + atomic { +// TM_BEGIN(); /* Check if matches */ - if (TM_SHARED_READ(startConstructEntryPtr->isStart) && - (TM_SHARED_READ_P(endConstructEntryPtr->startPtr) != startConstructEntryPtr) && - (strncmp(startSegment, - &endSegment[segmentLength - substringLength], - substringLength) == 0)) - { - TM_SHARED_WRITE(startConstructEntryPtr->isStart, FALSE); - - constructEntry_t* startConstructEntry_endPtr; - constructEntry_t* endConstructEntry_startPtr; +// if (TM_SHARED_READ(startConstructEntryPtr->isStart) && +// (TM_SHARED_READ_P(endConstructEntryPtr->startPtr) != startConstructEntryPtr) && +// (strncmp(startSegment, +// &endSegment[segmentLength - substringLength], +// substringLength) == 0)) + if(startConstructEntryPtr.isStart && + (endConstructEntryPtr.startPtr != startConstructEntryPtr) && + (startSegment != endSegment.substring((int)(segmentLength-substringLength), (int)substringLength))) + { +// TM_SHARED_WRITE(startConstructEntryPtr->isStart, FALSE); + startConstructEntryPtr.isStart = false; + + constructEntry startConstructEntry_endPtr; + constructEntry endConstructEntry_startPtr; /* Update endInfo (appended something so no longer end) */ - TM_LOCAL_WRITE(endInfoEntries[entryIndex].isEnd, FALSE); +// TM_LOCAL_WRITE(endInfoEntries[entryIndex].isEnd, FALSE); + endInfoEntries[(int)entryIndex].isEnd = false; /* Update segment chain construct info */ - startConstructEntry_endPtr = - (constructEntry_t*)TM_SHARED_READ_P(startConstructEntryPtr->endPtr); - endConstructEntry_startPtr = - (constructEntry_t*)TM_SHARED_READ_P(endConstructEntryPtr->startPtr); - - assert(startConstructEntry_endPtr); - assert(endConstructEntry_startPtr); - TM_SHARED_WRITE_P(startConstructEntry_endPtr->startPtr, - endConstructEntry_startPtr); - TM_LOCAL_WRITE_P(endConstructEntryPtr->nextPtr, - startConstructEntryPtr); - TM_SHARED_WRITE_P(endConstructEntry_startPtr->endPtr, - startConstructEntry_endPtr); - TM_SHARED_WRITE(endConstructEntryPtr->overlap, substringLength); - newLength = (long)TM_SHARED_READ(endConstructEntry_startPtr->length) + - (long)TM_SHARED_READ(startConstructEntryPtr->length) - - substringLength; - TM_SHARED_WRITE(endConstructEntry_startPtr->length, newLength); - } /* if (matched) */ - - TM_END(); - - if (!endInfoEntries[entryIndex].isEnd) { /* if there was a match */ +// startConstructEntry_endPtr = (constructEntry_t*)TM_SHARED_READ_P(startConstructEntryPtr->endPtr); + startConstructEntry_endPtr = startConstructEntryPtr.endPtr; +// endConstructEntry_startPtr = (constructEntry_t*)TM_SHARED_READ_P(endConstructEntryPtr->startPtr); + endConstructEntry_startPtr = endConstructEntryPtr.startPtr; + +// assert(startConstructEntry_endPtr); +// assert(endConstructEntry_startPtr); + + +// TM_SHARED_WRITE_P(startConstructEntry_endPtr->startPtr, endConstructEntry_startPtr); + startConstructEntry_endPtr.startPtr = endConstructEntry_startPtr; +// TM_LOCAL_WRITE_P(endConstructEntryPtr->nextPtr, startConstructEntryPtr); + endConstructEntryPtr.nextPtr = startConstructEntryPtr; +// TM_SHARED_WRITE_P(endConstructEntry_startPtr->endPtr, startConstructEntry_endPtr); + endConstructEntry_startPtr.endPtr = startConstructEntry_endPtr; +// TM_SHARED_WRITE(endConstructEntryPtr->overlap, substringLength); + endConstructEntryPtr.overlap = substringLength; + newLength = endConstructEntry_startPtr.length + startConstructEntryPtr.length - substringLength; +// TM_SHARED_WRITE(endConstructEntry_startPtr->length, newLength); + endConstructEntry_startPtr.length = newLength; + } /* if (matched) */ + +// TM_END(); + } + + if (!endInfoEntries[(int)entryIndex].isEnd) { /* if there was a match */ break; } } /* iterate over chain */ } /* for (endIndex < numUniqueSegment) */ + + System.out.println("out of for2"); - thread_barrier_wait(); - +// thread_barrier_wait(); + Barrier.enterBarrier(); + /* * Step 2c: Update jump values and hashes * @@ -361,36 +445,36 @@ public class Sequencer { if (substringLength > 1) { long index = segmentLength - substringLength + 1; /* initialization if j and i: with i being the next end after j=0 */ - for (i = 1; !endInfoEntries[i].isEnd; i+=endInfoEntries[i].jumpToNext) { + for (i = 1; !endInfoEntries[(int)i].isEnd; i+=endInfoEntries[(int)i].jumpToNext) { /* find first non-null */ } /* entry 0 is handled seperately from the loop below */ endInfoEntries[0].jumpToNext = i; if (endInfoEntries[0].isEnd) { - constructEntry_t* constructEntryPtr = &constructEntries[0]; - char* segment = constructEntryPtr->segment; - constructEntryPtr->endHash = (ulong_t)hashString(&segment[index]); + String segment = constructEntries[0].segment; + constructEntries[0].endHash = hashString(segment.substring((int)index)); } /* Continue scanning (do not reset i) */ - for (j = 0; i < numUniqueSegment; i+=endInfoEntries[i].jumpToNext) { - if (endInfoEntries[i].isEnd) { - constructEntry_t* constructEntryPtr = &constructEntries[i]; - char* segment = constructEntryPtr->segment; - constructEntryPtr->endHash = (ulong_t)hashString(&segment[index]); - endInfoEntries[j].jumpToNext = MAX(1, (i - j)); + for (j = 0; i < numUniqueSegment; i+=endInfoEntries[(int)i].jumpToNext) { + if (endInfoEntries[(int)i].isEnd) { + String segment = constructEntries[(int)i].segment; + constructEntries[(int)i].endHash = hashString(segment.substring((int)index)); + endInfoEntries[(int)j].jumpToNext = Math.imax((int)1, (int)(i - j)); j = i; } } - endInfoEntries[j].jumpToNext = i - j; + endInfoEntries[(int)j].jumpToNext = i - j; } } - thread_barrier_wait(); +// thread_barrier_wait(); + Barrier.enterBarrier(); } /* for (substringLength > 0) */ - thread_barrier_wait(); +// thread_barrier_wait(); + Barrier.enterBarrier(); /* * Step 3: Build sequence string @@ -400,73 +484,45 @@ public class Sequencer { long totalLength = 0; for (i = 0; i < numUniqueSegment; i++) { - constructEntry_t* constructEntryPtr = &constructEntries[i]; - if (constructEntryPtr->isStart) { - totalLength += constructEntryPtr->length; + if (constructEntries[(int)i].isStart) { + totalLength += constructEntries[(int)i].length; } } - sequencerPtr->sequence = (char*)P_MALLOC((totalLength+1) * sizeof(char)); - char* sequence = sequencerPtr->sequence; - assert(sequence); + String sequence = sequencerPtr.sequence; - char* copyPtr = sequence; + String copyPtr = sequence; long sequenceLength = 0; for (i = 0; i < numUniqueSegment; i++) { - constructEntry_t* constructEntryPtr = &constructEntries[i]; /* If there are several start segments, we append in arbitrary order */ - if (constructEntryPtr->isStart) { - long newSequenceLength = sequenceLength + constructEntryPtr->length; - assert( newSequenceLength <= totalLength ); + constructEntry constructEntryPtr = constructEntries[(int)i]; + if (constructEntryPtr.isStart) { + long newSequenceLength = sequenceLength + constructEntries[(int)i].length; +// assert( newSequenceLength <= totalLength ); copyPtr = sequence + sequenceLength; sequenceLength = newSequenceLength; do { - long numChar = segmentLength - constructEntryPtr->overlap; - if ((copyPtr + numChar) > (sequence + newSequenceLength)) { - TM_PRINT0("ERROR: sequence length != actual length\n"); - break; - } - memcpy(copyPtr, - constructEntryPtr->segment, - (numChar * sizeof(char))); + long numChar = segmentLength - constructEntries[(int)i].overlap; +// if ((copyPtr + numChar) > (sequence + newSequenceLength)) { +// System.out.print("ERROR: sequence length != actual length\n"); +// break; +// } + copyPtr = constructEntries[(int)i].segment; copyPtr += numChar; - } while ((constructEntryPtr = constructEntryPtr->nextPtr) != NULL); - assert(copyPtr <= (sequence + sequenceLength)); + constructEntryPtr = constructEntryPtr.nextPtr; + } while (constructEntryPtr != null); +// assert(copyPtr <= (sequence + sequenceLength)); } } - assert(sequence != NULL); - sequence[sequenceLength] = '\0'; +// assert(sequence != NULL); } - TM_THREAD_EXIT(); +// TM_THREAD_EXIT(); } - - private class endInfoEntry { - boolean isEnd; - long jumpToNext; - } - - private class constructEntry { - boolean isStart; - String segment; - long endHash; - constructEntry startPtr; - constructEntry nextPtr; - constructEntry endPtr; - long overlap; - long length; - } - - private class sequencer_run_arg { - Sequencer sequencerPtr; - Segments segmentsPtr; - long preAllocLength; - String returnSequence; /* variable stores return value */ - } /* ============================================================================= * hashString * -- uses sdbm hash function @@ -475,36 +531,23 @@ public class Sequencer { static long hashString (String str) { long hash = 0; - long c; + int index = 0; /* Note: Do not change this hashing scheme */ - while ((c = str++) != '\0') { - hash = c + (hash << 6) + (hash << 16) - hash; + for(index = 0; index < str.length(); index++) { + char c = str.charAt(index); + hash = c + (hash << 6) + (hash << 16) - hash; } - return (long)hash; + return hash; } - /* ============================================================================= - * hashSegment - * -- For hashtable - * ============================================================================= - */ - static long hashSegment (string keyPtr) - { - return (long)hash_sdbm(keyPtr); /* can be any "good" hash function */ - } /* ============================================================================= * compareSegment * -- For hashtable * ============================================================================= - */ - static long compareSegment (pair_t* a, pair_t* b) - { - return strcmp((char*)(a->firstPtr), (char*)(b->firstPtr)); - } - + */ } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Sequencer.java~ b/Robust/src/Benchmarks/SingleTM/genome/java/Sequencer.java~ index b5895aac..86899c41 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Sequencer.java~ +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Sequencer.java~ @@ -1,11 +1,11 @@ public class Sequencer { - public char* sequence; + public String sequence; public Segments segmentsPtr; /* For removing duplicate segments */ - Hashmap uniqueSegmentsPtr; + HashMap uniqueSegmentsPtr; /* For matching segments */ endInfoEntry endInfoEntries[]; @@ -25,18 +25,18 @@ public class Sequencer { * ============================================================================= */ Sequencer (long myGeneLength, long mySegmentLength, Segments mySegmentsPtr) { - + long maxNumUniqueSegment = myGeneLength - mySegmentLength + 1; - long i; + int i; - uniqueSegmentsPtr = new Hashmap(myGeneLength); + uniqueSegmentsPtr = new HashMap((int)myGeneLength); /* For finding a matching entry */ endInfoEntries = new endInfoEntry[maxNumUniqueSegment]; for (i = 0; i < maxNumUniqueSegment; i++) { - endInfoEntries[i].isEnd = TRUE; - endInfoEntries[i].jumpToNext = 1; + endInfoEntries[i] = new endInfoEntry(true, 1); } + startHashToConstructEntryTables = new Table[mySegmentLength]; for (i = 1; i < mySegmentLength; i++) { /* 0 is dummy entry */ startHashToConstructEntryTables[i] = new Table(myGeneLength); @@ -44,22 +44,15 @@ public class Sequencer { segmentLength = mySegmentLength; /* For constructing sequence */ - constructEntries = new ContructEntry[maxNumUniqueSegment]; + constructEntries = new constructEntry[maxNumUniqueSegment]; for (i= 0; i < maxNumUniqueSegment; i++) { - constructEntries[i].isStart = TRUE; - constructEntries[i].segment = NULL; - constructEntries[i].endHash = 0; - constructEntries[i].startPtr = constructEntries[i]; - constructEntries[i].nextPtr = NULL; - constructEntries[i].endPtr = constructEntries[i]; - constructEntries[i].overlap = 0; - constructEntries[i].length = segmentLength; + constructEntries[i] = new constructEntry(null, true, 0, constructEntries[i], null, constructEntries[i], 0, segmentLength); } - hashToConstructEntryTable = new Table(geneLength); + hashToConstructEntryTable = new Table(myGeneLength); segmentsPtr = mySegmentsPtr; - } + } /* ============================================================================= @@ -67,19 +60,23 @@ public class Sequencer { * ============================================================================= */ - void run () { + public static void run (long threadNum, long numOfThreads, Random randomPtr, Sequencer sequencerPtr) { //TM_THREAD_ENTER(); - long threadId = thread_getId(); +// long threadId = thread_getId(); + + long threadId = threadNum; + + Segments segmentsPtr = sequencerPtr.segmentsPtr; //Sequencer sequencerPtr = (sequencer_t*)argPtr; - Hashmap uniqueSegmentsPtr; - endInfoEntry endInfoEntries[]; - Hashmap startHashToConstructEntryTables[]; - constructEntry constructEntries[]; - Hashmap hashToConstructEntryTable; + HashMap uniqueSegmentsPtr = sequencerPtr.uniqueSegmentsPtr; + endInfoEntry endInfoEntries[] = sequencerPtr.endInfoEntries; + Table startHashToConstructEntryTables[] = sequencerPtr.startHashToConstructEntryTables; + constructEntry constructEntries[] = sequencerPtr.constructEntries; + Table hashToConstructEntryTable = sequencerPtr.hashToConstructEntryTable; Vector segmentsContentsPtr = segmentsPtr.contentsPtr; long numSegment = segmentsContentsPtr.size(); @@ -92,12 +89,14 @@ public class Sequencer { long numUniqueSegment; long substringLength; long entryIndex; + + int CHUNK_STEP1 = 12; /* * Step 1: Remove duplicate segments */ -#if defined(HTM) || defined(STM) - long numThread = thread_getNumThread(); +//#if defined(HTM) || defined(STM) + long numThread = numOfThreads; { /* Choose disjoint segments [i_start,i_stop) for each thread */ long partitionSize = (numSegment + numThread/2) / numThread; /* with rounding */ @@ -108,27 +107,35 @@ public class Sequencer { i_stop = i_start + partitionSize; } } -#else /* !(HTM || STM) */ - i_start = 0; - i_stop = numSegment; -#endif /* !(HTM || STM) */ +//#else /* !(HTM || STM) */ +// i_start = 0; +// i_stop = numSegment; +//#endif /* !(HTM || STM) */ for (i = i_start; i < i_stop; i+=CHUNK_STEP1) { - TM_BEGIN(); - { +// TM_BEGIN(); + atomic { long ii; - long ii_stop = MIN(i_stop, (i+CHUNK_STEP1)); + long ii_stop = Math.imin((int)i_stop, (int)(i+CHUNK_STEP1)); for (ii = i; ii < ii_stop; ii++) { - void* segment = vector_at(segmentsContentsPtr, ii); - TMHASHTABLE_INSERT(uniqueSegmentsPtr, - segment, - segment); + String segment = (String)segmentsContentsPtr.elementAt((int)ii); +// TMHASHTABLE_INSERT(uniqueSegmentsPtr, segment, segment); + System.out.print("Placing: " + segment + " into uniqueSegmentsPtr..."); + if(uniqueSegmentsPtr.put(segment, segment) == null) { + System.out.println("success!"); + } else { + System.out.println("fail, double entry."); + } } /* ii */ } - TM_END(); +// TM_END(); } - thread_barrier_wait(); - +// thread_barrier_wait(); + Barrier.enterBarrier(); + + + + /* * Step 2a: Iterate over unique segments and compute hashes. * @@ -150,13 +157,14 @@ public class Sequencer { */ /* uniqueSegmentsPtr is constant now */ - numUniqueSegment = hashtable_getSize(uniqueSegmentsPtr); + numUniqueSegment = uniqueSegmentsPtr.size(); entryIndex = 0; -#if defined(HTM) || defined(STM) +//#if defined(HTM) || defined(STM) { /* Choose disjoint segments [i_start,i_stop) for each thread */ - long num = uniqueSegmentsPtr->numBucket; + long num = uniqueSegmentsPtr.size(); + System.out.println("num: " + num); long partitionSize = (num + numThread/2) / numThread; /* with rounding */ i_start = threadId * partitionSize; if (threadId == (numThread - 1)) { @@ -165,97 +173,147 @@ public class Sequencer { i_stop = i_start + partitionSize; } } + { /* Approximate disjoint segments of element allocation in constructEntries */ long partitionSize = (numUniqueSegment + numThread/2) / numThread; /* with rounding */ entryIndex = threadId * partitionSize; } -#else /* !(HTM || STM) */ - i_start = 0; - i_stop = uniqueSegmentsPtr->numBucket; - entryIndex = 0; -#endif /* !(HTM || STM) */ +//#else /* !(HTM || STM) */ +// i_start = 0; +// i_stop = uniqueSegmentsPtr.size(); +// entryIndex = 0; +//#endif /* !(HTM || STM) */ + + String uniqueArray[] = new String[uniqueSegmentsPtr.size()]; + int ind = 0; + HashMapIterator iterarian = uniqueSegmentsPtr.iterator(1); + String roar; + System.out.println("uniqueSegmentsPtr contents: "); + while(iterarian.hasNext()) { + roar = (String)iterarian.next(); + uniqueArray[ind++] = roar; + System.out.println(" " + roar); + } + + i_stop = Math.imin(ind, (int)i_stop); for (i = i_start; i < i_stop; i++) { + String segment = uniqueArray[(int)i]; + System.out.println("segment[" + i + "]: " + segment); + // list_iter_t it; + // list_iter_reset(&it, chainPtr); - list_t* chainPtr = uniqueSegmentsPtr->buckets[i]; - list_iter_t it; - list_iter_reset(&it, chainPtr); + // while (list_iter_hasNext(&it, chainPtr)) { - while (list_iter_hasNext(&it, chainPtr)) { + // char* segment = (char*)((pair_t*)list_iter_next(&it, chainPtr))->firstPtr; - char* segment = - (char*)((pair_t*)list_iter_next(&it, chainPtr))->firstPtr; - constructEntry_t* constructEntryPtr; - long j; - ulong_t startHash; - bool_t status; + long newj; + long startHash; + boolean status; + + /* Find an empty constructEntries entry */ + atomic { +// TM_BEGIN(); +// while (((void*)TM_SHARED_READ_P(constructEntries[entryIndex].segment)) != NULL) { + while(constructEntries[(int)entryIndex].segment != null) { + entryIndex = (entryIndex + 1) % numUniqueSegment; /* look for empty */ + } +// constructEntryPtr = &constructEntries[entryIndex]; +// TM_SHARED_WRITE_P(constructEntryPtr->segment, segment); + constructEntries[(int)entryIndex].segment = segment; + System.out.println("constructEntries[" + entryIndex + "]: " + constructEntries[(int)entryIndex].segment); +// TM_END(); + } + + constructEntry constructEntryPtr = constructEntries[(int)entryIndex]; + + entryIndex = (entryIndex + 1) % numUniqueSegment; + + + + /* + * Save hashes (sdbm algorithm) of segment substrings + * + * endHashes will be computed for shorter substrings after matches + * have been made (in the next phase of the code). This will reduce + * the number of substrings for which hashes need to be computed. + * + * Since we can compute startHashes incrementally, we go ahead + * and compute all of them here. + */ + /* constructEntryPtr is local now */ + constructEntryPtr.endHash = hashString(segment.substring(1)); + + System.out.println("constructEntryPtr.segment: " + constructEntryPtr.segment); + System.out.println("constructentryPtr.hash: " + constructEntryPtr.endHash); + + startHash = 0; + for (newj = 1; newj < segmentLength; newj++) { + startHash = segment.charAt((int)newj-1) + (startHash << 6) + (startHash << 16) - startHash; + atomic { +// TM_BEGIN(); +// status = TMTABLE_INSERT(startHashToConstructEntryTables[j], (ulong_t)startHash, (void*)constructEntryPtr ); + System.out.println("BEFORE INSERTION INTO TABLE"); + System.out.println("constructEntryPtr.segment: " + constructEntryPtr.segment); + System.out.println("constructentryPtr.hash: " + constructEntryPtr.endHash); + + boolean check = startHashToConstructEntryTables[(int)newj].table_insert(startHash, constructEntryPtr); + System.out.println("check: " + check); +// TM_END(); + } +// assert(status); + } + + System.out.println("AFTER INSERTION INTO TABLE"); + System.out.println("constructEntryPtr.segment: " + constructEntryPtr.segment); + System.out.println("constructentryPtr.hash: " + constructEntryPtr.endHash); - /* Find an empty constructEntries entry */ - TM_BEGIN(); - while (((void*)TM_SHARED_READ_P(constructEntries[entryIndex].segment)) != NULL) { - entryIndex = (entryIndex + 1) % numUniqueSegment; /* look for empty */ - } - constructEntryPtr = &constructEntries[entryIndex]; - TM_SHARED_WRITE_P(constructEntryPtr->segment, segment); - TM_END(); - entryIndex = (entryIndex + 1) % numUniqueSegment; - - /* - * Save hashes (sdbm algorithm) of segment substrings - * - * endHashes will be computed for shorter substrings after matches - * have been made (in the next phase of the code). This will reduce - * the number of substrings for which hashes need to be computed. - * - * Since we can compute startHashes incrementally, we go ahead - * and compute all of them here. - */ - /* constructEntryPtr is local now */ - constructEntryPtr->endHash = (ulong_t)hashString(&segment[1]); - - startHash = 0; - for (j = 1; j < segmentLength; j++) { - startHash = (ulong_t)segment[j-1] + - (startHash << 6) + (startHash << 16) - startHash; - TM_BEGIN(); - status = TMTABLE_INSERT(startHashToConstructEntryTables[j], - (ulong_t)startHash, - (void*)constructEntryPtr ); - TM_END(); - assert(status); - } - /* - * For looking up construct entries quickly - */ - startHash = (ulong_t)segment[j-1] + - (startHash << 6) + (startHash << 16) - startHash; - TM_BEGIN(); - status = TMTABLE_INSERT(hashToConstructEntryTable, - (ulong_t)startHash, - (void*)constructEntryPtr); - TM_END(); - assert(status); + int tempi; + for(tempi = 0; tempi < 4; tempi++) { + System.out.println("centries[" + tempi + "]: " + constructEntries[tempi].segment); + } + + /* + * For looking up construct entries quickly + */ + startHash = segment.charAt((int)newj-1) + (startHash << 6) + (startHash << 16) - startHash; + atomic { +// TM_BEGIN(); +// status = TMTABLE_INSERT(hashToConstructEntryTable, (ulong_t)startHash, (void*)constructEntryPtr); + hashToConstructEntryTable.table_insert(startHash, constructEntryPtr); +// TM_END(); } +// assert(status); + } + + int tempi; + for(tempi = 0; tempi < 4; tempi++) { + System.out.println("centries[" + tempi + "]: " + constructEntries[tempi].segment); + } + + System.out.println("out of for"); - thread_barrier_wait(); - +// thread_barrier_wait(); + Barrier.enterBarrier(); + /* * Step 2b: Match ends to starts by using hash-based string comparison. */ for (substringLength = segmentLength-1; substringLength > 0; substringLength--) { - table_t* startHashToConstructEntryTablePtr = - startHashToConstructEntryTables[substringLength]; - list_t** buckets = startHashToConstructEntryTablePtr->buckets; - long numBucket = startHashToConstructEntryTablePtr->numBucket; + Table startHashToConstructEntryTablePtr = startHashToConstructEntryTables[(int)substringLength]; + LinkedList buckets[] = startHashToConstructEntryTablePtr.buckets; + long numBucket = startHashToConstructEntryTablePtr.numBucket; + + System.out.println("Retrieved the buckets."); long index_start; long index_stop; -#if defined(HTM) || defined(STM) +//#if defined(HTM) || defined(STM) { /* Choose disjoint segments [index_start,index_stop) for each thread */ long partitionSize = (numUniqueSegment + numThread/2) / numThread; /* with rounding */ @@ -266,88 +324,109 @@ public class Sequencer { index_stop = index_start + partitionSize; } } -#else /* !(HTM || STM) */ - index_start = 0; - index_stop = numUniqueSegment; -#endif /* !(HTM || STM) */ +//#else /* !(HTM || STM) */ +// index_start = 0; +// index_stop = numUniqueSegment; +//#endif /* !(HTM || STM) */ + + index_stop = Math.imin(ind, (int)index_stop); + + System.out.println("index_start: " + index_start); + System.out.println("index_stop: " + index_stop); + + System.out.println("endSegment: " + constructEntries[(int)index_start].segment); /* Iterating over disjoint itervals in the range [0, numUniqueSegment) */ for (entryIndex = index_start; entryIndex < index_stop; - entryIndex += endInfoEntries[entryIndex].jumpToNext) + entryIndex += endInfoEntries[(int)entryIndex].jumpToNext) { - if (!endInfoEntries[entryIndex].isEnd) { + if (!endInfoEntries[(int)entryIndex].isEnd) { continue; } /* ConstructEntries[entryIndex] is local data */ - constructEntry_t* endConstructEntryPtr = - &constructEntries[entryIndex]; - char* endSegment = endConstructEntryPtr->segment; - ulong_t endHash = endConstructEntryPtr->endHash; - - list_t* chainPtr = buckets[endHash % numBucket]; /* buckets: constant data */ - list_iter_t it; - list_iter_reset(&it, chainPtr); + constructEntry endConstructEntryPtr = constructEntries[(int)entryIndex]; + System.out.println("Retrieved constructEntry[" + entryIndex + "]."); + String endSegment = endConstructEntryPtr.segment; + System.out.println("pyah."); + System.out.println("endSegment: " + constructEntries[(int)entryIndex].segment); + long endHash = endConstructEntryPtr.endHash; + System.out.println("endHash: " + endHash); + + LinkedList chainPtr = buckets[(int)(endHash % numBucket)]; /* buckets: constant data */ + LinkedListIterator it = (LinkedListIterator)chainPtr.iterator(); +// list_iter_reset(&it, chainPtr); /* Linked list at chainPtr is constant */ - while (list_iter_hasNext(&it, chainPtr)) { + while (it.hasNext()) { - constructEntry_t* startConstructEntryPtr = - (constructEntry_t*)list_iter_next(&it, chainPtr); - char* startSegment = startConstructEntryPtr->segment; + constructEntry startConstructEntryPtr = (constructEntry)it.next(); + String startSegment = startConstructEntryPtr.segment; long newLength = 0; /* endConstructEntryPtr is local except for properties startPtr/endPtr/length */ - TM_BEGIN(); + atomic { +// TM_BEGIN(); /* Check if matches */ - if (TM_SHARED_READ(startConstructEntryPtr->isStart) && - (TM_SHARED_READ_P(endConstructEntryPtr->startPtr) != startConstructEntryPtr) && - (strncmp(startSegment, - &endSegment[segmentLength - substringLength], - substringLength) == 0)) - { - TM_SHARED_WRITE(startConstructEntryPtr->isStart, FALSE); - - constructEntry_t* startConstructEntry_endPtr; - constructEntry_t* endConstructEntry_startPtr; +// if (TM_SHARED_READ(startConstructEntryPtr->isStart) && +// (TM_SHARED_READ_P(endConstructEntryPtr->startPtr) != startConstructEntryPtr) && +// (strncmp(startSegment, +// &endSegment[segmentLength - substringLength], +// substringLength) == 0)) + if(startConstructEntryPtr.isStart && + (endConstructEntryPtr.startPtr != startConstructEntryPtr) && + (startSegment != endSegment.substring((int)(segmentLength-substringLength), (int)substringLength))) + { +// TM_SHARED_WRITE(startConstructEntryPtr->isStart, FALSE); + startConstructEntryPtr.isStart = false; + + constructEntry startConstructEntry_endPtr; + constructEntry endConstructEntry_startPtr; /* Update endInfo (appended something so no longer end) */ - TM_LOCAL_WRITE(endInfoEntries[entryIndex].isEnd, FALSE); +// TM_LOCAL_WRITE(endInfoEntries[entryIndex].isEnd, FALSE); + endInfoEntries[(int)entryIndex].isEnd = false; /* Update segment chain construct info */ - startConstructEntry_endPtr = - (constructEntry_t*)TM_SHARED_READ_P(startConstructEntryPtr->endPtr); - endConstructEntry_startPtr = - (constructEntry_t*)TM_SHARED_READ_P(endConstructEntryPtr->startPtr); - - assert(startConstructEntry_endPtr); - assert(endConstructEntry_startPtr); - TM_SHARED_WRITE_P(startConstructEntry_endPtr->startPtr, - endConstructEntry_startPtr); - TM_LOCAL_WRITE_P(endConstructEntryPtr->nextPtr, - startConstructEntryPtr); - TM_SHARED_WRITE_P(endConstructEntry_startPtr->endPtr, - startConstructEntry_endPtr); - TM_SHARED_WRITE(endConstructEntryPtr->overlap, substringLength); - newLength = (long)TM_SHARED_READ(endConstructEntry_startPtr->length) + - (long)TM_SHARED_READ(startConstructEntryPtr->length) - - substringLength; - TM_SHARED_WRITE(endConstructEntry_startPtr->length, newLength); - } /* if (matched) */ - - TM_END(); - - if (!endInfoEntries[entryIndex].isEnd) { /* if there was a match */ +// startConstructEntry_endPtr = (constructEntry_t*)TM_SHARED_READ_P(startConstructEntryPtr->endPtr); + startConstructEntry_endPtr = startConstructEntryPtr.endPtr; +// endConstructEntry_startPtr = (constructEntry_t*)TM_SHARED_READ_P(endConstructEntryPtr->startPtr); + endConstructEntry_startPtr = endConstructEntryPtr.startPtr; + +// assert(startConstructEntry_endPtr); +// assert(endConstructEntry_startPtr); + + +// TM_SHARED_WRITE_P(startConstructEntry_endPtr->startPtr, endConstructEntry_startPtr); + startConstructEntry_endPtr.startPtr = endConstructEntry_startPtr; +// TM_LOCAL_WRITE_P(endConstructEntryPtr->nextPtr, startConstructEntryPtr); + endConstructEntryPtr.nextPtr = startConstructEntryPtr; +// TM_SHARED_WRITE_P(endConstructEntry_startPtr->endPtr, startConstructEntry_endPtr); + endConstructEntry_startPtr.endPtr = startConstructEntry_endPtr; +// TM_SHARED_WRITE(endConstructEntryPtr->overlap, substringLength); + endConstructEntryPtr.overlap = substringLength; + newLength = endConstructEntry_startPtr.length + startConstructEntryPtr.length - substringLength; +// TM_SHARED_WRITE(endConstructEntry_startPtr->length, newLength); + endConstructEntry_startPtr.length = newLength; + } /* if (matched) */ + +// TM_END(); + } + + if (!endInfoEntries[(int)entryIndex].isEnd) { /* if there was a match */ break; } } /* iterate over chain */ } /* for (endIndex < numUniqueSegment) */ + + System.out.println("out of for2"); - thread_barrier_wait(); - +// thread_barrier_wait(); + Barrier.enterBarrier(); + /* * Step 2c: Update jump values and hashes * @@ -361,36 +440,36 @@ public class Sequencer { if (substringLength > 1) { long index = segmentLength - substringLength + 1; /* initialization if j and i: with i being the next end after j=0 */ - for (i = 1; !endInfoEntries[i].isEnd; i+=endInfoEntries[i].jumpToNext) { + for (i = 1; !endInfoEntries[(int)i].isEnd; i+=endInfoEntries[(int)i].jumpToNext) { /* find first non-null */ } /* entry 0 is handled seperately from the loop below */ endInfoEntries[0].jumpToNext = i; if (endInfoEntries[0].isEnd) { - constructEntry_t* constructEntryPtr = &constructEntries[0]; - char* segment = constructEntryPtr->segment; - constructEntryPtr->endHash = (ulong_t)hashString(&segment[index]); + String segment = constructEntries[0].segment; + constructEntries[0].endHash = hashString(segment.substring((int)index)); } /* Continue scanning (do not reset i) */ - for (j = 0; i < numUniqueSegment; i+=endInfoEntries[i].jumpToNext) { - if (endInfoEntries[i].isEnd) { - constructEntry_t* constructEntryPtr = &constructEntries[i]; - char* segment = constructEntryPtr->segment; - constructEntryPtr->endHash = (ulong_t)hashString(&segment[index]); - endInfoEntries[j].jumpToNext = MAX(1, (i - j)); + for (j = 0; i < numUniqueSegment; i+=endInfoEntries[(int)i].jumpToNext) { + if (endInfoEntries[(int)i].isEnd) { + String segment = constructEntries[(int)i].segment; + constructEntries[(int)i].endHash = hashString(segment.substring((int)index)); + endInfoEntries[(int)j].jumpToNext = Math.imax((int)1, (int)(i - j)); j = i; } } - endInfoEntries[j].jumpToNext = i - j; + endInfoEntries[(int)j].jumpToNext = i - j; } } - thread_barrier_wait(); +// thread_barrier_wait(); + Barrier.enterBarrier(); } /* for (substringLength > 0) */ - thread_barrier_wait(); +// thread_barrier_wait(); + Barrier.enterBarrier(); /* * Step 3: Build sequence string @@ -400,73 +479,45 @@ public class Sequencer { long totalLength = 0; for (i = 0; i < numUniqueSegment; i++) { - constructEntry_t* constructEntryPtr = &constructEntries[i]; - if (constructEntryPtr->isStart) { - totalLength += constructEntryPtr->length; + if (constructEntries[(int)i].isStart) { + totalLength += constructEntries[(int)i].length; } } - sequencerPtr->sequence = (char*)P_MALLOC((totalLength+1) * sizeof(char)); - char* sequence = sequencerPtr->sequence; - assert(sequence); + String sequence = sequencerPtr.sequence; - char* copyPtr = sequence; + String copyPtr = sequence; long sequenceLength = 0; for (i = 0; i < numUniqueSegment; i++) { - constructEntry_t* constructEntryPtr = &constructEntries[i]; /* If there are several start segments, we append in arbitrary order */ - if (constructEntryPtr->isStart) { - long newSequenceLength = sequenceLength + constructEntryPtr->length; - assert( newSequenceLength <= totalLength ); + constructEntry constructEntryPtr = constructEntries[(int)i]; + if (constructEntryPtr.isStart) { + long newSequenceLength = sequenceLength + constructEntries[(int)i].length; +// assert( newSequenceLength <= totalLength ); copyPtr = sequence + sequenceLength; sequenceLength = newSequenceLength; do { - long numChar = segmentLength - constructEntryPtr->overlap; - if ((copyPtr + numChar) > (sequence + newSequenceLength)) { - TM_PRINT0("ERROR: sequence length != actual length\n"); - break; - } - memcpy(copyPtr, - constructEntryPtr->segment, - (numChar * sizeof(char))); + long numChar = segmentLength - constructEntries[(int)i].overlap; +// if ((copyPtr + numChar) > (sequence + newSequenceLength)) { +// System.out.print("ERROR: sequence length != actual length\n"); +// break; +// } + copyPtr = constructEntries[(int)i].segment; copyPtr += numChar; - } while ((constructEntryPtr = constructEntryPtr->nextPtr) != NULL); - assert(copyPtr <= (sequence + sequenceLength)); + constructEntryPtr = constructEntryPtr.nextPtr; + } while (constructEntryPtr != null); +// assert(copyPtr <= (sequence + sequenceLength)); } } - assert(sequence != NULL); - sequence[sequenceLength] = '\0'; +// assert(sequence != NULL); } - TM_THREAD_EXIT(); - - } - - - private class endInfoEntry { - boolean isEnd; - long jumpToNext; - } +// TM_THREAD_EXIT(); - private class constructEntry { - boolean isStart; - String segment; - long endHash; - constructEntry startPtr; - constructEntry nextPtr; - constructEntry endPtr; - long overlap; - long length; } - private class sequencer_run_arg { - Sequencer sequencerPtr; - Segments segmentsPtr; - long preAllocLength; - String returnSequence; /* variable stores return value */ - } /* ============================================================================= * hashString * -- uses sdbm hash function @@ -475,36 +526,23 @@ public class Sequencer { static long hashString (String str) { long hash = 0; - long c; + int index = 0; /* Note: Do not change this hashing scheme */ - while ((c = str++) != '\0') { - hash = c + (hash << 6) + (hash << 16) - hash; + for(index = 0; index < str.length(); index++) { + char c = str.charAt(index); + hash = c + (hash << 6) + (hash << 16) - hash; } - return (long)hash; + return hash; } - /* ============================================================================= - * hashSegment - * -- For hashtable - * ============================================================================= - */ - static long hashSegment (string keyPtr) - { - return (long)hash_sdbm(keyPtr); /* can be any "good" hash function */ - } /* ============================================================================= * compareSegment * -- For hashtable * ============================================================================= - */ - static long compareSegment (pair_t* a, pair_t* b) - { - return strcmp((char*)(a->firstPtr), (char*)(b->firstPtr)); - } - + */ } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Table.java b/Robust/src/Benchmarks/SingleTM/genome/java/Table.java index 83893a87..42c7e536 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Table.java +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Table.java @@ -11,9 +11,12 @@ public class Table { */ Table (long myNumBucket) { - long i; + int i; buckets = new LinkedList[myNumBucket]; + for(i = 0; i < myNumBucket; i++) { + buckets[i] = new LinkedList(); + } numBucket = myNumBucket; @@ -25,16 +28,15 @@ public class Table { * -- Returns TRUE if successful, else FALSE * ============================================================================= */ - boolean table_insert (long hash, void* dataPtr) { - long i = hash % numBucket; - - if(buckets[i].indexOf(dataPtr) != -1) { - return FALSE; + boolean table_insert (long hash, Object dataPtr) { + System.out.println("Inside insert- hash: " + hash); + System.out.println("Inside insert- dataPtr: " + ((constructEntry)(dataPtr)).segment); + int i = (int)(hash % numBucket); + if(buckets[i].contains(dataPtr)) { + return false; } - buckets[i].add(dataPtr); - - return TRUE; + return true; } /* ============================================================================= @@ -42,15 +44,16 @@ public class Table { * -- Returns TRUE if successful, else FALSE * ============================================================================= */ - boolean table_remove (long hash, void* dataPtr) { + boolean table_remove (long hash, Object dataPtr) { - long i = hash % numBucket; - - if (!buckets[i].remove(dataPtr) { - return FALSE; + int i = (int)(hash % numBucket); + boolean tempbool = buckets[i].contains(dataPtr); + if (tempbool) { + buckets[i].remove(dataPtr); + return true; } - return TRUE; + return false; } diff --git a/Robust/src/Benchmarks/SingleTM/genome/java/Table.java~ b/Robust/src/Benchmarks/SingleTM/genome/java/Table.java~ index 28b2ed5f..3bafd74d 100644 --- a/Robust/src/Benchmarks/SingleTM/genome/java/Table.java~ +++ b/Robust/src/Benchmarks/SingleTM/genome/java/Table.java~ @@ -11,9 +11,12 @@ public class Table { */ Table (long myNumBucket) { - long i; + int i; buckets = new LinkedList[myNumBucket]; + for(i = 0; i < myNumBucket; i++) { + buckets[i] = new LinkedList(); + } numBucket = myNumBucket; @@ -25,16 +28,15 @@ public class Table { * -- Returns TRUE if successful, else FALSE * ============================================================================= */ - boolean table_insert (long hash, void* dataPtr) { - long i = hash % numBucket; - - if(buckets[i].indexOf(dataPtr) != -1) { - return FALSE; + boolean table_insert (long hash, Object dataPtr) { + System.out.println("Inside insert- hash: " + hash); + System.out.println("Inside insert- dataPtr: " + dataPtr); + int i = (int)(hash % numBucket); + if(buckets[i].contains(dataPtr)) { + return false; } - buckets[i].add(dataPtr); - - return TRUE; + return true; } /* ============================================================================= @@ -42,15 +44,16 @@ public class Table { * -- Returns TRUE if successful, else FALSE * ============================================================================= */ - boolean table_remove (long hash, void* dataPtr) { + boolean table_remove (long hash, Object dataPtr) { - long i = hash % numBucket; - - if (!list_remove(tablePtr->buckets[i], dataPtr)) { - return FALSE; + int i = (int)(hash % numBucket); + boolean tempbool = buckets[i].contains(dataPtr); + if (tempbool) { + buckets[i].remove(dataPtr); + return true; } - return TRUE; + return false; } -- 2.34.1