BitVertex evolutionary algorithm for accelerating graph coloring in register allocation
Kayıt tahsisinde çizge renklendirmeyi hızlandırmak için BitVertex evrimsel algoritması
- Tez No: 907306
- Danışmanlar: DR. ÖĞR. ÜYESİ ALP ARSLAN BAYRAKÇİ, DR. ÖĞR. ÜYESİ BETÜL BOZ
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Gebze Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 102
Özet
Kayıt tahsisi, derleyici tasarımında, programların yürütme hızını artırmayı amaçlayan önemli bir bileşendir; zira CPU kayıtları, bellek konumlarına kıyasla çok daha hızlı veri erişimi sağlar. Program değişkenlerinin sınırlı sayıdaki CPU kayıtlarına optimal bir şekilde atanması, pratik sürelerde verimli çözümler sunabilecek yenilikçi yaklaşımları gerektiren, bilinen NP-tam bir problemdir. Özellikle büyük ölçekli problem örnekleri söz konusu olduğunda, geleneksel yöntemler mevcut CPU mimarilerinde hesaplama açısından uygulanamaz hale gelebilmektedir. Bu tez, kayıt tahsisini hızlandırmak amacıyla bit düzeyindeki işlemler ve bit tabanlı çözümler üzerine kurulu olan BitVertex Evrimsel Algoritması'nı (BitEA) tanıtmaktadır. BitEA, verimli kodlama mekanizmalarından ve paralel işlem yeteneklerinden yararlanarak hesaplama performansını artırmak üzere tasarlanmıştır. BitEA, alana bir dizi önemli katkı sunmaktadır. İlk olarak, BitEA, algoritmaların ve problem örneklerinin bellek tüketimini azaltarak hesaplama verimliliğini artıran kompakt bir çizge kodlamasına olanak tanıyan yenilikçi bir bit tabanlı yapı olan BitVertex gösterimini kullanmaktadır. İkinci olarak, BitEA, bit düzeyindeki işlemleri iyileştirilmiş yavru üretimi ve daha az çatışma için entegre eden özel bir çaprazlama operatörü olan BitVertex Çaprazlama Operatörü (BitCX) sunmaktadır. Üçüncü olarak, çaprazlama sürecine, çatışma yaratan düğümleri akıllıca ele alarak çözümleri daha da iyileştiren Geliştirilmiş Geri Arama (ISB) operatörü eklenmiştir. Ayrıca, BitEA, düğümlerin yerleştirilmesini optimize etmek ve kromatik sayıyı en aza indirmek için tasarlanmış gelişmiş bir yerel arama stratejisini içermektedir. Önerilen BitEA çerçevesi, daha büyük çizge boyutlarına uyum sağlayarak BitVertex gösterimini genişleten ölçeklenebilir bir mimari ile desteklenmiştir. DIMACS ve InCEA kıyaslama veri kümelerinde gerçekleştirilen kapsamlı deneysel değerlendirmeler, BitEA'nın üstün performansını ortaya koymuş; mevcut algoritmalara kıyasla 60 kata kadar ortalama hesaplama hızlanması sergilediğini ve 9 DIMACS örneğinde çağdaş yöntemlere kıyasla daha düşük kromatik sayılar elde ettiğini göstermiştir. Bu tez, BitEA'yı kayıt tahsisinde tepe noktası ağırlıklı $k$-renklendirme problemini çözmek için son derece verimli bir yöntem olarak tanıtırken, detaylı analizler ve karşılaştırmalı çalışmalarla çok yönlülüğünü de vurgulamaktadır. Bulgular, BitEA'nın hesaplama verimliliği ile çözüm kalitesi arasında bir denge sağladığını ve hem sezgisel hem de evrimsel yöntemleri hız ve optimalite açısından geride bıraktığını göstermektedir. Araştırma, BitEA'nın diğer kombinatoryal optimizasyon problemlerinde potansiyel uygulamalarını ve gerçek zamanlı ve büyük ölçekli optimizasyon senaryolarında daha da geliştirilmesi için önerilerle sona ermektedir.
Özet (Çeviri)
Register allocation is an essential aspect of compiler design aimed at enhancing the execution speed of programs, as CPU registers offer significantly faster data access compared to memory locations. The challenge of optimally assigning program variables to a limited number of CPU registers is a known NP-complete problem, prompting the need for innovative approaches that can deliver efficient solutions within practical timeframes. Traditional methods often prove computationally infeasible on current CPU architectures, especially when dealing with large-scale problem instances. This thesis introduces the BitVertex Evolutionary Algorithm (BitEA), a novel approach grounded in bitwise operations and bit-based solutions, designed to accelerate computational performance in register allocation by leveraging efficient encoding mechanisms and parallel processing capabilities. BitEA introduces several key contributions to the field. First, it utilizes the BitVertex representation, an innovative bit-based structure that enables compact graph encoding, reducing memory consumption and enhancing the computational efficiency of evolutionary operations. Second, BitEA features a specialized crossover operator, the BitVertex Crossover Operator (BitCX), which integrates bitwise operations for improved offspring generation and reduced conflicts. Third, an Improved Search Back (ISB) operator is embedded within the crossover process to refine solutions further by intelligently handling conflicting vertices. Additionally, BitEA incorporates an enhanced local search strategy designed to optimize the placement of vertices and minimize the chromatic number. The proposed BitEA framework is supported by a scalable architecture that extends the BitVertex representation to accommodate graphs with significantly more vertices, ensuring adaptability for larger problem sizes. Comprehensive experimental evaluations conducted on DIMACS and InCEA benchmark datasets highlight the superior performance of BitEA, showcasing an average computational speedup of up to 60 times over existing algorithms and demonstrating lower chromatic numbers on 9 DIMACS instances compared to contemporary methods. This thesis not only introduces BitEA as a highly efficient method for solving the vertex-weighted $k$-coloring problem in register allocation but also underscores its versatility through detailed analysis and comparative studies. The findings indicate that BitEA achieves a balance between computational efficiency and solution quality, outperforming both heuristic and evolutionary methods in terms of speed and optimality. The research concludes by identifying potential applications of BitEA in other combinatorial optimization problems and suggesting future enhancements to further improve its robustness and adaptability in real-time and large-scale optimization scenarios.