A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network-On-Chips
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 difficu...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2009-01-01
|
| Series: | International Journal of Reconfigurable Computing |
| Online Access: | http://dx.doi.org/10.1155/2009/453970 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832568204120031232 |
|---|---|
| author | Peter Zipf Gilles Sassatelli Nurten Utlu Nicolas Saint-Jean Pascal Benoit Manfred Glesner |
| author_facet | Peter Zipf Gilles Sassatelli Nurten Utlu Nicolas Saint-Jean Pascal Benoit Manfred Glesner |
| author_sort | Peter Zipf |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-3123f5bf49f54108bff086b87576f0b8 |
| institution | Kabale University |
| issn | 1687-7195 1687-7209 |
| language | English |
| publishDate | 2009-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Reconfigurable Computing |
| spelling | doaj-art-3123f5bf49f54108bff086b87576f0b82025-02-03T00:59:34ZengWileyInternational Journal of Reconfigurable Computing1687-71951687-72092009-01-01200910.1155/2009/453970453970A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network-On-ChipsPeter Zipf0Gilles Sassatelli1Nurten Utlu2Nicolas Saint-Jean3Pascal Benoit4Manfred Glesner5Digital Technology Lab, University of Kassel, Wilhelmshöher Allee 73, 34121 Kassel, GermanyLaboratoire d'Informatique, de Robotique et de Microélectroniqe de Montpellier (LIRMM), University of Montpellier II, UMR CNRS 5506, 161 rue ADA, 34392 Montpellier Cedex 5, FranceInstitute of Microelectronic Systems, Darmstadt University of Technology , Karlstrasse 15, 64283 Darmstadt, GermanyLaboratoire d'Informatique, de Robotique et de Microélectroniqe de Montpellier (LIRMM), University of Montpellier II, UMR CNRS 5506, 161 rue ADA, 34392 Montpellier Cedex 5, FranceLaboratoire d'Informatique, de Robotique et de Microélectroniqe de Montpellier (LIRMM), University of Montpellier II, UMR CNRS 5506, 161 rue ADA, 34392 Montpellier Cedex 5, FranceInstitute of Microelectronic Systems, Darmstadt University of Technology , Karlstrasse 15, 64283 Darmstadt, GermanyWe 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.http://dx.doi.org/10.1155/2009/453970 |
| spellingShingle | Peter Zipf Gilles Sassatelli Nurten Utlu Nicolas Saint-Jean Pascal Benoit Manfred Glesner A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network-On-Chips International Journal of Reconfigurable Computing |
| title | A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network-On-Chips |
| title_full | A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network-On-Chips |
| title_fullStr | A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network-On-Chips |
| title_full_unstemmed | A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network-On-Chips |
| title_short | A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network-On-Chips |
| title_sort | decentralised task mapping approach for homogeneous multiprocessor network on chips |
| url | http://dx.doi.org/10.1155/2009/453970 |
| work_keys_str_mv | AT peterzipf adecentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT gillessassatelli adecentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT nurtenutlu adecentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT nicolassaintjean adecentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT pascalbenoit adecentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT manfredglesner adecentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT peterzipf decentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT gillessassatelli decentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT nurtenutlu decentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT nicolassaintjean decentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT pascalbenoit decentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips AT manfredglesner decentralisedtaskmappingapproachforhomogeneousmultiprocessornetworkonchips |