JPH07334530A

JPH07334530A - 論理回路の遅延最小化装置及び方法

Info

Publication number: JPH07334530A
Application number: JP6121638A
Authority: JP
Inventors: Koichi Sato; 光一佐藤; Masamichi Kawarabayashi; 政道河原林; Hideyuki Emura; 秀之江村; Naotaka Maeda; 直孝前田
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1994-06-03
Filing date: 1994-06-03
Publication date: 1995-12-22

Abstract

(57)【要約】【目的】面積の増大を抑制するとともに、論理回路の遅
延最小化を図ることのできる論理回路の遅延最小化装置
及び方法を実現する。【構成】本発明は、論理回路のテクノロジマッピングに
使用されるテクノロジライブラリ情報１０１を入力とす
るライブラリ入力手段１００と、論理回路記述１０３を
入力する回路入力手段１０２と、遅延または面積などの
制約条件１０５を入力する制約条件入力手段１０４と、
論理最適化とともにテクノロジ独立のレベルでタイミン
グ解析して最大クリティカルパスを求め、最大クリティ
カルパス上のクラスタのみをパーシャルコラップシング
することにより、制約条件に従って遅延を短縮する論理
最適化手段１０６と、テクノロジライブラリブロックの
マッピングを行うテクノロジマッピング部１０７と、論
理合成された論理回路記述１０９を出力する回路出力手
段１０８とを備えて構成される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は論理回路の遅延量最小化
装置及び方法に関し、特にパーシャルコラップシングを
用いた論理回路の遅延量最小化装置及び方法に関する。

【０００２】

【従来の技術】従来、パーシャルコラップシングを使用
した論理回路の遅延最小化装置としては、例えば、アイ
シーシーエーディ'91(ICCAD-'91)における“Delay Opti
miza−tion of Combinational Logic Circuits Cluster
ing and Partial Collapsing”に見受けられる。なお、
パーシャルコラップシングとは、回路を幾つかの部分回
路に分けて、それぞれにコラップシグ（２段化）を行う
処理のことである。

【０００３】図１２を用いて、従来技術の処理フローに
ついて説明する。先ず、テクノロジライブラリブロック
にマッピングされていないテクノロジ独立な回路が与え
られて、ステップ１２００においては、２入力ＮＡＮＤ
標準形に分解される。図１３に示されるのは、２入力Ｎ
ＡＮＤに分解された後の回路例であり、当該回路はグラ
フの形で表わされ、ノードは組合わせ回路を示し、有向
技は信号線を表わしており、矢印の方向は信号の流れる
方向を表わしている。

【０００４】次に、ステップ１２０１において、ラベリ
ング・クラスタリングが行われ、この処理において、回
路は幾つかのクラスタと呼ばれる部分回路に分けられ
る。各ノードに与えられるラベルは、入力端子からの論
理段数に相当している。このラベリングは、次のように
して行われる。出力端子から入力端子に深さ優先探索が
置こ行われ、並べられたノードの順（以下、トポロジカ
ルな順と云う）にノードが探索されて、各々のノードｖ
に対して、そのファンインの中で最も大きなラベルＬが
求められる。もしも、ノードｖがファンインを持たない
場合には、ノードｖのラベルは０とする。Ｌと同じラベ
ルを持つノードｖのファンイン方向に到達することがで
きる全てのノード（以下、 TFIノード群と云う）の個数
ｋを求めて、ｋの値がクラスタ内のノードの最大数のし
きい値Ｋ（以下、クラスタサイズと云う）を越える場合
に、ノードｖのラベルはＬ＋１とし、越えない場合には
Ｌとする。

【０００５】図１３および図１４を参照して、クラスタ
サイズ３の場合を例にとり説明する。トポロジカルな順
にノードを並べると、ノード１３００、１３０１、１３
０４、１３０２、１３０３、１３０５、１３０６、１３
０８、１３０７、１３０９、１３１０の順になる。先
ず、ノード１３００および１３０１は、ファンインがな
いため、ラベル０となる。次に、ノード１３０４の TFI
ノード群において、ラベルが最大値をとるものはラベル
０のノード１３００および１３０１の２個であり、１３
０４を加えてもクラスタサイズ３以内であるため、ノー
ド１３０４のラベルは０となる。同様に、ノード１３０
２、１３１３および１３０５にラベル０が与えられる。
しかし、ノード１３０６の場合には、 TFIノード群にお
いてラベルの最大値が０であるものはノード１３００〜
１３０５の６個であり、クラスタサイズ３を越えている
ため、ノード１３０６のラベルは１になる。このように
して、同様の処理を繰返して行われて、全てのノードに
ラベルが付けられる。図１４において、ノードの中の数
字はラベルの値を示している。

