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.