A Decentralised Task Mapping Approach for Homogeneous Multi-Processor Network-on-Chips

Abstract : This paper presents a heuristic algorithm for the run- time distribution of task sets in a homogeneous multi- processor network-on-chip. The algorithm is itself dis- tributed over the processors and thus can be applied to systems of arbitrary size. Based on local information on processor workload, task size, communication require- ments, and link contention, iterative decisions on task mi- grations to other processors are made. The heuristic as well as the underlying multi-processor network-on-chip are described and the mapping results are compared with those of an exact (enumeration) algorithm with global in- formation. A number of example task sets shows that the mapping results achieved by the heuristic are within 25% of those of the exact algorithm for a 3×3 processor ar- ray. Also, tasks added at run-time can be handled with- out any difficulty, allowing for inline optimisation. This adaptability and the low computation and communication overhead of the distributed heuristic clearly indicate that decentralised algorithms are a favourable solution for an automatic task distribution.
Type de document :
Article dans une revue
International Journal of Reconfigurable Computing, Hindawi Publishing Corporation, 2009, 2009 (Article ID 453970), pp.14. 〈10.1155/2009/453970〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00394624
Contributeur : Pascal Benoit <>
Soumis le : vendredi 12 juin 2009 - 11:23:47
Dernière modification le : mardi 26 juin 2018 - 01:18:34

Lien texte intégral

Identifiants

Collections

Citation

Peter Zipf, Gilles Sassatelli, Nurten Utlu, Nicolas Saint-Jean, Pascal Benoit, et al.. A Decentralised Task Mapping Approach for Homogeneous Multi-Processor Network-on-Chips. International Journal of Reconfigurable Computing, Hindawi Publishing Corporation, 2009, 2009 (Article ID 453970), pp.14. 〈10.1155/2009/453970〉. 〈lirmm-00394624〉

Partager

Métriques

Consultations de la notice

213