【０００６】クラスタリングは、次のようにして行われ
る。入力端子から出力端子方向に深さ優先探索が行わ
れ、並べられたノード順（以下、逆トポロジカルの順と
云う）にノードが探索されてゆく。ノードｖのラベル
が、そのファンアウトのノードのラベルよりも小さい場
合には、ノードｖの TFIノード群において、ノードｖと
同じラベルのノードとノードｖにより新しいクラスタが
作成される。ラベリングが異なり、逆トポロジカルな順
なので、ノード１３１０、１３０９、１３０７、１３０
８、１３０６、１３０５、１３０３、１３０２、１３０
４、１３０１、１３００の順に探索が行われる。先ず、
ノード１３１０のファンアウトは存在しないので、クラ
スタ１４０４が作成される。またノード１３１０と等し
いラベルのノード１３１０の TFIノード群は存在しない
ので、ノード１３１０だけのクラスタ１４０４ができ
る。次に、ノード１３０９のラベルがファンアウト１３
１０のラベルよりも小さいので、クラスタ１４０４と異
なるクラスタが作成される。この時、ノード１３０９と
同じラベルの TFIノード群は、ノード１３０６および１
３０７であり、この三つのノードによりクラスタ１４０
３が作成される。図１４において、破線にて示される各
領域に対応するクラスタ１４００、１４０１、１４０
２、１４０３および１４０４がクラスタリングの結果で
ある。

【０００７】このようにしてできた全てのクラスタに対
して、ステップ１２０２においては、コラップシングが
行われる。各クラスタの中で最も出力側にあるノードに
対して、クラスタ内の全てのノードに対するコラップシ
ングが行われる。この時に、複数のクラスタに所属する
ノードは、重複してコラップシング処理される。上述の
図１４に示されるクラスタ１４００、１４０１、１４０
２、１４０３および１４０４に対するコラップシングが
行われると、図１５に示されるように、ノード１５００
〜１５０４にまとめられて、入力端子から出力端子まで
の論理段数が削減されたことになる。

【０００８】

【発明が解決しようとする課題】上述した従来の論理回
路の遅延最小化装置及び方法においては、論理最適化を
図る場合に、全てのクラスタに対するコラップシングが
行われている。この場合に、複数のクラスタに所属する
ノードがある場合には、当該ノードを重複する必要があ
り、その分所要面積が増大する。従って、最大遅延値を
短かくすることにおいては、最大クリティカルパス上に
ないクラスタまでコラップシング処理が行われるため
に、不必要な面積増加が生じるという欠点がある。

【０００９】また、従来は、テクノロジ独立な回路にお
いてのみパーシャルコラップシングを適用することを考
えており、従って、テクノロジマッピングされた回路に
直接適用することができないという欠点がある。

【００１０】

【課題を解決するための手段】本発明の論理回路の遅延
最小化装置は、論理回路のテクノロジマッピングに用い
るテクノロジライブラリ情報を入力するライブラリ入力
手段と、前記論理回路に対応する論理回路記述を入力す
る回路入力手段と、前記論理回路による遅延および占有
面積等を含む制約条件を入力とする制約条件入力手段
と、論理最適化処理を行うとともに、最大クリティカル
パス上のクラスタのみをパーシャルコラップシングする
ことにより、遅延を最小化することができる機能を有す
る論理最適化手段と、前記論理回路による遅延および占
有面積等を含む制約条件を考慮したテクノロジライブラ
リブロックのマッピングを行うとともに、最大クリティ
カルパス上のクラスタに対してのみパーシャルコラップ
シングすることにより、前記遅延を最小化する機能を有
するテクノロジマッピング手段と、論理合成された論理
回路を出力する回路出力手段と、を少なくとも備えるこ
とを特徴としている。

