JP5516744B2 - スケジューラ、マルチコアプロセッサシステムおよびスケジューリング方法 - Google Patents

Description

この発明は、複数のコアによる並列処理によってマルチタスク処理を行う際のスケジューラ、マルチコアプロセッサシステムおよびスケジューリング方法に関する。

従来より、プロセッサが処理実行時に利用するデータを格納するメモリ領域として、キャッシュメモリ、メインメモリ、ファイルシステムという階層的なメモリ構成が採用されている。階層的なメモリ構成は、データへのアクセス速度を向上させるため、システムの高速化が期待される。階層的なメモリ構成の場合、他のメモリと比較して高速に動作するキャッシュメモリは、限られたメモリ容量であるため、キャッシュメモリに格納されたデータは、ＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）などのアルゴリズムを用いて入れ替えが行われる（例えば、下記特許文献１参照。）。

また、近年では複数のプロセッサを備えたマルチコアプロセッサシステムが広く採用されている。マルチコアプロセッサシステムは、各プロセッサによってタスクを並列に実行させるため、処理性能を大幅に向上させることができる（例えば、下記特許文献１参照。）。一方で、マルチコアプロセッサシステムは、タスクを並列に実行させた場合、各プロセッサのキャッシュメモリ上のデータが書き換えられた際に、他のプロセッサのキャッシュメモリ上のデータを同期させる処理が必要となる。

データの同期の手法として、具体的には、プロセッサ間でのキャッシュコヒーレンシを取るための機構であるスヌープキャッシュ機構が挙げられる。スヌープキャッシュ機構は、キャッシュメモリ上の、あるプロセッサが他のプロセッサと共有するデータが書き換えられた際に動作する。キャッシュメモリ上のデータの書き換えは、他のプロセッサのキャッシュメモリに搭載されているスヌープコントローラによって検知される。そして、スヌープコントローラは、キャッシュメモリ間のバスを介して、書き換えられた新しい値を他のプロセッサのキャッシュメモリにも反映させる（例えば、下記特許文献２参照。）。

また、組み込みシステムにおいても、複数のアプリケーションの並列実行が要求されており、並列実行を実現するための技術が提供されている。具体的には、１つのプロセッサ上で実行するタスクを時分割などで切り替えるマルチタスク処理や、複数のプロセッサで複数のタスクを実行する分散処理や、これらの処理を組み合わせた処理が開示されている（例えば、下記特許文献３参照。）。

特開平６−１７５９２３号公報 特開平１０−２４０６９８号公報 特開平１１−２１２８６９号公報

しかしながら、マルチコアプロセッサシステムの場合、複数のプロセッサによって並列タスクを実行する際に必要な、キャッシュメモリ間の同期処理や、マルチタスク処理の実行によって発生する頻繁なキャッシュメモリの書き換えが、性能低下の原因となることもあった。

図２０は、マルチコアの並列処理におけるスヌープの動作例を示す説明図である。マルチコアプロセッサシステム２０００の場合、マルチコア（例えば、図２０のようなＣＰＵ＃０，ＣＰＵ＃１）では、各ＣＰＵが同時に処理を実行する並列処理が行われる。そして並列処理の中でも、特に共通のデータを用いるタスクを各ＣＰＵ上で同時に実行する場合、一方のキャッシュメモリ（例えば、キャシュＬ１＄０とキャッシュＬ１＄１とのいずれか）上のデータが書き換えられると、スヌープ１２０によって同期処理が行われる。具体的には、スヌープ１２０は、ＣＰＵ＃０によってキャッシュＬ１＄０に配置されているデータの中の変数ａの値が書き換えられると、バスを介して、キャッシュＬ１＄１の変数ａのデータを書き換える。

スヌープ１２０によるデータの書き換えが頻繁に発生すると、キャシュＬ１＄０とキャッシュＬ１＄１とを接続するバスが混雑し、結果として性能劣化を起こしてしまう。さらに、頻繁な書き換え処理の発生によって、バストランザクションが増加してしまう。また、頻繁な書き換え処理の発生は、スヌープ１２０のバスを占有してしまうことになる。このような状態に、リアルタイム制約のある他のプロセスの実行要求が発生した場合、リアルタイム制約のある他のプロセスのキャッシュメモリへのアクセスを阻害してしまうため、重大な性能問題となる恐れがあった。

図２１は、マルチタスク処理におけるキャッシュ書き換え例を示す説明図である。マルチコアプロセッサシステム２０００がマルチタスク処理を行う場合、タスクの実行状況に応じて、実行対象となるタスクを切り替えるタスクスイッチが行われる。例えば、図２１において、マルチコアプロセッサシステム２０００は、タスク＃０〜タスク＃２を対象にしてマルチタスク処理を行う。

そして、図２１の左側のように、ＣＰＵ＃０によってタスク＃０が実行され、ＣＰＵ＃１によってタスク＃２が実行されている状態で、タスクスイッチが発生したとする。タスクスイッチの発生によって、図２１の右側のように、ＣＰＵ＃０によって実行されるタスクは、タスク＃０からタスク＃１に切り替えられる。実行対象となるタスクが切り替えられると、キャッシュＬ１＄０に配置されるデータの内容も、タスク＃０が利用するデータからタスク＃１が利用するデータへ書き換えられる。

キャッシュＬ１＄０に配置されるデータが書き換えられた後、書き換え以前に実行されていた処理の実行に戻った場合、ＣＰＵ＃０は、タスク＃０が利用するデータをメモリ１４０から再度読み出す必要がある。たとえ、タスクスイッチの発生によって、対象となるキャッシュメモリに配置されたデータが書き換えられても、その後ＣＰＵによってキャッシュメモリに配置されたデータが利用されないことも多かった。このように再利用性がないデータの書き換え処理は、キャシュメモリを利用するＣＰＵにとって性能劣化の原因となってしまうという問題があった。

本開示技術は、上述した従来技術による問題点を解消するため、並列処理およびマルチタスク処理が実行される場合であっても、キャッシュの利用効率を高めてマルチコアプロセッサシステムの処理能力を向上させることのできるスケジューラ、マルチコアプロセッサシステムおよびスケジューリング方法を提供することを目的とする。

上述した課題を解決し、目的を達成するため、本開示技術は、マルチコアプロセッサの各プロセッサに割り当てて実行させる処理群のうち前記各プロセッサに割り当てられる実行対象処理の優先度が、しきい値以上か否かを判断し、前記実行対象処理のうち、前記しきい値以上の優先度であると判断された高優先度の実行対象処理が実行時にアクセスするデータを、前記高優先度の実行対象処理を実行する各プロセッサのキャッシュメモリに配置し、前記実行対象処理のうち、前記しきい値以上の優先度でないと判断された低優先度の実行対象処理が実行時にアクセスするデータを、前記各プロセッサのキャッシュメモリよりアクセス速度の遅い他のメモリ領域に配置し、前記マルチコアプロセッサの中の一のプロセッサにおいて、前記他のメモリ領域に配置されたデータへのアクセス要求が発生した場合に、前記他のメモリ領域に配置されたデータを前記一のプロセッサのキャッシュメモリに配置する。

本スケジューラ、マルチコアプロセッサシステムおよびスケジューリング方法によれば、並列処理およびマルチタスク処理が実行される場合であっても、キャッシュの利用効率を高めてマルチコアプロセッサシステムの処理能力を向上させることができるという効果を奏する。

本実施の形態にかかるスケジューリング処理の一例を示す説明図である。 階層的なメモリ構成の一例を示す説明図である。 マルチタスク処理の一例を示す説明図である。 通常のキャッシュコヒーレンシの手順（その１）を示す説明図である。 通常のキャッシュコヒーレンシの手順（その２）を示す説明図である。 通常のキャッシュコヒーレンシの手順（その３）を示す説明図である。 通常のキャッシュコヒーレンシの手順（その４）を示す説明図である。 低優先度並列タスクにおけるキャッシュコヒーレンシの手順を示す説明図である。 スケジューラの機能的構成を示すブロック図である。 共有データの配置処理の手順を示すフローチャートである。 タスクテーブル作成処理の手順を示すフローチャートである。 タスクテーブルのデータ構造例を示すデータテーブルである。 タスクテーブルの設定例を示すデータテーブルである。 タスク実行処理の手順（その１）を示すフローチャートである。 タスク実行処理の手順（その２）を示すフローチャートである。 タスク実行処理の手順（その３）を示すフローチャートである。 タスク実行処理の手順（その４）を示すフローチャートである。 同一優先度の並列タスクの実行例を示す説明図である。 優先度の異なる並列タスクの実行例を示す説明図である。 マルチコアの並列処理におけるスヌープの動作例を示す説明図である。 マルチタスク処理におけるキャッシュ書き換え例を示す説明図である。

