MỤC LỤC

1


DANH MỤC HÌNH VẼ

2


LỜI NÓI ĐẦU
Cache là một bộ phận quan trọng trong hệ thống phân cấp bộ nhớ, ảnh
hướng lớn đến hiệu năng toàn hệ thống do là bộ phần gần bộ vi xử lý nhất. Do đó
nghiên cứu về cache sẽ giúp người lập trình có những hiểu biết tổng quan nhất về
hiệu năng hệ thống, cũng như cải tiến hiệu năng của các chương trình mà mình tạo
ra.
Hiện nay cache vẫn phát triển với tốc độ rất chóng mặt, cả về dung lượng,
bộ nhớ hay hiệu năng. Tuy vậy, hiện chưa thực sự có tài liệu tiếng Việt nào được sử
dụng rộng rãi như những tham khảo cơ bản nhất dành cho những người mới bắt
đầu sử nghiên cứu về cache. Nhóm sinh viên tiến hành nghiên cứu đề tài này, trước
hết là tăng vốn kiến thức cho bản thân, sau đó tuy không có tham vọng tạo ra một
tài liệu có tính nền tảng nhưng cũng mong muốn tạo ra một tài liệu tham khảo nhất
định cho những bước đầu nghiên cứu về cache.
Nhóm sinh viên cũng xin gửi lời cảm ơn tới Giảng viên hướng dẫn Ths. Tạ
Thị Kim Huệ đã giúp đỡ nhóm có những kiến thức nền tảng để có thể thực hiện đề
tài này.

3


1. TỔNG QUAN

Từ những ngày đầu tiên của công nghệ máy tính, các lập trình viên đã muốn
có một bộ nhớ có dung lượng lớn, thậm chí là không giới hạn và truy cập nhanh.
Tuy nhiên, với các công nghệ tại thời điểm đó đã không cho phép điều này xảy ra,
một bộ nhớ có dung lượng lớn thì sẽ truy cập chậm, và ngược lại một bộ nhớ có
dung lượng nhỏ thì sẽ truy cập nhanh.
Công nghệ hiện nay đã cho phép tạo ra những bộ nhớ có khả năng truy cập
nhanh và dung lượng “có vẻ ” như không giới hạn bằng cách sử dụng hệ thống
phân cấp bộ nhớ dựa trên nguyên tắc địa phương. Nguyên tắc địa phương có nghĩa
là một chương trình sẽ không truy cập vào tất cả các vùng của bộ nhớ với một xác
suất như nhau, mà sẽ truy cập từng vùng địa chỉ tương đối nhỏ của bộ nhớ với các
mức độ ưu tiên khác nhau và gần như có thể truy cập ngay lập tức. Có hai nguyên
tắc địa phương được sử dụng:
 Địa phương tạm thời (địa phương theo thời gian): nếu một mục được tham

chiếu, nó sẽ có xu hướng sớm được tham chiếu tiếp tục.
 Địa phương không gian: nếu một mục được tham chiếu, thì các mục có địa chỉ
xếp gần nó cũng sẽ sớm được tham chiếu. Địa phương không gian sẽ được đề
cập đến trong phần phân cấp bộ nhớ.

Các chương trình hầu hết đều chứa các vòng, do đó các biến được sử dụng
liên tục, điều này thể hiện tính địa phương theo thời gian. Khi các vòng đã kết thúc,
4


các thủ tục được gọi tuần tự, hoặc các mảng dữ liệu được gọi, tính địa phương
không gian được thể hiện. Các nguyên tắc địa phương được sử dụng để xây dựng
hệ thống phân cấp bộ nhớ. Một hệ thống phân cấp bộ nhớ bao gồm nhiều bộ nhớ
với tốc độ và kích cỡ khác nhau. Bộ nhớ càng nhanh thì càng đắt và kích thước
dung lượng càng nhỏ.
Ngày nay, có ba loại bộ nhớ chính được sử dụng để phân cấp bộ nhớ, đó là:

 Bộ nhớ chính của hệ thống DRAM (Dynamic RAM), có dung lượng lớn, rẻ.
 Bộ nhớ gần với vi xử lý (caches) là SRAM, có dung lượng nhỏ nhất, đắt nhất.
 Bộ nhớ cấp thấp nhất là đĩa từ, ở đây có thể là đĩa cứng, có dung lượng lớn

