Project 2: Instruction Trace Scheduling 11/19/19, 10’33 PM
Project 2: Instruction Trace Scheduling
Submit Assignment
Due Thursday by 11:59pm Points 4 Submitting a file upload File Types tar, tgz, and zip Available until Nov 24 at 11:59pm
For the second piece of your project, you will explore how to
a) programmatically perform the dataflow scheduling you have previously only done by hand
b) be able to use this scheduler to develop intuitions about marginal benefits of OoO core parameters in the service of developing heuristics for project part 3
In a programming language of your choice among {C, Java, Python, C++} [note, your makefile must ensure that the correct version of python is invoked on CSE machines, i.e. be explicit in whether to invoke the python3 or python2.7 interpreter], implement a program with the following specification that performs dynamic (OoO) scheduling with conservative load-store ordering on a restricted set of simplified instructions:
Your program will take one command line input, a filename, and output its results in a file named out.txt Format of input file:
The input file will consist of a first line with two comma separated (no whitespace) positive integers followed by between 1-256 lines of a format described below. The two integers on the first line will specify the number of physical registers in the system and the issue width of the machine. All machine resources will match issue width, and the number of physical registers will always be greater than 32. If not, the program should produce an empty output file.
Each subsequent line will contain one of the following “instructions” R,
I,
L,
S,
where {R,I,L,S} are the capital letters R, I, L, and S, {,} is comma,
https://psu.instructure.com/courses/2006125/assignments/11096685?module_item_id=27431607 Page 1 of 4
Project 2: Instruction Trace Scheduling 11/19/19, 10’33 PM
destination for S.
Assuming the same sequence of pipeline stages and unbounded queue sizes as in exam 2, and that the first instruction is always fetched in cycle 0, produce the following output in out.txt:
For each instruction in the input file, produce a corresponding line in out.txt of the form
where all comma-separated fields are non-negative integers encoded as decimals and represent the cycle in which the associated instruction completes the specified stage. For simplicity, assume that S instructions occupy WB in the cycle after they issue.
Note that the same restrictions from exam 2 with regard to register freeing and conservative load-store scheduling apply: registers freed at commit in a cycle are not available on the free list until the following cycle, and that potentially dependent memory operations cannot issue in the same cycle. Likewise, assume that all memory operations hit, and all instructions writeback in the cycle following their issue. Assume, as in exam 2, that the initial architectural to physical mappings are A0->P0, A1->P1…A31->P31 and all other physical registers are on the free list in increasing register order (i.e. the next register consumed in renaming will always be P32)
Reminder: You are not allowed to copy pieces of OoO simulator code from the web wholesale. Do your own work. You have been warned. That said, you are welcome to look over the SimpleScalar documentation for inspiration, noting for instance, the structure of its primary simulation loop.
Example input-output pairs are provided in the modules directory for your testing benefit.
Submit the following:
One {tar,tgz,zip} file containing both A and B below that extracts both A and B into the same (current) directory (i.e. does not contain any directory hierarchy itself):
A) Your program source code, in one of the above listed languages.
B) A makefile that, when run on a CSE p204 machine in a directory containing only your makefile, your submitted program code, and a file named test.in, when given the target “test” (i.e. the command line “make test” is executed) will perform any necessary compilation and invoke your program on test.in
Please note the following — while, as a project-type assignment, you are strictly prohibited from
https://psu.instructure.com/courses/2006125/assignments/11096685?module_item_id=27431607 Page 2 of 4
Project 2: Instruction Trace Scheduling 11/19/19, 10’33 PM
collaborating on the contents of A) above, you may freely assist each other in developing or making copies of B) — the point of this exercise is not to force you to read the manual pages for gmake if you are not familiar with make environments; however, a common build and invocation method is required for logistically plausible testing.
Suggestion 0: Please try copying your zip/tarball/etc. into a clean directory, unpacking, and running “make test” on a CSE machine before turning in this assignment. If you can’t be bothered to test if your code compiles before turning it in, we are not going to be charitably inclined to figure out how to fix your build for you.
Suggestion 1: note that implementing dynamic scheduling involves performing associative search – for the scales considered, this can be readily implemented (inefficiently) via linear search — substantially more efficient data structures e.g. dictionaries/maps/etc. can also be used, but may not be worthwhile to create from scratch if you are implementing your solution in a language like C that neither supports them natively or through standard libraries.
Suggestion 2: Do not attempt to program a closed form solution. It isn’t going to work. Really, just don’t. You want to do a cycle by cycle simulation.
Suggestion 3: No, really, you want to do a cycle by cycle simulation. Once you’ve parsed the input file into an internal data structure, the heart of your solution should be wrapped inside a loop that iterates over all of the structures that need to be updated in a given cycle and then repeats until all instructions have committed.
Consider the following as a reasonable guideline for your top level function:
int main(int argc, char** argv){
init(argc,argv);
unsigned int committedInsts=0;
unsigned int fetchIndex=0;
while(committedInsts
Reviews
There are no reviews yet.