Browse Prior Art Database

Multiple Column Automatic Placement Program

IP.com Disclosure Number: IPCOM000082563D
Original Publication Date: 1974-Dec-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Dunham, B: AUTHOR [+3]

Abstract

In Defensive Publication Article T918,014, Official Gazette of the U. S. Patent Office, January 22, 1974, pp. 1329-1330, a design automation method is set forth suitable for efficient ordering of circuits in a column. The method is based upon a progressive scoring mechanism for a method is set forth suitable for efficient ordering of circuits in a column. The method is based upon a progressive scoring mechanism for a "natural selection" design automation process. An exemplary automatic natural selection process is disclosed in the publication entitled "Design by Natural Selection", by B. Dunham et al, June 1961, RC #476 available from IBM T. J. Watson Research Center, Yorktown Heights, New York.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 40% of the total text.

Page 1 of 3

Multiple Column Automatic Placement Program

In Defensive Publication Article T918,014, Official Gazette of the U. S. Patent Office, January 22, 1974, pp. 1329-1330, a design automation method is set forth suitable for efficient ordering of circuits in a column. The method is based upon a progressive scoring mechanism for a method is set forth suitable for efficient ordering of circuits in a column. The method is based upon a progressive scoring mechanism for a "natural selection" design automation process. An exemplary automatic natural selection process is disclosed in the publication entitled "Design by Natural Selection", by B. Dunham et al, June 1961, RC #476 available from IBM T. J. Watson Research Center, Yorktown Heights, New York.

Article T918,014 notes that "by dividing what is scored by the optimization process at a given stage on what is defined as a 'care' 'don't care' basis, the program can focus attention on most troublesome points without prematurely building in structure elsewhere. At a next stage, some of the material previously treated as 'don't care' is now treated as 'care'. Thus the method can proceed through a sequence of stages progressively dealing with more and more of the content of the problem, until an appropriate stopping point is reached. In this way, not only can worst peaks be directly attacked, but also lesser peaks and valleys can be treated in due course".

Suppose a problem is presented in which there are a number of parallel columns, as, for example, in IBM field-effect transistor (FET) logic chips, which have been used in many commercial applications. Logical wire routing within a column is almost all on a given physical plane. Connections between columns normally require appropriate nodes at the edges of columns, although not always. Suppose a particular net connects the output of a given circuit in column A to various logic nodes in column B. If the line between columns enters column A at the same column height as the circuit just mentioned, no side connection point in column A is required. Also, no side connection point is required in a column where a line enters the line at a height which has been left "blank", in the sense that the transverse space perpendicularly across the column has not been used for other logic purposes.

Although placement of circuits within a column of an FET logic chip has been accomplished automatically in the manner described in Article T918,014, nevertheless the ability to do each column efficiently by automatic means still has meant that the dependency of one column's solution upon that of its neighbors could only be used in a single direction, i.e., for example, if column 2 and column 3 were strongly interconnected, it is necessary to do either 2 or 3 independently, and only then solve the other column dependent on the first solution. This tends to make the latter solution less efficient than the former. Also the exact location of crossover points between column...