BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
NGUYỄN MINH QUÝ

PHÂN TÍCH ẢNH HƯỞNG CỦA TRỄ TRUYỀN THÔNG
ĐẾN HIỆU NĂNG CỦA HỆ THỐNG TÍNH TOÁN
SONG SONG
CHUYÊN NGÀNH: KỸ THUẬT PHẦN MỀM
MÃ SỐ: 62480103
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT PHẦN MỀM


Vào hồi …… giờ, ngày … tháng … năm ……… Có thể tìm hiểu luận án tại:
1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội
2. Thư viện Quốc gia Việt Nam 1

MỞ ĐẦU
1. Lý do chọn đề tài
Khi nghiên cứu về các hệ thống tính toán song song thì một
vấn đề rất quan trọng thường hay đề cập đến, đó chính là Hiệu
năng. Trên thực tế, khi thêm các nút tính toán vào hệ thống thì
mong muốn của chúng ta là hiệu năng hay tốc độ sẽ tăng lên tương
ứng. Tuy nhiên, một điều rất rõ ràng là tốc độ tăng lên này sẽ có
xu hướng giảm dần. Có rất nhiều nguyên nhân ảnh hưởng đến hiệu
năng của toàn bộ hệ thống, có thể kể ra như: cấu hình mạng liên
kết, các trễ truyền thông, kiến trúc bộ nhớ chia sẻ, kiến trúc cache,
kiến trúc chip đa lõi, thuật toán của người dùng, công cụ phần
mềm hỗ trợ lập trình song song v.v
Như vậy, việc xác định và phân tích rõ ảnh hưởng của các yếu
tố kể đến hiệu năng của hệ thống là một bài toán vô cùng quan
trọng và cần thiết bởi khi đã xác định rõ được sự ảnh hưởng của
các thông số này, người ta hoàn toàn có thể điều chỉnh chúng để

năng lực tính toán giống nhau, cùng hoàn thành công việc với
khoảng thời gian như nhau.
Ngoài ra, luận án cũng chỉ tập trung nghiên cứu đối với các hệ
thống tính toán song song mà ở đó sự trao đổi thông tin là không nhỏ
giữa các phần tử tính toán. Còn đối với các hệ thống tính toán mà
các phần tử ít trao đổi thông tin với nhau và ít phải chờ đợi, lệ thuộc
nhau về dữ liệu và tài nguyên thì có thể bỏ qua trễ này.
4. Ý nghĩa khoa học và thực tiễn của đề tài
4.1 Ý nghĩa khoa học
Về mặt khoa học, công thức đề xuất để tính trễ truyền thông
trong luận án có thể làm cơ sở để nghiên cứu tính trễ cho rất nhiều
các loại liên kết mạng khác nhau. Ngoài ra, phương pháp sử dụng
mạng Petri để phân tích hiệu năng là một cách tiếp cận mới ngoài
phương pháp truyền thống là sử dụng mô hình mạng hàng đợi.
4.2 Ý nghĩa thực tiễn
Kết quả nghiên cứu trong luận án có thể được sử dụng vào
việc lựa chọn loại liên kết mạng phù hợp nhất cho mỗi loại ứng
dụng với kích thước các gói tin khác nhau để giảm thiểu nhất trễ
3

truyền thông, từ đó có được hiệu năng cao nhất cho toàn bộ hệ
thống.
Dựa vào công thức tính toán trễ được đề xuất, các hệ thống
phần mềm tính toán có thể tìm các giải pháp về thuật toán trong
chương trình để giảm thiểu các truyền thông không cần thiết, tránh
được các trễ khi thực hiện giao tiếp giữa các nút tính toán.
Phần xây dựng chương trình và thuật toán thám mã mật khẩu
của MS Office Word có thể mở rộng để xử lý trên hệ thống với
nhiều nút tính toán hơn và có tích hợp các bộ tăng tốc đồ họa để
có thể giải quyết nhiều bài toán thám mã tương tự khác, như khôi

tính toán song song, các kỹ thuật phân tích và phương pháp đánh
giá hiệu năng. Các nghiên cứu liên quan ở trong và ngoài nước về
lĩnh vực này cũng được đề cập và phân tích.
- Chương 2: Trình bày các cơ sở lý thuyết sẽ được sử dụng
trong luận án để phân tích hiệu năng, đó là mạng hàng đợi
(Queuing network) và mạng Petri (Petri net). Ngoài ra, luật
Amdalh cũng được phân tích và mở rộng trong trường hợp có tính
đến trễ truyền thông.
- Chương 3: Luận án đi vào phân tích ảnh hưởng của trễ
truyền thông đến hiệu năng của hệ thống tính toán song song có sử
dụng chip đa lõi. Luận án đề xuất công thức 4.5 để xác định trễ
truyền thông.
- Chương 4: Mở rộng đánh giá ảnh hưởng của trễ truyền
thông đến hiệu năng đối với hệ thống tính toán song song trong
môi trường cụm máy tính. Ngoài ra, chương này cũng thiết kế
thuật toán trình bày kết quả đánh giá hiệu năng và ảnh hưởng của
trễ truyền thông trên ứng dụng thực với bài toán thám mã mật
khẩu MS Office Word.

