JPH0451367A - 論理回路の合成装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明は論理回路を自動的に合成するための装置に係
り、特にタイミングの制約に基づいて論理回路を合成す
るための装置に関する。

（従来の技術） 論理合成技術の発展によって、レジスタ転送レベルの回
路記述から構造レベルの回路を自動生成できるようにな
った。

ところが、熟練設計者が設旧した論理回路と自動合成さ
れた論理回路の性能（特に動作速度なと）を比較すると
、人手設計のほうが優れている。というのは、熟練設計
者は、回路の動作周波数を満たずようにレジスタのクロ
ックを決定し、クリティカルパスを絶えず考慮しながら
論理回路を設旧しているからである。すなわち、どの様
な構造を持った回路にすれば信号遅延時間が少なくて済
むかを熟知しているからである。

また設計者はタイミング解析ツールを使用することによ
って、論理回路の詳細な信号遅延時間の解析結果を入手
できるようになったが（例えばとのパスが最長遅延もし
くは最小遅延パスであるか）これは設旧者が所望する論
理回路の設計を−通り終った後てないと使用できなった
。従って、論理合成後の論理回路に対してタイミング解
析を行い、設ｇｌｆｉ−が考えている制約に違反する箇
所を人手で修１丁−する必要があった。

一方、最近の論理合成技術では、ライブラリ化されたハ
ードウェアコンポーネント（ライブラリセル）をゲート
回路に割り当てた後で、論理合成システムに内蔵したタ
イミング解析手段を用いてタイミング解析を実行し、こ
の結果が設旧者の所望するタイミング制約を満たしてい
ない場合は、スピードの遅いハードウェアコンポーネン
トをスピードの速いハードウエアコンボーネン（・に交
換し、再びタイミング解析を実行してタイミング制約が
満たされているかとぅがを調べ、これが満たされるまで
、もしくはその限界まで繰り返すという手法をとってい
た。

他方では、タイミンク情報をハードウェアコンポーネン
トのテクノロジに依存しないライブラリ化された抽象コ
ンポーネントに格納し、これを合成時に使用する手法も
考えられている。この技術に関しては、特開昭６３−１
５５２６８号公報において示されている。

しかし抽象コンポーネントは入力数が可変であったりコ
ンポーネント自体ビット幅を有しているので、許される
ビット幅に応じた膨大な数のコンポーネントをライブラ
リに登録する必要があり、従ってこの手法では多大な記
録容量を必要とじていた。

（発明か解決しようとする課題） 」二連したように従来技術では、部品ライブラリとして
用意されたコンポーネントによって回路が構成されてい
ないと、タイミング解析が実行できないという不具合が
あった。

また、レジスタ転送回路から変換された抽象回路では元
来入出力数が可変のため、遅延時間を使用可能な全ての
抽象回路に持たせて、それぞれをライブラリ化するとデ
ータ量が膨大になり不紅済である。

本発明は、このような点に関してなされたもので、その
１」的は、同一機能を有するが、しかし異なる構造を持
ったハードウェアに適した遅延時間の割（＝Ｉ手段を用
いて抽象回路の段階でタイミング解析を実行し、その結
果のタイミング違反情報を合成開始前あるいは途中の段
階で使用することで高性能な論理回路を合成することが
可能な装置を提ｆ几するこ吉である。

［発明の構成］ （課題を解決するための手段） 上記課題を解決するために本発明では、論理回路を自動
生成するだめの論理回路の合成装置において、合成の開
始前、あるいはその途中で生成された抽象回路を使用【
、てタイミング解析を行なうために、前記抽象回路を構
成している素子に任意の遅延時間を与える手段と、与え
られた遅延時間を用いてタイミング解析を行い、タイミ
ング制約条件が満たされるかどうかを検出する手段と、
前記検出されたタイミング解析結果を使用してタイミン
グ制約条件が満たされるように前記抽象回路を論理回路
に変換あるいは合成する手段と、前記タイミング制約に
違反する回路の遅延時間を最適化するために回路を変換
あるいは合成する手段と、を具備することを特徴とする
。

（作用） 本発明の装置によれば、機能動作仕様記述から変換され
た抽象回路を構成する素子に任意の遅延時間を割当てる
ことができ、この遅延時間を使用して合成前あるいは合
成途中にタイミング検証が行える。さらにタイミンク解
析の結果を使用して遅延時間の制約を満足するように抽
象回路を論理回路に変換または合成し最適化を繰返して
行えるので、スピードの速い論理回路の合成ができる。

（実施例） 以下、本発明の実施例を図面を参照して説明する。

第１図は本発明の一実施例にかかる論理合成装置の構成
を示すブロック図である。

第１図の１０１は機能動作仕様を表すレジスタ転送仕様
の入力部で、レジスタ転送記述もしくは該仕様をスケマ
チック表示した機能ブロック図である。１〔〕２は設計
データ変換部（トランスレタ）である。この変換部］０
２は人力部１０１のレジスタ転送記述を構文解析して、
該記述に忠実な初期抽象回路を生成する。また機能ブロ
ック図の場合はスケマチック図よりネットワーク情報と
図形情報を抽出して初期抽象回路を生成する。１０３は
該抽象回路のネットワーク情報を格納する膜種データベ
ース部である。］０４はタイミング制約入力部で、レジ
スタ転送仕様の任意の点に制約遅延時間を設定できる。

