CHƯƠNG 4: THIẾT KẾ BỘ NHỚ
Khái niệm cơ bản
Bộ nhớ Cache
Bộ nhớ trong
Bộ nhớ ảo

Khoa KTMT

Vũ Đức Lung

1


Khái niệm cơ bản
Các cấp bộ nhớ cơ bản:
–
–
–
–

Thanh ghi
Cache
Bộ nhớ chính
Bộ nhớ thứ cấp

Khoa KTMT

Vũ Đức Lung

2

Khái niệm cơ bản
Thứ tự thực hiện tìm một item trong bộ nhớ:
– Tìm Item trong bộ nhớ mức cao nhất của các cấp bộ nhớ (xác suất tìm
thấy item trong đó gọi là hit ratio h1, khơng tìm thấy là miss ratio (1h1))
– Khi khơng tìm thấy thì tìm ở cấp thấp hơn (h2, (1-h2))
– Quá trình tiếp diễn cho đến khi tìm thấy hoặc hết cấp bộ nhớ
– Khi tìm thấy Item sẽ được chuyển cho Bộ xử lý

Giả sử Các cấp bộ nhớ có 3 cấp. Thời gian truy cập bộ nhớ
trung bình được tính:
tav = h1*t1 + (1-h1)*[t1+h2*t2+(1-h2)*(t2+t3)]
= t1 + (1-h1)*[t2 + (1-h2)*t3]

Khoa KTMT

Vũ Đức Lung

3


Nguyên tắc tổ chức bộ nhớ
Thống kê: 90% thời gian thi hành 10% số lệnh của chương
trình
Ngun tắc khơng gian:
– Khi bộ xử lý thâm nhập vào ô nhớ nào đó => nhiều khả năng sẽ thâm
nhập vào những ơ nhớ có địa chỉ kế tiếp trong thời gian sau đó

Ngun tắc về thời gian:
– Các ơ nhớ được hệ thống xử lý thâm nhập có khả năng sẽ được thâm

nhập lại trong tương lai gần. Thơng thường chỉ có một số lệnh và một
phần số liệu được thâm nhập nhiều nhất mà thơi. Ví dụ như một lệnh
trong một vịng lặp của chương trình

Khoa KTMT

Vũ Đức Lung

4


Cache Memory
a small high-speed memory that is near the CPU
Thành công cache (cache hit)
Thất bại cache (cache miss)
Tỷ số thành công cache hc(cache hit ratio)
Tỷ số thất bại cache (1-hc) (cache miss ratio)

Khoa KTMT

Vũ Đức Lung

5


Cache Memory (2)
Ảnh hưởng của nguyên lý lân cận thời gian

ntc + tm
tm

tav =
= tc +
n
n
Ảnh hưởng của nguyên lý lân cận không gian

mtc + tm
tm
tav =
= tc +
m
m
Ảnh hưởng tổ hợp của hai nguyên lý
mtc + tm
tm
(
) + (n − 1)tc tc + + (n − 1)tc
t
m
m
tav =
=
= tc + m
n
n
nm
Khoa KTMT

Vũ Đức Lung


6


Tổ chức bộ nhớ cache (0)

Khoa KTMT

Vũ Đức Lung

7


Tổ chức bộ nhớ cache (1)
Phải để một khối bộ nhớ vào chỗ nào của cache (sắp xếp khối)?
Có 3 kỹ thuật tổ chức :
– Kiểu tương ứng trực tiếp (Direct Mapping)
– Kiểu hoàn toàn phối hợp (Fully Associative Mapping)
– Kiểu phối hợp theo tập hợp (Set – Associative Mapping)

Dựa trên hai khía cạnh:
– Cách đặt vào cache một khối nhớ từ bộ nhớ trong
– Cách thay thế một khối cache (khi cache đầy)

Khoa KTMT

Vũ Đức Lung

8



Tổ chức bộ nhớ cache (2)
Kiểu tương ứng trực tiếp
– Nếu mỗi khối bộ nhớ chỉ có một vị trí đặt khối duy nhất trong cache
được xác định theo công thức:

K= i mod n
Trong đó: K: vị trí khối đặt trong cache
i: số thứ tự của khối trong bộ nhớ trong
n: số khối của cache

Kiểu hoàn toàn phối hợp: Một khối trong bộ nhớ trong có thể được
đặt vào vị trí bất kỳ trong cache.

Khoa KTMT

Vũ Đức Lung

9


Tổ chức bộ nhớ cache (3)
Kiểu phối hợp theo tập hợp: cache bao gồm các tập hợp của các khối
cache. Mỗi tập hợp của các khối cache chứa số khối như nhau. Một khối
của bộ nhớ trong có thể được đặt vào một số vị trí khối giới hạn trong tập
hợp được xác định bởi công thức: K= i mod s
Trong đó:
K: vị trí khối đặt trong cache
i: số thứ tự của khối trong bộ nhớ trong
s: số lượng tập hợp trong cache.


Khoa KTMT

