From 2cae159e862665cfd60da12d5bf84259c738f17b Mon Sep 17 00:00:00 2001 From: jzhou Date: Mon, 23 Feb 2009 23:22:47 +0000 Subject: [PATCH] change to new scheduling search algorithm: search part of the whole space -> simulate to find the best one -> analyze its critical path -> try to optimize the critical path and thus get another set of possible scheduling to simulate and optimize --- Robust/src/Analysis/Scheduling/ClassNode.java | 31 +- .../Analysis/Scheduling/CombinationUtil.java | 6 +- .../Analysis/Scheduling/CoreSimulator.java | 16 +- .../Analysis/Scheduling/MCImplSynthesis.java | 817 +++++++++++++++ .../Analysis/Scheduling/ObjectSimulator.java | 11 +- Robust/src/Analysis/Scheduling/Schedule.java | 23 +- .../Analysis/Scheduling/ScheduleAnalysis.java | 933 +++++++----------- .../src/Analysis/Scheduling/ScheduleEdge.java | 6 +- .../src/Analysis/Scheduling/ScheduleNode.java | 130 ++- .../Scheduling/ScheduleSimulator.java | 882 ++++++++++++----- .../Analysis/Scheduling/SchedulingUtil.java | 279 +++++- .../Analysis/Scheduling/SimExecutionEdge.java | 134 +++ .../Analysis/Scheduling/SimExecutionNode.java | 47 + .../Analysis/Scheduling/TaskSimulator.java | 14 +- .../Scheduling/TransTaskSimulator.java | 9 +- 15 files changed, 2467 insertions(+), 871 deletions(-) create mode 100644 Robust/src/Analysis/Scheduling/MCImplSynthesis.java create mode 100644 Robust/src/Analysis/Scheduling/SimExecutionEdge.java create mode 100644 Robust/src/Analysis/Scheduling/SimExecutionNode.java diff --git a/Robust/src/Analysis/Scheduling/ClassNode.java b/Robust/src/Analysis/Scheduling/ClassNode.java index 7f48ff10..ec448030 100644 --- a/Robust/src/Analysis/Scheduling/ClassNode.java +++ b/Robust/src/Analysis/Scheduling/ClassNode.java @@ -11,7 +11,11 @@ import Util.GraphNode; public class ClassNode extends GraphNode implements Cloneable { private int uid; + private int cid; private static int nodeID=0; + private static int colorID = 1; + private static Hashtable cd2cid = + new Hashtable(); private final ClassDescriptor cd; private ScheduleNode sn; @@ -25,11 +29,25 @@ public class ClassNode extends GraphNode implements Cloneable { * @param cd ClassDescriptor * @param fStates */ - public ClassNode(ClassDescriptor cd, Vector fStates) { + public ClassNode(ClassDescriptor cd, + Vector fStates) { this.cd=cd; this.flagStates = fStates; this.sn = null; this.uid=ClassNode.nodeID++; + // TODO: potential bug here + // DO NOT consider splitting a class node here. + // need to fix: 1. when a class node is splitted, the pieces should have + // different cid + // 2. when two pieces merged, it should have right cid as have + // never been splitted + // 3. NOTE: a piece could be splitted further + if(this.cd2cid.containsKey(cd)) { + this.cid = this.cd2cid.get(cd); + } else { + this.cid = ClassNode.colorID++; + this.cd2cid.put(this.cd, this.cid); + } this.transTime = 0; } @@ -45,6 +63,10 @@ public class ClassNode extends GraphNode implements Cloneable { return uid; } + public int getCid() { + return cid; + } + public ScheduleNode getScheduleNode() { return this.sn; } @@ -99,6 +121,8 @@ public class ClassNode extends GraphNode implements Cloneable { if (o instanceof ClassNode) { ClassNode fs=(ClassNode)o; if ((fs.getClassDescriptor()!= cd) || + (fs.getuid()!= uid) || + (fs.getCid()!= cid) || (fs.isSorted() != sorted) || (fs.clone != this.clone) || (fs.transTime != this.transTime)) { @@ -110,8 +134,8 @@ public class ClassNode extends GraphNode implements Cloneable { } public int hashCode() { - return cd.hashCode()^Boolean.toString(sorted).hashCode()^Boolean.toString(clone).hashCode()^ - transTime^flagStates.hashCode(); + return cd.hashCode()^uid^cid^Boolean.toString(sorted).hashCode()^ + Boolean.toString(clone).hashCode()^transTime^flagStates.hashCode(); } public String getLabel() { @@ -139,6 +163,7 @@ public class ClassNode extends GraphNode implements Cloneable { e.printStackTrace(); } o.uid = ClassNode.nodeID++; + o.cid = this.cid; o.clone = true; return o; } diff --git a/Robust/src/Analysis/Scheduling/CombinationUtil.java b/Robust/src/Analysis/Scheduling/CombinationUtil.java index 30bf2078..cc68fa4a 100644 --- a/Robust/src/Analysis/Scheduling/CombinationUtil.java +++ b/Robust/src/Analysis/Scheduling/CombinationUtil.java @@ -15,11 +15,13 @@ public class CombinationUtil { return cu; } - public static RootsGenerator allocateRootsGenerator(Vector> snodevecs, int rootNum) { + public static RootsGenerator allocateRootsGenerator(Vector> snodevecs, + int rootNum) { return CombinationUtil.allocateCombinationUtil().new RootsGenerator(snodevecs, rootNum); } - public static CombineGenerator allocateCombineGenerator(Vector> rootnodes, Vector> node2combine) { + public static CombineGenerator allocateCombineGenerator(Vector> rootnodes, + Vector> node2combine) { return CombinationUtil.allocateCombinationUtil().new CombineGenerator(rootnodes, node2combine); } diff --git a/Robust/src/Analysis/Scheduling/CoreSimulator.java b/Robust/src/Analysis/Scheduling/CoreSimulator.java index 38b3a0d1..a1804742 100644 --- a/Robust/src/Analysis/Scheduling/CoreSimulator.java +++ b/Robust/src/Analysis/Scheduling/CoreSimulator.java @@ -17,7 +17,8 @@ public class CoreSimulator { int coreNum; int activeTime; - public CoreSimulator(RuntimeSchedule schedule, int coreNum) { + public CoreSimulator(RuntimeSchedule schedule, + int coreNum) { super(); reset(); this.rSchedule = schedule; @@ -63,7 +64,8 @@ public class CoreSimulator { return targetCSimulator.get(fstate); } - public void setTargetCSimulator(Hashtable> targetCSimulator) { + public void setTargetCSimulator(Hashtable> targetCSimulator) { this.targetCSimulator = targetCSimulator; } @@ -74,7 +76,8 @@ public class CoreSimulator { return allyCSimulator.get(fstate); } - public void setAllyCSimulator(Hashtable> allyCSimulator) { + public void setAllyCSimulator(Hashtable> allyCSimulator) { this.allyCSimulator = allyCSimulator; } @@ -122,7 +125,9 @@ public class CoreSimulator { } } - public void addObject(ObjectSimulator newObj, FlagState fs, int version) { + public void addObject(ObjectSimulator newObj, + FlagState fs, + int version) { if(this.tasks == null) { return; } @@ -141,7 +146,8 @@ public class CoreSimulator { ObjectSimulator obj = paraQueues.elementAt(i).poll(); obj.setHold(false); boolean remove = false; - if((this.targetFState != null) && (this.targetFState.containsKey(obj.getCurrentFS()))) { + if((this.targetFState != null) + && (this.targetFState.containsKey(obj.getCurrentFS()))) { if(transObjs == null) { transObjs = new Vector(); } diff --git a/Robust/src/Analysis/Scheduling/MCImplSynthesis.java b/Robust/src/Analysis/Scheduling/MCImplSynthesis.java new file mode 100644 index 00000000..572349b7 --- /dev/null +++ b/Robust/src/Analysis/Scheduling/MCImplSynthesis.java @@ -0,0 +1,817 @@ +package Analysis.Scheduling; + +import java.io.FileOutputStream; +import java.io.PrintStream; +import java.util.Hashtable; +import java.util.Iterator; +import java.util.Vector; + +import Analysis.OwnershipAnalysis.OwnershipAnalysis; +import Analysis.TaskStateAnalysis.FEdge; +import Analysis.TaskStateAnalysis.FlagState; +import Analysis.TaskStateAnalysis.TaskAnalysis; +import IR.ClassDescriptor; +import IR.State; +import IR.TaskDescriptor; +import IR.TypeUtil; + +public class MCImplSynthesis { + + State state; + ScheduleAnalysis scheduleAnalysis; + TaskAnalysis taskAnalysis; + OwnershipAnalysis ownershipAnalysis; + ScheduleSimulator scheduleSimulator; + + int coreNum; + int scheduleThreshold; + + public MCImplSynthesis(State state, + TaskAnalysis ta, + OwnershipAnalysis oa) { + this.state = state; + this.coreNum = state.CORENUM; + this.taskAnalysis = ta; + this.ownershipAnalysis = oa; + this.scheduleAnalysis = new ScheduleAnalysis(state, + ta); + scheduleAnalysis.setCoreNum(this.coreNum); + this.scheduleSimulator = new ScheduleSimulator(this.coreNum, + state, + ta); + this.scheduleThreshold = 1000; + } + + public int getCoreNum() { + return this.scheduleAnalysis.getCoreNum(); + } + + public int getScheduleThreshold() { + return scheduleThreshold; + } + + public void setScheduleThreshold(int scheduleThreshold) { + this.scheduleThreshold = scheduleThreshold; + } + + public Vector synthesis() { + // Print stuff to the original output and error streams. + // The stuff printed through the 'origOut' and 'origErr' references + // should go to the console on most systems while the messages + // printed through the 'System.out' and 'System.err' will end up in + // the files we created for them. + //origOut.println ("\nRedirect: Round #2"); + //System.out.println ("Test output via 'SimulatorResult.out'."); + //origOut.println ("Test output via 'origOut' reference."); + + // Save the current standard input, output, and error streams + // for later restoration. + PrintStream origOut = System.out; + + // Create a new output stream for the standard output. + PrintStream stdout = null; + try { + stdout = new PrintStream(new FileOutputStream("/scratch/SimulatorResult.out")); + } catch (Exception e) { + // Sigh. Couldn't open the file. + System.out.println("Redirect: Unable to open output file!"); + System.exit(1); + } + + // Print stuff to the original output and error streams. + // On most systems all of this will end up on your console when you + // run this application. + //origOut.println ("\nRedirect: Round #1"); + //System.out.println ("Test output via 'System.out'."); + //origOut.println ("Test output via 'origOut' reference."); + + // Set the System out and err streams to use our replacements. + System.setOut(stdout); + + Vector scheduling = null; + Vector schedulinggraph = null; + int gid = 1; + + // generate multiple schedulings + this.scheduleAnalysis.setScheduleThreshold(this.scheduleThreshold); + this.scheduleAnalysis.schedule(); + + Vector> scheduleGraphs = null; + Vector> newscheduleGraphs = + this.scheduleAnalysis.getScheduleGraphs(); + Vector> schedulings = new Vector>(); + Vector selectedSchedulings = new Vector(); + Vector> selectedSimExeGraphs = + new Vector>(); + + // check all multi-parameter tasks + Vector multiparamtds = new Vector(); + Iterator it_tasks = this.state.getTaskSymbolTable().getDescriptorsIterator(); + while(it_tasks.hasNext()) { + TaskDescriptor td = (TaskDescriptor)it_tasks.next(); + if(td.numParameters() > 1) { + multiparamtds.addElement(td); + } + } + + int tryindex = 1; + int bestexetime = Integer.MAX_VALUE; + // simulate the generated schedulings and try to optimize it + do { + System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n"); + System.out.print("Simulate and optimize round: #" + tryindex + ": \n"); + gid += newscheduleGraphs.size(); + scheduleGraphs = newscheduleGraphs; + schedulings.clear(); + // get scheduling layouts from schedule graphs + for(int i = 0; i < scheduleGraphs.size(); i++) { + Vector scheduleGraph = scheduleGraphs.elementAt(i); + Vector tmpscheduling = + generateScheduling(scheduleGraph, multiparamtds); + schedulings.add(tmpscheduling); + } + selectedSchedulings.clear(); + selectedSimExeGraphs.clear(); + int tmpexetime = this.scheduleSimulator.simulate(schedulings, + selectedSchedulings, + selectedSimExeGraphs); + if(tmpexetime < bestexetime) { + bestexetime = tmpexetime; + scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0)); + schedulinggraph = newscheduleGraphs.elementAt(selectedSchedulings.elementAt(0)); + System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n"); + System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n"); + tryindex++; + } else { + break; + } + + // try to optimize the best one scheduling + newscheduleGraphs = optimizeScheduling(scheduleGraphs, + selectedSchedulings, + selectedSimExeGraphs, + gid, + this.scheduleThreshold); + }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop? + + scheduleGraphs = null; + newscheduleGraphs = null; + schedulings = null; + selectedSchedulings = null; + selectedSimExeGraphs = null; + multiparamtds = null; + + String path = "scheduling_selected.dot"; + SchedulingUtil.printScheduleGraph(path, schedulinggraph); + + // Close the streams. + try { + stdout.close(); + System.setOut(origOut); + } catch (Exception e) { + origOut.println("Redirect: Unable to close files!"); + } + + return scheduling; + } + + private Vector> optimizeScheduling(Vector> scheduleGraphs, + Vector selectedScheduleGraphs, + Vector> selectedSimExeGraphs, + int gid, + int count) { + if(this.coreNum == 1) { + // single core + return null; + } + + Vector> optimizeschedulegraphs = null; + int lgid = gid; + int left = count; + int num2try = (gid - 1) / this.scheduleThreshold; + + for(int i = 0; i < selectedScheduleGraphs.size(); i++) { + Vector schedulegraph = scheduleGraphs.elementAt( + selectedScheduleGraphs.elementAt(i)); + Vector simexegraph = selectedSimExeGraphs.elementAt(i); + Vector criticalPath = analyzeCriticalPath(simexegraph); + // for test, print out the criticalPath + if(this.state.PRINTCRITICALPATH) { + SchedulingUtil.printCriticalPath("criticalpath_" + num2try + ".dot", criticalPath); + } + num2try++; + Vector> tmposchedulegraphs = optimizeCriticalPath(schedulegraph, + criticalPath, + lgid, + left); + if(tmposchedulegraphs != null) { + if(optimizeschedulegraphs == null) { + optimizeschedulegraphs = new Vector>(); + } + optimizeschedulegraphs.addAll(tmposchedulegraphs); + lgid += tmposchedulegraphs.size(); + left -= tmposchedulegraphs.size(); + if(left == 0) { + schedulegraph = null; + simexegraph = null; + criticalPath = null; + tmposchedulegraphs = null; + break; + } + } + schedulegraph = null; + simexegraph = null; + criticalPath = null; + tmposchedulegraphs = null; + } + + return optimizeschedulegraphs; + } + + private Vector analyzeCriticalPath(Vector simexegraph) { + // first figure out the critical path + Vector criticalPath = new Vector(); + SimExecutionNode senode = (SimExecutionNode)simexegraph.elementAt(0).getSource(); + getCriticalPath(senode, criticalPath); + computeBestStartPoint(criticalPath); + + return criticalPath; + } + + private void computeBestStartPoint(Vector criticalPath) { + // calculate the earliest start time of each task on the critial path + for(int i = 0; i < criticalPath.size(); i++) { + SimExecutionEdge seedge = criticalPath.elementAt(i); + Vector predicates = seedge.getPredicates(); + if(predicates.size() > 0) { + // have predicates + int starttime = 0; + // check the latest finish time of all the predicates + for(int j = 0; j < predicates.size(); j++) { + SimExecutionEdge predicate = predicates.elementAt(j); + int tmptime = predicate.getBestStartPoint() + predicate.getWeight(); + if(tmptime > starttime) { + starttime = tmptime; + seedge.setLastpredicateEdge(predicate); + if(predicate.getTd() != null) { + seedge.setLastpredicateNode((SimExecutionNode)predicate.getTarget()); + } else { + // transfer edge + seedge.setLastpredicateNode((SimExecutionNode)predicate.getSource()); + } + } + } + seedge.setBestStartPoint(starttime); + } else if(seedge.getSource().getInedgeVector().size() > 0) { + // should have only one in edge + int starttime = ((SimExecutionNode)seedge.getSource()).getTimepoint(); + seedge.setBestStartPoint(starttime); + } else { + // no predicates + seedge.setBestStartPoint(0); + } + predicates = null; + } + } + + // TODO: currently only get one critical path. It's possible that there are + // multiple critical paths and some of them can not be optimized while others + // can. Need to fix up for this situation. + private int getCriticalPath(SimExecutionNode senode, + Vector criticalPath) { + Vector edges = (Vector)senode.getEdgeVector(); + if((edges == null) || (edges.size() == 0)) { + edges = null; + return 0; + } + Vector subcriticalpath = new Vector(); + SimExecutionEdge edge = edges.elementAt(0); + int sum = edge.getWeight() + getCriticalPath((SimExecutionNode)edge.getTarget(), + subcriticalpath); + criticalPath.clear(); + criticalPath.add(edge); + criticalPath.addAll(subcriticalpath); + for(int i = 1; i < edges.size(); i++) { + edge = edges.elementAt(i); + subcriticalpath.clear(); + int tmpsum = edge.getWeight() + + getCriticalPath((SimExecutionNode)edge.getTarget(), + subcriticalpath); + if(tmpsum > sum) { + // find a longer path + sum = tmpsum; + criticalPath.clear(); + criticalPath.add(edge); + criticalPath.addAll(subcriticalpath); + } + } + edges = null; + subcriticalpath.clear(); + subcriticalpath = null; + return sum; + } + + private Vector> optimizeCriticalPath(Vector scheduleGraph, + Vector criticalPath, + int gid, + int count) { + Vector> optimizeschedulegraphs = null; + int lgid = gid; + int left = count; + + // first check all seedges whose real start point is late than predicted + // earliest start time and group them + int opcheckpoint = Integer.MAX_VALUE; + Vector sparecores = null; + // first group according to core index, + // then group according to task type + Hashtable>> tooptimize = + new Hashtable>>(); + for(int i = 0; i < criticalPath.size(); i++) { + SimExecutionEdge seedge = criticalPath.elementAt(i); + int starttime = seedge.getBestStartPoint(); + if(starttime < ((SimExecutionNode)seedge.getSource()).getTimepoint()) { + // no restrictions due to data dependencies + // have potential to be parallelled and start execution earlier + seedge.setFixedTime(false); + // consider to optimize it only when its predicates can NOT + // be optimized, otherwise first considering optimize its predicates + if(seedge.getLastpredicateEdge().isFixedTime()) { + if(opcheckpoint >= starttime) { + // only consider the tasks with smallest best start time + if(opcheckpoint > starttime) { + tooptimize.clear(); + opcheckpoint = starttime; + sparecores = seedge.getLastpredicateNode().getSpareCores(); + } + int corenum = seedge.getCoreNum(); + if(!tooptimize.containsKey(corenum)) { + tooptimize.put(corenum, + new Hashtable>()); + } + if(!tooptimize.get(corenum).containsKey(seedge.getTd())) { + tooptimize.get(corenum).put(seedge.getTd(), + new Vector()); + } + tooptimize.get(corenum).get(seedge.getTd()).add(seedge); + } + } + } + } + + if(tooptimize.size() > 0) { + Iterator it_cores = tooptimize.keySet().iterator(); + // check if it is possible to optimize these tasks + if((sparecores == null) || (sparecores.size() == 0)) { + // lack of spare cores + while(it_cores.hasNext()) { + int corenum = it_cores.next(); + Hashtable> candidatetasks = + tooptimize.get(corenum); + if(candidatetasks.keySet().size() > 1) { + // there are multiple tasks could be optimized to start from + // this timepoint, try to change original execution order + Iterator it_tds = candidatetasks.keySet().iterator(); + TaskDescriptor td = null; + int starttime = Integer.MAX_VALUE; + do { + TaskDescriptor tmptd = it_tds.next(); + Vector seedges = candidatetasks.get(td); + int tmptime = ((SimExecutionNode)seedges.elementAt(0).getSource()).getTimepoint(); + for(int i = 1; i < seedges.size(); i++) { + int ttime = ((SimExecutionNode)seedges.elementAt(i).getSource()).getTimepoint(); + if(ttime < tmptime) { + tmptime = ttime; + } + } + if(tmptime < starttime) { + starttime = tmptime; + td = tmptd; + } + seedges = null; + }while(it_tds.hasNext()); + it_tds = null; + // TODO: only consider non-multi-param tasks currently + if(td.numParameters() == 1) { + Hashtable>> tooptimize2 = + new Hashtable>>(); + tooptimize2.put(corenum, candidatetasks); + Vector> ops = innerOptimizeCriticalPath(scheduleGraph, + tooptimize2, + lgid, + left); + if(ops != null) { + if(optimizeschedulegraphs == null) { + optimizeschedulegraphs = new Vector>(); + } + optimizeschedulegraphs.addAll(ops); + lgid += optimizeschedulegraphs.size(); + left -= optimizeschedulegraphs.size(); + } + tooptimize2.clear(); + tooptimize2 = null; + ops = null; + } + } + candidatetasks = null; + } + + if(left == 0) { + it_cores = null; + return optimizeschedulegraphs; + } + + // flush the dependences and earliest start time + it_cores = tooptimize.keySet().iterator(); + while(it_cores.hasNext()) { + Hashtable> candidatetasks = + tooptimize.get(it_cores.next()); + Iterator> it_edgevecs = + candidatetasks.values().iterator(); + while(it_edgevecs.hasNext()) { + Vector edgevec = it_edgevecs.next(); + for(int j = 0; j < edgevec.size(); j++) { + SimExecutionEdge edge = edgevec.elementAt(j); + SimExecutionEdge lastpredicateedge = edge.getLastpredicateEdge(); + SimExecutionNode lastpredicatenode = edge.getLastpredicateNode(); + // if(edge.getCoreNum() != lastpredicate.getCoreNum()) // should never hit this + int timepoint = lastpredicatenode.getTimepoint(); + if(lastpredicateedge.getTd() == null) { + // transfer edge + timepoint += lastpredicateedge.getWeight(); + } + // mapping to critical path + for(int index = 0; index < criticalPath.size(); index++) { + SimExecutionEdge tmpseedge = criticalPath.elementAt(index); + SimExecutionNode tmpsenode = + (SimExecutionNode)tmpseedge.getTarget(); + if(tmpsenode.getTimepoint() > timepoint) { + // update the predicate info + edge.getPredicates().remove(lastpredicateedge); + edge.addPredicate(criticalPath.elementAt(index)); + break; + } + } + } + edgevec = null; + } + candidatetasks = null; + it_edgevecs = null; + } + it_cores = null; + computeBestStartPoint(criticalPath); + Vector> ops = optimizeCriticalPath(scheduleGraph, + criticalPath, + lgid, + left); + if(ops != null) { + if(optimizeschedulegraphs == null) { + optimizeschedulegraphs = new Vector>(); + } + optimizeschedulegraphs.addAll(ops); + } + ops = null; + } else { + // there are spare cores, try to reorganize the tasks to the spare + // cores + Vector> ops = innerOptimizeCriticalPath(scheduleGraph, + tooptimize, + lgid, + left); + if(ops != null) { + if(optimizeschedulegraphs == null) { + optimizeschedulegraphs = new Vector>(); + } + optimizeschedulegraphs.addAll(ops); + } + ops = null; + } + } + sparecores = null; + tooptimize.clear(); + tooptimize = null; + + return optimizeschedulegraphs; + } + + private Vector> innerOptimizeCriticalPath(Vector scheduleGraph, + Hashtable>> tooptimize, + int gid, + int count) { + int lgid = gid; + int left = count; + Vector> optimizeschedulegraphs = null; + + // first clone the whole graph + Vector newscheduleGraph = + cloneScheduleGraph(scheduleGraph, lgid); + + // these nodes are root nodes + Vector roots = new Vector(); + for(int i = 0; i < newscheduleGraph.size(); i++) { + roots.add(newscheduleGraph.elementAt(i)); + } + + // map the tasks associated to SimExecutionedges to original + // ClassNode in the ScheduleGraph and split them from previous + // ScheduleGraph + Vector tocombines = new Vector(); + Iterator it_cores = tooptimize.keySet().iterator(); + while(it_cores.hasNext()) { + int corenum = it_cores.next(); + Hashtable> candidatetasks = + tooptimize.get(corenum); + Iterator it_tds = candidatetasks.keySet().iterator(); + while(it_tds.hasNext()) { + TaskDescriptor td = it_tds.next(); + int numtosplit = candidatetasks.get(td).size(); + // TODO: currently do not consider multi-param tasks + if(td.numParameters() == 1) { + ClassDescriptor cd = td.getParamType(0).getClassDesc(); + ScheduleNode snode = newscheduleGraph.elementAt(corenum); // corresponding ScheduleNode + Iterator it_cnodes = snode.getClassNodesIterator(); + Vector tosplit = new Vector(); + while((numtosplit > 0) && (it_cnodes.hasNext())) { + ClassNode cnode = it_cnodes.next(); + if(cnode.getClassDescriptor().equals(cd)) { + tosplit.add(cnode); + numtosplit--; + } + } + it_cnodes = null; + // split these node + for(int i = 0; i < tosplit.size(); i++) { + ScheduleNode splitnode = snode.spliteClassNode(tosplit.elementAt(i)); + newscheduleGraph.add(splitnode); + tocombines.add(splitnode); + } + tosplit = null; + } + } + candidatetasks = null; + it_tds = null; + } + it_cores = null; + + if(tocombines.size() == 0) { + return optimizeschedulegraphs; + } + + SchedulingUtil.assignCids(newscheduleGraph); + + // get all the ScheduleEdge + Vector scheduleEdges = new Vector(); + for(int i= 0; i < newscheduleGraph.size(); i++) { + scheduleEdges.addAll((Vector)newscheduleGraph.elementAt(i).getEdgeVector()); + } + + Vector> rootNodes = + SchedulingUtil.rangeScheduleNodes(roots); + Vector> nodes2combine = + SchedulingUtil.rangeScheduleNodes(tocombines); + + CombinationUtil.CombineGenerator cGen = + CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine); + while ((left > 0) && (cGen.nextGen())) { + Vector> combine = cGen.getCombine(); + Vector sNodes = SchedulingUtil.generateScheduleGraph(this.state, + newscheduleGraph, + scheduleEdges, + rootNodes, + combine, + lgid++); + if(optimizeschedulegraphs == null) { + optimizeschedulegraphs = new Vector>(); + } + optimizeschedulegraphs.add(sNodes); + combine = null; + sNodes = null; + left--; + } + rootNodes = null; + nodes2combine = null; + newscheduleGraph = null; + scheduleEdges.clear(); + scheduleEdges = null; + + return optimizeschedulegraphs; + } + + private Vector cloneScheduleGraph(Vector scheduleGraph, + int gid) { + Vector result = new Vector(); + + // get all the ScheduleEdge + Vector scheduleEdges = new Vector(); + for(int i= 0; i < scheduleGraph.size(); i++) { + scheduleEdges.addAll((Vector)scheduleGraph.elementAt(i).getEdgeVector()); + } + Hashtable> sn2hash = + new Hashtable>(); + Hashtable sn2sn = + new Hashtable(); + SchedulingUtil.cloneScheduleGraph(scheduleGraph, + scheduleEdges, + sn2hash, + sn2sn, + result, + gid); + + SchedulingUtil.assignCids(result); + scheduleEdges.clear(); + scheduleEdges = null; + sn2hash.clear(); + sn2hash = null; + sn2sn.clear(); + sn2sn = null; + + return result; + } + + private Vector generateScheduling(Vector scheduleGraph, + Vector multiparamtds) { + Hashtable> td2cores = + new Hashtable>(); // multiparam tasks reside on which cores + Vector scheduling = new Vector(scheduleGraph.size()); + // for each ScheduleNode create a schedule node representing a core + Hashtable sn2coreNum = + new Hashtable(); + int j = 0; + for(j = 0; j < scheduleGraph.size(); j++) { + sn2coreNum.put(scheduleGraph.elementAt(j), j); + } + int startupcore = 0; + boolean setstartupcore = false; + Schedule startup = null; + int gid = scheduleGraph.elementAt(0).getGid(); + for(j = 0; j < scheduleGraph.size(); j++) { + Schedule tmpSchedule = new Schedule(j, gid); + ScheduleNode sn = scheduleGraph.elementAt(j); + + Vector cNodes = sn.getClassNodes(); + for(int k = 0; k < cNodes.size(); k++) { + Iterator it_flags = cNodes.elementAt(k).getFlags(); + while(it_flags.hasNext()) { + FlagState fs = (FlagState)it_flags.next(); + Iterator it_edges = fs.edges(); + while(it_edges.hasNext()) { + TaskDescriptor td = ((FEdge)it_edges.next()).getTask(); + tmpSchedule.addTask(td); + if(!td2cores.containsKey(td)) { + td2cores.put(td, new Vector()); + } + Vector tmpcores = td2cores.get(td); + 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) { + tmpSchedule.addFState4TD(td, fs); + } + if(td.getParamType(0).getClassDesc().getSymbol().equals( + TypeUtil.StartupClass)) { + assert(!setstartupcore); + startupcore = j; + startup = tmpSchedule; + setstartupcore = true; + } + } + } + it_flags = null; + } + 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(); + while(it_edges.hasNext()) { + ScheduleEdge se = (ScheduleEdge)it_edges.next(); + ScheduleNode target = (ScheduleNode)se.getTarget(); + Integer targetcore = sn2coreNum.get(target); + switch(se.getType()) { + case ScheduleEdge.NEWEDGE: { + for(int k = 0; k < se.getNewRate(); k++) { + tmpSchedule.addTargetCore(se.getFstate(), targetcore); + } + break; + } + + case ScheduleEdge.TRANSEDGE: { + // 'transmit' edge + tmpSchedule.addTargetCore(se.getFstate(), + targetcore, + se.getTargetFState()); + // check if missed some FlagState associated with some multi-parameter + // task, which has been cloned when splitting a ClassNode + FlagState fs = se.getSourceFState(); + FlagState tfs = se.getTargetFState(); + Iterator it = tfs.edges(); + while(it.hasNext()) { + TaskDescriptor td = ((FEdge)it.next()).getTask(); + if(td.numParameters() > 1) { + if(tmpSchedule.getTasks().contains(td)) { + tmpSchedule.addFState4TD(td, fs); + } + } + } + break; + } + } + } + it_edges = sn.getScheduleEdgesIterator(); + while(it_edges.hasNext()) { + ScheduleEdge se = (ScheduleEdge)it_edges.next(); + switch(se.getType()) { + case ScheduleEdge.NEWEDGE: { + for(int k = 0; k < se.getNewRate(); k++) { + tmpSchedule.addTargetCore(se.getFstate(), j); + } + break; + } + + case ScheduleEdge.TRANSEDGE: { + // 'transmit' edge + tmpSchedule.addTargetCore(se.getFstate(), + j, + se.getTargetFState()); + break; + } + } + } + it_edges = null; + scheduling.add(tmpSchedule); + } + + int number = this.coreNum; + if(scheduling.size() < number) { + number = scheduling.size(); + } + + // set up all the associate ally cores + if(multiparamtds.size() > 0) { + for(j = 0; j < multiparamtds.size(); ++j) { + TaskDescriptor td = multiparamtds.elementAt(j); + Vector fes = + (Vector) this.taskAnalysis.getFEdgesFromTD(td); + Vector cores = td2cores.get(td); + for(int k = 0; k < cores.size(); ++k) { + Schedule tmpSchedule = cores.elementAt(k); + + for(int h = 0; h < fes.size(); ++h) { + FEdge tmpfe = fes.elementAt(h); + FlagState tmpfs = (FlagState)tmpfe.getTarget(); + Vector tmptds = new Vector(); + if((tmpSchedule.getTargetCoreTable() == null) + || (!tmpSchedule.getTargetCoreTable().containsKey(tmpfs))) { + // add up all possible cores' info + Iterator it_edges = tmpfs.edges(); + while(it_edges.hasNext()) { + TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask(); + if(!tmptds.contains(tmptd)) { + tmptds.add(tmptd); + Vector tmpcores = td2cores.get(tmptd); + for(int m = 0; m < tmpcores.size(); ++m) { + if(m != tmpSchedule.getCoreNum()) { + // if the FlagState can be fed to some multi-param tasks, + // need to record corresponding ally cores later + if(tmptd.numParameters() > 1) { + tmpSchedule.addAllyCore(tmpfs, + tmpcores.elementAt(m).getCoreNum()); + } else { + tmpSchedule.addTargetCore(tmpfs, + tmpcores.elementAt(m).getCoreNum()); + } + } + } + tmpcores = null; + } + } + it_edges = null; + } + tmptds = null; + } + + if(cores.size() > 1) { + Vector tmpfss = tmpSchedule.getFStates4TD(td); + for(int h = 0; h < tmpfss.size(); ++h) { + for(int l = 0; l < cores.size(); ++l) { + if(l != k) { + tmpSchedule.addAllyCore(tmpfss.elementAt(h), + cores.elementAt(l).getCoreNum()); + } + } + } + tmpfss = null; + } + } + fes = null; + cores = null; + } + } + td2cores = null; + sn2coreNum = null; + + return scheduling; + } +} diff --git a/Robust/src/Analysis/Scheduling/ObjectSimulator.java b/Robust/src/Analysis/Scheduling/ObjectSimulator.java index 3eebda44..27b2d7e1 100644 --- a/Robust/src/Analysis/Scheduling/ObjectSimulator.java +++ b/Robust/src/Analysis/Scheduling/ObjectSimulator.java @@ -5,6 +5,9 @@ import Analysis.TaskStateAnalysis.FlagState; import IR.ClassDescriptor; public class ObjectSimulator { + static int objid = 0; + + int oid; ClassDescriptor cd; FlagState currentFS; boolean changed; @@ -12,8 +15,10 @@ public class ObjectSimulator { boolean hold; int version; - public ObjectSimulator(ClassDescriptor cd, FlagState currentFS) { + public ObjectSimulator(ClassDescriptor cd, + FlagState currentFS) { super(); + this.oid = ObjectSimulator.objid++; this.cd = cd; this.currentFS = currentFS; this.changed = true; @@ -31,6 +36,10 @@ public class ObjectSimulator { } } + public int getOid() { + return oid; + } + public ClassDescriptor getCd() { return cd; } diff --git a/Robust/src/Analysis/Scheduling/Schedule.java b/Robust/src/Analysis/Scheduling/Schedule.java index 303513c7..8f8241b2 100644 --- a/Robust/src/Analysis/Scheduling/Schedule.java +++ b/Robust/src/Analysis/Scheduling/Schedule.java @@ -11,6 +11,7 @@ import IR.TaskDescriptor; /** This class holds flag transition diagram(s) can be put on one core. */ public class Schedule { + private int gid; private int coreNum; private Vector tasks; private Hashtable> targetCores; @@ -18,8 +19,9 @@ public class Schedule { private Hashtable> allyCores; private Hashtable> td2fs; - public Schedule(int coreNum) { - super(); + public Schedule(int coreNum, + int gid) { + this.gid = gid; this.coreNum = coreNum; this.tasks = null; this.targetCores = null; @@ -28,6 +30,10 @@ public class Schedule { this.td2fs = null; } + public int getGid() { + return gid; + } + public int getCoreNum() { return coreNum; } @@ -76,7 +82,8 @@ public class Schedule { return this.td2fs.get(td); } - public void addTargetCore(FlagState fstate, Integer targetCore) { + public void addTargetCore(FlagState fstate, + Integer targetCore) { if(this.targetCores == null) { this.targetCores = new Hashtable>(); } @@ -87,7 +94,9 @@ public class Schedule { // which reflects probabilities. } - public void addTargetCore(FlagState fstate, Integer targetCore, FlagState tfstate) { + public void addTargetCore(FlagState fstate, + Integer targetCore, + FlagState tfstate) { if(this.targetCores == null) { this.targetCores = new Hashtable>(); } @@ -101,7 +110,8 @@ public class Schedule { this.targetFState.put(fstate, tfstate); } - public void addAllyCore(FlagState fstate, Integer targetCore) { + public void addAllyCore(FlagState fstate, + Integer targetCore) { if(this.allyCores == null) { this.allyCores = new Hashtable>(); } @@ -114,7 +124,8 @@ public class Schedule { } } - public void addFState4TD(TaskDescriptor td, FlagState fstate) { + public void addFState4TD(TaskDescriptor td, + FlagState fstate) { if(this.td2fs == null) { this.td2fs = new Hashtable>(); } diff --git a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java index 1b33c69a..5a4a766f 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java +++ b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java @@ -14,6 +14,7 @@ public class ScheduleAnalysis { State state; TaskAnalysis taskanalysis; + Vector scheduleNodes; Vector classNodes; Vector scheduleEdges; @@ -22,26 +23,31 @@ public class ScheduleAnalysis { int transThreshold; + int scheduleThreshold; int coreNum; Vector> scheduleGraphs; - Vector> schedulings; - public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) { + public ScheduleAnalysis(State state, + TaskAnalysis taskanalysis) { this.state = state; this.taskanalysis = taskanalysis; this.scheduleNodes = new Vector(); this.classNodes = new Vector(); this.scheduleEdges = new Vector(); this.cd2ClassNode = new Hashtable(); - this.transThreshold = 45; + this.transThreshold = 45; // defaultly 45 + this.scheduleThreshold = 1000; // defaultly 1000 this.coreNum = -1; this.scheduleGraphs = null; - this.schedulings = null; } public void setTransThreshold(int tt) { this.transThreshold = tt; } + + public void setScheduleThreshold(int stt) { + this.scheduleThreshold = stt; + } public int getCoreNum() { return coreNum; @@ -51,26 +57,117 @@ public class ScheduleAnalysis { this.coreNum = coreNum; } - public Iterator getScheduleGraphs() { - return this.scheduleGraphs.iterator(); - } - - public Iterator getSchedulingsIter() { - return this.schedulings.iterator(); - } - - public Vector> getSchedulings() { - return this.schedulings; + public Vector> getScheduleGraphs() { + return this.scheduleGraphs; } // for test public Vector getSEdges4Test() { return scheduleEdges; } + + public void schedule() { + try { + Vector toBreakDown = new Vector(); + ScheduleNode startupNode = null; + + // necessary preparation such as read profile info etc. + preSchedule(); + // build the CFSTG + startupNode = buildCFSTG(toBreakDown); + // do Tree transform + treeTransform(toBreakDown, startupNode); + // do CFSTG transform to explore the potential parallelism as much + // as possible + CFSTGTransform(); + // mappint to real multi-core processor + coreMapping(); + } catch (Exception e) { + e.printStackTrace(); + System.exit(-1); + } + } + + private void preSchedule() { + this.checkBackEdge(); - public void preparation() { + // set up profiling data + if(state.USEPROFILE) { + java.util.Hashtable taskinfos = + new java.util.Hashtable(); + this.readProfileInfo(taskinfos); + + int tint = 0; + Iterator it_classes = + state.getClassSymbolTable().getDescriptorsIterator(); + while(it_classes.hasNext()) { + ClassDescriptor cd = (ClassDescriptor) it_classes.next(); + if(cd.hasFlags()) { + Vector rootnodes = this.taskanalysis.getRootNodes(cd); + if(rootnodes!=null) { + Iterator it_rootnodes = rootnodes.iterator(); + while(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 = + this.taskanalysis.getFEdgesFromTD(td); + int numEdges = fev.size(); + for(int j = 0; j < numEdges; j++) { + FEdge pfe = fev.elementAt(j); + TaskInfo taskinfo = + taskinfos.get(td.getSymbol()); + tint = taskinfo.m_exetime[pfe.getTaskExitIndex()]; + pfe.setExeTime(tint); + double idouble = + taskinfo.m_probability[pfe.getTaskExitIndex()]; + pfe.setProbability(idouble); + int newRate = 0; + if((taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()) != null) + && (taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()).containsKey(cd.getSymbol()))) { + newRate = taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()).get(cd.getSymbol()); + } + pfe.addNewObjInfo(cd, newRate, idouble); + if(taskinfo.m_byObj != -1) { + ((FlagState)pfe.getSource()).setByObj(taskinfo.m_byObj); + } + } + fev = null; + } + } + } + } + Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator(); + while(it_flags.hasNext()) { + FlagState fs = (FlagState)it_flags.next(); + Iterator it_edges = fs.edges(); + while(it_edges.hasNext()) { + FEdge edge = (FEdge)it_edges.next(); + TaskInfo taskinfo = taskinfos.get(edge.getTask().getSymbol()); + tint = taskinfo.m_exetime[edge.getTaskExitIndex()]; + edge.setExeTime(tint); + double idouble = taskinfo.m_probability[edge.getTaskExitIndex()]; + edge.setProbability(idouble); + if(taskinfo.m_byObj != -1) { + ((FlagState)edge.getSource()).setByObj(taskinfo.m_byObj); + } + } + } + } + } + taskinfos = null; + } else { + randomProfileSetting(); + } + } + + private void checkBackEdge() { // Indentify backedges - for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) { + Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); + while(it_classes.hasNext()) { ClassDescriptor cd=(ClassDescriptor) it_classes.next(); if(cd.hasFlags()) { Set fss = this.taskanalysis.getFlagStates(cd); @@ -97,280 +194,223 @@ public class ScheduleAnalysis { fss = null; } } - - // set up profiling data - if(state.USEPROFILE) { - try { - // 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); + } + + private void readProfileInfo(java.util.Hashtable taskinfos) { + try { + // 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); + + // profile data format: + // taskname, numoftaskexits(; exetime, probability, numofnewobjtypes(, newobj type, num of objs)+)+ + 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); + } + tmpinindex = inint.indexOf(','); + if(tmpinindex == -1) { + break; + } + int numofexits = Integer.parseInt(inint.substring(0, tmpinindex)); + TaskInfo tinfo = new TaskInfo(numofexits); + inint = inint.substring(tmpinindex + 1); + while(inint.startsWith(" ")) { + inint = inint.substring(1); } - String profiledata = new String(b, 0, length); - java.util.Hashtable taskinfos = new java.util.Hashtable(); + tmpinindex = inint.indexOf(';'); + int byObj = Integer.parseInt(inint.substring(0, tmpinindex)); + if(byObj != -1) { + tinfo.m_byObj = byObj; + } + inint = inint.substring(tmpinindex + 1); + while(inint.startsWith(" ")) { + inint = inint.substring(1); + } + for(int i = 0; i < numofexits; i++) { + String tmpinfo = null; + if(i < numofexits - 1) { + tmpinindex = inint.indexOf(';'); + tmpinfo = inint.substring(0, tmpinindex); + inint = inint.substring(tmpinindex + 1); + while(inint.startsWith(" ")) { + inint = inint.substring(1); + } + } else { + tmpinfo = inint; + } - // profile data format: - // taskname, numoftaskexits(; exetime, probability, numofnewobjtypes(, newobj type, num of objs)+)+ - 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; + tmpinindex = tmpinfo.indexOf(','); + tinfo.m_exetime[i] = Integer.parseInt(tmpinfo.substring(0, tmpinindex)); + tmpinfo = tmpinfo.substring(tmpinindex + 1); + while(tmpinfo.startsWith(" ")) { + tmpinfo = tmpinfo.substring(1); } - String inname = inline.substring(0, tmpinindex); - String inint = inline.substring(tmpinindex + 1); - while(inint.startsWith(" ")) { - inint = inint.substring(1); + tmpinindex = tmpinfo.indexOf(','); + tinfo.m_probability[i] = Double.parseDouble(tmpinfo.substring(0, tmpinindex)); + tmpinfo = tmpinfo.substring(tmpinindex + 1); + while(tmpinfo.startsWith(" ")) { + tmpinfo = tmpinfo.substring(1); } - tmpinindex = inint.indexOf(','); + tmpinindex = tmpinfo.indexOf(','); + int numofnobjs = 0; if(tmpinindex == -1) { - break; - } - int numofexits = Integer.parseInt(inint.substring(0, tmpinindex)); - TaskInfo tinfo = new TaskInfo(numofexits); - inint = inint.substring(tmpinindex + 1); - while(inint.startsWith(" ")) { - inint = inint.substring(1); - } - tmpinindex = inint.indexOf(';'); - int byObj = Integer.parseInt(inint.substring(0, tmpinindex)); - if(byObj != -1) { - tinfo.m_byObj = byObj; - } - inint = inint.substring(tmpinindex + 1); - while(inint.startsWith(" ")) { - inint = inint.substring(1); - } - for(int i = 0; i < numofexits; i++) { - String tmpinfo = null; - if(i < numofexits - 1) { - tmpinindex = inint.indexOf(';'); - tmpinfo = inint.substring(0, tmpinindex); - inint = inint.substring(tmpinindex + 1); - while(inint.startsWith(" ")) { - inint = inint.substring(1); - } - } else { - tmpinfo = inint; - } - - tmpinindex = tmpinfo.indexOf(','); - tinfo.m_exetime[i] = Integer.parseInt(tmpinfo.substring(0, tmpinindex)); - tmpinfo = tmpinfo.substring(tmpinindex + 1); - while(tmpinfo.startsWith(" ")) { - tmpinfo = tmpinfo.substring(1); + numofnobjs = Integer.parseInt(tmpinfo); + if(numofnobjs != 0) { + System.err.println("Error profile data format!"); + System.exit(-1); } - tmpinindex = tmpinfo.indexOf(','); - tinfo.m_probability[i] = Double.parseDouble(tmpinfo.substring(0, tmpinindex)); + } else { + tinfo.m_newobjinfo.setElementAt(new Hashtable(), i); + numofnobjs = Integer.parseInt(tmpinfo.substring(0, tmpinindex)); tmpinfo = tmpinfo.substring(tmpinindex + 1); while(tmpinfo.startsWith(" ")) { tmpinfo = tmpinfo.substring(1); } - tmpinindex = tmpinfo.indexOf(','); - int numofnobjs = 0; - if(tmpinindex == -1) { - numofnobjs = Integer.parseInt(tmpinfo); - if(numofnobjs != 0) { - System.err.println("Error profile data format!"); - System.exit(-1); - } - } else { - tinfo.m_newobjinfo.setElementAt(new Hashtable(), i); - numofnobjs = Integer.parseInt(tmpinfo.substring(0, tmpinindex)); + for(int j = 0; j < numofnobjs; j++) { + tmpinindex = tmpinfo.indexOf(','); + String nobjtype = tmpinfo.substring(0, tmpinindex); tmpinfo = tmpinfo.substring(tmpinindex + 1); while(tmpinfo.startsWith(" ")) { tmpinfo = tmpinfo.substring(1); } - for(int j = 0; j < numofnobjs; j++) { + int objnum = 0; + if(j < numofnobjs - 1) { tmpinindex = tmpinfo.indexOf(','); - String nobjtype = tmpinfo.substring(0, tmpinindex); + objnum = Integer.parseInt(tmpinfo.substring(0, tmpinindex)); tmpinfo = tmpinfo.substring(tmpinindex + 1); while(tmpinfo.startsWith(" ")) { tmpinfo = tmpinfo.substring(1); } - int objnum = 0; - if(j < numofnobjs - 1) { - tmpinindex = tmpinfo.indexOf(','); - objnum = Integer.parseInt(tmpinfo.substring(0, tmpinindex)); - tmpinfo = tmpinfo.substring(tmpinindex + 1); - while(tmpinfo.startsWith(" ")) { - tmpinfo = tmpinfo.substring(1); - } - } else { - objnum = Integer.parseInt(tmpinfo); - } - tinfo.m_newobjinfo.elementAt(i).put(nobjtype, objnum); + } else { + objnum = Integer.parseInt(tmpinfo); } + tinfo.m_newobjinfo.elementAt(i).put(nobjtype, objnum); } } - taskinfos.put(inname, tinfo); - inindex = profiledata.indexOf('\n'); } + taskinfos.put(inname, tinfo); + inindex = profiledata.indexOf('\n'); + } + } catch(Exception e) { + e.printStackTrace(); + } + } - int tint = 0; - for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) { - ClassDescriptor cd=(ClassDescriptor) it_classes.next(); - if(cd.hasFlags()) { - Vector rootnodes=this.taskanalysis.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)this.taskanalysis.getFEdgesFromTD(td); - int numEdges = fev.size(); - int total = 100; - for(int j = 0; j < numEdges; j++) { - FEdge pfe = fev.elementAt(j); - TaskInfo taskinfo = taskinfos.get(td.getSymbol()); - tint = taskinfo.m_exetime[pfe.getTaskExitIndex()]; - pfe.setExeTime(tint); - double idouble = taskinfo.m_probability[pfe.getTaskExitIndex()]; - pfe.setProbability(idouble); - int newRate = 0; - if((taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()) != null) - && (taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()).containsKey(cd.getSymbol()))) { - newRate = taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()).get(cd.getSymbol()); - } - pfe.addNewObjInfo(cd, newRate, idouble); - if(taskinfo.m_byObj != -1) { - ((FlagState)pfe.getSource()).setByObj(taskinfo.m_byObj); - } + // for test + private void randomProfileSetting() { + // 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=this.taskanalysis.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)this.taskanalysis.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); } - fev = null; + pfe.setProbability(tint); + total -= tint; } - } - } - } - Iterator it_flags = this.taskanalysis.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()) { - FEdge edge = (FEdge)it_edges.next(); - TaskInfo taskinfo = taskinfos.get(edge.getTask().getSymbol()); - tint = taskinfo.m_exetime[edge.getTaskExitIndex()]; - edge.setExeTime(tint); - double idouble = taskinfo.m_probability[edge.getTaskExitIndex()]; - edge.setProbability(idouble); - if(taskinfo.m_byObj != -1) { - ((FlagState)edge.getSource()).setByObj(taskinfo.m_byObj); - } - } - } - } - } - taskinfos = null; - } catch(Exception e) { - e.printStackTrace(); - } - } 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=this.taskanalysis.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)this.taskanalysis.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 { + //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")) || - (cdname.equals("Grid")) || - (cdname.equals("Fractal"))) { - 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); + // } 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")) || + (cdname.equals("Grid")) || + (cdname.equals("Fractal"))) { + newRate = 16; + } else if(cdname.equals("SentenceParser")) { + newRate = 4; } - fev = null; + //do { + // tint = r.nextInt()%100; + // } while(tint <= 0); + // int probability = tint; + int probability = 100; + pfe.addNewObjInfo(cd, newRate, probability); } + fev = null; } } } + } - Iterator it_flags = this.taskanalysis.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); - } + Iterator it_flags = this.taskanalysis.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); } - 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; + 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; } } } @@ -378,11 +418,13 @@ public class ScheduleAnalysis { } } - public void preSchedule() { - Hashtable cdToCNodes = new Hashtable(); + private ScheduleNode buildCFSTG(Vector toBreakDown) { + Hashtable cdToCNodes = + new Hashtable(); // Build the combined flag transition diagram // First, for each class create a ClassNode - for(Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext(); ) { + Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator(); + while(it_classes.hasNext()) { ClassDescriptor cd = (ClassDescriptor) it_classes.next(); Set fStates = taskanalysis.getFlagStates(cd); @@ -390,7 +432,8 @@ public class ScheduleAnalysis { Vector sFStates = FlagState.DFS.topology(fStates, null); Vector rootnodes = taskanalysis.getRootNodes(cd); - if(((rootnodes != null) && (rootnodes.size() > 0)) || (cd.getSymbol().equals(TypeUtil.StartupClass))) { + if(((rootnodes != null) && (rootnodes.size() > 0)) + || (cd.getSymbol().equals(TypeUtil.StartupClass))) { ClassNode cNode = new ClassNode(cd, sFStates); cNode.setSorted(true); classNodes.add(cNode); @@ -426,7 +469,7 @@ public class ScheduleAnalysis { } // Create 'new' edges between the ScheduleNodes. - Vector toBreakDown = new Vector(); + //Vector toBreakDown = new Vector(); for(i = 0; i < classNodes.size(); i++) { ClassNode cNode = classNodes.elementAt(i); ClassDescriptor cd = cNode.getClassDescriptor(); @@ -456,7 +499,11 @@ public class ScheduleAnalysis { ClassDescriptor pcd = pfs.getClassDescriptor(); ClassNode pcNode = cdToCNodes.get(pcd); - ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, ScheduleEdge.NEWEDGE, 0); + ScheduleEdge sEdge = new ScheduleEdge(sNode, + "new", + root, + ScheduleEdge.NEWEDGE, + 0); sEdge.setFEdge(pfe); sEdge.setSourceCNode(pcNode); sEdge.setTargetCNode(cNode); @@ -478,7 +525,14 @@ public class ScheduleAnalysis { } } cdToCNodes = null; - + + return startupNode; + } + + private void treeTransform(Vector toBreakDown, + ScheduleNode startupNode) { + int i = 0; + // Break down the 'cycle's try { for(i = 0; i < toBreakDown.size(); i++ ) { @@ -527,11 +581,12 @@ public class ScheduleAnalysis { toVisit = null; if(this.state.PRINTSCHEDULING) { - SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes); + SchedulingUtil.printScheduleGraph("scheduling_ori.dot", + this.scheduleNodes); } } - public void scheduleAnalysis() { + private void CFSTGTransform() { // First iteration int i = 0; //Access the ScheduleEdges in reverse topology order @@ -693,9 +748,9 @@ public class ScheduleAnalysis { ses = null; } keys = null; - fe2ses.clear(); - sn2fes.clear(); } + fe2ses.clear(); + sn2fes.clear(); fe2ses = null; sn2fes = null; @@ -704,7 +759,8 @@ public class ScheduleAnalysis { } } - private void handleScheduleEdge(ScheduleEdge se, boolean merge) { + private void handleScheduleEdge(ScheduleEdge se, + boolean merge) { try { int rate = 0; int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100); @@ -744,11 +800,13 @@ public class ScheduleAnalysis { scheduleNodes.remove(se.getTarget()); scheduleEdges.remove(se); // As se has been changed into an internal edge inside a ScheduleNode, - // change the source and target of se from original ScheduleNodes into ClassNodes. + // change the source and target of se from original ScheduleNodes + // into ClassNodes. if(se.getType() == ScheduleEdge.NEWEDGE) { se.setTarget(se.getTargetCNode()); - se.setSource(se.getSourceCNode()); - se.getTargetCNode().addEdge(se); + //se.setSource(se.getSourceCNode()); + //se.getTargetCNode().addEdge(se); + se.getSourceCNode().addEdge(se); } } else { // clone the whole ScheduleNode lists starting with se's target @@ -764,7 +822,8 @@ public class ScheduleAnalysis { } } - private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) throws Exception { + private void cloneSNodeList(ScheduleEdge sEdge, + boolean copyIE) throws Exception { Hashtable cn2cn = new Hashtable(); // hashtable from classnode in orignal se's targe to cloned one ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0); scheduleNodes.add(csNode); @@ -900,7 +959,8 @@ public class ScheduleAnalysis { return exeTime; } - private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) { + private ScheduleNode splitSNode(ScheduleEdge se, + boolean copy) { assert(ScheduleEdge.NEWEDGE == se.getType()); FEdge fe = se.getFEdge(); @@ -974,7 +1034,8 @@ public class ScheduleAnalysis { sEdge.setTransTime(cNode.getTransTime()); se.getSource().addEdge(sEdge); scheduleEdges.add(sEdge); - // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode + // remove the ClassNodes and internal ScheduleEdges out of this subtree + // to the new ScheduleNode ScheduleNode oldSNode = (ScheduleNode)se.getSource(); Iterator it_isEdges = oldSNode.getScheduleEdgesIterator(); Vector toremove = new Vector(); @@ -984,8 +1045,9 @@ public class ScheduleAnalysis { while(it_isEdges.hasNext()) { ScheduleEdge tse = (ScheduleEdge)it_isEdges.next(); if(rCNodes.contains(tse.getSourceCNode())) { - if(sCNode == tse.getSourceCNode()) { - if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) { + if(sCNode.equals(tse.getSourceCNode())) { + if (!(tse.getSourceFState().equals(fs)) + && (sFStates.contains(tse.getSourceFState()))) { tse.setSource(cNode); tse.setSourceCNode(cNode); } else { @@ -1006,8 +1068,10 @@ public class ScheduleAnalysis { Iterator it_sEdges = se.getSource().edges(); while(it_sEdges.hasNext()) { ScheduleEdge tse = (ScheduleEdge)it_sEdges.next(); - if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) { - if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) { + if(!(tse.equals(se)) && !(tse.equals(sEdge)) + && (tse.getSourceCNode().equals(sCNode))) { + if(!(tse.getSourceFState().equals(fs)) + && (sFStates.contains(tse.getSourceFState()))) { tse.setSource(sNode); tse.setSourceCNode(cNode); sNode.getEdgeVector().addElement(tse); @@ -1028,11 +1092,13 @@ public class ScheduleAnalysis { scheduleNodes.remove(se.getTarget()); scheduleEdges.removeElement(se); // As se has been changed into an internal edge inside a ScheduleNode, - // change the source and target of se from original ScheduleNodes into ClassNodes. + // change the source and target of se from original ScheduleNodes + // into ClassNodes. if(se.getType() == ScheduleEdge.NEWEDGE) { se.setTarget(se.getTargetCNode()); - se.setSource(se.getSourceCNode()); - se.getTargetCNode().addEdge(se); + //se.setSource(se.getSourceCNode()); + //se.getTargetCNode().addEdge(se); + se.getSourceCNode().addEdge(se); } } else { sNode.setCid(ScheduleNode.colorID++); @@ -1046,7 +1112,9 @@ public class ScheduleAnalysis { return sNode; } - public void schedule() throws Exception { + // TODO: restrict the number of generated scheduling according to the setted + // scheduleThreshold + private void coreMapping() throws Exception { if(this.coreNum == -1) { throw new Exception("Error: un-initialized coreNum when doing scheduling."); } @@ -1068,32 +1136,31 @@ public class ScheduleAnalysis { SchedulingUtil.printScheduleGraph(path, this.scheduleNodes); } } else { - // Go through all the Scheudle Nodes, organize them in order of their cid - Vector> sNodeVecs = new Vector>(); - for(int i = 0; i < this.scheduleNodes.size(); i++) { - ScheduleNode tmpn = this.scheduleNodes.elementAt(i); - int index = tmpn.getCid(); - while(sNodeVecs.size() <= index) { - sNodeVecs.add(null); - } - if(sNodeVecs.elementAt(index) == null) { - sNodeVecs.setElementAt(new Vector(), index); - } - sNodeVecs.elementAt(index).add(tmpn); - } + // Go through all the Schedule Nodes, organize them in order of their cid + Vector> sNodeVecs = + SchedulingUtil.rangeScheduleNodes(this.scheduleNodes); - CombinationUtil.RootsGenerator rGen = CombinationUtil.allocateRootsGenerator(sNodeVecs, this.coreNum); + CombinationUtil.RootsGenerator rGen = + CombinationUtil.allocateRootsGenerator(sNodeVecs, + this.coreNum); int gid = 1; - while(rGen.nextGen()) { + while((gid <= this.scheduleThreshold) && (rGen.nextGen())) { // first get the chosen rootNodes Vector> rootNodes = rGen.getRootNodes(); Vector> nodes2combine = rGen.getNode2Combine(); - CombinationUtil.CombineGenerator cGen = CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine); - while (cGen.nextGen()) { + CombinationUtil.CombineGenerator cGen = + CombinationUtil.allocateCombineGenerator(rootNodes, + nodes2combine); + while((gid <= this.scheduleThreshold) && cGen.nextGen()) { Vector> combine = cGen.getCombine(); - Vector sNodes = generateScheduling(rootNodes, combine, gid++); + Vector sNodes = SchedulingUtil.generateScheduleGraph(this.state, + this.scheduleNodes, + this.scheduleEdges, + rootNodes, + combine, + gid++); this.scheduleGraphs.add(sNodes); combine = null; sNodes = null; @@ -1103,280 +1170,6 @@ public class ScheduleAnalysis { } sNodeVecs = null; } - - // Generate schedulings according to result schedule graph - if(this.schedulings == null) { - this.schedulings = new Vector>(); - } - - Vector multiparamtds = new Vector(); - Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator(); - while(it_tasks.hasNext()) { - TaskDescriptor td = (TaskDescriptor)it_tasks.next(); - if(td.numParameters() > 1) { - multiparamtds.addElement(td); - } - } - - for(int i = 0; i < this.scheduleGraphs.size(); i++) { - Hashtable> td2cores = new Hashtable>(); // multiparam tasks reside on which cores - Vector scheduleGraph = this.scheduleGraphs.elementAt(i); - Vector scheduling = new Vector(scheduleGraph.size()); - // for each ScheduleNode create a schedule node representing a core - Hashtable sn2coreNum = new Hashtable(); - int j = 0; - for(j = 0; j < scheduleGraph.size(); j++) { - sn2coreNum.put(scheduleGraph.elementAt(j), j); - } - int startupcore = 0; - boolean setstartupcore = false; - Schedule startup = null; - for(j = 0; j < scheduleGraph.size(); j++) { - Schedule tmpSchedule = new Schedule(j); - ScheduleNode sn = scheduleGraph.elementAt(j); - - Vector cNodes = sn.getClassNodes(); - for(int k = 0; k < cNodes.size(); k++) { - Iterator it_flags = cNodes.elementAt(k).getFlags(); - while(it_flags.hasNext()) { - FlagState fs = (FlagState)it_flags.next(); - Iterator it_edges = fs.edges(); - while(it_edges.hasNext()) { - TaskDescriptor td = ((FEdge)it_edges.next()).getTask(); - tmpSchedule.addTask(td); - if(!td2cores.containsKey(td)) { - td2cores.put(td, new Vector()); - } - Vector tmpcores = td2cores.get(td); - 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) { - tmpSchedule.addFState4TD(td, fs); - } - if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) { - assert(!setstartupcore); - startupcore = j; - startup = tmpSchedule; - setstartupcore = true; - } - } - } - } - 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(); - while(it_edges.hasNext()) { - ScheduleEdge se = (ScheduleEdge)it_edges.next(); - ScheduleNode target = (ScheduleNode)se.getTarget(); - Integer targetcore = sn2coreNum.get(target); - switch(se.getType()) { - case ScheduleEdge.NEWEDGE: { - for(int k = 0; k < se.getNewRate(); k++) { - tmpSchedule.addTargetCore(se.getFstate(), targetcore); - } - break; - } - - case ScheduleEdge.TRANSEDGE: { - // 'transmit' edge - tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState()); - // check if missed some FlagState associated with some multi-parameter - // task, which has been cloned when splitting a ClassNode - FlagState fs = se.getSourceFState(); - FlagState tfs = se.getTargetFState(); - Iterator it = tfs.edges(); - while(it.hasNext()) { - TaskDescriptor td = ((FEdge)it.next()).getTask(); - if(td.numParameters() > 1) { - if(tmpSchedule.getTasks().contains(td)) { - tmpSchedule.addFState4TD(td, fs); - } - } - } - break; - } - } - } - it_edges = sn.getScheduleEdgesIterator(); - while(it_edges.hasNext()) { - ScheduleEdge se = (ScheduleEdge)it_edges.next(); - switch(se.getType()) { - case ScheduleEdge.NEWEDGE: { - for(int k = 0; k < se.getNewRate(); k++) { - tmpSchedule.addTargetCore(se.getFstate(), j); - } - break; - } - - case ScheduleEdge.TRANSEDGE: { - // 'transmit' edge - tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState()); - break; - } - } - } - scheduling.add(tmpSchedule); - } - - int number = this.coreNum; - if(scheduling.size() < number) { - number = scheduling.size(); - } - - // set up all the associate ally cores - if(multiparamtds.size() > 0) { - for(j = 0; j < multiparamtds.size(); ++j) { - TaskDescriptor td = multiparamtds.elementAt(j); - Vector fes = (Vector) this.taskanalysis.getFEdgesFromTD(td); - Vector cores = td2cores.get(td); - for(int k = 0; k < cores.size(); ++k) { - Schedule tmpSchedule = cores.elementAt(k); - - for(int h = 0; h < fes.size(); ++h) { - FEdge tmpfe = fes.elementAt(h); - FlagState tmpfs = (FlagState)tmpfe.getTarget(); - Vector tmptds = new Vector(); - if((tmpSchedule.getTargetCoreTable() == null) || (!tmpSchedule.getTargetCoreTable().contains(tmpfs))) { - // add up all possible cores' info - Iterator it_edges = tmpfs.edges(); - while(it_edges.hasNext()) { - TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask(); - if(!tmptds.contains(tmptd)) { - tmptds.add(tmptd); - Vector tmpcores = td2cores.get(tmptd); - for(int m = 0; m < tmpcores.size(); ++m) { - if(m != tmpSchedule.getCoreNum()) { - // if the FlagState can be fed to some multi-param tasks, - // need to record corresponding ally cores later - if(tmptd.numParameters() > 1) { - tmpSchedule.addAllyCore(tmpfs, tmpcores.elementAt(m).getCoreNum()); - } else { - tmpSchedule.addTargetCore(tmpfs, tmpcores.elementAt(m).getCoreNum()); - } - } - } - tmpcores = null; - } - } - } - tmptds = null; - } - - if(cores.size() > 1) { - Vector tmpfss = tmpSchedule.getFStates4TD(td); - for(int h = 0; h < tmpfss.size(); ++h) { - for(int l = 0; l < cores.size(); ++l) { - if(l != k) { - tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum()); - } - } - } - 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) { - Vector result = new Vector(); - - // clone the ScheduleNodes - Hashtable> sn2hash = new Hashtable>(); - Hashtable sn2sn = new Hashtable(); - for(int i = 0; i < this.scheduleNodes.size(); i++) { - Hashtable cn2cn = new Hashtable(); - ScheduleNode tocopy = this.scheduleNodes.elementAt(i); - ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid); - result.add(i, temp); - sn2hash.put(temp, cn2cn); - sn2sn.put(tocopy, temp); - cn2cn = null; - } - // clone the ScheduleEdges - for(int i = 0; i < this.scheduleEdges.size(); i++) { - ScheduleEdge sse = this.scheduleEdges.elementAt(i); - ScheduleNode csource = sn2sn.get(sse.getSource()); - ScheduleNode ctarget = sn2sn.get(sse.getTarget()); - Hashtable sourcecn2cn = sn2hash.get(csource); - Hashtable targetcn2cn = sn2hash.get(ctarget); - ScheduleEdge se = null; - switch(sse.getType()) { - case ScheduleEdge.NEWEDGE: { - se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid); - se.setProbability(sse.getProbability()); - se.setNewRate(sse.getNewRate()); - break; - } - - case ScheduleEdge.TRANSEDGE: { - se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid); - break; - } - } - se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode())); - se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode())); - se.setFEdge(sse.getFEdge()); - se.setTargetFState(sse.getTargetFState()); - se.setIsclone(true); - csource.addEdge(se); - sourcecn2cn = null; - targetcn2cn = null; - } - - // combine those nodes in combine with corresponding rootnodes - for(int i = 0; i < combine.size(); i++) { - if(combine.elementAt(i) != null) { - for(int j = 0; j < combine.elementAt(i).size(); j++) { - CombinationUtil.Combine tmpcombine = combine.elementAt(i).elementAt(j); - ScheduleNode tocombine = sn2sn.get(tmpcombine.node); - ScheduleNode root = sn2sn.get(rootnodes.elementAt(tmpcombine.root).elementAt(tmpcombine.index)); - ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next(); - try { - if(root.equals(((ScheduleNode)se.getSource()))) { - root.mergeSEdge(se); - if(ScheduleEdge.NEWEDGE == se.getType()) { - // As se has been changed into an internal edge inside a ScheduleNode, - // change the source and target of se from original ScheduleNodes into ClassNodes. - se.setTarget(se.getTargetCNode()); - se.setSource(se.getSourceCNode()); - se.getTargetCNode().addEdge(se); - } - } else { - root.mergeSNode(tocombine); - } - } catch(Exception e) { - e.printStackTrace(); - System.exit(-1); - } - result.removeElement(tocombine); - } - } - } - - sn2hash = null; - sn2sn = null; - - if(this.state.PRINTSCHEDULING) { - String path = "scheduling_" + gid + ".dot"; - SchedulingUtil.printScheduleGraph(path, result); - } - - return result; } static class TaskInfo { diff --git a/Robust/src/Analysis/Scheduling/ScheduleEdge.java b/Robust/src/Analysis/Scheduling/ScheduleEdge.java index 1d2ec6a1..fbda26d1 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleEdge.java +++ b/Robust/src/Analysis/Scheduling/ScheduleEdge.java @@ -38,7 +38,11 @@ public class ScheduleEdge extends Edge { /** Class Constructor * */ - public ScheduleEdge(ScheduleNode target, String label, FlagState fstate, int type, int gid) { + public ScheduleEdge(ScheduleNode target, + String label, + FlagState fstate, + int type, + int gid) { super(target); this.uid = ScheduleEdge.nodeID++; this.gid = gid; diff --git a/Robust/src/Analysis/Scheduling/ScheduleNode.java b/Robust/src/Analysis/Scheduling/ScheduleNode.java index 273473a7..b8d993bb 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleNode.java +++ b/Robust/src/Analysis/Scheduling/ScheduleNode.java @@ -17,9 +17,11 @@ public class ScheduleNode extends GraphNode implements Cloneable { public static int colorID = 0; private Vector classNodes; - Vector scheduleEdges; + private Vector scheduleEdges; private int executionTime; + + private int hashcid; /** Class constructor * @param cd ClassDescriptor @@ -32,6 +34,7 @@ public class ScheduleNode extends GraphNode implements Cloneable { this.executionTime = -1; this.classNodes = null; this.scheduleEdges = null; + this.hashcid = 0; } public ScheduleNode(ClassNode cn, int gid) { @@ -43,6 +46,11 @@ public class ScheduleNode extends GraphNode implements Cloneable { this.classNodes.add(cn); this.addEdge(cn.getEdgeVector()); this.executionTime = -1; + this.hashcid = 0; + } + + public int getGid() { + return gid; } public int getuid() { @@ -96,6 +104,38 @@ public class ScheduleNode extends GraphNode implements Cloneable { scheduleEdges = null; } + public int getHashcid() { + return hashcid; + } + + public void computeHashcid() { + this.hashcid = 0; + /*if(this.mergedcids != null) { + for(int i = 0; i < this.mergedcids.size(); i++) { + this.hashcid = this.hashcid * 31 + this.mergedcids.elementAt(i); + } + }*/ + Vector mergedcids = new Vector(); + for(int i = 0; i < this.classNodes.size(); i++) { + int tomerge = this.classNodes.elementAt(i).getCid(); + mergedcids.add(tomerge); + // insert tomerge in accent order + int j = mergedcids.size() - 1; + for( ; j > 0; j--) { + int tmp = mergedcids.elementAt(j-1); + if(tmp > tomerge) { + mergedcids.setElementAt(tmp, j); + } else { + break; + } + } + mergedcids.setElementAt(tomerge, j); + } + for(int i = 0; i < mergedcids.size(); i++) { + this.hashcid = this.hashcid * 31 + mergedcids.elementAt(i); + } + } + public int getExeTime() { if(this.executionTime == -1) { try { @@ -167,7 +207,8 @@ public class ScheduleNode extends GraphNode implements Cloneable { return label; } - public Object clone(Hashtable cn2cn, int gid) { + public Object clone(Hashtable cn2cn, + int gid) { ScheduleNode o = null; try { o = (ScheduleNode) super.clone(); @@ -193,14 +234,22 @@ public class ScheduleNode extends GraphNode implements Cloneable { ScheduleEdge se = null; switch(temp.getType()) { case ScheduleEdge.NEWEDGE: { - se = new ScheduleEdge(o, "new", temp.getFstate(), ScheduleEdge.NEWEDGE, gid); + se = new ScheduleEdge(o, + "new", + temp.getFstate(), + ScheduleEdge.NEWEDGE, + gid); se.setProbability(temp.getProbability()); se.setNewRate(temp.getNewRate()); break; } case ScheduleEdge.TRANSEDGE: { - se = new ScheduleEdge(o, "transmit", temp.getFstate(), ScheduleEdge.TRANSEDGE, gid); + se = new ScheduleEdge(o, + "transmit", + temp.getFstate(), + ScheduleEdge.TRANSEDGE, + gid); se.setProbability(temp.getProbability()); se.setNewRate(temp.getNewRate()); break; @@ -213,6 +262,9 @@ public class ScheduleNode extends GraphNode implements Cloneable { se.setTargetFState(temp.getTargetFState()); se.setIsclone(true); tses.add(se); + // internal edge, it's source and target have been redirected to ClassNodes + se.setTarget(se.getTargetCNode()); + se.getSourceCNode().addEdge(se); } o.classNodes = tcns; o.scheduleEdges = tses; @@ -336,7 +388,7 @@ public class ScheduleNode extends GraphNode implements Cloneable { } } - public void mergeSNode(ScheduleNode sn) throws Exception { + public void mergeSNode(ScheduleNode sn) { Vector targetCNodes = (Vector)sn.getClassNodes(); Vector targetSEdges = (Vector)sn.getScheduleEdges(); @@ -379,6 +431,72 @@ public class ScheduleNode extends GraphNode implements Cloneable { this.executionTime = 0; } this.executionTime += sn.getExeTime(); - + } + + public ScheduleNode spliteClassNode(ClassNode cd) { + ScheduleNode sNode = new ScheduleNode(cd, this.gid); + + this.classNodes.remove(cd); + cd.setScheduleNode(sNode); + try { + sNode.calExeTime(); + } catch (Exception e) { + e.printStackTrace(); + } + + // redirct all corresponding internal ScheduleEdge to the new snode + Iterator it_innersEdges = this.scheduleEdges.iterator(); + Vector toremove = new Vector(); + if(it_innersEdges != null) { + while(it_innersEdges.hasNext()) { + ScheduleEdge tse = (ScheduleEdge)it_innersEdges.next(); + if((cd.equals(tse.getSourceCNode())) || (cd.equals(tse.getTargetCNode()))) { + // related edge + toremove.addElement(tse); + } + } + } + this.scheduleEdges.removeAll(toremove); + for(int i = 0; i < toremove.size(); i++) { + ScheduleEdge tse = toremove.elementAt(i); + if(cd.equals(tse.getSourceCNode())) { + // outedge + tse.setTarget(this); + sNode.addEdge(tse); + } else if(cd.equals(tse.getTargetCNode())){ + // inedge + tse.setTarget(sNode); + this.addEdge(tse); + } + } + toremove.clear(); + // redirect external ScheudleEdges out of this cd to the new ScheduleNode + Iterator it_exsEdges = this.edges(); + while(it_exsEdges.hasNext()) { + ScheduleEdge tse = (ScheduleEdge)it_exsEdges.next(); + if(tse.getSourceCNode().equals(cd)) { + this.removeEdge(tse); + sNode.addEdge(tse); + } + } + // redirect inedges whose target is this Classnode to new ScheduleNode + Iterator it_insEdges = this.inedges(); + while(it_insEdges.hasNext()) { + ScheduleEdge tse = (ScheduleEdge)it_insEdges.next(); + if(tse.getTargetCNode().equals(cd)) { + toremove.add(tse); + tse.setTarget(sNode); + } + } + this.inedges.removeAll(toremove); + toremove.clear(); + toremove = null; + + // As all tasks inside one ScheduleNode are executed sequentially, + // simply subtract the execution time of the ClassNode . + assert(this.executionTime != -1); + this.executionTime -= sNode.getExeTime(); + + return sNode; } } diff --git a/Robust/src/Analysis/Scheduling/ScheduleSimulator.java b/Robust/src/Analysis/Scheduling/ScheduleSimulator.java index 21052466..190fe939 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleSimulator.java +++ b/Robust/src/Analysis/Scheduling/ScheduleSimulator.java @@ -21,36 +21,37 @@ public class ScheduleSimulator { private Vector scheduling; private Vector cores; private Vector tasks; - private Vector checkpoints; private int processTime; private int invoketime; State state; TaskAnalysis taskanalysis; - public ScheduleSimulator(int coreNum, State state, TaskAnalysis taskanalysis) { - super(); - this.coreNum = coreNum; + public ScheduleSimulator(int corenum, + State state, + TaskAnalysis taskanalysis) { + this.coreNum = corenum; this.scheduling = null; this.cores = null; this.tasks = null; - this.checkpoints = null; this.processTime = 0; this.invoketime = 0; this.state = state; this.taskanalysis = taskanalysis; } - public ScheduleSimulator(int coreNum, Vector scheduling, State state, TaskAnalysis taskanalysis) { + public ScheduleSimulator(int corenum, + Vector scheduling, + State state, + TaskAnalysis taskanalysis) { super(); - this.coreNum = coreNum; + this.coreNum = corenum; this.scheduling = scheduling; this.cores = new Vector(this.coreNum); for(int i = 0; i < this.coreNum; i++) { this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i)); } this.tasks = new Vector(); - this.checkpoints = null; this.processTime = 0; this.invoketime = 0; this.state = state; @@ -58,109 +59,82 @@ public class ScheduleSimulator { applyScheduling(); } - public Vector simulate(Vector> schedulings) { - // Print stuff to the original output and error streams. - // The stuff printed through the 'origOut' and 'origErr' references - // should go to the console on most systems while the messages - // printed through the 'System.out' and 'System.err' will end up in - // the files we created for them. - //origOut.println ("\nRedirect: Round #2"); - //System.out.println ("Test output via 'SimulatorResult.out'."); - //origOut.println ("Test output via 'origOut' reference."); - - // Save the current standard input, output, and error streams - // for later restoration. - PrintStream origOut = System.out; - - // Create a new output stream for the standard output. - PrintStream stdout = null; - try { - stdout = new PrintStream(new FileOutputStream("/scratch/SimulatorResult.out")); - } catch (Exception e) { - // Sigh. Couldn't open the file. - System.out.println("Redirect: Unable to open output file!"); - System.exit(1); - } - - // Print stuff to the original output and error streams. - // On most systems all of this will end up on your console when you - // run this application. - //origOut.println ("\nRedirect: Round #1"); - //System.out.println ("Test output via 'System.out'."); - //origOut.println ("Test output via 'origOut' reference."); - - // Set the System out and err streams to use our replacements. - System.setOut(stdout); - - Vector selectedScheduling = new Vector(); + public int simulate(Vector> schedulings, + Vector selectedScheduling, + Vector> selectedSimExeGraphs) { int processTime = Integer.MAX_VALUE; - if(schedulings.size() > 1500) { + /*if(schedulings.size() > 1500) { int index = 0; int upperbound = schedulings.size(); long seed = 0; java.util.Random r = new java.util.Random(seed); for(int ii = 0; ii < 1500; ii++) { - index = (int)((Math.abs((double)r.nextInt() / (double)Integer.MAX_VALUE)) * upperbound); + index = (int)((Math.abs((double)r.nextInt() + /(double)Integer.MAX_VALUE)) * upperbound); System.out.println("Scheduling index:" + index); - //System.err.println("Scheduling index:" + index); Vector scheduling = schedulings.elementAt(index); this.setScheduling(scheduling); - int tmpTime = this.process(); + Vector simexegraph = new Vector(); + Vector checkpoints = new Vector(); + int tmpTime = this.process(checkpoints, simexegraph); if(tmpTime < processTime) { selectedScheduling.clear(); selectedScheduling.add(index); + selectedSimExeGraphs.clear(); + selectedSimExeGraphs.add(simexegraph); processTime = tmpTime; } else if(tmpTime == processTime) { selectedScheduling.add(index); + selectedSimExeGraphs.add(simexegraph); } scheduling = null; + checkpoints = null; + simexegraph = null; } - } else { + } else {*/ Iterator it_scheduling = schedulings.iterator(); int index = 0; while(it_scheduling.hasNext()) { - Vector scheduling = (Vector)it_scheduling.next(); + Vector scheduling = + (Vector)it_scheduling.next(); + System.out.println("Scheduling index:" + scheduling.elementAt(0).getGid()); this.setScheduling(scheduling); - int tmpTime = this.process(); + Vector simexegraph = new Vector(); + Vector checkpoints = new Vector(); + int tmpTime = this.process(checkpoints, simexegraph); if(tmpTime < processTime) { selectedScheduling.clear(); selectedScheduling.add(index); + selectedSimExeGraphs.clear(); + selectedSimExeGraphs.add(simexegraph); processTime = tmpTime; } else if(tmpTime == processTime) { selectedScheduling.add(index); + selectedSimExeGraphs.add(simexegraph); } scheduling = null; + checkpoints = null; index++; } - } - + it_scheduling = null; + //} + System.out.print("Selected schedulings with least exectution time " + processTime + ": \n\t"); for(int i = 0; i < selectedScheduling.size(); i++) { - System.out.print((selectedScheduling.elementAt(i) + 1) + ", "); + int gid = schedulings.elementAt(selectedScheduling.elementAt(i)).elementAt(0).getGid(); + System.out.print(gid + ", "); } System.out.println(); - // Close the streams. - try { - stdout.close(); - System.setOut(origOut); - } catch (Exception e) { - origOut.println("Redirect: Unable to close files!"); - } - - return selectedScheduling; - } - - public Vector getCheckpoints() { - return checkpoints; + return processTime; } public int getCoreNum() { - return coreNum; + return this.coreNum; } - public void setCoreNum(int coreNum) { - this.coreNum = coreNum; + public void setCoreNum(int corenum) { + this.coreNum = corenum; if(this.cores != null) { this.cores.clear(); } @@ -200,9 +174,6 @@ public class ScheduleSimulator { this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i)); } } - if(this.checkpoints != null) { - this.checkpoints.clear(); - } applyScheduling(); } @@ -231,18 +202,25 @@ public class ScheduleSimulator { return tasks; } - public int process() { + public int process(Vector checkpoints, + Vector simexegraph) { assert(this.scheduling != null); this.invoketime++; - - if(this.checkpoints == null) { - this.checkpoints = new Vector(); - } /*else { - this.checkpoints.clear(); - }*/ - this.processTime = 0; + + // helper structures for building SimExecutionGraph + Hashtable senode2action = + new Hashtable(); + SimExecutionNode[] lastseNodes = new SimExecutionNode[this.cores.size()]; + Hashtable action2exetime = + new Hashtable(); + Hashtable tttask2senode = + new Hashtable(); + Hashtable obj2transtime = + new Hashtable(); + Hashtable obj2lastseedge = + new Hashtable(); // first decide next task to execute on each core int i = 0; @@ -252,17 +230,29 @@ public class ScheduleSimulator { if(task != null) { this.tasks.add(task); } + lastseNodes[i] = null; } // add STARTTASK checkpoint for all the initial tasks - CheckPoint cp = new CheckPoint(this.processTime); + CheckPoint cp = new CheckPoint(this.processTime, + this.coreNum); for(i = 0; i < this.tasks.size(); i++) { TaskSimulator task = this.tasks.elementAt(i); - Action action = new Action(task.getCs().getCoreNum(), Action.TASKSTART); - action.setTd(task.getTd()); + int coreid = task.getCs().getCoreNum(); + Action action = new Action(coreid, + Action.TASKSTART, + task); cp.addAction(action); + if(!(task instanceof TransTaskSimulator)) { + cp.removeSpareCore(coreid); + SimExecutionNode seNode = new SimExecutionNode(coreid, this.processTime); + seNode.setSpareCores(cp.getSpareCores()); + senode2action.put(seNode, action); + action2exetime.put(action, -1); + lastseNodes[coreid] = seNode; + } } - this.checkpoints.add(cp); + checkpoints.add(cp); while(true) { // if no more tasks on each core, simulation finish @@ -272,7 +262,6 @@ public class ScheduleSimulator { // for each task in todo queue, decide the execution path of this time // according to statistic information - //int index = 0; // indicate the task to finish first int finishTime = Integer.MAX_VALUE; Vector finishTasks = new Vector(); for(i = 0; i < this.tasks.size(); i++) { @@ -287,219 +276,550 @@ public class ScheduleSimulator { finishTasks.add(task); } } + + // advance to next finish point + this.processTime += finishTime; + cp = new CheckPoint(this.processTime, + this.coreNum); for(i = 0; i < this.tasks.size(); i++) { TaskSimulator task = this.tasks.elementAt(i); if(!finishTasks.contains(task)) { task.getCs().updateTask(finishTime); + if(!(task instanceof TransTaskSimulator)) { + cp.removeSpareCore(task.getCs().getCoreNum()); + } } } - this.processTime += finishTime; - cp = new CheckPoint(this.processTime); + Action action = null; for(i = 0; i < finishTasks.size(); i++) { TaskSimulator task = finishTasks.elementAt(i); this.tasks.removeElement(task); if(task instanceof TransTaskSimulator) { - TransTaskSimulator tmptask = (TransTaskSimulator)task; - // add ADDOBJ task to targetCore - int targetCoreNum = tmptask.getTargetCoreNum(); - ObjectInfo objinfo = tmptask.refreshTask(); - ObjectSimulator nobj = objinfo.obj; - FlagState fs = objinfo.fs; - int version = objinfo.version; - this.cores.elementAt(targetCoreNum).addObject(nobj, fs, version); - action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd()); - cp.addAction(action); - if(!tmptask.isFinished()) { - // still have some objects to be transpotted - this.tasks.add(task); + // handle TransTaskSimulator task's completion + finishTransTaskSimulator(task, + cp, + simexegraph, + senode2action, + lastseNodes, + action2exetime, + tttask2senode, + obj2transtime); + } else { + CoreSimulator cs = task.getCs(); + Vector tttasks = new Vector(); + + Vector transObjs = null; + if(task.getCurrentRun().getExetype() == 0) { + // normal execution of a task + transObjs = finishTaskNormal(task, + cp, + tttasks, + senode2action, + lastseNodes, + action2exetime); + } else if (task.getCurrentRun().getExetype() == 1) { + // task abort + finishTaskAbnormal(cs, + cp, + senode2action, + lastseNodes, + action2exetime, + Action.TASKABORT); + } else if (task.getCurrentRun().getExetype() == 2) { + // task remove + finishTaskAbnormal(cs, + cp, + senode2action, + lastseNodes, + action2exetime, + Action.TASKREMOVE); } - if(this.cores.elementAt(targetCoreNum).getRtask() == null) { - TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process(); - if(newTask != null) { + + // Choose a new task for this core + generateNewTask(cs, + cp, + transObjs, + tttasks, + simexegraph, + senode2action, + lastseNodes, + action2exetime, + tttask2senode, + obj2transtime, + obj2lastseedge); + tttasks.clear(); + tttasks = null; + transObjs = null; + }// end of if(task instanceof TransTaskSimulator) else + } + checkpoints.add(cp); + finishTasks = null; + } // end of while(true) + + // add the end node into the SimExecutionGraph + SimExecutionNode seNode = new SimExecutionNode(this.coreNum, this.processTime); + for(int j = 0; j < lastseNodes.length; j++) { + SimExecutionNode lastsenode = lastseNodes[j]; + // create edges between previous senode on this core to this node + if(lastsenode != null) { + Action tmpaction = senode2action.get(lastsenode); + int weight = tmpaction != null? action2exetime.get(tmpaction) : 0; // TODO ???? + SimExecutionEdge seEdge = new SimExecutionEdge(seNode, + lastsenode.getCoreNum(), + tmpaction != null? tmpaction.getTd():null, + weight, + tmpaction != null? tmpaction.getTaskParams():null); + lastsenode.addEdge(seEdge); + + // setup data dependencies for the task + Vector taskparams = seEdge.getTaskparams(); + if(taskparams != null) { + for(int k = 0; k < taskparams.size(); k++) { + Integer tparam = taskparams.elementAt(k); + SimExecutionEdge lastedge = obj2lastseedge.get(tparam); + if(lastedge != null) { + if(lastedge.getCoreNum() != seEdge.getCoreNum()) { + // the obj is transferred from another core + // create an seEdge for this transfer + int transweight = obj2transtime.get(tparam); + SimExecutionEdge transseEdge = new SimExecutionEdge((SimExecutionNode)seEdge.getSource(), + lastedge.getCoreNum(), + null, // TODO: not sure if this is enough + transweight, + null); + if(((SimExecutionNode)seEdge.getSource()).getTimepoint() < + ((SimExecutionNode)lastedge.getTarget()).getTimepoint()) { + System.err.println("ScheduleSimulator:393"); + System.exit(-1); + } + lastedge.getTarget().addEdge(transseEdge); + simexegraph.add(transseEdge); + transseEdge.addPredicate(lastedge); + seEdge.addPredicate(transseEdge); + } else { + seEdge.addPredicate(lastedge); + } + } + // update the last edge associated to the parameter obj + obj2lastseedge.put(tparam, seEdge); + } + } + taskparams = null; + simexegraph.add(seEdge); // add the seEdge afger all corresponding transfer edges + } + lastseNodes[j] = null; + } + + senode2action.clear(); + senode2action = null; + lastseNodes = null; + action2exetime.clear(); + action2exetime = null; + tttask2senode.clear(); + tttask2senode = null; + obj2transtime.clear(); + obj2transtime = null; + obj2lastseedge.clear(); + obj2lastseedge = null; + + int gid = this.scheduling.elementAt(0).getGid(); + if(this.state.PRINTSCHEDULESIM) { + SchedulingUtil.printSimulationResult("SimulatorResult_" + gid + ".dot", + this.processTime, + this.coreNum, + checkpoints); + } + System.out.println("Simulate scheduling #" + gid + ": "); + System.out.println("\tTotal execution time is: " + this.processTime); + System.out.println("\tUtility of cores: "); + for(int j = 0; j < this.cores.size(); j++) { + System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%"); + } + + return this.processTime; + } + + private void finishTransTaskSimulator(TaskSimulator task, + CheckPoint cp, + Vector simexegraph, + Hashtable senode2action, + SimExecutionNode[] lastseNodes, + Hashtable action2exetime, + Hashtable tttask2senode, + Hashtable obj2transtime) { + TransTaskSimulator tmptask = (TransTaskSimulator)task; + // add ADDOBJ task to targetCore + int targetCoreNum = tmptask.getTargetCoreNum(); + ObjectInfo objinfo = tmptask.refreshTask(); + ObjectSimulator nobj = objinfo.obj; + FlagState fs = objinfo.fs; + int version = objinfo.version; + this.cores.elementAt(targetCoreNum).addObject(nobj, fs, version); + Action action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd()); + cp.addAction(action); + + // get the obj transfer time and associated senode + SimExecutionNode senode = tttask2senode.get(tmptask); + obj2transtime.put(nobj.getOid(), this.processTime - senode.getTimepoint()); + + if(!tmptask.isFinished()) { + // still have some objects to be transferred + this.tasks.add(task); + } + if(this.cores.elementAt(targetCoreNum).getRtask() == null) { + TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process(); + if(newTask != null) { this.tasks.add(newTask); // add a TASKSTART action into this checkpoint - action = new Action(targetCoreNum, Action.TASKSTART); - action.setTd(newTask.getTd()); + action = new Action(targetCoreNum, + Action.TASKSTART, + newTask); cp.addAction(action); - } + if(!(newTask instanceof TransTaskSimulator)) { + cp.removeSpareCore(targetCoreNum); + SimExecutionNode seNode = new SimExecutionNode(targetCoreNum, this.processTime); + seNode.setSpareCores(cp.getSpareCores()); + senode2action.put(seNode, action); + action2exetime.put(action, -1); + + SimExecutionNode lastsenode = lastseNodes[targetCoreNum]; + // create edges between previous senode on this core to this node + if(lastsenode != null) { + Action tmpaction = senode2action.get(lastsenode); + SimExecutionEdge seEdge = null; + if(tmpaction == null) { + seEdge = new SimExecutionEdge(seNode, + lastsenode.getCoreNum(), + null, + 0, + null); + } else { + int weight = action2exetime.get(tmpaction); + seEdge = new SimExecutionEdge(seNode, + lastsenode.getCoreNum(), + tmpaction.getTd(), + weight, + tmpaction.getTaskParams()); + } + lastsenode.addEdge(seEdge); + simexegraph.add(seEdge); + } + lastseNodes[targetCoreNum] = seNode; + } } - } else { - CoreSimulator cs = task.getCs(); - int coreNum = cs.getCoreNum(); - if(task.getCurrentRun().getExetype() == 0) { - Hashtable> transObjQueues = new Hashtable>(); - if(task.getCurrentRun().getNewObjs() == null) { - action = new Action(coreNum, Action.TASKFINISH); - action.setTd(cs.getRtask().getTd()); - } else { - action = new Action(coreNum, Action.TFWITHOBJ); - action.setTd(cs.getRtask().getTd()); - Vector nobjs = task.getCurrentRun().getNewObjs(); - for(int j = 0; j < nobjs.size(); j++) { - ObjectSimulator nobj = nobjs.elementAt(j); - action.addNewObj(nobj.getCd(), Integer.valueOf(1)); - // send the new object to target core according to pre-decide scheduling - Queue cores = cs.getTargetCores(nobj.getCurrentFS()); - if(cores == null) { + } + } + + private Vector finishTaskNormal(TaskSimulator task, + CheckPoint cp, + Vector tttasks, + Hashtable senode2action, + SimExecutionNode[] lastseNodes, + Hashtable action2exetime) { + Vector totransObjs = new Vector(); + CoreSimulator cs = task.getCs(); + int corenum = cs.getCoreNum(); + Hashtable> transObjQueues = + new Hashtable>(); + Action action = null; + if(task.getCurrentRun().getNewObjs() == null) { + // task finish without new objects + action = new Action(corenum, + Action.TASKFINISH, + cs.getRtask()); + // get the execution time of this task + SimExecutionNode lastsenode = lastseNodes[corenum]; + Action startaction = senode2action.get(lastsenode); + action2exetime.put(startaction, cp.getTimepoint() - lastsenode.getTimepoint()); + + } else { + // task finish with new objects + action = new Action(corenum, + Action.TFWITHOBJ, + cs.getRtask()); + // get the execution time of this task + SimExecutionNode lastsenode = lastseNodes[corenum]; + Action startaction = senode2action.get(lastsenode); + action2exetime.put(startaction, cp.getTimepoint() - lastsenode.getTimepoint()); + + // get the infomation of how to send new objects + Vector nobjs = task.getCurrentRun().getNewObjs(); + for(int j = 0; j < nobjs.size(); j++) { + ObjectSimulator nobj = nobjs.elementAt(j); + totransObjs.add(nobj); + + action.addNewObj(nobj.getCd(), Integer.valueOf(1)); + // send the new object to target core according to pre-decide scheduling + Queue cores = cs.getTargetCores(nobj.getCurrentFS()); + if(cores == null) { // this obj will reside on this core cs.addObject(nobj); - } else { + } else { Integer targetCore = cores.poll(); - if(targetCore == coreNum) { - // this obj will reside on this core - cs.addObject(nobj); + if(targetCore == corenum) { + // this obj will reside on this core + cs.addObject(nobj); } else { - if(!transObjQueues.containsKey(targetCore)) { - transObjQueues.put(targetCore, new LinkedList()); - } - Queue tmpqueue = transObjQueues.get(targetCore); - tmpqueue.add(new ObjectInfo(nobj)); - tmpqueue = null; + if(!transObjQueues.containsKey(targetCore)) { + transObjQueues.put(targetCore, new LinkedList()); + } + 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) { + } + cores = null; + // check if this object becoming shared or not + Vector allycores = cs.getAllyCores(nobj.getCurrentFS()); + if(allycores != null) { nobj.setShared(true); for(int k = 0; k < allycores.size(); ++k) { - Integer allyCore = allycores.elementAt(k); - if(allyCore == coreNum) { - cs.addObject(nobj); - } else { - if(!transObjQueues.containsKey(allyCore)) { - transObjQueues.put(allyCore, new LinkedList()); - } - Queue tmpqueue = transObjQueues.get(allyCore); - ObjectInfo nobjinfo = new ObjectInfo(nobj); - if(!tmpqueue.contains(nobjinfo)) { - tmpqueue.add(nobjinfo); + Integer allyCore = allycores.elementAt(k); + if(allyCore == corenum) { + cs.addObject(nobj); + } else { + if(!transObjQueues.containsKey(allyCore)) { + transObjQueues.put(allyCore, new LinkedList()); + } + Queue tmpqueue = transObjQueues.get(allyCore); + ObjectInfo nobjinfo = new ObjectInfo(nobj); + if(!tmpqueue.contains(nobjinfo)) { + tmpqueue.add(nobjinfo); + } + tmpqueue = null; } - tmpqueue = null; - } } allycores = null; - } } - nobjs = null; - } - cp.addAction(action); - Vector transObjs = cs.finishTask(); - if(transObjs != null) { - for(int j = 0; j < transObjs.size(); j++) { - ObjectSimulator tobj = transObjs.elementAt(j); - // send the object to target core according to pre-decide scheduling - Queue cores = cs.getTargetCores(tobj.getCurrentFS()); - tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS())); - if(cores == null) { + } + nobjs = null; + } + cp.addAction(action); + + // group the new objects need to transfer + Vector transObjs = cs.finishTask(); + if(transObjs != null) { + totransObjs.addAll(transObjs); + for(int j = 0; j < transObjs.size(); j++) { + ObjectSimulator tobj = transObjs.elementAt(j); + // send the object to target core according to pre-decide scheduling + Queue cores = cs.getTargetCores(tobj.getCurrentFS()); + tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS())); + if(cores == null) { // this obj will reside on this core cs.addObject(tobj); - } else { + } else { Integer targetCore = cores.poll(); - if(targetCore == coreNum) { - // this obj will reside on this core - cs.addObject(tobj); + if(targetCore == corenum) { + // this obj will reside on this core + cs.addObject(tobj); } else { - if(!transObjQueues.containsKey(targetCore)) { - transObjQueues.put(targetCore, new LinkedList()); - } - Queue tmpqueue = transObjQueues.get(targetCore); - tmpqueue.add(new ObjectInfo(tobj)); - tmpqueue = null; + if(!transObjQueues.containsKey(targetCore)) { + transObjQueues.put(targetCore, new LinkedList()); + } + Queue tmpqueue = transObjQueues.get(targetCore); + tmpqueue.add(new ObjectInfo(tobj)); + tmpqueue = null; } cores.add(targetCore); - } - cores = null; - // check if this object becoming shared or not - Vector allycores = cs.getAllyCores(tobj.getCurrentFS()); - if(allycores != null) { + } + cores = null; + // check if this object becoming shared or not + Vector allycores = cs.getAllyCores(tobj.getCurrentFS()); + if(allycores != null) { tobj.setShared(true); for(int k = 0; k < allycores.size(); ++k) { - Integer allyCore = allycores.elementAt(k); - if(allyCore == coreNum) { - cs.addObject(tobj); - } else { - if(!transObjQueues.containsKey(allyCore)) { - transObjQueues.put(allyCore, new LinkedList()); + Integer allyCore = allycores.elementAt(k); + if(allyCore == corenum) { + cs.addObject(tobj); + } else { + if(!transObjQueues.containsKey(allyCore)) { + transObjQueues.put(allyCore, new LinkedList()); + } + Queue tmpqueue = transObjQueues.get(allyCore); + ObjectInfo nobjinfo = new ObjectInfo(tobj); + if(!tmpqueue.contains(nobjinfo)) { + tmpqueue.add(nobjinfo); + } + tmpqueue = null; } - Queue tmpqueue = transObjQueues.get(allyCore); - ObjectInfo nobjinfo = new ObjectInfo(tobj); - if(!tmpqueue.contains(nobjinfo)) { - tmpqueue.add(nobjinfo); - } - tmpqueue = null; - } } allycores = null; - } } - transObjs = null; - } - // add 'transport' tasks - Iterator it_entries = transObjQueues.entrySet().iterator(); - while(it_entries.hasNext()) { - Entry> tmpentry = (Entry>)it_entries.next(); - Integer tmpCoreNum = tmpentry.getKey(); - Queue nobjs = tmpentry.getValue(); - TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs); - this.tasks.add(tmptask); - tmpentry = null; - nobjs = null; - } - 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; - } - - if(this.state.PRINTSCHEDULESIM) { - SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime, - this.coreNum, this.checkpoints); - } - System.out.println("Simulate scheduling #" + this.invoketime + ": "); - System.out.println("\tTotal execution time is: " + this.processTime); - System.out.println("\tUtility of cores: "); - for(int j = 0; j < this.cores.size(); j++) { - System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%"); - } - - this.checkpoints.clear(); - this.checkpoints = null; - return this.processTime; + transObjs = null; + + // add 'transport' tasks + Iterator it_entries = transObjQueues.entrySet().iterator(); + while(it_entries.hasNext()) { + Entry> tmpentry = (Entry>)it_entries.next(); + Integer tmpCoreNum = tmpentry.getKey(); + Queue nobjs = tmpentry.getValue(); + TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs); + this.tasks.add(tmptask); + tttasks.add(tmptask); + tmpentry = null; + nobjs = null; + } + transObjQueues = null; + + return totransObjs; } + private void generateNewTask(CoreSimulator cs, + CheckPoint cp, + Vector nobjs, + Vector tttasks, + Vector simexegraph, + Hashtable senode2action, + SimExecutionNode[] lastseNodes, + Hashtable action2exetime, + Hashtable tttask2senode, + Hashtable obj2transtime, + Hashtable obj2lastseedge) { + TaskSimulator newTask = cs.process(); + int corenum = cs.getCoreNum(); + SimExecutionEdge seEdge = null; + if(newTask != null) { + this.tasks.add(newTask); + // add a TASKSTART action into this checkpoint + Action action = new Action(corenum, + Action.TASKSTART, + newTask); + cp.addAction(action); + if(!(newTask instanceof TransTaskSimulator)) { + cp.removeSpareCore(cs.getCoreNum()); + SimExecutionNode seNode = new SimExecutionNode(corenum, this.processTime); + seNode.setSpareCores(cp.getSpareCores()); + senode2action.put(seNode, action); + action2exetime.put(action, -1); + SimExecutionNode lastsenode = lastseNodes[corenum]; + // create edges between previous senode on this core to this node + if(lastsenode != null) { + Action tmpaction = senode2action.get(lastsenode); + int weight = tmpaction != null? action2exetime.get(tmpaction):0; + seEdge = new SimExecutionEdge(seNode, + lastsenode.getCoreNum(), + tmpaction!= null?tmpaction.getTd():null, + weight, + tmpaction!=null?tmpaction.getTaskParams():null); + lastsenode.addEdge(seEdge); + } + lastseNodes[corenum] = seNode; + for(int tmpindex = 0; tmpindex < tttasks.size(); tmpindex++) { + tttask2senode.put(tttasks.elementAt(tmpindex), seNode); + } + } + } else if(tttasks.size() > 0) { + SimExecutionNode seNode = new SimExecutionNode(corenum, this.processTime); + seNode.setSpareCores(cp.getSpareCores()); + // no action associated here + SimExecutionNode lastsenode = lastseNodes[corenum]; + // create edges between previous senode on this core to this node + if(lastsenode != null) { + Action tmpaction = senode2action.get(lastsenode); + int weight = action2exetime.get(tmpaction); + seEdge = new SimExecutionEdge(seNode, + lastsenode.getCoreNum(), + tmpaction.getTd(), + weight, + tmpaction.getTaskParams()); + lastsenode.addEdge(seEdge); + } + lastseNodes[corenum] = seNode; + for(int tmpindex = 0; tmpindex < tttasks.size(); tmpindex++) { + tttask2senode.put(tttasks.elementAt(tmpindex), seNode); + } + } + if(seEdge != null) { + // setup data dependencies for the task + Vector taskparams = seEdge.getTaskparams(); + if(taskparams != null) { + for(int i = 0; i < taskparams.size(); i++) { + Integer tparam = taskparams.elementAt(i); + SimExecutionEdge lastedge = obj2lastseedge.get(tparam); + if(lastedge != null) { + if(lastedge.getCoreNum() != seEdge.getCoreNum()) { + // the obj is transferred from another core + // create an seEdge for this transfer + int weight = obj2transtime.get(tparam); + SimExecutionEdge transseEdge = new SimExecutionEdge((SimExecutionNode)seEdge.getSource(), + lastedge.getCoreNum(), + null, // TODO: not sure if this is enough + weight, + null); + if(((SimExecutionNode)seEdge.getSource()).getTimepoint() < + ((SimExecutionNode)lastedge.getTarget()).getTimepoint()) { + System.err.println("ScheduleSimulator:757"); + System.exit(-1); + } + lastedge.getTarget().addEdge(transseEdge); + simexegraph.add(transseEdge); + transseEdge.addPredicate(lastedge); + seEdge.addPredicate(transseEdge); + } else { + seEdge.addPredicate(lastedge); + } + } + // update the last edge associated to the parameter obj + obj2lastseedge.put(tparam, seEdge); + } + } + taskparams = null; + simexegraph.add(seEdge); // add the seEdge afger all corresponding transfer edges + + // set seEdge as the last execution edge for all newly created objs + if(nobjs != null) { + for(int i = 0; i < nobjs.size(); i++) { + ObjectSimulator nobj = nobjs.elementAt(i); + obj2lastseedge.put(nobj.getOid(), seEdge); + } + } + } + } + + private void finishTaskAbnormal(CoreSimulator cs, + CheckPoint cp, + Hashtable senode2action, + SimExecutionNode[] lastseNodes, + Hashtable action2exetime, + int type) { + Action action = new Action(cs.getCoreNum(), + type, + cs.getRtask()); + cp.addAction(action); + cs.finishTask(); + + // remove the corresponding action on the starting SimExecutionNode + SimExecutionNode lastsenode = lastseNodes[cs.getCoreNum()]; + /*if(lastsenode.getInedgeVector().size() > 0) { + //SimExecutionEdge inseedge = (SimExecutionEdge)lastsenode.getinedge(0); + //lastseNodes[cs.getCoreNum()] = (SimExecutionNode)inseedge.getSource(); + } /*else { + lastseNodes[cs.getCoreNum()] = null; + }*/ + Action tmpaction = senode2action.remove(lastsenode); + action2exetime.remove(tmpaction); + } + public class CheckPoint { private int timepoint; private Vector actions; + private Vector spareCores; - public CheckPoint(int timepoint) { + public CheckPoint(int timepoint, + int corenum) { super(); this.timepoint = timepoint; this.actions = new Vector(); + this.spareCores = new Vector(); + for(int i = 0; i < corenum; i++) { + this.spareCores.add(i); + } } public Vector getActions() { @@ -509,10 +829,26 @@ public class ScheduleSimulator { public void addAction(Action action) { this.actions.add(action); } + + public void removeSpareCore(int core) { + for(int i = 0 ; i < this.spareCores.size(); i++) { + if(this.spareCores.elementAt(i) == core) { + for(int j = i; j < this.spareCores.size() - 1; j++) { + this.spareCores.setElementAt(this.spareCores.elementAt(j + 1), j); + } + this.spareCores.remove(this.spareCores.size() - 1); + return; + } + } + } public int getTimepoint() { return timepoint; } + + public Vector getSpareCores() { + return spareCores; + } } public class Action { @@ -526,15 +862,17 @@ public class ScheduleSimulator { private int coreNum; private int type; private TaskDescriptor td; + private Vector taskparams; private Hashtable nObjs; private int nObjNum; private ClassDescriptor transObj; - public Action(int coreNum, int type) { - super(); - this.coreNum = coreNum; + public Action(int corenum, + int type) { + this.coreNum = corenum; this.type = type; this.td = null; + this.taskparams = null; if(this.type == TFWITHOBJ) { this.nObjs = new Hashtable(); } else { @@ -543,18 +881,48 @@ public class ScheduleSimulator { this.nObjNum = -1; this.transObj = null; } + + public Action(int corenum, + int type, + TaskSimulator ts) { + assert(this.type != ADDOBJ); + + this.coreNum = corenum; + this.type = type; + this.td = ts.getTd(); + Vector> paraQueues = ts.getParaQueues(); + this.taskparams = new Vector(); + if((this.type != TASKABORT) && (this.type != TASKREMOVE)) { + for(int i = 0; i < paraQueues.size(); i++) { + ObjectSimulator tpara = paraQueues.elementAt(i).peek(); + this.taskparams.add(tpara.getOid()); + } + paraQueues = null; + } + if(this.type == TFWITHOBJ) { + this.nObjs = new Hashtable(); + } else { + this.nObjs = null; + } + this.nObjNum = -1; + this.transObj = null; + } - public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) { - super(); + public Action(int corenum, + int type, + int objNum, + ClassDescriptor transObj) { assert(type == ADDOBJ); - this.coreNum = coreNum; + this.coreNum = corenum; this.type = type; this.td = null; + this.taskparams = null; this.nObjNum = objNum; this.transObj = transObj; } - public void addNewObj(ClassDescriptor cd, Integer num) { + public void addNewObj(ClassDescriptor cd, + Integer num) { assert(this.type == TFWITHOBJ); if(this.nObjs.containsKey(cd)) { @@ -566,7 +934,7 @@ public class ScheduleSimulator { } public int getCoreNum() { - return coreNum; + return this.coreNum; } public int getType() { @@ -584,9 +952,9 @@ public class ScheduleSimulator { public TaskDescriptor getTd() { return td; } - - public void setTd(TaskDescriptor td) { - this.td = td; + + public Vector getTaskParams() { + return this.taskparams; } public Hashtable getNObjs() { diff --git a/Robust/src/Analysis/Scheduling/SchedulingUtil.java b/Robust/src/Analysis/Scheduling/SchedulingUtil.java index 09f59c12..6ba8c893 100644 --- a/Robust/src/Analysis/Scheduling/SchedulingUtil.java +++ b/Robust/src/Analysis/Scheduling/SchedulingUtil.java @@ -20,6 +20,7 @@ import Analysis.TaskStateAnalysis.FlagState; import Analysis.TaskStateAnalysis.FEdge.NewObjInfo; import IR.ClassDescriptor; import IR.Operation; +import IR.State; import IR.Tree.FlagExpressionNode; import IR.Tree.FlagNode; import IR.Tree.FlagOpNode; @@ -28,6 +29,159 @@ import Util.GraphNode; import Util.Namer; public class SchedulingUtil { + + public static Vector generateScheduleGraph(State state, + Vector scheduleNodes, + Vector scheduleEdges, + Vector> rootnodes, + Vector> combine, + int gid) { + Vector result = new Vector(); + + // clone the ScheduleNodes + Hashtable> sn2hash = + new Hashtable>(); + Hashtable sn2sn = + new Hashtable(); + cloneScheduleGraph(scheduleNodes, + scheduleEdges, + sn2hash, + sn2sn, + result, + gid); + + // combine those nodes in combine with corresponding rootnodes + for(int i = 0; i < combine.size(); i++) { + if(combine.elementAt(i) != null) { + for(int j = 0; j < combine.elementAt(i).size(); j++) { + CombinationUtil.Combine tmpcombine = combine.elementAt(i).elementAt(j); + ScheduleNode tocombine = sn2sn.get(tmpcombine.node); + ScheduleNode root = sn2sn.get(rootnodes.elementAt(tmpcombine.root).elementAt(tmpcombine.index)); + ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next(); + try { + if(root.equals(((ScheduleNode)se.getSource()))) { + root.mergeSEdge(se); + if(ScheduleEdge.NEWEDGE == se.getType()) { + // As se has been changed into an internal edge inside a ScheduleNode, + // change the source and target of se from original ScheduleNodes into ClassNodes. + se.setTarget(se.getTargetCNode()); + //se.setSource(se.getSourceCNode()); + //se.getTargetCNode().addEdge(se); + se.getSourceCNode().addEdge(se); + } + } else { + root.mergeSNode(tocombine); + } + } catch(Exception e) { + e.printStackTrace(); + System.exit(-1); + } + result.removeElement(tocombine); + } + } + } + + assignCids(result); + + sn2hash.clear(); + sn2hash = null; + sn2sn.clear(); + sn2sn = null; + + if(state.PRINTSCHEDULING) { + String path = "scheduling_" + gid + ".dot"; + SchedulingUtil.printScheduleGraph(path, result); + } + + return result; + } + + public static void cloneScheduleGraph(Vector scheduleNodes, + Vector scheduleEdges, + Hashtable> sn2hash, + Hashtable sn2sn, + Vector result, + int gid) { + for(int i = 0; i < scheduleNodes.size(); i++) { + Hashtable cn2cn = new Hashtable(); + ScheduleNode tocopy = scheduleNodes.elementAt(i); + ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid); + result.add(i, temp); + sn2hash.put(temp, cn2cn); + sn2sn.put(tocopy, temp); + cn2cn = null; + } + // clone the ScheduleEdges + for(int i = 0; i < scheduleEdges.size(); i++) { + ScheduleEdge sse = scheduleEdges.elementAt(i); + ScheduleNode csource = sn2sn.get(sse.getSource()); + ScheduleNode ctarget = sn2sn.get(sse.getTarget()); + Hashtable sourcecn2cn = sn2hash.get(csource); + Hashtable targetcn2cn = sn2hash.get(ctarget); + ScheduleEdge se = null; + switch(sse.getType()) { + case ScheduleEdge.NEWEDGE: { + se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid); + se.setProbability(sse.getProbability()); + se.setNewRate(sse.getNewRate()); + break; + } + + case ScheduleEdge.TRANSEDGE: { + se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid); + break; + } + } + se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode())); + se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode())); + se.setFEdge(sse.getFEdge()); + se.setTargetFState(sse.getTargetFState()); + se.setIsclone(true); + csource.addEdge(se); + sourcecn2cn = null; + targetcn2cn = null; + } + } + + public static void assignCids(Vector result) { + Hashtable hcid2cid = new Hashtable(); + int ncid = 0; + for(int i = 0; i < result.size(); i++) { + ScheduleNode tmpnode = result.elementAt(i); + tmpnode.computeHashcid(); + int hcid = tmpnode.getHashcid(); + if(hcid2cid.containsKey(hcid)) { + // already have a cid for this node + tmpnode.setCid(hcid2cid.get(hcid)); + } else { + // generate a new cid for such node + tmpnode.setCid(ncid); + hcid2cid.put(hcid, ncid); + ncid++; + } + } + hcid2cid.clear(); + hcid2cid = null; + } + + // Organize the scheduleNodes in order of their cid + public static Vector> rangeScheduleNodes(Vector scheduleNodes) { + Vector> sNodeVecs = new Vector>(); + + for(int i = 0; i < scheduleNodes.size(); i++) { + ScheduleNode tmpn = scheduleNodes.elementAt(i); + int index = tmpn.getCid(); + while(sNodeVecs.size() <= index) { + sNodeVecs.add(null); + } + if(sNodeVecs.elementAt(index) == null) { + sNodeVecs.setElementAt(new Vector(), index); + } + sNodeVecs.elementAt(index).add(tmpn); + } + + return sNodeVecs; + } /*public static int maxDivisor(int l, int r) { int a = l; @@ -61,7 +215,8 @@ public class SchedulingUtil { } }*/ - public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) { + public static boolean isTaskTrigger_flag(FlagExpressionNode fen, + FlagState fs) { if (fen==null) return true; else if (fen instanceof FlagNode) @@ -82,7 +237,8 @@ public class SchedulingUtil { } } - public static void printScheduleGraph(String path, Vector sNodes) { + public static void printScheduleGraph(String path, + Vector sNodes) { try { File file=new File(path); FileOutputStream dotstream=new FileOutputStream(file,false); @@ -98,7 +254,8 @@ public class SchedulingUtil { } } - private static void traverseSNodes(PrintWriter output, Vector sNodes) { + private static void traverseSNodes(PrintWriter output, + Vector sNodes) { //Draw clusters representing ScheduleNodes Iterator it = sNodes.iterator(); while (it.hasNext()) { @@ -170,7 +327,8 @@ public class SchedulingUtil { } } - private static void traverseCNodes(PrintWriter output, Iterator it) { + private static void traverseCNodes(PrintWriter output, + Iterator it) { //Draw clusters representing ClassNodes while (it.hasNext()) { ClassNode gn = (ClassNode) it.next(); @@ -186,7 +344,8 @@ public class SchedulingUtil { } } - private static void traverseFlagStates(PrintWriter output, Collection nodes) { + private static void traverseFlagStates(PrintWriter output, + Collection nodes) { Set cycleset=GraphNode.findcycles(nodes); Vector namers=new Vector(); namers.add(new Namer()); @@ -256,7 +415,8 @@ public class SchedulingUtil { } } - private static Set nonmerge(GraphNode gn, Collection nodes) { + private static Set nonmerge(GraphNode gn, + Collection nodes) { HashSet newset=new HashSet(); HashSet toprocess=new HashSet(); toprocess.add(gn); @@ -278,7 +438,10 @@ public class SchedulingUtil { return newset; } - public static void printSimulationResult(String path, int time, int coreNum, Vector checkpoints) { + public static void printSimulationResult(String path, + int time, + int coreNum, + Vector checkpoints) { try { File file=new File(path); FileOutputStream dotstream=new FileOutputStream(file,false); @@ -325,11 +488,13 @@ public class SchedulingUtil { for(int i = 0; i < actions.size(); i++) { Action taction = actions.elementAt(i); int cNum = taction.getCoreNum(); - if(!tmplastTasks.contains(cNum)) { + if(!tmplastTasks.containsKey(cNum)) { tmplastTasks.put(cNum, lastTasks[cNum]); } - if(!(tmpisset.contains(cNum)) && (isTaskFinish[cNum]) && !(tmpisTaskFinish.contains(cNum))) { - tmpisTaskFinish.add(cNum); // records those with task finished the first time visit it + if(!(tmpisset.contains(cNum)) + && (isTaskFinish[cNum]) + && !(tmpisTaskFinish.contains(cNum))) { + tmpisTaskFinish.add(cNum); // records those with task finished the first time visit it } String tmpTaskNode = "\"" + tnode + "core" + cNum + "\""; StringBuffer tmpLabel = null; @@ -365,7 +530,15 @@ public class SchedulingUtil { if(!isfirst) { tmpLabel.append("\\n"); } - tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;"); + tmpLabel.append("<" + taction.getTd().getSymbol() + "("); + /*Vector taskparams = taction.getTaskParams(); + for(int ii = 0; ii < taskparams.size(); ii++) { + tmpLabel.append(taskparams.elementAt(ii)); + if(ii < taskparams.size() - 1) { + tmpLabel.append(","); + } + }*/ + tmpLabel.append(")>finishes;"); if(!(lastTaskNodes[cNum].equals("first"))) { if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) { output.print("\t"); @@ -389,7 +562,15 @@ public class SchedulingUtil { if(!isfirst) { tmpLabel.append("\\n"); } - tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes; "); + tmpLabel.append("<" + taction.getTd().getSymbol() + "("); + /*Vector taskparams = taction.getTaskParams(); + for(int ii = 0; ii < taskparams.size(); ii++) { + tmpLabel.append(taskparams.elementAt(ii)); + if(ii < taskparams.size() - 1) { + tmpLabel.append(","); + } + }*/ + tmpLabel.append(")>finishes;"); Iterator> it_entry = (Iterator>)taction.getNObjs().entrySet().iterator(); while(it_entry.hasNext()) { Entry entry = it_entry.next(); @@ -423,7 +604,15 @@ public class SchedulingUtil { if(!isfirst) { tmpLabel.append("\\n"); } - tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;"); + tmpLabel.append("<" + taction.getTd().getSymbol() + "("); + /*Vector taskparams = taction.getTaskParams(); + for(int ii = 0; ii < taskparams.size(); ii++) { + tmpLabel.append(taskparams.elementAt(ii)); + if(ii < taskparams.size() - 1) { + tmpLabel.append(","); + } + }*/ + tmpLabel.append(")>starts;"); lastTasks[cNum] = taction.getTd().getSymbol(); if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) { @@ -447,7 +636,15 @@ public class SchedulingUtil { if(!isfirst) { tmpLabel.append("\\n"); } - tmpLabel.append("<" + taction.getTd().getSymbol() + ">aborts;"); + tmpLabel.append("<" + taction.getTd().getSymbol() + "("); + /*Vector taskparams = taction.getTaskParams(); + for(int ii = 0; ii < taskparams.size(); ii++) { + tmpLabel.append(taskparams.elementAt(ii)); + if(ii < taskparams.size() - 1) { + tmpLabel.append(","); + } + }*/ + tmpLabel.append(")>aborts;"); if(!(lastTaskNodes[cNum].equals("first")) && (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) { if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) { @@ -472,7 +669,15 @@ public class SchedulingUtil { if(!isfirst) { tmpLabel.append("\\n"); } - tmpLabel.append("<" + taction.getTd().getSymbol() + ">removes;"); + tmpLabel.append("<" + taction.getTd().getSymbol() + "("); + /*Vector taskparams = taction.getTaskParams(); + for(int ii = 0; ii < taskparams.size(); ii++) { + tmpLabel.append(taskparams.elementAt(ii)); + if(ii < taskparams.size() - 1) { + tmpLabel.append(","); + } + }*/ + tmpLabel.append(")>removes;"); if(!(lastTaskNodes[cNum].equals("first")) && (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) { if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) { @@ -572,4 +777,48 @@ public class SchedulingUtil { System.exit(-1); } } + + public static void printCriticalPath(String path, + Vector criticalPath) { + try { + File file=new File(path); + FileOutputStream dotstream=new FileOutputStream(file,false); + PrintWriter output = new java.io.PrintWriter(dotstream, true); + output.println("digraph simulation{"); + output.print("\t"); + output.println("node [shape=plaintext];"); + output.print("\t"); + output.println("edge [dir=none];"); + output.print("\t"); + output.println("ranksep=.05;"); + output.println(); + output.print("\t"); + Vector nodes = new Vector(); + String label = ""; + String dotnodeparams=""; + + for(int i = 0; i < criticalPath.size(); i++) { + SimExecutionEdge seedge = criticalPath.elementAt(i); + SimExecutionNode startnode = (SimExecutionNode)seedge.getSource(); + SimExecutionNode endnode = (SimExecutionNode)seedge.getTarget(); + if(!nodes.contains(startnode)) { + label = startnode.getCoreNum() + ":" + startnode.getTimepoint(); + output.println("\t" + startnode.getLabel() + " [label=\"" + + label + "\" ];"); + } + if(!nodes.contains(endnode)) { + label = endnode.getCoreNum() + ":" + endnode.getTimepoint(); + output.println("\t" + endnode.getLabel() + " [label=\"" + + label + "\" ];"); + } + output.println("\t" + startnode.getLabel() + " -> " + endnode.getLabel() + + " [" + "label=\"" + seedge.getLabel() + "\"];"); + } + output.println("}"); + output.close(); + } catch (Exception e) { + e.printStackTrace(); + System.exit(-1); + } + } } \ No newline at end of file diff --git a/Robust/src/Analysis/Scheduling/SimExecutionEdge.java b/Robust/src/Analysis/Scheduling/SimExecutionEdge.java new file mode 100644 index 00000000..533a5b05 --- /dev/null +++ b/Robust/src/Analysis/Scheduling/SimExecutionEdge.java @@ -0,0 +1,134 @@ +package Analysis.Scheduling; + +import java.util.Vector; + +import IR.TaskDescriptor; +import Util.Edge; + +public class SimExecutionEdge extends Edge { + + private int eid; + private static int nodeID=0; + + private int coreNum; + private TaskDescriptor td; + private Vector taskparams; + private int weight; + + private int bestStartPoint; + private SimExecutionNode lastpredicatenode; + private SimExecutionEdge lastpredicateedge; + private Vector predicates; + private boolean isFixedTime; + + public SimExecutionEdge(SimExecutionNode target, + int corenum, + TaskDescriptor td, + int weight, + Vector taskparams) { + super(target); + this.eid = SimExecutionEdge.nodeID++; + this.coreNum = corenum; + this.td = td; + this.taskparams = taskparams; + this.weight = weight; + this.bestStartPoint = -1; + this.lastpredicatenode = null; + this.lastpredicateedge = null; + this.predicates = new Vector(); + this.isFixedTime = true; + } + + public int getBestStartPoint() { + if(this.bestStartPoint == -1) { + if(this.predicates.size() > 0) { + // have predicates + int starttime = 0; + // check the latest finish time of all the predicates + for(int j = 0; j < this.predicates.size(); j++) { + SimExecutionEdge predicate = this.predicates.elementAt(j); + int tmptime = predicate.getBestStartPoint() + predicate.getWeight(); + if(tmptime > starttime) { + starttime = tmptime; + this.lastpredicateedge = predicate; + if(predicate.getTd() != null) { + this.lastpredicatenode = (SimExecutionNode)predicate.getTarget(); + } else { + // transfer edge + this.lastpredicatenode = (SimExecutionNode)predicate.getSource(); + } + } + } + this.bestStartPoint = starttime; + } else { + // no predicates + this.bestStartPoint = 0; + } + } + return bestStartPoint; + } + + public void setBestStartPoint(int bestStartPoint) { + this.bestStartPoint = bestStartPoint; + } + + public Vector getPredicates() { + return predicates; + } + + public void addPredicate(SimExecutionEdge predicate) { + if(!this.predicates.contains(predicate)) { + this.predicates.add(predicate); + } + } + + public Vector getTaskparams() { + return taskparams; + } + + public TaskDescriptor getTd() { + return td; + } + + public int getWeight() { + return weight; + } + + public void setWeight(int weight) { + this.weight = weight; + } + + public int getCoreNum() { + return coreNum; + } + + public SimExecutionNode getLastpredicateNode() { + return lastpredicatenode; + } + + public void setLastpredicateNode(SimExecutionNode lastpredicatenode) { + this.lastpredicatenode = lastpredicatenode; + } + + public SimExecutionEdge getLastpredicateEdge() { + return lastpredicateedge; + } + + public void setLastpredicateEdge(SimExecutionEdge lastpredicateedge) { + this.lastpredicateedge = lastpredicateedge; + } + + public boolean isFixedTime() { + return isFixedTime; + } + + public void setFixedTime(boolean isFixedTime) { + this.isFixedTime = isFixedTime; + } + + public String getLabel() { + String completeLabel = (this.td != null? this.td.getSymbol():"") + + "(" + this.weight + " | " + this.bestStartPoint + ")"; + return completeLabel; + } +} diff --git a/Robust/src/Analysis/Scheduling/SimExecutionNode.java b/Robust/src/Analysis/Scheduling/SimExecutionNode.java new file mode 100644 index 00000000..23f88861 --- /dev/null +++ b/Robust/src/Analysis/Scheduling/SimExecutionNode.java @@ -0,0 +1,47 @@ +package Analysis.Scheduling; + +import java.util.Vector; + +import Util.GraphNode; + +public class SimExecutionNode extends GraphNode { + + private int nid; + private static int nodeID=0; + + private int coreNum; + private int timepoint; + public Vector spareCores; + + public SimExecutionNode(int corenum, + int timepoint) { + this.nid = SimExecutionNode.nodeID++; + this.coreNum = corenum; + this.timepoint = timepoint; + this.spareCores = null; + } + + public int getNid() { + return nid; + } + + public int getTimepoint() { + return timepoint; + } + + public int getCoreNum() { + return coreNum; + } + + public Vector getSpareCores() { + return spareCores; + } + + public void setSpareCores(Vector spareCores) { + this.spareCores = spareCores; + } + + public String getLabel() { + return "N" + this.nid; + } +} diff --git a/Robust/src/Analysis/Scheduling/TaskSimulator.java b/Robust/src/Analysis/Scheduling/TaskSimulator.java index f8dfc927..b52ac2d0 100644 --- a/Robust/src/Analysis/Scheduling/TaskSimulator.java +++ b/Robust/src/Analysis/Scheduling/TaskSimulator.java @@ -70,7 +70,8 @@ public class TaskSimulator { } } - public TaskSimulator(TaskDescriptor td, CoreSimulator cs) { + public TaskSimulator(TaskDescriptor td, + CoreSimulator cs) { super(); this.td = td; this.paraQueues = null; @@ -104,7 +105,10 @@ public class TaskSimulator { return this.objVersionTbl.get(os).intValue(); } - public void enquePara(ObjectSimulator obj, FlagState fs, int version, boolean inherent) { + public void enquePara(ObjectSimulator obj, + FlagState fs, + int version, + boolean inherent) { ClassDescriptor cd = obj.getCd(); int paraNum = td.numParameters(); for(int i = 0; i < paraNum; i++) { @@ -142,7 +146,8 @@ public class TaskSimulator { } } - public void refreshPara(ObjectSimulator obj, boolean remove) { + public void refreshPara(ObjectSimulator obj, + boolean remove) { ClassDescriptor cd = obj.getCd(); int paraNum = td.numParameters(); for(int i = 0; i < paraNum; i++) { @@ -274,7 +279,8 @@ public class TaskSimulator { FlagState tfstate = tpara.getCurrentFS(); FEdge toexecute = tfstate.process(td); finishTime += toexecute.getExeTime(); - if((toexecute.getNewObjInfoHashtable() != null) && (toexecute.getNewObjInfoHashtable().size() > 0)) { + if((toexecute.getNewObjInfoHashtable() != null) + && (toexecute.getNewObjInfoHashtable().size() > 0)) { // have new objects Iterator it = toexecute.getNewObjInfoHashtable().keySet().iterator(); int invokeNum = toexecute.getInvokeNum(); diff --git a/Robust/src/Analysis/Scheduling/TransTaskSimulator.java b/Robust/src/Analysis/Scheduling/TransTaskSimulator.java index 66f75a2e..8e4dbaf4 100644 --- a/Robust/src/Analysis/Scheduling/TransTaskSimulator.java +++ b/Robust/src/Analysis/Scheduling/TransTaskSimulator.java @@ -6,7 +6,9 @@ public class TransTaskSimulator extends TaskSimulator { private int targetCoreNum; private Queue newObjs; - public TransTaskSimulator(CoreSimulator cs, int targetCoreNum, Queue nobjs) { + public TransTaskSimulator(CoreSimulator cs, + int targetCoreNum, + Queue nobjs) { super(null, cs); this.targetCoreNum = targetCoreNum; this.newObjs = nobjs; @@ -35,4 +37,9 @@ public class TransTaskSimulator extends TaskSimulator { public int getTargetCoreNum() { return targetCoreNum; } + + public Queue getNewObjs() { + return newObjs; + } + } \ No newline at end of file -- 2.34.1