１０５はタイミング制約設定及び違反検出部で、トラン
スレータ部１０２で生成された抽象機能素子の入出力数
が一定でないため、設計データベース部１０３から該初
期抽象回路の素子のタイプと入力数またはビット幅を取
り出し、該素子の遅延時間を計算し割り付ける遅延時間
計算割（＝Ｊ手段と、入力部１０４からタイミング制約
を取り込む手段と、ｊＦｊえられたタイミング制約が、
論理合成前及び途中の抽象回路もしくは論理回路におい
て実現されるかどうかを検証するクリティカルパス探索
手段から構成されている。］０６は論理合成部で、前記
タイミング制約違反検出部１０５で検出された違反回路
を解析して該回路を最適化対象回路に分割し、さらに最
適化目標値を設定し、該最適化目標値に従って抽象回路
を具象回路に展開し、また、冗長な回路の簡単化及び、
テクノロジに依存した回路素子の割付けを行う各処理手
段から構成されている。１０７は設計データ変換部で、
記述変換やスケマチック図の生成を行うためのもので、
具体的には設旧データベースに格納されている回路情報
を論理回路（構造記述またはスケマチック図）に変換す
る。

１０８は合成された論理回路の出力部である。

第２図は、第１図で説明した論理合成装置の処理フロー
を説明する図である。

２０１は、レジスタ転送記述及びタイミング制約を人力
するステップで、２０２は、記述の動作解析を行って初
期抽象回路を生成するステップである。２０３は抽象回
路素子に遅延時間を＃１算して割り付けるステップであ
る。２０４は、割り（＝１けた遅延時間を使用して全体
回路の遅延時間計算を行い、クリティカルパスを検出し
タイミング制約が守られているかどうかを調べるステッ
プである。制約が守られていないときは、制約に違反し
ている箇所をレボ−１・もしくはスケマチック表示する
。また、該タイミンク制約に違反しているパスに関して
は、この制約か実現されるようにスピドの速い回路に展
開して最適化を行い（２０５）ステップ２０３及び２０
４を繰り返して該タイミング制約が満たされているかど
うかを調べ、ノ＼−ドウニアコンポーネントを割り付け
る（２０６）ことによって合成を終了する。以下各ステ
ップの処理内容について詳細に説明する。

その前にレジスタ転送記述について説明する。

レジスタ転送記述では、回路の素子と認識されるファシ
リティ（外部端子、内部信号、レジスタ、メモリなど）
とハードウェアの詳細まで立ち入らすに機能を表せる演
算子、組み込み関数（加算、減算など）、ファシリティ
の動作を表すプロセス（レジスタの非同期クリアなと）
の記述や状態遷移表現が可能である。以下ファシリティ
、演算子、組み込み関数、プロセス、ステー１・を抽象
機能素子と呼ぶ。

ここで抽象機能素子の遅延時間について説明する。論理
合成は最終的に抽象機能素子を論理素子（ゲート）まで
展開して最適化を行い、これに所望のテクノロジからな
るハードウェアのライブラリセルを割り（＝１けるもの
である。しかしレジスタ転送レベルの回路は機能レベル
の回路であり、必］０ ずしもハードウェアとして最適化された回路、すなわち
ケート数とかゲート段数を考慮して設Ｊ１された回路と
はなっていない。従って最初からすべての抽象機能素子
にハードウェアのセルを割り付けて考えるのは得策では
ない。また同一機能のセルであっても異なるスピードの
セルを割りイ＝Ｉけることによって実遅延時間は変わっ
てしまうので、レジスタ転送レベルの回路の各抽象機能
素子に実時間を割り当てて信号伝播パスの遅延時間を４
算するのは適当ではない。そこでこの実施例の装置では
、基本的なゲートを単位としだゲート段数を遅延時間の
代わりに用いる。またハードウェアのＮＯＲゲートのセ
ルなどでは入力数か増加するにしたがって実遅延時間が
かなり異なってくるので（例えば６人力のＮＯＲは２人
力ＮＯＲの４倍の遅延時間を有する）、このようなゲー
トでは人力数を考慮して段数を与えることにする。

つぎに第１図の検出部］０５のザブ手段である遅延時間
計見開（＝Ｊ手段の処理について説明する。

まず論理合成途中で一部の抽象機能素子が具体的なハー
ドウェアセルに変換されてもクリティカルパスの検索が
可能なように、ハードウェアセルのライブラリに存在す
るセルについては、それを構成する論理素子を用いて段
数を計算ｌ、遅延情報のライブラリに格納する。またレ
ジスタ転送レベルの抽象機能素子及び合成途中で生成さ
れる抽象機能素子または論理素子については、設Ｒ１デ
ータベース部１０３から抽象機能素子を取り出して、該
素子のタイプやビット幅や入力数を変数と１７で、それ
らが論理合成途中に典型的な抽象素子や論理素子からな
るネットワークに展開されるとした遅延モデルや、論理
素子そのものの遅延モデルに従って段数を５１算して、
設計データベースに格納する。ここで抽象機能素子の遅
延段数は抽象機能素子の展開後の回路によって異なって
くるので、前記段数の計算を行う手段とともに、遅延モ
デルを複数用意しておく。またこの処理で一度計算した
遅延段数については抽象機能素子のタイプ、入力数、ビ
ット幅と一緒にワーク記憶領域に保存しておき、膜種デ
ータベースから同一タイプの抽象機１　］ 能素子が再び取り出されたらハッシュイングを行って、
該ワーク記憶領域のデータを取り出して割りイ【ｊける
。

ここで第６図の１０ピッｌ−２人力全加算器６゜Ｏを例
にとって段数計算を説明する。

