lab07 : Combinatorial + Sequential Logic Design

num ready? description assigned due
lab07 true Combinatorial + Sequential Logic Design Thu 02/28 08:00AM Wed 03/06 05:00PM

Lab 7: Combinatorial + Sequential Logic Design


Due Wednesday, Mar. 6th, at 5:00 PM as a PAPER COPY to be dropped-off at HFH. See further instructions at the end of this page.

Goals for This Week

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

Documentation:


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. Since this is a long lab, working with a partner is recommended (optional). The tasks are listed below:

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:

Input Name Input Description
Operation Which operation is to be performed, specified with a single bit. There are two possible operations:
  1. XOR, specified when Operation = 0
  2. NOR, specified when Operation = 1. Note that nor is equivalent to ~(A | B). That is, it is an OR operation whose result is negated.
A The first operand, specified with a single bit
B The second operand, specified with a single bit

The ALU returns the following single output:

Output Name Output Description
ALUout The result of whatever operator was chosen, applied to the given operands. For example, if XOR was chosen, then the result should be A ^ B.

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

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:

Input Name Input Description
R0 The first register to read, as a single bit. If 0, then reg0 should be read. If 1, then reg1 should be read.
R1 The second register to read, as a single bit. If 0, then reg0 should be read. If 1, then reg1 should be read.
WR Short for “Write Register”. Specifies which register to write to. If 0, then reg0 should be written to. If 1, then reg1 should be written to.
W The data that should be written to the register specified by WR. This correpsonds to a single bit.
WE Short for “Write Enable”. If 1, then we will write to a register. If 0, then we will not write to a register. Note that if WE = 0, then the inputs to WR and W are effectively ignored.

The register file returns the following two outputs:

Output Name Output Description
O1 Value of the first register read. As described previously, this depends on which register was selected to be read, via R0.
O2 Value of the second register read. As described previously, this depends on which register was selected to be read, via R1.

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

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. You will ONLY use 1 box from task 1 and 1 box from task 2. 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.

Instruction Name Opcode First Operand Second Operand Third Operand Description
xor 00 REG0: Register where the result should be placed, specified with a single bit REG1: Register specifying where the first operand is, specified with a single bit REG2: Register specifying where the second operand is, specified with a single bit XORs the contents of REG1 and REG2 together, putting the results in REG0. This should involve the ALU. In more terse notation, this calculates:
REG0 = REG1 ^ REG2
nor 01 REG0: Register where the result should be placed, specified with a single bit REG1: Register specifying where the first operand is, specified with a single bit REG2: Register specifying where the second operand is, specified with a single bit NORs the contents of REG1 and REG2 together, putting the results in REG0. This should involve the ALU. In more terse notation, this calculates:
REG0 = ~(REG1 | REG2)
load 10 REG: Register where the result should be placed, specified with a single bit A: A memory address, specified with two bits N/A This loads in a single bit of memory located in address A, and loads its value into register REG. In our setup, each cell in memory only holds a single bit (as opposed to a byte), and we can address individual bits. For example, memory address 00 would refer to the first bit in memory, 01 would refer to the second bit in memory, and so on.
store 11 REG: Register containing the value to store into memory, specified with a single bit A: A memory address, specified with two bits N/A This copies the value stored in REG to the memory slot located at address A. In our setup, each cell in memory only holds a single bit (as opposed to a byte), and we can address individual bits. For example, memory address 00 would refer to the first bit in memory, 01 would refer to the second bit in memory, and so on.

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 nor instruction, this means that:

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 NORed 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:

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:

Input Name Input Description
OP0 Bit 0 of the opcode. Recall that bit 0 refers to the rightmost bit, so for opcode 01, this refers to the bit with value 1.
OP1 Bit 1 of the opcode. For example, for opcode 01, this refers to the bit with value 0.
B0 The first non-opcode bit of the instruction. For example, with instruction 00100, this refers to the bit with value 1.
B1 The second non-opcode bit of the instruction. For example, with instruction 00010, this refers to the bit with value 1.
B2 The third non-opcode bit of the instruction, which is the last bit of the instruction. For example, with instruction 00001, this refers to the bit with value 1.

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

OP1 OP0 B0 B1 B2

Some more examples are shown below:

OP1 OP0 B0 B1 B2 Human-readable Encoding Description
0 0 0 0 0 xor reg0, reg0, reg0 Compute the XOR of the contents of reg0 with the contents of reg0, storing the result in reg0
0 1 1 0 1 nor reg1, reg0, reg1 Compute the NOR of the contents of reg0 with the contents of reg1, storing the result in reg1
1 0 1 0 1 load reg1, 01 Copy the bit stored at address 01 (decimal 1) into register reg1
1 1 0 1 0 store reg0, 10 Store the contents of reg0 at address 10 (decimal 2)
1 1 1 1 1 store reg1, 11 Store the contents of reg1 at address 11 (decimal 3)

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:

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 AS A PAPER COPY!!!!

You will do this lab entirely on paper (old school rules!!) and turn in your assignment at the CS64 BOX in the Computer Science department mail room (next door to the CS Dpt. Office) on the 2nd floor of HFH.

Your submission MUST be WRITTEN/DRAWN NEATLY and STAPLED together. Please ensure that your name (and your partner's name, if you have one) is on EVERY PAGE OF THE ASSIGNMENT!


Copyright 2018, Ziad Matni, CS Dept, UC Santa Barbara. Adapted from work by Diana Franklin and Kyle Dewey. Permission to copy for non-commercial, non-profit, educational purposes granted, provided appropriate credit is given; all other rights reserved.