(57)【要約】【課題】キャッシュミス発生時に迅速で正確に対応でき、無駄なメモリを不要にする。【解決手段】キャッシュデータ記憶部２Ｂおよび行アドレス記憶部２Ａを有するキャッシュメモリ部２と、行アドレス入力部３およびキャッシュデータに発生したキャッシュミスの位置を判定するミス判定部５を備えるキャッシュコントローラ４と、を備え、キャッシュコントローラ４は、キャッシュデータ記憶部２Ｂにキャッシュライン単位で行方向に記憶されたキャッシュデータに対して列方向に任意の境界を設定する境界設定部１１と、行アドレス入力部３を介してＣＰＵ１より入力された行アドレスと境界設定部１１により設定された任意の境界の行アドレスとを比較して行アドレスのミスが発生した位置を検出する位置検出部１２と、検出されたキャッシュミスが発生位置Ｐ１，Ｐ２が境界２Ｄ（２Ｅ）の後である場合にはそのキャッシュラインと次のキャッシュラインのキャッシュデータまでをも投機的に入れ替えるキャッシュデータ投機的入替部１３とを備える。【選択図】図１
2008102745.tif 000002
【特許請求の範囲】
【請求項１】
行と列のマトリクスで構成されたメモリセルアレイに対してパラレルポートを介して列方向に接続されると共にＣＰＵからの命令に基づいて行単位のデータをキャッシュライン単位のキャッシュデータとして一斉に転送可能なキャッシュデータ記憶部および該キャッシュデータ記憶部に記憶された前記キャッシュライン単位の前記キャッシュデータの行アドレスを記憶する行アドレス記憶部を有するキャッシュメモリ部と、
前記ＣＰＵから供給される前記行アドレスを入力する行アドレス入力部と、前記行アドレス入力部に入力された前記行アドレスを用いて前記キャッシュメモリ部に記憶された前記キャッシュデータに発生したキャッシュミスの位置を判定するミス判定部と、を少なくとも備えるキャッシュコントローラと、を備え、
前記キャッシュコントローラに設けられて、前記キャッシュデータ記憶部に前記キャッシュライン単位で行方向に記憶された前記キャッシュデータに対して列方向に任意の境界を設定する境界設定部と、
前記キャッシュコントローラに設けられて、前記行アドレス入力部を介して前記ＣＰＵより入力された前記行アドレスと前記境界設定部により設定された前記任意の境界の行アドレスとを比較して前記行アドレスのミスが発生した位置を検出する位置検出部と、
前記キャッシュコントローラに設けられて、前記位置検出部により検出された前記キャッシュミスが発生した位置が前記境界設定部により設定された前記境界の後である場合にはそのキャッシュラインばかりでなく次のキャッシュラインをも含めて２ライン分のキャッシュデータを投機的に入れ替えると共に前記キャッシュミスの発生した位置が前記境界の前である場合には次のキャッシュラインのキャッシュデータを入れ替えないでそのキャッシュラインのキャッシュデータのみを入れ替えるキャッシュデータ投機的入替部と、
を備えることを特徴とする命令キャッシュメモリのプリフェッチ機構。
【請求項２】
前記境界設定部は前記キャッシュメモリ部に記憶されたキャッシュライン上のオフセットの位置に基づいて前記境界の位置を設定すると共に、前記位置検出部は前記キャッシュミスの発生アドレスが前記オフセットの前か後かを検出することを特徴とする請求項１に記載の命令キャッシュメモリのプリフェッチ機構。
【請求項３】
前記境界設定部は、次のキャッシュラインまでも投機的に入れ替えるか否かの前記境界の設定位置をプログラムの分岐間隔に応じて動的に設定することを特徴とする請求項１に記載の命令キャッシュメモリのプリフェッチ機構。
【請求項４】
前記キャッシュコントローラは、分岐命令以外の命令実行数をカウントして分岐命令が発生するたびにカウントした命令実行数を記録してリセットされるカウンタをさらに備えると共に、前記境界設定部は、前記カウンタによりカウントされて収集された統計情報としての前記命令実行数に基づいて前記境界の設定位置を動的に設定することを特徴とする請求項３に記載の命令キャッシュメモリのプリフェッチ機構。
【請求項５】
前記キャッシュコントローラは、前記カウンタによりカウントされた前記命令実行数を記録するためのテーブルをさらに備えることを特徴とする請求項４に記載の命令キャッシュメモリのプリフェッチ機構。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、命令キャッシュメモリのプリフェッチ機構に関し、特に投機的なキャッシュリフィルを適用した命令キャッシュメモリのプリフェッチ機構に関する。
【背景技術】
【０００２】
一般に、メモリのアクセス速度を高めるために、ＣＰＵ（Central Processing Unit―中央処理装置―）などの制御回路と主メモリとの間にバスを介してキャッシュメモリを接続し、キャッシュメモリからデータのアクセスを行なう方式が用いられている。この方式では、メモリアクセスを行なうごとに、入力アドレス中の行アドレスとキャッシュメモリに記憶されたデータの行アドレスとの比較、すなわちタグ（ＴＡＧ）比較を行ない、タグが不一致（キャッシュミスヒット）の場合は、メモリから目的のデータをアクセスすると同時にキャッシュメモリへの行データの転送を行なっている。ところで、近年、高速バスインタフェースが提案されてキャッシュメモリとの併用も提案されている。
【０００３】
この高速バスインタフェースをキャッシュメモリと併用した場合、タグ比較時間やキャッシュミスヒットの際のメモリアクセス時間が必要となるためこれらの時間が原因（ネック）となって、高速バスインタフェースの性能を生かす上で十分なアクセス速度が得られないことがあった。これを回避するために、キャッシュミスヒットが生じた場合にパラレルポートを介してメモリセルアレイからキャッシュデータ記憶手段に対して、該当する行データを一斉に転送する構成も提案されている（特許文献１参照）。
【０００４】
従来のプリフェッチ機構は、図７に示すように、命令読み出しアドレスを出力するＣＰＵ１と、キャッシュデータを記憶するキャッシュメモリ部２と、ＣＰＵ１から出力される命令読み出しアドレスをラッチする行アドレス入力部３と、図示されないメモリセルアレイが接続される外部バスに接続されると共にＣＰＵ１とキャッシュメモリ部２との間でキャッシュデータのやりとりを制御するキャッシュコントローラ４とを備えている。キャッシュメモリ部２は、ＣＰＵ１から行アドレス入力部３に入力された行アドレスにおけるタグ（ＴＡＧ）部３Ａやインデクス部３Ｂを記憶するタグＲＡＭ（Random Access Memory）等の行アドレス記憶部２Ａと、キャッシュＲＡＭ等のキャッシュデータ記憶部２Ｂと、を備える。キャッシュコントローラ４は、行アドレス入力部３に入力された行アドレスのタグ部３Ａと行アドレス記憶部２Ａに記憶されたタグを比較してタグが不一致の場合にキャッシュミスヒットを判定するミス判定部５を備えている。
【０００５】
キャッシュコントローラ４は、ミス判定部５がキャッシュミスヒットを判定した場合には、キャッシュデータデータ記憶部２Ｂにおけるキャッシュミスヒットと判定されたその行アドレスに対応するラインのキャッシュデータを入れ替えている。このような従来の命令キャッシュメモリのプリフェッチ機構においては、命令キャッシュミス発生時のキャッシュミスペナルティを削減するために、ミスの発生したキャッシュラインに隣接するアドレスのラインを予めキャッシュに格納する投機的リフィル（speculative refill）を行なうか、もしくは、プリフェッチバッファを設けてこのプリフェッチバッファに格納しておく手法を提案している。
【０００６】
しかしながら、従来のプリフェッチ機構は、キャッシュメモリに投機的リフィルを適用してミスの発生したアドレスラインの隣接ラインを実際に入れ替えてしまうと、プログラムカウンタがそのラインに到達しない場合のいわゆるペナルティ（penalty―不利益や動作の損失［disadvantage/loss］―）が大きいという問題があった。また、命令キャッシュミス発生時のキャッシュミスペナルティを削減するために、キャッシュデータを格納するためのプリフェッチバッファを予め設けておくことは、余分なメモリを必要とするという問題があった。
【特許文献１】特開平６−１１０７７９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、上記課題に鑑みてなされたものであり、キャッシュミス発生時の対応を正確で迅速に行なうことができると共に無駄なメモリを設ける必要のない命令キャッシュメモリのプリフェッチ機構を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の基本概念に相当する第１構成に係る命令キャッシュメモリのプリフェッチ機構は、行と列のマトリクスで構成されたメモリセルアレイに対してパラレルポートを介して列方向に接続されると共にＣＰＵからの命令に基づいて行単位のデータをキャッシュライン単位のキャッシュデータとして一斉に転送可能なキャッシュデータ記憶部および該キャッシュデータ記憶部に記憶された前記キャッシュライン単位の前記キャッシュデータの行アドレスを記憶する行アドレス記憶部を有するキャッシュメモリ部と、前記ＣＰＵから供給される前記行アドレスを入力する行アドレス入力部と、前記行アドレス入力部に入力された前記行アドレスを用いて前記キャッシュメモリ部に記憶された前記キャッシュデータに発生したキャッシュミスの位置を判定するミス判定部と、を少なくとも備えるキャッシュコントローラと、を備え、前記キャッシュコントローラに設けられて、前記キャッシュデータ記憶部に前記キャッシュライン単位で行方向に記憶された前記キャッシュデータに対して列方向に任意の境界を設定する境界設定部と、前記キャッシュコントローラに設けられて、前記行アドレス入力部を介して前記ＣＰＵより入力された前記行アドレスと前記境界設定部により設定された前記任意の境界の行アドレスとを比較して前記行アドレスのミスが発生した位置を検出する位置検出部と、前記キャッシュコントローラに設けられて前記位置検出部により検出された前記キャッシュミスが発生した位置が前記境界設定部により設定された前記境界の後である場合にはそのキャッシュラインばかりでなく次のキャッシュラインをも含めて２ライン分のキャッシュデータを投機的に入れ替えると共に前記キャッシュミスの発生した位置が前記境界の前である場合には次のキャッシュラインのキャッシュデータを入れ替えないでそのキャッシュラインのキャッシュデータのみを入れ替えるキャッシュデータ投機的入替部と、を備えることを特徴としている。
【発明の効果】
【０００９】
上記構成を有する命令キャッシュメモリのプリフェッチ機構によれば、キャッシュミス発生時の対応を正確で迅速に行なうことができると共に無駄なメモリを設ける必要のないプリフェッチ機構を提供することができる。
【発明を実施するための最良の形態】
【００１０】
［第１実施形態］
以下、添付図面を参照しながら、本発明に係る命令キャッシュメモリのプリフェッチ機構の実施形態について詳細に説明する。まず、本発明の基本構成としての第１実施形態について図１を参照しながら説明する。なお、従来の構成を示す図７に示された構成と同一もしくは相当する構成要素は同一の参照符号を付している。
【００１１】
図１に示すように、本発明の基本概念に相当する第１実施形態に係る命令キャッシュメモリのプリフェッチ機構１０は、行と列のマトリクスで構成されたメモリセルアレイ６に対してパラレルポート７および外部バス８を介して行方向のデータ毎に伝送可能なように列方向に接続されている。プリフェッチ機構１０は、ＣＰＵ１からの命令に基づいてキャッシュメモリ部２を制御するキャッシュコントローラ４を備える。キャッシュメモリ部２は、キャッシュデータ記憶部２Ｂに記憶されたキャッシュライン単位のキャッシュデータの行アドレスを記憶する行アドレス記憶部２Ａと、行単位のデータをキャッシュライン単位のキャッシュデータとして一斉に転送可能なキャッシュデータ記憶部２Ｂを有する。
【００１２】
キャッシュコントローラ４は、ＣＰＵ１から供給される行アドレスを入力する行アドレス入力部３に入力された行アドレスを用いてキャッシュメモリ部２に記憶されたキャッシュデータに発生したキャッシュミスの位置を判定するミス判定部５を少なくとも備える。また、キャッシュコントローラ４は、キャッシュデータ記憶部２Ｂにキャッシュライン単位で行方向に記憶されたキャッシュデータに対して列方向に任意の境界２Ｄを設定する境界設定部１１と、行アドレス入力部３を介してＣＰＵ１より入力された行アドレスと境界設定部１１により設定された任意の境界の行アドレスとを比較して行アドレスのミスが発生した位置を検出する位置検出部１２と、キャッシュデータ投機的入替部１３とを備えている。
【００１３】
キャッシュデータ投機的入替部１３は、位置検出部１２により検出されたキャッシュミスが発生した位置Ｐ１が境界設定部１１により設定された境界２Ｄの後である場合には、そのキャッシュラインばかりでなく、次のキャッシュラインをも含めて２ライン分のキャッシュデータを投機的に入れ替える。また、キャッシュデータ投機的入替部１３は、キャッシュミスの発生した位置Ｐ２が境界の前である場合には、次のキャッシュラインのキャッシュデータを入れ替えないで、そのキャッシュラインのキャッシュデータのみを入れ替えるものである。
【００１４】
上記のように構成することにより、キャッシュメモリにキャッシュミスが発生したときでも、ミスの発生したキャッシュラインのみを入れ替えれば対応できる場合と、ミスの発生したキャッシュラインとその次のキャッシュラインを投機的に入れ替えなければならない場合とで、キャッシュミスが発生した際の対応を的確に分けることができ、キャッシュミスの発生に対して正確で迅速に対応することができる。また、キャッシュデータを格納するために、プリフェッチバッファを予め設けておかなくともよいので、余分なメモリを必要とせず。また、無駄なメモリを設ける必要がなくなる。
【００１５】
［第２実施形態］
次に、本発明のより具体的な構成としての第２実施形態に係る命令キャッシュメモリのプリフェッチ機構について、図２および図３を参照しながら説明する。第２実施形態によるプリフェッチ機構は、第１実施形態によるプリフェッチ機構において、境界設定部１１がキャッシュメモリ部２に記憶されたキャッシュライン上のオフセットの位置に基づいて境界２Ｄの位置を設定すると共に、位置検出部１２はキャッシュミスの発生アドレスがオフセットの前か後かを検出することを特徴としている。キャッシュデータ入替部１３は、位置検出部１２により検出されたオフセットの位置で境界２Ｄの設定を検知して、オフセットより前でミス（位置Ｐ２）が発生した場合にはそのミスが含まれるキャッシュラインのキャッシュデータのみを入れ替える。また、キャッシュデータ入替部１３は、オフセットよりも後でミス（位置Ｐ１）が発生した場合には検知されたミスが含まれるキャッシュラインと次のキャッシュラインとを投機的に入れ替える。
【００１６】
図２を参照しながら、第２実施形態に係る命令キャッシュメモリのプリフェッチ機構のさらに詳細な構成を説明する。図２において、命令キャッシュミスが発生したキャッシュライン上の位置によって次のラインのリフィルを行なうか否かを判定する。すなわち、ライン上のある境界２Ｄ（オフセット）よりも後方の位置Ｐ１でミスが発生した場合のみ、次のラインを投機的にリフィルし、前方の位置Ｐ２でミスが発生した場合は次のラインの投機的リフィルを行なわない。キャッシュミス発生アドレスの境界２Ｄ（オフセット）を検出する検出回路１２と、その位置が一定のオフセットよりも後方であるかどうかを判定する判定回路５と、その判定に基づきキャッシュミスを起こしたラインのリフィルに続くラインの（投機的）リフィルをスケジュールするキャッシュコントローラ１０を備えている。
【００１７】
キャッシュラインの最先端（最小アドレス）以外でキャッシュミスが発生するということは、すなわち、その位置が分岐命令のターゲットアドレスであることを意味している。分岐先から数命令分は特に命令が実行される確率が高く、もしもミス発生位置がキャッシュラインの後方に位置する場合は、次のラインが引き続いて必要とされる可能性が高いため、ミスの発生したラインと同時に次のラインも投機的にキャッシュリフィルすることによりバスの使用効率が向上することになる。一方、前端もしくはその直後でミスが発生した場合、次のラインに到達する前に別のアドレスへ分岐する可能性も高くなる。したがってこの場合には、投機的リフィルを行なわないほうが余分なバストランザクションを抑えることができる。
【００１８】
なお、上述した構成では、図２におけるキャッシュコントローラ４にはオフセットを検出する構成要素が示されていないが、例えば、図３に示すように、位置検出部１２の出力に基づいてオフセットを検出するオフセット検出部１４を設けるようにしても良い。
【００１９】
［第３実施形態］
また、第３実施形態に係る命令キャッシュメモリのプリフェッチ機構は、第１構成のものにおいて、前記境界設定部は、次のキャッシュラインまでも投機的に入れ替えるか否かの前記境界の設定位置をプログラムの分岐間隔に応じて動的に設定することを特徴としている。したがって、第３実施形態のプリフェッチ機構は、図４に示すように、キャッシュコントローラ４にＣＰＵ１から供給されるプログラムにおける分岐間隔を検出するプログラム分岐間隔検出部１５が設けられている。この構成は、次のラインの投機的リフィルを行なうキャッシュミス位置を、プログラムの代表的な分岐間隔に応じて動的に制御するものであり、往路グラム分岐間隔検出部１５により検出されたプログラムの分岐間隔に応じて境界２Ｄが境界２Ｅの用に変更されることもある。判定回路としての境界設定部１１における判定パラメータを、ソフトウェアもしくはハードウェアにより動的に変更できるようにしておいても良い。
【００２０】
このような構成に基づく効果としては、投機的リフィルを行なうかどうかを判定するキャッシュライン上の位置、すなわち残りのキャッシュライン長はバス使用効率向上のためにはなるべく長く、かつ分岐ターゲットアドレスからの連続実行命令数（＝次の分岐命令までの命令数）よりも短くなっていることが望ましい。プログラムの分岐間隔が静的もしくは動的に予測できれば、その結果に応じて判定回路のパラメータを変更することにより投機的リフィルの効率をさらに向上させることができる。
【００２１】
［第４実施形態］
次に、第４実施形態に係る命令キャッシュメモリのプリフェッチ機構は、図４に示した第３実施形態のプリフェッチ機構１０において、キャッシュコントローラ４が、分岐命令以外の命令実行数をカウントして分岐命令が発生するたびにカウントした命令実行数を記録してリセットされるカウンタ１６をさらに備え、境界設定部１１は、カウンタ１６によりカウントされて収集された統計情報としての命令実行数に基づいて境界２Ｄ（２Ｅ）の設定位置を動的に設定することを特徴としている。
【００２２】
第４実施形態の構成としては、分岐命令間隔に関する統計情報をプロセッサ等により測定し、第３実施形態における動的制御のデータとして用いている。すなわち、分岐命令以外の命令実行数をカウントするカウンタ１６を設け、分岐命令が発生するたびにカウンタ１６の値を履歴テーブル（図示されず）に記録する（カウンタはここでリセット）ことで統計情報を収集しておく。このテーブル（図示されず）は、ソフトウェアもしくはキャッシュコントローラ４から読み出し可能とする。
【００２３】
上述した第４実施形態の効果としては、分岐命令の間隔をプログラムの性質や実行状況に応じて動的・静的に変化させているので、プログラム実行時の分岐命令間隔をプロセッサまたはカウンタ１６により測定し、投機的リフィルの実施する判定位置としての境界を動的に制御することによって効率を向上させている。なお、第４実施形態においては、キャッシュコントローラ４の外部に履歴テーブルを設けるものとして説明したが、履歴テーブルをコントローラ４の内部に設けるようにしてもよい。
【００２４】
［第５実施形態］
すなわち、本発明の第５実施形態に係る命令キャッシュメモリのプリフェッチ機構は、第４実施形態に示されたプリフェッチ機構において、キャッシュコントローラ４は、カウンタ１６によりカウントされた命令実行数を記録するためのテーブル命令実行数記録テーブル１７をさらに備えることを特徴としている。
【００２５】
さらに、詳細な構成としての命令実行数記録テーブル１７は、分岐命令間隔の履歴テーブルとして、第１に過去の一定回数の分岐に関し分岐命令間隔を記録するようにしても良いし、第２に分岐命令間隔に対し、その発生度数を記録するようにしても良い。
【００２６】
上記のような命令実行数記録テーブル１７を設ける効果としては、第１の構成のようなテーブルを用いる場合は最近の分岐命令間隔の平均値を用いた制御理論を適用することができ、また、第２の構成のようなテーブルを用いる場合は最頻値（mode）もしくは中間値（median）などを用いた制御論理を適用することができる。
【００２７】
上記の第１ないし第５実施形態では、いずれのものもキャッシュミス発生時の対応を正確で迅速に行なうことができると共に無駄なメモリを設ける必要のない命令キャッシュメモリのプリフェッチ機構を提供するために、キャッシュデータ記憶部におけるキャッシュミスの発生する可能性の高い領域と低い領域との境界を設けると共にキャッシュミスの発生する可能性の高い領域でキャッシュミスが発生した場合には投機的リフィルを行ない、キャッシュミスの発生する可能性の低い領域でキャッシュミスが発生した場合にはリフィルをしないようにして、キャッシュミスが発生する可能性に応じて投機的にリフィルを行なったり全く行なわなかったりしている。
【図面の簡単な説明】
【００２８】
【図１】第１実施形態のキャッシュメモリのプリフェッチ機構を示すブロック図。
【図２】第２実施形態のキャッシュメモリのプリフェッチ機構を示すブロック図。
【図３】第２実施形態のキャッシュメモリのプリフェッチ機構を示すブロック図。
【図４】第３実施形態のキャッシュメモリのプリフェッチ機構を示すブロック図。
【図５】第４実施形態のキャッシュメモリのプリフェッチ機構を示すブロック図。
【図６】第５実施形態のキャッシュメモリのプリフェッチ機構を示すブロック図。
【図７】従来のキャッシュメモリのプリフェッチ機構を示すブロック図。
【符号の説明】
【００２９】
１  ＣＰＵ
２  キャッシュメモリ部
２Ａ  行アドレス記憶部（ＴＡＧ・ＲＡＭ）
２Ｂ  キャッシュデータ記憶部（キャッシュＲＡＭ）
３  行アドレス入力部
４  キャッシュコントローラ
５  ミス判定部
６  メモリセルアレイ
１０  プリフェッチ機構
１１  境界設定部
１２  位置検出部
１３  キャッシュデータ投機的入替部
１４  オフセット検出部
１５  プログラム分岐間隔検出部
１６  カウンタ
１７  命令実行数記録テーブル
【図１】
2008102745.tif 000003
【図２】
2008102745.tif 000004
【図３】
2008102745.tif 000005
【図４】
2008102745.tif 000006
【図５】
2008102745.tif 000007
【図６】
2008102745.tif 000008
【図７】
2008102745.tif 000009