いま論理合成で加算器をリップルキャリー型の加算器に
展開することになっている場合、第６図（ｂ）の回路に
展開されるものとして遅延モデルを考える。第６図（ｂ
→の回路は５個の２ビツト２人力の全加算器６０１〜６
０５より構成されている。これらは下位ビットで計算さ
れたキャリの信号に対してシリアルに接続されており（
６０１〜６０５）、入力ＣＩからＣＯまでのパスが最大
遅延段数を有している。また出力データｓく８：９　＞
　（６０９）も該段数と等しい遅延段数を有している。

従って２ビツト２人力の加算器の最大遅延段数が６段で
あることがわかっているとき、］０ピッｌ−２人力全加
算器の最大遅延段数は３０段になる。

以下第３図を用いて第１図の検出部１０５におけるクリ
ティカルパス検索手段の処理について説明する。いま、
クリティカルパスの探索域は入力レジスタ間、入力−出
力間、レジスターレジスタ間、レジスター出力間とする
。

処理を開始する（　３０１．　）。人力属性を有するフ
ァシリティやレジスタ転送記述に於ける定数に１１、え
た初期遅延情報や終点の信号名およびタイミング制約デ
ータ（ゲート段数）情報を取り込む（３０２）。レジス
タ転送記述をトランスレートした結果を格納した設計デ
ータベースからネットワークデータを抽出する（３０３
）。ネットワークを構成している機能素子が遅延情報の
ライブラリ内に存在するかどうかを調べ（３０４）　、
存在する場合は該ライブラリよりその遅延情報を取り込
み該機能素子に割り付ける（３０５）。存在しない場合
は展開後の回路の遅延モデルに従い段数を計算して該機
能素子に割り付ける（　３０６　）。

つぎに入力点より終点信号方向に向ってパスをトレース
する。ここで入力点とは人力属性や定数属性を有するフ
ァシリティのことで、終点とはレジメタのデータ入力や
出力属性のファシリティを指す。このときデータバス、
制御パス（レジスタ転送記述ではｉｆ、ｃａｓｅなとて
データ転送を制御でき、このｉｆ、ｃａｓｅの条件信号
を作成するパス）、クロックパス（レジスタのクロック
入力に接続されるパス）のそれぞれについてパスの有す
る最大段数を伝播しながら計算する。またクロックパス
についてはレジスタに人力後はレジスタの出力に接続さ
れているデータバスについて段数を４算する。−度旧算
したパス上の各素子の人力からの段数は膜種データベー
スに格納する（３０７）。すべての終点に対する段数計
算が終了したらつぎの処理を行う。

つぎに終点に割り付けられたタイミング制約情報を用い
て、終点から人力点に向かって抽象機能素子か持ってい
る段数を引去りながら、各抽象機能素子の出力で要求さ
れる最小の遅延段数（最もクリティカルな制約）を計算
して設計データパスに格納する（３０８）。抽象素子間
の信号はレジスタ転送レベルの回路ではファシリティと
じて認識されるのでパス自体の遅延についても考慮され
る。さらにスラック（いま求めた制約の遅延段数とパス
の人力からの段数との差）を計算して設計データベース
に格納する（３０９）。ここてスラックがマイナス値（
最大遅延を考えている）になった箇所はクルティカルパ
ス上に存在する。

その後終点からスラックの値を頼りにタイミング制約を
満足しないパスをトレースする（　３　］−０）さらに
このとき制御信号の値によって機能的に非現実的なパス
をクリティカルパスの候補としている場合があるのてｉ
ｆ、ｃａｓｅの条件が矛盾なく成立するパスを本当のク
リティカルパスとし、膜種データベースにパス情報を格
納する。そしてクリティカルパス」二の各抽象素子の出
力における人力からの段数、制約、スラックなどの情報
を膜種データベースに格納して（３１，１）木手段の処
理を終了する（３１．２）。

またクリティカルパス探索手段では、終点に与えた最大
遅延段数制約に対するクリティカルパスｍａｘ　　（ス
ラックｍａｘ　）と同しように、最小遅延段］　６ 数制約に対するクリティカルパスｍｉｎ　　（スラック
ｍｉｎ　）が同時に探索できる。

以下第４図を用いて第１図のクリティカルパス探索手段
によって発見されたクリティカルパスから論理合成部１
０６で行う被最適化回路（被最適化パス）の抽出と該パ
ス上の抽象機能素子の選択、展開及び最適化処理の手順
について説明する。

ここで説明の関係土木発明の論理合成が用いているルー
ルベースの方式について簡単に説明する。

レジスタ転送記述をＩ・ランスレータで初期回路に変換
したあと、抽象機能素子をより抽象度の低い機能素子ま
たは論理素子に展開する。このとき展開の度合によって
ゲート数は多いがスピードの速い回路やスピードは遅い
がゲート数は少ない回路が構成できるので、展開の制御
はルールベース方式を用いている。すなわち展開の仕方
をルールで選択できる。」二連したように展開の仕方も
ルールで記述できるが展開ルールの選択制御そのものが
ルールで記述でき、このルールをメタルールと呼ぶこと
にする。また抽象機能素子同士を対象にした最適化はア
ルゴリズムを用いた手法では不可能なので、本最適化に
もルールを用いている。

以下の実施例ではクリティカルパス１Ｔｌａｘを最適化
合成する手順について説明する。なお、今後特に断らな
い限りクリティカルパスはクリティカルパスｍａｘの意
味で用い、スラックもスラックｍａＸの意味で使用する
。クリティカルパスを解消するように合成するには、ク
リティカルパス探索手段によって計算されたスラック値
をゼロにするようにすればよいのでスラック値の絶対値
を最適化目標値とする。

処理を開始する（４０１）。クリティカルパスから被最
適化パス及び最適化目標値を求める（４０２）。被最適
化パスの選択については後述する。

