Hyper-heuristics for performance optimization of simultaneous multithreaded processors

Abstract

Eşzamanlı Çoklu İşparçacıklı işlemcilerin veri yollarında birçok kaynak eş zamanlı olarak birden çok iş parçacığı tarafından paylaşılmaktadır. Literatürde, performansı artırmak amacıyla bu kaynakları iş parçacıkları arasında doğrudan bölüştüren sezgisel yaklaşımlar mevcuttur. Seçici-üst-sezgiseller, önceden belirlenmiş bir sezgisel kümesinden sezgiselleri seçerek bir problemin çözümünde bu sezgisellerin avantajlarından faydalanan bir metottur. Bu çalışmada, çağ olarak adlandırdığımız periyodik zaman aralıklarında en iyi çalışan sezgiseli tahmin etmek ve seçmek için bir grup öğrenme tabanlı üst sezgisel sunuyoruz. Deneysel sonuçlar üst sezgisellerin test edilen iş yüklerinin performansını artırma potansiyeline sahip olduğunu göstermektedir. Çalışmamızda gözlemlenen en yüksek performans kazançları, literatürde sunulmuş olan Hill Climbing sezgiseli için yaklaşık yüzde 25, Adaptive Resource Partitioning Algorithm sezgiseli için ise yaklaşık yüzde 11'dir. En iyi üst sezgiselimiz olan HH4, literatürdeki en başarılı sezgisellerden en az birinde, test edilen iş yüklerinin yaklaşık yüzde 72'sinde daha iyi sonuç vermektedir. En iyi üst-sezgiselimiz olan HH4 aynı zamanda test edilen iş yüklerinin yaklaşık yüzde 30'unda ise her iki sezgiselden de daha yüksek performans göstermektedir.

In Simultaneous Multi-Threaded processor datapaths, there are many resources that are concurrently shared by multiple threads. A few number of heuristic approaches, which explicitly distribute those resources among threads with the goal of an improved overall performance, have been proposed. A selection hyper-heuristic is a high level search methodology which mixes a predetermined set of heuristics under an iterative framework to exploit their strengths while solving a given problem. In this study, we propose a set of learning selection hyper-heuristics for predicting, choosing and running the best performing heuristic at periodic time intervals that we name epochs. The empirical results show that hyper-heuristics are capable of improving the performance of the studied workloads. The peak performance improvement is observed to be around 25 per cent over a previously proposed Hill Climbing heuristic and around 11 per cent over Adaptive Resource Partitioning Algorithm. Our best hyper-heuristic, HH4, performs better than either of the state-of-the art heuristics on almost 72 per cent of the simulated workloads. HH4 also beats both of the heuristics on around 30 per cent of the simulated workloads.