Programming Assignment #0: Writing Bubble Sort in RISC-V (RV32I) Assembly

Due: March 31, 11:59PM

TA: Junwoo Park (jwpark@csl.korea.ac.kr)

---

1. Overview

In this assignment, you will implement the bubble sort algorithm in RISC-V (RV32I) assembly language. Pre-built tools are provided in the repository root so you can assemble and run your program without building them yourself:

Tool	Binary	Description
Assembler	./ku-rv32i-as	Translates .s -> .o
Simulator	./ku-rv32i-sim	Executes .o and prints register/memory state

The assembler translates your .s file into a binary .o file. The simulator executes the binary and shows the final register and memory state.

---

2. Background: Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are out of order. After each pass through the array, the largest unsorted element "bubbles" to its final position.

for i = 0 to n-2:
    for j = 0 to n-2-i:
        if array[j] > array[j+1]:
            swap(array[j], array[j+1])

Your program must sort the array in ascending order.

---

3. Supported Instruction Set

You may use any of the following instructions. No other instructions are available in the provided assembler.

Format	Instructions
R-type	add, sub, and, or
I-type	addi, andi, xori, ori, sltiu, slli, srli, lw, jalr
S-type	sw
B-type	beq, bne, blt, bge
J-type	jal
U-type	lui, auipc
Pseudo	la (expands to auipc + addi)

Note: blt and bge perform signed comparisons. Use sltu / sltiu if you need unsigned comparison.

---

4. Assembly File Constraints

The assembler imposes the following formatting rules.

• Fields are separated by tabs (not spaces).
• Register names are written as x0 through x31.
• Immediate values may be decimal (e.g., 4) or hexadecimal (e.g., 0x4).
• Labels in the .text section must appear on their own line followed by a colon: label:.
• Labels in the .data section must appear on the same line as their .word declaration: array:\t.word\t9.
• The .data section must come before the .text section.

Instruction syntax reference

# R-type
add   xRD, xRS1, xRS2

# I-type (arithmetic)
addi  xRD, xRS1, imm

# I-type (load)
lw    xRD, offset(xRS1)

# S-type (store)
sw    xRS2, offset(xRS1)

# B-type (branch)
blt   xRS1, xRS2, label    # branch if RS1 < RS2  (signed)
bge   xRS1, xRS2, label    # branch if RS1 >= RS2 (signed)
beq   xRS1, xRS2, label
bne   xRS1, xRS2, label

# J-type
jal   xRD, label           # jump and link
jalr  xRD, offset(xRS1)    # jump and link register

# Pseudo
la    xRD, label           # load address (data section label)

---

5. Requirements

Part A - Sort the array (60 pts)

Implement bubble sort so that after done: is reached, array in memory is sorted in ascending order.

Part B - Count swaps (30 pts)

In addition to sorting, your program must count the total number of swaps performed and store that count in register x20 when the program finishes.

• Initialize x20 = 0 before the loops begin.
• Increment x20 by 1 every time you swap two adjacent elements.
• The simulator output shows the final register state; the grader will read x20 directly.

Example: for the input [9, 2, 7, 4, 6], the expected swap count is 6 (stored in x20).

Part C - Comments (10 pts)

Document every register you use with a short comment explaining its role. Write these comments inside the existing comment block in main: in bubble_sort.s (between the two # ------------------------------------------------------- lines), replacing the TODO text.

Example:

main:
	# -------------------------------------------------------
	# ...
	# x5  : base address of array
	# x6  : array length
	# ...
	# x20 : total number of swaps
	# ...
	# -------------------------------------------------------

---

6. Skeleton Code

The file bubble_sort.s is provided as a starting point. The .data section is fixed - do not modify it. Implement the sorting algorithm inside the .text section.

# Name:
# Student ID:
# Description: Bubble sort implementation in RV32I assembly
	.data
array:	.word	9
	.word	2
	.word	7
	.word	4
	.word	6
n:	.word	5
	.text
main:
	# -------------------------------------------------------
	# TODO: implement bubble sort
	#
	# Sort 'array' of 'n' integers in ascending order.
	# You may use registers x1-x31 freely.
	# Document each register's role with a comment.
	# -------------------------------------------------------

done:
	jalr	x0, 0(x1)	# return (do not remove)

The jalr x0, 0(x1) at the end tells the simulator when your program has finished. Do not remove or move it.

---

7. Step-by-Step Testing

Step 1 - Check that the tools are executable (one time)

ls
# README.md  ku-rv32i-as  bubble_sort.s  ku-rv32i-sim

If you get a "Permission denied" error, make the binaries executable:

chmod +x ku-rv32i-as ku-rv32i-sim

Step 2 - Write your assembly code

Edit bubble_sort.s and implement the sorting algorithm.

Step 3 - Assemble

./ku-rv32i-as bubble_sort.s

If successful, bubble_sort.o is created. Fix any error messages before proceeding.

Step 4 - Simulate

./ku-rv32i-sim -n 500 bubble_sort.o

The -n 500 flag sets the maximum number of instructions to simulate. Increase this value if your program needs more instructions to finish.

Step 5 - Verify the result

Inspect the Memory and Registers sections of the simulator output.

Memory (data section starts at 0x10000000):

For the provided input [9, 2, 7, 4, 6], the expected memory content after sorting is:

[INFO] Memory content [0x10000000..0x1000001f] :
-------------------------------------
0x10000000: 0x00000002    <- array[0]
0x10000004: 0x00000004    <- array[1]
0x10000008: 0x00000006    <- array[2]
0x1000000c: 0x00000007    <- array[3]
0x10000010: 0x00000009    <- array[4]
0x10000014: 0x00000005    <- n (unchanged)

Register x20 (swap count): for [9, 2, 7, 4, 6], the expected value is 0x00000006 (6 swaps total).

Use the -d flag to print the state after every step, which is helpful for debugging:

./ku-rv32i-sim -d -n 500 bubble_sort.o

---

8. Hints

1. Load the array base address with la xRD, array before accessing elements.
2. Compute byte offset: element j is at byte offset j x 4. Use slli to multiply by 4: slli xOFF, xJ, 2.
3. Access array[j]: lw xVAL, 0(xADDR) where xADDR = base + offset.
4. Access array[j+1]: lw xVAL, 4(xADDR) by using the next word.
5. Swap by storing values in reverse: write array[j+1] to 0(xADDR) and array[j] to 4(xADDR).
6. Swap counter: initialize x20 to 0 with addi x20, x0, 0 before the loops, then add addi x20, x20, 1 immediately after a swap.
7. Start with the outer loop and make sure it terminates correctly before adding the inner loop body.

---

9. Grading

Item	Points
Program assembles without error	10
Part A: Correctly sorts the provided array [9, 2, 7, 4, 6]	30
Part A: Correctly sorts additional hidden test arrays	20
Part B: Correct swap count in x20 for provided array	20
Part B: Correct swap count in x20 for hidden test arrays	10
Part C: Comments explaining register usage and logic	10
Total	100

Hidden test arrays will use the same .data section format (same label names array and n) but with different values and sizes (up to 10 elements). Your code must handle any valid input in this format.

---

10. Submission

Submit only bubble_sort.s to the course submission system. Do not submit .o files or executables.

• Filename must be exactly bubble_sort.s
• Include your name and student ID as a comment at the top of the file

# Name:       Hong Gildong
# Student ID: 2026xxxxxx
# Description: Bubble sort implementation in RV32I assembly