JP6042170B2 - キャッシュ制御装置及びキャッシュ制御方法 - Google Patents

Description

本発明は、キャッシュ制御装置及びキャッシュ制御方法に関し、例えば、キャッシュメモリの領域を分割するキャッシュ制御装置及びキャッシュ制御方法に関する。

マルチプロセッサ又はマルチスレッドなどの並行処理や、命令又はデータのキャッシュは、プロセッサとメモリの速度差による性能低下の解決に適している。また、リアルタイム制御における並行処理では、タスク間干渉による処理時間の揺らぎを低減し、定められた実時間内に特定の処理を完了できる性質が要求される。

特許文献１には、ハードウェアスレッドの最低限の実行時間を保証しながら、柔軟なハードウェアスレッドの選択を可能とするためのマルチスレッドプロセッサに関する技術が開示されている。特許文献１にかかるマルチスレッドプロセッサが有するスレッドスケジューラは、予め定められた第１の実行時間において固定的に選択された少なくとも１つのハードウェアスレッドの実行を指定し、第２の実行時間において任意のハードウェアスレッドの実行を指定するものである。

ここで、キャッシュを有するプロセッサにおいては、あるタスクのためのキャッシュ領域が他のタスクのために上書きされるなどの干渉によるキャッシュヒット率のばらつきが発生する。そこで、特許文献２には、キャッシュメモリの領域を分割し、複数のタスクに個別に領域を割り当てる技術が開示されている。特許文献２にかかるキャッシュ制御装置は、マイクロプロセッサが並行処理する各タスクとキャッシュメモリのメモリ領域を分割した各領域とを対応付けて管理する領域管理部を含む。つまり、特許文献２では、各タスクが操作できるキャッシュメモリ領域を限定することで、タスク間の干渉を解決している。また、特許文献３〜５には、タスク（又はプロセス）の優先度に基づきキャッシュメモリの容量の割り当てを行う技術が開示されている。

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

しかしながら、特許文献２〜５では、リアルタイム制御における並行処理において、キャッシュメモリ全体の利用効率が悪くなり得るという問題がある。尚、特許文献１には、キャッシュメモリの利用効率を向上させるための技術は開示されていない。

その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。

一実施の形態によれば、キャッシュ制御装置は、プロセッサにより複数の命令流のそれぞれに割り当てられた単位時間当たりの実行時間の割当比率に基づいて、各命令流に割り当てるキャッシュメモリの領域を決定する領域決定部を備える。

また、他の実施の形態によれば、複数の命令流が分散して割り当てられた複数のプロセッサ間の処理速度の比率に基づいて、各命令流に割り当てるキャッシュメモリの領域を決定する領域決定部を備える。

さらに、他の実施の形態によれば、キャッシュ制御方法は、プロセッサにより複数の命令流のそれぞれに割り当てられた単位時間当たりの実行時間の割当比率を受け付け、前記実行時間の割当比率に基づいて、各命令流に割り当てるキャッシュメモリの領域を決定する。

前記一実施の形態によれば、リアルタイム制御における並列処理において、キャッシュメモリ全体の利用効率を向上させることができる。

本実施の形態１にかかるキャッシュ制御装置を含むコンピュータシステムの構成を示すブロック図である。 本実施の形態１にかかる領域決定部の構成を示すブロック図である。 本実施の形態１にかかるキャッシュ制御方法の処理の流れを示すフローチャートである。 課題及び効果を説明するための図である。 本実施の形態２にかかるキャッシュ制御装置を含むコンピュータシステムの構成を示すブロック図である。 本実施の形態２にかかる論理アドレスのビット構成例を示す図である。 本実施の形態２にかかる領域決定部の構成を示すブロック図である。 本実施の形態２にかかるスロット割当情報、割当スロット数情報及びIndexテーブルの例を示す図である。 本実施の形態２にかかる領域決定時のキャッシュメモリ内のデータの例を示す図である。 本実施の形態２にかかるスロット割当情報、割当スロット数情報及びIndexテーブルの他の例を示す図である。 本実施の形態２にかかる領域決定時のキャッシュメモリ内のデータの他の例を示す図である。 本実施の形態２にかかる領域分割方法の処理の流れを示すフローチャートである。 本実施の形態２にかかるアクセス処理方法の処理の流れを示すフローチャートである。 本実施の形態２にかかる割当変更処理の流れを示すフローチャートである。 本実施の形態２にかかる割当変更後のスロット割当情報、割当スロット数情報及びIndexテーブルの例を示す図である。 本実施の形態２にかかる割当変更後のキャッシュメモリ内のデータの例を示す図である。 本実施の形態３にかかる領域決定部の構成を示すブロック図である。 本実施の形態３にかかる論理アドレスのビット構成例を示す図である。 本実施の形態３にかかるバンクを用いた場合の領域決定時のキャッシュメモリ内のデータの例を示す図である。 本実施の形態３にかかるバンクを用いた場合の割当変更後のキャッシュメモリ内のデータの例を示す図である。 本実施の形態４にかかるキャッシュ制御装置を含むコンピュータシステムの構成を示すブロック図である。 本実施の形態４にかかる領域決定部の構成を示すブロック図である。 本実施の形態４にかかる論理アドレスのビット構成例を示す図である。 本実施の形態４にかかる領域決定時のデータの例を示す図である。 本実施の形態４にかかる領域更新時のデータの例を示す図である。 本実施の形態５にかかるキャッシュ制御装置を含むコンピュータシステムの構成を示すブロック図である。 関連技術にかかるキャッシュ制御装置を含むコンピュータシステムの構成を示すブロック図である。 関連技術にかかるキャッシュ制御装置の構成を示すブロック図である。

以下では、上述した課題を解決するための手段を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略する。

＜実施の形態１＞
図２７は、特許文献２にかかるキャッシュ制御装置を含むコンピュータシステムの構成を示すブロック図である。但し、図２７には、コンピュータシステムのうち、キャッシュ制御装置９１と、キャッシュメモリ９２と、マイクロプロセッサ９３と、メインメモリ９４と、ＭＭＵ（Ｍｅｍｏｒｙ Ｍａｎａｇｅｍｅｎｔ Ｕｎｉｔ）９５とが代表して記載されている。キャッシュ制御装置９１は、マイクロプロセッサ９３とキャッシュメモリ９２とメインメモリ９４とに接続されている。また、キャッシュ制御装置９１は、ＭＭＵ９５を介してもメインメモリ９４と接続されている。

マイクロプロセッサ９３は、複数のプログラムをタスクとしてマルチタスク処理を行う。マイクロプロセッサ９３は、処理するタスクが切り替わると、タスクＩＤ信号線９０１を介して現在処理されるタスクを識別するタスクＩＤをキャッシュ制御装置９１へ通知する。ここで、タスクＩＤは、タスクとして処理されるプログラムが格納されているメインメモリアドレスを示す論理アドレスが変換されたものである。例えば、タスクＩＤは、プログラムのアドレスである。

また、マイクロプロセッサ９３は、各タスクにおけるキャッシュメモリ９２へのアクセス処理において、メモリアクセス信号線９０２を介してアクセスアドレスをキャッシュ制御装置９１へ通知する。ここで、アクセスアドレスは、アクセス要求対象のデータのメインメモリ９４内のアドレスを示す論理アドレスである。そして、マイクロプロセッサ９３は、データ信号線９０３を介して、読み出し又は書込み対象のデータをキャッシュ制御装置９１との間で送受信する。

さらに、マイクロプロセッサ９３は、領域指定信号線９０６を介して領域指定情報をキャッシュ制御装置９１へ通知する。ここで、領域指定情報は、複数のタスクのそれぞれについて、各タスクに割り当てるためのキャッシュメモリサイズ等を指定する情報である。

キャッシュメモリ９２は、メインメモリ９４より高速にデータアクセスが可能な記憶媒体であり、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）である。ＭＭＵ９５は、キャッシュ制御装置９１からメモリアクセス信号線９０４を介して送られてきた論理アドレスを物理アドレスに変換する。メインメモリ９４は、キャッシュメモリ９２よりアクセス速度が低速な記憶媒体であり、例えば、ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）である。

キャッシュ制御装置９１は、キャッシュメモリ９２に対するデータアクセスを制御する装置である。キャッシュ制御装置９１は、マイクロプロセッサ９３から受け付けた領域指定情報に応じて、キャッシュメモリ９２のメモリ領域を分割し、タスクごとに対応付けて管理する。そして、キャッシュ制御装置９１は、タスクＩＤ及びアクセスアドレスに基づいてキャッシュメモリ９２へのアクセスを行う。また、キャッシュ制御装置９１は、アクセス要求のヒット又はミスの判定結果に応じて、適宜、メモリアクセス信号線９０４を介してアクセスアドレスをメインメモリ９４へ通知し、データ信号線９０５を介してメインメモリ９４との間で、データを送受信する。

