Bài giảng Kiến trúc máy tính và hợp ngữ - Chương 5: Tổ chức bộ nhớ

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ộ

nhớ

CPU

Cache

ò Cache được đặt giữa

CPU và bộ nhớ chính

nhằm tăng tốc độ truy

nhập bộ nhớ của CPU

Chuyển

từng

từ

Chuyển

từng

khối

ò Cache có thể được đặt

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

B₀→ L₀B₁→ L₁...... B_m-1→ L_m-1

B_m→ L₀B_m+1→ L₁

ò Vì thế:

L₀: B₀, B_m, B_2m...

L₁: B₁, B_m+1, B_2m+1..

Kết luận: B_jchỉ có thể được nạp vào L_ivớ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ⁿ: (8 = 2³)

ò Tối đa 32 khối: 5 bit

ò 12 giá trị nhị phân:

ò 12 mod 8 = 4, 3 bit cuối

ò 12 / 8 = 1, 2 bit đầu

0 1 1 0 0

1 0 0

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)

(01)

(10)

(11)

12 / 8 = 1

20 / 8 = 2

28 / 8 = 3

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)

2ⁿ¹= kích thước 1 Line

ò Trường Line (có n2 bit) để xác định Line trong

Cache

2ⁿ²= số Line trong Cache

Dung lượng Cache = 2ⁿ¹x 2ⁿ²= 2ⁿ¹⁺ⁿ²

ò Trường Tag (có n3 bit): số bit còn lại

n3 = N - (n1 + n2) > 0 vì 2^N>> 2ⁿ¹⁺ⁿ²

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₀, S₁, S₂...

ò 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:

ò B₀→ S₀B₁→ S₁

...... B_k-1→ S_k-1

B_k→ S₀

ò Đị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²⁰= 2²⁸⇒ N = 28 bit

ò Tính cho trường Byte:

Kích thước line = 16 = 2⁴Byte

⇒ n1 = 4 bit

ò Tính cho trường Line:

Số line trong Cache: 128 x 2¹⁰/ 16 = 2¹³

⇒ 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¹³/ 4 = 2¹¹⇒ 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

Bài giảng Kiến trúc máy tính và hợp ngữ - Chương 5: Tổ chức bộ nhớ - Phần bộ nhớ đệm nhanh (Cache memory)