【００１１】また、第１の発明の論理回路の遅延最小化
方法は、前記論理回路の遅延最小化装置に含まれる論理
最適化手段において、テクノロジ独立のレベルにおいて
論理回路に対するタイミング解析を行い、当該論理回路
に対応する最大クリティカルパスを求める第１のステッ
プと、前記第１のステップにおいて、前記論理回路の入
力回路における要求時刻が一つでも満たされていない場
合に、ラベリング・クラスタリングを行ってコラップシ
ングするクラスタを作成する第２のステップと、最大ク
リティカルパス上のクラスタのみを選択してパーシャル
コラップシングする第３のステップと、前記論理回路に
よる遅延および占有面積等を含む制約条件に従って、当
該遅延が短縮されたか否かを判定する第４のステップ
と、を少なくとも有することを特徴としている。

【００１２】また、第２の発明の論理回路の遅延最小化
方法は、前記論理回路の遅延最小化装置に含まれるテク
ノロジマッピング手段において、テクノロジライブラリ
ブロックの遅延データを使用して論理回路に対するタイ
ミング解析を行い、当該論理回路に対応する最大クリテ
ィカルパスを求める第１のステップと、前記第１のステ
ップにおいて、前記論理回路の入力回路における要求時
刻が一つでも満たされていない場合に、ラベリング・ク
ラスタリングを行ってコラップシングするクラスタを作
成する第２のステップと、最大クリティカルパス上のコ
ラップシング対象となるクラスタのみを選択してテクノ
ロジ独立化する第３のステップと、最大クリティカルパ
ス上のクラスタのみを選択してパーシャルコラップシン
グする第４のステップと、コラップシングした部分回路
を再度テクノロジマッピンクする第５のステップと、前
記論理回路による遅延および占有面積等を含む制約条件
に従って、当該遅延が短縮されたか否かを判定する第６
のステップと、を少なくとも有することを特徴としてい
る。

【００１３】

【実施例】次に、本発明について図面を参照して説明す
る。

【００１４】図１は本発明の第１の実施例を示すブロッ
ク図である。図１に示されるように、本実施例は、論理
回路のテクノロジマッピングに使用されるテクノロジラ
イブラリ情報１０１を入力とするライブラリ入力手段１
００と、論理回路記述１０３を入力する回路入力手段１
０２と、遅延または面積などの制約条件１０５を入力す
る制約条件入力手段１０４と、論理最適化とともにテク
ノロジ独立のレベルでタイミング解析して最大クリティ
カルパスを求め、最大クリティカルパス上のクラスタの
みをパーシャルコラップシングすることにより、制約条
件に従って遅延を短縮する論理最適化手段１０６と、テ
クノロジライブラリブロックのマッピングを行うテクノ
ロジマッピング部１０７と、論理合成された論理回路記
述１０９を出力する回路出力手段１０８とを備えて構成
される。また、図２は、本実施例における処理手順を示
すフローチャートである。

【００１５】次に、図２を参照して、図１における最適
化処理手段１０６の動作について説明する。なお、図６
は、本実施例における入力論理仕様を示す図であり、遅
延制約として入力側のノード６００、６０１、６０２お
よび６０３の入力信号の到着時刻arvlが、それぞれ１２
０、１２０、１２０、０に設定され、また出力側ノード
６０９および６１１の要求時刻req が、それぞれ１５
０、１５０に設定されて、クラスタサイズ４が設定され
ている。

【００１６】最初にステップ２００においてはタイミン
グ解析が実行される。図６のノード中に示される数字は
リテラル数を示す。ここで云うタイミング解析とは、各
パスの最大遅延値の計算を意味している。これは、各ノ
ードに入力される信号の中で最も遅くノードの出力側に
到達する信号の到着時刻をパスの入力側から順に加算し
た値である。テクノロジ独立の場合には、各ノードの遅
延計算式としては、次式が用いられる。

