Đề tài Song song hóa thuật toán Barnes - Hut với OpenMP

TÓM TẮT KHÓA LUẬN Song song hóa là một giải pháp quan trọng được áp dụng khi giải quyết các vấn đề đòi hỏi phải tính toán lớn thường gặp trong các lĩnh vực khoa học cơ bản Bài toán N- body là một trong những bài toán cơ bản trong lĩnh vực vật lý học thiên thể, liên quan tới lực tương tác giữa các hạt với nhau trong không gian. Có rất nhiều hướng để giải quyết bài toán trên, trong đó có phương pháp sử dụng thuật toán Barnes-Hut. OpenMP là giao diện lập trình ứng dụng API, cung cấp cho người lập trình một giao diện mềm dẻo, có tính khả chuyển trong khi phát triển các ứng dụng song song trên các máy tính sử dụng kiến trúc bộ nhớ chia sẻ. Khóa luận này giới thiệu tổng quan về bài toán N-body, thuật toán Barnes-Hut và giao diện lập trình ứng dụng OpenMP. Trên cơ sở đó đánh giá hiệu năng thuật toán Barnes-Hut, tiến hành tìm hiểu, phân tích và đề xuất các phương thức song song hóa thuật toán Barnes-Hut với OpenMP. LỜI CẢM ƠN Đầu tiên, em muốn gửi lời cảm ơn sâu sắc nhất tới TS. Nguyễn Hải Châu, người đã hướng dẫn và chỉ bảo em tận tình trong suốt thời gian làm khóa luận. Em xin chân thành cảm ơn thầy Phạm Kỳ Anh, giám đốc Trung tâm Tính toán hiệu năng cao – Trường Đại học KHTN – Đại học Quốc gia Hà Nội, người đã tạo điều kiện tốt nhất cho em thực hành và thử nghiệm thuật toán. Em cũng xin gửi lời cảm ơn tới tất cả các thầy và các anh chị trong Trung tâm, những người đã giúp đỡ và trả lời mọi thắc mắc, tạo điều kiện cho em hoàn thành khóa luận. Em xin cảm ơn thầy Đoàn Minh Phương, giảng viên bộ môn Mạng và Truyền thông máy tính, khoa CNTT, trường Đại học Công nghệ, người đã giúp đỡ em thử nghiệm bài toán trên máy đa xử lý Intel. Cuối cùng, em xin gửi lời cảm ơn sâu sắc tới những người thân trong gia đình em, những người luôn quan tâm, động viên khích lệ em trong học tập và trong cuộc sống. Sinh viên thực hiện khóa luận Lê Thị Lan Phương Mục lục TÓM TẮT KHÓA LUẬN . i LỜI CẢM ƠN . ii Danh sách hình vẽ iii Bảng từ viết tắt . iv Mục lục v MỞ ĐẦU 1 Chương 1: BÀI TOÁN N-BODY VÀ THUẬT TOÁN BARNES-HUT 2 1.1 Bài toán N-body 2 1.1.1 Giới thiệu bài toán N-body 2 1.1.2 Phương pháp nhằm tăng tốc bài toán N-body . 5 1.1.3 Cấu trúc cây Quadtree và Octree . 7 1.2 Thuật toán Barnes-Hut 9 1.2.1 Mô tả thuật toán Barnes-Hut . 10 Chương 2: GIỚI THIỆU VỀ OPENMP . 15 2.1 OpenMP (Open specifications for Multi Processing) . 15 2.2 Kiến trúc bộ nhớ chia sẻ 16 2.3 Mục tiêu của OpenMP . 17 2.4 Môi trường hỗ trợ OpenMP . 18 2.5 Mô hình lập trình OpenMP . 18 2.6 Một số chỉ thị cơ bản trong OpenMP 19 2.6.1 Các chỉ thị song song hóa 20 2.6.2 Chỉ thị khai báo miền song song . 20 2.6.3 Chỉ thị liên quan tới môi trường dữ liệu 21 2.6.4 Chỉ thị liên quan tới chia sẻ công việc 23 2.6.5 Chỉ thị đồng bộ hóa . 28 2.6.6 Thư viện và một số biến môi trường . 31 2.7 Ví dụ về lập trình song song với OpenMP 33 2.7.1 omp_hello.c . 33 2.7.2 Cách biên dịch . 33 2.7.3 Kết quả 34 Chương 3: SONG SONG HÓA THUẬT TOÁN BARNES-HUT 35 3.1 Treecode 35 3.1.1 Cấu trúc dữ liệu của cây 35 3.1.2 Các biến toàn cục 39 3.2 Thử nghiệm và đánh giá hiệu năng của treecode 40 3.2.1 Thử nghiệm chương trình treecode . 40 3.2.2 Đánh giá hiệu năng 42 3.3 Song song hóa treecode với OpenMP . 43 3.3.1 Môi trường thực hiện song song . 43 3.3.2 Thực hiện song song 44 3.4 Kết quả thực nghiệm . 51 KẾT LUẬN . 53 TÀI LIỆU THAM KHẢO 54 Danh sách hình vẽ Hình 1: Minh họa hệ N-body trong không gian 2 Hình 2: Biểu diễn lực tổng hợp tác dụng lên 1 hạt 4 Hình 3: Quan sát thiên hà Andromeda từ trái đất 6 Hình 4: Biểu diễn quá trình đệ quy thay thế một cụm bởi tâm điểm 7 Hình 5: Cây Quadtree với 4 mức 8 Hình 6: Cây Octree với 2 mức .8 Hình 7: Biểu diễn cây sau khi loại bỏ các ô trống .9 Hình 8: Các thành phần trong OpenMP 15 Hình 9: Kiến trúc bộ nhớ chia sẻ 16 Hình 10: Mô hình Fork-Join .19 Hình 11: Minh họa vùng được song song hóa 21 Hình 12: Hình minh họa chỉ thị Do/for 24 Hình 13: Hình minh họa chỉ thị sections 26 Hình 14: Hình minh họa chỉ thị single 28 Hình 15: Cấu trúc dữ liệu cây trong treecode (1) 36 Hình 16: Cấu trúc dữ liệu cây trong treecode (2) 39 Bảng từ viết tắt Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh Giao diện lập trình ứng dụng API Application Program Interface Các chỉ thị mở dành cho đa xử lý OpenMP Open Specifications for Multi Processing Luồng Thread Thread Hạt body Body Ô, Khối cell Cell Nút node Node Giao diện truyền thông điệp MPI Message Passing Interface Tâm khối Center of mass

TÀI LIỆU LUẬN VĂN CÙNG DANH MỤC

TIN KHUYẾN MÃI

  • Thư viện tài liệu Phong Phú

    Hỗ trợ download nhiều Website

  • Nạp thẻ & Download nhanh

    Hỗ trợ nạp thẻ qua Momo & Zalo Pay

  • Nhận nhiều khuyến mãi

    Khi đăng ký & nạp thẻ ngay Hôm Nay

NẠP THẺ NGAY