DocumentCode :
2330357
Title :
Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design
Author :
Brisk, Philip ; Verma, Ajay K. ; Ienne, Paolo
Author_Institution :
Ecole Polytech Fed. de Lausanne, Lausanne
fYear :
2007
fDate :
4-8 Nov. 2007
Firstpage :
172
Lastpage :
179
Abstract :
Register allocation, in high-level synthesis and ASIP design, is the process of determining the number of registers to include in the resulting circuit or processor. The goal is to allocate the minimum number of registers such that no scalar variable is spilled to memory. Previously, an optimal polynomial-time algorithm for this problem has been presented for individual procedures represented in Static Single Assignment (SSA) Form. This result is now extended to complete programs (or sub-programs), as long as: (1) each procedure is represented in SSA Form; and (2) at every procedure call, all live variables are split at the call point. With this representation, it is possible to ensure that the interprocedural interference graph (IIG) is chordal, and can therefore be colored optimally in polynomial time. An optimal coloring of the IIG can be achieved by allocating registers for each procedure individually. Previous work has shown that optimal register allocation in SSA Form does not require an interference graph. Optimal interprocedural register allocation, therefore, is achieved without constructing an interference graph, giving the optimal algorithm a significant runtime advantage over prior sub-optimal heuristics.
Keywords :
graph theory; instruction sets; microprocessor chips; polynomials; ASIP design; application-specific instruction set processors; high-level synthesis; interprocedural interference graph; optimal polynomial-time interprocedural register allocation; static single assignment form; suboptimal heuristics; Application specific processors; Embedded system; Hardware; High level synthesis; Interference; Laboratories; Polynomials; Process design; Registers; Time to market;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer-Aided Design, 2007. ICCAD 2007. IEEE/ACM International Conference on
Conference_Location :
San Jose, CA
ISSN :
1092-3152
Print_ISBN :
978-1-4244-1381-2
Electronic_ISBN :
1092-3152
Type :
conf
DOI :
10.1109/ICCAD.2007.4397262
Filename :
4397262
Link To Document :
بازگشت