HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

NGUYỄN ĐỨC KIỂN
NGHIÊN CỨU VÀ ĐÁNH GIÁ ẢNH HƯỞNG CỦA CẤU
TRÚC MẠNG KẾT NỐI ĐẾN HIỆU NĂNG CỦA SIÊU MÁY
TÍNH
Chuyên nghành: Khoa học máy tính
Mã số: 60.48.01.01
TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2013
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: TS. Hồ Khánh Lâm
Phản biện 1: …………………………………………………………………
Phản biện 2: ……………………………………………………………………
Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện
Công nghệ Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm
Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông
1
MỞ ĐẦU
Đã từ lâu, đi kèm với sự ra đời và phát triển mạnh mẽ của các phần cứng máy tính,
đem lại lợi ích to lớn cho người sử dụng là sự xuất hiện các siêu máy tính đơn bộ xử lý hiện
nay đã đạt được tốc độ và hiệu năng mạnh mẽ, đáng kinh ngạc và đạt tới giới hạn về mặt
phần cứng, về mặt vật lý của công nghệ sản xuất. Điều này đã đóng lại xu thế đơn xử lý và
đòi hỏi phải có một kỹ thuật xử lý tiên tiến khác thay thế để nâng cao hơn nữa khả năng tính
toán của hệ thống xử lý. Hiện nay trên thế giới, các bộ xử lý tiên tiến, các hệ thống tính toán
tích hợp, phức tạp có tốc độ cao đều áp dụng kỹ thuật xử lý song song, coi đây như là một
kỹ thuật tiên tiến, khả thi, có tính mở cao.
Từ các phân tích trên có thể thấy, giải pháp hiệu quả nhất để nâng cao hiệu năng xử

1.2 Phần cứng và kiến trúc của siêu máy tính
Xét theo công suất (tốc độ tính toán, độ rộng từ xử lý, không gian đánh địa chỉ nhớ)
siêu máy tính là loại mạnh nhất nhưng cũng là chi phí cao nhất (hàng trăm nghìn, hàng triệu
USD). Trong những năm 70 hầu hết là các siêu máy tính vector (vector supercomputer)
chuyên ứng dụng để thực hiện các tính toán vector liên quan đến các cấu trúc dữ liệu như
các ma trận và các mảng đa chiều.
Các hệ thống với số lượng lớn các bộ xử lý thường có thể được tạo ra bằng hai cách:
Một là: Ví dụ, trong tính toán lưới (Grid computing) công suất tính toán của một số lượng
lớn các máy tính phân tán, thuộc các nơi quản trị khác nhau, thích hợp được bất cứ khi nào
sẵn sàng. Hai là: Một số lớn các bộ xử lý được sử dụng kết hợp với nhau trong một cụm các
3
nút máy tính. Mỗi nút máy tính sử dụng các bộ xử lý đa lõi (Multi-Core processors) kết hợp
thành bộ xử lý trung tâm là một hướng phát triển chính của công nghệ siêu máy tính hiện
nay, bởi nó cho phép kết hợp đến hàng trăm ngàn bộ xử lý.
Hệ thống tính toán song song ghép cụm là các hệ thống máy tính song song được xây
dựng từ các nút tính toán và thiết bị mạng thông dụng. Mỗi nút tính toán đóng vai trò điều
khiển vào/ra là một hệ thống hoàn chỉnh, có khả năng làm việc độc lập. Hệ thống tính toán
song song ghép cụm là cũng một máy tính song song, trong đó: Các tài nguyên tính toán
bao gồm bộ vi xử lý và bộ nhớ trong tại mỗi nút máy tính, và các tài nguyên tính toán này
kết nối qua mạng (Interconnect network) truyền thông với nhau. Mạng kết nối chỉ giới hạn
trong một mạng cục bộ (LAN) nhưng có nhiều lựa chọn cấu hình khác nhau, trong đó có
một máy tính đóng vai trò máy chủ (Server), các máy tính còn lại đóng vai trò nút tính toán
(Computing node).
Sự thiết lập hệ thống tính toán song song ghép cụm từ những máy tính có cấu trúc
đơn giản sử dụng các công nghệ mạng phổ biến đã được bắt đầu từ năm 1994 với mô hình
Beowulf Cluster của Thomas Sterling và Donal Becker. Hệ thống tính toán song song ghép
cụm rẻ hơn nhiều so với một siêu máy tính cùng sức mạnh. Điều này làm cho các hệ thống
tính toán song song ghép cụm ngày càng phổ biến và đặc biệt phù hợp cho các nước đang
phát triển, các trường đại học.
Tất cả các siêu máy tính đều có kiến trúc song song ở các mức độ khác nhau, và

 Hệ thống làm mát bằng hơi Flourinert
 Làm mát bằng nước ấm
 Làm mát bằng môi trường không khí tự nhiên
