This paper presents 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 80,000 transistor CNOS chip developed by our group at LLNL, and is currently being used to route the control signals of a 100,000 transistor, high performance, EPU chip being developed by the Berkeley SPUR project. 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 detail, such as obeying the design rules, 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. (ERA citation 13:037395)
展开▼