Luận văn 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

ĐẠ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 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 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 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 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 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 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 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 Nx x Ny đ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 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 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 Chƣơng 1 LÝ 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 đượ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 hoặc mô phỏng vụ nổ hạt nhân, vv 1.2. Lý thuyết xử lý song song 1.2.1. Khái niệm Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt đồng thời và cùng tham gia giải quyết một bài toán, nói chung xử lý song song được thực hiện trên những hệ thống đa bộ xử lý [7]. 1.2.2. Phân biệt xử lý song song với tuần tự Trong tính toán tuần tự với một bộ xử lý (BXL) thì tại mỗi thời điểm chỉ thực hiện được một phép toán. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 Hình 1.1: Mô hình xử lý tuần tự - Bài toán được tách thành một chuỗi các câu lệnh rời rạc - Các câu lệnh được thực hiện một cách tuần tự - Tại mỗi thời điểm chỉ thực hiện được một câu lệnh Trong tính toán song song thì nhiều BXL cùng kết hợp với nhau để giải quyết một bài toán nên sẽ giảm được thời gian xử lý vì mỗi thời điểm có thể thực hiện đồng thời nhiều phép toán. Hình 1.2. Mô hình xử lý song song Mục đích của xử lý song song: là thực hiện tính toán nhanh trên cơ sở sử dụng nhiều BXL đồng thời. Cùng với tốc độ xử lý nhanh hơn, việc xử lý song song cũng giải được những bài toán lớn hơn, phức tạp hơn. Ba yếu tố chính dẫn đến việc xây dựng các hệ thống xử lý song song: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 1. Hiện nay giá thành của phần cứng (CPU) giảm mạnh, tạo điều kiện để xây dựng những hệ thống có nhiều BXL với giá thành hợp lý. 2. Sự phát triển của công nghệ mạch tích hợp (VLSI) cho phép tạo ra những hệ thống có hàng triệu transistor trên một chip. 3. Tốc độ xử lý của các BXL theo kiểu Von Neumann đã dần tiến tới giới hạn, không thể cải tiến thêm được do vậy dẫn tới đòi hỏi phải thực hiện xử lý song song. Những yếu tố trên thúc đẩy các nhà nghiên cứu phải tập trung khai thác công nghệ xử lý song song. Vấn đề xử lý song song liên quan trực tiếp đến kiến trúc máy tính, phần mềm hệ thống (hệ điều hành), thuật toán và ngôn ngữ lập trình, v.v Một máy tính song song: là một tập các BXL (thường là cùng một loại) kết nối với nhau theo một kiến trúc nào đó để có thể hợp tác trong hoạt động và trao đổi dữ liệu được với nhau [5]. Các máy tính song song có thể phân thành nhiều loại dựa vào các đặc trưng của các kiến trúc và việc tổ chức bộ nhớ. Phần lớn các hệ điều hành ngày nay đều hỗ trợ đa xử lý/đa nhiệm và cho phép thực hiện việc 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. Chúng ta dễ nhận thấy là độ phức tạp của xử lý song song sẽ lớn hơn xử lý tuần tự rất nhiều, tập trung 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 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 là thích hợp cho xử lý song song? Đố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 song trên các máy tính song song chúng ta phải sử dụng những ngôn ngữ lập trình song song. Nhiều ngôn ngữ lập trình song song đang được sử dụng như: Fortran 90, nCUBE C, Occam, C-Linda, PVM với C/C++, CDC 6600, v.v... 1.2.3. Phân loại máy tính song song Dựa vào các đặc tính về số lượng BXL, số chương trình thực hiện, cấu trúc bộ nhớ, v.v..., Michael Flynn (1966) [8] đã đưa ra cách phân loại nổi tiếng được nhiều người chấp nhận. Máy tính song song được phân chia thành các loại: + SISD: Single Instruction Stream, Single Data Stream: Đơn luồng lệnh, đơn luồng dữ liệu. + SIMD: Single Instruction Stream, Multiple Data Stream: Đơn luồng lệnh, đa luồng dữ liệu. + MISD: Multiple Instruction Stream, Single Data Stream: Đa luồng lệnh, đơn luồng dữ