Lab 8: Digital Design III

Due Wednesday, November 25 at 11:59:59 PM

Goals for This Week

By the time you have completed this work, you should be able to:

• Use multiplexers to switch between inputs
• Design a small arithmetic logic unit (ALU)
• Design a small register file
• Design a basic instruction decoder and executor

• partner.txt

• Week 5 Lecture Notes, for basic gate information (e.g., AND, OR, NOT, etc.)
• Week 6 Lecture Notes, for multiplexer and ALU design information
• Pages B-26 through B-29 for ALU design information
• Various D Latch Examples
• Section B.8 (pages B-50 through B-58) for D latch and register file information
• Pages B-58 and B-59 for memory information (only need to understand the interface for memory, shown in Figure B.9.1)
• Sections 4.3 and 4.4 for constructing an instruction executor (the figures are more important than anything else, and even then these are all significantly more complex than anything in this assignment)

Step by Step Instructions

For this week, you will sharpen your skills drawing circuits, and start to build bigger components from smaller ones. To this end, you will design some core components of a simple processor this week, broken up into three tasks. While each task can be completed independently of each other, they progressively build in difficulty, so it is recommended to complete them in order. The tasks are listed below:

• Task 1: Design a Small ALU
• Task 2: Design a Small Register File
• Task 3: Design a Small Instruction Decoder and Executor

The initial step below describes how to get the files you will need into the appropriate place. These files are used for all the different tasks.

Initial Step: Create a Directory for This Lab and Copy Over the Files

After you log in, go into your cs64 directory that you created last time:

cd cs64

Then create a new directory for this lab: lab8:

mkdir lab8

Then go into that directory.

Now copy over all of the files necessary for this week's tasks:

cp ~kyledewey/public_html/cs64/labs/8/partner.txt .

Note the use of the trailing . in the above command, which stipulates that the specified files should be copied into the current directory.

Task 1: Design a Small ALU

For this task, you will design a simple single-bit ALU, writing your design either on paper or in a file named alu.jpg. The ALU takes the following inputs:

The ALU returns the following single output:

To complete this task, you may use only the following components, in unlimited supply:

• AND, OR, XOR, and NOT gates, using the notation shown in the week 5 lecture notes.
• 2-input multiplexers, which take a selector bit S0 and two single-bit input operands A and B, and return a single-bit output Z. They should be drawn using the symbol below, provided by Wikipedia:
  

Task 2: Design a Small Register File

For this task, you will design a small register file, writing your design either on paper or in a file named registers.jpg. The register file contains two registers, each one bit long, which are named reg0 and reg1, respectively. The register file allows two registers to be read simultaneously, and also allows a register to be written to. The register file takes the following inputs:

The register file returns the following two outputs:

To complete this task, you may use only the following components, in unlimited supply:

• AND, OR, XOR, and NOT gates, using the notation shown in the week 5 lecture notes.
• 2-input multiplexers, which take a selector bit S0 and two single-bit input operands A and B, and return a single-bit output Z. They should be drawn using the symbol below, provided by Wikipedia:
  
• D latches, which take a single-bit input D and a block bit E, which is used to indicate that the value of D should be saved within. They produce single-bit outputs Q and !Q, which represent the value stored in the latch along with its negation, respectively. They should be drawn using the symbol below, provided by Wikipedia:
  

Task 3: Design a Small Instruction Decoder and Executor

This is the largest task of the three. For this task, you will design a small instruction decoder and executor, which is at the heart of a processor. This should be done either on paper or in a file named executor.jpg. This component will use the components you designed in tasks 1 and 2, in an abstract manner. That is, instead of needing to rewrite your definitions from tasks 1 and 2 for this, we'll provide you boxes that perform these operations. The processor instuctions you will be working with are described thusly.

Instructions are uniformly encoded with 5 bits, and there are four instructions in total. The first two bits of the instructions encode the opcode, which is used to differentiate between instruction types. The next three bits encode which registers the instruction operates on, or a memory address, depending on the particular instruction. Registers are specified using a single bit, and memory addresses are specified with two bits. A table of all the possible instructions is below.

Instructions are encoded with the two opcode bits on the far left, with the remaining three bits following. For example, consider the following instruction:

01110

The leftmost two bits are 01 which refers to the opcode for nor. As such, this is a nor instruction.
The next three bits are 110. Going from left to right, along with the definition of our xor instruction, this means that:

