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.
Type de document :
Communication dans un congrès
2013 IEEE 27th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), May 2013, Cambridge, MA, United States. IEEE Computer Society, 2013
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00923447
Contributeur : Equipe Roma <>
Soumis le : jeudi 2 janvier 2014 - 19:36:59
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : samedi 8 avril 2017 - 10:34:16

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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), May 2013, Cambridge, MA, United States. IEEE Computer Society, 2013. 〈hal-00923447〉

Partager

Métriques

Consultations de la notice

534

Téléchargements de fichiers

237