Đề tài Song song hóa thuật toán Barnes - Hut với OpenMP

i lượng và vị trí tâm khối trong hộp. Giả sử θ (theta) là ngưỡng (góc mở) cần tính toán (thông thường 0 < θ <= 1). Nếu D/r < θ, ta tính lực hấp dẫn tác dụng lên các hạt như sau. • (x, y, z) là vị trí của hạt trong không gian 3 chiều. • m là khối lượng của hạt. • (xcm, ycm, zcm) là vị trí của tâm hạt trong hộp • mcm là tổng khối lượng các hạt có trong hộp • G là hằng số hấp dẫn Khi đó lực hấp dẫn sẽ được tính theo công thức xấp xỉ là: Force = G * m * mcm * ( (xcm-x)/r3, (ycm-y)/r3, (zcm-z)/r3) (*) Trong đó r = sqrt ((xcm-x)2 + (ycm-y)2 + (zcm-z)2 ) là khoảng cách từ hạt tới tâm các hạt có trong hộp. Nếu D/r >= θ, quá trình tính lực tác dụng lên một hạt được áp dụng đệ quy. Lực tác dụng lên hạt bằng tổng các lực ở các nút con tác dụng lên hạt đó. Thuật toán tính lực tác dụng lên hạt ở bước này có thể được mô tả như dưới đây. Kích thước của hộp Khoảng cách từ hạt tới tâm khối Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 13 ... với mỗi hạt, duyệt cây để tính lực tác dụng lên nó For i = 1 to n f(i) = TreeForce(i,root) end for function f = TreeForce(i,n) ... tính lực hấp dẫn tác dụng lên hạt i ... dựa vào tất cả các hạt có trong nút n f = 0 if n chứa 1 hạt f = lực tính được dựa vào công thức (*) else r = khoảng cách từ hạt i tới tâm khối tại n D = kích thước của cell n if D/r < theta tính lực f dựa vào công thức (*) else for tất cả các con c của n f = f + TreeForce(i,c) end for end if end if Qua thuật toán trên ta nhận thấy: quá trình duyệt cây để tính lực tác dụng lên hạt là độc lập đối với mỗi hạt. Bởi vậy có thể tiến hành song song hóa quá trình này để nhằm tăng tốc bài toán N-body. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 14 Hiện nay, đã 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 cellnode; Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 38 #if !defined(QUICKSCAN) real rcrit2; #endif nodeptr more; union { nodeptr subp[NSUB]; matrix quad; } sorq; } cell, *cellptr; #if !defined(QUICKSCAN) #define Rcrit2(x) (((cellptr) (x))->rcrit2) #endif #define More(x) (((cellptr) (x))->more) #define Subp(x) (((cellptr) (x))->sorq.subp) #define Quad(x) (((cellptr) (x))->sorq.quad) Trong đó: • Subq(c) là mảng các con trỏ trở tới các con của c • More(c) là con trỏ trỏ tới con đầu tiên trong các con của c • Quad(c) là ma trận quadrupole moments • Rcrit2(c) là bình phương bán kính mà nếu nằm ngoài bán kính đó, ô cell c được coi như là một cell interaction. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 39 Hình 16: Cấu trúc dữ liệu cây trong treecode (2) 3.1.2 Các biến toàn cục Treecode sử dụng các biến toàn cục. Biến toán cục được sử dụng chung cho tất cả các tệp của chương trình và được khai báo với định nghĩa global. Định nghĩa global như sau: #define global extern Các tham số đầu vào: • theta: cho biết độ chính xác khi tính toán lực. Tham số này không được xác định nếu bản QUICKSCAN được biên dịch • options: là một chuỗi các tùy chọn để điều khiển thời gian chạy • usequad: cờ cho biết có sử dụng quadrupole correctión hay không? Các biến được sử dụng khi xây dựng cây: • root: con trỏ trỏ tới root cell • rsize: kích cỡ của root cell • ncell: số các cell được sử dụng để xây dựng cây • tdepth: chiều cao của cây • cputree: thời gian CPU đòi hỏi để xây dựng cây Các biến được sử dụng khi tính lực: Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 40 • actmax: độ dài lớn nhất của danh sách active trong khi tính lực • nbbcalc: số các tương tác giữa các hạt với nhau • nbccalc: số các tương tác giữa các hạt và các cell • cpuforce: thời gian CPU cần để tính lực 3.2 Thử nghiệm và đánh giá hiệu năng của treecode 3.2.1 Thử nghiệm chương trình treecode Toàn bộ mã chương trình treecode do J. Barnes viết có thể được download tại trang web Treecode được viết bằng ngôn ngữ C (ANSI C). Giả sử chương trình được biên dịch bởi trình biên dịch của hệ điều hành LINUX. Download file treecode.tar.gz tại trang web trên. Để thực hiện chương trình, copy file vào thư mục riêng, rồi thực hiện lệnh gunzip để giải nén tệp. $ gunzip treecode.tar.gz $ tar xvf treecode.tar Thư mục sau đó sẽ chứa các file .c , .h và Makefile Trước khi biên dịch, có thể cần phải chỉnh sửa một số thông tin trong Makefile tùy theo kiến trúc máy tính và trình biên dịch hiện đang sử dụng. Ở đây, ta sửa lại thông tin trong Makefile bằng cách thêm tùy chọn –pg vào các cờ biên dịch: CCFLAGS và cờ LDFLAGS để khi thực hiện chương trình sẽ sinh ra file gmon.out Tùy chọn biên dịch trong Makefile được sửa lại như dưới đây: # Compiler options. # LINUX: CCFLAGS = -pg -DLINUX LDFLAGS = -pg OPTFLAG = -O3 Thực hiện câu lệnh make để dịch nhiều file với nhau Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 41 $ make treecode Thực hiện chương trình bằng ./treecode [tham số] Có thể xem các tham số bằng câu lệnh: ./treecode –help treecode Hierarchical N-body code (theta scan) in= Input file with initial conditions out= Output file of N-body frames dtime=1/32 Leapfrog integration timestep eps=0.025 Density smoothing length theta=1.0 Force accuracy parameter usequad=false if true, use quad moments options= Various control options tstop=2.0 Time to stop integration dtout=1/4 Data output timestep nbody=4096 Number of bodies for test run seed=123 Random number seed for test run save= Write state file as code runs restore= Continue run from state file VERSION=1.4 Joshua Barnes February 21 2001 Khi thực hiện chương trình, kết quả của quá trình tính toán sẽ được hiển thị ra màn hình, có dạng như sau: Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 42 3.2.2 Đánh giá hiệu năng Mặc dù treecode là một cải tiến của thuật toán Barnes-Hut, với tốc độ tính toán lực nhanh hơn và vấn đề kiểm soát lỗi tốt hơn so với các chương trình trước đó, song vấn đề duyệt cây vẫn chiếm đa số thời gian thực hiện chương trình. Có thể xem thời gian thực hiện các hàm trong toàn bộ chương trình thông qua profile của nó. Thực hiện lệnh gprof với chương trình treecode để xem thông tin profile về chương trình như sau: gprof treecode gmon.out > treecode.out Kết quả hiển thị trong file treecode.out có dạng: Hierarchical N-body code (theta scan) nbody dtime eps theta usequad dtout tstop 4096 0.03125 0.0250 1.00 false 0.25000 2.0000 rsize tdepth ftree actmax nbbtot nbctot CPUfc 64.0 13 3.050 1114 1051990 1417390 0.003 time |T+U| T -U -T/U |Vcom| |Jtot| CPUtot 0.000 0.24032 0.25082 0.49114 0.51069 0.00000 0.00576 0.004 rsize tdepth ftree actmax nbbtot nbctot CPUfc 64.0 12 3.108 1121 1054863 1419799 0.003 time |T+U| T -U -T/U |Vcom| |Jtot| CPUtot 0.031 0.24028 0.25075 0.49104 0.51066 0.00001 0.00576 0.007 rsize tdepth ftree actmax nbbtot nbctot CPUfc 64.0 13 3.057 1108 1040044 1422316 0.003 time |T+U| T -U -T/U |Vcom| |Jtot| CPUtot 0.062 0.24029 0.25069 0.49098 0.51059 0.00001 0.00576 0.011 rsize tdepth ftree actmax nbbtot nbctot CPUfc Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 43 Kết quả này có được khi biên dịch và thực hiện chương trình trên máy Intel với 1 CPU, Pentium 4 CPU 2.26GHz, 240MB RAM, hệ điều hành LINUX. Như vậy, qua kết quả trên ta thấy hàm walktree chiếm đến 96.02% tổng số thời gian thực hiện cả chương trình, trong khi phần trăm thời gian thực hiện các hàm khác là rất nhỏ. Do vậy, tuy thời gian thực hiện treecode có nhanh hơn và vấn đề kiểm soát lỗi là tốt hơn so với các chương trình mô phỏng bài toán N-body trước đó, song để tối ưu hóa chương trình treecode, ta tiến hành thử nghiệm song song hóa chương trình với OpenMP trên máy Intel 4 CPU nhằm tăng hiệu năng tính toán. 3.3 Song song hóa treecode với OpenMP 3.3.1 Môi trường thực hiện song song Thực hiện song song hóa thuật toán treecode trên môi trường Intel (R) Xeon (TM) 4 CPU 2.40 GHz. Thông tin chi tiết về cấu hình 1 CPU trên máy Intel được cho dưới đây: processor : 0 vendor_id : GenuineIntel cpu family : 15 model : 2 model name : Intel(R) Xeon(TM) CPU 2.40GHz stepping : 7 Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 96.02 129.09 129.09 65 1.99 1.99 walktree 0.96 130.37 1.29 2466730 0.00 0.00 subindex 0.95 131.65 1.28 65 0.02 0.02 diagnostics 0.76 132.68 1.03 266240 0.00 0.00 loadbody 0.57 133.44 0.76 65 0.01 0.01 hackcofm 0.21 133.72 0.28 65 0.00 0.00 threadtree 0.19 133.97 0.25 65 0.00 0.00 newtree 0.13 134.15 0.18 64 0.00 2.05 stepsystem 0.10 134.28 0.13 65 0.00 0.00 expandbox 0.05 134.35 0.07 130637 0.00 0.00 makecell 0.03 134.39 0.04 69477 0.00 0.00 xrandom 0.01 134.41 0.02 130637 0.00 0.00 setrcrit 0.01 134.43 0.02 8192 0.00 0.00 fpickshell 0.01 134.45 0.02 65 0.00 2.05 treeforce 0.01 134.46 0.01 1 0.01 0.07 testdata Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 44 cpu MHz : 2394.914 cache size : 512 KB Physical processor ID: 0 Number of siblings : 2 fdiv_bug : no hlt_bug : no f00f_bug : no coma_bug : no fpu : yes fpu_exception : yes cpuid level : 2 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm bogomips : 4750.85 3.3.2 Thực hiện song song Theo đánh giá hiệu năng của treecode ở mục 3.2.2, ta thấy phần lớn thời gian chương trình dành cho việc thực hiện hàm walktree. Để tăng hiệu năng tính toán của treecode, ta tiến hành song song hóa treecode bằng cách song song hóa các hàm trên. Khó khăn gặp phải trong khi tiến hành song song hóa treecode đó là sự phụ thuộc vào chương trình dịch. Với các trình biên dịch của các kiến trúc máy tính khác nhau sẽ cho thời gian thực hiện từng hàm con trong chương trình treecode là khác nhau. Ví dụ với trình biên dịch của máy IBM eServer Cluster 1600, hệ điều hành AIX5.2 với cấu hình như sau: • 5 node tính toán pSeries 655, mỗi node gồm 8 CPU Power 4+ 64 bit RISC 1.7 GHz của IBM; cache 5.6MB ECC L2, 128MB ECC L3, băng thông: 72.3 GBps; 32GB RAM, băng thông bộ nhớ 51.2 GBps; 6x36 GB HDD. Năng lực tính toán tổng cộng khoảng 240 GFlops (mở rộng tối đa 768 GFlops/16 node). • 1 node quản lý CSM p630: Power4+ 64 bit 1.2 GHz; cache 1.5 MB ECC L2, 8MB ECC L3, băng thông: 12.8 GBps; 1GB RAM, băng thông: 6.4 GBps; 6x36 GB HDD, DVD ROM. • 1 node điều khiển phần cứng HCM: Intel Xeon 3.06 GHz, 1GB RAM, 40 GB HDD, DVD RAM. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 45 • Các node được kết nối với nhau thông qua HPS (High Performance Switch – Switch hiệu năng cao), băng thông 2GBps và GEthernet. • Hệ thống lưu trữ chung: IBM DS4400 và EXP700 kết nối với cụm IBM 1600 thông qua cáp quang với băng thông 2Gbps. • Các node chạy HĐH AIX 5L phiên bản 5.2 Kết quả profile của treecode trên IBM AIX sẽ là: Với trình biên dịch của Intel (R) Xeon (TM) 4 CPU 2.40 GHz, thì phần trăm thời gian thực hiện các hàm của treecode là: % cumulative self self total time seconds seconds calls ms/call ms/call name 42.3 13.85 13.85 .sqrt [8] 34.8 25.23 11.38 532480 0.02 0.02 .sumnode [9] 7.6 27.73 2.50 .__mcount [11] 5.4 29.50 1.77 161645903 0.00 0.00 .sqrtf [12] 4.0 30.81 1.31 16072949 0.00 0.00 .accept [13] 2.6 31.65 0.84 570149 0.00 0.03 .walktree_13_6 [7] 0.8 31.91 0.26 .qincrement [15] 0.5 32.09 0.18 65 2.77 2.77 .diagnostics [18] 0.4 32.22 0.13 2480994 0.00 0.00 .subindex [19] 0.4 32.34 0.12 .__stack_pointer [20] 0.4 32.46 0.12 .qincrement1 [21] 0.3 32.55 0.09 266240 0.00 0.00 .loadbody [16] 0.2 32.61 0.06 65 0.92 1.25 .hackcofm [22] 0.1 32.64 0.03 65 0.46 0.46 .threadtree [25] Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 46 Như vậy, với các trình biên dịch khác nhau, thời gian thực hiện các hàm của treecode là hoàn toàn khác. Vì vậy, việc đánh giá hàm nào tốn nhiều thời gian nhất cũng như cần phải tiến hành song song hóa như thế nào là vấn đề gặp nhiều khó khăn. 3.3.2.1 Phân tích hàm walktree Hàm walktree là hàm đệ quy chính dùng trong khi tính lực. Nguyên mẫu của nó có dạng void walktree(nodeptr *aptr, nodeptr *nptr, cellptr cptr, cellptr bptr,nodeptr p, real psize, vector pmid); Hàm walktree tính lực hấp dẫn lên tất cả các hạt có trong node p thông qua việc duyệt đệ quy p và các con của nó. Tại mỗi thời điểm trong lượt duyệt đệ quy, thông tin của các node từ gốc tới p được lưu trữ trong một tập các node. Tập đó chính là tập các tương tác. Tập này được chia thành 2 tập cell và body riêng biệt, được trỏ bởi các con trỏ tương ứng là cptr và bptr. Phần còn lại của cây được biểu diễn bởi một tập các active node, bao gồm node p và các node xung quanh nó trong không gian. Con trỏ trỏ tới các node này được lưu vào mảng nằm giữa aptr và nptr. Node p có kích thước là psize và vị trí là pmid. Trong vòng lặp chính, walktree duyệt qua tất cả các active node của p, kiểm tra xem node nào sẽ được thêm vào danh sách tương tác, và node nào gần với p đến mức phải kiểm tra các con của nó ở mức tiếp theo của quá trình duyệt đệ quy. Các cell được kiểm Flat profile: Each sample counts as 0.00195312 seconds. % cumulative self self total time seconds seconds calls ms/call ms/call name 73.87 9.13 9.13 532480 0.02 0.02 sumnode 12.84 10.71 1.59 16013212 0.00 0.00 accept 10.21 11.97 1.26 569962 0.00 0.02 walktree 0.84 12.08 0.10 2466729 0.00 0.00 subindex 0.47 12.14 0.06 266240 0.00 0.00 loadbody 0.46 12.19 0.06 303722 0.00 0.00 walksub 0.27 12.23 0.03 65 0.51 0.51 diagnostics 0.25 12.26 0.03 520 0.06 0.07 hackcofm 0.22 12.28 0.03 520 0.05 0.05 threadtree 0.19 12.31 0.02 266240 0.00 0.03 gravsum 0.14 12.33 0.02 64 0.27 189.50 stepsystem Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 47 tra thông qua hàm accept. Nếu cell cách khá xa p, nghĩa là tỉ số D/r là đủ nhỏ, cell được thêm vào danh sách tương tác của p. Ngược lại, kiểm tra tất cả các con của nó, và thêm vào danh sách các active node. Nếu có danh sách active mới được tạo ra, thì tiếp tục duyệt cây đệ quy ở mức tiếp theo thông qua lời gọi hàm walksub. Hàm walksub thực hiện việc gọi hàm walktree tại các con của p. Ngược lại, nếu không có danh sách active mới nào, tiến hành kiểm tra p. Nếu p là body, thực hiện tính toán lực tại p bằng lời gọi hàm gravsum. Nguyên mẫu của hàm walksub có dạng như sau: void walksub(nodeptr *nptr, nodeptr *np, cellptr cptr, cellptr bptr,nodeptr p, real psize, vector pmid); Các tham số trong hàm walksub có giá trị giống với các tham số trong hàm walktree tại lời gọi hàm. Có 2 trường hợp xảy ra: • Nếu p là cell, khi đó walksub sẽ duyệt qua tất cả các con của p, và gọi hàm walktree tại mỗi nút con đó. • Nếu p là body, walksub sẽ gọi hàm walktree đúng một lần duy nhất, để duyệt nốt danh sách active của nó. Dưới đây là chi tiết của hàm walktree và walksub Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 48 local void walktree(nodeptr *aptr, nodeptr *nptr, cellptr cptr, cellptr bptr, nodeptr p, real psize, vector pmid) { nodeptr *np, *ap, q; int actsafe; if (Update(p)) { /* are new forces needed? */ np = nptr; /* start new active list */ actsafe = actlen - NSUB;/* leave room for NSUB more */ for (ap = aptr; ap < nptr; ap++)/* loop over active nodes */ if (Type(*ap) == CELL) { /* is this node a cell? */ if (accept(*ap, psize, pmid)) {/* does it pass the test?*/ Mass(cptr) = Mass(*ap); /* copy to interaction list */ SETV(Pos(cptr), Pos(*ap)); SETM(Quad(cptr), Quad(*ap)); cptr++; /* and bump cell array ptr */ } else { /* else it fails the test */ if (np - active >= actsafe) /* check list has room */ error("walktree: active list overflow\n"); for (q = More(*ap); q != Next(*ap); q = Next(q)) /* loop over all subcells */ *np++= q; /* put on new active list */ } } else /* else this node is a body */ if (*ap != p) { /* if not self-interaction */ --bptr; /* bump body array ptr */ Mass(bptr) = Mass(*ap);/* and copy data to array */ SETV(Pos(bptr), Pos(*ap)); } actmax = MAX(actmax, np - active); /* keep track of max active */ if (np != nptr) /* if new actives listed */ walksub(nptr, np, cptr, bptr, p, psize, pmid); /* then visit next level */ else { /* else no actives left, so */ if (Type(p) != BODY) /* must have found a body */ error("walktree: recursion terminated with cell\n"); gravsum((bodyptr) p, cptr, bptr); /* sum force on the body */ } } } Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 49 3.3.2.2 Song song hóa treecode Ý tưởng song song hóa treecode như sau: • Sử dụng chỉ thị taskq được hỗ trợ bởi trình dịch của máy Intel, để song song hóa hàm đệ quy walktree. • Với các hàm khác, sử dụng các chỉ thị Do/for để song song hóa vòng lặp. Chỉ thị taskq thiết lập môi trường thực hiện các công việc (task). Khi gặp chỉ thị taskq, một trong số các thread sẽ được chọn để thực hiện chỉ thị đó. Một hàng đợi rỗng được tạo ra bởi thread đã chọn. Sau đó, đoạn chương trình nằm trong khối taskq sẽ được thực hiện bởi một thread đơn. Các thread còn lại chờ thực hiện khối công việc sẽ được thêm vào hàng đợi. Các chỉ thị task xác định một khối công việc có thể được thực hiện bởi nhiều thread khác nhau. Khi gặp chỉ thị task trong khai báo taskq, đoạn chương trình local void walksub(nodeptr *nptr, nodeptr *np, cellptr cptr, cellptr bptr, nodeptr p, real psize, vector pmid) { real poff; nodeptr q; int k; vector nmid; poff = psize / 4; /* precompute mid. offset */ if (Type(p) == CELL) { /* fanout over descendents */ for (q = More(p); q != Next(p); q = Next(q)) { /* loop over all subcells */ for (k = 0; k < NDIM; k++) /* locate each's midpoint */ nmid[k] = pmid[k] + (Pos(q)[k] < pmid[k] ? - poff : poff); walktree(nptr, np, cptr, bptr, q, psize / 2, nmid); /* recurse on subcell */ } } else { /* extend virtual tree */ for (k = 0; k < NDIM; k++) /* locate next midpoint */ nmid[k] = pmid[k] + (Pos(p)[k] < pmid[k] ? - poff : poff); walktree(nptr, np, cptr, bptr, p, psize / 2, nmid); /* and search next level */ } } Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 50 nằm trong khai báo task về mặt lý thuyết sẽ được xếp vào hàng đợi. Hàng đợi sẽ kết thúc khi tất cả các công việc trên đó đã được hoàn thành. Như vậy, với việc sử dụng hàng đợi, hàm walktree có thể được chỉnh sửa lại như sau: Trong hàm gravcal(), lời gọi hàm walktree sẽ được thêm các chỉ thị taskq và task của OpenMP. Trong hàm walksub gọi đệ quy hàm walktree, do vậy sẽ thêm các chỉ thị của OpenMP vào hàm walksub như sau: void gravcalc(void) { ………. ………. active[0] = (nodeptr) root; /* initialize active list */ CLRV(rmid); /* set center of root cell */ /* Add parallel region */ #pragma omp parallel { #pragma intel omp taskq { #pragma intel omp task { walktree(active, active + 1, interact, interact + actlen, (nodeptr) root, rsize, rmid); /* scan tree, update forces */ } } } /* end of parallel region */ cpuforce = cputime() - cpustart; /* store CPU time w/o alloc */ free(active); free(interact); } Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 51 Khi biên dịch chương trình, các chỉ thị của OpenMP sẽ được thực hiện song song. Kết quả thực nghiệm được cho dưới đây. 3.4 Kết quả thực nghiệm Phụ thuộc vào trình biên dịch và cấu hình máy Intel (R) Xeon (TM) với 4 CPU 2.40 GHz, chương trình treecode sau khi thử nghiệm song song với một số chỉ thị của OpenMP sẽ cho thời gian thực hiện các hàm như dưới đây: local void walksub(nodeptr *nptr, nodeptr *np, cellptr cptr, cellptr bptr, nodeptr p, real psize, vector pmid) { …………… if (Type(p) == CELL) { /* fanout over descendents */ /* add parallel region */ #pragma intel omp parallel taskq shared(q) { for (q = More(p); q != Next(p); q = Next(q)) { #pragma intel omp task captureprivate(q) { for (k = 0; k < NDIM; k++) nmid[k] = pmid[k] + (Pos(q)[k] < pmid[k] ? - poff : poff); walktree(nptr, np, cptr, bptr, q, psize / 2, nmid); } } } /* end of parallel region */ } else { for (k = 0; k < NDIM; k++) nmid[k] = pmid[k] + (Pos(p)[k] < pmid[k] ? - poff : poff); walktree(nptr, np, cptr, bptr, p, psize / 2, nmid); } } Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 52 Như vậy, tùy thuộc vào từng trình biên dịch trên các máy tính có cấu hình khác nhau, kết quả thử nghiệm thu được trên máy đa xử lý Intel chỉ mang tính chất tương đối. Flat profile: Each sample counts as 0.00195312 seconds. % cumulative self self total time seconds seconds calls ms/call ms/call name 74.84 10.43 10.43 532480 0.02 0.02 sumnode 11.18 11.99 1.56 569962 0.00 0.02 walktree 10.83 13.50 1.51 16013212 0.00 0.00 accept 0.68 13.59 0.09 2466729 0.00 0.00 subindex 0.48 13.66 0.07 266240 0.00 0.00 loadbody 0.29 13.70 0.04 _walksub_202__task4 0.27 13.73 0.04 520 0.07 0.09 hackcofm 0.24 13.77 0.03 266240 0.00 0.04 gravsum 0.22 13.80 0.03 130637 0.00 0.00 _walksub_199__taskq3 0 20 13 82 0 03 65 0 42 0 42 diagnostics Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 53 KẾT LUẬN Kết quả đạt được Sau một thời gian tìm hiểu, nghiên cứu và đánh giá, tôi nhận thấy thuật toán Barnes-Hut và các cải tiến của nó đã góp phần quan trọng khi giải quyết bài toán N-body, với độ phức tạp chỉ là O (N log N). Cũng qua tìm hiểu, tôi thấy OpenMP là một giao diện lập trình ứng dụng song song đơn giản và dễ sử dụng. Nó cung cấp cho người dùng một giao diện mềm dẻo, có tính khả chuyển cao trong khi xây dựng và phát triển các ứng dụng song song trên các kiến trúc máy tính bộ nhớ chia sẻ. Việc cài đặt và thử nghiệm cải tiến của thuật toán Barnes-Hut trên các máy đa xử lý Intel và IBM cũng giúp cho tôi có những kinh nghiệm và thu được một số kết quả thực nghiệm. Để qua đó tôi phân tích và thấy được một số khó khăn khi tiến hành song song hóa. Tuy kết quả thực nghiệm đạt được chưa cao, song qua tìm hiểu tôi đã học hỏi được kinh nghiệm và nâng cao vốn hiểu biết của mình về tính toán hiệu năng cao trên các máy đa xử lý, cũng như kinh nghiệm về sử dụng hệ điều hành Linux. Hướng phát triển Do điều kiện về thời gian nghiên cứu và điều kiện về phần cứng, nên tôi mới chỉ tìm hiểu và tiến hành thử nghiệm song song hóa trên máy đa xử lý Intel. Hướng nghiên cứu tiếp theo của tôi là tiếp tục tìm hiểu, thử nghiệm và tối ưu thuật toán treecode bằng cách tiến hành song song hóa trên máy IBM, cũng như tiến hành song song hóa thuật toán trên các máy đa xử lý kết hợp giữa bộ nhớ chia sẻ và bộ nhớ phân tán. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 54 TÀI LIỆU THAM KHẢO [1] Josh Barnes & Piet Hut, A hierarchical O(N log N) force – calculation algorithm, Nature, v. 324, December 1986. [2] Fast Hierarchical Methods for the N-body Problem, Part 1 [3] J. E. Barnes, A modified tree code: Don't laugh; It runs, Journal of Computational Physics 87 (1990) 161--170. [4] A. Kawai, J. Makino, High-accuracy treecode based on pseudoparticle multipole method, Proceedings of the 208th Symposium of the International Astronomical Union (Tokyo, Japan, July 10-13, 2001) 305-314. [5] A. Kawai, J. Makino, Pseudo-particle multipole method: A simple method to implement a high-accuracy treecode, The Astrophysical Journal, 550 (2001) L143-L146. [6] A. Kawai, J. Makino, T. Ebisuzaki, Performance analysis of high-accuracy tree code based on the pseudoparticle multipole method, The Astrophysical Journal Supplement 151 (2004) 13-33. [7] Joshua E. Barnes, Institute for Astronomy, University of Hawaii, Treecode Guide [8] Giovanni Erbacci, Shared Memory Paradigm, High Performance Systems Department, CINECA [9] Introduction to OpenMP, Technical User Support, Supercomputing Institute, University of Minnesota [10] OpenMP exercise [11] Michael Süß, Claudia Leopold, A User's Experience with Parallel Sorting and OpenMP, Talk at the EWOMP'04 conference, Stockholm Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 55 [12] Dieter an Mey, Two OpenMP Programming Patterns, Center for Computing and Communication, Aachen University [13] Paul Graham, Edinburgh Parallel Computing Centre, The university of Edinburgh, OpenMP A Parallel Programming Model for Shared Memory Architectures,March 1999, version 1.1