Project 2 Solution

Introduction



In this project, we’ll implement in Logisim a single-cycle processor that resembles MIPS. We’ll call the new processor and instruction set, JrMIPS, version 0.9, November 12, 2015. Your processor will be capable of running small programs.




JrMIPS Programmer’s Reference Manual



JrMIPS is a simpli ed architecture. The native word size is 16 bits. That is, instructions and data values are 16 bits wide. Two’s complement and unsigned data types are allowed for data values. There are eight 16-bit registers. There are separate instruction and data memories. The instruction memory can hold up to 256 instructions and the data memory can hold up to 256 data values.




2.1 Instructions




JrMIPS has a small number of instructions:




Opcode
Subop
Format
Instruction
De nition










































0001
0
R
add $rs,$rt
$rs
$rs
+ $rt




0001
1
R
sub $rs,$rt
$rs
$rs
- $rt




0010
0
I
addi $rs,imm
$rs
$rs
+ sxt(imm)


0010
1
I
addui $rs,imm
$rs
$rs
+ zxt(imm)


0011
0
R
and $rs,$rt
$rs
$rs
& $rt




0011
1
R
nor $rs,$rt
$rs
:($rs | $rt)


0100
0
R
sll $rs,shamt
$rs
$rs
shamt


0100
1
R
srl $rs,shamt
$rs
$rs
shamt


1000
X
I
bx $rs,imm
PC
($rs
6=0?
imm :
PC+1)
1001
X
I
bz $rs,imm
PC
($rs = 0 ?
imm :
PC+1)
1010
X
R
jr $rs
PC
$rs






1011
X
I
jal $rs,imm
$rs
PC+1;PC
imm


1100
X
I
j imm
PC
imm






















0111
0
R
lw $rs,$rt
$rs
MEM[$rt]




0111
1
R
sw $rs,$rt
MEM[$rt]
$rs














0000
X
R
put $rs
output $rs to Hex LED display
1111
X
R
halt
stop fetching and set halt LED to red





















In this table, \X" indicates the Subop eld (see below) is not applicable and the value doesn’t matter. Some opcodes are not listed because these codes are reserved for future instructions.




There are some di erences between JrMIPS and the regular MIPS instructions. First, JrMIPS 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:




1



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 ad-dressing. The branches also test the conditions \equal to zero" (branch zero), \not equal to zero" (branch not zero).




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.




2.2 Instruction Format




JrMIPS 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 posn


15-12




11-9


8-6
5


4-1
0






























Field


Opcode
Rs


Rt
unused


Shamt
Subop


















































I Format Instruction




































Bit posn




15-12




11-9
8-1


0




























Field




Opcode


Rs


Imm


Subop



































Rs is the rst 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. In addi, 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 speci es 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 16d, then the target address

for the branch is 16d.




Shamt is used by shift instructions. There are two varieties of shifts. One version encodes the shift amount as a 4-bit unsigned immediate in Shamt. The other version provides the shift amount as a source register. Notice that the left and right shifts of each variety have the same opcode. The shift direction is encoded in Subop. When Subop=0, the direction is left and when Subop=1, the direction is right.




2.3 Registers




There are 8 registers, labeled $r0 to $r7. In JrMIPS, $r0 may hold values other than 0. It is a general register and can be used like any other register. The registers are 16 bits wide.




2.4 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.













2



2.5 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.




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;




an instruction memory; 3) a register le; 4) an instruction decoder; 5) a sign extender; 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 nd it helpful to consult the book and class slides, particularly the diagram of the MIPS processor with control signals and the decoder and data path elements.



For the project, you may use any component (e.g., an 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 nd on the Web or any past CS 447 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 speci c decisions (e.g., control signal settings) with any one else other than the TAs and instructors.




Instruction Implementation



It is easiest to do this project with Logisim’s subcircuits. For the more complicated components in the data path and control (e.g., ALU), de ne a subcircuit. A subcircuit is like a function in a programming language. It can be added, or \instantiated", multiple times in a design.




4.1 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 Decoder 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 should be tied to all state elements (registers and ROM). The state elements in Logisim let you de ne the \trigger event" when a state element captures its inputs. I recommend that you use the default.




4.2 Program Counter




The program counter is a register that holds an 8-bit instruction address. It speci es 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).