CHƯƠNG 1. TỔNG QUAN
1.1 Kiến trúc tính toán song song
1.1.1 Khái niệm
Tính toán song song là một dạng tính toán trong đó nhiều lệnh
được thực hiện đồng thời trên các đơn vị xử lý.
1.1.2 Các loại xử lý song song
Theo phân loại của Michael J. Flynn thì có hình thức song
song là: SISD, SIMD, MISD và MIMD.
1.1.3 Mô hình tính toán song song
a) Song song sử dụng CPU nhiều lõi (MultiCore chip).
b) Song song sử dụng các bộ tăng tốc (bộ xử lý đồ họa GPU).

một đơn vị xử lý (tuần tự) và thời gian chạy trên hệ thống tính
toán song song.
1.2.4 Tính hiệu quả
Gọi p là số phần tử tham gia tính toán song song và E
p
là mức
độ hiệu quả thì:









 


1.2.5 Tính mở rộng
Tính mở rộng đo khả năng tận dụng hiệu quả khi tăng số phần
tử xử lý. Các hệ thống mô phỏng có thể được dùng để tiên đoán
tính mở rộng của hệ thống.
1.3 Các kỹ thuật phân tích đánh giá hiệu năng
Để phân tích hiệu năng, có thể tiến hành theo một trong 3
phương pháp: Mô hình hóa, mô phỏng và đo lường.
1.3.1 Mô hình hóa
Sử dụng các mô hình toán học để phân tích như: Mạng hàng
đợi, mạng Petri.
6

hàng đợi đóng có nghiệm dạng tích và mạng Petri.
- Phân tích ảnh hưởng của trễ truyền thông đến hiệu năng của hệ
thống tính toán song song có sử dụng vi xử lý đa lõi cũng như
hệ thống máy tính ghép cụm.
7

- Triển khai thử nghiệm đánh giá ảnh hưởng của trễ truyền
thông đối với bài toán thám mã mật khẩu trong môi trường
tính toán song song.

CHƯƠNG 2. CƠ SỞ LÝ THUYẾT CHO PHÂN TÍCH
HIỆU NĂNG
2.1 Hàng đợi và mạng hàng đợi
2.1.1 Hàng đợi
Mô hình hàng đợi cơ bản của một Trung tâm phục vụ bao gồm
các khách hàng tới một cách tuỳ ý và độc lập với nhau. Hệ thống
phục vụ có n điểm phục vụ (server), mỗi điểm phục vụ có khả
năng phục vụ một khách hàng ở một thời gian. Các thời gian phục
vụ cần thiết cho các khách hàng cũng được mô hình hóa như
những biến tuỳ ý.
2.1.2 Mạng hàng đợi
Mạng hàng đợi là các hệ thống mà chúng gồm một số tùy ý,
nhưng hữu hạn các hàng đợi được nối với nhau.
2.1.3 Mạng hàng đợi một lớp và nhiều lớp công việc
Mạng hàng đợi một lớp công việc là các công việc có cùng
thời gian phục vụ và xác suất định tuyến.
2.1.4 Các số đo hiệu năng của mạng hàng đợi 1 lớp công việc
Các số đo hiệu năng bao gồm: Xác suất biên, mức độ sử dụng,
thông lượng, thông lượng tổng, số lượng trung bình của các công
việc, độ dài trung bình của hàng đợi, thời gian đáp ứng trung bình,

Các kỹ thuật phân tích cấu trúc gồm các phương pháp: ma trận
liên thuộc, các T-invariant và các S-invariant.

