The last few years have seen significant advances in the quality of placement algorithms. This is in part due to the availability of large, challenging testcases by way of the ISPD-2005 [17] and ISPD-2006 [16] placement contests. These contests primarily evaluated the placers based on the half-perimeter wire length metric. Although wire length is an important metric, it still does not address a fundamental requirement for placement algorithms, namely, the ability to produce routable placements.

Routability is a mandatory metric for modern large-scale mixed-size circuit placement which typically needs to handle hundreds of large macros and millions of small standard cells. However, most existing academic mixed-size placers either focus on wirelength minimization alone, or do not consider the impact of movable macros on routing. To remedy these insufficiencies, this paper formulates design-hierarchy information as a novel fence force in an analytical placement framework. Unlike a state-of-the-art routability-driven placer that simply removes net bounding boxes during placement, this paper utilizes two different optimization forces, the global fence force and the local spreading force, to determine the positions of both standard cells and macros. We utilize design-hierarchy information to determine block distributions globally, and locally we add additional spreading forces to preserve sufficient free space among blocks by a net-topology estimation. With the interactions between these two forces, our placer can well balance routability and wirelength. Experimental results show that our placer can achieve the best routability and routing time among all published works.

Traditionally, the goal of physical synthesis has been to produce a physical realization of the input netlist that meets its timing constraints with minimum area. However, design routability has emerged from a secondary objective to perhaps the primary objective, in no small part due to the myriad of rules and constraints that emerge with each successive technology. This work overviews the complexities with modeling congestion during physical synthesis and discusses how optimizations may be able to provide some relief.

To ensure chip manufacturability, all routes must be completed without violations. Furthermore, the chip's power consumption and performance are determined by the length of its routed wires. Therefore, our work focuses on minimizing wirelength. Our key innovations include: (1) a novel branch-free representation (BFR) for routed nets, (2) a trigonometric penalty function (TPF), (3) dynamic adjustment of Lagrange multipliers (DALM), (4) cyclic net locking (CNL), and (5) aggressive lower-bound estimates (ALBE) for A*-search, resulting in faster routing. We complete all routable ISPD 2008 contest benchmarks and re-placed adaptec suite without violation and produce shorter routes.

Timing-driven placement is a critical step in nanometer-scale physical synthesis. To improve design timing on a global scale, net-weight based global timing-driven placement is a commonly used technique. This paper shows that such an approach can improve timing, but often degrades wire length and routability. Another problem with existing timing-driven placers is inconsistencies in the definition of timing closure. Approaches using linear programming are forced to make assumptions about the timing models that simplify the problem. To truly do timing-driven placement, the placer must be able to make queries to a real timing analyzer with incremental capabilities. This paper describes an incremental timing-driven placer called ITOP. Using accurate timing from an industrial static timer, ITOP integrates incremental timing closure optimizations like buffering and repowering within placement to improve design timing without degrading wire length and routability.

Dramatic progress has been made in algorithms for placement and routing over the last 5 years, with improvements in both speed and quality. Combining placement and routing into a joint optimization has also been proposed. However, it remains unclear if the benefits would be significant enough to justify major changes in commercial tools. CRISP addresses this challenge and is the first tool to demonstrate tangible benefits of combined place-and-route optimization including fewer global routing detours, reduced detailed routing violations and runtime, and even shrinking the floorplan of a commercial design. We employ fast global routing to choose standard cells to temporarily inflate and iteratively spread for congestion reduction. Spreading only in congested regions, we enable die area reduction by facilitating routing with high area utilization.

Our work addresses protection of hardware IP at the mask level with the goal of preventing unauthorized manufacturing. The proposed protocol based on chip locking and activation is applicable to a broad category of electronic systems with a primary bus. Such designs include (1) numerous IP offerings for USB, PCI, PCI-E, AMBA and other bus standards typically used in system-on-a-chip designs and computer peripherals, (2) SRAM-based FPGAs that are programmed through an input bus, (3) general-purpose and embedded microprocessors, including soft cores, (4) DSPs, (5) network processors, and (6) game consoles. Our key insight is that such designs can be locked by scrambling the central bus by controlled reversible bit-permutations and substitutions. To securely establish a unique code per chip to control bus scrambling, we employ true random number generators and Diffie-Hellman cryptography during activation.

As semiconductor manufacturing requires greater capital investments, the use of contract foundries has grown dramatically, increasing exposure to mask theft and unauthorized excess production. While only recently studied, IC piracy has now become a major challenge for the electronics and defense industries. We propose a novel comprehensive technique to end piracy of integrated circuits (EPIC). It requires that every chip be activated with an external key, which can only be generated by the holder of IP rights, and cannot be duplicated. EPIC is based on (i) automatically-generated chip IDs, (ii) a novel combinational locking algorithm, and (Hi) innovative use of public-key cryptography. Our evaluation suggests that the overhead of EPIC on circuit delay and power is negligible, and the standard flows for verification and test do not require change. In fact, major required components have already been integrated into several chips in production. We also use formal methods to evaluate combinational locking and computational attacks. A comprehensive protocol analysis concludes that EPIC is surprisingly resistant to various piracy attempts.

