JPH1056067A

JPH1056067A - 自動配置配線方法

Info

Publication number: JPH1056067A
Application number: JP8210127A
Authority: JP
Inventors: Yoshiyuki Kawakami; 善之川上
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1996-08-08
Filing date: 1996-08-08
Publication date: 1998-02-24

Abstract

(57)【要約】【課題】複数の遅延制約を満足したレイアウトを生成
する方法を提供する。【解決手段】色々な設計条件下における遅延制約を表
現したスラックグラフを用意する。条件は複数個存在す
るので複数のスラックグラフが生成させる。そのスラッ
クグラフを用いてピン配置の改善を行なうピン配置ステ
ップ４、セルの配置改善を行なうセル配置ステップ１、
概略配線経路改善を行なう概略配線ステップ３を行なう
が、ここで特徴的なのは各ステップにおいて全てのスラ
ックグラフを表現した遅延制約を満たすまでそれらの改
善を続けることである。これによって事前にタイミング
違反を除去しているので、ＬＳＩ設計の最終検証の段階
でのタイミング違反を検出することがなくなり、設計期
間の短縮化を図ることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、半導体ＬＳＩのレ
イアウト設計における自動配置配線方法に関するもので
ある。つまり、半導体集積回路の構成要素となる複数の
機能ブロックまたは複数の論理セルを配置した後複数の
機能ブロックまたは複数の論理セルの間を論理接続要求
に従って配線してレイアウト設計を行なうことに際し、
各々のネットの配線遅延を制約として複数の論理セルの
配置を行なうタイミングドリブン配置と、各々のネット
の配線遅延を制約として概略配線経路決定を行なうタイ
ミングドリブン概略配線と、各々のネットの配線遅延を
制約として未レイアウトの機能ブロックの外部ピン（以
下、浮動外部ピンと呼ぶ）の配置を決定するタイミング
ドリブンピン配置の少なくとも一つによる自動配置配線
方法に関するものである。

【０００２】

【従来の技術】近年はシステム・オン・シリコン時代と
呼ばれるように、１チップにシステムを搭載するほどに
高集積化された半導体ＬＳＩチップが開発されてきてお
り、ＬＳＩ設計にかかる工数が増加の一途をたどってい
る。その中で、レイアウト設計においても例外ではな
く、工数・処理時間が指数関数的に増大してきており、
回路全体を一度にレイアウトするには膨大な時間および
労力を費やすことになる。そこで、回路をいくつかの機
能ブロックに分割し、各々個別に設計し、最後に機能ブ
ロック間を配線して組み上げるといった階層設計の手法
が採られることが多い。このように、階層的に複数ブロ
ックを組み上げて１チップのレイアウト設計を行なった
ＬＳＩは、ビルディングブロック方式ＬＳＩと呼ばれ
る。

【０００３】半導体ＬＳＩチップのレイアウト設計方式
として、ゲートアレイ（または、シー・オブ・ゲート）
方式やスタンダードセル方式等がある。これらの方式
は、ＮＡＮＤゲート、ＯＲゲート等の基本論理セルやそ
れらを組み合わせた複合セルをアレイ状にＬＳＩ基板上
に配置し、所望の回路接続に従ってそれらセル上にある
端子の間を配線することによってＬＳＩチップを作る方
法である。これらの方法は設計の自動化が進んでおり、
様々な設計支援システム（ＣＡＤシステム）が開発され
ている。

【０００４】このシステムで設計を行なう基本手順を示
す。１）仮想的なチップ領域内に論理セルを配置する（セル
配置）。２）チップ上の大まかな配線経路を決定する概略配線を
施す（概略配線）。３）その概略配線経路を基に具体的にデザインルールを
満足して全てのネット間の配線を決定する詳細配線を行
なう（詳細配線）。ここで、ネットとは等電位に接続し
なければならない端子の集合である。

【０００５】もし前述のようなビルディングブロック方
式ＬＳＩで設計する場合、始めにチップ全体に対して機
能ブロックを何処に配置するかを決定するフロアプラン
を行なうことが多い。その際、未レイアウトの機能ブロ
ックの配置も行なうので、その機能ブロックの外部との
入出力を司る外部端子（浮動外部端子）の位置を決定す
るピン配置を行なう。

【０００６】半導体ＬＳＩの製造技術の進歩により、今
ではディープサブミクロンと呼ばれる０．５ミクロン以
下のデザインルールでチップを設計する程になってい
る。これによって、回路内を信号が伝達する時間、すな
わち信号遅延時間（単に、遅延時間）に占める配線遅延
とゲート遅延の関係が、配線遅延＞ゲート遅延となり、
チップ設計において配線遅延を考慮することが必須の課
題となっている。このような課題を解決するために、遅
延時間を考慮してチップ設計することをタイミングドリ
ブン設計と呼んでいる。

【０００７】ここで、タイミングドリブン設計の基本原
理を簡単に説明する。一般に、多くの半導体ＬＳＩは同
期回路で設計されている。この同期回路は、図５（ａ）
に示すように、同期素子（フリップフロップ等）の集合
と同期素子間をつなぐ組合せ回路の集合としてモデル化
することができる。このとき、同期回路のクロックサイ
クル時間Ｔclk は、Ｔclk ≧ｍａｘ（Ｔhold＋ＴD-Q ＋Ｔdelay ＋Ｔskew）として定式化できる。ここで、Ｔholdは同期素子のセッ
トアップ・ホールド時間、ＴD-Q は同期素子内部の信号
入力から出力までの遅延時間、Ｔdelay は組合せ回路の
遅延時間、Ｔskewはクロックスキューである。詳細は
「プロシーディング・オブ・第２７回・デザイン・オー
トメーション・カンファレンス、１９９０、ページ５７
３−５７９（Proc. of the 27th Design Automation Co
nference, 1990, pp.573-579）」に記述されている。

【０００８】さらに、組合せ回路の遅延時間Ｔdelay
は、ゲート間の遅延（あるゲートのファンインからつぎ
のゲートのファンインまでの遅延）Ｔd の和によってモ
デル化できる。例えば、図５（ｂ）のような２個のフリ
ップフロップ（ＦＦ１，ＦＦ２）とＡＮＤゲートとＯＲ
ゲートで回路構成された例では、Ｔdelay ＝ＴQ ＋ＴAND ＋ＴOR となる。なお、ＴQ ，ＴAND ，ＴORは、各々ＦＦ1 の出
力ドライバから、ＡＮＤゲートから、ＯＲゲートからの
ゲート間遅延時間Ｔd である。

【０００９】さらに、このゲート間遅延時間Ｔd は、Ｔd ＝Ｔintrinsic ＋Ｔload＋Ｔwire＋Ｔpriv として定式化できる。ここで、Ｔintrinsic は負荷に依
らないゲート遅延時間、Ｔloadは負荷全体（配線容量＋
端子容量の総和）に関わるゲート遅延時間、Ｔwireは配
線形状などに依存する配線遅延時間、Ｔprivは前段の波
形鈍りに依存する遅延時間である。詳細は「プロシーデ
ィング・オブ・第３１回・デザイン・オートメーション
・カンファレンス、１９９４、ページ３２７−３３２
（Proc. of the 31st Design Automation Conference,
1994, pp.327-332）」に記述されている。

【００１０】さらに、モデルを簡単化して、配線形状に
依存する配線遅延時間Ｔwireを除く３項をゲート遅延時
間Ｔgateにおくと、ゲート間遅延時間Ｔd はＴd ＝Ｔgate＋Ｔwire となる。タイミングドリブン設計は、以上のようなモデ
ル化を基にゲート遅延時間と配線遅延時間とを見積もっ
て設計する手法のことである。

