A CPU Simulator In this project, you will write a program to simulate the essential part of a CPU to execute a program. The project includes three major components, an instruction assembler and decoder, the CPU simulator itself that executes instructions in five stages (IF, ID, EXE MEM and WB), and a cache simulator. Your final CPU simulator should be able to execute the provided test program and produce the expected results. The three components of the project will first be implemented in Homework #4, #5 and #6 and at the end, you will need to integrate them into one program. While C and Linux are the preferred language and OS for the implementation, you can choose Java or C++, and other OS (Windows or Mac OS X) that you are comfortable with to work on. But the template code you are given to start with is in C only. If you need to choose other languages than C, C++ or Java, please confirm with me first. The CPU supports the following 7 instructions: R-Type arithmetic/logical instruction: add, and sub I-Type memory reference: lw, sw I-Type control transfer: beq, j I-Type add immediate: addi . . . . 1. Assembler, Disassembler and Decoder: Instruction format and decoding An instruction is encoded as a 32-bit word, [31:0]. We use very similar encoding schema as MIPS. 6 bits [31:26] are used for encoding the function of an instruction, according to the following table. Instructions [31:261 bits Decimal number ADD SUB LWR 000001 000010 000011 000100 000101 000110 000111 001000 001001 001010 001011 001100 001101 001110 001111 4 ADDI LW SW 10 BE 12 13 14 15 R-type ALU instructions (add and sub), used in the source code as \"Ins, Rd, Rs, Rt\" format, are encoded as instruction words of [func][Rs][Rt][Rd][unused] format. Please note the order of the three operands in the instruction word is different from the order of the operands in the source code. The func field is [31:26] as mentioned before. Rs, Rt and Rd operands, each with 5 bits, are encoded in the following 15 bits, Rs: [25:21], Rt: [20:16], and Rd: [15:11]. So of a 32-bit instruction word, a R-type instruction onlyy uses 6+15-21 bits. The rest 11 bits are not used. The LW/SW/Beq/Addi I-type instructions, used in the source code as \"LWSWBEQADDI, Rt, Rs, imm\", are encoded as instruction words of [funclTRslTRtImml. Please note the order of the Rt and Rs operands in the instruction word is different from the order of the instruction in the source code. The R:s and Rt operands, each with 5 bits, are encoded as Rs: [25:21] and Rt: [20:16]. The rest 16 bits [15:0] are used for encoding the immediate. The J instruction, used in the source code as \"J absolute-target\", is encoded in an instruction word of [func][absolute-target]. The absolute-target is an immediate encoded in bit [25:0]. You should start from the provided assembler decoder.c file for your implementation. It already includes the support for ADD instruction. You need to read the code and understand the details of how ADD is implemented in the assembler, decoder and disassembler. Your implementation should finish the code in those TODO places to support all the other instructions. While C and Linux are the preferred language and OS for the implementation, you can choose Java or C++, and other OS (Windows or Mac OS X) that you are comfortable with to work on. But the template code you are given to start with is in C only. If you need to choose other languages than C, C++ or Java, please confirm with me first. A test program, test.asm, is provided for testing your implementation. Currently if you compile and run the program with test.asm as following, its output shows that only ADD instruction can be assembled, decoded and disassembled. For other instructions, \"Unrecognized instruction...\" message is printed out. yanyh@vm:/csce212_simcpu$ gcc assembler_decoder.c -o assembler_decoder yanyh@vm:~/csce212_simcpu$ ./assembler_decoder test.asm ADDI, $s3, $S0, 1 # instruction #0, i- 1; # instruction #1, Init N 256 # instruction #2, $s4 has 255 # 3, Jump to the end of the code, use relative address 12 Unrecognized instruction: ADDI, ignore. Unrecognized instruction: ADDI, ignore. Unrecognized instruction: ADDI, ignore. Unrecognized instruction: BEQ, ignore. 0x00635800: ADD, $s11, $S3, $S3 0x016b5800: ADD, $s11, $s11, $s11 0x01622800: ADD, $S5, $s11, $S2 Unrecognized instruction: LW, ignore. Unrecognized instruction: LW, ignore. Unrecognized instruction: LW, ignore. 0x00c74800: ADD, $S9, $s6, $S7 0x01094800: ADD, $s9, $s8, $S9 0x01615000: ADD, $S10, $s11, $S1 Unrecognized instruction: SW, ignore. Unrecognized instruction: ADDI, ignore. Unrecognized instruction: J, ignore. ADDI, $s4, $s0, 256 ADDI, $s4, $S4, -2 BEQ, $S3, $S4, 12 ADD, $s11, $S3, $S3 ADD, $s11, $s11, $s11 ADD, $S5, $s11, $S2 LW $S6, $S5, -4 LW, $S7, $S5, 0 LW, $s8, $s5, 4 ADD, $S9, $S6, $S7 ADD, $S9, $S8, $S9 ADD, $s10, $s11, $s1 SW, $S9, $S10, 0 ADDI, $S3, $S3, 1 J, 3 i = 1*2*2, now $s11 has &B[i] is now in $s5 B[i-1] is now in $s6 B[i] is now in $57 B[i+1] is now in $58 B[i-1] + B[i] # 5, # 6, # 7, # 8, # 9, # 10, i#4 # 12, &A [i] is now in $s10 # 13, A[i] stored the result # 14, i++ # 15, Jump instruction #3 (BEQ instruction, use absolute address) After your implementation, your program should output the same or similar output as in the following screenshot using the test.asm file as input. Your program will be evaluated using another example program when being graded. Your submission needs to include your source code and the screenshot of your execution (similar to mine). yanyh@vm:~/csce212_simcpu$ /assembler_decoder test.asm ADDI, $s3, $s0, 1 ADDI, $s4, $s0, 256 ADDI, $s4, $S4, -2 BEQ, $S3, $S4, 12 ADD, $S11, $S3, $S3 ADD, $s11, $S11, $s11 ADD, $S5, $s11, $s2 LW, $S6, $S5, -4 LW, $S7, $S5, 0 LW, $s8, $S5, 4 ADD, $S9, $s6, $S7 ADD, $S9, $s8, $s9 ADD, $s10, $s11, $s1 SW, $$9, $S10, 0 ADDI, $s3, $$3, 1 J, 3 # instruction #0, i 1; # instruction #1, Init N 256 # instruction #2, $54 has 255 # 3, Jump to the end of the code, use relative address 12 # 4, i=1*2 # 5, i = i*2*2, now $s11 has i*4 # 6, &B[i] is now in $s5 # 7, B[1-1] is now in $s6 # 8, B[i] is now in $57 # 9, B[i+1] is now in $s8 # 10, B[i-1] + B[i] 0x14030001: ADDI, $S3, $S0, 1 0x14040100: ADDI, $S4, $s0, 256 0x1484fffe: ADDI, $S4, $S4, -2 0x3083000c: BEQ, $S3, $S4, 12 0x00635800: ADD, $s11, $S3, $S3 0x016b5800: ADD, $s11, $s11, $S11 0x01622800: ADD, $s5, $s11, $S2 0x20a6fffc: LW, $s6, $s5, -4 0x20a70000: LW, $S7, $s5, 0 0x20a80004: LW, $S8, $S5, 4 0x00c74800: ADD, $s9, $s6, $s7 0x01094800: ADD, $s9, $S8, $s9 0x01615000: ADD, $S10, $s11, $S1 0x25490000: SW, $S9, $s10, 0 0x14630001: ADDI, $S3, $S3, 1 0x3c000003: J, 3 # 12, &A [i] is now in $s10 # 13, A[i] stored the result # 14, i++ # 15, Jump instruction #3 (BEQ instruction, use absolute address) Instruction [25-0ShiftJ 25-0, JTlmm2 eft 2 ump address 131-0] PCnext 26 28 0 Add LI PC+4 Add result BTaddrPC+40rBTaddr Shift left 2 RegDst Jum MemRead Instruction (31-26 C INS31-26, Func MemtoFR MemWrite RegWrite Control ALU PC PCnekt Instruction [25-21 Read PCRead INS25-21, RSselectregister 1 Read RSvalue, ALU Instruction [20-16Read address data 1 Instruction lNS20-16, RTselect register 2 MEMout ALUout 31-0 MWrite2 Instruction |||Instruction [15-11] gister data 2 ALUin2 result +Address Rea ul memory INS15-11, RDselectWrite data Registers Write Data data memory RWselect RTvalue, MEM 16 Sign- extend 32 Instruction [15-0) INS15-0, Imm ALU control ALUout ignore Instruction [5-0] RWvalue ignore FIGURE 4.24 The simple control and datapath are extended to handle the jump instruction. An additional multiplexor (at 2. CPU Functional Simulator The second component of the project is to create a functional simulator of CPU of the above diagram using a program. In the program, CPU components (instruction memory, registers, ALU, and data memory), datapath, control signal and logic in the CPU diagram are implemented in the source code to support the designed 7 instructions. Question 1 and 2 of Homework 5 give you some exercises on how data are moved on the datapath and how control signals are set and used by the CPU when an instruction is being executed. Your program implements those data movement and logics in the program, simulating a real CPU execution. The initial part of program is already provided to you, cpusim.c. The program includes most of the implementation of the simulator and you need to add the code in the TODO place:s in the program Your tasks: Read the code and comments first to understand the overall structure of the simulator code and then fill in code in those TODO places to complete the simulator for the 7 instructions. When you add code in those TODO places, you should refer to the CPU diagram for adding statements for setting datapath and control. Execute the simulator program with provided input and collect trace data: The test.asm program and its binary test.asm.bin are provided for you to test your implementation. The test.asm.bin program is the binary program created from the test.asm file by the assembler. The test.asm is different from the file in the homework 4 since we introduced addi instruction. The assembler program is also revised and provided to you so you can assembly the test.asm program to binary program (test.asm.bin) if you need to make changes of the test.asm file. You are welcome to revise your own assembler, but not required. If you do not plan to change the test.asm file, you can just use the test.asm.bin file provided to test your CPU simulator. When you are working on your simulator program (cpusim.c), you should run with test.asm.bin as input The program will run and save the program execution into a trace file named \"cpusim trace.txt\" Without changing anything of the cpusim.c file, if you compile it and execute the program with test.asm.bin input, it will output \"Verification Failed\" message and the trace will contain more information as follows. (cat is the command to list the content of a file.) yanyh@vm: /csce212_simcpu$ gcc cpusim.c -o cpusim yanyh@vm: /csce212_simcpu$ ./cpusim test.asm.bin Verification Failed! yanyh@vm: /csce212_simcpu$ cat cpusim_ trace.txt Fetch instruction 14030001 at PC 0 Decode instruction (fun rs rt rd Imm JTImm) ADDI 0 3 0 1 196609 Fetch register: Rs: Reg [0]-0, Rt: Reg [3]-0 EXE: Ops ADD, ALUout: 0, Zero: 0, BTaddr: 0 MEM: PCnext: 0 Simulation goes to infinite loop of test.asm program, terminate it Verification failed: VA[1]: -850272457, Sim Number: 0 Verification failed: VA [2] 716293359, Sim Number: 0 Verification failed: VA[3]: 1122055173, Sim Number: 0 Verification failed: VA[4]: -788691734, Sim Number: 0 Verification failed: VA[5]: -1589852331, Sim Number: 0 Verification failed: VA[6]: 1805886067, Sim Number: 0 Verification failed: VA [7]: -1511266276, Sim Number: 0 Verification failed: VA[8] -1247878484, Sim Number: 0 Verification failed: VA[9]: -1159732566, Sim Number: 0 Verification failed: VA[10]: -576257088, Sim Number: 0 Verification failed: VA[11]: -718276064, Sim Number: 0 Verification failed: VA [12]: 2650504, Sim Number:0 Verification failed: VA[13]: -348487530, Sim Number: 0 After you make changes and you should compile and run the program with test.asm.bin as input. If you do it correctly, the program output and content of the trace file will be as follows: yanyh@vm:~/csce212_simcpu$ gcc cpusim.c -o cpusim yanyh@vm/csce212_simcpu$./cpusim test.asm.bin Simulation and Verification Passed Successfully! yanyh@vm: /csce212_simcpu$ less cpusim_trace.txt Fetch instruction 14030001 at PC 0 Decode instruction (fun rs rt rd Imm JTImm ADDI 0 3 0 1 196609 Fetch register: Rs: Reg [0]-0, Rt: Reg [3]-0 EXE: Ops ADD, ALUout: 1, Zero: 0, BTaddr: 8 MEM: PCnext: 4 WB: Reg [3]1 Fetch instruction 14040010 at PC 4 Decode instruction (fun rs rt rd Imm JTImm ADDI 040 16 262160 Fetch register: Rs: Reg [0]-0, Rt: Reg [4]-0 EXE: Ops ADD, ALUout: 16, Zero: 0, BTaddr: 72 MEM: PCnext: 8 WB: Reg [4] - 16