(57)【要約】  キャッシュ・メモリのマッピング・アルゴリズムおよび関連するハードウェアは、各セットがただ１つのキャッシュ・メモリ・チップからのキャッシュ・ラインを含むという方法でキャッシュ・ラインをマップする。連続するディスク・アクセスは、連続するセットにマップされ、これによって格納データを異なるキャッシュ格納チップから同時に取り出すことができる。キャッシュ・ライン割付けのポリシーは、新しいキャッシュ・ラインが適切なセットに動的に挿入され、かつ正確なキャッシュ・メモリ・チップに対応することを保証する。
2007513438.tif 000002
【特許請求の範囲】
【請求項１】
連続するディスク・アクセスを連続するセットにマップするためのキャッシュ・マッピング・アルゴリズムを含むことを特徴とするキャッシュ・メモリ。
【請求項２】
前記連続するセットの第１セットは第１キャッシュ格納チップからデータにアクセスし、第２セットは第２キャッシュ格納チップからデータにアクセスすることを特徴とする請求項１記載のキャッシュ・メモリ。
【請求項３】
前記第１および第２キャッシュ格納チップからの格納データは、１つのメモリ・サイクル中に同時に取り出されることを特徴とする請求項２記載のキャッシュ・メモリ。
【請求項４】
前記キャッシュ・マッピング・アルゴリズムは、前記第１キャッシュ格納チップから前記第１セットへのキャッシュ・ライン、および、前記第２キャッシュ格納チップから前記第２セットへのキャッシュ・ラインをハッシュすることを特徴とする請求項２記載のキャッシュ・メモリ。
【請求項５】
第１および第２キャッシュ・メモリ・チップと、
連続するディスク・アクセスを連続するセットにマップするために前記第１および第２キャッシュ・メモリ・チップに結合されたメモリ・コントローラであって、前記連続するセットの第１セットは前記第１キャッシュ・メモリ・チップからデータにアクセスし、第２セットは前記第２メモリ・チップからデータにアクセスする、メモリ・コントローラと、
から構成されることを特徴とするキャッシュ・メモリ。
【請求項６】
前記第１セットは、前記第１キャッシュ・メモリ・チップ内に任意の数のキャッシュ・ラインを含む追加リストを有することを特徴とする請求項５記載のキャッシュ・メモリ。
【請求項７】
前記メモリ・コントローラは、前記第１キャッシュ・メモリ・チップのためにキャッシュ・ラインのフリー・リストを保持することを特徴とする請求項５記載のキャッシュ・メモリ。
【請求項８】
前記メモリ・コントローラは、新しいキャッシュ・ラインが前記第１セット内に動的に挿入され、かつ前記第１キャッシュ・メモリ・チップに対応することを保証することを特徴とする請求項５記載のキャッシュ・メモリ。
【請求項９】
前記第１キャッシュ・メモリ・チップは、高分子メモリ装置であることを特徴とする請求項５記載のキャッシュ・メモリ。
【請求項１０】
前記高分子メモリ装置は、強誘電性高分子材料を有するメモリ・セルを含むことを特徴とする請求項９記載のキャッシュ・メモリ。
【請求項１１】
前記高分子メモリ装置は、抵抗変化高分子材料を有するメモリ・セルを含むことを特徴とする請求項９記載のキャッシュ・メモリ。
【請求項１２】
前記第１キャッシュ・メモリ・チップは、フラッシュ・メモリ装置であることを特徴とする請求項５記載のキャッシュ・メモリ。
【請求項１３】
前記第１キャッシュ・メモリ・チップは、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）装置であることを特徴とする請求項５記載のキャッシュ・メモリ。
【請求項１４】
１つのメモリ・サイクル中に複数のメモリ・チップからの連続するディスク・アクセスに対応するデータに同時にアクセスする段階を含むことを特徴とする方法。
【請求項１５】
連続するディスク・アクセスを連続するセットにマップするためにキャッシュ・マッピング・アルゴリズムを使用する段階を含むことを特徴とする請求項１４記載の方法。
【請求項１６】
前記キャッシュ・マッピング・アルゴリズムは、
第１キャッシュ格納チップからデータにアクセスするための第１セット、および、第２キャッシュ格納チップからデータにアクセスするための第２セットをハッシュする段階をさらに含むことを特徴とする請求項１５記載の方法。
【請求項１７】
前記第１および第２キャッシュ格納チップからの格納データに同時にアクセスする段階をさらに含むことを特徴とする請求項１６記載の方法。
【請求項１８】
前記第１および第２キャッシュ格納チップからの格納データにアクセスする段階は、１つのメモリ・サイクル中であることを特徴とする請求項１７記載の方法。
【請求項１９】
第１および第２アンテナのそれぞれを通って第１および第２信号を受信する送受信機と、
前記第１および第２信号を受信する前記送受信機に結合されたプロセッサと、
前記プロセッサに結合された第１および第２キャッシュ・メモリ・ブロックと、
前記第１および第２キャッシュ・メモリ・ブロックからデータにアクセスする連続するセットに、連続するディスク・アクセスをマップするためのキャッシュ・マッピング・アルゴリズムを実行するためのメモリ・コントローラと、
から構成されることを特徴とするシステム。
【請求項２０】
１つのメモリ・サイクル中に前記第１および第２キャッシュ・メモリ・ブロックからデータにアクセスする段階をさらに含むことを特徴とする請求項１９記載のシステム。
【請求項２１】
前記第１および第２キャッシュ・メモリ・ブロックは、１つの基板上に共に集積されることを特徴とする請求項１９記載のシステム。
【請求項２２】
前記第１および第２キャッシュ・メモリ・ブロックは、高分子メモリ装置を含むことを特徴とする請求項１９記載のシステム。
【請求項２３】
前記連続するセット内の各セットは、ただ１つのキャッシュ・メモリ・ブロックからのキャッシュ・ラインを含むことを特徴とする請求項１９記載のシステム。
【請求項２４】
前記キャッシュ・マッピング・アルゴリズムは、前記連続するセットの少なくとも１つの中へ新しいキャッシュ・ラインを動的に挿入することを特徴とする請求項１９記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適なキャッシュ・ハードウェア性能を可能にするための適応性のあるレイアウトのキャッシュ構成に関する。
【背景技術】
【０００２】
プロセッサを基本とするシステムは、ハードディスク・ドライブ上のデータにアクセスするが、固体メモリ内に装備されたキャッシュを利用にすることによって改善された性能を達成することができる。プロセッサは、システムがアクセスするディスクからデータを有するキャッシュを取り込む。キャッシュは、より短いアクセスタイムを提供するために、より小さく、より速い格納装置を使用するので、ディスクへアクセスするよりもキャッシュ内に格納されたデータへの後続のアクセスをスピードアップすることでシステム性能がより改善される。
【０００３】
キャッシュ、特にディスク・キャッシュおける周知の設計は、Ｎウェイ・セット・アソシエイティブ・キャッシュであり、そのアドレスは計算されたマッピング関数に基づいてセットにマップされる。かかる設計において、キャッシュは、キャッシュ・ラインのＮ個のアレイの集合として実現されるが、ここで各アレイはセットを表わす。したがって、ディスク上のあらゆる要素は、キャッシュ内のセットにマップされる。セット・アソシエイティブ・キャッシュ内に要素を配置するために、システムは、ディスク上のデータのアドレスを使用して要素が存在するセットを計算し、次に、一致が見つかるまでセットを表わすアレイを通って探索し、または、要素がセット内に存在しないことを決定する。先行技術のディスク・キャッシュは、ワードラインの要求の数を最小にする試みを行なわない。
【０００４】
ここに、ディスク要求毎のワードラインのアクセス数を削減し、かつシステム性能を改善する必要性が存在する。
【発明の開示】
【０００５】
本発明に関する主題は、明細書に添付した請求項において特に指摘され明確にクレームされる。しかしながら、本発明は、その目的、機能、および利点と共に、動作構成および方法の両方に関して、以下の詳細な説明を添付図面と合わせて参照することにより、最も良く理解することができるであろう。
【０００６】
図面を単純化および明瞭化するために、図中に示された要素は、必ずしも同じ寸法で図示されていないことが理解されるであろう。例えば、いくつかの要素の寸法は、明瞭化するために他の要素に比べて拡大される。さらに、適切であると考えられる場合には、参照番号は、対応または類似する要素を示すために図中で繰り返される。
【０００７】
以下の詳細な説明では、本発明についての完全な理解を提供するために、多くの特定の詳細事項が記述される。しかしながら、当業者は、本発明がこれらの特定の詳細事項の範囲を越えて実施可能であることを理解するであろう。また、例えば、周知の方法、手順、コンポーネント、および回路については、本発明を不明瞭にしないために詳細には記述されない。
【０００８】
以下の記述および請求項において、用語「結合された」、「接続された」がそれらの派生語と共に用いられる。これらの用語は、互いに同義語であるとは解さないと理解すべきである。特定の実施例において、「接続された」は、２つ以上の要素が互いに直接に物理的電気的に接触していることを示すために使用される。「結合された」もまた、２つ以上の要素が直接に物理的電気的に接触していることを意味する。しかしながら、「結合された」は、さらに、２つ以上の要素が互いに直接に接触していないが、互いに協働すること、または作用し合うことを意味することがある。
【０００９】
図１は、１またはそれ以上のアンテナからの変調信号を受信または送信する送受信機１４を有するワイヤレス通信装置１０を示す。かかる実施例では、関連するアンテナは、ダイポール・アンテナ、ヘリカル・アンテナ、またはその他同種のアンテナである。アナログ・フロント・エンド送受信機は、スタンド・アロンの無線周波数（ＲＦ）集積アナログ回路として提供されるか、または互換的に、ミクスト・モードの集積回路としてプロセッサ１２に埋め込まれる。受信された変調信号は、周波数がダウンコンバートされ、フィルタされ、そして、デジタル信号に変換される。プロセッサ１２によって処理されたベースバンド信号のためのデジタル・データは、メモリ・カード上のメモリ装置に格納するためにインターフェイス１６を介して転送される。
【００１０】
ネットワーク・インターフェイス・カード（ＮＩＣ）は、インターフェイス１６を介するデータ転送を促進し、かつ、１９９５年６月付の周辺装置相互接続（ＰＣＩ）ローカルバス規格によって定義されるようなＰＣＩバス、あるいは互換的に、ＰＣＩ高速バスまたは他の高帯域バスのようなバスを組込む。プロセッサ１２によって処理されたデータと共に、管理目的のためのキャッシュ管理システムによって使用されたメタデータは、キャッシュ格納チップによって格納される。例示および説明の容易化のために、図１に示されるメモリ・カードは、４つのキャッシュ格納チップ２０，２２，２４，２６を有するが、任意の数のキャッシュ装置をメモリ・カードに装備することができることに注目すべきである。一実施例において、４つのキャッシュ格納チップの各々は、２５６Ｍビットの記憶容量を有するが、この記憶容量には制限されない。さらに、キャッシュ格納チップ２０，２２，２４，２６は、別個のパッケージ装置であってもあるいは共に集積さてもよく、個別のメモリのブロックとしてアドレス指定が可能である。メモリ・カード上のメモリ・コントローラ２８は、アドレスおよび制御信号を介してキャッシュ格納チップに接続される。メモリ・コントローラ２８は、キャッシュ・マッピング・アルゴリズムを実行し、ワイヤレス通信装置１０の性能を改善する。
【００１１】
キャッシュ格納チップ２０，２２，２４，２６は、プロセッサ１２に結合された大容量格納装置（図示せず）のための情報をキャッシュするために適合された比較的大きな不揮発性のディスク・キャッシュ・メモリである。大容量格納装置は、典型的には、例えば少なくとも約１ギガバイトの格納容量を有する。大容量格納装置は、電気機械的なハードディスク・メモリ、光ディスク・メモリ、または磁気ディスク・メモリであるが、本発明の範囲はこの点に制限されない。
【００１２】
一実施例において、キャッシュ格納チップ２０，２２，２４，２６は、少なくとも約２５０メガバイトの格納容量を有する高分子メモリであり、強誘電性メモリ・セルを含み、さらに各セルは少なくとも２つの伝導性ライン間に位置する強誘電性高分子材料を含む。本実施例において、強誘電性高分子材料は強誘電性分極可能材料であり、フッ化ビニル樹脂、ポリエチレン・フッ化物、ポリ塩化ビニル、ポリエチレン塩化物、ポリアクリロニトリル、ポリアミド、これらの共重合体、またはこれらの組合せから成る強誘電性高分子材料を含む。
【００１３】
他の実施例では、キャッシュ格納チップ２０，２２，２４，２６は、例えば、プラスチック・メモリまたは抵抗変化高分子メモリのような高分子メモリである。本実施例では、プラスチック・メモリは、アドレス行列のノード間に挟まれた高分子メモリ材料の薄膜を含む。あらゆるノードでの抵抗は、高分子メモリ材料の両端に供給される電位、および高分子材料の抵抗が変化する高分子材料内における正負の電流の流れによって、数百オームから数メガオームまで変化させることができる。潜在的に、異なる抵抗レベルは、１つのセル毎にいくつかのビットを格納し、また、データ密度は層を積み重ねることによってさらに増加することができる。高分子メモリに加えて、キャッシュ格納チップ２０，２２，２４，２６はＮＯＲまたはＮＡＮＤのフラッシュであるか、または、バッテリでバックアップされたＤＲＡＭである。
【００１４】
大容量格納ディスク・ドライブは、一般にディスク・セクタと呼ばれる５１２バイトのデータ・ブロックを一度に一意のアドレスを指定することができ、従って、ワイヤレス通信装置１０のメモリ・カード上に図示されたディスク・キャッシュは、典型的には同一のアドレス指定の細分性を維持する。複数のアドレス可能な「ディスク・セクタ」またはブロックは、いくつかのキャッシュ・メタデータと共に、キャッシュ格納チップ２０，２２，２４，２６の各キャッシュ・ライン上に格納される。オフセット・アレイはシステム・メモリ内に設定されるが、そこではアレイ内のオフセットの数が、ディスク・キャッシュのために１ワードライン当たりディスク・セクタの数になるように選択される。例えば、１ワードライン当たり４ＫＢを有するディスク・キャッシュのためには、１ワードライン当たり８つのディスク・セクタが格納される。したがって、オフセット・アレイは、８つのディスク・セクタを表わすために８つのエントリを有する。
【００１５】
図２は、メモリ・コントローラ２８（図１参照）によって実行されるキャッシュ・メモリのマッピング・アルゴリズム２００を示す。この実施例において、データ構造および探索アルゴリズムは、Ｍ個の格納チップの並列のハードウェア動作を保証するが、この例におけるＭは、キャッシュ格納チップ２０，２２，２４，２６（図１参照）によって示されるように４である。データ構造およびキャッシュ・メモリのマッピング・アルゴリズムは、適切なキャッシュ・ラインに対するディスク・セクタのマッピングを定義し、システム性能の改善を提供する。マッピング・アルゴリズムは、最初にディスクの論理ブロック・アドレス（ＬＢＡ）を、セット０、セット１、・・・セットＭ等によって示されるようなセットに変換する。論理ブロック・アドレシングは、コンピュータがハードディスクをアドレスすることを可能にする技術であり、そこでは、４８ビットのＬＢＡ値によって、ディスク上の特定のシリンダ・ヘッド・セクタ・アドレスへのマッピングが可能になる。
【００１６】
図２は、さらに、多様なセットにマップされた対応するキャッシュ・ラインをさらに示す。例えば、セット０（参照番号１１０で示す）は、チップ１、すなわち図１のキャッシュ格納チップ２０に対応する。セット０は、チップ１（図１参照）上のキャッシュ・ライン０，１，２，３のそれぞれに対応する任意の数のキャッシュ・ライン１１２，１１４，１１６，１１８を含む追加リストを有する。同様に、セット１（参照番号１２０で示す）は、チップ２、すなわち図１のキャッシュ格納チップ２２に対応する。セット１は、チップ２（図１参照）上のキャッシュ・ライン０，１，２，３のそれぞれに対応する任意の数のキャッシュ・ライン１２２，１２４，１２６，１２８を含む追加リストを有する。さらに、セットＭのための追加リストは、チップＭ（図１参照）上のキャッシュ・ライン０，１，２，３のそれぞれに対応する任意の数のキャッシュ・ライン１３２，１３４，１３６，１３８を含む。セットＭ＋１（参照番号１４０で示す）は、一巡して再びチップ１、すなわち図１のキャッシュ格納チップ２０に対応する。セットＭ＋１のための追加リストは、チップ１（図１参照）上のキャッシュ・ライン４，５，６，７のそれぞれに対応する任意の数のキャッシュ・ライン１４２，１４４，１４６，１４８を含む。このようなセットおよび追加リストのレイアウトは、全てのキャッシュ・ラインが異なるセット内に取り込まれるまで繰り返される。
【００１７】
本発明に従って、ハッシュ関数は、複数のキャッシュ・ラインにまたがる連続的なユーザのデマンド要求を受け取る。この場合、キャッシュ・メモリのマッピング・アルゴリズム２００はハッシュ関数を制御し、連続的なセットにまたがるマッピングを提供する。図示されたマッピング・スキームにおいて、隣接するセットは、異なるキャッシュ格納チップのためのキャッシュ・ラインを有する。各セットに対するキャッシュ・ラインは、各セットがただ１つのキャッシュ・メモリ・チップからのキャッシュ・ラインを含むという方法でマップされることに注意されたい。さらに、隣接するアドレスは隣接するセットにマップされる、換言すれば、格納されたデータが異なるキャッシュ格納チップから同時に選び出されることを可能にするために、連続するディスク・アクセスは連続するセットにマップされることに注意されたい。この点について示す実施例として、４つの隣接するアドレスのためのユーザのデマンドは、４つの連続的なセットにマップし、ほぼ１メモリ・アクセス・タイム内に４つの異なるキャッシュ格納チップからデータを提供する。
【００１８】
図３は、キャッシュ格納チップの各々に利用可能なキャッシュ・ラインのフリー・リスト３００を示す。キャッシュ・メモリのマッピング・アルゴリズム２００は、セット毎に任意の数のキャッシュ・ラインを提供するので、フリー・リストは各キャッシュ・メモリ・チップのために維持される。キャッシュ・ラインの割付けポリシーは、例えばキャッシュ・ライン３１２，３１４のような新しいキャッシュ・ラインが適切なセット内へ動的に挿入され、かつ正確なキャッシュ・メモリ・チップに対応することを保証する。
【００１９】
図４は、ファイル・システムが各入出力（Ｉ／Ｏ）要求毎に複数のディスク・セクタを要求することを示し、ディスク組織内のオーバーヘッドを最小限にするために、通常セクタが増加する場合でさえ、複数のディスク・セクタが１つのファイル・システムのクラスタとしてアドレスされる。残念なことに、第１ファイル・システムのクラスタは、ディスク・ドライブ上のセクタ０からスタートせず、任意のセクタ・オフセットからスタートする。したがって、キャッシュ・アドレスへのディスクのマッピングが、オペレーティング・システム（ＯＳ）のファイル・システムのクラスタへ自然に整列しない場合は、追加のキャッシュ・ワードラインがアクセスされる。この実施例において、ＯＳクラスタ３〜６のためのキャッシュによってサービスされる要求が示され、その要求は、ＯＳのすべてのクラスタ１〜８が転送されるので（キャッシュ・ライン全体は１ユニットとして転送される）、データを転送するために２つのメモリ・サイクルを必要とする。
【００２０】
図４および図５で示される他のケースは、これもまた一般的であるが、両方のケースにおいて、例えばＯＳクラスタ１〜３のための要求である。これは結局データを得るために１つのメモリ・サイクルとなるが、そのケースは、単に、アラインメントによる２つの物理的なチップで時間の約５０％を生じる。ＯＳの３つのクラスタの読み取り（例えば、ＯＳクラスタ３〜５）に対する他のすべてのケースは、先行技術方法を使用して、結果として２つのメモリ・サイクルの読み取りになるが、開示された方法を使用して、なおも単一のメモリ・サイクルの読み取りになる。
【００２１】
図５は、本発明に従って、ＯＳクラスタ３〜６のためのキャッシュによってサービスされる、２つの８ＫＢキャッシュ・ラインに対する同一の要求を示すが、それは１つのメモリ・サイクル中におけるキャッシュ・メモリのマッピング・アルゴリズム２００によって処理される。データ転送はチップ１および２の両方から行われ、したがって、先行技術のサービス要求によって必要とされるような２つのメモリ・サイクルではなく、１つのメモリ・サイクル中にデータ・アクセスが実現されることに注意されたい。さらに、チップ（Ｍ）の数が増加するにつれて、確率は増加し開示された方法は著しい性能の向上を有することに注意されたい。４つのチップの場合には、４つのクラスタ転送のための全ての可能な開始ＯＳクラスタは、１つのメモリ・サイクル中で完了させることができる。
【００２２】
もしワイヤレス通信装置１０のリブートが必要な場合、（１）各キャッシュ・ラインは、メタデータを取り出すためにスキャンしなければならず、（２）キャッシュ・ラインのタグは回復されなければならず、（３）そのタグは、セット・ポインタに変換されなければならず、および（４）そのキャッシュは、適切なセット上に挿入されなければならない。
【００２３】
以上より、キャッシュ・メモリのマッピング・アルゴリズムおよび関連するハードウェアのための本発明が、先行技術のディスク・システム以上の利点を有することが明らかになった。各セットがただ１つのキャッシュ・メモリ・チップからのキャッシュ・ラインを含むという方法で、ハッシング関数はキャッシュ・ラインをマップする。連続するディスク・アクセスは連続するセットにマップされ、これによって格納データを異なるキャッシュ格納チップから同時に取り出すことができる。キャッシュ・ラインの割付けポリシーは、新しいキャッシュ・ラインが適切なセット内へ動的に挿入され、かつ、正確なキャッシュ・メモリ・チップに対応することを保証する。これらおよび他の機能によって性能が向上する。
【００２４】
本発明の原理は、セルラー・ネットワーク、ワイヤレス・ローカル・エリア・ネットワーク（ＷＬＡＮ）、パーソナル・エリア・ネットワーク（ＰＡＮ）、８０２．１１ネットワーク、超広帯域（ＵＷＢ）、その他を含む多種多様の通信ネットワーク内で動作するために接続されるワイヤレス装置内で実行される。特に、本発明は、スマート・フォン、通信および個人用デジタル情報処理端末（ＰＤＡ）、医療またはバイオテック機器、自動車用安全および保護機器、自動車用娯楽情報製品内で使用することができる。しかしながら、本発明の範囲は、これらの実施例に制限されないと理解されるべきである。
【００２５】
本発明のいくつかの機能がここに図示され記述されたが、多くの修正、代替、変更、および均等が当業者によって想起されるであろう。したがって、添付の請求項は、本発明の正しい思想の範囲内に該当するものであれば、かかる修正および変更をすべてカバーするように意図されると理解されるべきである。
【図面の簡単な説明】
【００２６】
【図１】本発明のキャッシュ・マッピング・アルゴリズムの機能が組込まれた、メモリ・コントローラおよびＭキャッシュ格納チップを図示する。
【図２】キャッシュ・メモリのマッピング・アルゴリズムの実施例を図示する。
【図３】各キャッシュ格納チップのために利用可能なキャッシュ・ラインのフリー・リストを示す。
【図４】ファイル・システム・クラスタとして複数のディスク・セクタにアドレスする先行技術のファイル・システムを示す。
【図５】本発明に従ってアドレスされたファイル・システム・クラスタとしての複数のディスク・セクタを示す。
【図１】
2007513438.tif 000003
【図２】
2007513438.tif 000004
【図３】
2007513438.tif 000005
【図４】
2007513438.tif 000006
【図５】
2007513438.tif 000007
【国際調査報告】
2007513438.tif 000008
2007513438.tif 000009
2007513438.tif 000010