From 0fd1a5e73c1297de9c67bf2132e9619dc891eac5 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 5 Nov 2010 15:54:33 +0000 Subject: [PATCH] changes --- Robust/src/IR/Flat/BuildCode.java | 53 +++++-- .../src/IR/Flat/RuntimeConflictResolver.java | 1 + Robust/src/Runtime/mlp_runtime.c | 141 +++++++----------- Robust/src/Runtime/mlp_runtime.h | 21 ++- Robust/src/Runtime/oooJava/TODO | 2 +- 5 files changed, 107 insertions(+), 111 deletions(-) diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index bb0679cc..807d2ee3 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -3310,9 +3310,7 @@ public class BuildCode { if(state.RCR) { //no need to enqueue parent effect if coarse grained conflict clears us - - output.println(" while(stallrecord.common.rcrstatus) {;}"); - output.println(" BARRIER();"); + output.println(" while(stallrecord.common.rcrstatus) BARRIER();"); // was the code above actually meant to look like this? //output.println(" while(stallrecord.common.rcrstatus) {"); //output.println(" BARRIER();"); @@ -4462,41 +4460,68 @@ public class BuildCode { output.println(" REntry* rentry=NULL;"); output.println(" INTPTR* pointer=NULL;"); output.println(" seseToIssue->common.rentryIdx=0;"); - output.println(" int dispCount;"); Vector invars=fsen.getInVarsForDynamicCoarseConflictResolution(); System.out.println(fm.getMethod()+"["+invars+"]"); + + Vector queuetovar=new Vector(); + for(int i=0;i weset=seseWaitingQueue.getWaitingElementSet(td); - if (weset==null) - System.out.println("ERROR:"+td+" "+fsen+" "+fm.getMethod()); int numqueues=weset.size(); output.println(" seseToIssue->rcrRecords["+i+"].flag="+numqueues+";"); + output.println(" int dispCount"+i+"=0;"); - //output.println(" seseToIssue->rcrRecords["+i+"].count=0;"); - //output.println(" seseToIssue->rcrRecords["+i+"].index=0;"); - //output.println(" seseToIssue->rcrRecords["+i+"].next=NULL;"); + for(Iterator wtit=weset.iterator();wtit.hasNext();) { + Analysis.OoOJava.WaitingElement waitingElement=wtit.next(); + int queueID=waitingElement.getQueueID(); + if (queueID>queuetovar.size()) + queuetovar.setSize(queueID); + Long l=queuetovar.get(queueID); + long val=(l!=null)?l.longValue():0; + val=val|(1< weset=seseWaitingQueue.getWaitingElementSet(td); + int numqueues=weset.size(); for(Iterator wtit=weset.iterator();wtit.hasNext();) { Analysis.OoOJava.WaitingElement waitingElement=wtit.next(); int queueID=waitingElement.getQueueID(); + if (generatedqueueentry.contains(queueID)) + continue; + else + generatedqueueentry.add(queueID); + assert(waitingElement.getStatus()>=ConflictNode.COARSE); - output.println(" rentry=mlpCreateREntry(runningSESE->memoryQueueArray["+ waitingElement.getQueueID()+ "]," + waitingElement.getStatus() + ", &(seseToIssue->common));"); + long mask=queuetovar.get(queueID); + output.println(" rentry=mlpCreateREntry(runningSESE->memoryQueueArray["+ waitingElement.getQueueID()+ "]," + waitingElement.getStatus() + ", &(seseToIssue->common)"+mask+"LL);"); output.println(" seseToIssue->common.rentryArray[seseToIssue->common.rentryIdx++]=rentry;"); output.println(" rentry->queue=runningSESE->memoryQueueArray[" + waitingElement.getQueueID()+"];"); + output.println(" if(ADDRENTRY(runningSESE->memoryQueueArray["+ waitingElement.getQueueID()+ "],rentry)==READY) {"); - output.println(" dispCount++;"); + for(int j=0;mask!=0;j++) { + if ((mask&1)==1) + output.println(" dispCount"+j+"++;"); + mask=mask>>1; + } output.println(" }"); } - output.println(" if(!dispCount || !atomic_sub_and_test(dispCount,&(seseToIssue->rcrRecords["+i+"].flag)))"); - output.println(" localCount++;"); + if (fsen.getDynamicInVarSet().contains(td)) { // dynamic in-var case //output.println(" pointer=seseToIssue->" + waitingElement.getDynID()+ "_srcSESE+seseToIssue->"+ waitingElement.getDynID()+ "_srcOffset;"); //output.println(" rentry=mlpCreateFineREntry("+ waitingElement.getStatus()+ ", &(seseToIssue->common), pointer );"); } } + for(int i=0;ircrRecords["+i+"].flag)))"); + output.println(" localCount++;"); + } output.println(" }"); } } diff --git a/Robust/src/IR/Flat/RuntimeConflictResolver.java b/Robust/src/IR/Flat/RuntimeConflictResolver.java index 0d9bb0ed..f09e79fc 100644 --- a/Robust/src/IR/Flat/RuntimeConflictResolver.java +++ b/Robust/src/IR/Flat/RuntimeConflictResolver.java @@ -662,6 +662,7 @@ public class RuntimeConflictResolver { } else { cFile.println(" record->rcrRecords["+index+"].count=RUNBIAS;\n"); cFile.println(" record->rcrRecords["+index+"].index=0;\n"); + cFile.println(" record->rcrRecords["+index+"].next=NULL;\n"); } //clears queue and hashtable that keeps track of where we've been. diff --git a/Robust/src/Runtime/mlp_runtime.c b/Robust/src/Runtime/mlp_runtime.c index c661c5ef..e769ed08 100644 --- a/Robust/src/Runtime/mlp_runtime.c +++ b/Robust/src/Runtime/mlp_runtime.c @@ -65,7 +65,11 @@ REntry* mlpCreateFineREntry(MemoryQueue* q, int type, SESEcommon* seseToIssue, v return newREntry; } -REntry* mlpCreateREntry(MemoryQueue* q, int type, SESEcommon* seseToIssue){ +#ifdef RCR +REntry* mlpCreateREntry(MemoryQueue* q, int type, SESEcommon* seseToIssue, INTPTR mask) { +#else +REntry* mlpCreateREntry(MemoryQueue* q, int type, SESEcommon* seseToIssue) { +#endif #ifdef OOO_DISABLE_TASKMEMPOOL REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry)); #else @@ -73,6 +77,9 @@ REntry* mlpCreateREntry(MemoryQueue* q, int type, SESEcommon* seseToIssue){ #endif newREntry->type=type; newREntry->seseRec=seseToIssue; +#ifdef RCR + newREntry->mask=mask; +#endif return newREntry; } @@ -256,7 +263,7 @@ int ADDTABLE(MemoryQueue *q, REntry *r) { //at this point, have table Hashtable* table=(Hashtable*)q->tail; - r->hashtable=table; // set rentry's hashtable + r->qitem=(MemoryQueueItem *) table; // set rentry's hashtable if( *(r->pointer)==0 || ( *(r->pointer)!=0 && BARRIER() && @@ -366,7 +373,7 @@ int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r, int inc) { if(inc){ atomic_inc(&T->item.total); } - r->hashtable=T; + r->qitem=(MemoryQueueItem *)T; r->binitem=b; be->tail=b; be->head=b;//released lock @@ -393,7 +400,7 @@ int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) { atomic_inc(&T->item.total); } - r->hashtable=T; + r->qitem=(MemoryQueueItem *)T; r->binitem=(BinItem*)b; be->tail->next=(BinItem*)b; @@ -422,7 +429,7 @@ int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) { return retval; } -READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) { +void READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) { BinItem * bintail=T->array[key]->tail; if (isReadBinItem(bintail)) { return TAILREADCASE(T, r, val, bintail, key, inc); @@ -463,12 +470,12 @@ int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int ke if(inc){ atomic_inc(&T->item.total); } - r->hashtable=T; + r->qitem=(MemoryQueueItem *)T; T->array[key]->head=val;//released lock return retval; } -TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) { +void TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) { // WriteBinItem* wb=createWriteBinItem(); //wb->val=r; //wb->item.total=1;//safe because item could not have started @@ -480,14 +487,14 @@ TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, if(inc){ atomic_inc(&T->item.total); } - r->hashtable=T; + r->qitem=(MemoryQueueItem *)T; r->binitem=(BinItem*)rb; T->array[key]->tail->next=(BinItem*)rb; T->array[key]->tail=(BinItem*)rb; T->array[key]->head=val;//released lock } -ADDVECTOR(MemoryQueue *Q, REntry *r) { +void ADDVECTOR(MemoryQueue *Q, REntry *r) { if(!isVector(Q->tail)) { //Fast Case if (isParentCoarse(r) && Q->tail->total==0 && Q->tail==Q->head) { @@ -531,7 +538,7 @@ ADDVECTOR(MemoryQueue *Q, REntry *r) { BARRIER(); V->index++; //*****NEED memory barrier here to ensure compiler does not cache V.status********* - r->vector=V; + r->qitem=(MemoryQueueItem *)V; if (BARRIER() && V->item.status==READY) { void* flag=NULL; flag=(void*)LOCKXCHG((unsigned INTPTR*)&(V->array[index]), (unsigned INTPTR)flag); @@ -551,12 +558,12 @@ ADDVECTOR(MemoryQueue *Q, REntry *r) { //SCC's don't come in parent variety -ADDSCC(MemoryQueue *Q, REntry *r) { +void ADDSCC(MemoryQueue *Q, REntry *r) { //added SCC SCC* S=createSCC(); S->item.total=1; S->val=r; - r->scc=S; + r->qitem=(MemoryQueueItem *)S; Q->tail->next=(MemoryQueueItem*)S; //*** NEED BARRIER HERE if (BARRIER() && Q->tail->status==READY && Q->tail->total==0 && Q->tail==Q->head) { @@ -594,15 +601,15 @@ void RETIRERENTRY(MemoryQueue* Q, REntry * r) { #endif } -RETIRESCC(MemoryQueue *Q, REntry *r) { - SCC* s=r->scc; +void RETIRESCC(MemoryQueue *Q, REntry *r) { + SCC* s=(SCC *)r->qitem; s->item.total=0;//don't need atomicdec RESOLVECHAIN(Q); } -RETIREHASHTABLE(MemoryQueue *q, REntry *r) { - Hashtable *T=r->hashtable; +void RETIREHASHTABLE(MemoryQueue *q, REntry *r) { + Hashtable *T=(Hashtable *)r->qitem; BinItem *b=r->binitem; RETIREBIN(T,r,b); atomic_dec(&T->item.total); @@ -611,7 +618,7 @@ RETIREHASHTABLE(MemoryQueue *q, REntry *r) { } } -RETIREBIN(Hashtable *T, REntry *r, BinItem *b) { +void RETIREBIN(Hashtable *T, REntry *r, BinItem *b) { int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) ); if(isFineRead(r)) { atomic_dec(&b->total); @@ -684,15 +691,15 @@ RETIREBIN(Hashtable *T, REntry *r, BinItem *b) { } -RETIREVECTOR(MemoryQueue *Q, REntry *r) { - Vector* V=r->vector; +void RETIREVECTOR(MemoryQueue *Q, REntry *r) { + Vector* V=(Vector *)r->qitem; atomic_dec(&V->item.total); if (V->item.next!=NULL && V->item.total==0) { //NOTE: ORDERING CRUCIAL HERE RESOLVECHAIN(Q); } } -RESOLVECHAIN(MemoryQueue *Q) { +void RESOLVECHAIN(MemoryQueue *Q) { while(TRUE) { MemoryQueueItem* head=Q->head; if (head->next==NULL||head->total!=0) { @@ -721,7 +728,7 @@ RESOLVECHAIN(MemoryQueue *Q) { } -RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) { +void RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) { int binidx; for (binidx=0;binidxarray[binidx]; @@ -769,7 +776,7 @@ RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) { } } -RESOLVEVECTOR(MemoryQueue *q, Vector *V) { +void RESOLVEVECTOR(MemoryQueue *q, Vector *V) { int i; Vector* tmp=V; //handle ready cases @@ -793,7 +800,7 @@ RESOLVEVECTOR(MemoryQueue *q, Vector *V) { } } -RESOLVESCC(SCC *S) { +void RESOLVESCC(SCC *S) { //precondition: SCC's state is READY void* flag=NULL; flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag); @@ -803,15 +810,36 @@ RESOLVESCC(SCC *S) { } -resolveDependencies(REntry* rentry){ +void resolveDependencies(REntry* rentry){ SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec; - if(rentry->type==READ || rentry->type==WRITE || rentry->type==COARSE || rentry->type==SCCITEM){ + int type=rentry->type; +#ifdef RCR + if (type==COARSE||type==SCCITEM) { + struct rcrRecord * array=(struct rcrRecord *)(((char *)seseCommon)+seseCommon->offsetToParamRecords); + INTPTR mask=rentry->mask; + int index=-1; + while(mask!=0) { + int shift=__builtin_ctzll(mask)+1; + index+=shift; + if(atomic_sub_and_test(1, &array[index].flag)) { + if(atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies))) + workScheduleSubmit((void *)seseCommon); + } + } + } else if (type==PARENTCOARSE) { + psem_give_tag(rentry->parentStallSem, rentry->tag); + } else { + printf("ERROR...\n"); + } +#else + if(type==READ || type==WRITE || type==COARSE || type==SCCITEM){ if( atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)) ){ workScheduleSubmit(seseCommon); } - }else if(rentry->type==PARENTREAD || rentry->type==PARENTWRITE ||rentry->type==PARENTCOARSE){ + }else if(type==PARENTREAD || type==PARENTWRITE || type==PARENTCOARSE){ psem_give_tag(rentry->parentStallSem, rentry->tag); } +#endif } void INITIALIZEBUF(MemoryQueue * q){ @@ -937,9 +965,8 @@ int RESOLVEBUF(MemoryQueue * q, SESEcommon *seseCommon){ } -resolvePointer(REntry* rentry){ - - Hashtable* table=rentry->hashtable; +void resolvePointer(REntry* rentry){ + Hashtable* table=(Hashtable *)rentry->qitem; MemoryQueue* queue; if(table==NULL || table->unresolvedQueue==NULL){ //resolved already before related rentry is enqueued to the waiting queue @@ -1005,60 +1032,4 @@ resolvePointer(REntry* rentry){ } void rehashMemoryQueue(SESEcommon* seseParent){ -#if 0 - // update memory queue - int i,binidx; - for(i=0; inumMemoryQueue; i++){ - MemoryQueue *memoryQueue=seseParent->memoryQueueArray[i]; - MemoryQueueItem *memoryItem=memoryQueue->head; - MemoryQueueItem *prevItem=NULL; - while(memoryItem!=NULL){ - if(memoryItem->type==HASHTABLE){ - //do re-hash! - Hashtable* ht=(Hashtable*)memoryItem; - Hashtable* newht=createHashtable(); - int binidx; - for(binidx=0; binidxarray[binidx]; - BinItem *binItem=bin->head; - //traverse over the list of each bin - while(binItem!=NULL){ - if(binItem->type==READBIN){ - ReadBinItem* readBinItem=(ReadBinItem*)binItem; - int ridx; - for(ridx=0; ridxindex; ridx++){ - REntry *rentry=readBinItem->array[ridx]; - int newkey=generateKey((unsigned int)(unsigned INTPTR)*(rentry->pointer)); - int status=rentry->binitem->status; - ADDTABLEITEM(newht,rentry,TRUE); - rentry->binitem->status=status; // update bin status as before rehash - } - }else{//write bin - REntry *rentry=((WriteBinItem*)binItem)->val; - int newkey=generateKey((unsigned int)(unsigned INTPTR)*(rentry->pointer)); - int status=rentry->binitem->status; - ADDTABLEITEM(newht,rentry,TRUE); - int newstatus=rentry->binitem->status; - //printf("[%d]old status=%d new status=%d\n",i,status,newstatus); - rentry->binitem->status=status; // update bin status as before rehash - } - binItem=binItem->next; - } - } - newht->item.status=ht->item.status; // update hashtable status - if(prevItem!=NULL){ - prevItem->next=(MemoryQueueItem*)newht; - }else{ - if(memoryQueue->head==memoryQueue->tail){ - memoryQueue->tail=(MemoryQueueItem*)newht; - } - memoryQueue->head=(MemoryQueueItem*)newht; - } - newht->item.next=ht->item.next; - } - prevItem=memoryItem; - memoryItem=memoryItem->next; - } - } -#endif } diff --git a/Robust/src/Runtime/mlp_runtime.h b/Robust/src/Runtime/mlp_runtime.h index 2b5415e7..ec0715b6 100644 --- a/Robust/src/Runtime/mlp_runtime.h +++ b/Robust/src/Runtime/mlp_runtime.h @@ -147,15 +147,16 @@ typedef struct REntry_t{ // fine read:0, fine write:1, parent read:2, // parent write:3 coarse: 4, parent coarse:5, scc: 6 int type; - struct Hashtable_t* hashtable; + int tag; + MemoryQueueItem *qitem; struct BinItem_t* binitem; - struct Vector_t* vector; - struct SCC_t* scc; struct MemoryQueue_t* queue; - psemaphore * parentStallSem; - int tag; SESEcommon* seseRec; INTPTR* pointer; + psemaphore * parentStallSem; +#ifdef RCR + INTPTR mask; +#endif int isBufMode; } REntry; @@ -252,9 +253,6 @@ static inline void ADD_FORWARD_ITEM( ForwardingListElement* e, //atomic_inc( &(s->refCount) ); } - - - // simple mechanical allocation and // deallocation of SESE records void* mlpAllocSESErecord( int size ); @@ -262,13 +260,14 @@ void mlpFreeSESErecord( SESEcommon* seseRecord ); MemoryQueue** mlpCreateMemoryQueueArray(int numMemoryQueue); REntry* mlpCreateFineREntry(MemoryQueue *q, int type, SESEcommon* seseToIssue, void* dynID); +#ifdef RCR +REntry* mlpCreateREntry(MemoryQueue *q, int type, SESEcommon* seseToIssue, INTPTR mask); +#else REntry* mlpCreateREntry(MemoryQueue *q, int type, SESEcommon* seseToIssue); +#endif MemoryQueue* createMemoryQueue(); void rehashMemoryQueue(SESEcommon* seseParent); - - - static inline void ADD_REFERENCE_TO( SESEcommon* seseRec ) { atomic_inc( &(seseRec->refCount) ); } diff --git a/Robust/src/Runtime/oooJava/TODO b/Robust/src/Runtime/oooJava/TODO index 31b3527f..551a2d32 100644 --- a/Robust/src/Runtime/oooJava/TODO +++ b/Robust/src/Runtime/oooJava/TODO @@ -2,7 +2,7 @@ Big TODOS: 1) Handle rapid reuse of SESEStall record - done 2) Handle linked list of bins - done 3) Hashtable management (managing links + each SESE should have its own traverser threads + traversers should be generated on demand) -4) Multiple taint of coarse management [what if one coarse entry supports two parameter conflicts...] +4) Multiple taint of coarse management [what if one coarse entry supports two parameter conflicts...] -- fixed 5) Recycling [recycle entries to improve runtime] 6) Parallelize traversal 7) Fix race on enqueue into table vs dequeue at retire... - done -- 2.34.1