CSE467 -- Computer Architecture Lab
Lab 2 -- Register File and ALU
Design due Friday October 30th

Overview

The instruction set of the CR16 uses standard 16-bit integer ALU operations. So, if we assume that the decoding has been done (actually you will design the decoder in a following lab), what you need to build to execute each instruction is an ALU to compute the numbers, and a register file to provide arguments and hold results. So, this lab is to design those pieces.

As an aside, it's interesting to note how much of the machine can be designed before knowing the complete picture of what the machine will look like. There are a set of basic things that are common to a number of different designs. Building these basic components (memory, register file, ALU, etc) don't really require knowing much more than the word size and the overall plan. Filling in the details later will determine the precise character of the final machine. Most VLSI design systems, for example, have large libraries of these generic parts which can be used to design a wide variety of different machine types.

Execution Datapath

Looking at the Baseline instruction set you should notice a few things:

• The word size is 16 bits. Therefore, although it's not absolutely essential, it would be natural to have a 16 bit ALU. It's not required because you could clearly do the ALU operations with a smaller ALU in a sequential way. The 16-bit result could, for example, be generated using an 8-bit ALU and two timesteps. Going to the extreme, you could use a single-bit ALU and iterate 16-times for each ALU operation. As an aside this is actually the approach that was used on the Connection Machine. This was a machine designed to be massively parallel. The full configuration had 64k (i.e. 65,536) total processors. In order to physically assemble this machine, each processor had to be very small so that many of them could fit on a single chip. Each processor had a single-bit ALU and operations were either done in sequence on a single processor, or done by combining processors into groups.

  Anyway, getting back to the point, your ALU should probably be 16-bits wide to match the data word size.

• The instruction set supports both ADD and SUB instructions, so your ALU should also support these operations. Reading the CR16 handout carefully you will note that signed numbers are represented as two's complement numbers. So, your ALU should operate on two's complement, and can use this representation for implementing subtraction. The main difference between a two's complement ALU and unsigned ALU is in the way subtraction is encoded, and also in the way condition codes are generated.

  The condition codes required by the Baseline instruction set are defined here and also in the programmers reference manual:

  C

  -- The Carry bit determines whether a carry or borrow occured after addition or subtraction. 0 means no carry or borrow, 1 means a carry or borrow occured.

  L

  -- The Low flag is set by comparision operations. L is set to 1 if the Rdest operand is less than the Rsrc operand when they are both interperted as unsigned numbers.

  F

  -- The Flag bit is a general flag used by various operations to signal exceptional situations. In particular, arithmetic operations use the F bit to signal arithmetic overflow (this is often called the V bit on other machines).

  Z

  -- The Z bit is set by the comparison operation. It is set to 1 if the two operands are equal, and is cleared otherwise.

  N

  -- The Negative bit is set by the comparison operation. It is set to 1 if the Rdest operand is less than the Rsrc operand when both are considered to be signed integers.

• The processor supports logical operations of AND, OR and XOR. Like the arithmetic operations, these can either take two registers as arguments, or one register and an immediate value.
• The Baseline instruction set has two shift instructions: logical shift and arithmetic shift. These instructions have an immediate field as part of the instruction. In the full processor design this is used to indicate how many places to shift. A value of 1 in the immediate field shifts the argument register by 1 place to the left. A value of -3 indicates a shift of 3 places to the right. In our Baseline processor, you can assume that all shifts will be by one only. The only legal values for the immediate are 1 and -1 to indicate left and right shifts.
• Branch and jump targets are computed in one of two ways: either as a displacement from the current PC, or to an absolute value held in a register. In the case of the displacement, the current PC value must be added to the immediate value in the instruction and written back to the PC. In the absolute case, the value in a register should be written directly to the PC.
• Load and store instructions need to use values in registers, possibly added to immediate values in registers, to compute memory addresses.

Looking at these constraints it is possible to do a general layout for the execution datapath of the machine. The important thing at this point is not to get everything exactly right the first time, but to make sure that you haven't made anything impossible that you will need to do later. The set of control points in this datapath (function codes, mux select signals, latch enables, etc) will be controlled by the control state machine and the decoded instruction later.

So, the register file must have two read ports. You must be able to read two arguments from the register file to feed the ALU. It also must have a single write port so that you can write back the result. However, since one of the source registers is overwritten with the result, it need only have two addresses specified. These addresses come from the decoded instruction word. To build the register file you should use a couple of the RAM16X8D components from the Xilinx library. These are 16x8 RAM cells that use the function LUTs in the Xilinx CLBs to build the RAM. You'll need a couple of them because our registers are 16 bits wide. The A[3:0] input to these RAMs is that address to write to as well as the address to read form that shows up on the SPO output port. The DPRA[3:0] input is the address that reads to the DPO output.

The ALU should be able to read these two register's contents and perform an operation on them. However, the ALU must also be able to operate on a register and an immediate value (an ADD-immediate for example), and the PC might also need to be combined with an immediate value (for a displacement-branch for example). These immediates will need to be sign-extended before going into the ALU, and there are a couple different lengths of immediates to consider. So muxes on the inputs of the ALU seem required. Also, it's possible that a register value might be sent to the shifter instead of the ALU. So, the output of the execution unit might come from either the ALU or the shifter. Sounds like we need another mux on the output side. One example of a possible organization is shown in Figure 1. Don't take this block as the required organization! This is just an example of how things might be organized. It's not even guaranteed to be correct for all the instructions that the Baseline instruction set needs. If you have a different organization in mind, by all means use that. Just make sure that it is able to compute all the values that will be required by the given instruction set! By being clever you may be able to reduce the number of muxes, or combine units together, or modify things an any number of interesting ways.

