1

MỞ ĐẦU
I. ĐẶT VẤN ĐỀ
Kiến trúc đa xử lý và vi xử lý đa lõi là những giải pháp công nghệ hiện đại
đang được phát triển để nâng cao hiệu suất của các hệ thống máy tính. Kiến trúc đa
xử lý có thể cho phép kết nối đến hàng trăm nghìn chip vi xử lý đảm bảo xử lý song
song nhiều luồng lệnh, dữ liệu ở tốc độ cao, nhưng lại tiêu tốn nhiều điện năng và
công suất tỏa nhiệt rất lớn. Trong khi đó, nhu cầu dân dụng đòi hỏi tiêu thụ điện
năng thấp, hiệu năng xử lý của hệ thống máy tính phải cao, nhưng giá phải rẻ. Kiến
trúc vi xử lý đa lõi đáp ứng được nhu cầu này. Từ chip 2 lõi được Intel và AMD
tung ra thị trường năm 2001, cho đến nay Tirela sắp cho ra bản thương mại với 80
lõi được tích hợp trong cùng một CPU. Tuy nhiên, nếu sắp xếp các lõi theo kiểu
thông thường thì kích thước CPU sẽ rất lớn, rất cồng kềnh.
Do đó, nghiên cứu các kiến trúc kết nối của các vi xử lý đa lõi để giảm diện
tích, giảm độ dài dây dẫn là vấn đề được nhiều nhà thiết kế 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.
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 cấu trúc kết nối chip đa lõi 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, các phương pháp
đánh giá hiệu năng, dựa vào thực nghiệm, mô phỏng để đánh giá các phương pháp
và tìm ra phương án tối ưu để vi xử lý đa lõi đạt được hiệu năng cũng như mức tăng
tốc tốt nhất.
IV. BỐ CỤC CỦA LUẬN VĂN
Luận văn gồm bốn chương như sau:

core của Intel nên hạn chế dùng).
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ề ngoà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ỉ

3

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.
Nhiều người có thể thắc mắc: Bên trong một CPU liệu có còn khoảng không
gian trống nào không cho nhân thứ hai, thứ tư hoặc nhiều hơn nữa trong khi tấm đế
của CPU vẫn giữ nguyên diện tích như vậy. Thực tế thì kích thước các nhân hiện tại
của CPU đã rất nhỏ, phần đế của mỗi CPU có kích thước như hiện tại bởi chúng cần
có các vị trí để có thể kết nối với các socket. Thông thường thì các ký hiệu của
socket hiện nay có chứa ý nghĩa về số vị trí tiếp xúc giữa CPU và bo mạch chủ, nếu
như một CPU hiện tại của Intel sử dụng socket T (LGA775) hay như AMD sử dụng
socket 939 thì cũng có nghĩa rằng chúng có 775 hay 939 vị trí tiếp xúc. Với một số
lượng kết nối nhiều như vậy thì các CPU nếu thiết kế tấm đế quá nhỏ sẽ không thể
đáp ứng được sự kết nối giữa CPU với bo mạch chủ theo kiểu cắm để dễ dàng thay
thế (nếu không muốn hàn chắc vào bo mạch chủ).
1.1.3. Thế hệ CPU đa lõi thông dụng
1.1.3.1. Thế hệ đầu tiên
Hãng Intel đã giới thiệu những CPU hai nhân Pentium Extreme Edition và
Pentium D đầu tiên vào tháng 4 năm 2005 phát triển trên nền Pentium 4 Prescott.
Thực chất sự ra đời của những CPU hai nhân đầu tiên này của Intel đã mong muốn
giới thiệu ra thị trường càng nhanh càng tốt nên các CPU hai nhân đầu tiên:
Pentium D, Pentium Extreme Edition (thường gọi tắt là Pentium EE) chứa trong
lòng nó hai nhân của Pentium 4 mã Prescot. Mỗi một nhân được giao tiếp với một
đường khác nhau với chipset cầu bắc trên bo mạch chủ. Chính vì vậy mà các chipset

