JPH05101141A

JPH05101141A - 高位合成装置

Info

Publication number: JPH05101141A
Application number: JP4071694A
Authority: JP
Inventors: Hiroshi Imai; 浩史今井; Seiichi Nishio; 誠一西尾; Tokuji Masuda; 篤司増田
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1991-08-13
Filing date: 1992-03-27
Publication date: 1993-04-23

Abstract

(57)【要約】（修正有）【目的】合成後の論理回路における演算器及びレジス
タの入力端子の余分な制御回路を省く。【構成】動作機能記述入力部１より入力された動作機
能記述によって表わされる動作をステート分割するステ
ート分割部２と、各ステートで必要とされるレジスタを
求める変数解析部３と、求められたレジスタを記憶する
レジスタ・リスト記憶部４と、レジスタのマージ規則を
持つマージ規則ライブラリ６と、レジスタのマージを実
行するマージ実行部５と、マージ結果を基に論理回路を
合成する合成部７を備える。別に、ビヘイビア記述を書
直さず、メモリ構成を変更することにより、又はサブル
ーチン演算実行時間の重複を調べて、サブルーチンコー
ルに必要なハードウェアブロックを割当てることによ
り、合成を行う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、動作機能記述あるいは
ビヘイビア記述によって動作が表わされた論理回路を合
成する高位合成装置に関する。

【０００２】

【従来の技術】近年、ＬＳＩの大規模化が進み、それに
伴ってＬＳＩ設計の期間短縮のため、論理回路を自動的
に合成する論理合成システムが用いられてきている。論
理合成システムを用いて論理回路を設計する際には、機
能記述言語により設計対象の動作を記述する必要があ
る。

【０００３】従来、機能記述言語はレジスタ転送レベル
の言語であった。レジスタ転送レベルの言語では、設計
対象のレジスタ、演算器などのハードウェア構成及び各
動作周期（以下、クロック・サイクルという）毎のレジ
スタ間のデータの流れと処理を記述する。この言語を用
いて論理回路を設計するには、レジスタ、演算器等のハ
ードウェアに関する専門知識が必要とされる。

【０００４】このため、最近ではハードウェアの専門知
識を必要としない設計対象の動作のみを記述する動作機
能記述（ビヘイビア記述ともいう）から論理回路を合成
する高位合成システムによる高位合成装置の開発が行わ
れてきている。動作機能記述ではハードウェアの構成を
意識せずに設計対象の動作仕様をプログラムと同様にア
ルゴリズミックに記述できる。

【０００５】アルゴリズミックに記述された動作を論理
回路で実行可能にするためには、前記のように記述され
た動作を各クロック・サイクル毎に実行される動作に分
割する処理、すなわちステート分割の処理が必要とな
る。１ステートにおける動作は１クロック・サイクルで
実行され、異なるステート間における演算データの受け
渡しにはレジスタが用いられる。

【０００６】この高位合成システムでは、動作機能記述
で表わされた設計対象の動作のステート分割の処理を行
い、ステート間で演算データの受け渡しがある場合、そ
の演算データに対応した動作機能記述中の演算対象とな
る変数をレジスタに割付ける。

【０００７】従来の高位合成装置では、変数をレジスタ
に割付ける手法として、動作機能記述中の変数が複数の
ステートに渡っているかを示す変数のライフ・タイムを
調べ、ライフ・タイムが重ならない変数同士をエッジで
結び、クリーク分割アルゴリズムを適用する事によりレ
ジスタ割付けを行うグラフ理論を用いた手法がある。あ
るいは、変数をライフ・タイムの昇順にソートし、ソー
トされた順にライフ・タイムが重ならない変数を次々と
同一のレジスタに割付けていくレフト・エッジ・アルゴ
リズムを用いた手法がある。

【０００８】前者の手法としては、例えば、C.J. Tseng
and D.P. Siewiorek,"Automated Synthesis of Data P
aths in Digital Systems,"IEEE Transactions on Comp
uter-Aided Design, vol. CAD-5, pp. 379-395,July 19
86.に挙げられる手法があり、後者の手法としては、例
えば、F.J. Kurdahi and A.C. Parker,"REAL: A Progra
m for Register Allocation,"in Proceeding of the 24
th ACM/IEEE Design Automation Conference,pp. 210-2
15, ACM/IEEE,June 1987.に挙げられる手法がある。

