ECSE 324- Lab 1

 » Labs » Lab 1
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 rounes. The following lecture content will be required for
conducng this lab: compare instrucons, branch instrucons, shi instrucons, load and store
instrucons, subrounes and funcon calls.
Part 1
In this part, we will implement a well-known opmizaon technique, namely stochasc 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 , where , the task is to calculate . Let be a loss
funcon. The square root of can be found (approximated) by finding that minimizes the loss
funcon L, where .
To find (esmate) using the SGD technique, at the first me step, , we start with a
(random) value of . The algorithm updates the esmate of by performing the following
computaon at each iteraon
,
where is the learning rate, is the me step. To simplify the update equaon, we
choose to be in the form of and . In pracce, the value of is oen
constrained to be within an interval to enable numerical stability.
In C, finding the square root of an integer number using the SGD technique with 100 iteraons
( cnt=100 ) can be implemented as:
𝑥 = 𝑎
2 𝑎 ∈ 𝑍+ 𝑥 = round(√𝑎‾) 𝐿 =
(𝑥 −𝑎
2
)
2
4
𝑎 𝑥
∗
𝑥 = 𝐿
∗ argmin∀𝑥
𝑥
∗
𝑖 = 0
𝑥0 𝑥
∗
𝑥𝑖+1 = 𝑥𝑖 − 𝛾 ∗ 𝐿 ( ) = − 𝛾 ∗ ( − 𝑎)
′ 𝑥𝑖 𝑥𝑖 𝑥
2
𝑖 𝑥𝑖
𝛾 (0 < 𝛾 < 1) 𝑖
𝛾 2
−𝑘 𝑘 ∈ 𝑍+
𝛾 ∗ (𝑥 − 𝑎)𝑥
2
(−𝑡, 𝑡), 𝑡 0,
𝑎
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 addion, the iterave approach used in the sqrtIter funcon can be alternavely
transformed to a recursive manner as follows.
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, xi is stored in r0 , a is stored in
r1 , and cnt is stored in r2 . The values of k , and t are treated as immediate values and are
fixed to 10, and 2, respecvely. 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 sqrtIter funcon.
2. Write an assembly program that implements the sqrtRecur funcon using subrounes and
funcon calls.
𝑎
 Note
If you are experiencing the warning Funcon calls nested too many levels ( 32), e.g., when
cnt32 for the sqrtRecur funcon, you can turn off the warning message by navigang to
the Sengs/Debugging Check menu of the simulator, then please unck the following
opon: Funcon nesng too deep.
Part 2
In this part, your task is to calculate the norm of a vector (array). Let be
a vector of size . The norm of is given as .
Note that you can reuse one of the assembly programs in Part 1 to calculate the square root in
the above equaon. In addion, we only consider the length of to be a power of 2, thus the
division can be implemented by a right-shi operaon.
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.
𝑥 = {𝑥0, 𝑥1, … 𝑥𝑛−1 }
𝑛 𝑥 ||𝑥|| =
𝑥 + +⋯+
2
0 𝑥
2
1 𝑥
2
𝑛−1
𝑛
‾‾‾‾‾‾‾‾‾‾‾‾ √
𝑥
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 funcon in part 1, simply call a dummy funcon that returns its argument and you
will not loose any point as long as you can demonstrate you can call a funcon correctly (you
may want to wait before implemenng the funcon call unl 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 oen
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 calculang the mean (average value) of the signal and subtracng 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 calculaons, work with the assumpon 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 resulng centered
signal ‘in place’ - i.e. in the same memory locaon that the input signal is passed in.
Part 4
In this part, your task is to implement the selecon sort algorithm. Below is an example of the
selecon 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 selecon sort algorithm, add comments to the C program if
necessary.
2. Write an assembly program that implements the selecon 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 quesons raised by the TA’s
during the demo (10%), and your lab report (20%).
Grade distribuon of the demo:
Part 1.1: assembly implementaon of sqrtIter (5%).
Part 1.2: assembly implementaon 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 selecon sort algorithm (25%).
Write up a short report (~1 page per part) that should include the following informaon.
A brief descripon of each part completed (do not include the enre code in the body of the
report).
The approach taken (e.g., using subrounes, stack, etc.).
The challenges faced, if any, and your soluons.
Possible improvevement to the programs.
A single compressed folder should be submied 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