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

CHU BÁ THÀNH

ĐÁNH GIÁ HIỆU NĂNG
CÁC KIẾN TRÚC VI XỬ LÝ ĐA LÕI

Chuyên ngành: CÔNG NGHỆ THÔNG TIN

LUẬN VĂN THẠC SĨ KỸ THUẬT
CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. HỒ KHÁNH LÂM

Hà Nội - 2013


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

CHU BÁ THÀNH

ĐÁNH GIÁ HIỆU NĂNG
CÁC KIẾN TRÚC VI XỬ LÝ ĐA LÕI

Chuyên ngành: CÔNG NGHỆ THÔNG TIN

LUẬN VĂN THẠC SĨ KỸ THUẬT
CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. HỒ KHÁNH LÂM

Hà Nội - 2013


LỜI CẢM ƠN
Để hoàn thành Luận văn thạc sỹ này, ngồi sự nỗ lực, cố gắng của bản thân, tơi
cịn nhận được sự giúp đỡ rất nhiệt tình của các thầy, cơ, gia đình và bè bạn. Để bày tỏ
lịng biết ơn của mình, tơi xin gửi lời cảm ơn chân thành và sâu sắc đến tập thể Ban
lãnh đạo và cán bộ, giáo viên Viện Công nghệ thông tin & truyền thông, Viện Đào tạo
sau đại học - trường Đại học Bách khoa Hà Nội; Ban lãnh đạo trường Đại học SPKT
Hưng Yên đã tạo điều kiện cho tôi theo học và bảo vệ luận văn khoá học thạc sỹ 20112013.
Tơi xin bày tỏ lịng cảm ơn trân trọng nhất đến TS. Hồ Khánh Lâm - người trực
tiếp hướng dẫn, đã tận tình, tận tâm chỉ bảo, góp ý, giúp đỡ về mọi mặt để tơi hồn
thành luận văn này.
Tơi xin bày tỏ lịng cảm ơn đến gia đình, bạn bè, đồng nghiệp đã động viên,
quan tâm, tạo điều kiện giúp đỡ tôi trong suốt thời gian theo học.
Xin chân thành cảm ơn !

Hà Nội, ngày 19 tháng 3 năm 2013
Học viên

Chu Bá Thành

5



LỜI CAM ĐOAN
Tôi là Chu Bá Thành, tôi xin cam đoan luận văn “Đánh giá hiệu năng các kiến
trúc vi xử lý đã lõi”, là sản phẩm nghiên cứu của cá nhân tơi. Các cơng thức, hình
vẽ,…là chính xác. Kết quả mô phỏng được thực hiện trên Microsoft Excel và JMT
(Java Modelling Tools).

6


MỤC LỤC
MỤC LỤC ................................................................................................................... 2
LỜI CẢM ƠN ............................................................................................................. 5
LỜI CAM ĐOAN ........................................................................................................ 6
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ................................................ 7
DANH MỤC CÁC BẢNG .......................................................................................... 8
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ....................................................................... 9
MỞ ĐẦU................................................................................................................... 12
I. LÝ DO CHỌN ĐỀ TÀI ................................................................................. 12
II. LỊCH SỬ NGHIÊN CỨU ............................................................................. 12
III. MỤC ĐÍCH NGHIÊN CỨU CỦA LUẬN VĂN, ĐỐI TƯỢNG, PHẠM VI
NGHIÊN CỨU. ................................................................................................. 12
IV. TÓM TẮT CƠ BẢN CÁC LUẬN ĐIỂM CƠ BẢN VÀ ĐÓNG GÓP MỚI
CỦA TÁC GIẢ. ................................................................................................ 12
V. PHƯƠNG PHÁP NGHIÊN CỨU ................................................................. 12
NỘI DUNG ............................................................................................................... 14
CHƯƠNG I: TỔNG QUAN VỀ CHIP ĐA LÕI ........................................................ 14
1.1. KHÁI NIỆM VI XỬ LÝ ĐA LÕI ............................................................... 14
1.1.1. Khái niệm chip đa lõi .......................................................................... 14
1.1.2. Kiến trúc chip đa lõi đa luồng .............................................................. 15

1.2. MẠNG KẾT NỐI CÁC LÕI XỬ LÝ TRONG CHIP.................................. 17
1.2.1. Mạng liên kết tĩnh các lõi .................................................................... 17
1.2.2. Các loại cấu hình kết nối động của mạng kết nối N ............................. 30
CHƯƠNG II: LUẬT AMDAHL CHO CÁC CHIP ĐA LÕI ...................................... 40

2