nhất, rẻ nhất.
Hệ thống phân cấp bộ nhớ ra đời đã khiến cho người dùng có thể sử dụng được
những bộ nhớ lớn với giá rẻ nhất và tốc độc nhanh nhất có thể.
Dữ liệu trong bộ nhớ trong hệ thống phân cấp bộ nhớ được chia làm các khối
(block) hoặc đường (line). Tại một thời điểm, một block hoặc một line chỉ có thể chuyển
tiếp giữa hai bộ nhớ có cấp độ liền kề nhau. Đối với một hệ thống phân cấp bộ nhớ bất kì,
bộ xử lý sẽ gửi yêu cầu đến bộ nhớ gần nhất và nhanh nhất (cache), sau đó các yêu cầu sẽ
được gửi xuống các bộ nhớ cấp thấp hơn nếu cần. Với một hệ thống phân cấp bộ nhớ, ta
cần quan tâm những khái niệm sau:


Hit – Dữ liệu yêu cầu ở cấp độ bộ nhớ đang truy cập.



Miss – Dữ liệu yêu cầu không tìm thấy trong cấp độ bộ nhớ đang cần truy cập.

5




Hit rate – Tỉ lệ phần trăm truy cập bộ nhớ được tìm thấy trong 1 cấp độ bộ nhớ đang cần
truy cập.




Miss rate – Tỉ lệ phần trăm truy cập bộ nhớ không được tìm thấy trong 1 cấp độ bộ nhớ
đang cần truy cập. Note: Miss Rate = 1 – Hit Rate.



Hit time – Số lần yêu cầu để truy cập thông tin yêu cầu trong 1 cấp độ bộ nhớ.



Miss penalty – Thời gian cần thiết để xử lý 1 miss, bao gồm thay thế 1 khối trong 1 cấp
độ trên của bộ nhớ, cộng với thời gian đưa dữ liệu yêu cầu tới bộ xử lý. (Hit time <<
Miss Penalty).

Hình 1. Tháp mô tả kiến trúc máy tính

6


2. CƠ BẢN VỀ CACHE
Phần này sẽ mô tả các phương pháp tổ chức bổ nhớ cache, cũng như phương
pháp truy cập bộ nhớ cache đơn giản nhất. Các loại bộ nhớ cache được nhắc đến
trong phần 2 này đều là cache 1 mức, cache nhiều mức sẽ được nhắc đến ở phần 3.
Để có thể lấy được đúng dữ liệu trong cache, ta cần trả lời được hai câu hỏi
sau:
- Làm sao biết dữ liệu cần tìm có trong cache hay không?
- Làm sao biết dữ liệu lấy ra có đúng ra dữ liệu cần tìm hay không?
Để có thể trả lời được hai câu hỏi này, ta cần có các quy ước đánh địa chỉ
cho các blocks dữ liệu của cache. Các quy ước này cần phải duy nhất và đảm bảo
xung đột dữ liệu có xác suất xảy ra nhỏ nhất. Phương pháp đơn giản nhất để giải

quyết hai câu hỏi trên là sử dụng cache có tổ chức dữ liệu theo kiểu ánh xạ trực
tiếp (direct-mapped).

7


2.1. Cache ánh xạ trực tiếp
2.1.1. Cấu trúc cache ánh xạ trực tiếp
Cache ánh xạ trực tiếp là dạng cache có cấu trúc mà mỗi vị trí trong bộ nhớ
chính ánh xạ xác định đến một vị trí duy nhất trong cache và ngược lại, mỗi vị trí
trong cache ánh xạ xác định đến một vị trí duy nhất trong bộ nhớ chính.
Trong bảng mô tả cấu trúc cache dưới đây, ta có thể thấy, trong cache còn
hai chỗ trống, nhưng Xn chỉ được ghi chính xác vào một chỗ còn trống.

Hình 2. Mô tả lưu trữ dữ liệu trong cache ánh xạ trực tiếp

2.2. Phương pháp đánh địa chỉ trong cache ánh xạ trực tiếp
Một ô nhớ có địa chỉ xác định trong bộ nhớ khi lưu vào cache sẽ có địa chỉ
xác định trong cache. Địa chỉ tương ứng trong cache được gọi là chỉ số (index).
Hai địa chỉ này có liên hệ với nhau theo công thức:
(Địa chỉ ô nhớ trong bộ nhớ) chia lấy dư (số block trong cache) = (Địa chỉ tương ứng trong cache)