図２８は、特許文献２にかかるキャッシュ制御装置の構成を示すブロック図である。キャッシュ制御装置９１は、タスクＩＤ入力レジスタ９１１と、領域管理部９１２と、アドレス分解部９１４と、キャッシュ内アドレス生成部９１５と、ｈｉｔ／ｍｉｓｓ判定部９１６と、キャッシュディレクトリ９１７と、キャッシング部９１８と、データアクセス部９１９とを備える。また、領域管理部９１２は、領域決定部９１３を含む。ここでは、本実施の形態に関係する領域管理部９１２及び領域決定部９１３を中心に説明し、その他の構成については説明を省略する。

領域管理部９１２は、マイクロプロセッサ９３から領域指定信号線９０６を介して送られた領域指定情報に基づいて、キャッシュメモリ９２のメモリ領域を分割し、各領域を識別する領域番号とタスクＩＤとを対応付けて管理する。このとき、領域決定部９１３は、領域指定情報に基づいて、領域管理テーブルを生成し、保持する。ここで、領域管理テーブルは、領域番号、ベースアドレス及びサイズを組にした表である。

このように、特許文献２にかかる技術は、領域指定情報で指定された各タスクに割り当てるためのキャッシュメモリサイズそのものを用いて、領域を割り当てているに過ぎない。また、当該領域指定情報は、予め固定して設定されたものである。つまり、特許文献２では、あるタスクについて他のタスクに比べて優先的にキャッシュメモリの領域を割り当てるために、予め領域指定情報を固定して設定しておく必要がある。

ここで、上述したように、リアルタイム制御における並行処理では、各タスクの優先度が動的に変化するため、特許文献２のような固定的なキャッシュメモリの領域設定では、設定変更に対応することは困難である。また、リアルタイム制御では、各タスクについて予め定められた実時間内に特定の処理を完了できる性質が要求される。しかしながら、特許文献３〜５等の関連技術では、優先度の低いタスクへの領域の割り当てが後回しにされてしまう。そのため、優先度が低いタスクについては、キャッシュメモリの領域の割り当てが不十分となり、定められた実時間内に特定の処理を完了できる保証がない。よって、これらの関連技術には、結果的にキャッシュメモリ全体の利用効率が悪くなり得るという問題がある。

そこで、本実施の形態１にかかるキャッシュ制御装置は、プロセッサにより複数の命令流のそれぞれに割り当てられた単位時間当たりの実行時間の割当比率に基づいて、各命令流に割り当てるキャッシュメモリの領域を決定する領域決定部を備えるものである。すなわち、リアルタイム処理において各命令流のプロセッサにおける実際の実行時間の割当比率とキャッシュメモリの使用率とを均衡する。これにより、各命令流のリソースの利用率をより正確に設定できる。

図１は、本実施の形態１にかかるキャッシュ制御装置を含むコンピュータシステムの構成を示すブロック図である。図１には、コンピュータシステムのうち、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１１０と、キャッシュ制御装置１２０と、キャッシュメモリ１３０とが代表して記載されている。キャッシュ制御装置１２０は、ＣＰＵ１１０とキャッシュメモリ１３０とメインメモリ（不図示）とに接続されている。

ＣＰＵ１１０は、複数のプログラムをタスクとしてマルチタスク処理を行う。ＣＰＵ１１０は、メモリアクセス部１１１と、実行時間割当部１１２とを備える。メモリアクセス部１１１は、各タスクにおけるキャッシュメモリへのアクセス処理において、キャッシュ制御装置１２０に対して、アクセスアドレスｄ１及び（タスクの）ＩＤｄ２を通知する。ここで、アクセスアドレスｄ１は、アクセス要求対象のメインメモリ内のアドレスを示す論理アドレスである。ＩＤｄ２は、タスクの識別情報である。

尚、メモリアクセス部１１１は、いわばロードストアユニットといえる。また、キャッシュメモリ１３０は、データキャッシュ又は命令キャッシュのいずれでも構わないものとする。

実行時間割当部１１２は、ＣＰＵ１１０において並列処理される複数のタスクのそれぞれについて、ＣＰＵ１１０内で実行させるための実行時間を割り当てるものである。つまり、実行時間割当部１１２は、各タスクにＣＰＵ１１０内のリソースを割り当てる。実行時間割当部１１２には、例えば、特許文献１のスケジューラを用いることができる。

特許文献１にかかるスケジューラは、複数のタイムスロットに対して複数のハードウェアスレッドを柔軟に割り当てるものである。ここで、タイムスロットとは、所定の時間を所定数で均等に分割した時間間隔であるものとする。また、ハードウェアスレッドとは、ＣＰＵ１１０に内蔵されるスレッドプログラムカウンタにより出力される命令フェッチアドレスに従って命令メモリから読み出される一連の命令群により構成される命令流を生成する系のことをいう。つまり、１つのハードウェアスレッドにより生成される命令流に含まれる命令は、互いに関連性の高い命令である。また、タスクも複数の関連性の高い命令により構成される命令流といえる。

ここで、各タスクは、所定の時間当たりに、割り当てられたタイムスロットの数（割当タイムスロット数）に応じた時間分の実行時間が確保される。また、各タスクは、同一のＣＰＵ１１０つまり同一のクロック周波数のうち、総タイムスロット数分の割当タイムスロット数の比率の周波数で実行されるものといえる。つまり、各タスクは、割当タイムスロット数に応じた処理速度でＣＰＵ１１０により実行されるものといえる。そのため、ここでは、各タスクに割り当てられたタイムスロットの比率が処理速度の比率ともいえる。

そして、実行時間割当部１１２は、キャッシュ制御装置１２０に対して実行時間の割当比率ｄ３を通知する。実行時間の割当比率ｄ３は、タスク間に割り当てられた実行時間の占有率を示す情報である。例えば、実行時間の割当比率ｄ３は、実行時間割当部１１２により実行時間の割り当ての都度、算出してもよい。または、実行時間割当部１１２は、各タスクに割り当てられた実行時間自体を通知し、キャッシュ制御装置１２０が各実行時間の比率から各タスクについて実行時間の割当比率ｄ３を算出するようにしてもよい。または、領域決定部１２２が実行時間割当部１１２から実行時間の割当比率ｄ３を読み出すようにしてもよい。つまり、領域決定部１２２は、少なくとも実行時間割当部１１２から実行時間の割当比率ｄ３を取得する。

キャッシュ制御装置１２０は、ＣＰＵ１１０からのアクセス要求で指定されたアクセスアドレスｄ１に対応するデータが、キャッシュメモリ１３０に格納されているか否かを判定する。そして、キャッシュメモリ１３０に格納されている場合には、キャッシュ制御装置１２０は、キャッシュメモリ１３０から読み出したデータをＣＰＵ１１０へ出力する。一方、キャッシュメモリ１３０に格納されていない場合には、キャッシュ制御装置１２０は、メインメモリに対してアクセス要求を行う。

キャッシュ制御装置１２０は、アドレス分割部１２１、領域決定部１２２及びヒットミス判定部１２３を備える。アドレス分割部１２１は、メモリアクセス部１１１から受け付けたアクセスアドレスｄ１を、少なくともタグｄ４及びラインｄ５に分割する。尚、アドレス分割部１２１は、ラインｄ５をさらに複数の領域に分割しても構わない。また、メモリアクセス部１１１がアドレス分割部１２１相当の構成を有しても構わない。その場合、キャッシュ制御装置１２０は、アドレス分割部１２１が不要となり、メモリアクセス部１１１からタグｄ４及びラインｄ５を受け付けることとなる。

領域決定部１２２は、実行時間割当部１１２から通知された実行時間の割当比率ｄ３に基づいて、タスクごとのキャッシュメモリ１３０の領域の割り当てを決定する。すなわち、実行時間の割当比率の高いタスクには、より多くの領域を割り当て、逆に実行時間の割当比率の低いタスクには、相対的に少ない領域を割り当てる。これにより、各命令流が実際にＣＰＵ１１０で処理される実行時間とキャッシュメモリ１３０における各命令流に対して割り当てられる領域のバランスを取ることができる。

また、領域決定部１２２は、ＩＤｄ２及びラインｄ５に応じて、キャッシュメモリ１３０へキャッシュアクセスｄ６を行う。そして、ヒットミス判定部１２３は、上記アクセスに対するキャッシュメモリ１３０からの応答としてタグｄ７を受け付ける。そして、ヒットミス判定部１２３は、タグｄ７と、メモリアクセス部１１１から通知されたアクセスアドレスｄ１に含まれるタグｄ４とを比較する。ヒットミス判定部１２３は、当該比較結果に応じてＨｉｔ応答又はＭｉｓｓリフィルｄ８を行う。

図２は、本実施の形態１にかかる領域決定部１２２の構成を示すブロック図である。領域決定部１２２は、加工部１２２１と、割当制御部１２２２と、領域割当情報１２２３とを備える。加工部１２２１は、実行時間の割当比率ｄ３を受け付け、実行時間の割当比率ｄ３を加工して、各タスクに割り当てる領域割当情報を生成する。例えば、加工部１２２１は、実行時間の割当比率ｄ３に基づいて、各タスクに割り当てるキャッシュメモリの領域を特定する。そして、加工部１２２１は、特定された領域とタスクとを対応付けて領域割当情報を生成する。

