| CPSC 220 | Introduction to Computer Architecture | Fall 2008 |
In this lab, which is due in two weeks, we will model the hardware in software. This will help give you a clear idea for how the hardware works. In particular, we are going to model a very simple arithmetic logic unit (ALU) in Java. As detailed in the exercise below, you will not be able to use the full functionality of Java, but instead will be restricted to mainly boolean operations, which will force you to write an ALU in software in a similar way to how it is designed in hardware. The diagrams of the ALU (or parts of the ALU) from class and the textbook will be an important resource in this lab. You will need to follow them closely in order to write the Java code. Make sure you look them over and understand them.
Create a lab04 directory within the ~/cs220 directory that you created in lab 1 for use in this lab. Change to the newly-created lab04 directory. Copy the provided files from the directory /classes/f08/cs220/labs/lab04 to your new lab04 directory.
If you have forgotten how to manipulate files and directories, check out the Using Linux tutorial or lab 2 from CS 124. As a reminder (these commands will not be provided in later labs), here are the commands you need to perform the steps above:
bash$ mkdir ~/cs220/lab04 bash$ cd ~/cs220/lab04 bash$ cp /classes/f08/cs220/labs/lab04/* ~/cs220/lab04/
Note: the rest of this lab assumes you are in your lab04 directory.
The three files Calculator.java, ALU.java, and TextIO.java should now have been copied to your lab04 directory. Calculator.java is a class that repeatedly prompts the user for an operation (e.g., addition, AND) and two operands, and then returns the result of that operation. To perform the operation it uses ALU.java, which is mainly incomplete and will need to be completed for lab04. But both classes will compile, and you can run Calculator, although it will always return 0 as the result since ALU is largely unimplemented (you will complete it in lab04). As always, TextIO.java defines some methods for reading data typed by the user into your program. Note: it must reside in the same directory as the programs that use it, so make sure it was actually copied to the lab04 directory. You will not need to use TextIO directly in this lab, however, it is used by the provided class Calculator.java.
There is one exercise for this week's lab. It is due in two weeks, not one week, at the start of lab on 10/9. Remember to use good programming style as laid out in lab 1.
In this exercise you build an arithmetic logic unit (ALU) in software. You will write an ALU class in Java that will perform various arithmetic operations. In particular, it should be able to add, subtract, and multiply two binary numbers (if you do the extra credit it will also be able to divide two numbers). It should also be able to OR, AND, and XOR two binary values. Finally, it should be able to NOT a single binary value.
I've provided a Calculator class, which will repeatedly get input from the user and call a calc method within the ALU class. So you will not have to worry about getting input from the user, printing out results or converting between decimal and binary as this will all be done by my Calculator class. My Calculator class passes the calc method in your ALU class two 8-bit binary values encoded using 2's complement (note: for NOT only the first value is used). These are represented using arrays of booleans. It also passes the calc method an opcode, which indicates the particular operation (0 for add, 1 for subtract, etc. -- see ALU.java for details). The opcode is encoded as a 3-bit, unsigned value, which is represented using an array of booleans. To reiterate, each operand is an 8-bit signed value and the opcode is a 3-bit unsigned value, and all three are represented using boolean arrays.
To encode a binary value in a boolean array the 0th position in the array will represent the 0th position or 1's place in the binary value, the 1st position in the array will represent the 1st position or 2's place in the binary value, and so on. Note: this works in the opposite way as the representation we used with Strings in the previous labs. For Strings, the 0th character was actually the leftmost bit and not the rightmost bit (which was for printing purposes). Let's look at an example to make this concrete. Assume the boolean array for the opcode and operands 1 and 2 are as follows (note: the entries of the array are listed in reverse order):
| Opcode: |
|
||||||||||||||||
| Operand 1: |
|
||||||||||||||||
| Operand 2: |
|
In this case, the opcode represents the unsigned, binary value 101 or 5, which refers to the AND operation (see ALU.java for details on the particular opcodes). Operand 1 represents 01101100 and operand 2 represents 11000110. Using conversions from previous labs (which you will not have to do in this lab), operand 1 represents 108 in decimal and operand 2 represents -58. Your calc method will need to compute the result of performing this operation. It will do this computation in a similar way to the hardware implementation of the ALU and return the following result, 68, as a boolean array (note: your ALU class never works with decimal values):
| Result: |
|
Your task is to complete ALU.java. However, there are some restrictions on what you can use in Java to ensure that your ALU class works similarly to a hardware implementation. For example, you cannot use any arithmetic operator such as +, -, *, / or bit vector operand such as &, |, ~, <<, >>, >>> (there is one exception discussed below). You may only use boolean operands, i.e., &&, ||, and !. These will act similarly to an AND gate, OR gate, and NOT gate, respectively. Also, with one exception, you may not use any statement besides an assignment statement and a method call. Therefore, you may not use if statements, switch statements, while loops, etc. The one exception to these rules is that you are allowed to use a for loop to iterate over a boolean array. For example, if you need to take the complement of a binary value stored as a boolean array in the variable binaryValue, you could use the following:
for (int i = 0; i < 8; i++)
binaryValue[i] = !binaryValue[i];
Note: the expression on the right hand side of the assignment can be as complicated as you like so long as it only involves boolean operators (e.g., (!b1 && b2) || b3). Note also that you cannot perform any additional arithmetic in the for loop or use the iterator variable (e.g., i) to set a binary value. The for loop can only be used to repeat a particular set of boolean operations.
To complete this exercise you will need to take the figures from in class and in the textbook and translate these into the equivalent Java code. For example, a not gate translates into the boolean ! operation, an AND gate translates into the boolean && operation, and an OR gate translates into the boolean || operation. There is one method already defined for you in ALU.java that performs the NOT operation. It should be straightforward to use this same approach to implement the AND, OR, and XOR operations. For addition, you will need to use the figures from class to first build a full 1-bit adder and then a ripple carry adder. For subtraction, you can leverage your addition implementation by using multiplexors as shown in class. Once you have an adder, you can also build a multiplier using the figure from class. The divider may be implemented for extra credit (it is not required).
One important thing that you will need to simulate in software is a multiplexor or mux. This is necessary to implement subtraction and multiplication. It is also necessary to select between the various operations based on the particular opcode. As a reminder, you cannot use if statements or switch statements, so you will definitely need to build a multiplexor out of boolean operators (look at the mux diagram to see how this can be done).
Feel free to define as many methods as you would like, and to insert a method call where ever you would like. For example, you may want to have a method for each supported operation (add, subtract, multiply, etc.). You may also want a method for doing a full 1-bit adder. Your add operation can use the full adder method (i.e., it can call it) to implement a ripple carry adder. A similar approach will help you in building the subtraction and multiplication operations, which should be built on top of the add operation. Note: you may only call methods defined within the ALU class. In fact, you may not use any outside classes of any kind. If you are in doubt about whether or not you are following the rules, then ask the instructor.
Finally, although you cannot use if statements in your final solution, you may want to use them initially and remove them later. For example, you could start out by using an if statement to select between the various operations based on the opcode, and later change this code to simulate a multiplexor (i.e., select using boolean operations rather than an if statement). This will help you write your program incrementally. For instance, you can focus on implementing each operation before worrying about implementing a mux.
As stated above, for extra credit you can implement the last operation: division. You will need to figure out how this works on your own. Make sure that you complete the rest of the exercise before attempting the extra credit.
Verify that your lab04 folder contains all of the files you created or modified for this lab (which is just ALU.java in this case), then copy your entire lab04 folder to the handin directory ~mcorliss/handin/cs220/username (where username is replaced with your username). For example, if your working directory is ~/cs220/lab04/ then you could do the following:
cp -r ~/cs220/lab04 ~mcorliss/handin/cs220/username
where username is replaced with your particular username (e.g., mcorliss).