2.1. TÍNH TỐN SONG SONG ....................................................................... 40
2.1.1. Khái niệm tính tốn song song............................................................. 40
2.1.2. Cơng thức mức tăng tốc của thực hiện song song ................................ 43
2.1.3. Phân tích hiệu năng của thực hiện song song ....................................... 43
2.2. LUẬT AMDAHL ....................................................................................... 44
2.2.1. Công thức luật Amdahl tổng quát ........................................................ 44
2.2.2. Luật Amdahl với sự tăng tốc trong một chương trình tuần tự ............... 47
2.2.3. Luật Amdahl cho các chip đa lõi.......................................................... 48
2.2.4. Hiệu ứng Amdahl ................................................................................ 52
2.2.5. Hạn chế của luật Amdahl ..................................................................... 52
CHƯƠNG III: MẠNG HÀNG ĐỢI ........................................................................... 53
3.1. PHÂN LOẠI MẠNG CÁC HÀNG ĐỢI ..................................................... 53
3.1.1. Mạng mở các hàng đợi ........................................................................ 53
3.1.2. Mạng đóng các hàng đợi ...................................................................... 54
3.13. Mạng kếp hợp....................................................................................... 55
3.1.4. Mạng có các ràng buộc số lượng khách hàng ....................................... 55
3. 2. MẠNG HÀNG ĐỢI NHIỀU LỚP CÔNG VIỆC ....................................... 55
3.2.1. Các mạng một lớp công việc................................................................ 55
3.2.2. Các mạng nhiều lớp công việc ............................................................. 57
3. 3. CÁC SỐ ĐO HIỆU NĂNG CỦA MẠNG HÀNG ĐỢI ............................. 59
3.3.1. Các mạng một lớp công việc................................................................ 59
3.3.2. Các mạng nhiều lớp công việc ............................................................. 61

3. 4. CÁC MẠNG HÀNG ĐỢI CĨ NGHIỆM DẠNG TÍCH CÁC XÁC SUẤT 63
3.4.1. Cân bằng toàn cục của mạng hàng đợi ................................................ 64

3


3.4.2. Cân bằng cục bộ .................................................................................. 64
CHƯƠNG IV: PHÂN TÍCH, ĐÁNH GIÁ HIỆU NĂNG CỦA CHIP ĐA LÕI.......... 68
4.1. ĐÁNH GIÁ HIỆU NĂNG THEO LUẬT AMDAHL ................................. 68
4.1.1. Phân tích hiệu năng vi xử lý đa lõi dựa trên luật Amdahl ..................... 68
4.1.2. Đánh giá hiệu năng dựa trên luật Amdahl ............................................ 75
4.2. ĐÁNH GIÁ HIỆU NĂNG THEO MẠNG XẾP HÀNG ĐĨNG CĨ
NGHIỆM DẠNG TÍCH CÁC XÁC SUẤT ....................................................... 82
TÀI LIỆU THAM KHẢO ......................................................................................... 95

4


DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
TT

Từ viết tắt

Giải nghĩa

1.

SMC

Symmetric Multi Core


2.

AMC

Asymmetric Multi Core

3.

DMC

Dynamic Multi Core

4.

CTMC

Continuous Time Markov Chain

7


DANH MỤC CÁC BẢNG

Bảng 1.1: Các đặc tính của cây kim tự tháp ........................................................... 24
Bảng 1.2: Các đặc tính của siêu lập thể ................................................................. 29
Bảng 1.3: Các đặc tính của kết nối đầy đủ ............................................................. 30
Bảng 1.4: So sánh một số cấu hình mạng kết nối động........................................... 38

8



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

Hình 1.1: Các kiến trúc của chip đa lõi ứng dụng chung ........................................... 15
Hình 1.2:Chip đa lõi với L2 cache chia sẻ ................................................................. 16
Hình 1.3:Chip đa lõi L2 cache riêng. ......................................................................... 16
Hình 1.4: Kiến trúc kiểu ngói lợp của chip đa lõi (tiled architecture) với 16 tiles. ..... 17
Hình 1.5: Mạng kết nối N: là bus đơn ........................................................................ 18
Hình 1.6: Mạng nối N: là nhiều bus .......................................................................... 19
Hình 1.7: Mạng kết nối N: là các bus giao nhau ........................................................ 19
Hình 1.8: chuỗi kết nối đa xử lý ................................................................................. 20
Hình 1.9:Cây nhị phân............................................................................................... 21
Hình 1.11:Cây béo ..................................................................................................... 22
Hình 1.10: Cây tam phân ........................................................................................... 22
Hình 1.12: Cây X ....................................................................................................... 22
Hình 1.13: Cây chuỗi hạt ........................................................................................... 23
Hình 1.14: Cây kim tự tháp ........................................................................................ 23
Hình 1.15: Các cấu trúc cây khơng thống nhất .......................................................... 24
Hình 1.16: Vịng đa xử lý ........................................................................................... 25
Hình 1.17: Vịng sợi dây ............................................................................................ 25
Hình 1.19: Các cấu trúc lưới ..................................................................................... 26
Hình 1.20: Vịng 3D (3D torus) 4x4x4 ....................................................................... 28
Hình 1.21: Mạng hình sao ......................................................................................... 28
Hình 1.22: Các mạng cấu trúc siêu lập thể (Hypercubes) .......................................... 29
Hình 1.23: Các cấu mạng kết nối đầy đủ ................................................................... 30

9



