HQR: A library to generate hierachical trees adapted to distributed mnay-cores architectures for QR/LQ tile algorithms

HQR is a C library providing tools to generate hierachical trees adapted to 2D block-cyclic data distribution and algorithms based on tiled QR/algorithms. This library is used in Chameleon and DPLASMA.

This libraries provides generation of trees for various configuration and intent to provide an automatically generated tree adapted to the matrix size, and the targetted architecture.

Tools to draw the trees in SVG and DOT formats are provided to display the generated trees and debug applications, as well as tools to provide critical path length.

1 Get HQR

To use last development states of the HQR library, please clone the master branch. Note that Chameleon already contains the HQR library as a submodule. To get sources please use these commands:

git clone git@gitlab.inria.fr:solverstack/hqr.git

Last releases of Chameleon are hosted on the gforge.inria.fr for now. Future releases will be available on this gitlab project.

2 Authors

The following people contributed to the development of the HQR library:

• Guillaume Aupy
• Raphael Boucherie
• Mathieu Faverge, PI
• Thomas Herault
• Mathias Jacquelin
• Julien Langou
• Yves Robert

If we forgot your name, please let us know that we can fix that mistake.

3 Citing HQR

Feel free to use the following publications to reference the HQR library:

• Original paper that initiated the hierarcical QR algorithms:
  • Henricus Bouwmeester, Mathias Jacquelin, Julien Langou, Yves Robert. Tiled QR factorization algorithms, in SC ‘11 Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis acm arxiv
• Hierachical trees for distributed memory:
  • Jack Dongarra, Mathieu Faverge, Thomas Hérault, Mathias Jacquelin, Julien Langou, et Yves Robert. Hierarchical QR factorization algorithms for multi-core clusters. Parallel Computing, Elsevier, 2013, 39 (4-5), pp.212-232. parco.2013.01.003 hal-00809770
• Systolic trees for the QR factorization:
  • Guillaume Aupy, Mathieu Faverge, Yves Robert, Jakub Kurzak, Piotr Luszczek, et Jack Dongarra. Implementing a systolic algorithm for QR factorization on multicore clusters with PaRSEC. PROPER 2013 - 6th Workshop on Productivity and Performance, Aug 2013, Aachen, Germany. 2013. hal-00844492
• Adapted trees to Bi-diagonalization algorithms:
  • Mathieu Faverge, Julien Langou, Yves Robert, Jack Dongarra. Bidiagonalization and R-Bidiagonalization: Parallel Tiled Algorithms, Critical Paths and Distributed-Memory Implementation. IPDPS’17 - 31st IEEE International Parallel and Distributed Processing Symposium, May 2017, Orlando, United States. 2017, ipdps hal-01484113