1

LỜI CẢM ƠN.

Trước tiên tôi xin chân thành cám ơn TS Hồ Khánh Lâm, đã luôn tạo điều kiện,
hỗ trợ, hướng dẫn và tận tình chỉ bảo, góp ý và động viên tôi trong suốt thời gian
làm luận văn tốt nghiệp này.
Đặc biệt tôi xin gửi lời cám ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia
giảng dạy lớp Cao Học Điện Tử - Thông tin khóa 2, viện Đại học Mở Hà Nội,
những người đã tận tình hướng d
ẫn truyền đạt kiến thức là nền tảng cho tôi hoàn
thành luận văn này.
Sau cùng tôi xin dành lời cám ơn cho bạn bè tôi, nhưng người đã quan tâm, hỗ
trợ và tạo điều kiện giúp đỡ tôi trong thời gian làm luận văn tốt nghiệp này.
Hà Nội, tháng 10 năm 2011
Tác giả
2.1.Mạng xếp hàng đóng nhiều lớp công việc 33
2.1.1. Mô hình xếp hàng 33
2.1.3.Vi xử lý và công việc trong hệ thống. 37
2.2.Mạng có nghiệm dạng tích xác suất (PFQN) 38
2.2.1.Mạng PFQN Jackson 39

3

2.2.2.Mạng PFQN Gordon Newell 39
2.2.3.Mạng PFQN BCMP 40
2.2.4.Vi xử lý là mạng xếp hàng đóng nhiều lớp công việc có nghiệm tích xác
suất (MCPFQN) 41
CHƯƠNG III 43
THUẬT TOÁN TÍNH HIỆU NĂNG CỦA VI XỬ LÝ ĐA LÕI 43
3.1.Thuật toán phân tích giá trị trung bình 43
3.2.Thuật toán cuộn 49
CHƯƠNG IV 53
ĐỀ XUẤT GIẢI PHÁP MÔ HÌNH HÓA VÀ PHÂN TÍCH HIỆU NĂNG CỦA VI
XỬ LÝ ĐA LÕI 53
4.1.Các mô hình đề
xuất 53
4.2. Sử dụng thuật toán Cuộn để tính toán hiệu năng cho vi xử lý đa lõi. 55
4.2.1.Các thông số cho mô hình 57
4.2.2.Tình hàm F
i
(S
i
) 57
4.2.3.Tính hằng số bình thường hóa 59
4.2.4.Tính các xác suất biên 60

Hình 1.14: Biểu diễn thuật toán LFU với cache 4 dòng (8 lần thay thế) 25
Hình 1.15 : Sự không nhất (a), thống nhất bằng MESI (b) và MOESI (c) 28
Hình 1.16: Kiến trúc vi xử lý 2 lõi của AMD 29
Hình 1.17: UltraSPARC T1 30
Hình 1.18: Sun T5120 Eight Cores x Eight Threads 31
Hình 1.19: Kiến trúc Nehalem 8 lõi với cache L1, L2, L3 của Intel 32
Hình 2.1: Hàng chờ M/M/1 34
Hình 2.2: Hàng chờ M/M/1/K 34
Hình 2.3: Hàng chờ M/M/m 35
Hình 2.4: Mạng xếp hàng mở 36

5

