Authors

Published On 02/01/1995 09:00 AM

Department Computer Engineering

Abstract This paper look at the problem of assigning pins and generating a planar topological routing for a pin grid array package. There is a freedom of assigning any pin to any pad but the routing resource is more limited. We showed that a monotonic pin assignment has no detours and has one and only one monotonic topological routing. We proposed an algorithm (EVENPGA) that generates this type of topological routing. In addition, EVENPGA creates the optimal uniform distribution of wires and shortest wire length possible for all wires under the taxicab wiring metric. If the topological routing is routable, the maximum density of critical cuts along a ring is the minimum theoretically possible. Once the topological routing is done, physical layout can easily be obtained using Surf, a rubberband-based routing system.

Download

UCSC-CRL-95-15