Bài giảng Kiến trúc máy tính - Chương 4: Bộ nhớ Cache - Nguyễn Thị Phương

ng lượng thấp hơn bộ nhớ chính
 • Bộ nhớ cache chứa bản sao của một phần của bộ nhớ chính. 
Nguyên lý
• BN chính gồm 풏 từ nhớ (word) được đánh địa chỉ: n bit địa chỉ
• BN chính được chia thành các khối (block) có kích thước cố định: K 
 word.
 2푛
 Như vậy, BN chính có = 푴 khối
 퐾
• BN cache được chia thành các đường (line), mỗi đường có K word.
• Mỗi block của BN chính được ánh xạ vào một line của Cache
• Khi bộ xử lý muốn đọc một word của bộ nhớ nó sẽ kiểm tra xem word đó
 có nằm trong bộ nhớ cache hay không. 
 Nếu có: word này được gửi đến bộ vi xử lý. 
 Nếu không: một khối dữ liệu từ bộ nhớ chính (chứa từ mà VXL đang muốn truy
 cập), được đọc vào bộ nhớ cache và sau đó từ được gửi đến bộ VXL.
• Tổ chức cache
Cấu trúc bộ nhớ chính/cache
Thao tác Đọc Cache
Tổ chức bộ nhớ cache điển hình
 4.3. Các yếu tố khi thiết kế Cache
a. Địa chỉ bộ nhớ cache e. Chính sách ghi
 Logic Ghi xuôi
 Vật lý Ghi ngược
b. Kích thước bộ nhớ cache f. Kích thước line
c. Ánh xạ bộ nhớ g. Cache nhiều cấp
 Trực tiếp Một hoặc hai cấp
 Kết hợp Thống nhất hoặc phân chia
 Tập kết hợp
d. Thuật toán thay thế
 Least recently used (LRU)
 First in first out (FIFO)
 Least frequently used (LFU)
 Table 4.2 Elements of Cache Design 
 Random
a. Địa chỉ bộ nhớ cache
• Địa chỉ ảo: bộ xử lý hỗ trợ bộ nhớ ảo: 
 Quản lý bộ nhớ thông qua địa chỉ logic
 Các trường địa chỉ trong lệnh là các địa chỉ ảo
 Để thực hiện các thao tác đọc/ghi vào bộ nhớ chính, khối quản lý 
 bộ nhớ (MMU – Memory Management Unit) sẽ dịch từng địa chỉ 
 ảo sang địa chỉ vật lý trong bộ nhớ chính
• Cache ảo (cache logic): bn
 cache đặt giữa BXL và
 MMU
  Địa chỉ được sử dụng
 là địa chỉ ảo
• Cache vật lý: bn cache đặt
 giữa MMU và bộ nhớ chính
  Địa chỉ được sử dụng
 là địa chỉ vật lý
b. Kích thước cache (cache size)
• Kích thước cache phải đủ nhỏ để không làm giá thành tăng cao
• Kích thước cache phải đủ lớn để giảm thời gian truy cập, tăng hiệu
 suất hệ thống
• Ngoài ra, kích thước cache quá lớn sẽ làm tăng số cổng để định địa
 chỉ cho các vị trí nhớ trong cache 
 giảm hiệu quả truy cập ngay cả khi cache nằm trong cùng chip 
 hoặc board với VXL
 b. Kích 
 thước 
 cache 
 trong 
 một số 
 bộ xử lý
a, Hai giá trị cách 
nhau bằng dấu / 
là cache chỉ thị và 
cache dữ liệu.
b, Cả hai cache 
đều là cache chỉ thị;
Không có cache dữ 
liệu.
c. Ánh xạ bộ nhớ
• Bởi vì số đường cache ít hơn số khối bộ nhớ chính, cần có một thuật 
 toán ánh xạ các khối bộ nhớ chính vào các đường bộ nhớ cache
• Ba kỹ thuật có thể được sử dụng:
 Trực tiếp Kết hợp Set Associative
 • Mỗi khối của bộ nhớ • Cho phép một khối nhớ • Kết hợp hai phương
 chính được nạp vào bất pháp trên
 chính được ánh xạ kỳ đường cache nào
 vào một đường • Thể hiện ưu điểm
 cache duy nhất • Logic điều khiển cache của cả phương pháp 
 diễn giải địa chỉ bộ nhớ trực tiếp và kết hợp, 
 • Đơn giản nhất bằng một trường Tag và đồng thời giảm 
 trường Word nhược điểm
 • Để xác định một khối có 
 ở trong một cache
 không, logic điều khiển 
 cache phải cùng lúc 
 kiểm tra Tag của tất cả
 các đường
