命令スケジューリング装置、命令スケジューリング方法および命令スケジューリングプログラム
【課題】 処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成することができる命令スケジューリング装置を提供すること。
【解決手段】 依存関係のある一連の命令を１つの命令群として命令ブロック内の命令を複数の命令群に分割する命令群分割部２と、各命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、各命令群に対して、命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定部３と、命令群別優先度の高い命令群から順に、該命令群に含まれる命令を命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち実機によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を命令単位優先度に基づいて配置する命令スケジューリング部４とを備える。
【解決手段】 依存関係のある一連の命令を１つの命令群として命令ブロック内の命令を複数の命令群に分割する命令群分割部２と、各命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、各命令群に対して、命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定部３と、命令群別優先度の高い命令群から順に、該命令群に含まれる命令を命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち実機によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を命令単位優先度に基づいて配置する命令スケジューリング部４とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置に実行させる命令をスケジューリングして命令列を生成する命令スケジューリング装置に関し、特に、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令をスケジューリングする命令スケジューリング装置、命令スケジューリング方法および命令スケジューリングプログラムに関する。
【背景技術】
【０００２】
一般的に、命令スケジューリング装置は、実行時間をより短縮する命令列を生成するため、命令を効率よく配置するスケジューリングを行って命令列を生成する。このような命令スケジューリング装置として、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令をスケジューリングするものが知られている。
【０００３】
処理サイクル毎に複数の命令を並列に実行可能な情報処理装置としては、例えば、命令パイプラインを採用したものがよく知られている。命令パイプラインを採用した情報処理装置は、命令が分割された複数のステージに対して、各ステージを処理する処理部を有する。各処理部は、前のステージの出力を入力として担当するステージを処理し、その結果を次のステージに出力する。各処理部が連続する命令の各ステージを並行して実行することにより、複数の命令を並列に実行する。
【０００４】
また、命令パイプラインを採用した情報処理装置において、さらなる性能向上のため、例えば、ＶＬＩＷ（Very Long Instruction Word）を採用したものも知られている。ＶＬＩＷを採用した情報処理装置は、並列実行可能な複数の命令が１つに記述された命令をパイプラインで実行する。
【０００５】
このような処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に対応した命令スケジューリング装置としては、命令ブロック毎に、命令の依存関係がノードおよびエッジで表されたＤＡＧ（Directed Acyclic Graph：無閉路有向グラフ）を構築し、ノード間の依存関係に基づいてノードの優先度を計算するものがある。そして、このような命令スケジューリング装置は、優先度の高いノードから順に、依存関係がない命令を並列実行可能であるとみなして並列に配置しながら全命令をスケジューリングする（例えば、非特許文献１および特許文献１参照）。
【０００６】
また、他のこのような命令スケジューリング装置として、１つ以上の命令からなる命令グループを生成し、並列に実行可能な命令グループ同士を対応付け、命令グループごとに、対応付けられた他の命令グループとの入れ替えまたは発行繰り上げを判断して、全体としての総実行時間を短縮するものがある（例えば、特許文献２参照）。
【０００７】
また、さらに他のこのような命令スケジューリング装置として、依存関係のある一連の命令を命令群とし、命令群毎に他の命令群とのコンフリクトを無視して命令スケジューリングを行って配置データを生成した後、複数の命令群の配置データをコンフリクトを解消するよう調整して合成するものがある（例えば、特許文献３参照）。
【０００８】
また、さらに他のこのような命令スケジューリング装置として、１つのレジスタの第１の部分にアクセスする命令と、同一のレジスタの第２の部分をアクセスする命令を同一のサイクルにスケジューリングするものがある（例えば、特許文献４参照）。また、この特許文献４に記載の命令スケジューリング装置は、同一のサイクルにおいて、複数の命令が１つのレジスタの同一の部分にアクセスする場合には、命令の種類毎に設定された優先度に基づいて優先度の高い命令を選択する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】中田育男著「コンパイラの構成と最適化」朝倉書店、1999年9月20日、ｐｐ．358−362
【特許文献】
【００１０】
【特許文献１】特開平３−１３５６３０号公報
【特許文献２】特開平６−２８３２４号公報
【特許文献３】特開２００２−２６８８９５号公報
【特許文献４】特開２０００−２２２２０９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、非特許文献１および特許文献１に記載されたものは、優先度の高い命令から順に、依存関係がないものを並列に配置し、情報処理装置のアーキテクチャに左右される並列実行可能な命令の組合せおよび数を考慮せずに命令を並べ替える。そのため、特許文献１および非特許文献１に記載されたものは、実機で並列に実行できない命令を並列に配置した命令列を生成する場合がある。したがって、特許文献１および非特許文献１に記載されたものは、生成した命令列を実機に実行させると、１つの処理を実行するための一連の命令の間で、依存関係のない他の命令を実行することになり、１つの処理の完了までの時間を遅延させる可能性があるという課題があった。
【００１２】
また、特許文献２に記載されたものは、１つの処理を実行するための一連の命令の依存関係を考慮せずに命令グループを生成している。このため、特許文献２に記載されたものは、１つの処理を実行するための一連の命令の間に、並列実行可能な他の命令を挿入してしまい、この１つの処理の完了を遅延させる可能性があるという課題があった。
【００１３】
また、特許文献３に記載されたものは、複数の命令群の配置データのコンフリクトを調整する際に、いったん配置した命令列の処理サイクル数を延長する場合があり、１つの処理の完了を遅延させる可能性があるという課題があった。
【００１４】
また、特許文献４に記載されたものは、命令の種類毎に設定された優先度に基づいて命令スケジューリングを行うとき、命令間の依存関係に関わらず優先度の高いものを選択する。このため、特許文献４に記載されたものは、１つの処理を実行するための一連の命令の間に、これらの一連の命令とは依存関係のない他の命令を配置する場合があり、１つの処理の完了を遅延させる可能性があるという課題があった。
【００１５】
また、これらの特許文献１〜４に記載されたものは、１つの処理の完了を遅延させる命令列では、この処理に必要な中間結果を保持するレジスタを長時間必要とするという課題があった。
【００１６】
ここで、これらの関連技術により生成される命令列の一例を用いて、上述の課題の具体例について図２１〜図２２を参照して説明する。
【００１７】
図２１（ａ）はソースコードを表している。このソースコードは、x[j+0]およびx[j+1]の互いに独立した処理によって構成されている。図２１（ｂ）は、（ａ）に示したソースコードから生成される中間言語の命令列である。
【００１８】
図２２（ａ）は、上述の関連技術によって、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に対して、x[j+0]およびx[j+1]の処理に対応する中間言語がスケジューリングされた命令列の一例である。なお、この情報処理装置では、同一の処理サイクルで並列に実行できる命令には次のような制約があるものとする。
・ロード命令（ｌｄ）同士は並列に実行できない。
・ストア命令（ｓｔ）同士は並列に実行できない。
・ロード命令およびストア命令は並列に実行できない。
・上記以外の組合せの命令は２命令並列に実行できる。
【００１９】
また、この情報処理装置は、各命令の実行に以下のサイクル数を必要するものとする。
・ロード命令の完了までに３サイクル
・その他の命令の完了までに1サイクル
図２２（ａ）の命令列では、x[j+0]の処理に関する一連の命令の間にx[j+1]に関する命令の一部が挿入されている。したがって、図２２（ａ）の命令列は、x[j+0]の処理開始から完了までに１４サイクルを要している。
【００２０】
これに対して、図２２（ｂ）に、x[j+0]に対応する命令のみをスケジューリングした場合の命令列を示す。図２２（ｂ）の命令列では、x[j+0]の処理開始から完了までに要する時間は１２サイクルである。このように、上述の関連技術により生成された命令列の一例では、x[j+0]の処理の完了を２サイクル遅延させている。
【００２１】
また、この遅延に伴って、上述の関連技術により生成された命令列の一例は、x[j+0]の処理に必要なレジスタｒ１５を解放可能とするタイミングを遅延させており、レジスタｒ１５をより長期間必要とする命令列となっている。
【００２２】
本発明は、上述の課題を解決するためになされたもので、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成することができる命令スケジューリング装置を提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明の命令スケジューリング装置は、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割手段と、前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定手段と、前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリング手段と、を備える。
【００２４】
また、本発明の命令スケジューリング方法は、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令をスケジューリングする命令スケジューリング装置が、前記複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割ステップと、前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定ステップと、前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリングステップと、を実行する。
【００２５】
また、本発明の命令スケジューリングプログラムは、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令をスケジューリングする命令スケジューリング装置に、前記複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割ステップと、前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定ステップと、
前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリングステップと、を実行させる。
【発明の効果】
【００２６】
本発明は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成することができる命令スケジューリング装置を提供することができる。
【図面の簡単な説明】
【００２７】
【図１】本発明の第１の実施の形態としての命令スケジューリング装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態としての命令スケジューリング装置の動作を示すフローチャートである。
【図３】本発明の第２の実施の形態としての命令スケジューリング装置の構成を示すブロック図である。
【図４】本発明の第２の実施の形態において構築されるＤＡＧの一例を説明する模式図である。
【図５】本発明の第２の実施の形態において分割される部分ＤＡＧの一例を説明する模式図である。
【図６】本発明の第２の実施の形態において分割される部分ＤＡＧの他の一例を説明する模式図である。
【図７】本発明の第２の実施の形態において命令単位優先度が設定された部分ＤＡＧの一例を説明する模式図である。
【図８】本発明の第２の実施の形態において命令単位優先度が設定された部分ＤＡＧの他の一例を説明する模式図である。
【図９】本発明の第２の実施の形態としての命令スケジューリング装置の動作を示すフローチャートである。
【図１０】本発明の第２の実施の形態としての命令スケジューリング装置の命令群別優先度の設定動作を示すフローチャートである。
【図１１】本発明の第２の実施の形態としての命令スケジューリング装置によって生成される命令列の一例を説明する図である。
【図１２】本発明の第２の実施の形態としての命令スケジューリング装置によって生成される命令列と関連技術によって生成される命令列とを比較する図である。
【図１３】本発明の第３の実施の形態としての命令スケジューリング装置の構成を示すブロック図である。
【図１４】本発明の第３の実施の形態において２段階優先度が設定された部分ＤＡＧの一例を説明する模式図である。
【図１５】本発明の第３の実施の形態において２段階優先度が設定された部分ＤＡＧの他の一例を説明する模式図である。
【図１６】本発明の第３の実施の形態において統合された統合ＤＡＧの一例を説明する模式図である。
【図１７】本発明の第３の実施の形態としての命令スケジューリング装置の動作を示すフローチャートである。
【図１８】本発明の第３の実施の形態としての命令スケジューリング装置の命令スケジューリング動作を示すフローチャートである。
【図１９】本発明の第４の実施の形態としての命令スケジューリング装置の構成を示すブロック図である。
【図２０】本発明の第４の実施の形態におけるＤＡＧに対応付けられた情報を説明する図である。
【図２１】本発明の各実施の形態におけるソースコードおよび中間言語を説明する図である。
【図２２】関連技術の命令スケジューリング装置によって生成される命令列の一例を説明する図である。
【発明を実施するための形態】
【００２８】
以下、本発明の第１の実施の形態について、図面を参照して詳細に説明する。
【００２９】
本発明の第１の実施の形態としての命令スケジューリング装置１の構成を図１に示す。
【００３０】
図１において、命令スケジューリング装置１は、機能ブロックとして、命令群分割部２と、優先度設定部３と、命令スケジューリング部４と、を備える。
【００３１】
ここで、命令スケジューリング装置１は、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、記憶装置とを備えた汎用的なコンピュータ装置によって構成されている。また、命令群分割部２と、優先度設定部３と、命令スケジューリング部４とは、プログラムモジュールとして記憶装置に記憶され、ＣＰＵによってＲＡＭに読み込まれて実行される回路として構成される。
【００３２】
命令群分割部２は、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置９９（図示せず）に実行させる命令列を命令ブロック単位で読み込み、命令ブロックを構成する命令の依存関係を分析する。そして、命令群分割部２は、依存関係のある一連の命令を１つの命令群として、命令ブロックを複数の命令群に分割する。
【００３３】
優先度設定部３は、各命令群内の各命令に対して、該命令群における処理順序の優先度を表す命令単位優先度を設定する。さらに、優先度設定部３は、各命令群に対して、命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する。
【００３４】
ここで、優先度設定部３は、例えば、その命令の結果に依存する全ての命令の処理を完了するまでの時間(処理サイクル数)に基づいて命令単位優先度を設定してもよい。また、優先度設定部３は、例えば、命令群内の命令に設定された命令単位優先度のうち最も高いものに基づいて命令群別優先度を設定してもよい。
【００３５】
命令スケジューリング部４は、命令群別優先度の高い命令群から順に、該命令群に含まれる命令を命令単位優先度に基づいてスケジューリングする。また、命令スケジューリング部４は、スケジューリングした命令群内の命令が配置された処理サイクルのうち、情報処理装置９９によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する。
【００３６】
以上のように構成された命令スケジューリング装置１の動作について、図２を用いて説明する。
【００３７】
まず、命令群分割部２によって、命令ブロック内の命令が、依存関係のある一連の命令をそれぞれ表す複数の命令群に分割される（ステップＳ１）。
【００３８】
次に、優先度設定部３によって、命令群毎に、命令群内の各命令に命令単位優先度が設定されるとともに、各命令群に命令群別優先度が設定される（ステップＳ２）。
【００３９】
次に、命令スケジューリング部４によって、命令群別優先度が最も高い命令群に含まれる命令が、命令単位優先度に基づいてスケジューリングされる（ステップＳ３）。ここで、命令スケジューリング部４は、この命令群内の命令で、情報処理装置９９で並列に実行可能な命令があれば並列に配置しながらこれらの命令をスケジューリングする。
【００４０】
次に、命令スケジューリング部４によって、ステップＳ３で生成された命令列の処理サイクルのうち、情報処理装置９９で他の命令群の命令を実行可能な処理サイクルがあるか否かが判断される（ステップＳ４）。
【００４１】
ここで、他の命令群の命令を実行可能な処理サイクルがあると判断された場合、命令スケジューリング部４によって、次に命令群別優先度が高い命令群に含まれる命令が命令単位優先度に基づいて順次選択され、これらの処理サイクルに配置される（ステップＳ５）。
【００４２】
次に、命令スケジューリング部４によって、次に命令群別優先度が高い命令群に含まれる残りの命令が、次の処理サイクルから順にスケジューリングされる（ステップＳ６）。
【００４３】
一方、ステップＳ４において、ステップＳ３で生成された命令列の処理サイクルに他の命令群の命令を実行可能なものがないと判断された場合も、ステップＳ６が実行される。
【００４４】
命令スケジューリング部４によって、全ての命令群がスケジューリングされるまで（ステップＳ７でＹｅｓ）、ステップＳ４〜Ｓ７が繰り返される。
【００４５】
全ての命令群のスケジューリングが完了すると、命令スケジューリング装置１は動作を終了する。
【００４６】
次に、本発明の第１の実施の形態の効果について述べる。
【００４７】
本発明の第１の実施の形態としての命令スケジューリング装置は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成することができる。
【００４８】
その理由は、まず、命令群別優先度の高い命令群のスケジューリングを完了させ、情報処理装置で他の命令を実行可能な処理サイクルに、命令群別優先度が次に高い命令群に属する命令も並行に実行するようスケジューリングを行い、実機で並列実行可能でない命令を並列に配置しないからである。
【００４９】
これにより、本発明の第１の実施の形態としての命令スケジューリング装置は、必要以上に並行処理を行わない命令スケジューリングを実現し、並行配置される他の命令によって、開始した１つの処理の完了が遅延することを防止することができる。
【００５０】
次に、本発明の第２の実施の形態としての命令スケジューリング装置１０の構成について図３を用いて説明する。
【００５１】
図３において、命令スケジューリング装置１０は、機能ブロックとして、命令ブロック入力部１１と、ＤＡＧ（無閉路有向グラフ）構築部１２と、ＤＡＧ分割部１３と、優先度設定部１４と、命令スケジューリング部１６と、命令ブロック出力部１７と、を備えている。
【００５２】
ここで、命令スケジューリング装置１０は、本発明の第１の実施の形態と同様な汎用的なコンピュータ装置によって構成される。また、命令ブロック入力部１１と、ＤＡＧ構築部１２と、ＤＡＧ分割部１３と、優先度設定部１４と、命令スケジューリング部１６と、命令ブロック出力部１７とは、プログラムモジュールとして記憶装置に記憶され、ＣＰＵによってＲＡＭに読み込まれて実行される回路として構成される。
【００５３】
命令ブロック入力部１１は、情報処理装置９９に実行させるソースコードの命令列を命令ブロック単位で読み込む。なお、ソースコードの命令列は、命令スケジューリング装置１０の外部の装置によってブロックに分割されている。
【００５４】
また、命令ブロック入力部１１は、読み込んだソースコードの命令列を、アセンブラコードに即した命令列である中間言語１００に変換する。例えば、命令ブロック入力部１１は、図２１の（ａ）に示したソースコードから（ｂ）に示した中間言語１００を生成する。
【００５５】
ＤＡＧ構築部１２は、中間言語１００を解析し、命令間の依存関係に基づいてＤＡＧ２００を構築する。ＤＡＧ２００の一例を図４に示す。
【００５６】
ここで、一般的なＤＡＧは、ノードと、ノード間を結ぶエッジとによって構成され、非循環でエッジが方向性を持つグラフである。ＤＡＧ内のノードのうち、他のノードから依存されないノードは根ノードと呼ばれ、他のノードに依存しないノードは葉ノードと呼ばれる。一般的なＤＡＧは、ノード間の依存関係を表現するために用いられる。
【００５７】
ＤＡＧ構築部１２は、中間言語１００におけるデータ（図４のｉ、ｊ、＆ｙ、＆ｚなど）または命令の計算結果（図４のｔ２、ｔ３など）をノードで表し、データから計算結果への依存関係をエッジで表すようＤＡＧ２００を構築する。
【００５８】
ここで、このような依存関係を表すエッジを、以下、依存のエッジと呼ぶ。図４において、依存のエッジは、データを表すノードから計算結果を表すノードへの方向を持った実線矢印で表される。
【００５９】
また、ＤＡＧ構築部１２は、ＤＡＧ２００を構成するエッジに、データが取得されて命令の表す計算が開始されてから計算結果が得られるまでの時間(サイクル数)を付す。これにより、ＤＡＧ２００において、エッジの表す依存関係が解消されるまでに要する時間が表現される。
【００６０】
また、ＤＡＧ構築部１２は、ＤＡＧ２００を構成するノードのうち、他のノードより先に処理される必要のあるノードが存在する場合、先に処理される必要のあるノードから後に処理されるノードへ、非実線エッジを張り、制約のある依存関係を表す。このようなエッジを、以下、制約のエッジと呼ぶ。なお、制約のエッジは、図４の例では図示されていない。
【００６１】
例えば、元のソースコードに、同一のメモリに対する読む命令（１）と書く命令（２）とがこの順に含まれる場合、命令を並べ替えた後も命令（１）および命令（２）は、ソースコードの順に従って処理される制約が生ずる。このような場合、ＤＡＧ構築部１２は、命令（１）の計算結果を表すノードから命令（２）の計算結果を表すノードへ制約のエッジを張る。
【００６２】
ＤＡＧ分割部１３は、ＤＡＧ２００において、根ノードから依存のエッジだけをエッジと逆方向に辿ることにより、依存関係のある一連の命令を表すノードとエッジを抽出する。そして、ＤＡＧ分割部１３は、抽出したノードとエッジを１つの部分ＤＡＧとする。
【００６３】
また、ＤＡＧ分割部１３は、ＤＡＧ２００を部分ＤＡＧ３０１および部分ＤＡＧ３０２（以下、総称して部分ＤＡＧ３００ともいう）に分割する。ここで、部分ＤＡＧ３０１の一例を図５に示し、部分ＤＡＧ３０２の一例を図６に示す。
【００６４】
図５の部分ＤＡＧ３０１は、図４に示したＤＡＧ２００の根ノード「ｔ７［０］」から依存のエッジが辿られて分割されたものである。
【００６５】
また、図６の部分ＤＡＧ３０２は、ＤＡＧ２００の根ノード「ｔ７［４］」から依存のエッジが辿られて分割されたものである。
【００６６】
すなわち、ＤＡＧ分割部１３は、ＤＡＧ２００に根ノードが２つ含まれる場合、ＤＡＧ２００を２つの部分ＤＡＧ３００に分割する。
【００６７】
なお、本実施の形態において、ＤＡＧ分割部１３がＤＡＧ２００を２つの部分ＤＡＧ３００に分割する例について説明しているが、本発明において、ＤＡＧ分割手段が分割する部分ＤＡＧの数を限定するものではない。
【００６８】
ＤＡＧ分割部１３は、同一のノードやエッジが異なる部分ＤＡＧ３００に重複して含まれるようにＤＡＧ２００を分割する場合もある。
【００６９】
例えば、図４〜図６において、ＤＡＧ２００に含まれるノード２００１およびノード２００１が依存するノード、ノード２００２およびノード２００２が依存するノード、ならびにノード２００３およびノード２００３が依存するノードは、根ノード「ｔ７［０］」からも、根ノード「ｔ７［４］」からも依存されているため、部分ＤＡＧ３０１および部分ＤＡＧ３０２の両方に含まれている。
【００７０】
優先度設定部１４は、各部分ＤＡＧ３００の各ノードについて、命令単位優先度を計算し対応付ける。
【００７１】
優先度設定部１４は、例えば、ある命令の処理を開始してから、その命令の処理結果に依存する全ての命令の処理を完了するまでの時間(サイクル数)を命令単位優先度として設定する。すなわち、優先度設定部１４は、部分ＤＡＧ３００内の各ノードについて、該当するノードが依存するノードをたどって根ノードにたどりつくまでのエッジに付されたサイクル数を合計したものを命令単位優先度として対応付ける。
【００７２】
優先度設定部１４によって、部分ＤＡＧ３０１の各ノードに命令単位優先度が対応付けられた部分ＤＡＧ３０１ａの一例を図７に示す。また、部分ＤＡＧ３０２の各ノードに命令単位優先度が対応付けられた部分ＤＡＧ３０２ａの一例を図８に示す。図７、図８において、各ノードの右側に記載された数字が命令単位優先度を表す。数字が大きいほど優先度が高いことを表す。
【００７３】
このように、優先度設定部１４は、部分ＤＡＧ３００内で完了までの時間が長い命令に高い優先度を設定することにより、複数の命令を同時に実行させる命令列を生成する可能性を高め、１つの処理の完了までの時間を減らす。
【００７４】
また、優先度設定部１４は、各部分ＤＡＧ３００について、内部のノードに対応付けられた命令単位優先度のうち最も高いものがより高い部分ＤＡＧに、より高い命令群別優先度を設定する。
【００７５】
すなわち、優先度設定部１４は、部分ＤＡＧ３００が表す命令群による一連の処理の完了までにより多くの時間を要する命令群ほど、より高い命令群別優先度を設定する。
【００７６】
なお、優先度設定部１４は、内部のノードに対応付けられた命令単位優先度のうち最も高いものが同一の命令群については、命令ブロック入力部１１で入力された命令列において先に出現する命令に関連する命令群により高い命令群別優先度を設定するようにしてもよい。
【００７７】
命令スケジューリング部１６は、各部分ＤＡＧ３００に対応付けられた命令群別優先度、および、各部分ＤＡＧ３００内のノードに対応付けられた命令単位優先度に基づいて、命令を並べ替えて命令列を生成する。
【００７８】
詳細には、命令スケジューリング部１６は、ｉ（ｉは１以上の整数）番目に高い命令群別優先度が対応付けられた部分ＤＡＧ３００内の命令をまず完了させて命令列を生成した後、生成した命令列のうち、情報処理装置９９によって他の命令を並列実行可能な処理サイクルに、ｉ＋１番目に高い命令群別優先度が対応付けられた命令群内の命令を配置する。
【００７９】
このようにして、命令スケジューリング部１６は、全ての命令群の命令について順次スケジューリングを行い命令列７００を生成する。
【００８０】
命令ブロック出力部１７は、命令列７００を、外部へ出力する。なお、出力された命令列７００は、命令スケジューリング装置１０の外部の装置によってアセンブラコードおよび情報処理装置９９によって実行可能なマシンコードに変換される。
【００８１】
以上のように構成された命令スケジューリング装置１０の動作について、図９〜図１１を用いて説明する。
【００８２】
まず、命令ブロック入力部１１によって、ソースコードの命令列が命令ブロック単位で読み込まれ、中間言語１００に変換される（ステップＳ１１）。
【００８３】
次に、ＤＡＧ構築部１２によって、中間言語１００の命令間の依存関係が分析され、ＤＡＧ２００が構築される（ステップＳ１２）。
【００８４】
次に、ＤＡＧ分割部１３によって、ＤＡＧ２００が、依存関係のある一連の命令群をそれぞれ表す複数の部分ＤＡＧ３００に分割される（ステップＳ１３）。
【００８５】
次に、優先度設定部１４によって、各部分ＤＡＧ３００の各ノードに命令単位優先度が対応付けられる（ステップＳ１４）。
【００８６】
次に、優先度設定部１４によって、各部分ＤＡＧ３００に対して命令群別優先度が設定される（ステップＳ１５）。ステップＳ１５の処理の詳細については後述する。
【００８７】
次に、命令スケジューリング部１６によって、各部分ＤＡＧ３００に基づいて、命令列７００が生成される（ステップＳ１６）。ステップＳ１６の処理の詳細については後述する。
【００８８】
次に、命令ブロック出力部１７によって、命令列７００が出力される（ステップＳ１７）。
【００８９】
ここで、ステップＳ１５において、優先度設定部１４によって各部分ＤＡＧ３００に命令群別優先度が設定される動作について、図１０を用いて説明する。
【００９０】
ここでは、まず、優先度設定部１４によって、命令群別優先度が未設定の命令群があるか否かが判断される（ステップＳ２１）。
【００９１】
ここで、未設定の命令群があると判断された場合、優先度設定部１４によって、未設定の命令群のうち、命令群内のノードに対応付けられた最高の命令単位優先度が一番低い命令群が選択される（ステップＳ２２）。
【００９２】
次に、優先度設定部１４によって、選択された命令群に対して、前回選択した命令群に対して設定した優先度より大きい優先度が、今回選択した命令群に対して設定される（ステップＳ２３）。例えば、優先度設定部１４によってｎ回目のステップＳ２３で選択された命令群には、命令群別優先度ｎが設定されてもよい。
【００９３】
以上で、優先度設定部１４による命令群別優先度の設定動作が終了する。
【００９４】
ここで、命令群別優先度の設定動作の一例として、図７および図８に示した部分ＤＡＧ３０１ａおよび部分ＤＡＧ３０２ａに命令群別優先度が設定される動作を説明する。
【００９５】
まず、優先度設定部１４によって、１回目のステップＳ２１〜Ｓ２３が実行される。
【００９６】
すなわち、優先度設定部１４によって、命令群別優先度が未設定の部分ＤＡＧ３００が残っているかどうかが判断される。ここでは、部分ＤＡＧ３０１ａおよび部分ＤＡＧ３０２ａが残っていると判断される（ステップＳ２１でＹｅｓ）。
【００９７】
次に、優先度設定部１４によって、未設定の部分ＤＡＧ３００のうち、部分ＤＡＧ内で最高の命令単位優先度が最も低いものが選択される。このとき、部分ＤＡＧ３０１ａおよび部分ＤＡＧ３０２ａ内で最高の命令単位優先度はそれぞれ１１で等しい。
【００９８】
この場合は、優先度設定部１４によって、命令ブロック入力部１１で入力された命令列に後に出現する命令が含まれる部分ＤＡＧ３００が選択される。ここでは、部分ＤＡＧ３０２ａにのみ属する命令が後に出現するため、部分ＤＡＧ３０２ａが選択される（ステップＳ２２）。
【００９９】
なお、優先度設定部１４が、最高の命令単位優先度が等しい部分ＤＡＧ３００を選択する順序は、他の順序であってもよい。
【０１００】
次に、優先度設定部１４によって、１回目に選択された部分ＤＡＧ３０２ａに、命令群別優先度1が設定される（ステップＳ２３）。
【０１０１】
次に、優先度設定部１４によって、２回目のステップＳ２１〜Ｓ２３が実行される。
【０１０２】
すなわち、優先度設定部１４によって、命令群別優先度が未設定の部分ＤＡＧ３００が残っているかどうかが判断される。ここでは、部分ＤＡＧ３０１ａが残っていると判断される（ステップＳ２１でＹｅｓ）。
【０１０３】
次に、優先度設定部１４によって、未設定の部分ＤＡＧ３００のうち、部分ＤＡＧ内で最高の命令単位優先度が最も低いものが選択される。ここでは、未設定の部分ＤＡＧは部分ＤＡＧ３０１ａのみなので、部分ＤＡＧ３０１ａが選択される（ステップＳ２２）。
【０１０４】
次に、優先度設定部１４によって、２回目に選択された部分ＤＡＧ３０２ａに、命令群別優先度２が設定される（ステップＳ２３）。
【０１０５】
次に、優先度設定部１４によって、３回目のステップＳ２１が実行される。
【０１０６】
すなわち、優先度設定部１４によって、命令群別優先度が未設定の部分ＤＡＧ３００が残っているかどうかが判断される。ここでは、未設定の部分ＤＡＧ３００が残っていないと判断され（ステップＳ２１でＮｏ）、命令群別優先度の設定動作が終了する。
【０１０７】
次に、図９のステップＳ１６において、命令スケジューリング部１６による命令列７００の生成動作について、図２および図１１を用いて詳細に説明する。図１１において、各処理サイクルに命令がスケジューリングされている。図１１（ａ）、（ｂ）において、命令の左側の番号が処理リサイクルの順番を表す。
【０１０８】
命令スケジューリング部１６は、ステップＳ１６において、本発明の第１の実施の形態に係る命令スケジューリング部４と同様に図２に示したステップＳ３〜Ｓ７の動作を実行する。
【０１０９】
ここでは、命令スケジューリング部１６が、図７および図８に示した部分ＤＡＧ３００に基づいて命令列を生成する動作についてステップＳ３〜Ｓ７に沿って説明する。
【０１１０】
なお、ここでは、情報処理装置９９が同一の処理サイクルで並列に実行できる命令には次のような制約があるものとする。
・ロード命令（ｌｄ）同士は並列に実行できない。
・ストア命令（ｓｔ）同士は並列に実行できない。
・ロード命令およびストア命令は並列に実行できない。
・上記以外の組合せの命令は２命令並列に実行できる。
【０１１１】
また、情報処理装置９９は、各命令の実行に以下のサイクル数を必要するものとする。
・ロード命令の完了までに３サイクル
・その他の命令の完了までに1サイクル
まず、命令スケジューリング部１６によって、より高い命令群別優先度２が対応付けられた部分ＤＡＧ３０１ａ内の命令についてスケジューリングが行われ、図１１（ａ）に示す命令列が生成される（ステップＳ３）。
【０１１２】
次に、命令スケジューリング部１６によって、生成された命令列のうち、図１１（ａ）の処理サイクル８、９および１２に、情報処理装置９９で他の命令を実行可能な余裕があると判断される（ステップＳ４でＹｅｓ）。
【０１１３】
そこで、命令スケジューリング部１６によって、次に高い命令群別優先度１が対応付けられた部分ＤＡＧ３０２ａ内の命令のうち、命令単位優先度の高い命令から順に３つの命令が、処理サイクル８、９および１２に配置される（ステップＳ５）。
【０１１４】
次に、命令スケジューリング部１６によって、次に高い命令群別優先度１が対応付けられた部分ＤＡＧ３０２ａ内の残りのノードに対応する命令が、命令単位優先度の高いものから順に処理サイクル１３および１４に配置され（ステップＳ６）、図１１（ｂ）に示す命令列７００が生成される。
【０１１５】
次に、命令スケジューリング部１６によって、命令群を表す部分ＤＡＧ３００の全てについて処理が完了したと判断され（ステップＳ７でＹｅｓ）、命令列７００の生成動作が終了する。
【０１１６】
以上のように命令スケジューリング装置１０によって生成された命令列７００と、関連技術の命令スケジューリング装置によって生成された命令列との比較を図１２に示す。
【０１１７】
ここで、関連技術の命令スケジューリング装置は、命令単位優先度のみに基づいて命令列を生成しているものとする。
【０１１８】
関連技術の命令スケジューリング装置は、図１２（ａ）に示すように、x[j+0]の処理に関連する一連の命令に１４サイクル要する命令列を生成している。これに対して、本発明の第２の実施の形態としての命令スケジューリング装置１０は、図１２（ｂ）に示すように、x[j+0]の処理に関連する一連の命令を１２サイクルで完了させる命令列を生成することができ、x[j+0]の処理の遅延を抑えている。
【０１１９】
また、関連技術の命令スケジューリング装置は、図１２（ａ）に示すように、x[j+0]の処理に必要とするレジスタｒ１５をサイクル１４で解放可能にする。これに対して、本発明の第２の実施の形態としての命令スケジューリング装置１０は、図１２（ｂ）に示すように、レジスタｒ１５をサイクル１２で解放可能にすることができ、レジスタの利用期間を短縮している。
【０１２０】
また、関連技術の命令スケジューリング装置は、図１２（ａ）に示すように、x[j+0]およびx[j+1]の処理として、全体で１５サイクルの命令列を生成している。これに対して、本発明の第２の実施の形態としての命令スケジューリング装置１０は、x[j+0]およびx[j+1]の処理として、全体で１４サイクルの命令列を生成することができ、全体としての処理の完了の遅延も抑えることができる。
【０１２１】
次に、本発明の第２の実施の形態の効果について述べる。
【０１２２】
本発明の第２の実施の形態としての命令スケジューリング装置は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を、ＤＡＧを利用して効率的に生成することができる。
【０１２３】
その理由は、依存関係のある一連の命令を部分ＤＡＧで表し、部分ＤＡＧの各ノードに命令単位優先度を対応付け、部分ＤＡＧに命令群別優先度を対応付け、部分ＤＡＧに基づいて命令スケジューリングを行うからである。
【０１２４】
また、本発明の第２の実施の形態としての命令スケジューリング装置は、計算中に同時に必要になるレジスタの数を抑えた命令列を生成することができる。
【０１２５】
その理由は、開始した処理の遅延を抑えた命令列を生成することにより、処理中に利用が開始されるレジスタを、処理の完了と共に遅延なく解放できるからである。
【０１２６】
例えば、関連技術の命令スケジューリング装置は、３つの独立した処理を行うソースコードに対して、３つの処理を並行に実行する命令列を生成する場合があり、３つの処理に関連するレジスタが同時に必要になる場合があった。
【０１２７】
本発明の第２の実施の形態の命令スケジューリング装置は、３つの独立した処理を行うソースコードに対しても、１つの処理を表す命令群別に命令群別優先度を設定して、命令群別優先度の高い順に並べ替える。その結果、本発明の第２の実施の形態の命令スケジューリング装置は、１つ目の処理を開始し、その処理の終了の間際に２つ目の処理を開始し、その処理の終了間際に３つ目の処理を開始するような命令列を生成する。このような命令列では、並行して実行される命令が高々２つに抑えられる。
【０１２８】
したがって、本発明の第２の実施の形態の命令スケジューリング装置は、同時に必要なレジスタを高々２つの処理に関連するものに抑えた命令列を生成することができる。
【０１２９】
次に、本発明の第３の実施の形態について、図面を参照して詳細に説明する。
【０１３０】
本発明の第３の実施の形態としての命令スケジューリング装置２０の構成を図１３に示す。
【０１３１】
図１３において、命令スケジューリング装置２０は、本発明の第２の実施の形態の命令スケジューリング装置１０に対して、優先度設定部１４に替えて優先度設定部２４を備え、命令スケジューリング部１６に替えて命令スケジューリング部２６を備え、さらにＤＡＧ統合部２５を備える点が異なる。
【０１３２】
ここで、命令スケジューリング装置２０は、本発明の第２の実施の形態と同様な汎用的なコンピュータ装置によって構成される。また、優先度設定部２４と、ＤＡＧ統合部２５と、命令スケジューリング部２６とは、プログラムモジュールとして記憶装置に記憶され、ＣＰＵによってＲＡＭに読み込まれて実行される回路として構成される。
【０１３３】
優先度設定部２４は、本発明の第２の実施の形態における優先度設定部１４と同様に命令単位優先度および命令群別優先度を設定する。
【０１３４】
また、優先度設定部２４は、さらに、各部分ＤＡＧを構成する各ノードに、該ノードが含まれる部分ＤＡＧに設定された命令群別優先度および各ノードに設定された命令単位優先度からなる２段階優先度を対応付ける。
【０１３５】
優先度設定部２４によって、部分ＤＡＧ３０１の各ノードに２段階優先度が対応付けられた部分ＤＡＧ３０１ｂを図１４に示す。また、部分ＤＡＧ３０２の各ノードに２段階優先度が対応付けられた部分ＤＡＧ３０２ｂを図１５に示す。
【０１３６】
図１４および図１５において、２段階優先度を「命令群別優先度：命令単位優先度」と表記している。
【０１３７】
ＤＡＧ統合部２５は、分割した部分ＤＡＧ３００を、元のＤＡＧ２００と同様の形に統合した統合ＤＡＧ６００を生成する。
【０１３８】
また、ＤＡＧ統合部２５は、統合ＤＡＧ６００内の各ノードに、優先度設定部２４によって設定された２段階優先度を対応付ける。
【０１３９】
このとき、ＤＡＧ統合部２５は、統合ＤＡＧ６００内のノードのうち、複数の部分ＤＡＧ３００に含まれていたノードに対しては、以下のように２段階優先度を対応付ける。
・命令群別優先度が異なる場合は、命令群別優先度が高い方の２段階優先度を選択して対応付ける。
・命令群別優先度が等しい場合は、命令単位優先度が高い方の２段階優先度を選択して対応付ける。
【０１４０】
部分ＤＡＧ３０１および部分ＤＡＧ３０２が統合された統合ＤＡＧ６００の一例を図１６に示す。
【０１４１】
命令スケジューリング部２６は、統合ＤＡＧ６００内の各ノードに対応付けられた２段階優先度に基づいて、より高い命令群別優先度でより高い命令単位優先度の命令から順に各処理サイクルに配置していく。
【０１４２】
このとき、命令スケジューリング部２６は、各処理サイクルに命令を配置する際に、該処理サイクルで他の命令群の命令を実行可能であるか否かを判断し、実行可能であれば、次に高い命令群別優先度の命令を該処理サイクルに配置する。
【０１４３】
以下、「より高い命令群別優先度が含まれる２段階優先度が対応付けられたノードに対応する命令」のことを、単に「より高い命令群別優先度の命令」ともいう。また、「より高い命令単位優先度が含まれる２段階優先度が対応付けられたノードに対応する命令」のことを、単に「より高い命令単位優先度の命令」ともいう。
【０１４４】
具体的には、命令スケジューリング部２６は、ｉ番目に高い命令群別優先度の命令について、命令単位優先度に基づいて各処理サイクルに配置していく。このとき、命令スケジューリング部２６は、命令を配置する処理サイクルで情報処理装置９９によって他の命令を並列実行可能か否かを判断する。そして、命令スケジューリング部２６は、他の命令を並列実行可能であれば、ｉ＋１番目に高い命令群別優先度の命令を該処理サイクルに配置する。
【０１４５】
このようにして、命令スケジューリング部２６は、ｉ＋１番目に命令群別優先度の高い命令を配置可能な処理サイクルには該命令を配置しながら、ｉ番目に命令群別優先度の高い命令のスケジューリングを完了させる。
【０１４６】
このようにして、命令スケジューリング部１６は、統合ＤＡＧ６００内のノードに対応する全ての命令について並べ替えを行い命令列７００を生成する。
【０１４７】
以上のように構成された命令スケジューリング装置２０の動作について、図１７を用いて説明する。
【０１４８】
なお、図１７において、本発明の第２の実施の形態としての命令スケジューリング装置１０と同様に動作するステップについては同一の符号を付して詳細な説明を省略する。
【０１４９】
命令スケジューリング装置２０は、ステップＳ１１〜Ｓ１５まで本発明の第２の実施の形態としての命令スケジューリング装置１０と同様に動作して部分ＤＡＧ３００を生成し、命令単位優先度および命令群別優先度を設定する。
【０１５０】
次に、命令単位優先度および命令群別優先度からなる２段階優先度が、優先度設定部２４によって、各部分ＤＡＧ３００の各ノードに対応付けられる（ステップＳ３６）。
【０１５１】
次に、部分ＤＡＧ３００が統合された統合ＤＡＧ６００が、ＤＡＧ統合部２５によって生成される（ステップＳ３７）。
【０１５２】
次に、統合ＤＡＧ６００に基づいて、命令スケジューリング部２６によって命令が並べ替えられ、命令列７００が生成される（ステップＳ３８）。
【０１５３】
ここで、ステップＳ３８における命令スケジューリング部２６の命令スケジューリング動作について、図１８を用いて説明する。
【０１５４】
ここでは、命令スケジューリング部２６によって、命令群別優先度が高いものから順に、命令群別優先度が同一の命令についてステップＳ４１〜Ｓ４４が実行される。
【０１５５】
まず、命令スケジューリング部２６によって、この命令群別優先度で次に命令単位優先度が高い命令が次の処理サイクルに配置可能であれば配置される（ステップＳ４１）。
【０１５６】
ここで、この命令群別優先度でさらに次に高い命令単位優先度の命令がこの処理サイクルに並列に配置可能であればこれらの命令がこの処理サイクルに並列に配置される。また、この命令群別優先度の命令でこの処理サイクルに配置可能なものがなければ、この命令群別優先度の命令はこの処理サイクルに配置されない。
【０１５７】
次に、命令スケジューリング部２６によって、この処理サイクルで他の命令群別優先度の命令が実行可能か否かが判断される（ステップＳ４２）。
【０１５８】
ここで、該当する処理サイクルで他の命令群別優先度の命令が実行可能でないと判断されると、命令スケジューリング部２６の処理はステップＳ４１に戻る。
【０１５９】
一方、該当する処理サイクルで他の命令群別優先度の命令が実行可能であると判断されると、命令群スケジューリング部２６によって、次に命令群別優先度が高い命令のうち命令単位優先度が高いものが該当する処理サイクルに配置される（ステップＳ４３）。
【０１６０】
このようにして、この命令群別優先度の命令のスケジューリングが完了すると（ステップＳ４４でＹｅｓ）、命令スケジューリング部２６によって、次に命令群別優先度が高い命令のうち未配置の命令について、ステップＳ４１〜Ｓ４４が繰り返し実行される。
【０１６１】
命令スケジューリング部２６によって、全ての命令群別優先度の命令のスケジューリングが完了すると、命令スケジューリング動作が終了する。
【０１６２】
例えば、命令スケジューリング部２６が、図１６に示した統合ＤＡＧ６００に基づいて、図１２（ｂ）に示した命令列７００を生成する例について説明する。
【０１６３】
命令スケジューリング部２６は、まず、命令群別優先度２の命令を、命令単位優先度に基づいて図１２（ｂ）の処理サイクル０に配置する（ステップＳ４１）。このとき、命令スケジューリング部２６は、命令群別優先度２の２つの命令を並列に配置可能であるため並列に配置する。
【０１６４】
次に、命令スケジューリング部２６は、この処理サイクル０で他の命令群別優先度の命令を実行可能でないと判断する（Ｓ４２でＮｏ）。
【０１６５】
命令スケジューリング部２６は、ステップＳ４１の処理およびステップＳ４２でＮｏの判断を繰り返して図１２（ｂ）の処理サイクル０〜７までスケジューリングを行う。
【０１６６】
次に、命令スケジューリング部２６は、次の処理サイクル８には、命令群別優先度２内の命令で配置可能なものがないため配置しない（ステップＳ４１）。
【０１６７】
ここで、命令スケジューリング部２６は、この処理サイクル８で他の命令群別優先度の命令を実行可能であると判断し（ステップＳ４２でＹｅｓ）、命令群別優先度１の命令のうち、２段階優先度「１：３」が対応付けられた「t8へのロード命令」を選択し処理サイクル８に配置する（ステップＳ４３）。
【０１６８】
次に、命令スケジューリング部２６は、さらに次の処理サイクル９にも、命令群別優先度２内の命令で配置可能なものがないため配置しない（ステップＳ４１）。
【０１６９】
ここで、命令スケジューリング部２６は、この処理サイクル９で他の命令群別優先度の命令を実行可能であると判断し（ステップＳ４２でＹｅｓ）、命令群別優先度１の命令のうち、２段階優先度「１：３」が対応付けられた「t9へのロード命令」を選択し処理サイクル９に配置する（ステップＳ４３）。
【０１７０】
次に、命令スケジューリング部２６は、命令群別優先度２の残りの命令について、ステップＳ４１の処理およびステップＳ４２でＮｏの判断を繰り返して図１２（ｂ）の処理サイクル１０〜１２までスケジューリングを行う。
【０１７１】
次に、命令スケジューリング部２６は、処理サイクル１２で他の命令群内の命令を実行可能であると判断し（ステップＳ４２でＹｅｓ）、命令群別優先度１の命令を処理サイクル１２に配置する（ステップＳ４３）。
【０１７２】
これで、命令スケジューリング部２６は、命令群別優先度２の命令群内の命令のスケジューリングを終えたと判断し（ステップＳ４４でＹｅｓ）、次の命令群別優先度１の命令群内の命令のスケジューリングに処理を移す。
【０１７３】
次に、命令スケジューリング部２６は、命令群別優先度１の残りの命令について、ステップＳ４１〜Ｓ４２を繰り返し、処理サイクル１３〜１４に配置する。
【０１７４】
これで、命令スケジューリング部２６は、全ての命令のスケジューリングを終え、命令列７００の生成を終了する。
【０１７５】
このように、命令スケジューリング部２６は、命令スケジューリング部１６と同様の命令列７００を、命令スケジューリング部１６に比べて簡略化された処理手順で生成する。
【０１７６】
次に、本発明の第３の実施の形態の効果について述べる。
【０１７７】
本発明の第３の実施の形態としての命令スケジューリング装置は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を、さらに効率的に生成することができる。
【０１７８】
その理由は、各ノードに２段階優先度を対応付けた統合ＤＡＧを生成することにより、命令群毎の命令スケジューリングを完了させてから次の命令群の命令を前の命令群の命令列にマージする必要がなく、簡略化された生成手順で命令列の生成時間を短縮することができるからである。
【０１７９】
次に、本発明の第４の実施の形態について、図面を参照して説明する。
【０１８０】
本発明の第４の実施の形態の命令スケジューリング装置３０の構成を図１９に示す。
【０１８１】
図１９において、命令スケジューリング装置３０は、本発明の第３の実施の形態の命令スケジューリング装置２０に対して、ＤＡＧ分割部１３に替えてＤＡＧ分割部３３を備え、優先度設定部２４に替えて優先度設定部３４を備え、ＤＡＧ統合部２５に替えてＤＡＧ統合部３５を備える点が異なる。
【０１８２】
ここで、命令スケジューリング装置３０は、本発明の第３の実施の形態と同様な汎用的なコンピュータ装置によって構成される。また、ＤＡＧ分割部３３と、優先度設定部３４と、ＤＡＧ統合部３５とは、プログラムモジュールとして記憶装置に記憶され、ＣＰＵによってＲＡＭに読み込まれて実行される回路として構成される。
【０１８３】
ＤＡＧ分割部３３は、ＤＡＧ構築部１２によって構成されたＤＡＧ２００の各ノードに、依存関係のある一連の命令群を識別する命令群識別情報を対応付ける。ここで、ＤＡＧ分割部３３は、複数の命令群に含まれるノードには、複数の命令群識別情報を対応付ける。これにより、ＤＡＧ分割部３３は、ＤＡＧ２００を複数の部分ＤＡＧ３００に仮想的に分割する。
【０１８４】
優先度設定部３４は、ＤＡＧ２００の各ノードに対応付けられた命令群識別情報に、２段階優先度を対応付ける。ここで、優先度設定部３４は、複数の命令群に含まれ複数の命令群識別情報が対応付けられたノードには、各命令群識別情報に対して２段階優先度を対応付ける。
【０１８５】
ＤＡＧ統合部３５は、複数の２段階優先度が対応付けられたノードについて、いずれかの２段階優先度を選択したことを表す選択情報を対応付ける。例えば、ＤＡＧ統合部３５は、複数の２段階優先度のうち、命令群別優先度が高い方の２段階優先度を選択したことを表す選択情報を、該当するノードに対応付ける。この場合、ＤＡＧ統合部３５は、複数の２段階優先度の命令群別優先度が同一であれば、命令単位優先度が高い方の２段階優先度を選択したことを表す選択情報を、該当するノードに対応付ける。
【０１８６】
これにより、ＤＡＧ統合部３５は、仮想的に分割された複数の部分ＤＡＧを仮想的に統合する。
【０１８７】
ＤＡＧ分割部３３、優先度設定部３４およびＤＡＧ統合部３５によって、命令群識別情報、２段階優先度および選択情報が対応付けられたＤＡＧ２００のノードの一例を図２０に示す。
【０１８８】
以上のように構成された命令スケジューリング装置３０は、各ノードに２段階優先度の選択情報が対応付けられたＤＡＧ２００を、本発明の第３の実施の形態における統合ＤＡＧ６００とみなすことにより、本発明の第３の実施の形態としての命令スケジューリング装置２０と同様に動作して、命令列７００を生成する。
【０１８９】
本発明の第４の実施の形態の効果について述べる。
【０１９０】
本発明の第４の実施の形態としての命令スケジューリング装置は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成する際の、メモリ使用量および生成時間を短縮することができる。
【０１９１】
その理由は、本発明の第４の実施の形態としての命令スケジューリング装置は、構築したＤＡＧを用いて部分ＤＡＧおよび統合ＤＡＧを仮想的に生成するので、部分ＤＡＧおよび統合ＤＡＧを表す情報を生成する時間を短縮することができ、部分ＤＡＧおよび統合ＤＡＧを表す情報を記憶するためのメモリ領域を必要としないからである。
【０１９２】
なお、上述した本発明の各実施の形態において、命令スケジューリング装置の動作は、本発明の命令スケジューリングプログラムを構成するプログラムモジュールとして命令スケジューリング装置が備える記憶装置に格納され、ＣＰＵによって実行されるようにしてもよい。
【０１９３】
また、上述した各実施の形態は、適宜組み合わせて実施されることが可能である。
【０１９４】
また、本発明は、上述した各実施の形態に限定されず、様々な態様で実施されることが可能である。
【符号の説明】
【０１９５】
１、１０、２０、３０ 命令スケジューリング装置
２ 命令群分割部
３ 優先度設定部
４ 命令スケジューリング部
１１ 命令ブロック入力部
１２ ＤＡＧ構築部
１３、３３ ＤＡＧ分割部
１４、２４、３４ 優先度設定部
１６、２６ 命令スケジューリング部
１７ 命令ブロック出力部
２５、３５ ＤＡＧ統合部
【技術分野】
【０００１】
本発明は、情報処理装置に実行させる命令をスケジューリングして命令列を生成する命令スケジューリング装置に関し、特に、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令をスケジューリングする命令スケジューリング装置、命令スケジューリング方法および命令スケジューリングプログラムに関する。
【背景技術】
【０００２】
一般的に、命令スケジューリング装置は、実行時間をより短縮する命令列を生成するため、命令を効率よく配置するスケジューリングを行って命令列を生成する。このような命令スケジューリング装置として、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令をスケジューリングするものが知られている。
【０００３】
処理サイクル毎に複数の命令を並列に実行可能な情報処理装置としては、例えば、命令パイプラインを採用したものがよく知られている。命令パイプラインを採用した情報処理装置は、命令が分割された複数のステージに対して、各ステージを処理する処理部を有する。各処理部は、前のステージの出力を入力として担当するステージを処理し、その結果を次のステージに出力する。各処理部が連続する命令の各ステージを並行して実行することにより、複数の命令を並列に実行する。
【０００４】
また、命令パイプラインを採用した情報処理装置において、さらなる性能向上のため、例えば、ＶＬＩＷ（Very Long Instruction Word）を採用したものも知られている。ＶＬＩＷを採用した情報処理装置は、並列実行可能な複数の命令が１つに記述された命令をパイプラインで実行する。
【０００５】
このような処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に対応した命令スケジューリング装置としては、命令ブロック毎に、命令の依存関係がノードおよびエッジで表されたＤＡＧ（Directed Acyclic Graph：無閉路有向グラフ）を構築し、ノード間の依存関係に基づいてノードの優先度を計算するものがある。そして、このような命令スケジューリング装置は、優先度の高いノードから順に、依存関係がない命令を並列実行可能であるとみなして並列に配置しながら全命令をスケジューリングする（例えば、非特許文献１および特許文献１参照）。
【０００６】
また、他のこのような命令スケジューリング装置として、１つ以上の命令からなる命令グループを生成し、並列に実行可能な命令グループ同士を対応付け、命令グループごとに、対応付けられた他の命令グループとの入れ替えまたは発行繰り上げを判断して、全体としての総実行時間を短縮するものがある（例えば、特許文献２参照）。
【０００７】
また、さらに他のこのような命令スケジューリング装置として、依存関係のある一連の命令を命令群とし、命令群毎に他の命令群とのコンフリクトを無視して命令スケジューリングを行って配置データを生成した後、複数の命令群の配置データをコンフリクトを解消するよう調整して合成するものがある（例えば、特許文献３参照）。
【０００８】
また、さらに他のこのような命令スケジューリング装置として、１つのレジスタの第１の部分にアクセスする命令と、同一のレジスタの第２の部分をアクセスする命令を同一のサイクルにスケジューリングするものがある（例えば、特許文献４参照）。また、この特許文献４に記載の命令スケジューリング装置は、同一のサイクルにおいて、複数の命令が１つのレジスタの同一の部分にアクセスする場合には、命令の種類毎に設定された優先度に基づいて優先度の高い命令を選択する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】中田育男著「コンパイラの構成と最適化」朝倉書店、1999年9月20日、ｐｐ．358−362
【特許文献】
【００１０】
【特許文献１】特開平３−１３５６３０号公報
【特許文献２】特開平６−２８３２４号公報
【特許文献３】特開２００２−２６８８９５号公報
【特許文献４】特開２０００−２２２２０９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、非特許文献１および特許文献１に記載されたものは、優先度の高い命令から順に、依存関係がないものを並列に配置し、情報処理装置のアーキテクチャに左右される並列実行可能な命令の組合せおよび数を考慮せずに命令を並べ替える。そのため、特許文献１および非特許文献１に記載されたものは、実機で並列に実行できない命令を並列に配置した命令列を生成する場合がある。したがって、特許文献１および非特許文献１に記載されたものは、生成した命令列を実機に実行させると、１つの処理を実行するための一連の命令の間で、依存関係のない他の命令を実行することになり、１つの処理の完了までの時間を遅延させる可能性があるという課題があった。
【００１２】
また、特許文献２に記載されたものは、１つの処理を実行するための一連の命令の依存関係を考慮せずに命令グループを生成している。このため、特許文献２に記載されたものは、１つの処理を実行するための一連の命令の間に、並列実行可能な他の命令を挿入してしまい、この１つの処理の完了を遅延させる可能性があるという課題があった。
【００１３】
また、特許文献３に記載されたものは、複数の命令群の配置データのコンフリクトを調整する際に、いったん配置した命令列の処理サイクル数を延長する場合があり、１つの処理の完了を遅延させる可能性があるという課題があった。
【００１４】
また、特許文献４に記載されたものは、命令の種類毎に設定された優先度に基づいて命令スケジューリングを行うとき、命令間の依存関係に関わらず優先度の高いものを選択する。このため、特許文献４に記載されたものは、１つの処理を実行するための一連の命令の間に、これらの一連の命令とは依存関係のない他の命令を配置する場合があり、１つの処理の完了を遅延させる可能性があるという課題があった。
【００１５】
また、これらの特許文献１〜４に記載されたものは、１つの処理の完了を遅延させる命令列では、この処理に必要な中間結果を保持するレジスタを長時間必要とするという課題があった。
【００１６】
ここで、これらの関連技術により生成される命令列の一例を用いて、上述の課題の具体例について図２１〜図２２を参照して説明する。
【００１７】
図２１（ａ）はソースコードを表している。このソースコードは、x[j+0]およびx[j+1]の互いに独立した処理によって構成されている。図２１（ｂ）は、（ａ）に示したソースコードから生成される中間言語の命令列である。
【００１８】
図２２（ａ）は、上述の関連技術によって、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に対して、x[j+0]およびx[j+1]の処理に対応する中間言語がスケジューリングされた命令列の一例である。なお、この情報処理装置では、同一の処理サイクルで並列に実行できる命令には次のような制約があるものとする。
・ロード命令（ｌｄ）同士は並列に実行できない。
・ストア命令（ｓｔ）同士は並列に実行できない。
・ロード命令およびストア命令は並列に実行できない。
・上記以外の組合せの命令は２命令並列に実行できる。
【００１９】
また、この情報処理装置は、各命令の実行に以下のサイクル数を必要するものとする。
・ロード命令の完了までに３サイクル
・その他の命令の完了までに1サイクル
図２２（ａ）の命令列では、x[j+0]の処理に関する一連の命令の間にx[j+1]に関する命令の一部が挿入されている。したがって、図２２（ａ）の命令列は、x[j+0]の処理開始から完了までに１４サイクルを要している。
【００２０】
これに対して、図２２（ｂ）に、x[j+0]に対応する命令のみをスケジューリングした場合の命令列を示す。図２２（ｂ）の命令列では、x[j+0]の処理開始から完了までに要する時間は１２サイクルである。このように、上述の関連技術により生成された命令列の一例では、x[j+0]の処理の完了を２サイクル遅延させている。
【００２１】
また、この遅延に伴って、上述の関連技術により生成された命令列の一例は、x[j+0]の処理に必要なレジスタｒ１５を解放可能とするタイミングを遅延させており、レジスタｒ１５をより長期間必要とする命令列となっている。
【００２２】
本発明は、上述の課題を解決するためになされたもので、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成することができる命令スケジューリング装置を提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明の命令スケジューリング装置は、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割手段と、前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定手段と、前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリング手段と、を備える。
【００２４】
また、本発明の命令スケジューリング方法は、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令をスケジューリングする命令スケジューリング装置が、前記複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割ステップと、前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定ステップと、前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリングステップと、を実行する。
【００２５】
また、本発明の命令スケジューリングプログラムは、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令をスケジューリングする命令スケジューリング装置に、前記複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割ステップと、前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定ステップと、
前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリングステップと、を実行させる。
【発明の効果】
【００２６】
本発明は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成することができる命令スケジューリング装置を提供することができる。
【図面の簡単な説明】
【００２７】
【図１】本発明の第１の実施の形態としての命令スケジューリング装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態としての命令スケジューリング装置の動作を示すフローチャートである。
【図３】本発明の第２の実施の形態としての命令スケジューリング装置の構成を示すブロック図である。
【図４】本発明の第２の実施の形態において構築されるＤＡＧの一例を説明する模式図である。
【図５】本発明の第２の実施の形態において分割される部分ＤＡＧの一例を説明する模式図である。
【図６】本発明の第２の実施の形態において分割される部分ＤＡＧの他の一例を説明する模式図である。
【図７】本発明の第２の実施の形態において命令単位優先度が設定された部分ＤＡＧの一例を説明する模式図である。
【図８】本発明の第２の実施の形態において命令単位優先度が設定された部分ＤＡＧの他の一例を説明する模式図である。
【図９】本発明の第２の実施の形態としての命令スケジューリング装置の動作を示すフローチャートである。
【図１０】本発明の第２の実施の形態としての命令スケジューリング装置の命令群別優先度の設定動作を示すフローチャートである。
【図１１】本発明の第２の実施の形態としての命令スケジューリング装置によって生成される命令列の一例を説明する図である。
【図１２】本発明の第２の実施の形態としての命令スケジューリング装置によって生成される命令列と関連技術によって生成される命令列とを比較する図である。
【図１３】本発明の第３の実施の形態としての命令スケジューリング装置の構成を示すブロック図である。
【図１４】本発明の第３の実施の形態において２段階優先度が設定された部分ＤＡＧの一例を説明する模式図である。
【図１５】本発明の第３の実施の形態において２段階優先度が設定された部分ＤＡＧの他の一例を説明する模式図である。
【図１６】本発明の第３の実施の形態において統合された統合ＤＡＧの一例を説明する模式図である。
【図１７】本発明の第３の実施の形態としての命令スケジューリング装置の動作を示すフローチャートである。
【図１８】本発明の第３の実施の形態としての命令スケジューリング装置の命令スケジューリング動作を示すフローチャートである。
【図１９】本発明の第４の実施の形態としての命令スケジューリング装置の構成を示すブロック図である。
【図２０】本発明の第４の実施の形態におけるＤＡＧに対応付けられた情報を説明する図である。
【図２１】本発明の各実施の形態におけるソースコードおよび中間言語を説明する図である。
【図２２】関連技術の命令スケジューリング装置によって生成される命令列の一例を説明する図である。
【発明を実施するための形態】
【００２８】
以下、本発明の第１の実施の形態について、図面を参照して詳細に説明する。
【００２９】
本発明の第１の実施の形態としての命令スケジューリング装置１の構成を図１に示す。
【００３０】
図１において、命令スケジューリング装置１は、機能ブロックとして、命令群分割部２と、優先度設定部３と、命令スケジューリング部４と、を備える。
【００３１】
ここで、命令スケジューリング装置１は、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、記憶装置とを備えた汎用的なコンピュータ装置によって構成されている。また、命令群分割部２と、優先度設定部３と、命令スケジューリング部４とは、プログラムモジュールとして記憶装置に記憶され、ＣＰＵによってＲＡＭに読み込まれて実行される回路として構成される。
【００３２】
命令群分割部２は、処理サイクル毎に複数の命令を並列に実行可能な情報処理装置９９（図示せず）に実行させる命令列を命令ブロック単位で読み込み、命令ブロックを構成する命令の依存関係を分析する。そして、命令群分割部２は、依存関係のある一連の命令を１つの命令群として、命令ブロックを複数の命令群に分割する。
【００３３】
優先度設定部３は、各命令群内の各命令に対して、該命令群における処理順序の優先度を表す命令単位優先度を設定する。さらに、優先度設定部３は、各命令群に対して、命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する。
【００３４】
ここで、優先度設定部３は、例えば、その命令の結果に依存する全ての命令の処理を完了するまでの時間(処理サイクル数)に基づいて命令単位優先度を設定してもよい。また、優先度設定部３は、例えば、命令群内の命令に設定された命令単位優先度のうち最も高いものに基づいて命令群別優先度を設定してもよい。
【００３５】
命令スケジューリング部４は、命令群別優先度の高い命令群から順に、該命令群に含まれる命令を命令単位優先度に基づいてスケジューリングする。また、命令スケジューリング部４は、スケジューリングした命令群内の命令が配置された処理サイクルのうち、情報処理装置９９によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する。
【００３６】
以上のように構成された命令スケジューリング装置１の動作について、図２を用いて説明する。
【００３７】
まず、命令群分割部２によって、命令ブロック内の命令が、依存関係のある一連の命令をそれぞれ表す複数の命令群に分割される（ステップＳ１）。
【００３８】
次に、優先度設定部３によって、命令群毎に、命令群内の各命令に命令単位優先度が設定されるとともに、各命令群に命令群別優先度が設定される（ステップＳ２）。
【００３９】
次に、命令スケジューリング部４によって、命令群別優先度が最も高い命令群に含まれる命令が、命令単位優先度に基づいてスケジューリングされる（ステップＳ３）。ここで、命令スケジューリング部４は、この命令群内の命令で、情報処理装置９９で並列に実行可能な命令があれば並列に配置しながらこれらの命令をスケジューリングする。
【００４０】
次に、命令スケジューリング部４によって、ステップＳ３で生成された命令列の処理サイクルのうち、情報処理装置９９で他の命令群の命令を実行可能な処理サイクルがあるか否かが判断される（ステップＳ４）。
【００４１】
ここで、他の命令群の命令を実行可能な処理サイクルがあると判断された場合、命令スケジューリング部４によって、次に命令群別優先度が高い命令群に含まれる命令が命令単位優先度に基づいて順次選択され、これらの処理サイクルに配置される（ステップＳ５）。
【００４２】
次に、命令スケジューリング部４によって、次に命令群別優先度が高い命令群に含まれる残りの命令が、次の処理サイクルから順にスケジューリングされる（ステップＳ６）。
【００４３】
一方、ステップＳ４において、ステップＳ３で生成された命令列の処理サイクルに他の命令群の命令を実行可能なものがないと判断された場合も、ステップＳ６が実行される。
【００４４】
命令スケジューリング部４によって、全ての命令群がスケジューリングされるまで（ステップＳ７でＹｅｓ）、ステップＳ４〜Ｓ７が繰り返される。
【００４５】
全ての命令群のスケジューリングが完了すると、命令スケジューリング装置１は動作を終了する。
【００４６】
次に、本発明の第１の実施の形態の効果について述べる。
【００４７】
本発明の第１の実施の形態としての命令スケジューリング装置は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成することができる。
【００４８】
その理由は、まず、命令群別優先度の高い命令群のスケジューリングを完了させ、情報処理装置で他の命令を実行可能な処理サイクルに、命令群別優先度が次に高い命令群に属する命令も並行に実行するようスケジューリングを行い、実機で並列実行可能でない命令を並列に配置しないからである。
【００４９】
これにより、本発明の第１の実施の形態としての命令スケジューリング装置は、必要以上に並行処理を行わない命令スケジューリングを実現し、並行配置される他の命令によって、開始した１つの処理の完了が遅延することを防止することができる。
【００５０】
次に、本発明の第２の実施の形態としての命令スケジューリング装置１０の構成について図３を用いて説明する。
【００５１】
図３において、命令スケジューリング装置１０は、機能ブロックとして、命令ブロック入力部１１と、ＤＡＧ（無閉路有向グラフ）構築部１２と、ＤＡＧ分割部１３と、優先度設定部１４と、命令スケジューリング部１６と、命令ブロック出力部１７と、を備えている。
【００５２】
ここで、命令スケジューリング装置１０は、本発明の第１の実施の形態と同様な汎用的なコンピュータ装置によって構成される。また、命令ブロック入力部１１と、ＤＡＧ構築部１２と、ＤＡＧ分割部１３と、優先度設定部１４と、命令スケジューリング部１６と、命令ブロック出力部１７とは、プログラムモジュールとして記憶装置に記憶され、ＣＰＵによってＲＡＭに読み込まれて実行される回路として構成される。
【００５３】
命令ブロック入力部１１は、情報処理装置９９に実行させるソースコードの命令列を命令ブロック単位で読み込む。なお、ソースコードの命令列は、命令スケジューリング装置１０の外部の装置によってブロックに分割されている。
【００５４】
また、命令ブロック入力部１１は、読み込んだソースコードの命令列を、アセンブラコードに即した命令列である中間言語１００に変換する。例えば、命令ブロック入力部１１は、図２１の（ａ）に示したソースコードから（ｂ）に示した中間言語１００を生成する。
【００５５】
ＤＡＧ構築部１２は、中間言語１００を解析し、命令間の依存関係に基づいてＤＡＧ２００を構築する。ＤＡＧ２００の一例を図４に示す。
【００５６】
ここで、一般的なＤＡＧは、ノードと、ノード間を結ぶエッジとによって構成され、非循環でエッジが方向性を持つグラフである。ＤＡＧ内のノードのうち、他のノードから依存されないノードは根ノードと呼ばれ、他のノードに依存しないノードは葉ノードと呼ばれる。一般的なＤＡＧは、ノード間の依存関係を表現するために用いられる。
【００５７】
ＤＡＧ構築部１２は、中間言語１００におけるデータ（図４のｉ、ｊ、＆ｙ、＆ｚなど）または命令の計算結果（図４のｔ２、ｔ３など）をノードで表し、データから計算結果への依存関係をエッジで表すようＤＡＧ２００を構築する。
【００５８】
ここで、このような依存関係を表すエッジを、以下、依存のエッジと呼ぶ。図４において、依存のエッジは、データを表すノードから計算結果を表すノードへの方向を持った実線矢印で表される。
【００５９】
また、ＤＡＧ構築部１２は、ＤＡＧ２００を構成するエッジに、データが取得されて命令の表す計算が開始されてから計算結果が得られるまでの時間(サイクル数)を付す。これにより、ＤＡＧ２００において、エッジの表す依存関係が解消されるまでに要する時間が表現される。
【００６０】
また、ＤＡＧ構築部１２は、ＤＡＧ２００を構成するノードのうち、他のノードより先に処理される必要のあるノードが存在する場合、先に処理される必要のあるノードから後に処理されるノードへ、非実線エッジを張り、制約のある依存関係を表す。このようなエッジを、以下、制約のエッジと呼ぶ。なお、制約のエッジは、図４の例では図示されていない。
【００６１】
例えば、元のソースコードに、同一のメモリに対する読む命令（１）と書く命令（２）とがこの順に含まれる場合、命令を並べ替えた後も命令（１）および命令（２）は、ソースコードの順に従って処理される制約が生ずる。このような場合、ＤＡＧ構築部１２は、命令（１）の計算結果を表すノードから命令（２）の計算結果を表すノードへ制約のエッジを張る。
【００６２】
ＤＡＧ分割部１３は、ＤＡＧ２００において、根ノードから依存のエッジだけをエッジと逆方向に辿ることにより、依存関係のある一連の命令を表すノードとエッジを抽出する。そして、ＤＡＧ分割部１３は、抽出したノードとエッジを１つの部分ＤＡＧとする。
【００６３】
また、ＤＡＧ分割部１３は、ＤＡＧ２００を部分ＤＡＧ３０１および部分ＤＡＧ３０２（以下、総称して部分ＤＡＧ３００ともいう）に分割する。ここで、部分ＤＡＧ３０１の一例を図５に示し、部分ＤＡＧ３０２の一例を図６に示す。
【００６４】
図５の部分ＤＡＧ３０１は、図４に示したＤＡＧ２００の根ノード「ｔ７［０］」から依存のエッジが辿られて分割されたものである。
【００６５】
また、図６の部分ＤＡＧ３０２は、ＤＡＧ２００の根ノード「ｔ７［４］」から依存のエッジが辿られて分割されたものである。
【００６６】
すなわち、ＤＡＧ分割部１３は、ＤＡＧ２００に根ノードが２つ含まれる場合、ＤＡＧ２００を２つの部分ＤＡＧ３００に分割する。
【００６７】
なお、本実施の形態において、ＤＡＧ分割部１３がＤＡＧ２００を２つの部分ＤＡＧ３００に分割する例について説明しているが、本発明において、ＤＡＧ分割手段が分割する部分ＤＡＧの数を限定するものではない。
【００６８】
ＤＡＧ分割部１３は、同一のノードやエッジが異なる部分ＤＡＧ３００に重複して含まれるようにＤＡＧ２００を分割する場合もある。
【００６９】
例えば、図４〜図６において、ＤＡＧ２００に含まれるノード２００１およびノード２００１が依存するノード、ノード２００２およびノード２００２が依存するノード、ならびにノード２００３およびノード２００３が依存するノードは、根ノード「ｔ７［０］」からも、根ノード「ｔ７［４］」からも依存されているため、部分ＤＡＧ３０１および部分ＤＡＧ３０２の両方に含まれている。
【００７０】
優先度設定部１４は、各部分ＤＡＧ３００の各ノードについて、命令単位優先度を計算し対応付ける。
【００７１】
優先度設定部１４は、例えば、ある命令の処理を開始してから、その命令の処理結果に依存する全ての命令の処理を完了するまでの時間(サイクル数)を命令単位優先度として設定する。すなわち、優先度設定部１４は、部分ＤＡＧ３００内の各ノードについて、該当するノードが依存するノードをたどって根ノードにたどりつくまでのエッジに付されたサイクル数を合計したものを命令単位優先度として対応付ける。
【００７２】
優先度設定部１４によって、部分ＤＡＧ３０１の各ノードに命令単位優先度が対応付けられた部分ＤＡＧ３０１ａの一例を図７に示す。また、部分ＤＡＧ３０２の各ノードに命令単位優先度が対応付けられた部分ＤＡＧ３０２ａの一例を図８に示す。図７、図８において、各ノードの右側に記載された数字が命令単位優先度を表す。数字が大きいほど優先度が高いことを表す。
【００７３】
このように、優先度設定部１４は、部分ＤＡＧ３００内で完了までの時間が長い命令に高い優先度を設定することにより、複数の命令を同時に実行させる命令列を生成する可能性を高め、１つの処理の完了までの時間を減らす。
【００７４】
また、優先度設定部１４は、各部分ＤＡＧ３００について、内部のノードに対応付けられた命令単位優先度のうち最も高いものがより高い部分ＤＡＧに、より高い命令群別優先度を設定する。
【００７５】
すなわち、優先度設定部１４は、部分ＤＡＧ３００が表す命令群による一連の処理の完了までにより多くの時間を要する命令群ほど、より高い命令群別優先度を設定する。
【００７６】
なお、優先度設定部１４は、内部のノードに対応付けられた命令単位優先度のうち最も高いものが同一の命令群については、命令ブロック入力部１１で入力された命令列において先に出現する命令に関連する命令群により高い命令群別優先度を設定するようにしてもよい。
【００７７】
命令スケジューリング部１６は、各部分ＤＡＧ３００に対応付けられた命令群別優先度、および、各部分ＤＡＧ３００内のノードに対応付けられた命令単位優先度に基づいて、命令を並べ替えて命令列を生成する。
【００７８】
詳細には、命令スケジューリング部１６は、ｉ（ｉは１以上の整数）番目に高い命令群別優先度が対応付けられた部分ＤＡＧ３００内の命令をまず完了させて命令列を生成した後、生成した命令列のうち、情報処理装置９９によって他の命令を並列実行可能な処理サイクルに、ｉ＋１番目に高い命令群別優先度が対応付けられた命令群内の命令を配置する。
【００７９】
このようにして、命令スケジューリング部１６は、全ての命令群の命令について順次スケジューリングを行い命令列７００を生成する。
【００８０】
命令ブロック出力部１７は、命令列７００を、外部へ出力する。なお、出力された命令列７００は、命令スケジューリング装置１０の外部の装置によってアセンブラコードおよび情報処理装置９９によって実行可能なマシンコードに変換される。
【００８１】
以上のように構成された命令スケジューリング装置１０の動作について、図９〜図１１を用いて説明する。
【００８２】
まず、命令ブロック入力部１１によって、ソースコードの命令列が命令ブロック単位で読み込まれ、中間言語１００に変換される（ステップＳ１１）。
【００８３】
次に、ＤＡＧ構築部１２によって、中間言語１００の命令間の依存関係が分析され、ＤＡＧ２００が構築される（ステップＳ１２）。
【００８４】
次に、ＤＡＧ分割部１３によって、ＤＡＧ２００が、依存関係のある一連の命令群をそれぞれ表す複数の部分ＤＡＧ３００に分割される（ステップＳ１３）。
【００８５】
次に、優先度設定部１４によって、各部分ＤＡＧ３００の各ノードに命令単位優先度が対応付けられる（ステップＳ１４）。
【００８６】
次に、優先度設定部１４によって、各部分ＤＡＧ３００に対して命令群別優先度が設定される（ステップＳ１５）。ステップＳ１５の処理の詳細については後述する。
【００８７】
次に、命令スケジューリング部１６によって、各部分ＤＡＧ３００に基づいて、命令列７００が生成される（ステップＳ１６）。ステップＳ１６の処理の詳細については後述する。
【００８８】
次に、命令ブロック出力部１７によって、命令列７００が出力される（ステップＳ１７）。
【００８９】
ここで、ステップＳ１５において、優先度設定部１４によって各部分ＤＡＧ３００に命令群別優先度が設定される動作について、図１０を用いて説明する。
【００９０】
ここでは、まず、優先度設定部１４によって、命令群別優先度が未設定の命令群があるか否かが判断される（ステップＳ２１）。
【００９１】
ここで、未設定の命令群があると判断された場合、優先度設定部１４によって、未設定の命令群のうち、命令群内のノードに対応付けられた最高の命令単位優先度が一番低い命令群が選択される（ステップＳ２２）。
【００９２】
次に、優先度設定部１４によって、選択された命令群に対して、前回選択した命令群に対して設定した優先度より大きい優先度が、今回選択した命令群に対して設定される（ステップＳ２３）。例えば、優先度設定部１４によってｎ回目のステップＳ２３で選択された命令群には、命令群別優先度ｎが設定されてもよい。
【００９３】
以上で、優先度設定部１４による命令群別優先度の設定動作が終了する。
【００９４】
ここで、命令群別優先度の設定動作の一例として、図７および図８に示した部分ＤＡＧ３０１ａおよび部分ＤＡＧ３０２ａに命令群別優先度が設定される動作を説明する。
【００９５】
まず、優先度設定部１４によって、１回目のステップＳ２１〜Ｓ２３が実行される。
【００９６】
すなわち、優先度設定部１４によって、命令群別優先度が未設定の部分ＤＡＧ３００が残っているかどうかが判断される。ここでは、部分ＤＡＧ３０１ａおよび部分ＤＡＧ３０２ａが残っていると判断される（ステップＳ２１でＹｅｓ）。
【００９７】
次に、優先度設定部１４によって、未設定の部分ＤＡＧ３００のうち、部分ＤＡＧ内で最高の命令単位優先度が最も低いものが選択される。このとき、部分ＤＡＧ３０１ａおよび部分ＤＡＧ３０２ａ内で最高の命令単位優先度はそれぞれ１１で等しい。
【００９８】
この場合は、優先度設定部１４によって、命令ブロック入力部１１で入力された命令列に後に出現する命令が含まれる部分ＤＡＧ３００が選択される。ここでは、部分ＤＡＧ３０２ａにのみ属する命令が後に出現するため、部分ＤＡＧ３０２ａが選択される（ステップＳ２２）。
【００９９】
なお、優先度設定部１４が、最高の命令単位優先度が等しい部分ＤＡＧ３００を選択する順序は、他の順序であってもよい。
【０１００】
次に、優先度設定部１４によって、１回目に選択された部分ＤＡＧ３０２ａに、命令群別優先度1が設定される（ステップＳ２３）。
【０１０１】
次に、優先度設定部１４によって、２回目のステップＳ２１〜Ｓ２３が実行される。
【０１０２】
すなわち、優先度設定部１４によって、命令群別優先度が未設定の部分ＤＡＧ３００が残っているかどうかが判断される。ここでは、部分ＤＡＧ３０１ａが残っていると判断される（ステップＳ２１でＹｅｓ）。
【０１０３】
次に、優先度設定部１４によって、未設定の部分ＤＡＧ３００のうち、部分ＤＡＧ内で最高の命令単位優先度が最も低いものが選択される。ここでは、未設定の部分ＤＡＧは部分ＤＡＧ３０１ａのみなので、部分ＤＡＧ３０１ａが選択される（ステップＳ２２）。
【０１０４】
次に、優先度設定部１４によって、２回目に選択された部分ＤＡＧ３０２ａに、命令群別優先度２が設定される（ステップＳ２３）。
【０１０５】
次に、優先度設定部１４によって、３回目のステップＳ２１が実行される。
【０１０６】
すなわち、優先度設定部１４によって、命令群別優先度が未設定の部分ＤＡＧ３００が残っているかどうかが判断される。ここでは、未設定の部分ＤＡＧ３００が残っていないと判断され（ステップＳ２１でＮｏ）、命令群別優先度の設定動作が終了する。
【０１０７】
次に、図９のステップＳ１６において、命令スケジューリング部１６による命令列７００の生成動作について、図２および図１１を用いて詳細に説明する。図１１において、各処理サイクルに命令がスケジューリングされている。図１１（ａ）、（ｂ）において、命令の左側の番号が処理リサイクルの順番を表す。
【０１０８】
命令スケジューリング部１６は、ステップＳ１６において、本発明の第１の実施の形態に係る命令スケジューリング部４と同様に図２に示したステップＳ３〜Ｓ７の動作を実行する。
【０１０９】
ここでは、命令スケジューリング部１６が、図７および図８に示した部分ＤＡＧ３００に基づいて命令列を生成する動作についてステップＳ３〜Ｓ７に沿って説明する。
【０１１０】
なお、ここでは、情報処理装置９９が同一の処理サイクルで並列に実行できる命令には次のような制約があるものとする。
・ロード命令（ｌｄ）同士は並列に実行できない。
・ストア命令（ｓｔ）同士は並列に実行できない。
・ロード命令およびストア命令は並列に実行できない。
・上記以外の組合せの命令は２命令並列に実行できる。
【０１１１】
また、情報処理装置９９は、各命令の実行に以下のサイクル数を必要するものとする。
・ロード命令の完了までに３サイクル
・その他の命令の完了までに1サイクル
まず、命令スケジューリング部１６によって、より高い命令群別優先度２が対応付けられた部分ＤＡＧ３０１ａ内の命令についてスケジューリングが行われ、図１１（ａ）に示す命令列が生成される（ステップＳ３）。
【０１１２】
次に、命令スケジューリング部１６によって、生成された命令列のうち、図１１（ａ）の処理サイクル８、９および１２に、情報処理装置９９で他の命令を実行可能な余裕があると判断される（ステップＳ４でＹｅｓ）。
【０１１３】
そこで、命令スケジューリング部１６によって、次に高い命令群別優先度１が対応付けられた部分ＤＡＧ３０２ａ内の命令のうち、命令単位優先度の高い命令から順に３つの命令が、処理サイクル８、９および１２に配置される（ステップＳ５）。
【０１１４】
次に、命令スケジューリング部１６によって、次に高い命令群別優先度１が対応付けられた部分ＤＡＧ３０２ａ内の残りのノードに対応する命令が、命令単位優先度の高いものから順に処理サイクル１３および１４に配置され（ステップＳ６）、図１１（ｂ）に示す命令列７００が生成される。
【０１１５】
次に、命令スケジューリング部１６によって、命令群を表す部分ＤＡＧ３００の全てについて処理が完了したと判断され（ステップＳ７でＹｅｓ）、命令列７００の生成動作が終了する。
【０１１６】
以上のように命令スケジューリング装置１０によって生成された命令列７００と、関連技術の命令スケジューリング装置によって生成された命令列との比較を図１２に示す。
【０１１７】
ここで、関連技術の命令スケジューリング装置は、命令単位優先度のみに基づいて命令列を生成しているものとする。
【０１１８】
関連技術の命令スケジューリング装置は、図１２（ａ）に示すように、x[j+0]の処理に関連する一連の命令に１４サイクル要する命令列を生成している。これに対して、本発明の第２の実施の形態としての命令スケジューリング装置１０は、図１２（ｂ）に示すように、x[j+0]の処理に関連する一連の命令を１２サイクルで完了させる命令列を生成することができ、x[j+0]の処理の遅延を抑えている。
【０１１９】
また、関連技術の命令スケジューリング装置は、図１２（ａ）に示すように、x[j+0]の処理に必要とするレジスタｒ１５をサイクル１４で解放可能にする。これに対して、本発明の第２の実施の形態としての命令スケジューリング装置１０は、図１２（ｂ）に示すように、レジスタｒ１５をサイクル１２で解放可能にすることができ、レジスタの利用期間を短縮している。
【０１２０】
また、関連技術の命令スケジューリング装置は、図１２（ａ）に示すように、x[j+0]およびx[j+1]の処理として、全体で１５サイクルの命令列を生成している。これに対して、本発明の第２の実施の形態としての命令スケジューリング装置１０は、x[j+0]およびx[j+1]の処理として、全体で１４サイクルの命令列を生成することができ、全体としての処理の完了の遅延も抑えることができる。
【０１２１】
次に、本発明の第２の実施の形態の効果について述べる。
【０１２２】
本発明の第２の実施の形態としての命令スケジューリング装置は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を、ＤＡＧを利用して効率的に生成することができる。
【０１２３】
その理由は、依存関係のある一連の命令を部分ＤＡＧで表し、部分ＤＡＧの各ノードに命令単位優先度を対応付け、部分ＤＡＧに命令群別優先度を対応付け、部分ＤＡＧに基づいて命令スケジューリングを行うからである。
【０１２４】
また、本発明の第２の実施の形態としての命令スケジューリング装置は、計算中に同時に必要になるレジスタの数を抑えた命令列を生成することができる。
【０１２５】
その理由は、開始した処理の遅延を抑えた命令列を生成することにより、処理中に利用が開始されるレジスタを、処理の完了と共に遅延なく解放できるからである。
【０１２６】
例えば、関連技術の命令スケジューリング装置は、３つの独立した処理を行うソースコードに対して、３つの処理を並行に実行する命令列を生成する場合があり、３つの処理に関連するレジスタが同時に必要になる場合があった。
【０１２７】
本発明の第２の実施の形態の命令スケジューリング装置は、３つの独立した処理を行うソースコードに対しても、１つの処理を表す命令群別に命令群別優先度を設定して、命令群別優先度の高い順に並べ替える。その結果、本発明の第２の実施の形態の命令スケジューリング装置は、１つ目の処理を開始し、その処理の終了の間際に２つ目の処理を開始し、その処理の終了間際に３つ目の処理を開始するような命令列を生成する。このような命令列では、並行して実行される命令が高々２つに抑えられる。
【０１２８】
したがって、本発明の第２の実施の形態の命令スケジューリング装置は、同時に必要なレジスタを高々２つの処理に関連するものに抑えた命令列を生成することができる。
【０１２９】
次に、本発明の第３の実施の形態について、図面を参照して詳細に説明する。
【０１３０】
本発明の第３の実施の形態としての命令スケジューリング装置２０の構成を図１３に示す。
【０１３１】
図１３において、命令スケジューリング装置２０は、本発明の第２の実施の形態の命令スケジューリング装置１０に対して、優先度設定部１４に替えて優先度設定部２４を備え、命令スケジューリング部１６に替えて命令スケジューリング部２６を備え、さらにＤＡＧ統合部２５を備える点が異なる。
【０１３２】
ここで、命令スケジューリング装置２０は、本発明の第２の実施の形態と同様な汎用的なコンピュータ装置によって構成される。また、優先度設定部２４と、ＤＡＧ統合部２５と、命令スケジューリング部２６とは、プログラムモジュールとして記憶装置に記憶され、ＣＰＵによってＲＡＭに読み込まれて実行される回路として構成される。
【０１３３】
優先度設定部２４は、本発明の第２の実施の形態における優先度設定部１４と同様に命令単位優先度および命令群別優先度を設定する。
【０１３４】
また、優先度設定部２４は、さらに、各部分ＤＡＧを構成する各ノードに、該ノードが含まれる部分ＤＡＧに設定された命令群別優先度および各ノードに設定された命令単位優先度からなる２段階優先度を対応付ける。
【０１３５】
優先度設定部２４によって、部分ＤＡＧ３０１の各ノードに２段階優先度が対応付けられた部分ＤＡＧ３０１ｂを図１４に示す。また、部分ＤＡＧ３０２の各ノードに２段階優先度が対応付けられた部分ＤＡＧ３０２ｂを図１５に示す。
【０１３６】
図１４および図１５において、２段階優先度を「命令群別優先度：命令単位優先度」と表記している。
【０１３７】
ＤＡＧ統合部２５は、分割した部分ＤＡＧ３００を、元のＤＡＧ２００と同様の形に統合した統合ＤＡＧ６００を生成する。
【０１３８】
また、ＤＡＧ統合部２５は、統合ＤＡＧ６００内の各ノードに、優先度設定部２４によって設定された２段階優先度を対応付ける。
【０１３９】
このとき、ＤＡＧ統合部２５は、統合ＤＡＧ６００内のノードのうち、複数の部分ＤＡＧ３００に含まれていたノードに対しては、以下のように２段階優先度を対応付ける。
・命令群別優先度が異なる場合は、命令群別優先度が高い方の２段階優先度を選択して対応付ける。
・命令群別優先度が等しい場合は、命令単位優先度が高い方の２段階優先度を選択して対応付ける。
【０１４０】
部分ＤＡＧ３０１および部分ＤＡＧ３０２が統合された統合ＤＡＧ６００の一例を図１６に示す。
【０１４１】
命令スケジューリング部２６は、統合ＤＡＧ６００内の各ノードに対応付けられた２段階優先度に基づいて、より高い命令群別優先度でより高い命令単位優先度の命令から順に各処理サイクルに配置していく。
【０１４２】
このとき、命令スケジューリング部２６は、各処理サイクルに命令を配置する際に、該処理サイクルで他の命令群の命令を実行可能であるか否かを判断し、実行可能であれば、次に高い命令群別優先度の命令を該処理サイクルに配置する。
【０１４３】
以下、「より高い命令群別優先度が含まれる２段階優先度が対応付けられたノードに対応する命令」のことを、単に「より高い命令群別優先度の命令」ともいう。また、「より高い命令単位優先度が含まれる２段階優先度が対応付けられたノードに対応する命令」のことを、単に「より高い命令単位優先度の命令」ともいう。
【０１４４】
具体的には、命令スケジューリング部２６は、ｉ番目に高い命令群別優先度の命令について、命令単位優先度に基づいて各処理サイクルに配置していく。このとき、命令スケジューリング部２６は、命令を配置する処理サイクルで情報処理装置９９によって他の命令を並列実行可能か否かを判断する。そして、命令スケジューリング部２６は、他の命令を並列実行可能であれば、ｉ＋１番目に高い命令群別優先度の命令を該処理サイクルに配置する。
【０１４５】
このようにして、命令スケジューリング部２６は、ｉ＋１番目に命令群別優先度の高い命令を配置可能な処理サイクルには該命令を配置しながら、ｉ番目に命令群別優先度の高い命令のスケジューリングを完了させる。
【０１４６】
このようにして、命令スケジューリング部１６は、統合ＤＡＧ６００内のノードに対応する全ての命令について並べ替えを行い命令列７００を生成する。
【０１４７】
以上のように構成された命令スケジューリング装置２０の動作について、図１７を用いて説明する。
【０１４８】
なお、図１７において、本発明の第２の実施の形態としての命令スケジューリング装置１０と同様に動作するステップについては同一の符号を付して詳細な説明を省略する。
【０１４９】
命令スケジューリング装置２０は、ステップＳ１１〜Ｓ１５まで本発明の第２の実施の形態としての命令スケジューリング装置１０と同様に動作して部分ＤＡＧ３００を生成し、命令単位優先度および命令群別優先度を設定する。
【０１５０】
次に、命令単位優先度および命令群別優先度からなる２段階優先度が、優先度設定部２４によって、各部分ＤＡＧ３００の各ノードに対応付けられる（ステップＳ３６）。
【０１５１】
次に、部分ＤＡＧ３００が統合された統合ＤＡＧ６００が、ＤＡＧ統合部２５によって生成される（ステップＳ３７）。
【０１５２】
次に、統合ＤＡＧ６００に基づいて、命令スケジューリング部２６によって命令が並べ替えられ、命令列７００が生成される（ステップＳ３８）。
【０１５３】
ここで、ステップＳ３８における命令スケジューリング部２６の命令スケジューリング動作について、図１８を用いて説明する。
【０１５４】
ここでは、命令スケジューリング部２６によって、命令群別優先度が高いものから順に、命令群別優先度が同一の命令についてステップＳ４１〜Ｓ４４が実行される。
【０１５５】
まず、命令スケジューリング部２６によって、この命令群別優先度で次に命令単位優先度が高い命令が次の処理サイクルに配置可能であれば配置される（ステップＳ４１）。
【０１５６】
ここで、この命令群別優先度でさらに次に高い命令単位優先度の命令がこの処理サイクルに並列に配置可能であればこれらの命令がこの処理サイクルに並列に配置される。また、この命令群別優先度の命令でこの処理サイクルに配置可能なものがなければ、この命令群別優先度の命令はこの処理サイクルに配置されない。
【０１５７】
次に、命令スケジューリング部２６によって、この処理サイクルで他の命令群別優先度の命令が実行可能か否かが判断される（ステップＳ４２）。
【０１５８】
ここで、該当する処理サイクルで他の命令群別優先度の命令が実行可能でないと判断されると、命令スケジューリング部２６の処理はステップＳ４１に戻る。
【０１５９】
一方、該当する処理サイクルで他の命令群別優先度の命令が実行可能であると判断されると、命令群スケジューリング部２６によって、次に命令群別優先度が高い命令のうち命令単位優先度が高いものが該当する処理サイクルに配置される（ステップＳ４３）。
【０１６０】
このようにして、この命令群別優先度の命令のスケジューリングが完了すると（ステップＳ４４でＹｅｓ）、命令スケジューリング部２６によって、次に命令群別優先度が高い命令のうち未配置の命令について、ステップＳ４１〜Ｓ４４が繰り返し実行される。
【０１６１】
命令スケジューリング部２６によって、全ての命令群別優先度の命令のスケジューリングが完了すると、命令スケジューリング動作が終了する。
【０１６２】
例えば、命令スケジューリング部２６が、図１６に示した統合ＤＡＧ６００に基づいて、図１２（ｂ）に示した命令列７００を生成する例について説明する。
【０１６３】
命令スケジューリング部２６は、まず、命令群別優先度２の命令を、命令単位優先度に基づいて図１２（ｂ）の処理サイクル０に配置する（ステップＳ４１）。このとき、命令スケジューリング部２６は、命令群別優先度２の２つの命令を並列に配置可能であるため並列に配置する。
【０１６４】
次に、命令スケジューリング部２６は、この処理サイクル０で他の命令群別優先度の命令を実行可能でないと判断する（Ｓ４２でＮｏ）。
【０１６５】
命令スケジューリング部２６は、ステップＳ４１の処理およびステップＳ４２でＮｏの判断を繰り返して図１２（ｂ）の処理サイクル０〜７までスケジューリングを行う。
【０１６６】
次に、命令スケジューリング部２６は、次の処理サイクル８には、命令群別優先度２内の命令で配置可能なものがないため配置しない（ステップＳ４１）。
【０１６７】
ここで、命令スケジューリング部２６は、この処理サイクル８で他の命令群別優先度の命令を実行可能であると判断し（ステップＳ４２でＹｅｓ）、命令群別優先度１の命令のうち、２段階優先度「１：３」が対応付けられた「t8へのロード命令」を選択し処理サイクル８に配置する（ステップＳ４３）。
【０１６８】
次に、命令スケジューリング部２６は、さらに次の処理サイクル９にも、命令群別優先度２内の命令で配置可能なものがないため配置しない（ステップＳ４１）。
【０１６９】
ここで、命令スケジューリング部２６は、この処理サイクル９で他の命令群別優先度の命令を実行可能であると判断し（ステップＳ４２でＹｅｓ）、命令群別優先度１の命令のうち、２段階優先度「１：３」が対応付けられた「t9へのロード命令」を選択し処理サイクル９に配置する（ステップＳ４３）。
【０１７０】
次に、命令スケジューリング部２６は、命令群別優先度２の残りの命令について、ステップＳ４１の処理およびステップＳ４２でＮｏの判断を繰り返して図１２（ｂ）の処理サイクル１０〜１２までスケジューリングを行う。
【０１７１】
次に、命令スケジューリング部２６は、処理サイクル１２で他の命令群内の命令を実行可能であると判断し（ステップＳ４２でＹｅｓ）、命令群別優先度１の命令を処理サイクル１２に配置する（ステップＳ４３）。
【０１７２】
これで、命令スケジューリング部２６は、命令群別優先度２の命令群内の命令のスケジューリングを終えたと判断し（ステップＳ４４でＹｅｓ）、次の命令群別優先度１の命令群内の命令のスケジューリングに処理を移す。
【０１７３】
次に、命令スケジューリング部２６は、命令群別優先度１の残りの命令について、ステップＳ４１〜Ｓ４２を繰り返し、処理サイクル１３〜１４に配置する。
【０１７４】
これで、命令スケジューリング部２６は、全ての命令のスケジューリングを終え、命令列７００の生成を終了する。
【０１７５】
このように、命令スケジューリング部２６は、命令スケジューリング部１６と同様の命令列７００を、命令スケジューリング部１６に比べて簡略化された処理手順で生成する。
【０１７６】
次に、本発明の第３の実施の形態の効果について述べる。
【０１７７】
本発明の第３の実施の形態としての命令スケジューリング装置は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を、さらに効率的に生成することができる。
【０１７８】
その理由は、各ノードに２段階優先度を対応付けた統合ＤＡＧを生成することにより、命令群毎の命令スケジューリングを完了させてから次の命令群の命令を前の命令群の命令列にマージする必要がなく、簡略化された生成手順で命令列の生成時間を短縮することができるからである。
【０１７９】
次に、本発明の第４の実施の形態について、図面を参照して説明する。
【０１８０】
本発明の第４の実施の形態の命令スケジューリング装置３０の構成を図１９に示す。
【０１８１】
図１９において、命令スケジューリング装置３０は、本発明の第３の実施の形態の命令スケジューリング装置２０に対して、ＤＡＧ分割部１３に替えてＤＡＧ分割部３３を備え、優先度設定部２４に替えて優先度設定部３４を備え、ＤＡＧ統合部２５に替えてＤＡＧ統合部３５を備える点が異なる。
【０１８２】
ここで、命令スケジューリング装置３０は、本発明の第３の実施の形態と同様な汎用的なコンピュータ装置によって構成される。また、ＤＡＧ分割部３３と、優先度設定部３４と、ＤＡＧ統合部３５とは、プログラムモジュールとして記憶装置に記憶され、ＣＰＵによってＲＡＭに読み込まれて実行される回路として構成される。
【０１８３】
ＤＡＧ分割部３３は、ＤＡＧ構築部１２によって構成されたＤＡＧ２００の各ノードに、依存関係のある一連の命令群を識別する命令群識別情報を対応付ける。ここで、ＤＡＧ分割部３３は、複数の命令群に含まれるノードには、複数の命令群識別情報を対応付ける。これにより、ＤＡＧ分割部３３は、ＤＡＧ２００を複数の部分ＤＡＧ３００に仮想的に分割する。
【０１８４】
優先度設定部３４は、ＤＡＧ２００の各ノードに対応付けられた命令群識別情報に、２段階優先度を対応付ける。ここで、優先度設定部３４は、複数の命令群に含まれ複数の命令群識別情報が対応付けられたノードには、各命令群識別情報に対して２段階優先度を対応付ける。
【０１８５】
ＤＡＧ統合部３５は、複数の２段階優先度が対応付けられたノードについて、いずれかの２段階優先度を選択したことを表す選択情報を対応付ける。例えば、ＤＡＧ統合部３５は、複数の２段階優先度のうち、命令群別優先度が高い方の２段階優先度を選択したことを表す選択情報を、該当するノードに対応付ける。この場合、ＤＡＧ統合部３５は、複数の２段階優先度の命令群別優先度が同一であれば、命令単位優先度が高い方の２段階優先度を選択したことを表す選択情報を、該当するノードに対応付ける。
【０１８６】
これにより、ＤＡＧ統合部３５は、仮想的に分割された複数の部分ＤＡＧを仮想的に統合する。
【０１８７】
ＤＡＧ分割部３３、優先度設定部３４およびＤＡＧ統合部３５によって、命令群識別情報、２段階優先度および選択情報が対応付けられたＤＡＧ２００のノードの一例を図２０に示す。
【０１８８】
以上のように構成された命令スケジューリング装置３０は、各ノードに２段階優先度の選択情報が対応付けられたＤＡＧ２００を、本発明の第３の実施の形態における統合ＤＡＧ６００とみなすことにより、本発明の第３の実施の形態としての命令スケジューリング装置２０と同様に動作して、命令列７００を生成する。
【０１８９】
本発明の第４の実施の形態の効果について述べる。
【０１９０】
本発明の第４の実施の形態としての命令スケジューリング装置は、処理の遅延を抑えてレジスタの利用期間を短縮する命令列を生成する際の、メモリ使用量および生成時間を短縮することができる。
【０１９１】
その理由は、本発明の第４の実施の形態としての命令スケジューリング装置は、構築したＤＡＧを用いて部分ＤＡＧおよび統合ＤＡＧを仮想的に生成するので、部分ＤＡＧおよび統合ＤＡＧを表す情報を生成する時間を短縮することができ、部分ＤＡＧおよび統合ＤＡＧを表す情報を記憶するためのメモリ領域を必要としないからである。
【０１９２】
なお、上述した本発明の各実施の形態において、命令スケジューリング装置の動作は、本発明の命令スケジューリングプログラムを構成するプログラムモジュールとして命令スケジューリング装置が備える記憶装置に格納され、ＣＰＵによって実行されるようにしてもよい。
【０１９３】
また、上述した各実施の形態は、適宜組み合わせて実施されることが可能である。
【０１９４】
また、本発明は、上述した各実施の形態に限定されず、様々な態様で実施されることが可能である。
【符号の説明】
【０１９５】
１、１０、２０、３０ 命令スケジューリング装置
２ 命令群分割部
３ 優先度設定部
４ 命令スケジューリング部
１１ 命令ブロック入力部
１２ ＤＡＧ構築部
１３、３３ ＤＡＧ分割部
１４、２４、３４ 優先度設定部
１６、２６ 命令スケジューリング部
１７ 命令ブロック出力部
２５、３５ ＤＡＧ統合部
【特許請求の範囲】
【請求項１】
処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割手段と、
前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定手段と、
前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリング手段と、
を備えた命令スケジューリング装置。
【請求項２】
前記命令群分割手段は、
前記命令ブロックに含まれる複数の命令の依存関係を表すＤＡＧ（Directed Acyclic Graph）を構築するＤＡＧ構築手段と、
前記ＤＡＧを、前記複数の命令群をそれぞれ表す複数の部分ＤＡＧに分割するＤＡＧ分割手段と、
を有することを特徴とする請求項１に記載の命令スケジューリング装置。
【請求項３】
前記部分ＤＡＧを統合した統合ＤＡＧを生成するＤＡＧ統合手段をさらに備え、
前記優先度設定手段は、前記部分ＤＡＧを構成する各ノードに、前記ノードが含まれる部分ＤＡＧが表す命令群に設定した命令群別優先度および前記ノードが表す命令に設定した命令単位優先度からなる２段階優先度を対応付け、
前記ＤＡＧ統合手段は、前記統合ＤＡＧの各ノードのうち、複数の前記部分ＤＡＧに重複して含まれていたノードにはより高い命令群別優先度を含む２段階優先度を選択して対応付け、
前記命令スケジューリング手段は、前記統合ＤＡＧの各ノードに対応付けられた２段階優先度に基づいて前記命令を順次配置していき、各処理サイクルに前記命令を配置する際に該処理サイクルで前記情報処理装置によって他の命令群の命令を実行可能であるか否かを判断し、実行可能であれば次に高い命令群別優先度を含む２段階優先度が設定された命令を該処理サイクルに配置することを特徴とする請求項２に記載の命令スケジューリング装置。
【請求項４】
前記ＤＡＧ分割手段は、前記ＤＡＧを構成する各ノードに前記複数の命令群をそれぞれ識別する命令群識別情報を対応付けることにより前記ＤＡＧを前記部分ＤＡＧに仮想的に分割し、
前記優先度設定手段は、前記各ノードに対応付けられた命令群識別情報毎に前記２段階優先度を対応付け、
前記ＤＡＧ統合手段は、前記各ノードに対応付けられた命令群識別情報毎に対応づけられた２段階優先度のうち、より高い命令群別優先度を含む２段階優先度を前記各ノードに対応付けることにより、前記統合ＤＡＧを仮想的に生成することを特徴とする請求項３に記載の命令スケジューリング装置。
【請求項５】
前記優先度設定手段は、前記命令群に含まれる命令に設定した命令単位優先度のうち最も高いものに基づいて前記命令群に対する命令群別優先度を設定することを特徴とする請求項１から請求項４のいずれかに記載の命令スケジューリング装置。
【請求項６】
処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令をスケジューリングする命令スケジューリング装置が、
前記複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割ステップと、
前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定ステップと、
前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリングステップと、
を実行する命令スケジューリング方法。
【請求項７】
前記命令スケジューリング装置が、
前記命令群分割ステップにおいて、
前記命令ブロックに含まれる複数の命令の依存関係を表すＤＡＧ（Directed Acyclic Graph）を構築するＤＡＧ構築ステップと、
前記ＤＡＧを、前記複数の命令群をそれぞれ表す複数の部分ＤＡＧに分割するＤＡＧ分割ステップと、
を実行することを特徴とする請求項６に記載の命令スケジューリング方法。
【請求項８】
処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令をスケジューリングする命令スケジューリング装置に、
前記複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割ステップと、
前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定ステップと、
前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリングステップと、
を実行させる命令スケジューリングプログラム。
【請求項９】
前記命令スケジューリング装置に、
前記命令群分割ステップにおいて、
前記命令ブロックに含まれる複数の命令の依存関係を表すＤＡＧ（Directed Acyclic Graph）を構築するＤＡＧ構築ステップと、
前記ＤＡＧを、前記複数の命令群をそれぞれ表す複数の部分ＤＡＧに分割するＤＡＧ分割ステップと、
を実行させることを特徴とする請求項８に記載の命令スケジューリングプログラム。
【請求項１】
処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割手段と、
前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定手段と、
前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリング手段と、
を備えた命令スケジューリング装置。
【請求項２】
前記命令群分割手段は、
前記命令ブロックに含まれる複数の命令の依存関係を表すＤＡＧ（Directed Acyclic Graph）を構築するＤＡＧ構築手段と、
前記ＤＡＧを、前記複数の命令群をそれぞれ表す複数の部分ＤＡＧに分割するＤＡＧ分割手段と、
を有することを特徴とする請求項１に記載の命令スケジューリング装置。
【請求項３】
前記部分ＤＡＧを統合した統合ＤＡＧを生成するＤＡＧ統合手段をさらに備え、
前記優先度設定手段は、前記部分ＤＡＧを構成する各ノードに、前記ノードが含まれる部分ＤＡＧが表す命令群に設定した命令群別優先度および前記ノードが表す命令に設定した命令単位優先度からなる２段階優先度を対応付け、
前記ＤＡＧ統合手段は、前記統合ＤＡＧの各ノードのうち、複数の前記部分ＤＡＧに重複して含まれていたノードにはより高い命令群別優先度を含む２段階優先度を選択して対応付け、
前記命令スケジューリング手段は、前記統合ＤＡＧの各ノードに対応付けられた２段階優先度に基づいて前記命令を順次配置していき、各処理サイクルに前記命令を配置する際に該処理サイクルで前記情報処理装置によって他の命令群の命令を実行可能であるか否かを判断し、実行可能であれば次に高い命令群別優先度を含む２段階優先度が設定された命令を該処理サイクルに配置することを特徴とする請求項２に記載の命令スケジューリング装置。
【請求項４】
前記ＤＡＧ分割手段は、前記ＤＡＧを構成する各ノードに前記複数の命令群をそれぞれ識別する命令群識別情報を対応付けることにより前記ＤＡＧを前記部分ＤＡＧに仮想的に分割し、
前記優先度設定手段は、前記各ノードに対応付けられた命令群識別情報毎に前記２段階優先度を対応付け、
前記ＤＡＧ統合手段は、前記各ノードに対応付けられた命令群識別情報毎に対応づけられた２段階優先度のうち、より高い命令群別優先度を含む２段階優先度を前記各ノードに対応付けることにより、前記統合ＤＡＧを仮想的に生成することを特徴とする請求項３に記載の命令スケジューリング装置。
【請求項５】
前記優先度設定手段は、前記命令群に含まれる命令に設定した命令単位優先度のうち最も高いものに基づいて前記命令群に対する命令群別優先度を設定することを特徴とする請求項１から請求項４のいずれかに記載の命令スケジューリング装置。
【請求項６】
処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令をスケジューリングする命令スケジューリング装置が、
前記複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割ステップと、
前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定ステップと、
前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリングステップと、
を実行する命令スケジューリング方法。
【請求項７】
前記命令スケジューリング装置が、
前記命令群分割ステップにおいて、
前記命令ブロックに含まれる複数の命令の依存関係を表すＤＡＧ（Directed Acyclic Graph）を構築するＤＡＧ構築ステップと、
前記ＤＡＧを、前記複数の命令群をそれぞれ表す複数の部分ＤＡＧに分割するＤＡＧ分割ステップと、
を実行することを特徴とする請求項６に記載の命令スケジューリング方法。
【請求項８】
処理サイクル毎に複数の命令を並列に実行可能な情報処理装置に実行させる命令ブロックに含まれる複数の命令をスケジューリングする命令スケジューリング装置に、
前記複数の命令の依存関係を分析し、依存関係のある一連の命令を１つの命令群として前記命令ブロックを複数の命令群に分割する命令群分割ステップと、
前記命令に対して、該命令が含まれる命令群における処理順序の優先度を表す命令単位優先度を設定するとともに、前記命令群に対して、前記命令ブロックにおける処理順序の優先度を表す命令群別優先度を設定する優先度設定ステップと、
前記命令群別優先度の高い命令群から順に、該命令群に含まれる命令を前記命令単位優先度に基づいてスケジューリングし、該命令群内の命令が配置された処理サイクルのうち前記情報処理装置によって他の命令群の命令を並列実行可能な処理サイクルに、次に命令群別優先度の高い命令群に含まれる命令を前記命令単位優先度に基づいて配置する命令スケジューリングステップと、
を実行させる命令スケジューリングプログラム。
【請求項９】
前記命令スケジューリング装置に、
前記命令群分割ステップにおいて、
前記命令ブロックに含まれる複数の命令の依存関係を表すＤＡＧ（Directed Acyclic Graph）を構築するＤＡＧ構築ステップと、
前記ＤＡＧを、前記複数の命令群をそれぞれ表す複数の部分ＤＡＧに分割するＤＡＧ分割ステップと、
を実行させることを特徴とする請求項８に記載の命令スケジューリングプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１１−１９８１９８（Ｐ２０１１−１９８１９８Ａ）
【公開日】平成２３年１０月６日（２０１１．１０．６）
【国際特許分類】
【出願番号】特願２０１０−６５７０６（Ｐ２０１０−６５７０６）
【出願日】平成２２年３月２３日（２０１０．３．２３）
【出願人】（３９０００１３９５）ＮＥＣシステムテクノロジー株式会社 (438)
【Ｆターム（参考）】
【公開日】平成２３年１０月６日（２０１１．１０．６）
【国際特許分類】
【出願日】平成２２年３月２３日（２０１０．３．２３）
【出願人】（３９０００１３９５）ＮＥＣシステムテクノロジー株式会社 (438)
【Ｆターム（参考）】
[ Back to top ]