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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00394624
Contributor : Pascal Benoit <>
Submitted on : Friday, June 12, 2009 - 11:23:47 AM
Last modification on : Tuesday, June 26, 2018 - 1:18:34 AM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

412