There have been significant prior efforts to quantify performance of academic placement algorithms, primarily by creating artificial test cases that attempt to mimic real designs, such as the PEKO benchmark containing known optimas [5]. The idea was to create benchmarks with a known optimal solution and then measure how far existing placers were from the known optimal. Since the benchmarks do not necessarily correspond to properties of real VLSI netlists, the conclusions were met with some skepticism. This work presents two custom constructed datapath designs that perform common logic functions with hand-designed layouts for each. The new generation of academic placers is then compared against them to see how the placers performed for these design styles. Experiments show that all academic placers have wirelengths significantly greater then the manual solution; solutions range from 1.75 to 4.88 times greater wirelengths. These testcases will be released publically to stimulate research into automatically solving structured datapath placement problems.

The impact of physical synthesis on design performance is increasing as process technology scales. Current physical synthesis flows generally perform a series of individual netlist transformations based on local timing conditions. However, such optimizations lack sufficient perspective or scope to achieve timing closure in many cases. To address these issues, we develop an integrated transformation system that performs multiple optimizations simultaneously on larger design partitions than existing approaches. Our system, SPIRE, combines physically-aware register retiming, along with a novel form of cloning and register placement. SPIRE also incorporates a placement-dependent static timing analyzer (STA) with a delay model that accounts for buffering and is suitable for physical synthesis. Empirical results on 45 nm microprocessor designs show 8% improvement in worst-case slack and 69% improvement in total negative slack after an industrial physical synthesis flow was already completed.

In a complete physical synthesis flow, optimization transforms, that can improve the timing on critical paths that are already well-optimized by a series of powerful transforms (timing driven placement, buffering and gate sizing) are invaluable. Finding such a transform is quite challenging, to say nothing of efficiency. This work explores innovative cloning (gate duplication) techniques to improve timing-closure in a physical synthesis environment.

A fundamental problem in timing-driven physical synthesis is the reduction of critical paths in a design. In this work, we propose a powerful new technique that moves (and can also resize) multiple cells simultaneously to smooth critical paths, thereby reducing delay and improving worst negative slack or a figure-of-merit. Our approach offers several key advantages over previous formulations, including the accurate modeling of objectives and constraints in the true timing model, and a guarantee of legality for all cell locations.

The purpose of global placement is to find non-overlapping locations for cells, typically while minimizing a wirelength objective. Because of this objective, however, when more timing information about the design is known, some cells will inevitably be sub-optimally placed from a timing perspective. In this paper, we present two new techniques to incrementally improve placements by moving cells to their optimal timing locations. We call our approach Pyramids, since it uses pyramid-shaped delay surfaces to solve for the optimal location, rather than running a more expensive linear programming solver. We show how to apply these techniques to timing-driven detailed placement and also for more accurate late-stage incremental timing correction. Experimental results validate the effectiveness of Pyramids by showing significantly improved timing after an industrial placement algorithm. Furthermore, compared to the linear programming solvers, the speedup of Pyramids solver is 373x vs. CLP and 448x vs. GLPK.

Physical synthesis tools are responsible for achieving timing closure. Starting with 130nm designs, multiple cycles are required to cross the chip, making latch placement critical to success. We present a new physical synthesis optimization for latch placement called RUMBLE (Rip Up and Move Boxes with Linear Evaluation) that uses a linear timing model to optimize timing by simultaneously re-placing multiple gates. RUMBLE runs incrementally and in conjunction with static timing analysis to improve the timing for critical paths that have already been optimized by placement, gate sizing, and buffering. Experimental results validate the effectiveness of the approach: our techniques improve slack by 41.3% of cycle time on average for a large commercial ASIC design

Physical-synthesis tools are responsible for achieving timing closure. Starting with 130-nm designs, multiple cycles are required to cross the chip, making latch placement critical to success. We present a new physical-synthesis optimization for latch placement called Rip Up and Move Boxes with Linear Evaluation (RUMBLE) that uses a linear timing model to optimize timing by simultaneously replacing multiple gates. RUMBLE runs incrementally and in conjunction with static timing analysis to improve the timing for critical paths that have already been optimized by placement, gate sizing, and buffering. Experimental results validate the effectiveness of the approach: Our techniques improve slack by 41.3% of cycle time on average for a large commercial ASIC design.

The proliferation of OpenAccess is opening promising new research opportunities to academic communities. The benefits of adopting an OpenAccess based approach to EDA research are growing, and we review a number of them. Among them is the ability to learn about a domain while writing software for it, increased ease of code reuse, high-quality benchmarks, and enhanced industry adoption.

