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_GET_THREAD_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