A modified O-Tree based packing algorithm and its applications

Author

Yan, Tan ; Li, Jing ; Yang, Bo ; Yu, Juebang

Author_Institution

Sch. of Environ. Eng., Univ. of Kitakyushu, Japan

Volume

2

fYear

2004

Firstpage

1266

Abstract

In this paper, we propose a new packing algorithm based on O-Tree representation that can reduce the time cost of turning an O-Tree into an admissible O-Tree and decoding it into a placement. By introducing a vertical contour into our algorithm, we replace the OT2OCG (O-Tree To its Orthogonal Constraint Graph) and CG2OT (Constrained Graph To O-Tree) procedures by a single OT2PL one with 50% timesaving in practical cases. Our algorithm can be applied to various problems such as placement with boundary constraint and with rectilinear blocks. A genetic algorithm is used to solve both problems and we additionally insert a block as an internal node of O-Tree without increasing the time complexity when perturbing the O-Tree. The effectiveness of our algorithm is justified by experimental results.

Keywords

VLSI; genetic algorithms; integrated circuit layout; tree data structures; O-Tree representation; OT2PL; VLSI; boundary constraint; genetic algorithm; packing algorithm; placement; rectilinear blocks; vertical contour; Algorithm design and analysis; Circuits; Cost function; Decoding; Genetic algorithms; Iterative algorithms; Space exploration; Turning; Very large scale integration; Wire;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Circuits and Systems, 2004. ICCCAS 2004. 2004 International Conference on

Print_ISBN

0-7803-8647-7

Type

conf

DOI

10.1109/ICCCAS.2004.1346404

Filename

1346404