Slide 1Fibonacci numbersProceduresSlide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Direct mapped cache implementation of instruction memoryRecursive function execution: step by stepRecursive function execution: step by stepRecursive function execution: step by stepRecursive function execution: step by stepRecursive function execution: step by stepRecursive function execution: step by stepRecursive function execution: step by stepRecursive function execution: step by stepRecursive function execution: step by stepIs code optimal?ECE 15B Computer OrganizationSpring 2011Dmitri StrukovPartially adapted from Computer Organization and Design, 4th edition, Patterson and Hennessy,Fibonacci numbersF(n) = F(n-1)+F(n-2)F(1) = 1F(2) = 1n = 1 2 3 4 5 6 …F(n) = 1 1 2 3 5 8 …/* Recursive function in c */int fib(int n) {If (n==1) return 1;If (n==2) return 1;return fib(n-1)+fib(n-2); } ECE 15B Spring 2011ProceduresProlog - spill all register to stack used by procedure expect for $t0-$t9 and the one used for returning values- advance stack pointer ($sp) first then write to stackBodycode of the procedure Epilog - restore all used registers - adjust stack pointer at the end ($sp)ECE 15B Spring 2011ECE 15B Spring 2011/* Recursive function in c */int fib(int n) {If (n==1) return 1;If (n==2) return 1;return fib(n-1)+fib(n-2); } # Recursive function in MIPS assembler #prolog FIB: addi $sp, $sp, -12sw $a0, 0($sp)sw $s0, 4($sp)sw $ra, 8($ra)# bodyaddi $v0, $zero, 1addi $t0, $zero, 1beq $a0, $t0, EPILOG #check for n==1addi $t0, $zero, 2beq $a0, $t0, EPILOG #check for n==2addi $a0, $a0, -1jal FIB #calculate fib(n-1)addi $s0, $zero, $v0 # save fib(n-1) to $s0addi $a0, $a0, -1 #calculate fib(n-2) jal FIBaddi $v0, $v0, $s0#epilogEPILOG: lw $a0, 0($sp)lw $s0, 4,($sp)lw $ra, 8,($sp)addi $sp, $sp, 12 jr $ra/* Recursive function in c */int fib(int n) { v0 = 1;If (n==1) goto EXIT;If (n==2) goto EXIT; n = n – 1;s0 = fib(n); n = n – 1;v0 = fib(n); v0 = v0 +s0; EXIT: return v0; }ECE 15B Spring 2011/* Recursive function in c */int fib(int n) {If (n==1) return 1;If (n==2) return 1;return fib(n-1)+fib(n-2); } # Recursive function in MIPS assembler #prolog FIB: addi $sp, $sp, -12sw $a0, 0($sp)sw $s0, 4($sp)sw $ra, 8($ra)# bodyaddi $v0, $zero, 1addi $t0, $zero, 1beq $a0, $t0, EPILOG #check for n==1addi $t0, $zero, 2beq $a0, $t0, EPILOG #check for n==2addi $a0, $a0, -1jal FIB #calculate fib(n-1)addi $s0, $zero, $v0 # save fib(n-1) to $s0addi $a0, $a0, -1 #calculate fib(n-2) jal FIBaddi $v0, $v0, $s0#epilogEPILOG: lw $a0, 0($sp)lw $s0, 4,($sp)lw $ra, 8,($sp)addi $sp, $sp, 12 jr $ra/* Recursive function in c */int fib(int n) { v0 = 1;If (n==1) goto EXIT;If (n==2) goto EXIT; n = n – 1;s0 = fib(n); n = n – 1;v0 = fib(n); v0 = v0 +s0; EXIT: return v0; }•Now let’s see changes in the memory (stack) and register file as we execute recursive function with n = 3 •First let’s review datapath and where code is storedECE 15B Spring 2011Simple datapath review ECE 15B Spring 2011Simple datapath review ECE 15B Spring 2011stackinstructionsWhere is the code stored?ECE 15B Spring 2011stackstackCode (????)static datadynamic data (heap)RF[$sp]0ANS: In main memoryInstruction memoryECE 15B Spring 2011stackcodestatic datadynamic data (heap)IM: Physically different memory Logically mapped to main memoryDirect mapped cache implementation of instruction memoryECE 15B Spring 2011Main Main memoryInstruction memoryAt any point in time IM has a copy of a portion of main memorySeparate memory (tag) to store which location is currently mapped 01624Tag (28 bit)If upper portion of PC (28 bit) matches tag then IM has right values (hit), otherwise stop execution and load right portionRecursive function execution: step by stepECE 15B Spring 20110x0100 addi $a0, $zero, 30x0104 jal FIB0x0108 next instructionXXXXXXXXXXXXXXXXXXXXXXFIB: 0x1000 addi $sp, $sp, -120x1004 sw $a0, 0($sp)0x1008 sw $s0, 4($sp)0x100C sw $ra, 8($ra)0x1010 addi $v0, $zero, 10x1014 addi $t0, $zero, 10x1018 beq $a0, $t0, EPILOG0x101C addi $t0, $zero, 20x1020 beq $a0, $t0, EPILOG0x1024 addi $a0, $a0, -10x1028 jal FIB0x102C addi $s0, $zero, $v00x1030 addi $a0, $a0, -1 0x1034 jal FIB0x1038 addi $v0, $v0, $s0EPILOG: 0x103C lw $a0, 0($sp)0x1040 lw $s0, 4,($sp)0x1044 lw $ra, 8,($sp)0x1048 addi $sp, $sp, 12 0x104C jr $raindex value$v0 0$a0 3$t0 0$s0 0$sp 0xFFFF0000$ra 0x0108index value0xFFFF0000 0x000000000xFFFF00FC0xFFFF00F80xFFFF00F4RF (right after execution of initial jal FIB at 0x0104)MM (initial values in stack)Recursive function execution: step by stepECE 15B Spring 20110x0100 addi $a0, $zero, 30x0104 jal FIB0x0108 next instructionXXXXXXXXXXXXXXXXXXXXXXFIB: 0x1000 addi $sp, $sp, -120x1004 sw $a0, 0($sp)0x1008 sw $s0, 4($sp)0x100C sw $ra, 8($ra)0x1010 addi $v0, $zero, 10x1014 addi $t0, $zero, 10x1018 beq $a0, $t0, EPILOG0x101C addi $t0, $zero, 20x1020 beq $a0, $t0, EPILOG0x1024 addi $a0, $a0, -10x1028 jal FIB0x102C addi $s0, $zero, $v00x1030 addi $a0, $a0, -1 0x1034 jal FIB0x1038 addi $v0, $v0, $s0EPILOG: 0x103C lw $a0, 0($sp)0x1040 lw $s0, 4,($sp)0x1044 lw $ra, 8,($sp)0x1048 addi $sp, $sp, 12 0x104C jr $raindex value$v0 1$a0 2$t0 2$s0 0$sp 0xFFFF00F4$ra 0x102Cindex value0xFFFF0100 0x000000000xFFFF00FC 0x01080xFFFF00F8 00xFFFF00F4 3RF (after execution jal FIB at 0x1028)MM - stackRecursive function execution: step by stepECE 15B Spring 20110x0100 addi $a0, $zero, 30x0104 jal FIB0x0108 next instructionXXXXXXXXXXXXXXXXXXXXXXFIB: 0x1000 addi $sp, $sp, -120x1004 sw $a0, 0($sp)0x1008 sw $s0, 4($sp)0x100C sw $ra, 8($ra)0x1010 addi $v0, $zero, 10x1014 addi $t0, $zero, 10x1018 beq $a0, $t0, EPILOG0x101C addi $t0, $zero, 20x1020 beq $a0, $t0, EPILOG0x1024 addi $a0, $a0, -10x1028 jal FIB0x102C addi $s0, $zero, $v00x1030 addi $a0, $a0, -1 0x1034