Mở đầu

Ngày nay với sự phát triển của công nghệ thông tin, các máy tính đa nhân, đa lõi (multiple processor) đang dần dần thay thế cho bộ xử lý đơn lõi

(single processor) vì các lý do khác nhau như:

Tốc độ của bộ xử lý đơn lõi (single processor) đã đến giới hạn.

Đáp ứng nhu cầu tính toán nhanh của người dùng.

Giải quyết các bài toán lớn mà với bộ xử lý đơn lõi không đáp ứng được.

Giảm chi phí đầu tư nhưng vẫn đạt hiệu quả trong tính toán.

Tuy nhiên với lối lập trình truyền thống là lập trình tuần tự thì hầu hết các chương trình ứng dụng đều được lập trình, thiết kế trên bộ xử lý đơn lõi

(single processor). Như vậy sẽ không khai thác hết hiệu năng tính toán mà bộ xử lý đa nhân, đa lõi mang lại đồng thời khó đáp ứng được yêu cầu tính toán của người dùng.

Một thách thức, một yêu cầu đặt ra là làm thế nào để khai thác được hiệu năng tính toán mà bộ xử lý đa nhân, đa lõi mang lại. Không còn cách nào khác là thay vì lập trình, tính toán tuần tự chuyển sang lập trình, tính toán song song.

Lập trình, tính toán song song ra đời nhằm khai thác, phát huy hiệu năng tính toán của bộ xử lý đa lõi, đồng thời giảm thời gian tính toán của các bài toán có khối lượng dữ liệu lớn.

Các công cụ hỗ trợ lập trình, tính toán song song có thể kể đến như: Thư viện MPI (Message Passing Interface), PMV (Parallel Virtual Machine), một số được tích hợp sẵn thành chuẩn trong các ngôn ngữ lập trình như thư viện OpenMP (Open Multiple Processing) trong C/C++, FOTRAN. Trong khuôn khổ bài khoá luận em sẽ đi tìm hiểu, áp dụng lập trình, tính toán song song, trên cơ sở sử dụng thư viện OpenMP trong việc giảm thời gian tính toán của bài toán tìm số nguyên tố có số chữ số lớn. Nội dung của bài khoá luận bao gồm:

Chương 1: Tìm hiểu lập trình song song, tính toán song song.

Chương này giới thiệu một cách tổng quan về lập trình và tính toán song song như sự phân chia cấu trúc tính toán song song, các mô hình lập trình tính toán song song.

Chương 2: Giới thiệu về thư viện mã nguồn mở OpenMP.

Chương này sẽ đi sâu, nghiên cứu cấu trúc, các thành phần của thư viện mã nguồn mở OpenMP như các chỉ thị biên dịch, các hàm thư viện runtime và các biến môi trường.

Chương 3: Phát biểu, mô tả và cài đặt thực nghiệm bài toán tính giai thừa và bài toán tìm số nguyên tố có số chữ số lớn.

Chương này sẽ đi vào mô tả, phân tích và cài đặt bài toán tính giai thừa của một số nguyên lớn và bài toán tìm số nguyên tố có số chữ số lớn theo cả hai hướng tuần tự và song song. Từ đó đưa ra sự so sánh, đối chiếu về mặt thời gian của hai bài toán theo hai hướng thực hiện.

Kết luận: Nêu lên những vấn đề đã nghiên cứu và kết quả đạt được, những hạn chế, thiếu sót và phương hướng phát triển trong tương

Mục lục

[URL="/#_Toc234217841"]Lời cảm ơn. 1

[URL="/#_Toc234217842"]Mục lục. 2

[URL="/#_Toc234217843"]Mở đầu. 5

[URL="/#_Toc234217844"]CHƯƠNG 1: Tổng quan về lập trình song song, tính toán song song. 7

[URL="/#_Toc234217845"]1.1 Định nghĩa: 7

[URL="/#_Toc234217846"]1.1.1 Thế nào là lập trình, tính toán song song ?. 7

[URL="/#_Toc234217847"]1.1.2 Tại sao phải lập trình, tính toán song song ?. 7

[URL="/#_Toc234217848"]1.1.3 Sử dụng lập trình, tính toán song song để làm gì ?. 7

[URL="/#_Toc234217849"]1.1.4 So sánh lập trình tính toán tuần tự và lập trình tính toán song song. 8

[URL="/#_Toc234217850"]1.2 Sự phân chia cấu trúc tính toán song song. 9

[URL="/#_Toc234217851"]1.2.1 Phân chia dựa trên quan hệ giữa chỉ thị lệnh và dữ liệu. 9

[URL="/#_Toc234217852"]1.2.2 Sự phân chia dựa trên mối quan hệ giữa bộ xử lý và bộ nhớ. 12

[URL="/#_Toc234217853"]1.3 Các mô hình lập trình song song. 16

[URL="/#_Toc234217854"]1.3.1 Mô hình dùng chung bộ nhớ (Shared Memory). 17

[URL="/#_Toc234217855"]1.3.2 Mô hình luồng (Thread). 17

[URL="/#_Toc234217856"]1.3.3 Mô hình truyền thông điệp (Message Passing). 18

[URL="/#_Toc234217857"]1.3.4 Mô hình song song dữ liệu (Data Parallel). 19

[URL="/#_Toc234217858"]1.4 Một số vấn đề liên quan đến lập trình và tính toán song song. 20

[URL="/#_Toc234217859"]1.4.1 Định luật Amdahl’s. 20

[URL="/#_Toc234217860"]1.4.2 Cân bằng tải. 21

[URL="/#_Toc234217861"]1.4.3 Sự bế tắc. 22

