Communications of the ACM
Home/Magazine Archive/June 2013 (Vol. 56, No. 6)/Technical Perspective: Circuit Placement Challenges/Full Text
Research highlights
Technical Perspective: Circuit Placement Challenges
For a semiconductor circuit with billions of transistors, finding desired locations of circuit components is a challenging task that substantially impacts circuit quality and manufacturing cost. On-chip components must not overlap and should simultaneously optimize several conflicting cost metrics, such as silicon area, circuit performance, and power. Circuit placement—studied since the invention of the integrated circuit (IC)—remains one of the most important steps in VLSI design because it determines the landscape of a silicon chip and increasingly influences other circuit optimizations. Even as a purely computational task, it is difficult. Emerging technology and design challenges have further reshaped the classical placement problem, and thus have provided substantial research opportunities. Consequently, dozens of new placers were developed in the past decade to address the new challenges.
Practical algorithms for VLSI placement trace their roots to three computational approaches: stochastic search based on simulated annealing, repeated min-cut partitioning of hypergraphs, and analytical minimization of specified differentiable functions. Some of these ideas have been successfully combined, but analytical algorithms have recently been recognized to provide the best trade-off between layout quality and scalability for modern VLSI circuits. This trend is not unique to application-specific IC (ASIC) designs, but can also be observed for field-programmable gate array (FPGA) applications. Xilinx Inc., a leading FPGA vendor, recently announced their new FPGA design tool, the Vivado Design Suite, has migrated from the traditional simulated-annealing-based placement to a modern analytical algorithm to improve scalability and design quality. Further, analytical placers have consistently dominated in all recent placement contests organized by IBM Research.
The SimPL placer by Kim et al. is an influential work that furthers the development of analytical placement. The authors formulated a self-contained, concise, and efficient framework to handle modern placement problems. To better understand the contributions of this placer, we start by dissecting the basic flow and structure of analytical placement. Modern analytical placers typically consist of three major steps: Global placement estimates ideal positions for individual circuit components to minimize a predefined cost function (such as interconnect length) while ignoring component overlaps; Legalization removes cell overlaps while trying to preserve the cost; and Detailed placement further improves the legalized placement solution. Global placement is crucial in determining placement quality and speed. Analytical placement models global placement as a mathematical program consisting of an objective function (for example, total interconnect length) and a set of placement constraints (for example, component-density limit), and then minimizes the objective using numerical algorithms. This minimization problem involves four major ingredients: A differentiable function to approximate interconnection length, algorithms to reduce component overlaps (to satisfy optimization constraints), simultaneous optimization of the objective and overlap functions, and the optimization process.
SimPL proposes an elegant integration of the Bound2Bound interconnection length function from the earlier Kraftwerk2 algorithm, geometric partitioning for overlap reduction, region density handling for interconnection length and overlap minimization, and quadratic optimization. SimPL tightly integrates interconnection length and overlap minimization. Like the earlier Vasstu algorithm, SimPL maintains a progression of lower-bound and upper-bound placements that converge to produce a solution. The lower-bound placements are produced by quadratic programming. The upper-bound placements are produced by look-ahead legalization that temporarily spreads out high-density regions to estimate a desirable placement. This concept of look-ahead legalization is similar to what was previously proposed for floor-planning at UCLA and for placement in my group at NTU. However, SimPL develops a new algorithm that implements look-ahead legalization using geometric partitioning and nonlinear scaling. Equally important is the systematic use of look-ahead legalization in global-placement iterations that is characteristic of SimPL. Here the idea is to treat the legalized component locations as fixed anchors (like the Vasstu algorithm) to which the components are tethered with artificial interconnects when the lower-bound placement is produced by quadratic programming. With an appropriate substitution, such connections to fixed locations do not increase the matrix size for quadratic optimization and, in fact, enhance diagonal dominance in matrix solvers, leading to faster convergence.
Among the two major families of analytical placers, quadratic placers (for example, Kraftwerk2 and SimPL) are typically more efficient, while nonlinear (non-quadratic) placers (for example, mPL and NTUplace series) often have better placement quality. To avoid biases with respect to specific circuit structures, more studies based on multiple sets of benchmarks (including at least recently released IBM benchmark suites) would be needed to explore the stability of a placer. Yet, interconnect length and overlap optimization alone is certainly not the end objective of modern placement. Emerging technologies and needs bring up substantial new challenges; some most addressed challenges include large-scale mixed-size placement with millions of cells and hundreds/thousands of big circuit blocks, routability, timing, manufacturability, reliability, power delivery, clock networks, 3D ICs, asynchronous designs, and parallelism. These challenges offer substantial placement research opportunities for the decades to come.
©2013 ACM 0001-0782/13/06
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2013 ACM, Inc.
No entries found