có thể trực tiếp liên kết với nhau mà không phải thông qua chipset cầu bắc. Để hạn
chế nhược điểm này, Intel đã tăng FSB để gia tăng băng thông giữa CPU và chipset
cầu bắc.
Tuy nhiên trong giai đoạn này thiết kế CPU đa lõi của AMD vẫn ưu thế hơn
Intel ở các điểm sau:
• Khác với sự thay đổi cấu trúc của Intel trong CPU hai nhân khiến cho khi
nâng cấp hệ thống cần phải thay thế bo mạch chủ do các chipset cũ không

5

hỗ trợ CPU hai nhân mới. Hệ thống của AMD có thể tương thích với hệ
thống cũ, người sử dụng có thể cần nâng cấp BIOS để có thể tương thích
với CPU hai nhân mới. Socket 939 cho Athlon 64 và Socket 940 cho
Opteron vẫn giữ nguyên cho các CPU AMD hai nhân, cùng với các
chipset cũ vẫn hỗ trợ bởi sự giao tiếp với CPU không trở thành hai dòng
riêng biệt cho mỗi nhân. Đây là ưu điểm thứ nhất của CPU hai nhân
AMD thế hệ đầu với Intel.
• Khi thiết kế các CPU dòng Athlon 64/Opteron AMD đã có một sự chuẩn
bị sẵn cho các thiết kế đa lõi theo định hướng ban đầu của AMD, nên khi
các dòng CPU đa lõi ra đời chúng hoàn toàn thích ứng với các tính toán
về nhiệt độ của CPU. Sự tác động về nhiệt độ khi tăng thêm một nhân đã
ảnh hưởng không nhiều. Ví dụ đa số các CPU hai nhân Athlon 64 X2 của
AMD chạy với tần số 2,2 GHz tiêu thụ công suất 89 W cũng bằng với với
Athlon 64 đơn nhân hoạt động ở tần số 2,4 GHz. So sánh giữa một CPU
hai nhân nóng nhất của AMD khi hoạt động ở tốc độ 2,2 đến 2,4 GHz
tiêu thụ công suất 110 W với một CPU hai nhân của Intel như Pentium
Extreme Edition tiêu thụ công suất 130 W sẽ thấy một ưu điểm thứ hai
của CPU hai nhân hãng AMD so với Intel.
Mặc dù tốc độ xử lý thực của các CPU hai nhân AMD thường thấp hơn CPU
Intel, tuy nhiên một số kết quả kiểm tra, đánh giá hiệu năng bằng các phần mềm

•
Truy xuất bộ nhớ thông minh (Smart Memory Access)
•
Tăng tốc phương tiện số tiên tiến (Advanced Digital Media Boost) giúp
tăng tốc thực thi tập lệnh SEE (Streaming SIMD Extension), cho phép hỗ
trợ các phép toán 128 bit, tức là gấp đôi so với các CPU cũ cùng hãng.
Ngay sau khi ra đời thì Core 2 Duo của Intel đã đánh bại đối thủ cạnh tranh
truyền thống của mình là AMD. Cùng với lộ trình giảm giá các loại sản phẩm
Pentium D, Core Duo, Intel đã lấy lại uy tín và dành lại thị phần của mình sau loạt
sản phẩm CPU hai nhân thế hệ đầu yếu thế hơn so với các CPU hai nhân Althon 64
X2 của AMD.

7

