Project 2 Solution

We have just spent the last few weeks implementing our 16-bit datapath. The simple 16-bit LC-2200 is capable of performing advanced computational tasks and logical decision making. Now it is time for us to move on to something more advanced. We have invested a great deal of time and money into developing a more powerful LC-2200 computer. This one is 32-bit and supports interrupts. The only trouble is that the interrupt support does not appear to be completed. We are quite disappointed by this, and so it is your assignment to fully implement and test interrupts using the provided datapath and Logisim. In this project, you will add the additional support needed to make all this work properly. Your job will be to hook up the interrupt acknowledgment lines to the input devices, modify the datapath to support interrupt operations, and write an interrupt handler to increment a clock value at a designated memory address.




 
Requirements




Part 1 - Add hardware support for handling interrupts.




Part 2 - Add microcontroller support for handling interrupts. Part 3 - Code an interrupt handler for the clock.




Extra Credit - Implement support for another interrupt!




Use the VirtualBox VM Image you previously downloaded for Project 1.




Alternatively, use 32-bit Ubuntu or Debian. Click here to download Ubuntu 14.04 32 bit.




Download build essentials for linux as needed. If you are using Mint/Ubuntu/Debian type in sudo apt-get install build-essential.




Download the proper version of Logisim. Be sure to use the most updated version. DO NOT USE BRANDONSIM FROM CS 2110! Click here to go to the download page. The VM image we provide you has Logisim ready to go.




Logisim is not perfect and does have small bugs. In certain scenarios, les have been corrupted and students have had to re-do the entire project. Please back up your work using some form of version control, such as a local git repository.




 
What We Have Provided




A reference guide to the LC 2200-32 located in Appendix B: LC 2200-32 Processor Reference Manual.




PLEASE READ THIS FIRST BEFORE YOU MOVE ON!




An INCOMPLETE LC 2200-32 datapath circuit. You'll need to add interrupt support for this.




