A Modified Binary Firefly Algorithm to Solve Hardware/Software Partitioning Problem
DOI:
https://doi.org/10.31449/inf.v45i7.3408Abstract
Hardware/Software (Hw/Sw) partitioning is a crucial step in Hw/Sw co-design that determines which components of the embedded system could be implemented on hardware and which ones on software. It aims to find a design implementation that fulfils all the specification requirements (functionality, goals and constraints) with a low cost. Most formulations of Hw/Sw partitioning dilemma have proven to NP-hard optimization problem. The firefly algorithm (FA) emerges as a significant tool of Swarm Intelligence that has been applied in many areas of optimization. The main purpose of this paper is to present a modified binary firefly algorithm to solve Hw/Sw partitioning problems. Results are compared with other well-known metaheuristic algorithms: Binary Differential Evolution (BDE) , Discrete Differential Evolution(DDE), Self-adaptive differential evolution algorithm (saBDE), New Modified Binary Differential Evolution (NMBDE), New Binary Differential Evolution(NBDE) , Particle Swarm Optimization Algorithm (PSO), and Genetic Algorithm (GA). The computational results show that it produced better results than the all used algorithms.References
J. Teich( 2012). Hardware/Software Codesign: The Past, the Present, and Predicting the Future. Proceedings of the IEEE, May 13th,Vol. 100.
W. Jigang, T. Srikanthan, and G. Chen (2010). Algorithmic aspects of hardware/software partitioning: 1D search algorithms. Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 59, no. 4, pp. 532–544.
S.A Tahaee and A.H. Jahangir (2010). A Polynomial Algorithm for Partitioning Problems, ACM Trans. Embed. Comput. Syst., vol.9 (4), pp.1–34.
P. Arato, S. Juhasz, Z.A. Mann and A. Orban(2003). Hardware/software partitioning in embedded system design. In Proc. of the IEEE Int. Symposium on Intelligent Signal Processing, pp. 197-202.
X.S. Yang (2008). Nature-Inspired Metaheuristic Algorithms. Luniver Press, UK.
X.S. Yang (2012). Efficiency analysis of swarm intelligence and randomization techniques. Journal of computational and theoretical Nanoscience , vol.9(2) ,pp.189-198.
R.C. Hrosik, , E. Tuba, , E. Dolicanin, R. Jovanovic, and M. Tuba (2019) . Brain Image Segmentation Based on Firefly Algorithm Combined with K-means Clustering, Studies in Informatics and Control, vol. 28(2) , pp.167-176.
M. Zaman, A. Matin, et al.(2012) . Non-uniformly spaced linear antenna array design using firefly algorithm. International journal of microwave science and technoogy , 256759(8 pages).
S. Severin and J. Rossmann (2012). A comparison of different metaheuristic algorithms for optimizing blended PTP movements for industrial robots. Intelligent robotics and applications , pp. 321-330.
S. Delir, A. Foroughi-Asl and S. Talatahari (2019). A Hybrid Charged System Search – Firefly Algorithm For Optimization Of Water Distribution Networks. International Journal Of Optimization In Civil Engineering, vol.9(2), pp. 273-290.
C. Ren, J. Zhao, L. Chen, and Y. Huang (2018). Application of Firefly Algorithm in Scheduling Optimization of Combined Cooling, Heating and Power with Multiple Objectives. Chemical Engineering Transactions, vol.67, pp.829-834. DOI: 10.3303/CET1867139
A. Memari, R. Ahmad, M. R. A. Jokar and Abd. R. A. Rahim (2019). A New Modified Firefly Algorithm for Optimizing a Supply Chain Network Problem. Applied Sciences , pp 12.
J. M. Rubio, C. L. Vidal-Silva, R. Soto, E. Madariaga, F. Johnson and L.Carter (2019). Applying FireFly Algorithm to Solve the Problem of Balancing Curricula. International Journal of Advanced Computer Science and Applications, Vol. 10, No. 1
S. A. Edwards, L. Lavagno, E. A. Lee et al.(1997). Design of Embedded Systems: Formal Models Validation, and Synthesis. Proceedings of the IEEE, vol.85(3), pp.366-390.
B. Mei, P. Schaumont and S.Vernalde (2000). A hardware-software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems. In Proceedings of ProRISC. Citeseer, pp. 405–411.
R. Ernst, J. Henkel and T. Benner (2002). Hardware-software cosynthesis for microcontrollers. Readings in hardware/software co-design, pp. 18–29.
J. Wu, T. Srikanthan and C. Yan (2008). Algorithmic aspects for power-efficient hardware/software partitioning. Math Comput Simul. ,vol.79(4),pp.1204–1215.
R.S. Rajakumari, K. Hariharan, R. Manikandan and K.R. Sekar (2018). A Survey on various method used in Hardware and Software Partitioning. International Journal of Pure and Applied Mathematics, Vol. 118 No. 18 ,pp.2365-2385.
M.M. Shehab, A.T. Khader and M.A. Al-Betar (2016). New selection schemes for particle swarm optimization. IEEE Transactions on Electronics, Information and Systems, vol. 136(12), pp.1706-1711.
M. Riabi, Y. Manai and J. Haggege (2015). Hardware/Software partitioning approach for embedded system design based on genetic algorithm. International Journal of Scientific Research & Engineering Technology, vol. 3, issue 3, pp. 20-25.
A. Musrrat, P. Millie, K. N. Atulya and W. A. Chang (2012). Two Local Search Strategies for Differential Evolution. Journal of Universal Computer Science, vol. 18, no. 13 ,pp. 1853-1870.
J. Dai, H. Han, Q. Hu and M. Liu (2016). Discrete particle swarm optimization approach for cost sensitive attribute reduction. Knowl. Based Syst. , vol.102,pp.116-126.
X.S. Yang (2009). Firefly algorithms for multimodal optimization, Stochastic Algorithms. Foundations and Applications (SAGA) Lecture Notes in Computer Sciences, 5792,pp.169–78.
] X.S. Yang (2010). Firefly Algorithm, Levy Flights and Global Optimization. Research and Development in Intelligent Systems XXVI (Eds M. Bramer, R. Ellis, Petridis), Springer London, pp. 209-218
S. Palit, S. Sinha, , M. Molla, , A. Khanra and M. Kule (2011). A cryptanalytic attack on the knapsack cryptosystem using binary firefly algorithm. In : the second international conference on computer and communication technology, IEEE, pp.428-432.
R. Falcon, M. Almeida and A. Nayak (2011). Fault identification with binary adaptive fireflies in parallel and distributed systems. In : IEEE congress on evolutionary computation (CEC-2011), IEEE, pp.1359-1366.
K. Chandrasekaran and S. Simon (2012). Network and reliability constrained unit commitment problem using binary real coded firefly algorithm. International journal of electrical power & energy systems , vol. 43(1) , pp. 921-932.
P.Arató, Z. Á. Mann and A. Orbán (2005). Algorithmic aspects of hardware/software partitioning. ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 10, no. 1, pp. 136–156.
K. Yahyaoui (2017). Partitioning And Scheduling Resolution Problems By Bees Mating Strategy In Dres’ Systems. International Journal of Computing, vol. 16(2), pp.97-105.
G. Li, J. Feng, C. Wang and J. Wang (2014). Hardware/software partitioning algorithm based on the combination of genetic algorithm and tabu search. Engineering Review, vol. 34, no. 2, pp. 151 –160.
T.-Y. Lee, Y.-H. Fan, Y.-M. Cheng, C.-C. Tsai and R.-S. Hsiao (2007). Enhancement of hardware-software partition for embedded multiprocessor FPGA systems. In Third International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IIHMSP 2007, vol. 1. IEEE, 2007, pp. 19–22.
M. B. Abdelhalim and S.-D. Habib (2011). An integrated high-level hardware/software partitioning methodology. Design Automation for Embedded Systems, vol. 15, no. 1, pp. 19–50.
P. K. Nath and D.Datta (2014). Multi-objective hardware–software partitioning of embedded systems: A case study of JPEG encoder. Applied Soft Computing, vol. 15, pp. 30–41.
E. Sha, L. Wang, Q. Zhuge, J. Zhang and J. Liu(2013). Power efficiency for hardware/software partitioning with time and area constraints on MPSOC. International Journal of Parallel Programming, pp. 1 –22.
M. Lopez-Vallejo and J. Lopez (2033). On the hardware-software partitioning problem: System modeling and partitioning techniques. ACM Transactions on Design Automation of Electronic Systems, vol. 8(3),pp.269–297. doi:10.1145/785411.785412.
N. Govil and S. R. Chowdhury (2015). A High Speed Metaheuristic Algorithmic Approach to Hardware Software Partitioning for Low-cost SoCs. International Symposium on Rapid System Prototyping (RSP) ,2015.
X. Zhao, H. Zhang, Y. Jiang, S. Song, X. Jiao and M.Gu (2013). An Effective Heuristic-Based Approach for Partitioning. Journal of Applied Mathematics, Vol. 2013, Article ID 138037, 8 pages.
L.Weijia , L. Lanying , S. Jianda , L. Zhiqiang, and F. Guan (2014). Hardware/software partitioning of combination of clustering algorithm and genetic algorithm. International journal of control and automation, vol. 7, no. 1,pp 347-356.
X.-H. Yan, F.Z. He and Y.L. Chen (2017). A Novel Hardware/Software Partitioning Method Based on Position Disturbed Particle Swarm Optimization with Invasive Weed
Optimization. Journal Of Computer Science And Technology, vol. 32(2),pp. 340–355.
Task Graphs for Free (TGFF v3.0) [EB/OL]. [2012-11-20]. http://z iyang.eecs.umich.edu/ dickrp/tgff/.
A. K.Qin and P. N. Suganthan (2005). Self-adaptive differential evolution algorithm for numerical optimization. In Proceedings of IEEE Congress on Evolutionary Computation, vol. 2, pp. 1785–1791.
J. Krause and H. S. Lopes (2013). A Comparison of Differential Evolution Algorithm with Binary and Continuous Encoding for the MKP. BRICS Congress on Computational Intelligence & 11th Brazilian Congress on Computational Intelligence, 2013.
H. Xingshi and L.Han (2007). A novel binary differential evolution algorithm based on artificial immune system, IEEE congress on evolutionary computation (CEC 2007) , pp.2267-2272.
A. W. Mohamed (2016). A New Modified Binary Differential Evolution Algorithm and its Applications. Applied Mathematics & Information Sciences, vol.10, No. 5, pp. 1965-1969.
Downloads
Published
How to Cite
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
