We introduce ZykovColor, a novel SATbased algorithm to solve the graph coloring problem working on top of an encoding that mimics the Zykov tree. Our method is based on an approach of Hébrard and Katsirelos (2020) that employs a propagator to enforce transitivity constraints, incorporate lower bounds for search tree pruning, and enable inferred propagations.

The cost-distance Steiner tree problem seeks a Steiner tree that minimizes the total congestion cost plus the weighted sum of sourcesink delays. This problem arises as a subroutine in timing-constrained global routing with a linear delay model, used before buffer insertion. Here, the congestion cost and the delay of an edge are essentially uncorrelated, unlike in most other algorithms for timing-driven Steiner trees. We present a fast algorithm for the cost-distance Steiner tree problem. Its running time is $\mathcal{O}(t(n \log n+m))$, where $t, n$, and m are the numbers of terminals, vertices, and edges in the global routing graph. We also prove that our algorithm guarantees an approximation factor of $\mathcal{O}(\log t)$. This matches the best-known approximation factor for this problem, but with a much faster running time. To account for increased capacitance and delays after buffering caused by bifurcations, we incorporate a delay penalty for each bifurcation without compromising the running time or approximation factor. In our experimental results, we show that our algorithm outperforms previous methods that first compute a Steiner topology, e.g. based on shallow-light Steiner trees or the Prim-Dijkstra algorithm, and then embed this into the global routing graph.

Uniform cost-distance Steiner trees minimize the sum of the total length and weighted path lengths from a dedicated root to the other terminals. They are applied when the tree is intended for signal transmission, e.g. in chip design or telecommunication networks. They are a special case of general cost-distance Steiner trees, where different distance functions are used for total length and path lengths. We improve the best published approximation factor for the uniform cost-distance Steiner tree problem from 2.39 to 2.05. If we can approximate the minimum-length Steiner tree problem arbitrarily well, our algorithm achieves an approximation factor arbitrarily close to $ 1 + \frac{1}{\sqrt{2}} $. This bound is tight in the following sense. We also prove the gap $ 1 + \frac{1}{\sqrt{2}} $ between optimum solutions and the lower bound which we and all previous approximation algorithms for this problem use. Similarly to previous approaches, we start with an approximate minimum-length Steiner tree and split it into subtrees that are later re-connected. To improve the approximation factor, we split it into components more carefully, taking the cost structure into account, and we significantly enhance the analysis.

We propose a new comprehensive solution to global interconnect optimization. Traditional buffering algorithms mostly insert repeaters on a net-by-net basis based on slacks and possibly guided by global wires. We show how to integrate routing congestion, placement congestion, global timing constraints, power consumption, and additional constraints into a single resource sharing formulation. The core of our algorithm is a new buffered routing subroutine. Given a net and Lagrangean resource prices for routing, timing, placement, and power, it computes a buffered Steiner tree. The resource sharing framework provides a special multiplicative price update for fast convergence. Our algorithm is fast enough for practical instances. We demonstrate experimentally on 7nm microprocessor units that it significantly improves timing while reducing netlength and power consumption in an industrial design flow. Our implementation scales well under parallelization with up to 128 threads.

In this paper, we will first have a brief review of the ISPD 2018 and 2019 Initial Detailed Routing Contests. We will then visit a few important and interesting topics in VLSI routing that includes GPU accelerated routing, signal speed optimization in routing, PCB routing and AI-driven analog routing.

We propose a new comprehensive solution to global interconnect optimization. Traditional buffering algorithms mostly insert repeaters on a net-by-net basis based on slacks and possibly guided by global wires. We show how to integrate routing congestion, placement congestion, global timing constraints, power consumption, and additional constraints into a single resource sharing formulation. The core of our algorithm is a new buffered routing subroutine. Given a net and Lagrangean resource prices for routing, timing, placement, and power, it computes a buffered global route. The resource sharing framework provides a special multiplicative price update for fast convergence. Our algorithm is fast enough for practical instances. We demonstrate experimentally on 7nm microprocessor units that it significantly improves timing while reducing netlength and power consumption in an industrial design flow.

Rectilinear Steiner arborescences under linear delay constraints play an important role for buffering. We present exact algorithms for either minimizing the total length subject to delay constraints, or minimizing the total length plus the (weighted) absolute total negative slack.

We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n -bit numbers (where n is a power of two) with a depth of 2 log 2 n logic gates, size 4 n log 2 n , and all fan-outs bounded by two. Fan-outs of more than two are disadvantageous in practice, because they lead to the insertion of repeaters for repowering the signal and additional depth in the physical implementation. However, the depth bound of the Kogge-Stone adder is off by a factor of two from the lower bound of log 2 n . Two separate constructions by Brent and Krapchenko achieve this lower bound asymptotically. Brent’s construction gives neither a bound on the fan-out nor the size, while Krapchenko’s adder has linear size, but can have up to linear fan-out. With a fan-out bound of two, neither construction achieves a depth of less than 2 log 2 n . In a further approach, Brent and Kung proposed an adder with linear size and fan-out two but twice the depth of the Kogge-Stone adder. These results are 33–43 years old and no substantial theoretical improvement for has been made since then. In this article, we integrate the individual advantages of all previous adder circuits into a new family of full adders, the first to improve on the depth bound of 2 log 2 n while maintaining a fan-out bound of two. Our adders achieve an asymptotically optimum logic gate depth of log 2 n + o (log 2 n ) and linear size O ( n ).

