Computer Science 220
Assembly Language & Computer Architecture

Fall 2011, Siena College

Home     Syllabus     Schedule

For this lab, you will gain more experience with MIPS programming by implementing an insertion sort for an array of integers. You may work alone or with a partner on this lab.

In Lab: Factorial Program

First, we look at a complete version of the factorial program you saw in class.

See Example:
~jteresco/shared/cs220/examples/spim-factorial/factorial.s

• The factorial subroutine is identical to what we looked at in class.
• We fill in the missing multiply routine with the one you did for the lecture assignment, changed to use $a0 and $a1 as the parameters and to put the answer into $v0.
• The main subroutine will use two "s" registers and will call subroutines, so we begin by pushing $s0, $s1, and $ra onto the stack. Note that SPIM initialized $sp for us appropriately.
• We print a prompt string with the print_string syscall and then read in an int from the keyboard with the read_int syscall. Note: a complete list of syscall codes is in Figure B.9.1.
• After the call to factorial, we use a series of syscalls to print the answer.
• Finally, we pop the stack and return from main.

Second, if you are not familiar with/do not recall the details of insertion sort, look it up and remember/learn them.

Programming Tasks

Your main tasks are to develop two working MIPS implementations of insertion sort subroutines. These should be based on the C functions found in the file

~jteresco/shared/cs220/labs/spim-sort/isort.c

Begin by making sure you understand both versions. Draw some examples. You should have a lot of boxes and arrows. If you don't follow what the C code is doing, it will be very challenging to write the corresponding MIPS code.

You should write the implementations of insertion sort in subroutines named isort and isortptr. Each should take two parameters: the address of the start of the array, and the number of integers in the array, passed using the standard MIPS conventions for subroutine calls and register usage. You may base your code on the functions in isort.c.

Think carefully about how to approach the compound conditional in the while loop. You may find it helpful to rewrite it first as a series of if statements with gotos.

Set up an array in memory and initialize it with a collection of random values (randomly chosen by you at programming time, not by SPIM at run time). Use the same technique for allocation and initialization that we used for the previous lab.

Your main routine should call a subroutine to print out the initial array (which you will also need to write), call isort, then print the array again through another subroutine call. Label your output appropriately. Changing just the call of the sort routine from isort to isortptr, you should be able to switch to the pointer-based subroutine.

In summary, your submission should include four complete MIPS subroutines: main, isort, isortptr, and the one to print the contents of the array. main calls the print function, then isort, then the print function again.

Submission and Evaluation

This lab is graded out of 30 points.

By the start of your next lab meeting, submit a single file called isort.s that includes your documented MIPS assembly source code for your program. Submit by email to jteresco AT siena.edu.

Note: During grading, I will replace your array's contents with my own, so be sure your programs work with a variety of array sizes and contents. Pay close attention again to appropriate documentation practices. It is always good to document as you go when doing any kind of programming, but it especially crucial for assembly language programming. And don't forget to include your name!