Benchmarks have been a cornerstone of research in integrated circuit design. Well defined problems and metrics have allowed research teams to address key challenges and measure the impact of new ideas and methodologies. Traditionally, researchers could follow a handful of conferences and journals to stay abreast of advances. Over the past few years, the research pace has increased, and the number of publication venues has significantly expanded; staying up-to-date has become much more challenging for active research groups, paper reviewers, editors, and for anyone with an interest in a particular topic area.

For years, integrated circuit design has been a driver for algorithmic advances. The problems encountered in the design of modern circuits are often intractable -- and with exponentially increasing size. Efficient heuristics and approximations have been essential to sustaining Moore's Law growth, and now almost every aspect of the design process is heavily automated. There is, however, one notable exception: there is often substantial floor planning effort from human designers to position large macro blocks. The lack of full automation on this step has motivated the exploration of novel optimization methods, most recently with reinforcement learning. In this paper, we argue that there are multiple forces which have prevented full automation -- and a lack of algorithmic methods is not the only factor. If the time has come for automation, there are a number of "traditional'' methods that should be considered again. We focus on recursive bisection, and highlight key ideas from partitioning algorithms that have broader impact than one might expect. We also stress the importance of benchmarking as a way to determine which approaches may be most effective.

Deep learning applications are compute intensive and naturally parallel; this has spurred the development of new processor architectures tuned for the work load. In this paper, we consider structural differences between deep learning neural networks and more conventional circuits -- highlighting how this impacts strategies for mapping neural network compute kernels onto available hardware. We present an efficient mapping approach based on dynamic programming, and also a method to establish performance bounds. We also propose an architectural approach to extend the practical life time of hardware accelerators, enabling the integration of a variety of heterogenous processors into a high performance system. Experimental results using benchmarks from a recent ISPD contest are also reported.

Circuit benchmarks for VLSI physical design have been growing in size and complexity, helping the industry tackle new problems and find new approaches. In this paper, we take a look back at how benchmarking efforts have shaped the research community, consider trade-offs that have been made, and speculate on what may come next.

Integrated circuit design encompasses a wide range of intractable optimization problems. In this paper, we extend linear time hill climbing techniques from graph partitioning to address detailed placement -- this results in a new way to refine circuit designs, dramatically expands the size of practical optimization windows, and enables wire length reductions on a variety of benchmark problems. The approach is versatile and straight-forward to implement, allowing it to be applied to a wide range of problems within design automation, and beyond.

Routing for dense circuits is a major challenge for VLSI physical design. Most routing approaches rely at least partially on a "rip-up and reroute" scheme, where solution quality and run times can be impacted profoundly by the order in which nets are routed. Other routing tools rely on backtracking methods embedded in integer linear programming solvers. In this paper, we present a novel approach which avoids backtracking, and largely eliminates the routing order considerations, by constructing a large number of routings simultaneously. By keeping "options open," our approach sidesteps conflicts. Our approach is a factor of ten faster than other recent work, reduces via counts by 30% or more, and is competitive on both wire length and completion rates. The approach is simple, scalable, and adaptable to the complex constraints of modern circuit fabrication processes.

Embedded systems are designed to perform a specific set of tasks, and are frequently found in mobile, power-constrained environments. There is growing interest in the use of parallel computation as a means to increase performance while reducing power consumption. In this paper, we highlight fundamental limits to what can and cannot be improved by parallel resources. Many of these limitations are easily overlooked, resulting in the design of systems that, rather than improving over prior work, are in fact orders of magnitude worse.

Floorplacement" has attracted attention, as a placement formula- tion for designs with thousands or millions of soft macro blocks. In this paper, we investigate the "standard block" approach, where soft blocks are shaped to have uniform height, rather than a wide range of different sizes. This allows many macro blocks can be treated as standard cells, simplifying the problem to one of ordinary mixed size placement. We obtain high quality results for a suite of recent benchmarks, and also present novel legalization algorithms that are more robust than the widely-used mixed-size tetris approach.

