Two-stage tridiagonal reduction for dense symmetric matrices using tile algorithms on multicore architectures

Piotr Luszczek*, Hatem Ltaief, Jack Dongarra

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

28 Scopus citations

Abstract

While successful implementations have already been written for one-sided transformations (e.g., QR, LU and Cholesky factorizations) on multicore architecture, getting high performance for two-sided reductions (e.g., Hessenberg, tridiagonal and bidiagonal reductions) is still an open and difficult research problem due to expensive memory-bound operations occurring during the panel factorization. The processor-memory speed gap continues to widen, which has even further exacerbated the problem. This paper focuses on an efficient implementation of the tridiagonal reduction, which is the first algorithmic step toward computing the spectral decomposition of a dense symmetric matrix. The original matrix is translated into a tile layout i.e., a high performance data representation, which substantially enhances data locality. Following a two-stage approach, the tile matrix is then transformed into band tridiagonal form using compute intensive kernels. The band form is further reduced to the required tridiagonal form using a left-looking bulge chasing technique to reduce memory traffic and memory contention. A dependence translation layer associated with a dynamic runtime system allows for scheduling and overlapping tasks generated from both stages. The obtained tile tridiagonal reduction significantly outperforms the state-of-the-art numerical libraries (10X against multithreaded LAPACK with optimized MKL BLAS and 2.5X against the commercial numerical software Intel MKL) from medium to large matrix sizes.

Original languageEnglish (US)
Title of host publicationProceedings - 25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011
Pages944-955
Number of pages12
DOIs
StatePublished - Oct 3 2011
Event25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011 - Anchorage, AK, United States
Duration: May 16 2011May 20 2011

Publication series

NameProceedings - 25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011

Other

Other25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011
CountryUnited States
CityAnchorage, AK
Period05/16/1105/20/11

Keywords

  • Bulge Chasing
  • Scheduling
  • Tile Algorithms
  • Translation Layer
  • Tridiagonal Reduction

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Two-stage tridiagonal reduction for dense symmetric matrices using tile algorithms on multicore architectures'. Together they form a unique fingerprint.

Cite this