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

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 .... Hình 1.9 Mô hì

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

LUẬN ÁN TIẾN SĨ KỸ THUẬT PHẦN MỀM

Hà Nội -2015

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

LUẬN ÁN TIẾN SĨ KỸ THUẬT PHẦN MỀM

NGƯỜI HƯỚNG DẪN KHOA HỌC

1 PGS.TS HUỲNH QUYẾT THẮNG

2 TS HỒ KHÁNH LÂM

Hà Nội -2015

LỜI CAM ĐOAN

Tôi xin cam đoan luận án này là công trình nghiên cứu khoa học của tôi dưới sự hướng dẫn của PGS.TS Huỳnh Quyết Thắng và TS Hồ Khánh Lâm

và không trùng lặp với bất kỳ công trình khoa học nào khác Các số liệu trình bày trong luận án đã được kiểm tra kỹ và phản ánh hoàn toàn trung thực Các kết quả nghiên cứu do tác giả đề xuất chưa từng được công bố trên bất kỳ tạp chí nào đến thời điểm này ngoài những công trình của tác giả

Hà Nội, ngày 2 tháng 6 năm 2015

XÁC NHẬN CỦA TẬP THỂ HƯỚNG DẪN

PGS.TS Huỳnh Quyết Thắng TS Hồ Khánh Lâm Nguyễn Minh Quý

LỜI CẢM ƠN

Với tất cả sự kính trọng và biết ơn sâu sắc nhất, tác giả xin chân thành cảm ơn PGS.TS Huỳnh Quyết Thắng và TS Hồ Khánh Lâm đã tận tình hướng dẫn, chỉ bảo và động viên trong suốt quá trình nghiên cứu và viết luận

án Những góp ý, quan tâm và sự chỉ bảo vô cùng quý báu ấy của hai thầy đã giúp tôi rất nhiều trong việc hình thành phương pháp và tư duy nghiên cứu khoa học, giúp tôi trưởng thành hơn về mọi mặt

Xin chân thành cảm ơn tập thể các thầy cô giáo Bộ môn Công nghệ phần mềm và các thầy cô của Viện Công nghệ thông tin và Truyền thông, Trường ĐHBKHN đã tạo điều kiện và đóng góp nhiều ý kiến quý báu cho nội dung của luận án

Xin được bày tỏ lòng biết ơn chân thành sự giúp đỡ quý báu của Ban giám hiệu Trường ĐHSPKT Hưng Yên đã tạo mọi điều kiện cho các nghiên cứu sinh nói chung và cho cá nhân tôi nói riêng có điều kiện vừa học tập vừa công tác Cảm ơn các đồng nghiệp trong Khoa Công nghệ thông tin - Trường Đại học Sư phạm Kỹ thuật Hưng Yên đã gánh vác một phần công việc giảng dạy

và công việc quản lý Khoa trong suốt thời gian tôi làm luận án

Cuối cùng xin bày tỏ lòng biết ơn sâu sắc tới gia đình đã luôn chăm lo, động viên và giúp đỡ tôi vượt qua mọi khó khăn trong suốt thời gian qua

Tác giả: Nguyễn Minh Quý

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 25

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

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 77

3.3.1 Mô hình hóa hệ thống bằng GSPN 78

3.3.2 Mô phỏng hệ thống 80

3.3.3 Kết luận 81

3.4 Kết chương 81

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 82

4.1 Trễ truyền thông trong các hệ thống tính toán song song ghép cụm 82

4.1.1 Hiệu năng của hệ thống tính toán soang song ghép cụm 82

4.1.2 Ảnh hưởng của trễ truyền thông đến hiệu năng 85

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 88

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 88

4.2.2 Thực nghiệm mô phỏng trên công cụ JMT 90

4.2.3 Đánh giá và nhận xét 92

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 93

4.3.1 Mô hình hệ thống 93

4.3.2 Mô phỏng trên phần mềm 98

4.3.3 Đánh giá và nhận xét 100

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 101

4.4.1 Bài toán thám mã mật khẩu 102

4.4.2 Thám mã trong MS Office 103

4.4.3 Xây dựng thuật toán 105

4.4.4 Thử nghiệm 108

4.4.5 Phân tích kết quả và bàn luận 111

4.4.6 Kết luận 112

4.5 Kết chương 112

Kết luận và kiến nghị 113

1 Kết luận 113

2 Kiến nghị 114

Tài liệu tham khảo 115

Danh mục công trình đã công bố của luận án 122

Danh mục các ký hiệu và chữ viết tắt

STT

Ký hiệu,

chữ viết

tắt

Ý nghĩa đầy đủ bằng tiếng Anh Ý nghĩa bằng tiếng Việt

2 2DTorus 2 Dimension Torus Lưới vòng hai chiều

3 3DTorus 3 Dimension Toros Lưới vòng ba chiều

4 AMC Asymmetric Multicore Chip Chip đa lõi bất đối xứng

6 CDF Cumulative Density Functions Hàm mật độ tích lũy

7 CPFQN Closed Product Form Queuing

Network

Mạng hàng đợi đóng dạng tích

9 CPU Central Processing Unit Bộ xử lý trung tâm

11 CUDA Compute Unified Device

Architecture

Kiến trúc thiết bị tính toán hợp nhất

12 DMC Dynamic Multicore Chip Chip đa lõi linh hoạt

15 GPU Graphic Processing Unit Bộ xử lý đồ họa

16 GSPN Generalized Stochastic Petri Net Mạng Petri ngẫu nhiên

tổng quát

17 HPC High Performance Computing Tính toán hiệu năng cao

18 MIMD Multiple Instruction stream

Multiple Data stream

Đa dòng lệnh đa dòng dữ liệu

19 MISD Multiple Instruction stream

Single Data stream

Đa dòng lệnh đơn dòng dữ liệu

20 MPI Message Passing Interface Giao diện truyền thông

điệp

21 MVA Mean Value Algorithm Giải thuật giá trị trung bình

STT

Ký hiệu,

chữ viết

tắt

Ý nghĩa đầy đủ bằng tiếng Anh Ý nghĩa bằng tiếng Việt

22 OCIN OnChip INterconnect Mạng liên kết trên chip

23 PDF Probability Distribution Function Hàm phân bố xác suất

26 SCPN Stochastic Color Petri Net Mạng Petri màu ngẫu nhiên

27 SIMD Single Instruction Multiple Data Đơn lệnh đa dữ liệu

28 SISD Single Instruction Single Data Đơn lệnh đơn dữ liệu

29 SMC Symmetric Multicore Chip Chip đa lõi đối xứng

30 SPN Stochastic Petri Net Mạng Petri ngẫu nhiên

Danh mục các bảng

Bảng 3.1 Các đánh dấu 80

Bảng 3.2 Vị trí và số thẻ trung bình 80

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

Bảng 3.4 Các thời gian lưu lại của các đánh dấu 80

Bảng 3.5 Thông lượng của các chuyển tiếp có trễ thời gian 81

Bảng 4.1 Tlink = tsw + tstartup + wtdata với Infiniband DDR 12x 86

Bảng 4.2 Một số cấu hình mạng kết nối trong các máy tính song song 86

Bảng 4.3 Tnet= H(tsw + tstartup + wtdata) với Infiniband DDR 12x, n=64 nút 86

Bảng 4.4 Tnet= H(tsw + tstartup + wtdata) với Infiniband DDR 12x, n=9 nút 86

Bảng 4.5 Danh sách các vị trí trong processor 94

Bảng 4.6 Các chuyển tiếp có trễ kích hoạt của processor 94

Bảng 4.7 Các chuyển tức thời (trễ thời gian = 0) của processor 94

Bảng 4.8 Danh sách các vị trí trong processor 95

Bảng 4.9 Các chuyển tiếp có trễ kích hoạt 95

Bảng 4.10 Các chuyển tức thời (trễ thời gian = 0) của Interconnect 95

Bảng 4.11 Các thông số hiệu năng 97

Bảng 4.12 Số lượng khóa theo độ dài xâu 105

Danh mục các hình vẽ, đồ thị

Hình 1.1 Trao đổi dòng lệnh, dòng dữ liệu trong một máy tính đơn giản 6

Hình 1.2 SISD-Đơn dòng lệnh, đơn dòng dữ liệu 6

Hình 1.3 SIMD- Đơn dòng lệnh, đa dòng dữ liệu 7

Hình 1.4 MISD- Đa dòng lệnh, đơn dòng dữ liệu 7

Hình 1.5 MIMD- Đa dòng lệnh, đa dòng dữ liệu 8

Hình 1.6 Kiến trúc của CPU đa lõi 9

Hình 1.7 Mô hình tính toán song song sử dụng thêm GPU 10

Hình 1.8 Mô hình xử lý song song sử dụng cụm máy tính 11

Hình 1.9 Mô hình hệ thống tính toán song song sử dụng cụm máy tính 12

Hình 1.10 Mức tăng tốc và số phần tử tham gia xử lý 14

Hình 1.11 Minh họa chi phí về thời gian trong xử lý song song 19

Hình 1.12 Mô hình bộ nhớ chia sẻ và bộ nhớ phân tán 20

Hình 1.13 Một số mạng liên kết phổ biến 21

Hình 2.1 Mô hình của trung tâm phục vụ 26

Hình 2.2 Mạng mở các hàng đợi 29

Hình 2.3 Mạng đóng các hàng đợi 29

Hình 2.4 Mạng kết hợp 30

Hình 2.5 Tính tuần tự 39

Hình 2.6 Tính đồng bộ 39

Hình 2.7 Tính hợp nhất 40

Hình 2.8 PN thể hiện các hoạt động song song 40

Hình 2.9 Tính đụng độ 40

Hình 2.10 Tính hỗn độn 41

Hình 2.11 Tính loại trừ 41

Hình 2.12 PN có đánh dấu 45

Hình 2.13 Biểu diễn một vị trí có thời gian bằng GSPN 48

Hình 2.14 Diễn giải thời gian thực hiện chương trình song song 52

Hình 2.15 Minh họa mức tăng tốc theo luật Amdahl 53

Hình 2.16 Sự tăng tốc thực hiện của một task gồm 2 phần 55

