Luận Văn Nguyên cứu chi tiết chuẩn OpenMP và ứng dụng của OpenMP vào việc song song hóa bài toán tính lực tươ

Tóm tắt nội dung

Ngày nay tính toán song song ra đời với sự thực thi đồng thời của nhiều tài
nguyên máy tính giúp giải quyết các bài toán đòi hỏi giới hạn về thời gian xử lý và
với dữ liệu lớn như bài toán dự báo thời tiết, bài toán mô phỏng tai nạn giao thông .
Và đã có rất nhiều chuẩn hỗ trợ cho cho việc lập trình song song như MPI (Message
Passing Interface) hỗ trợ lập trình song song trên mô hình bộ nhớ phân tán, OpenMP
(Open MultiProcesing) hỗ trợ lập trình song song trên mô hình chia sẻ bộ nhớ chung,
Pthread hỗ trợ lập trình luồng .
Trong khuôn khổ của khóa luận văn này chúng tôi đi vào nguyên cứu chi
tiết chuẩn OpenMP và ứng dụng của OpenMP vào việc song song hóa bài toán tính
lực tương tác giữa các hạt trong hệ mô phỏng N-body.



MỤC LỤC

MỞ ĐẦU 1
Chương 1 Tổng quan về tính toán song song . 3
1.1 Tính toán song song 3
1.1.1.Tính toán song song là gì .3
1.1.2 Tại sao phải tính toán song song .3
1.2 Phân loại máy tính song song .4
1.2.1 Phân loại dựa trên sự tương tác giữa các BXL 4
a.Chia sẻ bộ nhớ chung .4
b. Bộ nhớ phân tán 6
c.Máy tính với bộ nhớ lai .6
1.2.2 Phân loại dựa trên cơ chế điều khiển chung 7
a.Hệ thống đa xử lý một lệnh nhiều dữ liệu (SIMD) 7
b.Hệ thống đa xử lý nhiều dòng lệnh nhiều dòng dữ liệu (MIMD) .8
1.3 Các mô hình lập trình song song 8
1.3.1 Tổng quan về mô hình lập trình song song .8
1.3.2 Mô hình chia sẻ bộ nhớ chung .9
1.3.3. Mô hình luồng 9
1.3.4 Mô hình truyền thông điệp 10
1.3.5. Mô hình song song dữ liệu .11
1.3.6. Mô hình lai .11
1.4 Hiệu năng của tính toán song song .12
1.4.1 Định luật Amdahl’s .12
1.4.2 Cân bằng tải .13
a.Các thuật toán cân bằng tải tập trung .13
b.Các thuật toán cân bằng tải phân tán hoàn toàn 14
c.Các thuật toán cân bằng tải phân tán một nửa .14
d. Sự bế tắc(Deadlock) .14
Chương 2: Lập trình song song với OpenMP 16
2.1 Giới thiệu về OpenMP 16
2.1.1 Khái niệm cơ bản về OpenMP 16
2.1.2 Lịch sử của OpenMP .16
2.1.3 Mục đích và ứng dụng của OpenMP .17
2.2 Mô hình lập trình song song OpenMP .17
2.2.1 Song song hóa dựa trên cơ chế luồng (Thread based parallelism) 17
2.2.2 Mô hình song song hiện (Explicit Parallelism) .17
2.2.3 Mô hình Fork-Join .17
2.3 Các chỉ thị trong OpenMP 18
2.3.1 Khuôn dạng chỉ thị trong OpenMP 18
2.3.2 Phạm vi của chỉ thị 18
2.3.3 Cấu trúc vùng song song .20
2.3.4 Cấu trúc chia sẻ công việc .21
2.3.5. Cấu trúc đồng bộ 28
2.3.5.1 Chỉ thị MASTER 29
2.3.5.3 Chỉ thị BARRIER .30
2.3.5.4 Chỉ thị ATOMIC 31
2.3.5.5 Chỉ thị FLUSH .31
2.3.5.6 Chỉ thị ORDERED .32
2.3.6 Chỉ thị THREADPRIVATE 32
2.3. Các mệnh đề trong OpenMP .33
2.4.1 Mệnh đề PRIVATE .33
2.4.2 Mệnh đề FIRSTPRIVATE 33
2.4.3 Mệnh đề LASTPRIVATE .34
2.3.4 Mệnh đề SHARED 34
2.3.5 Mệnh đề DEFAULT 34
2.3.6 Mệnh đề REDUCTION .34
2.3.7 Mệnh đề COPYIN .35
2.5. Thư viện Run-Time .35
2.5.1 OMP_SET_NUM_THREADS 36
2.5.2. OMP_GET_NUM_THREADS 36
2.5.3. OMP_GET_MAX_THREADS .36
2.5.4. OMP_GEHREAD_NUM .36
2.5.4. OMP_GET_NUM_PROCS 36
2.5.5. OMP_IN_PARALLEL .37
2.5.7. OMP_SET_DYNAMIC .37
2.5.8. OMP_GET_DYNAMIC .37
2.5.9. OMP_SET_NESTED 37
2.5.10. OMP_GET_NESTED 37
2.5.11. OMP_INIT_LOCK .38
2.5.12. OMP_DESTROY_LOCK 38
2.5.13. OMP_SET_LOCK 38
2.5.14. OMP_UNSET_LOCK 38
2.5.15. OMP_TEST_LOCK 38
2.6. Các biến môi trường trong OpenMP .39
2.6.1. OMP_SCHEDULE .39
2.6.2. OMP_NUM_THREADS 39
2.6.3. OMP_DYNAMIC 39
2.6.3. OMP_NESTED 39
2.7. Trình biên dịch OpenMP .39
Chương 3: Bài toán mô phỏng N-Body .40
1.1. Giới thiệu chung về bài toán mô phỏng N-body .40
1.2. Mô tả bài toán N-body .41
1.3. Các bước trong quy trình giải bài toán mô phỏng N-body 42
1.4. Kết quả thực nghiệm 47
1.4.1. Đánh giá, nhận xét .49
KẾT LUẬN 49
HƯỚNG PHÁT TRIỂN TRONG TƯƠNG LAI 50
Bảng các chữ viết tắt

