Placement is one of the most important steps in the RTL-to-GDSII synthesis process as it directly defines the interconnects. The rapid increase in IC design complexity and the widespread use of intellectual-property blocks have made the so-called mixed-size placement a very important topic in recent years. The contributions of this paper include the following: 1) It proposes a flexible and robust mixed-size legalization scheme. Two constraint graphs are constructed from the global placement. Adjustments are iteratively applied to the constraint graphs until the longest paths on both graphs fall within the chip dimension. The macro coordinates are then computed by solving a linear programming (LP) formulation. The LP formulation has also been extended to handle macro spreading for routing density control. Experimental results show that our scheme can effectively legalize macros for all the global placements generated by mPL6 [1] on IBM-MSwPins. Experimental results also show that LP-based macro assignment can significantly reduce the amount of perturbation introduced during legalization compared to a greedy alternative. 2) Starting from the legalization scheme, it further proposes a three-step mixed-size detailed placement algorithm, XDP. An enhanced greedy method is used to remove the overlap between standard cells while preserving the legality of macros. Sliding-window-based cell swapping is applied in the end to further reduce the wirelength. Experiments show that, when compared with Floorist [2] with similar legalization capability, using the global placements generated by mPL6 [3], XDP is seven times faster with 6% shorter wirelength. Experiments also show that, when applied to the set of global placement results generated by APlace 2.0 [4], XDP can produce comparable wirelength to the native detailed placement of APlace 2.0 and 2% shorter wirelength compared with that with Fengshui 5.0 [5]. When applied to the set of global placements generated by mPL6, XDP is the only detailed placement that successfully produces legal placements for all 18 examples, whereas APlace and Fengshui failed for 3 and 16 of them, respectively. Furthermore, when legal placements can be compared, the wirelength produced by XDP is shorter by 8% on average compared with that with APlace. For scalability, XDP is ten times faster than APlace when applied to circuits with more than two million movable objects with comparable wirelength.

We present a two-stage congestion-driven placement flow. First, during each refinement stage of our multilevel global placement framework, we replace cells based on the wirelength weighted by congestion level to reduce the routing demands of congested regions. Second, after the global placement stage, we allocate appropriate amounts of white space into different regions of the chip according to a congestion map by shifting cut lines in a top-down fashion and apply a detailed placer to legalize the placement and further reduce the half-perimeter wirelength while preserving the distribution of white space. Experimental results show that our placement flow can achieve the best routability with the shortest routed wirelength among publicly available placement tools on IBM v2 benchmarks. Our placer obtains 100% successful routings on 16 IBM v2 benchmarks with shorter routed wirelengths by 3.1% to 24.5% compared to other placement tools. Moreover, our white space allocation approach can significantly improve the routability of placements generated by other placement tools.

The rapid increase in IC design complexity and wide-spread use of intellectual-property (IP) blocks have made the so-called mixed-size placement a very important topic in recent years. Although several algorithms have been proposed for mixed-sized placements, most of them primarily focus on the global placement aspect. In this paper we propose a three-step approach, named XDP, for mixed-size detailed placement. First, a combination of constraint graph and linear programming is used to legalize macros. Then, an enhanced greedy method is used to legalize the standard cells. Finally, a sliding-window-based cell swapping is applied to further reduce wirelength. The impact of individual techniques is analyzed and quantified. Experiments show that when applied to the set of global placement results generated by APlace (Kahng and Wang, 2004), XDP can produce wirelength comparable to the native detailed placement of APlace, and 3% shorter wire-length compared to Fengshui 5.0 (Agnitori et al., 2005). When applied to the set of global placements generated by mPL6 (Chan et al., 2005), XDP is the only detailed placement that successfully produces legal placement for all the examples, while APlace and Fengshui fail for 4/9 and 1/3 of the examples. For cases where legal placements can be compared, the wirelength produced by XDP is shorter by 3% on average compared to APlace and Fengshui. Furthermore, XDP displays a higher robustness than the other tools by covering a broader spectrum of examples by different global placement tools.

