From b4bdecb4a7ce30e3eb60f8ad0b233193ff6863c7 Mon Sep 17 00:00:00 2001 From: adash Date: Fri, 12 Jun 2009 01:17:44 +0000 Subject: [PATCH] new changes to common library files and bug fixes to Genome(still uses hashtable and Strings) --- .../Benchmarks/SingleTM/Genome/Sequencer.java | 195 +++++++++--------- .../src/Benchmarks/SingleTM/Genome/makefile | 2 +- Robust/src/Benchmarks/SingleTM/SSCA2/makefile | 2 +- .../Benchmarks/SingleTM/common/BitMap.java | 83 ++++---- .../src/Benchmarks/SingleTM/common/Queue.java | 49 +++-- .../Benchmarks/SingleTM/common/Vector_t.java | 8 +- 6 files changed, 171 insertions(+), 168 deletions(-) diff --git a/Robust/src/Benchmarks/SingleTM/Genome/Sequencer.java b/Robust/src/Benchmarks/SingleTM/Genome/Sequencer.java index 65407344..2fb7f834 100644 --- a/Robust/src/Benchmarks/SingleTM/Genome/Sequencer.java +++ b/Robust/src/Benchmarks/SingleTM/Genome/Sequencer.java @@ -228,112 +228,113 @@ public class Sequencer { int numBucket = startHashToConstructEntryTablePtr.numBucket; int index_start; - int index_stop; - - { - /* Choose disjoint segments [index_start,index_stop) for each thread */ - int partitionSize = (numUniqueSegment + numThread/2) / numThread; /* with rounding */ - index_start = threadId * partitionSize; - if (threadId == (numThread - 1)) { - index_stop = numUniqueSegment; - } else { - index_stop = index_start + partitionSize; - } + int index_stop; + + { + /* Choose disjoint segments [index_start,index_stop) for each thread */ + int partitionSize = (numUniqueSegment + numThread/2) / numThread; /* with rounding */ + index_start = threadId * partitionSize; + if (threadId == (numThread - 1)) { + index_stop = numUniqueSegment; + } else { + index_stop = index_start + partitionSize; } + } - /* Iterating over disjoint itervals in the range [0, numUniqueSegment) */ - for (entryIndex = index_start; - entryIndex < index_stop; - entryIndex += endInfoEntries[entryIndex].jumpToNext) - { - if (!endInfoEntries[entryIndex].isEnd) { - continue; - } - - /* ConstructEntries[entryIndex] is local data */ - constructEntry endConstructEntryPtr = constructEntries[entryIndex]; - String endSegment = endConstructEntryPtr.segment; - int endHash = endConstructEntryPtr.endHash; - - LinkedList chainPtr = buckets[(endHash % numBucket)]; /* buckets: constant data */ - LinkedListIterator it = (LinkedListIterator)chainPtr.iterator(); - while (it.hasNext()) { - constructEntry startConstructEntryPtr = (constructEntry)it.next(); - String startSegment = startConstructEntryPtr.segment; - int newLength = 0; - - /* endConstructEntryPtr is local except for properties startPtr/endPtr/length */ - atomic { - if(startConstructEntryPtr.isStart && - (endConstructEntryPtr.startPtr != startConstructEntryPtr) && - (startSegment.substring(0, (int)substringLength).compareTo(endSegment.substring((int)(segmentLength-substringLength))) == 0)) - { - startConstructEntryPtr.isStart = false; - constructEntry startConstructEntry_endPtr; - constructEntry endConstructEntry_startPtr; - - /* Update endInfo (appended something so no inter end) */ - endInfoEntries[entryIndex].isEnd = false; - /* Update segment chain construct info */ - startConstructEntry_endPtr = startConstructEntryPtr.endPtr; - endConstructEntry_startPtr = endConstructEntryPtr.startPtr; - startConstructEntry_endPtr.startPtr = endConstructEntry_startPtr; - endConstructEntryPtr.nextPtr = startConstructEntryPtr; - endConstructEntry_startPtr.endPtr = startConstructEntry_endPtr; - endConstructEntryPtr.overlap = substringLength; - newLength = endConstructEntry_startPtr.length + startConstructEntryPtr.length - substringLength; - endConstructEntry_startPtr.length = newLength; - } else {/* if (matched) */ - } - } - - if (!endInfoEntries[entryIndex].isEnd) { /* if there was a match */ - break; - } - } /* iterate over chain */ - - } /* for (endIndex < numUniqueSegment) */ + /* Iterating over disjoint itervals in the range [0, numUniqueSegment) */ + for (entryIndex = index_start; + entryIndex < index_stop; + entryIndex += endInfoEntries[entryIndex].jumpToNext) + { + if (!endInfoEntries[entryIndex].isEnd) { + continue; + } - Barrier.enterBarrier(); + /* ConstructEntries[entryIndex] is local data */ + constructEntry endConstructEntryPtr = constructEntries[entryIndex]; + String endSegment = endConstructEntryPtr.segment; + int endHash = endConstructEntryPtr.endHash; - /* - * Step 2c: Update jump values and hashes - * - * endHash entries of all remaining ends are updated to the next - * substringLength. Additionally jumpToNext entries are updated such - * that they allow to skip non-end entries. Currently this is sequential - * because parallelization did not perform better. - */ + LinkedList chainPtr = buckets[(endHash % numBucket)]; /* buckets: constant data */ + LinkedListIterator it = (LinkedListIterator)chainPtr.iterator(); + while (it.hasNext()) { + constructEntry startConstructEntryPtr = (constructEntry)it.next(); + String startSegment = startConstructEntryPtr.segment; + int newLength = 0; - if (threadId == 0) { - if (substringLength > 1) { - int 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) { - /* find first non-null */ - ; - } - /* entry 0 is handled seperately from the loop below */ - endInfoEntries[0].jumpToNext = i; - if (endInfoEntries[0].isEnd) { - String segment = constructEntries[0].segment; - constructEntries[0].endHash = hashString(segment.subString((int)index)); // USE BYTE SUBSTRING FUNCTION + /* endConstructEntryPtr is local except for properties startPtr/endPtr/length */ + atomic { + if(startConstructEntryPtr.isStart && + (endConstructEntryPtr.startPtr != startConstructEntryPtr) && + (startSegment.substring(0, (int)substringLength).compareTo(endSegment.substring((int)(segmentLength-substringLength))) == 0)) + { + startConstructEntryPtr.isStart = false; + constructEntry startConstructEntry_endPtr; + constructEntry endConstructEntry_startPtr; + + /* Update endInfo (appended something so no inter end) */ + endInfoEntries[entryIndex].isEnd = false; + /* Update segment chain construct info */ + startConstructEntry_endPtr = startConstructEntryPtr.endPtr; + endConstructEntry_startPtr = endConstructEntryPtr.startPtr; + startConstructEntry_endPtr.startPtr = endConstructEntry_startPtr; + endConstructEntryPtr.nextPtr = startConstructEntryPtr; + endConstructEntry_startPtr.endPtr = startConstructEntry_endPtr; + endConstructEntryPtr.overlap = substringLength; + newLength = endConstructEntry_startPtr.length + startConstructEntryPtr.length - substringLength; + endConstructEntry_startPtr.length = newLength; + } else {/* if (matched) */ } - /* Continue scanning (do not reset i) */ - for (j = 0; i < numUniqueSegment; i+=endInfoEntries[i].jumpToNext) { - - if (endInfoEntries[i].isEnd) { - String segment = constructEntries[i].segment; - constructEntries[i].endHash = hashString(segment.substring((int)index)); // USE BYTE SUBSTRING FUNCTION - endInfoEntries[j].jumpToNext = Math.imax((int)1, (int)(i - j)); - j = i; - } + } + + if (!endInfoEntries[entryIndex].isEnd) { /* if there was a match */ + break; + } + } /* iterate over chain */ + + } /* for (endIndex < numUniqueSegment) */ + + Barrier.enterBarrier(); + + /* + * Step 2c: Update jump values and hashes + * + * endHash entries of all remaining ends are updated to the next + * substringLength. Additionally jumpToNext entries are updated such + * that they allow to skip non-end entries. Currently this is sequential + * because parallelization did not perform better. + */ + + if (threadId == 0) { + if (substringLength > 1) { + int 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) { + /* find first non-null */ + ; + } + /* entry 0 is handled seperately from the loop below */ + endInfoEntries[0].jumpToNext = i; + if (endInfoEntries[0].isEnd) { + String segment = constructEntries[0].segment; + constructEntries[0].endHash = hashString(segment.subString((int)index)); // USE BYTE SUBSTRING FUNCTION + } + /* Continue scanning (do not reset i) */ + for (j = 0; i < numUniqueSegment; i+=endInfoEntries[i].jumpToNext) { + + if (endInfoEntries[i].isEnd) { + String segment = constructEntries[i].segment; + constructEntries[i].endHash = hashString(segment.substring((int)index)); // USE BYTE SUBSTRING FUNCTION + endInfoEntries[j].jumpToNext = Math.imax((int)1, (int)(i - j)); + j = i; } - endInfoEntries[j].jumpToNext = i - j; } + endInfoEntries[j].jumpToNext = i - j; } + } + - Barrier.enterBarrier(); + Barrier.enterBarrier(); } /* for (substringLength > 0) */ @@ -382,7 +383,7 @@ public class Sequencer { * -- uses sdbm hash function * ============================================================================= */ - static int hashString (String str) + static int hashString (String str) { int hash = 0; diff --git a/Robust/src/Benchmarks/SingleTM/Genome/makefile b/Robust/src/Benchmarks/SingleTM/Genome/makefile index 8f1f2e0f..d18720dd 100644 --- a/Robust/src/Benchmarks/SingleTM/Genome/makefile +++ b/Robust/src/Benchmarks/SingleTM/Genome/makefile @@ -10,7 +10,7 @@ SRC=${MAINCLASS}.java \ Sequencer.java \ Table.java \ Hashtable.java -FLAGS=-mainclass ${MAINCLASS} -singleTM -optimize -dcopts -abcclose -fastmemcpy -joptimize +FLAGS=-mainclass ${MAINCLASS} -singleTM -optimize -debug -fastmemcpy -abcclose -dcopts -joptimize default: ../../../buildscript ${FLAGS} -o ${MAINCLASS} ${SRC} diff --git a/Robust/src/Benchmarks/SingleTM/SSCA2/makefile b/Robust/src/Benchmarks/SingleTM/SSCA2/makefile index f2997895..b01d83e1 100644 --- a/Robust/src/Benchmarks/SingleTM/SSCA2/makefile +++ b/Robust/src/Benchmarks/SingleTM/SSCA2/makefile @@ -14,7 +14,7 @@ SRC=tmp${MAINCLASS}.java \ VList.java \ ../common/Random.java \ ../../../ClassLibrary/JavaSTM/Barrier.java -FLAGS=-mainclass ${MAINCLASS} -singleTM -optimize -debug -dcopts -stmstats -fastmemcpy -transstats -joptimize +FLAGS=-mainclass ${MAINCLASS} -singleTM -optimize -debug -dcopts -stmstats -fastmemcpy -transstats -joptimize -abcclose # -joptimize default: diff --git a/Robust/src/Benchmarks/SingleTM/common/BitMap.java b/Robust/src/Benchmarks/SingleTM/common/BitMap.java index 8f191033..7bc2f922 100644 --- a/Robust/src/Benchmarks/SingleTM/common/BitMap.java +++ b/Robust/src/Benchmarks/SingleTM/common/BitMap.java @@ -117,41 +117,39 @@ public class BitMap { /* ============================================================================= * bitmap_set * -- Sets ith bit to 1 - * -- Returns TRUE on success, else FALSE + * -- Returns true on success, else false * ============================================================================= */ - /* - bool_t - bitmap_set (bitmap_t* bitmapPtr, int i) + public boolean + bitmap_set (int i) { - if ((i < 0) || (i >= bitmapPtr.numBit)) { - return FALSE; + if ((i < 0) || (i >= numBit)) { + return false; } - bitmapPtr.bits[i/NUM_BIT_PER_WORD] |= (1UL << (i % NUM_BIT_PER_WORD)); + bits[i/NUM_BIT_PER_WORD] |= (1 << (i % NUM_BIT_PER_WORD)); - return TRUE; + return true; } - */ /* ============================================================================= * bitmap_clear * -- Clears ith bit to 0 - * -- Returns TRUE on success, else FALSE + * -- Returns true on success, else false * ============================================================================= */ /* - bool_t + boolean bitmap_clear (bitmap_t* bitmapPtr, int i) { if ((i < 0) || (i >= bitmapPtr.numBit)) { - return FALSE; + return false; } bitmapPtr.bits[i/NUM_BIT_PER_WORD] &= ~(1UL << (i % NUM_BIT_PER_WORD)); - return TRUE; + return true; } */ @@ -161,51 +159,49 @@ public class BitMap { * -- Clears all bit to 0 * ============================================================================= */ - /* - void - bitmap_clearAll (bitmap_t* bitmapPtr) + public void + bitmap_clearAll () { - memset(bitmapPtr.bits, 0, (bitmapPtr.numWord * sizeof(uint_t))); + for(int i = 0; i= 0) && (i < bitmapPtr.numBit) && !(bitmapPtr.bits[i/NUM_BIT_PER_WORD] & (1UL << (i % NUM_BIT_PER_WORD)))) { - return TRUE; + return true; } - return FALSE; + return false; } */ /* ============================================================================= * bitmap_isSet - * -- Returns TRUE if ith bit is set, else FALSE + * -- Returns true if ith bit is set, else false * ============================================================================= */ - /* - bool_t - bitmap_isSet (bitmap_t* bitmapPtr, int i) + public boolean + bitmap_isSet (int i) { - if ((i >= 0) && (i < bitmapPtr.numBit) && - (bitmapPtr.bits[i/NUM_BIT_PER_WORD] & (1UL << (i % NUM_BIT_PER_WORD)))) { - return TRUE; + if ((i >= 0) && (i < numBit) && + (bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD)))) { + return true; } - return FALSE; + return false; } - */ /* ============================================================================= @@ -215,23 +211,21 @@ public class BitMap { * -- If all bits are set, returns -1 * ============================================================================= */ - /* - int - bitmap_findClear (bitmap_t* bitmapPtr, int startIndex) + public int + bitmap_findClear (int startIndex) { - int i; - int numBit = bitmapPtr.numBit; - uint_t* bits = bitmapPtr.bits; + int tmp_numBit = numBit; + int[] tmp_bits = bits; + //uint_t* bits = bitmapPtr.bits; - for (i = MAX(startIndex, 0); i < numBit; i++) { - if (!(bits[i/NUM_BIT_PER_WORD] & (1UL << (i % NUM_BIT_PER_WORD)))) { + for (int i = MAX(startIndex, 0); i < tmp_numBit; i++) { + if (!(tmp_bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD)))) { return i; } } return -1; } - */ /* ============================================================================= @@ -328,6 +322,15 @@ public class BitMap { } } */ + + /** + * ====================================== + * MAX(a.b) + * ====================================== + **/ + public int MAX(int a, int b) { + return (a > b) ? a : b; + } } /* ============================================================================= diff --git a/Robust/src/Benchmarks/SingleTM/common/Queue.java b/Robust/src/Benchmarks/SingleTM/common/Queue.java index ef74143c..6cf6bbe0 100644 --- a/Robust/src/Benchmarks/SingleTM/common/Queue.java +++ b/Robust/src/Benchmarks/SingleTM/common/Queue.java @@ -168,11 +168,11 @@ public class Queue { * ============================================================================= */ public boolean - queue_isEmpty (Queue queuePtr) + queue_isEmpty () { - int pop = queuePtr.pop; - int push = queuePtr.push; - int capacity = queuePtr.capacity; + //int pop = queuePtr.pop; + //int push = queuePtr.push; + //int capacity = queuePtr.capacity; return (((pop + 1) % capacity == push) ? true : false); } @@ -183,10 +183,10 @@ public class Queue { * ============================================================================= */ public void - queue_clear (Queue* queuePtr) + queue_clear () { - queuePtr.pop = queuePtr.capacity - 1; - queuePtr.push = 0; + pop = capacity - 1; + push = 0; } @@ -243,12 +243,8 @@ public class Queue { * ============================================================================= */ public boolean - queue_push (Queue queuePtr, Object dataPtr) + queue_push (Object dataPtr) { - int pop = queuePtr.pop; - int push = queuePtr.push; - int capacity = queuePtr.capacity; - if(pop == push) { System.out.println("push == pop in Queue.java"); return false; @@ -265,7 +261,7 @@ public class Queue { } int dst = 0; - Object[] elements = queuePtr.elements; + Object[] tmpelements = elements; if (pop < push) { int src; for (src = (pop + 1); src < push; src++, dst++) { @@ -281,16 +277,16 @@ public class Queue { } } - elements = null; - queuePtr.elements = newElements; - queuePtr.pop = newCapacity - 1; - queuePtr.capacity = newCapacity; + //elements = null; + elements = newElements; + pop = newCapacity - 1; + capacity = newCapacity; push = dst; newPush = push + 1; /* no need modulo */ } - queuePtr.elements[push] = dataPtr; - queuePtr.push = newPush; + elements[push] = dataPtr; + push = newPush; return true; } @@ -419,19 +415,22 @@ public class Queue { * ============================================================================= */ public Object - queue_pop (Queue queuePtr) + //queue_pop (Queue queuePtr) + queue_pop () { - int pop = queuePtr.pop; - int push = queuePtr.push; - int capacity = queuePtr.capacity; + //int pop = queuePtr.pop; + //int push = queuePtr.push; + //int capacity = queuePtr.capacity; int newPop = (pop + 1) % capacity; if (newPop == push) { return null; } - Object dataPtr = queuePtr.elements[newPop]; - queuePtr.pop = newPop; + //Object dataPtr = queuePtr.elements[newPop]; + //queuePtr.pop = newPop; + Object dataPtr = elements[newPop]; + pop = newPop; return dataPtr; } diff --git a/Robust/src/Benchmarks/SingleTM/common/Vector_t.java b/Robust/src/Benchmarks/SingleTM/common/Vector_t.java index 87c95ad9..513e8032 100644 --- a/Robust/src/Benchmarks/SingleTM/common/Vector_t.java +++ b/Robust/src/Benchmarks/SingleTM/common/Vector_t.java @@ -13,7 +13,7 @@ public class Vector_t { * ============================================================================= */ public static Vector_t vector_alloc (int initCapacity) { - int capacity = Math.max(initCapacity, 1); + int capacity = Math.imax(initCapacity, 1); Vector_t vectorPtr = new Vector(); if(vectorPtr != null) { vectorPtr.size = 0; @@ -40,12 +40,12 @@ public class Vector_t { * -- Returns null if failed * ============================================================================= */ - public static Object vector_at (Vector_t vectorPtr, int i) { - if ((i < 0) || (i >= vectorPtr.size)) { + public Object vector_at (int i) { + if ((i < 0) || (i >= size)) { System.out.println("Illegal Vector.element\n"); return null; } - return (vectorPtr.elements[i]); + return (elements[i]); } -- 2.34.1