{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:45:48Z","timestamp":1759146348548,"version":"3.41.2"},"reference-count":26,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2009,8,9]],"date-time":"2009-08-09T00:00:00Z","timestamp":1249776000000},"content-version":"vor","delay-in-days":220,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["International Journal of Reconfigurable Computing"],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We present a heuristic algorithm for the run\u2010time distribution of task sets in a homogeneous Multiprocessor network\u2010on\u2010chip. The algorithm is itself distributed over the processors and thus can be applied to systems of arbitrary size. Also, tasks added at run\u2010time 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 \u00d7 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.<\/jats:p>","DOI":"10.1155\/2009\/453970","type":"journal-article","created":{"date-parts":[[2009,8,10]],"date-time":"2009-08-10T09:01:51Z","timestamp":1249894911000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A Decentralised Task Mapping Approach for Homogeneous Multiprocessor Network\u2010On\u2010Chips"],"prefix":"10.1155","volume":"2009","author":[{"given":"Peter","family":"Zipf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gilles","family":"Sassatelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nurten","family":"Utlu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Saint-Jean","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Benoit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred","family":"Glesner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2009,8,9]]},"reference":[{"key":"e_1_2_7_1_2","doi-asserted-by":"publisher","DOI":"10.1049\/ip\u2010cdt:20045100"},{"key":"e_1_2_7_2_2","doi-asserted-by":"crossref","unstructured":"BertozziS. AcquavivaA. BertozziD. andPoggialiA. Supporting task migration in multi-processor systems-on-chip: a feasibility study 1 Proceedings of the Conference on Design Automation and Test in Europe (DATE \u203206) March 2006 Munich Germany 1\u20136 EID2-s2.0-34047096657.","DOI":"10.1109\/DATE.2006.243952"},{"key":"e_1_2_7_3_2","doi-asserted-by":"crossref","unstructured":"BraunT. D. SiegelH. J. BeckN.et al. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems Proceedings of the 8th Heterogeneous Computing Workshop (HCW \u203299) April 1999 San Juan Puerto Rico 15\u201329 EID2-s2.0-0032591263.","DOI":"10.1109\/HCW.1999.765093"},{"key":"e_1_2_7_4_2","doi-asserted-by":"crossref","unstructured":"CarvalhoE. ecarvalho@inf.pucrs.br CalazansN. andcalazans@inf.pucrs.br MoraesF. moraes@inf.pucrs.br Congestion-aware task mapping in NoC-based MPSoCs with dynamic workload Proceedings of IEEE Computer Society Annual Symposium on VLSI (ISVLSI \u203207) March 2007 Porto Alegre Brazil 459\u2013460 EID2-s2.0-36349030136 https:\/\/doi.org\/10.1109\/ISVLSI.2007.32.","DOI":"10.1109\/ISVLSI.2007.32"},{"key":"e_1_2_7_5_2","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-1-4615-2223-2_3","volume-title":"The Impact of Emerging Technologies of Computer Science and Operations Research","author":"Chakrapani J.","year":"1995"},{"key":"e_1_2_7_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1980.1653419"},{"key":"e_1_2_7_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1982.1654050"},{"key":"e_1_2_7_8_2","first-page":"653","article-title":"Fundamentals of scatter search and path relinking","volume":"29","author":"Glover F.","year":"2000","journal-title":"Control and Cybernetics"},{"key":"e_1_2_7_9_2","doi-asserted-by":"crossref","unstructured":"HenkelJ. WolfW. andChakradharS. On-chip networks: a scalable communication-centric embedded system design paradigm Proceedings of the 17th IEEE International Conference on VLSI Design January 2004 Mumbai India 845\u2013851 EID2-s2.0-2342548153.","DOI":"10.1109\/ICVD.2004.1261037"},{"volume-title":"Computer Architecture: A Quantitative Approach","year":"2003","author":"Hennessy J. L.","key":"e_1_2_7_10_2"},{"volume-title":"Introduction to Operations Research","year":"2001","author":"Hillier F. S.","key":"e_1_2_7_11_2"},{"key":"e_1_2_7_12_2","doi-asserted-by":"crossref","unstructured":"HongB.andbohong@usc.edu PrasannaV. K. prasanna@usc.edu Performance optimization of a de-centralized task allocation protocol via bandwidth and buffer management Proceedings of the 2nd International Workshop on Challenges of Large Applications in Distributed Environments (CLADE \u203204) June 2004 Honolulu Hawaii USA 108\u2013117 EID2-s2.0-0000769475.","DOI":"10.1109\/CLADE.2004.1309097"},{"key":"e_1_2_7_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.844106"},{"key":"e_1_2_7_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-739X(94)00065-M"},{"key":"e_1_2_7_15_2","unstructured":"LinF.-T.andHsuC.-C. Task assignment scheduling by simulated annealing Proceedings of the 10th Conference on Computer and Communication Systems September 1990 Hong Kong 279\u2013283."},{"key":"e_1_2_7_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.8704"},{"key":"e_1_2_7_17_2","doi-asserted-by":"crossref","unstructured":"MarconC. BorinA. SusinA. CarroL. andWagnerF. Time and energy efficient mapping of embedded applications onto NoCs 1 Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC \u203205) 2005 33\u201338.","DOI":"10.1145\/1120725.1120738"},{"key":"e_1_2_7_18_2","doi-asserted-by":"crossref","unstructured":"NgouangaA. Ngouanga@lirmm.fr SassatelliG. Sassatelli@lirmm.fr TorresL. Torres@lirmm.fr GilT. Gil@lirmm.fr SoaresA. andborin@inf.ufrgs.br SusinA. susin@inf.ufrgs.br A contextual resources use: a proof of concept through the APACHES\u2032 platform Proceedings of IEEE Design and Diagnostics of Electronic Circuits and Systems April 2006 Prague Czech Republic 42\u201347 EID2-s2.0-8744312724 https:\/\/doi.org\/10.1109\/DDECS.2006.1649568.","DOI":"10.1109\/DDECS.2006.1649568"},{"key":"e_1_2_7_19_2","doi-asserted-by":"crossref","unstructured":"NolletV. nollet@imec.be MarescauxT. marescau@imec.be AvasareP. avasare@imec.be VerkestD. andMignoletJ.-Y. Centralized run-time resource management in a network-on-chip containing reconfigurable hardware tiles 1 Proceedings of the Conference on Design Automation and Test in Europe (DATE \u203205) March 2005 Munich Germany 234\u2013239 EID2-s2.0-0042850376 https:\/\/doi.org\/10.1109\/DATE.2005.91.","DOI":"10.1109\/DATE.2005.91"},{"key":"e_1_2_7_20_2","doi-asserted-by":"crossref","unstructured":"OrdunaJ. M. SillaF. andDuatoJ. A new task mapping technique for communication-aware scheduling strategies Proceedings of the International Conference on Parallel Processing Workshops (ICPPW \u203201) 2001 349\u2013354.","DOI":"10.1109\/ICPPW.2001.951971"},{"key":"e_1_2_7_21_2","doi-asserted-by":"crossref","unstructured":"ParkK. A heuristic approach to task assignment optimization in distributed systems 2 Proceedings of IEEE International Conference on Systems Man and Cybernetics October 1997 Orlando Fla USA 1838\u20131842 EID2-s2.0-0031331734.","DOI":"10.1109\/ICSMC.1997.638305"},{"volume-title":"Computer Organization and Design","year":"2004","author":"Patterson D. A.","key":"e_1_2_7_22_2"},{"key":"e_1_2_7_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"e_1_2_7_24_2","doi-asserted-by":"crossref","unstructured":"Saint-JeanN. SassatelliG. BenoitP. TorresL. andRobertM. HS-Scale: a hardware-software scalable mpsoc architecture for embedded systems Proceedings of IEEE Computer Society Annual Symposium on VLSI (ISVLSI \u203207) March 2007 Porto Alegre Brazil 21\u201328.","DOI":"10.1109\/ISVLSI.2007.51"},{"key":"e_1_2_7_25_2","unstructured":"VaradarajanR. An efficient approximation algorithm for load balancing with resource migration in distributed systems 1992 http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.49.6072."},{"key":"e_1_2_7_26_2","doi-asserted-by":"crossref","unstructured":"YangP.andCatthoorF. Dynamic mapping and ordering tasks of embedded real-time systems on multiprocessor platforms Proceedings of the 8th International Workshop on Software and Compilers for Embedded Systems (SCOPES \u203204) 2004 167\u2013181 EID2-s2.0-0028320392.","DOI":"10.1007\/978-3-540-30113-4_13"}],"container-title":["International Journal of Reconfigurable Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/ijrc\/2009\/453970.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/ijrc\/2009\/453970.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2009\/453970","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T18:13:22Z","timestamp":1739297602000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2009\/453970"}},"subtitle":[],"editor":[{"given":"Michael","family":"Huebner","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1155\/2009\/453970"],"URL":"https:\/\/doi.org\/10.1155\/2009\/453970","archive":["Portico"],"relation":{},"ISSN":["1687-7195","1687-7209"],"issn-type":[{"type":"print","value":"1687-7195"},{"type":"electronic","value":"1687-7209"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2008-12-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"453970"}}