Hình 3.1 Các loại kiến trúc chip đa lõi: SMC, AMC và DMC 58

Hình 3.2 Mức tăng tốc tính trên chip SMC 64

Hình 3.3 Mức tăng tốc trên chip AMC 65

Hình 3.4 Mức tăng tốc trên chip DMC 65

Hình 3.5 Mô hình tổ chức cache 3 tầng 67

Hình 3.6 Một số topo liên kết phổ biến 68

Hình 3.7 Mô hình mạng hàng đợi đóng của hệ thống VXL đa lõi 71

Hình 3.8 Mạng hàng đợi cho mô hình kiến trúc chip đa lõi với 3 cấp cache 75 Hình 3.9 Tỉ lệ giữa thời gian phục vụ và số khách hàng trong CPU1 75

Hình 3.10 Tỉ lệ giữa thời gian phục vụ và số khách hàng trong mạng 76

Hình 3.11 Tỉ lệ giữa thời gian phục vụ và thời gian chờ đợi trong mạng 76

Hình 3.12 Tỉ lệ giữa thời gian phục vụ và thông lượng của CPU1 77

Hình 3.13 Mô hình GSPN của vi xử lý đa lõi cho ở Hình 3.5 79

Hình 4.1 Các nhiệm vụ song song đồng bộ và không đồng bộ 84

Hình 4.2 So sánh trễ truyền thông của một số cấu hình mạng liên kết 87

sử dụng Infiniband DDR 12X và n=64 processor nodes 87

Hình 4.3 So sánh trễ truyền thông của một số cấu hình mạng liên kết 87

sử dụng Infiniband DDR 12X và n=9 processor nodes 87

Hình 4.4 CPFQN của hệ thống tính toán song song cho các ứng dụng gồm các nhiệm vụ song song không đồng bộ 89

Hình 4.5 a Thông lượng của hệ thống với cấu hình 2DMesh 90

Hình 4.5 b Thông lượng của hệ thống với cấu hình 2DTorus 91

Hình 4.5 c Thông lượng của hệ thống với cấu hình 3DTorus 91

Hình 4.5 d Thông lượng của hệ thống với cấu hình Hypercube 92

Hình 4.6 Sơ đồ mô tả hệ thống 5 nút bằng SCPN 93

Hình 4.7 SCPN của Interconnect 95

Hình 4.8 SCPN của hệ thống xử lý tính toán song song ghép cụm 2DTorus 96 Hình 4.9 Kịch bản 1, 8 gói tin 98

Hình 4.10 Kịch bản 2, 8 gói tin 99

Hình 4.11 Kịch bản 1, 16 gói tin 99

Hình 4.12 Kịch bản 2, 16 gói tin 99

Hình 4.13 Kịch bản 1, 32 gói tin 99

Hình 4.14 Kịch bản 2, 32 gói tin 100

Hình 4.15 Kịch bản 1, 64 gói tin 100

Hình 4.16 Kịch bản 2, 64 gói tin 100

Hình 4.17 Mô hình thử nghiệm 102

Hình 4.18 Quy trình khôi phục mật khẩu MS Word 103

Hình 4.19 Mô hình xử lý song song sử dụng CPU đa lõi và cụm tính toán 104 Hình 4.20 Chia không gian khóa cho các lõi và nút xử lý 104

Hình 4.21 Thuật toán tìm khóa trên một lõi xử lý 107

Hình 4.22 Chạy trên một nút và sử dụng 1 lõi 108

Hình 4.23 Chạy trên một nút và sử dụng 4 lõi 109

Hình 4.24 Chạy trên 2 nút, mỗi nút sử dụng 2 lõi 109

Hình 4.25 Kết quả thử nghiệm 111

Mở đầu

1 Lý do chọn đề tài

Trong những năm trở lại đây, cùng với sự phát triển vượt bậc của khoa học công nghệ, xử lý song song và điện toán đám mây đã và đang là một trong những hướng nghiên cứu được rất nhiều người quan tâm Các tính toán ở quy mô lớn trên những

bộ dữ liệu khổng lồ (hàng trăm, hàng nghìn thậm chí hàng triệu Gigabyte) chắc chắn không thể thực hiện trên những máy tính đơn lẻ mà phải được xử lý trên hệ thống cụm tính toán song song Hệ thống tính toán song song thông thường sẽ gồm các máy tính nối mạng đường truyền tốc độ cao Do sự phát triển mạnh mẽ của công nghệ chip đa xử lý hiện nay nên xử lý song song không chỉ trong các kiến trúc

đa máy tính mà trên cả nhiều bộ xử lý là các chip đa xử lý Các kiến trúc máy tính máy song song sử dụng các bộ xử lý dựa trên các chip đa xử lý kết hợp với các bộ đồng xử lý tăng tốc sử dụng bộ xử lý đồ họa (GPU-Graphic Processing Unit) của hãng Nvidia hiện nay là một xu hướng thiết kế và sử dụng khá phổ biến hiện nay bởi hiệu năng cao và chi phí khả thi [56]

Rất nhiều ứng dụng hiện nay, đặc biệt là trong xử lý dữ liệu lớn đã ứng dụng rất thành công hệ thống xử lý song song với hàng nghìn hay thậm chí hàng chục nghìn nút tính toán Có thể kể ra những hệ thống tiêu biểu như của Facebook, Yahoo, Google+… trong đó, dữ liệu về người dùng, dữ liệu về các giao dịch trên web có kích thước có thể lên đến hàng triệu Gigabyte [72] Có thể tìm hiểu cách thức triển khai của các hệ thống tính toán song song này thông qua một Framework nguồn mở hiện đang được áp dụng triển khai rất phổ biến là: Hadoop Framework [60] Với hệ thống xử lý song song trên nền Hadoop Framework, người ta đã sắp xếp 1TB dữ liệu chỉ trong khoảng thời gian là 60 giây [71] Các hệ thống này hoàn toàn có thể triển khai dễ dàng cho các nhu cầu tính toán cá nhân, ví dụ có thể dùng để tấn công vét cạn mật khẩu trong MS Word hay các tệp zip, pdf…

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 người ta thêm

các nút tính toán vào hệ thống thì đều mong muốn hiệu năng hay tốc độ của hệ thống 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 chậm lại 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 trúc 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 lập trình, công cụ phần mềm hỗ trợ lập trình song song v.v…[67]

Như vậy, việc xác định và phân tích rõ ảnh hưởng của các yếu tố đế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 vì khi đã xác định

rõ 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 phù hợp nhất cho hệ thống

Luận án này sẽ đi vào nghiên cứu 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

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

Các hệ thống tính toán song song đề cập trong luận án bao gồm tính toán song song trong phạm vi một bộ vi xử lý và trong một cụm tính toán Từ các kết quả này

sẽ trả lời được một số câu hỏi:

- Trễ truyền thông sẽ ảnh hưởng như thế nào đến hiệu năng của hệ thống Công thức để xác định trễ cụ thể tương ứng với mỗi kiến trúc mạng liên kết là gì!?

- Làm thế nào để lựa chọn được các kiến trúc mạng liên kết phù hợp trong hệ thống tính toán song song cho từng loại bài toán cụ thể để đạt hiệu năng tốt nhất

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ễ 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 Kết quả đạt được

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

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 và phương pháp phân tích 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) Mạng Petri và mạng hàng đợi là hai công cụ toán học rất mạnh để mô hình hóa

và phân tích nhiều bài toán trong khoa học kỹ thuật Luận án cũng sẽ làm rõ từng ưu điểm của hai công cụ phân tích này 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 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 Luận án sử dụng mạng hàng đợi đóng có nghiệm dạng tích các xác suất(Closed Product Form Queuing Network-CPFQN) và mạng Petri thời gian tổng quát (Generalized Stochastic Petri Net - GSPN), mạng Petri màu ngẫu nhiên (Stochastic Coloured Petri Net - SCPN) để 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

- Chương 4: Mở rộng phân tích ả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 Luận án cũng

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 để 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 Ngoài ra, chương này cũng thiết kế thuật toán trình bày kết quả phân tích 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

Nội dung của chương này trình bày tổng quan các vấn đề liên quan đến tính toán song song, bao gồm các kiến trúc tính toán song song, hiệu năng trong tính toán song song và tổng quan các kỹ thuật phân tích, đánh giá hiệu năng Các nghiên cứu liên quan trong và ngoài nước về phân tích hiệu năng cũng được đề cập

và phân tích Phần tiếp theo là đề xuất các nhiệm vụ được nghiên cứu, giải quyết trong luận án

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 [35] Tính toán song song vận hành trên nguyên tắc là các bài toán lớn được chia ra thành những phần nhỏ mà những phần nhỏ này có thể được thực hiện song song Tính toán song song đã được sử dụng từ nhiều năm nay, chủ yếu cho những tính toán hiệu năng cao và là một đặc điểm quan trọng trong kiến trúc máy tính hiện đại, nhất là trong các bộ xử lý nhiều lõi [22]

Tính toán song song có một số dạng khác nhau [10]:

- Song song mức bit

- Song song mức lệnh

- Song song dữ liệu

- Song song nhiệm vụ

Có 3 kiểu song song có thể có trong một chương trình thực hiện [49]:

- Song song dữ liệu: nhiều khoản dữ liệu có thể được xử lý trong cùng một cách và ở cùng một thời gian

- Song song chức năng: chương trình có các module khác nhau và độc lập với nhau có thể được thực hiện đồng thời

- Chồng lấn nhau (overlapped)/song song tạm thời (temporary parallelism): chương trình có một chuỗi các nhiệm vụ (task) có thể được thực hiện theo kiểu chồng lấn nhau Hình thức quan trọng nhất của chồng lấn nhau là kỹ thuật đường ống (pipelining)

1.1.2 Các loại xử lý song song

Có nhiều cách phân loại các bộ xử lý song song dựa trên cấu trúc hoặc hành vi của chúng Những phương pháp phân loại chính thường dựa trên số lượng các lệnh và/hoặc số lượng các toán hạng có thể được xử lý đồng thời, tổ chức bên trong của các bộ xử lý, cấu trúc kết nối các bộ xử lý hoặc các phương pháp điều khiển các dòng lệnh và dữ liệu bên trong hệ thống các bộ xử lý

