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.

  1. Identify and classify all RAW dependencies that exist in instruction1.txt and instruction2.txt.
  1. a. What is the CPI for instruction1.txt and instruction2.txt with no forwarding?
    b. What is the CPI with forwarding?
    c. What is the speedup for instruction1.txt and instruction2.txt when using forwarding?
  1. 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.
  1. Would CPI improve from doubling the processor frequency? Why or why not? How can you further improve the CPI of a processor?
  1. 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?
  1. 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?