Programming Project: Basic PipeliningCMSC411 Spring 2006Due: March 30, 2006 6:00PMIn this assignment, you will become familiar with how a basic 5-stage pipeline works. You will be givena simulator that models an unpipelined processor that implements a small MIPS-like instruction set. Yourassignment is to create a cycle-accurate simulator of a pipelined version of this processor. Your simulatorwill perform data forwarding, a simple branch prediction scheme, and the pipeline interlocks to stall thepipeline when necessary.1 FilesThe first thing you should do is copy the files from the /afs/csic.umd.edu/users/als/411/spr06/P1 directoryinto your own local directory. Alternatively, the files can be downloaded from the class Projects web page.There are 8 files: asm.c, mips-small.c, mips-small-pipe.c, mips-small-pipe.h, Make-file, mult.s, simple.s, and simple.output. asm.c is an assembler for the reduced MIPS ISAwhich your simulator will implement (more about the assembler and the ISA later). mips-small.c is theC source file for a fully functional unpipelined simulator. mips-small-pipe.c is a C source code tem-plate that has some useful data structures and routines for a pipelined simulator. You can use this templateto get started on the assignment. mips-small-pipe.h is a header file included by mips-small-pipe.c, and Makefile is a unix make file which will produce the binaries asm, sim, and sim-pipefrom the source files, asm.c, mips-small.c, and mips-small-pipe.c, respectively.In the remaining files, we have provided two example assembly programs. simple.s performs anarithmetic operation and mult.s multiplies two numbers. simple.output is the result of runningsimple.s through our pipelined simulator, and can be used to verify your simulator’s output.2 A Scaled-Down MIPS ISAYou will be simulating the MIPS ISA from Hennessy & Patterson, with some key differences. First, insteadof a 64-bit architecture, you will implement a 32-bit architecture. In other words, all registers and data pathsare 32 bits wide, and all instructions will operate on 32-bit operands. Second, to keep your simulator simple,you will only be required to support a scaled-down version of the MIPS ISA consisting of 11 instructions.These instructions, along with their encoding, are given in Table 1. We will adhere to the MIPS instructionformats presented in Figure 2.27 of Hennessy & Patterson, with the exception that there is no “shamt” fieldin the R-type format, and instead the “func” field is 11-bits wide. Finally, although all immediate values inbranch and jump instructions are left-shifted by 2, your BEQZ instruction SHOULD NOT perform the leftshift.1Name Format Type Opcode FuncLW I-type 0x23SW I-type 0x2BBEQZ I-type 0x4ADDI I-type 0x8ADD R-type 0x0 0x20SUB R-type 0x0 0x22SLL R-type 0x0 0x4SRL R-type 0x0 0x6AND R-type 0x0 0x24OR R-type 0x0 0x25HALT J-type 0x3FTable 1: Instruction encodings for a reduced MIPS ISA.Notice that all the instructions in Table 1 except for one exist in the normal MIPS ISA. These instructionsbehave exactly as described in the text (except they are 32-bit versions rather than 64-bit versions). Theinstruction we’ve added is “HALT.” As its name implies, when your simulator executes a HALT instruction,it should terminate the simulation. For more information about MIPS, consult Section 2.12 of Hennessy &Patterson.3 asm: An Assembler for the Reduced MIPS ISAWe have provided an assembler, asm.c, so that you can assemble programs for your simulator. The asm.cfile is fully functional, and you will not need to make any modifications to this file. Simply use the Make-file to make the binary asm from the asm.c source file.The format for assembly programs is very simple. A valid assembly program is an ASCII file in whicheach line of the file represents a single instruction, or a data constant. The format for a line of assembly codeis:label<tab>instruction<tab>field0<tab>field1<tab>field2<tab>commentsThe leftmost field on a line is the label field which indicates a symbolic address. Valid labels contain amaximum of 6 characters and can consist of letters and numbers. The label is optional (the tab following thelabel field is not). After the optional label is a tab. Then follows the instruction field, where the instructioncan be any of the assembly-language mnemonics listed in Table 1. After another tab comes a series of fields.All fields are given as decimal numbers. The number of fields depends on the instruction. The followingdescribes the instructions and how they are specified in assembly code:lw rd rs1 imm Reg[rd] <- Mem[Reg[rs1] + imm]sw rd rs1 imm Reg[rd] -> Mem[Reg[rs1] + imm]beqz rd rs1 imm if (Reg[rs1] == 0) PC <- PC+4+immaddi rd rs1 imm Reg[rd] <- Reg[rs1] + immadd rd rs1 rs2 Reg[rd] <- Reg[rs1] + Reg[rs2]sub rd rs1 rs2 Reg[rd] <- Reg[rs1] - Reg[rs2]sll rd rs1 rs2 Reg[rd] <- Reg[rs1] << Reg[rs2]srl rd rs1 rs2 Reg[rd] <- Reg[rs1] >> Reg[rs2]and rd rs1 rs2 Reg[rd] <- Reg[rs1] & Reg[rs2]or rd rs1 rs2 Reg[rd] <- Reg[rs1] | Reg[rs2]halt stop simulation2Note that in the case of the beqz instruction, PC-relative addressing is used (and again, your simulatorshould not perform the left-shift when computing the PC-relative branch target). For the lw, sw, and beqzinstructions, the imm field can either be a decimal value, or a label can be used. In the case of a label, theassembler performs a different action depending on whether the instruction is a lw / sw instruction, or abeqz instruction. For lw and sw instructions, the assembler inserts the absolute address corresponding tothe label. For beqz instructions, the assembler computes a PC-relative offset with respect to the label.After the last field is another tab, then any comments. The comments end at the end of the line.In addition to instructions, lines of assembly code can also include directives for the assembler. Theonly directive we will use is .fill. The .fill directive tells the assembler to put a number into theplace where the instruction would normally be stored. The .fill directive uses one field, which canbe either a numeric value or a symbolic address. For example, “.fill 32” puts the value 32 where theinstruction would normally be stored. In the following example, “.fill start” will store the value 8,because the label “start” refers to address 8 (remember that the MIPS architecture uses byte addresses).addi 1 0 5 load reg1 with 5addi 2 0 -1 load reg2 with -1start add 1 1 2 decrement reg1lw 3 0 var1 loads reg3