Hình 1.24: (a): Thành phần chuyển mạch, (b): Đi thơng (trực tiếp), .......................... 31
(c): Đấu chéo, (d): Quảng bá trên, (e): Quảng bá dưới ............................................. 31
Hình 1.25: Chuyển mạch thay đổi .............................................................................. 32
Hình 1.26: Mạng chuyển mạch 3 tầng ....................................................................... 33
Hình 1.27: Tầng 1 gồm các chuyển mạch ở trạng thái đấu chéo ................................ 34
Hình 1.28: tầng 2 gồm các chuyển mạch ở trạng thái đấu chéo ................................ 34
Hình 1.29: Tầng 3 gồm các chuyển mạch ở trạng thái đấu chéo ............................... 35
Hình 1.30: Mạng chuyển mạch Omega 3 tầng 8x8 ..................................................... 36
Hình 1.31: (a): kết nối xáo trộn N=8; (b): mạng chuyển mạch xáo trộn 1 tầng.......... 36
Hình 1.32: Mạng chuyển mạch 3 tầng (siêu cube) ..................................................... 37
với truyền thơng bình thường ..................................................................................... 37
Hình 1.33: Mạng cube với tầng bổ xung sử dụng các thành phần chuyển mạch biến đổi
để nâng cao độ tin cậy (mạng chịu lỗi) ...................................................................... 38
Hình 1.34: Mạng chuyển mạch đấu chéo 8x8............................................................. 39
Hình 2.1: Mảng tuyến tính hai chiều gồm n bộ xử lý .................................................. 41
Hình 2.2: Diễn giải thời gian thực hiện chương trình song song ................................ 44
Hình 2.3: Luật Amdahl: mức tăng tốc so với tỷ lệ phần trăm của phần tuần tự của
chương trình thực hiện song song. ............................................................................. 47
Hình 2.4: sự tăng tốc thực hiện của một task gồm 2 phần .......................................... 47
Hình 2.5: Chip đa lõi đối xứng (SMC) gồm n =16 lõi BCEs ...................................... 49
Hình 2.6: Chip đa lõi đối xứng (SMC) gồm n/r = 4/4 lõi (4 lõi, mỗi lõi có 4 BCEs) ... 49
Hình 2.8: Chip đa lõi đa lõi linh hoạt (DMC) gồm 16 lõi 1-BCE ............................... 50
Hình 2.7: Chip đa lõi bất đối xứng (AMC) gồm một lõi 4-BCEs và n-4 BCEs ............ 50
Hình 2.9: Hiệu ứng Amdahl: mức tăng tốc so với kích thước của chương trình với bất
kỳ số lượng cố định nào của các bộ xử lý ................................................................... 52

10


Hình 3.1: Mạng mở các hàng đợi .............................................................................. 54

Hình 3.2: Mạng mở các hàng đợi .............................................................................. 54
Hình 3.3: Mạng đóng các hàng đợi............................................................................ 54
Hình 3.4: Mạng kết hợp ............................................................................................. 55
Hình 3.5: Mạng với ràng buộc: ................................................................................. 55
Hình 4.1: Kiến trúc tile của chip đa lõi ...................................................................... 78
Hình 4.2. Mơ hình mạng hàng đợi đóng của hệ thống vi xử lý đa lõi.......................... 82

11


MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI
-

Công nghệ vi xử lý đa lõi đang là xu hướng phát triển của hiện tại và trong
tương lai. Công nghệ này được ứng dụng cho thiết kế, chế tạo các hệ thống máy
tính hiệu năng cao, các siêu máy tính.

-

Cơng nghệ vi xử lý đa lõi được ứng dụng trong nhiều lĩnh vực xử lý tín hiệu tốc
độ cao, thời gian thực và trong những hệ thống cung cấp dịch vụ băng thông
rộng, đa phương tiện hiện tại cũng như tương lai.

-

Đã có nhiều nghiên cứu, thiết kế, chế tạo thử nghiệm chip vi xử lý đa lõi với
nhiều lõi (đến trên 100 lõi), nhưng với rất nhiều kiến trúc kết nối bên trong khác
nhau. Tuy nhiên, hầu như chưa có một kiến trúc nào được cho là tối ưu.


II. LỊCH SỬ NGHIÊN CỨU
Tại Việt Nam, rất ít các cơng trình nghiên cứu về lĩnh vực này. Vì vậy, việc
chọn đề tài cũng là một thử thách tìm hiểu, nghiên cứu các loại kiến trúc chip vi xử lý
đa lõi và ứng dụng một số lý thuyết đã được biết, để đánh giá hiệu năng của các kiến
trúc này, nhằm làm sáng tỏ khả năng ứng dụng của chúng trong từng lĩnh vực cụ thể.
III. MỤC ĐÍCH NGHIÊN CỨU CỦA LUẬN VĂN, ĐỐI TƯỢNG, PHẠM VI
NGHIÊN CỨU.
- Tìm hiểu các loại kiến trúc, tổ chức của một số vi xử lý đa lõi hiện nay.
- Ứng dụng được một số lý thuyết để phân tích, đánh giá hiệu năng của các kiến trúc
vi xử lý đa lõi.
IV. TÓM TẮT CƠ BẢN CÁC LUẬN ĐIỂM CƠ BẢN VÀ ĐÓNG GÓP MỚI
CỦA TÁC GIẢ.
Đề tài đã tập trung nghiên cứu, phân tích kiến trúc và tổ chức các thế hệ chip vi xử
lý đa lõi thông dụng, các yếu tố ảnh hưởng đến hiệu năng và áp dụng các lý thuyết luật
Amdahl, lý thuyết mạng hàng đợi, nhằm đưa ra các phân tích, đánh giá về hiệu năng
hoạt động của các loại vi sử lý đa lõi thơng dụng. Từ đó, đề xuất, lựa chọn loại vi xử lý
phù hợp khi xây dựng hệ thống tính tốn hiệu năng cao, siêu máy tính,…
V. PHƯƠNG PHÁP NGHIÊN CỨU
12


