A fast wavelet based implementation to calculate coulomb potentials on the Cell/B.E.
A. Schiller, G. Sutmann, L. Yang.
HPCC '08. 10th IEEE International Conference on High Performance Computing and Communications, 2008., IEEE Computer Society, Dalian, China, 162-168, (2008)
The calculation of long range interactions is a computationally demanding task in particle based simulations. To reduce the computational complexity from O(N2) to O(N) an algorithm based on a fast 2d-Wavelet transform technique was developed. In this algorithm, a CPU and memory demanding part is to construct the 2d-Wavelet transform of a grid based inverse distance matrix. The 2d-Wavelet transform is thereby calculated via a triple-matrix-multiply and threshold procedure, which results in a sparse representation in Wavelet space. To accelerate the calculation of the triple matrix multiplication, the capabilities of the heterogeneous multicore processor Cell Broadband Engine (Cell/B.E.) are explored. An efficient implementation of the Wavelet transform is developed by considering the architectural requirements of Cell/B.E. Via this implementation, the difficulties and problems in porting code to Cell/B.E. and using sparse linear algebra operations on the processor are assessed.
Keyword(s): cell broadband engine; long range interactions; molecular dynamics; wavelet transform