CS61C Lab 5b

Advanced Logisim and Basic Pipelining

Background

Goals

There are two 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 gain some hands-on experience with pipelining.

Reading

P&H 4.5, 4.6 (4th edition)

Refer to the Logisim Website or last week's lab for a refresher on Logisim.

Part (A): Advanced Logisim

The following exercises will introduce you to how wires work in logism.

Exercise A.1: Splitters

This is the last essential tool you will need in this class. To demonstrate it's use you will construct a circuit that will output 1 when the most significant bit and least significant bit are 1.
  1. Create a new subcircuit and name it "Exer1".
  2. Add an 8 bit input pin to your circuit.
  3. Add a 1 bit output pin to your circuit.
  4. Go to the base folder and select the Splitter circuit. This circuit will take a wire and split it into a smaller set of wires.
  5. Before you place your circuit, change the "Bit Width In" property to 8, and "Fan Out" property to 3. If you move your cursor over the schematic, your cursor should look as follows:
  6. Now, select which bits to send out to which part of your fan. The least significant bit is bit 0 and the most significant bit is bit 7. Change bits 1, 2, and 6 to be coming out on fan arm 1. Alternatively, you can have bits 1, 2, and 6 to not come out on any of the fan arms by selecting "None"
  7. Once you configure your splitter, you can place your splitter into your circuit.
  8. Add an AND gate and complete the circuit.

Checkoff

Show your Exer1 circuit.  
Tell your TA a more meaningful name for the Exer1 circuit.  

Exercise A.2: Rotate Right

With your knowledge of splitters and your knowledge and experience with multiplexers from the last lab, you are ready to implement a non-trivial combinational logic block: rotr, which stands for "Rotate Right". The idea is that rotr A,B will "rotate" the bit pattern of input A to the right by B bits. So, if A were 1011010101110011 and B were 0101 (5 in decimal), the output of the block would be 1001110110101011. Notice that the rightmost 5 bits were rotated off the right end of the value and back onto the left end. In RTL, the operation would be something like "R = A >> B | A << (16 - B)".

You must implement a subcircuit named "rotr" with the following inputs:

The output should be A rotated right B bit positions, as outlined above. Please do not use logisim shifters in your solution. Show off your rotr subcircuit in the main subcircuit.

Hint: Before you start wiring, you should think veeeerrrry carefully about how you might decompose this problem into smaller ones and join them together. You should feel very free to use subcircuits when implementing rotr. If you don't, expect to regret it.

Checkoff

Show your TA your rotr circuit and verify that it works  

Part (B): 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 50ns, 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 are clocked registers that receive their data from an outside source.

Checkoff

Show your TA the calculations you performed to find the maximum clock rate.  

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.

Note that we need a register to hold the intermediate value of the computation between pipeline stages. This is a general theme with pipelines.

  1. 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

Show your TA the completed, pipelined circuit.  
Show your TA the calculations you performed to find the maximum clock rate.  
Explain to your TA why bubbles are unecessary in this circuit.  
In lecture we will discuss why one can't simply increase the number of pipeline stages to magically improve performance. Something to think about...