Bài giảng Kiến trúc máy tính - Chương 5: Bộ nhớ đệm (Caches) - Tạ Kim Huệ

01 1 xx 
110 0 xx 
110 1 xx 
111 0 xx 
111 1 xx 
Set 
1 
0 
1 
Way 
0 
1 
Khối 1 từ, 2 bit thấp cuối dùng để xác định byte trong từ (từ 32b) 
Bộ đệm kết hợp 4 tập 
2 8 = 256 đường / tập, 4 tập (mỗi đường chứa 1 khối = 256 đường) 
50 
31 30 . . . 13 12 11 . . . 2 1 0 
Byte offset 
Data 
Tag 
V 
0 
1 
2 
. 
. 
. 
 253 
 254 
 255 
Data 
Tag 
V 
0 
1 
2 
. 
. 
. 
 253 
 254 
 255 
Data 
Tag 
V 
0 
1 
2 
. 
. 
. 
 253 
 254 
 255 
 Index 
Data 
Tag 
V 
0 
1 
2 
. 
. 
. 
 253 
 254 
 255 
8 
Index 
22 
Tag 
Hit 
Data 
32 
4x1 select 
Way 0 
Way 1 
Way 2 
Way 3 
Bố trí bộ đệm kết hợp toàn phần/ liên kết toàn phần 
Với kích thước bộ đệm cố định, tăng độ kết hợp theo hệ số 2 sẽ tăng số khối trong mỗi tập (tăng số đường) và giảm số tập – giảm kích thước trường index 1 bít và tăng kích thước trường tag 1 bit 
51 
Block offset 
Byte offset 
Index 
Tag 
Giảm độ kết hợp 
Kết hợp toàn phần 
(chỉ có một tập ) 
Tag gồm tất cả các bít trừ bit 
offset của khối và byte 
Ánh xạ trực tiếp 
(chỉ có một đường ) 
Tag nhỏ hơn, chỉ có 1 khối so sánh 
Tăng độ kết hợp 
Chọn tập 
So sánh thẻ 
Chọn từ trong khối 
Lợi ích của bộ đệm kết hợp toàn phần 
Lựa trọn giữa bộ đệm kết hợp và bộ đệm trực tiếp phụ thuộc vào tổn thất trượt và giá thành triển khai 
52 
Data from Hennessy & Patterson, Computer Architecture , 2003 
Lợi ích lớn nhất là khi chuyển từ bộ đệm trực tiếp sang kết hợp 2 đường (tỉ lệ trượt giảm 20%+) 
Kích thước các trường trong bộ đệm 
Số bit trong bộ đệm gồm bit cho dữ liệu và bit cho các trường thẻ 
Địa chỉ byte 32 bit 
Bộ đệm ánh xạ trực tiếp 2 n khối, n bits cho trường index 
Kích thước khối là 2 m từ (2 m+2 bytes), m bits cho trường block offset xác định vị trí từ trong khối; 2 bits cho trường byte offset xác định vị trí byte trong từ 
Kích thước trường tag sẽ là? 
Tổng số bít trong bộ đệm ánh xạ trực tiếp sẽ là 
2 n x (block size + tag field size + valid field size) 
Cần bao nhiêu bit cho bộ đệm ánh xạ trực tiếp kích thước 16KB dữ liệu, kích thước khối là 4 từ và dữ liệu được đánh địa chỉ bằng 32 bit? 
SET-HUST, 22/03/2011 
Chương 4. Bộ nhớ - Phân cấp bộ nhớ 
53 
Bộ nhớ đệm ngày nay 
• Intel Ivy Bridge (2012, 4‐core x86 ) 
– L1 Data: 	32kB	8‐way set‐associative 	64‐byte line 
– L1 Instruction: 	32kB 	8‐way set‐associative 	64‐byte line 
– L2 I&D: 	256kB 	8‐way set‐associative 	64‐byte line 
– L3 I&D: 	 8MB 	16‐way set‐associative 	64‐byte line 
• Qualcomm Krait (2012, 4‐core ARM ) 
– L0 Data: 	 4kB 	Direct‐mapped 	 64‐byte line 
– L0 Instruction: 	 4kB 	Direct‐mapped 	 64‐byte line 
– L1Data: 	16kB 	4‐way set‐associative 	64‐byte line 
– L1 Instruction: 	16kB 	4‐way set‐associative 	64‐byte line 
– L2 I&D: 	 1MB 	8‐way set‐associative 	64‐byte line 
“Filter” cache. Designed to save energy for small pieces of code 
Higher associativity for larger caches . 
Same block size across the whole hierarchy 
Dung lượng bộ nhớ đệm  điều gì xảy ra nếu bộ nhớ đệm đầy? 
Dung lượng caches 
• Điều gì xảy ra khi cache đầy? 
• Chính xách thay thế 
– Cần chọn một số dữ liệu trong caches để loại bỏ ( evict ) 
– Chọn những dữ liệu không sử dụng từ lâu nhất 
• Dẫn đến: 
– Direct‐mapped: chỉ loại đi một khối (bởi vì một khối tương ứng với một vị trí) 
– Set/Fully‐associative: 
• Chọn ngẫu nhiên một khối để loại bỏ 
• Chọn khối nào không sử dụng lâu nhất ( least recently used - LRU) để loại bỏ. 
Chính sách thay thế 
• Bốn chiến thuật chủ yếu chọn khối thay thế trong cache 
• Thay thế ngẫu nhiên 
– Để phân bố đồng đều việc thay thế, các khối cần thay thế trong cache được chọn ngẫu nhiên 
• Khối xưa nhất ( Least Recently Used ): hiệu quả trong các vị trí tạm thời 
– Thay thế khối không được dùng từ lâu nhất 
• Vào trước ra trước (FIFO) 
– Khối được đưa vào cache đầu tiên, nếu bị thay thế sẽ là khối bị thay thế trước nhất. 
• Khối có tần suất sử dụng ít nhất (LFU – Least Frequently Used): Khối trong cache được tham chiếu ít nhất 
Thay thế ngẫu nhiên 
• Chọn ngẫu nhiên một khối để loại bỏ 
• Ví dụ: 
– Black loop và blue loop 
– Khi chuyển đổi giữa hai vòng lặp dữ liệu luôn được sử dụng lại 
• Problem: Dữ liệu loại bỏ là dữ liệu cần sử dụng lại 
Thay thế khối xưa nhất Least recently used (LRU) replacement 
• Loại bỏ khối không được sử dụng lâu nhất 
• Ví dụ : 
– Black loop và blue loop 
– Khi chuyển đổi giữa các vòng lặp, cần tất cả các lệnh trong vòng lặp mầu xanh ở lại trong cache 
Ghi vào bộ nhớ đệm  Chiến thuật ghi? 
Ghi vào bộ nhớ đệm 
• Khi đọc lệnh hoặc dữ liệu: đặt vào cache 
• Ghi như thế nào? 
• Write‐through (ghi đồng thời) 
– Thông tin được ghi đồng thời vào khối của cache và khối của bộ nhớ trong 
– Đơn giản, nhưng chậm (phải đợi ghi vào DRAM)	 
• Write‐back (ghi lại) 
– Chỉ ghi dữ liệu vào cache 
– Nếu khối không có trong cache, cần nạp lại vào cache 
– Cần đánh dấu lại nếu dữ liệu trong cache được cập nhật 
– Khi một khối bị thay thế, khối này sẽ được ghi lại vào bộ nhớ trong. 
Write‐through 
• Luôn ghi vào DRAM 
• Nếu dữ liệu ở trong cache, khi đó ghi đồng thời vào cache. 
Q: Ghi chậm hơn vì sao? 
Phụ thuộc vào vị trí của dữ liệu trong cache. 
Châm do ghi vào DRAM 
Chậm do ghi vào DRAM và cache 
A: Chậm do ghi vào DRAM 
Ghi vào DRAM ở mọi thời điểm . 
Write‐through with allocate‐on‐write 
• Luôn ghi vào DRAM 
• Nếu dữ liệu trong cache, ghi đồng thời vào cache 
• Allocate‐on‐write 
– Nếu khối dữ liệu không có trong cache, tải khối về cache 
Q: Tốt hơn tại sao? 
It isn’t 
Faster to read and write than just write 
Subsequent reads will hit in the cache 
A: Subsequent reads will hit in the cache 
Thường hay truy cập dữ liệu và ghi lại, chỉ ghi một phần của khối như một từ hoặc một byte, do vậy tải vào cache sẽ nhanh hơn. 
Write‐back 
• Luôn ghi vào cache 
• Nếu khối dữ liệu không có trong cache, tải vào cache 
• Note: cache và DRAM là không như nhau! 
• Khi chúng ta loại bỏ một dòng cần phải biết khác với dữ liệu ghi từ DRAM như thế nào? 
Ghi vào bộ nhớ đệm 
• Write‐through đơn giản, nhưng chậm 
– Phải đợi ghi đồng thời với DRAM trong mọi lần ghi 
• Write ‐back phức tạp hơn, nhưng nhanh 
– Phải đánh dấu dữ liệu ‘bẩn’ (dirty data) trong cache và ghi lại vào bộ nhớ trong nếu nó bị loại bỏ 
– Ghi nhanh hơn 
• Allocate‐on‐write tải dữ liệu vào cache khi ghi 
– no allocate : chỉ tải dữ liệu vào cache khi đọc. 
• Ghi vào cache ngày nay là kiểu write‐back 
– Intel’s new Xeon Phi có mức L2 write‐through cache 
Hiệu năng bộ nhớ đệm 
Tỉ lệ trượt vs Kích thước khối vs Kích thước bộ đệm 
SET-HUST, 22/03/2011 
67 
Chương 4. Bộ nhớ - Phân cấp bộ nhớ 
Tỉ lệ trượt tăng khi kích thước khối trở nên đáng kể so với kích thước bộ đệm vì với cũng kích thước bộ đệm số khối có thể lưu giữ giảm (tăng trượt do dung lượng ) 
Tăng kích thước khối làm tổn thất trượt tăng 
Xử lý trúng bộ đệm 
Đọc trúng (I $ và D $) 
Đó là điều ta cần! 
Ghi trúng (chỉ với D$) 
yêu cầu bộ đệm và bộ nhớ phải thống nhất (allocate) 
luôn ghi dữ liệu vào cả khối bộ đệm và vào bộ nhớ ở mức kế tiếp ( ghi xuyên - write-through ) 
ghi với tốc độ của bộ nhớ ở mức kế tiếp – chậm hơn! – sử dụng bộ đệm ghi (write buffer) và chỉ dừng khi bộ đệm ghi đầy 
cho phép bộ đệm và bộ nhớ không thống nhất 
chỉ ghi dữ liệu vào bộ đệm ( ghi lại write-back khối bộ đệm vào bộ nhớ ở mức kế tiếp khi khối bộ đệm bị lấy lại) 
cần 1 bít bẩn (dirty) cho mỗi khối bộ đệm để chỉ ra là khối đó cần được ghi lại vào bộ nhớ khi nó bị lấy lại – có thể dùng bộ đệm ghi để tăng tốc việc ghi lại các khối bộ đệm bẩn 
68 
Xử lý trượt bộ đệm (Khối kích thước 1 từ) 
Đọc trượt (I $ và D$): mất thời gian read_miss_penalty 
dừng đường ống, nạp khối từ bộ nhớ ở mức kế tiếp, đưa vào bộ đệm và gửi từ được yêu cầu tới bộ xử lý, tiếp tục đường ống 
Ghi trượt (D $) mất thời gian write_miss_penalty và write_buffer_stalls 
Cấp phát và ghi – Đầu tiên đọc khối từ bộ nhớ và ghi từ vào khối 
or 
Không cấp phát và ghi – bỏ qua việc ghi vào bộ đệm; ghi từ vào bộ đệm ghi (tức là sẽ ghi vào bộ nhớ ở mức kết tiếp), không cần dừng nếu bộ đệm ghi không đầy 
SET-HUST, 22/03/2011 
Chương 4. Bộ nhớ - Phân cấp bộ nhớ 
69 
Đo hiệu năng bộ đệm 
Giả sử thời gian truy cập bộ nhớ khi trúng bộ đệm được bao gồm trong 1 chu kỳ thực hiện thông thường của CPU thì: 
70 
CPI stall 
Số chu kỳ MemStallC là tổn thất trượt là tổng của read-stalls và write-stalls 
Read-stall cycles = reads/program × read miss rate × read miss penalty 
Write-stall cycles = (writes/program × write miss rate 	 × write miss penalty) + write buffer stalls 
Với bộ đệm ghi xuyên, ta có công thức đơn giản 
Memory-stall cycles = accesses/program × miss rate × miss penalty 
Ảnh hưởng của hiệu năng bộ đệm 
Tổn thất tương đối của bộ đệm sẽ tăng khi hiệu năng bộ xử lý tăng (tăng tốc độ đồng hồ và/hoặc giảm CPI) 
Tốc độ bộ nhớ không được cải thiện nhanh như tốc độ bộ xử lý. Tổn thất trượt dùng để tính CPI stall được đo theo số chu kỳ bộ xử lý cần thiết để xử lý trượt 
CPI ideal càng thấp thì ảnh hưởng của dừng do trượt càng lớn 
Bộ xử lý với CPI ideal = 2, tổn thất trượt là 100, 36% là lệnh load/store, tỉ lệ trượt bộ nhớ I$ là 2 % và bộ nhớ D$ là 4% 
Nếu CPI ideal giảm xuống 1 ? 0.5? 0.25 ? 
Nếu tỉ lệ trượt bộ nhớ D$ tăng lên 1%? 2%? 
Nếu tốc độ đồng hồ CPU tăng gấp 2 (tổn hao trượt tăng gấp 2)? 
SET-HUST, 22/03/2011 
Chương 4. Bộ nhớ - Phân cấp bộ nhớ 
71 
Ảnh hưởng của hiệu năng bộ đệm 
Tổn thất tương đối của bộ đệm sẽ tăng khi hiệu năng bộ xử lý tăng (tăng tốc độ đồng hồ và/hoặc giảm CPI) 
Tốc độ bộ nhớ không được cải thiện nhanh như tốc độ bộ xử lý. Tổn thất trượt dùng để tính CPI stall được đo theo số chu kỳ bộ xử lý cần thiết để xử lý trượt 
CPI ideal càng thấp thì ảnh hưởng của dừng do trượt càng lớn 
Bộ xử lý với CPI ideal = 2, tổn thất trượt là 100, 36% là lệnh load/store, tỉ lệ trượt bộ nhớ I$ là 2 % và bộ nhớ D$ là 4 % 
MemStallC = 2% × 100 + 36% × 4% × 100 = 3.44 
 CPI stalls = 2 + 3.44 = 5.44 	 gấp 2 lần CPI ideal ! 
