Cargando…

Hierarchical algorithms on hierarchical architectures

A traditional goal of algorithmic optimality, squeezing out flops, has been superseded by evolution in architecture. Flops no longer serve as a reasonable proxy for all aspects of complexity. Instead, algorithms must now squeeze memory, data transfers, and synchronizations, while extra flops on loca...

Descripción completa

Detalles Bibliográficos
Autores principales: Keyes, D. E., Ltaief, H., Turkiyyah, G.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: The Royal Society Publishing 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7015294/
https://www.ncbi.nlm.nih.gov/pubmed/31955677
http://dx.doi.org/10.1098/rsta.2019.0055
_version_ 1783496781314654208
author Keyes, D. E.
Ltaief, H.
Turkiyyah, G.
author_facet Keyes, D. E.
Ltaief, H.
Turkiyyah, G.
author_sort Keyes, D. E.
collection PubMed
description A traditional goal of algorithmic optimality, squeezing out flops, has been superseded by evolution in architecture. Flops no longer serve as a reasonable proxy for all aspects of complexity. Instead, algorithms must now squeeze memory, data transfers, and synchronizations, while extra flops 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 for a wide class of formally dense linear 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 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. They 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 the algorithm. We describe modules of a software toolkit, hierarchical computations on manycore architectures, that illustrate these features and are intended as building blocks of applications, such as matrix-free higher-order methods in optimization and large-scale spatial statistics. Some modules of this open-source project have been adopted in the software libraries of major vendors. This article is part of a discussion meeting issue ‘Numerical algorithms for high-performance computational science’.
format Online
Article
Text
id pubmed-7015294
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher The Royal Society Publishing
record_format MEDLINE/PubMed
spelling pubmed-70152942020-02-18 Hierarchical algorithms on hierarchical architectures Keyes, D. E. Ltaief, H. Turkiyyah, G. Philos Trans A Math Phys Eng Sci Articles A traditional goal of algorithmic optimality, squeezing out flops, has been superseded by evolution in architecture. Flops no longer serve as a reasonable proxy for all aspects of complexity. Instead, algorithms must now squeeze memory, data transfers, and synchronizations, while extra flops 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 for a wide class of formally dense linear 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 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. They 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 the algorithm. We describe modules of a software toolkit, hierarchical computations on manycore architectures, that illustrate these features and are intended as building blocks of applications, such as matrix-free higher-order methods in optimization and large-scale spatial statistics. Some modules of this open-source project have been adopted in the software libraries of major vendors. This article is part of a discussion meeting issue ‘Numerical algorithms for high-performance computational science’. The Royal Society Publishing 2020-03-06 2020-01-20 /pmc/articles/PMC7015294/ /pubmed/31955677 http://dx.doi.org/10.1098/rsta.2019.0055 Text en © 2020 The Authors. http://creativecommons.org/licenses/by/4.0/ Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/, which permits unrestricted use, provided the original author and source are credited.
spellingShingle Articles
Keyes, D. E.
Ltaief, H.
Turkiyyah, G.
Hierarchical algorithms on hierarchical architectures
title Hierarchical algorithms on hierarchical architectures
title_full Hierarchical algorithms on hierarchical architectures
title_fullStr Hierarchical algorithms on hierarchical architectures
title_full_unstemmed Hierarchical algorithms on hierarchical architectures
title_short Hierarchical algorithms on hierarchical architectures
title_sort hierarchical algorithms on hierarchical architectures
topic Articles
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7015294/
https://www.ncbi.nlm.nih.gov/pubmed/31955677
http://dx.doi.org/10.1098/rsta.2019.0055
work_keys_str_mv AT keyesde hierarchicalalgorithmsonhierarchicalarchitectures
AT ltaiefh hierarchicalalgorithmsonhierarchicalarchitectures
AT turkiyyahg hierarchicalalgorithmsonhierarchicalarchitectures