Hybrid evolutionary algorithms for solving the register allocation problem


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Institute for Graduate Studies in Pure and Applied Sciences, Turkey

Approval Date: 2004

Thesis Language: English

Student: BETÜL DEMİRÖZ

Supervisor: Haluk Rahmi Topcuoğlu

Abstract:

YAZMAÇ ÖZGÜLEME PROBLEMİ İÇİN EVRİMSEL KARMA ALGORİTMALAR İçine gömülmüş sistemler, güç ve bellek alanı gibi kısıtlamalarda uygulama programcılarına eşsiz bir kolaylık sağlamaktadır. Bu özellikler isteğe uygun derleyici tasarımını zorunlu kılmaktadır. Gömülü kodların çalışma performansını belirleyen en önemli faktörlerden biri derleyicinin yazmaç özgüleme safhasıdır. Değişkenleri yazmaçlara atmada (ör: belli sayıdaki değişkenlerin, kısıtlı sayıdaki yazmaçlara atılması) iyi bir yazmaç özgüleme kullanılmazsa, ciddi güç, performans ve kod büyüklüğü problemleri yaşanır. Bu tezde, yazmaç problemini çözebilmek için evrimsel karma algoritmalar kullanılmıştır. Tezde sunulan çözüm genetik algoritmaları yerel arama teknikleri ile birleştirmektedir. Sunulan algoritma, pek çok özelliğe sahip ve etki alanını da göz önünde bulunduran bir çaprazlama işleci sunmaktadır. Problemimizi gerçekleştirmemize bağlı olan sonuçlar iki farklı deneme çizgeleri kullanarak gerçekleştirilmiştir. Bunlardan ilki sentetik karşılaştırmalı değerlendirme deneyi kullanılarak, diğeri ise çok iyi bilinen karşılaştırmalı değerlendirme deneyleri kullanılarak yapılmıştır ve bu testlerin sonuçları sunulan yöntemin değişkenleri yazmaçlara özgülemede başarılı olduğunu göstermiştir. Aynı zamanda bu sonuçlar çizge boyama probleminin üzerine bina edilmiş, pek çok deneyde kullanılan buluşsal yazmaç özgülemesinden daha iyi sonuçlar vermektedir. Anahtar Kelimeler: Evrimsel algoritmalar, melezleştirme, çaprazlama, yazmaç özgüleme Haziran 2004 Betül Demiröz ABSTRACT HYBRID EVOLUTIONARY ALGORITHMS FOR THE REGISTER ALLOCATION PROBLEM Embedded systems are unique in challenges they present to application programmers, such as power and memory space constraints. These characteristics make it imperative to design customized compiler passes. One of the important factors that shape runtime performance of a given embedded code is the register allocation phase of compilation. Failing to do good job on allocating variables to registers (i.e., determining the set of variables to be stored in the limited number of registers) can have serious power, performance, and code size consequences. This thesis explores the possibility of employing a hybrid evolutionary algorithm for register allocation problem. The proposed solution combines genetic algorithms with a local search technique. The algorithm exploits a novel, highly-specialized crossover operator that takes into account domain-specific information. The results from our implementation based on synthetic benchmarks and routines that are extracted from well-known benchmark suites clearly show that the proposed approach is very successful in allocating registers to variables. In addition, our experimental evaluation also indicates that it outperforms a state-of-the-art register allocation heuristic based on graph coloring for most of the cases experimented. Keywords: Evolutionary algorithms, hybridization, crossover, register allocation. June 2004 Betül Demiröz