つぎに被最適化パスコニの抽象機能素子から被展開候補
抽象機能素子を捜し出しく４０３）（これについても後
で詳しく説明する）、候補が存在する場合は、該抽象機
能素子を展開したとき遅延段数が減少する（最適化目標
値に近づく）かどうかを調べる（４０４）。なお遅延時
間割付手段でレジスタ転送レベルの抽象機能素子には典
型的な遅延段数を割り当てであるので、スピードの速い
抽象回路に展開するルールが存在すれば減少することが
わかる。減少しない場合はつぎの候補の抽象機能素子を
抽出する（４０３）。減少する場合は該抽象素子をより
抽象度の低い抽象素子に展開する（４０５）。そして展
開後の抽象素子に対して遅延情報ライブラリを用いて遅
延段数を割り当てる。

該ライブラリにない場合はｔｌ算して割り当てる（４０
６）。展開後の抽象機能素子のネットワク仝体に対して
段数８１算を行い（４０７）、展開前の抽象機能素子の
遅延段数といま４算した遅延段数を比較して、該被最適
化パスの最適化目標値が達成されたかどうかを調べる（
４０８）。達成されない場合は、つぎの候補の抽象機能
素子がなくなるまで抽出して繰り返す。その後で最適化
［１標値が達成されない場合は、展開後の機能素子同士
または被最適化パスの端点の機能素子同士について最適
化を行う（４０９）。全ての被最適化パスに対して上記
処理が終了したかどうか調べ（４］Ｏ）、終了した場合
は該全体回路に対してクリティカルパス検索を行い展開
最適化合成前のクリティカルパスが解消されているかど
うかを調べる（４］１）。解消されていない場合は一連
の処理でクリティカルパスが解消されずに残るまでステ
ップ４０２以下の処理を繰り返す（４１２）。クリティ
カルパスが解消された場合もしくは残存するのが確定し
た場合は、上記展開後の抽象機能素子以外のネットワー
クの抽象機能素子に対【７ても展開を行い、さらに素子
数最適化を行う（４１’３）このききクリティカルパス
の解消のときに展開した回路については素子数最適化の
処理を行わない。以」二で遅延時間最適化合成の処理を
終ｒする（４１．４）。

つぎに第５図を用いて第４図のステップ４〔〕２の被最
適化パスの抽出手順について説明する。処理を開始する
（　５０１．　）。まずクリデイカルパス探索手段で発
見されたクリティカルパスｌ１ｌａＸのスラック値から
最も危険度の高い（余裕度の小さい）パスを選択する（
５０２）。該パスが他のクリテ１　つ ィカルパスと重複するかどうか調べ（５０３）、この重
複パスがクリティカルパスｍｉｎでないことを確かめる
（５０４）。クリティカルパスｍｉｎと重複していない
場合、この重複クリティカルパスのスラックのうち危険
度の最も小さい（余裕度の最も大きい）値を選ぶ（５０
５）。そして該重複したザブパスを被最適パスとし、い
ま求めた危険度の最も小さい（余裕度の最も大きい）ス
ラック値の絶対値を最適化目標値とする（　５０６　）
。また非−ｒｆｔ　ｌｊＪザブパスの最適化１」標値は
、各クリティカルパスが有するスラック値に重複ザブパ
スの最適化１」標値を加えた値の絶対値になる（５０７
）。

たたしこの値は重複ザブパスの最適化が成功したときに
用いる。すなわち最適化に失敗した場合は該重複クリテ
ィカルパスの未達最適化目標値分をそれぞれ被最適化ザ
ブパスの最適化目標値に対して加算し、最適化目標値を
更新する。ステップ５０３で調べたクリティカルパスが
他のものとｍｌしない場合は、取り出したクリティカル
パス全体を被最適化パスとし、またスラック値より最適
化目標値を求める（５０８）。すべてのクリティカルパ
スを被最適化パスに分けその最適化１１標値が求まった
ら（５０９）本処理を中＋１．Ｌ、（５１（］）、論理
合成へデータをインターフェースする。すなわち処理４
０２へ進む。

つぎに第４図のステップ４０３の被最適化パス」二の抽
象機能素子の選択手順について説明する。

まず、（１）外部出力に最も近い抽象機能素子を捜し出
す。これは該抽象素子の変換によって発生する他の回路
への影響を最小限にするためである。

（２）最も小さいファンアウトを有する抽象機能素子を
捜し出す。これは、いまファンアウトか多い抽象素子を
同一機能のより小さい遅延段数をもつ抽象素子に変換し
たとき、該変換後の抽象素子をノードとして持つパスが
最小段数違反パスとなる可能性があるからである。

（３）最も小さいファンインを有する抽象機能素子を捜
し出す。これは、いまファンインが多い抽象素子を同一
機能のより小さい遅延段数をもつ抽象素子に変換したと
き、該変換後の抽象素子をノードとして持つパスが最小
段数違反パスとなる１−ｉＪ能性があるからである。

前記（１）〜（３）の優先度は（２）と（３）を満たず
ものでかつ（１）を満足するものが最優先で、（２）と
（３）に関しては（２）の値のより小さい抽象機能素子
を選択する。この優先度についてはルールベース方式を
用いているので自由に変更できる。

ここで第６図を用いて第１図の論理合成部１０６におけ
る抽象機能素子の展開の実施例について説明する。

第６図（ａ）に示ず］Ｏビット２人力加算器６００の展
開の１順について説明する。第６図（ｂ）は、２ビット
加算器を５つ（６０１〜６０５）用いてリップルキャリ
ー１０ビット２人力加算器を構成した図である。第６図
（Ｃ）は２ビット加算器１つ（６（、）　６　）と４ビ
ツト加算器２つ（６０７。

