Lab 1 -- The Arithmetic and Logic Unit

Related Reading

1.1 Machine Words

The memory of a computer is divided into fixed-sized units called cells. Each cell has a unique address and can hold one machine word. A word is the unit of information in the machine. At the hardware level, a machine word is a collection of bits with no inherent meaning: the same word can mean different things in different contexts. For example, the 8-bit word 11101111 could refer to:

Dealing with bit-encodings is tedious. We will therefore abstract from the level of bits in our representation of machine words and use integers in decimal notation instead. But to benefit from the full power of Java, we encapsulate the integer representation of a word in an object:

public class Word {
	private int integerRep;
	
	protected Word (int integerRep) { this.integerRep = integerRep; }

	public int toInt() { return integerRep; }

	public String toString () { return String.valueOf(integerRep); }
}

The encapsulated integer is declared private; it is only accessible to the outside world via two public methods: toInt and toString. The first is presumably used by clients wishing to perform arithmetic calculations on the machine word, and the second used to display a printable representation of the machine word. The constructor that creates new machine words is protected which somewhat limits its access. You are encouraged to find the precise effect of the protected qualifier from a Java reference.

As discussed above, there are several kinds of machine words: address, data, and instructions. These special kinds of words extend the behavior of generic words, and hence are naturally encoded using subclass of Word. We defer discussion of the classes Address and Instruction until a later point. The class Data is defined as follows:

public class Data extends Word {
	public Data (int value) { super(value); }
}

The declaration extends Word means that every possible operation on a Word object is also possible on a Data object. In particular, Data objects can respond to the methods toInt and toString. The constructor for each object uses super to call the constructor of the superclass, i.e., the constructor for Word .

1.2 The Arithmetic and Logic Unit (ALU)

The Arithmetic and Logic Unit (which is usually referred to as the ALU) is the subsystem that performs operations such as addition (add), subtraction (sub), incrementing (inc), decrementing (dec), and comparison (compare). The arithmetic operations have the usual meaning. The comparison operation takes two machine words and sets indicators based on their relative values. The ALU contains three condition codes that serve as indicators: GT, EQ, and LT, which stand for greater than, equal to, and less than, respectively. The operation compare(x,y) returns no value but sets the condition codes as follows:

	x  > y 		GT=true	      EQ=false      LT=false
	x  = y 		GT=false      EQ=true       LT=false
	x  < y 		GT=false      EQ=false      LT=true

Abstractly speaking, the ALU is just an object with methods add, sub, inc, dec, and compare that implement the required operations, as well as three methods to read the contents of the condition codes. This analysis is formalized in the following interface for the ALU:

public interface ALUI {
	boolean fetchGT ();
	boolean fetchEQ ();
	boolean fetchLT ();

	Word add (Word w1, Word w2);
	Word sub (Word w1, Word w2);
	Word inc (Word w);
	Word dec (Word w);
	void compare (Word w1, Word w2);
}

The implementation of the interface ALUI is almost straightforward. For example, add can be implemented as follows:

public Word add (Word w1, Word w2) {
	int i1 = w1.toInt();
	int i2 = w2.toInt();
	return new Data (i1+i2);
}

In other words, we use Java's built-in operator + to implement addition in our machine. This is sensible but may not have the desired behavior in some situations.

The problem is that Java's + is not really the mathematical function +. In mathematics, we have:

	2000000000 + 2000000000 = 4000000000

but in Java we have:

	2000000000 + 2000000000 = -294967296

because Java specifies that an int is allocated exactly 32-bits in the Java virtual machine.

Thus if we want to simulate a hardware machine with words bigger than 32-bits, we cannot use Java's int and its associated operations to implement the machine's arithmetic operations. Fortunately, Java provides other datatypes with the right functionality. For example, we can use the long datatype or the bignum package for this purpose.

The important point to stress here is that one must be aware of the programming language conventions regarding arithmetic before using them.

1.3 Exercise

Create a new directory duckMachine that will contain the entire implementation of the machine. In this directory, create another directory architecture that will contain the Java package that implements the architecture of the machine. We will later implement other packages, e.g.,a graphical user interface for the machine.

Your job is to write a class ALU that implements the interface ALUI. You can use Java's arithmetic operations on integers to implement the ALU's operations but please document the decision. You can find some help files at the URL:

http://www.cs.uoregon.edu/~sabry/duckMachine/ALU/

For this assignment, the help files supplied to you are:

**Important notes on compiling and executing your java programs:

The following notes on compiling and executing your Java programs assumes that you have stored them in some duckMachine/architecture/ directory.

To compile:

Move to the same level of your directory structure as the duckMachine sub-directory before issuing the compile command. For example, suppose you have stored your java programs in the following directory:

c:\cis211\duckMachine\architecture\

Then to compile correctly, you must first move to the c:\cis211 directory before issuing the command:

 javac duckMachine\architecture\*.java 
Remember, if you're working in Unix, the \'s go the other way, e.g.,
javac duckMachine/architecture/*.java 

To execute:

From the same level of the directory structure as you compiled from, issue the command:

 java duckMachine.architecture.TestALU 

Test your implementation by running the Java interpreter on the class TestALU. A successful execution of the test program should produce the following output:

1+9 = 10
9-4 = 5
inc 8 = 9
dec 8 = 7
compare 9 and 1
	GT flag = true
	EQ flag = false
	LT flag = false
compare 9 and 9
	GT flag = false
	EQ flag = true
	LT flag = false
compare 9 and 10
	GT flag = false
	EQ flag = false
	LT flag = true

Turn in the code for ALU.java during class on Monday, April 12th. Write the lab (day and time) that you are attending on top of your assignment in addition to your name and SS#.


Visited times since March 23, 1999 (or the last crash).

Last modified: 03/31/99 09:24:25

yreimer@cs.uoregon.edu