AN EFFICIENT MULTILAYER DIAGONAL ROUTER FOR MULTITERMINAL PRINTED-CIRCUIT BOARDS

This paper presents a grid-based multi-layer, multi-terminal autoroute r with the unique feature of diagonal routing. The router is suitable for routing memory boards and highly congested printed circuit boards. Diagonal routing is extremely useful in minimizing vias and in obtain ing a high rate of completion with total route length reduced by up to 20% comparatively. The router employs an improved maze algorithm to i ncorporate multi-layer diagonal routing. The cost function used in the algorithm is complicated, but can be easily modified to meet specific needs. The algorithm models multi-terminal routing as a minimum spann ing tree problem to use the least amount of wiring which is most desir able in the electronic industry. Intelligent net ordering and dynamic data structures reduce memory requirement and total route time by up t o 30% compared to recently developed routers. The algorithm described in this paper was extensively tested against standard benchmarks and v ery inspiring results were achieved.