(57)【特許請求の範囲】
【請求項１】
コンピュータシステムにおいて、主記憶装置内に格納されプロセッサによって使用されるデータをバッファリングする方法であって、
（ａ）前記主記憶装置からデータ・ラインを第１のキャッシュに転送するステップであって、
（ａ１）該転送されたデータ・ラインのそれぞれを、該データ・ラインが該第１のキャッシュの外に移動させられる時の該データ・ラインの行先を示す値が設定された標示と共に、該第１のキャッシュに格納するステップを含み、該格納時に設定された標示の値に従い、該データ・ラインが該第１のキャッシュの外に移動させられるとき、第２のキャッシュに転送されるか、または前記主記憶装置に戻されるかが決められる、ステップと、
（ｂ）第１のデータ・ラインが前記第１のキャッシュの外に移動させられ、かつ、該第１のデータ・ラインの該第１のキャッシュへの格納時に設定された前記標示の値が、前記第２のキャッシュに転送されることを示すとき、該第１のデータ・ラインを該第２のキャッシュに移動するステップと、
（ｃ）第２のデータ・ラインが前記第２のキャッシュの外に移動させられ、かつ該第２のデータ・ラインが汚染されているとき、該第２のデータ・ラインを前記主記憶装置に戻すステップと、
（ｄ）前記プロセッサが第３のデータ・ラインに対するアクセスを要求したとき、前記第１のキャッシュおよび前記第２のキャッシュを、該第３のデータ・ラインを求めて並行に検索するステップと、を含む、
データをバッファリングする方法。
【請求項２】
前記ステップ（ｄ）は、
（ｄ．１）前記第２のキャッシュに対する索引を生成するステップと、
（ｄ．２）前記索引を使用して、前記第２のキャッシュ内の第４のデータ・ラインにアクセスするステップと、
（ｄ．３）前記第４のデータ・ラインのタグと、前記第３のデータ・ラインのタグとを比較し、該第４のデータ・ラインが該第３のデータ・ラインであるかどうかを判断するステップと、
（ｄ．４）前記第１のキャッシュに格納されたすべてのデータ・ラインのタグをチェックし、該第１のキャッシュにおけるデータ・ラインのいずれかが該第３のデータ・ラインかどうかを判断するステップと、をさらに含み、
前記ステップ（ｄ．４）は、前記ステップ（ｄ．１）から（ｄ．３）の実行に並行して実行される、請求項１に記載のデータをバッファリングする方法。
【請求項３】
前記第１のキャッシュ内のデータ・ラインは、先入れ先出しで管理され、前記ステップ（ｂ）において、前記第１のデータ・ラインが該第１のキャッシュの外に移動させられる時、該第１のデータ・ラインは、該第１のキャッシュの他のいずれのデータ・ラインよりも長く該第１のキャッシュにいたようにする、請求項１に記載のデータをバッファリングする方法。
【請求項４】
前記ステップ（ｂ）は、
（ｂ．１）前記第１のキャッシュが、予め決められた数のデータ・ラインよりも多くのデータ・ラインを含んでいるとき、前記第１のデータ・ラインと一緒に、該第１のキャッシュから追加のデータ・ラインを移動させるステップをさらに含む、請求項１に記載のデータをバッファリングする方法。
【請求項５】
前記ステップ（ｂ．１）において、前記追加のデータ・ラインが、前記第２のキャッシュにおいて、前記第１のデータ・ラインと同じ場所にマッピングされるとき、前記第１のデータ・ラインおよび前記追加のデータ・ラインのうちの１つを前記主記憶装置に移動させる、請求項４に記載のデータをバッファリングする方法。
【請求項６】
さらに、（ｅ）前記ステップ（ｄ）において、前記第３のデータ・ラインが前記第１のキャッシュにも第２のキャッシュにも存在しないとき、前記主記憶装置から該第３のデータ・ラインを該第１のキャッシュに転送するステップをさらに含み、該ステップ（ｅ）は、
（ｉ）前記第１のキャッシュにおいて、前記第３のデータ・ラインに参照済みとして印付けするステップと、
（ｉｉ）前記主記憶装置から前記第１のキャッシュに第４のデータ・ラインを先取りするステップと、
（ｉｉｉ）前記第１のキャッシュにおいて、前記第４のデータ・ラインに未参照として印付けするステップと、
をさらに含む、請求項１に記載のデータをバッファリングする方法。
【請求項７】
前記ステップ（ｅ）は、
（ｉｖ）第４のデータ・ラインに対するアクセスを前記プロセッサが要求したとき、
前記第１のキャッシュにおいて、前記第４のデータ・ラインに参照済みとして印付けするステップと、
前記主記憶装置から前記第１のキャッシュに第５のデータ・ラインを先取りするステップと、
前記第１のキャッシュにおいて、前記第５のデータ・ラインに未参照として印付けするステップと、
をさらに含む、請求項６に記載のデータをバッファリングする方法。
【請求項８】
主記憶装置に格納されプロセッサによって使用されるデータをバッファリングするキャッシュシステムであって、
データ・ラインを格納するデータ・ライン記憶装置を有する第１のキャッシュであって、該データ・ライン記憶装置に格納されるそれぞれのデータ・ラインと共に、該データ・ラインが該第１のキャッシュの外に移動されるときの該データ・ラインの行先を示す値が設定された標示を、該データ・ライン記憶装置に格納する手段をさらに有する、第１のキャッシュと、
第２のキャッシュと、
前記第１のキャッシュおよび前記主記憶装置に接続され、該主記憶装置から該第１のキャッシュにデータ・ラインを転送する第１の転送手段と、
前記第１のキャッシュ、前記第２のキャッシュおよび前記主記憶装置に接続され、該第１のキャッシュから該第２のキャッシュにデータ・ラインを転送し、および該第１のキャッシュから該主記憶装置にデータ・ラインを転送する第２の転送手段であって、該第１のキャッシュから移動される第１のデータ・ラインの行先は、前記第１のキャッシュの前記データ・ライン記憶装置に格納された時に該第１のデータ・ラインについて設定された前記標示の値に従って決まる、第２の転送手段と、
前記第２のキャッシュおよび前記主記憶装置に接続され、該第２のキャッシュから該主記憶装置にデータ・ラインを転送する第３の転送手段と、
前記第１のキャッシュおよび前記第２のキャッシュに並行にアクセスするアクセス手段と、を備える、
キャッシュシステム。
【請求項９】
前記アクセス手段は、
前記第２のキャッシュに接続され、該第２のキャッシュに対する索引を生成する索引生成手段と、
前記第２のキャッシュに接続され、前記索引生成手段によって生成された索引がアクセスするデータ・ラインのタグと、所望のデータ・ラインのタグとを比較する比較手段と、
前記第１のキャッシュに接続され、該第１のキャッシュのデータ・ラインのいずれかが前記所望のデータ・ラインかどうかを判断する連想型比較手段と、
をさらに備える、請求項８に記載のキャッシュシステム・
【請求項１０】
前記データ・ライン記憶装置は、先入れ先出しメモリである、請求項８に記載のキャッシュシステム。
【請求項１１】
前記第１のキャッシュが、予め決められた数のデータ・ラインよりも多くのデータ・ラインを含むとき、前記第２の転送手段は、前記第１のキャッシュの外に一度に２個のデータ・ラインを移動させる、請求項８に記載のキャッシュシステム。
【請求項１２】
前記第２の転送手段が、前記第２のキャッシュにおける同じ場所にマッピングされる２個のデータ・ラインを前記第１のキャッシュの外に移動させるとき、該第２の転送手段は、該２個のデータ・ラインのうちの１つを前記主記憶装置に移動させる、請求項１１に記載のキャッシュシステム。
【請求項１３】
主記憶装置に格納されプロセッサによって使用されるデータをバッファリングするキャッシュシステムであって、
完全連想型の第１のキャッシュと、
直接マッピング型の第２のキャッシュと、
前記第１のキャッシュおよび前記主記憶装置に接続され、該主記憶装置から該第１のキャッシュにデータ・ラインを転送する第１の転送手段と、
前記データ・ラインのそれぞれと共に、該データ・ラインが前記第１のキャッシュの外に移動されるときの該データ・ラインの行先を示す値が設定された標示を、前記第１のキャッシュに格納する格納手段であって、該データ・ラインが前記第１のキャッシュの外に移動されるとき、該格納時に設定された標示の値に従い、該データ・ラインが前記第２のキャッシュに転送されるのか、または前記主記憶装置に戻されるのかが決められる、格納手段と、
前記第１のキャッシュ、前記第２のキャッシュおよび前記主記憶装置に接続され、該第１のキャッシュから該第２のキャッシュにデータ・ラインを転送する第２の転送手段と、
前記第２のキャッシュおよび前記主記憶装置に接続され、該第２のキャッシュから該主記憶装置にデータ・ラインを転送する第３の転送手段と、
前記第１のキャッシュおよび前記第２のキャッシュに並行にアクセスするアクセス手段と、
を備えるキャッシュシステム。
【請求項１４】
前記アクセス手段は、
前記第２のキャッシュに接続され、該第２のキャッシュに対する索引を生成する索引生成手段と、
前記第２のキャッシュに接続され、前記索引生成手段によって生成された索引がアクセスするデータ・ラインのタグと、所望のデータ・ラインのタグを比較する比較手段と、
前記第１のキャッシュに接続され、該第１のキャッシュにおけるデータ・ラインのいずれかが前記所望のデータ・ラインであるかどうかを判断する連想型比較手段と、
をさらに備える、請求項１３に記載のキャッシュシステム。
【請求項１５】
前記第１のキャッシュは、
データ・ラインを格納するデータ・ライン記憶装置と、
前記データ・ライン記憶装置に格納されたデータ・ラインのタグを格納する内容参照可能メモリと、
をさらに備える、請求項１３に記載のキャッシュシステム。
【請求項１６】
前記データ・ライン記憶装置は、先入れ先出しメモリである、請求項１５に記載のキャッシュシステム。
【請求項１７】
前記第２の転送手段は、前記第１のキャッシュが予め決められた数のデータ・ラインよりも多くのデータ・ラインを含む時、該第１のキャッシュから、複数のデータ・ラインを一度に移動させる、請求項１３に記載のキャッシュシステム。
【請求項１８】
前記第２の転送手段が、前記第１のキャッシュから、前記第２のキャッシュの同じ場所にマッピングされる２個のデータ・ラインを移動させる時、該第２の転送手段は、該２個のデータ・ラインのうちの１つを前記主記憶装置に移動させる、請求項１７に記載のキャッシュシステム。
【請求項１９】
前記第１のキャッシュは、データ・ライン記憶装置に格納されるそれぞれのデータ・ラインと共に、該データ・ラインが参照されたかどうかを示す標示を格納する格納手段をさらに備える、請求項１３に記載のキャッシュシステム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、多重レベル・キャッシュ装置におけるキャッシュ・ミスに起因する時間ペナルティを低減させるためのキャッシュ・ミスによる時間ペナルティ減少方法に係わる。
【０００２】
【従来の技術】
現在のコンピュータ装置の殆どは、中央処理装置（以下、ＣＰＵという）と主記憶装置とを含む。ＣＰＵが命令とオペランドとを復号し実行することが可能な速度は、命令とオペランドとが主記憶装置からＣＰＵに転送される上で可能な転送速度によって決まる。主記憶装置から命令とオペランドとをＣＰＵが受け取るために要する時間を減少させるために、コンピュータ装置の多くは、ＣＰＵと主記憶装置との間にキャッシュ・メモリを含む。
【０００３】
キャッシュ・メモリは、ＣＰＵによって近い将来に使用されると推測される主記憶装置内の内容の一部分を一時的に保持するために使用される小型の高速バッファ記憶装置である。キャッシュ・メモリの主要な目的は、データ又は命令の取り出しのためのメモリ・アクセスを行うのに要する時間を短縮することである。キャッシュ・メモリ内に存在する情報に対するアクセスに要する時間は、主記憶装置内に存在する情報に対するアクセスに要する時間よりも遥かに短い。従って、キャッシュ・メモリを有するＣＰＵでは、命令とオペランドとの取出し及び／又は格納における待ち時間は著しく短くて済む。
【０００４】
キャッシュ・メモリは、１ワード以上のデータを含む多数のブロックによって構成される。各ブロックは、そのブロックが主記憶装置のどのブロックのコピーであるかを一意的に同定するアドレス・タグに対応付けられる。プロセッサがメモリ参照を行う度に、要求されたデータのコピーがキャッシュ・メモリ内に存在するかどうかを調べるためにアドレス・タグ比較が行われる。要求されたメモリ・ブロックがキャッシュ・メモリ内に存在しない場合には、その要求されたブロックが主記憶装置から検索され、キャッシュ・メモリ内に格納され、プロセッサに供給される。
【０００５】
主記憶装置からデータを検索するためにキャッシュ・メモリを使用することに加えて、ＣＰＵは、主記憶装置にデータを直接書き込む代わりにキャッシュ・メモリ内にデータを書き込むことも可能である。プロセッサがキャッシュ・メモリにデータを書き込むことを必要とする時には、キャッシュ・メモリは、データがその中に書き込まれるべきデータ・ブロックがキャッシュ・メモリ内に存在するかどうかを調べるために、アドレス・タグの比較を行う。データ・ブロックが存在する場合には、データがキャッシュ・メモリ内のそのデータ・ブロック内に書き込まれる。多くの装置の場合には、その後で、そのデータ・ブロックのためのデータ「汚染ビット（ｄｉｒｔｙ  ｂｉｔ）  」が設定される。このダーティ・ビットは、当該データ・ブロック内のデータが汚染されている（即ち、変更されている）ということを示し、従って、当該データ・ブロックがキャッシュ・メモリから削除される前に、その変更されたデータが主記憶装置内に書き込まれなければならない。データがその中に書き込まれるはずのデータ・ブロックがキャッシュ・メモリ内に存在しない時には、そのデータブロックがキャッシュ・メモリ内に移動させられるか、データが主記憶装置内に直接書き込まれなければならない。新たなデータがキャッシュ・メモリ内に入れられる時に重ね書きされるか又はキャッシュ・メモリからコピーされて移動させられるデータ・ブロックは、犠牲ブロック又は犠牲ラインと呼ばれる。
【０００６】
応用例によっては、第２のキャッシュ・メモリが、第１のキャッシュ・メモリと主記憶装置との間に直列に付加される場合もある。第１のキャッシュ・メモリは、典型的には、第２のキャッシュ・メモリ内のデータの部分セットを有する。同様に、第２のキャッシュ・メモリは、典型的には、主記憶装置内のデータの部分セットを有する。アクセスされるデータは、最初に、第１のキャッシュ・メモリ内で探索される。第１のキャッシュ・メモリ内でミスがある場合には、そのアクセスされたデータが第２のキャッシュ・メモリ内で探索される。第２のキャッシュ・メモリ（以下、キャッシュ・メモリを単に「キャッシュ」という）内でミスがある場合には、そのアクセスされたデータが主記憶装置の外に移動させられる。
【０００７】
プロセッサ装置用の２レベル・キャッシュの一例では、第１レベルのキャッシュが第２レベルのキャッシュの適正な部分セットである。この「適正な部分セット」という術語は、第１レベルのキャッシュ内の全項目が第２レベルのキャッシュ内にも存在するということを意味する。第２レベルのキャッシュは、第１レベルのキャッシュ内に存在しない追加の項目を含む。第１レベルのキャッシュは第２レベルのキャッシュよりも容量が小さく、且つ第２レベルのキャッシュよりもプロセッサに近い位置にある。第１レベルのキャッシュは、第２レベル・キャッシュよりも容量が小さく、且つ第２レベル・キャッシュよりもプロセッサに近い位置にあり、更には、その対応する第２レベルのキャッシュ又は記憶装置のアクセス待ち時間よりも短いアクセス待ち時間を有するので、一般的に性能の改善をもたらすことが可能である。
【０００８】
通常の動作では、何らかのメモリ参照を実現するためには、幾つかの異なった動作が必要である。メモリ参照は一般的にロード命令又は格納命令である。先ず最初に、最も単純で最も高速度の形で、メモリ参照が第１レベル・キャッシュ内でヒットすることが可能である。「ヒット（ｈｉｔ）  」とは、「チェックされているキャッシュ（第１レベル又は第２レベル）内に、所期メモリ・アドレスのためのデータが存在する場合」と定義される。「ミス」とは、「チェックされているキャッシュ（第１レベル又は第２レベル）内に、所期メモリ・アドレスのためのデータが存在しない場合」と定義される。第１レベル・キャッシュでヒットがあった時には、サイクル・ペナルティはゼロであり、メモリ参照は処理ペナルティなしに完了する。
【０００９】
その次に最高速度の場合は、第２レベルのキャッシュ内でヒットが生じる第１レベルのキャッシュ・ミスである。これは、第２レベルのキャッシュから適切な１６ビット量で単一の第１レベルのキャッシュを満たすために一連の動作シーケンスが行われることを引き起こす。その後で、データがプロセッサに送られるか、格納が完了する。これは、中速度の動作であり、プロセッサは、メモリ参照が完了されるのを待つ間、停止されられる。
【００１０】
最低速度の動作は、メモリ参照が第１レベルのキャッシュと第２レベルのキャッシュの両方をミスする場合である。この例では、主記憶装置から戻り、第２レベルのキャッシュの中に当該ラインを移動させるために、長い一連の動作シーケンスが開始させられる。このデータが記憶装置から第２レベルのキャッシュにコピーされる時には、第１レベルのキャッシュが再び参照され、この時には、第２レベルのキャッシュ内でヒットする第１レベルのキャッシュ・ミスによる。これは、第２レベルのキャッシュ・ラインの当該部分が第１レベル・キャッシュ内に書き込まれると、その後で、要求されたデータがプロセッサに供給されるか、格納が完了される。
【００１１】
典型的には、キャッシュ・メモリは直接マッピング型である。即ち、キャッシュ内の１つ以上の項目にアクセスするために索引が使用される。この場合、マッチングが生じるかどうかを判定するために、その項目のためのタグが、アドレスのタグ部分と比較される。
【００１２】
多方向セット連想キャッシュの場合には、複数のデータ・ランダム・アクセス・メモリ（以下、ＲＡＭという）に同時にアクセスするために、単一の索引が使用される。データＲＡＭは、１つ以上の物理ＲＡＭ集積回路によって実現されることが可能である。１つのセットは、単一のキャッシュ索引によってアドレス指定されるライン全ての集まりである。単一のキャッシュ索引によってアドレス指定されるデータＲＡＭの数は、キャッシュの方向数を表す。例えば、１つのキャッシュにおいて２つのデータＲＡＭからデータをアクセスするために単一のキャッシュ索引が使用される場合には、そのキャッシュは２方向セット連想キャッシュである。同様に、１つのキャッシュにおいて４つのデータＲＡＭからデータをアクセスするために単一のキャッシュ索引が使用される場合には、そのキャッシュは４方向セット連想キャッシュである。
【００１３】
多方向アクセスが行われる場合には、各データＲＡＭ毎にタグ比較が行われる。タグ比較が所期のデータ・ブロックが特定のデータＲＡＭ内に存在することを示す時には、その特定のデータＲＡＭからのデータに基づいて／によって、その動作が行われる。
【００１４】
完全連想キャッシュの場合には、索引は使用されない。完全連想キャッシュに対してアクセスが行われる時には、完全連想キャッシュ内の各キャッシュ・ラインに対してタグ比較が行われる。所期データ・ラインがそのキャッシュ内に存在することをタグ比較が示す時には、その特定のデータ・ラインからのデータに基づいて／によって、その動作が行われる。
【００１５】
キャッシュ装置の全般的な説明に関しては、例えばＤａｖｉｄ  Ａ．  Ｐａｔｔｅｒｓｏｎ，  Ｊｏｈｎ  Ｌ．  Ｈｅｎｎｅｓｓｙ，  Ｃｏｍｐｕｔｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ  Ａ  Ｑｕａｔｉｔａｔｉｖｅ  Ａｐｐｒｏａｃｈ，  Ｍｏｒｇａｎ  Ｋａｕｆｆｍａｎ  Ｐｕｂｌｉｓｈｅｒｓ，  Ｉｎｃ．，  Ｓａｎ  Ｍａｅｔｏ，  Ｃａｌｉｆｏｒｎｉａ，１９９０（１９９０年、カリフォルニア州、サン・メイト、「モルガン・カフマン出版株式会社」発行、「ダビッド・エイ・パターソン」、「ジョン・エル・ヘネシイ」共著、「容量処理方法に関するコンピュータ構造」）のページ４０４〜４２３、ページ４５４〜４６４を参照されたい。
【００１６】
【発明が解決しようとする課題】
従来技術の装置の１つでは、完全連想犠牲キャッシュが、より大容量の直接マッピング・キャッシュから犠牲ラインを受け取る。直接マッピング・キャッシュ内でミスがある時には、完全連想犠牲キャッシュが、完全連想キャッシュ内に発見される場合が時としてある。Ｎｏｒｍａｎ  Ｐ．  Ｊｏｕｐｐｉ，  Ｉｍｐｒｏｖｉｎｇ  Ｄｉｒｅｃｔ−Ｍａｐｐｅｄ  Ｃａｃｈｅ  Ｐｅｒｆｏｒｍａｎｃｅ  ｂｙ  ｔｈｅ  Ａｄｄｉｔｉｏｎ  ｏｆ  ａ  Ｓｍａｌｌ  Ｆｕｌｌｙ−Ａｓｓｏｃｉａｔｉｖｅ  Ｃａｃｈｅ  ａｎｄ  Ｐｒｅｆｅｔｃｈ  Ｂｕｆｆｅｒｓ，  Ｐｒｏｃｅｅｄｉｎｇｓ１７ｔｈ  ＩＳＣＡ，Ｍａｙ  １９９０｛１９９０年５月、第１７回議事録の「ノーマン・ピィ・ジュピィ」による「小容量完全連想キャッシュと、先取りバッファの追加による改善直線マッピング・キャツシュ性能」のページ３６４〜３７３ｓｅａｔｔｌｅ，ＷＡ（シアトル，ダフリュウ・エイ）｝を参照されたい。
【００１７】
【課題を解決するための手段】
本発明の好適な実施例では、キャッシュ装置が、主記憶装置内に格納されプロセッサによって使用されるデータをバッファリングする。このキャッシュ装置は、第１のキャッシュと、第２のキャッシュと、第１の転送手段と、第２の転送手段と、第３の転送手段と、アクセス手段とを含む。第１のキャッシュは完全連想型である。第２のキャッシュは直接マッピング型である。第１の転送手段は、主記憶装置から第１のキャッシュにデータ・ラインを転送する。第２の転送手段は、第１のキャッシュから第２のキャッシュにデータ・ラインを転送する。第３の転送手段は第２のキャッシュから主記憶装置にデータ・ラインを転送する。第１のキャッシュからデータ・ラインのアクセスと、第２のキャッシュからのデータ・ラインのアクセスとが、並行して行われる。
【００１８】
本発明の好適な実施例では、第２のキャッシュ内に索引を生成するためにハッシュ関数が使用される。その索引によってアクセスされるデータ・ラインのためのタグが、第２のキャッシュ内でヒットがあったかどうかを判定するために、所期データ・ラインのためのタグと比較される。
【００１９】
第１のキャッシュに対するデータ・アクセス１回毎に、ヒットがあるかどうかを判定するために、第１のキャッシュ内の全データ・ラインのためのタグがチェックされる。内容参照可能メモリが第１のキャッシュのためのタグを記憶する。データ・ラインが、先入れ先出し（以下、ＦＩＦＯという）記憶装置の形の第１のキャッシュによって格納される。
【００２０】
更に、この好適な実施例では、データ・ラインが第１のキャッシュの外に移動させられる時のデータ・ラインのための行先を示す表示が、第１のキャッシュ内の各データ・ラインと共に格納される。この表示は、データ・ラインが第２のキャッシュ・ラインに移動させられるのか又は主記憶装置に移動させられるかを表示する。
【００２１】
更に、この好ましい実施例では、データが第１のキャッシュ内に先取りされるためのメモリ空間を与えるために、予め決められた数より多くのデータ・ラインを第１のキャッシュが含む時に、データ・ラインが１度に２つずつ第１のキャッシュの外に移動させられる。これら２つのデータ・ラインが第２のキャッシュ内の同一の記憶場所にマッピングされる時には、これら２つのデータ・ラインのどちらか一方が主記憶装置に移動させられる。
【００２２】
例えば、特定のタイプのデータ・アクセスの場合には、プロセッサは、キャッシュ・ミスがある場合に使用されることになっている、又は、「ヒット」データ・ラインのための参照ビットがゼロにセットされる、第１のキャッシュ内のデータ・ライン上でヒットがある場合に使用されることになっている、先取りアドレスを生成する。先取りアドレスのためのデータ・ラインが既に第１と第２のキャッシュ内に存在する時には、更に動作を行う必要はない。先取りアドレスのためのデータ・ラインが既に第１と第２のキャッシュ内に存在しない時には、先取りアドレスのためのデータ・ラインが先取りされる。先取りデータ・ラインのための参照ビットがクリアされ（即ち、ゼロにセットされ）、先取りデータ・ラインが参照されなかったことを表示する。「未参照（ｕｎｒｅｆｅｒｅｎｃｅｄ）」という印を付けられている第１のキャッシュ内のデータ・ラインにおいてキャッシュ・ヒットがある場合には、参照ビットが、そのデータ・ラインの参照が現時点で完了したということを表示する「１」にセットされる。この好適な実施例では、「未参照」という印を付けられている第１のキャッシュ内のデータ・ライン上においてキャッシュ・ヒットがあり、かつ先取りアドレスが生成され終わっている時には、その先取りアドレスのためのデータ・ラインがキャッシュの一方の中に存在しない場合に、その先取りアドレスのためのデータ・ラインが主記憶装置から先取りされ、第１のキャッシュの中に入れられる。先取りデータ・ラインのための参照ビットがクリアされ、先取りデータ・ラインが参照されなかったことを表示する。
【００２３】
本発明の好適な実施例は、最少量のハードウェアの追加だけによって、直接マッピング型キャッシュに典型的に関連したスラッシング挙動を取り除く。
【００２４】
【実施例】
図１は、コンピュータ装置の単純化したブロック線図である。プロセッサ１２と主記憶装置１１とがバス１０に接続された形で示されている。プロセッサ１２は、命令キャッシュ１３とデータ・キャッシュ１４とを使用する。命令キャッシュ１３は、プロセッサ１２用の命令をスタティック・ランダム・アクセス記憶装置（以下、ＳＲＡＭという）内に格納する。データ・キャッシュ１４は、プロセッサ１２用のデータをＳＲＡＭ内に格納する。
【００２５】
図２は、プロセッサ１２の単純化したブロック線図を示す。プロセッサ１２は、バス・インターフェース論理回路２６と、命令キャッシュ・インターフェース論理回路２４と、データ・キャッシュ論理回路２５と、論理演算装置（ＡＬＵ）２２と、アドレス変換バッファ（以下、ＴＬＢという）２１と、補助キャッシュ２３とを含む形で示されている。装置のバス・インターフェース論理回路２６は、装置のバス１０に対するインターフェースをプロセッサ１２に与える。命令キャッシュ・インターフェース論理回路２４は、命令キャッシュ１３に対するインターフェースをプロセッサ１２に与える。データ・キャッシュ論理回路２５は、データ・キャッシュ１４に対するインターフェースをプロセッサ１２に与える。後で更に詳細に説明するように、補助キャッシュ２３は、論理演算装置２２に対してデータを与えるためにデータ・キャッシュ１４と並列に使用される。アドレス変換バッファ２１は、補助キャッシュ２３内に格納されたデータとデータ・キャッシュ１４内に格納されたデータとに対してアクセスするために使用されるキャッシュ・タグを生成するために、仮想アドレスを実アドレスにマッピングするために使用される。
【００２６】
図３は、データ・キャッシュ装置のための構成を示す。この好適な実施例では、補助キャッシュ２３は、６４個の完全連想３２バイト・キャッシュ・ラインから成る。補助キャッシュ２３は、アドレスの一部分が項目タグ各々と一致させられることを可能にする内容参照可能メモリ（以下、ＣＡＭという）内にタグを格納する。この好適な実施例では、データ・キャッシュ１４は直接マッピングされ、１メガバイトまでのデータ（３２Ｋ３２バイト・キャッシュ・ライン）から成る。
【００２７】
各キャッシュ・アクセス毎に、データ・キャッシュ１４と補助キャッシュ２３との両方が並行してアクセスされる。（図２に示される）ＴＬＢ２１からアクセスされる実アドレスが、アクセスのための補助キャッシュ・アクセス・タグを補助キャッシュ２３内に生成するために使用される。補助キャッシュ・アクセス・タグが、補助キャッシュ２３内のいずれかのデータ・ラインのためのタグと一致する場合には、データ・ライン３６上にヒットが発生させられる。ヒットは、補助キャッシュから「ヒット」データを選択しそのヒット・データをデータ・パス３３上に位置させるように、セレクタ３７に信号を送る。
【００２８】
補助キャッシュ２３へのアクセスと同時に、索引１３が、データ・キャッシュ１４内の単一のデータ・ラインにアクセスするために使用される。この好適な実施例では、その索引は、アクセスされた記憶場所のための仮想アドレスの一部分をハッシュすることによって導き出されたハッシュ値から構成される。データ・キャッシュ１４内の索引を付けられた記憶場所のためのアドレス・タグが、データライン３１上に位置したアクセス記憶場所の実アドレスの一部分と比較される。この比較は、比較論理回路３５によって表される。補助キャッシュ２３又はデータ・キャッシュ１４からのヒットがある場合には、論理回路３４がヒット・データ・ライン３２上にヒット信号を生成する。
【００２９】
補助キャッシュ２３とデータ・キャッシュ１４との両方からのヒットがある場合には、新たなデータ・ラインが主記憶装置１１から先取りされる。データ・ラインは、ＦＩＦＯの順序で補助キャッシュ２３から出し入れされる。主記憶装置１１から要求される全データ・ラインは、補助キャッシュ２３内に移動させられる。データ・ラインが補助キャッシュ２３の外に移動させられることになっている時には、そのデータ・ラインはデータ・キャッシュ１４に入れられるか又は主記憶装置１１に戻される。補助キャッシュ２３からのデータ・ラインをデータ・キャッシュ１４内に移動させるか又は主記憶装置１１に戻すかの決定は、補助キャッシュ２３内のデータ・ラインと共に格納された割り当てビットの値によって決まる。割り当てビットの値は、そのデータ・ラインが補助ビット２３の中に移されることを生じさせた命令と、その命令が、キャッシュ・ヒット副命令欄（ｃａｃｈｅ  ｈｉｔ  ｓｕｂ−ｏｐｅｒａｔｉｏｎ  ｆｉｅｌｄ）  において指定された「非割当て」キャッシュ・ヒットを有したかどうかということに基づいて決定される。例えば、この好適な実施例では、短い変位ロード及び格納と索引付きロード及び格納とが、キャッシュ・ヒット副命令欄を有する。
【００３０】
「非割当て」キャッシュ・ヒットを伴うロード命令又は格納命令がそのキャッシュをミスする場合には、アクセスされたデータ・ラインといずれかの先取りされたデータ・ラインとの両方が補助キャッシュ２３内に入れられ、その割当てビットがクリアされ（即ち、ゼロにセットされ）、「非割当て」を表示する。これに加えて、指定された「非割当て」キャッシュ・ヒットを伴うデータ・アクセスが、参照ビットがクリアされる（下記参照）補助キャッシュ２３内のデータ・ライン上でのヒットに結果し、従って（後で更に詳細に説明するように）先取りを生じさせる場合には、その好ましいデータ・ラインが、補助キャッシュ２３内に入れられ、その割当てビットがクリアされ（即ち、ゼロにセットされ）、「非割当て」を表示する。他の全てのデータ・ラインは補助キャッシュ２３に入れられ、その割当てビットが「１」にセットされ、「割当て」を表示する。
【００３１】
補助キャッシュ２３内のデータ・ラインが置換されることになっている時には、そのデータ・ラインがデータ・キャッシュ１４と（汚染ビットの場合に）主記憶装置１１とのどちらに移されなければならないかを決定するために、割当てビットがチェックされる。そのデータ・ラインのための割当てビットが１にセットされる場合には、そのデータ・ラインはデータ・キャッシュ１４に移される。そのデータ・ラインのための割当てビットが０にセットされる場合には、そのデータ・ラインが汚染されている（即ち、補助キャッシュ内に入れられてから変更が加えられている）ならば、そのデータ・ラインが主記憶装置１１に移される。そのデータ・ラインが汚染されていない場合には、そのデータラインは、主記憶装置１１に再び書き込まれることなしに、廃棄される。
【００３２】
例えば、補助キャッシュ２３内のデータ・ラインは、そのデータが長時間に亙って使用されることが無いと推測され且つそのデータの同一データ・ライン内の他のデータが近い将来に使用されると推測される時に、「非割当て」と印付けされる。キャッシュ・ヒットのための更に別の情報は、「可変的取出しを伴うキャッシュ・メモリと置換スキーマ（Ｃａｃｈｅ  Ｍｅｍｏｒｙ  ｗｉｔｈ  Ｖａｒｉａｂｌｅ  Ｆｅｔｃｈ  ａｎｄ  Ｒｅｐｌａｃｅｍｅｎｔ  Ｓｃｈｅｍｅｓ）」に関してＷｉｌｌｉａｍ  Ｒ．  Ｂｒｙｇ  （ウィリアム・アール・ブリッグ他に対して与えられた米国特許第４，９２８，２３９号に説明されている。データ・キャッシュ１４内のデータ・ラインが置換されることになっている時には、そのデータ・ラインがデータ・キャッシュ１４と主記憶装置１１とのどちらに移動させられなければならないかを決定するために、割当てビットがチェックされる。
【００３３】
データ・ラインをデータ・キャッシュ１４内に移動させる前にデータ・ラインを補助キャッシュ２３内に移動させることが、直接マッピング・キャッシュに典型的に関連したスラッシング挙動を取り除く。例えば、ベクトル計算では、
ｉ＝０〜Ｎの場合に次（１）式のようでる。
【００３４】
【数１】
0003618385.tif 000002
【００３５】
要素Ａ［ｉ］、Ｂ［ｉ］、Ｃ［ｉ］、Ｄ［ｉ］が同一のキャッシュ索引にマッピングされる場合には、直接マッピングされたキャッシュだけが上記計算の各要素に対してスラッシングを与えるだけだろう。これは、このループの８回の反復において３２回のキャッシュミスを生じさせるだろう。しかし、補助キャッシュの場合には、各データラインが、他を移動させずにそのキャッシュシステム内に移される。順次３２ビットデータ要素であると仮定すると、そのループの８回の反復は、最初の４つのキャッシュ・ミスだけしか引き起こさない。より大きなキャッシュでもこのタイプのキャッシュ・スラッシングを低減させることがないということに留意されたい。最新のコンパイラは、スラッシングを低減又は除去するためにデータ構造を再位置合せすることが可能であることが多いが、適正な最適化を可能にするために十分なコンパイル時間情報が、アプリケーションにおいて常に得られることが可能であるわけではない。補助キャッシュ２３は、最小限度のハードウェアしか必要とせずに、コンパイラによる最適化なしにキャッシュ・スラッシングを除去するという点で優れている。
【００３６】
補助キャッシュ２３内の項目は、循環ＦＩＦＯ待ち行列の形に順序付けられる。キャッシュ・ミス又は先取りのために主記憶装置１１から要求される新たなデータラインが、上記待ち行列の最上部に置かれ、古い項目が上記待ち行列の最下部の外に移動させられる。ＦＩＦＯ待ち行列内のデータ・ラインに対する消去又は排除が、待ち行列が循環するにつれて取り除かれるバブル（空白スロット）を生じさせる。３／４満杯ＦＩＦＯ（  ａ  ｔｈｒｅｅ  ｑｕａｔｅｒ  ｆｕｌｌ  ＦＩＦＯ）を維持するための試みが行われる。従って、典型的なミス待ち時間下で隠される可能性がある幾つかのデータ・ラインが、ＦＩＦ０が４８個未満の項目しか含まなくなるまで、ミスの間に補助キャッシュ２３の外に移動させられる。この好適な実施例では、各ミス毎に、待ち時間が、２つのデータ・ラインが補助キャッシュ２３の外に移動させられることを可能にする。
【００３７】
この好適な実施例では、先取りデータ・ライン用のメモリ空間を確保するように補助キャッシュ２３の外にデータ・ラインを移動させるために、追加のマシン・サイクルを必要とせずに補助キャッシュ２３の中に先取りデータのためのメモリ空間を実現にするためには、補助キャッシュ２３が３／４満杯以下であることが最適である。
【００３８】
例えば、この好適な実施例では、後で更に説明するように、データ・ラインが主記憶装置１１から補助キャッシュ２３の中に先取りされることが可能である。補助キャッシュ２３が満杯であり、且つ、補助キャッシュ２３内に格納されなければならない先取りデータ・ラインがある場合には、１つのデータ・ラインが補助キャッシュ２３の外に移動させられる。しかし、補助キャッシュ２３が完全に満杯ではない時には、データ・ラインが移動させられる必要はない。先取りデータのためのメモリ空間を事前に作るために、ミスが発生し且つ補助キャッシュ２３が３／４満杯以上である（即ち、全てのバブルを含むＦＩＦＯの初めと終わりとの間に４８個以上の項目が存在する）時には、２つのデータ・ラインが補助キャッシュ２３の外に移動させられる。
【００３９】
これに加えて、後で更に説明するように、先取りデータがキャッシュ・ミス時に補助キャッシュ２３内に移されることが可能である。例えば、キャッシュ・ミス時に、プロセッサが、その次のデータ・ラインが既に補助キャッシュ２３内に存在するかどうかを確かめるためにチェックを行う。そうでない場合には、プロセッサが、ミスがあるデータ・ラインを先取りし、更には、その次のデータ・ラインを先取りする。
【００４０】
この好ましい実施例では、キャッシュ・ミスが、単一のデータ・ラインが主記憶装置１１から先取りされることを要求し（即ち、第２のデータ・ラインの先取りがなく）、且つ、補助キャッシュ２３が３／４満杯以上である場合には、２つのデータ・ラインが補助キャッシュ２３の外に移動させられる。これらのデータラインはミス待ち時間の間に外に移動させられることが可能であり、一方、プロセッサ１２が機能停止させられ、データが主記憶装置１１から戻されるのを待機する。メモリ空間を作るためにデータ・ラインが外に移動させられる必要がないので、プロセッサが機能停止を回避するが故に、後続の先取りヒットが有利である。
【００４１】
データ・ラインが、次の例外を除いて、ＦＩＦＯ順にデータ・キャッシュに移される。２つのデータ・ラインがミス時に補助キャッシュ２３の外に移動させられ、且つ、これらのデータ・ラインの両方がデータ・キャッシュ１４内の同一の索引にマッピングされる場合には、その第１のデータ・ラインがデータ・キャッシュ１４に移され、第２のデータ・ラインが主記憶装置１１に戻される。
【００４２】
図４は、補助キャッシュ２３の単純化したブロック線図を示す。データ・ラインを格納するためにＳＲＡＭ４３が使用される。ＳＲＡＭ４３内に格納されたデータ・ラインのためのタグを格納するために、ＣＡＭ４１が使用される。ビット・メモリ４２は、様々なキャッシュ制御ビットを格納するために使用される。各データ・ラインと共に格納されるキャッシュ制御ビットは、上記の（カラム４６によって表される）割当てビットと、下記の（カラム４７で表される）参照ビットとを含む。補助キャッシュ２３からの特定のデータ・ラインをデータ・キャッシュ１４と主記憶装置１１のどちらに移動させるかの決定は、その特定のデータ・ラインのための格納された割当てビットの値に依存する。ＦＩＦＯポインタ４４は、ＦＩＦＯメモリとしてのＳＲＡＭの使用を容易にするために、ＳＲＡＭ４３中の最初の項目の位置と最後の項目の位置とを表示する。補助キャッシュがアクセスされ、キャッシュ・ミスがあることをＣＡＭ４１が検出する時に、選択論理回路４５がデータ・パス３３に適正なデータ・ラインを与える。
【００４３】
この好ましい実施例では、データ・キャッシュ１４と補助キャッシュ２３とに対するアクセスがその両方のキャッシュにおけるミスに起因する場合には、プロセッサ１２が主記憶装置１１からの「ミス・データ・ラインを要求する。そのミスデータ・ラインが主記憶装置１１から補助キャッシュ２３内に移動させられる時に、そのデータ・ラインのためのカラム４７内の参照（Ｒ）ビットがセットされ、そのデータ・ラインが参照されたことを表示する。
【００４４】
これに加えて、特定のタイプのデータ・アクセスの場合には、キャッシュ・ミスがある時に使用される、又は、「ヒット」データ・ラインのための参照ビットがゼロにセットされる補助キャッシュ１４内のデータ・ライン上でヒットがある時に使用される先取りアドレスを、プロセッサ１２が生成する。一般的に、プロセッサ１２によって生成される先取りアドレスは、アクセスされたデータ・ラインの次に続くデータ・ラインである。
【００４５】
キャッシュ・ミス時には、先取りアドレスのためのデータ・ラインが既にデータ・キャッシュ１４又は補助キャッシュ２３の内に存在するならば、更に別の動作が行われる必要がない。先取りアドレスのためのデータ・ラインが未だデータ・キャッシュ１４又は補助キャッシュ２３の内に存在しないならば、その先取りアドレスのためのデータ・ラインが先取りされる。先取りされたデータ・ラインが主記憶装置１１から補助キャッシュ２３の中に移される時に、その新たなデータ・ラインのためのカラム４７内の参照（Ｒ）ビットがクリアされ、その先取りデータ・ラインが参照されなかったことを表示する。
【００４６】
この好適な実施例では、「未参照」と印付けされている（即ち、その項目のためのカラム４７内の参照ビットがクリアされている）補助キャッシュ２３内のデータ・ライン上にキャッシュ・ヒットがあり、且つ、プロセッサ１２が先取りアドレスを生成する時に、プロセッサ１２が、そのデータ・ラインのためのカラム４７内の参照ビットをセットし、そのデータ・ラインが現時点で参照済みであるということを表示する。これに加えて、プロセッサ１２は、先取りアドレスのためのデータ・ラインが既にデータ・キャッシュ１４又は補助キャッシュ２３の内に存在するかどうかをチェックする。そうでない場合には、先取りアドレスのためのデータ・ラインが先取りされる。先取りデータ・ラインが主記憶装置１１から補助キャッシュ２３の中に移される時に、その新たなデータ・ラインのためのカラム４７内の参照（Ｒ）ビットがクリアされ、その先取りデータ・ラインが参照されなかったことを表示する。
【００４７】
データ・ラインは、主記憶装置１１からバス１０を経由してプロセッサ１２に転送される。この好適な実施例では、バス１０は６４ビット幅であり、各データ・ラインは２５６ビット幅である。従って、プロセッサ１２に転送されるべき全データ・ライン１つ当たり４つのバス・サイクルが必要である。プロセッサ実行時間に対する影響を最小限にするために、バス１０を経由したデータ転送が完了するまで各データ・ラインがムーブ・イン・バッファ４８内で併合される。そのデータ・ライン全体がムーブ・イン・バッファ４８に転送され終わると、そのデータ・ラインが単一のサイクルでＳＲＡＭ４３内に書き込まれる。従って、補助キャッシュ２３は、より大きい割合の時間に亙ってプロセッサ１２にとって使用可能である。
【００４８】
上記の説明は、本発明の方法の単なる一例と実施例とを開示し説明するものである。当業者には理解されるように、本発明は、本発明の思想又は本質的特徴とから逸脱することなく、他の特定の形態で具体化されることが可能である。従って、本発明のこの開示内容は、特許請求の範囲で請求される本発明の範囲を非限定的に例示するものであることが意図されている。
【００４９】
以上、本発明の各実施例について詳述したが、ここで各実施例の理解を容易にするために、各実施例ごとに要約して以下に列挙する。
【００５０】
１．  コンピュータ装置における、主記憶装置内に格納され、かつプロセッサによって利用されるデータをバッファリングするための方法であって、
（ａ）．データ・ラインを前記主記憶装置から第１のキャッシュに転送する工程であって、前記データ・ラインが前記第１のキャッシュの外に移動させられる時の前記データ・ラインの行先を表示するための表示を前記データ・ライン各々と共に前記第１のキャッシュ内に格納し、前記表示は前記データ・ラインが第２のキャッシュに送られるのかどうか又は前記主記憶装置に戻されるのかどうかを表示する前記工程と、
（ｂ）．第１のデータラインが前記第１のキャッシュの外に移動させられ、かつ前記表示は前記第１のデータ・ラインが前記第２のキャッシュに送られなければならないことを表示する時に、前記第１のデータ・ラインを前記第２のキャッシュに移動させる工程と、
（ｃ）．第２のデータ・ラインが前記第２のキャッシュの外に移動させられ、かつ、汚染されている時に、前記第２のデータ・ラインを前記主記憶装置に戻す工程と、
（ｄ）．前記プロセッサが第３のデータ・ラインに対するアクセスを要求する時に、前記第３のデータ・ラインに対して平行して前記第１のキャッシュと前記第２のキャッシュとを探索する工程と、
を含むキャッシュ・ミスによる時間ペナルティ減少方法である。
【００５１】
２．  前記工程（ｄ）が、
（ｄ．１）．前記第２のキャッシュの中に索引を生成する副次的工程と、
（ｄ．２）．前記第２のキャッシュ内の第４のデータ・ラインにアクセスするために前記索引を使用する副次的工程と、
（ｄ．３）．前記第４のデータ・ラインが前記第３のデータ・ラインであるかどうかを決定するために、前記第４のデータ・ラインのためのタグを前記第３のデータ・ラインのためのタグと比較する副次的工程と、
（ｄ．４）．前記第１のキャッシュ内のデータ・ラインのいずれかが前記第３のデータ・ラインであるかどうかを決定するために、前記第１のキャッシュ内に格納された個々のデータ・ラインのためのタグをチェックする副次的工程と、
を含み、
前記副次的工程（ｄ．４）が前記副次的工程（ｄ．１）から前記副次的工程（ｄ．３）までと共に並行して行われる上記１に記載のキャッシュ・ミスによる時間ペナルティ減少方法である。
【００５２】
３．  前記工程（ｂ）において、前記第１のデータ・ラインが前記第１のキャッシュの外に移動させられる時に前記第１のデータ・ラインが前記第１のキャッシュ内の他のデータ・ラインのいずれよりも長く前記第１のキャッシュ内に存在しているように、前記第１のキャッシュ内のデータ・ラインが先入れ先出しの形で処理される上記１に記載のキャッシュ・ミスによる時間ペナルティ減少方法である。
【００５３】
４．  前記工程（ｂ）が、
所定数よりも多いデータラインを前記第１のキャッシュが含む時に、追加のデータラインを前記第１のデータ・ラインと共に前記第１のキャッシュから移動させる副次的工程を含む上記１に記載のキャッシュ・ミスによる時間ペナルティ減少方法である。
【００５４】
５．  前記工程（ｂ．１）において、上記追加のデータ・ラインは、前記第１のデータ・ラインがマッピングされる前記第２のキャッシュ内の記憶場所と同一の前記第２のキャッシュ内の記憶場所にマッピングされる時に、前記第２のデータ・ラインを前記主記憶装置に移動させる上記４に記載のキャッシュ・ミスによる時間ペナルティ減少方法である。
【００５５】
６．  前記方法が更に、
（ｅ）．前記工程（ｄ）において、前記第３のデータ・ラインが前記第１のキャッシュ内に存在せずかつ前記第２のキャッシュ内に存在しない時に、前記主記憶装置から前記第１のキャッシュに前記第３のデータ・ラインを転送する工程を含み、この工程が更に、
（ｉ）．前記第１のキャッシュ内で、前記第３のデータ・ラインを「参照済」として印付けする副次的工程と、
（ｉｉ）．前記主記憶装置から前記第１のキャッシュに第４のデータ・ラインを先取りする副次的工程と、
（ｉｉｉ）．前記第１のキャッシュ内で、前記第４のデータ・ラインを「未参照」として印付けする副次的工程と、
を含む上記１に記載のキャッシュ・ミスによる時間ペナルティ減少方法である。
【００５６】
７．  前記工程（ｅ）が更に、
（ｉｖ）．前記プロセッサが前記第４のデータ・ラインに対するアクセスを要求する時に、前記第１のキャッシュ内で、前記第４のデータ・ラインを「参照済」として印付けし、前記主記憶装置から前記第１のキャッシュに第５のデータ・ラインを先取りし、前記第１のキャッシュ内で、前記第５のデータ・ラインを「未参照」として印付けする副次的工程と、
を含む上記６に記載のキャッシュ・ミスによる時間ペナルティ減少方法である。
【００５７】
８．  主記憶装置内に格納されプロセッサによって利用されるデータをバッファリングするためにキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュシ装置であって、
データ・ラインを格納するためのデータ・ラインメモリと、前記データ・ライン・メモリ内に格納されたデータ・ラインがその第１のキャッシュの外に移動させられる時に前記データ・ラインの行先を表示する表示を前記データ・ライン各々と共に格納するための格納手段とを含む、第１のキャッシュと、
第２のキャッシュと、
前記主記憶装置から前記第１のキャッシュにデータ・ラインを転送するために、前記第１のキャッシュと前記主記憶装置とに結合した第１の転送手段と、
前記第１のキャッシュの外に移動させられるいずれの第１のデータ・ラインのための行先も前記格納手段内に格納された前記第１のデータ・ラインのための表示の値に依存している、前記第１のキャッシュから前記第２のキャッシュと前記第１のキャッシュから前記主記憶装置とにデータ・ラインを転送するために、前記第１のキャッシュと前記第２のキャッシュと前記主記憶装置とに結合した第２の転送手段と、
前記第２のキャッシュから前記主記憶装置にデータ・ラインを転送するために、前記第２のキャッシュと前記主記憶装置とに結合した第３の転送手段と、
前記第１のキャッシュと前記第２のキャッシュとに対して並行してアクセスするためのアクセス手段と、
を含む前記キャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００５８】
９．  前記アクセス手段が、
前記第２のキャッシュ内に索引を生成するために、前記第２のキャッシュに結合された索引生成手段と、
前記索引生成手段によって生成された索引によってアクセスされたデータ・ラインのためのタグを所期データ・ラインのためのタグと比較するために、前記第２のキャッシュに結合した比較手段と、
前記第１のキャッシュ内のデータ・ラインのいずれかが前記所期データ・ラインであるかどうかを決定するために、前記第１のキャッシュに結合した連想型比較手段と、
を含む上記８に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００５９】
１０．  前記データ・ライン・メモリが先入れ先出し記憶装置である上記８に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６０】
１１．  前記第２の転送手段は、前記第１のキャッシュが予め決められた数より多い数のデータ・ラインを含む時に１度に２つのデータ・ラインを前記第１のキャッシュの外に移動させる上記８に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６１】
１２．  前記第２の転送手段が、前記第２のキャッシュ内の同一の記憶場所にマッピングされた２つのデータ・ラインを前記第１のキャッシュの外に移動させる時に、前記第２の転送手段が前記２つのデータ・ラインのどちらか一方を前記主記憶装置に移動させる上記１１に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６２】
１３．  主記憶装置内に格納され、かつプロセッサによって利用されるデータをバッファリングするためにキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置であって、
完全連想型の第１のキャッシュと、
直接マッピング型の第２のキャッシュと、
前記主記憶装置から前記第１のキャッシュにデータ・ラインを転送するための、前記第１のキャッシュと前記主記憶装置とに結合した第１の転送手段と、
前記第１のキャッシュから前記第２のキャッシュにデータ・ラインを転送するための、前記第２のキャッシュと前記主記憶装置とに結合された第２の転送手段と、
前記第２のキャッシュから前記主記憶装置にデータ・ラインを転送するための、前記第２のキャッシュと前記主記憶装置とに結合した第３の転送手段と、
前記第１のキャッシュと前記第２のキャッシュとに対して並行してアクセスするためのアクセス手段と、
を含むキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６３】
１４．  前記アクセス手段は、
前記第２のキャッシュ内に索引を生成するために、前記第２のキャッシュに結合した索引生成手段と、
前記索引生成手段によって生成された前記索引によってアクセスされるデータ・ラインのためのタグを所期データ・ラインのためのタグと比較するために、前記第２のキャッシュに結合した比較手段と、
前記第１のデータ・キャッシュ内のデータ・ラインのいずれかが前記所期データラインであるかどうかを決定するために、前記第１のキャッシュに結合した連想型比較手段と、
とを含む上記１３に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６４】
１５．  前記第１のキャッシュが、
データ・ラインを格納するためのデータ・ライン・メモリと、
前記データ・ライン・メモリ内に格納されたデータ・ラインのためのタグを格納するための内容参照可能メモリと、
を含む上記１３に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６５】
１６．  前記データ・ラインメモリが先入れ先出しメモリである上記１５に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６６】
１７．  前記第１のキャッシュは更に、前記第１のキャッシュからデータ・ラインを外に移動させる時の前記データ・ラインの行先を表示する表示を前記データ・ラインメモリ内に格納された前記データ・ライン各々と共に格納するための格納手段を含む上記１５に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６７】
１８．  前記第２の転送手段は、前記第１のキャッシュが所定数より多い数のデータ・ラインを含む時に１度に１つ以上のデータ・ラインを前記第１のキャッシュの外に移動させる上記１３に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６８】
１９．  前記第２の転送手段は、前記第２のキャッシュ内の同一の記憶場所にマッピングされた２つのデータ・ラインを前記第１のキャッシュの外に移動させる時に、前記第２の転送手段が前記２つのデータ・ラインのどちらか一方を前記主記憶装置に移動させる上記１８に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００６９】
２０．  前記第１のキャッシュが更に、前記データ・ライン各々が参照済みであることを表示する表示を前記データ・ライン・メモリ内に格納された前記データ・ライン各々と共に格納するための格納手段を含む上記１３に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００７０】
２１．  前記第１の転送手段は更に、第１のデータ・ラインに対する参照の結果として前記第１のキャッシュ内に前記第１のデータ・ラインが入れられる時に前記第１のデータ・ラインを前記第１のキャッシュ内で「参照済」と印付けし、かつ先取りの結果として前記第１のキャッシュ内に第２のデータ・ラインが入れられる時に前記第２のデータ・ラインを前記第１のキャッシュ内で「未参照」として印付けするためのものである上記２０に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００７１】
２２．  前記アクセス手段は更に、前記第２のデータ・ラインが参照される時に前記第２のデータ・ラインを前記第１のキャッシュ内で「参照済」として印付けするためのものである上記２１に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるキャッシュ装置である。
【００７２】
２３．  コンピュータ装置における、主記憶装置内に格納されプロセッサによって利用されるキャッシュ・ミスによる時間ペナルティ減少方法に適用されるデータをバッファリングするための方法であって、
（ａ）．前記主記憶装置から第１のキャッシュにデータ・ラインを転送する工程と、
（ｂ）．第１のデータ・ラインが前記第１のキャッシュの外に移動させられる時に、前記第１のデータ・ラインを第２のキャッシュに移動させる工程と、
（ｃ）．第２のデータ・ラインが前記第２のキャッシュの外に移動させられかつ汚染されている時に、前記第２のデータ・ラインを前記主記憶装置に戻す工程と、
（ｄ）．前記プロセッサが第３のデータ・ラインに対するアクセスを要求する時に、前記第３のデータ・ラインを求めて前記第１のキャッシュと前記第２のキャッシュとに対して並行して探索を行う工程と、
を含むキャッシュ・ミスによる時間ペナルティ減少方法に適用されるデータをバッファリングするための方法である。
【００７３】
２４．  前記工程（ｄ）が更に、
（ｄ．１）．前記第２のキャッシュの中に索引を生成する副次的工程と、
（ｄ．２）．前記第２のキャッシュ内の第４のデータ・ラインにアクセスするために前記索引を使用する副次的工程と、
（ｄ．３）．前記第４のデータ・ラインが前記第３のデータ・ラインであるかどうかを決定するために、前記第４のデータ・ラインのためのタグを前記第３のデータ・ラインのためのタグと比較する副次的工程と、
（ｄ．４）．前記第１のキャッシュ内のデータ・ラインのいずれかが前記第３のデータ・ラインであるかどうかを決定するために、前記第１のキャッシュ内に格納された個々のデータ・ラインのためのタグをチェックする副次的工程と、
を含み、
前記副次的工程（ｄ．４）が前記副次的工程（ｄ．１）から前記副次的工程（ｄ．３）までと共に並行して行われる２３項に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるデータをバッファリングするための方法である。
【００７４】
２５．  前記工程（ｂ）において、前記第１のデータ・ラインが前記第１のキャッシュの外に移動させられる時に前記第１のデータ・ラインが前記第１のキャッシュ内の他のデータ・ラインのいずれよりも長く前記第１のキャッシュ内に存在しているように、前記第１のキャッシュが先入れ先出しの形で処理される上記２３に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるデータをバッファリングするための方法である。
【００７５】
２６．  前記工程（ｂ）が、
所定数よりも多いデータ・ラインを前記第１のキャッシュが含む時に、追加のデータ・ラインを前記第１のデータ・ラインと共に移前記第１のキャッシュから移動させる副次的工程を含む上記２３に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるデータをバッファリングするための方法である。
【００７６】
２７．  前記副次的工程（ｂ．１）は、上記追加のデータ・ラインが、前記第１のデータ・ラインがマッピングされる前記第２のキャッシュ内の記憶場所と同一の前記第２のキャッシュ内の記憶場所にマッピングされる時に、前記第１のデータ・ラインを前記主記憶装置に移動させることを含む上記２６に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるデータをバッファリングするための方法である。
【００７７】
２８．  前記データをバッファリングするための方法が更に、
（ｅ）．前記工程（ｄ）において前記第３のデータ・ラインが前記第１のキャッシュ内に存在せずかつ前記第２のキャッシュ内に存在しない時に、前記主記憶装置から前記第１のキャッシュに前記第３のデータ・ラインを転送する工程を含み、この工程が更に、
（ｉ）．前記第１のキャッシュ内で、前記第３のデータ・ラインを「参照済」として印付けする副次的工程と、
（ｉｉ）．前記主記憶装置から前記第１のキャッシュに第４のデータ・ラインを先取りする副次的工程と、
（ｉｉｉ）．前記第１のキャッシュ内で、前記第４のデータ・ラインを「未参照」として印付けする副次的工程と、
を含む上記２３に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるデータをバッファリングする方法である。
【００７８】
２９．  前記工程（ｅ）が更に、
（ｉｖ）．前記プロセッサが前記第４のデータ・ラインに対するアクセスを要求する時に、前記第１のキャッシュ内で、前記第４のデータ・ラインを「参照済」として印付けし、前記主記憶装置から前記第１のキャッシュに第５のデータラインを先取りし、前記第１のキャッシュ内で、前記第５のデータラインを「未参照」として印付けする副次的工程
を含む上記２８に記載のキャッシュ・ミスによる時間ペナルティ減少方法に適用されるデータをバッファリングする方法である。
【００７９】
【発明の効果】
以上のように、本発明によれば、データ・ラインを主記憶装置から第１のキャッシュの外に移動させる時にデータ・ラインの行先表示をデータ・ラインのそれぞれとともに第１のキャッシュ内に格納し、この表示はデータ・ラインが第２のキャッシュに送られるのか、主記憶装置に戻されるのかを表示し、第１のデータ・ラインを第１のキャッシュの外に移動させる時に第１のデータ・ラインの行先表示が第１のデータ・ラインを第２のキャッシュに送らなければならない表示をしていると、第１のデータ・ラインを第２のキャッシュに移動させ、第２のデータ・ラインが第２のキャッシュの外に移動され、汚染されると第２のデータ・ラインを主記憶装置に戻し、プロセッサが第３のデータ・ラインに対するアクセスを要求すると、第３のデータ・ラインに対して並行して第１と第２のキャッシュを探索するようにしたので、最小量のハードウェアの追加のみで直接マッピング型キャッシュにコンパイラによる最適化なしにキャッシュ・スラッシングを取り除くことができる。
【図面の簡単な説明】
【図１】本発明の好適な実施例による命令キャッシュとデータ・キャッシュとを有するコンピュータ装置の単純化したブロック図である。
【図２】本発明の好適な実施例による図１に示したプロセッサの単純化したブロック図である。
【図３】本発明の好適な実施例による、図１に示したコンピュータ装置のためのキャッシュシ装置の単純化したブロック図である。
【図４】本発明の好適な実施例による、図２に示したプロセッサ内の補助キャッシュの単純化したブロック図である。
【符号の説明】
１０  バス
１１  主記憶装置
１２  プロセッサ
１３  命令キャッシュ
１４  データ・キャッシュ
２１  アドレス変換バッファ
２２  論理演算装置
２３  補助キャッシュ
２４  命令キャッシュ・インターフェース論理回路
２５  データ・キャッシュ・インターフェース論理回路
２６  装置のバス・インターフェース論理回路
３２  ピット・データ・ライン
３３  データ・バス
３４  論理回路
３５  比較論理回路
３６  データ・ライン
３７  セレクタ
４１  内容参照可能メモリ
４２  ビット・メモリ
４３  スタティツク・ランダム・アクセス記憶装置
４４  ＦＩＦＯポインタ
４５  選択論理回路
４６，４７  カラム
４８  ムーブ・イン・バッファ
【図１】
0003618385.tif 000003
【図２】
0003618385.tif 000004
【図３】
0003618385.tif 000005
【図４】
0003618385.tif 000006