›› 2017,Vol. 32 ›› Issue (2): 340-355.doi: 10.1007/s11390-017-1714-2

所属专题: Computer Architecture and Systems Software Systems

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

基于野草扰动粒子群算法的新型软硬件划分方法

Xiao-Hu Yan, Member, CCF, Fa-Zhi He*, Member, CCF, Yi-Lin Chen   

  1. 1 State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China;
    2 School of Computer Science, Wuhan University, Wuhan 430072, China
  • 收稿日期:2016-07-27 修回日期:2016-12-24 出版日期:2017-03-05 发布日期:2017-03-05
  • 通讯作者: Fa-Zhi He E-mail:fzhe@whu.edu.cn
  • 作者简介: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.
  • 基金资助:

    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.

A Novel Hardware/Software Partitioning Method Based on Position Disturbed Particle Swarm Optimization with Invasive Weed Optimization

Xiao-Hu Yan, Member, CCF, Fa-Zhi He*, Member, CCF, Yi-Lin Chen   

  1. 1 State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China;
    2 School of Computer Science, Wuhan University, Wuhan 430072, China
  • Received:2016-07-27 Revised:2016-12-24 Online:2017-03-05 Published:2017-03-05
  • Contact: Fa-Zhi He E-mail:fzhe@whu.edu.cn
  • 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.
  • Supported by:

    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.

随着嵌入式系统设计复杂度的增加,软硬件划分已成为软硬件协同设计中的关键优化难题。文中提出基于野草扰动粒子群算法(Position Disturbed Particle Swarm Optimization with Invasive Weed Optimization,PDPSO-IWO)的新型软硬件划分方法。当地松鼠察觉到有潜在捕食者的时候,就会发出警告信息,通知同类远离危险。在PDPSO中,通过模拟这种智能行为,粒子远离群体中全局最差的个体,保持种群多样性,以减少陷入局部最优的可能性。通过改进野草算法(Invasive Weed Optimization,IWO)的初始化和繁殖策略,将IWO集成到PDPSO-IWO中,以提高算法在当前全局最优解附近的搜索精度。将PDPSO和改进的IWO融合为PDPSO-IWO算法,能同时增强搜索的多样性和集中性。提出HNodeRank方法用于初始化PDPSO-IWO的种群,能进一步提升解的质量。由于软硬划分算法中最耗时的过程是计算软硬件的通信代价,文中采用GPU加速该过程,从而能有效减少求解大规模软硬件划分问题的运行时间。最后,通过基准任务和特大规模任务测试集验证了本文方法的有效性。

Abstract: 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.

[1] 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.

[2] 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.

[3] 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.

[4] 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.

[5] Wu J G, Srikanthan T. Low-complex dynamic programming algorithm for hardware/software partitioning. Information Processing Letters, 2006, 98(2):41-46.

[6] 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.

[7] Strachacki M. Speedup of branch and bound method for hardware/software partitioning. In Proc. the 1st International Conference on Information Technology, May 2008.

[8] 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.

[9] 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.

[10] 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.

[11] 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.

[12] Gupta R K, De Micheli G. Hardware-software cosynthesis for digital systems. IEEE Design & Test of Computers, 1993, 10(3):29-41.

[13] 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.

[14] 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.

[15] 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.

[16] 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.

[17] 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.

[18] 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.

[19] 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.

[20] 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.

[21] 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.

[22] 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.

[23] 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)

[24] 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.

[25] 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.

[26] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. Bell Labs Technical Journal, 1970, 49(2):291-307.

[27] 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.

[28] Saab Y G. A fast and robust network bisection algorithm. IEEE Transactions on Computers, 1995, 44(7):903-913.

[29] 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.

[30] 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.

[31] 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.

[32] 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.

[33] 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.

[34] Ernst R, Henkel J, Benner T. Hardware-software cosynthesis for microcontrollers. IEEE Design & Test of Computers, 1993, 10(4):64-75.

[35] 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.

[36] 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)

[37] 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.

[38] 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.

[39] 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.

[40] 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.

[41] Xue J, Jin Y. Position disturbed particle swarm optimization. Computer Engineering and Design, 2014, 35(3):1037-1040. (in Chinese)

[42] 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.

[43] 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.

[44] 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.

[45] Bordoloi U D, Chakraborty S. GPU-based acceleration of system-level design tasks. International Journal of Parallel Programming, 2010, 38(3/4):225-253.

[46] 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.

[47] 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.

[48] 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.

[49] 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.

[50] 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.

[51] 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.

[52] Patel A. Survival of the fittest and zero sum games. Fluctuation and Noise Letters, 2002, 2(4):279-284.

[53] 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.

[54] Mehrabian A R, Lucas C. A novel numerical optimization algorithm inspired from weed colonization. Ecological Informatics, 2006, 1(4):355-366.

[55] 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.

[56] 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.

[57] 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.

[58] 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.

[59] 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.

[60] 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.

[61] 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)

[62] 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.

[63] 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.

[64] 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.

[65] 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.

[66] Li K, He F Z, Chen X. Real-time object tracking via compressive feature selection. Frontiers of Computer Science, 2016, 10(4):689-701.

[67] 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.

[68] 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.

[69] 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.

[70] 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.

[71] 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.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 沈理; Stephen Y.H.Su;. Generalized Parallel Signature Analyzers with External Exclusive-OR Gates[J]. , 1986, 1(4): 49 -61 .
[2] S.T.Chanson; 梁路平; A.Kumar;. Throughput Models of CSMA Network with Stations Uniformly Distributed along the Bus[J]. , 1987, 2(4): 243 -264 .
[3] 孙昱东; 谢志良;. Macro-Dataflow Computational Model and Its Simulation[J]. , 1990, 5(3): 289 -295 .
[4] 郭恒昌;. On the Characterization and Fault Identification of Sequentially t-Diagnosable System Under PMC Model[J]. , 1991, 6(1): 83 -90 .
[5] 王能斌; 刘海青;. An Intelligent Tool to Support Requirements Analysis and Conceptual Design of Database Design[J]. , 1991, 6(2): 153 -160 .
[6] 朱鸿;. Program Transformation by Solving Equations[J]. , 1991, 6(2): 167 -177 .
[7] 宋茂强; FelixGrimm; HorstBunke;. A Prototype Expert System for Automatic Generation of Image Processing Programs[J]. , 1991, 6(3): 296 -300 .
[8] 林珊;. Using a Student Model to Improve Explanation in an ITS[J]. , 1992, 7(1): 92 -96 .
[9] 高济;. Functional Knowledge Representation Based on Problem Reduction[J]. , 1992, 7(2): 105 -113 .
[10] 魏国庆; 马颂德;. 3D Motion Estimation and Motion Fusion by Affine Region Matching[J]. , 1993, 8(1): 17 -25 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: