CS274: Computer Architecture - MIPS Processor Design: The ALU

Activity Goals

The goals of this activity are:

1. To incorporate the design of a 1-bit adder into a 1-bit ALU
2. To combine 1-bit ALUs into a 32-bit ALU design
3. To support subtraction within a 32-bit adder
4. To enable status bits to support the MIPS isntruction set from an ALU
5. To optimize an ALU for performance using a Carry Lookahead Adder

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

---

Model 1: Review: Components for a 1-bit Adder

sum = (A xor B) xor carryIn
carryOut = ((A xor B) and carryIn) or (A and B)

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Questions

1. Draw a 1-bit adder using these logic formulas

---

Model 2: A Multiplexor Circuit

A	B	select	Z
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Questions

1. The multiplexor (or "mux") takes two inputs and selects one of them: for example, A passes through if select is 0, and B passes through if select is 1. Draw a truth table and circuit for an ALU that selects between four options (you will need two select bits).

---

Model 3: A 1-bit ALU

Questions

1. Add the select line to this ALU such that the AND operation is select bits 00, the OR operation is select bits 01, and the adder is select bits 10. Call this select line operation.

---

Model 4: A 32-bit ALU

Questions

1. Suppose you had an 8-bit ALU. Connect each of the 8-bits of the inputs A and B to 8 individual ALUs. Where would you connect the select operation lines, and the carry inputs and outputs? Sketch your final result.

---

Model 5: Subtraction

Questions

1. Recall that binary subtraction involves adding the two's-complement inverse of B to A. Modify your 1-bit ALU design to invert B, and select either it or the original B value using a multiplexor. You can call your new select input bInvert.
2. However, you must also add 1 to the final answer to perform the two's complement. How can you use the existing 32-bit ALU design to add 1 in the one's place?

---

Model 6: Overflow Detection

MSB
carryIn	0	0	0	0	1	1	1	1
A	0	0	1	1	0	0	1	1
B	0	1	0	1	0	1	0	1
sum	0	1	1	0	1	0	0	1
carryOut	0	0	0	1	0	1	1	1
A sign?	+	+	-	-	+	+	-	-
B sign?	+	-	+	-	+	-	+	-
sum sign?	+	-	-	+	-	+	+	-
Overflow?	No	No	No	Yes	Yes	No	No	No

Questions

1. Can overflow occur when adding values of different signs? Why or why not?
2. For the cases where overflow occurs, what do their inputs and outputs have in common?
3. Look again at the cases where overflow does not occur. How do the carry bits ultimately indicate whether overflow will or will not occur?
4. Draw a truth table and circuit diagram using only the most significant carry in and out bits to indicate overflow detection.

---

Model 7: Status Bits (Zero and Less)

Questions

1. If you are performing subtraction, what will you know about B compared to A if the result is negative?
2. Add a status line called less to the output of the most significant bit ALU.
3. What does overflow do to the sign bit of the output? If overflow occurs, can we fix the less bit output, and how?
4. Draw a truth table with the less bit, overflow bit, and resulting "correct" less output. What circuit is this? Add it to your ALU!
5. What circuit can tell you if all 32 bits of the ALU result line are 0? Add an ALU output called zero that is set to 1 when this occurs. Hint - add a logic circuit that indicates if any of the bits is 1, and then negate it.

---

Model 8: Parallelized Addition with the Carry Lookahead Adder

A	B	Carry State	Logic formula
0	0	kill	A NOR B
0	1	propagate	A XOR B
1	0	propagate	A XOR B
1	1	generate	A AND B

Questions

1. What carry out bit is always generated if both A and B are 1?
2. What carry out bit is always generated if both A and B are 0?
3. What should the carry out bit be if A and B are different?
4. Write a logic formula for the carry out bit based on the carry in, generate, and propagate detection bits.
5. Sketch a "carry lookahead" circuit that outputs all 32 carry bits.
6. Design an ALU that adds all 32 bits in parallel using this carry lookahead circuit.

---

Model 9: Key Formulas and Concepts Recap

A quick-reference recap of the key rules from this activity. Try to reproduce each one from memory before peeking!

Key Rules and Formulas

• 1-bit full adder: sum = (A XOR B) XOR carryIn; carryOut = ((A XOR B) AND carryIn) OR (A AND B). Micro-example: A=1, B=0, carryIn=1 gives sum = 1 XOR 1 = 0, carryOut = (1 AND 1) OR 0 = 1.
• 1-bit ALU: compute A AND B, A OR B, and the adder's sum in parallel, and use a multiplexor with select lines (00 = AND, 01 = OR, 10 = add) to pick the operation's output.
• 32-bit ALU: chain 32 one-bit ALUs; each carryOut feeds the next bit's carryIn, and all bits share the operation select lines.
• Subtraction: A - B = A + ~B + 1: set bInvert = 1 to select the inverted B input, and set the ones-place carryIn = 1 to supply the "+1" of the two's complement for free.
• Overflow: overflow = carryIn XOR carryOut at the most significant bit.
• Zero status bit: zero = NOT(result31 OR result30 OR ... OR result0) - OR every result bit and negate (a NOR of all 32 bits).
• Less / set-on-less-than: subtract B from A; the sign bit of the result feeds the less output of bit 0. If overflow occurred, the sign bit is wrong, so correct it: less = sign XOR overflow.
• Carry lookahead: define g = A AND B (generate) and p = A XOR B (propagate); then carryOut_i+1 = g_i OR (p_i AND carryIn_i). Expanding lets all carries be computed in parallel instead of rippling. Micro-example: c1 = g0 + p0*c0; c2 = g1 + p1*g0 + p1*p0*c0.

1-bit ALU (bit i):
            bInvert     operation (2 bits)
               |            |
  A_i ====+==[AND]==+
          |  [OR ]==+==[ MUX ]== result_i
  B_i =[inv?]=+==[ADD]==+
                   |  |
            carryIn_i  carryOut_i --> to bit i+1

Glossary

Term	Meaning
ALU	Arithmetic Logic Unit: computes AND, OR, add, subtract, and comparisons
Multiplexor (mux)	A selector circuit: select bits choose which input passes through
bInvert	Control line that swaps B for its bitwise inverse (for subtraction)
Status bits	Extra ALU outputs (zero, less, overflow) that the instruction set uses for branches and slt
Zero bit	1 when all result bits are 0; used by beq/bne
Less bit	1 when A < B, taken from the (overflow-corrected) sign of A - B
Ripple-carry adder	Adder whose carries pass sequentially from bit to bit (slow: 32 stages)
Generate (g)	A AND B: this column produces a carry no matter what comes in
Propagate (p)	A XOR B: this column passes an incoming carry along
Carry lookahead adder	Adder computing all carries in parallel from g and p terms

Questions

1. Without looking, write the settings of bInvert, carryIn, and operation needed to compute A - B, and the formula for the overflow bit.

---

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.