Hình 2.5: Mạng xếp hàng đóng 36
Hình 4.1: Vi xử lý 2 lõi với cache L2 chia sẻ 53
Hình 4.2: Mô hình vi xử lý 2 lõi cache L2 độc lập 54
Hình 4.3: Mô hình vi xử lý đa lõi dùng chung cache L2 54
Hình 4.4: Mô hình vi xử lý đa lõi với cache L2 độc lập nhưng chia sẻ L3 54
Hình 4.5: Mô hình bộ vi xử lý lõi kép có L2 độc lập 55
Hình 4.6: Mô hình tính toán 56
Hình 4.7: WinPepsy mô phỏng mức độ sử dụng của các nút 64
Hình 4.8: Kết quả tính toán mức độ sử dụng của các nút 64
Hình 4.9: WinPepsy mô phỏng thông lượng của các nút 65
Hình 4.10: Kết quả tính toán thông lượng của các nút 65
Hình 4.11: WinPepsy mô phỏng thời gian đáp ứng của các nút 66
Hình 4.12: Kết quả tính toán thời gian đáp ứng của các nút 66
Hình 4.13: Mô hình bộ vi xử lý lõi kép có cache L2 chia sẻ 67
Hình 4.14: WinPepsy mô phỏng mức độ sử dụng của các nút 68
Hình 4.15: Kết quả tính toán mức độ sử dụng của các nút 68
Hình 4.16: WinPepsy mô phỏng thông lượng của các nút 69

năng thông minh, truy nhập bộ nhớ thông minh, bổ xung các tập lệnh đa ph
ương
tiên (MMX, SSE2, SSE3, SSSE3, SSE4), hỗ trợ tập lệnh 64-bit, thay thể bus FSB
bằng QPI (QuickPath Interconnect) tốc độ đạt đến 12,8GB/s (kiến trúc Nehalem –
core i), cho phép năng cao tốc độ xử lý của CPU lên nhiều lần, đồng thời giảm đáng
kể điện năng tiêu thụ (10W ở các chip core 2 Duo) và công suất tỏa nhiệt (TDP) chỉ
17W. Hiệu năng của vi xử lý đa lõi lại phụ thuộc rất nhiều vào công nghệ bộ nhớ
cache, tổ ch
ức cache, dung lượng của cache và của từng dòng cache (khối chứa dữ
liệu), số cấp cache (L1, L2, hay L3), nguyên tắc thay thế cache, và cấu trúc mạng
kết nối bên trong giữa các cấp cache. Xu thế phát triển của công nghệ vi xử lý đa lõi
là tiếp tục tăng số lượng lõi CPU trên một chip, nhưng cũng gia tăng tính phức tạp
của tổ chức cache, số cấp cache, cấu trúc mạng kết nối các cache. Do đó, nghiên
cứu các kiến trúc t
ối ưu của các vi xử lý đa lõi là vấn đề được nhiều nghiên cứu hiện
nay trên thế giới tiến hành. Phân tích đánh gía hiệu năng của các kiến trúc vi xử lý
đa lõi cũng là một vấn đề cần thiết.
7

II. MỤC TIÊU NGHIÊN CỨU CỦA LUẬN VĂN:
Mục tiêu chính của luận văn là tìm hiểu, nghiên cứu về công nghệ vi xử lý
đa lõi cùng với các tổ chức cache khác nhau, tìm hiểu một số công cụ mô phỏng và
đánh giá hiệu năng hiện nay có thể áp dụng cho các kiến trúc vi xử lý đa lõi.

III. NHIỆM VỤ CỦA LUẬN VĂN
Trình bày các kiến trúc phổ biến của vi xử lý đa lõi hiện nay, hệ thống nhớ với
các tổ chức cache của vi xử lý đa lõi, các nguyên tắc thay thế dòng cache, vấn đề

Cấu trúc của m
ột vi xử lý đơn lõi cổ điển gồm có các thanh ghi, ALU, CU, bus
dữ liệu bên trong, giao tiếp với bus bên ngoài… (hình 1.1). Hình 1.1:Sơ đồ tổng quát của vi xử lý đơn lõi cổ điển

Cùng với sự phát triển của công nghệ mạch tích hợp, các chip vi xử lý đơn lõi đã
có những bước tiến dài trong công nghệ chế tạo, từ kiến trúc tập lệnh x86 8/16/32-
bit đến X86 64-bit, từ đơn luồng đến đa luồng, từ đường ống lệnh đơn giản với siêu
đường ống, từ không có cache bên trong chip đến có hệ
thống nhớ phân cấp với hai
ba cấp cache (L1, L2 và L3), từ không có đến có điều khiển nguồn để tiết kiệm điện
năng, từ không có khả năng đến có khả năng kết nối nhiều chip vi xử lý với nhau để
tạo ra CPU đa xử lý, từ tập lệnh phức tạp (CISC) đến có các tập lệnh giảm thiểu

