Go to  ECE459   Experiment   |   1   |    2  |    3    |    4    |   Lab manuals   |    ECE Lab home

ECE459 Advanced Computer System Design Lab

Chapter 1

EXPERIMENT 1

MIPS Assembly Language Programming: Recursion

1.1   Objective

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

 

1.2   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

1.3   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.
    

5. 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.

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.

Go to  ECE459   Experiment   |   1   |    2  |    3    |    4    |   Lab manuals   |   ECE Lab home