JPH0546698A - 論理回路の自動合成方式 - Google Patents

Abstract

(57)【要約】 【目的】 テクノロジマッピグの際の回路とライブラリ
のマッチング処理を高速化する。 【構成】 入力ネットリストまたは論理式をポーランド
記述ストリングに変換する初期回路生成部１０４と、回
路中のインバータを入力側へ伝播して、さらに２段以上
にまたがる同種類のゲートを一まとめにする処理を行う
回路整形部１０５と、整形された回路を、入力信号の遅
延制約情報およびライブラリ中のゲート遅延時間を参照
して到着時間が早い入力信号ほど多い段数で出力に到達
するような２入力ゲートのみで構成される２入力ポーラ
ンド記述ストリングに展開する２入力ゲート展開部１０
６と、２入力ゲートに展開された回路のポーランド記述
ストリングとライブラリ中のゲートのポーランド記述ス
トリングとの、マッチング処理を行い、マッチングに成
功したら、コスト計算部１０８を呼び出してコスト計算
を行い、すべてのマッチングが終了したら出力正極性の
マッチング結果と出力負極性のマッチング結果との比較
を行って最適解を保存するマッチング処理部１０７とを
有する論理回路の自動合成方式。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は論理回路の自動合成方式
に関する。

【０００２】

【従来の技術】従来の論理回路の自動合成方式は、テク
トロジマッピングの際に回路を、ゲートを表すノードと
ゲート間の接続を表すネットのデータ構造で記述し、ラ
イブラリも同様のデータ構造で記述していた。

【０００３】

【発明が解決しようとする課題】上述した従来の論理回
路の自動合成方式では、テクトノロジマッピングの際に
回路とライブラリのマッチング処理でネットワークをト
レースする処理が必要となり、処理時間がかかるという
欠点があった。

【０００４】

【課題を解決するための手段】本発明の論理回路の自動
合成方式は、１出力の組み合せ論理回路のネットリスト
または論理式と、その論理回路への入出力信号の遅延制
約情報と、その論理回路を実現する対象テクノロジの各
ゲートの機能とゲート機能のポーランド記述ストリング
とゲート遅延時間の情報を含むライブラリを入力とし、
入力ネットリストまたは論理式をポーランド記述ストリ
ングに変換する初期回路生成部と、回路中のインバータ
を入力側へ伝播して、さらに２段以上にまたがる同種類
のゲートを一まとめにする処理を行う回路整形部と、整
形された回路を、入力信号の遅延制約情報およびライブ
ラリ中のゲート遅延時間を参照して到着時間が早い入力
信号ほど多い段数で出力に到達するような２入力ゲート
のみで構成される２入力ポーランド記述ストリングに展
開する２入力ゲート展開部と、２入力ゲートに展開され
た回路のポーランド記述ストリングとライブラリ中のゲ
ートのポーランド記述ストリングとの、出力極性を考慮
したマッチング行列を使ってマッチング処理を行い、マ
ッチングに成功したら、面積と遅延時間のコスト計算を
行うコスト計算部を呼び出してコスト計算を行い、すべ
てのマッチングが終了したら出力正極性のマッチング結
果と出力負極性のマッチング結果との比較を行って最適
解を保存するマッチング処理部と、最適解を対象テクノ
ロジの論理回路図として出力する回路生成部とを有して
いる。

【０００５】

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

【０００６】図１は本発明の一実施例を示すフローチャ
ートである。

【０００７】入力論理回路１０１は、１出力の組み合せ
論陸回路を記述したネットリストまたは論理式であり、
遅延制約情報１０２は、入力信号の対象回路への到着時
間および対象回路の最終段に到達するまでにかかる時間
の制限値を格納したパラメータファイルである。

【０００８】ライブラリ１０３は、対象テクノロジの各
ゲート機能と、ゲート遅延時間と、そのゲートの機能を
ポーランド記述ストリングで記述したものと、さらにそ
のゲートが複合ゲータや多入力ゲートの場合には２入力
のゲートで展開したときの全ての展開パターンをポーラ
ンド記述ストリングで記述したものが格納されている。

【０００９】初期回路生成部１０４は、入力論理回路図
１０１を入力とし、ライブラリ１０３を参照して、回路
を出力側から入力側へトレースして多入力ゲートのまま
のポーランド記述ストリングで回路図を記述する処理を
行う。

【００１０】回路整形部１０５は、回路中に現れるイン
バータをすべて入力側に伝播して、さらに２段以上にま
たがる同一ゲートを一まとめにする処理を行う。

