JPH07129657A

JPH07129657A - 論理最適化装置

Info

Publication number: JPH07129657A
Application number: JP5294039A
Authority: JP
Inventors: Yuji Kobayashi; 祐次小林
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1993-10-29
Filing date: 1993-10-29
Publication date: 1995-05-19
Anticipated expiration: 2012-07-30
Also published as: JP2636709B2

Abstract

(57)【要約】【目的】論理回路の最適化装置に於いて、処理速度を
高速化する。【構成】最適化ルールベース36中のルールはルールソ
ート手段25によって適用回数順にソートされている。ル
ール分離手段21は、最適化ルールベース36中のルールの
内、遅延優先モードのルールを遅延優先ルールベース38
に、面積優先のルールを面積優先ルールベース39に格納
する。遅延優先最適化手段22は、最適化の対象とする論
理回路の出力端子の内の出力端子表37に遅延優先の設定
がある出力端子に対して遅延優先ルールベース38中のル
ールを蓄積順に評価し、適用可能なルールであればそれ
を適用して最適化する処理を、遅延目標値をクリアする
まで続ける。面積優先最適化手段23は、出力端子表37に
面積優先の設定がある出力端子に対して面積優先ルール
ベース39中のルールを蓄積順に評価し、適用可能なルー
ルであればそれを適用して最適化するという処理を、面
積目標値をクリアするまで続ける。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、最適化ルールベース中
のルールに従って論理回路中の素子の置き換えを行なう
ことにより、遅延時間，面積の最適化を図る論理最適化
装置に関する。

【０００２】

【従来の技術】最適化の対象とする論理回路の接続情報
を入力し、最適化ルールベースに蓄積されているルール
に順次適用し、遅延時間，面積を最適化する論理最適化
装置は従来から提案されている。

【０００３】図１２〜図１５は、論理最適化装置によっ
て行なわれる最適化の様子を示した図である。図１２〜
図１５に於いて、ＩＮ１〜ＩＮ４は入力端子、ＯＵＴ
１，ＯＵＴ２は出力端子、ＩＮＶ１〜ＩＮＶ４はインバ
ータ、ＡＮＤ１，ＡＮＤ２はアンド回路、ＮＡＮＤ１，
ＮＡＮＤ２はナンド回路、ＮＯＲ１はノア回路、ＯＲ１
はオア回路を示している。

【０００４】図１２は論理最適化装置に入力された接続
情報が示す論理回路の回路図であり、この論理回路は最
適化ルールベース中のルールが順次適用されることによ
り、図１３〜図１５に示す論理回路に順次変化してい
く。

【０００５】図１３は、図１２の論理回路に対して出力
にインバータが接続されているナンド回路をアンド回路
に置き換えるルールを適用した後の論理回路を示し、図
１２中のナンド回路ＮＡＤ１とインバータＩＮＶ４と
が、図１３ではアンド回路ＡＮＤ２に置き換えられてい
る。

【０００６】図１４は、図１３の論理回路に対して両方
の入力にインバータが接続されているアンド回路をノア
回路に置き換えるルールを適用した後の論理回路を示
し、図１３中のインバータＩＮＶ１，ＩＮＶ２とアンド
回路ＡＮＤ１とが、図１４ではノア回路ＮＯＲ１に置き
換えられている。

【０００７】図１５は、図１４の論理回路に対して出力
にインバータが接続されているノア回路をオア回路に置
き換えるルールを適用した後の論理回路を示し、図１４
中のノア回路ＮＯＲ１とインバータＩＮＶ３とがオア回
路ＯＲ１に置き換えられている。

【０００８】このような最適化を行なうことにより、素
子数が減り、遅延時間の短縮，面積の縮小を図ることが
可能になる。

【０００９】図１６は従来の論理最適化装置の構成例を
示したブロック図であり、キーボード等の入力部１６１
と、論理最適化手段１６２と、最適化の結果をファイル
等に出力する出力部１６３と、接続情報記憶部１６５及
び最適化ルールベース１６６を含む記憶部１６４とから
構成されている。

【００１０】利用者は最適化を行なう場合、先ず、最適
化を行なう論理回路の接続情報を入力部１６１を用いて
接続情報記憶部１６５に格納し、その後、論理最適化手
段１６２を起動する。

