Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Placing Circuits on a LSI Chip

IP.com Disclosure Number: IPCOM000084156D
Original Publication Date: 1975-Sep-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 29K

Publishing Venue

IBM

Related People

Agule, BJ: AUTHOR [+4]

Abstract

This description relates to a method referred to as the force directed technique, embodied as a computer algorithm, which places circuits on a large-scale integrated (LSI) chip in less time and with smaller estimated wire length than the standard pairwise interchange technique.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

Placing Circuits on a LSI Chip

This description relates to a method referred to as the force directed technique, embodied as a computer algorithm, which places circuits on a large- scale integrated (LSI) chip in less time and with smaller estimated wire length than the standard pairwise interchange technique.

The placement of many circuits on an LSI chip will be a reality in the near future. Present placement algorithms are either too time consuming or do not yield good results. The method and algorithm described employs some known techniques which when used individually, do not satisfy the criterion of good results in reasonable computation time, but when combined in the fashion described does satisfy this criterion.

The main components of the algorithm are the force-directed pairwise interchange (FDPI) algorithm and a new transformation of the placement problem to the associated quadratic assignment problem. The force-directed pairwise interchange algorithm is described elsewhere (2). The concept of transforming the placement problem to an associated quadratic assignment problem is discussed in (1). The transformation used in this method, however, yields considerably better results than the standard transformation of (1). The reason for transforming the placement problem to an associated quadratic assignment problem is the savings in computation time this affords.

The transformation assigns a value C(ij) to every pair of blocks (i,j) in the graph. The standard transformation chooses C(ij) = number of nets common to i and j. The new transformation chooses:

(Image Omitted)

where S(k) = number...