【００１７】 d ＝ａ₀＋ａ₁lnｃ＋ａ₂lnｆ………………ォ…（１）これは、アイシーシーエーディ'90(ICCD-'90) における
“ High-Level DelayEstimation for Technology-Indep
ndent Logic Equations”において示されている方法で
ある。上記（１）式において、ｄはノードの遅延、ｃは
論理関数の複雑度、ｆはノードのファンアウト数を表わ
している。ａ₀、ａ₁およびａ₂は、テクノロジ依存の
パラメータである。テクノロジ依存のパラメータであ
る。テクノロジ依存のパラメータは、与えられているマ
ッピング対象とするテクノロジライブラリに依存してい
る。このパラメータは、予め、多くの回路を実際にマッ
ピングした時の遅延時間を統計的に処理して算出してお
く。ここにおいて、全てのノードのリテラル数と論理関
数の複雑度とが等しいものと仮定して、テクノロジ依存
パラメータが、ａ₀＝３０、ａ₁＝６０、ａ₂＝１０で
あるものとすると、図７に示されている出力側のノード
６０９の到着時刻arvl、要求時刻req およびスラックsl
ack(req からarvlを減算した値）は、それぞれarvl＝３
６６、req ＝１５０、slack ＝−１１６となり、ノード
６１１は、それぞれarvl＝５２６、req＝１５０、slack
＝−３７６となる。ここにおいて、スラックに負の出
力のものが存在しない場合には、ステップ２００におい
て入力回路の要求時刻が全て満たされているものとし
て、論理最適化手段１０６における処理は終了する。な
お、以下の説明においても、テクノロジ依存のパラメー
タの数値例としては、上記のａ₀＝３０、ａ₁＝６０、
ａ₂＝１０を使用するものとする。

【００１８】一方、一つでもslack に負の出力端子が存
在する場合には、ステップ２００において入力回路の要
求時刻が全て満たされてはいないものとして、次のステ
ップ２０１に移行し、ステップ２０１において、ラベリ
ング・クラスタリングが行われる。図３は、このラベリ
ング・クラスタリングの処理ステップを示すフローチャ
ートである。以下、当該ラベリング・クラスタリングの
処理ステップについて説明する。

【００１９】図３において、先ずステップ３００におい
て、ラベリング・クラスタリングが行われたことがある
か否かの判定処理が行われる。既に当該判定処理が行わ
れたことがある場合には、ラベリンク・クラスタリング
処理は終了する。一方未だラベリンク・クラスタリグ処
理が行われたことがない場合には、ステップ３０１にお
いて、占有クラスタ数とスタートラベルの設定が行われ
る。本発明においては、２入力ＮＡＮＤに分解してノー
ドを同じ大きさに揃えないように、クラスタサイズをリ
テラル数により評価して、クラスタの大きさを揃えるこ
とにする。しかし、クラスタサイズをリテラル数で評価
すると、一つのノードでクラスサイズＫを越える場合が
あり得る。このため、一つのノードが占める占有クラス
タ数levを計算することが必要となる。ノードのリテラ
ル数がクラスタサイズＫ以内の場合には、占有クラス数
lev ＝１とする。ノードのリテラル数がクラスサイズＫ
以上の場合には、次式により占有クラスタ数lev を計算
する。

【００２０】 lev ＝（ａ₀＋ａ₁lnｃ）／（ａ₀＋ａ₁lnＫ）…………（２）上式により、ノードｖの占有クラスタ数lev(ｖ) を、小
数点以下、四捨五入して整数化して計算する。ｃは論理
複雑度である。ａ₀およびａ₁は式（１）における遅延
パラメータであり、Ｋはクラスタサイズである。クラス
タサイズＫ＝４の時には、ノード６１１のリテラル数１
３が４より大きいので、上記の（２）式による計算によ
り、lev ＝２となる。このノード以外においては、lev
＝１である。

【００２１】本実施例においては、入力端子の到着時刻
が異なる場合をも考慮して、入力端子のラベルがalevか
ら始まるものとする。この場合、当該alevの値は、次式
により計算して求められる（小数点以下を四捨五入して
整数化する）。

【００２２】 alev＝（arrival time) ／（ａ₀＋ａ₁lnＫ）………（３）上式において、arrival timeは入力端子の到着時刻であ
り、ａ₀およびａ₁は前記（１）式における遅延パラメ
ータ、Ｋはクラスタサイズである。但し、入力端子以外
はalev＝０となる。ノード６００、６０１、６０２およ
び６０３の値は図７に示されるarvlがarrival timeとな
り、従って、上記（３）式より、これらのノード６０
０、６０１、６０２および６０３の値は、図８に示され
るように、それぞれalev＝１、alev＝１、alev＝１およ
びalev＝０となる。

