Hybrid scheduling for the parallel solution of linear systems

被引:750
作者
Amestoy, PR
Guermouche, A
L'Excellent, JY
Pralet, S
机构
[1] IRIT, ENSEEIHT, INRIA, F-31071 Toulouse 7, France
[2] Ecole Normale Super Lyon, LIP, INRIA, F-69364 Lyon, France
[3] IRIT, ENSEEIHT, CNRS, F-31071 Toulouse 7, France
关键词
sparse matrices; parallel multifrontal method; dynamic scheduling; memory;
D O I
10.1016/j.parco.2005.07.004
中图分类号
TP301 [理论、方法];
学科分类号
081202 [计算机软件与理论];
摘要
We consider the problem of designing a dynamic scheduling strategy that takes into account both workload and memory information in the context of the parallel multifrontal factorization. The originality of our approach is that we base our estimations (work and memory) on a static optimistic scenario during the analysis phase. This scenario is then used during the factorization phase to constrain the dynamic decisions that compute fully irregular partitions in order to better balance the workload. We show that our new scheduling algorithm significantly improves both the memory behaviour and the factorization time. We give experimental results for large challenging real-life 3D problems on 64 and 128 processors. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码:136 / 156
页数:21
相关论文
共 19 条
[1]
Task scheduling in an asynchronous distributed memory multifrontal solver [J].
Amestoy, PR ;
Duff, IS ;
Vömel, C .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2004, 26 (02) :544-565
[2]
Multifrontal parallel distributed symmetric and unsymmetric solvers [J].
Amestoy, PR ;
Duff, IS ;
L'Excellent, JY .
COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING, 2000, 184 (2-4) :501-520
[3]
Adapting a parallel sparse direct solver to architectures with clusters of SMPs [J].
Amestoy, PR ;
Duff, IS ;
Pralet, S ;
Vömel, C .
PARALLEL COMPUTING, 2003, 29 (11-12) :1645-1668
[4]
A fully asynchronous multifrontal solver using distributed dynamic scheduling [J].
Amestoy, PR ;
Duff, IS ;
L'Excellent, JY ;
Koster, J .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2001, 23 (01) :15-41
[5]
ScaLAPACK: A portable linear algebra library for distributed memory computers - Design issues and performance [J].
Choi, J ;
Demmel, J ;
Dhillon, I ;
Dongarra, J ;
Ostrouchov, S ;
Petitet, A ;
Stanley, K ;
Walker, D ;
Whaley, RC .
COMPUTER PHYSICS COMMUNICATIONS, 1996, 97 (1-2) :1-15
[6]
DONGARRA JJ, 1998, SOFTW ENVIRONM TOOL, P1
[7]
THE MULTIFRONTAL SOLUTION OF UNSYMMETRIC SETS OF LINEAR-EQUATIONS [J].
DUFF, IS ;
REID, JK .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1984, 5 (03) :633-641
[8]
THE MULTIFRONTAL SOLUTION OF INDEFINITE SPARSE SYMMETRIC LINEAR-EQUATIONS [J].
DUFF, IS ;
REID, JK .
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1983, 9 (03) :302-325
[9]
Duff IS, 1986, DIRECT METHODS SPARS
[10]
TASK-SCHEDULING FOR PARALLEL SPARSE CHOLESKY FACTORIZATION [J].
GEIST, GA ;
NG, E .
INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING, 1989, 18 (04) :291-314