JPH09305633A - 論理回路最適化方法 - Google Patents

Abstract

(57)【要約】 【課題】 レイアウト結果の配線面積の削減、総配線長
の縮小、遅延の短縮が図れる論理回路最適化方法を得
る。 【解決手段】 入力された論理回路からバッファーツリ
ーを検出し、各バッファーツリーに属するドライバゲー
トの集合を生成する（ステップ１０２）。複数のバッフ
ァーツリーに関連したゲートの集合（最適化ゲート群）
の検出を行なう（ステップ１０３）。被最適化ゲート群
を論理構造の対称性により分類する（ステップ１０
４）。被最適化ゲート群を１分類づつ抜きだす（ステッ
プ１０５）。対称性を反映するようにバッファーツリー
の再構成を行なう（ステップ１０６）。以上の処理によ
り、論理構造の対称性を反映した形態にバッファーツリ
ーを最適化することができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、ドライバゲート
の接続の最適化を行う論理回路最適化方法に関し、ＬＳ
Ｉの総配線長の短縮、遅延の短縮、配線エリアの縮小が
図れる論理回路最適化方法に関する。

【０００２】

【従来の技術】バッファーツリーとは、図１３に示すよ
うな、正論理あるいは反転論理のドライバゲートをツリ
ー状に接続した論理回路である。バッファーツリーは、
１つのゲートの出力信号が多数のゲートの入力信号とな
り、単独のゲートのドライブ能力ではドライブできない
ような論理回路において、ゲートの出力に付加して用い
られる。大きなビット幅を持ったデータパス系の論理回
路には、バッファーツリーが必要となる論理回路が多
い。

【０００３】データパス系の論理回路は、対称な回路構
造を持った論理回路が多い。この対称性をうまく利用す
ることにより、配線に必要な面積が小さくゲートの利用
密度の高いレイアウトを得ることができる。ゲートの利
用密度を高めるには、バッファーツリーの構造について
も対称性を反映した構成が必要となる。

【０００４】

【発明が解決しようとする課題】論理合成ツールは、論
理記述を入力し、論理記述に対応する論理回路を自動合
成するツールである。入力記述の論理構造に対称性があ
れば、合成される論理回路も、通常、対称性を保持す
る。しかし、バッファーツリーは、ファンアウト数やド
ライブ能力の制約を満たすために付加される論理回路で
あり、回路全体の論理構造とは無関係な論理回路であ
る。論理合成ツールは、回路全体の論理構造の対称性を
考慮することなく、バッファーツリーの付加を行なう。
このため、最終的に得られるバッファーツリーを含んだ
論理回路は、対称性を失った回路になることがある。

【０００５】図１４に示す対称な論理構造を持った論理
回路を例にとって詳細に説明する。図１４の四角形のブ
ロックはゲートを表す。論理構造ＧX’（X＝０，１，
２，３）は互いに対称である。それぞれのブロック内に
示された名称（ＳＥＬ，ＦＦ）は、ゲートの種類名であ
る。ブロックの下に示された名称（ＵX，ＦX）は各ゲー
トを区別するゲート名である。実線はゲート間を接続す
る配線を示す。配線とブロックの接点に隣接して置かれ
た名称（ＳＥＬのＡ，Ｂ，Ｓ，Ｙ、ＦＦのＤ，ＣＬ，
Ｑ）は、ゲートのピン名である。左右にあるヤジリ記号
は入出力ピンを表し、その隣に置かれた名称（ｃｌｋ，
ｓｅｌ，ａ［X］，ｂ［X］，ｙ［X］）は、入出力ピン
名である。

【０００６】図１４の論理回路の入力ピンｓｅｌ，ｃｌ
ｋのそれぞれに、正論理のドライバゲートＢXを２個使
用したバランスツリー形のバッファーツリーの付加を行
なう場合を考える。図１５は、対称性を保持するような
バッファーツリーの付加の例である。図１６は、対称性
を失うようなバッファーツリーの付加の例である。論理
合成ツールは、図１５，図１６の２つの論理回路の品質
は同じと判断し、どちらかの論理回路を合成する。な
お、図１５，図１６中の各名称は図１４中の各名称に対
応している。

【０００７】配置後の回路で比べた場合、図１５，図１
６の２つの論理回路には差が生ずる。図１７，図１８
は、それぞれ図１５，図１６の論理回路に対して、配置
を行なった結果を示す。この配置は、配置アルゴリズム
の通常の手法であるMin-Cut法による最適配置結果であ
る。Min-Cut法では、配置の評価尺度は、カットライン
を横切る配線の総和である。図１７，図１８の太線がカ
ットラインである。カットラインの右あるいは下に示す
数字は、そのカットラインを横切る配線数である。カッ
トラインを横切る配線数の総和は、図１７の論理回路で
は３２であり、図１８の論理回路では３４となる。図１
７の論理回路の方が、配置結果がよい。２つの配置結果
の差は、Ｂ０，Ｂ２とＵ１，Ｕ２のゲート間の配線だけ
である。このゲート間の配線が、図１７の場合は中央の
横方向のカットラインを横切らないが、図１８の場合は
横切る。あるカットラインを横切る配線数の多さは、そ
の付近の配線チャネルが混雑することにつながり、配置
配線ツールのコンパクション機能による配線領域の圧縮
を困難にする。また、図１７，図１８から分かるよう
に、図１８の方が配線が複雑であり、総配線長が長い。
総配線長の増加は、遅延の増加につながる。