Many important software applications are dominated by non-trivial serial components: Amdahl's Law places a hard upper bound on possible speedup that can be achieved for these applications. In this paper, we propose an integrated software/hardware approach for accelerating hard serial bottlenecks in data structure heavy algorithms. The key idea is to overlap the processing of the main algorithmic functions and the data structure related operations. We describe the language, compiler, ISA and architectural support for such data structure co-processing (DSCP), and define a clean interface between the software and the hardware. We perform extensive simulations using the popular C++ STL container classes, as well as a detailed implementation of our approach for Dijkstra's single-source shortest path algorithm. We find potential for improvements that are well beyond what can be achieved with more conventional parallel computation methods.

The five papers in this special section are extended versions of papers presented at ISPD'07, held in Austin, TX.

Many current integrated circuits designs, such as those released for the ISPD2005 (Nam et al., 2005) placement contest, are extremely large and can contain a great deal of white space. These new placement problems are challenging; analytic placers perform well, but can suffer from high run times. In this paper, we present a new placement tool called Vaastu. Our approach combines continuous and discrete optimization techniques. We utilize network flows, which incorporate the more realistic half-perimeter wire length objective, to facilitate module spreading in conjunction with a log-sum-exponential function based analytic approach. Our approach obtains wire length results that are competitive with the best known results, but with much lower run times.

Rising interconnect delay and power consumption have motivated the investigation of alternative integrated circuit routing architectures. In particular, the X architecture, which features preferred routing in diagonal directions, has gained a measure of industry support, and has even been validated at 65nm. While there has been extensive study of Manhattan design methods, there are markedly fewer published results for non-Manhattan design. To help fill this gap, we study a patented placement method for the X architecture; to our knowledge, there have been no prior published results for the method. Surprisingly, we find that the patented method in fact performs worse than traditional Manhattan methods - for both Manhattan and X routing metrics. We also present a theoretic formulation which explains why solution quality is degraded. Many groups in industry are evaluating the merits of non-Manhattan routing architectures. By providing concrete experimental results, we hope to improve the accuracy of these evaluations.

In 2005 and 2006, ISPD successfully hosted two placement contests and released a total of 16 benchmark circuits. These benchmarks are all derived from real industrial circuits and present modern physical design challenges such as scalability, variety of floorplans, movable macro handling, and congestion mitigation. Since their release, the ISPD placement benchmarks have been extensively used by the physical design community. Indeed, we have observed significant progress in placement and floorplanning in the last few years. Much of this success can be credited to the fact that the placement community finally has large, well-defined benchmark circuits available that allow for fair comparisons among different algorithms. In this presentation, we report the most recent results on ISPD placement benchmarks and review how much progress each placement tool has achieved.

The nine regular papers and two short papers are expanded versions of papers presented at the International Symposium on Physical Design (ISPD), held in San Jose, CA. Topics covered include: a new method for extraction of spatial correlation; placement-related problems; power-grid design; decoupling capacitor optimization; and buffer insertion.

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.

Incremental physical design is an important methodology towards achieving design closure for high-performance large-scale circuits. Placement tools must accommodate incremental changes to the layout and netlist due to physical synthesis techniques without perturbing the original metrics. We present an incremental placement approach using floorplan sizing to manage the resources and demands of the whole chip region in order to accommodate the changes due to gate sizing and buffer insertion. The experimental results show that this approach can accommodate a wide range of incremental changes without a loss in wirelength and routability. Most important, it also maintains the stability of a placement such that the convergence of physical synthesis iterations can be greatly enhanced.

Regular structures are present in many types of circuits. If this structure can be identified and utilized, performance can be improved dramatically. In this paper, we present a novel placement approach that successfully identifies regularity, and obtains placements that are superior to other "general purpose" methods. This method has been integrated into our Feng Shui 2.6 bisection-based placement tool.On experiments with the PEKO benchmarks, our results are within 32% of optimal for both the large and small suites. The largest example, with 2.1 million cells, can be completed in sixteen hours. The majority of our run time is during detail placement--global placement takes under three hours. The success of our method shows that it can find structure, even when the structure was not expected or intended.As part of this work, we have made a number of observations related to the nature of suboptimality in placement. These observations have shown that some neglected research areas have great potential, while problems that receive considerable attention are essentially adequately solved.

