(57)【要約】      （修正有）【課題】命令セット及び構成の異なるプロセッサエレメントを複数備えたヘテロジニアス・マルチプロセッサシステムにおいて、マルチプロセッサシステム全体の処理能力を向上させる。【解決手段】予め設定した複数のタスクの依存関係に基づいて実行可能なタスクを抽出し（９１）、前記抽出したタスクの依存関係に基づいて前記複数の第１のプロセッサを汎用プロセッサグループに割り当て、前記第２のプロセッサをアクセラレータグループに割り当てて、予め設定したタスク毎の優先度に基づいて、前記抽出したタスクから割り当てを行うタスクを決定し、前記決定したタスクを前記第１のプロセッサで実行したときの実行コストと、前記タスクを前記第２のプロセッサで実行したときの実行コストとを比較し（９２）、前記比較の結果、前記実行コストが小さい方の汎用プロセッサグループまたはアクセラレータグループの一方に当該タスクを割り当てる（９３）。【選択図】図９
2007328415.tif 000002
【特許請求の範囲】
【請求項１】
第１の命令セットを実行する第１のプロセッサと、
前記第１のプロセッサとは異なる第２の命令セットを実行する第２のプロセッサと、
前記第１のプロセッサを複数含み、かつ、少なくとも一つの前記第２のプロセッサを含むヘテロジニアス・マルチプロセッサシステムにタスクを割り当てる制御方法であって、
予め設定した複数のタスクの依存関係に基づいて実行可能なタスクを抽出する処理と、
前記抽出したタスクの依存関係に基づいて前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理と、
前記第２のプロセッサをアクセラレータグループに割り当てる処理と、
予め設定したタスク毎の優先度に基づいて、前記抽出したタスクから割り当てを行うタスクを決定する処理と、
前記決定したタスクを前記第１のプロセッサで実行したときの実行コストと、前記タスクを前記第２のプロセッサで実行したときの実行コストとを比較する処理と、
前記比較の結果、前記実行コストが小さい方の汎用プロセッサグループまたはアクセラレータグループの一方に当該タスクを割り当てる処理と、
を含むことを特徴とするヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項２】
前記タスクを割り当てる処理は、
前記比較の結果、第２のプロセッサの実行コストが小さいときには、当該タスクを前記アクセラレータグループへ割り当てる処理と、
前記比較の結果、第１のプロセッサの実行コストが小さいときには、当該タスクを前記汎用プロセッサグループへ割り当てる処理と、
を含むことを特徴とする請求項１に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項３】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記抽出したタスクの依存関係が並列性を持つ場合には、前記第１のプロセッサを前記並列性に応じた数の複数の汎用プロセッサグループに分割する処理を含み、
前記第２のプロセッサをアクセラレータグループに割り当てる処理は、
前記並列性に係わらず第２のプロセッサをアクセラレータグループに割り当てる処理を含むことを特徴とする請求項１に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項４】
前記実行コストを比較する処理は、
前記タスクを第１及び第２のプロセッサで処理したときの処理コストをそれぞれ演算する処理と、
前記タスクを第１及び第２のプロセッサで実行するために必要なデータ転送に要する転送コストを演算する処理と、
前記第１のプロセッサにおける処理コストと転送コストを加算した値と、前記第２のプロセッサにおける処理コストと転送コストを加算した値と、を比較することを特徴とする請求項２に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項５】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記汎用プロセッサグループ毎にレディキューを設定する処理を含み、
前記割り当てを行うタスクを決定する処理は、
前記抽出したタスクを前記レディキューへ投入する処理と、
前記レディキューへ投入したタスク毎に前記優先度を演算する処理と、
前記レディキューのタスクのうち優先度が最も高いタスクを選択する処理と、
を含むことを特徴とする請求項３に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項６】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記汎用プロセッサグループ毎にレディキューを設定する処理を含み、
前記割り当てを行うタスクを決定する処理は、
前記抽出したタスクを前記レディキューへ投入する処理と、
前記レディキューへ投入したタスク毎に前記優先度を演算する処理と、
前記レディキューのタスクのうち優先度が最も高いタスクを選択する処理と、
を含むことを特徴とする請求項３に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項７】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記汎用プロセッサグループのいずれか一つに第１の実行キューを設定する処理と、
前記プロセッサグループ毎に第２の実行キューを設定する処理と、を含み、
前記タスクを割り当てる処理は、
前記プロセッサグループの実行コストが小さいときには前記タスクを前記第１の実行キューへ投入し、前記アクセラレータグループの実行コストが小さいときには前記タスクを前記第２の実行キューへ投入することを特徴とする請求項５または請求項６に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項８】
前記汎用プロセッサグループに割り当てる処理は、
前記汎用プロセッサグループ毎に第１の実行キューを設定する処理と、
前記プロセッサグループの第２のプロセッサ毎に第２の実行キューをそれぞれ設定する処理と、を含み、
前記タスクを割り当てる処理は、
前記プロセッサグループの実行コストが小さいときには前記タスクを前記第１の実行キューへ投入し、前記アクセラレータグループの実行コストが小さいときには前記タスクを前記第２の実行キューへ投入することを特徴とする請求項５または請求項６に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項９】
第１の命令セットを実行する複数の第１のプロセッサと、
前記第１のプロセッサとは異なる第２の命令セットを実行する第２のプロセッサと、
を有するマルチプロセッサシステムに実行させる目的プログラムを生成するコンパイラであって、
入力プログラムを読み込む処理と、
前記入力プログラムを解析し、前記入力プログラムを複数の粒度のタスクに分割する処理と、
前記タスク間の制御依存性及びデータ依存性を解析し、複数のタスク間の依存関係に基づいて実行可能なタスクを抽出する処理と、
前記抽出したタスク間の制御依存性及びデータ依存性に基づいて前記タスクの並列性を抽出する処理と、
前記並列性に基づいて前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理と、
前記第２のプロセッサをアクセラレータグループに割り当てる処理と、
前記抽出したタスクの実行コストを演算する処理と、
前記実行コストに基づいて抽出したタスクの優先度を演算する処理と、
予め設定したタスク毎の優先度に基づいて、前記抽出したタスクから割り当てを行うタスクを決定する処理と、
前記決定したタスクを前記第２のプロセッサで実行したときの実行コストと、前記タスクを前記第１のプロセッサで実行したときの実行コストとを比較する処理と、
前記比較の結果、前記実行コストが小さい方の汎用プロセッサグループまたはアクセラレータグループの一方に当該タスクを割り当てる処理と、
前記割り当てたタスクに基づいて目的コードを出力する処理と、
を計算機に実行させることを特徴とするマルチグレイン並列化コンパイラ。
【請求項１０】
前記タスクを割り当てる処理は、
前記比較の結果、第２のプロセッサの実行コストが小さいときには、当該タスクを前記アクセラレータグループへ割り当てる処理と、
前記比較の結果、第１のプロセッサの実行コストが小さいときには、当該タスクを前記汎用プロセッサグループへ割り当てる処理と、
を含むことを特徴とする請求項９に記載のマルチグレイン並列化コンパイラ。
【請求項１１】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記抽出したタスクが並列性を持つ場合には、前記第１のプロセッサを前記並列性に応じた数の複数の汎用プロセッサグループに分割する処理を含み、
前記第２のプロセッサをアクセラレータグループに割り当てる処理は、
前記並列性に係わらず第２のプロセッサをアクセラレータグループに割り当てる処理を含むことを特徴とする請求項９に記載のマルチグレイン並列化コンパイラ。
【請求項１２】
前記実行コストを比較する処理は、
前記タスクを第１及び第２のプロセッサで処理したときの処理コストをそれぞれ演算する処理と、
前記タスクを第１及び第２のプロセッサで実行するために必要なデータ転送に要する転送コストを演算する処理と、
前記第１のプロセッサにおける処理コストと転送コストを加算した値と、前記第２のプロセッサにおける処理コストと転送コストを加算した値と、を比較することを特徴とする請求項１０に記載のマルチグレイン並列化コンパイラ。
【請求項１３】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記汎用プロセッサグループ毎にレディキューを設定する処理を含み、
前記割り当てを行うタスクを決定する処理は、
前記抽出したタスクを前記レディキューへ投入する処理と、
前記レディキューへ投入したタスク毎に前記優先度を演算する処理と、
前記レディキューのタスクのうち優先度が最も高いタスクを選択する処理と、
を含むことを特徴とする請求項１１に記載のマルチグレイン並列化コンパイラ。
【請求項１４】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記汎用プロセッサグループ毎にレディキューを設定する処理を含み、
前記割り当てを行うタスクを決定する処理は、
前記抽出したタスクを前記レディキューへ投入する処理と、
前記レディキューへ投入したタスク毎に前記優先度を演算する処理と、
前記レディキューのタスクのうち優先度が最も高いタスクを選択する処理と、
を含むことを特徴とする請求項１１に記載のマルチグレイン並列化コンパイラ。
【請求項１５】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記汎用プロセッサグループのいずれか一つに第１の実行キューを設定する処理と、
前記プロセッサグループ毎に第２の実行キューを設定する処理と、を含み、
前記タスクを割り当てる処理は、
前記プロセッサグループの実行コストが小さいときには前記タスクを前記第１の実行キューへ投入し、前記アクセラレータグループの実行コストが小さいときには前記タスクを前記第２の実行キューへ投入することを特徴とする請求項１３または請求項１４に記載のマルチグレイン並列化コンパイラ。
【請求項１６】
前記複数の第１のプロセッサを汎用プロセッサグループに割り当てる処理は、
前記汎用プロセッサグループ毎に第１の実行キューを設定する処理と、
前記プロセッサグループの第２のプロセッサ毎に第２の実行キューをそれぞれ設定する処理と、を含み、
前記タスクを割り当てる処理は、
前記プロセッサグループの実行コストが小さいときには前記タスクを前記第１の実行キューへ投入し、前記アクセラレータグループの実行コストが小さいときには前記タスクを前記第２の実行キューへ投入することを特徴とする請求項１３または請求項１４に記載のマルチグレイン並列化コンパイラ。
【請求項１７】
前記目的コードを出力する処理は、
前記タスクの割り当てを前記入力プログラムに付加し、前記各プロセッサユニット毎の実行コードを生成する処理を含むことを特徴とする請求項９に記載のマルチグレイン並列化コンパイラ。
【請求項１８】
前記目的コードを出力する処理は、
前記割り当てたタスクのスケジューリングコードを生成する処理と、
前記スケジューリングコードを入力プログラムに付加し、前記各プロセッサユニット毎の実行コードを生成し、目的コードとして生成する処理と、
を含むことを特徴とする請求項９に記載のマルチグレイン並列化コンパイラ。
【請求項１９】
前記目的コードを出力する処理は、
前記タスクに実行時の変動要素が含まれないときには、前記タスクの割り当てを前記入力プログラムに付加し、前記各プロセッサユニット毎の実行コードを目的コードとして生成する処理と、
前記タスクに実行時の変動要素が含まれるときには、
前記割り当てたタスクのスケジューリングコードを生成する処理と、
前記スケジューリングコードを入力プログラムに付加し、前記各プロセッサユニット毎の実行コードを生成し、目的コードとして生成する処理と、
を含むことを特徴とする請求項９に記載のマルチグレイン並列化コンパイラ。
【請求項２０】
前記タスクを割り当てる処理は、
前記タスクを割り当てた第１または第２のプロセッサにおいて、当該タスクの実行時に必要となるデータの転送命令を設定する処理を含むことを特徴とする請求項１に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項２１】
前記ヘテロジニアス・マルチプロセッサは、第１のプロセッサと第２のプロセッサで共有する共有メモリと、第１のプロセッサ及び第２のプロセッサがそれぞれ占有するローカルメモリと、を有し、
前記データの転送命令は、前記タスクの実行前に前記当該タスクを割り当てた第１または第２のプロセッサへ当該タスクが必要とするデータを前記共有メモリからローカルメモリへ読み込む命令を含むことを特徴とする請求項２０に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項２２】
前記ヘテロジニアス・マルチプロセッサは、第１のプロセッサと第２のプロセッサで共有する共有メモリと、第１のプロセッサ及び第２のプロセッサがそれぞれ占有するローカルメモリと、を有し、
前記データの転送命令は、前記当該タスクを割り当てた第１または第２のプロセッサで当該タスクが利用したデータにアクセスする最後のタスクの実行終了時に当該データを前記共有メモリへ書き込む命令を含むことを特徴とする請求項２０に記載のヘテロジニアス・マルチプロセッサシステムの制御方法。
【請求項２３】
前記タスクを割り当てる処理は、
前記タスクを割り当てた第１または第２のプロセッサにおいて、当該タスクの実行時に必要となるデータの転送命令を設定する処理を含むことを特徴とする請求項９に記載のマルチグレイン並列化コンパイラ。
【請求項２４】
前記ヘテロジニアス・マルチプロセッサは、第１のプロセッサと第２のプロセッサで共有する共有メモリと、第１のプロセッサ及び第２のプロセッサがそれぞれ占有するローカルメモリと、を有し、
前記データの転送命令は、前記タスクの実行前に前記当該タスクを割り当てた第１または第２のプロセッサへ当該タスクが必要とするデータを前記共有メモリからローカルメモリへ読み込む命令を含むことを特徴とする請求項２３に記載のマルチグレイン並列化コンパイラ。
【請求項２５】
前記ヘテロジニアス・マルチプロセッサは、第１のプロセッサと第２のプロセッサで共有する共有メモリと、第１のプロセッサ及び第２のプロセッサがそれぞれ占有するローカルメモリと、を有し、
前記データの転送命令は、前記当該タスクを割り当てた第１または第２のプロセッサで当該タスクが利用したデータにアクセスする最後のタスクの実行終了時に当該データを前記共有メモリへ書き込む命令を含むことを特徴とする請求項２３に記載のマルチグレイン並列化コンパイラ。
【請求項２６】
第１の命令セットを実行する複数の第１の計算機と、
前記第１の計算機とは異なる第２の命令セットを実行する第２の計算機と、
をネットワークを介して接続し、前記第１の計算機と第２の計算機に実行させる目的プログラムを生成するコンパイラであって、
入力プログラムを読み込む処理と、
前記入力プログラムを解析し、前記入力プログラムを複数の粒度のタスクに分割する処理と、
前記タスク間の制御依存性及びデータ依存性を解析し、複数のタスク間の依存関係に基づいて実行可能なタスクを抽出する処理と、
前記抽出したタスク間の制御依存性及びデータ依存性に基づいて前記タスクの並列性を抽出する処理と、
前記並列性に基づいて前記複数の第１の計算機を汎用プロセッサグループに割り当てる処理と、
前記第２の計算機をアクセラレータグループに割り当てる処理と、
前記抽出したタスクの実行コストを演算する処理と、
前記実行コストに基づいて抽出したタスクの優先度を演算する処理と、
予め設定したタスク毎の優先度に基づいて、前記抽出したタスクから割り当てを行うタスクを決定する処理と、
前記決定したタスクを前記第２の計算機で実行したときの実行コストと、前記タスクを前記第１の計算機で実行したときの実行コストとを比較する処理と、
前記比較の結果、前記実行コストが小さい方の汎用プロセッサグループまたはアクセラレータグループの一方に当該タスクを割り当てる処理と、
前記割り当てたタスクに基づいて目的コードを出力する処理と、
を計算機に実行させることを特徴とするマルチグレイン並列化コンパイラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、種類の異なる複数のプロセッサユニットを含むヘテロジニアス・マルチプロセッサシステムにおいて、複数のプロセッサユニットを効率よく動作させることを可能とするヘテロジニアス・マルチプロセッサシステムの制御方法及びプログラムを生成するコンパイラに関する。
【背景技術】
【０００２】
半導体製造技術の進歩による素子の微細化により、膨大な数のトランジスタを集積することが可能となっている。それと同時にプロセッサの高周波数化も進むが、動作時電力の増加、またリーク電流に起因する待機時電力の増加により、従来のプロセッサが歩んできた動作周波数の向上と論理方式の改善により達成してきた性能向上に限界が見え始めている。
【０００３】
そこで現在、性能改善と低電力化を実現する手段として、従来のＣＰＵ、ＤＳＰといったプロセッサエレメント（以下、ＰＥとする）を複数個オンチップで搭載し、処理を並列で行うことで、動作周波数を向上させなくとも、高い演算性能を得ることが可能な、マルチプロセッサシステム（シングルチップ・マルチプロセッサシステム）が有望となっている。マルチプロセッサシステムのうち、同一の命令セットで構成及び演算性能が同一のプロセッサエレメントを複数備えたものがホモジニアス・マルチプロセッサシステムであり、命令セット及び構成の異なるプロセッサエレメントを複数備えたものがヘテロジニアス・マルチプロセッサシステムである。
【０００４】
ホモジニアス・マルチプロセッサシステムにおいては、並列処理を推進することで処理性能を向上させるものが知られている（例えば、特許文献１、２）
ホモジニアス・マルチプロセッサシステムにおいて、入力プログラムを解析し、当該プログラム中から並列に動作可能な部分を抽出し、当該部分を複数のＰＥに割り当て同時に実行することを可能とする、自動並列化コンパイラの研究がすでに行われている。例えば、特許文献１では、入力ソースプログラムを解析し、当該プログラムをサブルーチンやループなどさまざまな粒度（グレイン）のブロック（タスク）に分割し、当該複数タスク間の並列性を解析すると共に、タスクとそれらがアクセスするデータをキャッシュあるいはローカルメモリに適合するサイズに分割し、それらを各ＰＥに対して当該タスクを最適割り当てすることによって、マルチプロセッサシステムを効率よく動かす目的プログラムを生成するコンパイル方式が開示されている。また特許文献２には、マルチグレイン並列処理の機能をサポートするチップマルチプロセッサのアーキテクチャが開示されている。
【０００５】
一方、ヘテロジニアス・マルチプロセッサシステムでは、多種のタスクを実行可能な汎用ＣＰＵと、特定の処理を高速に実行するＤＳＰなどのＰＥを組み合わせている。このようなヘテロジニアス・マルチプロセッサシステムにおける処理の最適化を図るものとして特許文献３、４等が知られている。
【０００６】
特許文献３では、命令セットが異なる異種プロセッサにタスクを仮割り付けし、タスクの実行時に異種命令セットのプロセッサに割付を変更するか否かを判定し、割り付けを変更した方が実行効率が向上する場合には、割り付けの変更を実施する、という技術が開示されている。
【０００７】
また、特許文献４では、ソースプログラムから分割したタスクを消費電力に基づいて各プロセッサに割り当てる。さらに、多種のタスクを実行可能なコアよりも小種類のタスクしか実行できないプロセッサに優先してタスクを割り付ける、という技術が開示されている。
【特許文献１】特開２００４−２５２７２８号
【特許文献２】特開２００１−１７５６１９号
【特許文献３】特開２００４−１７１２３４
【特許文献４】特開２００４−２５２９００号
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ここで、ヘテロジニアス・マルチプロセッサシステムでは、各ＰＥの構成及び特性が異なるため、プログラムの特性に合わせて異種のＰＥに対しスケジューリングを行う必要がある。このため、上記特許文献１，２のようなホモジニアス・マルチプロセッサシステムの手法をそのまま適用すると、並列化したタスクを階層的にグルーピングしていくことになってＰＥの資源が不足してしまう。例えばある特殊用途向けＰＥを１個持つヘテロジニアス・マルチプロセッサシステムにおいて、この特殊用途向けＰＥをある汎用ＰＥへグルーピングした場合、他の汎用コアグループや他の階層においては当該ＰＥに対しタスクをスケジュールすることができなくなる。つまり、効率的な並列化が行われず、システムの性能を引き出すことができない。
【０００９】
このため、ヘテロジニアス・マルチプロセッサシステムを利用するには、上記特許文献３、４のように、異種のＰＥを意識したスケジューリングが必要となる。
【００１０】
しかしながら、上記特許文献３においては、各ＰＥへ仮割り付けを行った後に、タスクの実行時に割り付け変更を判定する。このためスケジューリングに要するコスト（オーバーヘッド）が増大し、プロセッサ全体での実行効率が低下する場合がある。特に、汎用プロセッサとＤＳＰやＤＲＰ等のアクセラレータ（異種のＰＥ）を組み合わせたヘテロジニアスマルチプロセッサシステムでは、アクセラレータの数や種類が増えるにつれて上記スケジューリングのコストが増大し、スケジューリングのオーバーヘッドによりプロセッサ全体の処理速度が低下するという問題がある。
【００１１】
また、上記特許文献４では、処理可能なタスクの種類が少ないＰＥに対して優先的にタスクを割り付けるため、汎用プロセッサとＤＳＰ等のアクセラレータを組み合わせたヘテロジニアス・マルチプロセッサシステムでは、処理可能なタスクの種類が少ないアクセラレータにタスクが集中する一方、汎用プロセッサの利用率が低下して、特定のＰＥのリソースが不足し、プロセッサ全体の処理能力が低下する場合がある。
【００１２】
そこで本発明は、命令セット及び構成の異なるプロセッサエレメントを複数備えたヘテロジニアス・マルチプロセッサシステムにおいて、特定のＰＥのリソースが不足するのを防いで、マルチプロセッサシステム全体の処理能力を向上させることを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、第１の命令セットを実行する第１のプロセッサと、前記第１のプロセッサとは異なる第２の命令セットを実行する第２のプロセッサと、前記第１のプロセッサを複数含み、かつ、少なくとも一つの前記第２のプロセッサを含むヘテロジニアス・マルチプロセッサシステムにタスクを割り当てる制御方法であって、予め設定した複数のタスクの依存関係に基づいて実行可能なタスクを抽出し、前記抽出したタスクの依存関係に基づいて前記複数の第１のプロセッサを汎用プロセッサグループに割り当て、前記第２のプロセッサをアクセラレータグループに割り当てて、予め設定したタスク毎の優先度に基づいて、前記抽出したタスクから割り当てを行うタスクを決定し、前記決定したタスクを前記第１のプロセッサで実行したときの実行コストと、前記タスクを前記第２のプロセッサで実行したときの実行コストとを比較し、前記比較の結果、前記実行コストが小さい方の汎用プロセッサグループまたはアクセラレータグループの一方に当該タスクを割り当てる。
【発明の効果】
【００１４】
したがって、本発明により、命令セットの異なるプロセッサを集積するヘテロジニアス・マルチプロセッサシステムにおいて、タスクがアクセラレータグループへ集中するのを防いで、異種のプロセッサを効率よく動作させることが可能となる。そして、実行時の際にタスクの割り当てを制御する際には、実行コストに応じて汎用プロセッサグループまたはアクセラレータグループのいずれか一方へタスクを割り当てるので、前記従来例に比して割り当てにようするオーバーヘッドを抑制できる。この結果、ヘテロジニアス・マルチプロセッサシステムの処理をより高速に実行することが可能となる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の一実施形態を添付図面に基づいて説明する。
【００１６】
＜実施形態の全体構成＞
図１は、本発明の一実施形態であるマルチプロセッサシステムの構成を示す。図１において、ヘテロジニアス・マルチプロセッサシステム１は、命令セット及び構成の異なるプロセッサエレメント（以下、ＰＥとする）１０〜１７と、これらＰＥ１０〜１７で共有する集中共有メモリ（以下、ＣＳＭ：Centralized Shared Memory）１８及び各ＰＥ１０〜１７とＣＳＭ１８を接続する内部ネットワーク１９主体にして構成されたヘテロジニアス・マルチプロセッサシステムである。なお、内部ネットワーク１９は、共有バスやクロスバなどで構成してもよい。
【００１７】
各ＰＥ１０〜１７、ＣＳＭ１８は、それぞれのインタフェース（図示省略）を介して、内部ネットワーク１９に接続される。
【００１８】
本実施形態ではＰＥの種類と個数を、４個の汎用処理プロセッサ（以下、ＣＰＵ）１０、１１、１２，１３と、２個の動的再構成可能プロセッサ（以下、ＤＲＰ：Dynamically Reconfigurable Processor）１４、１５と、２個の信号処理プロセッサ（以下、ＤＳＰ：Digital Signal Processor）１６、１７で構成した例を示す。なお、上記ＰＥの種類や数は本実施形態で示した限りではなく、さまざまな構成を取り得る。
【００１９】
また、本実施形態では、ＤＲＰ（０、１）１４、１５と、ＤＳＰ（０、１）１６、１７を特定用途プロセッサエレメント（特定用途ＰＥ）とし、ＣＰＵ（０、１、２、３）１０、１１、１２、１３を汎用プロセッサエレメント（汎用ＰＥ）とする。また、ＤＲＰ１４、１５は、処理回路を動的に再構成することが可能なプロセッサを指し、限られたコア内で仮想的に回路を変更することができる。
【００２０】
本実施形態では、特定用途ＰＥのＤＲＰ１４，１５とＤＳＰ１６，１７は汎用ＰＥのＣＰＵ１０〜１３とは異なる命令セットを使用する。特定用途ＰＥは予め設定されたタスク（処理の単位ブロック）の処理のみを実行可能に構成され、アクセラレータとして機能する。一方、汎用ＰＥのＣＰＵ１０〜１３は、各特定用途ＰＥへの指令や汎用的な演算処理に加え、ＤＲＰ１４，１５やＤＳＰ１６、１７の特定用途ＰＥの処理を実行することが可能である。ただし、ＣＰＵ１０〜１３が特定用途ＰＥの処理を実行した場合の速度は、ＤＲＰ１４，１５やＤＳＰ１６、１７の処理速度より低下する。つまり特定用途ＰＥは、特定のタスクに対して汎用ＰＥのアクセラレータとして機能する。
【００２１】
汎用ＰＥのＣＰＵ１０は、演算処理を実行するＣＰＵコア２１と、ＣＰＵ１０で処理されるプログラムやデータを一時的に保存するローカルメモリ（ＬＭ）２２と各ＰＥ間で共有される分散共有メモリ（ＤＳＭ：Distributed Shared Memory）２３と、他のＰＥ１１〜１７やＣＳＭ１８との間でデータの転送を実行するデータ転送ユニット（以下、ＤＴＵ：Data Transfer Unit）２４と、ＣＰＵ１０に対する供給電圧や動作周波数を決定する周波数・電源電圧（ＦＶ）制御、及びＰＥ間の同期制御を行うためのシステム制御レジスタ（ＦＶＲ）２５を具備する。なお、他のＣＰＵ１１〜１３も、上記ＣＰＵ１０と同一の構成要素を備える。なお、システム制御レジスタＦＶＲは、設定する値が、例えば、「０」のときに電源オフとし、「１」のときに低駆動周波数、低電圧とし、「３」のときに最大駆動周波数、最大電圧とし、「２」のときに中間駆動周波数、中間電圧として各ＰＥを駆動するものである。
【００２２】
また、ＤＴＵ２４はＤＭＡＣ（Direct Memory Access Controller）を含んで構成され、ＣＰＵコア２１のバックグラウンドで、ＬＭ２２やＤＳＭ２３とＣＳＭ１８または他の汎用ＰＥ、特定用途ＰＥのＤＳＭ２３との間でデータの転送を実行する。
【００２３】
ＤＲＰ１４は、動的に再構成が可能なＤＲＰコア３１と、このＤＲＰコア３１の構成を制御と動作条件を制御する制御部（ＣＴＬ）３２と、ＤＲＰ１４で処理されるプログラムやデータを一時的に保存するＬＭ２２と各ＰＥ間で共有されるＤＳＭ２３と、他のＰＥ１０〜１７やＣＳＭ１８との間でデータの転送を実行するデータ転送ユニットＤＴＵ２４と、を備える。なお、ＤＲＰ１４に対する供給電圧や動作周波数を決定する周波数・電源電圧（ＦＶ）制御、及びＰＥ間の同期制御は制御部３２で行われる。なお、ＤＲＰ（１）１５もＤＲＰ１４と同一の構成である。
【００２４】
ＤＳＰ１６は、特定の信号処理を実行するＤＳＰコア４１と、ＤＳＰ１６で処理されるプログラムやデータを一時的に保存するＬＭ２２と各ＰＥ間で共有されるＤＳＭ２３と、他のＰＥ１０〜１７やＣＳＭ１８との間でデータの転送を実行するＤＴＵ２４と、ＤＳＰ１６に対する供給電圧や動作周波数を決定する周波数・電源電圧（ＦＶ）制御、及びＰＥ間の同期制御を行うためのシステム制御レジスタ（ＦＶＲ）２５を具備する。なお、ＤＳＰ（１）１７も、上記ＤＳＰ１６と同一の構成要素を備える。
【００２５】
なお、各ＰＥのＤＳＭ２３は、他のＰＥからアクセス可能なグローバルアドレスがマッピングされている。一方、ＬＭ２２は自ＰＥ内でアクセス可能なローカルアドレスがマッピングされる。
【００２６】
以上は本発明における適用構成の一例に過ぎず、実施の形態としてはこの限りでない。例えば図１では表現されていないが、内部ネットワーク１９には入出力処理、割り込み処理、タイマ、デバッグ回路、等の周辺回路を必要に応じて接続することとなる。
【００２７】
なお、上記ＰＥ１０〜１７は、一つのチップ（ＬＳＩ）上に構成された場合を示すが、ＰＥ１０〜１７を構成する複数のＬＳＩを結合し、一つのチップまたはモジュールとしたものであっても良い。
【００２８】
例えば、プロセッサコア内の各要素の接続を含めたアーキテクチャ構成例を図１９に示す。本例では、汎用ＰＥとしてＣＰＵ４個（ＣＰＵ０〜ＣＰＵ３）に加え、特定用途ＰＥとして、ＤＳＰを２個（ＤＳＰ０，ＤＳＰ１）、ＤＲＰを２個（ＤＲＰ０，ＤＲＰ１）搭載する。
【００２９】
特定用途ＰＥは、通常特定の演算を高速に処理することが可能なアクセラレータコア（本図ではＤＳＰコア、並びにＤＲＰコアがそれにあたる）を搭載し、さらに当該アクセラレータにて処理を行うために必要なデータ転送や、同期通信、アクセラレータコアの制御を行うコントローラＣＰＵ３２ａ，４２ａを搭載する。
【００３０】
本ＣＰＵ３２ａ，４２ａは、特定用途ＰＥを制御する用途で用いるため命令セットを簡易化した制御用ＣＰＵを用いてもよいが、汎用ＰＥと同様の高機能ＣＰＵコアを用いて、アクセラレータコアでの処理と並行して異なる演算処理を行うことも考えられる。
【００３１】
また、特定用途ＰＥは汎用ＣＰＵコアと同様に処理データを一時的に格納するローカルデータメモリＬＤＭ、コントローラＣＰＵ、またはアクセラレータコア上で実行するプログラムを格納するローカルプログラムメモリＬＰＭ、プロセッサ間で共有するデータを格納する分散共有メモリＤＳＭを持つ。また汎用ＰＥと同様に、データ転送ユニットＤＴＵを持ち、当該各種メモリと他のＰＥのメモリ、または共有メモリＣＳＭ間とのデータ転送を可能とする。なお、当該各種メモリは外部バス、アクセラレータコア、コントローラＣＰＵ、データ転送ユニットＤＴＵとＰＥ内部バスで接続される。また、ローカルプログラムメモリは、プリフェッチ可能なキャッシュとすることもできる。
【００３２】
＜マルチグレイン並列処理の概念＞
次に、上記図１のヘテロジニアス・マルチプロセッサシステム１で実行するタスクの並列処理について説明する。各ＰＥで実行するタスク（プログラム）は、後述するコンパイラによって入力プログラムを解析したマクロタスクグラフから生成される。つまり、入力プログラムは、まず後述するコンパイラにより、当該プログラムの構造を解析することで、代入文のみからなるベーシックブロック（ＢＢ）、繰り返しブロック（ＲＢ）、サブルーチン（ＳＢ）といった粒度が大きなステートメント・ブロックをマクロタスク（ＭＴ）として分割する。またマクロタスク内の処理がタスクとなる。
【００３３】
例えば、図２は、コンパイラが入力プログラムを解析した結果を示すマクロタスクグラフである。図２において本例では、入力プログラムを後述するように解析したものをマクロタスクグラフＭＴＧ１とすると、３個のマクロタスクＭＴ１＿１〜１＿３のマクロタスクに分割されるとする。ここで、マクロタスクは、入力プログラム（ソースコード）を複数の粒度の単位ブロックに分割したものである。つまり、マクロタスクに分割することで、サブルーチン等の粗粒度タスク間の並列処理を利用するマクロデータフロー処理、ループレベルの並列処理である中粒度並列処理に、基本ブロック内部のステートメントレベルの並列性を利用する近細粒度並列処理とを階層的に組み合わせて並列処理を行うマルチグレイン並列処理を行う。なお、入力プログラムの構成要素（粒度）から処理の並列性を抽出してマクロタスクに群介するマルチグレイン並列処理の粗粒度タスク並列処理については、本願発明者らが提案した特開２００４−２５２７２８号公報の手法や他の公知の手法を用いることができる。
【００３４】
ここで、図２の例では、入力プログラムは後述のコンパイラにより、３つのマクロタスクに分解され、この複数のマクロタスクのうち２つのマクロタスクＭＴ１＿２、ＭＴ１＿３に並列実行依存性があることを示している。ここで、並列実行依存性とはマクロタスク間またはタスク間のデータの依存性や制御の依存性から、各タスクを並列して実行できるか否かを決定する指標である。例えば、図２の実線で示すように、上位のマクロタスクが終了しなければ下位のマクロタスクを実行できないデータの依存性があるとき、並列依存性はない。つまり、マクロタスクＭＴ１＿２、ＭＴ１＿３は、マクロタスクＭＴ１＿１が終了しなければそれぞれ実行できないことを示している。
【００３５】
一方、マクロタスクＭＴ１＿１が終了した後には、マクロタスクＭＴ１＿２とマクロタスクＭＴ１＿３の間ではデータの依存性はなく、各マクロタスクを独立して並列的に実行することができる。このように、マクロタスクまたはタスクを並列して実行可能な状態を並列依存性があると判定する。
【００３６】
さらに、マクロタスクＭＴ１＿２の内部を解析すると、コンパイラはマクロタスクＭＴ１＿２を、５つのタスクＭＴ１＿２＿１〜１＿２＿５に分解する。そして、分割したタスクＭＴ１＿２＿１〜１＿２＿５の並列依存性を解析すると、タスクＭＴ１＿２＿１の終了後にタスクＭＴ１＿２＿２とＭＴ１＿２＿４が並列実行でき、タスクＭＴ１＿２＿２の終了後にタスクＭＴ１＿２＿３が実行でき、タスクＭＴ１＿２＿２とＭＴ１＿２＿４の双方が終了した後にタスクＭＴ１＿２＿５が実行可能になることを示している。
【００３７】
このマクロタスクＭＴ１＿２の内部は、上位階層から下位階層まで条件分岐などの実行時に不確定要素がないため、後述するように、静的にタスクを割り当てるスタティックスケジューリングを適用する。
【００３８】
一方、マクロタスクグラフＭＴＧ１＿３では、コンパイラが４つのタスクＭＴ１＿３＿１〜ＭＴ１＿３＿４に分割する。そして、タスクＭＴ１＿３＿１の実行結果に基づいて条件分岐が発生し、タスクＭＴ１＿３＿２かタスクＭＴ１＿３＿３及びＭＴ１＿３＿４のどちらかを実行する制御依存となる。この図において、タスクＭＴ１＿３＿４へは矢印のない破線が延びており、タスクＭＴ１＿３＿４への矢印のない当該破線と、タスクＭＴ１＿３＿３に接続される破線上には、制御依存のＡＮＤ条件を表す実線のアーク５２８が重なっている。これは、もし当該条件で、矢印で指されているタスクＭＴ１＿３＿３の方向に分岐すると、同一の分岐に制御依存しているタスクＭＴ１＿３＿４が同時に実行可能なことを示している。なお、図中破線はタスクの実行が確定される制御依存関係と、データ依存しているタスクが実行されない場合の条件を表している。また、矢印がついた破線は、データ依存・制御フロー解析（４０２）で求めた制御フローと同一（つまり、オリジナル）であることを表す。
【００３９】
さらにタスクＭＴ１＿３＿４はサブルーチンブロック（ＳＢ）であるので、この内部を解析すると、タスクＭＴ１＿３＿４は３つのタスクＭＴ１＿３＿４＿１〜ＭＴ１＿３＿４＿３に分解され、タスクＭＴ１＿３＿４＿１が終了した後にタスクＭＴ１＿３＿４＿２とＭＴ１＿３＿４＿３を並列実行可能になることを示している。ここで、タスクＭＴ１＿３＿１以降の処理は、タスクＭＴ１＿３＿１の結果に応じて条件分岐が行われるので、コンパイルの時点では分岐先が定まらず実行時の不確定要素を含む。この場合、コンパイラで生制されたタスクＭＴ１＿３＿１の下位の階層は、実行時にＰＥを決定すること望ましいので、後述するダイナミックスケジューリングを適用する。
【００４０】
また、コンパイラは入力プログラムに記述された使用するＰＥの記述やコンパイラの自動検出により、各タスクＭＴを各ＰＥのグループに割り当てる。
【００４１】
ここで、本願発明の特徴として、タスクを各ＰＥへ割り当てるとき、後述するプロセッサグループ毎にタスクを割り当てる。そして、各タスクが最も早く終了するようにスケジューリングを行う。このとき、ＤＲＰ１４，１５やＤＳＰ１６，１７の特定用途ＰＥが実行可能な特定のタスクでは、基本的に特定用途ＰＥのグループ毎にタスクを割り当てる。しかし、特定のタスクを全て特定用途ＰＥへ割り当てると、特定用途ＰＥで処理完了待ちが発生する一方、汎用ＰＥではタスク待ちが発生する場合がある。このような特定用途ＰＥのリソースが不足する場合では、特定用途ＰＥに割り当てるタスクを汎用ＰＥグループに割り当てて、ヘテロジニアス・マルチプロセッサシステム全体の処理速度が速くなるようにスケジューリングを行うのである。なお、このスケジューリングについては後述するように、コンパイラで設定するスタティックスケジューリングで行う場合と、タスク間に埋め込まれたダイナミックスケジューリングで行う場合の２通りがある。
【００４２】
＜プロセッサのグルーピング＞
次に、本発明のプロセッサのグルーピングについて図２および図３を参照しながら説明する。本発明では、コンパイラがタスクをＰＥに割り当てる際には、個々のＰＥへ割り当てるのではなく、ＰＥのグループ単位でタスクを割り当てる。
【００４３】
ＰＥのグループは、汎用ＰＥで構成される汎用プロセッサグループ（汎用ＰＧ）と、特定用途ＰＥで構成されるアクセラレータグループの２つに大別される。なお、以下ではＣＰＵ１０〜１３をＣＰＵ間の識別子であるＣＰＵ０〜３で示す。また、アクセラレータグループでは、ＤＲＰ１４，１５をＤＲＰ間の識別子であるＤＲＰ０、１で示し、ＤＳＰ１６、１７をＤＳＰ間の識別子であるＤＳＰ０、１で示す。
【００４４】
汎用プロセッサグループＰＧは、プログラム（マクロタスクＭＴ）の並列性や階層構造に応じて、ＣＰＵを仮想的にグルーピングしたものである。例えば、図３において、プログラム全体としては汎用プロセッサを４つ利用できる（図中４ＰＥｓ）。第１階層は、例えば、図２に示したマクロタスクグラフの最上位であるマクロタスクグラフＭＴＧ１に相当する。このＭＴＧ１内部の並列性等を考慮して、ここでは４つのＣＰＵのうち２つを１つのグループにしたものが汎用プロセッサグループＰＧ１＿０として、残り２つを１つのグループにしたものが汎用プロセッサグループＰＧ１＿１として表現され、ＭＴＧ１内部のマクロタスクを割り当てる単位となる。
【００４５】
ここでは、汎用プロセッサグループＰＧ１＿０には、図２のマクロタスクＭＴ１＿１およびマクロタスクＭＴ１＿２（マクロタスクグラフＭＴＧ１＿２を内包）が割り当てられ、汎用プロセッサグループＰＧ１＿１にはマクロタスクＭＴ１＿３（マクロタスクグラフＭＴＧ１＿３を内包）が割り当てられたとする。
【００４６】
図３の第２階層では、汎用プロセッサグループＰＧ１＿０上でマクロタスクＭＴ１＿１を実行後、ＭＴ１＿２およびＭＴ１＿３を並列実行している間のグルーピングの例が示されている。このとき、マクロタスクグラフＭＴＧ１＿２内部の情報から汎用プロセッサグループＰＧ１＿０に含まれるＣＰＵのうち１つが汎用プロセッサグループＰＧ１＿２＿０として、他方のＣＰＵが汎用プロセッサグループＰＧ１＿２＿１としてグルーピングされる。そしてマクロタスクグラフＭＴＧ１＿２内部の各マクロタスクグラフをＰＧ１＿２＿０あるいはＰＧ１＿２＿１、またはマクロタスクの種別に応じてアクセラレータグループに割り当てる。また、マクロタスクグラフＭＴＧ１＿３内部の情報から、汎用プロセッサグループＰＧ１＿１に含まれる２つのＣＰＵは汎用プロセッサグループＰＧ１＿３＿０としてグルーピングされ、マクロタスクグラフＭＴＧ１＿３に含まれる各マクロタスクがこの汎用プロセッサグループまたはアクセラレータグループに対して割り当てられる。この第２階層において、図２中のＭＴ１＿３＿４のように内部にマクロタスクグラフを持つマクロタスクが割り当てられた場合、そのマクロタスクを実行している間は、その内部構造に応じて第３階層以下のグルーピングが用いられる。また、仮にＭＴＧ１がＭＴ１＿２やＭＴ１＿３以外のマクロタスクを含み、それが内部にマクロタスクグラフを持つ場合や、スケジューリングによってマクロタスクが割り当てられるプロセッサグループが上記と異なる場合、汎用プロセッサのマクロタスクグラフの情報に応じてグルーピングが決定されるため、第２階層以下ではマクロタスクの割り当て・実行状況に応じて図３と異なる汎用プロセッサのグルーピングが行われることになる。例えば、上記においてＭＴ１＿２がＰＧ１＿１に割り当てられた場合、ＰＧ１＿２＿０およびＰＧ１＿２＿１はＰＧ１＿１に含まれるプロセッサを用いてグルーピングを行う。
【００４７】
このように汎用プロセッサグループＰＧでは、プログラムの階層構造または並列性に応じて階層的にネストされたグルーピングが行われる。
【００４８】
これに対してアクセラレータグループでは、プログラムの階層構造や並列性に依存せず、特定用途ＰＥの種類または機能単位でグルーピングを行う。つまり、図３のように、ＤＲＰ０，１をＤＲＰのアクセラレータグループに割り当て、ＤＳＰ０，１をＤＳＰのアクセラレータグループに割り当てる。そして、アクセラレータグループでは、ＤＲＰ、ＤＳＰともに各特定用途ＰＥ毎にタスクを割り当てる。また、ＤＲＰのアクセラレータグループでは、構成を変更したＤＲＰの機能毎（例えば、ＤＲＰコアの構成毎）にグルーピングを行っても良い。
【００４９】
このように、本発明のヘテロジニアス・マルチプロセッサシステム１では、ＰＥのグルーピングを汎用プロセッサグループＰＧではプログラム（タスク）の階層構造や並列性に依存して階層的にグルーピングを行う一方、アクセラレータグループではプログラムの階層構造や並列性に依存することなく、特定用途ＰＥの種類や機能単位でグルーピングを行う。
【００５０】
これにより、汎用プロセッサグループＰＧからアクセラレータグループへのタスクの投入は、何れの階層からも実行することが可能となり、特定用途ＰＥの利用率を向上させることができるのである。つまり、汎用プロセッサグループＰＧに特定用途ＰＥを割り当てることも可能ではあるが、汎用プロセッサグループＰＧに割り当てられるタスクには常に特定用途ＰＥで処理可能なタスクが含まれているとは限らない。
【００５１】
そこで、特定用途ＰＥを汎用プロセッサグループＰＧに含めずに、汎用プロセッサグループＰＧの何れの階層からもタスクを受け入れられるように、特定用途ＰＥの種類や機能単位でグルーピングを行うことで、汎用ＰＥと特定用途ＰＥの利用率を向上させて、ヘテロジニアス・マルチプロセッサシステム１全体の処理速度を向上させるのである。
【００５２】
＜コンパイラの処理フロー＞
次に上記ヘテロジニアス・マルチプロセッサシステム１で、ＰＥの特性に合わせたスケジューリングの最適制御を行うコードを生成するコンパイル方法と、当該手法を実装したコンパイラの処理について以下順を追って説明していく。図４に本手法を実装したコンパイラ４０の処理フローの一例を示す。このコンパイラ４０は、計算機５０上で実行されるものである。なお、計算機５０は、後述する各テーブルを各テーブルを格納する外部記憶装置５１を備える。
【００５３】
＜マクロタスクの生成＞
入力プログラム４００はＣやFortran等の高級言語で記述された逐次構造のソースである。コンパイラ４０は、まず、入力プログラム４００のプログラム構造を解析する。この解析は、繰り返しブロック（ＲＢ：Repetition Block）、サブルーチン（ＳＢ：Sub Routine）、擬似代入文ブロック（ＢＰＡ：Block of Pseudo Assignment statements）の３種類の粒度で入力プログラム４００を大きなマクロタスク（ＭＴ）に分割し、各タスクを生成する（Ｓ１）。
【００５４】
繰り返しブロックＲＢはループブロックで各階層での最も外側のループであり、擬似代入文ブロックＢＰＡはスケジューリングオーバーヘッドあるいは並列性を考慮し、代入文からなる複数の基本ブロックを融合あるいは分割したブロックである。
【００５５】
上記Ｓ１では、予めプロセッサグループ（またはＰＥ）の割り当てを記述することが可能であり、例えばあるサブルーチンをＤＳＰグループに、またあるサブルーチンを汎用プロセッサグループＰＧに割り当てることを明示的に指定することも可能である。その結果、当該ＤＳＰサブルーチンはコンパイラ４０によりさらに並列性の解析が行われ、例えばＤＳＰが２個ある場合、当該２個のＤＳＰに対してコンパイラ４０は並列化スケジューリングを実施する。
【００５６】
＜データ依存・制御フロー解析＞
続いて、コンパイラ４０は、分割生成された当該タスク間の制御フロー及びデータ依存性を解析し、マクロタスクＭＴの実行順序関係を抽出する（Ｓ２）。入力プログラム４００は、逐次的に記述されているため、通常のコンパイラ４０によって生成される実行コードは、当該プログラムの構造と同様に逐次的な順序で実行されるが、マクロタスクＭＴ間で見ると必ずしも記述された順序で実行する必要がないことが多い。
【００５７】
つまり、マクロタスクＭＴ間において、制御またはデータ参照の依存性がない場合、特にマルチプロセッサシステムにおいては、複数のＰＥに複数のマクロタスクＭＴを配置して同時に、または順序を変更して、全体の実行時間が短くなるようスケジューリングすることが重要となる。
【００５８】
このようなスケジューリングを行うためには、ＭＴ間の並列性を解析する必要がある。そこで、この解析に向けた準備として、データ依存・制御フロー解析処理Ｓ２により、マクロタスクＭＴ間の実行順序関係を抽出する。
【００５９】
＜ループレベル並列性解析＞
続いて、コンパイラ４０は、マクロタスクＭＴ内の中粒度レベルの並列性解析として、ループレベルの並列化を行う（Ｓ３）。ループレベル並列化Ｓ３では、ループの繰り返し（イタレーション）単位間のデータ依存性を解析して、各イタレーションが独立に処理できるかを判断し、可能な場合は各イタレーションを複数のＰＥに割り当てて並列処理を行う。
【００６０】
また、単一のループを複数のループに分割して並列性を高めたり、データのコピーや配列変数の拡張により、各ループ間のデータ依存性を削除することで並列化したり、また複数のループを単一のループに融合することでループ制御に必要なオーバーヘッドを軽減したり、といった様々な手法によりループの並列化を実現する。
【００６１】
＜処理コスト解析＞
次に、コンパイラ４０は、上記生成されたマクロタスクＭＴを各ＰＥ１０〜１７で実行した際に必要となる処理サイクルを見積もる、処理コスト解析を行う（Ｓ４）。処理コスト（演算コスト＝処理時間）の見積もり方法としては、例えば汎用プロセッサグループＰＧなどに関しては、乗算や加算など命令レベルで必要とするサイクル数をタスク処理コストテーブル４２０にプロファイリング情報として保持しておき、当該テーブル４２０を参照することで、マクロタスクＭＴを当該プロセッサグループで実行する際の逐次処理サイクル数を見積もることができる。なお、処理コストは、後述するように各ＰＥ毎の処理時間とデータ転送時間を加えたものとすることができる。
【００６２】
また、ＤＲＰやＤＳＰなどの特定用途ＰＥで、プログラム中から表現される命令レベルでのサイクル数の見積もりが困難な場合は、一度当該ブロックのプログラムをＤＲＰやＤＳＰ用の実行コードを生成するそれぞれのローカルコンパイラを呼び出し、変換した実行コードを元にプロファイリングを行い、処理コストを演算する（４１３）。
【００６３】
ここで、本発明では特定用途ＰＥ向けのタスクＭＴを全てアクセラレータグループに割り当てるのではなく、アクセラレータグループで処理完了待ちが発生して終了時刻が遅延するような場合には、当該タスクＭＴを汎用プロセッサグループＰＧで割り当てる。このため、特定用途ＰＥのタスクＭＴのコスト解析は、特定用途ＰＥのコードと汎用ＰＥのコードの双方で見積もる。なお、見積もりの際にプロファイリング情報を用いない場合では、この段階ではコンパイラ４０はまだ実行コードを出力していないので、中間コードを生成し、この中間コードで処理コストの見積もりを行えばよい。また、処理コストの見積もりの際には、データがどこにあるかなどの詳細な情報は決定されていないので、ＣＳＭ１８からＤＳＭ２３への転送コストなどを含めずに各ＰＥのローカルメモリＬＭ２２や分散共有メモリＤＳＭ２３に必要なデータ等があるものとして算出すればよい。
【００６４】
また、特定用途ＰＥのタスクＭＴは、上記プロセッサのグルーピングと同様に、汎用プロセッサグループＰＧのタスクＭＴの階層には含めない。これにより、各階層のタスクＭＴから特定用途ＰＥのタスクＭＴを投入することが可能となる。
【００６５】
なお、特定用途ＰＥ毎のローカルコンパイラは、特定用途ＰＥの種類に応じて予め設定され、例えば、ＤＳＰであればＤＳＰのローカルコンパイラプロファイリング情報を、ＤＲＰであればＤＲＰのローカルコンパイラプロファイリング情報を用いる。
【００６６】
また、例えば分岐を含む場合、あるいはループのサイズや配列のサイズが、タスクＭＴの実行前では定まらないような場合においは、ローカルなコンパイラで一度プロファイリングすることにより、精度を高めた処理コストの算出を行うこともできる。なお、各ローカルコンパイラのプロファイリング情報は、後述するタスク処理コストテーブル４２０に格納される。
【００６７】
以上では処理コストを、処理サイクル数（時間）として定義したが、他にコストを電力として定義することで、電力が最小となるようなスケジューリングを行うことも可能である。例えば、処理サイクル数とタスクＭＴを完了すべき処理期限から、設定可能なＦＶ制御モード（周波数、動作電圧）のうち処理期限内で最小の消費電力となる動作モードを選択する。あるいは、ＰＥの消費電力は、
消費電力＝動作電圧2×駆動周波数
と見積もることができるので、処理期限内で消費電力が最小となるＦＶ制御モードの組み合わせを選択し、スケジューリングすればよい。
【００６８】
処理コスト解析Ｓ４では、求めた処理コストに基づいて、コンパイラ４０が、各マクロタスクＭＴについて、マクロタスクＭＴの階層構造を考慮した処理全体におけるマクロタスクＭＴの優先度ＧＣＰ（Global-Cost Priority）をそれぞれ設定する。
【００６９】
優先度ＧＣＰの設定の際には、各マクロタスクＭＴの最長クリティカルパス（ＣＰ）長を求め、この最長ＣＰ長の大きさに応じて優先度ＧＣＰを設定する。最長ＣＰ長は、上位のタスクＭＴが終わらないと次のタスクＭＴへ進めないマクロタスクグラフにおいて処理コストが最も長くなる経路を表す。
【００７０】
例えば、図５で示すような２つの並列性を持ったマクロタスクＭＴ１１〜ＥＭＴのマクロタスクＭＴ１３内の並列性を持ったタスクＭＴ１３−２、１３−３について優先度ＧＣＰを設定する場合について説明する。
【００７１】
まず、マクロタスクＭＴ１１の出口ノードとなるマクロタスクＥＭＴからマクロタスクＥＭＴ１３の出口までの最長ＣＰ長を（ａ）として演算する。マクロタスクＥＭＴ１３と出口のマクロタスクＥＭＴの間には、処理コスト＝７のマクロタスクＭＴ１４と、処理コスト＝５のマクロタスクＭＴ１５が存在する。したがって、マクロタスクＥＭＴ１３の出口までの最長ＣＰ長（ａ）＝７となる。
【００７２】
次に、優先度ＧＣＰを設定するタスクＭＴ１３−２について、マクロタスクＥＭＴ１３の出口ノードとなるタスクＥＭＴからタスクＭＴ１３−２の入口までの最長ＣＰ長を（ｂ）として演算する。タスクＭＴ１３−２と出口のタスクＥＭＴの間には、処理コスト＝１のタスクＭＴＧ１３−４があり、このタスクＭＴ１３−２の処理コスト＝５である。したがって、タスクＥＭＴＧの出口までの最長ＣＰ長（ｂ）＝６となる。したがって、タスクＭＴ１３−２の最長ＣＰ長＝（ａ）＋（ｂ）＝１３となる。そして、この最長ＣＰ長の値を優先度ＧＣＰとしてタスクＭＴ１３−２に設定する。
【００７３】
タスクＭＴ１３−３についても同様に最長ＣＰ長を演算すると、（ａ）＝７は同様であり、（ｂ）＝４となる。したがって、タスクＭＴ１３−３の最長ＣＰ長＝１１となり、この最長ＣＰ長がタスクＭＴ１３−３の優先度ＧＣＰとなる。
【００７４】
後述する処理では、優先度ＧＣＰに基づいて実行すべきタスクＭＴを決定する。このため、タスクＭＴ１３を処理する際には、タスクＭＴ１３−２とＭＴ１３−３どちらを優先するかを判断する際に、コンパイラ４０は優先度ＧＣＰの値の大きいタスクＭＴ１３−２を優先することになる。
【００７５】
つまり、優先度ＧＣＰが高いということは、処理コストが大きいことを意味し、これはマクロタスクＭＴ内で処理すべきタスクが多いことを意味している。したがって、あるマクロタスクを迅速に処理するには、まず、処理すべきタスクやデータの多いマクロタスクＭＴを優先して実行することで、下位（下層）のマクロタスクＭＴの処理を迅速にすることができる。
【００７６】
すなわち、優先度ＧＣＰが高いということは、当該タスクの内部だけではなく、その後続のタスクの数あるいは処理コストも多いことを示している。このため、優先度ＧＣＰが高いタスクについては、スケジューリングの際に早期に割り当てを行って実行することで、マクロタスク全体の処理を高速化することができる。
【００７７】
以上の処理を各タスク毎に最長ＣＰ長を優先度ＧＣＰとして演算し、マクロタスク実行優先度テーブル４２５へ格納する。
【００７８】
＜マクロタスク間並列性解析＝最早実行条件解析＞
コンパイラ４０はマクロタスクＭＴの優先度ＧＣＰを決定した後、データ依存・制御フロー解析処理４０２で抽出したマクロタスクＭＴ間の制御フローと、データ依存性を同時に解析した結果から、マクロタスクＭＴ間の並列性、つまり各マクロタスクＭＴを最も早く実行してよい条件（最早実行条件）を決定する（Ｓ５）。
【００７９】
この最早実行条件をグラフで可視的に示したものがマクロタスクグラフＭＴＧである。入力プログラム４００を解析して生成されたマクロタスクグラフＭＴＧの一例が、図２である。マクロタスク間の並列性解析結果は、マクロタスクグラフ依存情報テーブル４２１として計算機５０の外部記憶装置５１に保持され、後段のコンパイル処理で使用される。
【００８０】
図２については＜マルチグレイン並列処理の概念＞で述べたように、マクロタスクグラフＭＴＧ１＿２は実行前に並列順序関係は確定されており、あらかじめ固定的（静的）にタスクをスケジューリング可能である。
【００８１】
一方、マクロタスクＭＴ１＿３内のマクロタスクグラフＭＴＧ１＿３では条件分岐を含むことを示している。タスクＭＴ１＿３＿１の条件分岐は、当該タスクＭＴ１＿３＿１を実行しないと分岐方向が確定しないため、実行時の状況に応じたスケジューリングを行う必要がある。当該条件分岐が確定し、タスクＭＴ１＿３＿２またはタスクＭＴ１＿３＿３方向に分岐した場合、タスクＭＴ１＿３＿１からタスクＭＴ１＿３＿４にデータ依存関係を示す実線があるため、双方のタスクＭＴ１＿３＿３、ＭＴ１＿３＿４の実行が終了した時点で、マクロタスクＭＴ１＿３が完了する。
【００８２】
＜プロセッサグルーピング＞
次にコンパイラ４０は、生成されたマクロタスクグラフデータ依存情報テーブル４２１を参照し、マクロタスクグラフの形状や並列性に応じた、またはユーザからの指定に応じたプロセッサのグループ化を行う（Ｓ６）。
【００８３】
つまり、マクロタスクグラフＭＴＧで表現された上位階層のマクロタスクＭＴ、例えば、図２のマクロタスクＭＴ１＿２、ＭＴ１＿３の形状、並列性を解析し、当該マクロタスクＭＴの処理に必要となる汎用ＰＥ１０〜１３をグループ化し、上述したように、当該汎用プロセッサグループＰＧとアクセラレータグループ毎に対してタスクＭＴを割り当てる。
【００８４】
また、マクロタスクグラフＭＴＧの構成により、特定用途プロセッサへの負荷が大きい場合、汎用プロセッサグループＰＧで処理を代行する。なお、決定したグルーピング情報は、プロセッサグルーピングテーブル４２２として外部記憶装置５１に保持され、後段の処理で使用される。
【００８５】
本実施形態では、図２のマクロタスクグラフＭＴＧ１においてマクロタスクＭＴ１＿２とＭＴ１＿３の処理コストが同等であり、これらマクロタスク内部のマクロタスクグラフＭＴＧ１＿２、ＭＴＧ１＿３の実行には汎用プロセッサによる特定用途プロセッサの制御が必要であるため、２個の汎用プロセッサグループＰＧ１＿０，１＿１を定義する。また、マクロタスクグラフＭＴＧ１＿２では、ＤＲＰとＤＳＰを利用可能なタスクがスタティックに割り当てられることが分かるため、アクセラレータグループとして図３のアクセラレータグループＤＲＰとアクセラレータグループＤＳＰを定義する。
【００８６】
＜マクロタスクスケジューリング＞
コンパイラ４０は、次に、スタティックスケジュール及びダイナミックスケジュールによりタスクＭＴのスケジューリングを実施する（Ｓ７）。それぞれのスケジューリング方法の詳細は後述するが、以下簡単に説明する。
【００８７】
まず、タスクＭＴに条件分岐がなく最早実行条件が予め決定できるＭＴフローであれば、前者のスタティックスケジュールを適用し、コンパイラ４０が予めタスクＭＴのスケジューリングを行い、同期コード及びＦＶ制御コード（スケジューリングコード）をタスクＭＴ間に挿入する（Ｓ８）。
【００８８】
一方、もし、タスクＭＴに条件分岐がある、あるいはタスクＭＴの処理時間が実行時に変動するなど、コンパイル時に予測できないＭＴフローであれば、後者のダイナミックスケジュールを適用し、コンパイラ４０は、条件分岐などの状況に応じた制御を実行時に行うスケジューリングプログラムを生成する（Ｓ９）。
【００８９】
そして、コンパイラ４０はスケジューリングコードを各ＰＥ１０〜１７の種類毎にコンパイルして目的コードとしての出力コードを生成する（Ｓ１０）。ここで、ダイナミックスケジューリングの場合には、汎用ＰＥの命令セットに対応するスケジューリングコードと、特定用途ＰＥに対するタスクに対する出力コードを含む。特定用途ＰＥに対するタスクの出力コードは、特定用途ＰＥの命令セットで記述された出力コードと、汎用ＰＥの命令セットで記述された出力コードの双方を生成する。そして、スケジューリングコードの実行の時点（スケジューラ）で、この特定用途ＰＥ向けのタスクを特定用途ＰＥで実行するか汎用ＰＥで実行するかを判定する。特定用途ＰＥで実行するときには、特定用途ＰＥの命令セットで記述された出力コードを特定用途ＰＥに割り当て、汎用ＰＥで実行するときには汎用ＰＥの命令セットで記述された特定用途ＰＥ向けタスクを汎用プロセッサグループに割り当てる。
【００９０】
このＰＥ毎のコード生成処理は、スタティックスケジューリングでは、スケジューリングコードでどの種類のＰＥに割り当てたタスクであるのかが分かっているので、対象タスクについて割り当てたＰＥの出力コードを生成すればよい。
【００９１】
これに対してダイナミックスケジューリングでは、特定用途ＰＥ向けのタスクであっても、実行時点で特定用途ＰＥに処理が集中して処理待ち時間が過大になるのを防ぐため、汎用ＰＥで特定用途ＰＥ向けのタスクを実行する場合がある。このため、ダイナミックスケジューリングによるスケジューリングコードについては、特定用途ＰＥ向けのタスクは、特定用途ＰＥの種類に応じた出力コードを生成するのに加え、汎用ＰＥで処理する出力コードも生成しておく。
【００９２】
コンパイラ４０がスケジューリングプログラム（スケジューリングコード）を生成する利点は、従来のマルチプロセッサのようにＯＳあるいはライブラリに粗粒度タスクの生成及びスケジューリングを依頼すると、数千から数万クロックのオーバーヘッドが生じてしまう可能性があり、それを避けるためである。
【００９３】
マクロタスクスケジューリングＳ７では、上述した最早実行条件やマクロタスクＭＴ内の条件分岐の有無などにより、上記Ｓ１で生成したマクロタスクＭＴ毎に静的に目的コードを決定するスタティックスケジューリングＳ８と、実行時にタスク制御を行うスケジューリングコードを生成するダイナミックスケジューリングＳ９の何れか一方を選択して、スケジューリングを実行する。
【００９４】
上記スタティックスケジューリングＳ８及びダイナミックスケジューリングコード生成Ｓ９により、静的な目的コードと動的なスケジューリングコードが生成される（Ｓ１０）。そして、これらのコードは、各プロセッサ毎の実行コードに変換されて外部記憶装置などに出力される。
【００９５】
＜スタティックスケジューリング＞
まず、スタティックスケジューリングの処理の概要について図６を参照しながら説明する。
【００９６】
コンパイラ４０は、スタティックスケジューリングＳ８を開始すると、まず、スケジューリング時刻Ｔを０にセットしてから、この時刻で実行可能なタスクＭＴのうち、優先度ＧＣＰの最も高いタスクＭＴを割り当てを実施するタスクＭＴとして選択する（Ｓ８１）。このとき、コンパイラ４０は一時的にコンパイル用の仮想レディキューを一時的に設定し、この仮想レディキューに現在時刻で実行可能なタスクＭＴを投入する。そして、仮想レディキューのタスクＭＴを、優先度ＧＣＰの高い順にソートして、最も優先度ＧＣＰの高いタスクＭＴを割り当てるタスクＭＴとして抽出する。
【００９７】
次に、抽出したタスクＭＴについて、各ＰＥ毎の処理コストを求め、マクロタスクグラフ・データ依存情報テーブル４２１とローカルメモリ変数情報テーブル４２６（後述）からデータ転送コストを計算して、各プロセッサグループ上でのタスク終了時刻をそれぞれ推定する（Ｓ８２）。
【００９８】
このとき、タスク毎の処理コストは、各ＰＥ毎に上記タスク処理コストテーブル４２０から読み込んだものを用いる（Ｓ８２１）。また、データの転送コストは、マクロタスクグラフデータ依存情報テーブル４２１とローカルメモリ変数情報テーブル４２６から、並列依存性に基づいて各時刻におけるデータの転送コストを推定する（Ｓ８２２）。このデータの転送コストは、タスクが必要とするデータを、他ＰＥのローカルメモリＬＭ２２や集中共有メモリＣＳＭ１８から当該ＰＥのローカルメモリＬＭにロードするといったデータ転送情報を予測する。なお、データの転送コストは、例えば、クロック数（レイテンシ）などで表現することができ、ローカルメモリＬＭを有効に活用し、データの転送にかかる時間が最小となるものを選択する。
【００９９】
そして、タスクＭＴについて各プロセッサグループ上での処理コストとデータ転送コストを加算して実行に必要なコスト（実行コスト）を推定演算する。
【０１００】
次に、各プロセッサグループまたは各ＰＥ毎に対象となる時刻での実行コストに対応する時間を加えて終了時刻を推定する。
【０１０１】
つまり、終了時刻は次式のように表される。
【０１０２】
終了時刻  ＝  現在割り当てられている最後のタスクの終了時刻
＋  データ転送時間（タスク処理前と後を含む）
＋  タスク処理時間
対象となるタスクＭＴについて、上記終了時刻を各プロセッサグループ毎に演算しておく。なお、最早終了時刻は、あるプロセッサグループまたはあるＰＥに選択したタスクを実行させたと仮定したときに、タスクを終了するであろう時刻のうち最も早いものである。つまり、データの転送待ち等の変動要因を含まない終了時刻である。
【０１０３】
なお、上記終了時刻の演算において、対象となるプロセッサがＤＲＰの場合で、ＤＲＰのＤＲＰコアの構成を変更する必要があるときには、ＤＲＰコアの変更に要するオーバーヘッド（変更時間）を上記終了時刻の演算で加算する。
【０１０４】
次に、コンパイラ４０は、各タスクの各プロセッサグループ毎の終了時刻に基づいて、最も終了時刻が早い（＝処理時間が短い＝処理コストが小さい）プロセッサグループに当該タスクを割り当てる（Ｓ８３）。つまり、本来、アクセラレータグループＤＲＰやＤＳＰで実行するタスクであっても、アクセラレータのグループに処理が集中している場合には、汎用プロセッサグループＰＧに当該タスクを割り当てる。例えば、アクセラレータグループＤＳＰ，ＤＲＰに処理が集中している場合、アクセラレータグループに当該タスクを割り当てると、処理待ちの時間が長くなってしまう。そこで、アクセラレータグループ向けのタスクＭＴを汎用プロセッサグループＰＧで割り当てることで、実行時間そのものはアクセラレータグループよりも長くなるが、待ち時間がない分終了時刻が早くなり、マクロタスクＭＴ全体の処理時間が短縮されるのである。
【０１０５】
なお、スタティックスケジューリングでは、上記のようにプロセッサグループ単位でタスクを割り当てる他に、各ＰＥ毎にタスクの割り当てを行っても良い。つまり、スタティックスケジューリングを適用するマクロタスクグラフＭＴＧは、実行時点で処理の順序や実行するタスクが変動する要素がないため、汎用ＰＥと特定用途ＰＥ毎に個別にタスクの割り当てを実施することができる。
【０１０６】
次に、タスクの割り当てが決定すると、コンパイラ４０はマクロタスクグラフ・データ依存情報テーブル４２１とを参照して、プロセッサグループに割り当てたタスクＭＴの実行に必要なデータの転送命令を必要に応じて挿入する。
【０１０７】
ここで、データの転送命令としては、タスクＭＴの実行前に明示的にデータを読み込むプレロード命令や、タスクＭＴの実行後に明示的にデータを書き込むポストストア命令などがある。
【０１０８】
プレロード命令は、ＤＴＵ２４のＤＭＡＣを用いて各ＰＥ上のタスク処理のバックグラウンドでＣＳＭ１８または他のＰＥのＤＳＭ２３から当該ＰＥのＤＳＭ２３やローカルメモリ２２へデータを読み込む処理を行う。
【０１０９】
ポストストア命令は、当該ＰＥのＤＳＭ２３やローカルメモリ２２のデータを、タスク処理のバックグラウンドでＣＳＭ１８または他のＰＥのＤＳＭ２３へ書き込む処理を行う。
【０１１０】
プレロード命令の挿入処理は、当該タスクＭＴで必要とするデータが、ローカルメモリ２２上にない場合には、タスクＭＴの実行開始前に、ＤＴＵ２４のＤＭＡにより他のタスク（当該タスクＭＴの実行前のタスク）の実行とオーバーラップして、当該ＰＥのコア近接のメモリ（ローカルメモリＬＭ２２または分散共有メモリ２３）などにロードしておく。
【０１１１】
すなわち、コンパイラ４０は、割り当てが完了したタスクＭＴで必要となるデータについて、マクロタスクグラフ・データ依存情報テーブル４２１とローカルメモリ変数情報テーブル４２６を参照し、必要とするデータの場所を特定する。そして、必要とするデータが他のＰＥまたはＣＳＭ１８にあれば、当該ＰＥのローカルメモリ１８へ転送する指令を入力プログラム４００へ挿入する。あるいは、必要とするデータが当該ＰＥの分散共有メモリ２３にあれば、当該ＰＥのローカルメモリ１８へ転送する指令を入力プログラム４００へ挿入する。なお、プレロード命令は、一般的な汎用プロセッサがハードウェア実装するプリフェッチとは異なり、タスクＭＴに対応して明示的に付加するものである。
【０１１２】
また、タスクＭＴが完了した後のデータのストアに関しても、同一ＰＥに割り当てられた後続タスクのみにしかアクセスされないデータは、集中共有メモリ１８や分散共有メモリ２３等へのストアを行わずに、ローカルメモリ２２上に残しておく。そして、コンパイラ４０は、実行キュー内のタスクの内、当該データにアクセスする最後のタスクの実行終了時にローカルメモリ２２上のデータを集中共有メモリ１８や分散共有メモリ２３へ書き込むポストストア命令を実行するように入力プログラム４００へ挿入する。特に、スタティックスケジューリングでは、プログラム全体を見渡して、適切な箇所にデータ転送命令を配置することが可能となる。
【０１１３】
このように、マクロタスクグラフの階層構造に基づいて、データの転送命令を明示的に挿入することにより、データ転送コストを最小限に抑えることができる。つまり、タスク開始時のデータ転送の遅延や、直前のタスクで利用したデータを再度ローカルメモリ１８へ読み込むなどの無駄なストア処理を抑制できる。
【０１１４】
図７は、コンパイラ４０で行われるスタティックスケジューリングＳ８の詳細を示すフローチャートの一例である。本フローチャートは、上位階層のスケジューリングによって得られたマクロタスクＭＴから、同一時刻に異なるプロセッサグループ（汎用プロセッサグループＰＧ、アクセラレータグループ）に割り当てられたマクロタスク間について処理するものである。
【０１１５】
まず、Ｓ８０１では、対象のタスクについて、処理コストと優先度ＧＣＰをタスク処理コストテーブル４２０マクロタスク実行優先度テーブル４２５を参照して演算する。そして、スケジューリングの時刻を初期化（例えば、０リセット）する。
【０１１６】
Ｓ８０２では、現在時刻Ｔにおいて実行中のマクロタスクグラフＭＴＧにおいて、割り当て可能な汎用プロセッサグループＰＧまたはアクセラレータグループ（アクセラレータコア上）で実行可能なタスクＭＴを検出する。コンパイラ４０は、マクロタスクグラフ・データ依存情報テーブル４２１を参照して、現在時刻Ｔにおいて最早実行可能条件を満たすタスクＭＴのうち、割り当てが完了していないタスクＭＴを抽出する。
【０１１７】
Ｓ８０３では、当該時刻において割り当ての対象となるタスクが存在するかの判定を行う。割り当ての対象となるタスクの条件としては、当該時刻において割り当て可能な汎用プロセッサグループＰＧまたはアクセラレータグループ（アクセラレータコア上）で実行可能かつ上記Ｓ８０２で抽出した実行可能なタスクＭＴに含まれる、ということになる。この条件を満たすタスクＭＴが存在すればＳ８０４へ、存在しなければＳ８０８に進む。
【０１１８】
Ｓ８０４では、割り当ての対象とするタスクＭＴを選択する。ここでは、上記Ｓ８０３の条件を満たすタスクＭＴに対して優先度ＧＣＰを実行優先度テーブル４２５から参照し、優先度ＧＣＰの最も高いタスクＭＴを割り当てを実施するタスクＭＴとして選択する。
【０１１９】
Ｓ８０５では、上記選択したタスクＭＴを割り当てるプロセッサグループを決定する。選択したタスクＭＴについて、選択したタスクＭＴを実行可能なプロセッサグループ（汎用プロセッサグループＰＧまたはアクセラレータグループ）上で、選択したタスクＭＴの処理コストとデータ転送コストを前述したように計算して、各プロセッサグループ上でのタスクＭＴの終了時刻を推定演算し、最も終了時刻の早いプロセッサグループ（汎用プロセッサグループＰＧまたはアクセラレータグループあるいはアクセラレータコア（特定用途ＰＥ））を選択する。
【０１２０】
Ｓ８０６では、コンパイラ４０はマクロタスクグラフ・データ依存情報テーブル４２１を参照して、プロセッサグループに割り当てたタスクＭＴの実行に必要なデータ転送命令や、タスク処理とオーバーラップして行われるプレロード／ポストストアデータ転送命令を上述したように、必要に応じて挿入する。
【０１２１】
Ｓ８０７では、現在時刻Ｔにおける全てのＰＥ１０〜１７が保有するローカルメモリ２２の情報（データなどの内容）と、ＤＲＰ１４，１５の構成（ＤＲＰコアの構成の変化など）をローカルメモリ変数情報テーブル４２６へ書き込む。このローカルメモリ変数情報テーブル４２６には、各時刻Ｔにおけるローカルメモリ２２の変数情報が格納されているので、どのＰＥにどのようなデータがあるかを知ることができる。このテーブル４２６を利用することにより、データの転送コストを最小にするスケジューリングを行うことができる。また、その他必要に応じてシステム内の情報を適宜更新する。Ｓ８０７の処理後は再びＳ８０２に戻り、レディタスクの検出および割り当ての対象となるタスクが存在するかどうかの判定処理を行う。
【０１２２】
Ｓ８０８では、全てのタスクＭＴをプロセッサグループに割り当て済みであればコンパイラ４０は処理を終了し、割り当てていないタスクＭＴがあれば、Ｓ８０９へ進む。
【０１２３】
Ｓ８０９では、現在時刻Ｔに所定値を加算して、新たなレディタスクが発生するか、割り当て可能な汎用プロセッサグループあるいはアクセラレータコアが発生する時刻まで進めてからＳ８０２へ戻る。
【０１２４】
上記処理を実行することにより、条件分岐などのないマクロタスクＭＴについて静的なスケジューリングが完了し、全てのタスクＭＴはマクロタスクグラフＭＴＧの階層に応じて各プロセッサグループに割り当てられる。
【０１２５】
続いて、コンパイラ４０は、スタティックＦＶスケジューリング処理を行うことができる。本処理では、マクロタスクスケジューリングＳ７で生成されたスケジュール情報より、タスクの処理コスト及びスケジュール期限（処理期限）で決定される余裕度を判定し、当該余裕度に応じた動作周波数・供給電圧を決定するＰＥ動作モードを設定するため、ＦＶ制御情報を生成する。当該ＦＶ制御情報は、電源・ＦＶ制御スケジュールテーブル４２４として、外部記憶装置に保持される。なお、余裕度は、例えば、実行開始から実行完了までの処理時間と、処理期限までの時間から求まるものであり、各ＰＥ１０〜１７の性能上の余裕の度合いを示す。例えば、ＣＰＵ０の実行完了から処理期限までの時間が長い場合には余裕度が大きいと判定し、逆に実行完了から処理期限までの時間が短い場合には余裕度が小さいと判定できる。
【０１２６】
また、処理期限（許容時間）は、入力プログラムに記述したり、コンパイラ４０の処理時に図示しないコンソールから入力してもよい。
【０１２７】
＜ダイナミックスケジューリング＞
次に、図４で示した、ダイナミックスケジューリングコードの生成（Ｓ９）について以下に説明する。
【０１２８】
ダイナミックスケジューリング時は、タスクＭＴ内の条件分岐等の不確定要素によりコンパイル時にスケジューリング内容を決定することができない。このためコンパイラ４０は、タスクＭＴの処理結果に基づき、プログラム実行時に動的にスケジューリングを行うスケジューリングコード（スケジューリングプログラム）を生成する。
【０１２９】
スケジューリングコードは、処理結果に基づきタスクＭＴの起動や同期、及び当該ＭＴが必要とするデータのロードを行う。
【０１３０】
ここで、本発明のダイナミックスケジューリングによるスケジューリングコードは、汎用プロセッサグループＰＧにおいてスケジューラとして実行される。そして、スケジューラは、マクロタスクＭＴの階層化に応じて汎用プロセッサグループＰＧのレディキューと実行キューを変化させる。ここで、レディキューは実行可能なタスクを一時的に格納する記憶領域で、汎用プロセッサグループＰＧのグループに一つ割り当てられる。また、実行キューＥＣは割り当てたタスクＭＴを一時的に格納する記憶領域で、各プロセッサグループ毎に１つずつ割り当てられる。レディキューは、後述するように、プロセッサ間で共有可能かつ排他的にアクセスを制御可能（ロック可能）な共有記憶域に設定する。この共有記憶域としては集中共有メモリ（ＣＳＭ）１８や分散共有メモリ（ＤＳＭ）２３がある。
【０１３１】
＜スケジューラの概念＞
ダイナミックスケジューリングにおけるスケジューラ（スケジューリングコード）の概念について、図８を参照しながら以下に説明する。図８は時刻Ｔ０からヘテロジニアス・マルチプロセッサシステム１上でダイナミックスケジューリングによりタスクＭＴを実行する例を示す。なお、この例は、各汎用プロセッサグループがタスク処理とスケジューリングの両方を行う分散型のダイナミックスケジューリングを用いた場合のものであるが、各階層の並列度と利用可能なプロセッサの数を考慮して、ある汎用プロセッサがスケジューリングを専門的に行う、集中型のダイナミックスケジューリング手法を用いることも出来る。
【０１３２】
また、この例は簡単のため全ての階層でダイナミックスケジューリングが適用される形になっているが、本来は上述のように、マクロタスクグラフ内部の情報により適宜スタティックスケジューリングとダイナミックスケジューリングが使い分けられる。
【０１３３】
時刻Ｔ０におけるプロセッサグループは、汎用プロセッサグループＰＧ０がＣＰＵ０〜３を含み、アクセラレータグループでは２つのＤＲＰ０、１を含むＤＲＰグループＤＲＰＧと、２つのＤＳＰ０、１を含むＤＳＰグループＤＳＰＧから構成される。
【０１３４】
まず、時刻Ｔ０では、汎用プロセッサグループＰＧ０に含まれる汎用プロセッサのうち、代表するひとつのプロセッサ上で（図中ではＣＰＵ０）でスケジューラＳＣ０が実行される。そして、例えば、集中共有メモリ（ＣＳＭ）１８にレディキューＲＣ０が設定され、ＣＰＵ０の分散共有メモリ（ＤＳＭ）２３に汎用プロセッサグループＰＧ０に対応する実行キューＥＣ０（図示省略）が設定される。また、アクセラレータグループのそれぞれについて、各１つの実行キューが割り当てられる。ＤＲＰグループＤＲＰＧにはＤＲＰ０のＤＳＭ２３に実行キューＥＣＤＲが設定され、ＤＳＰグループＤＳＰＧにはＤＳＰ０のＤＳＭ２３に実行キューＥＣＤＳが設定される。
【０１３５】
スケジューラＳＣ０は、実行可能なタスクＭＴをレディキューＲＣ０に格納し、優先度の順に各実行キューＥＣ０、ＥＣＤＲ、ＥＣＤＳにタスクＭＴを割り当てる。各プロセッサグループでは、各プロセッサグループ内のＰＥ１０〜１７が実行キューＥＣ０、ＥＣＤＲ、ＥＣＤＳのタスクを取得して実行する。
【０１３６】
時刻Ｔ１では、スケジューラＳＣ０によりＰＧ０に割り当てられたタスク内部のマクロタスクグラフにおける並列性に応じてＰＧ０が内部で階層的に２つのプロセッサグループにグルーピングされる。図８ではＣＰＵ０および１からなるＰＧ０−０とＣＰＵ２および３からなるＰＧ０−１にグルーピングされている。このとき、ＰＧ０−０に含まれるＣＰＵ０およびＰＧ０−１に含まれるＣＰＵ２上では、内部階層に対応するスケジューラＳＣ１およびＳＣ２がそれぞれ起動され、集中共有メモリ（ＣＳＭ）１８にレディキューＲＣ１が、またＣＰＵ０のＤＳＭ２３に実行キューＥＣ１（図示省略）が、ＣＰＵ２のＤＳＭ２３に実行キューＥＣ２（図示省略）がそれぞれ設定される。このとき、ＣＰＵ０ではスケジューラＳＣ０から内部階層に対応するするスケジューラＳＣ１に制御が移る。
【０１３７】
なお、この例の場合、内部に階層を持つタスクを実行する際にはスケジューリング処理が内部階層に対応したスケジューラに委譲され、内部階層の処理が終了して上位の階層の処理に戻る際、再びもとの階層に対応したスケジューラに制御が移ることになる。
【０１３８】
次に、スケジューラＳＣ１が時刻Ｔ２において、汎用プロセッサグループＰＧ０−０にタスクを割り当てたとする。このタスクが内部にマクロタスクグラフを含む場合、内部のタスクの並列性に応じてＰＧ０−０に含まれる汎用プロセッサがさらに階層的にグルーピングされる。ここでは、ＰＧ０−０がＰＧ０−０−０およびＰＧ０−０−１に分割されてグルーピングされる。また、この内部マクロタスクグラフに対応するレディキューＲＣ２が集中共有メモリ（ＣＳＭ）１８上に、実行キューＥＣ２（図示省略）がＣＰＵ１のＤＳＭ２３に上に設定される。さらに、この階層に対応するスケジューラＳＣ３およびＳＣ４がそれぞれＣＰＵ０とＣＰＵ１上で起動される。ＣＰＵ０では、時刻Ｔ１の時と同様、スケジューラＳＣ１から、内部階層に対応するスケジューラＳＣ３に制御が移る。
【０１３９】
時刻Ｔ３でＰＧ０−０−０およびＰＧ０−０−１に分割されて処理されていた第３階層目の処理が終わったとすると、この時点でひとつ上の階層に処理が戻る。このときＣＰＵ０上で処理を行っていたスケジューラＳＣ３とＣＰＵ１上で処理を行っていたスケジューラＳＣ４が終了し、ひとつ上の階層を担当するスケジューラであるＳＣ１が再び利用される。さらに時刻Ｔ４でＰＧ０−０とＰＧ０−１にグルーピングされて処理が行われていた第２階層の処理が終了したとすると、このとき、スケジューラＳＣ１およびＳＣ２が終了してメイン階層に処理が移る。つまり、スケジューラＳＣ０がスケジューリング処理を再び担当する。
【０１４０】
時刻Ｔ１以降Ｔ４までは、汎用プロセッサグループＰＧが階層的にグルーピングされ、それぞれの階層あるいは汎用プロセッサグループでスケジューラＳＣが動作する。これらのスケジューラは相互にアクセラレータの実行キューＥＣＤＲおよびＥＣＤＳを参照してタスクの割り当てを調整することにより、アクセラレータグループの特定用途ＰＥに処理が偏るのを防ぐ。
【０１４１】
例えば、汎用プロセッサグループＰＧ０−０のスケジューラＳＣ１がＤＳＰグループＤＳＰＧを利用する際には、ＤＳＰグループの実行キューＥＣＤＳを参照し、既に複数のタスクが投入されていれば、ＤＳＰで実行した場合と、自身の汎用プロセッサグループＰＧ０−０で実行した場合の終了予定時刻を比較する。スケジューラＳＣ１は、この比較結果で終了予定時刻が早いほうを選択して自身のレディキューＲＣ１へ投入する。
【０１４２】
さらに、他の階層またはマクロタスクグラフに対応したレディキューの状況を参照し、各タスクの優先度を考慮することで、さらに効率よくアクセラレータの利用を融通することも出来る。
【０１４３】
なお、上記図８では、レディキューＲＣ０、ＲＣ１、ＲＣ２を集中共有メモリ（ＣＳＭ）１８に設定する例を示したが、多のＰＥからのアクセスに対して選択的にロックをかけられる共有メモリであればよく、例えば、各汎用プロセッサＣＰＵ０〜３の分散共有メモリ２３にレディキューＲＣを設定してもよい。また、図８では各階層に対してレディキューＲＣをひとつずつ用意する形になっているが、マクロタスクの種別で分類するなどのため、ひとつのマクロタスクグラフに対して複数個用意して利用することも可能である。さらに、この例では階層ごとに個別にスケジューラが起動される形になっているが、下位の階層に処理が移る際に引き続き同じプロセッサ上でスケジューラが動作する場合、上位階層のスケジューラを引き継いで利用する形式をとることも出来る。
【０１４４】
上記の例では、ある階層を担当するスケジューラがあるひとつのプロセッサ上で継続して動作しているが、分散型スケジューラの場合では、スケジューラが動作するのはその汎用プロセッサグループに含まれるプロセッサを代表するいずれかのプロセッサ上であればよく、メモリや負荷の状況によって、プロセッサグループ内の他の汎用プロセッサ上にスケジューラの処理が動的に移動することも可能である。例えば、図８においてＳＣ０は常にＣＰＵ０上で動作しているが、負荷やメモリの状況に応じて同じＰＧ０に参加しているＣＰＵ０〜３のいずれかにスケジューラの処理が移動することもある。
【０１４５】
＜スケジューリングコード＞
次に、ダイナミックスケジューリングによるスケジューリングコードについて、図９を参照しながら以下に説明する。
【０１４６】
コンパイラ４０は、ダイナミックスケジューリングコードＳ９により、図９に示すダイナミックスケジューリングコード９０を生成する。なお、ＣＰＵ０〜３でダイナミックスケジューリングコード９０を実行したときの機能をスケジューラＳＣとする。
【０１４７】
ダイナミックスケジューリングコード９０は、実行可能タスク情報取得部９１と、タスク終了時刻推定部９２と、タスク割り当て部９３と、タスク処理コストテーブル１４２０と、マクロタスクグラフ・データ依存情報テーブル１４２１と、マクロタスク実行優先度テーブル１４２５、ローカルメモリ変数情報テーブル１４２６と、実行中タスク情報テーブル１４２７とを含む。なお、各テーブル１４２０〜１４２６は、上記スタティックスケジューリングＳ８で用いたタスク処理コストテーブル４２０と、マクロタスクグラフ・データ依存情報テーブル４２１と、マクロタスク実行優先度テーブル４２５、ローカルメモリ変数情報テーブル４２６と同様の構成であり、コンパイラ４０が生成したものである。
【０１４８】
実行中タスク情報テーブル１４２７は、各時刻毎の各プロセッサグループの実行キューの情報と、各時刻毎に実行したタスクＭＴの情報を格納する。また、スケジューラを複数起動する場合には、上記各テーブル１４２０〜１４２７を、ＣＳＭ１８に配置して複数のスケジューラから参照、更新するようにしても良い。
【０１４９】
実行可能タスク情報取得部９１は、現在時刻Ｔで実行可能、かつ割り当ての行われていないタスクＭＴをマクロタスクグラフ・データ依存情報テーブル１４２１から抽出する。
【０１５０】
タスク終了時刻推定部９２では、抽出したタスクＭＴについて、マクロタスク実行優先度テーブル１４２５から各タスク毎の優先度ＧＣＰを参照して最も優先度の高いタスクＭＴを選択する。
【０１５１】
そして、選択したタスクＭＴについて、マクロタスク実行優先度テーブル１４２５に基づいて各プロセッサグループ毎の処理コストを演算し、マクロタスクグラフ・データ依存情報テーブル１４２１とローカルメモリ変数情報テーブル１４２６からデータ転送コストを計算する。各プロセッサグループ毎の処理コストとデータ転送コストに基づいて、前記スタティックスケジューリングと同様に各プロセッサグループ毎にタスク終了時刻を推定する。つまり、処理コストとデータ転送コストを加算した実行コストからタスクＭＴの終了時刻を（最早終了時刻）を上記スタティックスケジューリングと同様に推定演算する。
【０１５２】
このため、タスク処理コスト推定部９２は、タスク処理コストテーブル１４２０から読み込んだコストに基づいて抽出したタスクＭＴのプロセッサグループ毎の処理コストを演算するタスク処理コスト推定部９２１と、マクロタスクグラフ・データ依存情報テーブル１４２１のタスク間の依存関係と、ローカルメモリ変数情報テーブル１４２６内のデータの位置からデータ転送コストを計算するデータ転送コスト計算部９２２とを含む。
【０１５３】
そして、タスクの終了時刻は、各プロセッサグループのレディキューＲＣまたは実行キューＥＣを参照して、現在実行中のタスクがあれば当該タスクの終了時刻を加えたものを、割り当てようとするタスクの終了時刻に加算する。
【０１５４】
こうして、現在時刻Ｔで実行可能なレディタスクの終了時刻の推定が完了すると、タスク割り当て部９３によりプロセッサグループにタスクＭＴの割り当てが行われる。
【０１５５】
タスク割り当て部９３は、終了時刻の最も早いプロセッサグループに対象のタスクＭＴを割り当てる。つまり実行キューＥＣへ選択したタスクＭＴを投入する。
【０１５６】
次に、タスクの割り当てが決定すると、コンパイラ４０はマクロタスクグラフ・データ依存情報テーブル４２１とローカルメモリ変数情報テーブル４２６を参照し、必要とするデータの場所を特定する。そして、必要とするデータが他のＰＥまたはＣＳＭ１８にあれば、当該ＰＥのローカルメモリ１８へ転送する指令をスケジューリングコードへ挿入する。あるいは、必要とするデータが当該ＰＥの分散共有メモリ２３にあれば、当該ＰＥの分散共有メモリ２３からローカルメモリ１８へ転送する指令をスケジューリングコードへ挿入する。ダイナミックスケジューリングにおいてもスタティックスケジューリングと同様にデータの転送命令を挿入するが、ダイナミックスケジューリングではスケジューリングコード９０にデータ転送命令を挿入する点がスタティックスケジューリングと相違する。
【０１５７】
なお、上記においては、ローカルメモリ１８へ転送する指令をスケジューリングコードへ挿入する例を示したが、これに限定されるものではない。例えば、実行キューＥＣ内のタスクＭＴにデータ転送命令を付加したり、あるいは、データ転送命令を一種のタスクとして実行キューＥＣに投入してもよい。
【０１５８】
また、当該タスクの実行の前後にデータ転送が必要ではあるが、ローカルメモリ１８や共有メモリ（ＤＳＭやＣＳＭ）の内容によっては、プレロード命令やポストストア命令を挿入できない場合がある。このようなときには、予めタスクＭＴの実行コードにデータ転送ユニット２４に転送を実行させるための起動コード等を含めてもよい。
【０１５９】
以上のデータ転送命令により、ダイナミックスケジューリングにおいてもスタティックスケジューリングと同様にデータ転送コストを最小限に抑制することができる。  以上の機能により、ダイナミックスケジューリングコード９０は、複数のプロセッサグループに対してタスクＭＴを割り当てていく。なお、ダイナミックスケジューリングコード９０は、条件分岐等によりダイナミックスケジューリングが適用された階層の処理が開始される時点で起動され、同時にレディキューＲＣと実行キューＥＣが設定される。さらに下位の階層において再びダイナミックスケジューリングが適用される際には、階層に対応したスケジューラが、階層の処理開始時に新たに起動される。
【０１６０】
なお、ダイナミックスケジューリングコード９０は、その階層の並列性や利用可能なプロセッサ数などから、分散スケジューリング方式あるいは集中スケジューリング方式のどちらかの形式を選択して実行される。分散スケジューリング方式が選択された階層では、その階層内の汎用プロセッサグループそれぞれの上でスケジューラが動作し、スケジューリングとタスク実行が交互に行われる。集中スケジューリング方式では、その階層の処理に参加する汎用プロセッサのうち、ある１つのがスケジューラの動作するプロセッサグループとして定義され、他の汎用プロセッサで構成された汎用プロセッサグループ、あるいは自らに対するタスク割り当てを担当する。このとき、スケジューリングを担当するプロセッサグループ以外はスケジューリング処理を行わず、タスク実行に専念する。
【０１６１】
図１０は、ダイナミックスケジューリングコード９０（スケジューラＳＣ）で行われる処理の一例を示すフローチャートである。
【０１６２】
まず、Ｓ９０１では、コンパイル時に生成したタスク処理コストテーブル１４２０と、マクロタスクグラフ・データ依存情報テーブル１４２１と、マクロタスク実行優先度テーブル１４２５と、ローカルメモリ変数情報テーブル１４２６とを読み込んで、各タスクＭＴの処理コストと優先度などを取得する。
【０１６３】
Ｓ９０２で、現在時刻Ｔにおいて実行可能なタスクＭＴであるレディタスクを更新し、マクロタスク実行優先度テーブル１４２５を参照して優先度ＧＣＰの高い順にソートを実施し、当該スケジューラＳＣを実行する汎用プロセッサグループＰＧのレディキューＲＣへ投入する。
【０１６４】
Ｓ９０３では、現在時刻Ｔにおいて割り当ての対象となるタスクＭＴが存在するか判定を行う。割り当ての対象となるタスクＭＴの条件としては、上記Ｓ９０２でレディキューに投入されており、当該時刻において先行割り当ての上限に達していない汎用プロセッサグループあるいはアクセラレータコア上で実行可能である、ということになる。この条件を満たすタスクＭＴが存在すればＳ９０４へ、存在しなければＳ９０８に進む。
【０１６５】
Ｓ９０４では、マクロタスク実行優先度テーブル１４２５を参照し、上記Ｓ９０３の条件を満たすタスクＭＴ中から最も優先度ＧＣＰが高いものを選択する。
【０１６６】
Ｓ９０５では、選択したタスクＭＴについてマクロタスク実行優先度テーブル１４２５からコストを参照して各プロセッサグループ毎の処理コストを演算する、さらにマクロタスクグラフ・データ依存情報テーブル１４２１のタスク間の依存関係と、ローカルメモリ変数情報テーブル１４２６のデータの位置からデータ転送コストを計算する。求めた処理コストとデータ転送コストから選択したタスクＭＴについて各プロセッサグループ毎の処理終了時刻を演算する。
【０１６７】
そして、最も終了時刻が早く、かつ、実行キューＥＣの割り当て済みタスクＭＴが上限（先行割り当ての上限）に達していないプロセッサグループを選択する。この選択したプロセッサグループの実行キューＥＣに、選択したタスクＭＴを投入する。
【０１６８】
Ｓ９０６では、投入したタスクＭＴを実行するために必要なデータ転送命令や実行キューＥＣ中のタスクに対するデータ転送を挿入する。なお、データ転送命令としては、上述したようなプレロード命令やポストストア命令など、ＤＴＵ２４によりタスク処理のバックグラウンドでデータ転送を行う命令を含む。
【０１６９】
Ｓ９０７では、現在時刻Ｔにおいて各ＰＥが保有するローカルメモリ２２の情報と、ＤＲＰ１４，１５の構成（ＤＲＰコアの構成の変化など）をローカルメモリ変数情報テーブル１４２６へ書き込む。また、その他必要に応じてシステム内の情報を適宜更新する。Ｓ９０７の処理後は再びＳ９０３に戻り、割り当ての対象となるタスクが存在するかどうかの判定処理を行う。
【０１７０】
Ｓ９０８では、全てのタスクＭＴを割り当て済みであればスケジューラＳＣは処理を終了し、割り当てていないタスクＭＴがあれば、Ｓ９０９へ進む。
【０１７１】
Ｓ９０９では、新たなレディタスクが生じるまで待機あるいは自らにタスクＭＴを割り当てて実行し、その後Ｓ９０２に戻る。
【０１７２】
上記図１０の処理を実行することにより、条件分岐などを含むマクロタスクＭＴについて動的にスケジューリングを実行し、複数のスケジューラＳＣからアクセラレータグループを共有して、全てのタスクＭＴはマクロタスクグラフＭＴＧの階層に応じて最適なプロセッサグループに割り当てられる。
【０１７３】
＜スケジューリングの結果＞
図１１は、入力プログラム４００としてコンパイラ４０へ入力し、生成されたマクロタスクグラフの一例を示す。
【０１７４】
入力プログラム４００をコンパイラ４０で解析した結果、図１１のように入力プログラム４００のマクロタスクグラフＭＴＧ１は、２つのマクロタスクＭＴ１＿１と、ＭＴ１＿２に逐次処理するよう分割される。なお、図中の表記は図２と同様である。また、図中斜線のハッチングはＤＳＰ向けのタスクを示し、図中十字のハッチングはＤＲＰ向けのタスクを示し、図中ハッチングのないタスクは汎用プロセッサＣＰＵ向けのタスクを示す。
【０１７５】
マクロタスクＭＴ１＿１、ＭＴ１＿２はサブルーチンとなっている。マクロタスクＭＴ１＿１は３階層のマクロタスクとなっており、マクロタスクＭＴ１＿１のマクロタスクグラフＭＴＧ１＿１は、最大３つの並列度を持つ条件分岐などの変動要素がないタスクＭＴ１＿１＿１〜ＭＴ１＿１＿６で構成され、このうちタスクＭＴ１＿１＿４はサブルーチンとなっている。サブルーチンのタスクＭＴ１＿１＿４のマクロタスクグラフＭＴＧ１＿１＿４は、最大２つの並列度を持つ条件分岐などの変動要素がないタスクＭＴ１＿１＿４＿１〜ＭＴ１＿１＿４＿２で構成される。マクロタスクＭＴ１＿１の内部は全て条件分岐など、実行時に処理内容が変動する要素がないためスタティックスケジューリングＳ８を適用することができる。
【０１７６】
マクロタスクＭＴ１＿１が完了した後に実行可能となるマクロタスクＭＴ１＿２は、３階層のマクロタスクとなっており、第２階層のマクロタスクとなるタスクＭＴ１＿２のマクロタスクグラフＭＴＧ１＿２は、最大２つの並列度を持つ条件分岐を有するマクロタスクＭＴ１＿２＿１〜ＭＴ１＿２＿１０で構成され、このうちタスクＭＴ１＿２＿７はサブルーチンとなっている。
【０１７７】
第２階層のタスクＭＴ１＿２＿１は所定の条件が成立したときには、２つの並列度を持つタスクＭＴ１＿２＿３とＭＴ１＿２＿４を並列実行し、所定の条件が成立しなかったときには、タスクＭＴ１＿２＿２を処理する。以下の説明では、所定の条件が成立してタスクＭＴ１＿２＿３、ＭＴ１＿２＿４を実行する例を示す。
【０１７８】
サブルーチンのタスクＭＴ１＿２＿４のマクロタスクグラフＭＴＧ１＿２＿７は、最大２つの並列度を持つ条件分岐を有するタスクＭＴ１＿２＿７＿１〜ＭＴ１＿２＿７＿７で構成される。第３階層のタスクＭＴ１＿２＿７＿１は所定の条件が成立したときには、２つの並列度を持つタスクＭＴ１＿２＿７＿２とＭＴ１＿２＿７＿３を並列実行し、所定の条件が成立しなかったときには、タスクＭＴ１＿２＿７＿４を処理する。以下の説明では、所定の条件が成立してタスクＭＴ１＿２＿７＿２とＭＴ１＿２＿７＿３を並列実行する例を示す。
【０１７９】
マクロタスクＭＴ１＿２では、第２階層と第３階層にそれぞれ条件分岐があるため、ダイナミックスケジューリング（Ｓ９）を適用する。
【０１８０】
この例では、第２階層以下で階層的に条件分岐が行われるため、並列的にダイナミックスケジューリングを行うことができ、スケジューラＳＣを複数並列実行させる分散ダイナミックスケジューリングを行う。
【０１８１】
図１１に示したマクロタスクグラフＭＴＧ１で構成された入力プログラム４００をコンパイラ４０で、コンパイルした出力コードを実行した結果を図１２及び図１６に示す。図１２は、タスクＭＴの処理時刻とキューの関係を示すタイムチャートであり、図１６はタスクＭＴの処理時刻とプロセッサグループの関係を示すタイムチャートである。これら図１２、図１６では、４つの汎用プロセッサＣＰＵ０〜３と１つのＤＲＰ０と、１つのＤＳＰ０を用いて実行する例を示し、アクセラレータグループはＤＲＰ、ＤＳＰともに１つの構成である。なお、汎用プロセッサグループに関しては実行キューのタスク保持上限数が１であるので、図１２では汎用プロセッサグループの実行キューを省略した。
【０１８２】
時刻Ｔ０では第一階層（メインプログラムに相当）であるマクロタスクグラフＭＴＧ１の実行が開始される。この階層では４つの汎用プロセッサＣＰＵ全体がひとつのグループを構成し（ＰＧ１＿０）、これにＭＴ１＿１が割り当てられる。同時に、ＭＴ１＿１の内部マクロタスクグラフであるＭＴＧ１＿１の並列性に応じて、ＭＴＧ１＿１のタスクを実行する階層においては、ＣＰＵ０、１からなる汎用プロセッサグループ（ＰＧ１＿１＿０）およびＣＰＵ２、３からなる汎用プロセッサグループ（ＰＧ１＿１＿１）の２つが形成される。この時点では、スタティックスケジューリングにより、タスクＭＴ１＿１＿１が汎用プロセッサグループＰＧ１＿１＿０に割り当てられて実行される。時刻Ｔ１では、タスクＭＴ１＿１＿２が汎用プロセッサグループＰＧ１＿１＿０で実行され、サブルーチンのタスクＭＴ１＿１＿４が汎用プロセッサグループＰＧ１＿１＿１に割り当てられる。ここで、ＭＴ１＿１＿４は内部にＭＴＧ１＿１＿４をもっているため、ＭＴ１＿１＿４が割り当てられた汎用プロセッサグループＰＧ１＿１＿１に含まれる汎用プロセッサＣＰＵ２、３をさらにグルーピングしてタスクを割り当てる単位とする。ここでは、ＭＴＧ１＿１＿４内部の並列度等を考慮して、このマクロタスクグラフ内で利用可能なＣＰＵ２、３でひとつの汎用プロセッサグループ（ＰＧ１＿１＿４＿０）を形成する。ＭＴＧ１＿１＿４では、時刻Ｔ１の時点でＰＧ１＿１＿４＿０上でタスクＭＴ１＿１＿４＿１が実行される。そして、タスクＭＴ１＿１＿４＿１が終了した後には、ＤＳＰ用のタスクＭＴ１＿１＿４＿３が汎用プロセッサグループＰＧ１＿１＿４＿０で実行される。ＤＳＰ０では、最初にタスクＭＴ１＿１＿３を実行した後、タスクＭＴ１＿１＿４＿２を実行する。これは、優先度ＧＣＰと終了時刻の比較の結果、タスクＭＴ１＿１＿４＿２の後に、ＤＳＰ０でタスクＭＴ１＿１＿４＿３を処理するよりも、アイドルとなってしまう汎用プロセッサグループＰＧ１＿１＿４＿０を利用した方がマクロタスクグラフＭＴＧ１＿１＿４の処理が早期に完了するためである。
【０１８３】
なお、この例において、時刻Ｔ０〜Ｔ２の期間ではスタティックスケジューリングが適用されるマクロタスクグラフのみが実行されるためこれらの割り当てはコンパイル時に静的に決定されており、またダイナミックスケジューリングで用いられるレディキューＲＣ及び実行キューＥＣは使用されていない。
【０１８４】
時刻Ｔ２においては、マクロタスクグラフＭＴＧ１内のＭＴ１＿２がＭＴ１＿１と同様に、４つの汎用プロセッサＣＰＵ全体で構成されるＰＧ１＿０に割り当てられ、実行される。このとき、ＭＴ１＿２は内部にマクロタスクグラフＭＴＧ１＿２を持つ。ＰＧ１＿０に含まれる各汎用プロセッサはＭＴＧ１＿２の並列度等を考慮して、ＣＰＵ０、１からなる汎用プロセッサグループ（ＰＧ１＿２＿０）およびＣＰＵ２、３からなる汎用プロセッサグループ（ＰＧ１＿２＿１）の２にグルーピングされ、これらがマクロタスクの割り当て・実行単位となる。ここでは、ＭＴＧ１＿２が条件分岐を含むことから実行時にタスクの割り当てを決定するダイナミックスケジューリングが適用され、特に並列度とプロセッサの数の関係などから、各プロセッサグループがスケジューリングとタスクの実行の両方を行う分散ダイナミックスケジューリングが選択されている。汎用プロセッサグループＰＧ１＿２＿０のＣＰＵ０ではスケジューラＳＣ１＿２＿０が起動し、汎用プロセッサグループＰＧ１＿２＿１のＣＰＵ２ではスケジューラＳＣ１＿２＿１が並列して起動する。
また、ＭＴＧ１＿２に対応するレディキューＲＣ１＿２が集中共有メモリ１８上に設定され、これはＣＰＵ０〜３（ＰＧ１＿２＿０およびＰＧ１＿２＿１）で共有される。時刻Ｔ２では、スケジューラＳＣ１＿２＿０が実行可能なタスクＭＴ１＿２＿１をレディキューＲＣ１＿２に投入し、これが時刻Ｔ３から汎用プロセッサグループＰＧ１＿２＿０に割り当てられ、実行される。なお、時刻Ｔ２〜Ｔ７までの期間、ＭＴＧ１＿２に含まれるマクロタスクに関しては、スケジューラＳＣ１＿２＿０がＰＧ１＿２およびアクセラレータグループへの割り当てを、スケジューラＳＣ１＿２＿１がＰＧ１＿２＿１およびアクセラレータグループへの割り当てを行う。
【０１８５】
時刻Ｔ４でタスクＭＴ１＿２＿１が完了すると、条件分岐の結果タスクＭＴ１＿２＿３とタスクＭＴ１＿２＿４がレディキューＲＣ１＿２へ投入され、優先度ＧＣＰの高い順にソートする。２つのタスクは、ＭＴ１＿２＿３がＤＳＰ用のタスクで、ＭＴ１＿２＿４がＤＲＰ用のタスクであり、アクセラレータグループがアイドル状態であるので、スケジューラＳＣ１＿２＿０は、レディキューＲＣ１＿２からタスクＭＴ１＿２＿３をＤＳＰ０の実行キューへ投入し、タスクＭＴ１＿２＿４をＤＲＰ０の実行キューへ投入する。
【０１８６】
２つの特定用途ＰＥでの処理（ＭＴ１＿２＿３、ＭＴ１＿２＿４）が時刻Ｔ６で完了すると、スケジューラＳＣ１＿２＿１は、レディキューＲＣ１＿２に図１１のタスクＭＴ１＿２＿６とタスクＭＴ１＿２＿７を投入し、ＭＴ１＿２＿６を担当であるＰＧ１＿２＿１に割り当て、これが実行される。その後スケジューラＳＣ１＿２＿０はタスクＭＴ１＿２＿７をＰＧ１＿２＿０に割り当てる。ＭＴ１＿２＿７は内部にマクロタスクグラフＭＴＧ１＿２＿７を含むため、その並列性等を考慮して、ＭＴＧ１＿２＿７を実行するＰＧ１＿２＿０は内部でＣＰＵ０からなるＰＧ１＿２＿７＿０とＣＰＵ１からなるＰＧ１＿２＿７＿１とに階層的にグルーピングされ、それぞれでスケジューラＳＣ１＿２＿７＿０およびスケジューラＳＣ１＿２＿７＿１が起動される。また、マクロタスクグラフＭＴＧ１＿２＿７用のレディキューＲＣ１＿２＿７が集中共有メモリ（ＣＳＭ）１８に設定され、ＰＧ１＿２＿７＿０とＰＧ１＿２＿７＿１で共有される。これ以降時刻Ｔ７〜Ｔ１４までの期間、ＣＰＵ０上ではスケジューラＳＣ１＿２＿０とスケジューラＳＣ２１＿２＿７＿０が同時に存在するが、ＭＴＧ１＿２＿７内のタスクの処理を行っている間はスケジューラＳＣ１＿２＿７＿０が制御を担当し、時刻Ｔ１４でＭＴＧ１＿２＿７の処理を終えた時点でスケジューラＳＣ１＿２＿７＿０が終了し、再びスケジューラＳＣ１＿２＿０に制御が移る。なお、ＭＴＧ１＿２以外の階層に制御が移らないＰＧ１＿２＿１では、この間もスケジューラＳＣ１＿２＿１が制御を担当する。
【０１８７】
ＰＧ１＿２＿７＿０は時刻Ｔ８でタスクＭＴ１＿２＿７＿１の処理が完了し、条件分岐の結果が出る。この例では、条件分岐の結果、タスクＭＴ１＿２＿７＿２とＭＴ１＿２＿７＿３を実行するので、スケジューラＳＣ１＿２＿７＿０は、汎用ＰＥ向けのタスクＭＴ１＿２＿７＿２と特定用途ＰＥ向けのＭＴ１＿２＿７＿２＿３をレディキューＲＣ１＿２＿７へ投入する。
【０１８８】
そして、時刻Ｔ９でスケジューラＳＣ１＿２＿７は汎用ＰＥ向けのタスクＭＴ１＿２＿７＿２をＰＧ１＿２＿７＿０へ投入し、ＤＳＰ向けのタスクＭＴ１＿２＿７＿３をＤＳＰ０へ割り当てて実行させる。
【０１８９】
スケジューラＳＣ１＿２＿１は、時刻Ｔ９で汎用ＰＥ向けのタスクＭＴ１＿２＿６が完了したので、２つのＤＲＰ向けのタスクＭＴ１＿２＿９、ＭＴ１＿２＿１０をレディキューＲＣ１＿２へ投入する。このとき、スケジューラＳＣ１＿２＿１は２つの優先度ＧＣＰを比較してタスクＭＴ１＿２＿９の優先度が高いのでレディキューＲＣ１＿２の先頭にタスクＭＴ１＿２＿９を投入し、その次にタスクＭＴ１＿２＿１０を投入する。そして、時刻Ｔ１０でスケジューラＳＣ１＿２＿１はタスクＭＴ１＿２＿９をＤＲＰ０の実行キューへ投入してＤＲＰ０に実行させる。次のタスクＭＴ１＿２＿１０をＤＲＰ０に実行させると、終了時刻が遅延するため、スケジューラＳＣ１はタスクＭＴ１＿２＿１０を時刻Ｔ１０で自プロセッサグループＰＧ１＿２＿１に投入して実行する。
【０１９０】
時刻Ｔ１１ではマクロタスクグラフＭＴＧ１＿２＿７のＤＳＰ向けのタスクＭＴ１＿２＿７＿３が完了するので、スケジューラＳＣ１＿２＿７＿１はレディタスクとなったＤＲＰ向けのタスクＭＴ１＿２＿７＿６をレディキューＲＣ１＿２＿７へ投入する。ＤＲＰ０では、他のスケジューラＳＣ１＿２＿１が割り当てたタスクＭＴ１＿２＿９を実行しているので、これをＤＲＰ０に割り当てた場合、このタスクＭＴ１＿２＿９が完了するまで実行キューで待機することになるが、それを考慮してもＤＲＰ０でＭＴ１＿２＿７＿６を実行したほうが効率が良いと判断し、スケジューラＳＣ１＿２＿７＿１はＭＴ１＿２＿７＿６をＤＲＰ０の実行キューに投入する。
【０１９１】
時刻Ｔ１２ではマクロタスクグラフＭＴＧ１＿２＿７の汎用ＰＥ向けのタスクＭＴ１＿２＿７＿２が完了するので、スケジューラＳＣ１＿２＿７＿０は実行可能となったＭＴ１＿２＿７＿５をレディキューＲＣ１＿２＿７へ投入する。ＤＲＰ０では、他のスケジューラＳＣ１＿２＿１が割り当てたタスクＭＴ１＿２＿９を実行しており、さらにＭＴ１＿２＿７＿６が実行キューで待機状態にある。スケジューラＳＣ１＿２＿７＿１はこれらを考慮してＤＲＰ向けタスクＭＴ１＿２＿７＿５の終了時刻を見積もって、自プロセッサグループＰＧ１＿２＿７＿１にＤＲＰ向けのタスクＭＴ１＿２＿７＿５を割り当てて時刻Ｔ１３から実行を開始する。
【０１９２】
一方、ＤＲＰ０の実行キューで待機状態となっていたタスクＭＴ１＿２＿７＿６は、時刻Ｔ１４で実行され、時刻Ｔ１５で完了し、全てのタスクＭＴが完了する。
【０１９３】
このように、条件分岐を含むマクロタスクグラフＭＴＧ１＿２及びＭＴＧ１＿２＿７では、複数のスケジューラをそれぞれの汎用プロセッサグループ上で並列して実行させる分散ダイナミックスケジューリングを行う。そして、本発明では、汎用プロセッサグループＰＧとアクセラレータグループを独立して扱うことにより、アクセラレータグループへのタスクの割り当てを複数の汎用プロセッサグループＰＧが行うことで、汎用プロセッサグループＰＧ間でアクセラレータグループの利用が偏るのを防止でき、リソースの有効な利用を実現できる。さらに、各スケジューラＳＣが、他の階層のタスクの情報を参照しあうことも可能である。これにより各階層間で優先度を円滑に調停でき、全体の処理速度を向上させることが可能となる。
【０１９４】
なお、上記ではスタティックスケジューリングにおいて、各ＰＥへ静的にタスクを割り当てる例を示したが、スタティックスケジューリングによって静的なスケジューリングコードを生成するようにしても良い。この場合、アクセラレータコアは、処理開始時にあらかじめスケジューリングされた処理の順番通りに投入されたタスクを保持する実行キューから適宜タスクを取得して実行する形態となる。
【０１９５】
また、上記では階層ごとに異なるスケジューラが利用される形となっているが、下位の階層に処理を移す際に同じプロセッサ上で引き続きスケジューラが動作する場合には、上位階層のスケジューラを引き継いで利用する形態をとることも考えられる。
【０１９６】
また、上記では汎用プロセッサグループに対応する実行キューの上限数を１としたが、アクセラレータグループ同様に上限数を複数個にすることで、汎用プロセッサグループに対しても先行割り当ておよびデータのプレロード等を設定することが可能である。
【０１９７】
＜第２実施形態＞
図１３、図１４及び図１７は、第２の実施形態を示し、ダイナミックスケジューリングのスケジューリングコードを、ひとつの汎用ＰＥを中心に処理する分散・集中ダイナミックスケジューリングを適用する例を示す。この第２実施形態では、スケジューリングコードを実行する汎用ＰＥを入力プログラムで静的に記述したもので、その他の構成は前記第１実施形態と同様である。
【０１９８】
図１３は、入力プログラム４００’としてコンパイラ４０へ入力し、生成されたマクロタスクグラフの他の一例を示す。
【０１９９】
入力プログラム４００’をコンパイラ４０で解析した結果、図１３のように、入力プログラム４００’のマクロタスクグラフＭＴＧ１は、２つのマクロタスクＭＴ１＿１と、ＭＴ１＿２に逐次処理するよう分割される。なお、図中の表記は図２と同様である。また、図中斜線のハッチングはＤＳＰ向けのタスクを示し、図中十字のハッチングはＤＲＰ向けのタスクを示し、図中ハッチングのないタスクは汎用プロセッサＣＰＵ向けのタスクを示す。
【０２００】
マクロタスクＭＴ１＿１、ＭＴ１＿２はサブルーチンとなっている。マクロタスクＭＴ１＿１は３階層のマクロタスクとなっており、マクロタスクＭＴ１＿１のマクロタスクグラフＭＴＧ１＿１は、最大３つの並列度を持つ条件分岐などの変動要素がないタスクＭＴ１＿１＿１〜ＭＴ１＿１＿６で構成され、このうちタスクＭＴ１＿１＿４はサブルーチンとなっている。サブルーチンのタスクＭＴ１＿１＿４のマクロタスクグラフＭＴＧ１＿１＿４は、最大２つの並列度を持つ条件分岐などの変動要素がないタスクＭＴ１＿１＿４＿１〜ＭＴ１＿１＿４＿２で構成される。マクロタスクＭＴ１＿１の内部は全て条件分岐など、実行時に変動する要素がないためスタティックスケジューリングＳ８を適用することができる。
【０２０１】
マクロタスクＭＴ１＿１が完了した後に実行可能となるマクロタスクＭＴ１＿２は、３階層のマクロタスクとなっており、第２階層のマクロタスクとなるタスクＭＴ１＿２のマクロタスクグラフＭＴＧ１＿２は、最大３つの並列度を持つ条件分岐を有するマクロタスクＭＴ１＿２＿１〜ＭＴ１＿２＿１６で構成され、このうちタスクＭＴ１＿２＿１１はサブルーチンとなっている。
【０２０２】
第２階層のタスクＭＴ１＿２＿１で所定の条件が成立したときには、３つの並列度を持つタスクＭＴ１＿２＿４とＭＴ１＿２＿５及びＭＴ１＿２＿５を並列実行し、所定の条件が成立しなかったときには、タスクＭＴ１＿２＿２とＭＴ１＿２＿３を並列して実行する。以下の説明では、所定の条件が成立してタスクＭＴ１＿２＿４、ＭＴ１＿２＿５、ＭＴ１＿２＿６を実行する例を示す。
【０２０３】
タスクＭＴ１＿２＿１で条件分岐が決定した後には、図示の実線に示すデータの依存性に従って各タスクＭＴが順次実行される。
【０２０４】
第２階層のサブルーチンのタスクＭＴ１＿２＿１１のマクロタスクグラフＭＴＧ１＿２＿７は、条件分岐の後に独立して実行されるタスクＭＴで構成される。第３階層のマクロタスクグラフＭＴＧ１＿２＿１１＿１は所定の条件が成立したときには、タスクＭＴ１＿２＿１１＿３を実行し、所定の条件が成立しなかったときには、タスクＭＴ１＿２＿１１＿４を処理する。以下の説明では、所定の条件が成立してタスクＭＴ１＿２＿１１＿３を実行する例を示す。
【０２０５】
マクロタスクＭＴ１＿２では、第２階層と第３階層にそれぞれ条件分岐があるため、ダイナミックスケジューリング（Ｓ９）を適用する。
【０２０６】
この例では、第２階層以下で階層的に条件分岐が行われるため、並列的にダイナミックスケジューリングを行うことができ、ひとつのスケジューラＳＣで集中的にタスクの割り当てを行い、第３階層の条件分岐は新たなスケジューラでタスクの割り当てを行う分散・集中ダイナミックスケジューリングの例を示す。
【０２０７】
図１３に示したマクロタスクグラフＭＴＧ１で構成された入力プログラム４００’をコンパイラ４０で、コンパイルした出力コードを実行した結果を図１４、図１７に示す。図１４は、タスクＭＴの処理時刻とキューの関係を示すタイムチャートであり、図１７は、タスクＭＴの処理時刻とプロセッサグループの関係を示すタイムチャートである。これら図１４、図１７では、前記第１実施形態の図１２、図１６と同様に、４つの汎用プロセッサＣＰＵ０〜３と１つのＤＲＰ０と、１つのＤＳＰ０を用いて実行する例を示し、アクセラレータグループはＤＲＰ、ＤＳＰともに１つの構成である。なお、汎用プロセッサグループに関しては、上記同様実行キューのタスク保持上限数が１であるので図１４中および以下文中では実行キューが省略されている。
【０２０８】
図１４、図１７において、時刻Ｔ０〜Ｔ２の期間では、上記図１２、図１６と同様にスタティックスケジューリングを適用して、メイン階層に対応する汎用プロセッサグループＰＧ１＿０とその内部で階層的にグルーピングされている２つの汎用プロセッサグループＰＧ１＿１＿０・ＰＧ１＿１＿１とＰＧ１＿１＿１内部で階層的に定義されるＰＧ１＿４＿０およびアクセラレータグループで、静的にタスクを実行する。スタティックスケジューリングの期間では、上記図１２、図１６と同様にレディキューＲＣ及び実行キューＥＣを使用せず、各ＰＥへ静的に割り当てられたタスクが実行される。
【０２０９】
時刻Ｔ２からはマクロタスクグラフＭＴＧ１＿２内の処理が開始される。マクロタスクグラフＭＴＧ１＿２を含むマクロタスクＭＴ１＿２が割り当てられた汎用プロセッサグループ（ＰＧ１＿０）は４つの汎用プロセッサを含む。マクロタスクグラフＭＴＧ１＿２内部の並列度やプロセッサの数等を考慮し、４つの汎用プロセッサのうちひとつにスケジューリング処理をさせる集中ダイナミックスケジューリングが選択され、汎用プロセッサはそれぞれ１つで１つの汎用プロセッサグループを形成する。ここでは、ＣＰＵ０が汎用プロセッサグループＰＧ１＿２＿０を、ＣＰＵ１が汎用プロセッサグループＰＧ１＿２＿１を、ＣＰＵ２がＰＧ１＿２＿２を、ＣＰＵ３がＰＧ１＿２＿３をそれぞれ構成する。また、集中スケジューラＳＣ１＿２が動作するＰＧ１＿２＿０のローカルメモリ（ＬＭ）２２上にレディキューＲＣ１＿２が設定される。上記図１２、図１６の分散ダイナミックスケジューリングでは、集中共有メモリ（ＣＳＭ）１８にレディキューＲＣ１＿２が設定されたのに対し、この分散・集中ダイナミックスケジューリングでは、スケジューリングを統括するスケジューラＳＣ１＿２が動作するＣＰＵ０のローカルメモリ２２にレディキューＲＣが設定される点が相違する。
【０２１０】
時刻Ｔ２では、スケジューラＳＣ１＿２が最も優先度ＧＣＰの高いタスクＭＴ１＿２＿１をレディキューＲＣ１＿２に投入し、時刻Ｔ３から汎用プロセッサグループＰＧ１＿２＿１に割り当てる。
【０２１１】
時刻Ｔ４で、条件分岐を含むタスクＭＴ１＿２＿１が完了する。スケジューラＳＣ１＿２は条件分岐の結果に基づいて、図１３に示したマクロタスクグラフＭＴＧ１＿２のタスクＭＴ１＿２＿４、タスクＭＴ１＿２＿５及びタスクＭＴ１＿２＿６の３つのタスクをレディキューＲＣ１＿２へ投入し、優先度ＧＣＰの高い順にソートする。３つのタスクのうち、ＭＴ１＿２＿５がＤＳＰ用のタスクで、ＭＴ１＿２＿４とＭＴ１＿２＿６はＤＲＰ用のタスクである。スケジューラＳＣ１＿２は、各タスクＭＴの優先度ＢＣＰと終了時刻に基づいて、タスクＭＴ１＿２＿４をレディキューＲＣ１＿２の先頭（優先度＝高）に並べ替え、タスクＭＴ１＿２＿５の処理順位を最後に設定する。
【０２１２】
この時刻Ｔ４では、アクセラレータグループがアイドル状態であるので、スケジューラＳＣ１＿２は、タスクＭＴ１＿２＿５をＤＳＰ０の実行キューに投入し、タスクＭＴ１＿２＿４をＤＲＰ０の実行キューへ投入し、その後タスクＭＴ１＿２＿６をＤＲＰ０の実行キューへ先行して投入する。スケジューラＳＣ１＿２は、時刻Ｔ４では、３つの汎用プロセッサグループＰＧ１＿２＿１〜ＰＧ１＿２＿２がアイドル状態であるので、ＤＲＰ用のタスクＭＴ１＿２＿６をＰＧ１＿２＿１〜ＰＧ１＿２＿２に割り当てることができる。しかし、スケジューラＳＣ１＿２は、タスクＭＴ１＿２＿４が終了するまで待機させても、ＤＲＰ０でタスクＭＴ１＿２＿６を実行した方が全体としての終了時刻は短くなると見積もって、タスクＭＴ１＿２＿６をＤＲＰ０に先行して割り当てる。
【０２１３】
時刻Ｔ５では、アクセラレータグループの各特定用途ＰＥは実行キューのタスクを取得して実行する。ＤＲＰ０は時刻Ｔ６でタスクＭＴ１＿２＿４を完了すると、実行キューで待機していたタスクＭＴ１＿２＿６の実行を開始する。
【０２１４】
ＤＳＰ０は時刻Ｔ７でタスクＭＴ１＿２＿５を完了する。スケジューラＳＣ１＿２は、図１３のマクロタスクグラフＭＴＧ１＿２におけるデータ依存情報から、タスクＭＴ１＿２＿５の後にタスクＭＴ１＿２＿９とＭＴ１＿２＿１０が実行可能になることを検出する。そして、スケジューラＳＣ１＿２は、この時刻Ｔ７で２つのタスクＭＴ１＿２＿９、ＭＴ１＿２＿１０をレディキューＲＣ１＿２へ投入する。これら２つのタスクＭＴ１＿２＿９、ＭＴ１＿２＿１０は汎用プロセッサ向けのタスクであるので、スケジューラＳＣ１＿２は時刻Ｔ８で、汎用プロセッサグループＰＧ１＿２＿１にタスクＭＴ１＿２＿９を割り当て、ＰＧ１＿２＿２にタスクＭＴ１＿２＿１０を割り当てて実行させる。
【０２１５】
一方、ＤＲＰ０では時刻Ｔ８でタスクＭＴ１＿２＿６が完了したので、スケジューラＳＣ１＿２は、図１２、図１６で示したマクロタスクグラフＭＴＧ１＿２からサブルーチンであるタスクＭＴ１＿２＿１１をレディキューＲＣ１＿２へ投入し、アイドル状態であるＰＧ１＿２＿３に割り当てる。このときＭＴ１＿２＿１１は内部に条件分岐を含むマクロタスクグラフＭＴＧ１＿２＿１１を含むが、ＰＧ１＿２＿３を構成する汎用プロセッサはＣＰＵ３が１つのみであることと、ＭＴＧ１＿２＿１１内部の構造から、ＰＧ１＿２＿３に含まれるＣＰＵ３が汎用プロセッサグループＰＧ１＿２＿１１＿０を構成し、汎用プロセッサがスケジューリングとタスク実行の両方を交互に行う分散ダイナミックスケジューリングが適用される。また、スケジューラＳＣ１＿２＿２＿１１＿０がＣＰＵ３で起動され、分散共有メモリ（ＤＳＭ）２３にレディキューＲＣ１＿２＿１１が設定される。この例では、マクロタスクグラフＭＴＧ１＿２＿１１を実行する階層にはひとつのＰＧしかないが、複数のＰＧを含む場合にはレディキューＲＣ１＿２＿１１が階層内のＰＧで共有される。
【０２１６】
そして、スケジューラＳＣ１＿２＿１１＿０は時刻Ｔ９でタスクＭＴ１＿２＿１１＿１をレディキューＲＣ１＿２＿１１へ投入する。このタスクＭＴ１＿２＿１１＿１は汎用プロセッサ向けのタスクであるので、スケジューラＳＣ１＿２＿１１＿０は時刻Ｔ１０でプロセッサグループＰＧ１＿２＿１１＿０に割り当てて、実行させる。
【０２１７】
時刻Ｔ１１では、ＰＧ１＿２＿１１＿０に割り当てられたタスクＭＴ１＿２＿１１＿１が完了して、図１３に示した条件分岐の結果、ＤＳＰ用のタスクＭＴ１＿２＿１１＿３へ分岐する。スケジューラＳＣ１＿２＿１１＿０は、ＤＳＰ用のタスクＭＴ１＿２＿１１＿３をレディキューＲＣ１＿２＿１１へ投入する。そして、時刻Ｔ１２でスケジューラＳＣ１＿２＿１１＿０はタスクＭＴ１＿２＿１１＿３をＤＳＰ０の実行キューへ投入して実行させる。
【０２１８】
時刻Ｔ１３では、ＰＧ１＿２＿２のタスクＭＴ１＿２＿１０が完了する。この時点では、ＰＧ１＿２＿１のタスクＭＴ１＿２＿９が未完了であるので、図１３のマクロタスクグラフＭＴＧ１＿２のデータ依存関係から、スケジューラＳＣ１＿２＿０はＤＲＰ用のタスクＭＴ１＿２＿１６のみが実行可能であるので、このタスクＭＴ１＿２＿１６をレディキューＲＣ１＿２へ投入し、時刻Ｔ１４からＤＲＰ０に実行させる。
【０２１９】
時刻Ｔ１５では、ＰＧ１＿２＿１のタスクＭＴ１＿２＿９が完了し、図１３のマクロタスクグラフＭＴＧ１＿２のデータ依存関係から、スケジューラＳＣ１＿２はＤＲＰ用のタスクＭＴ１＿２＿１５が実行可能となったので、ＤＳＰ用のタスクＭＴ１＿２＿１５をレディキューＲＣ１＿２へ投入する。この時点でＤＲＰ０はスケジューラＳＣ１＿２＿１１＿０のタスクを実行中であるので、スケジューラＳＣ１＿２は、終了時刻を見積もった結果、このＤＲＰ用のタスクＭＴ１＿２＿１５を汎用プロセッサのＰＧ１＿２＿２に割り当てて時刻Ｔ１６から実行させる。
【０２２０】
時刻Ｔ１７ではＤＳＰ０のタスクＭＴ１＿２＿１１＿３が完了するので、マクロタスクグラフＭＴＧ１＿２＿１１を処理するスケジューラＳＣ１＿２＿１１＿０は、ＤＲＰ用のタスクＭＴ１＿２＿１１＿５をレディキューＲＣ１＿２＿１１へ投入する。この時点ではＤＲＰ０がスケジューラＳＣ１＿２のタスクＭＴ１＿２＿１６を実行中であるが、スケジューラＳＣ１＿２＿１１＿０はタスクＭＴ１＿２＿１１＿５を汎用プロセッサのＰＧ１＿２＿１１＿０で実行するよりも、ＤＲＰ０が空くのを待った方が終了時刻が早いと判定して、ＤＲＰ０の実行キューへタスクＭＴ１＿２＿１１＿５を投入する。
【０２２１】
時刻Ｔ１８では、ＤＲＰ０がスケジューラＳＣ１＿２のタスクＭＴ１＿２＿１６を完了し、実行キューにあるスケジューラＳＣ１＿２＿１１＿０のタスクＭＴ１＿２＿１１＿５を実行する。
【０２２２】
時刻Ｔ１９では、全ての処理が完了する。
【０２２３】
なお、時刻Ｔ９からＴ１９までの間、スケジューラＳＣ１＿２からはＰＧ１＿２＿３はＭＴ１＿２＿１１を実行中であるという形に見え、その間ＰＧ１＿２＿３に対してスケジューラＳＣ１＿２からの割り当ては行われない。ＭＴ１＿２＿１１（つまりマクロタスクグラフＭＴＧ１＿２＿１１）の実行が終了した後、ＰＧ１＿２＿３は再びスケジューラＳＣ１＿２からの割り当ての対象になる。
この例では、マクロタスクグラフＭＴＧ１＿２におけるスケジューラＳＣ１＿２を実行するＣＰＵ０は、タスクの処理を行わずにスケジューリングを実施しているが、マクロタスクグラフの形状や負荷状況によってはスケジューリング処理の合間にタスク処理を行うことも出来る。さらに、他のスケジューラとレディキューＲＣ１＿２を共有する必要がないので、スケジューラＳＣ１＿２を実行するＣＰＵ０のローカルメモリ（ＬＭ）２２にレディキューＲＣ１＿２を設定することで、レイテンシを低下させて処理の高速化を図ることができる。
【０２２４】
また、集中ダイナミックスケジューリングが適用されている階層のさらに下位の階層で再び集中ダイナミックスケジューリングが適用される場合、上位階層でスケジューラが動作していたプロセッサ上で下位階層のスケジューラを動作させることも出来る。これにより、スケジューリング処理に無駄にプロセッサを割く必要がなくなり、各階層でプロセッサを有効に利用できる。
【０２２５】
なお、上記図１２、図１４及び図１７では、マクロタスクグラフＭＴＧの構造上、スタティックスケジューリングの後にダイナミックスケジューリングを行う例を示したが、マクロタスクグラフＭＴＧの構造が、スタティックスケジューリングとダイナミックスケジューリングを並列実行可能な場合には、複数の汎用プロセッサグループＰＧでそれぞれのスケジューリングを実行することができる。
【０２２６】
＜第３実施形態＞
図１５は、第３の実施形態を示し、前記第１実施形態のアクセラレータグループの実行キューを各特定用途ＰＥ毎に設定したもので、その他の構成は前記第１実施形態と同様である。
【０２２７】
前記第１実施形態の図８では、アクセラレータグループの特定用途ＰＥの種別毎にグループを設定し、各グループにひとつの実行キューを設定する例を示したが、図１５で示すように、アクセラレータグループの特定用途ＰＥ毎に実行キューを設けても良い。
【０２２８】
つまり、アクセラレータグループは特定用途ＰＥの種別毎にＤＳＰグループＤＳＰＧとＤＲＰグループＤＲＰＧを構成し、ＤＳＰグループＤＳＰＧ内では、各ＤＳＰ０、１の分散共有メモリ２３毎に実行キューＥＣＤＳ０、１を設け、ＤＲＰグループＤＲＰＧ内では、各ＤＲＰ０、１の分散共有メモリ２３毎に実行キューＥＣＤＲ０、１を設けるようにしてもよい。
【０２２９】
この場合、汎用プロセッサグループＰＧのスケジューラＳＣが処理コストの見積もり等を行う場合には、アクセラレータグループの各グループ単位で見積もりを行い、実際にタスクの割り当てを行う際には、各特定用途ＰＥの実行キューに投入する。この場合も、汎用プロセッサグループＰＧではスケジューリングの際には、アクセラレータグループの種別毎にタスクの割り当てを検討するので、上記と同様に、複数の汎用プロセッサグループＰＧで特定用途ＰＥを共有することができ、特定用途ＰＥのリソースが不足するのを防止することができる。
【０２３０】
また、上記第１実施形態及び第２実施形態では各階層における汎用プロセッサのグルーピングを均等に分割する形になっているが、必ずしもそうである必要はない。マクロタスクグラフの形状や各マクロタスクのコスト、また負荷状況等に応じて、不均等なグルーピングを行うこともできる。こういった場合でも、同様の方式を用いて効率的なタスクスケジューリングを行うことが可能である。
【０２３１】
＜第４実施形態＞
図１８は、第４の実施形態を示し、前記第１ないし第３実施形態のスケジューリングをＧＲＩＤコンピューティングに適用する例を示すブロック図である。図１８では、ネットワーク２００を介して各種スーパーコンピュータやサーバ、ＰＣ等の計算機が接続されている。こういった異機種分散環境においては、各計算資源をその機能や特性に応じて汎用プロセッサあるいはアクセラレータとしてグルーピングして定義することで、上記スケジューリング手法が適用可能となる。
【０２３２】
図１８では、例えばＡ社製のスーパーコンピュータがアクセラレータグループＡ（１１０）として定義され、Ｂ社製のスーパーコンピュータ２台がアクセラレータグループＢ（１２０として定義され、またＣ社製のサーバがアクセラレータグループＣ（１３０）として定義されている。また、ＰＣクラスタやＰＣなどのネットワーク２００に接続可能な汎用計算装置が汎用プロセッサグループ１４０としてグルーピングされている。この汎用プロセッサグループ１４０に含まれる各計算機は、階層的なグルーピングの対象となる。以上のように各グループを定義することで、上記のスケジューリング手法を適用することができる。各アクセラレータグループＡ〜Ｃと、汎用プロセッサグループは異なる命令セットを実行する計算機であり、前記第１ないし第３の実施形態のアクセラレータグループと汎用プロセッサグループと同様に扱うことで、アクセラレータグループＡ〜Ｃと汎用プロセッサグループをネットワーク２００で接続し、処理を分散するＧＲＩＤコンピューティングに本発明を適用できる。
【０２３３】
なお、アクセラレータグループや汎用プロセッサグループ等のグルーピングは必ずしも図１８の様に定義される必要はなく、処理の内容や各計算機の機能・特性によって適宜変更することが可能である。例えば、図１８では汎用プロセッサグループにゲーム機等も含まれているが、ゲーム機で高速に処理可能な内容を多く含むプログラムを実行するような場合には、ゲーム機群を汎用プロセッサグループから独立したアクセラレータグループとして定義するということも出来る。
【０２３４】
＜まとめ＞
以上のように、本発明の各実施形態によれば、多種のプロセッサエレメントＰＥを集積するマルチプロセッサシステムにおいて、当該ＰＥを効率よく動作させるプログラムの分割配置および制御コードを生成するコンパイラ４０により、当該プロセッサシステムの性能を最大限活用しつつ、最小限の処理時間内に低電力にて効率よく処理することが可能となる。
【０２３５】
すなわち、コンパイラ４０により、コンパイル時に実行順序を確定できるタスクは、事前にタスクの割り付けを決定するスタティックスケジューリングを適用する。一方、条件分岐など不確定要素を含むタスクについては、実行時に割り付けを決定するダイナミックスケジューリングを適用することで、スケジューリングに要する処理のオーバーヘッドを抑制することができる。
【０２３６】
また、上記各実施形態では、汎用プロセッサグループと、アクセラレータを種別毎に別グループとして分けておき、タスクの割り付け時にタスク毎に指定されたアクセラレータグループの特定用途ＰＥを用いるか、汎用プロセッサを用いるかの選択処理を、コンパイル時に求めたコスト情報（ＣＰ長）とアクセラレータの稼動状況で決定することにより、アクセラレータの種類や数が増えても、スケジューリングのコストは増加することがない。したがって、ヘテロジニアス・マルチプロセッサシステムにおいて汎用ＰＥと特定用途ＰＥの数が増大した場合でも、スケジューリングのオーバーヘッドが増大するのを防止できる。
【０２３７】
つまり、スタティックスケジューリングの場合にはコンパイル時に、スケジューラの中で仮想レディキューを使いながら、汎用プロセッサグループとアクセラレータグループに上記最早終了推定時刻の基準でタスクを各プロセッサグループに割り当てる。そして、タスクの割り当てに従って、各プロセッサグループ毎の命令セットを有するタスクコードを各プロセッサに割り当てられた順に並べ、目的コードとしての実行コードを出力する。
【０２３８】
ダイナミックスケジューリングでは、タスクコードは当該タスクを実行する可能性があるプロセッサにロードされ、各タスク実行終了毎にコンパイラによって埋め込まれたダイナミックスケジューリングコード（スケジューラＳＣ）を実行し、どのタスクが実行可能（レディ：最早実行可能条件を満たしているか）であるかを検出し、レディタスクをレディキューへ投入する。そして、スケジューラＳＣは、レディキュー上の最も優先順位の高いタスク（優先度ＧＣＰ長の最も大きいもの）を実行するタスクとして選択する。そして、選択したタスクを実行可能なプロセッサグループへ割り当てる場合の最早推定終了時刻を各グループ毎に演算する。なお、この最早終了時刻の演算は、各プロセッサグループの種類毎、あるいは同種類でも複数のプロセッサがある場合には、各プロセッサ毎にそれぞれ実行する。
【０２３９】
そしてスケジューラＳＣは、選択したタスクを最も早く実行を終了できそうなＰＥ（最早推定終了時刻をもつＰＥ）に割り当てる。つまり、各プロセッサグループ毎の実行キューに投入する。
【０２４０】
以上の処理によって、マクロタスクグラフ内のタスクの構造に応じて、スタティックスケジューリングとダイナミックスケジューリングが自動的に選択され、タスク毎の実行コード（タスクコード）とスケジューリングコードが生成される。
【０２４１】
また、上記第１実施形態では、分散ダイナミックスケジューリングを用いることで、スケジューリングのために汎用ＰＥを占有しないので、汎用プロセッサグループＰＧのリソースを無駄なく利用でき、処理速度の向上を図ることができる。
【０２４２】
また、上記各実施形態では、コンパイラ４０によりタスクの実行サイクル時間を事前に見積もり、タスク自体の実行時間に加え、タスク全体のクリティカルパス長より、タスクの処理優先度ＧＣＰを求めておき、スケジューリングの際に優先度ＧＣＰの順位で、実際のタスクの割り当てを行う。これにより、処理コストと優先度ＧＣＰでタスクの実行順序を決定するので、ヘテロジニアス・マルチプロセッサシステムのリソースを有効に利用して並列処理の速度を向上できる。さらに、コンパイル時に事前に処理コストと優先度ＧＣＰを求めておくことにより、スケジューリングの実行時のオーバーヘッドを抑制できる。
【０２４３】
なお、上記各実施形態においては、一つのチップに複数のＰＥ１０〜１７を備えたマルチプロセッサシステムに本発明を適用した例を示したが、図１に示したヘテロジニアス・マルチプロセッサシステム１を複数備えた並列計算機に適用することも可能であり、上記と同様の作用効果を得ることができる。
【０２４４】
さらに、上記各実施形態では、レディキューを汎用プロセッサグループ毎に設定したので、各汎用プロセッサグループで実行される複数のスケジューラＳＣは、各グループ単位でスケジューリングを効率よく行うことができる。
【０２４５】
また、上記第１、第２の実施形態では、実行キューをプロセッサグループ毎に設定したので、各グループのＰＥへのタスクの割り当てを簡易にすることができ、スケジューラＳＣの負荷を低減でき、スケジューリングに伴うオーバーヘッドを抑制できる。
【０２４６】
＜補足＞
２０．第１の命令セットを実行する第１のプロセッサと、
前記第１のプロセッサとは異なる第２の命令セットを実行する第２のプロセッサと、
前記第１のプロセッサを複数含み、かつ、少なくとも一つの前記第２のプロセッサを含むヘテロジニアス・マルチプロセッサシステムにタスクを割り当てる制御方法であって、
予め設定した複数のタスクの依存関係に基づいて実行可能なタスクを抽出する処理と、
前記依存関係から並列性を抽出する処理と、
前記依存関係が並列性を有するときには、前記複数の第１のプロセッサを前記並列性に応じた数の汎用プロセッサグループに割り当てる処理と、
前記並列性に係わらず前記第２のプロセッサをアクセラレータグループに割り当てる処理と、
前記汎用プロセッサグループ毎にレディキューを設定する処理と、
前記レディキューに前記抽出したタスクを投入する処理と、
前記レディキューのタスクを所定の条件に基づいて前記第１のプロセッサまたは第２のプロセッサに割り当てる処理と、
を含むことを特徴とするヘテロジニアス・マルチプロセッサシステムの制御方法。
【０２４７】
２１．第１の命令セットを実行する第１のプロセッサと、
前記第１のプロセッサとは異なる第２の命令セットを実行する第２のプロセッサと、
前記第１のプロセッサを複数含み、かつ、少なくとも一つの前記第２のプロセッサを含むヘテロジニアス・マルチプロセッサシステムにタスクを割り当てる制御方法であって、
予め設定した複数のタスクの依存関係に基づいて実行可能なタスクを抽出する処理と、
前記依存関係から並列性を抽出する処理と、
前記依存関係が並列性を有するときには、前記複数の第１のプロセッサを前記並列性に応じた数の汎用プロセッサグループに割り当てる処理と、
前記並列性に係わらず前記第２のプロセッサをアクセラレータグループに割り当てる処理と、
前記汎用プロセッサグループのいずれか一つにレディキューを設定する処理と、
前記レディキューに前記抽出したタスクを投入する処理と、
前記レディキューのタスクを所定の条件に基づいて前記第１のプロセッサまたは第２のプロセッサに割り当てる処理と、
を含むことを特徴とするヘテロジニアス・マルチプロセッサシステムの制御方法。
【０２４８】
２２．前記２０．または２１．において
前記プロセッサに割り当てる処理は、
前記レディキューのタスクを、予め設定した優先度に基づいてソートする処理と、
前記ソートしたレディキューのタスクのうち最も優先度が高いタスクを選択する処理と、
前記選択したタスクを前記第２のプロセッサで実行したときの実行コストと、前記タスクを前記第１のプロセッサで実行したときの実行コストとを比較する処理と、
前記比較の結果、前記実行コストが小さい方の汎用プロセッサグループまたはアクセラレータグループの一方に当該タスクを割り当てる処理と、
を含むことを特徴とするヘテロジニアス・マルチプロセッサシステムの制御方法。
【０２４９】
２３．第１の命令セットを実行する複数の第１のプロセッサと、
前記第１のプロセッサとは異なる第２の命令セットを実行する第２のプロセッサと、を備えたヘテロジニアス・マルチプロセッサシステムであって、
前記プロセッサシステムは、
前記第１及び第２のプロセッサで共有可能な第１の共有メモリを備え、
前記第１及び第２のプロセッサユニットは、
他の第１または第２のプロセッサと共有可能な第２の共有メモリを備え、
前記第１のプロセッサを複数の汎用プロセッサグループに分割するスケジューラと、
前記第１の共有メモリまたは第２の共有メモリのいずれか一方に前記汎用プロセッサグループ毎に設定したレディキューと、
を備えたことを特徴とするヘテロジニアス・マルチプロセッサシステム。
【０２５０】
２４．前記２３において、前記スケジューラは、実行するタスクの並列性に応じた数の汎用プロセッサグループを設定することを特徴とするヘテロジニアス・マルチプロセッサシステム。
【産業上の利用可能性】
【０２５１】
以上のように、本発明は、異種のＰＥを集積するヘテロジニアス・マルチプロセッサシステムにおいて、異種のＰＥを効率よく動作させるプログラムの分割配置および制御コードを生成するコンパイラにより、当該プロセッサシステムの性能を最大限活用しつつ、低電力にて効率よく処理することが可能となる。また、さらにはソフトウェア開発者がプロセッサの構成を意識することなく、短時間で効率良いプログラム作成が可能となる。その結果、高い演算性能を持ちかつ低電力に処理することが強く望まれる、カーナビゲーションシステムや携帯電話、情報家電向けのＬＳＩに本発明を適用することができ、高品質の動画像や音声処理、また画像認識や音声認識といった機能を実現することが可能となる。また、自動車における情報系、制御系システム向けＬＳＩに対しても適用することができ、自動運転や安全運転システム等を実現することが可能となる。またさらには、将来非常に高い演算性能を有しつつ低電力化が必須となる、スーパーコンピュータへの適用も可能である。
【図面の簡単な説明】
【０２５２】
【図１】本発明の一実施形態を示すマルチプロセッサシステムのブロック図。
【図２】コンパイラが生成したタスク間の依存関係を示すマクロタスクグラフ。
【図３】プロセッサのグループ分けの一例を示すブロック図。
【図４】コンパイラが実行する処理の一例を示すフローチャート。
【図５】優先度ＧＣＰを演算する際のマクロタスクグラフ。
【図６】図４のＳ８で行われるスタティックスケジューリングの概要を示すフローチャート。
【図７】図４のＳ８で行われるスタティックスケジューリングの詳細を示すフローチャート。
【図８】プロセッサシステムのキューの状態を示す説明図。
【図９】図４のＳ９で行われるダイナミックスケジューリングの概要を示すフローチャート。
【図１０】図４のＳ９で行われるダイナミックスケジューリングの詳細を示すフローチャート。
【図１１】入力プログラムを解析したコンパイラが生成したタスク間の依存関係を示すマクロタスクグラフ。
【図１２】図１１の入力プログラムをコンパイルしたスケジューリングコードを実行した結果を示し、各プロセッサが実行するタスクとキューの関係を示すタイムチャート。
【図１３】第２の実施形態を示し、他の入力プログラムを解析したコンパイラが生成したタスク間の依存関係を示すマクロタスクグラフ。
【図１４】図１３の入力プログラムをコンパイルしたスケジューリングコードを実行した結果を示し、各プロセッサが実行するタスクとキューの関係を示すタイムチャート。
【図１５】第３の実施形態を示し、プロセッサシステムのキューの状態を示す説明図。
【図１６】第１の実施形態を示し、図１１の入力プログラムをコンパイルしたスケジューリングコードを実行した結果を示し、プロセッサグループとタスクの関係を示すタイムチャート。
【図１７】第２の実施形態を示し、図１３の入力プログラムをコンパイルしたスケジューリングコードを実行した結果を示し、プロセッサグループとタスクの関係を示すタイムチャート。
【図１８】第４の実施形態を示し、異機種の計算機群からなるＧＲＩＤコンピューティングのブロック図。
【図１９】マルチプロセッサシステムの他の例を示すブロック図。
【符号の説明】
【０２５３】
１０〜１３  ＣＰＵ
１４、１５  ＤＲＰ
１６、１７  ＤＳＰ
１８  集中共有メモリ（ＣＳＭ）
１９  ローカルバス
２１  ＣＰＵコア
２２  ローカルメモリ（ＬＭ）
２３  分散共有メモリ（ＤＳＭ）
２４  データ転送ユニット（ＤＴＵ）
２５  システム制御レジスタ（ＦＶＲ）
３１  ＤＲＰコア
４１  ＤＳＰコア
【図１】
2007328415.tif 000003
【図２】
2007328415.tif 000004
【図３】
2007328415.tif 000005
【図４】
2007328415.tif 000006
【図５】
2007328415.tif 000007
【図６】
2007328415.tif 000008
【図７】
2007328415.tif 000009
【図８】
2007328415.tif 000010
【図９】
2007328415.tif 000011
【図１０】
2007328415.tif 000012
【図１１】
2007328415.tif 000013
【図１２】
2007328415.tif 000014
【図１３】
2007328415.tif 000015
【図１４】
2007328415.tif 000016
【図１５】
2007328415.tif 000017
【図１６】
2007328415.tif 000018
【図１７】
2007328415.tif 000019
【図１８】
2007328415.tif 000020
【図１９】
2007328415.tif 000021