BACKGROUND:  As chip clock rates have continued to increase and chip density has become tighter, the challenges associated with VLSI routing have become more burdensome. Long trace routes can lead to degraded signal quality and reduced chip performance. While various place and route tools exist to assist with and to optimize VLSI routing, none exploit the capabilities of the inventions disclosed here. Specifically, it has been shown that use of the heuristic algorithms presented here result in the shortest routing traces. Furthermore, optimal routing solutions are achieved in much less time when using the disclosed algorithms. Consequently, VLSI routes can be made shorter, which results in better chip performance, and VLSI designers can optimize their chips more quickly, which shortens product time to market.

INNOVATION:  Routing tree construction is one of the major tasks in the VLSI routing phase. When wirelength is of interest, routing is in essence an RSMT (Rectilinear Steiner Minimum Tree) construction problem on a given terminal set. The invention disclosed here presents a new obstacle-avoiding RSMT heuristic algorithm based on a current driven circuit (CDC) model. The CDC model comes from the topology of an escape graph, in which each routing edge is replaced by a resistor indicating the wirelength of that edge. By performing DC analysis on the circuit and selecting the edges according to the current distribution, the wirelength of the resulting tree is made to be as short as possible.

The invention also presents a new routing technique based on RC networks with terminals as inputs. By minimizing the rise and fall times of the RC network, it is ensured that the shortest trace lengths are achieved. Compared to existing algorithms, those disclosed here have the best wirelength and runtime for obstacle-free and/or obstacle-avoiding routing, compared to the published results in the literature.

POTENTIAL APPLICATIONS 

• Computer aided design, electronic design automation, and place and route tools

ADVANTAGES

• Improved VLSI chip performance
• Higher chip data rates
• Shorter time to market
• Reduced optimization run time

DEVELOPMENT-TO-DATE:  The inventions have been proven and implemented in software.

Reference: UCLA Case Nos. 2007-393; 2007-395