６０８）を用いて］０ビット２人力加算器を構成した図
である。２ビット加算器のケート数は２　ｒ）でゲート
段数は３段である。一方４ビット加算器のゲート数は４
５で段数は５段である。そこで第６図（ｂ）の構造にす
るとゲート数は１００でケト段数は１５段になる。一方
、第６図（Ｃ）の構造にするとゲート数は１１０となり
ゲート段数は１２段となる。

いま、クリティカルパス上の１０ビット加算器を高速回
路に展開する要求が出されているときは、前記メタルー
ルを用いて第６図（Ｃ）の回路を選択しこれに展開する
。また反対に１０ビット加算器がクリティカルパス上に
ない場合は、メタルールを用いて第６図（ｂ）の回路を
選択してこれに展開する。

展開後の抽象機能素子の最適化については、いま第６図
（ｂ）の様な回路がクリティカルパス」二に存在する場
合、２ビツト加算器６０１と６０２の２つを４ピツ１〜
加算器１つに置き換えることによって段数が６段から５
段に減少し１段数分スピドが速くなる。

つぎに第７図を用いて抽象機能素子から論理素子への変
換について説明する。

いま８ピツ］・の１加算器（インクリメンタ）を例に取
って説明する。レジスタ転送レベル言語で記述された８
ピットの］加算器は、Ｉ　Ｎ　Ｃ７０１という抽象素子
にトランスレートされる。そこで論理構成の処理が開始
されるとＩ　Ｎ　Ｃ７０］という素子はＥＸＯＲ（υ１
他的論理和）７０２、ＡＮＤ７０３、Ｎ０Ｔ７０４の論
理素子に展開される。

いま第７図（ｂ）の論理素子からなる回路と、第７図（
ｃ）の回路と２つが考えられ、第７図（ｂ）の回路では
各ピッ）・のキャリーの計算を独自の回路で行っている
のに対して、第７図（Ｃ）の回路は４ビットの１加算器
を２つ用いた構成であり、したがってＦ位４ビットから
のキャリーの４算結果を用いるようになっている。２つ
の展開回路の違いはそれぞれ他の物と比較して、第７図
（ｂ）では信号伝播遅延が小さいのに対して（ゲート数
４８、ゲート段数４段）、第７図（ｃ）　ではゲト数が
小さい（ゲート数４０、ゲート段数５段）という特徴が
ある。この展開の処理をルールベースて行う場合、まず
２つの基本展開ルールが用意されており、前記クリティ
カルパス探索手段で発見されたクリティカルパス上にＩ
ＮＣと言う素子−が使用されており、遅延最小の条件で
展開の要求が出された場合は、メタルールでそれを判断
して第７図（ｂ）の回路に展開し、さもなければ第７図
（ｃ）の回路に展開する。

さらに簡単化ルールとして４人力ＡＮＤと２人力ＡＮＤ
がシリアルに接続されている場合、′３人力ＡＮＤ２つ
に変換するというものがある場合、」二紀元７図（ｂ）
の回路は第７図（Ｃ）の回路になることが考えられるか
、ゲート数最小化のために設けられたＡＮＤのシリアル
結合は簡単化しないようにフラグをつけておく。そうす
ることによって、遅延時間最小化制約を満たす構造回路
を生成できる。

上記実施例は、遅延時間最小化のルールによって生成さ
れた回路が、上記簡単化ルールのようなゲーＩ・数最小
化のルールによって回路が変更されないようにした例で
あるが、反対にゲート数最小化のルールによって回路を
小さくする場合はフラグをｏｆｆにすればよい。

以下筒中なモチーフを用いてクリティカルパスの探索と
合成の処理を説明する。

第８図は合成前の機能ブロック図である。８０１〜８０
５は入力端子である。ここで入力端子８０１〜８０３は
４ビット幅を有している。８０６゜８０７はクロック入
力端子である。また８０８は４ビット幅の出力端子であ
る。８０９は４ビツト２人力加等器で、８１０は４ピッ
ｌ−２人力減算器である。８］］は比較器で、８１２は
４ビットの１加算器（ＩＮＣ）、８１３は４ビツトの１
減算器（Ｄ　Ｅ　Ｃ）である。８］４と８１５はそれぞ
れ１ビット、４ビットのレジスタで、８１６と８１７は
２〜１のマルチプレクサである。さらに８１８はＡＮＤ
て、８１９，８２０はインバータである。また８２１は
内部信号である。

まずこの回路の機能素子及び結線情報をスケマチック人
力または機能膜種記述言語で書く。この情報をデータ変
換手段を用いて回路設計データに変換する。いまこの回
路全体を論理合成の対象として遅延時間の制約を与える
。ここでは、レジススタＲ２（８１５）を終点とするパ
スに対して最大遅延制約段数１０を与える。また出力端
子Ｇ（８０８）に最大遅延制約段数１９を設定する。

この設定の仕方はスケマチック人力ではレジスタシンボ
ルＲ２のデータ入力端子に対して最大遅延時間制約のテ
キスト人力テーブルを開いて行うことができる。出力端
子Ｇについても同様である。

スケマチックの情報がなくてもこれらの制約はコマンド
で入力できる。

つぎに各抽象機能素ｒ・に対する遅延情報の与え方につ
いて説明する。膜種者は機能ブロックの遅延時間を自由
に選択または設定できることが重要だが、機能ブロック
をスケマチック入力するたびに、もしくは機能素子を記
述するたびに遅延時間を設定していたのでは膜種効率が
大変悪いので、自動割当の手段を用いる。抽象機能素子
の遅延時間は人力数及びそのビット数に依存し、さらに
同一機能に対して構造回路は複数考えられるため、ここ
てはゲート数も遅延時間も良好な標準的な論理回路を想
定して遅延時間を１７える。いま第８図の点線の円で囲
まれた数字は各機能ブロックの最大遅延段数である。イ
ンバータは他の論理ゲートに比べて遅延時間が小さいの
でここではゲート段数をＯとしている。

