Scheduling Instructions on Hierarchical Machines

Abstract : The aim of this work is to study the problem of scheduling fine grain task graphs on hierarchical distributed systems with communication delay. We consider as a case study how to schedule the instructions on a processor that implements incomplete bypass ( ST200). We show first how this problem can be expressed as scheduling unitary tasks on a hierarchical architecture with heavy communications between clustered units. The proposed analysis is generic and can be extended to other challenging problems like scheduling in clusters of multi-cores. Our main result is an approximation algorithm based on list scheduling whose approximation ratio is the minimum of two expressions, the first one depends on the number of clusters while the second one depends on the communication delay. Experiments run on random graphs and on structured graphs demonstrate the effectiveness of the proposed approach.
Type de document :
Communication dans un congrès
11th International Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC 2010), 2010, Atlanta, United States. 2010, 〈10.1109/IPDPSW.2010.5470711〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00798448
Contributeur : Grégory Mounié <>
Soumis le : vendredi 8 mars 2013 - 15:31:56
Dernière modification le : mercredi 11 avril 2018 - 01:53:31

Lien texte intégral

Identifiants

Citation

Florent Blachot, Guillaume Huard, Johnatan Pecero Sanchez, Érik Saule, Denis Trystram. Scheduling Instructions on Hierarchical Machines. 11th International Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC 2010), 2010, Atlanta, United States. 2010, 〈10.1109/IPDPSW.2010.5470711〉. 〈hal-00798448〉

Partager

Métriques

Consultations de la notice

301