1.1.3.3. CPU ba nhân:
Có thể có CPU ba nhân hay không ? Thực tế ngoài CPU đơn nhân các hãng
thường sản xuất loại đa lõi với số nhân là số chẵn, điều này dường như logic hơn
khi mà thiết đặt các nhân có tính chất đối xứng ở một tấm đế hình vuông.
CPU ba nhân đầu tiên trên thế giới này có mã hiệu Toliman, chúng không
phải là một thiết kế mới ba nhân trên một đế, mà là một CPU bốn nhân đã được cắt
bớt đi một nhân. Nó sẽ tích hợp một điều khiển DDR2, giao diện Hypertransport
3.0, mỗi nhân sử dụng một cache L2 riêng biệt với 512 KB dung lượng. CPU cache
L3 với dung lượng 2 MB.
1.1.3.4. CPU bốn nhân
Với sự phát triển rất nhanh của công nghệ, chỉ một thời gian ngắn, các hãng
sản xuất CPU đã cho ra đời loại bốn nhân dành cho cả dòng máy tính cá nhân để
bàn và các máy trạm, máy chủ. Tuy hiện nay các phần mềm hỗ trợ chưa nhiều, đa
phần người sử dụng còn chưa nâng cấp lên loại CPU hai nhân thì các hãng đã bắt
đầu giảm giá thành sản phẩm để cạnh tranh và hấp dẫn người sử dụng.
Với sự ra đời của 6 bộ vi xử lý bốn nhân Quad-Core Xeon dòng 7300, cho

mạnh nhất so với các CPU hàng đầu hiện nay ngay ở thời điểm quý III năm 2007.
Hai hãng AMD và Intel chưa ra mắt các CPU 8 nhân của mình cho đến thời
điểm đầu năm 2008, nhưng nhiều người vẫn cho rằng hai hãng này đang tích cực
chuẩn bị cho nó. Một số nhà phân tích nhận định rằng rất có thể AMD sẽ chạm đích
trong cuộc đua thời điểm giới thiệu bộ xử lý tám nhân so với Intel trong quá trình
cạnh tranh giữa hai hãng
.

1.1.3.6. CPU công nghệ nano
Trước đây thì chỉ có các “siêu máy tính” hoặc các hệ thống máy tính lớn sử
dụng nhiều CPU mới có khả năng xử lý mạnh mẽ với hàng nghìn tỷ phép tính mỗi

9

giây. Người sử dụng máy tính cá nhân để bàn hiện nay có thể hoàn toàn chạm tới
các tốc độ tính toán đó khi mà Intel đưa ra các CPU đa lõi trong tương lai. Hiện tại
Intel đang thử nghiệm chế tạo các CPU có chứa đến 80 nhân nhưng chưa có kế
hoạch tung chúng ra thị trường.
Các chuyên gia nghiên cứu tại Đại học Tokyo (Nhật Bản) còn công bố một
CPU chứa đến 512 nhân có xung nhịp 500 Mhz với kích thước 17x17 mm với 300
triệu transistor, tiêu thụ công suất chỉ 60 W để phục vụ dự phòng cho các máy chủ.
Những điều này cho thấy rằng công nghệ CPU đa lõi trong tương lai sẽ rất có triển
vọng.
Trở ngại lớn nhất của sự phát triển CPU đa lõi là các kích thước vật lý của
các linh kiện chứa trong lòng nó. Kích thước transistor, tiết diện dây dẫn nội bộ là
những thành phần cơ bản gây cản trở sự phát triển của các CPU đa lõi, mỗi hãng
đều có các công nghệ sản xuất riêng để làm nhỏ kích thước của chúng. Những công
nghệ mới gần đây đã có thể giúp tích hợp trên 2 tỷ transistor trong cùng một CPU.
Công nghệ chế tạo CPU đã tiến đến mức 32 nm (được công bố bởi Intel) và còn tiếp
tục nhỏ hơn nữa (tuy hiện nay nhiều hãng sản xuất vẫn mới áp dụng rộng rãi công

Các thế hệ hai nhân, bốn nhân kế tiếp ra đời thì AMD không còn giữ được
lợi thế về sự nâng cấp hệ thống mà không cần thay đổi bo mạch chủ nữa. Người sử
dụng muốn nâng cấp lên CPU đa lõi cần phải thay thế nhiều thiết bị phần cứng khác
để phù hợp với chúng.
•
Bo mạch chủ là thiết bị phải thay thế đầu tiên bởi các cấu trúc mới không
còn được sự hỗ trợ của chipset thế hệ cũ.
•
Bộ nhớ RAM cũng có sự thay đổi khi thay thế sang loại CPU đa lõi,
chúng thường là loại DDR2 thay thế cho thế hệ DDR đầu tiên để đáp ứng
về tốc độ cho các thế hệ CPU mới.

11

•
Nguồn máy tính cũng là thiết bị cần phải thay thế bởi các hệ thống mới
thường sử dụng nguồn máy tính theo chuẩn ATX loại 24 chân ở phần
cung cấp điện năng cho bo mạch chủ. Riêng phần cung cấp nguồn cho
CPU trước đây thường sử dụng một kết nối 4 chân thì với các hệ thống
mới có thể đòi hỏi kết nối 8 chân.
•
Bo mạch đồ hoạ phải thay đổi nếu hệ thống cũ sử dụng giao tiếp AGP.
Toàn bộ các bo mạch chủ thế hệ mới đều sử dụng khe PCI Express X16.
1.3. KIẾN TRÚC CHIP ĐA LÕI
1.3.1. 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ộ

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
Hình 1.1: Các kiến trúc của chip đa lõi ứng dụng chung

13

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.2: Chip đa lõi có L2 chia sẻ Hình 1.3: Chip đa lõi có L2 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.3.2. 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ác mạng interconnect được
phân biệt hai loại: kết nối tĩnh và kết nối động. 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.

14

Để đá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: toà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


M2

Mm15

• 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 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. • 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.

16

1.3.2.2. 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).

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 ở đầu và cuối 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 toá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à ‘xuôi dòng’ (downstream), một nút nào
đó tiếp nhận bản tin từ ‘dòng xuôi’ 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. Một điều khác biệt 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 cho mở rộng đơn giản, 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 toá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.
1.3.2.3. 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

