Data-sparse Methods for Large-scale Applications on Emerging Architectures

Overview

Abstract

A traditional goal of algorithmic optimality, squeezing out operations, has been superseded because of evolution in architecture. Arithmetic operations no longer serve as a reasonable proxy for all aspects of complexity. Instead, algorithms must now squeeze memory, data transfers, and synchronizations, while extra operations on locally cached data represent only small costs in time and energy. Hierarchically low-rank matrices realize a rarely achieved combination of optimal storage complexity and high-computational intensity in approximating a wide class of formally dense operators that arise in applications for which exascale computers are being constructed. They may be regarded as algebraic generalizations of the fast multipole method. Methods based on these hierarchical tree-based data structures and their simpler cousins, tile low-rank matrices, are well proportioned for early exascale computer architectures, which are provisioned for high processing power relative to memory capacity and memory bandwidth. Such data-sparse algorithms are ushering in a renaissance of computational linear algebra. A challenge is that emerging hardware architecture possesses hierarchies of its own that do not generally align with those of a given algorithm-application pair. We describe modules of a KAUST-built software toolkit, Hierarchical Computations on Manycore Architectures (HiCMA), that illustrate these features and are building blocks of KAUST mission applications, such as matrix-free higher-order methods in optimization and large-scale spatial statistics. Early modules of this open-source project have undergone industrial-rigor testing are distributed in the software libraries of major vendors.

Brief Biography

David Keyes directs the Extreme Computing Research Center at the King Abdullah University of Science and Technology (KAUST), where he was the founding Dean of the Division of Mathematical and Computer Sciences and Engineering in 2009 and currently serves in the Office of the President as Senior Associate for strategic priorities and institutional partnerships. 

He works at the interface between parallel computing and partial differential equations and statistics, with a current focus on scalable algorithms exploiting data sparsity. 

Before joining KAUST he led multi-institutional scalable solver software projects in the SciDAC and ASCI programs of the US DOE, ran university collaboration programs at US Department of Energy and NASA academic collaboration institutes, and taught at Columbia, Old Dominion, and Yale Universities. 

He is a Fellow of SIAM, AMS, and AAAS, and has been awarded the ACM Gordon Bell Prize, the IEEE Sidney Fernbach Award, and the SIAM Prize for Distinguished Service to the Profession. 

He earned a BSE in Aerospace and Mechanical Sciences from Princeton in 1978 and a Ph.D. in Applied Mathematics from Harvard in 1984.