【０００９】これらのような手法を用いて変数が割付け
られたレジスタを基にして、高位合成システムは論理回
路を合成する。その技法としては、例えば、P.G. Pauli
n, J.P. Knight, and E.F. Girczyc,"HAL: A Multi-Par
adigm Approach to Automatic Data Path Synthesis,"i
n Proceeding of the 23rd ACM/IEEE design Automatio
n Conference,pp. 263-270, ACM/IEEE, July 1986.に挙
げられる技法がある。

【００１０】しかしながら、前述した手法では、各変数
の属する演算を考慮せずにその変数をレジスタに割付け
るため、演算器及びレジスタの入力端子に余分なマルチ
プレクサが必要になる等、冗長な論理回路が合成され
る。

【００１１】例えば、図１９のようなステート分割後の
データフローから論理回路を合成する場合を考える。図
１９は、動作機能記述によって表わされた動作をステー
ト分割した後のデータの流れを表しており、この例では
ステート１〜３に分割されている。このデータフローか
らレフト・エッジ・アルゴリズムを用いてレジスタ割付
けを行うと図２０のようになる。

【００１２】この図から、合成される論理回路には４つ
のレジスタが必要であり、例えばステート１のレジスタ
Ｘ１とステート３のレジスタＺ１が共用されていること
が分かる。このレジスタ割付けを基にして合成された論
理回路のブロック図を図２１に示す。図２１の論理回路
では、レジスタ１１や演算機１２の入力にマルチプレク
サ１３が多数必要とされており、複雑な回路構成となっ
ている。

【００１３】一方、従来の高位合成装置においては、ビ
ヘイビア記述中の各配列変数に対し、１対１に対応した
メモリを割当てて合成していた。例えば、図８のビヘイ
ビア記述中の各配列変数ａａ［１２８］，ｂｂ［１２
８］に対し、共にデータサイズ１２８のメモリａａとメ
モリｂｂを割当てていた。

【００１４】これらの配列変数ａａ，ｂｂに対し、１つ
のメモリを割当てるためには、ａａｂｂ［２５６］など
と記述しなければならない。このように、並列動作は意
識しないレベルのビヘイビア記述で予め最適なメモリ構
成を考慮して、配列変数を用いた記述を行うことは非常
に困難である。

【００１５】このため、種々のメモリ構成に応じた配列
変数を記述するには、その都度設計者がビヘイビア記述
中の配列変数に関する部分を書き直して、高位合成を実
行し、試行錯誤的に最良のものを選択しなければならな
い。

【００１６】しかしながら、従来の方法では、ビヘイビ
ア記述を書き換えるための手間が大きいこと、ビヘイビ
ア記述自体を書き換えるためにビヘイビア記述中に誤り
が生じ易く、このためにビヘイビア記述のシミュレーシ
ョンによる検証を再度行う必要が生じる恐れがある。

【００１７】また一方、ビヘイビア記述中には、複数の
サブルーチンコールやサブルーチンが含まれており、こ
れらにハードウェアブロックを割り当てる方法として、
同じサブルーチンコールに対してそれぞれ別のハードウ
ェアブロックを割り当てる方法がある。

【００１８】しかしながら、この方法では、論理回路の
設計を行うと回路規模が大きくなってしまう。これは、
階層的に書かれた記述を平坦な構造にしてしまう為に生
じるもので、全ての同じサブルーチンコールでもそれぞ
れ別の物として取り扱っているからである。

【００１９】例えば、実際は時間的に全く重複のない時
刻に演算している２つの同じサブルーチンに対しても、
それぞれ２つの同じハードウェアブロックを与えてい
る。このような性質を持つ複数のサブルーチンコールに
対しては、一つのハードウェアブロックだけを対応させ
るのが理想的である。

【００２０】このため、同じサブルーチンコールに対し
て一つのハードウェアブロックを対応させるという方法
が考えられる。しかしながら、この方法では、演算時間
が重複した場合、並列動作が余り行えない回路構成とな
り、回路規模は小さくてすむのだが処理時間を満足させ
ることができない。

【００２１】そこで、これらのサブルーチンコールとハ
ードウェアの対応を設計者が行うという方法が考えられ
る。すなわち、演算時間が重複しない同じサブルーチン
コールに対しては一つのハードウェアブロックを割り当
て、重複する同じサブルーチンコールに対してはそれぞ
れ別のハードウェアブロックを割り当てることを設計者
が行うものである。