9

(RISC). Mt trong nhng tin b quan trng ca cụng ngh vi x lý n lừi l cú
s phõn cp h thng bus do s khỏc bit v cụng ngh v tc x lý ca cỏc
thnh phn thit b trong h thng vi x lý. S phõn cp h thng bus m bo d
dng ng b cỏc giao dch truyn thụng gia cỏc thnh phn thit b, d dng nõng
cp cụng ngh thit b, d dng tiờu chu
n húa v phi ghộp cỏc thit b. Cựng vi
s phõn chia h thng bus, h thng nh ca h thng mỏy tớnh cng c phõn
chia thnh nhiu cp nh cho hỡnh 1.2. Phân cấp hệ thống nhớ là nhóm các thiết
bị nhớ thành từng cấp theo tốc độ, dung lợng, và kiểu kết nối sao cho chúng đảm
bảo sự truy nhập của chơng trình đến các khoản (lệnh, dữ liệu) đợc thực hiện
nhanh nhất.



1.1.2.
a x lý CMP(Chip Multi Processor)
SIMD (Single Instrucstion stream, Multiple Data stream)
Cỏc mỏy SIMD cú mt s ln cỏc b x lý ging nhau, cỏc b vi x lý ny
cựng thc hin mt lnh ging nhau x lý nhiu dũng d liu khỏc nhau. Mi b
x lý cú b nh d liu riờng, nhng ch cú chung mt b nh lnh v mt b x lý
iu khin, b nh ny c v thi hnh cỏc lnh. Tớnh song song trong cỏc mỏy
SIMD l tớnh song song ca cỏc d liu. Nú ch
cú hiu qu nu cu trỳc cỏc d liu
d dng thớch ng vi cu trỳc vt lý ca cỏc b x lý thnh viờn. Cỏc b x lý vộc-
t v mng thuc loi mỏy tớnh ny. SIMD thng c s dng gii cỏc bi
toỏn d bỏo thi tit nh tớnh nhit trung bỡnh hng ngy trong sut 24 gi ca
nhiu a im, khi ú cụng vic tớnh toỏn l nh nhau nhng tp d liu li hon
ton khỏc nhau

MIMD (Multiple Instruction Stream, Multiple Data Stream)
Mt h thng MIMD l mt h thng nhiu b x lý v nhiu b nh,
trong ú mi b x lý cú mt n v x lý riờng v thc hin chng trỡnh

11

riêng. Các máy MIMD xử lý phân tán thông qua một số các bộ xử lý độc lập,
chia sẻ tài nguyên chứa trong hệ thống bộ nhớ chính, mỗi bộ xử lý thực hiện
độc lập, đồng thời và thực hiện các chương trình riêng. Các hệ thống MIMD thực
hiện các phép toán theo dạng song song không đồng bộ, các nút hoạt động hợp tác
chặt chẽ nhưng thực hiện độc lập. Ví dụ trong hệ thống phục vụ đặt ch
ỗ máy bay,
việc đặt chỗ xảy ra thường xuyên, liên tục và đồng thời, mỗi cuộc đặt chỗ cần một
chương trình để thực hiện, các chương trình này không bắt đầu song song từng lệnh

Có nhiều dạng tính toán song song như song song dữ liệu, song song mức lệnh,
song song nhiệm vụ,…

