Fix a bug in scheduling search algorithm: it can not find the best scheduling for...

diff --git a/Robust/src/Analysis/Scheduling/CombinationUtil.java b/Robust/src/Analysis/Scheduling/CombinationUtil.java
index cc68fa4a67dcbbd8d771654a47276a0b484f53d3..4356cbfaecccfb7a9d81a44751ea55f22113771c 100644 (file)
--- a/Robust/src/Analysis/Scheduling/CombinationUtil.java
+++ b/Robust/src/Analysis/Scheduling/CombinationUtil.java
@@ -31,7 +31,8 @@ public class CombinationUtil {
     Vector<Vector<ScheduleNode>> rootNodes;
     int rootNum;
 
-    public RootsGenerator(Vector<Vector<ScheduleNode>> snodevecs, int rootNum) {
+    public RootsGenerator(Vector<Vector<ScheduleNode>> snodevecs, 
+                         int rootNum) {
       this.sNodeVecs = snodevecs;
       this.rootNum = rootNum;
       this.node2Combine = null;
@@ -79,7 +80,7 @@ public class CombinationUtil {
        trial = trial(num2choose, next);
       }
       if(trial) {
-       // left nodes are all to be combined
+       // remaining nodes are all to be combined
        this.node2Combine = new Vector<Vector<ScheduleNode>>();
        int next = 1;
        int index = 0;
@@ -125,7 +126,8 @@ public class CombinationUtil {
       return trial;
     }
 
-    private boolean trial(int num2choose, int next) {
+    private boolean trial(int num2choose, 
+                         int next) {
       int index = 0;
       boolean first = true;
       while(num2choose > 0) {
@@ -185,7 +187,8 @@ public class CombinationUtil {
     int[] lastchoices;
     boolean first4choice;
 
-    public CombineGenerator(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<ScheduleNode>> node2combine) {
+    public CombineGenerator(Vector<Vector<ScheduleNode>> rootnodes, 
+                           Vector<Vector<ScheduleNode>> node2combine) {
       this.rootNodes = rootnodes;
       this.node2Combine = node2combine;
       this.rootNStates = new Vector<Vector<int[]>>();
@@ -282,7 +285,8 @@ public class CombinationUtil {
       return suc;
     }
 
-    private boolean firstexpand(int next, boolean first) {
+    private boolean firstexpand(int next, 
+                               boolean first) {
       for(int i = next; i < this.node2Combine.size(); i++) {
        if(this.node2Combine.elementAt(i) != null) {
          int choice = this.lastchoices[i];
@@ -308,7 +312,8 @@ public class CombinationUtil {
       return true;
     }
 
-    private boolean innertrial(int next, int layer) {
+    private boolean innertrial(int next, 
+                              int layer) {
       if((this.combine.elementAt(next) == null) ||
          (this.combine.elementAt(next).size() < 2)) {
        // skip over empty buckets and bucket with only one obj ( make sure
@@ -463,7 +468,11 @@ public class CombinationUtil {
       }
     }
 
-    private boolean propagateOne(int next, int rooti, int indexi, int ti, Combine tmp) {
+    private boolean propagateOne(int next, 
+                                int rooti, 
+                                int indexi, 
+                                int ti, 
+                                Combine tmp) {
       int root = rooti;
       int index = indexi;
       int t = ti;

diff --git a/Robust/src/Analysis/Scheduling/MCImplSynthesis.java b/Robust/src/Analysis/Scheduling/MCImplSynthesis.java
index 2d4a9d31e0c0641149f48091b7922371c30bd846..1bcb287915492ab40efbde064ff3cb16b389d67f 100644 (file)
--- a/Robust/src/Analysis/Scheduling/MCImplSynthesis.java
+++ b/Robust/src/Analysis/Scheduling/MCImplSynthesis.java
@@ -4,6 +4,7 @@ import java.io.FileOutputStream;
 import java.io.PrintStream;
 import java.util.Hashtable;
 import java.util.Iterator;
+import java.util.Random;
 import java.util.Vector;
 
 import Analysis.OwnershipAnalysis.OwnershipAnalysis;
@@ -25,6 +26,7 @@ public class MCImplSynthesis {
     
     int coreNum;
     int scheduleThreshold;
+    int probThreshold;
 
     public MCImplSynthesis(State state, 
                           TaskAnalysis ta,
@@ -40,6 +42,7 @@ public class MCImplSynthesis {
                                                       state,
                                                       ta);
        this.scheduleThreshold = 1000;
+       this.probThreshold = 0;
     }
 
     public int getCoreNum() {
@@ -54,6 +57,14 @@ public class MCImplSynthesis {
         this.scheduleThreshold = scheduleThreshold;
     }
 
+    public int getProbThreshold() {
+        return probThreshold;
+    }
+
+    public void setProbThreshold(int probThreshold) {
+        this.probThreshold = probThreshold;
+    }
+
     public Vector<Schedule> synthesis() {
        // Print stuff to the original output and error streams.
        // The stuff printed through the 'origOut' and 'origErr' references
@@ -118,6 +129,7 @@ public class MCImplSynthesis {
 
        int tryindex = 1;
        int bestexetime = Integer.MAX_VALUE;
+       Random rand = new Random();
        // simulate the generated schedulings and try to optimize it
        do {
            System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
@@ -144,6 +156,13 @@ public class MCImplSynthesis {
                System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
                System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
                tryindex++;
+           } else if(tmpexetime == bestexetime) {
+               System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
+               System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+               tryindex++;
+               if((Math.abs(rand.nextInt()) % 100) < this.probThreshold) {
+                   break;
+               }
            } else {
                break;
            }
@@ -163,7 +182,7 @@ public class MCImplSynthesis {
        selectedSimExeGraphs = null;
        multiparamtds = null;
        
-       String path = "scheduling_selected.dot";
+       String path = this.state.outputdir + "scheduling_selected.dot";
        SchedulingUtil.printScheduleGraph(path, schedulinggraph);
 
        // Close the streams.
@@ -190,18 +209,12 @@ public class MCImplSynthesis {
        Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
        int lgid = gid;
        int left = count;
-       int num2try = (gid - 1) / this.scheduleThreshold;
 
        for(int i = 0; i < selectedScheduleGraphs.size(); i++) {
            Vector<ScheduleNode> schedulegraph = scheduleGraphs.elementAt(
                    selectedScheduleGraphs.elementAt(i));
            Vector<SimExecutionEdge> simexegraph = selectedSimExeGraphs.elementAt(i);
            Vector<SimExecutionEdge> criticalPath = analyzeCriticalPath(simexegraph); 
-           // for test, print out the criticalPath
-           if(this.state.PRINTCRITICALPATH) {
-               SchedulingUtil.printCriticalPath("criticalpath_" + num2try + ".dot", criticalPath);
-           }
-           num2try++;
            Vector<Vector<ScheduleNode>> tmposchedulegraphs = optimizeCriticalPath(schedulegraph, 
                                                                                   criticalPath,
                                                                                   lgid,
@@ -321,6 +334,12 @@ public class MCImplSynthesis {
        int lgid = gid;
        int left = count;
        
+       // for test, print out the criticalPath
+       if(this.state.PRINTCRITICALPATH) {
+           SchedulingUtil.printCriticalPath(this.state.outputdir + "criticalpath_" + lgid + ".dot", 
+                                            criticalPath);
+       }
+       
        // first check all seedges whose real start point is late than predicted
        // earliest start time and group them
        int opcheckpoint = Integer.MAX_VALUE;
@@ -338,13 +357,30 @@ public class MCImplSynthesis {
                seedge.setFixedTime(false);
                // consider to optimize it only when its predicates can NOT 
                // be optimized, otherwise first considering optimize its predicates
-               if(seedge.getLastpredicateEdge().isFixedTime()) {
+               SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
+               if(lastpredicateedge.isFixedTime()) {
                    if(opcheckpoint >= starttime) {
                        // only consider the tasks with smallest best start time
                        if(opcheckpoint > starttime) {
                            tooptimize.clear();
                            opcheckpoint = starttime;
-                           sparecores = seedge.getLastpredicateNode().getSpareCores();
+                           SimExecutionNode lastpredicatenode = seedge.getLastpredicateNode();
+                           int timepoint = lastpredicatenode.getTimepoint();
+                           if(lastpredicateedge.getTd() == null) {
+                               // transfer edge
+                               timepoint += lastpredicateedge.getWeight();
+                           }
+                           // mapping to critical path
+                           for(int index = 0; index < criticalPath.size(); index++) {
+                               SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
+                               SimExecutionNode tmpsenode = 
+                                   (SimExecutionNode)tmpseedge.getTarget();
+                               if(tmpsenode.getTimepoint() > timepoint) {
+                                   // get the spare core info
+                                   sparecores = tmpsenode.getSpareCores();
+                                   break;
+                               }
+                           }
                        }
                        int corenum = seedge.getCoreNum();
                        if(!tooptimize.containsKey(corenum)) {
@@ -400,6 +436,7 @@ public class MCImplSynthesis {
                            tooptimize2.put(corenum, candidatetasks);
                            Vector<Vector<ScheduleNode>> ops = innerOptimizeCriticalPath(scheduleGraph,
                                                                                          tooptimize2,
+                                                                                         null,
                                                                                          lgid,
                                                                                          left);
                            if(ops != null) {
@@ -478,6 +515,7 @@ public class MCImplSynthesis {
                // cores
                Vector<Vector<ScheduleNode>> ops = innerOptimizeCriticalPath(scheduleGraph,
                                                                              tooptimize,
+                                                                             sparecores,
                                                                              lgid,
                                                                              left);
                if(ops != null) {
@@ -498,6 +536,7 @@ public class MCImplSynthesis {
     
     private Vector<Vector<ScheduleNode>> innerOptimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
                                                                   Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>> tooptimize,
+                                                                  Vector<Integer> sparecores,
                                                                   int gid,
                                                                   int count) {
        int lgid = gid;
@@ -511,7 +550,9 @@ public class MCImplSynthesis {
        // these nodes are root nodes
        Vector<ScheduleNode> roots = new Vector<ScheduleNode>();
        for(int i = 0; i < newscheduleGraph.size(); i++) {
-           roots.add(newscheduleGraph.elementAt(i));
+           if((sparecores == null) || (sparecores.contains(i))) {
+               roots.add(newscheduleGraph.elementAt(i));
+           }
        }
 
        // map the tasks associated to SimExecutionedges to original 

diff --git a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java
index 5a4a766f912f410f5e2ceea293ceb12cb0e2f462..9471e6514de2d067b073489ac9a13eb9a545cee7 100644 (file)
--- a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java
+++ b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java
@@ -581,7 +581,7 @@ public class ScheduleAnalysis {
        toVisit = null;
 
        if(this.state.PRINTSCHEDULING) {
-           SchedulingUtil.printScheduleGraph("scheduling_ori.dot", 
+           SchedulingUtil.printScheduleGraph(this.state.outputdir + "scheduling_ori.dot", 
                                              this.scheduleNodes);
        }
     }
@@ -755,7 +755,8 @@ public class ScheduleAnalysis {
        sn2fes = null;
 
        if(this.state.PRINTSCHEDULING) {
-           SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
+           SchedulingUtil.printScheduleGraph(this.state.outputdir + "scheduling_extend.dot", 
+                                             this.scheduleNodes);
        }
     }
 
@@ -1132,10 +1133,12 @@ public class ScheduleAnalysis {
            this.scheduleGraphs.addElement(this.scheduleNodes);
            int gid = 1;
            if(this.state.PRINTSCHEDULING) {
-               String path = "scheduling_" + gid + ".dot";
+               String path = this.state.outputdir + "scheduling_" + gid + ".dot";
                SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
            }
        } else {
+           SchedulingUtil.assignCids(this.scheduleNodes);
+           
            // Go through all the Schedule Nodes, organize them in order of their cid
            Vector<Vector<ScheduleNode>> sNodeVecs = 
                SchedulingUtil.rangeScheduleNodes(this.scheduleNodes);

diff --git a/Robust/src/Analysis/Scheduling/ScheduleSimulator.java b/Robust/src/Analysis/Scheduling/ScheduleSimulator.java
index 190fe93995519ba774487bde8d33816ca166e118..e8b7565e416c175923b368ded98c9fe6971a89b8 100644 (file)
--- a/Robust/src/Analysis/Scheduling/ScheduleSimulator.java
+++ b/Robust/src/Analysis/Scheduling/ScheduleSimulator.java
@@ -101,7 +101,7 @@ public class ScheduleSimulator {
              this.setScheduling(scheduling);
              Vector<SimExecutionEdge> simexegraph = new Vector<SimExecutionEdge>();
              Vector<CheckPoint> checkpoints = new Vector<CheckPoint>();
-             int tmpTime = this.process(checkpoints, simexegraph);
+             int tmpTime = process(checkpoints, simexegraph);
              if(tmpTime < processTime) {
                  selectedScheduling.clear();
                  selectedScheduling.add(index);
@@ -425,7 +425,7 @@ public class ScheduleSimulator {
 
     int gid = this.scheduling.elementAt(0).getGid();
     if(this.state.PRINTSCHEDULESIM) {
-       SchedulingUtil.printSimulationResult("SimulatorResult_" + gid + ".dot", 
+       SchedulingUtil.printSimulationResult(this.state.outputdir + "SimulatorResult_" + gid + ".dot", 
                                             this.processTime,
                                             this.coreNum, 
                                             checkpoints);
@@ -716,7 +716,7 @@ public class ScheduleSimulator {
          }
       } else if(tttasks.size() > 0) {
          SimExecutionNode seNode = new SimExecutionNode(corenum, this.processTime);
-         seNode.setSpareCores(cp.getSpareCores());
+         //seNode.setSpareCores(cp.getSpareCores());
          // no action associated here
          SimExecutionNode lastsenode = lastseNodes[corenum];
          // create edges between previous senode on this core to this node

diff --git a/Robust/src/Analysis/Scheduling/SchedulingUtil.java b/Robust/src/Analysis/Scheduling/SchedulingUtil.java
index 6ba8c8930d8cb9fe79db980b3f88a91406a42420..2728af34e6a04d8b1bcae6d7770a24bcc634b689 100644 (file)
--- a/Robust/src/Analysis/Scheduling/SchedulingUtil.java
+++ b/Robust/src/Analysis/Scheduling/SchedulingUtil.java
@@ -89,7 +89,7 @@ public class SchedulingUtil {
        sn2sn = null;
 
        if(state.PRINTSCHEDULING) {
-           String path = "scheduling_" + gid + ".dot";
+           String path = state.outputdir + "scheduling_" + gid + ".dot";
            SchedulingUtil.printScheduleGraph(path, result);
        }
 
@@ -170,13 +170,31 @@ public class SchedulingUtil {
        
        for(int i = 0; i < scheduleNodes.size(); i++) {
            ScheduleNode tmpn = scheduleNodes.elementAt(i);
-           int index = tmpn.getCid();
+           int tmpcid = tmpn.getCid();
+           int index = 0;
+           for(index = 0; index < sNodeVecs.size(); index++) {
+               if(sNodeVecs.elementAt(index).elementAt(0).getCid() > tmpcid) {
+                   // find the place to insert
+                   sNodeVecs.add(sNodeVecs.lastElement());
+                   for(int j = sNodeVecs.size() - 2; j > index; j--) {
+                       sNodeVecs.setElementAt(sNodeVecs.elementAt(j - 1), j);
+                   }
+                   sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);
+               } else if(sNodeVecs.elementAt(index).elementAt(0).getCid() == tmpcid) {
+                   break;
+               }
+           }
+           if(index == sNodeVecs.size()) {
+               sNodeVecs.add(new Vector<ScheduleNode>());
+           }
+           
+           /*int index = tmpcid;
            while(sNodeVecs.size() <= index) {
                sNodeVecs.add(null);
            }
            if(sNodeVecs.elementAt(index) == null) {
                sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);
-           }
+           }*/
            sNodeVecs.elementAt(index).add(tmpn);
        }
        

diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java
index 1419a507db62140e67247d3f4b1c620b6fba2ff4..3b9288fc78786baff41d3215adc9fac0dfb48c25 100644 (file)
--- a/Robust/src/IR/State.java
+++ b/Robust/src/IR/State.java
@@ -78,7 +78,7 @@ public class State {
   public int CORENUM = 1;
   public String structfile;
   public String main;
-  public String outputdir = null;
+  public String outputdir = "/scratch/";
 
   public HashSet selfloops;
   public HashSet excprefetch;

diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java
index d96a977259982af2e6bcd50ea8f6b74378e5ea8c..1450b9750ca8bcd085e3ebf4d3c1458e36d72239 100644 (file)
--- a/Robust/src/Main/Main.java
+++ b/Robust/src/Main/Main.java
@@ -272,6 +272,7 @@ public class Main {
                                                              ta,
                                                              oa);
        mcImplSynthesis.setScheduleThreshold(50);
+       mcImplSynthesis.setProbThreshold(0);
        Vector<Schedule> scheduling = mcImplSynthesis.synthesis();
        
        // generate multicore codes