BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
HỒ VĂN PHI

TỐI ƯU HÓA VÀ ĐÁNH GIÁ HIỆU NĂNG
CỦA TỔ CHỨC CACHE TRONG HỆ
THỐNG VI XỬ LÝ THẾ HỆ SAU LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG

TỐI ƯU HÓA VÀ ĐÁNH GIÁ HIỆU NĂNG
CỦA TỔ CHỨC CACHE TRONG HỆ
THỐNG VI XỬ LÝ THẾ HỆ SAU Chuyên ngành: Kỹ thuật Viễn thông
Mã số: 62520208

LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG NGƯỜI HƯỚNG DẪN KHOA HỌC:

1. TS. HỒ KHÁNH LÂM

2. TS. NGUYỄN VIẾT NGUYÊN Hà Nội - 2014


thông, các Nhà khoa học trong và ngoài Trường Đại học Bách khoa Hà Nội.
Tôi xin trân trọng cảm ơn Lãnh đạo Trường Đại học Quy Nhơn và Khoa Kỹ
thuật & Công nghệ - Trường Đại học Quy Nhơn, cũng như bạn bè đồng nghiệp đã
ủng hộ và tạo mọi điều kiện thuận lợi giúp đỡ tôi trong suốt thời gian học tập,
nghiên cứu và hoàn thành Luận án.
Cuối cùng, tôi muốn dành lời cảm ơn đến những người thân yêu nhất của tôi.
Bản Luận án này là món quà quý giá tôi xin được kính tặng cho cha mẹ, vợ và các
con thân yêu của tôi.
Hà Nội, tháng 06 năm 2014
Tác giả Luận án

Hồ Văn Phi
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
DANH MỤC CÁC BẢNG
DANH MỤC CÁC HÌNH, ẢNH VÀ ĐỒ THỊ
MỞ ĐẦU 1
1. Tính cấp thiết của luận án 1
2. Mục đích nghiên cứu của luận án 4
3. Đối tượng và phạm vi nghiên cứu của luận án 4
4. Phương pháp nghiên cứu của luận án 4
5. Ý nghĩa khoa học và thực tiễn của luận án 5
6. Cấu trúc của luận án 5
Chương 1. TỔNG QUAN VỀ KIẾN TRÚC CHIP ĐA XỬ LÝ, ĐA
LUỒNG 6
1.1. Giới thiệu 6
1.2. Kiến trúc của chip đa xử lý, đa luồng 6

2.2.1.10. Tổ chức cache ảnh hưởng đến tốc độ của CPU 36
2.2.2. Các giải pháp tăng hiệu năng của cache 38
2.3. Các chính sách thay thế dòng cache 38
2.3.1. Chính sách thay thế cache LRU 39
2.3.2. Chính sách thay thế cache LFU 39
2.3.3. Chính sách thay thế cache FIFO 39
2.3.4. Chính sách thay thế cache Random 39
2.3.5. Chính sách thay thế cache NRU 40
2.3.6. Chính sách thay thế cache SRRIP 40
2.3.7. Chính sách thay thế cache DRRIP 42
2.4. Ghi và đọc cache 42 2.4.1. Ghi cache 42
2.4.1.1. Ghi thông qua 43
2.4.1.2. Ghi trở lại 44
2.4.2. Đọc cache 46
2.4.2.1. Đọc bên cạnh 46
2.5.2.2. Đọc thông suốt 47
2.5. Cache chia sẻ thông minh 48
2.5.1. Tổ chức phân cấp cache trong các chip đa xử lý 48
2.5.2. Cache chia sẻ thông minh 49
2.6. Tính nhất quán cache trong các chip đa xử lý, đa luồng 50
2.6.1. Thế nào là nhất quán cache 50
2.6.2. Các giao thức nhất quán cache 52
2.7. Kết luận chương 2 52
Chương 3. PHÂN TÍCH ĐÁNH GIÁ HIỆU NĂNG CỦA TỔ CHỨC
CACHE TRONG KIẾN TRÚC CHIP ĐA XỬ LÝ, ĐA
LUỒNG 53
3.1. Cơ sở lý thuyết để phân tích đánh giá hiệu năng của tổ chức