【００１１】設計の上位のレベル（例えば、機能設計や
論理設計）からゲート遅延や配線遅延を見積もりながら
設計を進めていくが、レイアウト設計では見積もられた
配線遅延を満足するようなレイアウト図を生成すること
が必須となる。すなわち、ある配線遅延の制約の基に配
置配線を行なうことである。遅延制約を表現する方法と
して、スラックと呼ばれる概念を用いるのが一般的であ
る。スラック値は、信号パスなどがもつ、タイミング制
約（遅延制約）に対する余裕度を示す値であり、 slack(x)＝Ｔr(x)−Ｔa(x) のように定義される。ここで、Ｔr(x)とは回路ｘ（素
子、信号パス等）に（設計上）要求された到着時間、Ｔ
a(x)は回路ｘに実際に（レイアウト図上で求められた）
到着した時間である。slack(x)が負であることはタイミ
ング違反していることを意味する。

【００１２】さらに、タイミングドリブン設計において
よく使われるスラックグラフについて図６から図１２ま
でを参照しながら説明する。図６（ａ）は６個の論理セ
ル１〜６（４個のＡＮＤセルと２個のバッファセル）を
含むある回路の回路図を示しており、この回路の信号は
左から右へ流れ、この回路のパス遅延制約は例えば１９
であるとする。この図には、あるレイアウトを行なった
ときに求められたセル内遅延を示す数値を各論理セルに
近接して記述してあり、ネットの配線遅延を示す数値を
各論理セルを結ぶ配線に近接して記述している。なお、
遅延制約や各遅延値の単位は例えば、ピコ秒やナノ秒で
ある。

【００１３】図６（ｂ）は同図（ａ）の回路を含む回路
をスタンダードセル方式ＬＳＩで配置（レイアウト）し
たときの配置結果の一例の概略図を示している。図６
（ｃ）は同図（ｂ）における同図（ａ）の回路の部分の
拡大図を示しており、例えばこの図のようにレイアウト
したときのセル内遅延およびネットの配線遅延を図６
（ａ）の回路に記述している。なお、図６（ａ）の回路
を構成する各論理セル１〜６を列上に並べ、各論理セル
１〜６間のネット配線を行なうことにより、レイアウト
が行なえる。各論理セル１〜６の並べ方は任意である。
このようにして、各論理セル１〜６の配置が決まると、
ネットの配線によって物理的距離をもつことになり、ネ
ットの配線遅延の計算が可能となる。また、配線の長さ
がわかるので、セル内遅延の計算も可能となる。よっ
て、一度配置位置が決まると、ネットの配線遅延とセル
内遅延とが計算されることになる。

【００１４】ここで、配線の長さがわかることでセル内
遅延の計算が可能となる理由について説明する。上述し
たように、ゲート間遅延時間Ｔｄは、Ｔd ＝Ｔintrinsic ＋Ｔload＋Ｔwire＋Ｔpriv で表される。これをセル内遅延Ｔgateと配線遅延Ｔwire
で表現すると、前述のように、Ｔd ＝Ｔgate＋Ｔwire となる。ここで、Ｔgate＝Ｔintrinsic ＋Ｔload＋Ｔpriv である。

【００１５】つぎに、セル内遅延Ｔgateがどのようにし
て演算されるかを以下に説明する。Ｔintrinsic は、負
荷によらないゲート遅延であるから、セルが決まれば一
意に決まり、配線に依存しない。Ｔloadは、負荷全体に
かかわるゲート遅延時間であり、これはセルの出力側に
つながるネットの負荷容量の総和を基に計算される。よ
って、配線の長さがわかれば配線負荷容量がわかるの
で、計算可能となる。Ｔprivは、セルの入力側につなが
る前段の波形鈍りに依存する遅延時間であり、これは前
段の配線ネットによって計算されるものである。配線の
長さがわかれば、正確には計算できないが、近似的には
計算が可能である。以上のことから、配線の長さがわか
れば、Ｔgateを算出することができる。

【００１６】つぎに、パス遅延制約を、ネットの配線遅
延制約に置き換えることができる理由について説明す
る。設計上の遅延制約は、パス遅延制約の形で定義され
る。しかし、図６（ｂ）でわかるように、いったん配置
がなされた段階で配線の長さがわかるので、ネットの配
線遅延がわかることになる。パス遅延制約を満たすため
に配置を改善するときに、元の配置位置を参考に一部の
変更を繰り返し行うので、パスで遅延制約が守られてい
るかどうか検証しますが、ネット長の変化が基になり、
最終的にネット長を幾らに変更するということに帰着す
るので、パス遅延制約はネットの配線遅延制約に置き換
えることが可能となる。したがって、レイアウト設計に
おいては、パス遅延制約とネットの配線遅延制約と均等
なものと考えられる。

【００１７】図７は図６（ａ）の回路の図６（ｃ）の配
置結果を基にして作成した第１のスラックグラフの初期
状態を示している。このスラックグラフを条件０（typi
cal条件）下のグラフと定義する。従来はこのtypical
条件（条件０）下のみで、つまり１条件のみでタイミン
グドリブン配置／配線を行なう。図７においては、図６
（ａ）の各論理セルの出力端、つまり頂点を丸で示し、
図６（ａ）の各論理セル１〜６の入出力部の配線（ネッ
ト）を無向枝で示している。図７の頂点１〜６は図６
（ａ）の論理セル１〜６とそれぞれ対応しており、頂点
１〜６のそれぞれの中に図６（ａ）に示したのと同じセ
ル内遅延値を記述し、それと併せて括弧内に累積遅延値
を記述している。また、頂点１〜６につながる無向枝に
も図６（ａ）に示したの同じネットの配線遅延値を記述
し、それと併せて括弧内に累積遅延値を記述するように
している。なお、累積遅延値は図６（ａ）の回路の各始
端から該当する頂点もしくは無向枝までの遅延値の累積
値の最大値（最長パス）である。このときはパス遅延計
算をしていないので、累積遅延値はすべて０となってい
る。

【００１８】図８は図７の初期状態のスラックグラフを
基にしてパス遅延計算をした結果（typical 条件（条件
０））のスラックグラフを示している。この図のスラッ
クグラフにおいて、クリティカルパスは頂点２→頂点４
→頂点６となる。ここで、図８のスラックグラフにおけ
るパス遅延計算（累積遅延値の計算）の手法について説
明する。

【００１９】パス遅延の求め方は、常にある頂点に到達
するまでの遅延時間の最長で計算する。例えば、頂点１
までのパス遅延はそこまでにかかる時間が１であるの
で、セル内遅延値１との和をとって、頂点１までのパス遅延＝１＋１＝２となる。同様にして、頂点２までのパス遅延＝２＋３＝５となる。さらに、頂点３までのパス遅延は、頂点１まで
のパス遅延と頂点１と頂点３の間の配線遅延の和と、頂
点２までのパス遅延と頂点２と頂点３の間の配線遅延の
和との内の最大値と頂点３のセル内遅延値との和をとる
ことで求まる。つまり、頂点３までのパス遅延＝頂点２までのパス遅延＋頂点２
と頂点３の間の配線遅延＋頂点３のセル内遅延＝５＋１
＋４＝１０同様にして、頂点４までのパス遅延＝５＋１＋６＝１２頂点５までのパス遅延＝１０＋２＋６＝１８頂点６までのパス遅延＝１２＋２＋６＝２０となる。パス遅延制約が１９であるので、 slack(5)＝１９−１８＝１ slack(6)＝１９−２０＝−１となる。slack(5)＞slack(6)であるので、slack(6)を計
算した経路は２→４→６となり、このこの経路はクリテ
ィカルパスとなる。しかも、スラック値は負であるの
で、タイミング違反を起こしていることになる。この違
反をなくすためには頂点２までの配線、頂点２〜頂点４
までの配線、頂点４〜頂点６までの配線のいずれかを短
くすることをしなければならない。

【００２０】タイミングドリブン設計はこのように全て
のスラック値が正になるまで配線を改善（短く）するこ
とを行なう。詳細は「プロシーディング・オブ・第２２
回・デザイン・オートメーション・カンファレンス、１
９８５、ページ１２４−１３０（Proc. of the 22nd De
sign Automation Conference, 1985, pp.124-130）」に
記述されている。