8


Hình 3. Mô tả việc ánh xạ dữ liệu từ bộ nhớ về cache

Tuy nhiên, như trong hình 1, với bộ nhớ chính có 5 bits địa chỉ, ta nhận thấy,
một ô nhớ trong cache có thể tương ứng với nhiều ô nhớ trong bộ nhớ chính, điều
này dẫn đến xung đột dữ liệu. Để giải quyết vấn đề này, trường tag được đặt ra

trong nội dung lưu trữ của cache. Mỗi block trong cache sẽ có một thẻ tag tương
ứng để một block cache chỉ có thể tương ứng với một ô nhớ duy nhất trong bộ nhớ
chính.
Với ví dụ bộ nhớ chính có 5 bits địa chỉ như trên, sẽ có 3 bits cuối được sử
dụng làm index, 2 bits đầu sử dụng làm trường tag. Với 3 bits index, cache tương
ứng sẽ có 23 = 8 blocks. 8 blocks này có index tương ứng với vị trí, kết hợp 3 bits
index tương ứng với 2 bits tag ta sẽ xác định được ô nhớ trong bộ nhớ chính tương

9


ứng với block trong cache. Và mỗi block trong cache chỉ tương ứng với một ô nhớ
duy nhất trong bộ nhớ chính và ngược lại.

Hình 4. Mô tả quá trình điền thẻ tag và dữ liệu trong cache. Cach block size là 8, bộ nhớ chính
có 5 bits địa chỉ.

Trong hình 2, ta có thể thấy có trường V, ở đây là viết tắt của valid bit (bit
đánh dấu hợp lệ). Các block của cache có thể trống, kể cả sau khi chương trình đã
gọi rất nhiều lệnh, nếu bộ xử lý phải quét qua tất cả chiều dài của block trống này
thì sẽ lãng phí rất nhiều thời gian xử lý, do đó cần có một bit đánh dấu để chỉ ra ô
nhớ này có trống hay không.
10


Valid bit là MSB trong một block, khi bộ xử lý quét qua bit này nếu thấy giá
trị bit là ‘0’, sẽ bỏ qua không xử lý block, nếu thấy giá trị bit là ‘1’ sẽ tiến hành xử
lý block.
2.3. Phương pháp lấy dữ liệu trong cache


Hình 5. Mô tả quá trình lấy dữ liệu trong cache.

Trong hình 4, quá trình lấy dữ liệu từ cache được mô tả. Cache sử dụng 10
bit index, do đó có 210 = 1024 blocks. Một block có 1 word dữ liệu = 4 byte, vì vậy
cần 2 bit sử dụng để làm byte offset, chỉ thị xem cần lấy byte nào trong 4 byte của
một word. 20 bits còn lại để sử dụng làm thẻ tag.
Một bộ so sánh sẽ được sử dụng để so sánh 20 bit đầu tiên của địa chỉ với
thẻ tag, đưa ra kết quả là 1 nếu giống nhau và kết quả là 0 nếu khác nhau (bộ so

11


sánh là thành phần ảnh hưởng lớn đến giá thành của toàn bộ hệ thống, điều này sẽ
được đề cập trong phần 4). Kết quả của bộ so sánh được đưa vào một đầu vào của
cổng logic AND, đầu vào còn lại của cổng logic AND là valid bit, nếu valid bit
bằng 1, giá trị hit được trả về và dữ liệu được đọc ra.
Với một bộ nhớ sử dụng 32 bits địa chỉ, cache có kích thước 2n blocks, mỗi
block có kích thước 2m words, thì thẻ tag sẽ có độ dài
(32 – n – m -2) bits

(2.3.1)

Toàn bộ cache sẽ có độ dài:
2n x (m x 32 + (32 – n – m - 2) +1 ) = 2n x (m x 32 + 31 – n – m ) bits. (2.3.2)

Thực tế, với các máy tính hiện nay, một block không chỉ chứa 1 word dữ
liệu, nó có thể chứa 2, 4, và kích thước chuẩn là 8 words một block. Ta có thể xem
hình dưới để thấy một ví dụ:

12



Hình 6. Mô tả quá trình đọc dữ liệu trong cache ở bộ nhớ FASTMATH, 16 words trong 1 block.

