Method for automatic iterative area placement of module cells in an integrated circuit layout

• US 5,847,965 A
• Filed: 08/02/1996
• Issued: 12/08/1998
• Est. Priority Date: 08/02/1996
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: Avant! Corporation (Synopsys Incorporated)
• Inventors: Cheng, Chih-liang Eric
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/691,607
• Time in Patent Office: 858 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

In a computer system, a method for an area based place and route of an integrated circuit layout that provides automatic iterative area placement of module cells intelligently and effectively. In one embodiment, this is accomplished in three phases. The searching phase determines which hot spot is to be refined based on a congestion map. Next, the refining phase chooses a box with the proper aspect ratio, cut line direction, and placement options for minimizing the hot spot. The scheduling phase then decides whether to proceed with another area placement based on the current result or to restore a previous placement that exhibited superior characteristics. In the course of the area placements, several parameters are randomly varied in an intelligent manner so that successive iterative area placements produce equivalent or better results. All of this is accomplished without human intervention or expert knowledge. Instead, the computer system continuously runs its program until a design goal is attained.

Claims

1. A computer-implemented automation tool for automatic area placement in designing circuit layouts for semiconductor integrated circuits, comprising:

a computer platform for processing a plurality of program execution modules which accept a set of placement options and initial conditions related to a semiconductor integrated circuit design, computes an area placement solution, and that outputs a completed layout that is used as a guide for the fabrication of a semiconductor integrated circuit;

a first computer process for searching in an area-placement-solution computation for a hot-spot candidate with a relatively high concentration of overlapping connections for further refining, and for loading and execution on the computer platform as one of said program execution modules;

a second computer process for refining said hot-spot candidate by matching it with an area box having a particular combination of aspect ratio, cut-line direction, and placement options, and for loading and execution on the computer platform as one of said program execution modules; and

a third computer process connected to receive a plurality of refined ones of said hot-spot candidates, for scheduling area-placement-solution-computation repetitions, and for loading and execution on the computer platform as one of said program execution modules.

2. A computer-implemented automation tool for automatic area placement in designing circuit layouts for semiconductor integrated circuits, comprising:

a placement engine that calls for horizontal cuts to reduce vertical congestion and vertical cuts to reduce horizontal congestion, and providing for a generating of a plurality of placement congestion maps for a circuit layout for a semiconductor integrated circuit, wherein each of said placement congestion maps is a two-dimensional routing display for a particular placement and contains both vertical and horizontal routing congestion information;

a search mechanism providing for an identification within said plurality of placement congestion maps of a target hot-spot candidate with a relatively high concentration of overlapping connections;

a refining mechanism providing for a refined target hot-spot from said identified target hot-spot candidate and a surrounding adjacent area; and

a scheduling mechanism providing for a decision whether to proceed with a placement solution that includes said refined target hot-spot candidate and then repeat, or to restore a previous placement solution and then repeat, and wherein said decision is based on at least one of a count of a number of iterations, a run-time limit, and an attained placement goal.

3. The automation tool of claim 2, wherein:

the search mechanism further provides for partitioning a core area into a two-dimensional array of grids that are randomly sized within a design-dependent range to vary a cut line location, and that each contain an N×

M array of routing tracks; and

the search mechanism also provides for a grid map comprising said two-dimensional array of grids that is overlapped on top of at least one of said plurality of placement congestion maps to judge if any grid includes a hot-grid that is defined to be one that exceeds a congestion-threshold variable.

4. The automation tool of claim 3, wherein:

the search mechanism further provides for finding a plurality of hot-spots by grouping for each a plurality of said hot-grids that abut one another on a boundary edge.

5. The automation tool of claim 2, wherein:

the refining mechanism further includes determining a first and a second cut-line direction, and finding an area box to contain said target hot-spot;

wherein, said first and a second cut-line directions are each determined by analyzing a target hot-spot to determine a more-congested direction; and

wherein, said area box is determined by starting with initial area box equal to a bounding box for a hot spot, and

adjusting for a first cut at least one of a height (X) and a width (Y) dimension of said initial area box to achieve a first particular aspect ratio of said width and a height dimensions (R=Y/X), and

if a first and a second cut are in a same direction, adjusting for at least one of a height (X) and a width (Y) dimension of said initial area box to achieve a second particular aspect ratio of said width and a height dimensions (R=Y/X).

6. The automation tool of claim 5, wherein:

the refining mechanism further includes additional expansion of said initial area box if;

more than half of all grids in a current area box are hot grids;

there is an average overflow of more than two tracks for each global routing cell in a grid;

a current area box is smaller than half of said core box in two dimensions;

or

there is at least twenty percent random chance to expand said initial area box;

wherein, an objective of an area box adjustment is centered at the target hot spot. If the selected area box is not fully inside the core area box, the area box is shifted such that it is fully inside the core area box.

7. The automation tool of claim 2, wherein:

the searching mechanism further provides for a comparison between a current placement and at least one previous placement, and that then provides for a retention of one of said current and previous placements as being a best placement depending on a total global-routing-cell overflow value associated with each placement when a congestion map is processed.

8. A computer-implemented method for automatic area placement in designing circuit layouts for semiconductor integrated circuits, comprising the steps of:

computer processing a plurality of program execution modules which accept a set of placement options and initial conditions related to a semiconductor integrated circuit design, and that then compute an area placement solution, and output a completed layout for use as a fabrication guide for a semiconductor integrated circuit;

using one of one of said program execution modules to search in an area-placement-solution computation for a hot-spot candidate with a relatively high concentration of overlapping connections for further refining;

using one of one of said program execution modules to refine said hot-spot candidate by matching it with an area box having a particular combination of aspect ratio, cut-line direction, and placement options; and

using one of one of said program execution modules to receive a plurality of refined ones of said hot-spot candidates and schedule area-placement-solution-computation repetitions.