Towards Multi-objective Optimization of Automatic Design Space Exploration for Computer Architecture through Hyper-heuristic

M. Latif, M. A. Ismail

Abstract


Multi-objective optimization is an NP-hard problem. ADSE (automatic design space exploration) using heuristics has been proved to be an appropriate method in resolving this problem. This paper presents a hyper-heuristic technique to solve the DSE issue in computer architecture. Two algorithms are proposed. A hyper-heuristic layer has been added to the FADSE (framework for automatic design space exploration) and relevant algorithms have been implemented. The benefits of already existing multi-objective algorithms have been joined in order to strengthen the proposed algorithms. The proposed algorithms, namely RRSNS (round-robin scheduling NSGA-II and SPEA2) and RSNS (random scheduling NSGA-II and SPEA2) have been evaluated for the ADSE problem. The results have been compared with NSGA-II and SPEA2 algorithms. Results show that the proposed methodologies give competitive outcomes in comparison with NSGA-II and SPEA2.


Keywords


hyper-heuristic; multi-objective optimization; design space exploration; x86 processor

Full Text:

PDF

References


E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, J. R. Woodward, “A Classification of Hyper-Heuristic Approaches: Revisited”, in: Handbook of Metaheuristics, pp. 453-477, Springer, 2019

S. S. Choong, L. P. Wong, C. P. Lim, “Automatic design of hyper-heuristic based on reinforcement learning”, Information Sciences, Vol. 436-437, pp. 89-107, 2018

L. Vintan, R. Chis, M. A. Ismail, C. Cotofana, “Improving computing systems automatic multiobjective optimization through meta-optimization”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 35, No. 7, pp. 1125-1129, 2016

W. G. Jackson, E. Ozcan, J. H. Drake, “Late Acceptance-Based Selection Hyper-Heuristics for Cross-Domain Heuristic Search”, 13th UK Workshop on Computational Intelligence, Guildford, UK, September 9-11, 2013

J. H. Drake, E. Ozcan, E. K. Burke, “A Modified Choice Function Hyper-Heuristic Controlling Unary and Binary Operators”, IEEE Congress on Evolutionary Computation, Sendai, Japan, May 25-28, 2015

H. A. Calborean, Multi-Objective Optimization of Advanced Computer Architectures Using Domain-Knowledge, PhD Thesis, University of Sibiu, 2011

V. Zaccaria, G. Palermo, F. Castro, C. Silvano, G. Mariani, “Multicube Explorer: An Open Source Framework for Design Space Exploration of Chip Multi-Processors”, 23th International Conference on Architecture of Computing Systems 2010, Hannover, Germany, February 22-23, 2010

C. Silvano, W. Fornaciari, G. Palermo, V. Zaccaria, F. Castro, M. Martinez, S. Bocchio, R. Zafalon, P. Avasare, G. Vanmeerbeeck, C. Ykman-Couvreur, M. Wouters, C. Kavka, L. Onesti, A. Turco, U. Bondik, G. Mariani, H. Posadas, E. Villar, C. Wu, F. Dongrui, Z. Hao, T. Shibin, “Multicube: Multi-Objective Design Space Exploration of Multi-Core Architectures”, IEEE Computer Society Annual Symposium on VLSI, Kefalonia, Greece, July 5-7, 2010

Z. J. Jia, A. D. Pimentel, M. Thompson, T. Bautista, A. Nunez, “NASA: A Generic Infrastructure for System-Level MP-SoC Design Space Exploration”, 8th IEEE Workshop on Embedded Systems for Real-Time Multimedia, Scottsdale, USA, October 28-29, 2010

J. J. Durillo, A. J. Nebro, “jMetal: A java framework for multi-objective optimization”, Advances in Engineering Software, Vol. 42, No. 10, pp. 760-771, 2011

E. Zitzler, M. Laumanns, L. Thiele, SPEA2: Improving the Strength Pareto Evolutionary Algorithm, TIK-Report, Vol. 103, Swiss Federal Institute of Technology, 2001

P. Cowling, G. Kendall, E. Soubeiga, “A Hyperheuristic Approach to Scheduling a Sales Summit”, in: Lecture Notes in Computer Science, Vol. 2079, Springer, 2001

R. Bai, J. Blazewicz, E. K. Burke, G. Kendall, B. McCollum, “A simulated annealing hyper-heuristic methodology for flexible decision support”, 4OR, Vol. 10, No. 1, pp. 43-66, 2012

B. Kiraz, A. S. Etaner-Uyar, E. Ozcan, “Selection hyper-heuristics in dynamic environments”, Journal of the Operational Research Society, Vol. 64, No. 12, pp. 1753-1769, 2013

R. Chis, A. Florea, C. Buduleci, L. Vintan, “Multi-objective optimization for an enhanced multi-core SNIPER simulator”, Proceedings of the Romanian Academy-Series A, Vol. 19, No. 1, pp. 85-93, 2018

K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, pp. 182-197, 2002

A. Kheiri, E. Ozcan, “A Hyper-Heuristic with a Round Robin Neighbourhood Selection”, in: Lecture Notes in Computer Science, Vol. 7832, Springer, 2013

S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, A. Gupta, “The SPLASH-2 Programs: Characterization and Methodological Considerations”, 22nd Annual International Symposium on Computer Architecture, Santa Margherita Ligure, Italy, June 22-24, 1995

C. A. C. Coello, G. B. Lamont, D. A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, Springer, 2007

E. Zitzler, L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach”, IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, pp. 257-271, 1999




eISSN: 1792-8036     pISSN: 2241-4487