Wire routing, an important step in modern VLSI design, is increasingly responsible for timing closure and manufacturability. The CAD community has witnessed remarkable improvements in speed and quality of global routing algorithms in response to the inaugural ISPD 2007 Global Routing Contest, where prizes were awarded for best results on a new set of large industry benchmarks.

In this paper, we describe significant improvements to core routing technologies and outperform the best results from the International Symposium on Physical Design 2007 Global Routing Contest and the International Conference on Computer-Aided Design 2007 in terms of route completion and total wirelength.

In this work, we propose a new and efficient approach to the floorplan repair problem, where violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, a scalable placement algorithm, or result from engineering adjustments to an existing floorplan. In such cases, overlapping modules must be separated, and others may need to be repositioned to satisfy additional requirements. Our algorithmic framework uses an expressive graph-based encoding of constraints which can reflect fixed-outline, region, proximity and alignment constraints. By tracking the implications of existing constraints, we resolve violations by imposing gradual modifications to the floorplan, in an attempt to preserve the characteristics of its initial design. Empirically, our approach is effective at removing overlaps and repairing violations that may occur when design constraints are acquired and imposed dynamically.

In a realistic design flow, circuit and system optimizations must interact with physical aspects of the design. For example, improvements in timing and power may require replacing large modules with variants that have different power/delay trade-off, shape and connectivity. New logic may be added late in the design flow, subject to interconnect optimization, To support such flexibility in design flows we develop a robust system for performing engineering change orders (ECOs). In contrast with existing stand-alone tools that offer poor interfaces to the design flow and cannot handle a full range of modern VLSI layouts, our ECO-system reliably handles fixed objects and movable macros in instances with widely varying amounts of whitespace. It detects geometric regions and sections of the netlist that require modification and applies an adequate amount of change in each case. Given a reasonable initial placement, it applies minimal changes, but is capable of re-placing large regions to handle pathological cases. ECO-system can be used in the range from high-level synthesis, to physical synthesis and detail placement.

In this work we describe significant improvements to core routing technologies and outperform the best results from the ISPD '07 global routing contest, as well as previous literature, in terms of route completion, runtime and total wirelength. In particular, our router, FGR, improves upon wirelengths produced by BoxRouter and MaizeRouter in March 2007 by 9.9% and 8.4%. respectively. Additionally, we reveal the mathematical basis of negotiated-congestion routing. offer comprehensive analysis of existing routing techniques and discuss several applications at the nanometer scale.

We demonstrate that Steiner-tree wirelength (StWL) correlates with routed wirelength (rWL) much better than the more common half-perimeter wirelength (HPWL) objective. Therefore, we develop a technique to optimize StWL in global and detail placement without a significant runtime penalty. This new optimization, along with congestion-driven whitespace distribution, improves overall Place-and-Route results, making the use of HPWL unnecessary. Additionally, our empirical results provide ample evidence that the fidelity of net-length estimates is more important than their accuracy in Place-and-Route. The new data structures that make our min-cut algorithms fast can also be useful in multilevel analytical placement. Our placement algorithm Rigorous Optimization Of Steiner-Trees Eases Routing (ROOSTER) outperforms the best published results for Dragon, Capo, FengShui, mPL-R/WSA, and APlace in terms of rWL by 10.7%, 5.6%, 9.3%, 5.5%, and 4.2%, respectively. Via counts, which are especially important at 90 nm and below, are improved by 15.6% over mPL-R/WSA and 11.9% over APlace

In a realistic design flow, circuit and system optimizations must interact with physical aspects of the design. For example, improvements in timing and power may require the replacement of large modules with variants that have different power/delay tradeoff, shape, and connectivity. New logic may be added late in the design flow, which is subject to interconnect optimization. To support such flexibility in design flows, we develop a robust system in performing Engineering Change Orders (ECOs). In contrast with the existing stand-alone tools that offer poor interfaces to the design flow and cannot handle a full range of modern very large scale integration layouts, our ECO-system reliably handles fixed objects and movable macros in instances with widely varying amounts of whitespace. It detects geometric regions and sections of the netlist that require modification and applies an adequate amount of change in each case. Given a reasonable initial placement, it applies minimal changes but is capable of replacing large regions to handle pathological cases. The ECO-system can be used in the range from high-level synthesis to physical synthesis and detail placement.

We show how to optimize Steiner-tree Wirelength (StWL) in global and detail placement without a significant runtime penalty, making the use of Half-Perimeter Wirelength unnecessary. Given that StWL correlates with Routed Wirelength (rWL) much better than HPWL, our new optimization improves the overall Place-and-Route results. We also develop congestion-driven whitespace distribution during global placement. Comparing to the state of the art where whitespace is redistributed after global placement, we demonstrate that cell-shifting techniques often increase via counts.Our placer ROOSTER outperforms best published results for Dragon, Capo, FengShui, mPL-R/WSA and APlace in terms of routed wirelength by 10.7%, 5.6%, 9.3%, 5.5% and 4.2% respectively. Via counts, especially important at 90nm and below, are improved by 15.6% over mPL-R/WSA and 11.9% over APlace.

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.

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.