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.