以下に添付図面を参照して、この発明にかかるスケジューラ、マルチコアプロセッサシステムおよびスケジューリング方法の好適な実施の形態を詳細に説明する。

図１は、本実施の形態にかかるスケジューリング処理の一例を示す説明図である。本実施の形態では、マルチコアプロセッサシステム１００に備えられた複数のプロセッサによって、複数の処理を並列に実行することができる。したがって、マルチコアプロセッサシステム１００では、アプリケーションの中から並列に実行可能な処理群（例えば、並列タスク）を抽出して、効率的な並列処理を行うことができる。

また、本実施の形態では、実行対象となる処理に実行順序に関する優先度を、高優先度と低優先度とに設定することによって、再利用性の高いデータを選別してキャッシュメモリに配置することができる。優先度は、処理を実行させた際に一旦キャッシュメモリに格納したデータへアクセスする頻度や、デッドライン時間に基づいて設定されている。各タスクの優先度の設定内容はタスクテーブル１１１に記憶されている。なお、図１以降、高優先度のタスクを表すブロックを、低優先度のタスクを表すブロックよりも大きく表示する。

したがって、マルチコアプロセッサシステム１００のスケジューラ１１０は、並列実行させる処理に設定されている優先度を参照して、各処理を実行する際にアクセスされるデータ（以下、「共有データ」と呼ぶ）をそれぞれ、最適なメモリ領域に配置する。また、スケジューラ１１０は、複数のキャッシュメモリに同一の共有データが配置されている場合に、優先度に応じて共有データを同期させるキャッシュコヒーレンシとして、どのような手法を用いるかを選択する。

具体的には、左側のマルチコアプロセッサシステム１００のように、同一優先度が設定された並列に実行可能な処理を各ＣＰＵによって同時に実行する場合、スケジューラ１１０は、高優先度の処理の共有データをアクセス速度の速いメモリ領域から優先的に配置する。例えば、高優先度に設定されている並列可能なタスク＃０，１およびタスク＃３，４の共有データは、キャッシュＬ１＄から順に、アクセス速度の速いメモリ領域に配置される。そして、低優先度に設定されたタスク＃２およびタスク＃５の共有データについては、高優先度の処理の共有データが配置された後に、残りのメモリに配置される。

一方、右側のマルチコアプロセッサシステム１００のように、優先度の異なる並列に実行可能な処理を各ＣＰＵによって同時に実行する場合も、スケジューラ１１０は、左側のマルチコアプロセッサシステム１００と同様に、高優先度に設定された処理の共有データをキャッシュＬ１＄へ配置する。その後、スケジューラ１１０は、残りのメモリに、低優先度に設定されたタスク＃２およびタスク＃３の共有データを配置する。

また、左側のマルチコアプロセッサシステム１００の場合、スケジューラ１１０は、通常のキャッシュメモリに新たな値が書き込まれたタイミングでキャッシュコヒーレンシを行う。一方、右側のマルチコアプロセッサシステム１００の場合、スケジューラ１１０は、あるキャッシュメモリ（例えば、キャッシュＬ１＄０）に、新たな値が書き込まれた後、ＣＰＵから新たな値の書き込みが反映されていないキャッシュメモリ（キャッシュＬ１＄１）への読み込みが発生したタイミングでキャッシュコヒーレンシを行う。

このように、本実施の形態にかかるマルチコアプロセッサシステム１００は、利用頻度の高い共有データを、アクセス速度の速いキャッシュメモリに優先的に配置するため、処理速度を向上させることができる。また、低優先度に設定された処理の共有データは、ＣＰＵからのアクセス要求が発生するまで、キャッシュコヒーレンシによる同期処理が延期される。したがって、再利用性のない共有データをキャッシュメモリに書き込むなど、処理性能の低下の原因となる動作を回避することができる。以下には、本実施の形態にかかるマルチコアプロセッサシステム１００の詳細な構成と処理手順について説明する。

（階層的なメモリ構成）
図２は、階層的なメモリ構成の一例を示す説明図である。図２に例示したように、本実施の形態にかかるマルチコアプロセッサシステム１００は、複数種類のメモリ領域を備えている。各メモリ領域は、それぞれプロセッサからのアクセス速度やメモリ容量が異なるため、それぞれ用途に応じたデータが格納される。

図２のように、マルチコアプロセッサシステム１００の各プロセッサ（ＣＰＵ＃０，ＣＰＵ＃１）には、キャッシュＬ１＄（各プロセッサに搭載されたキャッシュメモリ）、キャッシュＬ２＄（スヌープ１２０に搭載されたキャッシュメモリ）、メモリ１４０およびファイルシステム１５０という４種類のメモリ領域が用意されている。

各プロセッサと接続関係が近い上位のメモリ領域ほど、アクセス速度が速く、メモリ容量が小さい。反対に、各プロセッサとの接続関係が遠い下位のメモリ領域ほど、アクセス速度が遅く、メモリ容量が大きい。したがって、マルチコアプロセッサシステム１００では、図１にて説明したように、優先的に処理したいタスクが利用する共有データや、利用頻度の高い共有データを上位のメモリに配置する。

（マルチタスク処理）
図３は、マルチタスク処理の一例を示す説明図である。本実施の形態にかかるマルチコアプロセッサシステム１００におけるマルチタスク処理とは、複数のタスクが複数のプロセッサによって並列に実行される処理を意味する。

例えば、図３では、マルチコアプロセッサシステム１００の実行対象となるタスクとしてタスク＃０〜タスク＃５が用意されている。そして、スケジューラ１１０の制御によって、ＣＰＵ＃０とＣＰＵ＃１とは、それぞれ、ディスパッチされたタスクを実行する。スケジューラ１１０は、複数のタスクの中から実行対象となるタスクをタイムスライシングなどで適宜切り替えながら各タスクを並列に実行させる。

（キャッシュコヒーレンシ）
次に、本実施の形態にかかるマルチコアプロセッサシステム１００のスヌープ１２０によって実行されるキャッシュコヒーレンシの手順について説明する。図１にて説明したように、スヌープ１２０は、スケジューラ１１０からの指示に応じて、通常のキャッシュコヒーレンシと、低優先度並列タスクにおけるキャッシュコヒーレンシのいずれかのコヒーレンス方式が設定される。

＜通常のキャッシュコヒーレンシ（ｗｒｉｔｅ時更新）＞
図４〜７は、通常のキャッシュコヒーレンシの手順を示す説明図である。図４に例示したマルチコアプロセッサシステム１００では、並列タスクを実行するＣＰＵ＃０およびＣＰＵ＃１のキャッシュメモリ（キャッシュＬ１＄０およびキャッシュＬ１＄１）に、実行対象のタスクの記述４００に基づいて、最新データが格納される。

その後、図５のように、マルチコアプロセッサシステム１００の１つのＣＰＵが、記述４００の変数ａの中身を書き換えたとする。例えば、図５では、ＣＰＵ＃０によって、キャシュＬ１＄０の変数ａの値が書き換えられている。すると、同じデータが格納されているキャッシュＬ１＄１の変数ａは古いデータとなり、同じ変数ａであっても異なる値となってしまう。

そこで、通常のキャッシュコヒーレンシの場合、古いデータが格納されているキャッシュＬ１＄１の変数ａの値は、まず、図６のように、記述４００に基づいて、パージされる。

その後、図７のように、スヌープ１２０のバスを介して、キャッシュＬ１＄０の変数ａの値は、キャッシュＬ１＄１の変数ａの値として格納される。以上説明したように、通常のキャッシュコヒーレンシの場合、図４〜７に例示した処理を施すことによって、キャッシュＬ１＄０とキャッシュＬ１＄１との一貫性が保たれる。

＜低優先度並列タスクにおけるキャッシュコヒーレンシ（ｒｅａｄ時更新）＞
図８は、低優先度並列タスクにおけるキャッシュコヒーレンシの手順を示す説明図である。図８は、低優先度に設定された並列タスクをマルチコアプロセッサシステム１００によって実行させる場合のコヒーレンシの手順を表している。

まず、マルチコアプロセッサシステム１００において、ＣＰＵ＃０とＣＰＵ＃１とは並列タスクを実行しており、キャッシュＬ１＄０とキャッシュＬ１＄１には同じデータが配置されている（ステップＳ８０１）。