• Mỗi khối (block) của bộ nhớ chính được ánh xạ vào một đường (line) nhất định
 của bộ nhớ cache.
• Cách xác định: giả sử BN cache có m line. Vậy, block thứ j trong BN chính sẽ được
 ánh xạ vào line nào trong BN cache?
 Với i là số thứ tự line mà block đó được ánh xạ vào, ta có
 풊 = 풋 풐풅풖풍풐 (phép chia lấy dư)
• Do vậy, nhiều block sẽ được ánh xạ vào một line. Để xác định block nào đang
 được ánh xạ vào cache: sử dụng trường tag 
Tổ chức cache ánh xạ trực tiếpKhi truy xuất một word, logic 
 cache tách địa chỉ BN thành 3 
 trường:
 • Word (w bit): xác định một
 word trong block
 • Line (r bit): xác định block 
 đó được ánh xạ vào line thứ
 tự bao nhiêu trong cache
 • Tag (s-r bit): xác định block 
 nào đang được ánh xạ vào
 line đó
 So sánh tag của đc này với tag
 của line trong cache để xác
 định xem có phải block đó
 đang được ánh xạ vào cache 
 không
Ví dụ 
ánh xạ 
 trực 
 tiếp
Tổng kết ánh xạ trực tiếp
• Độ dài địa chỉ = (푠 + 푤) bit
• Số ô nhớ trong bộ nhớ chính = 2푠+푤 word hoặc byte
• Kích thước khối = kích thước đường = 2푤 word hoặc byte
• Số khối trong bộ nhớ chính = 2푠+ 푤/2푤 = 2푠
• Số đường trong bộ nhớ cache = = 2 
• Kích thước của tag = (푠 – ) bit
Nhược điểm: các khối lưu cố định tại 1 đường trong bộ nhớ
cache. Vậy nếu chương trình tham chiếu các từ lặp lại từ hai 
khối mà cùng ánh xạ đến 1 đường thì cache liên tục phải đổi
dl từ memory vào, làm giảm hiệu suất (hiện tượng thrashing)
Bài tập ví dụ
 Bộ nhớ chính: 216 byte, kích thước khối 8 byte, ánh xạ trực 
 tiếp vào cache 32 đường.
 a. 16 bit địa chỉ được chia thành các trường Tag, Line và Word 
 như thế nào?
 b. Các địa chỉ sau sẽ được lưu ở đường nào của cache?
 0001 0001 0001 1011 1101 0000 0001 1101
 1100 0011 0011 0100 1010 1010 1010 1010
 c. Giả sử byte có địa chỉ 0001 1010 0001 1010 được lưu ở 
 cache, các byte nào của bộ nhớ chính cũng được lưu trên 
 đường đó?
 d. Có bao nhiêu byte có thể được lưu trên cache?
• Ánh xạ kết hợp khắc phục nhược điểm của ánh xạ trực 
 tiếp bằng cách cho phép mỗi khối được nạp vào bất kỳ 
 đường nào của bộ nhớ cache 
• Trong trường hợp này, bộ logic điều khiển bộ nhớ 
 cache (cache control logic) tách địa chỉ bộ nhớ thành 
 hai trường: Tag và Word. Trường Tag hiển thị duy nhất 
 một khối bộ nhớ chính. 
• Để xác định liệu một khối có trong bộ nhớ cache, bộ 
 logic điều khiển bộ nhớ cache phải cùng lúc kiểm tra 
 mỗi Tag của một đường để so sánh
Tổ chức ánh xạ kết hợp
 Khi truy xuất một word, 
 logic cache tách địa chỉ
 BN thành 2 trường:
 • Word (w bit): xác định
 một word trong block
 • Tag (s bit): xác định
 block nào đang được
 ánh xạ vào line đó
 So sánh Tag của đc này
 với Tag của các line trong
 cache để xác định xem
 block đó có đang đc ánh
 xạ vào cache không.
 Ví dụ 
ánh xạ
 kết 
 hợp