The multilevel placement package mPL6 combines improved implementations of the global placer mPL5 (ISPD05) and the XDP legalizer and detailed placer (ASPDAC06). It consistently produces robust, high-quality solutions to difficult instances of mixed-size placement in fast and scalable run time. Best-choice clustering (ISPD05) is used to construct a hierarchy of problem formulations. Generalized force-directed placement guides global placement at each level of the cluster hierarchy. During the declustering pass from coarsest to finest level, large movable objects are gradually fixed in positions without overlapping with one another. This progressive legalization of large objects during continuous optimization supports determination of a completely overlap-free configuration as close as possible to the continuous solution. Various discrete heuristics are applied to this legalized placement in order to improve the final wirelength.

The most recent version of the mPL multilevel placement algorithm, mPL6, is reviewed. This version is derived from the mPL5 placer (ISPD05) and the Patoma floorplanner (ASPDAC05). It is also augmented by new techniques for detailed placement. As a result, it can handle mixed-size placement very effectively. First-choice clustering is used to construct a hierarchy of problem formulations. Generalized force-directed placement guides global placement at each level of the cluster hierarchy. Prior to interpolation of each coarse-level solution to its adjacent finer level, however, recursive, top-down displacement-minimizing floorplanning optimizes block orientations and checks that overlap can be removed at the current level. Where necessary, the floor-planner perturbs coarse-level solutions enough that legalization of the given placement can be assured. The resulting flow is scalable and robust, and it produces very low-wirelength solutions for known benchmark circuits.

This paper presents MARS, a novel multilevel full-chip gridless routing system. The multilevel framework with recursive coarsening and refinement allows for scaling of our gridless routing system to very large designs. The downward pass of recursive coarsening builds the representations of routing regions at different levels while the upward pass of iterative refinement allows a gradually improved solution. We introduced a number of efficient techniques in the multilevel routing scheme, including resource reservation, graph-based Steiner tree heuristic and history-based iterative refinement. We compared our multilevel framework with a recently published three-level routing flow . Experimental results show that MARS helps to improve the completion rate by over 10%, and the runtime by 11.7/spl times/.

Placement is one of the most important steps in the RTL-to-GDSII synthesis process, as it directly defines the interconnects, which have become the bottleneck in circuit and system performance in deep submicron technologies. The placement problem has been studied extensively in the past 30 years. However, recent studies show that existing placement solutions are surprisingly far from optimal. The first part of this tutorial summarizes results from recent optimality and scalability studies of existing placement tools. These studies show that the results of leading placement tools from both industry and academia may be up to 50% to 150% away from optimal in total wirelength. If such a gap can be closed, the corresponding performance improvement will be equivalent to several technology-generation advancements. The second part of the tutorial highlights the recent progress on large-scale circuit placement, including techniques for wirelength minimization, routability optimization, and performance optimization.

We present a congestion-driven placement flow. First, we consider in the global placement stage the routing demand to replace cells in order to avoid congested regions. Then we allocate appropriate amounts of white space into different regions of the chip according to the congestion map. Finally, a detailed placer is applied to legalize placements while preserving the distributions of white space. Experimental results show that our placement flow can achieve the best routability with the shortest routed wirelength among all publicly available placement tools. Moreover, our white space allocation approach can significantly improve the routabilities of placements generated by other placement tools.

