Bài giảng Kiến trúc máy tính & Hợp ngữ - Bài 5: Tổ chức bộ nhớ (Phần 2)

 15/11/2017
 Bài 5
 Tổ chức bộ nhớ
 Phần BỘ NHỚ ĐỆM NHANH
 (CACHE MEMORY)
 (tham khảo trang 66 
 – KTMT Cần Thơ)
Ý tưởng thiết kế cache

 Xác suất truy cập dữ liệu trong bộ nhớ trong
 Một chương trình mất 90% thời gian thi hành lệnh 
 của nó để thi hành 10% số lệnh của chương trình.

 Cache thiết kế dựa trên 2 nguyên tắc:
 
 Nguyên tắc về thời gian: cho biết các ô nhớ được 
 hệ thống xử lý thâm nhập có khả năng sẽ được 
 thâm nhập trong tương lai gần.
 
 Nguyên tắc về không gian: cho biết, bộ xử lý 
 thâm nhập vào một ô nhớ thì có nhiều khả năng 
 thâm nhập vào ô nhớ có địa chỉ kế 
 1
 15/11/2017
Nguyên tắc chung

 Cache có tốc độ nhanh 
 hơn bộ nhớ chính, 
 chứa dữ liệu và lệnh 
 thường dùng đến. Bộ
 CPU Cache nhớ

 Cache được đặt giữa 
 CPU và bộ nhớ chính 
 nhằm tăng tốc độ truy 
 Chuyển Chuyển 
 nhập bộ nhớ của CPU từng từng 

 Cache có thể được đặt từ khối
 trên chip của CPU
 (vận hành bằng bộ điều 
 khiển cache)
Ví dụ về thao tác của cache

 CPU yêu cầu nội dung của ngăn nhớ

 CPU kiểm tra trên cache với dữ liệu này

 Nếu có, CPU nhận dữ liệu từ cache (nhanh) 
 (cache hit)

 Nếu không có (cache miss), 
 đọc block nhớ chứa dữ liệu từ bộ nhớ chính 
 vào cache (lâu) (cache penalty).

 Tiếp đó chuyển dữ liệu từ cache vào CPU
 2
 15/11/2017
Cấu trúc chung
của cache / bộ nhớ chính

 Bộ nhớ chia thành các Block
 cache chia làm các Line 
 có kích thước bằng nhau
Vận hành

 Một số Block của bộ nhớ chính được nạp vào các 
 Line của cache.

 Nội dung Tag (thẻ nhớ) cho biết block nào của bộ 
 nhớ chính hiện đang được chứa ở line đó.

 Khi CPU truy nhập (đọc/ghi) một từ nhớ, có 2 khả 
 năng xảy ra:
 
 Từ nhớ đó có trong cache (cache hit)
 
 Từ nhớ đó không có trong cache (cache miss)
 3
 15/11/2017
Các vấn đề khi vận hành
Vì số line của cache ít hơn số block của bộ nhớ chính, 
cần có một thuật giải ánh xạ thông tin trong bộ nhớ
chính vào cache.

 Câu hỏi 1: Phải để một khối bộ nhớ vào chỗ 
 nào của cache (sắp xếp khối)? 

 Câu hỏi 2: Làm sao để tìm một khối khi nó 
 hiện diện trong cache (nhận diện khối)? 

 Câu hỏi 3: Khối nào phải được thay thế trong 
 trường hợp thất bại cache (thay thế khối)? 

 Câu hỏi 4: Việc gì xảy ra khi ghi vào bộ nhớ 
 (chiến thuật ghi)? 
Các PP ánh xạ địa chỉ
a) Ánh xạ trực tiếp (Direct mapping)

 Mỗi block của bộ nhớ chính chỉ có thể được nạp 
 vào 1 line duy nhất của cache.

 Quy ước nạp: (với m là số line, đánh số: 0 đến m-1
 B0 → L 0 B1 → L 1 ...... B m-1 → L m-1
 Bm → L 0 Bm+1 → L 1

 Vì thế: L0 : B 0, B m, B 2m ...
 L1 : B 1, B m+1 , B 2m+1 ..
Kết luận: B j chỉ có thể được nạp vào L i với i = j mod m
 4
 15/11/2017
Ví dụ 1(a)
 
 Bộ nhớ trong có 32 khối, cache có 8 khối, mỗi 
 khối gồm 32 byte, khối thứ 12 của bộ nhớ trong 
 được đưa vào cache. Bộ nhớ có kích thước 1 KB
 
 Thao tách trên bit của
 Phép tính mod cho 2 n: ( 8 = 2 3)
 
 Tối đa 32 khối: 5 bit
 
 12 giá trị nhị phân: 0 1 1 0 0
 
 12 mod 8 = 4, 3 bit cuối 1 0 0
 
 12 / 8 = 1, 2 bit đầu 0 1
 giá trị (01) được lưu trong Tag để phân biệt Block nào 
 đang nằm trong Line
 Ví dụ: để phân biệt 4, 12, 20, 28
 4 / 8 = 0 (00)
 12 / 8 = 1 (01)
 20 / 8 = 2 (10)
 28 / 8 = 3 (11)
 5
 15/11/2017
(cơ chế)
Địa chỉ CPU phát ra có N bit, được chia thành 3 
 trường:

 Trường Byte (có n1 bit) để xác định byte nhớ trong
 Line (Block)
 2n1 = kích thước 1 Line

 Trường Line (có n2 bit) để xác định Line trong
 Cache
 2n2 = số Line trong Cache
 Dung lượng Cache = 2 n1 x 2n2 = 2 n1+n2

 Trường Tag (có n3 bit): số bit còn lại
 n3 = N - (n1 + n2) > 0 vì 2N >> 2 n1+n2
 6
 15/11/2017
 Ví dụ 1(b)
 
 Trường Byte:
 Địa chỉ từ (byte) nhớ: 5 bit
 
 Trường Line: 3 bit
 
 Trường Tag: 2 bit
 Ví dụ: truy cập từ nhớ có địa chỉ (10 bit) 195h
 0 1 /1 0 0/1 0 1 0 1
b) Ánh xạ liên kết toàn phần (Fully Associative Mapping)

 Mỗi Block có thể được nạp vào bất kỳ Line nào của 
 cache.

 Địa chỉ bộ nhớ do CPU phát ra được chia thành 2 
 phần: Tag và Byte.

 Để kiểm tra xem một Block có trong cache hay không, 
 phải đồng thời kiểm tra tất cả Tag của các Line trong 
 cache.

 Cần các mạch phức tạp để kiểm tra.
 7
 15/11/2017
