Matrix-Free Algorithms | Nikhil Kodali

Recent advancements in hardware-aware algorithms for higher-order finite-element (FE) discretized matrix-vector multiplications have shown that on-the-fly matrix-vector products can reduce arithmetic complexity and enhance data access efficiency. These matrix-free approaches exploit the tensor-structured FE polynomial basis for integral evaluations without explicit cell-level matrix construction. While the existing implementations of such algorithms are well-suited for the action of FE-discretized matrices on a single vector, they are not directly applicable to matrix-multivector products involving multiple vectors. To address this limitation, we have proposed a computationally efficient and scalable matrix-free implementation procedure for computing FE-discretized matrix-multivector products on multinode CPU architectures. Our implementation achieves significant speedups of up to 4.4x compared to baseline cell-matrix implementation when utilizing 1024 vectors and FE interpolating polynomial orders ranging from 6 to 8. The observed speedups underscore the potential of our matrix-free implementation to enhance the overall performance of subspace-iteration methods used in solving the Kohn-Sham eigenproblem incorporating non-collinear spin and spin-orbit coupling on multinode CPU and GPU architectures.

References

2023

Under Review
Fast Hardware-Aware Matrix-Free Algorithm for Higher-Order Finite-Element Discretized Matrix Multivector Products on Distributed Systems

Gourab Panigrahi, Nikhil Kodali, Debashis Panda, and 1 more author

Oct 2023

Abs Bib PDF

Recent hardware-aware matrix-free algorithms for higher-order finite-element (FE) discretized matrix-vector multiplications reduce floating point operations and data access costs compared to traditional sparse matrix approaches. This work proposes efficient matrix-free algorithms for evaluating FE discretized matrix-multivector products on both multi-node CPU and GPU architectures. We address a critical gap in existing matrix-free implementations, which are well suited only for the action of FE discretized matrices on a single vector. We employ batched evaluation strategies, with the batchsize tailored to underlying hardware architectures, leading to better data locality and enabling further parallelization. On CPUs, we utilize even-odd decomposition, SIMD vectorization, and overlapping computation and communication strategies. On GPUs, we employ strategies to overlap compute and data movement in conjunction with GPU shared memory, constant memory, and kernel fusion to reduce data accesses. Our implementation outperforms the baselines for Helmholtz operator action, achieving up to 1.4x improvement on one CPU node and up to 2.8x on one GPU node, while reaching up to 4.4x and 1.5x improvement on multiple nodes for CPUs (~ 3000 cores) and GPUs (~ 25 GPUs), respectively. We further benchmark the performance of the proposed implementation for solving a model eigenvalue problem for 1024 smallest eigenvalue-eigenvector pairs by employing the Chebyshev Filtered Subspace Iteration method, achieving up to 1.5x improvement on one CPU node and up to 2.2x on one GPU node while reaching up to 3.0x and 1.4x improvement on multinode CPUs (~ 3000 cores) and GPUs (~ 25 GPUs), respectively.
@misc{panigrahi_fast_2023, address = {Rochester, NY}, type = {{SSRN} {Scholarly} {Paper}}, title = {Fast {Hardware}-{Aware} {Matrix}-{Free} {Algorithm} for {Higher}-{Order} {Finite}-{Element} {Discretized} {Matrix} {Multivector} {Products} on {Distributed} {Systems}}, url = {https://papers.ssrn.com/abstract=4594538}, doi = {10.2139/ssrn.4594538}, language = {en}, urldate = {2023-11-06}, author = {Panigrahi, Gourab and Kodali, Nikhil and Panda, Debashis and Motamarri, Phani}, month = oct, year = {2023}, keywords = {Finite Element Method, Matrix-free, Scalable algorithms for heterogeneous architectures, Sum factorization}, dimensions = {true}, ownpub = {true} }