(57)【要約】【課題】  情報処理の内容によってはLRUやLFUアルゴリズムが、適切ではない場合が存在する。そこで、ハードウェアコストが小さく、キャッシュミスの発生を抑制するキャッシュメモリを提供することにある。【解決手段】複数のウェイを持つセットアソシアティブキャッシュメモリであって、  当該複数ウェイから読み出されるアドレス情報の大小関係を比較する比較部を有し、  キャッシュメモリからデータを置換する際に、  当該比較の結果に基づきキャッシュメモリから置換する対象となるデータを決定する  ことを特徴とする。【選択図】  図１３
2015153122.tif 000002
【特許請求の範囲】
【請求項１】
複数のウェイを持つセットアソシアティブキャッシュメモリであって、
当該複数ウェイから読み出されるアドレス情報の大小関係を比較する比較部を有し、
キャッシュメモリからデータを置換する際に、
当該比較の結果に基づきキャッシュメモリから置換する対象となるデータを決定する
ことを特徴とするキャッシュメモリ。
【請求項２】
請求項１記載のキャッシュメモリであって、
タグとタグに対応したデータを保持するウェイを複数有し、
前記アドレス情報は、前記複数ウェイから読み出されるタグであり、
該ウェイは、
アドレスデコーダからのインデックスを受け取り、データをデータ選択部に出力し、
該データ選択部は、キャッシュヒットしたデータに対応したウェイからのデータを選択することを特徴とするキャッシュメモリ。
【請求項３】
請求項２記載のキャッシュメモリであって、
タグ比較部が、
前記複数のウェイのそれぞれからのタグと、アドレスデコーダからのタグとを受け取り、
タグの値が最も大きい領域を置換対象として選択するように、置換するウェイの信号を出力する
ことを特徴とするキャッシュメモリ。
【請求項４】
請求項２記載のキャッシュメモリであって、
前記複数ウェイから読み出されるタグに基づき、キャッシュメモリに格納されているデータの根アドレスからの深さを比較する比較部と、
木構造上の左右位置を比較する左右位置の比較部を有し、
キャッシュメモリからデータを置換する際に、当該深さと左右位置の比較の結果に基づき、キャッシュメモリから置換する対象となるデータに対応したウェイの信号を出力することを特徴とするキャッシュメモリ。
【請求項５】
請求項２記載のキャッシュメモリであって、
当該複数ウェイから読み出されるデータの値と木構造が定義する優先度の計算方法に従い計算されるデータの優先度を比較する優先度比較部を有し、
前記根アドレスからの深さを比較する深さ比較部と、前記優先度比較部の比較結果に基づき、キャッシュメモリから置換する対象となるデータに対応したウェイの信号を出力することを特徴とするキャッシュメモリ。
【請求項６】
請求項１または２記載のキャッシュメモリにデータをプリフェッチするプリフェッチ部を有する情報処理装置であって、
ヒープによりデータを管理するメインメモリと、
該ヒープへのデータ挿入命令を判別する判別部と、
ヒープ末尾のアドレスを記憶する記憶領域とを有し、
前記データ挿入命令と前記ヒープ末尾のアドレスに基づき、ヒープの木構造上において右の葉へのデータ挿入命令を実行した際に、次のデータ挿入時に参照されるデータをキャッシュメモリに、プリフェッチをする信号を出力することを特徴とする情報処理装置。
【請求項７】
請求項１または２記載のキャッシュメモリにデータをプリフェッチするプリフェッチ部を有する情報処理装置であって、
ヒープによりデータを管理するメインメモリと、
ヒープへのデータ処理命令を判別する判別部と、
ヒープ末尾のアドレスを記憶する記憶領域と、
直前のヒープへのデータ処理命令を記憶する記憶領域を有し、
連続する２回のヒープからのデータ削除命令を実行し、かつ、２回目の削除命令実行時に、ヒープ末尾が左の葉である際に、前記ヒープ末尾のアドレスに基づき、次のデータ挿入時に参照されるデータを、キャッシュメモリにプリフェッチをする信号を出力することを特徴とする情報処理装置。
【請求項８】
請求項６または７記載のキャッシュメモリにデータをプリフェッチするプリフェッチ部を有する情報処理装置であって、
外部から設定可能な記憶領域、または、内部から当該記憶領域を設定する設定部と、
カウンタを有し、
当該記憶領域とカウンタに基づき  前記ヒープ末尾のアドレスに基づき、次のデータ挿入時に参照されるデータを、キャッシュメモリにプリフェッチをする信号を出力する回数を削減するプリフェッチ実行間引き部を有する
ことを特徴とする情報処理装置。
【請求項９】
請求項２記載の複数のウェイを持つセットアソシアティブキャッシュメモリであって、
当該キャッシュメモリは外部から設定可能な記憶領域、または内部から当該記憶領域を
設定する設定部を有し、
当該複数ウェイから読み出されるタグから計算可能なキャッシュメモリに格納され
ているデータのアドレス情報と当該記憶領域の値を比較する比較部を有し、
キャッシュメモリからデータを置換する際に、
当該比較の結果に基づきキャッシュメモリから置換する対象となるデータに対応したウェイの信号を出力することを特徴とするキャッシュメモリ。
【請求項１０】
請求項２記載の複数のウェイを持つセットアソシアティブキャッシュメモリであって、
当該キャッシュメモリは外部から設定可能な複数の記憶領域、または内部から当該記憶
領域を設定する設定部を有し、
当該複数ウェイから読み出されるタグから計算可能なキャッシュメモリに格納されているデータのアドレス情報と、複数の基準アドレスと重みづけ情報とに基づいて、置換対象データと基準アドレスとの間の総距離を比較する比較部を有し、
キャッシュメモリからデータを置換する際に、
当該比較の結果に基づきキャッシュメモリから置換する対象となるデータに対応したウェイの信号を出力することを特徴とするキャッシュメモリ。
【請求項１１】
書き込み回数制限の異なる２種のフラッシュメモリからなる記憶装置を有する情報処理装置であって、
当該記憶装置と外部の中央演算処理装置（CPU）との間に、該CPUから当該異なる２種のフラッシュメモリのアドレス情報を参照する参照部を有し、
当該CPUは当該記憶装置のアドレス情報に従いアドレスの割当てを行うことを特徴とする請求項１または２記載のキャッシュメモリを有する情報処理装置。
【請求項１２】
書き込み回数制限の異なる２種のフラッシュメモリからなる記憶装置を有した情報処理装置であって、
外部の中央演算処理装置（CPU）は、当該記憶装置を制御する制御部へ当該異なる２種のフラッシュメモリのいずれに対するアドレスであるのかを表す情報を通知する通知部を有し、
当該記憶装置を制御する制御部は、当該情報に従いアドレスの割当てを行うことを特徴とする請求項１または２記載のキャシュメモリを有する情報処理装置。
【請求項１３】
複数のウェイを持つセットアソシアティブキャッシュメモリのデータ置換方法であって、
当該複数ウェイから読み出されるアドレス情報の大小関係を比較し、
キャッシュメモリからデータを置換する際に、
当該比較の結果に基づき、キャッシュメモリから置換する対象となるデータを決定する
ことを特徴とするキャッシュメモリのデータ置換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリに係り、当該キャッシュメモリ、および当該キャッシュメモリを含む情報処理装置に関する。
【背景技術】
【０００２】
近年、多くの情報処理装置が中央演算処理装置11（CPU）とメインメモリ13の処理速度差を隠蔽するためにCPU11とメインメモリ13の間に、小容量だが高速な記憶装置(キャッシュメモリ12)を配置する構成を採用している（図１）。
【０００３】
CPU11がキャッシュメモリ12に格納されていないデータを参照する場合、メインメモリ13を参照する必要がある。この場合をキャッシュミスと呼ぶ。逆に、キャッシュメモリ上に参照対象であるデータが格納されている場合をキャッシュヒットと呼ぶ。外部記憶装置への参照性能はキャッシュメモリへの参照性能に比較して低いため、情報処理装置の処理性能向上のためには、キャッシュミス率を抑える事が重要となる。
【０００４】
キャッシュメモリはメインメモリ13よりも容量が小さいため、メインメモリ13上の複数のデータがキャッシュメモリ12上の同じ領域にマッピングされる（図２）。そのため、新たなデータをメインメモリ13からキャッシュメモリ12に格納する場合、既にキャッシュメモリ12に格納されているデータを追い出し、新たなデータを格納する必要がある。例えば、図２ではアドレス0000とアドレス0100はキャッシュメモリ12上の同じ領域に割当てられているため、アドレス0000のデータをキャッシュメモリ12に格納している状態で、アドレス0100のデータをキャッシュメモリ12に格納する場合、既にキャッシュメモリ12上にあるアドレス0000のデータを追出し、新たにアドレス0100のデータを格納する。
【０００５】
メインメモリ13上のデータがキャッシュメモリ12上にマッピングされる領域が複数あるキャッシュメモリ12をセットアソシアティブキャッシュメモリと呼ぶ。例えば、図３はマッピング領域が２つ存在する２ウェイセットアソシアティブキャッシュメモリの例図である。Nウェイセットアソシアティブキャッシュメモリでは、新たなデータを格納する際、既にあるN個のデータの中からどのデータを追い出す対象とするか決定する必要がある。追い出し対象を決定する手続きを置換アルゴリズムと呼ぶ。
【０００６】
キャッシュメモリ12から追い出されたデータを次に参照する場合、キャッシュミスが発生する。そのため、キャッシュミスの発生を抑制するには、今後再参照の可能性が高いデータをキャッシュメモリ12に残し、再参照の可能性が低いデータをキャッシュメモリ12からの追出し対象とする事が置換アルゴリズムには求められる。
【０００７】
従来の置換アルゴリズムとして各データの参照頻度履歴を記憶し、参照頻度が最も低いデータを追い出すLFU(Least Frequently Used)アルゴリズムが知られている。LFUは現在の参照頻度が高いデータほど、今後再参照される可能性が高いという方針に基づき、最も参照頻度が低いデータを追出し対象とするアルゴリズムである。また、最近参照されたデータが今後も再参照される可能性が高いという方針に基づき、最も最近に、使用されていないデータを追い出し対象とするLRU(Least Recently used)アルゴリズムが知られている（非特許文献１）。
【０００８】
また、キャッシュミスの発生を抑えるためには、今後必要になるデータを予めキャッシュメモリ12に格納しておくプリフェッチと呼ばれる技術が知られている。例えば、配列全体を走査するような処理において、配列参照の特性を考慮し、現在参照している配列のインデックスの次のインデックスを予め格納するストリームプリフェッチが知られている（特許文献１）。また、画像処理などで見られる特定の間隔毎に離れた情報への参照の特性を考慮し、一定間隔先のインデックス を予め格納するストライドプリフェッチなどが知られている。この他に、キャッシュミスの履歴情報を利用したプリフェッチ方式が知られている(特許文献２)。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許5025849 (任天堂の音声ストームデータプリフェッチ)
【特許文献２】特許4532931 （日立のキャッシュミス頻度測定プリフェッチ）
【非特許文献】
【００１０】
【非特許文献１】JL Hennesy and DA Patterson、 “Computer Architecture: a quantitative approach”、 Morgan Kaufman、 1996.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
従来技術であるLFUアルゴリズムは参照頻度を記憶するために多くの記憶素子を必要とするため、ハードウェアコストが高いという課題がある。
【００１２】
LRUアルゴリズムも同様に、参照順序を記憶するための記憶素子が必要である課題がある。またLRUアルゴリズムは参照順序を更新するための制御装置にも多くの回路が必要となる課題がある。
【００１３】
またLRUアルゴリズムが想定する、最も最近に、使用した情報が今後も再参照される可能性が高いという想定が適切に機能しない情報処理が存在する。データベースの中から最も大きな値など、最優先情報への参照効率を向上するためにヒープと呼ばれるデータ構造が利用される。例えば、ヒープへの新規情報挿入、最優先情報削除および検索処理などのヒープ処理に対して、LRUアルゴリズムは適切に機能せず、キャッシュミスが多発する可能性がある。また、ストームデータ処理では、最も最近に、参照されたデータと、最も最近に、参照されていないデータの両方への参照があるという特性から、LRUアルゴリズムではキャッシュミスが多発する可能性がある。
【００１４】
加えて、ヒープ処理の際に参照されるアドレスは連続したアドレスではなく、また、一定間隔毎に離れたアドレスでもないため、従来のストリームプリフェッチ、ストライドプリフェッチは有効ではない。
【００１５】
本願は、以上の課題を鑑みてなされたものであり、ヒープ処理を想定した場合に、ハードウェアコストが小さく、キャッシュミスの発生を抑制するキャッシュ置換アルゴリズム及び、ヒープ処理の参照アドレス特性を利用したプリフェッチ技術に関する技術を開示する。また、本願をストリームデータ処理及び、フラッシュメモリを利用する情報処理装置に対して拡張することで、ストームデータ処理の性能向上、およびフラッシュメモリの低コスト化、高寿命化に関する技術を開示する。
【課題を解決するための手段】
【００１６】
本発明は、複数のウェイを持つセットアソシアティブキャッシュメモリであって、
当該複数ウェイから読み出されるアドレス情報の大小関係を比較する比較部を有し、
キャッシュメモリからデータを置換する際に、
当該比較の結果に基づきキャッシュメモリから置換する対象となるデータを決定する
ことを特徴とする。
【発明の効果】
【００１７】
本発明によれば、キャッシュメモリのハードウェアコストを抑えたキャッシュ置換アルゴリズムによりキャッシュミスの発生を抑えることが可能となる。
【図面の簡単な説明】
【００１８】
【図１】キャッシュメモリを含む情報処理装置の一例を示す図。
【図２】メインメモリとキャッシュメモリのアドレス関係の一例を示す図。
【図３】メインメモリとセットアソシアティブキャッシュメモリのアドレス関係の一例を示す図。
【図４】ヒープのアドレス割当ての一例を示す図。
【図５】ヒープの一例を示す図。
【図６】ヒープへの新規データを挿入するフローチャートの一例を示す図。
【図７】ヒープへの新規データ挿入の一例を示す図。
【図８】ヒープからの最優先データを削除する処理を示すフローチャート。
【図９】ヒープからの最優先データを削除する一例を示す図。
【図１０】ヒープへのデータ挿入時の参照アドレス順序の一例を示す図。
【図１１】ダイレクトマップキャッシュメモリの構成の一例を示す図。
【図１２】Nウェイセットアソシアティブキャッシュメモリの構成の一例を示す図。
【図１３】実施例１を実現する構成の一例を示す図。
【図１４】実施例１の適用による効果を示す図。
【図１５】ヒープの増加方向の一例を示す図。
【図１６】実施例２を実現する構成の一例を示す図。
【図１７】実施例３を実現する構成の一例を示す図。
【図１８】連続するデータを挿入する時の参照データの一例を示す図。
【図１９】実施例４を実現する構成の一例を示す図。
【図２０】実施例５を実現する構成の一例を示す図。
【図２１】実施例６を実現する構成の一例を示す図。
【図２２】ストームデータ処理におけるウィンドウの例を示す図。
【図２３】ストームデータ処理における差分処理の一例を示す図。
【図２４】リングバッファの一例を示す図。
【図２５】実施例７の効果を示す図。
【図２６】実施例７を実現する構成の一例を示す図。
【図２７】実施例８を実現する構成の一例を示す図。
【図２８】SLC、 MLCを組み合わせるSSDにおけるアドレス割当てのを示す図。
【図２９】実施例９を実現する構成の一例を示す図。
【発明を実施するための形態】
【実施例１】
【００１９】
本願を実施するための具体的形態を図面に基づいて詳細に説明する。
【００２０】
データベースの中から、データベースが定義する優先度に従い、最優先情報を参照する処理を考える。例えば、数値データに対して、値が大きいほど優先度が高いと定義するデータベースから最優先データを参照することを考える。大量データの中から最優先データを検索する処理は、単純に処理する場合すべてのデータを検索する必要があるため、長い処理時間を必要とする。そこで、予め優先度に従いデータを適切にソーティングしておくことが考えられる。
【００２１】
しかし、最優先データ参照を効率的に処理するためには、最優先データのみがソーティングされていれば十分であり、データベース内のデータセット全てがソーティングしてある必要はない。このような目的に適したデータ構造としてヒープが知られている。ヒープとは図４に示すようにノードがひとつのデータに対応する木構造型のデータ構造であり、木の根に近いノードから順にアドレスが割当てられる。図４では根にアドレス１、根の２つの子ノードに左から順にアドレス２、アドレス３を割当て、以下同様に左の子から順にアドレスを割り当てている。このアドレス規則により、ヒープはポインタによる参照が不要であり、配列により実装が可能なデータ構造である。
【００２２】
ここで、本実施例では以降の説明において、数値データに対して値の大きい方を優先度が高いとし、親ノードのデータは子ノードのデータよりも優先度が高いとして説明をし、ヒープを２分木型のバイナリヒープとして説明する。しかし、本案はデータの優先度が定義されていれば、数値データに限定する必要は無く、また、３分木型など一般的ヒープに対して適用可能な技術である。また、説明容易化のためにヒープの開始アドレスを１から開始しているが、0からなど他の値から開始する場合にも同様に適用可能である。
【００２３】
ヒープではすべての親と子の間で順序関係が一意に定められる。そのため、根ノードには最も優先度が高いデータが格納される。例えば、図５は適切なヒープ構造である。図５に示す通りすべての親子間で親のほうが、優先度が高い条件を満たしている(注意：図４とは異なり、図５中の各ノードの値はデータの値である)。ヒープに新たにデータを追加する場合、また、ヒープからデータを削除する場合には、ヒープのすべての親子間で優先度条件を満足する必要がある。
【００２４】
ヒープに新たなデータを追加する場合の処理のフローチャートを図６に示す。ヒープに新たなデータを挿入する場合、まず始めにヒープの末尾の次の領域に新たなデータを挿入する(601)。ここでヒープの末尾とは、現在データが格納されているノードの中で最もアドレスが大きいノードである。例えば、図５のヒープに新たに値が70のデータを追加する場合処理を図７に示す。図７のように、図４のアドレス８の領域にデータが挿入される。次に、挿入するデータとその親の優先度を比較する(602)。優先度の比較結果が、ヒープが定義する優先度条件を満たさない場合(603のNO)、挿入するデータとその親のデータを交換し(604)、親子間の優先度関係を修正する。親とデータを交換した場合、再度、交換後の親と優先度を比較する。以下、交換が発生しなくなるか、または、挿入するデータが根ノードに達するまで比較と交換を繰返すことで、ヒープの優先度条件を満足する(603の YES)までヒープを再構築する。図７の場合、２回の交換により、ヒープの優先度条件を満たす構造が再構築される。
【００２５】
次に、ヒープから最優先データを削除する場合の処理のフローチャートを図８に示す。ヒープから最優先データを削除する場合、まず始めに現在のヒープの根ノードを削除し(801)、根ノードの位置に、ヒープ末尾のデータを格納する(802)。次に、移動後のヒープ末尾の左右両方の子の間の優先度を比較する(803)。比較の結果、ヒープの優先度条件を満足するか、比較対象の左右の子が存在しない場合(804のYES)にはここで終了である。また、比較の結果、ヒープの優先度条件を満足しない場合(804のNO)、左右の子の優先度が高い方のデータとヒープ末尾データを交換し(805)、再び交換後の左右の子の優先度比較と交換を繰返す（図９）。
【００２６】
以上、ヒープへの新規データ挿入、最優先データの削除のヒープ処理から、ヒープ処理では、根ノードと葉ノードを結ぶ特定の経路上のノードが参照されることが分かる。ここで、ヒープの構造上、根から葉に向かって順次分岐を繰返すため、根からの深さが浅いノードの方が根からの深さが深い（葉に近い）ノードよりも参照の確率が高くなる。ここで、あるノードの根ノードからの深さとは、木構造において、根ノードから当該ノードへの最短経路長と定義する。
【００２７】
このことから、ヒープ処理においては、根ノードからの深さが浅いほど、再参照される可能性が高いと考えられ、根ノードからの深さが浅いデータを優先的にキャッシュメモリに残し、根ノードからの深さが深いノードを優先して追い出す事がキャッシュメモリの置換アルゴリズムにとって適切であると考えられる。
【００２８】
しかし、従来の置換アルゴリズムであるLRUアルゴリズムを使用すると、必ずしも根ノードからの深さが浅いデータが優先的にキャッシュメモリに残されない。例えば、図１０のようにアドレス11の領域にデータを挿入し、続いて、アドレス12の領域にデータを挿入する場合を考える。図１０中のノードの右肩の数値は参照順序を表している。例えば、アドレス11への挿入処理で、アドレス５、アドレス２、アドレス１のデータが順に参照される。続いて、アドレス12への挿入処理で、アドレス6、アドレス3、アドレス1のデータが順に参照される。LRUアルゴリズムは、最も最近に、参照されていないデータを追出し対象とする。よって、ノードの右肩の数値が小さいデータから順に追出される。よって、LRUアルゴリズムに従う場合、図１０に示すように、アドレス２とアドレス６のデータではアドレス２のデータのほうが根ノードからの深さが浅いが、LRUアルゴリズムに従う場合にはアドレス２のデータの方がアドレス６のデータよりも優先的に追出される。
【００２９】
ここで、ヒープのアドレス割当て方法から、根ノードからの深さが浅いデータは、アドレスが小さいノードである事に着目すると、置換対象となるデータセットの各アドレスを比較し、アドレスが小さい方を優先的にキャッシュに残し、アドレスが大きい方のデータをキャッシュからの追出し対象データとすれば、根ノードにからの深さが浅いデータを優先的にキャッシュに残す置換アルゴリズムを実現することが可能である。
【００３０】
ここで、本実施例では説明のため、根ノードから昇順にアドレスを割当てる場合を考えるが、根ノードから降順にアドレスを割当てる場合でも、アドレスの大小比較結果を反対考えることで本案を適用可能であることは明らかである。
【００３１】
本案の説明のため、一般的なキャッシュメモリの構成を図１１に示す。ここで、説明を容易にするため図ではメインメモリのアドレスをインデックスとタグに分割するが、キャッシュのラインサイズが複数ワード、バイトである場合にはワード、バイト選択のビットを含むようにアドレスを分割する。
【００３２】
キャッシュメモリは外部記憶装置よりも容量が小さいため、外部記憶装置上の複数の領域がキャッシュメモリの同一の領域に割当てられる。例えば、図２に外部記憶装置に16のデータ格納領域を持ち、キャッシュメモリに４つのデータ格納領域を持つ場合を示す。この場合、図のように4つの外部記憶装置上の領域がキャッシュメモリ上の１つの領域に重複してマッピングされる。このようなキャッシュメモリをダイレクトマップキャッシュメモリと呼ぶ。また、キャッシュメモリ上のアドレスをインデックス（INDEX）と呼ぶ。キャッシュメモリのインデックス数をNINDEXとし、外部記憶装置のアドレスをADDRESSとする場合、外部記憶装置上のアドレス（ADDRESS）のデータが格納されるキャッシュのインデックスはADDRESSとNINDEXの剰余演算から計算される。つまり、INDEX=ADDRESS mod NINDEXとなる。ここでA mod BはAをBで割った時のあまりである。図２の例では、アドレスADDRESSの下位2ビットがキャッシュメモリ上のインデックスに一致する。ここで、アドレスADDRESSの内、インデックスに使用する下位2ビットを除く上位2ビットをタグと呼ぶ。キャッシュ上のデータを参照する場合、アドレスADDRESSの下位2ビットによりキャッシュ上のインデックスを計算し、当該キャッシュインデックスのデータを参照する。この時、キャッシュメモリに割当てられる重複した複数の領域の内、キャッシュから読み出されたデータが所望の領域のデータであるかどうかを、タグを比較することで判定する。その為、図１１に示すように、TAGがひとつからなるワンウエイ20のキャッシュメモリにはデータだけでなくタグを格納する記憶領域と、タグの値を比較するハードウェアが含まれる。タグの比較結果が一致する場合をキャッシュヒット、一致しない場合をキャッシュミスと呼び、タグ比較器1104はキャッシュミス、キャッシュヒットを表す制御信号（HIT_OR_MISS）を生成する。キャッシュヒットの場合は、アドレスデコーダ（ADRESS_DECORDER）1101からのINDEXに対応したDATAをウェイ20から読みだしたデータ（DATA）を参照データとし、キャッシュミスの場合はキャッシュから読みだしたデータは使用せずに、外部記憶装置から該当データを参照する。
【００３３】
Nウェイセットアソシアティブキャッシュメモリの場合、N個の各ウェイのタグメモリを比較し、キャッシュヒットかキャッシュミスであるかを判定する（図１２）。キャッシュヒットの場合はN個のウェイのうち、どのウェイのデータがキャッシュヒットしたのかを示すウェイ選択信号（WAY_SELECT）に従い、所望のデータを読み出す。キャッシュミスの場合、所望のデータをメインメモリから読出し、N領域の中から適当な追出し対象となる領域を選択し、所望のデータを新たに格納する。従来技術では、例えばこの追出し対象データを決定する際にLRUアルゴリズムが広く用いられている。
【００３４】
本実施例は根からの深さが浅いノードのデータを優先して残す置換アルゴリズムを開示する。本実施例を実現するシステム構成を図１３に示す。Nウェイセットアソシアティブキャッシュメモリでは各ウェイの、合計N個の領域が置換候補として存在する。本実施例では、タグ選択器（TAG_COMPARAROR）1104が複数のWAY（20-1から20-N）からのタグの値を入力するとともに、ADDRESS_DECODER1101からのタグの値を入力し、キャッシュヒットしているかをHIT_OR_MISS信号として出力し、ヒットしたタグに対応するウェイをWAY_SELECT信号として、データ選択器（DATA SELECTOR）1105に出力する。データ選択器は、複数のウェイからのデータから、キャッシュヒットしたタグに対応するウェイのデータを出力する。さらに、TAG_COMPARAROR1104は当該N個の領域のタグの値を比較する。次に、タグの値が最も大きい領域を置換対象として選択する。タグの値が大きい領域を選択することで、根からの深さが最も深いノードのデータが置換対象として選択される。当該機能を実現するために、本実施例のシステムは図１３のように、タグ比較器（TAG_COMPARATOR）1104からウェイ選択信号に加え、タグの値が最も大きなタグを備えたウェイにおけるデータを置換するために、どのウェイのデータを置換対象とするかを表す信号（REPLACE_WAY）を生成し出力する。ここで、本実施例の示すタグ比較器は従来のキャッシュメモリでもキャッシュミス/ヒット判定に使用されていたタグ比較器の機能を含み、加えて、新たに各ウェイから読み出されるタグの値同士の大小関係を比較する機能、また、比較結果に基づき最もタグの値が大きいタグがどのウェイであるかを決定する機能を有する。
【００３５】
また、本実施例ではアドレスの比較をタグの値を用いて行う例を示すが、参照先アドレスから求まるインデックスと併せてアドレスを生成し、実際のアドレス同士を比較することも可能であり、本願の方式が適用可能であることは明らかである。
【００３６】
以上より、本実施例に従えば、アドレスの比較によるキャッシュメモリの制御を行うことで、図１４のようにデータのアドレスに応じてキャッシュミス率が変化するキャッシュメモリを実現することが可能となる。よって、本実施例を適用することで、ヒープの根からの深さが浅いデータを優先的にキャッシュメモリに格納することが可能となり、ヒープなどの木構造型のデータ構造に適したキャッシュ追い出しアルゴリズムを実現することが可能となる。その際、図１３から分かる通り、従来のLFU、 LRUのように追加の記憶素子を必要とせず、キャッシュメモリに元来構成されているタグを利用して実現可能であり、ハードウェアコストの面でも優れた方式を実現可能となる。
【実施例２】
【００３７】
ヒープに次々にデータを挿入する場合を考える。この時、図１５のヒープ増加方向から分かる通り、ヒープへの新規データが連続して続く場合、次のデータ挿入時に参照されるノードは木構造上の左のノードから右のノードへと推移する。逆に、連続してヒープからデータを削除する場合、次のデータ挿入時に参照されるノードは木構造上の右のノードから左のノードへと推移する。
【００３８】
よって、ヒープへのデータ挿入が削除よりも多く、ヒープのデータサイズが増大傾向にある場合、次の挿入処理時には右のノードのほうが左のノードよりも参照される可能性が高く、逆に、ヒープからのデータ削除がデータ挿入よりも多く、ヒープのデータサイズが減少傾向にある場合、次の挿入処理時には左のノードのほうが右のノードよりも参照される可能性が高いと考えられる。
【００３９】
以上を考慮し、本実施例では実施例１が開示する根ノードからの深さによる置換対象決定に加え、根ノードからの深さが同一の置換対象候補が複数存在する場合に、さらに、ヒープのデータサイズの増減傾向と置換対象候補のノードの木構造上の左右位置に基づき、置換対象を決定する置換アルゴリズムを、第２の実施形態として開示する。
【００４０】
本実施例を実現するシステム構成図をそれぞれ図１６に示す。Nウェイセットアソシアティブキャッシュメモリでは各ウェイの、合計N個の領域が置換候補として存在する。本実施例では、深さ比較器(DEPTH_COMPARATOR)1106が、複数のウェイ１−Nからのタグ信号を入力し、入力したタグの値から、根からの深さ比較することにより置換対象を決定する判定を行う。根からの深さが最長となるデータが唯一に決定される場合、当該の唯一に決定されるデータを置換対象とし、根からの深さが最長になるタグを備えるウェイを示す信号をREPLACE_WAY信号として出力する（図示せず）。根からの深さ比較の結果、根からの深さが最長となるデータが（同率で）複数存在する場合、DEPTH_COMPARATOR1106から複数のタグの信号をLEFT_RIGHT_COMPARATOR 1107に出力する。LEFT_RIGHT_COMPARATOR 1107は、続けて、左右位置での比較を行う。予め設定される左右位置のどちらを優先するかに従い、左右位置のいずれか一方を置換対象として決定する。
【００４１】
ここで、左右位置のどちらを優先するかどうかは、左右位置比較器1107（LEFT_RIGHT_COMPARATOR）に入力される左右優先選択信号（LR＿PRIORITY）により決定される。左右優先選択信号はシステム外部から設定する構成と、システム内部で生成する構成の２つがある。外部から設定する構成では、システム内部に外部から設定可能な記憶領域を構成することで実現する。また、システム内部で生成する構成では、ヒープに対する単位時間あたりの挿入処理回数、削除処理回数を記録し、当該記録値にもとづき動的に生成する構成などがある。
【００４２】
左右優先選択信号が左を優先する信号である場合には、左右位置比較器1107は、複数存在する根からの深さが最長のデータに対応するタグの中からタグの値が最も小さい領域を置換対象として選択し、タグの値が最も小さいタグに対応したウェイのデータを置換対象とする信号（REPLACE_WAY）を生成し出力する。左右優先選択信号が右を優先する信号である場合には、複数存在する根からの深さが最長のデータに対応するタグの中からタグの値が最も大きい領域を置換対象として選択し、タグの値が最も大きいタグに対応したウェイのデータを置換対象とする信号（REPLACE_WAY）を生成し出力する。
【００４３】
また、実施例１同様に、図１６はアドレスの比較をタグの値を用いて行う例を示すが、参照先アドレスから求まるインデックスと併せてアドレスを生成し、実際のアドレス同士を比較することも可能であり、本願の方式が適用可能であることは明らかである。
【００４４】
以上より、本実施例２に従うと、根からの深さが最長となる置換対象データが複数存在する場合に、ヒープのデータサイズの増減方向と木構造上の左右位置に従い、どのデータを優先的にキャッシュメモリに残し、どのデータをキャッシュメモリから追い出すのかを決定することが可能となる。
【実施例３】
【００４５】
図９のヒープからの削除処理から分かる通り、ヒープからの削除処理においては、左右の子のうち、優先度が高い方と順次比較、交換を繰り返す。よって、優先度が高いデータの方が、削除処理において参照される可能性が高いと考えられる。
【００４６】
以上を考慮し、本実施例では本案の第３の実施形態として、実施例１で示した根からの深さに基づく置換対象決定に加え、当該データのヒープ上の優先度に基づき置換対象を決定する置換アルゴリズムを第３の実施形態として開示する。
【００４７】
本実施例を実現するシステム構成図をそれぞれ図１７に示す。Nウェイセットアソシアティブキャッシュメモリでは各ウェイの、合計N個の領域が置換候補として存在する。本実施例では、深さ比較器(DEPTH_COMPARATOR)1106が、複数のウエイ１−Nからのタグ信号を入力し、入力したタグの値から、根からの深さ比較することにより置換対象を決定する判定を行う。根からの深さが最長となるデータが唯一に決定される場合、当該の唯一に決定されるデータを置換対象として決定し、根からの深さが最長になるタグを備えるウェイを示す信号をREPLACE_WAY信号として出力する（図示せず）。根からの深さ比較の結果、根からの深さが最長となるデータに対応するタグが（同率で）複数存在する場合、続けて、ヒープが定義する優先度に従い優先度比較器1109（PRIORITY_COMPARATOR）にて比較を行う。優先度比較器1109は、複数ウェイからのデータを入力して、優先度の比較をする。その結果、複数存在する根からの深さが最長のデータの中で、ヒープが定義する優先度が最も高いデータを置換対象として選択することができる。
【００４８】
ここで、ヒープが定義する優先度とは、ヒープの親子間の優先度を定義するために定義される優先度である。例えば、売上高が大きいほうが優先度が高いとして、売上高に従い順序付けられたヒープでは売上高が優先度となる。比較の結果、優先度が最も低いデータを置換対象として決定し、置換対象となるデータが格納されているウェイを表す信号（REPLACE_WAY）を優先度比較器1109が出力する。
【００４９】
優先度は読み出されるデータに基づき決定される。この際、単純に読み出されたデータの値がそのまま優先度になる場合もあるが、読み出されたデータに基づき優先度を計算する場合もある。図１７では優先度を計算する場合を例示しており、優先度を計算するための優先度計算機1108（PRIORITY_CALCULATOR）を含み、優先度計算機1108から置換対象となるデータが格納されているウェイを表す信号（REPLACE_WAY）を出力する構成を示しているが、値がそのまま優先度となる場合には優先度計算機1108を省略しても構わない。優先度比較器1109や優先度計算機1108には、図示していないが、ヒープによって定義するデータを外部から入力するようにして、入力したデータによって、優先度を決めるための計算式や比較式を外部からプログラム可能とすることもできる。
【００５０】
また、実施例１同様に、図１７ではアドレスの比較をタグの値を用いて行う例を示すが、参照先アドレスから求まるインデックスと併せてアドレスを生成し、実際のアドレス同士を比較することも可能であり、本願の方式が適用可能であることは明らかである。
【００５１】
以上より、本実施例３に従うと、根からの深さが最長となる置換対象データが複数存在する場合に、ヒープが定義する優先度に従い、どのデータを優先的にキャッシュメモリに残し、どのデータをキャッシュメモリから追い出すのかを決定することが可能となる。
【実施例４】
【００５２】
本実施例では、ヒープ処理に対するキャッシュミスの発生を抑制するため、ヒープ処理の際に参照されるアドレスの特性に基づくプリフェッチ部を開示する。
【００５３】
ヒープへのデータ挿入処理において、例えば、図１８におけるアドレス１０の位置にデータを格納すると、挿入処理によりアドレス５、２、１のデータが参照され、その際キャッシュメモリにデータが格納される。この状態から、連続して次のデータ挿入処理を行う場合を考える。この時、アドレス１１にデータが挿入され、挿入処理によりアドレス５、２、１が参照される。一つ前の挿入処理により、当該アドレスの５、２、１のデータはキャッシュメモリに格納されているため、この場合、理想的にはキャッシュミスは発生しない。
【００５４】
次に、さらに連続してデータ挿入する場合を考える。この場合、アドレス１２にデータが挿入され、挿入処理によりアドレス６、３、１が参照される。この時、先の例とは異なり、参照されるデータのアドレスは前回の挿入処理の際に参照されるアドレスとは異なるため、キャッシュミスが発生する可能性がある。
【００５５】
以上より、ヒープへの挿入処理において挿入がヒープの木構造上の右の葉への挿入処理の場合に、次の挿入処理でキャッシュミスが発生する可能性が高いと考えられる。そこで、本実施例では、ヒープへのデータ挿入がヒープの木構造上の右の葉への挿入の場合に、次の挿入処理で参照されるデータをプリフェッチする。
【００５６】
ここで、ヒープへのデータ挿入の際に参照されるデータのアドレスは、挿入されるアドレスから計算することが可能である。例えば、図１８の場合、アドレス１１に挿入する場合にはアドレス５、２、１が参照されることがわかる。根のアドレスを１にしない場合など、アドレスのマッピングにより計算方法は様々考えられるが、一般的にヒープはアドレスのマッピングに従って挿入処理に際して参照されるアドレスが計算可能な特徴を持つ。
【００５７】
以上を鑑みて、本案が開示するヒープ処理の参照アドレスの特徴に基づくプリフェッチ方式を実現するシステム構成を図１９に示す。本実施例では右の葉へのデータ挿入処理の場合にプリフェッチを行うためのトリガ信号を上げる。そのために、プリフェッチトリガを上げるかどうかを判定する判定器2202（PREFETCH_JUDGE）には、処理が挿入処理であるかどうかを判定するための処理の種類を表す信号（INSTRUCTION_TYPE）と、挿入先のアドレスが右の葉であるかを判定するためにヒープ末尾のアドレス2201（HEAP_TAIL_ADDRESS）を入力する。現在のヒープ末尾アドレスから、次の挿入先アドレスは計算可能である。また、現在のヒープ末尾アドレスではなく、次の挿入先アドレスを記憶しておき、それを直接入力する構成でも同様の機能を実施可能である。挿入先が右の葉であるか否かの判定は、例えば図４のように根のアドレスを１とする場合には、挿入先のアドレスが２の倍数ではない場合であるとして判定可能である。
【００５８】
右の葉への挿入である場合には、判定器2202がプリフェッチトリガ信号（PREFETCH_TRIGGER）をプリフェッチ実行機2203へ出力し、プリフェッチトリガを受け取ると、プリフェッチ実行機2203（PREFETCHER）は、現在のヒープ末尾アドレスに従い次の挿入処理時に参照されるデータのアドレスを計算し、当該アドレスと当該データを読み出すための制御信号MEM_CTRLをメモリ制御回路(図示せず)に送信する。ここで、プリフェッチ実行機2203に入力するヒープ末尾アドレスは、プリフェッチ判定器2202と同様に、挿入先のアドレスを入力する構成でも同様の機能を実施可能である。
【００５９】
以上より、本実施例４に従うと、ヒープの挿入処理の参照アドレスの特性を利用し、挿入処理時のキャッシュミス発生を抑制するプリフェッチを実行することが可能となる。
【実施例５】
【００６０】
本実施例では、実施例４と同様にヒープ処理に対するキャッシュミスの発生を抑制するため、ヒープ処理の際に参照されるアドレスの特性に基づくプリフェッチ部を開示する。
【００６１】
ヒープへのデータ挿入処理において、例えば図１８のようにアドレス１１の位置にデータを格納すると、挿入処理によりアドレス５、２、１のデータが参照され、その際キャッシュメモリにデータが格納される。この状態からヒープからのデータ削除処理が行われ、続いて挿入処理が行われる場合、挿入先アドレスは前回の挿入処理にて挿入したアドレス１１と同一の為、挿入処理で参照されるアドレスはキャッシュに格納されている可能性が高い。
【００６２】
また、アドレス１１に挿入後、連続する２回の削除処理に続いて、挿入処理を行う場合、挿入先アドレスはアドレス１０となる。この際、挿入処理において参照されるアドレスはアドレス５、２、１であり、前回のアドレス１１への挿入処理時に参照されるアドレスと同一である。よって、この場合も挿入処理で参照されるアドレスはキャッシュに格納されている可能性が高い。
【００６３】
しかし、図１８のように、アドレス１２に挿入後、連続する２回の削除処理の後に挿入処理を行う場合には、前回のアドレス１２への挿入処理時にはアドレス６、３、１が参照されるが、次の挿入処理ではアドレス１１への挿入となり、挿入処理ではアドレス５、２、１が参照される。その為、前回の挿入処理と次の挿入処理で参照されるアドレスが異なることになり、キャッシュミスが発生する可能性が高い。
【００６４】
以上より、ヒープへの挿入処理において、その直前に連続した削除処理を実施し、かつ、２回目の削除処理時にヒープ末尾がヒープの木構造上の左の葉の場合、次の挿入処理においてキャッシュミスが発生する可能性が高いと考えられる。そこで、本実施例では、ヒープへの連続した削除処理を実施し、かつ、２回目の削除処理時にヒープ末尾が木構造上の左の葉である場合に、次の挿入処理で参照されるデータをプリフェッチする。プリフェッチ対象となるデータのアドレスに関しては実施例４と同様にヒープ末尾アドレス、または、次の挿入先アドレスに基づき求める。また、プリフェッチの実行に関しても実施例４と同様にプリフェッチ実行トリガを起点に同様の構成により実行する。
【００６５】
本案が開示するヒープ処理の参照アドレスの特徴に基づくプリフェッチ方式を実現するシステム構成を図２０に示す。プリフェッチ実行トリガを上げるか否かを判定するプリフェッチ実行判定器（PREFETCH_JUDGE）2202は、 処理の種類を表す信号（INSTRUCTION_TYPE）に基づいて、処理が削除処理であるかどうかを判定する。削除処理でない場合、プリフェッチトリガはあげず、また、直前の処理が削除処理であるかどうかを表す記憶領域（PRE_INSTRUCTION）に処理が削除処理ではない事を意味する値を書き込み終了する。処理が削除処理である場合、続いて直前に削除処理を実施しているか否かを判定する。この目的の為に、直前の処理が削除であるか否かを表す記憶領域（PRE_INSTRUCTION）を、本実施例のシステムは有する。直前に削除処理を実施していない場合、PRE_INSTRUCTIONに処理が、削除処理である事を書き込んで、書き込み処理を終了する。直前に削除処理を実施している場合、PRE_INSTRUCTIONに処理が、削除処理であることを書込み、続いて、受け取った ヒープ末尾のアドレス2201（HEAP_TAIL_ADDRESS）に基づいて、現在のヒープの末尾が左の葉であるか否かを判定する。現在のヒープの末尾が左の葉でない場合、プリフェッチ実行のトリガは上げずに処理を終了する。現在のヒープの末尾が左の葉である場合、プリフェッチ実行のトリガをプリフェッチ実行機2203へ上げ。プリフェッチ実行機2203（PREFETCHER）は、現在のヒープ末尾アドレスに従い、次の挿入処理時に参照されるデータのアドレスを計算し、当該アドレスと当該データを読み出すための制御信号MEM_CTRLをメモリ制御回路(図示せず)に送信する。
【００６６】
以上より、本実施例５に従うと、ヒープの挿入処理の参照アドレスの特性を利用し、挿入処理時のキャッシュミス発生を抑制するプリフェッチを実行することが可能となる。
【実施例６】
【００６７】
本実施例では実施例４、５を拡張するプリフェッチ部を、以下に説明する。
実施例４、５に従うと高頻度でプリフェッチ処理が実行される可能性がある。しかし、プリフェッチを高頻度で実行しすぎると、その間プリフェッチ実行の為にハードウェア資源を使用してしまう。そのため、本来処理するべき処理が停滞する、または、プリフェッチ中に次のプリフェッチ実行が要求されても、それが実行できない、などの状況が発生する可能性がある。以上を鑑みて、本実施例は実施例４、５のプリフェッチ実行の一部を実行せず、実行を間引く方法を開示する。
【００６８】
プリフェッチ実行を間引くための方法として図２1に示すように、カウンタを使用する方法を示す。カウンタを含むプリフェッチ実行間引き機2601（PREFETCH_INTERLEAVER）を、プリフェッチ実行判定器2202とプリフェッチ実行機2203の間に配置し、プリフェッチ実行判定器2202が出力するプリフェッチ実行トリガ信号をカウンタの値に基づきマスクしてプリフェッチ実行機に入力する。
【００６９】
例えば、一定時間毎にカウントアップするカウンタを使用し、カウンタの値が外部から設定可能な記憶素子（REG）の値と一致した際にだけプリフェッチ実行トリガを通し、他の場合にはプリフェッチ実行トリガ信号を遮断すれば、時間に基づき一定間隔でプリフェチの実行を間引くことが可能となる。この場合にはカウンタにはクロック信号等の時刻情報を入力する。また、外部から設定可能な記憶素子（REG）の値と一致するという条件ではなく、カウンタの値をREGで剰余演算した際の結果が０になる、などの演算を含む条件を使用することも可能である。
【００７０】
また、一定時刻毎にカウントアップするカウンタではなく、キャッシュミス発生などのイベント発生時に、カウントアップするカウンタを使用することで、一定時刻毎ではなく、一定のイベント回数毎にプリフェチ実行を間引くことが可能である。この場合、カウンタにはクロック信号だけでなく、イベント発生を示す信号を入力する構成となる。
【実施例７】
【００７１】
ストリームデータ処理では、時々刻々と流れこむ時系列データに対して適時処理を行う。多くのストリームデータ処理では、絶え間なく流入し続けるストリームデータのうち、時刻順序上の一定の区間（ウィンドウ：WINDOW）で区切られた区間のデータを対象にデータを処理する（図２２）。この時、差分処理と呼ばれる処理方式が適用される。差分処理とは、それまでの処理結果（RESULT）を記憶しておき、新しくウィンドウに入力されるデータ（NEW_DATA）が入力される度に、処理結果を更新する処理方式である。この際、時刻順序上、最も古く、ウィンドウから追い出されるデータ（OLDEST_DATA）も併せて利用した更新される場合がある。例えば、一定時刻前までのデータの和を演算する場合、図２３のように、新しいデータ（NEW_DATA）を演算処理結果（RESULT）に足し（ADD）2801、最も古いデータ（OLDEST_DATA）をデータベース2804から読み出して演算結果2802から引く（SUB）2804、という処理がデータの入力毎に繰り返される。
【００７２】
そのため、ストリームデータ処理では最新のデータをデータベース2804に格納し、データベース2804から最古のデータを読み出すという処理が多くの場合に必要となる。また、一般的なストリームデータ処理における差分処理の性質として、ウィンドウ内の最新のデータと最古のデータの両方を使用するという性質がある。
【００７３】
このようなウィンドウへの最新データの挿入と最古データの参照を実現するためのデータ構造としてキューが考えられる。キューは、キューの末尾から順次データを入力し（PUSH）、キューの先頭から順次データを取り出す（POP）という操作を行うのに適したデータ構造である。
【００７４】
キューを配列により実装する場合、配列の末尾または先頭に必ず最も古いデータが格納される。よって、実施例１で開示するアドレスの大小比較によるキャッシュ置換アルゴリズムを用いれば、最も古いデータを常にキャッシュに格納しておくことが可能である。
【００７５】
しかし、配列によりキューを実現する場合にはデータの挿入や削除時に配列の要素間でデータのコピーが発生するため性能上課題が残る。また単調に使用アドレスが増加してしまう点も課題である。そのため多くの場合、 リングバッファを用いてキューを実装する。リングバッファとはリング上のバッファである。図２４のように配列を循環するリングと捉え、キューの末尾（TAIL）と先頭（HEAD）を表すポインタを利用してキューを実現する。データの挿入や、削除時にTAIL、 HEADを動かすことでキューの指定範囲を変更する。
【００７６】
実施例１の構成によれば、アドレスの大小比較により置換対象を決定することで、最大アドレス、または最小アドレスのいずれかを中心アドレスとし、中心アドレスに近いアドレスのデータほどキャッシュメモリに格納されやすく、中心アドレスから遠いアドレスほどキャッシュメモリに格納されにくい、というキャッシュメモリの制御が可能である。  
しかし、リングバッファを用いて実装されるキューにおいて、参照されるキューのHEADとTAILがキューへのデータ操作従って変化する。そのため、実施例１ではストリームデータ処理において、参照されるウィンドウの最古データを優先的にキャッシュメモリに残すことができない。
【００７７】
そこで、本実施例では実施例１の拡張として、アドレスの大小比較ではなく、外部から、または、内部で生成される基準アドレス（BASE_ADDRESS）との比較結果に基づきキャッシュから追い出すデータを決定する方法を開示する。比較対象とする基準アドレスを可変にすることで、図２５のように、優先的にキャッシュメモリに格納するアドレスを可変にすることが可能となる。例えば、リングバッファの先頭を表すHEADのアドレスを基準アドレスとし、HEADからのアドレスの距離に応じてキャッシュメモリに残すデータを決定すれば、 HEADのアドレスが可変であった場合にもHEADに近いアドレスのデータを優先的に残すことが可能となる。この場合には、HEADアドレスの更新に併せてBASE_ADDRESSも更新する。
【００７８】
本実施例を実施するためのシステム構成を図２６に示す。実施例１を実現するためのシステム構成である図１３に加え、新たに、 基準アドレス（BASE_ADDRESS）と、アドレス比較器(ADDRESS_COMPARATOR)1110が、追加される。BASE_ADDRESSはキューの先頭のアドレスなどの比較基準となるアドレスである。
本実施例が開示する方法では、まずADDRESS_COMPARATOR1101は、基準アドレスと、複数ウェイからの複数のタグとADDRESS_DECODER1101のインデックスとを入力することで、キャッシュメモリに格納されている置換候補のデータのアドレスと基準アドレスとを、比較し、基準アドレスからの距離を計算する。図２６では基準アドレスと直接比較するため、参照アドレスのインデックスを各キャッシュメモリのタグ情報と組み合わせることでアドレス比較を実施する例を示している。しかし、基準アドレスのインデックスを除き、基準アドレスのタグを各キャッシュメモリのタグと比較する場合も同様の機能を実現可能である。
【００７９】
次に、各キャッシュメモリに格納されているデータのアドレスと基準アドレスとの距離のうち、最も距離が大きいデータをキャッシュからの置換対象データとして選択するように、置換対象データを備えるタグに対応したウェイを示す信号（REPLACE_WAY）を生成し出力する。
【００８０】
ここで、基準アドレスからの距離を考える場合、リングバッファではリングを循環するため距離が負になる場合がある。この場合はリングが循環していることを踏まえ、距離を補正する。距離の計算には当該の距離が負になった場合の補正計算を含む。しかし、アドレスの距離の比較結果の絶対値を距離として定義すれば、本実施例は基準アドレスを中心に、アドレスが基準アドレスに近いほどキャッシュメモリに格納されやすく、基準アドレスから離れるほどキャッシュメモリから追い出されやすい、というキャッシュメモリ制御を実現することができる。
【００８１】
また、本実施例では基準アドレスからの距離が大きいデータをキャッシュメモリから追い出す場合を例示したが、同様に基準アドレスからの距離が小さいデータをキャッシュ目オリから追い出す場合も、アドレス比較器での比較方向を逆にすることで可能であることは明らかである。
【００８２】
以上、本実施例によれば、可変な基準アドレスとの距離に応じてキャッシュメモリに残すデータとキャッシュメモリから追い出すデータを選択することが可能となるキャッシュメモリ制御が実現可能となる。また、本実施例を使用すれば、例えばリングバッファで実装されるキューからの最古データ参照時のキャッシュミス発生を抑制することが可能となり、ストリームデータ処理におけるウィンドウからのデータ参照におけるキャッシュヒット率を向上することが可能となる。
【実施例８】
【００８３】
ストリームデータ処理では、最古データが格納されるウィンドウの先頭（HEAD）付近のデータだけでなく、最新のデータが格納されるウィンドウの末尾（TAIL）付近のデータの両方を参照する事が多い。実施例７で述べたとおり、リングバッファによりウィンドウを実装する場合、TAILとHEADの両方のアドレスが可変である。しかし、実施例７の構成は可変な基準アドレスによりキャッシュメモリに格納されやすいアドレス領域を可変にすることができるものの、その基準アドレスはひとつに限定されている。
【００８４】
以上を鑑みて、本実施例は実施例７を拡張し基準アドレスが複数となる場合の構成と処理フローチャートを開示する。
本実施例を実施するためのシステム構成を図２７に示す。実施例７を実現するためのシステム構成である図２６に新たに、BASE_ADDRESSが複数本に追加される。また、複数(M個)存在する基準アドレスからの距離に基づき当該アドレスの優先度を決定するために、 アドレス比較器（ADDRESS_COMPARATOR）110は、複数存在する基準アドレスそれぞれに対する、複数ウェイからのタグ信号で決まる複数（N個）のアドレスとの距離を計算する。つまり、N個の領域のアドレスとM個の基準アドレスそれぞれの距離（差）を計算する。
【００８５】
次に、アドレス比較器1110は、各置換対象のデータ毎に、各基準アドレスそれぞれの距離の重み付き和を計算する。ここで、距離の重み付き和とは、各基準アドレス付近のアドレスのデータをどれだけキャッシュメモリに格納しておきたいかを表す指標を重みとし、その重みを考慮して各基準アドレスへの距離の和を計算する。つまり、N個の領域のアドレスのM個の基準アドレスそれぞれへの距離の重み付き総距離を計算する。距離が大きいほどキャッシュメモリから追い出されやすい場合には、キャッシュメモリに格納したい基準アドレスほど重みの値を小さくする。重みの設定は外部から入力する、または、内部で動的に生成する重み制御信号（WEIGHT）により設定する。距離が負の値になる場合の扱いに関しては実施例７と同様である。アドレス比較器1110は、各置換対象データの基準アドレス集合への総距離を計算後、 N個の領域の重み付き総距離のうち、最も距離の大きい領域を置換対象データとして選択するように、ウェイを示す信号（REPLACE_WAY）を生成し出力する。
【００８６】
以上、本実施例によれば、複数の可変な基準アドレスとの距離に応じてキャッシュメモリに残すデータとキャッシュメモリから追い出すデータを選択することが可能となるキャッシュメモリ制御が実現可能となる。また、本実施例を使用すれば、例えばリングバッファで実装されるキューからの最古データと最新データの両方の参照時のキャッシュミス発生を抑制することが可能となり、ストリームデータ処理におけるウィンドウからのデータ参照におけるキャッシュヒット率を向上することが可能となる。
【実施例９】
【００８７】
近年、記憶媒体としてNAND素子などフラッシュメモリを用いる不揮発性補助記憶装置（SSD）の利用が拡大している。SSDを構成するNAND素子にはSLC(Single Level Cell)、 MLC(Multi Level Cell)、 TCL(Triple Level Cell)など特性の異なる素子がある。本願ではSLCに対する素子としてMLC、 TLCをまとめてMLCとして以降は説明する。SLCはMLCに比較して高価であるが、書込み可能回数、書込み速度の観点でMLCに対して優れる。逆に、MLCは安価である反面、 書込み可能回数、書込み速度の観点でSLCに比較して劣る。
【００８８】
よって、SSDの価格を抑えるためにはMLCを用いる構成が適しており、書込み可能回数制限によるSSDの寿命を延ばすにはSLCを用いる構成が適している。ここで、価格と寿命のトレードオフを考慮する構成としてSLCとMLCを組合わせる構成を考える。SLCとMLCを組み合わせる構成において、書込み可能回数による寿命の優劣を考慮すると、高頻度で書込みが発生するデータをSLCにマッピングし、書込み回数頻度が少ないデータをMLCにマッピングする事が適切である。
【００８９】
本案が開示する実施例１、2、 ７、 8に従うと、アドレスによりキャッシュミスの発生頻度を変化させることが可能である。そこで、SSD内のSLC、 MLCに対してデータをマッピングする際に、図２８のようにキャッシュミスが頻繁に発生する領域（HIGH_CACHE_MISS_RATE REGION）をSLCに割当て、キャッシュミス発生が頻繁ではない領域(LOW_CACHE_MISS_RATE REGION)をMLCに割当てることで、MLCに対するキャッシュミス時の書込み回数を減らすことが可能となり、SSDの高寿命化が期待できる。
【００９０】
ここで、キャッシュミスが頻繁に発生する領域とは、実施例１においてはアドレスの大きい領域であり、また、実施例７、８では基準アドレス（BASE_ADDRESS）から遠い領域のことであり、キャッシュミスが頻繁に発生しない領域とはその逆である。
【００９１】
本機能を実施する一つの形態として、SSD内のSLCとMLCのアドレス情報をオペレーティング・システム（OS）から参照可能とし、OSによりSLC、 MLCのアドレスを考慮してアドレスを管理する方法がある。その場合、本実施例を構成するシステムは図２９
のSSDと中央演算処理装置（CPU）のインターフェス（SSD_IF）を介して、OSからSLC、 MLCのアドレス情報を参照する機能を有することで実現する。OSはSLC、 MLCのアドレス情報に基づき、実施例７、８で示した基準アドレスの設定値を決定する。
【００９２】
また、SSDはSSD内の制御部（SSD_CTRL）でアドレスの変換を行う機能を有するものもある。その場合には、本機能を実施する第２の実施形態として、CPUがSSDに書込みアクセスする際に、書込み先アドレスと共に、SLC、 MLCのどちらに格納するのかを表す情報をSSD_IFを介して送信し、SSD_CTRLにより、当該アドレスをSLC、MLCのいずれに割当てるのかを制御する方法がある。
【００９３】
本実施例として、フラッシュメモリは、キャッシュメモリとして利用してもよいし、メインメモリでもよいし、HDDのような外部記憶装置として利用してもよいし、それらを一部もしくは全部組み合わせた記憶媒体として利用してもよい。
【符号の説明】
【００９４】
CPU…11、キャッシュメモリ…12、ウェイ…20、タグ比較器…1104、深さ比較器…1106、 左右位置比較器…1107、優先度比較器…1109、 アドレス比較器…1110、 プリフェッチ実行判定器…2202、 プリフェッチ実行間引き機…2601
【図１】
2015153122.tif 000003
【図２】
2015153122.tif 000004
【図３】
2015153122.tif 000005
【図４】
2015153122.tif 000006
【図５】
2015153122.tif 000007
【図６】
2015153122.tif 000008
【図７】
2015153122.tif 000009
【図８】
2015153122.tif 000010
【図９】
2015153122.tif 000011
【図１０】
2015153122.tif 000012
【図１１】
2015153122.tif 000013
【図１２】
2015153122.tif 000014
【図１３】
2015153122.tif 000015
【図１４】
2015153122.tif 000016
【図１５】
2015153122.tif 000017
【図１６】
2015153122.tif 000018
【図１７】
2015153122.tif 000019
【図１８】
2015153122.tif 000020
【図１９】
2015153122.tif 000021
【図２０】
2015153122.tif 000022
【図２１】
2015153122.tif 000023
【図２２】
2015153122.tif 000024
【図２３】
2015153122.tif 000025
【図２４】
2015153122.tif 000026
【図２５】
2015153122.tif 000027
【図２６】
2015153122.tif 000028
【図２７】
2015153122.tif 000029
【図２８】
2015153122.tif 000030
【図２９】
2015153122.tif 000031