ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  PHAN THỊ GIANG NGHIÊN CỨU VÀ ỨNG DỤNG CÁC THUẬT TOÁN GIẢI CÁC BÀI TOÁN TÍNH TOÁN TRÊN COMPUTER CLUSTER LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii LỜI CAM ĐOAN Học viên xin khẳng định tất cả các kết quả được trình bày trong luận văn là của riêng học viên, không sao chép từ bất kỳ một công trình nào khác. Nếu có điều gì không trung thực, học viên xin hoàn toàn chịu trách nhiệm. Học viên Phan Thị Giang Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii LỜI CẢM ƠN Luận văn được thực hiện tại trường Đại học Công nghệ Thông tin và Truyền Thông – Đại học Thái Nguyên dưới sự hướng dẫn của GS.TS Nguyễn Thanh Thuỷ. Trước hết học viên xin bày tỏ lòng biết ơn sâu sắc tới thầy Nguyễn Thanh Thuỷ, người đã có những định hướng, những kiến thức quý báu, những lời động viên và chỉ bảo giúp học viên vượt qua những khó khăn để học viên hoàn thành tốt luận văn của mình. Học viên xin được bày tỏ lòng cảm ơn và sự kính trọng của mình đến các thầy cô giáo Trường Đại học Công nghệ Thông tin và Truyền Thông, Đại học Thái Nguyên, các thầy bên Viện Công nghệ thông tin, đặc biệt là các thầy cô giáo đã giảng dạy và giúp đỡ học viên trong suốt quá trình học tập tại trường. Học viên cũng đặc biệt cảm ơn tới bạn bè lớp Cao học K9, các đồng nghiệp đã luôn động viên, giúp đỡ học viên trong quá trình học tập và công tác, để học viên hoàn thành nhiệm vụ được giao. Xin chân thành cảm ơn sự quan tâm, giúp đỡ, chia sẻ, động viên về tinh thần và vật chất của người thân trong gia đình, bạn bè để học viên hoàn thành luận văn. Thái Nguyên, tháng 10 năm 2012 Học viên Phan Thị Giang Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv MỤC LỤC LỜI CAM ĐOAN 1 LỜI CẢM ƠN iii MỤC LỤC iv MỞ ĐẦU 1 1. Lý do chọn đề tài 1 2. Đối tượng và phạm vi nghiên cứu 1 3. Hướng nghiên cứu của đề tài 1 4. Phương pháp nghiên cứu 2 5. Ý nghĩa khoa học của đề tài 2 6. Cấu trúc của luận văn 2 Chƣơng 1. LÝ THUYẾT XỬ LÝ SONG SONG VÀ PHÂN TÁN 3 1.1. Giới thiệu chung 3 1.2. Lý thuyết xử lý song song 3 1.2.1. Khái niệm 3 1.2.2. Phân biệt xử lý song song với tuần tự 3 1.2.3. Phân loại máy tính song song 6 1.2.4. Song song hóa trong máy tính tuần tự 11 1.3. Lý thuyết xử lý phân tán 14 1.3.1. Khái niệm 14 1.3.2. Tính toán phân tán 15 1.4. Các phương pháp giải bài toán bằng xử lý song song và phân tán 15 1.4.1. Mô hình gửi/nhận thông báo 16 1.4.3. Mô hình lập trình 19 1.4.4. Lập trình trên cụm máy tính 23 Chƣơng 2. CLUSTER VÀ TÍNH TOÁN PHÂN TÁN BẰNG CLUSTER26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v 2.1. Mô hình chung của hệ thống Cluster 26 2.1.1. Mô hình 26 2.1.2. Chế độ hoạt động của Cluster 27 2.1.3. Một số ứng dụng trong Cluster 29 2.2. Các ưu điểm của hệ thống Cluster 30 2.3. Các thành phần của Cluster Service 32 2.4. Nguyên tắc hoạt động của Server Cluster 37 2.5. Cách cài đặt và cấu hình Cluster trên Linux 42 2.5.1. Khái niệm LVS 43 2.5.2. Các mô hình LVS 44 2.5.3. Mô hình Virtual Server via NAT 44 2.5.4. Mô hình Virtual Server via Tunneling 45 2.5.5. Mô hình Virtual Server via Direct Routing 46 2.5.6. Cách triển khai các mô hình 47 2.5.7. Các bước triển khai LVS via Direct Routing 47 2.6. Tính toán phân tán bằng Cluster 53 2.6.1. Lập trình trên môi trường MPI 53 2.6.2. Cài đặt MPICH2 55 2.6.3. Tính toán trên MPI 57 2.6.4. Các mô hình tương tác trong lập trình MPI 61 Chƣơng 3. CÀI ĐẶT THỬ NGHIỆM 66 3.1. Phương trình vi phân đạo hàm riêng 66 3.2. Phương trình Laplace 67 3.3. Công thức lặp Jacobi 69 3.3.1. Giá trị riêng của ma trận lặp Jacobi 70 3.3.2. Tính toán Jacobi 71 3.4. Song song hóa thuật toán 73 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi 3.5. Kết quả thực hiện 74 3.5.1. Thông tin chung về hệ thống 74 3.5.2. Giao diện và lệnh thực hiện 74 3.5.3. Kết quả thực hiện tuần tự 77 3.5.4. Kết quả thực hiện thực hiện xử lý song song trên nhiều máy 77 3.6. Nhận xét và đánh giá 78 KẾT LUẬN VÀ KIẾN NGHỊ 79 1. Kết luận 79 2. Kiến nghị 79 TÀI LIỆU THAM KHẢO 80 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vii DANH MỤC HÌNH VẼ Hình 1.1. Mô hình xử lý tuần tự 4 Hình 1.2. Mô hình xử lý song song 4 Hình 1.3. Mô hình của kiến trúc SISD 7 Hình 1.4. Mô hình của kiến trúc SIMD 8 Hình 1.5. Mô hình MISD 8 Hình 1.6. Mô hình của kiến trúc MISD 9 Hình 1.6.1. Thực hiện tuần tự và hình ống của hai tiến trình gồm 4 giai đoạn 10 Hình 1.7. (a) Xử lý hình ống theo ALU, (b) Xử lý hình ống theo CU 10 Hình 1.8. Mô hình của kiến trúc MIMD 11 Hình 1.9. Hệ thống bộ nhớ phân cấp 13 Hình 1.10. Dịch đơn chương trình, đa thao tác dữ liệu 20 Hình 1.11. Sự trao đổi thông điệp giữa hai tiến trình 22 Hình 1.12. Sự trao đổi thông điệp của các máy tính trong hệ PVM 24 Hình 1.13. Gọi hàm pvm_psend() và pvm_precv() 25 Hình 2.1. Nguyên lý hoạt động của một Cluster 28 Hình 2.2. Linux Virtual Server 43 Hình 2.3. Mô hình Virtual Server via NAT 45 Hình 2.4. Mô hình Virtual Server via Tunneling 46 Hình 2.5. Mô hình Virtual Server via Direct Routing 47 Hình 2.6. Mô hình chuẩn gồm 4 server 48 Hình 2.7. 6 vi xử lý kết nối với nhau thành hình tròn 63 Hình 2.8. Các vi-xử-lý kết nối với nhau thành lưới 64 Hình 3.1. Miền Ω và đường biên ∂Ω 67 Hình 3.2. Sai phân hữu hạn (Finite difference) 68 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn viii Hình 3.3. Phương trình Laplace/Poisson biểu diễn trên một hình lưới hình chữ nhật với N x x N y điểm. 69 Hình 3.4. Cấu trúc dải của ma trận lặp Jacobi cho phương trình Laplace/ Poisson 70 Hình 3.5. Thực hiện tính toán Jacobi trên một đối tượng 73 Hình 3.6a. Đăng nhập vào trung tâm với tên ccs1.hnue.edu.vn 75 Hình 3.6b. Nhập thông tin tài khoản 75 Hình 3.6c. Sử dụng phần mềm winscp để đăng nhập vào hệ thống 75 Hình 3.6d. Các file trên tài khoản đăng nhập vào hệ thống 76 Hình 3.7. Thời gian thực hiện trên tính toán tuần tự > 200s 77 Hình 3.8a. Lệnh qsub –q l1 –l nodes=2:ppn=4 Laplace.script trên 2 77 Hình 3.8b. Kết quả thời gian thực hiện 77 Hình 3.8c. Kết quả lưu trữ trên tệp. dat 78 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU 1. Lý do chọn đề tài Ngày nay có rất nhiều bài toán phức tạp và các ứng dụng thực tế cần phải tính toán, giải trên một số lượng lớn các dữ liệu, nếu chúng ta sử dụng máy tính thông thường để thực thi thì sẽ mất rất nhiều thời gian và công sức. Để giải quyết được những khó khăn trên chúng ta có thể sử dụng một hệ thống máy tính được kết nối với nhau gọi là Computer Cluster. Trong cuốn luận văn này học viên đã thực hiện tìm hiểu cách thức xây dựng một Computer Cluster cho việc giải quyết bài toán lớn (Phương trình Laplace với công thức lặp Jacobi) bằng cách song song hóa để đưa ra sự so sánh về thời gian thực hiện khi xử lý tuần tự. 2. Đối tƣợng và phạm vi nghiên cứu - Lý thuyết xử lý song song, xử lý phân tán. - Hệ thống Computer Cluster. - Một số bài toán thực tế trong Khoa học kỹ thuật. - Ngôn ngữ xử lý song song MPI (Message Passing Interface). 3. Hƣớng nghiên cứu của đề tài - Nghiên cứu các lý thuyết xử lý song song, xử lý phân tán. - Nghiên cứu cách xây dựng và vận hành Computer Cluster, tìm hiểu các khả năng của Computer Cluster. Nghiên cứu cách cài đặt các thuật toán xử lý song song trên Computer Cluster. - Giải quyết một số bài toán thực tế trong khoa học kỹ thuật. - Tìm hiểu thêm về ngôn ngữ xử lý song song MPI. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 4. Phƣơng pháp nghiên cứu - Về lý thuyết: + Ứng dụng các kết quả của lý thuyết xử lý song song. + Nắm bắt cách thức xây dựng và hoạt động của Computer Cluster, từ đó xây dựng và triển khai Computer Cluster theo yêu cầu của các bài toán. + Nghiên cứu triển khai các thuật toán xử lý song song trên Computer Cluster. - Về thực nghiệm: + Xây dựng và triển khai Computer Cluster. + Cài đặt liên quan tới bài toán thực tế. 5. Ý nghĩa khoa học của đề tài Luận văn nghiên cứu chi tiết lý thuyết xử lý song song và xử lý phân tán, nghiên cứu việc cài đặt hệ thống Cluster server và ứng dụng để giải phương trình vi phân đạo hàm riêng Laplace, một phương trình có ứng dụng lớn trong khoa học kỹ thuật và có cách giải rất phức tạp. Các kết quả khả quan thu được sẽ minh chứng nói lên triển vọng tính toán song song của Computer Cluster. 6. Cấu trúc của luận văn Nội dung của luận văn được chia thành 3 chương như sau: Chương I: Lý thuyết xử lý song song và phân tán. Chương II: Cluster và tính toán phân tán bằng Cluster. Chương III: Cài đặt thử nghiệm. [...]... được lưu trữ trên hai hoặc nhiều hệ thống máy tính Hệ thống cơ sở dữ liệu theo dõi các dữ liệu ở đó được phân phối tới người sử dụng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 1.3.2 Tính toán phân tán Tính toán phân tán là những tính toán được thực hiện trên cơ sở kết hợp khả năng tính toán và truyền thông của hai hay nhiều máy tính trên mạng Mô hình tính toán phân... - Computer Server Cluster Cụ thể chúng ta sẽ tìm hiểu cách thức hoạt động của một Cluster, các bước xây dựng một Cluster cũng như cách lập trình với thư viện xử lý song song MPI trên Cluster 2.1 Mô hình chung của hệ thống Cluster 2.1.1 Mô hình Server Cluster là một mô hình được đưa ra nhằm đáp ứng các nhu cầu ngày càng gia tăng trong việc truy xuất các ứng dụng có tính chất quan trọng như trí tuệ tính. .. để thực hiện các chương trình Mỗi máy tính có thể chạy một hay nhiều tiến trình Các chương trình ứng dụng chạy trong các máy tính thông qua các tiến trình của PVM để trao đổi với nhau trên mạng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 24 Máy tính trạm `PVM Chương trình ứng dụng Máy tính trạm PVM Chương trình ứng dụng Máy tính trạm Trao đổi thông điệp trên mạng PVM... thể làm được Nó là một vấn đề quan tâm đối với các nhà nghiên cứu ngày nay để sử dụng chiến thuật hợp tác tương tự trong việc xây dựng các siêu máy tính có thể thực hiện hàng nghìn tỉ tính toán trong một giây Hầu hết các siêu máy tính đều sử dụng phương pháp xử lý song song, chứa một giàn các bộ vi xử lý cực nhanh, làm việc đồng loạt để giải quyết những bài toán phức tạp, dữ liệu lớn như dự báo thời tiết... trong các hệ thống phân tán không có bộ nhớ chia sẻ để trao đổi dữ liệu với nhau Sự trao đổi được thực hiện bằng cách gửi/nhận thông báo Hiện nay có nhiều công cụ lập trình được sử dụng cho tính toán phân tán ở nhiều mức độ trừu tượng khác nhau, như PVM, MPI, vv 1.4 Các phƣơng pháp giải bài toán bằng xử lý song song và phân tán Những buổi đầu của tính toán với máy tính, tất cả các dữ liệu và mọi sự tính. .. chủ yếu ở phương diện truyền thông và sự đồng bộ các tiến trình Một trong các mục đích chính của xử lý song song là nghiên cứu và xây dựng những thuật toán thích hợp để cài đặt trên các máy tính song song, nghĩa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 là phát triển các thuật toán song song Câu hỏi tự nhiên là đánh giá một thuật toán song song như thế nào được gọi... Đối với thuật toán tuần tự thì chúng ta có thể thống nhất cách đánh giá dựa vào thời gian thực hiện thuật toán, không gian bộ nhớ và khả năng lập trình, v.v Đánh giá thuật toán song song thì phức tạp hơn nhiều, ngoài những tiêu chuẩn trên còn phải bổ sung thêm những tham số về số BXL, khả năng của các bộ nhớ cục bộ, sơ đồ truyền thông và các giao thức đồng bộ hoá, v.v Để cài đặt các thuật toán song... thế xử lý song song để đáp ứng các yêu cầu tính toán của nhiều bài toán trong thực tế Nhiều máy tính có kiến trúc song song như các loại máy tính kiểu SIMD, MISD, MIMD ra đời tạo điều kiện cho công nghệ xử lý song song phát triển cả về mặt công nghệ lẫn triển khai ứng dụng Vấn đề xử lý song song cũng có thể thực hiện được trên các máy tuần tự kiểu Von Neumann bằng cách sử dụng nguyên lý xử lý hình ống... THUYẾT XỬ LÝ SONG SONG VÀ PHÂN TÁN Trong chương này chúng ta sẽ tìm hiểu thế nào là xử lý song song và xử lý phân tán Đồng thời đưa ra các mô hình diễn tả cách thức hoạt động trong việc xử lý dữ liệu 1.1 Giới thiệu chung Hiện nay lý thuyết xử lý song song và xử lý phân tán đang được quan tâm và nghiên cứu để giải quyết những bài toán lớn và cần tốc độ tính toán cao mà trước đó một máy tính không thể làm... xử lý song song Như vậy, để xử lý song song chúng ta phải có nhiều BXL (các đơn vị tính toán độc lập) cùng hoạt động và quan trọng hơn là chúng ta phải thiết kế các thuật toán để chúng cùng tham gia "giải quyết một bài toán" Nói cách khác, những tiến trình thực hiện trên mỗi BXL phải trao đổi dữ liệu với nhau để giải quyết một bài toán cho trước Trường hợp ngược lại thì đó không phải là xử lý song song . tán. - Nghiên cứu cách xây dựng và vận hành Computer Cluster, tìm hiểu các khả năng của Computer Cluster. Nghiên cứu cách cài đặt các thuật toán xử lý song song trên Computer Cluster. - Giải. HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  PHAN THỊ GIANG NGHIÊN CỨU VÀ ỨNG DỤNG CÁC THUẬT TOÁN GIẢI CÁC BÀI TOÁN TÍNH TOÁN TRÊN COMPUTER CLUSTER . của các bài toán. + Nghiên cứu triển khai các thuật toán xử lý song song trên Computer Cluster. - Về thực nghiệm: + Xây dựng và triển khai Computer Cluster. + Cài đặt liên quan tới bài toán