How will the fast-multipole method fare in the exascale era?
Roofline model of current hardware and computational intensity of various representative algorithms.
SIAM News (Vol. 46, issue 6) has published on the front page our piece about the future of algorithms in the exascale era. This piece was written by invitation on the aftermath of a very successful SIAM Conference on Computational Science and Engineering, held in Boston last February. At this conference several minisymposia focused on the topics of integral-equation methods and fast-multipole algorithms.
The main question we address in this article is this: as hardware continues to evolve, will the fast multipole method soon become bandwidth-bound? In general, a conflict exists between algorithmic complexity and arithmetic intensity—algorithms that scale favorably with problem size tend to be low in arithmetic intensity, while high-intensity algorithms scale poorly—, but the FMM is an exception. This algorithm offers the optimal O(N) scaling while at the same time being arithmetically intense. But as machine balance declines, with memory bandwidth increasing more slowly than computing power, even the FMM could soon be crouching under the performance roofline. What happens then?
Link