データ供給装置、キャッシュ装置、データ供給方法、キャッシュ方法およびプログラム
【課題】 データ供給装置において、受信の際に必要となる記憶領域（受信領域）が大きい。またノンブロッキング動作のときに受信領域からデータを保持する記憶領域への転送が必要となる。データを保持する記憶領域（データ領域）と受信領域とを一体化し、受信領域からデータ領域への転送をなくし、装置全体の回路規模を抑制するための技術を提供する。
【解決手段】 フェッチ手段に備えられたデータを保持する記憶領域の一部に受信領域を割り当て、プリフェッチ手段の出力する情報に従い、受信領域の割り当てを更新してデータを取得しフェッチ手段からデータを供給する。
【解決手段】 フェッチ手段に備えられたデータを保持する記憶領域の一部に受信領域を割り当て、プリフェッチ手段の出力する情報に従い、受信領域の割り当てを更新してデータを取得しフェッチ手段からデータを供給する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・システムにおけるノンブロッキング動作を実現するためのデータ供給技術に関する。
【背景技術】
【０００２】
近年、さまざまな機器において処理性能の向上と、より一層のコスト削減の両立が求められている。これらの機器には、ある種のコンピュータ・システムが搭載されており、コンピュータ・システムの製造コストあたりの処理性能は、機器の良否を決定する要因の一つと言える。
一般的にコンピュータ・システムにはアプリケーションを実行するプロセッサやデータ処理回路と、プログラムや処理対象となるデータを記憶するメモリ等の記憶装置で構成される。プロセッサやデータ処理回路が使用するプログラムやデータのすべてが、各々のプロセッサやデータ処理回路から高速に読み書きできる記憶装置を具備することが理想である。例えば、記憶装置としてはＳＲＡＭ等のアクセス・レイテンシの比較的短いメモリ手段を、プロセッサやデータ処理回路の各々に専用のローカルメモリとして具備できれば、処理性能の向上を実現し易い。
しかしながら、機器を低コスト化するためには、多くのプロセッサやデータ処理回路で単一の記憶装置を共有し、搭載する記憶装置の個数を削減することが望ましい。また、搭載する記憶装置としてメモリを採用する場合、その時々で普及している安価なＤＲＡＭを使用することが多い。ただし安価なＤＲＡＭを使用すると前述のＳＲＡＭよりアクセス・レイテンシは長くなる。また多くのプロセッサやデータ処理回路で互いに単一の記憶装置を共有する場合、各々のプロセッサやデータ処理回路から記憶装置への読み書きが競合し、各々のアクセスを調停するため、プロセッサやデータ処理回路からのアクセス・レイテンシは長くなる。その結果、各々のプロセッサやデータ処理回路の処理性能は低下する。
前述のプロセッサやデータ処理回路の性能低下を抑えるために、各々のプロセッサやデータ処理回路と記憶装置との間にキャッシュ装置を設けることが多い。各々のプロセッサやデータ処理回路は、組み込んだキャッシュ装置から所望のデータが読み出せる間は、記憶装置にアクセス（データ要求）することはない。これにより各々のプロセッサやデータ処理回路からのアクセス（データ要求）の頻度が減り、必要となるアクセス帯域の総量を減らすことができる。当然、キャッシュ装置を設けることで回路規模は増加するが、上記のようにローカルメモリを専用に設けるよりは、回路規模は少なくてよい。このようにコンピュータ・システムに最適なキャッシュ装置を設けることで、機器を実現する際に求められる処理性能と低コストを両立することが可能となる。
キャッシュ装置に所望のデータが存在する場合（キャッシュヒットと言う）、記憶装置までアクセス（データ要求）する必要はなく、各々のプロセッサやデータ処理回路からのアクセス・レイテンシは短くなる。一方、キャッシュ装置に所望のデータが存在しない場合（キャッシュミスと言う）、当然ながら各々のプロセッサやデータ処理回路は記憶装置に所望のデータをアクセス（データ要求）する。このとき、アクセス・レイテンシはキャッシュ装置を設けない場合と同じである。一般的には、各々のプロセッサやデータ処理回路はデータを順番に処理するため、キャッシュミス時に記憶装置から所望なデータを読み出すまでの間、各々のプロセッサやデータ処理回路は一時停止する。当然ながら、プロセッサやデータ処理回路は、この一時停止により処理性能が低下する。このような動作をブロッキング動作という。またキャッシュミスのときに、データを読み出す行為をリフィル、読み出したデータをリフィル・データ、一度に読み出す単位をリフィル長、読み出す期間をリフィル・レイテンシという。
さらに処理性能を向上するため特許文献１は、上記のリフィル・レイテンシを隠蔽できるキャッシュ機構のデータ供給装置について言及している。特許文献１のパイプライン・プロセッサは、所定のパイプライン・ステージで行う処理のために必要なデータに対し、まず所定のパイプライン・ステージの前段（前処理）でキャッシュミスを評価する。そしてキャッシュミスのときは、この前段（前処理）で必要なデータを要求してリフィルを実行する。このとき、特許文献１のパイプライン・プロセッサは、リフィル・レイテンシより長い中間待ち行列（ＦＩＦＯ）をパイプライン・プロセッサ内部に備える。 そして特許文献１のパイプライン・プロセッサは、リフィル中の処理を含む後続の処理を、この中間待ち行例（ＦＩＦＯ）に順次格納していく。このように特許文献１のパイプライン・プロセッサは、この中間待ち行例（ＦＩＦＯ）に格納しながら次の処理のキャッシュミス／ヒットの評価を続けられるので前述のブロッキング動作のように、キャッシュミスの度に一時停止する必要がない。
一方、特許文献１のパイプライン・プロセッサは、キャッシュミスの度に必要とするデータを記憶装置から読み出し、キャッシュメモリに更新する前に、一旦 リフィル・データをフィルＦＩＦＯに格納することが必須となる。中間待ち行列（ＦＩＦＯ）の中にはキャッシュミスのデータ処理に先行する、キャッシュヒットのデータ処理があり、それらの処理を所定のパイプライン・ステージで終えなければ、キャッシュメモリを更新することはできない。そのため、特許文献１のパイプライン・プロセッサには、上記のフィルＦＩＦＯを必ず備える。このように中間待ち行例（ＦＩＦＯ）を用いて次のデータ処理のキャッシュミス／ヒット評価を行うような動作をノンブロッキング動作という。データ処理を行うコマンドは、中間待ち行列（ＦＩＦＯ）の中で遅延する。この遅延の間にリフィルが完了し、キャッシュミス時のリフィル・データがフィルＦＩＦＯにあれば、データ処理に際しフィルＦＩＦＯからリフィル・データを供給し、データ処理を実行できる。つまり、特許文献１のキャッシュ機構のデータ供給装置は、上記のような仕組みでキャッシュミス時のリフィル・レイテンシを隠蔽して一時停止することなくデータ処理を続けられる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第３８４６６３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら特許文献１の技術では、キャッシュメモリとは別に動作するリフィル・データを一旦、格納するためのフィルＦＩＦＯが必要となる。
本発明の目的は、処理性能を維持しながら、回路規模を削減することである。
【課題を解決するための手段】
【０００５】
上記目的を達成するため、本発明に係るデータ供給装置は、出力手段と、前記出力手段にデータを保持する記憶領域を備え、前記出力手段に当該記憶領域のデータを供給するフェッチ手段と、前記出力手段がデータを要求する前に、前記出力手段に供給すべきデータを外部に要求するプリフェッチ手段と、を備えるデータ供給装置であって、前記フェッチ手段は、前記記憶領域の一部を外部より供給されるデータを受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として割り当て、前記出力手段は前記フェッチ手段によって送信領域として割り当てられた領域のデータを出力することを特徴とする。
【発明の効果】
【０００６】
本発明によれば、ノンブロッキング動作で動作する装置にデータを供給するデータ供給装置について、処理性能を維持しつつフィルＦＩＦＯを削減し回路規模を低減できる。
【図面の簡単な説明】
【０００７】
【図１】第１実施形態の処理装置の一例を示すブロック図である。
【図２】第１実施形態のキャッシュ判定部の一例を示すブロック図である。
【図３】第１実施形態のデータ取得部の処理の一例を示すフローチャートである。
【図４】第１実施形態のキャッシュメモリの動作の一例を示す遷移図である。
【図５】第２実施形態のキャッシュ判定部の一例を示すブロック図である。
【図６】第２実施形態のデータ供給装置の一例を示すブロック図である。
【図７】第２実施形態のキャッシュメモリの一例を示すブロック図である。
【図８】第２実施形態のデータ取得部の処理の一例を示すフローチャートである。
【図９】ブロッキング動作をする処理装置の一例を示すブロック図である。
【発明を実施するための形態】
【０００８】
まず、前述の特許文献１について説明を補足する。特許文献１の技術では、キャッシュメモリとは別に動作するリフィル・データを一旦、格納するためのフィルＦＩＦＯが必要となる。
【０００９】
前述のようにキャッシュデータの読み書き先である記憶装置には、安価なＤＲＡＭを搭載する。一般的にＤＲＡＭへの読み書きは、ある程度の連続した記憶領域を一度にデータ要求（バースト・アクセス）する方がメモリ帯域の効率が良い。そのため、ＤＲＡＭへのアクセス単位は、このバースト・アクセスによる読み書き単位が望ましい。ＤＲＡＭを製造するときの半導体プロセスの微細化と製品ニーズから、ＤＲＡＭは製造世代と共に内部動作周波数は年々高くなっている。当然、このバースト・アクセスによる読み書きの単位も、年々大きくなる傾向がある。高性能を要求する製品ニーズから、今後もＤＲＡＭの読み書きの単位が大きくなり続けると予想される。
【００１０】
キャッシュ装置では、１つのキャッシュタグ（キャッシュアドレス）に対応するキャッシュデータ（キャッシュライン）を、このバースト・アクセスによる読み書き単位の整数倍に合わせることが多い。１つのキャッシュミスに対応する、前記リフィル・データの読み書き単位（リフィル長）は、当然ながら、このキャッシュラインと同容量となる。例えば、上記のＤＲＡＭとの関係でリフィル・データの読み書き単位は３２バイト〜１２８バイトに及ぶ。
【００１１】
前述のフィルＦＩＦＯは、先の中間待ち行列（ＦＩＦＯ）の中にある、キャッシュミスのコマンド数に対応したリフィル・データを十分格納する容量が必要となる。組み込み機器では、前記リフィル・レイテンシは数十サイクルから数百サイクルに及ぶので、中間待ち行列（ＦＩＦＯ）の段数もそれに準ずる。例えば、キャッシュヒット率が７５％の場合、中間待ち行列（ＦＩＦＯ）の２５％はキャッシュミスとなる。中間待ち行列（ＦＩＦＯ）が１２８段なら、フィルＦＩＦＯは、１２８段の２５％である３２段が必要となる。先ほどのリフィル・データの読み出し単位を考慮するとフィルＦＩＦＯは１Ｋバイト〜４Ｋバイトの容量となり、組込み機器において無視してよいほど小さいとは言えない。
【００１２】
特許文献１の技術のキャッシュ装置では、
１）プリフェッチ論理でキャッシュヒット／ミス評価で使用するキャッシュタグの記憶領域、
２）中間待ち行列（ＦＩＦＯ）の記憶領域、
３）フェッチ論理のフィルＦＩＦＯの記憶領域、
４）フェッチ論理のキャッシュデータを格納するキャッシュメモリの記憶領域、
が必要となる。前述の説明の通り、このうち回路規模に大きな影響を与えるのは、リフィル長の大きな「３）フィルＦＩＦＯ」と、「４）キャッシュメモリ」であり、特許文献１のように「３）フィルＦＩＦＯ」と、「４）キャッシュメモリ」が別のハードウエア構成として存在すると回路規模が増加してしまう。なお、「２）中間待ち行列」は、ＦＩＦＯ段数は多いものの、キャッシュヒット／ミス評価結果のフラグとキャッシュメモリの格納先のアドレスを伝搬するだけでよく、後述するようにＦＩＦＯそのもののデータ長は、リフィル長に比べ非常に小さい。
【００１３】
＜第１実施形態＞
以下、添付の図面を参照して本発明の好適な実施形態を説明する。
【００１４】
キャッシュ装置を組み込んだ処理装置と、このキャッシュ装置について詳細説明する。
【００１５】
（処理装置）
図１は、第１実施形態による処理装置の全体構成の一例を示すブロック図である。処理装置には、ＣＰＵ１６０、外部の記憶装置（外部メモリ）であるＤＲＡＭ１６５、ＤＲＡＭコントローラ１６６とシステムバス１６４が含まれる。また、ＤＲＡＭ１６５に対するデータの読み書きのために、データ読み出し用のＤＭＡＣ（Ｄｉｒｅｃｔ Ｍｅｍｏｒｙ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌｌｅｒ）であるＲＤＭＡＣ１６２とデータ書き込み用のＷＤＭＡＣ１６３も含まれる。また処理装置には、画像処理などのデータ処理を行うデータ処理装置１０１と、本発明のキャッシュ装置１１０が含まれる。なおデータ処理装置に含める処理装置の数は任意であり、処理装置の各々は、高速に固定処理するパイプライン回路で構成されていてもよいし、低速ではあるが、柔軟に処理内容を変更可能なプロセッサとプログラムで構成されていてもよい。
【００１６】
ＣＰＵ１６０は、制御バス１６１を介してＲＤＭＡＣ１６２、ＷＤＭＡＣ１６３、データ処理装置１０１を制御し、処理装置全体を統括制御する。ＣＰＵ１６０の指示によりＲＤＭＡＣ１６２は、システムバス１６４、ＤＲＡＭコントローラ１６６を介してＤＲＡＭ１６５に格納された画像やプログラムなどのデータを読み出し、データ処理装置１０１に入力する。データ処理装置１０１は、所望のデータ処理を行い、処理結果の画像などのデータをＷＤＭＡＣ１６３に送り出す。このとき、ＷＤＭＡＣ１６３は予めＣＰＵ１６０から指示されており、データ処理装置１０１から受け取ったデータをシステムバス１６４、ＤＲＡＭコントローラ１６６を介してＤＲＡＭ１６５に格納する。処理装置は、前述の一連の動作を実行することにより画像処理等のデータ処理を実施するのである。
【００１７】
前述のデータ処理の過程で、データ処理装置１０１は、接続されたキャッシュ装置１１０を介して、ＤＲＡＭ１６５から各種必要な対象データ（画像、映像、設定値、テーブル、属性情報など）を読み出してデータ処理に使用できる。またデータ処理装置１０１がプロセッサとプログラムで構成されている場合、キャッシュ装置１１０を介してプログラムを逐次的に読み出して処理を実行することも可能である。
【００１８】
（データ供給装置）
次にデータ供給装置（キャッシュ装置）の動作について詳細説明する。前述のデータ処理装置１０１は、データ供給装置（キャッシュ装置）を介してＤＲＡＭ１６５からデータを読み出すときに、ＤＲＡＭ１６５上のデータの格納アドレス１１３を、Ｉ／Ｆ１１２を介してキャッシュ判定部１２０に入力する。そして入力された格納アドレス１１３をもとにキャッシュ判定部１２０でキャッシュヒットもしくはキャッシュミスが判定される。
【００１９】
（キャッシュ判定部）
さらに図２を用いて図１記載の処理装置のキャッシュ判定部１２０の回路構成の一例について詳細説明する。第１実施形態では、連想（ライン選択）方式がフルアソシアティブ方式のキャッシュ装置について説明する。
【００２０】
前述の格納アドレス１１３がキャッシュ判定部１２０へ入力される。キャッシュ判定部１２０には、８個のキャッシュタグ２３０が記憶されており、８ノードのフルアソシアティブ方式のキャッシュ装置となる。また８個のキャッシュタグ２３０には、［０］〜［７］の番号が予め定められており、対応するキャッシュメモリの「相対」キャッシュライン番号を示している。「相対」番号である理由は後述する。入力された格納アドレス１１３と８個のキャッシュタグ２３０は、８個の比較器２２０で、「一致」が判定される。そして比較器２２０から８個の比較結果２２８が判定器２５０に出力される。
【００２１】
８個の比較結果２２８のうち、１つでも「一致」であれば、キャッシュヒットと評価される。８個の比較結果２２８のうち、いずれも「一致」でなければ、キャッシュミスと評価される。評価結果はキャッシュミス・フラグ２４０として、キャッシュ判定部１２０から出力される。
【００２２】
評価結果がキャッシュヒットの場合、「一致」したキャッシュタグの「相対」ライン番号が、ライン番号２４５としてキャッシュ判定部１２０から出力される。
【００２３】
また評価結果が、キャッシュミスの場合（分岐２５５のＹＥＳ）、入力された格納アドレス１１３がキャッシュタグ２３０へ書き込まれ、キャッシュタグが更新される。キャッシュタグ２３０は、シフトレジスタで構造された記憶領域である。評価結果がキャッシュミスの場合、シフト動作によりキャッシュタグの値が下流のキャッシュタグに移動する。つまり、キャッシュタグ［０］にはキャッシュタグ［１］の値が、キャッシュタグ［１］にはキャッシュタグ［２］の値が各々書き込まれる。同様の書き込みが繰り返され、キャッシュタグ［６］にはキャッシュタグ［７］の値が書き込まれる。そして最後にキャッシュタグ［７］に格納アドレス１１３の値が書き込まれる。評価結果がキャッシュミスの場合、上記のようなキャッシュタグの更新が行われ、ライン番号２４５としてライン［７］の値がキャッシュ判定部１２０から出力される。
【００２４】
このように必ず古いキャッシュタグ［０］のタグ情報が破棄される、キャッシュタグのリプレイス手法を、「ＦＩＦＯ方式（ラウンドロビン方式）」という。フルアソシアティブ方式のキャッシュ装置では、装置を簡単に実現できるので、リプレイス手法として「ＦＩＦＯ方式（ラウンドロビン方式）」を採用することが多い。
【００２５】
最後にキャッシュ判定部１２０は、上記のように求めたキャッシュミス・フラグ２４０とライン番号２４５に、入力された格納アドレス１１３を合わせてキャッシュ判定結果１２５として出力する。
【００２６】
本実施形態の処理装置では、キャッシュミス時のペナルティであるリフィル・レイテンシを隠蔽するためにノンブロッキングのキャッシュ機構を採用している。これは、たとえキャッシュ判定結果１２５がキャッシュミスと判定されても、後に必要となる情報「ライン番号、キャッシュミス・フラグ」１３５を中間待ち行列（ＦＩＦＯ）１４０に退避する。そして、キャッシュミスのキャッシュデータをＤＲＡＭ１６５から読み出し、キャッシュメモリ１９０へ格納する処理が完了する前に、次のデータのキャッシュ判定処理を先行して実行する。このような処理を行うことでキャッシュミスのキャッシュデータをＤＲＡＭ１６５からキャッシュメモリ１９０へリフィルしている間にも、続くデータに対するキャッシュ判定処理を行うことができる。したがって、キャッシュのキャッシュミス時の性能低下を抑制することが可能となる。
【００２７】
なお「アクセス調停部」の説明で後述するように、アクセス調停部１３０は、キャッシュミスのときにキャッシュ判定結果１２５の中から格納アドレス１１３に相当する格納アドレス１３２を取り出し送信ＦＩＦＯ１５０へ順次記憶する。ＤＲＡＭコントローラ１６６は、この送信ＦＩＦＯ１５０から格納アドレス１３２を受け取り、所望のデータ（リフィル・データ）をＤＲＡＭ１６５から読み出して、キャッシュメモリ１９０へ書き込んでいく。データ取得部１８０は、中間待ち行列（ＦＩＦＯ）１４０から「キャッシュミス・フラグ」を取り出して、キャッシュ判定の結果がキャッシュミスであったかキャッシュヒットであったかを特定する。データ取得部１８０は、キャッシュ判定の結果がキャッシュヒットのとき、キャッシュデータ１８５をキャッシュメモリ１９０から直接読み出してＩ／Ｆ１１６へ送り出す。一方、キャッシュ判定の結果がキャッシュミスのとき、「データ取得部」で後述するように、所望のキャッシュデータを更新する。そして、このキャッシュデータ１８５をＩ／Ｆ１１６へ送り出す。このようなキャッシュミスしたキャッシュデータをＤＲＡＭ１６５から読み出して、キャッシュメモリ１９０に更新する、一連の処理が前述のリフィルである。
【００２８】
（アクセス調停部）
アクセス調停部１３０は入力されたキャッシュ判定結果１２５が有効のとき動作し、それ以外は待機する。そしてアクセス調停部１３０は、キャッシュ判定の結果「キャッシュミス・フラグ」が有効／無効に応じて以下の処理を行う。
・キャッシュ判定の結果「キャッシュミス・フラグ」が有効（キャッシュミス）のとき、まず接続される２つのＦＩＦＯである、送信ＦＩＦＯ１５０、中間待ち行列（ＦＩＦＯ）１４０の格納領域の空き状態を評価する。さらにデータ取得部１８０からのプリフェッチ許可信号１８１の状態を評価する。２つのＦＩＦＯすべてに空き領域があり、プリフェッチ許可信号１８１の状態が「許可」である場合、「ライン番号、キャッシュミス・フラグ」１３５を中間待ち行列（ＦＩＦＯ）１４０に書き込む。また同時に、格納アドレス１３２を送信ＦＩＦＯ１５０に書き込む。２つのＦＩＦＯに空き領域がない、もしくはプリフェッチ許可信号１８１の状態が「許可」でない場合は、キャッシュ判定部１２０を停止（ストール）する。そして、２つのＦＩＦＯの格納領域が空き、かつ、プリフェッチ許可信号１８１の状態が「許可」になるまで待機する。
・キャッシュ判定の結果「キャッシュミス・フラグ」が無効（キャッシュヒット）のとき、中間待ち行列（ＦＩＦＯ）１４０の空き状態を評価する。そして記憶領域に空きがあれば、「ライン番号、キャッシュミス・フラグ」１３５を中間待ち行列（ＦＩＦＯ）１４０に書き込む。記憶領域に空きがなければ、キャッシュ判定部１２０を停止（ストール）し、格納領域が空くまで待機する。本実施形態の一例では、中間待ち行列（ＦＩＦＯ）１４０に格納する、「キャッシュミス・フラグ」は１ビット信号であり、「ライン番号」は３ビット信号でよいため、中間待ち行列（ＦＩＦＯ）１４０のデータ長は高々４ビット長となる。たとえ中間待ち行列（ＦＩＦＯ）１４０が１２８段あったとしても６４バイトの容量でよく、大きな記憶容量とは言えない。それ故、フルアソシアティブ方式のキャッシュタグのノード数や中間待ち行列（ＦＩＦＯ）の段数を増やすことは容易であり、中間待ち行列（ＦＩＦＯ）１４０が制約となることはない。
【００２９】
なお、上記で説明した「キャッシュ判定部」と「アクセス調停部」は、これから説明する「データ取得部」に対応したプリフェッチ構成（装置／回路／論理）となっている。そして、「キャッシュ判定部」と「アクセス調停部」は、データを必要とする所定のパイプライン・ステージに対し、先行するパイプライン・ステージと繋がり、所定のパイプライン・ステージに対する前処理にある。
【００３０】
（データ取得部）
データ取得部１８０は中間待ち行列（ＦＩＦＯ）１４０の格納領域に処理すべきデータがあるかどうかを評価する。中間待ち行列（ＦＩＦＯ）１４０が空の場合は処理すべきキャッシュ判定結果がないため、データ取得部１８０は当然ながら待機する。データ取得部１８０は、中間待ち行列（ＦＩＦＯ）１４０から処理すべきキャッシュ判定の評価結果である「ライン番号、キャッシュミス・フラグ」を取り出す（Ｓ３０５）。そして評価結果であるキャッシュミス・フラグの値に応じて次のキャッシュデータの取得動作を行う。図３（ａ）にデータ取得部１８０のキャッシュデータの取得動作の一例を示す。図４（ａ）に示すように本発明のキャッシュメモリ１９０は、「データ領域（送信領域、キャッシュ領域）」と「受信領域」を含んで構成される。そして、受信領域を管理する情報（受信ポインタ）と、データ領域を管理する情報（データポインタ）とをデータ取得部に備える。
・キャッシュミス・フラグが無効（キャッシュヒット）のときは、中間待ち行列（ＦＩＦＯ）１４０から同時に取り出したライン番号とキャッシュメモリ１９０の受信ポインタとデータポインタからキャッシュデータの格納アドレスを算出する。そして、その格納アドレスをもとに記憶済みのデータをキャッシュメモリ１９０からリードデータ１９２として読み出す（Ｓ３６０）。そして、要求されたキャッシュデータ１８５を、Ｉ／Ｆ１１６を介して処理装置１０１に送出する（Ｓ３６５）。なお、格納アドレスの算出方法については後述する。
【００３１】
キャッシュミス・フラグが有効（キャッシュミス）のとき、データ取得部１８０は受信ポインタとデータポインタの差を確認する（Ｓ３４０）。両ポインタに差がない（０の値）のとき（Ｓ３４０のＮＯ）、ＤＲＡＭ１６５からの要求されているリフィル・データがキャッシュメモリ１９０に届いていないと評価し、リフィル・データが届くまで待機する（Ｓ３４５）。両ポインタに差がある（０ではない値）のとき（Ｓ３４０のＹＥＳ）、ＤＲＡＭ１６５からの要求されているリフィル・データがキャッシュメモリ１９０に格納済みのためデータポインタを更新する（Ｓ３５０）。ここからキャッシュデータ１８５の出力までの手順は、前記のキャッシュミス・フラグが無効（キャッシュヒット）の手順と同様となる。
【００３２】
データ取得部１８０では、前述のキャッシュデータの取得動作とは並行して、要求されたリフィル・データの受信動作を行っている。図３（ｂ）にデータ取得部１８０のリフィル・データの受信動作の一例を示す。ＤＲＡＭ１６５からの要求されているリフィル・データがデータ取得部１８０に届いた場合（Ｓ３８０のＹＥＳ）、受信ポインタを更新する（Ｓ３８５）。次にデータ取得部１８０は受信ポインタとデータポインタの差を確認する（Ｓ３９０）。両ポインタに差が予め定められた受信の閾値と同数であるとき（Ｓ３９０のＹＥＳ）、これ以上、リフィル・データを受信することができないので、プリフェッチ許可信号１８１を「禁止」にする（Ｓ３９４）。両ポインタに差が予め定められた受信の閾値より小さいとき（Ｓ３９０のＮＯ）、ＤＲＡＭ１６５からリフィル・データを受け取ることができるので、プリフェッチ許可信号１８１は「許可」のままでよい（Ｓ３９２）。
【００３３】
回路実装では、アクセス調停部１３０の方がデータ取得部１８０より前段にある。それ故、データ取得部１８０からのプリフェッチ許可信号１８１を受け取ってから、アクセス調停部１３０でＤＲＡＭへのアクセス（データ要求）を止めても遅いケースがある。このような回路の位置関係からくるレイテンシの違いを考慮して、前記の受信の閾値を、予め記憶できる受信段数より少なく設定してもよい。また、より厳密な手法としては、リフィル待ち数を新たに定義し、このリフィル待ち数を用いてプリフェッチ許可信号１８１を生成してもよい。新たに定義するリフィル待ち数とは、０から開始し、アクセス調停部１３０でキャッシュミスの度に１を加算し、データ取得部にリフィル・データが到着する度に１を減算した数とする。
【００３４】
つまり、リフィル待ち数とは、データ要求を行ったが、まだフェッチ構成に到達していないリフィル・データの数を表している。そして、受信済みのリフィル・データ数（受信ポインタとデータポインタの差）とリフィル待ち数の合計値が将来受信するリフィル・データ数となる。この将来受信する数が受信の閾値より小さい場合、プリフェッチ許可信号１８１は「許可」とし、将来受信する数が受信の閾値と同じ数であればプリフェッチ許可信号１８１は「禁止」とするのである。
【００３５】
（データ取得部とキャッシュメモリの動作例）
図４（ｂ）を用いてキャッシュメモリ調停回路１８０とキャッシュメモリ１９０の具体的な動作の一例について説明する。
【００３６】
まず、状態［０］はリセット直後の初期状態を示している。初期状態では受信領域の開始を示す受信ポインタは「０」の値である。またデータ領域の上端を示すデータポインタは「０」での値である。この動作の一例では、受信領域は４段、データ領域は８段となっている。キャッシュメモリ１９０は合計１２段の記憶領域となっている。記憶領域には図面の下側から上側に向かて「０」から「１１」の番号が記載されており、キャッシュメモリ１９０のアドレスを示している。また記憶領域の１段は、１回のＤＲＡＭアクセス（データ要求）に対応するリフィル・データ（リフィル長）を格納できる記憶領域であり、１キャッシュラインに相当する。
【００３７】
次にアクセス調停部１３０で１回のミスヒット評価による１回のリフィル要求があり、そのリフィル・データがデータ取得部１８０に届いたとき（［Ａ］リフィル・データを１つ受信）、キャッシュメモリ１９０は状態［１］になる。状態［１］では、図３（ｂ）の動作手順に従い、１つのリフィル・データがキャッシュメモリに格納される。そして、受信ポインタが「１」の値となる。データポインタは「０」の値のままであり、受信ポインタとデータポインタの差は「１」の値となる。この差は受信数を表しており、受信領域は４段であったので残りの受信領域は３段となる。
【００３８】
次に中間待ち行列（ＦＩＦＯ）１４０を介してキャッシュミスのデータがキャッシュ調停部１８０に入力され（［Ｂ］キャッシュミスが１回発生）、キャッシュメモリ１９０は状態［２］となる。状態［２］では、図３（ａ）の動作手順に従い、１つのキャッシュデータが有効となる。そして、データポインタが「１」の値となる。データポインタはデータ領域の上限を示しており、データポインタの位置は仮想的にデータ領域のライン番号「８」に相当すると定義する。データポインタが「１」となった状態［２］のケースでは、有効化されたキャッシュデータはキャッシュメモリ１９０のアドレス「０」の領域にある。データポインタの指し示す「１」がライン番号「８」に相当するのに対応して、このアドレス「０」の領域は、ライン番号「７」（＝８−１）を指示している。前述の「キャッシュ判定部」の説明で判定の結果がキャッシュミスのときのライン番号が「７」になると説明した動作に合致している。このとき、前述のリフィル・データを受け取った受信領域の一部が、データ領域に置き換わることとなる。
【００３９】
キャッシュメモリ１９０はリング式ＦＩＦＯと同様に、アドレス「１１」とアドレス「０」に連続していると考える。アドレス「０」の領域がライン番号「７」に対応している規則と同様に、アドレス「１１」の領域はライン番号「６」を示している。 さらにアドレス「１０」の領域はライン番号「５」を示している。同様の規則を繰り返し、アドレス「５」の領域がライン番号「０」を示している。データ領域はアドレス「５」からアドレス「１１」を経てアドレス「０」の領域までとなる。
【００４０】
そして残りのアドレス「１」からアドレス「４」までの領域が受信領域となる。状態［２］では、受信ポインタとデータポインタの値が同一となり、受信済みのリフィル・データが格納済みのキャッシュデータに変わることで受信領域が１段回復している。つまり、受信領域の一部とデータ領域の一部が置き換わり（交換され）、キャッシュメモリに対する受信領域の割り当てが更新されている。
【００４１】
さらにアクセス調停部１３０で４回のミスヒット評価が連続し、４回のリフィル要求の後、その４つのリフィル・データがデータ取得部１８０に届いたとき（［Ｃ］リフィル・データを４つ受信）、キャッシュメモリ１９０は状態［３］になる。状態［３］では、４つのリフィル・データがキャッシュメモリに格納される。そして、受信ポインタが「５」の値となる。データポインタは「１」の値のままであり、受信ポインタとデータポインタの差は「４」の値となる。この差は受信数を表しており、受信領域は４段であったので残りの受信領域は０段となる。説明を簡単にするために前述の受信の閾値は、受信領域の数「４」と同じ設定とする。このとき、受信数と受信の閾値は同じ値であるので、これ以上、リフィル・データを受け取ることはできない。そのため、キャッシュ調停部１８０は、プリフェッチ許可信号１８１を「禁止」にしてアクセス調停部１３０に通知し、ノンブロッキング・アクセスを一旦、停止する。プリフェッチ構成は、記憶装置へのデータ要求を止めることとなる。
【００４２】
さらに、４つのキャッシュミスのデータがキャッシュ調停部１８０に連続して入力され（［Ｄ］キャッシュミスが連続４回発生）、キャッシュメモリ１９０は状態［４］となる。状態［４］では、４つのキャッシュデータが有効となる。そして、データポインタが「５」の値となる。データ領域は残り３段となる。
【００４３】
さらに、［Ｅ］リフィル・データを４つ受信し、状態［５］を経て、［Ｆ］キャッシュミスが連続４回発生し、状態［６］となる。状態［６］では、受信ポインタとデータポインタは共に「９」の値であり、データ領域はアドレス「１」から「８」までとなり、受信領域はアドレス「９」からアドレス「１１」を経てアドレス「０」までとなる。状態［５］から状態［６］に至るまでの過程で、データ領域の残りは０段となっており、これ以降、データ領域の８段すべてには何かしら有効なキャッシュデータが格納されている。また状態［６］では、状態［２］でアドレス「０」に格納されていたキャッシュデータは、データ領域の外側の受信領域に存在することになる。このキャッシュデータはもともと最も古く、状態［５］から状態［６］までの一連の動作の過程で、データ領域から破棄されたことになる。古いキャッシュデータから順に置き換えられるのでＦＩＦＯ方式（ラウンドロビン方式）のリプレイス手法と合致する。 このように受信領域の一部がデータ領域に置き換わり、データ領域の一部が受信領域に置き換わり（交換され）、結果として受信領域の割り当てが更新されている。
【００４４】
これまで説明した動作と同様により、キャッシュメモリ１９０は、動作［Ｇ］、動作［Ｈ］に対応して状態［７］、状態［８］へと遷移する。
【００４５】
なお、図４（ｂ）の状態［３］において、受信数が受信の閾値となったためノンブロッキング動作を停止すると説明した。しかしながら、状態［０］（初期状態）から状態［３］までの間は、データ領域には有効なキャッシュデータが保持されているわけではない。つまり、状態［０］（初期状態）からすべてのデータ領域が一度有効なキャッシュデータで埋まるまでの間は、受信の閾値を４段ではなく１２段とし、初期状態の受信領域を増加させる。このような工夫により、初期時のノンブロッキング動作の停止を抑制し、性能をさらに向上することができる。このようなことができるのは、受信領域とデータ領域を一体化したからに他ならない。
【００４６】
以上、説明した「データ取得部」は要求されたデータを取得する、フェッチ構成（装置／回路／論理）となっている。そして、取得したデータを所定のパイプライン・ステージにデータ供給する。
【００４７】
本実施形態のキャッシュ装置によれば、簡単な構成によって、ノンブロッキング動作のフルアソシアティブ方式のキャッシュ装置を実現できる。また従来技術では、ノンブロッキング動作のためにキャッシュメモリとは別に受信用のフィルＦＩＦＯを備える必要があったが、本発明の手法ではキャッシュメモリの領域の一部を受信領域に割り当てることでフィルＦＩＦＯを備える必要がない。一般的に、ある記憶領域を内蔵ＳＲＡＭで実現するとき、同容量の記憶領域に対して１つの内蔵ＳＲＡＭで構成する場合より、複数の内蔵ＳＲＡＭに分割して構成する方が回路規模は増大する。本発明の手法では、従来技術で言うところのフィルＦＩＦＯとキャッシュメモリを１つの内蔵ＳＲＡＭで構成できるのでキャッシュ装置の回路規模を小さく抑えることができる。
【００４８】
また従来技術では、キャッシュミス時にリフィル・データをフィルＦＩＦＯに一旦書き込み、さらにフィルＦＩＦＯから読み出してキャッシュメモリに再び書き込み、キャッシュデータとして利用する。従来技術では少なくとも、フィルＦＩＦＯとキャッシュメモリに２回の書き込みと１回の読み出しが必要となる。本発明の方法では、データ受信とデータ保持が一つの記憶領域に統合されているので、キャッシュミス時に記憶領域に対し、１回の書き込みと１回の読み出しでよい。本発明の手法をハードウエアで実現する場合、内蔵ＳＲＡＭの制御回路も簡易化が可能である。また本発明の手法をソフトウエアで実現したとしても、記憶領域へのアクセス回数が少なくてよいので、処理の高速化が可能となる。
【００４９】
本発明の主旨は、キャッシュメモリに受信領域を統合して、キャッシュメモリへのアクセス回数を削減することである。そのため、本実施形態のように受信ポインタとデータポインタを用いてキャッシュメモリと受信領域を関係付ける方法である必要はなく、キャッシュメモリと受信領域を関係付けるための対応表（リンクテーブル）を別途記憶し、プリフェッチ手段の情報に従い、対応表（リンクテーブル）を更新する関連付け方法でも良い。
【００５０】
また、本実施形態はＦＩＦＯ方式（ラウンドロビン方式）を採用しているフルアソシアティブ方式のキャッシュ装置にも適用できる。
【００５１】
＜第２実施形態＞
（データ供給装置）
次にフルアソシアティブ方式とは異なる連想（ライン選択）方式である、ダイレクトマップ方式やセットアソシアティブ方式に本発明のデータ供給方法を適用した場合の動作について詳細説明する。第１実施形態ではフルアソシアティブ方式の連想（ライン選択）方式を採用していたため、一般的な実装方法ではキャッシュタグをレジスタで構成することになる。そのため、あまり大きな数のキャッシュタグ数に対応するとキャッシュタグの回路規模が大きくなる課題がある。ダイレクトマップ方式やセットアソシアティブ方式の利点は、キャッシュタグをＳＲＡＭ等の記憶装置（タグメモリ）で構成することで回路規模を抑えられる点にある。もちろんダイレクトマップ方式やセットアソシアティブ方式においてもキャッシュタグをレジスタで構成できることは言うまでもない。
【００５２】
なお、第１実施形態と本実施形態との主な違いである「キャッシュ判定部」と「データ取得部」について詳細説明し、第１実施形態と同様の動作については以降での説明を割愛する。
【００５３】
（ダイレクトマップ方式のキャッシュ判定部）
図５（ａ）を用いて図１記載の処理装置のキャッシュ判定部１２０の回路構成の一例について詳細説明する。
【００５４】
前述の格納アドレス１１３がキャッシュ判定部１２０へ入力される。キャッシュ判定部１２０には、Ｎ個のキャッシュタグ５３０がタグメモリ（ＳＲＡＭ）に記憶されており、Ｎラインのダイレクトマップ方式のキャッシュ装置となる。またＮ個のキャッシュタグ５３０には、［０］〜［Ｎ−１］の番号が予め定められており、対応するキャッシュメモリのキャッシュライン番号を示している。まず格納アドレス１１３のうち、前述のキャッシュタグ［０］〜［Ｎ−１］の番号に対応する信号を抜き出し、下位アドレス５１５とする。そして残りの値を表現できる信号を抜き出し、上位アドレス５１２とする。次に下位アドレス５１５を用いてキャッシュタグ５３０から対応するキャッシュタグ［ｋ］５３５を読み出す。そして比較器５２０を用いて上位アドレス５１２とキャッシュタグ５３５の「一致」を判定する。比較器５２０から１個の比較結果５２８が判定器５５０に出力される。比較結果５２８が「一致」であれば、キャッシュヒットと評価される。比較結果５２８が「一致」でなければ、キャッシュミスと評価される。評価結果はキャッシュミス・フラグ２４０として、キャッシュ判定部１２０から出力される。
【００５５】
また評価結果が、キャッシュミスの場合（分岐５５５のＹＥＳ）、格納アドレス１１３がキャッシュタグ５３０へ書き込まれ、キャッシュタグが更新される。なお、ダイレクトマップ方式の場合、キャッシュタグは１個しかないため、リプレイス手法について考える必要はない。第１実施形態とは異なり、評価結果がキャッシュヒットの場合もキャッシュミスの場合も下位アドレス５１５の値がライン番号２４５としてキャッシュ判定部１２０から出力される。
【００５６】
以上の説明から明らかなようにキャッシュ判定部１２０には一般的なダイレクトマップ方式のキャッシュ判定構成（装置／回路／論理）を用いて差し支えない。
【００５７】
（セットアソシアティブ方式のキャッシュ判定部）
同様に図５（ｂ）を用いて図１記載の処理装置のキャッシュ判定部１２０の回路構成の一例について詳細説明する。多くの動作は前述のダイレクトマップ方式のキャッシュ判定部と同じである。図５（ｂ）は４ウェイ・セットアソシアティブ方式の一例であり、ダイレクトマップ方式と異なる点について言及する。
【００５８】
キャッシュ判定部１２０には、４×Ｎ個のキャッシュタグ５３０がタグメモリ（ＳＲＡＭ）に記憶されており、Ｎラインの４ウェイ・セットアソシアティブ方式のキャッシュ装置となる。またＮ個のキャッシュタグ５３０には、［０］［＊］〜［Ｎ−１］［＊］の番号が予め定められており、対応するキャッシュメモリのキャッシュライン番号を示している。また［＊］はウェイ番号を示し、本実施形態では４ウェイのため［＊］には［０］から［３］の値が入る。下位アドレス５１５を用いてキャッシュタグ５３０から対応する４個のキャッシュタグ［ｋ］［０］〜［ｋ］［３］５３５を読み出す。そして４個の比較器５２０を用いて上位アドレス５１２と４個のキャッシュタグ［ｋ］［０］〜［ｋ］［３］５３５の各々について「一致」を判定する。４個の比較器５２０から、４個の比較結果５２８が判定器５５０に出力される。４個の比較結果５２８のうち１つでも「一致」であれば、キャッシュヒットと評価される。また４個の比較結果５２８が何れも「一致」でなければ、キャッシュミスと評価される。評価結果はキャッシュミス・フラグ２４０として、キャッシュ判定部１２０から出力される。
【００５９】
また評価結果が、キャッシュミスの場合（分岐５５５のＹＥＳ）、ＦＩＦＯ方式（ラウンドロビン方式）のリプレイス手法を用いて最も古いウェイ番号を選択する。そして、そのウェイ番号のキャッシュタグのみ格納アドレス１１３と差し換え、その他のウェイ番号のキャッシュタグはそのままの値で、キャッシュタグ５３０が更新される。
【００６０】
以上の説明から明らかなようにキャッシュ判定部１２０には、一般的なセットアソシアティブ方式のキャッシュ判定構成（装置／回路／論理）を用いて差し支えない。
【００６１】
（データ取得部）
まず、図６を用いて第１実施形態と異なる本実施形態のデータ供給装置（キャッシュ装置）の特徴について言及する。本実施形態では、キャッシュミスで記憶装置に所望のデータを要求する際、ライン番号用の中間待ち行列（ＦＩＦＯ）６４５にキャッシュミス時のライン番号を格納する。そして、データ取得部１８０は、この中間待ち行例（ＦＩＦＯ）６４５を介し、キャッシュミス時のリフィル・データのキャッシュメモリへの格納先を示すライン番号を取得する。なお、この中間待ち行列（ＦＩＦＯ）６４５に空きがない場合、当然ながらアクセス調停部１３０は停止（ストール）する。
【００６２】
また図７を用いて本実施形態のキャッシュメモリ１９０の一例について説明する。この一例では同容量の記憶領域を、ダイレクトマップ方式に対応した場合（図７（ａ）記載）と、４ウェイ・セットアソシアティブ方式に対応した場合（図７（ｂ）記載）の２種の連想（ライン選択）方式に対応できることを説明している。この一例では、１つのキャッシュラインに対して８個の格納先が予め割り当てられている。ダイレクトマップ方式では７個の受信領域と１個のデータ領域が割り当てられており、４ウェイ・セットアソシアティブ方式では４個の受信領域と４個のデータ領域が割り当てられている。本実施形態のキャッシュメモリは、必ず１つのキャッシュラインに対して複数の格納先を持ち、データ取得部１８０への外部からのレジスタ設定等により、複数の格納先を受信領域とデータ領域に分配できる仕組みを持つ。一例では、まず、ダイレクトマップ方式のデータ領域は格納先１個とし、４ウェイ・セットアソシアティブ方式のデータ領域は格納先４個のように、アドレス１つにつき連想するキャッシュタグの数に合わせてデータ領域の格納先を割り当てる。 そして残りの格納先を受信領域とする。このように受信領域とデータ領域の分配を変更することで、同一のキャッシュメモリを異なる連想（ライン選択）方式に対応させている。キャッシュ判定部１２０を、連想（ライン選択）方式の異なる種々の判定回路に置き換えても、データ取得部１８０とキャッシュメモリ１９０は変更することなく使用できる。なお、記憶領域から連想（ライン選択）方式に応じたデータ領域を割り当てるが、残りの記憶領域に対しては、少なくとも１つの記憶先を受信領域に割り当てればよい。必ずしも残りの記憶領域すべてを受信領域に割り当てる必要はなく、受信ポインタとデータポインタの算出を工夫して、余った格納先を別用途で使用してもよい。
【００６３】
次にデータ取得部１８０のキャッシュデータの取得動作の一例を図８（ａ）に示し、リフィル・データの受信動作の一例を図８（ｂ）に示す。まず図７に示すように、本実施形態のデータ取得部１８０はキャッシュライン毎に受信ポインタとデータポインタを備える。そこで、データ取得動作やリフィル・データ受信動作において、最初に関連するライン番号から、対応する受信ポインタとデータポインタを選択する必要がある。例えば、データ取得動作においてデータ取得部１８０は、中間待ち行列（ＦＩＦＯ）１４０から処理すべきキャッシュ判定結果である「ライン番号、キャッシュミス・フラグ」を取り出す（Ｓ８０５）。そして、ライン番号を基に対応する受信ポインタとデータポインタを取得する（Ｓ８０２）。また、リフィル・データ受信動作においてデータ取得部１８０は、キャッシュミスに関するライン番号用の中間待ち行列（ＦＩＦＯ）６４５から関連するライン番号を取り出す（Ｓ８８２）。そして、そのライン番号を基に対応する受信ポインタ取り出し、更新する（Ｓ８８５）。
【００６４】
対応する受信ポインタとデータポインタを選択した後のデータ取得動作やリフィル・データ受信動作は、第１実施形態と同様の動作でよい。
【００６５】
（データ取得部とキャッシュメモリの動作例）
上記のような手法でライン番号が取り出され、キャッシュメモリ上の記憶領域がライン番号により定まった後は、アドレス算出を始め、受信ポインタやデータポインタの関係など第１実施形態と同様の動作でよい。
【００６６】
なお、データ取得部１８０からアクセス調停部１３０へのプリフェッチ許可信号６８１は、すべてのキャッシュラインに対応した受信ポインタとデータポインタから算出される１ビットの許可信号をキャッシュライン分、束ねた信号となる。この点が、第１実施形態とは異なるため注意が必要である。
【００６７】
なお、セットアソシアティブ方式の連想（ライン選択）方式は、第１実施形態と同様にＦＩＦＯ（ラウンドロビン）方式のリプレイス手法となる。しかしながら、ダイレクトマップ方式の連想（ライン選択）方式は、連想数が１個であるため、ＦＩＦＯ（ラウンドロビン）方式のリプレイス手法とは呼ばない。 ダイレクトマップ方式の連想（ライン選択）方式は、この点が他の連想（ライン選択）方式と異なるため注意が必要である。
以上、説明した「データ取得部」は、ダイレクトマップ方式やセットアソシアティブ方式の連想（ライン選択）方式に対応して、要求されたデータを取得する、フェッチ構成（装置／回路／論理）となっている。
【００６８】
本実施形態のデータ供給装置（キャッシュ装置）によれば、非常に簡単な構成において、ノンブロッキング動作のダイレクトマップ方式やセットアソシアティブ方式のキャッシュ装置を実現できる。また従来技術では、ノンブロッキング動作のためにキャッシュメモリとは別に受信用のフィルＦＩＦＯを備える必要があったが、本発明の手法ではキャッシュメモリの領域の一部を受信領域に割り当てることでフィルＦＩＦＯを備える必要がない。またプリフェッチ構成にあるダイレクトマップ方式やセットアソシアティブ方式のキャッシュ判定回路を所望する連想数に合わせて差し替えることができる。 そしてフェッチ構成にあるデータ取得部とキャッシュメモリは、設定により記憶領域の中での受信領域とデータ領域の容量を変更すればよい。このように本実施形態のデータ供給装置（キャッシュ装置）を用いれば、設計工数を軽減しつつ、幅広い連想数のキャッシュ装置（方法）に対応することができる。
【００６９】
＜第３実施形態＞
これまでキャッシュ装置において本発明のデータ供給方法を適用してきたが、キャッシュ装置以外にも適用できることは明らかである。キャッシュ装置は入力された格納アドレスに対し、キャッシュ判定部１２０にてキャッシュヒット／キャッシュミスを評価し、対応するキャッシュデータをキャッシュメモリから読み出す。これに対しデータ処理装置１０１が、キャッシュ判定部１２０を経由せず（構成としてキャッシュ判定部１２０を含めず）、直接アクセス調停部１３０へ格納アドレスのデータを要求してもよい。このときデータ処理装置１０１は、例えばシーケンサ回路等により予め決められたパターンで、記憶装置への更新データの要求（キャッシュミスに相当）と、既に記憶装置からリフィル済みのデータの再要求（キャッシュヒットに相当）を繰り返す。データ取得部１８０は、この予め決められたパターンでリフィル・データを受け取りつつ、データバッファ（キャッシュメモリに相当）にデータを更新し、要求された記憶装置のデータを更新しながらデータ処理装置１０１へ供給し続ければよい。
【００７０】
本実施形態のデータ供給装置によれば、非常に簡単な構成において、ノンブロッキング動作のデータ取得とデータバッファへのデータ更新を実現できる。また従来技術では、ノンブロッキング動作のためにキャッシュメモリとは別に受信用のフィルＦＩＦＯを備える必要があったが、本発明の手法ではデータバッファの領域の一部を受信領域に割り当てることでフィルＦＩＦＯを備える必要がない。
【００７１】
＜その他の実施形態＞
また、上述までの説明では性能向上を目的とし、ノンブロッキング動作を前提に装置の動作を説明してきた。しかしながら本発明の装置は、例え中間待ち行列（ＦＩＦＯ）を備えないブロッキング動作においても適用できることは明らかである。例えば図９に中間待ち行列（ＦＩＦＯ）を備えない処理装置の一例を示す。アクセス調停部からデータ取得部へ直接「ライン番号、キャッシュミス・フラグ」９３５を送出する。またデータ取得部からアクセス調停部にフェッチ許可信号９８１を返すことでブロッキング動作を実現する。
【００７２】
キャッシュミス・フラグがキャッシュミスのとき受信領域に要求したデータがリフィルされるまでプリフェッチ許可信号９８１を「禁止」にし、アクセス調停部のプリフェッチ動作を停止すればよい。一方、キャッシュミス・フラグがキャッシュヒットのときはプリフェッチ許可信号９８１を「許可」のままとし、アクセス調停部のプリフェッチ動作を継続すればよい。要求したデータがリフィルされるまで受信ポインタとデータポインタの差は「０」のままであるためデータ取得部は図３を用いて説明した処理フローに従い、「待機」となる。前述までの説明と矛盾することなくブロッキング動作に対応できる。ブロッキング動作の場合は、受信領域がたとえ０段であっても対応できるのではあるが、本発明の趣旨に沿うにはリフィル・データを１段の受信領域に受けてから、キャッシュデータとして有効化するという手順を守る。これによりデータ取得部を動作に合わせて作り直す必要はなくなる。
【００７３】
また、上述までの説明では本発明の特徴である、受信領域を管理する情報（受信ポインタ）と、データ領域を管理する情報（データポインタ）とをデータ取得部に備えた。それによりキャッシュ判定部には、一般的なキャッシュ判定構成（装置／回路／論理）を使用することができる。しかしながら、これらの管理情報をキャッシュ判定部にキャッシュタグと並んで格納してもよい。そしてデータ取得部で行っていたキャッシュデータの格納先アドレスの算出や受信ポインタとデータポインタの差の算出を予めキャッシュ判定部にて行う。そして算出結果を中間待ち行列（ＦＩＦＯ）を介してデータ取得部に送る構成でも何ら問題は生じない。特に第２実施形態の場合、キャッシュライン毎に管理情報を記憶する必要があり、これらをキャッシュ判定部のタグメモリにキャッシュタグと並んで格納することで、キャッシュタグと管理情報の記憶構成を一体化できるという利点がある。
【００７４】
また、前述までの説明では、受信領域を管理する情報（受信ポインタ）と、データ領域を管理する情報（データポインタ）を用いて動作説明を行った。しかしながら、必ずしも記憶領域の格納先を指すポインタだけで管理を行う必要はなく、受信領域の状態を示す、受信ポインタと受信数で管理してもよい。この管理では、先のデータポインタは、受信ポインタから受信数を減算した値とすればよい。そして、リフィル・データが届く度に受信数が１つ増え、受信ポインタが更新される。そして、プリフェッチ構成から出力される情報（キャッシュミス・フラグ）に従い、キャッシュミスでは受信数が１つ減り、キャッシュヒットではそのままの受信数となる。この場合の利点は、受信領域の管理情報のみで本発明のデータ供給装置を制御することができるということである。つまり、受信領域の管理情報のみで制御できるという点において、データを記憶する記憶領域に、受信のために必要な受信領域を割り当てるという本発明の趣旨に、より合致していると言える。
【００７５】
また、前述の各実施例の処理は、複数のハードウエアとソフトウエアの協同によって実現するようにしてもよい。この場合、ネットワーク又は各種記憶媒体を介して取得したソフトウエア（プログラム）をコンピュータ等の処理装置（ＣＰＵ、プロセッサ）にて実行することで実現できる。また、本発明は前述した実施例の機能をコンピュータに実現させるプログラムを記憶した記憶媒体を、システム或いは装置に供給することによって実現してもよい。
【技術分野】
【０００１】
本発明は、コンピュータ・システムにおけるノンブロッキング動作を実現するためのデータ供給技術に関する。
【背景技術】
【０００２】
近年、さまざまな機器において処理性能の向上と、より一層のコスト削減の両立が求められている。これらの機器には、ある種のコンピュータ・システムが搭載されており、コンピュータ・システムの製造コストあたりの処理性能は、機器の良否を決定する要因の一つと言える。
一般的にコンピュータ・システムにはアプリケーションを実行するプロセッサやデータ処理回路と、プログラムや処理対象となるデータを記憶するメモリ等の記憶装置で構成される。プロセッサやデータ処理回路が使用するプログラムやデータのすべてが、各々のプロセッサやデータ処理回路から高速に読み書きできる記憶装置を具備することが理想である。例えば、記憶装置としてはＳＲＡＭ等のアクセス・レイテンシの比較的短いメモリ手段を、プロセッサやデータ処理回路の各々に専用のローカルメモリとして具備できれば、処理性能の向上を実現し易い。
しかしながら、機器を低コスト化するためには、多くのプロセッサやデータ処理回路で単一の記憶装置を共有し、搭載する記憶装置の個数を削減することが望ましい。また、搭載する記憶装置としてメモリを採用する場合、その時々で普及している安価なＤＲＡＭを使用することが多い。ただし安価なＤＲＡＭを使用すると前述のＳＲＡＭよりアクセス・レイテンシは長くなる。また多くのプロセッサやデータ処理回路で互いに単一の記憶装置を共有する場合、各々のプロセッサやデータ処理回路から記憶装置への読み書きが競合し、各々のアクセスを調停するため、プロセッサやデータ処理回路からのアクセス・レイテンシは長くなる。その結果、各々のプロセッサやデータ処理回路の処理性能は低下する。
前述のプロセッサやデータ処理回路の性能低下を抑えるために、各々のプロセッサやデータ処理回路と記憶装置との間にキャッシュ装置を設けることが多い。各々のプロセッサやデータ処理回路は、組み込んだキャッシュ装置から所望のデータが読み出せる間は、記憶装置にアクセス（データ要求）することはない。これにより各々のプロセッサやデータ処理回路からのアクセス（データ要求）の頻度が減り、必要となるアクセス帯域の総量を減らすことができる。当然、キャッシュ装置を設けることで回路規模は増加するが、上記のようにローカルメモリを専用に設けるよりは、回路規模は少なくてよい。このようにコンピュータ・システムに最適なキャッシュ装置を設けることで、機器を実現する際に求められる処理性能と低コストを両立することが可能となる。
キャッシュ装置に所望のデータが存在する場合（キャッシュヒットと言う）、記憶装置までアクセス（データ要求）する必要はなく、各々のプロセッサやデータ処理回路からのアクセス・レイテンシは短くなる。一方、キャッシュ装置に所望のデータが存在しない場合（キャッシュミスと言う）、当然ながら各々のプロセッサやデータ処理回路は記憶装置に所望のデータをアクセス（データ要求）する。このとき、アクセス・レイテンシはキャッシュ装置を設けない場合と同じである。一般的には、各々のプロセッサやデータ処理回路はデータを順番に処理するため、キャッシュミス時に記憶装置から所望なデータを読み出すまでの間、各々のプロセッサやデータ処理回路は一時停止する。当然ながら、プロセッサやデータ処理回路は、この一時停止により処理性能が低下する。このような動作をブロッキング動作という。またキャッシュミスのときに、データを読み出す行為をリフィル、読み出したデータをリフィル・データ、一度に読み出す単位をリフィル長、読み出す期間をリフィル・レイテンシという。
さらに処理性能を向上するため特許文献１は、上記のリフィル・レイテンシを隠蔽できるキャッシュ機構のデータ供給装置について言及している。特許文献１のパイプライン・プロセッサは、所定のパイプライン・ステージで行う処理のために必要なデータに対し、まず所定のパイプライン・ステージの前段（前処理）でキャッシュミスを評価する。そしてキャッシュミスのときは、この前段（前処理）で必要なデータを要求してリフィルを実行する。このとき、特許文献１のパイプライン・プロセッサは、リフィル・レイテンシより長い中間待ち行列（ＦＩＦＯ）をパイプライン・プロセッサ内部に備える。 そして特許文献１のパイプライン・プロセッサは、リフィル中の処理を含む後続の処理を、この中間待ち行例（ＦＩＦＯ）に順次格納していく。このように特許文献１のパイプライン・プロセッサは、この中間待ち行例（ＦＩＦＯ）に格納しながら次の処理のキャッシュミス／ヒットの評価を続けられるので前述のブロッキング動作のように、キャッシュミスの度に一時停止する必要がない。
一方、特許文献１のパイプライン・プロセッサは、キャッシュミスの度に必要とするデータを記憶装置から読み出し、キャッシュメモリに更新する前に、一旦 リフィル・データをフィルＦＩＦＯに格納することが必須となる。中間待ち行列（ＦＩＦＯ）の中にはキャッシュミスのデータ処理に先行する、キャッシュヒットのデータ処理があり、それらの処理を所定のパイプライン・ステージで終えなければ、キャッシュメモリを更新することはできない。そのため、特許文献１のパイプライン・プロセッサには、上記のフィルＦＩＦＯを必ず備える。このように中間待ち行例（ＦＩＦＯ）を用いて次のデータ処理のキャッシュミス／ヒット評価を行うような動作をノンブロッキング動作という。データ処理を行うコマンドは、中間待ち行列（ＦＩＦＯ）の中で遅延する。この遅延の間にリフィルが完了し、キャッシュミス時のリフィル・データがフィルＦＩＦＯにあれば、データ処理に際しフィルＦＩＦＯからリフィル・データを供給し、データ処理を実行できる。つまり、特許文献１のキャッシュ機構のデータ供給装置は、上記のような仕組みでキャッシュミス時のリフィル・レイテンシを隠蔽して一時停止することなくデータ処理を続けられる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第３８４６６３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら特許文献１の技術では、キャッシュメモリとは別に動作するリフィル・データを一旦、格納するためのフィルＦＩＦＯが必要となる。
本発明の目的は、処理性能を維持しながら、回路規模を削減することである。
【課題を解決するための手段】
【０００５】
上記目的を達成するため、本発明に係るデータ供給装置は、出力手段と、前記出力手段にデータを保持する記憶領域を備え、前記出力手段に当該記憶領域のデータを供給するフェッチ手段と、前記出力手段がデータを要求する前に、前記出力手段に供給すべきデータを外部に要求するプリフェッチ手段と、を備えるデータ供給装置であって、前記フェッチ手段は、前記記憶領域の一部を外部より供給されるデータを受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として割り当て、前記出力手段は前記フェッチ手段によって送信領域として割り当てられた領域のデータを出力することを特徴とする。
【発明の効果】
【０００６】
本発明によれば、ノンブロッキング動作で動作する装置にデータを供給するデータ供給装置について、処理性能を維持しつつフィルＦＩＦＯを削減し回路規模を低減できる。
【図面の簡単な説明】
【０００７】
【図１】第１実施形態の処理装置の一例を示すブロック図である。
【図２】第１実施形態のキャッシュ判定部の一例を示すブロック図である。
【図３】第１実施形態のデータ取得部の処理の一例を示すフローチャートである。
【図４】第１実施形態のキャッシュメモリの動作の一例を示す遷移図である。
【図５】第２実施形態のキャッシュ判定部の一例を示すブロック図である。
【図６】第２実施形態のデータ供給装置の一例を示すブロック図である。
【図７】第２実施形態のキャッシュメモリの一例を示すブロック図である。
【図８】第２実施形態のデータ取得部の処理の一例を示すフローチャートである。
【図９】ブロッキング動作をする処理装置の一例を示すブロック図である。
【発明を実施するための形態】
【０００８】
まず、前述の特許文献１について説明を補足する。特許文献１の技術では、キャッシュメモリとは別に動作するリフィル・データを一旦、格納するためのフィルＦＩＦＯが必要となる。
【０００９】
前述のようにキャッシュデータの読み書き先である記憶装置には、安価なＤＲＡＭを搭載する。一般的にＤＲＡＭへの読み書きは、ある程度の連続した記憶領域を一度にデータ要求（バースト・アクセス）する方がメモリ帯域の効率が良い。そのため、ＤＲＡＭへのアクセス単位は、このバースト・アクセスによる読み書き単位が望ましい。ＤＲＡＭを製造するときの半導体プロセスの微細化と製品ニーズから、ＤＲＡＭは製造世代と共に内部動作周波数は年々高くなっている。当然、このバースト・アクセスによる読み書きの単位も、年々大きくなる傾向がある。高性能を要求する製品ニーズから、今後もＤＲＡＭの読み書きの単位が大きくなり続けると予想される。
【００１０】
キャッシュ装置では、１つのキャッシュタグ（キャッシュアドレス）に対応するキャッシュデータ（キャッシュライン）を、このバースト・アクセスによる読み書き単位の整数倍に合わせることが多い。１つのキャッシュミスに対応する、前記リフィル・データの読み書き単位（リフィル長）は、当然ながら、このキャッシュラインと同容量となる。例えば、上記のＤＲＡＭとの関係でリフィル・データの読み書き単位は３２バイト〜１２８バイトに及ぶ。
【００１１】
前述のフィルＦＩＦＯは、先の中間待ち行列（ＦＩＦＯ）の中にある、キャッシュミスのコマンド数に対応したリフィル・データを十分格納する容量が必要となる。組み込み機器では、前記リフィル・レイテンシは数十サイクルから数百サイクルに及ぶので、中間待ち行列（ＦＩＦＯ）の段数もそれに準ずる。例えば、キャッシュヒット率が７５％の場合、中間待ち行列（ＦＩＦＯ）の２５％はキャッシュミスとなる。中間待ち行列（ＦＩＦＯ）が１２８段なら、フィルＦＩＦＯは、１２８段の２５％である３２段が必要となる。先ほどのリフィル・データの読み出し単位を考慮するとフィルＦＩＦＯは１Ｋバイト〜４Ｋバイトの容量となり、組込み機器において無視してよいほど小さいとは言えない。
【００１２】
特許文献１の技術のキャッシュ装置では、
１）プリフェッチ論理でキャッシュヒット／ミス評価で使用するキャッシュタグの記憶領域、
２）中間待ち行列（ＦＩＦＯ）の記憶領域、
３）フェッチ論理のフィルＦＩＦＯの記憶領域、
４）フェッチ論理のキャッシュデータを格納するキャッシュメモリの記憶領域、
が必要となる。前述の説明の通り、このうち回路規模に大きな影響を与えるのは、リフィル長の大きな「３）フィルＦＩＦＯ」と、「４）キャッシュメモリ」であり、特許文献１のように「３）フィルＦＩＦＯ」と、「４）キャッシュメモリ」が別のハードウエア構成として存在すると回路規模が増加してしまう。なお、「２）中間待ち行列」は、ＦＩＦＯ段数は多いものの、キャッシュヒット／ミス評価結果のフラグとキャッシュメモリの格納先のアドレスを伝搬するだけでよく、後述するようにＦＩＦＯそのもののデータ長は、リフィル長に比べ非常に小さい。
【００１３】
＜第１実施形態＞
以下、添付の図面を参照して本発明の好適な実施形態を説明する。
【００１４】
キャッシュ装置を組み込んだ処理装置と、このキャッシュ装置について詳細説明する。
【００１５】
（処理装置）
図１は、第１実施形態による処理装置の全体構成の一例を示すブロック図である。処理装置には、ＣＰＵ１６０、外部の記憶装置（外部メモリ）であるＤＲＡＭ１６５、ＤＲＡＭコントローラ１６６とシステムバス１６４が含まれる。また、ＤＲＡＭ１６５に対するデータの読み書きのために、データ読み出し用のＤＭＡＣ（Ｄｉｒｅｃｔ Ｍｅｍｏｒｙ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌｌｅｒ）であるＲＤＭＡＣ１６２とデータ書き込み用のＷＤＭＡＣ１６３も含まれる。また処理装置には、画像処理などのデータ処理を行うデータ処理装置１０１と、本発明のキャッシュ装置１１０が含まれる。なおデータ処理装置に含める処理装置の数は任意であり、処理装置の各々は、高速に固定処理するパイプライン回路で構成されていてもよいし、低速ではあるが、柔軟に処理内容を変更可能なプロセッサとプログラムで構成されていてもよい。
【００１６】
ＣＰＵ１６０は、制御バス１６１を介してＲＤＭＡＣ１６２、ＷＤＭＡＣ１６３、データ処理装置１０１を制御し、処理装置全体を統括制御する。ＣＰＵ１６０の指示によりＲＤＭＡＣ１６２は、システムバス１６４、ＤＲＡＭコントローラ１６６を介してＤＲＡＭ１６５に格納された画像やプログラムなどのデータを読み出し、データ処理装置１０１に入力する。データ処理装置１０１は、所望のデータ処理を行い、処理結果の画像などのデータをＷＤＭＡＣ１６３に送り出す。このとき、ＷＤＭＡＣ１６３は予めＣＰＵ１６０から指示されており、データ処理装置１０１から受け取ったデータをシステムバス１６４、ＤＲＡＭコントローラ１６６を介してＤＲＡＭ１６５に格納する。処理装置は、前述の一連の動作を実行することにより画像処理等のデータ処理を実施するのである。
【００１７】
前述のデータ処理の過程で、データ処理装置１０１は、接続されたキャッシュ装置１１０を介して、ＤＲＡＭ１６５から各種必要な対象データ（画像、映像、設定値、テーブル、属性情報など）を読み出してデータ処理に使用できる。またデータ処理装置１０１がプロセッサとプログラムで構成されている場合、キャッシュ装置１１０を介してプログラムを逐次的に読み出して処理を実行することも可能である。
【００１８】
（データ供給装置）
次にデータ供給装置（キャッシュ装置）の動作について詳細説明する。前述のデータ処理装置１０１は、データ供給装置（キャッシュ装置）を介してＤＲＡＭ１６５からデータを読み出すときに、ＤＲＡＭ１６５上のデータの格納アドレス１１３を、Ｉ／Ｆ１１２を介してキャッシュ判定部１２０に入力する。そして入力された格納アドレス１１３をもとにキャッシュ判定部１２０でキャッシュヒットもしくはキャッシュミスが判定される。
【００１９】
（キャッシュ判定部）
さらに図２を用いて図１記載の処理装置のキャッシュ判定部１２０の回路構成の一例について詳細説明する。第１実施形態では、連想（ライン選択）方式がフルアソシアティブ方式のキャッシュ装置について説明する。
【００２０】
前述の格納アドレス１１３がキャッシュ判定部１２０へ入力される。キャッシュ判定部１２０には、８個のキャッシュタグ２３０が記憶されており、８ノードのフルアソシアティブ方式のキャッシュ装置となる。また８個のキャッシュタグ２３０には、［０］〜［７］の番号が予め定められており、対応するキャッシュメモリの「相対」キャッシュライン番号を示している。「相対」番号である理由は後述する。入力された格納アドレス１１３と８個のキャッシュタグ２３０は、８個の比較器２２０で、「一致」が判定される。そして比較器２２０から８個の比較結果２２８が判定器２５０に出力される。
【００２１】
８個の比較結果２２８のうち、１つでも「一致」であれば、キャッシュヒットと評価される。８個の比較結果２２８のうち、いずれも「一致」でなければ、キャッシュミスと評価される。評価結果はキャッシュミス・フラグ２４０として、キャッシュ判定部１２０から出力される。
【００２２】
評価結果がキャッシュヒットの場合、「一致」したキャッシュタグの「相対」ライン番号が、ライン番号２４５としてキャッシュ判定部１２０から出力される。
【００２３】
また評価結果が、キャッシュミスの場合（分岐２５５のＹＥＳ）、入力された格納アドレス１１３がキャッシュタグ２３０へ書き込まれ、キャッシュタグが更新される。キャッシュタグ２３０は、シフトレジスタで構造された記憶領域である。評価結果がキャッシュミスの場合、シフト動作によりキャッシュタグの値が下流のキャッシュタグに移動する。つまり、キャッシュタグ［０］にはキャッシュタグ［１］の値が、キャッシュタグ［１］にはキャッシュタグ［２］の値が各々書き込まれる。同様の書き込みが繰り返され、キャッシュタグ［６］にはキャッシュタグ［７］の値が書き込まれる。そして最後にキャッシュタグ［７］に格納アドレス１１３の値が書き込まれる。評価結果がキャッシュミスの場合、上記のようなキャッシュタグの更新が行われ、ライン番号２４５としてライン［７］の値がキャッシュ判定部１２０から出力される。
【００２４】
このように必ず古いキャッシュタグ［０］のタグ情報が破棄される、キャッシュタグのリプレイス手法を、「ＦＩＦＯ方式（ラウンドロビン方式）」という。フルアソシアティブ方式のキャッシュ装置では、装置を簡単に実現できるので、リプレイス手法として「ＦＩＦＯ方式（ラウンドロビン方式）」を採用することが多い。
【００２５】
最後にキャッシュ判定部１２０は、上記のように求めたキャッシュミス・フラグ２４０とライン番号２４５に、入力された格納アドレス１１３を合わせてキャッシュ判定結果１２５として出力する。
【００２６】
本実施形態の処理装置では、キャッシュミス時のペナルティであるリフィル・レイテンシを隠蔽するためにノンブロッキングのキャッシュ機構を採用している。これは、たとえキャッシュ判定結果１２５がキャッシュミスと判定されても、後に必要となる情報「ライン番号、キャッシュミス・フラグ」１３５を中間待ち行列（ＦＩＦＯ）１４０に退避する。そして、キャッシュミスのキャッシュデータをＤＲＡＭ１６５から読み出し、キャッシュメモリ１９０へ格納する処理が完了する前に、次のデータのキャッシュ判定処理を先行して実行する。このような処理を行うことでキャッシュミスのキャッシュデータをＤＲＡＭ１６５からキャッシュメモリ１９０へリフィルしている間にも、続くデータに対するキャッシュ判定処理を行うことができる。したがって、キャッシュのキャッシュミス時の性能低下を抑制することが可能となる。
【００２７】
なお「アクセス調停部」の説明で後述するように、アクセス調停部１３０は、キャッシュミスのときにキャッシュ判定結果１２５の中から格納アドレス１１３に相当する格納アドレス１３２を取り出し送信ＦＩＦＯ１５０へ順次記憶する。ＤＲＡＭコントローラ１６６は、この送信ＦＩＦＯ１５０から格納アドレス１３２を受け取り、所望のデータ（リフィル・データ）をＤＲＡＭ１６５から読み出して、キャッシュメモリ１９０へ書き込んでいく。データ取得部１８０は、中間待ち行列（ＦＩＦＯ）１４０から「キャッシュミス・フラグ」を取り出して、キャッシュ判定の結果がキャッシュミスであったかキャッシュヒットであったかを特定する。データ取得部１８０は、キャッシュ判定の結果がキャッシュヒットのとき、キャッシュデータ１８５をキャッシュメモリ１９０から直接読み出してＩ／Ｆ１１６へ送り出す。一方、キャッシュ判定の結果がキャッシュミスのとき、「データ取得部」で後述するように、所望のキャッシュデータを更新する。そして、このキャッシュデータ１８５をＩ／Ｆ１１６へ送り出す。このようなキャッシュミスしたキャッシュデータをＤＲＡＭ１６５から読み出して、キャッシュメモリ１９０に更新する、一連の処理が前述のリフィルである。
【００２８】
（アクセス調停部）
アクセス調停部１３０は入力されたキャッシュ判定結果１２５が有効のとき動作し、それ以外は待機する。そしてアクセス調停部１３０は、キャッシュ判定の結果「キャッシュミス・フラグ」が有効／無効に応じて以下の処理を行う。
・キャッシュ判定の結果「キャッシュミス・フラグ」が有効（キャッシュミス）のとき、まず接続される２つのＦＩＦＯである、送信ＦＩＦＯ１５０、中間待ち行列（ＦＩＦＯ）１４０の格納領域の空き状態を評価する。さらにデータ取得部１８０からのプリフェッチ許可信号１８１の状態を評価する。２つのＦＩＦＯすべてに空き領域があり、プリフェッチ許可信号１８１の状態が「許可」である場合、「ライン番号、キャッシュミス・フラグ」１３５を中間待ち行列（ＦＩＦＯ）１４０に書き込む。また同時に、格納アドレス１３２を送信ＦＩＦＯ１５０に書き込む。２つのＦＩＦＯに空き領域がない、もしくはプリフェッチ許可信号１８１の状態が「許可」でない場合は、キャッシュ判定部１２０を停止（ストール）する。そして、２つのＦＩＦＯの格納領域が空き、かつ、プリフェッチ許可信号１８１の状態が「許可」になるまで待機する。
・キャッシュ判定の結果「キャッシュミス・フラグ」が無効（キャッシュヒット）のとき、中間待ち行列（ＦＩＦＯ）１４０の空き状態を評価する。そして記憶領域に空きがあれば、「ライン番号、キャッシュミス・フラグ」１３５を中間待ち行列（ＦＩＦＯ）１４０に書き込む。記憶領域に空きがなければ、キャッシュ判定部１２０を停止（ストール）し、格納領域が空くまで待機する。本実施形態の一例では、中間待ち行列（ＦＩＦＯ）１４０に格納する、「キャッシュミス・フラグ」は１ビット信号であり、「ライン番号」は３ビット信号でよいため、中間待ち行列（ＦＩＦＯ）１４０のデータ長は高々４ビット長となる。たとえ中間待ち行列（ＦＩＦＯ）１４０が１２８段あったとしても６４バイトの容量でよく、大きな記憶容量とは言えない。それ故、フルアソシアティブ方式のキャッシュタグのノード数や中間待ち行列（ＦＩＦＯ）の段数を増やすことは容易であり、中間待ち行列（ＦＩＦＯ）１４０が制約となることはない。
【００２９】
なお、上記で説明した「キャッシュ判定部」と「アクセス調停部」は、これから説明する「データ取得部」に対応したプリフェッチ構成（装置／回路／論理）となっている。そして、「キャッシュ判定部」と「アクセス調停部」は、データを必要とする所定のパイプライン・ステージに対し、先行するパイプライン・ステージと繋がり、所定のパイプライン・ステージに対する前処理にある。
【００３０】
（データ取得部）
データ取得部１８０は中間待ち行列（ＦＩＦＯ）１４０の格納領域に処理すべきデータがあるかどうかを評価する。中間待ち行列（ＦＩＦＯ）１４０が空の場合は処理すべきキャッシュ判定結果がないため、データ取得部１８０は当然ながら待機する。データ取得部１８０は、中間待ち行列（ＦＩＦＯ）１４０から処理すべきキャッシュ判定の評価結果である「ライン番号、キャッシュミス・フラグ」を取り出す（Ｓ３０５）。そして評価結果であるキャッシュミス・フラグの値に応じて次のキャッシュデータの取得動作を行う。図３（ａ）にデータ取得部１８０のキャッシュデータの取得動作の一例を示す。図４（ａ）に示すように本発明のキャッシュメモリ１９０は、「データ領域（送信領域、キャッシュ領域）」と「受信領域」を含んで構成される。そして、受信領域を管理する情報（受信ポインタ）と、データ領域を管理する情報（データポインタ）とをデータ取得部に備える。
・キャッシュミス・フラグが無効（キャッシュヒット）のときは、中間待ち行列（ＦＩＦＯ）１４０から同時に取り出したライン番号とキャッシュメモリ１９０の受信ポインタとデータポインタからキャッシュデータの格納アドレスを算出する。そして、その格納アドレスをもとに記憶済みのデータをキャッシュメモリ１９０からリードデータ１９２として読み出す（Ｓ３６０）。そして、要求されたキャッシュデータ１８５を、Ｉ／Ｆ１１６を介して処理装置１０１に送出する（Ｓ３６５）。なお、格納アドレスの算出方法については後述する。
【００３１】
キャッシュミス・フラグが有効（キャッシュミス）のとき、データ取得部１８０は受信ポインタとデータポインタの差を確認する（Ｓ３４０）。両ポインタに差がない（０の値）のとき（Ｓ３４０のＮＯ）、ＤＲＡＭ１６５からの要求されているリフィル・データがキャッシュメモリ１９０に届いていないと評価し、リフィル・データが届くまで待機する（Ｓ３４５）。両ポインタに差がある（０ではない値）のとき（Ｓ３４０のＹＥＳ）、ＤＲＡＭ１６５からの要求されているリフィル・データがキャッシュメモリ１９０に格納済みのためデータポインタを更新する（Ｓ３５０）。ここからキャッシュデータ１８５の出力までの手順は、前記のキャッシュミス・フラグが無効（キャッシュヒット）の手順と同様となる。
【００３２】
データ取得部１８０では、前述のキャッシュデータの取得動作とは並行して、要求されたリフィル・データの受信動作を行っている。図３（ｂ）にデータ取得部１８０のリフィル・データの受信動作の一例を示す。ＤＲＡＭ１６５からの要求されているリフィル・データがデータ取得部１８０に届いた場合（Ｓ３８０のＹＥＳ）、受信ポインタを更新する（Ｓ３８５）。次にデータ取得部１８０は受信ポインタとデータポインタの差を確認する（Ｓ３９０）。両ポインタに差が予め定められた受信の閾値と同数であるとき（Ｓ３９０のＹＥＳ）、これ以上、リフィル・データを受信することができないので、プリフェッチ許可信号１８１を「禁止」にする（Ｓ３９４）。両ポインタに差が予め定められた受信の閾値より小さいとき（Ｓ３９０のＮＯ）、ＤＲＡＭ１６５からリフィル・データを受け取ることができるので、プリフェッチ許可信号１８１は「許可」のままでよい（Ｓ３９２）。
【００３３】
回路実装では、アクセス調停部１３０の方がデータ取得部１８０より前段にある。それ故、データ取得部１８０からのプリフェッチ許可信号１８１を受け取ってから、アクセス調停部１３０でＤＲＡＭへのアクセス（データ要求）を止めても遅いケースがある。このような回路の位置関係からくるレイテンシの違いを考慮して、前記の受信の閾値を、予め記憶できる受信段数より少なく設定してもよい。また、より厳密な手法としては、リフィル待ち数を新たに定義し、このリフィル待ち数を用いてプリフェッチ許可信号１８１を生成してもよい。新たに定義するリフィル待ち数とは、０から開始し、アクセス調停部１３０でキャッシュミスの度に１を加算し、データ取得部にリフィル・データが到着する度に１を減算した数とする。
【００３４】
つまり、リフィル待ち数とは、データ要求を行ったが、まだフェッチ構成に到達していないリフィル・データの数を表している。そして、受信済みのリフィル・データ数（受信ポインタとデータポインタの差）とリフィル待ち数の合計値が将来受信するリフィル・データ数となる。この将来受信する数が受信の閾値より小さい場合、プリフェッチ許可信号１８１は「許可」とし、将来受信する数が受信の閾値と同じ数であればプリフェッチ許可信号１８１は「禁止」とするのである。
【００３５】
（データ取得部とキャッシュメモリの動作例）
図４（ｂ）を用いてキャッシュメモリ調停回路１８０とキャッシュメモリ１９０の具体的な動作の一例について説明する。
【００３６】
まず、状態［０］はリセット直後の初期状態を示している。初期状態では受信領域の開始を示す受信ポインタは「０」の値である。またデータ領域の上端を示すデータポインタは「０」での値である。この動作の一例では、受信領域は４段、データ領域は８段となっている。キャッシュメモリ１９０は合計１２段の記憶領域となっている。記憶領域には図面の下側から上側に向かて「０」から「１１」の番号が記載されており、キャッシュメモリ１９０のアドレスを示している。また記憶領域の１段は、１回のＤＲＡＭアクセス（データ要求）に対応するリフィル・データ（リフィル長）を格納できる記憶領域であり、１キャッシュラインに相当する。
【００３７】
次にアクセス調停部１３０で１回のミスヒット評価による１回のリフィル要求があり、そのリフィル・データがデータ取得部１８０に届いたとき（［Ａ］リフィル・データを１つ受信）、キャッシュメモリ１９０は状態［１］になる。状態［１］では、図３（ｂ）の動作手順に従い、１つのリフィル・データがキャッシュメモリに格納される。そして、受信ポインタが「１」の値となる。データポインタは「０」の値のままであり、受信ポインタとデータポインタの差は「１」の値となる。この差は受信数を表しており、受信領域は４段であったので残りの受信領域は３段となる。
【００３８】
次に中間待ち行列（ＦＩＦＯ）１４０を介してキャッシュミスのデータがキャッシュ調停部１８０に入力され（［Ｂ］キャッシュミスが１回発生）、キャッシュメモリ１９０は状態［２］となる。状態［２］では、図３（ａ）の動作手順に従い、１つのキャッシュデータが有効となる。そして、データポインタが「１」の値となる。データポインタはデータ領域の上限を示しており、データポインタの位置は仮想的にデータ領域のライン番号「８」に相当すると定義する。データポインタが「１」となった状態［２］のケースでは、有効化されたキャッシュデータはキャッシュメモリ１９０のアドレス「０」の領域にある。データポインタの指し示す「１」がライン番号「８」に相当するのに対応して、このアドレス「０」の領域は、ライン番号「７」（＝８−１）を指示している。前述の「キャッシュ判定部」の説明で判定の結果がキャッシュミスのときのライン番号が「７」になると説明した動作に合致している。このとき、前述のリフィル・データを受け取った受信領域の一部が、データ領域に置き換わることとなる。
【００３９】
キャッシュメモリ１９０はリング式ＦＩＦＯと同様に、アドレス「１１」とアドレス「０」に連続していると考える。アドレス「０」の領域がライン番号「７」に対応している規則と同様に、アドレス「１１」の領域はライン番号「６」を示している。 さらにアドレス「１０」の領域はライン番号「５」を示している。同様の規則を繰り返し、アドレス「５」の領域がライン番号「０」を示している。データ領域はアドレス「５」からアドレス「１１」を経てアドレス「０」の領域までとなる。
【００４０】
そして残りのアドレス「１」からアドレス「４」までの領域が受信領域となる。状態［２］では、受信ポインタとデータポインタの値が同一となり、受信済みのリフィル・データが格納済みのキャッシュデータに変わることで受信領域が１段回復している。つまり、受信領域の一部とデータ領域の一部が置き換わり（交換され）、キャッシュメモリに対する受信領域の割り当てが更新されている。
【００４１】
さらにアクセス調停部１３０で４回のミスヒット評価が連続し、４回のリフィル要求の後、その４つのリフィル・データがデータ取得部１８０に届いたとき（［Ｃ］リフィル・データを４つ受信）、キャッシュメモリ１９０は状態［３］になる。状態［３］では、４つのリフィル・データがキャッシュメモリに格納される。そして、受信ポインタが「５」の値となる。データポインタは「１」の値のままであり、受信ポインタとデータポインタの差は「４」の値となる。この差は受信数を表しており、受信領域は４段であったので残りの受信領域は０段となる。説明を簡単にするために前述の受信の閾値は、受信領域の数「４」と同じ設定とする。このとき、受信数と受信の閾値は同じ値であるので、これ以上、リフィル・データを受け取ることはできない。そのため、キャッシュ調停部１８０は、プリフェッチ許可信号１８１を「禁止」にしてアクセス調停部１３０に通知し、ノンブロッキング・アクセスを一旦、停止する。プリフェッチ構成は、記憶装置へのデータ要求を止めることとなる。
【００４２】
さらに、４つのキャッシュミスのデータがキャッシュ調停部１８０に連続して入力され（［Ｄ］キャッシュミスが連続４回発生）、キャッシュメモリ１９０は状態［４］となる。状態［４］では、４つのキャッシュデータが有効となる。そして、データポインタが「５」の値となる。データ領域は残り３段となる。
【００４３】
さらに、［Ｅ］リフィル・データを４つ受信し、状態［５］を経て、［Ｆ］キャッシュミスが連続４回発生し、状態［６］となる。状態［６］では、受信ポインタとデータポインタは共に「９」の値であり、データ領域はアドレス「１」から「８」までとなり、受信領域はアドレス「９」からアドレス「１１」を経てアドレス「０」までとなる。状態［５］から状態［６］に至るまでの過程で、データ領域の残りは０段となっており、これ以降、データ領域の８段すべてには何かしら有効なキャッシュデータが格納されている。また状態［６］では、状態［２］でアドレス「０」に格納されていたキャッシュデータは、データ領域の外側の受信領域に存在することになる。このキャッシュデータはもともと最も古く、状態［５］から状態［６］までの一連の動作の過程で、データ領域から破棄されたことになる。古いキャッシュデータから順に置き換えられるのでＦＩＦＯ方式（ラウンドロビン方式）のリプレイス手法と合致する。 このように受信領域の一部がデータ領域に置き換わり、データ領域の一部が受信領域に置き換わり（交換され）、結果として受信領域の割り当てが更新されている。
【００４４】
これまで説明した動作と同様により、キャッシュメモリ１９０は、動作［Ｇ］、動作［Ｈ］に対応して状態［７］、状態［８］へと遷移する。
【００４５】
なお、図４（ｂ）の状態［３］において、受信数が受信の閾値となったためノンブロッキング動作を停止すると説明した。しかしながら、状態［０］（初期状態）から状態［３］までの間は、データ領域には有効なキャッシュデータが保持されているわけではない。つまり、状態［０］（初期状態）からすべてのデータ領域が一度有効なキャッシュデータで埋まるまでの間は、受信の閾値を４段ではなく１２段とし、初期状態の受信領域を増加させる。このような工夫により、初期時のノンブロッキング動作の停止を抑制し、性能をさらに向上することができる。このようなことができるのは、受信領域とデータ領域を一体化したからに他ならない。
【００４６】
以上、説明した「データ取得部」は要求されたデータを取得する、フェッチ構成（装置／回路／論理）となっている。そして、取得したデータを所定のパイプライン・ステージにデータ供給する。
【００４７】
本実施形態のキャッシュ装置によれば、簡単な構成によって、ノンブロッキング動作のフルアソシアティブ方式のキャッシュ装置を実現できる。また従来技術では、ノンブロッキング動作のためにキャッシュメモリとは別に受信用のフィルＦＩＦＯを備える必要があったが、本発明の手法ではキャッシュメモリの領域の一部を受信領域に割り当てることでフィルＦＩＦＯを備える必要がない。一般的に、ある記憶領域を内蔵ＳＲＡＭで実現するとき、同容量の記憶領域に対して１つの内蔵ＳＲＡＭで構成する場合より、複数の内蔵ＳＲＡＭに分割して構成する方が回路規模は増大する。本発明の手法では、従来技術で言うところのフィルＦＩＦＯとキャッシュメモリを１つの内蔵ＳＲＡＭで構成できるのでキャッシュ装置の回路規模を小さく抑えることができる。
【００４８】
また従来技術では、キャッシュミス時にリフィル・データをフィルＦＩＦＯに一旦書き込み、さらにフィルＦＩＦＯから読み出してキャッシュメモリに再び書き込み、キャッシュデータとして利用する。従来技術では少なくとも、フィルＦＩＦＯとキャッシュメモリに２回の書き込みと１回の読み出しが必要となる。本発明の方法では、データ受信とデータ保持が一つの記憶領域に統合されているので、キャッシュミス時に記憶領域に対し、１回の書き込みと１回の読み出しでよい。本発明の手法をハードウエアで実現する場合、内蔵ＳＲＡＭの制御回路も簡易化が可能である。また本発明の手法をソフトウエアで実現したとしても、記憶領域へのアクセス回数が少なくてよいので、処理の高速化が可能となる。
【００４９】
本発明の主旨は、キャッシュメモリに受信領域を統合して、キャッシュメモリへのアクセス回数を削減することである。そのため、本実施形態のように受信ポインタとデータポインタを用いてキャッシュメモリと受信領域を関係付ける方法である必要はなく、キャッシュメモリと受信領域を関係付けるための対応表（リンクテーブル）を別途記憶し、プリフェッチ手段の情報に従い、対応表（リンクテーブル）を更新する関連付け方法でも良い。
【００５０】
また、本実施形態はＦＩＦＯ方式（ラウンドロビン方式）を採用しているフルアソシアティブ方式のキャッシュ装置にも適用できる。
【００５１】
＜第２実施形態＞
（データ供給装置）
次にフルアソシアティブ方式とは異なる連想（ライン選択）方式である、ダイレクトマップ方式やセットアソシアティブ方式に本発明のデータ供給方法を適用した場合の動作について詳細説明する。第１実施形態ではフルアソシアティブ方式の連想（ライン選択）方式を採用していたため、一般的な実装方法ではキャッシュタグをレジスタで構成することになる。そのため、あまり大きな数のキャッシュタグ数に対応するとキャッシュタグの回路規模が大きくなる課題がある。ダイレクトマップ方式やセットアソシアティブ方式の利点は、キャッシュタグをＳＲＡＭ等の記憶装置（タグメモリ）で構成することで回路規模を抑えられる点にある。もちろんダイレクトマップ方式やセットアソシアティブ方式においてもキャッシュタグをレジスタで構成できることは言うまでもない。
【００５２】
なお、第１実施形態と本実施形態との主な違いである「キャッシュ判定部」と「データ取得部」について詳細説明し、第１実施形態と同様の動作については以降での説明を割愛する。
【００５３】
（ダイレクトマップ方式のキャッシュ判定部）
図５（ａ）を用いて図１記載の処理装置のキャッシュ判定部１２０の回路構成の一例について詳細説明する。
【００５４】
前述の格納アドレス１１３がキャッシュ判定部１２０へ入力される。キャッシュ判定部１２０には、Ｎ個のキャッシュタグ５３０がタグメモリ（ＳＲＡＭ）に記憶されており、Ｎラインのダイレクトマップ方式のキャッシュ装置となる。またＮ個のキャッシュタグ５３０には、［０］〜［Ｎ−１］の番号が予め定められており、対応するキャッシュメモリのキャッシュライン番号を示している。まず格納アドレス１１３のうち、前述のキャッシュタグ［０］〜［Ｎ−１］の番号に対応する信号を抜き出し、下位アドレス５１５とする。そして残りの値を表現できる信号を抜き出し、上位アドレス５１２とする。次に下位アドレス５１５を用いてキャッシュタグ５３０から対応するキャッシュタグ［ｋ］５３５を読み出す。そして比較器５２０を用いて上位アドレス５１２とキャッシュタグ５３５の「一致」を判定する。比較器５２０から１個の比較結果５２８が判定器５５０に出力される。比較結果５２８が「一致」であれば、キャッシュヒットと評価される。比較結果５２８が「一致」でなければ、キャッシュミスと評価される。評価結果はキャッシュミス・フラグ２４０として、キャッシュ判定部１２０から出力される。
【００５５】
また評価結果が、キャッシュミスの場合（分岐５５５のＹＥＳ）、格納アドレス１１３がキャッシュタグ５３０へ書き込まれ、キャッシュタグが更新される。なお、ダイレクトマップ方式の場合、キャッシュタグは１個しかないため、リプレイス手法について考える必要はない。第１実施形態とは異なり、評価結果がキャッシュヒットの場合もキャッシュミスの場合も下位アドレス５１５の値がライン番号２４５としてキャッシュ判定部１２０から出力される。
【００５６】
以上の説明から明らかなようにキャッシュ判定部１２０には一般的なダイレクトマップ方式のキャッシュ判定構成（装置／回路／論理）を用いて差し支えない。
【００５７】
（セットアソシアティブ方式のキャッシュ判定部）
同様に図５（ｂ）を用いて図１記載の処理装置のキャッシュ判定部１２０の回路構成の一例について詳細説明する。多くの動作は前述のダイレクトマップ方式のキャッシュ判定部と同じである。図５（ｂ）は４ウェイ・セットアソシアティブ方式の一例であり、ダイレクトマップ方式と異なる点について言及する。
【００５８】
キャッシュ判定部１２０には、４×Ｎ個のキャッシュタグ５３０がタグメモリ（ＳＲＡＭ）に記憶されており、Ｎラインの４ウェイ・セットアソシアティブ方式のキャッシュ装置となる。またＮ個のキャッシュタグ５３０には、［０］［＊］〜［Ｎ−１］［＊］の番号が予め定められており、対応するキャッシュメモリのキャッシュライン番号を示している。また［＊］はウェイ番号を示し、本実施形態では４ウェイのため［＊］には［０］から［３］の値が入る。下位アドレス５１５を用いてキャッシュタグ５３０から対応する４個のキャッシュタグ［ｋ］［０］〜［ｋ］［３］５３５を読み出す。そして４個の比較器５２０を用いて上位アドレス５１２と４個のキャッシュタグ［ｋ］［０］〜［ｋ］［３］５３５の各々について「一致」を判定する。４個の比較器５２０から、４個の比較結果５２８が判定器５５０に出力される。４個の比較結果５２８のうち１つでも「一致」であれば、キャッシュヒットと評価される。また４個の比較結果５２８が何れも「一致」でなければ、キャッシュミスと評価される。評価結果はキャッシュミス・フラグ２４０として、キャッシュ判定部１２０から出力される。
【００５９】
また評価結果が、キャッシュミスの場合（分岐５５５のＹＥＳ）、ＦＩＦＯ方式（ラウンドロビン方式）のリプレイス手法を用いて最も古いウェイ番号を選択する。そして、そのウェイ番号のキャッシュタグのみ格納アドレス１１３と差し換え、その他のウェイ番号のキャッシュタグはそのままの値で、キャッシュタグ５３０が更新される。
【００６０】
以上の説明から明らかなようにキャッシュ判定部１２０には、一般的なセットアソシアティブ方式のキャッシュ判定構成（装置／回路／論理）を用いて差し支えない。
【００６１】
（データ取得部）
まず、図６を用いて第１実施形態と異なる本実施形態のデータ供給装置（キャッシュ装置）の特徴について言及する。本実施形態では、キャッシュミスで記憶装置に所望のデータを要求する際、ライン番号用の中間待ち行列（ＦＩＦＯ）６４５にキャッシュミス時のライン番号を格納する。そして、データ取得部１８０は、この中間待ち行例（ＦＩＦＯ）６４５を介し、キャッシュミス時のリフィル・データのキャッシュメモリへの格納先を示すライン番号を取得する。なお、この中間待ち行列（ＦＩＦＯ）６４５に空きがない場合、当然ながらアクセス調停部１３０は停止（ストール）する。
【００６２】
また図７を用いて本実施形態のキャッシュメモリ１９０の一例について説明する。この一例では同容量の記憶領域を、ダイレクトマップ方式に対応した場合（図７（ａ）記載）と、４ウェイ・セットアソシアティブ方式に対応した場合（図７（ｂ）記載）の２種の連想（ライン選択）方式に対応できることを説明している。この一例では、１つのキャッシュラインに対して８個の格納先が予め割り当てられている。ダイレクトマップ方式では７個の受信領域と１個のデータ領域が割り当てられており、４ウェイ・セットアソシアティブ方式では４個の受信領域と４個のデータ領域が割り当てられている。本実施形態のキャッシュメモリは、必ず１つのキャッシュラインに対して複数の格納先を持ち、データ取得部１８０への外部からのレジスタ設定等により、複数の格納先を受信領域とデータ領域に分配できる仕組みを持つ。一例では、まず、ダイレクトマップ方式のデータ領域は格納先１個とし、４ウェイ・セットアソシアティブ方式のデータ領域は格納先４個のように、アドレス１つにつき連想するキャッシュタグの数に合わせてデータ領域の格納先を割り当てる。 そして残りの格納先を受信領域とする。このように受信領域とデータ領域の分配を変更することで、同一のキャッシュメモリを異なる連想（ライン選択）方式に対応させている。キャッシュ判定部１２０を、連想（ライン選択）方式の異なる種々の判定回路に置き換えても、データ取得部１８０とキャッシュメモリ１９０は変更することなく使用できる。なお、記憶領域から連想（ライン選択）方式に応じたデータ領域を割り当てるが、残りの記憶領域に対しては、少なくとも１つの記憶先を受信領域に割り当てればよい。必ずしも残りの記憶領域すべてを受信領域に割り当てる必要はなく、受信ポインタとデータポインタの算出を工夫して、余った格納先を別用途で使用してもよい。
【００６３】
次にデータ取得部１８０のキャッシュデータの取得動作の一例を図８（ａ）に示し、リフィル・データの受信動作の一例を図８（ｂ）に示す。まず図７に示すように、本実施形態のデータ取得部１８０はキャッシュライン毎に受信ポインタとデータポインタを備える。そこで、データ取得動作やリフィル・データ受信動作において、最初に関連するライン番号から、対応する受信ポインタとデータポインタを選択する必要がある。例えば、データ取得動作においてデータ取得部１８０は、中間待ち行列（ＦＩＦＯ）１４０から処理すべきキャッシュ判定結果である「ライン番号、キャッシュミス・フラグ」を取り出す（Ｓ８０５）。そして、ライン番号を基に対応する受信ポインタとデータポインタを取得する（Ｓ８０２）。また、リフィル・データ受信動作においてデータ取得部１８０は、キャッシュミスに関するライン番号用の中間待ち行列（ＦＩＦＯ）６４５から関連するライン番号を取り出す（Ｓ８８２）。そして、そのライン番号を基に対応する受信ポインタ取り出し、更新する（Ｓ８８５）。
【００６４】
対応する受信ポインタとデータポインタを選択した後のデータ取得動作やリフィル・データ受信動作は、第１実施形態と同様の動作でよい。
【００６５】
（データ取得部とキャッシュメモリの動作例）
上記のような手法でライン番号が取り出され、キャッシュメモリ上の記憶領域がライン番号により定まった後は、アドレス算出を始め、受信ポインタやデータポインタの関係など第１実施形態と同様の動作でよい。
【００６６】
なお、データ取得部１８０からアクセス調停部１３０へのプリフェッチ許可信号６８１は、すべてのキャッシュラインに対応した受信ポインタとデータポインタから算出される１ビットの許可信号をキャッシュライン分、束ねた信号となる。この点が、第１実施形態とは異なるため注意が必要である。
【００６７】
なお、セットアソシアティブ方式の連想（ライン選択）方式は、第１実施形態と同様にＦＩＦＯ（ラウンドロビン）方式のリプレイス手法となる。しかしながら、ダイレクトマップ方式の連想（ライン選択）方式は、連想数が１個であるため、ＦＩＦＯ（ラウンドロビン）方式のリプレイス手法とは呼ばない。 ダイレクトマップ方式の連想（ライン選択）方式は、この点が他の連想（ライン選択）方式と異なるため注意が必要である。
以上、説明した「データ取得部」は、ダイレクトマップ方式やセットアソシアティブ方式の連想（ライン選択）方式に対応して、要求されたデータを取得する、フェッチ構成（装置／回路／論理）となっている。
【００６８】
本実施形態のデータ供給装置（キャッシュ装置）によれば、非常に簡単な構成において、ノンブロッキング動作のダイレクトマップ方式やセットアソシアティブ方式のキャッシュ装置を実現できる。また従来技術では、ノンブロッキング動作のためにキャッシュメモリとは別に受信用のフィルＦＩＦＯを備える必要があったが、本発明の手法ではキャッシュメモリの領域の一部を受信領域に割り当てることでフィルＦＩＦＯを備える必要がない。またプリフェッチ構成にあるダイレクトマップ方式やセットアソシアティブ方式のキャッシュ判定回路を所望する連想数に合わせて差し替えることができる。 そしてフェッチ構成にあるデータ取得部とキャッシュメモリは、設定により記憶領域の中での受信領域とデータ領域の容量を変更すればよい。このように本実施形態のデータ供給装置（キャッシュ装置）を用いれば、設計工数を軽減しつつ、幅広い連想数のキャッシュ装置（方法）に対応することができる。
【００６９】
＜第３実施形態＞
これまでキャッシュ装置において本発明のデータ供給方法を適用してきたが、キャッシュ装置以外にも適用できることは明らかである。キャッシュ装置は入力された格納アドレスに対し、キャッシュ判定部１２０にてキャッシュヒット／キャッシュミスを評価し、対応するキャッシュデータをキャッシュメモリから読み出す。これに対しデータ処理装置１０１が、キャッシュ判定部１２０を経由せず（構成としてキャッシュ判定部１２０を含めず）、直接アクセス調停部１３０へ格納アドレスのデータを要求してもよい。このときデータ処理装置１０１は、例えばシーケンサ回路等により予め決められたパターンで、記憶装置への更新データの要求（キャッシュミスに相当）と、既に記憶装置からリフィル済みのデータの再要求（キャッシュヒットに相当）を繰り返す。データ取得部１８０は、この予め決められたパターンでリフィル・データを受け取りつつ、データバッファ（キャッシュメモリに相当）にデータを更新し、要求された記憶装置のデータを更新しながらデータ処理装置１０１へ供給し続ければよい。
【００７０】
本実施形態のデータ供給装置によれば、非常に簡単な構成において、ノンブロッキング動作のデータ取得とデータバッファへのデータ更新を実現できる。また従来技術では、ノンブロッキング動作のためにキャッシュメモリとは別に受信用のフィルＦＩＦＯを備える必要があったが、本発明の手法ではデータバッファの領域の一部を受信領域に割り当てることでフィルＦＩＦＯを備える必要がない。
【００７１】
＜その他の実施形態＞
また、上述までの説明では性能向上を目的とし、ノンブロッキング動作を前提に装置の動作を説明してきた。しかしながら本発明の装置は、例え中間待ち行列（ＦＩＦＯ）を備えないブロッキング動作においても適用できることは明らかである。例えば図９に中間待ち行列（ＦＩＦＯ）を備えない処理装置の一例を示す。アクセス調停部からデータ取得部へ直接「ライン番号、キャッシュミス・フラグ」９３５を送出する。またデータ取得部からアクセス調停部にフェッチ許可信号９８１を返すことでブロッキング動作を実現する。
【００７２】
キャッシュミス・フラグがキャッシュミスのとき受信領域に要求したデータがリフィルされるまでプリフェッチ許可信号９８１を「禁止」にし、アクセス調停部のプリフェッチ動作を停止すればよい。一方、キャッシュミス・フラグがキャッシュヒットのときはプリフェッチ許可信号９８１を「許可」のままとし、アクセス調停部のプリフェッチ動作を継続すればよい。要求したデータがリフィルされるまで受信ポインタとデータポインタの差は「０」のままであるためデータ取得部は図３を用いて説明した処理フローに従い、「待機」となる。前述までの説明と矛盾することなくブロッキング動作に対応できる。ブロッキング動作の場合は、受信領域がたとえ０段であっても対応できるのではあるが、本発明の趣旨に沿うにはリフィル・データを１段の受信領域に受けてから、キャッシュデータとして有効化するという手順を守る。これによりデータ取得部を動作に合わせて作り直す必要はなくなる。
【００７３】
また、上述までの説明では本発明の特徴である、受信領域を管理する情報（受信ポインタ）と、データ領域を管理する情報（データポインタ）とをデータ取得部に備えた。それによりキャッシュ判定部には、一般的なキャッシュ判定構成（装置／回路／論理）を使用することができる。しかしながら、これらの管理情報をキャッシュ判定部にキャッシュタグと並んで格納してもよい。そしてデータ取得部で行っていたキャッシュデータの格納先アドレスの算出や受信ポインタとデータポインタの差の算出を予めキャッシュ判定部にて行う。そして算出結果を中間待ち行列（ＦＩＦＯ）を介してデータ取得部に送る構成でも何ら問題は生じない。特に第２実施形態の場合、キャッシュライン毎に管理情報を記憶する必要があり、これらをキャッシュ判定部のタグメモリにキャッシュタグと並んで格納することで、キャッシュタグと管理情報の記憶構成を一体化できるという利点がある。
【００７４】
また、前述までの説明では、受信領域を管理する情報（受信ポインタ）と、データ領域を管理する情報（データポインタ）を用いて動作説明を行った。しかしながら、必ずしも記憶領域の格納先を指すポインタだけで管理を行う必要はなく、受信領域の状態を示す、受信ポインタと受信数で管理してもよい。この管理では、先のデータポインタは、受信ポインタから受信数を減算した値とすればよい。そして、リフィル・データが届く度に受信数が１つ増え、受信ポインタが更新される。そして、プリフェッチ構成から出力される情報（キャッシュミス・フラグ）に従い、キャッシュミスでは受信数が１つ減り、キャッシュヒットではそのままの受信数となる。この場合の利点は、受信領域の管理情報のみで本発明のデータ供給装置を制御することができるということである。つまり、受信領域の管理情報のみで制御できるという点において、データを記憶する記憶領域に、受信のために必要な受信領域を割り当てるという本発明の趣旨に、より合致していると言える。
【００７５】
また、前述の各実施例の処理は、複数のハードウエアとソフトウエアの協同によって実現するようにしてもよい。この場合、ネットワーク又は各種記憶媒体を介して取得したソフトウエア（プログラム）をコンピュータ等の処理装置（ＣＰＵ、プロセッサ）にて実行することで実現できる。また、本発明は前述した実施例の機能をコンピュータに実現させるプログラムを記憶した記憶媒体を、システム或いは装置に供給することによって実現してもよい。
【特許請求の範囲】
【請求項１】
出力手段と、データを保持する記憶領域を備え前記出力手段に当該記憶領域のデータを供給するフェッチ手段と、前記出力手段がデータを要求する前に前記出力手段に送信すべきデータを外部に要求するプリフェッチ手段と、を有するデータ供給装置であって、
前記フェッチ手段は、外部より受信するデータを前記記憶領域の一部である受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として割り当て、前記出力手段は前記フェッチ手段によって送信領域として割り当てられた領域のデータを出力することを特徴とするデータ供給装置。
【請求項２】
前記フェッチ手段は、前記記憶領域の一部を前記受信領域として割り当て、外部より供給されるデータを当該受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として再び割り当てることを特徴とする請求項１に記載のデータ供給装置。
【請求項３】
複数のステージを有するパイプライン手段を更に有し、前記フェッチ手段は前記複数のステージのうちの１つにデータを供給し、前記プリフェッチ手段は前記フェッチ手段がデータを供給するステージに先行するステージの動作に応じてデータを要求することを特徴とする請求項１又は２に記載のデータ供給装置。
【請求項４】
前記プリフェッチ手段で要求されたデータが前記フェッチ手段に届いたときに前記受信領域を管理する管理情報を更新することを特徴とする請求項１乃至３のいずれか１項に記載のデータ供給装置。
【請求項５】
前記記憶領域に対する前記受信領域の容量を変更することを特徴とする請求項１乃至４のいずれか１項に記載のデータ供給装置。
【請求項６】
前記受信領域の管理情報に基づいて前記プリフェッチ手段のデータ要求を停止することを特徴とする請求項４に記載のデータ供給装置。
【請求項７】
前記受信領域の管理情報に基づいて前記フェッチ手段からのデータ供給を待機することを特徴とする請求項４又は６に記載のデータ供給装置。
【請求項８】
前記プリフェッチ手段と前記フェッチ手段との間に中間待ち行列を備えることを特徴とする請求項１乃至７のいずれか１項に記載のデータ供給装置。
【請求項９】
請求項１乃至８のいずれか１項に記載のデータ供給装置と、キャッシュ判定手段とを備え、前記フェッチ手段の前記記憶領域に前記キャッシュ判定手段に対応するキャッシュデータを格納することを特徴とするキャッシュ装置。
【請求項１０】
ラウンドロビン方式のリプレイス手法を用いることを特徴とする請求項９に記載のキャッシュ装置。
【請求項１１】
連想（ライン選択）方式がフルアソシアティブ方式であることを特徴とする請求項９に記載のキャッシュ装置。
【請求項１２】
連想（ライン選択）方式がセットアソシアティブ方式であることを特徴とする請求項９に記載のキャッシュ装置。
【請求項１３】
連想（ライン選択）方式がダイレクトマップ方式であることを特徴とする請求項９に記載のキャッシュ装置。
【請求項１４】
前記フェッチ手段は前記受信領域を示す受信ポインタと前記送信領域を示すデータポインタとを管理し、当該受信ポインタ又はデータポインタを更新することによって、前記受信領域又は前記送信領域の割り当てを変更することを特徴とする請求項１乃至８のいずれか１項に記載のデータ供給装置。
【請求項１５】
出力手段と、前記出力手段が要求する前に前記出力手段に送信すべきデータを要求するプリフェッチ手段と、データを保持する記憶領域と、を有するデータ供給装置によるデータ供給方法であって、
外部より受信するデータを前記記憶領域の一部である受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として割り当て、前記出力手段は前記フェッチ手段によって送信領域として割り当てられた領域のデータを出力することを特徴とするデータ供給方法。
【請求項１６】
出力手段と、前記出力手段が要求する前にキャッシュ判定により前記出力手段に送信すべきデータを要求するプリフェッチ手段と、データを保持する記憶領域と、を有するデータ供給装置を有するキャッシュ装置のキャッシュ方法であって、
外部より受信するデータを前記記憶領域の一部である受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域をキャッシュ領域として割り当て、前記出力手段は前記フェッチ手段によってキャッシュ領域として割り当てられた領域のデータを出力することを特徴とするキャッシュ方法。
【請求項１７】
出力手段と、前記出力手段が要求する前に前記出力手段に送信すべきデータを要求するプリフェッチ手段と、データを保持する記憶領域と、を有するデータ供給装置に以下の手順を動作させるプログラムであって、
外部より受信するデータを前記記憶領域の一部である受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として割り当て、前記出力手段は前記フェッチ手段によって送信領域として割り当てられた領域のデータを出力することを特徴とするプログラム。
【請求項１】
出力手段と、データを保持する記憶領域を備え前記出力手段に当該記憶領域のデータを供給するフェッチ手段と、前記出力手段がデータを要求する前に前記出力手段に送信すべきデータを外部に要求するプリフェッチ手段と、を有するデータ供給装置であって、
前記フェッチ手段は、外部より受信するデータを前記記憶領域の一部である受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として割り当て、前記出力手段は前記フェッチ手段によって送信領域として割り当てられた領域のデータを出力することを特徴とするデータ供給装置。
【請求項２】
前記フェッチ手段は、前記記憶領域の一部を前記受信領域として割り当て、外部より供給されるデータを当該受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として再び割り当てることを特徴とする請求項１に記載のデータ供給装置。
【請求項３】
複数のステージを有するパイプライン手段を更に有し、前記フェッチ手段は前記複数のステージのうちの１つにデータを供給し、前記プリフェッチ手段は前記フェッチ手段がデータを供給するステージに先行するステージの動作に応じてデータを要求することを特徴とする請求項１又は２に記載のデータ供給装置。
【請求項４】
前記プリフェッチ手段で要求されたデータが前記フェッチ手段に届いたときに前記受信領域を管理する管理情報を更新することを特徴とする請求項１乃至３のいずれか１項に記載のデータ供給装置。
【請求項５】
前記記憶領域に対する前記受信領域の容量を変更することを特徴とする請求項１乃至４のいずれか１項に記載のデータ供給装置。
【請求項６】
前記受信領域の管理情報に基づいて前記プリフェッチ手段のデータ要求を停止することを特徴とする請求項４に記載のデータ供給装置。
【請求項７】
前記受信領域の管理情報に基づいて前記フェッチ手段からのデータ供給を待機することを特徴とする請求項４又は６に記載のデータ供給装置。
【請求項８】
前記プリフェッチ手段と前記フェッチ手段との間に中間待ち行列を備えることを特徴とする請求項１乃至７のいずれか１項に記載のデータ供給装置。
【請求項９】
請求項１乃至８のいずれか１項に記載のデータ供給装置と、キャッシュ判定手段とを備え、前記フェッチ手段の前記記憶領域に前記キャッシュ判定手段に対応するキャッシュデータを格納することを特徴とするキャッシュ装置。
【請求項１０】
ラウンドロビン方式のリプレイス手法を用いることを特徴とする請求項９に記載のキャッシュ装置。
【請求項１１】
連想（ライン選択）方式がフルアソシアティブ方式であることを特徴とする請求項９に記載のキャッシュ装置。
【請求項１２】
連想（ライン選択）方式がセットアソシアティブ方式であることを特徴とする請求項９に記載のキャッシュ装置。
【請求項１３】
連想（ライン選択）方式がダイレクトマップ方式であることを特徴とする請求項９に記載のキャッシュ装置。
【請求項１４】
前記フェッチ手段は前記受信領域を示す受信ポインタと前記送信領域を示すデータポインタとを管理し、当該受信ポインタ又はデータポインタを更新することによって、前記受信領域又は前記送信領域の割り当てを変更することを特徴とする請求項１乃至８のいずれか１項に記載のデータ供給装置。
【請求項１５】
出力手段と、前記出力手段が要求する前に前記出力手段に送信すべきデータを要求するプリフェッチ手段と、データを保持する記憶領域と、を有するデータ供給装置によるデータ供給方法であって、
外部より受信するデータを前記記憶領域の一部である受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として割り当て、前記出力手段は前記フェッチ手段によって送信領域として割り当てられた領域のデータを出力することを特徴とするデータ供給方法。
【請求項１６】
出力手段と、前記出力手段が要求する前にキャッシュ判定により前記出力手段に送信すべきデータを要求するプリフェッチ手段と、データを保持する記憶領域と、を有するデータ供給装置を有するキャッシュ装置のキャッシュ方法であって、
外部より受信するデータを前記記憶領域の一部である受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域をキャッシュ領域として割り当て、前記出力手段は前記フェッチ手段によってキャッシュ領域として割り当てられた領域のデータを出力することを特徴とするキャッシュ方法。
【請求項１７】
出力手段と、前記出力手段が要求する前に前記出力手段に送信すべきデータを要求するプリフェッチ手段と、データを保持する記憶領域と、を有するデータ供給装置に以下の手順を動作させるプログラムであって、
外部より受信するデータを前記記憶領域の一部である受信領域に格納し、前記プリフェッチ手段の要求に応じて当該要求に対応するデータを保持している受信領域を送信領域として割り当て、前記出力手段は前記フェッチ手段によって送信領域として割り当てられた領域のデータを出力することを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−２４３０２６（Ｐ２０１２−２４３０２６Ａ）
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願番号】特願２０１１−１１１５８５（Ｐ２０１１−１１１５８５）
【出願日】平成２３年５月１８日（２０１１．５．１８）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願日】平成２３年５月１８日（２０１１．５．１８）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]