Experiment 2: MIPS Assembly Language Programming: Recursion

Review the help notes for this experiment.

Objectives

The MIPS R2000/R3000 processors were the focus in ECE 451. Therefore, students taking this laboratory course (i.e., ECE 459) have already used the SPIM simulator for the MIPS R2000/R3000 processors in ECE 451. The objective of this experiment is to develop code that uses advanced programming techniques to better understand RISC (Reduced Instruction Set Computer) designs.

What You Need

• The SPIM simulator for the MIPS R2000/R3000 processors.
• A PC (Personal Computer).

Related References

• MIPS Assembly Language Programming, by Robert L. Britton, Pearson Educations, Inc. (Prentice Hall Publ.), 2004
• http://www.mips.com
• http://www.cs.wisc.edu/~larus/spim.html
• http://spimsimulator.sourceforge.net

Introduction

A procedure that calls itself is called recursive. Recursion is a programming technique frequently used to repetitively reduce the size of a given problem until the solutions can be obtained easily for similar problems of smaller size. Under the assumption that we know how to use the latter solutions to solve the larger problem, the original problem can then be solved more efficiently. Recursion is used for binary search, element selection, etc.

The MIPS R2000/R3000 processors are representative of RISC designs. Implementing recursion in assembly language for RISC designs is a very interesting task. The element selection problem is chosen here for this purpose.

The element selection problem is defined here as follows. Given a sequence S = {s₁, s₂, s₃, ..., s_n} of integers and an integer k, where 1 ≤ k ≤ n, find the k-th smallest integer in S. The outline of a recursive algorithm that can solve the selection problem follows (adapted from: S. Akl, The Design and Analysis of Parallel Algorithms, Prentice Hall, 1989). The parameter Q in procedure SELECT is a small integer constant.

procedure SELECT(S,k)

1. if | S | < Q  then sort S and return the k-th element
   else subdivide S into | S | / Q subsequences of Q elements each
   end if.
2. Sort each subsequence and determine its median.
3. Call SELECT recursively to find m, the median of the | S | / Q  medians found in 2.
4. Create three subsequences S₁, S₂, and S₃ to contain elements of S smaller than, equal to, and larger than m, respectively.
   1. if  | S₁| ≥ k then call SELECT recursively to find the k-th element of S₁
      else if  | S₁| + | S₂| ≥ k   then return m
      else call SELECT recursively to find the (k - | S₁| - | S₂|)-th element of S₃
      end if
      end if.

The running time of SELECT is O(n) for any value of Q ≥ 5 (under this condition, recursive calls are carried out for sequences ever-decreasing in size).

Notice the similarities between SELECT and the popular QUICKSORT algorithm. The latter algorithm is for sorting, and has worst case and expected running times O(n²) and O(n lgn), respectively.

Experiment

Provide a flowchart of your algorithm to solve the selection problem based on the given recursive procedure. Develop MIPS assembly language code for its implementation. Assume that Q = 5 and use pointer-based data structures to avoid relocation of elements from S in the memory. You may use any technique to sort  S, for | S | < Q.

Use the SPIM simulator to execute the code. Show intermediate and final results.