DOC PREVIEW
CMU CS 15745 - matts_carstens_checkpoint

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

CMU CS 15745 - matts_carstens_checkpoint

Documents in this Course
Lecture

Lecture

14 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

5 pages

Lecture

Lecture

6 pages

lecture

lecture

17 pages

Lecture 3

Lecture 3

12 pages

Lecture

Lecture

17 pages

Lecture

Lecture

18 pages

lecture

lecture

14 pages

lecture

lecture

8 pages

lecture

lecture

5 pages

Lecture

Lecture

19 pages

lecture

lecture

10 pages

Lecture

Lecture

20 pages

Lecture

Lecture

8 pages

Lecture

Lecture

7 pages

lecture

lecture

59 pages

Lecture

Lecture

10 pages

Task 2

Task 2

2 pages

Handout

Handout

18 pages

Load more
Download matts_carstens_checkpoint
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view matts_carstens_checkpoint and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view matts_carstens_checkpoint 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?