(57)【特許請求の範囲】
【請求項１】
セットアソシアティブ方式のキャッシュメモリを制御するキャッシュ制御方法であって、
前記キャッシュメモリ上の複数のセットの各々での再配置回数をカウントし、
前記カウントした各セットでの再配置回数に基づいて、各セットのウェイ数を調整する、
ことを特徴とするキャッシュ制御方法。
【請求項２】
前記ウェイ数の調整では、前記カウントした再配置回数が第１閾値以上であるセットに対応する判定参照値を増加させる一方、前記カウントした再配置回数が前記第１閾値より小さい第２閾値以下であるセットに対応する前記判定参照値を減少させ、前記判定参照値の大きさに基づいて、各セットのウェイ数を、増加させるか、減少させるか、又は、維持させる、
ことを特徴とする請求項１に記載のキャッシュ制御方法。
【請求項３】
前記複数のセットのうちの第１セットのウェイ数を減少させる場合、前記第１セットから外されたウェイを空きウェイ管理テーブルに登録する、
ことを特徴とする請求項２に記載のキャッシュ制御方法。
【請求項４】
前記複数のセットのうちの第２セットのウェイ数を増加させる場合、前記空きウェイ管理テーブルに登録されているウェイを前記第２セットに組み入れる、
ことを特徴とする請求項３に記載のキャッシュ制御方法。
【請求項５】
セットアソシアティブ方式のキャッシュメモリを制御するキャッシュ制御装置であって、
前記キャッシュメモリ上の複数のセットの各々での再配置回数をカウントするカウント部と、
前記カウントした各セットでの再配置回数に基づいて、各セットのウェイ数を調整するキャッシュメモリ制御部と、
を具備することを特徴とするキャッシュ制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ制御方法及びキャッシュ制御装置に関する。
【背景技術】
【０００２】
複数の移動局（つまり、複数のユーザ）と無線通信を行う基地局では、プロセッサ上で動作する呼処理アプリケーションがランダムに無線接続する各ユーザに対して「ユーザ設定（例えば、使用リソース等）」を割り当てる。ユーザ設定に関するデータ（以下では、「ユーザ設定データ」と呼ぶことがある）は、基地局のメインメモリに対して書き込まれる。また、メインメモリに書き込まれたユーザ設定データは、必要に応じてメインメモリから読み出される。ここで、メインメモリの処理スピードは通常遅いため、プロセッサとメインメモリとの間に処理スピードの速いキャッシュメモリが設けられている。また、キャッシュの構造としては、例えば、セットアソシアティブ方式がある。このセットアソシアティブ方式では、互いに「セットインデックス」が異なる複数の「セット（つまり、セット領域）」がキャッシュメモリ上に設けられる。また、各セットには、複数の「ウェイ」が設けられる。そして、例えば、メインメモリ上のアドレス（以下では、「メインメモリアドレス」と呼ぶことがある）のうちの「下位ビット」に「セットインデックス」が対応付けられる。すなわち、例えば、第１のユーザ設定データを第１のメインメモリアドレスのメインメモリ領域に書き込む場合、第１のメインメモリアドレスの下位ビットに対応付けられた第１のセットインデックスに対応するセット内のいずれかのウェイに、第１のユーザ設定データが書き込まれる。例えば、メインメモリアドレスの下位ビットをキャッシュメモリ上に設けられたセットの数で除算した余りが、セットインデックスとして用いられる。従って、１つのセットには、当該セットのウェイ数を超えるメインメモリアドレスが対応することがある。また、例えば、第１のメインメモリアドレスのメインメモリ領域に記憶されている第１のユーザ設定データを読み出す場合、第１のメインメモリアドレスの下位ビットに対応するセット内の各ウェイに第１のユーザ設定データが保持されているか検索する。各ウェイに保持されているユーザ設定データが第１のユーザ設定データであるか否かの判断は、メインメモリアドレスのうちの「上位ビット」が用いられる。この「上位ビット」は、「タグ」と呼ばれることがある。すなわち、１つのウェイには、「タグ」と「ユーザ設定データ」とが対応づけられて記憶される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−３１６９５１号公報
【特許文献２】特開平５−２３３３９９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、無線通信の利用状況はユーザによって異なる。このため、無線通信を利用しようとしている各ユーザのユーザ設定データが記憶されているメインメモリ領域に対応するセットが一部のセットに集中する可能性がある。すなわち、ユーザ設定データの読み出し及び書き込みが一部のセットに集中する可能性がある。この集中が発生するとその一部のセットでは「ヒット率」が低下して「再配置（ＲＡ）」が頻繁に生じるため、呼処理の処理効率が低下してしまう可能性がある。
【０００５】
そこで、呼処理アプリケーションによってユーザによる無線通信の利用状況を予測し、予測結果に基づいて、ユーザ設定データの読み出し及び書き込みが一部のセットに集中しないように、ユーザ設定データをメインメモリ上に配置することも考えられる。
【０００６】
しかしながら、昨今の通信事情によりユーザの利用状況を予測すること自体が難しい。すなわち、移動局による通信としては、従来では音声呼が主流であったが、現在ではインターネットを利用した電子メール、インターネットブラウザによる情報表示、及び、動画配信等のパケットサービスによる通話が広く利用されている。また、音声呼とパケット呼との割合は時々刻々と変化する。従って、ユーザによる無線通信の利用状況に関する予測結果に基づいて、ユーザ設定データの読み出し及び書き込みが一部のセットに集中しないように、ユーザ設定データをメインメモリ上に配置することは、難しい。
【０００７】
開示の技術は、上記に鑑みてなされたものであって、キャッシュのヒット率を向上させることができる、キャッシュ制御方法及びキャッシュ制御装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
開示の態様では、セットアソシアティブ方式のキャッシュメモリを制御するキャッシュ制御方法において、前記キャッシュメモリ上の複数のセットの各々での再配置回数をカウントし、前記カウントした各セットでの再配置回数に基づいて、各セットのウェイ数を調整する。
【発明の効果】
【０００９】
開示の態様によれば、キャッシュのヒット率を向上させることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、一実施例のキャッシュ制御装置を含む電子機器の一例を示す図である。
【図２】図２は、メインメモリアドレスの一例を示す図である。
【図３】図３は、空きウェイ管理テーブルの一例を示す図である。
【図４】図４は、先頭ポインタ管理テーブルの一例を示す図である。
【図５】図５は、再配置回数カウントテーブルの一例を示す図である。
【図６】図６は、ウェイト数管理テーブルの一例を示す図である。
【図７】図７は、ウェイ領域のフォーマットの一例を示す図である。
【図８】図８は、キャッシュメモリ初期化処理の一例を示すフローチャートである。
【図９】図９は、キャッシュデータ処理の一例を示すフローチャートである。
【図１０】図１０は、図９の続きを示すフローチャートである。
【図１１】図１１は、図１０の続きを示すフローチャートである。
【図１２】図１２は、図１１の続きを示すフローチャートである。
【図１３】図１３は、図１２の続きを示すフローチャートである。
【図１４】図１４は、図１１の続きを示すフローチャートである。
【図１５】図１５は、図１４の続きを示すフローチャートである。
【図１６】図１６は、図１５の続きを示すフローチャートである。
【図１７】図１７は、ウェイト数制御処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下に、本願の開示するキャッシュ制御方法及びキャッシュ制御装置の実施形態を図面に基づいて詳細に説明する。なお、この実施形態により本願の開示するキャッシュ制御方法及びキャッシュ制御装置が限定されるものではない。また、実施形態において同一の機能を有する構成には同一の符号を付し、重複する説明は省略される。
【００１２】
［電子機器の構成例］
図１は、一実施例のキャッシュ制御装置を含む電子機器の一例を示す図である。図１には、電子機器の主要部が示されている。図１において電子機器１０は、ＣＰＵ（Central  Processing  Unit）１１と、キャッシュメモリコントローラ（つまり、キャッシュ制御装置）１２と、キャッシュメモリ１３と、メインメモリコントローラ１４と、メインメモリ１５と、制御バス１６と、データバス１７とを有する。また、キャッシュメモリコントローラ１２は、キャッシュ制御部２１と、カウント部２２とを有する。電子機器１０は、例えば、無線基地局装置であり、この場合、図１には図示していないが、アンテナ、無線回路、及びネットワークインタフェース等を有している。また、ここでは、キャッシュメモリ１３には、Ｎ（Ｎは２以上の自然数）セットの「セットアソシアティブ方式」が適用されている。また、ここでは、電子機器１０には、「ライトバック方式」が適用されている。
【００１３】
ＣＰＵ１１は、例えば、アプリケーション（例えば、呼制御アプリケーション等）を実行する。ＣＰＵ１１は、データの書き込み（write）をする場合、そのデータを書き込むメインメモリ領域のアドレス（つまり、メインメモリアドレス）を含む「書き込みコマンド」を制御バス１６へ出力するとともに、そのデータをデータバス１７へ出力する。また、ＣＰＵ１１は、データの読み出し（read）をする場合、そのデータが記憶されているメインメモリ領域のアドレスを含む「読み出しコマンド」を制御バス１６へ出力する。
【００１４】
図２は、メインメモリアドレスの一例を示す図である。図２には、３２ビットで構成されるメインメモリアドレスが示されている。図２におけるメインメモリアドレスでは、上位の１６ビットが「タグ」に相当し、その次の８ビットが「セットインデックス」に相当し、最後の８ビットが「ブロック内オフセット」に相当する。メインアドレスのこの切り分けによれば、キャッシュメモリ１３上に８ビットで表すことができる２５６個のセットを設けることができる。すなわち、Ｎ＝２５６である。なお、上位から２４ビットをタグとセットインデックスにどのように分配するかによって、キャッシュメモリ１３上に設けることが可能なセットの数を変更することができる。また、例えば、メインメモリアドレスを６４ビットで構成する場合、少なくとも上位の３２ビットをタグとして用いてもよい。
【００１５】
図１の説明に戻り、キャッシュメモリコントローラ１２は、ＣＰＵ１１から書き込みコマンド及びデータを受け取ると、書き込みコマンドに含まれるメインメモリアドレスのタグと、そのメインメモリアドレスのセットインデックスに対応するセット内の各ウェイに保持されているタグとを比較し、一致するタグが在るか否かを判定する。一致するタグが存在する場合、キャッシュメモリコントローラ１２は、そのタグが保持されているウェイのデータをＣＰＵ１１から受け取ったデータによって更新する。一方、一致するタグが存在しない場合、キャッシュメモリコントローラ１２は、「再配置」処理を実行する。すなわち、キャッシュメモリコントローラ１２は、そのセット内で最も古いウェイに保持されているデータを、そのセットのセットインデックス及びそのウェイに保持されているタグに基づいて特定されるメインメモリアドレスに対応するメインメモリ領域に書き込む。そして、キャッシュメモリコントローラ１２は、その最も古いウェイに、ＣＰＵ１１から受け取った書き込みコマンドに含まれるメインメモリアドレスのタグとデータとを保持する。
【００１６】
また、キャッシュメモリコントローラ１２は、ＣＰＵ１１から読み出しコマンドを受け取ると、読み出しコマンドに含まれるメインメモリアドレスのタグと、そのメインメモリアドレスのセットインデックスに対応するセット内の各ウェイに保持されているタグとを比較し、一致するタグが在るか否かを判定する。一致するタグが存在する場合、キャッシュメモリコントローラ１２は、そのタグが保持されているウェイのデータをＣＰＵ１１へ送出する。一方、一致するタグが存在しない場合、キャッシュメモリコントローラ１２は、「再配置」処理を実行する。キャッシュメモリコントローラ１２は、そのセット内で最も古いウェイに保持されているデータを、そのセットのセットインデックス及びそのウェイに保持されているタグに基づいて特定されるメインメモリアドレスに対応するメインメモリ領域に書き込む。そして、キャッシュメモリコントローラ１２は、ＣＰＵ１１から受け取った読み出しコマンドに含まれるメインメモリアドレスに対応するメインメモリ領域からデータを読み出し、読み出したデータとそのメインメモリアドレスのタグとを、その最も古いウェイに書き込む。また、キャッシュメモリコントローラ１２は、その読み出したデータをＣＰＵ１１へ送出する。
【００１７】
また、キャッシュメモリコントローラ１２は、キャッシュメモリ１３上のＮ個のセットの各々での再配置回数を、「カウント周期」単位でカウントする。そして、キャッシュメモリコントローラ１２は、カウント周期単位でカウントした各セットでの再配置回数に基づいて、各セットのウェイ数を調整する。例えば、キャッシュメモリコントローラ１２は、カウントした再配置回数が「第１閾値」以上であるセットに対応する「判定参照値（以下では、「ウェイト数」と呼ぶことがある）」を増加させる。また、キャッシュメモリコントローラ１２は、カウントした再配置回数が第１閾値より小さい「第２閾値」以下であるセットに対応する判定参照値を減少させる。そして、キャッシュメモリコントローラ１２は、各セットの判定参照値の大きさに基づいて、各セットのウェイ数を、増加させるか、減少させるか、又は、維持させる。ここで、或るセットのウェイを増加させる場合、後述する「空きウェイ管理テーブル」の先頭に保持されているウェイ情報に対応するウェイがそのセットに組み入れられる。このとき、そのセットの複数のウェイは数珠つなぎに管理され、そのセットについての「ウェイ順列」の末尾に連結される。また、或るセットのウェイを減少させる場合、そのセットから外されたウェイについてのウェイ情報が、後述する「空きウェイ管理テーブル」の末尾に登録される。このとき、そのセットから外されるウェイは、そのセットの「ウェイ順列」の先頭のウェイ（つまり、そのセットで最も古いウェイ）である。ここで、後述する「空きウェイ管理テーブル」は、ＦＩＦＯ（First  In  First  Out）のキューのように機能する。なお、上記の「再配置処理」が実行される時には、再配置処理の対象であるウェイ（つまり、最も古いウェイ）は、ウェイ順列の最後尾に回され、２番目に古いウェイがウェイ順列の先頭にされる。
【００１８】
また、キャッシュメモリコントローラ１２は、「空きウェイ管理テーブル」、「先頭ポインタ管理テーブル」、「再配置回数カウントテーブル」、及び、「ウェイト数管理テーブル」を保持するとともに、順次更新する。
【００１９】
図３は、空きウェイ管理テーブルの一例を示す図である。図３に示すように、空きウェイ管理テーブルでは、「０」から「Ｍ−１」までのＭ（Ｍは２以上の自然数）個の順序と、各順序に対応する「空きウェイポインタ」とが対応づけられている。Ｍは、キャッシュメモリ１３に設けることができるウェイの全体数である。また、各順序に対応する「空きウェイポインタ」は、空いているウェイ、つまり、いずれのセットとも対応づけられていないウェイ領域の先頭ポインタを意味する。従って、図３に示す空きウェイ管理テーブルの状態は、（Ｍ−３）個のウェイが空いており３個のウェイが使用されている状態である。上記の通り、或るセットのウェイ数を１つ増加させる場合、空きウェイ管理テーブルの順序０に対応する空きウェイポンタのウェイからそのセットに組み入れられる。そして、順序１以降に対応づけられた空きウェイポインタは１つずつ順序が小さくなる。すなわち、「空きウェイ管理テーブル」は、ＦＩＦＯ（First  In  First  Out）のキューのように機能する。
【００２０】
図４は、先頭ポインタ管理テーブルの一例を示す図である。図４に示すように、先頭ポインタ管理テーブルでは、Ｎ個のセットインデックスと、各セットインデックスに対応する「先頭ポインタ」とが対応付けられている。先頭ポインタ管理テーブルにおける各セットの「先頭ポインタ」は、各セットの「ウェイ順列」の先頭ウェイのウェイ領域の先頭ポインタを意味する。上記の通り、「再配置処理」が実行される時には、再配置処理の対象であるウェイ（つまり、最も古いウェイ）は、ウェイ順列の最後尾に回され、２番目に古いウェイがウェイ順列の先頭にされる。従って、例えば、セットインデックス０のセットにおいて再配置処理が実行されると、セットインデックス０のウェイ順列において今まで先頭から２番目であったウェイの先頭ポインタによって、「UsePt0」が更新される。
【００２１】
図５は、再配置回数カウントテーブルの一例を示す図である。図５に示すように、再配置回数カウントテーブルでは、Ｎ個のセットインデックスと、各セットインデックスに対応する「再配置回数」とが対応づけられている。再配置回数カウントテーブルにおける「再配置回数」は、或るカウント周期が終了すると、そのカウント周期で各セットについてカウントされた再配置回数によって更新される。
【００２２】
図６は、ウェイト数管理テーブルの一例を示す図である。図６に示すように、ウェイト数管理テーブルでは、Ｎ個のセットインデックスと、各セットインデックスに対応する「ウェイト数」とが対応づけられている。ウェイト数管理テーブルにおける「ウェイト数」は、キャッシュメモリコントローラ１２によってウェイト数が増加又は減少されるときに更新される。
【００２３】
ここで、以上で説明したキャッシュメモリコントローラ１２による処理のうちで、再配置回数のカウント処理及び再配置回数カウントテーブルの更新処理はカウント部２２によって実行され、それ以外の処理はキャッシュ制御部２１で実行される。
【００２４】
図１の説明に戻り、キャッシュメモリ１３は、Ｍ個のウェイのそれぞれに対応する「ウェイ領域」を有している。
【００２５】
図７は、ウェイ領域のフォーマットの一例を示す図である。図７には、１つのウェイ領域に含まれる各種のマッピング領域が示されている。図７において、各マッピング領域の上に付された数字は、各マッピング領域にマッピング可能なビット数を示している。
【００２６】
図７に示すウェイ領域のフォーマットにおいて「Ｖａｌｉｄフラグ」は、Ｖａｌｉｄフラグをマッピングする領域である。「Ｖａｌｉｄフラグ」とは、ウェイ領域に保持されているタグ及びデータが有効であるか否かを示すフラグである。例えば、「Ｖａｌｉｄフラグ」が「１」であれば有効であり、「０」であれば無効である。
【００２７】
また、図７に示すウェイ領域のフォーマットにおいて「Ｄｉｒｔｙフラグ」は、Ｄｉｒｔｙフラグをマッピングする領域である。「Ｄｉｒｔｙフラグ」とは、ウェイ領域に保持されているデータが、ウェイ領域に保持されているタグにより特定されるメインメモリアドレスに保持されているデータと一致している状態か否かを示すフラグである。
【００２８】
また、図７に示すウェイ領域のフォーマットにおいて「タグ」は、ウェイ領域に保持されるデータがメインメモリにおいて保持されるべくメインメモリアドレスのタグがマッピングされる領域である。また、図７に示すウェイ領域のフォーマットにおいて「セットインデックス」は、ウェイ領域に保持されるデータがメインメモリにおいて保持されるべくメインメモリアドレスのセットインデックスがマッピングされる領域である。
【００２９】
また、図７に示すウェイ領域のフォーマットにおいて「Ｎｅｘｔ  Ｐｏｉｎｔ」は、そのウェイが対応付けられたセットの「ウェイ順列」において、そのウェイの次順ウェイの先頭ポインタがマッピングされる領域である。ここで、次順のウェイが無い場合、つまり、そのウェイがウェイ順列の最後尾ウェイである場合、「Ｎｅｘｔ  Ｐｏｉｎｔ」には０が保持される。また、図７に示すウェイ領域のフォーマットにおいて「Ｐｒｅｖ  Ｐｏｉｎｔ」は、そのウェイが対応付けられたセットの「ウェイ順列」において、そのウェイの前順ウェイの先頭ポインタがマッピングされる領域である。
【００３０】
また、図７に示すウェイ領域のフォーマットにおいて「Ｄａｔａ０」〜「Ｄａｔａ７」は、それぞれ、データがマッピングされる領域である。
【００３１】
図１の説明に戻り、メインメモリコントローラ１４は、メインメモリ１５へのデータの書き込み、及び、メインメモリ１５からのデータの読み取りを制御する。メインメモリ１５は、各メインメモリアドレスに対応する領域にデータを記憶する。
【００３２】
［電子機器の動作例］
以上の構成を有する電子機器１０の処理動作の一例について説明する。ここでは、キャッシュメモリコントローラ１２（つまり、キャッシュ制御装置）の処理動作を中心に説明する。
【００３３】
＜キャッシュメモリ初期化処理＞
図８は、キャッシュメモリ初期化処理の一例を示すフローチャートである。
【００３４】
キャッシュメモリコントローラ１２は、キャッシュメモリをゼロクリアする（ステップＳ１０１）。
【００３５】
キャッシュメモリコントローラ１２は、空きウェイテーブルを初期化する（ステップＳ１０２）。すなわち、キャッシュメモリがゼロクリアされているので、空きウェイテーブルには、キャッシュメモリ１３上のＭ個のウェイの各先頭ポインタが登録され、空きウェイ数はＭとされる。
【００３６】
キャッシュメモリコントローラ１２は、先頭ポインタ管理テーブルを初期化する（ステップＳ１０３）。すなわち、先頭ポインタ管理テーブルにおける各セットインデックスに対応する先頭ポインタにはすべて０が入力される。
【００３７】
＜キャッシュデータ処理（ウェイ数調整処理を含む）＞
図９から図１６は、キャッシュデータ処理の一例を示すフローチャートである。
【００３８】
キャッシュメモリコントローラ１２は、コマンドを受け取ったか否かを判定する（ステップＳ３０１）。キャッシュメモリコントローラ１２は、コマンドを受け取るまで待っている（ステップＳ３０１否定）。
【００３９】
コマンドを受け取ると（ステップＳ３０１肯定）、キャッシュメモリコントローラ１２は、ステップＳ３０２の処理を行う。すなわち、キャッシュメモリコントローラ１２は、受け取ったコマンドが読み出しコマンドか書き込みコマンドか特定する。また、キャッシュメモリコントローラ１２は、受け取ったコマンドに含まれるメインメモリアドレスから、タグ及びセットインデックスをそれぞれ抽出する。
【００４０】
キャッシュメモリコントローラ１２は、先頭ポインタ管理テーブルにて、抽出したセットインデックスに対応付けられた先頭ポインタを取得する（ステップＳ３０３）。
【００４１】
キャッシュメモリコントローラ１２は、抽出したセットインデックスの示すセットを、「対象セット」に設定する（ステップＳ３０４）。
【００４２】
キャッシュメモリコントローラ１２は、ステップＳ３０３で取得した先頭ポインタがゼロであるか否かを判定する（ステップＳ３０５）。例えば、上記のキャッシュメモリ初期化処理が行われた直後では、取得した先頭ポインタはゼロとなっている。
【００４３】
取得した先頭ポインタがゼロである場合（ステップＳ３０５肯定）、キャッシュメモリコントローラ１２は、空きウェイがあるか否かを判定する（ステップＳ３０６）。すなわち、キャッシュメモリコントローラ１２は、空きウェイ管理テーブルを参照して、空きウェイ数が１以上であるか否かを判定する。
【００４４】
空きウェイがある場合（ステップＳ３０６肯定）、キャッシュメモリコントローラ１２は、空きウェイ管理テーブルの順序０の空きウェイポインタを取得する（ステップＳ３０７）。
【００４５】
キャッシュメモリコントローラ１２は、ステップＳ３０２で抽出したセットインデックスとステップＳ３０７で取得した空きウェイポインタとを対応付けて、先頭ポインタ管理テーブルに記憶する（ステップＳ３０８）。
【００４６】
キャッシュメモリコントローラ１２は、取得した空きウェイポインタの示すウェイを、「対象ウェイ」に設定する（ステップＳ３０９）。
【００４７】
キャッシュメモリコントローラ１２は、ステップＳ３１０の処理を行う。すなわち、キャッシュメモリコントローラ１２は、対象ウェイが示すウェイの「Next  Point」をゼロに設定する。また、キャッシュメモリコントローラ１２は、対象ウェイの「Prev  Point」をゼロに設定する。また、キャッシュメモリコントローラ１２は、対象ウェイの「タグ」及び「セットインデックス」を、抽出したタグ及びセットインデックスで更新する。また、キャッシュメモリコントローラ１２は、コマンドに含まれるメインメモリアドレスに保持されているデータを読み出し、読み出したデータで、対象ウェイの「データ領域」を更新する。また、キャッシュメモリコントローラ１２は、対象ウェイの「Ｄｉｒｔｙフラグ」をゼロに更新し、「Ｖａｌｉｄフラグ」を１に更新する。
【００４８】
空きウェイが無い場合（ステップＳ３０６否定）、キャッシュメモリコントローラ１２は、メインメモリに対してコマンドに応じた処理を実行させる（ステップＳ３１１）。
【００４９】
取得した先頭ポインタがゼロでない場合（ステップＳ３０５否定）、キャッシュメモリコントローラ１２は、ステップＳ３０３で取得した先頭ポインタの示すウェイを、「対象ウェイ」に設定する（ステップＳ３１２）。
【００５０】
キャッシュメモリコントローラ１２は、キャッシュメモリ１３の対象ウェイに保持されている情報を参照する（ステップＳ３１３）。
【００５１】
キャッシュメモリコントローラ１２は、対象ウェイのＶａｌｉｄフラグが１か否かを判定する（ステップＳ３１４）。取得した先頭ポインタがゼロでないにも関わらず（ステップＳ３０５否定）、Ｖａｌｉｄフラグが１以外（つまり、ゼロ）の場合（ステップＳ３１４否定）、異常と認められるため、処理フローは終了する。
【００５２】
Ｖａｌｉｄフラグが１である場合（ステップＳ３１４肯定）、キャッシュメモリコントローラ１２は、ステップＳ３０３で抽出したタグと、対象ウェイに保持されているタグとは一致するか否かを判定する（ステップＳ３１５）。
【００５３】
ステップＳ３０３で抽出したタグと、対象ウェイに保持されているタグとは一致する場合（ステップＳ３１５肯定）、キャッシュメモリコントローラ１２は、ステップＳ３１６の処理を行う。すなわち、ステップＳ３０２で特定したコマンドが読み出しコマンドである場合、キャッシュメモリコントローラ１２は、対象ウェイに保持されているデータをデータバス１７へ送出する。これにより、データはＣＰＵ１１へ送出される。また、ステップＳ３０２で特定したコマンドが書き込みコマンドである場合、キャッシュメモリコントローラ１２は、書き込みコマンドとともに受け取ったデータを、対象ウェイに書き込む。
【００５４】
ステップＳ３０３で抽出したタグと、対象ウェイに保持されているタグとは一致しない場合（ステップＳ３１５否定）、キャッシュメモリコントローラ１２は、対象ウェイの「Next  Point」がゼロか否かを判定する（ステップＳ３１７）。
【００５５】
対象ウェイの「Next  Point」がゼロでない場合（ステップＳ３１７否定）、キャッシュメモリコントローラ１２は、「Next  Point」の示すウェイを、「対象ウェイ」に設定する（ステップＳ３１８）。そして、処理フローは、Ｐ１へ戻る。
【００５６】
対象ウェイの「Next  Point」がゼロである場合（ステップＳ３１７肯定）、キャッシュメモリコントローラ１２は、ウェイト数管理テーブルにて、対象セットに対応するウェイト数は、プラス、マイナス、ゼロのいずれであるか判定する（ステップＳ３１９）。
【００５７】
ステップＳ３１９で対象セットに対応するウェイト数がプラスである場合、キャッシュメモリコントローラ１２は、空きウェイがあるか否かを判定する（ステップＳ３２０）。空きウェイが無い場合（ステップＳ３２０否定）、処理フローはＰ４へ移行する。
【００５８】
空きウェイがある場合（ステップＳ３２０肯定）、キャッシュメモリコントローラ１２は、空きウェイ管理テーブルの順序０の空きウェイポインタを取得する（ステップＳ３２１）。
【００５９】
キャッシュメモリコントローラ１２は、対象ウェイの「Next  Point」を、ステップＳ３２１で取得した空きウェイポインタで更新する（ステップＳ３２２）。
【００６０】
キャッシュメモリコントローラ１２は、ステップＳ３２１で取得した空きウェイポインタの示すウェイを、「対象ウェイ」に設定する（ステップＳ３２３）。
【００６１】
キャッシュメモリコントローラ１２は、ステップＳ３２４の処理を行う。すなわち、キャッシュメモリコントローラ１２は、対象ウェイの「Next  Point」をゼロに設定する。また、キャッシュメモリコントローラ１２は、対象ウェイの「Prev  Point」を、１つ前の対象ウェイの先頭ポインタに設定する。また、キャッシュメモリコントローラ１２は、対象ウェイの「タグ」及び「セットインデックス」を、抽出したタグ及びセットインデックスで更新する。また、キャッシュメモリコントローラ１２は、コマンドに含まれるメインメモリアドレスに保持されているデータを読み出し、読み出したデータで、対象ウェイの「データ領域」を更新する。また、キャッシュメモリコントローラ１２は、対象ウェイの「Ｄｉｒｔｙフラグ」をゼロに更新し、「Ｖａｌｉｄフラグ」を１に更新する。
【００６２】
ステップＳ３１９で対象セットに対応するウェイト数がゼロである場合、キャッシュメモリコントローラ１２は、先頭ポインタ管理テーブルにて対象セットに対応付けられた先頭ポインタの示すウェイを、対象ウェイに設定する（ステップＳ３２５）。
【００６３】
キャッシュメモリコントローラ１２は、対象ウェイに保持されている情報を参照する（ステップＳ３２６）。
【００６４】
キャッシュメモリコントローラ１２は、対象ウェイのＤｉｒｔｙフラグが１であるか否かを判定する（ステップＳ３２７）。対象ウェイのＤｉｒｔｙフラグが１でない（つまり、ゼロ）場合（ステップＳ３２７否定）、処理ステップはステップＳ３２９へ進む。
【００６５】
対象ウェイのＤｉｒｔｙフラグが１である場合（ステップＳ３２７肯定）、キャッシュメモリコントローラ１２は、対象ウェイの「データ領域」に保持されているデータを、メインメモリへ出力する（ステップＳ３２８）。
【００６６】
キャッシュメモリコントローラ１２は、対象ウェイを「再利用ウェイ」として保持する（ステップＳ３２９）。
【００６７】
キャッシュメモリコントローラ１２は、対象セットのウェイ順列において対象ウェイの次のウェイを、「対象ウェイ」として設定する（ステップＳ３３０）。
【００６８】
キャッシュメモリコントローラ１２は、対象ウェイの「Prev  Point」を、ゼロに更新する（ステップＳ３３１）。
【００６９】
キャッシュメモリコントローラ１２は、先頭ポインタ管理テーブルにて対象セットに対応付けられた先頭ポインタを、対象ウェイの先頭ポインタで更新する（ステップＳ３３２）。
【００７０】
キャッシュメモリコントローラ１２は、対象セットのウェイ順列において最後尾のウェイの「Next  Point」を、再利用ウェイの先頭ポインタで更新する（ステップＳ３３３）。
【００７１】
キャッシュメモリコントローラ１２は、ステップＳ３３４の処理を行う。すなわち、キャッシュメモリコントローラ１２は、対象セットのウェイ順列において最後尾のウェイの先頭ポインタで、再利用ウェイの「Prev  Point」を更新する。また、キャッシュメモリコントローラ１２は、再利用ウェイの「Next  Point」をゼロに更新する。また、キャッシュメモリコントローラ１２は、コマンドに含まれるメインメモリアドレスに保持されているデータを読み出し、読み出したデータで、再利用ウェイの「データ領域」を更新する。また、キャッシュメモリコントローラ１２は、再利用ウェイの「Ｄｉｒｔｙフラグ」をゼロに更新し、「Ｖａｌｉｄフラグ」を１に更新する。
【００７２】
キャッシュメモリコントローラ１２は、ステップＳ３３５の処理を行う。すなわち、ステップＳ３０２で特定したコマンドが読み出しコマンドである場合、キャッシュメモリコントローラ１２は、再利用ウェイに保持されているデータをデータバスへ送出する。これにより、データはＣＰＵ１１へ送出される。また、ステップＳ３０２で特定したコマンドが書き込みコマンドである場合、キャッシュメモリコントローラ１２は、書き込みコマンドとともに受け取ったデータを、再利用ウェイに書き込む。
【００７３】
キャッシュメモリコントローラ１２は、再配置回数カウントテーブルで対象セットに対応付けられた再配置回数を１つインクリメントする（ステップＳ３３６）。そして、処理ステップはＰ０へ戻る。
【００７４】
ステップＳ３１９で対象セットに対応するウェイト数がマイナスである場合、キャッシュメモリコントローラ１２は、先頭ポインタ管理テーブルにて対象セットに対応付けられた先頭ポインタの示すウェイを、対象ウェイに設定する（ステップＳ３３７）。
【００７５】
キャッシュメモリコントローラ１２は、対象ウェイに保持されている情報を参照する（ステップＳ３３８）。
【００７６】
キャッシュメモリコントローラ１２は、対象ウェイのＤｉｒｔｙフラグが１であるか否かを判定する（ステップＳ３３９）。対象ウェイのＤｉｒｔｙフラグが１でない（つまり、ゼロ）場合（ステップＳ３３９否定）、処理ステップはステップＳ３４１へ進む。
【００７７】
対象ウェイのＤｉｒｔｙフラグが１である場合（ステップＳ３３９肯定）、キャッシュメモリコントローラ１２は、対象ウェイの「データ領域」に保持されているデータを、メインメモリへ出力する（ステップＳ３４０）。
【００７８】
キャッシュメモリコントローラ１２は、対象ウェイの先頭ポインタを、空きウェイ管理テーブルにて対象セットと対応付けて登録する（ステップＳ３４１）。
【００７９】
キャッシュメモリコントローラ１２は、対象セットのウェイ順列において対象ウェイの次のウェイを、「対象ウェイ」として設定する（ステップＳ３４２）。
【００８０】
キャッシュメモリコントローラ１２は、先頭ポインタ管理テーブルにて対象セットに対応付けられた先頭ポインタを、対象ウェイの先頭ポインタで更新する（ステップＳ３４３）。
【００８１】
キャッシュメモリコントローラ１２は、対象ウェイの「Prev  Point」を、ゼロに更新する（ステップＳ３４４）。
【００８２】
キャッシュメモリコントローラ１２は、対象ウェイに保持されている情報を参照する（ステップＳ３４５）。
【００８３】
キャッシュメモリコントローラ１２は、対象ウェイのＤｉｒｔｙフラグが１であるか否かを判定する（ステップＳ３４６）。対象ウェイのＤｉｒｔｙフラグが１でない（つまり、ゼロ）場合（ステップＳ３４６否定）、処理ステップはステップＳ３４８へ進む。
【００８４】
対象ウェイのＤｉｒｔｙフラグが１である場合（ステップＳ３４６肯定）、キャッシュメモリコントローラ１２は、対象ウェイの「データ領域」に保持されているデータを、メインメモリへ出力する（ステップＳ３４７）。
【００８５】
キャッシュメモリコントローラ１２は、対象ウェイを「再利用ウェイ」として保持する（ステップＳ３４８）。
【００８６】
キャッシュメモリコントローラ１２は、対象セットのウェイ順列において対象ウェイの次のウェイを、「対象ウェイ」として設定する（ステップＳ３４９）。
【００８７】
キャッシュメモリコントローラ１２は、対象ウェイの「Prev  Point」を、ゼロに更新する（ステップＳ３５０）。
【００８８】
キャッシュメモリコントローラ１２は、先頭ポインタ管理テーブルにて対象セットに対応付けられた先頭ポインタを、対象ウェイの先頭ポインタで更新する（ステップＳ３５１）。
【００８９】
キャッシュメモリコントローラ１２は、対象セットのウェイ順列において最後尾のウェイの「Next  Point」を、再利用ウェイの先頭ポインタで更新する（ステップＳ３５２）。
【００９０】
キャッシュメモリコントローラ１２は、ステップＳ３５３の処理を行う。すなわち、キャッシュメモリコントローラ１２は、対象セットのウェイ順列において最後尾のウェイの先頭ポインタで、再利用ウェイの「Prev  Point」を更新する。また、キャッシュメモリコントローラ１２は、再利用ウェイの「Next  Point」をゼロに更新する。また、キャッシュメモリコントローラ１２は、コマンドに含まれるメインメモリアドレスに保持されているデータを読み出し、読み出したデータで、再利用ウェイの「データ領域」を更新する。また、キャッシュメモリコントローラ１２は、再利用ウェイの「Ｄｉｒｔｙフラグ」をゼロに更新し、「Ｖａｌｉｄフラグ」を１に更新する。
【００９１】
キャッシュメモリコントローラ１２は、ステップＳ３５４の処理を行う。すなわち、ステップＳ３０２で特定したコマンドが読み出しコマンドである場合、キャッシュメモリコントローラ１２は、再利用ウェイに保持されているデータをデータバスへ送出する。これにより、データはＣＰＵ１１へ送出される。また、ステップＳ３０２で特定したコマンドが書き込みコマンドである場合、キャッシュメモリコントローラ１２は、書き込みコマンドとともに受け取ったデータを、再利用ウェイに書き込む。
【００９２】
キャッシュメモリコントローラ１２は、ウェイト数管理テーブルで対象セットに対応付けられたウェイト数を、ゼロに更新する（ステップＳ３５５）。そして、処理ステップはＰ０へ戻る。
【００９３】
なお、以上の説明では、対象セットに対応するウェイト数がマイナスである場合、先頭ポインタ管理テーブルにて対象セットに対応付けられた先頭ポインタの示すウェイが対象セットから外された後に、「再配置処理」が行われるものとして説明を行ったが、これに限定されない。例えば、ステップＳ３４５〜ステップＳ３５４の処理ステップを無くし、ステップＳ３５５の後に処理ステップがＰ４に戻る、処理フロートとされてもよい。
【００９４】
＜ウェイト数制御処理＞
図１７は、ウェイト数制御処理の一例を示すフローチャートである。図１７に示す処理フローは、例えば、１つのカウント周期が終了する度に実行される。
【００９５】
キャッシュメモリコントローラ１２は、セットインデックスＳＩ＝０のセットを、対象セットに設定する（ステップＳ５０１）。
【００９６】
キャッシュメモリコントローラ１２は、再配置回数カウントテーブルにて対象セットに対応付けられた再配置回数を参照する（ステップＳ５０２）。
【００９７】
キャッシュメモリコントローラ１２は、参照した再配置回数が、２以上、ゼロ、１のいずれであるか判定する（ステップＳ５０３）。ここで、「２」は、上記の「第１閾値」に対応し、「ゼロ」は、上記の「第２閾値」に対応する。
【００９８】
ステップＳ５０３で再配置回数が２以上である場合、キャッシュメモリコントローラ１２は、空きウェイ管理テーブルの空きウェイ数がゼロより大きいか否かを判定する（ステップＳ５０４）。
【００９９】
空きウェイ数がゼロより大きい場合（ステップＳ５０４肯定）、キャッシュメモリコントローラ１２は、ウェイト数管理テーブルにて対象セットに対応付けられているウェイト数を１つインクリメントする（ステップＳ５０５）。
【０１００】
キャッシュメモリコントローラ１２は、再配置回数カウントテーブルにて対象セットに対応付けられた再配置回数をゼロに更新する（ステップＳ５０６）。
【０１０１】
キャッシュメモリコントローラ１２は、セットインデックスＳＩ＝ＳＩ＋１のセットを、対象セットに設定する（ステップＳ５０７）。
【０１０２】
キャッシュメモリコントローラ１２は、セットインデックスＳＩがＮより大きいか否かを判定する（ステップＳ５０９）。セットインデックスＳＩがＮより大きい場合（ステップＳ５０９肯定）、図１７の処理フローは終了する。セットインデックスＳＩがＮ以下である場合（ステップＳ５０９否定）、処理フローはＰ０へ移行する。
【０１０３】
空きウェイ数がゼロである場合（ステップＳ５０４否定）、キャッシュメモリコントローラ１２は、再配置回数カウントテーブルにて対象セットに対応付けられた再配置回数を−１に更新する（ステップＳ５０８）。そして、処理ステップは、ステップＳ５０７へ進む。
【０１０４】
ステップＳ５０３で再配置回数がゼロである場合、キャッシュメモリコントローラ１２は、ウェイト数管理テーブルにて対象セットに対応付けられているウェイト数がゼロより大きいか否かを判定する（ステップＳ５１０）。ウェイト数管理テーブルにて対象セットに対応付けられているウェイト数がゼロ以下である場合（ステップＳ５１０否定）、処理ステップはＰ１へ進む。
【０１０５】
キャッシュメモリコントローラ１２は、ウェイト数管理テーブルにて対象セットに対応付けられているウェイト数がゼロより大きい場合（ステップＳ５１０肯定）、ウェイト数管理テーブルにて対象セットに対応付けられているウェイト数を１つデクリメントする（ステップＳ５１１）。そして、処理ステップはＰ１へ進む。
【０１０６】
ステップＳ５０３で再配置回数が１である場合、処理ステップはＰ１へ進む。
【０１０７】
以上のように本実施例によれば、キャッシュメモリコントローラ（つまり、キャッシュ制御装置）１２は、カウント部２２とキャッシュ制御部２１とを有し、セットアソシアティブ方式のキャッシュメモリ１３を制御する。カウント部２２は、キャッシュメモリ１３上の複数のセットの各々での再配置回数をカウントする。キャッシュ制御部２１は、カウント部２２でカウントした各セットでの再配置回数に基づいて、各セットのウェイ数を調整する。
【０１０８】
例えば、キャッシュ制御部２１は、カウント部２２でカウントした再配置回数が第１閾値以上であるセットに対応するウェイト数を増加させる一方、カウントした再配置回数が第１閾値より小さい第２閾値以下であるセットに対応するウェイト数を減少させる。そして、キャッシュ制御部２１は、ウェイト数の大きさに基づいて、各セットのウェイ数を、増加させるか、減少させるか、又は、維持させる。
【０１０９】
このキャッシュ制御装置の構成により、データの読み出し及び書き込みが或るセットに集中する場合でも、そのセットのウェイ数を増加させることができるので、そのセットのヒット率が低下することを防止することができる。すなわち、キャッシュのヒット率を向上させることができる。従って、このキャッシュメモリ制御装置を基地局に設けることにより、各ユーザのユーザ設定データが記憶されているメインメモリ領域に対応するセットが一部のセットに集中する場合でも、アプリケーションの変更等を行うことなく、呼処理の処理効率が低下することを防止することができる。
【０１１０】
また、キャッシュ制御部２１は、複数のセットのうちの第１セットのウェイ数を減少させる場合、第１セットから外されたウェイを空きウェイ管理テーブルに登録する。また、キャッシュ制御部２１は、複数のセットのうちの第２セットのウェイ数を増加させる場合、空きウェイ管理テーブルに登録されているウェイを第２セットに組み入れる。
【０１１１】
このキャッシュ制御装置の構成により、空きウェイ管理テーブルによって空きウェイを管理することができるので、増加対象のウェイを容易に選択することができる。
【０１１２】
また、空きウェイ管理テーブルは、ＦＩＦＯに従って空きウェイを出力する。これにより、増加対象のウェイの選択をさらに容易にすることができる。
【符号の説明】
【０１１３】
１０  電子機器
１１  ＣＰＵ
１２  キャッシュメモリコントローラ
１３  キャッシュメモリ
１４  メインメモリコントローラ
１５  メインメモリ
１６  制御バス
１７  データバス
２１  キャッシュ制御部
２２  カウント部
【図１】
0006390435.tif 000002
【図２】
0006390435.tif 000003
【図３】
0006390435.tif 000004
【図４】
0006390435.tif 000005
【図５】
0006390435.tif 000006
【図６】
0006390435.tif 000007
【図７】
0006390435.tif 000008
【図８】
0006390435.tif 000009
【図９】
0006390435.tif 000010
【図１０】
0006390435.tif 000011
【図１１】
0006390435.tif 000012
【図１２】
0006390435.tif 000013
【図１３】
0006390435.tif 000014
【図１４】
0006390435.tif 000015
【図１５】
0006390435.tif 000016
【図１６】
0006390435.tif 000017
【図１７】
0006390435.tif 000018