Oakton Community College Assembly Programming Worksheet

Project A: Quicksort in MIPS AssemblyECE 366 Computer Organization
Spring 2023
Submission Due: Friday, Feb. 24
1. Overview
The purpose of this project is to exercise MIPS assembly programming in the implementation of
a fairly complex algorithm. You will need to use the knowledge about MIPS function call
convention, MIPS branching, array access, and arithmetic and logic operations.
2. Get Started
Create a folder with name “bubblesort”. Download the three MIPS assembly program files,
namely “sort_main.asm”, “bubblesort.asm”, and “bublesort_swap.asm”, from the attachment of
the assignment.
Run the MARS MIPS simulator and click on the “Settings” menu. Check “Assemble all files in
directory” and uncheck “Permit extended (pseudo) instructions and formats” (see picture below).
Open “sort_main.asm” and then assemble the program. Set two checkpoints as shown in the
following screenshot. Run the program to the first checkpoint. Click on “Tools” menu, select
“Instruction Counter”, and then click on “Connect to MIPS”.
Continue to run the program and let it stop at the second checkpoint. Note down the number for
“Instructions so far”. That is the number of instructions for running the bubblesort function
(including the jal instruction). You should see the same number as shown in the screenshot.
Then, click on “Disconnect from MIPS”.
Continue to run the program until it stops. Verify that you see the same testing output as shown in
the screenshot in “Mars Messages”.
3. Study Quicksort
Quicksort is a very efficient sorting algorithm. If you haven’t yet learned about Quicksort or
wants to refresh your knowledge about it, read this Wikipedia page:
https://en.wikipedia.org/wiki/Quicksort.
Study the pseudocode of the Lomuto partition scheme given in the above Wikipedia page.
Make sure you understand how it works. Then, rewrite the two functions given in the
pseudocode, namely quicksort and partition, in C code. Note that they are called
“algorithm” in the pseudocode. If you have any question, please ask the TA or professor.
4. QuickSort in MIPS Assembly
Create another folder named “quicksort”. Copy “sort_main.asm” to this folder. Create two
assembly files named “quicksort.asm” and “partition.asm”. The first file should contain the
assembly code for the quicksort function, and the second file should contain the assembly code
for the partition function. You may use “bubblesort.asm” and “bubblesort_swap.asm” as
templates. Make sure your assembly codes are well formatted and well commented.
Assemble and run the program. Verify that the program output is correct. Then, set the two
breakpoints and use the Instruction Counter tool to count the number of instructions for running
the quicksort function, as you did in step 2. Compare it to that of the bubblesort function
with the same input.
Then, test your quicksort function using another input array of 10 elements. You may create
the input array, but make it is a representative case, e.g., with different numbers and containing
both positive and negative numbers. Again, count the number of instructions for running the
quicksort function, and compare it to that of the bubblesort function with the same input.
5. Project Report and Submit.
Write a project report with the following sections:
1. Your understanding about how QuickSort works. Use your own language.
2. The C code you wrote in Step 3.
3. The testing output with the original input array in “sort_main.asm”. Attach a screenshot
similar to the screenshot given in Step 2, showing both the testing output and the
instruction code. Calculate the ratio of the two instruction counts from quicksort and
bubblesort, respectively.
4. Repeat 3) but this time using your own input array.
5. Describe the responsibility of each person in your group and estimate the breakdown of
contribution in percentage (e.g., 50% and 50% for a two-person group, or 33.3%, 33.3%
and 33.3% for a three-person group). Also estimate your total working hours.
Note: If a partner contributes 40% or higher in a two-person group or 25% or higher in a threeperson group, the partner may receive the same grade as the group gets.
Submit the following items under this assignment. Your assembly code will be tested for
correctness.
1) The lab report (in PDF format)
2) quicksort.asm
3) partition.asm.
#
# Bubble sort version of the sort function
# Prototype: void sort(int X[], int N)
# X[] is the array to sort, N is the size of the array
#
# The original code is from the reference book:
# Computer Organization and Design: The Hardware/Software Interface, 5th
# Edition or later, by D. A Patterson and J. L. Hennessy
#
# The code has been reformatted and revised slightly.
#
.globl sort
sort:
# Function prologue
addi $sp, $sp, -20 # create stack frame of 5 words
sw $ra, 16($sp) # save $ra on stack
sw $s3,12($sp) # save $s3 on stack
sw $s2, 8($sp) # save $s2 on stack
sw $s1, 4($sp) # save $s1 on stack
sw $s0, 0($sp) # save $s0 on stack
add $s2, $zero, $a0 # save $a0 into $s2
add $s3, $zero, $a1 # save $a1 into $s3
addi $s0, $zero, 0 # i = 0
for1tst:
slt $t0, $s0, $s3 # $t0 = 0 if $s0 ? $s3 (i ? n)
beq $t0, $zero, exit1 # go to exit1 if $s0 ? $s3 (i ? n)
addi $s1, $s0, -1 # j = i ??1
for2tst:
slti $t0, $s1, 0 # $t0 = 1 if $s1 < 0 (j < 0) bne $t0, $zero, exit2 # go to exit2 if $s1 < 0 (j < 0) sll $t1, $s1, 2 # $t1 = j * 4 add $t2, $s2, $t1 # $t2 = v + (j * 4) lw $t3, 0($t2) # $t3 = v[j] lw $t4, 4($t2) # $t4 = v[j + 1] slt $t0, $t4, $t3 # $t0 = 0 if $t4 ? $t3 beq $t0, $zero, exit2 # go to exit2 if $t4 ? $t3 addi $a0, $s2, 0 # 1st param of swap is v (old $a0) addi $a1, $s1, 0 # 2nd param of swap is j jal swap # call swap procedure addi $s1, $s1, -1 # j -= 1 j for2tst # jump to test of inner loop exit2: addi $s0, $s0, 1 # i += 1 j for1tst # jump to test of outer loop # Function epilogue exit1: lw $s0, 0($sp) # restore $s0 from stack lw $s1, 4($sp) # restore $s1 from stack lw $s2, 8($sp) # restore $s2 from stack lw $s3, 12($sp) # restore $s3 from stack lw $ra, 16($sp) # restore $ra from stack addi $sp, $sp, 20 # restore stack pointer jr $ra # return to calling routine # # The swap function # Prototype: void swap(X[], k) # # It swaps X[k] and X[k+1] # # The original code is from the reference book: # Computer Organization and Design: The Hardware/Software Interface, 5th # Edition or later, by D. A Patterson and J. L. Hennessy # # The code has been reformatted. # .globl swap swap: sll $t1, $a1, 2 # $t1 = k * 4 add $t1, $a0, $t1 # $t1 = v+(k*4) # (address of v[k]) lw $t0, 0($t1) # $t0 (temp) = v[k] lw $t2, 4($t1) # $t2 = v[k+1] sw $t2, 0($t1) # v[k] = $t2 (v[k+1]) sw $t0, 4($t1) # v[k+1] = $t0 (temp) jr $ra # return to calling routine