これを整理して示すと以下の表１のようになる。

表　　　　１ 機能ブロックタイプ　　遅延段数 ＡＤＤ　　　　　　　６ ＳＵＢ　　　　　　　７ ＣＯＭＰ　　　　　　５ ＭＵＸ　　　　　　　　　　　　　　ＩＴＮＣ３ ＤＥＣ３ ＲＥＧ　　　　　　　　　　　　　２ ＡＮＤ　　　　　　　　　　　　　　１１ＮＶ　　　　
　　　　　　　　　Ｏ これらは設ス１データヘースから各抽象機能素子のタイ
プと人力数と人力数のビット幅を取り出して、この情報
をもとに計算して割り当てたものであり、これらについ
ては合成途中で再度生成される可能性があるためワーク
記憶領域に保存しておく。

そこで上で設定した遅延時間制約に基づいたクリティカ
ルパス探索の処理について説明する。

入力端子からの各抽象機能素子の出力における段数を求
める。入力点Ａ　（８０２）　、Ｂ　（８０３）Ｃ（８
０４）　、Ｄ　（８０５）は０段で、クロック人力ＣＫ
ｉ（８０６）にはＡ−Ｄ入力に対して遅延時間として３
段遅延を持たせ、ＣＲ２（８０７）は１６段とする。

いま入力端子Ａ　（８０２）　、Ｂ　（８０３）からの
データバスの段数について説明する。点線の四角形の上
から１段目の値が入力からの段数を示す。

減算器（８１０）の出力は７段となり加算器（８０９）
の出力は６段となる。またＭＵＸ（８１６）の出力は偽
人力（８１０）からの段数が大きいのでそれをとり８段
となる。一方ＭＵＸ（８１，６）の制御入力はＣＫｉ、
（８０６）か３段でレジスタ２つ Ｒ］、（８１，４）の段数２を加えて５段となる。また
ＭＵＸ（８１，６）の出力は最大６段となる。従ってこ
のパスはデータバスからの８段をとる。比較器（８１，
１）の出力はＦ（８２１）からのパスの８段と比較器本
体が有している５段を加えた１３段となる。さらにＭＵ
Ｘ　（８１７）の出力はブタパスＦ（８２１）や１加算
器（８１，２）の出力段数の３段よりも大きい１４段の
値をとる。最終的に、レジスタＲ２（８１５）のデータ
人力へのパスの最大段数は１４段となる。

つぎにＲ２（８１５）を終点とするパスに対して制約段
数（点数の四角形の２段目の値）を計算する。Ｒ２には
１０段の最大遅延の制約が割り付けられている。Ｒ２へ
人力するパスはＭＵＸ　（８１７）から来ている。ＭＵ
Ｘの右から人力する制御信号８２２は偽のときの条件を
表しており、８２３は真のときの条件を表している。Ｍ
ＵＸ　（８１７）の左から人力する信号はデータ信号で
右から人力する制御信号に対応するものである。いまＭ
ＵＸのデータ人力Ｆ（８２１）に於ける制約を求めると
９段になる。ここでＦはファンアウトが２以上であるの
てＦの出力のもとの遅延段数決めることができない。そ
こでＭＵＸ（８１，７）の真入力のデータバスの制約を
調べると、偽の場合と同様に９段となり、さらにＩＮＣ
（８］２）は３段なのでＩＮＣの入力は６段となる。こ
のパスについては、いま終点を指定したレジスタの出力
に達したのでここで終了する。そこでＭＵＸ（８１７）
の制御信号のパスの制約段数を求める。ＭＵＸの制御入
力端子はそれぞれ９段である。ＭＵＸの偽のパスのイン
バータによる遅延は考慮せず比較器（８１，１）の出力
端子に於ける段数は９段となる。そして比較器の入力端
子に於ける段数を４算する。比較器の遅延段数は５段で
あるので入力Ｆ（８２１）の出力は先はど４算した９段
よりも小さい、いま求めた４段を制約とする。以下同様
に加算器（８０９）、減算器（８１，０）の出力はそれ
ぞれ３段となり減算器（８１０）の遅延段数が７段であ
るのでＡ　（８０２）　、Ｂ　（８０３）はそれぞれ−
４段となる。一方ＭＵＸ　（８１６）の制御入力に対し
てレジスタＲ１（８１４）の出力は３段となり、レジス
タＲ１，（８１，４）のクロ・ツク人力からデータ出力
までの遅延段数を差し引いてクロック人力ＣＫ１．（８
０６）は１段となる。

ここでスラッジ（制約段数−始点からの段数）を求める
。点線の３段組の長方形の３段目の値がスラック値であ
る。そしてＲ２（８１５）からこのスラッジの値の内マ
イナス値をトレースすればこれがクリティカルパスとな
る。このモチーフでは−４のパスが最も危険なパスで、
つぎが−３のパスである。

