Due: Apr 26 via Canvas.

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 (region of execution between dispatch of the instruction that allocated the register, and the retirement of the instruction that writes to the same logical register) 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.

Simplifying Assumptions

There are a number of simplifying assumptions in this assignment to make your life easier.

• All insns have an execution latency of 1
• Insns communicate exclusively through registers; there are no memory dependences
• You're scheduling insns on an infinite machine, so you never have to worry about resource conflicts
• You do have to worry about the live-ranges of registers, so that you can use registers as efficiently as possible
• We've provided a random insn-trace generator (genInsns()) to make it easier for you to test your code
• For all insn traces, you can assume that only register 0 is live at the beginning. Insns will only ever consume input from live registers, though they may output to arbitrary registers (causing the output register to become live going forward).

The format for insns is documented at the top of ilp_scheduler.py. Each insn is a simple Python dictionary.

Our solution added about 70 lines of Python to ilp_scheduler.py.

Renaming Walkthrough

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 files you need for this assignment: hw2-ilp-scheduler.tar.gz.

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; it's easy to download and install. Be sure to install Python 2.x; this code will not work with the new syntax of 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 to Canvas.

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.

---

Thank you to Adrian Sampson who designed and created the first version of this assignment.