[URL="/#_Toc234217862"]CHƯƠNG 2: Thư viện Mã nguồn mở OpenMP. 24

[URL="/#_Toc234217863"]2.1 Tổng quan về OpenMP. 24

[URL="/#_Toc234217864"]2.1.1 Giới thiệu. 24

[URL="/#_Toc234217865"]2.1.2 Định nghĩa. 24

[URL="/#_Toc234217866"]2.1.3 Lịch sử phát triển. 24

[URL="/#_Toc234217867"]2.1.4 Mục đích của OpenMP. 25

[URL="/#_Toc234217868"]2.2 Mô hình lập trình song song trong OpenMP. 25

[URL="/#_Toc234217869"]2.3 Các chỉ thị biên dịch (Compiler Directive). 26

[URL="/#_Toc234217870"]2.3.1 Khuôn dạng của chỉ thị. 26

[URL="/#_Toc234217871"]2.3.2 Phạm vi của chỉ thị. 27

[URL="/#_Toc234217872"]2.3.3 Cấu trúc vùng song song. 28

[URL="/#_Toc234217873"]2.3.4 Cấu trúc chia sẻ công việc (Work Sharing Construct). 29

[URL="/#_Toc234217874"]2.3.5 Cấu trúc đồng bộ. 37

[URL="/#_Toc234217875"]2.3.6 Chỉ thị THREADPRIVATE 41

[URL="/#_Toc234217876"]2.4 Các mệnh đề trong OpenMP. 41

[URL="/#_Toc234217877"]2.4.1 Mệnh đề PRIVATE 41

[URL="/#_Toc234217878"]2.4.2 Mệnh đề FIRSTPRIVATE 42

[URL="/#_Toc234217879"]2.4.3 Mệnh đề LASTPRIVATE 42

[URL="/#_Toc234217880"]2.4.4 Mệnh đề SHARED 42

[URL="/#_Toc234217881"]2.4.5 Mệnh đề DEFAULT 42

[URL="/#_Toc234217882"]2.4.6 Mệnh đề REDUCTION 43

[URL="/#_Toc234217883"]2.4.7 Mệnh đề COPYIN 43

[URL="/#_Toc234217884"]2.5 Thư viện Runtime (Runtime Library Routine). 44

[URL="/#_Toc234217885"]2.5.1 OMP_SET_NUM_THREADS. 44

[URL="/#_Toc234217886"]2.5.2 OMP_GET_NUM_THREADS. 45

[URL="/#_Toc234217887"]2.5.3 OMP_GET_THREAD_NUM . 45

[URL="/#_Toc234217888"]2.5.4 OMP_GET_MAX_THREADS. 45

[URL="/#_Toc234217889"]2.5.5 OMP_GET_NUM_PROCS. 45

[URL="/#_Toc234217890"]2.5.6 OMP_IN_PARALLEL 45

[URL="/#_Toc234217891"]2.5.7 OMP_SET_DYNAMIC 46

[URL="/#_Toc234217892"]2.5.8 OMP_GET_DYNAMIC 46

[URL="/#_Toc234217893"]2.5.9 OMP_SET_NESTED 46

[URL="/#_Toc234217894"]2.5.10 OMP_GET_NESTED 47

[URL="/#_Toc234217895"]2.5.11 OMP_INIT_LOCK 47

[URL="/#_Toc234217896"]2.5.12 OMP_DESTROY_LOCK 47

[URL="/#_Toc234217897"]2.5.13 OMP_SET_LOCK 47

[URL="/#_Toc234217898"]2.5.14 OMP_UNSET_LOCK 47

[URL="/#_Toc234217899"]2.5.15 OMP_TEST_LOCK 48

[URL="/#_Toc234217900"]2.6 Các biến môi trường (Enviroment Variables). 48

[URL="/#_Toc234217901"]2.6.1 OMP_SCHEDULE 48

[URL="/#_Toc234217902"]2.6.2 OMP_NUM_THREADS. 48

[URL="/#_Toc234217903"]2.6.3 OMP_DYNAMIC 48

[URL="/#_Toc234217904"]2.6.4 OMP_NESTED. 49

[URL="/#_Toc234217905"]CHƯƠNG 3: Thực nghiệm 50

[URL="/#_Toc234217906"]3.1 Bài toán tính giai thừa của một số nguyên lớn. 50

[URL="/#_Toc234217907"]3.1.1 Phát biểu bài toán. 50

[URL="/#_Toc234217908"]3.1.2 Thuật toán thực hiện. 50

[URL="/#_Toc234217909"]3.1.3 Song song hoá thuật toán tính giai thừa của một số nguyên lớn. 51

[URL="/#_Toc234217910"]3.1.4 Thực hiện song song hoá bằng OpenMP. 53

[URL="/#_Toc234217911"]3.1.5 Kết quả thực nghiệm và nhận xét. 54

[URL="/#_Toc234217912"]3.2 Bài toán tìm số nguyên tố có n chữ số. 55

[URL="/#_Toc234217913"]3.2.1 Phát biểu bài toán. 55

[URL="/#_Toc234217914"]3.2.2 Thuật toán thực hiện. 55

[URL="/#_Toc234217915"]3.2.3 Song Song hoá thuật toán tìm số nguyên tố có n chữ số. 58

[URL="/#_Toc234217916"]3.2.4 Thực hiện song song hoá bằng OmpenMP. 60

[URL="/#_Toc234217917"]3.2.5 Kết quả thực nghiệm và nhận xét 62

[URL="/#_Toc234217918"]Kết luận. 64

[URL="/#_Toc234217919"]Tài liệu tham khảo. 6