Michael J Flynn đã đưa ra phân loại kiến trúc máy tính song song dựa theo các luồng dữ liệu và lệnh như sau [30]:

Đơn vị xử lý trung tâm đọc các lệnh và các toán hạng từ bộ nhớ, thực hiện các lệnh và chuyển kết quả trở lại bộ nhớ chính Các bước thực hiện lệnh này gộp lại

thành một chu kỳ lệnh (instruction cycle) Các lệnh có thể hình thành một dòng lệnh

MI (instruction stream) liên tiếp nhau đọc từ bộ nhớ vào bộ xử lý, trong khi các toán hạng cũng hợp thành dòng dữ liệu MD (data stream) theo sau đi tới và từ bộ xử lý

Sự trao đổi các dòng lệnh và các dòng dữ liệu giữa bộ xử lý và bộ nhớ được mô tả

đơn giản trong Hình 1.1

Nếu đặt MI và MD là số lượng các dòng lệnh và các dòng dữ liệu tương ứng, thì theo Michael J Flynn, các máy tính được phân loại thành 4 nhóm dựa trên số lượng

MI và MD được bộ xử lý thực hiện như sau [30]:

a) Đơn dòng lệnh đơn dòng dữ liệu - SISD

Đơn dòng lệnh đơn dòng dữ liệu có MI = 1, MD = 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ý (Hình 1.2) gồm

đơn vị điều khiển (Control Unit - CU), phần tử xử lý (Processing Element - PE) và

bộ nhớ M (Memory) 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 đơn dòng lệnh đơn dòng dữ liệu 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ổ sung, các đơn vị tính các vector, các bộ xử lý đồ họa và xử lý vào/ra

Hình 1.2 SISD-Đơn dòng lệnh, đơn dòng dữ liệu

Thông thường người ta phân chia các máy tính SISD ra thành hai nhóm [59]:

- Đơn dòng lệnh đơn dòng dữ liệu 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): IBM 701, IBM 1620, IBM

Tốc độ thực hiện của các máy tính đơn dòng lệnh đơn dòng dữ liệu được đo bằng đơn vị triệu lệnh trên giây – MIPS (Million of Instructions Per Second)

b) Đơn dòng lệnh đa dòng dữ liệu - SIMD

Đơn dòng lệnh đa dòng dữ liệu có MI = 1, MD > 1 Trong các hệ thống máy tính đơn dòng lệnh đa dòng dữ liệu có nhiều phần tử xử lý làm việc song song với nhau, thực hiện một lệnh giống nhau nhưng với những dữ liệu khác nhau Mỗi phần tử xử

Hình 1.1 Trao đổi dòng lệnh, dòng dữ liệu trong một máy tính đơn giản

lý (PEi, i = 1, 2,…, n) có bộ nhớ cục bộ riêng (Mi, i=1, 2, …n) Chương trình chứa trong bộ nhớ chung M và được chuyển đến đơn vị điều khiển để giải mã và điều

khiển thực hiện (Hình 1.3)

Các máy tính đơn dòng lệnh đa dòng dữ liệu cũng có kiến trúc Von Neumann nhưng với các lệnh lớn Phổ biến là các véc-tơ SIMD, mảng SIMD Các máy tính đơn dòng lệnh đa dòng dữ liệu như những bộ xử lý mảng (Array Processor) vì mảng

gồm n bộ xử lý Ví dụ những máy tính kiểu SIMD: ILLIAC-IV, BSP, MPP, PEPE,

STARAN, DAP và CM-1 (Connection Machine), MasPar MP-1&2, CM-200 Tốc

độ trong đơn vị đo là triệu phép tính dấu phảy động/giây (Mega FLoating-point Operations Per Second – MFLOPS)

Hình 1.3 SIMD- Đơn dòng lệnh, đa dòng dữ liệu

c) Đa dòng lệnh đơn dòng dữ liệu - MISD

Hình 1.4 MISD- Đa dòng lệnh, đơn dòng dữ liệu

MI > 1, MD = 1 Trong những hệ thống dạng này (Hình 1.4) một chuỗi dữ liệu từ

bộ nhớ chung M được chuyển đến dãy các bộ xử lý được điều khiển bởi các đơn vị điều khiển riêng và thực hiện các dòng lệnh khác nhau

Trên thực tế, không có nhiều bộ xử lý song song thuộc loại này Có thể các máy tính như Cray-1 và CYBER 205 của Control Data Corporation có tính năng xử lý đường ống (pipeline processing) được liệt vào nhóm đa dòng lệnh đơn dòng dữ liệu

d) Đa dòng lệnh đa dòng dữ liệu - MIMD

MI > 1, MD > 1 Trong hệ thống đa dòng lệnh đa dòng dữ liệu có tập hợp n phần

tử xử lý thực hiện đồng thời n dòng lệnh trên các dòng dữ liệu khác nhau (Hình

1.5) Hệ thống đa dòng lệnh đa dòng dữ liệu thường được gọi là hệ thống đa xử lý

với bộ nhớ chia sẻ

Hình 1.5 MIMD- Đa dòng lệnh, đa dòng dữ liệu

Ví dụ các hệ thống đa dòng lệnh đa dòng dữ liệu: Sequent, nCUBE, IBM RS6000 cluster, IBM SP1, IBM SP2, Intel iPSC/2, Intel Peragon, Cray C90, Cray-

2, Cray X-MP, Cray T3D/T3E, C.mmp, Burroughs, Pluribus, D825, HEP, Alliant FXC/8, nCUBE, Univac 1100/80, Tandem/16, C.m*, BBN Butterfly, Meiko Computing Surface (CS-1), FPS T/40000, Fujitsu VP 2000, KSR-1, Convex C-2, NEC SX-2

Các hệ thống có bộ nhớ chia sẻ (đơn dòng lệnh đa dòng dữ liệu và đa dòng lệnh

đa dòng dữ liệu) còn có thêm các phân chia nhỏ [6]:

- SM-R: bộ nhớ chia sẻ cho phép nhiều đọc đến cùng một địa chỉ

- SM-W: bộ nhớ chia sẻ cho phép ghi nhiều đến cùng một địa chỉ

- SM-RW: bộ nhớ chia sẻ cho phép cùng ghi và đọc đến cùng một địa chỉ

- SM: bộ nhớ chia sẻ không cho phép nhiều ghi và đọc

- TC: kết nối cặp chặt chẽ (phụ thuộc vào nhau), ví dụ như: C.mmp, Burroughs D825, Cray-2, S1, Cray X-MP, HEP, PluribusC

- LC: kết nối cặp lỏng lẻo, ví dụ như: IBM 370/168 MP, Univac 1100/80, Tandem/16, IBM 3081/3084, C.m*, BBN Butterfly

- UC: không kết nối, ví dụ như: Meiko Computing Surface, FPS T/40000, iPSC

Với hệ thống đa dòng lệnh đa dòng dữ liệu có thêm phân chia [50]:

- Bit-sliced MIMD: là các máy tính loại đa dòng lệnh đa dòng dữ liệu với các bộ xử lý chỉ thực hiện trên 1 bit trong một chu kỳ lệnh Một số máy Bit-sliced bao gồm: STARAN, MPP, DAP, CM-1

- Word-sliced MIMD: là các máy tính loại đa dòng lệnh đa dòng dữ liệu với các bộ xử lý thực hiện trên toàn bộ một từ trong một chu kỳ lệnh: ILLIAC-IV, PEPE, BSP

1.1.3 Mô hình tính toán song song

Có rất nhiều mô hình tính toán song song được đề xuất Tùy thuộc vào nhu cầu

cụ thể mà người ta có thể sử dụng một trong số các mô hình sau đây [91]:

a) Song song sử dụng bộ xử lý nhiều lõi (MultiCore chip)

Hình 1.6 Kiến trúc của bộ xử lý đa lõi

Hiện nay, với hầu hết các bộ xử lý thế hệ mới đều có chứa 2 hoặc nhiều lõi bên trong Các lõi có thể tiến hành xử lý song song các công việc do hệ điều hành chỉ định để làm tăng hiệu quả và tốc độ xử lý của toàn bộ hệ thống Với kiến trúc này, nhìn chung hệ thống sẽ không khai thác hết khả năng song song của các lõi cho một chương trình tính toán cụ thể Vì vậy, người lập trình sẽ phải tự thiết kế chương trình và lập trình để khai thác khả năng tính toán song song thông qua thuật toán và

cơ chế đa tuyến

Trong các ngôn ngữ lập trình hiện đại (Như Java, Visual C++ hay.NET framework nói chung) đều hỗ trợ cơ chế lập trình đa tuyến (Multi threading) Mỗi tuyến này khi được khởi động thì hệ điều hành sẽ đặt trong một lõi nhất định và như vậy có thể khai thác tối đa khả năng xử lý song song của bộ xử lý đa lõi

Hình 1.6 mô tả kiến trúc của bộ xử lý đa lõi, trong đó một bộ xử lý gồm 4 lõi (Lõi#1 đến Lõi#4), mỗi lõi có bộ nhớ cache L1 và L2 riêng, còn cache L3 được sử dụng chung (chia sẻ) Các lõi truy cập đến bộ nhớ cache L3 thông qua một mạng kết nối

b) Song song sử dụng các bộ tăng tốc đồ họa

Với các bộ xử lý đa lõi thì tốc độ xử lý được tăng lên đáng kể, tuy nhiên để tăng tốc độ xử lý mạnh hơn nữa người ta có thể lắp thêm các bộ tăng tốc đồ họa với số lõi tính toán lên tới hàng trăm thậm chí hàng nghìn lõi Điển hình như các bộ tăng tốc của hãng NVIDIA: Tesla M2070 (448 lõi), K29 (4096 lõi), …

Hình 1.7 Mô hình tính toán song song sử dụng thêm bộ tăng tốc đồ họa

Việc lập trình song song với các lõi trên bộ tăng tốc đồ họa nhìn chung là khó khăn và phức tạp hơn so với lập trình cho bộ xử lý đa lõi vì mỗi bộ tăng tốc đồ họa

