CS61C Spring 2014 Lab 12 - Project 4 Prelude

TA: Kevin Liston

In this assignment, you will first implement a 32 bit ALU in logisim. This lab assignment is similar to the CPU design project (it is essentially a slightly simpler version of Project 4's ALU). You will then create a small program that can later be used to help test your Project 4 implementation. Hopefully by getting a headstart here in lab, Project 4 will go a bit more smoothly!

Copy the starter lab files as usual, from the directory: ~cs61c/labs/12

Logisim ALU

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. For all operations, the procedure to perform is: Result = Source1 OP Source2. For shifts and rotates, Source2 amounts greater than 5 bits give undefined results.

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

Tunnels

The final feature of logisim required to complete this lab (and Project 4) are tunnels. Tunnels are grouped by case-sensitive labels give 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:

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:

You MUST use tunnels in this lab and in Project 4. Also, for this lab only, you are NOT ALLOWED to use splitters.

On Built-in logic blocks

In project 4, you will essentially have no restrictions on what logic blocks you may use, with the notable exception of using items from the Memory library in your ALU. The ALU should be stateless. We reserve the right to dock points on Project 4 for unjustifiable design decisions.

Checkoff

Ida Assembly

Read the Project 4 Ida Manual before continuing.

Your task here is to implement the following bubblesort algorithms in Ida. You will need to also read through how the supplied assembler and emulator for Ida is run. Your program should output the sorted contents of memory that is given as an input. Furthermore, your program should not make any function calls within the body of the sort method. In this code, a = 0 (this does not mean NULL) and n = 1000.

void sort(int * a, int n) {
  bool swapped;
  do {
    swapped = false;
    for(int i=1; i<n; i++) {
      if(A[i-1]>A[i]) {
        swap(A[i-1], A[i]);
        swapped = true;
      }
    }
  } while(swapped);
}

Assemble your code with the following command:

$ java -jar Ida.jar sort.ida

Execute your code on the emulator:

$ java -jar Ida.jar -exec sort.hex sort.in.hex

This should create an output file sort.out.hex that contains the sorted contents of data memory.

After you have completed your Project 4 implementation, you can use this program as one out of hopefully many tests for correctness. In fact, you can view the contents of data memory and watch the values actually bubble down. However, do note that this algorithm is fairly slow when run in logisim. You might consider testing a smaller sort size.

Checkoff