We present a new approach for the cell selection problem based on a resource sharing formulation, which is a specialization of Lagrangian relaxation with multiplicative weight updates. For the convex continuous gate sizing problem, we can prove fast polynomial running times. This theoretical result also gives some justification to previous heuristic multiplicative weight update methods. For the discrete cell selection problem, where voltage thresholds can also be chosen, we employ the new algorithm heuristically and achieve superior results on industrial benchmarks compared with one of the previously best known algorithms, and competitive results on the ISPD 2013 benchmarks. Finally, we demonstrate how the approach can be parallelized effectively achieving speed-ups of up to 16.

We show how to incorporate global static timing constraints into global routing. Our approach is based on the min-max resource sharing model that proved successful for global routing in theory and practice. Static timing constraints are modeled by a linear number of additional resources and customers. The algorithm dynamically adjusts delay budgets and can, thus, tradeoff wiring congestion for delay. As a subroutine, the algorithm routes a single net. If this subroutine is near-optimal, we will find near-optimal solutions for the overall problem very efficiently. The approach works for many delay models; here we discuss a linear delay model (before buffering) and the Elmore delay model (after buffering). We demonstrate the benefit of our timing-constrained global routing algorithm by experimental results on industrial chips.

We present a primal-dual approximation algorithm for minimizing the leakage power of an integrated circuit by assigning gate threshold voltages. While most existing techniques do not provide a performance guarantee, we prove an upper bound on the power consumption. The algorithm is practical and works with an industrial sign-off timer. It can be used for post-routing power reduction or for optimizing leakage power throughout the design flow. We demonstrate the practical performance on recent microprocessor units. Our implementation obtains significant leakage power reductions of up to 8% on top of one of the most successful algorithms for gate sizing and threshold voltage optimization. After timing-aware global routing, we achieve leakage power reductions of up to 34%.

We present local search algorithms for timing-driven placement optimization. They find local slack optima for cells under arbitrary delay models and can be applied late in the design flow.

We show how to incorporate global static timing constraints into global routing. Our approach is based on the min-max resource sharing model that proved successful for global routing in theory and practice. Static timing constraints are modeled by a linear number of additional resources and customers. The algorithm dynamically adjusts delay budgets and can, thus, trade off wiring congestion for delay. The approach works for many delay models. As a subroutine, the algorithm routes a single net. If this subroutine is near-optimal, we will find near-optimal solutions for the overall problem very efficiently. We demonstrate the benefit of our timing-driven global routing algorithm by experimental results on industrial chips.

We present an algorithm which permutes latch positions and sizes within a clock cluster to maximize the worst slack. It preserves the clock footprint and routing, and can therefore be applied late in the design flow after clock network design.

We study the minimum rectilinear Steiner tree problem in the presence of obstacles. Traversing obstacles is not strictly forbidden, but the total length of each connected component in the intersection of the tree with the interior of the blocked area is bounded by a constant.

Today, many chips are designed with predefined discrete cell libraries. In this paper we present a new fast gate sizing algorithm that works natively with discrete cell choices and realistic timing models. The approach iteratively assigns signal slew targets to all source pins of the chip and chooses discrete layouts of minimum size preserving the slew targets. Using slew targets instead of delay budgets, accurate estimates for the input slews are available during the sizing step. Slew targets are updated by an estimate of the local slew gradient. To demonstrate the effectiveness, we propose a new heuristic to estimate lower bounds for the worst path delay. On average, we violate these bounds by 6%. A subsequent local search decreases this gap quickly to 2%. This two-stage approach is capable of sizing designs with more than 5.8 million cells within 2.5 hours and thus helping to decrease turn-around times of multi-million cell designs.

We present a very fast algorithm for buffering repeater trees. We scan a given preliminary topology in a bottom-up fashion and insert buffers and inverters, respecting the parities of the sinks. Information obtained by preprocessing allows for very fast decisions. To bound the number of shielding repeaters, they are only used where necessary to maximize the worst slack. Furthermore, instead of using a fixed set of repeater positions, they are computed on the fly based on the already buffered subtrees. Another key feature of our algorithm is that we modify the preliminary topology while buffering in order to avoid parallel wires or too many inverters.

We present a very fast algorithm for topology generation of repeater trees. Based on the criticality of the individual sinks, which is estimated taking their required signal arrival times and their distance from the root of the repeater tree into account, this topology connects very critical sinks in such a way as to maximize the minimum slack and to minimize wiring for non-critical sinks.We establish theoretical bounds on the optimum solution and prove that our algorithm produces results that are close to optimum with respect to slack and wirelength. Experimental results on industrial designs in 130 nm and 90 nm technologies demonstrate the excellent quality of our algorithm. Moreover, one million nontrivial repeater tree topologies are constructed in less than one minute of computing time.