その後、マルチコアプロセッサシステム１００のＣＰＵ＃０が変数ａの中身を書き換えると（ステップＳ８０２）、キャッシュＬ１＄１の変数ａは、パージされる（ステップＳ８０３）。このように、低優先度並列タスクにおけるキャッシュコヒーレンシの場合も、キャシュメモリに格納されている変数ａの書き換えを検出して、古いデータがパージされるまでは、通常のキャッシュコヒーレンシと同じ手順が行われる。

その後、マルチコアプロセッサシステム１００のＣＰＵ＃１によって、変数ａへアクセスする処理が実行された場合、スヌープ１２０は、バスを介して、キャッシュＬ１＄０に格納されている最新の変数ａの値を、キャッシュＬ１＄１に格納する（ステップＳ８０４）。

以上説明したように、低優先度並列タスクにおけるキャッシュコヒーレンシでは、ＣＰＵ＃１によって最新の書き換え内容が反映されていないキャッシュＬ１＄１の変数ａへのアクセス要求が発生した際に、スヌープ１２０が制御され、コヒーレンスがとられる。したがって、通常のキャッシュコヒーレンシのような冗長なバストランザクションを回避することができる。

上述したように、通常のキャッシュコヒーレンシでは、変数ａが更新されたタイミングで動作を開始する。それに対して、低優先度並列タスクにおけるキャッシュコヒーレンシでは、ＣＰＵ＃０によって、キャッシュＬ１＄０の変数ａが更新された後、ＣＰＵ＃１によって変数ａへの読み込み要求が発生すると、はじめて動作を開始する。具体的には、スヌープ１２０が、最新の変数ａが配置されているキャッシュＬ１＄０の変数ａの値を読み込み、読み込んだ値を、キャッシュＬ１＄１の変数ａとして配置する。

また、図８に例示したステップＳ８０４では、キャッシュＬ１＄０にＣＰＵ＃０のアクセス対象となるデータが配置されていたが、キャッシュＬ１＄０によって実行されるタスクによっては、他のメモリ領域に格納されているデータがアクセス対象となる場合もある。例えば、ＣＰＵ＃０が、キャッシュＬ２＄やメモリ１４０やファイルシステム１５０に配置されているデータへアクセスする場合も想定される。そのような場合には、スヌープ１２０は、各データ領域から対象となるデータを読み出してキャシュメモリＬ１＄に配置することができる。

以下には、図１に示した本実施の形態にかかるスケジューリング処理を実現するマルチコアプロセッサシステム１００のスケジューラ１１０の機能的構成と、動作内容について説明する。

（スケジューラの機能的構成）
図９は、スケジューラの機能的構成を示すブロック図である。図９において、マルチコア９０１は、ｎ個のＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）を備え、マルチコアプロセッサシステム１００の全体の制御を司る。マルチコア９０１とは、コアが複数搭載されたプロセッサまたはプロセッサ群である。コアが複数搭載されていれば、複数のコアが搭載された単一のプロセッサでもよく、シングルコアのプロセッサが並列されているプロセッサ群でもよい。なお、本実施の形態では、説明を単純化するため、シングルコアのプロセッサが並列されているプロセッサ群を例に挙げて説明する。

そして、スケジューラ１１０は、判断部１００１と、第１配置部１００２と、第２配置部１００３と、第３配置部１００４と、特定部１００５と、抽出部１００６と、割当部１００７と、を含む構成である。判断部１００１〜割当部１００７は、具体的には、例えば、マルチコアプロセッサシステム１００の他のメモリ１００８（ＣＰＵに搭載されたキャッシュメモリ以外のメモリ）に記憶されたプログラムをマルチコア９０１の中の特定のＣＰＵに実行させることにより、その機能を実現する。

判断部１００１は、マルチコアプロセッサシステム１００において、実行対象となる処理（以下、「実行対象処理」と呼ぶ）に設定されている優先度がしきい値以上か否かを判断する機能を有する。具体的には、判断部１００１は、マルチコアプロセッサシステム１００の各プロセッサ（ＣＰＵ＃０〜ＣＰＵ＃ｎ）に割り当てて実行させる処理群のうち各プロセッサに割り当てられる実行対象処理の優先度が、しきい値以上か否かを判断する。判断部１００１による判断結果は、一旦、他のメモリ１００８などの記憶領域に記憶される。

優先度は、実行対象処理のシミュレーションによって得られる動作結果に基づいて設定される。例えば、各実行対象処理のデッドラインを比較して、デッドラインまでの時間が短い実行対象処理ほど、優先度が高くなるように設定してもよい。本実施の形態にかかるスケジューラ１１０は、優先度が高く設定されている実行対象処理の共有データを、一旦、アクセス速度の速いメモリ（キャッシュＬ１＄や、キャッシュＬ２＄）に配置すると、処理が終了するまでロック状態に保つ。したがって、優先度が高く設定されている実行対象処理は、他の実行対象処理よりも優先的に実行される。

また、他にも、動作結果を参照して、キャッシュメモリに配置した共有データの更新回数が多い実行対象処理ほど優先度が高くなるように設定してもよい。本実施の形態にかかるスケジューラ１１０は、再利用性の高い共有データを優先的に各プロセッサのキャッシュメモリ（キャッシュＬ１＄）に配置するため、キャッシュメモリの利用効率を高い値に維持することができる。

また、判断部１００１において判断基準となるしきい値は、調整可能である。そして、判断部１００１は、各実行対象処理について、設定されている優先度がしきい値以上であれば、高優先度の実行対象処理とし、設定されている優先度がしきい値に満たなければ、低優先度の実行対象処理とする。したがって、実行対象となるアプリケーションに応じて最適な値を設定することができる。また、実行対象処理の単位としては、タスク、プロセス、スレッドなど、任意の単位を選択することができる。本実施の形態では、一例として、タスクを実行対象処理の単位として説明を行う。

第１配置部１００２は、判断部１００１の判断結果に応じて、各ＣＰＵに搭載されたキャッシュメモリへデータを配置する機能を有する。具体的には、第１配置部１００２は、判断部１００１によって、実行対象処理のうち、しきい値以上の優先度であると判断された高優先度の実行対象処理が実行時にアクセスする共有データを、対象となるＣＰＵのキャッシュメモリに配置する。

例えば、高優先度の実行対象処理であるタスクＡが、マルチコア９０１の中のＣＰＵ＃１によって実行される場合、タスクＡが実行時にアクセスする共有データは、第１配置部１００２によって、キャッシュメモリ１に配置される。同様に、高優先度の実行対象処理であるタスクＢが、マルチコア９０１の中のＣＰＵ＃０によって実行される場合、タスクＢが実行時にアクセスする共有データは、第１配置部１００２によって、キャッシュメモリ０に配置される。

また、アプリケーション１０００によっては、実行対象処理の中に、判断部１００１によって、高優先度の実行対象処理が存在しないと判断されることがある。このような場合にキャッシュメモリを空の状態で放置すると、キャッシュメモリの利用効率が低下してしまう。そこで、第１配置部１００２は、高優先度の実行対象処理以外の処理（例えば、後述する低優先度の実行対象処理）であっても、各ＣＰＵに搭載されたキャッシュメモリへ共有データを配置する。その後、高優先度の実行対象処理が現れた場合、第１配置部１００２は、優先的に高優先度の処理の共有データを対象となるＣＰＵのキャッシュメモリに配置する。

また、第１配置部１００２は、上述したように、高優先度の実行対象処理の共有データを、対象となるプロセッサのキャッシュメモリに配置する際に、高優先度の実行対象処理の実行が終了するまで、共有データの上書きを禁止（ロック状態）にすることもできる。したがって、第１配置部１００２は、高優先度の実行対象処理の共有データに対する、再利用性のないデータによる上書きを防ぐことができる。

第２配置部１００３は、判断部１００１の判断結果に応じて、各プロセッサのキャッシュメモリよりもアクセス速度の遅い他のメモリ１００８に、データを配置する機能を有する。具体的には、第２配置部１００３は、判断部１００１によって、しきい値以上の優先度でないと判断された低優先度の実行対象処理が実行時にアクセスする共有データを、他のメモリ１００８に配置する。

なお、図２にて説明したように、キャッシュメモリ以外の他のメモリ１００８は、アクセス速度と、メモリ容量に応じて階層的に複数種類のメモリが用意されている。したがって、第２配置部１００３は、アクセス速度の高いメモリの順に配置可能な容量分のデータを順次格納する。例えば、図９の場合、キャッシュＬ２＄→メモリ１４０→ファイルシステム１５０の順序でデータが配置される。また、データも、事前のシミュレーションから特定した更新頻度が高いデータが優先的にアクセス速度の速いメモリに配置される。

