Title :
Optimal tile partition for space region of integrated circuits geometry
Author :
Hsiao, P.-Y. ; Lin, C.-Y. ; Shew, P.W.
Author_Institution :
Dept. of Comput. & Inf. Sci., Nat. Chaio Tung Univ., Hsinchu, Taiwan
fDate :
5/1/1993 12:00:00 AM
Abstract :
An optimal tile partition (OTP) is presented for partitioning the space region of a VLSI layout plane into rectangular space tiles. It modifies the corner stitching data structure to optimise the space tile partition. There is a serious restriction in the original corner stitching data structure, i.e. the solid rectangles cannot overlap each other, whereas the authors OTP allows overlapping. This paper also shows three theorems with rigorous proofs and experimental results to obtain the minimal number of the space tiles through the OTP. Moreover, a dynamic plane-sweep algorithm based on region query for the OTP has been developed. Using the OTP, the memory efficiency and the local query operations of the original corner stitching data structure have been enhanced.
Keywords :
VLSI; circuit layout CAD; data structures; VLSI; corner stitching data structure; integrated circuits geometry; local query operations; optimal tile partition; region query; solid rectangles; space region;
Journal_Title :
Computers and Digital Techniques, IEE Proceedings E