• Song song mức lệnh Instruction Levsl Parallism (ILP)
ILP được xác
định như là một kỹ thuật đồng thời gọi ra và xử lý nhiều lệnh bên
trong một chip vi xử lý. Trong hệ thống đồng thời có n lệnh được gọi ra trong một
chu kỳ của CPU và cũng nhận được n kết quả trong một chu kỳ. Kỹ thuật này làm
tăng tốc độ của hệ thống nhờ thực hiện tính toán song song các số nguyên và số dấu
phẩy động.
Trong các máy tính sử dụng ki
ến trúc đường ống, siêu vô hướng, máy tính
vectơ, máy tính VLIW, người ta đã dùng tính thực hiện song song các lệnh ở các
mức độ khác nhau để làm tăng hiệu quả của chúng. Giới hạn về khả năng tính toán
của loại các loại máy trên cùng với sự phát triển của công nghệ máy tính khiến
người ta nghĩ tới giải pháp song song theo đó người ta tăng cường hiệu quả của máy
tính bằng cách tăng số lượng bộ x
ử lý.

• Song song mức luồng Task Level Parallism (TLP)
Một luồng thường được gọi là một đơn vị cơ bản của việc sử dụng CPU, một
luồng được hình thành bởi một định danh (thread ID), một bộ đếm chương trình, tập
thanh ghi và ngăn xếp. Một luồng chia sẻ với các luồng khác thuộc cùng một quá
trình hành động (code), phần dữ liệu, và tài nguyên hệ điều hành như các tập tin
đ
ang mở Một quá trình truyền thống chỉ có một luồng điều khiển đơn. Nếu quá
trình có nhiều luồng điều khiển, nó có thể thực hiện nhiều hơn một nhiệm vụ tại một
thời điểm.

13

ếu một phần của nó bị khóa hay đang thực hiện một thao tác dài, do đó
gia tăng sự đáp ứng đối với người dùng. Thí dụ, một trình duyệt web vẫn có thể đáp
ứng người dùng bằng một luồng trong khi một ảnh đang được nạp bằng một luồng
khác.
Sự chia sẻ tài nguyên: Mặc định, các luồng chia sẻ bộ nhớ và các tài nguyên của
các quá trình thuộc về chúng. Thuậ
n lợi của việc chia sẻ là cho phép một ứng dụng
có nhiều hoạt động của các luồng khác nhau nằm trong cùng không gian địa chỉ.

14

Về Kinh tế: Cấp phát bộ nhớ và các tài nguyên cho việc tạo các quá trình là rất
đắt. Vì các luồng chia sẻ tài nguyên của quá trình thuộc về chúng nên nó kinh tế
hơn để tạo và chuyển ngữ cảnh giữa các luồng.
Sử dụng kiến trúc đa xử lý: Các lợi điểm của đa luồng có thể phát huy trong kiến
trúc đa xử lý, ở đó mỗi luồng thực thi song song trên một bộ xử lý khác nhau. Một
quá trình đơ
n luồng chỉ có thể chạy trên một CPU. Đa luồng trên một máy nhiều
CPU gia tăng tính đồng hành. Trong kiến trúc đơn xử lý, CPU thường chuyển đổi
qua lại giữa mỗi luồng thật nhanh để tạo ra hình ảnh của sự song song nhưng trong
thực tế chỉ một luồng đang chạy tại một thời điểm.

• Một số mô hình đa luồng (hình 1.4)
Mô hình nhiều-một: Ánh x
ạ nhiều luồng cấp người dùng tới một luồng cấp
nhân. Vì chỉ một luồng có thể truy xuất nhân tại một thời điểm nên nhiều luồng
không thể chạy song song trên nhiều bộ xử lý.
Mô hình một-một: Mô hình một-một ánh xạ mỗi luồng người dùng tới một
luồng nhân. Nó cung cấp khả năng đồng hành tốt hơn mô hình nhiều-một bằng cách
cho một luồng khác ch