có tổ chức bộ nhớ riêng Tuy nhiên, rất may là công việc phức tạp này đã được các nhà sản xuất đơn giản hóa đi nhiều bằng các bộ thư viện lập trình Ví dụ, với các bộ tăng tốc đồ họa của hãng NVIDIA có bộ công cụ phần mềm CUDA Toolkit CUDA Toolkit cung cấp rất nhiều thư viện cho phép lập trình viên có thể giao tiếp dễ dàng giữa thiết bị với bộ xử lý và truy cập vào bộ nhớ riêng của bộ tăng tốc đồ họa

Hình 1.7 là mô hình kiến trúc tính toán song song sử dụng bộ tăng tốc đồ họa

Trong mô hình này, bộ tăng tốc đồ họa có nhiều phần tử/ lõi xử lý và bộ nhớ dùng chung cho các lõi và trong mỗi lõi lại có bộ nhớ cục bộ riêng Phần tử xử lý chính cũng như các lõi có thể truy xuất đến bộ nhớ chung của bộ tăng tốc đồ họa

c) Song song sử dụng các máy tính nối cụm

Rõ ràng, vì kích thước của mỗi bộ tăng tốc đồ họa có giới hạn nên số lõi trên một bộ xử lý cũng bị giới hạn Do đó, một giải pháp rất phổ biến hiện nay nhằm tăng tốc độ tính toán là mô hình tính toán song song sử dụng các máy tính ghép cụm Với mô hình này, các máy tính sẽ nối với nhau thông qua hạ tầng mạng, ví dụ như các bộ chuyển mạch 100Mbps, 1000Mbps hay các đường truyền tốc độ cao hơn Khi đó, hiệu năng của toàn bộ hệ thống sẽ được tăng lên rất lớn tùy theo số lượng các máy tính tham gia trong cụm

Hình 1.8 Mô hình xử lý song song sử dụng cụm máy tính

Ưu điểm lớn nhất của mô hình này là khả năng mở rộng hầu như không bị hạn chế và các máy tính tham gia tính toán không nhất thiết phải cùng một cấu hình cũng như không nhất thiết phải chạy trên cùng một nền tảng hệ điều hành hay phần mềm

Tuy nhiên, có một vấn đề khi triển khai tính toán song song sử dụng mô hình này là tính ổn định của hệ thống bởi không thể đảm bảo được rằng tất cả các máy tính tham gia tính toán không gặp lỗi trong quá trình thực hiện Do vậy, khả năng kháng lỗi luôn là một nhiệm vụ cần phải được quan tâm Hadoop framework [74] là một hệ thống tiêu biểu thực hiện rất tốt yêu cầu này

Việc lập trình song song với mô hình này có thể thực hiện theo rất nhiều cách Thông thường sẽ có một chương trình điều khiển chạy trên máy “Master”, có nhiệm

vụ quản lý tác vụ, phân công công việc và tập hợp kết quả Các chương trình thực hiện tính toán sẽ chạy trên các máy “Slave” Các slave sẽ nhận chỉ thị công việc từ Master, sau đó thực hiện tính toán và gửi trả lại kết quả Giữa Master và Slave có thể giao tiếp với nhau theo kịch bản/giao thức mà người lập trình thiết kế và sử dụng giao thức mạng TCP hoặc UDP để truyền nhận các gói tin Tuy nhiên, một giải pháp được sử dụng rộng rãi và được xem như một chuẩn trong các hệ thống song song đó là dùng MPI (Message Passing Interface) [73]

Hình 1.8, thể hiện một hệ thống nối mạng gồm các nút tính toán (thường là các

máy tính cá nhân hoặc máy chủ cấu hình mạnh) cùng tham gia xử lý song song Các nút tính toán này có thể nối với nhau qua đường mạng tốc độ cao (Ví dụ các Switch Infiniband tốc độ khoảng 48 Gbps, 60 Gbps, ) Hoặc cũng có thể dùng các thiết bị kết nối mạng thông thường khác 100Mbps, 1Gbps , tùy thuộc vào từng yêu cầu

d) Song song sử dụng mô hình kết hợp

Trong thực tế, mô hình tính toán song song sử dụng chip đa lõi và cụm máy tính

ở trên khá phổ biến Tuy nhiên, cũng đã có nhiều nghiên cứu đề xuất và triển khai thành công mô hình tính toán kết hợp của cả hai mô hình này, hay còn được gọi là tính toán song song hai cấp Tiêu biểu như hệ thống tính toán song song của ElcomSoft [65] để phá mật khẩu, Hadoop framework trên môi trường cụm máy tính

có sử dụng chip đa lõi và bộ tăng tốc đồ họa [29]

Hình 1.9 Mô hình hệ thống tính toán song song sử dụng cụm máy tính

Đối với mô hình hỗn hợp này, việc thiết kế và lập trình sẽ khó khăn hơn vì vừa phải phân chia công việc trên các nút xử lý và trong mỗi nút lại tiếp tục phân chia cho các lõi trong bộ xử lý và thậm chí trên các lõi của bộ tăng tốc đồ họa đa năng GPGPU Một số kết quả cho mô hình này được đề cập trong [19,29,99]

Hình 1.9, thể hiện mô hình hệ thống tính toán song song, trong đó có nhiều nút

tính toán, mỗi nút này lại có nhiều lõi để có thể xử lý song song Các nút được kết nối thông qua mạng kết nối có thể là đường truyền mạng thông thường hoặc đường truyền tốc độ cao như Infiniband

1.2 Hiệu năng trong hệ thống tính toán song song

1.2.1 Khái niệm hiệu năng

Hiệu năng của hệ thống máy tính là tỉ lệ giữa khối lượng công việc hữu ích được

hoàn thành so với các chi phí về thời gian và tài nguyên phải bỏ ra

Các thông số (độ đo) chính dùng để phân tích hiệu năng bao gồm: Tính sẵn sàng (Availability), thời gian đáp ứng (Response time), mức tăng tốc (Speedup hay Processing speed), độ trễ (Latency), băng thông (Bandwidth), thông lượng (Throughput) Các nghiên cứu về phân tích hiệu năng có nhiệm vụ đề xuất và đưa ra các giải pháp nhằm cải thiện các độ đo này

Đối với các hệ thống tính toán song song, có ba độ đo chính thường được dùng

để phân tích, đánh giá hiệu năng [13], bao gồm: Mức tăng tốc, Tính hiệu quả và

Tính mở rộng

1.2.2 Thời gian thực thi

Có hai thông số thời gian trong đo hiệu năng, là thời gian thực thi tuần tự và thời gian thực thi song song Thời gian thực thi tuần tự là thời gian từ thời điểm bắt đầu cho đến thời điểm kết thúc thực thi công việc trên một máy tính tuần tự, ký hiệu là

T s hay T 1 (Số 1 thể hiện là có một đơn vị xử lý) 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à T p

1.2.3 Tổng chi phí song song

Chi phí mà một chương trình song song tiêu tốn được biểu diễn bởi một biểu thức và được gọi là hàm chi phí Người ta định nghĩa hàm chi phí hay tổng chi phí của hệ thống tính toán song song là tổng thời gian được sử dụng bởi tất cả các phần

tử xử lý so với chi phí khi sử dụng giải thuật tuần tự nhanh nhất có thể khi cùng giải quyết một bài toán trên một phần tử xử lý đơn lẻ Ký hiệu cho hàm chi phí của hệ

thống song song là T o [13]

Tổng thời gian sử dụng của tất cả n phần tử xử lý để giải quyết một bài toán là

nT p Trong số đó sẽ cần đến T s thời gian để thực hiện các công việc không thể song

song hóa, phần còn lại chính là chi phí Vì vậy, hàm chi phí T o được xác định bởi công thức:

T o = pT p - T s

1.2.4 Mức tăng tốc

Khi phân tích một hệ thống tính toán song song, người ta thường quan tâm xem hiệu năng đạt được bởi việc song song hóa là bao nhiêu so với cài đặt tuần tự Mức tăng tốc chính là đơn vị đo một cách tương đối lợi ích thu được khi giải quyết một bài toán bằng xử lý song song Nó được định nghĩa là tỉ lệ giữa thời gian cần để giải quyết bởi một phần tử xử lý đơn lẻ với thời gian cần thiết để giải quyết cùng một

bài toán đó trên máy tính song song với n phần tử xử lý giống hệt nhau Ký hiệu mức tăng tốc là S

Nếu gọi thời gian để giải quyết bài toán trên máy tính tuần tự là T s và thời gian

để giải quyết cũng bài toán ấy trên hệ thống tính toán song song là T p, thì mức tăng tốc được định nghĩa như sau:

Sp T s

Thời gian T p ở trên sẽ bao gồm 2 phần, phần xử lý tuần tự (t s) và phần có thể

song song hóa (t p ) Tức là: T p =t s +t p

Do phần thời gian t p có thể thực hiện song song nên nếu có n phần tử xử lý thì

thời gian cần thiết để hoàn thành sẽ là tp/n Khi đó, công thức (1.1) trở thành:

Theo công thức (1.2), nếu thời gian xử lý của phần tuần tự là 10%, của phần song song là 90% thì mức tăng tốc ứng với số phần tử xử lý là 8, 16, 32 tương ứng

sẽ là 4,7; 6,4 và 7,8 lần

Rõ ràng, dù tăng gấp đôi số phần tử xử lý nhưng mức tăng tốc thì không hẳn tăng được như vậy Việc tăng bao nhiêu còn tùy thuộc vào phần xử lý tuần tự

Có ba khả năng đối với mức tăng tốc [13], đó là: Tuyến tính (Linear), tuyến tính

một phần (Sublinear) và siêu tuyến tính (Super-Linear) Như minh họa trong Hình

1.10:

 Trường hợp đạt tuyến tính khi mức tăng tốc bằng số phần tử tham gia xử

lý Tức là nếu ta có p phần tử tham gia xử lý thì mức tăng tốc sẽ tăng lên p lần

 Trường hợp đạt tuyến tính một phần khi ta có p phần tử tham gia xử lý nhưng mức tăng tốc sẽ nhỏ hơn p Lý do chủ yếu là do trễ truyền thông giữa các

