Homework 2: Dynamic Instruction Scheduling

Due: Sunday, February 20 at 11:59pm via Catalyst

Questions about this assignment should go to Adrian the TA (asampson@cs).

Background

Dr. Chip D. Signer has been put in charge of designing a new dynamically scheduled processor for his employer. In order to know how to best utilize on-chip resources, Dr. Signer wants to understand a few things about the workloads that will be running on his new chip. Dr. Signer wants to simulate these workloads on an ideal machine with infinite resources, to see how many resources these workloads require. In particular, he wants to know, for a given program (i.e. stream of instructions):

• how many clock ticks it would take to run the program given infinite resources, assuming that each instruction (insn) takes 1 tick
• the maximum number of insns that execute in parallel, to know how wide to make the datapath
• the minimum number of physical registers needed by the program for it to run as quickly as possible, to know how large to make the register file

Since this is a dynamically scheduled processor, the register operands of each insn need to be renamed before the insns can be scheduled. In order to know which physical registers are free and which are still live, you must track the live-range of each physical register p. This range starts as soon as p is used for the first time, and ends after p's corresponding architectural register a is overwritten, as any subsequent uses of a should be routed to the new physical register responsible for storing a. p is then free to be reallocated to hold the value for some new architectural register.

Assignment

Your assignment is to write code that takes an insn stream, and performs register renaming and then scheduling of those insns on an infinite machine. After you have the insn schedule, you can answer Dr. Signer's 3 questions above.

Renaming Walkthrough

To help explain how renaming interacts with parallel OoO execution, here is a diagram showing how renaming works on a complicated insn trace.

This diagram walks through a modified version of random-3ticks-3width-4pregs.insns (included with the assignment), which has RAW, WAW and WAR data dependences. It shows how to optimally rename the trace, with an added insn F to make things more interesting.

A few things we can observe:

Since insns B, C and E all execute in cycle 2, they each need a distinct physical register for their output to avoid WAW conflicts. Some of these registers are then dead in the next cycle: e.g., blue is dead (since it's been overwritten by green in insn C) and so can be used in cycle 3 to store the output from insn D.

Keeping track of when a register is free can be tricky, as insn E shows. Data dependences allow it to execute in cycle 2, but we have to make sure that insn D gets the right value for architectural register 1 (from green), so insn E writes into orange, avoiding a WAR conflict. Since E overwrote architectural register 1, the value in green is dead. But we can't free green yet, because D needs to read from green "in the future". This is where OoO execution complicates renaming: all insns get renamed in-order (the light blue arrows), even though they may execute OoO if their data dependences (black arrows) allow.

This situation actually arises in other places, too, but some traces have not really required precise management of the free list. E.g., even in this trace, it's straightforward to rename insns A-D: the blue register always could be (incorrectly) set as "free immediately" and things would work ok, because of the data dependences. Once we add insns E and F, we're not so lucky: we can't let insn F write to green, as this would interfere with insn D which executes at the same time. So we need an extra physical register, yellow, to allow things to execute as quickly as possible.

Files

Download the Python files you need for this assignment.

You can run the code for this assignment with the command python ilp_scheduler.py in your Windows, Mac or Linux command terminal. You may need to install Python first, go here to download it. Be sure to install Python 2.x; this code will likely not work with Python 3.x.

You should ensure your code works for the included insn trace files (*.insns). We will test your code on these traces as well as others that we generate randomly, so you should test using the random insn trace generator yourself as well.

Turnin

You should submit your modified version of ilp_scheduler.py.

The formatting of the output of ilp_scheduler.py should be kept intact so our grading scripts will work, though you can otherwise change the code to your heart's content. We will test your code by calling main() with one of our insn streams and expect output on stdout; as long as you maintain this interface your code will work fine with our tests.