Skip to content Skip to main navigation Report an accessibility issue

EECS Publication

High Performance Bidiagonal Reduction using Tile Algorithms on Homogeneous Multicore Architectures

Hatem Ltaief, Piotr Luszczek, Jack Dongarra

This paper presents a new high performance bidiagonal reduction (BRD) on homogeneous multi-core architectures. This paper is an extension of the high performance tridiagonal reduction implemented by the same authors (Luszczek et al., IPDPS 2011) to the BRD case. The BRD is the first step toward computing the singular value decomposition of a matrix which is one of the most important algorithms in numerical linear algebra due to its broad impact in computational science. The high performance of the BRD described in this paper comes from the combination of four important features: (1) tile algorithms with tile data layout which provide an efficient data representation in main memory, (2) a two-stage reduction approach which allows to cast most of the computation during the first stage (reduction to band form) into calls to Level 3 BLAS and reduces the memory traffic during the second stage (reduction from band to bidiagonal form) by using high performance kernels optimized for cache reuse, (3) a data dependence translation layer which maps the general algorithm with column-major data layout into the tile data layout and (4) a dynamic runtime system which efficiently schedules the newly implemented kernels across the processing units and ensures the data dependencies are not violated. A detailed analysis is provided to understand the critical impact of the tile size on the total execution time which also corresponds to the matrix bandwidth size after the reduction of the first stage. The observed performance results show a staggering improvement over currently established alternatives. The new high performance BRD achieves up to 30-fold speedup on a 16 core Intel Xeon machine with a 12000x12000 matrix size against the state-of-theart open source and commercial numerical software packages, namely, LAPACK compiled with optimized and multithreaded BLAS from MKL as well as Intel MKL version 10.2.

Published  2011-05-19 04:00:00  as  ut-cs-11-673 (ID:35)


« Back to Listing