phần tử xử lý, do đồng bộ các tiến trình, do cân bằng tải v.v

 Trường hợp đạt siêu tuyến tính chủ yếu có được do tổ chức bộ nhớ Cache tốt hoặc do hệ thống có kích thước bộ nhớ cache lớn

Hình 1.10 Mức tăng tốc và số phần tử tham gia xử lý

1.2.5 Tính hiệu quả

Thông số mức tăng tốc ở trên mới chỉ cho biết thời gian giảm đi bao nhiêu lần nếu xử lý trên hệ thống song song mà không quan tâm đến việc đã sử dụng thêm bao nhiêu phần tử tham gia xử lý Vì vậy, một số đo khác được sử dụng để cho biết

tính hiệu quả khi đầu tư thêm số phần tử tham gia xử lý đó là Tính hiệu quả

Tính hiệu quả được đo bằng mức tăng tốc thu được so với số phần tử tham gia vào quá trình tính toán

Gọi n là số phần tử tham gia tính toán song song và E n là mức độ hiệu quả thì:

Siêu tuyến tính

Tuyến tính

Tuyến tính một phần

S P

n (#số bộ xử lý)

(SCALability Analyzer) là một framework dùng phát triển mô hình hóa hiệu năng

và các hệ thống dự báo

1.3 Các kỹ thuật phân tích, đánh giá hiệu năng

Hiệu năng của một hệ thống kỹ thuật được đánh giá qua thông số khác nhau phụ thuộc vào đặc điểm của từng loại hệ thống kỹ thuật Mục tiêu của chúng ta là các hệ thống máy tính, mạng máy tính và mạng các dịch vụ viễn thông tích hợp kỹ thuật máy tính và vi xử lý Hiệu năng của các hệ thống này liên quan đến các số đo như: thời gian đáp ứng, thời gian thực hiện, mức độ sử dụng, thông lượng, dung lượng,

sử dụng băng thông, trễ, mất thông tin, nghẽn, độ sẵn sàng, độ tin cậy, v.v…

Các kỹ thuật để phân tích hiệu năng của hệ thống máy tính được chia thành 3 loại: mô hình phân tích (analytic modeling), mô hình mô phỏng (simulation modeling) và đo hiệu năng (benchmarking)

Mô hình phân tích và mô hình mô phỏng đều yêu cầu phải xây dựng mô hình

Mô hình là biểu diễn trừu tượng của hệ thống thực Phương pháp đo đạc hiệu năng (gồm cả benchmarks) không sử dụng các mô hình mà thay vào đó, sử dụng quan sát trực tiếp hệ thống, hoặc hệ thống tương tự

1.3.1 Mô hình phân tích

Mô hình phân tích là một cấu trúc toán học biểu diễn các bộ phận then chốt của một hệ thống máy tính Các mô hình phân tích hiệu năng là công cụ hữu hiệu để đánh giá hiệu năng của một sản phẩm mới hoặc sản phẩm được cải tiến Nghệ thuật của mô hình phân tích là sự chọn lựa một mô hình tốt chứa đựng các đặc tính nổi bật của hệ thống mà không cần phải làm rõ ràng chúng trong nhiều chi tiết không liên quan Chúng cũng phù hợp để so sánh hiệu năng của một số thiết kế khác nhau

Có một số kỹ thuật mô hình phân tích được sử dụng để phân tích hiệu năng của hệ thống máy tính:

 Các tính toán giới hạn (bounding calculations): là các tính toán đơn giản

được thực hiện để đánh giá nhanh thông lượng tối đa của một thành phần riêng

lẻ của hệ thống Các tính toán giới hạn có thể thực hiện nhanh và dễ hiểu, nhưng chúng có một số hạn chế lớn Cụ thể, trong một số trường hợp, chúng không mang lại các dự đoán chính xác do hệ thống thực thường phức tạp hơn nhiều Các tính toán giới hạn thường đơn giản hoặc không thể dự đoán được các nguồn gây trễ, hay không thể mô hình hóa được bất kỳ tương tác nào giữa các thành phần của hệ thống

 Các mô hình mạng hàng đợi: Mạng hàng đợi biểu diễn một hệ thống máy tính

như một tập hợp các trung tâm phục vụ xử lý các yêu cầu khách hàng (cũng được biết như các công việc, các giao dịch, hoặc các cuộc đến) Các trung tâm phục vụ có thể là bất kỳ tài nguyên hoạt động nào, như CPU, ổ đĩa của hệ thống, máy tính hay liên kết mạng truyền thông Với các mô hình mạng hàng đợi, người ta có thể tính toán trễ, thông lượng, mức độ sử dụng của từng thành phần

và của toàn bộ hệ thống Trong nhiều trường hợp, thông lượng và mức độ sử dụng được dự đoán nằm trong khoảng 10% của các giá trị đo, trong khi các dự đoán trễ là trong khoảng 30% Có một số loại mô hình mạng hàng đợi sử dụng

cho phân tích hiệu năng hệ thống như mạng hàng đợi đóng có nghiệm dạng tích các xác suất, mạng hàng đợi BCMP (sẽ được đề cập chi tiết ở các chương sau)

 Mô hình tiệm cận ranh giới (asymptotic bounds model): là ứng dụng đơn giản

nhất của các mô hình mạng hàng đợi Chúng được sử dụng để dự đoán thông lượng và trễ trong các trường hợp xấu nhất và tốt nhất của trung tâm phục vụ Thông thường, việc sử dụng mô hình tiệm cận ranh giới là để kiểm tra hành vi của một tài nguyên gây nghẽn cổ chai dưới các tải khác nhau Những tính toán này có thể được thực hiện thủ công

 Các mô hình mạng hàng đợi mở, đóng: có nghiệm dạng tích các xác suất

(Open Product Form Queuing Network-OPFQN, Closed Product Form Queuing Network - CPFQN) và không có nghiệm dạng tích xác suất (NPFQN) Các tính toán hiệu năng được thực hiện bởi các định luật Jackson và các thuật toán lặp, như MVA, Các mô hình mạng hàng đợi là công cụ mạnh cho phân tích hiệu năng của hệ thống, nhưng chúng cũng có một số hạn chế: thứ nhất, các giải pháp của chúng yêu cầu thỏa mãn các điều kiện để phân biệt mô hình, mà trong một

số trường hợp làm cho mô hình có sự khác biệt lớn với hệ thống thực; thứ hai: các mô hình hàng đợi không phù hợp để mô hình hóa các tài nguyên thụ động như các bộ nhớ đệm

 Các chuỗi Markov: các chuỗi Markov có thể được sử dụng để mô hình hệ

thống thực như là một tập hợp các trạng thái với các tốc độ chuyển đổi trạng thái trước đó đã được biết Chúng phù hợp để dự đoán độ sẵn sàng của hệ thống và cho biết tỉ lệ lỗi và tốc độ sửa chữa (phục hồi) của các thành phần Chúng cũng

có thể được sử dụng để mô hình các bộ nhớ đệm và các hàng đợi chứa một số ít các thành phần tương tự nhau

Các công cụ của mô hình phân tích: có một số công cụ dùng để đánh giá các mô

hình mạng hàng đợi, chuỗi Markov, hoặc các mô hình phân tích hiệu năng, gồm:

 PDQ: phần mềm mã nguồn mở (ngôn ngữ C) để đánh giá các mô hình mạng hàng đợi của các hệ thống máy tính (truy cập tại địa chỉ www.perfdynamics.com/Tools/PDQ.html)

 Wolfram Research’s MathematicaR: công cụ mạnh cho các tính toán tượng trưng và tính toán số cho đánh giá các mô hình mạng hàng đợi và các chuỗi Markov (truy cập tại địa chỉ www.wolfram.com/Mathematica)

 Một số phần mềm đánh giá các mô hình mạng hàng đợi của Giáo sư Myron Hlynka, Đại học Windsor

 PEPSY-QNS (University of Debrecen, Hungary; University of Erlangen, Gemany): là một công cụ dùng để mô phỏng mạng

1.3.2 Mô hình mô phỏng

Mô phỏng là kỹ thuật được sử dụng rộng rãi trong phân tích hiệu năng Nó là một cách để dự báo hiệu năng trước khi hệ thống trước khi được cài đặt và cũng có thể được dùng để kiểm chứng kết quả của các mô hình phân tích [47]

Một số phương pháp mô phỏng được sử dụng phổ biến như: giả lập (emulation),

mô phỏng Monte Carlo, mô phỏng hướng theo dấu vết (trace-driven), mô phỏng

hướng thực hiện (execution-driven) và mô phỏng sự kiện rời rạc (Discrete-event),

cụ thể như sau [47]:

 Giả lập (Emulation)

Giả lập là phương pháp dùng các kỹ thuật hoặc xây dựng các chương trình để

mô phỏng các hành vi của hệ thống cần nghiên cứu Ví dụ, dùng một bộ xử lý để

mô phỏng các lệnh của một bộ vi xử lý khác

 Mô phỏng Monter Carlo

Mô phỏng Monte Carlo là một dạng mô phỏng tĩnh trong đó các hệ thống được

mô phỏng không thay đổi các đặc tính của nó theo thời gian Tuy nhiên, các hệ thống máy tính là động, do vậy không thuộc dạng này

 Mô phỏng hướng theo dấu vết

Là dạng mô phỏng trong đó thành phần sinh ra sự kiện (Event generator) của hệ thống sẽ tạo ra một vết các sự kiện thực thi, chủ yếu là các địa chỉ và các địa chỉ này

sẽ được sử dụng làm đầu vào của chương trình mô phỏng Thành phần mô phỏng (Simulator) của hệ thống sẽ sử dụng các dữ liệu này và mô phỏng kiến trúc đích nhằm ước lượng thời gian tiêu tốn khi thực hiện nó trên hệ thống đang nghiên cứu

 Mô phỏng hướng thực hiện

Mô phỏng dựa vào thực hiện: được sử dụng để mô hình hóa các bộ xử lý với các chi tiết Đầu vào của mô phỏng loại này là chương trình thực hiện mà hệ thống thực

sẽ chạy Nó có tác dụng đòn bẩy các chương trình biên dịch hiện có và cho phép nhiều loại tải khác nhau được mô hình

 Mô phỏng sự kiện rời rạc

Là một phương pháp sử dụng để mô phỏng các hệ thống mà ở đó hệ thống có thể được mô tả bằng các các mô hình sự kiện rời rạc Ví dụ các gói tin đến và đi của một bộ định tuyến mạng có thể sử dụng phương pháp này để mô phỏng

Nhược điểm chính trong bất kỳ dạng mô phỏng nào đó là cần phải viết và đánh giá chương trình mô phỏng và thường là những yêu cầu tính toán rất đáng kể (thời gian của bộ xử lý cho tất cả các mô phỏng, không gian nhớ của đĩa cho các vết) Nói chung, hệ thống mô phỏng sẽ phải chạy chậm hơn nhiều lần so với hệ thống thực: Có thể một giờ chạy mô phỏng chỉ bằng vài giây chạy trên hệ thống thực

1.3.3 Đo hiệu năng

Đo hiệu năng là kỹ thuật sử dụng các công cụ phần cứng, phần mềm hoặc kết hợp cả hai để thực hiện phân tích hiệu năng bằng cách đo kiểm (Benchmark)

Có ba dạng đo kiểm [13], bao gồm:

1) Đo kiểm bằng chương trình giả (Synthetic programs hay Synthetic benchmarks): Kỹ thuật này thực hiện bởi các chương trình phần mềm được thiết kế

