;;;; Assignment 4 ;;;; ;;;; File: asst4.txt ;;;; Author: CS 51 (Bob Walton) ;;;; Version: 3 The Fibonacci function is to be programmed in three different ways, two of which offer different methods of improving the complexity of the function. You are to roughly estimate the size of the call tree as a function of the input argument for each of these methods. In writing one form of the Fibonacci function, the following assembly language pseudo-operations will be useful: lw rt, symbol ===> la $1, symbol lw rt, 0($1) sw rt, symbol ===> la $1, symbol sw rt, 0($1) where register $1 is reserved for use by the assembler in generating pseudo-instruction code. The three forms of Fibonacci are in three separate files: fibonacci.asm Usual simplest recursive form. memo_fibonacci.asm Memoizing version that uses a cache. tail_fibonacci.asm Tail recursive version with a tail recursive optimization. The specific things you MUST do are: (0) You should reread Sections 1.4.7, 1.4.8, and 1.7.3 of Introduction to Symbolic Computing. The rest of the information you need is in the lecture viewgraphs on computer architecture and assembly language, in the mips and spim help files, and in the spim coding examples. (1) For the theory part of the assignment, do the following exercises from the above reading: 1.4.5.1 1.4.7.1(b) 1.4.8.1 1.7.3.4(a) (give this your best brief shot) Remember to staple this part separately as it will be graded separately from the code. (2) Remember that this is an exercise in hand compilation. You MUST stick to the rewrite rule definitions of the functions when writing C code, and perform a DIRECT translation of the C code into assembly language. (3) For each of the three forms of fibonacci you are given rewrite rules. You MUST write C-code corresponding to these rules for each form of fibonacci function in the indicate place in the form's file. These C-code designs should follow the style of memory_allocator.asm, which is to write straight forward C code for the rewrite rules. This is the design part of this assignment. You are given the design for the cache function, and need not do that. (4) Write the .asm code for the three forms of fibonacci in their corresponding files. You should first write pseudo-C-code after the manner of sum.asm. You should then hand compile the pseudo-C-code into assembly language. The result MUST be that the pseudo-C-code and assembly language code is mixed in with each other after the manner of memory_allocator.asm. There need not be a separate pseudo-C-code section (as there is in sum.asm). Please DO NOT attempt to write optimized code. Write the code that a simple-minded compiler program would output, as is done in the many class examples. You MUST indent your code in a proper readable fashion. We recommend the vi settings :set autoindent showmatch shiftwidth=4 which can be obtained by the .login file line setenv EXINIT ':set ai sm sw=4' which must replace any similar line you used for LISP. This will give indentations that are multiples of 4 spaces. Learn the vi commands << and >> that shift blocks of code left or right by the shiftwidth. Use of vi in this fashion leads to the style of indentation followed in memory_allocator.asm. If you use emacs you will get a different style of indentation that uses both 2 and 4 space indents, and is as in sum.asm. Either is OK. You are given the code for the cache function, and need not do that. In writing tail_fibonacci.asm you MUST follow the following prescription: (1) Write the code for fibonacci_recurse as a recursive function WITHOUT tail recursion optimization, using the standard form of prolog and epilog (see sum.asm and memory_allocator.asm). (2) In the prolog, after the pushes, and before assigns, put the label: fibonacci_tail_recurse: (3) Change any tail recursive call instruction: jal fibonacci_recurse to b fibonacci_tail_recurse This is all you need to do to install the tail recursion optimization. (5) Test the code by running: make fibonacci_debug.out and looking at the results. This is not the final test run, but rather a debugging run. The UNIX command `make' will also work. (6) Time the code by running make fibonacci_timing.out and looking at the results. The UNIX command make timing will also work. The timing here is in the form of counts of different types of instructions. For each run, the number of call instructions minus 1 (for the `main' function call) is the size of the call tree for the fibonacci function. Using the measurements in fibonacci_timing.out, write an equation estimating the size of the call tree for each form of fibonacci function as a function of the input argument m. E.g.: ## Call Tree Size of fibonacci ( m ) ~ 8 * m - 2 ## for 12 <= m <= 22. Enter your estimate in the place given for it at the top of the asm file for each form of fibonacci function. Your estimate need only be valid to within and error of -50% to +100% of the true value, and only for 12 <= m <= 22. Actually, if you perspire you can get it accurate to 0.1%. The theory part of this assignment is worth 15 points. The call tree size estimates are worth 2 points each. The separate C-code is the design part of this assignment and is worth 8 points total. The code part of the assignment, including the pseudo-C-code comments, is worth 31 points. A well written solution requires about the following number of SLOCS for each of the three forms, where a .asm SLOC is any non-comment non-blank .asm file line: C .asm SLOCS SLOCS points fibonacci.asm 2 27 7 memo_fibonacci.asm cached 2 15 4 fibonacci 4 33 8 tail_fibonacci.asm 4 45 11 The points are the number that will be deducted if you do NOT do the function (they do NOT exactly sum to 31). Hints: (1) You should NOT write optimal code. Straight- forward hand compilation of pseudo-C-code is what is desired. (2) Note there are separate tests in fibonacci_ debug.in/out for the cache/cached functions. (3) The file fibonacci_timing.out is printed and submitted. The file fibonacci_debug.out is not printed or submitted, and is just for your own use. (4) `make timing' takes a few tens of seconds to run. Good Luck!