Formula Sheets: Memory Hierarchy: Cache, Main Memory and Secondary Storage

 Page 1


Memory Hierarc h y: Cac he, Main Memory , and Secondary Stor-
age F orm ula Sheet
Memory Hierarc h y Basics
• Definition : Multi-lev el memory organization (Registers, Cac he, Main Memory , Secondary Stor-
age) to balance sp eed, cost, and capacit y .
• A ccess Time : T
access
, decreases with hierarc h y lev el (Registers: 1 ns, Cac he: 1-10 ns, Main
Memory: 10-100 ns, Secondary: 1-10 ms).
• Capacit y : C , increases with hierarc h y lev el (Registers: KB, Cac he: MB, Main Memory: GB,
Secondary: TB).
• Cost p er Bit : Decreases with hierarc h y lev el (C
reg
»C
cac he
>C
main
>C
secondary
).
• Lo calit y of Reference : T emp oral (reuse recen t data) and Spatial (access nearb y data).
Cac he Memory
• Definition : F ast, small memory b et w een CPU and main memory , stores frequen tly accessed data.
• Cac he Size : C
cac he
=N
lines
·S
line
, where N
lines
is n um b er of cac he lines, S
line
is line size (b ytes).
• Hit Ratio : h =
N
hit
N
hit
+N miss
, t ypically 0.9-0.99.
• Miss Ratio : m = 1-h .
• Effectiv e A ccess Time : T
eff
=h·T
cac he
+(1-h)·T
main
, whereT
cac he
˜ 1-10 ns,T
main
˜ 10-100
ns.
• Cac he A ccess Time : T
cac he
=T
tag-compare
+T
data-fetc h
, t ypically 1-2 cycles.
• T yp es of Cac he Misses :
– Compulsory: First access, N
compulsory
? program size.
– Capacit y: Cac he to o small, N
capacit y
?
w orking set
C
cac he
.
– Conflict: Mapping collision, N
conflict
?
1
asso ciat ivit y
.
Cac h e Mapping T ec hniques
• Direct Mapping :
– Line Mapping: Cac he Line = Memory Blo c k mod N
lines
.
– T ag Size: S
tag
= log
2
(
C main
S
line
)
-log
2
N
lines
, in bits.
– A ccess Time: T
access
=T
tag-compare
+T
data-fetc h
, fastest but high conflict misses.
• Set-Asso ciativ e Mapping :
– Set Mapping: Set = Memory Blo c k mod N
sets
, where N
sets
=
N
lines
k
, k is asso ciativit y .
– T ag Size: S
tag
= log
2
(
C main
S
line
)
-log
2
N
sets
.
– A ccess Time: T
access
=T
tag-compare
·k +T
data-fetc h
, balances sp eed and miss rate.
• F ully Asso ciativ e Mapping :
– No fixed mapping, an y blo c k in an y line.
– T ag Size: S
tag
= log
2
(
C main
S
line
)
.
– A ccess Time: T
access
=T
tag-compare
·N
lines
+T
data-fetc h
, slo w est but no conflict misses.
• Cac he Line Size : S
line
= 2
b
, where b is blo c k offset bits, t ypically 32-128 b ytes.
1
Page 2