Tổng hợp ánh xạ kết hợp
• Chiều dài địa chỉ = (s + w) bit
• Số ô nhớ được đánh địa chỉ = 2s+w word hoặc byte
• Kích thước khối = kích thước đường = 2w word hoặc byte
• Số lượng khối trong bộ nhớ chính = 2s+ w/2w = 2s
• Số đường trong cache = không xác định
• Chiều dài trường tag = s bit
Ưu điểm: linh hoạt khi thay thế một khối và đọc một khối mới vào cache. 
Các thuật toán thay thế được xây dựng để tối ưu hóa tỷ lệ truy cập. 
Nhược điểm: mạch phức tạp để thực hiện việc kiểm tra tất cả trường Tag 
của các đường trong cache một cách song song.
•Tận dụng các ưu điểm của cả phương pháp trên 
đồng thời giảm nhược điểm của chúng
•Chia cache thành một số Tập (set) - Mỗi Tập chứa 
một số đường
•Một khối sẽ được ánh xạ vào một đường bất kỳ 
trong một Tập nhất định
• Quan hệ
 m = v* k
 i = j/v (chia lấy phần dư)
 Trong đó
 i = số thứ tự Tập trong cache
 j = số thứ tự khối trong bộ nhớ chính
 m = số lượng đường trong cache
 v = số lượng Tập có trong cache
 k = số lượng đường trong mỗi Tập
• Ví dụ: 1 Tập có 2 đường
 • Ánh xạ kết hợp 2 chiều
 • Một khối có thể nằm trong 1 trong 2 đường trong 
 một Tập
 Ánh xạ từ 
 bộ nhớ chính 
đến bộ nhớ Cache:
 k-Way
 Set Associative
Tổ chức cache k-Way Set Associative
 Khi truy xuất một word, logic 
 cache tách địa chỉ BN thành 3 
 trường:
 • Word (w bit): xác định một
 word trong block
 • Set (d bit): xác định block 
 đó được ánh xạ vào set thứ
 tự bao nhiêu trong cache
 • Tag (s-d bit): xác định block 
 nào đang được ánh xạ vào
 line nào trong Set đó
 So sánh tag của đc này với tag
 của line trong Set để xác định
 xem có phải block đó đang
 được ánh xạ vào cache không
Tổng kết ánh xạ Set Associative
• Chiều dài địa chỉ = (s + w) bit
• Số lượng ô nhớ được đánh địa chỉ = 2s+w word hoặc byte
• Kích thước khối (hoặc đường) = 2w word hoặc byte
• Số khối trong BN chính = 2s+w/2w=2s
• Số đường trong 1 Tập= k
• Số lượng Tập = v = 2d
• Số lượng đường trong cache = m= kv = k * 2d
• Kích thước cache = k * 2d+w word hoặc byte
• Độ rộng trường Tag = (s – d) bits
So sánh hiệu suất của các PP ánh xạ 
 • Cache hit: số lần truy cập cache thành công
 • Cache miss: số lần truy cập cache không thành công
 • Hit ratio: tỷ lệ truy cập
 • Hiệu suất cache được đánh giá dựa trên
 ℎ푒 ℎ𝑖푡
 ℎ𝑖푡 푡𝑖표 =
 푡ổ푛𝑔 푠ố 푙ầ푛 푡 ậ 
Bài tập ví dụ
• Xét VXL 32 bit có một cache 16-Kbyte, ánh xạ tập 
 kết hợp 4-way. Giả sử một đường gồm 4 từ 32-bit 
 (mỗi từ nhớ 32 bit, 1 đường có 4 từ). Xác định các 
 trường của địa chỉ được sử dụng để ánh xạ cache. 
 Từ nhớ có địa chỉ ABCDE8F8 được ánh xạ vào vị trí 
 nào trong cache.
• Bộ nhớ Cache 64 đường sử dụng ánh xạ tập kết hợp 
 4 đường. Bộ nhớ chính có 4K khối, mỗi khối có kích 
 thước 128 từ. Xác định định dạng địa chỉ bộ nhớ
 d. Thuật toán thay thế