【００２２】しかしながら、サブルーチンを実行するハ
ードウェアブロックの演算時間は必ずしも一定でなく、
与えられたデータにより様々に変化することから調査を
行うだけでも大変な作業である。さらに、それらを制御
する回路部分の変更も必要となるので設計者の抱える負
担が膨大なものになってしまう。

【００２３】

【発明が解決しようとする課題】このように、従来の高
位合成装置においては、レジスタに割付ける各変数の属
する演算を考慮していないために、演算器及びレジスタ
の入力端子に余分なマルチプレクサなどの制御回路が必
要になり、冗長な論理回路が合成されるという問題があ
った。

【００２４】また、ビヘイビア記述中の配列変数に対し
て種々のメモリを割当てるには、ビヘイビア記述を書き
換えなければならず、手間や誤りが生ずるという問題が
あった。

【００２５】さらに、従来の高位合成装置では、複数の
同じサブルーチンコールに対してそれぞれ別のハードウ
ェアブロックを割り当てる方法や、同じサブルーチンコ
ールに対しては１つのハードウェアブロックを割り当て
る方法、または設計者の介入により上記２つの方法を組
み合わせてハードウェアブロックを割り当てる方法があ
った。

【００２６】しかしながら、これらの方法では、回路規
模が膨大な物になったり、処理時間を満足させることが
できなかったり、設計者の負担が大きくなるという問題
があった。

【００２７】本発明は上記のような従来技術の欠点を除
去するもので、第１の発明の目的とするところは、合成
後に余分な制御回路が不要となり、構成が簡単な論理回
路を合成することができる高位合成装置を提供すること
にある。

【００２８】また、第２の発明の目的とするところは、
記述を書き直さなくても、メモリ構成を変更した種々の
高位合成を容易に誤りなく行うことができ、高品質の高
位合成結果を得ることを可能とした高位合成装置を提供
することにある。

【００２９】さらに、第３の発明の目的とするところ
は、サブルーチンが実行する演算時間の重複状態を調
べ、各サブルーチンコールに必要となるハードウェアブ
ロックを割り当てることにより、並列動作が可能で、小
規模な論理回路を合成することができる高位合成装置を
提供することにある。

【００３０】

【課題を解決するための手段】上記目的を達成するた
め、第１の発明の高位合成装置は、動作機能記述によっ
て表わされた論理回路の動作を、動作周期毎にステート
分割するステート分割手段と、このステート分割手段に
よってステート分割された前記動作機能記述中の演算対
象となる変数を解析し、各ステート毎に前記変数に対応
するレジスタを求める変数解析手段と、この変数解析手
段によって求められた各ステート毎のレジスタを、異な
るステート間で共用するようにレジスタ割付けを行うマ
ージ実行手段とから構成されている。

【００３１】また、第２の発明の高位合成装置は、ビヘ
イビア記述中の配列変数に対するメモリの割当て方を示
すコマンドを入力するコマンド入力手段と、入力された
コマンドの割当て方を解析するメモリ割当てコマンド解
析手段と、解析された割当て方に応じて配列変数に対す
るメモリを割り当てるメモリ割当てコマンド処理手段
と、ビヘイビア記述からＲＴＬ（レジスタ転送レベル）
情報を生成するＲＴＬ情報生成手段とから構成されてい
る。

【００３２】さらに、第３の発明の高位合成装置は、ビ
ヘイビア記述を構文解析し、記述中の複数のサブルーチ
ンコールの実行順序関係を求める構文解析手段と、求め
られた実行順序関係から、前記複数のサブルーチンコー
ルによるツリー状の階層構造を作成する呼び出しツリー
作成手段と、前記実行順序関係と階層構造に基づいて各
サブルーチンコールに対応するサブルーチンの演算時間
を計算する演算時間解析手段と、計算された各サブルー
チンの演算時間の重複状態を解析するライフタイム解析
手段と、解析された演算時間の重複状態から、サブルー
チンを実行するハードウェアブロックの必要な個数を導
き出し、各サブルーチンコールに対してハードウェアブ
ロックの割り当てを行うハードウェアブロック割り当て
手段とから構成されている。

【００３３】

【作用】上記のような構成により、第１の発明は、ステ
ート分割手段によってステート分割された動作機能記述
を基にし、変数解析手段において各ステート毎に必要な
レジスタを求める。各変数の属する演算を考慮したマー
ジ規則を参照し、マージ実行手段においてレジスタの共
用化を実行する。そして、共用化されたレジスタを基に
し、論理回路を合成している。

