Skip to Main content Skip to Navigation
Journal articles

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 metadata
Contributor : Pascal Benoit <>
Submitted on : Tuesday, May 25, 2021 - 11:17:03 AM
Last modification on : Wednesday, May 26, 2021 - 12:53:54 PM
Long-term archiving on: : Thursday, August 26, 2021 - 6:53:05 PM


Publisher files allowed on an open archive


Distributed under a Creative Commons Attribution 4.0 International License




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, pp.#453970. ⟨10.1155/2009/453970⟩. ⟨lirmm-00394624⟩



Record views


Files downloads