This is a tough question, but I\'m hoping someone out there might find this easy

Question

This is a tough question, but I'm hoping someone out there might find this easy and fun to do. Will highly appreciate any help.. QUESTION: Write a MIPS program that iteratively (not recursively) computes the first n Fibonacci numbers. Derive a pipeline schedule for this program, and calculate the CPI in terms of an algebraic expression that has variables n. the number of pipeline stages N of the MIPS IF-ID-EX-MEM-WB pipeline, and the total number of instructions processed M.

Explanation / Answer

# Calculating Fibonacci numbers # fib(0) = 0 # fib(1) = 1 # fib(n) = fib(n-1)+fib(n-2) .text .globl main print_str: li $v0, 4 # print string at ($a0) syscall # jr $ra # return; print_eol la $a0, eol # print " " li $v0, 4 # syscall # jr $ra # return; print_int: li $v0, 1 # print integer ($a0) syscall # jr $ra # return; # fib(n) - recursive function to compute nth Fibonacci number # fib: sub $sp,$sp,12 # save registers on stack sw $a0, 0($sp) # save $a0 = n sw $s0, 4($sp) # save $s0 sw $ra, 8($sp) # save $ra to allow recursive calls bgt $a0,1, gen # if n>1 then goto generic case move $v0,$a0 # output = input if n=0 or n=1 j rreg # goto restore registers gen: sub $a0,$a0,1 # param = n-1 jal fib # compute fib(n-1) move $s0,$v0 # save fib(n-1) sub $a0,$a0,1 # set param to n-2 jal fib # and make recursive call add $v0, $v0, $s0 # $v0 = fib(n-2)+fib(n-1) rreg: lw $a0, 0($sp) # restore registers from stack lw $s0, 4($sp) # lw $ra, 8($sp) # add $sp, $sp, 12 # decrease the stack size jr $ra main: la $a0, en # print "n = " jal print_str li $v0, 5 # read integer syscall # move $a0, $v0 # $a0 := $v0x7. ELEMENTS OF STYLE 11 jal fib # call fib(n) move $s0, $v0 # store result in $s0 la $a0, fibstr # print "fib(n) = " jal print_str # move $a0,$s0 # print fib(n) jal print_int # jal print_eol # print " " li $v0,10 # exit syscall # .data eol: .asciiz " " en: .asciiz "n = " fibstr: .asciiz "fib(n) = " The overall structure is simple, except that at the beginning of the proce- dure fib, some registers are saved that are restored at the end of the procedure.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.