From 4da6c0eeeab1ffc76a4ee5e8cc1a2f992e90c18a Mon Sep 17 00:00:00 2001 From: jzhou Date: Wed, 22 Oct 2008 22:35:30 +0000 Subject: [PATCH] Integrate Jim's ownership ananlysis and fix some bugs in scheduling simulator --- .../Analysis/Scheduling/CombinationUtil.java | 4 + .../Analysis/Scheduling/CoreSimulator.java | 52 +- .../Analysis/Scheduling/FIFORSchedule.java | 2 + .../Analysis/Scheduling/ScheduleAnalysis.java | 17 +- .../src/Analysis/Scheduling/ScheduleNode.java | 1 + .../Scheduling/ScheduleSimulator.java | 34 +- .../Analysis/Scheduling/SchedulingUtil.java | 64 ++- .../Analysis/Scheduling/TaskSimulator.java | 13 +- .../src/Analysis/TaskStateAnalysis/FEdge.java | 23 +- .../Analysis/TaskStateAnalysis/FlagState.java | 22 +- .../TaskStateAnalysis/TaskAnalysis.java | 1 + Robust/src/IR/Flat/BuildCodeMultiCore.java | 332 +++++++++++- Robust/src/Main/Main.java | 479 ++++++++++-------- Robust/src/Runtime/multicoreruntime.c | 8 + Robust/src/Runtime/multicoretask.c | 453 ++++++++++------- Robust/src/Runtime/runtime.h | 5 +- Robust/src/Runtime/task.c | 2 +- Robust/src/Util/GraphNode.java | 2 +- 18 files changed, 1029 insertions(+), 485 deletions(-) diff --git a/Robust/src/Analysis/Scheduling/CombinationUtil.java b/Robust/src/Analysis/Scheduling/CombinationUtil.java index 3cf00d37..30bf2078 100644 --- a/Robust/src/Analysis/Scheduling/CombinationUtil.java +++ b/Robust/src/Analysis/Scheduling/CombinationUtil.java @@ -50,6 +50,7 @@ public class CombinationUtil { } int next = 1; trial = trial(num2choose, next); + toadd = null; } else { if(this.rootNodes.size() == 1) { return false; @@ -89,6 +90,7 @@ public class CombinationUtil { for(index = 0; index < toadd.size(); index++) { this.node2Combine.lastElement().add(toadd.elementAt(index)); } + toadd = null; } else { this.node2Combine.add(null); } @@ -101,6 +103,7 @@ public class CombinationUtil { this.node2Combine.lastElement().add(toadd.elementAt(index)); } } + toadd = null; next++; } while(next < this.sNodeVecs.size()) { @@ -110,6 +113,7 @@ public class CombinationUtil { for(index = 0; index < toadd.size(); index++) { this.node2Combine.lastElement().add(toadd.elementAt(index)); } + toadd = null; } else { this.node2Combine.add(null); } diff --git a/Robust/src/Analysis/Scheduling/CoreSimulator.java b/Robust/src/Analysis/Scheduling/CoreSimulator.java index 29e78b25..0bc4543b 100644 --- a/Robust/src/Analysis/Scheduling/CoreSimulator.java +++ b/Robust/src/Analysis/Scheduling/CoreSimulator.java @@ -135,38 +135,42 @@ public class CoreSimulator { assert(this.rtask != null); Vector transObjs = null; - Vector> paraQueues = this.rtask.getParaQueues(); - for(int i = 0; i < paraQueues.size(); i++) { - ObjectSimulator obj = paraQueues.elementAt(i).poll(); - obj.setHold(false); - boolean remove = false; - if((this.targetFState != null) && (this.targetFState.containsKey(obj.getCurrentFS()))) { - if(transObjs == null) { - transObjs = new Vector(); - } - if(!transObjs.contains(obj)) { - transObjs.add(obj); - } - remove = true; - } - // check if this object becoming shared or not - Vector allycores = this.getAllyCores(obj.getCurrentFS()); - if(allycores != null) { - obj.setShared(true); - for(int k = 0; k < allycores.size(); ++k) { - Integer allyCore = allycores.elementAt(k); + if(this.rtask.currentRun.getExetype() == 0) { + Vector> paraQueues = this.rtask.getParaQueues(); + for(int i = 0; i < paraQueues.size(); i++) { + ObjectSimulator obj = paraQueues.elementAt(i).poll(); + obj.setHold(false); + boolean remove = false; + if((this.targetFState != null) && (this.targetFState.containsKey(obj.getCurrentFS()))) { if(transObjs == null) { transObjs = new Vector(); } if(!transObjs.contains(obj)) { transObjs.add(obj); } - remove = false; + remove = true; + } + // check if this object becoming shared or not + Vector allycores = this.getAllyCores(obj.getCurrentFS()); + if(allycores != null) { + obj.setShared(true); + for(int k = 0; k < allycores.size(); ++k) { + //Integer allyCore = allycores.elementAt(k); + if(transObjs == null) { + transObjs = new Vector(); + } + if(!transObjs.contains(obj)) { + transObjs.add(obj); + } + remove = false; + } + allycores = null; + } + for(int j = 0; j < this.tasks.size(); j++) { + this.tasks.elementAt(j).refreshPara(obj, remove); } } - for(int j = 0; j < this.tasks.size(); j++) { - this.tasks.elementAt(j).refreshPara(obj, remove); - } + paraQueues = null; } this.activeTime += this.rtask.getCurrentRun().getFinishTime(); this.rtask.finish(); diff --git a/Robust/src/Analysis/Scheduling/FIFORSchedule.java b/Robust/src/Analysis/Scheduling/FIFORSchedule.java index 6a247404..d8f4e672 100644 --- a/Robust/src/Analysis/Scheduling/FIFORSchedule.java +++ b/Robust/src/Analysis/Scheduling/FIFORSchedule.java @@ -38,8 +38,10 @@ public class FIFORSchedule extends RuntimeSchedule { } } if(j == pqueues.size()) { + pqueues = null; return next; } + pqueues = null; } if(i == tasks.size()) { return null; diff --git a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java index d5932d53..94b887ec 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java +++ b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java @@ -211,6 +211,7 @@ public class ScheduleAnalysis { } } } + toVisit = null; SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes); } @@ -554,6 +555,8 @@ public class ScheduleAnalysis { clone = null; qcn2cn = null; cn2cn = null; + origins = null; + sn2sn = null; } private int calInExeTime(FlagState fs) throws Exception { @@ -697,6 +700,7 @@ public class ScheduleAnalysis { } se.getSource().getEdgeVector().removeAll(toremove); toremove = null; + rCNodes = null; sFStates = null; try { @@ -828,6 +832,7 @@ public class ScheduleAnalysis { if(!tmpcores.contains(tmpSchedule)) { tmpcores.add(tmpSchedule); } + tmpcores = null; // if the FlagState can be fed to some multi-param tasks, // need to record corresponding ally cores later if(td.numParameters() > 1) { @@ -842,6 +847,7 @@ public class ScheduleAnalysis { } } } + cNodes = null; // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn Iterator it_edges = sn.edges(); @@ -935,9 +941,11 @@ public class ScheduleAnalysis { } } } + tmpcores = null; } } } + tmptds = null; } if(cores.size() > 1) { @@ -949,13 +957,20 @@ public class ScheduleAnalysis { } } } + tmpfss = null; } } + fes = null; + cores = null; } } - this.schedulings.add(scheduling); + td2cores = null; + scheduleGraph = null; + scheduling = null; + sn2coreNum = null; } + multiparamtds = null; } public Vector generateScheduling(Vector> rootnodes, Vector> combine, int gid) { diff --git a/Robust/src/Analysis/Scheduling/ScheduleNode.java b/Robust/src/Analysis/Scheduling/ScheduleNode.java index e55bf2e5..273473a7 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleNode.java +++ b/Robust/src/Analysis/Scheduling/ScheduleNode.java @@ -260,6 +260,7 @@ public class ScheduleNode extends GraphNode implements Cloneable { Vector sfss = scn.getFlagStates(); sfss.addAll(tcn.getFlagStates()); sfss.removeElement(tfs); + sfss = null; classNodes.removeElement(tcn); // flush the exeTime of fs and its ancestors diff --git a/Robust/src/Analysis/Scheduling/ScheduleSimulator.java b/Robust/src/Analysis/Scheduling/ScheduleSimulator.java index 00b9ca02..fe80bc83 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleSimulator.java +++ b/Robust/src/Analysis/Scheduling/ScheduleSimulator.java @@ -257,10 +257,12 @@ public class ScheduleSimulator { } Queue tmpqueue = transObjQueues.get(targetCore); tmpqueue.add(new ObjectInfo(nobj)); + tmpqueue = null; } // enqueue this core again cores.add(targetCore); } + cores = null; // check if this object becoming shared or not Vector allycores = cs.getAllyCores(nobj.getCurrentFS()); if(allycores != null) { @@ -278,10 +280,13 @@ public class ScheduleSimulator { if(!tmpqueue.contains(nobjinfo)) { tmpqueue.add(nobjinfo); } + tmpqueue = null; } } + allycores = null; } } + nobjs = null; } cp.addAction(action); Vector transObjs = cs.finishTask(); @@ -305,7 +310,9 @@ public class ScheduleSimulator { } Queue tmpqueue = transObjQueues.get(targetCore); tmpqueue.add(new ObjectInfo(tobj)); + tmpqueue = null; } + cores = null; } // check if this object becoming shared or not Vector allycores = cs.getAllyCores(tobj.getCurrentFS()); @@ -324,10 +331,13 @@ public class ScheduleSimulator { if(!tmpqueue.contains(nobjinfo)) { tmpqueue.add(nobjinfo); } + tmpqueue = null; } } + allycores = null; } } + transObjs = null; } // add 'transport' tasks Iterator it_entries = transObjQueues.entrySet().iterator(); @@ -337,28 +347,34 @@ public class ScheduleSimulator { Queue nobjs = tmpentry.getValue(); TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs); this.tasks.add(tmptask); + tmpentry = null; + nobjs = null; } - // Choose a new task for this core - TaskSimulator newTask = cs.process(); - if(newTask != null) { - this.tasks.add(newTask); - // add a TASKSTART action into this checkpoint - action = new Action(coreNum, Action.TASKSTART); - action.setTd(cs.getRtask().getTd()); - cp.addAction(action); - } + transObjQueues = null; } else if (task.getCurrentRun().getExetype() == 1) { action = new Action(coreNum, Action.TASKABORT); action.setTd(cs.getRtask().getTd()); cp.addAction(action); + Vector transObjs = cs.finishTask(); } else if (task.getCurrentRun().getExetype() == 2) { action = new Action(coreNum, Action.TASKREMOVE); action.setTd(cs.getRtask().getTd()); cp.addAction(action); + Vector transObjs = cs.finishTask(); + } + // Choose a new task for this core + TaskSimulator newTask = cs.process(); + if(newTask != null) { + this.tasks.add(newTask); + // add a TASKSTART action into this checkpoint + action = new Action(coreNum, Action.TASKSTART); + action.setTd(cs.getRtask().getTd()); + cp.addAction(action); } } } this.checkpoints.add(cp); + finishTasks = null; } SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime, diff --git a/Robust/src/Analysis/Scheduling/SchedulingUtil.java b/Robust/src/Analysis/Scheduling/SchedulingUtil.java index c39791a8..09f59c12 100644 --- a/Robust/src/Analysis/Scheduling/SchedulingUtil.java +++ b/Robust/src/Analysis/Scheduling/SchedulingUtil.java @@ -508,8 +508,14 @@ public class SchedulingUtil { output.print(tmpTaskNode); output.print("; "); } + keys = null; output.println("}"); output.print("\t"); + tmplastTasks = null; + tmpisTaskFinish = null; + tmpisset = null; + actions = null; + tmpTaskNodes = null; } output.print("\t"); output.print("\t"); @@ -518,45 +524,49 @@ public class SchedulingUtil { int max = 0; int max2 = 0; for(j = 1; j < timeNodes.size(); j++) { - next = Integer.parseInt(timeNodes.elementAt(j)); - int delta = next - prev; - if(max < delta) { - max2 = max; - max = delta; - } else if((max != delta) && (max2 < delta)) { - max2 = delta; - } - prev = next; + next = Integer.parseInt(timeNodes.elementAt(j)); + int delta = next - prev; + if(max < delta) { + max2 = max; + max = delta; + } else if((max != delta) && (max2 < delta)) { + max2 = delta; + } + prev = next; } if(max2 == 0) { - max2 = 1; + max2 = 1; } else if(max/max2 > 100) { - max2 = max/100; + max2 = max/100; } output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];"); prev = Integer.parseInt(timeNodes.elementAt(0)); next = 0; for(j = 1; j < timeNodes.size(); j++) { - next = Integer.parseInt(timeNodes.elementAt(j)); - if(next - prev > max2) { - do { - output.print(prev + "->"); - prev += max2; - }while(next - prev > max2); - output.println(next + ";"); - } else { - output.println("{rank=same; rankdir=LR; " + prev + "; " + next + "}"); - output.println(prev + "->" + next + "[style=invis];"); - } - prev = next; + next = Integer.parseInt(timeNodes.elementAt(j)); + if(next - prev > max2) { + do { + output.print(prev + "->"); + prev += max2; + } while(next - prev > max2); + output.println(next + ";"); + } else { + output.println("{rank=same; rankdir=LR; " + prev + "; " + next + "}"); + output.println(prev + "->" + next + "[style=invis];"); + } + prev = next; } - + /*for(j = 0; j < time; j++) { - output.print(j + "->"); - } - output.println(timeNodes.lastElement() + ";");*/ + output.print(j + "->"); + } + output.println(timeNodes.lastElement() + ";");*/ output.println("}"); output.close(); + timeNodes = null; + lastTaskNodes = null; + lastTasks = null; + isTaskFinish = null; } catch (Exception e) { e.printStackTrace(); System.exit(-1); diff --git a/Robust/src/Analysis/Scheduling/TaskSimulator.java b/Robust/src/Analysis/Scheduling/TaskSimulator.java index 8748bb8b..6e5c6eb4 100644 --- a/Robust/src/Analysis/Scheduling/TaskSimulator.java +++ b/Robust/src/Analysis/Scheduling/TaskSimulator.java @@ -61,6 +61,13 @@ public class TaskSimulator { public void setExetype(int exetype) { this.exetype = exetype; } + + public void init() { + finishTime = 0; + if(newObjs != null) { + newObjs.clear(); + } + } } public TaskSimulator(TaskDescriptor td, CoreSimulator cs) { @@ -188,6 +195,8 @@ public class TaskSimulator { if(this.currentRun == null) { this.currentRun = new ExeResult(); + } else { + this.currentRun.init(); } int finishTime = 0; @@ -204,7 +213,7 @@ public class TaskSimulator { if(tpara.isShared()) { if(tpara.isHold()) { // shared object held by other tasks - finishTime = 1; // TODO currenly assume the effort on requesting locks are only 1 + finishTime = 800; // TODO currenly assume the effort on requesting locks are only 1 this.currentRun.setFinishTime(finishTime); this.currentRun.setExetype(1); paraQueues.elementAt(i).poll(); @@ -219,7 +228,7 @@ public class TaskSimulator { return; } else if (tpara.getVersion() != this.objVersionTbl.get(tpara)) { // shared object has been updated and no longer fitted to this task - finishTime = 1; // TODO currenly assume the effort on requesting locks are only 1 + finishTime = 800; // TODO currenly assume the effort on requesting locks are only 1 this.currentRun.setFinishTime(finishTime); this.currentRun.setExetype(2); paraQueues.elementAt(i).poll(); diff --git a/Robust/src/Analysis/TaskStateAnalysis/FEdge.java b/Robust/src/Analysis/TaskStateAnalysis/FEdge.java index 4b589b54..cb471860 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FEdge.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FEdge.java @@ -1,8 +1,5 @@ package Analysis.TaskStateAnalysis; import IR.*; -import Analysis.TaskStateAnalysis.*; -import IR.Tree.*; -import IR.Flat.*; import java.util.*; import Util.Edge; @@ -17,9 +14,10 @@ public class FEdge extends Edge { // jzhou private int executeTime; private Hashtable newObjInfos; - private int probability; + private double probability; private int invokeNum; private int expInvokeNum; + private boolean m_isbackedge; public class NewObjInfo { int newRate; @@ -98,16 +96,25 @@ public class FEdge extends Edge { this.probability = -1; this.invokeNum = 0; this.expInvokeNum = 0; + this.m_isbackedge = false; } - public int getProbability() { - return probability; + public double getProbability() { + return this.probability; } - public void setProbability(int probability) { + public void setProbability(double probability) { this.probability = probability; } + public boolean isbackedge() { + return m_isbackedge; + } + + public void setisbackedge(boolean isbackedge) { + this.m_isbackedge = isbackedge; + } + public String getLabel() { return label; } @@ -187,7 +194,7 @@ public class FEdge extends Edge { } public int getInvokeNumGap() { - return expInvokeNum - invokeNum; + return this.expInvokeNum - this.invokeNum; } public void setExpInvokeNum(int expInvokeNum) { diff --git a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java index 1ce4eaaf..2fb5b671 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java @@ -435,18 +435,36 @@ public class FlagState extends GraphNode implements Cloneable { // refresh all the expInvokeNum of each edge for(int i = 0; i < this.edges.size(); i++) { next = (FEdge) this.edges.elementAt(i); - next.setExpInvokeNum((int)Math.round(this.invokeNum * (next.getProbability() / 100))); + next.setExpInvokeNum((int)(Math.ceil(this.invokeNum * next.getProbability() / 100))); } // find the one with the biggest gap between its actual invoke time and the expected invoke time // and associated with task td int index = 0; int gap = 0; + double prob = 0; + boolean isbackedge = true; for(int i = 0; i < this.edges.size(); i++) { - int temp = ((FEdge) this.edges.elementAt(index)).getInvokeNumGap(); + next = ((FEdge) this.edges.elementAt(i)); + int temp = next.getInvokeNumGap(); + boolean exchange = false; if((temp > gap) && (next.getTask().equals(td))) { + exchange = true; + } else if(temp == gap) { + if(next.getProbability() > prob) { + exchange = true; + } else if(next.getProbability() == prob) { + if(!isbackedge && next.isbackedge()) { + // backedge has higher priority + exchange = true; + } + } + } + if(exchange) { index = i; gap = temp; + prob = next.getProbability(); + isbackedge = next.isbackedge(); } } next = (FEdge) this.edges.elementAt(index); diff --git a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java index 621805f1..4ed6f7d1 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java @@ -224,6 +224,7 @@ public class TaskAnalysis { FEdge newedge=new FEdge(fs, taskname, td, parameterindex); ((Vector)tdToFEdges.get(td)).add(newedge); fs.addEdge(newedge); + newedge.setisbackedge(true); continue; } else if (fn1.kind()==FKind.FlatFlagActionNode) { FlatFlagActionNode ffan=(FlatFlagActionNode)fn1; diff --git a/Robust/src/IR/Flat/BuildCodeMultiCore.java b/Robust/src/IR/Flat/BuildCodeMultiCore.java index 309f32a0..f247749e 100644 --- a/Robust/src/IR/Flat/BuildCodeMultiCore.java +++ b/Robust/src/IR/Flat/BuildCodeMultiCore.java @@ -5,7 +5,9 @@ import java.io.PrintWriter; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; +import java.util.LinkedList; import java.util.Queue; +import java.util.Set; import java.util.Vector; import Analysis.Locality.LocalityBinding; @@ -13,6 +15,8 @@ import Analysis.Scheduling.Schedule; import Analysis.TaskStateAnalysis.FEdge; import Analysis.TaskStateAnalysis.FlagState; import Analysis.TaskStateAnalysis.SafetyAnalysis; +import Analysis.OwnershipAnalysis.AllocationSite; +import Analysis.OwnershipAnalysis.OwnershipAnalysis; import Analysis.Prefetch.*; import IR.ClassDescriptor; import IR.Descriptor; @@ -43,6 +47,12 @@ public class BuildCodeMultiCore extends BuildCode { String otqueueprefix = "___otqueue"; int startupcorenum; // record the core containing startup task, suppose only one core can hava startup object + private OwnershipAnalysis m_oa; + private Vector> m_aliasSets; + Hashtable> m_aliasFNTbl4Para; + Hashtable> m_aliasFNTbl; + Hashtable> m_aliaslocksTbl4FN; + public BuildCodeMultiCore(State st, Hashtable temptovar, TypeUtil typeutil, SafetyAnalysis sa, Vector scheduling, int coreNum, PrefetchAnalysis pa) { super(st, temptovar, typeutil, sa, pa); this.scheduling = scheduling; @@ -60,6 +70,16 @@ public class BuildCodeMultiCore extends BuildCode { if(this.scheduling.size() < this.coreNum) { this.coreNum = this.scheduling.size(); } + + this.m_oa = null; + this.m_aliasSets = null; + this.m_aliasFNTbl4Para = null; + this.m_aliasFNTbl = null; + this.m_aliaslocksTbl4FN = null; + } + + public void setOwnershipAnalysis(OwnershipAnalysis m_oa) { + this.m_oa = m_oa; } public void buildCode() { @@ -603,8 +623,15 @@ public class BuildCodeMultiCore extends BuildCode { output.println(" struct Queue * totransobjqueue = createQueue();"); output.println(" struct transObjInfo * tmpObjInfo = NULL;"); + this.m_aliasSets = null; + this.m_aliasFNTbl4Para = null; + this.m_aliasFNTbl = null; + this.m_aliaslocksTbl4FN = null; + outputAliasLockCode(fm, lb, output); + /* generate print information for RAW version */ output.println("#ifdef RAW"); + output.println("{"); output.println("int tmpsum = 0;"); output.println("char * taskname = \"" + task.getSymbol() + "\";"); output.println("int tmplen = " + task.getSymbol().length() + ";"); @@ -620,6 +647,7 @@ public class BuildCodeMultiCore extends BuildCode { output.println("raw_test_pass(0xAAAA);"); output.println("raw_test_pass_reg(tmpsum);"); output.println("#endif"); + output.println("}"); output.println("#endif"); for(int i = 0; i < fm.numParameters(); ++i) { @@ -1241,14 +1269,260 @@ public class BuildCodeMultiCore extends BuildCode { output.println("while(0 == isEmpty(totransobjqueue)) {"); output.println(" struct QueueItem * totransitem = getTail(totransobjqueue);"); - output.println(" transferObject((struct transObjInfo *)totransitem->objectptr);"); - output.println(" RUNFREE(((struct transObjInfo *)totransitem->objectptr)->queues);"); + output.println(" transferObject((struct transObjInfo *)(totransitem->objectptr));"); + output.println(" RUNFREE(((struct transObjInfo *)(totransitem->objectptr))->queues);"); output.println(" RUNFREE(totransitem->objectptr);"); output.println(" removeItem(totransobjqueue, totransitem);"); output.println("}"); output.println("freeQueue(totransobjqueue);"); } + protected void outputAliasLockCode(FlatMethod fm, LocalityBinding lb, PrintWriter output) { + if(this.m_oa == null) { + return; + } + TaskDescriptor td = fm.getTask(); + Object[] allocSites = this.m_oa.getFlaggedAllocationSitesReachableFromTask(td).toArray(); + Vector> aliasSets = new Vector>(); + Vector> aliasFNSets = new Vector>(); + Hashtable> aliasFNTbl4Para = new Hashtable>(); + Hashtable> aliasFNTbl = new Hashtable>(); + for( int i = 0; i < fm.numParameters(); ++i ) { + // for the ith parameter check for aliases to all + // higher numbered parameters + aliasSets.add(null); + for( int j = i + 1; j < fm.numParameters(); ++j ) { + if(this.m_oa.createsPotentialAliases(td, i, j)) { + // ith parameter and jth parameter has alias, create lock to protect them + if(aliasSets.elementAt(i) == null) { + aliasSets.setElementAt(new Vector(), i); + } + aliasSets.elementAt(i).add(j); + } + } + + // for the ith parameter, check for aliases against + // the set of allocation sites reachable from this + // task context + aliasFNSets.add(null); + for(int j = 0; j < allocSites.length; j++) { + AllocationSite as = (AllocationSite)allocSites[j]; + if( this.m_oa.createsPotentialAliases(td, i, as) ) { + // ith parameter and allocationsite as has alias + if(aliasFNSets.elementAt(i) == null) { + aliasFNSets.setElementAt(new Vector(), i); + } + aliasFNSets.elementAt(i).add(as.getFlatNew()); + } + } + } + + // for each allocation site check for aliases with + // other allocation sites in the context of execution + // of this task + for( int i = 0; i < allocSites.length; ++i ) { + AllocationSite as1 = (AllocationSite)allocSites[i]; + for(int j = i + 1; j < allocSites.length; j++) { + AllocationSite as2 = (AllocationSite)allocSites[j]; + + if( this.m_oa.createsPotentialAliases(td, as1, as2) ) { + // as1 and as2 has alias + if(!aliasFNTbl.contains(as1.getFlatNew())) { + aliasFNTbl.put(as1.getFlatNew(), new Vector()); + } + if(!aliasFNTbl.get(as1.getFlatNew()).contains(as2.getFlatNew())) { + aliasFNTbl.get(as1.getFlatNew()).add(as2.getFlatNew()); + } + } + } + } + + // if FlatNew N1->N2->N3, we group N1, N2, N3 together + Iterator it = aliasFNTbl.keySet().iterator(); + Vector visited = new Vector(); + while(it.hasNext()) { + FlatNew tmpfn = it.next(); + if(visited.contains(tmpfn)) { + continue; + } + visited.add(tmpfn); + Queue tovisit = new LinkedList(); + Vector tmpv = aliasFNTbl.get(tmpfn); + if(tmpv == null) { + continue; + } + + for(int j = 0; j < tmpv.size(); j++) { + tovisit.add(tmpv.elementAt(j)); + } + + while(!tovisit.isEmpty()) { + FlatNew fn = tovisit.poll(); + visited.add(fn); + Vector tmpset = aliasFNTbl.get(fn); + if(tmpset != null) { + // merge tmpset to the alias set of the ith parameter + for(int j = 0; j < tmpset.size(); j++) { + if(!tmpv.contains(tmpset.elementAt(j))) { + tmpv.add(tmpset.elementAt(j)); + tovisit.add(tmpset.elementAt(j)); + } + } + aliasFNTbl.remove(fn); + } + } + it = aliasFNTbl.keySet().iterator(); + } + + // check alias between parameters and between parameter-flatnew + for(int i = 0; i < aliasSets.size(); i++) { + Queue tovisit = new LinkedList(); + Vector tmpv = aliasSets.elementAt(i); + if(tmpv == null) { + continue; + } + + for(int j = 0; j < tmpv.size(); j++) { + tovisit.add(tmpv.elementAt(j)); + } + + while(!tovisit.isEmpty()) { + int index = tovisit.poll().intValue(); + Vector tmpset = aliasSets.elementAt(index); + if(tmpset != null) { + // merge tmpset to the alias set of the ith parameter + for(int j = 0; j < tmpset.size(); j++) { + if(!tmpv.contains(tmpset.elementAt(j))) { + tmpv.add(tmpset.elementAt(j)); + tovisit.add(tmpset.elementAt(j)); + } + } + aliasSets.setElementAt(null, index); + } + + Vector tmpFNSet = aliasFNSets.elementAt(index); + if(tmpFNSet != null) { + // merge tmpFNSet to the aliasFNSet of the ith parameter + if(aliasFNSets.elementAt(i) == null) { + aliasFNSets.setElementAt(tmpFNSet, i); + } else { + Vector tmpFNv = aliasFNSets.elementAt(i); + for(int j = 0; j < tmpFNSet.size(); j++) { + if(!tmpFNv.contains(tmpFNSet.elementAt(j))) { + tmpFNv.add(tmpFNSet.elementAt(j)); + } + } + } + aliasFNSets.setElementAt(null, index); + } + } + } + + int numlock = 0; + int numparalock = 0; + Vector> tmpaliasSets = new Vector>(); + for(int i = 0; i < aliasSets.size(); i++) { + Vector tmpv = aliasSets.elementAt(i); + if(tmpv != null) { + tmpv.add(0, i); + tmpaliasSets.add(tmpv); + numlock++; + } + + Vector tmpFNv = aliasFNSets.elementAt(i); + if(tmpFNv != null) { + aliasFNTbl4Para.put(i, tmpFNv); + if(tmpv == null) { + numlock++; + } + } + } + numparalock = numlock; + aliasSets.clear(); + aliasSets = null; + this.m_aliasSets = tmpaliasSets; + tmpaliasSets.clear(); + tmpaliasSets = null; + aliasFNSets.clear(); + aliasFNSets = null; + this.m_aliasFNTbl4Para = aliasFNTbl4Para; + this.m_aliasFNTbl = aliasFNTbl; + numlock += this.m_aliasFNTbl.size(); + + // create locks + if(numlock > 0) { + output.println("int aliaslocks[" + numlock + "];"); + output.println("int tmpi = 0;"); + output.println("for(tmpi = 0; tmpi < " + numlock + "; tmpi++) {"); + output.println(" aliaslocks[tmpi] = (int)(RUNMALLOC(sizeof(int)));"); + output.println(" *(int *)(aliaslocks[tmpi]) = 0;"); + output.println("}"); + // associate locks with parameters + int lockindex = 0; + for(int i = 0; i < this.m_aliasSets.size(); i++) { + Vector toadd = this.m_aliasSets.elementAt(i); + for(int j = 0; j < toadd.size(); j++) { + int para = toadd.elementAt(j).intValue(); + output.println("addAliasLock(" + super.generateTemp(fm, fm.getParameter(para), lb) + ", aliaslocks[" + i + "]);"); + } + // check if this lock is also associated with any FlatNew nodes + if(this.m_aliasFNTbl4Para.contains(toadd.elementAt(0))) { + if(this.m_aliaslocksTbl4FN == null) { + this.m_aliaslocksTbl4FN = new Hashtable>(); + } + Vector tmpv = this.m_aliasFNTbl4Para.get(toadd.elementAt(0)); + for(int j = 0; j < tmpv.size(); j++) { + FlatNew fn = tmpv.elementAt(j); + if(!this.m_aliaslocksTbl4FN.contains(fn)) { + this.m_aliaslocksTbl4FN.put(fn, new Vector()); + } + this.m_aliaslocksTbl4FN.get(fn).add(i); + } + this.m_aliasFNTbl4Para.remove(toadd.elementAt(0)); + } + lockindex++; + } + Object[] key = this.m_aliasFNTbl4Para.keySet().toArray(); + for(int i = 0; i < key.length; i++) { + int para = ((Integer)key[i]).intValue(); + output.println("addAliasLock(" + super.generateTemp(fm, fm.getParameter(para), lb) + ", aliaslocks[" + lockindex + "]);"); + Vector tmpv = this.m_aliasFNTbl4Para.get(para); + for(int j = 0; j < tmpv.size(); j++) { + FlatNew fn = tmpv.elementAt(j); + if(this.m_aliaslocksTbl4FN == null) { + this.m_aliaslocksTbl4FN = new Hashtable>(); + } + if(!this.m_aliaslocksTbl4FN.contains(fn)) { + this.m_aliaslocksTbl4FN.put(fn, new Vector()); + } + this.m_aliaslocksTbl4FN.get(fn).add(lockindex); + } + lockindex++; + } + // check m_aliasFNTbl for locks associated with FlatNew nodes + Object[] FNkey = this.m_aliasFNTbl.keySet().toArray(); + for(int i = 0; i < FNkey.length; i++) { + FlatNew fn = (FlatNew)FNkey[i]; + Vector tmpv = this.m_aliasFNTbl.get(fn); + if(this.m_aliaslocksTbl4FN == null) { + this.m_aliaslocksTbl4FN = new Hashtable>(); + } + if(!this.m_aliaslocksTbl4FN.contains(fn)) { + this.m_aliaslocksTbl4FN.put(fn, new Vector()); + } + this.m_aliaslocksTbl4FN.get(fn).add(lockindex); + for(int j = 0; j < tmpv.size(); j++) { + FlatNew tfn = tmpv.elementAt(j); + if(!this.m_aliaslocksTbl4FN.contains(tfn)) { + this.m_aliaslocksTbl4FN.put(tfn, new Vector()); + } + this.m_aliaslocksTbl4FN.get(tfn).add(lockindex); + } + lockindex++; + } + } + } + protected void generateFlatReturnNode(FlatMethod fm, LocalityBinding lb, FlatReturnNode frn, PrintWriter output) { if (frn.getReturnTemp()!=null) { if (frn.getReturnTemp().getType().isPtr()) @@ -1275,6 +1549,60 @@ public class BuildCodeMultiCore extends BuildCode { } } + protected void generateFlatNew(FlatMethod fm, LocalityBinding lb, FlatNew fn, + PrintWriter output) { + if (state.DSM && locality.getAtomic(lb).get(fn).intValue() > 0 + && !fn.isGlobal()) { + // Stash pointer in case of GC + String revertptr = super.generateTemp(fm, reverttable.get(lb), lb); + output.println(revertptr + "=trans->revertlist;"); + } + if (fn.getType().isArray()) { + int arrayid = state.getArrayNumber(fn.getType()) + + state.numClasses(); + if (fn.isGlobal()) { + output.println(super.generateTemp(fm, fn.getDst(), lb) + + "=allocate_newarrayglobal(trans, " + arrayid + ", " + + super.generateTemp(fm, fn.getSize(), lb) + ");"); + } else if (GENERATEPRECISEGC) { + output.println(super.generateTemp(fm, fn.getDst(), lb) + + "=allocate_newarray(&" + localsprefix + ", " + + arrayid + ", " + super.generateTemp(fm, fn.getSize(), lb) + + ");"); + } else { + output.println(super.generateTemp(fm, fn.getDst(), lb) + + "=allocate_newarray(" + arrayid + ", " + + super.generateTemp(fm, fn.getSize(), lb) + ");"); + } + } else { + if (fn.isGlobal()) { + output.println(super.generateTemp(fm, fn.getDst(), lb) + + "=allocate_newglobal(trans, " + + fn.getType().getClassDesc().getId() + ");"); + } else if (GENERATEPRECISEGC) { + output.println(super.generateTemp(fm, fn.getDst(), lb) + + "=allocate_new(&" + localsprefix + ", " + + fn.getType().getClassDesc().getId() + ");"); + } else { + output.println(super.generateTemp(fm, fn.getDst(), lb) + + "=allocate_new(" + + fn.getType().getClassDesc().getId() + ");"); + } + } + if (state.DSM && locality.getAtomic(lb).get(fn).intValue() > 0 + && !fn.isGlobal()) { + String revertptr = super.generateTemp(fm, reverttable.get(lb), lb); + output.println("trans->revertlist=" + revertptr + ";"); + } + // create alias lock if necessary + if((this.m_aliaslocksTbl4FN != null) && (this.m_aliaslocksTbl4FN.contains(fn))) { + Vector tmpv = this.m_aliaslocksTbl4FN.get(fn); + for(int i = 0; i < tmpv.size(); i++) { + output.println("addAliasLock(" + super.generateTemp(fm, fn.getDst(), lb) + ", aliaslocks[" + tmpv.elementAt(i).intValue() + "]);"); + } + } + } + class TranObjInfo { public String name; public int targetcore; diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index a87f66ae..e9b82b96 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -1,13 +1,13 @@ package Main; import java.io.FileOutputStream; -import java.io.InputStream; import java.io.PrintStream; import java.io.Reader; import java.io.BufferedReader; import java.io.FileReader; import java.io.FileInputStream; import java.util.Iterator; +import java.util.Set; import java.util.Vector; import IR.Tree.ParseNode; @@ -22,8 +22,6 @@ import IR.TaskDescriptor; import IR.TypeUtil; import Analysis.Scheduling.Schedule; import Analysis.Scheduling.ScheduleAnalysis; -import Analysis.Scheduling.ScheduleEdge; -import Analysis.Scheduling.ScheduleNode; import Analysis.Scheduling.ScheduleSimulator; import Analysis.TaskStateAnalysis.TaskAnalysis; import Analysis.TaskStateAnalysis.TaskTagAnalysis; @@ -41,6 +39,9 @@ import Analysis.Prefetch.PrefetchAnalysis; import Analysis.FlatIRGraph.FlatIRGraph; import Analysis.OwnershipAnalysis.OwnershipAnalysis; import Interface.*; +import Util.GraphNode; +import Util.GraphNode.DFS; +import Util.GraphNode.SCC; public class Main { @@ -112,7 +113,7 @@ public class Main { else if (option.equals("-scheduling")) state.SCHEDULING=true; else if (option.equals("-useprofile")) - state.USEPROFILE=true; + state.USEPROFILE=true; else if (option.equals("-thread")) state.THREAD=true; else if (option.equals("-dsm")) @@ -252,6 +253,272 @@ public class Main { } if (state.SCHEDULING) { + // Indentify backedges + for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) { + ClassDescriptor cd=(ClassDescriptor) it_classes.next(); + if(cd.hasFlags()) { + Set fss = ta.getFlagStates(cd); + SCC scc=GraphNode.DFS.computeSCC(fss); + if (scc.hasCycles()) { + for(int i=0; i taskinfo = new java.util.Hashtable(); + + int inindex = profiledata.indexOf('\n'); + while((inindex != -1) ) { + String inline = profiledata.substring(0, inindex); + profiledata = profiledata.substring(inindex + 1); + //System.printString(inline + "\n"); + int tmpinindex = inline.indexOf(','); + if(tmpinindex == -1) { + break; + } + String inname = inline.substring(0, tmpinindex); + String inint = inline.substring(tmpinindex + 1); + while(inint.startsWith(" ")) { + inint = inint.substring(1); + } + int duration = Integer.parseInt(inint); + taskinfo.put(inname, duration); + inindex = profiledata.indexOf('\n'); + } + + java.util.Random r=new java.util.Random(); + int tint = 0; + for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) { + ClassDescriptor cd=(ClassDescriptor) it_classes.next(); + if(cd.hasFlags()) { + Vector rootnodes=ta.getRootNodes(cd); + if(rootnodes!=null) { + for(Iterator it_rootnodes=rootnodes.iterator(); it_rootnodes.hasNext();) { + FlagState root=(FlagState)it_rootnodes.next(); + Vector allocatingTasks = root.getAllocatingTasks(); + if(allocatingTasks != null) { + for(int k = 0; k < allocatingTasks.size(); k++) { + TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k); + Vector fev = (Vector)ta.getFEdgesFromTD(td); + int numEdges = fev.size(); + int total = 100; + for(int j = 0; j < numEdges; j++) { + FEdge pfe = fev.elementAt(j); + if(numEdges - j == 1) { + pfe.setProbability(total); + } else { + if((total != 0) && (total != 1)) { + do { + tint = r.nextInt()%total; + } while(tint <= 0); + } + pfe.setProbability(tint); + total -= tint; + } + //do { + // tint = r.nextInt()%10; + // } while(tint <= 0); + //int newRate = tint; + //int newRate = (j+1)%2+1; + int newRate = 1; + String cdname = cd.getSymbol(); + if((cdname.equals("SeriesRunner")) || + (cdname.equals("MDRunner")) || + (cdname.equals("Stage")) || + (cdname.equals("AppDemoRunner")) || + (cdname.equals("FilterBankAtom"))) { + newRate = 16; + } else if(cdname.equals("SentenceParser")) { + newRate = 4; + } + //do { + // tint = r.nextInt()%100; + // } while(tint <= 0); + // int probability = tint; + int probability = 100; + pfe.addNewObjInfo(cd, newRate, probability); + } + } + } + } + } + Iterator it_flags = ta.getFlagStates(cd).iterator(); + while(it_flags.hasNext()) { + FlagState fs = (FlagState)it_flags.next(); + Iterator it_edges = fs.edges(); + int total = 100; + while(it_edges.hasNext()) { + //do { + // tint = r.nextInt()%10; + // } while(tint <= 0); + FEdge edge = (FEdge)it_edges.next(); + tint = taskinfo.get(edge.getTask().getSymbol()).intValue(); + edge.setExeTime(tint); + if((fs.getClassDescriptor().getSymbol().equals("MD")) && (edge.getTask().getSymbol().equals("t6"))) { + if(edge.isbackedge()) { + if(edge.getTarget().equals(edge.getSource())) { + edge.setProbability(93.75); + } else { + edge.setProbability(3.125); + } + } else { + edge.setProbability(3.125); + } + continue; + } + if(!it_edges.hasNext()) { + edge.setProbability(total); + } else { + if((total != 0) && (total != 1)) { + do { + tint = r.nextInt()%total; + } while(tint <= 0); + } + edge.setProbability(tint); + total -= tint; + } + } + } + } + } + } else { + // for test + // Randomly set the newRate and probability of FEdges + java.util.Random r=new java.util.Random(); + int tint = 0; + for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) { + ClassDescriptor cd=(ClassDescriptor) it_classes.next(); + if(cd.hasFlags()) { + Vector rootnodes=ta.getRootNodes(cd); + if(rootnodes!=null) { + for(Iterator it_rootnodes=rootnodes.iterator(); it_rootnodes.hasNext();) { + FlagState root=(FlagState)it_rootnodes.next(); + Vector allocatingTasks = root.getAllocatingTasks(); + if(allocatingTasks != null) { + for(int k = 0; k < allocatingTasks.size(); k++) { + TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k); + Vector fev = (Vector)ta.getFEdgesFromTD(td); + int numEdges = fev.size(); + int total = 100; + for(int j = 0; j < numEdges; j++) { + FEdge pfe = fev.elementAt(j); + if(numEdges - j == 1) { + pfe.setProbability(total); + } else { + if((total != 0) && (total != 1)) { + do { + tint = r.nextInt()%total; + } while(tint <= 0); + } + pfe.setProbability(tint); + total -= tint; + } + //do { + // tint = r.nextInt()%10; + // } while(tint <= 0); + //int newRate = tint; + //int newRate = (j+1)%2+1; + int newRate = 1; + String cdname = cd.getSymbol(); + if((cdname.equals("SeriesRunner")) || + (cdname.equals("MDRunner")) || + (cdname.equals("Stage")) || + (cdname.equals("AppDemoRunner")) || + (cdname.equals("FilterBankAtom"))) { + newRate = 16; + } else if(cdname.equals("SentenceParser")) { + newRate = 4; + } + //do { + // tint = r.nextInt()%100; + // } while(tint <= 0); + // int probability = tint; + int probability = 100; + pfe.addNewObjInfo(cd, newRate, probability); + } + } + } + } + } + + Iterator it_flags = ta.getFlagStates(cd).iterator(); + while(it_flags.hasNext()) { + FlagState fs = (FlagState)it_flags.next(); + Iterator it_edges = fs.edges(); + int total = 100; + while(it_edges.hasNext()) { + //do { + // tint = r.nextInt()%10; + // } while(tint <= 0); + tint = 3; + FEdge edge = (FEdge)it_edges.next(); + edge.setExeTime(tint); + if((fs.getClassDescriptor().getSymbol().equals("MD")) && (edge.getTask().getSymbol().equals("t6"))) { + if(edge.isbackedge()) { + if(edge.getTarget().equals(edge.getSource())) { + edge.setProbability(93.75); + } else { + edge.setProbability(3.125); + } + } else { + edge.setProbability(3.125); + } + continue; + } + if(!it_edges.hasNext()) { + edge.setProbability(total); + } else { + if((total != 0) && (total != 1)) { + do { + tint = r.nextInt()%total; + } while(tint <= 0); + } + edge.setProbability(tint); + total -= tint; + } + } + } + } + } + } + + // Use ownership analysis to get alias information + CallGraph callGraph = new CallGraph(state); + OwnershipAnalysis oa = new OwnershipAnalysis(state, + tu, + callGraph, + state.OWNERSHIPALLOCDEPTH, + state.OWNERSHIPWRITEDOTS, + state.OWNERSHIPWRITEALL, + state.OWNERSHIPALIASFILE); + // Save the current standard input, output, and error streams // for later restoration. PrintStream origOut = System.out; @@ -285,209 +552,6 @@ public class Main { //System.out.println ("Test output via 'SimulatorResult.out'."); //origOut.println ("Test output via 'origOut' reference."); - if(state.USEPROFILE) { - // read in profile data and set - FileInputStream inStream = new FileInputStream("/scratch/profile.rst"); - byte[] b = new byte[1024 * 100]; - int length = inStream.read(b); - if(length < 0) { - System.out.print("No content in input file: /scratch/profile.rst\n"); - System.exit(-1); - } - String profiledata = new String(b, 0, length); - java.util.Hashtable taskinfo = new java.util.Hashtable(); - - int inindex = profiledata.indexOf('\n'); - while((inindex != -1) ) { - String inline = profiledata.substring(0, inindex); - profiledata = profiledata.substring(inindex + 1); - //System.printString(inline + "\n"); - int tmpinindex = inline.indexOf(','); - if(tmpinindex == -1) { - break; - } - String inname = inline.substring(0, tmpinindex); - String inint = inline.substring(tmpinindex + 1); - while(inint.startsWith(" ")) { - inint = inint.substring(1); - } - int duration = Integer.parseInt(inint); - taskinfo.put(inname, duration); - inindex = profiledata.indexOf('\n'); - } - - java.util.Random r=new java.util.Random(); - int tint = 0; - for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) { - ClassDescriptor cd=(ClassDescriptor) it_classes.next(); - if(cd.hasFlags()) { - Vector rootnodes=ta.getRootNodes(cd); - if(rootnodes!=null) { - for(Iterator it_rootnodes=rootnodes.iterator(); it_rootnodes.hasNext();) { - FlagState root=(FlagState)it_rootnodes.next(); - Vector allocatingTasks = root.getAllocatingTasks(); - if(allocatingTasks != null) { - for(int k = 0; k < allocatingTasks.size(); k++) { - TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k); - Vector fev = (Vector)ta.getFEdgesFromTD(td); - int numEdges = fev.size(); - int total = 100; - for(int j = 0; j < numEdges; j++) { - FEdge pfe = fev.elementAt(j); - if(numEdges - j == 1) { - pfe.setProbability(total); - } else { - if((total != 0) && (total != 1)) { - do { - tint = r.nextInt()%total; - } while(tint <= 0); - } - pfe.setProbability(tint); - total -= tint; - } - //do { - // tint = r.nextInt()%10; - // } while(tint <= 0); - //int newRate = tint; - //int newRate = (j+1)%2+1; - int newRate = 1; - String cdname = cd.getSymbol(); - if((cdname.equals("SeriesRunner")) || - (cdname.equals("MDRunner")) || - (cdname.equals("Stage")) || - (cdname.equals("AppDemoRunner")) || - (cdname.equals("FilterBankAtom"))) { - newRate = 16; - } else if(cdname.equals("SentenceParser")) { - newRate = 4; - } - //do { - // tint = r.nextInt()%100; - // } while(tint <= 0); - // int probability = tint; - int probability = 100; - pfe.addNewObjInfo(cd, newRate, probability); - } - } - } - } - } - Iterator it_flags = ta.getFlagStates(cd).iterator(); - while(it_flags.hasNext()) { - FlagState fs = (FlagState)it_flags.next(); - Iterator it_edges = fs.edges(); - int total = 100; - while(it_edges.hasNext()) { - //do { - // tint = r.nextInt()%10; - // } while(tint <= 0); - FEdge edge = (FEdge)it_edges.next(); - tint = taskinfo.get(edge.getTask().getSymbol()).intValue(); - edge.setExeTime(tint); - if(!it_edges.hasNext()) { - edge.setProbability(total); - } else { - if((total != 0) && (total != 1)) { - do { - tint = r.nextInt()%total; - } while(tint <= 0); - } - edge.setProbability(tint); - total -= tint; - } - } - } - } - } - } else { - // for test - // Randomly set the newRate and probability of FEdges - java.util.Random r=new java.util.Random(); - int tint = 0; - for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) { - ClassDescriptor cd=(ClassDescriptor) it_classes.next(); - if(cd.hasFlags()) { - Vector rootnodes=ta.getRootNodes(cd); - if(rootnodes!=null) { - for(Iterator it_rootnodes=rootnodes.iterator(); it_rootnodes.hasNext();) { - FlagState root=(FlagState)it_rootnodes.next(); - Vector allocatingTasks = root.getAllocatingTasks(); - if(allocatingTasks != null) { - for(int k = 0; k < allocatingTasks.size(); k++) { - TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k); - Vector fev = (Vector)ta.getFEdgesFromTD(td); - int numEdges = fev.size(); - int total = 100; - for(int j = 0; j < numEdges; j++) { - FEdge pfe = fev.elementAt(j); - if(numEdges - j == 1) { - pfe.setProbability(total); - } else { - if((total != 0) && (total != 1)) { - do { - tint = r.nextInt()%total; - } while(tint <= 0); - } - pfe.setProbability(tint); - total -= tint; - } - //do { - // tint = r.nextInt()%10; - // } while(tint <= 0); - //int newRate = tint; - //int newRate = (j+1)%2+1; - int newRate = 1; - String cdname = cd.getSymbol(); - if((cdname.equals("SeriesRunner")) || - (cdname.equals("MDRunner")) || - (cdname.equals("Stage")) || - (cdname.equals("AppDemoRunner")) || - (cdname.equals("FilterBankAtom"))) { - newRate = 16; - } else if(cdname.equals("SentenceParser")) { - newRate = 4; - } - //do { - // tint = r.nextInt()%100; - // } while(tint <= 0); - // int probability = tint; - int probability = 100; - pfe.addNewObjInfo(cd, newRate, probability); - } - } - } - } - } - - Iterator it_flags = ta.getFlagStates(cd).iterator(); - while(it_flags.hasNext()) { - FlagState fs = (FlagState)it_flags.next(); - Iterator it_edges = fs.edges(); - int total = 100; - while(it_edges.hasNext()) { - //do { - // tint = r.nextInt()%10; - // } while(tint <= 0); - tint = 3; - FEdge edge = (FEdge)it_edges.next(); - edge.setExeTime(tint); - if(!it_edges.hasNext()) { - edge.setProbability(total); - } else { - if((total != 0) && (total != 1)) { - do { - tint = r.nextInt()%total; - } while(tint <= 0); - } - edge.setProbability(tint); - total -= tint; - } - } - } - } - } - } - // generate multiple schedulings ScheduleAnalysis scheduleAnalysis = new ScheduleAnalysis(state, ta); scheduleAnalysis.preSchedule(); @@ -567,6 +631,7 @@ public class Main { //Vector scheduling = (Vector)it_scheduling.next(); Vector scheduling = scheduleAnalysis.getSchedulings().elementAt(selectedScheduling.lastElement()); BuildCodeMultiCore bcm=new BuildCodeMultiCore(state, bf.getMap(), tu, sa, scheduling, scheduleAnalysis.getCoreNum(), pa); + bcm.setOwnershipAnalysis(oa); bcm.buildCode(); } } diff --git a/Robust/src/Runtime/multicoreruntime.c b/Robust/src/Runtime/multicoreruntime.c index 47a42648..beb82573 100644 --- a/Robust/src/Runtime/multicoreruntime.c +++ b/Robust/src/Runtime/multicoreruntime.c @@ -143,6 +143,8 @@ void * allocate_new(void * ptr, int type) { v->type=type; v->isolate = 1; v->version = 0; + v->numlocks = 0; + v->locks = NULL; #ifdef THREADS v->tid=0; v->lockentry=0; @@ -158,6 +160,8 @@ struct ArrayObject * allocate_newarray(void * ptr, int type, int length) { v->type=type; v->isolate = 1; v->version = 0; + v->numlocks = 0; + v->locks = NULL; if (length<0) { #ifndef RAW printf("ERROR: negative array\n"); @@ -179,6 +183,8 @@ void * allocate_new(int type) { v->type=type; v->isolate = 1; v->version = 0; + v->numlocks = 0; + v->locks = NULL; return v; } @@ -189,6 +195,8 @@ struct ArrayObject * allocate_newarray(int type, int length) { v->type=type; v->isolate = 1; v->version = 0; + v->numlocks = 0; + v->locks = NULL; v->___length___=length; return v; } diff --git a/Robust/src/Runtime/multicoretask.c b/Robust/src/Runtime/multicoretask.c index 4f629a93..94626696 100644 --- a/Robust/src/Runtime/multicoretask.c +++ b/Robust/src/Runtime/multicoretask.c @@ -56,7 +56,7 @@ struct RuntimeHash * reverse; int corestatus[NUMCORES]; // records status of each core // 1: running tasks -// 0: stall + // 0: stall int numsendobjs[NUMCORES]; // records how many objects a core has sent out int numreceiveobjs[NUMCORES]; // records how many objects a core has received #ifdef RAW @@ -117,7 +117,7 @@ void releasewritelock(void* ptr); // profiling mode of RAW version #ifdef RAWPROFILE -#define TASKINFOLENGTH 150 +#define TASKINFOLENGTH 300 //#define INTERRUPTINFOLENGTH 500 bool stall; @@ -131,25 +131,24 @@ typedef struct task_info { } TaskInfo; /*typedef struct interrupt_info { - int startTime; - int endTime; -} InterruptInfo;*/ + int startTime; + int endTime; + } InterruptInfo;*/ TaskInfo * taskInfoArray[TASKINFOLENGTH]; int taskInfoIndex; bool taskInfoOverflow; /*InterruptInfo * interruptInfoArray[INTERRUPTINFOLENGTH]; -int interruptInfoIndex; -bool interruptInfoOverflow;*/ + int interruptInfoIndex; + bool interruptInfoOverflow;*/ int profilestatus[NUMCORES]; // records status of each core // 1: running tasks -// 0: stall + // 0: stall bool transProfileRequestMsg(int targetcore); void outputProfileData(); #endif #ifdef RAW -//#ifdef RAWPROFILE #ifdef RAWUSEIO int main(void) { #else @@ -195,7 +194,6 @@ int main(int argc, char **argv) { for(i = 0; i < 30; ++i) { msgdata[i] = -1; } - //msgdata = NULL; msgtype = -1; msgdataindex = 0; msglength = 30; @@ -238,8 +236,8 @@ int main(int argc, char **argv) { totalexetime = -1; taskInfoIndex = 0; /*interruptInfoIndex = 0; - taskInfoOverflow = false; - interruptInfoOverflow = false;*/ + taskInfoOverflow = false; + interruptInfoOverflow = false;*/ #endif #ifdef INTERRUPT @@ -322,7 +320,6 @@ int main(int argc, char **argv) { } } - //pthread_exit(NULL); while(true) { } } @@ -411,11 +408,6 @@ void run(void* arg) { #endif while(true) { -/*#ifndef INTERRUPT - while(receiveObject() != -1) { - } - #endif*/ - // check if there are new active tasks can be executed executetasks(); @@ -449,6 +441,8 @@ void run(void* arg) { #endif while(!isEmpty(&objqueue)) { void * obj = NULL; + int * locks = NULL; + int numlocks = 0; #ifdef INTERRUPT raw_user_interrupts_off(); #endif @@ -461,36 +455,48 @@ void run(void* arg) { sendStall = false; tocontinue = true; objitem = getTail(&objqueue); - //obj = objitem->objectptr; objInfo = (struct transObjInfo *)objitem->objectptr; obj = objInfo->objptr; #ifdef RAWDEBUG raw_test_pass_reg((int)obj); #endif // grab lock and flush the obj - getreadlock_I(obj); - while(!lockflag) { - receiveObject(); + grount = 0; + if(((struct ___Object___ *)obj)->numlocks == 0) { + locks = obj; + numlocks = 1; + } else { + locks = ((struct ___Object___ *)obj)->locks; + numlocks = ((struct ___Object___ *)obj)->numlocks; } - grount = lockresult; + for(; numlocks > 0; numlocks--) { + getreadlock_I(locks); + while(!lockflag) { + receiveObject(); + } + grount = grount || lockresult; #ifdef RAWDEBUG - raw_test_pass_reg(grount); + raw_test_pass_reg(grount); #endif - lockresult = 0; - lockobj = 0; - lockflag = false; + lockresult = 0; + lockobj = 0; + lockflag = false; #ifndef INTERRUPT - reside = false; + reside = false; #endif + if(grount == 0) { + goto grablockfail; + } + + locks = (int*)(*locks); + } + if(grount == 1) { int k = 0; + // flush the object raw_invalidate_cache_range((int)obj, classsize[((struct ___Object___ *)obj)->type]); - // flush the obj - /*for(k = 0; k < classsize[((struct ___Object___ *)obj)->type]; ++k) { - invalidateAddr(obj + k); - }*/ // enqueue the object for(k = 0; k < objInfo->length; ++k) { int taskindex = objInfo->queues[2 * k]; @@ -503,18 +509,35 @@ void run(void* arg) { enqueueObject_I(obj, queues, 1); } removeItem(&objqueue, objitem); - releasereadlock_I(obj); + if(((struct ___Object___ *)obj)->numlocks == 0) { + locks = obj; + numlocks = 1; + } else { + locks = ((struct ___Object___ *)obj)->locks; + numlocks = ((struct ___Object___ *)obj)->numlocks; + } + for(; numlocks > 0; numlocks--) { + releasereadlock_I(locks); + locks = (int *)(*locks); + } RUNFREE(objInfo->queues); RUNFREE(objInfo); - /*enqueueObject_I(obj, NULL, 0); - removeItem(&objqueue, objitem); - releasereadlock_I(obj);*/ } else { +grablockfail: // can not get lock // put it at the end of the queue // and try to execute active tasks already enqueued first removeItem(&objqueue, objitem); addNewItem_I(&objqueue, objInfo); + if(((struct ___Object___ *)obj)->numlocks > 0) { + //release grabbed locks + numlocks = ((struct ___Object___ *)obj)->numlocks - numlocks; + locks = ((struct ___Object___ *)obj)->locks; + for(; numlocks > 0; numlocks--) { + releasereadlock_I(locks); + locks = (int *)(*locks); + } + } #ifdef RAWPROFILE //isInterrupt = true; #endif @@ -596,7 +619,6 @@ void run(void* arg) { #ifdef RAWDEBUG raw_test_pass(0xee11); #endif -//#ifdef RAWPROFILE #ifdef RAWUSEIO totalexetime = raw_get_cycle(); #else @@ -707,7 +729,7 @@ void run(void* arg) { while(true) { switch(receiveObject()) { case 0: { - printf("[run, %d] receive an object\n", numofcore); + //printf("[run, %d] receive an object\n", numofcore); sendStall = false; // received an object // check if there are new active tasks can be executed @@ -805,15 +827,6 @@ void run(void* arg) { break; } - /* case 3: { - printf("[run, %d] receive a terminate msg\n", numofcore); - // receive a terminate Msg - assert(STARTUPCORE != corenum); // only non-startup core can receive such msg - mq_close(mqd[corenum]); - fflush(stdout); - exit(0); - break; - }*/ default: { printf("[run, %d] Error: invalid message type.\n", numofcore); fflush(stdout); @@ -850,12 +863,13 @@ void createstartupobject(int argc, char ** argv) { startupobject->isolate = 1; startupobject->version = 0; + startupobject->numlocks = 0; + startupobject->locks = NULL; /* Set initialized flag for startup object */ flagorandinit(startupobject,1,0xFFFFFFFF); enqueueObject(startupobject, NULL, 0); #ifdef RAW - //flushAll(); raw_flush_entire_cache(); #endif } @@ -1427,6 +1441,37 @@ void calCoords(int core_num, int* coordY, int* coordX) { } #endif +void addAliasLock(void * ptr, int lock) { + struct ___Object___ * obj = (struct ___Object___ *)ptr; + if(obj->numlocks == 0) { + // originally no alias locks associated + obj->locks = (int *)lock; + *(obj->locks) = 0; + obj->numlocks++; + } else { + // already have some alias locks + // insert the new lock into the sorted lock linklist + int prev, next; + prev = next = (int)obj->locks; + while(next != 0) { + if(next < lock) { + // next is less than lock, move to next node + prev = next; + next = *((int *)next); + } else if(next == lock) { + // already have this lock, do nothing + return; + } else { + // insert the lock between prev and next + break; + } + } + *(int *)prev = lock; + *(int *)lock = next; + obj->numlocks++; + } +} + /* Message format for RAW version: * type + Msgbody * type: 0 -- transfer object @@ -1436,7 +1481,7 @@ void calCoords(int core_num, int* coordY, int* coordX) { * 4 -- lock deny * 5 -- lock release * 6 -- transfer profile output msg - * 7 -- transfer profile ouput finish msg + * 7 -- transfer profile output finish msg * * ObjMsg: 0 + size of msg + obj's address + (task index + param index)+ * StallMsg: 1 + corenum + sendobjs + receiveobjs (size is always 4 * sizeof(int)) @@ -1454,21 +1499,15 @@ void transferObject(struct transObjInfo * transObj) { int type=((int *)obj)[0]; int size=classsize[type]; int targetcore = transObj->targetcore; - //assert(type < NUMCLASSES); // can only transfer normal object #ifdef RAW unsigned msgHdr; int self_y, self_x, target_y, target_x; - //int isshared = 0; // for 32 bit machine, the size of fixed part is always 3 words - //int msgsize = sizeof(int) * 2 + sizeof(void *); int msgsize = 3 + transObj->length * 2; int i = 0; struct ___Object___ * newobj = (struct ___Object___ *)obj; - /*if(0 == newobj->isolate) { - isshared = 1; - }*/ calCoords(corenum, &self_y, &self_x); calCoords(targetcore, &target_y, &target_x); @@ -1587,12 +1626,6 @@ void transferObject(struct transObjInfo * transObj) { fflush(stdout); exit(-1); } - /*struct ___Object___ * newobj = (struct ___Object___ *)obj; - if(0 == newobj->isolate) { - newobj = RUNMALLOC(size); - memcpy(newobj, obj, size); - newobj->original=obj; - }*/ struct transObjInfo * tmptransObj = RUNMALLOC(sizeof(struct transObjInfo)); memcpy(tmptransObj, transObj, sizeof(struct transObjInfo)); int * tmpqueue = RUNMALLOC(sizeof(int)*2*tmptransObj->length); @@ -1764,7 +1797,6 @@ bool transProfileRequestMsg(int targetcore) { unsigned msgHdr; int self_y, self_x, target_y, target_x; // for 32 bit machine, the size is always 4 words - //int msgsize = sizeof(int) * 4; int msgsize = 2; calCoords(corenum, &self_y, &self_x); @@ -1906,43 +1938,43 @@ void outputProfileData() { fclose(fp); #else - int i = 0; - int j = 0; - - raw_test_pass(0xdddd); - // output task related info - for(i= 0; i < taskInfoIndex; i++) { - TaskInfo* tmpTInfo = taskInfoArray[i]; - char* tmpName = tmpTInfo->taskName; - int nameLen = strlen(tmpName); - raw_test_pass(0xddda); - for(j = 0; j < nameLen; j++) { - raw_test_pass_reg(tmpName[j]); - } - raw_test_pass(0xdddb); - raw_test_pass_reg(tmpTInfo->startTime); - raw_test_pass_reg(tmpTInfo->endTime); - raw_test_pass(0xdddc); - } + int i = 0; + int j = 0; - if(taskInfoOverflow) { - raw_test_pass(0xefee); - } + raw_test_pass(0xdddd); + // output task related info + for(i= 0; i < taskInfoIndex; i++) { + TaskInfo* tmpTInfo = taskInfoArray[i]; + char* tmpName = tmpTInfo->taskName; + int nameLen = strlen(tmpName); + raw_test_pass(0xddda); + for(j = 0; j < nameLen; j++) { + raw_test_pass_reg(tmpName[j]); + } + raw_test_pass(0xdddb); + raw_test_pass_reg(tmpTInfo->startTime); + raw_test_pass_reg(tmpTInfo->endTime); + raw_test_pass(0xdddc); + } + + if(taskInfoOverflow) { + raw_test_pass(0xefee); + } - // output interrupt related info - /*for(i = 0; i < interruptInfoIndex; i++) { - InterruptInfo* tmpIInfo = interruptInfoArray[i]; - raw_test_pass(0xddde); - raw_test_pass_reg(tmpIInfo->startTime); - raw_test_pass_reg(tmpIInfo->endTime); - raw_test_pass(0xdddf); + // output interrupt related info + /*for(i = 0; i < interruptInfoIndex; i++) { + InterruptInfo* tmpIInfo = interruptInfoArray[i]; + raw_test_pass(0xddde); + raw_test_pass_reg(tmpIInfo->startTime); + raw_test_pass_reg(tmpIInfo->endTime); + raw_test_pass(0xdddf); } if(interruptInfoOverflow) { - raw_test_pass(0xefef); + raw_test_pass(0xefef); }*/ - raw_test_pass(0xeeee); + raw_test_pass(0xeeee); #endif } #endif @@ -1976,11 +2008,11 @@ int receiveObject() { } #ifdef RAWPROFILE /*if(isInterrupt && (!interruptInfoOverflow)) { - // raw_test_pass(0xffff); - interruptInfoArray[interruptInfoIndex] = RUNMALLOC_I(sizeof(struct interrupt_info)); - interruptInfoArray[interruptInfoIndex]->startTime = raw_get_cycle(); - interruptInfoArray[interruptInfoIndex]->endTime = -1; - }*/ + // raw_test_pass(0xffff); + interruptInfoArray[interruptInfoIndex] = RUNMALLOC_I(sizeof(struct interrupt_info)); + interruptInfoArray[interruptInfoIndex]->startTime = raw_get_cycle(); + interruptInfoArray[interruptInfoIndex]->endTime = -1; + }*/ #endif msg: #ifdef RAWDEBUG @@ -2005,38 +2037,6 @@ msg: raw_test_pass_reg(msgdata[msgdataindex]); #endif msgdataindex++; - - /*if(msgdataindex == 0) { - // type - msgtype = gdn_receive(); - if(msgtype > 2) { - msglength = 3; - } else { - msglength = 4; - } - if(msgtype != 0) { - msgdata = (int *)RUNMALLOC_I(msglength * sizeof(int)); - msgdata[msgdataindex] = msgtype; - } - #ifdef RAWDEBUG - raw_test_pass_reg(msgtype); - #endif - } else if((msgdataindex == 1) && (msgtype == 0)) { - // object transfer msg - msglength = gdn_receive(); - msgdata = (int *)RUNMALLOC_I(msglength * sizeof(int)); - msgdata[0] = msgtype; - msgdata[msgdataindex] = msglength; - #ifdef RAWDEBUG - raw_test_pass_reg(msgdata[msgdataindex]); - #endif - } else { - msgdata[msgdataindex] = gdn_receive(); - #ifdef RAWDEBUG - raw_test_pass_reg(msgdata[msgdataindex]); - #endif - } - msgdataindex++;*/ } #ifdef RAWDEBUG raw_test_pass(0xffff); @@ -2087,20 +2087,12 @@ msg: qitem = getNext(prev); } } - //memcpy(transObj->queues, msgdata[3], sizeof(int)*(msglength - 3)); addNewItem_I(&objqueue, (void *)transObj); } ++(self_numreceiveobjs); #ifdef RAWDEBUG raw_test_pass(0xe881); #endif - /* - addNewItem_I(&objqueue, (void *)data2); - ++(self_numreceiveobjs); - #ifdef RAWDEBUG - raw_test_pass(0xe881); - #endif - */ break; } @@ -2273,6 +2265,7 @@ msg: // receive lock release msg if(!RuntimeHashcontainskey(locktbl, data2)) { // no locks for this object, something is wrong + //raw_test_pass_reg(data2); raw_test_done(0xa004); } else { int rwlock_obj = 0; @@ -2300,7 +2293,6 @@ msg: // receive an output request msg if(corenum == STARTUPCORE) { // startup core can not receive profile output finish msg - // return -1 raw_test_done(0xa00a); } { @@ -2350,7 +2342,6 @@ msg: // receive a profile output finish msg if(corenum != STARTUPCORE) { // non startup core can not receive profile output finish msg - // return -1 raw_test_done(0xa00b); } profilestatus[data1] = 0; @@ -2361,13 +2352,10 @@ msg: default: break; } - //RUNFREE(msgdata); - //msgdata = NULL; for(msgdataindex--; msgdataindex > 0; --msgdataindex) { msgdata[msgdataindex] = -1; } msgtype = -1; - //msgdataindex = 0; msglength = 30; #ifdef RAWDEBUG raw_test_pass(0xe888); @@ -2380,7 +2368,7 @@ msg: interruptInfoArray[interruptInfoIndex]->endTime = raw_get_cycle(); interruptInfoIndex++; if(interruptInfoIndex == INTERRUPTINFOLENGTH) { - interruptInfoOverflow = true; + interruptInfoOverflow = true; } }*/ #endif @@ -2395,7 +2383,7 @@ msg: interruptInfoArray[interruptInfoIndex]->endTime = raw_get_cycle(); interruptInfoIndex++; if(interruptInfoIndex == INTERRUPTINFOLENGTH) { - interruptInfoOverflow = true; + interruptInfoOverflow = true; } }*/ #endif @@ -2425,11 +2413,7 @@ msg: printf(" index: %d, sendobjs: %d, reveiveobjs: %d\n", index, numsendobjs[index], numreceiveobjs[index]); free(msgptr); return 2; - } /*else if(((int*)msgptr)[0] == -2) { - // terminate msg - return 3; - } */ - else { + } else { // an object if(numofcore == STARTUPCORE) { ++(numreceiveobjs[numofcore]); @@ -2468,7 +2452,6 @@ bool getreadlock(void * ptr) { int self_y, self_x, target_y, target_x; int targetcore = 0; //((int)ptr >> 5) % TOTALCORE; // for 32 bit machine, the size is always 4 words - //int msgsize = sizeof(int) * 4; int msgsize = 4; int tc = TOTALCORE; #ifdef INTERRUPT @@ -2665,7 +2648,6 @@ void releasereadlock(void * ptr) { int self_y, self_x, target_y, target_x; int targetcore = 0; //((int)ptr >> 5) % TOTALCORE; // for 32 bit machine, the size is always 3 words - //int msgsize = sizeof(int) * 3; int msgsize = 3; int tc = TOTALCORE; #ifdef INTERRUPT @@ -2788,7 +2770,6 @@ bool getreadlock_I(void * ptr) { int self_y, self_x, target_y, target_x; int targetcore = ((int)ptr >> 5) % TOTALCORE; // for 32 bit machine, the size is always 4 words - //int msgsize = sizeof(int) * 4; int msgsize = 4; lockobj = (int)ptr; @@ -2871,7 +2852,6 @@ void releasereadlock_I(void * ptr) { int self_y, self_x, target_y, target_x; int targetcore = ((int)ptr >> 5) % TOTALCORE; // for 32 bit machine, the size is always 3 words - //int msgsize = sizeof(int) * 3; int msgsize = 3; if(targetcore == corenum) { @@ -2923,7 +2903,6 @@ bool getwritelock(void * ptr) { int self_y, self_x, target_y, target_x; int targetcore = 0; //((int)ptr >> 5) % TOTALCORE; // for 32 bit machine, the size is always 4 words - //int msgsize = sizeof(int) * 4; int msgsize= 4; int tc = TOTALCORE; #ifdef INTERRUPT @@ -3150,7 +3129,6 @@ void releasewritelock(void * ptr) { int self_y, self_x, target_y, target_x; int targetcore = 0; //((int)ptr >> 5) % TOTALCORE; // for 32 bit machine, the size is always 3 words - //int msgsize = sizeof(int) * 3; int msgsize = 3; int tc = TOTALCORE; #ifdef INTERRUPT @@ -3575,13 +3553,6 @@ newtask: currtpd=(struct taskparamdescriptor *) getfirstkey(activetasks); genfreekey(activetasks, currtpd); - /* Check if this task has failed, allow a task that contains optional objects to fire */ - /*if (gencontains(failedtasks, currtpd)) { - // Free up task parameter descriptor - RUNFREE(currtpd->parameterArray); - RUNFREE(currtpd); - goto newtask; - }*/ numparams=currtpd->task->numParameters; numtotal=currtpd->task->numTotal; @@ -3591,6 +3562,8 @@ newtask: /* Make sure that the parameters are still in the queues */ for(i=0; iparameterArray[i]; + int * locks; + int numlocks; #ifdef RAW #ifdef RAWDEBUG raw_test_pass(0xe993); @@ -3603,46 +3576,80 @@ newtask: } lock = true; // require locks for this parameter if it is not a startup object - getwritelock(parameter); + if(((struct ___Object___ *)parameter)->numlocks == 0) { + numlocks = 1; + locks = parameter; + } else { + numlocks = ((struct ___Object___ *)parameter)->numlocks; + locks = ((struct ___Object___ *)parameter)->locks; + } + grount = 0; + for(; numlocks > 0; numlocks--) { + getwritelock(locks); #ifdef INTERRUPT - raw_user_interrupts_off(); + raw_user_interrupts_off(); #endif #ifdef RAWPROFILE - //isInterrupt = false; + //isInterrupt = false; #endif - while(!lockflag) { - receiveObject(); - } + while(!lockflag) { + receiveObject(); + } #ifndef INTERRUPT - if(reside) { - while(receiveObject() != -1) { + if(reside) { + while(receiveObject() != -1) { + } } - } #endif - grount = lockresult; + grount = grount || lockresult; - lockresult = 0; - lockobj = 0; - lockflag = false; + lockresult = 0; + lockobj = 0; + lockflag = false; #ifndef INTERRUPT - reside = false; + reside = false; #endif #ifdef RAWPROFILE - //isInterrupt = true; + //isInterrupt = true; #endif #ifdef INTERRUPT - raw_user_interrupts_on(); + raw_user_interrupts_on(); #endif + if(grount == 0) { + goto grablock_fail; + } + locks = (int *)(*locks); + } + if(grount == 0) { +grablock_fail: #ifdef RAWDEBUG raw_test_pass(0xe994); #endif // can not get the lock, try later + // first release all grabbed locks for this parameter + numlocks = ((struct ___Object___ *)parameter)->numlocks - numlocks; + locks = ((struct ___Object___ *)parameter)->locks; + for(; numlocks > 0; numlocks--) { + releasewritelock(locks); + locks = (int *)(*locks); + } + // then releas all grabbed locks for previous parameters for(j = 0; j < i; ++j) { - releasewritelock(taskpointerarray[j+OFFSET]); + if(((struct ___Object___ *)taskpointerarray[j+OFFSET])->numlocks == 0) { + locks = taskpointerarray[j+OFFSET]; + numlocks = 1; + } else { + locks = ((struct ___Object___ *)taskpointerarray[j+OFFSET])->locks; + numlocks = ((struct ___Object___ *)taskpointerarray[j+OFFSET])->numlocks; + } + for(; numlocks > 0; numlocks--) { + releasewritelock(locks); + locks = (int *)(*locks); + } } genputtable(activetasks, currtpd, currtpd); if(hashsize(activetasks) == 1) { @@ -3666,10 +3673,6 @@ newtask: // flush the object { raw_invalidate_cache_range((int)parameter, classsize[((struct ___Object___ *)parameter)->type]); - /*int tmp = 0; - for(tmp = 0; tmp < classsize[((struct ___Object___ *)parameter)->type]; ++tmp) { - invalidateAddr(parameter + tmp); - }*/ } #endif tmpparam = (struct ___Object___ *)parameter; @@ -3683,8 +3686,7 @@ newtask: if(0 == tmpparam->isolate) { isolateflags[i] = 0; // shared object, need to flush with current value - //if(!getreadlock(tmpparam->original)) { - // // fail to get read lock of the original object, try this task later + // TODO: need modification according to added alias locks if(!getwritelock(tmpparam->original)) { // fail to get write lock, release all obtained locks and try this task later int j = 0; @@ -3697,9 +3699,6 @@ newtask: goto newtask; } if(tmpparam->version != tmpparam->original->version) { - // some task on another core has changed this object - // flush this object - //memcpy(tmpparam, tmpparam->original, classsize[tmpparam->type]); // release all obtained locks int j = 0; for(j = 0; j < i; ++j) { @@ -3725,8 +3724,6 @@ newtask: free(enterflags); } } - // try to enqueue it again to check if it feeds other tasks; - //enqueueObject(tmpparam, NULL, 0); // Free up task parameter descriptor RUNFREE(currtpd->parameterArray); RUNFREE(currtpd); @@ -3746,9 +3743,29 @@ newtask: #endif // release grabbed locks for(j = 0; j < i; ++j) { - releasewritelock(taskpointerarray[j+OFFSET]); + if(((struct ___Object___ *)taskpointerarray[j+OFFSET])->numlocks == 0) { + numlocks = 1; + locks = ((struct ___Object___ *)taskpointerarray[j+OFFSET])->locks; + } else { + numlocks = ((struct ___Object___ *)taskpointerarray[j+OFFSET])->numlocks; + locks = ((struct ___Object___ *)taskpointerarray[j+OFFSET])->locks; + } + for(; numlocks > 0; numlocks--) { + releasewritelock(locks); + locks = (int *)(*locks); + } + } + if(((struct ___Object___ *)parameter)->numlocks == 0) { + numlocks = 1; + locks = parameter; + } else { + numlocks = ((struct ___Object___ *)parameter)->numlocks; + locks = ((struct ___Object___ *)parameter)->locks; + } + for(; numlocks > 0; numlocks--) { + releasewritelock(locks); + locks = (int *)(*locks); } - releasewritelock(parameter); RUNFREE(currtpd->parameterArray); RUNFREE(currtpd); goto newtask; @@ -3788,9 +3805,29 @@ newtask: free(enterflags); // release grabbed locks for(j = 0; j < i; ++j) { - releasewritelock(taskpointerarray[j+OFFSET]); + if(((struct ___Object___ *)taskpointerarray[j+OFFSET])->numlocks == 0) { + numlocks = 1; + locks = taskpointerarray[j+OFFSET]; + } else { + numlocks = ((struct ___Object___ *)taskpointerarray[j+OFFSET])->numlocks; + locks = ((struct ___Object___ *)taskpointerarray[j+OFFSET])->locks; + } + for(; numlocks > 0; numlocks--) { + releasewritelock(locks); + locks = (int *)(*locks); + } + } + if(((struct ___Object___ *)parameter)->numlocks == 0) { + numlocks = 1; + locks = parameter; + } else { + numlocks = ((struct ___Object___ *)parameter)->numlocks; + locks = ((struct ___Object___ *)parameter)->locks; + } + for(; numlocks > 0; numlocks--) { + releasewritelock(locks); + locks = (int *)(*locks); } - releasewritelock(parameter); RUNFREE(currtpd->parameterArray); RUNFREE(currtpd); #ifdef RAWPROFILE @@ -3886,7 +3923,7 @@ parameterpresent: }*/ /* Actually call task */ #ifdef PRECISE_GC - ((int *)taskpointerarray)[0]=currtpd->numParameters; + ((int *)taskpointerarray)[0]=currtpd->numParameters; taskpointerarray[1]=NULL; #endif execute: @@ -3950,17 +3987,39 @@ execute: for(i = 0; i < numparams; ++i) { int j = 0; struct ___Object___ * tmpparam = (struct ___Object___ *)taskpointerarray[i+OFFSET]; + int numlocks; + int * locks; #ifdef RAWDEBUG raw_test_pass(0xe999); raw_test_pass(0xdd100000 + tmpparam->flag); #endif - releasewritelock(tmpparam); + if(tmpparam->numlocks == 0) { + numlocks = 1; + locks = tmpparam; + } else { + numlocks = tmpparam->numlocks; + locks = tmpparam->locks; + } + for(; numlocks > 0; numlocks--) { + releasewritelock(locks); + locks = (int *)(*locks); + } } #elif defined THREADSIMULATE for(i = 0; i < numparams; ++i) { if(0 == isolateflags[i]) { struct ___Object___ * tmpparam = (struct ___Object___ *)taskpointerarray[i+OFFSET]; - releasewritelock(tmpparam); + if(tmpparam->numlocks == 0) { + numlocks = 1; + locks = tmpparam; + } else { + numlocks = tmpparam->numlocks; + locks = tmpparam->locks; + } + for(; numlocks > 0; numlocks--) { + releasewritelock(locks); + locks = (int *)(*locks); + } } } #endif diff --git a/Robust/src/Runtime/runtime.h b/Robust/src/Runtime/runtime.h index f80a4ab7..0a5374bd 100644 --- a/Robust/src/Runtime/runtime.h +++ b/Robust/src/Runtime/runtime.h @@ -108,10 +108,6 @@ struct transObjInfo { }; #endif -#ifdef RAW -//struct RuntimeHash * ptbl = NULL; -#endif - #ifdef MULTICORE void flagorand(void * ptr, int ormask, int andmask, struct parameterwrapper ** queues, int length); void flagorandinit(void * ptr, int ormask, int andmask); @@ -119,6 +115,7 @@ void enqueueObject(void * ptr, struct parameterwrapper ** queues, int length); #ifdef RAW void enqueueObject_I(void * ptr, struct parameterwrapper ** queues, int length); #endif +void addAliasLock(void * ptr, int lock); #else void flagorand(void * ptr, int ormask, int andmask); void flagorandinit(void * ptr, int ormask, int andmask); diff --git a/Robust/src/Runtime/task.c b/Robust/src/Runtime/task.c index e5db4ef6..5f693ef3 100644 --- a/Robust/src/Runtime/task.c +++ b/Robust/src/Runtime/task.c @@ -1200,7 +1200,7 @@ parameterpresent: } /* Actually call task */ #ifdef PRECISE_GC - ((int *)taskpointerarray)[0]=currtpd->numParameters; + ((int *)taskpointerarray)[0]=currtpd->numParameters; taskpointerarray[1]=NULL; #endif #ifdef OPTIONAL diff --git a/Robust/src/Util/GraphNode.java b/Robust/src/Util/GraphNode.java index ebc31d0e..d765b2f2 100755 --- a/Robust/src/Util/GraphNode.java +++ b/Robust/src/Util/GraphNode.java @@ -380,7 +380,7 @@ public class GraphNode { } /** Returns whether the strongly connected component i contains a cycle */ - boolean hasCycle(int i) { + public boolean hasCycle(int i) { Integer scc=new Integer(i); Set s=(Set)map.get(scc); if (s.size()>1) -- 2.34.1