Khóa luận Song song hóa thuật toán Barnes-Hut với OpenMP

đã có rất nhiều giải thuật nhằm song song hóa quá trình tính toán lực tác dụng trong hệ thống N-body. Có hai hướng để tiến hành song song hóa thuật toán. 1) Song song hóa với MPI - sử dụng bộ nhớ phân tán 2) Song song hóa với OpenMP - sử dụng bộ nhớ chia sẻ Trong khóa luận này, ta sẽ xem xét phương pháp song song hóa thuật toán Barnes-Hut với OpenMP. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 15 Chương 2: GIỚI THIỆU VỀ OPENMP 2.1 OpenMP (Open specifications for Multi Processing) Lập trình song song trên các máy với bộ nhớ chia sẻ đóng vai trò khá quan trọng trong tính toán hiệu năng cao. Tuy nhiên việc sử dụng những tiện ích của hệ thống bộ nhớ chia sẻ là không dễ dàng đối với người lập trình. Giao diện truyền thông điệp MPI phần lớn được sử dụng trong các hệ thống bộ nhớ phân tán. Khả năng mở rộng và tính khả chuyển trong MPI là rất tốt, nhưng nó lại không có ý nghĩa khi triển khai với những đoạn mã viết cho các máy tính tuần tự. Hơn nữa MPI lại không tận dụng được những tiện ích mà hệ thống bộ nhớ chia sẻ mang lại. Trong nhiều năm, có nhiều sản phẩm được giới thiệu nhằm đưa ra tính khả chuyển và hiệu năng cao trên những hệ thống cụ thể. Tuy nhiên vẫn phát sinh những vấn đề trong tính khả chuyển khi sử dụng các sản phẩm này. OpenMP được coi như một giao diện lập trình ứng dụng API (Application Program Interface) chuẩn dành cho lập trình với bộ nhớ chia sẻ. OpenMP là sự kết hợp của các chỉ thị biên dịch, các hàm thư viện, và các biến môi trường được sử dụng để xác định phần thực hiện song song trên bộ nhớ chia sẻ trong lập trình Fortran hoặc C/C++. OpenMP đưa ra một mô hình lập trình song song có tính khả chuyển đối với những kiến trúc bộ nhớ chia sẻ đối với các nhà cung cấp khác nhau. Hình 8: Các thành phần trong OpenMP Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 16 2.2 Kiến trúc bộ nhớ chia sẻ Hệ thống bộ nhớ chia sẻ bao gồm nhiều bộ xử lý CPU, mỗi bộ xử lý truy cập tới bộ nhớ chung thông qua các siêu kết nối hoặc các đường bus. Việc sử dụng không gian địa chỉ đơn làm cho mỗi bộ xử lý đều có một cái nhìn giống nhau về bộ nhớ được sử dụng. Truyền thông trong hệ thống bộ nhớ chia sẻ thông qua cách đọc và ghi dữ liệu giữa các bộ xử lý với nhau lên bộ nhớ. Với cách này, thời gian truy cập tới các phần dữ liệu là như nhau, vì tất cả các quá trình truyền thông đều thông qua đường bus. Ưu điểm của kiến trúc này là dễ dàng lập trình, bởi vì không có một sự truyền thông chính tắc bắt buộc nào giữa các bộ xử lý với nhau, chúng chỉ đơn giản là truy cập tới bộ nhớ chung. Điều khiển quá trình truy cập tới bộ nhớ chung thông qua các kỹ thuật được phát triển trong các máy tính đa nhiệm, như kỹ thuật semaphores… Để tránh tình trạng thắt nút cổ chai, gây ra bởi việc nhiều bộ xử lý truy cập tới cùng một vị trí trong bộ nhớ, người ta chia bộ nhớ chung thành các module. Mỗi module nhớ được kết nối với một bộ xử lý thông qua một mạng chuyển mạch hiệu năng cao. Hình 9: Kiến trúc bộ nhớ chia sẻ Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 17 Một số ví dụ về các máy tính bộ nhớ chia sẻ: • SGI Origin2000: là sự kết hợp hiệu quả giữa kiến trúc bộ nhớ chia sẻ và bộ nhớ phân tán. Bộ nhớ được phân tán về mặt vật lý giữa các nút, với 2 bộ xử lý tại mỗi nút. Quyền truy cập tới bộ nhớ cục bộ của các bộ xử lý tại các nút là như nhau. Xét theo khía cạnh kiến trúc chia sẻ, tất cả các nút đều có quyền truy cập giống nhau tới bộ nhớ phân tán vật lý ( • Sun HPC servers, như Enterprise 3000 (gồm từ 1 đến 6 bộ xử lý) hoặc Enterprise 10000 (gồm 4 đến 64 bộ xử lý). ( • HP Exemplar series, như S-class (gồm 4 đến 16 bộ xử lý), X-class (tới 64 bộ xử lý) ( • DEC Ultimate Workstation. Gồm 2 bộ xử lý, nhưng tốc độ của mỗi bộ xử lý rất cao (533 MHz) ( html). 2.3 Mục tiêu của OpenMP • Cung cấp giao diện chuẩn: OpenMP đưa ra một giao diện chuẩn cho các hệ thống máy tính bộ nhớ chia sẻ. • Tính đơn giản: bao gồm tập các chỉ thị đơn giản và dễ sử dụng cho lập trình trên hệ thống máy tính bộ nhớ chia sẻ. Một chương trình song song hóa có thể chỉ cần sử dụng 3 hoặc 4 chỉ thị biên dịch. • Tính dễ sử dụng: o Khả năng để thực hiện song song cho các chương trình tuần tự. o Khả năng thực hiện song song hóa ở mức thô sơ, hoặc mức chi tiết. • Tính khả chuyển: hỗ trợ Fortran, C, C++ Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 18 2.4 Môi trường hỗ trợ OpenMP Qua tìm hiểu, ta thấy OpenMP là một mô hình lập trình ứng dụng song song dựa trên nền tảng của kiến trúc bộ nhớ chia sẻ, có tính khả chuyển và có thể mở rộng, giúp cho người lập trình có được một giao diện đơn giản và mềm dẻo khi xây dựng ứng dụng. OpenMP được xây dựng dựa trên sự hợp tác của các tập đoàn: • Digital Equipment Corp. ( • IBM ( • Intel Corporation ( • Kuck & Associates Inc. ( • Silicon Graphics Inc. ( Ngày nay nhiều hãng phần cứng, phần mềm và các nhà phát triển ứng dụng chính đều đang xác nhận tính năng của OpenMP. Xem chi tiết tại website để cập nhật thông tin cũng như các phiên bản, các chuẩn dành cho OpenMP. Ví dụ về một vài trình biên dịch có hỗ trợ OpenMP: • Absoft Pro FortranMP 6.0 ( • IBM XL Fortran ( • KAI KAP/Pro Toolset ( 2.5 Mô hình lập trình OpenMP OpenMP dựa trên việc sử dụng số lượng các luồng hiện có trong lập trình song song bộ nhớ chia sẻ. Đó là một mô hình lập trình chính tắc, cung cấp đầy đủ các điều khiển cho người lập trình. Có thể xem mô hình lập trình OpenMP như là một mô hình Fork-Join. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 19 Hình 10: Mô hình Fork-Join Trong mô hình Fork-Join, tất cả các chương trình OpenMP đều bắt đầu bởi một tiến trình đơn. Đó là master thread (luồng chính). Luồng chính này được thực hiện tuần tự cho đến khi gặp chỉ thị khai báo vùng cần song song hóa. Fork: sau khi gặp chỉ thị khai báo song song, master thread sẽ tạo ra một nhóm các luồng song song. Khi đó, các câu lệnh trong vùng được khai báo song song sẽ được thực hiện song song hóa trên nhóm các luồng vừa được tạo. Join: khi các luồng đã thực hiện xong nhiệm vụ của mình, chúng sẽ tiến hành quá trình đồng bộ hóa, ngắt luồng, và chỉ để lại 1 luồng duy nhất là master thread. 2.6 Một số chỉ thị cơ bản trong OpenMP Kỹ thuật để song song hóa đoạn code chính là các chỉ thị biên dịch. Chỉ thị biên dịch được thêm vào mã nguồn, để chỉ ra phần nào được tiến hành song song trên hệ thống bộ nhớ chia sẻ. Cùng với đó là một số chỉ thị đặc biệt chỉ ra phương thức song song hóa như thế nào? Ưu điểm của kỹ thuật này là dễ sử dụng và có tính khả chuyển đối với hệ thống các máy tính tuần tự và máy tính đa xử lý. Bởi vì đối với các trình biên dịch tuần tự, những chỉ thị này được coi như là các comment. Chú ý khi sử dụng thuật ngữ. OpenMP hỗ trợ ngôn ngữ C/C++ và Fortran. Tuy giống nhau về mặt ngữ nghĩa, song cấu trúc khai báo các chỉ thị của OpenMP lại khác nhau. Ví dụ: • Fortran: Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 20 f77: !$OMP PARALLEL f77: call work(x,y) f77: !$OMP END PARALLEL • C/C++: C/C++: #pragma omp parallel C/C++: { C/C++: work(x,y); C/C++: } Dưới đây là tóm tắt các chỉ thị cơ bản khi lập trình với OpenMP (dùng trong ngôn ngữ C/C++) 2.6.1 Các chỉ thị song song hóa Các chỉ thị song song hóa được thêm vào mã nguồn có cấu trúc như sau. Cấu trúc: #pragma omp directive_name [clauses] Chú ý: cuối các chỉ thị song song đều phải xuống dòng. 2.6.2 Chỉ thị khai báo miền song song Chỉ thị này xác định vùng cần tiến hành song song hóa. Khi một thread bắt gặp chỉ thị khai báo miền cần song song, nó sẽ tạo ra một nhóm các thread khác nhau, đồng thời trở thành master thread. Master thread có ID là 0. Số lượng các thread được xác định thông qua biến môi trường hoặc qua lời gọi hàm thư viện. Các thread này sẽ thực hiện đoạn mã nằm trong khai báo song song. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 21 Hình 11: Minh họa vùng được song song hóa Cấu trúc: #pragma omp parallel [clause [clause]…] strutured block Trong đó clause có thể là: • private • shared • default • firstprivate • reduction • if (scalar_logical_expression) • copyin 2.6.3 Chỉ thị liên quan tới môi trường dữ liệu • private (list): khai báo danh sách các biến là private đối với mỗi thread. Điều đó có nghĩa một quá trình xử lý sẽ sử dụng một bản sao các biến. Tham chiếu tới các biến gốc được thay thế bởi tham chiếu tới các bản sao. Vùng liên tục Vùng song song Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 22 • firstprivate (list): giống với khai báo private, song bản sao danh sách các biến được gán giá trị ban đầu là giá trị của các biến gốc. • lastprivate (list): giống với khai báo private, các biến gốc trong danh sách sẽ được gán giá trị là giá trị cuối cùng sau khi ra khỏi vòng lặp hoặc ra khỏi một section. • shared (list): tất cả các thread đều có quyền truy cập tới cùng một danh sách các biến được khai báo là shared. Về thực chất, biến được chia sẻ chiếm một vị trí cụ thể trong bộ nhớ. Mọi thread có thể đọc và ghi thông qua địa chỉ nhớ đó. Vấn đề đặt ra là phải đảm bảo cho các thread truy cập một cách hợp lý tới các biến chia sẻ. • default (shared | none): thiết lập thuộc tính mặc định cho tất cả các biến được sử dụng trong vùng song song hóa. Riêng các biến trong khai báo threadprivate không chịu ảnh hưởng của default. Các biến có thể được khai báo chính tắc là private, shared…mà không cần phải khai báo default. • reduction (operator : list): cho phép các biến thuộc list (biến shared) có các bản sao là private trong mỗi thread. Các thread sẽ thực hiện và ghi giá trị vào biến private đó. Kết thúc chỉ thị reduction, biến shared trong list được lấy giá trị từ các biến private ở mỗi thread bằng cách áp dụng toán tử operator. Toán tử operator có thể là các phép +, *, -, max, min, … • schedule (type [, chunk_size]): Chỉ thị này chỉ ra cách thức vòng lặp for được phân chia như thế nào giữa các thread, thường được sử dụng để tạo trạng thái cân bằng tải giữa các thread. Trong đó type có thể là: static, dynamic, guided, hoặc runtime o static: Nếu không chỉ ra chunk_size thì chunk_size được gán bằng CEILING(tổng số lần lặp/số luồng). Các chunk được gán lần lượt cho các thread (tức là theo kiểu round-robin) o dynamic: Nếu không chỉ ra chunk_size thì chunk_size được gán bằng 1. Các chunk được gán cho các thread theo kiểu: thread nào rỗi hoặc đến trước thì thực hiên trước (first-come first-do). Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 23 o guided: Nếu không chỉ ra chunk_size thì chunk_size được gán bằng 1. Nếu chỉ ra chunk_size thì tổng số lần lặp sẽ được chỉ ra sao cho cỡ của các chunk nối tiếp nhau (theo chỉ số tăng dần) hay chunk_size giảm theo hàm mũ. chunk_size chính là cỡ của chunk bé nhất. Cách làm: chunk_size đầu tiên = CEILING(số lần lặp chia cho số thread). các chunk_size tiếp theo = CEILING(số lần lặp còn lại chia cho số thread) Khi thực hiện, nếu số lượng chunk lớn hơn số thread thì thread nào thực hiện xong phần việc của mình sẽ đảm nhiệm chunk tiếp theo chưa được thực hiện. o runtime: Chunk_size sẽ được xác định khi chương trình được thực hiện. Kiểu schedule sẽ là static hoặc được chỉ ra thông qua biến môi trường OMP_SCHEDULE (như vậy có thể là DYNAMIC, GUIDED...) • threadprivate: #pragma omp threadprivate (list) Chỉ thị threadprivate được sử dụng để làm cho các biến có phạm vi toàn cục trở thành cục bộ và tiếp tục tồn tại trong mỗi thread trong suốt các quá trình cần được song song hóa. Chỉ thị phải được xuất hiện ngay sau khi khai báo biến. Sau đó mỗi thread sẽ làm việc với một bản sao các biến. • copyin (list): gán giá trị cho các biến được khai báo là threadprivate trong các thread bằng giá trị của các biến gốc trong master thread trước khi thực hiện song song. List chứa danh sách các biến để sao chép. 2.6.4 Chỉ thị liên quan tới chia sẻ công việc 2.6.4.1 Do/for Chỉ thị Do/for cho biết vòng lặp for nằm trong khai báo phải được thực thi song song. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 24 Hình 12: Hình minh họa chỉ thị Do/for Cấu trúc: #pragma omp for [clause [clause]…] C/C++ for loop Trong đó clause có thể là: • private (list) • firstprivate (list) • lastprivate (list) • reduction (operator:list) • schedule (type [,chunk_size]) • ordered • nowait Ý nghĩa của private, firstprivate, lastprivate, reduction, schedule đã được mô tả ở mục 6.3. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 25 o ordered: phải được xuất hiện khi trong vòng lặp for có sử dụng chỉ thị ordered o nowait: cho biết các thread không cần phải tiến hành đồng bộ hóa khi kết thúc vòng lặp song song. Chúng tiếp tục thực hiện các câu lệnh sau vòng lặp mà không cần phải chờ đợi thread nào. Có thể kết hợp giữa khai báo song song với chỉ thị chia sẻ công việc bằng cấu trúc sau: #pragma omp parallel for [clauses] for loop 2.6.4.2 Sections Chỉ thị Sections chỉ ra các đoạn mã được phân chia như thế nào giữa các thread. Một khai báo sections có thể gồm nhiều section con độc lập với nhau. Mỗi một section được thực hiện 1 lần bởi một thread. Nếu thời gian thực hiện là đủ nhanh và cách cài đặt cho phép, một thread có thể thực hiện nhiều hơn 1 section. Nếu số lượng thread nhiều hơn số lượng section, khi đó một vài thread có thể rỗi. Nếu số lượng thread ít hơn so với section, tùy thuộc vào cách cài đặt sẽ xác định các section được thực hiện như thế nào. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 26 Hình 13: Hình minh họa chỉ thị sections Cấu trúc: #pragma omp sections [clause[ clause] . . . ] { [#pragma omp section ] structured-block [#pragma omp section structured-block . . . ] } Trong đó clause có thể là: • private • lastprivate • firstprivate • reduction Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 27 • nowait Ý nghĩa của các thông số trên giống như đã được mô tả ở các phần trước. Có thể kết hợp giữa khai báo sections với khai báo parallel. #pragma omp parallel sections [clauses] { [#pragma omp section ] structured-block [#pragma omp section ] structured-block . . . ] } 2.6.4.3 Single Chỉ thị cho biết đoạn mã nằm trong khai báo single sẽ được thực thi bởi duy nhất một thread. Nếu không có tùy chọn nowait, các thread khác sẽ không thực hiện chỉ thị single và chờ đợi tại điểm cuối của khối lệnh trong khai báo single. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 28 Hình 14: Hình minh họa chỉ thị single Cấu trúc: #pragma omp single [clauses] structured-block Trong đó clause có thể là: • private • firstprivate • nowait 2.6.5 Chỉ thị đồng bộ hóa Xét ví dụ đơn giản dưới đây: 2 thread nằm trên 2 bộ xử lý khác nhau đều cùng thực hiện việc tăng giá trị của biến x vào một thời điểm. (giả sử x = 0) THREAD 1: increment(x) THREAD 2: increment(x) Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 29 { x = x + 1; } THREAD 1: 10 LOAD A, (x address) 20 ADD A, 1 30 STORE A, (x address) { x = x + 1; } THREAD 2: 10 LOAD A, (x address) 20 ADD A, 1 30 STORE A, (x address) Có thể xảy ra trường hợp: • thread1 lưu giá trị x vào thanh ghi A • thread2 lưu giá trị x vào thanh ghi A • thread1 cộng thêm 1 vào giá trị x trong thanh ghi A • thread2 cộng thêm 1 vào giá trị x trong thanh ghi A • thread1 lưu giá trị trong thanh ghi A tại địa chỉ của x • thread2 lưu giá trị trong thanh ghi A tại địa chỉ của x Kết quả: x=1, không phải là 2 như mong đợi. Để tránh tình trạng trên, việc tăng giá trị x phải được đồng bộ hóa giữa các thread để đảm bảo cho kết quả chính xác. Dưới đây là một số chỉ thị liên quan tới đồng bộ hóa. 2.6.5.1 Master Chỉ thị cho biết đoạn mã nằm trong khai báo master sẽ được thực hiện bởi master thread. Các thread khác sẽ bỏ qua đoạn mã này và tiếp tục thực hiện bình thường. Cấu trúc: Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 30 #pragma omp master structured-block 2.6.5.2 Critical Chỉ thị xác định đoạn mã nằm trong khai báo sẽ được truy cập bởi duy nhất một thread vào một thời điểm. Các thread khác sẽ phải chờ cho đến khi không có thread nào thực hiện đoạn mã đó. Cấu trúc: #pragma omp critical [(name)] structured-block 2.6.5.3 Barrier Khi 1 thread gặp chỉ thị barrier, thread đó sẽ phải chờ cho đến khi nào tất cả các thread còn lại đều gặp chỉ thị này. Cấu trúc: #pragma omp barrier 2.6.5.4 Atomic Chỉ thị atomic xác định một vùng bộ nhớ cụ thể nào đó sẽ được cập nhật một cách từng phần, không cho phép nhiều thread cùng thực hiện tại đó vào một thời điểm. Chỉ thị chỉ áp dụng cho các câu lệnh đơn. Cấu trúc: #pragma omp atomic statement_expression Các câu lệnh đơn có thể là: ++x x++ --x x-- Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 31 và các toán tử +, -, *, /, &, ^, |, >> hoặc << 2.6.5.5 Flush Chỉ thị flush sẽ ghi lại các biến visible trong thread vào bộ nhớ. Người lập trình có thể tự xác định quá trình đồng bộ hóa một cách trực tiếp trên bộ nhớ chia sẻ thông qua việc sử dụng flush. Tùy chọn list được sử dụng để xác định danh sách các biến cần flush, nếu không có tùy chọn này tất cả các biến sẽ được ghi lại vào bộ nhớ. Cấu trúc: #pragma omp flush [(list)] 2.6.5.6 Ordered Chỉ thị ordered xác định vòng lặp sẽ được thực hiện theo thứ tự như thể được thực thi trên bộ xử lý tuần tự. Ordered chỉ xuất hiện trong khai báo chỉ thị lặp Do/for. Tại một thời điểm, chỉ có một thread thực hiện công việc trong phần khai báo ordered. Cấu trúc: #pragma omp ordered structured-block 2.6.6 Thư viện và một số biến môi trường 2.6.6.1 Một số hàm trong thư viện của OpenMP Để sử dụng được các hàm có sẵn trong OpenMP, cần phải thêm file header “omp.h” trong khi include các thư viện. #include Một vài hàm cơ bản trong thư viện của OpenMP: • void omp_set_num_threads(int num_threads) • int omp_get_num_threads(void) • int omp_get_max_theads(void) • int omp_get_thead_num(void) • int omp_get_num_procs(void) Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 32 • int omp_in_parallel(void) • void omp_set_dynamic(int dynamic_threads) • int omp_get_dynamic(void) • void omp_set_nested(int nested) • int omp_get_nested(void) • ………… 2.6.6.2 Một số biến môi trường trong OpenMP Biến môi trường được sử dụng để điều khiển quá trình thực thi các đoạn mã song song. Truyền giá trị cho các biến môi trường tùy thuộc vào trình biên dịch và kiến trúc hệ thống bộ nhớ chia sẻ. Có thể truyền giá trị cho biến môi trường bằng: • export tên_biến = giá trị • setenv tên_biến giá_trị ví dụ: export OMP_NUM_THREADS=5 setenve OMP_NUM_THREADS 5 Một số biến môi trường thường gặp: • OMP_SCHEDULE • OMP_NUM_THREADSOMP_DYNAMIC • OMP_NESTED Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 33 2.7 Ví dụ về lập trình song song với OpenMP 2.7.1 omp_hello.c Chương trình minh họa hoạt động của các thread khi thực hiện song song. • Biến tid được khai báo là private, lưu ID của mỗi thread. • Biến private nthreads cho biết số lượng thread tham gia vào quá trình song song. 2.7.2 Cách biên dịch Tùy theo các nhà cung cấp và trình biên dịch hiện sử dụng, có thể có nhiều cách để biên dịch một chương trình OpenMP. Với hệ thống máy IBM, dùng cờ -qsmp=omp Với hệ thống máy Intel, dùng cờ -openmp Với hệ thống Compag, dùng cờ -omp /* omp_hello.c */ #include int main () { int nthreads, tid; /* Fork a team of threads giving them their own copies of variables */ #pragma omp parallel private(nthreads, tid) { /* Obtain thread number */ tid = omp_get_thread_num(); printf("Hello World from thread = %d\n", tid); /* Only master thread does this */ if (tid == 0) { nthreads = omp_get_num_threads(); printf("Number of threads = %d\n", nthreads); } } /* All threads join master thread and disband */ Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 34 Trên máy IBM AIX, để dịch chương trình “omp_hello.c”, dùng lệnh: xlc_r –qsmp=omp omp_hello.c –o hello Để thực hiện chương trình, gõ lệnh: ./hello Nếu không chỉ rõ số lượng thread cần sử dụng để thực hiện quá trình song song, thì chương trình sẽ lấy số thread mặc định hiện có trong hệ thống kiến trúc bộ nhớ chia sẻ. Có thể xác định số thread cần thiết thông qua hàm thư viện omp_set_num_threads(int num_threads) hoặc truyền giá trị cho biến môi trường OMP_NUM_THREADS bằng lệnh: export OMP_NUM_THREADS Giả sử, trong ví dụ trên đặt số thread là 4: export OMP_NUM_THREADS=4 Xem trang để biết thêm chi tiết về một số chỉ thị biên dịch. 2.7.3 Kết quả Hello World from thread = 0 Number of threads = 4 Hello World from thread = 3 Hello World from thread = 1 Hello World from thread = 2 Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 35 Chương 3: SONG SONG HÓA THUẬT TOÁN BARNES-HUT 3.1 Treecode Để tiến hành song song hóa thuật toán Barnes-Hut với bài toán N-body, ta xét chương trình treecode của J. Barnes làm ví dụ. Treecode là một trong những chương trình mô phỏng bài toán N-body. Dựa trên nền tảng của thuật toán Barnes-Hut, treecode thực hiện nhanh hơn và kiểm soát lỗi tốt hơn so với các chương trình mô phỏng hệ N-body trước đó. Như đã biết, trong thuật toán Barnes-Hut, sau khi xây dựng cây Quadtree (hoặc Octree), ta tiến hành duyệt cây để tính lực tác dụng lên từng hạt. Tuy nhiên, việc duyệt cây tốn rất nhiều thời gian. Treecode giảm thiểu chi phí cho duyệt cây bằng cách sử dụng tính chất: các hạt liền kề có danh sách các tương tác với nó là giống nhau. Ý tưởng này đã được sử dụng trước đó để nhằm tăng tốc khi tính toán lực trên các máy vector [3], nhưng các chương trình đó chỉ đơn giản áp dụng tìm kiếm cây trong một khối hạt nhỏ. Treecode áp dụng cho tất cả các mức của cây. Lực tác dụng lên các hạt được tính thông qua một vòng duyệt cây đệ quy. Quá trình duyệt cây đệ quy này lưu trữ và cập nhật danh sách các tương tác (interaction list). Tại mỗi mức của cây, hạt b (giả sử nằm trong ô c) được sử dụng để phân biệt với danh sách các tương tác mà b có thể có. Khi duyệt đệ quy tới hạt b, danh sách tương tác sẽ được sử dụng để tính lực hấp dẫn và thế năng tại hạt b. 3.1.1 Cấu trúc dữ liệu của cây Cấu trúc dữ liệu chính được sử dụng trong treecode là cây Octree, bao gồm các body và các cell. Lá của cây lưu trữ thông tin của body. Các nút trong của cây là các cell. Tiến hành duyệt toàn bộ cây bắt đầu từ gốc của cây. Cấu trúc cây Octree có thể được biểu diễn đơn giản như sau: Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 36 Hình 15: Cấu trúc dữ liệu cây trong treecode (1) Cấu trúc node biểu diễn các thông tin chung của body và cell. Theo lý thuyết, mỗi một thành phần của cây có thể được biểu diễn là tổ hợp của body và cell. Nhưng cách biểu diễn đó là không hiệu quả, vì cấu trúc của body và cell đòi hỏi không gian bộ nhớ khác nhau. Do vậy người ta sử dụng cấu trúc node để biểu diễn chung cho body và cell. Việc ép kiểu được sử dụng để chuyển con trỏ có kiểu tùy ý thành con trỏ trỏ tới node, body và cell. typedef struct _node { short type; bool update; real mass; vector pos; struct _node *next; } node, *nodeptr; #define Type(x) (((nodeptr) (x))->type) #define Update(x) (((nodeptr) (x))->update) #define Mass(x) (((nodeptr) (x))->mass) #define Pos(x) (((nodeptr) (x))->pos) #define Next(x) (((nodeptr) (x))->next) Trong đó: Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 37 • Type(q) trả lại kiểu của node q, có giá trị là CELL hoặc BODY • Update(q) có giá trị là boolean, cho biết q có cần cập nhật lực tương tác không? • Next(q) là con trỏ, trỏ tới node tiếp theo của q, sau khi tất cả các con của q đã được duyệt. • Mass(q) là khối lượng của hạt q hoặc là khối lượng của tất cả các hạt có trong cell q • Pos(q) là vị trí của hạt q hoặc vị trí của tâm khối trong cell q Cấu trúc body biểu diễn các hạt. typedef struct { node bodynode; vector vel; vector acc; real phi; } body, *bodyptr; #define Vel(x) (((bodyptr) (x))->vel) #define Acc(x) (((bodyptr) (x))->acc) #define Phi(x) (((bodyptr) (x))->phi) Trong đó: • Vel(b) là vận tốc của hạt b • Acc(b) là gia tốc của hạt b • Phi(b) là thế năng của hạt b Cấu trúc cell biểu diễn các nút trong của cây #define NSUB (1 << NDIM) typedef struct { node c