Tài liệu Phân tích ảnh hưởng của trễ truyền thông đến hiệu năng của hệ thống tính toán song song

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN MINH QUÝ PHÂN TÍCH ẢNH HƯỞNG CỦA TRỄ TRUYỀN THÔNG ĐẾN HIỆU NĂNG CỦA HỆ THỐNG TÍNH TOÁN SONG SONG 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 GV. HƯỚNG DẪN 1 GV. HƯỚNG DẪN 2 PGS.TS Huỳnh Quyết Thắng TS. Hồ Khánh Lâm i TÁC GIẢ LUẬN ÁN 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ý ii 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 iii 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 iv 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 v Danh mục các ký hiệu và chữ viết tắt Ký hiệu, STT chữ viết tắt Ý nghĩa đầy đủ bằng tiếng Anh Ý nghĩa bằng tiếng Việt 1 2DMesh 2 Dimension Mesh Lưới hai chiều 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 5 APN Algebra Petri Net Mạng Petri toán học 6 CDF Cumulative Density Functions Hàm mật độ tích lũy 7 CPFQN 8 CPN Colored Petri Net Mạng Petri có màu 9 CPU Central Processing Unit Bộ xử lý trung tâm 10 CU Control Unit Đơn vị điều khiển 11 CUDA Compute Unified Architecture 12 DMC Dynamic Multicore Chip Chip đa lõi linh hoạt 13 GPGPU General Purpose GPU GPU đa năng 14 GPN Graph Petri Net Mạng Petri đồ thị 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 19 MISD 20 MPI 21 MVA Closed Product Form Queuing Mạng hàng đợi đóng dạng Network tích Device Kiến trúc thiết bị tính toán hợp nhất stream Đa dòng lệnh đa dòng dữ liệu stream Đa dòng lệnh đơn dòng dữ liệu Giao diện truyền thông Message Passing Interface điệp Multiple Instruction Multiple Data stream Multiple Instruction Single Data stream Mean Value Algorithm vi Giải thuật giá trị trung bình Ký hiệu, Ý nghĩa đầy đủ bằng tiếng Anh Ý nghĩa bằng tiếng Việt STT chữ viết tắt 22 OCIN 23 PDF 24 PE Processing Element Phần tử xử lý 25 PN Petri Net Mạng Petri 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 31 TPN Timed Petri Net Mạng Petri có thời gian OnChip INterconnect Mạng liên kết trên chip Probability Distribution Function Hàm phân bố xác suất vii Danh mục các bảng Bảng 3.1 Các đánh dấu ................................................................................. 79 Bảng 3.2 Vị trí và số thẻ trung bình .............................................................. 79 Bảng 3.3 Mật độ xác suất thẻ ....................................................................... 79 Bảng 3.4 Các thời gian lưu lại của các đánh dấu .......................................... 79 Bảng 3.5 Thông lượng của các chuyển tiếp có trễ thời gian .......................... 80 Bảng 4.1 Tlink = tsw + tstartup + wtdata với Infiniband DDR 12x ........................ 85 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 ......... 85 Bảng 4.3 Tnet= H(tsw + tstartup + wtdata) với Infiniband DDR 12x, n=64 nút ..... 85 Bảng 4.4 Tnet= H(tsw + tstartup + wtdata) với Infiniband DDR 12x, n=9 nút ....... 85 Bảng 4.5 Danh sách các vị trí trong processor .............................................. 93 Bảng 4.6 Các chuyển tiếp có trễ kích hoạt của processor .............................. 93 Bảng 4.7 Các chuyển tức thời (trễ thời gian = 0) của processor .................... 93 Bảng 4.8 Danh sách các vị trí trong processor .............................................. 94 Bảng 4.9 Các chuyển tiếp có trễ kích hoạt .................................................... 94 Bảng 4.10 Các chuyển tức thời (trễ thời gian = 0) của Interconnect ............. 94 Bảng 4.11 Các thông số hiệu năng ............................................................... 96 Bảng 4.12 Số lượng khóa theo độ dài xâu .................................................. 103 viii 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 ix 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 ........................................................ 66 Hình 3.6 Một số topo liên kết phổ biến......................................................... 67 Hình 3.7 Mô hình mạng hàng đợi đóng của hệ thống VXL đa lõi................. 70 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 . 74 Hình 3.9 Tỉ lệ giữa thời gian phục vụ và số khách hàng trong CPU1 ............ 74 Hình 3.10 Tỉ lệ giữa thời gian phục vụ và số khách hàng trong mạng .......... 75 Hình 3.11 Tỉ lệ giữa thời gian phục vụ và thời gian chờ đợi trong mạng ...... 75 Hình 3.12 Tỉ lệ giữa thời gian phục vụ và thông lượng của CPU1 ................ 76 Hình 3.13 Mô hình GSPN của vi xử lý đa lõi cho ở Hình 3.5 ....................... 78 Hình 4.1 Các nhiệm vụ song song đồng bộ và không đồng bộ...................... 83 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 .......... 86 sử dụng Infiniband DDR 12X và n=64 processor nodes ............................... 86 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 .......... 86 sử dụng Infiniband DDR 12X và n=9 processor nodes ................................. 86 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ộ ............................................................. 88 Hình 4.5 a. Thông lượng của hệ thống với cấu hình 2DMesh ....................... 89 Hình 4.5 b. Thông lượng của hệ thống với cấu hình 2DTorus ...................... 90 Hình 4.5 c. Thông lượng của hệ thống với cấu hình 3DTorus....................... 90 Hình 4.5 d. Thông lượng của hệ thống với cấu hình Hypercube ................... 91 Hình 4.6 Sơ đồ mô tả hệ thống 5 nút bằng SCPN ......................................... 92 Hình 4.7 SCPN của Interconnect .................................................................. 94 Hình 4.8 SCPN của hệ thống xử lý tính toán song song ghép cụm 2DTorus. 95 Hình 4.9 Kịch bản 1, 8 gói tin ...................................................................... 97 Hình 4.10 Kịch bản 2, 8 gói tin .................................................................... 98 Hình 4.11 Kịch bản 1, 16 gói tin .................................................................. 98 Hình 4.12 Kịch bản 2, 16 gói tin .................................................................. 98 Hình 4.13 Kịch bản 1, 32 gói tin .................................................................. 98 Hình 4.14 Kịch bản 2, 32 gói tin .................................................................. 99 x Hình 4.15 Kịch bản 1, 64 gói tin .................................................................. 99 Hình 4.16 Kịch bản 2, 64 gói tin .................................................................. 99 Hình 4.17 Mô hình thử nghiệm .................................................................. 100 Hình 4.18 Quy trình khôi phục mật khẩu MS Word ................................... 101 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 . 102 Hình 4.20 Chia không gian khóa cho các lõi và nút xử lý ........................... 103 Hình 4.21: Thuật toán tìm khóa trên một lõi xử lý ..................................... 105 Hình 4.22 Chạy trên một nút và sử dụng 1 lõi ............................................ 106 Hình 4.23 Chạy trên một nút và sử dụng 4 lõi ............................................ 107 Hình 4.24. Chạy trên 2 nút, mỗi nút sử dụng 2 lõi ...................................... 107 Hình 4.25 Kết quả thử nghiệm ................................................................... 109 xi 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. 1 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. 2 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: 3 - 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. 4 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 5 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. Bộ xử lý Dòng lệnh (MI) Bộ nhớ M Dòng dữ liệu (MD) P 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 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. I CU D PE M I 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 7090, VAX 11/780. - Đơn dòng lệnh đơn dòng dữ liệu có nhiều hơn một đơn vị chức năng: CDC 6600, CDC Cyber 205, CDC-NASF, CDC Star 100, Cray-1, FPS164, FPS AP-120B, Fujitsu VP 200, Fujitsu FACOM-230/75, IBM 360/91, IBM 370/168UP, IBM 3838, TI-ASC. Những loại này đều là máy tính vector. 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ử 6 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). D1 PE1 I M D2 PE2 M1 M2 CU Dn PEn Mn 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 D M CU1 I1 PE1 CU2 I2 PE2 CUn In PEn I 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. 7