Circuit placement has a large impact on all aspects of performance; speed, power consumption, reliability, and cost are all affected by the physical locations of interconnected transistors. The placement problem is NP-Complete for even simple metrics.In this paper, we apply techniques developed by the Operations Research (OR) community to the placement problem. Using an Integer Programming (IP) formulation and by applying a "branch-and-price" approach, we are able to optimally solve placement problems that are an order of magnitude larger than those addressed by traditional methods. Our results show that suboptimality is rampant on the small scale, and that there is merit in increasing the size of optimization windows used in detail placement.

In this paper, we summarize circuit placement techniques and algorithms developed by the BLAC CAD research group; these have been integrated into our recursive bisection based placement tool feng shui. We also briefly describe current research interests.

Recursive bisection is a popular approach for large scale circuit placement problems, combining a high degree of scalability with good results. In this paper, we present a bisection-based approach for both standard cell and mixed block placement; in contrast to prior work, our horizontal cut lines are not restricted to row boundaries. This technique, which we refer to as a fractional cut, simplifies mixed block placement and also avoids a narrow region problem encountered in standard cell placement. Our implementation of these techniques in the placement tool Feng Shui 2.6 retains the speed and simplicity for which bisection is known, while making it competitive with leading methods on standard cell designs. On mixed block placement problems, we obtain substantial improvements over recently published work. Half perimeter wire lengths are reduced by 29% on average, compared to a flow based on Capo and Parquet; compared to mPG-ms, wire lengths are reduced by 26% on average.

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.

Many current designs contain a large number of standard cells intermixed with larger macro blocks. The range of size in these “mixed block ” designs complicates the placement process considerably; traditional methods produce results that are far from satisfactory. In this paper we extend the traditional recursive bisection standard cell placement tool Feng Shui to directly consider mixed block designs. On a set of recent benchmarks, the new version obtains placements with wire lengths substantially lower than other current tools. Compared to Feng Shui 2.4, the placements of a Capo-based approach have 29 % higher wire lengths, while the placements of mPG are 26 % higher. Run times of our tool are also lower, and the general approach is scalable.

Over the last five years, the large scale integrated circuit placement community achieved great strides in the understanding of placement problems, developed new high-performance algorithms, and achieved impressive empirical results. These advances have been supported by a nontrivial benchmarking infrastructure, and future achievements are set to draw on benchmarking as well. In this paper, we review motivations for benchmarking, especially for commercial electronic design automation, analyze available benchmarks, and point out major pitfalls in benchmarking. Our empirical data offers perhaps the first comprehensive evaluation of several leading large-scale placers on multiple benchmark families. We outline major outstanding problems and discuss the future of placement benchmarking. Furthermore, we attempt to extrapolate our experience to circuit layout tasks beyond placement.

In this paper, we present a new method to improve global routing results. By using an amplified congestion estimate to influence a rip-up and reroute approach, we obtain substantial reductions in total congestion. In comparisons with a recently published tool on publicly available benchmarks, our new router is roughly twice as fast, obtains 15.1% reductions in total wire length, and 65.2% reductions in the number of overcongested graph edges. A direct implementation of an old approach also performs extremely well, indicating that some known techniques have been overlooked.

In dense integrated circuit designs, management of routing congestion is essential; an over congested design may be unroutable. Many factors influence congestion: placement, routing, and routing architecture all contribute. Previous work has shown that different placement tools can have substantially different demands for each routing layer; our objective is to develop methods that allow "tuning" of interconnect topologies to match routing resources.We focus on congestion minimization for both Manhattan and non-Manhattan routing architectures, and have two main contributions. First, we combine prior heuristics for non-Manhattan Steiner trees and Preferred Direction Steiner trees into a hybrid approach that can handle arbitrary routing directions, via minimization, and layer assignment of edges simultaneously. Second, we present an effective method to adjust Steiner tree topologies to match routing demand to resource, resulting in lower congestion and better routability.