【００３４】また、第２の発明は、ビヘイビア記述中の
配列変数に対する合成回路のメモリ構成の割当て方を示
すコマンドを入力すると、メモリ割当てコマンド解析手
段がこれを解析する。メモリ割当てコマンド処理手段が
入力されたコマンドに応じて、配列変数に対するメモリ
を割り当て、ＲＴＬ情報を生成して論理回路を合成して
いる。

【００３５】さらに、第３の発明は、入力されたビヘイ
ビア記述からデータと制御の流れを解析しサブルーチン
の呼び出しツリーを作成する。また、各サブルーチンに
対してサブルーチン全体の演算時間を解析する。これは
前述の呼び出しツリーを利用してボトムアップ方式に行
われる。

【００３６】得られたサブルーチンの演算時間解析結果
とその他の演算の演算時間解析結果よりサブルーチンの
ライフタイム（サブルーチンの実行開始時間と終了時
間）を解析する。この段階でライフタイムの重複状態を
判断し、どのサブルーチンを同じハードウェアブロック
とするかを決定する。

【００３７】ビヘイビア記述中に条件ループなどが含ま
れている場合などはライフタイム解析の結果が不定の場
合が生じるが、この場合はライフタイムを変数として取
扱い、同じハードウェアブロックを利用する場合は、条
件ループによる処理が終了するまでサブルーチンの実行
を待つようにハードウェアを自動的に設計する。

【００３８】

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

【００３９】第１の発明図１に、第１の発明の高位合成装置の一実施例の構成図
を示す。

【００４０】動作機能記述入力部１は、動作機能記述を
ステート分割部２に入力する。

【００４１】ステート分割部２は、動作機能記述入力部
１より入力された記述によって表わされる動作を、各ク
ロック・サイクル毎に実行される動作にステート分割す
る。変数解析部３は、ステート分割部２においてステー
ト分割された動作機能記述に基づき、ステート間で受け
渡しの必要な演算対象となる変数を解析し、各ステート
で必要とされるレジスタを求める。

【００４２】レジスタ・リスト記憶部４は、変数解析部
３で求めたレジスタを記憶する。

【００４３】マージ実行部５は、変数解析部３で求めた
レジスタに対し、マージ規則ライブラリ６に登録されて
いるマージ規則に基づいてマージを行う。

【００４４】合成部７は、マージされたレジスタ割付け
の結果を用いて論理回路を合成する。

【００４５】次に、図１で示した変数解析部３におけ
る、ステート分割後の各ステートで必要とされるレジス
タの求め方を説明する。

【００４６】図２は、この変数解析部３による処理手順
を示すフローチャートである。

【００４７】まず、最初のステート中の変数の解析を実
行する（ステップ１０１）。その結果、次のステートに
受け渡される変数を、変数名とステートの番号と変数の
属する演算の組としてレジスタ・リスト記憶部４に登録
する（ステップ１０２）。この操作を各ステートに渡り
繰り返す（ステップ１０２〜１０４）。

【００４８】この処理を、図１９で示したステート分割
後のデータフローを用いて説明する。

【００４９】例えば、加算演算が行われるステート１に
おいて変数を解析することにより、変数ｘ１，ｘ４，ｙ
１に対応するエッジがステート１とステート２の境界を
越えている。従って、これらの変数は次のステート２に
受け渡される必要があることがわかる。同様な解析を各
ステートに渡って実行する。

【００５０】この結果得られた、各ステート毎に必要と
されるレジスタを図３に示す。同図は、例えば、ステー
ト１には変数ｘ１，ｘ２，ｘ３，ｘ４に対応するレジス
タ（図中、太線）が必要であることを示している。

【００５１】次に、図１で示したマージ実行部５におけ
る、レジスタのマージ方法を説明する。マージのフロー
チャートを図４に示す。

【００５２】マージの際には、マージ規則ライブラリ６
に登録さされたマージ規則を参照してマージが実行され
る。マージ規則を、規則適用の優先順に下記に示す。

【００５３】マージ規則１．同種の演算の入力変数に対
応したレジスタをマージする。

【００５４】マージ規則２．同種の演算の出力変数に対
応したレジスタをマージする。

【００５５】マージ規則３．異種の演算の入力変数に対
応したレジスタをマージする。

