The ISPD~2015 placement-contest benchmarks include all the detailed pin, cell, and wire geometry constraints from the 2014 release, plus

Wirelength is one of the most important metrics in the placement problem. Minimizing wirelength is not only beneficial, but also a fundamental step to optimize other metrics, such as timing, power, and routability. In this paper, we propose a high performance mixed-size wirelengh-driven placer called POLAR. POLAR is based on the recent popular look-ahead legalization idea. The goals of our look-ahead legalization are: 1) to achieve a roughly legalized placement and 2) to maintain cells' relative positions of quadratic placement while minimizing cell movements. To achieve these goals, in POLAR, look-ahead legalization is realized in a simple and elegant manner. Firstly, all placement density hotspots (where placement overflow occurs) are detected. Secondly, for each hotspot, an appropriate window is searched to cover it by enumerating many feasible candidates. Finally, cell-to-bin assignment is performed within each window by a fast recursive bisection method. The experimental results verify the efficiency of POLAR over the ISPD 2005 and 2006 benchmarks.

The public release of realistic industrial placement benchmarks by IBM and Intel Corporations from 1998--2013 has been crucial to the progress in physical-design algorithms during those years. Direct comparisons of academic tools on these test cases, including widely publicized contests, have spurred researchers to discover faster, more scalable algorithms with significantly improved quality of results.

A new quadratic global placer called POLAR is proposed. POLAR is based on novel techniques for rough legalization and wirelength refinement. During look-ahead rough legalization (LAL), relative positions of cells are maintained as they are relocated with minimal displacement to relieve excess area density. For each “hotspot” where placement overfill occurs, an expansion region covering the hotspot is constructed. Then the movable cells within each of these expansion regions are evenly assigned to density bins inside the expansion region by displacement-minimizing recursive bisection. In addition, a fast density-preserving and wirelength-reducing discrete refinement is applied to the first few LAL placements before each of these is used to augment the quadratic model used to obtain the next major placement iteration. The experimental results show that POLAR outperforms the state-of-the-art academic placers over the ISPD 2005 benchmarks.

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.

A new paradigm is introduced for floorplanning any combination of fixed-shape and variable-shape blocks under tight fixed-outline area constraints and a wirelength objective. Dramatic improvement over traditional floorplanning methods is achieved by the explicit construction of strictly legal layouts for every partition block at every level of a cutsize-driven top-down hierarchy. By scalably incorporating legalization into the hierarchical flow, post hoc legalization is successfully eliminated. For large floorplanning benchmarks, an implementation, called partitioning to optimize module arrangement (PATOMA), generates solutions with half the wirelength of state-of-the-art floorplanners in orders of magnitude less run time. Experiments on standard Gigascale Systems Research Center benchmarks compare PATOMA to the Capo macro placer, the Traffic floorplanner, and to both the default and high-effort modes of the Parquet 4.0 floorplanner. With all blocks hard, PATOMA's average wirelength is comparable to the high-effort mode of Parquet 4.0 floorplanner and Capo, while PATOMA runs significantly faster. With all blocks soft, PATOMA produces wirelength 9% shorter on average than that of Parquet's default mode, and PATOMA runs seven times faster. For a new set of benchmarks with a mix of 500 to 2000 hard and soft blocks, PATOMA produces results with wirelengths roughly half of Parquet's, with a speedup of almost 200times

A new paradigm is introduced for floorplanning any combination of fixed-shape and variable-shape blocks under tight fixed-outline area constraints and a wirelength objective. Dramatic improvement over traditional floorplanning methods is achieved by explicit construction of strictly legal layouts for every partition block at every level of a cutsize-driven, top-down hierarchy. By scalably incorporating legalization into the hierarchical flow, post-hoc legalization is successfully eliminated. For large floorplanning benchmarks, an implementation, called PATOMA, generates solutions with half the wirelength of state-of-the-art floorplanners in orders of magnitude less run time.

A novel and very simple correct-by-construction top-down methodology for high-utilization mixed-size placement is presented. The Polarbear algorithm combines recursive cut-size-driven partitioning with fast and scalable legalization of every placement subproblem generated by every partitioning. The feedback provided by the legalizer at all stages of partitioning improves final placement quality significantly on standard IBM benchmarks and dramatically on low-white-space adaptations of them. Compared to Feng Shui 5.1 and Capo 9.3, Polarbear is the only tool that can consistently find high-quality placements for benchmarks with less than 5% white space. With white space at 5%, Polarbear beats Capo 9.3 by 10% in average total wirelength while Feng Shui 5.1 frequently fails to find legal placements altogether. With 20% white space, POLARBEAR still beats Capo 9.3 by 1% and Feng Shui 5.1 by 1% in average total wirelength, in comparable run times.

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.

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.

A novel algorithm for rectangular floorplanning with guaranteed 100% area utilization is used to construct new sets of floorplanning benchmarks. By minimizing the maximum block aspect ratio subject to a zero-dead-space constraint, example zero-dead-space (ZDS) floorplans matching the area profiles of any existing floorplanning benchmark circuits can be constructed. A mathematical analysis shows that the aspect ratios of the ZDS benchmarks' blocks are uniformly bounded within [1, 3] in most cases. Block packings produced by the Parquet, B*-tree, TCG-S, and BloBB packages on these new benchmarks are compared to the optimal-area floorplans produced by the ZDS algorithm.

We have designed and implemented a new class of fast and highly scalable placement algorithms that directly handle complex constraints and achieve total wirelengths comparable to the state of the art. Our approach exploits recent advances in (i) multilevel methods for hierarchical computation, (ii) interior-point methods for nonconvex nonlinear programming, and (iii) the Fast Multipole Method for the order N evaluation of sums over the N(N-1)/2 pairwise interactions of N components. Significant adaptation of these methods for the placement problem is required, and we have therefore developed a set of customized discrete algorithms for clustering, declustering, slot assignment, and local refinement with which the continuous algorithms are naturally combined. Preliminary test runs on benchmark circuits with up to 184000 cells produce total wirelengths within approximately 5-10% of those of GORDIAN-L in less than one tenth the run time. Such an ultra-fast placement engine is badly needed for timing convergence of the synthesis and layout phases of integrated circuit design.