(57)【要約】【課題】動作記述から効率的な処理を行う回路の回路記述を得る。【解決手段】実施形態の動作合成方法は、コンピュータが、入力された動作記述において、当該動作記述に含まれるループ処理を展開し、展開されたループ処理の中から同型の処理を行う部分を抽出する処理を実行する。また、動作合成方法は、コンピュータが、抽出された部分を関数化して動作記述を変換し、変換された動作記述に基づいて動作合成を行う処理を実行する。【選択図】図１
2016177454.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが、
入力された動作記述において、当該動作記述に含まれるループ処理を展開し、
前記展開されたループ処理の中から同型の処理を行う部分を抽出し、
前記抽出された部分を関数化して前記動作記述を変換し、
前記変換された動作記述に基づいて動作合成を行う
処理を実行することを特徴とする動作合成方法。
【請求項２】
前記抽出する処理は、前記展開されたループ処理に基づいて、当該ループ処理の依存関係を示す木構造のグラフを構築し、当該構築された木構造のグラフの中から同型の部分グラフを抽出し、
前記変換する処理は、前記抽出された部分グラフにかかる処理を関数化して前記動作記述を変換する
ことを特徴とする請求項１に記載の動作合成方法。
【請求項３】
前記変換する処理は、前記動作記述において関数化された部分を前記動作合成の際に展開しないように制約する制約情報を出力し、
前記動作合成を行う処理は、前記出力された制約情報に基づいて前記動作合成を行う
ことを特徴とする請求項１又は２に記載の動作合成方法。
【請求項４】
前記変換する処理は、前記関数化された動作記述の中の繰り返し部分をループ処理に置き直した動作記述に変換する
ことを特徴とする請求項１乃至３のいずれか一項に記載の動作合成方法。
【請求項５】
コンピュータに、
入力された動作記述において、当該動作記述に含まれるループ処理を展開し、
前記展開されたループ処理の中から同型の処理を行う部分を抽出し、
前記抽出された部分を関数化して前記動作記述を変換し、
前記変換された動作記述に基づいて動作合成を行う
処理を実行させることを特徴とする動作合成プログラム。
【請求項６】
入力された動作記述において、当該動作記述に含まれるループ処理を展開する展開部と、
前記展開されたループ処理の中から同型の処理を行う部分を抽出する抽出部と、
前記抽出された部分を関数化して前記動作記述を変換する変換部と、
前記変換された動作記述に基づいて動作合成を行う合成部と
を有することを特徴とする動作合成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、動作合成方法、動作合成プログラムおよび動作合成装置に関する。
【背景技術】
【０００２】
従来、コンピュータによって論理回路を合成する技術が知られている。この合成技術の一例として、論理回路で処理するアルゴリズムがＣ言語等のプログラム言語により記述された動作記述をＶｅｒｉｌｏｇ−ＨＤＬまたはＶＨＤＬといったＲＴＬ（Register  Transfer  Level）の回路記述に変換する動作合成（高位合成）が知られている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平８−４４７７３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述した従来技術では、動作記述の内容によっては効率的な処理を行う回路の回路記述を得ることが困難であるという問題がある。
【０００５】
例えば、アルゴリズム的な観点では互いに違いのない２つの動作記述があり、互いのアルゴリズムは入力データに対して等しい出力データを返すものとする。この２つの動作記述について動作合成を行う場合、互いに処理効率の異なる回路の回路記述が生成される場合がある。
【０００６】
図１７は、動作記述２０１、２０２の一例を説明する説明図である。図１７に示すように、動作記述２０１、２０２は、入力データに対してＸＯＲ（排他的論理和）を行って出力データを返すアルゴリズムを記述したものである。この動作記述２０１、２０２は、互いに入力データに対してＸＯＲを行って等しい出力データを返すが、アルゴリズムにおける多重ループ構造に相違点がある。この相違点により、動作記述２０１、２０２から動作合成して回路記述を生成した場合、この回路記述による回路は互いに異なるものとなる。
【０００７】
図１８は、変数の解析結果２１１、２１２を説明する説明図である。具体的には、図１８は、図１７の動作記述２０１、２０２について、ソフトウェアとして処理を走らせることで得られる変数のライフタイムを解析結果２１１、２１２として示している。なお、ライフタイムの解析が行われた主な変数はｉｎ［ｊ］［ｉ］、ｔｍｐ［ｉ］（ｏｕｔ［ｉ］はｔｍｐ［ｉ］を代入するだけなので省略）である。変数ｉｎ［ｊ］［ｉ］はアドレス０〜６３に割り当てられており、変数ｔｍｐ［ｉ］はアドレス６４〜に割り当てられている。
【０００８】
解析結果２１１は、動作記述２０１の処理を走らせた場合の変数のライフタイムを示すグラフである。また、解析結果２１２は、動作記述２０２の処理を走らせた場合の変数のライフタイムを示すグラフである。時刻ｔ１、ｔ３は、最初の出力データであるｏｕｔ［０］が確定する時刻である。時刻ｔ２、ｔ４は、ｏｕｔ［０］を実際に出力する時刻である。
【０００９】
図１８に示すように、解析結果２１１では最初の出力データであるｏｕｔ［０］が確定する時刻ｔ１が１１であるのに対し、解析結果２１２ではｏｕｔ［０］が確定する時刻ｔ３が１４６である。なお、解析結果２１１、２１２において、ｏｕｔ［０］の実際の出力（時刻ｔ２、ｔ４）はｏｕｔ［０］確定の直後ではない。しかしながら、ｏｕｔ［０］の出力は、ｏｕｔ［０］確定後であればいつでも出力可能である。よって、ｏｕｔ［０］を確定後に即座に出力するＩ／Ｏスケジューリングでは、ｏｕｔ［０］を出力した後は、ｏｕｔ［０］にかかるリソースは開放可能となる。開放されたリソースでは次の処理で行うデータを格納可能であり、パイプライン処理による前倒し実行が可能となる。
【００１０】
解析結果２１１、２１２を比較すると、解析結果２１１ではパイプライン処理による前倒し実行が可能となるのは時刻ｔ１の１１であり、解析結果２１２では時刻ｔ３の１４６である。この結果、解析結果２１１の方が解析結果２１２よりも早くパイプライン処理による前倒し実行ができる。よって、解析結果２１１となる動作記述２０１の方が入力データに対する処理速度が早く、スループットが高い効率的な処理を行う回路の回路記述を生成できる。
【００１１】
１つの側面では、動作記述から効率的な処理を行う回路の回路記述を得ることを可能とする動作合成方法、動作合成プログラムおよび動作合成装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
第１の案では、動作合成方法は、コンピュータが、入力された動作記述において、当該動作記述に含まれるループ処理を展開し、展開されたループ処理の中から同型の処理を行う部分を抽出する処理を実行する。また、動作合成方法は、コンピュータが、抽出された部分を関数化して動作記述を変換し、変換された動作記述に基づいて動作合成を行う処理を実行する。
【発明の効果】
【００１３】
本発明の１実施態様によれば、動作記述から効率的な処理を行う回路の回路記述を得ることができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、実施形態にかかる動作合成装置の機能構成の一例を示す図である。
【図２】図２は、実施形態にかかる動作合成装置の動作の一例を示すフローチャートである。
【図３】図３は、前処理の一例を示すフローチャートである。
【図４】図４は、ループ展開の一例を説明する説明図である。
【図５】図５は、最適化の一例を説明する説明図である。
【図６】図６は、変数の名前変更の一例を説明する説明図である。
【図７】図７は、依存関係グラフの構築の一例を説明する説明図である。
【図８】図８は、部分グラフの一例を説明する説明図である。
【図９】図９は、関数化の一例を説明する説明図である。
【図１０】図１０は、前処理後の動作記述の一例を説明する説明図である。
【図１１】図１１は、高位合成による回路の一例を説明する説明図である。
【図１２】図１２は、回路ブロックの一例を説明する説明図である。
【図１３】図１３は、高位合成による回路の一例を説明する説明図である。
【図１４】図１４は、動作記述の一例を説明する説明図である。
【図１５】図１５は、前処理後の動作記述の一例を説明する説明図である。
【図１６】図１６は、実施形態にかかる動作合成装置として動作するコンピュータのハードウェア構成を示す図である。
【図１７】図１７は、動作記述の一例を説明する説明図である。
【図１８】図１８は、変数の解析結果を説明する説明図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して、実施形態にかかる動作合成方法、動作合成プログラムおよび動作合成装置を説明する。実施形態において同一の機能を有する構成には同一の符号を付し、重複する説明は省略する。なお、以下の実施形態で説明する動作合成方法、動作合成プログラムおよび動作合成装置は、一例を示すに過ぎず、実施形態を限定するものではない。また、以下の各実施形態は、矛盾しない範囲内で適宜組みあわせてもよい。
【００１６】
図１は、実施形態にかかる動作合成装置１の機能構成の一例を示す図である。図１に示すように、動作合成装置１は、前処理部１０および高位合成部２０を有する。前処理部１０は、入力された動作記述３１および合成制約３２に対し、動作合成（高位合成）に先立って前処理（詳細は後述する）を行う。
【００１７】
動作記述３１は、クロック信号を意識せずに論理回路の機能が記述されたものであり、例えば、論理回路で処理するアルゴリズムがＣ言語等のプログラム言語により記述されている。合成制約３２は、動作合成を行う際に制約する条件が記述されたものである。例えば、合成制約３２には、クロック周波数１００ＭＨｚで動作する回路とするなど、動作合成により生成される回路記述３５における回路（ハードウエア上）の動作条件として制約する各種条件が列挙されている。
【００１８】
高位合成部２０は、前処理部１０による前処理後の動作記述３３および合成制約３４をもとに動作合成を行い、動作条件とされたクロック周波数に基づいて論理回路のレジスタ間の機能を記述したＲＴＬの回路記述３５を生成し、出力する。
【００１９】
図２は、実施形態にかかる動作合成装置１の動作の一例を示すフローチャートである。図２に示すように、処理が開始されると、前処理部１０は、コンソールの操作やストレージに予め記憶されたデータの読み出しにより、動作記述３１および合成制約３２の入力を受け付ける（Ｓ１）。次いで、前処理部１０は、入力された動作記述３１および合成制約３２に対して前処理を行い、動作記述３３および合成制約３４を出力する（Ｓ２）。次いで、高位合成部２０は、動作記述３３および合成制約３４をもとに高位合成（動作合成）を行い（Ｓ３）、回路記述３５を出力する（Ｓ４）。
【００２０】
次に、前処理部１０における前処理の詳細を説明する。前処理部１０は、展開部１０１、最適化部１０２、グラフ構築部１０３、関数化部１０４および出力部１０５を有する。
【００２１】
図３は、前処理の一例を示すフローチャートである。図３に示すように、展開部１０１は、動作記述３１について構文解析を行い、動作記述３１に含まれるループ処理を展開する（Ｓ２１）。具体的には、展開部１０１は、動作記述３１において繰り返されるループ処理のループ変数を、実際の数値へ置換して列挙した記述を生成する。
【００２２】
図４は、ループ展開の一例を説明する説明図である。図４に示すように、展開部１０１は、動作記述３１に含まれるｆｏｒ文のループ処理を展開したデータＤ１を生成する。なお、ループ処理については、ＢＬＯＣＫ＿ＬＥＮ＝１６、ＢＬＯＣＫ＿ＮＵＭ＝４として展開した場合を示している。また、図示例では、動作記述３１において、ループ処理を展開した記述部分を抽出したデータＤ１を例示している。
【００２３】
Ｓ２１に次いで、最適化部１０２は、展開部１０１によりループ処理を展開した後の記述について、予め設定された規則に従い最適化（初期値代入、定数伝播）を行う（Ｓ２２）。
【００２４】
図５は、最適化の一例を説明する説明図であり、より具体的には、図４のデータＤ１について最適化を行ったデータＤ２を例示する図である。一例として、最適化部１０２は、図５に示すように、データＤ１の記述に含まれる変数への初期値の代入を行い、記述を最適化したデータＤ２を生成する。より具体的には、データＤ１におけるｔｍｐ［］の初期値が０であることを利用して記述を簡単化したデータＤ２を生成する。
【００２５】
Ｓ２２に次いで、グラフ構築部１０３は、最適化部１０２による最適化後の記述をもとに、ループ処理の依存関係を示す木構造のグラフを構築する。具体的には、グラフ構築部１０３は、記述に含まれる変数について、処理上の依存関係をトレースできるように、左辺、右辺に現れる変数の名前を変更する（Ｓ２３）。
【００２６】
例えば、プログラム言語の構文において、左辺の変数は、代入によって値が変化する。ある構文で左辺と右辺に同名の変数が出現している場合には、実行順序という暗黙的な依存関係が存在する。したがって、グラフ構築部１０３は、ループ処理を展開した後の記述について、後に構文の並べ替えを行う場合であっても記述された字面より依存関係が判断できるように、左辺、右辺の変数を適宜変更する。
【００２７】
図６は、変数の名前変更の一例を説明する説明図であり、より具体的には、図５のデータＤ２について変数の名前を変更したデータＤ３を例示する図である。図６に示すように、グラフ構築部１０３は、左辺および右辺において処理の実行順に出現する変数の名前に「＠１」、「＠２」…を順に付すことで、変数の依存関係が判断できるように変数の名前を変更する。
【００２８】
例えば、左辺に初出のｔｍｐ［０］については、ｔｍｐ［０］＠１のように名前を変更する。そして、次に左辺にｔｍｐ［０］が現れる場合には、左辺のｔｍｐ［０］をｔｍｐ［０］＠２のように変更する。また、左辺にｔｍｐ［０］が現れた後に、右辺にｔｍｐ［０］が現れる場合には、右辺のｔｍｐ［０］をｔｍｐ［０］＠１のように変更する。
【００２９】
Ｓ２３に次いで、グラフ構築部１０３は、依存関係が判断できるように変数の名前を変更したデータＤ３をもとに、処理の依存関係を木構造状で示す依存関係グラフを構築する（Ｓ２４）。
【００３０】
図７は、依存関係グラフの構築の一例を説明する説明図である。図７に示すように、グラフ構築部１０３は、データＤ３における各処理について、処理の依存関係を枝で表現し、変数と演算とをノードで表現するデータＤ４をもとに、同一名のノードで結合して依存関係グラフを示すデータＤ５を作成する。
【００３１】
具体的には、グラフ構築部１０３は、出力変数（図示例ではｏｕｔ［０］＠１）をｒｏｏｔノードとして選択する。次いで、グラフ構築部１０３は、ｒｏｏｔノードに接続するノード（図示例ではｔｍｐ［０］＠４）と同名のノードを結合する。以下、順次同名のノードを結合し、演算しないパスは短絡（ノード削除）していくことで、データＤ５を作成する。なお、図示例ではデータＤ３における１つの出力変数（ｏｕｔ［０］＠１）を例示しているが、他の出力変数（ｏｕｔ［１］＠１〜ｏｕｔ［１５］＠１）についても同様に依存関係グラフが作成される。
【００３２】
Ｓ２４に次いで、関数化部１０４は、構築した依存関係グラフ（データＤ５）の中から同型の部分グラフを検出する（Ｓ２５）。同型の部分グラフとは、依存関係グラフの中で、変数等の数値は異なる場合があるが、処理内容（例えば演算内容）が同型であることを示すグラフである。例えば、動作記述３１に含まれるループ処理において繰り返し呼び出されて利用される同型の演算処理に対応した部分が同型の部分グラフとして検出される。このように、同型の部分グラフに対応する同型の処理という場合は、数値および演算内容が同一の処理ということだけではなく、変数等の具体的な数値は異なるが演算内容等が同型である場合を含むものである。
【００３３】
具体的には、関数化部１０４は、依存関係グラフについて、入力変数、出力変数に相当するノード名を、パラメータ化（具体的な変数名を無意味な仮引数名への置換）する。次いで、パラメータ化したグラフをもとに、同型のグラフか否かを比較することで、同型の部分グラフを検出する。
【００３４】
例えば、ノード名のパラメータ化における命名規則を次のようにする。
・「＠１」を削除しても、依存関係を壊さない場合は削除する（１回しか出現しないものは削除してもよい）。
・出力変数にはｐｒｅｆｉｘ”ｏｕｔ”を付加する。
・入力変数にはｐｒｅｆｉｘ”ｉｎ”を付加する。
・出力変数、入力変数ごとに、元のノード名を辞書式順序で並べ替え、ｓｕｆｆｉｘとして通し番号を割り振る。
【００３５】
図８は、部分グラフの一例を説明する説明図であり、より具体的には、図７のデータＤ５より検出した部分グラフのデータＤ６を例示する図である。上述した命名規則によるパラメータ化後の依存関係グラフより、図８に示すような部分グラフが検出される。より具体的には、１６個の出力変数（ｏｕｔ［０］＠１〜ｏｕｔ［１５］＠１）に対応する部分グラフが１６個検出される。
【００３６】
Ｓ２５に次いで、関数化部１０４は、検出した同型の部分グラフを関数化する（Ｓ２６）。具体的には、関数化部１０４は、同型の部分グラフに対応する演算内容を関数記述に変換する。なお、同型の部分グラフは同名の関数とする。
【００３７】
図９は、関数化の一例を説明する説明図である。より具体的には、図９は、図８のデータＤ６における部分グラフを関数化した記述であるデータＤ７を例示する図である。図９に示すように、関数化部１０４は、データＤ６における部分グラフを、入力がｉｎ０〜ｉｎ３、出力がｏｕｔ０であり、演算内容をｏｕｔ０＝（（ｉｎ０＾ｉｎ１）＾ｉｎ２）＾ｉｎ３とするデータＤ７に変換する。なお、上述した演算内容については、「ｆｕｎｃ０」という関数名で関数化している。また、１６個の出力変数（ｏｕｔ［０］＠１〜ｏｕｔ［１５］＠１）に対応する１６個の部分グラフが１６個の「ｆｕｎｃ０」に変換される。
【００３８】
Ｓ２６に次いで、関数化部１０４は、関数化された記述の中で繰り返し部分をループ処理に置き直すループ化を行う（Ｓ２７）。具体的には、関数化部１０４は、Ｓ２６において関数化された記述の中で、ループ変数に置換できる部分を検出してループ処理へ組み立てなおす。例えば、図９におけるデータＤ７の場合は、ｆｕｎｃ０の関数が繰り返されることから、ｆｏｒ文のループ処理に置き直すループ化が行われる。上記のようにループ化を行うことで、高位合成部２０において動作合成を行った場合に生成される回路記述３５の論理回路を、よりコンパクトなものとすることができる。
【００３９】
Ｓ２７に次いで、出力部１０５は、Ｓ２７によるループ化後の動作記述３３を出力する。また、出力部１０５は、入力された合成制約３２に対して、Ｓ２６の関数化によって部分グラフから作成した関数については動作合成の際にインライン展開しないようにする条件を付加した合成制約３４を出力する（Ｓ２８）。
【００４０】
例えば、出力部１０５は、関数化による関数名「ｆｕｎｃ０」の関数をインライン展開しないようにフラグを付けた合成制約３４を出力する。これにより、高位合成部２０は、合成制約３４に付加された条件をもとに動作合成することで、部分グラフから作成した関数部分を単一のモジュールとして扱い、パイプライン合成する。このように部分グラフから作成した関数部分をパイプライン合成することで、論理回路のスループットを向上させることができる。
【００４１】
図１０は、前処理後の動作記述３３の一例を説明する説明図であり、より具体的には、図９のデータＤ７における繰り返し部分をループ化した後の動作記述３３を例示する図である。図４に例示した動作記述３１と、図１０に例示した動作記述３３とを比較しても明らかなように、動作記述３３では、動作記述３１に含まれるループ処理を展開した上で、同型の処理を行う部分を関数化している。
【００４２】
例えば、高位合成部２０において動作合成を行う場合、ループ処理の全展開において、スケジューリング・アロケーションアルゴリズムで計算量オーダ（Ｏ（Ｎ＾２）またはＯ（Ｎ・ｌｏｇ（Ｎ））等）におけるＮの部分が増加して、計算爆発が生じることがある。また、処理時間が長時間化して、動作合成における最適化が不十分となり、効率の悪い回路の回路記述が生成される場合がある。この場合には、レイテンシ数の大きい、深いパイプラインとなる回路記述が生成され、論理回路が巨大化する場合もある。
【００４３】
動作合成装置１では、高位合成部２０における動作合成の前処理として、入力された動作記述３１に含まれるループ処理を展開した上で、同型の処理を行う部分を関数化することで、上述した計算量オーダのＮの部分を抑えることができ、計算爆発が生じることを抑止できる。また、ループ処理を展開した上で、同型の処理を行う部分を関数化することにより、論理回路のレイテンシ数を小さくでき、内部にデータを抱え込む期間を短く、処理効率のよい回路の回路記述を得ることができる。これにより、例えば、論理回路に必要なバッファメモリ容量も削減でき、ストリーミング処理を効率的に行う回路の回路記述を得ることができる。
【００４４】
図１１は、高位合成による回路４０の一例を説明する説明図であり、より具体的には、図１０の動作記述３３を動作合成した場合の回路４０を例示する図である。図１１に示すように、回路４０は、メモリ４１、レジスタ４２、４３、４４、４５、４８、回路ブロック４６、制御回路４７を有し、入力データに対してＸＯＲ処理を施して出力データを出力する。なお、回路４０が扱うデータのビット幅は８ｂｉｔであるものとする。
【００４５】
メモリ４１は、入力データを記憶し、記憶された入力データをレジスタ４２〜４５へ出力する。回路ブロック４６は、レジスタ４２〜４５からの入力を受け付けて動作記述３３におけるｆｕｎｃ０の関数部分に対応する処理を行う。
【００４６】
図１２は、回路ブロック４６の一例を説明する説明図である。図１２に示すように、回路ブロック４６は、レジスタ４２〜４５からのデータ（ｉｎ０〜ｉｎ３）について、動作記述３３におけるｆｕｎｃ０の関数部分に対応するＸＯＲ演算を行うＸＯＲ演算器４６１〜４６３を有する。回路ブロック４６は、演算結果をｏｕｔ０として出力する。
【００４７】
制御回路４７は、回路４０の動作を制御する。制御回路４７に接続する外部からの信号線は、いつ入力データがメモリ４１に格納されたか、レジスタ４８に格納されたデータをいつ出力するのか等のタイミングを外部との間で調整するために用いる。レジスタ４８は、回路ブロック４６の演算結果（ｏｕｔ０）を記憶し、制御回路４７からの指示をもとに記憶されたデータを出力する。
【００４８】
制御回路４７の制御のもとで行われる回路４０の動作を説明する。まず、回路４０では、メモリ４１に入力データが格納される。次いで、制御回路４７は、メモリ４１に読み出しアドレスを指定し、メモリ４１から読み出されたデータをレジスタ４２〜４５に格納していく。制御回路４７は、上記の処理を４個のレジスタ４２〜４５それぞれについて、計４回行う。回路ブロック４６は、レジスタ４２〜４５に格納されたデータを読み出して演算し、演算結果をレジスタ４８に格納する。制御回路４７は、レジスタ４８に格納されたデータ（ｏｕｔ０）が有効になったこと外部に伝える。制御回路４７は、上述した処理を１６回繰り返す。
【００４９】
図１３は、高位合成による回路５０の一例を説明する説明図であり、より具体的には、図１７の動作記述２０２を前処理することなく動作合成した場合の回路５０を例示する図である。図１３に示すように、回路５０は、メモリ５１、５６、レジスタ５２、５３、５４、ＸＯＲ演算器５５、制御回路５７を有する。なお、回路４０と同様、回路５０が扱うデータのビット幅は８ｂｉｔであるものとする。
【００５０】
回路５０では、先ず、メモリ５１に入力データが格納される。次いで、制御回路５７は、メモリ５１とメモリ５６に読み出しアドレスを指定し、読み出されたデータをレジスタ５２〜５４に格納する。ＸＯＲ演算器５５は、レジスタ５２、５３のデータを演算した結果をメモリ５６に書き込む。回路５０では、上記の処理を４＊１６＝６４回繰り返す。
【００５１】
次いで、制御回路５７は、メモリ５６に読み出しアドレスを指定し、読み出されたデータをレジスタ５４に格納する。次いで、制御回路５７は、レジスタ５４に格納されたデータが有効になったことを外部に伝える。最初の出力データであるｏｕｔ０が有効となり、確定するタイミングは、図１８における解析結果２１２の時刻ｔ４である。制御回路５７は、上述した処理を１６回繰り返す。
【００５２】
回路４０における動作を解析した場合、変数の解析結果は、図１８に例示した解析結果２１１と同様の形となる。具体的には、レジスタ４８に格納されたデータが有効になるタイミング、すなわち、最初の出力データであるｏｕｔ０が確定するタイミングは、時刻ｔ１（１１）とほぼ同じ値となる。上述した回路４０と回路５０とを比較しても明らかなように、動作合成装置１では、入力された動作記述３１に対して前処理部１０による前処理を行うことで、効率的な処理を行う回路の回路記述３５を得ることができる。
【００５３】
なお、動作記述３１に含まれるループ処理については、ループの中にループが含まれる多重ループ以外の構成であってもよい。図１４は、動作記述の一例を説明する説明図である。図１４に示すように、動作記述に含まれるループ処理は、単純にループ処理が連続するものであってもよい。
【００５４】
図１５は、前処理後の動作記述３３の一例を説明する説明図である。より具体的には、図１５は、図１４に例示した動作記述を前処理した後の動作記述３３を例示する図である。図１５に示すように、単純にループ処理が連続する動作記述についても、ループ処理を展開した上で、同型の処理を行う部分を関数化した動作記述３３を得ることができる。
【００５５】
以上のように、動作合成装置１の前処理部１０は、入力された動作記述３１において、動作記述３１に含まれるループ処理を展開し、展開されたループ処理の中から同型の処理を行う部分を抽出し、抽出された部分を関数化する。動作合成装置１の高位合成部２０は、前処理部１０による前位処理後の動作記述３３に基づいて動作合成を行う。したがって、動作合成装置１では、動作記述３１のループ処理を展開した上で、同型の処理を行う部分を関数化しておくことで、論理回路のレイテンシ数を小さくでき、内部にデータを抱え込む期間を短く、処理効率のよい回路の回路記述３５を得ることができる。
【００５６】
上述した処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的におこなうこともできる。あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００５７】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散や統合の具体的形態は図示のものに限られない。つまり、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【００５８】
さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）および当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００５９】
図１６は、実施形態にかかる動作合成装置１として動作するコンピュータ３００のハードウェア構成を示す図である。図１６が示すように、コンピュータ３００は、各種演算処理を実行するＣＰＵ３１０、ＲＯＭ（Read  Only  Memory）３２０、ＨＤＤ（Hard  Disk  Drive）３３０、ＲＡＭ（Random  Access  Memory）３４０を有する。各装置３１０〜３４０は、バス３５０で接続される。
【００６０】
ＨＤＤ３３０は、上述した前処理部１０および高位合成部２０と同様の処理をコンピュータ３００に実行させるプログラム３３０ａを記憶する。ＣＰＵ３１０は、ＨＤＤ３３０に記憶されたプログラム３３０ａを読み出して、ＲＡＭ３４０に展開して実行することで、各種の処理を行う。
【００６１】
なお、上記のプログラム３３０ａは、必ずしもＨＤＤ３３０に記憶されている必要はない。例えば、コンピュータ３００が読み取り可能な記憶媒体に記憶されたプログラムを、コンピュータ３００が読み出して実行するようにしてもよい。コンピュータ３００が読み取り可能な記憶媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢ（Universal  Serial  Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ（Local  Area  Network）等に接続された装置にこのプログラムを記憶させておき、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【００６２】
１…動作合成装置
１０…前処理部
２０…高位合成部
３１、３３、２０１、２０２…動作記述
３２、３４…合成制約
３５…回路記述
１０１…展開部
１０２…最適化部
１０３…グラフ構築部
１０４…関数化部
１０５…出力部
２１１、２１２…解析結果
３００…コンピュータ
３３０ａ…プログラム
Ｄ１〜Ｄ７…データ
ｔ１〜ｔ４…時刻
【図１】
2016177454.tif 000003
【図２】
2016177454.tif 000004
【図３】
2016177454.tif 000005
【図４】
2016177454.tif 000006
【図５】
2016177454.tif 000007
【図６】
2016177454.tif 000008
【図７】
2016177454.tif 000009
【図８】
2016177454.tif 000010
【図９】
2016177454.tif 000011
【図１０】
2016177454.tif 000012
【図１１】
2016177454.tif 000013
【図１２】
2016177454.tif 000014
【図１３】
2016177454.tif 000015
【図１４】
2016177454.tif 000016
【図１５】
2016177454.tif 000017
【図１６】
2016177454.tif 000018
【図１７】
2016177454.tif 000019
【図１８】
2016177454.tif 000020