Solving Hardware/Software Partitioning via a Discrete Dynamic Convexized Method
LIN Geng1,21. Collaborative Innovation Center of IoT Industrialization and Intelligent Production, Minjiang University, Fuzhou 350121, Fujian, China; 2. College of Mathematics and Data Science, Minjiang University, Fuzhou 350121, Fujian, China
Hardware/software partitioning is an important step in the design of embedded systems. In this paper, the hardware/ software partitioning problem is modeled as a constrained binary integer programming problem, which is further converted equivalently to an unconstrained binary integer programming problem by a penalty method. A local search method, HSFM, is developed to obtain a discrete local minimizer of the unconstrained binary integer programming problem. Next, an auxiliary function, which has the same global optimal solutions as the unconstrained binary integer programming problem, is constructed, and its properties are studied. We show that applying HSFM to minimize the auxiliary function can escape from previous local optima by the increase of the parameter value successfully. Finally, a discrete dynamic convexized method is developed to solve the hardware/ software partitioning problem. Computational results and comparisons indicate that the proposed algorithm can get high-quality solutions.
 Yan X, He F, Chen Y. A novel hardware/software partitioning method based on position disturbed particle swarm optimi-zation with invasive weed optimization [J]. Journal of Computer Science and Technology, 2017, 32(2): 340-355.
 Lopez-Vallejo M, Lopez J. On the hardware-software parti-tioning problem: System modeling and partitioning techniques [J]. ACM Transactions on Design Automation of Electronic Systems, 2003, 8(3): 269-297.
 Govil N, Shrestha R, Chowdhury S R. PGMA: An algorith-mic approach for multi-objective hardware software parti-tioning [J]. Microprocessors and Microsystems, 2017, 54: 83-96.
 Wu J G, Srikanthan T, Ting L. Efficient heuristic algorithms for path-based hardware/software partitioning [J]. Mathe-matical and Computer Modeling, 2010, 51(7-8): 974-984.
 Gupta R, Micheli G D. Hardware-software cosynthesis for digital systems [J]. IEEE Design and Test of Computers, 1993, 10(3): 29-41.
 Ernst R, Henkel J, Benner T. Hardware-software co-synthesis for micro-controllers [J]. IEEE Design and Test of Computers, 1993, 10(4): 64-75.
 Purnaprajna M, Reformat M, Pedrycz W. Genetic algorithms for hardware-software partitioning and optimal resource al-location [J]. Journal of Systems Architecture, 2007, 53(7): 339-354.
 Zhang Y G, Luo W J, Zhang Z M, et al. A hardware/software partitioning based on artificial immune principles [J]. Applied Soft Computing, 2008, 8(1): 383-391.
 Eles P, Peng Z, Kuchcinski K, et al. System level hard-ware/software partitioning based on simulated annealing and tabu search [J]. Design Automation for Embedded Systems, 1997, 2(1): 5-32.
 Wiangtong T, Cheung P Y K, Luk W. Comparing three heu-ristic search methods for functional partitioning in hardware software codesign [J]. Design Automation for Embedded Systems, 2002, 6(4): 425-449.
 Zhang T, Zhao X, An X, et al. Using blind optimization algo-rithm for hardware/software partitioning [J]. IEEE Access, 2018, 5: 1353-1362.
 Dang T L, Hoshino Y. Hardware/software co-design for a neural network trained by particle swarm optimization algo-rithm [J/OL]. Neural Processing Letters, DOI: https://doi. org/10.1007/s11063-018-9826-4.
 Mann Z, Orban A, Farkas V. Evaluating the Kernighan-Lin heuristic for hardware/software partitioning [J]. International Journal of Applied Mathematics and Computer Science, 2007, 17(2): 249-267.
 Wu J G, Srikanthan T, Chen B Y. Algorithmic aspects for power-efficient hardware/software partitioning [J]. Mathe-matics and Computers in Simulation, 2008, 79(4): 1204- 1215.
 Wu J G, Srikanthan T, Chen G. Algorithmic aspects of hard-ware/software partitioning: 1D search algorithms [J]. IEEE Transactions on Computers, 2010, 59(4): 532-544.
 Zhu W X, Ali M M. Solving nonlinearly constrained global optimization problem via an auxiliary function method [J]. Journal of Computational and Applied Mathematics, 2009, 230(2): 491-503.
 Zhu W X, Fan H. A discrete dynamic convexized method for nonlinear integer programming [J]. Journal of Computational and Applied Mathematics, 2009, 223(2): 356-373.
 Zhu W X, Lin G. A dynamic convexized method for noncon-vex mixed integer nonlinear programming [J]. Computers & Operations Research, 2011, 38(12): 1792-1804.
 Zhu W X, Lin G, Ali M M. Max-k-cut by the discrete dynamic convexized method [J]. INFORMS Journal on Computing, 2013, 25(1): 27-40.
 Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs [J]. The Bell System Technical Journal, 1970, 49(2): 291-307.
 Fiduccia C M, Mattheyses R M. A linear time heuristic for improving network partitions [C] // Proceedings of ACM/ IEEE DAC. Piscataway N J: IEEE Press, 1982: 175- 181.
 Yang W, Wang G, Bhuiyan M Z A, et al. Hypergraph parti-tioning for social networks based on information entropy modularity [J]. Journal of Network and Computer Applica-tions, 2017, 86: 59-71.
 Dick R P, Rhodes D L, Wolf W. TGFF: Task graphs for free [C] // Proceedings of the International Workshop Hardware/ Software Codesign. Washington D C: IEEE Computer Society, 1998: 97-101.
 Shang Y L, Zhang L S. A filled function method for finding a global minimizer on global integer optimization [J]. Journal of Computational and Applied Mathematics, 2005, 181(1): 200-210.