Ta có thể nhận thấy khi một block có nhiều words dữ liệu, ta đã phải sử dụng
thêm các bits block offset để phát hiện ra cần đọc word nào trong block. Với 4 byte
block offset, ta có thể có 24 = 16 words trong 1 block. Bộ MUX được sử dụng để
lựa chọn word cần đọc trong 16 word của 1 block.

13


3. CÁC CƠ CHẾ XỬ LÝ SỰ KIỆN TRONG CACHES
Trong phần này, chỉ xem xét đến các cơ chế xử lý miss, xử lý ghi dữ liệu vào
cache và xử lý tràn cache. Cơ chế xử lý đọc dữ liệu từ cache tương đối đơn giản và
đã được trình bày ở trên.
3.1. Cơ chế xử lý khi xảy ra miss
Sự kiện miss khi truy cập dữ liệu trong caches xảy ra khi chương trình yêu
cầu dữ liệu từ bộ nhớ nhưng không được đáp ứng, lúc này dữ liệu cho các khối
thanh ghi, ALU đều không có. Do đó, bộ xử lý sẽ được tạm ngưng và thực hiện
đóng băng các thanh ghi chương trình nhìn thấy được.
Quá trình xử lý miss của cache được thực hiện tuần tự theo các bước sau:
 Gửi giá trị PC gốc bằng (PC – 4) về bộ nhớ lệnh. Do khi thực hiện đến pha truy

cập bộ nhớ, PC đã được mặc định tăng lên 4.
 Bộ nhớ lệnh chính tổ chức hành động đọc và đợi cho đến khi nó được truy cập

xong.
 Ghi dữ liệu vào cache, đưa các bit cao vào thẻ tag (lấy ra từ ALU) và bật bit đánh
dấu lên 1.

 Chạy lại toàn bộ lệnh từ pha đầu tiên.

14


3.2. Cơ chế ghi dữ liệu vào cache
Không đơn giản như xử lý miss và xử lý đọc, xử lý ghi dữ liệu vào cache rất
phức tạp và có nhiều phương pháp. Mỗi phương pháp có ưu nhược điểm riêng, đặc
biệt là có ảnh hưởng đáng kể đến hiệu năng của cache tại mỗi phương pháp.
3.2.1. Write – through
Giả sử ta có một lệnh lưu trữ dữ liệu, và dữ liệu được lưu trữ tại cache mà
không làm thay đổi dữ liệu tại bộ nhớ chính. Lúc này dữ liệu giữa bộ nhớ chính và
cache không còn giống nhau nhưng vẫn tương ứng về vị trí, như vậy là không hợp
lệ. Để giải quyết vấn đề này ta có thể lần lượt ghi dữ liệu trả về vào cache, sau đó
lưu vào bộ nhớ chính. Phương pháp này gọi là write-through.
Tuy nhiên phương pháp này rất chậm do lần ghi nào cũng phải ghi vào bộ
nhớ chính. Sau khi ghi xong vào bộ nhớ chính, bộ vi xử lý mới có thể thực hiện
lệnh tiếp theo. Mỗi lần ghi vào bộ nhớ chính mất khoảng 100 chu kì đồng hồ. Với
bộ nhớ có CPI = 1, 10% các lệnh là lệnh store thì CPI sau khi xảy ra miss ở cache
sẽ là 1 + 100 x 10% = 11, gấp tới 11 lần.
3.2.2. Write – buffer
Write – buffer là một phương pháp giải quyết được vấn đề tồn tại của Writethrough. Phương pháp write-buffer sử dụng một bộ đệm để lưu trữ dữ liệu trong
khi nó đang chờ để được lưu vào bộ nhớ chính. Khi dữ liệu đã được lưu vào bộ
nhớ chính, buffer sẽ được giải phóng.
15


Một lệnh sau khi thực hiện sẽ lưu kết quả vào cache và sau đó là bộ đệm, sau
khi lưu xong vào bộ đệm bộ xử lý có thể tiếp tục thực hiện lệnh mới, kết quả lại
tiếp tục lưu vào bộ đệm và cache. Các dữ liệu trong bộ đệm sẽ đồng thời được đưa

