EEET2394 Laboratory 2 – VR Sensor Signal Processing
To get started, download the project template from the subject Canvas website. The project template (provided as a single .zip archive) contains code stubs together with example test routines for each of the assembly programming tasks described below. You will complete these code stubs and must then archive (.zip) and submit your project directory for assessment.
3 Loops and conditionals (Linear search)
The project template contains two files: min.asm and max.asm. Each file contains a code stub defining a procedure to compute the minimum and maximum, respectively, of an array of signed 32- bit integers of arbitrary length. Your task is to complete each of these code stubs to return the minimum and maximum value using a linear search of the supplied array. Your implementation of each of these procedures must satisfy the following constraints:
1. The array of integers is stored in memory in a contiguous range of addresses. When each procedure (min or max) is called, the starting address of the array will be stored in a0 and the number of integers in the array will be stored in a1.
2. Each procedure should return the index of its target (i.e., the minimum or maximum value) in a0.
3. Each procedure should end with a ret pseudo-instruction.
Note: The returned value should be the element index, not an addresses or byte offset.
Do not rename the files (min.asm and max.asm) or change the name of the procedures (min and max) defined in the supplied code stubs.
To test your solution in RARS, you may use the example test routines tstmin.asm and tstmax.asm, provided in the tests directory.
Discussion questions: Evaluate the computational cost of your solution, in terms of the number of instructions executed. How does this vary with the length of the supplied array?
Hint: You can use RARS to confirm your estimate of the number of instructions executed using the Instruction Counter, located under the Tools menu or by using the ic command line argument.
4 Procedure calls (Quicksort)
The cost of many operations that involve linear search can be significantly reduced by first sorting the array to be searched. Consider the case of finding the minimum and maximum: for a sorted array no search is required (the minimum and maximum are simply the first and last elements in the array). Searching for an arbitrary value in an array is another example which can benefit significantly from sorting of the array before searching, especially if many searches for different values, are required.
The project template contains an additional file: quicksort.asm. This file contains a code stub defining a procedure to sort an array of signed 32-bit integers of arbitrary length into ascending order. Your task is to complete this code stub to sort the supplied array using the Quicksort algorithm [4].
Your implementation of the sort procedure must satisfy the following constraints:
1. The array of integers is stored in memory in a contiguous range of addresses. When the sort procedure is called, the starting address of the array will be stored in a0 and the element indices of the start and end of the region to be sorted will be stored in a1 and a2, respectively.
2. The sort procedure should modify the array in place, and does not need to return any value.
3. The sort procedure should end with a ret pseudo-instruction.
Page 2 of 6
EEET2394 Laboratory 2 – VR Sensor Signal Processing
algorithm sort(A, lo, hi) is if lo < hi then
p := partition(A, lo, hi) sort(A, lo, p - 1) sort(A, p + 1, hi)
algorithm partition(A, lo, hi) is pivot := A[hi]
i := lo
for j := lo to hi do
if A[j] < pivot then swap A[i] with A[j] i := i + 1
swap A[i] with A[hi] return i
Fig. 1. The Quicksort algorithm [4].
Hint: your implementation of the sort procedure should be recursive (see Fig. 1) and make use of
the partition procedure defined in the code stub.
Do not rename the file (sort.asm) or change the name of the procedure (sort) defined in the
supplied code stub.
To test your solution in RARS, you may use the example test routine tstsort.asm provided in
the tests directory.
Discussion questions: Evaluate the computational cost or your solution, in terms of the number of instructions executed. How does this vary with the length of the supplied array? Can you reduce this cost?
5 Constraints of the RV32I ISA (Binary search)
The file search.asm in the project template contains a code stub defining a procedure to search a sorted array of unsigned 32-bit integers. Your task is to complete this code stub to search the supplied array using a binary search algorithm [5]. Your implementation of the search procedure must satisfy the following constraints:
1. The array of integers is stored in memory in a contiguous range of addresses. When the search procedure is called, the starting address of the array will be stored in a0 and the number of integers in the array (constrained to be a power of 2) will be stored in a1. The target of the search will be stored in a2.
2. If the target is found in the array, the search procedure should return the index of the target in a0. If the target is not found in the array, a0 should be set to a value of -1.
3. The search procedure should end with a ret pseudo-instruction.
The binary search algorithm (Fig. 5) is also known as the half-interval search algorithm. It first compares the target with the middle element of the array. Based on this comparison half of the sorted array is eliminated, and the search proceeds on the remaining half, again comparing the target with the middle value (of the remaining half). Binary search is therefore based on division, by 2 – to halve the search interval after each step. In the RV32I ISA, this division must be achieved by use of a right- shift instruction (e.g., srai). To facilitate this division, and to simplify implementation of the binary search algorithm, here the length of the array is assumed (or rather constrained) to be a power of 2.
Page 3 of 6
EEET2394 Laboratory 2 – VR Sensor Signal Processing
function binary_search(A, n, T) is L := 0
R := n − 1 while L ≤ R do
m := L + ((R - L) 2) if A[m] < T then
L := m + else if A[m] R := m −
else:
return m
1
> T then 1
return unsuccessful
Fig. 2. The binary search algorithm [4].
Do not rename the file (search.asm) or change the name of the procedure (search) defined in
the supplied code stub.
To test your solution in RARS, you may use the example test routine tstsearch.asm provided in
the tests directory.
Discussion questions: As noted above, here the length of the array to be search is constrained to be
a power of 2. How could this constraint be relaxed?
6 Challenge task
In the search procedure implemented above, the length of the array to be searched was constrained to be a power of 2. In this Challenge Task, your task is to modify your implementation of the search procedure to accept (and search) arrays of arbitrary length.
7 Assessment process
Once you have completed (and tested) the code stubs described above (min.asm, max.asm, sort.asm and search.asm) archive the entire project directory into a single .zip archive and submit this archive via the subject Canvas website. Failure to submit your code archive will incur a 30% penalty.
Your completed code stubs will be assembled and linked with a set of test routines designed to test their functionality using the RISC-V Assembler and Runtime Simulator (RARS) version 1.5 [3]. These test routines are similar but not identical to those provided in the project template. The test routines provided in the project template are intended to serve as examples for testing your code. They provide only minimal testing of your code. You are encouraged to consider different scenarios and challenging edge cases, and to create any additional testing or debugging routines to test those cases.
Once you have completed the assessable tasks please prepare a short demonstration so the Laboratory Demonstrator can evaluate your solution. You should be able to step through any of your code in RARS, and to predict how the register or memory contents will change before executing each instruction.
You should arrange to demonstrate your code before the end of your laboratory session in Week 3.
Page 4 of 6
EEET2394 Laboratory 2 – VR Sensor Signal Processing
8 References
[1] The RISC-V Instruction Set Manual: Volume I: Unprivileged ISA, https://github.com/riscv/riscv-isa-manual/releases/tag/draft-20200717-259025b, [online], Accessed 2020-07-18.
[2] Open RISC-V Reference Gard, http://riscbook.com/greencard-20181213.pdf, [online], Accessed 2020-07-18.
[3] The RISC-V Assembler and Runtime Simulator (RARS), https://github.com/TheThirdOne/rars/releases/tag/v1.5, [online], Accessed 2020-07-18.
[4] Quicksort, https://en.wikipedia.org/wiki/Quicksort, [online], Accessed 2020-07-27.
[5] Binary search algorithm, https://en.wikipedia.org/wiki/Binary_search_algorithm, [online], Accessed 2020-07-29.
Page 5 of 6
EEET2394
Appendix: RISC-V Calling convention
Laboratory 2 – VR Sensor Signal Processing
Register
Alias
Description
Saver
x0
zero
–
–
x1
ra
Return address/link register
Caller
x2
sp
Stack pointer
Callee
x3
gp
Global pointer
–
x4
tp
Thread pointer
–
x5–x7, x28–x31
t0–t2, t3 – t6
Temporaries
Caller
x8–x9, x18–x27
s0 – s1, s2 – s11
Saved
Callee
x10 – x17
a0 – a7
Arguments/results
Caller
Page 6 of 6