【００２１】遅延時間を考慮してセル配置を行なう方法
はタイミングドリブン配置と呼び、従来技術として、
「アイ・イー・イー・イー・インターナショナル・カン
ファレンス・オン・コンピュータ・エイディッド・デザ
イン、１９８８、ページ５０６−５０９（Proc. IEEE I
nternational Conference on Computer Aided Design,1
988, pp.506-509）」、「アイ・イー・イー・イー・イ
ンターナショナル・カンファレンス・オン・コンピュー
タ・エイディッド・デザイン、１９９１、ページ４８−
５１（Proc. IEEE International Conference on Compu
ter Aided Design, 1991, pp.48-51）」等が挙げられ
る。

【００２２】また、概略配線ではタイミングドリブン概
略配線を呼び、従来技術として、「アイ・イー・イー・
イー・インターナショナル・カンファレンス・オン・コ
ンピュータ・エイディッド・デザイン、１９９０、ペー
ジ４８−５１（Proc. IEEE International Conference
on Computer Aided Design, 1990, pp.48-51）」等があ
る。

【００２３】ピン配置はタイミングドリブンで行なう例
は少ない。前述のように、セル配置→概略配線→詳細配
線の順番に設計を進めていくが、遅延制約（タイミン
グ）を考慮して遅延違反を起こさないようにする効果が
現れるのはセル配置＞概略配線＞詳細配線の順である。

【００２４】

【発明が解決しようとする課題】設計された半導体ＬＳ
Ｉチップを製造するかどうかを決定する工程として最終
検証シミュレーション、いわゆるバックアノテーション
の工程がある。これは、計算機上で設計されたレイアウ
ト図を基にゲート遅延や配線遅延を見積もって色々な条
件に対して動作シミュレーションを行なうものである。
もし最終検証シミュレーションでエラーになった場合、
レイアウト図を変更することが必要である。これは設計
コストの増大につながる。チップ製造のバラツキを考慮
するためにレイアウト図から求められたゲート遅延や配
線遅延をある一定の範囲内でバラつかせてシミュレーシ
ョンを行なうことが多い。例えば、基準ゲート遅延値と
基準配線遅延値に対して各々２倍かけてシミュレーショ
ンすることである。

【００２５】以上により、実際のチップ設計ではチップ
の製造や使用条件等を考慮するために複数の遅延制約を
満たすことが必要となっている。前述のセル配置技術に
おいて配線遅延の制約は各ネットについてただ１つしか
持たない。そこで、それを解決する方法として最悪の遅
延制約、すなわち配線遅延制約の厳しいもの（配線遅延
値が小さい）で代表してタイミングドリブン配置を行な
う。この方法はクロック設計におけるセットアップ時間
を満足することを意味するが、もう一つの指標であるホ
ールド時間を満足することを保証できず、最終検証シミ
ュレーションでエラーを発生させる可能性が残る。

【００２６】つまり、レイアウト設計では、いちばん遅
いときの時間がセットアップ時間の設計上の要求値より
小さいかどうかが問題となり、また、いちばん早いとき
の時間がホールド時間の設計上の要求値より大きいかど
うかが問題となり、配線遅延制約の厳しいもので代表し
てタイミングドリブン配置を行なうということは前者の
問題には対応しているが、後者の問題には対応できない
ということである。

【００２７】ここで、セットアップ時間とはセル内にデ
ータを格納するまでに必要な時間、例えばフリップフロ
ップにデータをセットし終えるまでの時間である。ま
た、ホールド時間とは、セル内でデータを保持しなけれ
ばならない時間、例えばフリップフロップ内でデータを
最低保持しなければならない時間である。また、前述の
概略配線技術においても配線遅延制約は各ネットについ
てただ１つしか持たない。したがって、セル配置と同じ
課題がある。

【００２８】また、ピン配置技術ではタイミングドリブ
ンで配置することが少ない。ピン配置問題は機能ブロッ
ク間の配線のときに発生する問題であり、未レイアウト
の機能ブロックにおいて（通常ブロックの周辺上に）浮
動外部端子をどこにおけばチップ面積が小さくできるか
という問題である。これまでのピン配置技術は機能ブロ
ック間配線の配線長を最小化できる位置に置くことを目
的としていた。配線遅延を考慮するのはフロアプランに
おける機能ブロック配置の問題として扱い、さらに配線
遅延の制御は機能ブロック間配線経路決定（概略配線）
に委ねられていた。もし配線遅延が厳しい（小さい）場
合は、制約の厳しいネットを有する機能ブロックの配置
を相対的に近付けることで対処する。さらに配線長最小
化を目的とした概略配線を行なって制約に近付ける。し
かし、ピン配置は機能ブロックの周辺上に自由に置くこ
とができるので、概略配線で制御できない大きな変更が
できる可能性がある。よりタイミング制約が厳しいチッ
プ設計ではピン配置の段階でタイミングドリブンで行な
うことが必須になってくる。

【００２９】したがって、この発明の目的は、最終検証
シミュレーションでタイミング違反によるエラーの発生
をなくすことができる自動配置配線方法を提供すること
である。

【００３０】

【課題を解決するための手段】上記課題を解決するため
に、請求項１記載の自動配置配線方法は、半導体集積回
路の構成要素となる複数の機能ブロックまたは複数の論
理セルを配置した後複数の機能ブロックまたは複数の論
理セルの間を論理接続要求に従って配線してレイアウト
設計を行なうことに際し、各々のネットの配線遅延を制
約として複数の論理セルの配置を行なうタイミングドリ
ブン配置による自動配置配線方法であって、各々のネッ
トに対して複数の配線遅延制約をもち、複数の配線遅延
制約を全て満足するように複数の論理セルの配置を行な
うセル配置ステップを含むことを特徴とする。

【００３１】この構成によると、複数の配線遅延制約を
全て満足するように複数の論理セルの配置を行なうの
で、複数の論理セルをタイミング違反を起こさないよう
に配置することができ、最終検証シミュレーションでタ
イミング違反によるエラーの発生をなくすことができ
る。請求項２記載の自動配置配線方法は、請求項１記載
の自動配置配線方法において、セル配置ステップは、複
数の配線遅延の制約を複数の遅延制約グラフ（以下、ス
ラックグラフと呼ぶ）で表現し、それらをスラックグラ
フＧｉ（ｉは自然数）としたときに、スラックグラフＧ
ｉを複数の配線遅延の制約を基に作成するスラックグラ
フ生成ステップと、複数の論理セルを一時的に配置する
セル初期配置ステップと、スラックグラフＧｉを基に複
数の配線遅延の制約を満足できるように複数の論理セル
の配置改善を行なうセル配置改善ステップとを含み、全
てのスラックグラフＧｉで表現した複数の配線遅延の制
約を満足するように順次セル配置改善ステップを繰り返
すことを特徴とする。

【００３２】この構成によると、スラックグラフＧｉを
複数の配線遅延の制約を基に作成し、複数の論理セルを
一時的に配置した後、全てのスラックグラフＧｉを基に
複数の配線遅延の制約を満足できるように複数の論理セ
ルの配置改善を行なうので、複数の論理セルをタイミン
グ違反を起こさないように配置することができ、最終検
証シミュレーションでタイミング違反によるエラーの発
生をなくすことができる。

【００３３】請求項３記載の自動配置配線方法は、半導
体集積回路の構成要素となる複数の機能ブロックまたは
複数の論理セルを配置した後複数の機能ブロックまたは
複数の論理セルの間を論理接続要求に従って配線してレ
イアウト設計を行なうことに際し、各々のネットの配線
遅延を制約として概略配線経路決定を行なうタイミング
ドリブン概略配線による自動配置配線方法であって、各
々のネットに対して複数の配線遅延制約をもち、複数の
配線遅延制約を全て満足するように概略配線経路決定を
行なう概略配線ステップを含むことを特徴とする。

