JPH04263367A - 論理回路自動合成装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は論理回路の論理記述か
ら、論理回路の接続記述を自動合成する論理回路自動合
成装置に関する。

【０００２】

【従来の技術】図５は従来の論理回路自動合成装置の構
成を示すブロック図である。同図に示すように、自動合
成に必要なファイルである入力論理記述ファイル２と設
計制約ファイル５とががあらかじめ用意されている。入
力論理記述ファイル２には合成されるべき論理回路の論
理記述が格納され、設計制約ファイル５には論理回路の
面積制約と遅延制約に関する種々の制約が格納されてい
る。

【０００３】多段論理簡単化手段１は、入力論理記述フ
ァイル２を受け取り、該ファイル２内の論理記述におけ
る論理的な冗長性の排除と論理の共有化を行い、より多
段の論理式からなる多段論理記述を生成する。素子割り
付け手段３は、多段論理簡単化手段により生成された多
段論理記述における個々の論理式から素子ライブラリ４
に登録された素子を割り付けて論理回路の接続記述を生
成する。

【０００４】面積・遅延解析手段６は、設計制約ファイ
ル５に格納された種々の設計制約条件に基づき、素子割
り付け手段３により生成された論理回路の接続記述から
、面積と信号遅延を評価し、該論理回路が面積制約を満
足し遅延制約に違反する場合は、その違反情報を素子割
り付け手段３に与え、再び、素子割り付け手段３に素子
の再割り付けによる接続記述の再生成を促し、面積制約
及び遅延制約双方共に満足する場合は、該接続記述を出
力接続記述ファイル８に出力して自動合成を終了する。 一方、面積制約に違反する場合は遅延違反の有無に関係
なく面積エラーを出力して処理を強制終了する。

【０００５】図６は図５で示した論理回路自動合成装置
の論理回路の自動合成手順を示すフローチャートである
。以下、同図を参照しつつ、自動合成手順を説明する。

【０００６】まず、ステップＳ１で、多段論理簡単化手
段１が入力論理記述ファイル２に格納されている論理式
群からなる論理回路の論理記述を読み込み、読み込んだ
論理記述内の冗長な論理を排除する。例えば、図７で示
すように、論理記述２５が冗長な論理項Ａ＊Ｂ＊Ｃを有
すれば、それが取り除かれた論理記述２６に訂正される
。なお、同図において、＊は論理積、＋は論理和を示し
ている。

【０００７】次に、ステップＳ２において、ステップＳ
１で冗長論理が排除され、簡単化された論理式群に対し
、多段論理簡単化手段１はさらに各論理式における共通
論理式をくくり出し多段論理記述を生成する。その結果
、積和型の論理記述はさらに簡単化され、より多段の論
理記述となる。例えば、図８に示すように、論理記述２
７における変数Ｘ及びＹは共通の論理式（Ａ＋Ｂ）を因
子に持つため、この論理式（Ａ＋Ｂ）を新たに変数Ｉで
置き換えることにより多段論理記述２８が導出される。

【０００８】そして、ステップＳ３において、素子割り
付け手段３が、ステップＳ２で多段化された多段論理記
述を論理的に等価な接続記述に変換する。この段階での
接続記述は、論理式中の論理積をＡＮＤゲートに、論理
和をＯＲゲートで置き換えるという単純な変換処理から
生成された抽象的な接続記述である。例えば、図９に示
すように、多段論理記述２９が抽象的な接続記述３０に
変換される。

【０００９】その後、ステップＳ４において、素子割り
付け手段３が、ステップＳ３で得た抽象的な接続記述に
対し、さらに具体的な接続記述に変更すべく、その接続
記述中のＡＮＤゲートやＯＲゲートを、素子ライブラリ
４に登録されている論理素子を用いて、回路面積が小さ
くなるように割り付ける。例えば、素子ライブラリ４が
図１０に示すような論理素子を登録している場合、図９
で示した抽象的な接続記述３０が図１１に示すような具
体的な接続記述に変換される。

【００１０】そして、ステップＳ５において、面積・遅
延解析手段６は、ステップＳ４で素子割り付けされた具
体的な接続記述に基づく論理回路に対し、素子ライブラ
リ４に登録されている素子の素子面積や素子遅延等の特
性値に基づき、回路面積と経路遅延を計算し、設計制約
ファイル５で規定されている許容面積に違反するか否か
を検出するとともに、最大許容遅延に違反する違反経路
を検出する。以下、遅延違反が検出された信号経路を「
クリティカルパス」という。

