JPH04250570A - 高位レベル合成におけるデータ管理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、高位レベル合成におけ
るデータ管理方式であって、抽象度の高いレベルでレイ
アウトに伴うパス遅延を管理してパス遅延違反を無くし
て合成を可能にする高位レベル合成におけるデータ管理
方式に関するものである。ＡＳＩＣ時代に入り、論理設
計支援の必要性がますます増加している。組み合わせ回
路の自動論理合成技術が、実用化のレベルに達してきた
ことにより、より高い、アリゴリズムレベルからの設計
支援、自動合成に対する要求が高まっている。

【０００２】

【従来の技術】従来の高位レベル合成の流れを図４の（
ａ）に示す。ここで、システムへの入力となる、動作記
述は、ＶＨＤＬなどの図４の（ｂ）の左側に示すような
ハードウェア記述言語で与える。トランスレータは、こ
の図４の（ｂ）の左側に示すような動作記述言語を、言
語の構文に依存しない図４の（ｂ）の右側に模式的に示
すような内部表現に変換する。この内部表現は、通常、
データの依存関係やオペレーション間の順序関係を表現
した、コントロール／データフローグラフが用いられる
。例えば図４の（ｂ）の左側に示すアルゴリズムは右側
に示すようなグラフで表現できる。

【０００３】高位レベル合成は、動作記述中に現れる変
数や演算子に、レジスタ、演算モジュールなどのファシ
リティをどのように割り当てるか、というデータパスア
ロケーション問題と、各オペレーションの実行順序をど
のようにするかというスケジューリングの問題から構成
されている。これら作業は相互に依存しあっているため
、双方を同時に考慮する、あるいは双方を繰り返し実行
しながら、データパスおよびデータコントロールを決定
していく。スケジューリングとアロケーションが終わっ
た段階で、データパス、およびそれに対する制御回路の
仕様が生成され、これ以降は更にレイアウトツールによ
って最終的な回路が生成されることとなる。

【０００４】

【発明が解決しようとする課題】従来のスケジューリン
グ／アロケーションは、できるだけ回路規模を小さく、
動作に必要なステップ数を少なくするように、ファシリ
ティの割り当てを行う。この際、ライブラリに格納され
ている各ファシリティの情報を使って回路規模や遅延時
間を評価することは行っていた。しかし、配置などのレ
イアウトを反映したパスの遅延時間の考慮を行っていな
かった。このため、実際のレイアウトを行った段階で、
回路の遅延が大きくなり１つのステージに許される遅延
時間を越えてしまう事態が発生し、どこかを修正しなけ
ればならなくなる。この修正のためのフィードバックは
できるだけ短かく、少ない方がよいが、長いフィードバ
ックループを戻って設計段階のスケジューリングなどを
修正していたため、効率的に設計し難いという問題があ
った。

【０００５】本発明は、コントロール／データフローグ
ラフをもとに高位レベルのスケジューリング、アロケー
ション、フロアプランした結果を評価し、レイアウトに
よるパス遅延時間をコントロール／データフローグラフ
のパスにフィードバックして高いレベルでレイアウト情
報を考慮に入れた合成を行い、効率的な設計を可能にす
ることを目的としている。

【０００６】

【課題を解決するための手段】図１は、本発明の原理説
明図を示す。図１において、コントロール／データフロ
ーグラフ１は、動作記述を言語の構文などに依存しない
内部表現で表わしたものである。スケジューリング部２
は、オペレーションの実行順序を決定（スケジューリン
グ）するものである。

【０００７】アロケーション部３は、コンロトール／デ
ータフローグラフ１によって表わされた変数や演算子に
レジスタなどのファシリティの割り当てを行うものであ
る。フロアプラン部４は、割り当てられたファシリティ
を配置するものである。レイアウト情報付加は、コント
ロール／データフローグラフ１にレイアウトに伴うパス
遅延情報１−１を付加するものである。

【０００８】データ管理部５は、スケジューリング部２
、アロケーション部３およびフロアプラン部４によって
スケジューリング、アロケーション、フロアプランされ
た結果について、遅延時間などを評価するものである。

【０００９】

