From 1529478194081c90a63d167b239cf28f2676eaef Mon Sep 17 00:00:00 2001 From: yeom Date: Thu, 7 Jan 2010 04:19:08 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/MLP/ConflictGraph.java | 107 +++++++++++++++++++ Robust/src/Analysis/MLP/MLPAnalysis.java | 4 + Robust/src/IR/Flat/BuildCode.java | 118 +++++++++++++++++---- Robust/src/Runtime/mlp_runtime.c | 61 +++++++++++ Robust/src/Runtime/mlp_runtime.h | 8 +- 5 files changed, 276 insertions(+), 22 deletions(-) diff --git a/Robust/src/Analysis/MLP/ConflictGraph.java b/Robust/src/Analysis/MLP/ConflictGraph.java index 53933c87..508dbfe4 100644 --- a/Robust/src/Analysis/MLP/ConflictGraph.java +++ b/Robust/src/Analysis/MLP/ConflictGraph.java @@ -2,6 +2,7 @@ package Analysis.MLP; import java.io.BufferedWriter; import java.io.FileWriter; +import java.util.Collection; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; @@ -93,6 +94,7 @@ public class ConflictGraph { } } } + } if (readEffectsSet != null) { @@ -479,6 +481,108 @@ public class ConflictGraph { return resultSet; } + + public Set getConnectedConflictNodeSet(ParentChildConflictsMap conflictsMap){ + + HashSet nodeIDSet = new HashSet(); + + Set> s = id2cn.entrySet(); + Iterator> i = s.iterator(); + + Collection stallSites=conflictsMap.getStallMap().values(); + for (Iterator iterator = stallSites.iterator(); iterator.hasNext();) { + StallSite stallSite = (StallSite) iterator.next(); + while (i.hasNext()) { + Entry entry = i.next(); + ConflictNode node = entry.getValue(); + + if (node instanceof StallSiteNode) { + StallSiteNode stallSiteNode = (StallSiteNode) node; + if (stallSiteNode.getStallSite() == stallSite) { + HashSet edgeSet = stallSiteNode.getEdgeSet(); + for (Iterator iter2 = edgeSet.iterator(); iter2.hasNext();) { + ConflictEdge conflictEdge = (ConflictEdge) iter2.next(); + nodeIDSet.addAll(getConnectedConflictNode(conflictEdge)); + } + } + } + } + } + + return nodeIDSet; + + } + + private Set getConnectedConflictNode(ConflictEdge conflictEdge){ + + HashSet nodeIDSet = new HashSet(); + + if(conflictEdge.getVertexU() instanceof LiveInNode){ + LiveInNode lin=(LiveInNode)conflictEdge.getVertexU(); + nodeIDSet.add(new Integer(lin.getSESEIdentifier())); + } + if(conflictEdge.getVertexV() instanceof LiveInNode){ + LiveInNode lin=(LiveInNode)conflictEdge.getVertexV(); + nodeIDSet.add(new Integer(lin.getSESEIdentifier())); + } + + return nodeIDSet; + } + + private Set getConnectedConflictNode(ConflictEdge conflictEdge, int seseID){ + + HashSet nodeIDSet = new HashSet(); + + if(conflictEdge.getVertexU() instanceof LiveInNode){ + LiveInNode lin=(LiveInNode)conflictEdge.getVertexU(); + if(lin.getSESEIdentifier()!=seseID){ + nodeIDSet.add(new Integer(lin.getSESEIdentifier())); + } + }else{ + // it is stall site + nodeIDSet.add(new Integer(-1)); + } + if(conflictEdge.getVertexV() instanceof LiveInNode){ + LiveInNode lin=(LiveInNode)conflictEdge.getVertexV(); + if(lin.getSESEIdentifier()!=seseID){ + nodeIDSet.add(new Integer(lin.getSESEIdentifier())); + } + }else{ + // it is stall site + nodeIDSet.add(new Integer(-1)); + } + + return nodeIDSet; + } + + public Set getConnectedConflictNodeSet(int seseID){ + + HashSet nodeIDSet = new HashSet(); + + Set> s = id2cn.entrySet(); + Iterator> i = s.iterator(); + + while (i.hasNext()) { + Entry entry = i.next(); + ConflictNode node = entry.getValue(); + + if (node instanceof LiveInNode) { + LiveInNode liveInNode = (LiveInNode) node; + if (liveInNode.getSESEIdentifier() == seseID) { + HashSet edgeSet = liveInNode.getEdgeSet(); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); + // + nodeIDSet.addAll(getConnectedConflictNode(conflictEdge,seseID)); + // + } + } + } + } + + return nodeIDSet; + + } public Set getAllocationSiteIDSetBySESEID(int seseID) { @@ -497,6 +601,9 @@ public class ConflictGraph { HashSet edgeSet = liveInNode.getEdgeSet(); for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); + // + getConnectedConflictNode(conflictEdge,seseID); + // if (conflictEdge.getType() == ConflictEdge.COARSE_GRAIN_EDGE) { allocSiteIDSet.addAll(getHRNIdentifierSet(conflictEdge.getVertexU())); allocSiteIDSet.addAll(getHRNIdentifierSet(conflictEdge.getVertexV())); diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 53cc78fb..76f0069b 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -3431,4 +3431,8 @@ public class MLPAnalysis { return conflictsResults; } + public Hashtable getSeseSummaryMap(){ + return seseSummaryMap; + } + } diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index aa242605..8c94b32a 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -2701,20 +2701,47 @@ public class BuildCode { TempDescriptor dynVar = dynItr.next(); output.println(" "+dynVar+"_srcSESE = NULL;"); } - } - - // eom - // handling stall site - ParentChildConflictsMap conflictsMap=mlpa.getConflictsResults().get(fn); - if (conflictsMap != null) { + // eom + // handling stall site + + ParentChildConflictsMap conflictsMap=mlpa.getConflictsResults().get(fn); + + if (conflictsMap != null) { + Set allocSet = conflictsMap .getAllocationSiteIDSetofStallSite(); if (allocSet.size() > 0) { + + FlatNode enclosingFlatNode=null; + if( currentSESE.getIsCallerSESEplaceholder() && currentSESE.getParent()==null){ + enclosingFlatNode=currentSESE.getfmEnclosing(); + }else{ + enclosingFlatNode=currentSESE; + } + + ConflictGraph graph=mlpa.getConflictGraphResults().get(enclosingFlatNode); + Set connectedSet=graph.getConnectedConflictNodeSet(conflictsMap); + output.println(" /* stall on parent's stall sites */"); output.println(" {"); output.println(" pthread_mutex_lock( &(seseCaller->lock) );"); + // + output.println(" ConflictNode* node;"); + for (Iterator iterator = connectedSet.iterator(); iterator + .hasNext();) { + Integer integer = (Integer) iterator.next(); + //output.print(" "+integer); + if(integer.intValue()<0){ + output.println(" node=mlpCreateConflictNode(seseCaller->classID);"); + }else{ + output.println(" node=mlpCreateConflictNode( "+integer+" );"); + } + output.println(" addNewConflictNode(node, seseCaller->connectedList);"); + } + // + output.println(" psem_init( &(seseCaller->memoryStallSiteSem) );"); output.println(" int qIdx;"); output.println(" int takeCount=0;"); @@ -2735,6 +2762,7 @@ public class BuildCode { output.println(" }"); } } + } } switch(fn.kind()) { @@ -3296,6 +3324,9 @@ public class BuildCode { output.println(" psem_init( &(seseToIssue->common.stallSem) );"); output.println(" seseToIssue->common.forwardList = createQueue();"); + //eom + output.println(" seseToIssue->common.connectedList = createQueue();"); + // output.println(" seseToIssue->common.unresolvedDependencies = 0;"); output.println(" pthread_cond_init( &(seseToIssue->common.doneCond), NULL );"); output.println(" seseToIssue->common.doneExecuting = FALSE;"); @@ -3346,8 +3377,27 @@ public class BuildCode { Set allocSet = graph.getAllocationSiteIDSetBySESEID(fsen .getIdentifier()); + Set connectedSet=graph.getConnectedConflictNodeSet(fsen + .getIdentifier()); + if (allocSet.size() > 0) { output.println(" {"); + + // + output.println(" ConflictNode* node;"); + for (Iterator iterator = connectedSet.iterator(); iterator + .hasNext();) { + Integer integer = (Integer) iterator.next(); + //output.print(" "+integer); + if(integer.intValue()<0){ + output.println(" node=mlpCreateConflictNode(seseCaller->classID);"); + }else{ + output.println(" node=mlpCreateConflictNode( "+integer+" );"); + } + output.println(" addNewItem(seseToIssue->common.connectedList,node);"); + } + // + output .println(" pthread_mutex_lock( &(parentCommon->lock) );"); @@ -3585,31 +3635,57 @@ public class BuildCode { output.println(" pthread_mutex_lock( &(___params___->common.parent->lock) );"); output.println(" int idx;"); output.println(" int giveCount=0;"); + output.println(" struct Queue* launchQueue=createQueue();"); + output.println(" struct QueueItem* nextQueueItem;"); output.println(" for(idx = 0 ; idx < ___params___->common.parent->numRelatedAllocSites ; idx++){"); - output.println(" if(!isEmpty(___params___->common.parent->allocSiteArray[idx].waitingQueue)){"); + output.println(" if(!isEmpty(___params___->common.parent->allocSiteArray[idx].waitingQueue)){"); output.println(" SESEcommon* item=peekItem(___params___->common.parent->allocSiteArray[idx].waitingQueue);"); output.println(" if( item->classID == ___params___->common.classID ){"); output.println(" struct QueueItem* qItem=findItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,item);"); output.println(" removeItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,qItem);"); output.println(" if( !isEmpty(___params___->common.parent->allocSiteArray[idx].waitingQueue) ){"); - output.println(" SESEcommon* nextItem=peekItem(___params___->common.parent->allocSiteArray[idx].waitingQueue);"); - output.println(" if(nextItem->classID==___params___->common.parent->classID){"); - output.println(" struct QueueItem* stallItem=findItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,nextItem);"); - output.println(" removeItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,stallItem);"); - output.println(" giveCount++;"); - output.println(" }else{"); - output.println(" pthread_mutex_lock( &(nextItem->lock) );"); - output.println(" --(nextItem->unresolvedDependencies);"); - output.println(" if( nextItem->unresolvedDependencies == 0){"); - output.println(" workScheduleSubmit( (void*)nextItem);"); - output.println(" }"); - output.println(" pthread_mutex_unlock( &(nextItem->lock) );"); - output.println(" }"); + + output.println(" struct QueueItem* nextQItem=getHead(___params___->common.parent->allocSiteArray[idx].waitingQueue);"); + output.println(" while(nextQItem!=NULL){"); + output.println(" SESEcommon* nextItem=nextQItem->objectptr;"); + output.println(" int isResolved=resolveWaitingQueue(___params___->common.parent->allocSiteArray[idx].waitingQueue,nextQItem);"); + output.println(" if(nextItem->classID==___params___->common.parent->classID){"); + output.println(" if(isResolved){"); + output.println(" struct QueueItem* stallItem=findItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,nextItem);"); + output.println(" removeItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,stallItem);"); + output.println(" giveCount++;"); + output.println(" }"); + output.println(" if(!isEmpty(___params___->common.parent->allocSiteArray[idx].waitingQueue)){"); +// output.println(" nextQItem=getHead(___params___->common.parent->allocSiteArray[idx].waitingQueue);"); + output.println(" nextQItem=getNextQueueItem(nextQItem);"); + output.println(" }else{"); + output.println(" nextQItem=NULL;"); + output.println(" }"); + output.println(" }else{"); + output.println(" if(isResolved){"); + output.println(" pthread_mutex_lock( &(nextItem->lock) );"); + output.println(" --(nextItem->unresolvedDependencies);"); + output.println(" if( nextItem->unresolvedDependencies == 0){"); + //output.println(" workScheduleSubmit( (void*)nextItem);"); + output.println(" addNewItem(launchQueue,(void*)nextItem);"); + output.println(" }"); + output.println(" pthread_mutex_unlock( &(nextItem->lock) );"); + output.println(" }"); + output.println(" nextQItem=getNextQueueItem(nextQItem);"); + output.println(" }"); + output.println(" } "); // end of while(nextQItem!=NULL) output.println(" }"); output.println(" }"); - output.println(" }"); + output.println(" }"); output.println(" }"); output.println(" pthread_mutex_unlock( &(___params___->common.parent->lock) );"); + output.println(" if(!isEmpty(launchQueue)){"); + output.println(" struct QueueItem* qItem=getHead(launchQueue);"); + output.println(" while(qItem!=NULL){"); + output.println(" workScheduleSubmit(qItem->objectptr);"); + output.println(" qItem=getNextQueueItem(qItem);"); + output.println(" }"); + output.println(" }"); output.println(" if(giveCount>0){"); output.println(" psem_give(&(___params___->common.parent->memoryStallSiteSem));"); output.println(" }"); diff --git a/Robust/src/Runtime/mlp_runtime.c b/Robust/src/Runtime/mlp_runtime.c index beea2f22..b9105ff3 100644 --- a/Robust/src/Runtime/mlp_runtime.c +++ b/Robust/src/Runtime/mlp_runtime.c @@ -39,6 +39,12 @@ AllocSite* mlpCreateAllocSiteArray(int numAllocSites){ return newAllocSite; } +ConflictNode* mlpCreateConflictNode(int id){ + ConflictNode* newConflictNode=(ConflictNode*)RUNMALLOC( sizeof( ConflictNode ) ); + newConflictNode->id=id; + return newConflictNode; +} + void addWaitingQueueElement(AllocSite* allocSiteArray, int numAllocSites, long allocID, void *seseRec){ int i; @@ -62,3 +68,58 @@ int getQueueIdx(AllocSite* allocSiteArray, int numAllocSites, long allocID){ } return -1; } + +int resolveWaitingQueue(struct Queue* waitingQueue,struct QueueItem* qItem){ + + if(!isEmpty(waitingQueue)){ + + SESEcommon* qCommon=qItem->objectptr; + + struct QueueItem* current=getHead(waitingQueue); + while(current!=NULL){ + if(current!=qItem){ + SESEcommon* currentCommon=current->objectptr; + if(hasConflicts(currentCommon->classID,qCommon->connectedList)){ + return 0; + } + }else{ + return 1; + } + current=getNextQueueItem(current); + } + } + return 1; +} + +int hasConflicts(int classID, struct Queue* connectedList){ + + if(!isEmpty(connectedList)){ + struct QueueItem* queueItem=getHead(connectedList); + + while(queueItem!=NULL){ + ConflictNode* node=queueItem->objectptr; + if(node->id==classID){ + return 1; + } + queueItem=getNextQueueItem(queueItem); + } + } + return 0; +} + +void addNewConflictNode(ConflictNode* node, struct Queue* connectedList){ + + if(!isEmpty(connectedList)){ + struct QueueItem* qItem=getHead(connectedList); + while(qItem!=NULL){ + ConflictNode* qNode=qItem->objectptr; + if(qNode->id==node->id){ + return; + } + qItem=getNextQueueItem(qItem); + } + } + + addNewItem(connectedList,node); + +} diff --git a/Robust/src/Runtime/mlp_runtime.h b/Robust/src/Runtime/mlp_runtime.h index 16adef36..99c8c426 100644 --- a/Robust/src/Runtime/mlp_runtime.h +++ b/Robust/src/Runtime/mlp_runtime.h @@ -15,12 +15,16 @@ #define TRUE 1 #endif -// each allocation site nees the following +// each allocation site needs the following typedef struct AllocSite_t{ long id; struct Queue* waitingQueue; } AllocSite; +typedef struct ConflictNode_t{ + int id; +} ConflictNode; + // forward declaration of pointer type typedef struct SESEcommon_t* SESEcommon_p; @@ -57,6 +61,7 @@ typedef struct SESEcommon_t { AllocSite* allocSiteArray; int numRelatedAllocSites; psemaphore memoryStallSiteSem; + struct Queue* connectedList; } SESEcommon; @@ -77,6 +82,7 @@ void* mlpCreateSESErecord( int size ); void mlpDestroySESErecord( void* seseRecord ); AllocSite* mlpCreateAllocSiteArray(int numAllocSites); +ConflictNode* mlpCreateConflictNode(int id); #endif /* __MLP_RUNTIME__ */ -- 2.34.1