import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.Collection;
+import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
private boolean compareHRNSet(Set<HeapRegionNode> setA,
Set<HeapRegionNode> setB) {
-
+ boolean found = false;
for (Iterator iterator = setA.iterator(); iterator.hasNext();) {
HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next();
String gID = heapRegionNode.getGloballyUniqueIdentifier();
- boolean found = false;
for (Iterator iterator2 = setB.iterator(); iterator2.hasNext();) {
HeapRegionNode heapRegionNode2 = (HeapRegionNode) iterator2
.next();
found = true;
}
}
- if (!found) {
- return false;
- }
+ }
+ if (!found) {
+ return false;
}
return true;
}
&& seseLock
.containsConflictEdge(conflictEdge)) {
WaitingElement newElement = new WaitingElement();
- newElement.setWaitingID(seseLock.getID());
+ newElement.setQueueID(seseLock.getID());
if (isFineElement(newElement.getStatus())) {
newElement
.setDynID(node
}
- public Set<WaitingElement> getWaitingElementSetBySESEID(int seseID,
+ public SESEWaitingQueue getWaitingElementSetBySESEID(int seseID,
HashSet<SESELock> seseLockSet) {
HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
&& seseLock
.containsConflictEdge(conflictEdge)) {
WaitingElement newElement = new WaitingElement();
- newElement.setWaitingID(seseLock.getID());
+ newElement.setQueueID(seseLock.getID());
newElement.setStatus(seseLock
.getNodeType(liveInNode));
if (isFineElement(newElement.getStatus())) {
}
}
+
+ //handle the case that multiple enqueues by an SESE for different live-in into the same queue
+ return refineQueue(waitingElementSet);
+// return waitingElementSet;
+
+ }
+
+ public SESEWaitingQueue refineQueue(Set<WaitingElement> waitingElementSet) {
+
+ Set<WaitingElement> refinedSet=new HashSet<WaitingElement>();
+ HashMap<Integer, Set<WaitingElement>> map = new HashMap<Integer, Set<WaitingElement>>();
+ SESEWaitingQueue seseDS=new SESEWaitingQueue();
+
+ for (Iterator iterator = waitingElementSet.iterator(); iterator
+ .hasNext();) {
+ WaitingElement waitingElement = (WaitingElement) iterator.next();
+ Set<WaitingElement> set=map.get(new Integer(waitingElement.getQueueID()));
+ if(set==null){
+ set=new HashSet<WaitingElement>();
+ }
+ set.add(waitingElement);
+ map.put(new Integer(waitingElement.getQueueID()), set);
+ }
+
+ Set<Integer> keySet=map.keySet();
+ for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+ Integer queueID = (Integer) iterator.next();
+ Set<WaitingElement> queueWEset=map.get(queueID);
+ refineQueue(queueID.intValue(),queueWEset,seseDS);
+ }
+
+ return seseDS;
+ }
+
+ private void refineQueue(int queueID,
+ Set<WaitingElement> waitingElementSet, SESEWaitingQueue seseDS) {
- return waitingElementSet;
+ if (waitingElementSet.size() > 1) {
+ //only consider there is more than one element submitted by same SESE
+ Set<WaitingElement> refinedSet = new HashSet<WaitingElement>();
+
+ int numCoarse = 0;
+ int numRead = 0;
+ int numWrite = 0;
+ int total=waitingElementSet.size();
+ WaitingElement SCCelement = null;
+ WaitingElement coarseElement = null;
+
+ for (Iterator iterator = waitingElementSet.iterator(); iterator
+ .hasNext();) {
+ WaitingElement waitingElement = (WaitingElement) iterator
+ .next();
+ if (waitingElement.getStatus() == ConflictNode.FINE_READ) {
+ numRead++;
+ } else if (waitingElement.getStatus() == ConflictNode.FINE_WRITE) {
+ numWrite++;
+ } else if (waitingElement.getStatus() == ConflictNode.COARSE) {
+ numCoarse++;
+ coarseElement = waitingElement;
+ } else if (waitingElement.getStatus() == ConflictNode.SCC) {
+ SCCelement = waitingElement;
+ }
+ }
+
+ if (SCCelement != null) {
+ // if there is at lease one SCC element, just enqueue SCC and
+ // ignore others.
+ refinedSet.add(SCCelement);
+ } else if (numCoarse == 1 && (numRead + numWrite == total)) {
+ // if one is a coarse, the othere are reads/write, enqueue SCC.
+ WaitingElement we = new WaitingElement();
+ we.setQueueID(queueID);
+ we.setStatus(ConflictNode.SCC);
+ refinedSet.add(we);
+ } else if (numCoarse == total) {
+ // if there are multiple coarses, enqueue just one coarse.
+ refinedSet.add(coarseElement);
+ } else if(numWrite==total || (numRead+numWrite)==total){
+ // code generator is going to handle the case for multiple writes & read/writes.
+ seseDS.setType(queueID, SESEWaitingQueue.EXCEPTION);
+ refinedSet.addAll(waitingElementSet);
+ } else{
+ // otherwise, enqueue everything.
+ refinedSet.addAll(waitingElementSet);
+ }
+ seseDS.setWaitingElementSet(queueID, refinedSet);
+ } else {
+ seseDS.setWaitingElementSet(queueID, waitingElementSet);
+ }
+
}
public boolean isFineElement(int type) {
HeapRegionNode heapRegionNode = (HeapRegionNode) iterator
.next();
String gID = heapRegionNode.getGloballyUniqueIdentifier();
- boolean found = false;
for (Iterator iterator2 = setB.iterator(); iterator2.hasNext();) {
HeapRegionNode heapRegionNode2 = (HeapRegionNode) iterator2
.next();
Set<HeapRegionNode> entryHRNSet = getSameHeapRoot(liveInHrnSetA,
liveInHrnSetB);
- if (entryHRNSet.size() == 0) {
+ if (entryHRNSet.size() == 0 ) {
+ return ConflictEdge.COARSE_GRAIN_EDGE;
+ }
+ if(entryHRNSet.size()!=liveInHrnSetA.size() || entryHRNSet.size()!=liveInHrnSetB.size()){
return ConflictEdge.COARSE_GRAIN_EDGE;
}
return getVertexU() + "-" + getVertexV();
}
-}
\ No newline at end of file
+}
--- /dev/null
+package Analysis.MLP;
+
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Set;
+
+public class SESEWaitingQueue {
+ public static final int NORMAL= 0; // enqueue all stuff.
+ public static final int EXCEPTION= 1; // dynamically decide whether a waiting element is enqueued or not.
+
+ private HashMap<Integer, Set<WaitingElement>>mapWaitingElement;
+ private HashMap<Integer, Integer>mapType;
+
+ public SESEWaitingQueue(){
+ mapWaitingElement=new HashMap<Integer, Set<WaitingElement>>();
+ mapType=new HashMap<Integer, Integer>();
+ }
+
+ public void setType(int queueID, int type){
+ mapType.put(new Integer(queueID), new Integer(type));
+ }
+
+ public int getType(int queueID){
+ Integer type=mapType.get(new Integer(queueID));
+ if(type==null){
+ return SESEWaitingQueue.NORMAL;
+ }else{
+ return type.intValue();
+ }
+ }
+
+ public void setWaitingElementSet(int queueID, Set<WaitingElement> set){
+ mapWaitingElement.put(new Integer(queueID), set);
+ }
+
+ public Set<WaitingElement> getWaitingElementSet(int queueID){
+ return mapWaitingElement.get(new Integer(queueID));
+ }
+
+ public Set<Integer> getQueueIDSet(){
+ return mapWaitingElement.keySet();
+ }
+
+ public int getWaitingElementSize(){
+ int size=0;
+ Set<Integer> keySet=mapWaitingElement.keySet();
+ for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+ Integer key = (Integer) iterator.next();
+ size+=mapWaitingElement.get(key).size();
+ }
+ return size;
+ }
+}
public class WaitingElement {
- private int waitingID;
+ private int queueID;
private int status;
private String dynID="";
private TempDescriptor tempDesc;
return tempDesc;
}
- public void setWaitingID(int waitingID) {
- this.waitingID = waitingID;
+ public void setQueueID(int queueID) {
+ this.queueID = queueID;
}
public String getDynID(){
}
public int getQueueID() {
- return waitingID;
+ return queueID;
}
public void setStatus(int status) {
WaitingElement in = (WaitingElement) o;
- if (waitingID == in.getQueueID() && status == in.getStatus() && dynID.equals(in.getDynID()) ) {
+ if (queueID == in.getQueueID() && status == in.getStatus() && dynID.equals(in.getDynID()) ) {
return true;
} else {
return false;
}
public String toString() {
- return "[waitingID=" + waitingID + " status=" + status + " dynID="
+ return "[waitingID=" + queueID + " status=" + status + " dynID="
+ dynID + "]";
}
int hash = 1;
- hash = hash * 31 + waitingID;
+ hash = hash * 31 + queueID;
hash += status;
import Analysis.MLP.MLPAnalysis;
import Analysis.MLP.ParentChildConflictsMap;
import Analysis.MLP.SESELock;
+import Analysis.MLP.SESEWaitingQueue;
import Analysis.MLP.VariableSourceToken;
import Analysis.MLP.VSTWrapper;
import Analysis.MLP.CodePlan;
.get(graph);
output.println();
output.println(" //add memory queue element");
- Set<WaitingElement> waitingQueueSet = graph
- .getWaitingElementSetBySESEID(fsen.getIdentifier(),
- seseLockSet);
- if (waitingQueueSet.size() > 0) {
+ SESEWaitingQueue seseWaitingQueue=graph.getWaitingElementSetBySESEID(fsen.getIdentifier(),
+ seseLockSet);
+ if(seseWaitingQueue.getWaitingElementSize()>0){
output.println(" {");
output.println(" REntry* rentry=NULL;");
output.println(" INTPTR* pointer=NULL;");
output.println(" seseToIssue->common.rentryIdx=0;");
- for (Iterator iterator = waitingQueueSet.iterator(); iterator
+
+ Set<Integer> queueIDSet=seseWaitingQueue.getQueueIDSet();
+ for (Iterator iterator = queueIDSet.iterator(); iterator
.hasNext();) {
- WaitingElement waitingElement = (WaitingElement) iterator
- .next();
-
- if (waitingElement.getStatus() >= ConflictNode.COARSE) {
- output.println(" rentry=mlpCreateREntry("
- + waitingElement.getStatus()
- + ", seseToIssue);");
- } else {
- TempDescriptor td = waitingElement.getTempDesc();
- // decide whether waiting element is dynamic or
- // static
- if(fsen.getDynamicInVarSet().contains(td)){
- // dynamic in-var case
- output.println(" pointer=seseToIssue->"+ waitingElement.getDynID()+"_srcSESE+seseToIssue->"+ waitingElement.getDynID()+"_srcOffset;");
- output.println(" rentry=mlpCreateFineREntry("
+ Integer key = (Integer) iterator.next();
+ int queueID=key.intValue();
+ Set<WaitingElement> waitingQueueSet = seseWaitingQueue.getWaitingElementSet(queueID);
+ int enqueueType=seseWaitingQueue.getType(queueID);
+ if(enqueueType==SESEWaitingQueue.EXCEPTION){
+ output.println(" INITIALIZEBUF(parentCommon->memoryQueueArray["
+ + queueID+ "]);");
+ }
+ for (Iterator iterator2 = waitingQueueSet.iterator(); iterator2
+ .hasNext();) {
+ WaitingElement waitingElement = (WaitingElement) iterator2
+ .next();
+ if (waitingElement.getStatus() >= ConflictNode.COARSE) {
+ output.println(" rentry=mlpCreateREntry("
+ waitingElement.getStatus()
- + ", seseToIssue, pointer );");
-// output.println(" rentry=mlpCreateFineREntry("
-// + waitingElement.getStatus()
-// + ", seseToIssue, seseToIssue->"
-// + waitingElement.getDynID() + "->oid);");
- }else if(fsen.getStaticInVarSet().contains(td)){
- // static in-var case
- VariableSourceToken vst = fsen.getStaticInVarSrc(td);
- if (vst != null) {
-
- String srcId = "SESE_"
- + vst.getSESE()
- .getPrettyIdentifier()
- + vst.getSESE().getIdentifier()
- + "_" + vst.getAge();
- output
- .println(" pointer=(void*)&seseToIssue->"
- + srcId
- + "->"
+ + ", seseToIssue);");
+ } else {
+ TempDescriptor td = waitingElement
+ .getTempDesc();
+ // decide whether waiting element is dynamic or
+ // static
+ if (fsen.getDynamicInVarSet().contains(td)) {
+ // dynamic in-var case
+ output.println(" pointer=seseToIssue->"
+ + waitingElement.getDynID()
+ + "_srcSESE+seseToIssue->"
+ waitingElement.getDynID()
- + ";");
- output.println(" rentry=mlpCreateFineREntry("
- + waitingElement.getStatus()
- + ", seseToIssue, pointer );");
-
-// output.println(" rentry=mlpCreateFineREntry("
-// + waitingElement.getStatus()
-// + ", seseToIssue, seseToIssue->"
-// + waitingElement.getDynID() + "->oid);");
+ + "_srcOffset;");
+ output
+ .println(" rentry=mlpCreateFineREntry("
+ + waitingElement
+ .getStatus()
+ + ", seseToIssue, pointer );");
+ } else if (fsen.getStaticInVarSet()
+ .contains(td)) {
+ // static in-var case
+ VariableSourceToken vst = fsen
+ .getStaticInVarSrc(td);
+ if (vst != null) {
+
+ String srcId = "SESE_"
+ + vst.getSESE()
+ .getPrettyIdentifier()
+ + vst.getSESE().getIdentifier()
+ + "_" + vst.getAge();
+ output
+ .println(" pointer=(void*)&seseToIssue->"
+ + srcId
+ + "->"
+ + waitingElement
+ .getDynID()
+ + ";");
+ output
+ .println(" rentry=mlpCreateFineREntry("
+ + waitingElement
+ .getStatus()
+ + ", seseToIssue, pointer );");
+
+ }
+ } else {
+ output
+ .println(" rentry=mlpCreateFineREntry("
+ + waitingElement
+ .getStatus()
+ + ", seseToIssue, (void*)&seseToIssue->"
+ + waitingElement.getDynID()
+ + ");");
}
- }else{
- output.println(" rentry=mlpCreateFineREntry("
- + waitingElement.getStatus()
- + ", seseToIssue, (void*)&seseToIssue->"
- + waitingElement.getDynID() + ");");
-// output.println(" rentry=mlpCreateFineREntry("
-// + waitingElement.getStatus()
-// + ", seseToIssue, seseToIssue->"
-// + waitingElement.getDynID() + "->oid);");
}
- }
- output
- .println(" rentry->queue=parentCommon->memoryQueueArray["
- + waitingElement.getQueueID() + "];");
- output
+ output
+ .println(" rentry->queue=parentCommon->memoryQueueArray["
+ + waitingElement.getQueueID()
+ + "];");
+
+ if(enqueueType==SESEWaitingQueue.NORMAL){
+ output
.println(" seseToIssue->common.rentryArray[seseToIssue->common.rentryIdx++]=rentry;");
- output
- .println(" if(ADDRENTRY(parentCommon->memoryQueueArray["
+ output
+ .println(" if(ADDRENTRY(parentCommon->memoryQueueArray["
+ + waitingElement.getQueueID()
+ + "],rentry)==NOTREADY){");
+ output.println(" ++(localCount);");
+ output.println(" } ");
+ }else{
+ output
+ .println(" ADDRENTRYTOBUF(parentCommon->memoryQueueArray["
+ waitingElement.getQueueID()
- + "],rentry)==NOTREADY){");
- output.println(" ++(localCount);");
- output.println(" } ");
- output.println();
+ + "],rentry);");
+ }
+ }
+ if(enqueueType!=SESEWaitingQueue.NORMAL){
+ output.println(" localCount+=RESOLVEBUF(parentCommon->memoryQueueArray["
+ + queueID+ "],&seseToIssue->common);");
+ }
}
output.println(" }");
}
output.println();
}
-
////////////////
-
-
}
// release this SESE for siblings to update its dependencies or,
int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
int status, retval;
- if (readbintail->item.status=READY) {
+ if (readbintail->item.status==READY) {
status=READY;
retval=READY;
if (isParent(r)) {
}
}
+void INITIALIZEBUF(MemoryQueue * q){
+ int i=0;
+ for(i=0; i<NUMBINS; i++){
+ q->binbuf[i]=NULL;
+ }
+ q->bufcount=0;
+}
+
+void ADDRENTRYTOBUF(MemoryQueue * q, REntry * r){
+ q->buf[q->bufcount]=r;
+ q->bufcount++;
+}
+
+int RESOLVEBUFFORHASHTABLE(MemoryQueue * q, Hashtable* table, SESEcommon *seseCommon){
+ int i;
+ // first phase: only consider write rentry
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r->type==WRITE){
+ int key=generateKey(r->oid);
+ if(q->binbuf[key]==NULL){
+ // for multiple writes, add only the first write that hashes to the same bin
+ q->binbuf[key]=r;
+ }else{
+ q->buf[i]=NULL;
+ }
+ }
+ }
+ // second phase: enqueue read items if it is eligible
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r!=NULL && r->type==READ){
+ int key=generateKey(r->oid);
+ if(q->binbuf[key]==NULL){
+ // read item that hashes to the bin which doen't contain any write
+ seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
+ if(ADDTABLEITEM(table, r, FALSE)==READY){
+ resolveDependencies(r);
+ }
+ }
+ q->buf[i]=NULL;
+ }
+ }
+
+ // then, add only one of write items that hashes to the same bin
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r!=NULL){
+ seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
+ if(ADDTABLEITEM(table, r, FALSE)==READY){
+ resolveDependencies(r);
+ }
+ }
+ }
+}
+
+int RESOLVEBUF(MemoryQueue * q, SESEcommon *seseCommon){
+ int localCount=0;
+ int i;
+ // check if every waiting entry is resolved
+ // if not, defer every items for hashtable until it is resolved.
+ int unresolved=FALSE;
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(*(r->pointer)==0){
+ unresolved=TRUE;
+ }
+ }
+ if(unresolved==TRUE){
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ r->queue=q;
+ r->isBufMode=TRUE;
+ if(ADDRENTRY(q,r)==NOTREADY){
+ localCount++;
+ }
+ }
+ return localCount;
+ }
+
+ // first phase: only consider write rentry
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r->type==WRITE){
+ int key=generateKey(r->oid);
+ if(q->binbuf[key]==NULL){
+ // for multiple writes, add only the first write that hashes to the same bin
+ q->binbuf[key]=r;
+ }else{
+ q->buf[i]=NULL;
+ }
+ }
+ }
+ // second phase: enqueue read items if it is eligible
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r!=NULL && r->type==READ){
+ int key=generateKey(r->oid);
+ if(q->binbuf[key]==NULL){
+ // read item that hashes to the bin which doen't contain any write
+ seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
+ if(ADDRENTRY(q,r)==NOTREADY){
+ localCount++;
+ }
+ }
+ q->buf[i]=NULL;
+ }
+ }
+
+ // then, add only one of write items that hashes to the same bin
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r!=NULL){
+ seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
+ if(ADDRENTRY(q,r)==NOTREADY){
+ localCount++;
+ }
+ }
+ }
+ return localCount;
+}
+
+
resolvePointer(REntry* rentry){
Hashtable* table=rentry->hashtable;
+ MemoryQueue* queue;
if(table==NULL){
//resolved already before related rentry is enqueued to the waiting queue
return;
if(val!=NULL && getHead(val)->objectptr==rentry){
// handling pointer is the first item of the queue
// start to resolve until it reaches unresolved pointer or end of queue
+ INTPTR currentSESE=0;
do{
struct QueueItem* head=getHead(val);
if(head!=NULL){
//now, address is resolved. update OID field.
struct ___Object___ * obj=(struct ___Object___*)((unsigned INTPTR)*rentry->pointer);
rentry->oid=obj->oid;
- if(ADDTABLEITEM(table, rentry, FALSE)==READY){
- resolveDependencies(rentry);
+
+ //check if rentry is buffer mode
+ if(rentry->isBufMode==TRUE){
+ if(currentSESE==0){
+ queue=rentry->queue;
+ INITIALIZEBUF(queue);
+ currentSESE=(INTPTR)rentry;
+ ADDRENTRYTOBUF(queue,rentry);
+ } else if(currentSESE==(INTPTR)rentry){
+ ADDRENTRYTOBUF(queue,rentry);
+ } else if(currentSESE!=(INTPTR)rentry){
+ RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
+ currentSESE=(INTPTR)rentry;
+ INITIALIZEBUF(queue);
+ ADDRENTRYTOBUF(rentry->queue,rentry);
+ }
+ }else{
+ if(currentSESE!=0){
+ //previous SESE has buf mode, need to invoke resolve buffer
+ RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
+ currentSESE=0;
+ }
+ //normal mode
+ if(ADDTABLEITEM(table, rentry, FALSE)==READY){
+ resolveDependencies(rentry);
+ }
}
}else{
table->unresolvedQueue=NULL; // set hashtable as normal-mode.
void* seseRec;
INTPTR* pointer;
int oid;
+ int isBufMode;
} REntry;
typedef struct MemoryQueueItem_t {
int type; // hashtable:0, vector:1, singleitem:2
int total; //total non-retired
int status; //NOTREADY, READY
- struct MemoryQueueItem_t *next;
+ struct MemoryQueueItem_t *next;
} MemoryQueueItem;
typedef struct MemoryQueue_t {
MemoryQueueItem * head;
MemoryQueueItem * tail;
+ REntry * binbuf[NUMBINS];
+ REntry * buf[NUMRENTRY];
+ int bufcount;
} MemoryQueue;
typedef struct BinItem_t {
projects / IRC.git / commitdiff