【００５６】マージ規則４．異種の演算の出力変数に対
応したレジスタをマージする。

【００５７】マージ規則５．同種の演算の入力変数及び
出力変数に対応したレジスタをマージする。

【００５８】マージ規則６．同一変数に対応したレジス
タをマージする。

【００５９】以下、図１９で示したデータフローのマー
ジ方法を、図４及びマージ規則を用いて説明する。

【００６０】まず、マージ規則１を適用する事により、
１つの加算器で実行したい演算の入力変数ｘ２に対応し
たレジスタｘ２はステート１に、ｘ１はステート２に属
しているので、これら２つのレジスタｘ１，ｘ２はマー
ジ可能である（ステップ２０１〜２０３）。この結果、
レジスタｘ１とｘ２がマージされる（ステップ２０
４）。

【００６１】同様にステート１に属するレジスタｘ３と
ステート２に属するレジスタｙ１がマージ規則１により
マージ可能であるため、マージされる（ステップ２０１
〜２０４）。

【００６２】次に、マージ規則２を適用する前に、ステ
ート２に同一の変数ｙ１が現われているので、レジスタ
ｘ３とｙ１とのマージ操作に関与しない、乗算への入力
変数ｙ１をレジスタ・リスト記憶部４から削除する。そ
して、出力変数ｙ１とｚ１とに対応したレジスタをマー
ジする（ステップ２０５，２０６）。

【００６３】さらに、マージ規則５，６を適用すること
により、図５に示すレジスタ割付けの結果が得られる。
図５から分かるように、ステート１で用いられるレジス
タｘ２とステート２で用いられるレジスタｘ１とが共用
化されている。他のレジスタも同様に共用化されてい
る。

【００６４】このマージ結果を基にして論理回路を合成
部７で合成すると、図６のようになる。図２１の従来の
論理回路と比べると、ファンアウト数が１、ファンイン
数が１、マルチプレクサ１３の数が１減少している。

【００６５】第２の発明図７に、第２の発明による高位合成装置の構成を示す。
以下では、簡単のため、メモリはすべて単一ポート（異
なる番地のデータを同時には読み書きできない）とす
る。

【００６６】入出力装置２１から、ビヘイビア記述、メ
モリ割当てコマンドが入力されると、ビヘイビア記述解
析部２２はビヘイビア記述を解析し、データフロー表現
に変換して設計情報記憶部２８に格納する。

【００６７】図８にビヘイビア記述の記述の一例を示
し、図９に図８のビヘイビア記述に対応したデータフロ
ー表現の例を示す。これらの図においては、データサイ
ズ１２８の配列変数をａａ，ｂｂとし、ａａのｉ番目に
３を、ｂｂのｉ番目に５を入力することを表わしてい
る。

【００６８】次に、メモリ割当てコマンド解析部２３
は、メモリ割当てコマンドを解析し、メモリ割当てコマ
ンド処理部２４を起動する。メモリ割当てコマンド処理
部２４は、メモリ割当てコマンド解析結果に従って設計
情報記憶部２８に格納されたデータフロー表現を修正す
る。

【００６９】図１０に、メモリ割当てコマンド処理部２
４の処理フローを示す。

【００７０】図８に示したビヘイビア記述に対し、例え
ば図１１（ａ）に示すようなメモリ割当てコマンドが設
計者によって入力されると、メモリ割当てコマンド解析
部２３は、コマンドの種類としてａｃａｔ，変更前名１
としてａａ，変更前名２としてｂｂ，変更後名としてａ
ａｂｂ，変更後サイズとして２５６を解析し、メモリ割
当てコマンド処理部２４を起動する。

【００７１】メモリ割当てコマンド処理部２４は、図１
０に示した処理フローに従い処理を進める。まず、変更
前名１ａａ，変更前名２ｂｂ，変更後名ａａｂ
ｂ，変更後サイズ２５６を得る（ステップ３０１）。
コマンドの種類はａｃａｔであるから（ステップ３０
２）、データフロー表現中のａａをａａｂｂに置き換え
（ステップ３０３）、ｂｂをアドレスに２５６／２＝１
２８を加算してａａｂｂに置き換える（ステップ３０
４）。この結果、図１１（ｂ）に示すデータフロー表現
に修正される。すなわち、前半にはａａのデータが、後
半にはｂｂのデータが設定される。

