(57)【要約】【課題】本発明は、複数の演算処理を効率良く実行させることができる情報処理装置を提供することを課題とする。【解決手段】演算装置を備え、複数の演算処理を行う情報処理装置であって、演算装置において動作している第２の演算処理を中断して第１の演算処理に切り替えるか否かを、第２の演算処理から第１の演算処理に切り替えることによって生じるコストに基づいて判定することを特徴とし、特に、第１の演算装置と第２の演算装置を備える場合、第１の演算装置において動作している第１の演算処理を中断して第１の演算装置を開放する場合、第２の演算装置において動作している第２の演算処理を中断して第１の演算処理に切り替えるか否かを、第２の演算処理から第１の演算処理に切り替えることによって生じるコストに基づいて判定する。【選択図】図５
2010205046.tif 000002
【特許請求の範囲】
【請求項１】
演算装置を備え、複数の演算処理を行う情報処理装置であって、
前記演算装置において動作している第２の演算処理を中断して第１の演算処理に切り替えるか否かを、第２の演算処理から第１の演算処理に切り替えることによって生じるコストに基づいて判定することを特徴とする情報処理装置。
【請求項２】
前記演算装置は、第１の演算装置と第２の演算装置を備え、
前記第１の演算装置において動作している第１の演算処理を中断して第１の演算装置を開放した場合、前記第２の演算装置において動作している第２の演算処理を中断して第１の演算処理に切り替えるか否かを、第２の演算処理から第１の演算処理に切り替えることによって生じるコストに基づいて判定することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
各演算処理は、固有の実行優先度をそれぞれ有し、
第１の演算処理の実行優先度に演算処理を切り替えることによって生じるコストを加味した優先度と第２の演算処理の実行優先度に演算処理を切り替えることによって生じるコストを加味した優先度とを比較することにより、演算装置において演算処理を切り替えるか否かを判定することを特徴とする請求項１又は請求項２に記載の情報処理装置。
【請求項４】
演算処理を切り替えることによって生じるコストは、演算処理が動作していた時間から推測されるキャッシュメモリのヒット率に基づいて設定されることを特徴とする請求項１〜請求項３のいずれか１項に記載の情報処理装置。
【請求項５】
演算処理を切り替えることによって生じるコストは、演算処理が動作していた時間から算出される演算処理終了までの予測時間に基づいて設定されることを特徴とする請求項１〜請求項４のいずれか１項に記載の情報処理装置。
【請求項６】
演算処理を切り替えることによって生じるコストは、演算処理終了まで第１の演算処理を動作させた場合でも第２の演算処理に規定されている目標処理終了時間までに第２の演算処理を終了させることができるか否かによって設定されることを特徴とする請求項１〜請求項５のいずれか１項に記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の演算処理を行う情報処理装置に関する。
【背景技術】
【０００２】
マルチタスクの情報処理装置では、複数のタスクについてのスケジューリングを行い、そのスケジューリングした順序で複数のタスクを実行する。特許文献１には、優先度情報に基づいて複数のタスクのスケジューリングを行い、優先度の高いタスクから順に実行する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−２４９３５７号公報
【特許文献２】特開平８−８３２５７号公報
【特許文献３】特開平６−２５９３８６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記のように優先度に基づいて複数のタスクを実行させる場合、高優先度のタスクが途中で追加されると、実行中の低優先度のタスクを中断して待機状態とし、高優先度のタスクを実行する。この際、低優先度のタスクがほぼ終了している場合や低優先度のタスクのキャッシュメモリのヒット率が高い場合、その低優先度のタスクを待機状態にすることによりかえって全体の処理効率が低下する。このような場合、低優先度のタスクが終了してから高優先度のタスクを実行させたほうがよい。
【０００５】
そこで、本発明は、複数の演算処理を効率良く実行させることができる情報処理装置を提供することを課題とする。
【課題を解決するための手段】
【０００６】
本発明に係る情報処理装置は、演算装置を備え、複数の演算処理を行う情報処理装置であって、演算装置において動作している第２の演算処理を中断して第１の演算処理に切り替えるか否かを、第２の演算処理から第１の演算処理に切り替えることによって生じるコストに基づいて判定することを特徴とする。
【０００７】
この情報処理装置は、少なくとも１つの演算装置を備えており、この演算装置で複数の演算処理を実行する。特に、情報処理装置では、演算装置において第２の演算処理が動作しているときに第１の演算処理が動作可能状態になった場合、演算装置で第２の演算処理の動作を継続させるかあるいは第２の演算処理を中断して第１の演算処理を動作させるかを判断する。その際、情報処理装置では、第２の演算処理から第１の演算処理に切り替えることによって生じるコストに基づいて第１の演算処理に切り替えるか否かを判定する。このように、情報処理装置では、演算処理を切り替えによるコストを導入することにより、効率の悪い演算処理の切り替えを回避でき、複数の演算処理を効率良く実行させることができる。これによって、演算処理の切り替えのオーバヘッドによる性能低下（処理遅延など）や動作中の演算処理のキャッシュメモリの無駄（ヒット率の低下）などを防止できる。
【０００８】
なお、演算装置は、演算処理を実行する装置であり、例えば、ＣＰＵ、プロセッサ、コアがある。演算処理は、処理実行単位を表わす概念であり、例えば、タスク、プロセス、スレッドがある。コストとしては、例えば、動作中の演算処理の動作経過時間、処理終了までの残時間、キャッシュメモリのヒット率、演算処理の動作予測時間がある。特に、複数の演算装置で複数の演算処理を行う場合、マイグレーション（演算処理の動作する演算装置が変更されること）が発生するときがあるので、コストとしては、マイグレーションの有無などもある。
【０００９】
本発明の上記情報処理装置では、演算装置は、第１の演算装置と第２の演算装置を備え、第１の演算装置において動作している第１の演算処理を中断して第１の演算装置を開放した場合、前記第２の演算装置において動作している第２の演算処理を中断して第１の演算処理に切り替えるか否かを、第２の演算処理から第１の演算処理に切り替えることによって生じるコストに基づいて判定する構成としてもよい。
【００１０】
この情報処理装置は、少なくとも２つの演算装置を備えおり、この複数の演算装置で複数の演算処理を実行する。特に、情報処理装置では、第１の演算装置において第１の演算処理が動作しかつ第２の演算装置において第２の演算処理が動作しているときに第１の演算装置における第１の演算処理を中断した場合（例えば、第３の演算処理を第１の演算装置で動作させる場合）、第２の演算装置で第２の演算処理の動作を継続させるかあるいは第２の演算処理を中断して第１の演算処理を動作させるかを判断する。その際、情報処理装置では、第２の演算装置において第２の演算処理から第１の演算処理に切り替えることによって生じるコスト（例えば、マイグレーションの有無、第２の演算装置における第２の演算処理の動作経過時間、処理終了までの残時間、キャッシュメモリのヒット率、第１の演算処理の第１の演算処理の動作経過時間、キャッシュメモリのヒット率）に基づいて第１の演算処理に切り替えるか否かを判定する。このように、情報処理装置では、各演算装置における演算処理を切り替えによるコストを導入することにより、複数の演算装置の環境下において複数の演算処理を効率良く実行させることができる。これによって、複数の演算装置を備える環境下で、効率が低下するようなマイグレーションの発生を抑制することができる。
【００１１】
本発明の上記情報処理装置では、各演算処理は、固有の実行優先度をそれぞれ有し、第１の演算処理の実行優先度に演算処理を切り替えることによって生じるコストを加味した優先度と第２の演算処理の実行優先度に演算処理を切り替えることによって生じるコストを加味した優先度とを比較することにより、演算装置において演算処理を切り替えるか否かを判定すると好適である。
【００１２】
この情報処理装置では、各演算処理が実行優先度をそれぞれ有している。そして、情報処理装置では、演算装置で第２の演算処理の動作を継続させるかあるいは第２の演算処理を中断して第１の演算処理を動作させるかを判断する場合、第１の演算処理の実行優先度に演算処理を切り替えることによって生じるコストを加味した優先度を算出するとともに第２の演算処理の実行優先度に演算処理を切り替えることによって生じるコストを加味した優先度を算出し、この実行優先度にコストを加味した優先度を比較することによって第１の演算処理に切り替えるか否かを判定する。このように、情報処理装置では、演算処理の実行優先度に演算処理を切り替えによるコストを加味することにより、演算処理個々の実行優先度と演算処理を切り替えによる効率低下の抑制との両立を図ることができる。
【００１３】
本発明の上記情報処理装置では、演算処理を切り替えることによって生じるコストは、演算処理が動作していた時間から推測されるキャッシュメモリのヒット率に基づいて設定される。
【００１４】
一般に、演算処理が動作している時間が長いほど、その演算処理によるキャッシュメモリのヒット率が高くなる。そこで、この情報処理装置では、演算処理が動作していた時間からキャッシュメモリのヒット率を推測し、そのキャッシュメモリのヒット率に基づいて演算処理を切り替えることによって生じるコストを設定することにより、キャッシュメモリのヒット率を精度良く推測でき、キャッシュメモリのヒット率に基づくコストよって動作中の演算処理を継続させたほうがよいか否かを判定できる。演算処理を中断するとキャッシュメモリの一部あるいは全部が無駄になり、キャッシュメモリのヒット率が高い場合には演算処理を継続させたほうが効率が良い。
【００１５】
本発明の上記情報処理装置では、演算処理を切り替えることによって生じるコストは、演算処理が動作していた時間から算出される演算処理終了までの予測時間に基づいて設定される。
【００１６】
演算処理が動作している時間が長いほど、その演算処理が終了するまでに要する時間が短くなる。そこで、この情報処理装置では、演算処理が動作していた時間から演算処理終了までに要する予測時間を算出し、その予測時間に基づいて演算処理を切り替えることによって生じるコストを設定することにより、演算処理終了までに要する時間を精度良く予測でき、その予測時間に基づくコストよって動作中の演算処理を継続させたほうがよいか否かを判定できる。演算処理の切り替えのオーバヘッドによって処理遅延が発生するので、演算処理終了までに要する時間が短い場合には演算処理を継続させたほうが効率が良い。
【００１７】
本発明の上記情報処理装置では、演算処理を切り替えることによって生じるコストは、演算処理終了まで第１の演算処理を動作させた場合でも第２の演算処理に規定されている目標処理終了時間までに第２の演算処理を終了させることができるか否かによって設定される。
【００１８】
この情報処理装置では、第２の演算処理の目標処理終了時間が規定されており、第２の演算処理を目標処理終了時間までに終了させる必要がある。情報処理装置では、演算装置において第２の演算処理が動作しているときに第１の演算処理が動作可能状態になった場合あるいは第１の演算処理が動作しているときに第２の演算処理が動作可能状態になった場合、第１の演算処理を動作開始（このとき、第２の演算処理は中断）あるいは動作継続（このとき、第２の演算処理は動作可能状態のまま待機）させて動作終了するまで動作させた後に第２の演算処理を再開あるいは動作開始しても、第２の演算処理を目標処理終了時間までに終了させることができるか否かを判定し、その判定結果に基づいて演算処理を切り替えることによって生じるコストを設定することにより、複数の演算処理を効率的に動作させることできる。
【発明の効果】
【００１９】
本発明は、演算処理を切り替えによるコストを導入することにより、効率の悪い演算処理の切り替えを回避でき、複数の演算処理を効率良く実行させることができる。
【図面の簡単な説明】
【００２０】
【図１】本実施の形態に係るマルチコアプロセッサの構成図である。
【図２】本実施の形態に係るタスク情報を示す図である。
【図３】本実施の形態に係るタスクのスケジューリングの一例である。
【図４】従来のタスクのスケジューリングの一例である。
【図５】本実施の形態に係るタスクのスケジューリング処理の流れを示すフローチャートである。
【図６】本実施の形態に係るマイグレーションコスト算出処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面を参照して、本発明に係る情報処理装置の実施の形態を説明する。
【００２２】
本実施の形態では、本発明に係る情報処理装置を、マルチコアプロセッサに適用する。本実施の形態に係るマルチコアプロセッサは、演算装置として２つのコアを備えるデュアルコアプロセッサであり、演算処理として複数のタスクを動作させるマルチタスクプロセッサである。
【００２３】
図１及び図２を参照して、本実施の形態に係るマルチコアプロセッサ１について説明する。図１は、本実施の形態に係るマルチコアプロセッサの構成図である。図２は、本実施の形態に係るタスク情報を示す図である。
【００２４】
マルチコアプロセッサ１は、第０コア１０及び第１コア１１を備えており、メインメモリ２０を共有する。マルチコアプロセッサ１では、リアルタイムＯＳであり、動作可能状態となったタスクを第０コア１０あるいは第１コア１１で動作させる。特に、第０コア１０と第１コア１１でタスク動作中に新たなタスクが動作可能状態（Ｒｅａｄｙ状態）になった場合、マルチコアプロセッサ１では、新たなタスクを含めたタスクのスケジューリングを行い、第０コア１０と第１コア１１で動作させるタスクを決定する。このスケジューリングは、第０コア１０と第１コア１１のうちタスクの動作可能状態を通知されたコアで行われる。
【００２５】
コア１０，１１は、最小限の実行ユニットであり、ＣＰＵと専用のキャッシュメモリを備えている。コア１０，１１では、各タスクを実行し、タスク動作中のデータをキャッシュメモリに格納する。また、コア１０，１１では、タスクが動作可能状態であることが通知されると、スケジューラとして機能する。なお、各コア１０，１１は処理能力（ビット幅、クロック周波数など）やキャッシュ容量などが異なっているので、タスクによっては動作可能なコアが限定される場合がある。
【００２６】
タスクは、ＯＳから見た実行単位であり、スタートからエンドが決まっているプログラムからなる。タスク情報は、図２に示すように、実行優先度、平均動作時間、動作経過時間、動作可能コア、前回動作コアなどがあり、タスク毎にメインメモリ２０に格納されている。実行優先度は、タスク固有の実行優先度であり、予め設定されている。ここでは、実行優先度は、値が小さいほど優先度が高い。平均動作時間は、タスクの動作履歴から求められる平均の動作時間であり、タスクを動作させたコアで算出される。動作経過時間は、動作可能状態後に実行リソースをアサイン（＝ＲＵＮ状態）にされてからの経過時間であり、タスクを動作させているコアで計測される。動作可能コアは、タスクが動作可能なコアの番号であり、予め決まっている。前回動作コアは、タスクが前回動作したコアの番号であり、タスクを前回動作させたコアで設定される。
【００２７】
スケジューラ（コア１０，１１）では、他のプロセッサなどからタスクが動作可能状態になったことの通知を受信すると、そのタスクを含めたスケジューリングを行う。第０コア１０及び第１コア１１で動作中のタスクがない場合、動作可能状態のタスクが任意のコアで動作可能なときには第０コア１０又は第１コア１１で動作させ、動作可能状態のタスクが動作可能なコアが限定されているときにはそのコアで動作させる。第０コア１０と第１コア１１の一方で動作中のタスクがある場合、動作可能状態のタスクが任意のコアで動作可能なときには非動作中のコアで動作させ、動作可能状態のタスクが動作可能なコアが限定されているときには非動作中のコアがそのコアに該当する場合にはそのコアで動作させ、動作中のコアがそのコアに該当する場合にはそのコアを対象としてスケジューリング選択を行う。第０コア１０と第１コア１１の両方で動作中のタスクがある場合、動作可能状態のタスクが任意のコアで動作可能なときには第０コア１０からスケジューリング処理を行い、動作可能状態のタスクが動作可能なコアが限定されているときにはその限定されているコアからスケジューリング処理を行う。このコアにおけるスケジューリング処理において動作可能状態のコアが動作させるタスクと決定した場合、そのコアで動作中であったタスクが動作可能状態のタスクとなるので、他方のコアにおけるスケジューリング処理を行う。
【００２８】
スケジューリング処理について説明する。まず、スケジューリング処理の対象のコアにおいて現在動作中のタスクの実行優先度と動作可能状態のタスクの実行優先度を読み出す。そして、現在動作中のタスクについてのマイグレーションコストを算出し、現在動作中のタスクについての実行優先度にマイグレーションコストを加算した優先度を算出する。また、動作可能状態のタスクについてのマイグレーションコストを算出し、動作可能状態のタスクについての実行優先度にマイグレーションコストを加算した優先度を算出する。マイグレーションコストは、コアでタスクが切り替わることによって生じるコスト（タスクを切り替えたほうが良いか否かを判断するための指標）であり、タスクの切り替えによるマイグレーションも考慮したコストである。
【００２９】
マイグレーションコストの算出では、パラメータとしてマイグレーションの発生の有無、タスクの動作経過時間、現在動作中のタスクの動作終了までの残時間、動作可能状態のタスクの動作予測時間などを用いる。
【００３０】
マイグレーションが発生する場合、現在動作中のタスクのキャッシュメモリを有効に利用できなかったり、タスク切り替えのオーバヘッドによる性能低下（例えば、処理遅延）などがあるので、マイグレーションが発生するタスクの優先度を下げる。具体的には、マイグレーションが発生するか否かを判定し、マイグレーションが発生する場合にはそのマイグレーションが発生するタスクについてプラス値のコスト（例えば、＋１）を加算する。
【００３１】
現在動作中のタスクの動作経過時間が長くなるほど、そのタスクのキャッシュメモリのヒット率が高くなると推測できるので、そのキャッシュメモリを有効に利用するために、動作経過時間が長くなっているタスクの優先度を上げる。具体的には、現在動作中のタスクの動作経過時間を読み出し、この動作経過時間が動作経過時間閾値以上か否かは判定し、動作経過時間が動作経過時間閾値以上の場合には現在動作中のタスクについてマイナス値のコスト（例えば、−１）を加算する。なお、この動作経過時間閾値は、実験やシミュレーションなどによって予め設定される。動作経過時間閾値は、全てのタスクやコアに対して同じ値でもよいし、あるいは、タスク毎やコア毎に設定されてもよい。
【００３２】
動作可能状態のタスク（他方のコアでの動作を中断したタスク）が他方のコアで途中まで動作していた場合、その他方のコアのキャッシュメモリに動作可能状態のタスクのデータが残っている可能性がある。そこで、動作可能状態のタスクの動作経過時間が長くなるほど、そのタスクの他方のコアでのキャッシュメモリのヒット率が高くなると推測できるので、他方のコアでのキャッシュメモリを有効に利用するために（他方のコアでの動作を再開させるために）、他方のコアでの動作経過時間が長かったタスクの優先度を下げる。具体的には、動作可能状態のタスクの前回動作コアでの動作経過時間を読み出し、この動作経過時間が動作経過時間閾値以上か否かは判定し、動作経過時間が動作経過時間閾値以上の場合には動作可能状態のタスクについてプラス値のコスト（例えば、＋１）を加算する。なお、この動作経過時間閾値は、上記の現在動作中のタスクについての動作経過時間閾値と同一の値であってもよいし、他方のコアで動作可能状態のキャッシュメモリが書き換えられている場合もあるので上記の現在動作中のタスクについての動作経過時間閾値よりも大きな値としてもよい。
【００３３】
現在動作中のタスクの動作終了までの残時間が短い場合、タスク切り替えのオーバヘッドによる処理遅延などを考えると、そのタスクを一旦中断して待機状態にするよりもそのまま最後まで動作を継続させたほうがよいので、残時間が短くなっているタスクの優先度を上げる。具体的には、現在動作中のタスクの動作経過時間及び平均動作時間を読み出し、（平均動作時間−動作経過時間）＝残時間が残時間閾値以下か否かは判定し、残時間が残時間閾値以下の場合には現在動作中のタスクについてマイナス値のコスト（例えば、−１）を加算する。この残時間閾値は、実験やシミュレーションなどによって予め設定される。残時間閾値は、全てのタスクやコアに対して同じ値でもよいし、あるいは、タスク毎やコア毎に設定されてもよい。
【００３４】
動作可能状態のタスクの動作予測時間の長短によって、現在動作中のタスクをそのまま動作させたほうがよいのかあるいは動作可能状態のタスクを割り込ませたほうがよいのかの判断基準が変わる。そこで、動作可能状態のタスクの動作予測時間によってタスクの優先度を上げたりあるいは下げたりする。ちなみに、周期タスクの場合、一般的に高優先で動作させるが、周期的に動作するので動作経過時間の予測もつきやすい。
【００３５】
図３に、マルチコアプロセッサ１におけるスケジューリングの一例を示す。この例では、第０コア１０でタスクＡが動作中（動作経過時間は動作経過時間閾値より短いとする）であり、第１コア１１でタスクＢが動作中（動作経過時間は動作経過時間閾値より長いとする）のときに、タスクＣが動作可能状態になった場合である。動作可能コアは、タスクＡ、タスクＢが任意のコア（第０コア１０、第１コア１１）であり、タスクＣが特定コア（第０コア１０のみ）である。実行優先度は、タスクＡが１０であり、タスクＢが１１であり、タスクＣが９であり、タスクＣ、タスクＡ，タスクＢの順で優先度が高い。ここでは、説明を簡単化するために、マイグレーションコストについてはマイグレーションの有無と動作経過時間についてのみ考え、コストの大きさについては１単位で考える。
【００３６】
タスクＣが動作可能状態になったと通知された場合、タスクＣは第０コア１０でのみ動作可能であるので、動作可能状態のタスクＣと現在動作中のタスクＡについての第０コア１０でのスケジューリング処理を行う。新たに動作可能状態になったタスクＣは、第０コア１０でのみ動作するので、マイグレーションが発生しない。また、タスクＣは、新たに動作するので、他方のコアでの前回の動作経過時間もない。したがって、タスクＣについては、マイグレーションコストが０であり、実行優先度の９がそのまま優先度となる。一方、第０コア１０で現在動作中のタスクＡは、第０コア１０で動作中であるので、マイグレーションが発生しない。また、タスクＡは、第０コア１０での動作経過時間が動作経過時間閾値未満である。したがって、タスクＡについては、マイグレーションコストが０であり、実行優先度の１０がそのまま優先度となる。このタスクＣの優先度８とタスクＡの優先度１０とを比較すると、タスクＣの優先度９のほうが小さいので、第０コア１０ではタスクＣを動作させると決定する。
【００３７】
第０コア１０で動作していたタスクＡと現在動作中のタスクＢについての第１コア１１でのスケジューリング処理を行う。動作可能状態になったタスクＡは、第１コア１１で動作させると仮定した場合には第０コア１０から第１コア１１へのマイグレーションが発生する。また、タスクＡは、第０コア１０で動作していたが、他方のコア（第０コア１０）での前回の動作経過時間が動作経過時間閾値未満である。したがって、タスクＡについては、マイグレーションコストがマイグレーションの発生よる＋１であり、実行優先度の１０からマイグレーションコストを１加算して優先度が１１となる。一方、第１コア１１で現在動作中のタスクＢは、第１コア１１で動作中であるので、マイグレーションが発生しない。また、タスクＢは、第１コア１１での動作経過時間が動作経過時間閾値以上なので、マイグレーションコストとして１減算される。したがって、タスクＢについては、マイグレーションコストが動作経過時間が動作経過時間閾値以上による−１であり、実行優先度の１１からマイグレーションコストを１減算して優先度が１０となる。このタスクＡの優先度１１とタスクＢの優先度１０とを比較すると、タスクＢの優先度１０のほうが小さいので、第１コア１１ではタスクＢを動作させると決定する。
【００３８】
タスクＡは、一旦待機状態となるが、第０コア１０でのタスクＣの動作が終了すると、第０コア１０で中断途中から動作を再開する。このように、この図３に示す例の場合、状態の遷移するタスクはタスクＡだけであり、マイグレーションも発生しない。タスクＡは、一時的に待機状態となるが第０コア１０で動作を再開することにより、第０コア１０で元々動作していたので、第０コア１０での前回の動作でキャッシュメモリに格納されたデータ（タスクＣでの動作によって書き換えが行われないで残っているデータ）をそのまま有効に利用することができる。
【００３９】
図４には、図３の例と同様の場合において、実行優先度のみに基づく従来のスケジューリングを示す。タスクＣが動作可能状態になったと通知された場合、タスクＣは第０コア１０でのみ動作可能であるので、動作可能状態のタスクＣと現在動作中のタスクＡについての第０コア１０でのスケジューリング処理を行う。タスクＣの優先度９とタスクＡの優先度１０とを比較すると、タスクＣの優先度９のほうが小さいので、第０コア１０ではタスクＣを動作させると決定する。次に、第０コア１０で動作していたタスクＡと現在動作中のタスクＢについての第１コア１１でのスケジューリング処理を行う。タスクＡの優先度１０とタスクＢの優先度１１とを比較すると、タスクＡの優先度１０のほうが小さいので、第１コア１１ではタスクＡを動作させると決定する。ここで、タスクＡにマイグレーションが発生し、第１コア１１で動作していたタスクＢは一旦待機状態となる。このように、実行優先度だけでスケジューリングを行った場合、状態の遷移するタスクはタスクＡとタスクＢの両方であり、マイグレーションも発生する。さらに、タスクＡの第０コア１０でのキャッシュメモリに格納されたデータも、全て無効となる。
【００４０】
図１及び図２を参照し、マルチコアプロセッサ１におけるスケジューリング処理の流れについて説明する。スケジューラにおけるスケジューリング処理を図５のフローチャートに沿って説明し、マイグレーションコスト算出処理を図６のフローチャートに沿って説明する。図５は、本実施の形態に係るタスクのスケジューリング処理の流れを示すフローチャートである。図６は、本実施の形態に係るマイグレーションコスト算出処理の流れを示すフローチャートである。ここでは、説明を簡単化するために、マイグレーションコストについてはマイグレーションの有無と動作経過時間についてのみ考え、コストの大きさについては１単位で考える。また、具体例として、図３の例に沿って説明する。
【００４１】
第０コア１０と第１コア１１のいずれかのコアにおいて新たなタスクが動作可能状態になったと通知を受けると、そのコア（スケジューラ）では、各コア１０，１１についてのスケジューリング処理を行う。動作可能状態になったタスクの動作可能コアの情報に基づいて、スケジューリング処理を最初に行う対象コアを決定する。図３の例では、新たに動作可能状態になったタスクＣは第０コア１０でのみ動作可能であるので、第０コア１０からスケジューリング処理を行う。
【００４２】
まず、スケジューリング処理を行う対象コア（第０コア１０）で動作可能なタスク（動作候補タスク）が有るか否かを判定する（Ｓ１０）。Ｓ１０にて対象コアで動作候補タスクが無いと判定した場合、この対象コアでのスケジューリング処理を終了する。一方、Ｓ１０にて対象コアで動作候補タスクが有ると判定した場合、マイグレーションコスト算出処理を行う（Ｓ１１）。図３の例では、新たに動作可能状態となったタスクＣが動作候補タスクであり、第０コア１０での動作候補タスクが有ると判定される。
【００４３】
マイグレーションコスト算出処理では、まず、対象コア（第０コア１０）での動作候補タスク（タスクＣ）にマイグレーションが発生するか否かを判定する（Ｓ２０）。Ｓ２０にて動作候補タスクにマイグレーションが発生すると判定した場合、動作候補タスクのマイグレーションコストを１加算する（Ｓ２１）。図３の例では、タスクＣにはマイグレーションが発生しないので、タスクＣのマイグレーションコストは０のままである。
【００４４】
次に、対象コア（第０コア１０）で現在動作中のタスク（タスクＡ）の動作経過時間が動作経過時間閾値以上か否かを判定する（Ｓ２２）。Ｓ２２にて対象コアで現在動作中のタスクの動作経過時間が動作経過時間閾値以上と判定した場合、対象コアで現在動作中のタスクのマイグレーションコストを１減算する（Ｓ２３）。図３の例では、第０コア１０で動作中のタスクＡの動作経過時間が動作経過時間閾値未満なので、タスクＡのマイグレーションコストは０のままである。
【００４５】
次に、動作候補タスク（タスクＣ）の他方のコア（第１コア１１）での前回の動作経過時間が動作経過時間閾値以上か否かを判定する（Ｓ２４）。Ｓ２４にて動作候補タスクの前回の動作経過時間が動作経過時間閾値以上と判定した場合、動作候補タスクのマイグレーションコストを１加算する（Ｓ２５）。図３の例では、タスクＣの前回の動作経過時間が動作経過時間閾値未満なので、タスクＣのマイグレーションコストは０のままである。
【００４６】
対象コア（第０コア１０）での動作候補タスク（タスクＣ）の実行優先度に算出したマイグレーションコストを加算した優先度と対象コア（第０コア１０）で現在動作中のタスク（タスクＡ）の実行優先度に算出したマイグレーションコストを加算した優先度とを比較する（Ｓ１２）。Ｓ１２の比較で動作候補タスクの優先度が現在動作中のタスクの優先度より高いと判定した場合、動作候補タスクを対象コアの動作タスクと決定し（Ｓ１３）、動作候補タスクの動作を開始する。一方、Ｓ１２の比較で現在動作中タスクの優先度が動作候補タスクの優先度より高いと判定した場合、現在動作中タスクを対象コアの動作タスクと決定し（Ｓ１４）、現在動作中タスクの動作を継続する。図３の例では、タスクＣについては実行優先度９がそのまま優先度となり、タスクＡについては実行優先度１０がそのまま優先度となり、タスクＣの実行優先度９とタスクＡの優先度１０を比較し、タスクＣのほうが優先度が高いと判定され、第０コア１０での動作タスクがタスクＣとなる。
【００４７】
次に、他方のコアを、スケジューリング処理を行う対象コアとする。図３の例では、第０コア１０のスケジューリング処理が終了したので、第１コア１１のスケジューリング処理を行う。まず、次の対象コア（第１コア１１）で動作候補タスクが有るか否かを判定する（Ｓ１０）。上記と同様に、Ｓ１０にて対象コアで動作候補タスクが無いと判定した場合には対象コアでのスケジューリング処理を終了し、Ｓ１０にて対象コアで動作候補タスクが有ると判定した場合にはマイグレーションコスト算出処理を行う（Ｓ１１）。図３の例では、第０コア１０での動作が中断されたタスクＡが動作候補タスクとなり、第１コア１１での動作候補タスクが有ると判定される。
【００４８】
マイグレーションコスト算出処理では、まず、次の対象コア（第１コア１１）での動作候補タスク（タスクＡ）にマイグレーションが発生するか否かを判定し（Ｓ２０）、マイグレーションが発生すると判定した場合には動作候補タスクのマイグレーションコストを１加算する（Ｓ２１）。図３の例では、タスクＡには第０コア１０から第１コア１１へのマイグレーションが発生するので、タスクＡのマイグレーションコストは＋１となる。
【００４９】
次に、対象コア（第１コア１１）で現在動作中のタスク(タスクＢ)の動作経過時間が動作経過時間閾値以上か否かを判定し（Ｓ２２）、現在動作中のタスクの動作経過時間が動作経過時間閾値以上と判定した場合には現在動作中のタスクのマイグレーションコストを１減算する（Ｓ２３）。図３の例では、第１コア１１で動作中のタスクＢの動作経過時間が動作経過時間閾値以上なので、タスクＢのマイグレーションコストは−１となる。
【００５０】
次に、動作候補タスク（タスクＡ）の他方のコア（第０コア１０）での前回の動作経過時間が動作経過時間閾値以上か否かを判定し（Ｓ２４）、動作候補タスクの前回の動作経過時間が動作経過時間閾値以上と判定した場合には動作候補タスクのマイグレーションコストを１加算する（Ｓ２５）。図３の例では、タスクＡの第０コア１０での前回の動作経過時間が動作経過時間閾値未満なので、タスクＡのマイグレーションコストは＋１のままである。
【００５１】
対象コア(第１コア１１)での動作候補タスク（タスクＡ）の実行優先度に算出したマイグレーションコストを加算した優先度と対象コア（第１コア１１）で現在動作中のタスク(タスクＢ)の実行優先度に算出したマイグレーションコストを加算した優先度とを比較し（Ｓ１２）、動作候補タスクの優先度が高いと判定した場合には動作候補タスクを対象コアの動作タスクと決定し（Ｓ１３）、現在動作中タスクの優先度が動作候補タスクの優先度より高いと判定した場合には現在動作中タスクを対象コアの動作タスクと決定する（Ｓ１４）。図３の例では、タスクＡについては実行優先度１０にマイグレーションコストの＋１が加算されて優先度１１となり、タスクＢについては実行優先度１１からマイグレーションコストの−１が加算された優先度１０となり、タスクＡの優先度１１とタスクＢの優先度１０を比較し、タスクＢのほうが優先度が高いと判定され、第１コア１１での動作タスクがタスクＢとなる。これで、各コア１０，１１についてのスケジューリング処理が終了する。
【００５２】
このマルチコアプロセッサ１によれば、タスク固有の実行優先度に加えてタスクを切り替えることによって発生するマイグレーションコストを導入することにより、効率の悪いタスクの切り替えを回避でき、複数のタスクを効率良く実行させることができるスケジューリングを行うことができる。これによって、マイグレーションの発生を抑制でき、キャッシュメモリのヒット率の低下やタスク切り替えのオーバヘッドによる性能低下などを抑制したスケジューリングとなる。また、実行優先度も加味されているので、タスク固有の優先度も考慮したスケジューリングとなる。
【００５３】
このマルチコアプロセッサ１によれば、マイグレーションの有無、タスクの動作経過時間、タスク終了までの残時間、動作予測時間などをパラメータとしてマイグレーションコストを算出することにより、高精度なマイグレーションコストを求めることができる。
【００５４】
以上、本発明に係る実施の形態について説明したが、本発明は上記実施の形態に限定されることなく様々な形態で実施される。
【００５５】
例えば、本実施の形態では２つのコアを備えるマルチコアプロセッサに適用したが、３つ以上のコアを備えるものあるいは１つのコアを備えるものにも適用できる。１つのコアの場合、マイグレーションは発生しないので、マイグレーションコストではなく、マイグレーションを伴わない、タスクが切り替わることによって生じるコスト（パラメータがタスクの動作経過時間、残時間など）を導入する。
【００５６】
また、本実施の形態では演算装置としてコアを適用したが、ＣＰＵ、プロセッサなどでもよい。また、本実施の形態では演算処理としてタスクを適用したが、プロセス、スレッドなどでもよい。
【００５７】
また、本実施の形態ではタスクを実行するコアでスケジューラ機能も担う構成としたが、専用のスケジューラを備える構成としてもよい。
【００５８】
また、本実施の形態ではタスク個々の実行優先度にタスクを切り替えることによって生じるコスト（ここでは、マイグレーションコスト）を加味した優先度に基づいてスケジューリングを行う構成としたが、コストのみに基づいてスケジューリングを行ってもよい。
【００５９】
また、本実施の形態では動作候補タスクと現在動作中タスクの実行優先度にマイグレーションコストを加味した優先度を比較することによって動作タスクを判定する構成としたが、動作候補タスクの実行優先度が現在動作中タスクの実行優先度より高い場合にのみマイグレーションコストを算出し、そのマイグレーションコストを実行優先度に加味して動作タスクを判定するようにしてもよい。
【００６０】
また、本実施の形態ではパラメータとしてマイグレーションの発生の有無、タスクの動作経過時間（キャッシュメモリの推測ヒット率）や終了までの残時間、動作候補タスクの動作予測時間を用いてコストを設定する構成としたが、この中の何れかのパラメータだけを用いてコストを設定してもよいし（例えば、マイグレーションの発生の有無だけでコストを設定）、あるいは、これら以外のパラメータも用いてコストを設定してもよい。
【００６１】
また、本実施の形態ではコアでの動作経過時間からキャッシュメモリのヒット率を推測する構成としたが、キャッシュメモリのヒット率を直接検出してもよい。
【００６２】
また、本実施の形態ではマイグレーションコストのパラメータの種別や各パラメータの時間の長さなどに関係なくコストを全て１単位で増減したが、マイグレーションコストのパラメータの種別や各パラメータの時間の長さなどに応じて増減するコストの大きさを変えてもよい。
【００６３】
また、終了時間が規定されているタスクＡ（一定時間毎に動作させる周期タスクなど）がある場合、他のタスクＢが動作中のときにタスクＡが動作可能状態になったときには、その動作中のタスクＢが終了した後にタスクＡの動作を開始しても規定されている終了時間までにタスクＡを終了させることができるか否かでコストを設定し、規定されている終了時間までにタスクＡを終了させることができる場合にはタスクＢの動作を継続させてもよい。あるいは、終了時間が規定されているタスクＡがある場合、タスクＡが動作中のときに他のタスクＢが動作可能状態になったときには、タスクＡを中断してタスクＢを動作させ、タスクＢが終了した後にタスクＡの動作を再開しても規定されている終了時間までにタスクＡを終了させることができるか否かでコストを設定し、規定されている終了時間までにタスクＡを終了させることができる場合にはタスクＡの動作途中でタスクＢを動作させてもよい。
【符号の説明】
【００６４】
１…マルチコアプロセッサ、１０…第０コア、１１…第１コア、２０…メインメモリ
【図１】
2010205046.tif 000003
【図２】
2010205046.tif 000004
【図３】
2010205046.tif 000005
【図４】
2010205046.tif 000006
【図５】
2010205046.tif 000007
【図６】
2010205046.tif 000008