On Partitioning and Reordering Problems in a Hierarchically Parallel Hybrid Linear Solver

Abstract : PDSLin is a general-purpose algebraic parallel hybrid (direct/iterative) linear solver based on the Schur complement method. The most challenging step of the solver is the computation of a preconditioner based on the global Schur complement. Efficient parallel computation of the preconditioner gives rise to partitioning problems with sophisticated constraints and objectives. In this paper, we identify two such problems and propose hyper graph partitioning methods to address them. The first problem is to balance the work loads associated with different sub domains to compute the preconditioner. We first formulate an objective function and a set of constraints to model the preconditioner computation time. Then, to address these complex constraints, we propose a recursive hyper graph bisection method. The second problem is to improve the data locality during the parallel solution of a sparse triangular system with multiple sparse right-hand sides. We carefully analyze the objective function and show that it can be well approximated by a standard hyper graph partitioning method. Moreover, an ordering compatible with a post ordering of the sub domain elimination tree is shown to be very effective in preserving locality. To evaluate the two proposed methods in practice, we present experimental results using linear systems arising from some applications of our interest. First, we show that in comparison to a commonly-used nested graph dissection method, the proposed recursive hyper graph partitioning method reduces the preconditioner construction time, especially when the number of sub domains is moderate. This is the desired result since PDSLin is based on a two-level parallelization to keep the number of sub domains small by assigning multiple processors to each sub domain. We also show that our second proposed hyper graph method improves the data locality during the sparse triangular solution and reduces the solution time. Moreover, we show that partitioning time can b- greatly reduced while maintaining its quality by removing quasi-dense rows from the solution vectors.
Liste complète des métadonnées

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00923447
Contributor : Equipe Roma <>
Submitted on : Thursday, January 2, 2014 - 7:36:59 PM
Last modification on : Friday, April 20, 2018 - 3:44:26 PM
Document(s) archivé(s) le : Saturday, April 8, 2017 - 10:34:16 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00923447, version 1

Collections

Citation

Ichitaro Yamazaki, Xiaoye S. Li, François-Henry Rouet, Bora Uçar. On Partitioning and Reordering Problems in a Hierarchically Parallel Hybrid Linear Solver. 2013 IEEE 27th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), IEEE, May 2013, Cambridge, MA, United States. ⟨hal-00923447⟩

Share

Metrics

Record views

633

Files downloads

244