
›› 2017,Vol. 32 ›› Issue (2): 340355.doi: 10.1007/s1139001717142
所属专题： Computer Architecture and Systems； Software Systems
• Special Section on Selected Paper from NPC 2011 • 上一篇 下一篇
XiaoHu Yan, Member, CCF, FaZhi He^{*}, Member, CCF, YiLin Chen
XiaoHu Yan, Member, CCF, FaZhi He^{*}, Member, CCF, YiLin Chen
随着嵌入式系统设计复杂度的增加，软硬件划分已成为软硬件协同设计中的关键优化难题。文中提出基于野草扰动粒子群算法（Position Disturbed Particle Swarm Optimization with Invasive Weed Optimization，PDPSOIWO）的新型软硬件划分方法。当地松鼠察觉到有潜在捕食者的时候，就会发出警告信息，通知同类远离危险。在PDPSO中，通过模拟这种智能行为，粒子远离群体中全局最差的个体，保持种群多样性，以减少陷入局部最优的可能性。通过改进野草算法（Invasive Weed Optimization，IWO）的初始化和繁殖策略，将IWO集成到PDPSOIWO中，以提高算法在当前全局最优解附近的搜索精度。将PDPSO和改进的IWO融合为PDPSOIWO算法，能同时增强搜索的多样性和集中性。提出HNodeRank方法用于初始化PDPSOIWO的种群，能进一步提升解的质量。由于软硬划分算法中最耗时的过程是计算软硬件的通信代价，文中采用GPU加速该过程，从而能有效减少求解大规模软硬件划分问题的运行时间。最后，通过基准任务和特大规模任务测试集验证了本文方法的有效性。
[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):139141. [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):383391. [3] Hidalgo J I, Lanchares J. Functional partitioning for hardwaresoftware codesign using genetic algorithms. In Proc. the 23rd EUROMICRO Conference on New Frontiers of Information Technology, Sept. 1997, pp.631638. [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):136156. [5] Wu J G, Srikanthan T. Lowcomplex dynamic programming algorithm for hardware/software partitioning. Information Processing Letters, 2006, 98(2):4146. [6] Madsen J, Grode J, Knudsen P V, Petersen M E, Haxthausen A. LYCOS:The Lyngby cosynthesis system. Design Automation for Embedded Systems, 1997, 2(2):195235. [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. Hardwaresoftware partitioning and pipelined scheduling of transformative applications. IEEE Transactions on Very Large Scale Integration Systems, 2002, 10(3):193208. [9] Wu J G, Thambipillai S. A branchandbound algorithm for hardware/software partitioning. In Proc. the 4th International Symposium on Signal Processing and Information Technology, Dec. 2004, pp.526529. [10] Niemann R, Marwedel P. An algorithm for hardware/software partitioning using mixed integer linear programming. Design Automation for Embedded Systems, 1997, 2(2):165193. [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.225230. [12] Gupta R K, De Micheli G. Hardwaresoftware cosynthesis for digital systems. IEEE Design & Test of Computers, 1993, 10(3):2941. [13] Wiangtong T, Cheung P Y K, Luk W. Comparing three heuristic search methods for functional partitioning in hardwaresoftware codesign. Design Automation for Embedded Systems, 2002, 6(4):425449. [14] Purnaprajna M, Reformat M, Pedrycz W. Genetic algorithms for hardwaresoftware partitioning and optimal resource allocation. Journal of Systems Architecture, 2007, 53(7):339354. [15] Dick R P, Jha N K. MOGAC:A multiobjective genetic algorithm for hardwaresoftware cosynthesis of distributed embedded systems. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 1998, 17(10):920935. [16] Janakiraman N, Kumar P N. Multiobjective module partitioning design for dynamic and partial reconfigurable systemonchip using genetic algorithm. Journal of Systems ArchitectureEmbeded Systems Design, 2014, 60(1):119139. [17] Henkel J, Ernst R. An approach to automated hardware/software partitioning using a flexible granularity that is driven by highlevel estimation techniques. IEEE Transactions on Very Large Scale Integration Systems, 2001, 9(2):273289. [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):409420. [19] Wu J G, Srikanthan T, Chen G. Algorithmic aspects of hardware/software partitioning:1D search algorithms. IEEE Transactions on Computers, 2010, 59(4):532544. [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):532. [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):118134. [22] Wang G, Gong W, Kastner R. A new approach for task level computational resource bipartitioning. In Proc. the 15th IASTED International Conference on Parallel and Distributed Computing and Systems, June 2003, pp.439444. [23] Xiong Z, Li S, Chen J. Hardware/software partitioning based on ant optimization with initial pheromone. Computer Research and Development, 2005, 42(12):21762183. (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 SystemonChip for RealTime Applications, Dec. 2006, pp.189194. [25] Abdelhalim M B, Habib S E D. An integrated highlevel hardware/software partitioning methodology. Design Automation for Embedded Systems, 2011, 15(1):1950. [26] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. Bell Labs Technical Journal, 1970, 49(2):291307. [27] Fiduccia C M, Mattheyses R M. A lineartime heuristic for improving network partitions. In Proc. the 19th Design Automation Conference, June 1982, pp.175181. [28] Saab Y G. A fast and robust network bisection algorithm. IEEE Transactions on Computers, 1995, 44(7):903913. [29] Vahid F, Gajski D D. Clustering for improved systemlevel functional partitioning. In Proc. the 8th International Symposium on System Synthesis, Sept. 1995, pp.2835. [30] LópezVallejo M, López J C. On the hardwaresoftware partitioning problem:System modeling and partitioning techniques. ACM Transactions on Design Automation of Electronic Systems, 2003, 8(3):269297. [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):237261. [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.197202. [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.2227. [34] Ernst R, Henkel J, Benner T. Hardwaresoftware cosynthesis for microcontrollers. IEEE Design & Test of Computers, 1993, 10(4):6475. [35] Wolf W H. An architectural cosynthesis algorithm for distributed, embedded computing systems. IEEE Transactions on Very Large Scale Integration Systems, 1997, 5(2):218229. [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):20332040. (in Chinese) [37] Abdelhalim M B, Salama A E, Habib S E D. Constrained and unconstrained hardwaresoftware partitioning using particle swarm optimization technique. In Proc. IIESS, May 30June 1, pp.207220. [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.171176. [39] Eimuri T, Salehi S. Using DPSO and B&B algorithms for hardware/software partitioning in codesign. In Proc. the 2nd International Conference on Computer Research and Development, May 2010, pp.416420. [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 (PSOIC) algorithm. In Proc. IEEE International Conference on Information and Automation (ICIA), June 2010, pp.490494. [41] Xue J, Jin Y. Position disturbed particle swarm optimization. Computer Engineering and Design, 2014, 35(3):10371040. (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.449459. [43] Farahani A F, Kamal M, SalmaniJelodar M. Parallelgeneticalgorithmbased HW/SW partitioning. In Proc. the 5th IEEE International Symposium on Parallel Computing in Electrical Engineering, Sept. 2006, pp.337342. [44] Cooke P, Fowers J, Brown G, Stitt G. A tradeoff analysis of FPGAS, GPUS, and multicores for slidingwindow applications. ACM Transactions on Reconfigurable Technology and Systems, 2015, 8(1):2:12:24. [45] Bordoloi U D, Chakraborty S. GPUbased acceleration of systemlevel design tasks. International Journal of Parallel Programming, 2010, 38(3/4):225253. [46] Du H Z, Xia N, Jiang J G, Xu L N, Zheng R. A monte carlo enhanced PSO algorithm for optimal QoM in multichannel wireless networks. Journal of Computer Science and Technology, 2013, 28(3):553563. [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):175185. [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):240255. [49] Herzenstein M, Dholakia U M, Andrews R L. Strategic herding behavior in peertopeer loan auctions. Journal of Interactive Marketing, 2011, 25(1):2736. [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):4754. [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):269275. [52] Patel A. Survival of the fittest and zero sum games. Fluctuation and Noise Letters, 2002, 2(4):279284. [53] Clerc M, Kennedy J. The particle swarmexplosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6(1):5873. [54] Mehrabian A R, Lucas C. A novel numerical optimization algorithm inspired from weed colonization. Ecological Informatics, 2006, 1(4):355366. [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:3343. [56] Yang Y, Li C, Zhou H Y. CUDANP:Realizing nested threadlevel parallelism in GPGPU applications. Journal of Computer Science and Technology, 2015, 30(1):319. [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):417427. [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.314. [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:1JAMDSM0048: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):23942416. [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/s1143201505942. (to be appeared) [62] Wu Y Q, He F Z, Zhang D J, Li X X. Serviceoriented featurebased data exchange for cloudbased 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 featurebased data exchange. Integrated ComputerAided Engineering, 2016, 23(1):3150. [64] Cheng Y, He F Z, Wu Y Q, Zhang D J. Metaoperation conflict resolution for humanhuman interaction in collaborative featurebased CAD systems. Cluster Computing, 2016, 19(1):237253. [65] Lv X, He F Z, Cai W W, Cheng Y. A stringwise CRDT algorithm for smart and largescale collaborative editing systems. Advanced Engineering Informatics, 2016, doi 10.1016/j.aei.2016.10.005. [66] Li K, He F Z, Chen X. Realtime object tracking via compressive feature selection. Frontiers of Computer Science, 2016, 10(4):689701. [67] Sun J, He F Z, Chen Y, Chen X. A multiple template approach for robust tracking of fast motion target. Applied MathematicsA Journal of Chinese Universities, 2016, 31(2):177197. [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):302314. [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 computeraided therapy. Applied MathematicsA Journal of Chinese Universities, 2016, 31(1):3752. [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):22512274. 
No related articles found! 
版权所有 © 《计算机科学技术学报》编辑部 本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn 总访问量： 