để mô phỏng tải thực [47] Các chương trình này sinh ra tải bằng cách không thực hiện các công việc “có ích” mà chỉ đơn giản là tiêu tốn các tài nguyên hoặc gửi các yêu cầu đến hệ thống Phương pháp này có ưu điểm là có thể áp dụng cho nhiều bài toán và không nhất thiết phải sử dụng dữ liệu thật Tuy nhiên, có nhược điểm là

tương đối đơn giản, và nhiều khi không phản ánh chính xác các vấn đề phát sinh trong hệ thống, chẳng hạn như bộ nhớ cache Một số chương trình phần mềm dạng này như [13]: Hyper Pi, Sisoft Sandra, wPrime

2) Đo kiểm phần cốt lõi (Kernel benchmarks)

Đây là kỹ thuật thực hiện đo kiểm hiệu năng hệ thống bằng phân tích những đoạn mã lệnh mà sử dụng nhiều nhất đến các tài nguyên của hệ thống Những nhà phân tích hiệu năng sẽ trích xuất các đoạn mã lệnh này và sử dụng chúng để phục

vụ cho việc đo kiểm Một số chương trình đo kiểm nổi tiếng như: LINPACK, PARKBENCH

3) Đo kiểm bằng chương trình thực (Real application benchmarks)

Rất nhiều hệ thống được thiết kế cho một yêu cầu cụ thể nào đó, chẳng hạn như hệ thống đặt vé máy bay hay hệ thông quản trị doanh nghiệp v.v Để phân tích hiệu năng của các hệ thống này, nhìn chung thì phương pháp đo kiểm dùng chương trình giả là không đủ Khi đó, người ta sẽ dùng một chương trình đo kiểm thực sự [47] Chương trình đo kiểm này sẽ kết hợp một số chức năng điển hình tương tự như của hệ thống cần đo có thể sử dụng Không giống như phương pháp đo kiểm bằng chương trình giả, ở đây nó sẽ thực hiện một số công việc thực thụ giống như chương trình chuẩn cần đo

Một ví dụ cho việc đo kiểm hiệu năng của hệ thống đó là phần mềm xử lý các giao dịch trong lĩnh vực ngân hàng Khi đó người ta xây dựng sẵn một chương trình đo kiểm, tạm gọi là chuẩn và có các chức năng cơ bản của phần mềm xử lý giao dịch ngân hàng thực thụ Sau đó người ta sẽ so sánh (ví dụ là số giao dịch xử lý được trong một khoảng thời gian cho trước) với phần mềm cần đo kiểm hiệu năng

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ễ trong tính toán song song

Trong các hệ thống tính toán song song, luôn tồn tại các trễ và chi phí phát sinh [61] Cho dù thuật toán nào được áp dụng đi nữa thì các thành phần xử lý vẫn phải có ít nhiều sự phụ thuộc vào dữ liệu hay kết quả tính toán trung gian của nhau

Do đó, luôn có sự tồn tại các truyền thông giữa các phần tử xử lý và việc xác định các trễ này là một công việc quan trọng để hiểu rõ hiệu năng của hệ thống song song đó [61]

Các nguồn gây trễ trong các tính toán song song bao gồm: Quá trình khởi tạo kết nối, quá trình đồng bộ, truyền thông giữa các tiến trình, phân chia công việc cho các tiến trình hay cho các phần tử tính toán,

Hình 1.11 Minh họa chi phí về thời gian trong xử lý song song [61]

Hình 1.11 minh họa 8 đơn vị tính toán (P 0 , ,P 7) cùng tham gia thực hiện chương trình song song Thời gian thực hiện tính toán trên hệ thống song song bao gồm thời gian tính toán cơ bản và thời gian tính toán dư thừa và trễ truyền thông

giữa các đơn vị tính toán:

- Thời gian tính toán cơ bản (Essential) là thời gian để xử lý các nhiệm vụ chính của bài toán

- Thời gian tính toán dư thừa (Excess): Trong hệ thống tính toán song song, các phần tử ngoài phần tính toán chính thì còn phải thực hiện thêm các tính toán khác so với khi thực hiện giải thuật tuần tự Một ví dụ cho việc này đó là bài toán biến đổi Fourier nhanh (Fast Fourier Transform) Ở bài toán này, trong phiên bản giải thuật tuần tự có thể sử dụng lại được một số kết quả biến đổi trước đó, tuy nhiên sang giải thuật song song không thể sử dụng được kết quả này vì chúng được sinh ra ở các phần tử xử lý khác nhau Như vậy, nếu cùng một khối lượng công việc thì thời gian một đơn vị xử lý phải thực hiện trong giải thuật song song sẽ lớn hơn thời gian mà chính đơn vị xử lý đó thực hiện với giải thuật tuần tự và thời gian này gọi là thời gian tính toán dư thừa (Excess computation)

- Trễ truyền thông giữa các đơn vị tính toán: Là thời gian cần phải truyền thông dữ liệu hoặc chuyển kết quả giữa các đơn vị tính toán với nhau hay cũng có thể là thời gian chờ đợi và đồng bộ hóa

1.4.2 Trễ truyền thông trong hệ thống tính toán song song

Giữa các tiến trình thường có sự trao đổi dữ liệu trung gian với nhau, do đó

sẽ xuất hiện trễ truyền thông giữa chúng (hay giữa các bộ xử lý qua mạng liên kết)

Truyền thông giữa các đơn vị xử lý có thể bị tạm dừng (hay tạm bị khóa) (processor idle) do nhiều lý do của điều khiển song song như: cân bằng tải, đồng bộ hóa và có thể phải thực hiện các thành phần tuần tự trong chương trình Trong nhiều ứng dụng song song, không thể hoặc là rất khó khăn để dự đoán kích thước của các nhiệm vụ nhỏ gán cho các bộ xử lý khác nhau Do vậy, có thể các đơn vị xử lý chịu tải khác nhau, dẫn đến, một số đơn vị xử lý chịu tải thấp có thời gian tính toán nhanh hơn sẽ phải chờ đợi các đơn vị xử lý đối tác truyền dữ liệu chịu tải lớn có thời gian tính toán chậm hơn

Trong điều kiện lý tưởng, thuật toán áp dụng cho thực hiện chương trình song song đảm bảo có sự cân bằng tải cho tất cả các đơn vị xử lý, thì sự cân bằng tải

và đồng bộ đảm bảo không có thời gian nghỉ của các đơn vị xử lý trong quá trình thực hiện tính toán song song Khi đó trễ chỉ chi phí cho truyền dữ liệu giữa các đơn

vị xử lý và trễ lúc này phụ thuộc vào kích thước dữ liệu (gói tin) mà các đơn vị xử

lý chuyển cho nhau, công nghệ và cấu hình mạng liên kết các đơn vị xử lý

Ảnh hưởng của công nghệ mạng, của cấu hình mạng liên kết các đơn vị xử lý trong các kiến trúc song song: chip đa xử lý, hệ thống nhiều máy tính (multicomputer system) như siêu máy tính cho đến trễ truyền thông là một vấn đề được nhiều nghiên cứu quan tâm [16,24, 57, 64] Bởi nó là yếu tố chính làm thay đổi tốc độ tính toán và qua đó là ảnh hưởng đến hiệu năng của các hệ thống tính toán song song

1.4.3 Mạng liên kết trong các hệ thống tính toán song song

Khi kết nối các phần tử xử lý trong hệ thống tính toán song song với nhau,

dù ở ngay trong phạm vi một chip đa lõi (mô hình bộ nhớ chia sẻ - Hình 1.12 a) hay

một hệ thống tính toán song song ghép cụm (mô hình bộ nhớ phân tán – Hình 1.12 b) thì đều cần phải cần đến một mạng kết nối các phần tử này lại Các mạng này có thể kết nối theo Topo kiểu lưới hai chiều, lưới vòng hai chiều, hay ba chiều, lưới vòng ba chiều, Hypercube (Hình 1.13) v.v

Hình 1.12 a) Mô hình bộ nhớ chia sẻ – b) Mô hình bộ nhớ phân tán

Mạng liên kết (Interconnection Network) các phần tử xử lý và các module bộ nhớ ở trên rất đa dạng Tùy thuộc vào từng nhà sản xuất, từng kiến trúc cụ thể mà người ta có thể dùng các mô hình mạng lưới hai chiều, lưới vòng hai chiều, lưới ba chiều, lưới vòng ba chiều, siêu lập phương, để kết nối Mỗi một loại mạng khác nhau sẽ có những độ trễ khác nhau và theo [57] thì mạng liên kết đóng vai trò then chốt trong việc phân tích và thiết kế hệ thống song song bởi nó là một trong những thành phần quyết định đến hiệu năng của toàn bộ hệ thống

Mạng liên kết

Mạng liên kết