LUỒNG 85
4.1. Kiến trúc cụm lõi cho chip đa xử lý, đa luồng 85
4.1.1. Khái quát 85
4.1.2. Mô hình MCPFQN cho kiến trúc cụm lõi 86
4.1.2.1. Mô hình MCPFQN tổng quát của kiến trúc cụm lõi 86
4.1.2.2. Mô hình MCPFQN rút gọn của kiến trúc cụm lõi 88
4.1.3. Kết quả mô phỏng và đánh giá hiệu năng cho kiến trúc cụm
lõi 90
4.1.3.1. Kết quả mô phỏng cho kiến trúc cụm lõi 90
4.1.3.2. Đánh giá hiệu năng cho kiến trúc cụm lõi 93
4.2. Lựa chọn cấu hình mạng liên kết trên chip 94
4.2.1. Khái quát 94 4.2.2. Đề xuất công thức tính trễ truyền thông trung bình cho mạng
liên kết trên chip 94
4.2.3. Lựa chọn cấu hình mạng liên kết trên chip 99
4.2.3.1. Kết quả mô phỏng 99
4.2.3.2. Đánh giá kết quả 104
4.3. Kết luận chương 4 104
KẾT LUẬN 106
TÀI LIỆU THAM KHẢO 107
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 115
PHỤ LỤC 116
Phụ lục 1. Kịch bản mô phỏng đánh giá hiệu năng của tổ chức cache
trong kiến trúc CMP đa luồng có 2 cấp cache và 3 cấp
cache 116
Phụ lục 2. Kịch bản mô phỏng đánh giá hiệu năng của tổ chức cache
trong kiến trúc cụm lõi 3 cấp cache 130


B
BCE Base Core Equivalents Tương đương lõi cơ sở
BIP Bimodal Insertion Policy Chính sách chèn hai phương
thức
BRRIP Bimodal Re-Reference Interval
Prediction (Bimodal RRIP)
Hai phương thức dự báo
khoảng tham chiếu lại
C

CAD Computer Aided Design Thiết kế bằng máy tính
ccNUMA cache-coherent Non-Uniform
Memory Access
Truy cập bộ nhớ không đồng
nhất tương quan cache
CD Compact Disk Đĩa compact
CISC Complex Instruction Set Computer Máy tính có tập lệnh phức CMP Chip Multi-Processors Chip đa xử lý
CPI Cycles per Instruction Chu kỳ cho một lệnh
CPU Central Processing Unit Đơn vị xử lý trung tâm
CSM Centralised Shared Memory Bộ nhớ chia sẻ tập trung
CTMC Continuous-Time Markov Chain Chuỗi Markov có thời gian liên
tục
D
DIMM Dual In-line Memory Modules Module bộ nhớ hai hàng chân
DMA Direct Memory Access Truy cập bộ nhớ trực tiếp
DMC Dynamic Multi-core Chip Chip đa lõi linh hoạt
DRAM Dynamic Random-Access Memory RAM động

IMC Integrated Memory Controller Bộ điều khiển bộ nhớ tích hợp
I/O Input/Output Vào/ra
IP Internet Protocol Giao thức Internet
IR Instruction Register Thanh ghi lệnh
J
JMT Java Modelling Tools Công cụ mô phỏng Java
L
LAN Local Area Network Mạng cục bộ
LFU Least Frequently Used Tần suất sử dụng ít nhất
LLC Last Level Cache Cache cấp cuối
LRU Least Recently Used Sử dụng gần đây ít nhất
LSI Large-Scale Integration Tích hợp cỡ lớn
M
MAPI Memory Accesses clock cycles Per
Instruction
Số chu kỳ đồng hồ truy cập bộ
nhớ/lệnh
MAR Memory Address Register Thanh ghi địa chỉ bộ nhớ
MAT Memory Access Time Thời gian truy nhập bộ nhớ
MCPFQN

Multiclass Closed Product-Form
Queuing Network
Mạng xếp hàng đóng đa lớp có
dạng tích các xác suất MESI Modified, Exclusive, Shared or
Invalid (Cache-Protocol)
Sửa đổi, loại trừ, chia sẻ hoặc