• Khi bộ nhớ cache đã đầy, nếu một khối mới được 
 đưa vào cache, một trong những khối hiện có phải 
 được thay thế
 • Đối với ax trực tiếp: một khối bất kỳ chỉ có thể ánh xạ vào 1 
 đường cụ thể. Nên khi cần đưa 1 khối mới vào cache buộc 
 phải xóa dữ liệu cũ trên đường tương ứng đi.
 • Đối với các kỹ thuật kết hợp và tập két hợp, một khối có 
 thể được ánh xạ vào 1 số đường. Vậy khi đưa 1 khối mới 
 vào cache, ta cần xác định xem khối đó sẽ được ánh xạ vào 
 đường nào: thuật toán thay thế
• Để đạt được tốc độ cao, thuật toán phải được thực 
 hiện trong phần cứng
4 thuật toán thay thế phổ biến nhất
• Least recently used (LRU)
 • Hiệu quả nhất
 • Thay thế khối nằm trong cache lâu nhất mà không có tham chiếu đến nó
 • Do triển khai đơn giản, LRU là thuật toán thay thế phổ biến nhất
• First-in-first-out (FIFO)
 • Thay thế khối đã nằm trong cache lâu nhất 
 • Dễ dàng thực hiện như một kỹ thuật vòng đệm hoặc round-robin
• Least frequently used (LFU)
 • Thay thế khối có ít tham chiếu đến nó nhất
 • Ở mỗi line thêm vào một bộ đếm, mỗi khi có tham chiếu đến line nào, bộ 
 đếm của line đó tăng thêm 1 đơn vị
• Ngẫu nhiên
 • Có thể thay thế bất cứ khối nào
 • Các nghiên cứu đã chỉ ra: thay thế ngẫu nhiên chỉ làm giảm hiệu suất của 
 hệ thống đi một chút so với các thuật toán thay thế ở trên
e. Chính sách ghi
Khi một khối trong cache được thay thế, có 2 trường hợp cần 
xem xét:
• Nếu dữ liệu trong cache không thay đổi, có thể ghi đè khối 
 mới lên mà không cần ghi khối cũ ra trước
• Nếu ít nhất 1 thao tác ghi đã được thực hiện trên 1 word 
 trong đường của cache thì bộ nhớ chính phải được cập nhật 
 bằng cách ghi dữ liệu từ cache ra bộ nhớ trước khi đưa 
 khối mới vào
Có hai vấn đề phải đối mặt:
• Nhiều thiết bị có thể có quyền truy cập vào bộ nhớ chính
• Trong trường hợp VXL đa nhân: nhiều cache tương ứng với 
 các nhân gây khó khăn trong việc quản lý dữ liệu
Có hai chính sách ghi: write though và write back
 Write Through
 và Write Back
• Write through: khi VXL gửi lệnh ghi dữ liệu ra bộ nhớ, dữ 
 liệu sẽ được ghi đồng thời ra cả cache và BN
 • Kỹ thuật đơn giản nhất
 • Tất cả các thao tác ghi được thực hiện cho bộ nhớ chính 
 cũng như cache
 • Nhược điểm: tạo ra lưu lượng bộ nhớ đáng kể và có thể tạo 
 ra nút cổ chai
• Write back: khi VXL gửi lệnh ghi, dữ liệu chỉ được cập nhật 
 trên cache, sử dụng 1 bit (gọi là dirty bit) thiết lập giá trị để 
 đánh dấu là dữ liệu đã bị thay đổi. Việc cập nhật dữ liệu 
 lên BNC chỉ xảy ra khi thay thế khối mới vào cache
 • Giảm thao tác ghi bộ nhớ
 • Dữ liệu trên BNC không có hiệu lực. Cơ chế DMA bắt buộc 
 phải thực hiệu qua cache
 • Nhược điểm: mạch phức tạp và khả năng có nút cổ chai
f. Kích thước Line
• Khi khối dữ liệu được lấy ra và đặt trong cache, sẽ thu 
 được không chỉ word mong muốn mà còn 1 số word 
 liền kề
• Khi kích thước khối tăng, ban đầu tỷ lệ truy cập sẽ tăng 
 do nguyên tắc cục bộ dữ liệu hữu ích (dữ liệu có 
 khả năng lớn được truy cập trong câu lệnh tiếp theo)
 được đưa vào cache
• Tuy nhiên, khi kích thước khối quá lớn, tỷ lệ này giảm 
 đi do:
 1, Các khối lớn hơn làm giảm số lượng đường trong một 
 cache
 2, Khi kích thước khối lớn, mỗi word thêm vào lại càng xa 
 word yêu cầu ít có khả năng truy xuất