同様に出力Ｇ　（８０８）については、ます人力ＣＫ２
（８０７）からの段数は入力Ａ　（８０２）、Ｂ　（８
０３）　、Ｅ　（８０１）に対して１６段の遅延を持っ
ているので、レジスタＲ２（８１，５）のクロック人力
では１６段となり、Ｒ２のデータ出力では１８段となる
。さらにＤＥＣ（８１３）の出力端子て２１段となり結
局出力Ｇ（８０８）で２１段になる。つぎに出力Ｇには
制約１９段がｌｊえられているので、ＤＥＣ（８１，３
）の人力はＤＥＣ自体が有している３段の遅延段数を差
し引き１６段となる。またレジスタＲ２のクロック入力
からデータ出力までの遅延段数を差し引いてクロック人
力ＣＫ２　（８０７）は１４段となる。スラッジは−２
となりクリティカルパスはＣＫ　２−　Ｒ２−ＤＥＣ−
Ｇのパスとなる。

つぎに最適化パスの選択方法について説明する。

クリティカルパスが有しているスラツク値から最も危険
度の高いパスを選ぶ。いまＲ２のデータ人力に与えた制
約に対して危険度の高いパスから示す。ｃｐｌ、１とｃ
ｐｌ、、２はスラッジが−４のクルティカルパスで、ｃ
ｐ２．］とｃｐ２．２はスラッジが−３のクリティカル
パスで、ｃｐ３゜］は−２のクリティカルパスである。

個々のクリティカルパスの最適化目標値はスラツク値の
絶対値としｔａｒｇｅｔ１〜３に示す。以」二を総合す
ると次の第２表のようになる。

（以下余白） ｃｐｌ、１：Ａ 第２表 ＳＵＢ−ＭＵＸ ＣＯＭＰ −ＭＵＸ−Ｒ２ ＣＩ）１．　２：Ｂ ＳＵＢ ＭＵＸ ＣＯＭＰ ＭＵＸ　　−Ｒ２ ５ｌａｃｋｌ： ｔａｒｇｅｔｌ：４ ｃｐ２．１　　・　Ａ ＭＵＸ−Ｒ２ ｃｐ２．　２：Ｂ　−ＡＤＤ ＭＵＸ−Ｒ２ ｓ　　１　　ａ　　Ｃｋ　　２　　：　　−３ｔａｒｇ
ｅｔ２：３ Ａ　　Ｄ　　Ｄ ＭＵＸ ＭＵＸ ＣＯＭＰ ＣＯＭＰ ｃｐ３．１：ＣＫＩ ＭＵＸ ＯＭ Ｐ　−ＭＵＸ−Ｒ２ ｓｌａｃｋ３ニー２ ｔａｒｇｅｔ３：２ いま、ｃｐｌ、、ｉに着目するとこれは他の全てのクリ
ティカルパスに重複する部分を有しており、これを重複
パスｏＶｐ１とする。最適化１１標値は全クリデイカル
パスのうちもっとも危険度の小さいスラックの絶対値を
取るので２（ｏｔｌ）となる。またｃｐｌ−、ｉはｃｐ
ｌ、２とも重複しておりこれをｏｖｐ２と示す。最適化
Ｌ１標値はｔａｒｇｅｔｌ−ｏｔｌで２（ｏｔ２）とな
る。

ｏｖｐ　１　：ＭＵＸ−Ｆ−ＣＯＭＰ−ＭＵＸ−Ｒ２ｏ
ｔｌ：２ ｏ　ｖ　ｐ　２　：　ＳＵＢ−ＭＵＸ ｏｔ２二２ つぎにｃｐ２，１に着目すると重複パスｏｖｐ１につい
て処理済みなので、Ｃｒ２，２との重複パスｏｖｐ３を
被最適化パスとし、最適化］−１標値ｏｖ３は１　　（
ｔａｒｇｅｔ２−ｏｔｌ）となる。

ｃ　ｐ　３゜１についてはｏｐｐｌか被最適化ハスの候
補になるが最適化ｌ」標値ｏｐｌは０（ｔａｒｇｅｔ３
−ｏｔｌ）となるため候補からはずず。

ｏ　ｖ　ｐ　３　：　ＡＤＤ−ＭＵＸ ｏｖ３：１ ｏｐｐ　１　：　ＣＫＩ−Ｒ１−ＭＵＸａｐｌ：０ 但し０ｒ）ｐ］はｏｖｐｌで最適化が実現できた場合に
のみ最適化目標値はゼロとなる。

つぎに被最適化パスｏｖｐｌについて適用する最適化工
法について説明する。

いま説明する手法は被最適化パス上の複数の機能素子に
対【７て応分の最適化目標値を分担するものである。一
方被最適化バス」二のある機能素子に対して最大限の最
適化目標値を担わせ、最小回数の展開でｌニー１標値を
実現する手法でも実現できる。

ますはＬ７めに、よりファンアラＩ・の小さい抽象機能
素子を選択するがその対象となるものはＭＵＸ８１７で
ある。そこてＭＵＸの展開方法について高速化ルールが
存在するかどうか調べ、いま高速化回路に展開するルー
ルが存在しないので（本実施例では存ｎニジないとした
）つぎの候補を捜す。

またファンアラｉ・の小さい抽象機能素子を選択すると
ＣＯＭＰ（８１，１）が候補に挙がる。そこでＣＯＭ　
Ｐを展開したあとて高速化されるかどうか：Ｊ！ａべる
と是であるので実際に展開を行う。展開後の回路を第９
図に示す。そして展開後の個々の機能素子に対して遅延
段数を与える。展開後の部分回路の段数計算を行うと４
段になるので１段分たけ最適化１」標値が達成された。

ただしＥＸＯＲ（９０１）は２段、４人力Ｎ０Ｒ（９０
２）は２段としている。ところが被最適化パスｏｖｐｌ
は最適化ｉ〒１標値が２段であるので、まだ」二記展開
のみでは達成されないためつぎの候補を捜しにいくが、
ＭＵＸ（８１，６）も」二記理由により最適化展開が不
可能である。そのためＣＯＭＰの展開後の回路について
機能素子間で遅延段数の最適化を行うが、第９図のよう
に最適化の余地が残っていないのでっぎの被最適化パス
の展開を行う。

