Assignment 1 - Pipelining
Due: Monday, January 25 @ 11:59:59 PM Pacific Time
This assignment will be turned in through Github Classroom.
Overview
The goal of assignment 1 is to extend a simple pipeline simulator to support forwarding.
For this lab, we will extend Pipesim, a very simple timing simulator for a 5-stage pipeline processor.
Note that this simulator is not functional since the instructions are not actually processed.
If you have any questions, please post to Campuswire as others may be having the same issue.
For this assigment, we will be using Github Classroom.
Please join the classroom by clicking the following link: https://classroom.github.com/a/7WrxYZbB
Once you join the classroom, a private github repository will automatically be created with the starter code.
Pipesim
Pipesim was developed with the sole purpose of teaching computer architecture.
Note that Pipesim is still under development and have limited feature sets.
Future extensions of Pipesim functionality are left to you. =)
Pipesim source code overview
Pipesim consists of 3 main files: pipeline.cpp
, pipeline.h
, and main.cpp
.
DO NOT MODIFY main.cpp
OR pipeline.h
!
main.cpp
initializes the pipeline and loads the instruction trace to run.pipeline.h
contains the class definitions for various objects.pipeline.cpp
implements the main functionality of the pipeline timing simulator.
Functions of interest are, but not limited to, the following:
bool Pipeline::hasDependency(void)
- Checks for hazards between the instruction in the decode stage and execute/memory/writeback stage.void Pipeline::cycle(void)
- Simulates the flow of instruction through the pipeline. Currently stalls the pipeline if RAW hazards are detected.
Pipesim inputs
Pipesim takes in two command line parameters:
$ ./pipesim
usage is
-i fileName : to run input file fileName
-f : for enabling forwarding
- The forwarding option sets a flag to enable or disable forwarding. Currently, forwarding is not implemented. You will be implementing forwarding for this lab.
- The input file is a sequence of instruction that will be simulated through the pipeline. We provide three sample inputs in the
traces
folder:instruction1.txt
,instruction2.txt
,instruction3.txt
.
Pipesim minimal ISA
The input instruction format uses a minimal ISA format that includes all the information we need to model the timing of the pipeline. (All we really need are registers to detect RAW hazards.) Currently, the ISA does not support immediate values, offset addressing, branches, etc.
For example, LW R1, 100(R2)
, is simplified to LW R1 R2
.
Running Pipesim
The following shows an example run of Pipesim. Pipesim prints out the flow of the instructions through a 5-stage pipeline. Pipesim currently supports stalling to resolve RAW hazards.
$ ./pipesim -i traces/instruction1.txt
Loading application...traces/instruction1.txt
Read file completed!!
Printing Application:
ADD r1 r2 r3
SUB r2 r3 r4
MULT r3 r1 r5
DIV r4 r3 r6
LW r5 r4
SW r5 r7
BNE r7 r8
Initializing pipeline...
Cycle IF ID EXEC MEM WB
0 * * * * *
1 ADD r1 r2 r3 * * * *
2 SUB r2 r3 r4 ADD r1 r2 r3 * * *
3 MULT r3 r1 r5 SUB r2 r3 r4 ADD r1 r2 r3 * *
4 DIV r4 r3 r6 MULT r3 r1 r5 SUB r2 r3 r4 ADD r1 r2 r3 *
5 DIV r4 r3 r6 MULT r3 r1 r5 * SUB r2 r3 r4 ADD r1 r2 r3
6 LW r5 r4 DIV r4 r3 r6 MULT r3 r1 r5 * SUB r2 r3 r4
7 LW r5 r4 DIV r4 r3 r6 * MULT r3 r1 r5 *
8 LW r5 r4 DIV r4 r3 r6 * * MULT r3 r1 r5
9 SW r5 r7 LW r5 r4 DIV r4 r3 r6 * *
10 SW r5 r7 LW r5 r4 * DIV r4 r3 r6 *
11 SW r5 r7 LW r5 r4 * * DIV r4 r3 r6
12 BNE r7 r8 SW r5 r7 LW r5 r4 * *
13 BNE r7 r8 SW r5 r7 * LW r5 r4 *
14 BNE r7 r8 SW r5 r7 * * LW r5 r4
15 * BNE r7 r8 SW r5 r7 * *
16 * * BNE r7 r8 SW r5 r7 *
17 * * * BNE r7 r8 SW r5 r7
18 * * * * BNE r7 r8
19 * * * * *
Completed in 18 cycles
Extending Pipesim
Your goal for assignment 1 is to extend Pipesim to support forwarding. Specifically, you are expected to support forwarding from 1) EXEC/MEM pipeline register to EXEC stage and 2) MEM/WB to EXEC stage
Submission
Answer the following questions by adding a report document in the repository.
Please name your report FirstName-LastName.pdf
or FirstName-LastName.txt
or FirstName-LastName.docx
, etc.
Commit and push your completed code to the github repository. (You only need to modify pipeline.cpp
.)
Please also include your name in the report.
Questions
Note that some of the following questions are not directly related to the simulation but are related to concepts discussed in the class.
- Identify and classify all RAW dependencies that exist in
instruction1.txt
andinstruction2.txt
.
- a. What is the CPI for
instruction1.txt
andinstruction2.txt
with no forwarding?
b. What is the CPI with forwarding?
c. What is the speedup forinstruction1.txt
andinstruction2.txt
when using forwarding?
- Using a pipeline without forwarding, reorder the instructions in
instruction2.txt
to minimize the number of stalls. Show the new reordered instruction trace and calculate the speedup compared to the original instruction trace.
- Would CPI improve from doubling the processor frequency? Why or why not? How can you further improve the CPI of a processor?
- Assuming a program has 30% of the overall execution time that uses the ALU, and we developed a technique to speedup ALU instructions, what is the maximum speedup that we can achieve?
- If 75% of a program can be done in parallel, given the same execution time what is the speedup of a machine with 4 cores vs a machine with 1 core?