第３配置部１００４は、マルチコア９０１からアクセス要求のあった共有データを、要求元のＣＰＵに搭載されているキャッシュメモリに配置する機能を有する。具体的には、第３配置部１００４は、マルチコア９０１の中のいずれかのＣＰＵ（例えば、ＣＰＵ＃１）においてメモリ１００８に配置された共有データへのアクセス要求が発生した場合に、メモリ１００８に配置された共有データを、ＣＰＵ＃１のキャッシュメモリ１に配置する。

特定部１００５は、判断部１００１によって実行対象処理の優先度が、しきい値以上か否かの判断が行われると、マルチコア９０１の各ＣＰＵのキャッシュメモリの中の書き換え可能な領域の容量を特定する機能を有する。書き換え可能な領域とは、すなわち、上書き可能な領域を意味する。

したがって、実行済の処理の共有データが配置されている領域や、低優先度の処理の共有データが配置されている領域は、上書き可能なため、書き換え可能な領域として特定される。特定部１００５による特定結果は、一旦、他のメモリ１００８などの記憶領域に記憶される。

また、第１配置部１００２は、特定部１００５によって特定された書き換え可能な領域の容量に応じて、配置処理を調整することもできる。例えば、書き換え可能な領域の容量が高優先度の実行対象処理が実行時にアクセスする共有データの容量よりも小さい場合、第１配置部１００２は、共有データをすべてキャッシュメモリに配置することはできない。そこで、第１配置部１００２は、共有データのうち、更新頻度が高いデータの順にキャッシュメモリに配置可能な容量分配置する。そして、第２配置部１００３は、キャッシュメモリに配置できなかった共有データを他のメモリ１００８領域に配置する。

また、反対に、書き換え可能な領域の容量が、高優先度の実行対象処理が実行時にアクセスする共有データの容量よりも大きくなる可能性もある。このような場合、第１配置部１００２は、まず、通常通り高優先度の実行対象処理が実行時にアクセスする共有データをキャッシュメモリに配置する。その後、第１配置部１００２は、低優先度の実行対象処理が実行時にアクセスする共有データのうち、更新頻度が高いデータの順にキャッシュメモリの中の空き容量に配置する。

抽出部１００６は、アプリケーション１０００に含まれる実行対象処理のうち、特定の条件を満たす処理を抽出する機能を有する。具体的には、抽出部１００６は、実行対象処理のうち、実行時にアクセスするデータが共通する処理（例えば並列タスク）を抽出する。実行時にアクセスするデータが共通するか否かは、各実行対象処理に設定されている共有データの識別子を参照する（例えば、後述する図１３にて説明する共有データＩＤ）。抽出部１００６による抽出結果は、一旦、メモリ１００８などの記憶領域に記憶される。

割当部１００７は、実行対象処理をマルチコア９０１の各ＣＰＵに割り当てる機能を有する。割当部１００７は、スケジューラ１１０からの指示がなければ、各実行対象処理を、事前に設定されている依存関係および実行順序と、現在の各ＣＰＵの処理負荷とに基づいて、最適なＣＰＵに割り当てる。

また、割当部１００７は、抽出部１００６によって抽出された処理が存在する場合には、共有データが共通する処理同士として抽出された各処理をマルチコア９０１の中の同一のＣＰＵに割り当てる。さらに、割当部１００７は、抽出部１００６によって抽出された処理のうち、同一の優先度が設定されている処理を、マルチコア９０１の中の同一のＣＰＵ（例えば、ＣＰＵ＃１など）に割り当てることもできる。

以下には、マルチコアプロセッサシステム１００が、実行対象処理の一例として、アプリケーション１００を構成する並列タスクを各ＣＰＵによって並列に実行する場合について説明する。

（共有データの配置処理）
図１０は、共有データの配置処理の手順を示すフローチャートである。図１０のフローチャートは、共有データをいずれのキャッシュメモリ（キャッシュＬ１＄やキャッシュＬ２＄）に配置するかを決定する手順を表している。図１０の各処理を実行することによって、各タスクを実行する際に利用する共有データをキャッシュコヒーレンシ処理の内容に対応した適切なキャッシュメモリに配置することができる。

図１０において、スケジューラ１１０には、実行対象となるタスクが順次入力される。したがって、スケジューラ１１０は、まず、実行対象となるタスクが高優先度タスクか否かを判断する（ステップＳ１００１）。ステップＳ１００１において、実行対象となるタスクが高優先度タスクであると判断された場合（ステップＳ１００１：Ｙｅｓ）、スケジューラ１１０は、実行対象となるタスクの全共有データサイズが、キャッシュＬ１＄サイズよりも小さいか否かを判断する（ステップＳ１００２）。

ステップＳ１００２において、全共有データサイズが、キャッシュＬ１＄サイズよりも小さいと判断された場合（ステップＳ１００２：Ｙｅｓ）、スケジューラ１１０は、全共有データをＬ１＄に配置して（ステップＳ１００３）、一連の処理を終了する。すなわち、スケジューラ１１０は、ステップＳ１００３によって、実行対象となるタスクが高優先度タスクであり、かつ、実行対象のタスクの全共有データがＣＰＵのキャッシュメモリに格納可能であれば、全共有データをアクセス速度の速いキャッシュＬ１＄に配置する。

ステップＳ１００２において、全共有データサイズが、キャッシュＬ１＄サイズよりも小さくないと判断された場合（ステップＳ１００２：Ｎｏ）、スケジューラ１１０は、全共有データをキャッシュＬ１＄に配置することはできない。したがって、スケジューラ１１０は、実行対象のタスクの共有データのうち、更新頻度の高い順番にキャッシュＬ１＄，Ｌ２＄に配置する（ステップＳ１００４）。すなわち、スケジューラ１１０は、ステップＳ１００４によって、共有データのうち更新頻度の高いデータから順番にキャッシュＬ１＄に配置し、キャッシュＬ１＄の容量がなくなると、続いて、残りの共有データのうち更新頻度の高いデータから順番にキャッシュＬ２＄に配置する。

以上説明したステップＳ１００２〜Ｓ１００４の処理は、高優先度タスクの共有データを配置する場合の手順を表している。一方、高優先度タスク以外のタスク（低優先度のタスク）の共有データは、更新頻度大となるデータを対象に、キャシュＬ１＄の空領域に配置される。

ステップＳ１００１において、実行対象となるタスクが高優先度タスクではないと判断された場合（ステップＳ１００１：Ｎｏ）、スケジューラ１１０は、共有データのうち、更新頻度の高いデータを対象として配置処理を行う。まず、スケジューラ１１０は、実行対象のタスクの共有データのうち、更新頻度大の全共有データサイズが未ロックのキャッシュＬ１＄サイズよりも小さいか否かを判断する（ステップＳ１００５）。未ロックのキャッシュＬ１＄サイズとは、キャッシュＬ１＄の全領域のうち、既に他の実行対象のタスクの共有データが配置されているロック領域以外の領域の容量を意味する。

ステップＳ１００５において、更新頻度大の全共有データサイズが未ロックのキャッシュＬ１＄サイズよりも小さいと判断された場合（ステップＳ１００５：Ｙｅｓ）、スケジューラ１１０は、更新頻度大の全共有データをキャッシュＬ１＄に配置できると判断する。したがって、スケジューラ１１０は、更新頻度大の共有データをキャッシュＬ１＄に配置して（ステップＳ１００６）、一連の処理を終了する。

一方、更新頻度大の全共有データサイズが未ロックのキャッシュＬ１＄サイズよりも小さくはないと判断された場合（ステップＳ１００５：Ｎｏ）、スケジューラ１１０は、更新頻度大の全共有データをキャッシュＬ１＄に配置できない。したがって、スケジューラ１１０は、実行対象のタスクの共有データのうち、更新頻度の高いデータを順番に、キャッシュＬ１＄，Ｌ２＄へ配置する（ステップＳ１００７）。すなわち、スケジューラ１１０は、ステップＳ１００４と同様に、共有データのうち、更新頻度の高いデータから順番にキャッシュＬ１＄へ配置する。そして、キャッシュＬ１＄の容量がなくなると、スケジューラ１１０は、続いて、残りの共有データのうち更新頻度の高いデータから順番にキャッシュＬ２＄へ配置する。

