(57)【要約】本発明は、マルチプロセッサにおけるアプリケーションタスクに対する動的なキャッシュパーティショニング方法及びシステムを提供する。又、アプリケーションタスクの実行フェーズに基づいてキャッシュパーティションを動的にリサイズする手段を提供する。アプリケーションタスクの実行フェーズを表形式で識別し且つ更新する。キャッシュパーティションは、アプリケーションタスクの特定の実行瞬時でリサイズし、いかなる所定の時点でも、必要で充分な量のキャッシュスペースがアプリケーションタスクに割当てられるようにする。キャッシュパーティションのサイズは、動的に又は静的にモニタリングされるタスクのワーキングセット条件に応じてその実行中に決定される。キャッシュパーティションはタスクの実行フェーズに応じて動的にリサイズし、キャッシュ全体の不必要な予約を回避し、従って、キャッシュの有効利用を達成する。
2009528610.tif 000002
【特許請求の範囲】
【請求項１】
複数のアプリケーションタスクに対するマルチプロセッサにおけるキャッシュパーティションを動的にリサイズするリサイズ方法であって、前記マルチプロセッサは、前記複数のアプリケーションタスクを実行することができるとともに、主メモリ及びキャッシュメモリを有し、このキャッシュメモリは一組のキャッシュパーティションを有するようにする当該リサイズ方法において、このリサイズ方法が、
前記複数のアプリケーションタスクの実行フェーズを識別するとともにモニタリングする工程と、
前記実行フェーズと、現在のアプリケーションタスクのワーキングセットとに関する情報を維持及び更新する工程と、
前記現在のアプリケーションタスクの実行フェーズに動的に依存して前記キャッシュパーティションを構成し、これにより実行タスクの全実行期間に亘るこれら実行タスクに対するキャッシュパーティションの余分な予約を回避する工程と
を有するリサイズ方法。
【請求項２】
請求項１に記載のリサイズ方法において、前記アプリケーションタスクが一連の命令を有するようにするリサイズ方法。
【請求項３】
請求項１に記載のリサイズ方法において、前記アプリケーションタスクの実行フェーズが、アプリケーションタスクの実行中に、同様な作用を有する一組のインターバルを有するようにするリサイズ方法。
【請求項４】
請求項１に記載のリサイズ方法において、アプリケーションタスクの前記ワーキングセットが、特定の実行フェーズにおいてアプリケーションタスクのキャッシュパーティションの条件を有するようにするリサイズ方法。
【請求項５】
請求項１に記載のリサイズ方法において、前記実行タスクの実行フェーズのモニタリングを静的に実施し、キャッシュパーティションのサイズは、実行中のアプリケーションタスクのワーキングセット条件に応じて決定するリサイズ方法。
【請求項６】
請求項１に記載のリサイズ方法において、前記実行タスクの実行フェーズのモニタリングを動的に実施し、キャッシュパーティションのサイズは、実行中のアプリケーションタスクのワーキングセット条件に応じて決定するリサイズ方法。
【請求項７】
請求項１に記載のリサイズ方法において、より優先度の高いタスクが生じた場合に、このより優先度の高いタスクに、適切なキャッシュパーティションを割当て、これによりこのより優先度の高いタスクのワーキングセットの充分な部分がキャッシュ上にマッピングされうるようにするリサイズ方法。
【請求項８】
請求項１に記載のリサイズ方法において、各アプリケーションタスクに対し割当てられたキャッシュパーティションが実行フェーズに応じて変化し、これにより、いかなる所定の時点でも最適量のキャッシュスペースが割当てられるようにするリサイズ方法。
【請求項９】
複数のアプリケーションタスクに対するマルチプロセッサにおけるキャッシュパーティションを動的にリサイズするリサイズシステムであって、前記マルチプロセッサは、前記複数のアプリケーションタスクを実行することができるとともに、主メモリ及びキャッシュメモリを有し、このキャッシュメモリは一組のキャッシュパーティションを有している当該リサイズシステムにおいて、このリサイズシステムが、
アプリケーションタスクのワーキングセット変化をモニタリングするタスクフェーズモニタと、
このタスクフェーズモニタからのアプリケーションタスクに関する情報を記憶する記憶装置と、
新たなアプリケーションタスクが現在実行しているアプリケーションタスクに割込む場合に、最大のキャッシュサイズを割当てるためのキャッシュ割当てコントローラと
を有するリサイズシステム。
【請求項１０】
請求項９に記載のリサイズシステムにおいて、前記記憶装置がタスクフェーズテーブルを有し、このタスクフェーズテーブルが、アプリケーションタスクのフェーズ情報と、タスクの切換え時に各アプリケーションタスクに割当てられるキャッシュパーティションのサイズとを有し、各アプリケーションタスクに割当てられるキャッシュパーティションのこのサイズが、対応するフェーズにおけるタスクのワーキングセットを有するリサイズシステム。
【請求項１１】
請求項９に記載のリサイズシステムにおいて、前記タスクフェーズモニタは、前記ワーキングセット変化を静的にモニタリングし、このワーキングセット変化をタスクフェーズテーブルに記憶するようになっているリサイズシステム。
【請求項１２】
請求項９に記載のリサイズシステムにおいて、前記タスクフェーズモニタは、前記ワーキングセット変化を動的にモニタリングし、このワーキングセット変化をタスクフェーズテーブルに記憶するようになっているリサイズシステム。
【請求項１３】
請求項９に記載のリサイズシステムにおいて、アプリケーションタスクが一連の命令を有しているリサイズシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、キャッシュ記憶装置を有するデータプロセスシステムに関するものであり、特にマルチプロセッサ内のアプリケーションタスクに対するキャッシュ記憶装置のダイナミックパーティショニングに関するものである。
【背景技術】
【０００２】
キャッシュパーティショニングは、リソース妨害を低減させることにより、キャッシュ性能をより一層予知しうるようにするマルチタスクシステムにおける周知の技術である。マルチプロセッサを有するデータプロセスシステムでは、キャッシュ記憶装置が複数のプロセッサ、すなわちタスク間で共有される。キャッシュ記憶装置は、異なるアプリケーションタスクに対する種々の区分にパーティショニングされる。キャッシュ記憶装置は、各区分が、このキャッシュ記憶装置の全体を共有するプロセスではなくそれぞれのクラスのプロセスに割当てられるように、区分にパーティショニングするのが有利である。キャッシュ記憶装置を多数の区分にパーティショニングする場合、異なるアプリケーションタスクに対するキャッシュ（記憶装置）のパーティションのサイズを如何にして決定するかという問題や、キャッシュ記憶装置のパーティションをいつリサイズ（サイズ変更）するかという問題が生じる。
【０００３】
Henk Muller 氏等による米国公開特許第２００２／０００２６５７号明細書には、プロセッサが複数のプロセスを実行しうるようにしたシステムにおけるキャッシュメモリの動作方法が開示されている。このような技術によれば、異なるデータオブジェクトへのアクセスが妨害を生じるおそれのある１つのモノリシックデータキャッシュを用いる代わりに、キャッシュメモリを多くの小さいパーティションにパーティショニングする。このような場合、代表的に、コンパイラがキャッシュアーキテクチャを知っており、キャッシュメモリのパーティションをタスクに割当てる。このような技術は、キャッシュメモリのパーティショニングされた区分をその全実行期間中タスクに予約する。従って、静的なパーティショニング技術はしばしば、キャッシュメモリの利用を次善的なものとするか、キャッシュメモリのパーティションの予約を不充分なものとする。
【０００４】
文献“Analytical Cache Models with applications to cache partitioning ”（著者：Edward Suh氏等）で提案されている動的なパーティショニング技術は、パーティションのサイズを動的にリサイズすることにより、静的なパーティショニングの上述した欠点を回避しようとするものである。このような技術は、個々のタスクの段階的な実行のようなプログラム特性を考慮していない。例えば、マルチメディアアプリケーションの実行動作はしばしば、キャッシュメモリの利用特性が異なるおそれのある繰り返し動作（フェーズ）に陥る。有効なキャッシュメモリの利用は、プログラムフェーズの境界でパーティションのサイズを決定することにより達成しうる。
【０００５】
文献“Discovering and exploiting program phases ”（Timothy Sherwoor氏等著）にはプログラム動作におけるフェーズを正確に特定及び推定することができるということが記載されている。これらのフェーズにおけるプログラム（タスク）動作は互いに異なるリソース使用特性を有しており、性能特性基準を用いて定量化しうる。このような測定基準の例は、この文献に記載されている基本ブロックベクトル（ＢＢＶ）である。
【０００６】
現在のキャッシュパーティショニング技術は、アプリケーションタスクに対するキャッシュ記憶装置のパーティショニングされた区分をこれらの全実行期間の間予約する。しかし、メディアプロセスタスクは識別可能な実行フェーズを有し、キャッシュ条件はこれらのフェーズの各々で変化する。マルチタスク実時間システムでは、優先度の高いアプリケーションタスクの到来によりアプリケーションタスクが切換わる。割込みによるアプリケーションタスクの切換えも一般的である。これらのタスクの切換えは、現在実行されているタスクの互いに異なる実行フェーズで生じるおそれがある。現在のキャッシュパーティショニング技術は、キャッシュに対するこの変化する要求に対処していない。
【０００７】
従って、マルチプロセッサにおける各タスクに対し割当てられたキャッシュパーティションを実行フェーズに応じて動的にリサイズする必要性が満足されておらず、いかなる所定の瞬時においても最小量のキャッシュスペースしか割当てられていない。この問題に対する解決策は、到来するタスク（切換えられる割込みタスク又は優先度の高いタスク）に対し、充分な（又は、より最適な）キャッシュスペースが確実に得られるようにすることである。
【特許文献１】米国公開特許第２００２／０００２６５７号明細書
【非特許文献１】Discovering and exploiting program phases （Timothy Sherwoor氏等著）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、マルチプロセッサにおける各アプリケーションタスクに対する動的なキャッシュパーティショニングを行う方法及びシステムを提供する。すなわち、アプリケーションタスクの実行フェーズに基づいてキャッシュパーティショニングを動的にリサイズする手段を提供する。キャッシュパーティションを現在のタスクの実行フェーズに応じて動的にリサイズし、キャッシュ全体の不必要な予約を回避し、従って、キャッシュの有効な利用を達成するようにする。
【０００９】
シナリオを共有キャッシュ／メモリでマルチタスク処理するマルチプロセッサにおいては、パーティショニングはしばしば、メモリサブシステムの予測可能な性能を実現する手段として考えられている。ウェイパーティショニング（コラムキャッシング）、セットパーティショニング等のような幾つかのパーティショニング機構が文献に記載されている。ストリーミングアプリケーションは、識別可能な期間の識別可能なフェーズを有する実行パターンを採用している。本発明の目的は、マルチメディアアプリーケーションタスクの識別可能な実行フェーズに関する情報を引き出すこと、従って、実行フェーズ中の条件に基づいてパーティションのサイズを適合させることにある。アプリケーションタスク（プログラム）の実行フェーズは種々の方法で識別しうる。その一例は、ワーキングセットの変化をモニタリングする方法であり、他の方法もある（前記の非特許文献を参照）。アプリケーションタスクの実行フェーズは、アプリケーションタスクの実行中で同様な動作を有する期間の組として規定され、アプリケーションタスクのワーキングセットは、特定の実行フェーズにおけるアプリケーションタスクのキャッシュパーティショニング条件として既定される。
【００１０】
本発明の１つの態様によれば、アプリケーションタスクの実行フェーズに基づいてキャッシュパーティションを動的にリサイズする方法を提供する。アプリケーションタスクの実行フェーズは、表形式で識別され且つ更新される。キャッシュパーティションは、タスクの実行の特定の瞬時にリサイズされ、いかなる所定の瞬時にも、必要で充分な量のキャッシュスペースがタスクに割当てられる。キャッシュパーティションのサイズは、動的に又は静的にモニタリングされているタスクのワーキングセット条件に応じてその実行中に決定される。
【００１１】
本発明の他の態様によれば、マルチプロセッサにおけるアプリケーションタスクに対しキャッシュパーティションを動的にリサイズするコンピュータシステムを提供する。このシステムは、ワーキングセットの変化をモニタリングするタスクフェーズモニタを有する。このワーキングセットの変化は動的にモニタリングしうるようにするか、又はフェーズ情報を静的に収集してこのタスクフェーズモニタに記憶するようにすることができる。タスクのフェーズ情報は、タスクフェーズテーブルに記憶させる。タスクフェーズテーブルはフェーズと、タスクの切換え時に割当てられたキャッシュパーティション（対応するフェーズにおけるアプリケーションタスクのワーキングセット）とを含んでいる。
【００１２】
本発明のシステムは、新たなアプリケーションタスクが現在実行されているタスクに割込む際に、最大のキャッシュサイズを割当てるようにするキャッシュ割当てコントローラをも有する。新たなアプリケーションタスクが現在実行されているタスクに割込む際、キャッシュ割当てコントローラは新たなアプリケーションタスクのワーキングセット条件を検査し、可能な最大キャッシュサイズを新たなタスクに割当てることによりキャッシュをパーティショニングする。キャッシュ記憶装置の割当ては、新たなアプリケーションタスクのフェーズに応じて行なわれる。
【００１３】
本発明の１つの目的は、コンピュータシステムで実行される複数のプロセス間でのキャッシュパーティショニングを動的に管理する方法及び手段を提供することにある。
【００１４】
本発明の他の目的は、実行するアプリケーションタスクに対するキャッシュパーティションを全実行期間に亘って不必要に予約するのを回避することにより、キャッシュの利用効率を改善することにある。
【００１５】
本発明の更に他の目的は、キャッシュ上にマッピングすべき割込みタスクのワーキングセットの部分を大きくしうる確率を高めることにある。従って、優先度の高いタスク、すなわち割込みが生じると、割込みタスクに対してキャッシュをより多く割当てうるようになる。
【００１６】
本発明の上述した概要は、本発明の上述した各例を表すためのものではない。以下の図面に関する詳細な説明は、本発明の追加の態様を提供するものである。
【発明を実施するための最良の形態】
【００１７】
本発明の前述した及びその他の特徴、態様及び利点を添付図面と関連させて以下に詳細に説明する。図面には６図存在する。
【００１８】
図１は、アプリケーションタスクに対するマルチプロセッサ内のキャッシュパーティションを動的にリサイズする方法の一実施例を示す。アプリケーションタスクのワーキングセット又はベーシックブロックベクタ（ＢＢＶ）メトリックスを用いることにより、各アプリケーションタスクの実行フェーズを識別する（ブロック１０１）。アプリケーションタスクのフェーズ情報及びワーキングセットを表形式で記憶させる（ブロック１０２）。次に、このフェーズ情報を、アプリケーションタスクの実行フェーズに応じてキャッシュパーティションを動的に設定するために利用する（ブロック１０３）。
【００１９】
本発明によれば、キャッシュパーティションを、アプリケーションタスクの特定の実行瞬時にリサイズし、必要で充分なキャッシュスペースが如何なる時にもアプリケーションタスクに割当てられるようにする。キャッシュパーティションのサイズは、タスクのワーキングセット条件に応じてその実行中に決定する。タスクのワーキングセット条件は動的に又は静的にモニタリングしうる。アプリケーションタスクの全実行期間に亘るこれらアプリケーションタスクに対するキャッシュパーティションの余分な予約を回避することにより、キャッシュの全利用効率が改善される。
【００２０】
図２は、アプリケーションタスク２０１に対するワーキングセット変化を示すグラフである。この図２には、タスクの実行期間Ｔ中のアプリケーションタスクに対するワーキングセットＷ（ｔ）の変化が示されている。アプリケーションタスクのワーキングセットはその実行期間Ｔ中に変化する。従って、ワーキングセットＷ１、Ｗ２及びＷ３に対応する識別可能なフェーズＰ１、Ｐ２及びＰ３がある。スケジュール量、割込み、入力／出力バッファのデータ／スペースの利用可能性等のようなシステム状態に応じて、アプリケーションタスクを、そのいかなる実行フェーズにおいても切換えることができる。アプリケーションタスクに割当てられるキャッシュパーティションがその実行期間Ｔ中に（従来技術のように）一定である場合には、このことによりキャッシュパーティションを無駄に遮断してしまう。
【００２１】
例えば、アプリケーションタスクに割当てられたキャッシュパーティションがＷ１（バイト）のキャッシュパーティションに等しく、アプリケーションタスクが（Ｗ３に対応する）Ｐ３に切換わる場合には、キャッシュスペースＷ１−Ｗ３がこのアプリケーションタスクに対して不必要に遮断される。
【００２２】
図３は、アプリケーションタスクに対するキャッシュパーティションを動的にリサイズするシステムの一実施例のアーキテクチュアを示すブロック線図である。アプリケーションタスクのワーキングセットの変化は、タスクフェーズモニタ３０１によりモニタリングされている。ワーキングセットの変化は動的にモニタリングしうるか、又はフェーズ情報を静的に収集しうる。このフェーズ情報は、タスクフェーズテーブル３０２に記憶される。このタスクフェーズテーブル３０２は、アプリケーションタスクの切換え時に割当てられているフェーズ及びキャッシュパーティション（対応するフェーズにおけるタスクのワーキングセット）を有する。
【００２３】
新たなアプリケーションタスクが現在実行しているアプリケーションタスクに割込む場合、キャッシュ割当てコントローラ３０３がこの新たなアプリケーションタスクのワーキングセット条件を検査し、この新たなアプリケーションタスクのフェーズを順守してこの新たなアプリケーションタスクに可能な最大のキャッシュサイズを割当てることにより、キャッシュをパーティショニングする。
【００２４】
図４は、アプリケーションタスク４０１のフェーズ情報を記憶するタスクフェーズテーブル３０２を示す。このタスクフェーズテーブル３０２は、アプリケーションタスクの各々に対する別々のタスクＩＤと、アプリケーションタスクのフェーズ情報と、タスクの切換え時において各アプリケーションタスクに対し割当てられるキャッシュパーティションのサイズとを有する。アプリケーションタスクのフェーズ情報は、３つの順次のアプリケーションタスクＴ１、Ｔ２及びＴ３のそれぞれに対するＰ1 （Ｔ１）、Ｐ2 （Ｔ２）及びＰ3 （Ｔ３）として示してあり、Ｐ1 、Ｐ2 及びＰ3 は３つのタスクの３つの識別可能なフェーズである。タスクの切換え時に各アプリケーションタスクに対し割当てられるキャッシュパーティションのサイズもＷ１、Ｗ２及びＷ３として示してある。
【００２５】
図５は、２つのアプリケーションタスク５０１に対するキャッシュ条件の一例を示す。図５に示す２つのアプリケーションタスクＴ１及びＴ２のキャッシュ条件を考慮する。キャッシュの全サイズが２０ラインであるものとする。アプリケーションタスクはあるタスクから他のタスクに切換わるマルチタスクモードで実行されている。実行により、ある時間後に、キャッシュがフェーズＰ2 （Ｔ１）でタスクＴ１と、フェーズＰ3 （Ｔ２）でタスクＴ２を有しているものとする。この場合、使用されている全キャッシュは、７＋４＝１１ラインであり、９ラインが使用されずに残っている（９フリーライン）。
【００２６】
図６は、新たなアプリケーションタスクが現在実行しているアプリケーションタスクに割込む場合の、２例６０１のキャッシュパーティショニングを示す。図５では、新たなアプリケーションタスクＴ３（割込みタスク）が８ラインのワーキングセット条件を有するフェーズＰ1 （Ｔ３）に到達する場合の状態を考慮する。例１（６０２）に示す通常のモードのキャッシュパーティショニングでは、キャッシュサイズは、全実行期間に亘り、最大のキャッシュ条件、すなわち、タスクＴ１の場合７ライン及びタスクＴ２の場合８ラインに基づいて割当てられている。この場合、タスクＴ１及びＴ２がこれらの実行を終了するまでに１５ラインが使用される。
【００２７】
例２（６０３）では、タスクＴ３は、１ラインを不使用状態にするように割当てられている。タスクＴ１及びＴ２が他のある実行フェーズにあるものとすると、例１（６０２）及び例２（６０３）における割当ては、より劇的なものとなる。例えば、タスクＴ１及びＴ２がそれぞれ、フェーズＰ1 （Ｔ１）及びＰ1 （Ｔ２）にあった場合で、タスクＴ３に到達する場合、このタスクＴ３に対し２０−（２＋４）＝１４ラインが得られるようになる。従って、例２の場合で、たとえタスクＴ３に対するワーキングセットがより多く（最大で１４）になったとしても、割込みアプリケーションタスクに対しフリーラインが得られる。
【００２８】
本発明は、オーディオ、ビデオ及びモバイル分野に対するシステムオンチップにその産業上の利用性を見いだすものである。本発明は、実行するアプリケーションタスクの全実行期間に亘るこれらアプリケーションタスクに対するキャッシュパーティションの不必要な予約を回避することにより、キャッシュの利用効率を改善するものである。従って、キャッシュ記憶装置を有効に利用しうるようになる。
【図面の簡単な説明】
【００２９】
【図１】図１は、マルチプロセッサにおけるキャッシュパーティションをアプリケーションタスクに対し動的にリサイズする方法の一実施例を示す。
【図２】図２は、アプリケーションタスクに対するワーキングセットの変化を示すグラフ線図である。
【図３】図３は、キャッシュパーティションをアプリケーションタスクに対し動的にリサイズするシステムのアーキテクチュアを示すブロック線図である。
【図４】図４は、アプリケーションタスクの情報を記憶するタスクフェーズテーブルを示す。
【図５】図５は、２つのアプリケーションタスク（Ｔ１及びＴ２）に対するキャッシュ条件の一例を示す説明図である。
【図６】図６は、新たなアプリケーションタスク（Ｔ３）が現在実行しているアプリケーションタスク（Ｔ１及びＴ２）に割込む場合の、図５に示す例に対するキャッシュパーティショニングを示す説明図である。
【図１】
2009528610.tif 000003
【図２】
2009528610.tif 000004
【図３】
2009528610.tif 000005
【図４】
2009528610.tif 000006
【図５】
2009528610.tif 000007
【図６】
2009528610.tif 000008
【手続補正書】
【提出日】平成20年10月16日(2008.10.16)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
Andrew Craig Sturges氏等による米国公開特許第２００２／０００２６５７号明細書には、プロセッサが複数のプロセスを実行しうるようにしたシステムにおけるキャッシュメモリの動作方法が開示されている。このような技術によれば、異なるデータオブジェクトへのアクセスが妨害を生じるおそれのある１つのモノリシックデータキャッシュを用いる代わりに、キャッシュメモリを多くの小さいパーティションにパーティショニングする。このような場合、代表的に、コンパイラがキャッシュアーキテクチャを知っており、キャッシュメモリのパーティションをタスクに割当てる。このような技術は、キャッシュメモリのパーティショニングされた区分をその全実行期間中タスクに予約する。従って、静的なパーティショニング技術はしばしば、キャッシュメモリの利用を次善的なものとするか、キャッシュメモリのパーティションの予約を不充分なものとする。
【国際調査報告】
2009528610.tif 000009
2009528610.tif 000010
2009528610.tif 000011
2009528610.tif 000012