Block placement using the segment tree data structure from computational geometry

Author

Maruvada, Sarat C. ; Krishnamoorthy, Karthik ; Balasa, Florin

Author_Institution

Dept. of Comput. Sci., Illinois Univ., Chicago, IL, USA

Volume

2

fYear

2002

fDate

4-7 Aug. 2002

Abstract

Since Murata et al introduced the elegant topological representation of a block placement configuration called sequence-pair (IEEE Trans. CAD of ICs and Systems, vol. 15, no. 12, pp. 1518-1524, 1996), there has been significant research effort in the field of encoding systems for non-slicing floorplans. This paper presents a block placement technique operating on the set of binary tree representations of the layout-called B*-trees (Y.-C. Chang et al, Proc. 37th ACM/IEEE Design Automation Conf., pp. 458-463, 2000). The novelty of this approach is due to an efficient B*-tree evaluation based on a data structure called segment tree (J.L. Bentley, Res. Report, Carnegie-Mellon Univ., Pittsburgh PA, 1977), mainly used in computational geometry. Experimental results using device-level analog placement problems as benchmarks confirm the efficiency of the novel exploration approach.

Keywords

analogue circuits; circuit complexity; circuit layout CAD; computational geometry; integrated circuit layout; network topology; tree data structures; B*-tree evaluation; binary tree layout representations; block placement; computational geometry; device-level analog placement; encoding systems; nonslicing floorplans; segment tree data structure; sequence-pair block placement configuration; topological representation; Binary trees; Computational geometry; Computer science; Cost function; Encoding; Genetic algorithms; Optimization methods; Simulated annealing; Space exploration; Tree data structures;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2002. MWSCAS-2002. The 2002 45th Midwest Symposium on

Print_ISBN

0-7803-7523-8

Type

conf

DOI

10.1109/MWSCAS.2002.1186810

Filename

1186810