M2L Translation Operators for Kernel Independent Fast Multipole Methods on Modern Architectures
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909625662570496 |
|---|---|
| author | Kailasa, Srinath Betcke, Timo Kazdadi, Sarah El |
| author_facet | Kailasa, Srinath Betcke, Timo Kazdadi, Sarah El |
| contents | Hardware trends favor algorithm designs that maximize data reuse per FLOP. We develop and benchmark high-performance Multipole-to-Local (M2L) translation operators for the kernel-independent Fast Multipole Method (kiFMM), a widely adopted FMM variant that supports a broad class of kernels and has been favored by recent implementations for its simple specification. Naively implemented, M2L is bandwidth-limited and therefore a key bottleneck in the FMM. State-of-the-art FFT-based M2L implementations, though elegant and with a fast setup time, suffer from low operational intensity and require architecture-specific optimizations. We demonstrate that a BLAS-based M2L, combined with randomized low-rank compression, achieves competitive performance with greater portability and a simpler implementation leveraging existing BLAS infrastructure, at the cost of higher setup times-especially for high-accuracy settings in double precision. Our Rust-based implementation enables seamless switching between strategies for fair benchmarking. Results on CPUs show that FFT-based M2L is favorable in low-accuracy settings or dynamic particle simulations, while BLAS-based M2L is favored for high-accuracy settings for static particle distributions, where its higher setup costs are amortized in many practical applications of the FMM. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07436 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | M2L Translation Operators for Kernel Independent Fast Multipole Methods on Modern Architectures Kailasa, Srinath Betcke, Timo Kazdadi, Sarah El Computational Engineering, Finance, and Science 65-04, 65Y05, 65Y10, 65Y15, 65Y20 Hardware trends favor algorithm designs that maximize data reuse per FLOP. We develop and benchmark high-performance Multipole-to-Local (M2L) translation operators for the kernel-independent Fast Multipole Method (kiFMM), a widely adopted FMM variant that supports a broad class of kernels and has been favored by recent implementations for its simple specification. Naively implemented, M2L is bandwidth-limited and therefore a key bottleneck in the FMM. State-of-the-art FFT-based M2L implementations, though elegant and with a fast setup time, suffer from low operational intensity and require architecture-specific optimizations. We demonstrate that a BLAS-based M2L, combined with randomized low-rank compression, achieves competitive performance with greater portability and a simpler implementation leveraging existing BLAS infrastructure, at the cost of higher setup times-especially for high-accuracy settings in double precision. Our Rust-based implementation enables seamless switching between strategies for fair benchmarking. Results on CPUs show that FFT-based M2L is favorable in low-accuracy settings or dynamic particle simulations, while BLAS-based M2L is favored for high-accuracy settings for static particle distributions, where its higher setup costs are amortized in many practical applications of the FMM. |
| title | M2L Translation Operators for Kernel Independent Fast Multipole Methods on Modern Architectures |
| topic | Computational Engineering, Finance, and Science 65-04, 65Y05, 65Y10, 65Y15, 65Y20 |
| url | https://arxiv.org/abs/2408.07436 |