Details
| Original language | English |
|---|---|
| Pages (from-to) | 655-678 |
| Number of pages | 24 |
| Journal | Journal of Signal Processing Systems |
| Volume | 92 |
| Issue number | 7 |
| Early online date | 17 Jan 2020 |
| Publication status | Published - Jul 2020 |
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.
Keywords
- Evolutionary algorithm, Instruction scheduling, Operation merging, Register allocation, VLIW
ASJC Scopus subject areas
- Engineering(all)
- Control and Systems Engineering
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- Signal Processing
- Computer Science(all)
- Information Systems
- Mathematics(all)
- Modelling and Simulation
- Computer Science(all)
- Hardware and Architecture
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Journal of Signal Processing Systems, Vol. 92, No. 7, 07.2020, p. 655-678.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Evolutionary Algorithms for Instruction Scheduling, Operation Merging, and Register Allocation in VLIW Compilers
AU - Giesemann, F.
AU - Gerlach, L.
AU - Payá-Vayá, G.
N1 - Funding information: This work was partly funded by the German Research Council (DFG) under project number PA 2762/2-1. This work was partly funded by the German Research Council (DFG) under project number PA 2762/2-1.
PY - 2020/7
Y1 - 2020/7
N2 - 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.
AB - 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.
KW - Evolutionary algorithm
KW - Instruction scheduling
KW - Operation merging
KW - Register allocation
KW - VLIW
UR - http://www.scopus.com/inward/record.url?scp=85078307564&partnerID=8YFLogxK
U2 - 10.1007/s11265-019-01493-2
DO - 10.1007/s11265-019-01493-2
M3 - Article
VL - 92
SP - 655
EP - 678
JO - Journal of Signal Processing Systems
JF - Journal of Signal Processing Systems
SN - 1939-8018
IS - 7
ER -