PCB Process Control Block Khối điều khiển quá trình
PLD Programmable Logic Device Thiết bị logic lập trình được PMF Probability mass function Hàm khối lượng xác suất
PS Processor Sharing Chia sẻ xử lý
PSELC Policy Selection Counter Bộ đếm lựa chọn chính sách
PSW Processor Status Word Từ trạng thái của bộ xử lý
Q
QPI Quick Path Interconnect Liên kết đường dẫn nhanh
R
RAID Redundant Array of Independent
Disks
Hệ thống đĩa dự phòng
RAM Random Access Memory Bộ nhớ truy cập ngẫu nhiên
RISC Reduced Instruction Set Computer Máy tính với tập lệnh đơn giản
hóa
ROM Read-Only Memory Bộ nhớ chỉ đọc
RRIP Re-Reference Interval Prediction Dự đoán khoảng tham chiếu lại
RRPV Re-reference Prediction Values Giá trị dự đoán tham chiếu lại
S
SD Set Dueling Tranh chấp tay đôi tập hợp
SDM Set Dueling Monitor Bộ giám sát tranh chấp tay đôi
tập hợp
SDRAM Synchronous Dynamic RAM DRAM đồng bộ
SIMD Single Instruction Multiple Data Một lệnh nhiều dữ liệu
SMC Symmetric Multi-core Chip Chip đa lõi đối xứng
SMP Symmetric Multiprocessors Đa xử lý đối xứng
SMT Simultaneous Multi-Threading Đa luồng đồng thời
SoC System on a Chip Hệ thống trên một chip

VLSI Very Large-Scale Integration Tích hợp có quy mô rất lớn DANH MỤC CÁC BẢNG

Bảng 2.1: Tần suất thực hiện các loại lệnh và CPI trong chip kiến trúc RISC. 36
Bảng 3.1: Giá trị trung bình của các thông số hiệu năng khi chip có 2-lõi với 8-
luồng/lõi. 73
Bảng 3.2: Giá trị trung bình của các thông số hiệu năng khi chip có 4-lõi với 8-
luồng/lõi. 77
Bảng 3.3: Giá trị trung bình của các thông số hiệu năng khi chip có 8-lõi với 8-
luồng/lõi. 80
Bảng 4.1: Giá trị trung bình của các thông số hiệu năng khi hệ thống có 2 cụm,
mỗi cụm 4-lõi với L3 cache riêng cho mỗi cụm, và L3 cache chung,
mỗi lõi xử lý 8-luồng. 91
Bảng 4.2: Các thông số của các cấu hình mạng liên kết trên CMP đa luồng 97

DANH MỤC CÁC HÌNH, ẢNH VÀ ĐỒ THỊ

Hình 1: Biểu diễn sự gia tăng transistor trên chip theo định luật Moore 1
Hình 1.1: Kiến trúc chung của CMP đa luồng. 6
Hình 1.2: Kiến trúc phân mảnh của CMP. 7
Hình 1.3: a) SMC gồm n =16 lõi BCE; b) SMC gồm n/r = 4/4 lõi (4 lõi, mỗi lõi
có 4 BCE). 8