2.3 Luật Amdahl
2.3.1 Mức tăng tốc và hiệu năng
Biểu thức mức tăng tốc chung là:

 



),(
)(
)(
)()(
pn
p
n
n
nn






(2.56)
σ(n) - thời gian thực hiện phần tuần tự.
φ(n) - thời gian thực hiện phần có thể song song.
κ(n,p) - thời gian liên quan cho thực hiện song song.

TRUYỀN THÔNG ĐẾN HIỆU NĂNG
CỦA HỆ THỐNG TÍNH TOÁN SONG SONG SỬ DỤNG
CHIP ĐA LÕI

3.1 Hiệu năng của kiến trúc chip đa lõi
3.1.1 Chip đa lõi SMC, AMC và DMC
Có 3 kiến trúc chip đa lõi phổ biến hiện nay là SMC (Symetric
Multicore Chip), AMC (Asymetric MC) và DMC (Dynamic MC).

3.1.2 Phân tích giá hiệu năng thông qua mức tăng tốc
Mức tăng tốc tương ứng với ba kiến trúc là:
frfn
rn
rn
rf
r
f
rnfSp
SMC





)1(
.1
1
),,(
(3.6)
 





)1(
)1(
1
),,(
(3.8)
10

3.2 Phân tích ảnh hưởng của mạng liên kết đến hiệu năng
của hệ thống tính toán song song có sử dụng chip đa lõi bằng
mạng hàng đợi đóng có nghiệm dạng tích các xác suất.

3.2.2 Phân tích ảnh hưởng của trễ truyền thông đến hiệu năng
Các kết quả mô phỏng cho thấy: sự thay đổi thời gian phục vụ
trung bình của mạng liên kết tỷ lệ tuyến tính với các thông số hiệu
năng của các lõi CPU. Do giá trị ban đầu của số công việc lớn (≥
1000), nên mức độ sử dụng của các lõi CPU đạt đến mức độ gần
tối đa, 0.9 – 1.0, thời gian chờ đợi (Queue time) tăng lên nhanh,
dẫn đến thông lượng của thông số hiệu năng của lõi CPU và của
toàn bộ chip (System_Througput) không có sự thay đổi đáng kể
(có phần giảm). Điều này cho thấy trễ của mạng liên kết (thời gian
phục vụ) khi số lượng công việc (lệnh, luồng) lớn sẽ gây ra giảm
thông lượng của các lõi CPU một cách tuyến tính.

3.3 Phân tích ảnh hưởng của mạng liên kết đến hiệu năng
của hệ thống tính toán song song có sử dụng chip đa lõi bằng
mạng Petri thời gian tổng quát - GSPN

Bảng 3.3 Mật độ xác suất thẻ

μ=0
μ =1
μ =2
Core 2
0.14286
0.28571
.57143
L12Ch
1
0
0
L12Q
0.85714
0.14286
0
L12ready
0.42857
0.57143
0
L12Sers
0.57143
0.42857
0
L22Ch
1
0
0
L22Q

L3Q
0
L3Sers
0
L11Sers
0.42857
L3ready
1
L3Ch
0
MemQ
0
Hình 3.13 Mô hình GSPN của vi xử lý đa lõi
12

L22ready
0
1
0
L22Sers
1
0
0
Core 1
0.14286
0.28571
0.57143
L11Q
0.85714
0.14286

0
1
0
L11Ch
1
0
0
L11ready
0.42857
0.57143
0
L21Q
1
0
0
L21Sers
1
0
0
L21ready
0
1
0
L21Ch
1
0
0

MemSers
0

0.33333
M6
0.2
M7
0.2
M8
0.25

Bảng 3.5 Thông lượng của các
chuyển tiếp có trễ thời gian
Transition
Throuh
put
L12out
0.85714
L22Out
0
ReqL12
0.85714
ReqL22
0
ReqL11
0.85714
ReqL31
0
L3Out
0
L11Out
0.85714
ReqM

(4.3)
- Luật Amdahl mở rộng cho mức tăng tốc có tính overhead
song song:
(4.4)
4.1.2 Ảnh hưởng của trễ truyền thông đến hiệu năng
Để phân tích ảnh hưởng của cấu hình mạng liên kết các nút
đến overhead song song, ở đây mặc định rằng các nhiệm vụ có
được sự cân bằng tải chạy trên các nút server xử lý tương đồng
nhau về tài nguyên và thời gian xử lý, do đo có thể coi
, công thức tính trễ truyền thông như sau:

(4.5)
Trong đó, khoảng cách trung bình của định tuyến từ
switch/router (hop) của nút server xử lý nguồn đến nút đích.
),( npT
O
),(
)(
)(),(),(),( npT
n
pT
pTnpTnpTnpT
O
par
seqcommOcomp

),(
)(
)(
)()(


4.2 Sử dụng mạng hàng đợi đóng có nghiệm dạng tích các
xác suất để phân tích ảnh hưởng của trễ truyền thông đến hiệu
năng trong hệ thống tính toán song song ghép cụm
4.2.1 Đánh giá ảnh hưởng của trễ truyền thông bằng mô hình
mạng hàng đợi đóng có nghiệm dạng tích
Để đánh giá ảnh hưởng của trễ truyền thông, luận án sử dụng
mô hình mạng hàng đợi. Mạng hàng đợi cho hệ thống như sau:

4.1.4 Thực nghiệm mô phỏng trên công cụ JMT
Phần mềm sử dụng mô phỏng là JMT 0.8. Các tham số thiết lập
như sau:
2.0;8,0;8.0
;2.0;2.0;8.0
000


inetineti
netnet
ppp
ppp


startup
t
startup
t

data
t

17

Kịch bản 1: Đặt: CPU_service_time:=5, net_access_time:=10,
net_service_time:=100, với các trường hợp các proccessor có 8,
16, 32, 64 gói tin (số thẻ).
Kịch bản 2: Đặt: CPU_service_time:=5, net_access_time:=10,
net_service_time:=300, với các trường hợp các proccessor có 8,
16, 32, 64 gói tin (số thẻ).
Dưới đây là kết quả chạy mô phỏng trên phần mềm TimeNet cho
trường hợp kịch bản 1 và 2 với 8 gói tin, CPU_service_time=5,
net_access_time=10, net_service_time=100.

Hình 4.9 Kịch bản 1, 8 gói tin, CPU_service_time=5,
net_access_time=10, net_service_time=100.

Hình 4.10 Kịch bản 2, 8 gói tin, CPU_service_time=5,
net_access_time=10, net_service_time=300

Hình 4.11 Kịch bản 1, 16 gói tin, CPU_service_time=5,
net_access_time=10, net_service_time=100.

18

4.3.3 Đánh giá và nhận xét
Bằng phương pháp SCPN có thể xây dựng các mô hình SCPN
cho bất kỳ cấu trúc liên kết mạng nào và thực hiện đánh giá hiệu
năng qua các thông số yêu cầu. Ở đây, trong phạm vi của luận án
chỉ đưa ra mô hình SCPN cho cấu trúc phổ biến là 2Dtorus để
minh họa cho ứng dụng SCPN trong đánh giá hiệu năng của các
hệ thống tính toán song song đa xử lý, còn đối với các cấu trúc
khác có thể thực hiện theo cách tương tự.

4.4 Phân tích hiệu năng hệ thống tính toán song song ghép
cụm thực hiện thám mã mật khẩu MS Office
4.4.1 Bài toán thám mã mật khẩu
Bài toán khôi phục mật khẩu MS Office là một bài toán trong
thực tế có thể sử dụng cơ chế tính toán song song khá hiệu quả.
luận án sẽ đề xuất một cách tiếp cận vừa sử dụng các lõi trong một
bộ xử lý (nút) và vừa sử dụng nhiều nút tính toán trong mạng.
Hình 4.16 Kịch bản 2, 64 gói tin, CPU_service_time=5,
net_access_time=10, net_service_time=300.

20

4.4.2 Thám mã trong MS Office

21

4.4.3 Xây dựng thuật toán
 Lưu đồ thuật toán xử lý trong một tiến trình cho 1 lõi:

 Mã giả viết trên ngôn ngữ C#:

thống khác với độ dài mật khẩu không quá dài và phức tạp hoàn
toàn có thể thực hiện được bằng tấn công vét cạn sử dụng hệ thống
tính toán song song trên nhiều nút và nhiều lõi kết hợp.
Các thực nghiệm ở trên đã cho thấy hiệu năng của hệ thống
tính toán song song phụ thuộc rất nhiều vào các yếu tố, trong đó
phải kể đến là trễ truyền thông, đặc biệt khi lưu lượng truyền
thông tăng lên. Để tăng hiệu năng của hệ thống bằng cách giảm
thiểu trễ truyền thông thì có thể tiến hành giảm lưu lượng truyền
thông giữa các tiến trình và giữa các nút tính toán, như: Giảm tối
thiểu kích thước gói tin hoặc tần suất gửi các gói tin.
Khi lựa chọn số lõi của CPU tham gia vào quá trình tính toán
song song, cần chú ý nên chọn số lượng lõi phù hợp để có hiệu
23

năng đạt mức cao nhất. Không phải cứ chọn hết số lõi để tham gia
tính toán là sẽ có mức tăng tốc tốt nhất.

KẾT LUẬN VÀ KIẾN NGHỊ
1. Kết luận
Nghiên cứu về hệ thống tính toán song song và tính toán hiệu
năng cao đang là một trong những chủ đề nhận được rất nhiều sự
quan tâm. Đặc biệt, khi công nghệ và giá thành cho những hệ
thống ghép cụm có sử dụng những vi xử lý đa lõi và GPU ngày
càng giảm và cho phép người dùng có thể ghép nối gần như không
hạn chế số nút tham gia tính toán.
Đi cùng với khả năng mở rộng các nút tham gia tính toán để
nâng cao hiệu năng là bài toán khá nan giải cần phải được nghiên
cứu giải quyết đó là vấn đề giảm thiểu trễ truyền thông. Vấn đề
này cũng đã được nhiều nhóm nghiên cứu trong và ngoài nước
quan tâm và cũng đã có một số kết quả được công bố. Tuy nhiên,