những thành phần không đượ
c sử dụng này có thể dùng để xử lý thread thứ hai, thứ
ba hoặc thứ tư Trong kỹ thuật SMT, mỗi CPU logic sở hữu một tập các thanh ghi
riêng kể cả thanh ghi bộ đếm chương trình PC. CPU vật lý sẽ luân phiên các giai
đoạn tìm/giải mã giữa hai CPU logic và cố gắng thực thi những thao tác từ hai chuỗi
lệnh đồng thời theo cách hướng tới những đơn vị thực thi ít được sử dụng.
Kỹ thuật SMT cho phép các ph
ần mềm ứng dụng được viết cho những máy chủ
đa luồng có thể thực hiện các chỉ thị song song đồng thời trên mỗi bộ xử lý riêng,
bằng cách này sẽ cải thiện tức thì tốc độ giao dịch cũng như thời gian đáp ứng và
các yêu cầu đặc thù khác của phần mềm nghiệp vụ và thương mại điện tử. Công
nghệ này tương thích với các phần m
ềm ứng dụng và hệ điều hành sẵn có trên các
máy chủ, nó cho phép hỗ trợ nhiều người dùng và tăng khối lượng công việc được
xử lý trên một máy chủ. Với các máy trạm cao cấp, công nghệ siêu phân luồng cũng
sẽ tăng đáng kể tốc độ các phần mềm ứng dụng đòi hỏi năng lực tính toán cao, ví dụ
như phần mềm thiết kế 3 chiều, xử lý ả
nh hay video…

16

