PARTITIONING AND SCHEDULING RESOLUTION PROBLEMS BY BEES MATING STRATEGY IN DRES’ SYSTEMS

Authors

  • Yahyaoui Khadidja

DOI:

https://doi.org/10.47839/ijc.16.2.886

Keywords:

Dynamic Reconfiguration, HW/SW partitioning, scheduling, HBMO, optimization.

Abstract

In last years, several approaches have been proposed for solving the Hardware/Software partitioning and scheduling problem in dynamically reconfigurable embedded systems (DRESs), directed by metaheuristic algorithms. Honey Bees Mating Optimization (HBMO) algorithm is one of these advanced methods. It is a nature inspired algorithm which simulates the process of real honey-bees mating. In this work, we propose a variant of the Honey-bee Mating Optimization Algorithm for solving Hardware/software (HW/SW) partitioning and scheduling problems in DRESs. The algorithm is used in a hybrid scheme with other metaheuristic algorithms for successfully solving these problems. More precisely, the proposed algorithm (HBMO_ DRESs) combines a Honey Bees Mating Optimization (HBMO) algorithm, the Tabu Search (TS) and Simulated Annealing (SA)). From an acyclic task graph and a set of Area-Time implementation trade off points for each task, the adopted method performs HW/SW partitioning and scheduling such that the global application execution time is minimized. Comparing the proposed method with Genetic Algorithm and Evolutionary Strategies (ES), the simulation results show that the proposed algorithm has better convergence performance.

References

Y. Jing, J. Krang, J. Du and B. Hu, “Application of improved simulated annealing optimization algorithms in hardware/software partitioning of the system on chip”, Springer, pp. 532-540, 2011.

R. Ayadi, B. Ouni and A. Mtibaa, “A partitioning methodology that optimizes the communication cost for reconfigurable computing systems,” International Journal of Automation and Computing (IJAC), Institute of Automation and Springer-Verlag Publishers, Vol. 9, No. 3, pp. 280-287, June 2012.

M.B. Abdelhalim, S.E.-D. Habib, “An integrated high-level hardware/software partitioning methodology,” Des Autom Embed Syst., No. 15, pp. 19-50, 2011.

P. Arat, Z.A. Mann, and A. Orbn, “Algorithmic aspects of hardware/software partitioning,” ACM Transactions on Design Automation of Electronic Systems (TODAES), Vol. 10, Issue 1, 136-156, 2005.

S. Luo, X. Ma, Y.i Lu, “An advanced non-dominated sorting genetic algorithm based SOC hardware/software partitioning,” Acta Electronica Sinica, Vol. 11, pp. 2595-2599, 2009.

S. Dimassi, M. Dijemai, B. Ouni, A. Mtibaa, “Hardware-software partitioning algorithm based on binary search trees and genetic algorithm to optimize logic area for sopc,” Journal of Theoretical and Applied Information Technology (JATIT), Vol. 66, No. 3, pp. 788-794, 2014.

F. Vahid, “Modifying min-cut for hardware and software functional partitioning,” in Proceedings of the 5th International Workshop on Hardware/Software Co-Design (CODES/CASHE97), Braunschweig, Germany, 1997, pp. 43-48.

F. Ferrandi, P. L. Lanzi, C. Pilato, D. Sciuto, A. Tumeo, “Ant colony optimization for mapping, scheduling and placing in reconfigurable systems,” in Proceedings of the NASA/ESA Conference on Adaptive Hardware and Systems (AHS), 2013.

M. Koudil, K. Benatchba, A. Tarabet, E. Batoul Sahraoui, “Using bees to solve partitioning and scheduling problem in codesign,” Applied Mathematics and Computation, Vol. 186, pp. 1710-1722, 2007.

H. Daz Pando1, S. C. Asensi, R. Seplveda Lima, J. F. Caldern and A. Rosete Suarez, “An application of fuzzy logic for hardware/software partitioning in embedded systems,” Computacion y Sistemas, Vol. 17, No. 1, pp. 25-39, 2013.

G. Rehaiem, H. Gharsellaoui, S. Ben Ahmed, “A neural networks based approach for the real-time scheduling of reconfigurable embedded systems with minimization of power consumption,” in Proceedings of the International Conference ICIS’2016, Okayama, Japan, June 26-29, 2016.

K. Yahyaoui, M. Bouchoicha, “A hardware-software partitioning and scheduling approach for dynamically reconfigurable embedded systems,” Proceedings of the International Conference ICHICS’S16, Morocco, 2016.

H.A. Abbas, “A single queen single worker honey bees approach to 3-Sat problem,” in Proceedings of the Genetic and Evolutionary Computation Conference GECCO’2001, San Francisco, USA, July 2001.

K. Yahyaoui, F. Debbat, M.F. Khelfi, “HBMO Hybridization: Application to real-time task scheduling,” The Mediterranean Journal of Computers Networks (MJCN), No. 2, 2012.

Y. Marinakis, M. Marinaki, G. Dounias, “Honey bees mating optimization algorithm for large scale vehicle routing problems,” Natural Computing, No. 9, pp. 5-27, 2010.

M. Koudil, K. Benatchba, A. Tarabet, E. Sahraoui, “Using bees to solve partitioning and scheduling problem in codesign,” Applied Mathematics and Computation, Vol. 186, pp. 1710-1722, 2007.

N. Yousefi and H. Ebrahimian, “Optimal design of multi-machine power system stabilizers using interactive honey bee mating optimization,” Trends in life science (TLS) Dama International Journal, Vol. 4, Issue 1, 2015.

N. Sabar, M. Ayob and G. Kendall, “Solving examination timetabling problems using honey-bee mating optimization (ETP-HBMO),” in Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), Dublin, Ireland, 2009.

M. Fleischer, “Simulated annealing: Past, present, and future,” in Proceedings of the Winter Simulation Conference, 1995.

F. Glover, “Tabu search part I,” ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206, 1989.

H. Han, W. Liu, W. Jigang, G. Jiang, “Efficient algorithm for hardware/ software partitioning and scheduling on MPSoC,” Journal of Computers, Vol. 8, No. 1, pp. 61-68, 2013.

Downloads

Published

2017-06-30

How to Cite

Khadidja, Y. (2017). PARTITIONING AND SCHEDULING RESOLUTION PROBLEMS BY BEES MATING STRATEGY IN DRES’ SYSTEMS. International Journal of Computing, 16(2), 97-105. https://doi.org/10.47839/ijc.16.2.886

Issue

Section

Articles