Nếu CPI ideal giảm xuống 1 ? 0.5? 0.25 ? 
Nếu tỉ lệ trượt bộ nhớ D$ tăng lên 1%? 2%? 
Nếu tốc độ đồng hồ CPU tăng gấp 2 (tổn hao trượt tăng gấp 2)? 
SET-HUST, 22/03/2011 
Chương 4. Bộ nhớ - Phân cấp bộ nhớ 
72 
Nguyên nhân trượt bộ đệm 
Không tránh được: 
Lần đầu truy cập khối 
Giải pháp: tăng kích thước khối (làm tăng tổn thất trượt, khối rất lớn làm tăng tỉ lệ trượt) 
Dung lượng : 
Bộ đệm không thể chứa toàn bộ các khối truy cập bởi chương trình 
Giải pháp: tăng kích thước bộ đệm (có thể làm tăng thời gian truy cập) 
Xung đột: 
Nhiều vị trí bộ nhớ cùng được ánh xạ vào 1 vị trí bộ đệm 
Giải pháp 1: tăng kích thước bộ đệm 
Giải pháp 2: tăng độ kết hợp trong bộ đệm (có thể tăng thời gian truy cập) 
SET-HUST, 22/03/2011 
Chương 4. Bộ nhớ - Phân cấp bộ nhớ 
73 
Tỷ số trượt bộ đệm 
Miss ratio = % of cache misses = (# cache misses / # memory accesses) 
Tỷ lệ trượt (%) = (số lần trượt/số lần truy nhập) 
Q: Hiệu năng thay đổi thế nào khi tỷ số trượt bộ đệm giảm từ 10.5% đến 3.5 %? 
Slower 
Stays the same 
Faster 
A: Faster 
Các ứng dụng có thể chạy nhanh hơn, nhưng không thể biết là nhanh ơn bao nhiêu. Tỷ lệ Trúng cache lớn hơn rất nhiều so với trượt. 
Average Memory Access Time (AMAT - Thời gian truy cập bộ nhớ trung bình ) 
• Số chu kỳ trung bình cho một truy cập bộ nhớ 
= (hit time) + (miss %)*(miss time + miss penalty) 
Hit time 	= 1 Hit (1cycle) 
Miss time 	= 1 Miss (1 cycle) 
Miss penalty 	= 3 Penalty 
% miss = 2/6 = 33% 
AMAT = (1) + (33%)*(1 + 3) = 2.3 cycles per access 
Miss Penalty là thời gian sau khi tìm kiếm trong cache . 
Ví dụ: AMAT 
Machine 1 
– 100 truy nhập DRAM 
– 1 chu kỳ truy nhập cache (hit or miss ) 
• Tính AMAT cho lbm ? 
– cache có dung lượng 256kB ? 
• 6% miss ratio 
• (1 ) + ( 6%)*(1+100 ) = 7.06 cycles per memory access 
– cache có dung lượng 8MB ? 
• 3% miss ratio 
• (1 ) + ( 3%)*(1+100 ) = 4.03 cycles per memory access 
Machine 2 
– 100 cycles to DRAM 
– 2 cycle cache access time (hit or miss ) 
• Tính AMAT cho bzip2 ? 
– 256kB cache ? 
• 1.5% miss ratio 
• (2 ) + ( 1.5%)*(2+100 ) = 3.53 
Q: Tại sao bzip2’s AMAT với 256kB cache gần giống với lbm’s với 8MB ? 
Slower cache 
Different miss ratios 
Different applications 
A: Slower cache 
Cache mất 2 cycles cho Machine 2 và chỉ một chu kỳ cho Machine 1. Diều này làm ảnh hưởng đến AMAT.Ứng dụng khác nhau sẽ thấy 8MB cache có 3% miss ratio đối với lbm trong khi bzip2 có 1.5% miss ratio với cache 256kB 
Performance impacts of memory access time 
• Ảnh thưởng của cace đến hiệu năng như thế nào(CPI )? 
– 100 chu kỳ trừng phạt trượt bộ đệm 
– 3% tỷ lệ trượt 
– 1.33 lần truy nhập bộ nhớ trên một lệnh (1 for instruction 33% for data ) 
– CPI = 1.0 khi thực thi thông thường (lý tưởng) 
• Hiệu năng thay đổi thế nào? 
– CPI = CPI Execution + Memory stall cycles per instruction = 1.0 + 1.33*0.03*100 = 4.99 
– Phân cấp bộ nhớ này làm bộ xử lý chạy chậm hơn 5 lần! 
• Caches là rất quan trọng! Caches là quan trọng nhất để tăng hiệu năng. 
How much does cache matter ? 
Phân tách lệnh và dữ liệu bộ nhớ đệm 
• Cần nạp lệnh( IF ) và dữ liệu ( MEM ) cùng một thời điểm 
• Cần 2 loại cache: 
– Instruction cache (just instructions ) 
– Data cache (just data) 
• AMAT khi phân chia cache: 
– AMAT : (% lệnh truy cập) *( hit time + (tỷ lệ trượt bộ đệm lệnh)*(miss time + miss penalty)) + (% dữ liệu truy cập) *( hit time + (tỷ lệ trượt bộ đệm dữ liệu) *( miss time + miss penalty)) 
• Ví dụ: 
– Thời gian truy nhập cache là 1 cycle (hit or miss) và thời gian truy nhập bộ nhớ 100 cycle 
– I‐cache: 1% miss ratio, D‐cache: 5% miss ratio 
– 33% là lệnh loads/stores → 25% truy cập dữ liệu / 75% truy cập lệnh 
– (75%)*( 1 + ( 1%)*(1+100 )) + ( 25%)*( 1 + ( 5%)*(1+100 )) = 1.5 + 1.5 = 3.0 
AMD/Intel caches 
Heterogeneous processor caches 
Memory hierarchy 
• We want big and fast 
– Build a hierarchy where we keep the most important data in fast memory 
– Other data goes in slow memory 
– If we move the data correctly we provide the illusion of fast and big 
• Registers 3 accesses/cycle 32­‐64 
• Cache 1­‐10 cycles 8kB­‐256kB 
• Cache 40 cycles 4­‐ 20MB 
• DRAM 200 cycles 4­‐ 16GB 
• Flash 1000+ cycles 64­‐ 512GB 
• Hard Disk 1M+ cycles 2 ­‐ 4TB 
Summary: how to make the memory hierarchy work 
• 3 different cache types 
– Fully‐associative : Have to search all blocks , but very flexible 
– Direct‐mapped : Only one place for each block , no flexibility 
– Set‐associative : Only have to search one set for each block , flexible 
• We can adjust the block (line) size to reduce the overhead of tags 
• We figure out where data goes in a cache by looking at the address 
– Last 2 bits are the byte in the word 
– Next N bits are the word in the cache block 
– Remaining bits are for the tag 
• We have different write policies 
– Write‐through : slow , simple 
– Write‐back : fast (keeps the data just in the cache), more complex 
• Performance effects are due to the average memory access time