以上説明したように、低優先度タスクの共有データの場合、スケジューラ１１０は、高優先度タスクの共有データが配置されていないメモリ領域に、低優先度タスクの共有データを効率的に配置することができる。たとえ、アクセス速度の速いメモリ領域（例えば、キャッシュＬ１＄）に配置されても、高優先度タスクの共有データを配置する場合と異なり、低優先度タスクの共有データはロックされていないため、高優先度タスクの処理を邪魔するような事態を防ぐことができる。

（タスクテーブル作成処理）
図１１は、タスクテーブル作成処理の手順を示すフローチャートである。図１１のフローチャートは、マルチコアプロセッサシステム１００によって実行させるアプリケーションを構成するタスクのシミュレーションを行い、シミュレーション結果に基づいて、タスクの優先度を表すタスクテーブル１１１を作成する手順を表している。図１１の各処理を実行することによって、スケジューラ１１０が、各タスクの共有データを適切に配置するために必要な、タスクテーブル１１１を作成することができる。

図１１において、スケジューラ１１０は、まず、実行対象の各タスク中の各データサイズの解析を行う（ステップＳ１１０１）。続いて、スケジューラ１１０は、各タスクのデッドライン解析を行う（ステップＳ１１０２）。さらに、スケジューラ１１０は、タスク間のデータ依存解析を行う(ステップＳ１１０３)。以上説明したステップＳ１１０１〜Ｓ１１０３によって、スケジューラ１１０は、各タスクの構成を特定するために必要なデータを取得できる。ステップＳ１１０１〜Ｓ１１０３によって取得されたデータは、タスクテーブル１１１に格納され、後述する優先度を設定するためのシミュレーションに利用される。

続いて、スケジューラ１１０は、各タスクの中に未シミュレーションの並列タスクが存在するか否かを判断する（ステップＳ１１０４）。ステップＳ１１０４において、未シミュレーションの並列タスクが存在すると判断された場合（ステップＳ１１０４：Ｙｅｓ）、スケジューラ１１０は、未シミュレーションの並列タスクのいずれか１組の並列タスクのシミュレーションを実行する（ステップＳ１１０５）。

その後、スケジューラ１１０は、依存解析のあるデータの更新頻度を測定し（ステップＳ１１０６）、依存関係のあるデータの更新頻度がしきい値よりも大きいか否かを判断する（ステップＳ１１０７）。ステップＳ１１０７は、優先度の設定が必要か否かを判断するための処理である。

ステップＳ１１０７において、依存関係のあるデータの更新頻度がしきい値よりも大きい場合（ステップＳ１１０７：Ｙｅｓ）、スケジューラ１１０は、タスクテーブル１１１に格納されているデッドラインを基に優先度を設定する（ステップＳ１１０８）。一方、依存関係のあるデータの更新頻度がしきい値よりも大きくはない場合（ステップＳ１１０７：Ｎｏ）、一旦キャッシュに格納されても更新頻度が低いため、スケジューラ１１０は、優先度を決定せずに、ステップＳ１１０９の処理に移行する。

次に、スケジューラ１１０は、処理中の並列タスクをシミュレーション済タスクに設定し（ステップＳ１１０９）、ステップＳ１１０４の処理に戻り、未シミュレーションの並列タスクが存在するか否かを判断する。

ステップＳ１１０４において、未シミュレーションの並列タスクが存在すると判断される限り、スケジューラ１１０は、ステップＳ１１０５〜Ｓ１１０９の処理によってシミュレーションを繰り返して、並列タスクの優先度を設定する。ステップＳ１１０４において、未シミュレーションの並列タスクが存在しないと判断されると（ステップＳ１１０４：Ｎｏ）、スケジューラ１１０は、すべての並列タスクのシミュレーションが終了したため、一連の処理を終了する。

以上説明したように、スケジューラ１１０は、図１１の各処理を実行することによって、タスクテーブル１１１を作成することができる。なお、上述したタスクテーブル作成処理は、スケジューラ１１０が実行主体となっているが、他のコンパイラやシミュレータが実行主体となって事前に実行しておいてもよい。

例えば、ステップＳ１１０１〜Ｓ１１０３による解析は、一般的なコンパイラによって実行することができる。また、ステップＳ１１０１〜Ｓ１１０３による解析結果を利用したステップＳ１１０５におけるシミュレーションも、各タスクを実行した場合の実行時間や更新回数を見積もる公知のシミュレータによって実行することができる（例えば、特開２０００−２７６３８１参照。）。

図１２は、タスクテーブルのデータ構造例を示すデータテーブルである。また、図１３は、タスクテーブルの設定例を示すデータテーブルである。図１２のデータテーブル１２００は、図１１にて説明したタスクテーブル作成処理によって作成されたタスクテーブル１１１のデータ構造例を表している。

タスクテーブル１１１は、図１２のデータテーブル１２００のように、タスク情報を表す下記の情報群のフィールドと、共有データ情報を表す下記の情報群のフィールドとから構成されている。なお、タスクテーブル１１１のうち、タスク名、タスクＩＤ、デッドラインなど、値が空白のフィードは、タスク毎に異なる値が入力される。また、優先度やコヒーレンスモードなど、値が○／×のように二値となっているフィールドは、二値のいずれかの値が入力される。

＜タスク情報＞
・タスク名 ：（タスクの名称）
・タスクＩＤ ：（タスクの識別子）
・デッドライン ：（ステップＳ１１０２の解析結果）
・優先度 ：高／低（ステップＳ１１０８の設定内容）
・コヒーレンスモード ：Ｗｒｉｔｅ時更新／ｒｅａｄ時更新
・他のＣＰＵへのｆｏｒｋ：許可／不許可

＜共有データ情報＞
・共有データ名 ：（データの名称）
・共有データＩＤ ：（データのＩＤ）
・更新回数 ：（ステップＳ１１０６の測定結果）
・配置されるキャッシュレベル：Ｌ１（キャッシュＬ１＄）／Ｌ２（キャッシュＬ２＄）
・データサイズ ：（ステップＳ１１０１の解析結果）

上記のタスク情報のうち、コヒーレンスモード、他のＣＰＵへのｆｏｒｋおよび配置されるキャッシュレベルは、タスク実行時に決定される。具体的には、コヒーレンスモード、他のＣＰＵへのｆｏｒｋは、後述する図１４〜１７によって説明されるタスク実行処理によって決定される。また、配置されるキャッシュレベルは、上述の図１０によって説明した共有データの配置処理によって決定される。なお、タスクテーブル１１１の具体的な数値が設定された、データテーブル１２００を図１３に例示している。

（タスク実行処理）
図１４〜１７は、タスク実行処理の手順を示すフローチャートである。図１４〜１７のフローチャートは、スケジューラ１１０が、実行対象となる並列タスクを各プロセッサに実行させる際の手順を表している。図１４〜１７の各処理を実行することによって、実行対象となる並列タスクは、タスクテーブル１１１に設定されている優先度や、実行中の他の並列タスクの優先度に応じたコヒーレンス手法に基づいて実行される。

図１４において、スケジューラ１１０は、まず、実行対象のタスクにおいて状態遷移が発生したか否かを判断する（ステップＳ１４０１）。ステップＳ１４０１における状態遷移とは、「タスク生成」、「タスク終了」および「タスクスイッチ」を意味する。したがって、ステップＳ１４０１において、状態遷移が発生したと判断された場合、スケジューラ１１０は、さらに、上記の３種類の中のいずれの状態になったかを判断する。

ステップＳ１４０１において、スケジューラ１１０は、状態遷移が発生するまで待機状態となる（ステップＳ１４０１：Ｎｏのループ）。ステップＳ１４０１において、状態遷移のうち、タスク生成が発生したと判断された場合（ステップＳ１４０１：Ｙｅｓタスク生成）、スケジューラ１１０は、実行対象のタスクが並列タスクか否かを判断する（ステップＳ１４０２）。

ステップＳ１４０２において、実行対象のタスクが並列タスクであると判断された場合（ステップＳ１４０２：Ｙｅｓ）、スケジューラ１１０は、新たに生成された並列タスクが、Ｍａｓｔｅｒスレッドか否かを判断する（ステップＳ１４０３）。Ｍａｓｔｅｒスレッドとは、優先的に実行されるスレッドである。

ステップＳ１４０３において、新たに生成された並列タスクが、Ｍａｓｔｅｒスレッドであると判断された場合（ステップＳ１４０３：Ｙｅｓ）、スケジューラ１１０は、さらに、新たに生成された並列タスクが、高優先度タスクか否かを判断する（ステップＳ１４０４）。ステップＳ１４０４において、高優先度タスクか否かは、タスクテーブル１１１を参照して判断することができる。

