CS 415: Compilers
Spring 2019, Project 1
Local Instruction Scheduling
Due date code : Monday, March 4, at 11:59pm EST
Due date report : Wednesday, March 6, at 11:59pm EST

Modifications and Clarifications

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:
The posted ILOC simulator uses these listed latencies for the instructions.

Code Shape Requirements


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: 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 lecture 5/6. You can execute this program using our ILOC simulator (see information where to find the simulator below).

At a later time, we will 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 . If you want to generate the simulator on your own machine, the subdirectory src contains the source code of the ILOC simulator. Note: the simulator source code is not needed if you want to run your ILOC programs on ilab.

Benchmark Programs

There will be 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. 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. 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). More details regarding the submission procedure 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.