PARTITIONING AND SCHEDULING RESOLUTION PROBLEMS BY BEES MATING STRATEGY IN DRES’ SYSTEMS
Keywords:Dynamic Reconfiguration, HW/SW partitioning, scheduling, HBMO, optimization.
AbstractIn 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.
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.
How to Cite
LicenseInternational Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.