Homework 3 - Computer Architecture I - ShanghaiTech University

Homework 3

Computer Architecture I ShanghaiTech University
HW2 HW3 HW4

Introduction

In this homework, you will implement a binary min heap with insert and pop operations in RISC-V assembly. Here is a very simple template to begin with.

Input

A reference input is already provided to you in the input.S file. Input is provided to you in binary format to alleviate the burden of parsing and dealing with Venus’s expermintal file system. There are basically 3 operations that you need to support, insert, pop, and print_heap, described in the comment below. Since this is a computer architecture course, we will not go into the details of how a binary heap works. Refer to your Data Structure course if in doubt.

.data

# Input array
# Non-negative integers are insert operations.
# -1 is the pop operation.
# You should print the popped (smallest) item, while maintaining the heap property.
# -2 is the print heap operation.
# You should the print the internal representation (array) of the heap.
# DO NOT MODIFY THIS VARIABLE
.globl  input
input:
    .word   0 1 2 3 -1 -2

# Constant integer specifying the number of operations
# DO NOT MODIFY THIS VARIABLE
.globl  input_len
input_len:
        .word   6

# Statically allocated array for the heap data structure
# You may assume that the maximum capacity is 32.
# Any operation that causes the array to hold more than 32 elements is an overflow.
.globl  heap
heap:
    .word   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

# Global variable that holds the current length of the heap
# You should modify this variable accordingly when inserting or popping elements.
.globl  len
len:
    .word   0

You may assume that the input array provided to you contains only unique non-negative integer, or multiple -1 or -2. Input like 1 1 or -3 -4 is invalid and will not appear in the testcase.

Output

It’s usually the duty of the supervisor (operating system) to deal with input/output and halting program execution. Venus, being a simple emulator, does not offer us such luxury, but supports a list of primitive environment calls. A snippet of assembly of how to exit with error code 0 is already provided to you in heap.S.

In addition handling the forementioned 3 operations correctly, you should also take care of errors. Should a buffer underflow or overflow occur, you must halt execution immediately and exit with error code -1.

In the above case, no error occurs so the output would be

0
1 3 2

Exited with error code 0

The command that we use to test your program’s correctness is

diff <your_output> <reference_output>

You can also test your result using this command. Be sure to calculate your reference_output correctly!

Running

Make sure that heap.S and input.S reside in the same directory. To run your program locally

java -jar venus-jvm-latest.jar heap.S

To debug your program online, you might want to replace .import input.S in heap.S with the content of input.S.

Tips

To interact with the input file, you can use the global labels defined in input.S. For example, you can get the input_len with the following code:
```
la    a7, input_len
```
Handwritten assembly are postfixed with extension .S to distinguish from compiler generated assembly .s
While being a strong proponent for python’s cult of space, I suggest you indent using tabs. Set your editor’s tabwidth to 8 for best visual experience.
Learn recursive functions
Learn save and load from memory using RISC-V
It is helpful writing in C first
Write comments
The test cases are very friendly! Don’t focus too much on the edge cases, focus on the correctness on the common cases.

Execution

We will test your program using RISC-V emulator venus. You probably want to read this before you started.

Submission

You need to follow the RISC-V integer register convention and the RISC-V integer calling convention.
You need to have meaningful comments not less than 50% of the total lines of code you wrote. A comment is defined by a sentence followed by #.
You should submit exactly one file, heap.S. Any other file found will result in a score of zero.

Last Modified: Fri Mar 19 14:25:32 CST 2021