(57)【要約】【課題】  回路性能の低下をさせることなく、1状態からの状態遷移数を制約できる動作合成を可能にする。【解決手段】  半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムにおいて、1状態からの状態遷移数を制約する状態遷移数制御手段２４を備える。【選択図】  図１
2009122812.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムにおいて、
1状態からの状態遷移数を制約する手段を備えることを特徴とする動作合成システム。
【請求項２】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムにおいて、
スケジューリング・バインディング処理において1状態からの状態遷移数を制約する手段を備えることを特徴とする動作合成システム。
【請求項３】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムにおいて、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理手段と、
前記前処理手段により生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング手段と、
前記スケジューリング・バインディング手段により生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理手段と、
前記スケジューリング・バインディング手段による処理において1状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御手段と
を備えることを特徴とする動作合成システム。
【請求項４】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムにおいて、
スケジューリング・バインディング処理後の処理において1状態からの状態遷移数を制約する手段を備えることを特徴とする動作合成システム。
【請求項５】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムにおいて、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理手段と、
前記前処理手段により生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング手段と、
前記スケジューリング・バインディング手段により生成された内部表現に対してデータパス・ＦＳＭを生成すると共に、１状態からの状態遷移数が制約数を超えている場合に処理を何も行わない空の状態を生成するＦＳＭ生成・調整手段と、
前記ＦＳＭ生成・調整手段により生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理手段と、
前記ＦＳＭ生成・調整手段による処理において１状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御手段と
を備えることを特徴とする動作合成システム。
【請求項６】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムにおいて、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理手段と、
前記前処理手段により生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング手段と、
前記スケジューリング・バインディング手段により生成された内部表現に対してデータパス・ＦＳＭを生成すると共に、１状態からの状態遷移数が制約数を超えている場合に複数の状態を結合した新しい状態を生成するＦＳＭ生成・調整手段と、
前記ＦＳＭ生成・調整手段により生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理手段と、
前記ＦＳＭ生成・調整手段による処理において１状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御手段と
を備えることを特徴とする動作合成システム。
【請求項７】
前記前処理手段により生成された内部表現においてループを含む静的な構造から遷移確率の高い遷移を推定する手段を有し、当該推定を前記状態遷移数制御手段の制御に用いることを特徴とする請求項３、請求項５又は請求項６に記載の動作合成システム。
【請求項８】
前記抽象度の低い回路記述出力をシミュレーション及び実チップで動作させ、各状態での状態遷移確率を取得・解析する動作解析手段を備え、前期動作解析手段による前記各状態での状態遷移確率を前記状態遷移数制御手段の制御に用いることを特徴とする請求項３、請求項５又は請求項６に記載の動作合成システム。
【請求項９】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムの動作合成方法であって、
スケジューリング・バインディング処理において１状態からの状態遷移数を制約する処理を含むことを特徴とする動作合成方法。
【請求項１０】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムの動作合成方法であって、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理と、
前記前処理で生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング処理と、
前記スケジューリング・バインディング処理で生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理と、
前記スケジューリング・バインディング処理において１状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御処理と
を含むことを特徴とする動作合成方法。
【請求項１１】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムの動作合成方法であって、
スケジューリング・バインディング処理後の処理において１状態からの状態遷移数を制約する処理を含むことを特徴とする動作合成方法。
【請求項１２】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムの動作合成方法であって、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理と、
前記前処理で生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング処理と、
前記スケジューリング・バインディング処理で生成された内部表現に対してデータパス・ＦＳＭを生成すると共に、１状態からの状態遷移数が制約数を超えている場合に処理を何も行わない空の状態を生成するＦＳＭ生成・調整処理と、
前記ＦＳＭ生成・調整処理で生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理と、
前記ＦＳＭ生成・調整処理において１状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御処理と
を含むことを特徴とする動作合成方法。
【請求項１３】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムの動作合成方法であって、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理と、
前記前処理で生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング処理と、
前記スケジューリング・バインディング処理で生成された内部表現に対してデータパス・ＦＳＭを生成すると共に、１状態からの状態遷移数が制約数を超えている場合に複数の状態を結合した新しい状態を生成するＦＳＭ生成・調整処理と、
前記ＦＳＭ生成・調整処理で生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理と、
前記ＦＳＭ生成・調整処理において１状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御処理と
を含むことを特徴とする動作合成方法。
【請求項１４】
前記前処理で生成された内部表現においてループを含む静的な構造から遷移確率の高い遷移を推定し、前記推定を用いて前記状態遷移数制御処理を行うことを特徴とする請求項１０、請求項１２又は請求項１３に記載の動作合成方法。
【請求項１５】
前記抽象度の低い回路記述出力をシミュレーション及び実チップで動作させ、各状態での状態遷移確率を取得・解析する動作解析を行い、前記各状態での状態遷移確率により前記状態遷移数制御処理を行うことを特徴とする請求項１０、請求項１２又は請求項１３に記載の動作合成方法。
【請求項１６】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムのコンピュータ上で動作するプログラムであって、
前記コンピュータに、
スケジューリング・バインディング処理において１状態からの状態遷移数を制約する処理を実行させることを特徴とするプログラム。
【請求項１７】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムのコンピュータ上で動作するプログラムであって、
前記コンピュータに、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理と、
前記前処理で生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング処理と、
前記スケジューリング・バインディング処理で生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理と、
前記スケジューリング・バインディング処理において１状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御処理を実行させることを特徴とするプログラム。
【請求項１８】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムのコンピュータ上で動作するプログラムであって、
前記コンピュータに、
スケジューリング・バインディング処理後の処理において１状態からの状態遷移数を制約する処理を実行させることを特徴とするプログラム。
【請求項１９】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムのコンピュータ上で動作するプログラムであって、
前記コンピュータに、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理と、
前記前処理で生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング処理と、
前記スケジューリング・バインディング処理で生成された内部表現に対してデータパス・ＦＳＭを生成すると共に、１状態からの状態遷移数が制約数を超えている場合に処理を何も行わない空の状態を生成するＦＳＭ生成・調整処理と、
前記ＦＳＭ生成・調整処理で生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理と、
前記ＦＳＭ生成・調整処理において１状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御処理を実行させることを特徴とするプログラム。
【請求項２０】
半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムのコンピュータ上で動作するプログラムであって、
前記コンピュータに、
前記動作レベルの回路記述を解析し、動作合成用の内部表現への変換や最適化を実行する前処理と、
前記前処理で生成された内部表現を用い各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際に使用する演算器やメモリを決定するスケジューリング・バインディング処理と、
前記スケジューリング・バインディング処理で生成された内部表現に対してデータパス・ＦＳＭを生成すると共に、１状態からの状態遷移数が制約数を超えている場合に複数の状態を結合した新しい状態を生成するＦＳＭ生成・調整処理と、
前記ＦＳＭ生成・調整処理で生成された内部表現に対して抽象度の低い回路記述を生成して出力する後処理と、
前記ＦＳＭ生成・調整処理において１状態からの状態遷移数が制約を超えないよう制御する状態遷移数制御処理を実行させることを特徴とするプログラム。
【請求項２１】
前記前処理で生成された内部表現においてループを含む静的な構造から遷移確率の高い遷移を推定し、前記推定を用い前記状態遷移数制御処理を行うことを特徴とする請求項１７、請求項１９又は請求項２０に記載のプログラム。
【請求項２２】
前記抽象度の低い回路記述出力をシミュレーション及び実チップで動作させ、各状態での状態遷移確率を取得・解析する動作解析を行い、前記各状態での状態遷移確率により前記状態遷移数制御処理を行うことを特徴とする請求項１７、請求項１９又は請求項２０に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路装置の動作を記述した動作レベルの回路記述から具体的な機能(回路)を記述したＲＴＬ回路記述もしくは相当する回路情報を生成する動作合成システムに関し、特に、回路記述もしくは相当する回路情報の状態遷移数を制約することのできる動作合成システム及び動作合成方法に関する。
【背景技術】
【０００２】
近年、半導体回路の回路規模が増大しているため、半導体回路の設計の際の手間や時間を削減するために様々な手法が用いられている。このような手法の１つとして、動作レベルの回路記述から、ＲＴＬ(Register Transfer Level)等の抽象度の低い回路記述を合成するための動作合成システムの使用が提案されている。このような動作合成システムを用いることにより、ハードウェアの動作を表現しただけの動作レベルの回路記述から、ハードウェアの動作順序やデータパスの構成等を自動的に設計することが可能となる。このようなシステムの一例が非特許文献１に記載されている。
【０００３】
また、動作合成システムを並列演算装置にマトリクス配列された処理回路の生成に用いる一例が特許文献１に記載されている。
【０００４】
これらの動作合成システムは、設計者の指示やデータ及び設計者が作成した動作レベルの回路記述を入力するための入力装置と、回路の動作合成結果や解析結果等を表示するための出力装置と、動作レベル記述を基に記述レベルの最適化やＣＤＦＧ(Control Data Flow Graph)などを生成する前処理手段、演算要素などのスケジューリング・バインディングを行うスケジューリング・バインディング手段、ＦＳＭ(Finite
State Machine)生成や最適化やＲＴＬ記述の出力などを行う後処理手段として動作合成処理を実行するデータ処理装置を含んでいる。
【０００５】
このような構成を有する動作合成システムは次のように動作する。
【０００６】
すなわち、入力装置から入力された動作レベル記述は前処理手段でデータ処理装置の内部形式に変換され、記述レベルの最適化を行い、ＣＤＦＧ(Control Data Flow Graph)が生成される。
【０００７】
スケジューリング・バインディング手段では、演算などの実行順序が決定され、それぞれの処理に対して必要なハードウェアリソース(レジスタや演算器など)を割り当てる。
【０００８】
後処理手段では、ＦＳＭ(Finite State
Machine)生成や最適化を行った後ＲＴＬ記述を出力する。
【０００９】
多くの動作合成システムでは、実際のデータ処理を行うデータパスと処理の状態遷移を制御するＦＳＭに分けて合成する。
【特許文献１】特開２００３−９９４０９号公報
【非特許文献１】DanielGajsky, Nikil Dutt, Allen, Steve Lin, “HIGH-LEVEL SYNTHESIS”, Kluwer AcademicPublishers, 1992
【発明の開示】
【発明が解決しようとする課題】
【００１０】
第１の問題点は、非特許文献１や特許文献１に記載の動作合成システムでは、１状態からの状態遷移数が多くなりＦＳＭの遅延が大きくなる可能性があるということである。
【００１１】
その理由は、非特許文献１や特許文献１に記載の動作合成システムでは１状態からの状態遷移数を何ら考慮していないためである。
【００１２】
第２の問題点は、非特許文献１や特許文献１に記載の動作合成システムでは、予めＦＳＭが作りこまれたような１状態からの状態遷移数に制約のある半導体回路用の合成を行う場合、ＦＳＭの１状態からの状態遷移数の上限を超えてしまう場合があるということである。その理由は、第１の問題点の理由と同じである。
【００１３】
（発明の目的）
本発明の目的は、１状態からの状態遷移数を制約することのできる動作合成システム、動作合成方法及びプログラムを提供することにある。
【００１４】
本発明の他の目的は、１状態からの状態遷移数を制約したときに実行サイクルが増加して回路性能が低下しないもしくは低下を抑えることのできる動作合成システム、動作合成方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１５】
本発明の第１の動作合成システムは、半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムにおいて、1状態からの状態遷移数を制約する手段を含む。
【００１６】
本発明の第２の動作合成方法は、半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムの動作合成方法であって、スケジューリング・バインディング処理において１状態からの状態遷移数を制約する処理を含む。
【００１７】
本発明の第３のプログラムは、半導体集積回路装置の動作を記述した動作レベルの回路記述から、抽象度の低い回路記述を生成するための動作合成システムのコンピュータ上で動作するプログラムであって、コンピュータに、スケジューリング・バインディング処理において１状態からの状態遷移数を制約する処理を実行させる。
【発明の効果】
【００１８】
第１の効果は、１状態からの状態遷移数を制約できるため、１状態からの状態遷移数が少なくなりＦＳＭの遅延を小さくできることにある。
【００１９】
第２の効果は、１状態からの状態遷移数を制約できるため、予めＦＳＭが作りこまれたような１状態からの遷移数に制約のある半導体回路用の回路の制約数を超えずに合成できることにある。
【発明を実施するための最良の形態】
【００２０】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００２１】
（第１の実施の形態）
本発明の第１の実施の形態による動作合成システムについて図面を参照して詳細に説明する。図１は、本発明の第１の実施の形態による動作合成システムの構成を示すブロック図である。
【００２２】
図１を参照すると、本発明の第１の実施の形態による動作合成システムは、プログラム制御により動作するデータ処理装置２０と、入力装置１０と、記憶装置３０と、出力装置４０から構成されている。
【００２３】
データ処理装置２０は、中央処理装置（プロセッサ、コンピュータ）により実現され、前処理手段２１と、スケジューリング・バインディング手段２２と、後処理手段２３と、状態遷移数制御手段２４とを含む。また、記憶装置３０は、システム内部表現記憶部３１を有している。
【００２４】
前処理手段２１は、入力装置１０により与えられた動作レベルの回路記述を解析し、動作合成用の内部表現に変換すると共に最適化を行う機能を有する。
【００２５】
ここで、内部表現とは、動作レベルの回路記述を解析した後に、その解析結果を内部で保持する際に使用される表現を意味している。具体的には、内部表現とは、動作レベルの回路記述を解析した結果を抽象構文木(abstract syntax tree; AST)やコントロールデータフローグラフ(control data flow graph;
CDFG)と呼ばれるデータ構造で保存する際の表現を意味している。
【００２６】
スケジューリング・バインディング手段２２は、各処理を行うサイクルを決定し、あるいは各処理の演算やメモリアクセスで実際にどの演算器やメモリを使用するかを決定する機能を有する。
【００２７】
後処理手段２３は、データパス・ＦＳＭの生成や最適化を実行した後、ＲＴＬ記述や並列演算装置にマトリクス配列された処理回路を出力する機能を有する。
【００２８】
状態遷移数制御手段２４は、１状態からの状態遷移数が制約数を超えないようスケジューリング・バインディング手段２２による処理を制御する機能を有する。そのとき、ループ構造などの静的に分かる構造から遷移確率を推定し、遷移確率の高い遷移が優先してスケジューリングされるようにスケジューリング・バインディング手段２２を制御する。
【００２９】
なお、前処理手段２１、スケジューリング・バインディング手段２２、後処理手段２３の各々の処理手段は、必要に応じてシステムの内部表現を、記憶装置３０のシステム内部表現記憶部３１に対して、書き出しおよび読み込みを行う。
【００３０】
（第１の実施の形態の動作）
【００３１】
次に、図１及び図２のフローチャートを参照して第１の実施の形態による動作合成システムの動作について詳細に説明する。
【００３２】
まず、利用者により用意されている、Ｃ言語などの抽象度の高い回路仕様が記述されている動作レベルの回路記述を入力装置１０から入力する（ステップＡ１）。
【００３３】
入力装置１０から与えられた動作レベルの回路記述は、データ処理装置２０の前処理手段２１に供給される。前処理手段２１は、動作レベルの回路記述を解析し動作合成用の内部表現に変換すると共にその最適化を行う（ステップＡ２）。
【００３４】
データ処理装置２０のスケジューリング・バインディング手段２２は、ＣＤＦＧでノードとして表現された演算やメモリアクセスや遷移などを順に処理し、スケジューリングしていないノードが残っているかを調べる（ステップＡ３）。
【００３５】
残っていない場合には、バインディング処理に進み（ステップＡ９）、残っている場合には、スケジューリングしていないノードを選択する（ステップＡ４）。
【００３６】
選択したノードが遷移を表したノードであるかを調べる（ステップＡ５）。選択したノードが遷移を表したノードでない場合は、制約に従いスケジューリングを行い（ステップＡ８）、遷移を表したノードである場合は、遷移数が制約数を超えているかどうかを調べる（ステップＡ６）。
【００３７】
遷移数が制約数を超えている場合は、次の状態以降において遷移ノードをスケジューリングするように処理する（ステップＡ７）。ここで、バインディング処理をスケジューリング処理の後に行う場合を説明しているが、両方の処理を混在させて実行することも可能である。
【００３８】
後処理手段２３は、スケジューリング・バインディング手段２２の処理結果をもとにデータパス・ＦＳＭの生成や最適化を実行した後、ＲＴＬ記述や並列演算装置にマトリクス配列された処理回路を出力装置４０から出力する（ステップＡ１０、Ａ１１）。
【００３９】
状態遷移数制御手段２４は、遷移数が制約数を超えないよう制御したり（ステップＡ６）、ループ構造などの静的に分かる構造から推定した遷移確率の高い遷移が先に行われるように制御したりする（ステップＡ４）。
【００４０】
（第１の実施の形態による効果）
次に、本実施の形態の効果について説明する。
【００４１】
本実施の形態では、状態遷移数制御手段２４を備えているため、各状態の状態遷移数を制約することができる。
【００４２】
また、各状態の状態遷移数を制約できるように構成されているため、１状態からの状態遷移数が少なくなりＦＳＭの遅延を小さくすることができる。
【００４３】
さらに、本実施の形態では、ループ構造などの静的に分かる構造から遷移確率を推定するように構成されているため、遷移確率の高い遷移が先に行われるように制御することにより、スループットが低下しないようにすることもできる。
【００４４】
（第２の実施の形態）
次に、本発明の第２の実施の形態による動作合成システムについて図面を参照して詳細に説明する。図３は、本発明の第２の実施の形態による動作合成システムの構成を示すブロック図である。
【００４５】
図３を参照すると、本発明の第２の発明を実施による動作合成システムは、プログラム制御により動作するデータ処理装置２０と、入力装置１０と、記憶装置３０と、出力装置４０から構成されている。図３において、図１中の構成要素と同一の構成要素には同一の符号を付し、説明を省略するものとする。
【００４６】
データ処理装置２０は、前処理手段２１と、スケジューリング・バインディング手段２２と、後処理手段２３と、状態遷移数制御手段２４と、動作解析手段２５とを含む。
【００４７】
すなわち、本実施の形態におけるデータ処理装置２０は、図１に示した第１の実施の形態による動作合成システムにおけるデータ処理装置２０に対して、動作解析手段２５が新たに追加された構成になっている。
【００４８】
この動作解析手段２５は、合成されたＲＴＬ記述や処理回路をシミュレーション及び実チップで動作させたときの各状態での状態遷移確率を取得・解析する機能を有している。
【００４９】
（第２の実施の形態の動作）
【００５０】
次に、図３及び図４、５のフローチャートを参照して本発明の第２の実施の形態による動作合成システムの動作について詳細に説明する。
【００５１】
なお、図５において、図２中のステップと同一のステップには同一の符号を付し、説明を省略するものとする。
【００５２】
図４は、動作合成システムの全体的な動作を示しており、まず、利用者により用意されたＣ言語などの抽象度の高い回路仕様が記述されている動作レベルの回路記述が入力装置１０から入力される（ステップＢ１）。
【００５３】
入力装置１０から与えられた動作レベルの回路記述は、データ処理装置２０の前処理手段２１に供給される。前処理手段２１は、動作レベルの回路記述を解析し動作合成用の内部表現に変換すると共にその最適化を行う（ステップＢ２）。
【００５４】
データ処理装置２０のスケジューリング・バインディング手段２２は、演算要素などについてスケジューリング・バインディング処理を行う（ステップＢ３）。
【００５５】
データ処理装置２０の後処理手段２３は、スケジューリング・バインディング手段２２の処理結果をもとにデータパス・ＦＳＭの生成や最適化を実行した後、ＲＴＬ記述や並列演算装置にマトリクス配列された処理回路を出力装置４０から出力する（ステップＢ４、Ｂ５）。
【００５６】
動作解析手段２５は、合成されたＲＴＬ記述や処理回路をシミュレーション及び実チップで動作させ、各状態での状態遷移確率を取得・解析する（ステップＡ１２、Ａ１３）。そして、その結果得られた状態遷移確率情報を状態遷移数制御手段２４に送る（ステップＡ１４）。
【００５７】
ここで、入力装置１０から与えられた動作レベル記述に対して再度動作合成処理を行う（ステップＡ１〜Ａ１１）。この処理は、図２に示した第１の実施の形態の動作合成システムの処理においてノードの選択に状態遷移確率情報を用いるようにしたものであり、状態遷移確率の高いノードを優先的に処理するようにしている（ステップＡ４）。
【００５８】
このとき、前処理（ステップＢ２）後の内部表現を保存してある場合には、ステップＡ１、Ａ２の処理をとばしてスケジューリング（ステップＡ３〜Ａ８）を行うことも可能である。
【００５９】
（第２の実施の形態による効果）
次に、本実施の形態の効果について説明する。
【００６０】
本実施の形態の動作合成システムによれば、第１の実施の形態と同様に、状態遷移数制御手段２４を備えているため、上述した第１の実施の形態と同じ効果が得られる。
【００６１】
さらに、本実施の形態では、合成されたＲＴＬ記述や処理回路をシミュレーション及び実チップで動作させ、各状態での状態遷移確率を取得・解析した結果に基づいて再度動作合成を行うように構成されているため、遷移確率の高い遷移が先に行われるように制御されスループットが低下しないようにすることが可能である。
【００６２】
（第３の実施の形態）
次に、本発明の第３の実施の形態による動作合成システムについて図面を参照して詳細に説明する。図６は、本発明の第３の実施の形態による動作合成システムの構成を示すブロック図である。
【００６３】
図６を参照すると、本発明の第３の実施の形態による動作合成システムは、プログラム制御により動作するデータ処理装置２０と、入力装置１０と、記憶装置３０と、出力装置４０から構成されている。図６において、図１中の構成要素と同一の構成要素には同一の符号を付し、説明を省略するものとする。
【００６４】
データ処理装置２０は、前処理手段２１と、スケジューリング・バインディング手段２２と、後処理手段２３と、状態遷移数制御手段２４と、ＦＳＭ生成・調整手段２６とを含む。
【００６５】
すなわち、本実施の形態におけるデータ処理装置２０は、図１に示した第１の実施の形態による動作合成システムにおけるデータ処理装置２０に対して、ＦＳＭ生成・調整手段２６が新たに追加された構成になっている。
【００６６】
このＦＳＭ生成・調整手段２６は、ＦＳＭを生成後、１状態からの状態遷移数が制約数を超えている場合に処理を何も行わない空の状態を生成する機能を有する。この場合、制約数を超えた状態はその空の状態を経由して目的の状態への遷移を行う。
【００６７】
本実施の形態におけるＦＳＭ生成・調整手段２６も、他の処理手段と同様に、必要に応じてシステムの内部表現を、記憶装置３０のシステム内部表現記憶部３１に対して、書き出し及び読み込みを行う。
【００６８】
（第３の実施の形態の動作）
次に、図６及び図７のフローチャートを参照して本発明の第３の実施の形態による動作合成システムの動作について詳細に説明する。
【００６９】
まず、利用者により用意されたＣ言語などの抽象度の高い回路仕様が記述されている動作レベルの回路記述が入力装置１０から入力される（ステップＣ１）。
【００７０】
入力装置１０から与えられた動作レベル記述は、データ処理装置２０の前処理手段２１に供給される。前処理手段２１は、動作レベルの回路記述を解析し動作合成用の内部表現に変換すると共に最適化を行う（ステップＣ２）。
【００７１】
データ処理装置２０のスケジューリング・バインディング手段２２は、ＣＤＦＧでノードとして表現された演算やメモリアクセスや遷移などを順に処理していく（ステップＣ３）。
【００７２】
データ処理装置２０のＦＳＭ生成・調整手段２６は、１状態からの状態遷移数を考慮せずにＦＳＭを生成する（ステップＣ４）。また、ＦＳＭ生成・調整手段２６は、状態遷移数が制約数を超えた状態が残っているかを調べる（ステップＣ５）。残っていない場合には後処理に進み（ステップＣ９）、残っている場合には空の状態を生成する（ステップＣ６）。空の状態への遷移を経由する遷移を決定し（ステップＣ７）、データパス・ＦＳＭを変更する（ステップＣ８）。
【００７３】
後処理手段２３は、ＦＳＭ生成・調整手段２６の結果をもとに最適化をした後、ＲＴＬ記述や並列演算装置にマトリクス配列された処理回路を出力装置４０から出力する（ステップＣ９、Ｃ１０）。
【００７４】
（第３の実施の形態による効果）
次に、本実施の形態の効果について説明する。
【００７５】
本実施の形態の動作合成システムによれば、第１の実施の形態と同様に状態遷移数制御手段２４を備えているため、上述した第１の実施の形態による効果と同じ効果が得られる。
【００７６】
さらに、第１、２の実施の形態の動作合成システムでは合成の早い段階であるスケジューリング・バインディングで制約を行っていたのに対し、第３の実施の形態では、スケジューリング・バインディング後の段階で制約を行うことができる。このため、処理時間の長いスケジューリング・バインディング処理を複雑にして処理時間を増やすことなく各状態の状態遷移数を制約できるという効果が得られる。
【００７７】
（第４の実施の形態）
次に、本発明の第４の実施の形態による動作合成システムについて図面を参照して詳細に説明する。図８は、本発明の第４の実施の形態による動作合成システムの構成を示すブロック図である。
【００７８】
図８に示す第４の実施の形態による動作合成システムの構成は、図６に示した第３の実施の形態の構成と同じであり、ＦＳＭ生成・調整手段２６がＦＳＭ生成・調整手段２６Ａに置き換えられている点が第３の実施の形態と相違する。その他の構成要素については、第３の実施の形態と同様であるので説明は省略する。
【００７９】
この第４の実施の形態による動作合成システムのデータ処理装置２０におけるＦＳＭ生成・調整手段２６Ａは、ＦＳＭを生成後、１状態からの状態遷移数が制約数を超えている場合に複数の状態を結合した新たな状態を生成する機能を有している。
【００８０】
次に、図８及び図９のフローチャートを参照して本発明の第４の実施の形態による動作合成システムの動作について詳細に説明する。
【００８１】
まず、利用者によりＣ言語などの抽象度の高い回路仕様が記述されている動作レベル記述が用意される（ステップＤ１）。
【００８２】
入力装置１０から与えられた動作レベル記述は、データ処理装置２０の前処理手段２１に供給される。前処理手段２１は、動作レベルの回路記述を解析し動作合成用の内部表現に変換したあと最適化を行う（ステップＤ２）。
【００８３】
データ処理装置２０のスケジューリング・バインディング手段２２は、ＣＤＦＧでノードとして表現された演算やメモリアクセスや遷移などを順に処理していく（ステップＤ３）。
【００８４】
データ処理装置２０のＦＳＭ生成・調整手段２６Ａは、１状態からの状態遷移数を考慮せずにＦＳＭを生成する（ステップＤ４）。また、ＦＳＭ生成・調整手段２６Ａは、状態遷移数が制約数を超えた状態が残っているかを調べ（ステップＤ５）、残っていない場合には後処理に進む（ステップＤ８）。残っている場合には結合する状態を決定し（ステップＤ６）、複数の状態を結合し新たな状態を生成しデータパス・ＦＳＭを変更する（ステップＤ７）。
【００８５】
データ処理装置２０の後処理手段２３は、ＦＳＭ生成・調整手段２６Ａの結果をもとに最適化をした後、ＲＴＬ記述や並列演算装置にマトリクス配列された処理回路を出力装置４０から出力する（ステップＤ８、Ｄ９）。
【００８６】
（第４の実施の形態による効果）
次に、本実施の形態の効果について説明する。
【００８７】
本実施の形態の動作合成システムによれば、第１の実施の形態と同様に状態遷移数制御手段２４を備えているため、上述した第１の実施の形態による効果と同じ効果が得られる。
【００８８】
さらに、上記で説明した第１から第３の実施の形態の動作合成システムでは、状態が増加してスループットが低下する可能性があるのに対し、第４の実施の形態では状態遷移数制約により実行タイミング自体は変わらないためスループット低下を防ぐことができるという効果がある。
【００８９】
（第５の実施の形態）
次に、本発明の第５の実施の形態による動作合成システムについて図面を参照して詳細に説明する。図１０は、本発明の第５の実施の形態による動作合成システムの構成を示すブロック図である。
【００９０】
図１０を参照すると、第５の実施の形態による動作合成システムの構成は、プログラム制御により動作するデータ処理装置２０と、入力装置１０と、記憶装置３０と、出力装置４０から構成されている。図１０において、図６中の構成要素と同一の構成要素には同一の符号を付し、説明を省略するものとする。
【００９１】
データ処理装置２０は、前処理手段２１と、スケジューリング・バインディング手段２２と、後処理手段２３と状態遷移数制御手段２４と動作解析手段２５とＦＳＭ生成・調整手段２６とを含む。
【００９２】
本実施の形態におけるデータ処理装置２０は、図６に示した第３の実施の形態の動作合成システムのデータ処理装置２０に対して、動作解析手段２５が新たに追加された構成になっている。
【００９３】
この動作解析手段２５は、合成されたＲＴＬ記述や処理回路をシミュレーション及び実チップで動作させたときの各状態での状態遷移確率を取得・解析する。
【００９４】
次に、図１０及び図４、図１１のフローチャートを参照して本発明を実施するための第５の実施の形態の動作について詳細に説明する。
【００９５】
図１１において、図７中のステップと同一のステップには同一の符号を付し、説明を省略するものとする。
【００９６】
まず、利用者によりＣ言語などの抽象度の高い回路仕様が記述されている動作レベル記述が用意され、動作合成を行う（図４のステップＢ１〜Ｂ５）。
【００９７】
動作解析手段２５は、合成されたＲＴＬ記述や処理回路をシミュレーション及び実チップで動作させ、各状態での状態遷移確率を取得・解析する（図１１のステップＣ１１、Ｃ１２、Ｃ１３）。
【００９８】
ここで、入力装置１０から与えられた動作レベル記述に対して再度動作合成処理を行う（図１１のステップＣ１〜Ｃ１０）。
【００９９】
この処理は、図７に示した第３の実施の形態の動作合成システムの処理において空の状態への遷移を経由する遷移の選択に状態遷移確率情報を用いるようにしたものであり、状態遷移確率の高いノードを優先的に処理する（ステップＣ７）。
【０１００】
このとき、最初の動作合成（ステップＢ１〜Ｂ５）においてＦＳＭ生成後の内部表現を保存してある場合には、ステップＣ１〜Ｃ４の処理をとばしてＦＳＭの調整処理（ステップＣ５〜Ｃ８）を行うことも可能である。
【０１０１】
（第５の実施の形態による効果）
次に、本実施の形態の効果について説明する。
【０１０２】
本実施の形態の動作合成システムによれば、第１の実施の形態と同様に状態遷移数制御手段２４を備えているため、上述した第１の実施の形態による効果と同じ効果が得られる。また、第３の実施の形態と同じＦＳＭ生成・調整手段２６を備えていることから、第３の実施の形態と同じ効果が得られる。
【０１０３】
さらに、本実施の形態では、合成されたＲＴＬ記述や処理回路をシミュレーション及び実チップで動作させ、各状態での状態遷移確率を取得・解析した結果をもとに再度合成を行うように構成されているため、遷移確率の高い遷移が先に行われるように制御しスループットが低下しないようにすることができる。
【０１０４】
次に、動作合成システムのハードウェア構成について、図２１を参照して説明する。図２１は、動作合成システムのハードウェア構成を示すブロック図である。
【０１０５】
図２１を参照すると、動作合成システムは、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）４０１（データ処理装置２０に相当）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のメインメモリであり、データの作業領域やデータの一時退避領域に用いられる主記憶部４０２、ネットワークを介してデータの送受信を行う通信部４０３、外部装置と接続してデータの送受信を行う入出力インタフェース部４０４、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、磁気ディスク、半導体メモリ等の不揮発性メモリから構成されるハードディスク装置である補助記憶部４０５（記憶装置３０に相当）、上記各構成要素を相互に接続するシステムバス４０６、ディスプレイ装置等の出力装置４０７（出力装置４０に相当）及びキーボード等の入力装置４０８（入力装置１０に相当）を備えている。
【０１０６】
本実施の形態による動作合成システムは、動作合成の処理を実行するプログラムを組み込んだ、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等のハードウェア部品である回路部品を実装することにより、その動作をハードウェア的に実現することは勿論として、データ処理装置２０の前処理手段２１、スケジューリング・バインディング手段２２、後処理手段２３、状態遷移数制御手段２４、動作回析手段２５、ＦＳＭ生成・調整手段２６の各機能を提供するプログラムを、補助記憶部４０５に格納し、そのプログラムを主記憶部４０２にロードしてＣＰＵ４０１で実行することにより、ソフトウェア的に実現することも可能である。
【実施例】
【０１０７】
次に、上述した本発明の各実施の形態の具体的な実施例を用いてその動作を説明する。
【０１０８】
以下に示す実施例では特に断りのない限り、１状態からの状態遷移制約数を「５」とするものとする。
【０１０９】
（第１の実施例）
次に、本発明の第１の実施例について図面を参照して説明する。この第１の実施例は、本発明の第３及び第５の実施の形態に対応するものである。
【０１１０】
図１２に示すように、ステップＣ４後の状態ｎからの状態遷移数が「６」となっている場合、ＦＳＭ生成・調整手段２６は、ステップＣ６〜Ｃ８において図１３に示すような空状態を生成する。状態Ｅ、状態Ｆへの遷移は生成された空状態を経由して行われる。これにより、状態ｎでの状態遷移数は正しく制約されることになる。
【０１１１】
（第２の実施例）
次に、本発明の第２の実施例について図面を参照して説明する。この第２の実施例は、本発明の第３及び第５の実施の形態に対応するものである。
【０１１２】
図１２に示すように、ステップＣ４後の状態ｎからの状態遷移数が「６」となっている場合、特に、状態ｎから状態Ｆへの遷移確率が、状態ｎから状態Ｄへの遷移確率よりも高い場合を考える。この場合、ＦＳＭ生成・調整手段２６は、ステップＣ６〜Ｃ８において図１４に示すような空状態を生成し、状態Ｄ、状態Ｆへの遷移は生成された空状態を経由して行われる。これにより、状態ｎでの状態遷移数は正しく制約されることになる。
【０１１３】
また、遷移確率の高い状態Ｆへの遷移が空状態を経由せず行われるため、図１３のような遷移を生成するよりも実行サイクルを少なくすることができスループットの高い回路を生成することができる。
【０１１４】
ここで、遷移確率はループ構造などの静的に分かる情報から得ることもできるし、動作解析手段２５により得られる情報から得ることもできる。
【０１１５】
（第３の実施例）
次に、本発明の第３の実施例について図面を参照して説明する。この第３の実施例は、本発明の第３及び第５の実施の形態に対応するものである。
【０１１６】
ステップＣ４後の状態ｎからの状態遷移数が「１０」となっている場合、図１３で行ったように空状態を１つ作成すると、図１５に示すように空状態からの状態遷移数は「６」となり、１状態からの状態遷移制約数「５」を超えてしまう。
【０１１７】
このような場合、図１６に示すように、１状態からの状態遷移数を１状態からの状態遷移制約数以下にするように空状態を複数作成することで、状態ｎ、空状態、空状態１、空状態２での状態遷移数は正しく制約されることになる。
【０１１８】
（第４の実施例）
次に、本発明の第４の実施例について図面を参照して説明する。この第４の実施例は、本発明の第３及び第５の実施の形態に対応するものである。
【０１１９】
図１５に示すように、空状態からの状態遷移数は「６」となり、１状態からの状態遷移制約数「５」を超えてしまう場合、図１７に示すように、空状態１、空状態２と空状態を複数回経由して遷移するような状態遷移を生成することもできる。状態Ａ〜Ｄへの遷移確率が高く、状態Ｅ、状態Ｆへの遷移確率が低い場合、図１６のような状態遷移に比べ実行サイクルの少ないスループットの高い回路を生成することができる。
【０１２０】
（第５の実施例）
次に、本発明の第５の実施例について図面を参照して説明する。この第５の実施例は、本発明の第４の実施の形態に対応するものである。
【０１２１】
図１２に示すように、ステップＤ４後の状態ｎからの状態遷移数が「６」となっている場合、ＦＳＭ生成・調整手段２６は、ステップＤ６、Ｄ７において図１８に示すような状態Ｅと状態Ｆを結合した新たな状態Ｅ’を生成する。これにより状態ｎでの状態遷移数は正しく制約されることになる。
【０１２２】
（第６の実施例）
次に、本発明の第６の実施例について図面を参照して説明する。この第６の実施例は、本発明の第３及び第５の実施の形態に対応するものである。
【０１２３】
ステップＣ４もしくはＤ４後の状態ｎからの状態遷移数が「１０」となっている場合、図１３で行ったように空状態を一つ作成すると、図１５に示すように空状態からの状態遷移数は「６」となり、１状態からの状態遷移制約数５を超えてしまう。このような場合、図１９に示すように、状態Ｉと状態Ｊを結合した新たな状態Ｉ’を作成し、１状態からの状態遷移数を状態遷移制約数以下にすることができる。
【０１２４】
（第７の実施例）
次に、本発明の第７の実施例について図面を参照して説明する。この第７の実施例は、本発明の第３及び第５の実施の形態に対応するものである。
【０１２５】
ステップＣ４もしくはＤ４後の状態ｎからの状態遷移数が「１０」となっている場合、図２０に示すように、生成する空状態を別の状態と結合し新たな状態を作ることもできる。この実施例では、状態Ｅと空状態を結合した新たな状態Ｅ’を作成することで、１状態からの状態遷移数を状態遷移制約数以下にすることができる。
【０１２６】
以上好ましい実施の形態と実施例をあげて本発明を説明したが、本発明は必ずしも、上記実施の形態及び実施例に限定されるものでなく、その技術的思想の範囲内において様々に変形して実施することができる。
【図面の簡単な説明】
【０１２７】
【図１】本発明の第１の実施の形態による動作合成システムの構成を示すブロック図である。
【図２】本発明の第１の実施の形態による動作合成システムにおける動作を示すフローチャートである。
【図３】本発明の第２の実施の形態による動作合成の構成を示すブロック図である。
【図４】本発明の第２の実施の形態による動作合成システムにおける動作を示すフローチャートである。
【図５】本発明の第２の実施の形態による動作合成システムにおける動作を示すフローチャートである。
【図６】本発明の第３の実施の形態による動作合成の構成を示すブロック図である。
【図７】本発明の第３の実施の形態による動作合成システムにおける動作を示すフローチャートである。
【図８】本発明の第４の実施の形態による動作合成の構成を示すブロック図である。
【図９】本発明の第４の実施の形態による動作合成システムにおける動作を示すフローチャートである。
【図１０】本発明の第５の実施の形態による動作合成の構成を示すブロック図である。
【図１１】本発明の第５の実施の形態による動作合成システムにおける動作を示すフローチャートである。
【図１２】第１の実施例における状態遷移を説明するための図である。
【図１３】第１の実施例における状態遷移を説明するための図である。
【図１４】第２の実施例における状態遷移を説明するための図である。
【図１５】第３の実施例における状態遷移を説明するための図である。
【図１６】第３の実施例における状態遷移を説明するための図である。
【図１７】第４の実施例における状態遷移を説明するための図である。
【図１８】第５の実施例における状態遷移を説明するための図である。
【図１９】第６の実施例における状態遷移を説明するための図である。
【図２０】第７の実施例における状態遷移を説明するための図である。
【図２１】本発明の各実施の形態による動作合成システムのハードウェア構成を示すブロック図である。
【符号の説明】
【０１２８】
１０：入力装置
２０：データ処理装置（中央処理装置；プロセッサ；コンピュータ）
２１：前処理手段
２２：スケジューリング・バインディング手段
２３：後処理手段
２４：状態遷移数制御手段
２５：動作解析手段
２６、２６Ａ：ＦＳＭ生成・調整手段
３０：記憶装置
３１：システム内部表現記憶部
４０：出力装置
【図１】
2009122812.tif 000003
【図２】
2009122812.tif 000004
【図３】
2009122812.tif 000005
【図４】
2009122812.tif 000006
【図５】
2009122812.tif 000007
【図６】
2009122812.tif 000008
【図７】
2009122812.tif 000009
【図８】
2009122812.tif 000010
【図９】
2009122812.tif 000011
【図１０】
2009122812.tif 000012
【図１１】
2009122812.tif 000013
【図１２】
2009122812.tif 000014
【図１３】
2009122812.tif 000015
【図１４】
2009122812.tif 000016
【図１５】
2009122812.tif 000017
【図１６】
2009122812.tif 000018
【図１７】
2009122812.tif 000019
【図１８】
2009122812.tif 000020
【図１９】
2009122812.tif 000021
【図２０】
2009122812.tif 000022
【図２１】
2009122812.tif 000023