Abstract

In recent years, meta-heuristics have become increasingly interesting in solving combinatorial problems including hardware-software partitioning. In this paper, we present a comparative study between some algorithms which involve meta-heuristics based on Tabu search, genetic algorithm and Binary Search Trees to address the problem of hardware-software partitioning. In fact, meta-heuristics can produce acceptable solutions within a reasonable time, but they do not guarantee an optimal solution. We have proposed these algorithms to find the efficient hardware-software partition that minimizes the logic area of System on a Programmable Chip while respecting a time constraint. This paper presents an analysis of these meta-heuristics by identifying the fundamental ideas guiding the choice of a meta-heuristic in practice.

References

• Sonia Dimassi, Mehdi Jemai, Bouraoui Ouni and Abdellatif Mtibaa,"Hardware-software partitioning algorithm based on Binary Search Trees and Genetic Algorithm to optimize logic area for SOPC", Published in Journal of Theoretical and Applied Information Technology (JATIT), Vol. 66, No. 3, August 2014.
• C. H. PAPADIMITRIOU, K. STEIGLITZ, Combinatorial optimization – algorithms and complexity. Prentice Hall, 1982.
• C. C. RIBEIRO, N. MACULAN (Eds. ), Applications of combinatorial optimization. Annals of Operations Research 50, 1994.
• M. R. GAREY, D. S. JOHNSON, Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman and Company, New York, 1979.
• Bouraoui Ouni, Ramzi Ayadi and Abdellatif Mtibaa, "Combining Temporal Partitioning and Temporal Placement Techniques for Communication Cost Improvement" Advances in Engineering Software, Elsevier Publishers, Volume 42, no 7, July 2011, pp : 444-451.
• Bouraoui Ouni. , Ramzi Ayadi, and Abdellatif Mtibaa. "Temporal partitioning of data flow graph for dynamically reconfigurable architecture", Journal of Systems Architecture, vol 57, no 8, September 2011, pp 790-798
• Bouraoui Ouni and Abdellatif Mtibaa, "Optimal placement of modules on partially reconfigurable device for reconfiguration time improvement", Microelectronics International published by Emerald Group Publishing Limited, volume 29, Issue 2, 2012, Pages 101-107
• Ramzi Ayadi, Bouraoui Ouni and Abdellatif Mtibaa, "A Partitioning Methodology that Optimizes the Communication Cost for Recongurable Computing Systems" International Journal of Automation and Computing (IJAC), Institute of Automation and Springer-Verlag Publishers, Volume 9, N° 3, June 2012, pp 280-287.
• Mehdi Jemai, Sonia Dimassi, Bouraoui Ouni and Abdellatif Mtibaa, "Optimization of logic area for System on Programmable Chip based on hardware-software partitioning", International Conference on Embedded Systems and Applications (ICESA) Hammamet-Tunisia,March 2014.
• K. Chatha and R. Vemuri, "Hardware-software partitioning and pipelined scheduling of transformative applications," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 10, no. 3, pp. 193–208, 2002.
• S. Banerjee, E. Bozorgzadeh, and N. D. Dutt, "Integrating physical constraints in hw-sw partitioning for architectures with partial dynamic reconfiguration," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 14, no. 11, pp. 1189 –1202, nov. 2006.
• J. Wu and T. Srikanthan, "Low-complex dynamic programming algorithm for hardware/software partitioning," Information processing letters, vol. 98, no. 2, pp. 41–46, 2006.
• C. R. REEVES (Ed. ) Modern heuristic techniques for combinatorial problems, Blackwell Scientific Publications, Oxford, 1993.
• E. H. L. AARTS, J. K. LENSTRA (Eds. ), Local search in combinatorial optimization, John Wiley & Sons, 1997.
• J. Henkel and R. Ernst, "An approach to automated hardware/ software partitioning using a flexible granularity that is driven by high-level estimation techniques," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 9, no. 2, pp. 273–289, 2001.
• P. Eles, Z. Peng, K. Kuchcinski, and A. Doboli, "System level hardware/software partitioning based on simulated annealing and tabu search," Design Automation for Embedded Systems, vol. 2, no. 1, pp. 5–32, 1997.
• R. Dick and N. Jha, "Mogac: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 10, pp. 920–935, 1998.
• G. LAPORTE, I. H. OSMAN, Metaheuristics in combinatorial optimization, Annals of Operations Research 63, J. C. Baltzer Science Publishers, Basel, Switzerland, 1996.
• I. H. OSMAN, J. P. KELLY (Eds. ), Meta-heuristics: theory and applications, Kluwers Academic Publishers, Boston, 1996.
• Holland J. H. 1975. Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor.
• Goldberg D. E. , 1987. Genetic algorithms in search, optimization, and machine learning, Addison Wesley.
• Glover F. , 1986. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, p. 533-549.
• Li-Wei Kang and Jin-Jang Leou. "An error resilient coding scheme for H. 264 video transmission based on data embedding+ ". Published in: Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on Volume 3, pp 257-260, 2004.
• Liangbao Jiao, Jing Zhou and Rui Chen. "Efficient Parallel Intra-prediction Mode Selection Scheme for 4x4 Blocks in H. 264". Published in: Intelligent Computation Technology and Automation (ICICTA). IEEE International Conference on Volume: 2, pp 527 – 530, 2011.