その後、加工部１２２１は、領域割当情報１２２３として記憶領域に格納する。領域割当情報１２２３は、領域とタスクとが対応付けられた情報である。また、割当制御部１２２２は、ＩＤｄ２に応じて領域割当情報１２２３から特定されるアクセス対象の領域と、ラインｄ５とに基づいて、キャッシュアクセスｄ６を行う。このように、本実施の形態１では、実行時間の割当比率ｄ３そのものでなく、領域割当情報という加工済みの情報により以降のキャッシュアクセス時に容易にアクセス対象の領域を特定できる。また、命令流とラインとの対応付けを効率的に行うことができる。

図３は、本実施の形態１にかかるキャッシュ制御方法の処理の流れを示すフローチャートである。まず、領域決定部１２２は、実行時間割当部１１２から実行時間の割当比率ｄ３を受け付ける（Ｓ１１）。そして、領域決定部１２２は、実行時間の割当比率ｄ３に基づいて、キャッシュメモリ１３０の領域の割り当てを決定する（Ｓ１２）。

図４は、２つのタスクを並行処理する場合における課題及び効果を説明するための図である。図４では、各タスクに割り当てられたプロセッサの実行時間及びキャッシュメモリの領域の関係を、特許文献２等の関連技術と後述する本実施の形態１との比較を模式的に示したものである。

ここで、例えば、リアルタイム制御における並列処理の場合には、上述した特許文献１のようなスケジューラによりタスクＡとタスクＢとの実行時間の割当比率が動的に変更されることがあり得る。そのため、特許文献２のように固定的にタスクにおけるキャッシュメモリの領域の割当比率を設定すると、実行時間の割当比率が変更した後に領域の割当比率とのバランスがとれなくなるおそれがある。例えば、当初の実行時間の割当比率がタスクＡよりもタスクＢの方が高く、その後にタスクＡよりもタスクＢが低くなった場合には、図４の左のグラフのような状況が起こり得る。

尚、関連技術のうち特許文献３〜５のように、単に優先度の設定に応じたキャッシュメモリ領域の割り当てるのであれば、最優先のタスクに対して全ての領域を割り当ててしまい、優先度の低いタスクには領域が割り当てられないおそれがある。しかしながら、リアルタイム制御における並列処理の場合、タスクの優先度が低いとはいえ、最低限の実行時間の確保及び実行終了時間の制約を満たす必要がある。そのため、優先度設定ではリアルタイム制御における並列処理について、タスクＡの優先度が高い場合には、タスクＢへの領域の割り当ては保証されず、不十分となる可能性がある。

一方、本実施の形態１では、図４の右のグラフのように、タスクＡとタスクＢとにおける実行時間の割当比率と領域の割当比率とを均衡させることができる。よって、プロセッサにおける実行時間の割り当てが相対的に高いタスクについてはより多くのキャッシュメモリの領域を確保することで、キャッシュヒット率を高くして当該タスクの実行時間を維持できる。また、プロセッサにおける実行時間の割り当てが相対的に低いタスクについてもその比率に応じたキャッシュメモリの領域を確保するため、ある程度のキャッシュヒット率を維持できる。そのため、本実施の形態１では、結果的にキャッシュメモリ全体の利用効率を向上させ、全タスクの処理時間を短縮することができる。

尚、図１では、実行時間割当部１１２がＣＰＵ１１０の内部に含まれる例を示したが、本実施の形態１はこれに限定されない。つまり、実行時間割当部１１２は、ＣＰＵ１１０の外部でも良く、キャッシュ制御装置１２０に内蔵されていても構わない。

以上のように、本実施の形態１では、実行時間の割当比率に応じて、使用するキャッシュメモリの領域を適応的に設定し、各タスクの処理実行部の使用率とキャッシュの使用率を均衡することができる。これにより、リアルタイム制御システムにおける各タスクのリソースの利用率を関連技術と比べて正確に設定できる。

＜実施の形態２＞
本実施の形態２は、上述した実施の形態１の具体例を示す。本実施の形態２にかかるキャッシュ制御装置は、複数のハードウェアスレッドについてキャッシュメモリの領域を割り当てるものである。特に、キャッシュメモリの領域は、ライン単位でスレッドに割り当てるものとする。ここで、キャッシュメモリのライン数（Ｌ）及びプロセッサのスロット数（Ｓ）は２のべき乗とする。但し、Ｌ＞Ｓの関係が成り立つものとする。

図５は、本実施の形態２にかかるキャッシュ制御装置２２０を含むコンピュータシステムの構成を示すブロック図である。図５には、リアルタイム制御における並列処理を行うコンピュータシステムのうち、ＣＰＵ２１０と、キャッシュ制御装置２２０と、キャッシュメモリ２３０とが代表して記載されている。キャッシュ制御装置２２０は、ＣＰＵ２１０とキャッシュメモリ２３０とメインメモリ（不図示）とに接続されている。ここで、キャッシュメモリ２３０は、メモリの領域が複数のウェイにより分割され、ウェイ内で複数のラインにより管理されているものとする。但し、キャッシュメモリ２３０は、バンク分けされていないものとする。

ＣＰＵ２１０、メモリアクセス部２１１及びスレッドスケジューラ２１２は、図１のＣＰＵ１１０、メモリアクセス部１１１及び実行時間割当部１１２の具体例の１つである。ＣＰＵ２１０は、複数の命令流として複数のハードウェアスレッド（以下、単に「スレッド」という。）にタイムスロット（以下、単に「スロット」という。）を割り当てて実行するマルチスレッドプロセッサである。

メモリアクセス部２１１は、図１のＩＤｄ２の一例としてスレッドＩＤ（ＨｔＩＤ）ｄ２ａをキャッシュ制御装置２２０へ通知する。スレッドスケジューラ２１２は、各スレッドに任意の実行時間を割り当てることが可能である。具体的には、スレッドスケジューラ２１２は、複数のスレッドに対して、所定数のタイムスロットを割り当てるものである。また、スレッドスケジューラ２１２は、スレッドに実行時間を割り当てた情報であるスロット割当情報ｄ３ａを保持している。ここで、スロット割当情報ｄ３ａは、実行時間の割当比率ｄ３の一例であり、ＣＰＵ２１０内の複数のタイムスロットと複数のスレッドとの対応関係を示す情報である。ここでは、スロット割当情報ｄ３ａは、スロット番号とスレッド番号との対応付けを定義した情報である。そして、スレッドスケジューラ２１２は、スロット割当情報ｄ３ａをキャッシュ制御装置２２０へ通知する。また、スレッドスケジューラ２１２は、各スレッドの実行状況や制御プログラムの指示に応じてスロット割当情報ｄ３ａを動的に変更するものである。尚、スロット割当情報ｄ３ａには、例えば、特許文献１のスケジューラのスロット設定を適用可能である。

キャッシュ制御装置２２０、アドレス分割部２２１、領域決定部２２２及びヒットミス判定部２２３は、図１のキャッシュ制御装置１２０、アドレス分割部１２１、領域決定部１２２及びヒットミス判定部１２３の具体例の１つである。アドレス分割部２２１は、アクセスアドレスｄ１をメモリアクセス部２１１から受け付けたアクセスアドレスｄ１をタグｄ４と、ラインｄ５とに分割し、さらにラインｄ５について上位領域ｄ５１及び下位領域ｄ５２とに分割する。本実施の形態２にかかる論理アドレスのビット構成例として図６に示す。

領域決定部２２２は、スロット割当情報ｄ３ａに含まれるタイムスロットに基づいて、各スレッドに割り当てるキャッシュメモリの領域を特定する。これにより、タイムスロットという所定の実行期間の単位を用いて実行時間を的確に認識でき、領域の特定も確実に行うことができる。また、シングルコアプロセッサにおけるリアルタイム処理において、各命令流のプロセッサにおける実際の使用率とキャッシュメモリの使用率を均衡し、キャッシュメモリ全体の利用効率を向上させることができる。

また、領域決定部２２２は、スレッドＩＤｄ２ａ、上位領域ｄ５１及び下位領域ｄ５２に応じて、キャッシュメモリ２３０へ各種アクセスを行う。また、領域決定部２２２は、アクセス対象のラインを指定するためのラインアドレスｄ６１をキャッシュメモリ２３０へ出力する。さらに、領域決定部２２２は、キャッシュメモリ２３０内の所定のラインを無効化するためのインバリデート信号ｄ６２をキャッシュメモリ２３０へ出力する。尚、ヒットミス判定部２２３は、ヒットミス判定部１２３と同等のもので構わない。

