Logic cell placement method in computer-aided-customization of universal arrays and resulting integrated circuit

• US 4,686,629 A
• Filed: 07/21/1986
• Issued: 08/11/1987
• Est. Priority Date: 05/10/1984
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: RCA Corporation (General Electric Company)
• Inventors: Smith, David C., Noto, Richard
• Primary Examiner(s): Lall, Parshotam S.
• Application Number:
  US06/886,936
• Time in Patent Office: 386 Days
• Field of Search: 364/488, 364/489, 364/491, 364/300, 357/45, 29/846-848, 174/68.5
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: Y10S 257/923 with means to optimize electrical conductor current carrying capacity, e.g. particular conductor aspect ratio

Abstract

An improved automatic placement process for placing logic cells in a universal array. Unused basic units are assigned to rows to reduce the congestion of the wiring in high congestion regions of a universal array. These assigned unused basic units are allocated among rows in a pyramidal manner. Those unused basic units allocated to a given row are distributed along that row in a manner to reduce wiring congestion. During a pair exchange portion of the placement process, quality criteria used for deciding whether to exchange two logic cells on different rows include skipped rows in a node, y-span of a node, minimizing the number of logic cells in excess of two in a node on a row, making a longest row shorter and making longer a shortest row or one which is within a tolerance of being a shortest row.

Claims

1. In a computer-programmed method of placing logic cells during the conversion of a universal array having a row region including rows of basic circuit units into a custom IC in which said array has more of said basic units in its row region than said IC requires for it'"'"'s implementation whereby the final IC includes some unused basic units, the improvement comprising the step of:

allocating at least some of said unused basic units to specific rows of said row region with the center row when there are an odd number of rows and one of the center two rows when there are an even number of rows being allocated the most unused basic units and with the number of unsed basic units allocated to said rows decreasing monotonically with the distance from said center row(s); and

preventing said allocated unused basic units from being moved from the respective rows to which they are allocated.

2. The method recited in claim 1 wherein said allocating step allocates fewer unsused basic units to each successive row as the row distance from said center row(s) increases.

3. The method recited in claim 1 further comprising:

exchanging selected pairs of logic cells, while restricting the exchange process to retaining said unused basic units in the rows to which they are allocated.

4. The method recited in claim 1 in which for at least some rows which contain more that one of said unused basic units, the method further comprises the step of:

spacing said unused basic units at intervals along said row.

5. The method recited in claim 4 wherein said spacing step comprises:

restricting each of said spaced apart unused basic units to being within a predetermined number of basic units of an associated fixed point along said row.

6. The method recited in claim 4 wherein said spacing step includes:

dividing a row into at least two sections and distributing said unused basic units among said sections in accordance with an assigned priority; and

distributing along each of said sections those unused basic units assigned to that section.

7. In a computer programmed method for placing logic cells in a universal array having a row region including parallel rows of basic circuit units, the improvement comprising the step of:

establishing for each row, a maximum number of said basic units which are allows to be connected into the IC, said maximum number being equal to the number of said basic units actually present in that row minus a variable number which depends on (1) the location of the row within the row region and (2) the number of said basic units present in the universal array which are unused in the custom circuit being designed, said variable number having its largest value for the center row when the there are an odd number of rows and one of the center two rows when there are an even number of rows in said row region and having a value for other rows which decreaess monotonically with increasing distance of said other rows from said center row(s), the sum of said variable number over all rows being less than or equal to a predetermined portion of said unused basic units.

8. In a method of placing logic cells in a universal array having a row region including parallel rows of basic circuit units in which logic cells are initially assigned to rows and then moved from row to row or pair exchanged in accordance with evaluation criteria which include the number of skipped rows for a node and the number of rows spanned by the node, the improvement comprising:

including in said evaluation criteria the minimization of the number of cells in a node in excess of two on a row.

9. The method recited in claim 8 wherein the minimization of the number of cells in a node in excess of two on a row has a lower priority than either the number of skipped rows or the number of rows spanned by the node.

10. The method recited in claim 9 wherein said method of placing is iterative and allows the rows to have fictitious lengths during part of the iterative process of establishing a preferred final logic cell placement which fits in the actual rows and when none of the three stated criteria provide a basis for choosing between two placements, a preference is given to a placement which shortens a longest row or lengthens a row which is shortest or within a tolerance of being shortest.

11. In a computer programmed method of converting a logic specification for an IC into the mask necessary to convert a universal array into said IC wherein the universal array of of the type which includes pre-placed basic circuit units arranged in parallel rows in a row region and includes more of said basic units than said IC requires for its implementation such that the final IC includes unused basic units, the method being one which (1) automatically determines the placement of logic cells on the rows of the universal array, (2) automatically determines routes for conductors to properly interconnect the universal aray basic units to produce said IC and (3) automatically generates the masks necessary to convert the universal array to said IC, the improvement comprising the step of:

allocating at least some of said unused basic units to specific rows of said row region with the center row when there are an odd number of rows and one of the center two rows when there are an even number of rows being allocated the most unused basic units and with the number of unused basic units allocated to said row decreasing monotonically with the distance from said center row(s); and

preventing said allocated unused basic units from being moved from the respective rows to which they are allocated.

12. A computer programmed method of converting a logic specification for an IC into the mask nessary to convert a universal array into said IC in which said array has a row region including parallel rows of basic circuit units and has more basic units in its row region than said IC requires for it'"'"'s implementation whereby the final IC includes some unused basic units, and wherein said universal array is of the type in which said basic units are pre-placed in parallel rows in said row region, the method comprising the steps of:

(1) assigning specific logic cells to specific rows of said universal array, said assigning step including allocating at least some of said unused basic units to specific rows of said row region with the center row when there are an odd number of rows and one of the center two rows when there are an even number of rows being allocated the most unused basic units and with the number of unused basic units allocated to said rows decreasing monotonically with the distance from said center row(s);

(2) placing said logic cells assigned to each row at specific locations along that row;

(3) routing customizing conductors to properly interconnect said basic units of said universal array to product said IC;

(4) providing an output specifying the configuration of a mask for customizing said universal array to form said IC; and

(5) generating said mask.

13. In a customized universal array IC of the type including a row region in which basic units are arranged in a plurality of parallel rows and in which some of said basic units are active and some are unused, the improvement comprising:

said unused basic units being distrubuted among said rows with the largest number of said unused basic units disposed in the center row when there are an odd number of rows and one of the center two rows when there are an even number of rows and with the number of unused basic units in each row decreasing monotonically with the distance of that row from said center row(s).

14. The IC recited in claim 13 wherein said distribution among said rows is pyramidal with the center row(s) containing the most unused basic units and the outermost rows containing the fewest unused basic units.

15. The IC recited in claim 14 wherein within rows which contain said unused basic units, said unused basic units are interspersed with said active basic units.

16. The IC recited in claim 15 wherein said unused basic units in at least some rows are spaced along at least a portion of said row at substantially constant intervals.