(57)【特許請求の範囲】
【請求項１】
複数のプロセッサユニットより共有のリソースへアクセスするために同一サイクルの衝突リクエストを調停（arbitrate）する方法であって、
前記共有のリソースにアクセスし得る好適なプロセッサとなるべく、複数のプロセッサユニットの１つを選択する過程と、
各々の前記複数のプロセッサユニットのために、前記選択過程の結果を基にリトライインジケータを生成する過程とを含み、
ここで前記好適なプロセッサのための前記リトライインジケータは、リトライが必要ないことを示す値を有し、
また、前記複数のプロセッサユニットに含まれる前記残りのプロセッサユニットのための前記リトライインジケータは、リトライが必要であることを示す値を有することを特徴とする方法。
【請求項２】
前記選択過程が、更に、
前記複数のプロセッサユニットに含まれるプロセッサユニットの数であるＰ個のセグメントを含む、繰り返し選択パターンを繰り返し実行する過程を含み、
ここで各々の前記セグメントが、所定の数の連続衝突リクエストのため、前記好適なプロセッサとして前記複数のプロセッサユニットのうち異なる１つを選択することを特徴とする請求項１に記載の方法。
【請求項３】
前記繰り返し選択パターンがプログラム可能に変更され得ることを特徴とする請求項２に記載の方法。
【請求項４】
前記繰り返し選択パターンが、
各々Ｎ回の連続する衝突リクエストに関連する前記サイクルの間、前記共有のリソースにアクセスするために、前記好適なプロセッサとして第１のプロセッサユニットを選択する第１セグメントと、
前記Ｎ回の連続的な衝突リクエストが発生した後に発生する各々Ｍ回の連続する衝突リクエストに関連する前記サイクルの間、前記共有のリソースにアクセスするために、前記好適なプロセッサとして第２のプロセッサユニットを選択する第２のセグメントとを有することを特徴とする請求項２に記載の方法。
【請求項５】
Ｎが２であることを特徴とする請求項４に記載の方法。
【請求項６】
Ｍが２であることを特徴とする請求項４に記載の方法。
【請求項７】
前記生成過程が更に、
各々の前記Ｎ及びＭ回の衝突リクエストのために、前記第１のプロセッサユニットのためには第１のリトライインジケータを、また前記第２のプロセッサユニットのためには第２のリトライインジケータを生成する過程を含み、
ここで前記Ｎ回の衝突リクエストのために生成された各々の前記第２のリトライインジケータは、リトライが必要であることを示す値を含み、
また前記Ｍ回の衝突リクエストのために生成された各々の前記第１のリトライインジケータは、リトライが必要であることを示す値を含むことを特徴とする請求項４に記載の方法。
【請求項８】
前記共有のリソースがデータキャッシュユニットを含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記共有のリソースがフィルバッファ中のデータレジスタを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記共有のリソースがライトバックバッファを含むことを特徴とする請求項１に記載の方法。
【請求項１１】
前記同一サイクルの衝突リクエストが、完了していないロード動作を含むことを特徴とする請求項１に記載の方法。
【請求項１２】
前記同一サイクルの衝突リクエストが、完了していないストア動作を含むことを特徴とする請求項１に記載の方法。
【請求項１３】
前記同一サイクルの衝突リクエストが、少なくとも１つの完了していないストア動作と、少なくとも１つの完了していないロード動作とを含むことを特徴とする請求項１に記載の方法。
【請求項１４】
前記選択過程が、前記好適なプロセッサとしてロード動作をリクエストするプロセッサユニットの選択を含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
複数のプロセッサユニットより共有のリソースにアクセスするため同一サイクルの衝突リクエストを調停する調停回路が、
前記複数のプロセッサユニットの１つを選択し、前記共有のリソースにアクセスし得る好適プロセッサとする調停プロトコル回路と、
各々の前記複数のプロセッサユニットのために、前記選択過程の結果を基にしてリトライインジケータを生成するリトライ信号ジェネレータとを有し、
ここで前記好適なプロセッサのための前記リトライインジケータがリトライが必要ないことを表す値を含み、また前記複数のプロセッサユニットに含まれる前記残りのプロセッサユニットのための前記リトライインジケータはリトライが必要であることを示す値を含むことを特徴とする調停回路。
【請求項１６】
前記調停プロトコル回路が更に、
前記複数のプロセッサユニットに含まれるプロセッサユニットの数であるＰ個のセグメントを有する選択パターンを繰り返して実行する選択ロジックを含み、
ここで各々の前記セグメントが、所定の数の連続衝突リクエストのため、前記好適なプロセッサとして前記複数のプロセッサユニットのうち異なる１つを選択することを特徴とする請求項１５に記載の調停回路。
【請求項１７】
前記選択ロジックがプログラム可能に変更され得ることを特徴とする請求項１６に記載の調停回路。
【請求項１８】
前記選択パターンが、
各々Ｎ回の連続する衝突リクエストに関連する前記サイクルの間、前記共有のリソースにアクセスするために、前記好適なプロセッサとして第１のプロセッサユニットを選択する第１セグメントと、
前記Ｎ回の連続的な衝突リクエストが発生した後に生じる各々Ｍ回の連続衝突リクエストに関連する前記サイクルの間、前記共有のリソースにアクセスするために、前記好適なプロセッサとして第２のプロセッサユニットを選択する第２セグメントとを有することを特徴とする請求項１６に記載の調停回路。
【請求項１９】
Nが２であることを特徴とする請求項１８に記載の調停回路。
【請求項２０】
Mが２であることを特徴とする請求項１８に記載の調停回路。
【請求項２１】
前記リトライ信号ジェネレータが更に、
各々の前記Ｎ及びＭ回の衝突リクエストのために、前記第１のプロセッサユニットのためには第１のリトライインジケータを、また前記第２のプロセッサユニットのためには第２のリトライインジケータを生成する過程を含み、
ここで前記Ｎ回の衝突リクエストのために生成された各々の前記第２のリトライインジケータは、リトライが必要であることを示す値を含み、
また前記Ｍ回の衝突リクエストのために生成された各々の前記第１のリトライインジケータは、リトライが必要であることを示す値を含むことを特徴とする請求項１８に記載の調停回路。
【請求項２２】
前記共有のリソースがデータキャッシュユニットを含むことを特徴とする請求項１５に記載の調停回路。
【請求項２３】
前記共有のリソースがフィルバッファ中のデータレジスタを含むことを特徴とする請求項１５に記載の調停回路。
【請求項２４】
前記共有のリソースがライトバックバッファを含むことを特徴とする請求項１５に記載の調停回路。
【請求項２５】
さらに、前記複数のプロセッサユニットに含まれる各々のプロセッサユニットよりの、少なくとも１つのトランザクション型インジケータをレシーブするべく構成されたトランザクション型インプットを含むことを特徴とする請求項１５に記載の調停回路。
【請求項２６】
前記少なくとも１つのトランザクション型インジケータが、ロードインジケータを含むことを特徴とする請求項２５に記載の調停回路。
【請求項２７】
前記少なくとも１つのトランザクション型インジケータが、ストアインジケータを含むことを特徴とする請求項２５に記載の調停回路。
【請求項２８】
前記トランザクション型インプットが、前記同一サイクルの間、前記複数のプロセッサユニットの１つよりのストアトランザクション型インジケータと、前記複数のプロセッサユニットの別ユニットよりのロードトランザクション型インジケータとの双方をレシーブするべく構成されることを特徴とする請求項２５に記載の調停回路。
【請求項２９】
前記調停プロトコル回路が、前記好適なプロセッサとして、前記ロードトランザクション型インジケータがレシーブされる前記プロセッサユニットを選択することを特徴とする請求項２８に記載の調停回路。
【請求項３０】
コンピュータシステムであって、
複数のプロセッサユニットと、
少なくとも１つの共有のリソースと、
複数のプロセッサユニットより共有のリソースにアクセスするため、同一サイクルの衝突リクエストを調停する調停回路とを含み、
ここで前記調停回路が、前記共有のリソースにアクセスし得る好適なプロセッサとなるべく、前記複数のプロセッサユニットの１つを選択する調停プロトコル回路を有し、更には前記複数のプロセッサユニットに含まれる各々のプロセッサユニットのためのリトライインジケータを生成するリトライ信号ジェネレータを有し、
前記好適なプロセッサのための前記リトライインジケータは、リトライの必要がないことを表す値を有し、
また前記複数のプロセッサユニットに含まれる残りのプロセッサユニットのための前記リトライインジケータは、リトライの必要があることを表す値を有することを特徴とするコンピュータシステム。
【請求項３１】
前記調停回路が、更に、
前記複数のプロセッサユニットに含まれるプロセッサユニットの数であるＰ個のセグメントを有する繰り返し選択パターンを繰り返し実行する選択ロジックを有し、
ここで各々の前記セグメントが、所定の数の連続衝突リクエストのため、前記好適なプロセッサとして前記複数のプロセッサユニットのうち異なる１つを選択することを特徴とする請求項３０に記載のコンピュータシステム。
【請求項３２】
前記選択ロジックがプログラム可能に変更され得ることを特徴とする請求項３１に記載のコンピュータシステム。
【請求項３３】
前記繰り返し選択パターンが、
各々Ｎ回の連続する衝突リクエストに関連する前記サイクルの間、前記共有のリソースにアクセスするために、前記好適なプロセッサとして第１のプロセッサユニットを選択する第１セグメントと、
前記Ｎ回の連続的な衝突リクエストが発生した後に発生する各々Ｍ回の連続する衝突リクエストに関連する前記サイクルの間、前記共有のリソースにアクセスするために、前記好適なプロセッサとして第２のプロセッサユニットを選択する第２のセグメントとを有することを特徴とする請求項３１に記載のコンピュータシステム。
【請求項３４】
Ｎが２であることを特徴とする請求項３３に記載のコンピュータシステム。
【請求項３５】
Ｍが２であることを特徴とする請求項３３に記載のコンピュータシステム。
【請求項３６】
前記リトライ信号ジェネレータが、
各々の前記Ｎ及びＭ回の衝突リクエストのために、前記第１のプロセッサユニットのためには第１のリトライインジケータを、また前記第２のプロセッサユニットのためには第２のリトライインジケータを生成するロジックを含み、
ここで前記Ｎ回の衝突リクエストのために生成された各々の前記第２のリトライインジケータは、リトライが必要であることを示す値を含み、
また前記Ｍ回の衝突リクエストのために生成された各々の前記第１のリトライインジケータは、リトライが必要であることを示す値を含むことを特徴とする請求項３３に記載のコンピュータシステム。
【請求項３７】
前記少なくとも１つの共有のリソースが、データキャッシュユニットを含むことを特徴とする請求項３０に記載のコンピュータシステム。
【請求項３８】
前記少なくとも１つの共有のリソースが、フィルバッファ中のデータレジスタを含むことを特徴とする請求項３０に記載のコンピュータシステム。
【請求項３９】
前記少なくとも１つの共有のリソースが、ライトバックバッファを含むことを特徴とする請求項３０に記載のコンピュータシステム。
【請求項４０】
前記調停回路が、更に前記複数のプロセッサユニットに含まれる各々のプロセッサユニットよりの少なくとも１つのトランザクション型インジケータをレシーブするべく構成されるトランザクション型インプットを含むことを特徴とする請求項３０に記載のコンピュータシステム。
【請求項４１】
前記少なくとも１つのトランザクション型インジケータがロードインジケータを含むことを特徴とする請求項４０に記載のコンピュータシステム。
【請求項４２】
前記少なくとも１つのトランザクション型インジケータがストアインジケータを含むことを特徴とする請求項４０に記載のコンピュータシステム。
【請求項４３】
前記トランザクション型インプットが、前記同一サイクルの間、前記複数のプロセッサユニットの１つよりのストアトランザクション型インジケータと、前記複数のプロセッサユニットの別ユニットよりのロードトランザクション型インジケータとの双方をレシーブするべく構成されることを特徴とする請求項４０に記載のコンピュータシステム。
【請求項４４】
前記調停プロトコル回路が、前記好適なプロセッサとして、前記ロードトランザクション型インジケータがレシーブされる前記プロセッサユニットを選択することを特徴とする請求項４３に記載のコンピュータシステム。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明はマルチプロセッサによって共有されるリソースに関し、更に詳しくはリソースを使用するための同時発生リクエストの解決に関する。
【０００２】
本発明は、発明者Marc Tremblay及びWilliam Joyによって"A Multiple-Thread Processor for Threaded Software Applications"と名付けられた、米国特許番号09/204,480（1998,10,12）に関連し、ここに参照したことで本出願の一部とされたい。
【０００３】
（関連技術の考察）
プロセッサは、多くの産業で広範囲に用いられてきた。プロセッサがその目的とするものは、情報の処理を迅速に実行することである。プロセッサが情報を処理するスピードを増加させるために用いられる１つの技術として、キャッシュと呼ばれる第１のローカルメモリを含むアーキテクチャを備えたプロセッサの提供がある。情報を処理するプロセッサのスピードを増加させるために用いられるその他の技術としては、マルチ（複数の）プロセッサユニットを備えたプロセッサアーキテクチャの提供がある。
【０００４】
キャッシュは命令やデータを一時的にストアする目的でプロセッサによって利用される。命令及びデータの双方をストアするキャッシュは統一キャッシュと呼ばれ、ここで命令のみをストアするキャッシュは命令キャッシュであり、データのみをストアするキャッシュはデータキャッシュである。統一キャッシュ又は命令キャッシュ及びデータキャッシュの何れかを備えたプロセッサアーキテクチャを提供することは、設計上の選択の問題である。
【０００５】
プロセッサのパフォーマンス要素は、プロセッサの要求データアイテムが、既にキャッシュ内に存在する確率である。プロセッサが情報アイテムにアクセスを試みる場合、それはキャッシュ内に存在するか否かの何れかである。存在する場合は、キャッシュ「ヒット」が発生する。プロセッサによって要求された時に、キャッシュ内にアイテムが存在しない場合、キャッシュ「ミス」が発生する。高いキャッシュヒットレート、即ち「ヒット率」に到達するキャッシュシステムを設計することが望ましい。
【０００６】
キャッシュミスが発生すると、プロセッサによって要求された情報が次にメモリより回収され、プロセッサによってアクセス可能となるようにキャッシュ内へと運ばれる。キャッシュミスの後のキャッシュ内にストアされていない情報アイテムのための検索は、通常システムメインメモリより情報アイテムを回収するために、費用が嵩み、また時間も要することとなる。キャッシュヒットの数を最大にするべく、プロセッサにおいて近未来に起こる動作で参照されるであろうデータがキャッシュ内にストアされる。キャッシュヒットを最大にする２つの普通の方法は、最新のリファレンスデータをストアすることと、最も一般的なリファレンスデータをストアすることである。
【０００７】
殆どの現存システムに於いて、キャッシュはキャッシュラインスロットのセットへ細分される。各々のセットが１つのラインのみを有する時、各々のメインメモリラインはキャッシュ内の１つの特定のラインスロット中にのみストアされることが可能である。このことはダイレクトマッピングと呼ばれる。対照的に、殆どの最新型プロセッサの各々のセットは複数のラインを有する。各々のセットが複数のラインを有することより、所与のセットに対しマッピングされたメインメモリラインがどのラインにストアされてもよく、またセット中でどのような「ウェイ（way）」でストアされてもよい。
【０００８】
キャッシュミスが発生する時、ミスしたアイテムを含むメモリのラインがキャッシュへとロードされ、別のキャッシュラインと置き換わる。このプロセスはキャッシュ置き換えと呼ばれる。ダイレクトマッピングシステムでは、メインメモリよりの各々のラインがキャッシュに於ける単一ラインスロット中に配置されるべく制限される。ダイレクトマッピングアプローチはキャッシュ置換プロセスを簡略化するが、ラインマッピングとの柔軟性の欠乏によってそのヒット率を制限してしまう傾向にある。対照的に、ラインマッピングの柔軟性、及びそれに伴う高いヒットレートが、アソシアティビティー（associativity）レベルの増加によって達成されてもよい。アソシアティビティーの増加は、セット当たりのライン数が増加し、メインメモリ中の各々のラインが任意にセット内のどのラインスロット（「ウェイ」）に配置されてもよい事を意味する。キャッシュ置き換えの間、セット中のラインの一つは置き換えられなければならない。キャッシュミス発生後にセット内のどのラインが置き換えられるのかを決定するための方法は、キャッシュ置き換えポリシーと呼ばれる。
【０００９】
オーバーライトするためのキャッシュ中でのデータ選択のために、従来方式のいくつかのキャッシュ置換ポリシーは、ランダム法、ＬＲＵ（Least-Recently Used）法、疑似ＬＲＵ（pseudo-LRU）法、及びＮＭＲＵ（Not Most-Recently-Used）法を含むものである。セット内に於いて置き換えられるべきラインがランダムに選択されることから、ランダム法が実行に際し最も簡潔なキャッシュ置き換えポリシーである。ＬＲＵ法は、更に複雑なキャッシュ置き換えポリシーである。それはプロセッサによってセット中の各ラインの実際のアクセスをトラッキング（track）し続ける論理回路を必要とする。ＬＲＵアルゴリズムによれば、ラインが長時間アクセスされない場合、それはそれ以上アクセスされる可能性が低く、それ故好適な置換候補であるという見込みが存在する。別の置き換えポリシーであるＮＭＲＵ法とは、アクセスされた最新のラインをトラッキングし続けるものである。この最新のアクセスラインは、置き換えのために選択されない。なぜなら、空間的局所参照性（spatial locality）の原理が、一度ある情報アイテムに対するアクセスが発生すれば、同一ライン内の別の近くのアイテムも近い将来アクセスされ得る可能性が高い事を示しているからである。ＮＭＲＵ法は、セット内の最新アクセスラインをトラッキングし続けるための論理回路を要求する。全てのキャッシュ置き換えポリシーに於いて、置き換えのために選択されるラインを「候補」と呼ぶこともある。
【００１０】
一度候補が選択されると、更なる処理がメモリの一貫性の保全を保証するためにキャッシュ内で発生し得る。候補の値がキャッシュ内で変更されている場合、それがメモリより回収されていることから、候補は「ダーティ」であり、メモリの非一貫性が存在する。ダーティ候補の値がプロセッサに要求される新しい情報と置き換えられ得る前に、ダーティ候補の現在の値がメモリへと更新され得る。この動作は「ライトバック」操作と呼ばれる。キャッシュラインに対する複数の変化がメモリにロードされる必要があるのはキャッシュラインが置き換えられようとする時のみであることから、そのようなスキームの実行がバストラフィックを低減する。一方で、ライトバック操作に対する欠点とは遅延である。即ちキャッシュに対するアクセスが遅延され、ライトバック操作の間、停止してしまう場合さえある。
【００１１】
（発明の要約）
本発明は、同一の共通のソースよりロードし、同一の共通のソースへストアすることを目標とする、マルチプロセッサユニットよりの同時リクエストを解決するための方法及びコンピュータシステムである。２つの異なるプロセッサユニットより衝突（colliding）リクエストが生じる場合、第１プロセッサユニットは所定数の連続衝突中で構造へのアクセスを許可され、第２装置は後に続く数の連続衝突中で構造へのアクセスを許可される。共通のリソースはフィルバッファ（fill buffer）であっても良く、ここでは、衝突リクエストはフィルバッファ中への同時のストアを試みる。共通のリソースは、共通のライトバックバッファであっても良く、ここで衝突リクエストはライトバックバッファ中への同時のストアを試みる。共通のリソースはデータキャッシュユニットであっても良く、ここで衝突リクエストはデータキャッシュユニット中の同一データスペースより同時ロードを試みる。衝突リクエストは、同一リソースよりロードしまたストアする試みを含んでも良く、そのような場合、ロードを試みる装置がストアを試みるデバイスよりも好まれる。
【００１２】
ある実施例では、共通リソースが複数のプロセッサユニットよりのアクセスリクエストをレシーブする。あるそのようなプロセッサユニットは、共通リソースにアクセスしうる好適なユニットとして選択されうる。各々のプロセッサユニットのために、リトライセレクタが設けられる。好適なユニットでは、ユニットの共通リソースに対するアクセスが許可されるので、リトライセレクタがリトライの必要が無い事を示す。好適ではないすべてのプロセッサユニットでは、リトライインジケータにリトライの必要を示す値が含まれる。好適プロセッサの選択は、P回のセグメントの反復選択パターン（repeating selection pattern）中で実行され、ここで各々のプロセッサはセグメントの一つの間、好適なプロセッサとして選択される。一実施例では、この反復選択パターンはプログラマブルに変更可能である。
【００１３】
ある実施例では、反復選択パターンはセグメントを含む。セグメントはN回の連続する衝突アクセスリクエストの間、好適なプロセッサとして第１のプロセッサユニットを選択する。また次に、セグメントは、N回の連続的な衝突アクセスリクエストが起こった後の各々M回の連続する衝突アクセスリクエストの間、好適なプロセッサとして第１のプロセッサユニットを選択する。ある実施例では、M及びNは共に２である。
【００１４】
衝突アクセス要求をレシーブする共通リソースは、フィルバッファ、データキャッシュユニット、若しくはライトバックバッファ内のデータレジスタであり得る。同一サイクルの衝突リクエストが、完了していないロード操作、若しくは完了していないストア動作であってもよい。
【００１５】
衝突リクエストが、１つのストア動作及び１つのロード動作を含むとき、ロード動作を要求するプロセッサユニットが好適プロセッサとして選択される。
【００１６】
ある実施例では、好適なプロセッサの選択が調停プロトコルユニットによって為される。調停プロトコルユニットは、選択パターンを繰り返して実行可能な選択ロジックを有し、ある実施例ではここでM及びNが２に等しい。選択ロジックは、プログラム可能に変更されてもよい。リトライ信号はリトライ信号ジェネレータで生成される。
【００１７】
ある実施例では、上述の方法がコンピュータシステムで実行される。ある実施例では、コンピュータシステムは、同一サイクルの衝突アクセスリクエストを調停する、調停回路を有する。調停回路は、選択ロジックを有する。選択ロジックのある実施例ではM及びNは共に２に等しい。ある実施例では、コンピュータシステムは上述のようにリトライ信号ジェネレータを有する。
【００１８】
本発明は、次の詳細な説明及び付随する図面によって、より完全に理解されるであろう。
【００１９】
（発明を実施するための最良の形態）
本発明は、同一サイクル中に複数のプロセッサユニットを有するような、共有リソースへのアクセスに対する衝突要求を決定する方法、回路及びコンピュータシステムに関する。リソースは、複数のプロセッサユニットにより共有される任意の構造または構造の一部、即ち例えばフィルバッファ、共有書込みバッファ、またはデータキャッシュユニットのアドレス空間であり得る。本発明を実行するための方法について以下に詳細に説明する。本明細書中の説明は、本発明の例示を意図するものであり、本発明を限定するものとは考えないでいただきたい。
【００２０】
本発明に基づくコンピュータシステム１００を図１に示す。コンピュータシステム１００は、第１プロセッサユニット１０４（MPU0）及び第２プロセッサユニット１０６（MPU1）に接続されたデータキャッシュユニット（DCU）１０２を有する。好適実施例ではプロセッサユニットの数は２つであるが、本発明では任意の数の複数のプロセッサユニットを用い得る。第１プロセッサユニット１０４及び第２プロセッサユニット１０６などの複数のプロセッサユニットは、メディアプロセッサユニットであり得る。例えば、発明者Marc Tremblay及びWilliam Joyにより出願された "Multiple-Tread Processor for Threaded Software Applications" と題する米国特許出願第09/204,480号は、本発明に基づくメディアプロセッサユニットを示す。該特許出願は、引用を以って本明細書の一部となす。
【００２１】
図１は、各MPU及びメインメモリに接続されたデータキャッシュユニット１０２を示す。第１プロセッサユニット１０４は、６４ビットデータ経路、３２ビットアドレス経路、リトライ経路及びヒット経路を介して、データキャッシュユニット１０２に接続されている。第２プロセッサユニット１０６もまた、６４ビットデータ経路、３２ビットアドレス経路、リトライ経路及びヒット経路を介して、データキャッシュユニット１０２に結合されている。データキャッシュユニット１０２は、従来のバス１１０により従来のメインメモリ１０８に接続されている。より具体的には、データキャッシュユニット１０２は、６４ビットデータ入力経路、６４ビットデータ出力経路及び２７ビットバッファフラッシュアドレス経路を介してバス１１０に接続されている。
【００２２】
図２は、データキャッシュユニット１０２をより詳細に示す図である。データキャッシュユニット１０２は、メインメモリ１０８にアクセスすることにより可能であり得るよりも、第１プロセッサユニット１０４及び第２プロセッサユニット１０６によるより高速なアクセスのためのデータをストアする。図２より、データキャッシュユニット１０２には、データアレイ２０２、ステータスアレイ２０４、ディレクトリアレイ２０６、フィルバッファ２０８、共有ライトバックバッファ２１０及び選択回路２１２が含まれることがわかる。データキャッシュユニット１０２のこれらの各構成要素については、以下に詳述する。先ずデータアレイ２０２について説明し、続いてディレクトリアレイ２０６、ステータスアレイ２０４、選択回路２１２、フィルバッファ２０８及びライトバックバッファ２１０について説明する。
【００２３】
図２は、データアレイ２０２が第１プロセッサユニット１０４から３２ビットアドレス信号（add_MPU0）を受け取り、第２プロセッサユニット１０６から３２ビットアドレス信号（add_MPU1）を受け取り、フィルバッファ２０８から２５６ビットデータ信号を受け取ることを示している。データアレイ２０２はまた、ディレクトリアレイ２０６から第１及び第２ヒット信号（hit0, hit1）を受け取る。データアレイ２０２は、６４ビットデータ信号（datum0）を第１プロセッサユニット１０４へ、６４ビットデータ信号（datum1）を第２プロセッサユニット１０６へ供給する。データアレイ２０２はまた、６４ビットデータ信号datum0及び６４ビットデータ信号 datum1をライトバックバッファ２１０へ供給する。
【００２４】
データアレイ２０２は、データキャッシュユニット１０２のデータをストアする。好適実施例では、データアレイ２０２は４つの論理バンク２４０ａ〜２４０ｄを有し、各バンクは１２８ラインの２５６ビットをストアする。論理バンク２４０を好適に具現化したものが静的ランダムアクセスメモリ（SRAM）である。図２からは、データアレイ２０２には２つのマルチプレクサ２３０ａ、２３０ｂも含まれることがわかる。データアレイ２０２の動作については以下に詳述する。
【００２５】
ディレクトリアレイ２０６に関して、図２は、ディレクトリアレイ２０６が第１プロセッサユニット１０４から３２ビットアドレス信号（add_MPU0）を受け取り、第２プロセッサユニット１０６から３２ビットアドレス信号（add_MPU1）を受け取ることを示している。ディレクトリアレイ２０６はまた、ステータスアレイ２０４から第１及び第２の１５ビットステータス信号（status0, status1）を受け取る。ディレクトリアレイ２０６は、第１及び第２ヒット信号をデータアレイ２０２へ供給する。ディレクトリアレイ２０６はまた、タグアドレスを含む第１及び第２データ出力信号（rdata0, rdata1）をライトバックバッファ２１０へ供給する。
【００２６】
ディレクトリアレイ２０６は、データキャッシュユニット１０２のデータアレイ２０２内の対応する位置にストアされたデータのアドレスをストアする。ディレクトリアレイ２０６は、４つの論理バンク２６０ａ〜２６０ｄを有し、各バンクは１２８本の２０ビット幅ラインを含む。この２０ビットは、３２ビットアドレスの２０以上の有効ビットに対応する。データは、４つの論理バンク２６０ａ〜２６０ｄの１つにある所与の位置にストアされる。４つの各所与の位置は、「ウェイ」と呼ばれる。「セット」には、データがストアされる４つの可能「ウェイ」が含まれる。論理バンク２６０を好適に具現化したものが静的ランダムアクセスメモリ（SRAM）である。図２からは、ディレクトリアレイ２０６には２つのコンパレータ２７０ａ、２７０ｂも含まれることがわかる。ディレクトリアレイ２０６の動作については、以下に詳述する。
【００２７】
再びステータスアレイに話を戻すと、図２は、ステータスアレイ２０４が第１プロセッサユニット１０４から３２ビットアドレス信号（add_MPU0）を受け取り、第２プロセッサユニット１０６から３２ビットアドレス信号（add_MPU1）を受け取ることを示している。ステータスアレイ２０４はまた、選択回路２１２から第１及び第２の１５ビットステータス信号（status0, status1）を受け取る。ステータスアレイ２０４は、有効ビットをディレクトリアレイ２０６へ供給する。ステータスアレイ２０４はまた、第１及び第２の１５ビットステータス信号（status0, status1）を選択回路２１２へ供給する。
【００２８】
ステータスアレイ２０４は、データアレイ２０２の各「ウェイ」に関する情報を含むステータスワードをストアする。ステータスアレイ２０４は、各１５ビットのステータスワードを１２８個ストアするための１若しくは数個の論理バンク２５０を有する。論理バンク２５０を好適に具現化したものが静的ランダムアクセスメモリ（SRAM）である。ステータスアレイ２０４の動作については以下に詳述する。
【００２９】
更に図２を見ながらデータキャッシュユニット１０２の構成要素の考察を続け、今度は選択回路２１２に目を向ける。選択回路２１２は、新たな１５ビットステータスワードを生成して各ロード／ストアアクセス後のサイクル毎にアップデートされ、ステータスアレイ２０４にストアされる（すぐ後に説明するように、１５ビットステータスワードのフォーマットを図３に示す）。選択回路２１２はまた、キャッシュ置き換えに対するビクティムナンバー（victim number）を生成し、候補がダーティかどうかを示し、候補の新しいデータがオーバーライトされる前にライトバックバッファにロードされることを表す。図２は、選択回路２１２がステータスアレイ２０４からアクセスのためのステータスワードを受け取ることを示す。例えば、ダーティビットを（ストアヒットにおいて）セットし、置換ビットをアップデートして有効ビットをクリアすることを必要とし得る。
【００３０】
図３にステータスワード３００のサンプルを示す。ステータスワード３００は、１５ビットワードであり、ロック・ステータス、リファレンスウェイ、４つの各ウェイ0〜3が前のキャッシュミスで利用されているかどうか、４つの各ウェイがダーティかどうか、４つの各ウェイが有効かどうかを示す。より具体的には、ビットR1及びR2は、以下に述べるようにキャッシュ置換アルゴリズムを実行するために選択回路２１２が用いるリファレンスウェイを表す。例えば、NMRUキャッシュ置換ポリシーでは、ビットR1及びR2は特定のセットに対する最高使用頻度ウェイを有することになる。LRUキャッシュ置換ポリシーでは、ビットR1及びR2は最低使用頻度ウェイを有することになる。ビットM0〜M3は、対応するウェイが既にキャッシュミスにより占められているかどうかを示す。このMインジケータは、キャッシュ置換アルゴリズムにおけるビクティムナンバー生成ロジックを簡単にする。ビットV0〜V3は、対応するウェイが有効かどうかを示す。無効なウェイとは、意味のあるデータがないウェイであり、従ってキャッシュミスでオーバーライトされそうな候補である。換言すれば、無効ウェイはメモリをフラッシュしないので、無効ウェイには新たなデータが取り込まれない。ビットD0〜D3は、対応するウェイがダーティかどうかを示す。即ち、このウェイは意味のあるデータを含むだけでなく、データはメモリから回収されたのでデータは変更されており、従ってメモリの非一貫性が存在する。しかし、ロックビットLは、キャッシュラインが所定の位置に固定されて動かせないことを示す。例えばロックビットを原子ロードヒット上にセットする。ロックビットのセッティングにより、ロックビットをリセットするまでセットへのアクセスが不可能になる。
【００３１】
データキャッシュユニット１０２の選択回路２１２は、適切なステータスワードの「ミス」ビットを変更していずれの「ウェイ」が置き換えの候補であるかを示すことにより、キャッシュ置換ポリシーを実行する。選択回路２１２は、ステータスアレイ２０４から要求されたデータに関連するステータスワードを受け取り、可能であればアップデートされたステータスワードをステータスアレイ２０４に供給する。
【００３２】
図５は、選択回路２１２のブロック線図である。選択回路２１２はステータスアレイ２０４をアップデートし、オーバーライトするために用いられるビクティム（または「候補」）ナンバーをキャッシュが生成するような本発明の多重可変置換ポリシー７００を実行する。選択回路２１２は、ステータスアレイ２０４から１５ビットのstatus0信号及び１５ビットのstatus1信号を受け取り、ライトバックバッファ２１０からフィルビットf1, f2を受け取る。選択回路２１２はまた、コントロール入力としてmiss0及びmiss1信号を受け取る。これらの４ビット信号は、ディレクトリアレイ２０６からデータアレイ２０２へ送られるhit0及びhit1信号の論理逆転である。別の信号は、選択回路２１２がフィルバッファ２０８からのフィルバッファステータスであることを入力する。選択回路２１２は、アップデートされた１５ビットのstatus0信号及びアップデートされた１５ビットのstatus1信号をステータスアレイ２０４へ供給する。選択回路２１２の動作については、以下に詳述する。
【００３３】
データキャッシュユニット１０２の次に述べる構成要素はフィルバッファ２０８であり、これはキャッシュミスが発生した際に用いられる。キャッシュミスが発生するのは、プロセッサMPU0、MPU1が要求するメモリのラインがデータキャッシュユニット１０２にないときである。フィルバッファ２０８は、第１プロセッサユニット１０４から３２ビットアドレス信号（add_MPU0）を受け取り、第２プロセッサユニット１０６から３２ビットアドレス信号（add_MPU1）を受け取る。フィルバッファ２０８は、メインメモリ１０８から６４ビットデータ信号を受け取り、データキャッシュユニット１０２にストアされることになるメインメモリ１０８からのデータを保持する。図２は、データアレイ２０２に書き込まれたデータをストアするデータレジスタ２２０を含むフィルバッファ２０８を示す。データレジスタ２２０は、２５６ビットのデータをストアする。フィルバッファ２０８は、２５６ビットデータ信号をデータアレイ２０２へ供給する。フィルバッファ２０８はまた、６４ビットデータ信号であるdata_MPU0及び第２の６４ビットデータ信号であるdata_MPU1をデータアレイ２０２に送る。最後に、フィルバッファ２０８はまた、フィルバッファヒットステータスをデータアレイ２０２及び選択回路２１２へ供給する。
【００３４】
更に図２からは、フィルバッファ２０８には、データアレイに書き込まれるデータに関連する或る種のステータスビット及びアドレスストアするアドレスレジスタ２２２も含まれることもわかる。アドレスレジスタはまた、データアレイ内にデータがストアされる「ウェイ」をストアする。フィルバッファ２０８の動作については、以下に詳述する。
【００３５】
最後に説明するデータキャッシュユニット１０２の構成要素は、ライトバックバッファ２１０である。ライトバックバッファ２１０は、キャッシュミスが発生した際に、メモリに押し込めるようになるまでダーティブロックのための一時プレースホルダとして働く。「ダーティ」ブロックとは、メインメモリ１０８からブロックを得られないためにコンテンツが変更されてしまったブロックである。ダーティブロックがライトバックバッファ２１０にストアされる前に、選択回路２１２は、ステータスワード３００（以下に述べる図３のM0、M1、M2、M3を参照）にストアされた「ビクティム」ナンバーをダーティブロックに割り当てる。ビクティムナンバーは、キャッシュ置換ポリシーに基づき所与のセットのためにキャッシュミス上でプレースホルダに選択された特定のウェイである。ダーティブロックが「犠牲化（victimize）」されたら、ダーティビクティムからデータが読み出され、ライトバックバッファ２１０にラッチされ得る。図２は、ライトバックバッファ２１０が第１プロセッサユニット１０４に関連してデータアレイ２０２から６４ビットデータ信号（datum0）を受け取り、第２プロセッサユニット１０６に関連してデータアレイ２０２から６４ビットデータ信号（datum1）を受け取ることを示している。ライトバックバッファ２１０はまた、ディレクトリアレイ２０６から第１プロセッサユニット１０４に対するデータ出力信号（rdata0）及び第２プロセッサユニット１０６に対するデータ出力信号（rdata1）を受け取る。データ出力信号（rdata0, rdata1）は、ダーティブロックのタグアドレスを含む。図２は、ライトバックバッファ２１０が、ダーティブロックのためのセットアドレスを示すような各プロセッサユニット１０４、１０６に対するset_addr信号も受け取ることを示す。set_addr信号は、add_MPU0またはadd_MPU1で表されるビットの全部または一部から作られる。
【００３６】
図４は、共有ライトバックバッファ２１０のブロック線図である。データキャッシュユニット１０２にはライトバックバッファ２１０が１つしかないので、MPU0１０４とMPU1１０６でライトバックバッファを共有する（図２に示したものと同様）。図４は、共有ライトバックバッファ２１０が、アドレスバンク４０２、データバンク４０４及び、キャッシュ制御ロジック（図示せず）に制御される選択回路４０６を有することを示している。共有ライトバックバッファ２１０のデータバンク４０４は２つのエントリを有し、各エントリはキャッシュラインサイズのデータレジスタ４０４ａ、４０４ｂを含む。好適実施例では、各データレジスタ４０４ａ、４０４ｂは、データアレイ２０２から受け取った２５６ビットのデータをストアする。同様に、ライトバックバッファ２１０のアドレスバンク４０２も２つのエントリ４０２ａ、４０２ｂを有し、各エントリは、メインメモリ１０８にライトバックされるべきダーティ候補のアドレスをストアすることができる。当業者であれば、ライトバックバッファのアーキテクチャが多数のバリエーションを有しうるものであり、図４に示す物理的実施形態に限定されるものではないことを理解されたい。ライトバックバッファは、幾つかのレベルを有しうる。例えば、共有ライトバックバッファは図４に示す２つのエントリアドレスバンク４０２及びデータバンク４０４に代えて複数のレベルで実行することができ、各MPU１０４、１０６は高レベル共有バッファと連絡する低レベル個別バッファを有する。同様に、共有ライトバックバッファは低レベル分割ライトバックバッファと連絡する共有ライトバックバッファを有し得る。更に、バッファコンポーネント４０４ａ、４０４ｂ、４０６は論理的に結合しているが、これらはプロセッサアーキテクチャ内で物理的に相互に隣接している必要は必ずしもないということは、当業者であれば理解されよう（類似例として好適実施例では、図２に示すフィルバッファデータレジスタ２２２ａ、２２２は、フィルバッファ２０８と論理的に関連しているが、物理的にはデータアレイ２０２の一部として区分されていることに留意すべきである）。
【００３７】
アドレスエントリ４０２ａ、４０２ｂは、各アドレスエントリ４０２ａ、４０２ｂがフルであるかどうかを示すfビットf1及びf2を更に有する。例えば、f1及びf2が共に２進ビットであれば、書込みバッファ２１０はフルである。f1及びf2ビットは、書込みバッファ２１０に関連する制御ロジックによりセットされる。共有書込みバッファ２１０は、以下に詳述するキャッシュ置換ポリシーで使用するために「フル」信号を選択回路２１２へ供給する。
【００３８】
本発明で使用される１つの共有書込みバッファ２１０は、各プロセッサに割り当てられた個別のライトバックバッファを含む先行技術のデータキャッシュユニットから離れた複数のデータレジスタ４０４ａ、４０４ｂ及びアドレスエントリ４０２ａ、４０２ｂを含む。本発明の好適実施例では、共有ライトバックバッファ２１０を用いて、データレジスタ４０４ａ、４０４ｂのより効率的な使用を提供する。ライトバック動作はデータキャッシュユニット１０２の動作を減速または停止させるので、共有ライトバックバッファ２１０を提供することにより、ライトバック動作の低下によるデータキャッシュユニット１０２の動作における遅延を低減する。例えば、先行技術システムでは、第１プロセッサが第１データワードを関連する第１ライトバックバッファに書き込むが、関連する第１ライトバックバッファが容量までフルになっている場合、第１ライトバックバッファにストアされたデータワードはメモリにライトバックされる。対照的に、図４に示すように、本発明は、データワードをストアするための容量を有する第２レジスタ４０４ｂを提供する。上記の例を本発明に適用すると、第１データワードを第２データレジスタ４０４ｂに書き込むことにより、ライトバック動作を回避することができる。ライトバックバッファ２１０の両エントリがフルであれば、先入れ先出し（FIFO）方式で動作する。ライトバックバッファ２１０がフルであるときに到達するデータワードは、メインメモリ１０８に戻されるライトバックバッファにストアされた最も古いデータワードをライトバックバッファ２１０に書き込ませる。
【００３９】
更に、本発明の共有ライトバックバッファ設計の利点は、各プロセッサのための個別のライトバックバッファと比較して、システムに必要なハードウェアが少ないことである。１つのライトバックバッファ２１０は、１本のラインを用いてライトバックバッファ２１０をメモリ１０８に接続することができ、メモリへの複数のバッファのアクセスを調整するためのロジックは必要なくなる。換言すれば、共有ライトバックバッファ２１０は、どのライトバックバッファが所与の時間にメモリに書き込むかを調整するためのロジックを必要としない。
【００４０】
図４を更に参照すると、ライトバックバッファ２１０に関連する制御ロジックは、巡回待ち行列としてバッファ２１０を実行し、上述のFIFO 動作に影響を与える。この制御ロジックは、図４中では選択回路４０６として示されており、アドレス選択回路４０６ａ及びデータ選択回路４０６ｄが含まれる。アドレス選択回路４０６ａは、どのアドレスバンク４０２が入力データをストアするかを決定する。データ選択回路４０６ｄは、どのデータバンク４０４に入力データワードがストアされているかを決定する。
【００４１】
本発明では、データキャッシュユニット１０２の上記構成要素コンポーネントが種々の機能を発揮することが要求される。１）ヒット／ミス計算及び２）ミス発生時のキャッシュ置換ポリシーの適用は、これら機能のうちの２つである。これらの機能に関する考察に役立つように、データキャッシュユニット１０２の一部即ちディレクトリアレイ２０６、データアレイ２０２及びステータスアレイ２０４を図６に示す。好適実施例の各データアレイ２０２は４つの論理バンク２４０ａ〜２４０ｄを有するが、説明を簡潔にするため、図６には２４０ａ及び２４０ｂの２つの論理バンクのみを示す。同様に、ディレクトリアレイ２０６の好適実施例は４つの論理バンク２６０ａ〜２６０ｄを有するが、図６には２６０ａ及び２６０ｂの２つのみを示す。
【００４２】
ヒット／ミス機能は、MPU１０４、１０６からデータキャッシュユニット１０２へのロードまたはストアアクセスに対する要求がトリガとなる。MPU１０４、１０６がロードまたはストアアクセスを要求してきたら、MPUはアクセスされるメモリ位置のためのアドレスを指定しなければならない。図６は、MPU0及びMPU1が各３２ビットのメインメモリアドレス（それぞれ「add_MPU0」「add_MPU1」）をディレクトリアレイ２０６、データアレイ２０２及びステータスアレイ２０４へ供給することを示している。この例では、独自のメインメモリアドレスを有するデータワードは単一セットにしかストアすることができないが、任意の２つのウェイにストアできる。各メインメモリアドレスは、従来の方法で０または１のいずれかのセット数に変換される。セット数に応じて、データアレイ２０２の２つの論理バンク２４０ａ、２４０ｂはそれぞれ、それぞれのMPU0及びMPU1が要求するデータに応じて各マルチプレクサ２３０ａ、２３０ｂにデータを提供する。同時に、ディレクトリアレイ２０６のセット数（２つの各論理バンク２６０ａ及び２６０ｂ）に応じて、メインメモリアドレス（いわゆる「ディレクトリアドレス」）をそれぞれのコンパレータ２７０ａ及び２７０ｂへ供給する。
【００４３】
ステータスアレイ２０４は、コンパレータ２７０ａ及び２７０ｂデータに、MPU0がアクセスする「valid0」信号及びMPU1がアクセスする「valid1」信号を供給する。これらの信号のＨ値は、それぞれのウェイが有効であり、オーバーライトするのによい候補ではないことを示す。「valid0」及び「valid1」信号は、図３に示すstatus0ワードから派生したものであり、各セットの各ウェイについての情報を示す。
【００４４】
ウェイを示す「valid0」のみならずマッチング「add_MPU0」及びディレクトリアドレスを受け取るコンパレータ２７０ａ、２７０ｂが有効であるとき、MPU0１０４に供給するための２つの論理バンク２４０ａ、２４０ｂからの出力を選択するための「hit0」信号をデータアレイ２０６のマルチプレクサ２３０ａに発する。MPU1１０６に対しても同様な動作を行い、マッチング「add_MPU0」及びディレクトリアドレスを受け取るコンパレータ２７０ａ、２７０ｂが有効であるとき、MPU1１０６に供給するためのデータアレイ２０６の２つの論理バンク２４０ａ、２４０ｂからの出力を選択するための「hit1」信号をデータアレイ２０６のマルチプレクサ２３０ａに発する。
【００４５】
ディレクトリアレイ２０６はまた、キャッシュヒットが発生したことをリクエストMPUに対して示すために、各々ＭＰＵ０ １０４若しくはＭＰＵ１ １０６に対して、「cache_hit0」信号若しくは「cache_hit1」信号を提供する（図１参照）。一方、ディレクトリアレイ２０６は、「cache_hit0」信号若しくは「cache_hit1」信号の低い値を通じて、要求されたデータワードがデータキャッシュユニット１０２内に存在しないこと（即ちキャッシュミス）をリクエストMPUに対し示す。
【００４６】
図７は、データキャッシュユニット１０２が上述したヒット／ミス機能を実行するのと同じ時間での、選択回路２１２によって実行されるキャッシュ置き換えポリシー７００を示す。２つの機能は、パラレルに実行され、キャッシュミスの場合に、ビクティムナンバーが利用可能となってもよい。ポリシー７００は、ライトバックバッファ２１０に対するダーティ候補の書込みを回避する試みの間に、書き換えられるべき候補として役立つ方法を選択するプロセスである。ライトバックバッファ２１０が混み合う所では、ライトバックバッファへのダーティ候補の書込みが、時間を要するライトバック動作のトリガとなってしまう。選択回路２１２は、第１のプロセッサユニット及び第２のプロセッサユニット１０６のため、同時にダーティ候補を決定する。
【００４７】
尚図７を参照すると、キャッシュにアクセスするためのMPU１０４及び１０６よりのリクエストは、キャッシュ置き換えポリシー７００の実行を開始させる。プロセス中の初期ステップ７０２は、ポテンシャルミスに関連したアドレスに対応する全ての４つのウェイが有効であるかどうかを決定するものである。選択回路２１２は、図３のステータスワードにアクセスすることでこれを達成し、それは特定のセットのためどのウェイが有効であるかを示す。ウェイが有効である場合は、それは有意データを含まないウェイと同様に、オーバーライトされるのに適した候補ではない。そのような訳で、候補となるセットに関連するどのようなウェイも有効でない場合、選択回路２１２は、連続するキャッシュストア中にオーバーライトされるような候補として、ステップ（７０３）で無効ウェイを選択する。（７０３）に於ける候補の選択は、最も低いウェイナンバー（０）に対する最も高いウェイナンバー（３）の解析過程と、ステータスワード内で無効であるとしてマークされている最も高いウェイナンバーの選択過程とを含む。プロセスはステップ（７０４）で終了する。
【００４８】
全てのウェイが有効である場合、データキャッシュユニット１０２は、ミスの場合の有効ウェイをオーバーライトする以外に選択の余地はない。そのような場合、ライトバック操作を開始させないウェイが選択されることが好ましい。換言すれば、ダーティではない有効なウェイが選択されることが好ましい。そのために、選択回路２１２は第１にステップ（７０５）に於いて複数の従来方式のキャッシュ置き換えアルゴリズムを実行する。そのアルゴリズムとは、例えばNMRU法である。ステップ（７０５）を促進するべく、図３のステータスワードのビットR1及びR2は共に、最も重要でないウェイを表すビットR1及びR2に於ける00、及び最も重要なウェイを示す11を伴い、リファレンスウェイを表現する。例えばNMRUアルゴリズムを用いるにあたり、ビットR1及びR2は最高アクセス頻度のウェイを表す。またLRUアルゴリズムを実行するにあたり、ビットR1及びR2は最低使用頻度のウェイを表す。
【００４９】
図７を見ると、ステップ（７０５）で潜在的候補が識別されたら、ステップ（７０６）でライトバックバッファが一杯になっているかどうかが決定されることがわかる。この決定は選択回路２１２によってなされる。選択回路２１２は、ライトバックバッファ２１０から供給されるフル信号を解析し、一杯になっていることの他のインジケータ、例えばライトバックバッファ２１０をロードするための容認できない長いサイクル時間も解析する。ライトバックバッファ２１０が一杯になっていれば、ステップ（７０８）において選択回路２１２はステップ（７０５）で識別された潜在的候補がダーティであるかどうかを決定する。当業者であれば、ステップ（７０５）、（７０６）、（７０８）の順序は重要ではないということが理解されよう。むしろ、ステップの任意の組み合わせが候補を選択し、（候補がダーティである）且つ（書込みバッファがフルである）を決定するのであれば、ステップを任意に組み合わせて実行し得る。別の実施例では、ステップ（７０８）の前にステップ（７０６）を実行し得る。更に別の実施例では、キャッシュ置換アルゴリズムを適用する前に書込みバッファがフルになるかどうか（７０６）をチェックし得る。
【００５０】
共有ライトバックバッファ２１０がフルでなければ、終了ステップ（７０７）でプロセス（７００）は終了する。その場合、候補が識別されていないのでライトバック操作がトリガとならないことになり、候補がダーティであると証明すべきであれば、ライトバックバッファ２１０に余地がある。一方で、ライトバックバッファがフルであれば、ステップ（７０５）で識別された候補がダーティならば更に処理を進めなければならない。従って、図７より、選択回路２１２はステップ（７０８）で候補がダーティであるかどうかを決定するが、これは、ステップ（７０５）で候補が選択され且つ選択回路２１２がステップ（７０６）でライトバックバッファ２１０が一杯になっていることを決定してから初めて実行されることがわかる。候補がダーティかどうかを決定するために、データキャッシュユニット２０１では、候補と、メインメモリまたは２次メモリにおいて同一アドレスを有する親とが異なるかどうかを決定する。異なる場合には、候補は「ダーティ」であり、親はライトバック動作においてダーティ候補で置き換えられなければならない。対応するステータスワードstatus_0またはstatus_1は、ビットD0〜D3によりどの「ウェイ」がダーティかを示す。候補がダーティでなければ、親をアップデートする必要がないのでプロセスは終了ステップ（７０７）で終了する。候補は、決定ステップ（７０５）中に識別される。
【００５１】
図７によれば、ステップ（７０８）で候補がダーティであると識別されたら、選択回路はライトバック動作のトリガリングを回避するためにダーティでない候補を識別しようとすることがわかる。図７からわかることは、ダーティ候補が識別され且つライトバックバッファ２１０が一杯になっていれば、選択回路２１２はステップ（７０９）でチェックしてセットに対してダーティでない候補が存在するかどうかを決定する。ダーティ候補の他の３つのウェイに対する「ダーティ」ビットD0〜D3をステップ（７０９）で決定し、残り３つのウェイがダーティであるかどうかを調べる。ダーティウェイが存在するならば、１つを候補として選択し、プロセス７００は終了ステップ（７１０）で終了する。ダーティ候補は候補ではなくなり、従ってライトバックバッファ２１０へのダーティ候補のストアを回避し、このことが、共有ライトバックバッファ２１０が一杯になっているようなライトバック動作のトリガとなることになる。
【００５２】
しかし、全てのウェイがダーティであり且つライトバックバッファが一杯になっていれば、ステップ（７０５）で選択したダーティ候補はとてもよい選択であり、新たな候補は選択されない。これが、プロセッサが選択した新たなデータでオーバーライトされたダーティ候補を生み出す結果となり、それによって候補の現在の値がステップ（７１１）でライトバックバッファ２１０にストアされる。共有ライトバックバッファ２１０がフルであれば、ライトバックバッファのコンテンツは関連するメインメモリ位置にライトバックされ、続いてダーティ候補がライトバックバッファに配置される。
【００５３】
候補の選択後に、選択回路２１２は、候補のウェイにおけるミスを示すために候補に関連するステータスワードをアップデートする。特定のウェイにミスビットをセットすることは、ウェイが前のキャッシュミスに対する候補として選択されたことを示す。選択回路２１２は、４ビット信号「miss0」及び「miss1」を生成し、それぞれMPU0及びMPU1により供給されるアドレスに関連するどのウェイがミスとしてマークされるかを示す。選択回路２１２は、図７のプロセス７００を実行する。
【００５４】
選択回路２１２はミス信号miss0を受け取り、MPU0に関連する候補のステータスワードを変更し、そうすることにより、「miss0」がどのウェイを表すかによって適切なミスビットM0、M1、M2またはM3をセットする。同様に、選択回路２１２は、MPU1に関連する候補のステータスワードを変更することでミス信号「miss1」に応答する。それによって、「miss1」がどのウェイを表すかによって適切なミスビットM0、M1、M2またはM3をセットする。選択回路２１２からステータスアレイ２０４に与えられるステータスワードは、キャッシュミスを生じさせる「add_MPU0」及び「add_MPU1」に応じてステータスワードをオーバーライトする。
【００５５】
図２を参照すると、アップデートされたステータスワードstatus0及びstatus1は、ステータスアレイ２０４に経路指定される。続いて、キャッシュ置換ポリシー７００の実行中に選択された候補は、キャッシュのリフィル動作時にオーバーライトされる。フィルバッファ２０８は、データキャッシュユニット１０２に書き込まれたデータをキャッシュミスにストアする。フィルバッファ２０８は、キャッシュ置換ポリシー７００で決定されたウェイ候補を用いて、適切なアドレスレジスタ２２２のボトム（即ち「先入れ」）エントリからのデータをストアする。フィルバッファ２０８は、関連ウェイ及び関連メインに基づきメモリアドレスにデータアレイ２０２の適切な位置にデータを書き込む。続いて、オーバーライトされたデータワードに関連するステータスワードのミスビットを0に戻し、ミスがデータに関連しないことを示す。
【００５６】
図１及び図２は、MPU0１０４及びMPU1１０６が、フィルバッファ２０８、ライトバックバッファ２１０、及びデータキャッシュユニット１０２を構成するその他のリソースを共有していることを示す。この構成は、複数のプロセッサユニット（例えばMPU0１０４及びMPU1１０６）が同一リソースへまたは同一リソース内のストレージ空間へのアクセスを要求することを可能にする。複数のプロセッサユニットが同一サイクル中に同一リソースへのアクセスを要求する場合には、要求は「衝突する」と言われ、衝突を生み出す。換言すると、２つのプロセッサユニットが同一サイクル中に同一リソースにアクセスしようとしたときに「衝突」が発生する。衝突を生じさせるコンテンションは、例えば、複数のプロセッサが同一サイクル中にフィルバッファ２０８にアクセスしようとしたとき、複数のプロセッサが同一サイクル中に共有ライトバックバッファ２１０にアクセスしようとしたとき、複数のプロセッサが同一サイクル中に同一キャッシュラインでBLKZERO命令を実行しようとしたか或いは同一メモリアドレス（またはキャッシュライン）に書き込もうとしたときなどに起こり得る。衝突は、例えば同一サイクル中に１つのプロセッサユニットがデータキャッシュユニット１０２のリソースにアドレスをストアしようとして、別のプロセッサユニットが同一位置からロードを実行しようとしたときなどにも起こり得る。別の例としては、両プロセッサユニットが同一アドレスにロードアクセスを実行しようとしたときなどにも衝突は起こり得る。この場合には、add_MPU0及びadd_MPU1の値は、その任意のサブセット（例えばadd_MPU0またはadd_MPU1に含まれるセットアドレスなど）であるので、現アドレスである。ロード動作時に衝突が発生するのは初めて現れるのではないが、ロードはメモリに書込みを行わないのでステータスワードのアップデート中に衝突が発生する。ステータスワードはロード動作のためにアップデートされ、２つのプロセッサが同一サイクル中に同一ステータスワードに書込みを行おうとすれば、衝突が発生することになる。
【００５７】
図８に示す調停回路８００は、データキャッシュユニット１０２が複数のプロセッサユニットから共有リソースにアクセスするという衝突要求を効果的に処理できるようにする。データキャッシュユニット１０２により或いはデータキャッシュユニット１０２内で用いるための調停回路８００は、調停プロトコル回路８０２及びリトライ信号ジェネレータ８０４を有する。調停プロトコル回路８０２は、どのプロセッサユニットが衝突の発生時にコンテンションリソースへのアクセスを得ることができるかを決定する。
【００５８】
例えば、MPU0１０４及びMPU1１０６は、キャッシュミスのトリガとなり、ライトバックバッファ２１０にストアするためのダーティ候補を有し得る。その場合、調停プロトコル回路８０２はそれぞれのプロセッサユニットから信号「address_valid0」及び「address_valid1」を受け取る。「address_valid0」及び「address_valid1」は、それぞれのプロセッサユニットにより供給されたアドレスが有効か否かを表す。address_validインジケータは、同一リソースへのアクセスに対する同時プロセッサ要求を「調停」する必要があることを調停プロトコル回路８０２に告知する。即ち、調停プロトコル回路８０２は、適用可能サイクル中にどのプロセッサの要求が遂行されることになるかを決定しなければならない。このタイプの衝突は、add_MPU0とadd_MPU1を比較するか、address_valid0及びaddress_valid1が共にセットされているならばその中のビットのサブセットと比較することにより、調停プロトコル回路８０２が検出する。各プロセッサが同一アドレスにアクセスしようとしていることをアドレスビットが示していれば、アドレスは有効であり、調停が必要である。
【００５９】
調停プロトコル回路８０２はまた、第２のタイプの衝突も検出し得る。場合によっては、MPUアドレス値の値に拘らず衝突が発生する。２つのプロセッサが同一サイクル中に書込みバッファまたはフィルバッファにアクセスしようとすると、衝突が発生する。このような場合には２つのMPUアドレス値を比較する必要はない。代わりに、調停プロトコル回路８０２は、各プロセッサユニットからトランザクション型インジケータを受け取る。複数のプロセッサユニットが同一サイクル中に書込みバッファまたはフィルバッファにアクセスしようとしたことをトランザクション型インジケータが示す場合には、MPUアドレス値に拘らず衝突が発生した。
【００６０】
衝突発生の決定の後で、調停ポリシー回路は、どのプロセッサが要求されたアクセスを行うことになるのかに関する決定を行う。どのプロセッサが要求されたアクセスを受け取ることになるかを決定するための、調停プロトコル回路８０２の好適実施例において実行されるデフォルト調停プロトコルについては、以下に更に詳述する。どのプロセッサが要求されたアクセスを行うことになるのかを決定した後で、調停プロトコル回路８０２は、適用可能なサイクル中にどのプロセッサの完了していないアクセスが優先されることになるのかをおのおの表すような２ビット信号「prefer0」及び「prefer1」を生成する。両信号が同時にセットされることがないようにするために、prefer0はprefer1の論理補数であり、逆もまた同じであるように設計される。優先MPUの値は、非優先MPUの値の逆である。「prefer0」及び「prefer1」インジケータは、次の反復のために調停プロトコル回路８０２に保存され、次の衝突ではどのプロセッサユニットが優先されるべきかを決定するのに役立つ。調停プロトコル回路８０２は、「prefer0」及び「prefer1」信号をリトライ信号ジェネレータ８０４へ供給する。
【００６１】
リトライ信号ジェネレータ８０４は、インジケータの値に基づき信号「retry0」及び「retry1」を生成する。MPUの要求されたアクセスが適用可能サイクルで遂行されることになることをMPUに対する「優先」インジケータが示していれば、リトライは必要ではなく、リトライ信号ジェネレータ８０４は適切な「優先」インジケータによりそのように表示することになる。対照的に、リトライ信号ジェネレータ８０４は、リトライが必要な非優先MPUへの「リトライ」インジケータの値を示す。リトライが必要であるという表示は、データキャッシュユニット１０２アクセスに応じて戻ってきたデータを無視し、ロードまたはストアアクセスをリトライするように非優先プロセッサユニットに告知する。
【００６２】
調停プロトコルに関して、本発明は、調停プロトコル回路８０２において、フィルバッファ２０８へのストア衝突のためのデフォルト調停プロトコル、共有ライトバックバッファ２１０へのストア衝突のための調停プロトコル、ロード衝突のための調停プロトコル及びロード／ストア衝突のための調停プロトコルを実行する。調停プロトコル回路８０２は、各プロセッサユニット１０４、１０６から調停回路８００が受け取ったトランザクション型インジケータの値に基づくポリシーの１つを実行する。これらのデフォルトポリシーは、以下に述べるが、最後の衝突に非優先プロセッサユニットを優先するとは限らないので、厳格でない「フェアネス」ポリシーである。代わりに、調停プロトコル回路８０２は通常、他のプロセッサユニットよりも非優先であることが多いプロセッサユニットを優先しようとする（ロードが常にストアに優先されることは除く）。この優先は、繰返し選択パターンを実行することにより実施される。各プロセッサユニットは、所定の回数の逐次衝突中に優先される。以下に述べるデフォルトポリシーはプログラム可能であり、従って、デフォルトポリシーを調整し、厳格なフェアネスポリシーを実行し、或いは他の任意の好適な調停プロトコルを実行するように、デフォルトポリシーを変えることができる。
【００６３】
調停回路８００は、複数のプロセッサユニットにより同一サイクル中にデータキャッシュユニット１０２の同一アドレス空間からロードしようとする調停プロトコルを有する。このような場合、調停プロトコル回路８０２は、第１プロセッサユニット１０４が所定の回数（M回）の逐次衝突で所望のアドレス空間でアクセスし、第２プロセッサユニット１０６が所定の回数（N回）の逐次的に続く衝突で所望のアドレス空間でアクセスすることを可能にする。好適実施例では、第１プロセッサユニットは第１及び第２逐次衝突（即ちM=2）で所望のアドレス空間でアクセスを受け取り、第２プロセッサユニットは第３及び第４逐次衝突（即ちN=2）で所望のアドレス空間でアクセスを得る。第１及び第２プロセッサユニットによりデータキャッシュユニット１０２の同一アドレス空間からロードするという第１及び第２の同時の試みにおいて、第１プロセッサユニット１０４は要求されたデータをロードすることを許容される。リトライジェネレータ８０４は「retry1」信号をMPU1に供給し、アクセスをリトライし、データキャッシュユニットの完了していないアクセスに応じて戻ったデータを無視するようにMPU1に知らせる。第１プロセッサユニット１０４及び第２プロセッサユニット１０６によりデータキャッシュユニット１０２の同一アドレス空間からロードするという第３及び第４の衝突の試みに逐次的に続いて、第２プロセッサユニット１０６が要求されたデータをロードすることを可能にし、リトライジェネレータ８０４は「retry0」信号を第１プロセッサユニット１０４に供給し、アクセスをリトライするように、またデータキャッシュユニットの干渉していないアクセスに応じて戻ったデータを無視するように、第１プロセッサユニット１０４に知らせる。
【００６４】
調停回路８００は、フィルバッファ２０８のデータレジスタへのストアに関与する衝突を決定する調停プロトコルも有する。同一サイクル中にメインメモリ１０８がフィルバッファ２０８のデータレジスタにデータを書き込むように第１プロセッサユニット１０４及び第２プロセッサユニット１０６の両者が要求する場合には、調停プロトコルはN回の逐次衝突で第１プロセッサユニットを遂行し、続くM回の逐次衝突で第２プロセッサユニット１０６を遂行する。繰り返すが、好適実施例ではM及びNは２に等しい。例えば、第１及び第２プロセッサユニットによりフィルバッファ２０８のデータレジスタへの書込みを行うという第１及び第２衝突要求において、第１プロセッサユニット１０４による要求が許容される。リトライジェネレータ８０４は、「retry1」信号を第２プロセッサユニット１０６に供給し、第２プロセッサユニット１０６に書込みをリトライするように知らせる。第１プロセッサユニット１０４及び第２プロセッサユニット１０６によりフィルバッファ２０８のデータレジスタへの書込みを行うという逐次的に続く第３及び第４の衝突要求において、第２プロセッサユニット１０６による要求が許容され、リトライジェネレータ８０４は「retry0」信号を第１プロセッサユニット１０４に供給し、第１プロセッサユニット１０４に書込みをリトライするように知らせる。
【００６５】
調停回路８００は、共有ライトバックバッファ２１０へのストアに関与する衝突を決定する調停プロトコルも有する。MPU0及びMPU1がキャッシュミスのトリガとなり、ダーティ候補をライトバックバッファ２１０にストアすることを要求する場合には、フェアネスプロトコルはM回の逐次衝突で第１プロセッサユニット１０４を遂行し、続くN回の逐次衝突で第２プロセッサユニット１０６を遂行する。好適実施例では、M及びNは２に等しい。例えば、第１プロセッサユニット１０４及び第２プロセッサユニット１０６によりダーティ候補を共有ライトバックバッファ２１０にストアするという第１及び第２の衝突要求において、第１プロセッサユニット１０４のダーティ候補がストアされる。リトライジェネレータ８０４は、「retry1」信号をMPU1に供給し、第２プロセッサユニット１０６にストレージ要求をリトライするように知らせる。逐次的に続く第１プロセッサユニット１０４及び第２プロセッサユニット１０６による、ダーティ候補を共有ライトバックバッファ２１０にストアするという第３及び第４の衝突要求において、第２プロセッサユニット１０６のダーティ候補がストアされる。リトライジェネレータ８０４は、「retry0」信号を第１プロセッサユニット１０４に供給し、第１プロセッサユニット１０４にストレージ要求をリトライするように知らせる。
【００６６】
第１プロセッサユニット１０４及び第２プロセッサユニット１０６が共に、同一サイクル中に、共有ライトバックバッファ２１０、フィルバッファ２０８、またはデータキャッシュユニット１０２のその他の位置の同一位置にストア及びロードしようとするような例もある。同一位置で同時にロード及びストア動作を実行することはできない。このような場合には、ストア動作よりもロード動作が選択され、ストア動作を要求するプロセッサユニットは、リトライジェネレータ８０４が生成する「リトライ」信号によりリトライするように告げられることになる。ロード動作は、ストア動作よりもかなり頻繁に発生する。従って、ストア動作よりロード動作を選択してデータキャッシュユニット１０２の動作における遅延を少なくする。
【００６７】
その他の実施例
本発明の上記実施例は、単なる例示であり、限定的なものではない。広範な見地において本発明から逸脱することなく種々の改変及び変更が許容されることは、当業者にとって明らかであろう。
【００６８】
例えば、フィルバッファ及びデータアレイは、開示した特定の実施例より多いまたは少ない量のデータをストアすることができる。また、例えばより多くのメディアプロセッサユニットが共有してデータキャッシュユニットを使用し得る。また、例えばここで述べた接続は例示的なものであり、システム１００内の他の接続または他のサイズの接続を制限するものではない。
【図面の簡単な説明】
【図１】  本発明の一実施例によるコンピュータシステムを示したものである。
【図２】  図１のコンピュータシステムのデータキャッシュユニットのブロック線図である。
【図３】  サンプルステータスワードを示すものである。
【図４】  図２のデータキャッシュユニットの共有ライトバックバッファのブロック線図である。
【図５】  図２のデータキャッシュユニットの選択回路のブロック線図である。
【図６】  図２のデータキャッシュユニットのデータアレイの２つの論理バンクである。
【図７】  キャッシュ置き換え動作の一実施例である。
【図８】  調停回路の一実施例である。
【図１】
0004714396.tif 000002
【図２】
0004714396.tif 000003
【図３】
0004714396.tif 000004
【図４】
0004714396.tif 000005
【図５】
0004714396.tif 000006
【図６】
0004714396.tif 000007
【図７】
0004714396.tif 000008
【図８】
0004714396.tif 000009