1.4. Hiệu năng của các siêu máy tính
1.4.1 Năng lực và khả năng tính toán
Các siêu máy tính có mục tiêu tối đa trong năng lực tính toán (Capability computing)
hơn là khả năng tính toán (Capacity computing). Năng lực tính toán thường được cho là sự
sử dụng tối đa công suất tính toán để giải quyết bài toán lớn trong một quãng thời gian ngắn
nhất. Một hệ thống có năng lực có thể giải một bài toán có kích thước hoặc độ phức tạp mà
không một máy tính nào khác có thể giải được. Ví dụ, ứng dụng mô phỏng thời tiết phức
tạp. Trái lại, khả năng tính toán thường được cho là sự sử dụng hiệu quả chi công suất tính
toán để giải một số nhỏ các bài toán lớn nào đó hoặc một số lớn các bài toán nhỏ. Ví dụ,
nhiều truy nhập của người dùng đến cơ sở dữ liệu hoặc web site.
5
1.4.2 Các số đo hiệu năng
Thông thường, tốc độ của các siêu máy tính được đo bằng FLOPS (FLoating
Point Operations Per Second). Các số đo của FLOPS cho các cấp tốc độ là: GFLOPS
(GigaFLOPS) = 10
9
FLOPS, TFLOPS (TeraFLOPS) = 10
12
FLOPS, PFLOPS (PetaFLOPS)
= 10
15
FLOPS, Petascale = 10
15
(1000 trillion)FLOPS, Exascale = 10
18
FLOPS (1 quintillion
FLOPS = 1 million teraflops). ZettaFLOPS = 1021FLOPS (1 sextillion FLOPS).

