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