CS 415: Compilers
Spring 2016, Project 1
Local Instruction Scheduling
Due date code : Wednesday, February 24, at 11:59pm EST
Due date report : Friday, February 26, at 11:59pm EST
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.
- 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/her 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 here to 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++, or Java
implementation. .
We will provide a benchmark suite of ILOC programs that you will use
to test your schedulers.
There are 15 benchmark programs that you can find at ~zz124/cs415_2016/projects/proj1/benchmarks on
the ilab cluster.
Each benchmark
program consists of a single basic block. Here is a sample
ILOC
program.
You may test the correctness of the ILOC code generated by your
schedulers by running it on the ILOC simulator sim provided in
directory ~zz124/cs415_2016/ILOC_Simulator/src on 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 15 benchmarks provided at ~zz124/cs415_2016/projects/proj1/benchmarks on
the ilab cluster and 5 hidden benchmarks. The TA
will release the 5
hidden benchmarks after the code deadline and after we receive your code
submission (whichever date comes late). In your project report,
this benchmark suite will be the basis for showing
the performance differences of 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 the
three schedulers and the performance evaluation of the benchmark programs. You
should list the execution time of the program generated
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 before the deadline.
Submission Procedure
Please submit a single tar-file with all your source files, including
the ReadMe file. Your ReadMe file may contain
comments that you want the grader to know about. Do a "make clean"
before tar-ing your files.
Do not submit your scheduler as an executable. Do not
submit 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 every 24 hours late. No late project submission will be
accepted from 72 hours after the deadline.
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 (70%) and your report
(30%).