From d15cd07ecbb33f3c45006fe430eb7c8dc2f9bc02 Mon Sep 17 00:00:00 2001 From: jzhou Date: Tue, 5 Aug 2008 01:03:17 +0000 Subject: [PATCH] fix a bug in combination stage of scheduling analysis --- .../Analysis/Scheduling/CombinationUtil.java | 456 ++++++++++++++++++ .../Analysis/Scheduling/ScheduleAnalysis.java | 257 ++++------ .../src/Analysis/Scheduling/ScheduleNode.java | 64 ++- .../src/Benchmarks/PERT/Mcore/Estimator.java | 107 ---- Robust/src/Benchmarks/PERT/Mcore/PERT.java | 56 --- Robust/src/Benchmarks/PERT/Mcore/Stage.java | 108 ----- Robust/src/Main/Main.java | 6 +- 7 files changed, 604 insertions(+), 450 deletions(-) create mode 100644 Robust/src/Analysis/Scheduling/CombinationUtil.java delete mode 100644 Robust/src/Benchmarks/PERT/Mcore/Estimator.java delete mode 100644 Robust/src/Benchmarks/PERT/Mcore/PERT.java delete mode 100644 Robust/src/Benchmarks/PERT/Mcore/Stage.java diff --git a/Robust/src/Analysis/Scheduling/CombinationUtil.java b/Robust/src/Analysis/Scheduling/CombinationUtil.java new file mode 100644 index 00000000..5ea3d89b --- /dev/null +++ b/Robust/src/Analysis/Scheduling/CombinationUtil.java @@ -0,0 +1,456 @@ +package Analysis.Scheduling; + +import java.util.Vector; + +public class CombinationUtil { + static CombinationUtil cu; + + public CombinationUtil() { + } + + public static CombinationUtil allocateCombinationUtil() { + if(cu == null) { + cu = new CombinationUtil(); + } + return cu; + } + + public static RootsGenerator allocateRootsGenerator(Vector> snodevecs, int rootNum) { + return CombinationUtil.allocateCombinationUtil().new RootsGenerator(snodevecs, rootNum); + } + + public static CombineGenerator allocateCombineGenerator(Vector> rootnodes, Vector> node2combine) { + return CombinationUtil.allocateCombinationUtil().new CombineGenerator(rootnodes, node2combine); + } + + public class RootsGenerator { + Vector> sNodeVecs; + Vector> node2Combine; + Vector> rootNodes; + int rootNum; + + public RootsGenerator(Vector> snodevecs, int rootNum) { + this.sNodeVecs = snodevecs; + this.rootNum = rootNum; + this.node2Combine = null; + this.rootNodes = null; + } + + public boolean nextGen() { + boolean trial = false; + if(this.rootNodes == null) { + int num2choose = this.rootNum; + this.rootNodes = new Vector>(); + this.rootNodes.add(new Vector()); + Vector toadd = this.sNodeVecs.elementAt(0); + for(int i = 0; i < toadd.size(); i++) { + // should be only one element: startup object + this.rootNodes.elementAt(0).add(toadd.elementAt(i)); + num2choose--; + } + int next = 1; + trial = trial(num2choose, next); + } else { + int next = this.rootNodes.lastElement().elementAt(0).getCid() + 1; + int num2choose = 0; + if(next == this.sNodeVecs.size()) { + // backtrack + num2choose = this.rootNodes.lastElement().size(); + this.rootNodes.removeElementAt(this.rootNodes.size() - 1); + if(this.rootNodes.size() == 1) { + // only startup object left, no more choices + return false; + } + next = this.rootNodes.lastElement().elementAt(0).getCid() + 1; + + } + num2choose++; + // reduce one from the last one + this.rootNodes.lastElement().removeElementAt(this.rootNodes.lastElement().size() - 1); + if(this.rootNodes.lastElement().size() == 0) { + this.rootNodes.removeElementAt(this.rootNodes.size() - 1); + } + + trial = trial(num2choose, next); + } + if(trial) { + // left nodes are all to be combined + this.node2Combine = new Vector>(); + int next = 1; + int index = 0; + for(int i = 1; i < this.rootNodes.size(); i++) { + int tmp = this.rootNodes.elementAt(i).elementAt(0).getCid(); + while(next < tmp) { + this.node2Combine.add(new Vector()); + Vector toadd = this.sNodeVecs.elementAt(next); + for(index = 0; index < toadd.size(); index++) { + this.node2Combine.lastElement().add(toadd.elementAt(index)); + } + next++; + } + Vector toadd = this.sNodeVecs.elementAt(tmp); + if(toadd.size() > this.rootNodes.elementAt(i).size()) { + this.node2Combine.add(new Vector()); + for(index = this.rootNodes.elementAt(i).size(); index < toadd.size(); index++) { + this.node2Combine.lastElement().add(toadd.elementAt(index)); + } + } + next++; + } + while(next < this.sNodeVecs.size()) { + this.node2Combine.add(new Vector()); + Vector toadd = this.sNodeVecs.elementAt(next); + for(index = 0; index < toadd.size(); index++) { + this.node2Combine.lastElement().add(toadd.elementAt(index)); + } + next++; + } + } + return trial; + } + + private boolean trial(int num2choose, int next) { + int index = 0; + boolean first = true; + while(num2choose > 0) { + if(first) { + if(next == this.sNodeVecs.size()) { + // no more nodes available to add + return false; + } + this.rootNodes.add(new Vector()); + first = false; + } + this.rootNodes.lastElement().add(this.sNodeVecs.elementAt(next).elementAt(index)); + num2choose--; + index++; + if(index == this.sNodeVecs.elementAt(next).size()) { + index = 0; + next++; + first = true; + } + } + return true; + } + + public Vector> getNode2Combine() { + return node2Combine; + } + + public Vector> getRootNodes() { + return rootNodes; + } + } + + public class Combine { + public ScheduleNode node; + public int root; + public int index; + + public Combine(ScheduleNode n) { + this.node = n; + this.root = -1; + this.index = -1; + } + } + + public class CombineGenerator { + Vector> rootNodes; + Vector> rootNStates; + Vector> node2Combine; + Vector> combine; + int[] lastchoices; + boolean first4choice; + + public CombineGenerator(Vector> rootnodes, Vector> node2combine) { + this.rootNodes = rootnodes; + this.node2Combine = node2combine; + this.rootNStates = new Vector>(); + for(int i = 0; i < this.rootNodes.size(); i++) { + this.rootNStates.add(new Vector()); + for(int j = 0; j < this.rootNodes.elementAt(i).size(); j++) { + this.rootNStates.elementAt(i).add(new int[this.node2Combine.size()]); + for(int k = 0; k < this.node2Combine.size(); k++) { + this.rootNStates.elementAt(i).elementAt(j)[k] = 0; + } + } + } + this.combine = new Vector>(); + for(int i = 0; i < this.node2Combine.size(); i++) { + this.combine.add(new Vector()); + for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) { + this.combine.elementAt(i).add(new Combine(this.node2Combine.elementAt(i).elementAt(j))); + } + } + this.lastchoices = null; + this.first4choice = false; + } + + public Vector> getCombine() { + return combine; + } + + public boolean nextGen() { + boolean trial = false; + if(this.lastchoices == null) { + // first time + this.lastchoices = new int[this.node2Combine.size()]; + for(int i = 0; i < this.lastchoices.length; i++) { + this.lastchoices[i] = 0; + } + this.first4choice = true; + trial = trial(); + } else { + trial = trial(); + while(!trial) { + // no more available combination under this choice + // choose another choice + int next = this.node2Combine.size() - 1; + boolean iter = false;; + do{ + this.lastchoices[next]++; + if(this.lastchoices[next] > this.node2Combine.elementAt(next).elementAt(0).getCid()) { + // break the rule that a node can only be combined to nodes with smaller colorid. + // backtrack + next--; + iter = true; + } else { + iter = false; + } + }while(iter && !(next < 0)); + if(next < 0) { + return false; + } + for(next += 1; next < this.node2Combine.size(); next++) { + this.lastchoices[next] = 0; + } + this.first4choice = true; + trial = trial(); + } + } + return trial; + } + + private boolean trial() { + boolean suc = false; + if(this.first4choice) { + // first time for each choice + // put all the objects of one color into the first bucket indicated by the choice + int next = 0; + suc = firstexpand(next, this.first4choice); + this.first4choice = false; + } else { + int next = this.node2Combine.size() - 1; + int layer = 0; + suc = innertrial(next, layer); + } + return suc; + } + + private boolean firstexpand(int next, boolean first) { + for(int i = next; i < this.node2Combine.size(); i++) { + int choice = this.lastchoices[i]; + for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) { + Combine tmp = this.combine.elementAt(i).elementAt(j); + if(!first) { + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + } + tmp.root = choice; + tmp.index = 0; + if(!first) { + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + } + } + if(first) { + this.rootNStates.elementAt(choice).elementAt(0)[i] = this.node2Combine.elementAt(i).size(); + for(int j = 1; j < this.rootNodes.elementAt(choice).size(); j++) { + this.rootNStates.elementAt(choice).elementAt(j)[i] = 0; + } + } + } + return true; + } + + private boolean innertrial(int next, int layer) { + Combine tmp = this.combine.elementAt(next).lastElement(); + // try to move it backward + int root = tmp.root; + int index = tmp.index; + index++; + if(index == this.rootNodes.elementAt(root).size()) { + // no more place in this color bucket + index = 0; + root++; + }else if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] < + this.rootNStates.elementAt(root).elementAt(index)[next] + 2) { + // break the law of non-increase order inside one color bucket + // try next bucket of another color + index = 0; + root++; + } + if(root == this.rootNodes.size()) { + // no more bucket + // backtrack + root = tmp.root; + index = tmp.index; + int t = this.combine.elementAt(next).size() - 2; + while(true) { + while(!(t < 0)) { + tmp = this.combine.elementAt(next).elementAt(t); + if ((tmp.root != root) || (tmp.index != index)) { + break; + } + t--; + } + if(t < 0) { + // try the bucket in node2combine before + if(next - 1 < 0) { + return false; + } else { + return innertrial(next - 1, ++layer); + } + } else if(tmp.root != root) { + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = root; + tmp.index = 0; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + // make all left things in this color bucket reset + for(t += 1; t < this.combine.elementAt(next).size(); t++) { + tmp = this.combine.elementAt(next).elementAt(t); + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = root; + tmp.index = 0; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + } + if(layer != 0) { + return firstexpand(next+1, this.first4choice); + } + return true; + } else if(tmp.index != index) { + if(this.rootNStates.elementAt(root).elementAt(tmp.index)[next] == + this.rootNStates.elementAt(root).elementAt(index)[next]) { + // break the law of non-increase order inside one color bucket + // go on search forward + index = tmp.index; + } else if(this.rootNStates.elementAt(root).elementAt(tmp.index)[next] < + this.rootNStates.elementAt(root).elementAt(index)[next] + 2) { + // break the law of non-increase order inside one color bucket + // and now they only differ by 1 + // propagate this difference to see if it can fix + boolean suc = propagateOne(next, root, index, t, tmp); + if(suc) { + return suc; + } else { + // go on search forward + index = tmp.index; + } + } else { + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = root; + tmp.index = index; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + if(layer != 0) { + return firstexpand(next+1, this.first4choice); + } + return true; + } + } + } + } else { + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = root; + tmp.index = index; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + if(layer != 0) { + return firstexpand(next+1, this.first4choice); + } + return true; + } + } + + private boolean propagateOne(int next, int rooti, int indexi, int ti, Combine tmp) { + int root = rooti; + int index = indexi; + int t = ti; + int rootbk = tmp.root; + int indexbk = tmp.index; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = root; + tmp.index = index; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + t += 2; + if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] < + this.rootNStates.elementAt(root).elementAt(index)[next]) { + // need to continue propagate + while(t < this.combine.elementAt(next).size()) { + tmp = this.combine.elementAt(next).elementAt(t); + if ((tmp.root != root) || (tmp.index != index)) { + break; + } + t++; + } + if(t == this.combine.elementAt(next).size()) { + if(index + 1 < this.rootNodes.elementAt(root).size()) { + // there is available place inside the same color bucket + Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1); + boolean suc = propagateOne(next, root, index + 1, t - 1, tmpbk); + if(!suc) { + // fail, roll back + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = rootbk; + tmp.index = indexbk; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + } + return suc; + } else if(root+1 < this.rootNodes.size()) { // check if there are another bucket + // yes + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = root + 1; + tmp.index = 0; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + return firstexpand(next+1, this.first4choice); + } else { + // no, roll back + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = rootbk; + tmp.index = indexbk; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + return false; + } + } else if(tmp.root != root) { + Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1); + this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]--; + tmpbk.root = tmp.root; + tmpbk.index = 0; + root = tmp.root; + this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]++; + index = tmp.index; + // make all left things in this color bucket reset + for(t += 1; t < this.combine.elementAt(next).size(); t++) { + tmp = this.combine.elementAt(next).elementAt(t); + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = root; + tmp.index = 0; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + } + return firstexpand(next+1, this.first4choice); + } else if(tmp.index != index) { + Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1); + boolean suc = propagateOne(next, root, tmp.index, t - 1, tmpbk); + if(!suc) { + // fail, roll back + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--; + tmp.root = rootbk; + tmp.index = indexbk; + this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++; + } + return suc; + } + // won't reach here, only to avoid compiler's complain + return true; + } else { + return true; + } + } + } +} \ No newline at end of file diff --git a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java index 2562a8cd..d151b1b3 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java +++ b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java @@ -94,11 +94,16 @@ public class ScheduleAnalysis { sFStates = null; } + ScheduleNode startupNode = 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), 0); - classNodes.elementAt(i).setScheduleNode(sn); + ClassNode cn = classNodes.elementAt(i); + ScheduleNode sn = new ScheduleNode(cn, 0); + if(cn.getClassDescriptor().getSymbol().equals(TypeUtil.StartupClass)) { + startupNode = sn; + } + cn.setScheduleNode(sn); scheduleNodes.add(sn); try { sn.calExeTime(); @@ -160,7 +165,7 @@ public class ScheduleAnalysis { } } cdToCNodes = null; - + // Break down the 'cycle's try { for(i = 0; i < toBreakDown.size(); i++ ) { @@ -191,6 +196,21 @@ public class ScheduleAnalysis { scheduleEdges = ssev; ssev = null; sorted = true; + + // Set the cid of these ScheduleNode + Queue toVisit = new LinkedList(); + toVisit.add(startupNode); + while(!toVisit.isEmpty()) { + ScheduleNode sn = toVisit.poll(); + if(sn.getCid() == -1) { + // not visited before + sn.setCid(ScheduleNode.colorID++); + Iterator it_edge = sn.edges(); + while(it_edge.hasNext()) { + toVisit.add((ScheduleNode)((ScheduleEdge)it_edge.next()).getTarget()); + } + } + } SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes); } @@ -710,78 +730,52 @@ public class ScheduleAnalysis { int reduceNum = this.scheduleNodes.size() - this.coreNum; - // Enough cores, no need to merge more ScheduleEdge + // Combine some ScheduleNode if necessary + // May generate multiple graphs suggesting candidate schedulings if(!(reduceNum > 0)) { + // Enough cores, no need to combine any ScheduleNode this.scheduleGraphs.addElement(this.scheduleNodes); int gid = 1; String path = "scheduling_" + gid + ".dot"; SchedulingUtil.printScheduleGraph(path, 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); - } - - 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; + // 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); } - 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++); + + CombinationUtil.RootsGenerator rGen = CombinationUtil.allocateRootsGenerator(sNodeVecs, this.coreNum); + + while(rGen.nextGen()) { + // first get the chosen rootNodes + Vector> rootNodes = rGen.getRootNodes(); + Vector> nodes2combine = rGen.getNode2Combine(); + + CombinationUtil.CombineGenerator cGen = CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine); + int gid = 1; + while (cGen.nextGen()) { + Vector> combine = cGen.getCombine(); + Vector sNodes = generateScheduling(rootNodes, combine, gid++); this.scheduleGraphs.add(sNodes); - reduceEdges = null; + combine = null; sNodes = null; - } else { - break; } - toreduce = null; - }while(true); - sEdges = null; - candidates = null; - + rootNodes = null; + nodes2combine = null; + } + sNodeVecs = null; } + // Generate schedulings according to result schedule graph if(this.schedulings == null) { this.schedulings = new Vector>(); } @@ -954,10 +948,9 @@ public class ScheduleAnalysis { this.schedulings.add(scheduling); } - } - public Vector generateScheduling(Vector reduceEdges, int gid) { + public Vector generateScheduling(Vector> rootnodes, Vector> combine, int gid) { Vector result = new Vector(); // clone the ScheduleNodes @@ -972,8 +965,7 @@ public class ScheduleAnalysis { sn2sn.put(tocopy, temp); cn2cn = null; } - // clone the ScheduleEdges and merge those in reduceEdges at the same time - Vector toMerge = new Vector(); + // clone the ScheduleEdges for(int i = 0; i < this.scheduleEdges.size(); i++) { ScheduleEdge sse = this.scheduleEdges.elementAt(i); ScheduleNode csource = sn2sn.get(sse.getSource()); @@ -999,129 +991,44 @@ public class ScheduleAnalysis { 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 - switch(sEdge.getType()) { - case ScheduleEdge.NEWEDGE: { - try { - ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge); - } catch(Exception e) { - e.printStackTrace(); - System.exit(-1); - } - break; - } - case ScheduleEdge.TRANSEDGE: { - try { - ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge); + // combine those nodes in combine with corresponding rootnodes + for(int i = 0; i < combine.size(); i++) { + 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); } - break; - } + result.removeElement(tocombine); } - result.removeElement(sEdge.getTarget()); - if(ScheduleEdge.NEWEDGE == sEdge.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. - sEdge.setTarget(sEdge.getTargetCNode()); - sEdge.setSource(sEdge.getSourceCNode()); - sEdge.getTargetCNode().addEdge(sEdge); - } } - toMerge = null; + + sn2hash = null; + sn2sn = null; String path = "scheduling_" + gid + ".dot"; SchedulingUtil.printScheduleGraph(path, result); return result; } - - class Combination{ - Combination tail; - Object head; - Vector factors; - int selectNum; - int resultNum; - - public Combination(Vector factors, int selectNum) throws Exception{ - this.factors = factors; - if(factors.size() < selectNum) { - throw new Exception("Error: selectNum > 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); - } - 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; - } - 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; - } - } } diff --git a/Robust/src/Analysis/Scheduling/ScheduleNode.java b/Robust/src/Analysis/Scheduling/ScheduleNode.java index ba8363f0..063515f9 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleNode.java +++ b/Robust/src/Analysis/Scheduling/ScheduleNode.java @@ -12,7 +12,9 @@ public class ScheduleNode extends GraphNode implements Cloneable{ private int uid; private int gid; + private int cid; private static int nodeID=0; + public static int colorID = 0; private Vector classNodes; Vector scheduleEdges; @@ -26,6 +28,7 @@ public class ScheduleNode extends GraphNode implements Cloneable{ public ScheduleNode(int gid) { this.uid = ScheduleNode.nodeID++; this.gid = gid; + this.cid = -1; this.executionTime = -1; this.classNodes = null; this.scheduleEdges = null; @@ -34,6 +37,7 @@ public class ScheduleNode extends GraphNode implements Cloneable{ public ScheduleNode(ClassNode cn, int gid) { this.uid = ScheduleNode.nodeID++; this.gid = gid; + this.cid = -1; this.classNodes = new Vector(); this.scheduleEdges = new Vector(); this.classNodes.add(cn); @@ -45,6 +49,14 @@ public class ScheduleNode extends GraphNode implements Cloneable{ return uid; } + public int getCid() { + return cid; + } + + public void setCid(int cid) { + this.cid = cid; + } + public String toString() { String temp = new String(""); for(int i = 0; i < classNodes.size(); i++) { @@ -116,6 +128,9 @@ public class ScheduleNode extends GraphNode implements Cloneable{ if(fs.uid != this.uid) { return false; } + if(fs.cid != this.cid) { + return false; + } } if ((fs.executionTime != this.executionTime)){ return false; @@ -133,7 +148,7 @@ public class ScheduleNode extends GraphNode implements Cloneable{ } public int hashCode() { - int hashcode = gid^uid^executionTime; + int hashcode = gid^uid^cid^executionTime; if(this.classNodes != null) { hashcode ^= classNodes.hashCode(); } @@ -161,6 +176,7 @@ public class ScheduleNode extends GraphNode implements Cloneable{ } o.uid = ScheduleNode.nodeID++; o.gid = gid; + o.cid = this.cid; // Clone all the internal ClassNodes and ScheduleEdges Vector tcns = new Vector(); Vector tses = new Vector(); @@ -317,4 +333,50 @@ public class ScheduleNode extends GraphNode implements Cloneable{ this.executionTime += ((ScheduleNode)se.getTarget()).getExeTime(); } } + + public void mergeSNode(ScheduleNode sn) throws Exception { + Vector targetCNodes = (Vector)sn.getClassNodes(); + Vector targetSEdges = (Vector)sn.getScheduleEdges(); + + for(int i = 0; i < targetCNodes.size(); i++) { + targetCNodes.elementAt(i).setScheduleNode(this); + } + + if(classNodes == null) { + classNodes = targetCNodes; + scheduleEdges = targetSEdges; + } else { + if(targetCNodes.size() != 0) { + classNodes.addAll(targetCNodes); + } + if(targetSEdges.size() != 0) { + scheduleEdges.addAll(targetSEdges); + } + } + targetCNodes = null; + targetSEdges = null; + + // redirect external ScheduleEdges to this ScheduleNode + Iterator it_edges = sn.edges(); + while(it_edges.hasNext()) { + ScheduleEdge tse = (ScheduleEdge)it_edges.next(); + tse.setSource(this); + this.edges.addElement(tse); + } + + it_edges = sn.inedges(); + while(it_edges.hasNext()) { + ScheduleEdge tse = (ScheduleEdge)it_edges.next(); + tse.setTarget(this); + this.inedges.addElement(tse); + } + + // As all tasks inside one ScheduleNode are executed sequentially, + // simply add the execution time of all the ClassNodes inside one ScheduleNode. + if(this.executionTime == -1) { + this.executionTime = 0; + } + this.executionTime += sn.getExeTime(); + + } } diff --git a/Robust/src/Benchmarks/PERT/Mcore/Estimator.java b/Robust/src/Benchmarks/PERT/Mcore/Estimator.java deleted file mode 100644 index 2539ae6f..00000000 --- a/Robust/src/Benchmarks/PERT/Mcore/Estimator.java +++ /dev/null @@ -1,107 +0,0 @@ -public class Estimator { - flag estimate; - flag prob; - - int stages; - int time; - float variance; - float[] probtable; - - public Estimator(int stages) { - this.stages = stages; - this.time = 0; - this.variance = 0; - - this.probtable = new float[31]; - int i = 0; - this.probtable[i++] = (float)0.5000; - this.probtable[i++] = (float)0.5398; - this.probtable[i++] = (float)0.5793; - this.probtable[i++] = (float)0.6179; - this.probtable[i++] = (float)0.6554; - this.probtable[i++] = (float)0.6915; - this.probtable[i++] = (float)0.7257; - this.probtable[i++] = (float)0.7580; - this.probtable[i++] = (float)0.7881; - this.probtable[i++] = (float)0.8159; - this.probtable[i++] = (float)0.8413; - this.probtable[i++] = (float)0.8643; - this.probtable[i++] = (float)0.8849; - this.probtable[i++] = (float)0.9032; - this.probtable[i++] = (float)0.9192; - this.probtable[i++] = (float)0.9332; - this.probtable[i++] = (float)0.9452; - this.probtable[i++] = (float)0.9554; - this.probtable[i++] = (float)0.9641; - this.probtable[i++] = (float)0.9713; - this.probtable[i++] = (float)0.9772; - this.probtable[i++] = (float)0.9821; - this.probtable[i++] = (float)0.9861; - this.probtable[i++] = (float)0.9893; - this.probtable[i++] = (float)0.9918; - this.probtable[i++] = (float)0.9938; - this.probtable[i++] = (float)0.9953; - this.probtable[i++] = (float)0.9965; - this.probtable[i++] = (float)0.9974; - this.probtable[i++] = (float)0.9981; - this.probtable[i++] = (float)0.9987; - } - - public boolean estimate(int time, float variance2) { - //System.printI(0xff30); - this.time += time; - this.variance += variance2; - --this.stages; - //System.printI(0xff31); - //System.printI(this.stages); - //System.printI(this.time); - //System.printI((int)this.variance); - if(this.stages == 0) { - //System.printI(0xff32); - //System.printString("variance2: " + (int)(this.variance*100) + "(/100); "); - this.variance = Math.sqrtf(this.variance); - //System.printString("variance: " + (int)(this.variance*100) + "(/100)\n"); - return true; - } - //System.printI(0xff33); - return false; - } - - public float getProbability(int x, int y) { - int l = x; - int r = y; - if(x > y) { - l = y; - r = x; - } - - float prob = prob(r) - prob(l); - return prob; - } - - private float prob(int s) { - int tmp = (int)((s - this.time) * 10 / this.variance); - //System.printString(tmp + "\n"); - int abs = (int)Math.abs(tmp); - float prob = 0; - if(abs > this.probtable.length - 1) { - prob = 1; - } else { - prob = this.probtable[abs]; - } - if(tmp < 0) { - return (float)1.0 - prob; - } else { - return prob; - } - } - - public int getTime() { - return this.time; - } - - public float getVariance() { - return this.variance; - } - -} diff --git a/Robust/src/Benchmarks/PERT/Mcore/PERT.java b/Robust/src/Benchmarks/PERT/Mcore/PERT.java deleted file mode 100644 index 1d5ff893..00000000 --- a/Robust/src/Benchmarks/PERT/Mcore/PERT.java +++ /dev/null @@ -1,56 +0,0 @@ -task t1(StartupObject s{initialstate}) { - //System.printString("task t1\n"); - int stages = 2; - Estimator estimator = new Estimator(stages){estimate}; - for(int i = 0; i < stages; ++i) { - Stage stage = new Stage(i){sampling}; - } - - taskexit(s{!initialstate}); -} - -task t2(Stage s{sampling}) { - //System.printString("task t2\n"); - - s.sampling(); - - taskexit(s{!sampling, estimate}); -} - -task t3(Stage s{estimate}) { - //System.printString("task t3\n"); - - s.estimate(); - - taskexit(s{!estimate, merge}); -} - -task t4(Estimator e{estimate}, Stage s{merge}) { - //System.printString("task t4\n"); - - boolean fake = false; - boolean finish = e.estimate(s.getAntTime(), s.getAntVariance2()); - - if(finish) { - //System.printI(0xff40); - taskexit(e{!estimate, prob}, s{!merge}); - } else { - //System.printI(0xff41); - taskexit(s{!merge}); - } -} - -task t5(Estimator e{prob}) { - //System.printString("task t5\n"); - - int x = 10; - int y = 20; - //System.printString("x: " + x + "; y: " + y + "\n"); - //System.printString("The anticipate days need to finish this project is: " + e.getTime() + "\n"); - //System.printString("And the anticipate variance is: " + (int)(e.getVariance()*100) + "(/100)\n"); - float prob = e.getProbability(x, y); - - //System.printString("The probability of this project to be finished in " + x + " to " + y + " days is: " + (int)(prob*100) + "%\n"); - //System.printI((int)(prob*100)); - taskexit(e{!prob}); -} diff --git a/Robust/src/Benchmarks/PERT/Mcore/Stage.java b/Robust/src/Benchmarks/PERT/Mcore/Stage.java deleted file mode 100644 index accb9bbc..00000000 --- a/Robust/src/Benchmarks/PERT/Mcore/Stage.java +++ /dev/null @@ -1,108 +0,0 @@ -public class Stage { - flag sampling; - flag estimate; - flag merge; - - int ID; - - int[] samplings; - int optime; - int nortime; - int petime; - int time; - float variance2; - - public Stage(int id) { - //System.printI(0xff20); - this.ID = id; - - this.samplings = new int[10]; - //System.printI(0xff21); - for(int i = 0; i < this.samplings.length; ++i) { - this.samplings[i] = 0; - //System.printString(tint + "; "); - } - //System.printI(0xff23); - - this.optime = 0; - this.nortime = 0; - this.petime = 0; - this.time = 0; - this.variance2 = 0; - //System.printI(0xff24); - } - - public void sampling() { - //System.printI(0xff00); - int tint = 0; - //System.printI(this.samplings.length); - int i = 0; - if(this.ID == 0) { - //System.printI(0xff01); - this.samplings[i++] = 33; - this.samplings[i++] = 36; - this.samplings[i++] = 27; - this.samplings[i++] = 15; - this.samplings[i++] = 43; - this.samplings[i++] = 35; - this.samplings[i++] = 36; - this.samplings[i++] = 42; - this.samplings[i++] = 49; - this.samplings[i++] = 21; - } else if(this.ID == 1) { - //System.printI(0xff02); - this.samplings[i++] = 12; - this.samplings[i++] = 27; - this.samplings[i++] = 40; - this.samplings[i++] = 9; - this.samplings[i++] = 13; - this.samplings[i++] = 26; - this.samplings[i++] = 40; - this.samplings[i++] = 26; - this.samplings[i++] = 22; - this.samplings[i++] = 36; - } - //System.printI(0xff03); - } - - public void estimate() { - //System.printI(0xff10); - int highest = this.samplings[0]; - //System.printI(0xff12); - int lowest = this.samplings[0]; - int sum = this.samplings[0]; - //System.printI(0xff13); - //System.printI(this.samplings.length); - for(int i = 1; i < this.samplings.length; ++i) { - //System.printI(0xff14); - int temp = this.samplings[i]; - if(temp > highest) { - highest = temp; - } else if(temp < lowest) { - lowest = temp; - } - sum += temp; - } - //System.printI(0xff15); - sum = sum - highest - lowest; - int ordinary = sum / (this.samplings.length - 2); - this.optime = lowest;; - this.petime = highest; - this.nortime = ordinary; - //System.printI(0xff16); - this.time = (this.optime + 4 * this.nortime + this.petime) / 6; - //System.printI(0xff17); - this.variance2 = (float)(this.optime - this.petime) * (float)(this.optime - this.petime) / (float)36.0; - //System.printI(0xff18); - //System.printString("Op time: " + this.optime + "; Nor time: " + this.nortime + "; Pe time: " + this.petime + "; variance2: " + (int)(this.variance2*100) + "(/100)\n"); - } - - public int getAntTime() { - return this.time; - } - - public float getAntVariance2() { - return this.variance2; - } - -} diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index be373de8..37a83aaf 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -307,7 +307,7 @@ public class Main { int newRate = 1; String cdname = cd.getSymbol(); if(cdname.equals("SeriesRunner")) { - newRate = 10; + newRate = 16; } else if(cdname.equals("MapWorker")) { newRate = 6; } else if(cdname.equals("ReduceWorker")) { @@ -332,7 +332,7 @@ public class Main { /*do { tint = r.nextInt()%10; } while(tint <= 0);*/ - tint = 1; + tint = 3; ((FEdge)it_edges.next()).setExeTime(tint); } } @@ -368,7 +368,7 @@ public class Main { } 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) + ", "); + System.out.print((selectedScheduling.elementAt(i) + 1) + ", "); } System.out.println(); -- 2.34.1