Block placement using the segment tree data structure from computational geometry

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.