Ánh xạ trực tiếp

Mỗi Block của BNC chỉ được ánh xạ vào một Line duy nhất:

i = j mod m

i: số hiệu Line trong cache

j: số hiệu Block trong BNC

m: số lượng Line trong cache

Khi đó, địa chỉ do CPU phát ra gồm 3 trường:

Word: xác định số ngăn nhớ trong Block

 Block (Line) có 2w ngăn nhớ

Line: xác định số Line trong cache

 Cache có 2r Line, cache chứa 2r + w ngăn nhớ

Tag: xác định Block nào đang ở trong Line

 BNC chứa 2(s - r) + r + w = 2s + w ngăn nhớ

Cho máy tính có dung lượng:

BNC = 256 MB, cache = 64 KB, line = 16 byte,

Độ dài ngăn nhớ = 4 byte.

Tìm dạng địa chỉ do BXL phát ra?

Giải: Ta có:

BNC = 256 MB = 228 byte = 228/22 = 226 ng/nhớ

Cache = 64 KB = 216 byte = 216/22 = 214 ng/nhớ

Line = 16 byte =24/22 = 22 ng/nhớ  w = 2

Số lượng Line trong cache: 214/22 = 212  r = 12

Số bit của phần Tag: 26 - 12 - 2 = 12, s - r = 12

Ưu điểm:

Dễ thực hiện, vì một Block được ánh xạ cố định vào một Line  không cần thuật toán chọn Line.

Thiết kế mạch đơn giản.

Nhược điểm:

Tỉ lệ cache hit thấp.

Ánh xạ liên kết hoàn toàn

Mỗi Block trong BNC được ánh xạ vào một Line bất kỳ trong Cache

Khi đó, địa chỉ do BXL phát ra có dạng

Word: xác định ngăn nhớ trong Block

 Block có 2w ngăn nhớ

Tag: xác định Block đang ở trong Line

 Số lượng Block: 2s

 Dung lượng BNC: 2s + w ngăn nhớ

Ưu điểm:

Tỉ lệ cache hit cao hơn ánh xạ trực tiếp vì một Block được phép vào một Line bất kỳ.

Nhược điểm:

Thiết kế mạch tương đối phức tạp, thể hiện ở mạch so sánh.

Ánh xạ liên kết tập hợp

Cache được chia thành nhiều Set, mỗi Set gồm nhiều Line liên tiếp

Một Block của BNC chỉ được ánh xạ vào một Set duy nhất trong cache, nhưng được ánh xạ vào Line bất kỳ trong set đó:

i = j mod v

i: số hiệu Set trong cache

j: số hiệu Block trong BNC

v: số lượng Set trong cache

Khi đó, địa chỉ do BXL phát ra gồm:

Word: xác định số hiệu ngăn nhớ trong Block

 Block (Line) có 2w ngăn nhớ

Set: xác định số hiệu Set trong cache

 Cache có 2d Set

Tag: xác định Block nào đang ở trong Line

 BNC chứa 2(s - d) + d + w = 2s + w ngăn nhớ

Cho máy tính có dung lượng:

BNC = 256 MB, cache = 128 KB, line = 64 byte,

Set = 4 Line, độ dài ngăn nhớ = 4 byte.

Tìm dạng địa chỉ do BXL phát ra?

Giải: Ta có:

BNC = 228 byte = 228/22 = 226 ng/nhớ

Cache = 217 byte = 217/22 = 215 ng/nhớ

Line = 26/22 = 24 ng/nhớ  w = 4

D/l Set: 22 * 24= 26  s/l Set: 215/26 = 29  d = 9

Số bit của phần Tag: 26 - 9 - 4 = 13, s - d = 13

Ưu điểm:

Tỉ lệ cache hit cao vì một Block được phép vào một Line bất kỳ trong Set, và dễ so sánh.

Đây là kỹ thuật ánh xạ tốt nhất trong 3 kỹ thuật.

Nhược điểm:

Thiết kế mạch phức tạp.

Các thuật toán thay thế

Kỹ thuật ánh xạ trực tiếp: Không thay được

Hai kỹ thuật ánh xạ liên kết: có 4 thuật toán

Random: thay ngẫu nhiên một Block cũ nào đó

 Dễ thực hiện, nhanh nhất, tỉ lệ cache hit thấp.

FIFO (First In - First Out): thay Block ở đầu tiên trong số các Block đang có trong cache

 tỉ lệ cache hit không cao

LFU (Least Frequently Used): thay Block được dùng với tần suất ít nhất  tỉ lệ cache hit tương đối cao

LRU (Least Recently Used): thay Block được dùng gần đây ít nhất  tỉ lệ cache hit cao

Hoạt động của cache

Đọc:

Nếu cache hit: đọc ngăn nhớ từ cache

Nếu cache miss: thay Block  cache hit

Ghi:

Nếu cache hit: có 2 phương pháp:

Write through: ghi dữ liệu vào cả cache và cả BNC

 không cần thiết, tốc độ chậm, mạch đơn giản.

Write back: chỉ ghi vào cache, khi nào Block (trong cache) được ghi bị thay đi  ghi vào BNC

 tốc độ nhanh, mạch phức tạp.

Nếu cache miss: thay Block  cache hit