# Project 1 – Total Points: 100 ## Important policies 1. Georgia Tech honor code will be strictly enforced. Please refrain from copying code from any source. We will enforce and prosecute such violations to the fullest possible extent permitted by the honor code. 2. Give enough details, but don’t write essays — be crisp and precise. 3. Make and write suitable assumptions where necessary in your report. 4. Ask on Piazza if you have doubts or questions. 5. As always, late submissions will NOT be accepted. Please make sure you submit by the deadline. 6. Submissions are expected to be typed up. A deduction of up to 5 points may apply for non-typed submissions. ## Submission instructions 1. Your solution should be submitted as two separate files to Canvas: * `project1_report.pdf` * `project1_code.zip`, which should contain the following files: * `vliwScheduler.cpp` * `Makefile` * Any other files needed for your code to compile * `4_wide_source_simple.s` * `4_wide_critpath_source_simple.s` * `4_wide_resource_source_simple.s` * `4_wide_fanout_source_simple.s` * `4_wide_critpath_resource_source_simple.s` * `4_wide_critpath_fanout_source_simple.s` * `4_wide_rename_source_simple.s`^ 2. Please use the precise filenames and directory structure. A failure to submit as directed will result in an automatic 5-point penalty. Please run `python3 project1_zip_validator.py` to validate that your zip file contains the minimum requested files but note that it’s not a guarantee of correctness. 3. Your report (`project1_report.pdf`) should contain everything requested in the Deliverables section at the end of the assignment. 4. You are free to submit as many times as you wish, but only the last submission prior to the deadline will be considered for grading. Canvas may rename your submissions by adding `-1` to filenames. No deduction will be applied for such cases. 5. Your code should compile in the default VM, if it does not, points will be deducted. ## Overview The overall goal of this project is to understand the VEX architecture and devise a scheduler for its VLIW instructions. In this project, you will design a scheduler that efficiently schedules instructions for a VLIW architecture. The goal of the scheduler is to schedule instructions such that the program completes in the minimum number of cycles. We are providing you with a 1-wide VLIW VEX assembly file, `simple.s`. Your job is to first build a data dependence graph and then build a scheduler based on the list scheduling algorithm. The goal is to schedule the instructions and convert the 1-wide code supplied to you into a 4-wide VLIW code. Make sure that the converted 4-wide VLIW is a valid schedule which satisfies all dependencies and latency requirements which can execute under the VEX simulator without any errors. The semantics of the code must be unaltered and it must produce the exact same output on the same input when executed. The latency requirements for different instruction can be found in Table 11 of the VEX manual (page 36). The **list scheduling algorithm** is given in Figure 10.8 on page 725 of the textbook: Compilers: Principles Techniques and Tools, 2nd edition, by Aho, Ullman, et.al. Please read all of Section 10.3 on basic block scheduling, and study the concept of **data dependence graph** and prioritized topological ordering. ## VM Setup Instructions 1. You should use the class VM. If you have not yet set it up, follow the instructions to install the VM in the README [here](https://github.gatech.edu/CS-6291/setup). 2. From your host machine, clone this repo into the directory that contains your `Vagrantfile`. 3. From within the VM, navigate to the shared directory by running `cd /vagrant`. ## Template Code A code template is provided to you in `vliwScheduler.cpp`. Complete the required functions to perform the list scheduling. Feel free to define any helper functions in the code but DO NOT modify any of the provided functions. ## Instruction Format In `vliwScheduler.cpp`, the helper function readInput returns a subset of instructions in the input assembly file that need to be scheduled. Note that that subset may contain `;;` delimiters and NOP instructions which you should discard when you are doing scheduling. All instructions in that vector are well-formatted and you can append them to your scheduling output directly. However, you may have to append NOP instructions to your output when there are no other instructions which can be scheduled under the given constraints and `;;` delimiters to the output when all the slots of the current VLIW instruction word are filled up. Format of NOP Instruction: “` “` Format of `;;` delimiter: “` ;; “` ## Executing `simple.s` The assembly file can be compiled and executed using the following steps within the VM: “` /home/vagrant/vex-3.43/bin/cc -o simple simple.s ./run.sh 1 2 3 4 5 6 7 8 9 10 “` When executing `run.sh`, you must provide 10 numbers for the code to run. Once you have completed the scheduling (more on this in the following sections), you will re-run each of the scheduled 4-wide code versions. You should verify that the converted VLIW schedules are valid by checking that the output matches that of the original 1-wide code. **Note: depending on how you pulled the repo down, you may need to run `dos2unix` on all the files in the repo to strip Windo