出版社：University of Malaya * Faculty of Computer Science and Information Technology
摘要：In this paper, we describe a routing optimization algorithm based on gridgraphs for application in a deepsubmicron VLSI layout design. The proposed algorithm, named SRABILA (for Simultaneous Routing and Buffer Insertion with LookAhead), 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 wiresizing, 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 lookahead 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 lookahead scheme and indicate that SRABILA provides significant performance improvements over similar existing VLSI routing algorithms.
