(57)【要約】【課題】  通信装置において、記憶領域を効率的に使用する。【解決手段】  置換領域選択装置は、データを格納する少なくとも１つの記憶手段に対する参照回数を記憶手段ごとに計測し、保持する参照回数保持手段と、記憶手段ごとに参照予定回数を保持する参照予定回数保持手段と、記憶手段ごとに参照回数と参照予定回数とを比較して、記憶手段ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定手段と、参照回数が参照予定回数に達している記憶手段を置換領域候補として選択する置換領域候補選択手段と、を備えることを特徴とする。【選択図】      図３
2011258073.tif 000002
【特許請求の範囲】
【請求項１】
データを格納する少なくとも１つの記憶手段に対する参照回数を前記記憶手段ごとに計測し、保持する参照回数保持手段と、
前記記憶手段ごとに参照予定回数を保持する参照予定回数保持手段と、
前記記憶手段ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶手段ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定手段と、
前記参照回数が前記参照予定回数に達している記憶手段を置換領域候補として選択する置換領域候補選択手段と、
を備えることを特徴とする置換領域選択装置。
【請求項２】
前記置換領域選択装置は、さらに、
データを前記記憶手段に格納する際、該データに含まれる情報を参照し、該データに含まれる情報に基づいて参照予定回数を算出する参照予定回数算出手段
を備えることを特徴とする請求項１に記載の置換領域選択装置。
【請求項３】
前記置換領域選択装置は、さらに、
前記置換領域候補から置換領域を決定する置換領域決定手段と、
データの読み出し要求を受信する要求受信手段と、
前記決定した置換領域を、前記読み出し要求を受けたデータに置換する置換手段と、
を備え、
前記参照回数保持手段は、前記置換領域が置換された場合、前記置換領域に対応する記憶手段の参照回数を初期化する
ことを特徴とする請求項１または２に記載の置換領域選択装置。
【請求項４】
前記参照予定回数算出手段は、さらに、
前記参照予定回数が複数存在する場合、あらかじめ指定された参照予定回数を判定し、該参照予定回数を使用する
ことを特徴とする請求項２または３に記載の置換領域選択装置。
【請求項５】
データを格納する少なくとも１つの記憶装置と、
置換領域選択装置と、
を備え、
前記置換領域選択装置は、
前記記憶装置に対する参照回数を前記記憶装置ごとに計測し、保持する参照回数保持手段と、
前記記憶装置ごとに参照予定回数を保持する参照予定回数保持手段と、
前記記憶装置ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶装置ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定手段と、
前記参照回数が前記参照予定回数に達している記憶装置を置換領域候補として選択する置換領域候補選択手段と、
を備えることを特徴とする置換領域選択システム。
【請求項６】
前記置換領域選択装置は、さらに、
データを前記記憶装置に格納する際、該データに含まれる情報を参照し、該データに含まれる情報に基づいて参照予定回数を算出する参照予定回数算出手段
を備えることを特徴とする請求項７に記載の置換領域選択システム。
【請求項７】
前記置換領域選択装置は、さらに、
前記置換領域候補から置換領域を決定する置換領域決定手段を備え、
前記置換領域選択システムは、さらに、
データの読み出し要求を受信する要求受信装置と、
前記決定した置換領域を、前記読み出し要求を受けたデータに置換する置換装置と、
を備え、
前記参照回数保持手段は、前記置換領域が置換された場合、前記置換領域に対応する記憶装置の参照回数を初期化する
ことを特徴とする請求項５または６に記載の置換領域選択システム。
【請求項８】
前記記憶装置として、バッファを用いることを特徴とする請求項５から７のいずれか１つに記載の置換領域選択システム。
【請求項９】
データを格納する少なくとも１つの記憶領域に格納する記憶ステップと、
前記記憶領域に対する参照回数を前記記憶領域ごとに計測し、保持する参照回数保持ステップと、
前記記憶領域ごとに参照予定回数を保持する参照予定回数保持ステップと、
前記記憶領域ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶領域ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定ステップと、
前記参照回数が前記参照予定回数に達している記憶領域を置換領域候補として選択する置換領域候補選択ステップと、
を含むことを特徴とする置換領域選択方法。
【請求項１０】
データを格納する少なくとも１つの記憶領域に格納する記憶処理と、
前記記憶領域に対する参照回数を前記記憶領域ごとに計測し、保持する参照回数保持処理と、
前記記憶領域ごとに参照予定回数を保持する参照予定回数保持処理と、
前記記憶領域ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶領域ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定処理と、
前記参照回数が前記参照予定回数に達している記憶領域を置換領域候補として選択する置換領域候補選択処理と、
をコンピュータに実行させることを特徴とする置換領域選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、置換領域選択装置、置換領域選択システム、置換領域選択方法、および置換領域選択プログラムに関し、特に、記憶領域を有する通信装置における置換領域選択装置、置換領域選択システム、置換領域選択方法、および置換領域選択プログラムに関する。
【背景技術】
【０００２】
近年、通信装置が扱うデータ量が急速に増加しているのに伴い、通信路におけるデータ転送レートも年々増加している。例として、携帯電話における下りの無線通信帯域を挙げる。第３世代の初期には通信帯域が３８４ｋｂｐｓであったものが、３．５世代として今や７．２Ｍｂｐｓの商用サービスが実現されている。加えて、将来の３．９世代となるＬＴＥ（Ｌｏｎｇ  Ｔｅｒｍ  Ｅｖｏｌｕｔｉｏｎ）では１００Ｍｂｐｓを超える帯域が利用可能となる見込みである。
【０００３】
無線通信路におけるデータ転送レートの向上に従い、携帯情報端末における無線通信処理性能も向上させる必要がある。
【０００４】
一般的に、携帯情報端末を含む、プロセッサとメモリから構成される計算機システムにおいては、システムの処理性能向上を阻害するメモリウォール問題が課題となっている。
【０００５】
メモリウォール問題とは、プロセッサのインストラクション処理の実行処理単位時間に比べて、外部メモリにアクセスするために必要なメモリアクセスレイテンシが極端に遅く、メモリアクセスの実行完了を待つプロセッサの処理を大きく阻害している状態を指す。つまり、プロセッサで実行されるインストラクション中にメモリアクセスを発生させるものが多く含まれているほど、システム全体の処理能力が低下する割合が大きくなる。
【０００６】
特許文献１では、あらかじめレジスタに指定されたアドレス範囲に該当するアクセスが発生したならば、プロセッサからのアクセス要求が発生する前に外部メモリからキャッシュに読み出しを行っておく、プリフェッチに関する技術が開示されている。
【０００７】
特許文献２には、メモリコントローラにおいて一時的に蓄えているデータを利用することにより、プロセッサからのメモリアクセスレイテンシを低減させる方法が開示されている。これから外部メモリに書き出そうとしているデータが格納されているバッファの中に、別のこれから読み出すべきデータが格納されていれば、外部メモリを介さずこのバッファのデータをプロセッサに返す。これによりメモリコントローラから外部メモリへのアクセスの分だけレイテンシが短縮されることになる。
【０００８】
キャッシュ、もしくはメモリコントローラにすでにデータが存在している確率が高いことも、平均レイテンシを削減する上で重要である。キャッシュにおける各ライン、もしくはメモリコントローラにおける各バッファは、それぞれデータもしくはインストラクションを一時的に蓄えるだけのものであるため、いずれは他のデータに置き換えられる。このデータの置き換え（リプレース）では、最後に参照される直前までデータを保持しておき、参照されなくなったら直ちに別のデータにリプレースされることが、キャッシュやメモリコントローラバッファの利用効率上はもっとも望ましい。
【０００９】
このリプレースのアルゴリズムとしては様々なものが提案されているが、性能と実装の両面からランダムリプレースアルゴリズムとＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）アルゴリズムがよく用いられている。ランダムリプレースアルゴリズムでは、リプレースする場所をランダムに選択するため必ずしも最適な置き換え場所を選ぶ訳ではない。しかし、実装のオーバーヘッドが非常に少ないため、よく用いられる方法である。他方、ＬＲＵアルゴリズムは、最も参照されにくいものを置き換え対象とするためループ処理などが多い場合には有効であるが、領域ごとに履歴を採る必要があり、その実装面積が必要なことがネックとなる。
【００１０】
特許文献３には、このＬＲＵアルゴリズムを用いたリプレース領域選択に関する技術が開示されている。
【００１１】
さらに、特許文献４には、直近にリプレース対象とすべきではない領域を直近のプロセッサからのアクセス要求から導出する方法が開示されている。この方法は、現在メモリコントローラに到着しているプロセッサからのアクセス要求を調べることによって、あらかじめリプレースすべきでない領域が特定できるというものである。この方法により、上記のランダムリプレースやＬＲＵなどのアルゴリズムを用いた汎用手段に加えて、さらにリプレース対象領域を正しく選択することが可能となる。
【００１２】
また、特許文献５には、アクセスされた回数（参照回数）の少ないデータブロックを優先的にリプレース対象にして、参照回数の多いデータブロックは削除せずに保持しておくという技術が開示されている。より具体的には、キャッシュラインごとに、データブロックの参照回数とその閾値とを比較し、閾値を超えているかどうかを判断し、新たなデータを書き込む際、空きブロックがない場合に、閾値未満のブロックがあれば、そのブロックにデータを上書きするという技術が開示されている。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】再公表ＷＯ０１／００４７６０号公報
【特許文献２】特開２００９−１４０３２４号公報
【特許文献３】特開２００８−２３４０７４号公報
【特許文献４】再公表ＷＯ２００７／０８８５９１号公報
【特許文献５】特開２００２−０７３４１６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、この特許文献５に記載された技術では、既に必要十分な回数だけアクセスが行われ、今後保存しておく必要がないデータブロックはリプレース対象とはならない。従って、今後使用する可能性が低いデータを維持することになるため、バッファ、キャッシュライン等の記憶領域の利用効率が良くないという課題がある。
【００１５】
本発明の目的は、上述した課題を解決することが可能な、置換領域選択装置、置換領域選択システム、置換領域選択方法、および置換領域選択プログラムを提供することである。
【課題を解決するための手段】
【００１６】
本発明による置換領域選択装置は、データを格納する少なくとも１つの記憶手段に対する参照回数を前記記憶手段ごとに計測し、保持する参照回数保持手段と、前記記憶手段ごとに参照予定回数を保持する参照予定回数保持手段と、前記記憶手段ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶手段ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定手段と、前記参照回数が前記参照予定回数に達している記憶手段を置換領域候補として選択する置換領域候補選択手段と、を備えることを特徴とする。
【００１７】
本発明による置換領域選択システムは、データを格納する少なくとも１つの記憶装置と、置換領域選択装置と、を備え、前記置換領域選択装置は、前記記憶装置に対する参照回数を前記記憶装置ごとに計測し、保持する参照回数保持手段と、前記記憶装置ごとに参照予定回数を保持する参照予定回数保持手段と、前記記憶装置ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶装置ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定手段と、前記参照回数が前記参照予定回数に達している記憶装置を置換領域候補として選択する置換領域候補選択手段と、を備えることを特徴とする。
【００１８】
本発明による置換領域選択方法は、データを格納する少なくとも１つの記憶領域に格納する記憶ステップと、前記記憶領域に対する参照回数を前記記憶領域ごとに計測し、保持する参照回数保持ステップと、前記記憶領域ごとに参照予定回数を保持する参照予定回数保持ステップと、前記記憶領域ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶領域ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定ステップと、前記参照回数が前記参照予定回数に達している記憶領域を置換領域候補として選択する置換領域候補選択ステップと、を含むことを特徴とする。
【００１９】
本発明による置換領域選択プログラムは、データを格納する少なくとも１つの記憶領域に格納する記憶処理と、前記記憶領域に対する参照回数を前記記憶領域ごとに計測し、保持する参照回数保持処理と、前記記憶領域ごとに参照予定回数を保持する参照予定回数保持処理と、前記記憶領域ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶領域ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定処理と、前記参照回数が前記参照予定回数に達している記憶領域を置換領域候補として選択する置換領域候補選択処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００２０】
本発明によれば、通信装置において記憶領域を効率的に使用することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】第１の実施形態のシステムの構成を示すブロック図である。
【図２】第１の実施形態のメモリコントローラの構成を示すブロック図である。
【図３】第１の実施形態のリプレース領域選択部の構成を示すブロック図である。
【図４】第１の実施形態のバッファ部の構成を示すブロック図である。
【図５】第１の実施形態のタグ部の構成を示すブロック図である。
【図６】第１の実施形態の外部メモリにおけるヒープの論理アドレスマップである。
【図７】第１の実施形態のデータ処理装置の処理フローを示すフローチャートである。
【図８】第２の実施形態のシステムの構成を示すブロック図である。
【図９】第２の実施形態のメモリコントローラの構成を示すブロック図である。
【図１０】第２の実施形態のリプレース領域選択部の構成を示すブロック図である。
【図１１】第３の実施形態のリプレース領域選択部の構成を示すブロック図である。
【図１２】第１の実施形態のメモリ上の通信データ配置の構成例を示す図である。
【図１３】第１の実施形態の参照予定回数の例示である。
【図１４】第４の実施形態の置換領域選択装置の構成を示す図である。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について、図面を参照して説明する。
【００２３】
＜第１の実施形態＞
（構成の説明）
本発明の第１の実施形態について図面を参照して詳細に説明する。
【００２４】
図１は、本発明の第１の実施形態のシステム構成を表すブロック図である。本実施形態のシステムは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１００、ＣＰＵ２００、共有バス３００、メモリコントローラ４００、外部ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５００を含む。ＣＰＵ１００およびＣＰＵ２００は、それぞれ共有バス３００にマスタ接続している。メモリコントローラ４００は共有バス３００にスレーブ接続している。外部ＲＡＭ５００は、ＣＰＵ１００およびＣＰＵ２００に対して、共有バス３００およびメモリコントローラ４００を介して接続する。
【００２５】
図２は、本実施形態のメモリコントローラ４００の構成を示すブロック図である。メモリコントローラ４００は、バス側インターフェース（Ｉ／Ｆ）４１０、要求バッファ４２０、マルチプレクサ４３０、リプレース領域選択部４４０、バッファ選択部４５０、バッファ部４６０、タグ部４７０、データパス制御部４８０、外部ＲＡＭ制御部４９０を含む。また、メモリコントローラ４００は、上述の通り、外部ＲＡＭ５００と接続する。
【００２６】
各機能の詳細について説明する。バス側Ｉ／Ｆ４１０は、共有バス３００（図２では非表示）と接続している。要求バッファ４２０は、ＣＰＵ１００またはＣＰＵ２００（図２では非表示）から受け取った要求をキューイングする。バッファ部４６０は、１つ以上のバッファを持ち、システムが受信したデータを格納する。マルチプレクサ４３０は、バッファ部４６０に格納されているデータを書き換えるにあたってのソースを選択する。リプレース領域選択部４４０は、バッファ部４６０のバッファのうち、どのバッファをリプレースするかを算出する。バッファ選択部４５０は、バッファ部４６０のバッファのうち、どのバッファから読み出しもしくは書き込みを行うかを選択する。タグ部４７０は、バッファ部４６０の各バッファに対応付けられているアドレスを保持する。データパス制御部４８０は、バッファ部４６０に対して読み出しもしくは書き込みのタイミングを示すバッファ書き換えイネーブル信号もしくはバッファ読み出しイネーブル信号を出力する。外部ＲＡＭ制御部４９０は、外部ＲＡＭ５００を制御する。
【００２７】
図３は、本実施形態のリプレース領域選択部４４０の構成を示すブロック図である。リプレース領域選択部４４０は、参照予定回数保持部４４１、参照回数保持部４４２、参照回数上限到達判定部４４３、汎用リプレースアルゴリズム部４４４、リプレース領域決定部４４５、参照予定回数取り出し部４４６を含む。
【００２８】
参照予定回数保持部４４１は、バッファ部４６０の各バッファに対応付けられたレジスタを含み、各バッファの参照予定回数を保持する。参照回数保持部４４２は、バッファ部４６０の各バッファに対応付けられたカウンタを含む。各バッファに対する参照回数を計測し、保持する。参照回数上限到達判定部４４３は、参照予定回数保持部４４１に格納された各バッファの参照予定回数と、参照回数保持部４４２に格納された各バッファに対する参照回数とを比較する。図３の例では、参照予定回数保持部４４１のレジスタ＃１、＃２、＃３、＃４と、参照回数保持部４４２のカウンタ＃１、＃２、＃３、＃４が、それぞれ図４のバッファ＃１、＃２、＃３、＃４に対応している。
【００２９】
図４は、バッファ部４６０の構成を示すブロック図である。バッファ部４６０は、バッファアレイ部４６１を含む。バッファアレイ部４６１には、１つ以上のバッファが存在する。バッファアレイ部４６１は、それぞれのバッファに対するバッファ読み出しイネーブル信号、バッファ書き換えイネーブル信号に応じて、対応するバッファの書き込みまたは読み出しを行う。
【００３０】
図５は、タグ部４７０の構成を示すブロック図である。タグ部４７０は、タグ情報保持部４７１、アドレス一致検出部４７２を含む。タグ情報保持部４７１は、上述の通り、バッファ部４６０の各バッファに対応付けられているアドレスを保持している。
【００３１】
図６は、外部ＲＡＭ５００におけるヒープ領域の論理アドレスマップである。バッファに格納される単位であるページごとに参照予定回数が保持される。例えば、ページ＃１の参照予定回数としては、通信データ＃１〜＃３の参照予定回数を足した値が格納されている。
【００３２】
（動作の説明）
次に、図７のフローチャートを用いて、データの読み出し処理を行う際の本実施形態の動作について説明する。
【００３３】
まず、ステップＳ００１では、要求バッファ４２０が、ＣＰＵ１００またはＣＰＵ２００からデータの読み出し要求を受信し、要求の中からアドレスを取り出す。ステップＳ００２では、タグ部４７０が、この取り出したアドレスを格納しているかどうかを判断する。
【００３４】
以下、ステップＳ００２の詳細について説明する。タグ部４７０（図５）がアドレスを受信すると、アドレス一致検出部４７２が、このアドレスがタグ情報保持部４７１に存在するかどうかを判断する。受信したアドレスがタグ情報保持部４７１のタグ＃１〜＃４のいずれかに存在する場合には、一致したタグの情報を、バッファ選択部４５０に送信する（図７では非表示）。
【００３５】
（ステップＳ００２が“ＹＥＳ”の場合）
ステップＳ００２において、タグ部４７０が、受信したアドレスをタグ部４７０に格納していると判定した場合は、以下の処理を行う。
【００３６】
まずステップＳ００８において、バッファ部４６０は、バッファ部４６０のバッファのうち、受信したアドレスに対応するデータを取り出す。バッファ部４６０は、取り出したデータを、共有バス３００を介してＣＰＵ１００もしくはＣＰＵ２００に転送する。
【００３７】
さらに、ステップＳ００９において、参照回数保持部４４２は、カウンタインクリメント信号に応じて、参照回数保持部４４２内のカウンタのうち、データが保持されていたバッファに対応するカウンタに保持されている参照回数の値をインクリメントする。
【００３８】
（ステップＳ００２が“ＮＯ”の場合）
一方、ステップＳ００２において、タグ部４７０が、受信したアドレスをタグ部４７０に格納していないと判断した場合は、上述したステップＳ００８およびステップＳ００９の処理を行う前に、ステップＳ００３からＳ００７までの処理を行う。
【００３９】
ステップＳ００３において、参照回数上限到達判定部４４３が、バッファ部４６０に含まれるバッファのうち、参照回数が参照予定回数に達したバッファがあるかどうかを判定する。この判定は、参照予定回数保持部４４１の各レジスタが保持する各バッファの参照予定回数と、参照回数保持部４４２の各カウンタが保持する各バッファの参照回数とを比較することで行われる。より具体的には、各バッファの参照回数が、各バッファの参照予定回数以上かどうかを判定する。
【００４０】
次に、ステップＳ００３において、参照回数が参照予定回数に達したバッファが存在すると判定された場合は、以下の処理を行う。
【００４１】
ステップＳ００４において、参照回数上限到達判定部４４３が、参照回数が参照予定回数に達したバッファをリプレースバッファ候補としてリストアップする。ここで、どのような方法でリストアップを行っても良いが、例えば、バッファ部４６０とは異なる別の記憶領域を設けておき、その記憶領域にリプレースバッファ候補を記憶しておくという方法が挙げられる。なお、参照回数が参照予定回数に達したバッファが複数ある場合は、複数のバッファをリストアップしても良い。
【００４２】
また、ステップＳ００３において、参照回数が参照予定回数に達したバッファが存在しないと判定された場合は、以下の処理を行う。
【００４３】
ステップＳ００５において、汎用リプレースアルゴリズム部４４４が、所定の汎用リプレースアルゴリズムを実行することにより、リプレース対象となるバッファをリプレースバッファ候補として選択する。所定の汎用リプレースアルゴリズムとしては、例えば、背景技術の項で述べた、ランダムリプレースアルゴリズムやＬＲＵアルゴリズム等を用いることができる。
【００４４】
ステップＳ００４またはステップＳ００５の処理の後、ステップＳ００６において、リプレース領域決定部４４５が、リプレースバッファ候補から、リプレース対象となるバッファを決定する処理を行う。
【００４５】
さらに、ステップＳ００７において、リプレース対象となったバッファに格納されているデータのリプレースが行われる。同時に、タグ部４７０が、リプレース対象となったバッファに対応するタグ情報保持部４７１内のタグのアドレスを書き換える。また、リプレース対象となったバッファに格納されているデータのリプレースが行われると同時に、参照回数保持部４４２は、リプレース対象となったバッファに対応する参照回数保持部４４２のカウンタに保持されている参照回数の値を初期化する。この参照回数の初期化は、データパス制御部４８０からのバッファ書き換えイネーブル信号およびバッファ選択部４５０からのバッファ選択信号に応じて行われる。
【００４６】
その後、ステップＳ００８において、バッファ部４６０は、リプレース後のデータを取り出し、共有バス３００を介して、ＣＰＵ１００またはＣＰＵ２００に転送する。
【００４７】
さらに、ステップＳ００９において、参照回数保持部４４２は、カウンタインクリメント信号に応じて、参照回数保持部４４２内のカウンタのうち、データが保持されていたバッファに対応するカウンタに保存されている参照回数の値をインクリメントする。
【００４８】
（参照予定回数の算出）
参照予定回数の算出方法の一例としては、メモリコントローラ４００がデータを受信し、バッファ部４６０のいずれかのバッファに格納する際に算出することが挙げられる。ただし、参照予定回数の算出方法は、以下に限られるものではない。
【００４９】
図１２は、メモリ上の通信データ配置の構成例を示している。通信データは、ペイロード＃１−１〜３とペイロード＃２−１〜４、およびペイロード＃１−１〜３のヘッダ情報を格納するヘッダ＃１と、ペイロード＃２―１〜４のヘッダ情報を格納するヘッダ＃２を含む。ページ＃Ｎは、ヘッダ＃１、ペイロード＃１−１、＃１−２、＃１−３の一部を格納する。同様に、ページ＃（Ｎ＋１）は、ペイロード＃１−３の一部、ヘッダ＃２、ペイロード＃２−１、＃２−２、＃２−３の一部を格納する。この通信データをメモリ上のページ＃Ｎ〜＃（Ｎ＋２）に格納する際には、メモリ上のページの先頭にペイロード参照予定回数＃Ｎ〜＃（Ｎ＋２）が通信データのメモリ格納時に挿入される。
【００５０】
図１３は、参照予定回数の例を示している。ここでは、通信データ内の各ヘッダ、および各ペイロードの参照予定回数はそれぞれ１回であるとあらかじめ分かっている場合を想定している。ヘッダおよびペイロードの参照予定回数は、通信プロトコルにより定められていることが多い。例えば、Ｅｔｈｅｒｎｅｔ（登録商標）においては、各通信データへの参照回数は、プロトコルレイヤごとに１度ずつという場合もある。
【００５１】
メモリ上のページ番号＃Ｎにはヘッダ＃１、ペイロード＃１−１〜２、およびペイロード＃１−３の一部が格納されているため、参照予定回数は、ヘッダについては１回、ペイロードについては３回という値がメモリ上の参照予定回数の格納領域に保持されている。メモリ上のページ番号＃（Ｎ＋１）にはヘッダ＃２、ペイロード＃１−３の一部、およびペイロード＃２−１〜３が格納されている。このため、参照予定回数は、ヘッダについては１回、ペイロードについては４回という値が、メモリ上の参照予定回数の格納領域に保持されている。
【００５２】
（効果）
以上、説明した通り、本実施形態では、各バッファに対する参照回数を計測し、参照回数が各バッファの参照予定回数に達したバッファをリプレース候補とする。これによって、参照予定回数を超えて不要と判断されるデータを含むバッファを優先的にリプレース候補とすることが可能になる。したがって、通信装置上のメモリを効率的に利用することが可能となる。
【００５３】
さらに、本実施形態によれば、バッファごとの参照回数と参照予定回数をリプレース判定に用いることにより、各バッファ上のデータ個々の生存すべき期間の絶対時間の長短によらず、必要な期間だけ保持することができる。
【００５４】
その理由は、リプレース判定に用いるバッファごとの参照回数と参照予定回数という２つのパラメータは絶対処理時間の長短に依存しない値であり、そこから導出されるリプレース判定結果も絶対時間の長短に依存しないためである。
【００５５】
また、本実施形態によれば、バッファごとの参照回数と参照予定回数をリプレース判定に用いることにより、確率やランダム性に依存せずにリプレース候補を選択することが可能となる。
【００５６】
その理由は、リプレース判定に用いるバッファごとの参照回数と参照予定回数という２つのパラメータは確率的に不確定な値を含まないため、そこから導出されるリプレース判定結果に不確実性が伴わないためである。
【００５７】
＜第２の実施形態＞
（構成と動作）
次に、本発明の第２の実施形態について図面を参照して詳細に説明する。
【００５８】
図８は、本実施形態のシステム構成を表すブロック図である。本実施形態のシステムは、ＣＰＵ８００、ＣＰＵ９００、共有バス３００、第２レベルキャッシュ（Ｌ２キャッシュ）６００、メモリコントローラ７００、外部ＲＡＭ５００を含む。ＣＰＵ８００およびＣＰＵ９００は、それぞれ共有バス３００にマスタ接続している。なお、ＣＰＵ８００およびＣＰＵ９００は、その内部に第１レベルキャッシュ（Ｌ１キャッシュ）を備えていても良い。Ｌ２キャッシュ６００は共有バス３００にスレーブ接続している。外部ＲＡＭ５００は、ＣＰＵ８００およびＣＰＵ９００に対して、共有バス３００、Ｌ２キャッシュ６００、メモリコントローラ７００を介して接続する。
【００５９】
第１の実施形態においては、メモリコントローラ４００がリプレース領域選択部４４０を含んでいた。一方、本実施形態では、Ｌ２キャッシュ６００が、リプレース領域選択部６４０を含む構成をとっている。
【００６０】
図９は、本実施形態におけるＬ２キャッシュ６００の構成を示すブロック図である。Ｌ２キャッシュ６００は、バス側Ｉ／Ｆ（インターフェース）６１０、要求バッファ６２０、マルチプレクサ６３０、リプレース領域選択部６４０、キャッシュライン選択部６５０、キャッシュライン部６６０、タグ部６７０、データパス制御部６８０、メモリコントローラ側Ｉ／Ｆ６９０、を含む。
【００６１】
各機能について説明する。バス側Ｉ／Ｆ６１０は、共有バス３００（図８）と接続している。要求バッファ６２０は、ＣＰＵ８００またはＣＰＵ９００から受け取った要求をキューイングする。キャッシュライン部６６０は、受信したデータを格納する。マルチプレクサ６３０は、キャッシュライン部６６０に格納されているデータを書き換えるにあたってのソースを選択する。リプレース領域選択部６４０は、キャッシュライン部６６０のキャッシュラインのうち、どのキャッシュラインをリプレースするかを算出する。キャッシュライン選択部６５０は、キャッシュライン部６６０のキャッシュラインのうち、どのキャッシュラインから読み出しもしくは書き込みを行うかを選択する。タグ部６７０は、キャッシュライン部６６０の各キャッシュラインそれぞれに対応付けられているアドレスを保持する。データパス制御部６８０は、キャッシュライン部６６０に対して読み出しもしくは書き込みのタイミングを示すキャッシュライン書き換えイネーブル信号、もしくはキャッシュライン読み出しイネーブル信号を出力する。メモリコントローラ側Ｉ／Ｆ６９０は、メモリコントローラ７００（図８）に対するインターフェースである。
【００６２】
図１０は、本実施形態のリプレース領域選択部６４０の構成を示すブロック図である。リプレース領域選択部６４０と、第１の実施形態におけるリプレース領域選択部４４０との差分は、記憶領域がバッファ（第１の実施形態）からキャッシュラインに変わったことである。よって、リプレース領域選択部６４０とリプレース領域選択部４４０はほぼ同様の構成および動作であるため、詳細な説明は省略する。
【００６３】
また、キャッシュライン部６６０およびタグ部６７０も、第１の実施形態とほぼ同様の構成および動作であるため、詳細な説明は省略する。キャッシュライン部６６０の構成は、第１の実施形態のバッファ部４６０とほぼ同様であり、バッファがキャッシュラインに替わったことが差分である。タグ部６７０の構成は、第１の実施形態のタグ部４７０とほぼ同様である。
【００６４】
（効果）
以上、説明した通り、本実施形態では、各キャッシュラインに対する参照回数を計測し、参照回数が各キャッシュラインの参照予定回数に達したキャッシュラインをリプレース候補とする。これによって、参照予定回数を超えて不要と判断されるデータを含むキャッシュラインを優先的にリプレース候補とすることが可能になる。したがって、通信装置上のメモリを効率的に利用することが可能となる。
【００６５】
さらに、本実施形態によれば、キャッシュラインごとの参照回数と参照予定回数をリプレース判定に用いることにより、各キャッシュライン上のデータ個々の生存すべき期間の絶対時間の長短によらず、必要な期間だけ保持することができる。
【００６６】
その理由は、リプレース判定に用いるキャッシュラインごとの参照回数と参照予定回数という２つのパラメータは絶対処理時間の長短に依存しない値であり、そこから導出されるリプレース判定結果も絶対時間の長短に依存しないためである。
【００６７】
また、本実施形態によれば、キャッシュラインごとの参照回数と参照予定回数をリプレース判定に用いることにより、確率やランダム性に依存せずにリプレース候補を選択することが可能となる。
【００６８】
その理由は、リプレース判定に用いるキャッシュラインごとの参照回数と参照予定回数という２つのパラメータは確率的に不確定な値を含まないため、そこから導出されるリプレース判定結果に不確実性が伴わないためである。
【００６９】
＜第３の実施形態＞
（構成と動作）
次に、本発明の第３の実施形態について図面を参照して詳細に説明する。本実施形態では、第１の実施形態のリプレース領域選択部４４０（図２、３）および第２の実施形態のリプレース領域選択部６４０（図９、１０）に換えて、リプレース領域選択部１１４０が設けられている。その他の構成および動作については、第１の実施形態および第２の実施形態とほぼ同様であるので、詳細な説明は省略する。
【００７０】
図１１は、本実施形態におけるリプレース領域選択部１１４０の構成を示すブロック図である。リプレース領域選択部１１４０は、参照予定回数保持部１１４１、参照回数保持部１１４２、参照回数上限到達判定部１１４３、汎用リプレースアルゴリズム部１１４４、リプレース領域決定部１１４５、参照予定回数取り出し部１１４６を含む。このうち、参照予定回数保持部１１４１、参照回数保持部１１４２、参照回数上限到達判定部１１４３、汎用リプレースアルゴリズム部１１４４、リプレース領域決定部１１４５については、第１の実施形態のリプレース領域選択部４４０および第２の実施形態のリプレース領域選択部６４０とほぼ同様の構成および動作であるため、詳細な説明は省略する。
【００７１】
なお、図１１では、記憶領域として、第１の実施形態と同様、バッファを使うことを想定しているが、第２の実施形態と同様に、キャッシュラインを用いても良い。その場合のリプレース領域選択部１１４０以外の構成は、第２の実施形態の構成（図８、図９）と同様である。
【００７２】
本実施形態のリプレース領域選択部１１４０は、第１の実施形態のリプレース領域選択部４４０および第２の実施形態のリプレース領域選択部６４０と比較して、参照予定回数取り出し部１１４６の構成が異なる。
【００７３】
参照予定回数取り出し部１１４６は、第１の実施形態の参照予定回数取り出し部４４６、第２の実施形態の参照予定回数取り出し部６４６と比較して、１つのバッファ領域に格納されたデータに対して複数の参照予定回数が格納されていた場合に、いずれの参照予定回数の値を用いるかを選択する機能をさらに有する。いずれの値を用いるかはＣＰＵからあらかじめ指定されており、その指定された値は参照予定回数取り出し部１１４６に保持されている。
【００７４】
本実施形態によれば、記憶領域に格納された１つのデータが複数の参照予定回数を有している場合にも、第１の実施形態および第２の実施形態と同等の効果を奏することが可能となる。
【００７５】
＜第４の実施形態＞
次に、本発明の第４の実施形態について、図１４を参照して詳細に説明する。
【００７６】
図１４は、本実施形態のシステム構成を示すブロック図である。本実施形態のシステムは、置換領域選択装置１０００と、記憶領域１００３とを含む。置換領域選択装置１０００は、参照予定回数保持部１００１−１、１００１−２、１００１−３、参照回数保持部１００２−１、１００２−２、１００２−３、参照回数上限到達判定部１００４、置換領域候補選択部１００５を含む。
【００７７】
参照予定回数保持部１００１−１、１００１−２、１００１−３と、参照回数保持部１００２−１、１００２−２、１００２−３は、それぞれ記憶領域１００３−１、１００３−２、１００３−３に対応して設けられている。
【００７８】
以下、各機能の詳細を説明する。まず、記憶領域１００３−１、１００３−２、１００３−３は、置換領域選択装置１０００が受信したデータを格納する。
【００７９】
参照回数保持部１００２−１、１００２−２、１００２−３は、それぞれ対応する記憶領域１００３−１〜３に対する参照回数を計測して、保持する。
【００８０】
参照予定回数保持部１００１−１、１００１−２、１００１−３は、それぞれ対応する記憶領域１００３−１〜３の参照予定回数を保持する。
【００８１】
参照回数上限到達判定部１００４は、参照予定回数保持部１００１に格納された各記憶領域１００３の参照予定回数と、参照回数保持部１００２に格納された各記憶領域１００３に対する参照回数とを比較する。参照回数上限到達判定部１００４は、各記憶領域１００３の参照回数が、参照予定回数以上の値になっているかどうかを判定する。
【００８２】
置換領域候補選択部１００５は、記憶領域１００３−１、１００３−２、１００３−３のうち、いずれかの参照回数が参照予定回数以上の値になっている場合、その記憶領域を置換領域候補として選択する。
【００８３】
（効果）
以上、説明した通り、本実施形態では、各記憶領域に対する参照回数を計測し、参照回数が各記憶領域の参照予定回数に達した記憶領域をリプレース候補とする。これによって、参照予定回数を超えて不要と判断されるデータを含む記憶領域を優先的にリプレース候補とすることが可能になる。したがって、通信装置上のメモリを効率的に利用することが可能となる。
【００８４】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００８５】
（付記１）
データを格納する少なくとも１つの記憶手段に対する参照回数を前記記憶手段ごとに計測し、保持する参照回数保持手段と、
前記記憶手段ごとに参照予定回数を保持する参照予定回数保持手段と、
前記記憶手段ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶手段ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定手段と、
前記参照回数が前記参照予定回数に達している記憶手段を置換領域候補として選択する置換領域候補選択手段と、
を備えることを特徴とする置換領域選択装置。
【００８６】
（付記２）
前記置換領域選択装置は、さらに、
データを前記記憶手段に格納する際、該データに含まれる情報を参照し、該データに含まれる情報に基づいて参照予定回数を算出する参照予定回数算出手段
を備えることを特徴とする付記１に記載の置換領域選択装置。
【００８７】
（付記３）
前記置換領域選択装置は、さらに、
データの読み出し要求を受信する要求受信手段と、
前記置換領域候補から置換領域を決定する置換領域決定手段と、
前記決定した置換領域を、前記読み出し要求を受けたデータに置換する置換手段と、
を備え、
前記参照回数保持手段は、前記置換領域が置換された場合、前記置換領域に対応する記憶手段の参照回数を初期化する
ことを特徴とする付記１または２に記載の置換領域選択装置。
【００８８】
（付記４）
前記参照予定回数算出手段は、さらに、
前記参照予定回数が複数存在する場合、あらかじめ指定された参照予定回数を判定し、該参照予定回数を使用する
ことを特徴とする付記２または３に記載の置換領域選択装置。
【００８９】
（付記５）
データを格納する少なくとも１つの記憶装置と、
置換領域選択装置と、
を備え、
前記置換領域選択装置は、
前記記憶装置に対する参照回数を前記記憶装置ごとに計測し、保持する参照回数保持手段と、
前記記憶装置ごとに参照予定回数を保持する参照予定回数保持手段と、
前記記憶装置ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶装置ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定手段と、
前記参照回数が前記参照予定回数に達している記憶装置を置換領域候補として選択する置換領域候補選択手段と、
を備えることを特徴とする置換領域選択システム。
【００９０】
（付記６）
前記置換領域選択装置は、さらに、
データを前記記憶装置に格納する際、該データに含まれる情報を参照し、該データに含まれる情報に基づいて参照予定回数を算出する参照予定回数算出手段
を備えることを特徴とする付記５に記載の置換領域選択システム。
【００９１】
（付記７）
前記置換領域選択装置は、さらに、
前記置換領域候補から置換領域を決定する置換領域決定手段を備え、
前記置換領域選択システムは、さらに、
データの読み出し要求を受信する要求受信装置と、
前記決定した置換領域を、前記読み出し要求を受けたデータに置換する置換装置と、
を備え、
前記参照回数保持手段は、前記置換領域が置換された場合、前記置換領域に対応する記憶装置の参照回数を初期化する
ことを特徴とする付記５または６に記載の置換領域選択システム。
【００９２】
（付記８）
前記記憶装置として、バッファを用いることを特徴とする付記５から７のいずれか１つに記載の置換領域選択システム。
【００９３】
（付記９）
前記記憶装置として、キャッシュラインを用いることを特徴とする付記５から７のいずれか１つに記載の置換領域選択システム。
【００９４】
（付記１０）
前記参照予定回数算出手段は、さらに、
前記参照予定回数が複数存在する場合、あらかじめ指定された参照予定回数を判定し、該参照予定回数を使用する
ことを特徴とする付記６から９のいずれか１つに記載の置換領域選択システム。
【００９５】
（付記１１）
データを格納する少なくとも１つの記憶領域に格納する記憶ステップと、
前記記憶領域に対する参照回数を前記記憶領域ごとに計測し、保持する参照回数保持ステップと、
前記記憶領域ごとに参照予定回数を保持する参照予定回数保持ステップと、
前記記憶領域ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶領域ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定ステップと、
前記参照回数が前記参照予定回数に達している記憶領域を置換領域候補として選択する置換領域候補選択ステップと、
を含むことを特徴とする置換領域選択方法。
【００９６】
（付記１２）
前記置換領域選択方法は、さらに、
データを前記記憶領域に格納する際、該データに含まれる情報を参照し、該データに含まれる情報に基づいて参照予定回数を算出する参照予定回数算出ステップ
を含むことを特徴とする付記１１に記載の置換領域選択方法。
【００９７】
（付記１３）
前記置換領域選択方法は、さらに、
前記置換領域候補から置換領域を決定する置換領域決定ステップと、
データの読み出し要求を受信する要求受信ステップと、
前記決定した置換領域を、前記読み出し要求を受けたデータに置換する置換ステップと、
を含み、
前記参照回数保持ステップは、前記置換領域が置換された場合、前記置換領域に対応する記憶手段の参照回数を初期化する
ことを特徴とする付記１１または１２に記載の置換領域選択方法。
【００９８】
（付記１４）
前記記憶領域として、バッファを用いることを特徴とする付記１１から１３のいずれか１つに記載の置換領域選択方法。
【００９９】
（付記１５）
前記記憶領域として、キャッシュラインを用いることを特徴とする付記１１から１３のいずれか１つに記載の置換領域選択方法。
【０１００】
（付記１６）
前記参照予定回数算出ステップは、さらに、
前記参照予定回数が複数存在する場合、あらかじめ指定された参照予定回数を判定し、該参照予定回数を使用する
ことを特徴とする付記１２から１５のいずれか１つに記載の置換領域選択方法。
【０１０１】
（付記１７）
データを格納する少なくとも１つの記憶領域に格納する記憶処理と、
前記記憶領域に対する参照回数を前記記憶領域ごとに計測し、保持する参照回数保持処理と、
前記記憶領域ごとに参照予定回数を保持する参照予定回数保持処理と、
前記記憶領域ごとに前記参照回数と前記参照予定回数とを比較して、前記記憶領域ごとに参照回数が参照予定回数に達したか否かの判定を行う参照回数上限到達判定処理と、
前記参照回数が前記参照予定回数に達している記憶領域を置換領域候補として選択する置換領域候補選択処理と、
をコンピュータに実行させることを特徴とする置換領域選択プログラム。
【０１０２】
（付記１８）
前記置換領域選択プログラムは、さらに、
データを前記記憶領域に格納する際、該データに含まれる情報を参照し、該データに含まれる情報に基づいて参照予定回数を算出する参照予定回数算出処理
を含むことを特徴とする付記１７に記載の置換領域選択プログラム。
【０１０３】
（付記１９）
前記置換領域選択プログラムは、さらに、
前記置換領域候補から置換領域を決定する置換領域決定処理と、
データの読み出し要求を受信する要求受信処理と、
前記決定した置換領域を、前記読み出し要求を受けたデータに置換する置換処理と、
を含み、
前記参照回数保持処理は、前記置換領域が置換された場合、前記置換領域に対応する記憶手段の参照回数を初期化する
ことを特徴とする付記１７または１８に記載の置換領域選択プログラム。
【０１０４】
（付記２０）
前記記憶領域として、バッファを用いることを特徴とする付記１７から１９のいずれか１つに記載の置換領域選択プログラム。
【０１０５】
（付記２１）
前記記憶領域として、キャッシュラインを用いることを特徴とする付記１７から１９のいずれか１つに記載の置換領域選択プログラム。
【０１０６】
（付記２２）
前記参照予定回数算出処理は、さらに、
前記参照予定回数が複数存在する場合、あらかじめ指定された参照予定回数を判定し、該参照予定回数を使用する
ことを特徴とする付記１８から２１のいずれか１つに記載の置換領域選択プログラム。
【産業上の利用可能性】
【０１０７】
本発明は、有線・無線の区別無く通信データを処理する通信装置に適用可能である。
【符号の説明】
【０１０８】
１００、２００、８００、９００    ＣＰＵ
３００    共有バス
４００、７００    メモリコントローラ
４１０、６１０    バス側インターフェース
４２０、６２０    要求バッファ
４３０、６３０    マルチプレクサ
４４０、６４０、１１４０    リプレース領域選択部
４４１、６４１、１００１、１１４１    参照予定回数保持部
４４２、６４２、１００２、１１４２    参照回数保持部
４４３、６４３、１００４、１１４３    参照回数上限到達判定部
４４４、６４４、１１４４    汎用リプレースアルゴリズム部
４４５、６４５、１１４５    リプレース領域決定部
４４６、６４６、１１４６    参照予定回数取り出し部
４５０    バッファ選択部
４６０    バッファ部
４６１    バッファアレイ部
４７０、６７０    タグ部
４７１    タグ情報保持部
４７２    アドレス一致検出部
４８０、６８０    データパス制御部
４９０    外部ＲＡＭ制御部
５００    外部ＲＡＭ
６００    Ｌ２キャッシュ
６５０    キャッシュライン選択部
６６０    キャッシュライン部
６９０    メモリコントローラ側インターフェース
１０００    置換領域選択装置
１００３    記憶領域
１００５    置換領域候補選択部
【図１】
2011258073.tif 000003
【図２】
2011258073.tif 000004
【図３】
2011258073.tif 000005
【図４】
2011258073.tif 000006
【図５】
2011258073.tif 000007
【図６】
2011258073.tif 000008
【図７】
2011258073.tif 000009
【図８】
2011258073.tif 000010
【図９】
2011258073.tif 000011
【図１０】
2011258073.tif 000012
【図１１】
2011258073.tif 000013
【図１２】
2011258073.tif 000014
【図１３】
2011258073.tif 000015
【図１４】
2011258073.tif 000016