{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:17:57Z","timestamp":1742401077439,"version":"3.32.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2005,1]]},"abstract":"One of the most crucial steps in the design of embedded systems is hardware\/software partitioning, that is, deciding which components of the system should be implemented in hardware and which ones in software. Most formulations of the hardware\/software partitioning problem are NP-hard, so the majority of research efforts on hardware\/software partitioning has focused on developing efficient heuristics.This article considers the combinatorial structure behind hardware\/software partitioning. Two similar versions of the partitioning problem are defined, one of which turns out to be NP-hard, whereas the other one can be solved in polynomial time. This helps in understanding the real cause of complexity in hardware\/software partitioning. Moreover, the polynomial-time algorithm serves as the basis for a highly efficient novel heuristic for the NP-hard version of the problem. Unlike general-purpose heuristics such as genetic algorithms or simulated annealing, this heuristic makes use of problem-specific knowledge, and can thus find high-quality solutions rapidly. Moreover, it has the unique characteristic that it also calculateslower bounds on the optimum solution<\/jats:italic>. It is demonstrated on several benchmarks and also large random examples that the new algorithm clearly outperforms other heuristics that are generally applied to hardware\/software partitioning.<\/jats:p>","DOI":"10.1145\/1044111.1044119","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"136-156","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":78,"title":["Algorithmic aspects of hardware\/software partitioning"],"prefix":"10.1145","volume":"10","author":[{"given":"P\u00e9ter","family":"Arat\u00f3","sequence":"first","affiliation":[{"name":"Budapest University of Technology and Economics, Hungary"}]},{"given":"Zolt\u00e1n \u00c1d\u00e1m","family":"Mann","sequence":"additional","affiliation":[{"name":"Budapest University of Technology and Economics, Hungary"}]},{"given":"Andr\u00e1s","family":"Orb\u00e1n","sequence":"additional","affiliation":[{"name":"Budapest University of Technology and Economics, Hungary"}]}],"member":"320","published-online":{"date-parts":[[2005,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.822566"},{"key":"e_1_2_1_2_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"Ahuja , R. K. , Magnanti , T. L. , and Orlin , J. B . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice-Hall , Englewood Cliffs, NJ . Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ."},{"volume-title":"Proceedings of the IEEE International Symposium on Intelligent Signal Processing.","author":"Arat\u00f3 P.","key":"e_1_2_1_3_1","unstructured":"Arat\u00f3 , P. , Juh\u00e1sz , S. , Mann , Z. \u00c1., Orb\u00e1n , A. , and Papp , D . 2003a. Hardware\/software partitioning in embedded system design . In Proceedings of the IEEE International Symposium on Intelligent Signal Processing. Arat\u00f3, P., Juh\u00e1sz, S., Mann, Z. \u00c1., Orb\u00e1n, A., and Papp, D. 2003a. Hardware\/software partitioning in embedded system design. In Proceedings of the IEEE International Symposium on Intelligent Signal Processing."},{"volume-title":"Proceedings of the IEEE 7th International Conference on Intelligent Engineering Systems.","author":"Arat\u00f3 P.","key":"e_1_2_1_4_1","unstructured":"Arat\u00f3 , P. , Mann , Z. \u00c1., and Orb\u00e1n , A . 2003b. Hardware-software co-design for Kohonen's self-organizing map . In Proceedings of the IEEE 7th International Conference on Intelligent Engineering Systems. Arat\u00f3, P., Mann, Z. \u00c1., and Orb\u00e1n, A. 2003b. Hardware-software co-design for Kohonen's self-organizing map. In Proceedings of the IEEE 7th International Conference on Intelligent Engineering Systems."},{"volume-title":"Proceedings of the 2nd International Workshop on Hardware-Software Codesign.","author":"Barros E.","key":"e_1_2_1_5_1","unstructured":"Barros , E. , Rosenstiel , W. , and Xiong , X . 1993. Hardware\/software partitioning with UNITY . In Proceedings of the 2nd International Workshop on Hardware-Software Codesign. Barros, E., Rosenstiel, W., and Xiong, X. 1993. Hardware\/software partitioning with UNITY. In Proceedings of the 2nd International Workshop on Hardware-Software Codesign."},{"volume-title":"Proceedings of the 33rd Design Automation Conference. 10","author":"Binh N. N.","key":"e_1_2_1_6_1","unstructured":"Binh , N. N. , Imai , M. , Shiomi , A. , and Hikichi , N . 1996. A hardware\/software partitioning algorithm for designing pipelined ASIPs with least gate counts . In Proceedings of the 33rd Design Automation Conference. 10 .1145\/240518.240618 Binh, N. N., Imai, M., Shiomi, A., and Hikichi, N. 1996. A hardware\/software partitioning algorithm for designing pipelined ASIPs with least gate counts. In Proceedings of the 33rd Design Automation Conference. 10.1145\/240518.240618"},{"volume-title":"Proceedings of CODES 01","author":"Chatha K. S.","key":"e_1_2_1_7_1","unstructured":"Chatha , K. S. and Vemuri , R . 2001. MAGELLAN: Multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs . In Proceedings of CODES 01 . 10.1145\/371636.371671 Chatha, K. S. and Vemuri, R. 2001. MAGELLAN: Multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs. In Proceedings of CODES 01. 10.1145\/371636.371671"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009180"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.573831"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.728914"},{"volume-title":"Proceedings of EURO-DAC '96","author":"Eles P.","key":"e_1_2_1_11_1","unstructured":"Eles , P. , Peng , Z. , Kuchcinski , K. , and Doboli , A . 1996. Hardware\/software partitioning of VHDL system specifications . In Proceedings of EURO-DAC '96 . Eles, P., Peng, Z., Kuchcinski, K., and Doboli, A. 1996. Hardware\/software partitioning of VHDL system specifications. In Proceedings of EURO-DAC '96."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008857008151"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.245964"},{"volume-title":"Proceedings of the 19th Design Automation Conference.","author":"Fiduccia C. M.","key":"e_1_2_1_14_1","unstructured":"Fiduccia , C. M. and Mattheyses , R. M . 1982. A linear-time heuristic for improving network partitions . In Proceedings of the 19th Design Automation Conference. Fiduccia, C. M. and Mattheyses, R. M. 1982. A linear-time heuristic for improving network partitions. In Proceedings of the 19th Design Automation Conference."},{"key":"e_1_2_1_15_1","unstructured":"Garey M. R. and Johnson D. S. 1979. A Guide to the Theory of NP--Completeness. Freeman San Francisco CA. Garey M. R. and Johnson D. S. 1979. A Guide to the Theory of NP--Completeness. Freeman San Francisco CA."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"volume-title":"Proceedings of Design Automation and Test in Europe (DATE '98)","author":"Grode J.","key":"e_1_2_1_17_1","unstructured":"Grode , J. , Knudsen , P. V. , and Madsen , J . 1998. Hardware resource allocation for hardware\/software partitioning in the LYCOS system . In Proceedings of Design Automation and Test in Europe (DATE '98) . Grode, J., Knudsen, P. V., and Madsen, J. 1998. Hardware resource allocation for hardware\/software partitioning in the LYCOS system. In Proceedings of Design Automation and Test in Europe (DATE '98)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.232470"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IEEE 4th Annual Workshop on Workload Characterization. 10","author":"Guthaus M. R.","year":"2001","unstructured":"Guthaus , M. R. , Ringenberg , J. S. , Ernst , D. , Austin , T. M. , Mudge , T. , and Brown , R. B . 1997. MiBench: A free, commercially representative embedded benchmark suite . In Proceedings of the IEEE 4th Annual Workshop on Workload Characterization. 10 .1109\/WWC. 2001 .15 Guthaus, M. R., Ringenberg, J. S., Ernst, D., Austin, T. M., Mudge, T., and Brown, R. B. 1997. MiBench: A free, commercially representative embedded benchmark suite. In Proceedings of the IEEE 4th Annual Workshop on Workload Characterization. 10.1109\/WWC.2001.15"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.924041"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008872518365"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.720318"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"volume-title":"Proceedings of DATE. 411--416","author":"Lopez-Vallejo M.","key":"e_1_2_1_25_1","unstructured":"Lopez-Vallejo , M. , Grajal , J. , and Lopez , J. C . 2000. Constraint-driven system partitioning . In Proceedings of DATE. 411--416 . 10.1145\/343647.343811 Lopez-Vallejo, M., Grajal, J., and Lopez, J. C. 2000. Constraint-driven system partitioning. In Proceedings of DATE. 411--416. 10.1145\/343647.343811"},{"volume-title":"Proceedings of DATE.","author":"Lopez-Vallejo M.","key":"e_1_2_1_26_1","unstructured":"Lopez-Vallejo , M. and Lopez , J. C . 1998. A knowledge based system for hardware-software partitioning . In Proceedings of DATE. Lopez-Vallejo, M. and Lopez, J. C. 1998. A knowledge based system for hardware-software partitioning. In Proceedings of DATE."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/785411.785412"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008884219274"},{"volume-title":"Proceedings of the 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications.","author":"Mann Z.","key":"e_1_2_1_29_1","unstructured":"Mann , Z. \u00c1. and Orb\u00e1n , A . 2003. Optimization problems in system-level synthesis . In Proceedings of the 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications. Mann, Z. \u00c1. and Orb\u00e1n, A. 2003. Optimization problems in system-level synthesis. In Proceedings of the 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications."},{"volume-title":"Proceedings of ProRISC.","author":"Mei B.","key":"e_1_2_1_30_1","unstructured":"Mei , B. , Schaumont , P. , and Vernalde , S . 2000. A hardware\/software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems . In Proceedings of ProRISC. Mei, B., Schaumont, P., and Vernalde, S. 2000. A hardware\/software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems. In Proceedings of ProRISC."},{"volume-title":"Kluwer Academic Publishers","author":"Niemann R.","key":"e_1_2_1_31_1","unstructured":"Niemann , R. 1998. Hardware \/Software Co-Design for Data Flow Dominated Embedded Systems. Kluwer Academic Publishers , Norwell, MA . Niemann, R. 1998. Hardware\/Software Co-Design for Data Flow Dominated Embedded Systems. Kluwer Academic Publishers, Norwell, MA."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1023\/A:1008832202436","article-title":"An algorithm for hardware\/software partitioning using mixed integer linear programming","volume":"2","author":"Niemann R.","year":"1997","unstructured":"Niemann , R. and Marwedel , P. 1997 . An algorithm for hardware\/software partitioning using mixed integer linear programming . Des. Automat. Embedd. Syst. Special Issue: Partitioning Methods for Embedded Systems 2 , 165 -- 193 . Niemann, R. and Marwedel, P. 1997. An algorithm for hardware\/software partitioning using mixed integer linear programming. Des. Automat. Embedd. Syst. Special Issue: Partitioning Methods for Embedded Systems 2, 165--193.","journal-title":"Des. Automat. Embedd. Syst. Special Issue: Partitioning Methods for Embedded Systems"},{"volume-title":"Proceedings of the International Conference on Recent Advances in Mechatronics.","author":"O'Nils M.","key":"e_1_2_1_33_1","unstructured":"O'Nils , M. , Jantsch , A. , Hemani , A. , and Tenhunen , H . 1995. Interactive hardware-software partitioning and memory allocation based on data transfer profiling . In Proceedings of the International Conference on Recent Advances in Mechatronics. O'Nils, M., Jantsch, A., Hemani, A., and Tenhunen, H. 1995. Interactive hardware-software partitioning and memory allocation based on data transfer profiling. In Proceedings of the International Conference on Recent Advances in Mechatronics."},{"key":"e_1_2_1_34_1","unstructured":"Qin S. and He J. 2000. An algebraic approach to hardware\/software partitioning. Tech. rep. 206 UNU\/IIST. Qin S. and He J. 2000. An algebraic approach to hardware\/software partitioning. Tech. rep. 206 UNU\/IIST."},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer Design.","author":"Quan G.","key":"e_1_2_1_35_1","unstructured":"Quan , G. , Hu , X. , and Greenwood , G . 1999. Preference-driven hierarchical hardware\/software partitioning . In Proceedings of the IEEE\/ACM International Conference on Computer Design. Quan, G., Hu, X., and Greenwood, G. 1999. Preference-driven hierarchical hardware\/software partitioning. In Proceedings of the IEEE\/ACM International Conference on Computer Design."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.392848"},{"volume-title":"Proceedings of DATE.","author":"Srinivasan V.","key":"e_1_2_1_37_1","unstructured":"Srinivasan , V. , Radhakrishnan , S. , and Vemuri , R . 1998. Hardware software partitioning with integrated hardware design space exploration . In Proceedings of DATE. Srinivasan, V., Radhakrishnan, S., and Vemuri, R. 1998. Hardware software partitioning with integrated hardware design space exploration. In Proceedings of DATE."},{"volume-title":"Proceedings of DAC. 10","author":"Stitt G.","key":"e_1_2_1_38_1","unstructured":"Stitt , G. , Lysecky , R. , and Vahid , F . 2003. Dynamic hardware\/software partitioning: A first approach . In Proceedings of DAC. 10 .1145\/775832.775896 Stitt, G., Lysecky, R., and Vahid, F. 2003. Dynamic hardware\/software partitioning: A first approach. In Proceedings of DAC. 10.1145\/775832.775896"},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"Multiprocessor scheduling with the aid of network flow algorithms","volume":"3","author":"Stone H.","year":"1977","unstructured":"Stone , H. 1977 . Multiprocessor scheduling with the aid of network flow algorithms . IEEE Trans. Softw. Eng. 3 , 1 (Jan.), 85--93. Stone, H. 1977. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Trans. Softw. Eng. 3, 1 (Jan.), 85--93.","journal-title":"IEEE Trans. Softw. Eng."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the International Workshop on Hardware-Software Codesign.","author":"Vahid F.","year":"1997","unstructured":"Vahid , F. 1997 . Modifying min-cut for hardware and software functional partitioning . In Proceedings of the International Workshop on Hardware-Software Codesign. Vahid, F. 1997. Modifying min-cut for hardware and software functional partitioning. In Proceedings of the International Workshop on Hardware-Software Codesign."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/567270.567273"},{"volume-title":"Proceedings of the 8th International Symposium on System Synthesis. 10","author":"Vahid F.","key":"e_1_2_1_42_1","unstructured":"Vahid , F. and Gajski , D . 1995. Clustering for improved system-level functional partitioning . In Proceedings of the 8th International Symposium on System Synthesis. 10 .1145\/224486.224492 Vahid, F. and Gajski, D. 1995. Clustering for improved system-level functional partitioning. In Proceedings of the 8th International Symposium on System Synthesis. 10.1145\/224486.224492"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008836303344"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.585225"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1044111.1044119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,22]],"date-time":"2024-12-22T20:59:06Z","timestamp":1734901146000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044111.1044119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1145\/1044111.1044119"],"URL":"https:\/\/doi.org\/10.1145\/1044111.1044119","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2005,1]]},"assertion":[{"value":"2005-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}