【００３４】この構成によると、複数の配線遅延制約を
全て満足するように概略配線経路決定を行なうので、概
略配線経路決定をタイミング違反を起こさないように行
なうことができ、最終検証シミュレーションでタイミン
グ違反によるエラーの発生をなくすことができる。請求
項４記載の自動配置配線方法は、請求項３記載の自動配
置配線方法において、概略配線ステップは、複数の配線
遅延の制約を複数の遅延制約グラフ（以下、スラックグ
ラフと呼ぶ）で表現し、それらをスラックグラフＧｉ
（ｉは自然数）としたときに、スラックグラフＧｉを複
数の配線遅延の制約を基に作成するスラックグラフ生成
ステップと、概略配線経路を一時的に決定する初期配線
経路決定ステップと、スラックグラフＧｉを基に複数の
配線遅延制約を満足できるように概略配線経路の改善を
行なう配線経路改善ステップとを含み、全てのスラック
グラフＧｉで表現した複数の配線遅延の制約を満足する
ように順次配線経路改善ステップを繰り返すことを特徴
とする。

【００３５】この構成によると、スラックグラフＧｉを
複数の配線遅延の制約を基に作成し、概略配線経路を一
時的に決定した後、全てスラックグラフＧｉを基に複数
の配線遅延制約を満足できるように概略配線経路の改善
を行なうので、概略配線経路をタイミング違反を起こさ
ないように決定することができ、最終検証シミュレーシ
ョンでタイミング違反によるエラーの発生をなくすこと
ができる。

【００３６】請求項５記載の自動配置配線方法は、半導
体集積回路の構成要素となる複数の機能ブロックまたは
複数の論理セルを配置した後複数の機能ブロックまたは
複数の論理セルの間を論理接続要求に従って配線してレ
イアウト設計を行なうことに際し、各々のネットの配線
遅延を制約として未レイアウトの機能ブロックの外部ピ
ン（以下、浮動外部ピンと呼ぶ）の配置を決定するタイ
ミングドリブンピン配置による自動配置配線方法であっ
て、各々のネットに対して複数の配線遅延制約をもち、
複数の配線遅延制約を全て満足するように機能ブロック
上の浮動外部ピンの配置を行なうピン配置ステップを含
むことを特徴とする。

【００３７】この構成によると、複数の配線遅延制約を
全て満足するように機能ブロック上の浮動外部ピンの配
置を行なうので、機能ブロック上の浮動外部ピンをタイ
ミング違反を起こさないように配置することができ、最
終検証シミュレーションでタイミング違反によるエラー
の発生をなくすことができる。請求項６記載の自動配置
配線方法は、請求項５記載の自動配置配線方法におい
て、ピン配置ステップは、複数の配線遅延の制約を複数
の遅延制約グラフ（以下、スラックグラフと呼ぶ）で表
現し、それらをスラックグラフＧｉ（ｉは自然数）とし
たときに、スラックグラフＧｉを複数の配線遅延の制約
を基に作成するスラックグラフ生成ステップと、機能ブ
ロック上の浮動外部ピンを一時的に配置する浮動外部ピ
ン初期配置ステップと、機能ブロック間の概略配線経路
を一時的に決定する浮動外部ピン間初期配線経路決定ス
テップと、スラックグラフＧｉを基に浮動外部ピン間初
期配線経路決定ステップで求めた概略配線経路を保持し
て複数の配線遅延の制約を満足できるように浮動外部ピ
ンの配置を改善する浮動外部ピン配置改善ステップと、
スラックグラフＧｉを基に浮動外部ピン間初期配線経路
決定ステップで求めた概略配線経路が複数の配線遅延制
約を満足できるように概略配線経路を改善する配線経路
改善ステップとを含み、全てのスラックグラフＧｉで表
現した複数の配線遅延の制約を満足するように順次浮動
外部ピン配置改善ステップと配線経路改善ステップとを
繰り返すことを特徴とする。

【００３８】この構成によると、スラックグラフＧｉを
複数の配線遅延の制約を基に作成し、機能ブロック上の
浮動外部ピンを一時的に配置し、機能ブロック間の概略
配線経路を一時的に決定した後、スラックグラフＧｉを
基に概略配線経路を保持して複数の配線遅延の制約を満
足できるように浮動外部ピンの配置を改善するととも
に、スラックグラフＧｉを基に概略配線経路が複数の配
線遅延制約を満足できるように概略配線経路を改善する
ので、浮動外部ピンをタイミング違反を起こさないよう
に配置することができ、最終検証シミュレーションでタ
イミング違反によるエラーの発生をなくすことができ
る。

【００３９】請求項７記載の自動配置配線方法は、半導
体集積回路の構成要素となる複数の機能ブロックまたは
複数の論理セルを配置した後複数の機能ブロックまたは
複数の論理セルの間を論理接続要求に従って配線してレ
イアウト設計を行なうことに際し、各々のネットの配線
遅延を制約として複数の論理セルの配置を行なうタイミ
ングドリブン配置と、各々のネットの配線遅延を制約と
して概略配線経路決定を行なうタイミングドリブン概略
配線と、各々のネットの配線遅延を制約として未レイア
ウトの機能ブロックの外部ピン（以下、浮動外部ピンと
呼ぶ）の配置を決定するタイミングドリブンピン配置と
による自動配置配線方法であって、各々のネットに対し
て複数の配線遅延制約をもち、複数の配線遅延制約を全
て満足するように複数の論理セルの配置を行なうセル配
置ステップと、各々のネットに対して複数の配線遅延制
約をもち、複数の配線遅延制約を全て満足するように配
線経路決定を行なう概略配線ステップと、各々のネット
に対して複数の配線遅延制約をもち、複数の配線遅延制
約を全て満足するように機能ブロック上の浮動外部ピン
の配置を行なうピン配置ステップを含むことを特徴とす
る。

【００４０】この構成によると、請求項１，３，５を組
み合わせたように作用する。請求項８記載の自動配置配
線方法は、請求項７記載の自動配置配線方法において、
セル配置ステップを請求項２と同様に構成している。こ
の構成によると、請求項２と同様に作用する。請求項９
記載の自動配置配線方法は、請求項７記載の自動配置配
線方法において、概略配線ステップを請求項４と同様に
構成している。

【００４１】この構成によると、請求項４と同様に作用
する。請求項１０記載の自動配置配線方法は、請求項７
記載の自動配置配線方法におて、ピン配置ステップを請
求項６と同様に構成している。この構成によると、請求
項６と同様に作用する。

【００４２】

【発明の実施の形態】以下、本発明の実施の形態の自動
配置配線方法について、図面を参照しながら説明する。
本発明の実施の形態は、半導体集積回路の構成要素とな
る複数の機能ブロックまたは複数の論理セルを配置した
後複数の機能ブロックまたは複数の論理セルの間を論理
接続要求に従って配線してレイアウト設計を行なうこと
に際し、各々のネットの配線遅延を制約として複数の論
理セルの配置を行なうタイミングドリブン配置と、各々
のネットの配線遅延を制約として概略配線経路決定を行
なうタイミングドリブン概略配線と、各々のネットの配
線遅延を制約として未レイアウトの機能ブロックの外部
ピン（以下、浮動外部ピンと呼ぶ）の配置を決定するタ
イミングドリブンピン配置の少なくと一つによる自動配
置配線方法を示すものである。本発明の各実施の形態
は、複数のスラックグラフを用いてレイアウト設計を行
なうので、実施の形態の説明に先立って、各々のネット
に対して複数の配線遅延制約をもち、複数の配線遅延制
約を全て満足するように配置もしくは配線を行なうの
で、複数の配線遅延制約、つまり複数のスラックグラフ
について説明する。図６の回路に対する第１のスラック
グラフは、先に説明した図７および図８のtypical 条件
のスラックグラフであるが、それ以外に、図６の回路に
対して、例えば以下に示すような条件の異なる第２から
第５のスラックグラフを作成することが可能である。な
お、スラックグラフの数は任意である。

