CS3350B Computer Organization Chapter 1: CPU and Memory Some Locality Examples
Alex Brandt
Department of Computer Science University of Western Ontario, Canada
Monday January 18, 2021
Alex Brandt
Chapter 1: CPU and Memory, Some Locality Examples Monday January 18, 2021 1 / 7
Instruction Locality Example 1
A C function and program.
int doSomething() {
int z = 10+12;
return z;
}
int main() {
int a = 1;
int b = 2;
doSomething();
return 0;
}
That program in assembly (MIPS).
doSomething:
add $t0 $0 $0
addi $t0 $t0 10
addi $t0 $t0 12
add $v0 $t0 $0
jr $ra
main:
li $s0 1
li $s1 2
jal doSomething
li $v0 10
syscall
Alex Brandt Chapter 1: CPU and Memory, Some Locality Examples Monday January 18, 2021 2 / 7
Instruction Locality Example 1
That program in assembly (MIPS).
doSomething:
add $t0 $0 $0
addi $t0 $t0 10
addi $t0 $t0 12
add $v0 $t0 $0
jr $ra
main:
li $s0 1
li $s1 2
jal doSomething
li $v0 10
syscall
Program Binary (fake).
01100010 00100010 10111000 11101010
01111011 10001000 11111001 11110100
00001011 11010111 01010001 11010110
00000110 00010011 10101111 01010010
10111100 00100011 01000010 00111000
10111011 00111011 01100010 00100101
00001010 01011011 10011101 01001011
10000001 01001011 01010110 10101101
11101110 11011100 11110000 00101011
11000101 10010001 00001101 11110010
A method call jumps to a different area of the program binary!
Alex Brandt Chapter 1: CPU and Memory, Some Locality Examples Monday January 18, 2021 3 / 7
Instruction Locality Example 2
An inlined C function and program.
inline int doSomething() {
int z = 10+12;
return z;
}
int main() {
int a = 1;
int b = 2;
doSomething();
return 0; }
That program in assembly (MIPS).
main:
li $s0 1
li $s1 2
add $t0 $0 $0
addi $t0 $t0 10
addi $t0 $t0 12
add $v0 $t0 $0
li $v0 10
syscall
Alex Brandt Chapter 1: CPU and Memory, Some Locality Examples
Monday January 18, 2021
4 / 7
Instruction Locality Example 2
main:
li $s0 1
li $s1 2
add $t0 $0 $0
addi $t0 $t0 10
addi $t0 $t0 12
add $v0 $t0 $0
li $v0 10
syscall
10011010 01110111 00101101 00110000
00010110 11011011 11000000 01101011
01001000 10011111 11010100 10100101
10000011 01101111 10110100 01100001
00000101 01110010 00101010 00110101
00110000 00111010 11101001 11110010
10010000 00110001 11110000 00100000
10101111 00110101 00100100 01110000
Inlined function ï All instructions are sequential.
Alex Brandt Chapter 1: CPU and Memory, Some Locality Examples Monday January 18, 2021 5 / 7
Data Locality Example Without Arrays (1/2)
Highly simplified example.
Assume CPU has no registers and cache is 4 words using LRU.
int fibonacci1(int n) {
int t1 = 0, t2 = 1;
if (n < 1) {
return t1; }
if (n < 2) {
return t2;
}
for (int i = 1; i < n ++i) {
int t3 = t1 + t2;
t1 = t2;
t2 = t3;
}
return t3; }
Inst. M/H t1n t1=0 M
Cache Contents
n start M
t2t1n nt2t1
in t2 t1 t1 t2 i n t3 t1 t2 n
t1 t2 t3 n
t2 t3 t1 n
i t2 t3 t1
in t2 t3 t1 t2 in t3 t1 t2 n
t2=1 M n<1;n<2H
i = 0; i < n t1+t2
t3=t1 t1=t2 t2=t3 ++i i