(57)【要約】【課題】キャッシュメモリの利用効率が低下しない範囲でできるだけ多くのタスクを実行できるように並列性とキャッシュの利用効率とのバランスをとる。【解決手段】複数のマイクロプロセッサ１と、それらによって共有されるキャッシュメモリ２及びメインメモリ３と、これらの間で行われたリフィルの回数を数えるリフィルカウンタ５とを有するマルチコアシステムにおけるタスクスケジューリング方法であって、実行可能状態のタスクの中からマイクロプロセッサ１を割り当てて実行状態とするタスクを選択するスケジューリングの際に、マイクロプロセッサ１を解放することによって実行状態から待機状態へ移行してから該スケジューリングの時点までに行われたリフィルの回数が所定回数未満である若い世代のタスクが存在するか否かを判断し、若い世代のタスクが存在する場合には、そのいずれかを選択してマイクロプロセッサ１を割り当てる。【選択図】図４
2011059777.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサと、該プロセッサによって共有されるキャッシュメモリ及びメインメモリと、前記複数のプロセッサによって前記キャッシュメモリと前記メインメモリとの間で行われたデータの授受であるリフィルの回数を数えるリフィルカウンタとを有するマルチコアシステムにおけるタスクスケジューリング方法であって、
前記プロセッサを割り当てる候補である実行可能状態のタスクの中から前記プロセッサを割り当てて実行状態とするタスクを選択するスケジューリングの際に、前記プロセッサを解放することによって前記実行状態から待機状態へ移行してから該スケジューリングの時点までに行われた前記リフィルの回数が所定回数未満である第１の種別のタスクが前記実行可能状態のタスクの中に存在するか否かを判断し、
前記第１の種別のタスクが存在する場合には、該第１の種別のタスクのいずれかを選択して前記プロセッサを割り当てることを特徴とするタスクスケジューリング方法。
【請求項２】
前記スケジューリングの際に、実行可能状態のタスクの全てが、前記待機状態となってから前記スケジューリングの時点までに行われたリフィル回数が所定回数以上の第２の種別のタスクである場合には、該スケジューリングの時点までの所定の期間に行われた前記リフィルの回数が所定の閾値未満であるか否かを判断し、
前記閾値未満である場合には、前記第２の種別のタスクのいずれかに前記プロセッサを割り当て、前記閾値以上である場合には、いずれのタスクにも前記プロセッサを割り当てないことを特徴とする請求項１記載のタスクスケジューリング方法。
【請求項３】
複数のプロセッサと、該プロセッサによって共有されるキャッシュメモリ及びメインメモリと、前記プロセッサによって前記キャッシュメモリと前記メインメモリとの間で行われたデータの授受であるリフィルの回数を数えるリフィルカウンタとを有するマルチコアシステムにおけるタスクスケジューリング方法であって、
前記プロセッサを割り当てる候補である実行可能状態のタスクの中から前記プロセッサを割り当てて実行状態とするタスクを選択するスケジューリングの際に、該スケジューリングの時点までの所定の期間に行われた前記リフィルの回数が所定の閾値未満であるか否かを判断し、
前記閾値未満である場合には、前記実行可能状態のタスクのいずれかを選択して前記プロセッサを割り当て、前記閾値以上である場合には、いずれのタスクにも前記プロセッサを割り当てないことを特徴とするタスクスケジューリング方法。
【請求項４】
前記実行可能状態のタスクの中から前記プロセッサを割り当てるタスクを選択する際に、前記プロセッサを解放することによって前記実行状態から待機状態へ移行してから該スケジューリングの時点までに行われた前記リフィルの回数が所定回数未満である第１の種別のタスクが前記実行可能状態のタスクの中に存在するか否かを判断し、
前記第１の種別のタスクが存在する場合には、該第１の種別のタスクのいずれかを選択して前記プロセッサを割り当て、
存在しない場合には、前記待機状態となってから前記スケジューリングの時点までに行われたリフィル回数が所定回数以上の第２の種別のタスクのいずれかに前記プロセッサを割り当てることを特徴とする請求項３記載のタスクスケジューリング方法。
【請求項５】
複数のプロセッサがキャッシュメモリ及びメインメモリを共有するマルチプロセッサ構成のマルチコアシステムであって、
前記複数のプロセッサによって前記キャッシュメモリと前記メインメモリとの間で行われたデータの授受であるリフィルの回数を計測するリフィルカウンタと、
前記各プロセッサ上で動作し、前記プロセッサを割り当てる候補である実行可能状態のタスクの中から前記プロセッサを割り当てて実行状態とするタスクを選択するスケジューリングを行うスケジューラとを有し、
前記スケジューラは、
前記スケジューリングの際に、前記プロセッサを解放することによって前記実行状態から待機状態へ移行してから該スケジューリングの時点までに行われた前記リフィルの回数が所定回数未満である第１の種別のタスクが前記実行可能状態のタスクの中に存在するか否かを判断する手段と、
前記第１の種別のタスク存在する場合に、該第１の種別のタスクのいずれかを選択して前記プロセッサを割り当てる手段と、
前記スケジューリングの時点での実行可能状態の全てのタスクが、前記待機状態となってから前記スケジューリングの時点までに行われたリフィル回数が所定回数以上である第２の種別のタスクの場合に、該スケジューリングの時点までの所定の期間に行われた前記リフィルの回数が所定の閾値未満であるか否かを判断する手段と、
前記所定の期間に行われたリフィルの回数が所定の閾値以上である場合には、いずれのタスクにも前記プロセッサを割り当てず、前記所定の期間に行われたリフィルの回数が閾値未満である場合にのみ、前記第２の種別のタスクのいずれかに前記プロセッサを割り当てる手段とを備えることを特徴とするマルチコアシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプロセッサがキャッシュメモリを共有するマルチコアシステム及びそのスループットを向上させるタスクスケジューリング方法に関する。
【背景技術】
【０００２】
複数のプロセッサがキャッシュメモリ及びメインメモリを共有するマルチコアシステムにおいては、同時に多数のタスクを実行させることで並列度を高めスループットを向上させることができる。
【０００３】
しかし、多数のタスクを同時に実行すると、時間的局所性や空間的局所性が低下するため、タスクが互いにキャッシュラインを置き換えあってキャッシュの利用効率が低下してしまう。さらに、キャッシュメモリ−メインメモリ間での転送がボトルネックとなってスループットが低下してしまう。このため、キャッシュメモリの利用効率が低下しない程度にできるだけ多くのタスクを実行できるように並列性とキャッシュの利用効率とのバランスをとることが求められている。
【０００４】
特許文献１には、バスのトラフィックを監視してトラフィックを軽減するようにタスクをスケジュールする技術が開示されている。しかし、キャッシュメモリを備えたマルチコアシステムにおいては、新たにタスクを実行することが即座にトラフィックの増加につながるわけではなく、新たに実行するタスクによる時間的局所性に応じてトラフィックの増加量が変動する。したがって、特許文献１に開示される発明は、キャッシュメモリの特性を考慮して並列性とキャッシュの利用効率とのバランスをとることはできない。
【０００５】
特許文献２には、同一のプロセッサで処理されたタスクの一覧を管理することで、キャッシュメモリの無用な置き換えを低減する技術が開示されている。この技術は、個々のプロセッサにキャッシュメモリを持つ場合には有効だが、複数のプロセッサが一つのキャッシュメモリを共有している場合には効果がない。
【０００６】
特許文献３には、タスクがアクセスするメモリ領域を検出し、同一領域をアクセスするタスクをグループにして、同一プロセッサに割り当てることでキャッシュメモリの無用な置き換えを低減する技術が開示されている。この技術は、複数のプロセッサが一つのキャッシュメモリを共有している場合には効果がない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平０６−２５９３９５号公報
【特許文献２】特開平０６−０１２３２５号公報
【特許文献３】特開２００２−０５５９６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、キャッシュメモリの利用効率が低下しない範囲でできるだけ多くのタスクを実行できるように並列性とキャッシュの利用効率とのバランスをとるタスクスケジューリング方法及びマルチコアシステムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本願発明の一態様によれば、複数のプロセッサと、該プロセッサによって共有されるキャッシュメモリ及びメインメモリと、複数のプロセッサによってキャッシュメモリとメインメモリとの間で行われたデータの授受であるリフィルの回数を数えるリフィルカウンタとを有するマルチコアシステムにおけるタスクスケジューリング方法であって、プロセッサを割り当てる候補である実行可能状態のタスクの中からプロセッサを割り当てて実行状態とするタスクを選択するスケジューリングの際に、プロセッサを解放することによって実行状態から待機状態へ移行してから該スケジューリングの時点までに行われたリフィルの回数が所定回数未満である第１の種別のタスクが実行可能状態のタスクの中に存在するか否かを判断し、第１の種別のタスクが存在する場合には、該第１の種別のタスクのいずれかを選択してプロセッサを割り当てることを特徴とするタスクスケジューリング方法が提供される。
【発明の効果】
【００１０】
本発明によれば、キャッシュメモリの利用効率が低下しない範囲でできるだけ多くのタスクを実行できるように並列性とキャッシュの利用効率とのバランスをとるタスクスケジューリング方法を提供できるという効果を奏する。
【００１１】
また、本発明によれば、キャッシュメモリの利用効率が低下しない範囲でできるだけ多くのタスクを実行できるように並列性とキャッシュの利用効率とのバランスをとるマルチコアシステムを提供できるという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】図１は、本発明の第１の実施の形態にかかるマルチコアシステムの構成を示す図。
【図２】図２は、タスクが取りうる状態の一例を示す図。
【図３】図３は、第１の実施の形態にかかるマルチコアシステムのメインメモリに記憶される情報の一例を示す図。
【図４】図４は、スケジューラがスケジューリングを実行する際の動作の流れの一例を示す図。
【図５】図５は、本発明の第２の実施の形態にかかるマルチコアシステムのスケジューラがスケジューリングを実行する際の動作の流れの一例を示す図。
【図６】図６は、本発明の第３の実施の形態にかかるマルチコアシステムの構成を示す図。
【図７】図７は、第３の実施の形態にかかるマルチコアシステムのスケジューラがスケジューリング動作を実行する際の動作の流れの一例を示す図。
【図８】図８は、本発明の第４の実施の形態にかかるマルチコアシステムの構成を示す図。
【図９】図９は、第４の実施の形態にかかるマルチコアシステムのスケジューラがスケジューリング動作を実行する際の動作の流れの一例を示す図。
【発明を実施するための形態】
【００１３】
以下に添付図面を参照して、本発明の実施の形態にかかるタスクスケジューリング方法及びマルチコアシステムを詳細に説明する。なお、これらの実施の形態により本発明が限定されるものではない。
【００１４】
（第１の実施の形態）
図１は、本発明の第１の実施の形態にかかるマルチコアシステムの構成を示す図である。
マルチコアシステムは、複数のマイクロプロセッサ１（１ａ、１ｂ、１ｃ）がキャッシュメモリ２及びメインメモリ３を共有したマルチプロセッサ構成であり、クロックカウンタ４とキャッシュリフィルカウンタ５とを備えている。
【００１５】
キャッシュリフィルカウンタ５は、キャッシュメモリ２がメインメモリ３から読み出した回数及びメインメモリ３に書き込んだ回数を計数する。具体的には、キャッシュリフィルカウンタ５は、キャッシュメモリ２からメインメモリ３に対するメモリの読み出し要求又はメモリの書き込み要求が１回送出されるごとに１回カウントする。
【００１６】
マイクロプロセッサ１ａ、１ｂ、１ｃはそれぞれスケジューラ１１ａ、１１ｂ、１１ｃを備えており、タスクから解放された際にスケジューラ１１ａ、１１ｂ、１１ｃを起動してスケジューリングを実行する。すなわち、マイクロプロセッサ１ａ、１ｂ、１ｃの各々は、タスクの実行が終了するとスケジューラ１１ａ、１１ｂ、１１ｃを起動して、次に自身が実行すべきタスクをメインメモリ３から選択的に取得し、そのタスクに自身を割り当てて実行する。なお、以下の説明においては、特に区別する必要がある場合を除いて、マイクロプロセッサ１及びスケジューラ１１の符号に添え字ａ〜ｃは付さないものとする。
【００１７】
スケジューラ１１は、キャッシュリフィルカウンタ５のカウント値を読み取ることが可能である。また、スケジューラ１１は、クロックカウンタ４からカウント値を読み取ることが可能である。
【００１８】
図２に示すように、タスクは「実行状態」、「待機状態」、「実行可能状態」の三つの状態を取りうるものとする。実行状態のタスクとは、現在マイクロプロセッサ１が割り当てられて実行されているタスクである。実行可能状態のタスクとは、スケジューラ１１がマイクロプロセッサ１を割り当てれば実行可能なタスクである。待機状態のタスクとは、条件が整わないため実行が保留されているタスクである。
【００１９】
図３に示すように、メインメモリ３内には、スケジューラ１１が次に実行すべきタスクを選択するための情報が記録される。すなわち、マイクロプロセッサ１において実行中ではないタスクが「実行可能状態」と「待機状態」とに分類されて格納されており、実行可能状態のタスクは、実行可能状態に遷移した順番にディスパッチキューとして整列している。各タスクには、それが待機状態に遷移した時点でのキャッシュリフィルカウンタ５の値Wtが関連付けられて格納されている。Wtはスケジューリング時に「若い世代のタスク」（特許請求の範囲における「第１の種別のタスク」）、「老いた世代のタスク」（特許請求の範囲における「第２の種別のタスク」）を判定する際に参照される。また、後述するように、メインメモリ３には、前回のスケジューリング時のクロックカウンタ４のカウント値Tprevと、前回のスケジューリング時のキャッシュリフィルカウンタ５のカウント値Cprevとが格納されている。
【００２０】
スケジューラ１１には、スケジューリングを行うパラメータとして、世代閾値Gthとキャッシュ閾値αとの二つを設定する。世代閾値Gthは、その時点でのキャッシュ容量に基づいて設定される。キャッシュ利用閾値αは、単位時間当たりのリフィル回数の閾値であり、キャッシュメモリ２とメインメモリ３との間のスループットに基づいて設定される。すなわち、スケジューラ１１は、システムの特性に合わせて上記二つのパラメータによって調整される。
【００２１】
図４に、スケジューラ１１がスケジューリングを実行する（次にマイクロプロセッサ１を割り当てるべきタスクを選択する）際の動作の流れを示す。
スケジューラ１１は、実行可能状態のタスクの中から次にマイクロプロセッサ１に実行させるタスクを選択する際に、現在のキャッシュリフィルカウンタ５の値（Ccurr）及び現在のクロックカウンタ４の値（Tcurr）を読み取る（ステップＳ１）。
次に、スケジューラ１１は、実行可能状態のタスクについて、Wtの値をメインメモリ３から読み出す（ステップＳ２）。そして、読み出したWtの値と現在のキャッシュリフィルカウンタ５の値（Ccurr）との差を世代閾値Gthと比較する（ステップＳ３）。Ccurr-Wt<Gthであるタスクが存在するならば（ステップＳ３／Ｙｅｓ）、スケジューラ１１は、そのタスクを「若い世代のタスク」と判定し（ステップＳ４）、直ちに選択して、マイクロプロセッサ１を割り当てる（ステップＳ５）。一方、実行可能状態のタスクがCcurr-Wt>=Gthであった場合（ステップＳ３／Ｎｏ）、スケジューラ１１は、それらのタスクを「老いた世代のタスク」と判定する（ステップＳ６）。「老いた世代のタスク」と判定した場合は、ステップＳ２に戻って他の実行可能状態のタスクにも同様の処理を行い、あるタスクを若い世代と判定してマイクロプロセッサ１を割り当てるか、全てのタスクを老いた世代と判定するまで処理を繰り返す。
【００２２】
実行可能状態のタスクが全て「老いた世代のタスク」であったならば、スケジューラ１１は、Ccurr-Cprev<α・（Tcurr-Tprev）が成立するか否か（前回のスケジュール後の単位時間当たりのリフィル回数{(Ccurr-Cprev)/(Tcurr-Tprev)}がキャッシュ利用閾値α未満であるか否か）を判定する（ステップＳ７）。Ccurr-Cprev<α・（Tcurr-Tprev）が成立する場合は（ステップＳ７／Ｙｅｓ）、スケジューラ１１は、「老いた世代のタスク」がスケジュール可能であると判断し、実行可能状態のタスクの中で最初に実行可能状態となったタスク（換言するとディスパッチキューの先頭にあるタスク）にマイクロプロセッサ１を割り当てる（ステップＳ８）。Ccurr-Cprev<α・（Tcurr-Tprev）が成立しない場合は（ステップＳ７／Ｎｏ）、スケジューラ１１は、「老いた世代のタスク」をスケジュールできないと判断し、次回のスケジュールのためにCcurrをCprevに、TcurrをTprevに保存する（ステップＳ９）。
【００２３】
「若い世代のタスク」又は「老いた世代のタスク」にマイクロプロセッサ１を割り当てた場合も、スケジューラ１１は、次回のスケジュールのためにCcurrをCprevに、TcurrをTprevに代入し、メインメモリ３に保存する（ステップＳ９）。
【００２４】
以上の動作により、キャッシュリフィルが必要となる可能性が高い「老いた世代のタスク」は、キャッシュの利用度が低い場合にのみスケジュールされてマイクロプロセッサ１が割り当てられる。
【００２５】
このように、本実施の形態にかかるマルチコアシステムによれば、待機状態に遷移した後のキャッシュリフィル回数が所定数以上である「老いた世代のタスク」については、単位時間当たりのキャッシュリフィル回数が、キャッシュメモリとメインメモリとの間のスループットに基づいて設定されるキャッシュ利用閾値α未満である場合にのみ、スケジュール可能であると判断する。すなわち、タスクの実行世代をキャッシュリフィルカウンタの値を使用して判定し、世代別にスケジュール方法を変更する。これにより、キャッシュメモリのヒット率を維持できる範囲で同時に実行するタスクを最大化できる。換言すると、キャッシュメモリの利用効率が低下しない範囲でできるだけ多くのタスクを実行できるように並列性とキャッシュの利用効率とのバランスをとることができる。
【００２６】
なお、図１ではクロックカウンタ４を備え、前回のスケジューリング時のクロックカウンタ４のカウンタ値と今回のスケジューリング時のクロックカウンタ４のカウンタ値との差によって、前回のスケジューリングからの経過時間を計測する構成を例として示したが、クロックカウンタ４の代わりにタイマを設けても同様の動作を行えることは言うまでも無い。
【００２７】
（第２の実施の形態）
本発明の第２の実施の形態にかかるマルチコアシステムの構成は、第１の実施の形態と同様である。
【００２８】
図５に、本発明の第２の実施の形態にかかるマルチコアシステムのスケジュール動作の流れを示す。
スケジューラ１１は、実行可能状態のタスクの中から次にマイクロプロセッサ１に実行させるタスクを選択する際に、現在のキャッシュリフィルカウンタ５の値（Ccurr）及び現在のクロックカウンタ４の値（Tcurr）を読み取る（ステップＳ１１）。そして、スケジューラ１１は、Ccurr-Cprev<α・（Tcurr-Tprev）が成立するか否か（前回のスケジュール後の単位時間当たりのリフィル回数{(Ccurr-Cprev)/(Tcurr-Tprev)}がキャッシュ利用閾値α未満であるか否か）を判定する（ステップＳ１２）。
【００２９】
Ccurr-Cprev<α・（Tcurr-Tprev）が成立する場合は（ステップＳ１２／Ｙｅｓ）、スケジューラ１１は、実行可能状態のタスクについて、Wtの値をメインメモリ３から読み出す（ステップＳ１３）。そして、読み出したWtの値と現在のキャッシュリフィルカウンタ５の値（Ccurr）との差を世代閾値Gthと比較する（ステップＳ１４）。Ccurr-Wt<Gthであるタスクが存在するならば（ステップＳ１４／Ｙｅｓ）、スケジューラ１１は、そのタスクを「若い世代のタスク」と判定し（ステップＳ１５）、直ちに選択して、マイクロプロセッサ１を割り当てる（ステップＳ１６）。一方、実行可能状態のタスクがCcurr-Wt>=Gthであった場合（ステップＳ３／Ｎｏ）、スケジューラ１１は、それらのタスクを「老いた世代のタスク」と判定する（ステップＳ１７）。「老いた世代のタスク」と判定した場合は、ステップＳ１３に戻って他の実行可能状態のタスクにも同様の処理を行い、あるタスクを若い世代と判定してマイクロプロセッサ１を割り当てるか、全てのタスクを老いた世代と判定するまで処理を繰り返す。
【００３０】
実行可能状態のタスクが全て「老いた世代のタスク」であったならば、実行可能状態のタスクのうち最初に実行可能状態となったタスク（換言するとディスパッチキューの先頭にあるタスク）にマイクロプロセッサ１を割り当てる（ステップＳ１８）。
【００３１】
Ccurr-Cprev<α・（Tcurr-Tprev）が成立しない場合は（ステップＳ１２／Ｎｏ）、スケジューラ１１は、タスクをスケジュールできないと判断し、次回のスケジュールのためにCcurrをCprevに、TcurrをTprevに保存する（ステップＳ１９）。
【００３２】
「若い世代のタスク」又は「老いた世代のタスク」にマイクロプロセッサ１を割り当てた場合も、スケジューラ１１は、次回のスケジュールのためにCcurrをCprevに、TcurrをTprevに代入し、メインメモリ３に保存する（ステップＳ１９）。
【００３３】
本実施の形態においては、先に単位時間当たりのリフィル回数がキャッシュ利用閾値α未満であるか否かの判定を行い（ステップＳ１２）、閾値未満である場合に実行可能状態のタスクについて若い世代であるか老いた世代であるかの判定を行う（ステップＳ１４）。すなわち、本実施の形態においては、単位時間当たりのリフィル回数がキャッシュ利用閾値α以上である場合には、世代の老若に関わらすタスクにマイクロプロセッサを割り当てない。
【００３４】
このため、第１の実施の形態と比較して、各マイクロプロセッサの稼働率は低くなるものの、キャッシュリフィル回数の増加を抑制する効果はより高くなる。従って、マイクロプロセッサの稼働率とリフィル回数の増加抑制とのどちらを優先するかに応じて、どちらの実施の形態を適用するかを決めるようにすれば良い。一例を挙げると、実行の遅れが許容されないタスク（リアルタイム性が要求されるストリーミング処理などのタスク）を実行する際には、本実施の形態のスケジュール動作を適用することが好ましい。
【００３５】
（第３の実施の形態）
図６は、本発明の第３の実施の形態にかかるマルチコアシステムの構成を示す図である。第１の実施の形態にかかるマルチコアシステムとは、クロックカウンタ４を備えていない点で相違する。
図７に、本実施の形態にかかるマルチコアシステムのスケジューラ１１がスケジューリングを実行する際の動作の流れを示す。スケジューリングの際に、実行可能状態のタスクについて若い世代であるか否かを判定し（ステップＳ２３）、若い世代のタスクが存在するならば（ステップＳ２４）、優先的にマイクロプロセッサ１を割り当てる（ステップＳ２５）点は第１の実施の形態と同様である。ただし、本実施の形態においては、若い世代のタスクが存在しない場合には、単位時間当たりのリフィル回数に関わらず老いた世代のタスクにプロセッサ１を割り当てる（ステップＳ２７）。
これにより、老いた世代のタスクが、マイクロプロセッサ１が割り当てられることなく長時間放置されることを防止できる。
【００３６】
若い世代のタスクを実行する上で必要なデータは、キャッシュメモリ２上に保持されている可能性が高い。このため、若い世代のタスクの有無を確認し、存在する場合には優先的にマイクロプロセッサ１を割り当てることで、キャッシュメモリの利用効率が低下しない範囲でできるだけ多くのタスクを実行できるように並列性とキャッシュの利用効率とのバランスをとることが可能となる。
【００３７】
（第４の実施の形態）
図８は、本発明の第４の実施の形態にかかるマルチコアシステムの構成を示す図である。第１の実施の形態にかかるマルチコアシステムとは、キャッシュリフィルカウンタ５を備えていない点で相違する。
図９に、本実施の形態にかかるマルチコアシステムのスケジューラ１１がスケジューリングを実行する際の動作の流れを示す。スケジューリングの際に、単位時間当たりのリフィル回数がキャッシュ利用閾値α未満であるか否かの判定を行い（ステップＳ３２）、閾値未満である場合に実行可能状態のタスクにマイクロプロセッサ１を割り当てる（ステップＳ３３）点については第２の実施の形態と同様であるが、本実施の形態においては、実行可能状態のタスクに関して、世代の老若についての判断は行わない。
このため、待機状態となってから時間が経過したタスクが、マイクロプロセッサ１が割り当てられることなく放置されることを防止できる。
【００３８】
単位時間当たりのリフィル回数がキャッシュ利用閾値α未満である場合には、キャッシュのリフィルを要するタスクを割り当てたとしても、キャッシュメモリ２−メインメモリ３間でのキャッシュラインの転送がボトルネックとなってスループットが低下する可能性は低い。このため、単位時間当たりのリフィル回数がキャッシュ利用閾値α未満である場合には任意のキャッシュにマイクロプロセッサ１を割り当てることで、キャッシュメモリの利用効率が低下しない範囲でできるだけ多くのタスクを実行できるように並列性とキャッシュの利用効率とのバランスをとることが可能となる。
【００３９】
なお、上記各実施の形態は本発明の好適な実施の一例であり、本発明はこれらに限定されることなく様々な変形が可能である。
【符号の説明】
【００４０】
１  マイクロプロセッサ、２  キャッシュメモリ、３  メインメモリ、４  クロックカウンタ、５  キャッシュリフィルカウンタ、１１  スケジューラ。
【図１】
2011059777.tif 000003
【図２】
2011059777.tif 000004
【図３】
2011059777.tif 000005
【図４】
2011059777.tif 000006
【図５】
2011059777.tif 000007
【図６】
2011059777.tif 000008
【図７】
2011059777.tif 000009
【図８】
2011059777.tif 000010
【図９】
2011059777.tif 000011