In this paper, we present improvements to recursive bisection based placement.In contrast to prior work, our horizontal cut lines are not restricted to row boundaries; this avoids a "narrow region" problem.To support these new cut line positions, a dynamic programming based legalization algorithm has been developed.The combination of these has improved the stability and lowered the wire lengths produced by our Feng Shui placement tool.On benchmarks derived from industry partitioning examples, our results are close to those of the annealing based tool Dragon, while taking only a fraction of the run time.On synthetic benchmarks, our wire lengths are nearly 23% better than those of Dragon.For both benchmark suites, our results are substantially better than those of the recursive bisection based tool Capo and the analytic placement tool Kraftwerk.

Over the last five years the VLSI Placement community achieved great strides in the understanding of placement problems, developed new high-performance algorithms, and achieved impressive empirical results. These advances have been supported by non-trivial benchmarking infrastructure, and future achievements are set to draw on benchmarking as well. In this paper we review motivations for benchmarking, especially for commercial EDA, analyze available benchmarks, and point out major pitfalls in benchmarking. We outline major outstanding problems and discuss the future of placement benchmarking. Furthermore, we attempt to extrapolate our experience to circuit layout tasks beyond placement.

Very large scale integration (VLSI) fabrication technology has advanced rapidly, bringing with it a strong demand for faster and better design automation tools. Accurate reporting of results for placement approaches is crucial to the development of improved automation tools; unfortunately, publicly available placement benchmarks are outdated, and there are wide variations in their interpretation. In addition, the metrics considered by some academic research have questionable relevance to modern design. At best, poor benchmarks and differences in interpretation result in misunderstandings of the effectiveness of some approaches. At worst, they can motivate research in areas of very little promise, while other areas which have true potential are ignored. In this paper, we expand on work previously presented, describing current standard cell placement benchmarks and illustrating common differences in their interpretation. We also propose specific interpretation methods for traditional objectives, and discuss new metrics which should be considered in modern placement research. Our hope is that by presenting these issues clearly, we can enable more accurate evaluations of placement methods, and improve research efficiency.

The planar rectilinear Steiner tree problem has been extensively studied. The common formulation ignores circuit fabrication issues such as multiple routing layers, preferred routing directions, and vias between layers. In this paper, the authors extend a previously presented planar rectilinear Steiner tree heuristic to consider layer assignment, preferred routing direction restrictions, and via minimization. They use layer-specific routing costs, via costs, and have a minimum cost objective. Their approach combines the low computational complexity of modern geometry-based methods with much of the freedom enjoyed by graph-based methods. When routing costs mirror those of traditional planar rectilinear Steiner problems, the authors' approach obtains close to 11% reductions in tree lengths, compared to minimum spanning trees; this is on par with the performance of the best available Steiner heuristics. When via costs are significant and layer costs differ, they observe average cost reductions of as much as 37%. Their method can also reduce the number of vias significantly.

In this paper we report experiences on a parallel implementation of a standard cell placement algorithm on a cluster of Myrinet connected PCs. The implementation is based on a recently developed placement tool (Feng Shui) that extends recursive bisection placement to incorporate global aspects of the design using an efficient optimization called iterative deletion. Contrary to previous attempts at parallelizing placement algorithms, initial experimental results show significant performance improvement with small reduction in the placement quality. Furthermore, the reduction in the placement quality does not increase with the number of processors. 1

Recursive partitioning based placement has a long history, but there has been little consensus on how cut sequences should be chosen. In this paper, we present a dynamic programming approach to cut sequence generation. If certain assumptions hold, these sequences are optimal. After study of these optimal sequences, we observe that an extremely simple method can be used to construct sequences that are near optimal.

