December 2004 | Patrick Amestoy, Abdou Guermouche, Jean-Yves L'Excellent, Stéphane Pralet
This paper presents a hybrid scheduling approach for the parallel solution of linear systems, focusing on balancing workload and memory usage in the context of the parallel multifrontal factorization method. The approach uses an optimistic scenario during the analysis phase to estimate workload and memory, which is then used to constrain dynamic decisions during the factorization phase. The task scheduler has been redesigned to incorporate these new features, leading to improved performance. The memory estimation becomes much closer to the actual memory used, and the factorization time is reduced compared to the initial approach. The paper describes the parallelism involved in the MUMPS solver, the constraints and objectives of the work, and the dynamic scheduling algorithm for unsymmetric matrices. It also explains the challenges of the symmetric case and how the algorithms were extended to this case. The paper presents experimental results on large symmetric and unsymmetric matrices on 64 and 128 Power 4 processors of an IBM machine, showing that the hybrid scheduling approach significantly reduces the estimated memory and improves the factorization time. The results also show that the hybrid approach is more scalable for symmetric problems compared to unsymmetric ones.This paper presents a hybrid scheduling approach for the parallel solution of linear systems, focusing on balancing workload and memory usage in the context of the parallel multifrontal factorization method. The approach uses an optimistic scenario during the analysis phase to estimate workload and memory, which is then used to constrain dynamic decisions during the factorization phase. The task scheduler has been redesigned to incorporate these new features, leading to improved performance. The memory estimation becomes much closer to the actual memory used, and the factorization time is reduced compared to the initial approach. The paper describes the parallelism involved in the MUMPS solver, the constraints and objectives of the work, and the dynamic scheduling algorithm for unsymmetric matrices. It also explains the challenges of the symmetric case and how the algorithms were extended to this case. The paper presents experimental results on large symmetric and unsymmetric matrices on 64 and 128 Power 4 processors of an IBM machine, showing that the hybrid scheduling approach significantly reduces the estimated memory and improves the factorization time. The results also show that the hybrid approach is more scalable for symmetric problems compared to unsymmetric ones.