CS61C $ummer 2017 Lab 7: Advanced Logisim

Video of the day

This is my favorite Facebook video of all time: click click

Goals

You will be learning how to use the second tier of essential parts of logisim. In particular...

  • Splitters to take slices of bits on a wire, and to rejoin them
  • Tunnels to avoid 63948732m-long wires
  • And you'll also be making a mini ALU

Official Logisim Stuff

Refer to the Logisim Website or last lab for a refresher on Logisim. This website also has documentation on how all the circuit components in the libraries (left-hand side menu) work, so if you're ever unsure of whether something could be helpful for your circuit, consult our good friend cburch.

Setup

Start all Logisim circuits from scratch. Feel free to do each exercise as separate sub-circuits in the same Logisim file.

Copy the lab files from the instructional servers to your lab account with

$ cp -r ~cs61c/labs/07/ ~/labs/07/

Alternatively, secure-copy (scp) them from the instructional servers to your own laptop with

$ scp -r cs61c-xxx@hive10.cs.berkeley.edu:~cs61c/labs/07/ ~/YOUR_FILEPATH

And if you want to secure-copy them back to your class account:

$ scp -r ~/YOUR_FILEPATH/07 cs61c-xxx@hive10.cs.berkeley.edu:~/YOUR_LABACCT_FILEPATH

Exercises

Advanced Logisim

The following exercises will introduce you to more advanced techniques you can use in Logisim.

Exercise 1: Splitters

This is the last essential tool you will need in this class. The preceding sentence was left in the lab specifications by some person from last semester. It's false. You definitely need some more stuff... like tunnels! To demonstrate its use you will construct a circuit that manipulates an 8-bit number.

Open up the logic simulator program called "Logisim" by typing logisim from the terminal. Or by running it however you like to run it.

  1. Create a new subcircuit and name it "A new subcircuit".
  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. You can do it the other way around too. It can 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.
    • Task: Change bits 1, 2, and 6 to be coming out on fan arm 1 (the middle one).
    • Also, make sure bit 0 is coming out of fan arm 0, and bit 7 is still coming out of fan arm 2.
    • NOTICE that you have to choose the fan arm for each individual bit. NOT the other way around. You can't choose the bits per arm. Kind of annoying if you have a large bit width in.
    • 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. Hook your input up to it.
  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 want Out2 to be the negative "sign and magnitude" value of the input. AKA you should interpret the input as a sign and magnitude number. Sign and magnitude is an alternate way of representing signed values - like 2s complement, but simpler! How do you negate a number a sign and magnitude format? Did you say, "flip its 0th bit?" WRONG.
  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.

Sanity check: the second splitter you placed should be facing the opposite direction as the first splitter.

Checkoff [1/3]

Exercise 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". Not "rotor." 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.

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

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

Believe it or not, the preceding snarky paragraph was NOT written by me. Looks like I have some competition from last semester... I wonder who it was. Anyways, it has some good advice.

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 individual input bits of B (the rotation amount). What can you do with them if you split B with a splitter? Can you do something with the binary form, like with the envelopes in exercise 5 of lab0?


If I want to rotate by 7 = 0b0111, I can rotate once by ___, once by ____, and once by ____


Tip: if you're making some helper subcircuits, think about what you want them to do in your rotr circuit. You'll want to be able to use them as a black box, so make sure they have the correct input and output bit widths.

Tip: To rotate by a fixed amount, you should only require TWO splitters!

Tip: If you've made some helper circuits and are wondering how to combine them, try running the 16-bit input A through a series of MUXes where each MUX decides to either do something or do nothing. Where should their control signals come from?

Checkoff [2/3]

Advanced Logisim Features [PLEASE READ!!]

Here are two more logisim features you will find useful.

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:

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

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

Exercise 3: Logisim ALU

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

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

Here's what occurs for each operation:

Control Operation Description
000 Shift Left Logical Shift source1 left by source2
001 Shift Right Logical Shift source1 right logical by source2
010 Shift Right Arithmetic shift source1 right arithmetic by source2
011 Rotate Left Rotate the bits of source1 left by source2
100 Rotate Right Rotate the bits of source1 right by source2
101 And Compute source1 & source2
110 Inclusive Or Compute source1 | source2
111 Exclusive Or Compute source1 ^ source2

How the heck do I start doing this? Good question! If you've read through the descriptions of the ALU above, you should know that it's just a circuit that can take two inputs and spit out a binary operation on them based on a control signal. What piece of hardware lets you choose between some inputs? (Everybody all together: A _ _ _!!)

So, how do we get the things to wire into the _ _ _? Well, we've laid out the 8 operations we want to be able to do, and if you look at the "Arithmetic" library in the left-hand side dropdown menu, you should find pretty much everything you need to implement these operations. By the way, you ARE allowed to use any and all of these now. You officially have all your rights back! :))))

You'll notice, if you try to use the SHIFTER, that you can't just stick source1 and source2 into the box. This is because if you set the "data bits" field of a shifter to 32, it automatically knows that it only makes sense to shift a 32-bit number by a 5-bit number, so it will start to only accept a 5-bit value for its second input. Smart, huh? But inconvenient for you. Make use of those bit extender things to fix this problem.

HEY!! YOU SHOULD USE SOME TUNNELS. The circuit harness (AKA skeleton) is designed to fit an implementation of the ALU that makes good use of tunnels. You might have to reuse the "source1" and "source2" tunnels a few times :P

Checkoff [3/3]

Exercise 3.5: 61C You Next Week

Question: Why do I keep including an "Exercise 3.5" when there clearly is no "Exercise 3.5?"

Answer: I would honestly feel really sad if I didn't include one. It would break the tradition. It's hard for me to let go of tiny little things like this.

Checkoff [3.5/3]