One approach to designing this ALU datapath is to look at every single instruction that you're interested in (i.e. the Baseline or Medium instruction sets), and check that each one can be accomodated by your datapath.

Here's the pdf picture Figure 1: One Possible ALU Organization

Some things not shown in Figure 1 are the control points in the datapath. The ALU, for example, will have a function code coming from the control path that tells it which operation it is actually doing at the moment. The muxes all have select inputs telling them which way they are switched. The latches have enable signals, etc. All these signals are the control points into the execute unit that allows the state machine controller to make it do the right things for each individual instruction.

ALU Details

There are a number of ways to design an ALU. One approach is to build one circuit that computes all the desired outputs given a single function code. An example of a 7400-series chip that takes this approach is the 74c181 ALU chip. Using this technique a single bit is built which can combine its two argument bits into all the desired combinations. These bits are then stacked together to make an ALU of any desired size. Another approach is to be a little more specialized and build an adder/subtracter and a logic unit separately, have them compute their result concurrently, and then use a mux-type circuit to select the desired result after the fact. It is possible, for example, to build a universal logical unit out of muxes using the bits as the select inputs and the desired function's truth table as the data inputs of each bit's mux. Either approach is fine, as long as the ALU can do the required functions.

Another piece of the execute unit to consider is the shifter. Note that I don't call this a shift-register. This is to indicate that it can, if you like, be built as a combinational circuit. The result will eventually be stored in the output latch of the ALU so there's no reason to use latches in the shifter too. In fact, a shifter that shifts a fixed number of bits can be constructed using only wires! Simply connect the wires in a way that shifts them at the next inputs (connect out0 to in1, out1 to in2, etc. and you have a shifted result). You may be able to exploit this property in your shifter by, for example, connecting the shifter inputs directly to the output mux, except in shifted order.

There are a number of special parts in the Xilinx library that may be of use in constructing your ALU, and the LogicBlox tool can also be very useful. Check the tools carefully to see what's there.

Remember that your ALU must generate condition codes that will be latched into the processor status register (PSR). Your ALU should generate all the Baseline condition codes. Also pay attention to which instructions update the condition code register! Not all ALU instructions update the the register, and even those that do, don't all update it in the same way! Some instructions only set some of the bits, and some instructions don't set any of the bits. Not even all the ADD instructions set the PSR. So, you need to have control over whether the PSR is updated or not. The decoder can decide which PSR bits are updated.

What to Do

For this lab you should design an ALU and a register file which will be used eventually in the execute unit of your processor. The overall block will look similar to Figure 1, but definitely need not be exactly like it. Your datapath should support all the instructions from the Baseline instruction set, although you do not have to design the control for those instructions for this lab. The register file should contain 16 16-bit registers using the dual-ported SRAM from the Xilinx library, and your ALU should be capable of performing 16-bit arithmetic (if you want to explore other options than a 16-bit wide adder, feel free, but to the external user (i.e. the outside of the symbol) it should look like a 16-bit ALU). The program counter and immediate register for this lab will also be 16-bit registers. These will likely be implemented slightly differently in the final circuit, so make sure that you can change things later.

Testing You should test your register file and ALU using the simulator and be prepared to explain your testing procedure, demonstrate the functionality of the circuits, and show the command files and simulation logs from your own testing. I would like you to use command scripts for testing this circuit (and all the rest of the circuits this quarter). Using a script allows you to write one script that checks the circuit and then use the same script to validate the circuit after you make changes. A good test file has comments and ``check'' commands in the script.

You should hand in a well-documented set of schematcs, test programs, and test logs for this lab. You should also hand in some sort of documentation on how each of the instrucions in the baseline instruction set are completed using your datapath. This should look like a table that has a line for each instruction in the baseline instruction set. For each instruction you should define what the mux settings should be, which control signals need to be set, and what they need to be set to in order to complete that instruction. This will help both you and us determine is you've thought of all the possibilities that your datapath will have to support.

Optimizing for Size

Once you have the circuit designed and working, one thing you might ask is how well you did. There are many many ways to evaluate a design. Performance is a common measure. Power consumption is another popular optimizing target (especially for circuits in portable consumer electronics). Neither of these are particularly interesting in our case (our clock is fixed and the boards are plugged into the wall). Because we are trying to squeeze things onto a single FPGA our biggest criterion is size. In particular, how many Xilinx CLBs are used? Try to pay close attention to this when you are designing the ALU and register file. One way to check your results is to put pad and I/O markers around your circuit and run the implement phase of the Foundation software on your design. The report on the placement phase will tell you how many CLBs (out of 400) you're using.

What to Handin

For this lab you should hand in schematics, test scripts, test logs, mux and control settings table, and other supporting documentation for your ALU design. As usual, you should say what the team members did and sign the document.

• About this document ...