Placement is an important step in the overall IC design process in deep submicron technologies, as it defines the on-chip interconnects which have become the bottleneck in determining circuit performance. The rapidly increasing design complexity, combined with the demand for the capability of handling nearly flattened designs for physical hierarchy generation, poses significant challenges to existing placement algorithms. There are very few studies dedicated to understanding the optimality (i.e., the comparison of the solution of an algorithm to the optimal solution) and scalability (i.e., the analysis of the degradation of the performance of an algorithm as the input size of the problem increases) of placement algorithms, due to the limited sizes of existing benchmarks and limited knowledge of optimal solutions. The contribution of this work includes three parts. 1) We implemented an algorithm [Placement Examples with Known Optimal (PEKO) algorithm] for generating synthetic benchmarks that have known optimal wirelengths and can match any given net degree distribution profile. 2) Using benchmarks of 10 k to 2 M placeable modules with known optimal solutions, we studied the optimality and scalability of four state-of-the-art placers, Dragon (Wang et al., 2000), Capo (Caldwell et al., 2000), mPL (Chan et al., 2000), and mPG (Chang et al., 2002) from academia, and a leading edge industrial placer, QPlace (Cadence 1999) from Cadence. For the first time our study reveals the gap between the results produced by these tools versus true optimal solutions. The wirelengths produced by these tools are 1.59 to 2.40 times the optimal in the worst cases, and are 1.43 to 2.12 times the optimal on average. As for scalability, the average solution quality of each tool deteriorates by an additional 9% to 17% when the problem size increases by a factor of ten. These results indicate significant room for improvement in existing placement algorithms. 3) We studied the impact of nonlocal nets on the quality of the placers by extending the PEKO algorithm (PEKU algorithm) to generate synthetic placement benchmarks with a known upper bound of the optimal wirelength. For these benchmarks, the wirelengths produced by these tools are 1.75 to 2.18 times the wirelength upper bound in the worst case, and are 1.62 to 2.07 times the wirelength upper bound on average. Moreover, in our study we found that the effectiveness of the algorithms varies for circuits with different characteristics.

Placement is an important step in the overall IC design process in DSM technologies, as it defines the on-chip interconnects, which have become the bottleneck in determining circuit performance. The rapidly increasing design complexity, combined with the demand for the capability of handling nearly flattened designs for physical hierarchy generation, poses significant challenges to existing placement algorithms. There are very few studies on understanding the optimality and scalability of placement algorithms, due to the limited sizes of existing benchmarks and limited knowledge of optimal solutions. The contribution of this paper includes two parts: 1) We implemented an algorithm for generating synthetic benchmarks that have known optimal wirelengths and can match any given net distribution vector. 2) Using benchmarks of 10K to 2M placeable modules with known optimal solutions, we studied the optimality and scalability of three state-of-the-art placers, Dragon [4], Capo [1], mPL [24] from academia, and one leading edge industrial placer, QPlace [5] from Cadence. For the first time our study reveals the gap between the results produced by these tools versus true optimal solutions. The wirelengths produced by these tools are 1.66 to 2.53 times the optimal in the worst cases, and are 1.46 to 2.38 times the optimal on the average. As for scalability, the average solution quality of each tool deteriorates by an additional 4% to 25% when the problem size increases by a factor of 10. These results indicate significant room for improvement in existing placement algorithms.

state-of-the-art partitioning and placement algorithms. We present algorithms to construct two classes of benchmarks, one for partitioning and the other for placement, which have known upper bounds of their optimal solutions, and can match any given net distribution vector. Using these partitioning and placement benchmarks, we studied the optimality of state-ofthe -art algorithms by comparing their solutions with the upper bounds of the optimal solutions, and their scalability and stability by varying the sizes and characteristics of the benchmarks. The conclusions from this study are: 1) State-ofthe -art, multilevel two way partitioning algorithms scale very well and are able to find solutions very close to the upper bounds of the optimal solutions of our benchmarks. This suggests that existing circuit partitioning techniques are fairly mature. There is not much room for improvement for cutsize minimization for problems of the current sizes. Multiway partitioning algorithms, on the other hand, do not perform that well. Their results can be up to 18% worse than our estimated upper bounds. 2) The state-of-the-art placement algorithms produce significantly inferior results compared with the estimated optimal solutions. There is still significant room for improvement in circuit placement. 3) Existing placement algorithms are not stable. Their effectiveness varies considerably depending on the characteristics of the benchmarks. New hybrid techniques are probably needed for future generation placement engines that are more scalable and stable.

In this paper, we present several novel techniques that make the recently published multilevel routing scheme [19] more effective and complete. Our contributions include: (1) resource reservation for local nets during the coarsening process, (2) congestion-driven, graph-based Steiner tree construction during the initial routing and the refinement process and (3) multi-iteration refinement considering the congestion history. The experiments show that each of these techniques helps to improve the completion rate considerately. Compared to [19], the new routing system reduces the number of failed nets by 2× to 18×, with less than 50% increase in runtime in most cases.