1CS232 Midterm Exam 1February 24, 2003Name: This exam has 6 pages, including this cover and the cheat sheet on the next page. You have 50 minutes; budget your time! No written references or calculators are allowed. To make sure you receive full credit, please write clearly and show your work. We will not answer questions regarding course material.100Total403302301Your ScoreMaximumQuestion2MIPS InstructionsThese are some of the most common MIPS instructions and pseudo-instructions, and should be all you need. However, you are free to use any valid MIPS instructions or pseudo-instruction in your programs.$ra = PC + 4; go to Labeljal Labelgo to address in $rajr $rago to Labelj LabelJumpif ($t1 < 100) then $t0 = 1 else $t0 = 0slti $t0, $t1, 100if ($t1 < $t2) then $t0 = 1 else $t0 = 0slt $t0, $t1, $t2Setif ($t0 < $t1) go to Labelblt $t0, $t1, Labelif ($t0 ≤ $t1) go to Labelble $t0, $t1, Labelif ($t0 > $t1) go to Labelbgt $t0, $t1, Labelif ($t0 ≥ $t1) go to Labelbge $t0, $t1, Labelif ($t0 ≠ $t1) go to Labelbne $t0, $t1, Labelif ($t0 = $t1) go to Labelbeq $t0, $t1, LabelBranchMem[100 + $t1] = $t0sw $t0, 100($t1)$t0 = Mem[100 + $t1]lw $t0, 100($t1)Data Transfer$t0 = 100li $t0, 100$t0 = $t1move $t0, $t1Register Setting$t0 = $t1 mod $t2rem $t0, $t1, $t2$t0 = $t1 ⁄ $t2div $t0, $t1, $t2$t0 = $t1 × $t2mul $t0, $t1, $t2$t0 = $t1 + 100addi $t0, $t1, 100$t0 = $t1 – $t2sub $t0, $t1, $t2$t0 = $t1 + $t2add $t0, $t1, $t2ArithmeticMeaningExample InstructionCategoryThe second source operand of the arithmetic and branch instructions may be a constant.Register ConventionsThe caller is responsible for saving any of the following registers that it needs, before invoking a function:$t0-$t9 $a0-$a3 $v0-$v1The callee is responsible for saving and restoring any of the following registers that it uses:$s0-$s7 $raPerformanceFormula for computing the CPU time of a program P running on a machine X:CPU timeX,P= Number of instructions executedP×CPIX,P× Clock cycle timeXCPI is the average number of clock cycles per instruction, or just:CPI = Number of cycles needed ⁄ Number of instructions executed3Question 1: Understanding MIPS programs (30 points)flathead:addi $t0, $a2, 1loop:bge $t0, $a1, exitmul $t1, $t0, 4add $t1, $t1, $a0lw $t2, 0($t1)sub $t1, $t1, 4sw $t2, 0($t1)addi $t0, $t0, 1j loopexit:jr $raPart (a)Translate the flathead function above into a high-level language like C or Java. You should include a header that lists the types of any arguments and return values. Also, your code should be as concise as possible, without any gotos or explicit pointers. We will not deduct points for syntax errors unless they are significant enough to alter the meaning of your code. (20 points)Part (b)Describe briefly, in English, what this function does. (10 points)4Question 2: Performance (30 points)Below is a C function that returns the index of the smallest element in an integer array V[], which contains nitems. A translation of this function into MIPS assembly language is shown to the right. Registers $a0 and $a1 correspond to V[] and n. The index of the minimal element is placed in $v0 as the return value.minimum:lw $t0, 0($a0) # min = V[0]addi $t1, $0, 1 #i=1loop:bge $t1, $a1, exit # i >= n ?mul $t2, $t1, 4add $t2, $t2, $a0lw $t2, 0($t2) # $t2 = V[i]bge $t2, $t0, next # V[i] >= min ?add $t0, $t2, $0 # min = V[i]next:addi $t1, $t1, 1 # i++j loopexit:add $v0, $t0, $0 # return minjr $raint minimum(int V[], int n){int min, i;min = V[0];for(i=1;i<n;i++)if (V[i] < min)min = V[i];return min;}Say that we run this program on a 500MHz processor, with a clock cycle time of 2ns. The CPIs for different types of MIPS instructions are given below; you can assume mul and bge each count as one instruction.3branches and jumps5loads10mul4addsCPIInstruction typePart (a)Assume minimum is passed an array with the numbers from 101 to 1 in descending order (101, 100, 99, …, 3, 2, 1). What would be the exact CPU time for the function call, in nanoseconds? (15points)5Question 2 continuedPart (b)It is possible to replace mul $t2, $t1, 4 by the following two instructions.add $t2, $t1, $t1add $t2, $t2, $t2What would be the exact CPU time in nanoseconds if we made this modification to the original code, and called the minimum function with the same input array 101, 100, 99, …, 3, 2, 1? (10 points)Part (c)What is the performance increase or decrease of the modified code in Part (b) compared to the original? You may leave your answer as a fraction. (5 points)6Question 3: Writing a nested function (40 points)Here is a C function count. Its arguments A[] and n are an integer array and the number of items in the array. The code passes eachelement of A[] to another function test, and counts the number of times test returns 1.Translate this into a MIPS assembly language function. Argument registers $a0 and $a1 will correspond to A[] and n, and the return value should be placed in $v0 as usual.int count(int A[], int n){int i;int num = 0;for(i=0;i<n;i++) {if (test(A[i]) == 1) {num++;}}return num;} Assume that we already have the MIPS function test, which takes an integer argument in $a0 and returns 0 or 1 in $v0. You will not be graded on the efficiency of your code, but you must follow all MIPS
View Full Document