Unit 1e

Creating the Comparison Sub-Block

Efficient Comparison in the MIPS ALU

For the comparison operations, Set on Less Than (SLT) and Set on Less Than Unsigned (SLTU), we wish to determine whether the input A is less than the input B. If it is, we wish to set the result to X"0000000000000001". If it is not, we wish to set the result to X"0000000000000000".

Let's start by looking at the calculation we wish to perform: A < B. Using a little simple algebra, this expression can be rewritten as A - B < 0. If we were to subtract B from A, then all that would remain is the relatively trivial matter of determining whether the result is less than zero. Instead of a large comparator which will consume a number of gates, we can once again reuse our single adder with a minimal amount of logic looking at the output.

First, we must make sure that our existing Arithmetic sub-block is performing a subtraction operation. This will occur when ALUOp(1 DOWNTO 0) is either "10" or "11". fortunately, we only have two comparison operations to perform. SLT will require a signed subtraction, thus it will be encoded as ALUOp(1 DOWNTO 0) = "10". SLTU will require an unsigned subtraction, thus it will be encoded as ALUOp(1 DOWNTO 0) = "11". The remaining two encodings for this sub-block will be undefined.

Now, the question is how do we determine if the result is less than zero based on the four inputs which we have defined to the Comparison sub-block: CarryOut from the subtractor, Bit 63 of the subtractor result (RSign), Bit 63 of the input A (ASign), and Bit 63 of the input B (BSign).

Lets start with the Signed version. There are four possible combinations of the signs of the inputs: both are positive; both are negative; A is positive and B is negative; A is negative and B is positive. When the signs of the inputs are different, our problem is trivial. If A is negative and B positive, then A MUST be less than B. Conversely, if A is positive and B is negative then A CAN NEVER be less than B. When the inputs have the same sign we need to look at the result of the signed subtraction. Two inputs with the same sign can never cause an overflow in subtraction, so we do not have to concern ourselves with an incorrect answer due to that. If the inputs are of the same sign, then whenever A is smaller than B the result of subtracting A - B MUST be a negative number. So, if the sign of the result, SignR, is negative we have A < B and if it is positive then we have A > B.

For the Unsigned version of the comparison we have a simple test. In unsigned representation, A and B are both positive numbers. Subtracting two positive numbers will result in a positive number if A > B or a negative number if A < B. However, we cannot represent a negative number with an Unsigned integer: if we try we will have an overflow condition. Overflow for unsigned subtraction means that the result is a negative number (it is impossible to subtract two unsigned numbers and get a result too large to represent). We can test for the occurence of overflow in unsigned subtraction by looking at the Carry Out of the most significant bit. In unsigned addition, the existence of a Carry Out indicates overflow. In unsigned subtraction, however, the situation is reversed: Carry Out high is the normal state and Carry Out low indicates overflow. Thus, since we are performing unsigned subtraction in our SLTU, if there is no Carry Out, then we had an overflow and A - B is less than zero and A < B is true. If there is a Carry Out, then A - B is greater than zero and A < B is false.

Since we are only concerned with four input bits to determine our output, we will be implementing the Comparison sub-block by creating a Truth Table view.

Creating a Truth Table View for the Comparison Sub-Block

• First, you need to open a new Truth Table view for the Comparison sub-block. Do this by opening the ALU block diagram, right-clicking over the Comparison sub-block, and selecting Open/New View from the pop-up menu. In the Create New View window which appears, select Truth Table from the list box and accept the default name of table.tt.

  The Truth Table view window will appear similar to Figure 1.

  

  Figure 1

• First, relabel the columns in the following order: ALUOp (1 downto 0), Asign, Bsign, Rsign, CarryOut, ComparisonR. You may resize the rows and columns of the Truth Table by moving the pointer over the lines separating the row and column headers (which are in gray), left-clicking, and dragging to the desired height or width just like in a spreadsheet program. Resize the ASign, BSign, RSign, and CarryOut columns so that the signal names just fit. Now make the ComparisonR column much larger because it will be holding a 64-bit wide vector. Your view should look something like Figure 2.

  

  Figure 2