【００１１】次に、ステップＳ６において、ステップＳ
５での面積制約違反の有無がチェックされ、面積制約違
反が有れば、面積エラーとして直ちに処理を終了し、面
積制約違反が無ければステップＳ７に移行する。

【００１２】次に、ステップＳ７において、ステップＳ
５におけるクリティカルパスの検出の有無がチェックさ
れ、クリティカルパスの検出があればステップＳ４に戻
り、無ければ制約違反なしとして処理を終了する。

【００１３】ステップＳ７からステップＳ４に戻ると、
素子割り付け手段３はクリティカルパスに対し、後述す
る遅延改善手段を施して素子の再割り付けを行う。以降
、面積・遅延解析手段６により面積制約違反が検出され
るか、あるいはクリティカルパスが検出されなくなるま
で、ステップＳ４〜Ｓ７が繰り返される。

【００１４】素子割り付け手段３による素子の再割り付
けの際、クリティカルパスの遅延改善を図る手段の１つ
として、クリティカルパス中に存在する素子を、この素
子と論理的に等価で駆動能力のより大きい論理素子へ置
換する方法がある。この方法を施すと占有面積は大きく
なるというデメリットを伴うが、駆動能力の増大に伴い
信号伝播速度を向上させることができる。

【００１５】クリティカルパスの遅延改善を図るもう１
つの手段として、クリティカルパス上の負荷を分散する
方法がある。この方法は、例えば図１２に示すように、
クリティカルパスＣＰを形成する論理素子（ＮＡＮＤゲ
ート）３２の出力経路上において、インバータ３３に加
え新たにインバータ３４を生成させ、クリティカルパス
ＣＰ上の信号線３１を孤立させることにより、論理構造
を変更することなく配線遅延を小さくすることができる
。

【００１６】

【発明が解決しようとする課題】従来の論理回路自動合
成装置は以上のように構成されており、素子割り付け手
段３は、多段論理簡単化手段１が出力した論理記述の論
理構造を変更することなく素子割り付けを行っているた
め、回路性能は多段論理簡単化手段１が出力する論理記
述によりほぼ決定されてしまう。

【００１７】一方、多段論理簡単化手段１による論理記
述の簡単化は、主として形成面積の縮小化を目的として
行われている。つまり、多段論理簡単化手段１は設計制
約ファイル５に格納された遅延制約を考慮せずに、多段
論理記述を出力している。このため、その論理構造は、
必ずしも対象とする半導体技術の下で遅延制約に適合し
た論理構造であるとは限らない。

【００１８】したがって、素子割り付け手段３により、
多段論理簡単化手段１が出力した論理記述の論理構造を
変更することなく、論理素子の（再）割り付けを行って
も、遅延改善手段が有効に寄与しない場合があり、最悪
の場合、遅延制約を満足する論理回路の接続記述を生成
できないという問題点があった。

【００１９】この発明は上記問題点を解決するためにな
されたもので、遅延制約を満足する論理回路の接続記述
を自動生成できる論理回路自動合成装置を得ることを目
的とする。

【００２０】

【課題を解決するための手段】この発明にかかる請求項
１記載の論理回路自動合成装置は、論理回路の論理記述
を取り込み、該論理記述に基づき論理回路の接続記述を
生成する装置であり、前記論理回路の接続記述が所定の
遅延制約を違反した場合、該論理回路における前記所定
の遅延制約を違反する違反経路上の論理構造の少なくと
も一部を変更した後、該違反経路が短くなるように論理
素子段数を減少させる素子圧縮動作を実行することによ
り、前記接続記述を変更する素子圧縮手段を備えている
。

【００２１】また、この発明にかかる請求項２記載の論
理回路自動合成装置は、論理回路の論理記述を付与する
論理記述付与手段と、論理回路の接続記述の構成要素と
して、使用可能な論理素子をその物理的特性とともにあ
らかじめ格納した素子ライブラリと、前記論理回路の論
理記述から論理的冗長性を排除し、さらに共通論理を見
いだして多段の論理式からなる多段論理記述を出力する
多段論理簡単化手段と、前記多段論理記述に対し、前記
素子ライブラリに格納された論理素子を割り付けること
により前記論理回路の接続記述を生成する素子割り付け
手段と、前記論理回路の接続記述を解析し、所定の遅延
制約を犯す違反経路の有無を検出する違反経路検出手段
と、前記違反経路検出手段により違反経路が検出された
場合、該違反経路上にある少なくとも一部の論理構造を
変更した後、前記素子ライブラリに格納された論理素子
を用いて、該違反経路が短くなるように素子段数を圧縮
する素子圧縮動作を実行することにより、前記接続記述
を変更する素子圧縮手段とを備えて構成されている。

