Technology

1. (5 points) Draw the CMOS transistor diagram for an XOR gate. Assume you are given the inputs A, A', B, and B'. Hint: remember, the function of a gate is the NOT of the function implemented by the nMOS network. So one way to implement an XOR is to implement the truth table of NOT XOR in the nMOS network.

2. (5 points) In class we learned that the combinational inverters NAND and NOR are universal, i.e., you can build any boolean function using combinations of NANDs and NORs. As it turns out other types of combinational circuits are universal too. For instance, a 1-bit 2-to-1 MUX is also universal. Prove this by demonstrating how you can construct NOT, OR, and AND gates using this MUX. Hint: the key is in providing some constant inputs to the MUX.

3. (5 points) Consider the truth table for the following three-input, two-output function:

A B C -> D E
0 0 0 -> 0 0
0 0 1 -> 0 0
0 1 0 -> 1 1
0 1 1 -> 1 1
1 0 0 -> 0 0
1 0 1 -> 0 0
1 1 0 -> 1 1
1 1 1 -> 0 1

How many terms must a PLA support in order to implement these two functions? Use Boolean algebra to simplify the two-level logic formulas for the functions D and E to their simplest form. Show the steps and the rules invoked.

Computer Arithmetic

4. (5 points) Powers of two are as important in computer software as they are in computer hardware. It is often useful in software to tell whether a (positive) number is a power of two. Use MIPS or R372 instructions to design a fast power-of-two test "if (is_power_of_two R1)". Just so you know what to shoot for, including the branch itself the fastest test uses three instructions. Hint: think of a unique property of the binary representation of numbers that are powers of two that you could exploit.

5. (15 points) Consider a 32-bit adder. Compute the number of gate levels for the 0th, 5th, 16th, 20th, and 31st sum bits for the following adder designs:

• Ripple-carry
• Carry speculate with four sub-adders
• Carry speculate with eight sub-adders
• Carry lookahead with four-input blocks at the first level and an eight-input block at the second level.
• Carry lookahead with four-input blocks at the first level, four-input blocks at the second level, and a two-input block at the third level.

6. (15 points) Given the multiplicand -55 and the multiplier 93, trace the following multiplication algorithms: a) adder-only, b) Booth's, and c) modified bit-pair Booth's algorithm. Assume that the multiplier (M) and multiplicand (A) have a fixed width of 8 bits and the product (P) has a fixed width of 16 bits. Show the steps individually. At each step, show the current product in binary and label the action taken by the multiplier (e.g., P = P + A). Assume the third multipler implementation in which the product register is shifted to the right.

7. (10 points) Divide the binary representation of 104 by 6 using the division algorithm shown in class. Assume that the divisor (S), dividend (D), quotient (Q), and remainder (R) are all 8 bits wide. At each step, show the quotient and remainder and label the action taken by the divider (e.g., Q = Q - S).

R372 Assembly Programming

(40 points) If you noticed, the R372 is conspicuously missing one of the arithmetic instructions: divide. The primary reason for this is that (as you have seen in class), the divide circuit is cumbersome to implement in hardware. The multiply circuit is somewhat simpler to implement, but is a sequential circuit. Since our first R372 processor implementation will be "single-cycle", it will not be able to support multiplication. How will you test your matrix multiply program then?

Never fear. For this exercise, you will implement multiplication and division in software as R372 assembly routines using the single-cycle R372 operations, i.e., all operations other than multiplication.

The multiply routine should have the following interface. It should be called MULS. For the input arguments, the multiplicand should be in R3 and the multiplier should be in R4. For the return value, R2 should contain the lower 16 bits of the product. You can ignore overflow.

The divide routine should have the following interface. It should be called DIVS. For the input arguments, R3 should contain the dividend and R4 should contain the divisor. For the return value, R2 should contain the quotient. You can ignore the remainder.

Both multiplier and divider should work with negative numbers. You can use any multiplication or division algorithm you want (hint: it's easier to use conventional software ones than ones that correspond directly to the hardware algorithms learned in class), but you are not allowed to call MULS from within DIVS.

As for program linkage, you may assume that the stack pointer is in R1. Also, the only register either MULS or DIVS can externally modify is the return value register R2.

Turn in a file muldiv.a that contains both functions. The file should not contain a :MAIN function, although for testing you may want to create one temporarily. Again, in addition to a hardcopy, mail the file as an ASCII text attachment to ggupta@seas with the subject line "CSE 371 Homework 2" and your name as the body of the message.