1CS232 Midterm Exam 1February 18, 2002Name:• This exam has 6 pages, including this cover and the cheat sheet on the next page.• There are three questions worth a total of 100 points.• You have only 50 minutes, so 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.Question Maximum Your Score130240330Total 1002MIPS 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.Category Example Meaningadd $t0, $t1, $t2 $t0 = $t1 + $t2sub $t0, $t1, $t2 $t0 = $t1 - $t2addi $t0, $t1, 100 $t0 = $t1 + 100mul $t0, $t1, $t2 $t0 = $t1 * $t2move $t0, $t1 $t0 = $t1Arithmeticli $t0, 100 $t0 = 100lw $t0, 100($t1) $t0 = Mem[100 + $t1]DataTransfersw $t0, 100($t1) Mem[100 + $t1] = $t1beq $t0, $t1, Label if ($t0 == $t1) go to Labelbne $t0, $t1, Label if ($t0 != $t1) go to Labelbge $t0, $t1, Label if ($t0 >= $t1) go to Labelbgt $t0, $t1, Label if ($t0 > $t1) go to Labelble $t0, $t1, Label if ($t0 <= $t1) go to LabelBranchblt $t0, $t1, Label if ($t0 < $t1) go to Labelslt $t0, $t1, $t2 if ($t1 < $t2) then $t0 = 1; else $t0 = 0Setslti $t0, $t1, 100 if ($t1 < 100) then $t0 = 1; else $t0 = 0j Label go to Labeljr $ra gotoaddressin$raJumpjal Label $ra = PC + 4; go to LabelThe second source operand of sub, mul, and all the branch instructions may be a constant.Register ConventionsThecaller is responsible for saving any of the following registers that it needs, before invoking a function:$t0-$t9 $a0-$a3 $v0-$v1Thecallee 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 executedPxCPIX,Px Clock cycle timeXCPI is the average number of clock cycles per instruction, or:CPI = Number of cycles needed / Number of instructions executed3Question 1: Understanding MIPS programs (30 points)Ostrich:bge $a1, $a2, Duckmul $t1, $a1, 4add $t1, $a0, $t1mul $t2, $a2, 4add $t2, $a0, $t2lw $t3, 0($t1)lw $t4, 0($t2)sw $t3, 0($t2)sw $t4, 0($t1)addi $a1, $a1, 1sub $a2, $a2, 1j OstrichDuck:jr $raPart (a)TranslateOstrich into a high-level language like C or Java. Be sure to describe the number and types of anyarguments and return values. We will not deduct points for syntax errorsunless they are significant enoughto alter the meaning of your code. (25 points)Part (b)Describe briefly, in English, what this function does. (5 points)4Question 2: Performance (40 points)Let’s study the performance of this function. Assume that we have a 500MHz processor with a clock cycletime of 2ns. The table below shows CPIs for some various classes of MIPS instructions. (You can assumethat pseudoinstructions are also accounted for in this table.)Part (a)What is the CPU time of this function in nanoseconds, assuming that the loop is executed 100 times? Inother words, the “bge” test fails 100 times and then succeeds on the 101st test. (10 points)Ostrich:bge $a1, $a2, Duckmul $t1, $a1, 4add $t1, $a0, $t1mul $t2, $a2, 4add $t2, $a0, $t2lw $t3, 0($t1)lw $t4, 0($t2)sw $t3, 0($t2)sw $t4, 0($t1)addi $a1, $a1, 1sub $a2, $a2, 1j OstrichDuck:jr $raInstruction class CPImul 5branches and jumps 3data transfers 3all others 15Question 2 continuedPart (b)Our code is somewhat slow, since expensive multiplication operations are executed repeatedly. Rewrite thefunction to eliminate both multiplications from the main body of the loop. (20 points)Ostrich:bge $a1, $a2, Duckmul $t1, $a1, 4add $t1, $a0, $t1mul $t2, $a2, 4add $t2, $a0, $t2lw $t3, 0($t1)lw $t4, 0($t2)sw $t3, 0($t2)sw $t4, 0($t1)addi $a1, $a1, 1sub $a2, $a2, 1j OstrichDuck:jr $raPart (c)What is the CPU time in nanoseconds for 100 loop iterations of your revised function? (10 points)Instruction class CPImul 5branches and jumps 3data transfers 3all others 16Question 3: Writing a nested function (30 points)Show how to translate the pseudocode below forSelectionSort into a MIPS assembly language function.This algorithm first finds the largest element in A[0]..A[n] and moves it to position n, then finds the largestelement in A[0]..A[n-1] and puts that in position n-1, and so forth.• You will not be graded on the efficiency of your code, but youmust follow all MIPS conventions.• Assume that you already have a MIPS functionMaxIndex, which takes two arguments A and n, andreturns the index of the largest element of A[0]..A[n]. The arguments and return values are passed inregisters $a0, $a1 and $v0 respectively.• Remember that integers are 32-bit, or 4-byte, MIPS quantities.SelectionSort(A, n)for i=ndownto 1m = MaxIndex(A, i) // Find the largest element in A[0]..A[i]exchange A[i] and A[m] // Move it to position
View Full Document
Unlocking...