CS61C Summer 2014 Lab 10 - Logisim and Pipelining


There are three parts to this lab. In the first part, you will be learning how to use the remaining essential parts of logisim, in particular, splitters to take a subset of bits on a wire, and to rejoin them. In the second part, you will implement a simple ALU. In the third and final part, you will gain some hands-on experience with pipelining.


Refer to the Logisim Website or the previous lab for a refresher on Logisim. When you are ready, copy the starter files.

$ cp -r ~cs61c/labs/su14/10 ~/lab10

Part 1: Splitters

Splitters allow you to rewire a multi-bit wire into various combinations of other-sized wires. For example, this shows a 5-bit wire split into 4 1-bit wires, with the middle wire (with a 0-index of 2) thrown out.

Note that splitters can both split OR join wires.

For this part, you will be required to use splitters to implement a rotate-right circuit in the file rotr.circ. A rotate right performs a shift in which the spilled bits wrap around. For example, 0b1011010101110011 rotated to the right by 5 would be 0b1001110110101011. Rotate right can thus be written as two shift operations: R = A >> B | A << (16 - B)

While implementing your rotr circuit, you are NOT ALLOWED to use any shift components. Instead, you will want to use splitters and MUXes. Be careful when approaching this problem; breaking it up into smaller subcircuits is a good idea!

Checkoff [1/4]

Part 2: ALU

In this assignment, you will first implement a small, generic 32-bit ALU in logisim, filling in the given file: alu.circ.

The 8 functions that you will implement are: shift left logical, shift right logical, shift right arithmetic, rotate left, rotate right, and, or, and xor. The ALU will perform a desired function on 2 32-bit inputs and output the result. The selected function will be determined by the value of the control signal, as listed below. You are allowed to use the built-in arithmetic blocks for this section.

Here's what occurs for each operation:

Control Operation
000 Shift Left Logical
001 Shift Right Logical
010 Shift Right Arithmetic
011 Rotate Left
100 Rotate Right
101 And
110 Inclusive Or
111 Exclusive Or

The final critical feature of logisim involves tunnels. Tunnels are grouped by case-sensitive labels given to a wire. Tunnels are used to connect wires like so:

Which has an effect such as the following:

Some care should be taken as to which wires are connected with tunnels to which other wires, such as in this case:

Which in turn has the following effect:

When changing the width of a wire, you should use a bit extender for clarity. For example, consider the following implementation of extending an 8-bit wire into a 16-bit wire:

Whereas the following is much simpler, easier to read, and less error-prone:

Additionally consider the case of throwing out bits. In this example, an 8-bit wire is being converted into a 4-bit wire by throwing out the other bits:

Despite the implications of its name, a bit extender can also do this same operation:

You MUST use tunnels in this section. Also, for this part only, you are NOT ALLOWED to use splitters.

Checkoff [2/4]

Part 3: Pipelining

This next exercise will get you some hands-on practice with pipelining. Assume that on power-on, registers initially contain zeros.

Consider the following 2-input FSM. Its next state and output is computed by multiplying the inputs and adding it to the current state.

Say the propogation delay of a adder block is 55ns, the propogation delay of a multiplication block is 50 ns, and the clk-to-q delay of a register is 5ns. Calculate the maximum clock rate at which this circuit can operate. Assume that the register setup time is negligible, and that both inputs come from clocked registers that receive their data from an outside source.

Checkoff [3/4]

We want to improve the performance of this circuit, and let it operate at a higher clock rate. To do so, we will divide up the multiplication and addition into two different pipeline stages; in the first pipeline stage, we will perform the multiplication of the two inputs. In the second pipeline stage, we will add the product to the state.

Our definition of correctness will be simple: we will consider the sequence of outputs from this circuit correct iff it corresponds to the sequence of outputs the non-pipelined version would emit, potentially with some leading zeros. For example, if for some sequence of inputs the non-pipelined version emits [3,5,1,2,4, ...], a correct circuit might emit the sequence of outputs [0,3,5,1,2,4, ...] for that same sequence of inputs.

For your convenience and to help standardize check-offs, we are providing a starting point in the files pipeline.circ, which includes randomized testing.

  1. Complete the sub-circuit Pipelined. You will need to add a register to divide the multiplication and addition into separate pipeline stages.
  2. Calculate the maximum clock rate for the pipelined version of the circuit.
  3. When we talked about pipelining in lecture, we discussed that if a computation depends on the output of a previous computation, it's difficult to pipeline them and we often need to insert a pipeline bubble (or several) to ensure that the output of the first computation is ready to be an input to the second. Explain why inserting such bubbles is unnecessary for this particular circuit.

Checkoff [4/4]