図７は、本実施の形態２にかかる領域決定部２２２を含む構成を示すブロック図である。領域決定部２２２は、割当スロット数算出部５１１と、割当スロット番号検出部５１２と、引数対応付け部５１３と、割当スロット数５３１と、Ｉｎｄｅｘテーブル５３２と、引数生成部５４と、オフセット生成部５５と、加算部５６と、ライトバックインバリデート処理部５７とを備える。割当スロット数算出部５１１は、スレッドスケジューラ２１２から通知されるスロット割当情報ｄ３ａから、スレッドごとの割当スロット数５３１を算出する。具体的には、割当スロット数算出部５１１は、スロット割当情報ｄ３ａに含まれるタイムスロットをスレッドごとに集計して各スレッドの割当スロット数を算出する。そして、割当スロット数算出部５１１は、算出された割当スロット数５３１を領域割当情報の一部として記憶領域に格納する。そのため、割当スロット数５３１により、スレッドＩＤｄ２ａから割当スロット数の比率に応じて各スレッドに割り当てるキャッシュメモリ２３０内のラインを特定できる。このように、実行時間の割り当てを割り当てられたタイムスロット数と解釈することで、実行時間の割当比率を容易に認識することができ、さらに、キャッシュメモリの領域をライン単位とすることで領域の特定も容易となる。

また、割当スロット番号検出部５１２は、スロット割当情報ｄ３ａからスレッドごとに割り当てられたスロット番号である割当スロット番号情報５２０、つまりインデックス値を算出する。そして、引数対応付け部５１３は、スレッドごとに当該インデックスと引数とを対応付けて、Ｉｎｄｅｘテーブル５３２として記憶領域に格納する。ここで、Ｉｎｄｅｘテーブル５３２は、スレッドごとに引数とインデックス値との対応付けを管理するテーブルである。

そのため、割当スロット数算出部５１１、割当スロット番号検出部５１２及び引数対応付け部５１３は、加工部２２２１といえ、割当スロット数５３１及びＩｎｄｅｘテーブル５３２は、領域割当情報２２２３ということができる。

図８は、本実施の形態２にかかるスロット割当情報ｄ３ａ、割当スロット数情報５３１及びIndexテーブル５３２の例を示す図である。図８では、スロット数が"１６"、スレッド数が"４"、キャッシュメモリ２３０のウェイ数が"４"、ウェイ当たりライン数が"３２"であるものとする。図８のスロット割当情報ｄ３ａでは、タイムスロット番号０〜１５についてスレッドＩＤ０〜４が割り当てられている場合を示す。また、図８の割当スロット数５３１は、スレッドＩＤ０〜４について、それぞれ割当スロット数"４"、"３"、"６"、"３"が対応付けられている場合を示す。

ここで、引数の最大値を"全スロット数−１"とする。図８では、引数が"０"〜"１５"つまりウェイ当たりのライン数"３２"の半分としている。また、インデックス値には、各スレッドに割り当てられたスロット番号が引数"０"から昇順に格納される。図８では、スレッド１について引数"０"〜"２"にそれぞれインデックス値"４"〜"６"が対応付けて格納され、引数"３"以降にはインデックス値"０"が格納されていることを示す。

図７に戻り説明を続ける。また、領域決定部２２２は、アドレス分割部２２１から受け付けたスレッドＩＤｄ２ａに対応する割当スロット数５３１を特定し、引数生成部５４へ出力する。つまり、領域決定部２２２は、キャッシュメモリ２３０へのアクセス要求に含まれる命令流の識別情報と、割当スロット数とに基づいて、アクセス対象のキャッシュメモリ２３０の領域を決定する。これにより、効率的にアクセス対象の領域を特定することができ、アクセス要求を高速化できる。

ここで、上位領域ｄ５１は、アクセスアドレスｄ１のラインｄ５のうちインデックスに相当する。上位領域ｄ５１はキャッシュメモリ２３０内のラインの特定に用いられる。図７の場合、上位領域ｄ５１は４ビットで表現される。下位領域ｄ５２は、キャッシュメモリ２３０のオフセットの生成に用いられる。ここで、下位領域ｄ５２のビット幅は、以下の式（１）により算出することができる。
ビット幅 ＝ log₂ ( 全ライン数 / 全スロット数 ) ・・・（１）
そのため、図７の場合、下位領域ｄ５２は１ビットで表現される。

引数生成部５４は、アドレス分割部２２１から取得した上位領域ｄ５１と、スレッドＩＤｄ２ａにより特定された割当スロット数５３１とから、引数を生成し、Ｉｎｄｅｘテーブル５３２へ出力する。例えば、引数生成部５４は、上位領域ｄ５１を割当スロット数５３１で除算し、その余りを引数としてもよい。その後、Ｉｎｄｅｘテーブル５３２は、スレッドＩＤｄ２ａと引数生成部５４からの引数とから該当するインデックス値を特定し、加算部５６へ出力する。

オフセット生成部５５は、アドレス分割部２２１から取得した下位領域ｄ５２に基づきラインのオフセットを生成する。例えば、ここでは、下位領域ｄ５２は１ビットの値つまり"０"又は"１"のためそれぞれ"０"又は"１６"へ変換するものとする。そして、加算部５６は、オフセット生成部５５による生成後のオフセットと、Ｉｎｄｅｘテーブル５３２から出力されたインデックス値とを加算して、アクセス対象のラインアドレスｄ６１としてキャッシュメモリ２３０へアクセスする。そのため、引数生成部５４、オフセット生成部５５及び加算部５６は、割当制御部２２２２といえる。

キャッシュメモリ２３０は、ウェイ選択論理部２３１と、ウェイｗ０〜ｗ３とを備える。ここで、本実施の形態２にかかるウェイ選択論理部２３１は、ウェイｗ０〜ｗ３の全てを固定的に選択するものとする。また、ウェイ選択論理部２３１は、ヒットミス判定部２２３においてヒットミス判定がＭｉｓｓであった場合、つまり、Ｍｉｓｓリフィル時にヒットミス判定部２２３から出力される書き込み対象のウェイを選択するウェイ選択信号ｄ８１に応じて、ウェイを選択する。ウェイｗ０〜ｗ３は、それぞれキャッシュメモリ２３０における記憶領域を４分割したものである。また、各ウェイは、３２ラインに分割されている。

これにより、キャッシュメモリ２３０は、全てのウェイｗ０〜ｗ３から該当するラインアドレスｄ６１のデータを読み出す。このとき、ウェイ選択論理部２３１は、ウェイｗ０〜ｗ３の全てが選択されているため、ウェイｗ０〜ｗ３から読み出されたデータをそれぞれタグｄ７０からｄ７３として、ヒットミス判定部２２３へ出力する。そして、ヒットミス判定部２２３は、読み出されたラインに含まれるタグと、アドレス分割部２２１からのタグｄ１とを比較してヒットミス判定を行う。

図９は、本実施の形態２にかかる領域決定時のキャッシュメモリ２３０内の１ウェイ当たりのデータの例を示す図である。図９のウェイは、３２ラインに分割されおり、各ラインは、ライングループＬ０、Ｌ１、Ｌ２又はＬ３のいずれかに所属するように管理されている。ここでは、ライングループＬ０は、ライングループＬ０ｘ及びＬ０ｙ、ライングループＬ１は、ライングループＬ１ｘ及びＬ１ｙ、ライングループＬ２は、ライングループＬ２ｘ及びＬ２ｙ、ライングループＬ３は、ライングループＬ３ｘ及びＬ３ｙとなっている場合を示す。そのため、ライングループＬ０ｘ、Ｌ１ｘ、Ｌ２ｘ、Ｌ３ｘは、オフセット"＋０"の場合のインデックス値により特定され、ライングループＬ０ｙ、Ｌ１ｙ、Ｌ２ｙ、Ｌ３ｙは、オフセット"＋１６"の場合のインデックス値により特定される。

このため、例えば、図８のＩｎｄｅｘテーブル５３２から特定されるスレッド１については、ライングループＬ１が対応し、具体的には、ライングループＬ１ｘに属するライン"４"〜"６"及びライングループＬ１ｙに属するライン"２０"〜"２２"がャッシュ領域として割り当てられたこととなる。

尚、本実施の形態２にかかるスロット割当情報ｄ３ａにおけるスレッドの割り当ての例は図８に限定されない。図１０は、本実施の形態２にかかるスロット割当情報、割当スロット数情報及びIndexテーブルの他の例を示す図である。図１０のスロット割当情報ｄ３ａでは、各スロットに対してスレッド番号がランダムに割り当てられている例を示す。図１０では、図８と同様に、割当スロット数５３１が、スレッドＩＤ０〜４について、それぞれ割当スロット数"４"、"３"、"６"、"３"が対応付けられている。しかし、図１０の割当スロット番号情報５２０は、各スレッドの割当スロット番号は図８とは異なるものとなる。同様に、Ｉｎｄｅｘテーブル５３２の内容も図８とは異なる。そのため、領域決定時のキャッシュメモリ内の各ラインが属するライングループは、図１１に示すようになる。このように、本実施の形態２により、スロット割当情報ｄ３ａ内の割り当て状態と、キャッシュメモリ２３０の各ウェイ内の各ラインのライングループへの割り当て状態とが同期を取ることができる。そのため、スロット割当情報ｄ３ａにおいて割り当てられたスレッドを漏らさず、キャッシュメモリ２３０のいずれかのラインに割り当てることができる。

