CS计算机代考程序代写 data structure arm COPE-04 Data Structures.indd

COPE-04 Data Structures.indd

4
Data Structures

Uwe R. Zimmer – The Australian National University

Computer Organisation & Program Execution 2021

Data Structures

References for this chapter

[Patterson17]
David A. Patterson & John L. Hennessy
Computer Organization and Design – The Hardware/Software Interface
Chapter 2 “Instructions: Language of the Computer”,
Chapter 5 “Large and Fast: Exploiting Memory Hierarchy”
ARM edition, Morgan Kaufmann 2017

Data Structures

Array layout

e0_b0

0347

e0_b1
e0_b2
e0_b3
e1_b0
e1_b1
e1_b2
e1_b3
e2_b0
e2_b1
e2_b2
e2_b3
e3_b0
e3_b1
e3_b2
e3_b3

}
x + 4

x + 8

x + 12

Array element

Lower array bound

Upper array boundx + 15

Elements of equal size
sequentially in memory

Data Structures

Array addressing

e0_b0

0347

e0_b1
e0_b2
e0_b3
e1_b0
e1_b1
e1_b2
e1_b3
e2_b0
e2_b1
e2_b2
e2_b3
e3_b0
e3_b1
e3_b2
e3_b3

}
x + 1·es

x + 0·es

x + 2·es

x + 3·es

Element size (es)
4 bytes

Lower array bound

Upper array boundx + 4·es – 1

x + i·es

Maybe be good to
have es 2n= ?

What happens if array
bounds are violated?

And who is checking that?

Can arrays always be
stored “packed”?

Data Structures

Array addressing via index register

e0_b0

0347

e0_b1
e0_b2
e0_b3
e1_b0
e1_b1
e1_b2
e1_b3
e2_b0
e2_b1
e2_b2
e2_b3
e3_b0
e3_b1
e3_b2
e3_b3

Rb – Base address

Ri – Index {shifted} +

Rd – Destination}

ldr , [, {, lsl #}]

Data Structures

Array addressing via index register

e0_b0

0347

e0_b1
e0_b2
e0_b3
e1_b0
e1_b1
e1_b2
e1_b3
e2_b0
e2_b1
e2_b2
e2_b3
e3_b0
e3_b1
e3_b2
e3_b3

Rb – Base address

Ri – Index {shifted} +

Rd – Destination}

ldr , [, {, lsl #}]

Shift works if es 2
n=

2b22b22_b2
b3b3_b3
b0

_
_

ee2ee2ee2_
e2e2e2_
e3

e2_
_

e3e3e3
Can be handy if Ri is actually an index.

e3 b2e3_b2
e3 b33 be3 b3e3 b3

000
11e3_b1

e3 b2e3 b2e3 b2

33e333e3 b0b0e3_b0
e3 b1e3 b1e3 b1 Otherwise Ri will be a byte offset.

Data Structures

Array addressing via element pointer

e0_b0

0347

e0_b1
e0_b2
e0_b3
e1_b0
e1_b1
e1_b2
e1_b3
e2_b0
e2_b1
e2_b2
e2_b3
e3_b0
e3_b1
e3_b2
e3_b3

Rd – Destination}Rp – Array pointer
Element offset

Write-back

ldr , [], #+/-

Data Structures

Array addressing via element pointer

e0_b0

0347

e0_b1
e0_b2
e0_b3
e1_b0
e1_b1
e1_b2
e1_b3
e2_b0
e2_b1
e2_b2
e2_b3
e3_b0
e3_b1
e3_b2
e3_b3

Rd – Destination}Rp – Array pointer
Element offset

Write-back

ldr , [], #+/-

2222
33

e3 b2e3 b2ee3_b2
e3_b33_be3 b3e3 b3

Effi cient if array has to be worked sequentially

Data Structures

Calculate xi/
int sum (unsigned int uints [], unsigned int from, unsigned int to) {

int i;
int acc = 0;

for (i = from; i <= to; i++) { acc += uints [i]; } return acc; } type Naturals is array (Integer range <>) of Natural;

function Sum (Numbers : Naturals) return Natural is

Acc : Natural := 0;

begin
for n of Numbers loop
Acc := Acc + n;
end loop;
return Acc;
end Sum;

g ) {) {

unsigned int uints [100];

unsigned int s;

int i;

for (i = 0; i <= 99; i++) { uints [i] = rand (); } s = sum (uints, 0, 99); Numbers : constant Naturals (1 .. 100) := (others => Random (Numbers_Generat
or));

Sum_of_Numbers : constant Natural := Sum (Numbers);

Data Structures

Calculate xi/
int sum (unsigned int uints [], unsigned int from, unsigned int to) {

int i;
int acc = 0;

for (i = from; i <= to; i++) { acc += uints [i]; } return acc; } type Naturals is array (Integer range <>) of Natural;

function Sum (Numbers : Naturals) return Natural is

Acc : Natural := 0;

begin
for n of Numbers loop
Acc := Acc + n;
end loop;
return Acc;
end Sum;

g ) {) {) {) {

unsigned int uints [100];

unsigned int s;

int i;

for (i = 0; i <= 99; i++) { uints [i] = rand (); } s = sum (uints, 0, 99); Numbers : constant Naturals (1 .. 100) := (others => Random (Numbers_Generat
or));

Sum_of_Numbers : constant Natural := Sum (Numbers);

}
s