1.1.4.Vi xử lý đa lõi (Multicore)
Tốc độ xử lý là vấn đề đầu tiên các nhà khoa học luôn trăn trở. Họ luôn muốn
cải tiến tốc độ cho hệ thống. Trải qua rất nhiều thế hệ tốc độ đã tăng một cách
chóng mặt, từ 4.77MHz của vi xử lý i8086, rồi đến 100MHz của vi xử lý i80486,
tiếp theo là 1.7MHz của vi xử lý Pentium IV,…Song song với nâng cao tốc độ là sự
tăng dần khả nă
ng xử lý dữ lý dữ liệu của vi xử lý (thông lượng). Khả năng xử lý dữ
liệu đã tăng từ 4 bit ban đầu cho đến hiện nay là 32bit, 64bit,…Cùng với việc nâng
cao tốc độ và tăng thông lượng thì giải pháp hỗ trợ đa xử lý cũng được đưa vào (tích


tính đa lõi khắc phục được nhược điểm của các bộ vi xử lý đơn lõi trước đó vì việc
thiết kê các chip đơn với tốc độ khoảng trên dưới 2GHz tương đối đơn giản và
không đòi hỏi sự đầu tư về công nghệ mới. Các máy tính đa lõi tiêu thụ điện năng
thấp hơn, tiếng ồn cũng giảm. Điều quan trọng nhất là vi xử
lý đa lõi đáp ứng kịp
thời đòi hỏi của các phần mềm tính toán song song như các chương trình chơi
Game, hoặc các dịch vụ Multimedia…Máy tính đa lõi là công nghệ kết hợp giữa đa
xử lý và kỹ thuật tính toán song song (hình 1.5). Hình 1.5: Đa lõi là kết hợp đa xử lý và tính toán song song
• Một số mô hình Multicore
Trong các bộ vi xử lý đa lõi, cấu trúc bên trong tương đối giống nhau. Sự khác
biệt là ở số lượng lõi và đặc biệt là các cấu trúc cache có thay đổi khá nhiều nhất là
Cache L2. Với các vi xử lý lõi kép được xây dựng trên nền kiến trúc của Pentium D
và AMD thì mỗi lõi đều có Cache L2 riêng (hình 1.6). Chính vì vậy mỗi lõi sẽ làm
việc như nó đang làm việc cho một CPU độc lậ
p. Với Cache riêng thì tại một thời
điểm nào đó một lõi có thể phải chạy quá tải trong khi đó lõi kia lại không được sử
dụng hoặc sử dụng không hết hiệu suất. Khi đó lõi chạy quá tải sẽ phải lấy dữ liệu
từ bộ nhớ chính trong khi không gian trên Cache L2 kia hoàn toàn trống mà lẽ ra
được sử dụng để lưu dữ liệu, điều này làm giảm hiệu suất củ
a toàn hệ thống. Trước
khi mỗi lõi truy xuất bản sao của dữ liệu trên Cache L2 của mình, để đảm bảo đó là
bản sao mới nhất của dữ liệu. Điều này tương đối phức tạp vì dữ liệu có thể đã được



19

• Multicore và SMT
Theo sự phát triển, các phần mềm ứng dụng viết cho những máy chủ đa luồng
hay các hệ điều hành mới yêu cầu tốc độ mà mỗi vi xử lý thực hiện các lệnh ngày
càng cao, tăng tốc độ xung nhịp với các CPU là phương pháp chủ yếu người ta đưa
ngày càng nhiều mạch bán dẫn vào một bộ chip, điều này sẽ khiến cho CPU phát
sinh nhiều nhiệt và một số thí nghiệ
m đã cho thấy CPU sẽ không còn hoạt động
hiệu quả nữa.
Công nghệ đa lõi sẽ giải quyết vấn đề trên, nó cho phép một bộ xử lý có thể
chứa 2 lõi hoặc nhiều hơn. Các lõi này sẽ hoạt động song song với nhau, chia sẻ
công việc tính toán xử lý mà bộ xử lý phải đảm nhận, nó có thể thực hiện 4 luồng,
thậm chí 8 luồng song song. Việc có hai lõi hoặc nhiều hơn giúp bộ xử lý hoạ
t động
hiệu quả và có công suất cao hơn mà không cần phải tăng xung nhịp, vì mỗi lõi sẽ
xử lý ít ứng dụng hơn, giảm hiện tượng bộ xử lý phải cùng một lúc gánh vác công
việc của nhiều ứng dụng.

1.1.5.Các ứng dụng của Multicore
• Database server
Database server (hình 1.8) là dịch vụ kết nối trực tiếp đến máy chủ chứa cơ
sở dữ liệu. Server là một máy chủ mà trên đ
ó có cài đặt phần mềm Hệ quản trị Cơ
sở dữ liệu (HQTCSDL). Chúng ta có một số HQTCSDL chẳng hạn như: SQL
Server, MySQL, Oracle… dịch vụ Database server hoàn toàn đạt hiệu quả nếu hệ
thống được thiết kê có bộ nhớ được chia sẻ kiểu kiến trúc MIMD UMA.

• Web server

vẽ. AutoCAD là phần mềm thuộc dạng này có mặt rất sớm và do đó rất phổ biến ở
Việt Nam. Kết quả của CAD là mộ
t bản vẽ xác định, một sự biểu diễn nhiều hình
chiếu khác nhau của một chi tiết cơ khí với các đặc trưng hình học và chức năng
CAM là một hoạt động cụ thể trong công nghệ chế tạo cơ khí. Kết quả của
CAM là cụ thể, đó là chi tiết cơ khí. Trong CAM không truyền đạt một sự biểu diễn

21

của thực thể mà thực hiện một cách cụ thể công việc. Việc chế tạo bao gồm các vấn
đề liên quan đến vật thể, cắt gọt vật liệu, công suất của trang thiết bị, các điều kiện
sản xuất khác nhau có giá thành nhỏ nhất.
CAD/CAM tương ứng với các hoạt động của hai quá trình hỗ trợ cho phép
biến một ý tưởng trừu tượng thành một vật th
ể thật. Hai quá trình này thể hiện rõ
trong công việc nghiên cứu và triển khai chế tạo. Xuất phát từ nhu cầu cho trước,
việc nghiên cứu đảm nhận thiết kế một mô hình mẫu cho đến khi thể hiện trên bản
vẽ biễu diễn chi tiết. Từ bản vẽ chi tiết, việc triển khai chế tạo đảm nhận lập ra quá
trình chế tạo các chi tiết cùng các vấn đề liên quan đến dụng cụ và phươ
ng pháp
thực hiện. Hai lĩnh vực hoạt động lớn này trong ngành chế tạo máy được thực hiện
liên tiếp nhau và được phân biệt bởi kết quả của nó.

1.2. Bộ nhớ trong vi xử lý đa lõi
1.2.1.Tổ chức bộ nhớ của vi xử lý đa lõi
Cũng như vi xử lý đơn lõi, tổ chức bộ nhớ của vi xử lý đa lõi được phân ra một
số cấp nh
ớ. Trong đó, các cấp cache thường sử dụng tổ chức liên kết tập hợp n-dòng
(n-way set association), với số dòng n = 2,4,8. Nhiều vi xử lý đa lõi sử dụng hai cấp
cache: L1 Cache và L2 Cache. L1 cache (L1Icache và L1Dcache) riêng cho từng lõi
Core 1
Core 1
Core 1
L1 cache
L1 cache
L1 cache
L1 cache
L1 cache
L1 cache
L3 cache
(smart cache)
L1 cache
L1 cache
L1 cache
MM
Interconnect networ
k

Memo
r
y
bus
Hình 1.11: nguyên tắc tham chiếu của các lõi CPU đến các cấp nhớ

23
24

Chính sách thay thế FIFO mặc dù dễ hiểu và dễ lập trình. Nhưng hiệu năng của
nó không cao. Các khối dữ liệu được nạp vào cache sớm thường là quan trọng,
chứa nhiều dữ liệu cần thiết thậm chí là các lệnh bắt đầu của một chương trình, thế
nhưng nó lại bị đẩy ra đầu tiên. Chúng ta hãy hình dung chương trình sẽ luôn phải
bắt đầu và không bao giờ kết thúc.

• Chính sách tối ưu OPT
Trong chính sách OPT (optimal) dòng cache “nạn nhân” là dòng chứa nội dung
dữ liệu chưa được dùng trong một khoảng thời gian lâu nhất (đã chờ lâu nhất mà
chưa được sử dụng đến). Với ví dụ ở hình 1.12 ta sử dụng chính sách OPT thì chỉ
phải thay thế 6 lần cho cache 4 dòng và 7 lần cho với cache 3 dòng (hình 1.13).
Hình 1.13: Biểu diễn thuật toán OPT với cache 4 dòng (6 lần thay thế)

Chính sách OPT có tỉ lệ thay thế thấp nhất trong tất cả các chính sách, và nó
không khả thi vì các thao tác tiếp theo phụ thuộc vào các yêu cầu truy nhập mà
CPU sau một quá trình xử lý đưa ra, nếu để CPU phải quan tâm trước đến tương lai
thì xem ra không khả thi vì con người chúng ta còn khó biết trước tương lai của
chính mình.
• Chính sách LRU (Least Recently Used)
Chính sách thay thế LRU gắn mỗi khối với thời gian sử dụng cuối cùng của khố
i
đó. Khi thay thế, khối “nạn nhân” là khối dữ liệu gần đây ít được sử dụng nhất.
LRU là chính sách thay thế dòng cache tối ưu. Nó thực hiện tìm kiếm lùi về quá

Hình 1.15: Biểu diễn thuật toán LFU với cache 4 dòng (8 lần thay thế)
• Chính sách ngẫu nhiên (Random)
Chính sách thay thế dòng cache ngẫu nhiên phân bố đồng đều khả năng bị thay
thế, các khối cần thay thế trong cache sẽ được chọn ngẫu nhiên. Cache ánh xạ trực
tiếp không có sự chọn lựa thay thế, vì mỗi khối chỉ được sắp xếp vào một dòng
tương ứng.
1.2.3. Các chính sách thay thế cache cho vi xử lý đa lõi