Vũ Đức Lung

10


Tổ chức bộ nhớ cache (4)
Ví dụ 1:
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

Khoa KTMT

Vũ Đức Lung

11


Tổ chức bộ nhớ cache (5)
Kiểu tương ứng trực tiếp:
Ví dụ 2: Main memory: 4K blocks
Cache : 128 blocks
Block size: 16 words

Ánh xạ khối bộ nhớ trong vào khối cache

Khoa KTMT

Vũ Đức Lung

12


Tổ chức bộ nhớ cache (6)
Địa chỉ mà bộ xử lý đưa ra có thể phân tích thành hai thành
phần: phần nhận dạng số thứ tự khối và phần xác định vị trí từ
cần đọc trong khối.
Căn cứ vào số từ trong một khối bộ nhớ mà số bit trong trường
địa chỉ sẽ xác định vị trí từ cần đọc trong khối.
Phần nhận dạng số thứ tự khối sẽ khác nhau tuỳ thuộc vào
cách xếp đặt khối, trường chỉ số khối được so sánh với nhãn
của cache để xác định khối trong cache.

Khoa KTMT

Vũ Đức Lung

13


Tổ chức bộ nhớ cache (7)
Kiểu tương ứng trực tiếp:
– Ưu điểm: đơn giản
– Nhược điểm: không hiệu quả sử dụng cache


MMU diễn giải địa chỉ phát ra từ CPU:
– Địa chỉ từ cần đọc trong khối (Word field) = log2B, B – kích thước khối
theo từ
– Chỉ số khối cache ( Block field) = log2N, N-kích thước cache theo block
– Nhãn (Tag field) = log2(M/N), M-kích thước bộ nhớ trong theo khối
– Số bit trong trường địa chỉ bộ nhớ trong = log2(B.M)

Khoa KTMT

Vũ Đức Lung

14


Tổ chức bộ nhớ cache (8)
VD: Xét trường hợp bộ nhớ trong chứa 4K khối, bộ nhớ cache chứa 128 khối và mối
khối có kích thước 16 từ nhớ.

Khoa KTMT

Vũ Đức Lung

15


Tổ chức bộ nhớ cache (9)
Q trình phân tích địa chỉ và trả lời yêu cầu từ CPU

2


3
1

Khoa KTMT

4

Vũ Đức Lung

16


Tổ chức bộ nhớ cache (10)
Kiểu hoàn toàn phối hợp
– Chỉ số khối trong bộ nhớ (Word field) = log2 B
– Địa chỉ từ cần đọc trong khối (Tag field) = log2 M
– Số bit trong trường địa chỉ bộ nhớ trong = log2(B.M)

Ví dụ tìm số bit cho các trường ở VD1 & 2

Khoa KTMT

Vũ Đức Lung

17


Tổ chức bộ nhớ cache (11)
Kiểu hoàn toàn phối hợp


Khoa KTMT

Vũ Đức Lung

18


Tổ chức bộ nhớ cache (12)
Kiểu phối hợp theo tập hợp
–
–
–
–

Word field = log2 B
Set field = log2 S, S – số tập hợp trong cache
Tag field = log2 (M/S), S = N/Bs, Bs số khối trong một tập hợp
Số bit trong trường địa chỉ bộ nhớ trong = log2(B.M)

Ví dụ tìm số bit cho các trường ở VD1 & 2 giả sử số khối
trong một tập tương ứng là 2 và 4

Khoa KTMT

Vũ Đức Lung

19



Tổ chức bộ nhớ cache (13)
Kiểu phối hợp theo tập hợp

Khoa KTMT

Vũ Đức Lung

20


Kỹ thuật thay thế khối
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 (LRU: Least Recently Used): các khối đã được
thâm nhập sẽ được đánh dấu và khối bị thay thế là khối không
được dùng từ lâu nhất.
Vào trước ra trước (FIFO: First In First Out): Khối được đưa
vào cache đầu tiên, nếu bị thay thế, khối đó sẽ được thay thế
trước nhất.
Tần số sử dụng ít nhất (LFU: Least Frequently Used): Khối
trong cache được tham chiếu ít nhất
Khoa KTMT

Vũ Đức Lung

21


Kỹ thuật thay thế khối
Ví dụ:

Ma trận số 4x8. Giả sử mỗi số lưu
trong một từ và các phần tử ma trận
lưu theo thứ tự từ địa chỉ 1000 đến
1031. Cache chứa 8 khối, mỗi khối 2
từ. Áp dụng kỹ thuật LRU. Thứ tự yêu
cầu từ CPU:

Khoa KTMT

Vũ Đức Lung

22


Kỹ thuật thay
thế khối –
Direct
mapping

Khoa KTMT

Vũ Đức Lung

23


Kỹ thuật thay
thế khối –
Fully
associative

mapping

Khoa KTMT

Vũ Đức Lung

24


Kỹ thuật thay
thế khối – Set
Associative
mapping

Khoa KTMT

Vũ Đức Lung

25