Algorithms and Tools for (Distributed) Heterogeneous Computing: A Prospective Report

We discuss algorithms and tools to help program and use metacomputing resources in the forthcoming years. Metacomputing with highly distributed heterogeneous environments stands to become a major, if not dominant, method to implement all kinds of parallel applications. In this report, we survey some general aspects of metacomputing (hardware, system and administration issues, as well as the application field). Next we identify some algorithmic issues and software challenges that must be solved to efficiently program and/or transparently use such platforms: - Data decomposition techniques for cluster computing, - Granularity issues for metacomputing, - Scheduling and load-balancing methods, - Programming models. We illustrate each of these issues and challenges by the analysis of several case studies: Cluster ScaLAPACK, AppLeS, Globus, Legion, Albatross and Netsolve. We conclude this report by stating some final remarks and recommendations.Le calcul distribué à hautes performances, encore appellé ``metacomputing'', constitue aujourd'hui une des approches les plus prometteuses pour implémenter des applications parallèles. Ce rapport présente une synthèse des outils facilitant la programmation et l'utilisation des ressources du métacomputing, et discute les nouvelles techniques algorithmiques à mettre en oeuvre pour utiliser efficacement de telles plateformes. Dans la première partie, nous introduisons les principes généraux du métacomputing (infrastructures matérielles, systèmes et environnements, administration ainsi que le champ applicatif). Nous détaillons ensuite quelques uns des nouveaux problèmes algorithmiques et les challenges logiciels pour pouvoir programmer efficacement et/ou utiliser de manière transparente ces nouvelles infrastructures: - Techniques d'allocation de données pour le calcul sur les grappes, - Problèmes de granularité pour le métacomputing, - Méthodes pour ordonnancer et réguler la charge de calcul, - Modèles de programmation. Nous illustrons cette étude par l'analyse de plusieurs projets: Cluster ScaLAPACK, AppLeS, Globus, Legion, Albatross et Netsolve. Nous concluons ce rapport avec un certain nombre de recommandations sur les directions à suivre dans ce nouveau domaine de recherche