ra bộ nhớ chính. Tuy nhiên, do chu kì lưu trữ dữ liệu từ cache xuống bộ đệm ngắn
hơn nhiều so với chu kì lưu trữ dữ liệu từ bộ đệm xuống bộ nhớ chính, do đó có thể
xảy ra hiện tượng tràn bộ đệm. Nếu xảy ra hiện tượng tràn bộ đệm, bộ vi xử lý sẽ
dừng toàn bộ hoạt động hiện thời, chờ cho bộ đệm ghi dữ liệu xuống bộ nhớ chính
và được giải phóng.
3.2.3. Write – back
Write – back là một phương pháp thay thế hoàn hảo cho Write – through và
khắc phục được hiện tượng tràn buffer của Write – buffer.
Khi kết quả một lệnh được đưa ra, nó sẽ chỉ được lưu vào trong cache. Khi
các blocks dữ liệu này cần được thay thế, các dữ liệu trong block sẽ được truyền
xuống các level thấp hơn trong hệ thống phân cấp bộ nhớ.
3.3. Cơ chế xử lý tràn cache
Rõ ràng rằng, một bộ nhớ nhỏ như cache thì việc tràn dữ liệu là điều luôn
phải đối mặt. Khi xảy ra tràn cache, một block dữ liệu trong cache sẽ được thay thế
bằng một block dữ liệu khác, nếu việc xử lý thay thế dữ liệu này không hợp lý sẽ
làm cho miss rate tăng lên. Do đó, các nhà lập trình đã đưa ra một số thuật toán
thay thế dữ liệu cho hiện tượng tràn cache:
16


 Thay thế ngẫu nhiên: các blocks trong cache sẽ có xác suất bị thay thế là như nhau. Khối

bị thay thế sẽ được chọn ngẫu nhiên.
 Khối đã không được sử dụng lâu nhất: mức độ ưu tiên thay thế tùy thuộc vào thời điểm

sử dụng khối đó cuối cùng. Khối nào được sử dụng gần nhất thì sẽ có mức độ ưu tiên
thay thế thấp nhất, và ngược lại, khối nào đã không được dùng từ lâu nhất sẽ có mức độ
ưu tiên thay thế cao nhất.
 Vào trước ra trước (FIFO): khối nào được đưa vào cache đầu tiên sẽ được thay thế đầu


tiên.
 Khối có tần suất sử dụng ít nhất: khối có tần suất sử dụng ít nhất sẽ bị thay thế trước

nhất.

17


4. TÍNH TOÁN HIỆU NĂNG CACHE
Để tính toán hiệu năng cache, ta cần quan tâm đến một số công thức sau:

Để có thể hiểu rõ về các công thức này, ta xem xét một bài toán sau:
Bài toán:
Giả sử có một cache lưu trữ lệnh có miss rate là 2% cho một chương trình,
một cache dữ liệu có miss rate là 4% cho một chương trình. CPI của bộ xử lý bằng
18


2 khi không xảy ra bất kì miss cache nào, miss penalty là 100 chu kì cho tất cả các
miss. Bộ vi xử lý có cache hoàn hảo không xảy ra bất kì miss nào sẽ chạy nhanh
hơn bao nhiêu lần so với bộ vi xử lý này. Cho tần suất của lệnh load và stores của
bộ vi xử lý là 36%.
Lời giải:
Số chu kì mất khi đọc cache lệnh = I x 2% x 100 = 2 x I
Số chu kì mất khi đọc cache dữ liệu = I x 36% x 4% x 100 = 1.44 x I
Vậy tất cả số chu kì vi xử lý phải chờ để đọc bộ nhớ là : 3.44 x I.
Vậy CPI khi xảy ra mất dữ liệu là: CPIstall = CPIperfect + 3.44 x I = 5.44 x I.
Vậy bộ nhớ có cache hoàn hảo sẽ chạy nhanh hơn bộ nhớ xảy ra mất dữ liệu là:
CPIstall / CPIperfect = (5.44 x I) / 2 x I = 2.72 lần


19


