Solved :Lab 1

In this lab, we will learn how to work with an ARM processor and the basics of ARM assembly by programming some common rou nes. The following lecture content will be required for conduc ng this lab: compare instruc ons, branch instruc ons, shi instruc ons, load and store instruc ons, subrou nes and func on calls.

Part 1

In this part, we will implement a well-known op miza on technique, namely stochas c gradient descent (SGD), which is the backbone of a wide range of machine learning algorithms. We will use the SGD technique to solve a simple problem: finding the square root of an integer number.

Let
2

, where
∈
+ , the task is to calculate

. Let
=

(2−)2
be a






















= round(   )

4

loss func
on. The square root of
can be found (approximated) by finding  ∗ that minimizes
the loss func on L, where
∗


.















= argmin∀







To find (es

mate)
∗ using the SGD technique, at the first
me step,
, we start with a
(random) value of
0
. The algorithm updates the es
mate of  ∗ by performing the following
computa
on at each itera
on










+1=−∗

′



2
− )
,









()= −∗(








where




is the learning rate,
is the
me step. To simplify the update equa on,

(0<  <1)


−  and   ∈


ce, the value of
∗ ( 2 − )  is
we choose  to be in the form of

+ . In prac


o en constrained to be within an interval
(−, ),
to enable numerical stability.











> 0,





In C, finding the square root of an integer number
using the SGD technique with 100
itera
ons (

) can be implemented as:









cnt=100
























/
int sqrtIter(int a, int xi, int cnt, int k, int t)

{

for (int i=0; i<cnt; i++)

{

int step = ((xi*xi-a)*xi)>>k;

if (step > t)

step = t;

else if(step< -t)

step = -t;

    xi = xi - step;

}

return xi;

}

int x = sqrtIter(168, 1, 100, 10, 2); // Output: 13




In addi on, the itera ve approach used in the transformed to a recursive manner as follows.




sqrtIter




func on can be alterna vely

int sqrtRecur(int a, int xi, int cnt, int k, int t)

{

if (cnt == 0)

return xi;

else

{

int grad =
((xi * xi - a) * xi) >> k;
if (grad >
t)
grad =
t;
else if (grad < -t)
grad =
-t;
    xi = xi - grad;

return sqrtRecur(a, xi, cnt - 1, k, t);

}

}

int x = sqrtRecur(168, 1, 100, 10, 2); // Output: 13




In this part, your tasks consit of wring assembly programs to find the square root of an integer

number
using different approaches. Note that in all cases,

is stored in

, a  is stored in


xi

r0


, and

is stored in

. The values of k , and t  are treated as immediate values and
r1

cnt

r2



are fixed to 10, and 2, respec vely. In addion, it is recommended that you perform the second exercise of Part 1 only once you will have covered funcon calls in the lecture.

Part 1 Exercises


    1. Write an assembly program that implements the

    2. Write an assembly program that implements the and func on calls.


sqrtIter  func on.


sqrtRecur  func on using subrou nes


Note

/
If you are experiencing the warning Func on calls nested too many levels (> 32), e.g., when cnt>32 for the sqrtRecur func on, you can turn off the warning message by naviga ng to the Se ngs/Debugging Check menu of the simulator, then please un ck the following op on: Func on nes ng too deep.



Part 2

In this part, your task is to calculate the norm of a vector (array). Let




= { 0, 1,…  −1}
be a vector of size  . The norm of  is given as
2
2
2
.

0
+ 1
+⋯+  −1


|| ||=√




Note that you can reuse one of the assembly programs in Part 1 to calculate the square root

in the above equa on. In addi on, we only consider the length of  to be a power of 2, thus

the division can be implemented by a right-shi    opera on.


Below is a C program that calculates the norm of a given vector (array) of size 4.




// Initialization

int array[] = {5, 6, 7, 8};

size_t n = sizeof(array) / sizeof(array[0]);

int log2_n = 0;

int *ptr;

int tmp = 0;

int norm = 1;

int cnt = 100;

int k = 10;

int t = 2;

    • Calculate log_2(n) while ((1 << log2_n) < n)
log2_n++;

    • Calculate the norm of the given array ptr = &array[0];
for (int i = 0; i < n; i++)

{

tmp += (*ptr) * (*ptr); ptr++;

}

tmp = tmp >> log2_n;

norm = sqrtIter(tmp, norm, cnt, k, t); // Output: 7




Part 2 Exercises


    1. Understand the C program that calculates the norm of a vector (array), add comments to the C program if necessary.
    2. Write an assembly that calculates the norm of a vector (array). Note that the length of the array is also given as a parameter of the program. If you did not manage to implement the sqrtIter func on in part 1, simply call a dummy func on that returns its argument and


/
you will not loose any point as long as you can demonstrate you can call a func on correctly (you may want to wait before implemen ng the func on call un l this has been covered in the lectures).

Part 3

In this part, your task is to implement an algorithm that “centers” a vector (array). It is o en necessary to ensure that a signal is “centered” (that is, its average is 0). For example, DC signals can damage a loudspeaker, so it is important to center an audio signal to remove DC components before sending the signal to the speaker.

You can center a signal by calcula ng the mean (average value) of the signal and subtrac ng the average from every sample of the signal. Write an ARM assembly program to center a signal.

The program should be able to accept the signal length as an input parameter. In order to simplify calcula ons, work with the assump on that only signal lengths that are powers of two can be passed to the program.

The following C program implements the above array centering algorithm.




// Initialization

int array[] = {3, 4, 5, 4};

size_t n = 4;

int mean = 0;

int *ptr;

    • Calculate log_2(n) int log2_n = 0;
while ((1 << log2_n) < n)  log2_n++;

    • Calculate the mean of the given array ptr = &array[0];
for (int i = 0; i < n; i++)

{

mean += *ptr; ptr++;

}

mean = mean >> log2_n;

    • Center the given array

ptr = &array[0];

for (int i = 0; i < n; i++)

{

*ptr -= mean;

ptr++;

}

// Output: array={-1,0,1,0}




Part 3 Exercises

/
    1. Understand the C program of the array centering algorithm, add comments to the C program if necessary.
    2. Write an assembly program that performs the array centering algorithm. Note that the length of the array is also given as an input parameter of the program. Store the resul ng centered signal ‘in place’ - i.e. in the same memory loca on that the input signal is passed in.

Part 4

In this part, your task is to implement the selec on sort algorithm. Below is an example of the selec on sort algorithm implemented in a C program.



int array[] = {4, 2, 1, 4, -1};

size_t n = sizeof(array) / sizeof(array[0]);

int *ptr = &array[0];

for (int i = 0; i < n-1; i++)

{

int tmp = *(ptr + i);

int cur_min_idx = i;

for (int j = i + 1; j < n; j++)

{

if (tmp > *(ptr + j))

{

tmp = *(ptr + j);

cur_min_idx = j;

}

}

// Swap

tmp = *(ptr + i);

*(ptr + i) = *(ptr + cur_min_idx);

*(ptr + cur_min_idx) = tmp;

}

// Output: array={-1, 1, 2, 4, 4}




Part 4 Exercises


    1. Understand the C program of the selec on sort algorithm, add comments to the C program if necessary.
    2. Write an assembly program that implements the selec on sort algorithm to sort a given array in ascending order. Note that the length of the array is also given as an input parameter of the program.

Grading and Report

Your grade will be evaluated through the deliverables of your work during the demo (70%) (basically showing us the working programs), your answers to the ques ons raised by the TA’s during the demo (10%), and your lab report (20%).

Grade distribu on of the demo:
/
Part 1.1: assembly implementa on of sqrtIter  (5%).


Part 1.2: assembly implementa on of sqrtRecur  (10%).


Part 2: assembly program that calculates the norm of an array (15%).


Part 3: assembly program that centers an array (15%).


Part 4: assembly program that implements selec on sort algorithm (25%).



Write up a short report (~1 page per part) that should include the following informa on.


A brief descrip on of each part completed (do not include the en re code in the body of the report).

The approach taken (e.g., using subrou nes, stack, etc.).


The challenges faced, if any, and your solu ons.


Possible improvevement to the programs.



Your final submission should be sumi ed on myCourses. The deadline for the submission and the report is Friday, 16 October 2020. A single compressed folder should be submi ed in the
.zip format, that contains the following files:


Your lab report in pdf format: StudentID_FullName_Lab1_report.pdf


The assembly program for Part 1.1: part1_1.s


The assembly program for Part 1.2: part1_2.s


The assembly program for Part 2: part2.s


The assembly program for Part 3: part3.s


The assembly program for Part 4: part4.s



Important

Note that we will check every submission (code and report) for possible plagiarism. All suspected cases will be reported to the faculty. Please make sure to familiarize yourself with the course policies regarding Academic Integrity and remember that all the labs are to be done individually. Also please note that you are not allowed to use a compiler to generate the assembly code and must write it by hand.


The demo will take place via Zoom during the week of 5-9 October 2020 on the day of you assigned lab session day. We will provide a registra on system for the demo the week before. You will need to answer live ques ons during the demo with your screen shared to onstrate the working program.












/