Go to  COE498   Experiment   |    |    2  |    3    |      |     Part List    |   Lab manuals   |   ECE Lab home

COE498 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., CoE 498) 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

 

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  =  {s1, s2, s3, ..., sn} 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 S1, S2, and S3 to contain elements of S smaller than, equal to, and larger than m, respectively.
     

  5. if  | S1  k   then call SELECT recursively to find the k-th element of S1
    else  if  | S1|  +  | S2
     k   then return m

else call SELECT recursively to find the  (k  -  | S1|  -  | S2|)-th  element of  S3

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(n2)  and  O(n2 lgn), respectively.

 

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

  Go to  COE498   Experiment   |    |    2  |    3    |      |     Part List    |   Lab manuals   |   ECE Lab home