(57)【要約】  複数のタスク（Ｔ１−Ｔ３）のインタリーブ処理用の少なくとも１つの処理装置（１）と、前記少なくとも１つの処理装置（１）に関連し、前記少なくとも１つの処理装置によって処理される前記複数のタスク（Ｔ１−Ｔ３）用のデータをキャッシュ記憶するためのキャッシュ（５）とを具えたデータ処理システムを提供する。前記キャッシュ（５）は複数のキャッシュライン（６）に分割される。前記キャッシュライン（６）の各々は、前記の複数タスク（Ｔ１−Ｔ３）の１つに関連する。さらに、前記少なくとも１つの処理装置（１）によってインタリーブ方式で処理する前記複数のタスク（Ｔ１−Ｔ３）をスケジュールするためのタスクスケジューラ（１０）を設ける。前記キャッシュ（５）内のキャッシュライン（６）のうち、前記キャッシュ（５）から退去させるものを選択するためのキャッシュコントローラ（２０）を設ける。この選択は前記タスクスケジューラ（１０）のタスクスケジューリングに基づいて実行する。
2008523490.tif 000002
【特許請求の範囲】
【請求項１】
複数のタスク（Ｔ１−Ｔ３）のインタリーブ処理用の少なくとも１つの処理装置（１）と；
前記少なくとも１つの処理装置（１）に関連し、前記少なくとも１つの処理装置（１）によって処理される前記複数のタスク（Ｔ１−Ｔ３）用のデータをキャッシュ記憶するための、複数のキャッシュライン（６）を具えたキャッシュ（５）と；
前記少なくとも１つの処理装置（１）によってインタリーブ方式で処理される複数タスク（Ｔ１−Ｔ３）をスケジュールするためのタスクスケジューラ（１０）であって、前記キャッシュライン（６）の各々が前記複数のタスク（Ｔ１−Ｔ３）の１つに関連するタスクスケジューラ（１０）と；
前記キャッシュ（５）内の前記キャッシュライン（６）のうち退去させるべきキャッシュライン（６）を、前記タスクスケジューラ（１０）のタスクスケジューリングに基づいて選択するキャッシュコントローラ（２０）と
を具えていることを特徴とするデータ処理システム。
【請求項２】
請求項１に記載のデータ処理システムにおいて、
前記タスクスケジューラ（１０）は、当該タスクスケジューラのスケジューリングパターンを格納するためのスケジューリングテーブル（３０）を具え、
前記キャッシュコントローラ（２０）は、前記スケジューリングテーブル（３０）に格納された前記スケジューリングパターンに従って退去させるべきキャッシュライン（６）に対するタスク識別子を格納するためのビクティム制御手段（５０）を具えている
ことを特徴とするデータ処理システム。
【請求項３】
請求項１に記載のデータ処理システムにおいて、
前記タスクスケジューラ（１０）は、当該タスクスケジューラのスケジューリングパターンを格納するためのスケジューリングテーブル（３０）を具え、
前記キャッシュコントローラ（２０）は、前記スケジューリングテーブル（３０）に格納された前記スケジューリングパターンに従って退去させないべきキャッシュライン（６）に対するタスク識別子を格納するためのビクティム制御手段（５０）を具えている
ことを特徴とするデータ処理システム。
【請求項４】
請求項２または３のいずれか１項に記載のデータ処理システムにおいて、
前記ビクティム制御手段（５０）は、前記タスクスケジューラ（１０）によって、前記スケジューリングテーブル（３０）に格納された前記スケジューリングパターンに従って更新されることを特徴とするデータ処理システム。
【請求項５】
複数のタスクをインタリーブ処理するための処理装置に関連するキャッシュにおけるキャッシュ置換の方法であって、前記キャッシュが、各々が前記複数のタスクの１つに関連する複数のキャッシュラインを具えているキャッシュ置換方法において、
前記処理装置（１）によってインタリーブ方式で処理すべき前記複数のタスクの１つをスケジュールするステップと；
前記キャッシュ内の前記キャッシュラインのうち退去させるべきキャッシュラインを、前記タスクスケジューリングに基づいて選択するステップと
を具えていることを特徴とするキャッシュ置換方法。
【発明の詳細な説明】
【背景技術】
【０００１】
今日のデータ処理システムやプロセッサは、異なる速度およびサイズで構成される特定のメモリー階層構造に基づく。しかし、高速メモリーは高価なので、メモリー階層構造はいくつかのレベルに組織され、各レベルは次のより下位のレベルよりも小さく、高速でバイト当たりの単価がより高価である。通常、あるレベルにあるすべてのデータはその下位のレベルにも見出すことができ、より下位のレベルにあるすべてのデータはその下位のレベルにも見出すことができ、このことは階層構造の最下位に達するまで続く。マルチプロセッサ環境を用いたマルチタスク・データ処理システムは一般に、それぞれのプロセッサ上で同時に実行される複数のアプリケーションを含む。
【０００２】
キャッシュメモリーはメモリー階層構造の第１レベルであり、すなわちＣＰＵあるいは処理装置に最も近いメモリーである。ＣＰＵがデータ項目を要求し、このデータ項目がキャッシュ内に見つかれば、いわゆるキャッシュヒットが生じたことになる。しかし、ＣＰＵが要求したデータ項目がキャッシュ内に見つからなければ、いわゆるキャッシュミスが生じたことになる。キャッシュミスの訂正および要求されたデータ項目のフェッチ（取り寄せ）に要する時間は、そのメモリーのレイテンシ（待ち時間）およびバンド幅に依存する。レイテンシはブロックの最初のワードを取り出すための時間に相当し、バンド幅はブロックの残りを取り出す時間に関係する。キャッシュの基本的な考え方は、次に来る処理サイクル中に必要となるデータ項目を、その実際の処理の前にフェッチするというものである。これはプリフェッチング（事前取り寄せ）とも呼ばれる。
【０００３】
キャッシュミスが起こると、キャッシュコントローラは、現在キャッシュに格納されているデータ項目やブロックの中から、フェッチすべき所望のデータ項目やデータブロックと置換すべきものを選択しなければならない。実際のキャッシュ置換はランダム、最長時間未使用（ＬＲＵ）、または先入れ先出し（ＦＩＦＯ）の基準で実行される。ランダム選択は、アロケーション（割付）を均等に拡張してブロックがランダムに選択されるように実行する。次に来るサイクルで必要となる情報を捨ててしまう機会を減らすためには、ブロックへのアクセスを最長時間未使用キャッシュ置換スキーム（方式）で記録する。従って、過去のアクセスに基づいて、最も長い時間にわたって使用されていないブロックが置換されるように予測を算出する。しかし、ＬＲＵキャッシュ置換方式は計算密度が高いので、先入れ先出し置換方式により、ＬＲＵではなく最も古いブロックを置換用に定める。
【０００４】
先入れ先出しＦＩＦＯ置換方式はラウンドロビン戦略とも呼ぶことができる。ここで、キャッシュはヒット毎ではなくミスの際のみに更新される。ブロックの置換はデータ、アドレスタグその他を更新することにより行う。キャッシュ内のデータブロックのうち、キャッシュ置換方式により選択されたものとして置換されるべきものをビクティム（犠牲者）と呼ぶ。このようなビクティムブロックはビクティムバッファに移動することができる。ビクティムブロックはメモリー階層構造内の次位のレベルに書き込まれる。
【０００５】
一般に、平均メモリーアクセス時間はヒット時間にミス率とミスペナルティーの積を足したものに相当する。ミスペナルティーを減らす１つの技法は、マルチレベルキャッシュを採用することである。ここで、実際のＣＰＵは無視して、キャッシュとメインメモリー（主記憶装置）との間のインターフェースに集中する。元のキャッシュとメインメモリーとの間に新たなキャッシュレベルを加えることによって、第１レベルキャッシュは高速なＣＰＵのクロックサイクルと一致するよう十分小さく設計することができ、他方、第２レベルキャッシュは次のクロックサイクルでＣＰＵが使用するための十分な量のデータを捕捉するよう十分大きくすることができる。
【０００６】
ミスペナルティーを減らす別の技法は、ビクティムキャッシュを採用することである。ここで、Ｌ１キャッシュのようなキャッシュから捨てられたデータ項目（ビクティムブロック）はビクティムキャッシュに格納することができる。キャッシュから捨てられたこのデータ（ビクティムブロック）は、すでにメインメモリーまたは他のキャッシュレベルからフェッチされているので、このデータ項目またはデータブロックは少ないレイテンシで再度使用することができる。従って、これらの捨てられたデータ項目またはデータブロックをビクティムキャッシュに格納する。言い換えると、キャッシュミスとそれに続くキャッシュ置換によって捨てられたデータ項目だけが、ビクティムキャッシュに格納されることになる。
【０００７】
このようなビクティムキャッシュは一般に、小型の十分関連性のある（ｆｕｌｌｙ-ａｓｓｏｃｉａｔｅｄ）キャッシュである。これは、コンフリクト（衝突）ミスまたは容量ミスによりＣＰＵキャッシュまたはＬ１キャッシュから退去させられたブロックを格納するように設計される。一般にメインキャッシュとそのリフィルパス（書替え経路）との間に配置される。キャッシュミスによりＬ１キャッシュから退去させられたブロックのみがその中に格納される。これは、キャッシュミスペナルティーを減少させるために用いる。
【０００８】
さらなるキャッシュ置換の技法は、最小使用頻度の技法である。これは、使用頻度が最小のブロックをキャッシュから退去させることによって、新しくプリフェッチするデータ用の空間を作るものである。
【０００９】
キャッシュ置換技法に関して２つの点が重要と思われる。すなわち、どのデータブロックをキャッシュ内にフェッチすべきかという点、および、どのデータブロックをキャッシュから退去させ、その退去させるデータブロックに替えて新しくフェッチするデータブロックをキャッシュ内に格納できるようにすべきかである。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、改善されたキャッシュ置換能力を有する、複数の処理装置及びキャッシュを有するデータ処理システム、並びにキャッシュ置換方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
この目的は、請求項１に記載のデータ処理システムおよび請求項５に記載のキャッシュ置換のための方法によって解決される。
【００１２】
従って、データ処理装置に、複数タスクのインタリーブ処理のための少なくとも１つの処理装置、および前記少なくとも１つの処理装置によって処理すべき前記複数タスクのためのデータのキャッシュ記憶を行うための、前記少なくとも１つの処理装置に関連するキャッシュを設ける。前記キャッシュは複数のキャッシュラインに分割される。各キャッシュラインはそれぞれ前記複数タスクの１つに関連する。さらに、前記少なくとも１つの処理装置によりインタリーブ方式で処理される前記複数タスクのスケジューリングを行うためのタスクスケジューラを設ける。キャッシュ内のキャッシュラインのうちキャッシュから退去させるものを選択するためのキャッシュコントローラを設ける。この選択は、タスクスケジューラのタスクスケジューリングに基づいて行われる。
【００１３】
したがって、キャッシュ置換は実際のタスクスケジューリング情報に基づく。タスクスケジューラはどのタスクが次に来るクロックサイクルにおいて前記処理装置により処理されるかを知っているので、この情報は、新たにプリフェッチするデータ用の十分な空間を提供するためにキャッシュ内のどのキャッシュラインを退去させるべきかをキャッシュコントローラが決定する際に使用される。言い換えれば、タスクスケジューリング情報を参照することによって、次に実行可能なタスクに対応するキャッシュラインを退去させず、これによりキャッシュミスが減少されることを保証することができる。
【００１４】
本発明の１つの態様によれば、前記タスクスケジューラは、そのスケジューリングパターンを格納するためのスケジューリングテーブルを具える。前記キャッシュコントローラは、退去させるべきキャッシュラインについての情報を格納するためのビクティム制御手段を具える。この情報は、前記スケジューリングテーブルに格納されている前記スケジューリングパターンに基づく。したがって、キャッシュコントローラはどのキャッシュラインが複数タスクのどのタスクに関連するかを知り、タスクスケジューラからのタスクスケジューリング情報により、キャッシュコントローラは退去させるべきキャッシュラインを、前もってタスクスケジューラと通信することなしに直接選択することができる。
【００１５】
本発明のさらなる態様によれば、前記タスクスケジューラは、そのスケジューリングパターンを格納するためのスケジューリングテーブルを具える。前記キャッシュコントローラは、退去させるべきでないキャッシュラインについての情報を格納するためのビクティム制御手段を具える。この選択はここでもスケジューリングテーブルに格納されたスケジューリングパターンに基づく。ここでは、代替の実施形態として、退去させるべきでないキャッシュラインが決定される。
【００１６】
本発明のさらなる態様によれば、前記ビクティム制御手段を前記タスクスケジューラによって、前記スケジューリングテーブルに格納されたスケジューリングパターンに従って更新し、前記ビクティム制御手段がキャッシュラインを退去させる前に前記タスクスケジューラを参照しなければならないことがないようにする。
【００１７】
本発明は、また、複数タスクのインタリーブ処理用の処理装置に関連するキャッシュのためのキャッシュ置換方法にも関する。前記キャッシュは複数のキャッシュラインを具え、各キャッシュラインは前記複数タスクの１つに関連し、前記複数タスクのうち前記処理装置によってインタリーブ方式で処理されるものがスケジューリングされている。キャッシュ内の退去させるべきキャッシュラインは、タスクスケジューリングに基づいて選択する。
【００１８】
本発明は、タスクスケジューラが知っている情報を利用して、キャッシュ内のどのキャッシュラインを退去させるかを決定する、という考え方に基づいている。タスクスケジューラには、マルチタスク環境におけるどのタスクが次に処理装置上で実行可能なタスクとなるかを知っているので、どのキャッシュラインが次に実行可能なタスクに対応するかを予測することができ、これにより、このタスクに対応するキャッシュラインを退去させないで、次のクロックサイクルにおけるキャッシュミスを防止することができる。
【００１９】
本発明のこれらおよびその他の態様は、以下で図面を参照しながら記述する実施の説明より明らかになる。
【発明を実施するための最良の形態】
【００２０】
図１に、本発明によるデータ処理システムのアーキテクチャの基本ブロック図を示す。このデータ処理システムは、処理装置１、キャッシュ５、キャッシュコントローラ２０、バス８、メインメモリー７およびタスクスケジューラ１０を具える。メインメモリー７はバス８に結合されている。キャッシュ５およびキャッシュコントローラ２０も同様にバス８に結合されている。処理装置１はキャッシュ５に結合されている。タスクスケジューラ１０は、バス８並びに処理装置１、およびキャッシュコントローラ２０に結合されている。
【００２１】
このようなデータ処理システムは、オンチップシステムとして実現することができる。第１の実施例によるデータ処理システムは特に、例えばオーディオ、ビデオといったマルチタスク・ストリーミングアプリケーションに適用可能である。しかし、その他のアプリケーションも第１実施例によるデータ処理システムによって実行することができる。
【００２２】
図２に、図１に示すシステムアーキテクチャの一部を示す。ここでは、タスクスケジューラ１０およびキャッシュコントローラ２０のみを示す。図１の他のすべての要素は、図面を簡略化するために省略した。図２は、本発明によるキャッシュ置換を行うためのタスクスケジューラ１０とキャッシュコントローラ２０との関係を説明する役割をする。タスクスケジューラ１０は、ルックアップテーブル（早見表）／スケジューリングテーブル３０を具える。キャッシュコントローラ２０は、ビクティム制御レジスタ５０およびビクティムエンジン・ユニット４０を具える。タスクスケジューラのタスクスケジューリングパターンは参照テーブル３０に格納される。したがって、このテーブルは、どのタスクが次のクロックサイクルにおいて処理装置により実行されるか、すなわち、どのタスクが次に実行されるタスクであるかについての情報を含む。
【００２３】
ビクティム制御レジスタ５０は、タスクスケジューラ１０によって、ルックアップテーブル３０に格納された情報に従って更新される。ビクティム制御レジスタ５０はＭＭＩＯレジスタとして実現することができる。上述の更新は、一定間隔および／または参照テーブル３０に変更が生じた際に実行することができる。
【００２４】
ビクティム制御レジスタ５０は、次のクロックサイクル中にどのタスクを実行すべきかに関する情報を有する。この情報は、タスクＩＤとすることができる。ビクティム制御レジスタ５０内の情報は、タスクスケジューラによって、テーブル３０に格納されたタスクパターンに基づいて更新される。ビクティムエンジン・ユニット４０は、ビクティム制御レジスタ５０すなわちビクティム制御ユニットに格納されタスクスケジューラによって更新されるタスクＩＤを読み出し、このタスクＩＤをキャッシュブロックまたはキャッシュラインのタグと比較して、キャッシュブロックまたはキャッシュラインのうち退去させるものを１つ選択する。
【００２５】
上述したキャッシュ置換方策は、上に述べた従来技術によるキャッシュ置換方策と組み合わせて使うこともできる。例えば、次に実行するタスクに対応するキャッシュラインがない場合、ビクティム選択は在来のキャッシュ置換方針に従って行うことができる。
【００２６】
図３に、図１に示すキャッシュ５のキャッシュ構成を示す。図１により説明したマルチタスク環境では、マルチタスクまたはマルチスレッドを、単一のプロセッサまたは処理装置１用にスケジューリングする必要がある。この処理装置は、異なるタスクに関する複数のコンテクストを格納することができ、あるタスクがブロックされた場合に、このタスクを他のタスクに切り替えることができる。したがって、図１により説明したキャッシュ５は、処理装置上で実行中のアプリケーション用に処理する必要のある異なるタスクからのデータを有する異なるキャッシュライン６を含む。実際のキャッシュ置換は、処理装置上で現在実行中のタスクにとって必要となり得る新しいキャッシュラインを持ってくるかフェッチする過程中に実行される。
【００２７】
３つのタスクＴ１〜Ｔ３が処理装置１にマッピングされている場合、各タスクＴ１〜Ｔ３は、キャッシュ上の異なるキャッシュライン６またはブロックを必要とし得る。図３では、第１および第２のキャッシュラインは第１タスクＴ１に対応するデータで満たされている。第３のキャッシュラインは第２タスクＴ２に対応するデータを含み、第４及び第５のキャッシュラインは第３タスクＴ３に対応するデータを含む。
【００２８】
処理装置による次の処理中に必要となる新しいデータをキャッシュ内にプリフェッチするために、キャッシュ５内に現在キャッシュ記憶されているデータの一部を退去させて、新しく（プリ）フェッチされるデータ用の十分な空間をキャッシュ内に用意する必要がある。どのキャッシュラインを退去させるかについての決定は、タスクスケジューラにおける次に処理されるタスクに関する情報に基づく。
【００２９】
図４に、スケジューリング・インスタンスに関するタスクスケジューリングパターンの例のテープル（表）を示す。上段はタスクのＩＤを示し、下段はスケジューリング・インスタンス１〜１２を示す。従って、図４より、タスクスケジュールが繰り返しパターン、すなわちＴ１，Ｔ２，Ｔ３，Ｔ１，Ｔ３，Ｔ２等に従うことがわかる。タスクスケジューリング情報は、図２に示すタスクスケジューラ１０の参照テーブル３０に格納される。したがって、このテーブルは次に実行可能なタスクについての情報を含む。キャッシュミスを避けるために、図３に示すキャッシュ５内のキャッシュライン６のうち、次に実行可能なタスクに関連するものはキャッシュから退去させるべきでない。
【００３０】
上述した実施例によるキャッシュ置換技術の利点を説明するため、以下、ＬＲＵ（最長時間未使用）技術によるキャッシュ置換を図４を参照しながら説明する。ＬＲＵは、第１タスクＴ１に関連し、処理装置１が第３タスクＴ３（スケジューリング・インスタンス３）を実行する際に置換されるキャッシュラインを選択する、というのは、第１タスクＴ１に対応するキャッシュラインは最長時間未使用であるからである。しかし、スケジュール・インスタンス４では、第１タスクＴ１は次に実行可能なタスクであるので、ＬＲＵに基づくキャッシュ置換は好ましくない。従って、ＬＲＵを用いるならば、処理装置１は、第３タスクＴ３の後に第１タスクＴ１がスケジュールされている場合には、キャッシュミスを生じる。したがって、本発明によるキャッシュ置換、すなわちタスクスケジューリング情報に基づくキャッシュ置換は、タスクスケジューラの情報に基づいて次に実行可能なタスクかを予測することができるので、より好ましい。図４の例では、本発明に基づくキャッシュ置換技術は、第１タスクＴ１に対応するキャッシュラインの代わりに、第２タスクＴ２に関連するキャッシュラインを退去させるべきものとして選択する。
【００３１】
上述したキャッシュ置換技術は、参照テーブル３０に格納された次に実行されるタスクの情報に基づき、繰り返し実行することができる。
【００３２】
言い換えれば、スケジューリング情報を置換技術用の入力として用いて、マルチタスク環境におけるキャッシュミスを最小化する。
【００３３】
なお、上述した実施例は本発明を例示するのもであって限定するものではなく、当業者は、請求項の範囲から逸脱することなしに多くの代案実施例を設計することができる。請求項中では、括弧内の参照記号はいずれも請求項を限定するものではない。「具える」とは、請求項に記載した以外の要素またはステップの存在を排除するものではない。いくつかの手段を列挙した装置請求項では、これら手段のいくつかはハードウエアの同一アイテムによって具体化することができる。互いに異なる従属請求項中に特定の方策が存在するということだけでは、これらの方策の組み合わせを有利に用いることができないということを示すものではない。
【００３４】
さらに、請求項中の参照符号は、いずれも請求項の範囲を限定するものではない。
【図面の簡単な説明】
【００３５】
【図１】本発明に係るデータ処理システムの基本アーキテクチャを示す。
【図２】図１のアーキテクチャの一部を示す。
【図３】図１に係るキャッシュ５のキャッシュ機構を示す。
【図４】図１に係るデータ処理システムのスケジュール例の説明を示す。
【図１】
2008523490.tif 000003
【図２】
2008523490.tif 000004
【図３】
2008523490.tif 000005
【図４】
2008523490.tif 000006
【国際調査報告】
2008523490.tif 000007
2008523490.tif 000008
2008523490.tif 000009