Parametric Pattern Router

This paper presents a new pattern router based on an enumeration scheme which sequentially produces alternative paths for a pin pair. First, we represent a pattern or shape of a route by a sequence of symbols representing directions of constituent line segments. Then, we investigate a condition that a sequence of symbols represents a valid pattern. We also count all valid patterns. Given two points, we can specify any route between them by a pattern of the route and lengths of segments. If we vary their lengths as parameters, then we can generate various routes. Therefore, the parametric pattern router with all possible patterns can always find a path between two points if one exists. The user of the router may define a set of admissible routing patterns according to circumstances.