Who Wears Short Sorts?
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.
1) Hardware Setup
If you haven't already, you should remove the LEDs and the wire connecting the ESP32 to BTNC.
Keep the LED display connected; we will be using that for the postlab.
2) Software Setup
You can find the starter code for today's lab here: [Starter Code]. In project's src folder you'll find:
main.c: your main C file. This file will still be our "entry point". Today, you should NOT modify this file, it merely serves as a "wrapper" for our assembly code.bubblesort.S: assembly (.S) file where you will implement your bubblesort.collatz.S: assembly (.S) file where an assembly program has been implemented for you.
Make sure to copy over both gpio_asm.S and 6190.h from lab4 into postlab4's src directory. Make sure that you're copying the 6190.h that you were using in Lab 4, and do not modify anything in either of these files for this postlab.
3) Collatz
We'll first explore how an assembly program is actually understood by our RV32I (RISC-V, 32-bit) processor.
Let's take this Python code:
def collatz(n):
# check if n is even
if n % 2 == 0:
n = n / 2
else:
n = 3*n + 1
return n
The corresponding assembly code is as follows:
collatz:
If:
andi a1, a0, 1
bne a1, zero, Else
Then:
srai a0, a0, 1
jal zero, End
Else:
slli a2, a0, 1
add a0, a2, a0
addi a0, a0, 1
End:
jalr zero, 0(ra)
However, our processor doesn't actually read, for example, "andi a1, a0, 1" from memory -- it reads a 32-bit value that means andi a1, a0, 1, and then decodes it. Let's investigate.
We've generated a file (named collatz.dump) that contains information about the program such as where instructions are stored in memory and how they're encoded. Open it (linked here) and scroll (or search for "<collatz>"). You should come across something that looks like this:
Disassembly of section .text:
00000000 <collatz>:
0: 00157593 andi a1,a0,1
4: 00059663 bne a1,zero,10 <Else>
This is the beginning of the "disassembly" of your program. Here we can see things like the memory address of each instruction and the 32-bit encoding of each instruction. You'll notice a few things here in this dump file. Continuing with our andi a1, a0, 1 example:
0: 00157593 andi a1,a0,1
0:The (hexadecimal) value before the colon (in this case,0:) indicates the address in memory where the instruction is stored. So ourandi a0, a0, 1instruction is stored in memory location 0.00157593The (hexadecimal) value after the colon is the 32-bit binary encoding of the instruction. This is the information that the processor understands!andi a1, a0, 1The instruction that'll be executed.
Please use the collatz.dump file (linked here) to answer the following questions.
slli a2, a0, 0x1? Please specify all 32 bits and include the '0x' prefix.
4) Bubblesort
For the rest of this week's postlab, you're going to sort an array using the bubblesort algorithm. First, you're going to get the algorithm working in RISC-V assembly, then you'll integrate it with your labkit to better visualize how the algorithm works (and to prove to yourself that it's running on your embedded system).
Here is a C implementation of bubblesort:
void bubblesort(int *p, int n) {
int swapped = 1;
while (swapped != 0) {
swapped = 0;
for (int i = 0; i < n - 1; i++) {
if (p[i] > p[i + 1]) {
int tmp = p[i];
p[i] = p[i + 1];
p[i + 1] = tmp;
swapped = 1;
}
}
n = n - 1;
}
}
It takes two arguments:
int *p: array to be sortedint n: length of the array to be sorted
When your bubblesort assembly procedure is called:
pwill be in registera0, andnwill be in registera1.
Please complete bubblesort below, using the C code above for reference. Make sure to comment your code well, as it is easy for assembly language to become hard to follow.
Please make sure that your implementation passes the test cases in the checker below before proceeding. You may only use registers a0 through a7. Additionally, your implementation must not modify a0.
Once you're passing the test cases above, paste your implementation into bubblesort.S.
4.1) Visualization
So now your bubblesort works, but we want to run it on our RISC-V microprocessor to get our money's worth. Additionally, we would like to have some visual indicator that our bubblesort is running.
Paste this block of code into your bubblesort program so that, every time a swap is made, the LED array is updated. Hint: where does your swap occur in your assembly program?
addi sp, sp, -36
sw a0, 0(sp)
sw a1, 4(sp)
sw a2, 8(sp)
sw a3, 12(sp)
sw a4, 16(sp)
sw a5, 20(sp)
sw a6, 24(sp)
sw a7, 28(sp)
sw ra, 32(sp)
jal ra, arrayViz
lw a0, 0(sp)
lw a1, 4(sp)
lw a2, 8(sp)
lw a3, 12(sp)
lw a4, 16(sp)
lw a5, 20(sp)
lw a6, 24(sp)
lw a7, 28(sp)
lw ra, 32(sp)
addi sp, sp, 36
If you've pasted it in the correct place, your system should do something like this:
5) Code Submission
Make sure to submit your bubblesort.S file in a zip file named None_postlab4.zip.
To create the zip file, you can select the folders/files you want, right click, and look for the option to compress these files.
Alternatively, you can run one of the following commands in the terminal:
If you're on MacOS or Linux or Command Prompt:
zip None_postlab4.zip src/bubblesort.S
or for Windows Powershell users,
Compress-Archive -Path src/bubblesort.S -DestinationPath None_postlab4.zip
bubblesort.S file here as a zip file. Name the file None_postlab4.zip for this assignment.
6) Checkoff
Show your bubblesort running on your microcontroller!