Memory Hierarc h y: Cac he, Main Memory , and Secondary Stor-
age F orm ula Sheet
Memory Hierarc h y Basics
• Definition : Multi-lev el memory organization (Registers, Cac he, Main Memory , Secondary Stor-
age) to balance sp eed, cost, and capacit y .
• A ccess Time : T
access
, decreases with hierarc h y lev el (Registers: 1 ns, Cac he: 1-10 ns, Main
Memory: 10-100 ns, Secondary: 1-10 ms).
• Capacit y : C , increases with hierarc h y lev el (Registers: KB, Cac he: MB, Main Memory: GB,
Secondary: TB).
• Cost p er Bit : Decreases with hierarc h y lev el (C
reg
»C
cac he
>C
main
>C
secondary
).
• Lo calit y of Reference : T emp oral (reuse recen t data) and Spatial (access nearb y data).
Cac he Memory
• Definition : F ast, small memory b et w een CPU and main memory , stores frequen tly accessed data.
• Cac he Size : C
cac he
=N
lines
·S
line
, where N
lines
is n um b er of cac he lines, S
line
is line size (b ytes).
• Hit Ratio : h =
N
hit
N
hit
+N miss
, t ypically 0.9-0.99.
• Miss Ratio : m = 1-h .
• Effectiv e A ccess Time : T
eff
=h·T
cac he
+(1-h)·T
main
, whereT
cac he
˜ 1-10 ns,T
main
˜ 10-100
ns.
• Cac he A ccess Time : T
cac he
=T
tag-compare
+T
data-fetc h
, t ypically 1-2 cycles.
• T yp es of Cac he Misses :
– Compulsory: First access, N
compulsory
? program size.
– Capacit y: Cac he to o small, N
capacit y
?
w orking set
C
cac he
.
– Conflict: Mapping collision, N
conflict
?
1
asso ciat ivit y
.
Cac h e Mapping T ec hniques
• Direct Mapping :
– Line Mapping: Cac he Line = Memory Blo c k mod N
lines
.
– T ag Size: S
tag
= log
2
(
C main
S
line
)
-log
2
N
lines
, in bits.
– A ccess Time: T
access
=T
tag-compare
+T
data-fetc h
, fastest but high conflict misses.
• Set-Asso ciativ e Mapping :
– Set Mapping: Set = Memory Blo c k mod N
sets
, where N
sets
=
N
lines
k
, k is asso ciativit y .
– T ag Size: S
tag
= log
2
(
C main
S
line
)
-log
2
N
sets
.
– A ccess Time: T
access
=T
tag-compare
·k +T
data-fetc h
, balances sp eed and miss rate.
• F ully Asso ciativ e Mapping :
– No fixed mapping, an y blo c k in an y line.
– T ag Size: S
tag
= log
2
(
C main
S
line
)
.
– A ccess Time: T
access
=T
tag-compare
·N
lines
+T
data-fetc h
, slo w est but no conflict misses.
• Cac he Line Size : S
line
= 2
b
, where b is blo c k offset bits, t ypically 32-128 b ytes.
1
Cac h e Replacemen t Algorithms
• Least Recen tly Used (LR U) : Replace least recen tly accessed line, T
LR U
? k , optimal for
temp oral lo calit y .
• First In, First Out (FIF O) : Replace o ldest line, T
FIF O
˜O(1) , simpler but less effectiv e.
• Random : Replace random line, T
random
˜O(1) , lo w o v erhead but unpredictable.
• Replacemen t Ov erhead : T
replace
=T
select
+T
mem-write
, where T
mem-write
is write-bac k time.
• Miss P enalt y : T
miss
=T
main
+T
replace
, t ypically 10-100 cycles.
Main Memory
• T yp es :
– RAM (Random A ccess Memory): V olatile, includes SRAM (cac he, 1-2 ns) and DRAM (main
memory , 10-100 ns).
– R OM (Read-Only Memory): Non-v olatile, includes PR OM, EPR OM, EEPR OM.
• DRAM A ccess Time : T
DRAM
=T
ro w-access
+T
column-access
, t ypically 50-70 ns.
• Sync hronous DRAM (SDRAM) : Clo c k ed, B
SDRAM
= w·f
bus
, where w is bus width, f
bus
is
bus frequency .
• Async hronous DRAM : No clo c k, T
access
? ro w/column dela ys.
• Ram bus DRAM (RDRAM) : High bandwidth, B
RDRAM
»B
SDRAM
, narro w er bus.
• Memory Bandwidth : B =
w·f
bus
T access
, in b ytes/s.
• Memory Capacit y : C
main
= 2
a
·S
w ord
, where a is address bits, S
w ord
is w ord size (b ytes).
Secondary Storage
• Definition : Non-v olatile, large capacit y (TB), slo w access (ms), e.g., Hard Disk Driv e (HDD),
SSD.
• HDD A ccess Time : T
HDD
=T
seek
+T
rotational
+T
transfer
, w here:
– Seek Time: T
seek
˜ 5-10 ms.
– Rotational Latency: T
rotational
=
1
2· RPM/60
, e.g., 4 ms for 7200 RPM.
– T ransfer Time: T
transfer
=
S
data
B HDD
, where B
HDD
˜ 100-200 MB/s.
• HDD Bandwidth : B
HDD
=
S sector·N
sectors/trac k
· RPM
60
, t ypically 100-200 MB/s.
• Capacit y : C
HDD
=N
platters
·N
trac ks
·N
sectors
·S
sector
, e.g., 1-16 TB.
• SSD A ccess Time : T
SSD
˜ 0.1-0.2 ms, B
SSD
˜ 500-2000 MB/s.
Virtual Memory
• Definition : Abstracts ph ysical memory , uses disk as extension.
• P age Size : S
page
, t ypically 4 KB (2
12
b ytes).
• A ddress T ranslation : Ph ysical A ddr = P age T able[ VPN]+ Offset, where VPN is Virtual P age
Num b er.
• P age F ault P enalt y : T
page-fault
=T
HDD
+T
sw ap
, t ypically 10-20 ms.
• Effectiv e A ccess Time : T
eff
= (1-p)·T
main
+p·T
page-fault
, where p is page fault rate (e.g.,
10
-4
).
• TLB (T ranslation Lo okaside Buffer) : Cac he for page table en tries, T
TLB
˜ T
cac he
, hit rate
h
TLB
˜ 0.99 .
2
Page 3


