An Optimization Algorithm Based On Grid-Graphs For Minimizing Interconnect Delay In VLSI Layout Design

Abstract

In this paper, we describe a routing optimization algorithm based on grid-graphs for application in a deep-submicron VLSI layout design. The proposed algorithm, named S-RABILA (for Simultaneous Routing and Buffer Insertion with Look-Ahead), constructs a maze routing path, simultaneously with buffer insertion and wire sizing, taking into account wire and buffer obstacles, such that the interconnect delay from source to sink is minimized. In current nanometer VLSI layout design, the interconnect delay has become the dominant factor affecting system performance. Research has shown that routing algorithms, which include simultaneous buffer insertion and wire-sizing, have been proven to be very effective in solving the timing optimization problem in VLSI interconnect design. A key contribution of this work is a novel look-ahead scheme applied to speed up the runtime of the algorithm, and aids in finding the exact solution. Hence, the algorithm is accurate, fast, scalable with problem size, and can handle large routing graphs. Experimental results show the effectiveness of the look-ahead scheme and indicate that S-RABILA provides significant performance improvements over similar existing VLSI routing algorithms.