Scalable Tile Communication-Avoiding QR Factorization on Multicore Cluster Systems

• Main Authors: Song, Fengguang, Ltaief, Hatem, Hadri, Bilel, Dongarra, Jack
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm design and analysis; Computer systems organization; Computer systems organization > Dependable and fault-tolerant systems and networks; General and reference; General and reference > Cross-computing tools and techniques; General and reference > Cross-computing tools and techniques > Performance; Kernel; Libraries; Multicore processing; Networks; Networks > Network performance evaluation; Runtime; Social and professional topics; Social and professional topics > Professional topics; Social and professional topics > Professional topics > Computing profession; Social and professional topics > Professional topics > Computing profession > Testing, certification and licensing; Tiles
• ISSN: 2167-4329; 2167-4337
• DOI: 10.1109/SC.2010.48

As tile linear algebra algorithms continue achieving high performance on shared-memory multicore architectures, it is a challenging task to make them scalable on distributed-memory multicore cluster machines. The main contribution of this paper is the extension to the distributed-memory environment of the previous work done by Hadri et al. on Communication- Avoiding QR (CA-QR) factorizations for tall and skinny matrices (initially done on shared-memory multicore systems). The fine granularity of tile algorithms associated with communicationavoiding techniques for the QR factorization presents a high degree of parallelism where multiple tasks can be concurrently executed, computation and communication largely overlapped, and computation steps fully pipelined. A decentralized dynamic scheduler has then been integrated as a runtime system to efficiently schedule tasks across the distributed resources. Our experimental results performed on two clusters (with dual-core and 8-core nodes, respectively) and a Cray XT5 system with 12-core nodes show that the tile CA-QR factorization is able to outperform the de facto ScaLAPACK library by up to 4 times for tall and skinny matrices, and has good scalability on up to 3,072 cores.