Print

Guzowski, Matthew Thomas

Computer Science

2004

M.S.

An ASIC (Application Specific Integrated Circuit) is made up of two main components, the image and the package. The image is the part of the chip that contains the circuitry and the package is the larger, ceramic part of the chip that interfaces with the image. The image contains a set of IOs (input/output) called pins and the package contains a set of IOs called ports. During the chip design process, the image pins need to be wired to the package ports with straight wires called nets. The auto assign problem is the problem of finding a set of nets in a time efficient manner that wires the maximum number of image pins to package ports and contains the minimum number of crossovers. A greedy algorithm was originally implemented to solve the auto assign problem and, although fast, produced results with many crossovers. In this thesis, we present an improved approximation method for the auto assign problem that is time efficient and results in fewer crossovers than the greedy algorithm. We analyze the algorithm based on empirical results and examine some interesting cases such as the minimum number of crossovers possible and the maximum number of pins that can be assigned for a given ASIC.