VIA design rule consideration in multi-layer maze routing algorithms
Jason Cong, Jie Fang, Kei-Yong Khoo · 1999
Maze routing algorithms are widely used for finding an optimal path in detailed routing for VLSI, PCB and MCMs.In this paper, we show that finding an optimal route of a two-pin net in a multi-layer routing environment under practical via design rules can be surprisely difficult.Furthermore, a straightforward extension to the maze routing algorithm that disallows via-rule incorrect routes may either cause a suboptimal route to be found, or more seriously, cause the failure to find any route even if one exists.We present a refined heuristic to this problem by embedding the distance to the most recently placed via in an extended connection graph so that the maze routing algorithm has a higher chance of finding a via-rule correct optimum path in the extended connection graph.We further present efficient data-structures to implement the maze routing algorithm without the need to preconstruct the extended connection graph.Experimental results confirmed the usefulness of our algorithm and its applicability to a wide range of CMOS technologies.