CS 351 Computer Architecture Fall 2005

CS 351 Computer Architecture Fall 2005

Practice Problems for Mid-Semester # 1 with solutions:

1) (a) Translate the following assembly code back to equivalent C code:

addi $t0, $zero, 1 # i = 1

addi $v0, $zero, 1 # v = 1

Loop: sle $t1, $t0, $a0 # set $t1 to 1 if (i < arg)

beq $t1, $zero, Exit # exit loop if (i >= arg)

mul $v0, $v0, $t0 # v *= i

addi $t0, $t0, 1 # i ++

j Loop # loop

Solution:

int v = 1;

for (int i = 1 ; i < arg ; i ++) {

v = v * i;

}

(b) What function does the above code perform?

Solution: factorial

2) Add a comment to each statement of the following MIPS assembly procedure:

Describe the computation performed by this code.

Solution:

3) (a) Write a recursive procedure binomial(n, m) (in C) where n and m are 32 bit positive integers to compute the binomial coefficient using the formula . Make sure that you provide appropriate exit conditions.

Solution:

int binomial(int n, int m) {

if ((m == 0) || (n == m)) return 1;

if (n == 0) return 0;

else return binomial(n-1, m) + binomial(n-1, m-1);

}

(b) Translate your code C for binomial(n, m) into MIPS assembly code.

Presented in class.

4) Shown below are five single precision floating-point integers in the IEEE 754 format. Arrange them from the smallest to the largest.

Solution: C, A, E, B, D where the numbers are A, B, C, D, E from top to bottom.

5)  Design a circuit of depth O(log n) that takes n input bits, and outputs 1 (0) if there is an odd (even) number of 1’s in the input.

The above is the circuit for n = 4, and generalization is obvious.

6)  Design a circuit of depth O(log n) that takes n input bits b1 b2… bn and outputs the binary representation of b1 b2… bn +1. (When all the input bits are 1, the output should be a string of n zeroes. (i.e., overflow is ignored.) Use a recursive approach to design the circuit and show clearly that the depth of the circuit is O(log n).

Solution: To make this recursive, we will generalize this problem slightly. We assume that there is an extra input bit e (enable) such that when e = 1, the output is input + 1, and when e = 0, the output = the input. (Also, we will assume that when the input is a string of 1’s, the output will be a string of 0’s.

The recursive construction was presented in class.

7) Exercise 3.11

Solution:

8) Exercise 3.14

Solution:

9) Write a code segment in MIPS assembly language that sets $t0 to 1 (0) if the architecture uses big-endian (little-endian) notation.

Solution: li $t0, 0x01000000

addi $sp, $sp, -4

sw $t0, 0($sp)

lb $t0, $sp

addi $sp, $sp, 4

10) Exercise 3.13

Solution:

11) Exercise 2.31

Assume that the code from Ex 2.30 is run on a machine with 2 GHz clock that requires the following number of cycles for each instruction:

add, addi, sll -> 1 cycle, lw, bne -> 2 cycles. In the worst-case, how many seconds will it take to execute the code?

Solution:

12) Exercise 2.43

Solution: