Comp2300 & Comp6300 Computer Organisation & Program Execution
The Australian National University Final Examination
- [8 marks] Logic & Instructions
(a) [4 marks] Your ARM CPU produces four main flag outputs for specific instructions:
N – Negative Z – Zero
C – Carry
V – Overflow
Provide the smallest number of ARM instruction which will set each of these flags indi- vidually while clearing all other flags. So you should produce the flag sequence:
N – Negative Z – Zero C – Carry V – Overflow
1000
0100
0010
0001
To make your life easier, assume that the following instructions were executed right before your instructions. Hint: the overflow flag is the tricky one, which requires a minimum of two ARM instructions.
movs r0, #0x00000001 movs r1, #0xFFFFFFFF movs r2, #0x7FFFFFFF movs r3, #0x80000000
(b) [4 marks] Explain why your ARM CPU does not provide an arithmetic-shift-left in- struction.
Comp2300 & Comp6300 Final Exam 2021 Page 2 of 16 - [24 marks] Functions
(a) [24 marks] Write a function in ARM assembly code, which doubles the individual values in a given array, which holds (word-sized) natural numbers. Your function will need to be able to handle different sized arrays. Four different versions of this function are required. The higher level language fragments below are for illustration only, as you can answer this question without being able to read any of those.
(i) [6 marks] Write an iterative version of this function which doubles the values inside the original array. This version of the function is side-effecting, but does not have any direct return value (hence it is called a procedure or void function). Your code will re- semble the output of a compiler for any of the following higher languages fragments:
Algol-style:
type Naturals is array (Positive range <>) of Natural;
procedure Double_In_Place (Numbers : access Naturals) is
begin
for E of Numbers.all loop
E := 2 * E;
end loop;
end Double_In_Place;
C-style:
void double_in_place (unsigned int array [], unsigned int length) {
unsigned int i;
for (i = 0; i + 1 <= length; i++) {
array [i] = 2 * array [i];
} }
Comp2300 & Comp6300 Final Exam 2021 Page 3 of 16
(ii) [6 marks] Write an iterative version of this function which has no side-effects, thus returns a new array where each element is double the value of the correspond- ing element in the original array. Your code will resemble the output of a compiler for the following higher language fragment (note that neither this, nor any of the follow- ing versions can be expressed in C-style languages, unless heap memory allocation is available):
Algol-style:
type Naturals is array (Positive range <>) of Natural;
function Double_Iterative (Numbers : Naturals) return Naturals is
Doubled_Numbers : Naturals (Numbers’Range);
begin
for I in Numbers’Range loop
Doubled_Numbers (I) := 2 * Numbers (I);
end loop;
return Doubled_Numbers;
end Double_Iterative;
Comp2300 & Comp6300 Final Exam 2021 Page 4 of 16
(iii) [6 marks] Write a recursive version of this function, which also has no side effects. Your code will resemble the output of a compiler for any of the following higher lan- guages fragments. Warning: this is a hard question.
Algol-style:
type Naturals is array (Positive range <>) of Natural;
function Double_Recursive (Numbers : Naturals) return Naturals is
(if Numbers’Length = 0
then Numbers
else 2 * Numbers (Numbers’First)
& Double_Recursive (Numbers (Numbers’First + 1 .. Numbers’Last)));
Functional-style:
double_recursive :: (Num a) => [a] -> [a]
double_recursive list = case list of
[] -> []
x: xs -> 2 * x : double_recursive xs
Comp2300 & Comp6300 Final Exam 2021 Page 5 of 16
(iv) [6 marks] Write a more flexible version of this function, which can be used to ap- ply any operation on the individual array elements. This version is also to be without side-effects, but you can chose an iterative or recursive form. Your code will resemble the output of a compiler for any of the following higher languages fragments:
Algol-style:
type Naturals is array (Positive range <>) of Natural;
function Map_Iterative (Numbers : Naturals;
Operation : access function (X : Natural) return Natural) return Naturals is
Doubled_Numbers : Naturals (Numbers’Range);
begin
for I in Numbers’Range loop
Doubled_Numbers (I) := Operation (Numbers (I));
end loop;
return Doubled_Numbers;
end Map_Iterative;
Functional-style:
map_recursive :: (a -> b) -> [a] -> [b]
map_recursive op list = case list of
[] -> []
x: xs -> op x: map_recursive op xs
Comp2300 & Comp6300 Final Exam 2021 Page 6 of 16
- [15 marks] Decompile & Optimize
(a) [5 marks] Write a program in any programming language of your choice which might have compiled down to the below ARM assembly code.
func:
stmdb sp!, {fp, lr} add fp, sp, #4 sub sp, #4
str r0, [fp, #-8] cbz r0, end_func sub r0, #1
bl func
ldr r1, [fp, #-8] add r0, r1
end_func:
add sp, #4
ldmia sp!, {fp, lr} bx lr
(b) [10 marks] Optimize the above ARM code as much as you can for performance, while keeping the exact same response to “bl func” (everything else can change).
Comp2300 & Comp6300 Final Exam 2021 Page 7 of 16 - [17 marks] Writing programs
(a) [5 marks] Your embedded device has been equipped with a key device, which provides secret key data via a single address in memory (ADR_KEY). You can load this address in the usual way into a register:
ldr r0, =ADR_KEY
On reading data from this address, you will be provided with unique key data. The next time you will be reading from this address, new key data will be provided. Simi- larly your device has also been equipped with a laser sensor which will provide fresh readings every time you read data from memory address ADR_LASER.
Your mission is top secret and the raw data from this laser cannot fall into the wrong hands. Consequently you will need to encrypt the raw data, before you can store it into local memory. Do this by a bit-wise ex-or operation between the key data and
the raw laser data. The key data will disappear from your device upon usage (the only other, known copy of the key data rests inside the ruler-of-the-universe’s toaster).
The key data as well as the raw laser data is sensitive and should only be held inside your device for processing for the shortest time possible and should never be stored in memory. Store the encrypted laser data at the address which is stored at the address ADR_SECRET_ADR. You will need to increment this address, after each usage, so that all data can be recorded (don’t worry about memory overflows).
Write an ARM assembly function Laser_Handler which can be used as an interrupt handler responding to the laser indicating that new data is available. Do not worry about how to connect the interrupt handler to the specific interrupt: this has already been done for you.
Comp2300 & Comp6300 Final Exam 2021 Page 8 of 16
(b) [12 marks] Write an ARM assembly function, which returns the maximum value of an unknown-sized array of integer numbers, which it takes as a parameter. If the array is empty your function should return -231 .
(i) [6 marks] Write a recursive version. Which parameter modes did you chose?
(ii) [6 marks] Write an iterative version. Which parameter modes did you chose?
Comp2300 & Comp6300 Final Exam 2021 Page 9 of 16
- [20 marks] Asynchronous Programming
(a) [10 marks] Implement the following concurrent code in ARM assembly, such that the final value of Counter will be 0, after both tasks completed. For performance reasons, keep the durations of synchronised code sections to a minimum.
The following Algol-style pseudo code (as used in lectures) shows: one task incre- ments a global Counter variable by 100, while another task decrements the same global Counter variable 10-times by 10:
Counter : Integer := 0;
task Up is
begin
Counter := Counter + 100;
end Up;
task Down is
begin
for I in 1 .. 10 loop
Counter := Counter – 10;
end loop;
end Down;
Assume the following global memory declaration:
Counter:
.word 0x00000000
Comp2300 & Comp6300 Final Exam 2021
Page 10 of 16
(b) [5 marks] Can you use a semaphore-wait operation inside of an interrupt handler? What would be the possible uses, or dangers? Will your answer be different for a single-core and a multi-core CPU? Explain as precisely as you can.
(c) [5 marks] In a press release on an unnamed manufacturer, it was revealed that a mal- function of a fast moving device was caused by a stack-overflow by interrupts. Could this be true? What would you recommend for this manufacturer to introduce in their design processes? Explain as precisely as you can.
Comp2300 & Comp6300 Final Exam 2021 Page 11 of 16
- [16 marks] Operating Systems, Networks & Architectures
(a) [3 marks] What are the minimal hardware requirements which enable you to write a multi-tasking operating system with a round robin scheduler? Give precise reasons for your answers.
(b) [3 marks] In a computer network, how can you send user data to devices which are not directly connected to your sending device? Which administrative data (in terms of OSI layers) will need to be looked at along the way, before your user data reaches the target device. Give precise reasons for your answers.
Comp2300 & Comp6300 Final Exam 2021 Page 12 of 16
(c) [4 marks] The following function is an attempt of one of your fellow students to write a fast sum-function (adding up all values inside of an array). You are however more educated than your fellow student and know about pipeline hazards. Optimize the program below such that pipeline hazards are avoided and the performance will in- crease (obviously without losing the logical correctness). Re-write the function inside the answer box and note for each of your changes which pipeline hazard you address.
@ r0: Address of array
@ r1: Size of array
@ return the sum of values in r0
Fast_Sum:
mov r2, r0
add r3, r2, r1, lsl #2 mov r0, #0
Fast_Sum_Loop:
ldr r1, [r2], #4 add r0, r1
cmp r2, r3
blt Fast_Sum_Loop bx lr
Comp2300 & Comp6300
Final Exam 2021
Page 13 of 16
(d) [6 marks] If you consider the following code fragment, which hardware support would you suggest to run this program correctly and at high performance. Relate each sug- gested hardware architecture to a concrete aspect of the code.
The code defines a global data array with 10.000 floating point values (all initialized to 1.0), as well as 100 tasks which each double all elements in this array.
Data : array (1 .. 10_000) of Float := (1 .. 10_000 => 1.0);
task type Worker;
task body Worker is
begin
for I in Data’Range loop
Data (I) := 2.0 * Data (I);
end loop;
end Worker;
Workers : array (1 .. 100) of Worker;
Comp2300 & Comp6300 Final Exam 2021 Page 14 of 16
continuation of answer to question part
continuation of answer to question part
Comp2300 & Comp6300 Final Exam 2021 Page 15 of 16
continuation of answer to question part
continuation of answer to question part
Comp2300 & Comp6300 Final Exam 2021 Page 16 of 16