Title :
On the register allocation problems and algorithms
Author :
Wang, Jhing-Fa ; Jeang, Yuan-Long ; Sheu, Ming-hwa ; Lee, Jau-Yien
Author_Institution :
Inst. of Electr. & Comput. Eng., Nat. Cheng Kung Univ., Tainan, Taiwan
Abstract :
Two new register allocation concepts are presented. One is the concept of the profit of allocation, which minimizes the number of registers and the interconnection cost simultaneously. The other is the concept of cutting lifetime segment, which reduces the number of registers to a minimum. A global register allocation optimal algorithm (GRAOA), which obtains an optimal number of registers and near-optimal interconnection cost, is presented. This algorithm takes O(TR3), where T is the number of slices and R is the minimum number of registers needed
Keywords :
VLSI; circuit CAD; shift registers; cutting lifetime segment; global register allocation optimal algorithm; interconnection cost; profit of allocation; register allocation problems; slices; Algorithm design and analysis; Cost function; Design automation; Design optimization; Integer linear programming; Minimax techniques; Minimization methods; Partitioning algorithms; Registers;
Conference_Titel :
VLSI Technology, Systems and Applications, 1989. Proceedings of Technical Papers. 1989 International Symposium on
Conference_Location :
Taipei
DOI :
10.1109/VTSA.1989.68597