g. Cache nhiều cấp
• Với các hệ thống ngày nay, người ta thường sử dụng 
 nhiều cache trong kiến trúc
• Cache trên chip (cache on chip) làm giảm hoạt động 
 bus ngoài của bộ xử lý; tăng tốc thời gian xử lý và tăng 
 hiệu năng toàn hệ thống
 • Khi lệnh hoặc dữ liệu được tìm thấy trong cache không cần 
 truy cập bus
 • Truy cập bộ nhớ cache trên chip nhanh hơn đáng kể 
 • Trong giai đoạn này, bus tự do hỗ trợ các lượt truyền khác
• Cache 2 cấp (cache 2 level) : sử dụng một cache on 
 chip (cache L1) và một cache bên ngoài (cache L2)
 • Cải thiện hiệu suất
 • Việc sử dụng cache nhiều cấp làm cho các vấn đề thiết kế liên 
 quan đến cache phức tạp hơn, gồm kích thước, thuật toán 
 thay thế, chính sách ghi
Tỉ lệ truy cập (L1 & L2) cho 8 Kbyte và 16 Kbyte L1
Cache thống nhất / cache phân chia
 • Cache thống nhất: lệnh và dữ liệu được lưu trên
 cùng một cache
 • Ưu điểm: Tốc độ truy cập cao hơn
 • Tự động cân bằng giữa việc nạp dữ liệu và lệnh
 • Chỉ cần thiết kế và thực hiện một bộ nhớ cache 
 • Cache phân chia: lệnh và dữ liệu được lưu trên
 hai cache khác nhau, thường là cache L1
 • Ưu điểm:Loại bỏ sự cạnh tranh cache giữa khối tìm 
 nạp/giải mã lệnh và khối thực hiện
 • Xu hướng: cache phân chia ở L1 và cache thống 
 nhất ở các level cao hơn
4.4.Tổ chức Cache Pentium 4
 Bảng 4.4 
 Intel
 Cache
 Evolution 
Sơ đồ khối Pentium 4
 Các chế độ hoạt động Cache Pentium 4
Note: CD = 0; NW = 1 là kết hợp không hợp lệ. 
4.5. Tổ chức cache ARM
Đặc tính Cache ARM 
ARM Cache và tổ chức bộ đệm ghi
 Tổng kết
 Chương 4: Bộ nhớ Cache
• Đặc điểm của hệ thống bộ • Các yếu tố trong thiết kế 
 nhớ cache
 • Vị trí • Địa chỉ bộ nhớ cache
 • Dung lượng • Kích thước bộ nhớ cache
 • Đơn vị truyền • Ánh xạ bộ nhớ
• Bộ nhớ phân cấp • Thuật toán thay thế
 • How much? • Chính sách ghi
 • How fast? • Kích thước line
 • How expensive? • Cache nhiều cấp
• Nguyên lý bộ nhớ Cache • Tổ chức cache Pentium 4
 • Tổ chức cache ARM
Từ khóa
• Cache: bộ nhớ cache
• Cache hit: việc truy cập thành công vào bộ nhớ cache
• Cache miss: truy cập BN cache không thành công 
• Hit ratio: tỷ lệ truy cập BN cache
• Cache mapping: ánh xạ BN cache
• Write policy: chính sách ghi
• Cache L1, L2, L3: BN cache level 1, 2,3
• Line: đường trong cache
• Block: khối
• Set: tập
Review questions
1. Sự khác nhau giữa truy cập tuần tự, trực tiếp và ngẫu nhiên là gì?
2. Nêu mối quan hệ giữa thời gian truy cập, giá thành và dung lượng
 bộ nhớ.
3. Sự khác nhau giữa ánh xạ trực tiếp, kết hợp và tập kết hợp là gì?
4. Khái niệm cache phân chia và cache thống nhất. Ứng dụng?
5. Các yếu tố chính trong thiết kế cache là gì
6. Write though và write back khác nhau như thế nào? Kỹ thuật nào
 giảm số lần truy cập bus hệ thống nhiều hơn?
7. Trình bày các kỹ thuật thay thế.
8. Kích thước của đường có ảnh hưởng như thế nào đến hiệu suất
 cache (cache hit)?
9. Dung lượng BN cache có ảnh hưởng như thế nào đến hiệu suất
 cache (cache hit)?