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 mas