An interactive maze router with hints

The authors present the Irouter, an interactive maze router for the Magic IC layout editor that takes hints. The Irouter is a flexible tool intended to be useful wherever tight or unusual constraints do not permit automatic routing. It has already been used in the layout of an 80000-transistor CMOS chip and is currently being used to route the control signals of a 100000 transistor, high-performance FPU (floating-point unit) chip. Several novel ideas for maze routing have been developed in the Irouter. Hint layers permit the user to map out the general path of a route and pull the route in desired directions, while leaving details to the router. The gross structure of the layout is preprocessed to facilitate accurate estimates of cost to completion during routing and hence effective pruning of misdirected partial routes. A windowed search strategy slowly shifts the focus from the start point towards the goal. This permits the consideration of alternatives at all stages of routing without blowing up into an exhaustive search.<>