CS 415: Compilers
Spring 2022, Project 1
Local Instruction Scheduling
Due date code : Wednesday, March 2, at 11:59pm
EST
Due date report : Friday, March 4, at 11:59pm EST
Modifications and Clarifications
- 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 with their specific latencies
given in parenthesis:
- arithmetic: add (1), sub (1), mult (3), div (3)
- memory load (5), loadI (1), loadAI (5)
store (5), storeAI (5)
- I/O: outputAI (1)
The posted ILOC simulator uses these listed latencies for the instructions.
Code Shape Requirements
-
The register r0 contains the base address
(namely 1024) of the memory 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.
However, as mentioned above, r0 is a reserved register that is
used for the base address of memory references.
-
Your dependence (precedence) graph has only to compute true-dependencies and
anti-dependencies on registers and memory in the ILOC code, i.e.,
output-dependencies can be ignored since they will be covered through other
dependencies in all benchmark codes (see below)
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 > test-opt.iloc).
-
highest latency instructions (scheduler -b < test.iloc > test-opt.iloc).
-
a heuristic of your choice (scheduler -c < test.iloc > test-opt.iloc).
You may use any implementation language that is supported on the
ilab machines. However, we only provide help with a C
implementation. . There is some C code that allows you to read in
ILOC instructions and represent them in a linked list. A list of
instructions can then be printed to standard output. The provided C code
can be found in ~uli/cs415/projects/proj1/C on ilab. Copy the
files over into your own directory, and say "make". This will generate
an executable called "scheduler" in your directory. This directory
also contains the file lectureExample.iloc from our lecture.
You can execute this program using our ILOC simulator (see information
where to find the simulator below).
We provide a benchmark suite of ILOC programs that you will use
to evaluate the correctness and efficiency of your schedulers.
The benchmark programs will be made available in directory ~uli/cs415/projects/proj1/benchmarks on
the ilab cluster. These benchmarks
will be the basis for your report. Each benchmark
program consists of a single basic block.
You may test the correctness of the ILOC code generated by your
schedulers by running it on the ILOC simulator sim provided in
directory ~uli/cs415/ILOC_Simulator on the:
ilab machines .
Benchmark Programs
There are 20 benchmark programs posted at ~uli/cs415/projects/proj1/benchmarks on
the ilab cluster. This benchmark suite will be the basis for showing
the performance differences of your three instruction schedulers.
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. Please 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. The grader has to be
able to execute your schedulers on the ilab machines. Do include any
additional benchmarks that showcase the benefits of your optional scheduler.
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 each day late. A day is a working day
(Monday through Friday) or the weekend (Saturday and Sunday).
More details regarding the submission procedure on canvas will be posted later.
Grading Criteria
Your scheduler has to run on the ilab machines. 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%). Show your work.