5. CÁC PHƯƠNG PHÁP TĂNG HIỆU NĂNG CACHE
Đo đạc hiệu năng cache là một công việc tương đối phức tạp, thể hiện qua
nhiều chỉ số với các đơn vị đo khác nhau, và không chỉ phụ thuộc hoàn toàn vào
cache. Có những chỉ số tưởng như có thể thể hiện hoàn toàn hiệu năng cache như
miss rate hay miss penalty, nhưng thật ra lại thể hiện thiếu sót ở một số mặt nào đó.
Ví dụ như bộ cache A có miss rate cao hơn bộ cache B nhưng bộ cache B lại có
hiệu năng cao hơn bộ nhớ A.
Hiệu năng cache cũng có thể thay đổi khi CPI của bộ vi xử lý, hay băng
thông cache, băng thông của buffer (trong trường hợp sử dụng phương pháp write
buffer) thay đổi. Trong phần này, báo cáo sẽ trình bày một số phương pháp cơ bản
để giảm tối thiểu như chỉ số bất lợi như miss rate, miss penalty cũng như một số
phương pháp tổ chức lại cấu trúc bộ nhớ cache để tăng hiệu năng cache.
5.1. Các phương pháp thay đổi các chỉ số cơ bản
5.1.1. Tăng kích thước dữ liệu trong block
Tăng kích thước dữ liệu trong block tức là tăng số lượng word dữ liệu được
chứa trong một block, điều này sẽ dẫn đến hai lợi điểm:
 Tiết kiệm số bit phải dành cho thẻ tag, dựa trên công thức 2.3.1.
 Tăng xác suất tìm thấy một gói tin trong cache, do nhiều dữ liệu được đưa vào

trong cache hơn. Tức là miss rate sẽ giảm xuống.

20


Tuy nhiên, phương pháp này gặp một bất lợi: tăng miss penalty. Do tính chất
địa phương không gian, một block bao giờ cũng được xử lý hết. Khi kích thước
một block tăng lên, độ trễ khi quét từ word đầu tiên tới word cuối cùng của block

sẽ tăng lên do đó sẽ làm tăng miss penalty. Hiện tượng này có thể được giải quyết
bằng các phương pháp sau:
 Tăng tốc độ chuyển tiếp dữ liệu, phương pháp này đòi hỏi tác động nhiều lên

các cấu trúc phần cứng, do đó tạo ra một số khó khăn nhất định.
 Early restart: phương pháp này sử dụng các thao tác mềm trên bộ xử lý. Như

ta đã xem xét về cơ chế xử lý miss trong cache ở trên, khi xảy ra miss, bộ xử lý
sẽ tạm ngừng mọi hoạt động, chờ dữ liệu được tải về xong rồi mới khởi tạo lại
quá trình nạp lệnh. Với phương pháp này, bộ xử lý sẽ không phải chờ toàn bộ
dữ liệu được tải về, mà chỉ cần chờ word đầu tiên (thường là dữ liệu yêu cầu
trước nhất) được tải về là sẽ khởi tạo lại quá trình nạp lệnh. Thời gian trả về
một word dữ liệu tương ứng với một chu kì xung đồng hồ của vi xử lý. Cơ chế
này rất tiết kiệm thời gian truy cập bộ nhớ, qua đó làm giảm miss penalty. Tuy
nhiên dẫn đến một số xung đội không mong muốn sau:
•

Word dữ liệu cần tìm không nằm ở một vị trí xác định trong cache, do đó thời
gian tải về của các word dữ liệu khác nhau là khác nhau. Vì vậy ta không thể
biết thời điểm nào word được trả về. Do đó không thể biết thời điểm chính xác
để khởi tạo lại quá trình nạp lệnh, nếu tiến trình được thực hiện lại trong lúc
bộ nhớ đang được tải, bộ xử lý sẽ bị treo.

21


•

Trong bộ xử lý đường ống, cũng do không biết chính xác thời điểm word
được trả về, nên có thể một trình tự lệnh khác đang gọi đến bộ nhớ lệnh hoặc

tệp thanh ghi đúng lúc dữ liệu được trả về. Hiện tượng này có thể dẫn đến treo
bộ xử lý hoặc kết quả tính toán bị sai lệch.

5.1.2. Split Caches
Split Caches hay gọi là cắt caches là cơ chế chia cache thành 2 bộ phận
không phụ thuộc nhau, một đảm nhiệm các dữ liệu từ bộ nhớ lệnh, một đảm nhiệm
các dữ liệu từ bộ nhớ dữ liệu.
Cơ chế này làm tăng gấp đôi băng thông qua đó làm giảm miss penalty, tuy
nhiên lại làm cho miss rate biến động. Với bộ nhớ FastMATH ở hình 5, ta có các
thông số sau:
 Kích thước cache: 32Kb
 Miss rate với cơ chế split cache: 3.24%
 Miss rate với cơ chế cache thông thường: 3.18%