;

Best of luck with the array bounds!

Data Structures

Arbitrary array indexing
; r0 base address for array a
; r1 from array index
; r2 to array index

mov r3, #0 ; sum := 0
mov r4, #4 ; element size is 4 bytes
mov r5, #-1 ; first_element_offset

for_sum:
cmp r1, r2 ; i > to
bgt end_for_sum
mla r6, r1, r4, r5 ; element_offset := (i * 4) – first_element_offset
ldr r7, [r0, r6] ; a [i] := [base + element_offset]
add r3, r7 ; sum := sum + a [i]
add r1, #1 ; i := i + 1
b for_sum

end_for_sum:
mov r0, r3 ; r0 sum over all a [from .. to]

Data Structures

Zero-based array indexing
; r0 base address for array a
; r1 from array index
; r2 to array index

mov r3, #0 ; sum := 0
mov r4, #4 ; element size is 4 bytes

for_sum:
cmp r1, r2 ; i > to
bgt end_for_sum
mul r5, r1, r4 ; element_offset := (i * 4)
ldr r6, [r0, r5] ; a [i] := [base + element_offset]
add r3, r6 ; sum := sum + a [i]
add r1, #1 ; i := i + 1
b for_sum

end_for_sum:
mov r0, r3 ; r0 sum over all a [from .. to]

Data Structures

Replacing multiplication with shifted index register
; r0 base address for array a
; r1 from array index
; r2 to array index

mov r3, #0 ; sum := 0

