Two-level dynamic scheduling in PARDISO:: Improved scalability on shared memory multiprocessing systems

The PARDISO package is a mathematical library of OpenMP routines for the parallel direct solution of large sparse linear systems of equations. One objective of PARDISO is to achieve a high efficiency on shared memory multiprocessing systems. A new parallelization strategy based on a dynamic two-level scheduling scheme is therefore explored. The method aims at minimizing cache conflicts and interprocessor communication costs and, at the same time, maximizing processor load balance and Level-3 BLAS performance. The synchronization events are reduced by one order of magnitude compared with a one-level scheduling strategy. This results in an efficient parallel sparse LU decomposition method. An overview of the two-level scheduling algorithm and the key algorithmic features of the solver PARDISO is given. Finally, numerical results and a comparison with another software package demonstrate the performance. (C) 2002 Published by Elsevier Science B.V.