Curvilinear detailed routing algorithm and its extension to wire-spreading and wire-fattening

Abstract — This article describes an algorithm for curvilinear detailed routing. We significantly improved the average time per-formance of Gao’s algorithm by resolving its bottleneck related to generation of fan-shaped forbidden regions along a wire. We also describe a method for simultaneous wire-spreading and wire-fattening, which consists of enlarging forbidden regions gener-ated by the detailed routing algorithm as long as there remains any space through which wires can pass. From the experiments we obtained the result that the average CPU time of the detailed routing algorithm is almost linear to the length of a wire. Since the curvilinear detailed routing is efficient in terms of space usage, the proposed algorithm is important especially for densely wired printed circuit boards such as PGA packages, BGA packages, and MCMs. We can also expect improvements on the electrical char-acteristics and the production yield by applying wire-spreading and wire-fattening to them. I