【００１１】２入力ゲート展開部１０６は、整形処理さ
れた回路に対し、遅延制約情報１０２の入力信号到着時
間と、ライブライ１０３のゲート遅延時間を参照して、
多入力ゲートを、到着時間の早い信号ほど多い段数で、
遅い信号ほど少ない段数で出力段に到着するような形で
２入力ゲートに展開する処理を行う。

【００１２】マッチング処理部１０７は、２入力ゲート
に展開した回路のポーランド記述とライブラリ中の機能
ブロックのポーランド記述とをマッチングして成功した
らコスト計算部１０８を呼び出してコスト計算を行い最
適解を保存する。

【００１３】次に、図２，３，４，５，６および７を参
照してマッチング処理部１０７を説明する。

【００１４】図２はマッチング処理部１０７の詳細なフ
ローチャートである。

【００１５】まず、処理２０１では、回路中のあるゲー
トをルートとするツリー構造を回路のサブツリーとし
て、入力側に近いサブツリーから順にマッチング対象と
する。図３に回路のサブツリーの一例を示す。また、図
４に、図３の回路のポーランド記述による表現を示す。

【００１６】図２の処理２０２では、処理２０１で選択
したサブツリーについて、そのサブツリーの入力数以下
の入力をもつライブラリ中の機能ブロックを１つ選択す
る。処理２０３では、回路のサブツリーのポーランド記
述ストリングとライブラリのポーランド記述ストリング
とをマッチングする。

【００１７】マッチングに成功したら処理２０４（コス
ト計算部１０８による）で、ライブラリ１０３のブロッ
クのセル数情報およびゲート遅延情報を参照してサブツ
リーのセル数と最悪の遅延時間を計算して、遅延制約情
報１０２の遅延時間に収まる範囲内でセル数が最小とな
るようなマッチング結果を最適解として保存する。

【００１８】コスト計算および最適解の保存の際に、サ
ブツリーのルートノードの出力極性が正極性となるよう
なマッチング結果と、出力極性が負極性となるようなマ
ッチング結果を考慮して、それぞれのマッチング結果の
最適解を求めて保存する。

【００１９】図５に、極性を考慮したマッチングの一例
を示す。図５（Ａ）はサブツリーｎのモデル、図５
（Ｂ）はサブツリーｍのマッチング結果である。サブツ
リーｎをマッチングした結果、入力極性が反転する場合
には、図５（Ｃ）に示すように、サブツリーｎのルート
の入力側の既にマッチング済みのサブツリーｍの出力負
極性でのマッチング結果の最適解と、サブツリーｎの入
力極性が反転しない場合には、図５（Ｄ）に示すよう
に、サブツリーｍの出力正極性でのマッチング結果の最
適解と、それぞれサブツリーｎのルートのマッチング結
果とを接続してサブツリーｎのマッチング結果とする。

【００２０】すべてのライブラリブロックとのマッチン
グが終了するまで、処理２０２以下を繰り返し、ライブ
ラリブロックがなくなったら処理２０１で次のサブツリ
ー選択以下の処理を繰り返す。

【００２１】次に図６を参照して回路のサブツリーのポ
ーランド記述とライブライのポーランド記述とのマッチ
ング処理２０３を説明する。

【００２２】回路のポーランド記述Ｃ〔ｉ〕，

【００２３】

【００２４】と、ライブライの機能ブロックのポーラン
ド記述Ｌ〔ｊ〕，

【００２５】

【００２６】の要素同士を比較する。回路Ｃ〔ｉ〕、ラ
イブラリ〔ｊ〕がともにオペレータの場合、処理５０１
でマッチング行列による判定を行う。マッチング行列の
定義は以下のようである。

【００２７】 返却値＝Ｍ〔回路オペレータ〕〔極性反転フラグ〕〔ライブラリオペレータ〕 回路オペレータ ＡＮＤ １ ＯＲ ２ ＸＯＲ ３ ＸＮＯＲ ４ 極性反転フラグ 出力極性そのまま０ 出力極性反転 １ ライブラリオペレータ ＡＮＤ １ ＯＲ ２ ＸＯＲ ３ ＸＮＯＲ ４ ＮＡＮＤ ５ ＮＯＲ ６ 返却値 入力極性そのまま，出力正極性 ０ 入力極性反転， 出力正極性 １ 入力極性そのまま，出力負極性 ２ 入力極性反転， 出力負極性 ３ マッチ失敗 −１ 図７にマッチング行列を使用したマッチングの一例を示
す。

【００２８】図７（Ａ）は回路のポーアンド記述とライ
ブラリのポーランド記述であり、図７（Ｂ）は、ノード
１のマッチングの判定である。マッチング行列の返却値
が１であるため、サブツリーのノード１のＯＲは入力極
性を反転してライブライのＮＡＮＤとマッチすることが
出来る。

