Towards Multi-objective Optimization of Automatic Design Space Exploration for Computer Architecture through Hyper-heuristic
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 processorDownloads
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 DOI: https://doi.org/10.1007/978-3-319-91086-4_14
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 DOI: https://doi.org/10.1016/j.ins.2018.01.005
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 DOI: https://doi.org/10.1109/TCAD.2015.2501299
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 DOI: https://doi.org/10.1109/UKCI.2013.6651310
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 DOI: https://doi.org/10.1109/CEC.2015.7257315
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 DOI: https://doi.org/10.1109/ISVLSI.2010.67
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 DOI: https://doi.org/10.1109/ESTMED.2010.5666979
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 DOI: https://doi.org/10.1016/j.advengsoft.2011.05.014
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 DOI: https://doi.org/10.1007/3-540-44629-X_11
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 DOI: https://doi.org/10.1007/s10288-011-0182-8
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 DOI: https://doi.org/10.1057/jors.2013.24
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 DOI: https://doi.org/10.1109/4235.996017
A. Kheiri, E. Ozcan, “A Hyper-Heuristic with a Round Robin Neighbourhood Selection”, in: Lecture Notes in Computer Science, Vol. 7832, Springer, 2013 DOI: https://doi.org/10.1007/978-3-642-37198-1_1
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 DOI: https://doi.org/10.1145/223982.223990
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 DOI: https://doi.org/10.1109/4235.797969
Downloads
How to Cite
License
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the 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) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
