CS 447 Computer Organization and Assembly Language

CS 447 Computer Organization and Assembly Language
Luis Oliveira General Info Syllabus Schedule Resources Labs Projects
Project 3: ¦ÌMIPS
Released: 23:59 Tuesday, November 14th, 2023. Due: 17:59 Friday, December 8th, 2023.
Let’s make a CPU
Introduction
In this project, we¡¯ll implement in Logisim a single-cycle processor that resembles MIPS. We¡¯ll call the new processor and its implementation ¦ÌMIPS, version 0.9.9, November 14th, 2023. Your processor will be capable of running small programs.
Start early
The deadline is close to the end of the semester. Life happens, sickness happens, so if you start early you can minimize the impact.
Do a little bit every day! 1 hour every day! 30 minutes every day! SOMETHING!
You know you will have questions, and if you decide to ask them in the last week, I may not be able to answer them all!
¦ÌMIPS Programmer¡¯s Reference Manual
¦ÌMIPS is a simplified architecture. The native word size is 16-bits. That is, instructions and data values are 16-bits wide. ¦ÌMIPS data can be both unsigned, and signed using two¡¯s complement. There will be 8 registers ($r0-$r7) for general-purpose use. Important: Instruction and data memory will be separate! The instruction memory can hold up to 256 instructions, and the data memory can hold up to 256 data values.
Instructions
¦ÌMIPS has a small number of instructions: (Grouped by purpose)
Opcode Subop Format 0000 0 R
0010 0 R 1010 0 R 0110 0 R 1110 0 R
0001 0 R 1001 0 R
0101 0 R 1101 0 R
1111 X R 1011 X R
Instruction
add $rs, $rt
sub $rs, $rt
nand $rs, $rt
or $rs, $rt
addui $rs, imm
addi $rs, imm
div $rs, $rt
mul $rs, $rt
srlv $rs,$rt
sllv $rs,$rt
lw $rs, $rt
sw $rs, $rt
li $rs, imm
bp $rs, imm
bn $rs, imm
bx $rs, imm
bz $rs, imm
jal $rs, imm
Definition
$rs¡û$rs+$rt
$rs¡û$rs-$rt
$rs¡û$rs&$rt
$rs ¡û ~($rs | $rt)
$rs ¡û $rs + zero_extend(imm)
$rs ¡û $rs + sign_extend(imm)
$lo¡û$rs¡Â$rt;$hi¡û$rsmod$rt
$hi:$lo ¡û $rs ¡Á $rt
$rs ¡û $rs >> ($rt & 0x0F)
$rs ¡û $rs << ($rt & 0x0F) $rs ¡û $lo $rs ¡û $hi $rs ¡û MEM[$rt & 0xFF] MEM[$rt & 0xFF] ¡û $rs $rs ¡û zero_extend(imm) PC¡û($rs>0?imm:PC+1)
PC¡û($rs<0?imm:PC+1) PC¡û($rs¡0?imm:PC+1) PC¡û($rs=0?imm:PC+1) $rs¡ûPC+1;PC¡ûimm stop fetching and set halt LED to red output $rs to Hex LED display In this table, ¡°X¡± indicates the Subop field (see below) is not applicable and the value doesn¡¯t matter. In other words, it can be any number! Some opcodes are not listed because these codes are reserved for future instructions. There are some differences between ¦ÌMIPS and the regular MIPS instructions. First, ¦ÌMIPS is a ¡°two- operand¡± instruction set. An instruction has at most two operands, including source and destination operands. In this instruction set style, one of the source operands (registers) is also the destination. For example, consider the add instruction: add $r2, $r3 This instruction will add the contents of source registers $r2 and $r3 and put the result into destination register $r2. Register $r2 is used both as a source operand and a destination operand. Most instructions behave like their MIPS counterparts. An important exception involves branches, which use absolute addressing to specify a target address rather than PC-relative addressing. The branches also test the conditions ¡°equal to zero¡± (branch zero), ¡°not equal to zero¡± (branch not zero), ¡°less than zero¡± (branch negative) and ¡°greater than zero¡± (branch positive). The put instruction causes the contents of $rs to be output to a LED hexadecimal display. This instruction will assist in debugging. The halt instruction causes the processor to stop and a stop LED to turn red. Instruction Format ¦ÌMIPS has two instruction formats: R and I. R is used for instructions that have only registers and I is used for instructions with an immediate. The formats are: R Format Instruction Bit position 15-12 11-9 Field Opcode Rs Rt unused Subop I Format Instruction Bit position 15-12 11-9 8-1 0 Field Opcode Rs is the first source register and Rt is the second source register. Rs is the destination register. Imm is an 8-bit immediate. The immediate is signed in addi and unsigned in addui, bn, bx, bp, bz, jal, and j. For the addition instructions with an immediate (i.e., addi and addui), the bit Subop controls whether the immediate is sign or zero extended. When Subop is 0, then Imm is zero extended to implement the addui instruction. Otherwise, Imm is sign extended to implement addi. Imm is zero extended for branches and jump (j). In branches, jal and j, Imm specifies the target address. Both branches and jumps use absolute addressing for the target address. So, for example, if a branch is taken and Imm is 0x1a, then the target address for the branch is 0x1a. There are eight general-purpose registers, labelled $r0 to $r7. The registers are 16-bits wide. Instruction Addresses The instruction memory holds 256 instructions. Each instruction is 16 bits wide. An instruction address references a single instruction as a whole. Thus, an instruction address has 8 bits to specify one of 256 instructions in the memory. Data Addresses The data memory holds 256 16-bit data words. A data address references a single data word as a whole. Thus, a data address has 8 bits to specify one of 256 words. Note: The notation MEM[$rt & 0xFF] means that only the 8-LSB of $rt are used! 0xFF is a mask. Project Requirements Your job is to implement this architecture! Your processor will be a single cycle implementation: in one cycle, the processor will fetch an instruction and execute it. Your implementation will need several components: 1) a program counter and fetch adder; 2) an instruction memory; 3) a register file; 4) an instruction decoder (aka the controller); 5) one or more sign extenders; 6) an arithmetic logic unit; 7) a data memory; 8) an LED hexadecimal display; and, 9) an LED to indicate the processor has halted. You¡¯ll also need muxes as appropriate. For the most part, these components are quite similar to what we¡¯ve talked about in lab and lecture. You will find it helpful to consult the class slides, particularly the diagram of the MIPS processor with control signals, the controller and data path elements. For the project, you may use any component (e.g., a 16-bit adder) from Logisim¡¯s built-in libraries. This makes the project much simpler! All other components must be implemented from scratch. Don¡¯t use or look at components that you might find on the Web or any past CS 0447 project! If you do look at this past material, this is considered cheating according to the course policy. The usual policy about outside help applies for this assignment: It is not allowed. You may talk about how to approach the project with others, but you are not allowed to show your design or discuss specific decisions (e.g., control signal settings) with any one else other than the instructor, TAs or the CS resource center help desk. Starting the project Start by downloading this archive with some circuits to get you started. The archive contains 3 files where you will have to implement some parts of your CPU design: 1. RegFile.circ - In this file, you will implement your Register File. I¡¯ve defined the ports you must to use, please do not modify them, or the autograder will fail. 2. ALU.circ - In this file, you will implement your ALU. I¡¯ve defined the ports you must to use, please do not modify them, or the autograder will fail. 3. umips.circ - In this file, you will implement your CPU. This file will include the bulk of your CPU design. Instruction Implementation It is easiest to do this project with Logisim¡¯s subcircuits. For the more complicated components in the data path and control, define a subcircuit. A subcircuit is like a function in a programming language. It can be added, or ¡°instantiated¡±, multiple times in a design. Clock Methodology A clock controls the execution of the processor. On each clock cycle (a rising and falling edge), an instruction is fetched from the Instruction Memory. The instruction is input to the Controller to generate control signal values for the data path. The control signals determine how the instruction is executed. You¡¯ll need a single Clock element in your design. This clock will be tied to all state elements (registers and ROM). The state elements in Logisim let you define the ¡°trigger event¡± when a state element captures its inputs. Program Counter The program counter is a register that holds an 8-bit instruction address. It specifies the instruction to fetch from the instruction memory. It is updated every clock cycle with PC + 1 or the target address of a taken branch (or jump). Instruction Memory This component is a ROM configured to hold 256 16-bit instructions. You should use the ROM in Logisim¡¯s Memory library. In your implementation, the ROM must be visible in the umips.circ main circuit. The ROM¡¯s contents will hold the instructions for a ¦ÌMIPS program. You can set the contents with the Poke tool or load the contents from a file. Data Memory This component is a RAM configured to hold 256 16-bit words. You should use the RAM in Logisim¡¯s Memory library. In your implementation, the RAM must be visible in the umips.circ main circuit. Be sure to read Logisim¡¯s documentation carefully for this component! To simplify the implementation, configure the RAM¡¯s Data Interface as Separate Load and Store Ports. This configuration is similar to what was described in lecture and the book. Hint: You¡¯ll need to set the RAM¡¯s Sel signal. Register File For the general-purpose registers, ¦ÌMIPS has 8 registers. An R-format instruction can read 2 source registers and write 1 destination register. Thus, the register file has 2 read ports and 1 write port. The register file design is the similar to the one that you implemented in lab, except it has more registers. I¡¯ve given you a file register RegFile.circ containing the skeleton for your register file. You should not change, move, add, or remove any of the ports in it, and you must use them. These ports will allow you to submit your design to the autograder (see submission details) that can give you immediate feedback on your solution. Arithmetic and Logic Unit (ALU) The ALU is used to execute the arithmetic (including multiplication and division) and the logic instructions. It is also be used to do branch comparison. Build the ALU in the ALU.circ file I¡¯ve given you; it is similar to the ALU described in lecture. Be sure to use Logisim¡¯s multi-bit Arithmetic library subcircuits; most of what you need is already here! At least a mux is also needed (likely more). The ALU for our CPU will also need some extra registers. Remember HI and LO in MIPS? Well ¦ÌMIPS uses a similar approach. When ¦ÌMIPS multiplies 2 16-bit numbers the result can take up to 32-bits. As such, the destination of the MUL instruction is not the register file. Instead, your ALU will contain 2 special-purpose registers to store the result of the multiplication. In fact, when the ALU does a multiplication, the output should be Zero; only the ALU registers (HI and LO) change. For division, the same registers are used. When running a DIV command, HI should contain the remainder of the division; and LO should contain the quotient of the division. As with the Register File, I¡¯ve given you an ALU skeleton in ALU.circ . You should not change, move, add, or remove any of the ports in it, and you must use them. These ports will allow you to submit your design to the autograder (see submission details) that can give you immediate feedback on your solution. The ALU has 3 inputs: (1) A and (2) B are the operands, and (3) ALUOp is the signal that configures the ALU to do each operation. The ALU has 6 outputs: (1) Result is the main output of the ALU and it¡¯s value depends on the operation being executed, (2) HI outputs the contents of the HI- register used by the mul and div instructions, (3) LO outputs the contents of the LO-register used by the mul and div instructions. The remaining 3 outputs are (4) GT , (5) Zero , and (6) LT ; these outputs are set to 1 whenever input A is respectively greater than, equal to, or less than The following table shows which operation must be executed by the ALU based on the ALUOp. Operation ALUOp Note that the value all other 5 outputs does not depend on the ALUOp signal, only on the inputs: GT Zero LT 1 if A>0; 0 otherwise
1 if A==0; 0 otherwise
1 if A<0; 0 otherwise 16 LSB of multiplication / Quotient of division It¡¯s a register, so there is 1 clock of delay! Multiplier and Divider 16 MSB of multiplication / Remainder of It¡¯s a register, so there is 1 clock of division delay! Logisim includes a multiplier and divider. You can use these components to implement the mul and div instructions. The multiplier has two output pins: result and carry-out. The low portion of the full result from multiplication is Output; the high portion is Carry-Out. The low portion is written to register $LO in the ALU, and the high portion is written to register $HI in the ALU. Likewise, the divider has two output pins: the Output pin is the quotient (put in $LO) and the Remainder pin is the remainder (put in $HI). Division-by-zero is undefined. The processor should ignore this error situation. Logisim¡¯s Divider treats division-by-zero as division by 1 (divider = 1), and so should you. Sign Extender Logisim has a built-in sign-extender (signed and zero extension) component, which you can use. Controller This component takes the instruction opcode as an input and generates control signal values for the data path as outputs. There are several ways you can approach this problem: 1. (recommend)Useadecoderlikesuggestedintheslidestodecodewhichinstructionisexecuting. Then, using that information as in the example available in the schedule, create the control signals using OR-gates and priority encoders. 2. It¡¯salsoeasytomakeadecodersubcircuitwithLogisim¡¯sCombinatorialAnalysistool (Window¡úCombinatorial Analysis). This tool will automatically build a subcircuit from a truth table. To make the controller, list the opcode bits (from the instruction) as table inputs and the control signals as outputs. For each opcode, specify the output values of the control signals. Once you¡¯ve filled in the table, click Build to create the circuit. To make your main circuit prettier, the opcode inputs and ALU operation outputs can be combined into multi-bit input and output pins using Splitters. Hint: Make sub-subcircuits within the controllers, one for each control signal, to make the design manageable. LED Hexadecimal Display ¦ÌMIPS has a four digit hexadecimal (16 bit) display. put outputs a register value to this display. The contents of a put¡¯s source register (16-bit value) is output on the display. A value that is ¡°put¡± must remain until the next put is executed. To implement the LED Hexadecimal Display, you should use the Logisim¡¯s Hex Digit Display library element (in the Input/Output library). You¡¯ll need the four Hex Digit Displays, where each one shows a hex digit in the 16-bit number. A way is also needed to make the display stay fixed until the next put is executed (don¡¯t simply wire the hex digits to the register file!). Hint: Use a separate register. The display should only be updated when the put instruction is executed. Halting Processor Execution When halt is executed, the processor should stop fetching instructions. The main circuit must have an LED that turns red when the processor is halted. Hint: A simple way to stop the processor is to AND the program counter control with a halt control signal (that also turns on the LED). Extracting Instruction Bit Fields Individual fields in a 16-bit instruction need to be extracted. For example, Opcode needs to be extracted for the controller. Likewise, register numbers and the immediate have to be extracted. This operation can be done with a subcircuit that has splitters connected to appropriate input and output pins. This component will simplify your main circuit drawing. Prof. Bruce Childers wrote a rudimentary assembler in Perl. I modified it for our project. You can get the assembler from the course website. A separate document describes the assembler. You can download two example programs from: - example_1.asm - example_2.asm If you want the pre-assembled versions: - example_1.m. - example_2.m. - example_2.dat. Note: wilkie (he taught this course before) wrote a JavaScript tool that provides you a self- contained, available everywhere place to assemble your programs umipsasm-js!! In his own words: ¡°Enjoy the hours of my life I will not get back.¡± 🙂 Currently, there is an error message being printed together with the output of the assembler. Please ignore it (aka don¡¯t copy it 🙂 About the autograder Testing a CPU is not an easy task. As such the Autograder has some limitations you need to be aware of. 1. It¡¯snotahumangrader.Ifyoudeviatefromtheprojectdescription,youwillhaveabadtime.Ask for help. 2. Theremultipletests: 1. TesttheALU-RunstestsonyourALUcircuit 2. TesttheRegisterFile-RunstestsonyourRegisterFilecircuit 3. TesttheCPUinstructions-RunstestonallCPUinstructions 3. Notallinstructionscanbetestedwithoutassumptions The consequence is: The autograder will test instructions following a certain sequence. You should implement your instructions in the same order because the latter tests expect the earlier tested instructions to be working. Instruction Expected to be working put halt, li nand halt, li, put or halt, li, put add halt, li, put addui halt, li, put addi halt, li, put sub halt, li, put sllv halt, li, put srlv halt, li, put mul halt, li, put, sllv, addui div halt, li, put, sllv, addui mfhi halt, li, put, sllv, addui mflo halt, li, put, sllv, addui bp halt, li, put, addi bn halt, li, put, addi bx halt, li, put, addi bz halt, li, put, addi j halt, li, put jal halt, put jr halt, li, put lw halt, li, put sw halt, li, put, lw Project Suggestions Building the ¦ÌMIPS processor is like writing a program. Plan your design carefully before trying to implement anything. Once you have a good plan, implement the design in small parts. Test each part independently and thoroughly to make sure it behaves as expected. Once you have the different parts, put them together to implement various classes of instructions. E.g. start with put, li and halt to make testing easy. After these work, add the arithmetic instructions. Next, tackle branches, and then loads and stores. Finally, implement jumps. I strongly suggest that you implement simple test cases as you progress in the project. The test cases should check that each of the instructions works. By starting with put and li, you will have an easy way to check the remaining instructions. To test instructions, use li to set registers to specific values. Next, use the instruction being tested on those values. Finally, use put to output the result of the instruction to the Hex display so you can visually check that the instruction under test computed the expected result. Repeat this process for each instruction; be sure to test all cases (e.g., does sign extension in addi work with a negative value?). Assuming li, put and halt work, here is an example to test add: Subcircuits will make the project easier. To define a subcircuit, use the Project¡úAdd Circuit menu option. Next, draw the subcircuit. Finally, add input and output pins to the subcircuit. Be sure to label each pin (i.e., set the pin¡¯s Label attribute). Once you¡¯re done with the subcircuit, double click the main circuit in the design folder (on the left side of the window). This will switch to the main circuit. Now, the subcircuit will appear in the design folder. It can be instantiated (added) in the main circuit by selecting and placing it in the main circuit. The subcircuit should be wired to the main circuit through its input and output pins. Logisim isn¡¯t smart about how it handles changes to instantiated subcircuits. If you make changes to a subcircuit that is already instantiated, I recommend that you delete it from the main circuit first. Then, make your changes and re-instantiate it. See Logisim¡¯s subcircuit tutorial. When you build your main circuit, follow a few conventions to make it easier to understand. First, wire your data path in a way that data signals flow from left to right (west to east). Second, wire control inputs so they run bottom to top (south to north). As a consequence of these two guidelines, put data input pins on the left and data output pins on the right in a subcircuit. Control input pins should be on the bottom of the subcircuit. Third, leave plenty of space between different elements in the design. This will make it easier to add more elements and route wires cleanly. Finally, try to route wires in straight lines as much as possible, and make judicious use of tunnels! Submission instructions You will need to make the usual Gradescope submission for autograding. Yes, this project will partially autograded using Gradescope. Note however: The gradescope grade will not be your final grade for the project! (Check rubric below) Go to the gradescope website and login with your Pitt credentials. Navigate to the Project 3 submission page, and upload your submission (check below!). Submit ALL your project files! and a README.txt There should be no folder!, just the following files: Your ALU.circ. Put your name and username at the top of the file using a label! Your RegFile.circ. Put your name and username at the top of the file using a label! Your umips.circ. Put your name and username at the top of the file using a label! A README.txt file. DO NOT SUBMIT A README.DOCX. DO NOT SUBMIT A README.PDF. SUBMIT A PLAIN TEXT FILE. PLEASE. It should contain: Your Pitt username Your Pitt e-mail address Anything that works (i.e., instructions implemented) Any known problems with your design The purpose of each control signal with sufficient detail that the grader can understand your approaches without further inspecting the circuit. Note: If you have known problems/issues (bugs!) with your design (e.g., certain instructions don¡¯t work, odd behaviour, etc.), then you should clearly specify the problems in this file. The explanation and bug list are critical to grading. So, if you¡¯re uncertain whether to include something, then err on the side of writing too much and just include it. Submit into the cs447-submissions Box folder I have shared with you. Your Box folder (you have 50GB!) is accessible through http://my.pitt.edu. When you see your file within the shared folder, you know you have uploaded it successfully. If you would like to resubmit, you can copy the file in again. Let me know immediately if there are any problems submitting your work. Here is the rubric for assignment of points out of a maximum 100 points. Points relate to both the presence of the necessary components and their correctness. li $r0,0x1 # source operand 1: value 1 halt # end program li $r1,0x2 # source operand 2: value 2 add $r0,$r1 # result in $r0 should be 3 (1 + 2) put $r0 # hex display should show 0x0003 Processor Component - Not autograded Clock and Program counter (must be visible on main of umips.circ) Appropriate sign extender(s) Branch and Jump Controls Controller/decoder, including choice of control signals Hex Displays and ¡°halt¡± LED Processor Component - Autograded ROM (instructions), RAM (data) memories Register File ALU (support for arithmetic and logic operations) Instruction Set Functionality - Autograded Output, load immediate, and halt instructions Arithmetic and logical operations (nand, or, add, etc.) Memory operations (lw, sw) Branch operations (bp, bn, bx, bz) Multiplications and division operations (div, mul, mfhi, mflo) Jump operations (jr, jal, j) Documentation README that describes problems and strategy employed. Test Programs Maximum Points Some of you want some test programs?? Ok. You got it. You probably still want to write small programs to test individual instructions. This is not exhaustive of all instructions. Having all of these programs ¡°work¡± does not imply your processor is correct. Iterative Fibonacci Multiply Sequence test_itr_fibo.asm test_mul.asm test_bitfields.asm Machine Code test_itr_fibo.m test_mul.m test_bitfields.m Shows ¡°8¡± as output Multiplies 1 x 2 x 3 x 4 x 5, showing each step, shows ¡°78¡± as output Encodes an ¡®add $rs, $rt¡¯ instruction. Outputs: ¡°14C0¡± Recursive Fibonacci test_rcr_fibo.asm test_rcr_fibo.m Shows ¡°5¡± as output Divide Sequence Divides 120 by 5, then that result by 4, by test_div.asm test_div.m 3, by 2, and then 1, showing each step, shows ¡°1¡± as output Code Help
Collaboration Policy
You cannot work with one other person on your project. According to course policy! Do not view or use past solutions for CS/CoE 0447 in completing this project. See the course web site for more details about the course policy on collaboration.
Backups!!!!!!!!!!!!!!
It is your responsibility to secure and back up your files. Please backup! Accidents happen! BACKUP!!!
From the syllabus:
It is your responsibility to backup your work regularly. Please consider using reliable and multiple ways to protect your files! I.e.: Please make backups, and backups of your backups, and… (you get the point!) The University offers space that you can use for backups through Box, if you like. Both Google Drive and Dropbox have free tiers that also work well. No extensions for assignments will be approved due to failed laptops, hard drive crashes, lost USB drives, or other calamities that lead to lost or corrupted data. Per the policy on voluntary late assignments, you may turn in a project up to five days late (with a penalty), which should give sufficient time to recover a lost/corrupted project.
CS 447 Computer Organization and Assembly Language
CS 447 Computer Organization and luisfnqoliveira CS 0447 // M-W Assembly Language

Code Help, Add WeChat: cstutorcs