2
(n+1) và n =
2
h
– 1, độ rộng chia đôi là 1, và đường kính của cây là
)12(log2log2
22
+
=
=
nND
.

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 ≥ log
2
(n+1) = log
2
8 = 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 toán tính SUM đã đề cập.
Hình 1.9:
Cây nhị phân

nhị phân (tầng h). Sau đó mỗi một cặp toán hạng
1
,
+
ii
bb
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ộ:
1+
+
=
iii
bby
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 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 log
2
n lần cộng.
•

Cây tam phân:

1.3.2.4. 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 tạp O(N). Đường kính của mạng vòng D = N/2 nếu liên kết
2 chiều (số N chẵn), và D = N-1 nếu lên kết chỉ một chiều (số N lẻ). Cấp của tất cả
nút trong mạng vòng là 2. Khoảng cách trung bình (N +1)/3, độ rộng chia đôi
(bisection width): 2. Vòng có các đặc tính tương tự như chuỗi và không phù hợp cho các hệ thống
máy tính song song với nhiều bộ xử lý. Nó phù hợp cho kết nối LAN của các bộ xử
lý có kết nối lỏng lẻo và truyền thông không thường xuyên.
•
Vòng sợi dây

Vòng sợi dây (chordal ring) là một cấu hình mở rộng thêm các kết nối giữa
các cặp nút trong tập hợp gồm các nút ở cách xa nhau. Hình 1.17 là ví dụ một vòng
Hình 1.16:
Vòng đa xử lý
Hình 1.11:

Hình 1.17:
Vòng s
ợi dây

(a): lưới vuông
(2D mesh)
(d): lưới 6 cạnh
(Hexagohal grid)
(c): lưới rèm
(b): lư
ới v
òng

(2D torus)
Hình 1.19:
Các cấu trúc lưới
(e): lưới 3D

21

Các cấu hình lưới là các kết nối các nút theo các mẫu đan lưới theo 2, hoặc 3
hướng. Có nhiều loại cấu hình lưới: luới vuông (grid, mesh), lưới 6 cạnh
(hexagonal grid), lưới vòng (torus), lưới toroidal (toroidal grid), lưới 3 chiều (3-D
grid),…
• Lưới vuông (2D mesh):
Tổng số nút của lưới vuông (hình 1.19a) là N, và n=2, là số chiều, p là số
nút của một chiều lưới,

. Độ phức tạp sinh trưởng là
12
2/1
+N
.

Ví
dụ, với nếu p = 5, ta có
255
2
==N
,
40)1(2
=
−
=
ppL
,
8
=
D
. Vì có nhiều đường
dẫn giữa nguồn và đích nên mạng có độ sẵn sàng cao, thuật toán định tuyến có
nhiều lựa chọn đường dẫn tối ưu. Mạng cũng cho dễ dàng mở rộng bởi các nút đang
kết nối không phải thay đổi phần cứng.
• Lưới vòng (2D Torus):
Lưới vòng có cấu hình gồm một lưới vuông 2D và thêm các cạnh bổ xung
vòng quanh, do đó nó còn được gọi là Torus hay 2D Torus. Trong lưới vòng (2D
Torus) (hình 1.19b) tất cả các nút đều có cấp độ d = 4 (4 kết nối) và nằm trên giao
điểm của các đường vòng quấn xung quanh từ trên xuống dưới, từ phải sang trái.

==N
,
502
2
==
pL
,
5
2/1
== ND
.

22

• Luới 3D (3D mesh):
Lưới 3D (hình 1.19e) có tổng số nút là N = p
3
, trong đó p là số nút dọc theo
một cạnh. Các nút ở các góc có cấp độ 3, các nút ở các cạnh có cấp độ 4, các nút ở
mặt có cấp độ 5, và các nút bên trong có cấp độ 6. Độ phức tạp liên kết bằng 3p
2
(p-
1) và đường kính bằng D = 3(p-1). Độ phức hợp sinh trưởng là một hàm của p và
bằng 3p+3p+1.
Mạng lưới 3D có nhiều tuyến cho định tuyến giữa hai nút, nhiều đường dẫn
ngắn nhất có thể chọn lựa, và độ sẵn sàng càng cao.
Có thể xây dựng những mạng lưới 4D, 5D, nhưng sẽ rất khó nhận dạng, và
thường các mảng 3D, 4D hoặc nhiều hướng hơn được sắp xếp thành các lưới 2D.
Lưới 3D thực hiện các bài toán nhanh tối thiểu cũng như lưới 2D, nhưng các bài
toán 2D có thể không luôn sử dụng tất cả các nút của lưới 3D. 1.3.2.7
.
Mạng kết nối siêu lập thể n chiều (n-dimensional hypercube):
Hình 1.21:
Mạng hình sao
Hình 1.22: Các mạng cấu trúc siêu lập thể (Hypercubes)

24 Kiến trúc kết nối lập thể (hình 1.22) còn gọi là kết nối lập phương-n nhị
phân (binary n-cube), vì nếu có n chiều thì có 2n mặt và N = 2
n
nút kết nối
trong khối lập phương, hay
Nn
2

N(N-1)/2. Tất cả các nút đều có cấp độ bằng N-1 (bảng 1.2). Đường kính là 1,
khoảng cách trung bình là 1, độ rộng chia đôi bằng:
2
)2/(
N
nếu N chẵn, và bằng
)4/(
2
N
nếu N lẻ.

Bảng 1.1: Các đặc tính của siêu lập thể
Đặc tính Công thức
Đường kính D = log
2
N = n, trong đó n là số chiều
Độ phức hợp nút N = 2
n

Cấp độ d = log
2
N
Độ phức hợp liên kết L = (Nlog
2
N)/2
Bisection width B = n/2
Độ phức hợp sinh trưởng G = N

25


= X
2
, Z
2
= X
1.

• Trạng thái quảng bá dưới (hình 1.24d): Z
1
= Z
2
= X
1
.
• Trạnh thái quảng bá dưới (hình 1.24e): Z
1
= Z
2
= X
2
.

Bảng 1.2: Các đặc tính của kết nối đầy đủ
Đặc tính Công thức
Đường kính D = 2
Độ phức hợp nút N= 1
Cấp độ d = n-1
Độ phức hợp liên kết L = n(n-1)/2
Bisection width B = 2
Độ phức hợp sinh trưởng G = 1