Assignment 31 (Assigned November 29)

1. (6 points) Consider the data path shown below which can also be used to compare two operands stored in two registers. An instruction like CMP R1, R2 will compare (subtract contents of register R2 from contents of register R1) and store condition codes to be used by a subsequent instruction. Seven branch instructions as given below.

• BGE address /* branch if R1 is greater than or equal to R2 */

• BGT address /* branch if R1 is greater than to R2 */
• BLE address /* branch if R1 is less than or equal to R2 */
• BLT address /* branch if R1 is less than to R2 */
• BNE address /* branch if R1 is not equal to R2 */
• BEQ address /* branch if R1 is equal to R2 */
• BR address /* branch any way */

Each branch instruction is coded and stored in two instruction words. One word contains the type of branch condition to be tested and the second instruction word contains the address to go to if branch condition is met. The execution of branch instruction involves first fetching two words from instruction memory to registers I0 and I1. Then contents of register I1 are brought onto the shared bus (by selecting out of register file) and appropriate ALU and no shift operation. The new value is loaded into PC register if the branch condition is met (which is automatically checked by the control unit from the condition codes as specified in instruction word in I0).

Using these branch and CMP and other instructions you already know, i.e., LD, ST, ADD, SUB, AND, OR, SUB write instruction sequences for the following program segments. (Refer to notes of Lecture 38. In a program, you can use any memory location as a label to specify address.)

1. (3 points) Give the clock period corresponding to the following clock frequencies: (i) 16 MHz; (ii) 250 MHz; and (iii) 400MHz.
2. (4 points) A carry propagation adder takes two bit inputs and a carry-in from a previous stage and produces a sum and carry-out as outputs. It produces these two outputs in 20 nsec. We can hook these components together (that is attaching carry-out of one adder to carry-in of the next adder) in sequence to build an n-bit adder. (a) Give a formula for the time it takes to an n-bit sum and carry. (b) Suppose we redesign the circuit so that it takes to produce 15 nsec to its carry-out output and 25 nsec to produce its sum output. Now, how long it takes to produce an n-bit sum and carry.
3. (3 points) Suppose you are to find the minimum of N integers, each is n-bit long, where N is a power of two. You are given a supply of identical two-input n-bit minimizer components each with a propagation delay of tmin nsec. (a) Give a formula for the propagation delay of a minimizer circuit that is balanced binary tree. (b) Give a formula for the propagation delay of a minimizer circuit that is a linear circuit.
4. (4 points) For a state machine, suppose propagation and contamination delays of the combinational circuit are 100 nsec and 10 nsec, respectively. For the register component, the propagation delay, set up time, and hold time are 40 nsec, 20 nsec, and 20 nsec, respectively. (a) What is minimum clock period required for this state machine? (b) When can the external inputs be changed after clock edge for proper operation? (c) For how long the external inputs be held stable for proper operation? (d) Suppose external outputs of such a state machine are external inputs of a similar state machine. What is the minimum allowable clock period that will ensure proper operation of the cascaded configuration? Show work in each of these cases.