【００４３】図９は図６（ａ）の回路の図６（ｃ）の配
置結果を基にして作成した第２のスラックグラフの初期
状態を示している。このスラックグラフは、図７のスラ
ックグラフのtypical 条件に対して、セル内遅延とネッ
ト遅延を各々２倍にしたときの初期スラックグラフを示
している。このスラックグラフを条件１下のグラフと定
義する。この条件１下のスラックグラフは、条件０下の
スラックグラフに比べて、それぞれの遅延値を２倍にし
ているので、物理的な意味はチップ全体として製造状態
が悪かった場合を想定していると言える。その後のパス
遅延計算の処理は条件０の場合と同様な方法で行う。

【００４４】図１０は図６（ａ）の回路の図６（ｃ）の
配置結果を基にして作成した第３のスラックグラフの初
期状態を示している。このスラックグラフは、図７のス
ラックグラフのtypical 条件に対して、セル内遅延とネ
ット遅延を各々０．５倍にしたときの初期スラックグラ
フを示している。このスラックグラフを条件２下のグラ
フと定義する。この条件２下のスラックグラフは、条件
０下のスラックグラフに比べて、それぞれの遅延値を
０．５倍にしているので、物理的な意味はチップ全体と
して製造状態が良好であった場合を想定していると言え
る。その後のパス遅延計算の処理は条件０の場合と同様
な方法で行う。

【００４５】図１１は図６（ａ）の回路の図６（ｃ）の
配置結果を基にして作成した第４のスラックグラフの初
期状態を示している。このスラックグラフは、図７のス
ラックグラフのtypical 条件に対して、セル内遅延を
０．５倍、ネット遅延を２倍にしたときの初期スラック
グラフを示している。このスラックグラフを条件３下の
グラフと定義する。この条件３下のスラックグラフは、
条件０下のスラックグラフに比べて、セル内遅延の遅延
値を０．５倍にし、ネット遅延を２倍にしているので、
物理的な意味は、配線領域の製造状態は悪かったが、ト
ランジスタ領域の製造状態は良好だった場合を想定して
いると言える。実際に、配線領域とトランジスタ領域の
縦方向における層数や材料が異なるので、配線領域とト
ランジスタ領域とで製造状態が異なることが十分にあり
得る。その後のパス遅延計算の処理は条件０の場合と同
様な方法で行う。

【００４６】図１２は図６（ａ）の回路の図６（ｃ）の
配置結果を基にして作成した第５のスラックグラフの初
期状態を示している。このスラックグラフは、図７のス
ラックグラフのtypical 条件に対して、ネット遅延を
０．５倍、セル内遅延を２倍にしたときの初期スラック
グラフを示している。このスラックグラフを条件４下の
グラフと定義する。この条件４下のスラックグラフは、
条件０下のスラックグラフに比べて、ネット遅延の遅延
値を０．５倍にし、セル内遅延を２倍にしているので、
物理的な意味は、トランジスタ領域の製造状態は悪かっ
たが、配線領域の製造状態は良好だった場合を想定して
いると言える。その後のパス遅延計算の処理は条件０の
場合と同様な方法で行う。

【００４７】以上の条件１〜４と先の条件０のスラック
グラフを基にそのパス遅延制約を満足するまで、配置の
改善を行なうことになる。この場合、前述したように、
いちばん遅いときの時間がセットアップ時間の設計上の
要求値より小さいかどうかの判断については、条件１と
条件３のスラックグラフにおいて、セットアップ時間の
要求値の条件を検証することができる。また、いちばん
早いときの時間がホールド時間の設計上の要求値より大
きいかどうかの判断については、条件２と条件４のスラ
ックグラフにおいて、ホールド時間の要求値の条件を検
証することができる。以上のように、条件の異なる複数
のスラックグラフを用いて、レイアウト設計を行なう
と、タイミング違反をなくすことが可能で、最終検証シ
ミュレーションでタイミング違反によるエラーの発生を
なくすことが可能となる。

【００４８】（第１の実施の形態）図１は本発明の第１
の実施の形態の自動配置配線方法におけるセル配置に関
するフロー図である。図１３のスタンダードセル方式Ｌ
ＳＩを例にとって説明する。図１３（ａ）がスタンダー
ドセル方式ＬＳＩにおける論理セルを配置する前の状態
を表している。同図左にあるのが配置すべきセル１１群
であり、同図右にあるのが入れられるべきセル列１２
（セル１つ１つの箱をスロットという）の集合からなる
スタンダードセル方式ブロック１０を示している。

【００４９】まず、図１に示すように、遅延制約を基に
図６から図１２までで説明したようなスラックグラフを
作成する（スラックグラフ生成ステップ２）。このとき
（前述のように実際のＬＳＩ設計では）遅延制約が複数
あるので、スラックグラフは複数個存在することにな
る。それをスラックグラフＧｉ（ｉは自然数）とする。
図１３（ｃ）では遅延制約が２つあるときを概略的に示
している（スラックグラフＧ１およびＧ２）。

【００５０】つぎに、初期セル配置ステップ１ａで仮に
セル配置を行なう。このときいずれかの方法で、スラッ
クグラフＧ１を用いてタイミングドリブン配置を行なっ
ても良いが、本実施の形態はスラックグラフＧ１を適用
していない。図１３（ｂ）は配置結果を示しており、そ
の内１ネットだけをハイライトするために白抜きの四角
でセル（セル１１）とその間の接続関係を実線（ネット
１３）で表している。以下、そのネットの動きがスラッ
クグラフＧｉを適用することによってどう変化するか図
示する。

【００５１】セル配置改善ステップ１ｂによって全ての
制約を満足するまでスラックグラフＧｉの適用を続け
る。図１３（ｄ）はスラックグラフＧ１を適用してタイ
ミングドリブン配置改善を行なったときのセル配置結果
である。ネット１３のセル１１の配置分布が若干変化し
たことを示している。つぎに、同図（ｄ）の配置結果を
元にスラックグラフＧ２を適用してタイミングドリブン
配置改善を行なう。さらに、ネット１３のセル１１の配
置分布が同図（ｅ）のように変化した。ここで、２つの
遅延制約を適用して配置改善を行なったが、スラックグ
ラフＧ２による配置改善が行なわれたので、再度スラッ
クグラフＧ１で遅延制約を満足しているかどうか検証す
る。もし満足していればそこで配置は終了する。しかし
遅延制約を満足していなければ、再度スラックグラフＧ
１を基にタイミングドリブン配置改善を行なう。図１３
（ｅ）では遅延制約を満足していないとして配置改善が
なされている。配置結果を図１３（ｆ）に示す。そし
て、同様に今度は同図（ｆ）の配置結果を基にスラック
グラフＧ２で遅延制約を満足しているかどうか検証す
る。もし満足していればそこで配置は終了する。本実施
の形態では満足したとして図１３（ｇ）が最終結果とな
った。

【００５２】この際、スラックグラフＧ１，Ｇ２の適用
されて、セル１１の配置が変更される毎に、スラックグ
ラフＧ１，Ｇ２のネットの配線遅延制約が変更されるこ
とにる。以上の動作で、各々のネットに対して複数の配
線遅延制約をもち、複数の配線遅延制約を全て満足する
ように複数のセルの配置を行なうセル配置ステップ１が
実行されることになる。

【００５３】以上のように、本実施の形態によれば、セ
ル配置の段階でネットの複数の配線遅延制約を満足する
まで配置改善を行なって事前にタイミング違反を除去し
ているので、ＬＳＩ設計の最終検証の段階でのタイミン
グ違反を検出することがなくなり、設計期間の短縮化を
図ることができる。（第２の実施の形態）図２は本発明の第２の実施の形態
の自動配置配線方法における概略配線に関するフロー図
である。

