JPH0513578A - 論理セル配置方法 - Google Patents
論理セル配置方法Info
- Publication number
- JPH0513578A JPH0513578A JP3159313A JP15931391A JPH0513578A JP H0513578 A JPH0513578 A JP H0513578A JP 3159313 A JP3159313 A JP 3159313A JP 15931391 A JP15931391 A JP 15931391A JP H0513578 A JPH0513578 A JP H0513578A
- Authority
- JP
- Japan
- Prior art keywords
- cell
- net
- signal transmission
- transmission time
- path
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Semiconductor Integrated Circuits (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】
【目的】 要求された信号伝達時間を守り、かつ複数の
目的を満たす良質な配置結果やフロアプラン結果を得る
ことを目的とする。 【構成】 予め、各ネットの配線長をそのネットにつな
がるセルからなる最大矩形をもとに予測する。セルある
いはセルグループの微小移動がネットの信号伝搬時間及
びパスの信号伝搬時間にどの程度影響をおよぼすかを評
価する（ステップＳ２〜Ｓ４）。信号伝搬時間を短縮す
るために効果的な移動候補セルの選びやすさを求め、移
動候補セルを確率的に選出する（ステップＳ５，Ｓ
６）。セルの移動位置を決定し、その位置に微小移動す
る（ステップＳ７）。 【効果】 パスの信号伝搬時間を短くでき、しかも自動
配置の際の他の目的の改善処理と組み合わせて用いるこ
とが容易である。
目的を満たす良質な配置結果やフロアプラン結果を得る
ことを目的とする。 【構成】 予め、各ネットの配線長をそのネットにつな
がるセルからなる最大矩形をもとに予測する。セルある
いはセルグループの微小移動がネットの信号伝搬時間及
びパスの信号伝搬時間にどの程度影響をおよぼすかを評
価する（ステップＳ２〜Ｓ４）。信号伝搬時間を短縮す
るために効果的な移動候補セルの選びやすさを求め、移
動候補セルを確率的に選出する（ステップＳ５，Ｓ
６）。セルの移動位置を決定し、その位置に微小移動す
る（ステップＳ７）。 【効果】 パスの信号伝搬時間を短くでき、しかも自動
配置の際の他の目的の改善処理と組み合わせて用いるこ
とが容易である。
Description
【０００１】
【産業上の利用分野】この発明は、半導体集積回路のレ
イアウト設計を行う際の、論理セルあるいはセルグルー
プの配置方法に関する。
イアウト設計を行う際の、論理セルあるいはセルグルー
プの配置方法に関する。
【０００２】
【従来の技術】半導体集積回路（以下、ＬＳＩと呼ぶ）
は、典型的には、図６のような構成になっている。チッ
プの外周に入出力用の論理セル（以下、セルと略す）１
が並び、チップの内部には、所望の機能を実現するため
のセル３と、セル同士を結ぶ配線５から構成されてい
る。チップ内部のセル３には、論理ゲート（インバー
タ，ＮＡＮＤゲート等）と、記憶素子（フリップフロッ
プ）がある。
は、典型的には、図６のような構成になっている。チッ
プの外周に入出力用の論理セル（以下、セルと略す）１
が並び、チップの内部には、所望の機能を実現するため
のセル３と、セル同士を結ぶ配線５から構成されてい
る。チップ内部のセル３には、論理ゲート（インバー
タ，ＮＡＮＤゲート等）と、記憶素子（フリップフロッ
プ）がある。
【０００３】一方、ＬＳＩの設計段階は、図７のように
Ｓ１１〜Ｓ１５の各段階からなっている。さらに、レイ
アウト設計Ｓ１３は、チップの顔つきを決めるフロアプ
ラン、セルのチップ上の配置位置を決定する自動配置、
接続関係のあるセル間の配線経路を決定するための自動
配線から構成されている。
Ｓ１１〜Ｓ１５の各段階からなっている。さらに、レイ
アウト設計Ｓ１３は、チップの顔つきを決めるフロアプ
ラン、セルのチップ上の配置位置を決定する自動配置、
接続関係のあるセル間の配線経路を決定するための自動
配線から構成されている。
【０００４】ＬＳＩのレイアウト設計において、チップ
面積の最小化、処理時間の短縮とともに、ＬＳＩの微細
化にともない、チップの動作性能を保証したレイアウト
設計が重要になってくる。これは、ＬＳＩを構成する素
子が小さくなり素子間を結ぶ配線幅が細くなるにつれて
信号の伝搬遅延が極端に大きくなり、これによる動作性
能の劣化が無視できなくなるからである。
面積の最小化、処理時間の短縮とともに、ＬＳＩの微細
化にともない、チップの動作性能を保証したレイアウト
設計が重要になってくる。これは、ＬＳＩを構成する素
子が小さくなり素子間を結ぶ配線幅が細くなるにつれて
信号の伝搬遅延が極端に大きくなり、これによる動作性
能の劣化が無視できなくなるからである。
【０００５】信号伝搬遅延が問題になる典型的なものと
しては、１クロックサイクルの間に信号が伝搬すること
を前提に設計されているフリップフロップ間（特にフリ
ップフロップと入出力素子の間や、入出力素子間）であ
る。図８に示すように、フリップフロップ７の間のセル
とセル間を接続するネットの連鎖をパス経路（以下、パ
スと略す）という。
しては、１クロックサイクルの間に信号が伝搬すること
を前提に設計されているフリップフロップ間（特にフリ
ップフロップと入出力素子の間や、入出力素子間）であ
る。図８に示すように、フリップフロップ７の間のセル
とセル間を接続するネットの連鎖をパス経路（以下、パ
スと略す）という。
【０００６】信号伝搬遅延を抑えるためには、ＬＳＩの
レイアウト設計の際の自動配置やフロアプランにおい
て、セルやセルグループの配置位置を決めるときに、信
号伝搬時間の仕様（タイミングスペック）を満たすよう
にすることが重要になる。
レイアウト設計の際の自動配置やフロアプランにおい
て、セルやセルグループの配置位置を決めるときに、信
号伝搬時間の仕様（タイミングスペック）を満たすよう
にすることが重要になる。
【０００７】信号伝搬時間は、図９のように一段の論理
ゲートの場合には以下のように算出される。図９におい
て、Ｒｏは出力ゲート抵抗、ＣL は配線容量、Ｃｉは入
力ゲート容量である。
ゲートの場合には以下のように算出される。図９におい
て、Ｒｏは出力ゲート抵抗、ＣL は配線容量、Ｃｉは入
力ゲート容量である。
【０００８】（信号伝搬時間)=((入力ゲート容量）＋
（配線容量))・(出力ゲートの抵抗）多段の場合には、 （信号伝搬時間)=（Σ（入力ゲート容量)+Σ（配線容量))・(出力ゲート抵抗） パスを構成する パスを構成する ネットにつながる ネットについて セルについて となる。
（配線容量))・(出力ゲートの抵抗）多段の場合には、 （信号伝搬時間)=（Σ（入力ゲート容量)+Σ（配線容量))・(出力ゲート抵抗） パスを構成する パスを構成する ネットにつながる ネットについて セルについて となる。
【０００９】このとき、パスの信号伝搬時間を決定する
には、パスを構成するセル（図１０太線）のみならず、
パスを構成するネットにつながるすべてのセル（図１０
細線）が関与している。このため、入力ゲート容量にこ
れらのセルの入力容量を加える必要があり、配線容量も
これらのセルの配置位置を考慮して見積る必要がある。
には、パスを構成するセル（図１０太線）のみならず、
パスを構成するネットにつながるすべてのセル（図１０
細線）が関与している。このため、入力ゲート容量にこ
れらのセルの入力容量を加える必要があり、配線容量も
これらのセルの配置位置を考慮して見積る必要がある。
【００１０】ネットの配線容量は、 （ネットの配線容量）＝（単位長さあたりの容量）・
（配線長さ） と求められる。
（配線長さ） と求められる。
【００１１】自動配置・フロアプランの時点では、上式
の配線長さは、セル位置から見積る必要があるのだが、
見積り方法には、最大矩形法（図１１（ａ））、ソース
シンク法（図１１（ｂ））、完全グラフ法（図１１
（ｃ））などがある。
の配線長さは、セル位置から見積る必要があるのだが、
見積り方法には、最大矩形法（図１１（ａ））、ソース
シンク法（図１１（ｂ））、完全グラフ法（図１１
（ｃ））などがある。
【００１２】（ａ）の最大矩形法は、ネット９を構成す
るセル１１のはる最大矩形の周囲長の半分（図中、太
線）を、ネット９の予測配線長とするものである。
（ｂ）のソースシンク法は、ネットを構成するセル１１
ａ，１１ｂのうちの、ソースセル１１ａとシンクセル１
１ｂとの間の直線距離の総和を、ネットの予測配線長と
するものである。（ｃ）の完全グラフ法は、ネットを構
成するセル１１をつなぐ完全グラフの全枝の直線距離の
２乗の和を、ネットの予測配線長とするものである。
るセル１１のはる最大矩形の周囲長の半分（図中、太
線）を、ネット９の予測配線長とするものである。
（ｂ）のソースシンク法は、ネットを構成するセル１１
ａ，１１ｂのうちの、ソースセル１１ａとシンクセル１
１ｂとの間の直線距離の総和を、ネットの予測配線長と
するものである。（ｃ）の完全グラフ法は、ネットを構
成するセル１１をつなぐ完全グラフの全枝の直線距離の
２乗の和を、ネットの予測配線長とするものである。
【００１３】これらのうち最大矩形法が、配線長の見積
り方法として良い性質を持つといわれている（Jackson,
M.,Srinivasan,A.,and Kuh,E.,”A Fast Algorithm for
Preformance-Driven Placement",Proc.ICCAD90.,IEEE,
pp.328-331,1990）。従来、信号伝搬遅延を少なくする
ために、以下のような方法がとられてきた。１つは、ネ
ットに対する重みづけであり、もう１つは、パス長に対
する制限をつけることである。
り方法として良い性質を持つといわれている（Jackson,
M.,Srinivasan,A.,and Kuh,E.,”A Fast Algorithm for
Preformance-Driven Placement",Proc.ICCAD90.,IEEE,
pp.328-331,1990）。従来、信号伝搬遅延を少なくする
ために、以下のような方法がとられてきた。１つは、ネ
ットに対する重みづけであり、もう１つは、パス長に対
する制限をつけることである。
【００１４】ネットに対する重みづけ法は、パスを構成
する各ネットに対してスラック値（要求される信号到達
時間−予測された到達時間）を算出し、このスラック値
に応じてネットに重みをつけていくものである（Burste
in,M.,and Youssef,M.,"Timing Influenced Layout Des
ign",Proc.22nd Design Automation Conf.,IEEE,pp.124
-130,1985)。この方法は、制約の単位がネットの配線長
であるため、従来からの自動配置に適用しやすいという
利点があるが、要求される信号到達時間が確実に守られ
る保証はない。
する各ネットに対してスラック値（要求される信号到達
時間−予測された到達時間）を算出し、このスラック値
に応じてネットに重みをつけていくものである（Burste
in,M.,and Youssef,M.,"Timing Influenced Layout Des
ign",Proc.22nd Design Automation Conf.,IEEE,pp.124
-130,1985)。この方法は、制約の単位がネットの配線長
であるため、従来からの自動配置に適用しやすいという
利点があるが、要求される信号到達時間が確実に守られ
る保証はない。
【００１５】これとは別の方法として、パスに要求され
る到達時間に応じてパス長に制限をつける方法がある。
しかしながら、この方法では問題を取り扱いやすくする
ために、ネット長の見積り方法に最大矩形法を用いてい
ない（Prasitjutrakul,S.,and Kubitz,W.J.,"Path ＿De
lay Constrained Floorplanning:A Mathematical Progr
amming Approach for Initial Placement",26th ACM/IE
EE Design AutomationConf.,pp.364-369,1989）。これ
により、信号到達時間を正確に予測できなかった。ま
た、この方法では、問題の定式化が複雑なため、解法に
時間がかかりすぎたり、タイミングスペックを満たすこ
ととは別の目的（総配線長の最小化、セル密度均一化、
セルのピン分布均一化など）の改善処理とともに用いる
のが困難である（Jackson,M.,and Kuh,E.,"Performance
-Driven Placement of cell BasedIC's",26th ACM/IEEE
Design Automation Conf.,pp.364-369,1989. Jackson,
M.,Srinivasan,A.,and Kuh,E.,"A Fast Algorithm for
Performance-Driven Placement",Proc.ICCAD90.,IEEE,p
p.328-331,1990)等の問題点があった。
る到達時間に応じてパス長に制限をつける方法がある。
しかしながら、この方法では問題を取り扱いやすくする
ために、ネット長の見積り方法に最大矩形法を用いてい
ない（Prasitjutrakul,S.,and Kubitz,W.J.,"Path ＿De
lay Constrained Floorplanning:A Mathematical Progr
amming Approach for Initial Placement",26th ACM/IE
EE Design AutomationConf.,pp.364-369,1989）。これ
により、信号到達時間を正確に予測できなかった。ま
た、この方法では、問題の定式化が複雑なため、解法に
時間がかかりすぎたり、タイミングスペックを満たすこ
ととは別の目的（総配線長の最小化、セル密度均一化、
セルのピン分布均一化など）の改善処理とともに用いる
のが困難である（Jackson,M.,and Kuh,E.,"Performance
-Driven Placement of cell BasedIC's",26th ACM/IEEE
Design Automation Conf.,pp.364-369,1989. Jackson,
M.,Srinivasan,A.,and Kuh,E.,"A Fast Algorithm for
Performance-Driven Placement",Proc.ICCAD90.,IEEE,p
p.328-331,1990)等の問題点があった。
【００１６】
【発明が解決しようとする課題】以上のように、従来の
レイアウト設計では、要求された信号伝達時間を守れな
かったり、最大矩形法を用いないためにネットの配線長
を正確に予測できなかったり、また解法に時間がかかる
などの問題があった。
レイアウト設計では、要求された信号伝達時間を守れな
かったり、最大矩形法を用いないためにネットの配線長
を正確に予測できなかったり、また解法に時間がかかる
などの問題があった。
【００１７】本発明は、このような従来の事情を鑑みて
なされたものであり、その目的とするところは、最大矩
形法を用いてネットの配線長を見積ることにより、信号
伝達時間を正確に予測して要求された信号伝達時間を満
たし、かつ他の複数の目的を同時に満足させることがで
きる論理セル配置方法を提供することにある。
なされたものであり、その目的とするところは、最大矩
形法を用いてネットの配線長を見積ることにより、信号
伝達時間を正確に予測して要求された信号伝達時間を満
たし、かつ他の複数の目的を同時に満足させることがで
きる論理セル配置方法を提供することにある。
【００１８】
【課題を解決するための手段】上記目的を達成するた
め、この発明は、半導体集積回路のレイアウト設計を行
う際に、論理セル間あるいは複数の論理セルからなるセ
ルグループ間を接続したネットの配線長を、このネット
を構成する論理セルの配置位置から得られる最大矩形を
基に予測し、予測したネットの配線長からこのネットの
信号伝達時間を予測し、予測したネットの信号伝達時間
から、複数のネットの連鎖からなるパス経路の信号伝達
時間を予測し、各論理セルあるいはセルグループの配置
位置が微小移動したと仮定したときの、この論理セルあ
るいはセルグループによって構成されるネットの変化し
た信号伝達時間を求め、各論理セルあるいはセルグルー
プの配置位置が微小移動したと仮定したときの、この論
理セルあるいはセルグループによって構成されるパス経
路の変化した信号伝達時間を求め、求められたネットの
変化した信号伝達時間とパス経路の変化した信号伝達時
間から、パス経路の信号伝達時間を短くするために配置
位置を移動すべき論理セルあるいはセルグループの選び
やすさを算出し、算出された選びやすさを用いて確率的
に論理セルあるいはセルグループを選出し、選出された
論理セルあるいはセルグループの配置位置を微小移動す
るように構成されている。
め、この発明は、半導体集積回路のレイアウト設計を行
う際に、論理セル間あるいは複数の論理セルからなるセ
ルグループ間を接続したネットの配線長を、このネット
を構成する論理セルの配置位置から得られる最大矩形を
基に予測し、予測したネットの配線長からこのネットの
信号伝達時間を予測し、予測したネットの信号伝達時間
から、複数のネットの連鎖からなるパス経路の信号伝達
時間を予測し、各論理セルあるいはセルグループの配置
位置が微小移動したと仮定したときの、この論理セルあ
るいはセルグループによって構成されるネットの変化し
た信号伝達時間を求め、各論理セルあるいはセルグルー
プの配置位置が微小移動したと仮定したときの、この論
理セルあるいはセルグループによって構成されるパス経
路の変化した信号伝達時間を求め、求められたネットの
変化した信号伝達時間とパス経路の変化した信号伝達時
間から、パス経路の信号伝達時間を短くするために配置
位置を移動すべき論理セルあるいはセルグループの選び
やすさを算出し、算出された選びやすさを用いて確率的
に論理セルあるいはセルグループを選出し、選出された
論理セルあるいはセルグループの配置位置を微小移動す
るように構成されている。
【００１９】
【作用】上記構成により、この発明は、各ネットの配線
長を、そのネットを構成するセルあるいはセルグループ
の配置位置から得られる最大矩形をもとに予測すること
で、パスの信号伝搬時間を正確に予測する。セルあるい
はセルグループが微小移動したと仮定し、これによるネ
ットの信号伝搬時間がどれだけ変化するか、またパスの
信号伝達時間がどれだけ変化するかを求める。この結果
から、信号伝搬時間を短くするのに効果の高い移動候補
セルの選びやすさを算出する。
長を、そのネットを構成するセルあるいはセルグループ
の配置位置から得られる最大矩形をもとに予測すること
で、パスの信号伝搬時間を正確に予測する。セルあるい
はセルグループが微小移動したと仮定し、これによるネ
ットの信号伝搬時間がどれだけ変化するか、またパスの
信号伝達時間がどれだけ変化するかを求める。この結果
から、信号伝搬時間を短くするのに効果の高い移動候補
セルの選びやすさを算出する。
【００２０】算出された選びやすさを用いて確率的に移
動候補セルを選出し、選出された移動候補セルを、決定
されたい同位置に微小移動している。
動候補セルを選出し、選出された移動候補セルを、決定
されたい同位置に微小移動している。
【００２１】
【実施例】以下、この発明の実施例を図面に基づいて詳
説する。図１はこの発明の論理セル配置方法に係わる一
実施例の処理手順を示すフローチャートである。図中、
“セル”とあるところをセルグループに書き換えれば、
フロアプラン用に適用することができる。
説する。図１はこの発明の論理セル配置方法に係わる一
実施例の処理手順を示すフローチャートである。図中、
“セル”とあるところをセルグループに書き換えれば、
フロアプラン用に適用することができる。
【００２２】初期配置（ステップＳ１）は、各セルの配
置位置を初期的に与えるものであり、一般的にはセルを
ランダムに並べることが多い。次に、１つのセルが微小
移動したと仮定したときに、このセルによって構成され
るネットの信号伝達時間がどれだけ変化するかの評価値
（変化した信号伝達時間）を各セルごとに求める（ステ
ップＳ２）。このとき、予め最大矩形法を用いてネット
の配線長を予測し、ネットの信号伝達時間を予測する。
置位置を初期的に与えるものであり、一般的にはセルを
ランダムに並べることが多い。次に、１つのセルが微小
移動したと仮定したときに、このセルによって構成され
るネットの信号伝達時間がどれだけ変化するかの評価値
（変化した信号伝達時間）を各セルごとに求める（ステ
ップＳ２）。このとき、予め最大矩形法を用いてネット
の配線長を予測し、ネットの信号伝達時間を予測する。
【００２３】 （あるネットの信号伝達時間） ＝（単位長さあたりの容量）・（配線長さ）・（出力抵抗） なので、
【００２４】
【外１】
【００２５】と求められる。上式は、微小移動量による
信号伝達時間の変化量を表している。このデータは、各
ネット毎に保存されていて、プログラム内においてｆ
（ネットＩＤ）で呼び出せる。
信号伝達時間の変化量を表している。このデータは、各
ネット毎に保存されていて、プログラム内においてｆ
（ネットＩＤ）で呼び出せる。
【００２６】 一方、パスの信号伝搬時間は、予測されたネットの配線長を基に、 (信号伝搬時間）=(Σ（入力ゲート容量)+Σ（配線容量))・(出力ゲートの抵抗） パスを構成する パスを構成する ネットにつながる ネットについて セルについて と求められる（ステップＳ３）。
【００２７】これを、上記ｆ（ネットＩＤ）で表わす
と、入力ゲート容量の項は定数とみなされ、 （信号伝搬時間）＝定数＋Σｆ（配線長） パスを構成するネット について と表現できる。
と、入力ゲート容量の項は定数とみなされ、 （信号伝搬時間）＝定数＋Σｆ（配線長） パスを構成するネット について と表現できる。
【００２８】次に、１つのセルが微小移動したと仮定し
たときに、パス全体の信号伝搬時間がどれだけ変化する
かの評価値を求める（ステップＳ４）。この評価値は、
パスを構成する各セルについて求める。パスを構成する
セルは、パスを構成するネットの唯一のソース（信号を
供給するセル）となっているため、この情報も、ネット
毎に持つこととする。基本的な考え方は、以下の通り。
たときに、パス全体の信号伝搬時間がどれだけ変化する
かの評価値を求める（ステップＳ４）。この評価値は、
パスを構成する各セルについて求める。パスを構成する
セルは、パスを構成するネットの唯一のソース（信号を
供給するセル）となっているため、この情報も、ネット
毎に持つこととする。基本的な考え方は、以下の通り。
【００２９】簡単のため、図２のように、パスを構成す
る各ネット１〜３は、パスを構成するセル１〜４のみか
らなる２端子ネットとする。また、セルの単位移動あた
りのネットｉの信号伝搬時間の変化（上記ｆ（ｉ））
は、１とする。図２において、セル２が左右にαだけ微
小移動しても、パス全体の信号伝搬時間に影響はない。
る各ネット１〜３は、パスを構成するセル１〜４のみか
らなる２端子ネットとする。また、セルの単位移動あた
りのネットｉの信号伝搬時間の変化（上記ｆ（ｉ））
は、１とする。図２において、セル２が左右にαだけ微
小移動しても、パス全体の信号伝搬時間に影響はない。
【００３０】
【外２】
【００３１】しかしながら、セル３が微小移動したとす
ると、 （ネット２の長さ±α）＋（ネット３の長さ±α） ＝ネット２の長さ＋ネット３の長さ±２α となり、大きく影響する。
ると、 （ネット２の長さ±α）＋（ネット３の長さ±α） ＝ネット２の長さ＋ネット３の長さ±２α となり、大きく影響する。
【００３２】つまり、セルｉの１つ前のセルｉ−１と１
つ後のセルｉ＋１がセルｉに向かって同じ方向にいる場
合（図２のセル２，３，４の関係）には、セルｉを動か
すとパスの信号伝搬時間を短くする効果が高いが、セル
ｉをはさんで反対側にいる場合（セル１，２，３の関
係）には効果が低い。
つ後のセルｉ＋１がセルｉに向かって同じ方向にいる場
合（図２のセル２，３，４の関係）には、セルｉを動か
すとパスの信号伝搬時間を短くする効果が高いが、セル
ｉをはさんで反対側にいる場合（セル１，２，３の関
係）には効果が低い。
【００３３】一般的には、セルｉを動かすことによる、
パスの信号伝搬時間の変化は、
パスの信号伝搬時間の変化は、
【００３４】
【外３】
【００３５】で求めることができる。ただし、ｘi はセ
ルｉの位置である。このようにして求めた信号伝搬時間
は、セルｉをソースとするネットｉに対するデータとし
てｇ（ネットＩＤ）で呼び出せる。
ルｉの位置である。このようにして求めた信号伝搬時間
は、セルｉをソースとするネットｉに対するデータとし
てｇ（ネットＩＤ）で呼び出せる。
【００３６】次に、移動候補セルの選ばれやすさを算出
する（ステップＳ５）。各セルが微小移動したときに各
ネットの信号伝達時間がどれだけ変化するかの評価値ｆ
（ネットＩＤ）と各セルが微小移動したときにパス全体
の信号伝搬時間がどれだけ変化するかの評価値ｇ（ネッ
トＩＤ）から以下のように算出する。
する（ステップＳ５）。各セルが微小移動したときに各
ネットの信号伝達時間がどれだけ変化するかの評価値ｆ
（ネットＩＤ）と各セルが微小移動したときにパス全体
の信号伝搬時間がどれだけ変化するかの評価値ｇ（ネッ
トＩＤ）から以下のように算出する。
【００３７】（セルｃの選ばれやすさ）＝（ｆ（セルｃ
のつながるネットｉ）＋ｇ（セルｃのつながるネット
ｉ））×（ネットｉの中心とセルｃの距離）ただし、図
３で示すように、ネットｉの中心Ｐはこのネットｉを構
成するセルｉとセルｉ＋１の中点とする。また、セルｃ
の選ばれやすさは、ｘ方向とｙ方向別々に求めた後、両
者を足し合わせる。
のつながるネットｉ）＋ｇ（セルｃのつながるネット
ｉ））×（ネットｉの中心とセルｃの距離）ただし、図
３で示すように、ネットｉの中心Ｐはこのネットｉを構
成するセルｉとセルｉ＋１の中点とする。また、セルｃ
の選ばれやすさは、ｘ方向とｙ方向別々に求めた後、両
者を足し合わせる。
【００３８】なお、セルｃは複数のパスに含まれる可能
性があるので、セルの選ばれやすさはパスのスラック値
（余裕度）によって重みをつけ足し合わせて求めること
も可能である。これにより、スラック値が最小となるパ
スに含まれるセルが選ばれやすくなる。
性があるので、セルの選ばれやすさはパスのスラック値
（余裕度）によって重みをつけ足し合わせて求めること
も可能である。これにより、スラック値が最小となるパ
スに含まれるセルが選ばれやすくなる。
【００３９】例えば、図４において、ネット２の最大矩
形Ｔ２内に配置される、ネット２につながるセル（図
中、○印）の場合、選ばれやすさの等高線は図５のよう
になる。ネット２の中心を原点とすると、図５のように
４つの部分（ａ）〜（ｄ）に分 けられ、それぞれの等高線を描く曲線は、 (a) （１＋２）ｘ2 ＋ ｙ2 ＝３ｘ2 ＋ ｙ2 ＝定数 (b) ｘ2 ＋ ｙ2 ＝ ｘ2 ＋ ｙ2 ＝定数 (c) ｘ2 ＋（１＋２）ｙ2 ＝ ｘ2 ＋３ｙ2 ＝定数 (d) （１＋２）ｘ2 ＋（１＋２）ｙ2 ＝３ｘ2 ＋３ｙ2 ＝定数 のように表される。
形Ｔ２内に配置される、ネット２につながるセル（図
中、○印）の場合、選ばれやすさの等高線は図５のよう
になる。ネット２の中心を原点とすると、図５のように
４つの部分（ａ）〜（ｄ）に分 けられ、それぞれの等高線を描く曲線は、 (a) （１＋２）ｘ2 ＋ ｙ2 ＝３ｘ2 ＋ ｙ2 ＝定数 (b) ｘ2 ＋ ｙ2 ＝ ｘ2 ＋ ｙ2 ＝定数 (c) ｘ2 ＋（１＋２）ｙ2 ＝ ｘ2 ＋３ｙ2 ＝定数 (d) （１＋２）ｘ2 ＋（１＋２）ｙ2 ＝３ｘ2 ＋３ｙ2 ＝定数 のように表される。
【００４０】移動候補セルの選出は、ステップＳ５で算
出された選ばれやすさを基に、いちばん選ばれやすいも
の（最も外側の等高線に位置するセル）が選ばれる確率
を１に正規化する。そして、ランダムに移動候補セルを
選び、［０，１］区間の乱数を発生させそのセルの選ば
れやすさより乱数が小さければそのセルを移動し、大き
ければランダムにセルを選び直す。このような処理を繰
り返すことにより、移動候補セルを選出する（ステップ
Ｓ６）。ランダムにセルを選ぶのは、選ばれたセルの偏
りをなくすためである。
出された選ばれやすさを基に、いちばん選ばれやすいも
の（最も外側の等高線に位置するセル）が選ばれる確率
を１に正規化する。そして、ランダムに移動候補セルを
選び、［０，１］区間の乱数を発生させそのセルの選ば
れやすさより乱数が小さければそのセルを移動し、大き
ければランダムにセルを選び直す。このような処理を繰
り返すことにより、移動候補セルを選出する（ステップ
Ｓ６）。ランダムにセルを選ぶのは、選ばれたセルの偏
りをなくすためである。
【００４１】この後、選ばれたセルのつながるネットの
中心方向に微小距離だけ移動することとして、移動位置
を算出する（ステップＳ７）。終了条件は各パスのスラ
ック値が十分大きくなるまでとし、この条件が満たされ
るまでステップＳ３〜Ｓ８を繰り返す。
中心方向に微小距離だけ移動することとして、移動位置
を算出する（ステップＳ７）。終了条件は各パスのスラ
ック値が十分大きくなるまでとし、この条件が満たされ
るまでステップＳ３〜Ｓ８を繰り返す。
【００４２】
【発明の効果】以上のように、この発明の論理セル配置
方法によれば、各ネットの配線長を最大矩形法を用いて
予測しているので、パスの信号伝搬時間を正確に予測す
る事ができる。これにより、タイミングスペックを満た
す論理セルの配置が可能になる。また、確率的に移動候
補セルを選び、次にその移動位置を決定することによ
り、タイミングスペックとは別の目的の改善処理と組み
合わせて使用することが容易となる。
方法によれば、各ネットの配線長を最大矩形法を用いて
予測しているので、パスの信号伝搬時間を正確に予測す
る事ができる。これにより、タイミングスペックを満た
す論理セルの配置が可能になる。また、確率的に移動候
補セルを選び、次にその移動位置を決定することによ
り、タイミングスペックとは別の目的の改善処理と組み
合わせて使用することが容易となる。
【図１】本発明の一実施例の処理手順を説明するための
フローチャートである。
フローチャートである。
【図２】セルが微小移動したときの、パスの信号伝搬時
間に与える影響を説明するための概略図である。
間に与える影響を説明するための概略図である。
【図３】ネットの中心を説明するための概略図である。
【図４】ネットの最大矩形とネットにつながるセルを示
す概略図である。
す概略図である。
【図５】セルの選ばれやすさを等高線で表した等高線グ
ラフである。
ラフである。
【図６】典型的なＬＳＩの構成図である。
【図７】ＬＳＩの設計工程を示す流れ図である。
【図８】フリップフロップ間のパスを示す回路図であ
る。
る。
【図９】一般の論理ゲートの場合の信号伝搬時間を説明
するための回路図である。
するための回路図である。
【図１０】パス全体の信号伝搬時間を説明するための回
路図である。
路図である。
【図１１】ネットの配線長の見積り方法を説明するため
の簡略図である。
の簡略図である。
Claims (1)
- 【特許請求の範囲】 【請求項１】 半導体集積回路のレイアウト設計を行う
際に、論理セル間あるいは複数の論理セルからなるセル
グループ間を接続したネットの配線長を、このネットを
構成する論理セルの配置位置から得られる最大矩形を基
に予測し、予測したネットの配線長からこのネットの信
号伝達時間を予測し、予測したネットの信号伝達時間か
ら、複数のネットの連鎖からなるパス経路の信号伝達時
間を予測し、各論理セルあるいはセルグループの配置位
置が微小移動したと仮定したときの、この論理セルある
いはセルグループによって構成されるネットの変化した
信号伝達時間を求め、各論理セルあるいはセルグループ
の配置位置が微小移動したと仮定したときの、この論理
セルあるいはセルグループによって構成されるパス経路
の変化した信号伝達時間を求め、求められたネットの変
化した信号伝達時間とパス経路の変化した信号伝達時間
から、パス経路の信号伝達時間を短くするために配置位
置を移動すべき論理セルあるいはセルグループの選びや
すさを算出し、算出された選びやすさを用いて確率的に
論理セルあるいはセルグループを選出し、選出された論
理セルあるいはセルグループの配置位置を微小移動する
ことを特徴とする論理セル配置方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3159313A JPH0513578A (ja) | 1991-07-01 | 1991-07-01 | 論理セル配置方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3159313A JPH0513578A (ja) | 1991-07-01 | 1991-07-01 | 論理セル配置方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0513578A true JPH0513578A (ja) | 1993-01-22 |
Family
ID=15691072
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3159313A Pending JPH0513578A (ja) | 1991-07-01 | 1991-07-01 | 論理セル配置方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0513578A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0407585A4 (en) * | 1988-07-15 | 1992-06-10 | Toray Silicone Co. Ltd. | Semiconductor device sealed with resin and a method of producing the same |
-
1991
- 1991-07-01 JP JP3159313A patent/JPH0513578A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0407585A4 (en) * | 1988-07-15 | 1992-06-10 | Toray Silicone Co. Ltd. | Semiconductor device sealed with resin and a method of producing the same |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2891328B2 (ja) | 多重レベル階層回路設計用の遅延時間値生成の方法 | |
| US8448104B1 (en) | Method and an apparatus to perform statistical static timing analysis | |
| US6557145B2 (en) | Method for design optimization using logical and physical information | |
| US7127695B2 (en) | Timing based scan chain implementation in an IC design | |
| US6425110B1 (en) | Incremental design tuning and decision mediator | |
| KR100249251B1 (ko) | 논리회로 최적화 장치 및 그 방법 | |
| EP1192559B1 (en) | Updating placement during technology mapping | |
| JP5401256B2 (ja) | 半導体装置の設計方法 | |
| US20020124230A1 (en) | Timing optimization for integrated circuit design | |
| US6836753B1 (en) | Cone slack allocator for computing time budgets | |
| US9317641B2 (en) | Gate substitution based system and method for integrated circuit power and timing optimization | |
| US6378116B1 (en) | Using budgeted required time during technology mapping | |
| US9342642B1 (en) | Statistical optimization in place-and-route | |
| Bock et al. | Local search algorithms for timing-driven placement under arbitrary delay models | |
| US7191417B1 (en) | Method and apparatus for optimization of digital integrated circuits using detection of bottlenecks | |
| CN105787147A (zh) | 减少集成电路的版图中的拥挤区的方法 | |
| US8418116B2 (en) | Zone-based optimization framework for performing timing and design rule optimization | |
| US7114139B2 (en) | Device and method for floorplanning semiconductor integrated circuit | |
| US20060242613A1 (en) | Automatic floorplanning approach for semiconductor integrated circuit | |
| US7415687B2 (en) | Method and computer program for incremental placement and routing with nested shells | |
| US6000038A (en) | Parallel processing of Integrated circuit pin arrival times | |
| JPH0513578A (ja) | 論理セル配置方法 | |
| US6615401B1 (en) | Blocked net buffer insertion | |
| US6449756B1 (en) | Method for accurate and efficient updates of timing information logic synthesis, placement and routing for integrated circuit design | |
| CN116562200A (zh) | 连接路径设计方法、装置、设计设备、存储介质及芯片 |