Evolutionary Algorithms for Instruction Scheduling, Operation Merging, and Register Allocation in VLIW Compilers

verfasst von: F. Giesemann, L. Gerlach, G. Payá-Vayá
Abstract: Code generation for VLIW processors includes several optimization problems like code optimization, instruction scheduling, and register allocation. The high complexity of these problems usually does not allow the computation of the optimal solution. Instead, optimization techniques, e.g., based on heuristics, are used to find acceptable solutions in a reasonable time. List scheduling is a well known heuristic-based microcode compaction method, that bases its scheduling decisions on weights derived from dependency analysis of the input program. Additional information and methods have to be used in order to reach better code compaction. Also, more sophisticated code optimization and register allocation support better code compaction. In this paper, evolutionary algorithms are used as dynamic heuristics in code generation, which allows dynamic adaption to the given input program and target processor configuration. Three evolutionary algorithms for operation merging, instruction scheduling, and register allocation are presented and evaluated on an exemplary image processing application, which shows different processing characteristics in the subroutines. They outperform code generation based on static heuristics and allow compilation for restricted target architectures that cannot be handled by the static heuristics.
Organisationseinheit(en): Fachgebiet Architekturen und Systeme
Typ: Artikel
Journal: Journal of Signal Processing Systems
Band: 92
Seiten: 655-678
Anzahl der Seiten: 24
ISSN: 1939-8018
Publikationsdatum: 07.2020
Publikationsstatus: Veröffentlicht
Peer-reviewed: Ja
ASJC Scopus Sachgebiete: Steuerungs- und Systemtechnik, Theoretische Informatik, Signalverarbeitung, Information systems, Modellierung und Simulation, Hardware und Architektur
Elektronische Version(en): https://doi.org/10.1007/s11265-019-01493-2 (Zugang: Geschlossen)