図１２は、本実施の形態２にかかる領域分割方法の処理の流れを示すフローチャートである。まず、領域決定部２２２は、スレッドスケジューラ２１２から、各スロット毎にスレッドが割り当てられたスロット割当情報ｄ３ａ（「スロット番号」対「スレッド番号」）を受け付ける（Ｓ２１）。例えば、スレッドスケジューラ２１２がスロット割当情報ｄ３ａを設定又は更新する度に領域決定部２２２へ通知してもよい。または、領域決定部２２２が定期的に、スロット割当情報ｄ３ａを読み出しにいってもよい。

次に、割当スロット数算出部５１１は、各スレッド毎に割り当てられた割当スロットの数５３１（「スレッド番号」対「スロット番号」）を算出する（Ｓ２２）。例えば、割当スロット数算出部５１１は、スロット割当情報ｄ３ａからスレッドごとに割り当てられているスロット数を集計する。そして、割当スロット数算出部５１１は、当該集計した値を割当スロット数５３１として記憶領域に格納する（Ｓ２３）。

また、割当スロット番号検出部５１２は、スロット割当情報ｄ３ａから各スレッド毎に割り当てられた割当スロット番号（「スレッド番号」対「スロット番号」（Index値））を検出する（Ｓ２４）。例えば、割当スロット番号検出部５１２は、スロット割当情報ｄ３ａからスレッドごとに割り当てられているスロット番号を検出し、検出されたスロット番号をインデックス値とする。そして、引数対応付け部５１３は、各スレッド毎に検出されたインデックス値と引数とを対応付けてＩｎｄｅｘテーブル５３２として記憶領域に格納する（Ｓ２５）。

図１３は、本実施の形態２にかかるアクセス処理方法の処理の流れを示すフローチャートである。まず、領域決定部２２２は、メモリアクセス部２１１からキャッシュメモリ２３０に対するアクセス要求としてアクセスアドレスｄ１及びスレッドＩＤｄ２ａを受け付ける（Ｓ３１）。次に、領域決定部２２２は、スレッドＩＤｄ２ａにより割当スロット数５３１を特定する（Ｓ３２）。図８及び図１０の場合、スレッドＩＤｄ２ａが"１"であれば、割当スロット数５３１として"３"が特定される。

また、アドレス分割部２２１は、アクセスアドレスｄ１を分割する（Ｓ３３）。例えば、アドレス分割部２２１は、アクセスアドレスｄ１をタグｄ４及びラインｄ５に分割し、ラインｄ２を上位領域ｄ５１及び下位領域ｄ５２に分割する。尚、メモリアクセス部２１１は、予めアクセスアドレスｄ１をタグｄ４及びラインｄ５に分割するか、さらにラインｄ５を上位領域ｄ５１及び下位領域ｄ５２に分割した上で、アクセス要求としてキャッシュ制御装置２２０へ通知しても構わない。

そして、引数生成部５４は、ステップＳ３２において特定された割当スロット数５３１と、ステップＳ３３において分割された上位領域ｄ５１とから引数を生成する（Ｓ３４）。図８では、引数生成部５４は、上位領域ｄ５１を割当スロット数５３１の"３"で除算するため、その余りは、"０"、"１"、"２"のいずれかとなる。その後、領域決定部２２２は、スレッドＩＤｄ２ａと引数によりＩｎｄｅｘテーブル５３２からインデックス値を取得する（Ｓ３５）。例えば、引数が"１"の場合、インデックス値は図８では"５"となり、図１０では"６"となる。

また、ステップＳ３４と並行して、オフセット生成部５５は、下位領域ｄ５２からオフセットを生成する（Ｓ３６）。例えば、下位領域ｄ５２が"１"の場合、オフセットが"１６"に変換されるものとする。

その後、加算部５６は、インデックス値とオフセットからライン番号を算出する（Ｓ３７）。例えば、図８ではインデックス値"５"、オフセット"１６"の場合、ライン番号"２１"が算出される。また、図１０ではインデックス値"６"、オフセット"１６"の場合、ライン番号"２２"が算出される。そして、領域決定部２２２は、ライン番号に対応するラインをキャッシュメモリ２３０から読み出す（Ｓ３８）。図８では、領域決定部２２２は、キャッシュメモリ２３０内のウェイｗ０におけるライン"２１"を読み出す。これは、ライングループＬ１に属するため、スレッドＩＤｄ２ａで指定されたスレッド１に対応する領域から読み出されることとなる。同様に、領域決定部２２２は、ウェイｗ１〜ｗ３からもライン"２１"を読み出す。尚、図１０では、領域決定部２２２は、キャッシュメモリ２３０内のウェイｗ０〜２３におけるライン"２２"を読み出す。ここでも、同様に、ライングループＬ１に属するため、スレッドＩＤｄ２ａで指定されたスレッド１に対応する領域から読み出されることとなる。

続いて、スレッドにおけるスロットの割当比率が変更される場合について説明する。上述したように、スレッドスケジューラ２１２により各スレッドにおける実行時間の割当比率は動的に変更される。その場合、領域決定部２２２は、割当スロット数５３１及びＩｎｄｅｘテーブル５３２を更新すると共に、キャッシュメモリ２３０に対してライトバックインバリデート処理を行う。

すなわち、領域決定部２２２は、実行時間の割当比率が変更された場合に、当該変更後の実行時間の割当比率に応じて当該変更にかかるスレッドに割り当てるキャッシュメモリの領域を更新する。例えば、あるスレッドにおける実行時間の割当比率が高く変更された場合、スレッドにおけるキャッシュへのアクセス頻度も一般的には増加する。そのため、アクセス頻度の増加に合わせて、当該スレッドにおけるキャッシュメモリの領域の割当量も増加させることで、リソースの使用率とキャッシュメモリの使用率との均衡を維持することができる。よって、継続的にキャッシュメモリの利用効率を高めることができる。

さらに、領域決定部２２２は、前記更新と共に、変更により実行時間の割当比率が減少した命令流に対して既に割り当てられていたキャッシュメモリの領域のうち、当該減少分を無効化する。これにより、新たに割り当てられたキャッシュメモリの領域を、必要になった際に即時に利用することができる。

そのため、ライトバックインバリデート処理部５７は、Ｉｎｄｅｘテーブル５３２の更新に応じて、該当のラインを無効化するためのインバリデート信号ｄ６２をキャッシュメモリ２３０へ出力する。言い換えると、ライトバックインバリデート処理部５７は、指定されたインデックス値に対応するラインのデータをメインメモリへ書き戻し、かつ、当該ラインを無効化する。このとき、ライトバックインバリデート処理部５７は、全ウェイについて横断的に実行する。

ここで、スレッドにおけるスロットの割当比率が変更される場合の動作について、図１４、図１５及び図１６を用いて説明する。図１４は、本実施の形態２にかかる割当変更処理の流れを示すフローチャートである。但し、図１２と同等の処理については同じ符号を付している。図１５は、本実施の形態２にかかる割当変更後のスロット割当情報ｄ３ａ、割当スロット数情報５３１及びIndexテーブル５３２の例を示す図である。図１６は、本実施の形態２にかかる割当変更後のキャッシュメモリ内の１ウェイ当たりのデータの例を示す図である。

図１５では、スロット３に割り当てられていたスレッド０がスレッド１に変更された場合について説明する。このとき、スレッドスケジューラ２１２は、スロット割当情報ｄ３ａを更新する。そして、領域決定部２２２は、変更後のスロット割当情報ｄ３ａを受け付ける（Ｓ２１）。

次に、割当スロット数算出部５１１は、変更されたスレッドの割当スロット数５３１を更新する。具体的には、割当スロット数算出部５１１は、スレッド０の変更後の割当スロット数"３"を算出し、また、スレッド１の変更後の割当スロット数"４"を算出する（Ｓ２２）。そして、割当スロット数算出部５１１は、割当スロット数５３１のうちスレッド０の割当スロット数を"４"から"３"へ、また、スレッド１の割当スロット数を"３"から"４"へ更新する（Ｓ２３、図１５）。また、割当スロット番号検出部５１２は、変更後の割当スロット番号を検出する（Ｓ２４）。具体的には、割当スロット番号検出部５１２は、変更にかかるスレッド１の割当スロット番号"３"を算出する。

併せて、領域決定部２２２は、割り当てが変更されたスロット及びスレッドを特定する（Ｓ４１）。ここでは、スロット番号"３"並びにスレッド０及びスレッド１が特定される。続いて、領域決定部２２２は、変更されたスレッドの変更前のインデックス値をＩｎｄｅｘテーブル５３２から取得する（Ｓ４２）。具体的には、領域決定部２２２は、スロット番号"３"が変更前に割り当てられていたスレッド０における引数"３"に対応付けられたインデックス値"３"を取得する。

