ASP-DAC 2006 Archives


3C-1
Title Post-Routing Redundant Via Insertion for Yield/Reliability Improvement
Author *Kuang-Yao Lee, Ting-Chi Wang (National Tsing Hua University, Taiwan)
Abstract Reducing the yield loss due to via failure is one of the important problems in design for manufacturability. A well known and highly recommended method to improve via yield/reliability is to add redundant vias. In this paper we study the problem of post-routing redundant via insertion and formulate it as a maximum independent set (MIS) problem. We present an efficient graph construction algorithm to model the problem, and an effective MIS heuristic to solve the problem. The experimental results show that our MIS heuristic inserts more redundant vias and distributes them more uniformly among via layers than a commercial tool and an existing method. The number of inserted redundant vias can be increased by up to 21.24%. Besides, since redundant vias can be classified into on-track and off-track ones, and on-track ones have better electrical properties, we also present two methods (one is modified from the MIS heuristic, and the other is applied as a post processor) to increase the amount of on-track redundant vias. The experimental results indicate that both methods perform very well.
Slides (pdf file) 3C-1


3C-2
Title Temperature-Aware Routing in 3D ICs
Author Tianpei Zhang, *Yong Zhan, Sachin S. Sapatnekar (University of Minnesota, United States)
Abstract Three-dimensional integrated circuits (3D ICs) provide an attractive solution for improving circuit performance. Such solutions must be embedded in an electrothermally-conscious design methodology, since 3D ICs generate a significant amount of heat per unit volume. In this paper, we propose a temperature-aware 3D global routing algorithm with insertion of "thermal vias” and "thermal wires” to lower the effective thermal resistance of the material, thereby reducing chip temperature. Since thermal vias and thermal wires take up lateral routing space, our algorithm utilizes sensitivity analysis to judiciously allocate their usage, and iteratively resolve contention between routing and thermal vias and thermal wires. Experimental results show that our routing algorithm can effectively reduce the peak temperature and alleviate routing congestion.
Slides (pdf file) 3C-2


3C-3
Title Closed Form Solution for Optimal Buffer Sizing Using The Weierstrass Elliptic Function
Author Sebastian Vogel (Darmstadt University of Technology, Germany), *Martin D.F. Wong (University of Illinois at Urbana-Champaign, United States)
Abstract This paper presents a fundamental result on buffer sizing. Given an interconnection wire with n buffers evenly spaced along the wire, we wouldlike to size all buffers such that the Elmore delay is minimized. It is well known that the problem can be solved by an iterative algorithm which size one buffer at a time. However, no closed form solution has ever been reported. In this paper, we derive a closed form buffer sizing function f(x), where f(x) gives the optimal buffer size for the buffer at position x. We show that f(x) can be expressed in terms of the Weierstrass elliptic function p(x) and its derivative p'(x).
Slides (pdf file) 3C-3


3C-4
Title An O(mn) Time Algorithm for Optimal Buffer Insertion of Nets with m Sinks
Author *Zhuo Robert Li, Weiping Shi (Texas A&M University, United States)
Abstract Buffer insertion is an effective technique to reduce interconnect delay. In this paper, we give a simple $O(mn)$ time algorithm for optimal buffer insertion, where $m$ is the number of sinks and $n$ is the number of buffer positions. This is the first linear time buffer insertion algorithm for nets with constant number of sinks. When $m$ is small, it is a significant improvement over our recent $O(n\log^2 n)$ time algorithm, and the $O(n^2)$ time algorithm of van Ginneken. For $b$ buffer types, the new algorithm runs in $O(b^2n+bmn)$ time, an improvement of our recent $O(bn^2)$ algorithm. The improvement is made possible by a clever bookkeeping method and an innovative linked list data structure that can perform addition of a wire, and addition of a buffer in amortized $O(1)$ time. On industrial test cases, the new algorithm is faster than previous best algorithms by an order of magnitude.
Slides (pdf file) 3C-4


3C-5
Title Spec-based Flip-Flop and Latch Repeater Planning
Author *Man Chung Hon (Intel Corporation, United States)
Abstract Shrinking process geometries and frequency scaling give rise to an increasing number of interconnects that require multiple clock cycles. This paper explores efficient techniques to insert flip-flops and latches to meet pre-determined latency and margin constraints at the receivers. Previous approaches push timing margins to either ends of interconnect. We present an $O(n \log n)$-time algorithm to insert flip-flops that evens out timing margins across the entire interconnect, resulting in more robust designs and faster design convergence. An $O(n \log n)$-time extension to handle symmetric, two-phases latches is also presented. Experimental results verify the correctness and practicality of our approach.
Slides (pdf file) 3C-5