|
CSE 410 Computer Systems - Homework 3 - Spring 2009 |
|
 CSE Home |
About Us |
Search |
Contact Info |
Due: Thursday, April 23, at 11 pm.
This assignment is intended to give you more experience with MIPS programming, in particular the standard procedure call sequence. There are also a few questions on two's complement numbers.
int mumble(int a, int b) {
int x;
int y;
x = 3;
y = 17+a;
x = foo(a,y,x);
return x+y+b;
}
mumble.
The stack frame should follow the conventions described in class and should
include space to save registers, space for local variables, and an argument
build area. You should allocate space for both local variables (x and y).
Show the location of the stack pointer ($sp) in your picture as it
appears after it has been changed at the beginning of procedure mumble to
allocate the stack frame, and show
the offsets
of
each of the variables, saved registers, and other items in the stack frame
by writing
the name and offset of each item.mumble to MIPS assembly language by hand.
Your translation should follow the standard MIPS calling conventions as outlined
in class. For the purposes of this exercise, wherever an assignment statement
in the original code stores a value in a variable, your answer should include
code to actually store
the value in the appropriate location in the stack frame allocated for that
variable, even though in normal assembly language code you might well be able
to leave the
value(s)
in some
register(s) and not have to store them to memroy.foo other
than it has three integer arguments and returns an integer result, and that
the label foo is defined elsewhere in the code.Write a MIPS procedure sort and a main program to test it on
two different integer arrays. The sorting algorithm should
be selection sort, implemented as described below. Your program should also
include
a procedure
to print an integer array and use it to print each array both before and
after sorting. Your program should be stored in a file named sort.s and you
should run it using SPIM.
Selection Sort
The idea behind selection sort is to repeatedly scan the unsorted part of the array for its smallest element and move that element to the front. Here is a pseudo-code description of the algorithm.
// input: an unsorted array A[0..n-1] containing n integer values
// output: a permutation of the original array A[0..n-1] such that
// A[0] <= A[1] <= ... <= A[n-1]
for (k = 0; k < n-1; k++) {
set loc = location of smallest value in A[k..n-1];
swap(A[k], A[loc]);
}
Because this is an exercise in programming in MIPS assembly language using procedures,
you should structure your sorting code so it implements
selection sort with the following procedures (illustrated in YFPL):
/* sort A[0..n-1] */
void sort(int A[], int n) {
int k, loc;
for (k = 0; k < n-1; k++) {
loc = minloc(A, k, n);
swap(A, k, loc);
}
}
/* return the value loc such that A[loc] is the smallest value in A[k..n-1] */
int minloc(int A[], int k, int n) {
// perform a sequential search of A[k..n-1] and return the position of the smallest value
}
/* interchange the values of A[i] and A[j] */
void swap(int A[], int i, int j) {
...
}
You should also include an additional procedure to print an array:
/* print the elements A[0], A[1], ..., A[n-1] with two spaces between */
/* each pair of numbers, followed by a newline after the last number */
void print(int A[], int n) {
...
}
Finally, you should declare two integer arrays of different lengths in the .data
section
of your code,
then write a main program that, for each array, prints its original contents,
sorts it, then prints the sorted results. The arrays don't need to be particularly
large, and you probably want to keep one of them pretty short (3 or
4 items) to make it easier to debug and trace your code. Feel free to print
extra text to label the output, etc. if you wish (within limits - a few
descriptive lines are fine, pages of ASCII art are not).
Constraints
Your code should divide the job into separate procedures as described above.
All of the procedures should follow the full standard
MIPS function call conventions, including allocating stack frames for all non-leaf
functions (and for leaf functions if needed). Procedure main should return
to the startup code when it is done by executing a jr $ra, and
not by executing an exit syscall as was done in some of the
earlier examples we've seen. You are free to use the
registers as you wish as long as you follow the standard conventions. In particular,
you may keep local variables in registers instead of storing and loading them
from main memory when this makes sense.
You should include reasonable comments in your code so a reader (including you!) can quickly figure out what you're trying to do, and can find things in the code. The comments should not paraphrase the operation of individual machine instructions. Instead, try to capture the higher-level control structures and organization that are not apparent from the detailed assembly instructions. Your comments should describe the stack frame layout and register usage in your functions. Be sure to include your name at the top of the file.
Suggestions/Hints
Simple, understandable, and working code is highly preferred over tricky and hard to follow code, even if it actually does work.
Thinking is highly recommended before coding. Spend some time designing your functions, particularly the stack frame layouts and how you plan to use the registers. Document your decisions with comments in the code. Planning and commenting will save you enormous amounts of time and get the whole job done sooner with much less pain.
Don't tackle the entire job at once. Instead, figure out something you can
do first without implementing everything else, test that out and get it working,
and then add to it to complete the project. For instance, you can test function
print before any of the sorting is implemented, and once that
works it will be useful for displaying data as you work on the rest of the
code. Once print works,
you can implement both swap and minloc independently
and test them before putting them together with everything else to finish sort.
A swap procedure was presented in lecture and is included in
the discussion of sorting in the book. Feel free to (re-)use or adapt that
code. You should mention
your source for this code in a comment if you use it. Other than that, all
of the code should be your own although, of course, you are free to model your
code
after
examples
in the book and presented in class.
Turn-in Instructions:
Use the turn-in drop box link on the main course web page to submit your assignment.
This should include a text file with the answer to the written questions,
and the sort.s file containing your solution to the sorting problem. You can
use any common file format for the written answers, including plain text,
word,
or pdf. If you wish, you could
also scan in a hand-written solution and submit
that, but if you do that, please be sure your handwriting is neat and
legible. Please be sure to include your name at the top of each of the files
you turn in.
 |
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to Hal Perkins] |