(57)【特許請求の範囲】
【請求項１】
メインメモリとキャッシュメモリとの間におけるデータの移行を管理するための方法であって、
前記メインメモリおよび前記キャッシュメモリにおける前記データのページに関連付けてカウンタを管理するステップを含み、前記カウンタは、前記ページにアクセスする要求の数を示し、前記メインメモリにおける前記ページに対するカウンタの数は前記メインメモリにおける前記ページの数未満であり、前記方法はさらに、
予め定められた時間間隔で、
前記カウンタに従って、前記メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が、前記キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを判断するステップと、
前記メインメモリのうち前記要求頻度の高いページについての前記ページアクセス要求の数が、前記キャッシュメモリのうち前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリのうち前記要求頻度の高いページを前記キャッシュメモリのうち前記要求頻度の低いページとスワップするステップとを含む、方法。
【請求項２】
メインメモリとキャッシュメモリとの間におけるデータの移行を管理するための方法であって、
前記メインメモリおよび前記キャッシュメモリにおける前記データのページに関連付けてカウンタを管理するステップを含み、前記カウンタは、前記ページにアクセスする要求の数を示し、前記方法はさらに、
予め定められた時間間隔で、前記カウンタのサブセットで、
前記カウンタに従って、前記メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が、前記キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを判断するステップと、
前記メインメモリのうち前記要求頻度の高いページについての前記ページアクセス要求の数が、前記キャッシュメモリのうち前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリのうち前記要求頻度の高いページを前記キャッシュメモリのうち前記要求頻度の低いページとスワップするステップとを含む、方法。
【請求項３】
メインメモリとキャッシュメモリとの間におけるデータの移行を管理するための方法であって、
前記メインメモリおよび前記キャッシュメモリにおける前記データのページに関連付けてカウンタを管理するステップを含み、前記カウンタは、前記ページにアクセスする要求の数を示し、前記方法はさらに、
前記管理に応じて前記カウンタの範囲を動的に拡張するステップを含み、前記方法はさらに、
予め定められた時間間隔で、
前記カウンタに従って、前記メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が、前記キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを判断するステップと、
前記メインメモリのうち前記要求頻度の高いページについての前記ページアクセス要求の数が、前記キャッシュメモリのうち前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリのうち前記要求頻度の高いページを前記キャッシュメモリのうち前記要求頻度の低いページとスワップするステップとを含む、方法。
【請求項４】
前記キャッシュメモリのうち前記要求頻度の低いページは前記キャッシュメモリのうち要求頻度の最も低いページに対応し、前記メインメモリのうち前記要求頻度の高いページは前記メインメモリのうち要求頻度の最も高いページに対応している、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記管理するステップは、所与のページにアクセスする要求に応じて、前記所与のページに関連付けられたカウンタをインクリメントするステップを含む、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記判断するステップおよび前記スワップするステップは、前記メインメモリおよび前記キャッシュメモリにおいて管理される前記ページにアクセスする、メモリユーザによってなされた要求を供給するバックグラウンドにおいて実行される、請求項１〜５のいずれか１項に記載の方法。
【請求項７】
前記メインメモリにおいて管理される前記ページの少なくとも１つのページにアクセスする要求を受取るステップと、
前記少なくとも１つの要求されたページを前記キャッシュメモリに最初に書込むことなく、前記少なくとも１つの要求されたページについての要求を前記メインメモリから供給するステップとをさらに含む、請求項１〜６のいずれか１項に記載の方法。
【請求項８】
前記ページは複数セットのページに分割され、前記複数セットの各々は、前記キャッシュメモリからの複数のページと、前記メインメモリにおける複数のページとを含む、請求項１〜７のいずれか１項に記載の方法。
【請求項９】
前記メインメモリのページは、異なるセットにおける前記キャッシュメモリのページとはスワップされない、請求項８に記載の方法。
【請求項１０】
前記判断するステップは、所与のセットにおける前記メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が、前記所与のセットにおける前記キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを判断する、請求項８または９に記載の方法。
【請求項１１】
前記所与のセットにおける前記メインメモリのうち前記要求頻度の高いページについての前記ページアクセス要求の数が、前記所与のセットにおける前記キャッシュメモリのう前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記スワップするステップは、前記所与のセットにおける前記メインメモリのうち前記要求頻度の高いページを前記所与のセットにおける前記キャッシュメモリのうち前記要求頻度の低いページとスワップする、請求項１０に記載の方法。
【請求項１２】
前記予め定められた時間間隔は１マイクロ秒（１μｓ）毎である、請求項１〜１１のいずれか１項に記載の方法。
【請求項１３】
システムであって、
データのページを管理するように構成されたメインメモリおよびキャッシュメモリを含み、前記キャッシュメモリは、前記メインメモリよりも少ないページを管理するように構成されており、前記メインメモリよりも、より少ない待ち時間、より高い帯域幅またはより少ない電力消費のうち少なくとも１つを有し、前記システムはさらに、
前記メインメモリおよび前記キャッシュメモリにおける前記ページに関連付けてカウンタを管理するように構成されたプロファイラを含み、前記カウンタは、前記ページにアクセスする要求の数を示すように構成されており、前記メインメモリにおける前記ページに対するカウンタの数は前記メインメモリにおける前記ページの数未満であり、前記システムはさらに、
ムーバーを含み、前記ムーバーは、
前記メインメモリにおける要求頻度の高いページについてのページアクセス要求の数が、前記キャッシュメモリにおける要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを、前記カウンタに従って判断するように構成され、
前記メインメモリにおける前記要求頻度の高いページについての前記ページアクセス要求の数が、前記キャッシュメモリにおける前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリにおける前記要求頻度の高いページを前記キャッシュメモリにおける前記要求頻度の低いページとスワップするように構成される、システム。
【請求項１４】
システムであって、
データのページを管理するように構成されたメインメモリおよびキャッシュメモリを含み、前記キャッシュメモリは、前記メインメモリよりも少ないページを管理するように構成されており、前記メインメモリよりも、より少ない待ち時間、より高い帯域幅またはより少ない電力消費のうち少なくとも１つを有し、前記システムはさらに、
前記メインメモリおよび前記キャッシュメモリにおける前記ページに関連付けてカウンタを管理するように構成されたプロファイラを含み、前記カウンタは、前記ページにアクセスする要求の数を示すように構成されており、前記システムはさらに、
ムーバーを含み、前記ムーバーは、予め定められた時間間隔で、前記カウンターのサブセットで、
前記メインメモリにおける要求頻度の高いページについてのページアクセス要求の数が、前記キャッシュメモリにおける要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを、前記カウンタに従って判断するように構成され、
前記メインメモリにおける前記要求頻度の高いページについての前記ページアクセス要求の数が、前記キャッシュメモリにおける前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリにおける前記要求頻度の高いページを前記キャッシュメモリにおける前記要求頻度の低いページとスワップするように構成される、システム。
【請求項１５】
システムであって、
データのページを管理するように構成されたメインメモリおよびキャッシュメモリを含み、前記キャッシュメモリは、前記メインメモリよりも少ないページを管理するように構成されており、前記メインメモリよりも、より少ない待ち時間、より高い帯域幅またはより少ない電力消費のうち少なくとも１つを有し、前記システムはさらに、
前記メインメモリおよび前記キャッシュメモリにおける前記ページに関連付けてカウンタを管理するように構成されたプロファイラを含み、前記カウンタは、前記ページにアクセスする要求の数を示すように構成されており、前記プロファイラはさらに、
前記管理に応じて前記カウンタの範囲を動的に拡張するように構成されており、前記システムはさらに、
ムーバーを含み、前記ムーバーは、
前記メインメモリにおける要求頻度の高いページについてのページアクセス要求の数が、前記キャッシュメモリにおける要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを、前記カウンタに従って判断するように構成され、
前記メインメモリにおける前記要求頻度の高いページについての前記ページアクセス要求の数が、前記キャッシュメモリにおける前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリにおける前記要求頻度の高いページを前記キャッシュメモリにおける前記要求頻度の低いページとスワップするように構成される、システム。
【請求項１６】
メモリアクセス要求に関連付けられた入力アドレスを、前記メモリアクセス要求を供給するのに有効な前記メインメモリまたは前記キャッシュメモリ内の対応するページにマッピングするように構成されたマッパーをさらに含む、請求項１３〜１５のいずれか１項に記載のシステム。
【請求項１７】
前記ページは各々、４キロバイト（４ＫＢ）のデータに対応する、請求項１３〜１６のいずれか１項に記載のシステム。
【請求項１８】
１または複数のプロセッサによって実行されるプログラム命令を格納する１つ以上のコンピュータ読取り可能記憶媒体であって、前記プログラム命令は前記プロセッサに動作を実行させ、前記動作は、
メインメモリおよびキャッシュメモリにおける前記データのページに関連付けてカウンタを管理するステップを含み、前記カウンタは、前記ページにアクセスする要求の数を示し、前記メインメモリにおける前記ページに対するカウンタの数は前記メインメモリにおける前記ページの数未満であり、前記動作はさらに、
予め定められた時間間隔で、
前記メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が前記キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを前記カウンタに従って、判断するステップと、
前記メインメモリのうち前記要求頻度の高いページについての前記ページアクセス要求の数が前記キャッシュメモリのうち前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリのうち前記要求頻度の高いページと前記キャッシュメモリのうち前記要求頻度の低いページとをスワップするステップとを含む、１つ以上のコンピュータ読取り可能記憶媒体。
【請求項１９】
１または複数のプロセッサによって実行されるプログラム命令を格納する１つ以上のコンピュータ読取り可能記憶媒体であって、前記プログラム命令は前記プロセッサに動作を実行させ、前記動作は、
メインメモリおよびキャッシュメモリにおける前記データのページに関連付けてカウンタを管理するステップを含み、前記カウンタは、前記ページにアクセスする要求の数を示し、前記動作はさらに、
予め定められた時間間隔で、前記カウンターのサブセットで、
前記メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が前記キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを前記カウンタに従って、判断するステップと、
前記メインメモリのうち前記要求頻度の高いページについての前記ページアクセス要求の数が前記キャッシュメモリのうち前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリのうち前記要求頻度の高いページと前記キャッシュメモリのうち前記要求頻度の低いページとをスワップするステップとを含む、１つ以上のコンピュータ読取り可能記憶媒体。
【請求項２０】
１または複数のプロセッサによって実行されるプログラム命令を格納する１つ以上のコンピュータ読取り可能記憶媒体であって、前記プログラム命令は前記プロセッサに動作を実行させ、前記動作は、
メインメモリおよびキャッシュメモリにおける前記データのページに関連付けてカウンタを管理するステップを含み、前記カウンタは、前記ページにアクセスする要求の数を示し、前記動作はさらに、
前記管理に応じて前記カウンタの範囲を動的に拡張するステップと、
予め定められた時間間隔で、
前記メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が前記キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数よりも大きいかどうかを前記カウンタに従って、判断するステップと、
前記メインメモリのうち前記要求頻度の高いページについての前記ページアクセス要求の数が前記キャッシュメモリのうち前記要求頻度の低いページについての前記ページアクセス要求の数よりも大きいという判断に応じて、前記メインメモリのうち前記要求頻度の高いページと前記キャッシュメモリのうち前記要求頻度の低いページとをスワップするステップとを含む、１つ以上のコンピュータ読取り可能記憶媒体。
【請求項２１】
前記キャッシュメモリは、少なくとも１２８メガバイト（ＭＢ）のサイズを有する、請求項１８〜２０のいずれか１項に記載の１つ以上のコンピュータ読取り可能記憶媒体。
【請求項２２】
前記メインメモリは、少なくとも４ギガバイト（ＧＢ）のサイズを有する、請求項１８〜２１のいずれか１項に記載の１つ以上のコンピュータ読取り可能記憶媒体。
【請求項２３】
コンピュータによって実行されるプログラムであって、前記プログラムは、前記コンピューターに請求項１〜１２のいずれか１項に記載の方法を実行させる、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本願は、２０１６年２月１０日に出願された「プロファイリングキャッシュ置換（Profiling Cache Replacement）」と題された仮出願第６２／２９３，６８８号の優先権を米国特許法第１１９条の下で主張する、２０１６年４月１２日に出願された米国特許出願連続番号第１５／０９７，１７７号の優先権を主張するものである。これらの開示は、それら全体が引用によりこの明細書中に援用されている。
【背景技術】
【０００２】
背景
コンピューティングにおいては、キャッシュは、頻繁にアクセスされたデータを一時的に格納するために用いられるメモリのブロックであって、キャッシュされたデータについての将来の要求が未キャッシュのデータについての要求よりも迅速に供給されることを可能にする。要求されたデータがキャッシュに含まれている（「キャッシュヒット（cache hit）」として公知のシナリオ）場合、当該要求は、単純にキャッシュを読出すことによって供給することができる。これは、メインメモリからデータにアクセスするよりも比較的高速である。逆に、要求されたデータがキャッシュに含まれていない（「キャッシュミス（cache miss）」として公知のシナリオ）場合、データは再計算されるか、または、従来の技術では、その元の格納位置からキャッシュに書込まれる。これは、単にキャッシュからデータを読出す場合よりも低速である。このため、データ要求のうちより大きな部分がキャッシュメモリから供給される場合に、全体的なシステム性能が速度の点で改善される。
【０００３】
キャッシュメモリは典型的にはメインメモリより小さいので、予めキャッシュに書込まれていたデータは、より最近に用いられたデータと置換される必要があるかもしれない。これを行なうために、キャッシュ置換アルゴリズムが採用されている。従来のキャッシュ置換アルゴリズムは、最長時間未使用の（least recently used：ＬＲＵ）アルゴリズム、最も最近使用された（most recently used：ＭＲＵ）アルゴリズム、使用頻度が最も低い（least frequently used：ＬＦＵ）アルゴリズム、ランダム置換アルゴリズムなどを含む。おおまかに言えば、キャッシュ置換アルゴリズムは、コンピュータプログラムまたはハードウェア維持型構造がキャッシュメモリを管理するために実現する１セットの最適化命令である。特に、キャッシュ置換アルゴリズムは、メインメモリからの情報のための空間を空けるために、キャッシュメモリ内におけるどの情報を追出すべきかを選択する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来のキャッシュ置換アルゴリズムの多くは、その時点でキャッシュメモリに存在しないデータブロックについての情報を管理していない。結果として、データのワーキングセットのサイズがキャッシュメモリのサイズを上回ると、過度の書込み（fill）および追出しトラフィックが生成される可能性がある。この過度の書込みおよび追出しトラフィックは、「スラッシング」として公知である状態を引起こす可能性がある。この場合、いくつかのキャッシュミスが劇的に増加し、これらのミスの結果キャッシュの書込みおよび追出しを実行するのに費やされる時間が、データのワーキングセットのために元来要求されていたコンピューティング動作を実行するのに費やされる時間を上回る可能性がある。したがって、従来のキャッシュ置換アルゴリズムは、コンピューティング動作を阻害し得るという欠点を有する。
【課題を解決するための手段】
【０００５】
概要
この文書はプロファイリングキャッシュ置換を記載する。プロファイリングキャッシュ置換は、全体的なシステム性能を向上させるために、メインメモリとキャッシュメモリとの間におけるデータ移行を管理するための技術である。キャッシュメモリおよびメインメモリはともに、データのページを格納するように構成されており、キャッシュメモリは、メインメモリよりも小さく、このため、管理することができるページがメインメモリよりも少なくなる。しかしながら、メインメモリと比べて、キャッシュメモリは、より短い待ち時間、より高い帯域幅またはより少ない電力消費のうち少なくとも１つを有する。結果として、データアクセス要求のうちより大きな部分をキャッシュメモリから供給することができれば、システム性能が向上する。データアクセス要求のうちキャッシュメモリから供給される部分を増やすために、プロファイリングキャッシュ置換は、要求頻度の高いページをキャッシュメモリにキャッシュし、要求頻度の低いページをメインメモリに移行させる（かまたは残しておく）。
【０００６】
従来のキャッシュ置換技術とは異なり、プロファイリングキャッシュ置換は、キャッシュメモリにおいて管理されるページだけではなく、メインメモリにおいて管理されるページにもアクセスするためのメモリ要求をカウントするカウンタを管理するためにプロファイラを用いる。プロファイラによって収集された（たとえばメモリアクセス要求についての）情報に基づき、ムーバーは、メインメモリとキャッシュメモリとの間でページを移動させる。一例として、ムーバーは、メインメモリのうち要求頻度の高いページ（メインメモリのうち要求頻度の最も高いページなど）を、キャッシュメモリのうち要求頻度の低いページ（キャッシュメモリのうち要求頻度の最も低いページなど）とスワップすることができる。ムーバーがこれを行ない得るのは、たとえば、メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が、キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数よりも大きいことをカウンタが示している場合である。
【０００７】
メモリユーザ（たとえば、クライアントアプリケーション）の動作を妨げないようにするために、メモリユーザによってなされる要求は、キャッシュミスのためにブロックされず、ムーバーは、バックグラウンドでページ・スワッピングを実行する。ブロックしない動作に関して、ページアクセス要求によって結果としてキャッシュミスがもたらされると、要求されたページはキャッシュメモリには直ちにロードされず、このため、キャッシュメモリから要求を供給することができるようになる。代わりに、要求はメインメモリから直接供給される。バックグラウンドでページ・スワッピングを実行することに関して、ムーバーによって実行されるページ・スワッピングよりも、メモリユーザによってなされる要求を供給することの方が優先される。これを行なうために、ムーバーは、マイクロ秒（μｓ）毎に１回などのように予め定められた時間間隔でページをスワップするように制限されている。ムーバーは、メインメモリのうち要求頻度の高いページについてのページアクセス要求の数が、キャッシュメモリのうち要求頻度の低いページについてのページアクセス要求の数を上回っているかどうかを、予め定められた時間間隔で、判断する。このようにすることで、ムーバーは、メインメモリのうち要求頻度の高いページをキャッシュメモリのうち要求頻度の低いページとスワップする。これを行なう際に、プロファイリングキャッシュ置換は、キャッシュメモリに書込まれたページを最適化し、これによりメモリユーザの動作に干渉することなく、結果としてシステム性能を向上させる。
【０００８】
この概要は、詳細な説明において以下にさらに記載されている技術に関する単純化された概念を紹介するために記載されている。この概要は、主張された主題の本質的な特徴を識別するように意図されたものではなく、また、主張された主題の範囲を決定するのに使用されるように意図されたものでもない。
【図面の簡単な説明】
【０００９】
プロファイリングキャッシュ置換のための技術およびデバイスの実施形態が添付の図面に関連付けて説明される。同様の特徴および構成要素を参照するために、添付の図面全体にわたって、同じ番号が用いられている。
【図１】当該技術が実現され得る例示的な環境を示す図である。
【図２】第１の時間におけるメインメモリおよびキャッシュメモリについての例示的なページカウンタ値を示す図である。
【図３】第１の時間の後に続く第２の時間におけるメインメモリおよびキャッシュメモリについての例示的なページカウンタ値を示す図である。
【図４】図１の例示的なメモリプロファイリングコンピューティングデバイスを示す図である。
【図５】プロファイリングアルゴリズムに従ってキャッシュメモリ内のページを置換するための方法を示す図である。
【図６】プロファイリングキャッシュ置換のために縮小空間カウンタを用いてページアクセスをカウントするための方法を示す図である。
【図７】メモリの各ページに対して１未満となる割合で設けられたカウンタを用いてプロファイリングキャッシュ置換のためにページアクセスをカウントするための方法を示す図である。
【図８】プロファイリングキャッシュ置換を具体化するか、または、プロファイリングキャッシュ置換の使用を可能にする技術が実現され得る、例示的コンピューティングシステムを示す図である。
【発明を実施するための形態】
【００１０】
詳細な説明
概略
この文書は、プロファイリングキャッシュ置換を用いる技術と、プロファイリングキャッシュ置換を可能にするデバイスとを説明する。これらの技術およびデバイスを用いることにより、メインメモリとキャッシュメモリとの間におけるデータ移行が、最長時間未使用の（ＬＲＵ）アルゴリズム、最も最近使用された（ＭＲＵ）アルゴリズム、使用頻度が最も低い（ＬＦＵ）アルゴリズム、ランダム置換アルゴリズムなどの従来のキャッシュ置換技術よりもシステム性能を向上させる態様で管理される。性能の向上は、少なくとも部分的には、従来の技術と比べて、メインメモリとキャッシュメモリとの間におけるデータの移行とともに発生する「スラッシング（thrashing）」の量を減じることによって、もたらされる。「スラッシング」という語は、データのワーキングセットのサイズがキャッシュメモリのサイズを上回ったときに生成され得る過度の書込みおよび追出しトラフィックによって引起こされる状態を指すものである。スラッシングは、結果として、キャッシュミスの数を劇的に増加させる可能性があり、これにより、システムが、データのワーキングセットのために本来要求されていたコンピューティング動作を実行する場合よりも、結果として生じるミスのためにキャッシュの書込みおよび追出しを実行するのにより多くの時間を費やすこととなる。プロファイリングキャッシュ置換を適用することにより、スラッシングを減らして全体的なシステム性能を向上させる態様で、キャッシュメモリおよびメインメモリ内のデータを管理することができる。
【００１１】
一例として、クライアントアプリケーションなどのメモリユーザは、メモリにロードされた特定のページにアクセスすることを要求することができる。この例においては、クライアントアプリケーションが初期化プロセスの一環として特定のページにアクセスするようにとメモリに要求する場合を想定する。初期化プロセス中、クライアントアプリケーションは、特定のページへのアクセスを何度も要求してもよい。クライアントアプリケーションの要求を最も効率的に供給するために、特定のページは、たとえば、特定のページについての要求が、メインメモリから供給される場合よりも迅速に供給され得るように、キャッシュメモリにロードすることができる。初期化プロセスの完了後、クライアントアプリケーションは、特定のページにアクセスする必要がないかもしれず、または、他のページと比べて少ししか特定のページにアクセスしなくてもよいかもしれない。通常の動作中、クライアントアプリケーションは、代わりに、他のページにより多くアクセスするように要求し得ることで、他のページにアクセスする要求が最終的に特定のページについての要求を上回るようにし得る。なぜなら、初期化プロセスが完了してしまっており、もはや、特定のページが要求されないからである。
【００１２】
クライアントアプリケーションの通常の動作の効率は、このように、他のページについての要求をキャッシュメモリから供給することによって向上させてもよい。なぜなら、たとえば、キャッシュメモリは、メインメモリよりもサイズが小さいにも関わらず、メインメモリよりも待ち時間がより少なく、帯域幅がより高く、電力消費がより少ないからである。言いかえれば、他のページのうちの１ページを特定のページとスワップすることによって効率を向上させ得る。「スワップ（スワッピング）」という語は、この明細書中において用いられている場合、他の１ページに対応するデータをキャッシュメモリに書込み、特定のページに対応するデータをキャッシュメモリから追出すことを可能にする動作または一連の動作を指すものである。いくつかのシナリオにおいては、他の１ページに対応するデータを特定のページに対応するデータと単純に交換することにより、他の１ページのデータがキャッシュメモリにおける特定のページの代わりとなり、かつ、特定のページのデータがメインメモリにおける他の１ページのデータの代わりとなるようにする。このようなシナリオにおいては、ページがキャッシュされると、そのデータはメインメモリにではなくキャッシュメモリだけに常駐することとなる。
【００１３】
しかしながら、他のシナリオにおいては、メモリ内の各ページについての少なくともいくらかのデータは、そのデータに対応するページがキャッシュされているか否かに関わらず、メインメモリに存在している。これらのシナリオにおいては、ページがキャッシュされると、キャッシュメモリにおけるページおよびメインメモリにおけるページが、一緒に、ページの有効データを提供する。しかしながら、いくつかの場合においては、キャッシュメモリにおけるページのうちのいくつかは、それらのページが書込まれていないので、有効データを含まない可能性もある。メインメモリにおけるページのうちのいくつかはまた、それらのページのデータ全体がキャッシュメモリにおいて変更されたなどの場合、有効データを含まない可能性もある。これらのシナリオの下では、特定のページのデータを他の１ページに対応するデータとスワップすることは、最初に記載されたシナリオにおけるような単なるデータの交換ではない。むしろ、スワッピングは、特定のページに対応するデータを、キャッシュメモリからメインメモリ内のそれぞれのページに追出すことを含む。それぞれのページにおいては、データのうちキャッシュメモリ内にある間に変更された部分が、メインメモリ内のそれぞれのページにコピーされる。このコピーは変更済みのブロックに限定されている。なぜなら、それぞれのページが、依然として、未変更のブロックについて同じデータを管理しているからである。追出し後、データ追出し済みのキャッシュメモリのページは、メインメモリからの他の１ページのデータで満たされる。しかしながら、それぞれのページ（たとえば、追出されたデータが配置されるページ）および他の１ページ（たとえば、利用可能なキャッシュメモリページを書込むのに用いられたメインメモリデータ）は、同じページに対応していない。
【００１４】
メインメモリおよびキャッシュメモリが構成される態様と、これにより、それらのページがスワップされる態様とに関わらず、スワッピングの後、他の１ページについての要求がキャッシュメモリから供給され得る。いつ、およびどのページがメインメモリとキャッシュメモリとの間でスワップされるかを判断するために、プロファイリングキャッシュ置換により、メインメモリおよびキャッシュメモリの両方において管理されているデータのページへのアクセスがカウントされる。特に、「アドレス指定可能メモリ」におけるページへのアクセスはカウンタで追跡される。「アドレス指定可能メモリ」という語は、メモリのうちメモリユーザによって認識される部分を指している。上述の最初のシナリオにおいては、アドレス指定可能メモリのサイズは、メインメモリのサイズにキャッシュメモリのサイズを加えたものに対応する。しかしながら、他のシナリオにおいては、アドレス指定可能メモリのサイズはちょうどメインメモリのサイズに対応する。このため、メインメモリにおけるページの数に対応するカウンタの数が管理される。このために、プロファイラは、アドレス指定可能メモリにおけるページの各々についてのカウンタを管理することができるとともに、それらのページのうちの１つへのアクセスが要求された場合、そのページについてのカウンタをインクリメントすることができる。上述の他のメモリ構成およびスワッピングシナリオにおいては、カウンタは、アドレス指定可能メモリにおける各ページごとに管理される。たとえば、カウンタは、メインメモリ内の各ページごとに管理される。なぜなら、キャッシュされたページもメインメモリ内のデータによって表わされるからである。
【００１５】
初期化中に特定のページへのアクセスを何度も要求するクライアントアプリケーションについての説明に戻ると、初期化の後には、特定のページへのアクセスを要求しないか、またはほとんど要求せず、通常の動作中には、他のページへのアクセスをより多く要求する。何らかの時点においてプロファイラによって管理されるカウンタは、他のページの少なくとも１ページへのアクセスが、特定のページへのアクセスよりも多く要求されたことを示し得る。これが該当する場合、メインメモリからキャッシュメモリに、かつこれとは逆にページを移動させるように構成されているムーバーは、他のページのうち、特定のページよりも多く要求された１ページを当該特定のページとスワップすることができる。特に、ムーバーは、要求頻度のより多いページをメインメモリからキャッシュメモリに移動させることができ、かつ、特定のページをキャッシュメモリからメインメモリに移動させることができる。クライアントアプリケーションの動作が中断されないようにするために、クライアントアプリケーションによってなされた要求はブロックされず、キャッシュメモリにおいて管理されるデータを最適化するためにページをスワップする動作がバックグラウンドで実行される。特に、ページアクセス要求の結果、キャッシュミスがもたらされた場合、要求されたページは、キャッシュメモリには直接ロードされず、これにより、キャッシュメモリから要求を供給することができるようになる。そうではなくむしろ、その要求をメインメモリから直接供給させる。さらに、ムーバーは、予め定められた時間間隔で、たとえば、マイクロ秒（μｓ）毎に１回、ページスワップを開始するように制限されている。結果として、ムーバーは、他の時にメインメモリまたはキャッシュメモリにアクセスするためにクライアントアプリケーションと競合することはない。このような技術を用いれば、コンピューティング動作の中断が回避され得るとともに、スラッシングが減らされ、これにより、システムの全体的性能を向上させ得る。
【００１６】
これは、プロファイリングキャッシュ置換が実行され得る方法のうち単なる一例に過ぎず、他の例および詳細が以下に記載される。この明細書はここで、ページカウンタ値を示す図を参照する例示的環境に向けられ、その後、デバイスおよび方法ならびに例示的なコンピューティングシステムが説明される。
【００１７】
例示的環境
図１は、プロファイリングキャッシュ置換が採用され得る例示的環境１００の具体例である。環境１００は、プロファイルされたメモリ１０４を有するメモリ・プロファイリングコンピューティングデバイス１０２を示す。図１の特定の例においては、メモリ・プロファイリングコンピューティングデバイス１０２はスマートフォンとして構成されているが、他の構成も企図される。メモリ・プロファイリングコンピューティングデバイス１０２のうち、プロファイリングキャッシュ置換を用いてメモリを最適化することができる他の構成が後の図に示されている。
【００１８】
環境１００はまた、プロファイルされたメモリ１０４の構成要素を示す。プロファイルされたメモリ１０４は、キャッシュメモリ１０６およびメインメモリ１０８を含む。キャッシュメモリ１０６およびメインメモリ１０８は、オペレーティングシステム、クライアントアプリケーションなどによって、メモリユーザによってアクセスすべきデータを格納することができる。たとえば、キャッシュメモリ１０６およびメインメモリ１０８は、データのページを格納することができる。「ページ」という語は、この明細書中に用いられている場合、同じサイズのデータブロック（たとえば、４キロバイト（kilobyte：ＫＢ）のデータブロック）を指している。メインメモリ１０８と比べて、キャッシュメモリ１０６はより小さく、ストレージがより少なく、このため、格納できるデータのページがメインメモリ１０８よりも少なくなる。ストレージについてはメインメモリ１０８よりも小さいが、キャッシュメモリは、メインメモリ１０８よりも、より少ない待ち時間、より高い帯域幅またはより少ない電力消費のうち少なくとも１つを有する。キャッシュメモリ１０６がこれらの特徴を有しているために、未キャッシュデータの場合よりも、キャッシュ済みデータの場合の方がデータアクセス要求のより大きな部分が供給されることとなり、結果として、メモリ・プロファイリングコンピューティングデバイス１０２のために、速度、パワーまたはシステム効率の他の何らかの基準の点で、より効率的に要求が供給されることとなる。
【００１９】
プロファイルされたメモリ１０４はまた、マッパー１１０、プロファイラ１１２およびムーバー１１４を含む。マッパー１１０、プロファイラ１１２およびムーバー１１４は、使用頻度の高いページをメインメモリ１０８にキャッシュして、使用頻度の低いページを残すことによって上記プロファイルされたメモリ１０４の性能を最適化するための機能を表わしている。マッパー１１０は各々のメモリアクセスのために用いられる。マッパー１１０は、キャッシュメモリ１０６におけるアドレス（たとえばキャッシュヒット）またはメインメモリ１０８におけるアドレス（たとえばキャッシュミス）に対して入力アドレスをマッピングする。従来の技術とは対照的に、ページアクセス要求の結果、キャッシュミスがもたらされた場合、要求されたページは、キャッシュメモリ１０６に直接ロードされず、このため、キャッシュメモリ１０６から要求を供給することができるようになる。そうではなくむしろ、要求をメインメモリ１０８から直接供給させる。たとえば、要求されたページは、ページへのアクセスをメインメモリ１０８に直接要求したメモリユーザに提供される。
【００２０】
プロファイラ１１２は、メモリアクセスについての情報を収集するための機能を表わしている。一例として、プロファイラ１１２は、プロファイルされたメモリ１０４内のページにアクセスする要求の数などの、ページアクセスの数を追跡する。各ページにアクセスする要求の数が追跡されている例を用いて、この明細書中において技術が説明されているが、プロファイラ１１２は、この明細書中に記載される技術の精神または範囲から逸脱することなく、さまざまな方法でメモリアクセスを追跡してもよい。要求のサイズが各要求にわたって均一でない場合、たとえば、いくつかの要求が６４Ｂに対するものであり他の要求が１２８Ｂに対するものであるなどの場合、プロファイラ１１２は、要求の数ではなくバイトをカウントすることができる。代替的には、プロファイラ１１２は、メモリ内のページにアクセスするより多くの要求を複数の要求として処理することができる。他の例においては、メモリアクセスは、ページへのアクセス要求の各々をカウントすることなく追跡することができる。むしろ、ページについての読出し要求は追跡することができるが、書込み要求は追跡することができない。同様に、ページについての書込み要求は追跡することができるが、読出し要求は追跡することができない。
【００２１】
ページへのメモリアクセスを追跡するのに用いられる単位に関わらず、プロファイラ１１２は、キャッシュメモリ１０６内の各ページおよびメインメモリ１０８内の各ページについてのカウンタを管理することができる。ページへのアクセスが要求されると、プロファイラ１１２はそのページについてのカウンタをインクリメントし、これにより、ページアクセスを追跡することができる。しかしながら、１つ以上の実現例においては、プロファイラ１１２は、メモリの各ページに対するカウンタの割合が１未満となるように管理する。これを行なう際に、プロファイラ１１２は、プロファイルされたメモリ１０４のページアクセスを記述する追跡情報を格納するのに用いられるメモリの量を減らすことができる。プロファイラ１１２が用いるカウンタの割合がメモリの各ページに対して１未満となっている態様の詳細をこの明細書中において以下に説明する。
【００２２】
ムーバー１１４は、キャッシュメモリ１０６とメインメモリ１０８との間でページを移動させるための機能を表わしている。たとえば、ムーバー１１４は、メインメモリ１０８のうち要求頻度の高いページを、キャッシュメモリ１０６のうち要求頻度の低いページとスワップすることができる。要求頻度の「高い」ページという語は、この明細書中において用いられている場合、対象となるメモリの部分における他の部分よりも多く要求されているページを指しているとともに、対象となる部分における要求頻度の最も高いページ、当該部分における上位１０パーセントを占める要求されページ、などに対応し得る。たとえば、メインメモリ１０８における要求頻度の高いページは、要求の数がメインメモリ１０８におけるページのうち上位１０パーセントの順位にあるページであり得るか、または、メインメモリ１０８における要求頻度の最も高いページであり得る。同様に、要求頻度の「低い」ページという語は、対象となるメモリの部分における他のページよりも要求頻度が低いページを指しているとともに、対象となる部分における要求頻度の最も低いページ、当該部分における下位１０パーセントを占める要求されたページなど、に対応し得る。一例として、キャッシュメモリ１０６における要求頻度の低いページは、要求の数がキャッシュメモリ１０６内のページのうち下位１０パーセントの順序にあるページであり得るか、または、キャッシュメモリにおいて要求頻度の最も低いページであり得る。しかしながら、「高い」および「低い」は、メモリのうち上記ページに対応する部分とともに用いられていることに留意されたい。このため、メインメモリ１０８における要求頻度の高いページは、キャッシュメモリ１０８における要求頻度の低いページよりもアクセスについての要求の数が少ない場合もあり、または、要求が同様の数であってもよい。しかしながら、メインメモリ１０８における要求頻度の高いページは、メインメモリ１０８における要求頻度の低いページよりも、アクセスについての要求の数が大きい。加えて、プロファイルされたメモリ１０４における（たとえば、メインメモリ１０８およびキャッシュメモリ１０６におけるページのうち）要求頻度の高いページは、プロファイルされたメモリ１０４における要求頻度の低いページよりも、アクセスについての要求の数が大きい。
【００２３】
いずれの場合も、メインメモリ１０８のうち要求頻度の高いページが、キャッシュメモリ１０６のうち要求頻度の低いページよりも多くアクセス要求されているという判断に応じて、ムーバー１１４は、メインメモリ１０８のうち要求頻度の高いページを、キャッシュメモリ１０６のうち要求頻度の低いページとスワップし得る。キャッシュメモリ１０６とメインメモリ１０８との間でページを移動させることに加えて、ムーバー１１４はまた、メインメモリ１０８内のページが、キャッシュメモリ１０６内のページよりも多くアクセスされるかどうかについての判断を行なうための機能を表わしている。ムーバー１１４は、プロファイラ１１２（たとえば、カウンタ）によって収集された情報をチェックすることによってこれを行なってもよい。ムーバー１１４がページを移動させる（たとえば、キャッシュメモリ１０６内のページをメインメモリ１０８内のページとスワップする）と、ムーバー１１４は、マッパー１１０によって用いられるアドレス情報を更新し、これにより、将来のメモリアクセス要求が、キャッシュメモリ１０６またはメインメモリ１０８における正確なアドレスにマッピングされるようにする。なお、メインメモリ１０８のうち要求頻度の高いページがキャッシュメモリ１０６のうち要求頻度の低いページよりも多くアクセス要求されていないとの判断に応じて、ムーバー１１４がページをスワップしないことに留意されたい。
【００２４】
文脈に応じて、メインメモリおよびキャッシュメモリについての例示的なページカウンタ値の略図を示す図２および図３について検討する。図２の略図２００は、第１の時間におけるメインメモリおよびキャッシュメモリについての例示的なページカウンタ値を示し、図３の略図３００は、第１の時間よりも後の第２の時間におけるメインメモリおよびキャッシュメモリについての例示的なページカウンタ値を示す。以下により詳細に説明されるように、ムーバー１１４は要求されたページアクセスについての情報をチェックする。ムーバー１１４はまた、予め定められた時間間隔で（たとえば、マイクロ秒（μｓ）毎に１回）ページスワップを開始する。予め定められた時間間隔に関して、略図２００に対応する第１の時間は、このような特定の予め定められた時間間隔の発生の前であってもよく、略図３００に対応する第２の時間は、特定の予め定められた時間間隔の発生の後である。
【００２５】
略図２００は、ページアクセスの数を示すカウンタ値に対応する第１の軸２０２を含む。略図２００の第２の軸２０４は、メモリにおいて管理されるページを表わしている。略図２００はまた分割線２０６を含む。分割線２０６の左側に示されるバーは、第１の時間におけるキャッシュメモリ１０６内のページのカウンタ値を表わしており、分割線の右側に示されるバーは、第１の時間におけるメインメモリ１０８内のページのカウンタ値を表わしている。図２および図３によって示される特定の例においては、キャッシュメモリ１０６は１２８メガバイト（１２８ＭＢ（megabyte））であり、メインメモリ１０８は４ギガバイト（４ＧＢ（gigabyte））であり、データの各ページは４キロバイト（４ＫＢ）である。このように、分割線２０６の左側のバーは、４ＫＢページ相当の１２８ＭＢを表わしており、分割線２０６の右側のバーは、４ＫＢページ相当の４ＧＢ（１００万ページ）を表している。これらが単に例示的なサイズであること、キャッシュメモリ１０６のサイズ、メインメモリ１０８のサイズ、およびそれらメモリに管理されているページが、この明細書中に記載される技術の精神または範囲から逸脱することなく例において用いられるサイズとは異なり得ることが認識されるはずである。
【００２６】
説明された概念をより理解し易くするために、図２および図３は、ページがキャッシュされたときにそのデータがメインメモリ１０８内ではなくキャッシュメモリ１０６内にあるように、メインメモリ１０８内のページに対応するデータがキャッシュメモリ１０６内のページに対応するデータと単に交換されるだけであるという、上述のシナリオを表わすために例示されてきた。これらのシナリオにおいては、メモリユーザは、アドレス指定可能メモリを４ＧＢと１２８ＭＢとの組合せ（たとえば、メインメモリ１０８とキャッシュメモリ１０６との組合せ）と認識する。しかしながら、実現例においては、キャッシュメモリ１０６がメインメモリ１０８と比べて小さい（１２８ＭＢ対４ＧＢ）場合、メインメモリ１０８およびキャッシュメモリ１０６は他のメモリ構成および上述のスワッピングシナリオに従って構成されてもよい。
【００２７】
他のメモリ構成および上述のスワッピングシナリオにおいては、キャッシュメモリ１０６内の或るページおよびメインメモリ１０８内の或るページは一緒に、キャッシュされたページの有効データを提供する。これらの他のシナリオにおいては、ページがキャッシュされた場合、キャッシュされたページに対応する少なくともいくらかのデータがキャッシュメモリ１０６内にあってもよく、キャッシュされたページに対応する少なくともいくらかのデータもメインメモリ１０８内にあってもよい。しかしながら、いくつかの場合においては、キャッシュメモリ１０６内のページのうちのいくつかは、それらのページが書込まれていないので、有効データを含んでいない可能性もある。メインメモリ１０８内のページのうちのいくつかはまた、それらのページのデータ全体がキャッシュメモリ１０６において変更された場合などには、有効データを含んでいない可能性もある。これらの他の構成およびスワッピングシナリオに従って、かつメインメモリ１０８が４ＧＢであり、キャッシュメモリが１２８ＭＢである例を想定して、メモリユーザは、アドレス指定可能メモリを単に４ＧＢ（たとえば、単にメインメモリ１０８）と認識する。メインメモリ１０８からの４ＫＢページのデータをキャッシュメモリ１０６に書込むと、ムーバー１１４は、当該ページの４ＫＢのデータの各部分をキャッシュメモリ１０６に書込まない可能性がある。たとえば、ムーバー１１４は、代わりに、１ＫＢのページのデータをキャッシュメモリ１０６に書込んでもよい。ムーバーは、他の３ＫＢがさらに用いられるかどうかについていくらか不確実である場合などには、要求アドレスに近い１ＫＢのデータを書込んでもよい。ページへの要求のほとんどが書込み要求になるであろうことが予想される場合、ムーバー１１４はキャッシュメモリ１０６に上書きされ得るページのデータを書込まない可能性がある。むしろ、ムーバー１１４は、ページのうち各６４バイト部分を見つけるべき箇所を示すための情報をキャッシュメモリ１０６に書込むことができる。
【００２８】
図２および図３に示される例に戻って、ページを表すバーは、カウンタ値の大きい順に左から右に、かつ、キャッシュメモリ１０６およびメインメモリ１０８の範囲内において、順序付けられている。このため、キャッシュメモリ１０６におけるアクセス頻度の最も高いページのページアクセスの数を表わしているバー２０８は、キャッシュメモリ１０６における２番目にアクセス頻度の高いページについてのページアクセスの数を表わしているバー２１０よりも大きなカウンタ値に対応している。同様に、メインメモリ１０８における２番目にアクセス頻度の低いページのページアクセスの数を表わしているバー２１２は、メインメモリ１０８におけるアクセス頻度の最も低いページのページアクセスの数を表わしているバー２１４よりも大きなカウンタ値に対応している。
【００２９】
特に、バー２１６および２１８は、それぞれ、第１の時間において、キャッシュメモリ１０６における要求頻度の最も低いページ、および、メインメモリ１０８における要求頻度の最も高いページを表わしていることに留意されたい。図示された例においては、バー２１６はバー２１８よりも小さく、このため、キャッシュメモリ１０６における要求頻度の最も低いページへのアクセスが、第１の時間において、メインメモリ１０８における要求頻度の最も高いページへのアクセスよりも、要求が少なかったことを表わしている。
【００３０】
略図３００は略図２００と同様であり、メモリに管理されているカウンタ値およびページ、キャッシュメモリ１０６において管理されるページとメインメモリ１０８において管理されるページとの間の分割線など、を表わす軸を含んでいる。しかしながら、略図３００には略図２００とは顕著に異なる点がある。略図３００において、バー２１６とバー２１８とがスワップされており、これは、キャッシュメモリ１０６とメインメモリ１０８との間における対応ページのスワップを表わしている。言いかえれば、略図３００は、バー２１６によって表わされているページが（たとえばムーバー１１４によって）メインメモリ１０８内に移動されるとともに、バー２１８によって表わされているページが（たとえばムーバー１１４によって）にキャッシュメモリ１０６内に移動されるシナリオを示している。
【００３１】
上述のとおり、略図２００は第１の時間に対応しており、略図３００は第１の時間よりも後の第２の時間に対応している。明瞭にする目的で、図２および図３においては、図示されるバーによって表わされるページへのアクセス要求が第１の時間と第２の時間との間になされていなかったと想定され得る。言いかえれば、略図２００および略図３００に表わされているページについてのカウンタ値は両方の時間においては同じである。しかしながら、第１の時間と第２の時間との間において、移動期間（すなわち、ムーバー１１４がキャッシュメモリ１０６とメインメモリ１０８との間でページをスワップする時間）が発生したと想定される。このため、第１の時間および第２の時間は、それぞれ、移動期間の直前および直後におけるそれぞれの期間を表わし得る。したがって、第１の時間と第２の時間との間において、メモリ・プロファイリングコンピューティングデバイス１０２のためにキャッシュされたページを最適化するために、プロファイリングキャッシュ置換技術がムーバー１１４によって適用される。
【００３２】
図１の例示的なメモリ・プロファイリングコンピューティングデバイス１０２に関して、図４における詳細な例について検討する。メモリ・プロファイリングコンピューティングデバイス１０２は、さまざまなデバイスのうちの１つまたはさまざまなデバイスの組合せであり得る。さまざまなデバイスとして、ここでは、スマートフォン１０２−１、コンピューティングウォッチ１０２−２、デジタルカメラ１０２−３、ラップトップ１０２−４、タブレットコンピュータ１０２−５およびデスクトップコンピュータ１０２−６という６個の例が示されているが、ネットブック、ゲームコンソールまたはセットトップボックスなどの他のコンピューティングデバイスおよびシステムが用いられてもよい。上述のように、いくつかの実施形態においては、当該技術は、少なくとも部分的にリモートコンピューティングデバイスを介して動作する。たとえば、リモートコンピューティングデバイスはサーバとして構成され得る。このような場合、たとえば、コンピューティングを可能にするデータを限定的なコンピューティング動作を行なう通信デバイスを介して通信することによって、または、さらには、コンピューティングを可能にするデータをメモリ・プロファイリングコンピューティングデバイス１０２から直接サーバに通信することによって、ローカルにおいていくらかのコンピューティングを無しにすることもできる。
【００３３】
メモリ・プロファイリングコンピューティングデバイス１０２は、ディスプレイ４０２（図４には５つ示されている）、トランシーバ４０４、１つ以上のプロセッサ４０６およびコンピュータ読取り可能記憶媒体４０８（computer-readable storage media：ＣＲＭ４０８）を含むかまたはこれらと通信することができる。トランシーバ４０４は、ローカルエリア、ワイドエリア、パーソナルエリア、セルラーエリアまたは近距離のネットワークを介して、デバイス１０２から、クライアントアプリケーションデータなどのデータを、直接または通信ネットワークを介して、送受信することができる。
【００３４】
１つ以上の実現例においては、キャッシュメモリ１０６、メインメモリ１０８、プロファイラ１１２、マッパー１１０およびムーバー１１４がＣＲＭ４０８の上で具体化される。キャッシュメモリ１０６はキャッシュされたページ４１０を含み、メインメモリは、メインメモリにロードされたページ（main-memory loaded page）４１２（ＭＭロードされたページ（MM-loaded page）４１２）を含む。プロファイラ１１２は、プロファイラ１１２によって集められた、メモリアクセスについてのメモリアクセス情報４１４を含む。一例として、メモリアクセス情報４１４は、キャッシュされたページ４１０およびＭＭロードされたページ４１２にアクセスする要求の数を示すカウンタを含む。ＣＲＭ４０８はまた、入力アドレスマッピング４１６を含む。入力アドレスマッピング４１６は、（キャッシュメモリまたはメインメモリ内の情報のページにアクセスするためにメモリユーザによって提供されるような）入力アドレスをキャッシュメモリ１０６内のキャッシュされたページ４１０（キャッシュヒット）のうちの１つのページのアドレス、またはメインメモリ１０８内のＭＭロードされたページ４１２（キャッシュミス）のうちの１つのページのアドレス、にマッピングする。
【００３５】
上述のとおり、マッパー１１０は、各々のメモリアクセスのために用いられ、入力アドレスをキャッシュメモリ１０６またはメインメモリ１０８におけるアドレスにマッピングするための機能を表わしている。マッパー１１０が（たとえば、データのページにアクセスすることをメモリに要求するために）入力アドレスを受取ると、マッパー１１０は入力アドレスマッピング４１６を参照し、キャッシュメモリ１０６またはメインメモリ１０８の対応するアドレスを返し得る。
【００３６】
プロファイラ１１２はまた、各々のメモリアクセスとともに用いられる。特に、プロファイラは、キャッシュされたページ４１０およびＭＭロードされたページ４１２へのアクセスの数を追跡する。１つ以上の実現例においては、プロファイラ１１２は、メモリアクセス情報４１４の一部として、キャッシュされたページ４１０毎に、かつＭＭロードされたページ４１２毎に、それぞれのカウンタを管理する。このシナリオにおいては、キャッシュされたページ４１０のうちの１つまたはＭＭロードされたページ４１２のうちの１つにアクセスされると、プロファイラ１１２はアクセスを示すためにそれぞれのカウンタをインクリメントする。しかしながら、いくつかの実現例においては、インクリメント可能なカウンタをキャッシュされたページ４１０毎にかつＭＭロードされたページ４１２毎に管理することは、あまりにも多くのストレージ空間を消費してしまう可能性がある。プロファイラ１１２が８ビットカウンタを用いる場合、メインメモリは４ＧＢであり、ＭＭロードされたページ４１２の各々は４ＫＢであり、たとえば、１ＭＢのメモリは、単に１００万ページ用のカウンタを格納するために用いられる。このことは、たとえば、メモリアクセス情報４１４がスタティック・ランダム・アクセス・メモリ（static random-access memory：ＳＲＡＭ）に格納される場合には、いくつかの実現例においては適していない可能性もある。したがって、プロファイラ１１２は、ストレージ利用がより少なくなる態様でメモリアクセス情報４１４を追跡して管理することができる。プロファイラ１１２は、たとえば、カウンタの範囲を動的に拡張することによって、または、メモリの各ページに対するカウンタの割合が１未満となるように、カウンタストレージ合計を少なくするカウンタを実現してもよい。
【００３７】
動的な拡張によってカウンタストレージの合計を少なくする点では、プロファイラ１１２は、１つ以上のデフォルト実現例においては、８ビットカウンタを用いてもよく、１つ以上の他の実現例においては、動的に拡張するカウンタを用いてもよい。範囲が動的に拡張するカウンタを実現するために、浮動小数点表示を用いることができる。おおまかに言えば、キャッシュメモリ１０６およびメインメモリ１０８内のページのアクセスカウントは高ダイナミックレンジを有しており、たとえば、アクセス頻度の高いページは、アクセス頻度の低いページよりもかなり多くアクセスされ得るとともに、アクセス頻度の高いページのアクセスの数は、システムオペレーション中に増加し続け得る。
【００３８】
動的に拡張するカウンタが採用されている実現例を含む１つ以上の実現例においては、メモリ内のデータは複数セットに分割することができる。言いかえれば、キャッシュされたページ４１０およびＭＭロードされたページ４１２は、各々のセットがキャッシュされたページ４１０のうちのいくつかおよびＭＭロードされたページ４１２のうちのいくつかを含むように、複数セットのページに分割することができる。キャッシュメモリ１０６が１２８ＭＢである続きの例においては、メインメモリ１０８は４ＧＢであり、各々のページは４ＫＢであり、たとえば、ページは、各々のセットが５１２のＭＭロードされたページ４１２および１６のキャッシュされたページ４１０を含むように、複数セットに分割することができる。メモリ内のデータが複数セットに分割されると、ムーバー１１４は、あるセット内のキャッシュされたページ４１０を、そのセットにも存在するＭＭロードされたページ４１２とスワップすることができる。結果として、カウンタをチェックするとき、ムーバー１１４は、この例においては、要求頻度の最も高いページおよび要求頻度の最も低いページを判断するために５１２のカウンタをチェックし得る。しかしながら、ムーバー１１４は、当該セット内のキャッシュされたページ４１０を、他のセットからのＭＭロードされたページ４１２とスワップすることはない。
【００３９】
動的に拡張するカウンタの実現例においては、プロファイラ１１２は、ページのセットの各々毎に共通スケールＳを管理し得るとともに、或るセットにおける各ページごとにＮ−ビットカウンタＣを管理し得る。一例として、プロファイラは、６ビットを用いる１セットのページのために共通スケールＳを実現することができる。おおまかに言えば、プロファイラ１１２は、ページが複数セットに分割されると共通スケールを用いることができる。なぜなら、カウンタ値が或るセットの範囲内で比較されるからであり、たとえば、単に、同じセットにあるキャッシュメモリ１０６およびメインメモリ１０８内の複数ページだけがスワップされるからである。共通スケールＳおよびＮ−ビットカウンタＣを有しているので、プロファイラ１１２は、それらの値がＣ×２Ｓに等しくなるように、カウンタを管理することができる。
【００４０】
【数１】
0006613375.tif 000002
動的に拡張するカウンタのための方式が採用されているシナリオについて検討する。プロファイラ１１２はさまざまな異なる方法で各々のカウンタ値を格納することができる。たとえば、プロファイラ１１２はＣ（Ｃは単に２進整数である）に等しいカウンタ値を格納することができる。プロファイラ１１２はまた、Ｃ×２Ｓに等しいカウンタ値を格納することができる。この場合もＣは２進整数である。プロファイラ１１２はまた、Ｃについて単純な浮動小数点表示を用いて、個々のカウンタのダイナミックレンジを増やすことができる。プロファイラ１１２によって格納されたカウンタ値は、依然として、Ｃ×２Ｓに等しくなり得るが、プロファイラ１１２は、以下のようにＣを符号化することができる。
【００４１】
Ｃ＝Ｋ×２Ｅ
ここで、項Ｋは、その有効数字から成る浮動小数点数の一部である仮数（significand）を表わしており、項Ｅは、基数（２が基数である）の指数を表わしている。このように想定すれば、最終的なカウンタ値は以下のとおりとなる。
【００４２】
Ｋ×２Ｅ＋Ｓ
仮に、このシナリオにおいて、プロファイラ１１２が（０〜１５の範囲にわたる値になり得るように）４ビット仮数Ｋと（０〜７の範囲にわたる値になり得るように）指数のために３ビットとを用いていると想定した場合、７ビットカウンタＣは、［０，１５×２７］の範囲内のページアクセス値を表わし得る。
【００４３】
動的に拡張するカウンタを採用するための代替的シナリオについて検討する。この代替的シナリオにおいては、プロファイラ１１２は、異なる態様で個々のカウンタＣを符号化する。特に、符号化は、この明細書中においてｎＫとして表わされている仮数Ｋのために割当てられたビットの数と、この明細書中においてｎＥとして表わされている指数Ｅのために割当てられたビットの数とに依存している。指数Ｅが０に等しい場合、プロファイラ１１２は、Ｃ＝Ｋとなるように仮数Ｋに等しくなるように、単に、カウンタＣの値を符号化するだけである。しかしながら、指数Ｅがゼロよりも大きい場合、プロファイラ１１２は、以下のように、カウンタＣの値を符号化する。
【００４４】
Ｃ（Ｋ＋２ｎＫ）＝２Ｅ−１
仮に、この代替的シナリオにおいて、仮数ｎＫのために割当てられたビットの数が４ビットであるとともに指数ｎＥのために割当てられたビットの数が３ビットであると想定した場合、カウンタは［０，１９８４］の範囲の値を格納することができる。上述のとおり、個々のカウンタのサイズを（ビット数の観点から）小さくすることに加えて、いくつかの機密情報のストレージに係る実現例においては、カウンタの数を、たとえば、メモリの１ページ毎に１つのカウンタから、メモリの各ページに対するカウンタの割合が１未満になるまで減らすこともできる。
【００４５】
メモリの各ページに対して用いられるカウンタの割合を１未満にすることに関して、これは、共通のワークロードとともにメモリユーザ（たとえばクライアントアプリケーション）によって用いられるデータのワーキングセットが、メインメモリ１０８のサイズと等しくなることまたはメインメモリ１０８のサイズを上回ることが起こりそうにないという所見に基づいている。さらに、プロファイリングキャッシュ置換は、単にページにアクセスすることが要求されているという理由で単にページをキャッシュメモリ１０６にキャッシュするのではなく、メインメモリ１０８のうち要求頻度の高いページをキャッシュメモリ１０６にキャッシュすることを伴っているので、メインメモリ１０８内でめったに要求されなかったページへのアクセスの数は、この明細書中に記載される技術にはほとんど関連していない。したがって、プロファイラ１１２は、より頻繁にアクセスされるページについてのカウンタを管理し得る。
【００４６】
キャッシュメモリ１０６およびメインメモリ１０８内のページを追跡するのに用いられるカウンタの数を減らすために、タグを用いて、カウンタの各々が関連付けられているページを識別してもよい。カウンタに関連付けられているページへのアクセスが要求されると、プロファイラ１１２は、アクセスを示すために上述の態様のうち１つの態様でカウンタを更新する。しかしながら、カウンタに関連付けられていないページ（たとえば、カウンタによってその時点でアクセスが追跡されていないページ）へのアクセスが要求されると、カウンタのうち、異なるページへのアクセスを追跡するために既に用いられている１つのカウンタが、異なるページとの関連付けが切離されて、要求されていたが予め関連付けられていなかったページと関連付けられる可能性がある。
【００４７】
追跡されたページとのカウンタの関連付けを切離して、それらカウンタを要求されていたが予め関連付けられていなかったページに関連付けるためのいくつかの従来の技術は、スラッシングを引起こす可能性がある。１つ以上の実現例においては、プロファイリングキャッシュ置換は、追跡されたページとのカウンタの関連付けを切離し、これらカウンタを要求されていたが予め関連付けられていなかったページに関連付けるために、１つ以上の変更済みカウンタタグ付け技術を適用することを伴っている。これらの変更済みカウンタタグ付け技術は、従来の技術と比べて、スラッシングを減らすことができる。
【００４８】
プロファイラ１１２は、カウンタＮの数をメモリアクセス情報４１４の一部として管理することにより、変更済みカウンタタグ付け技術を適用する。各々のカウンタは、カウンタが関連付けられているページを識別するページタグを表わすデータ対と、たとえば｛ｐａｇｅ，ｃｏｕｎｔ｝の形式でページに関連付けられたカウントとを含む。特定のページＸへのアクセスが要求されると、プロファイラ１１２は、特定のページＸに関連付けられたカウンタ｛Ｘ，Ｃ｝が存在しているかどうかをチェックする。特定のページＸに関連付けられたカウンタが存在している場合、たとえば｛Ｘ，Ｃ｝が存在している場合、プロファイラ１１２はカウントＣを１だけインクリメントする。特定のページＸを関連付けられたカウンタが存在していない場合、プロファイラ１１２は、最小のカウントＣを有するページＹについてのカウンタ｛Ｙ，Ｃ｝を見つけ出す。プロファイラ１１２は、次いで、カウンタの値を置換し、これにより、それが特定のページＸに関連付けられて、特定のページＸへの１回のアクセスを示すようにする。たとえば、プロファイラは、｛Ｙ，Ｃ｝〜｛Ｘ，１｝の値の対を調整する。これは、先のカウントを引継ぐ従来の技術とは異なっている。言いかえれば、変更済みカウンタタグ付け技術が行なっているようにＣを１と置換するのではなく、従来の技術はＣをＣ＋１と置換する。変更済みカウンタタグ付け技術を用いてページアクセスをカウントすることにより、最大カウントを有するいくつかのカウンタＮは上位ｎのページに対応する。
【００４９】
カウンタがどのように実現されているかに関わらず、ムーバー１１４は、メインメモリ１０８とキャッシュメモリ１０６との間でページをスワップするべきかどうか判断するためにメモリアクセス情報４１４において管理されるカウンタをチェックするための機能を表わす。上述のとおり、ムーバー１１４は、毎マイクロ秒（１μｓ）毎などの、予め定められた時間間隔でページのスワップを開始すべきとの判断を行なうためにこれらのチェックを実行する。この明細書中に記載される例は、予め定められているとともに１μｓに対応する時間間隔を指しているが、この時間間隔は、この明細書中に記載される技術の精神または範囲から逸脱することがなければ異なっていてもよい。一例として、予め定められた間隔はまた、以下により詳細に説明されるように、アクセスの数（たとえば、プロファイルされたメモリ１０４からのページに対して要求されたアクセスの総数）などに基づいて、ランダムに判断することができる。
【００５０】
予め定められた時間間隔で（各マイクロ秒毎に）、ムーバー１１４は、この明細書中に記載される技術に従って判断を行なうことができる。絶対時間（たとえば、予め定められた時間間隔）を用いるのではなく、ムーバー１１４は、代替的には、ページのセット毎にすべてのＮメモリアクセスについて判断を行なうことができる。このようにして、この明細書中に記載される技術は、使用されるバックグラウンド帯域幅の絶対値ではなく、使用されるバックグラウンド帯域幅の百分率を制御することができる。
【００５１】
頻度に関わらず、移動期間中、ムーバー１１４は、メインメモリ１０８のうち要求頻度の高いページが、キャッシュメモリ１０６における要求頻度の低いページよりも多く要求されているかどうかを判断するように構成されている。メインメモリ１０８のうち要求頻度の高いページは、ＭＭロードされたページ４１２に比べて要求頻度が高く、キャッシュメモリ１０６における要求頻度の低いページは、キャッシュされたページ４１０に比べて要求頻度が低い。しかしながら、要求頻度の高いメインメモリページに対する要求の数は、要求頻度の低いキャッシュメモリページに対する要求の数と実質的に同様であってもよい。
【００５２】
メインメモリ１０８における要求頻度の高いページが、キャッシュメモリ１０６における要求頻度の低いページよりも多く要求される場合、ムーバー１１４は、メインメモリ１０８のうち要求頻度の高いページを、キャッシュメモリ１０６のうち要求頻度の低いページとスワップする。そうするために、ムーバー１１４は、要求頻度の低いページをキャッシュメモリ１０６から追出して、メインメモリのうち要求頻度の高いページをキャッシュメモリ１０６に書込む。ムーバー１１４の動作がメモリユーザ（たとえばクライアントアプリケーション）からのデマンド要求と競合しているので、ムーバー１１４の判断する動作およびスワップする動作の実行を移動期間に制限することにより、ムーバー１１４のメモリユーザに対する影響を小さくする。すなわち、メモリ・プロファイリングコンピューティングデバイス１０２についてのメモリアクセスの待ち時間を少なくする。こうして、ムーバー１１４がバックグラウンドにおいて動作する一方で、メモリユーザは、キャッシュメモリ１０６およびメインメモリ１０８からデータのページにアクセスする。
【００５３】
ムーバー１１４の動作をバックグラウンドに制限することに加えて、メモリユーザによってなされるページアクセス要求は、メモリを最適化する目的でなされるページアクセス要求（たとえば、ムーバー１１４によって要求されるページスワップ）よりも優先される。キャッシュメモリ１０６およびメインメモリ１０８からデータのページにアクセスするためになされた要求は、概して、２つのタイプのデマンド要求およびバックグラウンド要求に分割することができる。「デマンド要求」という語は、キャッシュメモリ１０６またはメインメモリ１０８からのデータのページに対するクライアントアプリケーションなどのメモリユーザによってなされる要求を指している。「バックグラウンド要求」という語は、メインメモリ１０８とキャッシュメモリ１０６との間におけるページのスワップとともに、ムーバー１１４によってなされる書込み要求および追出し要求などの、デマンド要求によって間接的にトリガされる書込み要求または追出し要求を指している。
【００５４】
この明細書中に記載される技術は、２、３の方法でバックグラウンド要求を果たすよりも、デマンド要求を果たすことを優先させている。第１に、当該技術は、制限された数のペンディングのバックグラウンド要求を保持するように構成されたキューにおいてペンディングの要求を管理することなどによって、ペンディングのバックグラウンド要求の数を制限することを可能にし得る。バックグラウンド要求がなされたときにキューが満杯であれば、その要求は単に断念され、たとえば、その要求はキューに追加されない。実際には、満杯のキューにおけるペンディングのバックグラウンド要求の少なくとも１つが供給されるまで、他のバックグラウンド要求はキューに追加されない。
【００５５】
この明細書中に記載される技術が、バックグラウンド要求を果たすことよりもデマンド要求を果たすことを優先させている第２の方法は、ダイナミックランダムアクセス・メモリ（dynamic random-access memory：ＤＲＡＭ）要求キューが用いられているとともに、バックグラウンド要求が制限された量（たとえば半分）のＤＲＡＭ要求キューを書込むことが可能となっている実現例を含んでいる。たとえば、ＤＲＡＭ要求キューの書込みレベルがキューの最大書込みレベルの半分を上回っている場合、この明細書中に記載される技術によって、入ってくる要求がデマンド要求に制限される。この場合、ＤＲＡＭ要求キューの書込みレベルがキューの最大書込みレベルの半分を上回っていれば、バックグラウンド要求を止めることができる。たとえば、ムーバーによって要求されたバックグラウンド要求があまりにも多くペンディング中であれば、ムーバー１１４によって開始されたバックグラウンド要求は断念される。それにもかかわらず、ムーバー１１４によって開始されたが断念されていないバックグラウンド要求は、ＤＲＡＭ要求に分解されて、ＤＲＡＭ要求キューに送信される。ＤＲＡＭ要求キューが特定のしきい値（たとえば、キューの最大書込みレベルの半分）を越えている場合、これは、ＤＲＡＭ要求キューが入来ＤＲＡＭ要求をその時点で処理するにはあまりにもビジーであることを示しており、さらなるバックグラウンド要求がＤＲＡＭ要求キューに送信されなくなる。代わりに、ＤＲＡＭ要求キューレベルがしきい値よりも低くなるまで、バックグラウンドＤＲＡＭ要求が保持される。ＤＲＡＭ要求キューが再びバックグラウンドＤＲＡＭ要求を処理することができるようになれば、保持された要求がＤＲＡＭ要求キューに送信される。
【００５６】
動作中に、メモリユーザがプロファイルされたメモリ１０４に課すワークロードは時間とともに変化し得る。ワークロードの変化とともに、要求頻度の高いページも変化し得る。言いかえれば、１つのクライアントアプリケーションが動作している間にメインメモリ１０８にキャッシュされて頻度高く要求されたページは、別のクライアントアプリケーションが動作している間にメインメモリ１０８にキャッシュされて頻度高く要求されたページとは同じではないかもしれない。メモリ・プロファイリングコンピューティングデバイス１０２のその時点の動作に対応するページでキャッシュメモリ１０６が書込まれることを確実にするために、プロファイラ１１２は、ページカウンタの値を低減させることができる。いくらかの低減間隔でカウンタ値を自動的に低減させることによって、以前は頻度高くアクセスされていたページを、それらの使用が少なくなったときに、キャッシュメモリ１０６から追出すことができる。
【００５７】
１つ以上の実現例においては、プロファイラ１１２は、単に、或るセットのカウンタ値の各々を、低減間隔で半分に分割することができる。低減間隔が或るセットにおける複数ページに対して要求されたアクセスの総数（たとえば、２１４のアクセス）についての所定のしきい値に対応している例について検討する。この例においては、或るセットにおける複数ページに対するアクセスの総数が２１４のアクセスを上回ると、プロファイラ１１２は、当該セットのカウンタ値を２で分割する。共通スケールＳを用いる実現例を再び参照すると、プロファイラ１１２は、或るセットの共通スケールＳが０よりも大きい場合、当該セットの共通スケールＳを１だけ小さくすることによって、カウンタを低減させる。しかしながら、当該セットの共通スケールＳが既に０であれば、プロファイラ１１２は、当該セットのカウンタの各々を２で分割する。さらに他の実現例においては、低減間隔は、定義済みのアクセスの数ではなく、何らかの予め定められた絶対時間に対応している。カウンタが、この明細書中に記載される技術の精神または範囲から逸脱することなく、２で分割される以外の態様で低減され得ることが認識されるはずである。一例として、カウンタは、２で分割されるのではなく、３分の２（２／３）などの係数が乗じられてもよい。
【００５８】
さらに、メモリ・プロファイリングコンピューティングデバイス１０２の動作中に生じるさらなるシナリオに関して、いくつかの場合、キャッシュメモリ１０６のうち要求頻度の低いページのためのカウンタと、メインメモリ１０８のうち要求頻度の高いページのためのカウンタは、同じ値または非常に類似した値を有し得る。１セットのページを参照して、当該セットのうち（他のキャッシュされたページと比べて）要求頻度の低いキャッシュされたページと、メインメモリ１０８のうち当該セットの要求頻度の高いページとは、同じ値または非常に類似した値を有し得る。キャッシュされたページが、キャッシュされるべき候補であるページに類似したカウンタ値を有している場合に、どのページをキャッシュするべきかをムーバー１１４が判断するときに、問題が生じる可能性がある。或るセットの第１のページが当該セットの他のページよりもわずかに多くアクセスされる例について検討する。より多くアクセスした結果、ムーバー１１４は第１のページをキャッシュすることができる。しかしながら、当該セットの第２のページが後に第１のページよりもわずかに多くアクセスされる場合についても検討する。後にアクセスした結果、ムーバー１１４は、第１のページを第２のページと置換し、これにより、キャッシュメモリ１０６から第１のページを追出す。周期的に参照されている１セットのページにおいては、第１のページがわずかにより多くアクセスされていることによっても、ムーバー１１４に、キャッシュメモリ内の第２のページの置換などを実行させることができる。このシナリオは、これらのページに対するスラッシングを引起こす可能性があり、カウンタの低減が用いられるとともに低減間隔が短い場合には、特に問題となる可能性がある。
【００５９】
このようなスラッシングを防ぐために、ムーバー１１４は、メインメモリ１０８のうち要求頻度の高いページをキャッシュメモリ１０６のうち要求頻度の低いページとスワップするべきと判断する前に、エントリのバリアを追加することができる。このように、要求頻度の高いメインメモリページの要求されたアクセス数が、要求頻度の低いキャッシュされたページの要求されたアクセス数よりも大きい場合は常に、メインメモリ１０８のうち要求頻度の高いページをキャッシュメモリ１０６のうち要求頻度の低いページとスワップするのではなく、要求頻度の高いメインメモリページの要求されたアクセス数が要求頻度の低いキャッシュされたページのアクセス数およびエントリバリアよりも大きい場合に、ムーバー１１４は、ページをスワップするべきと判断することができる。一例として、ムーバー１１４は、以下が当てはまる場合、ページをスワップするべきと判断することができる。
【００６０】
AccessCount（ＭＭページ多）＞（AccessCount（ＣＭページ少）＋Δ）
この式においては、Δは、エントリバリアを表わしており、ページをスワップするためのリソースコスト（たとえば時間、パワーなど）をオフセットする整数などの予め定められた整数に対応し得る。
【００６１】
プロファイリングキャッシュ置換は、この明細書中に記載される技術の精神または範囲から逸脱することなく、さらに他の方法で実現され得る。代替的実現例の一例は、時間多重化されたカウンタを用いることである。アクセス頻度の最も高いページについてのみカウンタを管理するのではなく、プロファイラ１１２は、ページの各々についてカウンタを管理することができる。しかしながら、いずれの所与の時間においても、プロファイラ１１２は制限された数のカウンタにアクセスし得る。カウンタの１６分の１がＳＲＡＭにおいて管理されており、他の１６分の１５がＤＲＡＭにおいて管理されているシナリオについて検討する。カウンタがＳＲＡＭにあるページへのアクセスが要求されると、プロファイラ１１２は単純にカウンタをインクリメントする。しかしながら、カウンタがＤＲＡＭにあるページへのアクセスが要求されると、プロファイラ１１２は要求を無視する。これらの時間多重化カウンタ技術は、周期的に、ＳＲＡＭにおけるカウンタをＤＲＡＭにまでフラッシュし、カウンタのうちの別の１６分の１をＤＲＡＭからＳＲＡＭにロードする。いくらかの期間にわたってこれを行なうことにより、各カウンタが実際のアクセスカウント値の約１６分の１を有することとなると想定されている。ムーバー１１４は、ＤＲＡＭおよびＳＲＡＭの両方におけるカウンタをチェックするように構成され得る。
【００６２】
代替的な実施形態の別の例は、ページテーブルデータ構造でカウンタをバンドルすることである。これにより、別個のカウンタを管理するのではなく、プロファイラ１１２は、ページテーブルデータ構造でカウンタをバンドルすることができる。これを行なう際に、カウンタの管理は、ページテーブルおよびトランスレーション・ルックアサイド・バッファ（translation lookaside buffer：ＴＬＢ）と同じフローに追従し得る。代替的実施形態のさらに別の例においては、カウンタの低減は、共通スケールＳを徐々に小さくすることによって結果として分数Ｓをもたらすことにより、実現されてもよい。予め定められた低減間隔で各々のカウンタ値を低減させるのではなく、表わされたカウンタ値は、共通スケールＳを徐々に小さくすることによって徐々に低減させることができる。
【００６３】
これらおよび他の機能、ならびに図１および図４のエンティティが作用および相互作用する方法が、以下においてさらにより詳細に記載される。これらのエンティティはさらに、分割、組合わせ等がなされてもよい。図１の環境１００および図４の詳細な具体例は、説明された技術を採用することができる多くの実現可能な環境のうちのいくつかを示す。
【００６４】
例示的な方法
図５〜図７は、プロファイリングキャッシュ置換を可能にするかまたは用いる方法を示している。これらの方法は、実行される動作を指定するブロックのセットとして示されているが、それぞれのブロックによって動作を実行するために示された順序または組合せに必ずしも制限されるものではない。以下の説明部分においては、図１の環境１００および図４に詳述されるエンティティが参照され得るが、この参照は単に例示のためになされているに過ぎない。当該技術は、１つのデバイス上で動作する１つのエンティティまたは複数のエンティティによる動作に限定されるものではない。
【００６５】
図５が示す方法５００は、キャッシュメモリとメインメモリとの間におけるデータ移行を管理するのに用いられるプロファイリングアルゴリズムに従ってキャッシュメモリ内のページを置換するための態様を説明している。
【００６６】
５０２において、メインメモリおよびキャッシュメモリにおいて管理されるデータのページに関連付けて管理されるカウンタが更新される。カウンタは、メインメモリおよびキャッシュメモリにおいて管理されるページにアクセスする要求の数を示すように構成されている。一例として、プロファイラ１１２はメモリアクセス情報４１４におけるカウンタを管理する。これらのカウンタは、キャッシュされたページ４１０およびＭＭロードされたページ４１２にアクセスする要求の数を示す。キャッシュされたページ４１０のうちの１つまたはＭＭロードされたページ４１２のうちの１つにアクセスする要求に応じて、たとえば、プロファイラ１１２は、メモリアクセス情報４１４における対応するカウンタをインクリメントする。
【００６７】
クライアントアプリケーションなどのメモリユーザのメモリアクセスに干渉しないようにするために、プロファイリングメモリ置換は、キャッシュメモリ１０６およびメインメモリ１０８において管理されるページについてメモリによってなされた要求を供給するバックグラウンドにおいて実行される。これを行なう際に、方法ステップ５０４および５０６の実行は、マイクロ秒（μｓ）毎などの予め定められた時間間隔での実行に制限することができる。５０４において、メインメモリのうち要求頻度の高いページに対するページアクセス要求の数が、キャッシュメモリのうち要求頻度の低いページに対するページアクセス要求の数よりも大きいかどうかについて、カウンタに従って、予め定められた時間間隔で判断がなされる。メインメモリのうち要求頻度の高いページは、メインメモリにロードされたページに比べて要求頻度が高く、キャッシュメモリのうち要求頻度の低いページは、キャッシュメモリにロードされたページに比べて要求頻度が低い。しかしながら、要求頻度の高いメインメモリページについての要求の数は、要求頻度の低いキャッシュメモリページについての要求の数と実質的に類似している可能性がある。
【００６８】
一例として、ムーバー１１４は、メモリアクセス情報４１４においてプロファイラ１１２によって管理されるカウンタをチェックする。たとえば、マイクロ秒毎に、ムーバー１１４は、カウンタに従って、要求頻度の低いキャッシュされたページ４１０（たとえば、キャッシュメモリ１０６内の他のページよりも要求が少ない）と、要求頻度の高いＭＭロードされたページ４１２（たとえば、メインメモリ１０８内の他のページよりも要求が多い）とを判断する。ムーバー１１４は、メインメモリ１０８のうち要求頻度の高いページがキャッシュメモリ１０６のうち要求頻度の低いページよりも多く要求されているかどうかを判断するために、それぞれのカウンタ値を比較する。
【００６９】
５０６において、要求頻度の高いメインメモリページについてのページアクセス要求の数が、要求頻度の低いキャッシュメモリページについてのページアクセス要求の数よりも大きいと判断したことに応じて、要求頻度の高いメインメモリページと要求頻度の低いキャッシュメモリページとがスワップされる。一例として、ムーバー１１４は、ステップ５０４において、メインメモリ１０８からの要求頻度の高いページが、キャッシュメモリ１０６のうち要求頻度の低いページよりも多く要求されていると判断する。この判断に応じて、ムーバー１１４は、メインメモリ１０８からの要求頻度の高いページをキャッシュメモリ１０６のうち要求頻度の低いページとスワップする。言いかえれば、ムーバー１１４は、要求頻度の低いキャッシュメモリページをキャッシュメモリ１０６から追出し、そのページをメインメモリ１０８にロードする。ムーバー１１４はまた、要求頻度の高いメインメモリページをキャッシュする。
【００７０】
図６が示す方法６００は、プロファイリングキャッシュ置換のために縮小空間カウンタを用いてページアクセスがカウントされる態様を説明する。
【００７１】
６０２において、共通スケールがメモリ内の複数セットのページに対して管理される。一例として、プロファイルされたメモリ１０４において管理されるデータは、各々のセットが、キャッシュメモリ１０６からの複数のページおよびメインメモリ１０８からの複数のページを含むように、複数セットのページに分割される。特に、ページは、さらにより詳細に上述されたように複数セットに分割することができる。データの各セットごとに、プロファイラ１１２は、共通スケールＳを管理する。これは、当該セットのページについてのアクセスのベースカウントまたはベース数を示す。１つ以上の実現例においては、プロファイラ１１２は、ページのセットの各々毎に４ビットの共通スケールを管理する。（ビット数の点で）異なるサイズの共通スケールが、この明細書中に記載されている技術の精神または範囲から逸脱することなく使用され得ることが認識されるはずである。
【００７２】
６０４において、カウンタは、或るセットにおけるページの各々に対して管理され、これは、当該セットにおける他のページに対するページアクセスの数を示している。一例として、プロファイラ１１２は、さらに詳細に上述されたように、或るセット内の各ページごとにＮ−ビットカウンタを管理する。或るページについてのＮ−ビットカウンタは、そのページのセットの共通スケールＳとともに、そのページについてのアクセスの数を示す。６０６において、ページにアクセスする要求に応じて、対応するカウンタおよび共通スケールがアクセスに応じて更新される。一例として、ページにアクセスする要求に応じて、プロファイラ１１２は、要求されたページに関連付けられたＮ−ビットカウンタを更新し、要求されたページのセットに関連付けられた共通スケールＳを更新する。プロファイラ１１２は、より詳細に上述されているように、Ｎ−ビットカウンタおよび共通スケールＳを更新する。たとえば、メモリアクセス情報４１４がＳＲＡＭに格納されたときに、この明細書中に説明された技術が１つ以上の機密情報のストレージに係る実現例において方法６００を利用できることが認識されるはずである。
【００７３】
図７が示す方法７００は、メモリの各ページに対して１未満となる割合で設けられたカウンタを用いて、ページアクセスがプロファイリングキャッシュ置換のためにカウントされる態様を説明する。方法６００と同様に、方法７００も１つ以上の機密情報のストレージに係る実現例のために利用することができる。
【００７４】
７０２において、ｎ個のカウンタが、メモリ内で上位ｎ個のアクセスされたページに関連付けられる。一例として、プロファイラ１１２は、ｎ個のカウンタを、プロファイルされたメモリ１０４内の上位ｎ個のアクセスされたページに関連付ける。特に、カウンタは、プロファイルされたメモリ１０４のうちキャッシュされたページに関連付けられており、残りのカウンタは、メインメモリ１０８において次にアクセス頻度が最も高いページに関連付けられたままにされる。
【００７５】
７０４において、メモリにおいて管理されるページにアクセスする要求が受取られる。一例として、キャッシュされたページ４１０のうちの１つまたはＭＭロードされたページ４１２のうちの１つにアクセスするようになどの、プロファイルされたメモリ１０４に管理されるデータのページにアクセスする要求が受取られる。７０６において、要求されたページがカウンタのうちの１つに関連付けられているかどうか、たとえば、カウンタのうちの１つが、要求されたページを識別する属性を有しているかどうか、についての判断がなされる。一例として、プロファイラ１１２は、要求されたページが、カウンタのうちメモリアクセス情報４１４の一部として管理されている１つのカウンタに関連付けられているかどうかを判断する。
【００７６】
要求されたページがカウンタのうちの１つに関連付けられていると判断された場合（たとえば７０６において「ＹＥＳ」）、７０８において、要求されたページに関連付けられたカウンタが更新される。一例として、プロファイラ１１２は、要求されたページに関連付けられたカウンタについてのカウンタ値Ｃを、ＣからＣ＋１にインクリメントする。しかしながら、要求されたページがカウンタのうちの１つに関連付けられていないと判断された場合（たとえば、７０６において「ＮＯ」）、７１０において、カウンタに関連付けられたアクセス頻度の最も低いページが判断される。一例として、プロファイラ１１２は、要求されたページと同じセットのページにおけるカウンタに関連付けられたアクセス頻度の最も低いページを判断する。代替的には、プロファイラ１１２は、単に、カウンタに関連付けられたページのうちアクセス頻度の最も低いページを判断する。プロファイラ１１２は、カウンタのカウンタ値をチェックすることによってアクセス頻度の最も低いページを判断することができる。
【００７７】
７１２において、アクセス頻度の最も低いページのカウンタが、要求されたページに関連付けられる。一例として、プロファイラ１１２は、カウンタとのアクセス頻度の最も低いページの関連付けを切離し、次いで、たとえば、要求されたページを識別するためにカウンタのタグを変更することによって、当該カウンタを要求されたページに関連付ける。７１４において、カウンタのカウンタ値がアクセス要求を反映するように調整される。一例として、プロファイラ１１２は、カウンタ値を１に設定することによって、（カウンタに予め関連付けられたページのアクセスの数を示す）カウンタ値Ｃを調整する。カウンタ値を１に設定することは、カウンタ値ＣをＣ＋１に設定することを含むいくつかの従来の技術とは対照をなしている。これを行なう際に、方法７００はスラッシングを減らすことができる。
【００７８】
上述の説明は、プロファイリングキャッシュ置換に関する方法を記載している。これらの方法の局面は、ハードウェア（たとえば固定論理回路）、ファームウェア、ソフトウェア、手動処理またはこれらのいずれかの組合せで実現されてもよい。これらの技術は、さらに分割、組合せなどがなされ得る図１〜図４および図８（コンピューティングシステム８００は以下の図８に説明されている）に示されるエンティティのうち１つ以上のエンティティ上で具体化されてもよい。これにより、これらの図は、記載された技術を用いることができる多くの実現可能なシステムまたは装置のうちのいくつかを示す。これらの図のエンティティは、一般に、ソフトウェア、ファームウェア、ハードウェア、デバイス全体もしくはネットワーク、またはそれらの組合せを表わす。
【００７９】
例示的なコンピューティングシステム
図８は、プロファイリングキャッシュ置換を実現するために、上述の図１〜図７に関して記載された如何なるタイプのクライアント、サーバおよび／またはコンピューティングデバイスとしても実現することができる例示的なコンピューティングシステム８００のさまざまな構成要素を示す。いくつかの実施形態においては、コンピューティングシステム８００は、無線および／もしくは有線のウェアラブルデバイス、システム・オン・チップ（System-on-Chip：ＳｏＣ）、ならびに／または別のタイプのデバイスもしくはその一部として実現することができる。コンピューティングシステム８００はまた、デバイスがユーザ、ソフトウェア、ファームウェア、および／または、デバイスの組合せを含む論理デバイスを表わすように、当該デバイスを動作させるユーザ（たとえば人）および／またはエンティティに関連付けられてもよい。
【００８０】
コンピューティングシステム８００は、デバイスデータ８０４（たとえば受信されたデータ、受信されているデータ、同報通信されるようスケジュールされたデータ、データのデータパケットなど）の有線および／または無線通信を可能にする通信デバイス８０２を含む。デバイスデータ８０４または他のデバイスコンテンツは、デバイスの構成設定、デバイスに格納された媒体コンテンツ、および／または、デバイスのユーザに関連付けられた情報を含み得る。コンピューティングシステム８００に格納された媒体コンテンツは、プロファイリングキャッシュ置換動作の複雑な結果または詳細な結果を含む如何なるタイプの音声データ、映像データおよび／または画像データをも含み得る。コンピューティングシステム８００は１つ以上のデータ入力８０６を含む。１つ以上のデータ入力８０６を介して、如何なるタイプのデータ、媒体コンテンツおよび／または入力（たとえば、ヒトの発言、ユーザ選択可能な入力（明示的もしくは暗示的）、メッセージ、音楽、テレビ媒体コンテンツ、記録された映像コンテンツ、ならびに、任意のコンテンツおよび／もしくはデータソースから受信された他の任意のタイプの音声データ、映像データおよび／もしくは画像データなど）をも受信することができる。
【００８１】
コンピューティングシステム８００はまた通信インターフェイス８０８を含む。通信インターフェイス８０８は、シリアルおよび／またはパラレルインターフェイス、無線インターフェイス、任意のタイプのネットワークインターフェイス、モデムのうちのいずれか１つ以上として、ならびに、他の任意のタイプの通信インターフェイスとして実現することができる。通信インターフェイス８０８は、コンピューティングシステム８００と通信ネットワークとの間に接続および／または通信リンクをもたらし、これにより、他の電子デバイス、コンピューティングデバイスおよび通信デバイスがコンピューティングシステム８００とデータをやりとりする。
【００８２】
コンピューティングシステム８００は、１つ以上のプロセッサ８１０（たとえば、マイクロプロセッサ、コントローラなどのいずれか）を含む。１つ以上のプロセッサ８１０は、さまざまなコンピュータ実行可能命令を処理して、コンピューティングシステム８００の動作を制御し、プロファイリングキャッシュ置換のための技術を可能にするかまたはプロファイリングキャッシュ置換が具体化され得る技術を可能にする。代替的には、または、付加的には、コンピューティングシステム８００は、８１２において概略的に特定される処理および制御回路とともに実現されるハードウェア、ファームウェアまたは固定論理回路のうちのいずれか１つまたはこれらの組合せを用いて実現され得る。図示されていないが、コンピューティングシステム８００は、デバイス内のさまざまな構成要素を連結するシステムバスまたはデータ転送システムを含み得る。システムバスは、さまざまなバスアーキテクチャのいずれかを利用するメモリバスもしくはメモリコントローラ、周辺バス、ユニバーサル・シリアル・バス、および／またはプロセッサもしくはローカルバスなどのさまざまなバス構造のうちのいずれか１つまたはこれらの組合せを含み得る。
【００８３】
コンピューティングシステム８００はまた、プロファイルされたメモリ１０４に加えて、１つ以上のメモリデバイスなどのコンピュータ読取り可能媒体８１４を含む。コンピュータ読取り可能媒体８１４は、たとえば、永続的および／または非一時的なデータストレージ（すなわち単なる信号送信とは対照的）を可能にするものであって、それらの例として、ランダムアクセスメモリ（random access memory：ＲＡＭ）、不揮発性メモリ（たとえば、読取専用メモリ（read-only memory：ＲＯＭ）、フラッシュメモリ、ＥＰＲＯＭ、ＥＥＰＲＯＭなどのうちいずれか１つ以上）、およびディスク記憶装置を含む。ディスク記憶装置は、ハードディスクドライブ、記録可能および／または書換え可能なコンパクトディスク（compact disc：ＣＤ）、任意のタイプのデジタルバーサタイル・ディスク（digital versatile disc：ＤＶＤ）などの、任意のタイプの磁気または光学記憶装置として実現され得る。コンピューティングシステム８００はまた、大容量記憶媒体装置８１６を含み得る。この例においては、コンピュータ読取り可能媒体８１４はまたプロファイルされたメモリ１０４を含む。
【００８４】
コンピュータ読取り可能媒体８１４はデータ記憶機構を備える。データ記憶機構は、デバイスデータ８０４、さらにはさまざまなデバイスアプリケーション８１８、および他の如何なるタイプの情報、ならびに／または、コンピューティングシステム８００の動作局面に関するデータを格納するためのものである。たとえば、オペレーティングシステム８２０は、コンピュータ読取り可能媒体８１４でコンピュータアプリケーションとして維持され、プロセッサ８１０上で実行され得る。デバイスアプリケーション８１８は、任意の形態の制御アプリケーション、ソフトウェアアプリケーション、信号処理および制御モジュール、特定のデバイスに特有のコード、特定のデバイスのためのハードウエア・アブストラクション・レイヤなどのデバイスマネージャを含み得る。
【００８５】
デバイスアプリケーション８１８はまた、当該技術を実現するための如何なるシステムコンポーネント、エンジンまたはマネージャをも含む。
【００８６】
結論
プロファイリングキャッシュ置換を用いる技術およびプロファイリングキャッシュ置換を可能にする装置の実施形態を、特徴および／または方法に特有の用語で説明してきたが、添付の特許請求の主題が、記載された具体的特徴または方法に必ずしも限定されないことが理解されるべきである。むしろ、具体的な特徴および方法はこれらの技術の実現例として開示されている。
【図１】
0006613375.tif 000003
【図２】
0006613375.tif 000004
【図３】
0006613375.tif 000005
【図４】
0006613375.tif 000006
【図５】
0006613375.tif 000007
【図６】
0006613375.tif 000008
【図７】
0006613375.tif 000009
【図８】
0006613375.tif 000010