a) Mạng liên kết lưới hai chiều b) Mạng liên kết lưới vòng hai chiều

c) Mạng liên kết siêu lập phương - Hypercube

Hình 1.13 Một số mạng liên kết phổ biến

Việc nghiên cứu và phân tích sự ảnh hưởng của trễ thuyền thông và mạng

liên kết đến hiệu năng của hệ thống tính toán song song là nhiệm vụ trọng tâm của

luận án và sẽ được trình bày trong Chương 3

1.5 Tổng quan về các nghiên cứu liên quan

Các hệ thống tính toán song song ngày nay đều dựa trên các kiến trúc đa xử lý, chip đa lõi Công nghệ chip nhiều lõi xử lý được sử dụng làm các nút xử lý trong các hệ thống tính toán song song là xu hướng chính hiện nay trong các thiết kế các máy tính hiệu năng cao và siêu máy tính Theo luật Amdahl [92], mức tăng tốc lý tưởng chỉ phụ thuộc tuyến tính vào số bộ xử lý Nhưng, thực tế, với những thuật toán song song tốt nhất cũng không thể bỏ qua các tiến trình truyền thông giữa các

bộ xử lý để trao đổi các kết quả dữ liệu trung gian Càng nhiều nút xử lý, càng nhiều tiến trình truyền thông giữa các nút xử lý, không gian mạng liên kết truyền thông càng rộng thì trễ truyền thông sẽ càng tăng Do đó, mục tiêu của nhiều nghiên cứu ngày nay tập trung vào các giải pháp tăng hiệu năng nhờ tăng tốc độ tính toán với việc giảm trễ truyền thông của các hệ thống tính toán song song đa xử lý

Về tình hình nghiên cứu ngoài nước, có rất nhiều các nghiên cứu về phân tích hiệu năng của các kiến trúc và hệ thống tính toán song song El-Rewini và các cộng

sự [30] đề cập khá đầy đủ các khía cạnh liên quan đến phần cứng và phần mềm trong tính toán song song, như: mô hình tính toán song song; các mạng kết nối được

sử dụng trong kiến trúc tính toán song song; phân tích hiệu năng đối với kiến trúc

đa xử lý (Multi Processors); mô hình kiến trúc chia sẻ bộ nhớ, mô hình truyền thông

điệp; đo hiệu năng Trễ truyền thông cũng được El-Rewini và các cộng sự đề cập đến khi áp dụng luật Amdahl để tính mức tăng tốc, cụ thể trễ được tác giả đưa vào công thức Amdahl để tính mức tăng tốc như sau:

là thời gian hoàn thành công việc trên một bộ xử lý hay T 1 còn được gọi là thời gian

xử lý trên hệ thống tính toán tuần tự Tuy nhiên, đại lượng T overhead trong các nghiên cứu chưa được các tác giả chỉ ra là tính như thế nào và phương pháp tính là gì, bởi đại lượng này hoàn toàn phụ thuộc vào cấu trúc mạng, công nghệ mạng cụ thể và bài toán cụ thể

Chugh và các cộng sự [19] sử dụng mô hình hàng đợi và mạng hàng đợi (gồm

cả mô hình mạng hàng đợi nhiều lớp) để phân tích hiệu năng tương ứng với các giải thuật giá trịnh trung bình (Mean Valued Algorithm-MVA) khác nhau được sử dụng Paul Beekhuizen đề cập đến các loại mạng sử dụng trong các chip đa lõi và phân tích hiệu năng của các mạng trên chip này [75] Fashanu và các cộng sự [31] cung cấp các lý thuyết cơ bản về phân tích hiệu năng của kiến trúc đa lõi và áp dụng luật Amdahl, luật Gustafson trong việc đo mức tăng tốc, trong đó đã đề cập đến thời gian trễ (Overhead time-Ot) trong công thức tính mức tăng tốc Các nghiên cứu ngoài nước về hiệu năng của tính toán song song tập trung ở các giải pháp sau đây: 1) Nghiên cứu các thuật toán song song cho các ứng dụng riêng biệt, các tính toán

ma trận trên một số kiến trúc hệ thống tính toán đa xử lý, đặc biệt sử dụng kiến trúc có sử dụng bộ tăng tốc đồ họa [18, 21, 31, 41, 78, 83, 87]

2) Nghiên cứu các cấu hình và công nghệ truyền dẫn mới (công nghệ Infiniband) của mạng liên kết đa xử lý trong hệ thống nhiều máy, nhiều chip đa xử lý (multiprocessor interconnect) và trong chip đa xử lý (on chip interconnect) [9,

15, 16, 24, 37, 55, 62, 64, 69, 70, 77, 102]

3) Nghiên cứu giao thức MPI trên các hệ thống tính toán song song [16, 39]

4) Thiết kế các kiến trúc hệ thống tính toán song song hiệu năng cao và chi phí thấp như kiến trúc cụm các máy tính, các hệ thống siêu máy tính lớn sử dụng chip vi

xử lý nhiều lõi, các đồng xử lý tăng tốc đồ họa của Nvidia [27, 67, 101]

Các tác giả trong [67] nghiên cứu ảnh hưởng của trễ truyền thông và băng thông đến hiệu năng của kiến trúc tính toán song song ghép cụm và đề xuất một số phương pháp nhằm cải tiến hiệu năng của hệ thống này thông qua quan sát thực nghiệm Các kết quả nghiên cứu và thực nghiệm trong bài báo đã chứng minh sự ảnh hưởng của trễ truyền thông đến hiệu năng của hệ thống Tuy nhiên, nghiên cứu mới chỉ đề cập một cách chung chung về trễ truyền thông mà chưa đề cập cụ thể đến sự ảnh hưởng của các loại kết nối mạng được sử dụng trong các đánh giá đó Trong [47], các tác giả đã tính toán và đưa ra các công thức về mức tăng tốc và tính hiệu quả Các công thức này đều được giả thiết là không tính đến độ trễ do truyền thông và các chi phí phát sinh khác của hệ thống Công thức mức tăng tốc (giả thiết số đơn vị xử lý không bị giới hạn) khi đó được tác giả tính toán như sau:

  ∑∑

∑

∑ (1.5)

Với W i là khối lượng công việc được thực thi với mức độ song song là i, m là

mức độ song song tối đa trong toàn bộ quá trình thực hiện

Nếu có tính đến trễ truyền thông thì công thức mức tăng tốc được Tác giả tính toán là:

∑

∑ 

Với Q(n) là tổng các trễ Đại lượng này được tác giả đưa vào công thức mức

tăng tốc nhưng không chỉ ra cách tính toán nó cụ thể như thế nào

Một số nghiên cứu sử dụng đến các công cụ mô phỏng để phân tích và đánh giá hiệu năng (Như mạng Petri, mạng hàng đợi và chuỗi Markov, OPNet++) nhưng vẫn chưa đầy đủ, đặc biệt là sử dụng các mô hình có tính thời gian và dữ liệu Các phân tích này cũng ít so sánh về tính đặc trưng Tiêu biểu như [13] đã chỉ ra trễ trong công thức Amdahl, tuy nhiên lại không tính toán hay đưa ra công thức cụ thể, mà chỉ nói rằng trễ đó ảnh hưởng bởi quá trình đồng bộ, truyền thông giữa các vi xử lý

và các vấn đề khác

Về các nghiên cứu ở trong nước, theo tìm hiểu của tác giả thì các kết quả nghiên cứu về 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 trên các tạp chí, hội thảo hiện nay còn khá khiêm tốn Có thể lý giải điều này là bởi các trung tâm tính toán hiệu năng cao phục vụ cho thử nghiệm chưa được đầu tư đúng mức hoặc mới chỉ ở giai đoạn đầu tư nghiên cứu ban đầu Một số trung tâm tính toán hiệu năng cao như của Trường Đại học Bách Khoa Hà Nội (Thành lập năm 2001), Đại học Quốc gia Hà nội (Năm 2005), Đại học Quốc gia TP.Hồ Chí Minh (Năm 2012), Viện hàn lâm khoa học và công nghệ Việt nam (Viện HLKH&CNVN) (Năm 2013) được hình thành với hạ tầng phần cứng chủ yếu nhập sẵn và được tài trợ hoặc mua từ nước ngoài Riêng đối với Trung tâm Tin học

và tính toán thuộc Viện HLKH&CNVN đã triển khai hệ thống tính toán song song rất mạnh với 24 nút tính toán, mỗi nút này có 24 bộ xử lý trung tâm, trong đó 4 nút

có tích hợp bộ xử lý đồ họa (GPU) Tesla K20M Tốc độ tính toán của toàn hệ thống

đã đạt đến 4Tflops

Về luận án tiến sĩ trong nước, có đề tài “Nghiên cứu phương pháp phân hoạch động tài nguyên hệ thống để tối ưu hoá cấu trúc của hệ xử lý song song chuyên dụng” của tác giả Nguyễn Minh Ngọc, bảo vệ năm 2008 tại Học Viện Kỹ thuật Quân sự, có phân tích ảnh hưởng của các tài nguyên phần cứng của hệ thống đến hiệu năng và đề xuất một số giải pháp tăng hiệu năng của hệ tính toán song song bằng FPGA, tối ưu kiến trúc đường ống theo tiêu chuẩn độ trễ tối thiểu Các nghiên cứu trong luận án này đã tập trung vào kiến trúc bên trong của vi xử lý, còn các yếu

tố ảnh hưởng khác như là mạng liên kết các lõi đã không được tác giả đề cập

Nhóm nghiên cứu tại Trung tâm tính toán hiệu năng cao – Trường ĐHBK Hà Nội của GS.TS Nguyễn Thanh Thủy (Phan Đức Dung, Dương Nhật Tân, Phạm Hồng Phong, Nguyễn Hữu Đức, và Nguyễn Thanh Thủy) có nghiên cứu và đưa ra giải pháp tính toán song song cho bài toán khôi phục mật khẩu tệp nén Zip, sử dụng công nghệ tính toán CUDA Trong nghiên cứu này, các tác giả đã đề giải thuật tính toán song song và chạy trên các bộ tăng tốc đồ họa để thực hiện vét cạn mật khẩu tệp nén Zip Kết quả là tốc độ được cải thiện rất lớn theo khả năng của bộ tăng tốc

