-
O. Beaumont,
P. Ramet,
and J. Roman.
Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms.
In Proceedings of Fifth International Conference on Parallel Processing and Applied Mathematics, Workshop HeteroPar,
volume 3019 of LNCS,
Czestochowa, Poland,
pages 880-887,
September 2003.
Springer Verlag.
Keyword(s): Overlap.
Abstract: |
In this paper, we focus on the scheduling of Laplace task graph on a general platform where both communication links and processing units are heterogeneous. In this context, it is known that deriving optimal algorithm, in the sense of makespan minimization, is NP-Complete, and several inapproximation results have been proved. Nevertheless, we provide an asymtotically optimal algorithm in this general context. Moreover, we expect that this methodolgy can be extended to more general task graphs, especially for nested loops where the inner-most loop is parallel. |
@InProceedings{C:LaBRI::ppam03,
author = "Beaumont, O. and Ramet, P. and Roman, J.",
title = "Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms",
booktitle = "Proceedings of Fifth International Conference on Parallel Processing and Applied Mathematics, Workshop HeteroPar",
OPTcrossref = {},
OPTkey = {},
OPTeditor = {},
volume = {3019},
OPTnumber = {},
series = {LNCS},
year = "2003",
OPTorganization = {},
publisher = {Springer Verlag},
address = {Czestochowa, Poland},
month = sep,
pages = {880--887},
OPTnote = {},
OPTannote = {},
URL = {http://www.labri.fr/~ramet/restricted/ppam03.ps},
KEYWORDS = "Overlap",
ABSTRACT = { In this paper, we focus on the scheduling of Laplace task graph on a general platform where both communication links and processing units are heterogeneous. In this context, it is known that deriving optimal algorithm, in the sense of makespan minimization, is NP-Complete, and several inapproximation results have been proved. Nevertheless, we provide an asymtotically optimal algorithm in this general context. Moreover, we expect that this methodolgy can be extended to more general task graphs, especially for nested loops where the inner-most loop is parallel. }
}
-
D. Goudin,
P. Hénon,
M. Mandallena,
K. Mer,
F. Pellegrini,
P. Ramet,
J. Roman,
and J.-J. Pesqué.
Outils numériques parallèles pour la résolution de très grands problèmes d'électromagnétisme.
In Séminaire sur l'Algorithmique Numérique Appliquée aux Problèmes Industriels,
Calais, France,
May 2003.
Keyword(s): Sparse.
Abstract: |
L'émergence des machines parallèles téraflopiques permet maintenant de traiter des problèmes de diffraction de très grande taille liés à des calculs hautes fréquences par des méthodes exactes. Une première étape de ce travail a constisté à paralléliser des codes séquentiels existants qui utilisaient des méthodes numériques classiques. Ces codes étaient basés sur un couplage fort par complément de Schur entre une formulation intégrale (éléments-finis surfaciques pour traiter la condition de radiation à l'infini) et une formulation éléments-finis volumiques (pour calculer les champs à l'intérieur de l'objet). L'adapation au parallélisme a consisté à paralléliser la factorisation du système linéaire creux (à l'aide de la bibliothèque EMILIO/PaStiX, la résolution du système intégral plein (symétrique, complexe) et le couplage par complément de Schur (consistant en des descentes-remontées sur le système creux associé). Les deux premières étapes citées ont donné pleinement satisfaction, mais le complément de Schur, à cause du très grand nombre descentes-remontées liées aux inconnues surfaciques, limite l'efficacité globale de cette approche à des problèmes de taille intermédiaire. Par exemple, pour le cas test du ``Sphere-Cone'' comportant $3.10^6$ d'inconnues volumiques et $23.10^3$ inconnues surfaciques, sur 32 n\oe uds ES45 (quadri-processeurs), l'assemblage volumique repr\'esente 6s, la factorisation du syst\`eme creux est obtenue en 376s et le compl\'ement de Schur en 21500s (en complexe double pr\'ecision). Pour dépasser ces limites, une évolution globale de l'algorithme a été nécessaire~: - un couplage itératif entre les résolutions surfacique et volumique a été mis en place; - pour augmenter le nombre d'inconnues surfaciques une méthode multipôle multi-niveaux parallèle a été développée; - enfin, pour atteindre des tailles de problème de plusieurs dizaines de millions d'inconnues volumiques, des évolutions ont été apportées dans la bibliothèque EMILIO/PaStiX. En particulier, une algorithmique sp\'ecifique a \'et\'e mise en place pour utiliser au mieux les clusters de n\oe uds SMP et pour pr\'eserver une scalabilit\'e m\'emoire raisonnable. Enfin, le schéma actuel présente un couplage direct-itératif à plusieurs niveaux. L'évolution envisagée sera un couplage itératif-itératif, puis sera bas\'ee sur des méthodes hybrides globales (intermédiaire entre le direct et l'itératif)~: une version de PaStiX évoluée permettra de calculer un précondition\-neur par bloc ILU(k) parallèle. |
@InProceedings{c:LaBRI::GHMMPRRP03,
author = "Goudin, D. and H\'enon, P. and Mandallena, M. and Mer, K. and Pellegrini, F. and Ramet, P. and Roman, J. and Pesqu\'e, J.-J.",
title = "Outils num\'eriques parall\`eles pour la r\'esolution de tr\`es grands probl\`emes d'\'electromagn\'etisme",
booktitle = "{S}\'eminaire sur l'{A}lgorithmique {N}um\'erique {A}ppliqu\'ee aux {P}robl\`emes {I}ndustriels",
OPTcrossref = {},
OPTkey = {},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
year = "2003",
OPTorganization = {},
OPTpublisher = {},
address = {Calais, France},
month = may,
OPTpages = {},
OPTnote = {},
OPTannote = {},
KEYWORDS = "Sparse",
ABSTRACT = { L'émergence des machines parallèles téraflopiques permet maintenant de traiter des problèmes de diffraction de très grande taille liés à des calculs hautes fréquences par des méthodes exactes. Une première étape de ce travail a constisté à paralléliser des codes séquentiels existants qui utilisaient des méthodes numériques classiques. Ces codes étaient basés sur un couplage fort par complément de Schur entre une formulation intégrale (éléments-finis surfaciques pour traiter la condition de radiation à l'infini) et une formulation éléments-finis volumiques (pour calculer les champs à l'intérieur de l'objet). L'adapation au parallélisme a consisté à paralléliser la factorisation du système linéaire creux (à l'aide de la bibliothèque EMILIO/PaStiX, la résolution du système intégral plein (symétrique, complexe) et le couplage par complément de Schur (consistant en des descentes-remontées sur le système creux associé). Les deux premières étapes citées ont donné pleinement satisfaction, mais le complément de Schur, à cause du très grand nombre descentes-remontées liées aux inconnues surfaciques, limite l'efficacité globale de cette approche à des problèmes de taille intermédiaire. Par exemple, pour le cas test du ``Sphere-Cone'' comportant $3.10^6$ d'inconnues volumiques et $23.10^3$ inconnues surfaciques, sur 32 n\oe uds ES45 (quadri-processeurs), l'assemblage volumique repr\'esente 6s, la factorisation du syst\`eme creux est obtenue en 376s et le compl\'ement de Schur en 21500s (en complexe double pr\'ecision). Pour dépasser ces limites, une évolution globale de l'algorithme a été nécessaire~: - un couplage itératif entre les résolutions surfacique et volumique a été mis en place; - pour augmenter le nombre d'inconnues surfaciques une méthode multipôle multi-niveaux parallèle a été développée; - enfin, pour atteindre des tailles de problème de plusieurs dizaines de millions d'inconnues volumiques, des évolutions ont été apportées dans la bibliothèque EMILIO/PaStiX. En particulier, une algorithmique sp\'ecifique a \'et\'e mise en place pour utiliser au mieux les clusters de n\oe uds SMP et pour pr\'eserver une scalabilit\'e m\'emoire raisonnable. Enfin, le schéma actuel présente un couplage direct-itératif à plusieurs niveaux. L'évolution envisagée sera un couplage itératif-itératif, puis sera bas\'ee sur des méthodes hybrides globales (intermédiaire entre le direct et l'itératif)~: une version de PaStiX évoluée permettra de calculer un précondition\-neur par bloc ILU(k) parallèle. }
}
-
P. Hénon,
F. Pellegrini,
P. Ramet,
and J. Roman.
An efficient hybrid MPI/Thread implementation on a network of SMP nodes for the parallel sparse direct solver PaStix: ordering / scheduling / memory managment / out-of-core issues, and application to preconditioning.
In Sparse Days,
Saint Girons, France,
June 2003.
Keyword(s): Sparse.
@InProceedings{C:LaBRI::sparsedays2003,
author = {H\'enon, P. and Pellegrini, F. and Ramet, P. and Roman, J.},
title = {An efficient hybrid MPI/Thread implementation on a network of SMP nodes for the parallel sparse direct solver PaStix: ordering / scheduling / memory managment / out-of-core issues, and application to preconditioning},
booktitle = {Sparse Days},
OPTcrossref = {},
OPTkey = {},
OPTpages = {},
year = {2003},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Saint Girons, France},
month = jun,
OPTorganization = {},
OPTpublisher = {},
OPTnote = {},
OPTannote = {},
KEYWORDS = "Sparse"
}
-
P. Hénon,
F. Pellegrini,
P. Ramet,
and J. Roman.
Towards High Performance Hybrid Direct-Iterative Solvers for Large Sparse Systems.
In International SIAM Conference On Preconditioning Techniques For Large Sparse Matrix Problems In Scientific And Industrial Applications,
Napa Valley, USA,
October 2003.
Keyword(s): Sparse.
@InProceedings{C:LaBRI::pre03,
author = {H\'enon, P. and Pellegrini, F. and Ramet, P. and Roman, J.},
title = {Towards High Performance Hybrid Direct-Iterative Solvers for Large Sparse Systems},
booktitle = {International SIAM Conference On Preconditioning Techniques For Large Sparse Matrix Problems In Scientific And Industrial Applications},
OPTcrossref = {},
OPTkey = {},
OPTpages = {},
year = {2003},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Napa Valley, USA},
month = oct,
OPTorganization = {},
OPTpublisher = {},
OPTnote = {},
OPTannote = {},
URL = {http://www.labri.fr/~ramet/restricted/pred2003.ps},
KEYWORDS = "Sparse"
}
-
P. Hénon,
P. Ramet,
and J. Roman.
A Parallel Direct Solver for Very Large Sparse SPD Systems.
In IPDPS'2003,
Nice, France,
April 2003.
Keyword(s): Sparse.
@InProceedings{C:LaBRI::ipdps2003,
author = "H\'enon, P. and Ramet, P. and Roman, J.",
title = "{A} {P}arallel {D}irect {S}olver for {V}ery {L}arge {S}parse {SPD} {S}ystems",
booktitle = "{IPDPS}'2003",
OPTcrossref = {},
OPTkey = {},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
year = "2003",
OPTorganization = {},
OPTpublisher = {},
address = {Nice, France},
month = apr,
OPTpages = {},
OPTnote = {},
OPTannote = {},
URL = {http://www.labri.fr/~ramet/restricted/PaStiX_flyer_ipdps2003.ppt},
KEYWORDS = "Sparse"
}
-
P. Hénon,
P. Ramet,
and J. Roman.
Efficient algorithms for direct resolution of large sparse system on clusters of SMP nodes.
In SIAM Conference on Applied Linear Algebra,
Williamsburg, USA,
July 2003.
Keyword(s): Sparse.
Abstract: |
In previous works, we have described an efficient static scheduling based on a mixed 1D/2D block distribution with local aggregation for a parallel supernodal version of sparse $LL^{T}$ factorization. In this paper, we present new algorithms suitable for overcoming architectures based on clusters of SMP nodes and also technics to keep a good memory scalability. This algorithms are implemented in the PaStiX library that achieved high performances (resolution of a $26.10^6$ unknown system on 192 ES45 quadriprocessors with 35 percent of peak performance). |
@InProceedings{C:LaBRI::siam2003,
author = {H\'enon, P. and Ramet, P. and Roman, J.},
title = {Efficient algorithms for direct resolution of large sparse system on clusters of {SMP} nodes},
booktitle = {{SIAM} Conference on Applied Linear Algebra},
OPTcrossref = {},
OPTkey = {},
OPTpages = {},
year = {2003},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Williamsburg, USA},
month = jul,
OPTorganization = {},
OPTpublisher = {},
OPTnote = {},
OPTannote = {},
KEYWORDS = "Sparse",
URL = {http://www.labri.fr/~ramet/restricted/RAMETP.PDF},
ABSTRACT = {In previous works, we have described an efficient static scheduling based on a mixed 1D/2D block distribution with local aggregation for a parallel supernodal version of sparse $LL^{T}$ factorization. In this paper, we present new algorithms suitable for overcoming architectures based on clusters of SMP nodes and also technics to keep a good memory scalability. This algorithms are implemented in the PaStiX library that achieved high performances (resolution of a $26.10^6$ unknown system on 192 ES45 quadriprocessors with 35 percent of peak performance). }
}
-
P. Hénon and Y. Saad.
A Parallel ILU factorization based on a Hierarchical Interface Decomposition algorithm.
In International SIAM Conference On Preconditioning Techniques For Large Sparse Matrix Problems In Scientific And Industrial Applications,
Napa Valley, USA,
October 2003.
Keyword(s): Sparse.
@InProceedings{C:LaBRI::pre03ph,
author = {H\'enon, P. and Saad, Y.},
title = {A Parallel ILU factorization based on a Hierarchical Interface Decomposition algorithm},
booktitle = {International SIAM Conference On Preconditioning Techniques For Large Sparse Matrix Problems In Scientific And Industrial Applications},
OPTcrossref = {},
OPTkey = {},
OPTpages = {},
year = {2003},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Napa Valley, USA},
month = oct,
OPTorganization = {},
OPTpublisher = {},
OPTnote = {},
OPTannote = {},
OPTURL = {},
KEYWORDS = "Sparse"
}
-
P. Hénon and Y. Saad.
PHIDAL: A Parallel Hierarchical Interface Decomposition Algorithm for solving sparse linear systems.
In Sparse Days and Grid Computing,
Saint Girons, France,
June 2003.
Keyword(s): Sparse.
@InProceedings{C:LaBRI::sparsedays2003ph,
author = {H\'enon, P. and Saad, Y.},
title = {PHIDAL: A Parallel Hierarchical Interface Decomposition Algorithm for solving sparse linear systems},
booktitle = {Sparse Days and Grid Computing},
OPTcrossref = {},
OPTkey = {},
OPTpages = {},
year = {2003},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Saint Girons, France},
month = jun,
OPTorganization = {},
OPTpublisher = {},
OPTnote = {},
OPTannote = {},
KEYWORDS = "Sparse"
}