Computing Petaflops over Terabytes of Data

DOI10.1145/2560421MaRDI QIDQ5270698zbMATH OpenOpenAlexWikidataFDO

Authors Diego Fabregat-Traver, Paolo Bientinesi

Publication date 30 June 2017

Published in ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.7683

zbMATH Keywords

algorithmcomputational biologycomputational complexityGenome-Wide Association Studiesleast squares problemsmultiple instances of problemsnumerical linear algebraout-of-coreshared-memory

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Complexity and performance of numerical algorithms (65Y20) Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10)

Abstract: In many scientific and engineering applications, one has to solve not one but a sequence of instances of the same problem. Often times, the problems in the sequence are linked in a way that allows intermediate results to be reused. A characteristic example for this class of applications is given by the Genome-Wide Association Studies (GWAS), a widely spread tool in computational biology. GWAS entails the solution of up to trillions ($10^{12}$) of correlated generalized least-squares problems, posing a daunting challenge: the performance of petaflops ($10^{15}$ floating-point operations) over terabytes of data. In this paper, we design an algorithm for performing GWAS on multi-core architectures. This is accomplished in three steps. First, we show how to exploit the relation among successive problems, thus reducing the overall computational complexity. Then, through an analysis of the required data transfers, we identify how to eliminate any overhead due to input/output operations. Finally, we study how to decompose computation into tasks to be distributed among the available cores, to attain high performance and scalability. With our algorithm, a GWAS that currently requires the use of a supercomputer may now be performed in matter of hours on a single multi-core node. The discussion centers around the methodology to develop the algorithm rather than the specific application. We believe the paper contributes valuable guidelines of general applicability for computational scientists on how to develop and optimize numerical algorithms.

Recommendations

• Identifying candidate disease genes with high-performance computing
• Large scale bioinformatics data mining with parallel genetic programming on graphics processing units
• Parallel extraction of association rules from genomics data

Cites work

• A set of level 3 basic linear algebra subprograms
• Correlations in sequences of generalized eigenproblems arising in density functional theory
• Fast Numerically Stable Computations for Generalized Linear Least Squares Problems
• scientific article; zbMATH DE number 1424322 (Why is no real title available?)
• LAPACK Users' Guide
• Reducing the I/O Volume in Sparse Out-of-core Multifrontal Methods
• ScaLAPACK Users' Guide
• Solving sequences of generalized least-squares problems on multi-threaded architectures
• Solving systems of large dense linear equations
• Sparse direct factorizations through unassembled hyper-matrices

Cited in

(2)

• Solving sequences of generalized least-squares problems on multi-threaded architectures
• Large-scale linear regression: development of high-performance routines

Describes a project that uses

Uses Software

• LAPACK
• BLAS
• GenABEL
• ProbABEL
• ScaLAPACK

This page was built for publication: Computing Petaflops over Terabytes of Data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5270698)