【００７２】また、図１２（ａ）に示すようなメモリ割
当てコマンドが入力された場合は、メモリ割当てコマン
ド解析部２３は、コマンドの種類としてａｍｅｒｇｅ，
変更前名１としてａａ，変更前名２としてｂｂ、変更後
名としてａａｂｂ，変更後サイズとして２５６を解析
し、メモリ割当てコマンド処理部２４を起動する。

【００７３】メモリ割当てコマンド処理部２４は、変更
前名１ａａ，変更前名２ｂｂ，変更後名ａａｂ
ｂ，変更後サイズ２５６を得てる（ステップ３０
１）。コマンドの種類はａｍｅｒｇｅであるから（ステ
ップ３０２）、データフロー表現中のａａのアドレスを
１ビット左シフトした後、ａａｂｂに置き換える（ステ
ップ３０５）。さらに、ｂｂのアドレスを１ビット左シ
フトした後に１を加算し、ａａｂｂに置き換える（ステ
ップ３０６）。これにより、図１２（ｂ）に示すデータ
フロー表現に修正される。この処理により、ａａ，ｂｂ
のデータが１つずつ交互に設定される。

【００７４】なお、この第２の発明は、これら２つのコ
マンドに限らず、他のどのようなコマンドについても処
理可能なものである。

【００７５】このように、メモリが割当てられた後、ス
ケジューリング処理部２５は、設計情報記憶部２８に格
納されたデータフロー表現を各状態（クロックサイク
ル）毎の動作に、「同一メモリの異なる番地のデータを
同時には読み書きできない。」という制約下で分割す
る。

【００７６】アロケーション処理部２６は、設計情報記
憶部２８に格納されたデータフロー表現において、状態
をわたって保持する必要のある変数に対してなるべく少
ない数となるようにレジスタを割当て、演算オペレータ
に対してなるべく簡単なデータ転送路となるように演算
器を割当てる。

【００７７】さらに、ＲＴＬ情報生成部２７が、この結
果をレジスタ転送レベルの言語に変換して、設計情報記
憶部２８に格納するとともに、入出力装置２１に出力す
る。以上のようにして、メモリ割当てコマンドに従って
配列変数に対するメモリ割当てが実現される。

【００７８】なお、今回の実施例では、２つの配列変数
に対して１つのメモリを割当てる場合を示したが、この
発明はこれに限定されるものではない。例えば、データ
サイズの大きな１つの配列変数として定義されていたも
のを、複数の小さなデータサイズのメモリに分割して割
当てることもできる。

【００７９】また、複数の配列変数がある場合、１部の
配列についてのみこの第２の発明を適応し、残りの配列
に関しては従来方法による種々のメモリ割当ての組み合
わせを繰り返し実行し、最良の結果となったものを自動
的に選択するようにしても良い。

【００８０】第３の発明図１３は、第３の発明の高位合成装置の一実施例の構成
を示すブロック図である。

【００８１】入力されたビヘイビア記述３１は、構文解
析部３２で解析された後にサブルーチンコールの実行順
序関係を表わす、接続データ３３に変換される。この接
続データ３３から呼び出しツリー作成部３４がサブルー
チンの呼び出しツリーの作成を行う。

【００８２】演算時間解析部３５ではこの呼び出しツリ
ーを参考にボトムアップ式にサブルーチンの演算時間の
解析を行う。この際にサブルーチンの演算時間が不定の
場合が生じるがその場合は変数を割り当てて実行を続け
る。

【００８３】次に、算出した演算時間を参照してサブル
ーチンライフタイム解析部３６がサブルーチン毎のライ
フタイムの解析を行う。このライフタイムの解析結果を
基にハードウェアブロック割り当て部３７が必要なハー
ドウェアブロックの個数、及びそれらハードウェアブロ
ックに割り当てられたサブルーチンコールの対応表、す
なわちハードウェア構成３８を作成する。

【００８４】図１４は、入力となるビヘイビア記述の一
例である。このビヘイビア記述３１を入力した構文解析
部３２は接続データ３３の作成を行う。作成された接続
データ３３の例を図１５に示した。

【００８５】mainという関数の接続データ３３を表した
ものが図１５（ａ）である。この図ではmainという関数
の中で sub１， sub３というサブルーチンがそれぞれ呼
ばれていて、かつ両者の実行順序に制限が無いことを表
している。

