Partitioning, Ordering, and Load Balancing in a Hierarchically Parallel Hybrid Linear Solver

Ichitaro Yamazaki (1) , Xiaoye S. Li (1) , François-Henry Rouet (2, 3) , Bora Uçar (4, 5)

1 LBNL - Lawrence Berkeley National Laboratory [Berkeley]
2 IRIT - Institut de recherche en informatique de Toulouse
3 ENSEEIHT - Ecole Nationale Supérieure d'Electrotechnique, d'Electronique, d'Informatique, d'Hydraulique et de Télécommunications
4 LIP - Laboratoire de l'Informatique du Parallélisme
5 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement

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 an approximate global Schur complement. We investigate two combinatorial problems to enhance PDSLin's performance at this step. The first is a multi-constraint partitioning problem to balance the workload while computing the preconditioner in parallel. For this, we describe and evaluate a number of graph and hypergraph partitioning algorithms to satisfy our particular objective and constraints. The second problem is to reorder the sparse right-hand side vectors to improve the data access locality during the parallel solution of a sparse triangular system with multiple right-hand sides. This is to speed up the process of eliminating the unknowns associated with the interface. We study two reordering techniques: one based on a postordering of the elimination tree and the other based on a hypergraph partitioning. To demonstrate the effect of these techniques on the performance of PDSLin, we present the numerical results of solving large-scale linear systems arising from two applications of our interest: numerical simulations of modeling accelerator cavities and of modeling fusion devices.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Logiciel mathématique [cs.MS]; Mathématique discrète [cs.DM]

Ichitaro Yamazaki, Xiaoye S. Li, François-Henry Rouet, Bora Uçar. Partitioning, Ordering, and Load Balancing in a Hierarchically Parallel Hybrid Linear Solver. [Research Report] 2011, pp.22. ⟨hal-00797207⟩