Performance tuning
The performance of qr_mumps depends on a number of parameters. Default values are provided for these parameters that are expected to achieve reasonably good performance on a wide range of problems and architectures but for optimal performance these should be tuned. In this section we provide a list of these parameters and explain how do they have an effect on performance.
Block size
- qr_mumps decomposes frontal matrices into blocks of size mb × mb (set through the qrm_mb control parameter); this decomposition provides an additional level of parallelism (other than that already expressed by the elimination tree) because it is possible to execute concurrently tasks that operate on different blocks. On the one hand, small values of mb provide high parallelism; on the other hand, high values of mb provide high efficiency for each task and make the tasks scheduling overhead negligible. This parameter should be, therefore, chosen as to provide the best compromise between parallelism and tasks efficiency. The optimal value depends on the size and structure of the problem, the number and features of processing units, the efficiency and scalability of BLAS operations, etc... On current CPUs block sizes of 128 or 256 achieve close to optimal task performance and good parallelism on moderately sized problems; if GPUs are used, higher block sizes (1024) provide better performance. Choosing a large mb value to achieve high performance on GPU devices can severely reduce parallelism and lead to CPU starvation. In this case the nb parameter (qrm_nb) can be used to generate additional parallelism; if this parameter is set to a submultiple of mb, the dynamic, hierarchical partitioning technique is used which can lead to better performance. Finally, some tasks use an internal block size; this is set by the ib parameter (qrm_ib which has to be a submultiple of mb and nb) and defines a compromise between efficiency of tasks and overall amount of floating point operations. Again, when GPUs are used, larger values of ib lead to better speed whereas on CPUs values of 32/64 provide satisfactory speed.
Reduction tree shape
- The bh parameter (qrm_bh) defines the shape of the reduction tree in the QR panel reduction. A value of $k$ means that a panel is divided in groups of size $k$, intra-group reduction is done with a flat tree, inter-group reduction with a binary tree. Therefore, a value of one achieves the highest parallelism because the whole panel is reduced through a binary tree. Conversely a value which is equal or higher than the number of blocks in a panel leads to lower parallelism because all the blocks in the panels are reduced one after the other; a zero or negative value sets a flat tree on all panels in all fronts of the multifrontal factorization. Nevertheless it must be noted that excessively small values of bh may lead to inefficient computations because of the nature of the involved tasks. A flat tree typically achieves high performance on a wide range of problems but for very overdetermined problems it may be beneficial to use hybrid trees.
Ordering
- Fill-reducing ordering is essential to limit the fill-in produced by the factorization. This ordering (set through the qrm_ordering control parameter) is computed during the analysis phase and corresponds to a matrix permutation that defines the order in which unknowns are eliminated. The ordering will also affect the shape of the elimination tree which can be more or less balanced or deep with obvious consequences on parallelism, efficiency and, ultimately, execution time. Nested Dissection methods, such as those implemented in the Metis and SCOTCH packages, usually provide the best results and their running time may be high; local orderings such as AMD/COLAMD typically have a lower running time, which results in a faster analysis step, but lead to higher fill-in and thus higher running time and memory consumption for the factorization and the solve.