---

CS 415: Compilers
Spring 2014, Project 1
Local Instruction Scheduling
Due date code: Tuesday, February 25, at 11:59pm EST
Due date report: Tuesday, March 4, at 11:59pm EST

---

Modifications and Clarifications

• The project does not expect you to analyse accesses to memory. In order to generate correct code, instructions that read from main memory should not be moved across instructions that write to main memory.
• You can use any language, but we mainly provide help for C/C++ implementations.
• Your schedulers are only allowed to change the order of the instructions in the input basic block. Your scheduler must not perform any other optimizations (e.g.: constant folding, common subexpression elimination, strengh reduction, or “symbolic execution”).

Project Description: PART I

THIS IS NOT A GROUP PROJECT! Every student is expected to work on his own project. You may discuss overall design issues with your fellow students. Detailed discussions and/or code sharing is not allowed. The general rules for academic integrity apply.

Write three local instruction schedulers (single basic block) based on forward list scheduling. Your scheduler has to be able to accept the following ILOC instructions. These instructions are implemented in sim, our ILOC simulator. Click hereto look at a table of ILOC instructions and their semantics. The latencies of the instructions are given in parenthesis.

• no operation: nop (1)
• arithmetic: addI (1), add (1), subI (1), sub (1), mult (3), div (3)
• memory load (5), loadI (1), loadAO (5), loadAI (5), store (5), storeAO (5), storeAI (5)
• I/O: output (1)

Code Shape Requirements

• All variables are scalar, statically allocated, i.e., there is no need for activation records. The static area starts at memory location 1024. Addresses above are reserved for register spilling. The register r0 should contain the starting address (namely 1024) of the static area during program execution.
• You cannot rely on any particular naming strategy of the registers. For example, a code may use r1, r2, and r4, but not r3.
• Your scheduler has to work on ILOC code with anti-dependences. You will not need to track output dependences.

Deliverables

You are asked to write three different versions of a forward list scheduler. The difference between the schedulers are the heuristics used to select among READY instructions. Your executable should be named scheduler, and should allow the selection of the three different strategies through command line options (-a, -b, and -c). Your scheduler needs to read the input program from standard input, and write the generated ILOC instruction sequence to standard output. The three versions are based on the following heuristics:

• longest latency-weighted path to root (scheduler -a < test.iloc).
• highest latency instructions (scheduler -b < test.iloc).
• a heuristic of your choice (scheduler -c < test.iloc).

You may use any implementation language that is supported on the ilab machines. However, we only provide help with a C, C++ implementation.. We will provide a benchmark suite of ILOC programs that you will use to test your schedulers. There are 10 benchmark programs that you can find at ~zz124/cs415_2014/projects/proj1/benchmarkson the ilab cluster. Each benchmark program consists of a single basic block. Here is the ILOC programthat we used for the third homework. You may test the correctness of the ILOC code generated by your schedulers by running it on the ILOC simulator simprovided in directory ~zz124/cs415_2014/ILOC_Simulator/srcon the: ilab machines. This directory also contains the source code of the ILOC simulator.

Benchmark Programs

There are 20 benchmark programs we will use to test your implemented schedulers, including the 10 benchmarks provided at ~zz124/cs415_2014/projects/proj1/benchmarkson the ilab cluster and 10 other hidden benchmarks. The TA will release the 10 hidden benchmarks after the code package due date and after we receive your code package (whichever date comes late). In your project report, this benchmark suite will be the basis for showing the performance differences of your three instruction schedulers. You may add additional benchmarks to showcase particular features of your scheduler. You will need to describe these additional files in the ReadMe file for your project.

Project Description: PART II

You will write a project report that discusses the designs of your three schedulers and their performance on programs in the benchmark suite. You should list the execution times of the programs produced by your schedulers in terms of cycles as reported by the ILOC simulator. Please include in your report a discussion of the advantages and disadvantages of the different scheduling strategies. Particularly, your report should include the motivation of your heuristic for the third scheduler. The report should be in PDF format and between 3 and 6 pages. You are encouraged to use graphs to show your results.

Due Date

Please see above. If you have specific, overriding, personal reasons why these dates are unreasonable, you should discuss them directly with the instructor beforethe deadline.

Submission Procedure

Please submit a single tar-filewith all your sourcefiles, including the ReadMe file, to Sakai. The submission window for project I is open. Your ReadMe file may contain comments that you want the grader to know about. Do a “make clean” before tar-ing your files. Do notsubmit your scheduler as an executable. Do notsubmit the simulator, or the provided example programs.

We will use the following late policy: You will receive a penalty of 20% of your overall grade for each day late. A day is a working day (Monday through Friday). More details regarding the submission procedure will be posted later.

Grading Criteria

Your scheduler has to run on the ilab machines. Your schedulers should write their output into the file called schedule.out. This will allow us to perform automatic testing. You will receive no credit if your scheduler does not compile and/or execute on the ilab machines.You should submit a ReadMe file that contains a description of how to run your schedulers.
Your overall grade will be based on your code (60%) and your report (40%).