【００２２】

【作用】この発明における素子圧縮手段は、論理回路に
おける所定の遅延制約を違反する違反経路上の論理構造
の少なくとも一部を変更した後、該違反経路が短くなる
ように論理素子段数を減少させる素子圧縮動作を実行し
ている。

【００２３】つまり、当初の論理回路の（多段）論理記
述で規定された論理構造が、違反経路の遅延改善が困難
な論理構造を有していた場合でも、違反経路の遅延改善
が比較的容易な論理構造に変更した後に、素子圧縮動作
を行っている。

【００２４】

【実施例】図１はこの発明の一実施例である論理回路自
動合成装置の構成を示すブロック図である。同図に示す
ように、素子展開・圧縮手段７が新たに設けられている
。素子展開・圧縮手段７は、面積・遅延解析手段６によ
りクリティカルパスの発生が検出された場合、素子ライ
ブラリ４の情報に基づき、素子割り付け手段３により生
成された接続記述を展開して（後に詳述する）その論理
構造を変更し、抽象的な接続記述に戻した後、論理素子
の段数の圧縮処理を行う（後に詳述する）。なお、他の
構成は図５で示した従来例と同様であるため、説明は省
略する。

【００２５】図２は図１で示した論理回路自動合成装置
の論理回路の自動合成手順を示すフローチャートである
。以下、同図を参照しつつ、自動合成手順を説明する。

【００２６】同図において、ステップＳ１１〜Ｓ１６は
、図６で示した従来例におけるステップＳ１〜Ｓ６まで
と同様であるため、説明は省略する。

【００２７】ステップＳ１７において、ステップＳ１５
におけるクリティカルパスの検出の有無がチェックされ
、クリティカルパスの検出があればステップＳ１８に移
行し、無ければ、制約違反なしとみなし処理を終了する
。

【００２８】ステップＳ１８において、素子展開・圧縮
手段７は、クリティカルパス上に存在し、かつ隣接する
論理素子が分岐した信号線で結線されている場合（以下
、この条件を「素子生成条件」という）、入力側の論理
素子と同一の論理素子を新たに生成し、新たに生成した
論理素子をクリティカルパス上にある出力側の論理素子
に分岐のない信号線で直結する。

【００２９】例えば、図３（ａ）　に示すように、クリ
ティカルパスＣＰ上に互いに隣接するＯＲゲート９ａと
ＮＡＮＤゲート４１との結線がクリティカルパスＣＰ上
の信号線１０で行われると共に、この信号線１０から分
岐した信号線４２が存在した場合、図３（ｂ）　に示す
ように、ＯＲゲート９ａと等価なＯＲゲート９ｂを生成
し、このＯＲゲート９ｂとＮＡＮＤゲート４１との結線
を分岐のない信号線１０′で直結して行う。なお、４２
′は信号線４２と等価な信号線を示す。

【００３０】さらに、クリティカルパスＣＰ上の素子に
ＡＮＤゲートやＯＲゲート等の抽象素子に該当しない複
合素子等の論理素子があれば、抽象素子に置き換え、論
理回路の接続記述を抽象的な接続記述に戻す。

【００３１】このように、ステップＳ１８では、素子展
開・圧縮手段７により、論理回路の接続記述が素子生成
条件にマッチすると、新たな論理素子の生成、配線の変
更等を行うことにより、論理回路の等価性を維持しつつ
その論理構造を変更し、さらに、具体（的な論理）素子
（素子ライブラリ４に登録された論理素子）の抽象素子
への置き換えを行うことにより、素子の展開動作を実行
する。

【００３２】その後、ステップＳ１９において、ステッ
プＳ１８で展開された抽象素子による接続記述を、素子
段数を減少させるように素子圧縮を行いながら具体素子
による接続記述に変更する。素子圧縮には、次の３つの
方法がある。

【００３３】（１）　多入力論理の分割抽象素子をその
素子ライブラリ４に登録された該抽象素子と等価な具体
素子に置き換える際、抽象素子の入力ピン数が、その具
体素子のピン数を越える場合、１つの抽象素子を複数の
具体素子の組合せで補うことになる。このとき、必ずク
リティカルパスを形成する素子段数が増加しないように
する。

