Bouraoui OUNI, Abdellatif MTIBAA, Mehdi JEMAI, Sonia DIMASSI

A metaheuristic based on the tabu search for hardware-software partitioning

Several metaheuristics have become increasingly interesting in solving combinatorial problems. In this paper,we present an algorithm involving a metaheuristic based on tabu search and binary search trees to address the problem ofhardware-software partitioning. Metaheuristics do not guarantee an optimum solution, but they can produce acceptablesolutions in a reasonable time. Our proposed algorithm seeks to nd the efficient hardware-software partitioning thatminimizes the logic area of a system on a programmable chip under the condition of time constraints. Our goal is to havea better trade-off between the logic area of the application and its execution time. Finally, we compare our algorithm tosome metaheuristic-based algorithms.

PDF

___

[1]Hidalgo JI, Lanchares J. Functional partitioning for hardware-software codesign using genetic algorithms. In: IEEE1997 New Frontiers of Information Technology, Proceedings of the 23rd EUROMICRO Conference; 14 September1997; Budapest, Hungary. New York, NY, USA: IEEE. pp. 631-638.
[2]Ernst R, Henkel J, Benner T. Hardware-software co-synthesis for micro-controllers. IEEE Des Test Comp 1993; 10:64-75.
[3]Harkin J, McGinnity TM, Maguire LP. Partitioning methodology for dynamically recon gurable embedded systems.IEE Proc-E 2000; 147: 391-396.
[4]Bianco L, Auguin M, Gogninal G. Path analysis based partitioning for time constrained embedded systems. In:CODES/CASHE Proceedings of the Sixth Hardware/Software Codesign Conference; 1998. pp. 85-89.
[5]Bouraoui O, Ramzi A, Abdellatif M. Combining temporal partitioning and temporal placement techniques forcommunication cost improvement. Adv Eng Software 2011; 42: 444-451.
[6]Bouraoui O, Ramzi A, Abdellatif M. Temporal partitioning of data ow graph for dynamically recon gurablearchitecture. J Syst Archit 2011; 57: 790-798.
[7]Bouraoui O, Abdellatif M. Optimal placement of modules on partially recon gurable device for recon guration timeimprovement. Microelectron Int 2012; 29: 101-107.
[8]Ramzi A, Bouraoui O, Abdellatif M. A partitioning methodology that optimizes the communication cost forrecon gurable computing systems. Int J Autom Comput 2012; 9: 280-287.
[9]Mehdi J, Sonia D, Bouraoui O, Abdellatif M. Optimization of logic area for System on Programmable Chip based onhardware-software partitioning. In: ACEEE 2014 International Conference on Embedded Systems and Applications;2224 March 2014; Hammamet, Tunisia. pp 236-238.
[10]Chatha K, Vemuri R. Hardware-software partitioning and pipelined scheduling of transformative applications. IEEET VLSI Syst 2002; 10: 193-208.
[11]Banerjee S, Bozorgzadeh E, Dutt ND. Integrating physical constraints in HW-SW partitioning for architectureswith partial dynamic recon guration. IEEE T VLSI Syst 2006; 14: 1189-1202.
[12]Wu J, Srikanthan T. Low-complex dynamic programming algorithm for hardware/software partitioning. InformProcess Lett 2006; 98: 41-46.
[13]Reeves CR. Modern Heuristic Techniques for Combinatorial Problems. Oxford, UK: Blackwell Scienti c Publica-tions, 1993.
[14]Aarts E, Lenstra JK. Local Search in Combinatorial Optimization. New York, NY, USA: Wiley, 1997.
[15]Henkel J, Ernst R. An approach to automated hardware/software partitioning using a exible granularity that isdriven by high-level estimation techniques. IEEE T VLSI Syst 2001; 9: 273-289.
[16]Dick R, Jha N. MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributedembedded systems. IEEE T Comput Aid D 1998; 17: 920-935.
[17]Eles P, Peng Z, Kuchcinski K, Doboli A. System level hardware/software partitioning based on simulated annealingand Tabu search. Des Autom Embed Syst 1997; 2: 5-32.
[18]Papadimitriou C, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. New York, NY, USA:Prentice Hall, 1982.
[19]Ribeiro C, Maculan N. Applications of Combinatorial Optimization. Basel, Switzerland: J.C. Baltzer, 1994.
[20]Garey M, Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY,USA: W.H. Freeman and Company, 1979.
[21]Nicholson T. Optimization in Industry: Optimization Techniques. London, UK: Longman Press, 1971.
[22]Laporte G, Osman IH. Metaheuristics in Combinatorial Optimization. Basel, Switzerland: J.C. Baltzer, 1996.
[23]Osman IH, Kelly JP. Meta-Heuristics: Theory and Applications. Boston, MA, USA: Kluwer Academic Publishers,1996.
[24]Glover F. Future paths for integer programming and links to arti cial intelligence. Comput Oper Res 1986; 13:533-549.
[25]Mehdi J, Bouraoui O. Hardware software partitioning of control data ow graph on system on programmable chip.Microprocess Microsy 2015; 39: 259-270.
[26]Pankaj KN, Dilip D. Multi-objective hardwaresoftware partitioning of embedded systems: a case study of JPEGencoder. Appl Soft Comput 2014; 15: 30-41.
[27]Sonia D, Mehdi J, Bouraoui O, Abdellatif M. Hardware-software partitioning algorithm based on binary search treesand genetic algorithm to optimize logic area for SOPC. Journal of Theoretical and Applied Information Technology2014; 66: 788-794.