General gate array routing using a k-terminal net routing algorithmwith failure prediction

A general approach to gate array routing based on an abstract routing space model is presented. An efficient k-terminal net maze runner is described. It does not partition nets into two-terminal net routing problems, but solves the problem by simultaneously growing k search waves. It is shown that the explored routing space diminishes when compared to bidirectional routing schemes. Experimental data show a reduction of CPU time up to 55% and a decrease of total net length up to 6% compared to a bidirectional maze router. For k-terminal nets it is shown that net length decreases with increasing k. Additional routing space restriction is attained by use of variable search space restriction and by the introduction of a dynamic routing space partitioning method based on the concept of regions. This concept allows for determination of nonroutable nets or parts of nets in an efficient way. The new partitioning method may be implemented in any maze runner without increasing the complexity of the maze runner algorithm. Results show an additional decrease of CPU time up to 35%