(57)【要約】【課題】命令セットの異なる異種プロセッサを有するマルチプロセッサシステムにけるプログラムの実行効率を向上させるタスク割り付け方法を提供する。【解決手段】命令セットの異なる複数の異種プロセッサを含むマルチプロセッサシステムによって実行されるプログラムを構成する、該命令セットのいずれかでそれぞれ記述された複数のタスクをプロセッサに割り付ける際に、各タスクのうちの少なくとも一つの対象タスクを記述している命令セットを有する第１プロセッサに対して対象タスクを割り付け（Ｓ１１）、対象タスクの割り付け先を第１プロセッサと異なる第２プロセッサに変更することによって、プログラムの実行効率が向上するか否かを判定し（Ｓ１２）、実行効率が向上する対象タスクについては、第２プロセッサが有する命令セットによって記述されたプログラムモジュールを取得して割り付け先を第２プロセッサに変更する（Ｓ１３）。【選択図】    図１３
2004171234.tif 000002
【特許請求の範囲】
【請求項１】
異なる命令セットをそれぞれ有する少なくとも第１及び第２のプロセッサを含むマルチプロセッサシステムによって実行されるプログラムを構成する、前記命令セットのいずれかを用いて記述された複数のタスクを前記プロセッサに割り付けるタスク割り付け方法において、
前記タスクの中で、第１の命令セットで記述されているタスクを前記第１プロセッサに対して割り付ける第１のステップと、
前記第１プロセッサに割り付けられたタスクの少なくとも一つを対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することにより前記プログラムの実行効率が向上するか否かを判定する第２のステップと、
前記実行効率が向上する場合に前記対象タスクの割り付け先を前記第２プロセッサに変更する第３のステップと
を具備するマルチプロセッサシステムにおけるタスク割り付け方法。
【請求項２】
異なる命令セットをそれぞれ有する少なくとも第１及び第２のプロセッサを含むマルチプロセッサシステムによって実行されるプログラムを構成する、前記命令セットのいずれかを用いて記述されたプログラムモジュールとして与えられる複数のタスクを前記プロセッサに割り付けるタスク割り付け方法において、
前記タスクの中で、第１の命令セットで記述されているプログラムモジュールとして与えられるタスクを前記第１プロセッサに対して割り付ける第１のステップと、
前記第１プロセッサに割り付けられたタスクの少なくとも一つを、前記第１プロセッサが有する命令セットによって記述された第１プログラムモジュールとして与えられる対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することにより前記プログラムの実行効率が向上するか否かを判定する第２のステップと、
前記実行効率が向上する場合に前記対象タスクの割り付け先を前記第２プロセッサに変更する第３のステップと
を具備するマルチプロセッサシステムにおけるタスク割り付け方法。
【請求項３】
前記複数のタスクを前記対象タスクとして前記第１のステップの処理を行った後に前記第２及び第３のステップの処理を行う請求項１または２記載のマルチプロセッサシステムプロセッサにおけるタスク割り付け方法。
【請求項４】
前記複数のタスクから選択した一つのタスクについて前記第１、第２及び第３のステップの処理を行い、その後に前記プログラムの実行を開始する請求項１または２記載のマルチプロセッサシステムプロセッサにおけるタスク割り付け方法。
【請求項５】
前記第１のステップの処理が完了した後に前記プログラムの実行を開始し、該プログラムの実行途中で前記第２乃至第４のステップの処理を行う請求項１または２記載のマルチプロセッサシステムにおけるタスク割り付け方法。
【請求項６】
異なる命令セットをそれぞれ有する少なくとも第１及び第２プロセッサを含み、前記命令セットのいずれかを用いて記述された複数のタスクにより構成されるプログラムを実行するマルチプロセッサシステムにおいて、
前記タスクの中で、第１の命令セットで記述されているタスクを前記第１プロセッサに対して割り付ける仮割り付け部と、
前記第１プロセッサに割り付けられたタスクの少なくとも一つを対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することにより前記プログラムの実行効率が向上するか否かを判定する判定部と、
前記実行効率が向上する場合に前記対象タスクの割り付け先を前記第２プロセッサに変更する割り付け先変更部と
を具備するマルチプロセッサシステム。
【請求項７】
異なる命令セットをそれぞれ有する第１及び第２プロセッサを含み、前記命令セットのいずれかを用いて記述されたプログラムモジュールとして与えられる複数のタスクにより構成されるプログラムを実行するマルチプロセッサシステムにおいて、
各タスクのプログラムモジュールをそれぞれ記述している命令セットを有する第１プロセッサに対して、該タスクをそれぞれ割り付ける仮割り付け部と、
前記各タスクの少なくとも一つを前記第１プロセッサが有する命令セットによって記述された第１プログラムモジュールとして与えられる対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することにより前記プログラムの実行効率が向上するか否かを判定する判定部と、前記実行効率が向上する場合に前記第２プロセッサが有する命令セットによって記述された第２プログラムモジュールを取得することにより、前記対象タスクの割り付け先を前記第２プロセッサに変更する割り付け先変更部と
を具備するマルチプロセッサシステム。
【請求項８】
前記判定部は、前記各タスクのうち注目タスクの前後のタスクの割り付けられている前記第１プロセッサが該注目タスクの割り付けられている前記第１プロセッサとは異なる該注目タスクを前記対象タスクとして選定する請求項６または７記載のマルチプロセッサシステム。
【請求項９】
前記判定部は、前記各タスクのうち注目タスクの直後のタスクに割り付けられている前記第１プロセッサが該注目タスクに割り付けられている前記第１プロセッサと同一の場合に、該注目タスクと該直後のタスクをグループ化し、該グループを一つの前記対象タスクとして取り扱う請求項６または７記載のマルチプロセッサシステム。
【請求項１０】
前記判定部は、前記対象タスクを前記第１プロセッサに割り付けた場合の前記プログラムの実行時間と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合の前記プログラムの実行時間とを予測し、第２プロセッサへ割り付け先を変更した方が該予測した実行時間が短縮するか否かにより前記実行効率が向上するか否かを判定する請求項６または７記載のマルチプロセッサシステム。
【請求項１１】
前記判定部は、前記対象タスクを前記第１プロセッサに割り付けた場合の単位時間当たりの処理可能データ量と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合の前記タスクの単位時間当たりの処理可能データ量とを予測し、第２プロセッサへ割り付け先を変更した方が該予測した処理可能データ量が増加するか否かにより前記実行効率が向上するか否かを判定する請求項６または７記載のマルチプロセッサシステム。
【請求項１２】
前記判定部は、前記対象タスクを前記第１プロセッサに割り付けた場合の単位時間当たりの処理可能データ量と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合の前記タスクの単位時間当たりの処理可能データ量とを予測し、第２プロセッサへ割り付け先を変更した方が該予測した処理可能データ量が予め定められた閾値を越えて増加しているか否かにより前記実行効率が向上するか否かを判定する請求項６または７記載のマルチプロセッサシステム。
【請求項１３】
前記判定部は、前記対象タスクの割り付け先を前記第２プロセッサに変更することによる該第２プロセッサの負荷を予測し、該負荷が過負荷にならないか否かにより前記実行効率が向上するか否かを判定する請求項６または７記載のマルチプロセッサシステム。
【請求項１４】
前記判定部は、前記対象タスクを第１プロセッサに割り付けた場合のプロセッサ間通信データ量と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合のプロセッサ間通信データ量とを予測し、第２プロセッサへ割り付け先を変更した方が該予測したプロセッサ間通信データ量が減少するか否かにより前記実行効率が向上するか否かを判定する請求項６または７記載のマルチプロセッサシステム。
【請求項１５】
前記判定部は、前記対象タスクを第１プロセッサに割り付けた場合のプログラム全体の単位時間当たりのプロセッサ間通信データ量と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合のプログラム全体の単位時間当たりのプロセッサ間通信データ量とを予測し、第２プロセッサへ割り付け先を変更した方が該予測したプログラム全体の単位時間当たりのプロセッサ間通信データ量が減少するか否かにより前記実行効率が向上するか否かを判定する請求項６または７記載のマルチプロセッサシステム。
【請求項１６】
前記判定部は、下記（ａ）（ｂ）（ｃ）及び（ｄ）の判定結果を少なくとも２つ以上組み合わせて最終的に前記実行効率が向上するか否かを判定する請求項６記載のマルチプロセッサシステム。
（ａ）前記対象タスクを前記第１プロセッサに割り付けた場合の前記プログラムの実行時間と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合の前記プログラムの実行時間とを予測し、第２プロセッサへ割り付け先を変更した方が該予測した実行時間が短縮するか否かにより前記実行効率が向上するか否かを判定する；
（ｂ）前記対象タスクを前記第１プロセッサに割り付けた場合の単位時間当たりの処理可能データ量と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合の前記タスクの単位時間当たりの処理可能データ量とを予測し、第２プロセッサへ割り付け先を変更した方が該予測した処理可能データ量が増加するか否かにより前記実行効率が向上するか否かを判定する；
（ｃ）前記対象タスクを前記第１プロセッサに割り付けた場合の単位時間当たりの処理可能データ量と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合の前記タスクの単位時間当たりの処理可能データ量とを予測し、第２プロセッサへ割り付け先を変更した方が該予測した処理可能データ量が予め定められた閾値を越えて増加しているか否かにより前記実行効率が向上するか否かを判定する；
（ｄ）前記対象タスクの割り付け先を前記第２プロセッサに変更することによる該第２プロセッサの負荷を予測し、該負荷が過負荷にならないか否かにより前記実行効率が向上するか否かを判定する。
（ｅ）前記対象タスクを第１プロセッサに割り付けた場合のプロセッサ間通信データ量と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合のプロセッサ間通信データ量とを予測し、第２プロセッサへ割り付け先を変更した方が該予測したプロセッサ間通信データ量が減少するか否かにより前記実行効率が向上するか否かを判定する。
（ｆ）前記対象タスクを第１プロセッサに割り付けた場合のプログラム全体の単位時間当たりのプロセッサ間通信データ量と前記対象タスクの割り付け先を前記第２プロセッサに変更した場合のプログラム全体の単位時間当たりのプロセッサ間通信データ量とを予測し、第２プロセッサへ割り付け先を変更した方が該予測したプログラム全体の単位時間当たりのプロセッサ間通信データ量が減少するか否かにより前記実行効率が向上するか否かを判定する。
【請求項１７】
前記割り付け先変更部は、前記第１プログラムモジュール中の第１命令を、前記第２プログラムモジュールにおける、該第１命令と同じ処理を行う第２命令に置換することによって前記第２プログラムモジュールを取得する請求項７記載のマルチプロセッサシステム。
【請求項１８】
前記割り付け先変更部は、前記第１プログラムモジュールのソースコードからコンパイラを用いて前記第２プログラムモジュールを取得する請求項７記載のマルチプロセッサシステム。
【請求項１９】
前記割り付け先変更部は、前記第２プログラムモジュールをファイルシステム及びネットワークの少なくとも一方から取得する請求項７記載のマルチプロセッサシステム。
【請求項２０】
前記複数のタスクの少なくとも一つは、前記複数のプロセッサの二つ以上がそれぞれ有する命令セットによって記述された複数のプログラムモジュールを含むプログラムモジュール複合体であり、
前記仮割り付け部は、前記複数のプログラムモジュール中の第１プログラムモジュールを記述している命令セットを有する一つのプロセッサを前記第１プロセッサとして、該第１プロセッサに対して前記対象タスクを割り付ける請求項７記載のマルチプロセッサシステム。
【請求項２１】
前記複数のタスクの少なくとも一つは、前記複数のプロセッサの二つ以上がそれぞれ有する命令セットによって記述された複数のプログラムモジュールを含むプログラムモジュール複合体であり、
前記仮割り付け部は、前記複数のプログラムモジュール中の一つのプログラムモジュールを記述している命令セットを有する一つのプロセッサを前記第１プロセッサとして前記割り付けを行い、
前記割り付け先変更部は、前記第２プロセッサが前記複数のプログラムモジュール中の他の一つのプログラムモジュールを記述している命令セットを有する他の一つのプロセッサでない場合に、前記複数のプログラムモジュール中の任意の一つのプログラムモジュール中の第１命令を前記第２プログラムモジュールにおける、該第１命令と同じ処理を行う第２命令に置換することによって前記第２プログラムモジュールを取得する請求項７記載のマルチプロセッサシステム。
【請求項２２】
前記複数のタスクの少なくとも一つは、前記複数のプロセッサの二つ以上がそれぞれ有する命令セットによって記述された複数のプログラムモジュールを含むプログラムモジュール複合体であり、
前記仮割り付け部は、前記複数のプログラムモジュール中の一つのプログラムモジュールを記述している命令セットを有する一つのプロセッサを前記第１プロセッサとして前記割り付けを行い、
前記割り付け先変更部は、前記第２プロセッサが前記複数のプログラムモジュール中の他の一つのプログラムモジュールを記述している命令セットを有する他の一つのプロセッサでない場合に、前記複数のプログラムモジュール中の任意の一つのプログラムモジュールのソースコードからコンパイラを用いて前記第２プログラムモジュールを取得する請求項７記載のマルチプロセッサシステム。
【請求項２３】
前記割り付け先変更部は、前記第２プロセッサが前記複数のプログラムモジュール中の他の一つのプログラムモジュールを記述している命令セットを有する他の一つのプロセッサでない場合に、前記プログラムモジュールをファイルシステムあるいはネットワークから取得する請求項７記載のマルチプロセッサシステム。
【請求項２４】
異なる命令セットをそれぞれ有する少なくとも第１及び第２のプロセッサを含むマルチプロセッサシステムによって実行されるプログラムを構成する、前記命令セットのいずれかを用いて記述された複数のタスクを前記プロセッサに割り付ける処理をコンピュータに実行させるタスク割り付けプログラムであって、
前記タスクの中で、第１の命令セットで記述されているタスクを前記第１プロセッサに対して割り付ける第１の処理と、
前記第１プロセッサに割り付けられたタスクの少なくとも一つを対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することにより前記プログラムの実行効率が向上するか否かを判定する第２の処理と、
前記実行効率が向上する場合に前記対象タスクの割り付け先を前記第２プロセッサに変更する第３の処理と
を前記コンピュータに実行させるタスク割り付けプログラム。
【請求項２５】
異なる命令セットをそれぞれ有する少なくとも第１及び第２のプロセッサを含むマルチプロセッサシステムによって実行されるプログラムを構成する、前記命令セットのいずれかを用いて記述されたプログラムモジュールとして与えられる複数のタスクを前記プロセッサに割り付ける処理をコンピュータに実行させるタスク割り付けプログラムであって、
前記タスクの中で、第１の命令セットで記述されているプログラムモジュールとして与えられるタスクを前記第１プロセッサに対して割り付ける第１の処理と、
前記第１プロセッサに割り付けられたタスクの少なくとも一つを、前記第１プロセッサが有する命令セットによって記述された第１プログラムモジュールとして与えられる対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することにより前記プログラムの実行効率が向上するか否かを判定する第２の処理と、
前記実行効率が向上する場合に前記対象タスクの割り付け先を前記第２プロセッサに変更する第３の処理と
を前記コンピュータに実行させるタスク割り付けプログラム。
【請求項２６】
前記タスク割り付けプログラムを実行させる前記コンピュータは、前記複数のプロセッサ及び前記複数のプロセッサ以外のプロセッサのうちの少なくとも一つである請求項２４または２５記載のタスク割り付けプログラム。
【請求項２７】
前記タスク割り付けプログラムは、（ａ）前記複数のプロセッサの少なくとも一つのオペレーティングシステム、（ｂ）前記複数のプロセッサ以外の少なくとも一つのプロセッサのオペレーティングシステム、（ｃ）前記複数のプロセッサの少なくとも一つのオペレーティングシステムと前記複数のプロセッサ以外の少なくとも一つのプロセッサのオペレーティングシステム及び（ｄ）前記マルチプロセッサシステムが実行するプログラムの少なくともいずれかの一部である請求項２４または２５記載のタスク割り付けプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、命令セットの異なる異種プロセッサを有するマルチプロセッサシステムにおけるタスク割り付け方法、タスク割り付けプログラム及びマルチプロセッサシステムに関する。
【０００２】
【従来の技術】
マルチプロセッサシステム、すなわちマルチプロセッサ計算機は、例えば「コンピュータの構成と設計  ハードウェアとソフトウェアのインターフェース  第２版（下）」、Ｄａｖｉｄ  Ａ．Ｐａｔｔｅｒｓｏｎ，  Ｊｏｈｎ  Ｌ．Ｈｅｎｎｅｓｓｙ  著、成田光彰訳、日経ＢＰ社ＩＳＢＮ：４−８２２２−８０５７−８、第９章（非特許文献１）に記載されているように、複数のプロセッサ（ＣＰＵ）によって一つのプログラムを実行する計算機である。
【０００３】
各プロセッサは、バスあるいはクロスバスイッチのようなプロセッサ間結合装置によって結合される。プロセッサ間結合装置には、共有メモリ及び入出力制御装置が接続される。各プロセッサは、キャッシュメモリを持つことも多い。共有メモリを持たず、各々のプロセッサがローカルメモリを持つマルチプロセッサシステムもある。
【０００４】
マルチプロセッサシステム上で実行されるプログラムの開発手法として、タスクとタスク間の依存関係でプログラムを記述する方式が広く用いられている。タスクとは、ひとまとまりの処理を行うプログラムの実行単位である。タスク間の依存関係とは、タスク間でのデータの受渡しあるいは制御の受渡しのいずれか、あるいは両方をいう。各タスクに対して、実際にプロセッサ上でそのタスクを実行するのに必要なプログラムを格納しているプログラムモジュールが存在する。このようなプログラム開発手法は、タスクのプログラムモジュールを単位としてプログラムを再利用できるという特徴を持つ。これによりプログラムの開発効率が向上し、また、過去に開発されてきた数多くの優れたプログラムモジュールの資産を利用することができるという利点がある。
【０００５】
タスクとタスク間の依存関係によって記述されたプログラムをマルチプロセッサシステム上で実行する際には、各タスクをどのプロセッサで実行すべきかを判断して各タスクを各プロセッサに割り付ける処理が必要がある。このタスク割り付け処理は、実行効率が高くなるように配慮して行われる。ここでいう「実行効率が高い」とは、例えば、プログラム全体の実行時間が短いこと、単位時間当たりの処理データ量が大きいこと、各プロセッサの負荷が小さいこと、プロセッサ間通信のデータ量が小さいこと（あるいはプロセッサ間通信の回数が少ないこと）である。
【０００６】
プロセッサ（ＣＰＵ）は、その種類に応じて固有の命令セットを有する。命令セットとは、プロセッサが理解できる命令の集まりである。同一の命令セットを有する同種のプロセッサからなる通常のマルチプロセッサシステムとは別に、異なる命令セットを有する異種のプロセッサからなるマルチプロセッサシステム（以下、ヘテロマルチプロセッサシステムという）も存在する。ヘテロマルチプロセッサシステムは、異種プロセッサ用の複数の命令セットで記述されたプログラムモジュールをタスクとして組合せたプログラムを実行する。
【０００７】
【非特許文献１】
「コンピュータの構成と設計  ハードウェアとソフトウェアのインターフェース  第２版（下）」、Ｄａｖｉｄ  Ａ．Ｐａｔｔｅｒｓｏｎ，  Ｊｏｈｎ  Ｌ．Ｈｅｎｎｅｓｓｙ  著、成田光彰訳、日経ＢＰ社ＩＳＢＮ：４−８２２２−８０５７−８、第９章
【０００８】
【発明が解決しようとする課題】
ヘテロマルチプロセッサシステムにおいても、同種のプロセッサからなる通常のマルチプロセッサシステムと同様に、プロセッサに対する各タスクの割り付けをプログラムの実行効率がより良くなるように配慮して行うことが当然に要求される。しかし、通常のマルチプロセッサシステムで用いられているタスク割り付け方法をヘテロマルチプロセッサシステムに単純に適用しても、十分なプログラム実行効率を得ることはできない。
【０００９】
通常のマルチプロセッサシステムでは、各タスクを当該タスクのプログラムモジュールの記述に用いられている命令セットと同じ命令セットを有するプロセッサに割り付けている。このような通常のマルチプロセッサシステムにおけるタスク割り付けの手法を判断基準として、ヘテロマルチプロセッサシステムにおけるタスク割り付けを行うと、タスク間の依存関係、言い換えればタスクの実行順序の関係によって、プロセッサ間通信が頻発する。このようなプロセッサ間通信のオーバヘッドにより、ヘテロマルチプロセッサシステムではプログラムの実行効率が低下してしまうという大きな問題がある。
【００１０】
本発明の目的は、命令セットの異なる異種プロセッサを有するマルチプロセッサシステムにけるプログラムの実行効率を向上させるタスク割り付け方法、タスク割り付けプログラム及びマルチプロセッサシステムを提供することにある。
【００１１】
【課題を解決するための手段】
上記の課題を解決するため、本発明ではプログラムを構成する各タスクをその記述に用いられている命令セットと同じ命令セットのプロセッサに仮割り付けした後に、割り付け先プロセッサを変更することによりプログラムの実行効率が向上するか否かを判定し、その判定結果に従って必要な場合に対象タスクの割り付け先を変更して本割り付けを行う。
【００１２】
すなわち、本発明の一つの態様では、異なる命令セットをそれぞれ有する少なくとも第１及び第２のプロセッサを含むマルチプロセッサシステムによって実行されるプログラムを構成する、前記命令セットのいずれかを用いて記述された複数のタスクを前記プロセッサに割り付ける際、まず前記タスクの中で第１の命令セットで記述されているタスクを第１プロセッサに対して割り付ける。次に、第１プロセッサに割り付けられたタスクの少なくとも一つを対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することによりプログラムの実行効率が向上するか否かを判定する。この判定結果に従って、実行効率が向上する場合に前記対象タスクの割り付け先を第２プロセッサに変更する。
【００１３】
より具体的な態様では、マルチプロセッサシステムによって実行されるプログラムを構成する各タスクは、各プロセッサが有する異なる命令セットのいずれかでそれぞれ記述されたプログラムモジュールとして与えられる。そして、対象タスクの割り付け先を第１プロセッサから第２プロセッサに変更することによりプログラムの実行効率が向上する場合には、第２プロセッサが有する命令セットによって記述されたプログラムモジュールを取得することにより、対象タスクの割り付け先を第２プロセッサに変更する。
【００１４】
本発明によると、異なる命令セットをそれぞれ有する少なくとも第１及び第２のプロセッサを含むマルチプロセッサシステムによって実行されるプログラムを構成する、前記命令セットのいずれかを用いて記述された複数のタスクを前記プロセッサに割り付ける処理をコンピュータに実行させるタスク割り付けプログラムであって、前記タスクの中で、第１の命令セットで記述されているタスクを前記第１プロセッサに対して割り付ける第１の処理と、前記第１プロセッサに割り付けられたタスクの少なくとも一つを対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することにより前記プログラムの実行効率が向上するか否かを判定する第２の処理と、前記実行効率が向上する場合に前記対象タスクの割り付け先を前記第２プロセッサに変更する第３の処理とを前記コンピュータに実行させるタスク割り付けプログラムが提供される。
【００１５】
さらに、本発明によると異なる命令セットをそれぞれ有する少なくとも第１及び第２のプロセッサを含むマルチプロセッサシステムによって実行されるプログラムを構成する、前記命令セットのいずれかを用いて記述されたプログラムモジュールとして与えられる複数のタスクを前記プロセッサに割り付ける処理をコンピュータに実行させるタスク割り付けプログラムであって、
前記タスクの中で、第１の命令セットで記述されているプログラムモジュールとして与えられるタスクを前記第１プロセッサに対して割り付ける第１の処理と、前記第１プロセッサに割り付けられたタスクの少なくとも一つを、前記第１プロセッサが有する命令セットによって記述された第１プログラムモジュールとして与えられる対象タスクとして、該対象タスクの割り付け先を第２の命令セットを有する第２プロセッサに変更することにより前記プログラムの実行効率が向上するか否かを判定する第２の処理と、前記実行効率が向上する場合に前記対象タスクの割り付け先を前記第２プロセッサに変更する第３の処理とを前記コンピュータに実行させるタスク割り付けプログラムが提供される。
【００１６】
ここで、前記タスク割り付けプログラムを実行させる前記コンピュータは、例えば前記複数のプロセッサ及び前記複数のプロセッサ以外のプロセッサのうちの少なくとも一つである。
【００１７】
前記タスク割り付けプログラムは、具体的には例えば（ａ）前記複数のプロセッサの少なくとも一つのオペレーティングシステム、（ｂ）前記複数のプロセッサ以外の少なくとも一つのプロセッサのオペレーティングシステム、（ｃ）前記複数のプロセッサの少なくとも一つのオペレーティングシステムと前記複数のプロセッサ以外の少なくとも一つのプロセッサのオペレーティングシステム及び（ｄ）前記マルチプロセッサシステムが実行するプログラムの少なくともいずれかの一部として構成される。
【００１８】
このように本発明によると、命令セットが異なる複数種類のプロセッサから構成されるヘテロマルチプロセッサシステムにおいて、記述に用いられている命令セットが異なる複数のタスク群を実行する際に、命令セットが異なるプロセッサヘ割り付けた方がよいタスクの選定と割り付けの変更が実現でき、これによりシステム全体のプログラム実行効率が向上する。
【００１９】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
（マルチプロセッサシステムの全体構成）
図１に、本発明の一実施形態に係るマルチプロセッサシステムの基本的な構成例を示す。このシステムは、いわゆるヘテロマルチプロセッサシステムであり、命令セットＡ，Ｂ及びＣをそれぞれ有する複数のプロセッサ１〜３と、共有メモリ４及び入出力制御装置５がバスやクロスバスイッチ等のプロセッサ間結合装置７によって接続されている。入出力制御装置５には大容量記憶装置、例えばディスク装置６が接続されている。プロセッサ間結合装置７には、さらに図１では概念的に示したタスク割り付けシステム８が結合される。
【００２０】
図１中には示されていないが、プロセッサ１〜３はキャッシュやローカルメモリを持っていてもよい。マルチプロセッサシステムは、共用メモリを持たなくともよい。図１では、３個のプロセッサ１〜３が示されているが、マルチプロセッサシステムは２個あるいは４個以上のプロセッサを含んでいてもよい。ヘテロマルチプロセッサシステムに含まれる複数のプロセッサは、全て異なる命令セットを使用している必要はなく、２つまたはそれ以上のプロセッサが同一の命令セットを有する構成でもよい。要するに、ヘテロマルチプロセッサシステムは、異なる命令セットを有する少なくとも２つの異種プロセッサを含んでいればよい。
【００２１】
マルチプロセッサシステムが実行するプログラムを構成する各々のタスクに対して、実際にプロセッサ１〜３上でタスクを実行するために必要なプログラムを格納しているプログラムモジュールは、入出力制御装置５の先に接続されているディスク装置６あるいは共有メモリ４に格納される。共有メモリがなく、プロセッサ内のローカルメモリが存在するマルチプロセッサシステムでは、当該ローカルメモリにプログラムモジュールが格納される。プログラムモジュールは、当該タスクを実行するために必要な命令が特定の命令セットで記述されている。
【００２２】
（タスク割り付けシステムの実装例）
タスク割り付けシステム８は、マルチプロセッサシステムが実行するプログラムの各タスクをプロセッサ１〜３に適切に割り付けるものであり、具体的にはプログラム（以下、タスク割り付けプログラムという）として実装される。タスク割り付けプログラムは、タスク割り付けのみを行う専用のプログラムであってもよいし、オペレーティングシステムの一部であったり、オペレーティングシステムとは別のメインプログラムであってもよい。図２〜図５に、タスク割り付けプログラムの実装例を示す。
【００２３】
図２の例では、特定のプロセッサ１上で動作するオペレーティングシステム（ＯＳ）１１の一部としてタスク割り付けプログラム１２が存在している。タスク割り付けプログラム１２は、これが存在するオペレーティングシステム１１が動作しているプロセッサ１を含めた全てのプロセッサ１〜３に対するタスク割り付け処理を司る。
【００２４】
図３の例では、マルチプロセッサシステムに含まれる全てのプロセッサ１〜３上で動作するオペレーティングシステム１１の一部として、タスク割り付けプログラム１２が存在している。図３のシステムでのタスク割り付け処理の態様は、二つ考えられる。一つの態様では、各々のプロセッサ１〜３上で動作しているオペレーティングシステム１１の一部であるタスク割り付けプログラム１２が完全に対等の関係で協調してタスク割り付け処理を行う。
【００２５】
図３におけるタスク割り付け処理の他の態様では、特定のプロセッサ上で動作しているオペレーティングシステムの一部であるタスク割り付けプログラムをメインのプログラムとし、他のプロセッサで動作しているオペレーティングシステムの一部であるタスク割り付けプログラムをサブのプログラムとして、これらメイン及びサブのプログラムが協調してタスク割り付け処理を行う。
【００２６】
図４の例では、マルチプロセッサシステムを構成する主たるプロセッサ１〜３とは別に管理用プロセッサ９が設けられ、この管理用プロセッサ９上で動作するオペレーティングシステム１３の一部として、タスク割り付けプログラム１２が存在する。管理用プロセッサ９には、マルチプロセッサシステムが実行するプログラムのタスクは割り付けられない。
【００２７】
図５は、図３と図４を組み合わせた例であり、プロセッサ１〜３上で動作しているオペレーティングシステム１１の一部及び管理用プロセッサ９上で動作しているオペレーティングシステム１３の一部であるタスク割り付けプログラム１２のうち、後者がタスク割り付けプログラムのメインのプログラムとして動作し、前者はサブのプログラムとしてメインのプログラムと協調してタスクの割り付け処理を行う。
【００２８】
図２〜図５では、上述したようにタスク割り付けプログラムがオペレーティングシステムの一部である例について述べたが、タスク割り付けプログラムがメインプログラムの一部であったり、タスク割り付けのみを行う専用のプログラムである場合にも、タスク割り付けプログラムを同様に配置することが可能である。
【００２９】
（マルチプロセッサシステムが実行するプログラムについて）
本実施形態のマルチプロセッサシステムが実行するプログラムは、図６に示されるように複数のタスクＴ１〜Ｔ６とタスクＴ１〜Ｔ６間の依存関係で記述される。前述したように、タスクＴ１〜Ｔ６はひとまとまりの処理を行うプログラムの実行単位である。タスクＴ１〜Ｔ６間の依存関係は、タスクＴ１〜Ｔ６間でのデータの受渡しあるいは制御の受渡しのいずれか、あるいは両方であり、図６では矢印によってタスクからタスクへのデータまたは制御の受け渡しが示されている。タスクのプログラムモジュールを実行した時には、この矢印に従ってタスク間でデータ転送が行われる。
【００３０】
（プログラムのタスク実行例）
図７（ａ）（ｂ）（ｃ）に、タスクの実行の様子の種々の例を示す。
図７（ａ）の例は、一入力一出力のタスクの実行の様子を示している。タスクの実行は、まず入力元となるタスクから処理に必要なデータを受信し、次にそのデータに対して処理を行い、最後に出力先となるタスクに対してデータを送信する、という３つの段階からなる。
図７（ｂ）には、２入力２出力のタスクの実行の様子を示す。この例では、全ての入力元タスクからデータを受け取ってから、そのデータに対して処理を行い、最後に出力先にデータを送信する。
図７（ｃ）は、図７（ａ）（ｂ）は異なり、入力データは一度に全てを与えられるわけではなく、断続的に入力元となるタスクから与えられ、例えばある時間単位に受信したデータに対して処理を行い、その処理結果のデータを逐次出力先のタスクに送信するというタスク実行の様子を示している。
このようなタスク実行に伴うタスク間のデータ送受信にかかるコストは、マルチプロセッサシステムの構成にも大きく依存するが、一般的に比較的高い。
【００３１】
さらに、図１に示したような共有メモリ４を有するマルチプロセッサシステムでは、データを送信するタスクとデータを受信するタスクが同じプロセッサに割り付けられているか、異なるプロセッサに割り付けられているかに関わらず、データの送信は共有メモリ４への書き込み、そしてデータの受信は共有メモリ４からの読み出しで実現される。一般的に、共有メモリ４に対する書き込み／読み出しのコストも高い。
【００３２】
一方、プロセッサがキャッシュを有するマルチプロセッサシステムでは、もしデータの送信と受信をするタスクが同じプロセッサに割り付けされていた場合には、それらのタスク間のデータ送受信はプロセッサ内のキャッシュを介して行われる。通常、キャッシュへのアクセスは共有メモリへのアクセスに比べて高速であるため、タスクから見ると、処理結果のデータの送信や処理に必要なデータの受信がキャッシュへの読み書きによって行われる分、見かけ上データ送受信のコストは下っている。しかし、キャッシュはその内容についてメモリとの整合性を保つ必要があるため、実際にはやはりメモリへの書き込みが発生する。
【００３３】
逆に、データを送信するタスクと受信をするタスクが異なるプロセッサに割り付けされていた場合には、キャッシュの仕組みによっても異なるが、データの送信は共有メモリへの書き込みによって、データの受信は共有メモリからの読み出しによって行われることにより、タスク間のデータ送受信が実現される。このような共有メモリを介してのデータ送受信も、やはりコストが高い。
【００３４】
次に、プロセッサがローカルメモリを有するマルチプロセッサシステムでは、もしデータの送信と受信をするタスクが同じプロセッサに割り付けされていた場合は、それらのタスクの間ではプロセッサ内のローカルメモリを利用したデータの送受信が行われる。ローカルメモリへのアクセスは通常、共有メモリへのアクセスに比べ高速である。しかし、データの送信と受信をするタスクが異なるプロセッサに割り付けされていた場合には、送信元のタスクが割り付けられているプロセッサのローカルメモリから送信先のタスクが割り付けられているプロセッサ内のローカルメモリへのデータ転送によって、タスク間のデータ送受信が実現される。このローカルメモリ間の通信は通常、共有メモリへのアクセスと同様にコストが高い。
【００３５】
このようにマルチプロセッサシステムにおいては、プロセッサ間通信に伴うコストが高いため、プロセッサ間通信を十分に考慮してタスクをプロセッサに割り付ける必要がある。
【００３６】
従来のタスク割り付けにおいては、各タスクの実行に必要なプログラムを格納しているプログラムモジュールの記述に使用されている命令セットと同一命令セットを採用しているプロセッサへタスクを割り付けている。このような割り付け方法を本実施形態のようなヘテロマルチプロセッサシステムに適用すると、頻繁にタスク間のデータ通信がプロセッサ間で行われることにより、実行効率が悪くなってしまう。
【００３７】
この問題を緩和するため、本実施形態では従来の各タスクの実行に必要なプログラムを格納しているプログラムモジュールの記述に使用されている命令セットと同一命令セットを採用しているプロセッサへの割り当てを「仮割り当て」と位置付け、この「仮割り当て」の後に、プログラムの実行効率がより高くなるように各タスクのプロセッサへの割り付けを最適化する。
【００３８】
（タスク割り付けシステムの詳細）
次に、タスク割り付けシステム８について詳しく述べる。図８は、図１中に示したタスク割り付けシステム８の構成例を示している。前述のように、タスク割り付けシステム８は専用のタスク割り付けプログラム、オペレーティングシステムの一部、あるいはオペレーティングシステムとは別のメインプログラムで実現されるが、図８では分かる易くするためタスク割り付け部８の機能をブロック図で表している。
【００３９】
図８において、タスク仮割り付け部２１は上述した仮割り付け、すなわち各タスクの実行に必要なプログラムを格納しているプログラムモジュールの記述に使用されている命令セットと同一命令セットを採用しているプロセッサへのタスクの割り付けを行う。各タスクの仮割り付けに関する情報は、例えば図１中のディスク装置６または共有メモリ４の一部である仮割り付けタスク保持部２２に保持されており、仮割り付けタスク読出部２３により読み出される。
【００４０】
仮割り付けタスク読出部２３によって読み出された情報は、最適化対象タスク判定部２４に入力される。最適化対象タスク判定部２４では、マルチプロセッサシステムが実行する各プログラムを構成する全タスクについて、最適化によって割り付け先を変更した方がよいかどうかが判定される。各タスクのうち最適化対象と判定されたタスクに対して、実際に最適化によるプロセッサへの割り付けの変更を行うかどうかが、最適化実行判定部２５によって判定される。
【００４１】
最適化によるプロセッサへの割り付け先の変更を実行することになったタスクに対して、最適化実行部２６により実際に割り付け先の変更処理が行われる。割り付け先の変更を行ったかどうかに関わらず、全てのタスクについてその最終的な割り付け結果の情報が割り付けタスク書込部２７によって、例えば図１中のディスク装置６または共有メモリ４の一部である割り付けタスク保持部２８に書き込まれる。
【００４２】
図９に示されるように、最適化実行判定部２５はプログラムの実行効率を予測する手段として、例えば実行時間予測部３１、単位時間処理可能データ量予測部３２、プロセッサ負荷予測部３３及びプロセッサ間通信データ量予測部３４を有する。予測方法選択部３５によって、いずれか一つまたは複数の予測部が実行効率判定のために選択される。
【００４３】
ここで、実行時間予測部３１は対象タスクを仮割り付け先に割り付けた場合と割り付け先を変更した場合のタスクの実行時間とを予測する。単位時間処理可能データ量予測部３２は、対象タスクを仮割り付け先に割り付けた場合と割り付け先を変更することによるプログラムの単位時間当たりの処理可能データ量を予測する。プロセッサ負荷判定部３３は、対象タスクの割り付け先を変更することによる割り付け先プロセッサの負荷を予測する。プロセッサ間通信データ量予測部３４は、対象タスクを仮割り付け先に割り付けた場合と割り付け先を変更した場合のプログラムのプロセッサ間通信データ量とを予測する。
【００４４】
実行効率判定部３６では、予測方法選択部３５により選択された予測部の予測結果に基づいてプログラムの実行効率を判定する。具体的には、実行時間予測部３１は（ａ）実行時間予測部３１の予測した実行時間が割り付け先の変更によって短縮するか否か、（ｂ）単位時間処理可能データ量予測部３２が予測した処理可能データ量が割り付け先の変更によって増加するか否か、または予測した処理可能データ量が割り付け先の変更によって予め定められた閾値を越えて増加するか否か、（ｃ）プロセッサ負荷予測部３３が予測したプロセッサの負荷が過負荷にならないか否か、（ｄ）プロセッサ間通信データ量予測部３４が予測したプロセッサ間通信データ量が割り付け先の変更によって減少するか否かにより、タスク割り付け先の変更によってプログラムの実行効率が向上するか否かの判定を行う。
【００４５】
予測方法選択部３５により選択された予測部が複数の場合には、実行効率判定部３６はそれら複数の予測結果を総合的に判断して、実行効率が向上するか否かを最終的に判定する。これらの実行効率判定の具体的な手法については、後に詳しく説明する。
【００４６】
こうして実行効率判定部３６によって「タスク割り付け先の変更によりプログラムの実行効率が向上する」と判定されたタスクに対しては、割り付け先プロセッサ決定部３７により新たな割り付け先プロセッサが決定される。「タスク割り付け先を変更してもプログラムの実行効率が向上しない」と判定されたタスクについては、仮割り付け先のプロセッサが最終的な割り付け先プロセッサとして決定される。
【００４７】
図１０は、複数の異種プロセッサ用の命令セットで記述されたプログラムモジュールをタスクＴ１〜Ｔ９として組合せたプログラムの例である。各タスクＴ１〜Ｔ９のプログラムモジュールを記述している命令セットは、括弧内のアルファベットＡ，Ｂ，Ｃで示されている。すなわち、図１０のプログラムは命令セットＡで記述されたプログラムモジュールを持つタスクＴ１，Ｔ５，Ｔ９と、命令セットＢで記述されたプログラムモジュールを持つタスクＴ２，Ｔ６、及び命令セットＣで記述されたプログラムモジュールを持つタスクＴ３，Ｔ４，Ｔ７，Ｔ８から構成される。
【００４８】
従来のタスク割り付け方法に従うと、図１０に示したプログラム中の各タスクは図１１に示されるように、そのプログラムモジュールを記述している命令セットを有するプロセッサに割り付けられる。すなわち、タスクＴ１，Ｔ５，Ｔ９は命令セットＡを有するプロセッサ１に、タスクＴ２，Ｔ６は命令セットＢを有するプロセッサ２に、そしてタスクＴ３，Ｔ４，Ｔ７，Ｔ８は命令セットＣを有するプロセッサ３にそれぞれ割り付けられる。
【００４９】
これに対して、本実施形態では前述したように図１１のタスク割り付けを仮割り付けと位置付け、この仮割り付け後の最適化により例えば図１２に示すように割り付け先のプロセッサを変更することができる。これによりプロセッサ間での通信が必要なタスク間のデータ送受信の回数は、図１１に示す７回から図１２に示す２回へと大きく減少する。すなわち、プロセッサ間通信によるオーバヘッドが減少し、プログラムの実行効率が大きく改善される。
【００５０】
（タスク割り付け処理手順１）
次に、本実施形態に基づくタスク割り付けの処理手順について、フローチャートを用いて説明する。図１３は、本実施形態におけるタスク割り付け処理の一例の基本的な流れを示している。図１３に示した手順をタスク割り付け処理手順１とする。
【００５１】
まず、図８中のタスク仮割り付け部２１によって、プログラムを構成する全タスクを各プロセッサに対して仮割り付けする（ステップＳ１１）。各タスクの仮割り付けに関する情報は、図８中の仮割り付けタスク保持部２２に保持される。次に、仮割り付けタスク保持部２２から仮割り付けタスク読出部２３により仮割り付けに関する情報が読み出され、最適化対象タスク判定部２４に送られる。
【００５２】
最適化対象タスク判定部２４では、プログラムを構成する全タスクのうち、割り付け先プロセッサの変更により実行効率が向上する可能性のあるタスク（最適化対象タスク）と判定された対象タスクについて、最適化実行判定部２５において割り付け先プロセッサの変更によりプログラム実行効率が向上するか否かを判定する（ステップＳ１２）。
【００５３】
ここで、ステップＳ１２において割り付け先プロセッサの変更によりプログラム実行効率が向上しないと判定されたタスクに対しては、ステップＳ１１での仮割り付け先のプロセッサを最終的な割り付け先プロセッサとして決定して処理を終了する。一方、割り付け先プロセッサの変更によりプログラム実行効率が向上する場合には、新たな割り付け先プロセッサを決定する。
【００５４】
次に、割り付け先プロセッサの変更によりプログラム実行効率が向上すると判定された対象タスクに対して、決定された新たなプロセッサに割り付け先を変更する（ステップＳ１３）。割り付け先プロセッサの変更とは、具体的には対象タスクについて新たな割り付きけ先プロセッサが有する命令セットで記述されたプログラムモジュールを取得することである。
【００５５】
図１３に示した処理が終了すると、プログラムを構成する全タスクがそれぞれ適切なプロセッサに割り付けられる。これによって、マルチプロセッサシステムは当該プログラムを効率よく実行することができる。
【００５６】
次に、図１３の各ステップＳ１１〜Ｓ１３の処理について詳しく説明する。  図１４には、図１３中のステップＳ１１の処理の詳細を示す。割り付けるべき対象タスクのプログラムモジュールを記述している命令セットが何であるかを判断し（ステップＳ１０１）、その命令セットを有するプロセッサに対して対象タスクを割り付ける（ステップＳ１０２）。図１０に示したプログラムを例にとると、このタスク仮割り付けでは、図１０のプログラム中の各タスクを図１１に示したように各プロセッサに割り付けることになる。
【００５７】
図１５は、図１３中のステップＳ１２の詳細な処理を示すフローチャートである。図１５では一つの対象タスクに対する処理を記述しているが、実際にはプログラムを構成する全てのタスクに対して同様の処理を行う。この処理を同じ対象タスクに対して複数回にわたり適用することもできる。例えば、一度プログラムを構成する全てのタスクについて図１５の処理を行い、幾つかのタスクについて最適化による割り付けの変更を行った後に、その結果のタスク群に対して再度、同じ処理を施してもよい。このようにすることで、よりよい最適化の結果が得られる可能性がある。
【００５８】
まず、仮割り付けタスク読出部２３によって読み出されたタスク仮割り付けに関する情報は、最適化対象タスク判定部２４に送られる。最適化対象タスク判定部２４は、ステップＳ１１で仮割り付けされたタスクに対して、現在注目している対象タスクの直前または直後のタスクが、対象タスクが仮割り付けされているプロセッサとは命令セットが異なるプロセッサに割り付けられているか否かを判定する（ステップＳ２０１）。
【００５９】
ここで、例えば図１０のプログラムにおけるタスクＴ１，Ｔ２，Ｔ４，Ｔ５のような、直前のタスクが存在しない対象タスクについては、「直前のタスク」として仮想的なタスクを定義する。仮想的なタスクとは、例えば予想実行時間が０で、かつ当該対象タスクへ送信するデータも０、さらにプロセッサの負荷には全く影響を及ぼさないタスクである。さらに、図１０中のタスクＴ９のような、直後のタスクが存在しない対象タスクについても、同様に「直後のタスク」を定義する。
【００６０】
ステップＳ２０１の判定結果がＹＥＳであれば、対象タスクに関する情報を最適化対象タスクとして最適化実行判定部２４へ渡し、ステップＳ２０２の処理を行う。一方、ステップＳ２０１の判定結果がＮＯ、すなわち対象タスクの直前及び直後の両タスクが対象タスクと同じプロセッサに仮割り付けされている場合には、対象タスクの割り付け先プロセッサを変更する必要はない、言い換えれば割り付け先プロセッサを変更しても実行効率は向上しないので、その旨の判定結果を割り付けタスク書込部２７へ渡し、仮割り付けタスクに関する情報を割り付けタスク保持部２８に書き込んで処理を終了する。
【００６１】
ステップＳ２０２では、ステップＳ２０１により最適化対象タスクと判定されたタスクを既に当該タスクが仮割り付けされたプロセッサと割り付け変更先候補のプロセッサにそれぞれ割り付けた場合の各々におけるプログラムの実行効率を最適化実行判定部２５で予測する。ここで、割り付け変更先候補のプロセッサとは、現在注目している最適化対象タスクの仮割り付け先プロセッサと異なるプロセッサが仮割り付け先となっている、当該タスクの直前及び直後のタスクが割り付けられているプロセッサの全てである。
【００６２】
最適化実行判定部２５は、引き続き最適化対象タスクの割り付け先を割り付け変更先候補のプロセッサにした方がプログラムの実行効率が向上するかどうかを判定する（ステップＳ２０３）。ここで、ステップＳ２０３の判定結果がＹＥＳであれば、最適化実行判定部２５は割り付け変更先候補プロセッサを割り付け先プロセッサと決定し（ステップＳ２０４）、決定された割り付け変更先プロセッサに割り付け先を変更する旨の印を最適化対象タスクに付け（ステップＳ２０５）、処理を終了する。ステップＳ２０３の判定結果がＮＯであれば、そのまま処理を終了する。
【００６３】
（タスクのグループ化について）
プログラムが図１０に示したような簡単なものでなく、例えばタスク数が多く規模の大きなプログラム、タスク間依存関係の複雑なプログラム、あるいはタスク数が多くかつタスク間依存関係も複雑なプログラムでは、最適化対象タスク判定部２４及び最適化実行判定部２５での処理が複雑になることが考えられる。
【００６４】
図１６は、こうした複雑なプログラムに対するタスク割り付け処理を簡単にするため、プログラムを構成する各タスクをグループ化する処理を示している。この処理は、例えば図１５のステップＳ２０１の前処理として配置される。このようなタスクのグループ化によって、タスクの仮割り付け図を簡略化し、図１５の処理を簡略化することができる。図１６では、一つのタスクに関する処理を例示しているが、実際にはプログラムを構成する全てのタスクについて同様の処理を行う。
【００６５】
図１６の処理の流れを説明すると、まず注目している対象タスクの直後にタスクがあるかどうかを判定する（ステップＳ２１１）。ステップＳ２１１の判定結果がＹＥＳであれば、直後のタスクが全て対象タスクと同じプロセッサに仮割り付けされているかどうかを判定する（ステップＳ２１２）。
【００６６】
ステップＳ２１２の判定結果がＹＥＳであれば、対象タスクのみが先行タスクとなっている直後のタスクを選択する（ステップＳ２１３）。こうして選択したタスクと対象タスクをグループ化し（ステップＳ２１４）、このグループを一つの対象タスクとして取り扱い、図１５のステップＳ２０１に渡す。このようなグループ化により、複雑なプログラムについてもタスク割り付け処理を容易にすることができる。
【００６７】
（最適化実行判定）
次に、図１３中の判定ステップＳ１２の処理、特に図１５中に示したステップＳ２０２及びＳ２０３の処理について説明する。この処理は、図９に詳細な構成を示した図８中の最適化実行判定部２５によって、以下に列挙する幾つかの実行効率判定基準を単独で用いるか、あるいは幾つか組み合わせて行われる。
【００６８】
［実行効率判定基準１］
割り付け先プロセッサを変更することにより、プログラム実行時間（タスクの実行に要する時間）が短くなるかどうかを判定する。
タスクの実行に要する時間は、タスクの実行に必要なプログラムを格納するプログラムモジュールに記述してある命令列から見積もることができ、割り当て変更先の候補となっているプロセッサでのタスクの実行に要する時間も同様にして見積もることができる。
【００６９】
この実行効率判定基準１によれば、プロセッサに割り付けるべき対象タスクに対して、仮割り付けされているプロセッサでの実行に必要な予測実行時間よりも、割り付け変更先候補となっているいずれかのプロセッサでの実行に必要な予測実行時間の方が短ければ、その対象タスクは最適化対象タスク、すなわち最適化により割り付け先プロセッサを変更すべきタスクであると判定する。
【００７０】
複数の割り付け変更先候補プロセッサでの予測実行時間の方が、仮割り付け先プロセッサでの予測実行時間よりも短い場合も考えられる。この場合には、最も予測実行時間の短いプロセッサを割り付け変更先として選定するか、もしく実行効率判定基準１では複数のプロセッサを割り付け変更先候補として選定し、最終的な割り付け変更先プロセッサの選定は、他の実行効率判定基準による判定に委ねるという方法もある。
【００７１】
［実行効率判定基準２］
割り付け先プロセッサを変更することにより、タスクが単位時間内に処理できるデータ量が多くなるかどうかを判定する。
タスクが単位時間内に処理できるデータ量とは、すなわちタスクが単位時間に先行タスクから受信できるデータ量である。単位時間内に先行タスクからタスク間通信により受信できるデータ量は、現在注目している対象タスクと各先行タスクが同一プロセッサに仮割り付けされているか、異なるプロセッサに仮割り付けされているかかの違いによって影響を受ける。これは異なるプロセッサ間の通信は、同一プロセッサ内での通信に比べて非常にコストが高いからである。
【００７２】
実行効率判定基準２によると、まず単位時間内に全ての先行タスクとのタスク間通信によって受信できるデータ量について、仮割り付け先となっているプロセッサでの場合と、各割り付け変更先候補となっているプロセッサについてそれぞれ予測する。
【００７３】
ここで、もし現在の仮割り付け先プロセッサにおいて単位時間内に受信することのできるデータ量よりも、割り付け変更先候補となっているプロセッサのいずれかに割り付けを変更した場合の方が、単位時間内に受信することのできるデータ量が増加していれば、現在注目しているタスクに対して当該割り付け変更先候補プロセッサへ割り付け先プロセッサを変更するべきと判断する。
【００７４】
複数の割り付け変更先候補プロセッサに割り付けを変更した場合に、現在注目している対象タスクが単位時間に受信できるデータ量が、現在注目しているタスクが仮割り当てされているプロセッサ上で単位時間内に受信できるデータ量よりも多い場合も考えられる。この場合には、現在注目している対象タスクが単位時間内に最も多いデータ量を受信することのできるプロセッサを割り付け変更先として選定する。
【００７５】
複数の割り付け変更先候補プロセッサでの対象タスクが単位時間内に受信できるデータ量が同じで、かつ仮割り当てされているプロセッサ上での単位時間内に受信することのできるデータ量よりも多い場合も含めて、実行効率判定基準２では複数のプロセッサを割り付け変更先候補として選定し、最終的な割り付け変更先プロセッサの選定は、他の実行効率判定基準による判定に委ねるという方法もある。
【００７６】
［実行効率判定基準３］
割り付け先プロセッサを変更することにより、タスクが単位時間に処理できるデータ量が予め設定された閾値よりも多くなるかどうかを判定する。
これは実行効率判定基準２と基本的に同様の判定であるが、現在注目している対象タスクが単位時間に受信できるデータ量を仮割り付け先プロセッサと割り付け変更先候補プロセッサについて比較する際に、予め単位時間内に受信できるデータ量について、開始する前に設定された静的な閾値、もしくは選定中に動的に設定された動的な閾値よりを導入する。
【００７７】
ここで、もし仮割り付け先プロセッサよりも割り付け変更先候補プロセッサのいずれかの方が、現在注目している対象タスクが単位時間に受信できるデータ量が多く、かつ閾値よりも大きい場合には、対象タスクに対して当該割り付け変更先候補プロセッサへ割り付け先プロセッサの変更を行うべきと判定する。
【００７８】
［実行効率判定基準４］
割り付け先プロセッサを変更することにより、割り付け変更先プロセッサが過負荷にならないかどうかを判定する。
割り付け先プロセッサを仮割り付け先プロセッサから変更したとしても、割り付け変更先となったプロセッサが過負荷になってしまっては、プログラム全体の実行効率の改善にはならない。
【００７９】
そこで、現在注目しているタスクを仮割り付け先プロセッサにそのまま割り付けた場合の全プロセッサの負荷を予測する。さらに、現在注目しているタスクを割り付け変更先候補のプロセッサのいずれかに割り当て先を変更した場合の全プロセッサの負荷をそれぞれ予測する。そして、割り付けを変更した場合に、割り付け変更先候補プロセッサが過負荷になっていなければ、最適化による割り付け先プロセッサの変更を行うべきと判断する。
【００８０】
割り付け先を変更しても、全プロセッサの予測した負荷が過負荷にならないような複数の割り付け変更先候補プロセッサが存在する場合もある。このような場合には、最も負荷の変動が少ない割り付け変更先候補プロセッサを選定したり、現在注目している対象タスクの割り付け先を変更しても最も負荷が少ない割り付け変更先候補プロセッサを選定するなどの方法をとることができる。さらには、この実行効率判定基準４では複数のプロセッサを割り付け先候補として選定し、最終的な割り当て変更先プロセッサの選定は他の実行効率判定基準による判定に委ねるという方法もある。
【００８１】
［実行効率判定基準５］
割り付け先プロセッサを変更することにより、プログラム全体でのプロセッサ間の通信データ量が小さくなるかどうかを判定する。
マルチプロセッサシステムにおけるプログラムの実行効率改善の鍵は、やはりプロセッサ間通信のデータ量である。この点に着目して、仮割り付け先プロセッサと割り付け変更先候補のプロセッサとで、プログラム全体におけるプロセッサ間通信によって転送されるデータ量が削減されるかどうかを判定基準とする。
【００８２】
具体的には、現在注目している対象タスクの割り付け先プロセッサを変更しない場合と、割り付け変更先候補プロセッサのいずれかに割り付け先を変更した場合について、プログラム全体でのプロセッサ間通信によって転送されるデータ量を見積もる。もし、いずれかの割り付け変更先プロセッサに割り付け先を変更した方が、割り付け先変更前よりもプログラム全体におけるプロセッサ間通信により転送されるデータ量が減少する場合には、当該割り付け変更先候補プロセッサへ割り付けを変更した方がよいと判断する。
【００８３】
対象タスクを複数の割り付け変更先候補プロセッサに割り付け先を変更した場合のプログラム全体でのプロセッサ間通信によって転送されると予想されるデータ量が、対象タスクが仮割り付けされているプロセッサに対してそのまま割り付けた際にプログラム全体でのプロセッサ間通信によって転送されると予想されるデータ量よりも少ないことも考えられる。この場合には、プログラム全体で最もプロセッサ間通信によって転送されるデータ量が少ない割り付け変更先候補プロセッサを割り付け変更先プロセッサとして選定する。あるいは、この実行効率判定基準５では複数のプロセッサを割り付け先候補として選定し、最終的な割り当て変更先プロセッサの選定は他の実行効率判定基準による判定に委ねるという方法もある。
【００８４】
［実行効率判定基準６］
割り付け先プロセッサを変更することにより、プログラム全体での単位時間のプロセッサ間の通信データ量が小さくなるかどうか。
これは実行効率判定基準５と基本的に同様の判定基準であるが、仮割り付け先プロセッサと各割り付け変更先候補プロセッサについてプロセッサ間転送データ量を単位時間当たりについて見積もる。割り付け変更先候補プロセッサのいずれかに割り付けを変更した場合のプログラム全体で単位時間内にプロセッサ間で転送されるデータ量が、仮割り付け先プロセッサにおけるプログラム全体で単位時間にプロセッサ間で転送されるデータ量よりも少なければ、当該割り付け変更先候補プロセッサへ割り付けを変更した方がよいと判定する。
【００８５】
（タスク割り付け処理の具体例）
次に、上述したタスク割り付け処理の手順を具体的なプログラムの例を用いて説明する。
以下の説明では、図１１のように仮割り付けされた図１０のプログラムの各タスクＴ１〜Ｔ９の割り付け先を最適化する手順について詳細に述べる。図１０のプログラムは、命令セットＡで記述されたプログラムモジュールを持つタスクＴ１，Ｔ５，Ｔ９と、命令セットＢで記述されたプログラムモジュールを持つタスクＴ２，Ｔ６、及び命令セットＣで記述されたプログラムモジュールを持つタスクＴ３，Ｔ４，Ｔ７，Ｔ８から構成される。
【００８６】
図１０のプログラムに対する図１１に示した仮割り付け結果においては、タスクＴ１，Ｔ５，Ｔ９は命令セットＡを有するプロセッサ１に、タスクＴ２，Ｔ６は命令セットＢを有するプロセッサ２に、そしてタスクＴ３，Ｔ４，Ｔ７，Ｔ８は命令セットＣを有するプロセッサ３にそれぞれ割り付けられている。
【００８７】
ここで説明するタスク割り付け処理の例では、割り付け先プロセッサを変更するかどうか、さらに割り付け先をどのプロセッサに変更するかどうかの判定に、先の実行効率判定基準１及び５のみを使用することとする。また、実行効率判定基準１より実行効率判定基準５の方が優先度が高いと仮定する。これらの仮定の導入は、実際のマルチプロセッサシステムではシステムの構成上の制約などにより、前述した全ての実行効率判定基準１〜６を用意するのは難しいと考えることができることから、妥当であると考えられる。
【００８８】
［タスクＴ１の割り付け先の最適化］
＜ステップ１−１＞タスクＴ１を読み出す。
＜ステップ１−２＞タスクＴ１の直前には仮想的なタスクしかないので、直前は無視できる。
＜ステップ１−３＞タスクＴ１の直後にはタスクＴ２，Ｔ３があり、タスクＴ２，Ｔ３はタスクＴ１とは異なるプロセッサ２，３にそれぞれ仮割り付けされているので、タスクＴ１の割り付け先を変更するかどうかの判断に進む。
＜ステップ１−４＞タスクＴ１の割り付け先をプロセッサ１からプロセッサ２，３に変更することによって、プログラム全体での単位時間当たりのプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ１−５＞タスクＴ１をそのままプロセッサ１で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ２，３で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ１−６＞ステップ１−４の結果、割り付け先変更前後でプログラム全体のプロセッサ間の通信データ量は変化することがなく、しかもステップ１−５の結果、タスクＴ１をプロセッサ１上で実行した方が、必要と予測される実行時間が短いと判明したとする。
＜ステップ１−７＞ステップ１−６の結果より、タスクＴ１については割り付け先プロセッサを変更しない旨、決定する。
【００８９】
［タスクＴ２の割り付け先の最適化］
＜ステップ２−１＞タスクＴ２を読み出す。
＜ステップ２−２＞タスクＴ２の直前には、タスクＴ１が存在する。
＜ステップ２−３＞タスクＴ２の直後にはタスクＴ３があり、タスクＴ１，Ｔ３はタスクＴ２とは異なるプロセッサ１，３にそれぞれ仮割り付けされているので、タスクＴ２の割り付け先を変更するかどうかの判断に進む。
＜ステップ２−４＞タスクＴ２の割り付け先をプロセッサ２からプロセッサ１，３に変更することによって、プログラム全体での単位時間当たりのプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ２−５＞タスクＴ２をそのままプロセッサ２で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ１，３で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ２−６＞ステップ２−４の結果、割り付け変更前後でプログラム全体のプロセッサ間の通信データ量は変化することはなく、またステップ２−５の結果、タスクＴ２をプロセッサ１上で実行した方が、必要と予測される実行時間が最も短いと判明したとする。
＜ステップ２−７＞ステップ２−６の結果より、タスクＴ２の割り付け先プロセッサをプロセッサ１に変更する旨、決定する。
【００９０】
［タスクＴ３の割り付け先の最適化］
＜ステップ３−１＞タスクＴ３を読み出す。
＜ステップ３−２＞タスクＴ３の直前には、タスクＴ１，Ｔ２が存在する。
＜ステップ３−３＞タスクＴ３の直後にはタスクＴ７があり、タスクＴ１，Ｔ２はタスクＴ３とは異なるプロセッサ１に仮割り付けされている。タスクＴ７はプロセッサ３に仮割り付けされている。タスクＴ１，Ｔ２がプロセッサ１に仮割り付けされているので、タスクＴ３の割り付け先を変更するかどうかの判断に進む。
＜ステップ３−４＞タスクＴ３の割り付け先をプロセッサ１に変更することによって、プログラム全体での単位時間のプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ３−５＞また、タスクＴ３をそのままプロセッサ３で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ１で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ３−６＞ステップ３−４の結果、既にタスクＴ１，Ｔ２がプロセッサ１に割り付けされているため、タスクＴ３の割り付け先をプロセッサ１に変更した方が、プログラム全体のプロセッサ間の通信データ量は減少することが判明したとする。また、ステップ３−５の結果、タスクＴ３をプロセッサ１上で実行しても必要と予測される実行時間はほとんど変化しないと判明したとする。
＜ステップ３−７＞ステップ３−６の結果より、タスクＴ３の割り付け先プロセッサをはプロセッサ１に変更する旨、決定する。
【００９１】
［タスクＴ４の割り付け先の最適化］
＜ステップ４−１＞タスクＴ４を読み出す。
＜ステップ４−２＞タスクＴ４の直前には仮想的なタスクしかないので、無視できる。
＜ステップ４−３＞タスクＴ４の直後にはタスクＴ６があり、タスクＴ６はタスクＴ４とは異なるプロセッサ２に仮割り付けされているので、タスクＴ４の割り付け先を変更するかどうかの判断に進む。
＜ステップ４−４＞タスクＴ４の割り付け先をプロセッサ２に変更することによって、プログラム全体での単位時間のプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ４−５＞タスクＴ４をそのままプロセッサ３で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ２で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ４−６＞ステップ４−４の結果、タスクＴ４の割り付け先をプロセッサ２に変更した方が、プログラム全体のプロセッサ間の通信データ量は減少することが判明したとする。また、ステップ４−５の結果、タスクＴ４をプロセッサ２上で実行しても、必要と予測される実行時間はほとんど変化しないと判明したとする。
＜ステップ４−７＞ステップ４−６の結果より、タスクＴ４の割り付け先プロセッサをプロセッサ２に変更する旨、決定する。
【００９２】
［タスクＴ５の割り付け先の最適化］
＜ステップ５−１＞タスクＴ５を読み出す。
＜ステップ５−２＞タスクＴ５の直前には仮想的なタスクしかないので、無視できる。
＜ステップ５−３＞タスクＴ５の直後にはタスクＴ６があり、タスクＴ６はタスクＴ５とは異なるプロセッサ２に仮割り付けされているので、タスクＴ５の割り付け先を変更するかどうかの判断に進む。
＜ステップ５−４＞タスクＴ５の割り付け先をプロセッサ２に変更することによって、プログラム全体での単位時間のプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ５−５＞また、タスクＴ５をそのままプロセッサ１で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ２で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ５−６＞ステップ５−４の結果、タスクＴ５の割り付け先をプロセッサ２に変更した方が、プログラム全体のプロセッサ間の通信データ量は減少することが判明したが、ステップ５−５の結果、タスクＴ５をプロセッサ２上で実行すると、必要と予測される実行時間が増加すると判明したとする。
＜ステップ５−７＞ステップ５−６の結果と処理開始前に設定されていた優先度によって、タスクＴ５の割り付け先プロセッサをプロセッサ２に変更する旨、決定する。
【００９３】
［タスクＴ６の割り付け先の最適化］
＜ステップ６−１＞タスクＴ６を読み出す。
＜ステップ６−２＞タスクＴ６の直前にはタスクＴ４，Ｔ５があるが、タスクＴ４，Ｔ５は共にタスクＴ６と同じプロセッサ３に割り付けられているので、無視できる。
＜ステップ６−３＞タスクＴ６の直後にはタスクＴ８があり、タスクＴ８はタスクＴ６とは異なるプロセッサ３に仮割り付けされているので、タスクＴ６の割り付け先を変更するかどうかの判断に進む。
＜ステップ６−４＞タスクＴ６をプロセッサ３に割り付け先を変更することによって、プログラム全体での単位時間のプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ６−５＞タスクＴ６をそのままプロセッサ２で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ３で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ６−６＞ステップ６−４の結果、タスクＴ６の割り付け先をプロセッサ３に変更すると、プログラム全体のプロセッサ間の通信データ量は増加することが判明し、ステップ６−５の結果、タスクＴ６をプロセッサ３上で実行すると、必要と予測される実行時間が増加すると判明したとする。
＜ステップ６−７＞ステップ６−６の結果から、タスクＴ６の割り付け先プロセッサを変更しない旨、決定する。
【００９４】
［タスクＴ７の割り付け先の最適化］
＜ステップ７−１＞タスクＴ７を読み出す。
＜ステップ７−２＞タスクＴ７の直前にはタスクＴ３があり、タスクＴ７と異なるプロセッサに割り付けられている。
＜ステップ７−３＞タスクＴ７の直後にはタスクＴ８があり、タスクＴ８はタスクＴ７と同じプロセッサ３に割り付けられている。しかし、タスクＴ７の直前のタスクＴ３がタスクＴ７と異なるプロセッサ１に割り付けられているので、タスクＴ７の割り付け先を変更するかどうかの判断に進む。
＜ステップ７−４＞タスクＴ７の割り付け先をプロセッサ１に変更することによって、プログラム全体での単位時間のプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ７−５＞タスクＴ７をそのままプロセッサ３で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ１で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ７−６＞ステップ７−４の結果、タスクＴ７の割り付け先をプロセッサ１に変更すると、プログラム全体のプロセッサ間の通信データ量は増加することが判明し、また、ステップ７−５の結果、タスクＴ７ほプロセッサ１上で実行すると、必要と予測される実行時間が増加すると判明したとする。
＜ステップ７−７＞ステップ７−６の結果から、タスクＴ７の割り付け先プロセッサを変更しない旨、決定する。
【００９５】
［タスクＴ８の割り付け先の最適化］
＜ステップ８−１＞タスクＴ８を読み出す。
＜ステップ８−２＞タスクＴ８の直前にはタスクＴ６，Ｔ７があり、タスクＴ６はタスクＴ８とは異なるプロセッサ３に割り付けられている。
＜ステップ８−３＞タスクＴ８の直後にはタスクＴ９があり、タスクＴ９はタスクＴ８とは異なるプロセッサ１に割り付けられているので、タスクＴ８の割り付け先を変更するかどうかの判断に進む。
＜ステップ８−４＞タスクＴ８の割り付け先をプロセッサ１及び２に変更することによって、プログラム全体での単位時間のプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ８−５＞タスクＴ８をそのままプロセッサ３で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ１及び２で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ８−６＞ステップ８−４の結果、タスクＴ８の割り付け先をプロセッサ１または２に割り付けを変更しても、プログラム全体のプロセッサ間の通信データ量は変化しないことが判明し、また、ステップ８−５の結果、タスクＴ８をそのままプロセッサ３上で実行した方が、必要と予測される実行時間が最も短いと判明したとする。
＜ステップ８−７＞ステップ８−６の結果から、タスクＴ８の割り付け先プロセッサを変更しない旨、決定する。
【００９６】
［タスクＴ９の割り付け先の最適化］
＜ステップ９−１＞タスクＴ９を読み出す。
＜ステップ９−２＞タスクＴ９の直前にはタスクＴ８があり、タスクＴ９とは異なるプロセッサ３に割り付けられている。
＜ステップ９−３＞タスクＴ９の直後には仮想的なタスクしかないので、無視できる。しかし、タスクＴ９の直前のタスクＴ８がタスクＴ９と異なるプロセッサ３に割り付けられているので、タスクＴ９の割り付け先を変更するかどうかの判断に進む。
＜ステップ９−４＞タスクＴ９をプロセッサ３に割り付け先を変更することによって、プログラム全体での単位時間のプロセッサ間の通信データ量が小さくなるかどうかを見積もる。
＜ステップ９−５＞タスクＴ９をそのままプロセッサ１で実行した場合に必要と予測される実行時間と、割り付け変更先候補プロセッサであるプロセッサ３で実行した場合に必要と予測される実行時間を見積もる。
＜ステップ９−６＞ステップ９−４の結果、タスクＴ９の割り付け先をプロセッサ１に変更した方が、プログラム全体のプロセッサ間の通信データ量は減少することが判明する。ステップ９−５の結果、タスクＴ９をプロセッサ３上で実行した方が、必要と予測される実行時間が短いと判明したとする。
＜ステップ９−７＞ステップ９−６の結果から、タスクＴ９の割り付け先プロセッサをプロセッサ３へ変更する旨、決定する。
以上のタスク割り付け処理の結果、図１０のプログラムについて図１１のように仮割り付けされていたタスク群の割り付け先が図１２のように最適化される。
【００９７】
（割り付け先プロセッサ用のプログラムモジュール取得）
次に、図８中の最適化実行部（割り付け先プロセッサ変更部）２６において、変更すべき割り付け先プロセッサ用のプログラムモジュールを取得する処理について説明する。
前述の処理により割り付け先プロセッサが変更されたタスクを実行するためには、割り付け先プロセッサ用のプログラムモジュールを何らかの方法で取得する必要がある。割り付け先が変更されたタスクを実行するためのプログラムを格納したプログラムモジュールは、仮割り付けされたプロセッサが有する命令セットで記述されており、変更された割り付け先プロセッサが有する命令セットとは異なるからである。
【００９８】
そこで、本実施形態では例えば図１７〜図１９に示すような３つの手順のいずれかによって、変更された割り付け先プロセッサが有する命令セットで記述された、当該タスクを実行するためのプログラムを格納したプログラムモジュールを取得する。図１７〜図１９は、図１３中のステップＳ１３の処理を詳しく示している。
【００９９】
図１７に示す手順では、対象タスクが元々持っていたプログラムモジュールの記述に用いられている、仮割り付け先プロセッサが有する命令セットに特有の命令を、変更された割り付け先プロセッサの命令セットにおける同じ処理を行う命令に置換することによって、変更された割り付け先プロセッサが有する命令セットで記述されたプログラムモジュールを得る。
【０１００】
すなわち、まず割り付け先を変更すべきと判定された対象タスクのプログラムモジュール内の命令が割り付け先プロセッサに存在しない命令か否かを判定する（ステップＳ３０１）。ステップＳ３０１の判定結果がＹＥＳの場合には、その命令を割り付け先プロセッサ用の同一処理を行う命令に置換することによって、割り付け先プロセッサ用のプログラムモジュールを生成する（ステップＳ３０２）。ステップＳ３０１の判定結果がＮＯの場合には、新たなプログラムモジュールの取得は必要がないため、処理を終了する。ステップＳ３０１〜Ｓ３０２の処理をステップＳ３０３で全ての命令について処理が終了したと判断されるまで行う。
【０１０１】
図１８は、図１７のステップＳ３０２に代わる処理を示している。この手順では、対象タスクが元々持っていたプログラムモジュールのソースコードから、変更された割り付け先プロセッサが有する命令セットで記述されたプログラムモジュールを生成することのできるコンパイラを用いて、変更された割り付け先プロセッサが有する命令セットで記述されたプログラムモジュールを取得する。
【０１０２】
図１９は、同様に図１７のステップＳ３０２に代わる処理を示している。この手順では、変更された割り付け先プロセッサが有する命令セットで記述された、当該タスクのプログラムモジュールをファイルシステム中から、もしくはネットワークから検索して取得する。
【０１０３】
（タスク割り付け処理手順２）
次に、本実施形態に基づくタスク割り付けの処理手順の他の例について説明する。図２０は、タスク割り付け処理手順２の流れを示している。
図１３に示したタスク割り付け処理手順１では、プログラムを構成する全タスクを各プロセッサに対して、仮割り付け（ステップＳ１１）、割り付け先プロセッサの変更によりプログラム実行効率が向上するか否かの判定（ステップＳ１２）及び割り付け先プロセッサの変更によりプログラム実行効率が向上すると判定された対象タスクに対する割り付け先プロセッサの変更（ステップＳ１３）を順次行っている。
【０１０４】
これに対し、図２０に示すタスク割り付け処理手順２では、まずプログラムを構成する全タスクから一つのタスクを選択し（ステップＳ２１）、選択したタスクについて図１３中のステップＳ１１〜Ｓ１３に相当する処理を行う（ステップＳ２２〜Ｓ２４）。そして、プログラムを構成する全タスクについてプロセッサに対する割り付け処理が終了したと判断されるまで、ステップＳ２１〜Ｓ２４の処理を繰り返す。
【０１０５】
このようにして図２０の処理が終了すると、プログラムを構成する全タスクがそれぞれ適切なプロセッサに割り付けられるので、マルチプロセッサシステムは当該プログラムを効率よく実行することができる。
【０１０６】
（タスク割り付け処理手順３）
図２１は、本実施形態に基づくもう一つのタスク割り付け処理手順の流れを示している。このタスク割り付け処理手順３では、図１３のステップＳ１１に相当するプログラムを構成する全タスクの仮割り付けを行った後、プログラムの実行を開始する（ステップＳ３１〜Ｓ３２）。この後、プログラムの実行途中でステップＳ３３において所定の条件が満たされた場合にのみ、図１３中のステップＳ１２〜Ｓ１３に相当する処理を行う（ステップＳ３４〜Ｓ３５）。そして、ステップＳ３６でプログラムの実行が終了したと判断されるまで、ステップＳ３２〜Ｓ３５の処理を繰り返す。
【０１０７】
ここで、ステップＳ３３における「所定の条件」としては、例えば以下の条件が挙げられる。
［条件１］一定時間間隔で訪れるシステムタイマによる割り込みがあった。
［条件２］あるプロセッサから、過負荷になりそうだという通知があった。
［条件３］アイドル状態にあるプロセッサからの割り込みがあった。
［条件４］あるプロセッサが入出力命令を発行したことにより、入出力命令の実行完了待ち状態に入ったという通知があった。
［条件５］あるプロセッサから、一つのタスクの実行を終了したという通知があった。
ただし、これらの条件１〜５はあくまで例であり、この限りではない。
【０１０８】
（プログラムモジュール複合体）
次に、本発明の他の実施形態を説明する。
これまでの説明では、本実施形態のヘテロマルチプロセッサシステムが実行すべきプログラムとして、タスクとタスク間の依存関係で記述されたプログラムであって、しかも例えば図１０に示したように各タスクが特定のプロセッサ用の命令セットで記述されたプログラムモジュールのみで構成されている例について説明した。
【０１０９】
ヘテロマルチプロセッサシステムが実行対象とするプログラムは、それを構成する全タスクが一つのプログラムモジュールとして与えられている必要は必ずしもない。プログラムを構成する全タスクのうち、少なくとも一つのタスクは、二つ以上の異種プロセッサがそれぞれ有する命令セットによって記述された複数のプログラムモジュールを含む複合体（これをプログラムモジュール複合体という）であってもよい。
【０１１０】
例えば、図２２（ａ）に示すプログラムモジュール複合体４０Ａは、命令セットＡ，Ｂ，Ｃでそれぞれ記述されているプログラムモジュール４１，４２，４３を含んでいる。図２２（ｂ）に示すプログラムモジュール複合体４０Ｂは、命令セットＡ，Ｂでそれぞれ記述されているプログラムモジュール４１，４２を含んでいる。
【０１１１】
プログラムを構成する各タスクは、例えばタスクの内容やタスクの作成者の意図に応じて図２２（ａ）（ｂ）に示されるようにいずれかのプログラムモジュール複合体として与えられるか、あるいは図２２（ｃ）に示されるように一つのプログラムモジュール４１のみとして与えられる。
【０１１２】
プログラムを構成する全タスクが、共通の複数の命令セットでそれぞれ記述されている複数のプログラムモジュールを含むプログラムモジュール複合体として与えられてもよい。すなわち、プログラムを構成する全タスクが、いずれも例えば図２２（ａ）のようなプログラムモジュール複合体であってもよい。
【０１１３】
上述のようなプログラムモジュール複合体という構造をタスクに適用した場合には、図１５の処理により割り付け先変更の対象となるタスクを選定して割り付け先プロセッサを変更するかどうかの判定を行う際に、前述した実行効率判定基準の他に「割り付け先プロセッサの命令セットで記述されたプログラムモジュールが、当該タスクのプログラムモジュール複合体の中に存在する」という判定基準を設けて、これを必ず満たさなければならない基準とすることが望ましい。これは、割り付け変更先候補プロセッサの命令セットで記述されたプログラムモジュールがプログラムモジュール複合体の中に存在しない限り、割り付け先を変更しても変更された割り付け先プロセッサ上で当該タスクを実行することはできないからである。
【０１１４】
次に、プログラムを構成する少なくとも一部のタスクが上述したプログラムモジュール複合体である場合の図１３のステップＳ１１及びＳ３１の処理について説明する。
図２３は、図１３中のステップＳ１１の本実施形態に対応する処理の詳細を示す。割り付けるべき対象タスクのプログラムモジュール複合体中のプログラムモジュールを記述している命令セットが何であるかを判断し（ステップＳ１１１）、その命令セットを有するプロセッサに対して対象タスクを割り付ける（ステップＳ１１２）。
【０１１５】
次に、図２４〜図２６を用いて図１３中のステップＳ１３の本実施形態に対応する処理手順の種々の例について述べる。
図２４の処理手順では、まず図１３中のステップＳ１２で決定された割り付け先プロセッサは、対象タスクのプログラムモジュール複合体に含まれるプログラムモジュールの命令セットのいずれかを用いるプロセッサであるかどうかを判定する（ステップＳ３１１）。ステップＳ３１１の判定の結果がＹＥＳであれば、そのプログラムモジュール複合体から当該命令セットで記述されたプログラムモジュールを取得する（ステップＳ３１２）。
【０１１６】
一方、ステップＳ３１１の判定の結果がＮＯであれば、対象タスクのプログラムモジュール複合体に含まれる任意の一つのプログラムモジュールを選択する（ステップＳ３１３）。次いで、図１７中のステップＳ３０２と同様に、ステップＳ３１３で選択された命令セットで記述されたタスクのプログラムモジュール中の命令を、割り付け先プロセッサ用の当該命令と同一処理を行う命令に置換することによって、割り付け先プロセッサ用のプログラムモジュールを生成する（ステップＳ３１４）。
【０１１７】
図２５の処理手順では、ステップＳ３２１〜Ｓ３２３の処理については図２４中のステップＳ３１１〜Ｓ３１２と全く同様であり、ステップＳ３２４の処理だけが異なっている。ステップＳ３２１の判定の結果がＮＯの場合には、対象タスクのプログラムモジュール複合体に含まれる任意の一つのプログラムモジュールをステップＳ３２３で選択する。
【０１１８】
次に、図１８に示した処理と同様に、ステップＳ３２３で選択されたプログラムモジュールのソースコードから、変更された割り付け先プロセッサが有する命令セットで記述されたプログラムモジュールを生成することのできるコンパイラを用いて、変更された割り付け先プロセッサが有する命令セットで記述されたプログラムモジュールを生成する。
【０１１９】
図２６の処理手順では、ステップＳ３３１，Ｓ３３３の処理については図２４中のステップＳ３１１，Ｓ３１２と全く同様であり、ステップＳ３３４の処理だけが異なっている。すなわち、ステップＳ３３１の判定結果がＮＯの場合にはステップＳ３３４に移り、割り付け先プロセッサが有する命令セットで記述された、当該タスクのプログラムモジュールをファイルシステム中から、もしくはネットワークから検索して取得する。
このように、プログラムを構成するタスクがプログラムモジュール複合体で構成される場合にも、本発明によるタスク割り付けは有効である。
【０１２０】
【発明の効果】
以上説明したように、本発明によれば命令セットが異なる複数のプロセッサから構成されるヘテロなマルチプロセッサシステムにおいて、記述に用いられている命令セットが異なる複数のタスク群を実行する際に、よりプログラムの実行効率が向上するような、命令セットの異なるプロセッサヘの割り付け先の変更を実現することが可能となり、それによってシステム全体の実行効率を大きく改善することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係るマルチプロセッサシステムの構成を示すブロック図
【図２】同実施形態におけるタスク割り付けプログラムの第１の実装例を示す図
【図３】同実施形態におけるタスク割り付けプログラムの第２の実装例を示す図
【図４】同実施形態におけるタスク割り付けプログラムの第３の実装例を示す図
【図５】同実施形態におけるタスク割り付けプログラムの第４の実装例を示す図
【図６】マルチプロセッサシステムで実行されるタスクとタスク間の依存関係で記述されたプログラムの例を示す図
【図７】タスクの実行の様子の種々の例を示す図
【図８】同実施形態におけるタスク割り付けシステムの機能的構成を示すブロック図
【図９】図９中の最適化実行判定部２５の詳細な構成を示すブロック図
【図１０】異なる複数の命令セットで記述されたプログラムモジュールで構成されるタスクとタスク間の依存関係で記述されたプログラムの例を示す図
【図１１】
図１０のプログラムをプログラムモジュールの記述に用いられている命令セットを基準として各プロセッサに割り付けた例を示す図
【図１２】図１１の割り付け例を仮割り付けとして本実施形態に従って割り付け先を変更した後の割り付け例を示す図
【図１３】同実施形態におけるタスク割り付け処理の一例を示すフローチャート
【図１４】図１３中の仮割り付け処理の一例を示すフローチャート
【図１５】図１３中の判定処理の一例を示すフローチャート
【図１６】図１５の判定処理の前処理の一例を示す図
【図１７】図１３中の割り付け先プロセッサ変更処理の一例を示すフローチャート
【図１８】図１３中の割り付け先プロセッサ変更処理の他の例を示すフローチャート
【図１９】図１３中の割り付け先プロセッサ変更処理の別の例を示すフローチャート
【図２０】同実施形態におけるタスク割り付け処理の他の例を示すフローチャート
【図２１】同実施形態におけるタスク割り付け処理の別の例を示すフローチャート
【図２２】本発明の他の実施形態におけるタスク割り付け処理に関わるモジュール複合体についての説明図
【図２３】同実施形態における仮割り付け処理の一例を示すフローチャート
【図２４】同実施形態における割り付け先プロセッサ変更処理の一例を示すフローチャート
【図２５】同実施形態における割り付け先プロセッサ変更処理の他の例を示すフローチャート
【図２６】同実施形態における割り付け先プロセッサ変更処理の別の例を示すフローチャート
【符号の説明】
１〜３…プロセッサ
４…共有メモリ
５…入出力制御装置
６…ディスク装置
７…プロセッサ間結合装置
８…タスク割り付けシステム
９…管理用プロセッサ
１１，１３…オペレーティングシステム
１２…タスク割り付けプログラム
【図１】
2004171234.tif 000003
【図２】
2004171234.tif 000004
【図３】
2004171234.tif 000005
【図４】
2004171234.tif 000006
【図５】
2004171234.tif 000007
【図６】
2004171234.tif 000008
【図７】
2004171234.tif 000009
【図８】
2004171234.tif 000010
【図９】
2004171234.tif 000011
【図１０】
2004171234.tif 000012
【図１１】
2004171234.tif 000013
【図１２】
2004171234.tif 000014
【図１３】
2004171234.tif 000015
【図１４】
2004171234.tif 000016
【図１５】
2004171234.tif 000017
【図１６】
2004171234.tif 000018
【図１７】
2004171234.tif 000019
【図１８】
2004171234.tif 000020
【図１９】
2004171234.tif 000021
【図２０】
2004171234.tif 000022
【図２１】
2004171234.tif 000023
【図２２】
2004171234.tif 000024
【図２３】
2004171234.tif 000025
【図２４】
2004171234.tif 000026
【図２５】
2004171234.tif 000027
【図２６】
2004171234.tif 000028