【作用】本発明は、図１に示すように、論理設計の動作
記述について言語の構文に依存しない表現であるコント
ロール／データフローグラフ１のパスにパス遅延情報１
−１を付加し、このコントロール／データフローグラフ
１およびパス遅延情報１−１をもとにスケジューリング
部２、アロケーション部３、フロアプラン部４がスケジ
ューリング、ファシリティの割り当て、フロアプランを
行い、データ管理部５がこれらの結果の評価を行ってレ
イアウトに伴うパス遅延情報をコントロール／データフ
ローグラフ１のパス遅延情報１−１にフィードバックす
ることを繰り返し、レイアウトに依存するパス遅延の違
反を無くした合成を行うようにしている。

【００１０】従って、スケジューリング、アロケーショ
ン、フロアプラン段階で得られたレイアウト時のパス遅
延情報をコントロール／データフローグラフのパスに付
加してフィードバックし、遅延時間の評価を繰り返すこ
とにより、高いレベルでレイアウト情報を考慮に入れて
遅延時間違反の無い合成を行い、効率的な設計を行うこ
とが可能となる。

【００１１】

【実施例】次に、図１ないし図３を用いて本発明の実施
例の構成および動作を順次詳細に説明する。図１（イ）
において、コントロール／データフローグラフ１は、既
述した図４の（ｂ）の左側に記載した動作記述言語の構
文などに依存しない、右側に記述した内部表現で表わし
たグラフである。

【００１２】パス遅延情報１−１は、コントロール／デ
ータフローグラフ１のパスに付加した本実施例で設けた
ものであって、後述するレイアウト情報付加のときに求
めたパス遅延時間について、フィードバックして更新す
るものである。スケジューリング／アロケーションは、
図１の（ロ）のスケジューリング部２およびアロケーシ
ョン部３が行うものであって、コントロール／データフ
ローグラフ１を入力として、各オペレーションの実行順
序をスケジューリングしたり、このスケジューリングを
もとに変数や演算子にレジスタや演算モジュールなどの
ファシリティを割り当てたり、接続関係を決定したり、
レジスタなどへの制御信号を生成したりなどするもので
ある（図２の（ａ）、（ｂ）参照）。これら作業は、相
互に依存しているので、双方を同時に考慮して処理を行
う。具体的に説明すると、これら作業は、各オペレーシ
ョンが実現できるかの対応表、各ファシリティの実行遅
延時間および回路規模のデータなどをもとにして行う。

【００１３】フロアプランは、図１の（ロ）のフロアプ
ラン部４が行うものであって、スケジューリング／アロ
ケーションによってスケジューリングおよびファシリテ
ィの割り当てなどを行った後、これら作業によって生成
されたデータパスをもとに、フロアプランの作成（レジ
スタなどをどこに置くかのフロアプラン）を行うもので
ある（図３の（ｃ）参照）。

【００１４】レイアウト情報付加は、フロアプランした
後、フロアプランされた各ブロック間の距離をもとに当
該ブロック間のパス遅延時間を算出し、これをコントロ
ール／データフローグラフ１の該当するパスにパス遅延
情報１−１としてフィードバックする態様で設定する。 評価は、図１の（ロ）のデータ管理部５が行うものであ
って、レイアウト情報付加によってコントロール／デー
タフローグラフ１のパスのパス遅延情報１−１をもとに
、スケジューリング／アロケーションされた結果を評価
（例えばコントロールステップ間の遅延時間を算出して
予め指定したクロック時間内に収まるか評価）するもの
である。評価の結果、遅延時間が長くて１クロック内に
収まらないなどの違反が検出されると、そのパスに関連
するオペレーションに対するスケジューリングやアロケ
ーションを修正する。これらループを、条件を満たすま
で自動的あるいはオペレータの指示に従って繰り返す（
図３を用いて後述する）。

【００１５】以上のように、動作記述を言語の構文など
に依存しないコントロール／データフローグラフ１に変
換したものを入力とし、スケジューリング、アロケーシ
ョン、フロアプランを行い、フロアプランの結果から求
めた各ブロック間のパス遅延時間をコントロール／デー
タフローグラフ１の該当するパスのパス遅延時間１−１
に設定し、これらをもとに遅延時間の評価（例えば１ク
ロック内に収まるか否かの評価）を行い、違反が検出さ
れたときにそのパスに関連するスケジューリング、アロ
ケーションを修正することを自動的あるいはオペレータ
からの指示をもとに繰り返し行うことにより、高位レベ
ルでレイアウトによるパス遅延時間の違反の無い設計を
早い段階で行うことが可能となる。

【００１６】図１の（ロ）は、本発明の構成図を示す。 ここで、スケジューリング部２、アロケーション部３、
フロアプラン部４、データ管理部５は、図１の（イ）の
スケジューリング／アロケーション、フロアプラン、評
価で説明した処理を行うプログラムである。設計データ
６は、（ａ）、（ｂ）、（ｃ）、（ｄ）に示すような各
種データである。

