Browse Prior Art Database

Optimized Package I/O Assignment

IP.com Disclosure Number: IPCOM000108741D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 75K

Publishing Venue

IBM

Related People

Broker, HJ: AUTHOR

Abstract

Disclosed is an algorithm for optimizing package I/O pin assignment. As presented, the algorithm minimizes the total wire length for all package I/O nets. Any metric such as net delay could be used, but it is assumed that minimizing the length will in turn minimize most applicable metrics.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 55% of the total text.

Optimized Package I/O Assignment

       Disclosed is an algorithm for optimizing package I/O pin
assignment.  As presented, the algorithm minimizes the total wire
length for all package I/O nets.  Any metric such as net delay could
be used, but it is assumed that minimizing the length will in turn
minimize most applicable metrics.

      The algorithm presented in flowchart form in the figure is
iterative and greedy.  It tries to establish a connection between a
given component (chip) pin and the closest package I/O.  If the
desired package I/O is available, the assignment is made and the
algorithm moves on to consider the next component I/O needing a
package I/O.  Conversely, if the desired package I/O has already been
assigned to another component pin, a test is performed to see if the
total wire required to wire BOTH connections can be reduced by
breaking the existing connection and assigning that particular
package I/O to the chip pin currently under consideration.  If so,
the new assignment is made.  If not, the existing connection remains
and the assignment of the component pin under consideration to the
next closest package I/O is examined in the same way.  Since there
must be more pins available on the package than there are signals
requiring them, the proof of termination of the iterations is that
eventually a package I/O will be found that has not been assigned yet
allowing its assignment to the chip pin under consideration.

      Let A be th...