ステップＳ１４０４において、新たに生成された並列タスクが、高優先度タスクであると判断された場合（ステップＳ１４０４：Ｙｅｓ）、スケジューラ１１０は、さらに、ＣＰＵにおいて高優先度タスクを実行中か否かを判断する（ステップＳ１４０５）。

ステップＳ１４０５において、高優先度タスクを実行中であると判断された場合（ステップＳ１４０５：Ｙｅｓ）、スケジューラ１１０は、実行対象のタスクを実行に移すための準備処理を行う。すなわち、スケジューラ１１０は、実行中の並列タスクを、並列スレッドを実行中のＣＰＵの中で負荷最小のＣＰＵにｍｉｇｒａｔｉｏｎ（データ移行）し、実行中に新たなスレッドの他のＣＰＵへのｆｏｒｋ（新たなスレッドのコピー生成）を禁止する（ステップＳ１４０６）。

さらに、スケジューラ１１０は、ステップＳ１４０６において、ｍｉｇｒａｔｉｏｎしたタスクの共有データを配置したキャッシュ領域を、ロックする（ステップＳ１４０７）。そして、スケジューラ１１０は、ｍｉｇｒａｔｉｏｎしたタスクを逐次実行し（ステップＳ１４０８）、新たに生成された並列タスクにおいてスレッドの他のＣＰＵへのｆｏｒｋを禁止し、負荷最小のＣＰＵに割り当てる（ステップＳ１４０９）。

その後、スケジューラ１１０は、新たに生成された並列タスクの共有データを配置したキャッシュ領域をロックし、タスクの実行を開始する（ステップＳ１４１０）。ステップＳ１４１０の処理が終了すると、スケジューラ１１０は、ステップＳ１４０１の処理に戻り、新たに状態遷移が発生するまで待機状態となる。

また、ステップＳ１４０３において、新たに生成された並列タスクがＭａｓｔｅｒスレッドではないと判断された場合（ステップＳ１４０３：Ｎｏ）、スケジューラ１１０は、スレッドのｆｏｒｋが禁止されているか否かを判断する（ステップＳ１４１１）。ステップＳ１４０３において、判断基準となっているスレッドとは、新たに生成されたタスクを構成するスレッドである。

ステップＳ１４０３において、新たに生成されたタスクのスレッドのｆｏｒｋが禁止されていると判断された場合（ステップＳ１４１１：Ｙｅｓ）、スケジューラ１１０は、新たに生成されたタスクをＭａｓｔｅｒスレッドが実行されるＣＰＵと同じＣＰＵにキューイングする（ステップＳ１４１２）。ステップＳ１４１２の処理によってキューイングされたタスクは、キューイング先のＣＰＵによって、現在実行中のタスクの終了後に実行される。スケジューラ１１０は、ステップＳ１４１２の処理が終了すると、ステップＳ１４０１の処理に戻り、新たに状態遷移が発生するまで待機状態となる。

また、スケジューラ１１０は、新たに生成されたタスクが並列タスクではないと判断された場合（ステップＳ１４０２：Ｎｏ）、または、スレッドのｆｏｒｋが禁止されていないと判断された場合（ステップＳ１４１１：Ｎｏ）、タスクを負荷最小のＣＰＵにキューイングする（ステップＳ１４１３）。ステップＳ１４１３によってキューイングされるタスクは、ステップＳ１４０１によって新たに生成されたと判断されたタスクである。スケジューラ１１０は、ステップＳ１４１３の処理が終了すると、ステップＳ１４０１の処理に戻り、新たに状態遷移が発生するまで待機状態となる。

図１５のフローチャートは、ステップＳ１４０１において、タスク終了が発生したと判断された場合（１４０１：Ｙｅｓタスク終了）と、タスクスイッチが発生したと判断された場合（ステップＳ１４０１：Ｙｅｓタスクスイッチ）とにおけるスケジューラ１１０の処理を表している。

図１５において、スケジューラ１１０は、まず、ステップＳ１４０１において、タスク終了が発生したと判断された場合（１４０１：Ｙｅｓタスク終了）、ロックしていた並列タスクの共有データを配置したキャッシュ領域を、開放する（ステップＳ１５０１）。

その後、スケジューラ１１０は、実行待ちのタスクがあるか否かを判断する（ステップＳ１５０２）。ステップＳ１５０２において、実行待ちのタスクがあると判断された場合（ステップＳ１５０２：Ｙｅｓ）、スケジューラ１１０は、ステップＳ１５０３に移行して、実行待ちのタスクを実行するための処理を行う。一方、ステップＳ１５０２において、実行待ちのタスクがないと判断された場合（ステップＳ１５０２：Ｎｏ）、スケジューラ１１０は、図１４のステップＳ１４０１の処理に戻り、次の状態遷移が発生するまで待機状態となる。

一方、ステップＳ１４０１において、タスクスイッチが発生したと判断された場合（１４０１：Ｙｅｓタスクスイッチ）、スケジューラ１１０は、タスクの実行権を渡すのが低優先度の並列タスクか否かを判断する（ステップＳ１５０３）。なお、ステップＳ１５０２において、実行待ちのタスクがあると判断された場合（ステップＳ１５０２：Ｙｅｓ）も、スケジューラ１１０は、ステップＳ１５０３の判断処理を行う。

ステップＳ１５０３において、タスクの実行権を渡すのが低優先度の並列タスクであると判断された場合（ステップＳ１５０３：Ｙｅｓ）、スケジューラ１１０は、低優先度の並列タスクを実行する際のキャッシュコヒーレンス方式を採用する。すなわち、スケジューラ１１０は、ＣＰＵのキャシュコヒーレンス方式を、他のＣＰＵがデータにアクセスしたときにスヌープ機構が動作するモードに設定する（ステップＳ１５０４）。

ステップＳ１５０３において、タスクの実行権を渡すのが低優先度の並列タスクではないと判断された場合（ステップＳ１５０３：Ｎｏ）、または、ステップＳ１５０４の処理が終了すると、スケジューラ１１０は、実行対象となるタスクの実行を開始する（ステップＳ１５０５）。ステップＳ１５０５によってタスクが実行されると、スケジューラ１１０は、ステップＳ１４０１の処理に戻り、次のタスクの状態遷移が発生するまで待機状態となる。

図１６のフローチャートは、ステップＳ１４０４において、新たに生成された並列タスクが、高優先度タスクではないと判断された場合（ステップＳ１４０４：Ｎｏ）のスケジューラ１１０の処理を表している。

図１６において、スケジューラ１１０は、まず、ステップＳ１４０４にて新たに生成された並列タスクが、高優先度タスクではないと判断された場合（ステップＳ１４０４：Ｎｏ）、高優先度タスクを実行中か否かを判断する（ステップＳ１６０１）。なお、ステップＳ１６０１では、新たに生成されたタスクを実行させるＣＰＵにおいて、現在、高優先度タスクが実行されているか否かを判断する。

ステップＳ１６０１において、高優先度タスクを実行中であると判断された場合（ステップＳ１６０１：Ｙｅｓ）、スケジューラ１１０は、低優先度の並列タスクを実行する際のキャッシュコヒーレンス方式を採用する。すなわち、スケジューラ１１０は、実行中の並列タスクのキャシュコヒーレンス方式を、他のＣＰＵがデータにアクセスするときにスヌープ１２０のスヌープ機構が動作するモードに設定する（ステップＳ１６０２）。

その後、スケジューラ１１０は、実行対象となるタスクを負荷最小のＣＰＵにキューイングして（ステップＳ１６０３）、ステップＳ１４０１の処理に移行する。ステップＳ１６０３において、キューイングされたタスクは、現在実行中のタスクが終了した後、実行される。負荷最小のＣＰＵとは、キューイング済のタスクの処理量が最小のＣＰＵを意味する。なお、ステップＳ１４０１に移行したスケジューラ１１０は、次に遷移状態が発生するまで待機状態となる。

ステップＳ１６０１において、高優先度タスクを実行中ではないと判断された場合（ステップＳ１６０１：Ｎｏ）、スケジューラ１１０は、高優先度の並列タスクを実行する際のキャッシュコヒーレンス方式を採用する。すなわち、スケジューラ１１０は、実行中の並列タスクを、並列タスクに含まれる並列スレッドを実行中の他のＣＰＵの中で負荷最小のＣＰＵにｍｉｇｒａｔｉｏｎし、実行中に並列タスクに含まれる新たなスレッドの他のＣＰＵへのｆｏｒｋを禁止する（ステップＳ１６０４）。