【００３４】例えば、抽象素子のＯＲゲートが３入力で
、具体素子のＯＲゲートが２入力の場合、図４（ａ）　
に示すように、１つの３入力ＯＲゲート１２を２つの２
入力ＯＲゲート１５，１６の組合せで補うことになるが
、このとき、クリティカルパスＣＰ上の信号線を優先的
に処理することにより、クリティカルパスＣＰの信号入
力は必ず、後段のＯＲゲート１５への直接入力となるよ
うに変換してクリティカルパスを形成する素子段数が増
加しないようにする。

【００３５】（２）　複合ゲートの活用クリティカルパ
スＣＰを形成する素子段数を最も圧縮するように、素子
ライブラリ４に存在する複合ゲートを積極的に活用して
、素子の再割り付けを行う。

【００３６】例えば、図４（ｂ）　に示すように、２つ
の２入力ＯＲゲート１８，１９の出力がそれぞれ２入力
ＮＡＮＤゲート１７の入力となっている場合、複合ゲー
トとして、論理ゲート１７及び１８の組合せからなる複
合ゲートと論理ゲート１７及び１９の組合せからなる複
合ゲートとが存在するが、信号線２１がクリティカルパ
スＣＰ上にあることを考慮し、論理ゲート１７，１８の
複合ゲート２０を割り付け、クリティカルパスＣＰを形
成する素子段数の圧縮を行う。

【００３７】また、図４（ａ）　に示すように、多入力
論理の分割後のゲート１５及び１３に対しても、複合ゲ
ートを活用し、論理ゲート１５及び１３を複合ゲート１
４に変換してクリティカルパスＣＰを形成する素子段数
の圧縮を図ることができる。なお、図３（ｂ）　〜図３
（ｃ）　も、クリティカルパスＣＰ上にあるＯＲゲート
９ｂとＮＡＮＤゲート４１を複合ゲート１１に置き換え
た例を示している。

【００３８】（３）　極性の最適化 クリティカルパスＣＰを形成する素子段数を最も圧縮す
るように、クリティカルパスＣＰを形成する素子の極性
を変更する。

【００３９】例えば、図４（ｃ）　に示すように、クリ
ティカルパスＣＰ上にＮＡＮＤゲート２２及びインバー
タ２３が接続されている場合、双方を極性の反転してＮ
ＡＮＤゲート２２をＡＮＤゲート２４に置き換え、イン
バータ２３を除去する。これに伴い、ＮＡＮＤゲート２
４の他の出力における極性を反転させて、新たにインバ
ータ２４を設ける。その結果、クリティカルパスＣＰを
形成するの素子段数がインバータ２３が消去される分、
圧縮される。なお、この方法は、極性を反転できる論理
素子（図４（ｃ）　の例ではＡＮＤゲート）が素子ライ
ブラリ４に登録されていることが前提となる。

【００４０】このように、ステップＳ１９で、クリティ
カルパスＣＰを形成する素子の圧縮を行うことにより、
信号遅延の短縮化を図ることができる。

【００４１】ステップＳ１９の処理が終了すると、ステ
ップＳ１４に戻り、ここで素子割り付け手段３が、クリ
ティカルパスＣＰを形成する素子に対し、従来例で述べ
た駆動能力を最適化する素子置換や出力負荷の分散処理
等の遅延改善処理を施す。以降、面積・遅延解析手段６
により面積制約違反が検出されるか、あるいはクリティ
カルパスが検出されなくなるまで、ステップＳ１４〜Ｓ
１９が繰り返される。

【００４２】このように素子展開・圧縮手段７により、
多段論理簡単化手段１より出力された論理回路の多段論
理記述における論理構造を部分的に変更することにより
、素子圧縮等の遅延改善が容易な論理構造にした後に、
素子圧縮を行っているため、多段論理記述がクリティカ
ルパスが生じやすい論理構造を有していても、比較的容
易にクリティカルパスの発生を抑制することができ、当
初遅延違反を犯した論理回路の接続記述が素子割り付け
手段３から生成されても、遅延制約を満足した論理回路
の接続記述に自動的に変更することができる。

【００４３】また、多段論理簡単化手段１から出力され
る論理回路の論理記述は基本的に形成面積の縮小化に有
効な論理記述であるため、回路形成面積の小さい論理回
路を自動生成することができる。しかも、面積・遅延解
析手段６は面積違反を検出すると直ちに面積エラーを警
告し、すみやかに処理を終了するため、面積制約を違反
した論理回路が誤って自動生成されることはない。

