Floating Node Reduction Using Random Walk Method

摘要

A method for floating node reduction uses a capacitance matrix that specifies coupling capacitances between signal nodes and floating nodes of an interconnect structure. Random walks are performed from a first signal node to the other signal nodes, wherein each of the random walks traverses one or more of the floating nodes. Each of the random walks is directed based on probabilities derived from the coupling capacitances of the capacitance matrix. A count is maintained for each of the other signal nodes, wherein each count specifies a number of the random walks that end on the corresponding signal node. The indirect coupling capacitance from the first signal node to a second signal node is selected to correspond with the total indirect coupling capacitance of the first signal node, times the count associated with the second signal node, divided by the total number of random walks.