【００２３】次に、ステップ３０２においては、ラベリ
ングが行われる。ラベリングは、従来技術の場合と同様
であるが、本発明においては、スタートラベルは０では
なくalevとし、隣接するクラスタのラベルの差は１では
なくlev で処理される。次いで、ステップ３０３におい
てクラスタリング処理が行われるが、このクラスタリン
グの処理内容は、前述の従来例におけるクラスタリング
と同様の処理内容であるため、ここでは説明を省略す
る。なお、図７に示される入力回路のタイミング解析の
内容に対応して、ラベリング処理ならびにクラスタリン
グ処理が行われた結果が図９に示されており、破線で囲
まれた領域がクラスタに相当する。

【００２４】次に、図２に戻り、ステップ２０２におい
てはコラップシングが行われる。このコラップシング処
理の内容は図４のフローチャートに示されており、先
ず、ステップ４００において、コラップシングするクラ
スタの選択が行われる。従来技術においては、全てのク
ラスタに対してコラップシングが行われているが、本発
明においては、最大クリティカルパス上のクラスタが選
択されてコラップシングされる。図９に示される本実施
例における回路の最大クリティカルパスを、図１０のク
ラスタ選択図の太矢印で示されるパスであるものとす
る。この場合には、クラスタ９０２および９０６が最大
クリティカルパス上のクラスタであり、二つ以上のノー
ドを持つため、コラップシングの候補となる。コラップ
シングするクラスタは、下記（４）式により評価関数が
最小値となるクラスタが選択される。

【００２５】

【００２６】上記（４）式による評価値は、スラック最
小のノードに対して求められる。クラスタが複数の最大
クリティカルパス上にある場合には、その多くのパス上
にスラック最小のノードが存在しており、コラップシン
グにより重複する可能性の低いクラスタが選択される。
slack(c)i は、クラスタｃのスラックが、そのファンア
ウト方向に到達することのできる全てのノード（以下、
TFO ノードと云う）の中のｉ番目の出力端子のスラック
と等しい時に、その出力端子のスラックとなり、等しく
ない時には０となる。また、ｎ(c) は、クラスタｃのTF
O ノードとなる出力端子の数であり、dulp(c) は、クラ
スタの重複するノードのリテラル数総和である。αおよ
びβは、遅延時間と面積のどちらに重きをおくかを表わ
す係数であり、αが大きくなると遅延時間の注目度が高
くなり、βが大きくなると面積の注目度が高くなる。本
実施例において、α＝１、β＝１の時には、value の値
としては、クラスタ９０２がvalue ＝−３７６＋０＝−
３７６となり、クラスタ９０６はvalue ＝−３７６＋２
＝−３７４となるので、クラスタ９０２は選択される。
次に、ステップ４０１において、クラスタ選択判定処理
が行われる。なお、ステップ４００において、クラスタ
が一つも選択されなかった場合には、コラップシング処
理が全て終了となる。一方、ステップ４００において、
クラスタが選択された場合には、ステップ４０２におい
て、コラップシング処理が実行され、当該コラップシン
グ処理は終了する。これにより、図１に示される論理最
適化手段１０６による処理は全て終了となる。

【００２７】図２に戻って、ステップ２０３においては
遅延改善判定処理が行われる。図５は、この遅延改善判
定処理の処理ステップを示すフローチャートである。以
下、当該遅延改善判定処理の処理ステップについて説明
する。図５において、先ずコラップシングしたノードの
到着時刻が前記（１）式により計算され、ステップ５０
０において到着時刻判定が行われる。ステップ５００に
おいて遅延が改善されている場合には、当該遅延改善判
定処理は終了となり、一方、遅延が改善されていない場
合には、ステップ５０１に移行して、コラップシング処
理前の回路に対する復帰処理が行われ、図２に示される
ステップ２００に戻る。図２において、ステップ２０３
の遅延改善判定処理の終了により、再度ステップ２００
より繰返して処理が続行されるが、ステップ２０３にお
いて復帰処理されたクラスタは、以降のクラスタ選択処
理における選択対象からは除外されて処理が継続され
る。そして、ステップ２００において、入力回路の要求
時刻が全て満たされている場合、またはステップ２０２
において、評価関数が最小値となるクラスタが選択され
なかった場合には、全ての処理は終了する。