【００８６】一方、 sub１というサブルーチンの接続デ
ータ３３を表したものが図１５（ｂ）である。これは s
ub１というサブルーチンの中で sub２， sub３というサ
ブルーチンがそれぞれ呼ばれていて、かつ両者の実行順
序は sub２の実行が最初に終了しなければいけないこと
を表している。

【００８７】この接続データ３３は呼び出しツリー作成
部３４に入力され、呼び出しツリーの作成が行われる。
この例が図１６である。呼び出しツリーには実行の順序
関係は表されておらず、サブルーチンの階層構造のみが
表されている。本例ではmainという関数の中で sub１，
sub３のサブルーチンが呼ばれ sub１のサブルーチンの
中で sub２， sub３のサブルーチンが呼ばれていること
を表している。

【００８８】これらの呼び出しツリーと接続データ３３
を入力として演算時間解析部３５が動作し、各サブルー
チンの演算時間が計算される。この計算は呼び出しツリ
ーをボトムアップ式にたどり実行される。例によると、
まず sub２の演算時間が計算される。 sub２ではサブル
ーチンの呼び出しを行っていないので接続データ３３よ
り演算時間が計算できる。

【００８９】同様にして sub３の演算時間が計算され
る。ここで sub１の中で使われているサブルーチンの演
算時間が解ったことになるので、 sub１の演算時間が計
算できるようになる。

【００９０】このようにして計算した結果を用いてサブ
ルーチンライフタイ解析部３６がそれぞれのライフタイ
ムの解析を行う。行った結果が図１７である。参考のた
めに上部に呼び出しツリーを書き入れてある。例えばこ
こで sub１のライフタイムはｔ２からｔ８ということに
なる。

【００９１】最後にこの結果からハードウェアブロック
割り当て部３７がそれぞれのサブルーチンに対して必要
なハードウェアブロックの個数を導き出して割り当て
る。本例では２つの sub３のサブルーチンコールが使わ
れているが両者のライフタイムの重複が無いことが解
る。そこでこの２つのサブルーチンコールは同じハード
ウェアブロックで実行可能と言う結論を出して図１８の
様なハードウェア構成を取るように論理回路を構成す
る。

【００９２】仮に、図１７において、２つの sub３の演
算時間が重複していれば、 sub３に対するハードウェア
ブロックを２つ割り当てることになる。

【００９３】なお、本例ではサブルーチンのライフタイ
ムは決定できかつ重複の無い場合であったが、記述によ
っては演算時間の解析が不可能な物もある。例えば条件
ループなどが例として挙げられる。これは条件が満たさ
れるまで何回ループするかを調べることが静的には困難
なためである。

【００９４】このような場合には、ライフタイムとして
変数を割り当てておく。ハードウェアブロック割り当て
部３７ではこの変数時間を考慮して重複の起こりにくい
サブルーチンを対象としてハードウェアブロックを割り
当てていく。しかし、完全に重複しないという保証がな
いため、条件ループによる処理が終了したか否かをチェ
ックするコントロール回路を新たに付加してこれを回避
する。

【００９５】つまり、後から実行されるサブルーチンに
割り当てられるハードウェアブロックに、前で実行され
ている条件ループによる処理が終わるまで待機させるコ
ントロール回路を付加する。これによって、同時に同じ
ハードウェアブロックの使用を回避する様に回路を構成
することができる。

【００９６】

【発明の効果】以上説明したように、第１の発明の高位
合成装置によれば、ステート分割された動作機能記述に
おいて各ステートで必要とされるレジスタを求め、変数
の属する演算を考慮したマージ規則に基づいてレジスタ
のマージを行い、論理回路を合成している。これによ
り、演算器及びレジスタの入力端子に余分なマルチプレ
クサがなくなり、構成が簡単な論理回路を得ることがで
きる。

【００９７】また、第２の発明の高位合成装置によれ
ば、ビヘイビア記述を書き換えることなく、メモリ構成
を変更した種々の高位合成を容易に行うことができ、こ
の中から最も良いものを選択することにより、高品質の
高位合成結果を得ることができる。

【００９８】さらに、第３の発明の高位合成装置によれ
ば、サブルーチンの演算時間の重複を解析し、ハードウ
ェアブロックを割り当てているので、並列動作が可能
で、規模が小さい論理回路を合成でき、かつ設計者の負
担を軽減することができる。

【図面の簡単な説明】

【図１】第１の発明による高位合成装置の一実施例の構
成図である。