Đề tài sử dụng phương pháp nghiên cứu tài liệu và mô phỏng, đánh giá kết quả.
Phương pháp nghiên cứu tài liệu :
Tìm kiếm, sưu tập, tham khảo, phân tích và nghiên cứu các tài liệu có liên quan
đến đề tài.
Mô phỏng, đánh giá kết quả:
Dựa trên các thông số do nhà sản xuất cung cấp và nghiên cứu luật Amdahl áp
dụng trong các bộ vi xử lý đa lõi, lý thuyết mạng hàng đợi, từ đó bổ sung thêm các
tham số vào luật Amdahl, xây dựng các mơ hình và đánh giá, phân tích kết quả mơ
phỏng.


13


NỘI DUNG
CHƯƠNG I: TỔNG QUAN VỀ CHIP ĐA LÕI
1.1. KHÁI NIỆM VI XỬ LÝ ĐA LÕI
1.1.1. Khái niệm chip đa lõi
Chip đa lõi, hay chip đa nhân, CPU đa lõi (tiếng Anh: multi-core) là bộ vi xử
lý trung tâm (Central Processing Unit) có nhiều đơn vị vi xử lý được tích hợp trên
cùng một CPU vật lý duy nhất. Một cách khác, chúng giống như sự ghép nối nhiều
CPU thông thường trước đây trở thành một CPU duy nhất.
CPU đa lõi được giới thiệu lần đầu tiên vào năm 2001 bởi hãng IBM với loại
CPU Power4 dành riêng cho các máy chủ. Bắt đầu từ đó các hãng sản xuất CPU khác
bắt đầu chú ý đến thể loại CPU đa lõi và định hướng phát triển sản phẩm của mình
theo theo thể loại này. Hai nhà sản xuất CPU cho PC lớn là AMD và Intel cũng có các
phản ứng khác nhau: AMD đã bắt đầu có định hướng ngay cho CPU đa lõi, Intel còn
dè dặt trong giai đoạn đầu, nhưng cũng bắt đầu vào cuộc.[1] Kể từ đó có một sự cạnh
tranh giữa hai hãng để chiếm lĩnh thị phần CPU máy tính trên phương diện đa lõi, hiệu
năng xử lý và giá bán, sự cạnh tranh này vẫn còn tồn tại cho đến thời điểm hiện nay và
chưa có dấu hiệu kết thúc.
Những CPU hai nhân đầu tiên được Intel và AMD sản xuất khi đặt hai nhân xử
lý trong cùng một tấm đế. Có nghĩa trong một CPU nhìn bề ngồi như một CPU thơng
thường nhưng bên trong nó chứa các phần mạch điện của cả hai CPU, điểm chung của
nó là các chân cắm tiếp xúc với socket của bo mạch chủ. Nếu như chỉ nhìn hình dáng
mà khơng nhìn vào các thơng số trên vỏ CPU thì các loại CPU hai nhân này khơng
khác so với các CPU đơn nhân sử dụng cùng loại socket.
Công nghệ chip đa lõi đa luồng là xu hướng chế tạo phổ biến hiện nay của các
nhà sản xuất chip xử lý. Bởi vì các hệ thống máy tính kiến trúc máy tính song song sử
ngày nay được ứng dụng rộng rãi cho các thiết kế các hệ thống máy chủ dịch vụ, tính

tốn hiệu năng cao, siêu tính toán cần đến các chip xử lý đa luồng tạo ra các bộ xử lý
trung tâm tốc độ cao.
14


1.1.2. Kiến trúc chip đa lõi đa luồng
Kiến trúc đa lõi, đa luồng là một trong những giải pháp công nghệ hiện nay
đang được phát triển mạnh nhằm nâng cao hiệu năng của các hệ thống máy tính. Với
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 làm 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 giữa các cache, tăng gánh nặng cho bộ xử lý và bus bộ nhớ.
Hiệu năng của hệ thống vi xử lý đa lõi, đa luồng phụ thuộc rất nhiều vào số
lượng lõi, số luồng trong mỗi lõi, tổ chức cache, dung lượng của cache, số cấp cache
(L1, L2, hay L3) và cấu trúc mạng kết nối bên trong giữa các cấp cache. Điều này, đã
gây nên những hạn chế đáng kể cho kiến trúc vi xử lý đa lõi, đa luồng.