そして、ライトバックインバリデート処理部５７は、取得したインデックス値に対応するラインについて、各ウェイをライトバックインバリデートする（Ｓ４３）。例えば、ウェイｗ０では、ライン"３"及びライン"１９"がライトバックインバリデートされる（図１６）。同様に、ウェイｗ１〜ｗ３についてもライトバックインバリデートされる。ここで、ライン"３"をライングループＬ０ｘｂ及びライン"１９"をライングループＬ０ｙｂとする。

その後、引数対応付け部５１３は、変更されたスレッドのＩｎｄｅｘテーブル５３２を更新する（Ｓ４６）。具体的には、引数対応付け部５１３は、スレッド０の引数"３"のインデックス値を"０"に更新する。また、領域決定部２２２は、スレッド１の引数"０"〜"３"のインデックス値を"３"〜"６"に更新する。これにより、変更前のライングループＬ０のうち、ライングループＬ０ｘａ及びＬ０ｘｂは引き続きスレッド０に割り当てられ、変更後のライングループＬ０ａとなる。また、ライングループＬ０ｘｂ及びＬ０ｙbは今後スレッド１の引数"０"へのアクセスが発生した場合に、変更後のライングループＬ１ｂに加えられる。

このように、本実施の形態２では、スレッドにおけるスロットの割当比率が動的に変更される場合であっても、処理速度の比率と領域の割当比率との均衡を維持すること、つまり同期することができる。よって、キャッシュメモリ全体の利用効率を向上することができる。

＜実施の形態３＞
実施の形態３では、キャッシュメモリがバンク分けされた場合について、バンク分けされていない上述した実施の形態２と同様に実現可能であることを説明する。図１７は、本実施の形態３にかかる領域決定部２２２ａの構成を示すブロック図である。尚、実施形態３にかかるキャッシュ制御装置を含むコンピュータシステムの構成は、図５と同等であるため、図示及び説明を省略する。

領域決定部２２２ａは、領域決定部２２２の構成のうちオフセット生成部５５がバンク変換部５５ａに置き換わったものである。バンク変換部５５ａは、下位領域ｄ２２をラインのオフセットに変換する。例えば、ここでは、下位領域ｄ２２は１ビットの値つまり"０"又は"１"のためそれぞれ"０"又は"１６"へ変換するものとする。つまり、下位領域ｄ５２は、バンクの特定に用いられる。本実施の形態３にかかる論理アドレスのビット構成例として図１８に示す。

そして、加算部５６は、バンク変換部５５ａによる変換後のオフセットと、Ｉｎｄｅｘテーブル５３２から出力されたインデックス値とを加算して、アクセス対象のラインとしてキャッシュメモリ２３０ａへアクセスする。これにより、キャッシュメモリ２３０ａは、全てのウェイｗ０〜ｗ３から該当するラインのデータを読み出す。

また、キャッシュメモリ２３０ａは、ウェイｗ０ａ〜ｗ３ａの４つのウェイを有し、各ウェイは２つのバンクにグループ分けされているものとする。図１９は、本実施の形態３にかかるバンクを用いた場合の領域決定時のキャッシュメモリ内の１ウェイ当たりのデータの例を示す図である。ここでは、バンク数がウェイ当たり"２"、ライン数が"３２"つまりライン数がバンク当たり"１６"であるものとする。例えば、ウェイｗ０は、バンクｂ０及びｂ１を有し、バンクｂ０にはライン"０"〜"１５"、バンクｂ１にはライン"１６"〜"３１"が所属している。ウェイ内のラインをバンクにグループ分けすることで、領域決定部２２２ａは、"０"又は"１"のバンク番号と"０"乃至"１５"のライン番号とを指定することで、所望のラインへアクセスすることができる。そのため、指定すべきライン番号がウェイ当たりの全ライン数"３２"ではなく、その半分の"１６"とすることができ、領域決定部２２２に比べて領域決定部２２２ａの容量を抑えることができる。

例えば、キャッシュメモリ２３０ａのウェイｗ０では、バンクｂ０のライン"０"〜"３"とバンクｂ１のライン"１６"〜"１９"がライングループＬ０として、スレッド０のためのキャッシュ領域として割り当てられたこととなる。同様に、スレッド１についてはライングループＬ１、スレッド２についてはライングループＬ２及びスレッド３についてはライングループＬ３がキャッシュ領域として割り当てられたこととなる。

図２０は、本実施の形態３にかかるバンクを用いた場合の割当変更後のキャッシュメモリ内のデータの例を示す図である。ここでは、図１５と同様に、スロット３に割り当てられていたスレッド０がスレッド１に変更された場合について説明する。このとき、ウェイｗ０では、バンクｂ０のライン"３"及びバンクｂ１のライン"１９"がライトバックインバリデートされる。同様に、ウェイｗ１〜ｗ３についてもライトバックインバリデートされる。ここで、ライン"３"及び"１９"をライングループＬ０ｂとする。そして、変更前のライングループＬ０のうち、ライングループＬ０ａは引き続きスレッド０に割り当てられ、ライングループＬ０ｂは今後スレッド１の引数"０"へのアクセスが発生した場合に、ライングループＬ１に加えられる。

このように、本実施の形態３についても上述した実施の形態２と同様の効果を奏することができる。

＜実施の形態４＞
本実施の形態４は、上述した実施の形態１の具体例を示す。特に、上述した実施の形態２又は３との違いとして、キャッシュメモリの領域をウェイ単位でスレッドに割り当てるものとする。ここで、キャッシュメモリのウェイ数は、プロセッサのスロット数と等しいものとする。
図２１は、本実施の形態４にかかるキャッシュ制御装置３２０を含むコンピュータシステムの構成を示すブロック図である。尚、図２１のうち、図５と同等の構成については同一の符号を付し、説明を省略するものとする。領域決定部３２２は、ラインアドレスｄ６１及びインバリデート信号ｄ６２に加え、アクセス対象のウェイを選択させるためのウェイ選択信号ｄ６０をキャッシュメモリ２３０へ出力する。

図２２は、本実施の形態４にかかる領域決定部３２２の構成を示すブロック図である。図２４は、本実施の形態４にかかる領域決定時のデータの例を示す図である。また、図２２では、スロット数が"４"、スレッド数が"３"、キャッシュメモリ３３０のウェイ数が"４"であるものとする。そのため、図２２のスロット割当情報ｄ３ｂは、４スロットについて３スレッドが割り当てられていることとなる。例えば、図２４に示すようにスロット０〜３について、スレッド"０"、"１"、"１"、"２"が対応付けられており、スロット４以降にはスレッドが割り当てられていないものとする。

領域決定部３２２は、割当ウェイ番号算出部６１と、ウェイ設定情報６２と、アドレス連接部６３と、ライトバックインバリデート処理部６４とを備える。割当ウェイ番号算出部６１は、スロット割当情報ｄ３ｂを受け付けて、各スレッド毎に割り当てられた割当ウェイ番号を算出する。例えば、図２４の場合、割当ウェイ番号算出部６１は、スロット割当情報ｄ３ｂからスレッド番号"０"、"１"、"２"を検出する。そして、割当ウェイ番号算出部６１は、各スロットをウェイに対応付けて、スロットに割り当てられたスレッド番号を対応するウェイ番号に設定し、ウェイ設定情報６２として内部の記憶領域に格納する。つまり、割当ウェイ番号算出部６１は、領域としてのウェイの割り当てを決定する。また、領域決定部３２２は、受け付けたスレッドＩＤｄ２ａに対応するウェイ番号をウェイ設定情報６２から特定し、特定したウェイ番号をウェイ選択信号ｄ６０としてウェイ選択論理部３３１へ出力する。また、アドレス連接部６３は、上位領域ｄ５１及び下位領域ｄ５２を受け付けて、これらを連接してラインアドレスｄ６１としてキャッシュメモリ３３０へ出力する。本実施の形態４にかかる論理アドレスのビット構成例として図２３に示す。

キャッシュメモリ３３０は、ウェイ選択論理部３３１と、ウェイｗ０〜ｗ３とを備える。但し、ウェイｗ０〜ｗ３は、バンクの有無は問わない。ウェイ選択論理部３３１は、領域決定部３２２から通知されたウェイ選択信号ｄ６０に基づき読み出し対象のウェイを選択する。

ここで、本実施の形態４にかかる領域決定部３２２は、次のように表現できる。すなわち、領域決定部３２２は、実行時間の割当情報ｄ３ｂに含まれる複数のタイムスロットのそれぞれをキャッシュメモリ３３０内の複数のウェイのいずれかと対応付け、タイムスロットに対応付けられたウェイを、当該タイムスロットに対応付けられたスレッドに割り当てるキャッシュメモリの領域として特定する。これにより、実施の形態２又は３に比べて、領域決定部３２２の回路規模を抑えることができる。また、実施の形態２又は３に比べて、簡易な方法で領域を割り当てるため、領域の決定処理の負荷を軽減できる。その上で、実施の形態２又は３と同等の効果を奏することができる。

