Giải song song các bài toán có mô hình toán học là các hệ phương trình đạo hàm riêng bằng phương pháp số.

- BỘ GIÁO DỤCVÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHÙNG THỊ HOÀNG GIẢI SONG SONG CÁC BÀI TOÁN CÓ MÔ HÌNH TOÁN HỌC LÀ CÁC HỆ PHƢƠNG TRÌNH ĐẠO HÀM RIÊNG BẰNG PHƢƠNG PHÁP SỐ Chuyên ngành: CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ KỸ THUẬT CÔNG NGHỆ THÔNG TIN Hà nội - 2015 NGƯỜI HƯỚNG DẪN TS.
- VŨ VĂN THIỆU LỜI CAM ĐOAN Luận văn thạc sĩ này do tôi nghiên cứu và thực hiện dưới sự hướng dẫn của thầy giáo TS.Vũ văn Thiệu.
- Để hoàn thành luận văn này, ngoài các tài liệu tham khảo đã liệt kê, tôi cam đoan không sao chép toàn văn các công trình hoặc thiết kế tốt nghiệp của người khác.
- Tác giả luận văn Phùng Thị Hoàng MỤC LỤC DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT.
- Phương pháp số giải hệ phương trình PDEs.
- Mô hình lập trình song song SPMD.
- 7 2.3.2 Các khái niệm cơ bản của MPI.
- 16 2.3.4 Các API MPI.
- 17 Chƣơng 3: Bài toán phƣơng trình truyền nhiệt(HeatEquations.
- 21 3.1.Giới thiệu bài toán Heat Equations.
- Phương pháp số giải bài toán Heat Equations.
- Phương pháp rời rạc hóa theo không gian.
- Phương pháp tích hợp theo thời gian.
- Cài đặt chương trình.
- Cài đặt hàm rời rạc theo không gian.
- Cài đặt hàm tích hợp theo thời gian.
- 29 Chƣơng 4: Phân tích sự phụ thuộc dữ liệu, thiết kế giải thuậttruyền thông và cài đặt chƣơng trình song song.
- Phân tích sự phụ thuộc dữ liệu.
- Thiết kế giải thuật song song.
- Hệ thống tính toán song song.
- 46 DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT STT Viết tắt Tiếng Anh Tiếng Việt 1 PDEs Partial Differential Equations Hệ phương trình đạo hàm riêng 2 CPU Central Processing Unit Bộ vi xử lý 3 RAM Random Access Memory Bộ nhớ truy cập ngẫu nhiên 4 SPMD Single Program Multiple Data Mô hình lập trình song song 5 MPI Message Passing Interface Giao tiếp truyền dữ liệu 6 SD Spatial discretization Rời rạc hóa không gian 7 TI Time integration Tích hợp theo thời gian 8 FEM Finite Element Method Phương pháp phần tử hữu hạn 9 FDM Finite Difference Method Phương pháp sai phân hữu hạn 10 FVM Finite Volume Method Phương pháp thể tích hữu hạn DANH MỤC CÁC HÌNH VẼ STT Hình Tên Trang 1 Hình 2.1 Mô hình lập trình song song SPMD 6 2 Hình 2.2 Các MPI_COMM_WORLD 18 3 Hình 3.1 Gradient nồng độ.
- 21 4 Hình 3.2 Khối thể tích nhỏ dxdydz 22 5 Hình 3.3 Chia miền tính toán thành một lưới điểm 24 6 Hình 3.4 Các điểm lân cận 27 7 Hình 3.5 Điều kiện biên 28 8 Hình 4.1 Chia miền tính toán 32 9 Hình 4.2 Gửi dữ liệu đầu vào từ Root đến các CPU 33 10 Hình 4.3 Truyền thông 34 11 Hình 4.3.1 Truyền thông Cu 36 12 Hình 4.3.2 Truyền thông Cd 38 13 Hình 4.4 Gửi kết quả tính toán về Root 39 DANH MỤC CÁC BẢNG STT Bảng Tên Trang 1 Bảng 1 Các kiểu dữ liệu MPI 11 2 Bảng 2 Các hàm tính toán của MPI 12 3 Bảng 3 Các hàm phổ biến của MPI 13 4 Bảng 4 Thông số cơ bản của máy tính trạm T7610 40 5 Bảng 5 Thời gian chạy chương trình C và MPI (ms) 41 6 Bảng 6 Thời gian chạy chương trình MPI với NP khác nhau 42 LỜI NÓI ĐẦU Trong thực tế có rất nhiều bài toán có mô hình toán học là các hệ phương trình đạo hàm riêng có khối lượng tính toán rất lớn như các bài toán dự báo thời tiết, dự báo bão, dự báo lũ lụt sóng thần.
- bài toán mô phỏng các hệ sinh thái biển.
- bài toán mô hình phát triển vi sinh vật.
- bài toán mô phỏng khí động lực học.
- Thông thường các bài toán có khối lượng tính toán lớn trên được xử lý song song trên các (hệ thống) máy tính có khả năng tính toán cao như các siêu máy tính, cluster, grid.
- Các hệ thống này thường bao gồm nhiều bộ vi xử lý (CPU) kết nối với nhau theo một cấu hình nhất định, sử dụng các công cụ (phần mềm) quản lý giao tiếp phù hợp.
- Chính vì vậy, trong luận văn này tôi sẽ nghiên cứu và trình bày thuật toán song song giải bài toán có mô hình toán học là phương trình đạo hàm riêng bằng phương pháp số trên nền tảng siêu máy tính, cluster, hoặc grid.Bài toán cụ thể được trình bày là bài toán phương trình truyền nhiệt.
- Luận văn được hoàn thành dưới sự hướng dẫn của thầy giáo TS.
- Em xin được bày tỏ lòng cảm ơn chân thành nhất tới Thầy đã nhiệt tình giúp đỡ và hướng dẫn em trong suốt quá trình để hoàn thành luận văn.
- Hà nội, tháng 04 năm 2015 Học viên Phùng Thị Hoàng Hoc viên: Phùng Thị Hoàng 1 Luận văn thạc sĩ Chƣơng 1: Mở đầu Hệ phương trình đạo hàm riêng (PDEs: Partial Differential Equations) được sử dụng trong nhiều lĩnh vực khoa học và kỹ thuật khác nhau.
- Ví dụ,hệ phương trình PDEs thường xuất hiện trong các mô hình toán học mô phỏng các hiện tượng trong các lĩnh vực như khí tượng thủy văn, môi trường, sinh học, hóa học, khí động lực học, hay trong ngành khoa học vật liệu, vật lý.
- Có rất nhiều bài toán trong thực tế có mô hình toán học là các hệ phương trình đạo hàm riêng có khối lượng tính toán rất lớn và/hoặc yêu cầu được xử lý trong một khoảng thời gian nhất định.
- Ví dụ như các bài toán dự báo thời tiết, dự báo báo, dự báo lũ lụt sóng thần.
- Mặc dù các nguyên lý cơ bản của tính toán song song rất rõ ràng, nhưng việc xây dựng các chương trình xử lý song song thường phức tạp và tốn nhiều thời gian, đặc biệt là các chương trình song song giải các bài toán phức tạp.
- Rất khó có thể tìm được nghiệm chính xác của các hệ phương trình đạo hàm riêng PDEs.Thông thường người ta sẽ dùng phương pháp số (Numerical Method) để giải các hệ phương trình PDEs.Theo cách này, miền tính toán của bài toán (Domain) được chia thành một lưới điểm.
- Các hàm, đạo hàm.
- được tính toán một cách rời rạc tại từng điểm lưới.
- Để tính đạo hàm ta có thể dùng một số phương pháp như sai phân thuận, sai phân ngược, sai phân trung tâm,… Các phương pháp này yêu cầu thông tin Hoc viên: Phùng Thị Hoàng 2 Luận văn thạc sĩ (dữ liệu) bổ sung từ các điểm lưới xung quanh để tính toán đạo hàm tại một điểm lưới.
- Người ta gọi vấn đề này là sự phụ thuộc dữ liệu trong tính toán.
- Trongmột chương trình tuần tự thực hiện trên một CPU, tất cả dữ liệu được lưu trong cùng một bộ nhớ nên chúng ta không cần quan tâm đến vấn đề phụ thuộc dữ liệu.
- Trên hệ thống máy tính song song có bộ nhớ phân tán, mỗi CPU có một bộ nhớ riêng.CPU này không thể truy cập dữ liệu trên bộ nhớ của CPU khác.
- Trong một chương trình song song SPMD (Single Program Multiple Data) hay còn gọi là mô hình lập trình song song Domain decomposition (Phân chia miền tính toán), miền tính toán của bài toán (domain) được chia thành các miền con (subdomain).
- Do các CPU không thể truy cập bộ nhớ của nhau, nên nếu có sự phụ thuộc dữ liệu trong tính toán thì cần phải truyền thông giữa các CPU.
- Cụ thể hơn, nếu việc tính toán trên CPU A cần dữ liệu lưu trữ trong bộ nhớ riêng của CPU B, CPU B sẽ gửi và CPU A sẽ nhận dữ liệu này.
- Tiến trình đó gọi là truyền thông.
- Việc cài đặt một chương trình song song có sự phụ thuộc dữ liệu rất phức tạp, bởi vì, trước hết chúng ta phải xác định được dữ liệu phụ thuộc (hay dữ liệu cần truyền thông), lưu dữ liệu cần truyền thông vào các biến, sau đó thiết kế một giải thuật truyền thông phù hợp, cuối cùng sử dụng dữ liệu thu được một cách chính xác.
- Chính vì vậy, trong luận văn này tôi sẽ nghiên cứu và trình bày thuật toán song song giải bài toán có mô hình toán học là phương trình đạo hàm riêng bằng phương pháp số trên nền tảng siêu máy tính, cluster, hoặc grid.Trước tiên tôi tìm hiểu các phương pháp số giải hệ phương trình đạo hàm riêng, sau đó sẽ đi sâu nghiên cứu và đưa ra giải pháp để xây dựng các chương trình tính toán song song cho bài toán trên.Cuối cùng tôi sẽ áp dụng xây dựng chương trình song song cho một bài toán cụ thể như bài toán phương trình truyền nhiệt.Các chương trình song song này sẽ được chạy thử nghiệm trên máy tính trạm có nhiều CPU.
- Hoc viên: Phùng Thị Hoàng 3 Luận văn thạc sĩ Luận văn bao gồm các chương chính sau: Chƣơng 2:Tìm hiểu cơ sở lý thuyết về các phương pháp số giải hệ phương trình PDEs,tìm hiểu mô hình tính toán song song SPMD và thư viện lập trình song song MPI.
- Chƣơng 3: Tìm hiểu bài toán phương trình Heat Equations (Phương trình truyền nhiệt.
- Chƣơng 4:Phân tích sự phụ thuộc dữ liệu, thiết kế giải thuật truyền thông, cài đặt chương trình song song.
- Chƣơng 5: Chạy thử nghiệm chương trình,phân tích kết quả, đánh giá hiệu quả của chương trình song song.
- Hoc viên: Phùng Thị Hoàng 4 Luận văn thạc sĩ Chƣơng 2: Cơ sở lý thuyết 2.1.
- Phƣơng pháp số giải hệ phƣơng trình PDEs Nói chung, rất khó tìm được nghiệm chính xác của các hệ phương trình đạo hàm riêng PDEs.
- Vì vậy, thông thường người ta sử dụng phương pháp số(Numerical Method) để giải các hệ phương trình PDEs.
- Ngày nay có nhiều phương pháp số để giải các hệ PDEs, ví dụ như phương phápDST(Direct Space-Time) hay phương pháp MOL (Method Of Line).
- Theo phương pháp MOL, hai bước rời rạc theo không gian và tích hợp theo thời gian được thực hiện riêng, trong khi đối với phương pháp DST, hai bước này được thực hiện đồng thời.
- Phương pháp MOL có ưu điểm là đơn giản và linh hoạt hơn so với phương pháp DST, do đó trong luận văn này tôi sẽ chọn MOL là phương pháp số giải các hệ PDEs.
- Phương pháp MOL giải các hệ PDEs bao gồm hai bước: 1) Rời rạc hóa theo không gian (Spatial discretization) 2) Tích hợp theo thời gian (Time integration) Có nhiều cách để rời rạc hóa hệ phương trình PDEs trong không gian, ví dụ, phương pháp phần tử hữu hạn (FEM: Finite Element Method), phương pháp sai phân hữu hạn (FDM: Finite Difference Method), và phương pháp thể tích hữu hạn (FVM: Finite Volume Method).
- Trong luận văn này tôi sẽ sử dụng phương pháp sai phân hữu hạn FDM.
- Trong phương pháp sai phân hữu hạn FDM, miền tính toán của bài toán (Domain) được chia thành một lưới điểm hình chữ nhật.Đạo hàm của các biến trong không gian thay vì được tính liên tục, sẽ được tính một cách rời rạc tại từng điểm lưới Hoc viên: Phùng Thị Hoàng 5 Luận văn thạc sĩ này.Có nhiều phương pháp số để tính đạo hàm trong không gian, trong luận văn này tôi sẽ sử dụng các phương pháp như sai phân thuận hoặc sai phân trung tâm.
- Sau khi rời rạc hóa hệ phương trình PDEs trong không gian, ta sẽ thu được một hệ phương trình vi phân thường (ODEs: Ordinary Differential Equations) có dạng như sau.
- Trong đó : ω là các biến của hệ phương trình PDEs, F là hàm thu được từ bước rời rạc hóa theo không gian, t là biến thời gian.
- Có nhiều phương pháp để giải hệ phương trình vi phân thường ODEs, trong luận văn này chúng tôi sẽ sử dụng phương pháp Euler thuận (Forward Euler).
- Phương pháp Euler thuận giải phương trình vi phân thường ODEs có công thức như sau.
- Trong đó : n là bước tính toán thứ n, ht là độ dài bước thời gian.
- Công thức Euler thuận có thể được tính toán lặp như sau.
- Hoc viên: Phùng Thị Hoàng 6 Luận văn thạc sĩ.
- Mô hình lập trình song song SPMD Hiện có rất nhiều mô hình lập trình song song.Tuy nhiên, mô hình lập trình song song SPMD (Single Program Multiple Data) là phổ biến nhất vì nó phù hợp với các hệ thống tính toán có bộ nhớ phân tán và các bài toán có dữ liệu phân tán.
- Do đó, trong luận văn này tôi sẽ chọn SPMD làm mô hình tính toán song song.
- Trong mô hình SPMD, miền tính toán của bài toán (Domain) được chia thành các miền con (Subdomain), các miền con được tính toán bởi cùng một chương trình trên các bộ xử lý (Process) khác nhau.
- Mô hình lập trình song song SPMD được mô tả như Hình 2.1.
- Hình 2.1: Mô hình lập trình song song SPMD Domain decomposition & Distribute data Compute & Exchange Compute & Exchange Compute & Exchange Collect results Hoc viên: Phùng Thị Hoàng 7 Luận văn thạc sĩ Một chương trình song song sử dụng mô hình SPMD bao gồm các bước chính sau.
- Phân chia miền tính toán (Domain decomposition.
- Phân tán dữ liệu đầu vào (Data distribution.
- Truyền thông dữ liệu (Communication.
- Tính toán (Computation.
- Tập hợp dữ liệu đầu ra (Result collection) 2.3.
- Thƣ viện MPI MPI là viết tắt của các chữ Message Passing Interface.
- MPI là bộ thư viện hỗ trợ việc lập trình song song với các ngôn ngữ như C, Fortran.
- Tập MPI thi hành bao gồm một thư viện các thủ tục sao cho có thể gọi được từ các chương trình Fortran, C, C++ hay Ada.
- 2.3.1 MPI tiêu chuẩn MPI tiêu chuẩn hỗ trợ cho nhiều ngôn ngữ lập trình như C, C.
- Giảm thời gian viết chương trình.
- Hoc viên: Phùng Thị Hoàng 8 Luận văn thạc sĩ Mục tiêu chính của các đặc điểm này của MPI là để cho phép người dùng không cần phải băn khoăn về hiệu quả, tính năng linh hoạt, và chức năng của chương trình.
- Điều này có nghĩa rằng người ta có thể viết các chương trình chạy linh hoạt trên nhiều hệ thống mà vẫn có thể tận dụng lợi thế của các phần cứng chuyên dụng và phần mềm được cung cấp bởi các nhà cung cấp cá nhân.
- Đồng thời, các tính năng tiên tiến, chẳng hạn như tập rộng lớn của các hoạt động tập thể, có thể được dự kiến trong mỗi MPI và có thể được sử dụng trong tất cả các chương trình ứng dụng song song nơi mà họ có thể có ích.
- MPI không phải là một cuộc cách mạng mới của máy tính lập trình song song, đúng hơn, nó là một nỗ lực để thu thập các tính năng tốt nhất của nhiều hệ thống đi qua hiện có, cải thiện chúng ở nơi thích hợp, và chuẩn hóa chúng.
- 2.3.2 Các khái niệm cơ bản của MPI Các khái niệm cơ bản của các MPItiêu chuẩn là tiến trình và các truyền thông.
- Trong khi truyền thông kiểu điểm – điểm (point-to point) và kiểu tập hợp (Collective) là trung tâm của MPI, nhóm tiến trình, gói dữ liệu,các kiểu dữ liệu, và topo ảo là những khái niệm quan trọng khác của MPItiêu chuẩn.
- 2.3.2.1 Gói dữ liệu và các tiến trình Một tiến trình MPI là một thực thể tham gia vào thực hiện một số nhiệm vụ tính toán.Trong mô hình lập trình cơ bản MPI, mỗi tiến trình được liên kết với một bộ nhớ duy nhất, được gọi là bộ nhớ cục bộ của nó, mà nó chỉ có thể truy cập và cập nhật trực tiếp.
- Một gói dữ liệubao gồm một phần nội dung thông tin, cùng với một số dữ liệu bổ sung được gọi là một nhãn.
- Nhãn của một gói tin chỉ rõ để người nhận tiến trình có thể đọc nội dung thông tin của các tin nhắn vào bộ nhớ địa phương của mình.
- Nhãn chứa thêm thông tin có thể được sử dụng bởi các tiến trình nhận để quyết định hay không và

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt