BitEA: BitVertex Evolutionary Algorithm to Enhance Performance for Register Allocation

Terci G. S., Abdulhalik E., Bayrakci A. A., BOZ B.

IEEE Access, cilt.12, ss.115497-115514, 2024 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 12
  • Basım Tarihi: 2024
  • Doi Numarası: 10.1109/access.2024.3446596
  • Dergi Adı: IEEE Access
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, INSPEC, Directory of Open Access Journals
  • Sayfa Sayıları: ss.115497-115514
  • Anahtar Kelimeler: BitVertex representation, bitwise operations, crossover operator, evolutionary algorithms, Evolutionary optimization, graph coloring problem, k-coloring, parallel processing, register allocation, vertex-weighted graphs
  • Marmara Üniversitesi Adresli: Evet

Özet

Register allocation is important in compiler design to enhance the execution time of programs, as CPU registers operate significantly faster than memory locations. The challenge of optimally assigning program variables to a limited number of CPU registers requires innovative solutions within constrained timeframes, particularly when traditional methods are not applicable due to computational infeasibility on current CPU architectures. This study introduces BitVertex Evolutionary Algorithm (BitEA), a novel approach grounded in bitwise operations and bit-based solutions, designed to accelerate computational performance in register allocation. Our experimental results show that BitEA outperforms the existing methods by a factor of up to 60 across all tested scenarios in the DIMACS benchmarks. Furthermore, in terms of solution quality, BitEA achieves lower chromatic numbers on 9 DIMACS benchmarks compared to its closest contemporaries. This research underscores that BitEA has potential to set a new standard for register allocation through its superior speed and solution quality.