=========================preview======================
(COMP180)midterm-02.pdf
Back to COMP180 Login to download
======================================================
Question 1. (15%)
Consider a complier C1 runs on a machine M that has a clock rate 250MHz. There are four types of instructions that are used by C. The average number of cycles for each instruction type on the machine is given in the following table:
Instruction Type Usage in C1 Average CPI
ALU operations 43% 1
Loads 21% 2
Stores 12% 2
Branches 24% 2

The complier C1 is then optimized to C2 such that C2 is able to discard 50% of the ALU operations but other instructions remain the same.
(a)
What is the average CPI for C1 and C2 on M? [5 pts]

CPI for C1 = 0.43x1 + 0.21x2 + 0.12x2 + 0.24x2 = 1.57 CPI for C2 = (0.43x0.5x1 + 0.21x2 + 0.12x2 + 0.24x2)/(1-0.43x0.5) = 1.73

(b)
Compared with C1, do you think that the performance of C2 is actually better than C1? Explain why or why not. [5 pts]


Ratio of CPU times for C1 and C2 = (CPI1/CPI2) x (IC1/IC2)
= (1.57/1.73) x 1/(1C 0.43x0.5)
= 1.156

C2 is 1.156 times faster than C1
(c) Using the data given in this question to explain why the MIPS (million instructions per second) rating fails to give a true picture of performance. [5 pts]
MIPS for C2 = 250/1.73 = 144.5 and MIPS for C1 = 250/1.57 = 159.25
It shows that MIPS rating is lower for C2 but in fact CPU time for C2 is shorter..

Question 2. (25%)
Assume a machine with a 500-MHz clock requires the following number of cycles for each instruction:
Instructions Cycles
add, addi, slt 1
lw, sw, bne 2
Others 3

(a) Consider the following fragment of C code: for (i = 0; i < 100; i = i + 1) {a[i] = b[i] + c;}. Assume that the variables a and b are arrays of words and the base address of a is stored in $a0 and the base address of b is stored in $a1. The register $t0 is associated with the variable i and the register $s0 with the variable c. The constants 4 and 401 are available in memory locations whose labels are AddConst4 and AddConst401, respectively. Write the code for MIPS with short comments to aid comprehension. (No pseudoinstruction is allowed.) [10 pts]
add $t0, $zero, $zero // temp reg $t0 = 0 lw $t1, 0($s0) // temp reg $t1 = c lw $t2, AddConst4($zero) // temp reg $t2 = 4 lw $t3 AddConst401($zero) // temp reg $t3 = 401 sub $t3, $t3, $t2 // temp reg $t3 = 401 C 4 = 397
Loop: add $t4, $a1, $t0 // temp reg $t4 = address of b[i] lw $t5, 0($t4) // temp reg $t5 = b[i] add $t6, $t5, $t1 // temp reg $t6 = b[i] + c add $t7, $a0, $t0 // temp reg $t7 = address of a[i] sw $t6, 0($t7) // a[i] = b[i] + c add $t0, $t0, $t2 // i = i + 4 slt $t8, $t0, $t3 // $t8 = 1 if $t0 < 397, i.e. i < 100 bne $t8, $zero, Loop // goto loop if i < 100
(b)
How many clock cycles will it take to execute the code? [5 pts]

(c)
The following code fragment finds the most frequently occurred word in the array. It processes an array and produces the word found count $v1 and its frequency count in registers $v0. Assume that the array consists of 5000 words indexed 0 through 4999, a