【００４４】なお、この実施例では、論理回路の論理記
述として、論理式からなる論理記述を示したが、これに
限定されず、例えば、真理値表や既存回路の接続記述で
あっても、同様の効果を奏する。

【００４５】

【発明の効果】以上説明したように、この発明によれば
、素子圧縮手段は、論理回路における所定の遅延制約を
違反する違反経路上の論理構造の少なくとも一部を変更
した後、該違反経路が短くなるように論理素子段数を圧
縮する素子圧縮動作を実行している。

【００４６】その結果、当初の論理回路の（多段）論理
記述で規定された論理構造が、違反経路の遅延改善が困
難な論理構造を有していた場合でも、違反経路の遅延改
善が比較的容易な論理構造に変更することができるため
、その後に行う素子圧縮動作は有効に働き、遅延制約を
満足した論理回路の接続記述を自動生成することができ
る。

【００４７】さらに請求項２記載の論理回路自動合成装
置は、素子割り付け手段による素子割り付けを行う直前
の論理回路の論理記述として、多段論理簡単化手段によ
り出力された、論理的冗長性を排除し、さらに共通論理
を見いだして多段の論理式からなる多段論理記述を用い
ており、この多段論理記述は面積縮小化に有効な論理記
述であるため、面積制約も満足した論理回路の接続記述
を自動生成することができる。

【図面の簡単な説明】

【図１】この発明の一実施例である論理回路自動合成装
置の構成を示すブロック図である。

【図２】図１で示した論理回路自動合成装置の動作を示
すフローチャートである。

【図３】図１で示した論理回路自動合成装置の素子展開
例等を示す回路図である。

【図４】図１で示した論理回路自動合成装置の素子圧縮
例を示す回路図である。

【図５】従来の論理回路自動合成装置の構成を示すブロ
ック図である。

【図６】図５で示した論理回路自動合成装置の動作を示
すフローチャートである。

【図７】多段論理簡単化手段による論理の冗長性の排除
動作を示す説明図である。

【図８】多段論理簡単化手段による論理記述の多段化動
作を示す説明図である。

【図９】素子割り付け手段による抽象的な接続記述への
変換動作を示す説明図である。

【図１０】素子ライブラリの一例を示す説明図である。

【図１１】素子割り付け手段による素子割り付け後の論
理回路の接続記述を示す回路図である。

【図１２】素子割り付け手段による負荷分散処理の一例
を示す説明図である。

【符号の説明】

１　　　　多段論理簡単化手段 ２　　　　入力論理記述ファイル ３　　　　素子割り付け手段 ４　　　　素子ライブラリ ５　　　　設計制約ファイル ６　　　　面積・遅延解析手段 ７　　　　素子展開・圧縮手段

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　論理回路の論理記述を取り込み、該論
   理記述に基づき論理回路の接続記述を生成する論理回路
   自動合成装置において、前記論理回路の接続記述が所定
   の遅延制約を違反した場合、該論理回路における前記所
   定の遅延制約を違反する違反経路上の論理構造の少なく
   とも一部を変更した後、該違反経路が短くなるように論
   理素子段数を減少させる素子圧縮動作を実行することに
   より、前記接続記述を変更する素子圧縮手段を設けたこ
   とを特徴とする論理回路自動合成装置。
2. 【請求項２】　　論理回路の論理記述を付与する論理記
   述付与手段と、論理回路の接続記述の構成要素として、
   使用可能な論理素子をその物理的特性とともにあらかじ
   め格納した素子ライブラリと、前記論理回路の論理記述
   から論理的冗長性を排除し、さらに共通論理を見いだし
   て多段の論理式からなる多段論理記述を出力する多段論
   理簡単化手段と、前記多段論理記述に対し、前記素子ラ
   イブラリに格納された論理素子を割り付けることにより
   前記論理回路の接続記述を生成する素子割り付け手段と
   、前記論理回路の接続記述を解析し、所定の遅延制約を
   犯す違反経路の有無を検出する違反経路検出手段と、前
   記違反経路検出手段により違反経路が検出された場合、
   該違反経路上にある少なくとも一部の論理構造を変更し
   た後、前記素子ライブラリに格納された論理素子を用い
   て、該違反経路が短くなるように素子段数を圧縮する素
   子圧縮動作を実行することにより、前記接続記述を変更
   する素子圧縮手段とを備えた論理回路自動合成装置。