Hierarchical QR factorization algorithms for multi-core clusters

Abstract

This paper describes a new QR factorization algorithm which is especially designed for massively parallel platforms combining parallel distributed nodes, where a node is a multi-core processor. These platforms represent the present and the foreseeable future of high-performance computing. Our new QR factorization algorithm falls in the category of the tile algorithms which naturally enables good data locality for the sequential kernels executed by the cores (high sequential performance), low number of messages in a parallel distributed setting (small latency term), and fine granularity (high parallelism). Each tile algorithm is uniquely characterized by its sequence of reduction trees. In the context of a cluster of nodes, in order to minimize the number of inter-processor communications (aka, “communication-avoiding”), it is natural to consider hierarchical trees composed of an “inter-node” tree which acts on top of “intra-node” trees. At the intra-node level, we propose a hierarchical tree made of three levels: (0) “TS level” for cache-friendliness, (1) “low-level” for decoupled highly parallel inter-node reductions, (2) “domino level” to efficiently resolve interactions between local reductions and global reductions. Our hierarchical algorithm and its implementation are flexible and modular, and can accommodate several kernel types, different distribution layouts, and a variety of reduction trees at all levels, both inter-node and intra-node. Numerical experiments on a cluster of multi-core nodes (i) confirm that each of the four levels of our hierarchical tree contributes to build up performance and (ii) build insights on how these levels influence performance and interact within each other. Our implementation of the new algorithm with the DAGuE scheduling tool significantly outperforms currently available QR factorization software for all matrix shapes, thereby bringing a new advance in numerical linear algebra for petascale and exascale platforms.

Introduction

Future exascale machines will likely be massively parallel architectures, with ${10}^5$ to ${10}^6$ nodes, each node itself being equipped with ${10}^3$ to ${10}^4$ cores. At the node level, the architecture is a shared-memory machine, running many parallel threads on the cores. At the machine level, the architecture is a distributed-memory machine. This additional level of hierarchy, together with the interplay between the cores and the accelerators, dramatically complicates the design of new versions of the standard factorization algorithms that are central to many scientific applications. In particular, the performance of numerical linear algebra kernels is at the heart of many grand challenge applications, and it is of key importance to provide highly-efficient implementations of these kernels to leverage the impact of exascale platforms.

This paper investigates the impact of this hierarchical hardware organization on the design of numerical linear algebra algorithms. We deal with the QR factorization algorithm which is ubiquitous in high-performance computing applications, and which is representative of many numerical linear algebra kernels. In recent years, the quest of efficient, yet portable, implementations of the QR factorization algorithm has never stopped [1], [2], [3], [4], [5], [6], [7], [8]. In a nutshell, state-of-the-art software has evolved from block-column panels to tile-based versions, and then to multi-eliminator algorithms. We briefly review this evolution in the following paragraphs.

First the LAPACK library [9] has provided Level 3 BLAS kernels to boost performance on a single CPU. The ScaLAPACK library [10] builds upon LAPACK and provides a coarse-grain parallel version, where processors operate on large block-column panels, i.e. blocks of b columns of the original matrix. Here b is the block size, typically $b=200$ or more, for Level 3 BLAS performance. Inter-processor communications occur through highly tuned MPI send and receive primitives. The factorization progresses panel by panel. Once the current panel is factored, updates are applied on all the following panels (remember that the matrix operated upon shrinks as the factorization progresses). Sophisticated lookahead versions of the algorithms factor the next panel while the current updates are still being applied to the trailing matrix.

Then, the advent of multi-core processors has led to a major modification in the programmings [1], [4], [5], [7]. To avoid any confusion, we define a node as a processor equipped with several cores. Now each node should run several threads in parallel to keep all cores within that node busy. Tiled versions of the algorithms have thus been designed: dividing large block-column panels into several tiles allows for a decrease in the granularity down to a level where many smaller-size tasks are spawned. In the current panel, the diagonal tile, or eliminator tile, is used to eliminate all the tiles below it in the panel. Because the factorization of the whole panel is now broken into the elimination of several tiles, the update operations can also be partitioned at the tile level, which generates many tasks to feed all cores. However, the dependencies between these tasks must be enforced, and the algorithms have become much more complicated.

A technical difficulty arises with the elimination operations within the panel: these are sequential because the diagonal tile is used for each of them, hence it is modified at each elimination operation. This observation applies to the updates as well: in any trailing column, the update of a tile must wait until the update of its predecessor tile is completed. To further increase the degree of parallelism of the algorithms, it is possible to use several eliminator tiles inside a panel. The only condition is that concurrent elimination operations must involve disjoint tile pairs. Of course, in the end there must remain only one non-zero tile on the panel diagonal, so that all eliminators but the diagonal tile must be eliminated themselves later on, using a reduction tree of arbitrary shape (e.g. serial, fully binary, …). The extra source for parallelism resides in the fact that the whole matrix can be partitioned into domains, with one eliminator per domain responsible for eliminating the tiles local to the domain. In each domain, all these operations, and the corresponding updates, are independent and can run concurrently. Such multi-eliminator algorithms represent the state-of-the-art for a single node, but they are still being refined, because the impact of the reduction trees which are chosen is not fully understood, and also because using many eliminators implies the use of different tile kernels, called TT kernels, which are less-efficient than the TS kernels used with a single eliminator per panel.