Hình 1.1: Các kiến trúc của chip đa lõi ứng dụng chung

Xu hướng hiện nay trong công nghệ vi xử lý là tập trung vào đa lõi và đa luồng
cho mỗi lõi trong một chip. Chip vi xử lý đa luồng CMT (Chip Multi Threaded) kết
hợp hỗ trợ cho chip đa xử lý CMPs (Chip Multi Processors) cho phép đa lõi nằm trong
cùng một chip để chia sẻ tài nguyên và cải thiện mức độ sử dụng. Đa luồng đồng thời
SMT (Simultaneous Multithreading) cho phép các lõi xử lý riêng trong một chip để
thực hiện các lệnh từ nhiều luồng đơn cùng một lúc (hai, bốn hoặc 8 luồng) còn gọi là
siêu luồng (Hyperthreading).
15


Các chip vi xử lý đa lõi đa luồng yêu cầu phân cấp cache để quản lý độ trễ và
băng thơng. Chúng có thể có 2 cấp cache, hoặc 3 cấp cache (hình 1.1). Trên mỗi lõi

thường có L1cache riêng, L2 cache và L3 cache có thể là riêng hay chia sẻ, và bộ nhớ
chính ln ln được chia sẻ và mỗi lõi . Các hình 1.2 và 1.3 thể hiện chip đa lõi với 2
cấp cache: L2 chia sẻ hay L2 riêng cho từng lõi.

Hình 1.2:Chip đa lõi với L2 cache chia sẻ

Hình 1.3:Chip đa lõi L2 cache riêng.

Cache riêng lẻ có lợi thế: chúng gần lõi, do đó truy cập nhanh hơn, và làm giảm
tranh chấp. Ngoài ra, cache riêng cũng có được vị trí khoảng cách tốt hơn, như tất cả
các dữ liệu cần thiết qua lõi luôn được đưa vào cache của lõi. Cache riêng dễ dàng để
đạt được hiệu năng hơn cache chia sẻ, do ranh giới tự nhiên giữa các cache sắp xếp
cạnh nhau như kiểu ngói lợp (tiles). Kiến trúc đa lõi kiểu ngói lợp (tiles) là kiến trúc
khá phổ biến trong các chế tạo chip đa lõi hiện nay. Chúng cho phép đạt đến vài trăm
lõi xử lý trong một chip. Hình 1.4 là ví dụ chip đa lõi kiểu ngói lợp với 16 ngói (tiles)
trên chip. Mỗi tile gồm core (ống lệnh), caches, chuyển mạch/định tuyến trên
interconnect giữa các lõi. Thường mỗi lõi có L1 và L2 caches riêng.
Nhưng với kiến trúc cache riêng, vấn đề kết nối cache bằng cách sử dụng giao
thức phù hợp để giữ các dữ liệu ổn định qua các cache, giới hạn không gian cache
được dùng không thể chia sẻ các dữ liệu cùng cache đến các luồng trên các lõi khác
nhau và có thể dẫn đến không đồng đều mức độ sử dụng của tồn bộ khơng gian
16


cache. Mức độ sử dụng cache không đồng đều như vậy có thể dẫn đến một sự mất mát
đáng kể tổng hiệu năng của hệ thống.
Chip đa xử lý đa lõi đa luồng, sử dụng cache chia sẻ có lợi thế: độ trễ của thơng
tin ít, một lõi có thể tìm nạp trước dữ liệu cho lõi khác có kích thước cache nhỏ hơn
cần thiết, tắc nghẽn trên phạm vi kết nối bộ nhớ ít hơn, chia sẻ động cho phép sử dụng
hiệu quả chia sẻ không gian cache. Tuy nhiên, với số lượng lõi cao địi hỏi băng thơng

và kích thước cache cao hơn. Độ trễ trúng cache sẽ cao hơn do chuyển đổi logic trên
bộ nhớ cache. Mặt khác, khi thực hiện đồng thời các luồng được tạo ra từ các ứng
dụng khác nhau, tổng hiệu năng của một bộ vi xử lý đa lõi đa luồng có thể suy giảm do
các xung đột giữa các các luồng trong không gian cache chia sẻ, một luồng của một lõi
có thể truy xuất các dữ liệu của một luồng khác và thời gian thực hiện của nó trở nên
dài hơn so với cache riêng .

Hình 1.4: Kiến trúc kiểu ngói lợp của chip đa lõi (tiled architecture) với 16 tiles.

1.2. MẠNG KẾT NỐI CÁC LÕI XỬ LÝ TRONG CHIP
1.2.1. Mạng liên kết tĩnh các lõi
Trong các hệ thống đa xử lý: nhiều chip CPU, hoặc chip đa lõi xử lý, mạng
liên kết (interconnect network) các chip CPU (off chip interconnect) và mạng liên
kết các lõi trong chip (on chip interconnect) đóng vai trị quan trọng ảnh hưởng
đến hiệu năng của hệ thống đa xử lý. Đặc biệt, khi số chip CPU hay số lõi trong
chip tăng lên đáng kể.
Các mạng interconnect được phân biệt thành hai loại: kết nối tĩnh và kết nối
động.