【００２８】次に、本発明の第２の実施例について説明
する。本実施例は、基本的な構成については、前述の第
１の実施例と同様であり図１に示されるとうりである
が、テクノロジ依存の回路を扱うという点において第１
の実施例とは異なっている。また、処理上の点について
は、図１に示されるテクノロジマッピング手段１０７に
おいて、パーシャルコラップシングが適用されて、テク
ノロジライブラリブロックデータを用いたタイミング解
析が使用されている。また、図２の処理フロー、図３の
ラベリング・クラスタリング処理フローおよび図５の遅
延改善判定処理フローに示される第１の実施例における
各処理フローについては、本実施例の場合においても全
く同一の処理フローとなるが、図４の第１の実施例にお
けるコラップシング処理フローのみが本実施例の場合と
は異なっている。第１の実施例の図４に対応する本実施
例のコラップシング処理フローは、図１１の処理フロー
に示されるとうりであり、図４と図１１との対比により
明らかように、図１１においては、ステップ４０２の前
の処理ステップにおいて、コラップシングするノードを
テクノロジ独立化させるステップ１１００と、ステップ
４０２の後に、コラップシングしたノードをマッピング
するステップ１１０１とが付加されている点に差異があ
る。

【００２９】本実施例のコラップシング処理フローにつ
いては、図１１において、先ず、ステップ４００におい
て、コラップシングするクラスタの選択が行われる。次
に、ステップ４０１において、クラスタの選択判定処理
が行われる。なお、ステップ４００において、クラスタ
が一つも選択されなかった場合には、コラップシング処
理が全て終了となる。一方、ステップ４００において、
クラスタが選択された場合には、ステップ１１００にお
いて、コラップシングするノードがテクノロジ独立化さ
れてステップ４０２に移行し、ステップ４０２において
は、コラップシング処理が実行される。次いで、ステッ
プ１１０１において、コラップシングされたノードがマ
ッピングされて、当該コラップシング処理は終了する。
これにより、図１に示される論理最適化手段１０６によ
る処理は全て終了となる。

【００３０】そして、更に、このマッピング処理の部分
においては、当該マッピング処理に対して別個の遅延最
適化手法を適用することも可能である。

【００３１】なお、本発明の適用による実験の結果によ
れば、１００〜１０００ゲート程度の回路に対して、従
来技術に比較して、平均２％、最大１２％程度の面積の
縮小が可能となっている。

【００３２】

【発明の効果】以上説明したように、本発明は、テクノ
ロジマッピングすることにより、所定の制約条件に従っ
て論理回路の遅延が短縮されるために、テクノロジ独立
のタイミング解析を用いて最大クリティカルパスを求
め、当該最大クリティカルパス上のクラスタのみをパー
シャルコラップシングすることにより、最大遅延の短縮
に影響を及ぼすことのないクラスタをコラップシング処
理することが排除され、これにより、所要面積の増大を
防止することができるとともに、テクノロジマッピング
された回路に対しても、直接的に適用することできるい
う効果がある。

【図面の簡単な説明】

【図１】本発明の第１および第２の実施例を示すブロッ
ク図である。

【図２】第１の実施例の処理フローを示す図である。

【図３】第１の実施例のラベリング・クラスタリング処
理フローを示す図である。

【図４】第１の実施例のコラップシング処理フローを示
す図である。

【図５】第１の実施例の遅延改善判定処理フローを示す
図である。

【図６】第１の実施例の入力論理仕様を示す図である。

【図７】第１の実施例の入力回路のタイミング解析を示
す図である。

【図８】第１の実施例の占有クラスタ数とスタートラベ
ルの設定を示す図である。

【図９】第１の実施例のラベリング・クラスタリングを
示す図である。

