Improving data locality for compiler optimization by using hybrid genetic algorithms

Abstract

KARMA GENETİK ALGORİTMALARI KULLANARAK DERLEYİCİ ENİYİLEME İÇİN VERİ YERELLİĞİNİ İYİLEŞTİRMEK Belleğin yüksek verimle kullanılması performansa yönelik programlar için çok önemlidir. Programların çalışma performansını belirleyen en önemli faktörlerden biri verilerin yetersiz veri yerelliği nedeni ile ön bellekte bulunamamasından kaynaklanmaktadır. Döngü dönüşümleri tekniği kullanılarak ana belleğe ulaşım sırası değiştirilebilir ve yeterli veri yerelliği sağlanabilir. Bu tezde, karma genetik algorithmalar kullanılarak derleyici en iyleme için veri yerelliğini iyileştirmeye çalışılmıştır. Tezde sunulan çözümde genetik algoritmalar yerel arama teknikleri ile iyileştirilmeye çalışılmıştır. Sunulan algoritmanın performansı çok iyi bilinen derleyicilerin iyileştirmeleri ile değerlendirme deneyleri kullanılarak yapılmıştır. Bu testlerin sonuçları sunulan yöntemin derleyici iyileştirmesi yapılmadığında orjinal programlara göre başarılı olduğunu göstermiştir. Fakat derleyici iyileştirmesi yapıldığında ise %25 inde iyileştirme sağlanırken geri kalanda yaklaşık aynı derecede iyileştirme olduğunu göstermiştir. Kasım 2005 Gülşah Yılmaz

IMPROVING DATA LOCALITY for COMPILER OPTIMIZATION by USING HYBRID GENETIC ALGORITHMS The efficient use of memory is very important for performance-oriented programs. Cache misses due to inefficient data locality is one of the critical factors that determine the performance of the programs. Loop transformation techniques target to change the order of memory accesses to increase the data locality. This thesis proposes a compiler optimization framework for improving data locality by using a hybrid genetic algorithm. Local search techniques were applied at various phases of the proposed genetic algorithm to improve the quality of solutions. The performance of proposed algorithm was evaluated using well-known commercial compilers’ optimizations by using selected benchmark codes. The results indicate that the transformed codes generated by our algorithm significantly outperform the source codes of the corresponding source codes with respect to execution times. Moreover, the transformed codes give better performance than the related source codes that are compiled with compiler provided optimizations for 25% of the test cases. November 2005 Gülşah Yılmaz