【０００８】このように、論理合成ツールは論理構造の
対称性を意識せずバッファーツリーを付加するため、配
置後の回路の総配線長の増加、配線面積の増大、遅延の
増加を招く問題点がある。バッファーツリーの構成に関
する手法として、“Routability-Driven Fanout Optimi
zation”,(Proc. of 30th DAC,pp.230-235）の手法があ
る。この手法では、論理合成において、バッファーツリ
ーの付加前に、論理回路の配置を行ない配置結果に応じ
て最適なバッファーツリーを構成する。しかし、この手
法は、対称な論理構造を反映したバッファーツリーの最
適化は行なっていない。

【０００９】本発明は、以上の問題点を解決するために
なされたものであり、レイアウト結果の配線面積の削
減、総配線長の縮小、遅延の短縮が図れる論理回路最適
化方法を得ることを目的とする。

【００１０】

【課題を解決するための手段】本発明の請求項１に係る
課題解決手段は、バッファーツリーを有する論理回路の
最適化方法であって、前記論理回路から論理構造の対称
性を検出するステップと、前記バッファーツリーを前記
検出した対称性に基づいて、当該対称性を反映したバッ
ファーツリーに再構成するステップとを備える。

【００１１】本発明の請求項２に係る課題解決手段にお
いて、前記対称性を検出するステップは、前記論理回路
から異なるバッファーツリーを検出する第１のステップ
と、前記第１のステップで検出した前記バッファーツリ
ーに属するドライバゲートを検出する第２のステップ
と、前記第１のステップで検出した前記異なるバッファ
ーツリーに接続されている同一の親ゲートを検出する第
３のステップと、前記第３のステップで検出した前記親
ゲートが接続されている前記異なるバッファーツリーに
対し、前記ドライバーゲート及び前記親ゲートを含めた
前記ドライバゲートから前記親ゲートに至るパス上に存
在するゲートからなる複数の前記論理構造を検出する第
４のステップと、前記第４のステップで検出した複数の
前記論理構造に対し、同じ前記バッファーツリーに属す
る前記ドライバゲートは同じとみなし、その他の前記論
理構造に属する前記ゲートのうち、同じ種類の前記ゲー
トは同じとみなした場合に同形となる複数の前記論理構
造を検出することで、前記対称性を検出する第５のステ
ップとを含み、前記バッファーツリーを再構成するステ
ップは、前記第５のステップで検出した前記対称性を有
する複数の同形となる前記論理構造に対し、前記ドライ
バーゲートを除く前記論理構造に属する前記ゲートのう
ち、同じ種類の前記ゲートは同じとみなした場合、前記
論理構造が同形になるように、前記論理構造にそれぞれ
属する前記ドライバゲートを交換する第６のステップを
含む。

【００１２】本発明の請求項３に係る課題解決手段は、
前記バッファーツリーの再構成前後の前記論理回路の遅
延を同じにするステップをさらに備える。

【００１３】本発明の請求項４に係る課題解決手段にお
いて、前記第６のステップは、前記バッファーツリーの
ルートからの段数が同じ前記ドライバゲートのみを交換
する。

【００１４】本発明の請求項５に係る課題解決手段にお
いて、前記第６のステップは、前記バッファーツリーの
ルートからの段数が同じであって、かつファンアウト数
が同じ前記ドライバゲートのみを交換する。

【００１５】本発明の請求項６に係る課題解決手段にお
いて、前記第５のステップにおける同じ種類の前記ゲー
トは、回路の論理的な対称性を有するゲートを含む。

【００１６】本発明の請求項７に係る課題解決手段にお
いて、前記回路の論理的な対称性を有するゲートは、複
数の入力を有し、かつ前記複数の入力の接続を交換して
も論理の変わらないゲートである。

【００１７】本発明の請求項８に係る課題解決手段にお
いて、前記対称性を検出するステップは、前記論理構造
に複合論理ゲートが前記ゲートとして属している場合、
前記複合論理ゲートを前記複数の入力の接続を交換して
も論理の変わらないゲートに展開するステップをさらに
含む。

【００１８】本発明の請求項９に係る課題解決手段にお
いて、前記バッファーツリーを再構成するステップは、
前記論理構造を予め定められた順序に並べるステップを
さらに含む。

【００１９】本発明の請求項１０に係る課題解決手段に
おいて、論理記述を入力し、論理記述に対応する前記論
理回路を合成する論理合成ツール内の回路情報を用いる
ように、前記論理合成ツールに組み込まれる。

【００２０】

【発明の実施の形態】

実施の形態１．図１は本発明の実施の形態１における論
理回路最適化方法を説明するフローチャートである。本
実施の形態における論理回路最適化方法は論理合成ツー
ルにてバッファツリーが付加された論理合成後の論理回
路から論理構造の対称性を検出し、検出した対称性に基
づいて、当該対称性を反映した形態のバッファーツリー
に最適化する方法である。以下、フローチャートの各処
理を論理合成後の論理回路の例として図１６に示す回路
を用いて、詳細に説明する。

【００２１】ステップ１０１では、論理合成ツールにて
付加されたバッファーツリーを有する論理合成後の論理
回路を入力する。入力される論理回路の記述フォーマッ
トは、VerilogHDLやVHDL等の論理回路のネットリストを
表現できるフォーマットである。

【００２２】ステップ１０２では、入力された論理回路
から複数の異なるバッファーツリーを検出する。バッフ
ァーツリーの検出は周知の技術を用いて実現できる。次
に、検出した各バッファーツリーに属するドライバゲー
トを検出して、検出したドライバゲートの集合ＢＴjを
生成する。反転論理のゲートを用いたバッファーツリー
の場合、バッファーツリーのルートから数えた奇数段と
偶数段では、論理極性が反転している。従って、奇数段
と偶数段を異なったバッファーツリーとみなして区別
し、独立の集合ＢＴjを生成する。正論理と反転論理の
両方の出力を持つドライバゲートがある場合や正論理と
反転論理のドライバゲートが混在している場合も同様
に、論理極性に応じてバッファーツリーを区別し、独立
の集合ＢＴjを生成する。図１６の回路には、入力ピン
ｓｅｌがルートであるバッファーツリーと、入力ピンｃ
ｌｋがルートであるバッファーツリーとが存在する。そ
れら２つのバッファーツリーに属するドライバゲートの
集合ＢＴjは、ＢＴsel＝｛Ｂ０，Ｂ２｝，ＢＴclk＝
｛Ｂ１，Ｂ３｝となる。ＢＴsel，ＢＴclkはバッファー
ツリーの集合名である。

【００２３】ステップ１０３では、被最適化ゲート群と
呼ばれる、複数のバッファーツリーに関連したゲートの
集合の検出を行なう。詳細に、この処理を説明する。ま
ず、ゲートの全ての入力ピンからファンイン方向に接続
をトレースしたとき、２つ以上の異なるバッファーツリ
ーに属するドライバゲートに到達可能なゲートを検出す
る。この異なるバッファーツリーに到達可能なゲートを
被最適化ゲート群の親ゲートと呼ぶ。また、バッファー
ツリー内のドライバゲートから、この親ゲートに至るパ
ス上に存在するゲートの集合を、被最適化ゲート群と呼
ぶ。この被最適化ゲート群を単位として、バッファーツ
リーの最適化を行なう。ただし、被最適化ゲート群の探
索時に、別の被最適化ゲート群の親ゲートより先のファ
ンイン方向のトレースは行なわないものとする。ネット
リスト内の全てのゲートに対して上述の処理を行ない、
全ての被最適化ゲート群の集合を求める。バッファーツ
リー内のドライバゲートを除いて、複数の被最適化ゲー
ト群に属するゲートは存在しない。図１６の回路には、
４つの被最適化ゲート群（｛Ｆ０，Ｕ０，Ｂ０，Ｂ
１｝，｛Ｆ１，Ｕ１，Ｂ２，Ｂ１｝，｛Ｆ２，Ｕ２，Ｂ
０，Ｂ３｝，｛Ｆ３，Ｕ３，Ｂ２，Ｂ３｝）がある。上
記４つの被最適化ゲート群の最初のゲートが親ゲートで
あり、最後の２つがバッファーツリー内のドライバゲー
トである。

【００２４】ステップ１０４では、被最適化ゲート群
を、被最適化ゲート群に属する各ゲートにより構成され
る論理構造（被最適化ゲート群論理構造）の対称性によ
り分類する。論理構造の対称性は、次のような方法で調
べることができる。まず、各被最適化ゲート群に対し
て、次の４つの条件を持つ論理構造グラフを生成する。

【００２５】（条件１）論理構造グラフは、被最適化ゲ
ート群のゲートに１対１に対応した、ノードを持つ。

【００２６】（条件２）各ノードは、対応するゲートが
バッファーツリーに属するゲートである場合は、バッフ
ァーツリーの集合名を、それ以外のゲートの場合は、ゲ
ートの種類名をタグとして持つ。即ち、同じバッファー
ツリーに属するドライバゲートは同じとみなし、その他
の論理構造グラフに属するゲートのうち、同じ種類のゲ
ートは同じとみなす。

【００２７】（条件３）論理構造グラフは、被最適化ゲ
ート間の接続関係に対応したアークをもつ。

【００２８】（条件４）各アークは、接続の入力と出力
のピン名をタグとしてもつ。

【００２９】図１６の被最適化ゲート群の論理構造グラ
フを図２に示す。図２中のＹ−ＣＬ，Ｙ−Ｄ，Ｙ−Ｓは
アーク、Ｙ，ＣＬ，Ｄ，Ｓは図１４のピン名に対応して
いる。図１６には、４個の被最適化ゲート群が存在する
が、全て同形（タグを含む論理構造グラフの形が同じ）
の論理構造グラフとなる。同形な論理構造をもつ被最適
化ゲート群は、対称な論理構造を持つことを表してい
る。論理構造グラフの同形性により、被最適化ゲート群
を論理構造の対称性により分類できる。４個の被最適化
ゲート群は全て同形の論理構造グラフであるため、分類
は１つだけである。このように、同形となる複数の論理
構造グラフを検出することで、論理構造の対称性を検出
する。

【００３０】ステップ１０５では、ステップ１０４で分
類された被最適化ゲート群を１分類づつ抜きだし、ステ
ップ１０６の処理に渡す。全ての分類の処理が終ると、
ステップ１０７の処理へ進む。

【００３１】ステップ１０６では、論理構造の対称性を
反映するようにバッファーツリーの再構成を行なう。再
構成の方法を詳細に説明する。論理構造グラフのバッフ
ァーツリーのドライバゲートに対応するノードのタグ
を、バッファーツリーの集合名からゲート名に置き換え
たグラフを、実構造グラフと呼ぶ。即ち、実構造グラフ
は、同形となる被最適化ゲート群論理構造に対し、ドラ
イバーゲートを除く被最適化ゲート群論理構造に属する
ゲートのうち、同じ種類のゲートは同じとみなしたグラ
フである。対称性を有する同形の論理構造グラフであっ
ても、バッファーツリーのゲートが異なっていれば、実
構造グラフは同形とはならない。同形の論理構造グラフ
を持つ被最適化ゲート群間では、論理回路の論理を変化
させることなく、同じバッファーツリーの集合内のドラ
イバゲートを交換することができる。実構造グラフが同
形となるように、ドライバゲートの交換を行なうことに
より、異なった実構造グラフ数を削減することができ
る。異なった実構造グラフの数を最小にすることで、バ
ッファーツリーの再構成を行なう。最小化は、例えばド
ライバゲートの交換を全ての実構造グラフの組み合わせ
に対して行うことで実現できる。

【００３２】図３に、図１６の４個の被最適化ゲート群
の実構造グラフを示す。図３に示す実構造グラフＧ０，
Ｇ１，Ｇ２，Ｇ３はそれぞれ図１６に示す論理構造Ｇ
０’，Ｇ１’，Ｇ２’，Ｇ３’に相当する。これらの実
構造グラフは互いに異なっている。実構造グラフＧ１の
バッファーツリーのゲートＢ２と、実構造グラフＧ２の
バッファーツリーのゲートＢ０を交換する。この時、実
構造グラフＧ０とＧ１、及び、Ｇ２とＧ３は同形とな
る。これ以上交換を行なっても、異なった実構造グラフ
の個数は削減できない。従って、異なった実構造グラフ
数は２が最小となる。交換後の実構造グラフＧ０，Ｇ
１，Ｇ２，Ｇ３はそれぞれ図１５に示す論理構造Ｇ
０’，Ｇ１’，Ｇ２’，Ｇ３’に相当する。

【００３３】ステップ１０７では、ステップ１０６で行
なわれた最適化に応じてバッファーツリーを再構成し、
再構成後の論理回路をステップ１０１で入力した論理合
成後の論理回路と同形のフォーマットで出力する。図１
６の論理回路に対して本最適化を行えば、図１５の論理
回路を得ることができる。

【００３４】以上の処理により、論理構造の対称性を反
映した形態にバッファーツリーを最適化することがで
き、最適化後の論理回路におけるレイアウト結果の配線
面積の削減、総配線長の縮小、遅延の短縮が図れる。

【００３５】実施の形態２．実施の形態１において、ス
テップ１０１において入力した論理合成後の論理回路の
遅延と、ステップ１０７において再構成したバッファー
ツリーを有する論理回路の遅延とが異なる場合がある。
そこで、本実施の形態は、バッファーツリーの再構成前
後の論理回路の遅延を同じにする。

【００３６】図４において、ドライバゲート２ａはバッ
ファーツリーのルートから数えて論理段数が１でファン
アウト数が４、ドライバゲート２ｂはバッファーツリー
のルートから数えて論理段数が１でファンアウト数が
３、ドライバゲート２ｃはバッファーツリーのルートか
ら数えて論理段数が２でファンアウト数が２、ドライバ
ゲート２ｄはバッファーツリーのルートから数えて論理
段数が２でファンアウト数が２である。実施の形態１に
おけるステップ１０６のドライバゲートの交換処理にお
いて、交換を行なうバッファーの論理段数が異なってい
たり、ファンアウト数が異なっていたりする場合、論理
合成後の論理回路と遅延が異なったものとなる。論理合
成後の論理回路の遅延とバッファーツリーの最適化後の
論理回路の遅延とを同じにするには、ドライバゲートの
交換処理に、次に述べるような制約を設ければよい。論
理段数を遅延の尺度とする場合、バッファーツリーの論
理段数が同じドライバゲートのみの交換を行なうように
すればよい。この場合は、図４の例では、ステップ１０
６において、ドライバゲート２ａ，２ｂが交換でき、ド
ライバーゲート２ｃ，２ｄが交換できる。また、配線先
のゲートの入力負荷容量とファンアウト数から計算され
る配線容量から遅延を計算する場合、バッファーツリー
のドライバゲートの論理段数とドライバゲートのファン
アウト数とが同じドライバゲートのみに対して交換をお
こなうようにすればよい。この場合は、図４の例では、
ステップ１０６において、ドライバゲート２ｃ，２ｄが
交換できる。

【００３７】以上のように、交換に制限を設けることに
より、バッファーツリーの再構成前後の論理回路の遅延
を変化させずに、バッファーツリーの最適化を行なうこ
とができる。

【００３８】実施の形態３．図５，図６にパス上のゲー
トであるＡＮＤゲートの２つの入力ピン（ピン名はＡと
Ｂ）のみが異なった論理構造グラフの例を示す。実施の
形態１のステップ１０４において、これら２つの論理構
造グラフは、ピン名のタグが異なるため、同形でない。
しかし、ＯＲゲートやＡＮＤゲートは、入力ピンの接続
を互いに入れ換えても論理回路全体の機能には影響しな
い。このような論理ゲートをピン可換な論理ゲートと呼
ぶ。

【００３９】そこで、本実施の形態では、実施の形態１
におけるステップ１０４において、パス上のゲートの論
理を考慮して処理する。即ち、ピン可換な論理ゲートの
入力ピンのみが異なる論理構造グラフは同形とみなす。
例えば、図５，図６におけるタグであるＹ−ＡとＹ−Ｂ
は同じとみなすことにより、図５，図６の論理構造グラ
フを同形とみなす。

【００４０】なお、以上はパス上のゲートがピン可換な
論理ゲートの場合であるが、その他に、パス上のゲート
が、接続を換えても論理回路の機能には影響しない回路
の論理的な対称性を有する回路の場合にも適用しても良
い。この場合も、この回路のタグが異なっても、実施の
形態１におけるステップ１０４において、論理構造グラ
フは同形とみなす。なお、論理的な対称性を有する回路
はピン可換な論理ゲートを含む。なお、ピン可換な論理
ゲートの情報は、例えば、データベースに予め入力され
ていて、ステップ１０４の処理において、そのデータベ
ースにアクセスして、ピン可換な論理ゲートの情報を参
照する。

【００４１】本実施の形態では、ピン可換な論理ゲート
のピンが異なる論理構造グラフは同じとみなすことで、
対称性を有する論理構造グラフの数が増加するため、最
適化能力を強化できる。

【００４２】実施の形態４．複合論理ゲートとは、図７
に示す例のように、ＡＮＤ論理やＯＲ論理や否定論理を
組み合わせた論理を単一のゲートとして実現したゲート
である。一般に、複合論理ゲートはピン可換な論理ゲー
トではない。従って、通常、実施の形態３に示した方法
を適用することができない。

【００４３】しかし、複合論理ゲートは、ピン可換な論
理ゲートに展開することができる。例えば、図７に示す
例であれば、図８に示すＡＮＤ論理やＯＲ論理や否定論
理のピン可換な論理ゲートに展開できる。従って、例え
ば実施の形態１におけるステップ１０４中に、あるいは
ステップ１０４に入る前に、複合論理ゲートをピン可換
な論理ゲートに展開することで、実施の形態３に示した
方法を適用することができる。なお、複合論理ゲート及
びピン可換な論理ゲートの情報は、例えば、データベー
スに予め入力されていて、ステップ１０２の前の複合論
理ゲートをピン可換な論理ゲートに展開する処理の際に
アクセスする。

【００４４】以上の処理により、複合論理ゲートをピン
可換な論理ゲートに展開することにより、対称性を有す
る論理構造グラフの数が増加するため、最適化能力を強
化できる。

【００４５】実施の形態５．図９，図１０に、４ビット
幅のデータ配線に関連した被最適化ゲート群を持つ論理
回路に対する、２種類のバッファーツリーの構成法を示
す。図９と図１０は、出力がnet[2]とnet[3]の被最適化
ゲート群の位置を交換すれば、同じ構成である。実施の
形態１の方式のステップ１０６の処理では、異なった実
構造グラフの個数を最小化することにより最適化を行な
っている。この最適化方式では、図１０の構成を生成す
ることもあり得る。

【００４６】実際のＬＳＩの配置では、入出力ピンの位
置は固定されていることが一般的である。また、ビット
幅をもった入出力ピンについては、ビット順に並べるこ
とが普通である。入出力ピンの位置まで考慮に入れた
時、バッファーと被最適化ゲート群間の配線の複雑さに
関して差が生ずる。例えば、図１０は出力がnet[2]の被
最適化ゲート群とドライバゲートとの間の配線と、出力
がnet[3]の被最適化ゲート群とドライバゲートとの間の
配線との配線が交差しているが、図９は交差していな
い。従って、図１０に示す論理回路は図９に示す論理回
路より複雑である。

【００４７】そこで、本実施の形態では、入出力ピンの
位置まで考慮に入れた時、配線が複雑にならないよう
に、被最適化ゲート群を対応する予め定められたビット
順に並べる。以下、その予め定められたビット順に並べ
る処理を説明する。ビット幅をもった論理回路の情報
は、論理回路のピン名や配線名から判断することができ
る。例えば、図９，図１０の例では、被最適化ゲート群
の出力の配線名が、net[1]，net[2]，net[3]，net[4]と
なっている。この名称からビット幅を持つデータ配線に
関連した被最適化ゲート群であることを認識する。な
お、ビット順は、net[1]，net[2]，net[3]，net[4]であ
ると予め定めておく。この名称から。被最適化ゲート群
をビット順に並べる。以上の予め定められたビット順に
並べる処理は、ステップ１０６において行う。

【００４８】以上のように、実施の形態１の方式のステ
ップ１０６の処理において、予め定められた順番のビッ
ト順に合わせて、図９，図１０のようなバッファーツリ
ーを構成することにより、入出力ピンの位置を考慮した
バッファーツリーの構成が可能となる。

【００４９】実施の形態６．図１１は本実施の形態６に
おける実施の形態１〜５の全ての機能を実現する論理回
路最適化方法を示すフローチャートである。図１１のフ
ローチャートは図１のフローチャートと主として同様で
ある。

【００５０】まず、実施の形態２を実現するために、ス
テップ１０６の処理を、バッファーツリーの再構成前後
の論理回路の遅延を変化させないために、ドライバゲー
トの交換に制限をステップ１０６に加えたステップ１０
６ａの処理に置き換える。

【００５１】実施の形態３，４を実現するために、図１
のステップ１０４の処理を、論理を考慮し、かつ複合論
理ゲートをピン可換な論理ゲートに展開して被最適化ゲ
ート群の分類するステップ１０４ａの処理に変更してい
る。このステップ１０４ａでは、パス上のゲートの論理
を調べるために、ピン可換な論理ゲート等の論理情報を
格納しているデータベース１０９にアクセスを行う。

【００５２】実施の形態５を実現するために、論理回路
から各配線のビット順等を含むビット幅情報１１０の抽
出を行う処理（ステップ１０８）を追加し、ステップ１
０６の処理をビット順序に考慮したバッファーツリーの
再編成を行う処理をステップ１０６ａに追加している。
図１１中のその他の符号は、図１中の符号に対応してい
る。

【００５３】以上のように、ステップ１０４，１０６を
それぞれステップ１０４ａ，１０６ａに置き換え、ステ
ップ１０８、データベース１０９のアクセスの各処理を
図１に追加することで、実施の形態１〜５の全ての機能
を実現する論理回路最適化方法が得られる。

【００５４】実施の形態７．実施の形態１〜６では、論
理合成ツールにて付加されたバッファツリーを有する論
理合成後の論理回路をステップ１０１において入力し
て、バッファーツリーの最適化を行なう場合を示した
が、この方式は論理合成ツール内部に組み込んで実現す
ることもできる。

【００５５】図１９は、論理合成ツールの動作のアルゴ
リズムを示すフローチャートである。ハードウェア記述
言語（ＨＤＬ）による記述を入力し、論理回路を出力す
る。内部フローは、まず、ステップ２０１では、ＨＤＬ
記述を読み込む。ステップ２０２では、ＨＤＬ記述から
論理を抽出し、抽象的なネットリストへ変換する。ステ
ップ２０３では、ピン可換な論理ゲート等のゲートの論
理情報を格納しているデータベース１０９にアクセスを
行って、ステップ２０３において変換されたネットリス
トに抽象的なネットリストの仮想的なセルを実際のセル
にマッピングする。ステップ２０４では、マッピングし
たネットリストにバッファーツリーの付加を行う。ステ
ップ２０５では、バッファーツリーを付加したネットリ
ストから、最後に合成された論理回路を出力する。ステ
ップ２０１の処理を行う過程で、詳細なビット順序の情
報１１０が得られる。ビット順序の情報１１０の一部
は、ネットやセル名をつける為に、ステップ２０５にお
いて使用される。なお、詳細なビット順序の情報１１０
及びデータベース１０９に格納されているピン可換な論
理ゲート等のゲートの論理情報は、論理合成ツール内の
回路情報に含まれる。

【００５６】図１２は本発明の実施の形態７における論
理回路最適化方法が論理合成ツール内に組み込まれた場
合のフローチャートであって、図１９に示すフローチャ
ートで表される論理合成ツールの動作のフロー内に実施
の形態１〜６におけるバッファーツリーの最適化処理
（ステップ１００）を組み込んだ場合のフローチャート
である。ステップ１００は図１や図１１のフローチャー
トに対応する。論理合成ツールの動作のアルゴリズムに
組み込むことにより、ゲートの論理情報のデータベース
１０９，ビット順序の情報１１０を共用できる。なお、
ステップ１００にはステップ１０１を含まない。

【００５７】以上のように、論理合成ツールに組み込む
ことにより、実施の形態１〜６における論理合成後の論
理回路を入力する処理（ステップ１０１）をなくすこと
ができ、処理の単純化や高速化を図ることができる。ま
た、論理合成ツールはゲートの論理情報をもっているた
め実施の形態３、４の処理を行なうために、ゲートの論
理情報を別に入力する必要がなくなる。また、実施の形
態５のビット幅を持ったデータ配線の情報も容易に得る
ことができるようになる。

【００５８】

【発明の効果】本発明請求項１によると、バッファーツ
リーを対称性が反映されたバッファーツリーに再構成す
ることで、配線面積が小さく、総配線長が短く、遅延が
短いレイアウト結果を得ることができるという効果を奏
す。

【００５９】本発明請求項２によると、対称性が反映さ
れたバッファーツリーが得られるという効果を奏す。

【００６０】本発明請求項３によると、最適化前後の論
理回路の遅延を同じにすることで、論理合成後の論理回
路と同じ遅延時間を実現する論理回路が得られるという
効果を奏す。

【００６１】本発明請求項４によると、バッファーツリ
ーのルートからの段数が同じドライバゲートのみを交換
することで、最適化前後の論理回路の遅延を同じにする
ことができ、論理合成直後の論理回路と同じ遅延時間を
実現する論理回路が得られるという効果を奏す。

【００６２】本発明請求項５によると、ファンアウト数
が同じバッファーのみを交換することで、最適化前後の
論理回路の遅延を同じにすることができ、論理合成直後
の論理回路と同じ遅延時間を実現する論理回路が得られ
るという効果を奏す。

【００６３】本発明請求項６によると、同形となる論理
構造の個数が増加し、最適化能力を強化できるという効
果を奏す。

【００６４】本発明請求項７によると、使用する入力ピ
ンが異なっていても、当該ゲートは全て同じとみなすこ
とで、同形となる論理構造の個数が増加し、最適化能力
を強化できるという効果を奏す。

【００６５】本発明請求項８によると、複合論理ゲート
を複数の入力の接続を交換しても論理の変わらないゲー
トに展開した後、使用する入力ピンが異なっていても、
当該ゲートは全て同じとみなすことで、同形となる論理
構造の個数が増加し、最適化能力を強化できるという効
果を奏す。

【００６６】本発明請求項９によると、論理構造を予め
定められた順序に並べることで、入出力ピンの位置を考
慮したバッファーツリーの構成が可能となるという効果
を奏す。

【００６７】本発明請求項１０によると、論理合成ツー
ルに組み込むことにより、論理回路の入力処理をなくす
ことができ、処理の単純化や高速化を図ることができる
という効果を奏す。

【図面の簡単な説明】

【図１】 本発明の実施の形態１における論理回路最適
化方法を説明するフローチャートである。

【図２】 被最適化ゲート群の論理構造グラフの一例を
示す図である。

【図３】 被最適化ゲート群の実構造グラフの一例を示
す図である。

【図４】 本発明の実施の形態２における遅延を変化さ
せないゲートの交換を説明する図である。

【図５】 本発明の実施の形態３におけるピン可換な論
理ゲートを含む論理構造グラフの例を示す図である。

【図６】 本発明の実施の形態３における図５とピン名
が異なるピン可換な論理ゲートを含む論理構造グラフの
例を示す図である。

【図７】 本発明の実施の形態４を説明するための複合
論理ゲートの例を示す回路図である。

【図８】 図７に示す複合論理ゲートの等価回路を単純
論理ゲートを組み合わせて構成した回路図である。

【図９】 本発明の実施の形態５を説明するためのビッ
ト順を考慮したバッファーツリーの構成図である。

【図１０】 本発明の実施の形態５を説明するためのビ
ット順を考慮しないバッファーツリーの構成図である。

【図１１】 本発明の実施の形態６における論理回路最
適化方法を示すフローチャートである。

【図１２】 本発明の実施の形態７における論理回路最
適化方法が論理合成ツール内に組み込まれた場合のフロ
ーチャートである。

【図１３】 バッファーツリーの一例を示す図である。

【図１４】 対称な論理構造を持った論理回路の一例を
示す図である。

【図１５】 対称性を反映したバッファーツリーを付加
した論理回路の一例を示す回路図である。

【図１６】 対称性を喪失したバッファーツリーを付加
した論理回路の一例を示す回路図である。

【図１７】 図１５の論理回路に対して最適化配置を行
った論理回路図である。

【図１８】 図１６の論理回路に対して最適化配置を行
った論理回路図である。

【図１９】 論理合成ツールの動作のアルゴリズムを示
すフローチャートである。

【符号の説明】

２ａ，２ｂ，２ｃ，２ｄ ドライバゲート、Ｇ０，Ｇ
１，Ｇ２，Ｇ３ 実構造グラフ、Ｇ０’，Ｇ１’，Ｇ
２’，Ｇ３’ 論理構造。

Claims (10)

【特許請求の範囲】
1. 【請求項１】 バッファーツリーを有する論理回路の最
   適化方法であって、 前記論理回路から論理構造の対称性を検出するステップ
   と、 前記バッファーツリーを前記検出した対称性に基づい
   て、当該対称性を反映したバッファーツリーに再構成す
   るステップと、を備えた論理回路最適化方法。
2. 【請求項２】 前記対称性を検出するステップは、 前記論理回路から異なるバッファーツリーを検出する第
   １のステップと、 前記第１のステップで検出した前記バッファーツリーに
   属するドライバゲートを検出する第２のステップと、 前記第１のステップで検出した前記異なるバッファーツ
   リーに接続されている同一の親ゲートを検出する第３の
   ステップと、 前記第３のステップで検出した前記親ゲートが接続され
   ている前記異なるバッファーツリーに対し、前記ドライ
   バーゲート及び前記親ゲートを含めた前記ドライバゲー
   トから前記親ゲートに至るパス上に存在するゲートから
   なる複数の前記論理構造を検出する第４のステップと、 前記第４のステップで検出した複数の前記論理構造に対
   し、同じ前記バッファーツリーに属する前記ドライバゲ
   ートは同じとみなし、その他の前記論理構造に属する前
   記ゲートのうち、同じ種類の前記ゲートは同じとみなし
   た場合に同形となる複数の前記論理構造を検出すること
   で、前記対称性を検出する第５のステップと、を含み、 前記バッファーツリーを再構成するステップは、 前記第５のステップで検出した前記対称性を有する複数
   の同形となる前記論理構造に対し、前記ドライバーゲー
   トを除く前記論理構造に属する前記ゲートのうち、同じ
   種類の前記ゲートは同じとみなした場合、前記論理構造
   が同形になるように、前記論理構造にそれぞれ属する前
   記ドライバゲートを交換する第６のステップを含む請求
   項１記載の論理回路最適化方法。
3. 【請求項３】 前記バッファーツリーの再構成前後の前
   記論理回路の遅延を同じにするステップをさらに備えた
   請求項１記載の論理回路最適化方法。
4. 【請求項４】 前記第６のステップは、 前記バッファーツリーのルートからの段数が同じ前記ド
   ライバゲートのみを交換する請求項２記載の論理回路最
   適化方法。
5. 【請求項５】 前記第６のステップは、 前記バッファーツリーのルートからの段数が同じであっ
   て、かつファンアウト数が同じ前記ドライバゲートのみ
   を交換する請求項２記載の論理回路最適化方法。
6. 【請求項６】 前記第５のステップにおける同じ種類の
   前記ゲートは、回路の論理的な対称性を有するゲートを
   含む請求項２記載の論理回路最適化方法。
7. 【請求項７】 前記回路の論理的な対称性を有するゲー
   トは、複数の入力を有し、かつ前記複数の入力の接続を
   交換しても論理の変わらないゲートである請求項６記載
   の論理回路最適化方法。
8. 【請求項８】 前記対称性を検出するステップは、 前記論理構造に複合論理ゲートが前記ゲートとして属し
   ている場合、前記複合論理ゲートを前記複数の入力の接
   続を交換しても論理の変わらないゲートに展開するステ
   ップをさらに含む請求項７記載の論理回路最適化方法。
9. 【請求項９】 前記バッファーツリーを再構成するステ
   ップは、 前記論理構造を予め定められた順序に並べるステップを
   さらに含む請求項２記載の論理回路最適化方法。
10. 【請求項１０】 論理記述を入力し、論理記述に対応す
    る前記論理回路を合成する論理合成ツール内の回路情報
    を用いるように、前記論理合成ツールに組み込まれた請
    求項２記載の論理回路最適化方法。