続いて、実施の形態４において、スレッドにおけるスロットの割当比率が変更される場合について説明する。図２２のライトバックインバリデート処理部６４は、指定されたウェイのデータをメインメモリへ書き戻し、かつ、当該ウェイを無効化する。

図２５は、本実施の形態４にかかる領域更新時のデータの例を示す図である。図２５では、スロット１に割り当てられていたスレッド１がスレッド０に変更された場合を示す。このとき、スレッドスケジューラ２１２は、スロット割当情報ｄ３ｂを更新する。そして、領域決定部３２２は、変更後のスロット割当情報ｄ３ｂを受け付ける。また、割当ウェイ番号算出部６１は、割り当てが変更されたスロットを特定する。ここでは、スロット番号"１"がスレッド１からスレッド０に変更されたことが特定される。

次に、割当ウェイ番号算出部６１は、変更されたスロットに対応するウェイ番号に設定されたスレッドＩＤを更新する。つまり、割当ウェイ番号算出部６１は、ウェイ設定情報６２を更新する。具体的には、割当ウェイ番号算出部６１は、ウェイ番号"１"のスレッド番号を"１"から"０"へ更新する（図２５）。そして、割当ウェイ番号算出部６１は、更新されたウェイ番号をライトバックインバリデート処理部６４へ通知する。その後、ライトバックインバリデート処理部６４は、通知されたウェイ番号についてライトバックインバリデートする。ここでは、ウェイｗ１が対象となる。

このように、本実施の形態４においても、実施の形態２及び３と同様に、スレッドにおけるスロットの割当比率が動的に変更される場合であっても、処理速度の比率と領域の割当比率との均衡を維持すること、つまり同期することができる。よって、キャッシュメモリ全体の利用効率を向上することができる。

＜実施の形態５＞
本実施の形態５は、上述した実施の形態１の具体例を示す。但し、キャッシュ制御装置を利用するプロセッサが複数存在する場合を対象とする。本実施の形態５にかかる領域決定部は、複数の命令流が分散して割り当てられた複数のプロセッサ間の処理速度の比率に基づいて、各命令流に割り当てるキャッシュメモリの領域の割り当てを決定するものである。ここで、処理速度とは、プロセッサにおける単位時間当たりの処理性能を示す指標である。処理速度は、例えば、プロセッサに割り当てられた単位時間当たり実行時間や、プロセッサのクロック周波数等を示す。

また、処理速度の比率は、各タスクの重み付け情報と表現しても構わない。また、各プロセッサは周波数が異なる場合があり、各命令流の処理速度は割り当てられたプロセッサにより異なることとなる。つまり、本実施の形態５では、各周波数の比率を処理速度の比率として扱うものである。または、各プロセッサの実行状態に応じて、どのプロセッサにどのくらいキャッシュメモリの領域を割り当てるかを決定するようにしてもよい。

本実施の形態５は、マルチコアプロセッサを搭載したコンピュータシステムに対して適用可能である。図２６は、本実施の形態５にかかるキャッシュ制御装置を含むコンピュータシステムの構成を示すブロック図である。図２６には、コンピュータシステムのうち、ＣＰＵ４１１、４１２、・・・４１ｎと、キャッシュ制御装置４２０と、キャッシュメモリ４３０と、処理速度情報４４０とが代表して記載されている。ここで、ＣＰＵ４１１〜４１ｎとキャッシュ制御装置４２０とが同じバスに接続されるものとする。

ＣＰＵ４１１〜４１ｎは、それぞれ上述したマルチスレッドコアであるか、シングルコアであるかは問わない。また、ＣＰＵ４１１〜４１ｎは、それぞれ処理速度情報４４０が保持されたレジスタに、自己の周波数等の処理速度の情報を通知する。処理速度情報４４０は、レジスタ自体であるか、複数のプロセッサへの命令流の割り当てを行うスケジューラ等であっても構わない。また、キャッシュメモリ４３０は、上述したキャッシュメモリ２３０等と同等のものである。

キャッシュ制御装置４２０は、アドレス分割部４２１と、領域決定部４２２と、ヒットミス判定部４２３とを備える。アドレス分割部４２１及びヒットミス判定部４２３は、上述したアドレス分割部２２１及びヒットミス判定部２２３と同等のもので実現可能である。領域決定部４２２は、処理速度情報４４０から処理速度比率ｄ３ｃを取得し、処理速度比率ｄ３ｃに基づいて、各プロセッサに割り当てるキャッシュメモリの領域の割り当てを決定する。領域の割当の仕方は、実施の形態２〜４と同等のものを適用することができる。また、各プロセッサに命令流が割り当てられることにより、リアルタイム制御における並行処理を実現できる。

これにより、リアルタイム処理において各命令流のプロセッサにおける実際の使用率とキャッシュメモリの使用率を均衡することができる。そのため、キャッシュメモリ全体の利用効率を向上させることができる。

＜その他の実施の形態＞
上述した実施の形態１〜５にかかるキャッシュ制御装置は、キャッシュメモリを内蔵し、リアルタイム制御を行うデータ処理装置に適用可能である。

尚、上述した実施の形態２及び３では、全ライン数が全スロット数の整数倍となる例により説明をした。そのため、割当スロット数が最小値"１"であるスレッドに対しても割当スロット数の比率に応じて確実にラインを割り当てることができる。しかし、キャッシュメモリ２３０及び２３０ａ内のラインは一部が故障する場合があり、その際は当該故障したラインを無効化し、そのラインを領域の割当対象から除外する必要がある。この場合には、使用可能なライン数が全スロット数の整数倍でなくなる可能性がある。また、上述した実施の形態４では、全ウェイ数が全スロット数と一致する例により説明した。この場合についても同様の課題が発生し得る。

そこで、領域決定部は、実行時間の割当比率のうち最も小さい比率が割り当てられた命令流については、当該比率に関わらず、キャッシュメモリの領域のうち割り当て可能な最小単位の領域を、少なくとも当該命令流に割り当てるキャッシュメモリの領域として決定するとよい。例えば、あるスレッドの割当スロット数が最小値"１"の場合、キャッシュメモリの領域の最小単位のラインを必ず割り当てるものとする。

また、スロット数がウェイ数より多い場合には、実行時間の割当比率に関わらず、１スロットしか割り当てられていないスレッドに対して、ウェイを割り当てるようにすることが考えられる。または、その場合にのみウェイ内のラインを所定数にグループ分けするようにしてもよい。

これにより、比率が小さ過ぎて領域の割り当てができない場合であっても最低限の領域を割り当てることで、ある程度のキャッシュヒット率を実現でき、所定時間内の終了時間を確保できる。つまり、プロセッサにおける処理速度の割当比率が最小のスレッドについても最低限一単位の領域を確保するものである。

さらに、領域決定部は、キャッシュメモリにおけるラインの故障のチェック機構を設け、キャッシュメモリにおける故障したラインを除いて領域の割り当てを決定することが望ましい。これにより、キャッシュヒット率を向上させることができる。

また、上記のことから全ライン数が全スロット数の整数倍に限定されない。また、スレッドに割り当てるキャッシュメモリの領域の最小単位をライン単位としたがこれに限定されない。例えば、複数ラインを領域の最小単位としてもよい。

尚、セットアソシアティブ方式のキャッシュにおいては、ウェイ及びインデックスの両方を領域設定の対象としてもよい。例えば、ハードウェアスレッドの優先度設定に従い、使用できるウェイ数を設定してもよい。または、インデックスを分割して割り当てても良い。

尚、その他の実施の形態として、複数のタスクを処理するプロセッサと、キャッシュと、タスクに割り当てられた重み付け情報を制御する装置と、タスクの重み付け情報に基づきキャッシュメモリを制御する装置とを備えるマイクロコンピュータがある。

尚、本実施の形態１は、一つのキャッシュメモリを複数のスレッドやＣＰＵで共有する場合に適用可能である。図１では、ＣＰＵが１つのいわゆるシングルコアの例を示したが、マルチコアの場合であっても構わない。その場合、各命令流は各コアに割り当てられて実行されることで並列処理となる。そして、領域決定部１２２は、コアにおける周波数の比率に応じて領域を決定することで実現可能となる。そして、一部のコアだけ動作クロック周波数を変更する場合などにも対応できる。

また、実行時間割当部１１２は、特許文献１のスケジューラを用いる必要はなく、各タスクのプロセッサにおける重み付けを定義するものであっても構わない。そして、タスクの追加や削除等によってその重み付けが動的に変化するものであればよい。

以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。