さらに、スケジューラ１１０は、ステップＳ１６０４において、ｍｉｇｒａｔｉｏｎしたタスクを逐次実行させる（ステップＳ１６０５）。そして、スケジューラ１１０は、新たに生成された並列タスクにおいて、並列タスクに含まれるスレッドの他のＣＰＵへのｆｏｒｋを禁止し、負荷最小のＣＰＵにキューイングする（ステップＳ１６０６）。

ステップＳ１６０６によって、キューイングされたタスクは、現在実行中のタスクが終了した後、実行される。また、ステップＳ１６０６が終了すると、スケジューラ１１０は、ステップＳ１４０１の処理に移行して、新たな状態遷移が発生するまで待機状態となる。

図１７のフローチャートは、ステップＳ１４０５において、新たに生成された並列タスクが、高優先度タスクを実行中ではないと判断された場合（ステップＳ１４０５：Ｎｏ）のスケジューラ１１０の処理を表している。

図１７において、スケジューラ１１０は、まず、ステップＳ１４０５にて対象となるＣＰＵが高優先度タスクを実行中ではないと判断された場合（ステップＳ１４０５：Ｎｏ）、新たに生成されたタスクを負荷最小のＣＰＵに割り当てる（ステップＳ１７０１）。

そして、スケジューラ１１０は、新たに生成された並列タスクが逐次実行ではデッドライン制約を満たさないか否かを判断する（ステップＳ１７０２）。ステップＳ１７０２において、スケジューラ１１０は、タスクテーブル１１１に設定されているデッドライン制約に基づいてデットライン制約を満たさないか否かの判断を行う。

ステップＳ１７０２において、デッドライン制約を満たさないと判断された場合（ステップＳ１７０２：Ｙｅｓ）、スケジューラ１１０は、さらに、現在低優先度の並列タスクを実行中か否かを判断する（ステップＳ１７０３）。

ステップＳ１７０３において、低優先度の並列タスクが実行中と判断された場合（ステップＳ１７０３：Ｙｅｓ）、スケジューラ１１０は、低優先度の並列タスクを実行する際のキャッシュコヒーレンス方式を採用する。すなわち、スケジューラ１１０は、実行中の並列タスクのコヒーレンス方式を、他のＣＰＵがデータにアクセスした時にスヌープ機構が動作するモードに設定する（ステップＳ１７０４）。

ステップＳ１７０４の処理が終了すると、スケジューラ１１０は、新たに生成された並列タスクの共有データを配置したキャシュ領域をロックする（ステップＳ１７０５）。また、ステップＳ１７０３において、低優先度の並列タスクを実行中ではないと判断された場合（ステップＳ１７０３：Ｎｏ）、スケジューラ１１０は、通常のコヒーレンス方式を採用するため、ステップＳ１７０４の処理を行わずに、ステップＳ１７０５の処理に移行する。

ステップＳ１７０５の処理が終了すると、スケジューラ１１０は、新たに生成された並列タスクの実行を開始させ（ステップＳ１７０６）、ステップＳ１４０１の処理に戻り、次のタスクの状態遷移が発生するまで待機状態となる。

一方、ステップＳ１７０２において、デッドライン制約を満たすと判断された場合（ステップＳ１７０２：Ｎｏ）、スケジューラ１１０は、新たに生成された並列タスクの共有データを配置したキャッシュ領域を、ロックする（ステップＳ１７０７）。

そして、スケジューラ１１０は、新たに生成された並列タスクの逐次実行を開始させる（ステップＳ１７０８）。その後、スケジューラ１１０は、ステップＳ１４０１の処理に戻り、次のタスクの状態遷移が発生するまで待機状態となる。

以上説明したように、スケジューラ１１０は、並列タスクとして特定された各タスクにそれぞれ、どのような優先度（高優先度／低優先度）が設定されているか、さらに、並列タスク同士が同一の優先度であるかに応じて、最適なＣＰＵに実行されるようにスケジューリングすることができる。また、スケジューラ１１０は、各タスクの優先度に応じて共有データのキャッシュコヒーレンス方式を設定するため、キャッシュメモリ（キャッシュＬ１＄）の利用効率の低下を防ぐことができる。

（適用例）
次に、本実施の形態にかかるスケジューリング処理を通信機器に適用させた場合の動作例について説明する。具体的には、スマートフォンなどの携帯型の通信機器と、サーバなどの固定型の通信機器とによってそれぞれ実行される並列タスクについて説明する。

＜同一優先度の並列タスクの場合＞
図１８は、同一優先度の並列タスクの実行例を示す説明図である。図１８では、スマートフォン１８０１は、他のスマートフォン１８０２とＷＬＡＮ（Ｗｉｒｅｌｅｓｓ ＬＡＮ）の規格に準拠した通信を行っている。さらに、スマートフォン１８０１は、サーバ１８０３ともＬＴＥ（Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ）の規格に準拠した通信を行っている。

ＷＬＡＮの規格に沿ったタスク（ＷＬＡＮ＃０，１）と、ＬＴＥの規格に沿ったタスク（ＬＴＥ＃０，１）は、共にリアルタイム制約があるため高優先度タスクとなる。したがって、スマートフォン１８０１は、ＷＬＡＮ＃０，１およびＬＴＥ＃０，１を、同一優先度の並列タスクとして実行する。スマートフォン１８０１のスヌープ１２０では、同一優先度の並列タスクが実行されるため、通常のキャッシュコヒーレンシを行うスヌープ方式が採用される。

＜優先度の異なる並列タスクの場合＞
図１９は、優先度の異なる並列タスクの実行例を示す説明図である。図１９では、スマートフォン１８０１が、サーバ１８０３とＬＴＥの規格に準拠した通信を行っている。また、スマートフォン１８０１では、通信を必要としないドライバのアプリケーションについてのタスク（ｄｒｉｖｅｒ＃０，１）が実行されている。

スマートフォン１８０１によって実行されているドライバのアプリケーションは、リアルタイム制約が設けられていないため、低優先度タスクとなる。したがって、スマートフォン１８０１は、ＬＴＥ＃０，１を、高優先度の並列タスクとして実行し、ｄｒｉｖｅｒ＃０，１を、低優先度の並列タスクとして実行する。優先度の異なる並列タスクが実行されるため、スマートフォン１８０１のスヌープ１２０では、ＬＴＥ＃０，１に対して低優先度並列タスクにおけるキャッシュコヒーレンシを行うスヌープ方式が採用される。

以上説明したように、スケジューラ、マルチコアプロセッサシステムおよびスケジューリング方法によれば、利用頻度の高い共有データを、アクセス速度の速いキャッシュメモリに優先的に配置するため、処理速度を向上させることができる。

また、低優先度に設定された処理の共有データの場合、ＣＰＵからのアクセス要求が発生するまで、キャッシュコヒーレンシによる同期処理を延期する。すなわち、再利用性のない共有データをキャッシュメモリに書き込むといった、マルチコアプロセッサシステムの処理性能の低下の原因となる処理を回避することができる。したがって、並列処理およびマルチタスク処理が実行される場合であっても、キャッシュの利用効率を高めてマルチコアプロセッサシステムの処理能力を向上させることができる。

また、高優先度タスクがなく、キャッシュメモリに空き領域がある場合には、低優先度タスクの共有データを、各ＣＰＵのキャッシュメモリに配置してもよい。したがって、高優先後タスクが存在しない場合であっても、キャッシュメモリを効率的に利用させることができる。

さらに、キャッシュメモリに配置した高優先度タスクの実行時にアクセスされる共有データは、高優先度タスクが終了するまでロックされるように設定してもよい。共有データをロックすることによって、タスクスイッチが発生しても、他のタスクの共有データによって高優先度タスクの共有データが書き換えられてしまうような事態を防ぎ、高優先度タスクを効率的に実行させることができる。

また、高優先度タスクが実行時にアクセスする共有データが、キャッシュメモリの容量よりも大きく、キャッシュメモリに配置しきれない場合には、キャッシュメモリ以外のメモリ領域のうち、アクセス速度の速いメモリ領域に共有データを配置してもよい。また、共有メモリを配置する際に、複数のメモリ領域が存在する場合には、アクセス速度の早いメモリから順番に共有データを配置する。したがって、高優先度タスクの共有データを優先的にアクセス速度の速いメモリ領域に配置するため、効率的な処理を期待することができる。

