代写EEET2394、代做VR Sensor、c/c++，Python，Java程序语言代写

日期：2020-08-10 11:39

EEET2394 Laboratory 2 – VR Sensor Signal Processing

Page 2 of 6

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.

EEET2394 Laboratory 2 – VR Sensor Signal Processing

Page 3 of 6

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 rightshift

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.

EEET2394 Laboratory 2 – VR Sensor Signal Processing

Page 4 of 6

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 + 1

else if A[m] > T then

R := m ? 1

else:

return m

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.