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

Execution

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

Submission


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