Special Issue: Software Systems

• Architecture and High Performance Computer Systems • Previous Articles     Next Articles

New Model and Algorithm for Hardware/Software Partitioning

Ji-Gang Wu, Thambipillai Srikanthan, and Guang-Wei Zou   

  1. Centre for High Performance Embedded Systems, School of Computer Engineering, Nanyang Technological University, 639798, Singapore
  • Received:2007-08-08 Revised:2008-05-21 Online:2008-07-10 Published:2008-07-10

This paper focuses on the algorithmic aspects for the hardware/software (HW/SW) partitioning which searches a reasonable composition of hardware and software components which not only satisfies the constraint of hardware area but also optimizes the execution time. The computational model is extended so that all possible types of communications can be taken into account for the HW/SW partitioning. Also, a new dynamic programming algorithm is proposed on the basis of the computational model, in which source data, rather than speedup in previous work, of basic scheduling blocks are directly utilized to calculate the optimal solution. The proposed algorithm runs in $O(n\cdot A)$ for $n$ code fragments and the available hardware area $A$. Simulation results show that the proposed algorithm solves the HW/SW partitioning without increase in running time, compared with the algorithm cited in the literature.

Key words: Kolmogorov complexity; algorithm; average-case analysis; sorting;

[1] Niemann R, Marwedel P. Hardware/software partitioning using integer programming. In {\it Proc. the IEEE/ACM European Design Automation Conference $($EDAC$)$}, Paris, France, March 1996, pp.473--479.
[2]} Gupta R, Micheli G D. Hardware-software cosynthesis for digital systems. {\it IEEE Design and Test of Computers}, 1993, 10(3): 29--41.
[3]} Gupta R K, Coelho C, De Micheli G. Synthesis and simulation of digital systems containing interacting hardware and software components. In {\it Proc. the 29th ACM/IEEE Design Automation Conference}, Los Alamitos, CA, USA, June 1992, pp.225--230.
[4]}Ernst R, Henkel J, Benner T. Hardware-software co-synthesis for micro-controllers. {\it IEEE Design and Test of Computer}, 1993, 10(4): 64--75.
[5]}Vahid F, Gajski D D, Gong J. A binary-constraint search algorithm for minimizing hardware during hardware/software partitioning. In {\it Proc. IEEE/ACM European Design Automation Conference $($EDAC$)$}, Paris, France, February 1994, pp.214--219.
[6]}Vahid F, Gajski D D. Clustering for improved system-level functional partitioning. In {\it Proc. the 8th International Symposium on System Synthesis}, Cannes, France, September 1995, pp.28--33.
[7]}Quan G, Hu X, Greenwood G W. Preference-driven hierarchical hardware/software partitioning. In {\it Proc. IEEE International Conference on Computer Design}, Austin, TX, USA, October 1999, pp.652--657.
[8]}Srinivasan V, Radhakrishnan S, Vemuri R. Hardware software partitioning with integrated hardware design space exploration. In {\it Proc. DATE'98}, Paris, France, February 1998, pp.28--35.
[9]}Niemann R, Marwedel P. An algorithm for hardware/software partitioning using mixed integer linear programming. {\it Design Automation for Embedded Systems}, Special Issue: Partitioning Methods for Embedded Systems, 1997, 2(2): 165--193.
[10]} Weinhardt M. Integer programming for partitioning in software oriented codesign. {\it Lecture Notes in Computer Science}, 1995, 975: 227--234.
[11]}Peng Z, Kuchcinski K. An algorithm for partitioning of application specific system. In {\it Proc. IEEE/ACM European Design Automation Conference $($EDAC$)$}, Paris, February 1993, pp.316--321.
[12]} Henkel J, Ernst R. An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. {\it IEEE Trans. VLSI Sys.}, 2001, 9(2): 273--289.
[13]}Eles P, Peng Z, Kuchcinski K, Dobolt A. System level hardware/software partitioning based on simulated annealing and tabu search. {\it Design Automation for Embedded Systems}, 1997, 2(1): 5--32.
[14]}Karam S C, Ranga V. Hardware-software partitioning and pipelined scheduling of transformative applications. {\it IEEE Transactions on Very Large Scale Integration $($VLSI$)$ Systems}, 2002, 10(3): 193--208.
[15]} Madsen J, Grode J, Knudsen P V, Petersen M E, Haxthausen A. LYCOS: The Lyngby co-synthesis system. {\it Design Automation for Embedded Systems}, 1997, 2: 195--235.
[16]}Wu Jigang, Srikanthan T. Low-complex dynamic programming algorithm for hardware/software partitioning. {\it Information Processing Letters}, 2006, 98: 41--46.
[17]} Edwards S A, Lavagno L, Lee E A {\it et al}. Design of embedded systems: Formal models validation, and synthesis. In {\it Proc. the IEEE}, 1997, 85(3): 366--390.
[18]} Vallejo M L, Lopez J C. On the hardware-software partitioning problem: System modeling and partitioning techniques. {\it ACM Transactions on Design Automation of Electronic Systems}, 2003, 8(3): 269--297.
[19]}Pisinger D. Algorithms for knapsack problems [Dissertation]. University of Copenhagen, 1995.
[20]}Arato P, Mann Z A, Orban A. Algorithmic aspects of hardware/software partitioning. {\it ACM Transactions on Design Automation of Electronic Systems}, 2005, 10(1): 136--156.
[1] Yong-Hao Long, Yan-Cheng Chen, Xiang-Ping Chen, Xiao-Hong Shi, and Fan Zhou. Test-Driven Feature Extraction of Web Components [J]. Journal of Computer Science and Technology, 2022, 37(2): 389-404.
[2] Chun-Hui Wang, Zhi Jin, Wei Zhang, Didar Zowghi, Hai-Yan Zhao, Wen-Pin Jiao. Activity Diagram Synthesis Using Labelled Graphs and the Genetic Algorithm [J]. Journal of Computer Science and Technology, 2021, 36(6): 1388-1406.
[3] Einollah Pira. Using Markov Chain Based Estimation of Distribution Algorithm for Model-Based Safety Analysis of Graph Transformation [J]. Journal of Computer Science and Technology, 2021, 36(4): 839-855.
[4] Jun-Shi Chen, Hong An, Wen-Ting Han, Zeng Lin, Xin Liu. Towards Efficient Short-Range Pair Interaction on Sunway Many-Core Architecture [J]. Journal of Computer Science and Technology, 2021, 36(1): 123-139.
[5] Xin Li, Patrick Gardy, Yu-Xin Deng, Hiroyuki Seki. Reachability of Patterned Conditional Pushdown Systems [J]. Journal of Computer Science and Technology, 2020, 35(6): 1295-1311.
[6] Momodou L. Sanyang, Ata Kabán. Large-Scale Estimation of Distribution Algorithms with Adaptive Heavy Tailed Random Projection Ensembles [J]. Journal of Computer Science and Technology, 2019, 34(6): 1241-1257.
[7] Chi Zhang, Jun-Rong Liu, Da-Wu Gu, Wei-Jia Wang, Xiang-Jun Lu, Zheng Guo, Hai-Ning Lu. Side-Channel Analysis for the Authentication Protocols of CDMA Cellular Networks [J]. Journal of Computer Science and Technology, 2019, 34(5): 1079-1095.
[8] Jie Xiao, Zhan-Hui Shi, Jian-Hui Jiang, Xu-Hua Yang, Yu-Jiao Huang, Hai-Gen Hu. A Locating Method for Reliability-Critical Gates with a Parallel-Structured Genetic Algorithm [J]. Journal of Computer Science and Technology, 2019, 34(5): 1136-1151.
[9] Mansoor Davoodi, Esmaeil Delfaraz, Sajjad Ghobadi, Mahtab Masoori. Algorithms for Handoff Minimization in Wireless Networks [J]. Journal of Computer Science and Technology, 2019, 34(4): 887-900.
[10] Wei-Bei Fan, Jian-Xi Fan, Cheng-Kuan Lin, Yan Wang, Yue-Juan Han, Ru-Chuan Wang. Optimally Embedding 3-Ary n-Cubes into Grids [J]. Journal of Computer Science and Technology, 2019, 34(2): 372-387.
[11] Wen-Guo Liu, Ling-Fang Zeng, Dan Feng, Kenneth B. Kent. ROCO: Using a Solid State Drive Cache to Improve the Performance of a Host-Aware Shingled Magnetic Recording Drive [J]. Journal of Computer Science and Technology, 2019, 34(1): 61-76.
[12] Shuai-Bing Lu, Jie Wu, Huan-Yang Zheng, Zhi-Yi Fang. On Maximum Elastic Scheduling in Cloud-Based Data Center Networks for Virtual Machines with the Hose Model [J]. Journal of Computer Science and Technology, 2019, 34(1): 185-206.
[13] Ying-Lin Zhao, Jian-Lei Yang, Wei-Sheng Zhao, Aida Todri-Sanial, Yuan-Qing Cheng. Power Supply Noise Aware Task Scheduling on Homogeneous 3D MPSoCs Considering the Thermal Constraint [J]. Journal of Computer Science and Technology, 2018, 33(5): 966-983.
[14] Ji-Zhou Luo, Sheng-Fei Shi, Guang Yang, Hong-Zhi Wang, Jian-Zhong Li. O2iJoin: An Efficient Index-Based Algorithm for Overlap Interval Join [J]. Journal of Computer Science and Technology, 2018, 33(5): 1023-1038.
[15] José Alberto Fernández-Zepeda, Daniel Brubeck-Salcedo, Daniel Fajardo-Delgado, Héctor Zatarain-Aceves. A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem [J]. , 2018, 33(4): 823-837.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved