COMPUTER ORGANIZATION September
19, 2002
WC3824-001
(CSEE) HOMEWORK #2
PROF. TONY JEBARA
|
DUE |
TUESDAY,
OCTOBER 1st, 2002 AT BEGINNING OF CLASS |
Please
use the class newsgroup (bulletin board) for questions, updates,
clarifications, and corrections related to the homework. It is linked off of
the class home page: http://www.cs.Columbia.edu/~jebara/3824
As a
second resort, you can also email a TA directly: kdunn@cs.columbia.edu or am2104@columbia.edu.
1. (20
points):
Patterson and Hennessy Exercise 3.19. Start by reading the ‘In more depth’
section from p. 201-202 first.
Note:
“Instruction bytes fetched” refers to the total number of instructions bytes
that are read from memory. Recall that instructions are stored in memory; each
instruction must be read (“fetched”) from memory before it can be executed.
“Memory-data bytes transferred” refers to the number of data bytes
transferred to and from memory. For example, in a load-store architecture such
as MIPS, sw transfers 1 word to memory from the processor and lw
transfers 1 word of data from memory to the processor. In a memory-memory
architecture, a=b+c requires data to be transferred first from
memory into the processor, the result computed, and the result then stored back
to memory. You should add up (i) total bytes transferred from memory and
(ii) total bytes transferred to memory.
2. (5
points): Patterson
and Hennessy Exercise 3.20.
3. (20
points):
Patterson and Hennessy Exercise 3.23. Make sure to follow the callee-caller
conventions we discussed (and in the text) for storing and restoring registers.
You do not need to write a “main” routine, just the procedure’s code fragment
by itself.
Whenever
using the stack and procedure calls in the homework, follow the protocol and
conventions we covered in class (i.e. $a0-$a3 argument registers, $v0-$v1
output registers, $sp stack pointer, etc. do not save unnecessary registers,
etc.) and which are described in detail in section A.6 of the text (starting on
page A-22).
4. (30
points):
Patterson and Hennessy Exercise 3.25. Follow the same guidelines as the
previous question above.
5. (30
points):
Patterson and Hennessy Exercise 3.26. Read p. 204 first.
6. (30
points):
Patterson and Hennessy Exercise 3.27. Read p. 204 first.
7. (20
points):
Patterson and Hennessy Exercise 3.28. Read p. 204 first.
8. (45 points): Iterative Factorial Function
(SPIM). Below is C code for an iterative version of the factorial function,
factorial. Factorial sequences were presented in class as a recursive
function and have the following pattern: factorial(0)=1, factorial(1)=1,
factorial(2)=2, factorial(3)=6, factorial(4)=24, etc. Here you will implement
an iterative function instead that does not call itself recursively. Recall the
mathematical definition of factorial is:
factorial(n) = n*(n-1)*(n-2)*…*3*2*1*1
int factorial(n)
{
int res = 1;
if (n<2)
return(res);
for (i=2;
i<=n; i++) {
res = res*i;
}
return(res);
}
Write a MIPS assembly version of the function as a
procedure. You should also write a main routine which calls factorial.
Your main routine should call it at least 4 times with different test cases by using
the $a0-$a3 registers (it should work for any value of n, in principle). Be
sure to use the caller-callee conventions as outlined above and in class. Put
comments in your program to make it easy to read and understand.
Use the SPIM simulator to test our your code and to make
it output results on the console. Use syscalls as in the example code on
the class web page and the SPIM documentation to output results on the console.
Print for each test case the value of n and the result of factorial(n). See pages
A-26 to A-32 for details on syscalls.
SPIM is
available for download through the class web page http://www.cs.columbia.edu/~jebara/3824
if you follow the ‘Tutorials’ link. You can obtain the Windows or X versions of
it from there. Please also read the documentation from Larus’s web page. On the
class page there are a few example assembly programs you should be able to
download and run to get an idea of how things work. Follow those links to get
familiar with SPIM, we will discuss SPIM further in the lectures and in a
recitation and use it more in forthcoming homeworks.
Note, you
will only need to hand in your assembly code for this question, either
hand-written or as a print-out. You don’t need to show the console output or
the SPIM registers and status windows.