１１０ ＣＰＵ
１１１ メモリアクセス部
１１２ 実行時間割当部
１２０ キャッシュ制御装置
１２１ アドレス分割部
１２２ 領域決定部
１２２１ 加工部
１２２２ 割当制御部
１２２３ 領域割当情報
１２３ ヒットミス判定部
１３０ キャッシュメモリ
２１０ ＣＰＵ
２１１ メモリアクセス部
２１２ スレッドスケジューラ
２２０ キャッシュ制御装置
２２１ アドレス分割部
２２２ 領域決定部
２２２ａ 領域決定部
２２２１ 加工部
２２２２ 割当制御部
２２２３ 領域割当情報
２２３ ヒットミス判定部
２３０ キャッシュメモリ
２３０ａ キャッシュメモリ
２３１ ウェイ選択論理部
５１１ 割当スロット数算出部
５１２ 割当スロット番号検出部
５１３ 引数対応付け部
５２０ 割当スロット番号情報
５３１ 割当スロット数
５３２ Ｉｎｄｅｘテーブル
５４ 引数生成部
５５ オフセット生成部
５５ａ バンク変換部
５６ 加算部
５７ ライトバックインバリデート処理部
３２０ キャッシュ制御装置
３２２ 領域決定部
３３０ キャッシュメモリ
３３１ ウェイ選択論理部
６１ 割当ウェイ番号算出部
６２ ウェイ設定情報
６３ アドレス連接部
６４ ライトバックインバリデート処理部
４１１ ＣＰＵ
４１２ ＣＰＵ
４１ｎ ＣＰＵ
４２０ キャッシュ制御装置
４２１ アドレス分割部
４２２ 領域決定部
４２３ ヒットミス判定部
４３０ キャッシュメモリ
４４０ 処理速度情報
９１ キャッシュ制御装置
９２ キャッシュメモリ
９３ マイクロプロセッサ
９４ メインメモリ
９５ ＭＭＵ
９０１ タスクＩＤ信号線
９０２ メモリアクセス信号線
９０３ データ信号線
９０４ メモリアクセス信号線
９０５ データ信号線
９０６ 領域指定信号線
９１１ タスクＩＤ入力レジスタ
９１２ 領域管理部
９１３ 領域決定部
９１４ アドレス分解部
９１５ キャッシュ内アドレス生成部
９１６ ｈｉｔ／ｍｉｓｓ判定部
９１７ キャッシュディレクトリ
９１８ キャッシング部
９１９ データアクセス部
ｄ１ アクセスアドレス
ｄ２ ＩＤ
ｄ２ａ スレッドＩＤ
ｄ３ 実行時間の割当比率
ｄ３ａ スロット割当情報
ｄ３ｂ スロット割当情報
ｄ３ｃ 処理速度比率
ｄ４ タグ
ｄ５ ライン
ｄ５１ 上位領域
ｄ５２ 下位領域
ｄ６ キャッシュアクセス
ｄ６０ ウェイ選択信号
ｄ６１ ラインアドレス
ｄ６２ インバリデート信号
ｄ７ タグ
ｄ７０ タグ
ｄ７１ タグ
ｄ７２ タグ
ｄ７３ タグ
ｄ８ Ｈｉｔ応答又はＭｉｓｓリフィル
ｄ８１ ウェイ選択信号
ｗ０ ウェイ
ｗ１ ウェイ
ｗ２ ウェイ
ｗ３ ウェイ
ｗ０ａ ウェイ
ｗ１ａ ウェイ
ｗ２ａ ウェイ
ｗ３ａ ウェイ
ｂ０ バンク
ｂ１ バンク
Ｌ０ ライングループ
Ｌ０ａ ライングループ
Ｌ０ｂ ライングループ
Ｌ０ｘ ライングループ
Ｌ０ｙ ライングループ
Ｌ０ｘａ ライングループ
Ｌ０ｘｂ ライングループ
Ｌ０ｙａ ライングループ
Ｌ０ｙｂ ライングループ
Ｌ１ ライングループ
Ｌ１ｂ ライングループ
Ｌ１ｘ ライングループ
Ｌ１ｙ ライングループ
Ｌ２ ライングループ
Ｌ２ｘ ライングループ
Ｌ２ｙ ライングループ
Ｌ３ ライングループ
Ｌ３ｘ ライングループ
Ｌ３ｙ ライングループ

Claims (15)

1. プロセッサにより複数の命令流のそれぞれに割り当てられた単位時間当たりの実行時間の割当比率に基づいて、各命令流に割り当てるキャッシュメモリの領域を決定する領域決定部を備え、
   前記実行時間の割当比率は、前記プロセッサ内の複数のタイムスロットと前記複数の命令流との対応関係に基づく割当情報であり、
   前記領域決定部は、
   前記実行時間の割当情報に含まれるタイムスロットに基づいて、前記命令流ごとに割当スロット数と割当スロット番号とを算出し、
   前記割当スロット数の比率に応じて各命令流に割り当てる前記キャッシュメモリ内のラインを特定し、
   前記割当スロット番号に応じて前記ラインのインデックスを決定するキャッシュ制御装置。
2. 前記領域決定部は、
   前記命令流と前記割当スロット数、割当スロット番号との対応を領域割当情報として記憶領域に格納する
   請求項１に記載のキャッシュ制御装置。
3. 前記領域決定部は、
   前記キャッシュメモリへのアクセス要求に含まれる前記命令流の識別情報と、前記割当スロット数と前記割当スロット番号とに基づいて、アクセス対象の前記キャッシュメモリのラインを決定する
   請求項１に記載のキャッシュ制御装置。
4. 前記領域決定部は、
   前記実行時間の割当比率が変更された場合に、当該変更後の実行時間の割当比率に応じて当該変更にかかる命令流に割り当てる前記キャッシュメモリの領域を更新する
   請求項１に記載のキャッシュ制御装置。
5. 前記領域決定部は、
   前記更新と共に、前記変更により前記実行時間の割当比率が減少した命令流に対して既に割り当てられていた前記キャッシュメモリの領域のうち、当該減少分を無効化する
   請求項４に記載のキャッシュ制御装置。
6. 前記領域決定部は、
   前記実行時間の割当比率のうち最も小さい比率が割り当てられた命令流については、当該割当比率に関わらず、前記キャッシュメモリの領域のうち割り当て可能な最小単位の領域を、少なくとも当該命令流に割り当てるキャッシュメモリの領域として決定する
   請求項１乃至５のいずれか１項に記載のキャッシュ制御装置。
7. 前記領域決定部は、前記命令流に含まれるアドレス情報と前記割当スロット番号とを対応付けるためのテーブル情報を有する
   請求項１に記載のキャッシュ制御装置。
8. 前記テーブル情報は、前記アドレス情報に所定の演算を行った結果を引数とし、当該引数と前記割当スロット番号とを対応づけたものである
   請求項７に記載のキャッシュ制御装置。
9. プロセッサにより複数の命令流のそれぞれに割り当てられた単位時間当たりの実行時間の割当比率を受け付け、
   前記実行時間の割当比率に基づいて、各命令流に割り当てるキャッシュメモリの領域を決定するキャッシュ制御方法であって、
   前記実行時間の割当比率は、前記プロセッサ内の複数のタイムスロットと前記複数の命令流との対応関係に基づく割当情報であり、
   前記実行時間の割当情報に含まれるタイムスロットに基づいて、前記命令流ごとに割当スロット数と割当スロット番号とを算出し、
   前記割当スロット数の比率に応じて各命令流に割り当てる前記キャッシュメモリ内のラインを特定し、
   前記割当スロット番号に応じて前記ラインのインデックスを決定するキャッシュ制御方法。
10. 前記キャッシュメモリへのアクセス要求を受け付け、
    前記アクセス要求に含まれる前記命令流の識別情報と、前記割当スロット数と前記割当スロット番号とに基づいて、アクセス対象の前記キャッシュメモリのラインを決定する
    請求項９に記載のキャッシュ制御方法。
11. 前記実行時間の割当比率が変更された場合に、当該変更後の実行時間の割当比率に応じて当該変更にかかる命令流に割り当てる前記キャッシュメモリの領域を更新する
    請求項９に記載のキャッシュ制御方法。
12. 前記更新と共に、前記変更により前記実行時間の割当比率が減少した命令流に対して既に割り当てられていた前記キャッシュメモリの領域のうち、当該減少分を無効化する
    請求項１１に記載のキャッシュ制御方法。
13. 前記実行時間の割当比率のうち最も小さい比率が割り当てられた命令流については、当該割当比率に関わらず、前記キャッシュメモリの領域のうち割り当て可能な最小単位の領域を、少なくとも当該命令流に割り当てるキャッシュメモリの領域として決定する
    請求項９乃至１２のいずれか１項に記載のキャッシュ制御方法。
14. 前記命令流に含まれるアドレス情報と前記割当スロット番号とを対応付けるためのテーブル情報を記憶装置に格納する
    請求項９に記載のキャッシュ制御方法。
15. 前記テーブル情報は、前記アドレス情報に所定の演算を行った結果を引数とし、当該引数と前記割当スロット番号とを対応づけたものである
    請求項１４に記載のキャッシュ制御方法。

Images