The goal of this paper is to move a step forward and to introduce a flexible and modular algorithm for clusters, where a cluster is a multi-node machine (each node being a multi-core processor). Tackling such hierarchical architectures is a difficult challenge for two reasons. The first challenge arises from the algorithmic perspective. Brand new avenues must be explored to accommodate the hierarchical nature of multi-core clusters. Concurrent eliminators allow for more parallelism, but the reduction tree that follows breaks the smooth pipelining of operations from one panel to the next. With one domain per node, we may not have enough parallel operations to feed all the many-cores, so we may need to have several domains per node. The reduction operations involve inter-node communications, which are much slower than intra-node shared memory accesses. Limiting their number could be achieved with a block row-distribution, but this would severely imbalance node loads. This small list is not exhaustive: good load-balance, efficient pipelining, and memory locality are all conflicting objectives. The main contribution of this paper is to provide a novel algorithm that is fully aware of the hierarchical nature of the target platform and squeezes the most out of its resources.

The second challenge is at the programing level. Within a node, the architecture is a shared-memory machine, running many parallel threads on the cores. But the global architecture is a distributed-memory machine, and requires MPI communication primitives for inter-node communications. A slight change in the algorithm, or in the matrix layout across the nodes, might call for a time-consuming and error-prone process of code adaptation. For each version, one must identify, and adequately implement, inter-node versus intra-node kernels. This dramatically complicates the task of the programmer if he relies on a manual approach. We solve this problem by relying on the DAGuE software [8], [11], so that we can concentrate on the algorithm and forget about MPI sends and thread synchronizations. Once we have specified the algorithm at a task level, the DAGuE software will recognize which operations are local to a node (and hence correspond to shared-memory accesses), and which are not (and hence must be converted into MPI communications). Our experiments show that this approach is very powerful, and that the use of a higher-level framework does not prevent our algorithms from outperforming all existing solutions.

In this paragraph, we briefly highlight our contribution with respect to existing work (see Section 3 for a full overview). Two recent papers [2], [8] have discussed tiled algorithms for clusters of multi-core nodes. In [2], the authors use a two-level hierarchical tree made of an inter-node binary tree on top of an intra-node TS flat tree and use a 1D block data layout. A flat tree is a reduction tree with a single eliminator (the same tile here is sued to eliminate all other tiles). The limitations are: (1) the use of a flat tree at the node level is not adapted when the local matrices are tall and skinny; (2) the use of the 1D block data layout results in serious load imbalance for square matrices. In [8], the authors use a plain flat tree on top of a 2D block data layout. The limitations are: (1) the use of a flat tree is not adapted for tall and skinny matrices; (2) the flat tree with natural ordering is not aware of the 2D data block cyclic distribution and therefore performs many more communications than needed. Our algorithm addresses all these issues while keeping the positive features. At the intra-node level, we propose a hierarchical tree made of three levels: (0) “TS level” for cache-friendliness, (1) “low-level” for decoupled highly parallel inter-node reductions, (2) “domino level” to efficiently resolve interactions between local reductions and global reductions. Finally (3) a “high-level” tree is used for the inter-node reduction. The use of the “high-level” tree enables a small number of inter-processor communications, thereby making our algorithm “communication-avoiding”. For the levels (1), (2) and (3) of the hierarchical algorithm, the reduction can accommodate any tree. Our implementation is flexible and modular, and proposes several reduction trees per level. This allows us to use those reduction trees which are efficient for a given matrix shape. Finally the “domino level” – which operates within a node, and fits in between the intra- and inter-node reductions – resolves all interactions between the low-level and high-level trees, in such a way that the low-level tree (acting within a node) becomes decoupled from the influence of the other nodes. To summarize, our new algorithm is a tile QR factorization which is (a) designed especially for massively parallel platforms combining parallel distributed multi-core nodes; (b) features a hierarchical four-level tree reduction; (c) incorporates a novel domino level; (d) is 2D block cyclic aware; and (e) implements a variety of trees at each level. The resulting properties of the algorithm are (i) cache-efficiency at the core level, (ii) high granularity at the node level, (iii) communication avoiding at the distributed level, (iv) excellent load balancing overall, (v) nice coupling between the inter-node and intra-node interactions, and (vi) ability to efficiently handle any matrix shape.

The rest of the paper is organized as follows. We start with a quick review of tiled QR algorithms (Section 2). Then we detail the key principles underlying the design of state-of-the-art algorithms from the literature (Section 3). The core contributions of the paper reside in the next three sections. The new algorithm is presented in full details, first with a general description (Section 4), and then with analytical formulas for the number of operations at each kernel that compose the algorithm (Section 5). Then in Section 6, we report experiments showing that we outperform current state-of-the-art implementations. We observe that the execution time of each algorithmic variant is in direct accordance with its critical path length, thereby showing a very good match between predicted and actual performance. Finally, we provide some concluding remarks and future research directions in Section 7.