In this invited note we outline several algorithms and features appearing in Capo 10, free open-source software for congestion-driven standard cell placement, mixed-size placement and floorplanning. Capo scales on par with industry placers and has been successfully used with a broad range of netlists. It can also satisfy lower bounds on local whitespace, using several techniques for global, detail and macro placement.

Large macro blocks, predesigned datapaths, embedded memories, and analog blocks are increasingly used in application-specific integrated circuit (ASIC) designs. However, robust algorithms for large-scale placement of such designs have only recently been considered in the literature. Large macros can be handled by traditional floorplanning, but are harder to account for in min-cut and analytical placement. On the other hand, traditional floorplanning techniques do not scale to large numbers of objects, especially in terms of solution quality. The authors propose to integrate min-cut placement with fixed-outline floorplanning to solve the more general placement problem, which includes cell placement, floorplanning, mixed-size placement, and achieving routability. At every step of min-cut placement, either partitioning or wirelength-driven fixed-outline floorplanning is invoked. If the latter fails, the authors undo an earlier partitioning decision, merge adjacent placement regions, and refloorplan the larger region to find a legal placement for the macros. Empirically, this framework improves the scalability and quality of results for traditional wirelength-driven floorplanning. It has been validated on recent designs with embedded memories and accounts for routability. Additionally, the authors propose that free-shape rectilinear floorplanning can be used with rough module-area estimates before logic synthesis

In this invited note we describe Capo, an open-source software tool for cell placement, mixed-size placement and floorplanning with emphasis on routability. Capo is among the fastest academic placers and scales to millions of movable objects. This note surveys the overall structure of Capo, discusses recent improvements and describes ongoing research.

Physical design EDA research in academia has historically been based on infrastructure developed independently by individual contributors. This has led to fragmentation in the community, where interaction, data interchange and comparison of results between tools are difficult. We discuss our early experience with the OpenAccess Gear system, an open source software initiative intended to provide pieces of the critical integration and analysis infrastructure that are taken for granted in proprietary tools, but often wholly absent in research tools. Built on top of the widely available OpenAccess database, OA Gear provides components such as industrial-strength static timing analysis and extensible layout and netlist visualization. We discuss preliminary results from two on-going research efforts that have adopted OA Gear as their infrastructure: retrofitting the University of Michigan Capo placer into this environment, and the addition of a timing-driven capability to the Carnegie Mellon Warp placer.

In the last 20 years, mainstream research in VLSI placement has been driven by formal optimization and the ad hoc requirement that downstream tools, particularly routers, work. Progress is currently measured by improving routed wirelength and place-and-route run-time on large benchmarks. However, these results now appear questionable as (i) major placers were shown to be tuned to particular benchmark suites, and (ii) some reported improvements could not be replicated on full-fledged industrial circuits.Instead of blind wirelength minimization, our work seeks a better understanding of what a good placer should produce and what existing placers actually produce. We abstract away details from various circuit patterns into separate "constructive benchmarks" and perform a detailed study of leading placers. Unlike the randomized PEKO benchmarks, ours are highly structured and easy to visualize. We know all of their wirelength-optimal solutions, and in many cases there is only one per benchmark. By comparing actual solutions to optimal ones, we reason about the underlying placer algorithms and their possible improvements.In a new development, we show that the (wirelength) sub-optimality ratio of several existing placers quickly grows with the size of the netlist. Some of the reasons for such poor performance are obvious from our visualizations. While it seems easy to coerce a given placer to improve wirelength on any particular constructive benchmark, improving the overall performance is more difficult. We improve the performance of Capo placer on several constructive benchmarks and a proprietary 72K-cell circuit from IBM, without wirelength penalty on commonly used benchmarks.

Large macro blocks, pre-designed datapaths, embedded memories and analog blocks are increasingly used in ASIC designs. However, robust algorithms for large-scale placement of such designs have only recently been considered in the literature, and improvements by over 10% per paper are still common. Large macros can be handled by traditional floorplanning, but are harder to account for in min-cut and analytical placement. On the other hand, traditional floorplanning techniques do not scale to large numbers of objects, especially in terms of solution quality. We propose to integrate min-cut placement with fixed-outline floor-planning to solve the more general placement problem, which includes cell placement, floorplanning, mixed-size placement and achieving routability. At every step of min-cut placement, either partitioning or wirelength-driven, fixed-outline floorplanning is invoked. If the latter fails, we undo an earlier partitioning decision, merge adjacent placement regions and re-floorplan the larger region to find a legal placement for the macros. Empirically, this framework improves the scalability and quality of results for traditional wirelength-driven floorplanning. It has been validated on recent designs with embedded memories and accounts for routability. Additionally, we propose that free-shape rectilinear floorplanning can be used with rough module-area estimates before synthesis.