D
= 1. Đây là hệ
thống đơn xử lý, là máy tính kiến trúc Von Neumann cổ điển chỉ với một bộ xử lý. Các
lệnh được thực hiện tuần tự nhưng có thể gối chồng theo đường ống. Hầu hết các hệ
thống SISD hiện nay đều có đường ống lệnh, một số đơn vị chức năng, như các bộ
đồng xử lý toán học bổ xung, các đơn vị tính các vector, các bộ xử lý đồ họa và xử lý
vào/ra.
Thường phân các máy tính SISD ra thành hai nhóm:
 SISD với một đơn vị chức năng hay các máy tính hướng tuần tự (Serial scalar
computer
 SISD có nhiều hơn một đơn vị chức năng
Tốc độ thực hiện của các máy tính SISD được đo trong MIPS (Million of
instructions per second)
2.1.2. Một chuỗi lệnh nhiều chuỗi dữ liệu SIMD
SIMD (Single instruction stream multiple data stream) có M
I
= 1, M
D
> 1.
Trong các hệ thống máy tính SIMD có nhiều bộ xử lý làm việc song song với nhau,
thực hiện một mệnh lệnh giống nhau nhưng với những dữ liệu khác nhau. Mỗi bộ xử lý
(Pi, i = 1, 2,…, n) có bộ nhớ cục bộ riêng (Mi, i=1, 2, …n).
2.1.3 Nhiều chuỗi lệnh một chuỗi dữ liệu MISD
M
I
> 1, M
D
= 1. Trong những hệ thống dạng này, một chuỗi dữ liệu từ bộ nhớ chung
M được chuyển đến chuỗi các bộ xử lý được điều khiển bởi từng bộ điều khiển CU riêng và
thực hiện các chuỗi lệnh khác nhau.

Các loại cấu hình kết nối tĩnh của mạng kết nối N
Phân biệt kết nối tĩnh(cố định) và động(nhờ chuyển mạch).
1. 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
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
8
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ổ xung
thêm.
2. Bus chia sẻ đơn (single shared bus)
Kiểu bus đơn này đượ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.
3. Nhiều Bus (multi-bus)
Mạng nhiều Bus 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.

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
.
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.
 Cây tam phân: Trong cây tam phân (ternary tree) 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 ≥ log
3
(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
10
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.
 Cây béo: Cây béo là một 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 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.
 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

8. 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.
9. Các cấu hình lưới: Vòng sợi dây có ưu điểm so với vòng 2 chiều là nó có ‘cắt
ngắn’ (short cut) trong đường dẫn giữa các nút khác nhau. Đường kính của vòng sợi dây là
một hàm phụ thuộc vào số nút trong vòng và ‘độ dài’ của dây. Có một số tuyến cho bản tin
tới đích, nhưng thuật toán định tuyến phức tạp hơn. Nếu vòng sợi có tổng số nút là n thì
tổng số liên kết là 2n. Máy tính song song ILLIAC-IV có mạng kết nối cấu trúc vòng sợi
gồm 64 nút, trong đó các sợi dây kết nối các cặp nút cách xa 9 nút.
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 là N, và n=2, là số chiều, p là số nút của một chiều lưới,
2
ppN
n

,
2/1
Np 
. Số liên kết là
)1(2)1(2
2/12/1
 NNppL
, đường kính là
)1(2)1(2)1(
2/1
 NppnD
, khoảng cách trung bình là
2/1

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) 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ó có số nút ít,
băng thông cao, tăng được không gian sử dụng cho các chip xử lý, và vì các vòng là thống
12
nhất nên thuật toán định tuyến đơn giản. Nếu số nút là N, n là số hướng, p là số nút của một
chiều lưới, thì 2D torus có:
2
ppN
n

, trong đó
2n
, số liên kết là
NpL 22
2

, cấp
độ của nút là d=2n=4, đường kính
2/1
NpD 
, khoảng cách trung bình là
2/1
2
1
N
, và độ
rộng chia đôi (bisection width) là
2/1
22 Np 

tâm, do đó chúng có cấp độ là 1, và sự cố ở nút gốc làm mạng không thể hoạt động. Nếu
tổng số nút trong mạng là n thì nút gốc có cấp độ bằng n-1. Thuật toán định tuyến đơn giản.
Để tăng độ sẵn sàng cần tăng độ tin cậy và khả năng chịu lỗi của nút trung tâm.
11. Mạng kết nối siêu lập thể n chiều (n-dimensional hypercube): Kiến
trúc kết nối lập thể 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
log
,
đường kính
ND
2
log
, số liên kết
NNL
2
log
, độ rộng chia đôi là N/2. Cấp độ của
nút là
Nd
2
log
.
Trong siêu lập thể, một nút (hay đỉnh) là 0-D (hay 0-cube), một đường nối 2 đỉnh là
1D (hay 1-cube), một mạng vuông nối 4 nút gọi là 2D (2-cube), lập thể 3 chiều là 3D (3-
cube), và hai 3-cube nối với nhau gọi là 4D (4-cube),v.v
12. Kết nối đầy đủ: Trong kết nối đầy đủ FCN (full connected network), mỗi một

2
= X
2
 Trạng thái đấu chéo (cross) : Z
1
= X
2
, Z
2
= X
1.
 Trạng thái quảng bá dưới: Z
1
= Z
2
= X
1
.
 Trạnh thái quảng bá dưới: Z
1
= Z
2
= X
2
.
Thành phần chuyển mạch với cấu trúc là chuyển mạch biến đổi được sử dụng trong
các mạng chuyển mạch chịu lỗi. Một cặp ghép kênh (multiplexer) M và tách kênh
(demultiplexer) D được thêm vào cho từng thành phần chuyển mạch S 2x2, và có thể được
điều khiển để bỏ qua hoặc cho phép thành phần chuyển mạch S tham gia vào mạng chuyển
mạch.

phần chuyển mạch được điều khiển để đáp ứng yêu cầu kết nối của từng cặp thành phần xử
lý và thành phần nhớ. Ví dụ, máy tính BBN TC-2000, IBM RP3 sử dụng kết nối mạng
chuyển mạch động nhiều tầng. Các siêu máy tính máy tính Cray Y-MP/816, Fujitsu VPP500
sử dụng mạng chuyển mạch kết nối chéo.
2.4. Kết luận chương: Qua chương này, chúng ta đã có cái nhìn chi tiết về cấu trúc các
mạng kết nối của hệ thống đa xử lý ảnh hưởng đến hiệu năng siêu máy tính, cách phân loại
các loại cấu trúc theo Flynn, các loại kết nối tĩnh của mạng kết nối, các loại cấu hình kết nối
động của mạng kết nối.
15
Chương 3 – ĐÁNH GIÁ ẢNH HƯỞNG CỦA CẤU TRÚC MẠNG KẾT
NỐI ĐẾN HIỆU NĂNG SIÊU MÁY TÍNH
3.1. Luật Amdahl
3.1.1 Công thức Luật Amdahl tổng quát
Luật Amdahl (lấy theo tên của Gene Myron Amdahl, nhà kiến trúc máy tính Mỹ gốc
NaUy, từng là nhân viên của IBM từ 1970, đã đưa ra luật này năm 1967) để tìm kiếm sự
cải thiện mong đợi tối đa của toàn bộ một hệ thống khi chỉ một phần của hệ thống được cải
thiện. Luật Amdahl thường được sử dụng trong tính toán song song để dự đoán sự tăng tốc
tối đa về lý thuyết nhờ sử dụng nhiều bộ xử lý.
Thời gian thực hiện một chương trình gồm có các thành phần:
T
seq
(p) – thời gian thực hiện phần tuần tự vốn có của chương trình.
T
par
(p) – thời gian thực hiện phần của chương trình có thể thực hiện song song.
k(p,n) – overhead truyền thông (communication overhead) là: Thời gian liên quan
cho thực hiện song song (parallel overhead) như: các thao tác truyền thông (thời gian khởi
tạo và kết thúc quá trình hay các luồng, đồng bộ quá trình hay các luồng, truyền thông giữa
các quá trình hay các luồng), thời gian chờ đợi của bộ xử lý và các tính toán dư thừa.
Overhead của xử lý song song thường là hàm tăng của số lượng bộ xử lý. Nó tăng theo số

pTpT
npS
par
seq
parseq




Hiệu năng
),( npE
:
16
- Là số đo mức sử dụng của bộ xử lý
- Là tỷ số của mức tăng tốc S(p,n) trên n bộ xử lý được sử dụng đối với một
chương trình kích thước p:
nnpSnpE /),(),( 
được xác định bằng:
)),(/)()((
)()(
),(
npnpTpTn
pTpT
npE
parseq
parseq





seq
parseq




ta có :
npTpT
pTpT
np
n
pT
pT
pTpT
npS
parseq
parseq
par
seq
parseq
/)()(
)()(
),(
)(
)(
)()(
),(




pT
f
seqpar
seq
parseq
parseq
seq
và overhead truyền thông
0),( npk
, thì Luật Amdahl xác định mức tăng tốc
),( npS
tối đa đạt được nhờ thực hiện trên máy tính song song với n bộ xử lý là:
nff
npS
/)1(
1
),(


(3.2)
Và khi số bộ xử lý
n
thì mức tăng tốc cực đại đạt được là :
f
npS
n
1
),(lim 

(3.3)

là phần trăm của các lệnh được nâng tốc độ (hoặc chậm đi).
k
S
là số nhân tăng tốc (trong đó 1 là không thay đổi tốc độ: không nhanh hơn và
không chậm đi).
k
là chỉ số của từng phần của chương trình.
n
là số phần được chia của chương trình.
Ví dụ, một chương trình thực hiện được chia ra 4 phần: P
1
= 0,11 hay 11%, P
2
= 0,18
hay 18%, P
3
= 0,23 hay 23%, P
4
= 0,48 hay 48%. Cho rằng, phần P
1
không thực hiện tăng
tốc, như vậy S
1
= 1 hay 100%, P
2
được tăng tốc lên 5x, như vậy S
2
= 5 hay 500%, P
3
được










n
k
k
k
S
P
S
P
S
P
S
P
S
P
Như vậy, với Luật Amdahl (3.10) xác định mức tăng tốc độ là 1/0,4575 =
2,186 hơn gấp đôi một chút tốc độ nguyên gốc (không thực hiện tăng tốc).
3.1.2 Luật Amdahl với sự tăng tốc trong một chương trình tuần tự
Cho rằng một chương trình thực hiện (task) có hai phần độc lập, A và B. Phần B
chiếm tới 25% thời gian thực hiện toàn bộ task. Có hai cách tăng tốc độ nhờ thực hiện song
song một phần của chương trình: cách một là thực hiện song song phần B để tăng tốc lên 5x,
nhưng cách này không làm tăng đáng kể tốc độ. Cách thứ hai là thực song song phần A để

bộ xử lý (hay lõi xử lý) để thực hiện song song phần f
để đạt được mức tăng tốc
ns 
, trong khi vẫn giữ nguyên phần tuần tự
)1( f
thì công thức
(3.12) được viết là:
n
f
f
S


)1(
1
(3.7)
Luật Amdahl về mức tăng tốc tối đa (công thức 3.7) bỏ qua thành phần trễ truyền
thông. Thực tế trong các hệ thống siêu máy tính có hàng trăm nghìn nút xử lý, do đó trong
tính toán các ứng dụng song song các tiến trình nằm trên các nút phải trao đổi dữ liệu cho
nhau và điều đó phải tính đến trễ truyền thông giữa chúng. Trễ truyền thông trong các ứng
dụng tính toán song song trên siêu máy tính là 1 thành phần ảnh hưởng đến tốc độ thực hiện
chương trình. Vì vậy khi đánh giá hiệu năng của hệ thống siêu máy tính đã có nhiều công
trình nghiên cứu xét đến vấn đề này. Do đó, trong phần này tôi cũng muốn đưa ra giải pháp
đánh giá hiệu năng siêu máy tính với ảnh hưởng của cấu trúc mạng liên kết các nút xử lý
nhờ sử dụng luật Amdahl mở rộng.
3.1.3 Hiệu ứng Amdahl
Đối với bất kỳ số lượng cố định n nào các bộ xử lý, mức tăng tốc thường được coi là
hàm tăng của kích thước chương trình. Đó chính là hiệu ứng Amdahl.
 Thời gian
),( np

nTs /)1( 
. Tổng thời gian thực hiện chương trình trên hệ thống gồm n nút xử lý
phải là
nTssTT
P
/)1( 
. Khi đó, Luật Amdahl xác định mức tăng tốc tối đa không tính
đến overhead song song:
nssnTssT
TssT
T
T
S
P
/)1(
1
/)1(
)1(





(3.8)
Overhead song song, gọi là
O
T
- không phải là thời gian tính toán hữu ích mà nó gồm:
thời gian khởi động các nhiệm vụ (tạo ra các nhiệm vụ song song và chuyển đến các nút xử
lý song song), các đồng bộ (thiết lập điểm đồng bộ trong một chương trình mà ở đó một

n
s
s
T
T
S
O
P




1
1
(3.10)
Trong đó, n là số nút xử lý, s – tỷ lệ thời gian thực hiện phần tuần tự, T- thời gian
thực hiện chương trình trên một nút xử lý,

O
T
là overhead song song của hệ thống.
Đối với một xử lý CPU+GPU, thì mức tăng tốc tốc đạt được nhờ các GPU – đóng vai
trò của các bộ tăng tốc nhờ chúng có số lõi luồng rất lớn. Như vậy nếu một hệ thống song
song gồm có

CL
N
cluster và mỗi cluster có
CLGPUCPU
N









 ///
1
1
(3.11)
Chờ đợi đồng bộ và
bắt tay truyền thông
Thời gian tính toán
Thời gian truyền
thông
P0
P1
P2
P3
P4
P5
P6
P7
Thời gian thực hiện hiện
datasw
tt 
Rec. ack
syn

//
1
1
(3.12)
Trong đó,

clusterOIntra
T
overhead trong một cluster.
Ví dụ, nếu một nút xử lý CPU+GPU sử dụng 2 Fermi GPU M2070 với 448 lõi cuda,
và cluster có
32
/

 CLGPUCPU
N
thì
)448)(2)(32)(1(
///

 GPUCoresNodeGPUCLGPUCPUCL
NNNNn
.
Một hệ thống có thể có nhiều cluster liên kết với nhau theo một cấu hình mạng kết
nối nào đó của nhiều switch, mỗi cluster lại có thể gồm một hay một số switch liên kết theo
một cấu hình có thể khác hoặc giống như liên kết các cluster. Overhead song song phụ
thuộc vào công nghệ mạng (ethernet, infiniband, ), cấu hình đấu nối (cây nhị phân, cây béo,
2D-mesh, 2D-Torus, 3D-mesh, 3D-Torus, Hypercube, ), kích thước bản tin (dữ liệu
truyền), giao thức truyền thông (MPI, ). Do đó tôi đề xuất công thức tính overhead song
song trong một cluster như sau:

cân bằng tải nên
syn
t
có thể bỏ qua, sử dụng Mellanox SX6036 36-port FDR 56Gb/s
infiniBand/VPI Switch Systems [8] có
nst
sw
170
;
ns
Gbps
t
data
018.0
56
1

, như vậy
22
có thể bỏ qua
data
t
, và trễ truyền thông chủ yếu rơi vào
st
sw

17.0
. Khi đó công thức
(4.6) áp dụng cho cluster sử dụng các Mellanox Infiniband switch có thể xấp xỉ bằng:
))(17.0( wNHsT

cluster đấu nối cấu hình 3D-torus, mỗi cluster có một
switch (cấu hình liên kết star), khi đó:
))(32.0())(17.0(16
4
3
3
3
wNwNTHT
WWclusterOStarIntratorusDO









(3.16)
Nếu cluster có cấu hình 2D-mesh gồm 4 switch và tất cả 16 cluster nối theo cấu hình
2D-torus thì:
wNwNwNHHT
WWWmeshDtorusDO
45.0)(4
3
2
)17.0(16
2
1
))(17.0(

TT
S
clusterOStarIntratorusD 


3
)448)(2)(32)(16(
99.0
01.0
1
Cho rằng một chương trình có thời gian thực hiện trên một nút xử lý CPU+GPU là T =
1 ms, và thuật toán song song chạy trên hệ thống song song mà sự trao đổi dữ liệu giữa các
luồng/nút xử lý CPU+GPU bằng các bản tin có w = 1, và Nw = 64, thì:
23
33
03048217.0
1
)(10
))(64)(32.0(
)10)(17.2(01.0
1
3
6




us
us
S