Memory Hierarc h y: Cac he, Main Memory , and Secondary Stor-
age F orm ula Sheet
Memory Hierarc h y Basics
• Definition : Multi-lev el memory organization (Registers, Cac he, Main Memory , Secondary Stor-
age) to balance sp eed, cost, and capacit y .
• A ccess Time : T
access
, decreases with hierarc h y lev el (Registers: 1 ns, Cac he: 1-10 ns, Main
Memory: 10-100 ns, Secondary: 1-10 ms).
• Capacit y : C , increases with hierarc h y lev el (Registers: KB, Cac he: MB, Main Memory: GB,
Secondary: TB).
• Cost p er Bit : Decreases with hierarc h y lev el (C
reg
»C
cac he
>C
main
>C
secondary
).
• Lo calit y of Reference : T emp oral (reuse recen t data) and Spatial (access nearb y data).
Cac he Memory
• Definition : F ast, small memory b et w een CPU and main memory , stores frequen tly accessed data.
• Cac he Size : C
cac he
=N
lines
·S
line
, where N
lines
is n um b er of cac he lines, S
line
is line size (b ytes).
• Hit Ratio : h =
N
hit
N
hit
+N miss
, t ypically 0.9-0.99.
• Miss Ratio : m = 1-h .
• Effectiv e A ccess Time : T
eff
=h·T
cac he
+(1-h)·T
main
, whereT
cac he
˜ 1-10 ns,T
main
˜ 10-100
ns.
• Cac he A ccess Time : T
cac he
=T
tag-compare
+T
data-fetc h
, t ypically 1-2 cycles.
• T yp es of Cac he Misses :
– Compulsory: First access, N
compulsory
? program size.
– Capacit y: Cac he to o small, N
capacit y
?
w orking set
C
cac he
.
– Conflict: Mapping collision, N
conflict
?
1
asso ciat ivit y
.
Cac h e Mapping T ec hniques
• Direct Mapping :
– Line Mapping: Cac he Line = Memory Blo c k mod N
lines
.
– T ag Size: S
tag
= log
2
(
C main
S
line
)
-log
2
N
lines
, in bits.
– A ccess Time: T
access
=T
tag-compare
+T
data-fetc h
, fastest but high conflict misses.
• Set-Asso ciativ e Mapping :
– Set Mapping: Set = Memory Blo c k mod N
sets
, where N
sets
=
N
lines
k
, k is asso ciativit y .
– T ag Size: S
tag
= log
2
(
C main
S
line
)
-log
2
N
sets
.
– A ccess Time: T
access
=T
tag-compare
·k +T
data-fetc h
, balances sp eed and miss rate.
• F ully Asso ciativ e Mapping :
– No fixed mapping, an y blo c k in an y line.
– T ag Size: S
tag
= log
2
(
C main
S
line
)
.
– A ccess Time: T
access
=T
tag-compare
·N
lines
+T
data-fetc h
, slo w est but no conflict misses.
• Cac he Line Size : S
line
= 2
b
, where b is blo c k offset bits, t ypically 32-128 b ytes.
1
Cac h e Replacemen t Algorithms
• Least Recen tly Used (LR U) : Replace least recen tly accessed line, T
LR U
? k , optimal for
temp oral lo calit y .
• First In, First Out (FIF O) : Replace o ldest line, T
FIF O
˜O(1) , simpler but less effectiv e.
• Random : Replace random line, T
random
˜O(1) , lo w o v erhead but unpredictable.
• Replacemen t Ov erhead : T
replace
=T
select
+T
mem-write
, where T
mem-write
is write-bac k time.
• Miss P enalt y : T
miss
=T
main
+T
replace
, t ypically 10-100 cycles.
Main Memory
• T yp es :
– RAM (Random A ccess Memory): V olatile, includes SRAM (cac he, 1-2 ns) and DRAM (main
memory , 10-100 ns).
– R OM (Read-Only Memory): Non-v olatile, includes PR OM, EPR OM, EEPR OM.
• DRAM A ccess Time : T
DRAM
=T
ro w-access
+T
column-access
, t ypically 50-70 ns.
• Sync hronous DRAM (SDRAM) : Clo c k ed, B
SDRAM
= w·f
bus
, where w is bus width, f
bus
is
bus frequency .
• Async hronous DRAM : No clo c k, T
access
? ro w/column dela ys.
• Ram bus DRAM (RDRAM) : High bandwidth, B
RDRAM
»B
SDRAM
, narro w er bus.
• Memory Bandwidth : B =
w·f
bus
T access
, in b ytes/s.
• Memory Capacit y : C
main
= 2
a
·S
w ord
, where a is address bits, S
w ord
is w ord size (b ytes).
Secondary Storage
• Definition : Non-v olatile, large capacit y (TB), slo w access (ms), e.g., Hard Disk Driv e (HDD),
SSD.
• HDD A ccess Time : T
HDD
=T
seek
+T
rotational
+T
transfer
, w here:
– Seek Time: T
seek
˜ 5-10 ms.
– Rotational Latency: T
rotational
=
1
2· RPM/60
, e.g., 4 ms for 7200 RPM.
– T ransfer Time: T
transfer
=
S
data
B HDD
, where B
HDD
˜ 100-200 MB/s.
• HDD Bandwidth : B
HDD
=
S sector·N
sectors/trac k
· RPM
60
, t ypically 100-200 MB/s.
• Capacit y : C
HDD
=N
platters
·N
trac ks
·N
sectors
·S
sector
, e.g., 1-16 TB.
• SSD A ccess Time : T
SSD
˜ 0.1-0.2 ms, B
SSD
˜ 500-2000 MB/s.
Virtual Memory
• Definition : Abstracts ph ysical memory , uses disk as extension.
• P age Size : S
page
, t ypically 4 KB (2
12
b ytes).
• A ddress T ranslation : Ph ysical A ddr = P age T able[ VPN]+ Offset, where VPN is Virtual P age
Num b er.
• P age F ault P enalt y : T
page-fault
=T
HDD
+T
sw ap
, t ypically 10-20 ms.
• Effectiv e A ccess Time : T
eff
= (1-p)·T
main
+p·T
page-fault
, where p is page fault rate (e.g.,
10
-4
).
• TLB (T ranslation Lo okaside Buffer) : Cac he for page table en tries, T
TLB
˜ T
cac he
, hit rate
h
TLB
˜ 0.99 .
2
P e rformance Metrics
• Effectiv e Memory A ccess Time : T
eff
=h·T
cac he
+(1-h)·[h
main
·T
main
+(1-h
main
)·T
secondary
] .
• Memory Bandwidth : B
mem
=
S
data
T access
, higher for cac he (B
cac he
»B
main
»B
secondary
).
• Cac he Miss P enalt y : T
miss
=T
main
+T
replace
, impacts T
eff
.
• Amdahl’s La w : Sp eedupS =
1
(1-P)+
P
k
, whereP is memory-b ound fraction,k is memory sp eedup.
• Hit Ratio Impact :
?T
eff
?h
=T
cac he
-T
main
, higher h reduces T
eff
.
• Memory Latency : T
latency
=T
access
+T
transfer
, minimized b y cac he and TLB.
Applications and Concepts
– Cac he : Impro v es T
eff
, critical for CPU p erformance, optimized b y asso ciativit y and S
line
.
– Main Memory : DRAM for sp eed, R OM for firm w are, B
main
k ey for data-in tensiv e tasks.
– Secondary Storage : HDD/SSD for p ersisten t storage,T
HDD
limits I/O-b ound applications.
– Virtual Memory : Enables large address space, T
page-fault
mitigated b y TLB and page size.
– Multilev el Cac he : L1 (fastest, smalles t), L2, L3, T
eff
=
?
h
i
·T
i
+(1-
?
h
i
)·T
main
.
– Bus Organization : Single Bus (B
bus
?w·f ), Multiple Bus (B
total
?N
bus
), impactsT
transfer
.
3