The ECRC IPCC at KAUST will focus on optimizing two types of scalable hierarchical algorithms -- fast multipole methods (FMM) and H-matrices -- on next generation Xeon processors and Xeon Phi coprocessors. These algorithms have the potential of replacing "workhorse" kernels of molecular dynamics codes (drug/material design), sparse matrix preconditioners (structural/fluid dynamics), and covariance matrix calculations (statistics/big data) due to their following exascalable features. FMM and H-matrices share a rare combination of O(N) arithmetic complexity and high arithmetic intensity (flops/Byte). This is in contrast to traditional methods that have either low arithmetic complexity with low arithmetic intensity (FFT, sparse linear algebra, and stencil), or high arithmetic intensity with high arithmetic complexity (dense linear algebra, direct N-body). In short, FMM and H-matrices are efficient algorithms that will remain compute-bound on future architectures. Furthermore, these methods have a communication complexity of O(log P) for P processors, and permit high asynchronicity in their communication. This endows them with overall performance robustness without requiring all components of the computing infrastructure to be performance robust, e.g., to allow improved energy efficiency. Therefore, they are amenable to asynchronous programming models that have been gaining popularity.
Principal Research Scientist, Extreme Computing Research Center