A Modified Binary Firefly Algorithm to Solve Hardware/Software Partitioning Problem

Khetatba Mourad, Rachid Boudour

Abstract


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.

Full Text:

PDF

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.




DOI: https://doi.org/10.31449/inf.v45i7.3408

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.