CIS 480/580 Computer Architecture, Fall 2021Project 1-3 – MIPS Simulator1. ObjectivesThis project is designed to help students to understand the pipelining on a RISC architecture(MIPS), pipeline hazards, and hazards mitigation techniques including forwarding and stalling.Students will gain programming experience in C.2. GoalsYour team of 2 students will build a simulator of a (5-stage pipelined) MIPS in C. This simulatorwill read a binary executable file containing a sequence of MIPS instructions and simulate theirexecution in stages in a (pipelined) MIPS processor.Project 1 is a non-pipelined MIPS.Project 2 is a pipelined MIPS without the considerations for branch hazard and data forwarding.Project 3 is a pipelined MIPS including branch hazard and data forwarding.Due dates for Project 1, 2 and 3 are October 6, November 5 and December 1, respectively.3. Specification3.1 InputYour simulator will read a binary executable file. It is of size 1KB and consists of 512B of datasegment followed by 512B of text segment (offset 0x200). Do not try to open this file as it causesan error. You can view a binary file using od command in linux (e.g., od -Ax -t x4 memory.out)or format-hex command in Windows Powershell (e.g., format-hex memory.out). Assume inputfiles do not contain any errors.3.1.1 RegistersThe user can use any of the 32 MIPS registers (0-31). Please note that $0 is read-only and shouldalways contain the value 0. Your simulator will need to include a register file (e.g., an array of 32integers) that maintains the values of all the 32 registers and updates the registers as theinstructions are executed.3.1.2 Data segmentThe data segment is of 512B and the only form of data will be integer numbers (4 bytes long). I.e.,there can be at maximum 128 integer data in the data segment. The data will not contain anyother form of data such as string (ascii characters) or floating point numbers. When the programsees load or store instructions, the address will resolve to access one of these 128 integer data.Therefore, as execution proceeds, loads (lw) can read from the data segment and stores (sw) canwrite to the data segment.3.1.3 Text segmentThe text segment is of 512B, i.e., there can be at maximum 128 MIPS instructions because eachMIPS instruction is 4 bytes long. However, due to the presence of branches and jumps, someinstructions will be executed multiple times. The text segment will only contain the followingMIPS instructions. Instruc-tionSyntaxMIPS instruction encoding (32 bits)(R-type)Opcode(6)Rs(5)Rt(5)Rd(5)Shamt(5)Func(6)ADDadd $1,$2,$300000000000100000 (=3210)SUBsub $1,$2,$300000000000100010 (=3410)SLLsll $1,$2,5000000000000 (=0)SRLsrl $1,$2,5000000000010 (=2)SLTslt $1,$2,$300000000000101010 (=4210)HALThalt00000000000000000000000000001100 (=1210)(I-type)Opcode(6)Rs(5)Rt(5)Immediate (16)ADDIaddi $1,$2,45001000LWlw $1,100($2)100011SWsw $1,100($2)101011BEQbeq $1,$2,Label000100BNEbne $1,$2,Label000101 The ‘halt’ instruction indicates the end of the program but note that it is not an actualMIPS instruction. Note that branch target will be contained in the program. In other words, it does notgo beyond the 512B boundary. Since the text segment begins at 0x200, this meansthe targets will be in the range of 0x200 ~ 0x400. Please note the use of labels in the branch (beq and bne) instructions. You will needto calculate the branch target based on the following relationship.Addr(Label) = Addr(branch_instruction) + 4 + immediate(16 bits)*43.1.4 Sample inputConsider an input file as follows (binary view; e.g., od -Ax -t x4 or format-hex in Linux andWindows, respectively):000000 00000000 00000000 00000001 00000002000010 00000000 00000000 00000000 00000000*000200 20010008 8c240000 8c250004 00020940000210 00020942 0043082a 00000000 00000000000220 00000000 00000000 00000000 00000000*000400Note that this file begins with the data segment (512 bytes) followed by the text segment (512bytes). The data segment contains two non-zero data at location 8 and 12 and the data is 1 and 2,respectively, and the first instruction is “20010008” which indicates an ADDI instruction.In general, when you execute a program, OS reads the program executable file and loads it intomemory. You can assume the 1KB file mentioned above is an executable file and thus is loaded.Therefore, the 512 bytes of data in the data segment is loaded into Memory[0~511]. The two nonzero data can be explained as Memory[8] = 1 and Memory[12] = 2. The 512 bytes of textsegment is loaded into Memory[512~1023]. The first instruction, “20010008” (ADDI) is thus atMemory[512].3.2 OutputYour simulator should show the followings for every cycle of program execution until itencounters an HALT instruction. Clock cycle count and the value of PC Data memory words (the first 16 only out of 128 words) Registers ($0 ~ $15 only)For Project 1, your simulator should output as follows. Note that an arrow sign and theinstructions on the right is just for your information; you do not have to print this. Cycle = 1, PC = 200addi $1,$0,8DM0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0RegFile0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0——————————————————————————————Cycle = 2, PC = 204lw $4,0($1)DM0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0RegFile0 8 0 0 1 0 0 0 0 0 0 0 0 0 0 0——————————————————————————————Cycle = 3, PC = 208lw $5,4($1)DM0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0RegFile0 8 0 0 1 2 0 0 0 0 0 0 0 0 0 0 ——————————————————————————————For Project 2 & 3, your simulator should output the values of all pipeline registers and controlsignals too. The content of the pipeline registers and control signals (ctrl) are explained in detaillater in this document. Note that an arrow sign and the instructions on the right is just for yourinformation; you do not have to print this.Cycle = 1, PC = 200 DMRegFileIF/ID (pc4, inst)0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0addi $1,$0,8 in IF204 20010008ID/EX (pc4, rd1, rd2, extend, rs, rt, rd, ctrl)0 0 0 0 0 0 0 0EX/MEM (btgt, zero, ALUOut, rd2, RegRd, ctrl) 0 0 0 0 0 0MEM/WB (memout, ALUOut, RegRd, ctrl)0 0 0 0——————————————————————————————Cycle = 2, PC = 204DMRegFileIF/ID (pc4, inst)0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0lw $4,0($1) in IF208 8c240000ID/EX (pc4, rd1, rd2, extend, rs, rt, rd, ctrl)204 0 0 8 0 1 0 180 addi $1,$0,8 in IDEX/MEM (btgt, zero, ALUOut, rd2, RegRd, ctrl) 0 0 0 0 0 0MEM/WB (memout, ALUOut, RegRd, ctrl)0 0 0 0——————————————————————————————Cycle = 3, PC = 208DMRegFileIF/ID (pc4, inst)0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0lw $5,4($1) in IF20c 8c250004ID/EX (pc4, rd1, rd2, extend, rs, rt, rd, ctrl)208 0 0 0 1 4 0 2c0 lw $4,0($1) in IDEX/MEM (btgt, zero, ALUOut, rd2, RegRd, ctrl) 204 0 8 0 1 180addi $1,$0,8 in EXMEM/WB (memout, ALUOut, RegRd, ctrl)0 0 0 0 ——————————————————————————————Note that rs is typically not a part of the ID/EX pipeline register but included here to implementdata forwarding. See section 4.7 of this document for details.3.3 TestingA few sample test binary files will also be provided about a week before the project is due. Makeuse of the sample executable to help verify your output.You can test your design using your own programs. The quality of your simulator will bedetermined by how much and how varied the tests are. For example, testing if the simulatorworks for BNE for both the equal and not equal cases, and forward and backward branching, andall combinations of these, would get a better grade than just testing for one case of BNE.4. Suggested Approach4.1 DatapthDatapath of the MIPS processor is as in the following figure. You may want name the variables inyour simulator as shown in the following figure. Note that you may use an integer variable(32-bit) for most of the signals for your convenience even though they are not 32-bit data.The logic for “BNE” is not included in the figure and can be added easily. I.e., find in the figurethat PCSrc = Branch & Zero. It can be extended to incorporate BNE:PCSrc = (Branch && Zero) || (BranchNE && !Zero)PCInstructionmemoryReadaddressInstruction[31– 0]Instruction [20– 16]Instruction [25– 21]AddInstruction [5– 0]MemtoRegALUOpMemWriteRegWriteMemReadBranchRegDstALUSrcInstruction [31– 26]416 32Instruction [15– 0]00Co 0 Mux 1ntrolAdd ALUresult0 Mux 1RegistersWriteregisterWritedataReaddata 1Readdata 2Readregister 1Readregister 2SignextendShiftleft 2Mux 1ALUresultZeroDatamemoryWritedataReaddata1 MuxInstruction [15– 11]ALUcontrolALUAddresspc instrpc4oprsrtrdwnextendwdrd1immedrd2offsetpc_nextfunctALUOut memoutPCSrcbtgt0 14.2 Pipelined datapth (for Project 2 & 3)The processor pipeline has the following 5 stages: Instruction Fetch (IF), Register fetch/instruction decode (ID), ALU/Execute (EX), Memory (MEM), and Write back (WB). You maywant name the variables in your simulator as shown in the following figure. For example,“EX_RegRd” and “MEM_RegRd” refer to the destination register number in the EX and theMEM stage, respectively. Note that you may use an integer variable (32-bit) for most of thesignals for your convenience even though they are not 32-bit data.The logic for “BNE” is not included in the figure and can be added easily. I.e., find in the figurethat MEM_PCSrc = MEM_Branch & MEM_Zero. It can be extended to incorporate BNE:MEM_PCSrc = (MEM_Branch && MEM_Zero) || (MEM_BranchNE && !MEM_Zero)Note: WB_RegRd and WB_wn are the same. In the skeleton program in section 4.6 of thisdocument uses WB_RegRd.Note: EX_rd2 is not shown in this figure.Note: Signals IF_pc4j, ID_Jump, and ID_jtarget are not needed because “j” instruction is not thescope of the project.4.3 ControlControl signals consists of 11 signals including BranchNE and Jump and the control signal word(ctrl) is generated based on opcode of an instruction as follows.bit10 bit9 bit8 bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 RegDstALUSrcMemtoRegRegWriteMemReadMemWriteBranchALUOp1ALUOp0BranchNEJumpR-format101100010000x588 or 1416lw010110000000x2c0 or 704swx1x001000000x220 or 544beqx0x000101000x014 or 20addi011100000000x380 or 896bnex0x000001100x006 or 6 Whenever necessary, you can extract a particular control signal by using bitwise “shift (>>)” and“and (&)” operations. For example, MemtoReg is bit 8 in the control signal word (ctrl). If it is a“lw” instruction, “ctrl” is 010 1100 0000 (0x2c0 or 704) and bit 8 is 0. To obtain bit 8, first, shiftthe 11-bit control data 8 bits to the right. Thus, (010 1100 0000 >> 8) = 000 0000 0010. Then,ANDed it with 1, thus, 0000 0000 0010 & 1 = 0. I.e.,MemtoReg = (ctrl >> 8) & 1;Note that you may use an integer variable (32-bit) for each of the control signals (e.g.,MemtoReg) for your convenience even though they are just a 1-bit data.In Project 2 & 3, control signals are generated in the ID stage and move to next stages along withthe instruction as discussed in class. For convenience, you can pass all 11 control signals (ctrl)from stage to stage. Extracting a particular control signal should be done in each stage.For example, WB_MemtoReg is bit 8 in the control signal word (WB_ctrl). If it is an “lw”instruction, “WB_ctrl” is 010 1100 0000 (0x2c0 or 704) and bit 8 is 0. To obtain bit 8, first, shiftthe 11-bit control data 8 bits to the right. Thus, (010 1100 0000 >> 8) = 000 0000 0010. Then,ANDed it with 1, thus, 0000 0000 0010 & 1 = 0. I.e.,WB_MemtoReg = (WB_ctrl >> 8) & 1;Note that you may use an integer variable (32-bit) for each of the control signals (e.g.,WB_MemtoReg) for your convenience even though they are just a 1-bit data.4.4 Pipeline registers (Project 2 & 3)Pipeline registers (such as IF/ID and ID/EX in the figure) are tosave the computed values necessary for the next stage and eachpipeline register includes a number of components. To conform tothe naming conventions, it is advised to name the pipelineregisters (their components) like IFID_pc4 (a part of IF/IDpipeline register) and IDEX_rd1 (a part of ID/EX pipelineregister).Pipeline registers are read to set internal signals in the beginningof a cycle in the read_pipeline_registers() function. As an example,below is the EX stage part of read_pipeline_registers() function.EX_ctrl = IDEX_ctrl;EX_pc4 = IDEX_pc4;EX_rd1 = IDEX_rd1; EX_rd2 = IDEX_rd2;EX_extend = IDEX_extend:EX_rs = IDEX_rs; EX_rt = IDEX_rt; EX_rd = IDEX_rd;These internal signals will be used to set other internal signals. Asan example, below is the EX stage part of thecarryout_operations() function.EX_offset = EX_entend > 9) & 1;If (EX_ALUSrc == 0) EX_alu2 = EX_rd2;else EX_alu2 = EX_extend;…………EX_Zero = _____;EX_RegDst = (EX_ctrl >> 10) & 1;if (EX_RegDst == 0) EX_RegRd = EX_rt;else EX_RegRd = EX_rd;The outcome of operations in each stage will be used to set pipeline registers at the end of thecycle. As an example, below is the EX stage part of theupdate_pipeline_registers() function.EXMEM_ctrl = EX_ctrl;EXMEM_btgt = EX_btgt;EXMEM_ALUOut = EX_ALUOut;EXMEM_Zero = EX_Zero;EXMEM_rd2 = EX_rd2;EXMEM_RegRd = EX_RegRd;4.5 Simulation programThis is a suggested skeleton of the MIPS simulator.(I have never tested this pseudo-code. Please use it at your own risk.)int memory[256], register[32], PC, inst;main() {int i,cycles_to_halt;initialize(); PC = 512;cycles_to_halt = 1000;// equivalent to 0x200//maximum number of cycles to execute while (true){IF_inst = memory[PC/4];// The instruction word “0000 0000 0000 1100” (or 12) indicates HALT.if (IF_inst == 12) break;if (cycles_to_halt > 0) cycles_to_halt –;if (cycles_to_halt == 0) break; carryout_operations();update_mem();// during the cycle// end of the cycle (rising edge of the clock) // make sure memory are updated in this function onlyprint_results();update_pc(); // end of the cycle (rising edge of the clock)}}initialize() {// Set up and initialize the register array (e.g., register[32]).// your code// Initialize the memory array (e.g. memory[256]) by copying the contents in the input binary file.// Note that it is 128 data words and 128 instruction words, totaling 256 items in the memory array.// The data segment begins at memory[0] while the text segment begins at memory[128].// your codeFILE *sourcefile;sourcefile = fopen(argv[1], “rb”);for (i=0; i> 21) && 31;rt = ___; rd = ___; immed = ___; funct = ___; extend = ___;// ctrl=________;//////RegDst =__; ALUSrc =__; MemtoReg=__; RegWrite=__; MemRead=__; MemWrite=__;Branch=___; BranchNE=___; Jump=__;// rd1 = ___; rd2 = ___;////if (RegDst==0) wn =______;else wn =______; //////////////////////////if (ctrl==1416) {if (funct==32)// R-typeALUOut =_______ ; // addelse if (funct==34) ALUOut = _______; // subelse if (funct==0)else if (funct==2)ALUOut = _______; // sllALUOut = _______; // srlelse if (funct==42) ALUOut = _______; // sltelse if (funct==12) ALUOut = 0;// halt}else if ((ctrl==20) || (ctrl==6)) ALUOut = 0;//beq or bneelse if ((ctrl==704) || (ctrl==544) || (ctrl==896)) ALUOut = ________; //lw or sw or addipc4 = ________;offset = _________;// btgt = __________;////////////Zero = ______;PCSrc = (Branch && Zero) || (BranchNE && !Zero);if (PCSrc == 0) pc_next = pc4;else pc_next= btgt;//when accessing memory, be sure to divide the memory address by four ////////////for example, if (MEM_MemRead) MEM_memout = memory[MEM_ALUOut/4];if (MemRead) memout = _______;//update the destination “register” (RegRd) if RegWrite is 1wd = _____; // if (MemtoReg==0) wd = _____;// else wd = ________;// if (RegWrite==1) register[wn] = _______;}update_mem() {// update memory if appropriate// your code, i.e., if (MemWrite==1) memory[ALUOut]=________;}print_results() {// print the clock count, the content of PC, data memory, and register file as follows// (use hexadecimal for PC; use decimal for memory and register contents)//Cycle = 3//PC = 208 //DM0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0//RegFile0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }update_pc() {// Update pc based on signals as a result of carryout_operations()// update “PC” using pc_next// your code, i.e., PC = _______;}4.6 Simulation program (Project 2 & 3)This is a suggested skeleton of the MIPS simulator.(I have never tested this pseudo-code. Please use it at your own risk.)int memory[256], register[32], PC, IF_inst;main() {int cycles_to_halt;initialize(); PC = 512;cycles_to_halt = 1000;// equivalent to 0x200//maximum number of cycles to execute while (true) {IF_inst = memory[PC/4];// The instruction word “0000 0000 0000 1100” (or 12) indicates HALT.// It does not stop immediately because there are four proceeding instructions in the pipeline// that have to be completed their execution. Thus, it needs to run 4 more cycles.if (IF_inst == 12) cycles_to_halt = 4;if (cycles_to_halt > 0) cycles_to_halt –;if (cycles_to_halt == 0) break; read_pipeline_registers();carryout_operations();// beginning of a cycle// during the cycle// update the destination register early here (the first half of the cycle)// end of the cycle (rising edge of the clock)// make sure memory are updated in this function onlyupdate_mem(); update_pipeline_registers(); // end of the cycle (rising edge of the clock)// make sure pipeline registers are updated in this function onlyprint_results();update_pc(); // end of the cycle (rising edge of the clock)}}initialize() {// Set up and initialize the register file array (e.g., register[32]).// your code// Initialize the memory array (e.g. memory[256]) by copying the contents in the input binary file.// Note that it is 128 data words and 128 instruction words, totaling 256 items in the memory array.// The data segment begins at memory[0] while the text segment begins at memory[128].// your codeFILE *sourcefile;sourcefile = fopen(argv[1], “rb”);for (i=0; i
