(57)【要約】  高速メモリ操作を提供するためのシステムおよび方法を開示する。この技術はメモリ空間の仮想化を使用してさらに大容量の物理アドレス空間に仮想アドレス空間をマッピングするが、メモリバンクの競合は発生しない。さらに大容量の物理アドレス空間は、メモリに書き込まれているデータの仮想メモリアドレスを、メモリバンクの競合を取り除く物理メモリの別の場所に移動させることによってメモリバンクの競合が発生しないように使用される。【選択図】図６Ａ
2013513884.tif 000002
【特許請求の範囲】
【請求項１】
デジタルメモリシステムにおいてメモリアクセス要求を処理する方法であって、
仮想メモリアドレス空間内の第１の仮想メモリアドレスを特定する第１のメモリアクセス要求を受け付け、
前記第１の仮想メモリアドレスに関連するデータを現在保存している物理メモリシステムのメモリバンクを識別する第１のメモリバンク識別子、前記仮想メモリアドレス空間より大容量の物理アドレス空間を有する前記物理メモリシステム、を得るためのメモリマッピングテーブルへのインデックスとして前記仮想メモリアドレスを使用して、
前記メモリバンク識別子と前記第１の仮想メモリアドレスの一部とを含む第１の物理メモリアドレスによって前記第１のメモリアクセス要求を処理する、
ことを含む、方法。
【請求項２】
前記メモリマッピングテーブルは前記仮想メモリアドレス空間のメモリバンクの数と競合を防ぐために使用されるメモリバンクの数とを加えた数とに等しい列のセットを含む、請求項１に記載のメモリアクセス要求を処理する方法。
【請求項３】
前記メモリマッピングテーブルおよび前記メモリバンクは等しい数の行を有する、請求項２に記載のメモリアクセス要求を処理する方法。
【請求項４】
前記メモリマッピングテーブルの各エントリはメモリバンク識別子値を保存する、請求項２に記載のメモリアクセス要求を処理する方法。
【請求項５】
前記第１の物理メモリアドレス空間はＮ個のメモリバンクを含み、前記仮想メモリアドレス空間はＮ−１個のメモリバンクのサイズの前記物理メモリアドレス空間の一部を占める、請求項１に記載のメモリアクセス要求を処理する方法。
【請求項６】
前記第１のメモリアクセス要求は前記物理メモリの第１のバンクへの読み出し操作を含み、
前記方法は、
前記第１のメモリアクセス要求とともに第２のメモリアクセス要求を同時に受け付け、前記第２のメモリアクセス要求は、書き込み操作を含み、前記第２のメモリアクセス要求は、前記仮想メモリアドレス空間内の第２の仮想メモリアドレスを識別し、
前記第２の仮想メモリアドレスに現在結び付けられている第２の物理アドレスが前記第１のメモリアクセス要求とメモリバンクの競合を引き起こしうる場合に、新しい第２の物理メモリアドレスに書き込み、
前記メモリマッピングテーブルを更新して前記新しい第２の物理メモリアドレスを前記第２の仮想メモリアドレスに結び付けることをさらに含む、請求項１に記載のメモリアクセス要求を処理する方法。
【請求項７】
前記第１のメモリアクセス要求および前記第２のメモリアクセス要求とともに第３のメモリアクセス要求を同時に受け付け、前記第３のメモリアクセス要求は、書き込み操作を含み、前記仮想メモリアドレス空間内の第３の仮想メモリアドレスを識別し、
前記第３の仮想メモリアドレスに現在結び付けられている第３の物理アドレスが前記第１のメモリアクセス要求または前記第２のメモリアクセス要求とメモリバンクの競合を引き起こしうる場合に、新しい第３の物理メモリアドレスに書き込み、
前記メモリマッピングテーブルを更新して前記新しい第３の物理メモリアドレスを前記第３の仮想メモリアドレスに結び付けることをさらに含む、請求項６に記載のメモリアクセス要求を処理する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジタルコンピュータシステム分野に関する。特に、限定することを目的としないが、本発明はデジタルメモリシステムへのアクセス要求を迅速に提供するための技術を開示する。
【背景技術】
【０００２】
本特許出願は、２００９年１２月１５日に出願し、発明の名称が「ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＳＴＯＲＩＮＧ  ＤＡＴＡ  ＩＮ  Ａ  ＶＩＲＴＵＡＬＩＺＥＤ  ＨＩＧＨ  ＳＰＥＥＤ  ＭＥＭＯＲＹ  ＳＹＳＴＥＭ」である米国特許出願第１２／６５３，６６０号（特許文献１）の優先権を主張する。
【０００３】
最近のほとんどのコンピュータシステムは、コンピュータ命令を処理するための少なくとも１つのプロセッサと、プロセッサによって処理される命令およびデータを保存するメインメモリシステムを含む。一般に、メインメモリシステムはＤＲＡＭとして広く知られているある種のダイナミックランダムアクセスメモリで実装される。ＤＲＡＭデバイスは、記録密度（使用される集積回路の面積当たりで保存されるデータ量）がきわめて高く、低消費電力で相対的に安価である。したがって、ＤＲＡＭデバイスはコンピュータシステムの大容量メインメモリシステムを構成するために使用される。
【０００４】
コンピュータプロセッサの動作速度は絶えず増大している。具体的には、半導体トランジスタのサイズが縮小し、これらのトランジスタの動作電圧が低下したことにより、プロセッサクロックがさらに速く動作することが可能になった。しかし、これらの高速プロセッサにデータを提供するＤＲＡＭメインメモリシステムの性能は、ますます速くなるプロセッサに追従していない。
【０００５】
したがって、ＤＲＡＭによるメインメモリシステムはコンピュータ性能のボトルネックとなっている。この問題を軽減するために、さらに大容量のスタティックランダムアクセスメモリ（ＳＲＡＭ）によるキャッシュメモリシステムが使用されることが多い。ＳＲＡＭデバイスはＤＲＡＭデバイスよりはるかに速い速度で動作するが、記録密度が低く、多くの電力を消費し、高価である。さらに、キャッシュメモリシステムは、キャッシュ「ヒット」が発生した（必要とされるデータがキャッシュメモリシステムで利用可能である）際にのみ速度が改善するにすぎない。キャッシュミスが発生すると、低速ＤＲＡＭメモリシステムからデータをフェッチしなくてはならない。高速性能を保証する必要のあるいくつかの用途では、キャッシュメモリシステムの使用は十分ではない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許出願第１２／６５３，６６０号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
したがって、メモリシステムがメモリの読み出し操作と書き込み操作を可能な限り速く処理できるようにメモリシステムの速度を改善するのが望ましい。
【図面の簡単な説明】
【０００８】
【図１】機械装置に本願明細書に記載する方法の１つまたは複数を実行させるために、１セットの命令が実行できる例示的形態のコンピュータシステムにおける機械装置を概略的に表す図である。
【図２】実際に利用可能な容量よりも大容量のメインメモリシステムを構築する従来の仮想メモリシステムの概念図である。
【図３Ａ】インターリーブメモリシステムを示す図である。
【図３Ｂ】図３Ａのインターリーブメモリシステムの使用を示すタイミングチャートを示す図である。
【図４Ａ】複数の独立したメモリバンクを有するメモリシステムを示す図である。
【図４Ｂ】図４Ａの複数のバンクメモリシステムの使用を示すタイミングチャートを示す。
【図５】さらに小容量の仮想メモリ空間で良好な性能を提供するために増設物理メモリを使用する仮想メモリシステムの概念図である。
【図６Ａ】仮想メモリシステムの第１の実施形態のブロック図である。
【図６Ｂ】仮想メモリシステムの第２の実施形態のブロック図である。
【図７Ａ】同時の読み出し操作と書き込み操作を受け付ける仮想メモリシステムの初期開始状態を示す図である。
【図７Ｂ】同時の読み出し操作と書き込み操作を処理した後の図７Ａの仮想メモリシステムの状態を示す図である。
【図７Ｃ】別の同時の読み出し操作と書き込み操作を受け付ける図７Ｂの仮想メモリシステムを示す図である。
【図７Ｄ】読み出し操作と書き込み操作を処理した後の図７Ｃの仮想メモリシステムの状態を示す図である。
【図８】図６Ａの仮想メモリシステムがどのように動作するかを説明するフローチャートである。
【図９】各メモリの行に１つ以上の要素を保存する仮想メモリシステムの一実施形態の別のブロック図である。
【図１０】仮想メモリマッピングテーブルの拡大図である。
【図１１Ａ】符号化されたメモリマッピングテーブルにおける関係を確立するための設定パターンを示す図である。
【図１１Ｂ】図１１Ａの設定パターンを使用してメモリマッピングテーブルの行を符号化する実施例を示す図である。
【図１１Ｃ】符号化されたメモリマッピングテーブルにおける関係を確立するための設定パターンを示す図である。
【図１１Ｄ】図１１Ｃの設定パターンを使用してメモリマッピングテーブルの行を符号化する実施例を示す図である。
【図１２Ａ】符号化されたメモリマッピングテーブルにおける関係を確立するための設定パターンを示す図である。
【図１２Ｂ】図１２Ａの設定パターンを使用してメモリマッピングテーブルの行を符号化する実施例を示す図である。
【図１２Ｃ】符号化されたメモリマッピングテーブルにおける関係を確立するための設定パターンを示す図である。
【図１２Ｄ】図１２Ｃの設定パターンを使用してメモリマッピングテーブルの行を符号化する実施例を示す図である。
【図１２Ｅ】図１２Ｃおよび１２Ｄの行のパターンを符号化する代替実施例を示す図である。
【図１３Ａ】速度を改善するための複製された仮想メモリテーブルを含む仮想メモリシステムを示す図である。
【図１３Ｂ】仮想マッピングテーブルが通常の保存に使用されるメモリバンクの残部と同じ物理メモリシステム内に実装されることを示す図である。
【図１３Ｃ】ピンポンのように動作する２つの異なるセットの複製された仮想メモリテーブルを含む仮想メモリシステムを示す図である。
【図１４Ａ】１つの読み出し操作と２つの書き込み操作を同時に処理する仮想メモリシステムの初期状態を示す図である。
【図１４Ｂ】１つの読み出し操作と２つの同時書き込み操作を処理した後の図１４Ａの仮想メモリを示す図である。
【図１４Ｃ】別の読み出し操作とさらに２つの書き込み操作を受け付ける図１４Ｂの仮想メモリシステムを示す図である。
【図１４Ｄ】図１４Ｃでの読み出し操作と２つの書き込み操作を処理した後の図１４Ｃの仮想メモリシステムの状態を示す図である。
【図１５Ａ】同時の読み出し操作と書き込み操作を処理し、読み出し操作の時間は書き込み操作の半分であるという非対称性のメモリ操作を利用する仮想メモリシステムのタイミングチャートである。
【図１５Ｂ】さらに第２の書き込み操作を処理する図１５Ａの仮想メモリシステムのタイミングチャートである。
【図１５Ｃ】同時の読み出し操作と書き込み操作を処理し、互いの偶数倍ではない非対称性のメモリ操作を利用する仮想メモリシステムのタイミングチャートである。
【図１５Ｄ】別の書き込み操作が別の増設メモリバンクを追加することで処理される図１５Ｃのタイミングチャートである。
【図１５Ｅ】別の書き込み操作が別の増設メモリバンクを必要としないで処理される図１５Ｄのタイミングチャートである。
【図１５Ｆ】同じメモリサイクルの読み出し操作後に書き込みを連続で実行することで分割性能が増大する仮想メモリシステムのタイミングチャートである。
【図１５Ｇ】図１５Ｆのタイミングチャートであり、並列書き込み操作を移動させて、マッピングテーブルのメモリ性能要件を減らしているタイミングチャートである。
【図１５Ｈ】別の並列書き込み操作が追加されている図１５Ｇのタイミングチャートである。
【図１５Ｉ】非対称性の読み出し操作と書き込み操作による仮想メモリシステムのタイミングチャートである。
【図１５Ｊ】第３の書き込み操作が２つの読み出し操作後に連続して追加され、分割性能を向上させる図１５Ｉのタイミングチャートである。
【図１５Ｋ】メモリサイクル単位で３つの読み出しと３つの書き込みを処理する仮想メモリシステムのタイミングチャートである。
【図１５Ｌ】６ナノ秒メモリサイクルで２つの読み出しと２つの書き込みを３つの増設バンクで処理する仮想メモリシステムのタイミングチャートである。
【図１５Ｍ】６ナノ秒メモリサイクルで４つの読み出しと４つの書き込みを３つの増設バンクで処理する仮想メモリシステムのタイミングチャートである。
【図１６】１つの読み出し操作と１つの書き込み操作を同時に処理する仮想メモリシステムの初期状態を示し、書き込み操作が読み出し操作よりも優先することを示す図である。
【図１７Ａ】初回のメモリ書き込み操作を受け付ける図１６の教示を用いて構成される仮想メモリシステムの初期状態を示す図である。
【図１７Ｂ】初回の書き込み操作を処理した後の図１７Ａの仮想メモリシステムの状態を示す図である。
【図１７Ｃ】別のメモリ書き込み操作を受け付けた後の図１７Ｂの仮想メモリシステムの状態を示す図である。
【図１７Ｄ】この書き込み操作を処理した後の図１７Ｃの仮想メモリシステムの状態を示す図である。
【図１７Ｅ】読み出し操作と書き込み操作を受け付けるデータ値が存在する図１７Ａの仮想メモリシステムの状態を示す図である。
【図１７Ｆ】この読み出し操作と書き込み操作を処理した後の図１７Ｅの仮想メモリシステムの状態を示す図である。
【図１８】あらゆる仮想アドレスがあらゆる物理アドレスに配置できる制限されていない仮想メモリシステムを示す図である。
【図１９】書き込みバッファを使用してメモリバンクの競合を回避し性能の低下を防ぐメモリシステムを示す図である。
【図２０】メインメモリバンクより小容量の増設メモリバンクを備え、書き込みバッファを含むことも可能な仮想メモリシステムを示す図である。
【発明を実施するための形態】
【０００９】
図面では、必ずしも縮尺して描画しておらず、複数の図面を通して同じ番号は実質的に類似する構成要素を示す。さまざまな添え字を有する同じ番号は、実質的に類似する構成要素のさまざまな例を表す。一般に、図面は、一例として示すが限定目的ではなく、本願明細書に記載するさまざまな実施形態を示す。
【００１０】
以下の詳細な記載は、添付の図面を参照することを含み、図面は記載の一部を成す。図面は例示的実施形態による図を示す。これらの実施形態は、本願明細書では「実施例」とも呼ばれ、当業者が本発明を実施できるほど十分詳細に記載する。例示的実施形態の詳細情報は本発明を実施するために必要とされないことは当業者には明らかである。たとえば、例示的実施形態のいくつかは、パケット交換網に使用されるコンピュータ処理システムに関連して開示しているが、この教示は他の多くの環境で使用することができる。したがって、デジタルメモリを使用するあらゆるデジタルシステムは本開示の教示から便益を得ることができる。例示的実施形態を組み合わせてもよく、他の実施形態を利用してもよく、あるいは、特許請求の範囲から逸脱せずに、構造的に、論理的に、電気的に変更してもよい。したがって、以下の詳細な記載は限定的な意味に理解されるのではなく、本発明の範囲は本願特許請求の範囲とその均等物によって定義される。
【００１１】
本願明細書では、明記しない限り、「または」という用語は非排他的なものに言及するために使用する。つまり「ＡまたはＢ」は、「ＢではなくＡ」、「ＡではなくＢ」および「ＡおよびＢ」を含むように使用する。さらに、本願明細書で言及する全ての出版物、特許および特許文献は、参照によりその全体が組み込まれるものである。つまりそれぞれ参照により本願明細書に組み込まれるとする。本願明細書とそのように参照によって組み込まれた文書との間で用法が矛盾している場合、組み込んだ参照における用法は本願明細書の用法を補完するものとみなすべきであり、解消できない矛盾に関しては本願明細書の用法が支配する。
【００１２】
コンピュータシステム
本開示はデジタルコンピュータシステムに関する。図１は、本開示の部分を実装するために使用できる例示的形態のコンピュータシステム１００の機械装置を概略的に表す図である。図１のコンピュータシステム１００内には、機械装置に本願明細書に記載する方法の１または複数を実行させるために実行できる１セットの命令１２４がある。
【００１３】
ネットワーク配置では、図１の機械装置は、クライアントサーバネットワーク環境で、あるいは、ピア機としてピアツーピア（または分散型）ネットワーク環境でサーバ機またはクライアント機の能力で動作してもよい。機械装置は、パーソナルコンピュータ（ＰＣ）、タブレット型ＰＣ、セットトップボックス（ＳＴＢ）、携帯情報端末（ＰＤＡ）、携帯電話、ウェブ機器、ファイルサーバ、ネットワークルータ、ネットワークスイッチ、ネットワークブリッジ、または、機械装置によって実施される動作を明示する１セットのコンピュータ命令（順次またはその他の方法による）を実行可能なあらゆる機械装置であってよい。さらに、単一の機械装置のみを示しているが、「機械装置」という用語は１セットの（または複数のセット）の命令を別個で、あるいは、一緒に実行して本願明細書に記載する方法の１または複数を実行するあらゆる群の機械装置を含むものとする。
【００１４】
図１の例示的なコンピュータシステム１００は、プロセッサ１０２（たとえば中央演算処理装置（ＣＰＵ）、グラフィック処理装置（ＧＰＵ）または両方）、メインメモリ１０４およびスタティックメモリ１０６を含み、バス１０８を介して互いに通信する。コンピュータシステム１００は、液晶ディスプレイ（ＬＣＤ）または陰極線管（ＣＲＴ）などのビデオディスプレイシステム１１５を駆動するビデオディスプレイアダプタ１１０をさらに含んでもよい。また、コンピュータシステム１００は英数字入力装置１１２（たとえばキーボード）、カーソル制御装置１１４（たとえばマウスまたはトラックボール）、ディスク装置１１６、信号発生装置１１８（たとえばスピーカ）およびネットワークインタフェース装置１２０を含む。図１に示すこれらの部品全てが実施形態全てに存在するわけではないことに注意する。たとえば、サーバがネットワークインタフェース装置１２０によって制御される場合、コンピュータサーバシステムはビデオディスプレイアダプタ１１０またはビデオディスプレイシステム１１５を有してなくてもよい。
【００１５】
ディスク装置１１６は、本願明細書に記載する方法または機能の１または複数によって実施されるか、あるいは、利用される１または複数のセットのコンピュータ命令およびデータ構造（たとえば、「ソフトウェア」としても知られている命令１２４）が保存される機械可読媒体１２２を含む。また、命令１２４は、プロセッサ１０２に関連するメインメモリ１０４内および／またはキャッシュメモリ１０３内に完全に、あるいは、少なくとも部分的に存在してもよい。また、プロセッサ１０２に関連するメインメモリ１０４およびキャッシュメモリ１０３は機械可読媒体を構成する。
【００１６】
命令１２４は、ネットワークインタフェース装置１２０を介してコンピュータネットワーク１２６上でさらに送受信してもよい。このような転送は、周知のファイルトランスポートプロトコル（ＦＴＰ）などの多くのよく知られた転送プロトコルのいずれかを利用して行なってもよい。
【００１７】
機械可読媒体１２２は、単一の媒体となるように例示的実施形態に示されているが、「機械可読媒体」という用語は、１または複数のセットの命令を保存する単一の媒体またはマルチメディア（たとえば、集中データベースまたは分散データベースおよび／または関連するキャッシュおよびサーバ）を含むものとみなされるべきである。また、「機械可読媒体」という用語は、機械装置によって実行するための１セットの命令を保存、符号化または転送することが可能であり、機械装置に本願明細書に記載する方法の１つまたは複数を実行させ、あるいは、そのような１セットの命令によって利用されるか、あるいは、関連するデータ構造を保存、符号化または転送することが可能なあらゆる媒体も含むものとみなされるべきである。したがって、「機械可読媒体」という用語は、ソリッドステートメモリ、光媒体および磁気媒体を含むものとみなされるべきだが、これらに限定されない。
【００１８】
本願明細書において、「モジュール」という用語は、コードの識別可能な部分、コンピュータによる命令もしくは実行可能な命令、データまたはコンピュータによるオブジェクトを含み、特定の機能、動作、処理またはプロシージャを得る。モジュールは、ソフトウェアに実装する必要はなく、ソフトウェア、ハードウェア／回路に、あるいは、ソフトウェアとハードウェアとを組み合わせて実装してもよい。
【００１９】
従来の仮想メモリ
図１の例示的なコンピュータシステム１００を参照すると、プロセッサ１０２は命令１２４を実行し、命令１２４は一般に、メインメモリ１０４からフェッチされるか、あるいは、プロセッサ１０２自体の内蔵キャッシュメモリ１０３からフェッチされる。しかし、大規模コンピュータプログラムを作成し、大規模データセットを処理したいという要望は、結局のところコンピュータプログラマがメインメモリ１０４の利用可能なメモリ空間を使い果たすことになるため、コンピュータプログラマにとって困難であった。メインメモリの容量が限られているという問題に対処するために、仮想メモリの発想が生まれた。
【００２０】
仮想メモリによって、コンピュータプログラマが作業できる大容量アドレス空間の「仮想メモリ」が提供される。しかし実際には、仮想メモリを備えるコンピュータシステムは、仮想メモリアドレス全体を表すのに必要とされる物理半導体メモリほどの容量を含んでいない。その代わりに実際には、単に仮想アドレス空間の一部が、コンピュータシステムの集積回路に実装されたメモリ内で利用可能である。仮想メモリ空間の他の部分は、磁気ディスクなどの速度の遅い長期保存メモリシステムによって保存される。仮想メモリシステム２２０の概念図を図２に示す。
【００２１】
図２を参照すると、仮想メモリシステム２２０は、コンピュータプログラマが使用するために利用可能な仮想メモリ全体を表す大容量仮想メモリアドレス空間２２５を含む。プロセッサ２１０は、仮想アドレスを使用し、仮想メモリシステムコントローラ２２１を介して大容量仮想メモリアドレス空間２２５の命令およびデータにアクセスする。仮想メモリシステムコントローラ２２１は、仮想メモリシステムへの全メモリアクセス要求を処理する役割を担う。（プロセッサ２１０は、利用可能なメモリの小さい部分の複製である内蔵キャッシュメモリ２０２を含んでもよいことに注意する。）
【００２２】
仮想メモリシステム２２０に関しては、実際には大容量仮想アドレス空間２２５からの現在必要とされる部分の命令およびデータのみが、コンピュータシステムの実物理メインメモリ２０４内に物理的に存在する。仮想メモリコントローラ２２１は、物理メインメモリ２０４内の物理メモリアドレスに仮想メモリアドレスを変換する役割を担う。この物理メインメモリ２０４は通常、ダイナミックランダムアクセスメモリ装置などの半導体メモリ装置に実装される。
【００２３】
仮想メモリアドレス空間２２５にロードされているものの物理メインメモリ２０４に存在していない他のコンピュータ命令およびデータの全ては、長期ストレージシステム２１６に保存される。典型的なパーソナルコンピュータシステムでは、この長期ストレージは通常、図１に示すようにハードディスクドライブ１１６によって設けられる。（他のシステムは長期ストレージシステムとしてフラッシュメモリなどの代替手段を使用してもよい。）プロセッサ２１０が仮想メモリアドレス空間の特定の部分にアクセスしていない可能性があり、それゆえ仮想メモリのアクセスされていない領域の状態は不明確であることから、仮想アドレス空間２２５の容量は、長期ストレージシステム２１６が仮想メモリシステム２２０とともに使用するために現在割り当てられている部分より大きくてもよいことに注意する。しかし、プロセッサ２１０が仮想アドレス空間の過去にアクセスしていない部分にアクセスする場合、仮想メモリシステム２２１は、長期保存メモリシステムから増設長期ストレージ空間２１６を割り当てて、仮想メモリアドレス空間２２５の新たにアクセスされた領域を処理する。多くの仮想メモリシステムは、仮想メモリアドレス空間全体のサイズに等しい長期ストレージの領域を割り当て、十分な長期ストレージが仮想メモリシステム２２０に対して常に利用可能になることを確実にする。
【００２４】
仮想メモリシステムコントローラ２２１は、仮想メモリアドレス空間２２５からの現在必要とされる命令およびデータが物理メインメモリ２０４にロードされることを確実にする役割を担う。仮想メモリアドレス空間２２５の必要な部分が物理メインメモリ２０４に現在表されていない場合、仮想メモリシステムコントローラ２２１は、長期ストレージシステム２１６から仮想メモリアドレス空間のその部分を読み出し、実メインメモリ２０４に転送する。必要とされる仮想アドレス空間の新しい部分に対して空間を形成するためには、仮想メモリシステムコントローラ２２１は実メインメモリ２０４に現在存在している命令およびデータを長期ストレージ２１６に移動させることになる。メモリの部分をメインメモリシステムに入出力するこの技術は、「スワップ」と呼ばれることが多い。実行せざるを得ないスワップの数を減少させるために、多数のアルゴリズムは、メモリのどの特定の部分が最も早くアクセスされそうもないかを判断することを支援するために存在する。
【００２５】
上に記載したとおり、仮想メモリの概念によって、小容量の実物理メインメモリ２０４は長期ストレージ２１６から割り当てられる増設ストレージ空間の支援によってはるかに大容量の仮想メモリアドレス空間２２５を表すことができる。しかし、利用可能な実物理メモリアドレス空間よりはるかに大容量の仮想メモリアドレス空間を表すこの能力には不利な点がある。具体的には、仮想メモリアドレス空間２２５の必要な部分がメインメモリ２０４で現在表されていない場合、さらに遅い長期ストレージシステム２１６のデータにアクセスせざるを得ないため、メモリシステム全体の平均的性能はさらに遅くなるのである。
【００２６】
高速メモリ技術
いくつかの要求が厳しい用途に対しては、長期ストレージの使用は高帯域幅メモリを必要とするため実行可能な選択肢ではない。たとえば、ネットワークルータなどの高速ネットワーク装置では、ネットワークルータは最初のデータ通信リンクからメモリシステムに受信データパケットをすぐに保存する必要がある。後に、ルータは別のデータ通信リンクで転送されるメモリシステムから再び保存されたデータパケットを読み出す必要がある。データパケットのこのような読み書きは、超高速で実行してデータ通信リンクにデータを満たし続ける必要がある。したがって、仮想メモリシステムはそのような用途で使用することができない。
【００２７】
したがって、上に記載したパケットルーティングの用途などの特定の用途に関しては、データを保存するために使用される全てのメモリ位置に対してメモリ応答を高速にする必要がある。一貫性のある高速メモリ性能を必要とするこれらの用途に対して、メモリシステム全体は実物理メモリ装置で構成することができる。このようにして、全てのメモリ位置は、メモリシステムを構成するために使用される集積回路メモリ装置の最高速度でデータを保存して呼び戻すことができるようになる。
【００２８】
しかし、メインコンピュータメモリシステム全体が従来のダイナミックランダムアクセスメモリ装置を使用して構成されても、メモリシステムは、いくつかの要求が厳しい用途に対して所望のメモリ性能を未だに備えることができない。最近の超高速プロセッサおよびデジタル通信リンクのせいで、メモリシステムはコンピュータシステム性能全体の向上を制限する性能ボトルネックになってしまっている。新しい技術は、特定のコンピュータ利用技術の超高速メモリの性能要件を満たすことを必要とする。
【００２９】
図２を参照すると、１つの明らかな解決法は、プロセッサ２１０内に実装された内蔵キャッシュメモリ２０２のサイズを大幅に増大させることだろう。この技術は、特定用途に対する高速メモリの必要性を全て内蔵キャッシュメモリ２０２の限られたアドレス空間によって満たすことができる場合に使用することができる。しかし、これは多くのさまざまな理由から完全に満足できる解決法というわけではない。超大容量の内蔵キャッシュメモリ２０２を備えるコンピュータプロセッサは大規模集積回路のダイサイズを必要とするため、プロセッサの歩留まり（作製されたひとまとまりの集積回路に対する完全に操作可能な集積回路の割合）は低下する。さらに、プロセッサ回路の集積回路ダイ領域が小さくなることから、プロセッサ回路をあまり複雑にすることができない。このような制限のため、超大容量のキャッシュメモリシステムで構成されるコンピュータプロセッサは、そのプロセッサには大規模な市場が存在しないことから、隙間製品となるため高価となる。しかし、この解決法に関する最大の問題は、多くの用途が、内蔵キャッシュメモリ２０２で実装できるよりはるかに大容量のメモリアドレス空間を単に必要としているということである。したがって、メインメモリシステムの性能を改善するための新しい技術が必要である。
【００３０】
使用可能な別の技術は、実現しうる最高のメモリ性能をもたらすスタティックランダムアクセスメモリ（ＳＲＡＭ）などのメモリ設計を使用してメモリシステム全体を構成することである。この技術は最適なメモリ性能を必要とするいくつかの用途に使用されている。しかし、ＳＲＡＭ装置が高価であり、メモリ密度が低く、大量の電力を消費することから、これは望ましい解決法でない。したがって、ＤＲＡＭなどの高密度メモリ装置からさらに良好な性能を得るための技術が必要である。
【００３１】
インターリーブメモリバンク
ＤＲＡＭメモリ装置に一つ共通する特性とは、最初のメモリ要求をメモリ装置に行うと、ＤＲＡＭメモリ装置がすぐに応答するということである。しかし、直後のメモリ要求が同じメモリ装置内のあらゆるメモリアドレスに行われる場合、メモリ装置は最初のメモリ要求に対する応答ほど速く応答することができない。この理由は内部のもので、メモリが、ある種の維持操作を実行し、最初のメモリアクセスサイクルを完了する必要があるということによる。たとえばＤＲＡＭ装置に関して、ＤＲＡＭメモリ装置は、その後のメモリ要求に応答する前にメモリマトリクスから読み出されたメモリの行に対してリフレッシュを実行する必要がある。
【００３２】
メモリシステムは、メモリ装置がさまざまな独立したメモリバンクにメモリアドレス空間を編成して全メモリサイクルを完了する前のデータに応答し、各メモリバンクはさまざまなメモリ装置から構成されるという事実を利用することができる。そこで、これらのメモリバンクは、最も多く連続したメモリアクセス要求が異なるメモリバンクにアクセスするようにインターリーブされる。このように、コンピュータシステムはほとんどのメモリアクセスに対して最初のメモリアクセスのメモリ応答が高速であるという利点を有するようになる。その後のアクセスを準備する前の、メモリのリフレッシュを完了する時間が、読み出しサイクルを開始した後のデータに対する応答時間より短ければ、各メモリバンクとしては、速い応答時間であらゆる他のメモリ要求に応答する準備が整っていることになる。
【００３３】
図３Ａは簡易双方向インターリーブメモリシステムの実施例を示す。図３Ａの双方向インターリーブメモリには、バンク０およびバンク１の２つのメモリバンクがある。２つのメモリバンクは独立しており、バンク０がメモリ操作を完了するために使用されている場合、バンク１は即時に利用可能となり、メモリアクセスに素早く応答する。（同じように、バンク１がメモリ操作を完了するために使用されている場合、バンク０は利用可能となる。）メモリシステムのアドレス方式はインターリーブされることから、あらゆる直後の連続したアドレスは前回のアドレスとは異なるメモリバンクにある。したがって、図３Ａに示すように、アドレス０はバンク０にあり、アドレス１はバンク１にあり、アドレス２はバンク０にあり、アドレス３はバンク１にあるなどと続く。
【００３４】
コンピュータプログラムが実行する場合、一般にコンピュータシステムのプロセッサは、メモリに連続して編成されるコンピュータ命令を読み込む必要がある。このようにして、図３Ａのメモリシステムからメモリアドレスを連続して読み込むと、各連続したメモリアクセスは前回のメモリアクセスとは異なるメモリバンクから行われる。最初にバンク０のアドレス０が読み込まれ、次にバンク１のアドレス１が読み込まれ、次にバンク０のアドレス２が読み込まれ、次にバンク１のアドレス３が読み込まれるなどと続く。２つのメモリバンクが独立しているため、別のメモリバンクが前回のメモリアクセス操作を完了するために依然として使用されている間、異なるメモリバンクへのアクセスが発生する可能性がある。したがって、図３Ｂに示すようにメモリアクセスを交互にして、メモリシステムの性能を大幅に改善することができる。
【００３５】
図３Ｂを参照すると、プロセッサは最初に時間３３１でアドレス０を要求してもよい。バンク０は、時間３３２でアドレス０からデータに応答することになる。時間３３２ではバンク０は何らかの内部操作（メモリリフレッシュなど）を実行する必要があるため、別のメモリ要求を即時に受け付けることができない。しかし、次の連続したメモリアクセスは使用されていないメモリバンク１内のアドレス１に対して行われるため、アドレス１に対する要求は時間３６１ですぐに発行することができる。バンク１はアドレス１に対するメモリ要求に応答する間、バンク０はアドレス０へのアクセス後に必要とされる内部操作を終了している。バンク１が時間３５１でアドレス１からのデータに応答する場合、バンク０は時間３３３で別のメモリ要求を準備する。したがって、コンピュータプロセッサは時間３３３でアドレス２にメモリアクセス要求を発行することができる。したがって、インターリーブメモリシステムは、ＤＲＡＭ装置の総読み出しサイクルをマスクする支援をするために使用することができる。
【００３６】
メモリをインターリーブするこの技術とは、各メモリアクセス後に異なるメモリバンクにアクセスする場合にのみ性能が改善するものである。直後の連続したメモリアクセス要求がまさにアクセスした同じメモリバンクにある場合、性能は向上しない。たとえば、プロセッサは時間３５３でメモリアドレス５からデータを得た後にメモリアドレス１にアクセスする必要がある場合（アドレス位置１に対してプログラムループバックがあるなどの場合）、メモリが同じメモリバンク内に配置されるアドレス１にアクセスを試みる前に、メモリアドレス５への前回のメモリアクセスに関連する内部操作を完了するまでバンク１を待つ必要がある。次に、プロセッサがメモリアドレス９などのバンク１の別のメモリアドレスに即時にアクセスする場合、メモリシステムは、アドレス１に対する前回のメモリアクセスを完了するまでバンク１を再度待つ必要がある。したがって、メモリアクセスはバンク０にもはや重ならない。したがって、同じメモリバンクに連続したメモリアクセスがある場合はインターリーブメモリの利点は失われる。
【００３７】
インターリーブシステムにおいてメモリ操作の性能を向上させるために、コンピュータプログラマは、プログラムデータにアクセスする際に連続して同じメモリバンクにアクセスしないようなコンピュータプログラムの作成を試みることができる。これは可能であるが、コンピュータプログラマがそのような制約に対処するようにコンピュータコードを注意深く作成することは極めて困難で時間がかかる。さらに、かなり多数のコンピュータソフトウェア開発は、Ｃ、Ｃ＋＋、Ｐａｓｃａｌ、ＦＯＲＴＲＡＮなどの高水準コンピュータ言語で行われる。これらの高水準プログラミング言語は、このようなメモリバンクの制約に対処する特徴が一切欠けており、プログラミングは、取扱いがきわめて困難なアセンブリ言語で行う必要があるだろう。
【００３８】
独立したメモリバンクへの並列アクセス
図３Ａおよび３Ｂで記載されているように、異なるメモリバンクの操作は互いに完全に独立していてもよい。したがって、２つの完全に独立したメモリアクセス操作は２つの異なるメモリバンクで同時に実行することができる。これは、メモリの複数の消費者を同時に扱うことによって、高いメモリ帯域幅を得る高速メモリシステムの構築を可能にする。メモリシステムの２つの異なるユーザが独立したメモリバンクに同時にアクセスすることを可能にすることで、メモリシステムの実効メモリ帯域幅は２倍となる。
【００３９】
図４Ａは、複数のメモリ要求を２つの異なるメモリユーザ４１１およびメモリユーザ４１２から受け付けることを可能にする４つの独立したメモリバンク（メモリバンク０、１、２および３）を有するメモリシステムの実施例を示す。２つのメモリユーザ（４１１および４１２）が異なるメモリバンクにアクセスする場合にのみ、２つのメモリユーザはメモリシステムを同時に共有し、遅延させないで動作することができる。したがって、図４Ｂのタイミングチャートで示すように、メモリユーザ４１２がメモリアドレス１０１にアクセスする間、メモリユーザ４１１はメモリアドレス０００にアクセスすることができる。メモリユーザ４１２がメモリアドレス３０４にアクセスする間、メモリユーザ４１１はメモリアドレス２０２にアクセスすることができる。
【００４０】
しかし、２つのメモリユーザ（４１１および４１２）が同じメモリバンクにアクセスを試みる場合、メモリユーザの少なくとも１つは遅延せざるをえない。たとえば、図４Ｂに示す第４のデータ時間では、メモリユーザ４１２がメモリアドレス１０１にアクセスする間、メモリユーザ４１１はメモリアドレス１０５にアクセスする。メモリアドレス１０５およびメモリアドレス１０１が同じメモリバンク（メモリバンク１）にあるため、２つのメモリユーザの１つ（４１１または４１２）は遅延せざるをえない。図４Ｂの実施例では、メモリユーザ４１１が優先されるため、メモリユーザ４１２は遅延する。なぜならメモリユーザ４１１によるメモリアドレス１０５へのアクセスが完了するまで待たないと、メモリユーザ４１２によるメモリアドレス１０１へのメモリアクセスは完了しえないからである
【００４１】
図４Ａで開示されているメモリシステムに関する上の記載は、メモリユーザ４１１およびメモリユーザ４１２の２つの個々のメモリユーザに関連していた。しかし、図４Ａで開示するメモリシステムも、メモリユーザ４１１およびメモリユーザ４１２の２倍の速度で動作している単一のメモリユーザとともに容易に使用することができる。プロセッサ４１０は、メモリユーザ４１１および４１２のクロックスピードの２倍で動作する場合、メモリユーザ４１１および４１２によって使用される１つのクロックサイクルで２つのメモリ要求を発行することができる。これらの２つのメモリ要求をメモリシステムコントローラ４２１に同時に表すことができる。したがって、メモリシステムコントローラ２２１の観点からすると、２倍の速度でメモリ要求を発行する単一のエンティティは、通常速度でメモリ要求を発行する２つのエンティティときわめて類似している。
【００４２】
図４Ａで示されているメモリシステムに対してメモリ帯域幅を最大限にするために、そのようなシステムのプログラマは、メモリバンクの競合を最小限化するようなコンピュータコードを注意深く構築する必要がある。しかし、上に記載するように、そのような制約を作成すると、このようなシステムのプログラミングは困難となり、時間がかかる。上に記載したように、高水準プログラミング言語には、プログラマがそのような制約を守ることを確実なものにするような特徴はない。
【００４３】
理想的なメモリシステムとは、複数の異なるエンティティが、メモリシステムのあらゆるアドレス位置に同時にアクセスすることが可能なものである。この理想的なシステムにおいては、あらゆるメモリ位置にメモリアクセスを同時に行なっても、システムを遅延させるメモリバンクの競合を引き起こすことはない。さらに、この理想的なメモリシステムは特殊なプログラミング制約を課すことがないため、プログラマは、あらゆる高水準プログラミング言語を使用することが可能であり、メモリ競合がいつ発生するか心配することはない。
【００４４】
高速メモリシステムの新しいパラダイム
複数のエンティティがほぼ制約なしにメモリにアクセスすることを可能にするような理想的なメモリシステムにさらに近い実際のメモリシステムを構成するため、本開示は「仮想メモリシステム」を採用する。仮想メモリシステムは、特定のプログラミング制約を仮想メモリシステムのユーザに課すことなくこの目標を達成する。本開示の仮想メモリシステムは、通常メモリバンクの競合による不利益を被っている同じ見かけ上のメモリバンクに対して、読み出し操作および書き込み操作を同時に行うことを考慮に入れている。
【００４５】
仮想メモリシステムは、図２に関して開示されているような従来の仮想メモリに類似の方法で動作する。従来の仮想メモリのように、本開示の高速仮想メモリシステムは、仮想メモリシステムがどのように具体的に実物理メモリアドレス空間のデータの保存および検索を処理するかという具体的な詳細を心配する必要なしに、コンピュータプログラマが仮想メモリアドレス空間で作業することを可能にする。その代わりに、仮想メモリコントローラは仮想メモリアドレス空間に行われた全メモリアクセス要求を、物理メモリアドレス空間に変換する。しかし、仮想メモリコントローラは、メモリバンクの競合が仮想メモリシステムを使用しているエンティティの性能に全く影響しないような方法で、このアドレス空間の変換を達成する。したがって、最適なメモリ性能は、仮想メモリシステムにメモリアクセス要求を送信するエンティティの観点から得られる。
【００４６】
その背景では、仮想メモリコントローラは、仮想メモリシステムにアクセスするエンティティ（または複数のエンティティ）の性能を低下させるメモリバンクの競合がないことを確実にする１セットのアドレス空間マッピングテーブルを使用して、仮想アドレス空間でのメモリ要求を実物理アドレス空間に変換している。この目標を達成するため、仮想メモリコントローラは仮想メモリアドレス空間をさらに大容量の物理アドレス空間にマッピングする。さらに大容量の物理メモリアドレス空間を使用することで、仮想メモリシステムは、あらゆる潜在的なメモリバンクの競合の影響を仮想メモリシステムのユーザが受けないようにしている。したがって、従来の仮想メモリシステム（図２に関して開示するものなど）は、さらに大容量メモリ空間の外観を得るために、大容量の仮想アドレス空間２２５を小容量の物理メモリアドレス空間２０４にマッピングするが、本開示の仮想メモリシステムは、メモリ性能を改善するように、小容量の仮想アドレス空間を大容量の物理メモリアドレス空間にマッピングする。
【００４７】
図５は、本開示に関する教示を用いる基本的な仮想メモリシステム５００の概念図を示す。図５で開示されているメモリシステムでは、メモリユーザ５１１およびメモリユーザ５１２は同じ仮想メモリシステム５００にアクセスする。図４Ａに開示するメモリシステムと同じように、仮想メモリシステム５００に対して同時に行われるメモリ要求は、２つの個々のエンティティの２倍の速度で動作する単一のエンティティから行なってよい。したがって、ユーザ５１１およびメモリユーザ５１２のクロックスピードの２倍の速さで動作するプロセッサ５１０は、仮想メモリシステム５００によって同時に受け付けられる２つのメモリ要求として現れる２つの連続したメモリ要求を発行することが可能である。
【００４８】
仮想メモリシステム５００へのメモリアクセス要求の全てが、仮想メモリシステムコントローラ５２１によって処理される。仮想メモリシステムコントローラ５２１は、仮想メモリアドレスを含むメモリアクセス要求（読み出し、書き込みまたは他のメモリコマンド）を受け付け、全ての仮想メモリアドレス（仮想メモリアドレス空間５０４にある）をさらに大容量の物理メモリアドレス空間５２０の実物理メモリアドレスに変換し、物理メモリアドレス空間５２０内の物理アドレスを使用して、要求された情報にアクセスする。仮想メモリシステムコントローラ５２１は、仮想メモリシステムコントローラ５２１の１または複数の仮想メモリテーブル５２３を用い、仮想アドレス空間から物理アドレス空間への変換を実行する。仮想アドレス空間から物理アドレス空間への変換の最終結果は、従来のメモリシステム（図４Ａに示すシステムなど）で性能を低下させるメモリバンクの競合を通常引き起こしうるメモリユーザ５１１およびメモリユーザ５１２からのメモリアクセス要求のパターンによって、メモリユーザ５１１およびメモリユーザ５１２の観点から、いかなるメモリバンクの競合も引き起こされないということになる。潜在的なメモリバンクの競合の全てがさまざまな技術を使用して取り除かれる。
【００４９】
仮想メモリシステム５００と典型的な従来のメモリシステムの大きな違いの１つは、メモリシステムは増設メモリ装置が「ドープ」されている点である。これらの増設メモリ装置によって、仮想メモリシステム５００の物理アドレス空間５２０は仮想メモリアドレス空間より大きくなる。
【００５０】
仮想メモリシステムの内部編成
図６Ａは、本開示の教示による仮想メモリシステム６００の第１の実施形態のブロック図である。図５の概念図で示したように、仮想メモリシステム６００は、主に仮想メモリシステムコントローラ６２１および物理メモリアレイ６２０から成る。図６Ａおよび以下の記載で示す実施例は、具体的な数のメモリバンク、メモリアドレスなどを設ける。しかし、これらはこの一例示的実施形態のための数にすぎないことは当業者にとって明らかだろう。さまざまな異なるメモリシステムのサイズは、きわめてさまざまな数のメモリバンク、メモリアドレスなどを使用して形成してもよい。
【００５１】
図６Ａを参照すると、物理メモリアレイ６２０は、それぞれ１００行を有する５つの独立したメモリバンク（バンクＡ〜Ｅ）に編成される。説明を容易にするため、本願明細書はメモリバンクのサイズおよびメモリアドレスを、２進数によるアドレスシステムの代わりに１０進数で表記するが、実際の実施形態のほとんどは２の偶数倍を使用するだろう。それぞれ１００行の５つのメモリバンクを有する図６Ａの仮想メモリシステム６００の実施形態では、５００個の独自の物理メモリアドレスが、物理メモリ６２０の中に存在する。
【００５２】
図５の概念図で説明されているように、仮想メモリシステム６００は、実物理アドレス空間より小容量の仮想メモリシステム６００のユーザに対し、仮想メモリアドレス空間を提示している。したがって、図６Ａの実施形態では、仮想メモリアドレス０００〜３９９を含む初期の仮想メモリアドレス空間６０４（点線の長方形で囲まれる）が、物理メモリバンクＡ〜Ｄ内で提示されている。物理メモリバンクＥは、最初に仮想メモリ位置を全く提示しないため、メモリバンクＥのメモリ位置は「空」と表示されている。図６Ａで示されているように、本願明細書は、物理メモリ位置の箱の中で、３桁の仮想メモリアドレスとして、物理メモリ位置により現在示されている仮想メモリアドレスを具体的に明示する。たとえば、バンクＢの行００の物理メモリ位置は、最初に仮想メモリアドレス１００を表すため、メモリバンクＢの行００の箱の中では「１００」が表示されている。本願明細書の以下で記載されているように、さまざまな仮想メモリアドレスの実際の位置は物理メモリ空間６２０を転々とする。したがって、図６Ａで示されている仮想メモリアドレス空間６０４の編成は、多くの状態がある中、１つのありうる状態を表しているにすぎない。
【００５３】
仮想メモリシステムコントローラ６２１はメモリユーザ６１０からの仮想メモリアクセス要求全てを処理する役割を担う。メモリシステムコントローラ６２１は、仮想メモリアドレス（図６Ａのアドレス０００〜３９９）を物理メモリ６２０内の実物理メモリアドレス（図６Ａでメモリバンクの文字とメモリバンクの行によって識別される）に変換する。仮想アドレスから物理アドレスへの変換タスクを達成するため、メモリシステムコントローラ６２１は少なくとも１つの仮想メモリマッピングテーブル６２３を使用する。
【００５４】
図６Ａの第１の仮想メモリシステム実施形態では、仮想メモリアドレスは最上位桁（３桁仮想アドレスの上１桁）と下２桁（３桁仮想アドレスの下２桁）に分割される。図６Ａの具体的な実施形態では、仮想メモリシステムは、物理メモリシステムの物理行を示す文字として仮想メモリアドレス（仮想メモリアドレスの下２桁）の下１桁を使用する。したがって、仮想メモリアドレスの下２桁が物理メモリアドレスの下２桁と同じであるため、仮想メモリアドレスの下２桁を変換する必要はない。
【００５５】
しかし、仮想メモリアドレスの最上位桁は物理メモリアドレスに変換する必要がある。図６Ａのシステムでは、仮想メモリアドレスの最上位桁は、物理メモリバンクに変換される。変換を実行するため、仮想メモリマッピングテーブル６２３は、メモリバンクの行数と等しい数の行と、アドレスの考えうる最上位桁の数（仮想アドレス空間０００〜３９９のこの実施例では０、１、２および３）とに等しい数の列とを含む。仮想メモリアドレスを物理メモリ位置に変換するため、仮想メモリシステムコントローラ６２１は、仮想メモリアドレスの下２桁と同じ行と、仮想メモリアドレスの最上位桁と同じ列とを有する仮想メモリマッピングテーブル６２３のエントリを調べる。たとえば、仮想アドレス３０４を物理メモリ位置に変換するため、仮想メモリシステムコントローラ６２１は、仮想アドレス３０４（行０４にある）を現在表しているメモリバンクとして列「３」および行「０４」のエントリを閲覧する。
【００５６】
０〜３列に加えて、図６Ａの仮想メモリマッピングテーブル６２３の実施形態は「ｅ」を示す列も含む。この列は、指定された行での空のメモリ位置を含むメモリバンクを識別するために使用される。たとえば、仮想メモリマッピングテーブル６２３の列「ｅ」の行「０２」は、位置が空のメモリバンクとして「Ｅ」を表示している。しかしこの列は実装する必要がない。なぜなら、その特定の行にあるメモリ位置が空のメモリバンクは、その同じ行の０〜３列で表示されていないメモリバンクを示す文字（Ａ、Ｂ、Ｃ、ＤまたはＥ）を確定することにより推察されるからである。
【００５７】
図６Ｂは、仮想メモリシステム６００の第２の実施形態のブロック図である。図６Ｂの代替実施形態では、メモリバンクが物理メモリにある場合は仮想メモリテーブル６２３には同じ数の列がある。このように、仮想メモリテーブル６２３の列とメモリバンクとの間には１対１対応があり、仮想メモリテーブル６２３の行と物理メモリバンクの行との間に１対１対応がある。図６Ｂの仮想メモリテーブル６２３の各エントリは、対応するメモリバンクおよび行で現在表示されている仮想メモリアドレスの最上位桁を明示する。したがって、初期状態では、物理メモリ６２０のバンクＡはアドレス０００〜０９９を含むことから、仮想メモリテーブル６２３のバンクＡの列の全エントリは「０」を含む。（この場合もやはり、この実施例は説明を簡単にするために１０進数を使用しているにすぎないことに注意する。実際の実施形態は２進数の仮想メモリアドレスから最上位ビット１セットを使用することが多い。）同じように、初期状態では、物理メモリ６２０のバンクＢは、アドレス１００〜１９９を含むことによって、化想メモリテーブル６２３のバンクＢの列の全エントリは「１」を含む。メモリバンクＣおよびＤの列に関しては、それぞれ「２」および「３」を含む。図６Ｂで示されている初期状態では、メモリバンクＥは仮想アドレスに保存されているいかなる情報も現在含んでいないことから、仮想メモリアドレス空間からのいかなる情報も表示しないため、「ｅ」で示される対応する列Ｅのエントリを有する。
【００５８】
同時読み出しと書き込みの処理
図６Ａおよび図６Ｂの仮想メモリシステム６００は、メモリユーザ６１０がメモリバンクの競合によって遅延することが決してないように、仮想メモリシステム６００内のあらゆる他のアドレスへの同時書き込み要求とともに読み出し要求を処理するように構成される。したがって、同じメモリバンクに読み出し要求と書き込み要求があった（ほとんどのメモリシステムでメモリバンクの競合を引き起こすとされる）としても、仮想メモリシステム６００はメモリユーザ６１０が遅延しないように要求を処理する。したがって、仮想メモリシステム６００は、保証されたメモリ帯域幅を備えるため、保証されたメモリアクセス時間を必要とする全ての用途は仮想メモリシステム６００を使用することができる。
【００５９】
容易に対処できない１つの状況は、同時に全く同じ仮想アドレスに対して読み出しと書き込みを同時に受け付ける場合であることに注意する必要がある。通常、その同じアドレスが同じエンティティによって書き込まれる場合はアドレスを読み込む理由が全くないため、メモリユーザはそのような１対の同時要求を発行すべきではない。しかし、そのようなことが発生する場合は、実施形態に応じて元のデータまたは新しく書き込まれたデータをリーダに与えてもよい。
【００６０】
図４Ａおよび図４Ｂに関して上に記載されているように、メモリアクセス要求がメモリシステム内の異なるメモリバンクに向けられる場合にのみ、独立したメモリバンクを備えるマルチバンクメモリシステムは複数の同時メモリアクセス要求を容易に処理することができる。たとえば、図６Ａを参照すると、あるメモリユーザがバンクＡに書き込む間に、別のメモリユーザはメモリバンクの競合がない状態で、バンクＣから読み込むことが可能であり、これはメモリバンクが独立していることによる。しかし、２つの同時のメモリアクセス要求が同じメモリバンクに向けられた場合、メモリバンクの競合は発生する。
【００６１】
仮想メモリシステムコントローラ６２１はメモリバンクの競合を処理し、書き込み操作に対する仮想メモリアドレスを、異なるメモリバンクの未使用メモリ位置に移動させることによって、読み出し操作と書き込み操作が同じメモリバンクに同時に発行される。未使用メモリ位置は、仮想メモリテーブル６２３を読み込むことで求められ、未使用のメモリ位置が求められる。その後、仮想メモリアドレスの新しい位置で仮想メモリテーブル６２３が更新される。
【００６２】
その技術の記述には、実施例を使用することが最適である。図６Ａの仮想メモリシステム６００の実施形態の例示的な動作は、図７Ａ、図７Ｂおよび図８に関して記載される。図７Ａは、同じ初期状態図６Ａの同じ仮想メモリシステム６００を示す。仮想メモリシステムコントローラ７２１が、図７ＡのＷ（１０１）と示されている、仮想アドレス１０１に対するメモリ書き込みと、Ｒ（１０３）と示されている、仮想アドレス１０３に対するメモリ読み出しとを同時に受け付ける場合、仮想アドレス１０１および仮想アドレス１０３の両方が同じメモリバンク（メモリバンクＢ）にあるため、このメモリアクセスパターンは通常、メモリバンクの競合を引き起こすものである。メモリバンクの競合を防ぐために、仮想メモリシステムコントローラ７２１は通常、物理メモリバンクＢで仮想アドレス１０３の読み出しを開始するが、異なるメモリバンクを使用して仮想アドレス１０１への書き込みを処理する。新しいデータ値が仮想アドレス１０１に書き込まれているため、現在の仮想アドレス１０１に現在存在しているデータにはもはや関連性がなくなる。
【００６３】
全ての一連のイベントは、図８のフローチャートに関して記載されている。図８のフローチャートは、システムを簡単に説明するために使用される。実際の実施形態では、いくつかの段階（段階８１０および段階８３０のテーブルルックアップなど）は並列で実行してもよい。
【００６４】
最初に、段階８０５では、仮想メモリシステムコントローラ７２１は読み出し要求（アドレス１０３から）と書き込み要求（アドレス１０１に）を受け付ける。次に、段階８１０では、仮想メモリシステムコントローラ７２１は仮想メモリテーブル７２３を閲覧して、読み出し要求に関連する仮想アドレス１０３の現在の物理位置が求められる。最上位桁は仮想メモリテーブル７２３の列を選択するために使用され、下２桁は仮想メモリテーブル７２３の行を選択するために使用され、仮想アドレス１０３はメモリバンクＢに現在配置されていることを明示する。したがって、仮想メモリシステムコントローラ７２１はその物理位置を読み込み、段階８２５ではアドレス１０３から読み出し要求に応答する。この場合もやはり、これらの実施例は説明を簡単にするために１０進数で表すだけであって、通常の実施形態は２進数を使用することになることを強調する必要がある。さらに、他の多くのルックアップテーブル設計（行および列に結び付けられるさまざまなアドレスビットなど）は、図７Ａに示す特定の仮想メモリテーブル７２３の実施例と同じ結果を得るために使用してもよい。
【００６５】
段階８３０では、仮想メモリシステムコントローラ７２１は仮想メモリテーブル７２３を閲覧して書き込み要求に関連する仮想アドレス（この実施例では１０１）の物理位置が求められる。仮想メモリテーブル７２３を閲覧すると、仮想アドレス１０１がメモリバンクＢにあることが明らかである。次に、段階８３５では、システムはこの位置によって読み出し操作とのメモリバンクの競合が引き起こされるかを判断する。書き込みは、異なるメモリバンクのメモリ位置（バンクＤのアドレス２００など）に対して要求された場合、その位置を使用し、段階８４０の読み出し操作と並列して簡単に実行することから、双方のメモリ操作を終了することが可能となる。しかし、この実施例では、書き込みはメモリバンクＢにある仮想アドレス１０１に対するものであることから、メモリバンクＢでも仮想アドレス１０３の読み出しとのメモリバンクの競合が引き起こされる。
【００６６】
アドレス１０１とアドレス１０３との間のメモリバンクの競合を防ぐため、システムは段階８５０に進み、仮想メモリシステムコントローラ７２１は仮想メモリテーブル７２３の０１行の「ｅ」列を閲覧して利用可能なメモリバンクの物理位置を求め、仮想アドレス１０１に関するデータを書き込む。仮想メモリテーブル７２３の列「ｅ」の行０１は、利用可能であるメモリバンクＥを明示する。したがって、仮想メモリシステムコントローラ７２１は書き込み要求からのデータをメモリバンクＥの行０１に書き込む。（実データ値は、ここでの説明には重要でないことから示していない。）
【００６７】
仮想メモリアドレス１０１の位置が移動したため、仮想メモリテーブル７２３は仮想アドレス１０１の新しい物理位置を反映するために更新する必要がある。したがって段階８６０では、仮想メモリシステムコントローラ７２１は仮想メモリテーブル７２３の０１行の１列に「Ｅ」を書き込む。
【００６８】
同じように、０１行に結び付けられる新しい空きメモリバンクは更新する必要がある。したがって、段階８７０では、仮想メモリシステムコントローラ７２１は仮想メモリテーブル７２３の行０１の「ｅ」列に「Ｂ」を書き込む。空きメモリバンクは特定の行の００、０１、０２または０３の列に示されないメモリバンクよって推測される実施形態では、この段階は実行する必要はないことに注意する。この時点では、アドレス１０３に対する読み出し操作とアドレス１０１に対する書き込み操作が、メモリアクセス要求を発行したメモリユーザが遅延しないように実行されている。
【００６９】
図７Ｃおよび図７Ｄに関して、同時の読み出し操作と書き込み操作の第２の実施例が記載されている。図７Ｃは、開始点として図７Ｂの状態を用い、仮想アドレス２０１への書き込みと仮想アドレス２０４からの読み出しを同時に受け付ける。仮想アドレス２０４の読み出しを実行するためには、メモリコントローラ７２１は最初に物理メモリ内の仮想アドレス２０４の位置を求める。したがって、メモリコントローラは最初に、仮想アドレス２０４がメモリバンクＣに現在配置されていることを明示する仮想アドレステーブル７２３の行０４の列２でエントリを読み出す。したがって、メモリコントローラ７２１はメモリバンクＣの０４行から仮想アドレス２０４に対するデータを読み出し、読み出し要求を処理する。
【００７０】
仮想アドレス２０１への書き込み（過去に列Ｃの０１行にあったことから、メモリバンクＣの行０４から読み出しとのメモリバンクの競合が引き起こされる）を処理するために、メモリコントローラ７２１は仮想アドレステーブル７２３の行０１の「ｅ」列からエントリを読み込み、行０１に対する空きメモリバンクがメモリバンクＢであることを求める。したがって、位置２０１への書き込みに関連するデータは、図７Ｄに示すように物理メモリバンクＢの行０１に配置される。次に、メモリコントローラ７２１は、テーブル７２３を更新して仮想アドレス２０１の新しい位置（列２の行０１のエントリに「Ｂ」を書き込むことによる）と、行０１に対する新しい空きメモリの位置（行０１の「ｅ」列のエントリに「Ｃ」を書き込むことによる）とを反映する。
【００７１】
上記の２つの実施例から明らかなように、仮想メモリシステムには、あらゆる仮想アドレスに対して書き込みを実行できる少なくとも２つの位置が常にあり、その仮想アドレスの現在の位置は、空として示される行に対する仮想アドレスまたはメモリバンクの現在の位置である。入力された書き込みが、同時に起こる読み出しによりメモリバンクの競合を引き起こさない場合、仮想メモリコントローラ７２１は現在の位置にデータを保存してもよい。しかし、同じメモリバンクに対する読み出しと書き込みによって引き起こされたメモリバンクの競合がある場合、仮想メモリコントローラ７２１はその行に対する空の位置を有するメモリバンクにデータを書き込み、仮想メモリテーブル７２３内のその仮想メモリアドレスの新しい位置を更新する。図に示す実施形態では、仮想アドレス空間の位置の下２桁が物理メモリ空間の行を常に示す。しかし、実際のデジタル実現では、仮想メモリアドレスからの一部のビット（仮想メモリアドレスの最下位ビット１セットなど）を使用してもよい。
【００７２】
各メモリおよび各テーブル行への複数入力
図６Ａおよび図７Ａ〜図７Ｄの実施例では、各メモリバンク（および対応するメモリテーブルのエントリ）の行が単一のメモリ位置として示されている。しかし、これは本開示のシステム要件でない。各メモリバンクの個々の列が独立して読み出されて書き込まれることが可能な場合にのみ、各メモリバンクの各行は複数の個々のデータエントリを含んでもよい。図９はそのような実施形態の考えうる一実施例を示す。
【００７３】
図９を参照すると、各メモリバンクは３つの列に分割されている。各行のこれらの列はそれぞれ、メモリバンクのその同じ行にある異なる仮想メモリアドレスを表してもよい。仮想メモリアドレスからの追加アドレスビット（図示しない）は、そのメモリバンク行のどの列が処理されるかを具体的に明示するために使用する必要があることに注意する。さまざまな列を処理するためには、仮想メモリテーブル９２３は対応するセットの列も有する必要がある。このようにして、各個々の列は、必要に応じて配置され、読み出され、移動させることができる。図９で示されているように、仮想メモリテーブル９２３のメモリバンクおよびメモリ位置のアドレス可能な物理メモリ位置の間の１対１対応が依然として存在する。
【００７４】
図９で示されている実施形態は、多くの実施形態の中で有利となりうることに注意しなければならない。桁幅のある行のデータを読み出すことから１メモリセル単位でさらに少ない読み出し回路を有するメモリ回路を使用して、さらに高い記録密度を得ることができる。したがって、多くの（相当数の）実施形態は図９を参照して記載する教示を用いることが可能である。多くの実施形態は図９を参照して記載する教示を用いてもよいが、本願明細書は実施例が不必要に複雑にならないようにメモリバンク単位の１つのエントリを示す図を継続して使用する。
【００７５】
マッピングテーブルの符号化
図６Ａを再び参照すると、仮想メモリマッピングテーブル６２３を使用して、仮想メモリシステム６００は仮想メモリアドレスを物理メモリアドレスに変換する。図１０は、仮想メモリマッピングテーブル１０２３の拡大図である。仮想メモリマッピングテーブル１０２３へのインデックスとして特定の仮想メモリアドレスを使用して、仮想メモリマッピングテーブル１０２３のエントリは、どのメモリバンクがその特定の仮想メモリアドレスを現在保存しているかを明示する。
【００７６】
仮想メモリマッピングテーブル１０２３には異なる仮想アドレスそれぞれに対してエントリがあるため、仮想メモリマッピングテーブル１０２３のサイズはかなり大きくなりかねない。仮想メモリマッピングテーブル１０２３のサイズを縮小させるため、図１０の実施形態は各仮想メモリアドレスを制限して各メモリバンクの同じ行に配置する。これにより、システムがあらゆる仮想メモリアドレスをあらゆる物理メモリアドレスに保存することを可能にする場合、各テーブルのエントリは行およびメモリバンクを必要とする代わりに、仮想メモリアドレスを含む特定のメモリバンクをただ明示することが可能となる。しかし、このように制限しても、仮想メモリマッピングテーブル１０２３は相対的に大きくなる。
【００７７】
仮想メモリマッピングテーブル１０２３の各エントリは、５つの異なるメモリバンク（Ａ、Ｂ、Ｃ、ＤまたはＥ）のどの１つが特定の仮想メモリアドレスを保存するのかを明示する必要がある。５つの異なる状態の１つを保存するためには、図１０の例示的な行１０５０で示されているように、通常３ビットが必要である。しかし、３ビットが８つの異なる利用可能な状態を実際に保存できるため、これは無駄なことである。したがって、ストレージシステムの効率を上げて仮想メモリマッピングテーブル１０２３のサイズを縮小させることが望ましいということになる。
【００７８】
図１１Ａおよび図１１Ｂは、仮想メモリマッピングテーブル１０２３の各行のサイズを縮小させるために使用できる符号化方法を示す。開示する符号化方法では、図１１Ａの左の部分で示されているように、各メモリバンクにはユニークな３ビット符号化が割り当てられ、メモリバンクＡは０００で識別され、メモリバンクＢは００１で識別されるなどと続く。この３ビット符号化システムは、仮想メモリマッピングテーブル１０２３の第１の列のメモリバンクを明示するために使用される。これは図１１Ｂで示されており、「０」列が３ビットの値を含んでいる。
【００７９】
次に、４つの残りの列は、設定相関パターンによる第１の列の値からのオフセットを明示する２ビット値で符号化される。図１１Ａの右の部分は、さまざまなメモリバンクの間の１つの例示的な相関パターンを示す。図１１Ａの例示的な相関パターンでは、第１の列で特定される位置から時計回りに１つ離れた位置は「００」に符号化され、第１の列で特定される位置から時計回りに２つ離れた位置は「０１」に符号化されるなどと続く。各符号化は位置の番号から１を引いた２進値であることに注意する。
【００８０】
図１１Ｂでは一実施例が示されている。図１１Ｂの第２の行はテーブル行の例示的パターンＣ、Ａ、Ｂ、Ｅ、Ｄを示す。これを符号化するために、第１の列は、図１１Ａのパターンの位置１１１０によって明示するように０１０であるＣの符号化によって特定される。次に、残りの位置は、図１１ＡのパターンのＣ位置１１１０からのその相対位置によって符号化される。ＡはＣの符号化から時計回りのパターンに沿って３つの位置であるため、第２の列はバンクＡを明示することから、第２の位置で１０に符号化される。次に、第３の列は図１１ＡのパターンのＣから４つ離れた位置であるバンクＢを明示するため、「１１」に符号化される。次の２つの列が同じ方法で符号化される。図１１Ｃおよび１１Ｄは第２の実施例を示し、Ａ、Ｅ、Ｃ、Ｄ、Ｂを含むマッピングテーブル行が符号化される。
【００８１】
図１１Ａ〜１１Ｄに記載の符号化システムは、仮想メモリマッピングテーブルの各行のサイズを１５ビットから１１ビットに縮小させ、これにより仮想メモリマッピングテーブル全体のサイズを縮小させる。仮想メモリマッピングテーブルがはるかに大規模の実際の実施形態では、これは大規模な仮想メモリマッピングテーブルのサイズに対して大幅な縮小となる。
【００８２】
しかし、仮想メモリマッピングテーブルをさらに効率的に符号化することができる。各行は、各異なるメモリバンクのインスタンスを一度含むのみであることに注意する。特定のメモリバンク値は符号化されると、メモリバンクは再び同じ行に現れない。これは、仮想メモリマッピングテーブルのサイズをさらに縮小させるために使用することができる。具体的には、連続する残りのエントリを符号化するのに必要なビット数は、残りのエントリの数を符号化するのが必要なビット数に等しい。図１２Ａおよび１２Ｂに関する一実施例が供給される。
【００８３】
最初に、符号化される必要がある５つのエントリがある。３ビットが５つの異なる状態を符号化するために必要であるため、第１のエントリは、前出の実施例に示すように３ビットで符号化される。図１２Ｂの実施例では、バンクＣを明示する第１のエントリは０１０に符号化される。この時点では、符号化される４つの残りのエントリがあり、２ビットのみが４つの異なる状態を符号化するのに必要であることから、２ビットが第２のエントリを符号化するために使用される。一方、前出の実施例に使用される同じ方法は、第２のエントリを符号化するために使用される。第２のエントリは図１２Ａの相関パターンのＣ位置から３つ離れた位置であるバンクＡを明示するため、「１０」が第２のエントリのバンクＡを符号化するために使用される。この時点では、符号化される３つの残りのエントリがあり、２ビットが３つの異なる状態を符号化するのに必要であることから、２ビットが第３のエントリを符号化するために使用される。一方、前出の実施例に使用される同じ方法は、第３のエントリを符号化するために使用される。第３のエントリは図１２Ａの相関パターンのＣ位置から４つ離れた位置であるバンクＢを明示するため、「１１」が第３のエントリを符号化するために使用される。
【００８４】
この時点では、テーブルには符号化される２つの残りのエントリのみがあり、１ビットのみが２つの異なる状態を符号化するのに必要であることから、第４のエントリを符号化するためには１ビットのみが使用される。第４のエントリを符号化するためには、第１のエントリからの図１２Ａのパターンに沿った位置の数は、残りの値が符号化される考慮される場合にのみ使用される。この実施例では、Ｃ、ＡおよびＢが既に符号化されているため、ＥおよびＤのみが符号化されていない。第４の位置はバンクＥを明示し、バンクＥは図１２ＡのＣ位置からの２つ離れた位置であることから、残りのＤおよびＥ位置を考慮する場合にのみ第４のエントリは「１」として符号化される。
【００８５】
最後に、符号化される位置は１つ残るのみである。技術的には、考えうるエントリが１つのみであることから最終の位置を符号化するビットを必要はない。さらに上に記載したとおり、その値を推測できるため、いくつかの実施形態は最終列を備えなくてもよい。しかし、図１２Ｂの実施形態では、第５（最終）の位置は第４の位置と同じ方法で符号化される。第５の位置は図１２ＡのＣ位置からの１つのみ離れた位置であるバンクＤを明示し、残りのＤおよびＥ位置を考慮する場合にのみ第４のエントリは「０」として符号化される。この方法による行を符号化する第２の実施例が図１２Ｃおよび図１２Ｄで示されている。
【００８６】
行の最初のエントリでエントリに関連して符号化位置を生成する代わりに、さらに多くのビット数で符号化された最新のエントリに関連する各エントリを生成することができる。図１２Ｅはそのような実施形態を示す。図１２Ｅの実施例では、３ビットがメモリバンクＡを指定する第１のエントリを実装するために使用される。次の２つのエントリは、２ビットを使用して３ビットで符号化されたその第１のエントリに対して生成される。したがって、第２および第３のエントリは１１および０１に符号化され、バンクＥおよびＣのＡ位置に相対する位置数をそれぞれ特定する。次の２つのエントリは１ビットで符号化され、２ビットで符号化される最後の位置に対して生成してもよく、第３のエントリはバンクＣを明示する。したがって、ＤはＣエントリから１つのみ離れた位置であることから（ＤおよびＢの残りの値を考慮する場合のみ）、第４のエントリはメモリバンクを「０」で符号化する。最終的には、ＤおよびＢの残りの値を考慮する場合のみ、Ｂ位置がＣ位置から２つ離れた位置であることから最終のエントリは「１」を含む。
【００８７】
きわめて大規模の仮想メモリマッピングテーブルでは、図１２Ａ〜図１２Ｅで示されている符号化システムは、仮想メモリマッピングテーブルのサイズを大幅に縮小させる。しかし、このように仮想メモリマッピングテーブルのサイズを縮小させることによって、仮想メモリマッピングテーブルのエントリを符号化および復号化するため、さらに複雑なロジックになってしまう。しかし、多くの実際の実施形態で使用されるきわめて大規模な仮想メモリマッピングテーブルに関しては、符号化および復号化のロジックを実装するために使用されるダイ領域はダイの容量よりはるかに小さく、この符号化スキームによって仮想メモリマッピングテーブルサイズを縮小させることによって節約される。
【００８８】
マッピングテーブルの実装
高速ロジックおよび高速メモリは、本開示の仮想メモリシステムに使用される仮想メモリマッピングテーブルを実装するため使用することができる。具体的には、図８のフローチャートに記載されているように、仮想メモリマッピングテーブルは段階８１０、段階８３０、段階８５０、段階８６０および段階８７０でアクセスする必要がある。多くの技術は、仮想メモリテーブルが実際にアクセスされる回数を減少させるために、さらに、仮想メモリテーブルの性能を向上させるために使用することができる。この節では、仮想メモリテーブルを実装するために使用できるいくつかの方法を開示する。
【００８９】
図８を再び参照すると、仮想メモリコントローラは段階８３０で仮想メモリテーブルを閲覧して書き込み操作がアクセスしている仮想メモリアドレスの現在のメモリバンクを求める。読み出し操作が前の段階８２０でアクセスした書き込み操作に関連する仮想メモリアドレスが同じメモリバンクにある場合、メモリバンクの競合が検知されることから、仮想メモリコントローラは段階８５０でマッピングテーブルにアクセスしてその同じ物理メモリの行に対して空きメモリバンクを求める必要がある。図６Ａの仮想メモリテーブル６２３を再び参照すると、書き込まれている仮想アドレスの現在のメモリバンクを配置するために単に読み出されたエントリとして、空きメモリバンクが仮想メモリテーブル６２３の同じ行に配置されることが明らかである。たとえば、システムは、仮想アドレス３０２に書き込む場合、行０２の３列でエントリを読み出してアドレス３０２を保存するメモリバンクを特定する必要がある。競合が発生する場合、システムは行０２の「ｅ」列からエントリを得て空きメモリバンクを特定する必要がある。したがって、システムは、書き込まれているメモリバンク仮想アドレスとこの行に対する空きメモリバンクとを、段階８３０で仮想メモリテーブル６２３の行全体を読み出すことによって同時に得ることがでる。
【００９０】
同じように、段階８６０および段階８７０で実行された仮想メモリテーブル６２３のアップデートは同じような単一のアクセスで実行することができる。具体的には、段階８２０（並列型に改良）で読み出された行全体が更新され、書き込みのために移動した仮想アドレスの新しい位置と空きメモリバンクの新しい位置とを含む仮想メモリテーブル６２３に再び書き込まれる行全体が更新される。したがって、段階８６０および８７０の更新は、仮想メモリテーブル６２３への単一の書き込みによって実行される。
【００９１】
仮想メモリテーブル６２３から行全体を読み出したり書き込んだりして読み出し操作と書き込み操作を前出のように２回組み合わせることによって、段階８１０で読み出し仮想アドレス対する読み出し、書き込みを行う仮想アドレスおよび空バンクの物理アドレスに対して合わせて読み出し（段階８３０および段階８５０）、書き込み操作を行う仮想アドレスおよび空バンクに結び付けられた更新される物理アドレスに対して合わせて書き込む（段階８６０および段階８７０）ことから、アクセスの数は３回まで減少した。これは、仮想メモリマッピングテーブルに対する２つの読み出し操作と１つの書き込み操作である。仮想メモリテーブルの２つの同一の複製を実装することによって、２つの読み出しは並列して実行することができ、仮想メモリテーブルの双方の複製に対して単一の書き込み操作を実行することができる。そこで、図１３Ａは２つの仮想メモリテーブル（仮想メモリテーブル１３２３および仮想メモリテーブル１３２４）を含む仮想メモリシステム１３００を示す。このようなシステムでは、各メモリサイクルに対して仮想メモリテーブルへのアクセスが２回のみであることから、仮想メモリテーブルは物理メインメモリ１３２０の２倍必要とするのみである。具体的に、単一の読み出し操作（実際に並列で２つの読み出し）と単一の書き込み操作がある。
【００９２】
これらの最適化の全てを実行した後に、１つの最後の実施形態が仮想メモリテーブルの速度をさらに上昇させるために使用することができる。仮想メモリテーブル自体は、本発明の技術を使用して実装することができる。したがって、本開示の技術は再帰的方法で使用してもよい。
【００９３】
上に記載されているように、仮想メモリテーブルに対して単一の読み出し操作と単一の書き込み操作があるのみである。書き込み操作は読み出し操作に依存するため、これら２つの操作は並列で実行できない。しかし、複数の異なるメモリアクセス要求がさまざまな異なる段階で同時に処理されるパイプラインの実施形態では、過去のメモリアクセスからの書き込みは、その後のメモリアクセスへの読み出しと組み合わせてもよい。したがって、単一の読み出しと書き込みが同時に実行される必要がある。まさにこれは、図７Ａ〜図７Ｄに記載されているように解決される問題である。したがって、図１３Ａで示されている仮想メモリシステム１３００を構築する全く同じ技術は、その仮想メモリシステム１３００で仮想メモリテーブル１３２３および１３２４を構築する再帰的方法で使用することができる。このように、仮想メモリテーブル１３２３および１３２４を実装するために使用されるメモリ技術は、メイン物理メモリ１３２０を実装するために使用されるメモリ技術と同じ速度で動作することができる。
【００９４】
同じ種類のメモリ技術は物理メモリとして仮想メモリマッピングテーブルを実装するために使用できることから、仮想メモリマッピングテーブルは実際に、物理メモリに統合することができる。この実施例は図１３Ｂの概念図に示されている。図１３Ｂでは、仮想マッピングテーブルが通常の保存に使用される他のメモリバンクと同じ物理メモリシステム１３２０内に実装されている。このような実施形態では、小規模の高速メタマッピングテーブル１３６０が仮想メモリコントローラ１３２１内で必要とされるだろうが、この高速メタマッピングテーブル１３６０はメイン仮想メモリマッピングテーブル１３２３および１３２４よりはるかに小さくなるだろう。
【００９５】
図１３Ａを再び参照すると、複製されたメモリマッピングテーブル（１３２３および１３２４）は、「ピンポン」構成で再び複製して配置してもよい。そのような実施形態の実施例を図１３Ｃに示す。メモリシステム１３００では、第２のセットの複製されたメモリマッピングテーブル（１３２５および１３２６）は仮想メモリコントローラ３１２１に追加される。ピンポン構成では、システムは２つの異なるメモリシステムの間で交互に書き込むため、一方のメモリシステムはメモリ書き込みを完了し、他方のメモリシステムは新しいデータを取り込むのに利用可能である。
【００９６】
さまざまな異なるメモリ技術は、開示する仮想メモリシステムのさまざまな異なる部分を実装するためを使用してもよい。一実施形態では、システムのメイン物理メモリに標準のＤＲＡＭを使用してもよい。別の実施形態では、メイン物理メモリシステムとして埋め込み型ＤＲＡＭを使用してもよい。
【００９７】
図１３Ｂに示されている再帰的な実施形態には埋め込み型ＤＲＡＭ（ｅＤＲＡＭ）が特に有利であり、仮想メモリコントローラ１３２１を実装するためのロジックが仮想メモリアドレスマッピングテーブルと同じダイに実装できるため、仮想メモリアドレスマッピングテーブルはメインデータストレージと同じ物理メモリ（ｅＤＲＡＭ）に保存される。
【００９８】
仮想メモリマッピングテーブルを加速するために使用されるさまざまな技術は、仮想メモリマッピングテーブルのメモリサイズを増大させるだろう。たとえば、複製テーブルを作成することによって必要とされるメモリのサイズが倍増する。パイプライン方法でシステムを実装すると、この場合もやはりサイズは少なくとも倍増する。しかし、必要とされるメモリのサイズをこのように増大させることは、高速ＳＲＡＭは埋め込み型ＤＲＡＭに比してビット単位のダイ領域が４〜６倍必要となりうるという事実のために行なってもよい。さらに、ＳＲＡＭ回路の歩留り率は埋め込み型ＤＲＡＭの歩留り率より低い傾向があるため、さらに多くの操作可能なチップを製造することが可能であれば、ＳＲＡＭの代わりに埋め込み型ＤＲＡＭを使用することが望ましいとことが多い。
【００９９】
デジタル半導体の設計者は、リスクを最小限にして開発時間を減少させるために、デジタル回路の１セットの所定のライブラリのセットを使用して作業する。デジタル回路のこれらのライブラリは、一般に必要とされるさまざまな機能を実行するためのさまざまな回路を含む。たとえば、メモリアレイ、プロセッサコア、デジタルプロトコルスタック、標準デジタル入出力システムおよび他の多くの機能のためのライブラリ回路がある。本開示の技術を実装するデジタル回路は、そのようなデジタル回路ライブラリに追加してもよい。きわめて有用な一実施例は、本開示の技術の実装を含む埋め込み型ＤＲＡＭ装置（ｅＤＲＡＭ）のデジタル回路ライブラリでエントリを生成することになる。そのようなデジタル回路ライブラリエントリは、完全に明確な方法で集積回路設計者に改良したメモリシステムを提供することになる。デジタル回路ライブラリエントリは、さらに多くのダイ領域を使用するという点を除いて、はるかに良好なメモリ性能をもたらす既存のｅＤＲＡＭ回路エントリと同じように見えることになる。
【０１００】
さまざまな技術は、メモリが超高速で動作する必要があるシステムのメモリ部分を実装するために使用してもよい。高速ＳＲＡＭは、メモリを必要とする高速部分のための基本技術として使用することができる。図１３Ｂのメタマッピングテーブル１３６０などのメモリ部分を実現する際に加速するために、オーバークロックＳＲＡＭを使用してもよい。オーバークロックＳＲＡＭは、小面積で実装される従来のＳＲＡＭであるため、短い導線でＳＲＡＭを高いクロック速度で動作させることを可能にする。また、超高速メモリサービスを必要とする部分に個々のフリップフロップ回路を使用してもよい。
【０１０１】
単一の読み出しと複数の書き込みの同時操作
上に記載されている仮想メモリシステムは、単一の同時読み出し操作を伴う１つ以上のメモリ書き込み操作を処理するように拡張することができる。さらに書き込み操作を処理するためには、各増設メモリバンクによって潜在するメモリバンクの競合を回避することができるため、メモリ読み出し操作とともに同時に発生する書き込み操作それぞれに対してメモリバンクを増設する必要がある。たとえば、同時に２つの書き込み操作と１つの読み出し操作を処理するためには、図１４Ａの実施形態に示されているように、２つの増設メモリバンクが必要である。
【０１０２】
図１４Ａは、１つの読み出し操作と２つの書き込み操作を同時に処理することができる仮想メモリシステムの１つの考えうる初期状態を示している。上に記載されているように、メモリアクセス要求が全て異なるメモリバンクアクセスする場合、全てのメモリ操作がそれぞれ独立したメモリバンクによって独立して処理してもよいことから、メモリバンクの競合はない。しかし、図１４Ａのメモリアクセスの実施例では、同じメモリバンク（メモリバンクＤ）内の仮想メモリアドレスにアクセスする次の３つのメモリ操作、仮想アドレス３０１からの読み出し、仮想アドレス３０３への書き込みおよび仮想アドレス３９８への書き込みが受け付けられる。
【０１０３】
仮想アドレス３０１からの読み出しを処理するために、メモリシステムコントローラ１４２１は、仮想メモリテーブル１４２３にアクセスして行０１の３列のエントリを読み出し、仮想アドレス３０１がメモリバンクＤに現在保存されていることを認識する。したがって、メモリシステムコントローラ１４２１はメモリバンクＤの行０１にアクセスし、仮想アドレス３０１に関連するデータを得て読み出し要求に応答する。メモリバンクＤは仮想アドレス３０１からのこのメモリ読み出しを処理することによって使用中であるため、書き込み操作は異なるメモリバンクを用いて処理してメモリバンクの競合を防ぐ必要がある。
【０１０４】
どのメモリバンク（使用中のメモリバンクＤ以外）が書き込み操作を処理するのに空いているのかを求めるために、メモリシステムコントローラ１４２１は仮想メモリテーブル１４２３にアクセスし、書き込み操作に対応する行のｅ１列およびｅ２列（空１および空２）のエントリを読み出す。したがって、メモリシステムコントローラは行０３および９８から列ｅ１およびｅ１のエントリを読み出す。この場合、双方の行は、メモリバンクＥおよびＦには行０３および９８の空のメモリバンクがあることを報告する。次に、メモリシステムコントローラ１４２１は、メモリ書き込み操作から利用可能であると示されたそれらのメモリバンクにデータを保存する。行０３および行９８がメモリバンクＥおよびＦが利用可能であることを報告したため、メモリシステムコントローラ１４２１は、別のメモリバンクの競合を回避するように書き込みを調整する必要があることに注意する。したがって、書き込み操作の一方がメモリバンクＥを使用し、他方の書き込み操作はメモリバンクＦを使用する。この特定の実施例では、仮想アドレス３０３への書き込みがメモリバンクＥに書き込まれ、仮想アドレス３９８への書き込みがメモリバンクＦに書き込まれる。そこで、仮想メモリテーブル１４２３は、仮想アドレス３０３および３９８（それぞれバンクＥおよびＦ）と、行０３および９８の新しい空のメモリバンク（両方の行のメモリバンクＤ）に対して新しい物理メモリ位置を反映するために更新する必要がある。アドレス３０１に対する読み出し操作と、アドレス３０３および３９８への書き込み操作とは図１４Ｂに示されている。
【０１０５】
１つの読み出し操作と２つの書き込み操作の別の実施例を図１４Ｃおよび図１４Ｄに示す。図１４Ｃは出発点として図１４Ｂの状態を用い、仮想アドレス２００に対する読み出し操作と、仮想アドレス２０３に対する書き込み操作と、仮想アドレス２９９に対する別の書き込み操作を受け付ける。システムは同じ方法で動作し、最終状態を図１４Ｄに示す。この場合、仮想アドレス２０３への書き込みにはバンクＤおよびＦが利用可能であり、仮想アドレス２９９への書き込みにはバンクＥおよびバンクＦが利用可能である。この場合、メモリシステムコントローラ１４２１は、バンクＤの行０３に仮想アドレス２０３に書き込むデータを保存し、列Ｅの行９９に仮想アドレス２９９に書き込むデータを保存した。
【０１０６】
潜在的なメモリバンクの競合を回避するために増設メモリバンクを物理メモリに追加して、さらに同時に書き込み操作を処理することができる。しかし結局のところ、仮想メモリテーブル１４２３へのアクセス（読み出されているデータが現在どこにあるのかを求め、書き込み操作に対して空きメモリバンクを配置する）の数はきわめて多くなるため、仮想メモリテーブル１４２３はオーバーロードするようになる。前段落に記載されているさまざまなメモリ技術は、仮想メモリテーブル１４２３の性能を向上させるために使用できることから、仮想メモリテーブル１４２３は要件を処理することができる。
【０１０７】
偶数倍の非対称性メモリの性能向上
さまざまなメモリ技術にはさまざまな異なるアーティファクトがある。本開示のシステムはそのようなメモリアーティファクトを利用し、最も効率的な方法でメモリを使用することができる。たとえば、いくつかのメモリシステムは書き込み操作の２倍で読み出し操作を実行することができる。これは、書き込み操作によってＤＲＡＭメモリ装置がメモリマトリクスからメモリの行全体を読み出し、その行で新しいデータを配置し、その行のメモリマトリクスに再び書き込む一方、読み出し操作は行を読み出して要求されたデータに応答するのみであるという事実によると考えられる。読み出し操作と書き込み操作に対して大きく時間要件が異なるメモリ装置は、読み出しと書き込みでは時間要件が等しくないため、「非対称性のメモリ装置」と呼んでもよい。本開示のメモリシステム技術は、非対称性のメモリ装置のこのアーティファクトを利用することができる。
【０１０８】
図７Ａ〜図７Ｄを再び参照すると、本開示に関する教示によって、メモリバンクの競合によってメモリシステムの性能に悪影響を与えないように、メモリシステムに単一のメモリバンクを追加することによって、メモリシステムは単一の読み出し操作と単一の書き込み操作を同時に処理することが可能となる。しかし、書き込み操作を完了するのに、読み出し操作の２倍時間がかかる場合、同じ技術は、単一の書き込み操作サイクルの間に、２つの読み出し操作と１つの書き込み操作を実行するために使用することができる。図１５Ａはそのようなメモリシステムがどのように動作するのかを示すタイミングチャートを示す。
【０１０９】
図１５Ａを参照すると、一連のメモリサイクルは単一の書き込み操作を実行するのに必要とされる時間としてスケジュールに沿って定義される。読み出し操作が書き込み操作の時間の半分以下を必要とする場合にのみ、単一の書き込み操作が実行されている間に２つの読み出し操作を連続して実行することができる。２つの読み出し操作が連続して実行されるため、２つの読み出し操作は互いに競合する可能性がないことに注意する。２つの連続した読み出し操作が行われている間、単一の書き込み操作を同時に実行することが可能である。２つの読み出し操作とメモリバンクの競合を回避するためには、書き込み操作によってデータを書き込むことができる少なくとも３つの異なる位置が必要である。したがって、そのような非対称性の実施形態は２つの増設メモリバンクを必要とし、これにより、既存の位置（いずれの書き込み操作とのメモリバンクの競合がない場合）、第１の空バンク（読み出し操作の１つとのメモリバンクの競合がある場合）または第２の空きメモリバンク（双方の読み出し操作とのメモリバンクの競合がある場合）に書き込むことができる。
【０１１０】
多くのメモリバンクを増設する技術は、同時的なさらなる書き込み操作を可能にするために使用することができる。図１５Ｂはタイミングチャートを示し、１つの読み出し操作の少なくとも２倍時間がかかる２つの書き込み操作は、２つの一連の読み出し操作と同時に実行される。図１５Ｂの２つの読み出し２つの書き込みシステムは、３つの増設メモリバンクを必要とする。
【０１１１】
また、これらの技術は不揮発性フラッシュメモリに適用することができる。書き込みが読み出し操作の最大１０倍時間がかかる可能性があることから、フラッシュメモリにはまさしく非対称性の側面がある。したがって、単一の書き込み操作が処理されている間にいくつかの読み出しを処理することができる。
【０１１２】
奇数倍の非対称性メモリの性能向上
いくつかのメモリシステムでは、読み出し時間と書き込み時間との間に、そのような偶数の差はないだろう。たとえば、１つのメモリシステムでは、読み出しは２ナノ秒を必要としてもよく、書き込みは３ナノ秒を必要としてもよい。それらの２つの時間値の最小公倍数（６ナノ秒）を用い、整数個の読み出し操作および書き込み操作を行うメモリサイクルを生成することができる。
【０１１３】
２ナノ秒の読み出し時間と３ナノ秒の書き込み時間の上記の実施例を使用すると、最小公倍数は６ナノ秒である。６ナノ秒になるようにメモリサイクルを定義して、そのメモリサイクルでは３つの読み出し操作と２つの書き込み操作を実行することができる。図１５Ｃはそのようなシステムの考えうる１つのメモリサイクルタイミングチャートを示す。図１５Ｃの特定のシステムに対して、２つの増設メモリバンクが必要である。具体的には、第１の書き込みは第１および第２の読み出し操作と重なって競合する可能性があるため３つの異なる利用可能な位置が必要である。同じように、第２の書き込み操作は、重複している第２および第３の読み出し操作が重なって競合する可能性があるため、書き込むことができる３つの利用可能な位置を必要とする。
【０１１４】
前出の実施形態では、必要に応じて増設メモリバンクを設けることによってさらに書き込み操作を追加することができる。第３の書き込み操作が図１５Ｃのシステムに追加される場合、１つの増設メモリバンクが必要となる。そのようなシステムのタイミングチャートを図１５Ｄに示す。第３の書き込み操作は、第１の読み出し操作、第２の読み出し操作または第１の書き込み操作と競合する可能性があるため３つの増設メモリバンクを必要とする。
【０１１５】
増設メモリバンクは、書き込み操作を追加するのに常に必要というわけではない。たとえば、図１５Ｅは図１５Ｄのタイミングチャートを示し、第４の読み出し操作がシステムに追加されている。第４の読み出し操作は、第３の読み出し操作後に連続して行うことができる。したがって、第３および第４の書き込み操作はそれぞれ２つの読み出し操作ともう１つの書き込み操作のみ重なる。したがって、図１５Ｄのシステムに別の書き込み操作を追加する場合、増設メモリバンクは必要ない。
【０１１６】
読み出し操作に続く書き込み操作
メモリが性能と比較して乏しいリソースの場合、いくつかの書き込み操作を読み出し操作後に連続して行うようにして、増設メモリバンクの必要性は減らすことができる。たとえば、読み出し操作と書き込み操作がそれぞれ２ナノ秒を必要とする場合、６ナノ秒のメモリサイクルの間に、２つの読み出し操作と２つの書き込み操作を実行することができ、１つの増設メモリバンクのみが必要とされる、６ナノ秒のメモリサイクルでシステムを構成することができる。したがって、性能低下と引き換えに、１回の（延長）メモリサイクルに２つのメモリ読み出しと２メモリ書き込みを実装するために１つの増設メモリバンクのみ必要であったことから、ハードウェア要件は減る。そのようなシステムのタイミングチャートが図１５Ｆに示されている。
【０１１７】
図１５Ｆで示されているように、１つの書き込み操作のみが１つの読み出し操作に重なる。したがって、そのようなシステムでは、読み出し操作と重なる１つの書き込み操作のみがその読み出し操作と競合しうるにすぎないことから、単一の増設バンクのみ必要である。第２の読み出し操作と第２の書き込み操作は、他の操作と重ならずに連続して実行されるため、他のあらゆる操作と競合しないだろう。
【０１１８】
必要とされるメモリバンクの容量を縮小させることのほかに、仮想メモリマッピングテーブルから必要とされるメモリ装置の性能も低下する可能性がある。上に記載されているように、本開示の技術を使用して実装されたシステムは一般に、仮想メモリマッピングテーブルを実装するために高速メモリシステムを必要とする。しかし、図１５Ｇで示されているように、第１の書き込み操作を遅延させることによって、仮想メモリマッピングテーブルの性能要件を減らしてもよい。具体的には、仮想メモリマッピングテーブルは、第１の読み出しデータの物理位置と第１の書き込みによってデータが保存される物理位置とをすぐに求める必要はない。その代わりに、仮想メモリマッピングテーブルは最初に第１の読み出し操作に対するアドレスを配置する。次に、第１の読み出し操作が実行されている間、仮想メモリマッピングテーブルは、第１の書き込み操作に対する物理的な書き込み位置と第２の読み出し操作に対する物理的な読み出し位置とを求めるためにアクセスされる。
【０１１９】
図１５Ｆおよび図１５Ｇの実施形態で示されているように、使用されていない別のメモリアクセス帯域がある。たとえば図１５Ｆでは、第２の読み出しと第２の書き込み操作が実行されているときには使用可能なメモリ帯域がある。この別の帯域は、増設メモリバンクに保存されたデータを、データの仮想アドレスに対する最初に割り当てられた物理メモリアドレスに戻すために使用してもよい。このようにして、可能な場合はデータがメイン物理メモリに戻されるため、増設メモリバンクの要件は減る。したがって、性能に影響を与えずに追加するメモリバンクのサイズを縮小させることが可能となりうる。
【０１２０】
図１５Ｆおよび図１５Ｇの方法は、他のさまざまに並べ変えた読み出しと書き込みを実装するために使用してもよい。たとえば、図１５Ｈは実施形態を示し、増設メモリバンクを１つのみ必要とする方法で２つの読み出しと３つの書き込みが単一のメモリサイクル内で実行される。同時に物理メモリにアクセスする、最大２つの異なるメモリアクセス操作があるため、増設メモリバンク１つのみが必要である。
【０１２１】
奇数倍の非対称性メモリの分割性能の向上
非対称性のメモリ装置による性能向上の技術と、分割性能向上による性能向上の技術とを組み合わせて、それぞれが独特の特徴を有する多数の異なるメモリシステムを構築してもよい。たとえば、図１５Ｉおよび図１５Ｊは、システムが非対称性のメモリ装置を使用して分割性能を向上させてもよい。図１５Ｉに示すように、書き込み操作は読み出し操作より終了するのに時間がかかる。２つの連続した書き込み操作が２つの連続した読み出し操作と並行して実行された場合、システムは２つのメモリバンクが必要となる。しかし、２つの連続した読み出し操作後に無駄な時間が費やされることに注意する。図１５Ｊに示すように、別の書き込み操作が２つの連続した読み出し操作後に追加される場合、システムはメモリサイクルをほんの僅かに延ばすことによって、２つの読み出し操作と３つの書き込み操作を実行してもよい。
【０１２２】
分割サイクルの種類
読み出しサイクルが２ナノ秒を必要とし、書き込みサイクルが６ナノ秒を必要とする場合、３の偶数倍の読み込みと３つの書き込みは６ナノ秒のメモリサイクルを使用して実施することができる。この実施例は図１５Ｍで示されている。このシステムは、６つの操作が６ナノ秒で完了していることから１操作当り１ナノ秒の独立した操作時間を設ける。しかし、この構成は５つの増設メモリバンクと多くのロジックを必要とする。
【０１２３】
システムが６ナノ秒のサイクル時間で２つの読み出しと２つの書き込みにまで減らす場合、４つのメモリ操作は６ナノ秒で実行される。この構成のタイミングチャートを図１５Ｌに示す。このシステムは３つの増設メモリバンクのみ必要とする。６ナノ秒で実行される４つメモリ操作は、１．５ナノ秒の分割サイクル時間を有すると考えることができる。
【０１２４】
図１５Ｌの分割システムをさらに改良することができる。システムが１２ナノ秒のサイクルで設計される場合、４つの読み出しと書き込みを実施することができる。図１５Ｍは、そのようなシステムのタイミングチャートを示す。図１５Ｍのシステムでは、最悪のシナリオは１つの書き込みが２つの読み出しに重なることであり、これにより増設メモリバンクが２つのみ必要とされる。したがって、図１５Ｍのシステムには１．５ナノ秒（１２ナノ秒／８操作）の分割サイクル時間があるため、メモリバンクは３つではなく２つのみ必要である。
【０１２５】
マッピングテーブルを使用しない転置ＸＯＲシステム
前出のメモリシステムでは、読み出される必要があるデータがメモリの１つの場所で存在しているのみであることから、メモリ読み出し操作は常に優先される。書き込み操作が前出のシステムで優先される場合、書き込み操作と読み出し操作との間のメモリバンクの競合によって、読み出し操作は書き込みが終了するまで待たされることになる。しかし、全メモリアドレスからのデータがメモリシステムの少なくとも２つの異なるメモリバンクで表される場合、読み出し操作は２つの異なる場所のいずれかから実行することが可能であるため、書き込み操作を優先することが可能となる。具体的には、潜在的な競合がメモリバンクの１つに読み出し操作と書き込み操作との間にある場合、読み出し操作は別のメモリバンクの位置で第２の複製データから要求されたデータにアクセスすることが可能である。書き込み操作が読み出し操作より優先するように動作するメモリシステムは、「転置」メモリシステムと呼んでもよい。
【０１２６】
そのような転置メモリシステムを構築することは一般的ではない。２つの異なるメモリバンクで単に全データを表すことは、複製メモリシステム全体を単に構築するにすぎない。複製メモリシステムは、メモリシステムを構築する効率的な方法では全くない。
【０１２７】
書き込み操作が同時の読み出し操作より優先する転置システムを構築するために新しいシステムを開示し、単一の増設高速メモリバンクが１セットの既存のメモリバンクに追加され、符号化された第２の複製データを保存する。符号化された第２の複製データは、排他的論理和演算と組み合わせられる全ての正常なメモリバンクからのデータの組み合わせであってよい。書き込みが優先され、排他的論理和が第２の複製データを符号化するために使用されることから、システムは「転置ＸＯＲ」メモリシステムと呼ばれる。図１６は転置ＸＯＲメモリシステムのブロック図を示す。
【０１２８】
図１６に示すように、１セットのアドレス０００〜３９９は１セットのメモリバンク１６０４として保存され、各メモリバンクはメモリアドレスの特定の最上位桁を有するアドレスに結び付けられる。（図１６では、バンク０は最上位桁が「０」である仮想アドレスに結び付けられ、バンク１は最上位桁が「１」である仮想アドレスに結び付けられるなどと続く。）メインメモリバンク１６０４のほかには、ＸＯＲメモリバンク１６３０がある。メモリコントローラ１６２１は、ＸＯＲメモリバンク１６３０への全てのメインメモリバンク（バンク０〜３）の対応する行に書き込まれているデータ全ての排他的論理和で符号化されたデータを保存する。転置ＸＯＲメモリシステムでは、データが元の位置に常に存在するため、詳細なマッピングテーブルは、各データが存在する場所を追跡するためにメモリコントローラ１６２１には必要とされない。しかし、メモリバンクがＸＯＲバンク１６２０で表される有効データがある場所を追跡するために、きわめて少規模のＸＯＲバンク内容テーブル１６３３のみが必要とされる。
【０１２９】
図１６のシステムでは、全ての書き込み操作はメインメモリ１６０４とＸＯＲバンク１６３０の対応する行に情報を保存する。メインメモリ１６０４への書き込みは、書き込み操作で特定されるアドレスを使用する。ＸＯＲバンク１６３０の対応する位置に対する書き込み操作は、最初にＸＯＲバンク１６３０の位置を読み出し、他のメモリバンクの対応する位置からの既存のデータに新データをＸＯＲ演算で論理的に組み合わせ、ＸＯＲバンク１６３０に対応する位置に新しく組み合わせた値を再び書き込む必要がある。したがって、高速メモリがＸＯＲバンク１６３０を実装するために必要である。ＸＯＲで符号化されたデータは、以下記載するように読み出し操作を処理するために使用される。
【０１３０】
図１６の転置ＸＯＲメモリシステム実施形態は、データは読み出し時に破壊されると、「過去に読み出した」メモリシステムとして、あるいは、メモリシステムのユーザが特定のメモリ位置の最後の読み出しがいつ行われるかを特定する必要がある「最新の読み出しが特定される」システムとして実装する必要がある。この理由は、メモリコントローラ１６２１がメモリシステムに書き込むときに空のメモリ位置に書き込む必要があるということである。メモリコントローラ１６２１は、最初にメモリ位置から既存のデータを最初に読み出して、ＸＯＲバンク１６３０からそのデータを削除し、次に、メインメモリの位置およびＸＯＲバンク１６３０の位置に新しいデータを書き込む時間がないことから、単に空のメモリ位置に書き込むことができるにすぎない。
【０１３１】
読み出し要求と書き込み要求が受け付けられ、メモリバンクの競合を引き起こさない場合、読み出し操作および書き込み操作はメインメモリバンク１６０４で同時に行うことができる。しかし、読み出しと書き込みは、ＸＯＲバンク１６３０にアクセスすることを必要としてもよい。上に記載するとおり、書き込み操作は常にＸＯＲバンク１６３０にアクセスしてＸＯＲで暗号化されたデータをＸＯＲバンク１６３０に追加する必要がある。読み出し操作がそのメモリ位置の最後の読み出しである（あるいはこの実装が常にデータを破壊する「過去に読み出した」実装である）場合、読み出し操作もＸＯＲバンク１６３０にアクセスしてＸＯＲバンク１６３０からＸＯＲ表記のデータを削除する必要がある。読み出し操作と書き込み操作によって、ＸＯＲバンク１６３０を読み出し、変更し、書き込んでもよいため、ＸＯＲバンクは単一のメモリサイクル内の２つの読み出し操作と２つの書き込み操作を支援する必要がある。したがって、ＸＯＲバンクは４ポートメモリ装置を必要としてもよい。
【０１３２】
メモリバンクの競合が発生する（メモリ読み出し操作とメモリ書き込み操作が同じメモリバンク内のアドレスを対象にする）と、メモリ書き込み操作が優先となり、メインメモリ１６０４内のメモリバンクにアクセスする。さらに、書き込み操作はＸＯＲバンク１６３０内の対応する位置を更新する必要がある。メモリ読み出し（書き込みがアクセスしているメインメモリ１６０４内の同じバンクにアクセスすることができない）は、ＸＯＲバンク１６３０からＸＯＲ符号化されたデータの対応する位置を検索し、ＸＯＲバンク１６３０に符号化された有効データを有する他のメモリバンクの対応する位置からデータを検索し、次にＸＯＲコード化されたデータを復号化して要求されたデータを得ることによって処理される。復号化は、このデータの全てをＸＯＲ操作と組み合わせることによって実行される。ＸＯＲバンク内容テーブル１７３３は、ＸＯＲバンク１６３０の対応する位置に有効データを現在有するメモリバンクのみを選択するために使用されることに注意する。これがこのメモリ位置対する最新の読み出しではない場合、ＸＯＲバンク１６３０の対応する位置は変化しなくてもよい。しかし、これがこの特定の位置に対する最新の読み出しである場合、読み出し操作は、単に読み出されたデータではなく有効データを有する他の行からのデータを含むＸＯＲで符号化されたデータを再び書き込む必要がある。
【０１３３】
転置ＸＯＲメモリシステムの動作の実施例は、図１７Ａ〜図１７Ｆに記載されている。図１７Ａは空の初期状態のメモリシステムを示す。第１の書き込み操作は、アドレス位置３０２を指定したメモリシステムに受け付けられる。メモリコントローラ１７２１がメインメモリ内のメモリ位置３０２にデータを書き込み、ＸＯＲバンクの同じ行にデータの排他的論理和をとる。ＸＯＲバンク１７３０が空であるため、ヌルとの排他的論理和がとられることから、ＸＯＲバンク１７３０の０２行はアドレス３０２に書き込まれた同じデータを含んでいるにすぎない。次に、メモリコントローラ１７２１は、ＸＯＲバンク内容テーブル１７３３を更新し、ＸＯＲバンク１７３０の０２行がメインメモリバンク３の行０２からのデータを含むことを示す。位置３０２への書き込み後の最終状態は図１７Ｂに示される。
【０１３４】
図１７Ｃは、図１７Ｂからの状態からアドレス１０２への書き込みを受け付けるシステムを示す。データがメインメモリの１０２位置に書き込まれ、ＸＯＲバンク１７３０も更新される。具体的には、ＸＯＲバンク１７３０の行０２は読み出され、排他的論理和演算を用いて新しいデータと組み合わせられ、次に、ＸＯＲバンク１７３０の行０２に再び書き込まれる。また、ＸＯＲバンク内容テーブル１７３３は更新され、この時点でＸＯＲバンク１７３０の行０２は、バンク１およびバンク３からのデータを含むことを反映する。位置１０２への書き込み後の最終状態は図１７Ｄに示される。
【０１３５】
このようにして、メモリシステムは埋まり続ける。図１７Ｅは、さらに多くのデータを追加した後のメモリシステムの例示的な状態を示す。図１７Ｅのシステムは、図に示すようにアドレス１００への書き込みとアドレス１０４からの読み出しを同時に受け付けてもよい。書き込みが優先され、書き込み操作に関連するデータはメインメモリバンク内のアドレス１００に書き込まれる。さらに、ＸＯＲバンク１７３０からの００行が読み出され、アドレス１００に書き込まれるデータ値との排他的論理和がとられ、ＸＯＲバンク１７３０の００行に再び書き込まれ、ＸＯＲバンク内容テーブル１７３３は更新され、この時点でＸＯＲバンク１７３０の行００がメモリバンク１からのデータを含むことを示す。
【０１３６】
アドレス１０４からの読み出しは、位置１００への書き込みとのバンクの競合のため、メインメモリ内のアドレス１０４からデータを読み込むことによって直接処理することができない。読み出しは、ＸＯＲバンク１７３０と他のメインメモリバンクを使用して処理する必要がある。メモリコントローラは、最初にＸＯＲバンク内容テーブル１７３３の行０４を読み出し、どのメインメモリバンクがＸＯＲバンク１７３０の行０４で表されるデータを有するのかを特定する。ＸＯＲバンク内容テーブル１７３３の行０４は、バンク１、２および３が全てＸＯＲバンク１７３０の行０４に排他的論理和がとられたデータを有することを明示する。次に、メモリコントローラは、ＸＯＲバンク１７３０の行０４とＸＯＲバンク１７３０の行０４で表されるデータを有する他のバンク（バンク２および３）の０４行を読み込む。したがって、メモリコントローラはバンク２、バンク３およびＸＯＲバンク１７３０の行０４を読み込む。これらの３つの位置から読み出されたデータは共に排他的論理和がとられ、読み出し要求に応答するために使用されるアドレス１０４から元のデータを得る。次に、メモリコントローラは、バンク２および３からの行０４のデータの排他的論理和をとり、次いでＸＯＲバンクＸＲ３０の列０４にその値を再び書き込む。最終的には、ＸＯＲバンク内容テーブル１７３３は更新され、アドレス１０４からのデータはもはやＸＯＲバンク１７３０で表されないことを示す。
【０１３７】
上に記載されているように、システムは常に、最新の読み出し操作（データがメインメモリバンクから読み出されるか、ＸＯＲバンクから読み出される）後にＸＯＲバンクからデータを削除し、次の書き込みのためにその位置を空にする。過去に読み出したメモリシステムでは、メモリコントローラは全ての読み出し操作後にＸＯＲバンクからの表示を削除することになる。代替のシステムでは、メモリユーザは、別の信号線を使用して読み出しがデータの最新の読み出しであるかを特定することが可能である。読み出しが最新の読み出しでない場合、データはメインメモリ位置に残り、符号化されたＸＯＲバンクで示される。したがって、メモリユーザは、そのデータを破壊せずにアドレスから繰り返して読み込むことが可能である。しかし、プロセッサは、そのアドレスにあらゆる新しい情報を書き込む前にそのアドレスに対して「最新の読み出し」操作を実行することを確実にすることが必要となる。そうでない場合、ＸＯＲバンクの対応する行のデータは破損するようになる。この破損はその特定のアドレスに関連するデータに悪影響を与えるのみならず、他の全てのメモリバンクからの同じ行に関連するＸＯＲバンクで表されるデータも破損することになることに注意する。メインメモリ位置のデータは、後の書き込み操作が受け付けられる場合に上書きされることになるため変える必要はない。
【０１３８】
図１６〜図１７Ｆを参照して開示するＸＯＲシステムはいくつかの用途で有利になるが、他の用途では理想的でない特徴を有する。ＸＯＲシステムの１つの良好な特徴は、大規模のマッピングテーブルがメモリコントローラに保存される必要がないということである。その代わりに、各メモリアドレスの１ビットを含むＸＯＲバンク内容テーブルがまさに必要である。ＸＯＲシステムは、異なるメモリバンク（ＸＯＲバンクを含む）の全てからの並列データパスは、適切にＸＯＲバンクを使用するためにメモリコントローラにルーティングする必要があるため、桁幅のあるデータ値に対して理想的ではない。さらに、ＸＯＲシステムは、メモリバンクの競合が毎回発生し、ＸＯＲバンクと、読み出されている同じ行に対してＸＯＲバンクで表されるデータを有する他のあらゆるメモリバンクとに書き込まれているメモリバンクにアクセスするため、他のシステムより多くの電力を使用する可能性がある。
【０１３９】
制限されないメモリ仮想化システム
上に記載したさまざまなメモリシステムでは、メモリシステムは異なるメモリバンクとそのメモリバンクの行（列の場合もある）に編成される。そこで、メモリバンクの競合によってメモリシステムの性能が低下しないようにするために、１または複数の同じような増設メモリバンクがメモリシステムに追加される。そこで、仮想メモリマッピングテーブルは、さまざまな異なる仮想メモリアドレスが物理メモリシステムの現在表されているところを追跡するために使用される。
【０１４０】
仮想メモリマッピングテーブルのサイズを制限するために、上に記載した実施形態は、各仮想メモリアドレスを保存できる物理メモリ位置を制限する。たとえば、図６Ａおよび６Ｂの仮想メモリシステムでは、メモリシステムに保存された各仮想メモリアドレスは、単に同じ最下位の２桁を有する物理アドレス行で表すことができるにすぎない。たとえば、アドレス１０１は、単に物理メモリのバンクＡ〜Ｅの０１行に保存できるにすぎない。この制限は利点をもたらす（メモリマッピングテーブルのサイズを縮小させる）が、そのような制限がないシステムを構成してもよい。
【０１４１】
図１８は実施例メモリシステムを示し、ありとあらゆる仮想メモリアドレスが物理メモリアドレスのいずれかで表されることを可能にする。仮想メモリテーブル１８２３に言及すると、仮想アドレスの最大有効桁の列と仮想アドレス最下位の２桁の行とをアクセスしてあらゆる仮想アドレスの物理位置を求めて、仮想アドレスが配置されるメモリバンクと行を特定するテーブルのエントリを得ることができる。あらゆる仮想アドレスはあらゆる物理アドレスに配置することができるため、仮想メモリテーブル１８２３には「空」の列を必要としないことに注意する。その代わりに、さまざまな異なる空の物理アドレスの間で関連する相違点がないことから、簡単な非順序セットに空の物理メモリアドレスを保存できる。しかし、代替実施形態では、空の物理アドレスは使用可能なリストまたはデータ構造のような他の典型的なメモリ割当てリストに保存することができる。
【０１４２】
一見したところでは、図１８のメモリシステムは、仮想メモリテーブル１８２３が極めて大規模であるためそれほど有用でないように思われることがある。しかし、実際の仮想メモリアドレスによって参照されるデータのサイズがきわめて大きい場合、そのようなシステムには有用な用途がある。たとえば、仮想アドレスのそれぞれが大きなブロックのメモリを参照する場合、図１４Ａのメモリシステムにはいくつかの有用な用途があるだろう。
【０１４３】
制限されないメモリシステムの１つの例示的な使用は、ダイナミックメモリブロック配置のためのものである。最近のコンピュータシステムでは、多くのさまざまなコンピュータ資源（プロセッサ時間、メモリ、出力装置など）とそのコンピュータ資源を使用する多くのさまざまな独立したプロセスとがある。コンピュータオペレーティングシステムの主要機能の１つは、コンピュータ資源を要求するさまざまな異なるプロセスへのコンピュータ資源の割り当てを調整することである。「Ｃ」ファミリーのプログラミング言語では、ｍａｌｌｏｃ（）関数は、オペレーティングシステムがプロセスにいくらかの追加メモリを与えることを動的に要求するプロセスによって使用される。最近のマルチコアプロセッサによって、さまざまなプロセスは実際に、物理的に異なるコアで動作することができることから、時分割多重化方式を用いて完全に同時に実行されているのであって、それは単に同時のように見えているのではない。独立したプロセスが実現しうる最高速度で動作することを可能にするため、図１４Ａのメモリシステムは、さまざまなメモリバンクからメモリブロックを割り当てるために使用してもよいことから、同じメモリバンクに保存されたデータにアクセスを試みる２つの独立したプロセスによって引き起こされるメモリバンクの競合はない。
【０１４４】
別の用途では、開示しているメモリシステムの技術はメモリブロックの連結リストとともに使用することができる。メモリブロックの連結リストは、メモリ割り当てシステムおよびパケットバッファリングキューで広く使用される。本開示のメモリシステムでは、システムは各仮想メモリの位置が存在する特定の物理メモリバンクを追跡する。したがって、メモリシステムは、メモリバンクの競合を最小限にするように連結リストにメモリブロックを割り当てるために使用することができる。
【０１４５】
一実施形態では、メモリシステムは、メモリユーザ（データパケットがキューイングされるプロセスなど）が論理アドレスを使用してメモリ要求を生成することを可能にする。これらのさまざまなメモリキュープロセスは、論理アドレスを使用してメモリのブロックを要求することができる。たとえば、３つのメモリキュープロセス０、１および２（データパケットキューに関連するプロセスなど）があり、それぞれ異なるメモリキュープロセスが簡易な論理アドレスを使用してメモリのブロックを要求する場合、メモリシステムは各メモリ要求および対応するメモリブロックの追跡をしてもよい。各メモリ要求は、この（キュー識別子、論理アドレス）ようなメモリキュープロセス識別子とそのキューの論理ブロックアドレスによって識別することができる。したがって、第１のメモリキュープロセスが第１（論理アドレス０）のメモリ要求をする場合、メモリシステムはその第１のメモリ要求に（０，０）を結び付けられる。その（０，０）識別子は、得られたメモリブロックの物理アドレスに結び付けられる。同じメモリキュープロセスが第２（論理アドレス１）のメモリ要求を要求する場合、メモリシステムは要求に応答して得られたメモリブロックアドレスに（０，１）を結び付けられる。
【０１４６】
そのようなシステムに関して、メモリシステムはインテリジェントメモリの割り当てを決定してもよい。たとえば、メモリシステムは、どのメモリキュープロセスが各メモリ要求をするかを認識しているため、メモリキュープロセスが一般に一度に１つのメモリブロックにのみアクセスし、メモリバンクの競合はないことから、同じメモリバンクからのメモリブロックによって同じメモリキュープロセスからの要求に応答することを試みることができる。同じように、さまざまなメモリキュープロセスがそれぞれ割り当てられたメモリブロックに同時メモリアクセスを実行するため、メモリシステムは異なるメモリバンクから他のメモリキュープロセスにメモリブロックを与えることを試みることになる。このようにしてメモリブロックが異なるメモリバンクからのものである場合、性能を減少させるメモリバンクの競合がない。言うまでもなくその一方で、メモリキューは、さまざまなメモリバンク全てにわたる要求の負荷バランスを行い、全てのキューに対してメモリの帯域幅利用を最大限にするために、さまざまなメモリバンクからのデータを得ることができる。
【０１４７】
一部制限されるメモリ仮想化方式
各仮想メモリアドレスを物理メモリに配置することが可能な位置がきわめて制限される完全に制限されるメモリシステムと、あらゆる仮想メモリアドレスをあらゆる物理メモリ位置に配置することが可能な制限されないメモリシステムとの間には、さまざまな一部制限された異なる実施形態がある。たとえば、仮想アドレスが特定の行に常に存在することを制限する（図６Ａおよび６Ｂの実施形態に示すように）代わりに、部分的に制限されたメモリシステムは、オフセットビットによって明示されるように仮想アドレスが特定の行または近隣の行で表されることを可能にしてもよい。たとえば、２つのオフセットビットを用いて、特定の仮想アドレスは特定の指定された行または近隣の１〜３つの行に存在するように明示してもよい。たとえば、１０は指定された行の前２つの行を明示してもよく、１１は指定された行の前の１つの行を明示してもよく、００は指定された行を明示してもよく、０１は指定された行の後の行を明示してもよい。
【０１４８】
書き込みバッファのみ競合回避システム
良好なメモリインタリーブシステムと十分なランダムメモリアクセスパターンを用いて、増設メモリバンクを必要としないで高速メモリシステムを実装してもよい。その代わりに、（願わくは）稀なメモリバンクの競合に対処するために書き込みバッファを使用してもよい。
【０１４９】
図１９は、同時にアクセス可能なさまざまなメモリバンクで構成される物理メモリ１９２０とメモリコントローラ１９２１で構成されるメモリシステム１９００の実施例を示す。メモリシステム１９００は、１つ以上の同時のメモリ操作を処理するように設計される。簡易な実施形態では、メモリシステム１９００は、１つの読み出しメモリ操作と１つの書き込みメモリ操作を処理してもよい。同時読み出し操作および書き込み操作がさまざまなメモリバンクにアクセスする場合のみメモリバンクの競合はなく、読み出し操作と書き込み操作を同時に実行することができる。
【０１５０】
読み出し操作と書き込み操作が同じメモリバンクに配置されるメモリ位置にアクセスを試みる（アドレス１００への書き込みとアドレス１０４からの読み出しによって示すように）場合はメモリバンクの競合があるため、２つの操作のうちの１つしか行うことができない。読み出し操作は、その１つの特定のメモリの位置にアクセスすることによってのみ処理可能であるため、読み出しは優先されることから、メモリコントローラはアドレス１０４から読み込んで、読み出し要求に応答する。書き込み操作は、メモリバンクの競合のため物理メモリ１９２０を用いて処理することができず、その代わりに図１９に示すように書き込みバッファ１９３０に配置される。書き込み操作が書き込みバッファ１９３０内に存在している間にアドレス１００から読み出されたメモリが受け付けられる場合、メモリコントローラは書き込みバッファ１９３０からのデータを用いて読み出し要求に応答する。
【０１５１】
バッファ１９３０内のアドレス１００に書き込み操作を配置した後のメモリサイクルでは、メモリコントローラ１９２１は、書き込みバッファ１９３０から物理メモリ１９２０にデータを移動させることによって書き込み操作を完成することを試みる。これは、書き込み操作のアドレスとメモリバンクの競合がない場合のみ、その後のメモリサイクルで実行することができる。たとえば、次のメモリサイクルでシステムがアドレス２０４からの読み出しとアドレス４０１への書き込みを受け付ける場合、アドレス１００への過去の書き込みからのデータは、アドレス２０４からの読み出しとアドレス４０１への書き込みによって同時に処理することができる。しかし、読み出し操作または書き込み操作が同じメモリバンクにアクセスする場合、書き込み操作データは書き込みバッファ１９３０に残ることになる。
【０１５２】
メモリサイクルでは、書き込み操作を書き込みバッファ１９３０に追加し、書き込みバッファ１９３０から削除してもよいことに注意する。たとえば、メモリシステムでは、図１９で示されているように、書き込みバッファ１９３０内のアドレス１００への書き込み操作があり、次に、アドレス４００からの読み出しとアドレス４９９への書き込みを受け付ける場合、メモリシステムは書き込みバッファ１９３０への読み出しと書き込みを実行する。具体的には、アドレス４９９への書き込み操作は（アドレス４００からの読み出しとの競合のため）書き込みバッファ１９３０に追加され、データが物理アドレス１００に書き込まれるために書き込みバッファ１９３０内のアドレス１００への書き込み操作は削除される。さらに、同じメモリサイクルの間、書き込みバッファ１９３０からの複数の書き込み操作を物理メモリ１９２０に書き込んでもよい。たとえば、前出の実施例で書き込みバッファ１９３０もアドレス２０５への書き込み操作を含んだ場合、メモリコントローラ１９２１は、アドレス４００から読み出しを実行している間にアドレス１００およびアドレス２０５に同時に書き込むことが可能である。
【０１５３】
書き込みバッファがメモリ競合を回避するために使用されるそのようなメモリシステムでは、さまざまなメモリバンクがあるためにバンクの競合が減少して、メモリバンクがさまざまなメモリバンクの中でメモリアクセスを展開するために十分にインターリーブされて、メモリアクセス要求は十分ランダムに行われる場合のみ、システムは高速性能を供給してもよい。しかし、全く同じメモリバンクへの長時間にわたる読み出し操作および書き込み操作が受け付けられる場合、書き込みバッファ１９３０は最終的に満杯となることから、バッファリングされた書き込み操作のいくつか（全て）を再び書き込むために、メモリシステムは最終的にメモリ要求を中断するか、あるいは減速させる必要がある。この状況に陥る確率を減少させるために、ハッシュメカニズムを使用してランダム化の特徴をシステムに追加してもよい。具体的には、メモリコントローラ１９２１は、アドレスをランダム化するが物理メモリ内のアドレスと位置との１対１の関係を維持しているハッシュメカニズムに、仮想アドレスまたは物理アドレスを渡してもよい。このようにして、たとえアドレスの特定のパターンを受け付けても、ハッシュメカニズムはアドレスをランダム化することにより、度重なるメモリバンクの競合を引き起こすメモリアクセスパターンの確率を減少させる。
【０１５４】
さらに小容量の増設メモリバンクを備えるメモリシステム
図６Ａおよび図６Ｂの仮想メモリシステムでは、メモリシステムには物理メモリ６２０の他のメモリバンクと同じサイズの増設メモリバンク（バンクＥ）がある。このようにして、メモリバンクの競合がある場合に書き込むことができる異なるメモリバンクには、別のメモリ位置が常にある。しかし、多数のメモリバンクがある場合、メモリバンクの競合がほとんどない可能性があるため、フルサイズの増設バンクは必要としなくてもよい。
【０１５５】
図２０は仮想メモリシステム２０００を示し、増設メモリバンク（バンクＥ）には、メインメモリバンクの２行毎に１列があるのみである。メモリバンクの競合がない限り、バンクＥは全く必要ではない。メモリバンクの競合が発生する場合、書き込み操作からのデータは増設メモリバンクＥの行の１つに配置してもよい。その後のメモリバンクの競合が発生し、指定された増設メモリバンクの行が既に使用されるために制限されずに利用できる位置がない状況を防ぐために、仮想メモリコントローラ２０２１は、データをバンクＥからメインメモリ領域２００４の元の場所に動かすことを試みてもよい。たとえば、メモリバンクＥの第１の行が仮想アドレス３０１に対するデータを保存し、アドレス２０４からの読み出しとアドレス００２から書き込みが受け付けられる（全て図２０に示すように）場合、アドレス２０４からの読み出しとアドレス００２への書き込みを実行している間に、仮想メモリコントローラ２０２１はメモリバンクＥ内のアドレス３０１に関連するデータをメモリバンクＤ（アドレス３０１が最初に表される）に再び書き込んでもよい。
【０１５６】
さらなる保護を目的として、メモリバンクが競合し、バンクＥの指定された行が既に使用されているためにいくつかのデータをすぐに書き込む場所がない場合は、書き込みバッファ２０３０は時間を処理するために追加してもよい。バンクＥのように、仮想メモリコントローラ２０２１は、書き込みバッファ２０３０からメインメモリ領域２００４内の元の場所にデータを移動させることを試みてもよい。サイズが小さい増設メモリバンクＥと追加されたバッファ２０３０との利用の間、メモリバンクの競合によってメモリシステム２０００が遅延してしまう確率をきわめて低くすることができる。
【０１５７】
書き込みバッファのみを使用した前出のメモリシステムのように、サイズが小さい増設バンクを備えるメモリシステムはハッシュメカニズムの使用から便益を得てもよい。ハッシュメカニズムはメモリアクセスパターンをランダム化することから、一連の度重なるメモリバンクの競合に遭遇する確率は減少する。
【０１５８】
前出の技術の開示は、説明目的であり限定しないことを意図する。たとえば、上記の実施形態（またはその１または複数の態様）は、互いに組み合わせて使用してもよい。上の記載を読めば、他の実施形態は当業者に明らかとなる。したがって、本願の特許請求の範囲は、請求項の主題の均等物とともに請求項を参照して定めるべきである。本願の特許請求の範囲では、「含む（ｉｎｃｌｕｄｉｎｇ）」と「そこで（ｉｎ  ｗｈｉｃｈ）」という用語は、それぞれの用語「含む（ｃｏｍｐｒｉｓｉｎｇ）」と「そこで（ｗｈｅｒｅｉｎ）」と同等のわかりやすい表現として用いる。また、本願の特許請求の範囲では、用語「含む（ｉｎｃｌｕｄｉｎｇ）」および「含む（ｃｏｍｐｒｉｓｉｎｇ）」はオープエンド形式であり、すなわち、請求項でそのような用語の前に列挙される要素を含むシステム、装置、物品またはプロセスは、特許請求の範囲内とみなす。さらに、本願の特許請求の範囲では、「第１」、「第２」および「第３」という用語は、単なるラベルとして使用され、その対象に数値要件を課すことを意図しない。
【０１５９】
要約は、読み手が技術開示の本質をすぐに確認できることを要求する３７Ｃ．Ｆ．Ｒ．１．７２（ｂ）に従って記載する。要約は、特許請求の範囲または意味を解釈したり、あるいは限定したりするためには使用されないという理解とともに提出される。また、上記の発明を実施するための形態では、さまざまな特徴を集めて開示内容を簡素化してもよい。これは、請求していないが開示している特徴が、いずれかの請求項にとって必須であることを意図すると解釈するべきでない。むしろ、本発明の主題が開示する特定の実施形態の全ての特徴より少なくてもよい。したがって、本願の特許請求の範囲は、本願明細書によって発明を実施するための形態に組み入れられ、各請求項はそれ自体が別々の実施形態として存在する。
【符号の説明】
【０１６０】
１００  コンピュータシステム
２２０、５００、６００、１３００、１６００、１８００、１９００、２０００  仮想記憶システム
６０４、１３０４、１６０４、１８０４、２００４  仮想メモリアドレス空間
７２３、９２３、１０２３、１３２３、１３２４、１３２５、１３２６、１４２３  仮想メモリテーブル
【図１】
2013513884.tif 000003
【図２】
2013513884.tif 000004
【図３Ａ】
2013513884.tif 000005
【図３Ｂ】
2013513884.tif 000006
【図４Ａ】
2013513884.tif 000007
【図４Ｂ】
2013513884.tif 000008
【図５】
2013513884.tif 000009
【図６Ａ】
2013513884.tif 000010
【図６Ｂ】
2013513884.tif 000011
【図７Ａ】
2013513884.tif 000012
【図７Ｂ】
2013513884.tif 000013
【図７Ｃ】
2013513884.tif 000014
【図７Ｄ】
2013513884.tif 000015
【図８】
2013513884.tif 000016
【図９】
2013513884.tif 000017
【図１０】
2013513884.tif 000018
【図１１Ａ】
2013513884.tif 000019
【図１１Ｂ】
2013513884.tif 000020
【図１１Ｃ】
2013513884.tif 000021
【図１１Ｄ】
2013513884.tif 000022
【図１２Ａ】
2013513884.tif 000023
【図１２Ｂ】
2013513884.tif 000024
【図１２Ｃ】
2013513884.tif 000025
【図１２Ｄ】
2013513884.tif 000026
【図１２Ｅ】
2013513884.tif 000027
【図１３Ａ】
2013513884.tif 000028
【図１３Ｂ】
2013513884.tif 000029
【図１３Ｃ】
2013513884.tif 000030
【図１４Ａ】
2013513884.tif 000031
【図１４Ｂ】
2013513884.tif 000032
【図１４Ｃ】
2013513884.tif 000033
【図１４Ｄ】
2013513884.tif 000034
【図１５Ａ】
2013513884.tif 000035
【図１５Ｂ】
2013513884.tif 000036
【図１５Ｃ】
2013513884.tif 000037
【図１５Ｄ】
2013513884.tif 000038
【図１５Ｅ】
2013513884.tif 000039
【図１５Ｆ】
2013513884.tif 000040
【図１５Ｇ】
2013513884.tif 000041
【図１５Ｈ】
2013513884.tif 000042
【図１５Ｉ】
2013513884.tif 000043
【図１５Ｊ】
2013513884.tif 000044
【図１５Ｋ】
2013513884.tif 000045
【図１５Ｌ】
2013513884.tif 000046
【図１５Ｍ】
2013513884.tif 000047
【図１６】
2013513884.tif 000048
【図１７Ａ】
2013513884.tif 000049
【図１７Ｂ】
2013513884.tif 000050
【図１７Ｃ】
2013513884.tif 000051
【図１７Ｄ】
2013513884.tif 000052
【図１７Ｅ】
2013513884.tif 000053
【図１７Ｆ】
2013513884.tif 000054
【図１８】
2013513884.tif 000055
【図１９】
2013513884.tif 000056
【図２０】
2013513884.tif 000057
【国際調査報告】
2013513884.tif 000058