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<ScheduleNode> scheduleNodes;
Vector<ClassNode> classNodes;
+ Vector<ScheduleEdge> scheduleEdges;
Hashtable<ClassDescriptor, ClassNode> cd2ClassNode;
boolean sorted = false;
- Vector<ScheduleEdge> scheduleEdges;
int transThreshold;
+
+ int coreNum;
+ Vector<Vector<ScheduleNode>> scheduleGraphs;
+ Vector<Vector<Schedule>> schedulings;
public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) {
this.state = state;
this.classNodes = new Vector<ClassNode>();
this.scheduleEdges = new Vector<ScheduleEdge>();
this.cd2ClassNode = new Hashtable<ClassDescriptor, ClassNode>();
-
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<Vector<Schedule>> getSchedulings() {
+ return this.schedulings;
+ }
+
+ // for test
public Vector<ScheduleEdge> getSEdges4Test() {
return scheduleEdges;
}
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 {
// 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);
rootnodes = null;
}
}
+ cdToCNodes = null;
// Do topology sort of the ClassNodes and ScheduleEdges.
Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
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++) {
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<ClassNode> cNodes = sNode.getClassNodes();
- for(int i = 0; i < cNodes.size(); i++) {
- classNodes.removeElement(cNodes.elementAt(i));
- cd2ClassNode.remove(cNodes.elementAt(i).getClassDescriptor());
- }
- Vector<ScheduleEdge> edges = sNode.getEdgeVector();
- for(int j = 0; j < edges.size(); j++) {
- removeSNodeList(edges.elementAt(j));
- }
- }*/
-
public void scheduleAnalysis() {
// First iteration
int i = 0;
fe2ses.clear();
sn2fes.clear();
}
+ fe2ses = null;
+ sn2fes = null;
+
+ SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
}
private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
// 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());
private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) {
Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
- 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;
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<ScheduleNode> toClone = new LinkedList<ScheduleNode>();
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 {
}else {
break;
}
+ inedges = null;
}
exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
return exeTime;
}
}
}
+ sfss = null;
Vector<FlagState> 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());
}
}
}
-
+ 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);
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<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
+ Vector<ClassNode> rCNodes = new Vector<ClassNode>();
+ 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<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
+ //Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
while(it_sEdges.hasNext()) {
ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
}
}
se.getSource().getEdgeVector().removeAll(toremove);
+ toremove = null;
+ sFStates = null;
if(!copy) {
//merge se into its source ScheduleNode
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<Vector<ScheduleNode>>();
+ }
+
+ 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<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
+ 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<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
+ 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<ScheduleNode> 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<Vector<Schedule>>();
+ }
+
+ for(int i = 0; i < this.scheduleGraphs.size(); i++) {
+ Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
+ Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
+ // for each ScheduleNode create a schedule node representing a core
+ Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
+ 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<ClassNode> 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<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
+ Vector<ScheduleNode> result = new Vector<ScheduleNode>();
+
+ // clone the ScheduleNodes
+ Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
+ Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
+ for(int i = 0; i < this.scheduleNodes.size(); i++) {
+ Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
+ 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<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
+ 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<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
+ Hashtable<ClassNode, ClassNode> 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<namers.size();i++) {
- Namer name=(Namer) namers.get(i);
- String newlabel=name.nodeLabel(gn);
- String newparams=name.nodeOption(gn);
-
- if (!newlabel.equals("") && !label.equals("")) {
- label+=", ";
+ 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);
}
- 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<namers.size();i++) {
- Namer name=(Namer) namers.get(i);
- String newlabel=name.edgeLabel(edge);
- String newoption=name.edgeOption(edge);
- if (!newlabel.equals("")&& ! edgelabel.equals(""))
- edgelabel+=", ";
- edgelabel+=newlabel;
- if (!newoption.equals(""))
- edgedotnodeparams+=", "+newoption;
- }
- edgelabel+=":[" + ((FEdge)edge).getExeTime() + "]";
- Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
- if(hashtable != null) {
- Set<ClassDescriptor> 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;
}
-
}
projects / IRC.git / blobdiff