The planar rectilinear Steiner tree problem has been extensively studied. The common formulation ignores circuit fabrication issues such as multiple routing layers, preferred routing directions, and vias between layers. In this paper, the authors extend a previously presented planar rectilinear Steiner tree heuristic to consider layer assignment, preferred routing direction restrictions, and via minimization. They use layer-specific routing costs, via costs, and have a minimum cost objective. Their approach combines the low computational complexity of modern geometry-based methods with much of the freedom enjoyed by graph-based methods. When routing costs mirror those of traditional planar rectilinear Steiner problems, the authors' approach obtains close to 11% reductions in tree lengths, compared to minimum spanning trees; this is on par with the performance of the best available Steiner heuristics. When via costs are significant and layer costs differ, they observe average cost reductions of as much as 37%. Their method can also reduce the number of vias significantly.

Recursive bisection based placement is well known, and recent advances in partitioning have made the approach more attractive. While partitioners can optimize a placement from a local perspective, high performance design requires consideration of global issues as well. We focus on aspects of the placement problem which cannot be captured with bisection, addressing them through a new approach derived from recent work on k-way partitioning. We consider large values of k, and objective functions which are more complex than the traditional min-cut. Our placement tool, Feng Shui, integrates this new k-way partitioning method into a traditional recursive bisection framework. Experimental results show the effect of the approach; there is reduced variation in solution quality, in 8 of 11 benchmarks best case wire length is improved, and for 9 of 11 benchmarks, average wire length is improved. These improvements are obtained with negligible impact to total run time. 1.

VLSI fabrication technology has advanced rapidly, bringing with it a strong demand for faster and better design automation tools. Accurate reporting of results for placement approaches is crucial to the development of improved automation tools; unfortunately, publicly available placement benchmarks are outdated, and there are wide variations in their interpretation.

In this paper, we study the interconnect layout optimization problem under a higher order resistance-inductance-capacitance model to optimize not only delay, but also waveform for interconnects with nonmonotone signal response in the context of multichip-module global routing. We propose a unified approach that considers topology optimization and waveform optimization simultaneously. Using a new incremental moment-computation algorithm, we interleave topology construction with moment computation to facilitate accurate delay calculation and evaluation of waveform quality. Our algorithm considers a large class of routing topologies, ranging from shortest path Steiner trees to bounded-radius Steiner trees and Steiner routings. We construct a set of required arrival-time Steiner (RATS) trees, providing smooth tradeoffs among signal delay, waveform, and routing area. When combined with the MINOTAUR MCM global router (Cong and Madden, 1998), (Madden, 1998) that we have developed, the RATS-tree solutions prove to be effective in reducing overall routing congestion.

Circuit interconnect has become a substantial obstacle in the design of high performance systems. In this paper we explore a new routing paradigm that strikes at the root of the interconnect problem by reducing wire lengths directly. We present a non-Manhattan Steiner tree heuristic, obtaining wire length reductions of much as 17% on average, when compared to rectilinear topologies. Moreover, we present a graph-based interconnect optimization algorithm, called the GRATS-tree algorithm, which allows performance optimization beyond what can be obtained through wire length reduction alone. The two tree construction algorithms are integrated into a new global router that allows large scale non-Manhattan design. Although we consider circuit placements performed under rectilinear objectives, our global router can reduce maximum congestion levels by as much as 20%. In general we find that the non-Manhattan approach requires additional Steiner points and bends; realization of non-Manhattan routing structures requires additional vias. We observe that the increase in via cost is much less dramatic than might be expected; the benefits of wire length reduction may outweigh the additional via cost.

Personal digital assistants (PDAs) are becoming commonplace, and feature continually increasing processing and storage capabilities. Distribution of media through wireless means to these devices is becoming less expensive, but is not yet widespread. The authors describe a novel communication infrastructure to provide distribution of information to PDAs utilizing inexpensive methods; our approach is both scalable and flexible. Most PDAs support infrared (IR) communication, and we focus on this; our infrastructure is not restricted to this, however, and is adaptable to the emerging wireless communication technologies.

