Computer Architecture
Super Computing Lab.
本资料来源
Computer Architecture
Super Computing Lab.
Lecture 10:
Memory Hierarchy: Reducing Hit
Time, Main Memory, & Examples
Spring 2010
Super Computing Lab.
Supercomputing Lab. CA10-L10-3
Review: Reducing Misses
• 3 Cs: Compulsory, Capacity, Conflict Misses
• Reducing Miss Rate
1. Reduce Misses via Larger Block Size
2. Reduce Misses via Higher Associativity
3. Reducing Misses via Victim Cache
4. Reducing Misses via Pseudo-Associativity
5. Reducing Misses by HW Prefetching Instr, Data
6. Reducing Misses by SW Prefetching Data
7. Reducing Misses by Compiler Optimizations
• Remember danger of concentrating on just one
parameter when evaluating performance
Supercomputing Lab. CA10-L10-4
Reducing Miss Penalty Summary
• Five techniques
– Read priority over write on miss
– Subblock placement
– Early Restart and Critical Word First on miss
– Non-blocking Caches (Hit under Miss, Miss under Miss)
– Second Level Cache
• Can be applied recursively to Multilevel Caches
– Danger is that time to DRAM will grow with multiple levels in
between
– First attempts at L2 caches can make things worse, since increased
worst case is worse
Supercomputing Lab. CA10-L10-5
Review: Improving Cache
Performance
1. Reduce the miss rate,
2. Reduce the miss penalty, or
3. Reduce the time to hit in the cache
- hit time: read tag + compare
Supercomputing Lab. CA10-L10-6
1. Fast Hit times
via Small and Simple Caches
• Why Alpha 21164 has 8KB Instruction and 8KB
data cache + 96KB second level cache?
– Small data cache (faster) and clock rate (on-chip)
• Direct Mapped, on chip
– Advantage: overlap tag check & data transfer
Supercomputing Lab. CA10-L10-7
1. Fast Hit times via
Small and Simple Caches
• Index tag memory and then compare takes time
• Small cache can help hit time since smaller memory
takes less time to index
– ., L1 caches same size for 3 generations of AMD
microprocessors: K6, Athlon, and Opteron
– Also L2 cache small enough to fit on chip with the processor
avoids time penalty of going off chip
• Simple direct mapping
– Can overlap tag check with data transmission since no choice
• Access time estimate for 90 nm using CACTI model
– Median ratios of access time relative to the direct-mapped
caches are , , and for 2-way, 4-way, and 8-way
caches
Supercomputing Lab. CA10-L10-8
2. Fast hits by Avoiding Address
Translation
• Send virtual address to cache: Called Virtually Addressed Cache or just
Virtual Cache vs. Physical Cache
– Every time process is switched logically must flush the cache; otherwise get
false hits
» Cost is time to flush + “compulsory” misses from empty cache
– Dealing with aliases (sometimes called synonyms);
Two different virtual addresses map to same physical address
– I/O must interact with cache, so need virtual address
• Solution to aliases
– HW guarantees that every cache block has unique physical address
– SW guarantee : lower n bits must have same address;
as long as covers index field & direct mapped, they must be unique;
called page coloring
• Solution to cache flush
– Add process identifier tag that identifies process as well as address within
process: cannot get a hit if wrong process
Supercomputing Lab. CA10-L10-9
Virtually Addressed Caches
CPU
TB
$
MEM
VA
PA
PA
Conventional
Organization
CPU
$
TB
MEM
VA
VA
PA
Virtually Addressed Cache
Translate only on miss
Synonym Problem
CPU
$ TB
MEM
VA
PA
Tags
PA
Overlap $ access
with VA translation:
requires $ index to
remain invariant
across translation
VA
Tags
L2 $
Supercomputing Lab. CA10-L10-10
2’. Fast Cache Hits by Avoiding Translation: Index with
Physical Portion of Address
• If index is physical part of address, can start tag
access in parallel with translation so that can
compare to physical tag
• Limits cache to page size: what if want bigger
caches and uses same trick?
– Higher associativity moves barrier to right
– Page coloring
Page Address Page Offset
Address Tag Index Block Offset
31 12 11 0
Supercomputing Lab. CA10-L10-11
• Pipeline Tag Check and Update Cache as separate stages;
current write tag check & previous write cache update
• Only STORES in the pipeline; empty during a miss
Store r2, (r1) Check r1
Add --
Sub --
Store r4, (r3) M[r1]<-r2&
check r3
• In shade is Delayed Write Buffer? must be checked on reads;
either complete write or read from buffer
3. Fast Hit Times Via Pipelined Writes
write
buffer
CPU
in out
DRAM
(or lower mem)
Supercomputing Lab. CA10-L10-12
4. Fast Writes on Misses Via Small
Subblocks
• If most writes are 1 word, subblock size is 1 word, & write
through then always write subblock & tag immediately
– Tag match and valid bit already set: Writing the block was proper, &
nothing lost by setting valid bit on again.
– Tag match and valid bit not set: The tag match means that this is the
proper block; writing the data into the subblock makes it appropriate to
turn the valid bit on.
– Tag mismatch: This is a miss and will modify the data portion of the
block. Since write-through cache, no harm was done; memory still has an
up-to-date copy of the old value. Only the tag to the address of the write
and the valid bits of the other subblock need be changed
• Doesn’t work with write back due to last case
Supercomputing Lab. CA10-L10-13
5. Fast Hit times via Trace Cache
(Pentium 4 only; and last time?)
• Find more instruction level parallelism?
How avoid translation from x86 to microops?
• Trace cache in Pentium 4
1. Dynamic traces of the executed instructions vs. static sequences
of instructions as determined by layout in memory
– Built-in branch predictor
2. Cache the micro-ops vs. x86 instructions
– Decode/translate from x86 to micro-ops on trace cache miss
+ 1. better utilize long blocks (don’t exit in middle of
block, don’t enter at label in middle of block)
- 1. complicated address mapping since addresses no
longer aligned to power-of-2 multiples of word size
- 1. instructions may appear multiple times in multiple
dynamic traces due to different branch outcomes
Supercomputing Lab. CA10-L10-14
6: Increasing Cache Bandwidth by
Pipelining
• Pipeline cache access to maintain bandwidth, but
higher latency
• Instruction cache access pipeline stages:
1: Pentium
2: Pentium Pro through Pentium III
4: Pentium 4
- greater penalty on mispredicted branches
- more clock cycles between the issue of the load
and the use of the data
Supercomputing Lab. CA10-L10-15
7: Increasing Cache Bandwidth
via Multiple Banks
• Rather than treat the cache as a single monolithic
block, divide into independent banks that can support
simultaneous accesses
– .,T1 (“Niagara”) L2 has 4 banks
• Banking works best when accesses naturally spread
themselves across banks mapping of addresses to
banks affects behavior of memory system
• Simple mapping that works well is “sequential
interleaving”
– Spread block addresses sequentially across banks
– E,g, if there 4 banks, Bank 0 has all blocks whose address
modulo 4 is 0; bank 1 has all blocks whose address modulo 4
is 1; …
Supercomputing Lab. CA10-L10-16
Cache Optimization Summary
Technique MR MP HT Complexity
Larger Block Size + - 0
Higher Associativity + - 1
Victim Caches + 2
Pseudo-Associative Caches + 2
HW Prefetching of Instr/Data + 2
Compiler Controlled Prefetching + 3
Compiler Reduce Misses + 0
Priority to Read Misses + 1
Subblock Placement + + 1
Early Restart & Critical Word 1st + 2
Non-Blocking Caches + 3
Second Level Caches + 2
Small & Simple Caches - + 0
Avoiding Address Translation + 2
Pipelining Writes + 1
m
is
s
ra
te
hi
t t
im
e
m
is
s
pe
na
lty
Supercomputing Lab. CA10-L10-17
Main Memory Background
• Performance of Main Memory:
– Latency: Cache Miss Penalty
» Access Time: time between request and word arrives
» Cycle Time: min time between requests to memory
– Bandwidth: I/O & Large Block Miss Penalty (L2)
• Main Memory is DRAM: Dynamic Random Access Memory
– Dynamic since needs to be refreshed periodically (8 ms, 1% time)
– Addresses divided into 2 halves (Memory as a 2D matrix):
» RAS or Row Access Strobe
» CAS or Column Access Strobe
• Cache uses SRAM: Static Random Access Memory
– No refresh (6 transistors/bit vs. 1 transistor /bit, area is 10X)
– Address not divided: Full addreess
• Size: DRAM/SRAM : 4-8,
Cost/Cycle time: SRAM/DRAM : 8-16
Supercomputing Lab. CA10-L10-18
DRAM logical organization
(4 Mbit)
• Square root of bits per RAS/CAS
Column Decoder
Sense Amps & I/O
Memory Array
(2,048 x 2,048)
A0…A1 0
11 D
Q
Word Line Storage Cell
Supercomputing Lab. CA10-L10-19
DRAM physical organization (4Mbit)
Block
Row Dec.
9 : 512
Row
Block
Row Dec.
9 : 512
Column Addr ess
Block
Row Dec.
9 : 512
Block
Row Dec.
9 : 512
Block 0 Block 3
I/O
I/O
I/O
I/O
I/O
I/O
I/O
I/O
D
Q
Addr ess
2
8 I/Os
8 I/Os
Supercomputing Lab. CA10-L10-20
4 Key DRAM Timing Parameters
• tRAC: minimum time from RAS line falling to the
valid data output.
– Quoted as the speed of a DRAM when buy
– A typical 4Mb DRAM tRAC = 60 ns
– Speed of DRAM since on purchase sheet?
• tRC: minimum time from the start of one row
access to the start of the next.
– tRC = 110 ns for a 4Mbit DRAM with a tRAC of 60 ns
• tCAC: minimum time from CAS line falling to valid
data output.
– 15 ns for a 4Mbit DRAM with a tRAC of 60 ns
• tPC: minimum time from the start of one column
access to the start of the next.
– 35 ns for a 4Mbit DRAM with a tRAC of 60 ns
Supercomputing Lab. CA10-L10-21
A
D
OE_L
256K x 8
DRAM9 8
WE_LCAS_LRAS_L
OE_L
A Row Address
WE_L
Junk
Read Access
Time
Output Enable
Delay
CAS_L
RAS_L
Col Address Row Address JunkCol Address
D High Z Data Out
DRAM Read Cycle Time
Early Read Cycle: OE_L asserted before CAS_L Late Read Cycle: OE_L asserted after CAS_L
• Every DRAM access begins at:
– The assertion of the RAS_L
– 2 ways to read:
early or late v. CAS
Junk Data Out High Z
DRAM Read Timing
Supercomputing Lab. CA10-L10-22
DRAM Performance
• A 60 ns (tRAC) DRAM can
– perform a row access only every 110 ns (tRC)
– perform column access (tCAC) in 15 ns, but time between
column accesses is at least 35 ns (tPC).
» In practice, external address delays and turning around
buses make it 40 to 50 ns
• These times do not include the time to drive the
addresses off the microprocessor nor the
memory controller overhead!
Supercomputing Lab. CA10-L10-23
DRAM History
• DRAMs: capacity +60%/yr, cost -30%/yr
– cells/area, die size in 3 years
• ‘98 DRAM fab line costs $2B
– DRAM only: density, leakage v. speed
• Rely on increasing no. of computers & memory per computer
(60% market)
– SIMM or DIMM is replaceable unit
=> computers use any generation DRAM
• Commodity, second source industry
=> high volume, low profit, conservative
– Little organization innovation in 20 years
• Order of importance: 1) Cost/bit 2) Capacity
– First RAMBUS: 10X BW, +30% cost => little impact
Supercomputing Lab. CA10-L10-24
DRAM Future: 1 Gbit DRAM
Mitsubishi Samsung
Blocks 512 x 2 Mbit 1024 x 1 Mbit
Clock 200 MHz 250 MHz
Data Pins 64 16
Die Size 24 x 24 mm 31 x 21 mm
Sizes will be much smaller in production
Metal Layers 3 4
Technology micron micron
Supercomputing Lab. CA10-L10-25
Fast Memory Systems: DRAM specific
• Multiple CAS accesses: several names (page mode)
– Extended Data Out (EDO): 30% faster in page mode
• New DRAMs to address gap;
what will they cost, will they survive?
– RAMBUS: startup company; reinvent DRAM interface
» Each Chip a module vs. slice of memory
» Short bus between CPU and chips
» Does own refresh
» Variable amount of data returned
» 1 byte / 2 ns (500 MB/s per chip)
» 20% increase in DRAM area
– Synchronous DRAM: 2 banks on chip, a clock signal to DRAM,
transfer synchronous to system clock (66 - 150 MHz)
– Intel claims RAMBUS Direct (16 b wide) is future PC memory?
» Possibly not true! Intel to drop RAMBUS?
• Niche memory or main memory?
– ., Video RAM for frame buffers, DRAM + fast serial output
Supercomputing Lab. CA10-L10-26
Main Memory Performance
• Simple:
– CPU, Cache, Bus, Memory
same width
(32 or 64 bits)
• Wide:
– CPU/Mux 1 word;
Mux/Cache, Bus, Memory N
words (Alpha: 64 bits & 256
bits; UtraSPARC 512)
• Interleaved:
– CPU, Cache, Bus 1 word:
Memory N Modules
(4 Modules); example is
word interleaved
Supercomputing Lab. CA10-L10-27
Interleaving
Access Pattern without Interleaving:
Start Access for D1
CPU Memory
Start Access for D2
D1 available
Access Pattern with 4-way Interleaving:
A
cc
es
s
B
an
k
0
Access Bank 1
Access Bank 2
Access Bank 3
CPU
Memory
Bank 1
Memory
Bank 0
Memory
Bank 3
Memory
Bank 2
Supercomputing Lab. CA10-L10-28
Main Memory Performance
• Timing model (word size is 32 bits)
– 1 to send address,
– 6 access time, 1 to send data
– Cache Block is 4 words
• Simple . = 4 x (1+6+1) = 32
• Wide . = 1 + 6 + 1 = 8
• Interleaved . = 1 + 6 + 4x1 = 11
Supercomputing Lab. CA10-L10-29
Independent Memory Banks
• Memory banks for independent accesses
vs. faster sequential accesses
– Multiprocessor
– I/O
– CPU with Hit under n Misses, Non-blocking Cache
• Superbank: all memory active on one block transfer (or
Bank)
• Bank: portion within a superbank that is word
interleaved (or Subbank)
Superbank Bank
Supercomputing Lab. CA10-L10-30
Independent Memory Banks
• How many banks?
number banks >=number clocks to access word in bank
– For sequential accesses, otherwise will return to original bank
before it has next word ready
– (like in vector case)
• Increasing DRAM => fewer chips => harder to have banks
Supercomputing Lab. CA10-L10-31
DRAMs per PC over Time
M
in
im
um
M
em
or
y
S
iz
e
DRAM Generation
86 89 92 96 99 02
1 Mb 4 Mb 16 Mb 64 Mb 256 Mb 1 Gb
4 MB
8 MB
16 MB
32 MB
64 MB
128 MB
256 MB
32 8
16 4
8 2
4 1
8 2
4 1
8 2
Supercomputing Lab. CA10-L10-32
DRAM Latency >> BW
• More App Bandwidth =>
Cache misses
=> DRAM RAS/CAS
• Application BW =>
Lower DRAM Latency
• RAMBUS, Synch DRAM
increase BW but higher
latency
• EDO DRAM < 5% in PC
D
R
A
M
D
R
A
M
D
R
A
M
D
R
A
M
Bus
I$ D$
Proc
L2$
Supercomputing Lab. CA10-L10-33
Potential : DRAM Crossroads?
• After 20 years of 4X every 3 years, running into
wall? (64Mb - 1 Gb)
• How can keep $1B fab lines full if buy fewer
DRAMs per computer?
• Cost/bit -0%/yr if stop 4X/3 yr?
• What will happen to $40B/yr DRAM industry?
Supercomputing Lab. CA10-L10-34
Main Memory Summary
• Wider Memory
• Interleaved Memory: for sequential or independent
accesses
• Avoiding bank conflicts: SW & HW
• DRAM specific optimizations: page mode & Specialty
DRAM
Supercomputing Lab. CA10-L10-35
Cache Cross Cutting Issues
• Superscalar CPU & Number Cache Ports must
match: number memory accesses/cycle?
• Speculative Execution and non-faulting option on
memory/TLB
• Parallel Execution vs. Cache locality
– Want far separation to find independent operations vs.
want reuse of data accesses to avoid misses
• I/O and consistency of data between cache and
memory
– Caches => multiple copies of data
– Consistency by HW or by SW?
– Where connect I/O to computer?
Supercomputing Lab. CA10-L10-36
Alpha 21064
• Separate Instr & Data TLB
& Caches
• TLBs fully associative
• TLB updates in SW
(“Priv Arch Libr”)
• Caches 8KB direct
mapped, write thru
• Critical 8 bytes first
• Prefetch instr. stream
buffer
• 2 MB L2 cache, direct
mapped, WB (off-chip)
• 256 bit path to main
memory, 4 x 64-bit
modules
• Victim Buffer: to give read
priority over write
• 4 entry write buffer
between D$ & L2$
Stream
Buffer
Write
Buffer
Victim Buffer
Instr Data
Supercomputing Lab. CA10-L10-37
Alpha Memory Performance: Miss
Rates of SPEC92
8K
8K
2M
I$ miss = 2%
D$ miss = 13%
L2 miss = %
I$ miss = 1%
D$ miss = 21%
L2 miss = %
I$ miss = 6%
D$ miss = 32%
L2 miss = 10%
Supercomputing Lab. CA10-L10-38
Alpha CPI Components
• Instruction stall: branch mispredict (green);
• Data cache (blue); Instruction cache (yellow); L2$ (pink)
Other: compute + reg conflicts, structural conflicts
Supercomputing Lab. CA10-L10-39
Pitfall: Predicting Cache Performance from
Different Prog. (ISA, compiler, ...)
• 4KB Data cache miss
rate 8%,12%, or 28%?
• 1KB Instr cache miss
rate 0%,3%,or 10%?
• Alpha vs. MIPS
for 8KB Data $:
17% vs. 10%
• Why 2X Alpha v. MIPS?
D$, Tom
D$, gcc
D$, esp
I$, gcc
I$, esp
I$, Tom
Supercomputing Lab. CA10-L10-40
Pitfall: Simulating Too Small an
Address Trace
I$ = 4 KB, B=16B
D$ = 4 KB, B=16B
L2 = 512 KB, B=128B
MP = 12, 200
