To reduce the effect of parasitic mismatches and circuit sensitivity to thermal gradients or process variations for analog circuits, some pairs of modules need to be placed symmetrically with respect to a common axis, and the symmetric modules are preferred to be placed at closest proximity for better electrical properties. Most previous works handle the problem with symmetry constraints by imposing symmetric-feasible conditions in floorplan representations and using cost functions to minimize the distance between symmetric modules. Such approaches are inefficient due to the large search space and cannot guarantee the closest proximity of symmetry modules. In this paper, we present the first linear-time-packing algorithm for the placement with symmetry constraints using the topological floorplan representations. We first introduce the concept of a symmetry island which is formed by modules of the same symmetry group in a single connected placement. Based on this concept and the B*-tree representation, we propose automatically symmetric-feasible (ASF) B*-trees to directly model the placement of a symmetry island. We then present hierarchical B*-trees (HB*-trees) which can simultaneously optimize the placement with both symmetry islands and nonsymmetric modules. Unlike the previous works, our approach can place the symmetry modules in a symmetry group in close proximity and significantly reduce the search space based on the symmetry-island formulation. In particular, the packing time for an ASF-B*-tree or an HB*-tree is the same as that for a plain B*-tree (only linear) and much faster than previous works. Experimental results show that our approach achieves the best-published quality and runtime efficiency for analog placement.

In analog layout design, it is very important to reduce the parasitic coupling effects and improve the circuit performance. Consequently, the most important device-level placement constraints are matching, symmetry, and proximity. However, many previous works deal with these constraints separately, and none of them mention how to handle different constraints simultaneously and hierarchically. In this paper, we first give a case study to show the needs of integrating these constraints in a hierarchical manner. Then, we present the first formulation for analog placement based on hierarchical module clustering. Our approach can handle analog placement with various constraint groups including matching, (hierarchical) symmetry, and (hierarchical) proximity groups. To our best knowledge, this is also the first work in the literature to handle floorplanning with the clustering constraint using the B*-tree based representation. Experimental results based on industrial analog designs show that our approach is very effective and efficient.

We present in this paper a new interconnect-driven multilevel floorplanner, called interconnect-driven multilevel-floorplanning framework (IMF), to handle large-scale building-module designs. Unlike the traditional multilevel framework that adopts the ldquoLambda-shapedrdquo framework (inaccurately called the ldquoV-cyclerdquo framework in the literature): bottom-up coarsening followed by top-down uncoarsening, the IMF, in contrast, works in the ldquoV-shapedrdquo manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). The top-down partitioning stage iteratively partitions the floorplan region based on min-cut bipartitioning with exact net-weight modeling to reduce the number of global interconnections and, thus, the total wirelength. Then, the bottom-up merging stage iteratively applies fixed-outline floorplanning using simulated annealing for all regions and merges two neighboring regions recursively. Experimental results show that the IMF obtains the best published fixed-outline floorplanning results with the smallest average wirelength for the Microelectronics Center of North Carolina/Gigascale Systems Research Center benchmarks. In particular, IMF scales very well as the circuit size increases. The V-shaped multilevel framework outperforms the Lambda-shaped one in the optimization of global circuit effects, such as interconnection and crosstalk optimization, since the V-shaped framework considers the global configuration first and then processes down to local ones level by level, and thus, the global effects can be handled at earlier stages. The V-shaped multilevel framework is general and, thus, can be readily applied to other problems.

In this paper, we present the first amortized linear-time packing algorithm for the placement with symmetry con-straints. We first introduce the concept of a symmetry is-land which is formed by modules of the same symmetry group in a single connected placement. Based on this con-cept and the B*-tree representation, we propose automati-cally symmetric-feasible B*-trees (ASF-B*-trees) to directly model the placement of a symmetry island. Unlike the pre-vious works that can handle only 1D symmetry constraints, our ASF-B*-tree is the first in the literature to addition-ally consider 2D symmetry. We then present hierarchical B*-trees (HB*-trees) which can simultaneously optimize the placement with both symmetry islands and non-symmetry modules. Unlike the previous works, our approach can guar-antee the close proximity of symmetry modules and signifi-cantly reduce the search space based on the symmetry-island formulation. In particular, the packing time for an ASF-B*-tree or an HB*-tree is the same as that for a plain B*-tree (only amortized linear) and much faster than previous works which need at least loglinear time. Experimental results show that our approach achieves the best published quality and runtime efficiency for analog placement.

Due to its great flexibility, gridless routing is desirable for nanometer circuit designs that use variable wire widths and spacings. Nevertheless, it is much more difficult than grid-based routing because of its larger solution space. In this paper, we present a novel "V-shaped" multilevel framework (called VMF) for full-chip gridless routing. Unlike the traditional "A-shaped" multilevel framework (inaccurately called the "Vcycle" framework in the literature), our VMF works in the V-shaped manner: top-down uncoarsening followed by bottom-up coarsening. Based on the novel framework, we develop a multilevel full-chip gridless router (called VMGR) for large-scale circuit designs. The top-down uncoarsening stage of VMGR starts from the coarsest regions and then processes down to finest ones level by level; at each level, it performs global pattern routing and detailed routing for local nets and then estimate the routing resource for the next level. Then, the bottom-up coarsening stage performs global maze routing and detailed routing to reroute failed connections and refine the solution level by level from the finest level to the coarsest one. We employ a dynamic congestion map to guide the global routing at all stages and propose a new cost function for congestion control. Experimental results show that VMGR achieves the best routability among all published gridless routers based on a set of commonly used MCNC benchmarks. Besides, VMGR can obtain significantly less wire-length, smaller critical path delay, and smaller average net delay than the previous works. In particular, VMF is general and thus can readily apply to other problems.

We present in this paper, a new interconnect-driven multilevel floorplanning, called IMF, to handle large-scale building-module designs. Unlike the traditional multilevel framework that adopts the "V-cycle" framework: bottom-up coarsening followed by top-down uncoarsening, in contrast, IMF works in the "/spl Lambda/-cycle" manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). The top-down partitioning stage iteratively partitions the floorplan region based on mm-cut bipartitioning with exact net-weight modeling to reduce the number of global interconnections and thus the total wirelength. Then, the bottom-up merging stage iteratively applies fixed-outline floorplanning using simulated annealing for all regions and merges two neighboring regions recursively. We also propose an accelerative fixed-outline floorplanning (AFF) to speed up wirelength minimization under the outline constraint. Experimental results show that IMF consistently obtains the best floorplanning results with the smallest wirelength for large-scale building-module designs, compared with all publicly available floorplanners. In particular, IMF scales very well as the circuit size increases. The /spl Lambda/-cycle multilevel framework outperforms the V-cycle one in the optimization of global circuit effects, such as interconnection and crosstalk optimization, since the /spl Lambda/-cycle framework considers the global configuration first and then processes down to local ones level by level and thus the global effects can be handled at earlier stages. The /spl Lambda/-cycle multilevel framework is general and thus can be readily applied to other problems.