(57)【要約】【課題】  欠陥を有するメモリセルの数が増加しても、キャッシュメモリを適切に動作させることが可能なキャッシュメモリを有する装置を提供する。【解決手段】  ｎウェイのセットアソシエイティブキャッシュとして組織化されたキャッシュエントリ230と、これらキャッシュエントリのうち、データを置換するための１つの第１のキャッシュエントリを選択する置換管理装置290と、を具備し、置換管理装置290は、欠陥を有するキャッシュエントリを識別し、前記第１のキャッシュエントリとして前記欠陥を有するキャッシュエントリの選択を禁止する。【選択図】      図２
2007018514.tif 000002
【特許請求の範囲】
【請求項１】
ｎウェイのセットアソシエイティブキャッシュとして組織化されている複数のキャッシュエントリと、
前記キャッシュエントリのうち、データを置換するための、１つの第１のキャッシュエントリを選択するように構成されている置換管理装置と、を具備し、
前記置換管理装置は、欠陥を有するキャッシュエントリを識別し、前記第１のキャッシュエントリとして前記欠陥を有するキャッシュエントリの選択を禁止するように構成されていることを特徴とするキャッシュメモリを有する装置。
【請求項２】
キャッシュアクセスに関連するインデックスにしたがって、キャッシュエントリのｎ個のセットのそれぞれから、１つのキャッシュエントリを選択するように構成されている回路と、
キャッシュエントリの１以上の前記ｎ個のセットから、前記キャッシュエントリを選択する前に、前記インデックスを変換するように構成されているインデックス変換回路と、を、さらに具備することを特徴とする請求項１に記載のキャッシュメモリを有する装置。
【請求項３】
ｎ−ウェイのセットアソシエイティブキャッシュを提供し、
キャッシュエントリのｎ個のセットのそれぞれにおける、キャッシュエントリにインデックスを行い、
前記インデックスされたキャッシュエントリに対するキャッシュアクセスがミスであったとき、
前記キャッシュアクセスがミスであったキャッシュエントリに記憶されたデータを、前記キャッシュミスに関連するデータで置換するために、前記インデックスされたキャッシュエントリの一つを選び、前記欠陥を有するキャッシュエントリの選択を禁止することを特徴とする欠陥キャッシュエントリの選択禁止方法。
【請求項４】
キャッシュエントリのｎ個のセットのそれぞれにおける、前記キャッシュエントリにインデックスする前に、前記キャッシュミスに関連するインデックスを変換すること、をさらに含むことを特徴とする請求項３に記載の欠陥キャッシュエントリの選択禁止方法。
【請求項５】
キャッシュミスに関連するデータが記憶されているデータを置換するために、ｎ−ウェイのセットアソシエイティブキャッシュ中のｎ個のキャッシュエントリの１つを選択するように構成され、データを置換するためｎ個のキャッシュエントリのうちの、欠陥を有するキャッシュエントリを選択することを禁止するように構成されていることを特徴とするキャッシュ置換管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメモリシステムに関し、特に多数の欠陥メモリセルが存在するにもかかわらず、メモリを、適切に動作させるためのシステム、装置及び方法に関する。
【背景技術】
【０００２】
デジタル回路は複雑さを増している。これらの回路の１つが数百万のトランジスタから形成されることは、珍しくない。デジタル回路は複雑になってきているので、これらは典型的に、より大きな容量を有するが、回路の１以上のコンポーネントが適切に動作しない危険性も大きくなる。幾つかの例では、単一の不正確なビットが、故障を生じ、回路全体を使用できなくしかねない。これは新型のマイクロプロセッサのような、高価なデジタル回路に当てはまる。それ故、デジタル回路の製造において生じる欠陥数を最小にすることが、非常に重要である。
【０００３】
デジタル回路に存在する欠陥数を最小にするために、多くの努力がそそがれたが、事実上、全ての欠陥を除去することは不可能である。結果として、製造プロセス中に生じる欠陥数を最小にするだけではなく、これらの欠陥が存在しても、デジタル回路が適切に動作することを可能にする機構を利用することが、重要である。
【０００４】
メモリシステムは、１以上の欠陥メモリセルを有するにもかかわらず、正常に動作するように設計されることのできるシステムの一例を与えている。メモリアレイは多数の、同一のメモリセルを含んでおり、これらはそれぞれ、単一のデータビットを記憶できる。これらのメモリセルの１セットは、メモリアレイ内に特有のアドレスを有する、データのブロック（例えば８ビットのバイトまたは３２ビットのワード）を記憶できる。アレイ中の単一のメモリセルが、欠陥を有するならば、その欠陥セルを含んでいる、アレイのアドレスに記憶されているデータは、破壊され、このデータを使用するプログラムは、エラーのある結果を発生する可能性がある。しかしながら、メモリセルは機能的に同一であるので、適切に動作するメモリセルを、欠陥を有するメモリセルと置換するための、機構が設けられることができる。
【０００５】
通常、このメモリの置換は、メモリセルの欠陥を有する行または列が、メモリアレイ中に設けられた冗長な行または列によって、機能的に置換される、ライン−置換冗長機構を使用して行われる。幾つかのシステムでは、単一の冗長な行または列が存在するが、より最近のシステムでは、複数の冗長な行または列が存在する。メモリアレイの特定の行または列が、欠陥を有していることが決定されたならば、そのメモリアレイに結合されたメモリ管理回路は、欠陥を有する行または列の代わりに、冗長な行または列をアクセスするように構成される。換言すると、アドレスの変換は、メモリアレイの単一の行／列に対して効率的に行われ、それによって欠陥を有する行／列にアクセスしようとするとき、このアクセスは冗長な行／列へ再指向される。
【０００６】
通常のライン−置換の冗長機構は、欠陥が少数であれば、メモリアレイの使用を可能にするのに有効であるが、この機構は幾つかの欠点を有している。例えば、典型的に、１または幾つかの置換行／列だけが、欠陥を有する行／列を置換するために利用可能である。付加的な置換行／列を設けることは、特に、プロセッサと同一のチップ上に形成されるキャッシュメモリの場合では、非常に高価になる。キャッシュメモリのサイズが増加すると、メモリセルが欠陥を有する潜在性は同様に増加するが、潜在的に増加する欠陥に適応するために、それに応じてライン置換機構を拡大することは困難である。
【特許文献１】米国特許第６,４１８,５１５号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
それ故、潜在的に欠陥を有するメモリセルの数を増加するにもかかわらず、メモリシステム、特にキャッシュメモリが、適切に動作することを可能にするための、改良されたシステム及び方法を提供し、それによって対応する装置の良品率を増加することが望ましい。
【０００８】
この発明は、潜在的に欠陥を有するメモリセルの数を増加するにもかかわらず、メモリシステム、特にキャッシュメモリが適切に動作することを可能にするキャッシュメモリを有する装置、欠陥キャッシュエントリの選択禁止方法、及びキャッシュ置換管理装置を提供する。
【課題を解決するための手段】
【０００９】
この発明の第１態様に係るキャッシュメモリを有する装置は、ｎウェイのセットアソシエイティブキャッシュとして組織化されている複数のキャッシュエントリと、前記キャッシュエントリのうち、データを置換するための、１つの第１のキャッシュエントリを選択するように構成されている置換管理装置と、を具備する。そして、前記置換管理装置は、欠陥を有するキャッシュエントリを識別し、前記第１のキャッシュエントリとして前記欠陥を有するキャッシュエントリの選択を禁止するように構成される。
【００１０】
この発明の第２態様に係る欠陥キャッシュエントリの選択禁止方法は、ｎ−ウェイのセットアソシエイティブキャッシュを提供し、キャッシュエントリのｎ個のセットのそれぞれにおける、キャッシュエントリにインデックスを行い、前記インデックスされたキャッシュエントリに対するキャッシュアクセスがミスであったとき、前記キャッシュアクセスがミスであったキャッシュエントリに記憶されたデータを、前記キャッシュミスに関連するデータで置換するために、前記インデックスされたキャッシュエントリの一つを選び、前記欠陥を有するキャッシュエントリの選択を禁止する。
【００１１】
この発明の第３態様に係るキャッシュ置換管理装置は、キャッシュミスに関連するデータが記憶されているデータを置換するために、ｎ−ウェイのセットアソシエイティブキャッシュ中のｎ個のキャッシュエントリの１つを選択するように構成され、データを置換するためｎ個のキャッシュエントリのうちの、欠陥を有するキャッシュエントリを選択することを禁止するように構成される。
【発明の効果】
【００１２】
この発明によれば、潜在的に欠陥を有するメモリセルの数を増加するにもかかわらず、メモリシステム、特にキャッシュメモリが適切に動作することを可能にするキャッシュメモリを有する装置、欠陥キャッシュエントリの選択禁止方法、及びキャッシュ置換管理装置を提供できる。
【発明を実施するための最良の形態】
【００１３】
先に概要を説明した１以上の問題は、本発明の種々の実施形態によって解決されよう。広義では、本発明はキャッシュメモリを組込んだ、装置の良品率を増加するための、システム及び方法を含んでいる。これらのシステム及び方法は、セットアソシエイティブキャッシュメモリを構成することを含んでおり、それにおいては、欠陥を含むキャッシュエントリの使用は、選択的に回避される。
【００１４】
この発明の一実施形態では、ｎ−ウェイのセットアソシエイティブキャッシュとして組織化される。キャッシュ置換管理装置は、ｎ個の可能なエントリデータのうちのいずれが記憶されるか、を決定する。キャッシュ置換管理装置は、そのエントリを、新しいデータに対する目的地エントリとして選択するか否かを、決定するとき、各キャッシュエントリが欠陥を有するか否かについて考慮するように構成されている。
【００１５】
一実施形態では、キャッシュ置換管理装置は、新しいデータを記憶するキャッシュエントリの選択に際して、「ＬＲＵ（least-recently-used）」の原則を実行する。キャッシュ置換管理装置は、任意の欠陥を有するエントリを、これらが最も、最近使われたらデータを保持するかのように扱い、それによって欠陥を有するエントリを、新しいデータの目的地として、選択することを避ける。
【００１６】
一実施形態では、キャッシュは、キャッシュエントリの各セットへインデックスする前に、インデックスの変換を行い、それによってインデックス間で、欠陥を有するエントリを、効率的に再分配する。
【００１７】
一実施形態は、データを記憶するキャッシュエントリを１つ選択するように構成された置換管理装置を有している、ｎ−ウェイのセットアソシエイティブキャッシュを具備している。置換管理装置は、欠陥を有するキャッシュエントリを識別し、欠陥を有するキャッシュエントリの選択を禁止するように構成されている。エントリの欠陥状態は、各エントリに関連する状態情報によって決定される。
【００１８】
一実施形態では、置換管理装置は、「ＬＲＵ」の原則を実行し、欠陥を有するエントリを、これらが最も、最近使われたたエントリであるとして識別するように構成されている。一実施形態では、キャッシュは、そのキャッシュを使用するプロセッサと同一の集積回路チップ上に構成される。一実施形態では、キャッシュは、キャッシュエントリにおける異なるセット中から、対応するエントリを選択する前に、インデックスを変換するように構成された回路を含んでいる。そのインデックス変換回路は、キャッシュエントリの異なるセットに対して異なったインデックス変換を行い、またはキャッシュエントリの幾つかのセットに対しては、変換を行わなくてもよい。
【００１９】
別の実施形態は、キャッシュで実行される方法を含んでおり、この方法は、
キャッシュ書込みリクエストを受信し、
キャッシュエントリのｎ個のセットのそれぞれにおける、キャッシュエントリにインデックスし、
インデックスされたキャッシュエントリから、前記キャッシュ書込みリクエストに関連するデータを記憶するインデックスされたキャッシュエントリを１つ選択する、工程を含んでおり、
その選択において、欠陥を有するキャッシュエントリの選択は、禁止される。欠陥を有するキャッシュエントリは、そのエントリに関連する状態情報に基づいて、識別されることができる。データを書込むためのキャッシュエントリの選択は、「ＬＲＵ」の原則にしたがうことができる。この場合、欠陥を有するキャッシュエントリは、それらの選択を禁止するために、「最も、最近使われた」エントリとして識別される。一実施形態では、そのインデックス値は、キャッシュエントリの１以上の異なるセットへ、インデックスされるように使用される前に、変換されることができる。
【００２０】
さらに別の実施形態は、セットアソシエイティブキャッシュと関連して使用するための、置換管理装置を備えている。この置換管理装置は、欠陥を有するキャッシュエントリを識別し（例えば、各エントリに関連する状態情報を使用し）、欠陥を有するキャッシュエントリのいずれの選択も禁止するように構成される。置換管理装置は、例えば、「ＬＲＵ」の原則を実行し、欠陥を有するエントリは、それらの選択を禁止するために、最も、最近使われたエントリとして、識別されることができる。置換管理装置は、キャッシュエントリの異なるセットに対して、異なるインデックス変換を選択的に行うように構成されているインデックス変換回路を含むことができる。
【００２１】
多数の付加的な実施形態もまた可能である。
【００２２】
本発明のその他の目的および利点は、以下の詳細な説明を読み、添付図面を参照するときさらに明瞭になるであろう。
【００２３】
本発明は種々の変形および別の形態が可能であるが、その特定の実施形態を図面に例示し詳細な説明によって示す。このような図面および詳細な説明は、記載された特定の実施形態に本発明を限定する意図はないことを理解すべきである。この開示は、特許請求の範囲に規定されている本発明の技術的範囲内に含まれる全ての変形、等価物、置換をカバーすることを意図している。
【００２４】
本発明の１以上の好ましい実施形態を以下説明する。以下説明するこれらおよび任意の他の実施形態は例示であり、本発明を限定するものではなく、本発明の例示を意図していることに注意すべきである。
【００２５】
概説すると、本発明は、セットアソシエイティブキャッシュメモリを構成する、システム及び方法を含んでおり、ここで欠陥を含むキャッシュエントリの使用は、選択的に防止される。
【００２６】
一実施形態では、プロセッサは、そのプロセッサと同一の集積回路チップ上のキャッシュメモリ（ここでは単にキャッシュとも呼んでいる）を備えている。キャッシュメモリは、プロセッサによって近い将来に使用される可能性のあるデータ（例えば最近アクセスされたデータ、或いは先取りされたデータ）を記憶するために使用される。キャッシュメモリに記憶されているデータは、主メモリに記憶されているデータよりも、迅速に、プロセッサによってアクセスされることができ、したがって、プロセッサの効率を増加する。キャッシュメモリは、欠陥を有する（故障した）１以上のエントリを含む可能性があるので、他のエントリの使用を可能にしながら、欠陥を有するエントリの使用を阻止するための機構が設けられる。
【００２７】
一実施形態では、キャッシュメモリは、セット−連想方式で組織される。換言すると、キャッシュエントリはセットにグループ化され、ここでは特定のセット中の各エントリは、他のセットのそれぞれからの対応するエントリと関連付けられる。キャッシュ中に記憶されることのできるデータの各ピースはその後、キャッシュ中の幾つかのエントリのうちの１つ（各セットから１つ）に記憶されることができる。キャッシュ置換管理装置（置換管理装置）は、何れの可能なエントリがデータを実際に記憶するかを決定する。この実施形態では、キャッシュ置換管理装置は、そのエントリを、新しいデータに対する目的地エントリとして、選択するか否かを決定するとき、各キャッシュエントリが欠陥を有するか否かについて考慮するように構成されている。
【００２８】
一実施形態では、キャッシュ置換管理装置は、新しいデータを記憶するキャッシュエントリの選択に際して、「ＬＲＵ：least-recently-used（最近、最も使われていないもの）」原則を実行する。この原則により、キャッシュ置換管理装置は、どの潜在的な目的地エントリが、「使用されたのが最も古い」データを保持しているかを決定し、このエントリを、新しいデータを記憶する目的地として選択する。いずれのエントリが、「使用されたのが最も古い」データを保持するのかを決定する際に、キャッシュ置換管理装置は、何等かの欠陥を有するエントリを、これらが最も最近使用されたデータを保持しているかのように扱う。このようにして、キャッシュ置換管理装置は、（欠陥を有するエントリが「使用されたのが最も古い」データを保持するものと決定されることはないので）新しいデータを記憶するために、欠陥を有するエントリを選択することを阻止する。
【００２９】
一実施形態では、アドレス変換機構がキャッシュ中に構成される。アドレス変換機構は、必要ならば、キャッシュエントリの各セットに対して、別々に与えられる。データのピースを潜在的に記憶しているキャッシュエントリのグループが、２以上の単一の欠陥を有するエントリを含むならば、アドレス変換機構は、キャッシュエントリの１以上のセットに適用されることができ、それによってエントリを効率的に“シャッフル”する。これは欠陥を有するエントリを再分配する目的であり、したがって、欠陥を有するエントリを予め多数、含んでいたグループは、より少ない欠陥を有するエントリを含む（例えば１）ようにされる。単一のグループ中の、欠陥を有するエントリ数を減少することによって、新しく記憶されるデータの余地を作るために、有効なデータがキャッシュから破棄される危険性を減少し、それに対応して、キャッシュの性能を増加する。
【００３０】
本発明の開示は、主として、キャッシュメモリがプロセッサチップ中に統合されている、一実施形態に焦点を置いている。これは図１に概略的に示されている。図１は、プロセッサ120と、キャッシュメモリ130と、主メモリ140との関係を示す機能ブロック図である。プロセッサ120とキャッシュメモリ130は、同じ集積回路チップ110上に構成されている。キャッシュメモリ130と主メモリ140は、プロセッサ120によって使用されるデータを記憶するための階層メモリシステムを形成している。
【００３１】
典型的に、データがプロセッサ120により必要とされるとき、このデータはメモリシステムからリクエストされる。このデータリクエストを受信するとき、メモリシステムは最初に、そのデータがキャッシュメモリ130に記憶されているか否かを決定する。それはこのメモリがプロセッサに対してさらに近接しており、そこに記憶されているデータが、主メモリ140からよりも迅速に検索されることができるためである。データがキャッシュメモリ130に記憶されているならば、そのデータはキャッシュメモリ130から検索され、プロセッサ120へ戻される。キャッシュメモリ130がそのデータを保持していないならば、そのリクエストは主メモリ140へ転送され、その主メモリ140から、データが検索され、プロセッサへ戻される。典型的に、主メモリ140から検索されたデータは、プロセッサ120へ戻されるとき、キャッシュメモリ130に記憶される。
【００３２】
キャッシュメモリは種々の方法で組織化されることができる。例えば、１つの簡単なタイプのキャッシュでは、主メモリのアドレスはそのキャッシュ中の特有のアドレスへマップされる。換言すると、主メモリ中の特定のアドレスに記憶されているデータは、そのキャッシュ中の単一の、対応する位置（エントリ）にのみ記憶される。この構造は幾つかの欠点を有する。例えば、キャッシュメモリは主メモリよりも小さいので、主メモリ中の多数の異なるアドレスは、そのキャッシュ中の単一位置へマップされる。その結果として、プロセッサにより使用されるデータが、主メモリ中のこれらのアドレスのうちの１つからのデータであるときはいつでも、キャッシュに記憶されることのできるこれらの他のアドレスのうちの１つに対応するデータは、さらに最近使用されたデータによって排除され、プロセッサにより使用されるためにキャッシュではもはや利用可能ではない。さらに、キャッシュメモリ中のエントリの１つに欠陥があるならば、通常のライン置換機構が構成されなければ、主メモリ中の対応するアドレスからのデータを記憶するための場所は、キャッシュにはもはや存在しない。
【００３３】
本発明の実施形態は、異なるタイプのキャッシュ組織を使用し、セットアソシエイティブキャッシュと呼ばれる。セットアソシエイティブキャッシュでは、キャッシュエントリは多数のセットで組織される。そのセットの１つにおける各エントリは、各他のセットの対応するエントリと関連付けられる。例えば、４−ウェイ、セットアソシエイティブキャッシュでは、キャッシュエントリは４つのセットに組織化され、第１のセットの各エントリでは、第２のセット中に対応するエントリと、第３のセット中に対応するエントリと、第４のセット中に対応するエントリが存在する。その後、主メモリ中の各アドレスは、単一のキャッシュエントリに対してではなく、キャッシュエントリのこれらのグループの１つに対して、マップされる。
【００３４】
セットアソシエイティブキャッシュは、先に説明した簡単なキャッシュよりも優れた幾つかの利点を有することができる。例えば、主メモリ中の第１のアドレスからのデータが、キャッシュエントリの特定のグループに記憶されるならば、主メモリ中の第２のアドレスからのデータも、第１のアドレスからのデータを必然的に排除せずに、キャッシュエントリのその同一のグループに記憶されることができる。グループ中のキャッシュエントリの１つに、データを重ね書きすることが必要ならば、（以下詳細に説明するように、幾つかの予め定められたアルゴリズムにしたがって）、キャッシュは、エントリのグループに記憶されるいずれのデータが最も有効性がないか、について決定を行い、最も有効性のない情報に重ね書きする。別の利点は、グループ中のキャッシュエントリの１つに欠陥があるときでさえも、主メモリからの対応するデータを記憶することのできるエントリが他に存在することである。
【００３５】
図２を参照すると、図面は、一実施形態による、セットアソシエイティブキャッシュの構造を示している。キャッシュ200は４−ウェイ、セットアソシエイティブキャッシュである。このキャッシュエントリは４つのセット、221-224に組織化されている。各セットは２５６個のキャッシュエントリ（例えば230）を有する。各キャッシュエントリは３つの部分、即ち制御フィールド（例えば231）と、タグ（例えば232）と、データ（例えば233）とを有している。
【００３６】
この実施形態では、各エントリの制御フィールドは、エントリに関連する状態を識別するために使用される。通常、各エントリは、３つの可能な状態、即ち無効、排他的、又は共有のうち、１つを有する。本発明の実施形態は第４の状態、即ち故障に対しても与えられる。これについて以下さらに詳細に説明する。各エントリに記憶されているデータは、実際には、主メモリの特定位置における、既に記憶されているデータのコピーであるか、または記憶されているプロセス中にある。したがって、ここで使用されている“データのアドレス”は、データを記憶するか、データを記憶するであろう主メモリ中の、アドレスを指している。各エントリ中のタグは、そのエントリに記憶されているデータのアドレスの一部分からなる。図２に示されているように、タグはアドレスのビット10:31からなる。
【００３７】
キャッシュエントリの各セットは、アドレス210を受信するために、結合されている。アドレス210は、プロセッサによりアクセスされるデータアドレスである。アドレス210のビットの第１のセット（ビット10:31）はタグとして使用される。書込み動作中、このタグは、キャッシュエントリの中の、選択された１つに記憶される。読取動作中、このタグは、読取られるデータがキャッシュエントリの１つに記憶されているか否かを決定する比較目的のために、使用される。アドレス210のビットの第２のセットは、キャッシュエントリの各セット（221-224）へのインデックスとして、使用される。各セットは２５６個のキャッシュエントリを含んでいるので、８つのビット（ビット2:9）は、エントリのセットへインデックスすることを必要とされる。アドレス210の最後の２つのビット（ビット0:1）は、キャッシュシステムにより使用されない。インデックスに対して、ビット0:7の代わりに、ビット2:9を使用することによって、そのインデックスは、データの単一バイトではなく、データの４バイトブロックを指す。
【００３８】
キャッシュエントリの各セット（221-224）は、対応する比較器（241-244）および対応するＡＮＤゲート（251-254）へ結合される。各比較器241-244は、アドレス210のタグ部分を受けるように結合される。各比較器241-244はまた、キャッシュエントリの対応するセット221-224における、選択されたエントリのタグ部分を受取るために結合されている。読取動作中、比較器は、２つのタグを比較し、タグが一致するならば、出力信号を発生する。この出力信号は、対応するＡＮＤゲートに対する入力として与えられる（例えば、比較器241の出力は、ＡＮＤゲート251に対する入力として与えられる）。ＡＮＤゲート（例えば251）はまた、エントリの対応するセット（例えば221）における、選択されたエントリの制御フィールドに対応する信号を受信するように結合されている。選択されたエントリが妥当であるならば、この信号はアサートされる。対応するセット中の、選択されたエントリが妥当であり、このエントリ中に記憶されているタグが、アドレス210のタグ部分に一致するならば、ＡＮＤゲートの出力はそれに従ってアサートされる。
【００３９】
各ＡＮＤゲート251-254の出力は、ＯＲゲート260に対する入力として与えられる。ＡＮＤゲート251-254から受信された任意の信号がアサートされるならば、ＯＲゲート260の出力は同様にアサートされ、キャッシュアクセスがヒットした（即ち、アクセスのターゲットであったデータが、キャッシュ中で見つかった）ことを示す。ＡＮＤゲート251-254から受信された任意の信号がアサートされないならば、ＯＲゲート260の出力はアサートされず、キャッシュアクセスはミスであった（即ち、アクセスのターゲットであったデータが、キャッシュ中で見つからなかった）ことを示す。
【００４０】
各ＡＮＤゲート251-254の出力は、マルチプレクサ270に対する制御入力としても与えられる。ＡＮＤゲート251-254から受信された制御信号に加えて、マルチプレクサ270は、キャッシュエントリの各セット（221-224）からもデータ信号を受信する。さらに厳密には、各セット中の、インデックスされたエントリ中に記憶されているデータは、マルチプレクサ270に対する入力として与えられる。エントリの特定のセットに対応する、ＡＮＤゲートの入力がアサートされたものであるならば、この信号により、マルチプレクサ270は、同じセットのインデックスされたエントリからデータ信号を選択する。このデータ信号は、マルチプレクサ270の出力で与えられる。
【００４１】
図３を参照すると、図２のキャッシュにおける読取動作のプロセスを要約しているフロー図が示されている。図面で示されているように、アドレス210は最初に、キャッシュに与えられる（ブロック305）。アドレス210の一部（即ち、ビット2:9）はその後、キャッシュエントリの各セットへインデックスするために使用される（ブロック310）。その後、アドレス210のタグ部分（即ち、ビット10:31）は、キャッシュエントリの各セットにおける、インデックスされたエントリ中に記憶されたタグと比較される（ブロック315）。キャッシュエントリの各セットにおけるインデックスされたエントリが妥当であるか否か、もまた決定される（ブロック320）。タグの比較と、エントリが妥当であるか否かについての決定は、実際に、図２の実施形態で並行して行われることに注意すべきである。インデックスされたエントリの１つが妥当であり、且つアドレス210に一致するタグを含んでいるならば（ブロック325）、ＯＲゲート260の出力でそれがアサートされ、このエントリに記憶されたデータは、マルチプレクサ270の出力で与えられる（ブロック330）。
【００４２】
インデックスされたエントリの中に、妥当であるものがなく、且つ一致するタグを有するものがないならば、ＯＲゲート260の出力はディアサートされ、マルチプレクサ270の出力は無視される（ブロック335）。リクエストされたデータが、キャッシュ中で見つからなかったので、データはメモリから検索される（ブロック340）。後続してアクセスするため、（少なくとも一時的に）データを利用可能にするために、データはキャッシュ中にも記憶される。図３の方法はそれ故、インデックスされたエントリのうちの１つを選択し（ブロック345）、そのデータを、選択されたエントリへ書込む（ブロック350）ことを含んでいる。さらに詳しく説明すると、エントリの制御フィールドは、エントリの状態を示すように設定され、書込みアドレスのタグ部分は、エントリのタグ部分に記憶され、書込みデータはエントリのデータ部分に記憶される。
【００４３】
図４を参照すると、図２のキャッシュにおける、書込み動作のプロセスを要約しているフロー図が示されている。図面で示されているように、このプロセスは、再度、アドレス210が最初に、キャッシュに与えられて開始している。しかしながら、この例では、アドレスは書込みアドレスである。アドレス210の一部分（ビット2:9）は、キャッシュエントリの各セットへインデックスするために使用される（ブロック410）。次に、アドレス210のタグ部分（10:31）は、キャッシュエントリの各セットにおける、インデックスされたエントリ中に記憶されたタグと比較され（ブロック415）、キャッシュエントリの各セットにおける、インデックスされたエントリが妥当であるか否かが決定される（ブロック420）。説明を反復するが、タグの比較と、妥当性についての決定は、この実施形態では並行して行われる。インデックスされたエントリのうちの１つが妥当であり、且つアドレス210に一致するタグを含んでいるならば（ブロック425）、ＯＲゲート260の出力はアサートされ（ブロック445）、書込みアドレスに対応するデータが、既にキャッシュに記憶されていることを示す。データはそれ故、この同じキャッシュエントリに書込まれる（ブロック450）。
【００４４】
インデックスされたエントリの中に、妥当であるものがなく、且つ一致するタグを有するものがないならば、ＯＲゲート260の出力はディアサートされ（ブロック430）、書込みアドレスに対応する妥当なデータが、キャッシュ中に存在しないことを示す。キャッシュはそれ故、インデックスされたエントリの１つを選択し（ブロック435）、そのデータを、選択されたエントリへ書込み（ブロック440）、この書込み動作は、エントリの状態を示すようにエントリの制御フィールドを設定し、書込みアドレスのタグ部分をエントリのタグ部分中に記憶し、書込みデータをエントリのデータ部分に書込むことを含んでいる。インデックスされたキャッシュエントリの中で、書込みアドレスに関連するデータを既に記憶しているものがないならば、書込み動作のためのデータは、インデックスされたエントリ中の任意の１つに、潜在的に記憶できることに注意すべきである。それ故、データを記憶するためのエントリの中の１つを選択することが必要である。キャッシュエントリの１つの選択は、読取りミス時に、メモリから検索されたデータがキャッシュに記憶されるときと同様の方法で行われる。
【００４５】
先に指摘したように、読取ミスまたは書込みミスのいずれかが生じたときに、データはキャッシュ中に記憶される。キャッシュミスがあったとき、インデックスされたキャッシュエントリには、キャッシュアクセスアドレスに関連するデータを既に記憶しているものがなく、したがってキャッシュアクセスのためのデータは、インデックスされたエントリのうちの任意の１つに潜在的に記憶されることができる。それ故、これらのエントリのいずれが、データを実際に記憶するかを決定することが必要である。一実施形態では、このタスクは、置換管理装置により処理される。図２を再度参照すると、置換管理装置290は、マルチプレクサ280と285に与えられる制御信号を発生する。マルチプレクサ280はアドレス210のタグ部分を受信し、キャッシュエントリの各セットに結合される出力を有している。同様に、マルチプレクサ285は、データ215を受信し、キャッシュエントリの各セットに結合される出力を有している。置換管理装置290から受信された制御信号に基づいて、マルチプレクサ280と285は、それぞれ、タグ及びデータを、インデックスされたキャッシュエントリのうちの選択された１つのキャッシュエントリへ提供する。
【００４６】
別の実施形態は、異なる構造を使用して、同じ機能を実行できることに注意すべきである。例えば、タグ及びデータを、インデックスされたキャッシュエントリの１つだけに選択的に提供するのではなく、この情報が全てのインデックスされたキャッシュエントリに与えられることができ、書込み信号は、インデックスされたキャッシュエントリの１つに選択的に提供されることができ、それによってタグ及びデータは、書込み信号を受信するエントリにのみ記憶される。他の変形も同様に可能である。
【００４７】
置換管理装置290は、インデックスされたキャッシュエントリの１つを、種々の方法により、選択するように構成されることができる。一実施形態では、置換管理装置は、インデックスされたキャッシュエントリの１つを選択する際に、「ＬＲＵ（least-recently-used）」の原則を実行するように構成される。この原則により、置換管理装置は、プロセッサによる「最近、最も使われていない」データを記憶しているキャッシュエントリを選択する。この原則の基礎となる理論は、さらに最近使用されたデータが、プロセッサによって必要とされる可能性がさらに高く、それ故、キャッシュに記憶されている新しいデータが「最近、最も使われていない（したがって必要とされる可能性が少ない）」データを排除するならば、プロセッサの効率が最大にされるという理論である。
【００４８】
通常のキャッシュシステムの置換管理装置は、幾つかの形態の「ＬＲＵ」の原則を広く実行する。場合によっては、この原則の実行は、各キャッシュエントリに記憶されているデータの使用を追跡し、どのくらい最近、そのデータが使用されたかにしたがって、各キャッシュエントリのランクを識別するステップを含んでいる。例えば、特定のキャッシュエントリ中のデータが使用されるとき、そのエントリはランク“１”を割当てられることができる。他のセットの１つにおける同一のインデックスのキャッシュエントリが使用されるときはいつでも、このランクはインクリメントされる。したがって、最近、最も使われたデータを有するキャッシュエントリはランク“１”を有し、最近、２番目に最も使われたデータを有するエントリはランク“２”を有し、最近、３番目に最も使われたデータを有するエントリはランク“３”を有し、最近、最も使われていないデータを有するエントリはランク“４”を有する。その後、いずれのキャッシュエントリが新しいデータを記憶するか、を決定することが必要なときはいつでも、ランク“４”を有するエントリが選択される。
【００４９】
通常、置換管理装置は、欠陥を有するキャッシュエントリの放出をアドレスしない。この放出は、代わりに、前述のライン置換機構のような一般的な機構によってアドレスされる。それ故、キャッシュエントリの中には、欠陥があるものはないことが、キャッシュシステムによって一般的に仮定される。しかしながら、本発明の実施形態では、幾つかのキャッシュエントリが欠陥を有することが仮定され、したがって、これらの欠陥を有するエントリの使用を回避するための機構を提供することが必要である。
【００５０】
一実施形態では、この機構は、「ＬＲＵ」の置換原則の実行に関連して、置換管理装置によって実行される。この実施形態では、欠陥を有するキャッシュエントリが識別され、「ＬＲＵ」データを有するエントリよりも高いランクが割当てられる。例えば、欠陥を有する、キャッシュエントリはランク“１”または“０”を割当てられることができる。置換管理装置はその後、前述の方法と全く同じ方法で（即ち、最大の数値のランクを有するエントリを選択することによって）、インデックスされたキャッシュエントリのうち、新しいデータを記憶するための１つのキャッシュエントリを選択することができる。
【００５１】
一実施形態では、どのくらい最近、各エントリが使用されたかにしたがった、キャッシュエントリの格付けは、ＬＲＵ（最近、最も使われていない）決定回路のセットによって行われる。この実施形態では、１つのＬＲＵ決定回路が各インデックスに対して設けられる。したがって、図２の例示的なキャッシュでは、２５６個のＬＲＵ決定回路が存在する。これらの各回路は、（各セット221-224から１つの）対応するインデックスにおいて４つのキャッシュエントリを考慮し、これらのエントリのうちのいずれが「最近、最も使われていない」かを決定するように構成されている。各ＬＲＵ決定回路は、各エントリで記憶された状態情報にしたがって、対応する４つのエントリのうちのいずれに欠陥があるか否かを決定するように構成されている。状態情報が、特定のエントリに欠陥があることを示したならば、そのエントリは、最も最近使用されたデータを保持するとして、扱われる。
【００５２】
一実施形態では、特定のキャッシュエントリに欠陥があるか否かを示す、状態情報は、エントリの制御フィールド（例えば、図２の項目231）に記憶される。この実施形態では、キャッシュは、マルチプロセッサシステム中の単一プロセッサによって使用されるライトバック（書戻し）キャッシュであり、書込み−無効キャッシュコヒーレンスプロトコルを実行する。各エントリに対する制御フィールドは、エントリの状態の識別に使用され、それは次のうちの何れかであり、即ち、無効、排他的（読取／書込には妥当）、共有（読取のみに妥当）、故障、である。これらの状態、およびその状態間の転移が図５のＡおよびＢで示されている。
【００５３】
図５のＡおよびＢを参照すると、一実施形態による、可能なキャッシュエントリ状態と、これらの状態間の転移とを示している１対の状態図が示されている。図５のＡは、プロセッサからのリクエストに基づいた、転移を有するキャッシュエントリ状態を示しており、図５のＢは、プロセッサバスからのリクエストに基づいた、転移を有する状態を示している。キャッシュエントリが妥当なデータを記憶していない（例えば、パワーアップ時、任意のデータがエントリに記憶される前）ならば、エントリの制御フィールドは、そのエントリの状態が無効であることを示している（510）。データがエントリに記憶されるとき、そのエントリは妥当であり、エントリの状態は排他的（520）または共有（530）である。このキャッシュが、このキャッシュエントリ中にデータを記憶する唯一のキャッシュであるならば、状態は排他的（520）であり、データは、キャッシュエントリに対する読取及び書込みの両動作に対して妥当である。同じデータが同様に、他のキャッシュに記憶されるならば、状態は共有（530）であり、データはキャッシュエントリから妥当に読取られることができるが、（データは更新されなければならず、他のキャッシュも同様なので）書き込まれない。
【００５４】
無効（510）、排他的（520）、共有（530）の状態は、通常のキャッシュシステムで普通に使用される。これらの状態間の転移はよく知られ、理解されており、したがって、ここでは詳細に説明しないで、図面に簡単に示されている。しかしながら、本発明のキャッシュシステムは、キャッシュエントリが故障した状態（540）でも存在しうる点で、通常のシステムとは異なっている。キャッシュ中のエントリが欠陥を有することが決定されたならば（例えばエントリ中のエントリのビットのうちの任意の１つに欠陥があるならば）、エントリの状態は故障である。エントリの欠陥特性は種々の方法で決定され、エントリの状態は、適当な時に“故障”に設定されることができる。したがって、図５のＡおよびＢには、故障状態への転移は示されていない。例えば、キャッシュは、製造プロセスの一部として、欠陥を走査されることができ。システムのブートアップ手順は、欠陥を有するキャッシュエントリの状態を故障状態へ設定することを含むことができる。キャッシュエントリが、故障として識別されると、そのエントリは使用してはならず、故障状態から任意の他の状態への転移は、図面では示されていない。
【００５５】
本発明の機構によって、メモリの製造で生じ得る多数の欠陥にもかかわらず、キャッシュメモリを使用することが可能になる。実際に、この機構によって、多数の欠陥を有するキャッシュメモリを効率的に使用することが潜在的に可能になる。例えば、キャッシュ中の各インデックスに対する１エントリ（キャッシュの４分の１）に欠陥がある場合に、そのキャッシュは依然として、（４ウェイではなく）３ウェイのセットアソシエイティブキャッシュとして、効率的に機能する。この多数の欠陥がキャッシュメモリで生じる可能性は非常に低いが、各インデックスに関連するエントリのうち１つのみに影響するように、生じた任意の欠陥が分配される可能性も非常に低い。代わりに、非常に多数の欠陥が存在するならば、幾つかのインデックスは欠陥を有する、エントリをもたず、一方、他のインデックスは多数の欠陥を有するように、欠陥が分配される可能性がある。
【００５６】
キャッシュメモリが、所定数の故障したエントリを有するならば、同一のインデックスに対応する多数のエントリが故障した場合、その後、各インデックスが単一の故障したエントリだけを有する場合、そのキャッシュの性能はさらに劣化されることに注意すべきである。キャッシュシステムはそれ故、故障したエントリを、異なるインデックス間のキャッシュエントリへ再分配し、それによって単一のインデックスに関連する故障したエントリ数を、最小にするための機構を含むことができる。一実施形態では、この機構は、特定のセット内で、エントリを効率的にシャッフルできる１組のアドレス（インデックス）変換回路を使用して、実行されることができる。
【００５７】
図６を参照すると、一実施形態による、インデックス変換機構を有するセットアソシエイティブキャッシュの構造図が示されている。このキャッシュシステムの構造は、図２のシステムと同一であるが、インデックス変換回路（611-614）がアドレス610と、キャッシュエントリの各セット（621-624）との間に挿入される点が異なっている。この実施形態では、各インデックス変換回路は、１組の制御信号を受信するように構成されており、この制御信号によって、インデックス値の１以上のビットが、キャッシュエントリの対応するセット中へインデックスするために使用される前に、反転される。その結果として、各インデックスは、各セット621-624からの単一のキャッシュエントリと関連されるが、各インデックスに関連された特定のキャッシュエントリは変更されることができる。一実施形態では、インデックスは、アドレス610から受信されたインデックス値の１以上のビットを反転させ、その結果的な値を、キャッシュエントリのセットへインデックスするために使用することによって、変更される。異なるビットは、キャッシュエントリの異なるセットのそれぞれにおいて、反転されることができる。
【００５８】
図７を参照すると、一実施形態による、インデックス変換回路の例示的な構造図が示されている。この実施形態では、インデックス変換回路700は、ｎ個のビットのアドレスのビットを選択的に反転するように構成されている。図６のキャッシュシステムでは、インデックスは８ビットの長さである（それによって、２５６または２８のキャッシュエントリがアドレスされることができる）。以下説明する例では、４ビットのインデックスを使用している。
【００５９】
インデックスＩ［0:7］のビットは、インデックス変換回路に並列で与えられる。各ビットは、そのビットの別々のチャンネルと考慮されることができるものによって、処理される。インデックス変換回路は、ｎ個のビットを処理するように構成されるが、図面では、ビットＩ［0］とＩ［1］とを処理する２つのチャンネルのみが、図面を簡単にするために、明確に示されている。各入力ビット（例えばＩ［0］またはＩ［1］）は、対応する２：１マルチプレクサ（例えばそれぞれ710または711）へ入力される。各ビットはまた、インバータ（例えば、720または721）に与えられ、その出力は、対応するマルチプレクサへ第２の入力として与えられる。制御信号（例えば、Ｃ［0］またはＣ［1］）は、それぞれのマルチプレクサへ与えられ、入力ビット、または反転されたビットのいずれかが選択され、マルチプレクサの出力で変換されたビット（例えば、Ｉ’［0］またはＩ’［1］）として与えられる。変換されたインデックスビットは、その後、キャッシュエントリのそれぞれのセットへインデックスするために使用される。
【００６０】
図８のＡ−Ｃを参照すると、図７のシステムを使用して可能である、幾つかのインデックス変換を示す表のセットを示している。図８のＡは、インデックスの変換がない例を示し、図８のＢは、インデックスが、反転ビットＡ３によって変換されている例を示している。図８のＣは、インデックスが、反転ビットＡ２によって変換されている例を示している。図８のＡ−Ｃの各表は６つの列を含んでいる。第１の列は、１０進法の形態の入力インデックスを含んでいる。最後の列は、１０進法の形態の出力（変換）インデックスを含んでいる。第２乃至第５の列は、変換されたインデックスのビットを含んでいる。
【００６１】
インデックスの変換がない、図８のＡを参照すると、ビットＡ３−Ａ０は変更されていないことが認められる。入力インデックス０−１５はそれ故、それぞれ出力インデックス０−１５を発生する。例えば、入力インデックス１（２進数０００１）は、出力インデックス１（２進数０００１）を発生し、入力インデックス２（２進数００１０）は、出力インデックス２（２進数００１０）を発生する等である。
【００６２】
図８のＢを参照すると、インデックスは、反転ビットＡ３により変換される。その結果として、入力インデックス０−７はそれぞれ、出力インデックス８−１５を発生し、入力インデックス８−１５はそれぞれ、出力インデックス０−７を発生する。例えば、入力インデックス１（２進数０００１）は、出力インデックス９（２進数１００１）を発生し、入力インデックス１０（２進数１０１０）は、出力インデックス２（２進数００１０）を発生する。
【００６３】
図８のＣを参照すると、インデックスは、反転ビットＡ２により変換される。その結果として、入力インデックス０−３はそれぞれ、出力インデックス４−７を発生し、入力インデックス４−７はそれぞれ、出力インデックス０−３を発生し、入力インデックス８−１１はそれぞれ、出力インデックス１２−１５を発生し、入力インデックス１２−１５はそれぞれ、出力インデックス８−１１を発生する。例えば、入力インデックス１（２進数０００１）は、出力インデックス５（２進数０１０１）を発生し、入力インデックス１０（２進数１０１０）は、出力インデックス１４（２進数１１１０）を発生する。
【００６４】
図６のキャッシュシステムで構成されているように、キャッシュエントリの各セットは別々のインデックス変換回路を有し、それによって、そのインデックスに適用される特定のインデックス変換は、エントリのそれぞれの意味で、異なることに注意すべきである。例えば、キャッシュエントリの第１のセットに対してはインデックス変換がなく、キャッシュエントリの第２のセットに対しては第１のインデックス変換、キャッシュエントリの第３のセットに対しては異なるインデックス変換が存在する。インデックス変換はここでは、同一の（変換のない）インデックスに関連する故障したエントリが非常に多く存在しないようにするために使用されるので、キャッシュエントリのセットのうちの１つはインデックス変換回路をもつ必要がないことに注意すべきである。
【００６５】
図９のＡ−Ｂを参照すると、変換されないインデックスのうちの任意の１つと関連する故障したエントリの最大数を減少するために、インデックス変換が有効である状態の一例が示されている。図９のＡは、何等のインデックス変換もない場合の、各インデックスに関連するエントリと、データの記憶に実際に利用可能なエントリの番号とを示している。図９のＢは、各インデックスに関連するエントリと、利用可能なエントリの対応する番号とを示している。各図面の最初の２つの列は、（１０進法の形態の）インデックスと、データの記憶に利用可能なエントリの対応する番号とを示している。その後、キャッシュエントリの４つのセット（セット０−３）のそれぞれに対して、各キャッシュエントリに関連するインデックスと、エントリのデータ記憶に対する利用可能性とが示されている。“Ｘ”は、対応するキャッシュエントリが故障し、データの記憶には利用できないことを示している。
【００６６】
図９のＡは、インデックス変換が、キャッシュエントリの任意のセットに適用される前の状態を示している。インデックス３については、セット０、２、３では、このインデックスを有するエントリは故障しているので、１つのキャッシュエントリだけが利用可能であることが認められる。インデックス８は、データの記憶に対して利用可能な３つのキャッシュエントリを有し、残りのインデックスはそれぞれ４つの有効なエントリを有している。プロセッサが、インデックス３に関連するアドレスを有するデータを記憶しようと試みる都度、このデータは、このエントリが最近使用されたデータを含み、それを近い将来に再度使用する可能性があったとしても、２つの利用可能なエントリ中に記憶される必要があるので、この状態は望ましくない。ただ１つのみ利用可能なキャッシュエントリを有している単一のインデックスをもつよりも、３つの利用可能なエントリを有しているインデックスを多くもつことが好ましい。それ故、キャッシュエントリの１以上のセットに対して、インデックス変換を適用することが望ましい。
【００６７】
図９のＢを参照すると、キャッシュエントリの同じセットに適用されるときの、例示的なインデックス変換が示されている。キャッシュエントリの各セットは、依然として同じ故障したエントリを有するが、インデックス変換によって、これらのエントリの幾つかは、異なるインデックスに関連されることが認められる。この図面で示されているように、キャッシュエントリの第１の２つのセット（セット０とセット１）にはインデックス変換が適用されない。セット２のエントリに関連されるインデックスは、（図８のＣに示されているように）反転ビットＡ２により変換され、セット３のエントリに関連されるインデックスは、（図８のＢに示されているように）反転ビットＡ３により変換される。その結果として、キャッシュに記憶されるデータのアドレスに関連するインデックスが３であるとき、そのデータは、セット１の第４のエントリと、セット２の第８のエントリと、セット３の第１２のエントリとを含む３つの異なるキャッシュエントリのうちの１つに記憶されることができる。セット２および３の第４のエントリはそれぞれ、インデックス７および１１に関連される。それ故、アドレス変換は、インデックス変換に先行する場合のように、１つの利用可能なエントリを有する１つのインデックスおよび、３つの利用可能なエントリとを有する１つのインデックスではなく、３つの利用可能なキャッシュエントリを有する４つのインデックスが存在する状態を生じる。
【００６８】
先に指摘したように、説明した実施形態は、本発明を説明する目的で記載されたものである。上記実施形態において、多数の別の実施形態及び変形が可能であることは、本発明の説明を読むとき、当業者に明白になるであろう。例えば、前述した実施形態は、利用可能なキャッシュエントリのうち、新しいデータの記憶に使用されるキャッシュエントリを選択する際に、「ＬＲＵ」の原則を実行する。別の実施形態では別の原則を使用してもよい。これらの実施形態では、故障したキャッシュエントリは、任意の適切な特徴に関連付けされることができ、この特徴によって、故障したエントリは新しいデータを記憶するために選択されない。例えば置換原則が、（最も、最近ではなくても）最も頻繁にアクセスされるデータを、キャッシュ中に保持することが望ましいという、「アクセスが最少」の原則であるならば、故障したエントリは、（故障したエントリが、実際に任意の妥当データを含んでいなくても）他のキャッシュエントリ中のデータよりも、多数回アクセスされているデータを保持しているとして、識別されることができる。
【００６９】
キャッシュ中の構成である説明した実施形態についての他の変形は、キャッシュエントリのセットにおける異なるメンバで組織されるものである。即ち、キャッシュエントリの４つのセットを有するのではなく、キャッシュは、２ウェイ、８ウェイ、またはより一般的には、ｎウェイのセットアソシエイティブキャッシュであり、ここでｎは１よりも大きい。別の実施形態はまた、前述の方法とは異なる方法で動作するキャッシュで実行されることができる。例えば、前述の実施形態は、マルチプロセッサシステムで構成されるキャッシュに焦点を置いており、それ故、排他的及び共有の両状態を有するが、別の実施形態は、単一の妥当な状態だけを有することのできるユニプロセッサシステムで構成されることができる。別の実施形態のキャッシュは、異なるブロックサイズを有するデータを保持するか、または付加的な制御またはメタデータを記憶するようにも構成されていてもよい。さらに、キャッシュ自体におけるその他の変形もまた可能である。
【００７０】
当業者は情報および信号が任意の種々の異なる技術を使用して表されることができることを理解するであろう。例えば、先の説明を通して参照されることのできるデータ、命令、コマンド、情報、信号、ビット、シンボルは電圧、電流、電磁波、磁界または粒子、光フィールドまたは粒子、或いは任意のそれらの組合せによって表されることができる。
【００７１】
当業者はさらに、ここで開示した実施形態に関連して説明した種々の例示的な論理ブロック、モジュール、回路、アルゴリズムステップが電子ハードウェア、コンピュータソフトウェアまたはその両者の組合せとして構成されてもよいことを認識するであろう。このハードウェアとソフトウェアとの交換が可能であることを明白に示すために、種々の例示的なコンポーネント、ブロック、モジュール、回路、およびステップをそれらの機能に関して一般的に説明した。このような機能がハードウェアまたはソフトウェアのいずれとして構成されるかは特定の応用と、システム全体に課された設計制約にしたがっている。当業者はそれぞれの特定の応用に対して、説明された機能を種々の方法で実行することができるが、このような実行の決定は本発明の技術的範囲からの逸脱するものとして解釈されるべきではない。
【００７２】
ここで開示した実施形態に関して説明した種々の例示的な論理ブロック、モジュールおよび回路は、汎用目的のプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途用集積回路（ＡＳＩＣ）、フィールドプログラム可能なゲートアレイ（ＦＰＧＡ）、またはその他のプログラム可能な論理装置、ディスクリートなゲートまたはトランジスタ論理装置、ディスクリートなハードウェアコンポーネント、或いはここで説明した機能を実行するように設計された任意のその組合せによって構成され、または実行されることができる。汎用目的のプロセッサは任意の通常のプロセッサ、制御装置、マイクロ制御装置、状態マシン等であってもよい。プロセッサはまたコンピュータ装置の組合せ、例えばＤＳＰ、マイクロプロセッサ、複数のマイクロプロセッサ、ＤＳＰコアと連結した１以上のマイクロプロセッサ、或いは任意のその他のこのような構造として構成されることもできる。
【００７３】
ここで開示した実施形態に関連して説明した方法またはアルゴリズムのステップは、直接ハードウェア、プロセッサにより実行されるソフトウェアモジュール、またはその２つの組合わせで実施されることができる。ソフトウェアモジュールはＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、取外し可能なディスク、ＣＤ−ＲＯＭ、または技術で知られているその他の形態の記憶媒体中に存在してもよい。例示的な記憶媒体はプロセッサに結合され、このようなプロセッサは情報を記憶媒体から読出し、そこに情報を書込むことができる。その代りに、記憶媒体はプロセッサに一体化されることもできる。プロセッサおよび記憶媒体は例えばＡＳＩＣ中に存在していてもよい。ＡＳＩＣはユーザ端末に存在してもよい。その代りに、プロセッサおよび記憶媒体はユーザ端末中にディスクリートなコンポーネントとして配置することもできる。
【００７４】
また、上記実施形態は、以下の態様を含む。
【００７５】
（１）  ｎウェイのセットアソシエイティブキャッシュとして組織化されている複数のキャッシュエントリと、
前記キャッシュエントリのうち、データを置換するための、１つの第１のキャッシュエントリを選択するように構成されている置換管理装置と、を具備し、
前記置換管理装置は、欠陥を有するキャッシュエントリを識別し、前記第１のキャッシュエントリとして前記欠陥を有するキャッシュエントリの選択を禁止するように構成されているキャッシュメモリを有する装置。
【００７６】
（２）  （１）の態様に係る装置において、前記キャッシュエントリは、単一の集積回路チップ上に、プロセッサと共に構成される装置。
【００７７】
（３）  （１）の態様に係る装置において、前記置換管理装置は、データを記憶するキャッシュエントリの選択に際して、「ＬＲＵ」の原則を実行するように構成されている装置。
【００７８】
（４）  （３）の態様に係る装置において、置換管理装置は、置換する各エントリを選択するための所望度にしたがって潜在的に選択可能なキャッシュエントリを格付けし、欠陥を有するエントリを置換するのに最も低い所望度として格付けするように構成されている装置。
【００７９】
（５）  （１）の態様に係る装置において、各前記キャッシュエントリは、前記対応するキャッシュエントリが欠陥を有するか否かを示す状態情報を含んでいる装置。
【００８０】
（６）  （１）の態様に係る装置において、キャッシュアクセスに関連するインデックスにしたがって、キャッシュエントリのｎ個のセットのそれぞれから、１つのキャッシュエントリを選択するように構成されている回路と、
キャッシュエントリの１以上の前記ｎ個のセットから、前記キャッシュエントリを選択する前に、前記インデックスを変換するように構成されているインデックス変換回路と、を、さらに具備する装置。
【００８１】
（７）  （６）の態様に係る装置において、前記インデックス変換回路は、前記インデックスの１以上のビットを反転することにより、前記インデックスを変換するように構成されている装置。
【００８２】
（８）  （６）の態様に係る装置において、前記インデックス変換回路は、キャッシュエントリの前記ｎ個のセットの２以上に対して、異なるインデックス変換を行うように構成されている装置。
【００８３】
（９）  （８）の態様に係る装置において、前記インデックス変換回路は、キャッシュエントリの前記ｎ個のセットの１つについて、インデックス変換を行わずにおくように構成されている装置。
【００８４】
（１０）  ｎ−ウェイのセットアソシエイティブキャッシュを提供し、
キャッシュエントリのｎ個のセットのそれぞれにおける、キャッシュエントリにインデックスを行い、
前記インデックスされたキャッシュエントリに対するキャッシュアクセスがミスであったとき、
前記キャッシュアクセスがミスであったキャッシュエントリに記憶されたデータを、前記キャッシュミスに関連するデータで置換するために、前記インデックスされたキャッシュエントリの一つを選び、前記欠陥を有するキャッシュエントリの選択を禁止する欠陥キャッシュエントリの選択禁止方法。
【００８５】
（１１）  （１０）の態様に係る方法において、前記キャッシュアクセスされたキャッシュエントリに記憶されたデータを、前記キャッシュミスに関連するデータで置換するために、前記キャッシュエントリの選択は、「ＬＲＵ」の原則を使用して行われる方法。
【００８６】
（１２）  （１１）の態様に係る方法において、前記キャッシュアクセスされたキャッシュエントリに記憶されたデータを、前記キャッシュミスに関連するデータで置換するためのキャッシュエントリの選択は、置換する各エントリを選択するための所望度にしたがって、潜在的に選択可能なキャッシュエントリを格付けすること、を含み、
欠陥を有するキャッシュエントリの選択の禁止は、欠陥を有するキャッシュエントリを、置換するのに最も低い所望度として格付けすること、を含む方法。
【００８７】
（１３）  （１０）の態様に係る方法において、各キャッシュエントリに関連する状態情報に基づいて、前記インデックスされた各キャッシュエントリが欠陥を有するか否かを決定すること、をさらに含む方法。
【００８８】
（１４）  （１０）の態様に係る方法において、キャッシュエントリのｎ個のセットのそれぞれにおける、前記キャッシュエントリにインデックスする前に、前記キャッシュミスに関連するインデックスを変換すること、をさらに含む方法。
【００８９】
（１５）  （１４）の態様に係る方法において、前記インデックスの変換は、前記インデックスの１以上のビットの反転を含む方法。
【００９０】
（１６）  （１４）の態様に係る方法において、前記インデックスの変換は、キャッシュエントリの前記ｎ個のセットの２以上に対して、異なるインデックス変換を行うこと、を含む方法。
【００９１】
（１７）  （１６）の態様に係る方法において、前記インデックスの変換は、キャッシュエントリの前記ｎ個のセットの１つについて、インデックス変換を行わずにおくこと、を含む方法。
【００９２】
（１８）  キャッシュミスに関連するデータが記憶されているデータを置換するために、ｎ−ウェイのセットアソシエイティブキャッシュ中のｎ個のキャッシュエントリの１つを選択するように構成され、データを置換するためｎ個のキャッシュエントリのうちの、欠陥を有するキャッシュエントリを選択することを禁止するように構成されているキャッシュ置換管理装置。
【００９３】
（１９）  （１８）の態様に係る置換乖離装置において、前記置換管理装置は、置換する各前記ｎ個のキャッシュエントリのそれぞれを選択するために、所望度にしたがって、前記ｎ個のキャッシュエントリを格付けし、前記ｎ個のキャッシュエントリのうちの欠陥を有するキャッシュエントリを、置換するのに最も低い所望度として格付けするように構成される。
【００９４】
（２０）  （１８）の態様に係る置換管理装置において、前記キャッシュミスに関連するインデックスを変換し、前記変換されたインデックスを使用してキャッシュエントリのｎ個のセットのそれぞれにインデックスすることによって、前記ｎ個のキャッシュエントリを選択するように構成される。
【００９５】
本発明により与えられる効果および利点を特定の実施形態に関連して説明した。これらの効果および利点と、行われ、またはさらに明白にされるその他のエレメントまたは限定は、特許請求の範囲に記載された任意または全ての特徴において臨界的な、必要とされる、または基本的な特性として解釈されるべきではない。ここで使用されている用語“具備する”、“具備している”または任意のその他のその変形はこれらの用語にしたがっているエレメントまたは限定を排他的ではなく含んでいるとして解釈されることを意図している。したがって、システム、方法または、１組のエレメントを含むその他の実施形態はこれらのエレメントだけに限定されるのではなく、記載されていない、または請求された実施形態に固有ではないその他のエレメントを含むことができる。
【００９６】
開示された実施形態の前述の説明は、当業者が本発明を構成または使用することを可能にするために行われた。これらの実施形態に対する種々の変形は当業者に容易に明白であり、ここで規定されている一般原理は本発明の技術的範囲を逸脱せずに他の実施形態に適用されることができる。したがって、本発明はここで示されている実施形態に限定されることを意図するものではなく、ここで説明され、特許請求の範囲で挙げられている原理および優れた特徴と一貫する最も広い技術的範囲にしたがうことを意図している。
【図面の簡単な説明】
【００９７】
【図１】一実施形態による、プロセッサと、キャッシュメモリと、主メモリとの関係を示す機能ブロック図。
【図２】一実施形態による、セットアソシエイティブキャッシュの構造を示す図。
【図３】図２のキャッシュにおける読取動作プロセスを要約しているフロー図。
【図４】図２のキャッシュにおける書込み動作プロセスを要約しているフロー図。
【図５】一実施形態による、可能なキャッシュエントリ状態と、これらの状態間の転移とを示している１対の状態図。
【図６】一実施形態による、インデックス変換機構を有するセットアソシエイティブキャッシュの構造を示す図。
【図７】一実施形態による、インデックス変換回路の例示的な構造を示す図。
【図８】図７のシステムを使用して可能な幾つかのインデックス変換を示す表のセット図。
【図９】インデックスが、異なるインデックス間で、故障したエントリの再分配にどのように使用されることができるかを示す１組の表を示す図。
【符号の説明】
【００９８】
２３０…キャッシュエントリ、２９０…置換管理装置
【図１】
2007018514.tif 000003
【図２】
2007018514.tif 000004
【図３】
2007018514.tif 000005
【図４】
2007018514.tif 000006
【図５】
2007018514.tif 000007
【図６】
2007018514.tif 000008
【図７】
2007018514.tif 000009
【図８】
2007018514.tif 000010
【図９】
2007018514.tif 000011