(57)【要約】      （修正有）【課題】柔軟性を伴った投機実行のスケジューリング機能を有する高位合成装置を提供する。【解決手段】高位合成装置１０００は、制御データフローグラフに含まれる演算ごとに、演算の実行順序を決定する実行順序決定部１２１と、動作記述における条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを複数通り生成する投機実行パターン生成部１２２と、投機実行パターン生成部１２２により生成された複数通りの投機実行パターンそれぞれの評価値を算出する投機実行パターン評価部１２３と、算出された評価値に基づいて投機実行パターンを選択する投機実行パターン選択部１２４と、を備える。【選択図】図１
2011013823.tif 000002
【特許請求の範囲】
【請求項１】
設計対象の回路の処理を表わす動作記述を入力する動作記述入力手段と、
前記動作記述入力手段により入力された前記動作記述を変換して制御データフローグラフを生成するＣＤＦＧ生成手段と、
前記ＣＤＦＧ生成手段により生成された前記制御データフローグラフに含まれる演算ごとに、前記演算の実行順序を決定する実行順序決定手段と、
前記実行順序決定手段により実行順序を決定された前記演算のうち、前記動作記述における条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを、前記条件分岐中の演算の実行順序を入れ替えて複数通り生成する投機実行パターン生成手段と、
前記投機実行パターン生成手段により生成された複数通りの前記投機実行パターンそれぞれの評価値を算出する投機実行パターン評価手段と、
前記投機実行パターン評価手段により算出された前記評価値に基づいて前記投機実行パターンを選択する投機実行パターン選択手段と、
前記ＣＤＦＧ生成手段により生成された前記制御データフローグラフと、前記投機実行パターン選択手段により選択された前記投機実行パターンと、に基づいて前記設計対象の回路のハードウェア構成を決定するバインディング手段と、
前記バインディング手段により決定された前記設計対象の回路の前記ハードウェア構成を、レジスタ転送レベル記述で表して出力するＲＬＴ記述出力手段と、
を備えることを特徴とする高位合成装置。
【請求項２】
請求項１に記載の高位合成装置であって、
前記実行順序決定手段は、予め定めれらた複数のタイムスロットのいずれかに前記演算をそれぞれ割り当て、
前記投機実行パターン生成手段は、前記条件分岐中の演算への前記タイムスロットの割り当てを変更して前記投機実行パターンを生成することを特徴とする高位合成装置。
【請求項３】
請求項２に記載の高位合成装置であって、
前記実行順序決定手段は、前記制御データフローグラフの開始点から各々の前記演算までの演算経由数を算出し、算出された前記演算経由数が同一の前記条件分岐中の演算を、同一の前記タイムスロットに割り当て、
前記投機実行パターン生成手段は、前記演算経由数が同一の前記条件分岐中の演算ごとに、前記タイムスロットの割り当てを変更することを特徴とする高位合成装置。
【請求項４】
請求項３に記載の高位合成装置であって、
前記投機実行パターン生成手段は、前記演算経由数が同一の前記条件分岐中の演算の集合体を一つのノードとし、複数の前記ノードそれぞれに前記タイムスロットを割り当てたツリー構造で表す投機実行ツリーを生成し、
前記投機実行パターン評価手段は、前記投機実行パターン生成手段により生成された前記投機実行ツリーの前記ノードをそれぞれ探索して葉ノードに着目したとき、当該葉ノードに関係付けられた上位ノードと当該葉ノードとから成る前記投機実行パターンに対して前記評価値を算出し、
前記投機実行パターン選択手段は、前記投機実行パターン評価手段により算出された前記評価値が所定の基準を満たしたとき、当該評価値に対応する前記投機実行パターンを選択することを特徴とする高位合成装置。
【請求項５】
請求項４に記載の高位合成装置であって、
前記投機実行パターン評価手段は、前記投機実行ツリーにおいて親ノードと同一の前記タイムスロットを割り当てられた子ノードを優先的に探索することを特徴とする高位合成装置。
【請求項６】
制御データフローグラフに含まれる演算ごとに、前記演算の実行順序を決定する実行順序決定ステップと、
前記実行順序決定ステップで前記実行順序を決定された前記演算のうち、条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを、前記条件分岐中の演算の実行順序を入れ替えて複数通り生成する投機実行パターン生成ステップと、
前記投機実行パターン生成ステップで生成された複数通りの前記投機実行パターンそれぞれの評価値を算出する投機実行パターン評価ステップと、
前記投機実行パターン評価ステップで算出された前記評価値に基づいて前記投機実行パターンを選択する投機実行パターン選択ステップと、
を備えることを特徴とする投機実行のスケジューリング方法。
【請求項７】
請求項６に記載の投機実行のスケジューリング方法であって、
前記実行順序決定ステップでは、予め定めれらた複数のタイムスロットのいずれかに前記演算をそれぞれ割り当て、
前記投機実行パターン生成ステップでは、前記条件分岐中の演算への前記タイムスロットの割り当てを変更して前記投機実行パターンを生成することを特徴とする投機実行のスケジューリング方法。
【請求項８】
請求項７に記載の投機実行のスケジューリング方法であって、
前記実行順序決定ステップでは、前記制御データフローグラフの開始点から各々の前記演算までの演算経由数を算出し、算出された前記演算経由数が同一の前記条件分岐中の演算を、同一の前記タイムスロットに割り当て、
前記投機実行パターン生成ステップでは、前記演算経由数が同一の前記条件分岐中の演算ごとに、前記タイムスロットの割り当てを変更することを特徴とする投機実行のスケジューリング方法。
【請求項９】
請求項８に記載の投機実行のスケジューリング方法であって、
前記投機実行パターン生成ステップでは、前記演算経由数が同一の前記条件分岐中の演算の集合体を一つのノードとし、複数の前記ノードそれぞれに前記タイムスロットを割り当てたツリー構造で表す投機実行ツリーを生成し、
前記投機実行パターン評価ステップでは、前記投機実行パターン生成ステップで生成された前記投機実行ツリーの前記ノードをそれぞれ探索して葉ノードに着目したとき、当該葉ノードに関係付けられた上位ノードと当該葉ノードとから成る前記投機実行パターンに対して前記評価値を算出し、
前記投機実行パターン選択ステップでは、前記投機実行パターン評価ステップで算出された前記評価値が所定の基準を満たしたとき、当該評価値に対応する前記投機実行パターンを選択することを特徴とする投機実行のスケジューリング方法。
【請求項１０】
請求項９に記載の投機実行のスケジューリング方法であって、
前記投機実行パターン評価ステップでは、前記投機実行ツリーにおいて親ノードと同一の前記タイムスロットを割り当てられた子ノードを優先的に探索することを特徴とする投機実行のスケジューリング方法。
【請求項１１】
プログラムに記述された条件分岐中の演算の投機実行に関するスケジューリングをコンピュータに実行させる投機実行用プログラムであって、
前記条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを、前記条件分岐中の演算の実行順序を入れ替えて複数通り生成する投機実行パターン生成処理と、
前記投機実行パターン生成処理で生成された複数通りの前記投機実行パターンそれぞれの評価値を算出する投機実行パターン評価処理と、
前記投機実行パターン評価処理で算出された前記評価値に基づいて前記投機実行パターンを選択する投機実行パターン選択処理と、
を前記コンピュータに実行させることを特徴とする投機実行用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高位合成装置、投機実行のスケジューリング方法および投機実行用プログラムに関する。
【背景技術】
【０００２】
近年、高位合成技術において、ネスト構造を持ったif文・並列構造を持ったif文を系統的に扱う有用な記法およびスケジューリング手法が提案されている。
【０００３】
この種の技術として、特許文献１（特開２００８−９０４３９号公報）には、次のような技術が記載されている。高位合成装置に入力される動作記述の演算ノードが属する外側の条件演算が未確定であって、内側の条件演算が確定している場合に、ベクタの一部の連続部分に一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ：ＧＣＶ）を生成する。そして、上記動作記述に対応する制御データフローグラフ（Ｃｏｎｔｒｏｌ  Ｄａｔａ  Ｆｌｏｗ  Ｇｒａｐｈ：ＣＤＦＧ）の演算ノードに設定された一般化条件ベクタに基づいてスケジューリング処理を実行する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−９０４３９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら上記技術は、以下の点で改善の余地を有していた。ネストした条件分岐やより複雑で条件分岐構造内に含まれている演算処理ごとに投機実行の順序の調節を行うスケジューリング手法が提案されておらず、投機実行に関するスケジューリングの柔軟性が欠けていた。このため、幅広いレイテンシ（遅延時間）／面積の探索を効果的に行うことができず、よりよい解空間の探索が行えないという課題がある。
【０００６】
本発明は上記事情に鑑みてなされたものであり、その目的とするところは、柔軟性を伴った投機実行に関するスケジューリング機能を有する高位合成装置、またはそれに適用される投機実行のスケジューリング方法および投機実行用プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明によれば、設計対象の回路の処理を表わす動作記述を入力する動作記述入力手段と、前記動作記述入力手段により入力された前記動作記述を変換して制御データフローグラフを生成するＣＤＦＧ生成手段と、前記ＣＤＦＧ生成手段により生成された前記制御データフローグラフに含まれる演算ごとに、前記演算の実行順序を決定する実行順序決定手段と、前記実行順序決定手段により前記実行順序を決定された前記演算のうち、前記動作記述における条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを、前記条件分岐中の演算の実行順序を入れ替えて複数通り生成する投機実行パターン生成手段と、前記投機実行パターン生成手段により生成された複数通りの前記投機実行パターンそれぞれの評価値を算出する投機実行パターン評価手段と、前記投機実行パターン評価手段により算出された前記評価値に基づいて前記投機実行パターンを選択する投機実行パターン選択手段と、前記ＣＤＦＧ生成手段により生成された前記制御データフローグラフと、前記投機実行パターン選択手段により選択された前記投機実行パターンと、に基づいて前記設計対象の回路のハードウェア構成を決定するバインディング手段と、前記バインディング手段により決定された前記設計対象の回路の前記ハードウェア構成を、レジスタ転送レベル記述で表して出力するＲＬＴ記述出力手段と、を備えることを特徴とする高位合成装置が提供される。
【０００８】
また、本発明によれば、制御データフローグラフに含まれる演算ごとに、前記演算の実行順序を決定する実行順序決定ステップと、前記実行順序決定ステップで前記実行順序を決定された前記演算のうち、条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを、前記条件分岐中の演算の実行順序を入れ替えて複数通り生成する投機実行パターン生成ステップと、前記投機実行パターン生成ステップで生成された複数通りの前記投機実行パターンそれぞれの評価値を算出する投機実行パターン評価ステップと、前記投機実行パターン評価ステップで算出された前記評価値に基づいて前記投機実行パターンを選択する投機実行パターン選択ステップと、を備えることを特徴とする投機実行のスケジューリング方法が提供される。
【０００９】
さらに、本発明によれば、プログラムに記述された条件分岐中の演算の投機実行に関するスケジューリングをコンピュータに実行させる投機実行用プログラムであって、前記条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを、前記条件分岐中の演算の実行順序を入れ替えて複数通り生成する投機実行パターン生成処理と、前記投機実行パターン生成処理で生成された複数通りの前記投機実行パターンそれぞれの評価値を算出する投機実行パターン評価処理と、前記投機実行パターン評価処理で算出された前記評価値に基づいて前記投機実行パターンを選択する投機実行パターン選択処理と、を前記コンピュータに実行させることを特徴とする投機実行用プログラムが提供される。
【発明の効果】
【００１０】
本発明によれば、柔軟性を伴った投機実行に関するスケジューリング機能を有する高位合成装置、またはそれに適用される投機実行方法および投機実行用プログラムが提供される。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態に係る高位合成装置の構成図である。
【図２】ｉｆ文がネスト構造となっている動作記述の一例を示す図である。
【図３】図２の動作記述から生成されたＣＤＦＧを示す図である。
【図４】ｉｆ文が並列構造となっている動作記述の一例を示す図である。
【図５】図４の動作記述から生成されたＣＤＦＧを示す図である。
【図６】図３のＣＤＦＧに表される投機実行パターンをツリー構造で表した投機実行ツリーを示す図である。
【図７】本発明の実施の形態に係る高位合成装置に適用されるフローチャートである。
【図８】図７のスケジューリングステップの詳細を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００１３】
図１は、本発明の実施の形態に係る高位合成装置１０００の構成図である。高位合成装置１０００は、情報処理部１００、記憶部２００、動作記述入力部３００およびＲＬＴ記述出力部４００から構成される。
【００１４】
動作記述入力部３００は、設計対象の回路の処理を表わす動作記述を入力する。ここで動作記述とは、ある処理を実行する専用ハードウェアを設計する際に、対象となる処理のアルゴリズムを直接的に記述したものであり、Ｃ言語、Ｃ＋＋言語、ＳｙｓｔｅｍＣ言語等で記述されてもよい。
【００１５】
また、動作記述入力部３００としては、例えばキーボード、マウスポインタ、タッチパネル等であって、ユーザの操作入力によって動作記述を入力してもよい。もしくは、動作記述入力部３００としては、例えば他装置（図示せず）とのインタフェイス回路であって、他装置によって生成された動作記述を要求して、当該他装置から動作記述を入力してもよい。
【００１６】
ＲＬＴ記述出力部４００は、情報処理部１００（バインディング部１３０）により決定された設計対象の回路のハードウェア構成を、レジスタ転送レベル記述で表して出力する。ここで、ＲＬＴ記述出力部４００の出力方法としては、ディスプレイ装置等を用いて表示出力してもよいし、印刷装置等を用いて印刷出力してもよいし、これらの組み合わせであってもよい。
【００１７】
情報処理部１００は処理したデータや変数等を記憶部２００に適宜記憶させてもよい。さらに、情報処理部１００は記憶部２００に記憶されているプログラムやデータ等を適宜読み出してもよい。
【００１８】
情報処理部１００は、ＣＤＦＧ生成部１１０、スケジューリング部１２０およびバインディング部１３０を内包している。特に、スケジューリング部１２０は、実行順序決定部１２１、投機実行パターン生成部１２２、投機実行パターン評価部１２３および投機実行パターン選択部１２４を有している。
【００１９】
ＣＤＦＧ生成部１１０は、動作記述入力部３００により入力された動作記述を変換して制御データフローグラフ（以下、ＣＤＦＧ）を生成する。より詳細には、入力された動作記述の字句・構文を解析した後に、浮動小数点演算の変換を行ってＣＤＦＧに変換する。
【００２０】
実行順序決定部１２１は、ＣＤＦＧ生成部１１０により生成されたＣＤＦＧに含まれる演算ごとに、演算の実行順序を決定する。実行順序決定部１２１は、予め定めれらた複数のタイムスロットのいずれかに演算をそれぞれ割り当てる。
【００２１】
投機実行パターン生成部１２２は、実行順序決定部１２１により実行順序を決定された演算のうち、動作記述における条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを、条件分岐中の演算の実行順序を入れ替えて複数通り生成する。より詳細には、投機実行パターン生成部１２２は、条件分岐中の演算へのタイムスロットの割り当てを変更して投機実行パターンを生成する。ここで、条件分岐中の演算とは、ｉｆ文ネスト構造内部の演算であってもよいし、ｉｆ文並列構造内部の演算であってもよい。また、演算の種別も加算、減算、乗算、比較演算等いずれであってもよい。
【００２２】
図２は、ｉｆ文がネスト構造となっている動作記述の一例を示す図である。また、図３は、図２の動作記述から生成されたＣＤＦＧを示す図である。図２に示す記述においては、「ａ＝ａ＊ｃ」、「ａ＝ａ＊ｄ」、「ａ＝ａ＋ｅ」、「ａ＝ａ＋ｆ」等が、条件分岐中の演算である。
【００２３】
図４は、ｉｆ文が並列構造となっている動作記述の一例を示す図である。また、図５は、図４の動作記述から生成されたＣＤＦＧを示す図である。図４に示す記述においては、「ｅ＝ａ＋ｂ」、「ｅ＝ｃ＋ｄ」、「ｉ＝ｇ＊ｈ１」、「ｉ＝ｇ＊ｈ２」等が、条件分岐中の演算である。
【００２４】
実行順序決定部１２１が、演算をタイムスロットに割り当てる手法は種々存在する。本実施形態において、実行順序決定部１２１は、ＣＤＦＧ生成部１１０により生成されたＣＤＦＧの開始点から各々の演算までの演算経由数Ｎを算出し、算出された演算経由数Ｎが同一の条件分岐中の演算を、同一のタイムスロットに割り当てる手法を用いる。
【００２５】
例えば、図３のＣＤＦＧにおいて、演算経由数Ｎ＝１の条件分岐中の演算は「ａ＝ａ＋ｂ」と「ａ＝ａ＋ｆ」であり、演算経由数Ｎ＝２の条件分岐中の演算は「ａ＝ａ＊ｃ」と「ａ＝ａ＊ｄ」と「ａ＝ａ＊ｇ」と「ａ＝ａ＊ｈ」であり、演算経由数Ｎ＝３の条件分岐中の演算は「ａ＝ａ＋ｅ」と「ａ＝ａ＋ｉ」である。
【００２６】
ここで、演算経由数Ｎ＝１の条件分岐中の演算に割り当てたタイムスロットをスロットＳ１、演算経由数Ｎ＝２の条件分岐中の演算に割り当てたタイムスロットをスロットＳ２、演算経由数Ｎ＝３の条件分岐中の演算に割り当てたタイムスロットをスロットＳ３とする。スロット１、スロット２およびスロット３は時間的に連続したタイムスロットであってもよいし、各々のタイムスロットの間に時間間隔が設けられてもよい。なお、投機実行をしないのであれば、演算経由数Ｎが小さい順に演算が実行されることが一般的であり、本実施形態においてもスロット１→スロット２→スロット３の順で実行するものとする。
【００２７】
実行順序決定部１２１が上記のような手法を用いた場合、投機実行パターン生成部１２２は、演算経由数が同一の条件分岐中の演算ごとに、タイムスロットの割り当てを変更する。より詳細には、投機実行パターン生成部１２２は、演算経由数Ｎが同一の条件分岐中の演算の集合体を一つのノードとし、複数のノードそれぞれにタイムスロットを割り当てたツリー構造で表す投機実行ツリーを生成する。なお、ここで集合体とは、少なくとも一つの演算から構成されるものとする。
【００２８】
図６は、図３のＣＤＦＧに表される投機実行パターンをツリー構造で表した投機実行ツリーを示す図である。この投機実行ツリーはノードＮ１〜ノードＮ９の９つのノードで構成されている。なお、この投機実行ツリーにおいて、ノードＮ１→ノードＮ２→ノードＮ６等の根ノードから葉ノードまでに含まれる一連のノードが、１通りの投機実行パターンを表している。すなわち、この投機実行ツリーは全体で６通りの投機実行パターンを表している。
【００２９】
この投機実行ツリーにおいて、例えばノード内の「２→１」の記載は、実行順序決定部１２１によってスロット２を割り当てられた演算の集合体に、スロット１を割り当てることを意味している。すなわち、ノードＮ１→ノードＮ３→ノードＮ９で表される投機実行パターンは、これらのノードに含まれる全ての演算をスロット１で実行することを示している。なお、ノードＮ１→ノードＮ２→ノードＮ４で表される投機実行パターンは、実行順序決定部１２１が決定した実行順序と全く同じ順序である。つまり、この投機実行パターンが投機実行パターン選択部１２４によって選択されることは、条件分岐中の演算の投機実行が行われないことを意味する。
【００３０】
本実施形態の投機実行ツリーにおいては、条件分岐中の演算をスロットＳ１〜スロットＳ３のいずれかに割り当てることを前提としている。しかし、スロットＳ１より前の時間帯を示すタイムスロットや、スロットＳ１とスロットＳ２との間の時間帯またはスロットＳ２とスロットＳ３との間の時間帯を示すタイムスロットが存在するのであれば、これらのタイムスロットも条件分岐中の演算の投機実行に用いてもよい。この場合、当然ながら図６に示す投機実行ツリーより多分岐となる。
【００３１】
投機実行パターン評価部１２３は、投機実行パターン生成部１２２により生成された複数通りの投機実行パターンそれぞれの評価値を算出する。より詳細には、投機実行パターン評価部１２３は、投機実行パターン生成部１２２により生成された投機実行ツリーのノードをそれぞれ探索して葉ノードに着目したとき、当該葉ノードと関係付けられた上位ノードと当該葉ノードとから成る投機実行パターンに対して評価値を算出する。例えば、図６においてはノードＮ４〜ノードＮ９が葉ノードであり、投機実行パターン評価部１２３がこれらのいずれかに着目したときに、着目した葉ノードを含む投機実行パターンの評価値を算出する。
【００３２】
なお、投機実行パターン評価部１２３は、投機実行ツリーにおいて親ノードと同一のタイムスロットを割り当てられた子ノードを優先的に探索することが望ましい。すなわち、図６においては、ノードＮ２を根ノードとする部分木よりノードＮ３を根ノードとする部分木を優先的に探索することが好ましい。さらに、ノードＮ３を根ノードとする部分木の中でもノードＮ９がノードＮ８やノードＮ７より優先的に探索されることが好ましい。
【００３３】
また、投機実行パターン評価部１２３が算出する評価値は、設計対象の回路に実装される演算器やレジスタ等のハードウェアの数、当該回路の予測面積、当該回路における予測遅延時間等の少なくとも一つを評価値として算出してもよい。これらを算出する手法としては既知な技術を利用してもよい。例えば、上述した特許文献１に記載されている条件ベクタを用いた手法を利用してもよい。
【００３４】
投機実行パターン選択部１２４は、投機実行パターン評価部１２３により算出された評価値に基づいて投機実行パターンを選択する。より詳細には、投機実行パターン選択部１２４は、投機実行パターン評価部１２３により算出された評価値が所定の基準を満たしたとき、当該評価値に対応する投機実行パターンを選択する。
【００３５】
ここで、所定の基準とは、投機実行パターン評価部１２３により算出される評価値によって異なるが、例えば、設計対象の回路に実装される演算器やレジスタ等のハードウェアの制約数、当該回路の許容最大面積、当該回路における許容最大遅延時間等の少なくとも一つを所定の基準として用いてもよい。
【００３６】
バインディング部１３０は、ＣＤＦＧ生成部１１０により生成されたＣＤＦＧと、投機実行パターン選択部１２４により選択された投機実行パターンと、に基づいて設計対象の回路のハードウェア構成を決定する。すなわち、バインディング部１３０は、ＣＤＦＧに示される実行順序と、投機実行パターンに示される条件分岐中の演算を投機実行する実行順序と、を反映して設計対象の回路のハードウェア構成を決定する。
【００３７】
図７は、本実施形態の高位合成装置１０００に適用されるフローチャートである。このフローチャートは、設計対象の回路の処理を表わす動作記述を入力する動作記述入力ステップ（ステップＳ１１）を備える。また、このフローチャートは、ステップＳ１１で入力された動作記述を変換してＣＤＦＧを生成するＣＤＦＧ生成ステップ（ステップＳ１２）を備える。また、このフローチャートは、ステップＳ１２で生成されたＣＤＦＧに含まれる演算のうち、条件分岐中の演算の投機実行の順序を示す投機実行パターンを選択するスケジューリングステップ（ステップＳ１３）を備える。また、このフローチャートは、ステップＳ１２で生成されたＣＤＦＧと、ステップＳ１３で選択された投機実行パターンと、に基づいて設計対象の回路のハードウェア構成を決定するバインディングステップ（ステップＳ１４）を備える。また、このフローチャートは、ステップＳ１４で決定された設計対象の回路のハードウェア構成を、レジスタ転送レベル記述で表して出力するＲＬＴ記述出力ステップ（ステップＳ１５）を備える。
【００３８】
図８は、図７のスケジューリングステップ（ステップＳ１３）の詳細を示すフローチャートである。このフローチャートは、ＣＤＦＧに含まれる演算ごとに、演算の実行順序を決定する実行順序決定ステップ（ステップＳ１３１）を含む。また、このフローチャートは、ステップＳ１３１で実行順序を決定された演算のうち、条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを、条件分岐中の演算の実行順序を入れ替えて複数通り生成する投機実行パターン生成ステップ（ステップＳ１３２）を含む。さらに、このフローチャートは、ステップＳ１３２で生成された複数通りの投機実行パターンそれぞれの評価値を算出する投機実行パターン評価ステップ（ステップＳ１３５）を含む。さらに、このフローチャートは、ステップＳ１３５で算出された評価値に基づいて投機実行パターンを選択する投機実行パターン選択ステップ（ステップＳ１３７）を含む。
【００３９】
より詳細には、高位合成装置１０００は、演算経由数Ｎが同一の条件分岐中の演算の集合体を一つのノードとし、複数のノードそれぞれにタイムスロットを割り当てたツリー構造で表す投機実行ツリーを生成する（ステップＳ１３２）。そして、高位合成装置１０００は、ステップＳ１３２で生成された投機実行ツリーのノードをそれぞれ探索して（ステップＳ１３３）、葉ノードに着目したとき（ステップＳ１３４のＹＥＳ）、当該葉ノードに関係付けられた上位ノードと当該葉ノードとから成る投機実行パターンに対して評価値を算出する（ステップＳ１３５）。なお、着目したノードが葉ノードではないとき（ステップＳ１３４のＮＯ）、ステップＳ１３３に移行して別のノードを探索する。
【００４０】
さらに、高位合成装置１０００は、ステップＳ１３５で算出された評価値が所定の基準を満たしたとき（ステップＳ１３６のＹＥＳ）、当該評価値に対応する投機実行パターンを選択する（ステップＳ１３７）。なお、ステップＳ１３５で算出された評価値が所定の基準を満たさないとき（ステップＳ１３６のＮＯ）、ステップＳ１３３に移行して別のノードを探索する。
【００４１】
ここで、本実施形態の効果について説明する。本実施形態の高位合成装置１０００は、ＣＤＦＧに含まれる演算ごとに実行順序を決定し、これらの実行順序を組み替えて投機実行のスケジューリングを行うので、柔軟性の高いスケジューリングを実現することができる。
【００４２】
また、本実施形態は、投機実行ツリーを探索しながら評価値を算出し、算出された評価値が所定の基準を満たしたとき、当該評価値に対応する投機実行パターンを選択するので、全部の投機実行パターンの評価値を算出しなくても、所望の投機実行パターンを選択することが可能である。これにより、投機実行に関わるスケジューリング処理の負荷コストが軽減される。
【００４３】
さらに、本実施形態は、親ノードと同一のタイムスロットを割り当てられた子ノードを優先的に探索するので、効率的に所望の投機実行パターンを探索することができる。その理由は、同一のタイムスロットに割り当てられた演算が多いほど、レイテンシは短く、合成面積は大きくなる傾向がある。よって、上述のような探索手法を用いることによって、ランダムに探索するより速やかに所望の投機実行パターンを探索することができる。
【００４４】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【００４５】
上記の実施形態において、演算の実行順序を決定するために、各演算をタイムスロットのいずれかに割り当てる手法を用いたが、これに限らなくてもよい。例えば、各演算の実行するタイミングを絶対時間で決めてもよい。
【００４６】
上記の実施形態において、複数通りの投機実行パターンを生成する手法として投機実行ツリーを用いることを説明したが、これに限らなくてもよい。例えば、データテーブルを用いてもよい。
【００４７】
上記の実施形態は、情報処理部１００の各部の実現方法について言及しなかったが、コンピュータプログラムにより各種機能として論理的に実現されてもよいし、固有のハードウェアとして形成してもよいし、ソフトウェアとハードウェアとの組み合わせとして実現してもよい。
【００４８】
例えば、上記実施形態において、情報処理部１００に以下のような特徴を有する投機実行用プログラムを実行させて、投機実行パターン生成部１２２、投機実行パターン評価部１２３、投機実行パターン選択部１２４を実現してもよい。すなわち、この投機実行用プログラムは、動作記述（プログラム）に記述された条件分岐中の演算の投機実行に関するスケジューリングを情報処理部１００（コンピュータ）に実行させるプログラムである。そして、この投機実行用プログラムは、条件分岐中の演算を投機実行する実行順序を示す投機実行パターンを複数通り生成する投機実行パターン生成処理を情報処理部１００に実行させてもよい。また、この投機実行用プログラムは、投機実行パターン生成処理で生成された複数通りの投機実行パターンそれぞれの評価値を算出する投機実行パターン評価処理を情報処理部１００に実行させてもよい。また、この投機実行用プログラムは、投機実行パターン評価処理で算出された評価値に基づいて投機実行パターンを選択する投機実行パターン選択処理を情報処理部１００に実行させてもよい。
【００４９】
なお、当然ながら、上述した実施の形態および複数の変形例は、その内容が相反しない範囲で組み合わせることができる。また、上述した実施の形態および変形例では、各構成要素の機能などを具体的に説明したが、その機能などは本願発明を満足する範囲で各種に変更することができる。
【００５０】
また、図７および図８のフローチャートには複数のステップを順番に記載してあるが、その記載の順番は複数のステップを実行する順番を限定するものではない。このため、本発明を実行するときには、その複数のステップの順番は内容的に支障しない範囲で変更することができる。
【符号の説明】
【００５１】
１０００  高位合成装置
１００  情報処理部
１１０  ＣＤＦＧ生成部
１２０  スケジューリング部
１２１  実行順序決定部
１２２  投機実行パターン生成部
１２３  投機実行パターン評価部
１２４  投機実行パターン選択部
１３０  バインディング部
２００  記憶部
３００  動作記述入力部
４００  ＲＬＴ記述出力部
Ｎ１〜Ｎ９  ノード
【図１】
2011013823.tif 000003
【図２】
2011013823.tif 000004
【図３】
2011013823.tif 000005
【図４】
2011013823.tif 000006
【図５】
2011013823.tif 000007
【図６】
2011013823.tif 000008
【図７】
2011013823.tif 000009
【図８】
2011013823.tif 000010