University
of
Washington
Roadmap
Memory
&
data
Integers
&
floats
Machine
code
&
C
C:
Java:
x86
assembly
car *c = malloc(sizeof(car)); Car c = new Car(); Procedures
&
stacks
c->miles = 100; c.setMiles(100); Arrays
&
structs
c->gals = 17; c.setGals(17);
float mpg = get_mpg(c); float mpg =
Memory
&
caches
free(c); c.getMPG(); Processes
Virtual
memory
Assembly
get_mpg: Memory
allocaIon
language:
pushq %rbp Java
vs.
C
movq %rsp, %rbp
...
popq %rbp
ret
OS:
Machine
0111010000011000
100011010000010000000010
code:
1000100111000010
110000011111101000011111
Computer
system:
Caches
University
of
Washington
SecIon
7:
Memory
and
Caches
¢ Cache
basics
¢ Principle
of
locality
¢ Memory
hierarchies
¢ Cache
organizaIon
¢ Program
opImizaIons
that
consider
caches
Caches
University
of
Washington
How
does
execuIon
Ime
grow
with
SIZE?
int array[SIZE];
int A = 0;
for (int i = 0 ; i < 200000 ; ++ i) {
for (int j = 0 ; j < SIZE ; ++ j) {
A += array[j];
}
} TIME
Plot
SIZE
Caches
University
of
Washington
Actual
Data
Time
SIZE
Caches
University
of
Washington
Problem:
Processor-‐Memory
BoVleneck
Processor
performance
doubled
about
every
18
months
Bus
bandwidth
evolved
much
slower
CPU
Reg
Main
Memory
Core
2
Duo:
Core
2
Duo:
Can
process
at
least
Bandwidth
256
Bytes/cycle
2
Bytes/cycle
Latency
100
cycles
Problem:
lots
of
wai4ng
on
memory
Caches
University
of
Washington
Problem:
Processor-‐Memory
BoVleneck
Processor
performance
doubled
about
every
18
months
Bus
bandwidth
evolved
much
slower
CPU
Reg
Cache
Main
Memory
Core
2
Duo:
Core
2
Duo:
Can
process
at
least
Bandwidth
256
Bytes/cycle
2
Bytes/cycle
Latency
100
cycles
Solu4on:
caches
Caches
University
of
Washington
Cache
¢ English
definiIon:
a
hidden
storage
space
for
provisions,
weapons,
and/or
treasures
¢ CSE
definiIon:
computer
memory
with
short
access
Ime
used
for
the
storage
of
frequently
or
recently
used
instrucIons
or
data
(i-‐cache
and
d-‐cache)
more
generally,
used
to
opImize
data
transfers
between
system
elements
with
different
characterisIcs
(network
interface
cache,
I/O
cache,
etc.)
Caches
University
of
Washington
General
Cache
Mechanics
Smaller,
faster,
more
expensive
Cache
8
9
14
3
memory
caches
a
subset
of
the
blocks
Data
is
copied
in
block-‐sized
transfer
units
Larger,
slower,
cheaper
memory
Memory
0
1
2
3
viewed
as
parIIoned
into
“blocks”
4
5
6
7
8
9
10
11
12
13
14
15
Caches
University
of
Washington
General
Cache
Concepts:
Hit
Request:
14
Data
in
block
b
is
needed
Block
b
is
in
cache:
Cache
8
9
14
3
Hit!
Memory
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Caches
University
of
Washington
General
Cache
Concepts:
Miss
Request:
12
Data
in
block
b
is
needed
Block
b
is
not
in
cache:
Cache
8
9
12 14
3
Miss!
Block
b
is
fetched
from
12
Request:
12
memory
Block
b
is
stored
in
cache
Memory
0
1
2
3
• Placement
policy:
4
5
6
7
determines
where
b
goes
• Replacement
policy:
8
9
10
11
determines
which
block
12
13
14
15
gets
evicted
(vicAm)
Caches
University
of
Washington
Not
to
forget…
CPU
A little of super
fast memory (cache$)
Lots of
slower Mem
Caches