Chữ viết tắt Tiếng Việt Tiếng Anh
API Giao diện
lập trình ứng
dụng
Application Program Interface
BXL Bộ xử lý
MIMD Đa lệnh đa
dữ liệu
Multiple instruction multiple data
MPI Giao diện
truyền thông
điệp
Message Passing Interface
OPENMP Open MultiProcessing
SIMD Đơn lệnh đa
dữ liệu
Single instruction multiple data
SMP Đa xử lý đối
xứng
Symmetric MultiProcesor
UMA Truy cập bộ
nhớ một
cách thống
nhất
Uniform Access Memory


Mở đầu

Ngày nay sự phát triển của công nghệ được thách thức bởi lớp bài toán lớn cần
giải quyết trong nhiều lĩnh vực của đời sống xã hội như dự báo thời tiết, khai phá dữ
liệu, xử lý ảnh, mô phỏng tai nạn xe hơi, tự động hóa . Lớp bài toán này vừa đòi hỏi
đáp ứng thời gian thực vừa yêu cầu xử lý trên khối dữ liệu lớn. Để giải quyết bài toán
này đòi hỏi các bộ xử lý có hiệu năng cao.
Xử lý song song ra đời với mục đích làm tăng khả năng tính toán của máy tính
bằng cách kết hợp nhiều bộ xử lý tham gia đồng thời vào quá trình xử lý thay với việc
sử dụng các máy tính chuyên biệt đắt tiền.
Với sự phát triển cua kiến trúc máy tính và mạng máy tính cho thấy rằng trong
tương lai cho thấy xử lý song song không những được thực hiện trên những siêu máy
tính mà có thể được thực hiện trên các trạm làm việc, máy tính cá nhân, mạng máy
tính. Nhưng hầu hết các thuật toán ngày nay đều là những thuật toán tuần tự. Cho nên
cần xây dựng những thuật toán, cấu trúc dữ liệu cho phép xử lý một cách song song.
Xử lý song song giúp giải quyết hiệu quả rất nhiều bài toán lớn đặc biệt là bài
toán mô phỏng N-body. Đó là một bài toán mô phỏng chuyển động của các body trong
hệ mô phỏng N-body do lực tương tác giữa giữa các body.Việc song song hóa bài toán
trên là rất hợp lý vì một hệ N-body có rất nhiều các body nên việc tính lực tương tác
giữa các body tốn rất nhiều thời gian.
Trong khuôn khổ của khóa luận. Áp dụng xử lý song song vào việc giảm thời
gian tính lực tương tác giữa các body trong hệ mô phỏng N-body. Luận văn gồm ba
chương.
Chương 1: Là chương giới thiệu tổng quan về lập tính toán song song. Chương
này đề cập đến các vấn đề như các kiến trúc của máy tính song song, các mô hình lập
trình song song, và các vấn đề liên quan đến hiệu năng của lập trình song song như
định luật amdahl’s, bế tắc và cân bằng tải.
Chương 2: Là chương giới thiệu về OpenMP. Chương này tập trung nghiên
cứu chi tiết các thành phần củac OpenMP. Bao gồm các chỉ thị biên dịch, các hàm thư
viện và các biến môi trường.
Chương 3: Là chương mô tả và cài đặt bài toán N-body. Chương này mô tả sơ
qua bài toán N-body. Thuật toán tính lực tương tác lên các body trong hệ, và ba cách
song song hóa giai đoạn tính lực tương tác giữa các body.
Kết luận: Nêu lên những vấn đề, kết quả đã đạt được. Chỉ ra sự khác biết giữa
các chiến lược song song và hướng phát triển trong tương lai.