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

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. 
 3 
 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. 
 4 
 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. 
 5 
 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. 
 6 
- 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ở). 
 7 
 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): N (P,T, I,O) (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à: 
  (n) (n)
 (2.56) 
 (n)
  (n) (n, p)
 p
 σ(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à: 
 8 
 1
  (n, p) (2.61) 
 f (1 f ) / p
 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à: 
 1 n r
Sp ( f ,n,r) (3.6) 
 SMC 1 f f .r n(1 f ) fr
 r n r
 1 r n r r
Sp ( f ,n,r) (3.7) 
 AMC 1 f f
 r n r (1 f ) f r
 r r n r
 1 n r
Sp ( f ,n,r) (3.8) 
 DMC (1 f ) f
 n(1 f ) f r
 r n
 9 
 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 
 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): 
 10 
 Hình 3.13 Mô hình GSPN của vi xử lý đa lõi 
 3.3.2 Mô phỏng hệ thống 
 Bảng 
.1 Các đánh dấu Bảng 3.2 Vị trí và số 
 Các đánh 
 Giá trị thẻ trung bình 
 dấu 
 Số thẻ 
 Vị trí 
 M0 0.32653 trung bình 
 M1 0.16327 
 Core 2 1.42857 
 M2 0.16327 
 L12Ch 0 
 M3 0.08163 
 L12Q 0.14286 
 M4 0.08163 
 L12ready 0.57143 
 M5 0.08163 
 L12Sers 0.42857 
 M6 0.04082 
 L22Ch 0 
 M7 0.04082 
 L22Q 0 
 M8 0.02041 
 L22ready 1 
Bảng 3.3 Mật độ xác suất thẻ L22Sers 0 
 μ=0 μ =1 μ =2 Core 1 1.42857 
Core 2 0.14286 0.28571 
.57143 L11Q 0.14286 
L12Ch 1 0 0 L3Q 0 
L12Q 0.85714 0.14286 0 L3Sers 0 
L12ready 0.42857 0.57143 0 L11Sers 0.42857 
L12Sers 0.57143 0.42857 0 L3ready 1 
L22Ch 1 0 0 L3Ch 0 
L22Q 1 0 0 MemQ 0 
 11 
L22ready 0 1 0 MemSers 0 
L22Sers 1 0 0 Memready 1 
Core 1 0.14286 0.28571 0.57143 L11Ch 0 
L11Q 0.85714 0.14286 0 L11ready 0.57143 
L3Q 1 0 0 L21Q 0 
L3Sers 1 0 0 L21Sers 0 
L11Sers 0.57143 0.42857 0 L21ready 1 
L3ready 0 1 0 L21Ch 0 
L3Ch 1 0 0 Bảng 3.4 Các thời 
MemQ 1 0 0 gian lưu lại của các 
MemSers 1 0 0 
Memready 0 1 0 đánh dấu 
L11Ch 1 0 0 Marking Value 
L11ready 0.42857 0.57143 0 M0 0.5 
L21Q 1 0 0 M1 0.25 
L21Sers 1 0 0 M2 0.25 
L21ready 0 1 0 M3 0.33333 
L21Ch 1 0 0 
 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 
 Throuh 
Transition 
 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 
 12 
 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 TO ( p, n) – 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: 
 T ( p)
T( p,n) T ( p,n) T ( p,n) T ( p) par T ( p,n) (4.3) 
 comp commO seq n O
 - Luật Amdahl mở rộng cho mức tăng tốc có tính overhead 
 song song: 
 T ( p) T ( p)
 S( p,n) seq par (4.4) 
 T ( p)
 T ( p) par T ( p,n)
 seq n O
 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 
TO ( p,n)  TcommO(p, n) , công thức tính trễ truyền thông như sau: 
T ( p,n) kHT kH(t t wt ) (4.5) 
 commO net sw startup data 
Trong đó, H 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. tsw 
 13 
trễ ở nút switch/router. tstartup thời gian khởi tạo truyền thông. 
tstartup được cho là không thay đổi (constant). tdata thời gian 
truyền một từ dữ liệu, w Kích thước của bản tin (số bytes) 
(khoản dữ liệu), k 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 
 p 0.8; p 0.2; p 0.2;
như sau: 0 0net net0 
 pneti 0.8; pi 0,8; pinet 0.2
 14 
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 
 15 
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: 
 16 
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. 
 17 
 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. 
 18 
 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. 
 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. 
 19 
4.4.2 Thám mã trong MS Office 
 20 
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 
 21 
 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 
 22 
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