Multicore Performance Engineering of Sparse Triangular Solves Using a Modified Roofline Model

• Markus Wittmann Friedrich-Alexander University
• Georg Hager Friedrich-Alexander University
• Radim Janalik Universitá della Svizzera italiana
• Martin Lanser University of Cologne
• Axel Klawonn University of Cologne
• Oliver Rheinbach TU Bergakademie Freiberg
• Olaf Schenk Universitá della Svizzera italiana
• Gerhard Wellein Friedrich-Alexander University

Resumo

The Roofline model is widely used to visualize the performance of executed code together with the upper performance bounds given by the memory bandwidth and the processor peak performance. The model can thus provide an insightful visualization of bottlenecks. In this paper, we try to establish realistic bandwidth ceilings for the sparse triangular solve step of PARDISO, a leading sparse direct solver package, which is also part of the Intel MKL library. The performance of the forward and backward substitution process is analyzed and benchmarked for a representative set of sparse matrices on seven modern x86-type multicore architectures and the Knights Landing manycore architecture. It is shown how to accurately measure the necessary quantities also for threaded code, and the measurement approach, its validation, as well as limitations are discussed. Our modeling approach covers the serial and parallel execution phases, allowing for in-socket performance predictions.

Palavras-chave: Sparse matrices, Particle separators, Analytical models, Computational modeling, Computer architecture, Mathematical model, Hardware