【００１１】論理最適化手段１６２は起動されると、図
１７の流れ図に示すように、先ず、接続情報によって示
される論理回路中の第１番目の出力端子に注目する (ス
テップＳ１７１，Ｓ１７２）。

【００１２】次いで、論理最適化手段１６２は、図１８
に示すように、複数のルールが蓄積されている最適化ル
ールベース１６６中の第１番目のルールに注目する (ス
テップＳ１７４，Ｓ１７５）。

【００１３】その後、論理最適化手段１６２は、第１番
目の出力端子から入力端子に向かってパストレースを行
ない (ステップＳ１７８）、第１番目のルールを適用で
きる部分が存在するか否かを判断する (ステップＳ１７
９）。

【００１４】適用できる部分が存在しないと判断した場
合は、第２番目のルールに注目し (ステップＳ１８２，
Ｓ１７５）、前述したと同様の処理を行なう。

【００１５】また、適用できる部分が存在すると判断し
た場合は、第１番目のルールに従って素子の置き換えを
行ない (ステップＳ１８０）、置き換え後のパスが遅延
目標値等の目標をクリアしているか否かを判断する (ス
テップＳ１８１）。

【００１６】そして、目標をクリアしていると判断した
場合は第２番目の出力端子に注目し(ステップＳ１７
７，Ｓ１７２）、前述したと同様の処理を行なう。

【００１７】また、目標をクリアしていないと判断した
場合は、第２番目のルールに注目し(ステップＳ１８
２，Ｓ１７５）、前述したと同様の処理を行なう。

【００１８】そして、全てのルールに対して前述した処
理を行なうと (ステップＳ１７６がＹＥＳ）、論理最適
化手段１６２は、第２番目の出力端子に注目し (ステッ
プＳ１７７，Ｓ１７２）、前述したと同様の処理を行な
う。

【００１９】以下、論理最適化手段１６２は、第３番
目，第４番目，…の出力端子に対して前述したと同様の
処理を行ない、全ての出力端子に対して前述した処理を
行なうと (ステップＳ１７３がＹＥＳ）、その処理を終
了する。

【００２０】

【発明が解決しようとする課題】上述したように、従来
は、遅延目標値等の目標がクリアされるまで、最適化デ
ータベースに蓄積されているルールの内、適用可能なル
ールを蓄積順に適用して最適化を行なっているが、次の
ような問題があった。

【００２１】即ち、従来は、最適化ルールベースへのル
ールの蓄積順を設計者が経験に頼って決定していたた
め、適用頻度の多いルールの蓄積順が適用頻度の少ない
ルールよりも後になることがある。このような場合、適
用不可能と判断される可能性が高い適用回数の少ないル
ールに対する処理が、適用可能と判断される可能性が高
い適用回数の多いルールに対する処理よりも前に行なわ
れることになるため、最適化目標をクリアするまでに参
照しなければならないルールの数が増え、最適化に要す
る時間が多くなるという問題がある。

【００２２】また、ルールには、遅延時間を最適化する
ために有効なルール，面積を最適化するために有効なル
ール，遅延時間と面積の両方を最適化するために有効な
ルールが存在するが、従来は、これらのルールが混在し
ている最適化ルールベースを使用して論理回路の最適化
を行なっているため、遅延制約の厳しい論理回路の最適
化を行なう場合、面積を最適化するためのルールが適用
されることによって遅延制約をクリアできない事態が発
生する場合がある。

【００２３】そこで、遅延制約の厳しい論理回路の最適
化を行なう場合は、遅延時間を最適化するためのルール
だけを適用して最適化を行なうということが提案されて
いる。

【００２４】しかし、この方法は、最適化の対象とする
論理回路全体に対して遅延時間最適化用のルールを選択
しているため、遅延制約の厳しい論理回路中に遅延制約
の厳しくないパスが存在している場合であっても、上記
パスに対して遅延を最適化するためのルールが適用さ
れ、面積を最適化するためのルールは適用されないた
め、論理回路の規模が大きくなってしまうという問題が
ある。

【００２５】本発明の目的は、論理回路の最適化処理に
要する時間を短縮させることができ、且つ、遅延制約の
厳しい論理回路を最適化する場合であっても遅延制約の
必要のないパスが存在する論理回路については回路規模
を小さくすることができる論理最適化装置を提供するこ
とにある。

【００２６】

【課題を解決するための手段】本発明は、最適化処理に
要する時間を短縮させるために、（Ａ）論理最適化を行
なうためのルールが蓄積された最適化ルールベースと、
前記最適化ルールベースに蓄積されているルールをその
蓄積順に評価して最適化の対象とする論理回路に対して
適用可能なルールであれば該ルールを適用して最適化す
る処理を、最適化目標値をクリアするまで続ける最適化
手段と、前記最適化ルールベースに蓄積されているルー
ルを適用回数順にソートするルールソート手段とを備え
たものである。

【００２７】また、本発明は、最適化処理に要する時間
を短縮させ、且つ遅延制約の厳しい論理回路であって
も、遅延制約の必要のないパスが存在する論理回路に対
しては回路規模を小さくできるようにするため、（Ｂ）
最適化の対象とする論理回路の各出力端子が、遅延優先
の最適化を行なう出力端子か、面積優先の最適化を行な
う出力端子かを示す情報が格納される出力端子表と、前
記最適化ルールベースに蓄積されているルールをその蓄
積順に評価して、最適化の対象とする論理回路中の各パ
スの内、前記出力端子表に遅延優先の最適化を行なうこ
とを示す情報が格納されている出力端子に対応する各パ
スに対して、適用可能なルールであれば該ルールを適用
して最適化する処理を、パスの遅延時間が遅延目標値を
クリアするまで続ける前記最適化手段に含まれる遅延優
先最適化手段と、該遅延優先最適化手段による最適化が
行なわれた後、前記最適化ルールベースに蓄積されてい
るルールをその蓄積順に評価して、最適化の対象とする
論理回路中の各パスの内、前記出力端子表に面積優先の
最適化を行なうことを示す情報が格納されている出力端
子に対応する各パスに対して、適用可能なルールであれ
ば該ルールを適用して最適化する処理を、前記論理回路
の面積が面積目標値をクリアするまで続ける前記最適化
手段に含まれる面積優先最適化手段とを備えたものであ
る。

【００２８】また、本発明は、更に、最適化処理に要す
る時間を短縮させるため、（Ｃ）遅延優先ルールベース
と、面積優先ルールベースと、前記最適化ルールベース
に蓄積されているルールの内、遅延優先モードのルール
を前記最適化ルールベースに蓄積されている順序で前記
遅延優先ルールベースに格納し、面積優先モードのルー
ルを前記最適化ルールベースに蓄積されている順序で前
記面積優先ルールベースに蓄積するルール分離手段とを
備え、前記遅延優先最適化手段及び前記面積優先最適化
手段は、それぞれ前記遅延優先ルールベース及び面積優
先ルールベースを通じて前記最適化ルールベース中のル
ールを読み込むようにしたものである。

【００２９】

【作用】本発明は、最適化処理に要する時間を短縮させ
るために、（Ａ）の構成に於いては、ルールソート手段
が最適化ルールベースに蓄積されているルールを適用回
数順にソートし、最適化手段が最適化ルールベースに蓄
積されているルールをその蓄積順に評価して最適化の対
象とする論理回路に対して適用可能なルールであれば該
ルールを適用して最適化する処理を、最適化目標値をク
リアするまで続ける。

【００３０】（Ｂ）の構成に於いては、最適化の対象と
する論理回路の各出力端子の内、遅延優先の出力端子で
あることが出力端子表によって示されている出力端子に
対応するパスに対しては、遅延優先最適化手段が最適化
ルールベースに蓄積されているルールを蓄積順に評価
し、そのパスに対して適用可能なルールであればそれを
適用して最適化する処理を、パスの遅延時間が遅延目標
値をクリアするまで続ける。

【００３１】また、面積優先の出力端子であることが出
力端子表によって示されている出力端子に対応するパス
に対しては、面積優先最適化手段が最適化ルールベース
に蓄積されているルールを蓄積順に評価し、そのパスに
対して適用可能なルールであればそれを適用して最適化
する処理を、論理回路の面積が面積目標値をクリアする
まで続ける。

【００３２】（Ｃ）の構成に於いては、ルール分離手段
が最適化ルールベースに蓄積されているルールの内、遅
延優先モードのルールを遅延優先ルールベースに格納
し、面積優先モードのルールを面積優先ルールベースに
格納し、遅延優先最適化手段，面積優先最適化手段が、
それぞれ遅延優先ルールベース，面積優先ルールベース
を通じて最適化ルールベース中のルールを読み込み、最
適化を行なう。

【００３３】

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

【００３４】図１は本発明の実施例のブロック図であ
り、キーボード等の入力部１と、制御部２と、記憶部３
と、ファイル等へ最適化の結果を出力するための出力部
４とから構成されている。

【００３５】記憶部３は、ライブラリ３１と、目標達成
表３２と、遅延目標記憶部３３と、面積目標記憶部３４
と、接続情報記憶部３５と、最適化ルールベース３６
と、出力端子表３７と、遅延優先ルールベース３８と、
面積優先ルールベース３９と、遅延優先ルール適用回数
表４０と、面積優先ルール適用回数表４１と、ルール適
用回数表４２とを含んでいる。

【００３６】最適化ルールベース３６には、遅延最適
化，面積最適化を行なうためのルールが複数蓄積されて
いる。

【００３７】ルール適用回数表４２には、最適化ルール
ベース３６に蓄積されている各ルールのルール番号と適
用回数とが図２に示すように格納される。

【００３８】遅延優先ルールベース３８には、最適化ル
ールベース３６に蓄積されている各ルールの内、遅延優
先モードのルールが格納される。

【００３９】面積優先ルールベース３９には、最適化ル
ールベース３６に蓄積されている各ルールの内、面積優
先モードのルールが格納される。

【００４０】遅延優先ルール適用回数表４０には、或る
論理回路に対する最適化処理を開始してから終了するま
での間の遅延優先ルールベース３８中の各ルールの適用
回数が格納される。

【００４１】面積優先ルール適用回数表４１には、或る
論理回路に対する最適化処理を開始してから終了するま
での間の面積優先ルールベース３９中の各ルールの適用
回数が格納される。

【００４２】ライブラリ３１には、遅延制約，面積制約
をクリアしたか否かを判断するために必要となる情報
（例えば、各素子の遅延時間，各素子の面積）等が格納
されている。

【００４３】遅延目標記憶部３３には、遅延目標値が格
納される。

【００４４】面積目標記憶部３４には、面積目標値が格
納される。

【００４５】目標達成表３２には、図３に示すように、
最適化の対象とする論理回路中の各出力端子の出力端子
番号に対応してその出力端子と対応するパスが遅延制約
をクリアしているか否かを示すクリア情報が格納され
る。

【００４６】出力端子表３７には、図４に示すように、
最適化の対象とする論理回路中の各出力端子の出力端子
番号と、その出力端子に対応するパスが遅延優先，面積
優先の最適化の内のどちらを行なうものなのかを示す情
報とが格納される。

【００４７】制御部２は、ルール分離手段２１と、遅延
優先最適化手段２２と、面積優先最適化手段２３と、適
用回数更新手段２４と、ルールソート手段２５とから構
成されている。

【００４８】ルール分離手段２１は、最適化ルールベー
ス３６に格納されているルールの内、遅延優先モードの
ルールを遅延優先ルールベース３８に格納し、面積優先
モードのルールを面積優先ルールベース３９に格納する
機能を有する。

【００４９】遅延優先最適化手段２２は、最適化を行な
う論理回路中の各パスの内、出力端子表３７によって遅
延優先の最適化を行なうことが示されているパスに対し
て、パスの遅延時間が遅延目標記憶部３３に格納されて
いる遅延目標値をクリアするまで、遅延優先ルールベー
ス３８に格納されているルールの内、適用可能なルール
を適用して最適化を行なう機能と、或る論理回路に対す
る最適化を開始する時、目標達成表３２及び遅延優先ル
ール適用回数表４０に対する初期化処理を行なう機能
と、遅延優先ルールベース３８中のルールを適用する毎
に遅延優先ルール適用回数表４０を更新する機能とを有
する。

【００５０】面積優先最適化手段２３は、最適化を行な
う論理回路中の各パスの内、出力端子表３７によって面
積優先の最適化を行なうことが示されているパスに対し
て、論理回路の面積が面積目標記憶部３４に格納されて
いる面積目標値をクリアするまで、面積優先ルールベー
ス３９に格納されているルールの内、適用可能なルール
を適用して最適化を行なう機能と、或る論理回路に対す
る最適化処理を開始する時、面積優先ルールベース３９
に対する初期化処理を行なう機能と、面積優先ルールベ
ース３９中のルールを適用する毎に面積優先ルール適用
回数表４１を更新する機能とを有する。

【００５１】適用回数更新手段２４は、或る論理回路に
対する最適化処理が終了した時、遅延優先ルール適用回
数表４０，面積優先ルール適用回数表４１に格納されて
いるテンポラリな適用回数を用いてルール適用回数表４
２を更新する機能を有する。

【００５２】ルールソート手段２５は、ルール適用回数
表４２に格納されている各ルールの適用回数に基づい
て、最適化ルールベース３６に蓄積されている各ルール
を適用回数が多い順にソートする機能を有する。

【００５３】図５はルール分離手段２１の処理例を示す
流れ図、図６及び図７は遅延優先最適化手段２２の処理
例を示す流れ図、図８及び図９は面積優先最適化手段２
３の処理例を示す流れ図、図１０は適用回数更新手段２
４の処理例を示す流れ図、図１１はルールソート手段２
５の処理例を示す流れ図であり、以下各図を参照して本
実施例の動作を説明する。

【００５４】利用者は、論理回路の最適化を行なう場
合、入力部１を用いて上記論理回路の接続情報を接続情
報記憶部３５に格納し、遅延目標値を遅延目標記憶部３
３に格納し、面積目標値を面積目標記憶部３４に格納
し、上記論理回路の各出力端子に対応するパスが遅延優
先の最適化を行なうものなのか面積優先の最適化を行な
うものなのかを示す情報を出力端子表３７に格納する。

【００５５】次いで、利用者は、入力部１を用いてルー
ル分離手段２１に遅延優先の最適化のためだけに使用す
るルール及び面積優先の最適化のためだけに使用するル
ールを示す情報を入力し、その後、ルール分離手段２１
を起動する。

【００５６】ルール分離手段２１は、起動されると、図
５に示すように、最適化ルールベース３６に蓄積されて
いるルールの内、遅延優先の最適化のためだけに使用す
ることが指定されたルール及び遅延優先の最適化のため
だけに使用することも面積優先の最適化のためだけに使
用することも指定されていないルール（遅延優先モード
のルール）を、最適化ルールベース３６に蓄積されてい
る順序で遅延優先ルールベース３８に格納する (ステッ
プＳ１）。

【００５７】次いで、ルール分離手段２１は、最適化ル
ールベース３６に蓄積されているルールの内、面積優先
の最適化のためだけに使用することが指定されたルール
及び遅延優先の最適化のためだけに使用することも面積
優先の最適化のためだけに使用することも指定されてい
ないルール（面積優先モードのルール）を、最適化ルー
ルベース３６に蓄積されている順序で面積優先ルールベ
ース３９に格納する (ステップＳ２）。

【００５８】ここで、最適化ルールベース３６中のルー
ルは、ルールソート手段２５によって適用回数の多い順
にソートされているので、遅延優先ルールベース３８，
面積優先ルールベース３９中のルールも適用回数の多い
順にソートされた形になる。

【００５９】ルール分離手段２１の処理が終了すると、
遅延優先最適化手段２２は、遅延優先ルールベース３８
に格納されているルールの何番目のルールに注目するの
かを示す変数ｉを「１」にする（図６，ステップＳ１
１）。

【００６０】次いで、遅延優先最適化手段２２は、遅延
優先ルール適用回数表４０に格納されている各ルールの
適用回数を全て「０」にすると共に、目標達成表３２に
格納されている、遅延目標値をクリアしたか否かを示す
クリア情報を全て“０”（クリアしていないことを示
す）にする (ステップＳ１２）。

【００６１】その後、遅延優先最適化手段２２は、遅延
優先ルールベース３８の第ｉ番目のルールに注目し (ス
テップＳ１３）、ルールが終了している場合 (ステップ
Ｓ１４がＹＥＳ）はその処理を終了する。

【００６２】また、ルールが終了していなければ (ステ
ップＳ１４がＮＯ）、遅延優先最適化手段２２は、最適
化の対象としている論理回路の何番目の出力端子に注目
するのかを示す変数ｊを「１」にする (ステップＳ１
５）。

【００６３】その後、遅延優先最適化手段２２は、第ｊ
番目の出力端子に注目し (図７，ステップＳ１６）、出
力端子が終了していなければ (ステップＳ１７がＮ
Ｏ）、第ｊ番目の出力端子が遅延優先の最適化を行なう
パスに対応するものであるか否かを出力端子表３７の内
容に基づいて判断する (ステップＳ２０）。

【００６４】第ｊ番目の出力端子が遅延優先の最適化を
行なうパスに対応するものでないと判断した場合 (ステ
ップＳ２０がＮＯ）は、変数ｊを＋１し (ステップＳ２
９）、次の出力端子に注目する (ステップＳ１６）。

【００６５】また、第ｊ番目の出力端子が遅延優先の最
適化を行なうパスに対応するものであると判断した場合
(ステップＳ２０がＹＥＳ）は、目標達成表３２を参照
して上記パスが既に遅延目標値をクリアしているか否か
を判断する (ステップＳ２１）。

【００６６】そして、クリアしていると判断した場合
(ステップＳ２１がＹＥＳ）は、ステップＳ２９の処理
を行ない、クリアしていないと判断した場合 (ステップ
Ｓ２１がＮＯ）は、第ｊ番目の出力端子から入力端子に
向かってパストレースを行ない(ステップＳ２２）、ト
レースしたパス中に第ｉ番目のルールを適用できる部分
があるか否かを判断する (ステップＳ２３）。

【００６７】第ｉ番目のルールを適用できる部分がない
と判断した場合 (ステップＳ２３がＮＯ）は、遅延優先
最適化手段２２はステップＳ２９の処理を行ない、適用
できる部分があると判断した場合 (ステップＳ２３がＹ
ＥＳ）は、第ｉ番目のルールに従って素子の置き換え
（変換）を行なう (ステップＳ２４）。

【００６８】ステップＳ２４の処理が終了すると、遅延
優先最適化手段２２は、遅延優先ルール適用回数表４０
に格納されている第ｉ番目のルールの適用回数を更新す
る (ステップＳ２５）。ここで、上記パスに第ｉ番目の
ルールを適用できる部分がｋ箇所存在する場合は、遅延
優先最適化手段２２は、遅延優先ルール適用回数表４０
に格納されている第ｉ番目のルールの適用回数を＋ｋす
る。

【００６９】その後、遅延優先最適化手段２２は、ライ
ブラリ３１に格納されている各素子の遅延時間に基づい
て、第ｊ番目の出力端子から入力端子に至るまでの各パ
スの遅延時間を見積もり (ステップＳ２６）、その全て
が遅延目標記憶部３３に格納されている遅延目標値をク
リアしているか否かを判断する (ステップＳ２７）。

【００７０】ステップＳ２７で遅延目標値をクリアして
いないパスが存在すると判断した場合（判断結果がＮ
Ｏ）は、遅延優先最適化手段２２は、ステップＳ２９の
処理を行ない、全てのパスが遅延目標値をクリアしてい
ると判断した場合（判断結果がＹＥＳ）は、目標達成表
３２の第ｊ番目の出力端子に対応するクリア情報を
“１”（遅延目標値をクリアしたことを示す）にした後
(ステップＳ２８）、次の出力端子に注目する (ステッ
プＳ２９，Ｓ１６）。

【００７１】以下、前述したと同様の処理を全ての出力
端子に対して行ない、全ての出力端子に対して前述した
処理を行なうと (ステップＳ１７がＹＥＳ）、遅延優先
最適化手段２２は、目標達成表３２を参照して全ての出
力端子に対応するパスが遅延目標値を達成しているか否
かを判断する (ステップＳ１８）。

【００７２】そして、全ての出力端子に対応するパスが
遅延目標値を達成していると判断した場合 (ステップＳ
１８がＹＥＳ）は、遅延優先最適化手段２２は、その処
理を終了し、達成していないと判断した場合 (ステップ
Ｓ１８がＮＯ）は、遅延優先ルールベース３８に格納さ
れている次のルールに注目し（図７ステップＳ１９，図
６ステップＳ１３）、前述したと同様の処理を行なう。

【００７３】遅延優先最適化手段２２の処理が終了する
と、面積優先最適化手段２３は、面積優先ルールベース
３９に格納されているルールの何番目のルールに注目す
るのかを示す変数ｍを「１」にし (図８，ステップＳ３
１）、その後、面積優先ルール適用回数表４１に格納さ
れている各ルールの適用回数を全て「０」にする (ステ
ップＳ３２）。

【００７４】次いで、面積優先最適化手段２３は、面積
優先ルールベース３９に格納されているルールの内の第
ｍ番目のルールに注目し (ステップＳ３３）、ルールが
終了している場合 (ステップＳ３４がＹＥＳ）はその処
理を終了し、ルールが終了していない場合（ステップＳ
３４がＮＯ）は最適化の対象とする論理回路の何番目の
出力端子に注目するのかを示す変数ｎを「１」にする
(ステップＳ３５）。

【００７５】その後、面積優先最適化手段２３は、第ｎ
番目の出力端子に注目し (図９，ステップＳ３６）、出
力端子が終了していなければ (ステップＳ３７がＮ
Ｏ）、第ｎ番目の出力端子が面積優先の最適化を行なう
パスに対応するものであるか否かを出力端子表３７の内
容に基づいて判断する (ステップＳ４１）。

【００７６】そして、第ｎ番目の出力端子が面積優先の
最適化を行なうパスに対応するものでないと判断した場
合 (ステップＳ４１がＮＯ）は、次の出力端子に注目す
る (ステップＳ４６，Ｓ３６）。

【００７７】また、第ｎ番目の出力端子が面積優先の最
適化を行なうパスに対応するものであると判断した場合
(ステップＳ４１がＹＥＳ）は、第ｎ番目の出力端子か
ら入力端子に向かってパストレースを行ない (ステップ
Ｓ４２）、トレースしたパス中に第ｍ番目のルールを適
用できる部分が存在するか否かを判断する (ステップＳ
４３）。

【００７８】そして、第ｍ番目のルールを適用できる部
分がないと判断した場合 (ステップＳ４３がＮＯ）は、
面積優先最適化手段２３は、次の出力端子に注目し (ス
テップＳ４６，Ｓ３６）、適用できる部分があると判断
した場合 (ステップＳ４３がＹＥＳ）は、第ｍ番目のル
ールに従って素子の変換を行なう (ステップＳ４４）。

【００７９】ステップＳ４４の処理が終了すると、面積
優先最適化手段２３は、面積優先ルール適用回数表４１
に格納されている第ｍ番目のルールの適用回数を更新し
た後(ステップＳ４５）、次の出力端子に注目する (ス
テップＳ４６，Ｓ３６）。

【００８０】全ての出力端子に対して前述した処理を行
なうと (ステップＳ３７がＹＥＳ）、面積優先最適化手
段２３は、ライブラリ３１に格納されている各素子の面
積を示す情報に基づいて現段階に於ける論理回路の面積
を見積もる (ステップＳ３８）。

【００８１】そして、面積の見積もりが、面積目標記憶
部３４に格納されている面積目標値を達成している場合
(ステップＳ３９がＹＥＳ）は、その処理を終了し、達
成していない場合 (ステップＳ３９がＮＯ）は、次のル
ールに注目し (図９ステップＳ４０，図８ステップＳ３
３）、前述したと同様の処理を行なう。

【００８２】面積優先最適化手段２３の処理が終了する
と、適用回数更新手段２４は、図１０に示すように、遅
延優先ルール適用回数表４０，面積優先ルール適用回数
表４１に格納されている各ルールのテンポラリな適用回
数を取得し (ステップＳ５１，Ｓ５２）、取得したテン
ポラリな適用回数をルール適用回数表４２中の対応する
ルールの適用回数に加算する (ステップＳ５３）。

【００８３】適用回数更新手段２４の処理が終了する
と、ルールソート手段２５は、図１１に示すように、ル
ール適用回数表４２から各ルールの適用回数を取得し
(ステップＳ６１）、最適化ルールベース３６に蓄積さ
れているルールを適用回数が多い順にソートする (ステ
ップＳ６２）。

【００８４】尚、上述した実施例に於いては、ルール分
離手段２１を用いて最適化ルールベース３６に蓄積され
ている遅延優先モードのルール，面積優先モードのルー
ルをそれぞれ遅延優先ルールベース３８，面積優先ルー
ルベース３９に格納し、遅延優先最適化手段２２，面積
優先最適化手段２３でそれぞれ遅延優先ルールベース３
８，面積優先ルールベース３９に格納されているルール
を用いて最適化を行なうようにしたが、最適化ルールベ
ース３６に蓄積されているルールを遅延優先ルールベー
ス３８，面積優先ルールベース３９に分離せずに、遅延
優先最適化手段２２，面積優先最適化手段２３で最適化
ルールベース３６に蓄積されているルールを用いて最適
化を行なうようにしても良いことは勿論である。

【００８５】しかし、実施例のように、最適化ルールベ
ース３６に蓄積されているルールを遅延優先ルールベー
ス３８，面積優先ルールベース３９に分離し、遅延優先
最適化手段２２，面積優先最適化手段２３でそれぞれ遅
延優先ルールベース３８，面積優先ルールベース３９に
蓄積されているルールを使用して最適化を行なう方がル
ールの参照回数が少なくなるので、処理が高速になる。

【００８６】

【発明の効果】以上説明したように、本発明によれば、
以下の効果を得ることができる。

【００８７】最適化ルールベースに蓄積されているルー
ルはルールソート手段によって適用回数順にソートされ
ており、最適化手段は、最適化ルールベース中のルール
を蓄積順に評価して最適化の対象とする論理回路に対し
て適用可能なルールであれば該ルールを適用して最適化
する処理を、最適化目標値をクリアするまで続けるの
で、最適化目標値をクリアするまでに評価するルールの
数が従来に比較して少なくなり、その結果、処理速度を
高速化することが可能になる。

【００８８】最適化の対象とする論理回路の各出力端子
が遅延優先のものなのか、面積優先のものなのかを示す
出力端子表を備え、先ず、出力端子表で遅延優先である
ことを示されている出力端子に対して遅延優先最適化手
段を用いて最適化を行ない、その後、面積優先であるこ
とが示されている出力端子に対して面積優先最適化手段
を用いて最適化を行なうものであるので、遅延制約が厳
しい論理回路の最適化がやりやすくなる効果があると共
に、遅延制約が厳しい論理回路であっても遅延制約の必
要のないパスが存在する論理回路については、規模を従
来に比較して小さくすることができる効果がある。

【００８９】ルール分離手段により、最適化ルールベー
ス中のルールの内、遅延優先モードのルールを遅延優先
ルールベースに格納し、面積優先モードのルールを面積
優先ルールベースに格納し、遅延優先最適化手段，面積
優先最適化手段は、それぞれ遅延優先ルールベース，面
積優先ルールベース中のルールを用いて最適化を行なう
ので、最適化ルールベースを用いて最適化を行なう場合
に比較して遅延優先最適化手段，面積優先最適化手段で
評価するルールの数が少なくなり、その結果、処理をよ
り高速化することが可能になる効果がある。

【図面の簡単な説明】

【図１】本発明の実施例のブロック図である。

【図２】ルール適用回数表４２の構成例を示す図であ
る。

【図３】目標達成表３２の構成例を示す図である。

【図４】出力端子表３７の構成例を示す図である。

【図５】ルール分離手段２１の処理例を示す流れ図であ
る。

【図６】遅延優先最適化手段２２の処理例を示す流れ図
である。

【図７】遅延優先最適化手段２２の処理例を示す流れ図
である。

【図８】面積優先最適化手段２３の処理例を示す流れ図
である。

【図９】面積優先最適化手段２３の処理例を示す流れ図
である。

【図１０】適用回数更新手段２４の処理例を示す流れ図
である。

【図１１】ルールソート手段２５の処理例を示す流れ図
である。

【図１２】最適化処理を説明するための図である。

【図１３】最適化処理を説明するための図である。

【図１４】最適化処理を説明するための図である。

【図１５】最適化処理を説明するための図である。

【図１６】従来例のブロック図である。

【図１７】論理最適化手段１６２の処理例を示す流れ図
である。

【図１８】最適化ルールベース１６６の構成例を示す図
である。

【符号の説明】

１…入力部２…制御部２１…ルール分離手段２２…遅延優先最適化手段２３…面積優先最適化手段２４…適用回数更新手段２５…ルールソート手段３…記憶部３１…ライブラリ３２…目標達成表３３…遅延目標記憶部３４…面積目標記憶部３５…接続情報記憶部３６…最適化ルールベース３７…出力端子表３８…遅延優先ルールベース３９…面積優先ルールベース４０…遅延優先ルール適用回数表４１…面積優先ルール適用回数表４２…ルール適用回数表４…出力部

Claims

【特許請求の範囲】

【請求項１】論理最適化を行なうためのルールが蓄積
された最適化ルールベースと、前記最適化ルールベースに蓄積されているルールをその
蓄積順に評価して、最適化の対象とする論理回路に対し
て適用可能なルールであれば該ルールを適用して最適化
する処理を、最適化目標値をクリアするまで続ける最適
化手段と、前記最適化ルールベースに蓄積されているルールを適用
回数順にソートするルールソート手段とを備えたことを
特徴とする論理最適化装置。
【請求項２】最適化の対象とする論理回路の各出力端
子が、遅延優先の最適化を行なう出力端子か、面積優先
の最適化を行なう出力端子かを示す情報が格納される出
力端子表と、前記最適化ルールベースに蓄積されているルールをその
蓄積順に評価して、最適化の対象とする論理回路中の各
パスの内、前記出力端子表に遅延優先の最適化を行なう
ことを示す情報が格納されている出力端子に対応する各
パスに対して、適用可能なルールであれば該ルールを適
用して最適化する処理を、パスの遅延時間が遅延目標値
をクリアするまで続ける前記最適化手段に含まれる遅延
優先最適化手段と、該遅延優先最適化手段による最適化が行なわれた後、前
記最適化ルールベースに蓄積されているルールをその蓄
積順に評価して最適化の対象とする論理回路中の各パス
の内、前記出力端子表に面積優先の最適化を行なうこと
を示す情報が格納されている出力端子に対応する各パス
に対して適用可能なルールであれば該ルールを適用して
最適化する処理を、前記論理回路の面積が面積目標値を
クリアするまで続ける前記最適化手段に含まれる面積優
先最適化手段とを備えたことを特徴とする請求項１記載
の論理最適化装置。
【請求項３】遅延優先ルールベースと、面積優先ルールベースと、前記最適化ルールベースに蓄積されているルールの内、
遅延優先モードのルールを前記最適化ルールベースに蓄
積されている順序で前記遅延優先ルールベースに格納
し、面積優先モードのルールを前記最適化ルールベース
に蓄積されている順序で前記面積優先ルールベースに蓄
積するルール分離手段とを備え、前記遅延優先最適化手段及び前記面積優先最適化手段
は、それぞれ前記遅延優先ルールベース及び面積優先ル
ールベースを通じて前記最適化ルールベース中のルール
を読み込むことを特徴とする請求項２記載の論理最適化
装置。
【請求項４】前記遅延優先最適化手段によって前記遅
延優先ルールベースに蓄積されているルールが適用され
た回数を保持する遅延優先ルール適用回数表と、前記面積優先最適化手段によって前記面積優先ルールベ
ースに蓄積されているルールが適用された回数を保持す
る面積優先ルール適用回数表と、ルール適用回数表と、最適化の対象とする論理回路に対する最適化処理の終了
毎に、前記遅延優先ルール適用回数表及び前記面積優先
ルール適用回数表の内容に基づいて前記ルール適用回数
表を更新する適用回数更新手段とを備え、前記ルールソート手段は、前記ルール適用回数表を参照
して前記最適化ルールベースに蓄積されているルールを
適用回数順にソートすることを特徴とする請求項３記載
の論理最適化装置。