{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:26:39Z","timestamp":1758709599539,"version":"3.37.3"},"reference-count":36,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2019,2,23]],"date-time":"2019-02-23T00:00:00Z","timestamp":1550880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"National Key R&D Program of China","award":["2018YFB1003201"],"award-info":[{"award-number":["2018YFB1003201"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672171"],"award-info":[{"award-number":["61672171"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Guangdong Natural Science Foundation of China","award":["2018B030311007"],"award-info":[{"award-number":["2018B030311007"]}]},{"name":"Guangdong Educational Commission foundation of China","award":["2016KZDXM052"],"award-info":[{"award-number":["2016KZDXM052"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,5,20]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Hardware\/software (HW\/SW) partitioning, that decides which components of an application are implemented in hardware and which ones in software, is a crucial step in embedded system design. On modern heterogeneous embedded system platform, each component of application can typically have multiple feasible configurations\/implementations, trading off quality aspects (e.g. energy consumption, completion time) with usage for various types of resources. This provides new opportunities for further improving the overall system performance, but few works explore the potential opportunity by incorporating the multiple choices of hardware implementation in the partitioning process. This paper proposes three algorithms for multiple-choice HW\/SW partitioning of tree-shape task graph on multiple processors system on chip (MPSoC) with the objective of minimizing execution time, while meeting area constraint. Firstly, an efficient heuristic algorithm is proposed to rapidly generate an approximate solution. The obtained solution produced by the first algorithm is then further refined by a customized Tabu search algorithm. We also propose a dynamic programming algorithm to calculate the exact solutions for relatively smaller scale instances. Simulation results show that the proposed heuristic algorithm is able to quickly generate good approximate solutions, and the solutions become very close to the exact solutions after refined by the proposed Tabu search algorithm, in comparison to the exact solutions produced by the dynamic programming algorithm.<\/jats:p>","DOI":"10.1093\/comjnl\/bxy140","type":"journal-article","created":{"date-parts":[[2018,12,14]],"date-time":"2018-12-14T13:43:34Z","timestamp":1544795014000},"page":"688-700","source":"Crossref","is-referenced-by-count":4,"title":["Multiple-Choice Hardware\/Software Partitioning for Tree Task-Graph on MPSoC"],"prefix":"10.1093","volume":"63","author":[{"given":"Wenjun","family":"Shi","sequence":"first","affiliation":[{"name":"School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jigang","family":"Wu","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guiyuan","family":"Jiang","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siew-kei","family":"Lam","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,2,23]]},"reference":[{"key":"2020051808480720300_bxy140C1","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1109\/5.558710","article-title":"Design of embedded systems: formal models, validation and synthesis","volume":"85","author":"Edwards","year":"1997","journal-title":"Proc. IEEE"},{"key":"2020051808480720300_bxy140C2","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/54.232470","article-title":"Hardware-software cosynthesis for digital systems","volume":"10","author":"Gupta","year":"1993","journal-title":"IEEE Des. Test Comput."},{"year":"1996","author":"Niemann","key":"2020051808480720300_bxy140C3"},{"year":"1995","author":"Vahid","key":"2020051808480720300_bxy140C4"},{"key":"2020051808480720300_bxy140C5","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1145\/1044111.1044119","article-title":"Algorithmic aspects of hardware\/software partitioning","volume":"10","author":"Arat\u00f3","year":"2005","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"year":"2004","author":"Mann","key":"2020051808480720300_bxy140C6"},{"year":"2004","author":"Banerjee","key":"2020051808480720300_bxy140C7"},{"key":"2020051808480720300_bxy140C8","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1109\/92.924041","article-title":"An approach to automated hardware\/software partitioning using a flexible granularity that is driven by high-level estimation techniques","volume":"9","author":"Henkel","year":"2001","journal-title":"IEEE Trans. VLSI Syst."},{"year":"1996","author":"Knudsen","key":"2020051808480720300_bxy140C9"},{"key":"2020051808480720300_bxy140C10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.ipl.2005.12.008","article-title":"Low-complex dynamic programming algorithm for hardware\/software partitioning","volume":"98","author":"Wu","year":"2006","journal-title":"Inf. Process. Lett."},{"key":"2020051808480720300_bxy140C11","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s10766-013-0283-4","article-title":"Power efficiency for hardware\/software partitioning with time and area constraints on MPSoC","volume":"43","author":"Sha","year":"2015","journal-title":"Int. J. Parallel Programming"},{"year":"2003","author":"Arat\u00f3","key":"2020051808480720300_bxy140C12"},{"year":"2008","author":"Tahaee","key":"2020051808480720300_bxy140C13"},{"key":"2020051808480720300_bxy140C14","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s10617-010-9068-9","article-title":"An integrated high-level hardware\/software partitioning methodology","volume":"15","author":"Abdelhalim","year":"2011","journal-title":"Des. Autom. Embedded Syst."},{"key":"2020051808480720300_bxy140C15","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/1698759.1698763","article-title":"Hardware\/software partitioning and pipelined scheduling on runtime reconfigurable FPGAs","volume":"15","author":"Yuan","year":"2010","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"2020051808480720300_bxy140C16","doi-asserted-by":"crossref","first-page":"2:1","DOI":"10.1145\/1640457.1640459","article-title":"Autonomous hardware\/software partitioning and voltage\/frequency scaling for low-power embedded systems","volume":"15","author":"Mu","year":"2009","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"2020051808480720300_bxy140C17","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1023\/A:1016567828852","article-title":"Comparing three heuristic search methods for functional partitioning in hardware-software codesign","volume":"6","author":"Wiangtong","year":"2002","journal-title":"Des. Autom. Embedded Syst."},{"key":"2020051808480720300_bxy140C18","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/785411.785412","article-title":"On the hardware-software partitioning problem: system modeling and partitioning techniques","volume":"8","author":"L\u00f3pez-Vallejo","year":"2003","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"year":"2008","author":"Li","key":"2020051808480720300_bxy140C19"},{"key":"2020051808480720300_bxy140C20","doi-asserted-by":"crossref","first-page":"34:1","DOI":"10.1145\/1721695.1721700","article-title":"A polynomial algorithm for partitioning problems","volume":"9","author":"Tahaee","year":"2010","journal-title":"ACM Trans. Embedded Comput. Syst."},{"year":"2015","author":"Azari","key":"2020051808480720300_bxy140C21"},{"key":"2020051808480720300_bxy140C22","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/s11227-013-0888-9","article-title":"Efficient heuristic and tabu search for hardware\/software partitioning","volume":"66","author":"Wu","year":"2013","journal-title":"J. Supercomput."},{"key":"2020051808480720300_bxy140C23","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1109\/TC.2009.173","article-title":"Algorithmic aspects of hardware\/software partitioning: 1D search algorithms","volume":"59","author":"Wu","year":"2010","journal-title":"IEEE Trans. Comput."},{"key":"2020051808480720300_bxy140C24","doi-asserted-by":"crossref","first-page":"2251","DOI":"10.1007\/s11227-015-1381-4","article-title":"Algorithmic aspects of graph reduction for hardware\/software partitioning","volume":"71","author":"Jiang","year":"2015","journal-title":"J. Supercomput."},{"year":"2014","author":"Ma","key":"2020051808480720300_bxy140C25"},{"key":"2020051808480720300_bxy140C26","doi-asserted-by":"crossref","first-page":"3217","DOI":"10.1109\/TC.2016.2519895","article-title":"Uncertainty model for configurable hardware\/software and resource partitioning","volume":"65","author":"Wang","year":"2016","journal-title":"IEEE Trans. Comput."},{"year":"2013","author":"Das","key":"2020051808480720300_bxy140C27"},{"key":"2020051808480720300_bxy140C28","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.micpro.2017.09.002","article-title":"PGMA: an algorithmic approach for multi-objective hardware software partitioning","volume":"54","author":"Govil","year":"2017","journal-title":"Microprocessors Microsyst."},{"key":"2020051808480720300_bxy140C29","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1023\/A:1008872518365","article-title":"The extended partitioning problem: hardware\/software mapping, scheduling, and implementation-bin selection","volume":"2","author":"Kalavade","year":"1997","journal-title":"Des. Autom. Embedded Syst."},{"key":"2020051808480720300_bxy140C30","doi-asserted-by":"crossref","first-page":"3281","DOI":"10.1016\/j.cor.2012.04.013","article-title":"Algorithmic aspects for multiple-choice hardware\/software partitioning","volume":"39","author":"Wu","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"2020051808480720300_bxy140C31","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.compeleceng.2016.01.006","article-title":"Algorithms for bi-objective multiple-choice hardware\/software partitioning","volume":"50","author":"Shi","year":"2016","journal-title":"Comput. Electr. Eng."},{"year":"2005","author":"Tosun","key":"2020051808480720300_bxy140C32"},{"key":"2020051808480720300_bxy140C33","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.scico.2004.11.003","article-title":"Extending component-based design with hardware components","volume":"56","author":"Arat\u00f3","year":"2005","journal-title":"Sci. Comput. Program."},{"key":"2020051808480720300_bxy140C34","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-6089-0","volume-title":"Tabu Search","author":"Glover","year":"1997"},{"volume-title":"The Design and Analysis of Computer Algorithms","year":"1974","author":"Aho","key":"2020051808480720300_bxy140C35"},{"key":"2020051808480720300_bxy140C36","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s10617-008-9032-0","article-title":"Algorithmic aspects for functional partitioning and scheduling in hardware\/software co-design","volume":"12","author":"Wu","year":"2008","journal-title":"Des. Autom. Embedded Syst."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/5\/688\/33222467\/bxy140.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/5\/688\/33222467\/bxy140.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T12:48:30Z","timestamp":1589806110000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/63\/5\/688\/5363890"}},"subtitle":[],"editor":[{"given":"Iain","family":"Stewart","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2019,2,23]]},"references-count":36,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2019,2,23]]},"published-print":{"date-parts":[[2020,5,20]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxy140","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2020,5]]},"published":{"date-parts":[[2019,2,23]]}}}