4.3 Instruction Memory




This component is a ROM con gured 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 main circuit. The ROM’s contents will hold the instructions for a JrMIPS program. You can set the contents with the Poke tool or load the contents from a le.



















3



4.4 Data Memory




This component is a RAM con gured 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 main circuit. Be sure to read Logisim’s documentation carefully for this component! To simplify the implementation, con gure the RAM’s Data Interface as Separate Load and Store Ports. This con guration is similar to what was described in lecture and the book. Hint: You’ll need to set the RAM’s Sel signal.




4.5 Register File




JrMIPS has 8 registers. An R-format instruction can read 2 source registers and write 1 destination register. Thus, the register le has 2 read ports and 1 write port. The register le is the same one that you implemented in lab, except it has more registers.




4.6 Arithmetic Logic Unit (ALU)




The ALU is used to execute the arithmetic instructions: NOR, AND, ADD, and SUB. It may also be used to do branch comparison. Build the ALU as a subcircuit; 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! A mux is also needed.




4.7 Shifter




Logisim includes a shifter. You can use this component to implement left and right shift operations.




4.8 Sign Extender




Logisim has a built-in sign-extender component, which you can use.




4.9 Decoder




This component takes the instruction opcode as an input and generates control signal values for the data path as outputs. It’s easy to make a decoder subcircuit with Logisim’s Combinational Analysis tool (Window!Combinational Analysis). This tool will automatically build a subcircuit from a truth table. To make the decoder, 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 lled 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: Logisim has a limit on the number of elds in a truth table. So, you may need two (or more!) decoders.




4.10 LED Hexadecimal Display




JrMIPS 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 Logisim’s Hex Digit Display library element (in the Input/Output library). You’ll need 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 xed until the next put is executed (don’t simply wire the hex digits to the register le!). Hint: Use a separate register. The display should only be updated when the put instruction is executed.




4.11 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).







4



4.12 Extracting Instruction Bit Fields




Individual elds in a 16-bit instruction need to be extracted. For example, Opcode needs to be extracted for the decoder. 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.




Assembler



I wrote a rudimentary assembler in Perl. You can get the assembler from the project web site. A separate document on the web site describes the assembler.




Project Suggestions



Building the JrMIPS 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 di erent parts, put them together to implement various classes of instructions. I started with put and halt to make testing easy. After these worked, I added the arithmetic instructions. Next, I tackled branches, and then loads and stores. Finally, I implemented shifts and jumps. You can nd numerous test case programs on the project web site. I recommend that you write and try additional test cases as well.




Subcircuits will make the project easier. To de ne 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 rst. 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 ow 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 di erent 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.




Turning in the Project



7.1 Files to Submit




You must submit a compressed le (.zip) containing:




jrmips.circ (the circuit implementation)




README.txt (a help le; see next paragraph)




Put your name and e-mail address in both les. For the circuit le, use the text widget to list your name and e-mail address. In the README, put the name and e-mail address at the top of the le. The README le should list what works (i.e., instructions implemented) and any known problems with your design. If you have known problems/issues (bugs!) with your design (e.g.,







5



certain instructions don’t work, odd behavior, etc.), then you should clearly specify the problems in this le. 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.




The lename of your submission (the compressed le) should have the format:




For example: firstname-fall2015.zip




Please submit by December 10 at 11:59 PM. Per the course policy on late work, we will accept late projects until December 15. We will not accept late projects after this date because we need to complete all project grading during nals week. It is strongly suggested that you submit your le well before the deadline. If you have a problem during submission, we cannot guarantee to respond at the last minute before the deadline.




7.2 Where to Submit




Follow the directions on CourseWeb for submission.




Collaboration



In accordance with the policy on individual work for CS/COE 447, this project is strictly an individual e ort. Unlike labs, you must not collaborate with a partner. Please see the course web site (syllabus) for more information. Do not view or use past solutions for CS/COE 447 in completing this project. It is your responsibility to secure and back up your les. See the web site for more details about the course policy on collaboration.




8.1 Grading the Project




We will grade the project with multiple test cases, some of which will come from the tests listed on the project web site.




































































































6