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 i TÓM TẮT KHÓA LUẬN Song song hóa là một giải pháp quan trọng được áp dụng khi giải quyết các vấn đề đòi hỏi phải tính toán lớn thường gặp trong các lĩnh vực khoa học cơ bản…Bài toán N- body là một trong những bài toán cơ bản trong lĩnh vực vật lý học thiên thể, liên quan tới lực tương tác giữa các hạt với nhau trong không gian. Có rất nhiều hướng để giải quyết bài toán trên, trong đó có phương pháp sử dụng thuật toán Barnes-Hut. OpenMP là giao diện lập trình ứng dụng API, cung cấp cho người lập trình một giao diện mềm dẻo, có tính khả chuyển trong khi phát triển các ứng dụng song song trên các máy tính sử dụng kiến trúc bộ nhớ chia sẻ. Khóa luận này giới thiệu tổng quan về bài toán N-body, thuật toán Barnes-Hut và giao diện lập trình ứng dụng OpenMP. Trên cơ sở đó đánh giá hiệu năng thuật toán Barnes-Hut, tiến hành tìm hiểu, phân tích và đề xuất các phương thức 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 ii LỜI CẢM ƠN Đầu tiên, em muốn gửi lời cảm ơn sâu sắc nhất tới TS. Nguyễn Hải Châu, người đã hướng dẫn và chỉ bảo em tận tình trong suốt thời gian làm khóa luận. Em xin chân thành cảm ơn thầy Phạm Kỳ Anh, giám đốc Trung tâm Tính toán hiệu năng cao – Trường Đại học KHTN – Đại học Quốc gia Hà Nội, người đã tạo điều kiện tốt nhất cho em thực hành và thử nghiệm thuật toán. Em cũng xin gửi lời cảm ơn tới tất cả các thầy và các anh chị trong Trung tâm, những người đã giúp đỡ và trả lời mọi thắc mắc, tạo điều kiện cho em hoàn thành khóa luận. Em xin cảm ơn thầy Đoàn Minh Phương, giảng viên bộ môn Mạng và Truyền thông máy tính, khoa CNTT, trường Đại học Công nghệ, người đã giúp đỡ em thử nghiệm bài toán trên máy đa xử lý Intel. Cuối cùng, em xin gửi lời cảm ơn sâu sắc tới những người thân trong gia đình em, những người luôn quan tâm, động viên khích lệ em trong học tập và trong cuộc sống. Sinh viên thực hiện khóa luận Lê Thị Lan Phương Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương iii Danh sách hình vẽ Hình 1: Minh họa hệ N-body trong không gian ..............................................................2 Hình 2: Biểu diễn lực tổng hợp tác dụng lên 1 hạt ..........................................................4 Hình 3: Quan sát thiên hà Andromeda từ trái đất..........................................................6 Hình 4: Biểu diễn quá trình đệ quy thay thế một cụm bởi tâm điểm............................7 Hình 5: Cây Quadtree với 4 mức ......................................................................................8 Hình 6: Cây Octree với 2 mức...........................................................................................8 Hình 7: Biểu diễn cây sau khi loại bỏ các ô trống ...........................................................9 Hình 8: Các thành phần trong OpenMP........................................................................15 Hình 9: Kiến trúc bộ nhớ chia sẻ ....................................................................................16 Hình 10: Mô hình Fork-Join ...........................................................................................19 Hình 11: Minh họa vùng được song song hóa................................................................21 Hình 12: Hình minh họa chỉ thị Do/for ..........................................................................24 Hình 13: Hình minh họa chỉ thị sections ........................................................................26 Hình 14: Hình minh họa chỉ thị single............................................................................28 Hình 15: Cấu trúc dữ liệu cây trong treecode (1)..........................................................36 Hình 16: Cấu trúc dữ liệu cây trong treecode (2)..........................................................39 Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương iv Bảng từ viết tắt Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh Giao diện lập trình ứng dụng API Application Program Interface Các chỉ thị mở dành cho đa xử lý OpenMP Open Specifications for Multi Processing Luồng Thread Thread Hạt body Body Ô, Khối cell Cell Nút node Node Giao diện truyền thông điệp MPI Message Passing Interface Tâm khối Center of mass Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương v Mục lục TÓM TẮT KHÓA LUẬN........................................................................................... i LỜI CẢM ƠN ............................................................................................................. ii Danh sách hình vẽ...................................................................................................... iii Bảng từ viết tắt........................................................................................................... iv Mục lục ........................................................................................................................ v MỞ ĐẦU...................................................................................................................... 1 Chương 1: BÀI TOÁN N-BODY VÀ THUẬT TOÁN BARNES-HUT ................ 2 1.1 Bài toán N-body .......................................................................................... 2 1.1.1 Giới thiệu bài toán N-body............................................................ 2 1.1.2 Phương pháp nhằm tăng tốc bài toán N-body............................... 5 1.1.3 Cấu trúc cây Quadtree và Octree................................................... 7 1.2 Thuật toán Barnes-Hut ................................................................................ 9 1.2.1 Mô tả thuật toán Barnes-Hut ....................................................... 10 Chương 2: GIỚI THIỆU VỀ OPENMP................................................................. 15 2.1 OpenMP (Open specifications for Multi Processing) ............................... 15 2.2 Kiến trúc bộ nhớ chia sẻ ............................................................................ 16 2.3 Mục tiêu của OpenMP............................................................................... 17 2.4 Môi trường hỗ trợ OpenMP....................................................................... 18 2.5 Mô hình lập trình OpenMP ....................................................................... 18 2.6 Một số chỉ thị cơ bản trong OpenMP ........................................................ 19 2.6.1 Các chỉ thị song song hóa............................................................ 20 2.6.2 Chỉ thị khai báo miền song song ................................................. 20 2.6.3 Chỉ thị liên quan tới môi trường dữ liệu...................................... 21 2.6.4 Chỉ thị liên quan tới chia sẻ công việc ........................................ 23 2.6.5 Chỉ thị đồng bộ hóa ..................................................................... 28 2.6.6 Thư viện và một số biến môi trường........................................... 31 Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương vi 2.7 Ví dụ về lập trình song song với OpenMP................................................ 33 2.7.1 omp_hello.c ................................................................................. 33 2.7.2 Cách biên dịch............................................................................. 33 2.7.3 Kết quả ........................................................................................ 34 Chương 3: SONG SONG HÓA THUẬT TOÁN BARNES-HUT ........................ 35 3.1 Treecode .................................................................................................... 35 3.1.1 Cấu trúc dữ liệu của cây .............................................................. 35 3.1.2 Các biến toàn cục ........................................................................ 39 3.2 Thử nghiệm và đánh giá hiệu năng của treecode ...................................... 40 3.2.1 Thử nghiệm chương trình treecode ............................................. 40 3.2.2 Đánh giá hiệu năng...................................................................... 42 3.3 Song song hóa treecode với OpenMP ....................................................... 43 3.3.1 Môi trường thực hiện song song ................................................. 43 3.3.2 Thực hiện song song.................................................................... 44 3.4 Kết quả thực nghiệm ................................................................................. 51 KẾT LUẬN ............................................................................................................... 53 TÀI LIỆU THAM KHẢO........................................................................................ 54 Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 1 MỞ ĐẦU Bài toán N-body là một trong những bài toán cơ bản của vật lý học thiên thể. Trước đây đã có rất nhiều hướng khác nhau khi giải quyết vấn đề liên quan tới lực tương tác giữa các hạt của hệ N hạt trong không gian. Trong đó có hai cách giải quyết cơ bản. Đó là tính trực tiếp lực giữa các cặp hạt với độ phức tạp là O (N2) và cách tính thế năng lặp với độ phức tạp là O (N log N). Cách thứ nhất cho phép tính toán một cách gần chính xác lực tương tác. Song thời gian cần để thực hiện trong bài toán N-body là rất lớn, xấp xỉ O (N2) với N là số hạt. Trong đó thời gian tính lực chiếm chủ yếu, khoảng 96 % thời gian thực hiện chương trình khi được thử nghiệm trên máy Intel 1 CPU. Cách thứ hai dường như giảm thiểu thời gian tính toán nhưng lại thiếu độ chính xác và thiếu tính tổng quát khi mô phỏng hệ N-body. Thuật toán Barnes-Hut và các cải tiến của nó đã được áp dụng để tính lực với độ phức tạp xấp xỉ O (N log N) và cho kết quả tương đối chính xác. Song song hóa thuật toán Barnes-Hut có ý nghĩa vô cùng quan trọng trong việc tăng tốc bài toán N-body. Song song hóa thuật toán Barnes-Hut trên kiến trúc máy tính có bộ nhớ phân tán bằng cách sử dụng giao diện lập trình ứng dụng MPI đã được nhiều tác giả nghiên cứu và đạt kết quả tốt. Tuy nhiên vấn đề song song hóa thuật toán này trên kiến trúc máy tính đa xử lý bộ nhớ chia sẻ chưa được nghiên cứu nhiều. OpenMP là một trong các giao diện lập trình ứng dụng dành cho các ứng dụng song song trên kiến trúc máy tính đa xử lý bộ nhớ chia sẻ. So với MPI, OpenMP có tính mềm dẻo, tính khả chuyển cao, và cho phép người lập trình có được một giao diện đơn giản khi xây dựng và phát triển các ứng dụng song song. Khóa luận này nghiên cứu tổng quan về bài toán N-body, tìm hiểu về thuật toán Barnes-Hut cũng như về giao diện lập trình OpenMP. Từ đó rút ra những nhận xét và đánh giá hiệu năng thuật toán và nghiên cứu vấn đề song song hóa thuật toán Barnes-Hut sử dụng OpenMP trên mô hình bộ nhớ chia sẻ. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 2 Chương 1: BÀI TOÁN N-BODY VÀ THUẬT TOÁN BARNES-HUT 1.1 Bài toán N-body 1.1.1 Giới thiệu bài toán N-body Bài toán N-body về thực chất là bài toán liên quan tới tính lực tương tác giữa các hạt trong không gian. Các mô phỏng của bài toán N-body đóng vai trò quan trọng trong nhiều ứng dụng của vật lý học thiên thể, động lực học phân tử, và các phương pháp tính lưu lượng của gió xoáy (vortex flow methods)… Xét hệ N hạt trong không gian. Giữa các hạt có tương tác lực hấp dẫn. Vì có N hạt, nên mỗi hạt sẽ chịu tác dụng của N-1 lực khác nhau gây ra bởi các hạt còn lại, lực tổng hợp của N-1 lực này sẽ làm thay đổi vận tốc và vị trí của hạt đó. Hình 1: Minh họa hệ N-body trong không gian Dưới đây là giải thuật cơ bản khi mô phỏng hệ N-body. while (t < tfinal) { Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 3 for i =1 to n do { tính lực f(i) tác dụng lên hạt i cập nhật vận tốc và vị trí của hạt i } t = t + ∆t } Trong đó lực f(i) tác dụng lên hạt i có thể được tính đơn giản như sau: for i = 1 to n f(i) = sum[ j=1,...,n, j!=i] f(i,j) /* f(i,j) la luc cua hat j tac dung len i*/ end for Lực tương tác của các hạt phụ thuộc vào khoảng cách giữa chúng. Bởi vậy, khi hạt chuyển động ta cần phải xác định lại lực tác dụng lên nó. Xét hạt chuyển động dưới tác dụng của lực hấp dẫn. Trong đó: • F là lực hấp dẫn gây ra bởi hai hạt a, b. • G: hằng số hấp dẫn. = (6.6742 ± 0.001) x 10-11 N m2 kg-2 • ma, mb: khối lượng của hạt a, b tương ứng. • d: khoảng cách giữa hai hạt Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 4 Khi đó gia tốc của hạt là: Lực tổng hợp tác dụng lên hạt a là: Fnet Hình 2: Biểu diễn lực tổng hợp tác dụng lên 1 hạt Xét các thời điểm t0, t1, … với khoảng thời gian là δt. Dưới tác dụng của lực Fnet, vận tốc của hạt là: Khi đó vị trí của hạt theo trục x là: Trong không gian 3 chiều, khoảng cách giữa hai hạt a, b là: Lực hấp dẫn chiếu lên trục Ox là: Như vậy, bài toán N-body có thể đơn giản như sau: Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 5 for(t=0;t<tmax;t++){ for(i=0;i<N;i++){ F=Calc_force(i); vnew[i]=v[i]+F*dt/m; xnew[i]=x[i]+v[i]*dt; } for(i=0;i<N;i++){ x[i]=xnew[i]; v[i]=vnew[i]; } } Rõ ràng với N hạt trong không gian, thuật toán tính trực tiếp lực tương tác giữa các cặp hạt sẽ làm cho độ phức tạp của bài toán là O(N2). Vậy làm thế nào để có thể giảm thiểu được thời gian tính toán? 1.1.2 Phương pháp nhằm tăng tốc bài toán N-body Trước đây, bài toán N-body đã được mô hình hoá bằng cách tích hợp trực tiếp, trong đó ta tính lực tương tác theo từng cặp hạt, giống như mô tả ở phần trên. Cách này đã mô tả gần chính xác trạng thái động lực học của hệ N hạt nhưng độ phức tạp là O(N2). Cũng có thể mô phỏng hạt bằng phương pháp thế năng lặp, độ phức tạp chỉ còn là O(NlogN) nhưng lại thiếu tính chính xác và thiếu tính tổng quát của bài toán. Như vậy vấn đề đặt ra là làm thế nào vừa giảm thiểu độ phức tạp của thuật toán nhưng lại mô phỏng được một cách tương đối chính xác và có tính tổng quát của hệ thống N hạt trong không gian? Ta xét một ví dụ thực tế dưới đây. Giả sử cần phải tính lực hấp dẫn của trái đất tác dụng lên các vì sao và các hành tinh. Quan sát bằng mắt thường, ta thấy nhiều điểm sáng trông giống như là một ngôi sao đơn lẻ, nhưng thực chất đó là một chòm sao (Ví dụ chòm sao tinh nữ Andromeda), bao gồm hàng tỉ các vì sao con. Nhưng vì chúng xuất hiện rất gần nhau, nên tưởng như chúng là một điểm sáng đơn. Xét D là kích thước của khối hộp bao quanh chòm sao Andromeda Xét r là khoảng cách từ tâm khối tới trái đất Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 6 Thiết lập tỉ số: D/r = Ta thấy tỉ số D/r là rất nhỏ, do vậy có thể thay thế một cách tương đối chính xác tất cả các vì sao trong chòm sao Andromeda như một điểm x đặt tại tâm của khối. Hình 3: Quan sát thiên hà Andromeda từ trái đất Ý tưởng này đã được các nhà bác học trước phát hiện và áp dụng vào nhiều bài toán. Như trong lý thuyết cơ học cổ điển, khi tính lực hút của trái đất tác dụng lên quả táo đang rơi, Newton đã coi trái đất như là một điểm được đặt tại tâm của trái đất. Điểm mới mẻ ở đây là việc ta áp dụng ý tưởng này một cách đệ quy để giải quyết bài toán N-body. Chẳng hạn khi ta quan sát từ chòm sao tinh nữ Andromeda, dải ngân hà Milky Way có thể được xấp xỉ là một điểm đặt tại tâm dải. Nhưng điều quan trọng hơn là quá trình này có thể được lặp lại nhiều lần miễn là tỉ số khoảng cách D1/r1 là đủ nhỏ để có thể thay thế các vì sao trong một khối nhỏ hơn bằng một điểm đặt tại tâm khối khi tính lực hấp dẫn. Kích thước khối hộp Khoảng cách từ tâm khối tới trái đất Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 7 Hình 4: Biểu diễn quá trình đệ quy thay thế một cụm bởi tâm điểm Để quá trình đệ quy khi chia nhỏ không gian trở nên đơn giản, người ta sử dụng một cấu trúc dữ liệu đặc biệt. Đó là cấu trúc cây Quadtree và Octree. 1.1.3 Cấu trúc cây Quadtree và Octree Cấu trúc cây Quadtree (dùng trong không gian 2 chiều) và Octree (trong không gian 3 chiều) là các cấu trúc dữ liệu được sử dụng để chia nhỏ không gian. Để đơn giản, ta xét mô hình cây Quadtree (tương tự với xây dựng cây Octree). Cây Quadtree bắt đầu bởi một hình vuông trong mặt phẳng. Hình vuông lớn này được chia thành 4 hình vuông nhỏ. Mỗi hình vuông nhỏ lại được chia ra làm 4. Quá trình phân chia này cứ tiếp tục được diễn ra… Hình dưới đây mô tả một cây Quadtree với 4 mức. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 8 Hình 5: Cây Quadtree với 4 mức Mỗi nút (node) của cây tương ứng có 4 con (children), là 4 ô vuông nhỏ vừa mới được tạo thành từ việc phân chia ô vuông lớn hơn trước đó. Với cây Octree, quá trình diễn ra tương tự. Nhưng thay vì mỗi nút có 4 con (như trong Quadtree), mỗi nút của cây Octree có 8 con. Dưới đây là hình mô tả một cây Octree với 2 mức chia. Hình 6: Cây Octree với 2 mức Các lá của cây Quadtree lưu thông tin về vị trí, khối lượng của các hạt tương ứng có trong hộp. Tuy nhiên, nếu như phân bố các hạt trong không gian không đồng đều thì việc phân chia như trên sẽ khiến cho nhiều lá của cây là rỗng. Do vậy, việc lưu trữ các lá rỗng Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 9 như thế rất lãng phí. Để khắc phục tình trạng trên, người ta chỉ tiến hành phân chia các ô vuông chỉ khi chúng có chứa nhiều hơn một hạt. Ta có cấu trúc cây có dạng như sau Hình 7: Biểu diễn cây sau khi loại bỏ các ô trống 1.2 Thuật toán Barnes-Hut Thuật toán Barnes-Hut được giới thiệu lần đầu trong bài báo “A hierachical O(n logn) force caculation algorithm” vào tháng 12/1986. Tuy độ chính xác không bằng thuật toán FMM (Fast Mutipole Method), nhưng tốc độ tính toán lại nhanh hơn. Thuật toán Barnes-Hut được sử dụng khá rộng rãi trong lĩnh vực vật lý học thiên thể. Dựa trên nền tảng mà Barnes-Hut đưa ra, đã có rất nhiều cải tiến và phát triển mới của thuật toán như việc áp dụng tính lực trên các máy tính vector (Barnes 1990), giải thuật Greengard 1990, J. Makino với “Treecode with a special-purpose processor”, Publ. Astron. Soc. Japan 43 (1991) 621--638… Các cải tiến mới này nhằm tăng độ chính xác, tăng tốc độ khi tiến hành song song hóa và có thể cải tiến để cài đặt trên các máy tính chuyên dụng GRAPE. Song song hóa thuật toán Barnes-Hut với OpenMP Lê Thị Lan Phương 10 1.2.1 Mô tả thuật toán Barnes-Hut Thuật toán Barnes-Hut sử dụng chiến thuật chia để trị nhằm tìm ra cụm các hạt trong bài toán N-body. Giả sử tất cả các hạt nằm trong 1 hình khối 3 chiều. Cây octree được xây dựng một cách đệ quy bằng cách chia nhỏ hình khối thành 8 cell nhỏ hơn. Loại bỏ các cell không chứa hạt nào. Lá của cây là các cell chỉ chứa một hạt duy nhất. Quá trình chia nhỏ khối được lặp lại cho đến khi các khối chỉ chứa duy nhất một hạt. Để đơn giản, ta xét thuật toán Barnes-Hut trong không gian 2 chiều dưới đây. Như vậy, thuật toán có thể được mô tả qua 3 bước như sau: Bước 1: Xây dựng cây Quadtree. Bước 2: Đối với mỗi ô vuông của cây, tính tâm khối và tổng khối lượng các hạt có trong cell. Bước 3: Với mỗi hạt, duyệt lại cây để tính lực tác dụng lên nó. Trong đó: Bước 1: Xây dựng cây Quadtree. procedure QuadtreeBuild Quadtree = {empty} For i = 1 to n ... duyệt tất cả các hạt QuadInsert(i, root) ... thêm hạt i vào cây end for …Duyệt cây để loại bỏ những lá trống procedure QuadInsert(i,n) ... thủ tục này để thêm hạt i vào nút n trong cây ... khi xây dựng cây, chú ý mỗi lá trong cây chỉ chứa ... 1 hoặc 0 hạt If cây con có gốc tại n chứa nhiều hơn 1 hạt Lựa chọn con