【００１７】（ａ）　　コントロール／データフローグ
ラフ１であって、オペレーション間の順序関係を表わし
ている。 （ｂ）　　（ａ）のコントロール／データフローグラフ
１をスケジューリングした結果であって、ここでは例え
ばオペレーション”＋”がステップｉにスケジューリン
グされている。

【００１８】（ｃ）　　演算モジュール、レジスタなど
のファシリティを割り当てた結果のデータパス、その制
御回路である。 （ｄ）　　（ｃ）のデータパスにもとづいて、作成した
フロアプランである。以上説明した図１の（ロ）の各デ
ータ間の対応関係を具体的に示すと図２に示すようにな
る。

【００１９】図２は、本発明のデータ間の対応関係を示
す。図２の（ａ）は、オペレーションとファシリティの
対応関係を示す。コントロール／データフロープラン１
の上段、各オペレーションにファシリティを割付た中段
、ファシリティをフロアプランした下段とについて、そ
れぞれ矢印を用いて対応関係を示す。例えば上段のオペ
レーション”＋”は中段の”ＡＬＵ（加算器）”、更に
下段の”ＡＬＵ”に対応づけている。

【００２０】図２の（ｂ）は、オペレーションの依存関
係を表わすエッジとフロアプラン上のパスの対応関係を
示す。上段に示すように、コントロール／データフロー
グラフ１中のオペレーションに付随するエッジがコント
ロールステップを通過する点には、値を保持するための
レジスタｓ１、ｓ２、ｓ３を図示のように導入している
。これらレジスタｓ１、ｓ２、ｓ３にはレジスタ転送を
制御する信号が入る。従って、レジスタ転送に関するパ
スには、制御回路からレジスタへのパスも含まれる。 下段は、上段のコントロール／データフローグラフ１に
ファシリティを割り当て、これら割り当てたファシリテ
ィ間のパスｐａｔｈについてパス遅延時間を求め、コン
トロール／データフローグラフ１の該当するパスにこの
パス遅延時間１−１を設定する。これにより、コントロ
ールステップ内に実行すべきオペレーション列の実行に
要する時間と、更に本実施例で設定したパス遅延時間と
を加算した総遅延時間が１クロックの時間内に収まるか
否かを評価し、収まりきらないときに、スケジューリン
グ、アロケーションを修正し、再度評価して総遅延時間
が１クロックの時間内に収まるように繰り返す。これに
より、従来、コントロールステップに要する時間につい
て、パスの遅延時間を無視してオペレーションのみの遅
延時間で評価していたものを、本実施例では、更にフロ
アプランした後のパス遅延時間を加算した総遅延時間で
評価することとしたことにより、フロアプランの早い段
階でレイアウトによる遅延を考慮した効率的な設計を行
うことが可能となる。また、制御回路からの信号線の遅
延時間も併せてパス遅延時間に組み入れることにより、
これらについても検査を行って遅延時間が１クロック内
に収まるように設計することが可能となる。

【００２１】次に、図３は、本発明の１実施例構成図を
示す。図３の（ａ）は、合成対象の仕様を示す。これは
、下記動作記述の言語について、構文に関係のない内部
表現であるコントロール／データフローグラッフ１で表
わしたものである。 ｔ１＝ａ＋ｂ ｄ＝ｔ１×ｃ また、オペレーション＋、×は加算、乗算をそれぞれ表
わす。

【００２２】図３の（ｂ）は、スケジューリング／アロ
ケーション結果を表わす。ここで、ｐ１はレジスタと＋
（加算器）との間のパス、ｐ２は＋（加算器）と×（乗
算器）との間のパス、ｐ３は×（乗算器）とレジスタと
の間のパスである。図３の（ｃ）は、フロアプラン結果
を表わす。これは、図３の（ｂ）のスケジューリング／
アロケーション結果について、フロアプランした結果を
表わす。ここで、ｐ１、ｐ２、ｐ３は図３の（ｂ）のパ
スｐ１、ｐ２、ｐ３を表わし、レジスタ１、２、３、４
は図３の（ｂ）のレジスタ１、２、３、４を表わし、加
算器は図３の（ｂ）の＋を表わし、乗算器は図３の（ｂ
）の×を表わし、制御回路はレジスタ１、２、３、４な
どへの制御信号を送る回路を表わす。