• REG0 = 1
• REG1 = 1
• REG2 = 0

Taking all this information together, this means to first get the values stored in registers reg1 and reg0 (because REG1 = 1 and REG2 = 0). These values are then XORed together, and then the result is stored in register reg1 (because REG0 = 1).

As another example, consider the following instruction:

11011

The leftmost two bits are 11, which refers to the opcode for store. As such, this is a store instruction.
The next three bits are 011. Going from left to right, along with the definition of our store instruction, this means that:

• REG = 0
• A = 11

Taking all this information together, this means to first get the value stored in register reg0 (because REG = 0). This value should then be put into the single-bit memory slot stored at address 11 (because A = 11).

The instruction decoder / executor takes in a single instruction to work with, specified with five bits, as our instructions are five bits long. Each of these bits corresponds to a distinct input, each of which is described below:

Another view of the above information is provided in the table below, which shows where the different inputs bits in an instruction are located:

Some more examples are shown below:

The instruction decoder / executor does not produce any outputs. This makes sense, as the effect of running a single instruction is reflected in changes made to the register file and to memory.

To complete this task, you may use only the following components, in unlimited supply:

• AND, OR, XOR, and NOT gates, using the notation shown in the week 5 lecture notes.
• 2-input multiplexers, which take a selector bit S0 and two single-bit input operands A and B, and return a single-bit output Z. They should be drawn using the symbol below, provided by Wikipedia:
  
• An abstract component, representing the ALU you designed in task 1. In should be drawn using the symbol below:
  
• An abstract component, representing the register file you design in task 2. It should be drawn using the symbol below:
  
• An abstract component, representing the interface for the memory chip. The memory chip contains four bits of memory, which are individually addressed.
  This component has the following inputs:
  • A0: Bit 0 of the address. Recall that bit 0 refers to the rightmost bit, so for address 01, this refers to the bit with value 1.
  • A1: Bit 1 of the address. For example, with address 01, this refers to the bit with value 0.
  • OE: Short for “Output Enable”. If 1, then the value at the address specified by A0 and A1 will be read, and sent to the output line O. If 0, then the memory will not be accessed, and the value sent to the output line is unspecified (could be either 0 or 1, in an unpredictable fashion).
  • W: The value to write to memory
  • WE: Short for “Write Enable”. If 1, then the value sent into W will be written to memory at the address specified by A0 and A1. If 0, then no memory write occurs (the value sent to W will be ignored).
  The output of the component is O, which refers to the value read from memory (or unspecified if OE = 0).
  The memory component should be drawn using the symbol below:
  

Note that D latches are not a component you may introduce for this task. While these are needed to implement the memory file and the memory interface, these aren't needed at the higher level of abstraction we are working with in task 3. You are forbidden to use them only to prevent confusing situations where D latches are added needlessly.

Implementation Hints

Rather than implementing task 3 all at once, it is strongly recommended to take the following incremental approach:

1. Design a version that assumes the instruction is either xor or nor. This version would do something broken on load or store instructions.
2. Design a version that assumes the instruction is load. This version would do something broken on any other instruction.
3. Design a version that assumes the instruction is store. This version would do something broken on any other instruction.
4. Finally, stitch the above three solutions together, introducing additional gates and multiplexers to only trigger the correct portions of the circuit depending on whatever the whole opcode is. This should be fairly mechanical in nature.

Turn in Everything Using turnin, or the CS64 Homework Box

If you partnered with someone, record the email address they are using for the class in partner.txt. For example, if your partner had the email address foo@bar.com, then the contents of partner.txt should be the following (and only the following):

Partner: foo@bar.com

If you did not partner with anyone, you do not need to (and should not) edit partner.txt.

Assuming you are in the cs64/lab8 directory you created at the beginning, you can send in your answers with the circuit images via the following command:

turnin lab8@cs64 alu.jpg registers.jpg executor.jpg partner.txt

If, instead, you are planning to turn in the image using the CS64 homework box in Harold Frank Hall, room 2108, then you can use the following command:

turnin lab8@cs64 partner.txt

You may turn in the same assignment up to 100 times, which is useful if you are working on it incrementally. Note that only the last version you submitted will be graded.

Even if you did not partner with anyone, you should still turn in partner.txt, which should not have been modified.

Prepared for Computer Science 64 by Kyle Dewey, with incorportation of materials by Diana Franklin.