We propose a timing optimization framework that replaces critical paths by logically equivalent realizations with less delay. Our tool allows to revise early decisions on the logical structure of the netlist in late physical design. The core routine of our framework is a new algorithm that constructs delay-optimized circuits for alternating AND-OR paths with prescribed input arrival times. It is a sophisticated dynamic programming algorithm which is a common generalization of the previously best approaches. In contrast to all earlier methods, we avoid fixing the structure of sub-solutions before deciding on how to combine them, significantly expanding the search space of the algorithm. Our algorithm provably fulfills the best known approximation guarantees, almost always computes delay-optimum solutions, and empirically outperforms all previous approaches. The reduction to AND-OR path optimization allows us to optimize general combinatorial paths of arbitrary length in our logic restructuring framework. The framework is applied successfully as a late step in an industrial physical design flow. Experiments demonstrate the effectiveness of our tool on industrial 7nm instances.

We consider the fundamental problem of constructing fast circuits for the carry bit computation in binary addition. Up to a small additive constant, the carry bit computation reduces to computing an A nd -O r path, i.e., a formula of type t 0 ∧ ( t 1 ∨ ( t 2 ∧ (… t m −1 ) …) or t 0 ∨ ( t 1 ∧ ( t 2 ∨ (… t m −1 ) …). We present an algorithm that computes the fastest known Boolean circuit for an A nd -O r path with given arrival times a ( t 0 ), …, a ( t m −1 ) for the input signals. Our objective function is delay, a natural generalization of depth with respect to arrival times. The maximum delay of the circuit we compute is log 2 W + log 2 log 2 m + log 2 log 2 log 2 m + 4.3, where W := ∑ i = 0 m −1 2 a ( t i ) . Note that ⌈ log 2 W ⌉ is a lower bound on the delay of any circuit depending on inputs t 0 , …, t m −1 with prescribed arrival times. Our method yields the fastest circuits for A nd -O r paths, carry bit computation, and adders in terms of delay known so far.

We present a new algorithm for VLSI placement. Our tool BonnPlace incorporates a partitioning-based legalization into a force-directed loop by iteratively pulling circuits towards their positions in a legalized placement. This self-stabilizing algorithm combines the accuracy of partitioning-based methods with the stability of force-directed placement strategies. Using information from earlier iterations, it is capable of improving netlength as well as more involved objective functions like routability and timing behavior. In contrast to previous techniques, we legalize with higher effort, which allows us to reduce the number of iterations. Performance is further improved by adapting a clustering heuristic that takes into account the current cell positions, both for clustering and unclustering. We tested our tool on recent instances from industry and on publicly available benchmark suites. In particular on the routability-driven placement instances of the DAC 2012 contest, our algorithm produces the best known results.

We describe BONNPLACELEGAL, an algorithm for VLSI placement legalization. Based on a minimum-cost flow algorithm that iteratively augments flows along paths, our approach ensures that only augmentations are considered that can be realized exactly by cell movements. Hence, this method avoids realization problems that are inherent to previous flow-based legalization algorithms. As a result, it combines the global perspective of minimum-cost flow approaches with the efficiency of local search algorithms. The tool is mainly designed to minimize total and maximum cell movement, but it is flexible enough to optimize other objective functions provided that the effect of single cell movements on them can be estimated efficiently. We compare our approach to legalization tools from industry and academia by experiments on dense recent real-world designs and public benchmarks. The results show that we are much faster and produce significantly better results in terms of average (linear and quadratic) and maximum movement than any other tool. The experiments also demonstrate that by minimizing squared movement we also produce a smaller increase in net length than the other tools.

We present a new approach to VLSI placement legalization. Based on a minimum-cost flow algorithm that iteratively augments flows along paths, our algorithm ensures that only augmentations are considered that can be realized exactly by cell movements. Hence, the method avoids realization problems which are inherent to previous flow-based legalization algorithms. As a result, it combines the global perspective of minimum-cost flow approaches with the efficiency of local search algorithms. The tool is mainly designed to minimize total and maximum cell movement but it is flexible enough to optimize the effect on timing or netlength, too. We compare our approach to legalization tools from industry and academia by experiments on dense recent real-world designs and public benchmarks. The results show that we are much faster and produce significantly better results in terms of average (linear and quadratic) and maximum movement than any other tool.

BonnPlace is the placement tool of the University of Bonn, Germany. It is continuously used in the industry for the placement of most complex chips. Global placement is based on quadratic placement and multisection. Legalization of macros and standard cells uses minimum cost flow and dynamic programming algorithms. We describe details of our implementation and present new experimental results.

We present BonnPlace, a new VLSI placement algorithm that combines the advantages of analytical and partitioning-based placers. Based on (non-disjoint) placements minimizing the total quadratic netlength, we partition the chip area into regions and assign the circuits to them (meeting capacity constraints) such that the placement is changed as little as possible. The core routine of our placer is a new algorithm for the Transportation Problem that allows to compute efficiently the circuit assignments to the regions. We test our algorithm on a set of industrial designs with up to 3.6 millions of movable objects and two sets of artificial benchmarks showing that it produces excellent results. In terms of wirelength, we can improve the results of leading-edge placement tools by about 5%.

VLSI placement tools usually work in two steps: First, the cells that have to be placed are roughly spread out over the chip area ignoring disjointness (global placement). Then, in a second step, the cells are moved to their final position such that all overlaps are removed and all additional constraints are met (detailed placement or legalization).We consider algorithms for legalization. In particular, we analyze a generic legalization algorithm based on minimum cost flows and dynamic programming. Specializations are being used in industry for many years, and an improved version was proposed very recently in [2]. The objective of all these algorithms is to minimize the weighted sum of (squared) movements, i.e. they assume the placement to be already optimized except for not being legal.To evaluate results, we propose two different lower bounds for the legalization problem, one based on linear assignment, and the other one based on an integer linear programming relaxation. We prove that the second lower bound is always at least as good as the first one. We also show how to compute the bounds efficiently. We then give an extensive experimental analysis of the algorithms and the lower bounds by testing them on a set of recent industrial ASICs with up to 2.4 million cells. In particular, we show that the gap between the new algorithm and the better lower bound is usually less than 10 percent. This proves that the legalization problem is solved almost optimally.Besides (weighted) total (squared) movement, we also consider various other objectives like wirelength, timing, and routability. Our experiments demonstrate that minimizing total (weighted, squared) movement has almost no negative effect on the timing properties, routability and netlength. Therefore the new algorithm will help in overall design closure.

Most tools for the placement of very large scale integrated chips work in two steps. First, the cells that have to be placed are roughly spread out over the chip area, ignoring disjointness (global placement). Then, in a second step, the cells are moved to their final position such that all overlaps are removed and all additional constraints are met (detailed placement or legalization). In this paper, we describe new ideas for legalization. We divide the task into appropriate subproblems that can be solved optimality in polynomial time. For the most important parts, even a linear running time can be shown. Together, the solutions of the subproblems can be combined to an algorithm that legalizes a placement minimizing the total (linear or squared) movement of cells. The algorithm is tested on a set of recent application specific integrated circuits and the results are compared to lower bounds showing that it computes provably good solutions (within a few percent of the optimum) even on very large industrial chips. By introducing significantly fewer violations, our legalization helps in overall design closure.

We present a fast but reliable way to detect routing criticalities in very large scale integration chips. In addition, we show how this congestion estimation can be incorporated into a partitioning based placement algorithm. Different to previous approaches, we do not rerun parts of the placement algorithm or apply a postplacement optimization, but we use our congestion estimator for a dynamic avoidance of routability problems in one single run of the placement algorithm. Computational experiments on chips with up to 1300000 cells are presented. The framework reduces the usage of the most critical routing edges by 9.0% on average, the running time increase for the placement is about 8.7%. However, due to the smaller congestion, the running time of routing tools can be decreased drastically, so the total time for placement and (global) routing is decreased by 47% on average.

We present a fast but reliable way to detect routing criticalities in VLSI chips. In addition, we show how this congestion estimation can be incorporated into a partitioning based placement algorithm. Different to previous approaches, we do not rerun parts of the placement algorithm or apply a post-placement optimization, but we use our congestion estimator for a dynamic avoidance of routability problems in one single run of the placement algorithm. Computational experiments on chips with up to 1,300,000 cells are presented: The framework reduces the usage of the most critical routing edges by 9.0% on average, the running time increase for the placement is about 8.7%. However, due to the smaller congestion, the running time of routing tools can be decreased drastically, so the total time for placement and (global) routing is decreased by 47% on average.

We consider the problem of placing a set of cells in a single row with a given horizontal ordering, minimizing the (weighted) bounding box netlength. We analyze the running time of an algorithm of Kahng, Tucker and Zelikovsky which solves this problem optimally. By using different data structures we are able to improve the worst-case running time in the unweighted case as well as in the presence of netweights.