Tóm tắt Luận án 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

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 
Hà Nội – 2015 
Công trình được hoàn thành tại: 
Trường Đại học Bách khoa Hà Nội 
 Người hướng dẫn khoa học: 
- PGS.TS Huỳnh Quyết Thắng 
- TS Hồ Khánh Lâm 
Phản biện 1: GS.TS Vũ Đức Thi 
Phản biện 2: PGS.TS Hà Hải Nam 
Phản biện 3: PGS.TS Ngô Quốc Tạo 
Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ 
cấp trường họp tại Trường Đại học Bách khoa Hà Nội 
 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 để 
có được hiệu năng tốt nhất cho hệ thống. 
Luận án này sẽ đi vào nghiên cứu phân tích hiệu năng của các 
hệ thống tính toán song song, trong đó tập trung nghiên cứu sâu 
ảnh hưởng của trễ truyền thông đến hiệu năng của hệ thống. 
2. Mục tiêu nghiên cứu 
Mục tiêu nghiên cứu của luận án là phân tích ảnh hưởng của 
trễ truyền thông (Communication Overhead) tới hiệu năng của hệ 
thống tính toán song song và đề xuất công thức tính toán trễ truyền 
thông ứng với một số cấu trúc mạng liên kết phổ biến. Ngoài ra, 
luận án tiến hành thiết kế và thử nghiệm phần mềm thám mã mật 
khẩu trong MS Office Word chạy trên nền hệ thống tính toán song 
song để cho thấy rõ sự ảnh hưởng của trễ truyền thông đến hiệu 
năng của hệ thống. Phương pháp lý thuyết được sử dụng để phân 
tích trễ truyền thông trong luận án là mạng hàng đợi và mạng 
Petri. 
2 
3. Đối tượng và phạm vi nghiên cứu 
3.1 Đối tượng nghiên cứu 
Đối tượng nghiên cứu của luận án là Trễ truyền thông trong 
các hệ thống tính toán song song. 
3.2 Phạm vi nghiên cứu 
Do việc phân tích hiệu năng trong các hệ thống tính toán song 
song có phạm vi rất rộng và phức tạp. Vì vậy, phạm vi nghiên cứu 
của luận án là phân tích ảnh hưởng của trễ truyền thông đến hiệu 
năng của các hệ thống tính toán song song. Các hệ thống tính toán 
song song này chỉ gồm kiến trúc chip đa lõi và kiến trúc nối cụm. 
Luận án cũng giả thiết các nút tham gia tính toán trong các hệ 
thống cụm cũng như các lõi trong cùng một vi xử lý có cấu hình và 
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 
phục mật khẩu MS Excel, tệp zip, mật khẩu windows, v.v... 
5. Đóng góp của luận án 
Các kết quả chính của luận án, gồm: 
Thứ nhất: Xây dựng được công thức tính trễ truyền thông 
(Công thức 4.5) cho một số mạng liên kết trong hệ thống tính toán 
song song ghép cụm. Công thức này có thể được sử dụng để tính 
trễ truyền thông cho hầu hết các cấu trúc mạng liên kết đa xử lý 
phổ biến như mạng liên kết lưới hai chiều (2Dmesh), lưới ba chiều 
(3Dmesh), lưới vòng hai chiều (2Dtorus),... 
Thứ hai: Tiến hành 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 
thông qua sử dụng mạng hàng đợi đóng có nghiệm dạng tích các 
xác suất và mạng Petri thời gian tổng quát. 
Thứ ba: Tiến hành 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 ghép cụm. Sử 
dụng mạng hàng đợi CPFQN và mạng Petri để tiến hành phân tích 
và đánh giá ảnh hưởng của mạng liên kết đến hiệu năng của hệ 
thống cho các kiến trúc điển hình (lưới hai chiều, lưới vòng hai 
chiều, lưới lưới ba chiều, lưới vòng ba chiều, siêu lập phương - 
Hypercube). 
Thứ tư: Thiết kế thuật toán và chương trình thám mã mật khẩu 
MS Word chạy trên hệ thống cụm máy tính sử dụng bộ vi xử lý đa 
lõi, có thể mở rộng chạy trên hệ thống nhiều nút tính toán. 
4 
6. Bố cục của luận án 
Nội dung của luận án gồm 4 chương, cụ thể như sau: 
- Chương 1: Trình bày tổng quan về các mô hình kiến trúc 
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). 
c) Song song sử dụng các máy tính nối cụm. 
5 
d) Song song sử dụng mô hình kết hợp: Cụm, GPU, 
MultiCore. 
1.2 Hiệu năng trong kiến trúc tính toán song song 
Có 3 tiêu chí quan trọng để đánh giá là: Thời gian thực thi, 
tổng chi phí song song, mức độ tăng tốc, tính hiệu quả và tính mở 
rộng. 
1.2.1 Thời gian thực thi 
Thời gian thực thi song song là khoảng thời gian bắt đầu quá 
trình tính toán song song cho đến khi phần tử tính toán cuối cùng 
kết thúc, ký hiệu là Tp 
1.2.2 Tổng chi phí song song 
Chi phí tiêu tốn bởi một chương trình song song được biểu 
diễn bởi một biểu thức và được gọi là hàm chi phí (Overhead 
function). Ký hiệu là To và To = pTp - Ts 
1.2.3 Mức tăng tốc 
Mức tăng tốc được định nghĩa là tỉ số giữa thời gian chạy trên 
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à Ep 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 
1.3.2 Mô phỏng 
Mô phỏng hệ thống bằng các công cụ phần mềm. 
1.3.3 Đo lường 
Thực hiện chạy hệ thống và dùng các phần cứng, phần mềm đo 
các thông số cần quan tâm. 
1.4 Trễ truyền thông trong các hệ thống tính toán song song 
1.4.1 Các nguồn gây trễ 
Bao gồm kiến trúc mạng liên kết, đồng bộ hóa, thời gian 
truyền thông, thời gian nghỉ/chờ... 
1.4.2 Mạng liên kết trong hệ thống tính toán song song 
Trong hệ thống tính toán song song, các phần tử xử lý liên kết 
với nhau qua một mạng liên kết, có thể là 2Dmesh, 2Dtorus, 
3Dmesh, 3Dtorus, Hypercube, v.v.... 
1.5 Tổng quan về các nghiên cứu liên quan 
a) Tình hình trong nước: Chưa có nhiều nghiên cứu và công 
trình liên quan đến hệ thống xử lý song song. Dù các cơ sở đào tạo 
và nghiên cứu về CNTT lớn như ĐHBKHN, ĐHQGHN, 
ĐHQGHCM, Viện hàn lâm khoa học và công nghệ VN đã trang bị 
hạ tầng tính toán... 
b) Tình hình ngoài nước: Đã có nhiều nghiên cứu, tuy nhiên về 
vấn đề trễ truyền thông vẫn còn nhiều việc tiếp tục cần phải 
nghiên cứu, phát triển. Trong đó việc tính toán trễ truyền thông 
trong công thức Amdahl mở rộng cho một số mạng liên kết cụ thể 
cần được tính toán đề xuất. 
1.6 Các nhiệm vụ trong luận án 
- Nghiên cứu hướng tiếp cận đánh giá hiệu năng sử dụng mạng 
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, 
thời gian chờ đợi trung bình. 
2.1.5 Số đo hiệu năng của mạng hàng đợi nhiều lớp công việc 
Các số đo này giống như các số đo của mạng hàng đợi một lớp 
công việc, tuy nhiên công thức tính là khác nhau. 
2.1.6 Các mạng hàng đợi có nghiệm dạng tích các xác suất 
Bao gồm các mạng hàng đợi: BCMP, BCMP phiên bản 1 (cho 
PFQN đóng) và BCMP phiên bản 2 (cho PFQN mở). 
8 
2.2 Mạng Petri 
2.2.1 Giới thiệu mạng Petri 
Petri Net (PN) là một đồ thị song hướng có trọng số gồm 4 
thành phần: tập hợp các vị trí P (place), tập hợp các chuyển tiếp T 
(transition), hàm vào I (input function) và hàm ra O (output 
function): ),,,( OITPN (2.42) 
2.2.2 Các đặc tính cơ bản của mạng Petri 
Các đặc tính cơ bản của mạng Petri gồm: Tuần tự, đồng bộ, kết 
hợp, song song hay tương tranh, đụng độ, hỗn độn, loại trừ lẫn 
nhau, các ưu tiên, các chuyển tiếp cuối cùng, khóa chết. 
2.2.3 Một số mạng Petri phổ biến 
Trong mạng Petri, có một số loại mạng hay được sử dụng là 
mạng Petri có màu, mạng Petri có đánh dấu, mạng Petri thời gian 
ngẫu nhiên, mạng Petri màu ngẫu nhiên. 
2.2.4 Phân tích mô hình mạng petri 
Việc phân tích mô hình PN cho ta biết hành vi của hệ thống. 
Có các kỹ thuật phân tích cấu trúc và các kỹ thuật phân tích không 
gian trạng thái. 
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. 
2.3.2 Mức tăng tốc theo Luật Amdahl 
Theo luật Amdahl, mức tăng tốc là: 
9 
 pff
pn
/)1(
1
),(
  (2.61) 
2.3.3 Luật Amdahl mở rộng 
Mức tăng tốc tính theo Luật Amdahl mở rộng bao gồm cả trễ 
truyền thông, được tính bởi công thức: 
Sp = 1/(f + tc/ts). Trong đó tc là trễ truyền thông. 
CHƯƠNG 3. 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 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
rnfSpSMC
)1(.1
1
),,( (3.6) 
 rffrnr
rrnr
rnr
f
r
f
rnfSpAMC
)1(1
1
),,( (3.7) 
rffn
rn
n
f
r
f
rnfSpDMC
)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  ...  ả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 
3.3.1 Mô hình hóa hệ thống bằng GSPN 
Với định nghĩa của GSPN và cơ chế thực thi trong kiến trúc 
chip đa lõi, việc biểu diễn mô hình hệ thống cho ở Hình 3.5 hoàn 
toán có thể biểu diễn bằng GSPN, như sau (Hình 3.13): 
11 
3.3.2 Mô phỏng hệ thống 
Bảng 
.1 Các đánh dấu 
Các đánh 
dấu 
Giá trị 
M0 0.32653 
M1 0.16327 
M2 0.16327 
M3 0.08163 
M4 0.08163 
M5 0.08163 
M6 0.04082 
M7 0.04082 
M8 0.02041 
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 1 0 0 
Bảng 3.2 Vị trí và số 
thẻ trung bình 
Vị trí 
Số thẻ 
trung bình 
Core 2 1.42857 
L12Ch 0 
L12Q 0.14286 
L12ready 0.57143 
L12Sers 0.42857 
L22Ch 0 
L22Q 0 
L22ready 1 
L22Sers 0 
Core 1 1.42857 
L11Q 0.14286 
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 
L3Q 1 0 0 
L3Sers 1 0 0 
L11Sers 0.57143 0.42857 0 
L3ready 0 1 0 
L3Ch 1 0 0 
MemQ 1 0 0 
MemSers 1 0 0 
Memready 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 
Memready 1 
L11Ch 0 
L11ready 0.57143 
L21Q 0 
L21Sers 0 
L21ready 1 
L21Ch 0 
Bảng 3.4 Các thời 
gian lưu lại của các 
đánh dấu 
Marking Value 
M0 0.5 
M1 0.25 
M2 0.25 
M3 0.33333 
M4 0.16667 
M5 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 0 
MemOut 0 
ReqL32 0 
ReqL21 0 
L21Out 0 
13 
3.3.3 Kết luận 
Ngoài công cụ phân tích hiệu năng sử dụng CPFQN, công cụ 
GSPN cho phép dễ dàng mô hình các kiến trúc đa lõi trong đó có 
thể phân tích được các đặc tính hành vi của hệ thống mà CPGQN 
còn hạn chế. Việc kết hợp hai công cụ sẽ cho ta cách nhìn toàn 
diện hơn về hệ thống cần phân tích, đồng thời cũng là cách để ta 
kiểm chứng kết quả theo các cách tiếp cận khác nhau. 
CHƯƠNG 4. 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 GHÉP CỤM 
4.1 Trễ truyền thông trong các hệ thống tính toán song song 
ghép cụm 
4.1.1 Hiệu năng của hệ thống tính toán soang song ghép cụm 
- Gọi – overhead song song. Khi đó, tổng thời gian 
thực hiện chương trình kích thước p trên máy tính song song 
ghép cụm với n nút xử lý được xác định bằng: 
 (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. 
),( npTO
),(
)(
)(),(),(),( npT
n
pT
pTnpTnpTnpT
O
par
seqcommOcomp
),(
)(
)(
)()(
),(
npT
n
pT
pT
pTpT
npS
O
par
seq
parseq
),(),( npTnpT commOO 
)(),(
datastartupswnetcommO
wtttkHkHTnpT 
 H
 swt
14 
trễ ở nút switch/router. thời gian khởi tạo truyền thông. 
 được cho là không thay đổi (constant). thời gian 
truyền một từ dữ liệu, Kích thước của bản tin (số bytes) 
(khoản dữ liệu), số lượng các bản tin. 
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
 startupt
startup
t 
data
t
 w
 k
15 
Hình 4.5 b. Thông lượng của hệ thống tính toán song song với cấu hình 
2DTorus Infiniband interconnect DDR 12x, n=9 
Hình 4.5 c. Thông lượng của hệ thống tính toán song song với cấu hình 
3DTorus Infiniband interconnect DDR 12x, n=9 
16 
Hình 4.5 d. Thông lượng của hệ thống tính toán song song với cấu hình 
Hypercube Infiniband interconnect DDR 12x, n=9 
4.3 Sử dụng mạng Petri màu ngẫu nhiên để 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 ghép cụm 
4.3.1 Mô hình hệ thống 
Hệ thống song song kết nối cụm với các cấu hình liên kết phổ biến 
là 2Dtorus mà ở đó mỗi một nút xử lý kết nối với 4 nút kề cận (cấp 
độ của nút bằng 4). Mô hình gồm 5 nút xử lý: nút P0, nối với 4 nút 
kề cận P1, P2, P3, P4. Cấu trúc và công nghệ của mỗi nút Pi 
(i=0,1,2,3,4) đều giống nhau (Hình 4.6). 
Hình 4.6 SCPN của processor 
4.3.2 Mô phỏng trên phần mềm 
Xây dựng hai kịch bản thử nghiệm: 
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 
Hình 4.12 Kịch bản 2, 16 gói tin, CPU_service_time=5, 
net_access_time=10, net_service_time=300. 
Hình 4.13 Kịch bản 1, 32 gói tin, CPU_service_time=5, 
net_access_time=10, net_service_time=100. 
Hình 4.14 Kịch bản 2, 32 gói tin, CPU_service_time=5, 
net_access_time=10, net_service_time=300. 
Hình 4.15 Kịch bản 1, 64 gói tin, CPU_service_time=5, 
net_access_time=10, net_service_time=100. 
19 
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#: 
void Try(int idxCurrentChar) 
{ 
 if (Found) return; 
 for (j = 0; j < CharSet.Length; j++) { 
 strBuffer[idxCurrentChar] = CharSet[j]; 
 if (i == PasswordLength){ 
 for (k = 1; k <= PasswordLength; k++) { 
 Key = Key + strBuffer [k]; 
 } 
 //So sánh password với khóa ứng cử: K=K’? 
 if (RC4.Verify(Key)) { 
 Found = true; 
 PWFound = Key; //Đã tìm thấy pass 
 } 
 } 
 else Try(idxCurrentChar+1);}}//Đệ quy quay lui 
22 
4.4.4 Thử nghiệm 
Trong các thử nghiệm dưới đây, sẽ thực hiện quét mật khẩu 
có độ dài 4 ký tự. Kết quả được thể hiện như Hình 4.25. 
Hình 4.25 Kết quả thử nghiệm 
4.4.5 Phân tích kết quả 
Các thử nghiệm cho thấy, khi tăng số lõi xử lý thì tốc độ sẽ 
tăng lên nhưng sẽ có xu hướng giảm khi đạt đến số lượng lõi tối 
đa của chip. Khi tăng tần suất và kích thước gói tin thì hiệu năng 
giảm. 
4.4.6 Kết luận 
Việc tìm lại mật khẩu trong MS Word cũng như một số hệ 
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, 
do có nhiều yếu tố ảnh hưởng đến hiệu năng nên chưa thể có một 
nghiên cứu nào bao quát và đưa ra giải pháp trọn vẹn. Ngoài ra, 
việc sử dụng các phương pháp và công cụ phân tích khác nhau 
cũng là một trong những cách tiếp cận cần được khuyến khích. 
Luận án đã tiến hành phân tích hiệu năng của một số kiến trúc 
và hệ thống tính toán song song, trong đó sử dụng hai công cụ 
phân tích chính là mạng hàng đợi và mạng Petri. Các kết quả 
nghiên cứu của luận án có thể ứng dụng trong việc phân tích các 
hệ thống tính toán song song trong các hệ thống thực tế mà không 
nhất thiết phải là vi xử lý cho máy tính, cụm máy tính. Ví dụ, có 
thể áp dụng để phân tích các hệ thống điều khiển song song, hệ 
thống cảm biến, hệ thống chip giám sát, hệ thống thu thập thông 
tin, v.v... 
Luận án đã nghiên cứu ả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 đối với cả các vi xử lý đa 
lõi và cả hệ thống có sử dụng nhiều máy tính theo mô hình nối 
cụm và đã đề xuất công thức tính trễ ứng với một số cấu trúc mạng 
liên kết cụ thể. Từ kết quả này, có thể áp dụng để phân tích các 
cấu trúc mạng liên kết tương tự khác. 
24 
Phần phân tích sự ảnh hưởng của trễ truyền thông đối với bài 
toán thám mã mật khẩu MS Office Word giúp khẳng định và làm 
sáng tỏ thêm các kết quả nghiên cứu được đề cập trước đó. Các 
kết quả thực nghiệm và thuật toán đề xuất trong luận án có thể làm 
cơ sở để xây dựng và phát triển các hệ thống tính toán song song 
hiệu năng cao sử dụng vi xử lý đa lõi, bộ GPU và cụm máy tính để 
thám mã các hệ thống khác bằng phương pháp vét cạn. 
Kết quả thực nghiệm và thuật toán đề xuất đối với bài toán 
thám mã mật khẩu MS Office Word có thể được sử dụng và áp 
dụng đối với các bài toán vét cạn một cách tương tự và chạy trên 
hệ thống tính toán song song ghép cụm sử dụng vi xử lý đa lõi, kết 
hợp với bộ xử lý đồ họa đa năng GPU. Kết quả nghiên cứu có thể 
phát triển thành sản phẩm có tính thương mại cao, tương tự như 
các phần mềm thám mã hiện có trên thị trường như: LM Software. 
Như vậy, về cơ bản, kết quả của luận án đã đáp ứng được yêu 
cầu đặt ra ban đầu và các công trình thể hiện các kết quả trong 
đócũng đã được công bố trên các tạp chí và hội thảo chuyên ngành 
trong và ngoài nước, đảm bảo độ tin cậy và có ý nghĩa đối với nội 
dung nghiên cứu. 
2. Kiến nghị và hướng phát triển tiếp theo 
Trong khuôn khổ của luận án mới chỉ nghiên cứu một trong 
số những yếu tố ảnh hưởng đến hiệu năng trong hệ thống tính toán 
song song đó là trễ truyền thông, mà chủ yếu tập trung vào mạng 
kết nối hay nói cách khác là cấu trúc topo của mạng kết nối. Các 
topo và các mô hình xử lý được lựa chọn để phân tích trong luận 
án nhìn chung còn hạn chế cả về số lượng và độ phức tạp. 
Vì vậy, cần tiếp tục nghiên cứu về các cấu trúc mạng kết nối 
khác nhau cũng như cần đưa vào nghiên cứu những mô hình phức 
tạp hơn và sát với thực tế hơn. 
Các công cụ phần mềm khác nhau có thể được sử dụng để 
kiểm chứng lại các kết quả từ mô hình được xây dựng nhằm đảm 
bảo tính đúng đắn của phương pháp được đề xuất. 
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 
1. Hồ Khánh Lâm, Huỳnh Quyết Thắng, Nguyễn Minh Quý, "Phân 
tích hiệu năng của vi xử lý đa lõi bằng CPFQN và GSPN", Tạp 
chí Nghiên cứu khoa học và công nghệ quân sự, Số 16 năm 2011 
(tháng 12), ISSN 1859-1043, trang 179-186. 
2. Nguyễn Minh Quý, Hồ Khánh Lâm, Huỳnh Quyết Thắng. “Phân 
tích ảnh hưởng của mạng liên kết đến hiệu năng của vi xử lý đa 
lõi”. Tạp chí Nghiên cứu khoa học và công nghệ quân sự, số 16 
năm 2011 (tháng 12), ISSN 1859-1043, trang 187-198. 
3. Nguyễn Minh Quý, Hồ Khánh Lâm “Phân tích hiệu năng của 
các kiến trúc chip đa lõi”, Kỷ yếu Hội nghị Quốc gia lần thứ VI 
về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR) 
- Huế, ngày 20 – 21/6/2013, ISBN: 978-604-913-165-3, trang 
230-236. 
4. Nguyen Minh Quy, Ho Khanh Lam, Huynh Quyet Thang. 
“Analysis of Effectiveness of Communication Overheads in the 
Parallel Computing System Using the Closed Product Form 
Queuing Network”. RIVF-2013: The 10th IEEE RIVF 
International Conference on Computing and Communication 
Technologies, Hanoi, Vietnam, 10-13 November 2013, pp. 131-
134, ISBN 978-1-4799-1350-3. 
5. Nguyen Minh Quy, Huynh Quyet Thang, Ho Khanh Lam, 
“Analysis of Effectiveness of Communication Overhead in the 
Parallel Computing System Using Stochastic Colored Petri 
Nets”, American Journal of Networks and Communications, 
ISSN 2326-8964, Vol 2, pp. 29-38, 2014. 
6. Nguyễn Minh Quý, Huỳnh Quyết Thắng, Hồ Khánh Lâm. “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 trong bài toán khôi phục mật khẩu Microsoft 
Word”. Tạp chí Khoa học và Công nghệ các Trường đại học kỹ 
thuật số 104, ISSN 0868-3980, trang 41-45, 2015.