c) Ánh xạ liên kết tập hợp (Set Associative Mapping)

 Là phương pháp dung hòa của 2 phương pháp trên

 Chia cache thành các tập: S 0, S 1, S 2 ...

 Mỗi Set có một số Line (2, 4, 8, 16 Line)
 Vd mỗi Set có 2 line

 Mỗi block được nạp vào 1 line nào đó trong Set nhất 
 định:

 B0 → S 0 B1 → S 1 ...... Bk-1 → S k-1
 Bk → S 0

 Địa chỉ do CPU phát ra có 3 trường: Tag, Set, Byte
 Ví dụ 2
 
 Hệ thống có: 
 
 bộ nhớ chính = 256 MB
 
 Cache = 128 KB
 
 Line = 16 Byte
 
 Xác định số bit của các trường địa chỉ khi
 
 Ánh xạ trực tiếp
 
 Ánh xạ liên kết tập hợp 4 Line/Set
 8
 15/11/2017
1) 2 N = 256 x 2 20 = 2 28 ⇒ N = 28 bit

 Tính cho trường Byte:
 Kích thước line = 16 = 2 4 Byte ⇒ n1 = 4 bit

 Tính cho trường Line:
 Số line trong Cache: 128 x 2 10 / 16 = 2 13 ⇒ n2 = 13 bit

 Tính cho trường Tag:
 n3 = N - (n1 + n2) = 28 - (4 + 13) = 11 bit
2) 

 Trường Byte: 
 n1 = 4 bit

 Trường Set:
 Số Set = Số line / 4 = 2 13 / 4 = 2 11 ⇒ n2 = 11 bit

 Trường Tag: 
 n3 = N - (n1 + n2) = 28 - (4 + 11) = 13 bit
3. Các thuật giải thay thế block trong cache
 
 Khi CPU truy nhập một thông tin mà không có 
 trong cache (cache miss) thì nạp block chứa 
 thông tin đó vào trong cache để thay thế block cũ 
 trong cache.
 
 Ánh xạ trực tiếp chỉ có 1 cách nạp không cần 
 thuật giải để nạp.
 
 Hai phương pháp ánh xạ liên kết cần có thuật giải 
 để lựa chọn thay thế.
 9
 15/11/2017
 
 Các thuật giải thay thế block trong cache
 1. Random: thay block một cách ngẫu nhiên.
 2. FIFO (First In, First Out): thay thế block đã tồn tại lâu 
 nhất trong toàn cache đối với ánh xạ liên kết toàn 
 phần, trong set đối với ánh xạ liên kết tập hợp.
 3. LFU (Least Frequently Used): thay block có số lần 
 truy nhập ít nhất.
 4. LRU (Least Recently Used): thay block có khoảng 
 thời gian dài nhất không được truy nhập được đánh 
 giá là hiệu quả nhất.
4. Phương pháp ghi dữ liệu khi cache hit
(để đồng bộ dữ liệu giữa cache và bộ nhớ)

 Ghi xuyên qua (Write through)
 
 ghi cả cache và bộ nhớ chính
 
 tốc độ chậm

 Ghi trả sau (Write back)
 
 chỉ ghi ra cache
 
 tốc độ nhanh
 
 khi block trong cache bị thay thế cần phải ghi trả 
 cả block về bộ nhớ chính
 10
 15/11/2017
Các mức cache
 
 Việc dùng cache trong có thể làm cho sự cách 
 biệt giữa kích thước và thời gian thâm nhập giữa 
 cache trong và bộ nhớ trong càng lớn. 

 Người ta đưa vào nhiều mức cache: 
 
 Cache mức một (L1 cache): thường là cache 
 trong (on-chip cache; nằm bên trong CPU) 
 
 Cache mức hai (L2 cache) thường là cache ngoài 
 (off-chip cache; cache này nằm bên ngoài CPU). 
 
 Ngoài ra, trong một số hệ thống còn có tổ chức 
 cache mức ba (L3 cache), đây là mức cache 
 trung gian giữa cache L2 và một thẻ bộ nhớ. 
 11