【００５４】図１３（ｇ）のスタンダードセル方式ＬＳ
Ｉにおけるセル配置結果を例にとって説明する。図１４
（ａ）にセル１１とそれにつながるネット１３の接続関
係の状態を表している。また、遅延制約も同様に２つも
のとする。まず、図２に示すように、スラックグラフ生
成ステップ２により遅延制約が２つあるので、スラック
グラフＧ１およびＧ２を生成する（図１４（ｃ））。

【００５５】つぎに、初期配線経路決定ステップ３ａで
仮に概略配線経路を求める。これも初期セル配置ステッ
プ１ａと同様に、いずれかの方法でスラックグラフＧ１
を用いてタイミングドリブン配置を行なってもよいが、
本実施の形態はスラックグラフＧ１を適用していない。
図１４（ｂ）は初期配線経路決定ステップ３ａによる配
線経路結果の一例を示しており、ネット１３だけをハイ
ライトしている。以下、そのネットの動きがスラックグ
ラフＧｉを適用することによってどう変化するか図示す
る。

【００５６】配線経路改善ステップ３ｂによって全ての
配線遅延制約を満足するまでスラックグラフＧｉの適用
を続ける。図１４（ｄ）はスラックグラフＧ１を適用し
てタイミングドリブン概略配線改善を行なったときの概
略配線結果である。ネット１３の配線経路が若干変化し
たことを示している。つぎに、同図（ｄ）の配置結果を
元にスラックグラフＧ２を適用してタイミングドリブン
概略配線改善を行なう。さらに、ネット１３の配線経路
が変化した。ここで、２つの遅延制約を適用して配線経
路改善を行なったが、スラックグラフＧ２による配線経
路改善が行なわれたので、再度スラックグラフＧ１で遅
延制約を満足しているかどうか検証する。もし満足して
いればそこで配線改善は終了する。しかし遅延制約を満
足していなければ、再度スラックグラフＧ１を基にタイ
ミングドリブン概略配線改善を行なう。図１４（ｅ）で
は遅延制約を満足しているとしており、これが最終結果
となる。

【００５７】この際、スラックグラフＧ１，Ｇ２の適用
されて、ネット１３の概略配線が変更される毎に、スラ
ックグラフＧ１，Ｇ２のネットの配線遅延制約が変更さ
れることにる。以上の動作で、各々のネットに対して複
数の配線遅延制約をもち、複数の配線遅延制約を全て満
足するように概略配線経路決定を行なう概略配線ステッ
プ３が実行されることになる。

【００５８】以上のように、本実施の形態によれば、概
略配線の段階で複数の遅延制約を満足するまで配線経路
改善を行なって事前にタイミング違反を除去しているの
で、ＬＳＩ設計の最終検証の段階でのタイミング違反を
検出することがなくなり、設計期間の短縮化を図ること
ができる。（第３の実施の形態）図３は本発明の第３の実施の形態
の自動配置配線方法におけるピン配置に関するフロー図
である。図１５を用いて説明する。

【００５９】図１５（ａ）は未レイアウトの機能ブロッ
ク２３（ソフトブロックと呼び、例えばスタンダードセ
ル方式ブロックで作成）が３つ、レイアウト済み機能ブ
ロック２４（ハードブロックと呼び、例えばメモリ、乗
算器等）が１つ存在するフロアプラン図である。機能ブ
ロック２４には配置位置固定の固定外部ピン２２、機能
ブロック２３には配置位置不定の浮動外部ピン２１を有
している。図では仮に浮動外部ピン２１を機能ブロック
２３の中心に配置している。さらに、それらのピンは同
一ネットであるものとする（ネット２０）。また、遅延
制約も前の実施の形態と同様に２つあるものとする。

【００６０】まず、図３に示すように、スラックグラフ
生成ステップ２により遅延制約が２つあるので、スラッ
クグラフＧ１およびＧ２を生成する（図１５（ｂ））。
これはこれまでの説明と同様である。つぎに、浮動外部
ピン初期配置ステップ４ａによって機能ブロック２３の
浮動外部ピン２１をブロックのある位置（ここではブロ
ックの周辺上）に配置する（図１５（ｃ））。これも図
１の初期セル配置ステップ１ａと同様に、いずれかの方
法でスラックグラフＧ１を用いてタイミングドリブン配
置を行なってもよいが、本実施の形態はスラックグラフ
Ｇ１を適用していない。図１５（ｃ）は浮動外部ピン初
期配置ステップ４ａの実行後のピン配置結果の一例を示
しており、ネット２０だけをハイライトしている。以
下、そのネットの動きがスラックグラフＧｉを適用する
ことによってどう変化するか図示する。

【００６１】浮動外部ピン２１の配置が決まったので、
ネット２０における概略配線を外部ピン間初期配線経路
決定ステップ４ｂで求める。このとき概略配線ステップ
３のときと同様にスラックグラフＧｉを用いてタイミン
グドリブン概略配線を行なう。その結果は図１５（ｄ）
に示される。ここでもし遅延制約が全て（スラックグラ
フＧｉ）満足させることができれば、ここでピン配置を
終了させる。本実施の形態の場合、全ての遅延制約が満
たされなかったとする。

【００６２】つぎに、浮動外部ピン配置改善ステップ４
ｃを用いて浮動外部ピン配置の改善を行なう。このとき
もスラックグラフＧｉに対してタイミングドリブンでピ
ン配置を行なう。タイミングドリブンピン配置はピンを
セルに置き換えてタイミングドリブンセル配置すれば実
現できる。この例の場合、機能ブロック２３の浮動外部
ピン２１が若干移動したことを図示している（同図
（ｅ））。

【００６３】つぎに、そのピンの配置に従って概略配線
経路を決定する。その方法は配置経路改善ステップ３ｂ
と同様である。ここで再度遅延制約が全て満足したかど
うか検証する。もし満足していなかったら、浮動外部ピ
ン配置改善ステップ４ｃかまたは配置経路改善ステップ
３ｂを実行する。遅延の改善（配線経路長の調整）はピ
ン配置の方が効果が高い。何故ならブロック間では配線
チャネル（配線領域）数が多くない場合配線経路長が大
きく変わることが少ないからである。図１５（ｆ）では
遅延制約を満足しているとしており、これが最終結果と
なる。

【００６４】この際、スラックグラフＧ１，Ｇ２の適用
されて、浮動外部ピン配置が変更される毎に、スラック
グラフＧ１，Ｇ２のネットの配線遅延制約が変更される
ことにる。以上の動作で、各々のネットに対して複数の
配線遅延制約をもち、複数の配線遅延制約を全て満足す
るように機能ブロック上の浮動外部ピンの配置を行なう
ピン配置ステップ４が実行されることになる。

【００６５】以上のように本実施の形態によれば、ピン
配置の段階で複数の遅延制約を満足するまでピンの配置
と配線経路の改善を行なって事前にタイミング違反を除
去しているので、ＬＳＩ設計の最終検証の段階でのタイ
ミング違反を検出することがなくなり、設計期間の短縮
化を図ることができる。（第４の実施の形態）図４は本発明の第４の実施の形態
の自動配置配線方法に関するフロー図である。図１６を
用いて説明する。図１６（ａ）は図１５（ａ）と同様な
ものである。ネットの配線が一連の手順によってどう変
化するか図示する。

【００６６】まず、図４に示すように、フロアプランで
は機能ブロックの配置位置決定（機能ブロック配置ステ
ップ５）とブロック間配線経路を考慮しながら未レイア
ウト機能ブロックにおける外部ピンの配置（ピン配置ス
テップ４）を行なうのが主な処理である。図１６（ａ）
は機能ブロック配置ステップ５が終了した時点の結果を
示している。機能ブロック配置の位置は任意に決定でき
る。