【００２９】図７（Ｃ）は、ノード２のマッチングの判
定である。図７（Ａ）でノード１が入力極性反転でマッ
チしたため、マッチング行列の極性反転フラグを１とし
てマッチする。

【００３０】図７（Ｄ）は、マッチング後の回路であ
る。マッチングに成功したらＣの要素番号ｉ，Ｌの要素
番号ｊをともに１つ先に進める。

【００３１】回路Ｃ〔ｉ〕がオペレータかつライブラリ
Ｌ〔ｊ〕がともにオペレータでない場合、Ｃの要素番号
ｉ，Ｌの要素番号ｊをともに１つ先に進める。

【００３２】回路Ｃ〔ｉ〕がオペレータでなく、ライブ
ラリＬ〔ｊ〕がオペレータの場合、マッチング不可とす
る。

【００３３】以上の処理を回路のポーランドＣの要素ｉ
が最大値ｃｍａｘを越えるか、ライブラリのポーランド
Ｌの要素ｊが最大値ｌｍａｘを越えるまで行う。

【００３４】マッチング成否の判定はｉがｊ以上ならば
成功とし、ｉがｊ未満またはマッチング行列の返却値に
よって失敗とする。

【００３５】以上のマッチング処理部１０７により得ら
れた最適解を回路生成部１０９で対象テクノロジの論理
回路図としてのネットリストデータ構造に置き換えてか
ら出力回路図１１０を出力する。

【００３６】

【発明の効果】以上説明したように本発明は、回路及び
ライブラリを２入力ゲートのポーランド記述ストリング
で表現することにより、テクノロジマッピング処理がス
トリング列の単純な比較ですみ、マッチング行列を利用
することによりオペレータのマッチング成否の判定でＩ
Ｆ−ＥＬＳＥ文等の条件文を使わずに一度の動作で判定
を行うことができ、マッチング処理を高速に行うことが
できるという効果がある。

【００３７】また、出力極性を正極性，負極性の両方で
マッチング処理を行い、それぞれ面積，遅延時間等のコ
スト計算を行って比較することにより、コスト最小の論
理回路図を合成できるという効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例を示すフローチャートであ
る。

【図２】本実施例におけるマッチング処理部の詳細なフ
ローチャートである。

【図３】回路中のサブツリーの一例を示す。

【図４】図３に示した回路のポーランド記述による表現
を示す。

【図５】出力極性を考慮したマッチングの一例を示す。

【図６】サブツリーのポーランド記述とライブラリのポ
ーランド記述のマッチング処理の一例を示す。

【図７】マッチング処理の一例を示す。

【符号の説明】

１０１ 入力論理回路図 １０２ 遅延制約情報 １０３ ライブラリ １０４ 初期回路生成部 １０５ 回路整形部 １０６ ２入力ゲート展開部 １０７ マッチング処理部 １０８ コスト計算部 １０９ 回路生成部 １１０ 出力論理回路図

Claims (1)

【特許請求の範囲】
1. 【請求項１】 １出力の組み合せ論理回路のネットリス
   トまたは論理式と、その論理回路への入出力信号の遅延
   制約情報と、その論理回路を実現する対象テクノロジの
   各ゲートの機能とゲート機能のポーランド記述ストリン
   グとゲート遅延時間の情報を含むライブラリを入力と
   し、 入力ネットリストまたは論理式をポーランド記述ストリ
   ングに変換する初期回路生成部と、 回路中のインバータを入力側へ伝播して、さらに２段以
   上にまたがる同種類のゲートを一まとめにする処理を行
   う回路整形部と、 整形された回路を、入力信号の遅延制約情報およびライ
   ブラリ中のゲート遅延時間を参照して到着時間が早い入
   力信号ほど多い段数で出力に到達するような２入力ゲー
   トのみで構成される２入力ポーランド記述ストリングに
   展開する２入力ゲート展開部と、 ２入力ゲートに展開された回路のポーランド記述ストリ
   ングとライブラリ中のゲートのポーランド記述ストリン
   グとの、出力極性を考慮したマッチング行列を使ってマ
   ッチング処理を行い、マッチングに成功したら、面積と
   遅延時間のコスト計算を行うコスト計算部を呼び出して
   コスト計算を行い、すべてのマッチングが終了したら出
   力正極性のマッチング結果と出力負極性のマッチング結
   果との比較を行って最適解を保存するマッチング処理部
   と、 最適解を対象テクノロジの論理回路図として出力する回
   路生成部とを有する論理回路の自動合成方式。