Slide 1AgendaFibonacci numbersProceduresSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Direct 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?Instruction formatsInstruction formatsInstruction formatsR-format ExampleBasic addressing modesSpecific Addressing Mode in MIPSMIPS PC-relative or branch addressingPseudodirect or Jump AddressingTarget Addressing ExampleNote on the PC incrementingBranching Far AwayVarious specific addressing modes in other ISAsExample: Basic x86 Addressing ModesExample of decoding and addressing modes in datapathSlide 37Datapath With ControlR-Type InstructionLoad InstructionBranch-on-Equal InstructionImplementing JumpsDatapath With Jumps AddedAdvanced Topics: Code density examplesRecent study (2009)Code density examplesECE 15B Computer OrganizationSpring 2011Dmitri StrukovPartially adapted from Computer Organization and Design, 4th edition, Patterson and Hennessy,Agenda•Recursive function (correction to the last lecture)Wrap-up of HW part (except for floating point)•Instruction formats•Addressing modesECE 15B Spring 2011Fibonacci 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