A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network‐On‐Chips
Authors:
Open Access
- 1 January 2009
- journal article
- research article
- Published by Wiley in International Journal of Reconfigurable Computing
- Vol. 2009 (1)
Abstract
We present a heuristic algorithm for the run‐time distribution of task sets in a homogeneous Multiprocessor network‐on‐chip. The algorithm is itself distributed over the processors and thus can be applied to systems of arbitrary size. Also, tasks added at run‐time can be handled without any difficulty, allowing for inline optimisation. Based on local information on processor workload, task size, communication requirements, and link contention, iterative decisions on task migrations to other processors are made. The mapping results for several example task sets are first compared with those of an exact (enumeration) algorithm with global information for a 3 × 3 processor array. The results show that the mapping quality achieved by our distributed algorithm is within 25% of that of the exact algorithm. For larger array sizes, simulated annealing is used as a reference and the behaviour of our algorithm is investigated. The mapping quality of the algorithm can be shown to be within a reasonable range (below 30% mostly) of the reference. 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.Keywords
This publication has 20 references indexed in Scilit:
- Energy- and performance-aware mapping for regular NoC architecturesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005
- Network-on-chip architectures and design methodsIEE Proceedings - Computers and Digital Techniques, 2005
- Performance optimization of a de-centralized task allocation protocol via bandwidth and buffer management2004
- Dynamic Mapping and Ordering Tasks of Embedded Real-Time Systems on Multiprocessor PlatformsLecture Notes in Computer Science, 2004
- Comparing distributed memory and virtual shared memory parallel programming modelsFuture Generation Computer Systems, 1995
- Mapping Tasks to Processors to Minimize Communication Time in a Multiprocessor System1995
- Heuristic algorithms for task assignment in distributed systemsIEEE Transactions on Computers, 1988
- Heuristic Models of Task Assignment Scheduling in Distributed SystemsComputer, 1982
- Task Allocation in Distributed Data ProcessingComputer, 1980
- P-Complete Approximation ProblemsJournal of the ACM, 1976