動作合成方法、動作合成プログラム及び動作合成装置
【課題】動作合成により共有化するレジスタのビット幅を小さくすることが可能な動作合成方法、動作合成プログラム及び動作合成装置を提供する。
【解決手段】動作合成方法は、動作記述情報に基づいてスケジューリングしたＣＤＦＧを生成し、スケジューリングされたＣＤＦＧに基づいてライフタイムを変数毎に生成し（Ｓ３０１）、ライフタイム情報が時間軸上で重ならないｍ個の変数を選択し（Ｓ３０２）、第１のビット幅の第１の変数と、その他の変数内の第１のビット幅のビットとに、第１のレジスタを割り当て（Ｓ３０７）、その他の変数内の第１のビット幅のビット以外のビットに、第２のレジスタを割り当て（Ｓ３０８）、第１及び第２のレジスタを有する合成回路の回路情報を出力する。
【解決手段】動作合成方法は、動作記述情報に基づいてスケジューリングしたＣＤＦＧを生成し、スケジューリングされたＣＤＦＧに基づいてライフタイムを変数毎に生成し（Ｓ３０１）、ライフタイム情報が時間軸上で重ならないｍ個の変数を選択し（Ｓ３０２）、第１のビット幅の第１の変数と、その他の変数内の第１のビット幅のビットとに、第１のレジスタを割り当て（Ｓ３０７）、その他の変数内の第１のビット幅のビット以外のビットに、第２のレジスタを割り当て（Ｓ３０８）、第１及び第２のレジスタを有する合成回路の回路情報を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動作合成方法、動作合成プログラム及び動作合成装置に関し、特に、変数の演算動作が記述された動作記述を動作合成する動作合成方法、動作合成プログラム及び動作合成装置に関する。
【背景技術】
【０００２】
近年、ＬＳＩの大規模化が進んでおり、より効率の良い設計方法や設計ツールが望まれている。そこで、ＬＳＩの機能設計において、動作レベルの記述である動作記述を動作合成し、レジスタ転送レベルの記述であるＲＴＬ記述を生成する手法が知られている。動作合成では、Ｃ言語と同様の言語により回路素子を意識せずに動作のみを記述するため、回路設計を容易にし、設計期間を短縮することができる。
【０００３】
従来の動作合成方法として、非特許文献１に記載の方法が知られている。図２８は、非特許文献１に記載された従来の動作合成方法を示している。
【０００４】
図に示されるように、従来の動作合成方法９００では、回路の動作を記述した動作記述が入力され（９０１）、ＨＤＬコンパイラが、この動作記述を解析し（９０２）、内部表現に変換される（９０３）。この内部表現としては，動作記述に現れたデータの流れ(データフロー)と各演算の実行順序の制御の流れ(コントロールフロー)を表した，コントロールデータフローグラフ(CDFG : Control Data Flow Graph)が用いられる。
【０００５】
生成された内部表現に対して、スケジューリングが行われる（９０４）。スケジューリングでは、動作記述中の各演算やデータ転送を実行する具体的な制御ステップを決定する。また、スケジューリングされた内部表現に対しアロケーションが行われる（９０５）。アロケーションでは所望の動作を実現する回路構成を決定する。
【０００６】
スケジューリングとアロケーションが終了すると，レジスタ，機能ユニット，マルチプレクサ等を回路要素としたデータパスのネットリストと（９０８），各クロックで実行する動作を制御する信号と順次実行させるための状態遷移の情報を示す制御回路用テーブル（９０７）が生成される（９０６）。
【０００７】
図２９は、非特許文献１に記載された従来の動作合成方法におけるアロケーション処理の例を示している。
【０００８】
従来の動作合成方法では、動作記述に基づいてＣＤＦＧが生成され、スケジューリングが行われると、図２９（ａ）のようなスケジューリング後のＣＤＦＧが生成される。そうすると、従来の動作合成方法では、アロケーションにより、変数ａ，ｂ，ｃ，ｄ，ｅにレジスタが割り当てられ、加算ｏ１、ｏ２に加算器が割り当てられる。
【０００９】
一般的に、アロケーションでは、回路面積を減らす目的で、複数の変数を同じレジスタに割り当てて使用する「レジスタの共有化」が行われている。図２９（ｂ）（ｃ）は、レジスタを共有化してアロケーションを行った例である。
【００１０】
図２９（ａ）の例では、変数ａ及び変数ｂと加算器は同時に使用され、変数ｄ及び変数ｃと加算器は同時に使用されるが、その他の組み合わせは同時に使用されない。このため、図２９（ｂ）では、変数ａ、ｄ、ｅでレジスタｒ１を共有し、変数ｂにレジスタｒ２、変数ｃにレジスタｒ３を割り当て、共有した加算器の入力の値を選択するためにマルチプレクサを割り当てている。
【００１１】
また、図２９（ｃ）では、変数ａ、ｅでレジスタｒ１を共有し、変数ｂ、ｄでレジスタｒ２を共有し、変数ｃにレジスタｒ３を割り当て、共有したレジスタと加算器の入力の値を選択するために２つのマルチプレクサを割り当てている。
【００１２】
図３０は、非特許文献１に記載された従来の動作合成方法におけるレジスタの共有化の例を示している。図３０（ａ）は、図２９（ａ）と同様にスケジューリング後のＣＤＦＧである。
【００１３】
スケジューリング後のＣＤＦＧが生成されると、従来の動作合成方法では、図３０（ｂ）のように各変数のライフタイムを計算する。ライフタイムとは、変数に値が書き込まれてから使用されるまでの期間であり、変数に値を保持する必要がある期間である。
【００１４】
図３０（ｂ）の例では、変数ａはステップ１より前からステップ２まで、変数ｂはステップ１より前からステップ１まで、変数ｃはステップ１からステップ２まで、変数ｄはステップ２からその後までが、それぞれライフタイムである。ライフタイムが重ならない変数は同じレジスタに割り当てて共有化することが可能である。
【００１５】
従来の動作合成方法では、図３０（ｃ）のように、変数ａ，ｂ，ｃ，ｄをそのライフタイムの開始時刻順にソートし，最初の変数を１番目のレジスタに割り当てる。以下、変数を順に調べながら、ライフタイムが重ならない限りそのレジスタに変数を割り当てていく。割り当てられる変数がなくなると新しいレジスタを用意し，すべての変数が割り当てられるまで繰り返す。図３０（ｃ）の例では、まず、変数ａと変数ｄとでライフタイムが重ならないため、レジスタｒ１を割り当てて共有化し、変数ｂと変数ｃとでライフタイムが重ならないため、レジスタｒ２を割り当てて共有化している。
【００１６】
また、レジスタの共有に関する従来の動作合成方法として、特許文献１が知られている。図３１は、特許文献１に記載された従来の動作合成方法におけるレジスタの共有化の例を示している。
【００１７】
図３１は、変数ａ１の値をレジスタｃ１に転送し、変数ｂ１の値をレジスタｃ２に転送する場合に、ｃ１とｃ２とを一つのレジスタ（５ビット）で共有化する例である。
【００１８】
図３１（ａ）では、２ビットのｓｉｇｎｅｄの変数ａ１、及び４ビットのｓｉｇｎｅｄの変数ｂ１を共通のレジスタ（５ビット）に転送する場合、転送先のレジスタのビット数に対して不足するビット数を変数ａ１及びｂ１にそれぞれ付与し、マルチプレクサ（ＭＵＸ）によってレジスタに転送する変数を切り替えている。ここで、変数ａ１及びｂ１はそれぞれ０ビット目が符号ビットであるため、不足するビットには符号ビットと同じデータを挿入している。
【００１９】
図３１（ｂ）では、４ビットのｕｎｓｉｇｎｅｄの変数ａ２、及び２ビットのｕｎｓｉｇｎｅｄの変数ｂ２を共通のレジスタ（５ビット）に転送する場合、ｓｉｇｎｅｄの変数の場合と同様に、転送先のレジスタのビット数に対して不足するビット数を変数ａ２及びｂ２にそれぞれ付与し、マルチプレクサ（ＭＵＸ）によってレジスタに転送する変数を切り替えている。ここで、変数ａ２及びｂ２はそれぞれ符号ビットを持たないため、不足するビットにはデータ"０"を挿入している。
【００２０】
なお、従来の動作合成方法に関連する技術として特許文献２も知られている。しかし、特許文献２は、動作合成の結果を検証する検証方法の技術であり、動作合成方法の具体的な内容については記載されていない。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】松永裕介、"高位レベル合成"、インターネット<URL:http://www.c.csce.kyushu-u.ac.jp/~matsunaga/lecture/lsicad/pdf/Lecture06.pdf>
【特許文献】
【００２２】
【特許文献１】特許第２８６１９９４号公報
【特許文献２】特開２０１１−３４５１７号公報
【発明の概要】
【発明が解決しようとする課題】
【００２３】
上記のように、特許文献１や２には、従来の動作合成方法において、アロケーションを行う際に、レジスタを共有化することが記載されている。
【００２４】
特に、図３１で示したように、従来の動作合成方法では、ビット幅の違う変数に対してもレジスタの共有化が可能となるよう、ビット幅の小さい変数の上位ビットにデータを補って、ビット幅の大きい変数に揃えた上で、レジスタの共有化を行っていた。すなわち、図３１（ａ）では、ビット幅の大きな変数ｂ１に合わせて、ビット幅の小さな変数ａ１の上位ビットを符号拡張し、また、図３１（ｂ）では、ビット幅の大きな変数ａ２に合わせて、ビット幅の小さな変数ｂ２の上位ビットを"０"で埋めて、レジスタを共有化していた。
【００２５】
そうすると、この共有化されたレジスタでは、ビット幅の小さな変数から見ると、未使用の無駄なビットが存在することになる。
【００２６】
したがって、従来の動作合成方法では、ビット幅の大きい変数に合わせたビット幅でレジスタを共有化するため、ビット幅の小さい変数にとって未使用のビットが発生することから、共有化するレジスタのビットが無駄に大きいという問題があった。
【課題を解決するための手段】
【００２７】
本発明に係る動作合成方法は、変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択し、前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、前記第１及び第２のレジスタを有する合成回路の回路情報を出力するものである。
【００２８】
本発明に係る動作合成方法は、変数の演算動作を含む動作記述情報から、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、前記スケジューリングされたデータフローグラフ情報から、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、前記ライフタイム情報が時間軸上で重ならない、第１のビット幅として定義された第１の変数と、第２の変数とを選択し、前記第１の変数と、前記第２の変数に含まれる前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記第２の変数に含まれる前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、前記第１及び第２のレジスタを有する合成回路の回路情報を出力するものである。
【００２９】
本発明に係る動作合成プログラムは、コンピュータに動作合成処理を実行させる動作合成プログラムであって、前記動作合成処理は、変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択し、前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、前記第１及び第２のレジスタを有する合成回路の回路情報を出力するものである。
【００３０】
本発明に係る動作合成装置は、変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成するスケジューリング部と、前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成するライフタイム生成部と、前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択する変数選択部と、前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当てるレジスタ割り当て部と、前記第１及び第２のレジスタを有する合成回路の回路情報を出力する回路情報出力部と、を備えるものである。
【００３１】
本発明では、第１のビット幅の第１の変数と、その他の変数（第２の変数）のうちの第１のビット幅のビットとに、レジスタを割り当てて共有化するため、共有化するレジスタのビット幅を小さくすることができる。
【発明の効果】
【００３２】
本発明によれば、共有化するレジスタのビット幅を小さくすることが可能な動作合成方法、動作合成プログラム及び動作合成装置を提供することができる。
【図面の簡単な説明】
【００３３】
【図１】本発明の実施の形態１に係る動作合成装置を実現するためのコンピュータシステムのハードウェア構成を示す構成図である。
【図２】本発明の実施の形態１に係る動作合成装置の機能構成を示すブロック図である。
【図３】本発明の実施の形態１に係る記憶ユニットアロケーション部の機能構成を示すブロック図である。
【図４】本発明の実施の形態１に係る動作合成方法の流れを示すフローチャートである。
【図５】本発明の実施の形態１に係る記憶ユニットのアロケーション方法の流れを示すフローチャートである。
【図６】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図７】本発明の実施の形態１に係る動作合成方法で使用されるデータ構造の具体例を示す図である。
【図８】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図９】本発明の実施の形態１に係る動作合成方法で使用されるデータ構造の具体例を示す図である。
【図１０】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図１１】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図１２】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図１３】本発明の実施の形態１に係る動作合成方法により生成されるデータパスの回路構成を示す回路図である。
【図１４】本発明の実施の形態１に係る動作合成方法により生成される合成回路の回路構成を示す回路図である。
【図１５】本発明の実施の形態１に係る動作合成方法により生成されるＲＴＬの記述例を示す図である。
【図１６】本発明の実施の形態１に係る動作合成方法により生成されるＲＴＬの記述例を示す図である。
【図１７】本発明の実施の形態２に係る動作合成装置の機能構成を示すブロック図である。
【図１８】本発明の実施の形態２に係る動作合成方法により生成される合成回路の回路構成を示す回路図である。
【図１９】本発明の実施の形態２に係る動作合成方法により生成される合成回路の動作を示すタイミングチャートである。
【図２０】本発明の実施の形態３に係る記憶ユニットのアロケーション方法の流れを示すフローチャートである。
【図２１】本発明の実施の形態４に係る記憶ユニットのアロケーション方法の流れを示すフローチャートである。
【図２２】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２３】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２４】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２５】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２６】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２７】本発明の実施の形態４に係る動作合成方法により生成されるデータパスの回路構成を示す回路図である。
【図２８】従来の動作合成方法を示す図である。
【図２９】従来の動作合成方法を示す図である。
【図３０】従来の動作合成方法を示す図である。
【図３１】従来の動作合成方法を示す図である。
【図３２】本発明と比較するための参考例を示す図である。
【発明を実施するための形態】
【００３４】
（本発明の実施の形態１）
以下、図面を参照して本発明の実施の形態１について説明する。
【００３５】
図１は、本発明の実施の形態１に係る動作合成装置が実現されるコンピュータシステムのハードウェア構成を示している。なお、後述する他の実施の形態においても、図１と同様のコンピュータシステムにより動作合成装置が実現される。
【００３６】
このコンピュータシステム１００は、パーソナルコンピュータやワークステーション等の情報処理装置である。図に示されるように、コンピュータシステム１００は、ＣＰＵ１０２、メインメモリ１０３、ハードディスク１０４等を内蔵した本体部１０１、本体部１０１からの指示により画面表示を行う表示装置１０５、このコンピュータシステムにユーザの指示や文字情報を入力するためのキーボード１０６、および表示装置の画面上における任意の位置を指定し、その位置に表示されていたアイコン等に応じた指示を入力するマウス１０７から構成される。
【００３７】
なお、ＣＰＵ１０２及びメインメモリ１０３は、プログラムを実行し各部を制御する制御部の一例であり、ハードディスク１０４は、プログラム等を記憶する記憶部の一例である。制御部と記憶部は、一つの装置でもよいし、複数の装置であってもよい。例えば、複数の制御装置や複数の記憶装置に分散されていてもよい。また、表示装置１０５は、ユーザに対し種々の出力を行う出力装置の一例であり、キーボード１０６、マウス１０７は、ユーザが種々の入力操作を行う入力装置の一例である。
【００３８】
ハードディスク１０４には、本実施形態に係る動作合成装置を実現するための動作合成プログラム１０８、動作合成処理等に必要なその他の各種データ１０９が格納される。動作合成プログラム１０８は、図４，図５に後述する動作合成方法の処理を実行するためのプログラムであり、各種データ１０９は、図２に後述する各記憶部に記憶されるデータである。
【００３９】
コンピュータシステム１００が、動作合成プログラム１０８および各種データ１０９をメインメモリ１０３にロードし、ＣＰＵ１０２はメインメモリ１０３にロードされた動作合成プログラム１０８を実行することで、本実施形態の動作合成方法の各処理が実施されて、動作合成装置（図２、図３に後述する機能構成）が実現される。なお、コンピュータシステム１００の基本動作は、ハードディスク１０４に格納された基本プログラムであるオペレーティングシステム（ＯＳ）を介して実行される。
【００４０】
図２は、本発明の実施の形態１に係る動作合成装置の機能構成を示している。この動作合成装置２００は、コンピュータシステム１００上で動作合成プログラムが実行されて実現される。
【００４１】
図に示されるように、この動作合成装置２００は、動作記述情報記憶部２０１、パーズ処理部２０２、内部表現情報記憶部２０３、スケジューリング処理部２０４、アロケーション処理部２０５、制御回路用テーブル及びネットリスト生成部２０６、制御回路用テーブル記憶部２０７、ネットリスト記憶部２０８、ＲＴＬ出力部２０９、ＲＴＬ情報記憶部２１０を備えている。
【００４２】
動作記述情報記憶部２０１は、動作記述言語で記述された動作記述を表すデータである動作記述情報を記憶する。動作記述は、Ｃ言語をハードウェア記述のために拡張したＳｙｓｔｅｍＣ等の動作記述言語により記述される。例えば、動作記述情報は、ユーザによりキーボード１０６等を介して入力されて、動作記述情報記憶部２０１に記憶される。
【００４３】
パーズ処理部２０２は、動作記述情報記憶部２０１に記憶された動作記述情報に基づいて、動作記述情報をパーズ（変換）して、内部表現であるＣＤＦＧを表す内部表現情報を生成する。
【００４４】
内部表現情報記憶部２０３は、パーズ処理部２０２が生成した内部表現情報を記憶する。また、内部表現情報記憶部２０３は、内部表現情報に対しスケジューリング処理部２０４及びアロケーション処理部２０５が処理した結果である、スケジューリング後のＣＤＦＧやアロケーション後のＣＤＦＧのデータも記憶される。
【００４５】
スケジューリング処理部２０４は、パーズ処理部２０２が生成した内部表現情報に基づいて、この内部表現情報に対し各演算が実行される制御ステップをスケジューリングして、スケジューリング後の内部表現情報を生成する。
【００４６】
アロケーション処理部２０５は、スケジューリング処理部２０４が生成したスケジューリング後の内部表現情報に基づいて、この内部表現情報に対し機能ユニット、記憶ユニット、通信ユニットのアロケーションを行って、アロケーション後の内部表現情報を生成する。
【００４７】
また、アロケーション処理部２０５は、加算器等の機能ユニットをアロケーションする機能ユニットアロケーション部２０５ａ、レジスタ等の記憶ユニットをアロケーションする記憶ユニットアロケーション部２０５ｂ、マルチプレクサ等の通信ユニットをアロケーションする通信ユニットアロケーション部２０５ｃを有している。
【００４８】
制御回路用テーブル及びネットリスト生成部２０６は、スケジューリング処理部２０４及びアロケーション処理部２０５が生成したスケジューリング及びアロケーション後の内部表現情報に基づいて、この内部表現情報から制御回路の制御対象と制御タイミング等を特定して制御回路用テーブルを生成し、かつ、この内部表現情報からデータパスの各回路素子と接続関係を特定してネットリストを生成する。
【００４９】
制御回路用テーブル記憶部２０７は、制御回路用テーブル及びデータパスのネットリスト生成部２０６が生成した制御回路用テーブルを記憶する。ネットリスト記憶部２０８は、御回路用テーブル及びデータパスのネットリスト生成部２０６が生成したネットリストを記憶する。
【００５０】
ＲＴＬ出力部２０９は、制御回路用テーブル及びネットリスト生成部２０６が生成した制御回路用テーブルとデータパスのネットリストとに基づいて、制御回路用テーブルに応じた制御回路とネットリストのデータパスとを合成した合成回路のＲＴＬ情報を生成し、生成したＲＴＬ情報を出力する。
【００５１】
ＲＴＬ情報記憶部２１０は、ＲＴＬ出力部２０９が出力したＲＴＬ情報を記憶する。ＲＬＴ情報は、ＶＨＤＬ(Very High Speed Integrated Circuits Hardware Description Language)等のハードウェア記述言語（Hardware Description Language）により記述されたＲＴＬのデータである。
【００５２】
図３は、本発明の実施の形態１に係る記憶ユニットアロケーション部の機能構成を示している。この記憶ユニットアロケーション部２０５ｂは、図２のアロケーション処理部２０５に含まれている。
【００５３】
図に示されるように、記憶ユニットアロケーション部２０５ｂは、ライフタイム計算部２２１、変数選択部２２２、ビット幅検出部２２３、符号拡張部２２４、変数分割部２２５、レジスタ割り当て部２２６を備えている。
【００５４】
ライフタイム計算部２２１は、スケジューリング処理部２０４がスケジューリングしたスケジューリング後の内部表現情報（ＤＣＦＧ）に基づいて、各制御ステップで使用される変数を求め、変数ごとにライフタイムを計算する。
【００５５】
変数選択部２２２は、ライフタイム計算部２２１が計算したライフタイムに基づいて、各変数のライフタイムが時間軸上（制御ステップ）で重なっているかどうか判定し、ライフタイムが重ならない２つの変数を選択する。
【００５６】
ビット幅検出部２２３は、変数選択部２２２が選択した２つの変数について、ビット幅を検出し、２つのビット幅が異なるかどうか判定する。また、ビット幅検出部２２３は、符号拡張部２２４が符号を拡張した変数についても、ビット幅が異なるかどうか判定する。
【００５７】
符号拡張部２２４は、ビット幅検出部２２３により２つの変数のビット幅が異なると判定された場合、ビット幅が小さい変数を必要最小限に符号を拡張する。
【００５８】
変数分割部２２５は、ビット幅検出部２２３により２つの変数のビット幅が異なると判定された場合、ビット幅が大きい変数を、ビット幅が小さい変数の幅に合わせて上位ビットと下位ビットにビット分割する。
【００５９】
レジスタ割り当て部２２６は、ビット幅検出部２２３により２つの変数のビット幅が同じであると判定された場合、この２つの変数に同じレジスタを割り当てる。また、レジスタ割り当て部２２６は、変数分割部２２５が分割した下位ビットと、ビット幅の小さい変数とに同じレジスタを割り当て、変数分割部２２５が分割した残りの上位ビットに、別のレジスタを割り当てる。
【００６０】
以下に、本発明の実施の形態１における、記憶ユニットのアロケーション方法を含む動作合成方法の動作について説明する。まず、図４及び図５のフローチャートを用いて動作合成方法の流れを説明した後、図６〜図１６を用いて動作合成方法の具体例について説明する。
【００６１】
図４に示すように、本実施形態の動作合成方法Ｓ２００では、まず、パーズ処理部２０２は、入力された動作記述のデータである動作記述情報をパーズして、ＣＤＦＧのデータである内部表現情報を生成する（Ｓ２０１）。
【００６２】
次いで、スケジューリング処理部２０４は、Ｓ２０１で生成された内部表現情報に対しスケジューリングを行って、スケジューリング後の内部表現情報を生成する（Ｓ２０２）。
【００６３】
次いで、アロケーション処理部２０５が、Ｓ２０２で生成されたスケジューリング後の内部表現情報に対しアロケーションを行って、アロケーション後のＣＤＦＧが生成される（Ｓ２０３〜Ｓ２０５）。すなわち、機能ユニットアロケーション部２０５ａは、内部表現情報に対し加算器等の機能ユニットを割り当て（Ｓ２０３）、記憶ユニットアロケーション部２０５ｂは、内部表現情報に対しレジスタ等の記憶ユニットを割り当て（Ｓ２０４）、通信ユニットアロケーション部２０５ｃは、内部表現情報に対しマルチプレクサ等の通信ユニットのアロケーションを行う（Ｓ２０５）。
【００６４】
なお、機能ユニット、記憶ユニット、通信ユニットのアロケーションは、互いに関連しているため、アロケーションの順序は適宜変更される。例えば、記憶ユニットのアロケーションでレジスタを共有化すると、レジスタの構成が変わるため、機能ユニットや通信ユニットの割り当ても変更される。
【００６５】
次いで、制御回路用テーブル及びネットリスト生成部２０６は、Ｓ２０２〜Ｓ２０５で生成されたスケジューリング及びアロケーション後の内部表現情報を用いて、制御回路用テーブル及びデータパスのネットリストを生成する（Ｓ２０６）。
【００６６】
次いで、ＲＴＬ出力部２０９は、Ｓ２０６で生成された制御回路用テーブル及びデータパスのネットリストを用いて、制御回路とデータパスを合成した合成回路のＲＴＬ情報を出力し（Ｓ２０７）、動作合成処理が終了するＲＴＬを出力する（Ｓ２０７）。
【００６７】
また、図５に示されるように、記憶ユニットのアロケーション処理（Ｓ２０４）では、まず、ライフタイム計算部２２１は、スケジューリングされたＣＤＦＧ（内部表現）上で状態を横切る各変数についてライフタイムを計算する（Ｓ３０１）。次いで、変数選択部２２２は、Ｓ３０１でライフタイムを計算した複数の変数のうち、ライフタイムの重ならない２つの変数に着目する（Ｓ３０２）。次いで、ビット幅検出部２２３は、Ｓ３０２で着目した２つの変数のビット幅が異なるかどうか判定する（Ｓ３０３）。
【００６８】
Ｓ３０３において、ビット幅が異なると判定された場合、符号拡張部２２４は、ビット幅が小さい変数を、必要最小限に符号拡張する（Ｓ３０４）。さらに、ビット幅検出部２２３は、Ｓ３０４で符号拡張した２つの変数のビット幅が異なるかどうか判定する（Ｓ３０５）。
【００６９】
なお、後述のように動作記述情報には、各変数のビット幅が予め定義されている。この予め定義されたビット幅を、そのまま利用できる場合はＳ３０４の符号拡張は不要であり、Ｓ３０５の判定も不要である。たとえば、ビット幅が小さい変数が入力される演算について、入力と出力とのビット幅が同じである場合は、符号拡張が０である。すなわちビット幅の拡張はない。このような場合であって、かつ、Ｓ３０３で共有される変数のビット幅が違うケースにあっては、Ｓ３０４、Ｓ３０５は不要であり、ビット削減が可能となる。また、予め定義されたビット幅を、そのまま利用できない場合にＳ３０４の符号拡張を行って、対象の変数のビット幅を再度定義し、Ｓ３０５の判定が行われる。すなわち、Ｓ３０３では、予め定義された変数のビット幅を比較しており、Ｓ３０５では、符号拡張により定義された変数のビット幅を比較している。
【００７０】
Ｓ３０５において、符号拡張後にビット幅が異なると判定された場合、変数分割部２２５は、ビット幅が大きい変数を、ビット幅が小さい変数の幅に合わせて上位ビットと下位ビットにビット分割する（Ｓ３０６）。
【００７１】
次いで、レジスタ割り当て部２２６は、ビット幅が小さい変数とビット幅が大きい変数の分割後の下位ビットとを同じレジスタに割り当てる（Ｓ３０７）。次いで、レジスタ割り当て部２２６は、ビット幅が大きい変数の分割後の上位ビットを別のレジスタに割り当てる（Ｓ３０８）。
【００７２】
Ｓ３０３またはＳ３０５において、２つの変数のビット幅が同じと判定された場合、レジスタ割り当て部２２６は、着目した２つの変数を同じレジスタに割り当てる（Ｓ３０９）。
【００７３】
Ｓ３０８またはＳ３０９のレジスタ割り当ての後、レジスタ割り当て部２２６は、さらなるレジスタ共有化の余地があるかどうか判定する（Ｓ３１０）。Ｓ３１０において、レジスタ共有化の余地があると判定した場合、Ｓ３０２以降の処理を繰り返し、さらにレジスタの共有化を行う。また、Ｓ３１０において、レジスタ共有化の余地がないと判定した場合、残った変数があれば全てレジスタに割り当てて、処理を終了する（Ｓ３１１）。
【００７４】
以下、図６〜図１６の動作合成方法の具体例について、図４及び図５の各ステップに対応付けて説明する。
【００７５】
まず、動作合成方法Ｓ２００の処理が開始されると、図６に示すようにパーズが行われる（Ｓ２０１）。図６（ａ）は動作記述の例を示し、図６（ｂ）は、図６（ａ）の動作記述をパーズして生成されたＣＤＦＧを示している。
【００７６】
図６（ａ）のように、動作記述３００は、変数宣言記述部３０１と演算記述部３０２を有している。なお、動作記述情報は、動作記述の文字列からなるテキストデータである。
【００７７】
変数宣言記述部３０１では、各行に変数の型、変数のビット幅、変数名の順に記述され、変数の符号情報の有無と、ビット幅が定義されている。なお、変数は、その取りうる値を２進数表現する場合に割り当てるビット数を決める必要がある。本明細書では、このように変数の値を２進数表現するために割り当てるビット数を、ビット幅と称する。したがって、ｎビット幅（ｎ：整数）の変数Ｘは、ｎビットの２進数表現で現す変数Ｘの意味である。このように、ｎビット幅が割り当てられた変数Ｘのことを、ｎビット幅として定義された変数Ｘと称する。
【００７８】
この例では、変数ｘ４、ｙ４を４ビットの符号無し整数（ｕｉｎｔ型）の変数、変数ｘ８を８ビットの符号無し整数の変数、変数ｚ５を５ビットの符号無し整数の変数、変数ｚ９を９ビットの符号無し整数の変数として宣言（定義）している。なお、同様に、符号有り整数（ｉｎｔ型）の変数を宣言することも可能であり、その場合に定義するビットには、符号情報を示すビット（例えば最上位ビット）が含まれている。
【００７９】
演算記述部３０２では、変数宣言記述部３０１で宣言した変数を四則演算する動作（式）が記載される。この例では、変数ｘ４と変数ｙ４を加算した結果を変数ｚ５に入力し（式３０２ａ）、変数ｘ８と変数ｚ５を加算した結果を変数ｚ９に入力する（式３０２ｂ）動作が記載されている。
【００８０】
変数宣言記述部３０１と演算記述部３０２により、４ビットの変数と４ビットの変数の加算結果を５ビットの変数に格納し、さらにその５ビットの変数と８ビットの変数の加算結果を９ビットの変数として出力する動作が表される。
【００８１】
図６（ｂ）のように、動作記述３００をパーズして生成されるＣＤＦＧ３１０は、動作記述に対応して、演算内容と演算に用いる変数とが関係付けて表される。動作記述３００の演算記述部３０２の記述の式には、演算記号として「＋」があるため、加算（加算器）を示す記号と各変数とを接続して関連付けられる。
【００８２】
この例では、加算１の演算が、式３０２ａに対応しており、４ビットの変数ｘ４と４ビットの変数ｙ４を加算して５ビットの変数ｚ５へ出力することを表している。そして、加算２の演算が、式３０２ｂに対応しており、５ビットの変数ｚ５と８ビットの変数ｘ８を加算して９ビットの変数ｚ９へ出力することを表している。なお、ここでは符号無しの変数の例を示しているが、符号ありの変数の場合には、ビット幅を必要最小限だけ増やし、同様にＣＤＦＧを生成することができる
【００８３】
図７は、このＣＤＦＧをデータとして記憶・処理するための内部表現情報の一例を示している。この内部表現情報３２０は、ＣＤＦＧを構成する変数や演算等のノード（要素）を表す構造体の集合である。構造体は、各ノードを特定するため、例えば、「種類」、「名称」、「ビット幅」、「接続関係」等のパラメータを有している。構造体は、「種類」に応じて、複数通りのものがある。この例では、「外部入力変数」、「加算」、「中間変数」、「外部出力変数」の４通りの構造体があり、ノード間のつながりは、構造体中に「接続先」や「接続元」を指定する領域を設けて表現する。
【００８４】
図７の内部表現情報３２０は、図６のＣＤＦＧ３１０の各ノードを表している。構造体３２１は変数ｘ４、構造体３２２は変数ｙ４、構造体３２３は加算１、構造体３２４は変数ｚ５、構造体３２５は変数ｘ８、構造体３２６は加算２、構造体３２７は変数ｚ９をそれぞれ表している。
【００８５】
図６でパーズした後、図８（ａ）に示すようにスケジューリングが行われる（Ｓ２０２）。図８（ａ）は、図６のＣＤＦＧ３１０に対しスケジューリングを行った後のＣＤＦＧ３１１を示している。
【００８６】
スケジュール処理では、各演算処理の順序に従って、各演算処理を実行する制御ステップが決定される。図６（ａ）（ｂ）から理解できるように、変数ｘ４と変数ｙ４の加算の後に、変数ｘ８と変数ｚ５を加算する必要がある。このため、２つの加算処理を２つのステップで実行することにする。
【００８７】
すなわち、図８（ａ）のように、２つの加算を別のステップに区切り、ステップ１において、変数ｘ４と変数ｙ４とを加算して変数ｚ５へ出力する加算１の処理を実行し、次のステップ２において、変数ｚ５と変数ｘ８とを加算して変数ｚ９を出力する加算２の処理を実行するようにスケジュールする。
【００８８】
図８（ａ）でスケジューリングした後、Ｓ２０３〜Ｓ２０４のアロケーションが行われ、記憶ユニットのアロケーションでは、図８（ｂ）に示すようにライフタイムが計算される（Ｓ３０１）。図８（ｂ）は、図８（ａ）でスケジュールされたＣＤＦＧ３１１の各変数のライフタイムを示すライフタイムテーブル３３０である。なお、ここでは、ライフタイムを示す図において、主にステップ１及びステップ２を図示し、その前後のステップについては省略しているが、実際にはステップ１及びステップ２を繰り返すことになる。
【００８９】
ライフタイムの計算では、ＣＤＦＧで表される制御ステップと演算及び変数との関係から、変数ごとに、どの制御ステップからどの制御ステップまでの期間、値を保持する必要があるかを計算する。
【００９０】
この例では、変数ｘ４は、ステップ１の加算１の入力として使用され、加算１の後は使用されないため、ステップ１より前のステップからステップ１までがライフタイムとなる。変数ｙ４も同様に、変数ｘ４と同じライフタイムとなる。
【００９１】
変数ｘ８は、ステップ２の加算２の入力として使用され、加算２の後は使用されないため、ステップ１からステップ２までがライフタイムとなる。変数ｚ５は、ステップ１の加算１により値が確定して、ステップ２の加算２の入力として使用され、加算２の後は使用されないため、ステップ１からステップ２までがライフタイムとなる。
【００９２】
変数ｚ９は、最終的な演算結果が保持される変数であり、ここでは、状態に関係なく出力値を常に保持するものとする。したがって、変数ｚ９は、ステップ１より前のステップから、ステップ２より後のステップまで、全期間がライフタイムとなる。
【００９３】
図９は、このライフタイムをデータとして記憶・処理するためのライフタイム情報の一例を示している。このライフタイム情報は、各変数のライフタイムを表すテーブル構造体３４０である。テーブル構造体３４０は、ライフタイムの名称、期間を特定するため、例えば、「変数名」、「始点」、「終点」の欄を有し、さらに、レジスタの割り当てを特定するため「割当先」の欄を有している。
【００９４】
「始点」がＮＵＬＬの場合、「初期ステップ(ｓｔｅｐ１)以前からライフタイムあり」を表しており、「終点」がＮＵＬＬの場合、「最終ステップ(ｓｔｅｐ２)以後までライフタイムあり」を表している。「割当先」がＮＵＬＬは、割当先レジスタが未決定を表しており、割当先レジスタが決まった場合、「割当先」の欄にレジスタを記憶する。
【００９５】
ライフタイムは、連続する期間毎に記憶され、同じ変数が複数のライフタイムを有する場合には、複数のライフタイムが登録される。
【００９６】
図９では、テーブル構造体３４０は、ライフタイムテーブル３３１に対応しており、変数ｘ４、ｙ４、ｘ８、ｚ５、ｚ９の各ライフタイム（ａ）〜（ｆ）が、テーブル構造体３４０の各行に登録される。
【００９７】
このテーブル構造体３４０では、（ａ）が変数ｘ４の１つ目のライフタイム、（ｂ）が変数ｘ４の２つ目のライフタイム、（ｃ）が変数ｙ４のライフタイム、（ｄ）が変数ｘ８のライフタイム、（ｅ）が変数ｚ５のライフタイム、（ｆ）が変数ｚ６のライフタイムをそれぞれ表している。
【００９８】
図８（ｂ）でライフタイムを計算した後、図１０（ａ）に示すように２つの変数が着目される（Ｓ３０２）。図１０（ａ）は、図８（ｂ）と同じライフタイムテーブル３３０である。
【００９９】
ライフタイムの始点と終点から、ライフタイムが各制御ステップで重なっているか解析する。図１０（ａ）では、まず、変数ｘ４と変数ｚ５でライフタイムが重ならないため、変数ｘ４と変数ｚ５に着目する。
【０１００】
図１０（ａ）で２つの変数ｘ４とｚ５に着目した後、ビット幅の比較が行われ（Ｓ３０３）、変数ｘ４とｚ５はビット幅が異なるため、ビット幅が小さい変数ｘ４を必要最小限に符号拡張して５ビットとする（Ｓ３０４）。
【０１０１】
この符号拡張では、着目した変数が入力となっている演算に着目し、その演算の出力のビット幅に合わせて符号拡張する。上記のように、演算の入力と出力のビット幅が同じ場合、符号拡張は不要であり、演算の入力と出力のビット幅が異なる場合、出力のビット幅に合わせて符号拡張したビット幅を変数のビット幅として再定義する。
【０１０２】
例えば、４ビットの変数ｘ４が、出力ビット幅５ビットの加算演算の入力となっている場合、出力のビット幅５ビットに合わせるため、４ビットの変数ｘ４を１ビット符号拡張し、５ビットにする。例えば、５ビットの変数ｚ５が、出力ビット幅９ビットの加算演算の入力となっている場合、出力のビット幅９ビットに合わせるため、５ビットの変数ｚ５を４ビット符号拡張し、９ビットにする。
【０１０３】
着目した変数と異なる入力側には、一般に任意の値が入る可能性がある。それを考慮し、加算、減算の場合は一方の入力に０が入るケース、乗算の場合は一方の入力に１が入るケースをそれぞれ考えた場合、着目した変数の値が丸々、演算の出力に反映されることになる。
【０１０４】
このとき、もし、演算の出力のビット幅よりも、着目した変数のビット幅の方が小さいと、足りない上位ビットの値は未確定であり、ＲＴＬ生成後の接続関係によって不安定な値（ゴミ）が入る可能性があるため、正しい演算結果が得られない。このため、本実施形態では、予め、必要ビット数の符号拡張を行うことで、正確な動作を可能にしている。
【０１０５】
図１０（ａ）で、変数ｘ４を符号拡張した後、さらにビット幅の比較が行われ（Ｓ３０５）、拡張した変数ｘ４と変数ｚ５は同じ５ビットであるため、図１０（ｂ）に示すように、着目した２つの変数に同じレジスタを割り当てる（Ｓ３０９）。図１０（ｂ）は、図１０（ａ）のライフタイムテーブル３３０について、変数ｘ４とｙ４にレジスタｒ１を割り当てたライフタイムテーブル３３２である。
【０１０６】
すなわち、ライフタイムが重ならず、かつ、同じビット幅の変数ｘ４とｚ５を、ライフタイムテーブル上で連続するように表し、この連続する変数ｘ４とｚ５に、変数ｘ４及びｚ５と同じ５ビットのレジスタｒ１を割り当てる。
【０１０７】
図１０（ｂ）でレジスタｒ１を割り当てた後、さらなるレジスタの共有化の余地があるかどうか判定し（Ｓ３１０）、ライフタイムの重ならない変数があるため、図１１（ａ）に示すようにさらに２つの変数が着目される（Ｓ３０２）。図１１（ａ）は、図１０（ｂ）と同じライフタイムテーブル３３２である。図１１（ａ）では、変数ｙ４と変数ｘ８でライフタイムが重ならないため、変数ｙ４と変数ｘ８に着目する。
【０１０８】
図１１（ａ）で２つの変数ｙ４とｘ８に着目した後、ビット幅の比較が行われ（Ｓ３０３）、ビット幅が小さい変数ｘ４を必要最小限に符号拡張して５ビットとする（Ｓ３０４）。さらにビット幅の比較が行われ（Ｓ３０５）、拡張した変数ｙ４は５ビット、変数ｘ８は８ビットであり、ビット幅が異なるため、図１１（ｂ）に示すように、大きいビット幅の変数ｘ８を分割し（Ｓ３０６）、小さいビット幅の変数ｙ４と分割したｘ８の下位ビットとに同じレジスタｒ２を割り当て（Ｓ３０７）、分割したｘ８の上位ビットに別のレジスタｒ３を割り当てる（Ｓ３０８）。図１１（ｂ）は、図１１（ａ）のライフタイムテーブル３３２について、変数ｙ４とｘ８にレジスタｒ２、ｒ３を割り当てたライフタイムテーブル３３３である。
【０１０９】
すなわち、着目した変数ｙ４とｘ８は、ライフタイムが重ならず、かつ、ビット幅が異なるため、大きいビット幅の変数ｘ８を、上位３ビットと下位５ビットに分割する。小さいビット幅の変数ｙ４と変数ｘ８の下位５ビットを、ライフタイムテーブル上で連続するように表し、この連続する変数ｙ４と変数ｘ８の下位ビットに、５ビットのレジスタｒ２を割り当てる。さらに、変数ｘ８の上位ビットにレジスタｒ３を割り当てる。
【０１１０】
図１１（ｂ）でレジスタｒ２、ｒ３を割り当てた後、さらなるレジスタの共有化余地があるかどうか判定する（Ｓ３１０）。ライフタイムの重ならない変数は無いため、図１２（ａ）に示すように、残りの変数ｚ９に着目し、図１２（ｂ）に示すように、残りの変数ｚ９に９ビットのレジスタｒ４を割り当てる（Ｓ３１１）。
【０１１１】
図１２（ｂ）のライフタイムテーブル３３４により、レジスタ（記憶ユニット）のアロケーションが完了する。このレジスタのアロケーションに合わせて、加算器（機能ユニット）、マルチプレクサ（通信ユニット）のアロケーションが行われる。これらのアロケーションが完了すると、図１３に示すような、データパスのネットリストが生成される（Ｓ２０６）。
【０１１２】
ライフタイムテーブル３３４により割り当てられたレジスタｒ１、ｒ２、ｒ３、ｒ４を加算器Ａ１で接続する。ライフタイムテーブル３３４の制御ステップに応じて共有のレジスタｒ１、ｒ２に入力する変数を切り替えるためにマルチプレクサＭ１、Ｍ２を、レジスタｒ１、ｒ２に接続する。また制御ステップに応じてレジスタｒ３、ｒ４に入力する変数のタイミングを制御するためマルチプレクサＭ３、Ｍ４を、レジスタｒ３、ｒ４に接続する。
【０１１３】
すなわち、図１３に示すように、このデータパス４００は、変数ｘ４と加算器Ａ１の出力である変数ｚ５のいずれかを切り替えてレジスタｒ１へ出力するマルチプレクサＭ１、マルチプレクサＭ１が選択した変数を保持するレジスタｒ１、変数ｙ４と変数ｘ８の下位ビットのいずれかを切り替えてレジスタｒ２へ出力するマルチプレクサＭ２、マルチプレクサＭ２が選択した変数を保持するレジスタｒ２、変数ｘ８の上位ビットをレジスタｒ３へ出力するマルチプレクサＭ３、マルチプレクサＭ３を介した変数ｘ８の上位ビットを保持するレジスタｒ３、レジスタｒ１の値と、レジスタｒ２及びｒ３の値とを加算する加算器Ａ１、加算器Ａ１の出力をレジスタｒ４へ出力するマルチプレクサＭ４、マルチプレクサＭ４を介した加算器Ａ１の出力を変数ｚ９として保持し出力するレジスタｒ４を備えている。
【０１１４】
図１３のデータパスのネットリストが生成され、さらに、このデータパスを制御ステップに応じて制御する制御回路用テーブルが生成される（Ｓ２０６）。例えば、図１２のライフタイムテーブル３３４から、各制御ステップで使用するレジスタ及び変数が決定するため、これに合わせてマルチプレクサを制御するための制御回路用テーブルを生成する。例えば、制御回路用テーブルには、制御ステップと、そのタイミングで制御されるマルチプレクサとが対応付けられている。
【０１１５】
そして、図１３のデータパスのネットリストと制御回路用テーブルが生成されると、図１４に示すような、データパス４００と制御回路４１０を合成した合成回路４２０のＲＴＬが出力される（Ｓ２０７）。
【０１１６】
制御回路用テーブルに基づいて、制御ステップ１，２に対応する制御信号ｓ１、ｓ２を出力する制御回路４１０を生成する。そして、この制御信号ｓ１、ｓ２をデータパス４００のマルチプレクサに供給するように接続する。さらに、制御回路４１０及びデータパス４００にクロックを供給する。
【０１１７】
すなわち、図１４に示すように、この合成回路４２０は、データパス４００と制御回路４１０を有している。
【０１１８】
データパス４００の構成は図１３と同様である。また、データパス４００では、クロックが、レジスタｒ１、ｒ２、ｒ３、ｒ４にそれぞれ供給される。さらに、制御信号ｓ１、ｓ２が、マルチプレクサＭ１、Ｍ２、Ｍ３、Ｍ４にそれぞれ供給される。
【０１１９】
制御回路４１０は、クロックのタイミングごとに"０"と"１"を繰り返す制御信号ｓ２を生成するレジスタｒ５、制御信号ｓ２を反転した制御信号ｓ１を生成するインバータＩＮ１を備えている。
【０１２０】
制御信号ｓ１とｓ２により、ステップ１とステップ２が切り替えられる。例えば、制御信号ｓ１によりステップ１が選択され、制御信号ｓ２によりステップ２が選択される。
【０１２１】
制御信号ｓ１が"１"、制御信号ｓ２が"０"の場合、マルチプレクサＭ１が変数ｘ４を選択してレジスタｒ１に保持され、マルチプレクサＭ２が変数ｙ４を選択してレジスタｒ２に保持され、加算器Ａ１により変数ｘ４と変数ｙ４が加算されて変数ｚ５が出力される。
【０１２２】
次に、制御信号ｓ１が"０"、制御信号ｓ２が"１"の場合、マルチプレクサＭ１が変数ｚ５を選択してレジスタｒ１に保持され、マルチプレクサＭ２が変数ｘ８の下位５ビットを選択してレジスタｒ２に保持され、マルチプレクサＭ３が変数ｘ８の上位３ビットを選択してレジスタｒ３に保持され、加算器Ａ１により変数ｚ５と変数ｘ８が加算される。さらに、マルチプレクサＭ４が加算器Ａ１の出力を選択してレジスタｒ４に保持され、加算器Ａ１の出力結果が変数ｚ９として出力される。
【０１２３】
図１５及び図１６は、図１４の合成回路４２０をＶｅｒｉｌｏｇ−ＨＤＬで記述したＲＴＬ記述の例である。ＲＴＬは、階層構造のモジュール単位に記述されている。例えば、ＲＴＬ情報記憶部２１０に、ＲＴＬ記述のテキストデータが格納される。
【０１２４】
この例では、まず、最上位階層であるトップのトップモジュール記述５０１が記述され、次に、トップモジュールの下位である制御回路の制御回路モジュール記述５０２が記述され、次に、トップモジュールの下位であるデータパスのデータパスモジュール記述５０３が記述されている。制御回路モジュール記述５０２は、図１４の制御回路４１０に対応しており、データパスモジュール記述５０３は、図１４のデータパス４００に対応している。
【０１２５】
トップモジュール記述５０１には、データパスの入出力信号が記述され（５０１ａ）、制御回路の入出力信号が記述されている（５０１ｂ）。
【０１２６】
制御回路モジュール記述５０２には、レジスタｒ５と制御信号ｓ２の関係が記述され（５０２ａ）、レジスタｒ５の反転信号と制御信号ｓ１の関係が記述され（５０２ｂ）、クロックとレジスタｒ５の関係が記述されている（５０２ｃ）。
【０１２７】
データパスモジュール記述５０３には、変数ｘ４、ｙ４、ｘ８、ｚ９のビット幅が記述され（５０３ａ）、レジスタｒ１、ｒ２、ｒ３、ｒ４のビット幅が記述され（５０３ｂ）、レジスタｒ１、ｒ２、ｒ３と加算器の関係が記述され（５０３ｃ）、クロックとレジスタｒ１、ｒ２、ｒ３、ｒ４の関係が記述され（５０３ｄ）、制御信号ｓ１、ｓ２とレジスタｒ１、ｒ２、ｒ３、ｒ４の関係が記述されている（５０３ｅ）。
【０１２８】
ここで、本発明の実施の形態１に係る動作合成方法と従来の動作合成方法とを比較するために、図３２を用いて、従来の動作合成方法によりレジスタをアロケーションする参考例について説明する。
【０１２９】
図３２（ａ）は、図８のライフタイムテーブル３３０に対し、従来の動作合成方法によりレジスタを割り当てたライフタイムテーブル９２０を示している。
【０１３０】
従来の動作合成方法では、ライフタイムの重ならない変数であることのみがレジスタを共有化する条件である。ここでは、変数ｘ４と変数ｚ５とが重ならない２つの変数であり、また、変数ｙ４と変数ｘ８とが重ならない２つの変数である。
【０１３１】
そうすると、図３２（ａ）に示すように、ライフタイムの重ならない変数に一つのレジスタを割り当てる。すなわち、変数ｘ４と変数ｚ５に、ビット幅が大きい変数ｚ５に合わせた５ビットのレジスタｒ１を割り当てる。変数ｙ４と変数ｘ８に、ビット幅が大きい変数ｘ８に合わせた８ビットのレジスタｒ２を割り当てる。変数ｚ９は、共有化できないため、変数ｚ９に合わせた９ビットのレジスタｒ３を割り当てる。
【０１３２】
図３２（ｂ）は、図３２（ａ）のライフタイムテーブル９２０から生成されたデータパス９３０を示している。
【０１３３】
ライフタイムテーブル９２０により割り当てられたレジスタｒ１、ｒ２、ｒ３を加算器Ａ１で接続する。ライフタイムテーブル９２０の制御ステップに応じて共有のレジスタｒ１、ｒ２に入力する変数を切り替えるためにマルチプレクサＭ１、Ｍ２を、レジスタｒ１、ｒ２に接続する。また制御ステップに応じてレジスタｒ３に入力する変数のタイミングを制御するためマルチプレクサＭ３を、レジスタｒ３に接続する。
【０１３４】
すなわち、図３２（ｂ）に示すように、このデータパス９３０は、変数ｘ４と加算器Ａ１の出力である変数ｚ５のいずれかを切り替えてレジスタｒ１へ出力するマルチプレクサＭ１、マルチプレクサＭ１が選択した変数を保持するレジスタｒ１、変数ｙ４と変数ｘ８との入力のいずれかを切り替えてレジスタｒ２へ出力するマルチプレクサＭ２、マルチプレクサＭ２が選択した変数を保持するレジスタｒ２、レジスタｒ１の値とレジスタｒ２の値とを加算する加算器Ａ１、加算器Ａ１の出力をレジスタｒ３へ出力するマルチプレクサＭ３、マルチプレクサＭ３を介した加算器Ａ１の出力を変数ｚ９として保持し出力するレジスタｒ３を備えている。
【０１３５】
図３２のように、従来の動作合成方法によって生成された回路では、ビット幅の異なる値が共有化された後は、ビット幅の大きな変数に合わせて生成されたレジスタの全ビットをアクセスする回路構造となる。このため、下位ビットのみアクセスして演算を行えばよいタイミングにおいても、意味のない上位ビットのために無駄な電力を消費するという問題があった。
【０１３６】
例えば、図３２の回路では、４ビットの変数ｘ４と４ビットの変数ｙ４との加算結果の変数ｚ５は、５ビットのレジスタｒ１に格納されるため、加算器の入力の６ビット目以上は、どのような値をとっても、レジスタｒ１の値が変わることはない。しかしながら、変数ｙ４の値は、８ビットに拡張された上で、８ビットの変数ｘ８と切り替えてアクセスされるため、意味を持たない６ビット目以上のビットに対しても、切り替えが生じ、無駄な電力を消費することになる。
【０１３７】
また、図３２の回路では、４ビットの変数ｙ４の値をレジスタｒ２に取り込む際、５ビット目以上のビットには明示的に"０"が代入される記述となる。例えば、この後の処理で、レジスタｒ２に対してビット単位でクロックゲーティング回路を構成したとしても、変数ｙ４の値をレジスタｒ２に取り込むタイミングでも６ビット目以上にも代入がなされているため、クロックゲーティングの対象とはできず、電力低減の機会が減ることになる。
【０１３８】
このように、従来の動作合成方法では、ビット幅の大きい変数に合わせたビット幅でレジスタを共有化するため、ビット幅の小さい変数にとって未使用のビットが発生することから、共有化するレジスタおよびその入力を切り替えるマルチプレクサのビットが無駄に大きいという問題があった。これにより回路面積が大きくなるという問題も生じる。
【０１３９】
近年、半導体の微細化に伴い、リーク電流によるスタティックな電力消費が無視できなくなってきている。リーク電流は、回路面積が大きいほど大きくなる傾向にあるため、面積が縮小できれば、スタティックな電力消費の削減にもつながる。従来の動作合成方法では、レジスタやマルチプレクサのビットが無駄に大きくなることから、このようなスタティックな電力消費という観点でも、最適化の余地が残るものであった。
【０１４０】
また、従来の動作合成方法では、４ビットの演算の時でも、８ビットの切り替えが生じ、無駄な電力を消費することになる。すなわち、従来の動作合成方法では、ビット幅の小さい変数の値を格納する場合であっても、未使用の無駄なビットを含む、レジスタの全入力ビットを切り替えるためのマルチプレクサを生成しており、これは、切り替えのために消費されるダイナミックな電力消費を削減するという観点においても、最適化の余地が残るものであった。
【０１４１】
さらに、従来の動作合成方法では、未使用ビットにも明示的に値を代入しているため、クロックゲーティングの余地がなく、ダイナミック電力を低減することができないという問題があった。
【０１４２】
これに対し、本実施形態では、上記図１２のライフタイムテーブル３３４のように、ビット幅の異なる変数に対しレジスタ共有化する場合、大きいビット幅の変数を分割して、小さいビット幅の変数に合わせたレジスタを割り当てて共有化し、残りのビットには別のレジスタを割り当てるようにした。
【０１４３】
これにより、図１３のように、変数ｙ４と変数ｘ８との共有化において、ビット幅の小さい変数ｙ４に合わせたビット幅（５ビット）でレジスタが共有されるため、レジスタの入力を切り替えるマルチプレクサのビット幅も、図３２と比べて従来の８ビットよりも小さい５ビットにすることができる。したがって、切り替えるビット数が減る分、マルチプレクサの面積が小さくなり、それに比例してリーク電流も少なく出来るため、スタティックな電力消費を低減することができる。また、マルチプレクサの切り替え時の未使用ビットの切り替えを削減することができ、ダイナミックな消費電力を低減することができる。
【０１４４】
また、変数ｘ８を分割して残った上位ビットの部分は、共有のレジスタとは別のレジスタｒ３に割り当てられる。このため、変数ｙ４の値の取り込みタイミングとは無関係にクロックゲーティングができるようになり、ダイナミックな消費電力をより一層低減することが可能となる。
【０１４５】
（本発明の実施の形態２）
以下、図面を参照して本発明の実施の形態２ついて説明する。図１７は、本発明の実施の形態２に係る動作合成装置の機能構成を示している。
【０１４６】
図１７の動作合成装置２００は、図２の構成と比べて、ＲＴＬ出力部のみが異なっている。その他の構成は同様である。すなわち、本実施形態の動作合成装置２００は、実施の形態１のＲＴＬ出力部２０９に代えて、クロックゲーティング及びＲＴＬ出力部２１１を有している。
【０１４７】
クロックゲーティング及びＲＴＬ出力部２１１は、制御回路用テーブル記憶部２０７に記憶された制御回路用テーブルと、ネットリスト記憶部２０８に記憶されたデータパスのネットリストとに基づいて、クロックゲーティングを含む合成回路のＲＴＬ情報を生成し、出力する。
【０１４８】
図１８は、クロックゲーティング及びＲＴＬ出力部２１１が生成した合成回路４２０の例である。図１８の合成回路４２０は、図１４の構成と比べて、制御回路４１０は同じ構成であり、データパス４００は、マルチプレクサＭ３、Ｍ４に代えて、クロックゲーティングＬ１、Ｌ２を有している。
【０１４９】
このクロックゲーティングＬ１，Ｌ２は論理和回路で構成され、クロックゲーティングＬ１，Ｌ２は、レジスタｒ３、ｒ４に供給されるクロックの変動を抑える。クロックゲーティングＬ１は、クロックと制御信号ｓ２とを論理和演算してレジスタｒ３のクロック端子へ供給する。クロックゲーティングＬ２は、クロックと制御信号ｓ１とを論理和演算してレジスタｒ４のクロック端子へ供給する。
【０１５０】
図１９のタイミングチャートは、図１８の合成回路４２０の動作を示している。制御信号ｓ１、ｓ２は、クロックごとのタイミングで"０"と"１"を交互に繰り返し、これに応じてステップ１とステップ２が繰り返される。
【０１５１】
ステップ１では、レジスタｒ１に変数ｘ４が保持され、レジスタｒ２に変数ｙ４が保持され、加算器Ａ１が変数ｘ４と変数ｙ４とを加算し、変数ｚ５を出力する。ステップ２では、レジスタｒ１に変数ｚ５が保持され、レジスタｒ２に変数ｘ８の下位ビットが保持され、レジスタｒ３に変数ｘ８の上位ビットが保持され、加算器Ａ１が変数ｚ５と変数ｘ８の上位ビット及び下位ビットとを加算し、変数ｚ９を出力する。
【０１５２】
ここで、レジスタｒ３では、ステップ２においてのみ変数ｘ８を使用するため、ステップ１のタイミングではクロックをゲーティングしてレジスタｒ３をラッチ動作させず、ステップ２のみクロックを供給してレジスタｒ２をラッチ動作させる。なお、図１４の構成のようにクロックゲーティングしない場合には、レジスタｒ３は、変数ｘ８と"０"とをクロック毎に交互に格納する。
【０１５３】
また、レジスタｒ４では、ステップ２の次のステップにおいてのみ変数ｚ９の値が確定するため、ステップ２のタイミングではクロックをゲーティングしてレジスタｒ４をラッチ動作させず、ステップ２の次のステップ（ここではステップ１）のみクロックを供給してレジスタｒ４をラッチ動作させる。図１９のように、レジスタｒ３、ｒ４に供給されるクロックが半分になるため、レジスタｒ３、ｒ４のダイナミックな消費電力を半分に減らすことができる。
【０１５４】
このように、本実施形態では、変数を保持するレジスタにクロックゲーティングを行うことで、消費電力を低減することができる。特に、従来、レジスタ共有によりクロックゲーティングが不可能な場合があったが、実施の形態１で説明したように、ビット幅の大きい変数を上位ビットと下位ビットに分割して、別のレジスタに割り当てているため、上位ビットのレジスタをクロックゲーティングができるようになり、消費電力を確実に低減することができる。
【０１５５】
（本発明の実施の形態３）
以下、図面を参照して本発明の実施の形態３ついて説明する。実施の形態１では、記憶ユニットのアロケーション処理において、ライフタイムの重ならない２つの変数に着目して、レジスタの割り当てを行った。これに対し、本実施形態では、ライフタイムの重ならない２以上の変数に着目して、レジスタを割り当てる。記憶ユニットのアロケーション以外については、実施の形態１，２と同様である。
【０１５６】
図２０は、本発明の実施の形態３に係る記憶ユニットのアロケーション処理（Ｓ２０４）の流れを示している。
【０１５７】
図に示されるように、まず、ライフタイム計算部２２１は、ＣＤＦＧ上で状態を横切る各変数についてライフタイムを計算し（Ｓ４０１）、変数選択部２２２は、ライフタイムの重ならない２つ以上の変数及びレジスタに着目する（Ｓ４０２）。次いで、ビット幅検出部２２３は、着目した全ての変数のビット幅が同じかどうか判定する（Ｓ４０３）。
【０１５８】
Ｓ４０３において、ビット幅が異なると判定された場合、変数選択部２２２は、着目した変数の中から２つの変数を選ぶ（Ｓ４０４）。２つの変数を選んだ後は、実施の形態１と同様に、図５のＳ３０３〜Ｓ３０８の処理を行う。
【０１５９】
すなわち、選択した２つの変数のビット幅が異なるかどうか判定し（Ｓ３０３）、ビット幅が異なる場合、ビット幅が小さい変数を必要最小限に符号拡張し（Ｓ３０４）、符号拡張した２つの変数のビット幅が異なるかどうか判定し（Ｓ３０５）、ビット幅が異なる場合、ビット幅が大きい変数をビット幅が小さい変数の幅に合わせて上位ビットと下位ビットにビット分割し（Ｓ３０６）、ビット幅が小さい変数とビット幅が大きい変数の下位ビットとを同じレジスタに割り当て（Ｓ３０７）、ビット幅が大きい変数の上位ビットを別のレジスタに割り当てる（Ｓ３０８）。
【０１６０】
Ｓ４０３において、着目した全ての変数のビット幅が同じ場合、Ｓ３０３、Ｓ３０５において、選択した２つの変数のビット幅が同じ場合、着目した全ての変数もしくは選択した２つの変数に、同じレジスタを割り当てる（Ｓ４０５）。
【０１６１】
Ｓ３０８またはＳ４０５のレジスタ割り当ての後、レジスタ割り当て部２２６は、割り当てたレジスタと残った変数とを着目対象とする。
【０１６２】
次いで、レジスタ割り当て部２２６は、共有化の余地があるかどうか判定する（Ｓ４０７）。現在着目している複数の変数において、割り当てたレジスタも含めて、共有化する余地があるかどうか判定する。Ｓ４０７において、共有化の余地があると判定された場合、Ｓ４０３以降の処理を繰り返し、さらに２つの変数を選択して共有化を行う。
【０１６３】
Ｓ４０７において、共有化の余地がないと判定された場合、レジスタ割り当て部２２６は、さらなるレジスタ共有化の余地があるかどうか判定する（Ｓ４０８）。Ｓ４０８において、レジスタ共有化の余地があると判定された場合、Ｓ４０２以降の処理を繰り返す。また、Ｓ４０８において、レジスタ共有化の余地がないと判定された場合、レジスタ割り当て部２２６は、残った変数があれば全てレジスタに割り当てて、処理を終了する（Ｓ４０９）。
【０１６４】
このように、本実施形態では、記憶ユニットのアロケーションにあたり、ライフタイムの重ならない２つ以上の変数に着目し、ビット幅が異なる場合は、２つの変数を選択してレジスタの割り当てを行うようにした。これにより、ライフタイムの重ならない変数が２つ以上ある場合でも、実施の形態１と同様にレジスタを共有化することができる。
【０１６５】
（本発明の実施の形態４）
以下、図面を参照して本発明の実施の形態４ついて説明する。実施の形態３では、記憶ユニットアロケーション処理において、ライフタイムの重ならない２つ以上の変数に着目し、さらに２つの変数を選択してレジスタの割り当てを行った。これに対し、本実施形態では、ライフタイムの重ならない２以上の変数に着目して、その着目した２つ以上の変数に対しレジスタを割り当てる。記憶ユニットのアロケーション以外については、実施の形態１，２と同様である。
【０１６６】
図２１は、本発明の実施の形態４に係る記憶ユニットのアロケーション処理（Ｓ２０４）の流れを示している。
【０１６７】
図に示されるように、まず、ライフタイム計算部２２１は、ＣＤＦＧ上で状態を横切る各変数についてライフタイムを計算し（Ｓ５０１）、変数選択部２２２は、ライフタイムの重ならない２つ以上の変数及びレジスタに着目する（Ｓ５０２）。次いで、ビット幅検出部２２３は、着目した変数が全て同じビット幅かどうか判定する（Ｓ５０３）。
【０１６８】
Ｓ５０３において、全ての変数のビット幅が同じではないと判定された場合、符号拡張部２２４は、ビット幅が最大の変数以外の変数を、必要最小限に符号拡張する（Ｓ５０４）。次いで、ビット幅検出部２２３は、符号拡張後の着目した変数が全て同じビット幅かどうか判定する（Ｓ５０５）。
【０１６９】
Ｓ５０５において、全ての変数のビット幅が同じではないと判定された場合、変数分割部２２５は、ビット幅が最小の変数のビット幅に合わせて、その他の変数を上位ビットと下位ビットにビット分割する（Ｓ５０６）。次いで、レジスタ割り当て部２２６は、ビット幅が最小の変数とその他の変数の下位ビットとを同じレジスタに割り当てる（Ｓ５０７）。
【０１７０】
次いで、レジスタ割り当て部２２６は、分割したその他の変数の上位ビットを新たな着目対象とする（Ｓ５０８）。その後、Ｓ５０５以降を繰り返し、分割した残りの変数に対し、レジスタの割り当てを行う。
【０１７１】
Ｓ５０３またはＳ５０５において、着目した変数が全て同じビット幅である場合、レジスタ割り当て部２２６は、着目した全ての変数を同じレジスタに割り当てる（Ｓ５０９）。
【０１７２】
次いで、レジスタ割り当て部２２６は、さらなるレジスタ共有化の余地があるかどうか判定する（Ｓ５１０）。Ｓ５１０において、レジスタ共有化の余地があると判定された場合、Ｓ５０２以降の処理を繰り返す。また、Ｓ５１０において、レジスタ共有化の余地がないと判定された場合、レジスタ割り当て部２２６は、残った変数があれば全てレジスタに割り当てて、処理を終了する（Ｓ５１１）。
【０１７３】
次に、図２２〜図２７を用いて、本発明の実施の形態４に係る動作合成方法の具体例について説明する。
【０１７４】
まず、動作合成方法Ｓ２００の処理が開始されると、図２２（ａ）の動作記述６００をパーズして、図２２（ｂ）のＣＤＦＧが生成される（Ｓ２０１）。
【０１７５】
この動作記述６００では、変数宣言記述部６０１に変数ｘ４、ｙ４、ｘ８、ｚ５、ｚ９、ｘ１６、ｚ１７が定義され、演算記述部６０２に、これらの変数を使用した式６０２ａ、式６０２ｂ、式６０２ｃが記述されている。
【０１７６】
動作記述６００をパーズすると、図２２（ｂ）に示すように、加算１の演算が、式６０２ａに対応しており、４ビットの変数ｘ４と４ビットの変数ｙ４を加算して５ビットの変数ｚ５へ出力することを表し、加算２の演算が、式６０２ｂに対応しており、５ビットの変数ｚ５と８ビットの変数ｘ８を加算して９ビットの変数ｚ９へ出力することを表し、加算３の演算が、式６０２ｃに対応しており、９ビットの変数ｚ９と１６ビットの変数ｘ１６を加算して１７ビットの変数ｚ１７へ出力することを表すＣＤＦＧ６１０が生成される。
【０１７７】
次に、図２３（ａ）に示すように、図２２（ｂ）のＣＤＦＧに対し制御ステップに区切ってスケジューリングが行われ、スケジューリングのＣＤＦＧ６１１が生成される（Ｓ２０２）。
【０１７８】
この例では、ステップ１において、変数ｘ４と変数ｙ４とを加算して変数ｚ５へ出力する加算１の処理を実行し、次のステップ２において、変数ｚ５と変数ｘ８とを加算して変数ｚ９を出力する加算２の処理を実行し、次のステップ３において、変数ｚ９と変数ｘ１６とを加算して変数ｚ１７を出力する加算３の処理を実行するようにスケジュールする。
【０１７９】
次に、図２３（ａ）のスケジューリング後のＣＤＦＧ６１１から、各変数のライフタイムを計算し、図２３（ｂ）に示すライフタイムテーブル６２０を生成する（Ｓ５０１）。
【０１８０】
この例では、変数ｘ４、ｙ４は、ステップ１より前のステップからステップ１までがライフタイムであり、変数ｘ８、ｚ５は、ステップ１からステップ２までがライフタイムであり、変数ｘ１６、ｚ９は、ステップ２からステップ３までがライフタイムであり、変数ｚ１７は、全期間がライフタイムである。
【０１８１】
次に、図２４（ａ）に示すように、変数ｘ４と変数ｚ５と変数ｚ９とでライフタイムが重ならないため、変数ｘ４、変数ｚ５、変数ｚ９に着目する（Ｓ５０２）。変数ｘ４は４ビットであり、変数ｚ５は５ビットであり、変数ｚ９は９ビットであり、ビット幅が異なるため、ビット幅が最大ではない、変数ｘ４、変数ｚ５の変数を最小限に符号拡張し５ビットと９ビットとする（Ｓ５０４）。ビット幅最小の変数ｘ４のビット幅５に合わせて、変数ｚ５を上位４ビットと下位５ビットに分割し、変数ｚ９を上位４ビットと下位５ビットに分割する（Ｓ５０６）。
【０１８２】
そして、図２４（ｂ）に示されるように、ビット幅最小の変数ｘ４と、変数ｚ５の下位ビット、変数ｚ９の下位ビットに同じレジスタｒ１を割り当てる（Ｓ５０７）。さらに、分割した変数ｚ５の上位４ビットと、変数ｚ９の上位４ビットを着目対象とし（Ｓ５１１）、両者はビットが同じであるため、変数ｚ５の上位４ビットと、変数ｚ９の上位４ビットに同じレジスタｒ２を割り当てる（Ｓ５０９）。
【０１８３】
変数ｘ４、変数ｚ５、変数ｚ９にレジスタを割り当てた後、図２５（ａ）に示すように、変数ｙ４と変数ｘ８と変数ｘ１６とでライフタイムが重ならず、レジスタ共有化の余地があるため、変数ｙ４、変数ｘ８、変数ｘ１６に着目する（Ｓ５０２）。
【０１８４】
変数ｙ４は４ビットであり、変数ｘ８は８ビットであり、変数ｘ１６は１６ビットであり、ビット幅が異なるため、ビット幅が最大ではない、変数ｙ４、変数ｘ８の変数を最小限に符号拡張し５ビットと９ビットとする（Ｓ５０４）。
【０１８５】
そして、ビット幅最小の変数ｙ４のビット幅５に合わせて、変数ｘ８を上位４ビットと下位５ビットに分割し、変数ｘ１６を上位１１ビットと下位５ビットに分割する（Ｓ５０６）。図２５（ｂ）のように、ビット幅最小の変数ｙ４と、変数ｘ８の下位ビット、変数ｘ１６の下位ビットに同じレジスタｒ３を割り当てる（Ｓ５０７）。
【０１８６】
さらに、分割した変数ｘ８の上位４ビットと、変数ｘ１５の上位１１ビットを着目対象とする（Ｓ５１１）。ビット幅の小さい変数ｘ８の４ビットに合わせて、変数ｘ１５の上位１１ビットを上位７ビットと下位４ビットに分割する（Ｓ５０６）。図２５（ｂ）のように、ビット幅の小さい変数ｘ８の上位４ビットと、変数ｘ１６の下位ビットに同じレジスタｒ４を割り当てる（Ｓ５０７）。さらに、残りの変数ｘ１６の上位７ビットにレジスタｒ５を割り当てる。
【０１８７】
次に、変数ｚ１７が残っているが、レジスタ共有化の余地がないため、図２６（ａ）に示すように変数ｚ１７に着目し、図２６（ｂ）に示すように、変数ｚ１７にレジスタｒ６を割り当て（Ｓ５１１）、処理が終了する。
【０１８８】
図２７は、図２６のライフタイムテーブル６２３から生成されたデータパス７００の構成を示している。データパス７００では、ライフタイムテーブル６２３により割り当てられたレジスタｒ１〜ｒ６を加算器Ａ１で接続する。ライフタイムテーブル６２３の制御ステップに応じて共有のレジスタｒ１〜ｒ４に入力する変数を切り替えるためにマルチプレクサＭ１〜Ｍ４を、レジスタｒ１〜ｒ４に接続する。また制御ステップに応じてレジスタｒ５、ｒ６に入力する変数のタイミングを制御するためマルチプレクサＭ５、Ｍ６を、レジスタｒ５、ｒ６に接続する。
【０１８９】
すなわち、このデータパス７００は、変数ｘ４と、加算器Ａ１の出力である変数ｚ５と、加算器Ａ１の出力である変数ｚ９の下位ビットのいずれかを切り替えて出力するマルチプレクサＭ１、マルチプレクサＭ１が選択した変数を保持するレジスタｒ１、変数ｚ５の上位ビット（４ビットの"０"）と、変数ｚ９の上位ビットのいずれかを切り替えて出力するマルチプレクサＭ２、マルチプレクサＭ２が選択した変数を保持するレジスタｒ２、変数ｙ４と、変数ｘ８の下位ビットと、変数ｘ１６の下位ビットのいずれかを切り替えて出力するマルチプレクサＭ３、マルチプレクサＭ３が選択した変数を保持するレジスタｒ３、変数ｘ８の上位ビットと、変数ｘ１６の中間ビットのいずれかを切り替えて出力するマルチプレクサＭ４、マルチプレクサＭ４が選択した変数を保持するレジスタｒ４、変数ｘ１６の上位ビットをレジスタｒ５へ出力するマルチプレクサＭ５、マルチプレクサＭ５を介した変数ｘ１６の上位ビットを保持するレジスタｒ５、レジスタｒ１及びｒ２の値と、レジスタｒ３、ｒ４及びｒ５の値とを加算する加算器Ａ１、加算器Ａ１の出力をレジスタｒ６へ出力するマルチプレクサＭ６、マルチプレクサＭ６を介した加算器Ａ１の出力を変数ｚ９として保持するレジスタｒ６を備えている。
【０１９０】
このように、本実施形態では、記憶ユニットのアロケーションにあたり、ライフタイムの重ならない２つ以上の変数に着目し、最小のビット幅の変数に合わせて複数の変数を分割してレジスタの割り当てを行うようにした。
【０１９１】
これにより、ライフタイムの重ならない変数が２つ以上ある場合でも、実施の形態１と同様に共有化するレジスタのビット幅を小さくすることができる。
【０１９２】
また、実施の形態１と同様に、マルチプレクサの面積が小さくなり、スタティック電力を低減することができる。さらに、切り替え時の（ダイナミックな）消費電力を低減することができる。また、クロックゲーティングできる余地が増え、さらに消費電力を低減することが可能となる。
【０１９３】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【０１９４】
１００ コンピュータシステム
１０１ 本体部
１０３ メインメモリ
１０４ ハードディスク
１０５ 表示装置
１０６ キーボード
１０７ マウス
１０８ 動作合成プログラム
１０９ 各種データ
２００ 動作合成装置
２０１ 動作記述情報記憶部
２０２ パーズ処理部
２０３ 内部表現情報記憶部
２０４ スケジューリング処理部
２０５ アロケーション処理部
２０５ａ 機能ユニットアロケーション部
２０５ｂ 記憶ユニットアロケーション部
２０５ｃ 通信ユニットアロケーション部
２０６ 制御回路用テーブル及びネットリスト生成部
２０７ 制御回路用テーブル記憶部
２０８ ネットリスト記憶部
２０９ ＲＴＬ出力部
２１０ ＲＴＬ情報記憶部
２１１ クロックゲーティング及びＲＴＬ出力部
２２１ ライフタイム計算部
２２２ 変数選択部
２２３ ビット幅検出部
２２４ 符号拡張部
２２５ 変数分割部
２２６ レジスタ割り当て部
【技術分野】
【０００１】
本発明は、動作合成方法、動作合成プログラム及び動作合成装置に関し、特に、変数の演算動作が記述された動作記述を動作合成する動作合成方法、動作合成プログラム及び動作合成装置に関する。
【背景技術】
【０００２】
近年、ＬＳＩの大規模化が進んでおり、より効率の良い設計方法や設計ツールが望まれている。そこで、ＬＳＩの機能設計において、動作レベルの記述である動作記述を動作合成し、レジスタ転送レベルの記述であるＲＴＬ記述を生成する手法が知られている。動作合成では、Ｃ言語と同様の言語により回路素子を意識せずに動作のみを記述するため、回路設計を容易にし、設計期間を短縮することができる。
【０００３】
従来の動作合成方法として、非特許文献１に記載の方法が知られている。図２８は、非特許文献１に記載された従来の動作合成方法を示している。
【０００４】
図に示されるように、従来の動作合成方法９００では、回路の動作を記述した動作記述が入力され（９０１）、ＨＤＬコンパイラが、この動作記述を解析し（９０２）、内部表現に変換される（９０３）。この内部表現としては，動作記述に現れたデータの流れ(データフロー)と各演算の実行順序の制御の流れ(コントロールフロー)を表した，コントロールデータフローグラフ(CDFG : Control Data Flow Graph)が用いられる。
【０００５】
生成された内部表現に対して、スケジューリングが行われる（９０４）。スケジューリングでは、動作記述中の各演算やデータ転送を実行する具体的な制御ステップを決定する。また、スケジューリングされた内部表現に対しアロケーションが行われる（９０５）。アロケーションでは所望の動作を実現する回路構成を決定する。
【０００６】
スケジューリングとアロケーションが終了すると，レジスタ，機能ユニット，マルチプレクサ等を回路要素としたデータパスのネットリストと（９０８），各クロックで実行する動作を制御する信号と順次実行させるための状態遷移の情報を示す制御回路用テーブル（９０７）が生成される（９０６）。
【０００７】
図２９は、非特許文献１に記載された従来の動作合成方法におけるアロケーション処理の例を示している。
【０００８】
従来の動作合成方法では、動作記述に基づいてＣＤＦＧが生成され、スケジューリングが行われると、図２９（ａ）のようなスケジューリング後のＣＤＦＧが生成される。そうすると、従来の動作合成方法では、アロケーションにより、変数ａ，ｂ，ｃ，ｄ，ｅにレジスタが割り当てられ、加算ｏ１、ｏ２に加算器が割り当てられる。
【０００９】
一般的に、アロケーションでは、回路面積を減らす目的で、複数の変数を同じレジスタに割り当てて使用する「レジスタの共有化」が行われている。図２９（ｂ）（ｃ）は、レジスタを共有化してアロケーションを行った例である。
【００１０】
図２９（ａ）の例では、変数ａ及び変数ｂと加算器は同時に使用され、変数ｄ及び変数ｃと加算器は同時に使用されるが、その他の組み合わせは同時に使用されない。このため、図２９（ｂ）では、変数ａ、ｄ、ｅでレジスタｒ１を共有し、変数ｂにレジスタｒ２、変数ｃにレジスタｒ３を割り当て、共有した加算器の入力の値を選択するためにマルチプレクサを割り当てている。
【００１１】
また、図２９（ｃ）では、変数ａ、ｅでレジスタｒ１を共有し、変数ｂ、ｄでレジスタｒ２を共有し、変数ｃにレジスタｒ３を割り当て、共有したレジスタと加算器の入力の値を選択するために２つのマルチプレクサを割り当てている。
【００１２】
図３０は、非特許文献１に記載された従来の動作合成方法におけるレジスタの共有化の例を示している。図３０（ａ）は、図２９（ａ）と同様にスケジューリング後のＣＤＦＧである。
【００１３】
スケジューリング後のＣＤＦＧが生成されると、従来の動作合成方法では、図３０（ｂ）のように各変数のライフタイムを計算する。ライフタイムとは、変数に値が書き込まれてから使用されるまでの期間であり、変数に値を保持する必要がある期間である。
【００１４】
図３０（ｂ）の例では、変数ａはステップ１より前からステップ２まで、変数ｂはステップ１より前からステップ１まで、変数ｃはステップ１からステップ２まで、変数ｄはステップ２からその後までが、それぞれライフタイムである。ライフタイムが重ならない変数は同じレジスタに割り当てて共有化することが可能である。
【００１５】
従来の動作合成方法では、図３０（ｃ）のように、変数ａ，ｂ，ｃ，ｄをそのライフタイムの開始時刻順にソートし，最初の変数を１番目のレジスタに割り当てる。以下、変数を順に調べながら、ライフタイムが重ならない限りそのレジスタに変数を割り当てていく。割り当てられる変数がなくなると新しいレジスタを用意し，すべての変数が割り当てられるまで繰り返す。図３０（ｃ）の例では、まず、変数ａと変数ｄとでライフタイムが重ならないため、レジスタｒ１を割り当てて共有化し、変数ｂと変数ｃとでライフタイムが重ならないため、レジスタｒ２を割り当てて共有化している。
【００１６】
また、レジスタの共有に関する従来の動作合成方法として、特許文献１が知られている。図３１は、特許文献１に記載された従来の動作合成方法におけるレジスタの共有化の例を示している。
【００１７】
図３１は、変数ａ１の値をレジスタｃ１に転送し、変数ｂ１の値をレジスタｃ２に転送する場合に、ｃ１とｃ２とを一つのレジスタ（５ビット）で共有化する例である。
【００１８】
図３１（ａ）では、２ビットのｓｉｇｎｅｄの変数ａ１、及び４ビットのｓｉｇｎｅｄの変数ｂ１を共通のレジスタ（５ビット）に転送する場合、転送先のレジスタのビット数に対して不足するビット数を変数ａ１及びｂ１にそれぞれ付与し、マルチプレクサ（ＭＵＸ）によってレジスタに転送する変数を切り替えている。ここで、変数ａ１及びｂ１はそれぞれ０ビット目が符号ビットであるため、不足するビットには符号ビットと同じデータを挿入している。
【００１９】
図３１（ｂ）では、４ビットのｕｎｓｉｇｎｅｄの変数ａ２、及び２ビットのｕｎｓｉｇｎｅｄの変数ｂ２を共通のレジスタ（５ビット）に転送する場合、ｓｉｇｎｅｄの変数の場合と同様に、転送先のレジスタのビット数に対して不足するビット数を変数ａ２及びｂ２にそれぞれ付与し、マルチプレクサ（ＭＵＸ）によってレジスタに転送する変数を切り替えている。ここで、変数ａ２及びｂ２はそれぞれ符号ビットを持たないため、不足するビットにはデータ"０"を挿入している。
【００２０】
なお、従来の動作合成方法に関連する技術として特許文献２も知られている。しかし、特許文献２は、動作合成の結果を検証する検証方法の技術であり、動作合成方法の具体的な内容については記載されていない。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】松永裕介、"高位レベル合成"、インターネット<URL:http://www.c.csce.kyushu-u.ac.jp/~matsunaga/lecture/lsicad/pdf/Lecture06.pdf>
【特許文献】
【００２２】
【特許文献１】特許第２８６１９９４号公報
【特許文献２】特開２０１１−３４５１７号公報
【発明の概要】
【発明が解決しようとする課題】
【００２３】
上記のように、特許文献１や２には、従来の動作合成方法において、アロケーションを行う際に、レジスタを共有化することが記載されている。
【００２４】
特に、図３１で示したように、従来の動作合成方法では、ビット幅の違う変数に対してもレジスタの共有化が可能となるよう、ビット幅の小さい変数の上位ビットにデータを補って、ビット幅の大きい変数に揃えた上で、レジスタの共有化を行っていた。すなわち、図３１（ａ）では、ビット幅の大きな変数ｂ１に合わせて、ビット幅の小さな変数ａ１の上位ビットを符号拡張し、また、図３１（ｂ）では、ビット幅の大きな変数ａ２に合わせて、ビット幅の小さな変数ｂ２の上位ビットを"０"で埋めて、レジスタを共有化していた。
【００２５】
そうすると、この共有化されたレジスタでは、ビット幅の小さな変数から見ると、未使用の無駄なビットが存在することになる。
【００２６】
したがって、従来の動作合成方法では、ビット幅の大きい変数に合わせたビット幅でレジスタを共有化するため、ビット幅の小さい変数にとって未使用のビットが発生することから、共有化するレジスタのビットが無駄に大きいという問題があった。
【課題を解決するための手段】
【００２７】
本発明に係る動作合成方法は、変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択し、前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、前記第１及び第２のレジスタを有する合成回路の回路情報を出力するものである。
【００２８】
本発明に係る動作合成方法は、変数の演算動作を含む動作記述情報から、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、前記スケジューリングされたデータフローグラフ情報から、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、前記ライフタイム情報が時間軸上で重ならない、第１のビット幅として定義された第１の変数と、第２の変数とを選択し、前記第１の変数と、前記第２の変数に含まれる前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記第２の変数に含まれる前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、前記第１及び第２のレジスタを有する合成回路の回路情報を出力するものである。
【００２９】
本発明に係る動作合成プログラムは、コンピュータに動作合成処理を実行させる動作合成プログラムであって、前記動作合成処理は、変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択し、前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、前記第１及び第２のレジスタを有する合成回路の回路情報を出力するものである。
【００３０】
本発明に係る動作合成装置は、変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成するスケジューリング部と、前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成するライフタイム生成部と、前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択する変数選択部と、前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当てるレジスタ割り当て部と、前記第１及び第２のレジスタを有する合成回路の回路情報を出力する回路情報出力部と、を備えるものである。
【００３１】
本発明では、第１のビット幅の第１の変数と、その他の変数（第２の変数）のうちの第１のビット幅のビットとに、レジスタを割り当てて共有化するため、共有化するレジスタのビット幅を小さくすることができる。
【発明の効果】
【００３２】
本発明によれば、共有化するレジスタのビット幅を小さくすることが可能な動作合成方法、動作合成プログラム及び動作合成装置を提供することができる。
【図面の簡単な説明】
【００３３】
【図１】本発明の実施の形態１に係る動作合成装置を実現するためのコンピュータシステムのハードウェア構成を示す構成図である。
【図２】本発明の実施の形態１に係る動作合成装置の機能構成を示すブロック図である。
【図３】本発明の実施の形態１に係る記憶ユニットアロケーション部の機能構成を示すブロック図である。
【図４】本発明の実施の形態１に係る動作合成方法の流れを示すフローチャートである。
【図５】本発明の実施の形態１に係る記憶ユニットのアロケーション方法の流れを示すフローチャートである。
【図６】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図７】本発明の実施の形態１に係る動作合成方法で使用されるデータ構造の具体例を示す図である。
【図８】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図９】本発明の実施の形態１に係る動作合成方法で使用されるデータ構造の具体例を示す図である。
【図１０】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図１１】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図１２】本発明の実施の形態１に係る動作合成方法を説明するための具体例を示す図である。
【図１３】本発明の実施の形態１に係る動作合成方法により生成されるデータパスの回路構成を示す回路図である。
【図１４】本発明の実施の形態１に係る動作合成方法により生成される合成回路の回路構成を示す回路図である。
【図１５】本発明の実施の形態１に係る動作合成方法により生成されるＲＴＬの記述例を示す図である。
【図１６】本発明の実施の形態１に係る動作合成方法により生成されるＲＴＬの記述例を示す図である。
【図１７】本発明の実施の形態２に係る動作合成装置の機能構成を示すブロック図である。
【図１８】本発明の実施の形態２に係る動作合成方法により生成される合成回路の回路構成を示す回路図である。
【図１９】本発明の実施の形態２に係る動作合成方法により生成される合成回路の動作を示すタイミングチャートである。
【図２０】本発明の実施の形態３に係る記憶ユニットのアロケーション方法の流れを示すフローチャートである。
【図２１】本発明の実施の形態４に係る記憶ユニットのアロケーション方法の流れを示すフローチャートである。
【図２２】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２３】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２４】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２５】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２６】本発明の実施の形態４に係る動作合成方法を説明するための具体例を示す図である。
【図２７】本発明の実施の形態４に係る動作合成方法により生成されるデータパスの回路構成を示す回路図である。
【図２８】従来の動作合成方法を示す図である。
【図２９】従来の動作合成方法を示す図である。
【図３０】従来の動作合成方法を示す図である。
【図３１】従来の動作合成方法を示す図である。
【図３２】本発明と比較するための参考例を示す図である。
【発明を実施するための形態】
【００３４】
（本発明の実施の形態１）
以下、図面を参照して本発明の実施の形態１について説明する。
【００３５】
図１は、本発明の実施の形態１に係る動作合成装置が実現されるコンピュータシステムのハードウェア構成を示している。なお、後述する他の実施の形態においても、図１と同様のコンピュータシステムにより動作合成装置が実現される。
【００３６】
このコンピュータシステム１００は、パーソナルコンピュータやワークステーション等の情報処理装置である。図に示されるように、コンピュータシステム１００は、ＣＰＵ１０２、メインメモリ１０３、ハードディスク１０４等を内蔵した本体部１０１、本体部１０１からの指示により画面表示を行う表示装置１０５、このコンピュータシステムにユーザの指示や文字情報を入力するためのキーボード１０６、および表示装置の画面上における任意の位置を指定し、その位置に表示されていたアイコン等に応じた指示を入力するマウス１０７から構成される。
【００３７】
なお、ＣＰＵ１０２及びメインメモリ１０３は、プログラムを実行し各部を制御する制御部の一例であり、ハードディスク１０４は、プログラム等を記憶する記憶部の一例である。制御部と記憶部は、一つの装置でもよいし、複数の装置であってもよい。例えば、複数の制御装置や複数の記憶装置に分散されていてもよい。また、表示装置１０５は、ユーザに対し種々の出力を行う出力装置の一例であり、キーボード１０６、マウス１０７は、ユーザが種々の入力操作を行う入力装置の一例である。
【００３８】
ハードディスク１０４には、本実施形態に係る動作合成装置を実現するための動作合成プログラム１０８、動作合成処理等に必要なその他の各種データ１０９が格納される。動作合成プログラム１０８は、図４，図５に後述する動作合成方法の処理を実行するためのプログラムであり、各種データ１０９は、図２に後述する各記憶部に記憶されるデータである。
【００３９】
コンピュータシステム１００が、動作合成プログラム１０８および各種データ１０９をメインメモリ１０３にロードし、ＣＰＵ１０２はメインメモリ１０３にロードされた動作合成プログラム１０８を実行することで、本実施形態の動作合成方法の各処理が実施されて、動作合成装置（図２、図３に後述する機能構成）が実現される。なお、コンピュータシステム１００の基本動作は、ハードディスク１０４に格納された基本プログラムであるオペレーティングシステム（ＯＳ）を介して実行される。
【００４０】
図２は、本発明の実施の形態１に係る動作合成装置の機能構成を示している。この動作合成装置２００は、コンピュータシステム１００上で動作合成プログラムが実行されて実現される。
【００４１】
図に示されるように、この動作合成装置２００は、動作記述情報記憶部２０１、パーズ処理部２０２、内部表現情報記憶部２０３、スケジューリング処理部２０４、アロケーション処理部２０５、制御回路用テーブル及びネットリスト生成部２０６、制御回路用テーブル記憶部２０７、ネットリスト記憶部２０８、ＲＴＬ出力部２０９、ＲＴＬ情報記憶部２１０を備えている。
【００４２】
動作記述情報記憶部２０１は、動作記述言語で記述された動作記述を表すデータである動作記述情報を記憶する。動作記述は、Ｃ言語をハードウェア記述のために拡張したＳｙｓｔｅｍＣ等の動作記述言語により記述される。例えば、動作記述情報は、ユーザによりキーボード１０６等を介して入力されて、動作記述情報記憶部２０１に記憶される。
【００４３】
パーズ処理部２０２は、動作記述情報記憶部２０１に記憶された動作記述情報に基づいて、動作記述情報をパーズ（変換）して、内部表現であるＣＤＦＧを表す内部表現情報を生成する。
【００４４】
内部表現情報記憶部２０３は、パーズ処理部２０２が生成した内部表現情報を記憶する。また、内部表現情報記憶部２０３は、内部表現情報に対しスケジューリング処理部２０４及びアロケーション処理部２０５が処理した結果である、スケジューリング後のＣＤＦＧやアロケーション後のＣＤＦＧのデータも記憶される。
【００４５】
スケジューリング処理部２０４は、パーズ処理部２０２が生成した内部表現情報に基づいて、この内部表現情報に対し各演算が実行される制御ステップをスケジューリングして、スケジューリング後の内部表現情報を生成する。
【００４６】
アロケーション処理部２０５は、スケジューリング処理部２０４が生成したスケジューリング後の内部表現情報に基づいて、この内部表現情報に対し機能ユニット、記憶ユニット、通信ユニットのアロケーションを行って、アロケーション後の内部表現情報を生成する。
【００４７】
また、アロケーション処理部２０５は、加算器等の機能ユニットをアロケーションする機能ユニットアロケーション部２０５ａ、レジスタ等の記憶ユニットをアロケーションする記憶ユニットアロケーション部２０５ｂ、マルチプレクサ等の通信ユニットをアロケーションする通信ユニットアロケーション部２０５ｃを有している。
【００４８】
制御回路用テーブル及びネットリスト生成部２０６は、スケジューリング処理部２０４及びアロケーション処理部２０５が生成したスケジューリング及びアロケーション後の内部表現情報に基づいて、この内部表現情報から制御回路の制御対象と制御タイミング等を特定して制御回路用テーブルを生成し、かつ、この内部表現情報からデータパスの各回路素子と接続関係を特定してネットリストを生成する。
【００４９】
制御回路用テーブル記憶部２０７は、制御回路用テーブル及びデータパスのネットリスト生成部２０６が生成した制御回路用テーブルを記憶する。ネットリスト記憶部２０８は、御回路用テーブル及びデータパスのネットリスト生成部２０６が生成したネットリストを記憶する。
【００５０】
ＲＴＬ出力部２０９は、制御回路用テーブル及びネットリスト生成部２０６が生成した制御回路用テーブルとデータパスのネットリストとに基づいて、制御回路用テーブルに応じた制御回路とネットリストのデータパスとを合成した合成回路のＲＴＬ情報を生成し、生成したＲＴＬ情報を出力する。
【００５１】
ＲＴＬ情報記憶部２１０は、ＲＴＬ出力部２０９が出力したＲＴＬ情報を記憶する。ＲＬＴ情報は、ＶＨＤＬ(Very High Speed Integrated Circuits Hardware Description Language)等のハードウェア記述言語（Hardware Description Language）により記述されたＲＴＬのデータである。
【００５２】
図３は、本発明の実施の形態１に係る記憶ユニットアロケーション部の機能構成を示している。この記憶ユニットアロケーション部２０５ｂは、図２のアロケーション処理部２０５に含まれている。
【００５３】
図に示されるように、記憶ユニットアロケーション部２０５ｂは、ライフタイム計算部２２１、変数選択部２２２、ビット幅検出部２２３、符号拡張部２２４、変数分割部２２５、レジスタ割り当て部２２６を備えている。
【００５４】
ライフタイム計算部２２１は、スケジューリング処理部２０４がスケジューリングしたスケジューリング後の内部表現情報（ＤＣＦＧ）に基づいて、各制御ステップで使用される変数を求め、変数ごとにライフタイムを計算する。
【００５５】
変数選択部２２２は、ライフタイム計算部２２１が計算したライフタイムに基づいて、各変数のライフタイムが時間軸上（制御ステップ）で重なっているかどうか判定し、ライフタイムが重ならない２つの変数を選択する。
【００５６】
ビット幅検出部２２３は、変数選択部２２２が選択した２つの変数について、ビット幅を検出し、２つのビット幅が異なるかどうか判定する。また、ビット幅検出部２２３は、符号拡張部２２４が符号を拡張した変数についても、ビット幅が異なるかどうか判定する。
【００５７】
符号拡張部２２４は、ビット幅検出部２２３により２つの変数のビット幅が異なると判定された場合、ビット幅が小さい変数を必要最小限に符号を拡張する。
【００５８】
変数分割部２２５は、ビット幅検出部２２３により２つの変数のビット幅が異なると判定された場合、ビット幅が大きい変数を、ビット幅が小さい変数の幅に合わせて上位ビットと下位ビットにビット分割する。
【００５９】
レジスタ割り当て部２２６は、ビット幅検出部２２３により２つの変数のビット幅が同じであると判定された場合、この２つの変数に同じレジスタを割り当てる。また、レジスタ割り当て部２２６は、変数分割部２２５が分割した下位ビットと、ビット幅の小さい変数とに同じレジスタを割り当て、変数分割部２２５が分割した残りの上位ビットに、別のレジスタを割り当てる。
【００６０】
以下に、本発明の実施の形態１における、記憶ユニットのアロケーション方法を含む動作合成方法の動作について説明する。まず、図４及び図５のフローチャートを用いて動作合成方法の流れを説明した後、図６〜図１６を用いて動作合成方法の具体例について説明する。
【００６１】
図４に示すように、本実施形態の動作合成方法Ｓ２００では、まず、パーズ処理部２０２は、入力された動作記述のデータである動作記述情報をパーズして、ＣＤＦＧのデータである内部表現情報を生成する（Ｓ２０１）。
【００６２】
次いで、スケジューリング処理部２０４は、Ｓ２０１で生成された内部表現情報に対しスケジューリングを行って、スケジューリング後の内部表現情報を生成する（Ｓ２０２）。
【００６３】
次いで、アロケーション処理部２０５が、Ｓ２０２で生成されたスケジューリング後の内部表現情報に対しアロケーションを行って、アロケーション後のＣＤＦＧが生成される（Ｓ２０３〜Ｓ２０５）。すなわち、機能ユニットアロケーション部２０５ａは、内部表現情報に対し加算器等の機能ユニットを割り当て（Ｓ２０３）、記憶ユニットアロケーション部２０５ｂは、内部表現情報に対しレジスタ等の記憶ユニットを割り当て（Ｓ２０４）、通信ユニットアロケーション部２０５ｃは、内部表現情報に対しマルチプレクサ等の通信ユニットのアロケーションを行う（Ｓ２０５）。
【００６４】
なお、機能ユニット、記憶ユニット、通信ユニットのアロケーションは、互いに関連しているため、アロケーションの順序は適宜変更される。例えば、記憶ユニットのアロケーションでレジスタを共有化すると、レジスタの構成が変わるため、機能ユニットや通信ユニットの割り当ても変更される。
【００６５】
次いで、制御回路用テーブル及びネットリスト生成部２０６は、Ｓ２０２〜Ｓ２０５で生成されたスケジューリング及びアロケーション後の内部表現情報を用いて、制御回路用テーブル及びデータパスのネットリストを生成する（Ｓ２０６）。
【００６６】
次いで、ＲＴＬ出力部２０９は、Ｓ２０６で生成された制御回路用テーブル及びデータパスのネットリストを用いて、制御回路とデータパスを合成した合成回路のＲＴＬ情報を出力し（Ｓ２０７）、動作合成処理が終了するＲＴＬを出力する（Ｓ２０７）。
【００６７】
また、図５に示されるように、記憶ユニットのアロケーション処理（Ｓ２０４）では、まず、ライフタイム計算部２２１は、スケジューリングされたＣＤＦＧ（内部表現）上で状態を横切る各変数についてライフタイムを計算する（Ｓ３０１）。次いで、変数選択部２２２は、Ｓ３０１でライフタイムを計算した複数の変数のうち、ライフタイムの重ならない２つの変数に着目する（Ｓ３０２）。次いで、ビット幅検出部２２３は、Ｓ３０２で着目した２つの変数のビット幅が異なるかどうか判定する（Ｓ３０３）。
【００６８】
Ｓ３０３において、ビット幅が異なると判定された場合、符号拡張部２２４は、ビット幅が小さい変数を、必要最小限に符号拡張する（Ｓ３０４）。さらに、ビット幅検出部２２３は、Ｓ３０４で符号拡張した２つの変数のビット幅が異なるかどうか判定する（Ｓ３０５）。
【００６９】
なお、後述のように動作記述情報には、各変数のビット幅が予め定義されている。この予め定義されたビット幅を、そのまま利用できる場合はＳ３０４の符号拡張は不要であり、Ｓ３０５の判定も不要である。たとえば、ビット幅が小さい変数が入力される演算について、入力と出力とのビット幅が同じである場合は、符号拡張が０である。すなわちビット幅の拡張はない。このような場合であって、かつ、Ｓ３０３で共有される変数のビット幅が違うケースにあっては、Ｓ３０４、Ｓ３０５は不要であり、ビット削減が可能となる。また、予め定義されたビット幅を、そのまま利用できない場合にＳ３０４の符号拡張を行って、対象の変数のビット幅を再度定義し、Ｓ３０５の判定が行われる。すなわち、Ｓ３０３では、予め定義された変数のビット幅を比較しており、Ｓ３０５では、符号拡張により定義された変数のビット幅を比較している。
【００７０】
Ｓ３０５において、符号拡張後にビット幅が異なると判定された場合、変数分割部２２５は、ビット幅が大きい変数を、ビット幅が小さい変数の幅に合わせて上位ビットと下位ビットにビット分割する（Ｓ３０６）。
【００７１】
次いで、レジスタ割り当て部２２６は、ビット幅が小さい変数とビット幅が大きい変数の分割後の下位ビットとを同じレジスタに割り当てる（Ｓ３０７）。次いで、レジスタ割り当て部２２６は、ビット幅が大きい変数の分割後の上位ビットを別のレジスタに割り当てる（Ｓ３０８）。
【００７２】
Ｓ３０３またはＳ３０５において、２つの変数のビット幅が同じと判定された場合、レジスタ割り当て部２２６は、着目した２つの変数を同じレジスタに割り当てる（Ｓ３０９）。
【００７３】
Ｓ３０８またはＳ３０９のレジスタ割り当ての後、レジスタ割り当て部２２６は、さらなるレジスタ共有化の余地があるかどうか判定する（Ｓ３１０）。Ｓ３１０において、レジスタ共有化の余地があると判定した場合、Ｓ３０２以降の処理を繰り返し、さらにレジスタの共有化を行う。また、Ｓ３１０において、レジスタ共有化の余地がないと判定した場合、残った変数があれば全てレジスタに割り当てて、処理を終了する（Ｓ３１１）。
【００７４】
以下、図６〜図１６の動作合成方法の具体例について、図４及び図５の各ステップに対応付けて説明する。
【００７５】
まず、動作合成方法Ｓ２００の処理が開始されると、図６に示すようにパーズが行われる（Ｓ２０１）。図６（ａ）は動作記述の例を示し、図６（ｂ）は、図６（ａ）の動作記述をパーズして生成されたＣＤＦＧを示している。
【００７６】
図６（ａ）のように、動作記述３００は、変数宣言記述部３０１と演算記述部３０２を有している。なお、動作記述情報は、動作記述の文字列からなるテキストデータである。
【００７７】
変数宣言記述部３０１では、各行に変数の型、変数のビット幅、変数名の順に記述され、変数の符号情報の有無と、ビット幅が定義されている。なお、変数は、その取りうる値を２進数表現する場合に割り当てるビット数を決める必要がある。本明細書では、このように変数の値を２進数表現するために割り当てるビット数を、ビット幅と称する。したがって、ｎビット幅（ｎ：整数）の変数Ｘは、ｎビットの２進数表現で現す変数Ｘの意味である。このように、ｎビット幅が割り当てられた変数Ｘのことを、ｎビット幅として定義された変数Ｘと称する。
【００７８】
この例では、変数ｘ４、ｙ４を４ビットの符号無し整数（ｕｉｎｔ型）の変数、変数ｘ８を８ビットの符号無し整数の変数、変数ｚ５を５ビットの符号無し整数の変数、変数ｚ９を９ビットの符号無し整数の変数として宣言（定義）している。なお、同様に、符号有り整数（ｉｎｔ型）の変数を宣言することも可能であり、その場合に定義するビットには、符号情報を示すビット（例えば最上位ビット）が含まれている。
【００７９】
演算記述部３０２では、変数宣言記述部３０１で宣言した変数を四則演算する動作（式）が記載される。この例では、変数ｘ４と変数ｙ４を加算した結果を変数ｚ５に入力し（式３０２ａ）、変数ｘ８と変数ｚ５を加算した結果を変数ｚ９に入力する（式３０２ｂ）動作が記載されている。
【００８０】
変数宣言記述部３０１と演算記述部３０２により、４ビットの変数と４ビットの変数の加算結果を５ビットの変数に格納し、さらにその５ビットの変数と８ビットの変数の加算結果を９ビットの変数として出力する動作が表される。
【００８１】
図６（ｂ）のように、動作記述３００をパーズして生成されるＣＤＦＧ３１０は、動作記述に対応して、演算内容と演算に用いる変数とが関係付けて表される。動作記述３００の演算記述部３０２の記述の式には、演算記号として「＋」があるため、加算（加算器）を示す記号と各変数とを接続して関連付けられる。
【００８２】
この例では、加算１の演算が、式３０２ａに対応しており、４ビットの変数ｘ４と４ビットの変数ｙ４を加算して５ビットの変数ｚ５へ出力することを表している。そして、加算２の演算が、式３０２ｂに対応しており、５ビットの変数ｚ５と８ビットの変数ｘ８を加算して９ビットの変数ｚ９へ出力することを表している。なお、ここでは符号無しの変数の例を示しているが、符号ありの変数の場合には、ビット幅を必要最小限だけ増やし、同様にＣＤＦＧを生成することができる
【００８３】
図７は、このＣＤＦＧをデータとして記憶・処理するための内部表現情報の一例を示している。この内部表現情報３２０は、ＣＤＦＧを構成する変数や演算等のノード（要素）を表す構造体の集合である。構造体は、各ノードを特定するため、例えば、「種類」、「名称」、「ビット幅」、「接続関係」等のパラメータを有している。構造体は、「種類」に応じて、複数通りのものがある。この例では、「外部入力変数」、「加算」、「中間変数」、「外部出力変数」の４通りの構造体があり、ノード間のつながりは、構造体中に「接続先」や「接続元」を指定する領域を設けて表現する。
【００８４】
図７の内部表現情報３２０は、図６のＣＤＦＧ３１０の各ノードを表している。構造体３２１は変数ｘ４、構造体３２２は変数ｙ４、構造体３２３は加算１、構造体３２４は変数ｚ５、構造体３２５は変数ｘ８、構造体３２６は加算２、構造体３２７は変数ｚ９をそれぞれ表している。
【００８５】
図６でパーズした後、図８（ａ）に示すようにスケジューリングが行われる（Ｓ２０２）。図８（ａ）は、図６のＣＤＦＧ３１０に対しスケジューリングを行った後のＣＤＦＧ３１１を示している。
【００８６】
スケジュール処理では、各演算処理の順序に従って、各演算処理を実行する制御ステップが決定される。図６（ａ）（ｂ）から理解できるように、変数ｘ４と変数ｙ４の加算の後に、変数ｘ８と変数ｚ５を加算する必要がある。このため、２つの加算処理を２つのステップで実行することにする。
【００８７】
すなわち、図８（ａ）のように、２つの加算を別のステップに区切り、ステップ１において、変数ｘ４と変数ｙ４とを加算して変数ｚ５へ出力する加算１の処理を実行し、次のステップ２において、変数ｚ５と変数ｘ８とを加算して変数ｚ９を出力する加算２の処理を実行するようにスケジュールする。
【００８８】
図８（ａ）でスケジューリングした後、Ｓ２０３〜Ｓ２０４のアロケーションが行われ、記憶ユニットのアロケーションでは、図８（ｂ）に示すようにライフタイムが計算される（Ｓ３０１）。図８（ｂ）は、図８（ａ）でスケジュールされたＣＤＦＧ３１１の各変数のライフタイムを示すライフタイムテーブル３３０である。なお、ここでは、ライフタイムを示す図において、主にステップ１及びステップ２を図示し、その前後のステップについては省略しているが、実際にはステップ１及びステップ２を繰り返すことになる。
【００８９】
ライフタイムの計算では、ＣＤＦＧで表される制御ステップと演算及び変数との関係から、変数ごとに、どの制御ステップからどの制御ステップまでの期間、値を保持する必要があるかを計算する。
【００９０】
この例では、変数ｘ４は、ステップ１の加算１の入力として使用され、加算１の後は使用されないため、ステップ１より前のステップからステップ１までがライフタイムとなる。変数ｙ４も同様に、変数ｘ４と同じライフタイムとなる。
【００９１】
変数ｘ８は、ステップ２の加算２の入力として使用され、加算２の後は使用されないため、ステップ１からステップ２までがライフタイムとなる。変数ｚ５は、ステップ１の加算１により値が確定して、ステップ２の加算２の入力として使用され、加算２の後は使用されないため、ステップ１からステップ２までがライフタイムとなる。
【００９２】
変数ｚ９は、最終的な演算結果が保持される変数であり、ここでは、状態に関係なく出力値を常に保持するものとする。したがって、変数ｚ９は、ステップ１より前のステップから、ステップ２より後のステップまで、全期間がライフタイムとなる。
【００９３】
図９は、このライフタイムをデータとして記憶・処理するためのライフタイム情報の一例を示している。このライフタイム情報は、各変数のライフタイムを表すテーブル構造体３４０である。テーブル構造体３４０は、ライフタイムの名称、期間を特定するため、例えば、「変数名」、「始点」、「終点」の欄を有し、さらに、レジスタの割り当てを特定するため「割当先」の欄を有している。
【００９４】
「始点」がＮＵＬＬの場合、「初期ステップ(ｓｔｅｐ１)以前からライフタイムあり」を表しており、「終点」がＮＵＬＬの場合、「最終ステップ(ｓｔｅｐ２)以後までライフタイムあり」を表している。「割当先」がＮＵＬＬは、割当先レジスタが未決定を表しており、割当先レジスタが決まった場合、「割当先」の欄にレジスタを記憶する。
【００９５】
ライフタイムは、連続する期間毎に記憶され、同じ変数が複数のライフタイムを有する場合には、複数のライフタイムが登録される。
【００９６】
図９では、テーブル構造体３４０は、ライフタイムテーブル３３１に対応しており、変数ｘ４、ｙ４、ｘ８、ｚ５、ｚ９の各ライフタイム（ａ）〜（ｆ）が、テーブル構造体３４０の各行に登録される。
【００９７】
このテーブル構造体３４０では、（ａ）が変数ｘ４の１つ目のライフタイム、（ｂ）が変数ｘ４の２つ目のライフタイム、（ｃ）が変数ｙ４のライフタイム、（ｄ）が変数ｘ８のライフタイム、（ｅ）が変数ｚ５のライフタイム、（ｆ）が変数ｚ６のライフタイムをそれぞれ表している。
【００９８】
図８（ｂ）でライフタイムを計算した後、図１０（ａ）に示すように２つの変数が着目される（Ｓ３０２）。図１０（ａ）は、図８（ｂ）と同じライフタイムテーブル３３０である。
【００９９】
ライフタイムの始点と終点から、ライフタイムが各制御ステップで重なっているか解析する。図１０（ａ）では、まず、変数ｘ４と変数ｚ５でライフタイムが重ならないため、変数ｘ４と変数ｚ５に着目する。
【０１００】
図１０（ａ）で２つの変数ｘ４とｚ５に着目した後、ビット幅の比較が行われ（Ｓ３０３）、変数ｘ４とｚ５はビット幅が異なるため、ビット幅が小さい変数ｘ４を必要最小限に符号拡張して５ビットとする（Ｓ３０４）。
【０１０１】
この符号拡張では、着目した変数が入力となっている演算に着目し、その演算の出力のビット幅に合わせて符号拡張する。上記のように、演算の入力と出力のビット幅が同じ場合、符号拡張は不要であり、演算の入力と出力のビット幅が異なる場合、出力のビット幅に合わせて符号拡張したビット幅を変数のビット幅として再定義する。
【０１０２】
例えば、４ビットの変数ｘ４が、出力ビット幅５ビットの加算演算の入力となっている場合、出力のビット幅５ビットに合わせるため、４ビットの変数ｘ４を１ビット符号拡張し、５ビットにする。例えば、５ビットの変数ｚ５が、出力ビット幅９ビットの加算演算の入力となっている場合、出力のビット幅９ビットに合わせるため、５ビットの変数ｚ５を４ビット符号拡張し、９ビットにする。
【０１０３】
着目した変数と異なる入力側には、一般に任意の値が入る可能性がある。それを考慮し、加算、減算の場合は一方の入力に０が入るケース、乗算の場合は一方の入力に１が入るケースをそれぞれ考えた場合、着目した変数の値が丸々、演算の出力に反映されることになる。
【０１０４】
このとき、もし、演算の出力のビット幅よりも、着目した変数のビット幅の方が小さいと、足りない上位ビットの値は未確定であり、ＲＴＬ生成後の接続関係によって不安定な値（ゴミ）が入る可能性があるため、正しい演算結果が得られない。このため、本実施形態では、予め、必要ビット数の符号拡張を行うことで、正確な動作を可能にしている。
【０１０５】
図１０（ａ）で、変数ｘ４を符号拡張した後、さらにビット幅の比較が行われ（Ｓ３０５）、拡張した変数ｘ４と変数ｚ５は同じ５ビットであるため、図１０（ｂ）に示すように、着目した２つの変数に同じレジスタを割り当てる（Ｓ３０９）。図１０（ｂ）は、図１０（ａ）のライフタイムテーブル３３０について、変数ｘ４とｙ４にレジスタｒ１を割り当てたライフタイムテーブル３３２である。
【０１０６】
すなわち、ライフタイムが重ならず、かつ、同じビット幅の変数ｘ４とｚ５を、ライフタイムテーブル上で連続するように表し、この連続する変数ｘ４とｚ５に、変数ｘ４及びｚ５と同じ５ビットのレジスタｒ１を割り当てる。
【０１０７】
図１０（ｂ）でレジスタｒ１を割り当てた後、さらなるレジスタの共有化の余地があるかどうか判定し（Ｓ３１０）、ライフタイムの重ならない変数があるため、図１１（ａ）に示すようにさらに２つの変数が着目される（Ｓ３０２）。図１１（ａ）は、図１０（ｂ）と同じライフタイムテーブル３３２である。図１１（ａ）では、変数ｙ４と変数ｘ８でライフタイムが重ならないため、変数ｙ４と変数ｘ８に着目する。
【０１０８】
図１１（ａ）で２つの変数ｙ４とｘ８に着目した後、ビット幅の比較が行われ（Ｓ３０３）、ビット幅が小さい変数ｘ４を必要最小限に符号拡張して５ビットとする（Ｓ３０４）。さらにビット幅の比較が行われ（Ｓ３０５）、拡張した変数ｙ４は５ビット、変数ｘ８は８ビットであり、ビット幅が異なるため、図１１（ｂ）に示すように、大きいビット幅の変数ｘ８を分割し（Ｓ３０６）、小さいビット幅の変数ｙ４と分割したｘ８の下位ビットとに同じレジスタｒ２を割り当て（Ｓ３０７）、分割したｘ８の上位ビットに別のレジスタｒ３を割り当てる（Ｓ３０８）。図１１（ｂ）は、図１１（ａ）のライフタイムテーブル３３２について、変数ｙ４とｘ８にレジスタｒ２、ｒ３を割り当てたライフタイムテーブル３３３である。
【０１０９】
すなわち、着目した変数ｙ４とｘ８は、ライフタイムが重ならず、かつ、ビット幅が異なるため、大きいビット幅の変数ｘ８を、上位３ビットと下位５ビットに分割する。小さいビット幅の変数ｙ４と変数ｘ８の下位５ビットを、ライフタイムテーブル上で連続するように表し、この連続する変数ｙ４と変数ｘ８の下位ビットに、５ビットのレジスタｒ２を割り当てる。さらに、変数ｘ８の上位ビットにレジスタｒ３を割り当てる。
【０１１０】
図１１（ｂ）でレジスタｒ２、ｒ３を割り当てた後、さらなるレジスタの共有化余地があるかどうか判定する（Ｓ３１０）。ライフタイムの重ならない変数は無いため、図１２（ａ）に示すように、残りの変数ｚ９に着目し、図１２（ｂ）に示すように、残りの変数ｚ９に９ビットのレジスタｒ４を割り当てる（Ｓ３１１）。
【０１１１】
図１２（ｂ）のライフタイムテーブル３３４により、レジスタ（記憶ユニット）のアロケーションが完了する。このレジスタのアロケーションに合わせて、加算器（機能ユニット）、マルチプレクサ（通信ユニット）のアロケーションが行われる。これらのアロケーションが完了すると、図１３に示すような、データパスのネットリストが生成される（Ｓ２０６）。
【０１１２】
ライフタイムテーブル３３４により割り当てられたレジスタｒ１、ｒ２、ｒ３、ｒ４を加算器Ａ１で接続する。ライフタイムテーブル３３４の制御ステップに応じて共有のレジスタｒ１、ｒ２に入力する変数を切り替えるためにマルチプレクサＭ１、Ｍ２を、レジスタｒ１、ｒ２に接続する。また制御ステップに応じてレジスタｒ３、ｒ４に入力する変数のタイミングを制御するためマルチプレクサＭ３、Ｍ４を、レジスタｒ３、ｒ４に接続する。
【０１１３】
すなわち、図１３に示すように、このデータパス４００は、変数ｘ４と加算器Ａ１の出力である変数ｚ５のいずれかを切り替えてレジスタｒ１へ出力するマルチプレクサＭ１、マルチプレクサＭ１が選択した変数を保持するレジスタｒ１、変数ｙ４と変数ｘ８の下位ビットのいずれかを切り替えてレジスタｒ２へ出力するマルチプレクサＭ２、マルチプレクサＭ２が選択した変数を保持するレジスタｒ２、変数ｘ８の上位ビットをレジスタｒ３へ出力するマルチプレクサＭ３、マルチプレクサＭ３を介した変数ｘ８の上位ビットを保持するレジスタｒ３、レジスタｒ１の値と、レジスタｒ２及びｒ３の値とを加算する加算器Ａ１、加算器Ａ１の出力をレジスタｒ４へ出力するマルチプレクサＭ４、マルチプレクサＭ４を介した加算器Ａ１の出力を変数ｚ９として保持し出力するレジスタｒ４を備えている。
【０１１４】
図１３のデータパスのネットリストが生成され、さらに、このデータパスを制御ステップに応じて制御する制御回路用テーブルが生成される（Ｓ２０６）。例えば、図１２のライフタイムテーブル３３４から、各制御ステップで使用するレジスタ及び変数が決定するため、これに合わせてマルチプレクサを制御するための制御回路用テーブルを生成する。例えば、制御回路用テーブルには、制御ステップと、そのタイミングで制御されるマルチプレクサとが対応付けられている。
【０１１５】
そして、図１３のデータパスのネットリストと制御回路用テーブルが生成されると、図１４に示すような、データパス４００と制御回路４１０を合成した合成回路４２０のＲＴＬが出力される（Ｓ２０７）。
【０１１６】
制御回路用テーブルに基づいて、制御ステップ１，２に対応する制御信号ｓ１、ｓ２を出力する制御回路４１０を生成する。そして、この制御信号ｓ１、ｓ２をデータパス４００のマルチプレクサに供給するように接続する。さらに、制御回路４１０及びデータパス４００にクロックを供給する。
【０１１７】
すなわち、図１４に示すように、この合成回路４２０は、データパス４００と制御回路４１０を有している。
【０１１８】
データパス４００の構成は図１３と同様である。また、データパス４００では、クロックが、レジスタｒ１、ｒ２、ｒ３、ｒ４にそれぞれ供給される。さらに、制御信号ｓ１、ｓ２が、マルチプレクサＭ１、Ｍ２、Ｍ３、Ｍ４にそれぞれ供給される。
【０１１９】
制御回路４１０は、クロックのタイミングごとに"０"と"１"を繰り返す制御信号ｓ２を生成するレジスタｒ５、制御信号ｓ２を反転した制御信号ｓ１を生成するインバータＩＮ１を備えている。
【０１２０】
制御信号ｓ１とｓ２により、ステップ１とステップ２が切り替えられる。例えば、制御信号ｓ１によりステップ１が選択され、制御信号ｓ２によりステップ２が選択される。
【０１２１】
制御信号ｓ１が"１"、制御信号ｓ２が"０"の場合、マルチプレクサＭ１が変数ｘ４を選択してレジスタｒ１に保持され、マルチプレクサＭ２が変数ｙ４を選択してレジスタｒ２に保持され、加算器Ａ１により変数ｘ４と変数ｙ４が加算されて変数ｚ５が出力される。
【０１２２】
次に、制御信号ｓ１が"０"、制御信号ｓ２が"１"の場合、マルチプレクサＭ１が変数ｚ５を選択してレジスタｒ１に保持され、マルチプレクサＭ２が変数ｘ８の下位５ビットを選択してレジスタｒ２に保持され、マルチプレクサＭ３が変数ｘ８の上位３ビットを選択してレジスタｒ３に保持され、加算器Ａ１により変数ｚ５と変数ｘ８が加算される。さらに、マルチプレクサＭ４が加算器Ａ１の出力を選択してレジスタｒ４に保持され、加算器Ａ１の出力結果が変数ｚ９として出力される。
【０１２３】
図１５及び図１６は、図１４の合成回路４２０をＶｅｒｉｌｏｇ−ＨＤＬで記述したＲＴＬ記述の例である。ＲＴＬは、階層構造のモジュール単位に記述されている。例えば、ＲＴＬ情報記憶部２１０に、ＲＴＬ記述のテキストデータが格納される。
【０１２４】
この例では、まず、最上位階層であるトップのトップモジュール記述５０１が記述され、次に、トップモジュールの下位である制御回路の制御回路モジュール記述５０２が記述され、次に、トップモジュールの下位であるデータパスのデータパスモジュール記述５０３が記述されている。制御回路モジュール記述５０２は、図１４の制御回路４１０に対応しており、データパスモジュール記述５０３は、図１４のデータパス４００に対応している。
【０１２５】
トップモジュール記述５０１には、データパスの入出力信号が記述され（５０１ａ）、制御回路の入出力信号が記述されている（５０１ｂ）。
【０１２６】
制御回路モジュール記述５０２には、レジスタｒ５と制御信号ｓ２の関係が記述され（５０２ａ）、レジスタｒ５の反転信号と制御信号ｓ１の関係が記述され（５０２ｂ）、クロックとレジスタｒ５の関係が記述されている（５０２ｃ）。
【０１２７】
データパスモジュール記述５０３には、変数ｘ４、ｙ４、ｘ８、ｚ９のビット幅が記述され（５０３ａ）、レジスタｒ１、ｒ２、ｒ３、ｒ４のビット幅が記述され（５０３ｂ）、レジスタｒ１、ｒ２、ｒ３と加算器の関係が記述され（５０３ｃ）、クロックとレジスタｒ１、ｒ２、ｒ３、ｒ４の関係が記述され（５０３ｄ）、制御信号ｓ１、ｓ２とレジスタｒ１、ｒ２、ｒ３、ｒ４の関係が記述されている（５０３ｅ）。
【０１２８】
ここで、本発明の実施の形態１に係る動作合成方法と従来の動作合成方法とを比較するために、図３２を用いて、従来の動作合成方法によりレジスタをアロケーションする参考例について説明する。
【０１２９】
図３２（ａ）は、図８のライフタイムテーブル３３０に対し、従来の動作合成方法によりレジスタを割り当てたライフタイムテーブル９２０を示している。
【０１３０】
従来の動作合成方法では、ライフタイムの重ならない変数であることのみがレジスタを共有化する条件である。ここでは、変数ｘ４と変数ｚ５とが重ならない２つの変数であり、また、変数ｙ４と変数ｘ８とが重ならない２つの変数である。
【０１３１】
そうすると、図３２（ａ）に示すように、ライフタイムの重ならない変数に一つのレジスタを割り当てる。すなわち、変数ｘ４と変数ｚ５に、ビット幅が大きい変数ｚ５に合わせた５ビットのレジスタｒ１を割り当てる。変数ｙ４と変数ｘ８に、ビット幅が大きい変数ｘ８に合わせた８ビットのレジスタｒ２を割り当てる。変数ｚ９は、共有化できないため、変数ｚ９に合わせた９ビットのレジスタｒ３を割り当てる。
【０１３２】
図３２（ｂ）は、図３２（ａ）のライフタイムテーブル９２０から生成されたデータパス９３０を示している。
【０１３３】
ライフタイムテーブル９２０により割り当てられたレジスタｒ１、ｒ２、ｒ３を加算器Ａ１で接続する。ライフタイムテーブル９２０の制御ステップに応じて共有のレジスタｒ１、ｒ２に入力する変数を切り替えるためにマルチプレクサＭ１、Ｍ２を、レジスタｒ１、ｒ２に接続する。また制御ステップに応じてレジスタｒ３に入力する変数のタイミングを制御するためマルチプレクサＭ３を、レジスタｒ３に接続する。
【０１３４】
すなわち、図３２（ｂ）に示すように、このデータパス９３０は、変数ｘ４と加算器Ａ１の出力である変数ｚ５のいずれかを切り替えてレジスタｒ１へ出力するマルチプレクサＭ１、マルチプレクサＭ１が選択した変数を保持するレジスタｒ１、変数ｙ４と変数ｘ８との入力のいずれかを切り替えてレジスタｒ２へ出力するマルチプレクサＭ２、マルチプレクサＭ２が選択した変数を保持するレジスタｒ２、レジスタｒ１の値とレジスタｒ２の値とを加算する加算器Ａ１、加算器Ａ１の出力をレジスタｒ３へ出力するマルチプレクサＭ３、マルチプレクサＭ３を介した加算器Ａ１の出力を変数ｚ９として保持し出力するレジスタｒ３を備えている。
【０１３５】
図３２のように、従来の動作合成方法によって生成された回路では、ビット幅の異なる値が共有化された後は、ビット幅の大きな変数に合わせて生成されたレジスタの全ビットをアクセスする回路構造となる。このため、下位ビットのみアクセスして演算を行えばよいタイミングにおいても、意味のない上位ビットのために無駄な電力を消費するという問題があった。
【０１３６】
例えば、図３２の回路では、４ビットの変数ｘ４と４ビットの変数ｙ４との加算結果の変数ｚ５は、５ビットのレジスタｒ１に格納されるため、加算器の入力の６ビット目以上は、どのような値をとっても、レジスタｒ１の値が変わることはない。しかしながら、変数ｙ４の値は、８ビットに拡張された上で、８ビットの変数ｘ８と切り替えてアクセスされるため、意味を持たない６ビット目以上のビットに対しても、切り替えが生じ、無駄な電力を消費することになる。
【０１３７】
また、図３２の回路では、４ビットの変数ｙ４の値をレジスタｒ２に取り込む際、５ビット目以上のビットには明示的に"０"が代入される記述となる。例えば、この後の処理で、レジスタｒ２に対してビット単位でクロックゲーティング回路を構成したとしても、変数ｙ４の値をレジスタｒ２に取り込むタイミングでも６ビット目以上にも代入がなされているため、クロックゲーティングの対象とはできず、電力低減の機会が減ることになる。
【０１３８】
このように、従来の動作合成方法では、ビット幅の大きい変数に合わせたビット幅でレジスタを共有化するため、ビット幅の小さい変数にとって未使用のビットが発生することから、共有化するレジスタおよびその入力を切り替えるマルチプレクサのビットが無駄に大きいという問題があった。これにより回路面積が大きくなるという問題も生じる。
【０１３９】
近年、半導体の微細化に伴い、リーク電流によるスタティックな電力消費が無視できなくなってきている。リーク電流は、回路面積が大きいほど大きくなる傾向にあるため、面積が縮小できれば、スタティックな電力消費の削減にもつながる。従来の動作合成方法では、レジスタやマルチプレクサのビットが無駄に大きくなることから、このようなスタティックな電力消費という観点でも、最適化の余地が残るものであった。
【０１４０】
また、従来の動作合成方法では、４ビットの演算の時でも、８ビットの切り替えが生じ、無駄な電力を消費することになる。すなわち、従来の動作合成方法では、ビット幅の小さい変数の値を格納する場合であっても、未使用の無駄なビットを含む、レジスタの全入力ビットを切り替えるためのマルチプレクサを生成しており、これは、切り替えのために消費されるダイナミックな電力消費を削減するという観点においても、最適化の余地が残るものであった。
【０１４１】
さらに、従来の動作合成方法では、未使用ビットにも明示的に値を代入しているため、クロックゲーティングの余地がなく、ダイナミック電力を低減することができないという問題があった。
【０１４２】
これに対し、本実施形態では、上記図１２のライフタイムテーブル３３４のように、ビット幅の異なる変数に対しレジスタ共有化する場合、大きいビット幅の変数を分割して、小さいビット幅の変数に合わせたレジスタを割り当てて共有化し、残りのビットには別のレジスタを割り当てるようにした。
【０１４３】
これにより、図１３のように、変数ｙ４と変数ｘ８との共有化において、ビット幅の小さい変数ｙ４に合わせたビット幅（５ビット）でレジスタが共有されるため、レジスタの入力を切り替えるマルチプレクサのビット幅も、図３２と比べて従来の８ビットよりも小さい５ビットにすることができる。したがって、切り替えるビット数が減る分、マルチプレクサの面積が小さくなり、それに比例してリーク電流も少なく出来るため、スタティックな電力消費を低減することができる。また、マルチプレクサの切り替え時の未使用ビットの切り替えを削減することができ、ダイナミックな消費電力を低減することができる。
【０１４４】
また、変数ｘ８を分割して残った上位ビットの部分は、共有のレジスタとは別のレジスタｒ３に割り当てられる。このため、変数ｙ４の値の取り込みタイミングとは無関係にクロックゲーティングができるようになり、ダイナミックな消費電力をより一層低減することが可能となる。
【０１４５】
（本発明の実施の形態２）
以下、図面を参照して本発明の実施の形態２ついて説明する。図１７は、本発明の実施の形態２に係る動作合成装置の機能構成を示している。
【０１４６】
図１７の動作合成装置２００は、図２の構成と比べて、ＲＴＬ出力部のみが異なっている。その他の構成は同様である。すなわち、本実施形態の動作合成装置２００は、実施の形態１のＲＴＬ出力部２０９に代えて、クロックゲーティング及びＲＴＬ出力部２１１を有している。
【０１４７】
クロックゲーティング及びＲＴＬ出力部２１１は、制御回路用テーブル記憶部２０７に記憶された制御回路用テーブルと、ネットリスト記憶部２０８に記憶されたデータパスのネットリストとに基づいて、クロックゲーティングを含む合成回路のＲＴＬ情報を生成し、出力する。
【０１４８】
図１８は、クロックゲーティング及びＲＴＬ出力部２１１が生成した合成回路４２０の例である。図１８の合成回路４２０は、図１４の構成と比べて、制御回路４１０は同じ構成であり、データパス４００は、マルチプレクサＭ３、Ｍ４に代えて、クロックゲーティングＬ１、Ｌ２を有している。
【０１４９】
このクロックゲーティングＬ１，Ｌ２は論理和回路で構成され、クロックゲーティングＬ１，Ｌ２は、レジスタｒ３、ｒ４に供給されるクロックの変動を抑える。クロックゲーティングＬ１は、クロックと制御信号ｓ２とを論理和演算してレジスタｒ３のクロック端子へ供給する。クロックゲーティングＬ２は、クロックと制御信号ｓ１とを論理和演算してレジスタｒ４のクロック端子へ供給する。
【０１５０】
図１９のタイミングチャートは、図１８の合成回路４２０の動作を示している。制御信号ｓ１、ｓ２は、クロックごとのタイミングで"０"と"１"を交互に繰り返し、これに応じてステップ１とステップ２が繰り返される。
【０１５１】
ステップ１では、レジスタｒ１に変数ｘ４が保持され、レジスタｒ２に変数ｙ４が保持され、加算器Ａ１が変数ｘ４と変数ｙ４とを加算し、変数ｚ５を出力する。ステップ２では、レジスタｒ１に変数ｚ５が保持され、レジスタｒ２に変数ｘ８の下位ビットが保持され、レジスタｒ３に変数ｘ８の上位ビットが保持され、加算器Ａ１が変数ｚ５と変数ｘ８の上位ビット及び下位ビットとを加算し、変数ｚ９を出力する。
【０１５２】
ここで、レジスタｒ３では、ステップ２においてのみ変数ｘ８を使用するため、ステップ１のタイミングではクロックをゲーティングしてレジスタｒ３をラッチ動作させず、ステップ２のみクロックを供給してレジスタｒ２をラッチ動作させる。なお、図１４の構成のようにクロックゲーティングしない場合には、レジスタｒ３は、変数ｘ８と"０"とをクロック毎に交互に格納する。
【０１５３】
また、レジスタｒ４では、ステップ２の次のステップにおいてのみ変数ｚ９の値が確定するため、ステップ２のタイミングではクロックをゲーティングしてレジスタｒ４をラッチ動作させず、ステップ２の次のステップ（ここではステップ１）のみクロックを供給してレジスタｒ４をラッチ動作させる。図１９のように、レジスタｒ３、ｒ４に供給されるクロックが半分になるため、レジスタｒ３、ｒ４のダイナミックな消費電力を半分に減らすことができる。
【０１５４】
このように、本実施形態では、変数を保持するレジスタにクロックゲーティングを行うことで、消費電力を低減することができる。特に、従来、レジスタ共有によりクロックゲーティングが不可能な場合があったが、実施の形態１で説明したように、ビット幅の大きい変数を上位ビットと下位ビットに分割して、別のレジスタに割り当てているため、上位ビットのレジスタをクロックゲーティングができるようになり、消費電力を確実に低減することができる。
【０１５５】
（本発明の実施の形態３）
以下、図面を参照して本発明の実施の形態３ついて説明する。実施の形態１では、記憶ユニットのアロケーション処理において、ライフタイムの重ならない２つの変数に着目して、レジスタの割り当てを行った。これに対し、本実施形態では、ライフタイムの重ならない２以上の変数に着目して、レジスタを割り当てる。記憶ユニットのアロケーション以外については、実施の形態１，２と同様である。
【０１５６】
図２０は、本発明の実施の形態３に係る記憶ユニットのアロケーション処理（Ｓ２０４）の流れを示している。
【０１５７】
図に示されるように、まず、ライフタイム計算部２２１は、ＣＤＦＧ上で状態を横切る各変数についてライフタイムを計算し（Ｓ４０１）、変数選択部２２２は、ライフタイムの重ならない２つ以上の変数及びレジスタに着目する（Ｓ４０２）。次いで、ビット幅検出部２２３は、着目した全ての変数のビット幅が同じかどうか判定する（Ｓ４０３）。
【０１５８】
Ｓ４０３において、ビット幅が異なると判定された場合、変数選択部２２２は、着目した変数の中から２つの変数を選ぶ（Ｓ４０４）。２つの変数を選んだ後は、実施の形態１と同様に、図５のＳ３０３〜Ｓ３０８の処理を行う。
【０１５９】
すなわち、選択した２つの変数のビット幅が異なるかどうか判定し（Ｓ３０３）、ビット幅が異なる場合、ビット幅が小さい変数を必要最小限に符号拡張し（Ｓ３０４）、符号拡張した２つの変数のビット幅が異なるかどうか判定し（Ｓ３０５）、ビット幅が異なる場合、ビット幅が大きい変数をビット幅が小さい変数の幅に合わせて上位ビットと下位ビットにビット分割し（Ｓ３０６）、ビット幅が小さい変数とビット幅が大きい変数の下位ビットとを同じレジスタに割り当て（Ｓ３０７）、ビット幅が大きい変数の上位ビットを別のレジスタに割り当てる（Ｓ３０８）。
【０１６０】
Ｓ４０３において、着目した全ての変数のビット幅が同じ場合、Ｓ３０３、Ｓ３０５において、選択した２つの変数のビット幅が同じ場合、着目した全ての変数もしくは選択した２つの変数に、同じレジスタを割り当てる（Ｓ４０５）。
【０１６１】
Ｓ３０８またはＳ４０５のレジスタ割り当ての後、レジスタ割り当て部２２６は、割り当てたレジスタと残った変数とを着目対象とする。
【０１６２】
次いで、レジスタ割り当て部２２６は、共有化の余地があるかどうか判定する（Ｓ４０７）。現在着目している複数の変数において、割り当てたレジスタも含めて、共有化する余地があるかどうか判定する。Ｓ４０７において、共有化の余地があると判定された場合、Ｓ４０３以降の処理を繰り返し、さらに２つの変数を選択して共有化を行う。
【０１６３】
Ｓ４０７において、共有化の余地がないと判定された場合、レジスタ割り当て部２２６は、さらなるレジスタ共有化の余地があるかどうか判定する（Ｓ４０８）。Ｓ４０８において、レジスタ共有化の余地があると判定された場合、Ｓ４０２以降の処理を繰り返す。また、Ｓ４０８において、レジスタ共有化の余地がないと判定された場合、レジスタ割り当て部２２６は、残った変数があれば全てレジスタに割り当てて、処理を終了する（Ｓ４０９）。
【０１６４】
このように、本実施形態では、記憶ユニットのアロケーションにあたり、ライフタイムの重ならない２つ以上の変数に着目し、ビット幅が異なる場合は、２つの変数を選択してレジスタの割り当てを行うようにした。これにより、ライフタイムの重ならない変数が２つ以上ある場合でも、実施の形態１と同様にレジスタを共有化することができる。
【０１６５】
（本発明の実施の形態４）
以下、図面を参照して本発明の実施の形態４ついて説明する。実施の形態３では、記憶ユニットアロケーション処理において、ライフタイムの重ならない２つ以上の変数に着目し、さらに２つの変数を選択してレジスタの割り当てを行った。これに対し、本実施形態では、ライフタイムの重ならない２以上の変数に着目して、その着目した２つ以上の変数に対しレジスタを割り当てる。記憶ユニットのアロケーション以外については、実施の形態１，２と同様である。
【０１６６】
図２１は、本発明の実施の形態４に係る記憶ユニットのアロケーション処理（Ｓ２０４）の流れを示している。
【０１６７】
図に示されるように、まず、ライフタイム計算部２２１は、ＣＤＦＧ上で状態を横切る各変数についてライフタイムを計算し（Ｓ５０１）、変数選択部２２２は、ライフタイムの重ならない２つ以上の変数及びレジスタに着目する（Ｓ５０２）。次いで、ビット幅検出部２２３は、着目した変数が全て同じビット幅かどうか判定する（Ｓ５０３）。
【０１６８】
Ｓ５０３において、全ての変数のビット幅が同じではないと判定された場合、符号拡張部２２４は、ビット幅が最大の変数以外の変数を、必要最小限に符号拡張する（Ｓ５０４）。次いで、ビット幅検出部２２３は、符号拡張後の着目した変数が全て同じビット幅かどうか判定する（Ｓ５０５）。
【０１６９】
Ｓ５０５において、全ての変数のビット幅が同じではないと判定された場合、変数分割部２２５は、ビット幅が最小の変数のビット幅に合わせて、その他の変数を上位ビットと下位ビットにビット分割する（Ｓ５０６）。次いで、レジスタ割り当て部２２６は、ビット幅が最小の変数とその他の変数の下位ビットとを同じレジスタに割り当てる（Ｓ５０７）。
【０１７０】
次いで、レジスタ割り当て部２２６は、分割したその他の変数の上位ビットを新たな着目対象とする（Ｓ５０８）。その後、Ｓ５０５以降を繰り返し、分割した残りの変数に対し、レジスタの割り当てを行う。
【０１７１】
Ｓ５０３またはＳ５０５において、着目した変数が全て同じビット幅である場合、レジスタ割り当て部２２６は、着目した全ての変数を同じレジスタに割り当てる（Ｓ５０９）。
【０１７２】
次いで、レジスタ割り当て部２２６は、さらなるレジスタ共有化の余地があるかどうか判定する（Ｓ５１０）。Ｓ５１０において、レジスタ共有化の余地があると判定された場合、Ｓ５０２以降の処理を繰り返す。また、Ｓ５１０において、レジスタ共有化の余地がないと判定された場合、レジスタ割り当て部２２６は、残った変数があれば全てレジスタに割り当てて、処理を終了する（Ｓ５１１）。
【０１７３】
次に、図２２〜図２７を用いて、本発明の実施の形態４に係る動作合成方法の具体例について説明する。
【０１７４】
まず、動作合成方法Ｓ２００の処理が開始されると、図２２（ａ）の動作記述６００をパーズして、図２２（ｂ）のＣＤＦＧが生成される（Ｓ２０１）。
【０１７５】
この動作記述６００では、変数宣言記述部６０１に変数ｘ４、ｙ４、ｘ８、ｚ５、ｚ９、ｘ１６、ｚ１７が定義され、演算記述部６０２に、これらの変数を使用した式６０２ａ、式６０２ｂ、式６０２ｃが記述されている。
【０１７６】
動作記述６００をパーズすると、図２２（ｂ）に示すように、加算１の演算が、式６０２ａに対応しており、４ビットの変数ｘ４と４ビットの変数ｙ４を加算して５ビットの変数ｚ５へ出力することを表し、加算２の演算が、式６０２ｂに対応しており、５ビットの変数ｚ５と８ビットの変数ｘ８を加算して９ビットの変数ｚ９へ出力することを表し、加算３の演算が、式６０２ｃに対応しており、９ビットの変数ｚ９と１６ビットの変数ｘ１６を加算して１７ビットの変数ｚ１７へ出力することを表すＣＤＦＧ６１０が生成される。
【０１７７】
次に、図２３（ａ）に示すように、図２２（ｂ）のＣＤＦＧに対し制御ステップに区切ってスケジューリングが行われ、スケジューリングのＣＤＦＧ６１１が生成される（Ｓ２０２）。
【０１７８】
この例では、ステップ１において、変数ｘ４と変数ｙ４とを加算して変数ｚ５へ出力する加算１の処理を実行し、次のステップ２において、変数ｚ５と変数ｘ８とを加算して変数ｚ９を出力する加算２の処理を実行し、次のステップ３において、変数ｚ９と変数ｘ１６とを加算して変数ｚ１７を出力する加算３の処理を実行するようにスケジュールする。
【０１７９】
次に、図２３（ａ）のスケジューリング後のＣＤＦＧ６１１から、各変数のライフタイムを計算し、図２３（ｂ）に示すライフタイムテーブル６２０を生成する（Ｓ５０１）。
【０１８０】
この例では、変数ｘ４、ｙ４は、ステップ１より前のステップからステップ１までがライフタイムであり、変数ｘ８、ｚ５は、ステップ１からステップ２までがライフタイムであり、変数ｘ１６、ｚ９は、ステップ２からステップ３までがライフタイムであり、変数ｚ１７は、全期間がライフタイムである。
【０１８１】
次に、図２４（ａ）に示すように、変数ｘ４と変数ｚ５と変数ｚ９とでライフタイムが重ならないため、変数ｘ４、変数ｚ５、変数ｚ９に着目する（Ｓ５０２）。変数ｘ４は４ビットであり、変数ｚ５は５ビットであり、変数ｚ９は９ビットであり、ビット幅が異なるため、ビット幅が最大ではない、変数ｘ４、変数ｚ５の変数を最小限に符号拡張し５ビットと９ビットとする（Ｓ５０４）。ビット幅最小の変数ｘ４のビット幅５に合わせて、変数ｚ５を上位４ビットと下位５ビットに分割し、変数ｚ９を上位４ビットと下位５ビットに分割する（Ｓ５０６）。
【０１８２】
そして、図２４（ｂ）に示されるように、ビット幅最小の変数ｘ４と、変数ｚ５の下位ビット、変数ｚ９の下位ビットに同じレジスタｒ１を割り当てる（Ｓ５０７）。さらに、分割した変数ｚ５の上位４ビットと、変数ｚ９の上位４ビットを着目対象とし（Ｓ５１１）、両者はビットが同じであるため、変数ｚ５の上位４ビットと、変数ｚ９の上位４ビットに同じレジスタｒ２を割り当てる（Ｓ５０９）。
【０１８３】
変数ｘ４、変数ｚ５、変数ｚ９にレジスタを割り当てた後、図２５（ａ）に示すように、変数ｙ４と変数ｘ８と変数ｘ１６とでライフタイムが重ならず、レジスタ共有化の余地があるため、変数ｙ４、変数ｘ８、変数ｘ１６に着目する（Ｓ５０２）。
【０１８４】
変数ｙ４は４ビットであり、変数ｘ８は８ビットであり、変数ｘ１６は１６ビットであり、ビット幅が異なるため、ビット幅が最大ではない、変数ｙ４、変数ｘ８の変数を最小限に符号拡張し５ビットと９ビットとする（Ｓ５０４）。
【０１８５】
そして、ビット幅最小の変数ｙ４のビット幅５に合わせて、変数ｘ８を上位４ビットと下位５ビットに分割し、変数ｘ１６を上位１１ビットと下位５ビットに分割する（Ｓ５０６）。図２５（ｂ）のように、ビット幅最小の変数ｙ４と、変数ｘ８の下位ビット、変数ｘ１６の下位ビットに同じレジスタｒ３を割り当てる（Ｓ５０７）。
【０１８６】
さらに、分割した変数ｘ８の上位４ビットと、変数ｘ１５の上位１１ビットを着目対象とする（Ｓ５１１）。ビット幅の小さい変数ｘ８の４ビットに合わせて、変数ｘ１５の上位１１ビットを上位７ビットと下位４ビットに分割する（Ｓ５０６）。図２５（ｂ）のように、ビット幅の小さい変数ｘ８の上位４ビットと、変数ｘ１６の下位ビットに同じレジスタｒ４を割り当てる（Ｓ５０７）。さらに、残りの変数ｘ１６の上位７ビットにレジスタｒ５を割り当てる。
【０１８７】
次に、変数ｚ１７が残っているが、レジスタ共有化の余地がないため、図２６（ａ）に示すように変数ｚ１７に着目し、図２６（ｂ）に示すように、変数ｚ１７にレジスタｒ６を割り当て（Ｓ５１１）、処理が終了する。
【０１８８】
図２７は、図２６のライフタイムテーブル６２３から生成されたデータパス７００の構成を示している。データパス７００では、ライフタイムテーブル６２３により割り当てられたレジスタｒ１〜ｒ６を加算器Ａ１で接続する。ライフタイムテーブル６２３の制御ステップに応じて共有のレジスタｒ１〜ｒ４に入力する変数を切り替えるためにマルチプレクサＭ１〜Ｍ４を、レジスタｒ１〜ｒ４に接続する。また制御ステップに応じてレジスタｒ５、ｒ６に入力する変数のタイミングを制御するためマルチプレクサＭ５、Ｍ６を、レジスタｒ５、ｒ６に接続する。
【０１８９】
すなわち、このデータパス７００は、変数ｘ４と、加算器Ａ１の出力である変数ｚ５と、加算器Ａ１の出力である変数ｚ９の下位ビットのいずれかを切り替えて出力するマルチプレクサＭ１、マルチプレクサＭ１が選択した変数を保持するレジスタｒ１、変数ｚ５の上位ビット（４ビットの"０"）と、変数ｚ９の上位ビットのいずれかを切り替えて出力するマルチプレクサＭ２、マルチプレクサＭ２が選択した変数を保持するレジスタｒ２、変数ｙ４と、変数ｘ８の下位ビットと、変数ｘ１６の下位ビットのいずれかを切り替えて出力するマルチプレクサＭ３、マルチプレクサＭ３が選択した変数を保持するレジスタｒ３、変数ｘ８の上位ビットと、変数ｘ１６の中間ビットのいずれかを切り替えて出力するマルチプレクサＭ４、マルチプレクサＭ４が選択した変数を保持するレジスタｒ４、変数ｘ１６の上位ビットをレジスタｒ５へ出力するマルチプレクサＭ５、マルチプレクサＭ５を介した変数ｘ１６の上位ビットを保持するレジスタｒ５、レジスタｒ１及びｒ２の値と、レジスタｒ３、ｒ４及びｒ５の値とを加算する加算器Ａ１、加算器Ａ１の出力をレジスタｒ６へ出力するマルチプレクサＭ６、マルチプレクサＭ６を介した加算器Ａ１の出力を変数ｚ９として保持するレジスタｒ６を備えている。
【０１９０】
このように、本実施形態では、記憶ユニットのアロケーションにあたり、ライフタイムの重ならない２つ以上の変数に着目し、最小のビット幅の変数に合わせて複数の変数を分割してレジスタの割り当てを行うようにした。
【０１９１】
これにより、ライフタイムの重ならない変数が２つ以上ある場合でも、実施の形態１と同様に共有化するレジスタのビット幅を小さくすることができる。
【０１９２】
また、実施の形態１と同様に、マルチプレクサの面積が小さくなり、スタティック電力を低減することができる。さらに、切り替え時の（ダイナミックな）消費電力を低減することができる。また、クロックゲーティングできる余地が増え、さらに消費電力を低減することが可能となる。
【０１９３】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【０１９４】
１００ コンピュータシステム
１０１ 本体部
１０３ メインメモリ
１０４ ハードディスク
１０５ 表示装置
１０６ キーボード
１０７ マウス
１０８ 動作合成プログラム
１０９ 各種データ
２００ 動作合成装置
２０１ 動作記述情報記憶部
２０２ パーズ処理部
２０３ 内部表現情報記憶部
２０４ スケジューリング処理部
２０５ アロケーション処理部
２０５ａ 機能ユニットアロケーション部
２０５ｂ 記憶ユニットアロケーション部
２０５ｃ 通信ユニットアロケーション部
２０６ 制御回路用テーブル及びネットリスト生成部
２０７ 制御回路用テーブル記憶部
２０８ ネットリスト記憶部
２０９ ＲＴＬ出力部
２１０ ＲＴＬ情報記憶部
２１１ クロックゲーティング及びＲＴＬ出力部
２２１ ライフタイム計算部
２２２ 変数選択部
２２３ ビット幅検出部
２２４ 符号拡張部
２２５ 変数分割部
２２６ レジスタ割り当て部
【特許請求の範囲】
【請求項１】
変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、
前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、
前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択し、
前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、
前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、
前記第１及び第２のレジスタを有する合成回路の回路情報を出力する、
動作合成方法。
【請求項２】
前記第１のレジスタの割り当ては、前記その他の変数を、前記第１のビット幅のビットと、前記第１のビット幅のビット以外のビットとに分割して、前記分割した前記第１のビット幅のビットに、前記第１のレジスタを割り当て、
前記第２のレジスタの割り当ては、前記分割した前記第１のビット幅のビット以外のビットに、前記第２のレジスタを割り当てる、
請求項１に記載の動作合成方法。
【請求項３】
前記第１のビット幅は、前記第１の変数の符号情報を示すビットを含めたビット幅として定義されている、
請求項１または２に記載の動作合成方法。
【請求項４】
前記第１のビット幅は、前記動作記述情報に記載された前記第１の変数に対して符号拡張したビット幅として定義されている、
請求項１乃至３のいずれか一項に記載の動作合成方法。
【請求項５】
前記第１のビット幅は、前記第１の変数の演算結果のビット幅に合わせて定義されている、
請求項４に記載の動作合成方法。
【請求項６】
前記その他の変数内の前記第１のビット幅のビットは、前記その他の変数の下位ビットである、
請求項１乃至５のいずれか一項に記載の動作合成方法。
【請求項７】
前記その他の変数内の前記第１のビット幅のビット以外のビットは、前記その他の変数の上位ビットである、
請求項１乃至６のいずれか一項に記載の動作合成方法。
【請求項８】
前記ｍ個の変数から２個の変数を特定し、
前記第１の変数は、前記特定した２個の変数のうちビット幅が小さい変数であり、
前記その他の変数は、前記特定した２個の変数のうちビット幅が大きい変数である、
請求項１乃至７のいずれか一項に記載の動作合成方法。
【請求項９】
前記第１の変数は、前記ｍ個の変数のうちビット幅が最小の変数である、
請求項１乃至８のいずれか一項に記載の動作合成方法。
【請求項１０】
前記第１の変数のデータもしくは前記その他の変数のデータのいずれかを切り替えて、前記第１のレジスタに入力するマルチプレクサを、前記合成回路に割り当てる、
請求項１乃至９のいずれか一項に記載の動作合成方法。
【請求項１１】
前記第２のレジスタに供給されるクロックを非活性にするクロックゲーティング回路を、前記合成回路に割り当てる、
請求項１乃至１０のいずれか一項に記載の動作合成方法。
【請求項１２】
前記ｍは２である、
請求項１乃至１１のいずれか一項に記載の動作合成方法。
【請求項１３】
変数の演算動作を含む動作記述情報から、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、
前記スケジューリングされたデータフローグラフ情報から、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、
前記ライフタイム情報が時間軸上で重ならない、第１のビット幅として定義された第１の変数と、第２の変数とを選択し、
前記第１の変数と、前記第２の変数に含まれる前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、
前記第２の変数に含まれる前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、
前記第１及び第２のレジスタを有する合成回路の回路情報を出力する、
動作合成方法。
【請求項１４】
コンピュータに動作合成処理を実行させる動作合成プログラムであって、前記動作合成処理は、
変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、
前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、
前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択し、
前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、
前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、
前記第１及び第２のレジスタを有する合成回路の回路情報を出力する、
動作合成プログラム。
【請求項１５】
前記第１のレジスタの割り当ては、前記その他の変数を、前記第１のビット幅のビットと、前記第１のビット幅のビット以外のビットとに分割して、前記分割した前記第１のビット幅のビットに、前記第１のレジスタを割り当て、
前記第２のレジスタの割り当ては、前記分割した前記第１のビット幅のビット以外のビットに、前記第２のレジスタを割り当てる、
請求項１４に記載の動作合成プログラム。
【請求項１６】
前記ｍは２である、
請求項１４または１５に記載の動作合成プログラム。
【請求項１７】
変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成するスケジューリング部と、
前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成するライフタイム生成部と、
前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択する変数選択部と、
前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当てるレジスタ割り当て部と、
前記第１及び第２のレジスタを有する合成回路の回路情報を出力する回路情報出力部と、
を備える動作合成装置。
【請求項１８】
前記レジスタ割り当て部は、前記その他の変数を、前記第１のビット幅のビットと、前記第１のビット幅のビット以外のビットとに分割して、前記分割した前記第１のビット幅のビットに、前記第１のレジスタを割り当て、前記分割した前記第１のビット幅のビット以外のビットに、前記第２のレジスタを割り当てる、
請求項１７に記載の動作合成装置。
【請求項１９】
前記ｍは２である、
請求項１７または１８に記載の動作合成装置。
【請求項１】
変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、
前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、
前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択し、
前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、
前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、
前記第１及び第２のレジスタを有する合成回路の回路情報を出力する、
動作合成方法。
【請求項２】
前記第１のレジスタの割り当ては、前記その他の変数を、前記第１のビット幅のビットと、前記第１のビット幅のビット以外のビットとに分割して、前記分割した前記第１のビット幅のビットに、前記第１のレジスタを割り当て、
前記第２のレジスタの割り当ては、前記分割した前記第１のビット幅のビット以外のビットに、前記第２のレジスタを割り当てる、
請求項１に記載の動作合成方法。
【請求項３】
前記第１のビット幅は、前記第１の変数の符号情報を示すビットを含めたビット幅として定義されている、
請求項１または２に記載の動作合成方法。
【請求項４】
前記第１のビット幅は、前記動作記述情報に記載された前記第１の変数に対して符号拡張したビット幅として定義されている、
請求項１乃至３のいずれか一項に記載の動作合成方法。
【請求項５】
前記第１のビット幅は、前記第１の変数の演算結果のビット幅に合わせて定義されている、
請求項４に記載の動作合成方法。
【請求項６】
前記その他の変数内の前記第１のビット幅のビットは、前記その他の変数の下位ビットである、
請求項１乃至５のいずれか一項に記載の動作合成方法。
【請求項７】
前記その他の変数内の前記第１のビット幅のビット以外のビットは、前記その他の変数の上位ビットである、
請求項１乃至６のいずれか一項に記載の動作合成方法。
【請求項８】
前記ｍ個の変数から２個の変数を特定し、
前記第１の変数は、前記特定した２個の変数のうちビット幅が小さい変数であり、
前記その他の変数は、前記特定した２個の変数のうちビット幅が大きい変数である、
請求項１乃至７のいずれか一項に記載の動作合成方法。
【請求項９】
前記第１の変数は、前記ｍ個の変数のうちビット幅が最小の変数である、
請求項１乃至８のいずれか一項に記載の動作合成方法。
【請求項１０】
前記第１の変数のデータもしくは前記その他の変数のデータのいずれかを切り替えて、前記第１のレジスタに入力するマルチプレクサを、前記合成回路に割り当てる、
請求項１乃至９のいずれか一項に記載の動作合成方法。
【請求項１１】
前記第２のレジスタに供給されるクロックを非活性にするクロックゲーティング回路を、前記合成回路に割り当てる、
請求項１乃至１０のいずれか一項に記載の動作合成方法。
【請求項１２】
前記ｍは２である、
請求項１乃至１１のいずれか一項に記載の動作合成方法。
【請求項１３】
変数の演算動作を含む動作記述情報から、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、
前記スケジューリングされたデータフローグラフ情報から、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、
前記ライフタイム情報が時間軸上で重ならない、第１のビット幅として定義された第１の変数と、第２の変数とを選択し、
前記第１の変数と、前記第２の変数に含まれる前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、
前記第２の変数に含まれる前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、
前記第１及び第２のレジスタを有する合成回路の回路情報を出力する、
動作合成方法。
【請求項１４】
コンピュータに動作合成処理を実行させる動作合成プログラムであって、前記動作合成処理は、
変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成し、
前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成し、
前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択し、
前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、
前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当て、
前記第１及び第２のレジスタを有する合成回路の回路情報を出力する、
動作合成プログラム。
【請求項１５】
前記第１のレジスタの割り当ては、前記その他の変数を、前記第１のビット幅のビットと、前記第１のビット幅のビット以外のビットとに分割して、前記分割した前記第１のビット幅のビットに、前記第１のレジスタを割り当て、
前記第２のレジスタの割り当ては、前記分割した前記第１のビット幅のビット以外のビットに、前記第２のレジスタを割り当てる、
請求項１４に記載の動作合成プログラム。
【請求項１６】
前記ｍは２である、
請求項１４または１５に記載の動作合成プログラム。
【請求項１７】
変数の演算動作を含む動作記述情報に基づいて、前記変数の演算動作のタイミングをスケジューリングしたデータフローグラフ情報を生成するスケジューリング部と、
前記スケジューリングされたデータフローグラフ情報に基づいて、前記変数でデータの保持が必要な期間であるライフタイム情報を前記変数毎に生成するライフタイム生成部と、
前記ライフタイム情報が時間軸上で重ならないｍ個（ｍは２以上の整数）の変数を選択する変数選択部と、
前記ｍ個の変数に含まれる第１のビット幅として定義された第１の変数と、前記ｍ個の変数に含まれるその他の変数内の前記第１のビット幅のビットとに、前記第１のビット幅の第１のレジスタを割り当て、前記その他の変数内の前記第１のビット幅のビット以外のビットに、第２のレジスタを割り当てるレジスタ割り当て部と、
前記第１及び第２のレジスタを有する合成回路の回路情報を出力する回路情報出力部と、
を備える動作合成装置。
【請求項１８】
前記レジスタ割り当て部は、前記その他の変数を、前記第１のビット幅のビットと、前記第１のビット幅のビット以外のビットとに分割して、前記分割した前記第１のビット幅のビットに、前記第１のレジスタを割り当て、前記分割した前記第１のビット幅のビット以外のビットに、前記第２のレジスタを割り当てる、
請求項１７に記載の動作合成装置。
【請求項１９】
前記ｍは２である、
請求項１７または１８に記載の動作合成装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【公開番号】特開２０１３−１０９４３８（Ｐ２０１３−１０９４３８Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５２２６３（Ｐ２０１１−２５２２６３）
【出願日】平成２３年１１月１８日（２０１１．１１．１８）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月１８日（２０１１．１１．１８）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
[ Back to top ]