【図１０】第１の実施例のクラスタ選択を示す図であ
る。

【図１１】本発明の第２の実施例の処理フローを示す図
である。

【図１２】従来例の処理フローを示す図である。

【図１３】従来例の２入力ＮＡＮＤ標準形に分解する図
である。

【図１４】従来例のラベリング・クラスタリングを示す
図である。

【図１５】従来例のコラップシングを示す図である。

【符号の説明】

１００ライブラリ入力手段１０１テクノロジライブラリ情報１０２回路入力手段１０３、１０９論理回路記述１０４制約条件入力手段１０５制約条件１０６論理最適化手段１０７テクノロジマッピング手段１０８回路出力手段２００タイミング解析２０１、１２０１ラベリング・クラスタリング２０２、３０２、４０２、１２０２コラップシング２０３遅延改善判定３００ラベリング・クラスタリング判定処理３０１占有クラスタ数とスタートラベルの設定３０３クラスタリング４００クラスタ選択４０１クラスタ選択判定５００到着時刻判定５０１復帰処理６００〜６１１、１３００〜１３１０、１５００〜１５
０４ノード９００〜９０７、１４００〜１４０４クラスタ１１００テクノロジ独立化１１０１マッピング１２００２入力ＮＡＮＤ標準形に分解

───────────────────────────────────────────────────── フロントページの続き (72)発明者前田直孝東京都港区芝五丁目７番１号日本電気株式会社内

Claims

【特許請求の範囲】

【請求項１】論理回路のテクノロジマッピングに用い
るテクノロジライブラリ情報を入力するライブラリ入力
手段と、前記論理回路に対応する論理回路記述を入力する回路入
力手段と、前記論理回路における遅延および占有面積等を含む制約
条件を入力とする制約条件入力手段と、論理最適化処理を行うとともに、最大クリティカルパス
上のクラスタのみをパーシャルコラップシングすること
により、遅延を最小化することができる機能を有する論
理最適化手段と、前記論理回路による遅延および占有面積等を含む制約条
件を考慮したテクノロジライブラリブロックのマッピン
グを行うとともに、最大クリティカルパス上のクラスタ
に対してのみパーシャルコラップシングすることによ
り、前記遅延を最小化する機能を有するテクノロジマッ
ピング手段と、論理合成された論理回路を出力する回路出力手段と、を少なくとも備えることを特徴とする論理回路の遅延最
小化装置。
【請求項２】前記論理回路の遅延最小化装置に含まれ
る論理最適化手段において、テクノロジ独立のレベルにおいて論理回路に対するタイ
ミング解析を行い、当該論理回路に対応する最大クリテ
ィカルパスを求める第１のステップと、前記第１のステップにおいて、前記論理回路の入力回路
における要求時刻が一つでも満たされていない場合に、
ラベリング・クラスタリングを行ってコラップシングす
るクラスタを作成する第２のステップと、最大クリティカルパス上のクラスタのみを選択してパー
シャルコラップシングする第３のステップと、前記論理回路における遅延および占有面積等を含む制約
条件に従って、当該遅延が短縮されたか否かを判定する
第４のステップと、を少なくとも有することを特徴とする論理回路の遅延最
小化方法。
【請求項３】前記論理回路の遅延最小化装置に含まれ
るテクノロジマッピング手段において、テクノロジライブラリブロックの遅延データを使用して
論理回路に対するタイミング解析を行い、当該論理回路
に対応する最大クリティカルパスを求める第１のステッ
プと、前記第１のステップにおいて、前記論理回路の入力回路
における要求時刻が一つでも満たされていない場合に、
ラベリング・クラスタリングを行ってコラップシングす
るクラスタを作成する第２のステップと、最大クリティカルパス上のコラップシング対象となるク
ラスタのみを選択してテクノロジ独立化する第３のステ
ップと、最大クリティカルパス上のクラスタのみを選択してパー
シャルコラップシングする第４のステップと、コラップシングした部分回路を再度テクノロジマッピン
クする第５のステップと、前記論理回路による遅延および占有面積等を含む制約条
件に従って、当該遅延が短縮されたか否かを判定する第
６のステップと、を少なくとも有することを特徴とする論理回路の遅延最
小化方法。