Tiến Sĩ 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

iii

MỤC LỤC
Mở đầu 1
1. Lý do chọn đề tài 1
2. Mục tiêu nghiên cứu .2
3. Đối tượng và phạm vi nghiên cứu 2
3.1 Đối tượng nghiên cứu .2
3.2 Phạm vi nghiên cứu 2
4. Ý nghĩa khoa học và thực tiễn của đề tài .2
4.1 Ý nghĩa khoa học 2
4.2 Ý nghĩa thực tiễn 3
5. Kết quả đạt được 3
6. Bố cục của luận án 3
Chương 1. Tổng quan 5
1.1 Kiến trúc tính toán song song 5
1.1.1 Khái niệm 5
1.1.2 Các loại xử lý song song 5
1.1.3 Mô hình tính toán song song 9
1.2 Hiệu năng trong hệ thống tính toán song song 12
1.2.1 Khái niệm hiệu năng 12
1.2.2 Thời gian thực thi . 12
1.2.3 Tổng chi phí song song 13
1.2.4 Mức tăng tốc 13
1.2.5 Tính hiệu quả . 14
1.2.6 Tính mở rộng . 14
1.3 Các kỹ thuật phân tích, đánh giá hiệu năng 15
1.3.1 Mô hình phân tích 15
1.3.2 Mô hình mô phỏng . 16
1.3.3 Đo hiệu năng 17
1.4 Trễ truyền thông trong các hệ thống tính toán song song 18
1.4.1 Các nguồn gây trễ trong tính toán song song 18
1.4.2. Trễ truyền thông trong hệ thống tính toán song song . 19
1.4.3 Mạng liên kết trong các hệ thống tính toán song song 20
1.5 Tổng quan về các nghiên cứu liên quan 21
1.6 Các nhiệm vụ trong luận án . 24
1.7 Kết chương . 25
Chương 2. Cơ sở lý thuyết cho phân tích hiệu năng . 26
2.1 Hàng đợi và mạng hàng đợi . 26
2.1.1 Hàng đợi 26
2.1.2 Mạng hàng đợi . 28 iv

2.1.3 Mạng hàng đợi một lớp và nhiều lớp công việc 30
2.1.4 Các số đo hiệu năng của mạng hàng đợi một lớp công việc 32
2.1.5 Các số đo hiệu năng của mạng hàng đợi nhiều lớp công việc . 33
2.1.6 Các mạng hàng đợi có nghiệm dạng tích các xác suất (Closed Product
Form Queueing Network) . 34
2.2 Mạng Petri 38
2.2.1 Giới thiệu về mạng Petri 38
2.2.2 Các đặc tính cơ bản của mạng Petri 39
2.2.3 Một số mạng Petri phổ biến . 42
2.2.4 Phân tích mô hình mạng Petri 49
2.3 Luật Amdahl . 51
2.3.1 Mức tăng tốc và hiệu năng . 51
2.3.2 Mức tăng tốc theo luật Amdahl 52
2.3.3 Luật Amdahl mở rộng 56
2.4 Một số nhận xét về việc áp dụng mạng hàng đợi và mạng Petri trong
phân tích hiệu năng và sử dụng luật Amdahl . 56
2.5 Kết chương . 57
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 . 58
3.1 Hiệu năng kiến trúc chip đa lõi 58
3.1.1 Chip đa lõi SMC, AMC và DMC . 58
3.1.2 Phân tích, đánh giá hiệu năng thông qua mức tăng tốc . 59
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 . 66
3.2.1 Mô hình nghiên cứu . 66
3.2.2 Phân tích ảnh hưởng của trễ truyền thông đến hiệu năng 68
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 76
3.3.1 Mô hình hóa hệ thống bằng GSPN . 77
3.3.2 Mô phỏng hệ thống 79
3.3.3 Kết luận . 80
3.4 Kết chương . 80
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 81
4.1. Trễ truyền thông trong các hệ thống tính toán song song ghép cụm 81
4.1.1. Hiệu năng của hệ thống tính toán soang song ghép cụm 81
4.1.2 Ảnh hưởng của trễ truyền thông đến hiệu năng 84 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 87
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 . 87
4.2.2. Thực nghiệm mô phỏng trên công cụ JMT 89
4.2.3. Đánh giá và nhận xét . 91
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 . 92
4.3.1 Mô hình hệ thống . 92
4.3.2 Mô phỏng trên phần mềm 97
4.3.3 Đánh giá và nhận xét 99
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 . 100
4.4.1 Bài toán thám mã mật khẩu 101
4.4.2 Thám mã trong MS Office . 101
4.4.3 Xây dựng thuật toán . 104
4.4.4 Thử nghiệm . 106
4.4.5 Phân tích kết quả và bàn luận . 109
4.4.6 Kết luận . 110
4.5 Kết chương . 110
Kết luận và kiến nghị . 111
1. Kết luận . 111
2. Kiến nghị . 112
Tài liệu tham khảo . 113
Danh mục công trình đã công bố của luận án 120