With the development of the design complexity in embedded systems, hardware/software (HW/SW) partitioning becomes a challenging optimization problem in HW/SW co-design. A novel HW/SW partitioning method based on position disturbed particle swarm optimization with invasive weed optimization (PDPSO-IWO) is presented in this paper. It is found by biologists that the ground squirrels produce alarm calls which warn their peers to move away when there is potential predatory threat. Here, we present PDPSO algorithm, in each iteration of which the squirrel behavior of escaping from the global worst particle can be simulated to increase population diversity and avoid local optimum. We also present new initialization and reproduction strategies to improve IWO algorithm for searching a better position, with which the global best position can be updated. Then the search accuracy and the solution quality can be enhanced. PDPSO and improved IWO are synthesized into one single PDPSO-IWO algorithm, which can keep both searching diversification and searching intensification. Furthermore, a hybrid NodeRank (HNodeRank) algorithm is proposed to initialize the population of PDPSO-IWO, and the solution quality can be enhanced further. Since the HW/SW communication cost computing is the most time-consuming process for HW/SW partitioning algorithm, we adopt the GPU parallel technique to accelerate the computing. In this way, the runtime of PDPSO-IWO for large-scale HW/SW partitioning problem can be reduced efficiently. Finally, multiple experiments on benchmarks from state-of-the-art publications and large-scale HW/SW partitioning demonstrate that the proposed algorithm can achieve higher performance than other algorithms.
The work was supported by the National Natural Science Foundation of China under Grant No. 61472289 and the National Key Research and Development Project of China under Grant No. 2016YFC0106305.
通讯作者: Fa-Zhi He
About author: Xiao-Hu Yan received his B.S. degree in information and computing science from Huazhong Agricultural University, Wuhan, in 2008, and his M.S. degree in computer application from North China Electric Power University, Beijing, in 2010. Currently, he is a Ph.D. candidate of the School of Computer Science in Wuhan University, Wuhan. His research interests include hardware/software partitioning and optimization algorithm.
Xiao-Hu Yan, Fa-Zhi He, Yi-Lin Chen.基于野草扰动粒子群算法的新型软硬件划分方法[J] Journal of Computer Science and Technology , 2017,V32(2): 340-355
Xiao-Hu Yan, Fa-Zhi He, Yi-Lin Chen.A Novel Hardware/Software Partitioning Method Based on Position Disturbed Particle Swarm Optimization with Invasive Weed Optimization[J] Journal of Computer Science and Technology, 2017,V32(2): 340-355
 Trappey A J C, Shen W, Cha J J. Special issue editorial on advances in collaborative systems engineering for product design, production and service network. Journal of Systems Science and Systems Engineering, 2016, 25(2):139-141. Zhang Y G, Luo W J, Zhang Z M, Li B, Wang X F. A hardware/software partitioning algorithm based on artificial immune principles. Applied Soft Computing, 2008, 8(1):383-391. Hidalgo J I, Lanchares J. Functional partitioning for hardware-software codesign using genetic algorithms. In Proc. the 23rd EUROMICRO Conference on New Frontiers of Information Technology, Sept. 1997, pp.631-638. Arató P, Mann Z A, Orbán A. Algorithmic aspects of hardware/software partitioning. ACM Transactions on Design Automation of Electronic Systems, 2005, 10(1):136-156. Wu J G, Srikanthan T. Low-complex dynamic programming algorithm for hardware/software partitioning. Information Processing Letters, 2006, 98(2):41-46. Madsen J, Grode J, Knudsen P V, Petersen M E, Haxthausen A. LYCOS:The Lyngby co-synthesis system. Design Automation for Embedded Systems, 1997, 2(2):195-235. Strachacki M. Speedup of branch and bound method for hardware/software partitioning. In Proc. the 1st International Conference on Information Technology, May 2008. Chatha K S, Vemuri R. Hardware-software partitioning and pipelined scheduling of transformative applications. IEEE Transactions on Very Large Scale Integration Systems, 2002, 10(3):193-208. Wu J G, Thambipillai S. A branch-and-bound algorithm for hardware/software partitioning. In Proc. the 4th International Symposium on Signal Processing and Information Technology, Dec. 2004, pp.526-529. Niemann R, Marwedel P. An algorithm for hardware/software partitioning using mixed integer linear programming. Design Automation for Embedded Systems, 1997, 2(2):165-193. Gupta R K, Coelho Jr C N, De Micheli G. Synthesis and simulation of digital systems containing interacting hardware and software components. In Proc. the 29th ACM/IEEE Design Automation Conference, June 1992, pp.225-230. Gupta R K, De Micheli G. Hardware-software cosynthesis for digital systems. IEEE Design & Test of Computers, 1993, 10(3):29-41. Wiangtong T, Cheung P Y K, Luk W. Comparing three heuristic search methods for functional partitioning in hardware-software codesign. Design Automation for Embedded Systems, 2002, 6(4):425-449. Purnaprajna M, Reformat M, Pedrycz W. Genetic algorithms for hardware-software partitioning and optimal resource allocation. Journal of Systems Architecture, 2007, 53(7):339-354. Dick R P, Jha N K. MOGAC:A multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(10):920-935. Janakiraman N, Kumar P N. Multi-objective module partitioning design for dynamic and partial reconfigurable system-on-chip using genetic algorithm. Journal of Systems Architecture-Embeded Systems Design, 2014, 60(1):119-139. Henkel J, Ernst R. An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. IEEE Transactions on Very Large Scale Integration Systems, 2001, 9(2):273-289. Liu P, Wu J G, Wang Y J. Hybrid algorithms for hardware/software partitioning and scheduling on reconfigurable devices. Mathematical and Computer Modelling, 2013, 58(1/2):409-420. Wu J G, Srikanthan T, Chen G. Algorithmic aspects of hardware/software partitioning:1D search algorithms. IEEE Transactions on Computers, 2010, 59(4):532-544. Eles P, Peng Z, Kuchcinski K, Doboli A. System level hardware/software partitioning based on simulated annealing and tabu search. Design Automation for Embedded Systems, 1997, 2(1):5-32. Wu J G, Wang P, Lam S K, Srikanthan T. Efficient heuristic and tabu search for hardware/software partitioning. The Journal of Supercomputing, 2013, 66(1):118-134. Wang G, Gong W, Kastner R. A new approach for task level computational resource bi-partitioning. In Proc. the 15th IASTED International Conference on Parallel and Distributed Computing and Systems, June 2003, pp.439-444. Xiong Z, Li S, Chen J. Hardware/software partitioning based on ant optimization with initial pheromone. Computer Research and Development, 2005, 42(12):2176-2183. (in Chinese) Abdelhalim M B, Salama A E, Habib S E D. Hardware software partitioning using particle swarm optimization technique. In Proc. the 6th International Workshop on Systemon-Chip for Real-Time Applications, Dec. 2006, pp.189-194. Abdelhalim M B, Habib S E D. An integrated high-level hardware/software partitioning methodology. Design Automation for Embedded Systems, 2011, 15(1):19-50. Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. Bell Labs Technical Journal, 1970, 49(2):291-307. Fiduccia C M, Mattheyses R M. A linear-time heuristic for improving network partitions. In Proc. the 19th Design Automation Conference, June 1982, pp.175-181. Saab Y G. A fast and robust network bisection algorithm. IEEE Transactions on Computers, 1995, 44(7):903-913. Vahid F, Gajski D D. Clustering for improved system-level functional partitioning. In Proc. the 8th International Symposium on System Synthesis, Sept. 1995, pp.28-35. López-Vallejo M, López J C. On the hardware-software partitioning problem:System modeling and partitioning techniques. ACM Transactions on Design Automation of Electronic Systems, 2003, 8(3):269-297. Vahid F, Le T D. Extending the Kernighan/Lin heuristic for hardware and software functional partitioning. Design Automation for Embedded Systems, 1997, 2(2):237-261. Arató P, Juhász S, Mann Z A, Orban A, Papp D. Hardwaresoftware partitioning in embedded system design. In Proc. IEEE International Symposium on Intelligent Signal Processing, Sept. 2003, pp.197-202. Grode J, Knudsen P V, Madsen J. Hardware resource allocation for hardware/software partitioning in the LYCOS system. In Proc. the Conference on Design, Automation and Test in Europe, Feb. 1998, pp.22-27. Ernst R, Henkel J, Benner T. Hardware-software cosynthesis for microcontrollers. IEEE Design & Test of Computers, 1993, 10(4):64-75. Wolf W H. An architectural co-synthesis algorithm for distributed, embedded computing systems. IEEE Transactions on Very Large Scale Integration Systems, 1997, 5(2):218-229. Chen Z, Wu J G, Song G Z, Chen J L. NodeRank:An efficient algorithm for hardware/software partitioning. Chinese Journal of Computers, 2013, 36(10):2033-2040. (in Chinese) Abdelhalim M B, Salama A E, Habib S E D. Constrained and unconstrained hardware-software partitioning using particle swarm optimization technique. In Proc. IIESS, May 30-June 1, pp.207-220. Bhattacharya A, Konar A, Das S, Grosan C, Abraham A. Hardware software partitioning problem in embedded system design using particle swarm optimization algorithm. In Proc. the 2nd International Conference on Complex, Intelligent and Software Intensive Systems, March 2008, pp.171-176. Eimuri T, Salehi S. Using DPSO and B&B algorithms for hardware/software partitioning in co-design. In Proc. the 2nd International Conference on Computer Research and Development, May 2010, pp.416-420. Luo L, He H, Liao C, Dou Q, Xu W X. Hardware/software partitioning for heterogeneous multicore SoC using particle swarm optimization and immune clone (PSO-IC) algorithm. In Proc. IEEE International Conference on Information and Automation (ICIA), June 2010, pp.490-494. Xue J, Jin Y. Position disturbed particle swarm optimization. Computer Engineering and Design, 2014, 35(3):1037-1040. (in Chinese) Wu Y, Zhang H, Yang H. Research on parallel HW/SWpartitioning based on hybrid PSO algorithm. In Proc. the 9th International Conference on Algorithms and Architectures for Parallel Processing, June 2009, pp.449-459. Farahani A F, Kamal M, Salmani-Jelodar M. Parallelgenetic-algorithm-based HW/SW partitioning. In Proc. the 5th IEEE International Symposium on Parallel Computing in Electrical Engineering, Sept. 2006, pp.337-342. Cooke P, Fowers J, Brown G, Stitt G. A tradeoff analysis of FPGAS, GPUS, and multicores for sliding-window applications. ACM Transactions on Reconfigurable Technology and Systems, 2015, 8(1):2:1-2:24. Bordoloi U D, Chakraborty S. GPU-based acceleration of system-level design tasks. International Journal of Parallel Programming, 2010, 38(3/4):225-253. Du H Z, Xia N, Jiang J G, Xu L N, Zheng R. A monte carlo enhanced PSO algorithm for optimal QoM in multi-channel wireless networks. Journal of Computer Science and Technology, 2013, 28(3):553-563. Inbarani H H, Azar A T, Jothi G. Supervised hybrid feature selection based on PSO and rough sets for medical diagnosis. Computer Methods and Programs in Biomedicine, 2014, 113(1):175-185. Ratnaweera A, Halgamuge S K, Watson H C. Selforganizing hierarchical particle swarm optimizer with timevarying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 2004, 8(3):240-255. Herzenstein M, Dholakia U M, Andrews R L. Strategic herding behavior in peer-to-peer loan auctions. Journal of Interactive Marketing, 2011, 25(1):27-36. Swan D C, Hare J F. The first cut is the deepest:Primary syllables of Richardson's ground squirrel, Spermophilus richardsonii, repeated calls alert receivers. Animal Behaviour, 2008, 76(1):47-54. Thompson A B, Hare J F. Neighbourhood watch:Multiple alarm callers communicate directional predator movement in Richardson's ground squirrels, Spermophilus richardsonii. Animal Behaviour, 2010, 80(2):269-275. Patel A. Survival of the fittest and zero sum games. Fluctuation and Noise Letters, 2002, 2(4):279-284. Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6(1):58-73. Mehrabian A R, Lucas C. A novel numerical optimization algorithm inspired from weed colonization. Ecological Informatics, 2006, 1(4):355-366. Pourjafari E, Mojallali H. Solving nonlinear equations systems with a new approach based on invasive weed optimization algorithm and clustering. Swarm and Evolutionary Computation, 2012, 4:33-43. Yang Y, Li C, Zhou H Y. CUDA-NP:Realizing nested thread-level parallelism in GPGPU applications. Journal of Computer Science and Technology, 2015, 30(1):3-19. Qi R Z, Wang Z J, Li S Y. A parallel genetic algorithm based on spark for pairwise test suite generation. Journal of Computer Science and Technology, 2016, 31(2):417-427. Guthaus MR, Ringenberg J S, Ernst D, Austin TM,Mudge T, Brown R B. MiBench:A free, commercially representative embedded benchmark suite. In Proc. the 4th IEEE Annual Workshop on Workload Characterization, Workload Characterization, Dec. 2001, pp.3-14. Yan X H, He F Z, Chen Y L, Yuan Z Y. An efficient improved particle swarm optimization based on prey behavior of fish schooling. Journal of Advanced Mechanical Design, Systems, and Manufacturing, 2015, 9(4):JAMDSM0048:1-JAMDSM0048:11. Zhou Y, He F Z, Qiu Y M. Optimization of parallel iterated local search algorithms on graphics processing unit. The Journal of Supercomputing, 2016, 72(6):2394-2416. Zhou Y, He F Z, Qiu Y M. Dynamic strategy based parallel ant colony optimization on GPUs for TSPs. Science China Information Sciences, 2016, doi 10.1007/s11432-015-0594-2. (to be appeared) Wu Y Q, He F Z, Zhang D J, Li X X. Service-oriented feature-based data exchange for cloud-based design and manufacturing. IEEE Transactions on Services Computing, 2016, pp(99), doi 10.1109/TSC.2015.2501981. Zhang D J, He F Z, Han S H, Li X X. Quantitative optimization of interoperability during feature-based data exchange. Integrated Computer-Aided Engineering, 2016, 23(1):31-50. Cheng Y, He F Z, Wu Y Q, Zhang D J. Meta-operation conflict resolution for human-human interaction in collaborative feature-based CAD systems. Cluster Computing, 2016, 19(1):237-253. Lv X, He F Z, Cai W W, Cheng Y. A string-wise CRDT algorithm for smart and large-scale collaborative editing systems. Advanced Engineering Informatics, 2016, doi 10.1016/j.aei.2016.10.005. Li K, He F Z, Chen X. Real-time object tracking via compressive feature selection. Frontiers of Computer Science, 2016, 10(4):689-701. Sun J, He F Z, Chen Y, Chen X. A multiple template approach for robust tracking of fast motion target. Applied Mathematics-A Journal of Chinese Universities, 2016, 31(2):177-197. Ni B, He F Z, Yuan Z Y. Segmentation of uterine fibroid ultrasound images using a dynamic statistical shape model in HIFU therapy. Computerized Medical Imaging and Graphics, 2015, 46(part3):302-314. Ni B, He F Z, Pan Y T, Yuan Z Y. Using shapes correlation for active contour segmentation of uterine fibroid ultrasound images in computer-aided therapy. Applied Mathematics-A Journal of Chinese Universities, 2016, 31(1):37-52. Yu H P, He F Z, Pan Y T, Chen X. An efficient similaritybased level set model for medical image segmentation. Journal of Advanced Mechanical Design, Systems, and Manufacturing, 2016, 10(8):JAMDSM0100. Jiang G, Wu J, Lam S K, Srikanthan T, Sun J. Algorithmic aspects of graph reduction for hardware/software partitioning. The Journal of Supercomputing, 2015, 71(6):2251-2274.