さらに、高優先度タスクが実行時にアクセスする共有データが、キャッシュメモリの容量よりも小さく、キャッシュメモリに余裕がある場合には、余った領域に低優先度タスクの共有データを配置してもよい。余った領域に低優先度タスクの共有データを配置することによって、キャッシュメモリの空き容量を防ぎ、高い利用効率を維持することができる。

また、各ＣＰＵのキャシュメモリの他のメモリ領域として、複数のメモリ領域が用意されている場合には、アクセス速度の速いメモリ領域から順番に共有データを配置してもよい。優先度にかかわらず、各タスクの共有データをアクセス速度の速いメモリ領域に優先的に配置することによって、各タスクを効率的に実行させることができる。

さらに、実行対象となるタスクの中から並列タスクを抽出して、同一のプロセッサに割り当ててもよい。さらに、並列タスクのうち優先度も同一の並列タスクを抽出して同一のプロセッサに割り当ててもよい。優先度が同一の並列タスクが同一のプロセッサに割り当てられることによって、一旦キャシュメモリに配置した共有データを効率的に利用することができる。

なお、本実施の形態で説明したスケジューリング方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。本スケジューラは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本スケジューラは、インターネットなどのネットワークを介して配布してもよい。

１００ マルチコアプロセッサシステム
１１０ スケジューラ
１２０ スヌープ
１３０ メモリコントローラ
１４０ メモリ
１５０ ファイルシステム
１０００ アプリケーション
１００１ 判断部
１００２ 第１配置部
１００３ 第２配置部
１００４ 第３配置部
１００５ 特定部
１００６ 抽出部
１００７ 割当部

Claims (11)

1. マルチコアプロセッサの各プロセッサに割り当てて実行させる処理群のうち前記各プロセッサに割り当てられる実行対象処理の優先度が、しきい値以上か否かを判断する判断工程と、
   前記判断工程によって、前記実行対象処理のうち、前記しきい値以上の優先度であると判断された高優先度の実行対象処理が実行時にアクセスするデータを、前記高優先度の実行対象処理を実行する前に、前記高優先度の実行対象処理を実行する各プロセッサのキャッシュメモリに配置する第１の配置工程と、
   前記判断工程によって、前記実行対象処理のうち、前記しきい値以上の優先度でないと判断された低優先度の実行対象処理が実行時にアクセスするデータを、前記各プロセッサのキャッシュメモリよりアクセス速度の遅い他のメモリ領域に配置する第２の配置工程と、
   前記マルチコアプロセッサの中の一のプロセッサにおいて、前記他のメモリ領域に配置されたデータへのアクセス要求が発生した場合に、前記他のメモリ領域に配置されたデータを前記一のプロセッサのキャッシュメモリに配置する第３の配置工程と、
   を前記マルチコアプロセッサ内の特定のプロセッサに実行させることを特徴とするスケジューラ。
2. 前記第１の配置工程は、
   前記判断工程によって、前記実行対象処理のうち、前記しきい値以上の優先度であると判断された前記高優先度の実行対象処理がなかった場合、前記実行対象処理のうち、前記低優先度の実行対象処理が実行時にアクセスするデータを、前記低優先度の実行対象処理を実行する各プロセッサのキャッシュメモリに配置することを特徴とする請求項１に記載のスケジューラ。
3. 前記第１の配置工程は、
   前記高優先度の実行対象処理を実行する各プロセッサのキャッシュメモリに配置した、前記高優先度の実行対象処理が実行時にアクセスするデータに対して、前記高優先度の実行対象処理の実行が終了するまで他のデータによる上書きを禁止することを特徴とする請求項１に記載のスケジューラ。
4. 前記判断工程によって前記実行対象処理の優先度が、しきい値以上か否かの判断が行われると、前記マルチコアプロセッサの各プロセッサのキャッシュメモリの中の書き換え可能な領域の容量を特定する特定工程を、前記特定のプロセッサに実行させ、
   前記第１の配置工程は、
   前記特定工程によって特定された書き換え可能な領域の容量が、前記高優先度の実行対象処理が実行時にアクセスするデータの容量よりも小さい場合、当該データのうち、更新頻度が高いデータの順に前記キャッシュメモリに配置可能な容量分配置し、
   前記第２の配置工程は、
   前記第１の配置工程によって前記キャッシュメモリに配置できなかったデータを前記他のメモリ領域に配置することを特徴とする請求項１に記載のスケジューラ。
5. 前記第１の配置工程は、
   前記特定工程によって特定された書き換え可能な領域の容量が、前記高優先度の実行対象処理が実行時にアクセスするデータの容量よりも大きい場合、前記高優先度の実行対象処理が実行時にアクセスするデータの配置が終了した後、前記低優先度の実行対象処理が実行時にアクセスするデータのうち、更新頻度が高いデータの順に前記キャッシュメモリに配置可能な容量分配置することを特徴とする請求項４に記載のスケジューラ。
6. 前記第２の配置工程は、
   前記他のメモリ領域としてアクセス速度の異なる複数種類のメモリが用意されている場合、前記低優先度の実行対象処理が実行時にアクセスするデータを、前記他のメモリ領域のうち、アクセス速度の速いメモリの順に配置可能な容量分配置することを特徴とする請求項１に記載のスケジューラ。
7. 前記実行対象処理のうち、実行時にアクセスするデータが共通する処理を抽出する抽出工程と、
   前記抽出工程によって抽出された処理を前記マルチコアプロセッサの中の同一のプロセッサに割り当てる割当工程と、
   を前記特定のプロセッサに実行させることを特徴とする請求項１〜６のいずれか一つに記載のスケジューラ。
8. 前記割当工程は、
   前記抽出工程によって抽出された処理のうち、同一の優先度が設定されている処理を、前記マルチコアプロセッサの中の同一のプロセッサに割り当てることを特徴とする請求項７に記載のスケジューラ。
9. 前記マルチコアプロセッサの中の一のプロセッサにおいて、前記低優先度の実行対象処理が実行時にアクセスするデータへのアクセス要求が発生するまで、前記低優先度の実行対象処理が実行時にアクセスするデータに対してキャッシュコヒーレンシによる同期処理を延期する同期制御工程、
   を前記特定のプロセッサに実行させることを特徴とする請求項１に記載のスケジューラ。
10. マルチコアプロセッサの各プロセッサに割り当てて実行させる処理群のうち前記各プロセッサに割り当てられる実行対象処理の優先度が、しきい値以上か否かを判断する判断手段と、
    前記判断手段によって、前記実行対象処理のうち、前記しきい値以上の優先度であると判断された高優先度の実行対象処理が実行時にアクセスするデータを、前記高優先度の実行対象処理を実行する前に、前記高優先度の実行対象処理を実行する各プロセッサのキャッシュメモリに配置する第１の配置手段と、
    前記判断手段によって、前記実行対象処理のうち、前記しきい値以上の優先度でないと判断された低優先度の実行対象処理が実行時にアクセスするデータを、前記各プロセッサのキャッシュメモリよりアクセス速度の遅い他のメモリ領域に配置する第２の配置手段と、
    前記マルチコアプロセッサの中の一のプロセッサにおいて、前記他のメモリ領域に配置されたデータへのアクセス要求が発生した場合に、前記他のメモリ領域に配置されたデータを前記一のプロセッサのキャッシュメモリに配置する第３の配置手段と、
    を備えることを特徴とするマルチコアプロセッサシステム。
11. マルチコアプロセッサの各プロセッサに割り当てて実行させる処理群のうち前記各プロセッサに割り当てられる実行対象処理の優先度が、しきい値以上か否かを判断する判断工程と、
    前記判断工程によって、前記実行対象処理のうち、前記しきい値以上の優先度であると判断された高優先度の実行対象処理が実行時にアクセスするデータを、前記高優先度の実行対象処理を実行する前に、前記高優先度の実行対象処理を実行する各プロセッサのキャッシュメモリに配置する第１の配置工程と、
    前記判断工程によって、前記実行対象処理のうち、前記しきい値以上の優先度でないと判断された低優先度の実行対象処理が実行時にアクセスするデータを、前記各プロセッサのキャッシュメモリよりアクセス速度の遅い他のメモリ領域に配置する第２の配置工程と、
    前記マルチコアプロセッサの中の一のプロセッサにおいて、前記他のメモリ領域に配置されたデータへのアクセス要求が発生した場合に、前記他のメモリ領域に配置されたデータを前記一のプロセッサのキャッシュメモリに配置する第３の配置工程と、
    を前記マルチコアプロセッサ内の特定のプロセッサが実行することを特徴とするスケジューリング方法。

Images