【図２】図１で示した変数解析部による処理手順を示す
フローチャートである。

【図３】変数解析部によって求められたレジスタとステ
ートとの関係を示す図である。

【図４】図１で示したマージ実行部によるマージの処理
手順を示すフローチャートである。

【図５】マージ実行部によって最終的に得られたレジス
タ割付けの結果を示す図である。

【図６】第１の発明によって合成された論理回路のブロ
ック図である。

【図７】第２の発明による高位合成装置の一実施例の構
成を示すブロック図である。

【図８】第２の発明の実施例で用いたビヘイビア記述の
一例を示す記述図である。

【図９】図８で示したビヘイビア記述に対応したデータ
フロー表現である。

【図１０】図７で示したメモリ割当てコマンド処理部の
処理を示すフローチャートである。

【図１１】第２の発明の実施例で用いたメモリ割当てコ
マンドとメモリ割当て処理結果を示す図である。

【図１２】図１１と異なるメモリ割当てコマンドとメモ
リ割当て処理結果を示す図である。

【図１３】第３の発明による高位合成装置の一実施例の
構成を示すブロック図である。

【図１４】第３の発明の実施例で用いたビヘイビア記述
の一例である。

【図１５】図１４のビヘイビア記述から作成された接続
データである。

【図１６】図１４のビヘイビア記述から作成された呼び
出しツリーである。

【図１７】図１５の接続データと図１６の呼び出しツリ
ーから解析されたサブルーチンライフタイムである。

【図１８】図１７のサブルーチンライフタイムから割り
当てられたハードウェア構成図である。

【図１９】第１の発明で用いた、ステート分割後のデー
タフローの一例を示すデータフロー図である。

【図２０】第１の発明に対する、従来のレジスタ割付け
方法による割付け結果を示す図である。

【図２１】第１の発明に対する、従来の高位合成装置に
よって合成された論理回路のブロック図である。

【符号の説明】

１動作機能記述入力部２ステート分割部３変数解析部４レジスタ・リスト記憶部５マージ実行部６マージ規則ライブリ７合成部２１入出力装置２２ビヘイビア記述解析部２３メモリ割当てコマンド解析部２４メモリ割当てコマンド処理部２５スケジューリング処理部２６アロケーション処理部２７ＲＴＬ情報生成部２８設計情報記憶部３１ビヘイビア記述３２構文解析部３３接続データ３４呼び出しツリー作成部３５演算時間解析部３６サブルーチンライフタイム解析部３７ハードウェアブロック割り当て部３８ハードウェア構成

Claims

【特許請求の範囲】

【請求項１】動作機能記述によって表わされた論理回
路の動作を、動作周期毎にステート分割するステート分
割手段と、このステート分割手段によってステート分割された前記
動作機能記述中の演算対象となる変数を解析し、各ステ
ート毎に前記変数に対応するレジスタを求める変数解析
手段と、この変数解析手段によって求められた各ステート毎のレ
ジスタを、異なるステート間で共用するようにレジスタ
割付けを行うマージ実行手段とを有することを特徴とす
る高位合成装置。
【請求項２】ビヘイビア記述中の配列変数に対するメ
モリの割当て方を示すコマンドを入力するコマンド入力
手段と、入力されたコマンドの割当て方を解析するメモリ割当て
コマンド解析手段と、解析された割当て方に応じて配列変数に対するメモリを
割り当てるメモリ割当てコマンド処理手段と、ビヘイビア記述からレジスタ転送レベル情報を生成する
レジスタ転送レベル情報生成手段とを有することを特徴
とする高位合成装置。
【請求項３】ビヘイビア記述を構文解析し、記述中の
複数のサブルーチンコールの実行順序関係を求める構文
解析手段と、求められた実行順序関係から、前記複数のサブルーチン
コールによるツリー状の階層構造を作成する呼び出しツ
リー作成手段と、前記実行順序関係と階層構造に基づいて各サブルーチン
コールに対応するサブルーチンの演算時間を計算する演
算時間解析手段と、計算された各サブルーチンの演算時間の重複状態を解析
するライフタイム解析手段と、解析された演算時間の重複状態から、サブルーチンを実
行するハードウェアブロックの必要な個数を導き出し、
各サブルーチンコールに対してハードウェアブロックの
割り当てを行うハードウェアブロック割り当て手段とを
有することを特徴とする高位合成装置。