An intergenerator subcircuit which will generate an interrupt signal every so often (this is also called the \clock").




The complete microcode from project 1, to which you will have to add interrupt support. The compiler for the microcode.




An INCOMPLETE assembly program (prj2.s) to run on the datapath to test interrupt support. An assembler to assemble your interrupt handling program.




A example.s le that shows how to use the bonus instructions - For extra credit only

Project 2 CS 2200 - Systems and Networks










 
Initial Interrupt Hardware Support




For this part of the assignment, you need to add hardware support for interrupts to the LC2200-32 datapath. You have been provided with a completed LC2200-32 datapath from project 1. Keep in mind this is a 32-bit implementation; the LC2200 in project 1 was a 16-bit implementation.




You must do the following:




 
Create an Interrupt Enabled Register (IE) so we can keep track of whether or not interrupts are currently enabled or disabled.




 
Sometimes the processor might be busy when an interrupt is raised. (Think of some cases that might cause this behavior for our simple processor.) So, we need to keep track of whether or not an interrupt is pending. Additionally, we need to continue asserting it to the microcontroller until the processor responds with an IntAck signal to let the device know it is ready to handle the interrupt. (What happens if we don't catch the interrupt? Hint: Consider how long (in clock cycles) the device is raising its interrupt. Analyze the intergenerator circuit if you need to.) Once the INTA signal is received, the device should drive its device index onto the bus. Use 0x1 as the device index.




 
Modify the datapath so that the PC starts at 0x10 when the processor is reset. Normally the PC starts at 0x00, however we need to make space for the interrupt vector table. Therefore, when you actually load in the code you wrote in part 2, it needs to start at 0x10. Please make sure that your solution ensures that datapath can never execute from below 0x10 - or in other words, force the PC to drive the value 0x10 if the PC is pointing in the range of the vector table.




 
Create hardware to support selecting the register $k0 within the microcode. This is needed by some interrupt related instructions. HINT: Use only the register selection bits that the main ROM already outputs to select $k0.




 
Microcontroller Interrupt Support




Before beginning this part, be sure you have read through Appendix B: LC 2200-32 Processor Refer-




ence Manual and Appendix A: Microcontroller Unit and pay special attention to the new instruction set.




In this part of the assignment you will modify the microcontroller and the microcode of the LC 2200-32 to support interrupts. You will need to to the following:




 
Be sure to read the appendix on the microcontroller and look at its implementation in the LC-2200-32.circ le as there are instructions and guidance for what needs to be supported.




 
Modify the microcontroller to support asserting three new signals:




 
LdEnInt & DrEnInt to control whether interrupts are enabled/disabled




 
IntAck to send an interrupt acknowledge to the device.




 
Extend the size of the ROM accordingly.




 
Fully hook up the microcontroller to the datapath before continuing (our version is not 100% hooked-up).




 
Add the fourth ROM described in the appendix to handle onInt.




 
Modify the FETCH macrostate microcode so that we actively check for interrupts. Normally this is done within the INT macrostate (as described in chapter 4 of the book and in the lectures) but we are rolling this functionality in the FETCH macrostate for the sake of simplicity. You can accomplish this by doing the following:




 
First check to see if an interrupt was raised.

Project 2 CS 2200 - Systems and Networks










 
If not, continue with FETCH normally.




 
If an interrupt was raised, then perform the following:




 
Save the current PC to the register $k0.




 
Disable interrupts.




 
Assert the interrupt acknowledge signal (IntAck). Next, take the device index on the bus and use it to index into the interrupt vector table at (0x01) and retrive the new PC value. This new PC value should the be loaded into the PC. This second step can either be done during the same clock cycle as the IntAck assertion or the next clock cycle (depending on how you choose to implement the hardware support for this in part 1).




Note: To do this new conditional in the FETCH macrostate, we have supplied you with a new attribute of the state tag called onInt. onInt works in the same manner that onZ did in project 1. The processor should branch to the appropriate microstate depending on the value of onInt. onInt should be true when interrupts are enabled AND when there is an interrupt to be acknowledged.




 
Implement the microcode for the three new instructions for supporting interrupts as described in Chapter 4. These are the EI, DI, and RETI instructions. You need to write the microcode in the main ROM controlling the datapath for these three new instructions. Keep in mind that:




 
EI sets the IE register to 1.




 
DI sets the IE register to 0.




 
RETI loads $k0 into the PC, and enables interrupts.




 
Implementing the Interrupt Handler




Our datapath and microcontroller now fully support interrupts BUT we still need to implement an interrupt handler within prj2.s to support interrupts without interfering with the correct operation of any user programs. In prj2.s we provide you with a program that runs in the background. For part 3 of this project, you have to write an interrupt handler for the clock device (Intergenerator). You should refer to Chapter 4 of the textbook to see how to write a correct interrupt handler. As detailed in that chapter, your handler will need to do the following:




 
First save the current value of $k0 (the return address to where you came from to the current handler), and the state of the interrupted program.




 
Enable interrupts (which should have been disabled implicitly by the processor in the FETCH macrostate).




 
Implement the actual work to be done in the handler. In the case of this project, we want you to increment a clock variable in memory.




 
Restore the state of the original program and return using RETI.




The handler you have written should run every time the clock interrupt is triggered. Even though there is only one interrupt for this project, the handler should be written such that interrupts can be nested (higher priority interrupts should be allowed while running handler). With that in mind, interrupts should be enabled for as long as possible within the handler. Furthermore, you will need to do the following:




 
Load the starting address of the handler into the interrupt vector table at address 0x00000001.




 
Write the interrupt handler (should follow the above instructions or simply refer to chapter 4 in your book). In the case of this project, we want the interrupt handler to keep time in memory at some predetermined locations:




 
0xFFFFFC for seconds




 
0xFFFFFD for minutes

Project 2 CS 2200 - Systems and Networks










(c) 0xFFFFFE for hours




Assume that the clock interrupt res every second.




 
Complete the two FIXMEs located in prj2.s. You should read through this le as it contains more information about this part of the project.




 
Extra Credit - Implement Keyboard Interrupt (25 Bonus Points)




Make sure that everything upto this point is working correctly before you attempt this section




For extra credit, Once you have a working clock interrupt handler, as described in the above sections, you may wish to add support for another interrupt. Use the Keyboard located in the Input/Output sub menu of logisim, to create a keyboard device. Now you will need to add support in your computer to do the following:




 
Add support in the datapath for the second device




 
Add support in the microcontroller for the second device, that is choose between which interrupt to handle. The clock has a higher priority than the keyboard.




 
Add support in the handler (prj2.s) to store the result from the keyboard to memory starting at location 0xEEEEE0 going towards increasing memory addresses. The processor has 16 IVT entries, one of them is the clock handler make another one the keyboard handler address.




Hints:




A priority encoder might be useful in choosing between interrupts from di erent devices.




The compiler supports bonus instructions (see appendix B and example.s le for how to use them). You may nd it necessary to implement these in the microcode and use them for controlling the second device.




Note: Both the clock and the keyboard interrupt should be working at the same time to receive credit for this portion!!!




 
Deliverables




Please submit all of the following les in a rstNamelastName.tar.gz archive (please replace rstNamelastName with you actual name...). You must turn in:




prj2.s




LC-2200-32.circ




microcode lastName.xml (please replace lastName with you actual last name...)




If you do the bonus portion of the project, please include a text le explaining how to use it







Don't forget to sign up for a demo slot! We will announce when these are available. Failure to demo results in a 0!




Precaution: You should always re-download your assignment from T-Square after submitting to ensure that all necessary les were properly uploaded.

Project 2 CS 2200 - Systems and Networks










 
Appendix A: Microcontroller Unit




As you may have noticed, we currently have an unused input on our multiplexer. This gives us room to add another ROM to control the next microstate upon an interrupt. You need to use this fourth ROM to generate the microstate address when an interrupt is signaled. The input to this ROM will be controlled by your interrupt enabled register and the interrupt signal asserted by the clock interrupt from the part 1. This fourth ROM should have a 2-bit input and 6-bit output. The most signi cant input bit of the ROM should be set to 0.




The outputs of the FSM control which signals on the datapath are raised (asserted). Here is more detail about the meaning of the output bits for the microcontroller:







Table 1: ROM Output Signals







Bit
Purpose


Bit
Purpose




Bit


Purpose


Bit
Purpose






































0
NextState[0]


7
DrMEM




14


LdA


21
ALULo






































1
NextState[1]


8
DrALU




15


LdB


22
ALUHi








































2
NextState[2]


9


DrPC




16


LdZ


23
OPTest






































3
NextState[3]


10
DrOFF




17


WrREG


24
chkZ








































4
NextState[4]


11


LdPC




18


WrMEM


25
LdEnInt








































5
NextState[5]


12


LdIR




19


RegSelLo


26
DrEnInt






































6
DrREG


13
LdMAR




20


RegSelHi


27
IntAck








































































Table 2: Register Selection Map














































RegSelHi




RegSelLo


Register






















































0






0










RX






















































0






1










RY






















































1






0










RZ






















































1






1










$k0




































































Table 3: ALU Function Map












































ALUHi




ALUlLo


Function


















































0




0








ADD




















































0




1








NAND




















































1




0








A - B




















































1




1








A + 1





























































































Reminder: Logisim implements the typical edge-triggered logic used in modern digital circuits. This means that stateful devices only change state when the clock makes a 0 to 1 transition.




This note pertains to the microsequencer implementation of the control logic. NOTE: Logisim has a minimum of two address bits for a ROM, even though only one address bit is needed for the OnZ ROM and the new interrupt ROM. You may want to do something so that the high address bit for these two ROMs are permanently set to zero.

Project 2 CS 2200 - Systems and Networks










 
Appendix B: LC 2200-32 Processor Reference Manual




The LC-2200-32 is a 32-bit computer with 16 general registers plus a separate program counter (PC) register. All addresses are word addresses. Register 0 is wired to zero: it always reads as zero and writes to it are ignored. There are four types of instructions: R-Type (Register Type), I-Type (Immediate value Type), J-Type (Jump Type), and O-Type (Other Type).




Here is the instruction format for R-Type instructions (ADD, NAND):




Bits
31 - 28
27 - 24
23 - 20
19 - 4
3 - 0












Purpose
opcode
RX
RY
Unused
RZ















Here is the instruction format for I-Type instructions (ADDI, LW, SW, BEQ):




Bits
31 - 28
27 - 24
23 - 20
19 - 0










Purpose
opcode
RX
RY
2's Complement O set













Here is the instruction format for J-Type instructions (JALR):




Bits
31 - 28
27 - 24
23 - 20
19 - 0










Purpose
opcode
RX
RY
Unused (all 0s)













Here is the instruction format for S-Type instructions (HALT, EI, DI, RETI):








Bits
31 - 28


27-0


























Purpose
opcode


Unused (all 0s)


























Table 4: Registers and their Uses
















Register Number


Name




Use
Callee Save?














0




$zero


Always Zero
NA
1




$at
Reserved for the Assembler
NA
2




$v0
Return Value
No
3




$a0
Arg or Temp Register
No
4




$a1
Arg or Temp Register
No
5




$a2
Arg or Temp Register
No
6




$a3
Arg or Temp Register
No
7




$a4
Arg or Temp Register
No
8




$s0
Saved Register
Yes
9




$s1
Saved Register
Yes
10




$s2
Saved Register
Yes
11




$s3
Saved Register
Yes
12




$k0
Reserved for OS and Traps
NA
13




$sp
Stack Pointer
No
14




$fp
Frame Pointer
Yes
15




$ra
Return Address
No


















Project 2


CS 2200 - Systems and Networks
 






















Table 5: Assembly Language Instruction Descriptions






















Name
Type
Example
Opcode
Action




















add
R
add $v0, $a0, $a2
0000
Add contents of RY with the contents of












RZ and store the result in RX.




















nand
R
nand $v0, $a0, $a2
0001
NAND contents of RY with the contents












of RZ and store the result in RX.




















addi
I
addi $v0, $a0, 7
0010
Add contents of RY to the contents of












the o set eld and store the result in RX.


















lw
I
lw $v0, 0x07($sp)
0011
Load RX from memory. The memory ad-












dress is formed by adding the o set to the












contents of RY.




















sw
I
sw $a0, 0x07($sp)
0100
Store RX into memory. The memory ad-












dress is formed by adding the o set to the












contents of RY.




















beq
I
beq $a0, $a1, done
0101
Compare the contents of RX and RY. If












they are the same, then branch to address












PC + 1 + O set, where PC is the address












of the beq instruction. Memory is word












addressed.




















jalr
J
jalr $at, $ra
0110
First store PC + 1 in RY, where PC is












the address of the jalr instruciton. Then












branch to the address in RX. If RX = RY,












then the processor will store PC + 1 into












RY and end up branching to PC + 1.






















halt
O
halt
0111
Tells the processor to halt.






















bonr
R
bonr $a0, $a1, $a2
1000
Optional bonus R-Type instruction






















bono
O
bono
1001
Optional bonus O-Type instruction






















ei
O
ei
1010
Enable Interrupts






















di
O
di
1011
Disable Interrupts




















reti
O
reti
1100
Return from interrupt by loading address












stored in $k0 into the PC and then en-












abling interrupts.






















boni
I
$a0, (0x01)$a1
1101
Optional bonus I-Type instruction.






















bonj
J
$a1, $a2
1110
Optional bonus J-Type instruction.























Finally, the assembler supports pseudo-operations. These operations aren't actually supported by the ISA, but the assembler will produce the appropriate instructions to get the desired instructions.







Table 6: Assembly Language Pseudo-Instructions







Name
Type
Example
Opcode
Action










noop
Pseudo-Op
noop
N/A
No operation, this does nothing. It ac-








tually just spits out \add $zero, $zero,








$zero".










.word
Pseudo-Op
.word 32
N/A
Fill the word at the current location with








some value.










la
Pseudo-Op
la $sp, stack
N/A
Loads the address of the label into the








register. It actually spits out \addi $sp,








$zero, label"













The provided datapath follows the following diagram:




Here is a description of each datapath component:
Project 2 CS 2200 - Systems and Networks










Figure 1: LC 2200-32 Datapath Diagram







 
PC is the program counter register.




 
Z is the zero detection register (used for deciding if a branch should occur).




 
ALU performs four functions: ADD, NAND, SUBTRACT, and INCREMENT.




 
Register File stores the 16 32-bit registers.




 
IE is the interrupts enabled register (interrupts on = 1, interrupts o = 0).




 
MAR memory address register (address to read/write from memory).




 
IR instruction register, which contains the 32-bit instruction currently being executed.




 
Sign Extender extends the 20 bit o set in the IR to 32-bit values suitable for driving on to the bus.




9.1 Interrupts Support




Note that some items mentioned in this section are not implemented yet. The implementation is part of your assignment for this project. You must handle the following:




1. Memory Mappings



 
For the purposes of this assignment, we have chosen to keep the interrupt vector table to be located at address 0x00000000. It can store 16 interrupt vectors. Program memory starts at 0x00000010.




 
Hardware Timer




 
The hardware timer will re every so often. You should con gure it as device 1 - it should place the assigned index (its driver is located on the vector table) onto the bus when it receives an IntAck signal from the processor.