ac476561225262b150af6c9c3397628b3f2b1a16
[IRC.git] / Robust / src / Analysis / Scheduling / ScheduleAnalysis.java
1 package Analysis.Scheduling;
2
3 import Analysis.TaskStateAnalysis.*;
4 import IR.*;
5
6 import java.util.*;
7
8 /** This class holds flag transition diagram(s) can be put on one core.
9  */
10 public class ScheduleAnalysis {
11     
12     State state;
13     TaskAnalysis taskanalysis;
14     Vector<ScheduleNode> scheduleNodes;
15     Vector<ClassNode> classNodes;
16     Vector<ScheduleEdge> scheduleEdges;
17     Hashtable<ClassDescriptor, ClassNode> cd2ClassNode;
18     boolean sorted = false;
19
20     int transThreshold;
21     
22     int coreNum;
23     Vector<Vector<ScheduleNode>> scheduleGraphs;
24     Vector<Vector<Schedule>> schedulings;
25
26     public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) {
27         this.state = state;
28         this.taskanalysis = taskanalysis;
29         this.scheduleNodes = new Vector<ScheduleNode>();
30         this.classNodes = new Vector<ClassNode>();
31         this.scheduleEdges = new Vector<ScheduleEdge>();
32         this.cd2ClassNode = new Hashtable<ClassDescriptor, ClassNode>();
33         this.transThreshold = 45;
34         this.coreNum = -1;
35         this.scheduleGraphs = null;
36         this.schedulings = null;
37     } 
38     
39     public void setTransThreshold(int tt) {
40         this.transThreshold = tt;
41     }
42     
43     public int getCoreNum() {
44         return coreNum;
45     }
46
47     public void setCoreNum(int coreNum) {
48         this.coreNum = coreNum;
49     }
50     
51     public Iterator getScheduleGraphs() {
52         return this.scheduleGraphs.iterator();
53     }
54     
55     public Iterator getSchedulingsIter() {
56         return this.schedulings.iterator();
57     }
58     
59     public Vector<Vector<Schedule>> getSchedulings() {
60         return this.schedulings;
61     }
62     
63     // for test
64     public Vector<ScheduleEdge> getSEdges4Test() {
65         return scheduleEdges;
66     }
67     
68     public void preSchedule() {
69         Hashtable<ClassDescriptor, ClassNode> cdToCNodes = new Hashtable<ClassDescriptor, ClassNode>();
70         // Build the combined flag transition diagram
71         // First, for each class create a ClassNode
72         for(Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext(); ) {
73             ClassDescriptor cd = (ClassDescriptor) it_classes.next();
74             Set<FlagState> fStates = taskanalysis.getFlagStates(cd);
75             
76             //Sort flagState nodes inside this ClassNode
77             Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
78             
79             Vector rootnodes  = taskanalysis.getRootNodes(cd);
80             if(((rootnodes != null) && (rootnodes.size() > 0)) || (cd.getSymbol().equals(TypeUtil.StartupClass))) {
81                 ClassNode cNode = new ClassNode(cd, sFStates);
82                 cNode.setSorted(true);
83                 classNodes.add(cNode);
84                 cd2ClassNode.put(cd, cNode);
85                 cdToCNodes.put(cd, cNode);
86                 cNode.calExeTime();
87                 
88                 // for test
89                 if(cd.getSymbol().equals("C")) {
90                     cNode.setTransTime(45);
91                 }
92             }
93             fStates = null;
94             sFStates = null;
95         }
96
97         // For each ClassNode create a ScheduleNode containing it
98         int i = 0;
99         for(i = 0; i < classNodes.size(); i++) {
100             ScheduleNode sn = new ScheduleNode(classNodes.elementAt(i), 0);
101             classNodes.elementAt(i).setScheduleNode(sn);
102             scheduleNodes.add(sn);
103             try {
104                 sn.calExeTime();
105             } catch (Exception e) {
106                 e.printStackTrace();
107             }
108         }
109         
110         // Create 'new' edges between the ScheduleNodes.
111         Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
112         for(i = 0; i < classNodes.size(); i++) {
113             ClassNode cNode = classNodes.elementAt(i);
114             ClassDescriptor cd = cNode.getClassDescriptor();
115             Vector rootnodes  = taskanalysis.getRootNodes(cd);              
116             if(rootnodes != null) {
117                 for(int h = 0; h < rootnodes.size(); h++){
118                     FlagState root=(FlagState)rootnodes.elementAt(h);
119                     Vector allocatingTasks = root.getAllocatingTasks();
120                     if(allocatingTasks != null) {
121                         for(int k = 0; k < allocatingTasks.size(); k++) {
122                             TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
123                             Vector<FEdge> fev = (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
124                             int numEdges = fev.size();
125                             ScheduleNode sNode = cNode.getScheduleNode();
126                             for(int j = 0; j < numEdges; j++) {
127                                 FEdge pfe = fev.elementAt(j);
128                                 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
129                                 if ((noi == null) || (noi.getNewRate() == 0) || (noi.getProbability() == 0)) {
130                                     // fake creating edge, do not need to create corresponding 'new' edge
131                                     continue;
132                                 }
133                                 if(noi.getRoot() == null) {
134                                     // set root FlagState
135                                     noi.setRoot(root);
136                                 }
137                                 FlagState pfs = (FlagState)pfe.getTarget();
138                                 ClassDescriptor pcd = pfs.getClassDescriptor();
139                                 ClassNode pcNode = cdToCNodes.get(pcd);
140                                 
141                                 ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, ScheduleEdge.NEWEDGE, 0);
142                                 sEdge.setFEdge(pfe);
143                                 sEdge.setSourceCNode(pcNode);
144                                 sEdge.setTargetCNode(cNode);
145                                 sEdge.setTargetFState(root);
146                                 sEdge.setNewRate(noi.getNewRate());
147                                 sEdge.setProbability(noi.getProbability());
148                                 pcNode.getScheduleNode().addEdge(sEdge);
149                                 scheduleEdges.add(sEdge);
150                                 if((j !=0 ) || (k != 0) || (h != 0)) {
151                                     toBreakDown.add(sEdge);
152                                 }
153                             }
154                             fev = null;
155                         }
156                         allocatingTasks = null;
157                     }
158                 }
159                 rootnodes = null;
160             }
161         }
162         cdToCNodes = null;
163         
164         // Create 'associate' edges between the ScheduleNodes.
165         /*Iterator<TaskDescriptor> it_tasks = (Iterator<TaskDescriptor>)state.getTaskSymbolTable().getDescriptorsIterator();
166         while(it_tasks.hasNext()) {
167             TaskDescriptor td = it_tasks.next();
168             int numParams = td.numParameters();
169             if(!(numParams > 1)) {
170                 // single parameter task
171                 continue;
172             }
173             ClassNode[] cNodes = new ClassNode[numParams];
174             for(i = 0; i < numParams; ++i) {
175                 cNodes[i] = this.cd2ClassNode.get(td.getParamType(i).getClassDesc());
176             }
177             Vector<FEdge> fev = (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
178             // for each fedge associated to this td, create an associate ScheduleEdge
179             // from the ClassNode containg this FEdge to every other ClassNode representing
180             // other parameters.
181             for(i = 0; i < fev.size(); ++i) {
182                 FEdge tmpfe = fev.elementAt(i);
183                 for(int j = 0; j < numParams; ++j) {
184                     if(j == tmpfe.getIndex()) {
185                         continue;
186                     }
187                     FlagState fs = (FlagState)tmpfe.getSource();
188                     ScheduleEdge se = new ScheduleEdge(cNodes[j].getScheduleNode(), "associate", fs, ScheduleEdge.ASSOCEDGE, 0);
189                     se.setFEdge(tmpfe);
190                     se.setSourceCNode(cNodes[i]);
191                     se.setTargetCNode(cNodes[j]);
192                     // targetFState is always null
193                     cNodes[i].getScheduleNode().addAssociateSEdge(se);
194                     // scheduleEdges only holds new/transmit edges
195                     //scheduleEdges.add(se);  
196                     fs.addAlly(se);
197                 }
198             } 
199         }*/
200
201         // Break down the 'cycle's
202         try {
203             for(i = 0; i < toBreakDown.size(); i++ ) {
204                 cloneSNodeList(toBreakDown.elementAt(i), false);
205             }
206             toBreakDown = null;
207         } catch (Exception e) {
208             e.printStackTrace();
209             System.exit(-1);
210         }
211         
212         // Remove fake 'new' edges
213         for(i = 0; i < scheduleEdges.size(); i++) {
214             /*if(ScheduleEdge.NEWEDGE != scheduleEdges.elementAt(i).getType()) {
215                 continue;
216             }*/
217             ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
218             if((0 == se.getNewRate()) || (0 == se.getProbability())) {
219                 scheduleEdges.removeElement(se);
220                 scheduleNodes.removeElement(se.getTarget());
221             }
222         }
223         
224         // Do topology sort of the ClassNodes and ScheduleEdges.
225         Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
226         Vector<ScheduleNode> tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev);
227         scheduleNodes.removeAllElements();
228         scheduleNodes = tempSNodes;
229         tempSNodes = null;
230         scheduleEdges.removeAllElements();
231         scheduleEdges = ssev;
232         ssev = null;
233         sorted = true;
234         
235         SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
236     }
237     
238     public void scheduleAnalysis() {
239         // First iteration
240         int i = 0; 
241         //Access the ScheduleEdges in reverse topology order
242         Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses = new Hashtable<FEdge, Vector<ScheduleEdge>>();
243         Hashtable<ScheduleNode, Vector<FEdge>> sn2fes = new Hashtable<ScheduleNode, Vector<FEdge>>();
244         ScheduleNode preSNode = null;
245         for(i = scheduleEdges.size(); i > 0; i--) {
246             ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
247             if(ScheduleEdge.NEWEDGE == se.getType()) {
248                 if(preSNode == null) {
249                     preSNode = (ScheduleNode)se.getSource();
250                 }
251             
252                 boolean split = false;
253                 FEdge fe = se.getFEdge();
254                 if(fe.getSource() == fe.getTarget()) {
255                     // back edge
256                     try {
257                         int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
258                         int rate = 0;
259                         if(repeat > 1){
260                             for(int j = 1; j< repeat; j++ ) {
261                                 cloneSNodeList(se, true);
262                             }
263                             se.setNewRate(1);
264                             se.setProbability(100);
265                         }  
266                         try {
267                             rate = (int)Math.ceil(se.getListExeTime()/ calInExeTime(se.getSourceFState()));
268                         } catch (Exception e) {
269                             e.printStackTrace();
270                         }
271                         for(int j = rate - 1; j > 0; j--) {
272                             for(int k = repeat; k > 0; k--) {
273                                 cloneSNodeList(se, true);
274                             }
275                         }
276                     } catch (Exception e) {
277                         e.printStackTrace();
278                         System.exit(-1);
279                     }
280                 } else {
281                     // if preSNode is not the same as se's source ScheduleNode
282                     // handle any ScheduleEdges previously put into fe2ses whose source ScheduleNode is preSNode
283                     boolean same = (preSNode == se.getSource());
284                     if(!same) {
285                         // check the topology sort, only process those after se.getSource()
286                         if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()) {
287                             if(sn2fes.containsKey(preSNode)) {
288                                 Vector<FEdge> fes = sn2fes.remove(preSNode);
289                                 for(int j = 0; j < fes.size(); j++) {
290                                     FEdge tempfe = fes.elementAt(j);
291                                     Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
292                                     ScheduleEdge tempse = ses.elementAt(0);
293                                     int temptime = tempse.getListExeTime();
294                                     // find out the ScheduleEdge with least exeTime
295                                     for(int k = 1; k < ses.size(); k++) {
296                                         int ttemp = ses.elementAt(k).getListExeTime();
297                                         if(ttemp < temptime) {
298                                             tempse = ses.elementAt(k);
299                                             temptime = ttemp;
300                                         }
301                                     }
302                                     // handle the tempse
303                                     handleScheduleEdge(tempse, true);
304                                     ses.removeElement(tempse);
305                                     // handle other ScheduleEdges
306                                     for(int k = 0; k < ses.size(); k++) {
307                                         handleScheduleEdge(ses.elementAt(k), false);
308                                     }
309                                     ses = null;
310                                     fe2ses.remove(tempfe);
311                                 }
312                                 fes = null;
313                             }
314                         }
315                         preSNode = (ScheduleNode)se.getSource();
316                     }
317                     
318                     // if fe is the last task inside this ClassNode, delay the expanding and merging until we find all such 'new' edges
319                     // associated with a last task inside this ClassNode
320                     if(!fe.getTarget().edges().hasNext()) {
321                         if(fe2ses.get(fe) == null) {
322                             fe2ses.put(fe, new Vector<ScheduleEdge>());
323                         }
324                         if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
325                             sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
326                         }
327                         if(!fe2ses.get(fe).contains(se)) {
328                             fe2ses.get(fe).add(se);
329                         }
330                         if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
331                             sn2fes.get((ScheduleNode)se.getSource()).add(fe);
332                         }
333                     } else {
334                         // As this is not a last task, first handle available ScheduleEdges previously put into fe2ses
335                         if((same) && (sn2fes.containsKey(preSNode))) {
336                             Vector<FEdge> fes = sn2fes.remove(preSNode);
337                             for(int j = 0; j < fes.size(); j++) {
338                                 FEdge tempfe = fes.elementAt(j);
339                                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
340                                 ScheduleEdge tempse = ses.elementAt(0);
341                                 int temptime = tempse.getListExeTime();
342                                 // find out the ScheduleEdge with least exeTime
343                                 for(int k = 1; k < ses.size(); k++) {
344                                     int ttemp = ses.elementAt(k).getListExeTime();
345                                     if(ttemp < temptime) {
346                                         tempse = ses.elementAt(k);
347                                         temptime = ttemp;
348                                     }
349                                 }
350                                 // handle the tempse
351                                 handleScheduleEdge(tempse, true);
352                                 ses.removeElement(tempse);
353                                 // handle other ScheduleEdges
354                                 for(int k = 0; k < ses.size(); k++) {
355                                     handleScheduleEdge(ses.elementAt(k), false);
356                                 }
357                                 ses = null;
358                                 fe2ses.remove(tempfe);
359                             }
360                             fes = null;
361                         }
362                         
363                         if((!(se.getTransTime() < this.transThreshold)) && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
364                             split = true;
365                             splitSNode(se, true);
366                         } else {
367                             // handle this ScheduleEdge
368                             handleScheduleEdge(se, true);
369                         }
370                     }                   
371                 }
372             }
373         }
374         if(!fe2ses.isEmpty()) {
375             Set<FEdge> keys = fe2ses.keySet();
376             Iterator it_keys = keys.iterator();
377             while(it_keys.hasNext()) {
378                 FEdge tempfe = (FEdge)it_keys.next();
379                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
380                 ScheduleEdge tempse = ses.elementAt(0);
381                 int temptime = tempse.getListExeTime();
382                 // find out the ScheduleEdge with least exeTime
383                 for(int k = 1; k < ses.size(); k++) {
384                     int ttemp = ses.elementAt(k).getListExeTime();
385                     if(ttemp < temptime) {
386                         tempse = ses.elementAt(k);
387                         temptime = ttemp;
388                     }
389                 }
390                 // handle the tempse
391                 handleScheduleEdge(tempse, true);
392                 ses.removeElement(tempse);
393                 // handle other ScheduleEdges
394                 for(int k = 0; k < ses.size(); k++) {
395                     handleScheduleEdge(ses.elementAt(k), false);
396                 }
397                 ses = null;
398             }
399             keys = null;
400             fe2ses.clear();
401             sn2fes.clear();
402         }
403         fe2ses = null;
404         sn2fes = null;
405         
406         SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
407     }
408     
409     private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
410         try {
411             int rate = 0;
412             int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
413             if(merge) {
414                 try {
415                     rate = (int)Math.ceil((se.getTransTime() - calInExeTime(se.getSourceFState()))/ se.getListExeTime());
416                     if(rate < 0 ) {
417                         rate = 0;
418                     }
419                 } catch (Exception e) {
420                     e.printStackTrace();
421                 }
422                 if(0 == rate) {
423                     // clone the whole ScheduleNode lists starting with se's target
424                     for(int j = 1; j < repeat; j++ ) {
425                         cloneSNodeList(se, true);
426                     }
427                     se.setNewRate(1);
428                     se.setProbability(100);
429                 } else {
430                     repeat -= rate;
431                     if(repeat > 0){
432                         // clone the whole ScheduleNode lists starting with se's target
433                         for(int j = 0; j < repeat; j++ ) {
434                             cloneSNodeList(se, true);
435                         }
436                         se.setNewRate(rate);
437                         se.setProbability(100);
438                     }
439                 }
440                 // merge the original ScheduleNode to the source ScheduleNode
441                 ((ScheduleNode)se.getSource()).mergeSEdge(se);
442                 scheduleNodes.remove(se.getTarget());
443                 scheduleEdges.remove(se);
444                 // As se has been changed into an internal edge inside a ScheduleNode, 
445                 // change the source and target of se from original ScheduleNodes into ClassNodes.
446                 se.setTarget(se.getTargetCNode());
447                 se.setSource(se.getSourceCNode());
448                 se.getTargetCNode().addEdge(se);
449             } else {
450                 // clone the whole ScheduleNode lists starting with se's target
451                 for(int j = 1; j < repeat; j++ ) {
452                     cloneSNodeList(se, true);
453                 }
454                 se.setNewRate(1);
455                 se.setProbability(100);
456             }
457         } catch (Exception e) {
458             e.printStackTrace();
459             System.exit(-1);
460         }
461     }
462     
463     private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) throws Exception {
464         Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in orignal se's targe to cloned one
465         ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
466         scheduleNodes.add(csNode);
467         
468         // Clone all the external in ScheduleEdges
469         int i;  
470         if(copyIE) {
471             Vector inedges = sEdge.getTarget().getInedgeVector();
472             for(i = 0; i < inedges.size(); i++) {
473                 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
474                 ScheduleEdge se;
475                 switch(tse.getType()) {
476                 case ScheduleEdge.NEWEDGE: {
477                     se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getType(), 0);
478                     se.setProbability(100);
479                     se.setNewRate(1);
480                     break;
481                 }
482                 case ScheduleEdge.TRANSEDGE: {
483                     se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), tse.getType(), 0);
484                     se.setProbability(tse.getProbability());
485                     se.setNewRate(tse.getNewRate());
486                     break;
487                 }
488                 /*case ScheduleEdge.ASSOCEDGE: {
489                     se = new ScheduleEdge(csNode, "associate", tse.getFstate(), tse.getType(), 0);
490                     se.setProbability(tse.getProbability());
491                     se.setNewRate(tse.getNewRate());
492                     break;
493                 }*/
494                 default: {
495                     throw new Exception("Error: not valid ScheduleEdge here");
496                 }
497                 }
498                 se.setSourceCNode(tse.getSourceCNode());
499                 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
500                 se.setFEdge(tse.getFEdge());
501                 se.setTargetFState(tse.getTargetFState());
502                 se.setIsclone(true);
503                 tse.getSource().addEdge(se);
504                 scheduleEdges.add(se);
505             }
506             inedges = null;
507             
508             // in associate ScheduleEdgs
509             /*inedges = ((ScheduleNode)sEdge.getTarget()).getInAssociateSEdges();
510             for(i = 0; i < inedges.size(); i++) {
511                 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
512                 ScheduleEdge se;
513                 switch(tse.getType()) {
514                 case ScheduleEdge.ASSOCEDGE: {
515                     se = new ScheduleEdge(csNode, "associate", tse.getFstate(), tse.getType(), 0);
516                     se.setProbability(tse.getProbability());
517                     se.setNewRate(tse.getNewRate());
518                     break;
519                 }
520                 default: {
521                     throw new Exception("Error: not valid ScheduleEdge here");
522                 }
523                 }
524                 se.setSourceCNode(tse.getSourceCNode());
525                 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
526                 se.setFEdge(tse.getFEdge());
527                 se.setTargetFState(tse.getTargetFState());
528                 se.setIsclone(true);
529                 ((ScheduleNode)tse.getSource()).addAssociateSEdge(se);
530             }
531             inedges = null;*/
532         } else {
533             sEdge.getTarget().removeInedge(sEdge);
534             sEdge.setTarget(csNode);
535             csNode.getInedgeVector().add(sEdge);
536             sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
537             //sEdge.setTargetFState(null);
538             sEdge.setIsclone(true);
539         }
540         
541         Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
542         Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>(); //clone nodes
543         Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
544         Vector<ScheduleNode> origins = new Vector<ScheduleNode>(); // queue of source ScheduleNode cloned
545         Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
546         clone.add(csNode);
547         toClone.add((ScheduleNode)sEdge.getTarget());
548         origins.addElement((ScheduleNode)sEdge.getTarget());
549         sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
550         qcn2cn.add(cn2cn);
551         while(!toClone.isEmpty()) {
552             Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
553             csNode = clone.poll();
554             ScheduleNode osNode = toClone.poll();
555             cn2cn = qcn2cn.poll();
556             // Clone all the external ScheduleEdges and the following ScheduleNodes
557             Vector edges = osNode.getEdgeVector();
558             for(i = 0; i < edges.size(); i++) {
559                 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
560                 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
561                 scheduleNodes.add(tSNode);
562                 clone.add(tSNode);
563                 toClone.add((ScheduleNode)tse.getTarget());
564                 origins.addElement((ScheduleNode)tse.getTarget());
565                 sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
566                 qcn2cn.add(tocn2cn);
567                 ScheduleEdge se = null;
568                 switch(tse.getType()) {
569                 case ScheduleEdge.NEWEDGE: {
570                     se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getType(), 0);
571                     break;
572                 }
573                 case ScheduleEdge.TRANSEDGE: {
574                     se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), tse.getType(), 0);
575                     break;
576                 }
577                 /*case ScheduleEdge.ASSOCEDGE: {
578                     se = new ScheduleEdge(tSNode, "associate", tse.getFstate(), tse.getType(), 0);
579                     break;
580                 }*/
581                 default: {
582                     throw new Exception("Error: not valid ScheduleEdge here");
583                 }
584                 }
585                 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
586                 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
587                 se.setFEdge(tse.getFEdge());
588                 se.setTargetFState(tse.getTargetFState());
589                 se.setProbability(tse.getProbability());
590                 se.setNewRate(tse.getNewRate());
591                 se.setIsclone(true);
592                 csNode.addEdge(se);
593                 scheduleEdges.add(se);
594             }
595             tocn2cn = null;
596             edges = null;
597         }
598
599         // associate ScheduleEdges
600         /*for(int j = 0; j < origins.size(); ++j) {
601             ScheduleNode osNode = origins.elementAt(i);
602             Vector<ScheduleEdge> edges = osNode.getAssociateSEdges();
603             ScheduleNode csNode = sn2sn.get(osNode);
604             for(i = 0; i < edges.size(); i++) {
605                 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
606                 assert(tse.getType() == ScheduleEdge.ASSOCEDGE);
607                 ScheduleNode tSNode = (ScheduleNode)tse.getTarget();
608                 if(origins.contains(tSNode)) {
609                     tSNode = sn2sn.get(tSNode);
610                 }
611                 ScheduleEdge se = new ScheduleEdge(tSNode, "associate", tse.getFstate(), tse.getType(), 0);
612                 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
613                 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
614                 se.setFEdge(tse.getFEdge());
615                 se.setTargetFState(tse.getTargetFState());
616                 se.setProbability(tse.getProbability());
617                 se.setNewRate(tse.getNewRate());
618                 se.setIsclone(true);
619                 csNode.addAssociateSEdge(se);
620             }
621             tocn2cn = null;
622             edges = null;
623         }*/
624         
625         toClone = null;
626         clone = null;
627         qcn2cn = null;
628         cn2cn = null;
629     }
630     
631     private int calInExeTime(FlagState fs) throws Exception {
632         int exeTime = 0;
633         ClassDescriptor cd = fs.getClassDescriptor();
634         ClassNode cNode = cd2ClassNode.get(cd);
635         exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
636         while(true) {
637             Vector inedges = cNode.getInedgeVector();
638             // Now that there are associate ScheduleEdges, there may be multiple inedges of a ClassNode
639             if(inedges.size() > 1) {
640                 throw new Exception("Error: ClassNode's inedges more than one!");
641             }
642             if(inedges.size() > 0) {
643                 /*ScheduleEdge sEdge = null;
644                 for(int i = 0; i < inedges.size(); ++i) {
645                     sEdge = (ScheduleEdge)inedges.elementAt(i);
646                     if(sEdge.getType() == ScheduleEdge.NEWEDGE) {
647                         break;
648                     }
649                 }*/
650                 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
651                 cNode = (ClassNode)sEdge.getSource();
652                 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
653             }else {
654                 break;
655             }
656             inedges = null;
657         }
658         exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
659         return exeTime;
660     }
661     
662     private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
663         assert(ScheduleEdge.NEWEDGE == se.getType());
664         
665         FEdge fe = se.getFEdge();
666         FlagState fs = (FlagState)fe.getTarget();
667         FlagState nfs = (FlagState)fs.clone();
668         fs.getEdgeVector().removeAllElements();
669         nfs.getInedgeVector().removeAllElements();
670         ClassNode sCNode = se.getSourceCNode();
671         
672         // split the subtree whose root is nfs from the whole flag transition tree
673         Vector<FlagState> sfss = sCNode.getFlagStates();
674         Vector<FlagState> fStates = new Vector<FlagState>();
675         Queue<FlagState> toiterate = new LinkedList<FlagState>();
676         toiterate.add(nfs);
677         fStates.add(nfs);
678         while(!toiterate.isEmpty()){
679             FlagState tfs = toiterate.poll();
680             Iterator it_edges = tfs.edges();
681             while(it_edges.hasNext()) {
682                 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
683                 if(!fStates.contains(temp)) {
684                     fStates.add(temp);
685                     toiterate.add(temp);
686                     sfss.removeElement(temp);
687                 }
688             }
689         }
690         sfss = null;
691         Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
692         fStates = null;
693         // create a ClassNode and ScheduleNode for this subtree
694         ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
695         ScheduleNode sNode = new ScheduleNode(cNode, 0);
696         cNode.setScheduleNode(sNode);
697         cNode.setSorted(true);
698         cNode.setTransTime(sCNode.getTransTime());
699         classNodes.add(cNode);
700         scheduleNodes.add(sNode);
701         try {
702             sNode.calExeTime();
703         } catch (Exception e) {
704             e.printStackTrace();
705         }
706         // flush the exeTime of fs and its ancestors
707         fs.setExeTime(0);
708         toiterate.add(fs);
709         while(!toiterate.isEmpty()) {
710             FlagState tfs = toiterate.poll();
711             int ttime = tfs.getExeTime();
712             Iterator it_inedges = tfs.inedges();
713             while(it_inedges.hasNext()) {
714                 FEdge fEdge = (FEdge)it_inedges.next();
715                 FlagState temp = (FlagState)fEdge.getSource();
716                 int time = fEdge.getExeTime() + ttime;
717                 if(temp.getExeTime() > time) {
718                     temp.setExeTime(time);
719                     toiterate.add(temp);
720                 }
721             }
722         }
723         toiterate = null;
724         
725         // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
726         ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
727         sEdge.setFEdge(fe);
728         sEdge.setSourceCNode(sCNode);
729         sEdge.setTargetCNode(cNode);
730         sEdge.setTargetFState(nfs);
731         // TODO
732         // Add calculation codes for calculating transmit time of an object 
733         sEdge.setTransTime(cNode.getTransTime());
734         se.getSource().addEdge(sEdge);
735         scheduleEdges.add(sEdge);
736         // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
737         ScheduleNode oldSNode = (ScheduleNode)se.getSource();
738         Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
739         Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
740         Vector<ClassNode> rCNodes = new Vector<ClassNode>();
741         rCNodes.addElement(sCNode);
742         if(it_isEdges != null){
743             while(it_isEdges.hasNext()) {
744                 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
745                 if(rCNodes.contains(tse.getSourceCNode())) {
746                     if(sCNode == tse.getSourceCNode()) {
747                         if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
748                             tse.setSource(cNode);
749                             tse.setSourceCNode(cNode);
750                         } else {
751                             continue;
752                         }
753                     }
754                     sNode.getScheduleEdges().addElement(tse);
755                     sNode.getClassNodes().addElement(tse.getTargetCNode());
756                     rCNodes.addElement(tse.getTargetCNode());
757                     oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
758                     toremove.addElement(tse);
759                 }
760             }
761         }
762         oldSNode.getScheduleEdges().removeAll(toremove);
763         toremove.clear();
764         // redirect ScheudleEdges out of this subtree to the new ScheduleNode
765         Iterator it_sEdges = se.getSource().edges();
766         while(it_sEdges.hasNext()) {
767             ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
768             if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
769                 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
770                     tse.setSource(sNode);
771                     tse.setSourceCNode(cNode);
772                     sNode.getEdgeVector().addElement(tse);
773                     toremove.add(tse);
774                 }
775             }
776         }
777         se.getSource().getEdgeVector().removeAll(toremove);
778         toremove = null;
779         sFStates = null;
780         
781         try {
782             if(!copy) {
783                 //merge se into its source ScheduleNode
784                 ((ScheduleNode)se.getSource()).mergeSEdge(se);
785                 scheduleNodes.remove(se.getTarget());
786                 scheduleEdges.removeElement(se);
787                 // As se has been changed into an internal edge inside a ScheduleNode, 
788                 // change the source and target of se from original ScheduleNodes into ClassNodes.
789                 se.setTarget(se.getTargetCNode());
790                 se.setSource(se.getSourceCNode());
791                 se.getTargetCNode().addEdge(se);
792             } else {
793                 handleScheduleEdge(se, true);
794             }
795         } catch (Exception e) {
796             e.printStackTrace();
797             System.exit(-1);
798         }
799         
800         return sNode;
801     }
802     
803     public void schedule() throws Exception {
804         if(this.coreNum == -1) {
805             throw new Exception("Error: un-initialized coreNum when doing scheduling.");
806         }
807         
808         if(this.scheduleGraphs == null) {
809             this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
810         }
811         
812         int reduceNum = this.scheduleNodes.size() - this.coreNum;
813         
814         // Enough cores, no need to merge more ScheduleEdge
815         if(!(reduceNum > 0)) {
816             this.scheduleGraphs.addElement(this.scheduleNodes);
817             int gid = 1;
818             String path = "scheduling_" + gid + ".dot";
819             SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
820         } else {
821             // sort the ScheduleEdges in dececending order of transmittime
822             Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
823             sEdges.addElement(this.scheduleEdges.elementAt(0));
824             for(int i = 1; i < this.scheduleEdges.size(); i++) {
825                 ScheduleEdge temp = this.scheduleEdges.elementAt(i);
826                 int j = sEdges.size() - 1;
827                 do {
828                     if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) {
829                         break;
830                     }
831                 } while(j >= 0);
832                 sEdges.add(j+1, temp);
833             }
834
835             int temp = sEdges.elementAt(reduceNum - 1).getTransTime();
836             for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) {
837                 if(sEdges.elementAt(i).getTransTime() != temp) {
838                     sEdges.removeElementAt(i);
839                 } else {
840                     break;
841                 }
842             }
843             int start = reduceNum - 2;
844             for(; start >= 0; start--) {
845                 if(sEdges.elementAt(start).getTransTime() != temp) {
846                     start++;
847                     reduceNum -= start;
848                     break;
849                 } 
850             }
851             if(start < 0) {
852                 start = 0;
853             }
854
855             // generate scheduling
856             Vector candidates = new Vector();
857             for(int i = start; i < sEdges.size(); i++) {
858                 candidates.addElement(Integer.valueOf(i));
859             }
860             Combination combGen = new Combination(candidates, reduceNum);
861             int gid = 1;
862             do {
863                 Vector toreduce = combGen.next();
864                 if(toreduce != null) {
865                     Vector<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
866                     for(int i = 0; i < start; i++) {
867                         reduceEdges.add(sEdges.elementAt(i));
868                     }
869                     for(int i = 0; i < toreduce.size(); i++) {
870                         reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
871                     }
872                     Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
873                     this.scheduleGraphs.add(sNodes);
874                     reduceEdges = null;
875                     sNodes = null;
876                 } else {
877                     break;
878                 }
879                 toreduce = null;
880             }while(true);
881             sEdges = null;
882             candidates = null;
883
884         }
885         
886         if(this.schedulings == null) {
887             this.schedulings = new Vector<Vector<Schedule>>();
888         }
889         
890         Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
891         Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator();
892         while(it_tasks.hasNext()) {
893             TaskDescriptor td = (TaskDescriptor)it_tasks.next();
894             if(td.numParameters() > 1) {
895                 multiparamtds.addElement(td);
896             }
897         }
898         
899         for(int i = 0; i < this.scheduleGraphs.size(); i++) {
900             Hashtable<TaskDescriptor, Vector<Schedule>> td2cores = new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks reside on which cores
901             Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
902             Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
903             // for each ScheduleNode create a schedule node representing a core
904             Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
905             int j = 0;
906             for(j = 0; j < scheduleGraph.size(); j++) {
907                 sn2coreNum.put(scheduleGraph.elementAt(j), j);
908             }
909             int startupcore = 0;
910             boolean setstartupcore = false;
911             Schedule startup = null;
912             Vector<Integer> leafcores = new Vector<Integer>();
913             Vector[] ancestorCores = new Vector[this.coreNum];
914             for(j = 0; j < ancestorCores.length; ++j) {
915                 ancestorCores[j] = new Vector();
916             }
917             for(j = 0; j < scheduleGraph.size(); j++) {
918                 Schedule tmpSchedule = new Schedule(j);
919                 ScheduleNode sn = scheduleGraph.elementAt(j);
920                 
921                 Vector<ClassNode> cNodes = sn.getClassNodes();
922                 for(int k = 0; k < cNodes.size(); k++) {
923                     Iterator it_flags = cNodes.elementAt(k).getFlags();
924                     while(it_flags.hasNext()) {
925                         FlagState fs = (FlagState)it_flags.next();
926                         Iterator it_edges = fs.edges();
927                         while(it_edges.hasNext()) {
928                             TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
929                             tmpSchedule.addTask(td);
930                             if(td.numParameters() > 1) {
931                                 if(!td2cores.containsKey(td)) {
932                                     td2cores.put(td, new Vector<Schedule>());
933                                 }
934                                 Vector<Schedule> tmpcores = td2cores.get(td);
935                                 if(!tmpcores.contains(tmpSchedule)) {
936                                     tmpcores.add(tmpSchedule);
937                                 }
938                                 tmpSchedule.addFState4TD(td, fs);
939                             }
940                             if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
941                                 assert(!setstartupcore);
942                                 startupcore = j;
943                                 startup = tmpSchedule;
944                                 setstartupcore = true;
945                             }
946                         }
947                     }
948                 }
949
950                 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
951                 Iterator it_edges = sn.edges();
952                 if(!it_edges.hasNext()) {
953                     // leaf core, considered as ancestor of startup core
954                     if(!leafcores.contains(Integer.valueOf(j))) {
955                         leafcores.addElement(Integer.valueOf(j));
956                     }
957                 }
958                 while(it_edges.hasNext()) {
959                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
960                     ScheduleNode target = (ScheduleNode)se.getTarget();
961                     Integer targetcore = sn2coreNum.get(target);
962                     switch(se.getType()) {
963                     case ScheduleEdge.NEWEDGE: {
964                         for(int k = 0; k < se.getNewRate(); k++) {
965                             tmpSchedule.addTargetCore(se.getFstate(), targetcore);
966                         }
967                         break;
968                     }
969                     case ScheduleEdge.TRANSEDGE: {
970                         // 'transmit' edge
971                         tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
972                         // check if missed some FlagState associated with some multi-parameter 
973                         // task, which has been cloned when splitting a ClassNode
974                         FlagState fs = se.getSourceFState();
975                         FlagState tfs = se.getTargetFState();
976                         Iterator it = tfs.edges();
977                         while(it.hasNext()) {
978                             TaskDescriptor td = ((FEdge)it.next()).getTask();
979                             if(td.numParameters() > 1) {
980                                 if(tmpSchedule.getTasks().contains(td)) {
981                                     tmpSchedule.addFState4TD(td, fs);
982                                 }
983                             }
984                         }
985                         break;
986                     }
987                     /*case ScheduleEdge.ASSOCEDGE: {
988                         //TODO
989                         +
990                     }*/
991                     }
992                     tmpSchedule.addChildCores(targetcore);
993                     if((targetcore.intValue() != j) && (!ancestorCores[targetcore.intValue()].contains((Integer.valueOf(j))))) {
994                         ancestorCores[targetcore.intValue()].addElement(Integer.valueOf(j));
995                     }
996                 }
997                 it_edges = sn.getScheduleEdgesIterator();
998                 while(it_edges.hasNext()) {
999                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
1000                     switch(se.getType()) {
1001                     case ScheduleEdge.NEWEDGE: {
1002                         for(int k = 0; k < se.getNewRate(); k++) {
1003                             tmpSchedule.addTargetCore(se.getFstate(), j);
1004                         }
1005                         break;
1006                     }
1007                     case ScheduleEdge.TRANSEDGE: {
1008                         // 'transmit' edge
1009                         tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
1010                         break;
1011                     }
1012                     /*case ScheduleEdge.ASSOCEDGE: {
1013                         //TODO
1014                         +
1015                     }*/
1016                     }
1017                 }
1018                 scheduling.add(tmpSchedule);
1019             }       
1020             
1021             leafcores.removeElement(Integer.valueOf(startupcore));
1022             ancestorCores[startupcore] = leafcores;
1023             int number = this.coreNum;
1024             if(scheduling.size() < number) {
1025                 number = scheduling.size();
1026             }
1027             for(j = 0; j < number; ++j) {
1028                 scheduling.elementAt(j).setAncestorCores(ancestorCores[j]);
1029             }
1030             
1031             // set up all the associate ally cores
1032             if(multiparamtds.size() > 0) {              
1033                 Object[] tds = (td2cores.keySet().toArray());
1034                 for(j = 0; j < tds.length; ++j) {
1035                     TaskDescriptor td = (TaskDescriptor)tds[j];
1036                     Vector<Schedule> cores = td2cores.get(td);
1037                     if(cores.size() == 1) {
1038                         continue;
1039                     }
1040                     for(int k = 0; k < cores.size(); ++k) {
1041                         Schedule tmpSchedule = cores.elementAt(k);
1042                         Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
1043                         for(int h = 0; h < tmpfss.size(); ++h) {
1044                             for(int l = 0; l < cores.size(); ++l) {
1045                                 if(l != k) {
1046                                     tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum());
1047                                 }
1048                             }
1049                         }
1050                     }
1051                 }
1052             }
1053             
1054             this.schedulings.add(scheduling);
1055         }
1056         
1057     }
1058     
1059     public Vector<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
1060         Vector<ScheduleNode> result = new Vector<ScheduleNode>();
1061
1062         // clone the ScheduleNodes
1063         Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
1064         Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
1065         for(int i = 0; i < this.scheduleNodes.size(); i++) {
1066             Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
1067             ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
1068             ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
1069             result.add(i, temp);
1070             sn2hash.put(temp, cn2cn);
1071             sn2sn.put(tocopy, temp);
1072             cn2cn = null;
1073         }
1074         // clone the ScheduleEdges and merge those in reduceEdges at the same time
1075         Vector<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
1076         for(int i = 0; i < this.scheduleEdges.size(); i++) {
1077             ScheduleEdge sse = this.scheduleEdges.elementAt(i);
1078             ScheduleNode csource = sn2sn.get(sse.getSource());
1079             ScheduleNode ctarget = sn2sn.get(sse.getTarget());
1080             Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
1081             Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
1082             ScheduleEdge se =  null;
1083             switch(sse.getType()) {
1084             case ScheduleEdge.NEWEDGE: {
1085                 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
1086                 se.setProbability(sse.getProbability());
1087                 se.setNewRate(sse.getNewRate());
1088                 break;
1089             } 
1090             case ScheduleEdge.TRANSEDGE: {
1091                 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
1092                 break;
1093             }
1094             /*case ScheduleEdge.ASSOCEDGE: {
1095                 //TODO
1096                 se = new ScheduleEdge(ctarget, "associate", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
1097                 break;
1098             }*/
1099             }
1100             se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
1101             se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
1102             se.setFEdge(sse.getFEdge());
1103             se.setTargetFState(sse.getTargetFState());
1104             se.setIsclone(true);
1105             csource.addEdge(se);
1106             if(reduceEdges.contains(sse)) {
1107                 toMerge.add(se);
1108             } 
1109             sourcecn2cn = null;
1110             targetcn2cn = null;
1111         }
1112         sn2hash = null;
1113         sn2sn = null;
1114         
1115         for(int i = 0; i < toMerge.size(); i++) {
1116             ScheduleEdge sEdge = toMerge.elementAt(i);
1117             // merge this edge
1118             switch(sEdge.getType()) {
1119             case ScheduleEdge.NEWEDGE: {
1120                 try {
1121                     ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
1122                 } catch(Exception e) {
1123                     e.printStackTrace();
1124                     System.exit(-1);
1125                 }
1126                 break;
1127             } 
1128             case ScheduleEdge.TRANSEDGE: {
1129                 try {
1130                     ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
1131                 } catch(Exception e) {
1132                     e.printStackTrace();
1133                     System.exit(-1);
1134                 }
1135                 break;
1136             }
1137             /*case ScheduleEdge.ASSOCEDGE: {
1138                 // TODO
1139                 +
1140             }*/
1141             }
1142             result.removeElement(sEdge.getTarget());
1143             if(ScheduleEdge.NEWEDGE == sEdge.getType()) {
1144                 // As se has been changed into an internal edge inside a ScheduleNode, 
1145                 // change the source and target of se from original ScheduleNodes into ClassNodes.
1146                 sEdge.setTarget(sEdge.getTargetCNode());
1147                 sEdge.setSource(sEdge.getSourceCNode());
1148                 sEdge.getTargetCNode().addEdge(sEdge);
1149             } 
1150         }
1151         toMerge = null;
1152         
1153         String path = "scheduling_" + gid + ".dot";
1154         SchedulingUtil.printScheduleGraph(path, result);
1155         
1156         return result;
1157     }
1158     
1159     class Combination{
1160         Combination tail;
1161         Object head;
1162         Vector factors;
1163         int selectNum;
1164         int resultNum;
1165         
1166         public Combination(Vector factors, int selectNum) throws Exception{
1167             this.factors = factors;
1168             if(factors.size() < selectNum) {
1169                 throw new Exception("Error: selectNum > candidates' number in combination.");
1170             }
1171             if(factors.size() == selectNum) {
1172                 this.resultNum = 1;
1173                 head = null;
1174                 tail = null;
1175                 return;
1176             } 
1177             this.head = this.factors.remove(0);
1178             if(selectNum == 1) {
1179                 this.resultNum = this.factors.size() + 1;
1180                 this.tail = null;
1181                 return;
1182             }   
1183             this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1184             this.selectNum = selectNum;
1185             this.resultNum = 1;
1186             for(int i = factors.size(); i > selectNum; i--) {
1187                 this.resultNum *= i;
1188             }
1189             for(int i = factors.size() - selectNum; i > 0; i--) {
1190                 this.resultNum /= i;
1191             }
1192         }
1193         
1194         public Vector next() {
1195             if(resultNum == 0) {
1196                 return null;
1197             }
1198             if(head == null) {
1199                 resultNum--;
1200                 Vector result = this.factors;
1201                 return result;
1202             }
1203             if(this.tail == null) {
1204                 resultNum--;
1205                 Vector result = new Vector();
1206                 result.add(this.head);
1207                 if(resultNum != 0) {
1208                     this.head = this.factors.remove(0);
1209                 }
1210                 return result;
1211             }
1212             Vector result = this.tail.next();
1213             if(result == null) {
1214                 if(this.factors.size() == this.selectNum) {
1215                     this.head = null;
1216                     this.tail = null;
1217                     result = this.factors;
1218                     this.resultNum--;
1219                     return result;
1220                 }
1221                 this.head = this.factors.remove(0);
1222                 try {
1223                     this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1224                     result = this.tail.next();
1225                 } catch(Exception e) {
1226                     e.printStackTrace();
1227                 }
1228                 
1229             }
1230             result.add(0, head);
1231             resultNum--;
1232             return result;
1233         }
1234     }
1235 }