logo

SCIENTIA SINICA Informationis, Volume 46, Issue 9: 1321-1338(2016) https://doi.org/10.1360/N112016-00006

A parallel hardware/software partitioning method based on conformity particle-swarm optimization with harmony search

Xiaohu YAN1,2,3, Fazhi HE1,2,*, Yilin CHEN1,2
More info
  • ReceivedJan 5, 2016
  • AcceptedMay 3, 2016
  • PublishedSep 9, 2016

Abstract

Hardware/software (HW/SW) partitioning is a key step in HW/SW codesign. With the increasing design complexity of embedded systems, HW/SW partitioning has become a challenging optimization problem. A parallel HW/SW partitioning method based on Conformity Particle-Swarm Optimization with Harmony Search (CPSO-HS) is presented in this paper. Firstly, the particles act as psychological conformists and tend to move towards a security point, with many particles and a lower possibility of being attacked by a predator. By simulating the conformist mentality in CPSO-HS, the searching population can remain varied and the algorithm avoids local optima. Secondly, to improve the initialization strategy, the Harmony Search (HS) is integrated to search for better positions, with which the global best position is updated. Hence, the searching precision and solution quality can be enhanced. The searching diversification and intensification in CPSO-HS can be improved through the two methods. Thirdly, since the time to compute the HW/SW communication cost is the most time-consuming process for the HW/SW partitioning problem, we adopt a multi-core parallel technique to accelerate the computing. Thus, the CPSO-HS runtime for large-scale HW/SW problems can be reduced efficiently in an ordinary PC platform. Finally, a number of experiments on benchmarks from state-of-the-art publications demonstrate that the proposed approach can achieve higher performance than other previous methods.


Funded by

国家自然科学基金(61472289)

湖北省自然科学基金(2015CFB254)


References

[1] Zhang Y G, Luo W J, Zhang Z M, et al. A hardware/software partitioning algorithm based on artificial immune principles. Appl Soft Comput, 2008, 8: 383-391 CrossRef Google Scholar

[2] Arato P, Mann Z A, Orban A. Algorithmic aspects of hardware/software partitioning. ACM Trans Des Automat El, 2005, 10: 136-156 CrossRef Google Scholar

[3] Wu J G, Srikanthan T. Low-complex dynamic programming algorithm for hardware/software partitioning. Inform Process Lett, 2006, 98: 41-46 CrossRef Google Scholar

[4] Madsen J. Lycos: the lyngby cosynthesis system. Des Autom Embed Syst, 1997, 2: 195-235 CrossRef Google Scholar

[5] Chatha K S, Vemuri R. Hardware-software partitioning and pipelined scheduling of transformative applications. IEEE Trans VLSI Syst, 2002, 10: 193-208 CrossRef Google Scholar

[6] Niemann R, Marwedel P. An algorithm for hardware/software partitioning using mixed integer linear programming. Des Autom Embed Syst, 1997, 2: 165-193 CrossRef Google Scholar

[7] Wiangtong T, Cheung P Y K, Luk W. Comparing three heuristic search methods for functional partitioning in hardware-software codesign. Des Autom Embed Syst, 2002, 6: 425-449 CrossRef Google Scholar

[8] Janakiraman N, Kumar P N. Multi-objective module partitioning design for dynamic and partial reconfigurable system-on-chip using genetic algorithm. J Syst Architect, 2014, 60: 119-139 CrossRef Google Scholar

[9] Henkel J, Ernst R. An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. IEEE Trans VLSI Syst, 2001, 9: 273-290 CrossRef Google Scholar

[10] Peng L, Wu J G, Wang Y J. Hybrid algorithms for hardware/software partitioning and scheduling on reconfigurable devices. Math Comput Model, 2013, 58: 409-420 CrossRef Google Scholar

[11] Wu J G, Srikanthan T, Chen G. Algorithmic aspects of hardware/software partitioning: 1D search algorithms. IEEE Trans Comput, 2010, 59: 532-544 CrossRef Google Scholar

[12] Eles P, Peng Z, Kuchcinski K, et al. System level hardware/software partitioning based on simulated annealing and tabu search. Des Autom Embed Syst, 1997, 2: 5-32 CrossRef Google Scholar

[13] Wu J G, Pu W, Lam S K, et al. Efficient heuristic and tabu search for hardware/software partitioning. J Supercomput, 2013, 66: 118-134 CrossRef Google Scholar

[14] Xiong Z H, Li S K, Chen J H. Hardware/software partitioning based on ant optimization with initial pheromone. Comput Res Dev, 2005, 42: 2176-2183 [熊志辉, 李思昆, 陈吉华. 具有初始信息素的蚂蚁寻优软硬件划分算法. 计算机研究与发展, 2005, 42: 2176-2183]. Google Scholar

[15] Badawy W, Salem A. Hardware software partitioning using particle swarm optimization technique. In: Proceedings of the 6th International Workshop on System-on-Chip for Real-Time Applications. Alberta: IEEE Press, 2006. 189-194. Google Scholar

[16] Abdelhalim M B, Habib S E D. An integrated high-level hardware/software partitioning methodology. Des Autom Embed Syst, 2011, 15: 19-50 CrossRef Google Scholar

[17] Lopez V M, Lopez J C. On the hardware-software partitioning problem: system modeling and partitioning techniques. ACM Trans Des Automat El, 2003, 8: 269-297 CrossRef Google Scholar

[18] Bhattacharya A, Konar A, Das S, et al. Hardware software partitioning problem in embedded system design using particle swarm optimization algorithm. In: Proceedings of the 2nd International Conference on Complex, Intelligent and Software Intensive Systems. Barcelona: IEEE Press, 2008. 171-176. Google Scholar

