(57)【要約】【課題】ユーザに求られた実行性能(周波数、実行サイクル数)を満たし、演算器の使用数および演算処理速度によるコストを削減する命令スケジューリング方法を提供する。【解決手段】回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てる命令スケジューリング方法であって、各命令の配置可能な時間範囲を表す自由度を検出する検出ステップと、命令に対応する演算器による負荷をサイクル毎に算出する算出ステップと、前記負荷に基づいて前記自由度の範囲内で同じ演算器を使用する命令を別のサイクルに割り当てる割り当てステップとを有する。【選択図】図１
2006139553.tif 000002
【特許請求の範囲】
【請求項１】
回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てる命令スケジューリング方法であって、
各命令の配置可能な時間範囲を表す自由度を検出する検出ステップと、
命令に対応する演算器による負荷をサイクル毎に算出する算出ステップと、
前記負荷に基づいて前記自由度の範囲内で同じ演算器を使用する命令を別のサイクルに割り当てる割り当てステップと
を有することを特徴とする命令スケジューリング方法。
【請求項２】
前記命令スケジューリング方法は、さらに、
実行サイクル数についてのユーザ指定を受け付け、前記命令列を配置するサイクル数を決定するステップを有する
ことを特徴とする請求項１記載の命令スケジューリング方法。
【請求項３】
前記命令スケジューリング方法は、さらに、
演算器の個数指定を演算器の種類別に受け付ける受付ステップを有し、
前記割り当てステップは、前記個数指定に従って命令を割り当てる
ことを特徴とする請求項１記載の命令スケジューリング方法。
【請求項４】
前記命令スケジューリング方法は、さらに、
演算器の限界数を演算器の種類別に受け付ける受付ステップを有し、
前記割り当てステップにおいて、前記限界数の範囲内で演算器に対応する命令を配置する
ことを特徴とする請求項１記載の命令スケジューリング方法。
【請求項５】
前記命令スケジューリング方法は、さらに、
コストを削減すべき演算器に関するユーザ指定を受け付ける受付ステップを有し、
前記割り当てステップにおいて、ユーザ指定による演算器を優先して配置する
ことを特徴とする請求項１記載の命令スケジューリング方法。
【請求項６】
前記命令スケジューリング方法は、さらに、
コストを削減すべき演算器の優先順位に関するユーザ指定を受け付ける受付ステップを有し、
前記割り当てステップにおいて、当該優先順位に従って配置する
ことを特徴とする請求項１記載の命令スケジューリング方法。
【請求項７】
前記命令スケジューリング方法は、さらに、
使用演算器数と演算処理速度に伴うコストとのどちらを優先的に削減するかユーザ指定により選択する選択ステップを有し、
前記算出ステップにおいて、前記負荷として、使用演算器数による第１の負荷と、演算処理速度に伴うコストに関する第２の負荷とを算出し、
前記割り当てステップにおいて、第１および第２の負荷のうち選択結果に対応する方を優先して削減するように配置する
ことを特徴とする請求項１記載の命令スケジューリング方法。
【請求項８】
回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てる命令スケジューリング方法であって、
ユーザによって指定された回路の実行性能として実行サイクル数を取得する取得ステップと、
前記命令列の命令間の依存関係を示す有向非循環グラフを作成する作成ステップと、
指定された実行性能を満たし、かつ演算器数および演算処理速度に伴うコストが小さくなるように各命令を何れかのサイクルに割り当てる割り当てステップと
を有し、
前記割り当てステップは、
前記実行性能に基づいてスケジューリングの対象となる命令列が割り当てられるべき全体のサイクル数を表すスケジューリング時間範囲を決定する第１サブステップと、
目標とする演算器数を演算器の種類別に設定する第２サブステップと、
有向非循環グラフに基づいて命令毎にスケジューリング時間範囲内で命令を割り当て可能な時間範囲を表す自由度を求める第３サブステップと、
サイクル毎に演算器の負荷を算出する第４サブステップと、
目標とする演算器数と算出された負荷とに基づいて前記自由度の範囲内で命令の配置時刻を決定することによって、命令をサイクルに割り当てる第５サブステップをと有する
ことを特徴とする命令スケジューリング方法。
【請求項９】
前記第１サブステップでは、
ユーザにより指定された実行サイクル数をスケジューリング時間範囲と決定する
ことを特徴とする請求項８記載の命令スケジューリング方法。
【請求項１０】
前記第２サブステップでは、
ユーザにより演算器数を指定されていない種類の演算器に対して、その演算器を使用する命令の総数をスケジューリング時間範囲のサイクル数で割って整数化した値を目標演算器数と設定する
ことを特徴とする請求項８記載の命令スケジューリング方法。
【請求項１１】
前記第２サブステップでは、
ユーザにより演算器数を指定された種類の演算器に対して、当該演算器数を目標演算器数と設定する
ことを特徴とする請求項８記載の命令スケジューリング方法。
【請求項１２】
第４サブステップでは、
演算器数を削減するような命令配置時間を求める指標となる演算器数負荷、および演算処理速度に伴うコストを削減するような命令配置時間を求める指標となる最小演算速度負荷を算出する
ことを特徴とする請求項８記載の命令スケジューリング方法。
【請求項１３】
前記最小演算速度負荷は、最小演算速度負荷を求めるサイクルに該当の命令を配置する場合に、演算時間として使用可能な最大の時間の逆数と等しい
ことを特徴とする請求項１２記載の命令スケジューリング方法。
【請求項１４】
第５サブステップでは、
命令列全体で使用される演算器を削減するために、演算器数負荷が目標演算器数を超えている演算器を用いる命令から先に配置時刻を決定する
ことを特徴とする請求項８記載の命令スケジューリング方法
【請求項１５】
第５サブステップでは、
演算器数負荷が目標演算器数を超えている演算器を用いる命令のなかから、以下の規則（ａ）（ｂ）の優先度に従って選択された命令に対して最初に自由度を変更する
ことを特徴とする、請求項１４記載の命令スケジューリング方法。
（ａ）演算器数負荷が目標演算器数を最も超えているサイクルを負荷削減対象サイクルとし、それよりも前のサイクルに配置される可能性のある命令が存在する場合
(優先１)最も高さが高い命令
(優先２)最も子ノードの数が多い命令
(優先３)最も深さが浅い命令
(優先４)最も親ノードの数が少ない命令
(優先５)最もＤＡＧノードIDの小さい命令
（ｂ）負荷削減対象サイクルよりも前のサイクルに配置される可能性のある命令が存在しない場合
(優先１)最も高さが低い命令
(優先２)最も子ノードの数が少ない命令
(優先３)最も深さが深い命令
(優先４)最も親ノードの数が多い命令
(優先５)最もＤＡＧノードIDの大きい命令
【請求項１６】
第５サブステップでは、
最初に自由度を変更する命令が負荷削減対象サイクルよりも前のサイクルに配置される可能性がある場合、その命令は負荷削減対象サイクルの１つ手前のサイクルまでに配置されるものとして自由度を変更し、
負荷削減対象サイクルよりも前のサイクルに配置される可能性がない場合、その命令は負荷削減対象サイクルの１つ後のサイクル以降に配置されるものとして自由度を変更することを特徴とする請求項１５記載の命令スケジューリング方法
【請求項１７】
第４サブステップでは、サイクル毎の命令について、演算処理速度に伴うコストを削減するような命令配置時間を求める指標となる最小演算速度負荷を算出し、
第５サブステップでは、演算速度負荷削減の指標となる目標演算速度負荷を用いて命令の配置時刻を決定し、
前記目標演算速度負荷は、演算速度負荷削減の対象となる演算器を使用する命令の最小演算速度負荷の最小値の中で、最も大きい最小演算速度負荷の値と設定される
ことを特徴とする請求項８記載の命令スケジューリング方法
【請求項１８】
前記命令スケジューリング方法は、さらに、
命令の割り当て結果に従って、命令の演算結果が同一サイクル内の他の命令で使用される場合には、レジスタに格納することなく同一サイクル内で演算結果を他の命令に引き渡すように当該２つ命令を書き換える書き換えステップを有する
ことを特徴とする請求項８記載の命令スケジューリング方法。
【請求項１９】
回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てる命令スケジューリング装置であって、
各命令の配置可能な時間範囲を表す自由度を検出する検出手段と、
命令に対応する演算器による負荷をサイクル毎に算出する算出手段と、
前記負荷に基づいて前記自由度の範囲内で同じ演算器を使用する命令を別のサイクルに割り当てる割り当て手段と
を備えることを特徴とする命令スケジューリング装置。
【請求項２０】
回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てて、命令列から回路を合成する回路合成方法であって、
各命令の配置可能な時間範囲を表す自由度を検出する検出ステップと、
命令に対応する演算器による負荷をサイクル毎に算出する算出ステップと、
前記負荷に基づいて前記自由度の範囲内で同じ演算器を使用する命令を別のサイクルに割り当てる割り当てステップと
を有することを特徴とする回路合成方法。
【請求項２１】
回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てて、命令列から回路を合成する回路合成装置であって、
各命令の配置可能な時間範囲を表す自由度を検出する検出手段と、
命令に対応する演算器による負荷をサイクル毎に算出する算出手段と、
前記負荷に基づいて前記自由度の範囲内で同じ演算器を使用する命令を別のサイクルに割り当てる割り当て手段と
を備えることを特徴とする回路合成装置。
【請求項２２】
回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てる命令スケジューリング方法をコンピュータに実行させるプログラムであって、
各命令の配置可能な時間範囲を表す自由度を検出する検出ステップと、
命令に対応する演算器による負荷をサイクル毎に算出する算出ステップと、
前記負荷に基づいて前記自由度の範囲内で同じ演算器を使用する命令を別のサイクルに割り当てる割り当てステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項２３】
回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てて、命令列から回路を合成する回路合成方法をコンピュータに実行させるプログラムであって、
各命令の配置可能な時間範囲を表す自由度を検出する検出ステップと、
命令に対応する演算器による負荷をサイクル毎に算出する算出ステップと、
前記負荷に基づいて前記自由度の範囲内で同じ演算器を使用する命令を別のサイクルに割り当てる割り当てステップと
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに配置する命令スケジューリング方法に関する。
【背景技術】
【０００２】
従来の高位合成コンパイラは、ソフトウェアパイプライニング等の各種並列化技術により実行効率が向上されているが、結果の実行サイクル数はコンパイル終了時まで不明である。また、実行効率を向上させる最適化が各種なされているのに対し、回路面積削減や消費電力削減を狙った最適化はあまり行われていない。
【０００３】
非特許文献１では、命令スケジューリング方法として、演算器の再利用率を向上させる方法としてForce Directed Schedulingが提案されている。
【非特許文献１】P.G. Paulin and J.P. Knight, "Force-directed scheduling in automatic data path synthesis," Proc. 24th Design Automation Conference, pp. 195-202, 1987.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の高位合成コンパイラでは、実行効率を向上させることのみを主眼とするため、必要以上に実行性能を向上させる反面、電力や回路面積の増加を引き起こす可能性が高い。
【０００５】
より詳しく言うと、機能が同じ演算器であっても、レイテンシ（処理遅延）が小さいが回路規模が大きく消費電力も多い高速型の演算器と、レイテンシが大きいが回路規模が小さく消費電力も小さい低速型の演算器がある場合に、従来技術では必要とされる周波数（又はサイクル時間）両者を使い分けることなく、必要以上の実行性能を持たせることがある。また、演算器による演算時間(レイテンシ)が１サイクルの時間に比べて無駄に短い場合もある。
【０００６】
このように、従来技術では、回路の実行性能を高めることを可能にする反面、必要以上の実行性能を持たせることにより回路規模や消費電力というコスト（以下、演算処理速度に伴うコストと呼ぶ。）を高めてしまっているという問題がある。
【０００７】
例えば、ＡＶ処理を行うハードウェア設計においては、各モジュールに割り当てられる実行サイクル数は決まっており、それを満たし、なおかつ演算器数や演算処理速度に伴うコストを考慮した最適な回路を設計する必要がある。
【０００８】
本発明は上記問題点を解決するもので、回路面積の削減と消費電力の削減をバランスよく行う命令スケジューリング方法を提供することを目的とする。
【０００９】
さらに本発明は、ユーザに求められた実行性能(周波数、実行サイクル数)を満たし、演算器の使用数および演算処理速度によるコストを削減する命令スケジューリング方法を提供することを他の目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するため本発明の命令スケジューリング方法は、回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てる命令スケジューリング方法であって、各命令の配置可能な時間範囲を表す自由度を検出する検出ステップと、命令に対応する演算器による負荷をサイクル毎に算出する算出ステップと、前記負荷に基づいて前記自由度の範囲内で同じ演算器を使用する命令を別のサイクルに割り当てる割り当てステップとを有することを特徴とする。
【００１１】
この構成によれば、同一演算器を使用する命令を異なるサイクルに割り当てることにより、複数の命令が同一演算器を使用するように演算器の再利用率を高め、使用演算器数を減少させ、負荷に基づく割り当てにより、例えば演算速度が遅くコストの小さい演算器の使用率を向上させることができ、回路面積の削減と消費電力の削減をバランスよく行うことができる。
【００１２】
ここで、前記命令スケジューリング方法は、さらに、実行サイクル数についてのユーザ指定を受け付け、前記命令列を配置するサイクル数を決定するステップを有していてもよい。
【００１３】
この構成によれば、ユーザの求める実行性能(周波数、実行サイクル数)に応じてスケジューリングを行うことを特徴としており、必要以上に実行性能の向上を求めて電力や回路面積の増加を引き起こすことなく、ユーザの求める実行性能を満たし、なおかつ回路面積や消費電力の小さい最適な回路を生成することができる。
【００１４】
ここで、前記命令スケジューリング方法は、さらに、演算器の個数指定を演算器の種類別に受け付ける受付ステップを有し、前記割り当てステップは、前記個数指定に従って命令を割り当てるようにしてもよい。
【００１５】
この構成によれば、使用される演算器の数が既に決まっているものは、その種類の演算器を最大限に利用することで、他の演算器の使用数および演算処理速度によるコストを削減することができる。
【００１６】
ここで、前記命令スケジューリング方法は、さらに、演算器の限界数を演算器の種類別に受け付ける受付ステップを有し、前記割り当てステップにおいて、前記限界数の範囲内で演算器に対応する命令を配置するようにしてもよい。
【００１７】
この構成によれば、回路面積や消費電力の大きい演算器の使用限度を決めることで、回路面積および消費電力の増加を防ぐことが可能となる。
【００１８】
ここで、前記命令スケジューリング方法は、さらに、コストを削減すべき演算器に関するユーザ指定を受け付ける受付ステップを有し、前記割り当てステップにおいて、ユーザ指定による演算器を優先して配置するようにしてもよい。
【００１９】
この構成によれば、回路面積や消費電力の大きい演算器など、ユーザ指定により特に演算器数や演算速度に伴うコストを削減したい演算器を優先して配置することにより、その演算器の使用数や演算速度に伴うコストを削減することが可能となる。
【００２０】
ここで、前記命令スケジューリング方法は、さらに、コストを削減すべき演算器の優先順位に関するユーザ指定を受け付ける受付ステップを有し、前記割り当てステップにおいて、当該優先順位に従って配置するようにしてもよい。
【００２１】
この構成によれば、特に使用演算器数または演算処理速度に伴うコストを削減したい演算器の優先順位をつけることで、優先順位の高いものは確実に削減することが可能となる。
【００２２】
ここで、前記命令スケジューリング方法は、さらに、使用演算器数と演算処理速度に伴うコストとのどちらを優先的に削減するかユーザ指定により選択する選択ステップを有し、前記算出ステップにおいて、前記負荷として、使用演算器数による第１の負荷と、演算処理速度に伴うコストに関する第２の負荷とを算出し、前記割り当てステップにおいて、第１および第２の負荷のうち選択結果に対応する方を優先して削減するように配置するようにしてもよい。
【００２３】
この構成によれば、  使用演算器数と演算処理速度に伴うコストのどちらを優先的に削減するかユーザ選択可能であることを特徴としており、スケジューリング対象となる命令列がデータパス型なのかパイプライン型なのか、そのタイプに応じて最適な回路を生成することが可能となる。
【００２４】
また、本発明の命令スケジューリング方法は、回路合成の対象となる命令列に含まれる各命令を、回路の実行サイクルに割り当てる命令スケジューリング方法であって、ユーザによって指定された回路の実行性能として実行サイクル数を取得する取得ステップと、前記命令列の命令間の依存関係を示す有向非循環グラフを作成する作成ステップと、指定された実行性能を満たし、かつ演算器数および演算処理速度に伴うコストが小さくなるように各命令を何れかのサイクルに割り当てる割り当てステップと有し、前記割り当てステップは、前記実行性能に基づいてスケジューリングの対象となる命令列が割り当てられるべき全体のサイクルを表すスケジューリング時間範囲を決定する第１サブステップと、目標とする演算器数を演算器の種類別に設定する第２サブステップと、有向非循環グラフに基づいて命令毎にスケジューリング時間範囲内で命令を割り当て可能な時間範囲を表す自由度を求める第３サブステップと、サイクル毎に演算器の負荷を算出する第４サブステップと、目標とする演算器数と算出された負荷とに基づいて前記自由度の範囲内で命令の配置時刻を決定することによって、命令をサイクルに割り当てる第５サブステップをと有する。
【００２５】
この構成によれば、スケジューリング対象となる命令を、使用演算器数および演算処理速度に伴うコストが小さくなるように、自由度の範囲内で最も適した時間に挿入することで、回路面積および消費電力の小さい回路を生成することが可能となる。
【００２６】
ここで、前記第１サブステップでは、ユーザにより指定された実行サイクル数をスケジューリング時間範囲と決定するようにしてもよい。
【００２７】
この構成によれば、スケジューリング対象となる命令列をユーザが指定したサイクル数で実行するのに最適な回路を生成することが可能となる。
【００２８】
ここで、前記第２サブステップでは、ユーザにより演算器数を指定されていない種類の演算器に対して、その演算器を使用する命令の総数をスケジューリング時間範囲のサイクル数で割って整数化した値を目標演算器数と設定するようにしてもよい。
【００２９】
この構成によれば、演算器の再利用性を高めるためにはどの命令をどの時間に配置すべきか容易に判断することが可能となる。
【００３０】
ここで、前記第２サブステップでは、ユーザにより演算器数を指定された種類の演算器に対して、当該演算器数を目標演算器数と設定するようにしてもよい。
【００３１】
この構成によれば、数が決まっている演算器の再利用性を必要以上に高めることを防ぐことが可能となる。
【００３２】
ここで、第４サブステップでは、演算器数を削減するような命令配置時間を求める指標となる演算器数負荷、および演算処理速度に伴うコストを削減するような命令配置時間を求める指標となる最小演算速度負荷を算出するようにしてもよい。
【００３３】
この構成によれば、２種類の負荷を利用することで、回路面積と消費電力の両方をバランスよく削減した回路を得ることが可能となる。
【００３４】
ここで、前記最小演算速度負荷は、最小演算速度負荷を求めるサイクルに該当の命令を配置する場合に、演算時間として使用可能な最大の時間の逆数と等しいものとしてもよい。
【００３５】
この構成によれば、最小演算速度負荷に基づいて消費電力の小さい回路を作成するためにどの命令をどの時間に配置すべきか容易に判断することが可能となる。
【００３６】
ここで、第５サブステップでは、命令列全体で使用される演算器数を削減するために、演算器数負荷が目標演算器数を超えている演算器を用いる命令から先に配置時刻を決定するようにしてもよい。
【００３７】
この構成によれば、再利用されるべき演算器を確実に再利用することが可能となる。
ここで、第５サブステップでは、演算器数負荷が目標演算器数を超えている演算器を用いる命令のなかから、以下の規則（ａ）（ｂ）の優先度に従って選択された命令に対して最初に自由度を変更するようにしてもよい。（ａ）演算器数負荷が目標演算器数を最も超えているサイクルを負荷削減対象サイクルとし、それよりも前のサイクルに配置される可能性のある命令が存在する場合、(優先１)最も高さが高い命令、(優先２)最も子ノードの数が多い命令、(優先３)最も深さが浅い命令、(優先４)最も親ノードの数が少ない命令、(優先５)最もＤＡＧノードIDの小さい命令。（ｂ）負荷削減対象サイクルよりも前のサイクルに配置される可能性のある命令が存在しない場合、(優先１)最も高さが低い命令、(優先２)最も子ノードの数が少ない命令、(優先３)最も深さが深い命令、(優先４)最も親ノードの数が多い命令、(優先５)最もＤＡＧノードIDの大きい命令。
【００３８】
この構成によれば、早い時刻に配置すべき命令および、遅い時刻に配置すべき命令が正しく選出され、この命令の自由度を変更した影響で、他の命令において演算器数を削減可能な配置サイクルを自由度から排除してしまうことを防ぐことが可能となる。
【００３９】
ここで、第５サブステップでは、最初に自由度を変更する命令が負荷削減対象サイクルよりも前のサイクルに配置される可能性がある場合、その命令は負荷削減対象サイクルの１つ手前のサイクルまでに配置されるものとして自由度を変更し、負荷削減対象サイクルよりも前のサイクルに配置される可能性がない場合、その命令は負荷削減対象サイクルの１つ後のサイクル以降に配置されるものとして自由度を変更するようしてもよい。
【００４０】
この構成によれば、使用演算器数を削減可能な配置サイクルを自由度から排除してしまうことのないように変更後の自由度を正しく設定することが可能となる。
【００４１】
ここで、第４サブステップでは、サイクル毎の命令について、演算処理速度に伴うコストを削減するような命令配置時間を求める指標となる最小演算速度負荷を算出し、第５サブステップでは、演算速度負荷削減の指標となる目標演算速度負荷を用いて命令の配置時刻を決定し、前記目標演算速度負荷は、演算速度負荷削減の対象となる演算器を使用する命令の最小演算速度負荷の最小値の中で、最も大きい最小演算速度負荷の値と設定されるようにしてもよい。
【００４２】
この構成によれば、演算器の消費電力を減少させるにはどの命令をどの時間に配置すべきか容易に判断することが可能となる。
【００４３】
ここで、前記命令スケジューリング方法は、さらに、命令の割り当て結果に従って、命令の演算結果が同一サイクル内の他の命令で使用される場合には、レジスタに格納することなく同一サイクル内で演算結果を他の命令に引き渡すように当該２つ命令を書き換える書き換えステップを有するようにしてもよい。
【００４４】
この構成によれば、回路のレジスタ数を削減することが可能となる。
また、本発明の命令スケジュール装置、回路合成方法、回路合成装置、それらをコンピュータに実現するプログラムについても、上記と同様である。
【発明の効果】
【００４５】
本発明は、ユーザが指定した実行性能を満たし、なおかつ演算器(種類別)の使用数および演算速度に伴うコストが平均的に小さくなるようスケジューリングを行うことで、演算器の再利用性およびコストの小さい演算器の使用率を向上させるものである。これにより、回路面積および消費電力の削減が可能となる。
【発明を実施するための最良の形態】
【００４６】
以下に、本発明の実施の形態における命令スケジュール装置を備える高位合成コンパイラについて、図面を参照しながら詳細に説明する。
【００４７】
図１は、本発明の実施の形態における高位合成コンパイラの構成を示すブロック図である。
【００４８】
同図の高位合成コンパイラ１は、構文解析部１０、中間コード生成部１１、スケジューリング部１２、ＶＨＤＬ生成部１３を備える。
【００４９】
高位合成コンパイラ１は、高級言語で記述されたプログラムから回路を生成する。高級言語プログラムは、例えばＣ言語などである。また、ここでいう回路は、ハードウェアの構成を記述したプログラムであり、例えばＶＨＤＬ(VHSIC(Very High Speed Integrated Circuit) Hardware Description Language)で記述されたレジスタ・トランスファーレベルの回路記述プログラムをいう。
【００５０】
構文解析部１０は、Ｃ言語などの高級言語プログラムＰ１の構文を解析する。
中間コード生成部１１は、解析結果に基づいて高級言語プログラムＰ１を中間命令（以下単に命令と呼ぶ。）の記述に置き換えた中間コードの命令列Ｐ２を生成する。
【００５１】
スケジューリング部１２は、スケジューリング対象となる命令列Ｐ２が入力され、ユーザの求める実行性能(周波数、実行サイクル数)を満たし、かつ回路面積および消費電力の小さい回路が生成されるように最適にスケジューリングされた命令列Ｐ３を生成する。ここでいうスケジューリングは、生成すべき回路に割り当てられた複数の実行サイクルにおいて、どのサイクルにどの命令を配置するか（あるいは割り当てるか）を決定することをいう。スケジューリング部１２は、ユーザの求める実行性能(周波数、実行サイクル数)を満たす範囲内で、同一演算器を使用する命令を異なるサイクルに配置し、これらの命令にかかるサイクル毎の演算時間が平均的に余裕を持つように依存関係のある命令を適宜別のサイクルに移動させる。これにより、演算器の再利用率を高めて使用演算器数を減少させ、また演算速度が遅くコストの小さい演算器の使用率を向上させるようにしている。
【００５２】
ＶＨＤＬ生成部１３は、スケジューリング部１２によってスケジューリングされた命令列からＶＨＤＬプログラムを生成する。
【００５３】
また、同図のスケジューリング部１２は、実行性能読みこみ部１４、ＤＡＧ生成部１５、命令配置時刻検出部１６、命令挿入部１７を備える。
【００５４】
実行性能読み込み部１４は、ユーザによって指定された、スケジューリング対象となる命令列の実行性能(周波数、実行サイクル数)を外部からあるいは所定のファイルから読み込む。
【００５５】
ＤＡＧ生成部１５は、スケジューリング対象となる命令列Ｐ２における命令間の依存関係を示す有向非循環グラフ(ＤＡＧ：Directed Acyclic Graph、以下ＤＡＧと呼ぶ。)を生成する。
【００５６】
命令配置時刻検出部１６は、実行性能読み込み部１４により読み込まれた実効性を満たし、かつ使用演算器数および演算処理速度に伴うコストが小さくなるように、各命令の配置時刻をスケジューリング時間範囲内から求める。ここで、スケジューリング時間範囲は、命令列Ｐ２に対応する回路に割り当てられるサイクル数をいう。また、命令の配置時刻は、スケジューリング時間範囲内の時刻をいう。この時刻は、例えばサイクルおよびサイクル先頭からの遅延時間により表される。
【００５７】
命令挿入部１７は、命令配置時刻検出ステップで求められた時刻に命令を挿入する。具体的には、命令挿入部１７は、同一サイクルで実行される命令を区別するために、各サイクルの区切りを示すマーク(例えば”;;”)の間に命令を挿入する（図２１Ａ参照）とともに、命令の演算結果が同一サイクル内の他の命令で使用される場合には、レジスタに格納することなく同一サイクル内で演算結果を他の命令に引き渡すように当該２つ命令のオペランドを書き換える。
【００５８】
図２Ａは、スケジューリング対象となる命令列Ｐ２の一例を示す図である。
ここで、命令列Ｐ２で示された命令１〜命令６について説明する。
【００５９】
命令１は、仮想レジスタvr1と仮想レジスタvr2に格納されているデータを加算し、その結果を仮想レジスタvr8に格納する命令である。
【００６０】
命令２は、仮想レジスタvr3と仮想レジスタvr4に格納されているデータを乗算し、その結果を仮想レジスタvr9に格納する命令である。
【００６１】
命令３は、仮想レジスタvr6と仮想レジスタvr7に格納されているデータを乗算し、その結果を仮想レジスタvr10に格納する命令である。
【００６２】
命令４は、仮想レジスタvr8に格納されている命令１(加算)の演算結果を仮想レジスタvr9に格納されている命令２(乗算)の演算結果でシフトし、その結果を仮想レジスタvr11に格納する命令である。つまり、命令４(シフト)は命令１(加算)と命令２(乗算)に依存している。
【００６３】
命令５は、仮想レジスタvr11に格納されている命令４(シフト)の演算結果と仮想レジスタvr5に格納されているデータを加算し、その結果を仮想レジスタvr12に格納する命令である。つまり、命令５(加算)は命令４(シフト)に依存している。
【００６４】
命令６は、仮想レジスタvr12に格納されている命令５(加算)の演算結果と仮想レジスタvr10に格納されている命令３(乗算)の演算結果を乗算し、その結果を仮想レジスタvr13に格納する命令である。つまり、命令６(乗算)は命令５(加算)と命令３(乗算)に依存している。
【００６５】
図２Ｂは、命令列Ｐ２に対してＤＡＧ生成部１５で生成されるＤＡＧの具体例を示した図である。
【００６６】
ＤＡＧ２２は、依存される命令(親ノード)と依存する命令(子ノード)が、依存される命令から依存する命令の方向に矢印で結ばれる。
【００６７】
命令１(加算)と命令４(シフト)は命令１(加算)から命令４(シフト)の方向へ、命令２(乗算)と命令４(シフト)は命令２(乗算)から命令４(シフト)の方向へ、命令４(シフト)と命令５(加算)は命令４(シフト)から命令５(加算)の方向へ、命令５(加算)と命令６(乗算)は命令５(加算)から命令６(乗算)の方向へ、命令３(乗算)と命令６(乗算)は命令３(乗算)から命令６(乗算)の方向へ、それぞれ矢印で結ばれる。
【００６８】
図３は、命令配置時刻検出部１６における命令配置時刻検出処理の詳細なフローを示した図である。
【００６９】
(S31)は、スケジューリング対象となる命令列が配置される時間範囲（サイクル数）を求めるスケジューリング時間範囲検出ステップである。
【００７０】
(S32)は、目標とされる使用演算器数を演算器の種類別に求める目標演算器数検出ステップである。ここで、ユーザにより使用演算器数が指定されている演算器の目標演算器数は、使用演算器数と等しいものとする。また、ユーザにより使用演算器数が指定されていない演算器の目標演算器数は、以下に示す[式1]より求められる。
【００７１】
目標演算器数 =
ceil ( 該当の演算器を使用する命令数 / スケジューリング時間範囲) [式1]
[式1]は、目標演算器数を求める演算器を使用する命令の総数をスケジューリング時間範囲(サイクル数)で割ったものを屋根関数の引数とした結果が目標演算器数と等しいことを示す。ここで、関数ceil(x)は屋根関数を示し、引数x以上の最小の整数を導出する関数である。
【００７２】
(S33)は、スケジューリング対象となる命令毎に、スケジューリング時間範囲内で命令が配置できる時間範囲(自由度)を求める自由度検出ステップである。
【００７３】
(S34a)は、各サイクルで使用される演算器数を演算器毎に示す指標となる使用演算器数負荷を検出するステップである。
【００７４】
(34b)は、演算処理速度に伴うコストを示す指標となる最小演算速度負荷を検出するステップである。
【００７５】
(S35)は、負荷検出ステップで求められた負荷をもとに、回路面積や消費電力を小さくするような命令の配置時刻を自由度内から求める負荷削減命令配置時刻検出ステップである。
【００７６】
まず、スケジューリング時間範囲検出ステップ(S31)について、図４を用いて説明する。
【００７７】
図４は、スケジューリング時間範囲検出ステップの検出フローを示す図である。
(S41)は、ユーザによりスケジューリング対象となる命令列に対する実行サイクル数が指定されているか否かを判定するステップである。
【００７８】
(S42)は、(S41)で指定されていると判断された場合に、指定された実行サイクル数をスケジューリング時間範囲として設定するステップである。
【００７９】
(S43)は、(S41)で指定されていないと判断された場合に、スケジューリング対象となる命令列を最高の実行性能で実行する場合の最短実行サイクル数をスケジューリング時間範囲として設定するステップである。したがって、求められる実行性能が決まっておらず、最高の実行性能で回路面積や消費電力を削減したい場合は、ユーザは実行サイクル数を指定する必要はない。
【００８０】
次に、自由度検出ステップ(S33)について、図５を用いて説明する。
図５は、自由度検出ステップでの検出フローを示す図である。
【００８１】
(S51)は、各命令をスケジューリング時間範囲内に配置する際、配置可能な時間の中で最も早い時刻(以下、ASAP(As Soon As Possible）時刻と呼ぶ。)を、親ノードから順に、それぞれの命令間のレイテンシを加算していくことで求めるステップである。ここでレイテンシとは、依存関係にある２つの命令において親ノードが実行されてから子ノードが実行可能とされるまでの時間を示す。レイテンシの単位はns(ナノセカンド)であり、２つの命令が真の依存の関係にある場合、レイテンシは親ノードが演算にかかる時間に等しい。また、２つの命令が逆依存および出力依存の関係にある場合、レイテンシは０に等しい。
【００８２】
(S52)は、各命令をスケジューリング時間範囲内に配置する際、配置可能な時間の中で最も遅い時刻(以下、ALAP(As Late As Possible)時刻と呼ぶ)を、子ノードから順に、それぞれの命令間のレイテンシを減算していくことで求めるステップである。
【００８３】
(S53)は、(S51)および(S52)で求められたASAP時刻、ALAP時刻から各命令の自由度を求めるステップである。自由度はASAP時刻からALAP時刻までの時間範囲を示し、この範囲内であれば該当する命令は配置可能である。ここでASAP時刻およびALAP時刻は、配置サイクル(cycle)および配置サイクルの先頭時間からのオフセット(offset)で表されるものとする。
【００８４】
ここで、ASAP時刻検出およびALAP時刻検出について、図６および図７を用いて説明する。
【００８５】
図６は、ASAP時刻検出フローを示す図である。
(S61)は、ＤＡＧ生成部１５で生成されたＤＡＧノードを読み込むステップである。
【００８６】
(S62)は、(S61)で読み込まれたＤＡＧノードに親ノードがあるか判定するステップである。
【００８７】
(S63)は、(S62)で親ノードがあると判定された場合に、親ノードを検出するステップである。
【００８８】
(S64)は、(S63)で検出された親ノードのASAP時刻および(S61)とのレイテンシを求めるステップである。
【００８９】
(S65)は、(S64)で求められた親ノードのASAP時刻およびレイテンシから、ASAP候補時刻を求めるステップである。
【００９０】
(S66)は、(S61)で読み込んだＤＡＧノードを、(S65)で求められたASAP候補時刻に配置した場合に、(S61)のＤＡＧノードの演算時間が配置サイクル内に収まるか判定するステップである。
【００９１】
(S67)は、(S66)で配置サイクル内に収まらないと判定された場合に、ASAP候補時刻を(S65)で求められたASAP候補時刻の次のサイクルの先頭に変更するステップである。
【００９２】
(S68)は、(S62)で求められた親ノードとは別の親ノードがあるか判定するステップである。ここであると判定された場合、(S63)から(S67)を繰り返す。
【００９３】
(S69)は、(S63)から(S67)ですべての親ノードに対するASAP候補時刻が求められた後、検出されたASAP候補時刻の中からもっとも遅い時刻を(S61)で読み込まれたＤＡＧノードのASAP時刻とするステップである。
【００９４】
(S610)は、(S62)で親ノードが１つもないと判定された場合に、先頭時刻をASAP時刻とするステップである。
【００９５】
図７は、ALAP時刻検出フローを示す図である。
(S71)は、ＤＡＧ生成部１５で生成されたＤＡＧノードを読み込むステップである。
【００９６】
(S72)は、(S71)で読み込まれたＤＡＧノードに子ノードがあるか判定するステップである。
【００９７】
(S73)は、(S72)で子ノードがあると判定された場合に、子ノードを検出するステップである。
【００９８】
(S74)は、(S73)で検出された子ノードのALAP時刻および(S71)とのレイテンシを求めるステップである。
【００９９】
(S75)は、(S74)で求められた子ノードのALAP時刻およびレイテンシから、ALAP候補時刻を求めるステップである。
【０１００】
(S76)は、(S71)で読み込んだＤＡＧノードを、(S75)で求められたALAP候補時刻に配置した場合に、(S71)のＤＡＧノードの演算時間が配置サイクル内に収まるか判定するステップである。
【０１０１】
(S77)は、(S76)で配置サイクル内に収まらないと判定された場合に、ALAP候補時刻を(S75)で求められたALAP候補時刻の前のサイクルの、サイクル終了時刻から演算に必要な時間を引いた時刻に変更するステップである。
【０１０２】
(S78)は、(S72)で求められた子ノードとは別の子ノードがあるか判定するステップである。ここであると判定された場合、(S73)から(S77)を繰り返す。
【０１０３】
(S79)は、(S73)から(S77)ですべての子ノードに対するALAP候補時刻が求められた後、検出されたALAP候補時刻の中からもっとも早い時刻を(S71)で読み込まれたＤＡＧノードのALAP時刻とするステップである。
【０１０４】
(S710)は、(S72)で子ノードが１つもないと判定された場合に、スケジューリング時間範囲の中で最も遅いサイクルのサイクル終了時刻から演算に必要な時間を引いた時刻をALAP時刻とするステップである。
【０１０５】
次に、図２Ａに示した命令列Ｐ２のASAP時刻、ALAP時刻、および自由度を求めた場合の例を図８、図９、図１０で示す。ただし、各命令の演算時間は、乗算命令が２(ns)、加算命令が１(ns)、シフト命令が１(ns)とし、すべて真の依存の関係にあるとする。また、１サイクルあたりの所要時間は５(ns)であるとし、スケジューリング時間範囲は３サイクルに指定されたものとする。
【０１０６】
図８は、図２Ａに示した命令列Ｐ２のASAP時刻を示す説明図である。
図８においてサイクル１〜３はスケジュール時間範囲を示す。黒塗りの菱形マークは各命令のをASAP時刻を示す。黒塗りの菱形マークから伸びる棒グラフは、各命令のレイテンシを示す。
【０１０７】
図２Ｂに示したＤＡＧより、命令１(加算)、命令２(乗算)、命令３(乗算)は１サイクル目の先頭に配置され、ASAP時刻はcycle=1,offset=0となる。
【０１０８】
次に命令４(シフト)は命令１(加算)および命令２(乗算)と依存があるため、命令４(シフト)の親ノードは命令１(加算)および命令２(乗算)となる。親ノード命令１(加算)のASAP時刻にレイテンシを加算した結果得られた時間はcycle=1,offset=1である。また、親ノード命令２(乗算)のASAP時刻にレイテンシを加算した結果得られた時刻はcycle=1,offset=2である。これより、命令４(シフト)のASAP候補時刻はcycle=1,offset=2となる。このASAP候補時刻に命令４(シフト)の演算時間を加算しても演算時間が配置サイクル内に収まるため、命令４(シフト)のASAP時刻はcycle=1,offset=2となる。
【０１０９】
次に命令５(加算)は命令４(シフト)と依存があるため、命令５(加算)の親ノードは命令４(シフト)となる。親ノード命令４(シフト)のASAP時刻にレイテンシを加算した結果得られた時刻はcycle=1,offset=3である。これより、命令５(加算)のASAP候補時刻はcycle=1,offset=3となる。このASAP候補時刻に命令５(加算)の演算時間を加算しても演算時間が配置サイクル内に収まるため、命令５(加算)のASAP時刻はcycle=1,offset=3となる。
【０１１０】
次に命令６(乗算)は命令５(加算)および命令３(乗算)と依存があるため、命令６(乗算)の親ノードは命令５(加算)および命令３(乗算)となる。親ノード命令５(加算)のASAP時刻にレイテンシを加算した結果得られた時刻はcycle=1,offset=4である。また、親ノード命令３(乗算)のASAP時刻にレイテンシを加算した結果得られた時刻はcycle=1,offset=2である。これより、命令６(乗算)のASAP候補時刻はcycle=1,offset=4となる。しかしながら、このASAP候補時刻に命令６(乗算)の演算時間を加算した場合、演算時間が配置サイクル内に収まらないため、命令６(乗算)のASAP時刻はcycle=2,offset=0となる。
【０１１１】
図９は、図２Ａに示した命令列Ｐ２のALAP時刻を示す説明図である。
図９において白抜きの菱形マークは各命令のをALAP時刻を示す。
【０１１２】
命令列Ｐ２のＤＡＧ（図２Ｂ参照）より、命令６(乗算)はスケジューリング時間範囲の最下端で演算を終えるように配置されるため、ALAP時刻はcycle=3,offset=3となる。
【０１１３】
次に命令５(加算)は命令６(乗算)と依存があるため、命令５(加算)の子ノードは命令６(乗算)となる。子ノード命令６(乗算)のALAP時刻からレイテンシをひいた結果得られた時刻はcycle=3,offset=2である。これより、命令５(加算)のALAP候補時刻はcycle=3,offset=2となる。このALAP候補時刻に命令５(加算)の演算時間を加算しても演算時間が配置サイクル内に収まるため、命令５(加算)のALAP時刻はcycle=3,offset=2となる。
【０１１４】
次に命令４(シフト)は命令５(加算)と依存があるため、命令４(シフト)の子ノードは命令５(加算)となる。子ノード命令５(加算)のALAP時刻からレイテンシをひいた結果得られた時刻はcycle=3,offset=1である。これより、命令４(シフト)のALAP候補時刻はcycle=3,offset=1となる。このALAP候補時刻に命令４(シフト)の演算時間を加算しても演算時間が配置サイクル内に収まるため、命令４(シフト)のALAP時刻はcycle=3,offset=1となる。
【０１１５】
次に命令３(乗算)は命令６(乗算)と依存があるため、命令３(乗算)の子ノードは命令６(乗算)となる。子ノード命令６(乗算)のALAP時刻からレイテンシをひいた結果得られた時刻はcycle=3,offset=1である。これより、命令３(乗算)のALAP候補時刻はcycle=3,offset=1となる。このALAP候補時刻に命令３(乗算)の演算時間を加算しても演算時間が配置サイクル内に収まるため、命令３(乗算)のALAP時刻はcycle=3,offset=1となる。
【０１１６】
次に命令２(乗算)は命令４(シフト)と依存があるため、命令２(乗算)の子ノードは命令４(シフト)となる。子ノード命令４(シフト)のALAP時刻からレイテンシをひいた結果得られた時刻はcycle=2,offset=4である。これより、命令２(乗算)のALAP候補時刻はcycle=2,offset=4となる。しかしながら、このALAP候補時刻に命令２(乗算)の演算時間を加算した場合、演算時間が配置サイクル内に収まらないため、命令２(乗算)のALAP時刻はcycle=2,offset=3となる。
【０１１７】
次に命令１(加算)は命令４(シフト)と依存があるため、命令１(加算)の子ノードは命令４(シフト)となる。子ノード命令４(シフト)のALAP時刻からレイテンシをひいた結果得られた時刻はcycle=3,offset=0である。これより、命令１(加算)のALAP候補時刻はcycle=3,offset=0となる。このALAP候補時刻に命令１(加算)の演算時間を加算しても演算時間が配置サイクル内に収まるため、命令１(加算)のALAP時刻はcycle=3,offset=0となる。
【０１１８】
図１０は、図２Ａに示した命令列Ｐ２に含まれる各命令の配置の自由度を示す説明図である。
【０１１９】
図８のASAP時刻から図９のALAP時刻までが自由度となるため、命令１(加算)の自由度はcycle=1,offset=0からcycle=3,offset=0、命令２(乗算)の自由度はcycle=1,offset=0からcycle=2,offset=3、命令３(乗算)の自由度はcycle=0,offset=0からcycle=3,offset=1、命令４(シフト)の自由度はcycle=1,offset=2からcycle=3,offset=1、命令５(加算)の自由度はcycle=1,offset=3からcycle=3,offset=2、命令６(乗算)の自由度はcycle=2,offset=0からcycle=3,offset=3となる。
【０１２０】
次に、負荷検出ステップ(S34a)(S34b)の詳細にについて図１１および図１２を用いて説明する。
【０１２１】
図１１は、使用演算器数負荷の検出フローを示す図である。
(S111)は、負荷を求める演算器を用いた命令を該当命令ノードリストに設定するステップである。
【０１２２】
(S112)は、該当命令ノードリストに設定されている命令を読み込むステップである。
(S113)は、読み込んだ命令の自由度を検出するステップである。
【０１２３】
(S114)は、(S113)で検出された自由度がまたがっているサイクル数を検出するステップである。すなわちここでは読み込んだ命令が配置されうるサイクルの総数を求める。
【０１２４】
(S115)は、読み込んだ命令のサイクル毎の使用演算器数負荷を、(S114)で検出されたサイクル数から求めるステップである。ここで、自由度がまたがっていない使用演算器数サイクル負荷は0とし、自由度がまたがっている使用演算器数サイクル負荷は、以下に示す[式2]より求められる。
【０１２５】
使用演算器数サイクル負荷 = 1 /自由度がまたがっているサイクル数  [式２]
(S116)は、使用演算器数サイクル負荷を算出した命令ノードを該当命令ノードリストから削除するステップである。
【０１２６】
(S117)は、該当命令ノードリストが空であるか判定するステップである。(S117)で空でないと判定された場合は(S112)に戻り、空であると判定された場合は(S118)を行う。
【０１２７】
(S118)は、(S115)で算出された使用演算器数サイクル負荷を、サイクル別にすべて加算するステップである。ここで算出されたサイクル毎の負荷を、該当演算器の使用演算器数負荷とする。
【０１２８】
図１２は、最小演算速度負荷検出フローを示す図である。
(S121)は、ＤＡＧ生成部１５で生成されたＤＡＧノードを読み込むステップである。
【０１２９】
(S122)は、(S121)で読み込まれた命令の自由度を検出するステップである。
(S123)は、(S121)で読み込まれた命令のサイクル毎の最小演算速度負荷を算出するステップである。ここで、自由度がまたがっていないサイクルの最小演算速度負荷は0とし、自由度がまたがっている最小演算速度負荷は、以下に示す[式３][式４]より求められる。
【０１３０】
最大演算使用可能時間
=命令ノードを、最小演算速度負荷を求めるサイクルに配置する場合に
演算時間として使用可能な最大の時間    [式３]
最小演算速度負荷 = 1 /最大演算使用可能時間      [式４]
次に、図２Ａに示した命令列Ｐ２の使用演算器数負荷と最小演算速度負荷を求めた場合の例を図１３に示す。
【０１３１】
図１３は、図２Ａに示した命令列Ｐ２から求められた使用演算器数負荷と最小演算速度負荷の具体例を示す図である。
【０１３２】
同図において命令ノードの自由度131は、図２Ａに示した命令列Ｐ２の自由度であり、図１０の結果と等しい。
【０１３３】
使用演算器数負荷132は、図２Ａに示した命令列Ｐ２の使用演算器数負荷である。
ここで、乗算器の使用演算器数負荷を例に挙げて説明する。
【０１３４】
乗算器を用いた命令は命令２(乗算)、命令３(乗算)、命令６(乗算)の３命令である。まず、命令２(乗算)の使用演算器数サイクル負荷を求める。命令２(乗算)の自由度がまたがっているサイクルは、サイクル１およびサイクル２である。したがって、命令２(乗算)のサイクル１およびサイクル２の使用演算器数サイクル負荷は1/2となる。サイクル３は自由度がまたがっていないため、サイクル３の使用演算器数サイクル負荷は0となる。同様に命令３(乗算)および命令６(乗算)の使用演算器数サイクル負荷を求めた結果、命令３(乗算)のサイクル１から３の使用演算器数サイクル負荷は1/3、命令６(乗算)のサイクル１の使用演算器数サイクル負荷は0、サイクル２およびサイクル３の使用演算器数サイクル負荷は1/2となる。これより、サイクル毎に使用演算器数サイクル負荷の総和を求めると、サイクル１は5/6、サイクル２は8/6、サイクル３は5/6となる。
【０１３５】
最小演算速度負荷133は、図２Ａに示した命令列Ｐ２の最小演算速度負荷である。
ここで、命令４(シフト)のサイクル３の最小演算速度負荷を例に挙げて説明する。
【０１３６】
命令４(シフト)をサイクル３に配置する場合の演算使用可能時間が最大となるのは、命令１(加算)および命令２(乗算)がサイクル２以前に行われており、サイクル３の先頭から命令４(シフト)の演算が可能な場合である。また、命令５(加算)および命令６(乗算)もサイクル３に配置される必要があるため、命令５(加算)および命令６(乗算)をサイクル３の最下端から下詰めスケジューリングを行った結果、すなわち命令５(加算)がcycle=3,offset=2、命令６(乗算)がcycle=3,offset=3に配置された場合に、命令４(シフト)に残された時間範囲が命令４(シフト)の演算使用可能時間となる。これより命令４(シフト)の演算使用可能時間は2となる。したがって、命令４(シフト)の最小演算速度負荷は1/2となる。
【０１３７】
次に、負荷削減命令配置時間検出ステップ(S35)について、図１４を用いて説明する。
図１４は、負荷削減命令配置時間検出フローを示す図である。
【０１３８】
(S141)は、使用演算器数の削減と演算処理速度に伴うコストの削減のどちらを優先させるか判定するステップである。
【０１３９】
(S142)は、(S141)で使用演算器数の削減を優先すると判定された場合に、使用演算器数を優先的に削減する配置時刻を検出するステップである。
【０１４０】
(S143)は、(S141)で演算処理速度に伴うコストの削減を優先すると判定された場合に、演算処理速度に伴うコストを優先的に削減する配置時刻を検出するステップである。
【０１４１】
ここで、使用演算器数を優先的に削減する配置時刻を検出するステップについて図１５を用いて、演算処理速度に伴うコストを優先的に削減する配置時刻を検出するステップについて図１６を用いて説明する。
【０１４２】
図１５は、使用演算器数を優先的に削減する配置時刻検出フローを示す図である。
(S151)は、スケジューリング対象となる命令列で使用される演算器を、目標演算器数リストに登録するステップである。ここで、目標演算器数リストには、資源制約の厳しい(１サイクル内で使用可能な演算器資源数の少ない)演算器や目標演算器数の小さい演算器など、優先的に使用演算器資源を削減する演算器から順にリストに登録されるものとする。
【０１４３】
(S152)は、(S151)の目標演算器数リストの先頭を読み込むステップである。ここで読み込まれた演算器を負荷削減対象演算器とする。
【０１４４】
(S153)は、負荷削減対象演算器の使用演算器数負荷が目標演算器数を超えるサイクルがあるか判定するステップである。
【０１４５】
(S154)は、(S153)で目標演算器数を超えるサイクルがないと判定された場合に、(S152)で読み込んだ演算器が、目標演算器数リストの最後のリストであるか判定するステップである。
【０１４６】
(S155)は、(S154)で最後のリストであると判定されなかった場合に、次のリストを読み込むステップである。
【０１４７】
(S156)は、(S153)で目標演算器数を超えるサイクルがあると判定された場合に、(S152)で読み込んだ演算器の使用演算器数負荷が目標演算器数を最も大きく超えているサイクルの使用演算器数負荷が削減されるように、各命令ノードの自由度を変更するステップである。
【０１４８】
(S157)は、(S156)で使用演算器負荷の削減が可能であったか判定するステップである。
(S158)は、(S157)で可能だと判定された場合に、(S156)で各命令ノードの自由度が変更されるため、負荷を再度計算しなおすステップで、再計算後(S152)に戻る。
【０１４９】
(S159)は、(S157)で可能だと判定されなかった場合に、使用演算器数負荷の値を目標演算器数に設定しなおすステップで、変更後(S152)に戻る。
【０１５０】
(S1510)は、(S153)で存在しないと判定された場合に、演算速度負荷を削減可能な演算器があるか判定するステップである。
【０１５１】
(S1511)は、(S1510)で演算速度負荷の削減が可能な演算器があると判定された場合に、演算速度負荷の削減が可能な演算器のうち消費電力が最も大きい演算器の演算速度負荷の削減を行うステップである。
【０１５２】
(S1512)は、(S1511)で各命令の自由度が変更されるため、負荷を再度計算しなおすステップで、再計算後(S152)に戻る。
【０１５３】
(S1513)は、(S1510)で演算速度負荷の削減が可能な演算器がないと判定された場合に、各命令の自由度から、演算速度負荷が最も小さくなるような命令配置時刻を求めるステップである。
【０１５４】
図１６は、演算処理速度に伴うコストを優先的に削減する配置時刻検出フローを示す図である。
【０１５５】
(S161)は、スケジューリング対象となる命令列で使用される演算器を、目標演算器数リストに登録するステップである。ここで、目標演算器数リストには、資源制約の厳しい(１サイクル内で使用可能な演算器資源数の少ない)演算器や目標演算器数の小さい演算器など、優先的に使用演算器資源を削減する演算器から順にリストに登録されるものとする。
【０１５６】
(S162)は、(S161)の目標演算器数リストの先頭を読み込むステップである。ここで読み込まれた演算器を負荷削減対象演算器とする。
【０１５７】
(S163)は、(S162)で読み込まれた演算器の演算速度負荷を削減可能な命令があるか判定するステップである。
【０１５８】
(S164)は、(S163)で演算速度負荷を削減可能な命令があると判定されなかった場合に、(S162)で読み込んだ演算器が、目標演算器数リストの最後のリストであるか判定するステップである。
【０１５９】
(S165)は、(S164)で最後のリストであると判定されなかった場合に、次のリストを読み込むステップである。
【０１６０】
(S166)は、(S163)で演算速度負荷を削減可能な命令があると判定された場合に、演算速度負荷の削減を行うステップである。
【０１６１】
(S167)は、(S166)で各命令ノードの自由度が変更されるため、負荷を再度計算しなおすステップで、再計算後(S162)に戻る。
【０１６２】
(S168)は、(S164)で最後のリストであると判定された場合に、再度目標演算器数リストの先頭を読み込むステップである。
【０１６３】
(S169)は、負荷削減対象演算器の使用演算器数負荷が目標演算器数を超えるサイクルがあるか判定するステップである。
【０１６４】
(S1610)は、(S169)で目標演算器数を超えるサイクルがないと判定された場合に、(S168)で読み込んだ演算器が、目標演算器数リストの最後のリストであるか判定するステップである。
【０１６５】
(S1611)は、(S1610)で最後のリストであると判定されなかった場合に、次のリストを読み込むステップである。
【０１６６】
(S1612)は、(S169)で目標演算器数を超えるサイクルがあると判定された場合に、(S158)で読み込んだ演算器の使用演算器数負荷が目標演算器数を最も大きく超えているサイクルの使用演算器数負荷が削減されるように、各命令ノードの自由度を変更するステップである。
【０１６７】
(S1613)は、(S1612)で使用演算器負荷の削減が可能であったか判定するステップである。
【０１６８】
(S1614)は、(S1613)で可能だと判定された場合に、(S1612)で各命令ノードの自由度が変更されるため、負荷を再度計算しなおすステップで、再計算後(S162)に戻る。
【０１６９】
(S1615)は、(S1613)で可能だと判定されなかった場合に、使用演算器数負荷の値を目標演算器数に設定しなおすステップで、変更後(S162)に戻る。
【０１７０】
(S1616)は、(S1610)で最後のリストであると判定された場合に、各命令の自由度から、演算速度負荷が最も小さくなるような命令配置時刻を求めるステップである。
【０１７１】
次に、(S156)(S1612)に示される使用演算器負荷の削減について、図１７を用いて説明する。
【０１７２】
図１７は、使用演算器負荷削減フローを示す図である。
(S171)は、負荷を削減するサイクル(目標演算器数を最も大きく超えているサイクル)において、負荷削減対象演算器を使用する命令ノードを抽出するステップである。
【０１７３】
(S172)は、(S171)で抽出された命令ノードのうち、移動可能な命令(ASAP時刻サイクルとALAP時刻サイクルが異なる命令)があるか判定するステップである。
【０１７４】
(S173)は、(S172)で移動可能な命令ノードがあると判定された場合に、移動対象命令の選出を行うステップである。ここでは、(S171)で抽出された命令ノードのうち、負荷削減対象サイクルよりも前のサイクルに配置される可能性のある命令がある場合(ASAP時刻のサイクル<負荷削減対象サイクルの場合)、以下の順序で当てはまる命令を検出し、移動対象命令とする。
【０１７５】
(優先１)最も深さが浅い命令
(優先２)最も高さが高い命令
(優先３)最も親ノードの数が少ない命令
(優先４)最も子ノードの数が多い命令
(優先５)最もＤＡＧノードIDの小さい命令
また、負荷削減対象サイクルよりも前のサイクルに配置される可能性のある命令がない場合(ASAP時刻のサイクル==負荷削減対象サイクルの場合)、以下の順序で当てはまる命令を検出し、移動対象命令とする。
【０１７６】
(優先１)最も高さが低い命令
(優先２)最も深さが深い命令
(優先３)最も子ノードの数が少ない命令
(優先４)最も親ノードの数が多い命令
(優先５)最もＤＡＧノードIDの大きい命令
(S174)は、(S173)で選出された移動対象命令の自由度を変更ステップである。ここでは、移動対象命令が負荷削減対象サイクルよりも前のサイクルに配置される可能性がある場合(ASAP時刻のサイクル<負荷削減対象サイクルの場合)、移動対象命令のALAP時刻を、負荷削減対象サイクルの１つ手前のサイクルの、サイクル終了時刻から命令ノードの演算に必要な時間を引いた時刻に変更する。また、移動対象命令が負荷削減対象サイクルよりも前のサイクルに配置される可能性がない場合(ASAP時刻サイクル<負荷削減対象サイクルの場合)、移動対象命令のASAP時刻を、負荷削減対象サイクルの次のサイクルの先頭時刻に変更する。
【０１７７】
(S175)は、(S174)で移動対象命令の自由度が変更されたことに伴い、全命令ノードの自由度を変更するステップである。
【０１７８】
(S176)は、(S175)で変更された自由度において資源制約を満たすことが可能であるか検出するステップである。
【０１７９】
(S177)は、(S176)で資源制約を満たすことが不可能であると判定された場合に、(S174)および(S175)で変更した自由度を元に戻すステップである。
【０１８０】
(S178)は、(S176)で資源制約を満たすことが不可能であると判定された場合に、再度移動対象命令の自由度を変更するステップである。ここでは、移動対象命令が負荷削減対象サイクルよりも前のサイクルに配置される可能性がある場合(ASAP時刻サイクル<負荷削減対象サイクルの場合)、移動対象命令のASAP時刻を負荷削減対象サイクルの次のサイクルの先頭時刻に変更する。また、負荷削減対象サイクルよりも前のサイクルに配置される可能性がない場合(ASAP時刻サイクル<負荷削減対象サイクルの場合)、移動対象命令のALAP時刻を負荷削減対象サイクルの、サイクル終了時刻から命令ノードの演算に必要な時間を引いた時刻に変更する。
【０１８１】
(S179)は、(S178)で再度、移動対象命令の自由度を変更したことに伴い、全命令ノードの自由度を変更するステップである。
【０１８２】
(S1710)は、(S174)および(S175)、または(S178)および(S179)で自由度を変更することにより負荷削減が成功したとするステップである。
【０１８３】
(S1711)は、自由度を変更することが不可能であったことにより、負荷削減が不成功であったとするステップである。
【０１８４】
次に、(S1511)(S166))に示される演算速度負荷の削減について、図１８を用いて説明する。
【０１８５】
図１８は、演算速度負荷削減フローを示す図である。
(S181)は、演算速度負荷削減の対象となる演算器を使用する命令ノードの最小演算速度負荷の抽出を行うステップである。
【０１８６】
(S182)は、目標演算速度負荷の算出を行うステップである。ここで、目標演算速度負荷は、演算速度負荷削減の対象となる演算器を使用する命令ノードのそれぞれの最小演算速度負荷の最小値の中で、最も大きい最小演算速度負荷と等しいものとする。これは、同じ演算を行う命令は演算器を共有し、なおかつコストの小さい演算器を使用するためである。
【０１８７】
同じ演算器を使用する複数の命令が別サイクルに配置された場合に、同じ演算器を共有しようとするが、演算にかかる時間が異なる場合、演算器が異なるため共有化できない。したがって、ある命令においてコストの小さい低速に演算をする演算器を用いることが可能であったとしても、別の命令でコストの高い高速に演算をする演算器を用いなければならない場合、それらの命令で演算器を共有するには、コストの高い高速に演算をする演算器を用いなければならない。したがって、(S182)では、はじめから同じ演算を行う命令に対しては演算器を共有するものとし、どの命令にも使用可能な速さの演算器を目標演算速度として負荷を求める。
【０１８８】
例えば、ある命令(命令１とする)においてサイクル１での最小演算速度負荷が1/3、サイクル２での最小演算速度負荷が1/4とし、同じ演算器を使用する別の命令(命令２とする)においてサイクル１での最小演算速度負荷が1/5、サイクル２での最小演算速度負荷が1/3とすると、命令それぞれの最小演算速度負荷の最小値は、命令１が1/4、命令２が1/５となる。したがって目標演算速度負荷はこれらの最大値である1/4となる。
【０１８９】
また、ある命令(命令３とする)においてサイクル１での最小演算速度負荷が1/5、サイクル２での最小演算速度負荷が1/4とし、同じ演算器を使用する別の命令(命令４とする)においてサイクル１での最小演算速度負荷が1/5、サイクル２での最小演算速度負荷が1/3とすると、命令それぞれの最小演算速度負荷の最小値は、命令３、命令４共に1/5となる。したがって目標演算速度負荷は1/5となるが、目標演算器速度で配置できるサイクルは命令３、命令４ともにサイクル１のみである。このように、同じ演算器を使用する命令において、目標演算器速度で配置できるサイクルが各命令に１サイクルずつしかなく、それが同一サイクルとなる場合は、目標演算速度負荷は目標演算速度負荷を分数で表し、分母に１を加えた値に変更する。したがって、上記例(命令３と命令４の例)の場合、目標演算器速度負荷は1/4となる。
【０１９０】
(S183)は、演算速度負荷削減の対象となる演算器を使用する命令ノードを読み込むステップである。
【０１９１】
(S184)は、目標演算速度負荷で実行することが可能なサイクルの検出を行うステップである。ここで、目標演算速度負荷で実行可能なサイクルとは、最小演算速度負荷が目標演算速度負荷以下であるサイクルである。１命令で目標演算速度負荷で実行可能なサイクルが複数あってもかまわない。(S182)での命令１と命令２の例では、命令１ではサイクル２、命令２ではサイクル１となり、命令３と命令４の例では、命令３ではサイクル１および２、命令４ではサイクル２となる。
【０１９２】
(S185)は、(S184)で検出されたサイクルに命令ノードを配置するとして、自由度を変更するステップである。
【０１９３】
(S186)は、(S184)で自由度が変更されたことに伴い、それ以外の命令の自由度を変更するステップである。
【０１９４】
(S187)は、自由度の変更後、資源制約を満たすことが可能であるか判定するステップである。
【０１９５】
(S188)は、(S187)で可能であると判定された場合に、演算速度負荷削減の対象となる演算器を使用する命令ノードがほかにあるか判定するステップである。(S188)であると判定された場合は、演算速度負荷削減の対象となる演算器を使用するすべての命令ノードで(S183)から(S188)を繰り返し、演算速度負荷削減の対象となる演算器を使用するすべての命令ノードで配置可能であった場合、終了する。
【０１９６】
(S189)は、(S187)で可能であると判定されなかった場合に、目標演算速度負荷を変更するステップである。ここで、変更された目標演算速度負荷は、変更前の目標演算速度負荷を分数で表した場合に、分母に１加算したものと等しいものとする。
【０１９７】
(S1810)は、(S184)(S185)で既に変更された自由度を元に戻すステップである。ここで自由度を戻した後、(S189)で変更された目標演算速度負荷を用いて、再度自由度の変更をやりなおす。
【０１９８】
次に、図２Ａに示した命令列Ｐ２から求められた使用演算器負荷(S132)および最小演算速度負荷(S133)を用いて、負荷削減命令配置時刻を検出する過程を図１９および図２０を用いて説明する。
【０１９９】
図１９Ａ〜図１９Ｅは、使用演算器数の削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。ここでは、乗算器、加算器、シフトの順に、使用演算器数および演算速度に伴うコストが優先的に削減されるように指定されているものとする。
【０２００】
図１９Ａは、図２Ａに示した命令列Ｐ２の自由度および演算器負荷を示した図で、図１３と同様である。
【０２０１】
最初に、各演算器の目標演算器数を求める。乗算器の目標演算器数を例に挙げて説明すると、乗算器を使用する命令は命令２(乗算)、命令３(乗算)、命令６(乗算)の3命令であり、スケジューリング時間範囲は３であるため、乗算器の目標使用演算器数を[式１]より求めると、
ceil (3 / 3) = １
となる。同様にして、加算器とシフト演算器の目標演算器数を求めると、加算器の目標演算器数は１、シフト演算器の目標演算器数は１となる。
【０２０２】
次にそれぞれの使用演算器負荷に着目すると、使用演算器数および演算速度に伴うコストが優先的に削減されるように指定されている乗算器において、サイクル２の乗算器の使用演算器負荷が目標使用演算器数よりも大きいことがわかる。このため、サイクル２に配置される可能性のある乗算器を用いる命令命令２(乗算)、命令３(乗算)、命令６(乗算)の中から移動対象命令を選び、自由度を変更することにより、サイクル２の乗算器の使用演算器数を目標使用演算器数以下にする。ここでは、上記ステップ(S173)の優先順序により移動対象命令は、深さが最も浅く、高さが最も高い命令２(乗算)となる。
【０２０３】
図１９Ｂは、移動対象命令である命令２(乗算)を、サイクル２の乗算器の使用演算器数を目標使用演算器数以下となるように、自由度内で移動させた結果である。この結果、命令２(乗算)はサイクル1に配置されるよう自由度が再設定されている。これにより、乗算器の使用演算器数負荷は、サイクル１で9/6、サイクル２で5/6、サイクル３で5/6となっており、サイクル１の使用演算器数負荷が目標使用演算器数よりも大きいことがわかる。このため、サイクル１に配置される可能性のある乗算器を用いる命令２(乗算)、命令３(乗算)の中から移動対象命令を選び、自由度を変更することにより、サイクル１の乗算器の使用演算器数を目標使用演算器数以下にする。ここでは、上記ステップ(S173)の優先順序により移動対象命令は、配置可能性のあるサイクル数が複数ある(ASAP時刻サイクルとALAP時刻サイクルの異なる)命令３(乗算)となる。
【０２０４】
図１９Ｃは、移動対象命令である命令３(乗算)を、サイクル１の乗算器の使用演算器数を目標使用演算器数以下となるように、自由度内で移動させた結果である。この結果、命令３(乗算)はサイクル２以降に配置されるよう自由度が再設定されている。これにより、乗算器の使用演算器数負荷は、サイクル１、サイクル２、サイクル３でともに1となっており、目標使用演算器数以下であることがわかる。また、乗算器以外の演算器においても、使用演算器数負荷は目標演算器数以下である。これより、すべての使用演算器負荷が目標演算器数より小さくなったため、次に、演算速度に伴うコストが最小となる配置時刻を自由度内から求める。使用演算器数および演算速度に伴うコストが優先的に削減されるように指定されている乗算器の最小演算速度負荷は命令２(乗算)、命令３(乗算)、命令６(乗算)においてすべて1/5である。したがって、目標演算速度負荷は1/5となる。これより、演算速度負荷が1/5になるように、命令２(乗算)、命令３(乗算)、命令６(乗算)の配置時刻を自由度内より求める。
【０２０５】
図１９Ｄは、命令２(乗算)、命令３(乗算)、命令６(乗算)の演算速度負荷が1/5となるように、自由度内から配置時刻を求めた結果である。同図中の黒丸印が配置時刻を示す。命令２(乗算)、命令３(乗算)、命令６(乗算)の配置時刻が定められたことにより、ほかの演算器を用いる命令の自由度も影響を受ける。再度演算器負荷を求めた結果、使用演算器負荷は目標演算器数以下であるため、乗算器の次に使用演算器数および演算速度に伴うコストが優先的に削減されるように指定されている加算器について、演算速度に伴うコストが最小となる配置時刻を自由度内から求める。加算器の最小演算速度負荷は命令１(加算)では1/5、命令５(加算)では1/4である。したがって、目標演算速度負荷は1/4となる。これより、演算速度負荷が1/4になるように、命令１(加算)、命令５(加算)、の配置時刻を自由度内より求める。
【０２０６】
図１９Ｅは、命令１(加算)、命令５(加算)、の演算速度負荷が1/4となるように、自由度内から配置時刻を求めた結果である。同図中の黒丸印が配置時刻を示す。命令１(加算)、命令５(加算)の配置時刻が定められたことにより、ほかの演算器を用いる命令の自由度も影響を受ける。この結果、命令３(乗算)の配置時刻も決定されており、すべての命令において配置時刻が決定された。
【０２０７】
図２０Ａ〜図２０Ｃは、演算速度に伴うコストの削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。ここでも、乗算器、加算器、シフトの順に、使用演算器数および演算速度に伴うコストが優先的に削減されるように指定されているものとする。
【０２０８】
図２０Ａは、図２Ａに示した命令列Ｐ２の自由度および演算器負荷を示した図で、図１３と同様である。
【０２０９】
まず、使用演算器数および演算速度に伴うコストが優先的に削減されるように指定されている乗算器の最小演算速度負荷に着目する。乗算器の最小演算速度負荷は、命令２(乗算)、命令３(乗算)、命令６(乗算)においてすべて1/5である。したがって、目標演算速度負荷は1/5となる。これより、演算速度負荷が1/5になるように、命令２(乗算)、命令３(乗算)、命令６(乗算)の配置時刻を自由度内より求める。
【０２１０】
図２０Ｂは、命令２(乗算)、命令３(乗算)、命令６(乗算)の演算速度負荷が1/5となるように、自由度内から配置時刻を求めた結果である。同図中の黒丸印が配置時刻を示す。命令２(乗算)、命令３(乗算)、命令６(乗算)の配置時刻が定められたことにより、ほかの演算器を用いる命令の自由度も影響を受けるため、再度負荷を検出する。この結果を用いて、乗算器の次に使用演算器数および演算速度に伴うコストが優先的に削減されるように指定されている加算器について、演算速度に伴うコストが最小となる配置時刻を自由度内から求める。加算器の最小演算速度負荷は命令１(加算)、命令５(加算)においてすべて1/5である。したがって、目標演算速度負荷は1/5となる。これより、演算速度負荷が1/5になるように、命令１(加算)、命令５(加算)、の配置時刻を自由度内より求める。しかしながら、命令１(加算)、命令５(加算)の演算速度負荷をともに1/5とするような配置時刻を求めることは不可能であるため、目標演算速度負荷を、現在の目標演算器負荷の分母に１を加算した1/４に変更し、再度演算速度負荷が1/4になるように、命令１(加算)、命令５(加算)、の配置時刻を自由度内より求める。
【０２１１】
図２０Ｃは、命令１(加算)、命令５(加算)、の演算速度負荷が1/4となるように、自由度内から配置時刻を求めた結果である。同図中の黒丸印が配置時刻を示す。命令１(加算)、命令５(加算)の配置時刻が定められたことにより、ほかの演算器を用いる命令の自由度も影響を受ける。この結果、命令３(乗算)の配置時刻も決定されており、すべての命令において配置時刻が決定された。
【０２１２】
次に、図２Ａに示した命令列Ｐ２を、使用演算器数の削減を優先した場合と、演算速度に伴うコストの削減を優先した場合のスケジューリング結果を図２１を用いて説明する。
【０２１３】
図２１Ａは、図２Ａに示した命令列Ｐ２を、使用演算器数の削減を優先した場合と、演算速度に伴うコストの削減を優先した場合のスケジューリング結果を示す図である。(図２Ａに示した命令列Ｐ２を、使用演算器数の削減を優先した場合と、演算速度に伴うコストの削減を優先した場合のスケジューリング結果はここでは等しくなっている。)
図２１Ａは、図２Ａに示した命令列Ｐ２を、使用演算器数の削減を優先した場合と、演算速度に伴うコストの削減を優先した場合のスケジューリング結果を表すアセンブラコードである。図２１Ａ中に示される;;(PARA)はサイクルの区切りを示すものである。つまり、PARAではさまれた命令は、同一サイクル内で実行されるものとする。図２１Ａの各命令のオペランドは、仮想レジスタから実レジスタに書き換えられている。また、命令４および命令５中のオペランドwire11は、演算結果を命令間でレジスタに格納することなく同一サイクル内で引き渡すことを意味する。これらの書き換えとサイクル区切りマークの付加は命令挿入部１７による。
【０２１４】
図２１Ｂは、図２Ａに示した命令列Ｐ２を、使用演算器数の削減を優先した場合と、演算速度に伴うコストの削減を優先した場合のスケジューリング結果のイメージ図である。
【０２１５】
図２１Ｂで示されるように、サイクル1では命令１(加算)の加算命令と命令２(乗算)の乗算命令が並列実行される。また、サイクル2では命令４(シフト)のシフト命令と命令５(加算)の加算命令が逐次的に実行され、それと並列に命令３(乗算)の乗算命令が実行される。また、サイクル３では命令６(乗算)の乗算命令のみが実行される。このように、命令２(乗算)、命令３(乗算)、命令６(乗算)の乗算命令はそれぞれ異なるサイクルに配置されるため、再利用が可能である。また、命令１(加算)、命令５(加算)の加算命令もそれぞれ異なるサイクルに配置されるため、再利用が可能である。以上より、必要とされる演算器の数は、乗算器が1つ、加算器が1つ、シフト演算器が3つとなる。
【０２１６】
図２２は、図２１Ａのスケジューリング結果をもとにして生成された回路を示すブロック図である。この回路は、乗算器、シフト演算器、加算器をそれぞれ１つずつ備えている。スケジューリングにおいて別サイクルに配置された命令２(乗算)、命令３(乗算)、命令６(乗算)の乗算命令は同じ乗算器を利用し、命令１(加算)、命令５(加算)の加算命令は同じ加算器を利用していることがわかる。また、命令４(シフト)のシフト命令の結果は同一サイクルに配置された命令５(加算)の入力値となっているため、レジスタには格納されず、直接加算器の入力値となり、レジスタが１つ削減される。
【０２１７】
以上のように、本発明の実施の形態によれば、ユーザが指定した実行性能を満たし、なおかつ演算器(種類別)の使用数および演算処理速度に伴うコストが平均的に小さくなるようスケジューリングを行うため、演算器の再利用性およびコストの小さい演算器の使用率が向上し、回路面積および消費電力の削減が可能となる。
【産業上の利用可能性】
【０２１８】
本発明の命令スケジューリング方法、および装置によれば、ユーザが指定した実行性能を満たす範囲で演算器(種類別)の使用数および演算速度に伴うコストが平均的に小さくなるようスケジューリングを行い、演算器の再利用性およびコストの小さい演算器の使用率を向上させることで回路面積および消費電力の削減することが可能であり、（ソフトウェア言語処理分野で有用である。
【図面の簡単な説明】
【０２１９】
【図１】実施の形態における高位合成コンパイラの構成を示すブロック図である。
【図２Ａ】スケジューリング対象となる命令列Ｐ２の一例を示す図である。
【図２Ｂ】ＤＡＧ生成部で生成されるＤＡＧの具体例を示した図である。
【図３】命令配置時刻検出処理の詳細なフローを示した図である。
【図４】スケジューリング時間範囲検出ステップの検出フローを示す図である。
【図５】自由度検出ステップでの検出フローを示す図である。
【図６】SAP時刻検出フローを示す図である。
【図７】ALAP時刻検出フローを示す図である。
【図８】ASAP時刻を示す説明図である。
【図９】ALAP時刻を示す説明図である。
【図１０】各命令の配置の自由度を示す説明図である。
【図１１】使用演算器数負荷の検出フローを示す図である。
【図１２】最小演算速度負荷検出フローを示す図である。
【図１３】使用演算器数負荷と最小演算速度負荷の具体例を示す図である。
【図１４】負荷削減命令配置時間検出フローを示す図である。
【図１５】使用演算器数を優先的に削減する配置時刻検出フローを示す図である。
【図１６】演算処理速度に伴うコストを優先的に削減する配置時刻検出フローを示す図である。
【図１７】使用演算器負荷削減フローを示す図である。
【図１８】演算速度負荷削減フローを示す図である。
【図１９Ａ】使用演算器数の削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。
【図１９Ｂ】使用演算器数の削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。
【図１９Ｃ】使用演算器数の削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。
【図１９Ｄ】使用演算器数の削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。
【図１９Ｅ】使用演算器数の削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。
【図２０Ａ】演算速度に伴うコストの削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。
【図２０Ｂ】演算速度に伴うコストの削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。
【図２０Ｃ】演算速度に伴うコストの削減を優先した場合の、負荷削減命令配置時刻を検出する過程の具体例を示す図である。
【図２１Ａ】使用演算器数の削減を優先した場合、および演算速度に伴うコストの削減を優先した場合のスケジューリング結果を示す図である。
【図２１Ｂ】スケジューリング結果
【図２２】生成された回路を示すブロック図である。
【符号の説明】
【０２２０】
１  高位合成コンパイラ
１０  構文解析部
１１  中間コード生成部
１２  スケジューリング部
１３  ＶＨＤＬ生成部
１４  実行性能読みこみ部
１５  ＤＡＧ生成部
１６  命令配置時刻検出部
１７  命令挿入部
【図１】
2006139553.tif 000003
【図２Ａ】
2006139553.tif 000004
【図２Ｂ】
2006139553.tif 000005
【図３】
2006139553.tif 000006
【図４】
2006139553.tif 000007
【図５】
2006139553.tif 000008
【図６】
2006139553.tif 000009
【図７】
2006139553.tif 000010
【図８】
2006139553.tif 000011
【図９】
2006139553.tif 000012
【図１０】
2006139553.tif 000013
【図１１】
2006139553.tif 000014
【図１２】
2006139553.tif 000015
【図１３】
2006139553.tif 000016
【図１４】
2006139553.tif 000017
【図１５】
2006139553.tif 000018
【図１６】
2006139553.tif 000019
【図１７】
2006139553.tif 000020
【図１８】
2006139553.tif 000021
【図１９Ａ】
2006139553.tif 000022
【図１９Ｂ】
2006139553.tif 000023
【図１９Ｃ】
2006139553.tif 000024
【図１９Ｄ】
2006139553.tif 000025
【図１９Ｅ】
2006139553.tif 000026
【図２０Ａ】
2006139553.tif 000027
【図２０Ｂ】
2006139553.tif 000028
【図２０Ｃ】
2006139553.tif 000029
【図２１Ａ】
2006139553.tif 000030
【図２１Ｂ】
2006139553.tif 000031
【図２２】
2006139553.tif 000032