This paper describes the ISPD global routing benchmark suite and related contests. Total 16 global routing benchmarks are produced from the ISPD placement contest benchmark suite using a variety of publicly available academic placement tools. The representative characteristics of the ISPD global routing benchmark suite include multiple metal layers with layer assignment requirement, wire and via width/space modeling, and macro porosity modeling. The benchmarks have routable nets from 200 thousand 1.6 million. While primarily intended for global routing, they can be certainly extended for detailed routing or routing congestion estimation. In conjunction with the previous ISPD placement contest benchmark suite, the new global routing benchmarks will present realistic and challenging physical design problems of modern complex IC designs

Current design methodologies are geared towards meeting different design criteria, such as delay, area or power. However, in order to correctly identify the critical parts of a circuit for optimization, the circuit has to be electrically clean - i.e., slews on each pin have to be within certain limits, a gate cannot drive more than a certain amount of capacitance, etc. Thus far, this requirement has largely been ignored in the literature. Instead, existing methods which optimize delay are used to fix electrical violations. This leads to solutions that are unnecessarily expensive, and still leave violations that remain unfixed. There is therefore a need for an area-efficient strategy that targets the electrical state of a circuit and fixes all violations quickly. This paper explicitly defines "electrical violations" and presents a flexible approach (called EVE, the electrical violation eliminator) for fixing these. Experimental results validate our approach.

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 traditional purpose of physical synthesis is to perform timing closure , i.e., to create a placed design that meets its timing specifications while also satisfying electrical, routability, and signal integrity constraints. In modern design flows, physical synthesis tools hardly ever achieve this goal in their first iteration. The design team must iterate by studying the output of the physical synthesis run, then potentially massage the input, e.g., by changing the floorplan, timing assertions, pin locations, logic structures, etc., in order to hopefully achieve a better solution for the next iteration. The complexity of physical synthesis means that systems can take days to run on designs with multimillions of placeable objects, which severely hurts design productivity. This paper discusses some newer techniques that have been deployed within IBM's physical synthesis tool called PDS that significantly improves throughput. In particular, we focus on some of the biggest contributors to runtime, placement, legalization, buffering, and electric correction, and present techniques that generate significant turnaround time improvements

Network tomography is an appealing method for active measurement of link level characteristics such as delay and loss on end-to-end paths. Most network tomography techniques developed to date are based on one-way measurements requiring collaboration from both sending and receiving hosts which severely limits the scope of the paths over which these techniques can be used. We extend our previous work on Network Radar, a new tomographic inference method based on round trip time (RTT) measurements from TCP SYN/SYN-ACK packets. In this paper, our contributions are three-folded. (1) We extend our analytic framework for estimating delay variance on the shared network segment using Network Radar to include confidence estimates which enable measurement accuracy to be assessed - an important consideration for practical deployment. (2) We evaluate Network Radar in a series of experiments conducted in a controlled laboratory environment. These tests explore the boundaries of effectiveness of our RTT-based method, and show that it works well over a wide range of traffic conditions. (3) We evaluate Network Radar in a series of tests conducted in the wide area Internet. These tests show that RTT-based delay variance estimates can be used effectively to identify most likely network topology - a natural and verifyable application for RTT tomography. The performance results in this paper demonstrate that Network Radar can now be used for both research and operational purposes.

To achieve timing closure, one often has to run through several iterations of physical synthesis flows, for which placement is a critical step. During these iterations, one hopes to consistently move towards design convergence. A placement algorithm that is "stable" will consistently drive towards similar solutions, even with changes in the input netlist and placement parameters. Indeed, the stability of the algorithm is arguably as important a characteristic as the wirelength it achieves. However, currently there is no way to actually quantify the stability of a placement algorithm. This work seeks to address the issue by proposing metrics that measure the stability of a placement algorithm. Our experimental results examine the stability of three different placement algorithms with our proposed metrics and convincingly illustrate that some algorithms are quantifiably more stable than others. We believe that this opens the door to applying different standards for evaluating placement algorithms in terms of their effectiveness for achieving timing closure.

Without the MCNC and ISPD98 benchmarks, it would arguably not have been possible for the academic community to make consistent advances in physical design over the last decade. While still being used extensively in placement and floorplanning research, those benchmarks can no longer be considered representative of today's (and tomorrow's) physical design challenges. In order to drive physical design research over the next few years, a new benchmark suit is being released in conjunction with the ISPD2005 placement contest. These benchmarks are directly derived from industrial ASIC designs, with circuit sizes ranging from 210 thousand to 2.1 million placeable objects. Unlike the ISPD98 benchmarks, the physical structure of these designs is completely preserved, giving realistic challenging designs for today's placement tools. Hopefully, these benchmarks will help accelerate new physical design research in the placement, floor-planning, and routing.

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.

Knowledge of link specific traffic characteristics is important in the operation and design of wide area networks. Network tomography is a powerful method for measuring characteristics such as delay and loss on network-internal links using end--to--end active probes. Prior work has established the basic mechanisms for the use of tomographic inference techniques in the networking context. However, the measurement methods described in prior network tomography studies require cooperation between sending and receiving end-hosts, which limits the scope of the paths over which the measurements can be made. In this paper, we describe a new network tomographic technique based on round trip time (RTT) measurements which eliminates the need for special-purpose cooperation from receivers. Our technique uses RTT measurements from TCP SYN and SYN-ACK segments to estimate the delay variance of the shared network segment in the standard one sender - two receivers configuration. We call this approach Network Radar since it is analogous to standard radar. We present an analytic evaluation of Network Radar that specifies the variance bounds within which the technique is effective. We also evaluate Network Radar in a series of tests conducted in a controlled laboratory environment using live end hosts and IP routers. These tests demonstrate the boundaries of effectiveness of the RTT-based approach.

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 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.

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.