đồ họa Tuy nhiên, các tác giả cũng chưa phân tích kỹ khả năng tăng tốc đó sẽ đạt đến giới hạn nào? có thể lắp tối đa bao nhiêu bộ tăng tốc? hay nói cách khác là sự ảnh hưởng của các yếu tố, trong đó có trễ truyền thông đến hiệu năng chung

Một số đề tài nghiên cứu khoa học khác có sử dụng đến các tính toán hiệu năng cao tuy nhiên ở mức độ áp dụng, như: đề tài “Xây dựng hệ thống tính toán, mô phỏng song song đa luồng ứng dụng cho nghiên cứu và đào tạo ngành vật liệu và linh kiện quang tử nano” của TS Ngô Quang Minh, Viện Khoa học Vật liệu 2013-2014; Đề tài cấp nhà nước “Nghiên cứu ứng dụng hệ thống tính toán song song hiệu năng cao để lập trình gia công các bề mặt khuôn mẫu trên máy công cụ CNC” do GS.TSKH Bành Tiến Long 2006 làm chủ nhiệm

Cũng theo tìm hiểu của tác giả, các công bố khoa học liên quan đến phân tích hiệu năng của các hệ thống tính toán song song có thể nói là khá ít trên các tạp chí, hội thảo chuyên ngành Như nghiên cứu triển khai của các tác giả tại Viện HLKH&CNVN tập trung vào khai thác hệ thống tính toán hiệu năng cao này hơn là

đi vào phân tích hiệu năng của chính hệ thống đó (như hỗ trợ phân tích trình tự DNA, di truyền học ngoài gen (epigenetics), di truyền học môi trường (metagenomics), nghiên cứu tương quan toàn bộ nhiễm sắc thể (GWAS))

Phân tích và đánh giá hiệu năng của các hệ thống tính toán song song có sử dụng kiến trúc chip đa xử lý và cụm máy tính là một lĩnh vực nghiên cứu rộng và khó khăn, đòi hỏi nhiều chi phí về thiết bị, công cụ Tuy đã có nhiều nghiên cứu trong và ngoài nước về lĩnh vực này, nhưng thực tế cũng còn rất nhiều vấn đề tiếp tục cần phải nghiên cứu và cải tiến, đặc biệt là sử dụng các cách tiếp cận mới Do

đó, phương pháp nghiên cứu bằng mô phỏng sẽ là tối ưu hơn cả Giải pháp nghiên cứu sử dụng luật Amdahl, mạng Petri và mạng hàng đợi sẽ được đề xuất trong luận

án này Một trong các thông số ảnh hưởng lớn đến tốc độ tính toán của hệ thống tính toán song song đa xử lý là trễ truyền thông trên các cấu hình mạng liên kết khác nhau, mà các nghiên cứu trong và ngoài nước ít đề cập sâu đến, cũng sẽ được luận án đề cập và giải quyết

Luận án này sẽ tập trung phân tích ảnh hưởng của trễ truyền thông đến hiệu năng của hệ thống sử dụng các công cụ chính là mạng hàng đợi và mạng Petri Trong đó sẽ chỉ rõ công thức để tính trễ truyền thông ứng với một số mạng liên kết thông dụng Công thức này sẽ cho phép tính toán mức tăng tốc trong luật Amdahl

có bao gồm yếu tố trễ truyền thông Ngoài ra, luận án cũng tiến hành thử nghiệm một bài toán thực tế chạy trong môi trường song song là thám mã mật khẩu MS Office Word để minh họa thêm yếu tố trễ có ảnh hưởng đến hiệu năng của hệ thống

1.6 Các nhiệm vụ trong luận án

Luận án tập trung vào 4 nhiệm vụ trọng tâm sau đây:

Nhiệm vụ thứ nhất: Nghiên cứu tổng hợp các lý thuyết về sử dụng mạng

hàng đợi đóng có nghiệm dạng tích các xác suất, mạng Petri thời gian ngẫu nhiên chung và mạng Petri có mầu cho mô hình hóa và phân tích, đánh giá hiệu năngphân tích, đánh giá hiệu năng của các hệ thống tính toán song song Xác định mức tăng tốc theo luật Amdahl, một trong những thông số hiệu năng của hệ thống tính toán

song song Tổng hợp các lý thuyết chung này được trình bày trong Chương 2 của

luận án

Nhiệm vụ thứ hai: Trên cơ sở các nghiên cứu trong Nhiệm vụ 1, tác giả đề

xuất mô hình mạng hàng đợi đóng dạng tích, mạng Petri thời gian ngẫu nhiên chung

và mạng Petri có màu cho mô phỏng và phân tích, đánh giá hiệu năng của các kiến trúc chip đa lõi và các hệ thống tính toán song song ghép cụm Nhiệm vụ này được

thể hiện trong Chương 3 và Chương 4 (các mục 4.1 và 4.2.) của luận án

Nhiệm vụ thứ ba: Phân tích ảnh hưởng của trễ truyền thông đến một trong

các thông số hiệu năng là mức tăng tốc của hệ thống tính toán song song và đề xuất công thức tính trễ truyền thông cho một số cấu trúc mạng liên kết được sử dụng phổ

biến trong các kiến trúc song song Nhiệm vụ này được thể hiện trong Chương 4

của luận án

Nhiệm vụ thứ tƣ: thực hiện thiết kế thuật toán và thử nghiệm bài toán thám

mã mật khẩu tài liệu MS Office Word trên hệ thống tính toán song song sử dụng mô hình cụm máy tính kết hợp vi xử lý đa lõi và đánh giá sự ảnh hưởng của trễ truyền thông đến hiệu năng của hệ thống Nội dung này được trình bày trong mục 4.3 của luận án

1.7 Kết chương

Chương này đã trình bày những thông tin tổng quan về luận án, bao gồm những khái niệm cơ bản về tính toán song song; các mô hình tính toán song song; các khái niệm về phân tích hiệu năng và các kỹ thuật phân tích, đánh giá hiệu năng; các nghiên cứu trong và ngoài nước liên quan đến lĩnh vực phân tích hiệu năng đối với các hệ thống tính toán song song và các nhiệm vụ nghiên cứu chính trong luận án

Chương 2 Cơ sở lý thuyết cho phân tích hiệu năng

Các mạng hàng đợi (Queueing Networks) và mạng Petri (Petri nets) là các công cụ toán học rất mạnh trong việc mô hình hóa và phân tích hiệu năng của nhiều hệ thống phức tạp, như các mạng máy tính, các hệ thống viễn thông, các trung tâm cuộc gọi, các hệ thống sản xuất, các hệ thống dịch vụ và nhiều hệ thống trong nhiều lĩnh vực khác nhau

Chương này sẽ đề cập đến một số lý thuyết cơ bản về mạng hàng đợi và mạng Petri, hai công cụ chính và quan trọng trong việc phân tích và đánh giá hiệu năng của các hệ thống tính toán song song, trong đó tập trung trình bày chi tiết mô hình mạng hàng đợi đóng có nghiệm dạng tích các xác suất và mô hình mạng Petri có thời gian chung và mạng Petri màu ngẫu nhiên Ngoài ra, luận án cũng đề cập đến một luật rất quan trọng khi tính toán mức tăng tốc của hệ thống tính toán song song

là luật Amdahl Phần cuối của chương đưa ra các nhận xét, đánh giá về hai công

cụ được dùng để phân tích hiệu năng là mạng hàng đợi và mạng Petri

và được sử dụng để trả lời các câu hỏi như: thời gian chờ đợi trung bình trong hàng đợi, thời gian đáp ứng trung bình của hệ thống phục vụ, mức độ sử dụng trung bình của phương tiện phục vụ, phân bố số khách hàng trong hàng đợi, phân bố số khách hàng trong hệ thống, v.v Những câu hỏi này chủ yếu được khảo sát với những điều kiện cho trước Nghiên cứu lý thuyết hàng đợi đòi hỏi phải có kiến thức cơ bản

về xác suất và chuỗi Markov

Mô hình hàng đợi cơ bản của một trung tâm phục vụ được cho trong Hình 2.1

Các khách hàng tới trung tâm phục vụ 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ỳ ý

Các nút phục vụ

Hình 2.1 Mô hình của trung tâm phục vụ

Đám đông khách hàng

b) Các nguyên tắc phục vụ

Có một số nguyên tắc phục vụ của mạng hàng đợi [11], đó là:

FIFO: (First In, First Out), hay FCFS (First Come First Served): khách hàng

đến trước thì được phục vụ trước

LIFO: (Last in, First Out), LIFS (Last In, First Served): khách hàng đến sau sẽ

được phục vụ trước

SIRO (Service In Random Order): Khách hàng được phục vụ ngẫu nhiên

RR (Round Robin): mỗi khách được phục vụ trong một khoảng thời gian cho

trước và tiếp tục được quay vòng cho đến khi hoàn thành

SJF (Shortest Jobs First): Việc nào cần ít thời gian nhất sẽ được phục vụ trước

c) Các giá trị cơ bản trong mô hình mạng hàng đợi

Trong phân tích mô hình hàng đợi, có một số giá trị cơ bản hay được dùng [11]: )

T - thời gian mà khách hàng thứ i tiêu tốn trong hệ thống

d) Một số luật cơ bản sử dụng trong mô hình hàng đợi [11,28]

- Luật mức độ sử dụng:

][]

[]

C

B T

C T

B U

E    (2.1) Trong đó: E [T]là thông lượng trung bình, E [S]là thời gian phục vụ trung bình Luật mức độ sử dụng trung bình được xác định bởi công thức:

][]

[]

(t T t

N   (2.3) Luật Little đưa ra mối quan hệ quan trọng giữa số lượng khách hàng trung bình )

Giả thiết N(t) E[N], trong đó E[N] là giá trị trung bình của N số lượng khách

hàng ở trong hệ thống và là biến ở trạng thái bền vững và T E [R]với E[R] là giá

trị trung bình của quãng thời gian mà một khách hàng phải lưu lại ở trong hệ thống (thời gian đáp ứng trung bình của hệ thống), thì dạng chung của luật Little: