tailieunhanh - Special - Purpose computer accelerated fast multipole method

Bài báo trình bày phương pháp cài đặt và tăng tốc thuật toán khai triển đa cực nhanh trên máy tính chuyên dụng GRAPE. FMM là thuật toán tính lực tương tác trong hệ N-Chất điểm với độ phức tạp tính toán tuyến tính. nội dung chi tiết. | Tạp chí Tin học và Điều khiển học 2007 231--239 SPECIAL-PURPOSE COMPUTER ACCELERATED FAST MULTIPOLE METHOD NGUYEN HAI CHAU1 ATSUSHI KAWAI2 TOSHIKAZU EBISUZAKI3 1 College of Technology Vietnam National University Hanoi. Email chaunh.@. edu. vn 2 Saitama Institute of Technology Saitama Japan. Email kawai@ 3 Advanced Computing Center Institute of Physical and Chemical Research RIKEN Saitama Japan. Email ebisu@ Abstract. This paper presents the implementation of fast multipole algorithm FMM on a specialpurpose computer GRAPE GRAvity PipE . FMM is one of the fastest algorithms for the calculation of interaction force in a 7V-particle system. The FMM s computational complexity is O N . GRAPE is a special-purpose computer dedicated for the calculation of Coulombic or gravitational force. Its calculation speed is 100-1000 times faster than commodity PC computers at the same cost. However GRAPE is not able to calculate FMM s multipole expansions. We have found new formulae to express multipole expansions so that they are calculable on GRAPE. Consequently we successfully accelerated FMM using GRAPE. Our numerical experiments show that for close-to-uniform distribution of particle systems GRAPE accelerates the FMM by a factor of 3 to 60 for low and high accuracy respectively. Tóm tat. Bài báo này trình bày phuong pháp cài đặt và tăng tốc thuật toán khai triển đa cực nhanh FMM trên máy tính chuyên dụng GRAPE. FMM là thuật toán tính lực tuơng tác trong hệ IV-chất điểm với độ phức tạp tính toán tuyến tính. GRAPE là một họ máy tính chuyên dụng dành để tính lục tuong tác tĩnh điện Culông hoặc lực hấp dẫn với tốc độ cao hon các máy PC thông thuờng từ 100 đến 1000 lần. Tuy nhiên GRAPE không thể trực tiếp tính đuợc các biểu thức khai triển đa cực của FMM. Chúng tôi đã tìm ra các công thức mới biểu diễn các khai triển đa cực để có thể thục hiện đuọc trên GRAPE và cài đặt thành công thuật toán FMM trên máy tính chuyên dụng GRAPE. Kết quả thực nghiệm của