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
- Show your ALU circuit to your TA.
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
- Show your sort.ida code to your TA.
- What aspects of Ida might this program not test?