17


Các mạng kết nối động có thể cấu hình lại được nhờ các nút chuyển mạch.
Để đánh giá đặc điểm của các cấu trúc interconnect thường có một số thơng
số cấu hình của cấu hình mạng kết nối:
• Độ phức tạp liên kết: tồn bộ số liên kết trong mạng.
• Cấp độ của nút (node degree): số nút liên kết với một nút (number of
incident nodes).
• Đường kính của mạng (network diameter): khoảng cách định tuyến dài
nhất trong mạng giữa 2 nút (hay độ dài của tuyến dài nhất trong mạng (maximum

routing distance, hay maximum hop distance).
• Khoảng cách trung bình (average distance): là khoảng cách định tuyến
trung bình giữa tất cả các cặp nút (average routing distance hay average hop
distance).
• Độ rộng chia đơi (bisection width): số tối thiểu các liên kết mà sự lấy
chúng ra khỏi mạng sẽ tách mạng và cắt mạng thành 2 nửa.
• Độ phức tạp sinh trưởng (growth complexity): số nút có thể được bổ
sung thêm.
1. Bus chia sẻ đơn (single shared bus):
Kiểu bus đơn này (hình 1.5) được sử dụng nhiều trong các hệ thống máy
kiến trúc Von Neumann cổ điển với một bus hệ thống. Nhưng một nhược điểm
lớn là khi số lượng các thành phần xử lý và thành phần nhớ tăng lên sẽ làm tăng
đụng độ cạnh tranh chiếm bus, dẫn đến tăng thời gian chờ đợi được phục của các
thành phần xử lý và thành phần nhớ, và tốc độ truyền thơng bị suy giảm. Khi đó
cần phải tăng tốc độ bus. Độ sẵn sàng của kết nối bus thấp.

PE1

PE2

PEn

M1

M2

Mm

Hình 1.5: Mạng kết nối N: là bus đơn


2. Nhiều Bus (multi-bus):
Mạng nhiều Bus (hình 1.6) khắc phục nhược điểm của Bus đơn, trong đó,
một số thành phần xử lý và thành phần nhớ kết nối với một Bus, những thành
18


phần xử lý và thành phần nhớ khác lại kết nối với một Bus khác, hoặc có chúng
kết nối cùng trên một số Bus, như vậy sẽ giảm quá tải cho các Bus, sự đụng độ
truy nhập Bus giảm tối thiểu. Nhược điểm của mạng: khi có sự cố xảy ra đối với
một Bus nào đó, thì hiệu xuất mạng giảm đi rõ rệt và lỗi tăng lên.
PE1

PE2

PEn

M1

M2

Mm

Hình 1.6: Mạng nối N: là nhiều bus

3. Các Bus giao nhau (crossbar buses):
Trong cấu trúc kết nối Bus giao nhau (hình 1.7) mỗi thành phần xử lý kết
nối với tất cả thành phần nhớ và tương tự, mỗi thành phần nhớ kết nối với tất cả
thành phần xử lý. Như vậy ta có một kết nối kiểu ma trận hai chiều n x m. Cấu
trúc này khắc phục nhược điểm của cấu trúc nhiều Bus. Trường hợp xấu nhất có
thể xảy ra: nếu tất cả các thành phần xử lý cùng truy nhập vào một thành phần

nhớ. Kết nối này đã được áp dụng một số hệ thống máy tính lớn.
M1

M2

Mm

PE1
PE2

Hình 1.7: Mạng kết nối N:
là các bus giao nhau

PEn

4. Chuỗi (Linear Array):
Cấu trúc chuỗi (chain) là một mảng tuyến tính (linear array) các bộ xử lý
(gồm CPU, memory, I/O), nên thường được gọi là cấu trúc mảng tuyến tính, có
các kết trực tiếp chỉ với các nút xử lý kề cận trung gian (hình 1.8).
19


Hình 1.8: chuỗi kết nối đa xử lý

Cho rằng tổng số nút xử lý là N thì mạng chuỗi này có các thơng số: mỗi một
nút bên trong có cấp độ là 2 (một nút nối 2 kênh), ngoại trừ 2 nút biên chỉ có cấp độ 1,
số liên kết trong mạng là một hàm phụ thuộc vào số lượng nút, O(N) (độ phức tạp liên
kết) của mạng, là L = N-1. Đường kính của mạng, D được tính bằng D = N-1 (một nút
biên nối với N-1 nút). Khoảng cách trung bình là (N-1)/3. Độ rộng chia đơi là 1. Giữa
các nút chỉ có một liên kết nên thuật tốn định tuyến truyền thơng đơn giản, như hệ

thống bus đơn: các bản tin kèm địa chỉ nguồn và đích được chuyển từ một nút nguồn
đến đích là ‘xi dịng’ (downstream), một nút nào đó tiếp nhận bản tin từ ‘dịng xi’
và thu nhận bản tin nếu địa chỉ đích trùng với nút đó, nếu địa chỉ đích khơng trùng thì
bản tin được chuyển ‘ngược dịng’ trở lại’ (upstream).
Cấu trúc chuỗi khác với cấu trúc bus đơn ở chỗ không phải tất cả các nút đều có
thể đọc tất cả các bản tin. Đặc biệt, các nút trong khoảng ‘xuôi dịng’ từ nguồn và
‘ngược dịng’ từ đích sẽ khơng có cơ hội đọc bản tin. Điều này làm khó khăn thực hiện
chuyển các bản tin toàn cục. Một điều khác biệt với cấu trúc bus nữa là chuỗi cho phép
một số các gói của bản tin đồng thời được vận chuyển đảm bảo chúng không gối đè
lên nhau. Chuỗi đơn giản cho mở rộng, bởi vì phần cứng của các nút đang trong mạng
không cần phải thay đổi và thuật tốn định tuyến vẫn duy trì như cũ. Độ sẵn sàng của
chuỗi thấp, tốc độ truyền thông chậm, các nút phải chờ đợi lâu.
5. Kết nối hình cây:
Cấu trúc hình cây có dạng giống với các cây tự nhiên. Chúng bắt đầu với một
nút ở đỉnh gọi là gốc (root). Nút gốc kết nối với các nút khác nhờ các cành. Những nút
ở cành lại kết nối với các nút nhờ các cành rẽ tiếp tạo ra một cây có nhiều cành cao và
thấp, hay một cấu trúc kết nối các nút xử lý đa tầng. Một nút xử lý ở một tầng kết nối
truyền thông trực tiếp với một nút ở tầng trên và một số nút xử lý ở tầng dưới. Nút kề
cận ở tầng trên gọi là nút cha (chỉ có một nút cha), các nút kề cận ở tầng dưới gọi là
các nút con. Kết nối như vậy gọi là tách (disjoint) và khơng có vịng lặp trong cấu trúc.
Cấu trúc cây có một số loại:
• Cây nhị phân:
20


Trong cây nhị phân, hay còn gọi là cây nhị phân đầy đủ, mỗi một nút xử lý ở
một tầng (trừ gốc) có 3 nút kề cận: 1 nút cha và 2 nút con. Giữa hai nút kề cận chỉ một
đường dẫn duy nhất (hình 1.9) và là liên kết 2 chiều.

Hình 1.9:Cây nhị phân


Nếu có cây nhị phân có tổng số N nút, trong đó có n nút bên trong (kể cả gốc),
thì nó có các thơng số như sau: n+1 nút kết thúc (ngọn), tổng số nút N = 2n+1, cấp độ
của nút là 3, số liên kết L=2n-1, chiều cao h (số tầng) là h ≥ log2(n+1) và n = 2h – 1, độ
rộng chia đôi là 1, và đường kính của cây là D = 2 log 2 N = 2 log 2 (2n + 1) .
Ví dụ: với cây nhị phân ở hình 3.19, ta có số nút bên trong n = 7, tổng số nút
ngọn là n+1 = 8, cả cây có tổng số N = 2n+1 = 15, số liên kết L = 2n-1 = 14, và chiều
cao của cây h ≥ log2(n+1) = log28 = 3.
Kết nối hình cây đơn giản, có thể thực hiện đánh địa chỉ nhị phân cho các
nút, đơn giản được thuật toán định tuyến. Các nút Hạn chế của cây nhị phân là có
tốc độ trao đổi chậm, càng lên cao trễ càng lớn và nghẽn nút cổ chai. Các nút con
trao đổi với nhau phải thông qua nút cha. Khi có sự cố xảy ra ở nút cha thì sẽ làm
mất đi liên hệ với các nút con, dẫn tới sự loại bỏ nhiều đơn vị xử lý trong nhánh.
Tuy vậy, dạng cấu trúc kết nối này vẫn được sử dụng ở một số hệ thống máy tính.
Ví dụ, quay lại với bài tốn tính SUM đã đề cập.

SUM= b1 + b2 + b3 +...+ bn ; Trong đó:

n = 2h −1

Q trình giải phép tính SUM này như sau:
Nạp tất cả các toán hạng b1 , b2 , b3 ,..., bn vào 2 h − 1 đơn vị xử lý ngọn của cây nhị
phân (tầng h). Sau đó mỗi một cặp tốn hạng bi , bi +1 chuyển từ các đơn vị xử lý tầng h
lên đơn vị xử lý cha ở tầng h-1 để tính tổng cục bộ: y i = bi + bi +1 và kết quả này nằm
lại trong đơn vị xử lý cha ở tầng h-1. Như vậy sẽ giảm số lượng toán hạng đi một nửa,
tất cả kết quả cục bộ này nằm ở trong các đơn vị xử lý ở tầng h-1. Từ tầng h-1, tất cả
n/2 toán hạng được cộng song song vào các đơn vị xử lý ở tầng h-2. Tại đây, ta có các

21



kết quả cộng cục bộ, và số lượng toán hạng giảm xuống còn n/4. Cuối cùng đạt tới đơn
vị xử lý gốc, và tại gốc có kết quả của phép cộng SUM . Để đạt được kết quả cuối
cùng SUM cần phải có h-1 hay log2n lần cộng.
• Cây tam phân:
Trong cây tam phân (ternary tree) (hình 1.10) mỗi một nút (trừ gốc) có 4 nút kề
cần: 1 nút cha, 3 nút con. Nếu có n nút bên trong (kể cả gốc) thì có 2n +1 nút ngọn, cả
cây có N= 3n+1 nút, 3n-1 cành, và chiều cao h ≥ log3(2n+1).

Cây tam phân có ưu

điểm hơn cây nhị phân là có nhiều nhánh cây hơn, do đó kết nối được nhiều nút con
hơn, nhưng cũng như cây nhị phân nhược điểm lớn của nó lại càng lên cao càng gia
tăng sự chậm chế và nghẽn nút cổ chai.

Hình 1.11:
Cây béo

Hình 1.10: Cây tam phân

• Cây béo:
Cây béo (hình 1.11) là cách khắc phục nhược điểm nghẽn nút của các cây nhị
phân, tam phân bằng cách bổ xung thêm các kết nối giữa các nút con ở cùng tầng dưới
(trừ các nút ở các cành ngoài) nhưng thuộc các nút cha khác nhau ở tầng trên.
• Cây X:
Cây X (hình 1.12) cũng là một cách
khắc phục nghẽn nút cổ chai bằng bổ xung
thêm một kết nối giữa 2 nút ở cùng tầng dưới
nhưng thuộc 2 nút cha ở tầng trên. Các cây X
và béo khơng cịn là các cây rẽ nhánh

(disjoint) vì có các vịng lặp.
22

Hình 1.12:
Cây X


• Cây hình chuỗi hạt:
Một trong những vấn đề lớn trong các cấu trúc cây ở trên là tìm kiến và phân
loại (sort). Các thuật tốn tìm kiếm có thể thực hiện tốt ở trong cây hình chuỗi hạt
(diamon tree) (hình 1.13). Trong cây chuỗi hạt, số lượng các nút N thỏa mãn công thức
tổng của cấp số nhân (sum of geometric progression):
N = (dW - 1)/(d - 1)
Trong đó số lượng các nút N tăng theo độ sâu (hay chiều cao) của cây là W, hay
theo sự tăng của hệ số phân đầu ra của nút (fan-out), d. Số lượng các liên kết của cây
chuỗi hạt được tính bằng:
L = (dW - d)/(d - 1)
Độ phức tạp sinh trưởng G của cây được tính theo : G = (d-1)/(N+1)
Độ phức tạp sinh trưởng của các loại cây là cao so với các cấu trúc khác.

Hình 1.13: Cây chuỗi hạt

• Cây hình kim tự tháp:
•

Hình 1.14: Cây kim tự tháp

Các cây cấu trúc kim tự tháp (pyramid) là một tập hợp con của cấu trúc cây.
Kim tự tháp cho ở hình 1.14 có thể có được từ vẽ lại một cây tứ phân (quaternary tree).
Tất cả các đặc tính cấu hình của cây kim tự tháp tương tự như cây tứ phân (bảng 1.1).


23


Bảng 1.1: Các đặc tính của cây kim tự tháp

Đặc tính
Độ phức hợp nút

Cơng thức
N = (4W - 1)/3 ,

W - độ sâu

(chiều cao)

Độ phức hợp liên kết

L = (4W - 4)/3

Đường kính

D = 2W = 2log4[(3N + 1)/4]
E = 1 đối với các nút ngọn

Cấp độ

E = 4 đối với nút gốc
E = 5 đối với các nút còn lại


Growth Complexity

G = 3N + 1

• Cây có cấu trúc khơng thống nhất:
Hình 1.15 là các cấu trúc cây khơng thống nhất trong đó hệ số phân đầu ra của
nút gốc là 3, và của các nút khác là 2.

Hình 1.15: Các cấu trúc cây
khơng thống nhất

6. Vịng (1D-Torus):
Nhược điểm của cấu chuỗi có thể được khắc phục bằng cấu trúc vịng (Ring)
(hình 1.16). Tất cả các nút xử lý có thể truyền thơng với nhau ngay cả nếu các bản tin
chỉ có thể chuyển theo một hướng. Nếu vịng có N nút thì nó cũng có N liên kết (hay
độ phức hợp liên kết bằng N), nghĩa độ phức tạp liên kết phụ thuộc số nút, O(N). Vịng
có thể vận chuyển các bản tin theo cả hai hướng. do đó nó là vịng 2 chiều. Thường có
tuyến dài và tuyến ngắn giữa các nút truyền thông với nhau. Thuật toán định tuyến
thực hiện định tuyến theo tuyến ngắn nhất nếu tuyến đó đang rỗi. Vịng có mức phức
24