Hình 2.20: P1 thực hiện các lệnh: add r1, r2, r4; st x, r1 51
Hình 3.1: Mô hình mạng xếp hàng đóng. 53
Hình 3.2: Các kiến trúc CMP đa luồng. 64
Hình 3.3: Mô hình MCPFQN tổng quát cho CMP đa luồng của hình 3.2. 65
Hình 3.4: Mô hình MCPFQN rút gọn cho CMP đa luồng, 2 cấp cache với L2
cache chung. 67
Hình 3.5: Mô hình MCPFQN rút gọn cho CMP đa luồng, 3 cấp cache với L3
cache chung. 69
Hình 3.6: Mô hình MCPFQN 2-lõi, đa luồng; a) với L2 cache chung và b) với
L3 cache chung. 73
Hình 3.7: Biểu diễn giá trị trung bình của Thời gian chờ đợi ở các nút khi chip
có 2-lõi, mỗi lõi xử lý 8-luồng với L2 cache chung và L3 cache
chung. 74
Hình 3.8: Biểu diễn giá trị trung bình của Thời gian đáp ứng ở các nút khi chip
có 2-lõi, mỗi lõi xử lý 8-luồng với L2 cache chung và L3 cache
chung. 74
Hình 3.9: Biểu diễn giá trị trung bình của Mức độ sử dụng ở các nút khi chip có
2-lõi, mỗi lõi xử lý 8-luồng với L2 cache chung và L3 cache chung. 75
Hình 3.10: Biểu diễn giá trị trung bình của Thông lượng ở các nút khi chip có
2-lõi, mỗi lõi xử lý 8-luồng với L2 cache chung và L3 cache chung. 75
Hình 3.11: Mô hình MCPFQN 4-lõi, đa luồng; a) với L2 cache chung và b) với
L3 cache chung. 76
Hình 3.12: Biểu diễn giá trị trung bình của Thời gian chờ đợi ở các nút khi chip
có 4-lõi, mỗi lõi xử lý 8-luồng với L2 cache chung và L3 cache
chung. 77 Hình 3.13: Biểu diễn giá trị trung bình của Thời gian đáp ứng ở các nút khi
chip có 4-lõi, mỗi lõi xử lý 8-luồng với L2 cache chung và L3 cache
chung. 78
Hình 4.7: Biểu diễn giá trị trung bình của Mức độ sử dụng ở các nút khi hệ
thống có 2-cụm, L3 cache riêng cho mỗi cụm và L3 cache chung cho
8-lõi, mỗi lõi xử lý 8-luồng. 92
Hình 4.8: Biểu diễn giá trị trung bình của Thông lượng ở các nút khi hệ thống
có 2-cụm, L3 cache riêng cho mỗi cụm và L3 cache chung cho 8-lõi,
mỗi lõi xử lý 8-luồng. 93
Hình 4.9: Chip đa lõi với tổ chức cache 3 cấp: L1I, L1D, L2 riêng lẻ cho mỗi
lõi và L3 cache chia sẻ cho tất cả các lõi. 96
Hình 4.10: Trễ truyền thông trung bình của các mạng liên kết Ring, 2DMesh,
2DTorus
,
3DMesh, 3DTorus, cho các trường hợp số lõi trên chip n =
8, 16, 32, 64, 128. 101
Hình 4.11: Mức tăng tốc xử lý của các mạng liên kết Ring, 2DMesh, 2DTorus,
3DMesh, 3DTorus, cho các trường hợp số lõi trên chip n = 8, 16,
32, 64, 128. 104

1

MỞ ĐẦU
1. Tính cấp thiết của luận án
Những tiến bộ trong công nghệ bán dẫn đã thúc đẩy sự phát triển việc thiết kế
hệ thống trên chip. Những gì trước đây được sản xuất trên toàn bộ một bảng mạch,
giờ đây có thể được chế tạo trong một chip duy nhất. Việc tích hợp bộ xử lý và thiết
bị ngoại vi vào trong một chip duy nhất ngày càng trở nên phổ biến trong các hệ
thống nhúng, máy tính xách tay, máy tính để bàn, máy tính quy mô lớn và điện
thoại di động… đã đáp ứng nhu cầu ứng dụng của người tiêu dùng, kinh doanh và
nghiên cứu. Sự tiến bộ này phần lớn được thúc đẩy bởi định luật Moore, định luật

nhà nghiên cứu và sản xuất chip đa lõi hiện nay [28].
Một vấn đề đặt ra cho các nhà nghiên cứu và sản xuất chip đa xử lý, đa luồng
là: với chip đa xử lý thì cần giới hạn bao nhiêu lõi trên chip; chọn bao nhiêu cấp
cache; cấu trúc tổ chức cache như thế nào; dung lượng cache và kích thước dòng
cache là bao nhiêu; đồng thời mạng liên kết trên chip có cấu hình như thế nào để đạt
được hiệu năng tối ưu của bộ xử lý?
Tại Việt Nam vấn đề nghiên cứu và sản xuất chip đa xử lý cũng được bắt đầu
quan tâm và được ưu tiên hàng đầu trong lĩnh vực khoa học và công nghệ nhưng chỉ
là bước đầu sơ khai. Theo [74], ngày 16 tháng 01 năm 2008 tại khu công nghiệp
phần mềm, Đại học Quốc gia Thành phố Hồ Chí Minh đã tổ chức lễ ra mắt “Trung
tâm nghiên cứu và đào tạo thiết kế vi mạch (ICDREC)”, và công bố sản phẩm
SigmaK3 8 bit - chip đa xử lý đầu tiên mang thương hiệu Made in Việt Nam. Thành
3

