(57)【要約】【課題】できるだけ短時間で最適なスケジューリング解を求める。【解決手段】  最多の演算処理部が割り付けられる可能性のある実行ステップに含まれる複数の演算処理部から二つの演算処理部を選ぶ順列を抽出する順列抽出手段１１４Ｃと、抽出された各演算処理部の順列から一つを選び、選んだ二つの演算処理部間に、実行順序を決定する枝を挿入し、この枝が挿入されたコントロールデータフローグラフの自由度を用いてコントロールデータフローグラフの評価値を求める評価値算出処理を全順列の組合せについて実行する評価値算出手段１１４Ｄと、評価値が最も高い組合せを選択することにより、複数の演算処理に対応した実行ステップをそれぞれ決定する実行ステップ決定手段１１４Ｅとの各種機能を実行する。【選択図】  図２
2005316785.tif 000002
【特許請求の範囲】
【請求項１】
回路動作が表現された動作記述を用いて、演算処理部を示す節点とデータの流れを示す枝により生成されたコントロールデータフローグラフ中の各演算処理を実行する実行ステップをスケジューリング手段でそれぞれ決定して、レジスタトランスファレベルの設計回路を自動合成する高位合成装置において、
該スケジューリング手段は、
該コントロールデータフローグラフ中で同一種類の複数の演算処理部が同一実行ステップで実行される可能性がある場合に、該複数の演算処理部のうち二つの演算処理部を表す節点間に枝を挿入して該節点間の前後関係を決定し、該枝が挿入されたコントロールデータフローグラフの自由度を用いて該コントロールデータフローグラフの評価値を求める評価値算出手段と、
該評価値が最も大きいコントロールデータフローグラフを選択して、該複数の演算処理部に対応した実行ステップをそれぞれ決定する実行ステップ決定手段とを有する高位合成装置。
【請求項２】
前記評価値算出手段は、前記枝を挿入する二つの節点の順列が複数ある場合は、該節点間の前後関係を決定するときに、該枝を挿入する二つの節点の順列を所定の評価関数を用いて決定する請求項１に記載の高位合成装置。
【請求項３】
前記評価関数は、前記前後関係を与えた後のコントロールデータフローグラフ中の各演算処理部のスケジューリング可能な実行ステップの個数を用いて評価値を求める請求項２に記載の高位合成装置。
【請求項４】
前記実行ステップ決定手段は、前記コントロールデータフローグラフの実行ステップ数が、最小の実行ステップ数かまたは、与えられた実行ステップ数を越えない範囲で、できるだけ演算器を減らす場合には、二つの演算処理部間に前後関係を与えたときに実行ステップ数が延びないコントロールデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択する請求項１または３に記載の高位合成装置。
【請求項５】
前記実行ステップ決定手段は、与えられた演算器数を越えない範囲で、できるだけコントロールデータフローグラフの実行ステップ数を減らす場合には、二つの演算処理部間に前後関係を与えたときに該実行ステップ数が延びないコントロールデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択し、仮に、該実行ステップ数が延びないコントロールデータフローグラフがないなら、該実行ステップ数が延びるデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択する請求項１または３に記載の高位合成装置。
【請求項６】
前記スケジューリング手段は、
各演算処理をできるだけ早く実行する第１スケジューリングと該各演算処理をできるだけ遅く実行する第２スケジューリングとに基づいて、各実行ステップにスケジューリングされる可能性がある各演算処理部の割付表を作成する割付表作成手段と、
該割付表に基づいて、最多の演算処理部が割り付けられる可能性のある実行ステップに含まれる複数の演算処理部から二つの演算処理部を選ぶ順列を抽出する順列抽出手段とを更に有し、
前記評価値算出手段は、抽出された各演算処理部の順列から一つを選び、選んだ二つの演算処理部間に、実行順序を決定する枝を挿入し、該枝が挿入されたコントロールデータフローグラフの自由度を用いて該コントロールデータフローグラフの評価値を求める評価値算出処理を全順列について実行し、
前記実行ステップ決定手段は、該評価値が最も高い順列の組合せを選択することにより、前記複数の演算処理に対応した実行ステップをそれぞれ決定する請求項1〜５のいずれかに記載の高位合成装置。
【請求項７】
前記スケジューリング手段は、
最小の実行ステップ数か、または、ある与えられた実行ステップ数を越えないようにする場合に、前記実行ステップ決定手段で選んだ評価値が正のときは前記割付表作成手段で割付表を再度作成して、前記順列抽出手段、評価値算出手段および実行ステップ決定手段による各処理を繰り返し、または、該評価値が正以外のときは演算終了判定を行う演算終了判定手段を更に有する請求項６に記載の高位合成装置。
【請求項８】
前記スケジューリング手段は、
演算器数を上限個数以下にする場合に、実行ステップで演算処理部数が演算器数の上限個数よりも大きいときは前記割付表作成手段で割付表を再度作成して、前記順列抽出手段、評価値算出手段および実行ステップ決定手段による各処理を繰り返し、または、該全ての実行ステップで演算処理部数が演算器数の上限個数よりも小さいか同じときは演算終了判定を行う演算終了判定手段を更に有する請求項６に記載の高位合成装置。
【請求項９】
前記スケジューリング手段は、
前記割付表作成手段の前段に、占有面積が大きい演算器で実行する演算処理の種類から先に、該演算処理の種類を決定する演算種類決定手段を更に有し、
前記演算終了判定手段の後段に、全演算種類が終了したかどうかを判定する全演算種類終了判定手段を更に有して、該全演算種類が終了していない場合には該演算種類決定手段により該演算処理の種類を決定して、前記割付表作成手段、順列抽出手段、評価値算出手段、実行ステップ決定手段、演算終了判定手段および全演算種類終了判定手段による各処理を繰り返す請求項７または８に記載の高位合成装置。
【請求項１０】
回路動作が表現された動作記述を用いて、演算処理を示す節点とデータの流れを示す枝により生成されたコントロールデータフローグラフ中の各演算処理を実行する実行ステップを決定するスケジューリング方法において、
該コントロールデータフローグラフ中で同一種類の複数の演算処理部が同一実行ステップで実行される可能性がある場合に、該複数の演算処理部のうち二つの演算処理部を表す節点間に枝を挿入して該節点間の前後関係を決定し、該枝が挿入されたコントロールデータフローグラフの自由度を用いて該コントロールデータフローグラフの評価値を求める評価値算出処理手順と、
該評価値が最も大きいコントロールデータフローグラフを選択して、該複数の演算処理部に対応した実行ステップをそれぞれ決定する実行ステップ決定処理手順とを有するスケジューリング方法。
【請求項１１】
前記評価値算出処理手順は、前記枝を挿入する二つの節点の組合せが複数ある場合は、該節点間の前後関係を決定するときに、該枝を挿入する二つの節点の順列を評価関数を用いて決定する請求項１０に記載のスケジューリング方法。
【請求項１２】
前記評価関数は、前記前後関係を与えた後のコントロールデータフローグラフ中の各演算処理部のスケジューリング可能な実行ステップの個数を用いて評価値を求める請求項１１に記載のスケジューリング方法。
【請求項１３】
前記実行ステップ決定処理手順は、コントロールデータフローグラフの実行ステップ数が、最小の実行ステップ数か、または、与えられた実行ステップ数を越えない範囲で、できるだけ演算器を減らす場合には、二つの演算処理部間に前後関係を与えたときに実行ステップ数が延びないコントロールデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択する請求項１０または１２に記載のスケジューリング方法。
【請求項１４】
前記実行ステップ決定処理手順は、与えられた演算器数を越えない範囲で、できるだけコントロールデータフローグラフの実行ステップ数を減らす場合には、二つの演算処理部間に前後関係を与えた時に該実行ステップ数が延びないコントロールデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択し、仮に、該実行ステップ数が延びないコントロールデータフローグラフがないなら、該実行ステップ数が延びるデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択する請求項１０または１２に記載のスケジューリング方法。
【請求項１５】
各演算処理をできるだけ早く実行する第１スケジューリングと該各演算処理をできるだけ遅く実行する第２スケジューリングとに基づいて、各実行ステップにスケジューリングされる可能性がある各演算処理部の割付表を作成する割付表作成処理手順と、
該割付表に基づいて、最多の演算処理部が割り付けられる可能性のある実行ステップに含まれる複数の演算処理部から二つの演算処理部を選ぶ順列を抽出する順列抽出処理手順とを更に有し、
前記評価値算出処理手順は、抽出された各演算処理部の順列から一つを選び、選んだ二つの演算処理部間に、実行順序を決定する枝を挿入し、該枝が挿入されたコントロールデータフローグラフの自由度を用いて該コントロールデータフローグラフの評価値を求める評価値算出処理を全順列について実行し、
前記実行ステップ決定処理手順は、該評価値が最も高い順列の組合せを選択することにより、前記複数の演算処理に対応した実行ステップをそれぞれ決定する請求項１０〜１４のいずれかに記載のスケジューリング方法。
【請求項１６】
最小の実行ステップ数か、または、ある与えられた実行ステップ数を越えないようにする場合に、前記実行ステップ決定処理手順で選んだ評価値が正のときは前記割付表作成処理手順で割付表を再度作成して、前記順列抽出処理手順、評価値算出処理手順および実行ステップ決定処理手順による各処理を繰り返し、または、該評価値が正以外のときは演算終了判定を行う演算終了判定処理手順を更に有する請求項１５に記載のスケジューリング方法。
【請求項１７】
演算器数を上限個数以下にする場合に、実行ステップで演算処理部数が演算器数の上限個数よりも大きいときは前記割付表作成処理手順で割付表を再度作成して、前記順列抽出処理手順、評価値算出処理手順および実行ステップ決定処理手順による各処理を繰り返し、または、該全ての実行ステップで演算処理部数が演算器数の上限個数よりも小さいか同じときは演算終了判定を行う演算終了判定処理手順を更に有する請求項１５に記載のスケジューリング方法。
【請求項１８】
前記割付表作成処理手順の前段に、占有面積が大きい演算器で実行する演算処理の種類から先に、該演算処理の種類を決定する演算種類決定処理手順を更に有し、
前記演算終了判定処理手順の後段に、全演算種類が終了したかどうかを判定する全演算種類終了判定処理手順を更に有して、該全演算種類が終了していない場合には該演算種類決定処理手順により該演算処理の種類を決定して、前記割付表作成処理手順、順列抽出処理手順、評価値算出処理手順、実行ステップ決定処理手順、演算終了判定処理手順および全演算種類終了判定処理手順による各処理を繰り返す請求項１６または１７に記載のスケジューリング方法。
【請求項１９】
請求項１０〜１８のいずれかに記載のスケジューリング方法における各処理手順をコンピュータに実行させるためのスケジューリングプログラム。
【請求項２０】
請求項１９に記載のスケジューリングプログラムを記録したコンピュータ読み取り可能な可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回路動作が表現された動作記述を解析し、解析された動作情報からレジスタトランスファーレベルの回路を高位合成する高位合成装置、この高位合成処理において、動作記述から、各種処理手段を示す各節点とデータの流れを示す入出力枝によりコントロールデータフローグラフを生成し、コントロールデータフローグラフ中の各演算を実行するステップを決定するスケジューリング処理を行うスケジューリング方法、スケジューリングプログラムおよび可読記録媒体に関する。
【背景技術】
【０００２】
近年、システムＬＳＩなどの回路の大規模化に伴い、回路を動作記述言語で記述し、そこからＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌｅｖｅｌ；レジスタ・トランスファ・レベル）記述を生成する、動作合成技術が用いられるようになっている。この動作合成は高位合成とも言われている。例えば、雑誌である非特許文献１に記載の動作合成システムは、Ｃ言語を回路設計用に拡張した言語を動作記述言語として、回路を高位合成することが可能である。
【０００３】
この動作記述とは、回路の構造に関する情報を含まずに、処理のアルゴリズムのみを記述したものであり、Ｃ言語や、Ｃ＋＋言語、Ｓｙｓｔｅｍ−Ｃ言語、Ｓｐｅｃ−Ｃ言語や、それらを拡張した言語が用いられている。
【０００４】
図２１はＣ言語で書かれた動作記述の一例を示す図であり、図２２は図２１の動作記述から得られるデータフローグラフの一例を示す図である。
【０００５】
動作合成では、まず、入力した図２１の動作記述を図２２に示すようなデータフローグラフと言われるデータ形式に変換する。このデータフローグラフ中の各節点は演算を表し、枝はデータの流れを表している。図２２では、乗算を表す節点２０１は「ａ」と「ｂ」とが乗算されて加算「＋」を表す節点２０３に結果を渡す。これと同様に、節点２０２は「ｃ」と「ｄ」を乗算する。節点２０３は「ａ＊ｂ」と「ｃ＊ｄ」とを加算して、その結果を「ｘ」として出力する。
【０００６】
このようなデータフローグラフは、計算機（コンピュータ）上では、例えば図２３のようなデータ構造で表される。
【０００７】
図２３によると、節点はノード（Ｎｏｄｅ）構造体で表され、各節点固有の節点番号「ｎｏｄｅ＿ｉｄ」（ノードＩＤ）を持つ。また、「ｉｎ＿ｅｄｇｅ」，「ｏｕｔ＿ｅｄｇｅ」配列には入力枝と出力枝の枝番号が記憶されている。図２３の例の場合には、節点は２入力１出力の演算であり、「ｉｎ＿ｅｄｇｅ」は二つの要素、「ｏｕｔ＿ｅｄｇｅ」は一つの要素を持つ。
【０００８】
また、「ｏｐ＿ｔｙｐｅ」には加算・減算・乗算などの演算の種類を表す番号が記憶されている。
【０００９】
さらに、「ｓｃｈｅｄｕｌｉｎｇ」には、その節点のスケジューリング結果が格納されている。必要に応じて、スケジューリング結果を得るために必要な中間データなどを格納する領域もＮｏｄｅ構造体に準備する。
【００１０】
枝はＥｄｇｅ構造体で表され、各枝固有の枝番号「ｅｄｇｅ＿ｉｄ」を持つ。また、「ｆｒｏｍ＿ｎｏｄｅ」，「ｔｏ＿ｎｏｄｅ」には、その枝が接続された節点の節点番号が格納されている。これらのデータ構造により、計算機上のメモリ上にデータフローグラフの各節点とそれらの間の接続が記憶されている。「ｅｄｇｅ＿ｔｙｐｅ」には、枝の種類が格納され、実際のデータを表す枝か、節点間の実行順序を表すために挿入された枝かなどを区別する。また、データフローグラフ上で、節点を接続する場合や、ある節点の入出力につながる別の節点を見つける場合は、上記データベースの各要素に節点や枝の番号を登録したり、参照したりする。
【００１１】
以下では説明をわかりやすくするため、データフローグラフを視覚的に表した図２２のような図を用いて、節点を枝で接続したり、節点の上下につながる節点を見つけたりすることにより説明する。
【００１２】
図２１の動作記述は、処理のアルゴリズムのみを記述したものであり、一部の演算には回路外部とタイミングを合わせるなどの理由で動作タイミングに関する制約が付けられる場合があるが、それ以外の演算の動作タイミングに関する情報は含まれていない。これによって、この動作記述から、クロックに同期して動作する回路を合成するためには、記述中の各演算が実行されるタイミングを決定しなければならない。この処理はスケジューリングと言われている。
【００１３】
図２４は、図２２のデータフローグラフをスケジューリングしたスケジューリング結果の一例を示す図である。
【００１４】
図２４に示すように、節点４０１，４０２，４０３は全てステップ１にスケジューリングされている。乗算器の遅延と加算器の遅延の合計がクロックサイクルよりも短い場合は、１ステップで乗算と加算を行なうことができるため、図２４のようなスケジューリングが可能である。この場合、乗算４０１と４０２が同じクロックサイクルで処理されるため、２個の乗算器と１個の加算器が必要である。
【００１５】
図２５は、図２４のスケジューリング結果から得られる回路図である。
【００１６】
図２５に示すように、ａ，ｂ，ｃ，ｄの値はそれらを保持するレジスタからの出力である。乗算器５０１，５０２によって、「ａ＊ｂ」と「ｃ＊ｄ」の値が計算され、加算器５０３によって、「ａ＊ｂ」＋「ｃ＊ｄ」の値が計算される。この値はｘの値としてレジスタ５０４に格納される。このレジスタ５０４が値を読み込むタイミングはコントローラ５０５によって制御される。
【００１７】
図２６は、図２２のデータフローグラフをスケジューリングしたスケジューリング結果の別の一例を示す図である。
【００１８】
図２６に示すように、節点６０１はステップ１に、節点６０２と６０３はステップ２にスケジューリングされている。このスケジューリングの場合には、図２１の演算を行なうのに２サイクル必要である。しかし、乗算６０１と乗算６０２は異なるクロックサイクルで実行されるため、１個の乗算器を２回使って二つの乗算を行なうことが可能である。
【００１９】
図２７は、図２６のスケジューリング結果から得られる回路図である。
【００２０】
図２７に示すように、ステップ１では、セレクタ７０１，７０２はそれぞれ左の入力「ａ」と「ｂ」をそれぞれ出力するように、コントローラが制御信号を出力する。これによって、乗算器７０３では「ａ＊ｂ」が先に計算される。このとき、コントローラはレジスタ７０４の書き込み信号を出力しており、「ａ＊ｂ」の乗算結果はレジスタ７０４に格納される。
【００２１】
次に、ステップ２では、コントローラの信号によりセレクタ７０１，７０２はそれぞれ右の入力「ｃ」と「ｄ」をそれぞれ出力する。これによって、乗算器７０３では「ｃ＊ｄ」が計算される。この値と、レジスタ７０４に蓄えられている「ａ＊ｂ」の乗算値とが加算器７０５で加算されて、「ａ＊ｂ」＋「ｃ＊ｄ」の値が出力される。その値を「ｘ」としてレジスタ７０６が格納するようにコントローラがレジスタ７０６に書き込み信号を出力する。
【００２２】
一般に、乗算器の回路規模はレジスタやセレクタよりも大きいため、乗算器が二つの図２５の回路よりも、乗算器が一つの図２７の回路の方が回路規模は小さい。しかし、図２５の方が、二つの乗算器で同時に演算処理するため高速である。このため、計算速度が必要な場合は図２５の回路、コストダウンのために回路規模を小さくする場合は図２７の回路が好ましい。
【００２３】
一般的に言うと、クロック周期が同じ場合は、図２４のようにスケジューリング結果のステップ数が少ないほど、回路は高速である。また、図２６のように、演算器が複数のステップに分散して、１ステップ内の演算器数が少なくなるほど、回路規模は小さくなる。これによって、スケジューリングの目的は、データフローグラフ中の全ての演算をできるだけ少ないステップ内に入れ、しかも、できるだけ分散させて１ステップ内の演算器数を小さくすることである。また、設計仕様によっては、演算器を増やしても処理速度を向上させたり、逆に処理速度を犠牲にして演算器を減らしたりすることもできなければならない。実際の回路の処理を表すデータフローグラフは、数百から多い場合は数万個の演算節点を含んでいる。これによって、それら全ての実行ステップを上記目的を考慮しつつ決定するのは人手では不可能であり、計算機（コンピュータ）で行なう場合も高速に処理をする工夫が必要である。
【００２４】
従来のスケジューリング技術としては特許文献１や特許文献２がある。これらの方法では、図２８のような、データフローグラフ中の各演算が各ステップにスケジューリングされる確率の表を作っている。例えば演算Ａはステップ１と２にスケジューリングされる可能性があり、ステップ３と４にはスケジューリングされないことを表している。確率の値はスケジューリングされる可能性があるステップに等分している。ここで、あるステップにおける各演算の確率を合計すると、そのステップで必要な演算器の個数の期待値が求まる。各ステップの期待値のうち最大の値が、全体として必要な演算器数の期待値である（図２８ではステップ２の１．３３個）。次に、最大期待値を与えるステップの演算器が減るように確率を変更する。変更方法は発明によって異なるが、例えば、演算Ａのステップ２の確率を０とする。その時、同時に演算Ａのステップ１の確率は１となり、さらに演算Ａとデータ依存関係がある演算の確率も変更する。この変更を繰り返すことにより、表中の全ての確率が０または１となり、各演算の実行ステップが決定される。
【００２５】
これらの方法では、確率モデルを用いて徐々にスケジューリングを決定して行くことにより、局所最適解にならないように工夫している。
【非特許文献１】“Ａ  Ｃ−ｂａｓｅｄ  Ｓｙｎｔｈｅｓｉｓ  Ｓｙｓｔｅｍ，  Ｂａｃｈ，  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎ”Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＳＰ−ＤＡＣ  ２００１，  ２００１（ＩＥＥＥ  Ｃａｔａｌｏｇ  Ｎｕｍｂｅｒ：  ０１ＥＸ４５５，  ＩＳＢＮ：  ０−７８０３−６６３３−６）
【特許文献１】特開平９−８１６０５号公報
【特許文献２】特開２０００−３４８０６９号公報
【発明の開示】
【発明が解決しようとする課題】
【００２６】
これらの従来手法では、スケジューリング結果が局所最適解になってしまうことを防ぐため、確率モデルを用いて徐々にスケジューリングを決めていくことを特徴としている。しかし、ある一部の節点のスケジューリングが一旦決定されると、それ以降はそのスケジューリングは決して変更されないため、他の節点のスケジューリングの妨げとなる可能性がある。
【００２７】
例えば図２９のようなデータフローグラフをスケジューリングする場合を考える。
【００２８】
図２９では、節点９０１〜９０６は演算を表しており、節点９０１，９０３，９０５，９０６は同一の演算種類の演算であり、その演算種類をＡとする。また、節点９０２と９０４は演算種類Ａとは異なる演算種類Ｂの演算である。各節点を区別するために、演算種類Ａの演算にはＡ１，Ａ２，Ａ３，Ａ４、演算種類Ｂの演算にはＢ１，Ｂ２と記号をつけている。
【００２９】
演算種類Ａ，Ｂは例えば論理否定や負号などの１入力１出力の演算である。それぞれの遅延はクロックサイクルより少し小さい値で、１クロックサイクルでは１演算しかできないものとする。
【００３０】
図３０では、節点１００１で表された点線で示す演算Ａ３よりも先に、節点１００２で表された演算Ａ４がスケジューリングされている状態を示しており、演算Ａ４はステップ２にスケジューリングされている。まだスケジューリングされていない点線で示す演算Ａ３のスケジューリングを行わなければならないが、演算Ａ３はステップ２の演算Ａ４が障害となってステップ１にしかスケジューリングすることができない。しかし、ステップ１には演算Ａ１が存在するため、演算Ａ３をステップ１にスケジューリングすると演算器Ａは２個必要になってしまう。
【００３１】
即ち、従来手法では、一旦、図３０のようになってしまうと図３１のような最適なスケジューリング結果を得ることはできなくなってしまい、回路規模が増大してしまう。よって、図３１のような演算器Ａを１個しか必要としない最適解を得るには、図３０のように先にスケジューリングした節点が後からスケジューリングする節点の障害になってしまわないようにするための何らかの工夫が必要である。
【００３２】
また、これらの従来手法では、演算を各ステップに割り付ける確率の表を作っているため、予めステップ数を決めねばならない。例えば、図２２のデータフローグラフで乗算器を１個しか用いないでスケジューリングを行う場合、スケジューリングの前にステップ数が「２」となることを予見しなければ図２６の結果を得ることはできない。しかし、スケジューリング前にスケジューリング結果を予見するのは非常に困難である。
【００３３】
さらに、これらの従来手法では、確率モデルを用いてスケジューリングを徐々に決めていくが、全演算の実行ステップを決定するために、演算の個数と予め決めたステップ数の積の個数の確率値を決定せねばならないため、計算時間が長くなるという問題もある。
【００３４】
本発明は、上記従来の問題を解決するもので、できるだけ短時間で最適なスケジューリング解を求めることができる高位合成装置、スケジューリング方法、スケジューリングプログラムおよび可読記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００３５】
本発明の高位合成装置は、回路動作が表現された動作記述を用いて、演算処理部を示す節点とデータの流れを示す枝により生成されたコントロールデータフローグラフ中の各演算処理を実行する実行ステップをスケジューリング手段でそれぞれ決定して、レジスタトランスファレベルの設計回路を自動合成する高位合成装置において、該スケジューリング手段は、該コントロールデータフローグラフ中で同一種類の複数の演算処理部が同一実行ステップで実行される可能性がある場合に、該複数の演算処理部のうち二つの演算処理部を表す節点間に枝を挿入して該節点間の前後関係を決定し、該枝が挿入されたコントロールデータフローグラフの自由度を用いて該コントロールデータフローグラフの評価値を求める評価値算出手段と、該評価値が最も大きいコントロールデータフローグラフを選択して、該複数の演算処理部に対応した実行ステップをそれぞれ決定する実行ステップ決定手段とを有するものであり、そのことにより上記目的が達成される。
【００３６】
また、好ましくは、本発明の高位合成装置における評価値算出手段は、前記枝を挿入する二つの節点の順列が複数ある場合は、該節点間の前後関係を決定するときに、該枝を挿入する二つの節点の順列を所定の評価関数を用いて決定する。
【００３７】
さらに、好ましくは、本発明の高位合成装置における評価関数は、前記前後関係を与えた後のコントロールデータフローグラフ中の各演算処理部のスケジューリング可能な実行ステップの個数を用いて評価値を求める。
【００３８】
さらに、好ましくは、本発明の高位合成装置における実行ステップ決定手段は、前記コントロールデータフローグラフの実行ステップ数が、最小の実行ステップ数かまたは、与えられた実行ステップ数を越えない範囲で、できるだけ演算器を減らす場合には、二つの演算処理部間に前後関係を与えたときに実行ステップ数が延びないコントロールデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択する。
【００３９】
さらに、好ましくは、本発明の高位合成装置における実行ステップ決定手段は、与えられた演算器数を越えない範囲で、できるだけコントロールデータフローグラフの実行ステップ数を減らす場合には、二つの演算処理部間に前後関係を与えたときに該実行ステップ数が延びないコントロールデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択し、仮に、該実行ステップ数が延びないコントロールデータフローグラフがないなら、該実行ステップ数が延びるデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択する。
【００４０】
さらに、好ましくは、本発明の高位合成装置におけるスケジューリング手段は、各演算処理をできるだけ早く実行する第１スケジューリングと該各演算処理をできるだけ遅く実行する第２スケジューリングとに基づいて、各実行ステップにスケジューリングされる可能性がある各演算処理部の割付表を作成する割付表作成手段と、該割付表に基づいて、最多の演算処理部が割り付けられる可能性のある実行ステップに含まれる複数の演算処理部から二つの演算処理部を選ぶ順列を抽出する順列抽出手段とを更に有し、前記評価値算出手段は、抽出された各演算処理部の順列から一つを選び、選んだ二つの演算処理部間に、実行順序を決定する枝を挿入し、該枝が挿入されたコントロールデータフローグラフの自由度を用いて該コントロールデータフローグラフの評価値を求める評価値算出処理を全順列について実行し、前記実行ステップ決定手段は、該評価値が最も高い順列の組合せを選択することにより、前記複数の演算処理に対応した実行ステップをそれぞれ決定する。
【００４１】
さらに、好ましくは、本発明の高位合成装置におけるスケジューリング手段は、最小の実行ステップ数か、または、ある与えられた実行ステップ数を越えないようにする場合に、前記実行ステップ決定手段で選んだ評価値が正のときは前記割付表作成手段で割付表を再度作成して、前記順列抽出手段、評価値算出手段および実行ステップ決定手段による各処理を繰り返し、または、該評価値が正以外のときは演算終了判定を行う演算終了判定手段を更に有する。
【００４２】
さらに、好ましくは、本発明の高位合成装置におけるスケジューリング手段は、演算器数を上限個数以下にする場合に、実行ステップで演算処理部数が演算器数の上限個数よりも大きいときは前記割付表作成手段で割付表を再度作成して、前記順列抽出手段、評価値算出手段および実行ステップ決定手段による各処理を繰り返し、または、該全ての実行ステップで演算処理部数が演算器数の上限個数よりも小さいか同じときは演算終了判定を行う演算終了判定手段を更に有する。
【００４３】
さらに、好ましくは、本発明の高位合成装置におけるスケジューリング手段は、前記割付表作成手段の前段に、占有面積が大きい演算器で実行する演算処理の種類から先に、該演算処理の種類を決定する演算種類決定手段を更に有し、前記演算終了判定手段の後段に、全演算種類が終了したかどうかを判定する全演算種類終了判定手段を更に有して、該全演算種類が終了していない場合には該演算種類決定手段により該演算処理の種類を決定して、前記割付表作成手段、順列抽出手段、評価値算出手段、実行ステップ決定手段、演算終了判定手段および全演算種類終了判定手段による各処理を繰り返す。
【００４４】
本発明のスケジューリング方法は、回路動作が表現された動作記述を用いて、演算処理を示す節点とデータの流れを示す枝により生成されたコントロールデータフローグラフ中の各演算処理を実行する実行ステップを決定するスケジューリング方法において、該コントロールデータフローグラフ中で同一種類の複数の演算処理部が同一実行ステップで実行される可能性がある場合に、該複数の演算処理部のうち二つの演算処理部を表す節点間に枝を挿入して該節点間の前後関係を決定し、該枝が挿入されたコントロールデータフローグラフの自由度を用いて該コントロールデータフローグラフの評価値を求める評価値算出処理手順と、該評価値が最も大きいコントロールデータフローグラフを選択して、該複数の演算処理部に対応した実行ステップをそれぞれ決定する実行ステップ決定処理手順とを有するものであり、そのことにより上記目的が達成される。
【００４５】
また、好ましくは、本発明のスケジューリング方法において、評価値算出処理手順は、前記枝を挿入する二つの節点の組合せが複数ある場合は、該節点間の前後関係を決定するときに、該枝を挿入する二つの節点の順列を評価関数を用いて決定する。
【００４６】
さらに、好ましくは、本発明のスケジューリング方法における評価関数は、前記前後関係を与えた後のコントロールデータフローグラフ中の各演算処理部のスケジューリング可能な実行ステップの個数を用いて評価値を求める。
【００４７】
さらに、好ましくは、本発明のスケジューリング方法において、実行ステップ決定処理手順は、コントロールデータフローグラフの実行ステップ数が、最小の実行ステップ数か、または、与えられた実行ステップ数を越えない範囲で、できるだけ演算器を減らす場合には、二つの演算処理部間に前後関係を与えたときに実行ステップ数が延びないコントロールデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択する。
【００４８】
さらに、好ましくは、本発明のスケジューリング方法において、実行ステップ決定処理手順は、与えられた演算器数を越えない範囲で、できるだけコントロールデータフローグラフの実行ステップ数を減らす場合には、二つの演算処理部間に前後関係を与えた時に該実行ステップ数が延びないコントロールデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択し、仮に、該実行ステップ数が延びないコントロールデータフローグラフがないなら、該実行ステップ数が延びるデータフローグラフの中から、前記評価値が最大であるコントロールデータフローグラフを選択する。
【００４９】
さらに、好ましくは、本発明のスケジューリング方法において、各演算処理をできるだけ早く実行する第１スケジューリングと該各演算処理をできるだけ遅く実行する第２スケジューリングとに基づいて、各実行ステップにスケジューリングされる可能性がある各演算処理部の割付表を作成する割付表作成処理手順と、該割付表に基づいて、最多の演算処理部が割り付けられる可能性のある実行ステップに含まれる複数の演算処理部から二つの演算処理部を選ぶ順列を抽出する順列抽出処理手順とを更に有し、前記評価値算出処理手順は、抽出された各演算処理部の順列から一つを選び、選んだ二つの演算処理部間に、実行順序を決定する枝を挿入し、該枝が挿入されたコントロールデータフローグラフの自由度を用いて該コントロールデータフローグラフの評価値を求める評価値算出処理を全順列について実行し、前記実行ステップ決定処理手順は、該評価値が最も高い順列の組合せを選択することにより、前記複数の演算処理に対応した実行ステップをそれぞれ決定する。
【００５０】
さらに、好ましくは、本発明のスケジューリング方法において、最小の実行ステップ数か、または、ある与えられた実行ステップ数を越えないようにする場合に、前記実行ステップ決定処理手順で選んだ評価値が正のときは前記割付表作成処理手順で割付表を再度作成して、前記順列抽出処理手順、評価値算出処理手順および実行ステップ決定処理手順による各処理を繰り返し、または、該評価値が正以外のときは演算終了判定を行う演算終了判定処理手順を更に有する。
【００５１】
さらに、好ましくは、本発明のスケジューリング方法において、演算器数を上限個数以下にする場合に、実行ステップで演算処理部数が演算器数の上限個数よりも大きいときは前記割付表作成処理手順で割付表を再度作成して、前記順列抽出処理手順、評価値算出処理手順および実行ステップ決定処理手順による各処理を繰り返し、または、該全ての実行ステップで演算処理部数が演算器数の上限個数よりも小さいか同じときは演算終了判定を行う演算終了判定処理手順を更に有する。
【００５２】
さらに、好ましくは、本発明のスケジューリング方法において、割付表作成処理手順の前段に、占有面積が大きい演算器で実行する演算処理の種類から先に、該演算処理の種類を決定する演算種類決定処理手順を更に有し、前記演算終了判定処理手順の後段に、全演算種類が終了したかどうかを判定する全演算種類終了判定処理手順を更に有して、該全演算種類が終了していない場合には該演算種類決定処理手順により該演算処理の種類を決定して、前記割付表作成処理手順、順列抽出処理手順、評価値算出処理手順、実行ステップ決定処理手順、演算終了判定処理手順および全演算種類終了判定処理手順による各処理を繰り返す。
【００５３】
本発明のスケジューリングプログラムは、上記スケジューリング方法における各処理手順をコンピュータに実行させるためのものであり、そのことにより上記目的が達成される。
【００５４】
本発明の可読記録媒体は、上記スケジューリングプログラムを記録したコンピュータ読み取り可能なものであり、そのことにより上記目的が達成される。
【００５５】
上記構成により、以下、本発明の作用を説明する。
【００５６】
本発明においては、コントロールデータフローグラフ中で同一種類の複数の演算処理が同一実行ステップで実行される可能性がある場合に、それらの演算処理部間に前後関係を与えることにより各演算処理部に対応した実行ステップをそれぞれ決定することが可能となる。
【００５７】
このように、コントロールデータフローグラフ中の演算処理部間の相対的な順序が決定され、各演算処理部に対応した実行ステップは可変である。このため、先に任意の演算処理部に対してスケジューリング処理を行なったとしても、その演算処理部が後から他の演算処理部のスケジューリング処理を行なうときの妨げとならず、局所解に陥る可能性が少なくなる。これにより、実行ステップ数が短く、使用する演算器の個数が少ない最適なスケジューリング結果が得られる。
【００５８】
また、スケジューリングアルゴリズムの終了判定の方法を変えるだけで、実行ステップ数を最小化したスケジューリング結果や、演算器数を指定した個数以下にしたスケジューリング結果が得られる。よって、高速に動作する回路が必要な場合は前者、回路規模を小さくしてコストを削減したい場合は後者を、必要に応じて選択することが可能となる。
【００５９】
さらに、演算処理部間の順序を一意的に決めていくため、スケジューリング処理が早く終り、設計期間を短縮することが可能となる。
【発明の効果】
【００６０】
以上により、本発明のよれば、コントロールデータフローグラフ中で同一種類の複数の演算処理が同一実行ステップで実行される可能性がある場合に、それらの演算処理部間に前後関係を与えることにより各演算処理部に対応した実行ステップをそれぞれ決定することが可能となる。これによって、できるだけ短時間で最適なスケジューリング解を求めることができる。
【発明を実施するための最良の形態】
【００６１】
以下に、本発明の高位合成装置およびこれを用いたスケジューリング方法の実施形態について図面を参照しながら説明する。なお、ここでは、本実施形態の高位合成装置の全体構成について簡単に説明した後に、これに用いられる本発明の特徴構成であるスケジューリング手段およびスケジューリング方法について詳細に説明する。
【００６２】
図１は、本発明の高位合成装置の一実施形態における要部構成例を示すブロック図である。
【００６３】
図１において、高位合成装置１０は、コンピュータシステムにより構成されており、各部を制御して制御プログラム（スケジューリングプログラムを含む）を実行する制御部１１と、制御プログラムおよびそのデータなどが記録されるハードディスクなどの可読記録媒体としてのＲＯＭ１２と、制御部１１の制御時にワークメモリとして働くＲＡＭ１３と、回路設計に必要な各種データが記録されていると共に、コントローラ情報やデータパス情報など各種生成結果情報を記憶可能とするデータベース１４と、ユーザによる操作指令入力を可能とする操作部１５と、各種画像表示が為される表示部１６とを有し、回路動作が表現された動作記述を解析し、この解析された動作記述から、演算処理を示す節点とデータの流れを示す入出力枝により生成されたコントロールデータフローグラフ中の各演算を実行するステップをスケジューリング手段により決定して、ＲＴＬ（レジスタトランスファレベル）の所望のハードウェア（設計回路図）を自動合成（自動回路設計）する。この場合、ＲＯＭ１２には、ＦＤやＣＤ（光ディスク）などの別の可読記録媒体から制御プログラムおよびそのデータがインストールされ得る。
【００６４】
制御部１１は、ＣＰＵ（中央演算処理装置）で構成されており、制御プログラムに基づいて、構文解析・字句解析部１１１と、ブロック分割部１１２と、ＣＤＦＧ（コントロールデータフローグラフ）生成部１１３と、コントロールデータフローグラフ中の各演算を実行するステップを決定するスケジューリング手段としてのスケジューリング部１１４と、演算器・レジスタの割り当て部１１５と、データパス生成部１１６と、コントローラ生成部１１７と、ＲＴＬ記述自動生成部１１８との各種機能部による各処理手順を順次実行するようになっている。
【００６５】
上記構成により、まず、回路の動作記述格納部（データベース１４の一部）からの動作記述は、構文解析・字句解析部１１１によって解析された後、ブロック分割部１１２で、動作記述に従って、回路がブロック分割される。その後、ＣＤＦＧ生成部１１３では、分割された各ブロックにおいて、各種演算を示す各節点とデータの流れを示す入出力枝などからなるコントロールデータフローグラフ（ＣＤＦＧ）が作成される。さらに、スケジューリング部１１４によって、ＣＤＦＧの各ノードについて、各演算を実行するステップを決定するスケジューリングが行われる。演算器・レジスタの割り当て部１１５で、スケジューリングされた各ノードについて、演算器やレジスタなどのハードウェア部品が割り当てられて、各コンポーネントについての動作情報が作成される。
【００６６】
次に、データパス生成部１１６では、演算器・レジスタの割り当て部１１５でハードウェア部品にアロケーション（割り当て）された各演算器やレジスタの接続関係から、回路のデータパス情報が作成される。さらに、コントローラ生成部１１７では、各ブロックのコントローラ回路が生成され、コントローラ回路の状態遷移を含むコントローラ情報が作成される。
【００６７】
以上の各種情報に基づいて、ＲＴＬ記述自動生成部１１８で、レジスタトランスファレベルの所望の設計回路図を自動合成する。
【００６８】
ここで、本発明の特徴構成であるスケジューリング部１１４の詳細構成例について説明する。
【００６９】
図２は、図１のスケジューリング部１１４の詳細構成例を示すブロック図である。
【００７０】
図２において、制御部１１のスケジューリング部１１４は、ＲＯＭ１２内のスケジューリングプログラムおよびそのデータに基づいて、占有面積が大きい演算器で実行する演算処理の種類から先に、該演算処理の種類を決定する演算種類決定手段１１４Ａと、この決定された演算処理の種類に対して、各演算処理をできるだけ早く実行する第１スケジューリングと各演算処理をできるだけ遅く実行する第２スケジューリングとに基づいて、各実行ステップにスケジューリングされる可能性がある各演算処理部の割付表を作成する割付表作成手段１１４Ｂと、この割付表に基づいて、最多の演算処理部が割り付けられる可能性のある実行ステップに含まれる複数の演算処理部から二つの演算処理部を選ぶ順列を抽出する順列抽出手段１１４Ｃと、抽出された各演算処理部の順列から一つを選び、選んだ二つの演算処理部間に、実行順序を決定する枝を挿入し、この枝が挿入されたコントロールデータフローグラフの自由度を用いてコントロールデータフローグラフの評価値を求める評価値算出処理を全順列の組合せについて実行する評価値算出手段１１４Ｄと、評価値が最も高い順列の組合せを選択することにより、複数の演算処理に対応した実行ステップをそれぞれ決定する実行ステップ決定手段１１４Ｅと、最小の実行ステップ数か、または、ある与えられた実行ステップ数を越えないようにする場合に、実行ステップ決定手段で選んだ評価値が正のときは割付表作成手段１１４Ｂで割付表を再度作成して、順列抽出手段１１４Ｃ、評価値算出手段１１４Ｄおよび実行ステップ決定手段１１４Ｅによる各処理を繰り返し、または、評価値が正以外のときは演算終了判定を行う演算終了判定手段１１４Ｆまたは、演算器数を上限個数以下にする場合に、実行ステップで演算処理部数が演算器数の上限個数よりも大きいときは割付表作成手段１１４Ｂで割付表を再度作成して、順列抽出手段１１４Ｃ、評価値算出手段１１４Ｄおよび実行ステップ決定手段１１４Ｅによる各処理を繰り返し、または、全ての実行ステップで演算処理部数が演算器数の上限個数よりも小さいか同じときは演算終了判定を行う演算終了判定手段１１４Ｆと、全演算種類が終了したかどうかを判定し、全演算種類が終了していない場合には演算種類決定手段１１４Ａにより演算処理の種類を決定して、割付表作成手段１１４Ｂ、順列抽出手段１１４Ｃ、評価値算出手段１１４Ｄ、実行ステップ決定手段１１４Ｅ、演算終了判定手段１１４Ｆおよび全演算種類終了判定手段１１４Ｇによる各処理を繰り返す全演算種類終了判定手段１１４Ｇとの各種機能を実行するようになっている。
【００７１】
このように、スケジューリング部１１４は、コントロールデータフローグラフ中で同一種類の複数の演算処理が同一実行ステップで実行される可能性がある場合に、複数の演算処理のうち二つの演算処理を表す節点間に枝を挿入して節点間の前後関係を決定し、枝を挿入する二つの節点の順列を所定の評価関数を用いて決定することにより、複数の演算処理に対応した実行ステップをそれぞれ決定するスケジューリングを行う。
【００７２】
この評価関数としては、前後関係を与えた後のコントロールデータフローグラフ中の各演算処理のスケジューリング可能な実行ステップの個数を用いて評価値を求める。
【００７３】
コントロールデータフローグラフの実行ステップ数が、最小の実行ステップ数かまたは、与えられた実行ステップ数を越えない範囲で、できるだけ演算器を減らす場合には、二つの演算処理間に前後関係を与えたときに実行ステップ数が延びないコントロールデータフログラフの中から、評価値が最大であるコントロールデータフローグラフを選択する。
【００７４】
または、与えられた演算器数を越えない範囲で、できるだけコントロールデータフローグラフの実行ステップ数を減らす場合には、二つの演算処理間に前後関係を与えたときに実行ステップ数が延びないコントロールデータフローグラフの中から、評価値が最大であるコントロールデータフローグラフを選択し、仮に、実行ステップ数が延びないコントロールデータフローグラフがないなら、実効ステップ数が延びるデータフローグラフの中から、評価値が最大であるコントロールデータフローグラフを選択する。
【００７５】
上記構成により、図１のスケジューリング部１１４によるスケジューリング方法について詳細に説明する。
【００７６】
図３は、本発明のスケジューリング方法における各処理手順の一例を示すフローチャートである。
【００７７】
図３に示すように、最初に、ステップＳ１１で演算の種類を決める。本スケジューリング手法では、アルゴリズムを演算の種類毎に適用していく。また、演算間の順序を決めていくことでスケジューリングを決定するため、スケジューリング処理の初期が最も自由度が高く、演算器数を減らしやすい。よって、占有面積が大きい演算器で実行する演算種類から順番にアルゴリズムを適用するのがよく、本ステップではまだアルゴリズムを適用されていない中で最も占有面積が大きい演算を選択する。ただし、データフローグラフ中に１個しか演算がない演算種類については順番を決める必要がないため選択しない。例えば図２９のデータフローグラフは「Ａ」と「Ｂ」、二つの演算の種類を含む。演算の種類「Ａ」と「Ｂ」共に演算は２個以上であり、選択の対象となる。ここでは演算種類「Ａ」を実行する演算器の占有面積の方が、演算の種類「Ｂ」を実行する演算器の占有面積よりも大きいものとすると、本ステップでは演算の種類として「Ａ」が選ばれる。
【００７８】
次に、ステップＳ１２で割り付け表を作成する。この割り付け表は、各ステップについて、そのステップにスケジューリングされる可能性がある複数の節点（演算）が対応する。各ステップにスケジューリングされる可能性がある節点は、第１スケジューリングとしてのデータフローグラフのＡＳＡＰ（Ａｓ  Ｓｏｏｎ  Ａｓ  Ｐｏｓｓｉｂｌｅ）スケジューリング結果と、第２スケジューリングとしてのデータフローグラフのＡＬＡＰ（Ａｓ  Ｌａｔｅ  Ａｓ  Ｐｏｓｓｉｂｌｅ）スケジューリング結果とから求まる。ＡＳＡＰスケジューリングは各節点をできるだけ早く実行するスケジューリングであり、各節点を上詰めで置くことで求まる。ＡＬＡＰスケジューリングは各節点をできるだけ遅く実行するスケジューリングであり、各節点を下詰めで置くことで求まる。各節点は、その節点のＡＳＡＰスケジューリング結果か、ＡＬＡＰスケジューリング結果か、またはその間のいずれかのステップにスケジューリングされ得る。
【００７９】
図２９のデータフローグラフを別の一例として説明する。図４は図２９のＡＳＡＰスケジューリング結果である。図５は図２９のＡＬＡＰスケジューリング結果である。これによると、節点Ａ１，Ａ２はＡＳＡＰスケジューリングとＡＬＡＰスケジューリングが一致している。よって、これらの節点はそのステップにしか置くことができないとわかる。これに対して、節点Ａ３はＡＳＡＰスケジューリングではステップ１、ＡＬＡＰスケジューリングではステップ３にスケジューリングされている。よって、節点Ａ３は、ステップ１、ステップ２またはステップ３にスケジューリングすることが可能であることがわかる。これと同様に節点Ａ４は、ステップ２、ステップ３またはステップ４にスケジューリング可能である。これにより、ステップ１に配置される可能性がある節点はＡ１とＡ３であることがわかる。ステップ２には節点Ａ３とＡ４、ステップ３には節点Ａ２とＡ３とＡ４、ステップ４には節点Ａ４である。これを表にしたのが図６の各節点の割り付け表である。
【００８０】
図４のＡＳＡＰスケジューリング結果と、図５のＡＬＡＰスケジューリング結果とのステップ数は必ず一致し、それは、そのデータフローグラフを実行する時の最小ステップ数である。最小ステップ数よりも大きいステップ数になるようにスケジューリングする場合、例えば、図２９のデータフローグラフを５ステップで実行する場合には、ＡＳＡＰスケジューリングは、図４のＡＳＡＰスケジューリングの４ステップ目の次に空の５ステップ目が追加されることになる。ＡＬＡＰスケジューリングは、図５の１ステップから４ステップがそれぞれ、２ステップから５ステップになり、１ステップ目に空のステップが追加されることになる。本実施形態では、ステップ数を最小化する場合（図４と図５）について説明する。
【００８１】
次に、図３のステップＳ１３で各節点（各演算）の組合せ抽出を行う。図６の割り付け表において、最も多数の演算が割り付けられる可能性のあるステップを見つける。もし、最多の演算が割り付けられる可能性のあるステップが複数の場合はランダムに一つのステップを選択するか、または、最初に見つかったステップを選択するなどの方法で一つのステップを選ぶ。図６の場合には、ステップ３に三つの演算が割り付けられる可能性があり、ステップ３が最も多い。選んだステップに含まれる演算から二つの演算を選ぶ順列を列挙する。例えば図６のステップ３には、三つの演算種類の節点Ａ２，Ａ３，Ａ４が含まれるので、それらから二つの演算を選ぶ順列は、（Ａ２，Ａ３），  （Ａ３，Ａ２），  （Ａ２，Ａ４），  （Ａ４，Ａ２），  （Ａ３，Ａ４），  （Ａ４，Ａ３）の６通りである。なお、最多の演算が割り付けられる可能性のあるステップを複数選び、各ステップから求まる演算の順列を列挙してもよい。
【００８２】
さらに、図３のステップＳ１４において、ステップＳ１３で選んだ演算（節点）の組合せから一つを選び、ステップＳ１５の仮枝挿入、さらにステップＳ１６の評価の各処理を順次適用する。これらを全組合せについて実施する。
【００８３】
ステップＳ１５では、ステップＳ１４で選んだ二つの演算の間に仮枝を挿入する。既に別の仮枝が挿入されている場合は、その仮枝は削除する。仮枝は二つの演算の実行順序を決定する有向枝であり、仮枝の終点の演算は必ず仮枝の始点の演算よりも後のステップで実行されるものとする。
【００８４】
図７は、図６から例えば（Ａ３，Ａ２）の組合せを選び、節点Ａ３から節点Ａ２へ仮枝（有向枝）を挿入した場合のデータフローグラフである。
【００８５】
図７に示すように、仮枝は、点線の矢印１６０１で示している。この場合、節点Ａ３よりも節点Ａ２の方が後で実行されなければならないため、節点Ａ３はステップ１かまたはステップ２にしか置くことができなくなる。
【００８６】
ステップＳ１６では、仮枝を挿入したデータフローグラフの自由度を求めることによりデータフローグラフを評価する。自由度は次の式で求めることができる。
【００８７】
Σ  （ＡＬＡＰ（ｎ）  −  ＡＳＡＰ（ｎ））
ここで、ＡＳＡＰ（ｎ）は節点ｎをＡＳＡＰスケジューリングしたときの実行ステップ、ＡＬＡＰ（ｎ）は同様にＡＬＡＰスケジューリングしたときの実行ステップである。よって、これらの差、ＡＬＡＰ（ｎ）  −  ＡＳＡＰ（ｎ）  の値は、節点ｎを置くことができる実行ステップの個数から１を減じたものとなる。ｎはデータフローグラフ中の全節点であり、ステップＳ１１で選んだ節点種類以外の節点も含む。演算器の面積の影響を考慮して、次の式のように面積を乗じてもよい。ＡＲＥＡ（ｎ）は演算ｎを実行する演算器の面積である。
【００８８】
Σ  （（ＡＬＡＰ（ｎ）  −  ＡＳＡＰ（ｎ））  ＊  ＡＲＥＡ（ｎ））
以降の説明では、演算器の面積を乗じない式を用いることとする。図７の場合、節点Ａ１，Ａ２，Ｂ１，Ｂ２はＡＳＡＰスケジューリングとＡＬＡＰスケジューリングとが一致しており、１箇所にしかスケジューリングできない。よって、演算の節点Ａ１，Ａ２，Ｂ１，Ｂ２の自由度は「０」である。また、節点Ａ３のＡＳＡＰスケジューリングはステップ１、ＡＬＡＰスケジューリングはステップ２であり、節点Ａ３はステップ１とステップ２にスケジューリング可能である。よって、Ａ３の自由度は２−１＝１である。節点Ａ４はステップ２からステップ４にスケジューリング可能であり、自由度は４−２＝２である。よって、この場合の自由度は図８（ａ）のように１＋２＝３である。
【００８９】
一方、図８（ｂ）のように、節点Ａ４から節点Ａ２へ仮枝が挿入されている場合は、全ての演算のＡＳＡＰスケジューリングとＡＬＡＰスケジューリングは同じであるので、自由度は「０」となる。
【００９０】
図８（ｃ）のように、節点Ａ２から節点Ａ４へ仮枝が挿入されている場合は、節点Ａ３がステップ１からステップ３にスケジューリング可能で、それ以外の演算は固定されているため、全体の自由度は「２」である。
【００９１】
このように、自由度が大きいほど、仮枝挿入後のデータフローグラフから実現可能なスケジューリング結果はたくさんあるため、その中に良い結果がある可能性が高い。よって、自由度をその仮枝挿入の評価値とする。この評価値（自由度）が大きいほどよい。もし仮に、仮枝挿入によってステップ数が増加してしまう場合には、ペナルティとして例えば１００を評価値から減じる。ペナルティの値を十分大きい数とすることにより、ステップ数が延びない場合は評価値が正となり、ステップ数が延びる場合は評価値が負となる。これにより、不必要にステップ数が延びることを防ぐことができる。即ち、ステップ数が延びる選択肢しかなく、しかも、ステップ数を延ばしても演算器数を優先して削減しようとする場合にのみ、負の評価値の結果が選択される。
【００９２】
図８（ｄ）では、節点Ｂ２がステップ４とステップ５にスケジューリング可能であるため自由度は「１」であるが、ステップ数が延びてしまうため、評価値は１−１００＝−９９となる。図８（ａ）から図８（ｃ）では、ステップ数が延びないため評価値は自由度と同じ値である。
【００９３】
節点Ａ３から節点Ａ４に仮枝を挿入する場合については、節点Ａ３と節点Ａ４には元々必ずステップをまたぐ枝がついているので、仮枝を挿入してもデータフローグラフが変化しない。よって、この場合は評価する必要がない。もし、節点Ａ３と節点Ａ４の遅延の和がクロックサイクルよりも小さく、１クロックで節点Ａ３と節点Ａ４を実行できる場合は、節点Ａ３と節点Ａ４の間の枝はステップを跨がない場合があり得るので、ステップを必ず跨る仮枝とは性質が異なる。よって、この場合は、評価せねばならない。節点Ａ４から節点Ａ３に仮枝を挿入する場合は、元々ある節点Ａ３から節点Ａ４の枝と仮枝によってループができてしまう。このときは、節点Ａ３と節点Ａ４の順序が決定できなくなり、スケジューリングができななる。よって、この場合も評価しない。
【００９４】
ステップＳ１７では、ステップＳ１３で列挙した全ての組合せについてステップＳ１５とステップＳ１６の各処理を実行していれば（ｙｅｓ；全組み合せ完了の場合）、次のステップＳ１８の処理に進み、まだ実行していなければ（ｎｏ；全組み合せ完了していない場合）、ステップＳ１４〜Ｓ１６の各処理を順次繰り返す。なお、図８（ａ）〜図８（ｄ）は、ステップＳ１６で全ての評価をせねばならない組合せの評価値を求めた結果である。
【００９５】
ステップＳ１８では、評価値が最も高い組合せを見つける。図８（ａ）〜図８（ｄ）の場合には、評価値が最も高いのは図８（ａ）の節点Ａ３から節点Ａ２へ仮枝を入れた場合である。
【００９６】
ステップＳ１９では、一つの演算処理部に関するスケジューリング処理が終了したかどうかを判定する。この終了判定は次の条件で行う。
【００９７】
即ち、ステップＳ１１で選んだ演算種類の演算器数に上限がなく、ステップ数を最小のステップ数か、または、ある与えられたステップ数を越えないようにする場合、ステップＳ１８で選んだ順列の評価値が正の場合は終了しておらず、評価値が負または評価された選択肢がない場合は終了している。評価値が負の場合は、ステップ数が延びない仮枝の入れ方が存在しないためである。
【００９８】
また、ステップＳ１１で選んだ演算種類の演算器数をある与えられた個数以下にする場合、即ち、ステップ数を延ばしてもよいが演算器数を限定する場合、ステップＳ１３で選んだ実行ステップの演算数が演算器数の上限よりも小さいか同じ時は終了している。演算器の上限より多い演算器は使われないためである。また、ステップＳ１３で選んだ実行ステップの演算数が演算器数の上限よりも大きい場合は終了していない。この場合は、評価値が負の場合も採用され、全てのステップで演算数が演算器数の上限よりも小さいか同じになるまでステップ数が延長されることになる。
【００９９】
ステップＳ１９で全演算が終了ではない場合（ｎｏ）はステップＳ２０の処理に進み、全演算が終了の場合（ｙｅｓ）はステップＳ２１の処理に進む。
【０１００】
ステップＳ２０では、ステップＳ１８で得た最大評価値のデータフローグラフ中の仮枝を本枝に変更する。本枝は仮枝と同じ機能を果たし、仮枝が評価毎に削除されるのに対して、本枝は削除されない。
【０１０１】
その後、ステップＳ１２の処理に戻る。図８（ａ）の仮枝を本枝とした場合、ステップＳ１２で再度作られる割り付け表は図９のようになる。これと図６との各表を比較すると、新たに挿入された本枝によって、節点Ａ３がステップ３にはスケジュールされなくなっている点が異なっている。これを見ると、各ステップに割り付けられる最大演算数は２個になっており、節点Ａ３と節点Ａ４をどこにスケジューリングしたとしても最大２個の演算器で済む。図６では最大３個の演算器が必要であったので、これで演算器数が一つ減少したことになる。
【０１０２】
さらに、ステップＳ１２〜Ｓ２０の各処理を再度繰り返す。図９にステップＳ１３を適用する場合、ステップ１とステップ２とステップ３で最大演算数は同じく「２」である。ここでは、ステップ１を選ぶものとすると、仮枝を挿入する組合せは、（Ａ１，Ａ３）と（Ａ３，Ａ１）である。各組合せを評価すると、図１０（ａ）および図１０（ｂ）のようになる。
【０１０３】
図１０（ａ）中の実線の矢印１９０１は、ステップＳ２０で入れた本枝を表す。図１０（ａ）と図１０（ｂ）は共に、節点Ａ３から節点Ａ２へ本枝が挿入されているが、図１０（ａ）では、節点Ａ３はステップ２、節点Ａ２はステップ３に置かれており、図１０（ｂ）では、節点Ａ３はステップ１、節点Ａ２はステップ４に置かれている。このように、本枝は演算の順序のみを決定して、演算の実行ステップは固定しない。これにより、より多様な可能性を試すことが可能となり、局所解に陥りにくくなる。ステップＳ１８では、同様に評価値の高い図１０（ａ）を選ぶ。
【０１０４】
さらに、ステップＳ１２〜Ｓ２０の各処理を再度繰り返す。ステップＳ１２では図１１の表が得られる。ステップＳ１３で、最も演算数が多いステップ３を選ぶと、図１２（ａ）および図１２（ｂ）の評価結果となり、評価値の高い図１２（ａ）を選ぶ。
【０１０５】
さらに、ステップＳ１２〜Ｓ２０の各処理を再度繰り返す。ステップＳ１２では図１３の割り付け表が得られる。これにより、演算器の最大数は「１」となり、１個の演算器で節点Ａ１，Ａ２，Ａ３，Ａ４の全ての処理を行なえることになる。ステップＳ１４では組合せが存在しなくなり、ステップＳ１８で評価される組合せはない。よって、ステップＳ１９の全演算の終了判定で全演算終了（全演算完了）が選ばれて、ステップＳ２１の仮枝削除処理に移行する。
【０１０６】
ステップＳ２１では、終了条件判定前の評価で挿入された仮枝が残っているならば、それを削除する仮枝削除処理が為される。
【０１０７】
ステップＳ２２では、全ての演算種類について処理が終っていれば（ｙｅｓ）、全体の処理を終了する。また、全ての演算種類について処理が終っていないのであれば（ｎｏ）、ステップＳ１１の演算種類選択処理に戻る。
【０１０８】
この例の場合には、演算種類Ａについては処理が終ったが、別の演算種類Ｂについては未処理であるため、別の演算種類Ｂを選択するために、ステップＳ１１の演算種類選択処理に戻る。
【０１０９】
演算種類Ｂについても同じ処理を繰り返す。図１２（ａ）では既に演算の節点Ｂ１と演算の節点Ｂ２のスケジューリングは異なるステップに決まっているため、ステップＳ１３で選ばれる組合せは存在しない。よって、ステップＳ１４〜Ｓ１８の各処理は行なわれず、ステップＳ１９の終了判定で終了（ｙｅｓ）と判定される。最終的に、図３１の最適解がスケジューリング結果として得られる。
【０１１０】
ここで、更に別の例で説明する。図２２のデータフローグラフをスケジューリングする場合を考える。以下の説明では、図２２の節点２０１の乗算を＊１、節点２０２の乗算を＊２と表す。
【０１１１】
図２２のデータフローグラフは演算の種類として乗算と加算を含んでおり、乗算器の方が加算器よりも占有面積が大きい。よって、図３のステップＳ１１の処理では演算の種類として乗算を先に選択する。
【０１１２】
次に、ステップＳ１２で各節点の割り付け表を作成する。ここで、クロックサイクルが乗算器と加算器の遅延の和よりも長いとすると、図２２のデータフローグラフに含まれる三つの演算は１クロックサイクルで実行可能である。よって、図２２のデータフローグラフのＡＳＡＰスケジューリングとＡＬＡＰスケジューリングは共に図２４の場合と等しくなる。この結果、割り付け表は図１４のようになり、ステップＳ１３で得られる組合せは（＊１，＊２）と（＊２，＊１）のみである。
【０１１３】
さらに、ステップＳ１４〜ステップＳ１７で仮枝の挿入を行う。（＊１）から（＊２）に仮枝を入れた場合が図１５（ａ）、（＊２）から（＊１）に仮枝を入れた場合が図１５（ｂ）である。どちらも自由度は「０」で、ステップが延びているので評価値は−１００である。よって、ステップＳ１８ではどちらを選んでもよく、ここでは、図１５（ａ）を選ぶ。
【０１１４】
さらに、ステップＳ１９で全演算が完了かどうかを判定する終了判定を行う。ステップ数を最小化する場合、即ち、乗算器の個数に上限がない場合、ステップＳ１８で選んだ組合せの評価値が正の場合は終了しておらず、評価値が負または評価された選択肢がない場合は終了している。この場合は評価値は負であるので処理は終了している。よって、ステップＳ２１の処理に進み、仮枝を削除する。
【０１１５】
さらに、ステップＳ２２で全演算種類が完了かどうかを判定する終了判定を行う。乗算は今の手順で処理が終了し、加算はデータフローグラフ中に１個しかないため処理する必要がない。よって、終了している。これにより、１クロックサイクルで終了する図２４のスケジューリング結果が得られる。
【０１１６】
使用できる乗算器の個数に制限がある場合は、次の終了判定方法となる。乗算器を１個しか使えない場合、ステップＳ１３で選んだステップの演算数が演算器数の上限よりも小さいか同じの時は終了であるが、この場合はステップＳ１３で選んだステップの乗算器の個数は２個であるので終了しておらず、ステップＳ２０の処理に進む。使用できる乗算器の個数に制限がある場合は評価値が負でもよい。
【０１１７】
ステップＳ２０では、図１５（ａ）の仮枝を本枝として図１６のデータフローグラフを得る。
【０１１８】
再度、ステップＳ１２で、各節点の割り付け表を作成する。図１６で（＊１）から（＊２）に本枝が入っているため、ＡＳＡＰスケジューリングとＡＬＡＰスケジューリングは共に図１５（ａ）と同じものとなる。よって、図１６のデータフローグラフから図１７の各節点の割り付け表が得られる。ステップＳ１３で図１７の各節点の割り付け表から各節点の組合せを抽出するが、図１７の各節点の割り付け表では全てのステップで乗算が１個しかないので、組合せが存在しない。よって、ステップＳ１４〜Ｓ１８では何も処理が為されない。
【０１１９】
ステップＳ１９の全演算が完了したかどうかを判定する終了判定では、ステップＳ１３で選んだステップの演算数が演算器数の上限よりも小さいか同じの時は終了である。この場合はどちらも１個であるため終了し、ステップＳ２１の処理に進む。
【０１２０】
ステップＳ２１では、この場合は仮枝がないために何も処理をしない。
【０１２１】
ステップＳ２２で全演算の種類が完了したかどうかを判定する終了判定を行う。乗算は今の手順で処理が終了し、加算はデータフローグラフ中に１個しかないため処理する必要がない。よって、終了している。これにより、１個しか乗算器を含まない、図２６と同じスケジューリング結果が得られる。
【０１２２】
このように、本発明のスケジューリング方法では、ステップＳ１９の終了条件の判定方法を変更するだけで、与えられたステップ数で動作するスケジューリング結果や与えられた演算器の個数で動作するスケジューリング結果を得ることができる。これにより、図２４のような高速に動作するスケジューリング結果や、図２５のような演算器数が少ないスケジューリング結果を選択的に得ることが可能である。
【０１２３】
図３のアルゴリズムは、演算の間に枝を挿入することで演算間の前後関係を決め、実行するステップは固定しない。このため、例えば図２６のような並列演算を含む処理などの場合に、アルゴリズム適用完了後に実行するステップが一意に決まらない場合があり得る。図１９は図１８の並列演算を含む動作記述例から得られるデータフローグラフである。
【０１２４】
ここで、乗算器は１個しか使用しないとう条件でスケジューリングを行うと、乗算２８０１と２８０２の間に本枝が張られて乗算２８０１はステップ１に、乗算２８０２はステップ２にスケジューリングされることになる。しかし、加算２８０３に関しては枝は張られないため、加算２８０３のステップが決まらない。これは、加算２８０３がステップ１とステップ２のどちらにスケジューリングされても乗算器１個と加算器１個が必要で、使用する演算器数はどちらでも同じであることを意味している。よって、演算器の個数の観点から見ると、加算器をステップ１にスケジューリングした図２０（ａ）でも、加算器をステップ２にスケジューリングした図２０（ｂ）でも同じである。
【０１２５】
しかし、図２０（ａ）と図２０（ｂ）とは、必要とするレジスタの個数が異なっている。図２０（ａ）では、ステップ１からステップ２へ移るときに、レジスタが３個必要である。枝２９０１に対応するａの値、枝２９０２に対応するｂ＊ｃの値、枝２９０３に対応するｂ＋ｃの値の三つを記憶しなければならないからである。
【０１２６】
これに対して、図２０（ｂ）では、ステップ１からステップ２へ移る時に、レジスタが４個必要となる。枝２９０４に対応するａの値、枝２９０５に対応するｂ＊ｃの値、枝２９０６に対応するｂの値、枝２９０７に対応するｄの値の四つを記憶せねばならないからである。よって、演算器の個数は図２０（ａ）と図２０（ｂ）で等しいが、レジスタ数の少ない図２０（ａ）の方が優れている。
【０１２７】
一般的に言うと、図３のアルゴリズムを適用した後のデータフローグラフにおいて、ＡＳＡＰスケジューリングとＡＬＡＰスケジューリングが異なる演算については、ＡＳＡＰスケジューリングのステップとＡＬＡＰスケジューリングのステップの間のどこのステップにスケジューリングしても、使用する演算器の個数は同じである。よって、入力のビット数合計が出力のビット数合計よりも大きい演算はできるだけ上にスケジューリングし、逆の演算はできるだけ下にスケジューリングすることでレジスタを削減することができる。例えば、図２０の例では、二つの乗算はＡＳＡＰスケジューリングとＡＬＡＰスケジューリングが等しいためスケジューリングは決定している。加算は、ＡＳＡＰスケジューリングはステップ１でＡＬＡＰスケジューリングはステップ２と異なっており、ステップ１とステップ２のいずれにもスケジューリングが可能である。ここで、加算の入力のビット数は出力のビット数の倍であるため、できるだけ上にスケジューリングする方がレジスタの数は減る。よって、ステップ１にスケジューリングする。これにより、必要なレジスタが少ない図２０（ａ）のスケジューリング結果を得ることができる。
【０１２８】
以上により、本実施形態によれば、スケジューリング部１１４は、最多の演算処理部が割り付けられる可能性のある実行ステップに含まれる複数の演算処理部から二つの演算処理部を選ぶ順列を抽出する順列抽出手段１１４Ｃと、抽出された各演算処理部の順列から一つを選び、選んだ二つの演算処理部間に、実行順序を決定する枝を挿入し、この枝が挿入されたコントロールデータフローグラフの自由度を用いてコントロールデータフローグラフの評価値を求める評価値算出処理を全順列の組合せについて実行する評価値算出手段１１４Ｄと、評価値が最も高い組合せを選択することにより、複数の演算処理に対応した実行ステップをそれぞれ決定する実行ステップ決定手段１１４Ｅとを有する。これによって、できるだけ短時間で最適なスケジューリング解を求めることができる。
【０１２９】
なお、以上のように、本発明の好ましい実施形態を用いて本発明を例示してきたが、本発明は、この実施形態に限定して解釈されるべきものではない。本発明は、特許請求の範囲によってのみその範囲が解釈されるべきであることが理解される。当業者は、本発明の具体的な好ましい実施形態の記載から、本発明の記載および技術常識に基づいて等価な範囲を実施することができることが理解される。本明細書において引用した特許、特許出願および文献は、その内容自体が具体的に本明細書に記載されているのと同様にその内容が本明細書に対する参考として援用されるべきであることが理解される。
【産業上の利用可能性】
【０１３０】
本発明は、回路動作が表現された動作記述を解析し、解析された動作情報からレジスタトランスファーレベルの回路を高位合成する高位合成装置、この高位合成処理において、動作記述から、各種処理手段を示す各節点とデータの流れを示す入出力枝によりコントロールデータフローグラフを生成し、コントロールデータフローグラフ中の各演算を実行するステップを決定するスケジューリング処理を行うスケジューリング方法、スケジューリングプログラムおよび可読記録媒体の分野において、できるだけ短時間で最適なスケジューリング解を求めることができる。
【図面の簡単な説明】
【０１３１】
【図１】本発明の高位合成装置の一実施形態における要部構成例を示すブロック図である。
【図２】図１のスケジューリング部の詳細構成例を示すブロック図である。
【図３】本発明のスケジューリング方法における各処理手順の一例を示すフローチャートである。
【図４】図２９のＡＳＡＰスケジューリング結果のデータフローグラフを示す図である。
【図５】図２９のＡＬＡＰスケジューリング結果のデータフローグラフを示す図である。
【図６】図３のステップＳ１２の処理手順で作成される各節点の割り付け表を示す図である。
【図７】図６から例えば（Ａ３，Ａ２）の組合せを選び、節点Ａ３から節点Ａ２へ仮枝（有向枝）を挿入した場合のデータフローグラフを示す図である。
【図８】（ａ）〜（ｄ）は、図３のステップＳ１６で全ての評価処理をしなければならない組合せ時の自由度および評価値を求めた結果を示す図である。
【図９】図３のステップＳ１２の処理手順で再度作成される各節点の割り付け表を示す図である。
【図１０】図９のステップ１の組合せの自由度と評価値を示す図であって、（ａ）は節点Ａ３がステップ２で、節点Ａ２がステップ３に置かれた場合のデータフローグラフを示す図であり、（ｂ）は節点Ａ３がステップ１で、節点Ａ２がステップ４に置かれた場合のデータフローグラフを示す図である。
【図１１】図３のステップＳ１２の処理手順で更に再度作成される各節点の割り付け表を示す図である。
【図１２】図１１のステップ３の組合せの自由度と評価値を示す図であって、（ａ）は節点Ａ２がステップ３で、節点Ａ４がステップ４に置かれた場合のデータフローグラフを示す図であり、（ｂ）は節点Ａ２がステップ４で、節点Ａ４がステップ３に置かれた場合のデータフローグラフを示す図である。
【図１３】図３のステップＳ１２の処理手順で更に再度作成される各節点の割り付け表を示す図である。
【図１４】図２２のデータフローグラフをスケジューリングする場合に、図３のステップＳ１２の処理手順で作成される各節点の割り付け表を示す図である。
【図１５】図１４のステップ１の組合せの自由度と評価値を示す図であって、（ａ）は、図１４の（＊１）から（＊２）に仮枝を入れた場合のデータフローグラフの一例を示す図であり、（ｂ）は、図１４の（＊２）から（＊１）に仮枝を入れた場合のデータフローグラフの一例を示す図である。
【図１６】図１５（ａ）の仮枝を本枝とした場合のデータフローグラフを示す図である。
【図１７】図１６のデータフローグラフから得られる各節点の割り付け表を示す図である。
【図１８】動作記述例を示す図である。
【図１９】図１８の動作記述例から得られるデータフローグラフを示す図である。
【図２０】レジスタ数の評価を行うために、図１９のデータフローグラフをスケジューリングした場合を示す図であって、（ａ）は加算をステップ１に設置した場合の図であり、（ｂ）は加算をステップ２に設置した場合の図である。
【図２１】Ｃ言語で書かれた動作記述の一例を示す図である。
【図２２】図２１の動作記述から得られるデータフローグラフの一例を示す図である。
【図２３】図２２のデータフローグラフの計算機上でのデータ構造を示す図である。
【図２４】図２２のデータフローグラフをスケジューリングしたスケジューリング結果の一例を示す図である。
【図２５】図２４のスケジューリング結果から得られる回路図である。
【図２６】図２２のデータフローグラフをスケジューリングしたスケジューリング結果の別の一例を示す図である。
【図２７】図２６のスケジューリング結果から得られる回路図である。
【図２８】データフローグラフ中の各演算が各ステップにスケジューリングされる確率の表を示す図である。
【図２９】データフローグラフの他の例を示す図である。
【図３０】図２９のデータフローグラフにおけるスケジューリングの途中経過を示す図である。
【図３１】図２９のデータフローグラフにおける最適なスケジューリング結果を示す図である。
【符号の説明】
【０１３２】
１０  高位合成装置
１１  制御部
１２  ＲＯＭ（可読記録媒体）
１１４  スケジューリング部（スケジューリング手段）
１１４Ａ  演算種類決定手段
１１４Ｂ  割付表作成手段
１１４Ｃ  順列抽出手段
１１４Ｄ  評価値算出手段
１１４Ｅ  実行ステップ決定手段
【図１】
2005316785.tif 000003
【図２】
2005316785.tif 000004
【図３】
2005316785.tif 000005
【図４】
2005316785.tif 000006
【図５】
2005316785.tif 000007
【図６】
2005316785.tif 000008
【図７】
2005316785.tif 000009
【図８】
2005316785.tif 000010
【図９】
2005316785.tif 000011
【図１０】
2005316785.tif 000012
【図１１】
2005316785.tif 000013
【図１２】
2005316785.tif 000014
【図１３】
2005316785.tif 000015
【図１４】
2005316785.tif 000016
【図１５】
2005316785.tif 000017
【図１６】
2005316785.tif 000018
【図１７】
2005316785.tif 000019
【図１８】
2005316785.tif 000020
【図１９】
2005316785.tif 000021
【図２０】
2005316785.tif 000022
【図２１】
2005316785.tif 000023
【図２２】
2005316785.tif 000024
【図２３】
2005316785.tif 000025
【図２４】
2005316785.tif 000026
【図２５】
2005316785.tif 000027
【図２６】
2005316785.tif 000028
【図２７】
2005316785.tif 000029
【図２８】
2005316785.tif 000030
【図２９】
2005316785.tif 000031
【図３０】
2005316785.tif 000032
【図３１】
2005316785.tif 000033