被最適化パス０Ｖｐ２について最適化［１標値を計算す
る。重複したクリティカルパスｏｖｐｌの最適化１」標
値が実現できなかったので、本最適化パスはその分最適
化目標値が大きくなる。本来の最適化ｌ」標値は２段で
あるが、いまｏｖｐｌの非実現最適化［１標値１段を加
えて３段になる。そこで最適化展開候補を捜すとＳＵＢ
　（８１０）か選択され、さらに高速化回路に展開する
ルールがあるかどうかを調べると存在するのて、ＳＵＢ
を高速化回路に展開する。ここでは５段の遅延段数を持
つ回路に展開できるので（第１０図を参照、１００１は
４ビット全加算器で遅延段数は５段）、最適化［“１標
値３に対して２段分を満足させる。０ｖｐ２には他に最
適化展開可能な機能素子がないので、展開後の回路につ
いて機能素子間の最適化を行うが、最適化の余地が残っ
ていないのでクリティカルパスｃｐ１．１とｃｐｓ、２
は最適化１１標値４を達成てきず３段分しか稼げなかっ
たことになる。同様にｏ　ｖ　ｐ　３の最適化目標値は
２段になりパス」−のＡＤＤは展開後最小５段にしかな
らないのでクリティカルパスｃｐ２．１、ｃｐ２゜２の
最適化！−１標値の３段は実現できず１段分の危険度は
残る。さらに重複クリティカルパスの最適化目標値が実
現できなかったことから、パスｏｐｐ１は最適化目標値
１段を持った被最適化パスになるか、ｏｐｐｌ上にはＭ
ＵＸとかＲＥＧ等最等化適化候補いためなにも行われな
い。従ってクリティカルパスｃｐ３．１について１段分
の危険度が残ってしまう。また各被最適化パスの端点同
士の最適化が可能かとうか試みるが本実施例では被最適
化パスがＭＵＸ（８１６）で分離されているため不可能
である。本実施例によると最長遅延段数が１４段から１
１段に削減された。

本実施例は展開後の回路の遅延段数を既知として説明し
たが、未知の場合は展開後の回路の段数計算を行う必要
がある。さらに展開後の回路同士で遅延段数の最適化が
行われた場合は再度クリティカルパス探索手段で展開前
のクリティカルパスが回避されたかどうか調べ、クリテ
ィカルパス」二の機能素子がすべて展開されるまで繰り
返す。

［発明の効果］ 以」二説明したように、本発明の装置によれば少ないメ
モリ容量で抽象回路のレベルでタイミング検証が行え、
合成前にタイミング仕様が満たされるか否かの判定が可
能になる。また、抽象回路に割り当てられた遅延時間を
利用して、回路の展開及び最適化時にスピードの速い回
路を生成するの３　つ で、論理式の筒中化やハードウェアのインプリメンテー
ションによる遅延時間の最適化だけを用いた場合よりも
遅延時間の制約を満足する回路が実現できるという効果
がある。

【図面の簡単な説明】

第１図は本発明の一実施例にかかる論理回路の合成装置
の構成を説明するブロック図、第２図は本発明の一実施
例における論理合成の処理フローを説明する図、 第３図は本発明の一実施例におけるクリティカルパス探
索手段の処理を説明する図、 第４図は本発明の一実施例における被最適化回路（被最
適化パス）の油田と該パス上の抽象機能素ｒの選択、展
開及び最適化処理の手順について説明する図、 第５図は本発明の一実施例におけるクリティカルパスか
ら被最適化パスの抽出１法について説明する図、 第６図は本発明の一実施例における抽象機能素子の展開
について説明する図、 第７図は本発明の一実施例における抽象機能素子から論
理素子への変換について説明する図、第８図は本発明の
一実施例におけるクリティカルパスの探索と合成の処理
を説明するのに使用する簡単なモチーフの機能ブロック
図、 第９図は本発明の一実施例における比較器の論理素子へ
の変換について説明する図、および第１０図は本発明の
一実施例における減算器の展開について説明する図であ
る。 １０１・　レジスタ転送仕様の人力部 ］０４・タイミング制約の入力部 １０５−タイミング制約設定及び違反検１１１部１０６
　論理合成部 １０８　論理回路の出力部

Claims (2)

【特許請求の範囲】
1. （１）論理回路を自動生成するための論理回路の合成装
   置において、 合成の開始前、あるいはその途中で生成された抽象回路
   を使用してタイミング解析を行なうために、前記抽象回
   路を構成している素子に任意の遅延時間を与える手段と
   、 与えられた遅延時間を用いてタイミング解析を行い、タ
   イミング制約条件が満たされるかどうかを検出する手段
   と、 前記検出されたタイミング解析結果を使用してタイミン
   グ制約条件が満たされるように前記抽象回路を論理回路
   に変換あるいは合成する手段と、前記タイミング制約に
   違反する回路の遅延時間を最適化するために回路を変換
   あるいは合成する手段と、 を具備することを特徴とする論理回路の合成装置。
2. （２）前記遅延時間最適化のための回路の変換あるいは
   合成手段は、前記タイミング解析手段で検出された制約
   違反の回路を解析して前記回路を最適化対象回路に分割
   するとともに分割された回路に最適化目標値を設定し、
   前記最適化目標値にしたがって回路を変換あるいは合成
   する手段を有することを特徴とする請求項１記載の論理
   回路の合成装置。