Xây dựng cây bát phân dựa trên đường cong lấp đầy không gian với bộ xử lý đồ họa GPU
Main Article Content
Abstract
Tóm tắt. Cây bát phân (octree) là một cấu trúc dữ liệu có nhiều ứng dụng trong các lĩnh vực như đồ họa máy tính, mô phỏng và mô hình hóa. Trong mô phỏng động lực phân tử và mô phỏng N-body, cây bát phân được sử dụng nhiều với các thuật toán phân cấp như tree, khai triển đa cực nhanh FMM (fast multipole method) để tính lực tương tác xa. Có nhiều phương pháp và cấu trúc dữ liệu có thể sử dụng để xây dựng cây bát phân. Trong bài báo này, chúng tôi sử dụng đường cong lấp đầy không gian SFC (space-filling curve) để xây dựng cây bát phân và song song hóa thuật toán xây dựng cây trên bộ xử lý đồ họa GPU. Kết quả thực nghiệm trên máy tính Acer 5745G với bộ xử lý Intel Core i3 2.13 GHz, 4GB RAM được trang bị bộ xử lý đồ họa GeForce 310M và máy tính để bàn với CPU Dual-Core AMD Opteron 2216 HE 1.0 GHz, 2GB RAM, được trang bị bộ xử lý đồ họa nVidia GeForce 8800 GT cho thấy, thuật toán song song do chúng tôi cài đặt trên GPU có tốc độ thực hiện nhanh hơn thuật toán tuần tự trên CPU từ 2.1 đến 7 lần đối với các hệ có từ 220 đến 10.220 phân tử. Đồng thời, mức độ tăng tốc của thuật toán song song xây dựng cây bát phân phụ thuộc vào hai yếu tố chính, đó là tốc độ truyền dữ liệu giữa máy tính với GPU và tốc độ thực hiện thuật toán sắp xếp các phân tử theo khóa Morton trên GPU.
Từ khóa: cây bát phân (octree), FMM, treecode, mô phỏng động lực phân tử, mô phỏng N-body, GPU.References
[2] C. R. Anderson, An implementation of the fast multipole method without multipoles, SIAM J. Sci. Stat. Comput. 13 (4) (1992) 923–947.
[3] L.Greengard, V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics 73 (1987) 325–348.
[4] L. Greengard, V. Rokhlin, A new version of the fast multipole method for the Laplace equation in three dimensions, Acta Numerica 6 (1997) 229–269.
[5] Appel, An efficient program for many-body simulation, SIAM J. Sci. Stat. Comput. 6 (1) (1985), 85–103.
[6] J. E. Barnes, A modified tree code: Don’t laugh; It runs, Journal of Computational Physics 87 (1990) 161–170.
[7] J. E. Barnes, P. Hut, A hierarchical O(N logN) force-calculation algorithm, Nature 324 (1986) 446–449.
[8] D. Sugimoto, Y. Chikada, J. Makino, T. Ito, T. Ebisuzaki, M. Umemura, A special-purpose computer for gravitational many-body problems, Nature 345 (1990) 33–35.
[9] J. Makino, M. Taiji, Scientific Simulations with Special-Purpose Computers - The GRAPE Systems (Chichester: John Wiley and Sons, 1998).
[10] J. Makino, Yet another fast multipole method without multipoles - P2M2 multipole method, Journal of Computational Physics 151(1999) 910-920.
[11] L. Ying, G. Biros, D. Zorin. A kernel-independent adaptive fast multipole method in two and three dimensions, Journal of Computational Physics 196(2004) 591-626.
[12] http://www.nvidia.com
[13] J. Sanders, E. Kandrot, CUDA by examples – An introduction to general-purpose GPU programming, Addison-Wesley, 2011.
[14] Wen-Mei W. Hwu ed., GPU computing gems, Emerald edition, Morgan-Kaufmann, 2011.
[15] http://www.amd.com
[16] Hans Sagan, Space-filling curves, Springer-Verlag, 1994
[17] N. H. Chau, A. Kawai, T. Ebisuzaki, Implementation of fast multipole algorithm on specialpurpose computer MDGRAPE-2, Proceedings of the 6th World Multiconference on Systemics, Cybernetics and Informatics SCI2002, (Orlando, Colorado, USA, July 14-18, 2002), 477–481.
[18] N. H. Chau, A. Kawai, T. Ebisuzaki, Special-purpose computer accelerated fast multipole method, Journal of Computer Science and Cybernetics, 23 (3), (2007) 231-239.
[19] N. H. Chau, A. Kawai, T. Ebisuzaki, Acceleration of fast multipole method using special-purpose computer GRAPE, International Journal of High Performance Computing Applications, 22 (2)(2008)194-205.
[20] http://developer.nvidia.com/cuda-toolkit-40
[21] http://atlas.riken.jp
[22] http://www.riken.jp