【００６７】つぎに、スラックグラフ生成ステップ２に
より遅延制約をスラックグラフＧｉで表現する。そのス
ラックグラフＧｉを用いてピン配置ステップ４を実行す
る。このとき、第３の実施の形態で説明したような手順
でピン配置を決定する。その結果は図１６（ｂ）に示さ
れる。つぎに、外部ピンの配置が決定したので、未レイ
アウトの機能ブロック内のレイアウトを作成する（配置
配線）。ここでは機能ブロック２３を例にとり、スタン
ダードセル方式ブロックで作成するものとする（図１６
（ｃ））。セル配置ステップ１によって、予め設計され
た回路を基に論理セル１１を列上に配置する。配置結果
は同図（ｄ）で示されている。もちろん、配置結果は遅
延制約を全て満たしている。

【００６８】さらに概略配線ステップ３でタイミングド
リブンで概略配線経路を決定する。その結果は同図
（ｅ）に示す（ネット１３だけハイライト）。概略配線
経路が決定したので、それらに対してデザインルールを
満たす配線パターンを生成するために詳細配線ステップ
６を実行する。できた結果は同図（ｆ）に示す。全ての
未レイアウトの機能ブロックに対してそれらのステップ
を実行する。全てのブロックのレイアウトが終了した
ら、機能ブロック間レイアウトを行なう。

【００６９】機能ブロック間レイアウトは、機能ブロッ
ク内レイアウトと同様に概略配線と詳細配線の２つのフ
ェーズをもつ。機能ブロック間の概略配線は機能ブロッ
ク内の概略配線と同様な手続きで実現できる（機能ブロ
ック間概略配線ステップ３＝概略配線ステップ３）。最
後に、デザインルールを満たす配線パターンを生成する
ために機能ブロック間詳細配線ステップ７を実行して処
理が終了する。

【００７０】以上のように、本実施の形態によれば、配
置配線の各段階で複数の遅延制約を満足するまでピンの
配置やセル配置や配線経路の改善を行なって事前にタイ
ミング違反を除去しているので、ＬＳＩ設計の最終検証
の段階でのタイミング違反を検出することがなくなり、
設計期間の短縮化を図ることができる。

【００７１】

【発明の効果】請求項１記載の自動配置配線方法によれ
ば、複数の配線遅延制約を全て満足するように複数の論
理セルの配置を行なうので、複数の論理セルをタイミン
グ違反を起こさないように配置することができ、最終検
証シミュレーションでタイミング違反によるエラーの発
生をなくすことができる。

【００７２】請求項２記載の自動配置配線方法によれ
ば、スラックグラフＧｉを複数の配線遅延の制約を基に
作成し、複数の論理セルを一時的に配置した後、全ての
スラックグラフＧｉを基に複数の配線遅延の制約を満足
できるように複数の論理セルの配置改善を行なうので、
複数の論理セルをタイミング違反を起こさないように配
置することができ、最終検証シミュレーションでタイミ
ング違反によるエラーの発生をなくすことができる。

【００７３】請求項３記載の自動配置配線方法によれ
ば、複数の配線遅延制約を全て満足するように概略配線
経路決定を行なうので、概略配線経路決定をタイミング
違反を起こさないように行なうことができ、最終検証シ
ミュレーションでタイミング違反によるエラーの発生を
なくすことができる。請求項４記載の自動配置配線方法
によれば、スラックグラフＧｉを複数の配線遅延の制約
を基に作成し、概略配線経路を一時的に決定した後、全
てスラックグラフＧｉを基に複数の配線遅延制約を満足
できるように概略配線経路の改善を行なうので、概略配
線経路をタイミング違反を起こさないように決定するこ
とができ、最終検証シミュレーションでタイミング違反
によるエラーの発生をなくすことができる。

【００７４】請求項５記載の自動配置配線方法によれ
ば、複数の配線遅延制約を全て満足するように機能ブロ
ック上の浮動外部ピンの配置を行なうので、機能ブロッ
ク上の浮動外部ピンをタイミング違反を起こさないよう
に配置することができ、最終検証シミュレーションでタ
イミング違反によるエラーの発生をなくすことができ
る。

【００７５】請求項６記載の自動配置配線方法によれ
ば、スラックグラフＧｉを複数の配線遅延の制約を基に
作成し、機能ブロック上の浮動外部ピンを一時的に配置
し、機能ブロック間の概略配線経路を一時的に決定した
後、スラックグラフＧｉを基に概略配線経路を保持して
複数の配線遅延の制約を満足できるように浮動外部ピン
の配置を改善するとともに、スラックグラフＧｉを基に
概略配線経路が複数の配線遅延制約を満足できるように
概略配線経路を改善するので、浮動外部ピンをタイミン
グ違反を起こさないように配置することができ、最終検
証シミュレーションでタイミング違反によるエラーの発
生をなくすことができる。

【００７６】請求項７記載の自動配置配線方法によれ
ば、請求項１，３，５の効果を有する。請求項８記載の
自動配置配線方法によれば、請求項１，２，３，５の効
果を有する。請求項９記載の自動配置配線方法によれ
ば、請求項１，３，４，５の効果を有する。

【００７７】請求項１０記載の自動配置配線方法によれ
ば、請求項１，３，５，６の効果を有する。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態の自動配置配線方法
におけるセル配置のフロー図である。

【図２】本発明の第２の実施の形態の自動配置配線方法
における概略配線のフロー図である。

【図３】本発明の第３の実施の形態の自動配置配線方法
におけるピン配置のフロー図である。

【図４】本発明の第４の実施の形態の自動配置配線方法
における配置配線のフロー図である。

【図５】同期設計の原理を説明する概略図である。

【図６】スラックグラフの概念を説明する概略図であ
る。

【図７】スラックグラフの例を示す概略図である。

【図８】スラックグラフの例を示す概略図である。

【図９】スラックグラフの例を示す概略図である。

【図１０】スラックグラフの例を示す概略図である。

【図１１】スラックグラフの例を示す概略図である。

【図１２】スラックグラフの例を示す概略図である。

【図１３】本発明の第１の実施の形態の自動配置配線方
法におけるセル配置を説明する分解図である。

【図１４】本発明の第２の実施の形態の自動配置配線方
法における概略配線を説明する分解図である。

【図１５】本発明の第３の実施の形態の自動配置配線方
法におけるピン配置を説明する分解図である。

【図１６】本発明の第４の実施の形態の自動配置配線方
法における配置配線を説明する分解図である。

【符号の説明】

１セル配置ステップ１ａ初期セル配置ステップ１ｂセル配置改善ステップ２スラックグラフ生成ステップ３概略配線ステップ３ａ初期配線経路決定ステップ３ｂ配線経路改善ステップ４ピン配置ステップ４ａ初期ピン配置ステップ４ｂ浮動外部ピン間初期配線経路決定ステップ４ｃ浮動外部ピン配置改善ステップ

Claims

【特許請求の範囲】

