-
Patrick R. Amestoy,
Iain S. Duff,
Jacko Koster,
and Jean-Yves L'Excellent.
A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling.
SIAM Journal on Matrix Analysis and Applications,
23(1):15--41,
2001.
@Article{ ArticleAmestoy.ADKL_SJMAA01,
title = {A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling},
author = {Patrick R. Amestoy and Iain S. Duff and Jacko Koster and Jean-Yves L'Excellent},
journal = {SIAM Journal on Matrix Analysis and Applications},
volume = 23,
number = 1,
year = 2001,
pages = {15--41}
}
-
Patrick R. Amestoy,
Iain S. Duff,
Jean-Yves L'Excellent,
and Xiaoye S. Li.
Analysis and Comparison of Two General Sparse Solvers for Distributed Memory Computers.
ACM Transactions on Mathematical Software,
27(4):388--421,
2001.
@Article{ ArticleAmestoy.ADLL_ATMS01,
author = {Patrick R. Amestoy and Iain S. Duff and Jean-Yves L'Excellent and Xiaoye S. Li},
title = {Analysis and Comparison of Two General Sparse Solvers for Distributed Memory Computers},
journal = {{ACM} Transactions on Mathematical Software},
volume = 27,
number = 4,
year = 2001,
pages = {388--421}
}
-
Olivier Beaumont,
Vincent Boudet,
Antoine Petitet,
Fabrice Rastello,
and Yves Robert.
A proposal for a heterogeneous cluster ScaLAPACK (dense linear solvers).
IEEE Trans. Computers,
50(10):1052-1070,
2001.
@Article{ ArticleBeaumont.BBPRR_ITC01,
author = {Olivier Beaumont and Vincent Boudet and Antoine Petitet and Fabrice Rastello and Yves Robert},
journal = {IEEE Trans. Computers},
title = {A proposal for a heterogeneous cluster {ScaLAPACK} (dense linear solvers)},
year = {2001},
pages = {1052-1070},
number = {10},
volume = {50}
}
-
Olivier Beaumont,
Vincent Boudet,
Fabrice Rastello,
and Yves Robert.
Matrix multiplication on heterogeneous platforms.
IEEE Trans. Parallel Distributed Systems,
12(10):1033-1051,
2001.
@Article{ ArticleBeaumont.BBRR_ITPDS01,
author = {Olivier Beaumont and Vincent Boudet and Fabrice Rastello and Yves Robert},
journal = {IEEE Trans. Parallel Distributed Systems},
title = {Matrix multiplication on heterogeneous platforms},
pages = {1033-1051},
number = {10},
volume = {12},
year = {2001}
}
-
Olivier Beaumont,
Arnaud Legrand,
Fabrice Rastello,
and Yves Robert.
Static LU decomposition on heterogeneous platforms.
Int. Journal of High Performance Computing Applications,
15(3):310-323,
2001.
@Article{ ArticleBeaumont.BLRR_IJHPCA01,
author = {Olivier Beaumont and Arnaud Legrand and Fabrice Rastello and Yves Robert},
journal = {Int. Journal of High Performance Computing Applications},
title = {Static {LU} decomposition on heterogeneous platforms},
pages = {310-323},
volume = {15},
number = {3},
year = {2001}
}
-
Vincent Boudet,
Fabrice Rastello,
and Yves Robert.
Alignment and distribution is not (always) NP-hard.
J. Parallel and Distributed Computing,
61:501-519,
2001.
@Article{ ArticleBoudet.BRR_JPDC01,
author = {Vincent Boudet and Fabrice Rastello and Yves Robert},
journal = {J. Parallel and Distributed Computing},
title = {Alignment and distribution is not (always) {NP}-hard},
pages = {501-519},
volume = {61},
year = {2001}
}
-
Eddy Caron,
Serge Chaumette,
Sylvain Contassot-Vivier,
Frédéric Desprez,
Eric Fleury,
Claude Gomez,
Maurice Goursat,
Emmanuel Jeannot,
Dominique Lazure,
Frédéric Lombard,
Jean-Marc Nicod,
Laurent Philippe,
Martin Quinson,
Pierre Ramet,
Jean Roman,
Franck Rubi,
Serge Steer,
Frédéric Suter,
and Gil Utard.
Scilab to Scilab//, the OURAGAN Project.
Parallel Computing,
11(27):1497-1519,
October 2001.
Keywords:
Scilab//,
Metacomputing.
| Abstract: |
In this paper, we present the developments realized in the OURAGAN project around the parallelization of a MATLAB-like tool called SCILAB. These developments use high-performance numerical libraries and different approaches based either on the duplication of SCILAB processes or on computational servers. This tool, SCILAB//, allows users to perform high-level operations on distributed matrices in a metacomputing environment. We also present performance results on different architectures. |
@Article{ ArticleCaron.CCCDFGGJLLNPQRRRS_PC01,
abstract = {In this paper, we present the developments realized in the OURAGAN project around the parallelization of a MATLAB-like tool called SCILAB. These developments use high-performance numerical libraries and different approaches based either on the duplication of SCILAB processes or on computational servers. This tool, SCILAB//, allows users to perform high-level operations on distributed matrices in a metacomputing environment. We also present performance results on different architectures.},
author = {Caron, Eddy and Chaumette, Serge and Contassot-Vivier, Sylvain and Desprez, Fr{\'e}d{\'e}ric and Fleury, Eric and Gomez, Claude and Goursat, Maurice and Jeannot, Emmanuel and Lazure, Dominique and Lombard, Fr{\'e}d{\'e}ric and Nicod, Jean-Marc and Philippe, Laurent and Quinson, Martin and Ramet, Pierre and Roman, Jean and Rubi, Franck and Steer, Serge and Suter, Fr{\'e}d{\'e}ric and Utard, Gil},
journal = {Parallel Computing},
keywords = {Scilab//,Metacomputing},
month = oct,
number = 27,
pages = {1497-1519},
pdf = {http://www.elsevier.nl/gej-ng/10/35/21/47/41/33/article.pdf},
title = {Scilab to Scilab//, the OURAGAN Project},
volume = 11,
year = 2001
}
-
G Piganeau,
R Westrelin,
B Tourancheau,
and C Gautier.
Multiplicative versus additive selection in relation to genome evolution: a simulation study.
Genetical Research,
78:171-175,
2001.
@Article{ ArticlePiganeau.PWTG_GR01,
author = {Piganeau, G and Westrelin, R and Tourancheau, B and Gautier, C},
journal = {Genetical Research},
pages = {171-175},
title = {Multiplicative versus additive selection in relation to genome evolution: a simulation study},
volume = {78},
year = {2001}
}
-
Bernard Tourancheau and Roland Westrelin.
Study of the medium message performance of BIP/Myrinet.
Parallel Processing Letters,
11(2/3):297-309,
2001.
@Article{ ArticleTourancheau.TW_PPL01,
author = {Tourancheau, Bernard and Westrelin, Roland},
journal = {Parallel Processing Letters},
number = {2/3},
pages = {297-309},
title = {Study of the medium message performance of {BIP/Myrinet}},
volume = {11},
year = {2001}
}
-
R. Wolski,
J. Brevik,
G. Obertelli,
N. Spring,
and A. Su.
Writing Programs that Run EveryWare on the Computational Grid.
IEEE Transactions on Parallel and Distributed Systems,
12(10):1066--1080,
October 2001.
@Article{ ArticleWolski.WBOSS_ITPDS01,
author = {R. Wolski and J. Brevik and G. Obertelli and N. Spring and A. Su},
title = {{Writing Programs that Run EveryWare on the Computational Grid}},
journal = {IEEE Transactions on Parallel and Distributed Systems},
volume = 12,
number = 10,
month = oct,
year = 2001,
pages = {1066--1080}
}
-
Patrick R. Amestoy,
Iain S. Duff,
Jean-Yves L'Excellent,
and Xiaoye S. Li.
Performance and tuning of two distributed memory sparse solvers.
In 10th SIAM Conference on Parallel Processing for Scientific Computing,
Portsmouth, Virginia,
March 2001.
@InProceedings{ InProceedingsAmestoy.ADLL_01,
author = {Patrick R. Amestoy and Iain S. Duff and Jean-Yves L'Excellent and Xiaoye S. Li},
title = {Performance and tuning of two distributed memory sparse solvers},
booktitle = {10th SIAM Conference on Parallel Processing for Scientific Computing},
address = {Portsmouth, Virginia},
month = mar,
year = 2001
}
-
Olivier Beaumont,
Vincent Boudet,
Arnaud Legrand,
Fabrice Rastello,
and Yves Robert.
Heterogeneous Matrix-Matrix Multiplication, or Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms.
In EuroMicro Workshop on Parallel and Distributed Computing (EuroMicro'2001),
pages 298-305,
2001.
IEEE Computer Society Press.
@InProceedings{ InProceedingsBeaumont.BBLRR_01,
author = {Olivier Beaumont and Vincent Boudet and Arnaud Legrand and Fabrice Rastello and Yves Robert},
booktitle = {EuroMicro Workshop on Parallel and Distributed Computing {(EuroMicro'2001)}},
publisher = {IEEE Computer Society Press},
title = {Heterogeneous Matrix-Matrix Multiplication, or Partitioning a Square into Rectangles: {NP}-Completeness and Approximation Algorithms},
pages = {298-305},
year = {2001}
}
-
Olivier Beaumont,
Arnaud Legrand,
and Yves Robert.
Master-slave tasking with heterogeneous processors.
In 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'2001),
pages 857-863,
2001.
CSREA Press.
@InProceedings{ InProceedingsBeaumont.BLR_01,
author = {Olivier Beaumont and Arnaud Legrand and Yves Robert},
booktitle = {2001 International Conference on Parallel and Distributed Processing Techniques and Applications {(PDPTA'2001)}},
publisher = {CSREA Press},
pages = {857-863},
title = {Master-slave tasking with heterogeneous processors},
year = {2001}
}
-
Olivier Beaumont,
Arnaud Legrand,
and Yves Robert.
The master-slave paradigm with heterogeneous processors.
In D.S. Katz,
T. Sterling,
M. Baker,
L. Bergman,
M. Paprzycki,
and R. Buyya, editors,
Cluster'2001,
pages 419-426,
2001.
IEEE Computer Society Press.
@InProceedings{ InProceedingsBeaumont.BLR_01*1,
author = {Olivier Beaumont and Arnaud Legrand and Yves Robert},
booktitle = {{Cluster'2001}},
publisher = {IEEE Computer Society Press},
editor = {D.S. Katz and T. Sterling and M. Baker and L. Bergman and M. Paprzycki and R. Buyya},
pages = {419-426},
title = {The master-slave paradigm with heterogeneous processors},
year = {2001}
}
-
Vincent Boudet and Yves Robert.
Scheduling heuristics for heterogeneous processors.
In 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'2001),
pages 2109-2115,
2001.
CSREA Press.
@InProceedings{ InProceedingsBoudet.BR_01,
author = {Vincent Boudet and Yves Robert},
booktitle = {2001 International Conference on Parallel and Distributed Processing Techniques and Applications {(PDPTA'2001)}},
publisher = {CSREA Press},
pages = {2109-2115},
title = {Scheduling heuristics for heterogeneous processors},
year = {2001}
}
-
Eddy Caron.
Inversion matricielle parallèle de grande taille.
In RenPar'13. 13èmes Rencontres francophones du Parallélisme des Architectures et des Systèmes. Paris, Cité des Sciences et de l'Industrie de la Vilette. France,
pages 1-6,
April 2001.
Keywords:
Out-of-core.
@InProceedings{ InProceedingsCaron.C_01,
author = {Caron, Eddy},
booktitle = {Ren{P}ar'13. 13{\`e}mes {R}encontres francophones du {P}arall{\'e}lisme des Architectures et des Syst{\`e}mes. Paris, Cit{\'e} des Sciences et de l'Industrie de la Vilette. France},
keywords = {Out-of-core},
month = apr,
pages = {1-6},
postscript = {http://www.ens-lyon.fr/~ecaron/biblio/papers/renpar01_ec.ps.gz},
title = {Inversion matricielle parall{\`e}le de grande taille},
year = {2001}
}
-
Alain Darte,
Yves Robert,
and Frédéric Vivien.
Loop parallelization algorithms.
In Compiler Optimizations for Scalable Parallel Systems: Languages, Compilation Techniques and Run Time Systems,
LNCS 1808,
pages 141-171,
2001.
Springer Verlag.
@InProceedings{ InProceedingsDarte.DRV_01,
author = {Alain Darte and Yves Robert and Fr\'ed\'eric Vivien},
booktitle = {Compiler Optimizations for Scalable Parallel Systems: Languages, Compilation Techniques and Run Time Systems},
publisher = {Springer Verlag},
series = {LNCS 1808},
title = {Loop parallelization algorithms},
pages = {141-171},
year = {2001}
}
-
Frédéric Desprez,
Martin Quinson,
and Frédéric Suter.
Dynamic Performance Forecasting for Network-Enabled Servers in a Heterogeneous Environment.
In H.R. Arabnia, editor,
Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA),
volume III,
Las Vegas,
pages 1421-1427,
June 2001.
CSREA Press.
Note: ISBN: 1-892512-69-6.
Keywords:
Performance Forecasting,
FAST.
@InProceedings{ InProceedingsDesprez.DQS_01,
author = {Desprez, Fr\'ed\'eric and Quinson, Martin and Suter, Fr\'ed\'eric},
title = {{Dynamic Performance Forecasting for Network-Enabled Servers in a Heterogeneous Environment}},
booktitle = {Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA)},
pages = {1421-1427},
year = 2001,
editor = {H.R. Arabnia},
volume = {III},
address = {Las Vegas},
month = jun,
publisher = {CSREA Press},
note = {ISBN: 1-892512-69-6},
keywords = {Performance Forecasting, FAST}
}
-
Benjamin Gaidioz,
Pascale Primet,
and Bernard Tourancheau.
Differentiated Fairness: Model and Implementation.
In HPSR : High Performance Switching and Routing,
Dallas, USA,
pages 260--264,
May 2001.
IEEE.
@InProceedings{ InProceedingsGaidioz.GPT_01,
address = {Dallas, {USA}},
author = {Gaidioz, Benjamin and Primet, Pascale and Tourancheau, Bernard},
booktitle = {HPSR : High Performance Switching and Routing},
month = may,
pages = {260--264},
publisher = {IEEE},
title = {Differentiated Fairness: Model and Implementation},
year = {2001}
}
-
P. Geoffray,
C. Pham,
L. Prylli,
B. Tourancheau,
and R. Westrelin.
Protocols and Software for Exploiting Myrinet Clusters.
In Proceedings of the International Conference on Computational Science (ICCS 2001),
number 2073&2074 of LNCS,
San Francisco, CA, USA,
pages 233-242,
May 2001.
Springer-Verlag.
@InProceedings{ InProceedingsGeoffray.GPPTW_01,
address = {San Francisco, CA, USA},
author = {P. Geoffray and C. Pham and L. Prylli and B. Tourancheau and R. Westrelin},
booktitle = {Proceedings of the International Conference on Computational Science (ICCS 2001)},
month = may,
number = {2073\&2074},
pages = {233-242},
publisher = {Springer-Verlag},
series = {LNCS},
title = {Protocols and Software for Exploiting Myrinet Clusters},
url = {http://bat710.univ-lyon1.fr/~cpham/Paper/ICCS-CCIU.ps.gz},
year = {2001}
}
-
L. Lefèvre,
C. Pham,
P. Primet,
B. Tourancheau,
B. Gaidioz,
J.P. Gelas,
and M. Maimour.
Active Networking Support for the Grid.
In Noaki Wakamiya Ian W. Marshall, Scott Nettles, editor,
IFIP-TC6 Third International Working Conference on Active Networks, IWAN 2001,
volume 2207 of Lecture Notes in Computer Science,
pages 16-33,
October 2001.
Note: ISBN: 3-540-42678-7.
@InProceedings{ InProceedingsLefevre.LPPTGGM_01,
author = {L. Lef\`evre and C. Pham and P. Primet and B. Tourancheau and B. Gaidioz and J.P. Gelas and M. Maimour},
booktitle = {IFIP-TC6 Third International Working Conference on Active Networks, IWAN 2001},
editor = {Ian W. Marshall, Scott Nettles, Noaki Wakamiya},
month = oct,
note = {ISBN: 3-540-42678-7},
pages = {16-33},
series = {Lecture Notes in Computer Science},
title = {Active Networking Support for the Grid},
url = {http://bat710.univ-lyon1.fr/~cpham/Paper/IWAN01.ps.gz},
volume = {2207},
year = {2001}
}
-
Arnaud Legrand.
Équilibrage de charge statique pour la décomposition LU sur une plate-forme hétérogène.
In 13e Rencontres Francophones du Parallélisme des Architectures et des Systèmes,
Paris, La Villette,
24-27 Avril 2001.
| Abstract: |
Dans cet article, nous nous int\'eressons \`a des sch\'emas distribution des donn\'ees pour des noyaux d'alg\`ebre lin\'eaire (tels que le produit de matrices ou la d\'ecomposition LU) adapt\'es aux plates-formes h\'et\'erog\`enes. Les distributions cycliques par blocs utilis\'ees dans ScaLAPACK ne sont plus adapt\'ees \`a de telles plates-formes et ne permettent pas d'obtenir un bon \'equilibrage de charge. Le r\'esultat principal de cet article porte sur une technique de distribution des donn\'ees qui permet d'obtenir un \'equilibrage de charge asymptotiquement optimal pour les d\'ecompositions LU, et qui peut donc servir de fondement \`a la mise en oeuvre d'une version de ScaLAPACK h\'et\'erog\`ene |
@InProceedings{ InProceedingsLegrand.L_01,
author = {Arnaud Legrand},
title = {\'Equilibrage de charge statique pour la d\'ecomposition {LU} sur une plate-forme h\'et\'erog\`ene},
booktitle = {13e Rencontres Francophones du Parall\'elisme des Architectures et des Syst\`emes},
year = {2001},
address = {Paris, La Villette},
month = {24-27 Avril},
postscript = {articles/renpar01.ps.gz},
abstract = {Dans cet article, nous nous int\'eressons \`a des sch\'emas distribution des donn\'ees pour des noyaux d'alg\`ebre lin\'eaire (tels que le produit de matrices ou la d\'ecomposition LU) adapt\'es aux plates-formes h\'et\'erog\`enes. Les distributions cycliques par blocs utilis\'ees dans ScaLAPACK ne sont plus adapt\'ees \`a de telles plates-formes et ne permettent pas d'obtenir un bon \'equilibrage de charge. Le r\'esultat principal de cet article porte sur une technique de distribution des donn\'ees qui permet d'obtenir un \'equilibrage de charge asymptotiquement optimal pour les d\'ecompositions LU, et qui peut donc servir de fondement \`a la mise en oeuvre d'une version de ScaLAPACK h\'et\'erog\`ene}
}
-
Frédéric Lombard,
Martin Quinson,
and Frédéric Suter.
Une approche extensible des serveurs de calcul.
In Treizièmes Rencontres Francophones du Parallélisme des Architectures et des Systèmes,
Paris, La Villette,
pages 79-84,
apr # 24-26 2001.
Keywords:
Metacomputing,
DIET.
@InProceedings{ InProceedingsLombard.LQS_01,
author = {Lombard, Fr\'ed\'eric and Quinson, Martin and Suter, Fr\'ed\'eric},
title = {{Une approche extensible des serveurs de calcul}},
booktitle = {Treizi\`emes Rencontres Francophones du Parall\'elisme des Architectures et des Syst\`emes},
year = 2001,
pages = {79-84},
address = {Paris, La Villette},
month = apr # "24-26",
keywords = {Metacomputing, DIET}
}
-
Jean-Marc Nicod.
DIET: Distributed Interactive Engineering Toolbox.
In Management of Metacomputers, Seminar N. 01241, Report N. 310,
Dagstuhl, Germany,
May 2001.
Note: Invited Talk.
Keywords:
DIET.
@InProceedings{ InProceedingsNicod.N_01,
author = {Nicod, Jean-Marc},
title = {{DIET: Distributed Interactive Engineering Toolbox}},
booktitle = {Management of Metacomputers, Seminar N.~01241, Report N.~310},
address = {Dagstuhl, Germany},
note = {Invited Talk},
month = may,
year = 2001,
keywords = {DIET}
}
-
Martin Quinson.
Un outil de modélisation de performances dans un environnement de metacomputing.
In 13e Rencontres Francophones du Parallélisme des Architectures et des Systèmes,
Paris, La Villette,
apr # 24-27 2001.
@InProceedings{ InProceedingsQuinson.Q_01,
author = {Martin Quinson},
title = {Un outil de mod\'elisation de performances dans un environnement de metacomputing},
booktitle = {13e Rencontres Francophones du Parall\'elisme des Architectures et des Syst\`emes},
address = {Paris, La Villette},
month = apr # "24-27",
year = {2001}
}
-
William Thies,
Frédéric Vivien,
Jeffrey Sheldon,
and Saman Amarasinghe.
A Unified Framework for Schedule and Storage Optimization.
In Proceedings of the ACM SIGPLAN'01 conference on Programming Language Design and Implementation (PLDI),
Snowbird, UT, USA,
pages 232--242,
June 2001.
@InProceedings{ InProceedingsThies.TVSA_01,
author = {William Thies and Fr\'ed\'eric Vivien and Jeffrey Sheldon and Saman Amarasinghe},
title = {A {U}nified {F}ramework for {S}chedule and {S}torage {O}ptimization},
booktitle = {Proceedings of the ACM SIGPLAN'01 conference on Programming Language Design and Implementation (PLDI)},
pages = {232--242},
year = 2001,
address = {Snowbird, UT, USA},
month = jun
}
-
Bernard Tourancheau and Roland Westrelin.
Support for MPI at the network interface level.
In 8th European PVM/MPI Users Group Meeting,
volume 2131,
Santorini (Thera) Island, Greece,
pages 52-60,
September 2001.
Springer - Verlag.
@InProceedings{ InProceedingsTourancheau.TW_01,
address = {Santorini (Thera) Island, Greece},
author = {Tourancheau, Bernard and Westrelin, Roland},
booktitle = {8th European {PVM/MPI} Users Group Meeting},
month = sep,
volume = 2131,
pages = {52-60},
publisher = {Springer - Verlag},
title = {Support for {MPI} at the network interface level},
year = 2001
}
-
Frédéric Vivien and Martin Rinard.
Incrementalized Pointer and Escape Analysis.
In Proceedings of the ACM SIGPLAN'01 conference on Programming Language Design and Implementation (PLDI),
Snowbird, UT, USA,
pages 35--46,
June 2001.
@InProceedings{ InProceedingsVivien.VR_01,
author = {Fr\'ed\'eric Vivien and Martin Rinard},
title = {Incrementalized {P}ointer and {E}scape {A}nalysis},
booktitle = {Proceedings of the ACM SIGPLAN'01 conference on Programming Language Design and Implementation (PLDI)},
pages = {35--46},
year = 2001,
address = {Snowbird, UT, USA},
month = jun
}
-
Olivier Beaumont,
Larry Carter,
Jeanne Ferrante,
Arnaud Legrand,
and Yves Robert.
Bandwidth-centric allocation of independent tasks on heterogeneous platforms.
Technical report 2001-25,
LIP,
June 2001.
| Abstract: |
In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogenerous grid computing platform. Such problems arise in collaborative computing efforts like SETI@home. We use a tree to model a grid, where resources can have different speeds of computation and communication, as well as different overlap capabilities. We define a base model, and show how to determine the maximum steady-state throughput of a node in the base model, assuming we already know the throughput of the subtrees rooted at the node's children. Thus, a bottom-up traversal of the tree determines the rate at which tasks can be processed in the full tree. The best allocation is {\em bandwidth-centric}: if enough bandwidth is available, then all nodes are kept busy; if bandwidth is limited, then tasks should be allocated only to the children which have sufficiently small communication times, regardless of their computation power. We then show how nodes with other capabilities --- ones that allow more or less overlapping of computation and communication than the base model --- can be transformed to equivalent nodes in the base model. We also show how to handle a more general communication model. Finally, we present simulation results of several demand-driven task allocation policies that show that our bandwidth-centric method obtains better results than allocating tasks to all processors on a first-come, first serve basis. |
@TechReport{ TechReportRR-LIP-2001-25,
author = {Olivier Beaumont and Larry Carter and Jeanne Ferrante and Arnaud Legrand and Yves Robert},
title = {Bandwidth-centric allocation of independent tasks on heterogeneous platforms},
institution = {LIP},
year = {2001},
number = {2001-25},
month = jun,
postscript = {ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR2001/RR2001-25.ps.Z},
abstract = {In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogenerous grid computing platform. Such problems arise in collaborative computing efforts like SETI@home. We use a tree to model a grid, where resources can have different speeds of computation and communication, as well as different overlap capabilities. We define a base model, and show how to determine the maximum steady-state throughput of a node in the base model, assuming we already know the throughput of the subtrees rooted at the node's children. Thus, a bottom-up traversal of the tree determines the rate at which tasks can be processed in the full tree. The best allocation is {\em bandwidth-centric}: if enough bandwidth is available, then all nodes are kept busy; if bandwidth is limited, then tasks should be allocated only to the children which have sufficiently small communication times, regardless of their computation power. We then show how nodes with other capabilities --- ones that allow more or less overlapping of computation and communication than the base model --- can be transformed to equivalent nodes in the base model. We also show how to handle a more general communication model. Finally, we present simulation results of several demand-driven task allocation policies that show that our bandwidth-centric method obtains better results than allocating tasks to all processors on a first-come, first serve basis.}
}
-
Olivier Beaumont,
Arnaud Legrand,
and Yves Robert.
Data Allocation Strategies for Dense Linear Algebra on two-dimensional Grids with Heterogeneous Communication Links.
Technical report 2001-14,
LIP,
April 2001.
| Abstract: |
In this paper, we study the implementation of dense linear algebra kernels, such as matrix multiplication on 2D grids with homogeneous processors when the communication links between the processors are heterogeneous (i.e. the time to transfer a block of the matrix between two processors depends on these processors). We prove that finding the best allocation of the processors into a grid, with respect to the minimization of the communication overhead, is a NP-complete problem. |
@TechReport{ TechReportRR-LIP-2001-14,
author = {Olivier Beaumont and Arnaud Legrand and Yves Robert},
title = {Data Allocation Strategies for Dense Linear Algebra on two-dimensional Grids with Heterogeneous Communication Links},
institution = {LIP},
year = {2001},
number = {2001-14},
month = apr,
postscript = {ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR2001/RR2001-14.ps.Z},
abstract = {In this paper, we study the implementation of dense linear algebra kernels, such as matrix multiplication on 2D grids with homogeneous processors when the communication links between the processors are heterogeneous (i.e. the time to transfer a block of the matrix between two processors depends on these processors). We prove that finding the best allocation of the processors into a grid, with respect to the minimization of the communication overhead, is a NP-complete problem.}
}
-
Olivier Beaumont,
Arnaud Legrand,
and Yves Robert.
The Master-Slave Paradigm with Heterogeneous Processors.
Technical report 2001-13,
LIP,
March 2001.
| Abstract: |
In this paper, we revisit the master-slave tasking paradigm in the context of heterogeneous processors. We assume that communications take place in exclusive mode. We present a polynomial algorithm that gives the optimal solution when a single communication is needed before the execution of the tasks on the slave processors. When communications are required both before and after the task processing, we show that the problem is at least as difficult as a problem whose complexity is open. In this case, we present a guaranteed approximation algorithm. Finally, we present asymptotically optimal algorithms when communications are required before the processing of each task, or both before and after the processing of each task. |
@TechReport{ TechReportRR-LIP-2001-13,
author = {Olivier Beaumont and Arnaud Legrand and Yves Robert},
title = {The Master-Slave Paradigm with Heterogeneous Processors},
institution = {LIP},
year = {2001},
number = {2001-13},
month = mar,
postscript = {ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR2001/RR2001-13.ps.Z},
abstract = {In this paper, we revisit the master-slave tasking paradigm in the context of heterogeneous processors. We assume that communications take place in exclusive mode. We present a polynomial algorithm that gives the optimal solution when a single communication is needed before the execution of the tasks on the slave processors. When communications are required both before and after the task processing, we show that the problem is at least as difficult as a problem whose complexity is open. In this case, we present a guaranteed approximation algorithm. Finally, we present asymptotically optimal algorithms when communications are required before the processing of each task, or both before and after the processing of each task.}
}
-
Anne Benoit,
Brigitte Plateau,
and William J. Stewart.
Memory Efficient Iterative Methods for Stochastic Automata Networks.
Research Report 4259,
INRIA,
September 2001.
@TechReport{ TechReportRR-INRIA-4259,
author = {Benoit, Anne and Plateau, Brigitte and Stewart, William J.},
title = {{Memory Efficient Iterative Methods for Stochastic Automata Networks}},
institution = {INRIA},
year = 2001,
number = 4259,
month = sep,
type = {Research Report}
}
-
Eddy Caron,
Serge Chaumette,
Sylvain Contassot-Vivier,
Frédéric Desprez,
Eric Fleury,
Claude Gomez,
Maurice Goursat,
Emmanuel Jeannot,
Dominique Lazure,
Frédéric Lombard,
Jean-Marc Nicod,
Laurent Philippe,
Martin Quinson,
Pierre Ramet,
Jean Roman,
Franck Rubi,
Serge Steer,
Frédéric Suter,
and Gil Utard.
Scilab to Scilab//: the OURAGAN Project..
Research report 2001-24,
Laboratoire de l'Informatique du Parallélisme (LIP),
June 2001.
Note: Also available as INRIA Research Report RR-4203.
Keywords:
Scilab//.
@TechReport{ TechReportRR-Laboratoire-2001-24,
author = {Caron, Eddy and Chaumette, Serge and Contassot-Vivier, Sylvain and Desprez, Fr{\'e}d{\'e}ric and Fleury, Eric and Gomez, Claude and Goursat, Maurice and Jeannot, Emmanuel and Lazure, Dominique and Lombard, Fr{\'e}d{\'e}ric and Nicod, Jean-Marc and Philippe, Laurent and Quinson, Martin and Ramet, Pierre and Roman, Jean and Rubi, Franck and Steer, Serge and Suter, Fr{\'e}d{\'e}ric and Utard, Gil},
institution = {Laboratoire de l'Informatique du Parall{\'e}lisme (LIP)},
keywords = {Scilab//},
month = jun,
note = {Also available as INRIA Research Report RR-4203},
number = {2001-24},
postscript = {ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR2001/RR2001-24.ps.Z},
title = {Scilab to Scilab//: the OURAGAN Project.},
type = {Research report},
year = {2001}
}
-
Eddy Caron,
Serge Chaumette,
Sylvain Contassot-Vivier,
Frédéric Desprez,
Eric Fleury,
Claude Gomez,
Maurice Goursat,
Emmanuel Jeannot,
Dominique Lazure,
Frédéric Lombard,
Jean-Marc Nicod,
Laurent Philippe,
Martin Quinson,
Pierre Ramet,
Jean Roman,
Franck Rubi,
Serge Steer,
Frédéric Suter,
and Gil Utard.
Scilab to Scilab//: the OURAGAN Project..
Research report RR4203,
Institut National de Recherche en Informatique et en Automatique (INRIA),
June 2001.
Note: Also available as LIP Research Report 2001-24.
Keywords:
Scilab//.
@TechReport{ TechReportRR-Institut-RR4203,
author = {Caron, Eddy and Chaumette, Serge and Contassot-Vivier, Sylvain and Desprez, Fr{\'e}d{\'e}ric and Fleury, Eric and Gomez, Claude and Goursat, Maurice and Jeannot, Emmanuel and Lazure, Dominique and Lombard, Fr{\'e}d{\'e}ric and Nicod, Jean-Marc and Philippe, Laurent and Quinson, Martin and Ramet, Pierre and Roman, Jean and Rubi, Franck and Steer, Serge and Suter, Fr{\'e}d{\'e}ric and Utard, Gil},
institution = {Institut National de Recherche en Informatique et en Automatique (INRIA)},
keywords = {Scilab//},
month = jun,
note = {Also available as LIP Research Report 2001-24},
number = {RR4203},
postscript = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-4203.ps.gz},
title = {Scilab to Scilab//: the OURAGAN Project.},
type = {Research report},
year = 2001
}
-
Frédéric Desprez and Emmanuel Jeannot.
Adding Data Persistence and Reddistribution to NetSolve.
Research report 2001-39,
LIP,
December 2001.
@TechReport{ TechReportRR-LIP-2001-39,
author = {Desprez, Fr\'ed\'eric and Jeannot, Emmanuel},
institution = {LIP},
title = {Adding Data Persistence and Reddistribution to NetSolve},
number = {2001-39},
type = {Research report},
month = dec,
year = {2001}
}
-
Frédéric Desprez,
Martin Quinson,
and Frédéric Suter.
Dynamic Performance Forecasting for Network Enabled Servers in a Heterogeneous Environment.
Research report RR-4320,
Institut National de Recherche en Informatique et en Automatique (INRIA),
November 2001.
Note: Also available as LIP Research Report 2001-40.
Keywords:
Performance Forecasting,
FAST.
@TechReport{ TechReportRR-Institut-RR-4320,
author = {Desprez, Fr\'ed\'eric and Quinson, Martin and Suter, Fr\'ed\'eric},
title = {{Dynamic Performance Forecasting for Network Enabled Servers in a Heterogeneous Environment}},
institution = {Institut National de Recherche en Informatique et en Automatique (INRIA)},
year = 2001,
number = {RR-4320},
month = nov,
note = {Also available as LIP Research Report 2001-40},
postscript = "ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-4320.ps.gz",
type = {Research report},
keywords = {Performance Forecasting, FAST}
}
-
Frédéric Desprez,
Martin Quinson,
and Frédéric Suter.
Dynamic Performance Forecasting for Network Enabled Servers in a Heterogeneous Environment.
Research report 2001-40,
Laboratoire de l'Informatique du Parallélisme (LIP),
November 2001.
Note: Also available as INRIA Research Report RR-4320.
Keywords:
Performance Forecasting,
FAST.
@TechReport{ TechReportRR-Laboratoire-2001-40,
author = {Desprez, Fr\'ed\'eric and Quinson, Martin and Suter, Fr\'ed\'eric},
title = {{Dynamic Performance Forecasting for Network Enabled Servers in a Heterogeneous Environment}},
institution = {Laboratoire de l'Informatique du Parall\'elisme (LIP)},
year = 2001,
number = {2001-40},
month = nov,
note = {Also available as INRIA Research Report RR-4320},
postscript = "ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR2001/RR2001-40.ps.Z",
type = {Research report},
keyword = {Performance Forecasting, FAST}
}