X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FScheduling%2FScheduleAnalysis.java;h=a44cbab6c2229e017c1cddc9b06626cd9bc10ffe;hb=90387876e887ae7dc034e2ddfb6a3df0fb7dc281;hp=b31b59871d9300fb3ebdc7ef1a55e611816c3c15;hpb=889090703643a3ad93015a6b42d65bdaa847672f;p=IRC.git diff --git a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java index b31b5987..a44cbab6 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java +++ b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java @@ -1,29 +1,27 @@ package Analysis.Scheduling; import Analysis.TaskStateAnalysis.*; -import Analysis.TaskStateAnalysis.FEdge.NewObjInfo; import IR.*; import java.util.*; -import java.io.*; - -import Util.Edge; -import Util.GraphNode; -import Util.Namer; /** This class holds flag transition diagram(s) can be put on one core. */ public class ScheduleAnalysis { - TaskAnalysis taskanalysis; State state; + TaskAnalysis taskanalysis; Vector scheduleNodes; Vector classNodes; + Vector scheduleEdges; Hashtable cd2ClassNode; boolean sorted = false; - Vector scheduleEdges; int transThreshold; + + int coreNum; + Vector> scheduleGraphs; + Vector> schedulings; public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) { this.state = state; @@ -32,14 +30,37 @@ public class ScheduleAnalysis { this.classNodes = new Vector(); this.scheduleEdges = new Vector(); this.cd2ClassNode = new Hashtable(); - this.transThreshold = 45; + this.coreNum = -1; + this.scheduleGraphs = null; + this.schedulings = null; } public void setTransThreshold(int tt) { this.transThreshold = tt; } + public int getCoreNum() { + return coreNum; + } + + public void setCoreNum(int coreNum) { + this.coreNum = coreNum; + } + + public Iterator getScheduleGraphs() { + return this.scheduleGraphs.iterator(); + } + + public Iterator getSchedulingsIter() { + return this.schedulings.iterator(); + } + + public Vector> getSchedulings() { + return this.schedulings; + } + + // for test public Vector getSEdges4Test() { return scheduleEdges; } @@ -68,13 +89,15 @@ public class ScheduleAnalysis { if(cd.getSymbol().equals("C")) { cNode.setTransTime(45); } - } + } + fStates = null; + sFStates = null; } // For each ClassNode create a ScheduleNode containing it int i = 0; for(i = 0; i < classNodes.size(); i++) { - ScheduleNode sn = new ScheduleNode(classNodes.elementAt(i)); + ScheduleNode sn = new ScheduleNode(classNodes.elementAt(i), 0); classNodes.elementAt(i).setScheduleNode(sn); scheduleNodes.add(sn); try { @@ -107,11 +130,15 @@ public class ScheduleAnalysis { // fake creating edge, do not need to create corresponding 'new' edge continue; } + if(noi.getRoot() == null) { + // set root FlagState + noi.setRoot(root); + } FlagState pfs = (FlagState)pfe.getTarget(); ClassDescriptor pcd = pfs.getClassDescriptor(); ClassNode pcNode = cdToCNodes.get(pcd); - ScheduleEdge sEdge = new ScheduleEdge(sNode, "new",/* td,*/ cd); + ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, 0);//new ScheduleEdge(sNode, "new", cd, 0); sEdge.setFEdge(pfe); sEdge.setSourceCNode(pcNode); sEdge.setTargetCNode(cNode); @@ -132,6 +159,7 @@ public class ScheduleAnalysis { rootnodes = null; } } + cdToCNodes = null; // Do topology sort of the ClassNodes and ScheduleEdges. Vector ssev = new Vector(); @@ -148,6 +176,7 @@ public class ScheduleAnalysis { for(i = 0; i < toBreakDown.size(); i++ ) { cloneSNodeList(toBreakDown.elementAt(i), false); } + toBreakDown = null; // Remove fake 'new' edges for(i = 0; i < scheduleEdges.size(); i++) { @@ -157,22 +186,10 @@ public class ScheduleAnalysis { scheduleNodes.removeElement(se.getTarget()); } } + + SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes); } - /*private void removeSNodeList(ScheduleEdge se) { - ScheduleNode sNode = (ScheduleNode)se.getTarget(); - scheduleNodes.removeElement(sNode); - Vector cNodes = sNode.getClassNodes(); - for(int i = 0; i < cNodes.size(); i++) { - classNodes.removeElement(cNodes.elementAt(i)); - cd2ClassNode.remove(cNodes.elementAt(i).getClassDescriptor()); - } - Vector edges = sNode.getEdgeVector(); - for(int j = 0; j < edges.size(); j++) { - removeSNodeList(edges.elementAt(j)); - } - }*/ - public void scheduleAnalysis() { // First iteration int i = 0; @@ -327,6 +344,10 @@ public class ScheduleAnalysis { fe2ses.clear(); sn2fes.clear(); } + fe2ses = null; + sn2fes = null; + + SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes); } private void handleScheduleEdge(ScheduleEdge se, boolean merge) { @@ -362,7 +383,7 @@ public class ScheduleAnalysis { // merge the original ScheduleNode to the source ScheduleNode ((ScheduleNode)se.getSource()).mergeSEdge(se); scheduleNodes.remove(se.getTarget()); - scheduleEdges.removeElement(se); + 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. se.setTarget(se.getTargetCNode()); @@ -379,8 +400,8 @@ public class ScheduleAnalysis { private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) { Hashtable cn2cn = new Hashtable(); - ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn); - scheduleNodes.add(csNode); + ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0); + scheduleNodes.add(csNode); // Clone all the external in ScheduleEdges int i; @@ -388,24 +409,30 @@ public class ScheduleAnalysis { Vector inedges = sEdge.getTarget().getInedgeVector(); for(i = 0; i < inedges.size(); i++) { ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i); - ScheduleEdge se = new ScheduleEdge(csNode, "new", tse.getClassDescriptor(), tse.getIsNew()); + ScheduleEdge se; if(tse.getIsNew()) { - //se.setProbability(tse.getProbability()); + se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getIsNew(), 0); //new ScheduleEdge(csNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0); se.setProbability(100); se.setNewRate(1); - se.setFEdge(tse.getFEdge()); + } else { + se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), false, 0);//new ScheduleEdge(csNode, "transmit", tse.getClassDescriptor(), false, 0); } se.setSourceCNode(tse.getSourceCNode()); se.setTargetCNode(cn2cn.get(tse.getTargetCNode())); + se.setFEdge(tse.getFEdge()); + se.setTargetFState(tse.getTargetFState()); + se.setIsclone(true); tse.getSource().addEdge(se); scheduleEdges.add(se); } + inedges = null; } else { sEdge.getTarget().removeInedge(sEdge); sEdge.setTarget(csNode); csNode.getInedgeVector().add(sEdge); sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode())); - sEdge.setTargetFState(null); + //sEdge.setTargetFState(null); + sEdge.setIsclone(true); } Queue toClone = new LinkedList(); @@ -423,25 +450,34 @@ public class ScheduleAnalysis { Vector edges = osNode.getEdgeVector(); for(i = 0; i < edges.size(); i++) { ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i); - ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn); + ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0); scheduleNodes.add(tSNode); clone.add(tSNode); toClone.add((ScheduleNode)tse.getTarget()); qcn2cn.add(tocn2cn); ScheduleEdge se = null; if(tse.getIsNew()) { - se = new ScheduleEdge(tSNode, "new", tse.getClassDescriptor(), tse.getIsNew()); + se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getIsNew(), 0);//new ScheduleEdge(tSNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0); se.setProbability(tse.getProbability()); se.setNewRate(tse.getNewRate()); } else { - se = new ScheduleEdge(tSNode, "transmit", tse.getClassDescriptor(), false); + se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), false, 0);//new ScheduleEdge(tSNode, "transmit", tse.getClassDescriptor(), false, 0); } se.setSourceCNode(cn2cn.get(tse.getSourceCNode())); se.setTargetCNode(tocn2cn.get(tse.getTargetCNode())); + se.setFEdge(tse.getFEdge()); + se.setTargetFState(tse.getTargetFState()); + se.setIsclone(true); csNode.addEdge(se); scheduleEdges.add(se); } + tocn2cn = null; + edges = null; } + toClone = null; + clone = null; + qcn2cn = null; + cn2cn = null; } private int calInExeTime(FlagState fs) throws Exception { @@ -461,6 +497,7 @@ public class ScheduleAnalysis { }else { break; } + inedges = null; } exeTime = cNode.getScheduleNode().getExeTime() - exeTime; return exeTime; @@ -492,10 +529,12 @@ public class ScheduleAnalysis { } } } + sfss = null; Vector sFStates = FlagState.DFS.topology(fStates, null); + fStates = null; // create a ClassNode and ScheduleNode for this subtree ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates); - ScheduleNode sNode = new ScheduleNode(cNode); + ScheduleNode sNode = new ScheduleNode(cNode, 0); cNode.setScheduleNode(sNode); cNode.setSorted(true); cNode.setTransTime(sCNode.getTransTime()); @@ -523,11 +562,10 @@ public class ScheduleAnalysis { } } } - + toiterate = null; // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode - ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false); - sEdge.setTargetFState(fs); + ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, false, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0); sEdge.setFEdge(fe); sEdge.setSourceCNode(sCNode); sEdge.setTargetCNode(cNode); @@ -537,9 +575,37 @@ 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 + ScheduleNode oldSNode = (ScheduleNode)se.getSource(); + Iterator it_isEdges = oldSNode.getScheduleEdgesIterator(); + Vector toremove = new Vector(); + Vector rCNodes = new Vector(); + rCNodes.addElement(sCNode); + if(it_isEdges != null){ + 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()))) { + tse.setSource(cNode); + tse.setSourceCNode(cNode); + } else { + continue; + } + } + sNode.getScheduleEdges().addElement(tse); + sNode.getClassNodes().addElement(tse.getTargetCNode()); + rCNodes.addElement(tse.getTargetCNode()); + oldSNode.getClassNodes().removeElement(tse.getTargetCNode()); + toremove.addElement(tse); + } + } + } + oldSNode.getScheduleEdges().removeAll(toremove); + toremove.clear(); // redirect ScheudleEdges out of this subtree to the new ScheduleNode Iterator it_sEdges = se.getSource().edges(); - Vector toremove = new Vector(); + //Vector toremove = new Vector(); while(it_sEdges.hasNext()) { ScheduleEdge tse = (ScheduleEdge)it_sEdges.next(); if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) { @@ -552,6 +618,8 @@ public class ScheduleAnalysis { } } se.getSource().getEdgeVector().removeAll(toremove); + toremove = null; + sFStates = null; if(!copy) { //merge se into its source ScheduleNode @@ -569,197 +637,298 @@ public class ScheduleAnalysis { return sNode; } - public void schedule() { - // Assign a core to each ScheduleNode - int i = 0; - int coreNum = 1; - for(i = 0; i < scheduleNodes.size(); i++) { - ScheduleNode sn = scheduleNodes.elementAt(i); - sn.setCoreNum(coreNum++); - sn.listTasks(); - // 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(); - sn.addTargetSNode(se.getTargetFState().getClassDescriptor(), target); + public void schedule() throws Exception { + if(this.coreNum == -1) { + throw new Exception("Error: un-initialized coreNum when doing scheduling."); + } + + if(this.scheduleGraphs == null) { + this.scheduleGraphs = new Vector>(); + } + + int reduceNum = this.scheduleNodes.size() - this.coreNum; + + // Enough cores, no need to merge more ScheduleEdge + if(!(reduceNum > 0)) { + this.scheduleGraphs.addElement(this.scheduleNodes); + } else { + // sort the ScheduleEdges in dececending order of transmittime + Vector sEdges = new Vector(); + sEdges.addElement(this.scheduleEdges.elementAt(0)); + for(int i = 1; i < this.scheduleEdges.size(); i++) { + ScheduleEdge temp = this.scheduleEdges.elementAt(i); + int j = sEdges.size() - 1; + do { + if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) { + break; + } + } while(j >= 0); + sEdges.add(j+1, temp); } - } - } - - public void printScheduleGraph(String path) { - try { - File file=new File(path); - FileOutputStream dotstream=new FileOutputStream(file,false); - PrintWriter output = new java.io.PrintWriter(dotstream, true); - output.println("digraph G {"); - output.println("\tcompound=true;\n"); - traverseSNodes(output); - output.println("}\n"); - } catch (Exception e) { - e.printStackTrace(); - System.exit(-1); - } - } - - private void traverseSNodes(PrintWriter output){ - //Draw clusters representing ScheduleNodes - Iterator it = scheduleNodes.iterator(); - while (it.hasNext()) { - ScheduleNode gn = (ScheduleNode) it.next(); - Iterator edges = gn.edges(); - output.println("\tsubgraph " + gn.getLabel() + "{"); - output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";"); - Iterator it_cnodes = gn.getClassNodesIterator(); - traverseCNodes(output, it_cnodes); - //Draw the internal 'new' edges - Iterator it_edges =gn.getScheduleEdgesIterator(); - while(it_edges.hasNext()) { - ScheduleEdge se = (ScheduleEdge)it_edges.next(); - output.print("\t"); - if(se.getSourceFState() == null) { - output.print(se.getSourceCNode().getLabel()); - } else { - output.print(se.getSourceFState().getLabel()); - } - output.print(" -> "); - if(se.getTargetFState() == null) { - output.println(se.getTargetCNode().getLabel() + " [label=\"" + se.getLabel() + "\", color=red];"); - } else { - output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail="); - if(se.getSourceFState() == null) { - output.println(se.getSourceCNode().getLabel() + "];"); + + int temp = sEdges.elementAt(reduceNum - 1).getTransTime(); + for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) { + if(sEdges.elementAt(i).getTransTime() != temp) { + sEdges.removeElementAt(i); + } else { + break; + } + } + int start = reduceNum - 2; + for(; start >= 0; start--) { + if(sEdges.elementAt(start).getTransTime() != temp) { + start++; + reduceNum -= start; + break; + } + } + if(start < 0) { + start = 0; + } + + // generate scheduling + Vector candidates = new Vector(); + for(int i = start; i < sEdges.size(); i++) { + candidates.addElement(Integer.valueOf(i)); + } + Combination combGen = new Combination(candidates, reduceNum); + int gid = 1; + do { + Vector toreduce = combGen.next(); + if(toreduce != null) { + Vector reduceEdges = new Vector(); + for(int i = 0; i < start; i++) { + reduceEdges.add(sEdges.elementAt(i)); + } + for(int i = 0; i < toreduce.size(); i++) { + reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue())); + } + Vector sNodes = generateScheduling(reduceEdges, gid++); + this.scheduleGraphs.add(sNodes); + reduceEdges = null; + sNodes = null; + } else { + break; + } + toreduce = null; + }while(true); + sEdges = null; + candidates = null; + + } + + if(this.schedulings == null) { + this.schedulings = new Vector>(); + } + + for(int i = 0; i < this.scheduleGraphs.size(); i++) { + 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); + } + 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); + } + } + } + + // 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(); + if(se.getIsNew()) { + for(int k = 0; k < se.getNewRate(); k++) { + tmpSchedule.addTargetCore(se.getFstate(), sn2coreNum.get(target)); + } + } else { + // 'transmit' edge + tmpSchedule.addTargetCore(se.getFstate(), sn2coreNum.get(target), se.getTargetFState()); + } + } + it_edges = sn.getScheduleEdgesIterator(); + while(it_edges.hasNext()) { + ScheduleEdge se = (ScheduleEdge)it_edges.next(); + if(se.getIsNew()) { + for(int k = 0; k < se.getNewRate(); k++) { + tmpSchedule.addTargetCore(se.getFstate(), j); + } } else { - output.println(se.getSourceCNode().getClusterLabel() + "];"); + // 'transmit' edge + tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState()); } - } - } - output.println("\t}\n"); - //Draw 'new' edges of this ScheduleNode - while(edges.hasNext()) { - ScheduleEdge se = (ScheduleEdge)edges.next(); - output.print("\t"); - if(se.getSourceFState() == null) { - output.print(se.getSourceCNode().getLabel()); - } else { - output.print(se.getSourceFState().getLabel()); - } - output.print(" -> "); - if(se.getTargetFState() == null) { - output.println(se.getTargetCNode().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed]"); - } else { - output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed]"); - } - } - } + } + scheduling.add(tmpSchedule); + } + this.schedulings.add(scheduling); + } + } - private void traverseCNodes(PrintWriter output, Iterator it){ - //Draw clusters representing ClassNodes - while (it.hasNext()) { - ClassNode gn = (ClassNode) it.next(); - if(gn.isclone()) { - output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];"); + public Vector generateScheduling(Vector reduceEdges, 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 and merge those in reduceEdges at the same time + Vector toMerge = new Vector(); + 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; + if(sse.getIsNew()) { + se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getIsNew(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid); + se.setProbability(sse.getProbability()); + se.setNewRate(sse.getNewRate()); } else { - output.println("\tsubgraph " + gn.getClusterLabel() + "{"); - output.println("\t\tstyle=dashed;"); - output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";"); - traverseFlagStates(output, gn.getFlagStates()); - output.println("\t}\n"); + se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), false, gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid); } - } + 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); + if(reduceEdges.contains(sse)) { + toMerge.add(se); + } + sourcecn2cn = null; + targetcn2cn = null; + } + sn2hash = null; + sn2sn = null; + + for(int i = 0; i < toMerge.size(); i++) { + ScheduleEdge sEdge = toMerge.elementAt(i); + // merge this edge + if(sEdge.getIsNew()) { + ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge); + } else { + try { + ((ScheduleNode)sEdge.getSource()).mergeTransEdge(sEdge); + } catch(Exception e) { + e.printStackTrace(); + System.exit(-1); + } + } + result.removeElement(sEdge.getTarget()); + if(sEdge.getIsNew()) { + // As se has been changed into an internal edge inside a ScheduleNode, + // change the source and target of se from original ScheduleNodes into ClassNodes. + sEdge.setTarget(sEdge.getTargetCNode()); + sEdge.setSource(sEdge.getSourceCNode()); + } + } + toMerge = null; + + String path = "scheduling_" + gid + ".dot"; + SchedulingUtil.printScheduleGraph(path, result); + + return result; } - private void traverseFlagStates(PrintWriter output, Collection nodes) { - Set cycleset=GraphNode.findcycles(nodes); - Vector namers=new Vector(); - namers.add(new Namer()); - namers.add(new Allocations()); - //namers.add(new TaskEdges()); - - Iterator it = nodes.iterator(); - while (it.hasNext()) { - GraphNode gn = (GraphNode) it.next(); - Iterator edges = gn.edges(); - String label = ""; - String dotnodeparams=""; - - for(int i=0;i candidates' number in combination."); + } + if(factors.size() == selectNum) { + this.resultNum = 1; + head = null; + tail = null; + return; + } + this.head = this.factors.remove(0); + if(selectNum == 1) { + this.resultNum = this.factors.size() + 1; + this.tail = null; + return; + } + this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1); + this.selectNum = selectNum; + this.resultNum = 1; + for(int i = factors.size(); i > selectNum; i--) { + this.resultNum *= i; + } + for(int i = factors.size() - selectNum; i > 0; i--) { + this.resultNum /= i; + } + } + + public Vector next() { + if(resultNum == 0) { + return null; + } + if(head == null) { + resultNum--; + Vector result = this.factors; + return result; + } + if(this.tail == null) { + resultNum--; + Vector result = new Vector(); + result.add(this.head); + if(resultNum != 0) { + this.head = this.factors.remove(0); } - if (!newparams.equals("")) { - dotnodeparams+=", " + name.nodeOption(gn); + return result; + } + Vector result = this.tail.next(); + if(result == null) { + if(this.factors.size() == this.selectNum) { + this.head = null; + this.tail = null; + result = this.factors; + this.resultNum--; + return result; } - label+=name.nodeLabel(gn); - } - label += ":[" + ((FlagState)gn).getExeTime() + "]"; - - if (!gn.merge) - output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];"); - - if (!gn.merge) - while (edges.hasNext()) { - Edge edge = (Edge) edges.next(); - GraphNode node = edge.getTarget(); - if (nodes.contains(node)) { - for(Iterator nodeit=nonmerge(node, nodes).iterator();nodeit.hasNext();) { - GraphNode node2=(GraphNode)nodeit.next(); - String edgelabel = ""; - String edgedotnodeparams=""; - - for(int i=0;i hashtable = ((FEdge)edge).getNewObjInfoHashtable(); - if(hashtable != null) { - Set keys = hashtable.keySet(); - Iterator it_keys = keys.iterator(); - while(it_keys.hasNext()) { - ClassDescriptor cd = (ClassDescriptor)it_keys.next(); - NewObjInfo noi = hashtable.get(cd); - edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }"; - } - } - output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];"); - } - } - } - } - } - - private Set nonmerge(GraphNode gn, Collection nodes) { - HashSet newset=new HashSet(); - HashSet toprocess=new HashSet(); - toprocess.add(gn); - while(!toprocess.isEmpty()) { - GraphNode gn2=(GraphNode)toprocess.iterator().next(); - toprocess.remove(gn2); - if (!gn2.merge) - newset.add(gn2); - else { - Iterator edges = gn2.edges(); - while (edges.hasNext()) { - Edge edge = (Edge) edges.next(); - GraphNode node = edge.getTarget(); - if (!newset.contains(node)&&nodes.contains(node)) - toprocess.add(node); + this.head = this.factors.remove(0); + try { + this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1); + result = this.tail.next(); + } catch(Exception e) { + e.printStackTrace(); } + } + result.add(0, head); + resultNum--; + return result; } - return newset; } - }