CS61C Fall 2016 Lab 6: Advanced Logisim and ALU Design

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 prepare for your project 3 by designing a basic ALU.

Reading

P&H 4.5, 4.6
Refer to the Logisim Website or last week's lab for a refresher on Logisim.

Setup

For part A, start all Logisim circuits from scratch. Feel free to do each exercise as separate sub-circuits in the same Logisim file.

For part B, we've provided you with a starter Logisim circuit.

$ cp -r ~cs61c/labs/06 [appropriate directory]

Alternatively, you can download the file here.

Exercises

Part A: Advanced Logisim

The following exercises will introduce you to more advanced techniques/concepts in Logisim.

Exercise A.1: Splitters

This is the last essential tool you will need in this class. To demonstrate its use you will construct a circuit that manipulates an 8-bit number.
  1. Create a new subcircuit and name it "Ex1".
  2. Add an 8-bit input pin to your circuit and label it.
  3. Add a 1-bit output pin labeled "Out1" and an 8-bit output pin labeled "Out2" to your circuit.
  4. Go to the Wiring folder and select the Splitter circuit. This circuit will take a wire and split it into a smaller set of wires. Conversely, it can also take many sets of wires and combine them into a larger bus.
  5. Before you place your circuit, change the "Bit Width In" property (bus width) to 8, and "Fan Out" property (# of branches) 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 the splitter output so bit 0 is coming out on fan arm 0, bits 1 through 6 are coming out on fan arm 1 (the middle one), and bit 7 is coming out on fan arm 2. FYI: the "None" option means that the selected bit will not come out on ANY of the fan arms.
  7. Once you configure your splitter, you can place your splitter into your circuit.
  8. Attach a 2-input AND gate to fan arms 0 and 2 and route the output of the AND gate to Out1.
  9. Now we interpret the input as a "sign and magnitude" value. We want Out2 (when interpeted as a "sign and magnitude" number) to be the negative of the input. How do we multiply a "sign and magnitude" number by -1?
  10. We will need another splitter to recombine the fans into a single 8-bit bus. Place another splitter with the proper properties (Bit Width In: 8, Fan Out: 3, correct fan widths). Play with the Facing and Appearance properties to make your final circuit as clean-looking as possible.

Checkoff

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 0b1011010101110011 and B were 0b0101 (5 in decimal), the output of the block would be 0b1001110110101011. 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 by B bit positions, as outlined above. You are NOT allowed to use Logisim shifters in your solution, though all other combinational logic (MUXes, constants, gates, adders, etc.) is allowed. Show off your rotr subcircuit in the main subcircuit.

Hint: Before you start wiring, you should think very 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.

Hint, the second: Just because we gave you an RTL representation doesn't mean it's the best way to look at this problem. Think about the input bits of B and think about how to effectively use splitters!

Tip: In exercise A.1, you practiced adjusting the splitters so you can have one bit coming out of one fan output, and multiple bits coming out of another. Try to keep your fan-out to a minimum to keep your circuits easy to work with.

Checkoff

Advanced Logisim Features

Here are two more logisim features you will find useful. After reading about tunnels and extenders, begin part B below.

Tunnels

A tunnel allows you draw an "invisible wire" to bind two points together. Tunnels are grouped by case-sensitive labels give to a wire. They 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:

A warning: if your tunnels do not have EXACTLY the same name, they will not connect your wires. I once spent hours looking for a bug. Turned out in one tunnel, I had a lower case L "l" and in the other I had an upper case i "I". Hopefully this warning will save you some time ;)

We strongly recommend you use tunnels with Logisim, because they make your circuits much cleaner looking, and therefore easier to debug.

Extenders

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 16-bit wire by throwing out the other bits:

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

Part B: Logisim ALU

In this exercise, you will first implement a 32 bit ALU in Logisim. Remember: we have provided a starter file!

As a reminder, recall that ALU stands for Arithmetic Logic Unit. An ALU is a fundamental building block of a CPU (central processing unit) and it performs integer arithmetic and logical (bitwise) operations. The function that the ALU performs (e.g. add, xor) is determined by the control of our datapath, which is determined by the instruction the processor is executing. The ALU is highlighted in a simplified datapath diagram below:

This lab assignment is similar to the CPU design project that we will have in a couple weeks (it is essentially a slightly simpler version of Project 3's ALU). Hopefully by getting a headstart here in lab, Project 3 will go a bit more smoothly!

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 can use built in Logisim circuits for these operations, don't worry about reimplementing them all on your own.

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

Hint: did you notice that an ALU kindof looks like a big MUX? This is not an accident!


Checkoff