Netlist partitioning is an important and well studied problem.In this paper, a linear time partitioning approach based on iterative deletion is presented.We use the partitioning problem to allow a fair comparison of the iterative deletion approach with well known iterative improvement methods.For partitioning problems with a range of edge weights, and for multi-way partitioning, the iterative deletion approach can outperform the iterative improvement method.The algorithmic approach is flexible and can support complex cost functions directly.

In this paper we present a new global router appropriate for Multichip Module (MCM) and dense Printed Circuit Board (PCB) design, which utilizes a hybrid of the classical rip-up and reroute approach, and the more recent iterative deletion [9] method. The global router addresses performance issues by utilizing recent results in high performance interconnect design, while still effectively minimizing global congestion.

Advances in fabrication technology have resulted in a continual shrinkage of device dimensions.This has resulted in smaller device delays, greater resistance along interconnect wires, and a greater impact of interconnect on total system performance.These changes have driven a considerable number of studies on single-net interconnect optimization, but relatively little work has been done to integrate the results on single-net optimization with the problem of global routing and interconnect optimization for the entire circuit.In this paper, we present the DECIMATE global router for performance driven standard cell design.The router applies both interconnect topology optimization and variable-width wire sizing optimization results to the global routing problem, while mainbaining routing areas that are comparable with TimberWolf Systems' well-known commercial global router, Optimal selection of interconnection structures is shown to be an NP-Hard problem; we provide a simple heuristic for the problem, and show that it is effective with expe'rimcnts on industry benchmarks.Under the Elmore delay model, our global router produces as much as a 35% reduction in critical path delay over TimberWolf Systems' global router, while path length reductions are as large as 52%.Circuit area optimization is performed taking into account variably-sized wires, fixed routing topologies, and pre-existing obstacles; an improved cost function obtains .a.s much &as an 11.6% reduction in channel density over the result, in [lil].

Existing routing problems for delay minimization consider the connection of a single source node to a number of sink nodes, with the objective of minimizing the delay from the source to all sinks, or a set of critical sinks. In this paper, we study the problem of routing nets with multiple sources, such as those found in signal busses. This new model assumes that each node in a net may be a source, a sink, or both. The objective is to optimize the routing topology to minimize the total weighted delay between all node pairs (of a subset of critical node pairs). We present a heuristic algorithm for the multiple-source performance driven routing tree problem based on efficient construction of minimum diameter minimum-cost Steiner trees. Experimental results on random nets with submicrometer CMOS IC and MCM technologies show an average of 12.6% and 21% reduction in the maximum interconnect delay, when compared with conventional minimum Steiner tree based topologies. Experimental results on multisource nets extracted from an Intel processor show as much as a 16.1% reduction in the maximum interconnect delay, when compared with conventional minimum Steiner tree based topologies.

Existing routing problems for delay minimization consider the connection of a single source node to a number of sink nodes, with the objective of minimizing the delay from the source to all sinks, or a set of critical sinks. In this paper, we study the problem of routing nets with multiple sources, such as those found in signal busses. This new model assumes that each node in a net may be a source, a sink, or both. The objective is to optimize the routing topology to minimize the total weighted delay between all node pairs (or a subset of critical node pairs). We present two heuristic algorithms for the multiple-source performance-driven routing problem based on efficient construction of minimum-diameter minimum-cost Steiner trees. Experimental results for sub-micron IC technology show as much as an 11% reduction in the maximum interconnect delay, while MCM results show as much as a 13% reduction, when compared to conventional minimum Steiner tree based routing algorithms.

The authors examine the properties of fanout-free circuits, and develop an algorithm to generate single stuck-at fault test experiments that also detect all multiple stuck-at faults. These experiments are shown to be minimal in size. Results demonstrate that elaborate selection of nonsensitizing test pattern guarantees the detection of all multiple stuck-at faults using single stuck-at test experiments. The algorithm is deterministic, and will produce test sets for tree circuits containing any mixture of AND, OR, NOT, NAND, and NOR gates. The results can be extensively applied to multiple stuck-at fault detection for pseudo tree circuits such as parity checkers. The time complexity of the algorithm is determined to the O(n/sup 2/), where n is the number of gates in the circuit.>