CSE logo University of Washington Computer Science & Engineering
 CSE 410 Computer Systems - Homework 3 - Spring 2010
  CSE Home   About Us    Search    Contact Info 

Due: Thursday, April 22, at 11 pm.

The main purpose of this assignment is to gain additional experience with assembly language programming, particularly with procedure/function calls and stack frames. There are also a few questions about translating between assembly language and binary machine code.

Part I. Written questions

  1. For each of the following MIPS assembly instructions, (i) show the binary encoding of the instruction word, and (ii) write the binary instruction word in hexadecimal. For the binary encodings, use spaces or draw boxes to clearly show the different fields of the instructions and label those fields (op, rs, rt, etc.).

    1. addi $s1, $t3, 5
    2. addu $v0, $zero, $a3
    3. or $t0, $t9, $s2
    4. sw $s4, 80($fp)

  2. For each of the following 32-bit hex numbers in parts (a) through (c),

    1. Write the instruction word in binary. Leave enough spaces between the binary digits for part (iii) of the question.
    2. What is the format of the instruction? (I, R, J)
    3. Draw boxes around the bits in part (i) that make up the fields of the instruction and label those fields (op, rs, rt, etc.).
    4. Translate the instruction to assembly language. Use symbolic register names like $t0 instead of $8.

    1. 0xAE0B0004
    2. 0x8D08FFC0
    3. 0x00000000
    4. The instruction in part (c) (0x00000000) is sometimes referred to as a no-op instruction since it can be inserted in an assembly language program and executed without apparently doing anything. Why doesn't it seem to have any effect?

Part II. Programming

The purpose of these two programming problems is to practice MIPS assembly language programming. You should create programs to solve the following two problems and run them using SPIM. Your code should conform to the following ground rules:

  1. Your code should use the standard MIPS function call and register conventions, including allocating stack frames as needed for local variables and to save/restore registers. In particular, your code must not make any assumptions about how called procedures use the registers, beyond the guarantees provided by the standard conventions. This is true even though you are writing all of the code. Write your code as if any procedure you call might change every register that it is entitled to alter without saving and restoring.
  2. Simple, understandable, and obviously correct code is highly preferred over tricky and hard to follow code, even if it actually does "work". You should include reasonable comments so the reader can see the structure of the code and follow its logic. Brief comments that describe register usage are particularly helpful. Be sure to include identifying information at the top of each file you turn in with your name, the assignment and problem number, and the date.

Feel free to do things like adding additional functions to your test programs to reduce the amount of almost-identical code, etc.

Sorting Things Out

Write a MIPS procedure sort and a main program to test it on at least 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 that procedure to print each array both before and after sorting. Your program should be stored in a file named sort.s.

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, where n>0.
// 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]);
}

You should implement this algorithm using the following three procedures. Any reasonable translation of these procedures to assembly language is fine provided that you implement the given algorithms and don't make any changes to procedure specifications or parameter lists. Remember to observe the standard calling and register usage conventions.

/* 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 or more integer arrays of different lengths in the .data section of your code, and 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. (within limits - a few descriptive lines are fine, pages of ASCII art are not).

Suggestions/Hints

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.

To Understand Recursion, You Must Understand Recursion

You probably remember the Fibonocci numbers. This is a sequence defined on positive integers as follows:

Write a MIPS function fib(n) that computes the nth Fibonocci number recursively using the above definition directly. In other words, include appropriate if statements and recursive calls to calculate the answer; don't rewrite the algorithm to use a loop or closed formula to calculate the answer.

Test your function by calling it several times from a main program with different arguments. Be sure to verify that the base cases and general case work properly. For each test, print the argument value and the function result. Include the code for your function and your test program in a file named fib.s.

Hint: Don't try this for particularly large arguments, at least while you're testing. The direct recursive implementation takes exponential time in the value of n, and SPIM is not particularly fast anyway. It might be fun, however, to time your code for some larger arguments and post your times as well as information about your computer on the class discussion list so we can compare results.

Turnin 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 and fib.s files containing your solutions to the programming problems. 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.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Hal Perkins]