[2021] CS350 Computer Organization and Assembly Language Programming - Final Project: Building the iit3503
8 Final Project: Building the iit3503
This is the final project/lab for this class. Congratulations on making it this far! This one is going to involve quite a bit more work than the prior labs, so make sure to start early. Before you begin, make sure you read Appendix C of your textbook. You should really watch lecture 22 as well.
Objectives
Get experience with Chisel on a more realisitic codebase Understand how an actual processor is implemented Understand how a control unit and datapath work together Understand how microcoded control units work
1 Setup
Just like in several programming labs before, we’ll first need to get a development environment set up using Vagrant. On your machine, clone the repo like so:
Now, assuming you’ve installed VirtualBox and Vagrant successfully, you should be able to launch our provided Linux virtual machine with the following:
If you’re using VMware with Vagrant (instead of VirtualBox) you will want to do something like this:
This process will take a while, so be patient. After some time, you will see a virtual machine window come up with a login screen. Use the username “vagrant” with the password “vagrant”. Note we’re using Ubuntu 18.04 this time rather than Fedora (mostly for Chisel compatibility).
Open up a Linux terminal by clicking on “Activities” on the top left, and typing in “terminal” in the search window. You are now set up for the rest of the lab. Continue to the next sections.
2 Implementing a Multi-cycle, Microprogrammed CPU
You’ll first need to get the starter code. From inside your Vagrant VM, run the following:
[vagrant@ubuntu] cd ~
[vagrant@ubuntu] git clone https://github.com/khale/iit3503-starter [vagrant@ubuntu] cd iit3503-starter
A good portion of your time for this lab is going to be looking at our code and understanding what is going on. You do have to write some code, but not too much. Most of your time will go into understanding how your code fits into the bigger picture of the CPU.
Luckily for you, I’ve already implemented most of the CPU for you. You just need to fill in some essential missing/broken parts, and you’ll have a working LC-3 microprocessor that you could (with some extra work and money) have fabricated and sent back to you in silicon form! For debugging though, we can’t use a physical chip; that would be too costly. As you work through completing the code, you’ll first debug your design using Chisel-based unit tests, just like you did in your prior labs. As you progress, you will use a more complete simulator that allows you debug your CPU cycle by cycle (or instruction by instruction, as you did with lc3sim previously).
The complete code for the iit3503 comprises about 1300 lines of Chisel source code. That adds up to about 200KB of text. Think about that; a working CPU can be described with only 200KB of text! This CPU isn’t going to win any awards for performance, but I find that remarkable. While 1300 lines of code is tiny by real-world codebase standards, it’s probably bigger than you’re used to working with at this point. Don’t panic! We’ll guide you through what you need to do, and we’ll start off with easier components. Then we’ll work our way to getting this thing running some real LC-3 code!
As you work on more codebases like this, you’ll gain more confidence and go on to work on even bigger projects. This is a process you must go through if you are to become a computer scientist or a professional software developer. At some point we have to wean you off the tiny fibonacci and quicksort toy problems and let you get your hands dirty. Better sooner than later, hence this project!
2.1 Getting the lay of the land
As with your previous projects, pretty much everything you need to worry about you can find in .scala files. You can find the code for the entire CPU in src/main/scala/iit3503/*.scala. As before, the corresponding unit tests can be found in src/test/scala/iit3503/*.scala.
[you@vagrant] ls -1 src/main/scala/iit3503 ALU.scala
AddrCtrl.scala
Bus.scala
Control.scala ControlStore.scala DataPath.scala IntCtrl.scala MemCtrl.scala MicroSequencer.scala RAM.scala RegFile.scala Top.scala UART.scala Utils.scala
Unlike previous projects, all of these .scala files are all part of the same project. They are organized somewhat hierarchically, as shown below.
Take some time now to explore. Try to connect back this code to the state machine and datapath diagrams from the book in Appendix C. I’ve tried to comment the code well so that you can get an idea of what’s going on. These separate modules constitute different circuits of the CPU. Connecting them all together is Top.scala. This module has two roles: tying all the various modules’ inputs and outputs together, and exposing an interface to the outside world (with a top-level IO() block). You can
hink of Top.scala as being the chip package that you’d see on a motherboard. The signals in its IO() block represent the pins coming out of the chip.
While you’d ideally want to understand all of these modules, there are a few you can ignore. I’ll briefly describe them here, but you won’t need to understand them for the
project:
2.2
AddrCtrl.scala: implements the core of the memory controller. This essentially determines whether an address in MAR corresponds to a device or RAM IntCtrl.scala: implements interrupt, exception, and trap handling logic for the CPU
RAM.scala: implements an interface to RAM, which will be provided by the simulator framework
UART.scala: implements the output device for the LC-3. This is a serial port. It’s an I/O device that just sends bits one after another out on a wire. The cool thing about UARTs is that the sender and receiver don’t have to use the same clock. UARTs are often used to get output from systems that don’t have any other way to display data.
Utils.scala: This just implements the SignExt and ZeroExt utility functions (which you will need to use). The ALU
Take a look at src/main/scala/iit3503/ALU.scala. This is a good place to start, because you’ve already implemented a version of this in a prior lab. The ALU here is very similar, and in fact even simpler. The only somewhat strange thing here is that this ALU has a function called PASSA. This just takes the A input of the ALU and sends it through to the output unchanged. The datapath will use this functionality in situations where we need to send something from the register file straight out to the bus without ADDing or ANDing it with anything.
Complete the specified functionality (see the comment at the top of the file). Once you’re done, you can test your code using the ALU unit tests by running
Once you’re passing all the tests, you should be pretty confident that your ALU is working properly. Finish that first, then we’ll move on.
2.3 The Register File
Now open up src/main/scala/iit3503/RegFile.scala. This is the 3503’s register file. Keep in mind this is a type of memory. These registers will likely be implemented using very fast storage elements like flip-flops. Note the RegInit(VecInit(...)) line. This is creating the register file as an 8-element vector of 16-bit registers (which is exactly what we wan’t). In its current state, the register file just ignores writes and outputs zeros for reads. You will need to implement reads from and writes to this register file.
One interesting thing about this register file is that it has two ports. Remember from lecture that this really just means that surrounding the memory elements we have several groups of row decoding logic, wordlines, bitlines, etc rather than just one. While only one write can occur at a time, we can use the two read ports concurrently. In other words, we can read from two registers at the same time. We can even read from the same register on both ports. Without a dual-ported register file like this, we would not be able to implement instructions that use multiple registers (e.g. ADD R0, R2, R3 or AND R0, R0, R0).
You should ignore the debug outputs. These are used by the simulator.
Once you’ve implemented reads and writes, make sure you’ve done so properly by testing the register file:
2.4 The Control Store (microcode ROM)
Now we’re getting to the fun part. For this part we’ll dive into the microcode ROM. Remember from lecture that this is the part of the control unit that stores in each row all the control signals that should be active in a given state of the state machine (i.e. in a particular clock cycle). The really cool thing about using a microcoded implementation, is that we can change this control store to enhance our CPU or fix bugs in its implementation even after we’ve baked it into silicon. If you’ve ever installed a “microcode update” on your PC, this is the thing that was being updated. It also allows for some fun and somewhat devious things to happen; take a look at the extra credit section if that interest you.
Open up src/main/scala/iit3503/ControlStore.scala. Here you’ll see a lot of similar-looking blocks of code. Each one creates a distinct row for the control store. Normally a code ROM is implemented as a big array of binary data, but here we set it up for you so that it’s easier to modify and reason about. Each of the blocks here are selecting and setting values of control signals that should be active during the clock cycle corresponding to that particular state.
Unfortunately, several states have been left blank. You’ll need to fill those in by understanding the control unit’s state machine and the corresponding signals on the datapath. I’ve highlighted the missing states that you’ll need to implement below.
Take a close look at the register-transfer notation inside each state of the state machine. While the steps there don’t directly correspond to what control signals should be activated, they do provide hints. Take a look at our implementation of other states to get an idea of what to do here. In fact, some of the states are so similar to others that you may be able to reduce the amount of work you have to do here drastically.
Since getting the control signals right is so important, we’ve got a lot of unit tests for you to test it out. While these don’t test the particular signals active at each clock, they do test that you’re state machine is going through the correct sequence of states, which is more than half the battle. These tests are all in src/test/scala/iit3503/ControlTester.scala. You can run them all at once using make test-control, but this will take quite a long time . You may want to comment out most of the tests and make sure you pass each one individually instead.
1. It is an unfortunate limitation of the Chisel testing framework that these tests have to be so slow. I’m told they’re working on this.
NOTE: Some control store tests (namely the branch tests) will not pass until you’ve implemented your microsequencer (next section).
2.5 The Microsequencer
We’re not done with the control unit yet! The microsequencer is mostly done, but someone failed to do their job. One of the conditions is unimplemented. You should find it and complete the microsequencer. Once you’re done, test it with make test-useq.
2.6 The Memory Controller
The memory controller is in charge of dealing with all things memory. The CPU just sees the memory system as the MAR/MDR pair. It can ignore the rest of the details. The memory controller needs to deal with those details. The primary job of the memory controller is to route memory read/write requests to the appropriate place. Because the LC-3 uses memory-mapped I/O (MMIO), there are four possible components that an address could refer to:
RAM
The Keyboard (KBSR/KBDR)
The Console (DSR/DDR)
The Machine Control Register (MCR)
These devices and registers are all mapped at different addresses. Given some address in MAR, the memory controller must route the read/write request to the appropriate place. Take a look at MemCtrl.scala to get started. I’ve highlighted the missing functionality below.
Once you’re done, you can test your fixes for the memory controller by running make test-memctrl.
2.7 The Data Path
This is the last step! There are some unfinished components of the datapath as well. I’ve highlighted them below.
Mostly there are some multiplexors (MUXes) that you need to implement ( see other examples of using the Chisel Mux() and MuxLookup() primitives elsewhere in the code). The instruction register is also not quite complete. You’ll need to finish these in DataPath.scala.
Unfortunately, the datapath is a little more complicated to target with unit tests. There are a couple of tests (which you can run with make test-datapath, but you will really want to start using the simulator. Once you get to this point, you can actually start running instructions on your machine to make sure it works properly.
3 Testing/debugging your CPU
Once your CPU is getting closer to complete, you can start using the simulator. The simulator is automatically constructed by taking the output of the Chisel compiler and 1
transforming it into C++ code using a special compiler . This simulator is an example of a cycle-accurate simulator, in that it models what the hardware does at every clock cycle. You can build the simulator like so:
1. This is the purpose of Verilator, if you’re curious
This will take a while to compile. Once its done, it will create an executable for the simulator in build/sim. You can get some idea of how to run by running build/sim -h. At this point, since you’re not quite sure your implementation is done, you’ll want to run simple programs, and you’ll want to step through them cycle by cycle to make sure things are working properly. We’re going to run things without an operating system at this point, and our programs will run with full privilege. We’ve provided a lot of test LC-3 programs for you that test individual instructions in functionality in the asm/ directory. Take a look for yourself.
If I wanted to make sure my CPU can execute a LD properly, I could use the asm/simple_ld.asm program as follows:
The -i flag tells the simulator to drop you in an interactive debugger that you can use to step through cycles or instructions, print out memory locations, registers, and other state of the CPU. This will help make sure your CPU is working as expected. You can even set breakpoints! Its operation is quite similar to the interactive CLI debugger in ‘lc3sim‘, but we’ve tried to make it a bit prettier.
Most of these simple_xxx test programs go into an infinite loop after they’ve tested the functionality of interest. This is because they can’t invoke HALT, since that is a type of TRAP routine, which of course requires an operating system!
3.1 Waveforms
If you want the simulator to generate waveforms, you just add the -t option. For example,
[you@vagrant] build/sim -b binaries/simple_ld.bin -t foo.vcd -q
Will generate a waveform file for all the signals in my CPU (there are a lot!) during this execution. The -q flag tells the simulator to shutdown when the CPU encounters a HALT instruction. My waveform is shown below:
4 Taking it to the next level
So far your simple programs aren’t doing anything very interesting, in particular I/O. To do that, we’ll need trap routines, and for that we need an OS!
Once you’re reasonably confident your code works, you can load up our small 3503 operating system, techOS. In this model, you give the simulator an OS image and a program binary. When the machine starts, the OS boots up sets up machine state, then transfers control to your user program (now running in usermode). Here we can write any LC-3 program we want, including those that use GETC, PUTS, HALT, etc. You can do this like so:
Try writing your own test codes! All you have to do is add a well-formed .asm file in the asm/ directory and run make sim and your code will be compiled into a binary file in binaries/. Have fun!
5 Handing in your code
This time, we’ve set up an automated code submission server, so you won’t be submitting your code on Diderot. Once you’re happy with your implementation, you can submit your code by running
This will ask you to input your name and your 8-digit A# (be careful to avoid typos here!) You should omit the leading ’A’. If everything goes well, it will zip up your code into a compressed format and send it to us. You should see an OK message printed out. You can resubmit with make handin as many times as you’d like until the deadline. We’ll use your most recent submission for grading.
6 Grading Criteria
We will be grading your code along the following criteria:
1. Does your code pass all the unit tests for the various components? (alu, datapath, memctrl, control, useq, regs)
2. Does your code run the assembly tests in asm/ properly using the simulator?
7 Extra Credit Opportunities
There are several opportunities to get some extra credit here, but none are for the faint of heart.
There’s an undocumented instruction hiding somewhere in the iit3503. Can you find it, figure out how to execute it, and figure out what it does? (5 pts). By the way, this kind of thing happens in the real world.
Implement a macro testing framework so that test programs can be run automatically (15 pts)
Build a command interpreter (shell) for the 3503 OS (10 pts)
Put your design on an FPGA (we have a partial setup to get you started for this, using the Goboard from Nandland (10 pts) Implement a curses-based VGA device for the simulator (15 pts)
Add an L1 cache to your CPU (15 pts)
Pipeline your design (a simple 5-stage pipeline is fine) (up to 20 pts)
Add unit tests. We can always use more unit tests! Especially add one if there were any bugs in your code that you think could be found with a simple test case (1 pt per test, max 10 pts).
