Logic cell placement method for semiconductor integrated circuit

• US 5,222,031 A
• Filed: 02/20/1991
• Issued: 06/22/1993
• Est. Priority Date: 02/21/1990
• Status: Expired due to Term

• Current Assignee: Toshiba Corporation
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Kaida, Hiromasa
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/658,406
• Time in Patent Office: 853 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

A logic cell placement method for a semiconductor circuit includes a cluster pair generating and calculating step for forming a cluster pair made up of any two clusters when there are more than three clusters, each of which comprises at least one logic cell. The calculating method includes estimate values of each cluster pair by using estimate functions based on a congestion rate of the number of wirings on the cluster pair. The method also includes an upper limit setting step for calculating cost values by using the estimate values for each cluster pair, mean values of the cost values and the estimate values for the whole cluster pairs, then setting the upper limit of for each estimate value obtained by using the mean values of the estimate values. A selecting step selects the cluster pair having the smallest cost value. A calculating step calculates estimate values of the cluster pair having the smallest cost value by using the estimate functions based on the congestion rate of the number of wirings, a clustering step for clustering the pair into one cluster when all of the estimate values of the cluster pair having the smallest cost value are less than the upper limits thereof. The current process is returned into the selecting step when there are two clusters which are not handled by the clustering step. The current process is returned into the cluster pair generating and calculating step when a terminate condition for the logic cell placement method is not satisfied.

Claims

1. A logic cell placement method for arranging clusters on a semiconductor circuit, each cluster having at least one logic cell, the method being implemented by a computer aided design system, comprising the steps of:

(a) forming pairs of clusters when there are more than three clusters, each cluster having at least one logic cell, and determining estimate values of each cluster pair by using estimate functions based on a congestion rate of the number of wirings on said cluster pairs;

(b) determining cost values using said estimate values for each said pair of clusters, determining mean values of the cost values and estimate values for all said cluster pairs, then setting an upper limit for each estimate value obtained using said mean values of said estimate values;

(c) selecting the cluster pair having the smallest cost value;

(d) determining estimate values of the cluster pair having the smallest cost value by using said estimate functions based on said congestion rate of the number of wirings;

(e) clustering said cluster pair having the smallest cost value into one cluster when all of the estimate values of said cluster pair having the smallest cost value are less than upper limits thereof;

(f) returning to step (c) when there are at least two clusters which are not clustered into said one cluster in step (e);

(g) returning to step (a) when a terminate condition for said logic cell placement is not satisfied.

2. A logic cell placement method according to claim 1, wherein a connection strength of each cluster pair, the number of terminals of each cluster pair, the number of wirings which can e wired on the logic cells of each cluster pair, and a sum of values increasing in accordance with an increase of the area in the cluster pair are used as the estimate functions based on the congested rate of the number of wirings.

3. A logic cell placement method for arranging clusters, each cluster having at least one logic cell on a chip of a semiconductor integrated circuit, the method being used for a computed aided semiconductor design process and comprising:

a cluster pair generating and calculating step for forming a pair of clusters when there are more than three clusters, each cluster having at least one logic cell, and for calculating estimate values of each cluster pair by using estimate functions based on a congestion rate of the number of wirings on the cluster pair;

an upper limit setting step for calculating and storing in the computer cost values by using the estimate values for each cluster pair, mean values of the cost values and the estimate values for all the cluster pairs, and an upper limit for each estimate value obtained by using the mean values of the estimate values;

a calculating step for calculating estimate values of the cluster pair having the smallest cost value stored in the computer by using the estimate functions based on the congestion rate of the number of wirings;

a clustering step for clustering the pair of clusters into a new cluster when all of the estimate values of the pair of clusters having the smallest cost value stored in the computer are less than the upper limits thereof;

a step of returning to the selecting step when there are two clusters which are not handled by the clustering step;

a step of returning to the cluster pair generating and calculating step when a terminate condition for the logic cell placement method is not satisfied.

4. A logic cell placement method according to claim 3, wherein a connection strength of each cluster pair, the number of terminals of each cluster pair, the number of wiring which can be wired on the logic cells of each cluster pair, and a sum of values increasing in accordance with an increase of the area in each cluster pair are used as the estimate functions based on the congestion rate of the number of wirings.