Tuy nhiên như đã xem xét ở trên cơ chế split cache đem lại hiệu năng tốt
hơn nhiều. Như vậy có thể thấy không thể chỉ sử dụng miss rate để đánh giá hiệu
năng của cache.
5.1.3. Tổ chức bus
Miss penalty chịu ảnh hưởng lớn từ quá trình trao đổi dữ liệu giữa cache và
DRAM, thời gian này càng dài miss penalty càng lớn. Quá trình trao đổi dữ liệu
giữa cache và DRAM thông qua bus, chu kì bus lại chậm hơn rất nhiều chu kì xung
đồng hồ của bộ xử lý, thường là gấp 10 lần. Nếu băng thông của bus có thể tăng
22


lên (đưa được nhiều dữ liệu vào cache cùng lúc) thì miss penalty sẽ giảm đi đáng
kể. Phần này sẽ đưa ra các cách tổ chức bộ nhớ chính DRAM để tăng băng thông
bus, qua đó giảm các chu kì bus phải sử dụng.

Hình 7. Các cách thức tổ chức bộ nhớ


Để rõ ràng về khả năng giảm miss penalty của các cách tổ chức bộ nhớ này,
ta đưa ra một kịch bản như sau:





Có một bộ nhớ cache tổ chức 4 words/block.
Mất 1 chu kì bus để gửi địa chỉ.
Mất 15 chu kì bus để DRAM đọc dữ liệu.
Mất 1 chu kì bus để gửi một word dữ liệu về cache.

Với tổ chức bộ nhớ thông thường, ta sẽ phải xử lý lần lượt từng word, do đó
cần:
23


1 + 4 x 15 + 4 x 1 = 65 chu kì bus

Với cách thức tổ chức bộ nhớ one-word-wide (Hình 6.a), bộ nhớ được tổ
chức theo dạng ngăn, mỗi ngăn chứa nhiều hơn 1 word. Nếu dạng bộ nhớ là 2
word theo một ngăn thì miss penalty sẽ giảm xuống còn:
1 + 2 x 15 + 2 x 1 = 33 chu kì bus

Với cách thức tổ chức bộ nhớ interleaved (Hình 6.c), bộ nhớ được tổ chức
theo từng băng, lưu trữ lượng dữ liệu như nhau và có khả năng truy cập song song
vào từng băng. Ta giả sử 4 word dữ liệu được đặt trong 4 băng khác nhau, do đó, ta
chỉ cần 15 chu kì bus để đọc cả 4 băng, 4 chu kì bus để gửi dữ liệu về, miss penalty
sẽ giảm xuống:

1 + 15 + 4 x 1 = 20 chu kì bus

Với chỉ một word được truyền, rõ ràng không có gì khác nhau giữa cả ba
cách tổ chức DRAM, tuy nhiên với nhiều word được truyền đi, ta có thể thấy chu
kì bus phải sử dụng được tiết kiệm đáng kể.

24


5.2. Tổ chức lại cấu trúc dữ liệu của cache
Cache có cấu trúc ánh xạ trực tiếp tỏ ra đơn giản trong việc lưu trữ, tuy
nhiên cấu trúc này khiến cho các thuật toán tìm kiếm cũng như lưu dữ liệu kém
linh hoạt do vị trí dữ liệu trong các ô nhớ không thể thay đổi.
Các phương pháp tổ chức dữ liệu của cache đều nhằm mục đích giảm thiểu
số lần miss của cache thông qua việc tạo ra các cấu trúc dữ liệu linh hoạt, giúp tăng
tốc độ tìm kiếm và tăng xác suất dữ liệu cần tìm có trong cache. Hơn nữa còn giảm
số bit cần sử dụng cho trường index, với trường hợp fully associative, số bit cần
cho index là 0.

Hình 8. Ba phương pháp tổ chức cấu trúc dữ liệu của cache.

5.2.1. Fully – associative
Với phương pháp tổ chức Fully – associative, dữ liệu có thể nằm ở bất cứ
block nào của cache. Để tìm kiếm một dữ liệu trong cache, tất cả các block đều
25