İsa Ahmet GÜNEY, Kemal POYRAZ, Gürhan KÜÇÜK, Ender ÖZCAN

Hyperheuristics for explicit resource partitioning in simultaneous multithreaded processors

In simultaneous multithreaded SMT processors, various data path resources are concurrently shared by many threads. A few heuristic approaches that explicitly distribute those resources among threads with the goal of improved overall performance have already been proposed. A selection hyperheuristic is a high-level search methodology that mixes a predetermined set of heuristics in an iterative framework to utilize their strengths for solving a given problem instance. In this study, we propose a set of selection hyperheuristics for selecting and executing the heuristic with the best performance at a given stage. To the best of our knowledge, this is one of the first studies implementing a hyperheuristic algorithm on hardware. The results of our experimental study show that hyperheuristics are indeed capable of improving the performance of the studied workloads. Our best performing hyperheuristic achieves better throughput than both baseline heuristics in 5 out of 12 workloads and gives about 15% peak performance gain. The average performance gains over the well-known hill-climbing and adaptive resource partitioning heuristics are about 5% and 2%, respectively.

Keywords:

Hyperheuristics, simultaneous multithreading, resource partitioning,

PDF

___

[1] Tullsen DM, Eggers SJ, Levy HM. Simultaneous multithreading: maximizing on-chip parallelism. In: 25 Years of the International Symposia on Computer Architecture (Selected Papers); Barcelona, Spain; 1998. pp. 533-544.
[2] Tullsen DM, Brown JA. Handling long-latency loads in a simultaneous multithreading processor. In: Proceedings of the 34th Annual ACM/IEEE International Symposium on Microarchitecture; Austin, TX, USA; 2001. pp. 318-327.
[3] Tullsen DM, Eggers SJ, Emer JS, Levy HM, Lo JL et al. Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor. ACM SIGARCH Computer Architecture News 1996; 24 (2): 191-202. doi: 10.1145/232974.232993
[4] Cazorla FJ, Ramirez A, Valero M, Fernandez E. Dynamically controlled resource allocation in SMT processors. In: Proceedings of the 37th Annual IEEE/ACM International Symposium on Microarchitecture; Portland, OR, USA; 2004. pp. 171-182.
[5] Choi S, Yeung D. Hill-climbing SMT processor resource distribution. ACM Transactions on Computer Systems 2009; 27 (1): 1-47. doi: 10.1145/1482619.1482620
[6] Wang H, Koren I, Krishna CM. Utilization-based resource partitioning for power-performance efficiency in SMT processors. IEEE Transactions on Parallel and Distributed Systems 2011; 22 (7): 1150-1163. doi: 10.1109/TPDS.2010.199
[7] Burke EK, Gendreau M, Hyde M, Kendall G, Ochoa G et al. Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society 2013; 64 (12): 1695-1724. doi: 10.1057/jors.2013.71
[8] Kiraz B, Etaner-Uyar AS, Özcan E. Selection hyper-heuristics in dynamic environments. Journal of the Operational Research Society 2013; 64 (12): 1753-1769. doi: 10.1057/jors.2013.24
[9] Uludağ G, Kiraz B, Etaner-Uyar AS, Özcan E. A hybrid multi-population framework for dynamic environments combining online and offline learning. Soft Computing 2013; 17 (12): 2327-2348. doi: 10.1007/s00500-013-1094-7
[10] Eyerman S, Eeckhout L. Memory-level parallelism aware fetch policies for simultaneous multithreading processors. ACM Transactions on Architecture and Code Optimization 2009; 6 (1): 1-33. doi: 10.1145/1509864.1509867
[11] Vandierendonck H, Seznec A. Managing SMT resource usage through speculative instruction window weighting. ACM Transactions on Architecture and Code Optimization 2011; 8 (3): 1-20. doi: 10.1145/2019608.2019611
[12] Eyerman S, Eeckhout L. Per-thread cycle accounting in SMT processors. ACM SIGPLAN Notices 2009; 44 (3): 133-144. doi: 10.1145/1508284.1508260
[13] Weng L, Liu C. A resource utilization based instruction fetch policy for SMT processors. Microprocessors and Microsystems 2015; 39 (1): 1-10. doi: 10.1016/j.micpro.2014.10.001
[14] Zhang Y, Hays M, Lin WM, John E. Autonomous control of issue queue utilization for simultaneous multi-threading processors. In: Proceedings of the High Performance Computing Symposium; Tampa, FL, USA; 2014. pp. 1-8.
[15] Zhang Y, Lin WM. Efficient resource sharing algorithm for physical register file in simultaneous multi-threading processors. Microprocessors and Microsystems 2016; 45 (PB): 270-282. doi: 10.1016/j.micpro.2016.06.002
[16] Güngörer H, Küçük G. Dynamic capping of physical register files in simultaneous multi-threading processors for performance. In: 32nd International Symposium (ISCIS 2018); Poznan, Poland; 2018. pp. 41-48.
[17] Sheikh MN, Lin WM. Dynamic capping of rename registers for SMT processors. Journal of Systems Architecture 2019; 99: 1-20. doi: 10.1016/j.sysarc.2019.101637
[18] Fisher H, Thompson GL. Probabilistic learning combinations of local job-shop scheduling rules. In: Muth JF, Thompson GL (editors). Industrial Scheduling. Hoboken, NJ, USA: Prentice Hall, 1963, pp. 225-251.
[19] Burke EK, Hyde M, Kendall G, Ochoa G, Özcan E et al. A classification of hyper-heuristics approaches. In: Gendreau M, Potvin JY (editors). Handbook of Metaheuristics. New York, NY, USA: Springer, 2010, pp. 449-468.
[20] Özcan E, Bilgin B, Korkmaz E. A comprehensive analysis of hyper-heuristics. Intelligent Data Analysis 2008; 12 (1): 3-23. doi: 10.3233/ida-2008-12102
[21] Cowling P, Kendall G, Soubeiga E. A hyperheuristic approach to scheduling a sales summit. In: Burke E, Erben W (editors). Practice and Theory of Automated Timetabling III. Berlin, Germany: Springer, 2001, pp. 176-190.
[22] Nareyek A. Choosing search heuristics by non-stationary reinforcement learning. In: Resende MGC, de Sousa JP (editors). Metaheuristics: Computer Decision-Making. New York, NY, USA: Springer, 2003, pp. 523-544.
[23] Özcan E, Mısır M, Ochoa G, Burke EK. A reinforcement learning - great-deluge hyper-heuristic for examination timetabling. International Journal of Applied Metaheuristic Computing 2010; 1 (1): 39-59. doi: 10.4018/jamc.2010102603
[24] Bai R, Blazewicz J, Burke EK, Kendall G, McCollum B. A simulated annealing hyper-heuristic methodology for flexible decision support. 4OR 2012; 10 (1): 43-66. doi: 10.1007/s10288-011-0182-8
[25] Lehre PK, Özcan E. A runtime analysis of simple hyper-heuristics: to mix or not to mix operators. In: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII; Adelaide, Australia; 2013. pp. 97-104.
[26] Kheiri A, Özcan E. An iterated multi-stage selection hyper-heuristic. European Journal of Operational Research 2016; 250 (1): 77-90. doi: 10.1016/j.ejor.2015.09.003
[27] Shahriar A, Karapetyan D, Kheiri A, Özcan E, Parkes AJ. Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. Information Sciences 2016; 373: 476-498. doi: 10.1016/j.ins.2016.09.010
[28] Cowling P, Kendall G, Soubeiga E. Hyperheuristics: a tool for rapid prototyping in scheduling and optimisation. In: Applications of Evolutionary Computing: Proceedings of Evo Workshops 2002; Kinsale, Ireland; 2002. pp. 269-287.
[29] Ross P. Hyper-heuristic. In: Burke EK, Kendall G (editors). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. New York, NY, USA: Springer, 2005, pp. 529-556.
[30] Prakash TK, Peng L. Performance characterization of SPEC CPU2006 benchmarks on Intel Core 2 Duo processor. ISAST Transactions on Computers and Software Engineering 2008; 2 (2): 36-41. doi: 10.1109/TPDS.2010.199

Turkish Journal of Electrical Engineering and Computer Science-Cover

ISSN: 1300-0632
Yayın Aralığı: Yılda 6 Sayı
Yayıncı: TÜBİTAK

Arşiv