【００２３】図３の（ｄ）は、スケジューリング／アロ
ケーションの修正した例を表わす。これは、図３の（ｂ
）のコントロールスップ内のパスｐ１、＋（加算器）、
パスｐ２、×（乗算器）、パスｐ３のルートの総遅延時
間が下記に説明するように、１クロック内の時間に収ま
りきらいないので、レジスタ５を設けて２つのコントロ
ールステップに修正したものである。以下詳細に説明す
る。

【００２４】（１）　　クロックサイクル：４５ｎｓオ
ペレーション＋の遅延時間：１０ｎｓであるとする。 （２）　　スケジューリング部２、アロケーション部３
は、 　　　　　　Σ（１ステップ内のオペレーションの遅延
時間）≦クロックサイクル・■として、コントロールス
テップ、ファシリティの割り当てを行う。このとき、 　　　　　　　　（＋の遅延時間）＋（×の遅延時間）
＝１０＋３０＝４０・・・・・■で、クロックサイル４
５ｎｓよりも小さいため、図３の（ｂ）に示すように、
＋と×を１ステップ内で行うようにコントロールステッ
プを割り当て、加算器、乗算器、および必要なレジスタ
１、２、３、４からなるデータパスを生成する。

【００２５】（３）　　（２）で生成したデータパスを
もとに、フロアプランを作成して図３の（ｃ）に示すよ
うに得る。そして、このフロアプラン上で各ファシリテ
ィ間のパスｐ１、ｐ２、ｐ３の遅延時間をそれぞれ求め
る。 （４）　　（３）で求めた各ファシリティ間のパスｐ１
、ｐ２、ｐ３の遅延時間を各パスに付加すると、■は、
下記■のようになる。

【００２６】 　　　　　　Σ（１ステップ内のオペレーションの遅延
時間）＋Σ（パスの遅延時間）　　　　　　≦クロック
サイクル・・・・・・・・・・・・・・・・・・・・・
・・■従って、例えば 　　ｐ１＋ｐ２＋ｐ３のパス遅延時間＝１０ｎｓ・・・
・・・・・・・・・・・■とすると、図３の（ｂ）中の
矢印で示すパスＰの総遅延時間が ４０ｎｓ＋１０＝５０ｎｓ となり、クロックサイクル４５ｎｓという制約を満たさ
なくなる（違反する）。この違反を解消するために、図
３の（ｄ）に示すように、レジスタ５を新たに加算器と
乗算器との間に設るというスケジューリング、アロケー
ションを変更する。これにより制約を満たすように修正
されたこととなる。

【００２７】

【発明の効果】以上説明したように、本発明によれば、
スケジューリング、アロケーション、フロアプラン段階
で得られたレイアウト時のパス遅延時間をコントロール
／データフローグラフのパスに付加してフィードバック
し、遅延時間の評価を繰り返す構成を採用しているため
、高いレベルでレイアウト情報を考慮に入れて遅延時間
違反の無い合成を効率的に行うことができる。これによ
り、従来では論理合成、および実際のレイアウト実施後
に遅延時間の違反が検出され、長いフィードバックルー
プを戻らなければならかったのが、早い高位レベルでの
修正で回避でき、効率的な設計を行うことが可能となる
。

【図面の簡単な説明】

【図１】本発明の原理説明図である。

【図２】本発明のデータ間の対応関係説明図である。

【図３】本発明の１実施例構成図である。

【図４】従来技術の説明図である。

【符号の説明】

１：コントロール／データフローグラフ１−１：パス遅
延時間 ２：スケジューリング部 ３：アロケーション部 ４：フロアプラン部 ５：データ管理部 ６：設計データ

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　論理設計の高位レベル合成におけるデ
   ータ管理方式において、論理設計の動作記述を言語の構
   文に依存しない表現であるコントロール／データフロー
   グラフ（１）のパスにパス遅延情報（１−１）を付加し
   、このコントロール／データフローグラフ（１）および
   付加したこのパス遅延情報（１−１）をもとにスケジュ
   ーリング、アロケーション、フロアプランおよびこれら
   の結果の遅延時間の評価を行うと共にフロアプランした
   結果に伴うパス遅延情報を上記パス遅延情報（１−１）
   としてフィードバックすることを繰り返し、動作記述レ
   ベルでレイアウトに依存するパス遅延の違反を無くした
   合成を行うように構成したことを特徴とする高位レベル
   合成におけるデータ管理方式。