Overview
CSCI 2500 — Computer Organization Homework 5 (document version 1.0) Pipelining in MIPS
• This homework is due by 11:59:59 PM on Tuesday, December 4, 2018.
• This homework is to be completed individually. Do not share your code with anyone else.
• You must use C for this homework assignment, and your code must successfully execute on Submitty to obtain full credit.
Homework Specifications
For this individual homework assignment, you will use C to implement a simulation of MIPS pipelining. As we’ve covered in lecture, there are five stages to the pipeline, i.e., IF, ID, EX, MEM, and WB.
For your simulation, you are required to support the add, sub, and, or, lw, and sw instructions; note that some of these are pseudo-instructions, which is fine. More specifically, you must simu- late (and output) how a given sequence of instructions would be pipelined in a five-stage MIPS implementation.
Do not implement forwarding in your simulation.
You can assume that each given instruction will be syntactically correct. You can also assume that there is a single space character between the instruction and its parameters. Further, each parameter is delimited by a comma or parentheses. Below are a few example instructions that you must support:
add $t0,$s2,$s3
add $t1,$t3,73
or $s0,$s0,$t3
lw $a0,12($sp)
sw $t6,32($a1)
Required Command-Line Argument
Your program must accept one command-line argument as input. This argument (i.e., argv[1]) specifies the input file containing MIPS code to simulate. You may assume that no more than five instructions are given in the input file. And note that each instruction will end with a newline character (i.e., ‘\n’).
Required Output
For your output, you must show each cycle of program execution. Each cycle will correspond to a column of output. Initially, each column is empty, indicated by a period (i.e., ‘.’). Use TAB characters (i.e., ‘\t’) to delimit each column. And assume that you will have no more than nine cycles to simulate.
Recall that a data hazard describes a situation in which the next instruction cannot be executed in the next cycle until a previous instruction is complete. Your code should be able to detect when it is necessary to insert one or more “bubbles” (see Section 4.7 of the textbook and corresponding lecture notes for more details).
More specifically, you will need to properly handle data hazards by adding nop instructions as necessary. Show these cases by indicating an asterisk (i.e., ‘*’) in the appropriate columns and adding the required number of nop instructions. To ensure proper formatting, add an extra TAB character after the nop.
On the next few pages, we present a few example runs of your program that you should use to better understand how your program should work, how you can test your code, and what output formatting to use for Submitty.
2
The first example (i.e., ex01.s) includes no data hazards. START OF SIMULATION
CPUCycles===>1 add$s1,$s0,$s0IF add$t2,$s0,$s5. add$t4,$s3,70.
CPUCycles===>1 add $s1,$s0,$s0 IF add$t2,$s0,$s5. add$t4,$s3,70.
CPUCycles===>1 add $s1,$s0,$s0 IF add $t2,$s0,$s5 . add$t4,$s3,70.
CPUCycles===>1 add $s1,$s0,$s0 IF add $t2,$s0,$s5 . add$t4,$s3,70.
CPUCycles===>1 add $s1,$s0,$s0 IF add $t2,$s0,$s5 . add $t4,$s3,70 .
CPUCycles===>1 add $s1,$s0,$s0 IF add $t2,$s0,$s5 . add $t4,$s3,70 .
CPUCycles===>1 add $s1,$s0,$s0 IF add $t2,$s0,$s5 . add $t4,$s3,70 .
END OF SIMULATION
2 3 . . . . . .
2 3 ID . IF . . .
2 3 ID EX IF ID . IF
2 3 ID EX IF ID . IF
2 3 ID EX IF ID . IF
2 3 ID EX IF ID . IF
2 3 ID EX IF ID . IF
4 5 . . . . . .
4 5 . . . . . .
4 5 . . . . . .
4 5 MEM . EX . ID .
4 5 MEM WB EX MEM ID EX
4 5 MEM WB EX MEM ID EX
4 5 MEM WB EX MEM ID EX
6 7 8 9 . . . . . . . . . . . .
6 7 8 9 . . . . . . . . . . . .
6 7 8 9 . . . . . . . . . . . .
6 7 8 9 . . . . . . . . . . . .
6 7 8 9 . . . . . . . . . . . .
6 7 8 9 . . . . WB . . . MEM . . .
6 7 8 9 . . . . WB . . . MEM WB . .
3
The second example (i.e., ex02.s) includes a dependency on register $t1. START OF SIMULATION
CPUCycles===>1 add$t1,$s0,$s0IF add$t2,$s0,42. add$t4,$t1,70.
CPUCycles===>1 add $t1,$s0,$s0 IF add$t2,$s0,42. add$t4,$t1,70.
CPUCycles===>1 add $t1,$s0,$s0 IF add$t2,$s0,42. add$t4,$t1,70.
CPUCycles===>1 add $t1,$s0,$s0 IF add $t2,$s0,42 . add$t4,$t1,70.
CPUCycles===>1
add $t1,$s0,$s0 IF
add $t2,$s0,42 .
nop . . IF ID * . . . .
2 3 . . . . . .
2 3 ID . IF . . .
2 3 ID EX IF ID . IF
2 3 ID EX IF ID . IF
4 5 . . . . . .
4 5 . . . . . .
4 5 . . . . . .
4 5 MEM . EX . ID .
6 7 8 9
- . . . .
- . . . .
- . . . .
6 7 8 9
- . . . .
- . . . .
- . . . .
6 7 8 9
- . . . .
- . . . .
- . . . .
6 7 8 9
- . . . .
- . . . .
- . . . .
2 3 ID EX IF ID
4 5 MEM WB EX MEM
6 7 8 9
- . . . .
- . . . .
add $t4,$t1,70 .
CPUCycles===>1
add $t1,$s0,$s0 IF
add $t2,$s0,42 .
nop . . IF ID * * . . .
. IF
ID ID . .
. .
2 3 ID EX IF ID
4 5 6 7 MEM WB . . EX MEM WB .
8 9 . . . .
add $t4,$t1,70 .
CPUCycles===>1
add $t1,$s0,$s0 IF
add $t2,$s0,42 .
nop . . IF ID * * * . .
END OF SIMULATION
. IF
ID ID EX .
. .
2 3 ID EX IF ID
4 5 6 7 MEM WB . . EX MEM WB .
8 9 . . . .
add $t4,$t1,70 .
CPUCycles===>1
add $t1,$s0,$s0 IF
add $t2,$s0,42 .
nop . . IF ID * * * . . add $t4,$t1,70 . . IF ID ID EX MEM WB .
. IF
ID ID EX
MEM . .
2 3 ID EX IF ID
4 5 6 MEM WB . EX MEM WB
7 8 9 . . . . . .
4
The third example (i.e., ex03.s) includes two dependencies on register $t2. START OF SIMULATION
CPUCycles===>1 lw$t2,20($a0)IF and$t4,$t2,$t5. or$t8,$t2,$t6.
CPUCycles===>1 lw$t2,20($a0)IF and$t4,$t2,$t5. or$t8,$t2,$t6.
CPUCycles===>1 lw $t2,20($a0) IF and $t4,$t2,$t5 . or$t8,$t2,$t6.
CPUCycles===>1
lw $t2,20($a0) IF
nop . IF ID * . . . . . nop . IF ID * . . . . .
2 3 . . . . . .
2 3 ID . IF . . .
2 3 ID EX IF ID . IF
4 5 . . . . . .
4 5 . . . . . .
4 5 . . . . . .
6 7 8 9
- . . . .
- . . . .
- . . . .
6 7 8 9
- . . . .
- . . . .
- . . . .
6 7 8 9
- . . . .
- . . . .
- . . . .
2 3 ID EX
4 5 MEM .
6 7 8 9 . . . .
and $t4,$t2,$t5 . or$t8,$t2,$t6.
CPUCycles===>1
lw $t2,20($a0) IF
nop . IF ID * * . . . . nop . IF ID * * . . . .
IF ID . IF
ID . . IF . .
. . . . . .
2 3 ID EX
4 5 6 MEM WB .
7 8 9 . . .
and $t4,$t2,$t5 . or $t8,$t2,$t6 .
CPUCycles===>1
lw $t2,20($a0) IF
nop . IF ID * * * . . . nop . IF ID * * * . . .
IF ID . IF
ID ID . IF IF .
. . . . . .
2 3 ID EX
4 5 6 MEM WB .
7 8 9 . . .
and $t4,$t2,$t5 . or $t8,$t2,$t6 .
CPUCycles===>1
lw $t2,20($a0) IF
nop . IF ID * * * . . . nop . IF ID * * * . . . and $t4,$t2,$t5 . IF ID ID ID EX MEM . . or $t8,$t2,$t6 . . IF IF IF ID EX . .
IF ID . IF
ID ID EX . IF IF ID .
. . . .
2 3 ID EX
4 5 6 7 MEM WB . .
8 9 . .
5
CPUCycles===>1 2 3 4 5 6 7 8 9 lw $t2,20($a0) IF ID EX MEM WB . . . . nop . IF ID * * * . . . nop . IF ID * * * . . .
and $t4,$t2,$t5 . or $t8,$t2,$t6 .
CPUCycles===>1
lw $t2,20($a0) IF
nop . IF ID * * * . . . nop . IF ID * * * . . . and $t4,$t2,$t5 . IF ID ID ID EX MEM WB . or $t8,$t2,$t6 . . IF IF IF ID EX MEM WB
END OF SIMULATION
Assumptions
Given the complexity of this assignment, you can make the following assumptions: • Assume all input files are valid.
• Assume the length of argv[1] is at most 128 characters, but do not assume that argv[1] is present.
Error Checking
Given the complexity of this assignment, you can assume that the input file is valid. Be sure to verify that you have the correct number of arguments by checking argc; display an error message if argument(s) are missing.
In general, if an error occurs, use either perror() or fprintf( stderr, “…” ), depending on whether the global errno is set.
And be sure to return either EXIT_SUCCESS or EXIT_FAILURE upon program termination.
Submission Instructions
Before you submit your code, be sure that you have clearly commented your code (this should not be an after-thought). Further, your code should have a clear and logical organization.
To submit your assignment (and also perform final testing of your code), please use Submitty. Note that the test cases for this assignment will be available on Submitty a minimum of three days before the due date and will include hidden test cases.
Also as a reminder, your code must successfully execute on Submitty to obtain credit for this assignment.
IF ID . IF
ID ID EX IF IF ID
MEM WB . EX MEM .
2 3 ID EX
4 5 6 MEM WB .
7 8 9 . . .
6