page 1  (20 pages)
2to next section

Pin Assignment and Routing on a
Single-Layer Pin Grid Array

Man-fai Yu
Wayne Wei-Ming Dai

February 24, 1995

For Submission to ASPDAC'95

Board of Studies in Computer Engineering
University of California, Santa Cruz
Santa Cruz, CA 95064
Phone: +1 (408)459-4954 or +1 (408)459-4234
Fax: +1 (408)459-4829
e-mail: or

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.

Keywords: package routing, pin grid array, planar routing, routability, even wiring