for_sum:
cmp r1, r2 ; i > to
bgt end_for_sum
ldr r4, [r0, r1, lsl #2] ; a [i] := [base + element_offset]
add r3, r4 ; sum := sum + a [i]
add r1, #1 ; i := i + 1
b for_sum

end_for_sum:
mov r0, r3 ; r0 sum over all a [from .. to]

Data Structures

Replacing indices with offsets
; r0 base address for array a
; r1 from array index
; r2 to array index

lsl r1, r1, #2 ; translate from index to offset
lsl r2, r2, #2 ; translate to index to offset
mov r3, #0 ; sum := 0

for_sum:
cmp r1, r2 ; i > to
bgt end_for_sum
ldr r4, [r0, r1] ; a [i] := [base + offset]
add r3, r4 ; sum := sum + a [i]
add r1, #4 ; offset := offset + 4
b for_sum

end_for_sum:
mov r0, r3 ; r0 sum over all a [from .. to]

Data Structures

Assuming non-empty arrays
; r0 base address for array a
; r1 from array index
; r2 to array index >= from index

lsl r1, r1, #2 ; translate from index to offset
lsl r2, r2, #2 ; translate to index to offset
mov r3, #0 ; sum := 0

for_sum:
ldr r4, [r0, r1] ; a [i] := [base + offset]
add r3, r4 ; sum := sum + a [i]
add r1, #4 ; offset := offset + 4
cmp r1, r2 ; i <= to ble for_sum end_for_sum: mov r0, r3 ; r0 sum over all a [from .. to] 3 6 1 Data Structures © 2021 Uwe R. Zimmer, The Australian National University page 248 of 487 (chapter 4: “Data Structures” up to page 253) Replacing offsets with addresses ; r0 base address for array a ; r1 from array index ; r2 to array index >= from index

lsl r1, r1, #2 ; translate from index to offset
lsl r2, r2, #2 ; translate to index to offset
add r1, r0 ; translate from index to address -> i_addr
add r2, r0 ; translate to index to address -> to_addr
mov r0, #0 ; sum := 0

for_sum:
ldr r3, [r1], #4 ; a [i] := [i_addr]; i_addr += 4
add r0, r3 ; sum := sum + a [i]
cmp r1, r2 ; i_addr <= to_addr ble for_sum end_for_sum: ; r0 sum over all a [from .. to] 5 5 Data Structures © 2021 Uwe R. Zimmer, The Australian National University page 249 of 487 (chapter 4: “Data Structures” up to page 253) Array Slices numbers = [0, 1, 2, 3, 4, 5] numbersSlice = numbers [1:3] # numbersSlice equals [1, 2, 3] numbers := []int {0, 1, 2, 3, 4, 5} numbersSlice := numbers [1:3] type Naturals is array (Integer range <>) of Natural;

Numbers : constant Naturals (-50 .. 50) := (others => Random (Generator));

Numbers_Slice_1 : constant Naturals := Numbers (-10 .. 10);
Numbers_Slice_2 : constant Naturals ( 1 .. 10) := Numbers ( 11 .. 20);
Numbers_Slice_3 : Naturals := Numbers (-20 .. 50);

begin
for n of Numbers_Slice_3 loop
n := n + 1;
end loop;
end;

Data Structures

Array Slices
numbers = [0, 1, 2, 3, 4, 5]
numbersSlice = numbers [1:3]

# numbersSlice equals [1, 2, 3]

numbers := []int {0, 1, 2, 3, 4, 5}
numbersSlice := numbers [1:3]

type Naturals is array (Integer range <>) of Natural;

Numbers : constant Naturals (-50 .. 50) := (others => Random (Generator));

Numbers_Slice_1 : constant Naturals := Numbers (-10 .. 10);
Numbers_Slice_2 : constant Naturals ( 1 .. 10) := Numbers ( 11 .. 20);
Numbers_Slice_3 : Naturals := Numbers (-20 .. 50);

begin
for n of Numbers_Slice_3 loop
n := n + 1;
end loop;
end;

Are those copy or
reference affairs?

Data Structures

Copy array slice
; r0 base address for array a
; r1 from array index
; r2 to array index >= from index
; r3 base address for array b

for_copy:
ldr r4, [r1], #4 ; a [i] := [i_addr]; i_addr += 4
str r4, [r3], #4 ; [j_addr] := a [i] ; j_addr += 4
cmp r1, r2 ; i_addr <= to_addr ble for_copy end_for_copy: ; b [] := a [from .. to] 4 6 Data Structures © 2021 Uwe R. Zimmer, The Australian National University page 252 of 487 (chapter 4: “Data Structures” up to page 253) Copy array slice ; r0 base address for array a ; r1 from array index ; r2 to array index >= from index
; r3 base address for array b

for_copy:
ldr r4, [r1], #4 ; a [i] := [i_addr]; i_addr += 4
str r4, [r3], #4 ; [j_addr] := a [i] ; j_addr += 4
cmp r1, r2 ; i_addr <= to_addr ble for_copy end_for_copy: ; b [] := a [from .. to] 4 6 page 252 of 487 (chapter 4: “Data Structures” up to p7page 252 of 487 ( h t 4 “D t St7 Moving blocks of memory can be done even/much faster with special hardware. DMA controllers Data Structures © 2021 Uwe R. Zimmer, The Australian National University page 253 of 487 (chapter 4: “Data Structures” up to page 253) Data Structures • Arrays • Structure • Alignment • Addressing • Iterators • Copy procedures Summary

Related Posts