【請求項１】半導体集積回路の構成要素となる複数の
機能ブロックまたは複数の論理セルを配置した後前記複
数の機能ブロックまたは複数の論理セルの間を論理接続
要求に従って配線してレイアウト設計を行なうことに際
し、各々のネットの配線遅延を制約として前記複数の論
理セルの配置を行なうタイミングドリブン配置による自
動配置配線方法であって、前記各々のネットに対して複数の配線遅延制約をもち、
前記複数の配線遅延制約を全て満足するように前記複数
の論理セルの配置を行なうセル配置ステップを含むこと
を特徴とする自動配置配線方法。
【請求項２】セル配置ステップは、複数の配線遅延の
制約を複数の遅延制約グラフ（以下、スラックグラフと
呼ぶ）で表現し、それらをスラックグラフＧｉ（ｉは自
然数）としたときに、前記スラックグラフＧｉを前記複
数の配線遅延の制約を基に作成するスラックグラフ生成
ステップと、複数の論理セルを一時的に配置するセル初
期配置ステップと、前記スラックグラフＧｉを基に前記
複数の配線遅延の制約を満足できるように前記複数の論
理セルの配置改善を行なうセル配置改善ステップとを含
み、前記全てのスラックグラフＧｉで表現した前記複数
の配線遅延の制約を満足するように順次前記セル配置改
善ステップを繰り返すことを特徴とする請求項１記載の
自動配置配線方法。
【請求項３】半導体集積回路の構成要素となる複数の
機能ブロックまたは複数の論理セルを配置した後前記複
数の機能ブロックまたは複数の論理セルの間を論理接続
要求に従って配線してレイアウト設計を行なうことに際
し、各々のネットの配線遅延を制約として概略配線経路
決定を行なうタイミングドリブン概略配線による自動配
置配線方法であって、前記各々のネットに対して複数の配線遅延制約をもち、
前記複数の配線遅延制約を全て満足するように概略配線
経路決定を行なう概略配線ステップを含むことを特徴と
する自動配置配線方法。
【請求項４】概略配線ステップは、複数の配線遅延の
制約を複数の遅延制約グラフ（以下、スラックグラフと
呼ぶ）で表現し、それらをスラックグラフＧｉ（ｉは自
然数）としたときに、前記スラックグラフＧｉを前記複
数の配線遅延の制約を基に作成するスラックグラフ生成
ステップと、概略配線経路を一時的に決定する初期配線
経路決定ステップと、前記スラックグラフＧｉを基に前
記複数の配線遅延制約を満足できるように前記概略配線
経路の改善を行なう配線経路改善ステップとを含み、前
記全てのスラックグラフＧｉで表現した前記複数の配線
遅延の制約を満足するように順次前記配線経路改善ステ
ップを繰り返すことを特徴とする請求項３記載の自動配
置配線方法。
【請求項５】半導体集積回路の構成要素となる複数の
機能ブロックまたは複数の論理セルを配置した後前記複
数の機能ブロックまたは複数の論理セルの間を論理接続
要求に従って配線してレイアウト設計を行なうことに際
し、各々のネットの配線遅延を制約として未レイアウト
の機能ブロックの外部ピン（以下、浮動外部ピンと呼
ぶ）の配置を決定するタイミングドリブンピン配置によ
る自動配置配線方法であって、前記各々のネットに対して複数の配線遅延制約をもち、
前記複数の配線遅延制約を全て満足するように前記機能
ブロック上の浮動外部ピンの配置を行なうピン配置ステ
ップを含むことを特徴とする自動配置配線方法。
【請求項６】ピン配置ステップは、複数の配線遅延の
制約を複数の遅延制約グラフ（以下、スラックグラフと
呼ぶ）で表現し、それらをスラックグラフＧｉ（ｉは自
然数）としたときに、前記スラックグラフＧｉを前記複
数の配線遅延の制約を基に作成するスラックグラフ生成
ステップと、機能ブロック上の浮動外部ピンを一時的に
配置する浮動外部ピン初期配置ステップと、前記機能ブ
ロック間の概略配線経路を一時的に決定する浮動外部ピ
ン間初期配線経路決定ステップと、前記スラックグラフ
Ｇｉを基に前記浮動外部ピン間初期配線経路決定ステッ
プで求めた概略配線経路を保持して前記複数の配線遅延
の制約を満足できるように前記浮動外部ピンの配置を改
善する浮動外部ピン配置改善ステップと、前記スラック
グラフＧｉを基に前記浮動外部ピン間初期配線経路決定
ステップで求めた概略配線経路が前記複数の配線遅延制
約を満足できるように概略配線経路を改善する配線経路
改善ステップとを含み、前記全てのスラックグラフＧｉ
で表現した前記複数の配線遅延の制約を満足するように
順次前記浮動外部ピン配置改善ステップと前記配線経路
改善ステップとを繰り返すことを特徴とする請求項５記
載の自動配置配線方法。
【請求項７】半導体集積回路の構成要素となる複数の
機能ブロックまたは複数の論理セルを配置した後前記複
数の機能ブロックまたは複数の論理セルの間を論理接続
要求に従って配線してレイアウト設計を行なうことに際
し、各々のネットの配線遅延を制約として前記複数の論
理セルの配置を行なうタイミングドリブン配置と、前記
各々のネットの配線遅延を制約として概略配線経路決定
を行なうタイミングドリブン概略配線と、前記各々のネ
ットの配線遅延を制約として未レイアウトの機能ブロッ
クの外部ピン（以下、浮動外部ピンと呼ぶ）の配置を決
定するタイミングドリブンピン配置とによる自動配置配
線方法であって、前記各々のネットに対して複数の配線遅延制約をもち、
前記複数の配線遅延制約を全て満足するように前記複数
の論理セルの配置を行なうセル配置ステップと、前記各
々のネットに対して複数の配線遅延制約をもち、前記複
数の配線遅延制約を全て満足するように配線経路決定を
行なう概略配線ステップと、前記各々のネットに対して
複数の配線遅延制約をもち、前記複数の配線遅延制約を
全て満足するように前記機能ブロック上の浮動外部ピン
の配置を行なうピン配置ステップを含むことを特徴とす
る自動配置配線方法。
【請求項８】セル配置ステップは、複数の配線遅延の
制約を複数の遅延制約グラフ（以下、スラックグラフと
呼ぶ）で表現し、それらをスラックグラフＧｉ（ｉは自
然数）としたときに、前記スラックグラフＧｉを前記複
数の配線遅延の制約を基に作成するスラックグラフ生成
ステップと、複数の論理セルを一時的に配置するセル初
期配置ステップと、前記スラックグラフＧｉを基に前記
複数の配線遅延の制約を満足できるように前記複数の論
理セルの配置改善を行なうセル配置改善ステップとを含
み、前記全てのスラックグラフＧｉで表現した前記複数
の配線遅延の制約を満足するように順次前記セル配置改
善ステップを繰り返すことを特徴とする請求項７記載の
自動配置配線方法。
【請求項９】概略配線ステップは、複数の配線遅延の
制約を複数の遅延制約グラフ（以下、スラックグラフと
呼ぶ）で表現し、それらをスラックグラフＧｉ（ｉは自
然数）としたときに、前記スラックグラフＧｉを前記複
数の配線遅延の制約を基に作成するスラックグラフ生成
ステップと、概略配線経路を一時的に決定する初期配線
経路決定ステップと、前記スラックグラフＧｉを基に前
記複数の配線遅延制約を満足できるように前記概略配線
経路の改善を行なう配線経路改善ステップとを含み、前
記全てのスラックグラフＧｉで表現した前記複数の配線
遅延の制約を満足するように順次前記配線経路改善ステ
ップを繰り返すことを特徴とする請求項７記載の自動配
置配線方法。
【請求項１０】ピン配置ステップは、複数の配線遅延
の制約を複数の遅延制約グラフ（以下、スラックグラフ
と呼ぶ）で表現し、それらをスラックグラフＧｉ（ｉは
自然数）としたときに、前記スラックグラフＧｉを前記
複数の配線遅延の制約を基に作成するスラックグラフ生
成ステップと、機能ブロック上の浮動外部ピンを一時的
に配置する浮動外部ピン初期配置ステップと、前記機能
ブロック間の概略配線経路を一時的に決定する浮動外部
ピン間初期配線経路決定ステップと、前記スラックグラ
フＧｉを基に前記浮動外部ピン間初期配線経路決定ステ
ップで求めた概略配線経路を保持して前記複数の配線遅
延の制約を満足できるように前記浮動外部ピンの配置を
改善する浮動外部ピン配置改善ステップと、前記スラッ
クグラフＧｉを基に前記浮動外部ピン間初期配線経路決
定ステップで求めた概略配線経路が前記複数の配線遅延
制約を満足できるように概略配線経路を改善する配線経
路改善ステップとを含み、前記全てのスラックグラフＧ
ｉで表現した前記複数の配線遅延の制約を満足するよう
に順次前記浮動外部ピン配置改善ステップと前記配線経
路改善ステップとを繰り返すことを特徴とする請求項７
記載の自動配置配線方法。