An Integer Programming Approach to Instruction SchedulingObjectiveOptimization & ConstraintsFormulation SourceInteger Programming FormulationConstraints: Instruction Executed OnceConstraints: ResourceConstraints: Data DependencePreliminary resultsSlide 10Slide 11Slide 12An Integer Programming Approach to Instruction SchedulingMatt StreeterCarsten SchwickingObjective•To use integer programming to obtain optimal instruction schedules•Assume partioning has already been done (copies inserted, etc.)Optimization & Constraints•Optimize schedule length •Constraints –Single execution (of each instruction)–Resource–Data dependence•Not yet dealing with crossbar constraintFormulation Source•Daniel Kaestner and Sebastian Winkel. “ILP-based Instruction Scheduling for IA-64,” in LCTES 2001.•Used a real multiple issue architecture•IA-64 has VLIW characteristicsInteger Programming Formulation•Define a variable for each possible instruction, start time, and function unit tuple•Xkm t {0,1}–m = instruction id–t = start time (cycle #)–k = execution unit #Constraints:Instruction Executed Once € xntk=1t∑k∑∀nConstraints:Resource•Rk = # of execution units of type k•R(n) = all possible execution units for n € xntk≤Rkn:k∈R(n)∑∀t,RConstraints:Data Dependence•where n must not execute until m finishes € t *xmtk+latency(m)≤t∑k∑t *xntkt∑k∑Preliminary results•Generated random data dependency trees•Each node has degree chosen uniformly at random from {0, 1, 2, 3}; durations chosen from {1, 2, 3, 4}; function unit assigned at random•4 function units, one of each type•Maximum height H (=6 here)Preliminary results•Optimal scheduling only feasible for basic blocks of ~10 instructions•An alternative is to search for locally optimal schedulesPreliminary results•Use simple heuristic (list scheduling) to generate a “center” schedule•Until 10 seconds have elapsed:–For r from 1 to rmax do:•Generate optimal schedule subject to the constraint that the cycle assigned to each instruction is within a distance r of the cycle assigned by the center schedulePreliminary results051015202530[0,4] [5,9] [10,14] [15,19] [20,24] [25,29] [30,34] [35,39] [40,44] [45,49] [50,54] [55,59]Number of instructionsSchedule lengthList schedulesIP
View Full Document