công của sản phẩm chip đa xử lý 8-bit RISC SigmaK3 góp phần khẳng định Việt
Nam có đủ khả năng tạo được những chip đa xử lý tham gia vào thị trường thế giới.
Sau hơn hai năm tập trung nghiên cứu, ngày 27/10/2010, Trung tâm ICDREC đã
công bố sản xuất thành công chip đa xử lý 32-bit VN1632 với công nghệ IBM
0,13µm đầu tiên tại Việt Nam. Đây được coi là bước tiến mới của ngành công nghệ
vi mạch ở Việt Nam. Đặc biệt, vào ngày 09/11/2013, trung tâm ICDREC thành phố
Hồ Chí Minh và Công ty RADRIX của Nhật Bản đã ký kết Bản ghi nhớ hợp tác
(MOU) về việc phối hợp thiết kế và sản xuất chip. Theo MOU, hai bên sẽ hợp tác
để thực hiện các dự án thiết kế LSI mẫu và hướng đến là chip MPW ở công nghệ
65nm. Sự kiện này đã mở ra một hướng đi mới cho ngành công nghệ chế tạo chip ở
Việt Nam. Tuy nhiên, điều này cũng tạo nên một thách thức mới cho các nhà nghiên
cứu trong nước cũng như trung tâm ICDREC. Hơn thế nữa, trong những năm gần
đây công nghệ vi mạch tích hợp chuyên dụng (ASIC) [65]: PLD và FPGA đã và
đang được các nước đang phát triển và cả ở nước ta quan tâm nghiên cứu ứng dụng
và đưa vào đào tạo. Những công nghệ này cho phép thiết kế các chip đa xử lý, vi
điều khiển, hệ thống trên chip (SoC), hệ thống nhúng, mạng liên kết trên chip

Luận án tập trung nghiên cứu tổ chức cache đa cấp trong kiến trúc chip đa xử
lý, đa luồng.
 Phạm vi nghiên cứu:
- Luận án tập trung nghiên cứu các tổ chức cache 2 cấp (với L1 cache riêng
cho mỗi lõi và L2 cache chia sẻ cho tất cả các lõi), và tổ chức cache 3 cấp (với L1,
L2 cache riêng cho mỗi lõi và L3 cache chia sẻ cho tất cả các lõi) cho các kiến trúc
chip đa xử lý, đa luồng có 2-lõi, 4-lõi, và 8-lõi trên chip.
- Dựa vào mô hình mạng xếp hàng đóng đa lớp có dạng tích các xác suất
(MCPFQN) để phân tích, đánh giá hiệu năng của chip đa xử lý, đa luồng với đa cấp
cache theo các thông số hiệu năng (thời gian chờ đợi, thời gian đáp ứng, mức độ sử
dụng, thông lượng tại các nút, thông lượng hệ thống…). Các thông số hiệu năng này
được xác định bằng phân tích giá trị trung bình (MVA). Đồng thời, tiến hành đánh
giá ảnh hưởng của các cấu hình mạng liên kết trên chip đến hiệu năng của kiến trúc
chip đa lõi đã đề xuất. Trên cơ sở đó, lựa chọn tổ chức cache và cấu hình mạng liên
kết trên chip phù hợp nhất để nâng cao hiệu năng của chip đa xử lý, đa luồng.
4. Phương pháp nghiên cứu của luận án
- Sử dụng lý thuyết mạng xếp hàng đóng đa lớp có dạng tích các xác suất để
xây dựng mô hình cho kiến trúc chip đa xử lý, đa luồng với đa cấp cache.
5

- Sử dụng thuật toán giá trị trung bình (MVA) và tiến hành mô phỏng trên máy
tính bằng phần mềm JMT v.0.8.0 để đánh giá hiệu năng của kiến trúc chip đa xử lý,
đa luồng.
5. Ý nghĩa khoa học và thực tiễn của luận án
Nghiên cứu và đề xuất các kiến trúc chip đa xử lý, đa luồng nhằm nâng cao
hiệu năng xử lý của hệ thống luôn được các nhà nghiên cứu và chế tạo chip trong và
ngoài nước quan tâm và hướng tới. Đây là vấn đề có tính khoa học và thực tiễn cao.
Luận án là nghiên cứu mở đầu về kiến trúc chip đa xử lý, đa luồng ở Việt
Nam. Các mô hình đề xuất và các kết quả nghiên cứu của luận án có thể góp phần
mở ra triển vọng nghiên cứu và chế tạo chip đa xử lý, đa luồng đáp ứng nhu cầu đổi