[19] Eimuri T, Salehi S. Using DPSO and B&B algorithms for hardware/software partitioning in co-design. In: Proceedings of the 2nd International Conference on Computer Research and Development. Kuala Lumpur: IEEE Press, 2010. 416-420. Google Scholar

[20] Wu Y, Zhang H, Yang H B. Research on parallel HW/SW partitioning based on hybrid PSO algorithm. Lect Notes Comput Sci, 2009, 5574: 449-459 CrossRef Google Scholar

[21] Chen Z, Wu J G, Song G Z, et al. NodeRank: an efficient algorithm for hardware/software partitioning. Chin J Comput, 2013, 36: 2033-2040 [陈志, 武继刚, 宋国治, 等. NodeRank: 一种高效软硬件划分算法. 计算机学报, 2013, 36: 2033-2040]. Google Scholar

[22] Farmahini F A, Mehdi K, Mehdi S J. Parallel-genetic-algorithm-based HW/SW partitioning. In: Proceedings of the International Symposium on Parallel Computing in Electrical Engineering. Bialystok: IEEE Press, 2006. 337-342. Google Scholar

[23] Bordoloi U D, Chakraborty S. GPU-based acceleration of system-level design tasks. Int J Parallel Prog, 2010, 38: 225-253 CrossRef Google Scholar

[24] Bergh F, Engelbrecht A P. A cooperative approach to particle swarm optimization. IEEE Trans Evolut Comput, 2004, 8: 225-239 CrossRef Google Scholar

[25] Coello C A C, Pulido G T, Lechuga M S. Handling multiple objectives with particle swarm optimization. IEEE Trans Evolut Comput, 2004, 8: 256-279 CrossRef Google Scholar

[26] Zhang D J, He F Z, Wu Y Q. Singular feature interoperability of heterogeneous CAD model based on directed mutation particle swarm optimization. Sci Sin Inform, 2015, 45: 634-649 [张德军, 何发智, 吴亦奇. 一种基于定向变异粒子群算法的异构CAD 模型奇异特征互操作方法. 中国科学: 信息科学, 2015, 45: 634-649]. Google Scholar

[27] Hei Y Q, Li W T, Li X H. Novel scheduling strategy for downlink multiuser MIMO system: particle swarm optimization. Sci Sin Inform, 2011, 41: 1463-1473 [黑永强, 李文涛, 李晓辉. 基于粒子群优化的多用户MIMO下行链路调度算法. 中国科学: 信息科学, 2011, 41: 1463-1473]. Google Scholar

[28] Liu C A, Yan X H, Liu C Y. Dynamic path planning for mobile robot based on improved genetic algorithm. Chinese J Electron, 2010, 19: 245-248. Google Scholar

[29] Ratnaweera A, Halgamuge S K, Watson H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Trans Evolut Comput, 2004, 8: 240-255 CrossRef Google Scholar

[30] Liang J J, Qin A K, Suganthan P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Trans Evolut Comput, 2006, 10: 281-295 CrossRef Google Scholar

[31] Veissier I, Boissy A, Nowak R, et al. Ontogeny of social awareness in domestic herbivores. Appl Anim Behav Sci, 1998, 57: 233-245 CrossRef Google Scholar

[32] Herzenstein M, Dholakia U M, Andrews R L. Strategic herding behavior in peer-to-peer loan auctions. J Interact Mark, 2011, 25: 27-36 CrossRef Google Scholar

[33] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Trans Evolut Comput, 2002, 6: 58-73 CrossRef Google Scholar

[34] Geem Z W, Kim J H, Loganathan G V. A new heuristic optimization algorithm: harmony search. Simulation, 2001, 76: 60-68 CrossRef Google Scholar

[35] Lee K S, Geem Z W. A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice. Comput Method Appl M, 2005, 194: 3902-3933 CrossRef Google Scholar

[36] Mahdavi M, Fesanghary M, Damangir E. An improved harmony search algorithm for solving optimization problems. Appl Math Comput, 2007, 188: 1567-1579. Google Scholar

[37] Kaveh A, Talatahari S. Particle swarm optimizer, ant colony strategy and harmony search scheme hybridized for optimization of truss structures. Comput Struct, 2009, 87: 267-283 CrossRef Google Scholar

[38] Gordon M I, Thies W, Amarasinghe S. Exploiting coarse-grained task, data, and pipeline parallelism in stream programs. In: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems. California: ACM, 2006. 151-162. Google Scholar

[39] Gao W J, Qian K M. Parallel computing in experimental mechanics and optical measurement: a review. Opt Laser Eng, 2012, 50: 608-617 CrossRef Google Scholar

[40] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agent. IEEE Syst Man Cybern, 1996, 26: 29-41 CrossRef Google Scholar

[41] Yan X H, He F Z, Chen Y L, et al. An efficient improved particle swarm optimization based on prey behavior of fish schooling. J Adv Mech Des Syst, 2015, 9: 1-10. Google Scholar

[42] Zhan Z H, Zhang J, Li Y, et al. Adaptive particle swarm optimization. IEEE Syst Man Cybern, 2009, 39: 1362-1381 CrossRef Google Scholar

[43] He F Z, Han S H. A method and tool for human-human interaction and instant collaboration in cscw-based CAD. Comput Ind, 2006, 57: 740-751 CrossRef Google Scholar

[44] Zhang D J, He F Z, Han S H, et al. Quantitative optimization of interoperability during feature-based data exchange. Integr Comput-Aid E, 2016, 23: 31-50. Google Scholar

[45] Jing S X, He F Z, Han S H, et al. A method for topological entity correspondence in a replicated collaborative CAD system. Comput Ind, 2009, 60: 467-475 CrossRef Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1