Via design rule consideration in multilayer maze routing algorithms

Maze routing algorithms are widely used for finding an optimal path in deta iled routing for very large scale integration, printed circuit board and mu ltichip modules In this paper, me show that finding an optimal route of a t wo-pin net in a multilayer routing environment under practical via design r ules can be surprisingly difficult, A straightforward extension to the maze routing algorithm that disallows via-rule incorrect routes may either caus e a suboptimal route to be found, or more seriously, cause the failure to f ind any route even if one exists, We present a refined heuristic to this pr oblem by embedding the distance to the most recently placed via in an exten ded connection graph so that the maze routing algorithm has a higher chance of finding a via-rule correct optimum path in the extended connection grap h. We further present efficient data-structures to implement the maze routi ng algorithm without the need to preconstruct the extended connection graph , Experimental results confirmed the usefulness of our algorithm and its ap plicability to a wide range of CMOS technologies.