• We will need more than four rows in this Truth Table. A row can be added, by right-clicking anywhere over the table and selecting Add Row from the pop-up menu. Add six more rows so that your table looks like Figure 3.

  

  Figure 3

• Now we will start to add information to the table. Values are entered by left-clicking on the appropriate cell and typing in the data. Don't Care values are specified by leaving a cell empty. Don't care's are useful to shorten the length of the table when a particular entry does not depend on the state of one or more of the inputs. For example, to completely specify the truth table for our design with six bits of input we would need 64 rows but by using don't cares we can reduce that to 10.

  The first thing to look at is the fact that we don't have a defined operation for ALUOp = "00" or ALUOp = "01". These operations should never actually be issued for the Comparison unit, but as a default, we will output the value X"0000000000000000". So, in the ALUOp cell of the first row, enter the value 00 and in the corresponding ComparisonR cell enter "0000000000000000000000000000000000000000000000000000000000000000" (Using Hex notation here will not work with std_logic_vectors, the design will generate, but there will be errors when you attemp to compile). In the same manner, enter row two with ALUOp as 01 and ComparisonR as "0000000000000000000000000000000000000000000000000000000000000000". Your table should now look like Figure 4. We have now specified 32 rows of data in 2 rows because of the use of don't care values for the bits ASign, BSign, RSign, and CarryOut.

  

  Figure 4

• Now we will look at the signed comparison operation, SLT, which is performed when ALUOp is equal to "10". Remember from above that there were three possible situations: A and B have the same sign, A is positive and B is negative, or A is negative and B is positive.

  Let's start with the case of both inputs having the same sign. This occurs when ASign = '0' and BSign = '0' or ASign = '1' and BSign = '1'. In each case all we need to do is look at the sign of the result, RSign. If RSign = '0' then the result is positive and we want to output FALSE, or "0000000000000000000000000000000000000000000000000000000000000000". If RSign = '1' then the result is negative and the output is TRUE, or "0000000000000000000000000000000000000000000000000000000000000001". We can do this by entering four lines on the table as seen in Figure 5.

  

  Figure 5

  Now we have two cases left. When ASign = '0' and BSign = '1' we have A as a positive number and B as a negative number, meaning that A must be greater than B and our result is always going to be false. This means that we don't care what the value of RSign or CarryOut is. Conversely, when ASign = '1' and BSign = '0' then A is negative and B is positive and A must be less than B so our result is always true. This is implemented in two lines of the table which have been added in Figure 6.

  

  Figure 6

  We have now completely specified the behavior of the table for SLT, or ALUOp(1 DOWNTO 0) = "10". Check to see that by expanding the existing 6 lines of the table with don't cares you would get 16 lines.

• We have two lines left to fill in in the table which will specify the last 16 cases and correspond to ALUOp(1 DOWNTO 0) = "11", or Set on Less than Unsigned. Remember from above that we can test for A < B unsigned by performing an unsigned subtraction and checking for an overflow indicated by examining carry out from the most significant bit of the adder. So, if we are performing SLTU all we need to look at is the CarryOut signal. If CarryOut = '1', then we did not have overflow, hence A - B > 0 and we report FALSE. If CarryOut = '0', then we have had an overflow and A - B < 0 so we report TRUE. This has been implemented in the table in Figure 7.

  

  Figure 7

• The Comparison sub-block is difficult to fully test in a stand-alone manner due to the fact that it requires the Arithmetic sub-block to function correctly. However, it is also a relatively simple sub-block, so we will put off testing its functionality for now and verify that it works correctly when we are simulating the entire ALU.

• Now that you have finished defining the last of the Operation sub-blocks, all that is left to complete the ALU is to Fill in the Mux4B64 sub-block.