Using a genetic algorithm approach to reduce register file pressure during instruction scheduling
Authors:
- 1 July 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 179-187
Abstract
Instruction scheduling and register allocation for VLIW architectures are complex problems for which computing the optimal solution is often infeasible. Instead, optimization techniques and heuristics are used to find good solutions in reasonable time. List scheduling is a well known microcode compaction method, which uses weights derived from data dependency graphs of the input program in its heuristic function. Additional information and mechanisms have to be used in order to reach better code compaction. In this paper, a genetic algorithm is used to tune the heuristics during list scheduling, which allows dynamic adaption of the algorithm to the given input program. The genetic scheduler often outperforms list scheduling with static heuristic and handles situations with register file pressure that might be impossible to schedule with the heuristic based list scheduling. A second genetic algorithm is proposed to perform X2 operation merging, a code optimization step exploiting special execution mode of the target hardware architecture.Keywords
This publication has 12 references indexed in Scilit:
- A comprehensive ASIC/FPGA prototyping environment for exploring embedded processing systems for advanced driver assistance applications2014
- Instruction merging to increase parallelism in VLIW architectures2009
- Design Space Exploration of Media Processors: A Parameterized Scheduler2007
- Road-Sign Detection and Recognition Based on Support Vector MachinesIEEE Transactions on Intelligent Transportation Systems, 2007
- Genetic Instruction Scheduling and Register Allocation2005
- Optimal instruction scheduling using integer programmingACM SIGPLAN Notices, 2000
- Genetic algorithms and instruction scheduling1991
- Trace Scheduling: A Technique for Global Microcode CompactionIEEE Transactions on Computers, 1981
- Optimization of horizontal microcode within and beyond basic blocks: an application of processor scheduling with resources1979
- On storage optimization of horizontal microprograms1974