Global Timing Optimization in Chip Design

Abstract

In this thesis, we aim at solving the interconnect optimization problem comprehensively. By balancing global timing, routing, placement, and power constraints in a global model, we obtain solutions which outperform the classic approach in both resource usage and timing quality. <br /> For the time-cost tradeoff problem in chip design, we present a new implementation of a primal-dual optimization algorithm. Instead of requiring separable delay constraints as in previous approaches, it only has mild assumptions on the delay model. The approach allows us to achieve leakage reductions of up to 8% on netlists that were pre-optimized by one of the most successful algorithms. <br /> The Vt assignment problem with separable delays directly corresponds to the discrete time-cost tradeoff problem in directed graphs. If d is the maximum number of vertices in any path, our practical algorithm yields a d approximation. Previously, Svensson showed that for general instances with unbounded values of d no constant factor approximation exists if we assume P&ne;NP and the Unique Games Conjecture holds. For the discrete time-cost tradeoff problem, we devise an improved algorithm with a guarantee of d/2. We achieve this by reformulating the problem to a vertex cover problem in d-partite hypergraphs. For this more general problem, the approximation ratio of our new algorithm is slightly better than d/2, which is asymptotically best possible under the Unique Games Conjecture and P&ne;NP. We also study the inapproximability of the time-cost tradeoff problem and show that no better approximation ratio than (d+2)/4 is possible, again assuming the Unique Games Conjecture and P&ne;NP. Therefore, we settle the approximability of this problem up to a factor of less than 2. <br /> We then focus on the gate sizing problem. It is similar to the time-cost tradeoff problem but optimizes a more involved timing function, which is not linear but only posynomial. Schorr presented a resource-sharing formulation for the gate sizing problem in her dissertation. We give a new runtime analysis for the resource sharing algorithm applied to gate sizing, resolving small inaccuracies in the previous proof. <br /> Finally, we consider the buffering problem. In this problem the interconnect for all nets should be computed. Simultaneously, repeating gates need to be inserted to strengthen electrical signals. We build on the resource sharing formulation for this problem given by Rotter and his initial implementation. On the theoretic side, we modify the model by using a path based formulation for timing proposed by Hähnle. The new implementation is now robust enough to be used in an industrial environment. It outperforms a state-of-the-art design flow in almost all metrics, including netlength, power, congestion and timing. We also implement speedups that reduce the runtime by up to 70%.