JPH11317069A - Ｆｉｆｏ記憶装置 - Google Patents

Abstract

(57)【要約】 【課題】 フレームバッファメモリのバンクでの再ペー
ジングを隠してページングオーバヘッドを低減する。 【解決手段】 コンピュータグラフィックスディスプレ
イシステム１０が、ホストＣＰＵ１２から表示装置２１
までの構成を有して、第１（第２）記憶素子が、ＦＩＦ
Ｏ記憶装置の入力ポート１０１から１（２）番目のエン
トリ集合を受け取って、各エントリを記憶領域に格納す
る。書込ポインタによってアドレス指定される第１およ
び第２記憶素子の記憶領域にエントリが格納される。第
１読取ポインタデバイスは、最終的にＦＩＦＯ記憶装置
の第１出力ポートを通じてＦＩＦＯから出力されるエン
トリを第１記憶素子内の記憶領域から読み出すためのア
ドレスを決定する。第２読取ポインタデバイスは、２番
目のエントリ集合内にあるタグ付きエントリに基づいて
第２記憶素子内のアドレスを計算して読み出す。これら
のエントリが第２出力ポートを通じてＦＩＦＯ記憶装置
から出力される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はグラフィックス記憶
システムに係り、特に、フレームバッファメモリのバン
クに対する再ページングを隠してページングオーバヘッ
ド低減のためのグラフィックス記憶システム用インテリ
ジェンス内蔵ＦＩＦＯ（先入れ先出し）記憶装置に関す
る。

【０００２】

【従来の技術】従来、多くの高性能グラフィックス記憶
システムは、フレームバッファメモリ用に同期式グラフ
ィックスランダムアクセスメモリ（ＳＧＲＡＭ）を使用
している。これらの装置は一般的に２バンクアーキテク
チャを使用しており、一方のバンク内のページがアクセ
スされている間に他方のバンク内のページ（すなわち、
バンク内の特定の行アドレス）をクローズして再オープ
ン（再ページング）することが出来る。メモリコントロ
ーラが両バンク（通常はバンク０およびバンク１であ
る）に対する要求に応じられるように、通常の要求がソ
ートされて別々のバンクに判別される。具体的には、バ
ンク０に対する要求は一つのＦＩＦＯ記憶素子（ＦＩＦ
Ｏ）に格納され、バンク１に対する要求は別のＦＩＦＯ
記憶素子（ＦＩＦＯ）に格納される。

【０００３】次に、メモリコントローラは各ＦＩＦＯ記
憶素子（ＦＩＦＯ）の出力を受け取る。そして、メモリ
コントローラは行を比較して、一方のバンク上のページ
がアクセスされている間に他方のバンクに新しいバンク
をオープンできる。この場合、バンクのいずれかを再ペ
ージングする必要があるかを判断する。したがって、一
方のバンクのページへのアクセスが終了した際に、メモ
リコントローラは、すでにオープンしている他方のバン
クのページに直ちにアクセスすることが出来る。これに
よって再ページングを隠すことが出来るようになり、ペ
ージングオーバヘッドの低減が可能になる。

【０００４】

【発明が解決しようとする課題】このように上記従来例
では、フレームバッファメモリの現行の２バンクアーキ
テクチャに関連するオーバヘッドは、各バンクが他のバ
ンクのトランザクションが完了するまで新しいページの
オープンを待たなければならない場合に発生するオーバ
ヘッドよりも少ないが、ページング技術に伴う次のよう
な問題がある。第１に、現行のページング技術では、バ
ンク０要求とバンク１要求を別々にグループ化するため
に２つのＦＩＦＯを使用しなければならない。第２に、
バンク０要求とバンク１要求をソートするステップは、
ピクセルの処理順序を混乱させてしまう。

【０００５】この混乱は全ての場合に顕著ではないが、
メモリコントローラが要求するトランザクションが読取
トランザクションである場合に、一貫性と順序性に問題
が生ずる。この一貫性の問題は「フラッシング」を行う
ことによって対処できる。フラッシングは、読取トラン
ザクションが試みられる前に事前の書込トランザクショ
ンの発生を許容することによって行われ、フレームバッ
ファメモリの内容が古くならないように保証している。
順序性の問題は、読取要求トランザクションのためにデ
ータの順序を復元するハードウェアをグラフィックス記
憶システム内に実装することによって対処する。

【０００６】そこで、バンク０要求とバンク１要求を異
なるＦＩＦＯに別々にグループ化しなくてもページング
オーバヘッドを隠して低減できる２バンクアーキテクチ
ャを用いたグラフィックス記憶システムが必要である。

【０００７】本発明は、このような従来の技術における
課題を解決するものであり、フレームバッファメモリの
バンクに対する再ページングを隠してページングオーバ
ヘッド低減が可能になるグラフィックス記憶システム用
インテリジェンス内蔵ＦＩＦＯ記憶装置の提供を目的と
する。

【０００８】

【課題を解決するための手段】上記課題を達成するため
に、本発明は、第１記憶素子、第２記憶素子、書込みポ
インタデバイス、第１読取りポインタデバイス、および
第２読取りポインタデバイスを備えたページングオーバ
ヘッド低減のためのグラフィックス記憶システム用イン
テリジェンス内蔵ＦＩＦＯ記憶装置を提供する。

【０００９】第１記憶素子は、ＦＩＦＯ記憶装置の入力
ポートから１番目のエントリ集合を受け取って、各エン
トリを第１記憶素子内の記憶領域に格納する。第２記憶
素子は、ＦＩＦＯ記憶装置の入力ポートから２番目のエ
ントリ集合を受け取って、各エントリを第２記憶素子内
の記憶領域に格納する。エントリは、書込みポインタに
よってアドレス指定される第１記憶素子および第２記憶
素子の記憶領域に格納される。第１読取りポインタデバ
イスは、最終的にＦＩＦＯ記憶装置の第１出力ポートを
通じてＦＩＦＯから出力されるエントリを第１記憶素子
内の記憶領域から読み出すために、第１記憶素子内のア
ドレスを決定する。第２読取りポインタデバイスは、２
番目のエントリ集合内にタグ付きエントリがあるかを判
断する。第２読取りポインタデバイスは、これらのタグ
付きエントリに基づいて第２記憶素子内のアドレスを計
算し、このアドレスを第２記憶素子から読み出す。これ
らのエントリは、最終的にはＦＩＦＯ記憶装置の第２出
力ポートを通じてＦＩＦＯ記憶装置から出力される。

【００１０】第２記憶素子ではタグ付きエントリのみが
ＦＩＦＯ記憶装置から出力されるが、第１記憶素子に記
憶されているエントリは全てＦＩＦＯ記憶装置から出力
されるのが最適である。本発明の好ましい実施形態で
は、第２記憶素子内から選択されたタグ付きエントリが
オフセットを生成させる。オフセットの値は、その生成
に係わったタグ付きエントリの相対的位置によって決定
される。続いてオフセットの値は、第１読取りポインタ
アドレスと組み合わされ、第２読取りポインタアドレス
を生成する。第２読取りポインタアドレスは、オフセッ
トの生成に係わったタグ付きエントリと関連付けられる
第２記憶素子内の記憶領域に対応する。

【００１１】本発明の好ましい実施形態では、本発明の
ＦＩＦＯ記憶装置が、ページングオーバヘッド低減のた
めに、２バンクアーキテクチャを有するグラフィックス
記憶システムに実装される。第１記憶素子および第２記
憶素子は、それぞれ第１ラッチ配列と第２ラッチ配列で
あることが好ましい。本実施形態では、第２ラッチ配列
は、グラフィックス記憶システムのフレームバッファメ
モリのバンク０とバンク１のために行アドレスおよび他
の関連データを記憶する目的で用いられる。第１ラッチ
配列は、フレームバッファメモリのバンク０とバンク１
のために列アドレスおよび他の関連データを記憶する目
的で用いられる。行アドレスは、第２ラッチ配列にロー
ドされる際に、アクセスすべきバンクを示すバンクビッ
トでタグ付けされる。更に、バンク０またはバンク１の
再ページングを必要とする行アドレスは、ページングビ
ットでタグ付けされる。

【００１２】第２読取りポインタデバイスは、バンク０
とバンク１の再ページングの候補となる行アドレスを決
定するために、いずれの行アドレスがページングビット
でタグ付けされているか判断する。続いて、第２読取り
ポインタデバイスは、バンク０候補およびバンク１候補
の中からそれぞれダンプ候補を決定するために、バンク
０候補およびバンク１候補に優先順位を付与する。特定
のバンクのダンプ候補は、第２ラッチ配列内にあって同
一バンク用の第２ラッチ配列内に先行する他の行アドレ
スを持たない行アドレスに対応する。続いて、第２読取
りポインタデバイスは、２つのダンプ候補に優先順位を
付与し、最初にロードされた最初に必要とされるダンプ
候補を選択する。次に、この行アドレスは行ポート出力
レジスタに送出される。

【００１３】この行アドレスが行ポート出力レジスタか
らアンロードされると、次のダンプ候補に対応する行ア
ドレスを行ポート出力レジスタに送出することが出来
る。本発明の態様では、一方のバンクのトランザクショ
ンが処理されている間に他方のバンクの行アドレスを行
ポート出力レジスタにロードすることが出来る。したが
って、再ページングを隠すことが出来る。グラフィック
ス記憶システムのＲＡＭコントローラが、行ポート出力
レジスタにアンロード信号を送出することによって、行
ポート出力レジスタからの行アドレスのアンロードを制
御する。

【００１４】第１ラッチ配列に記憶されており、この再
ページングトランザクションに対応する列アドレスは、
ページング同調ビットによってもタグ付けが行われる。
第１ラッチ配列での各列アドレスは、先入れ先出し（Ｆ
ＩＦＯ）方式によって第１ラッチ配列の列ポート出力レ
ジスタに送出される。ＲＡＭコントローラは、列ポート
出力レジスタでの列アドレスをアンロードする前に、そ
の列アドレスがページング同調ビットを有しているかを
判断する。ここでページング同調ビットがある場合、Ｒ
ＡＭコントローラが、列アドレスを列ポート出力レジス
タからアンロードする前に、列アドレスによってアドレ
ス指定されるバンク用のメモリのページを確実に「オー
プン」する。このページが「オープン」されていない場
合に、ＲＡＭコントローラは、列ポート出力レジスタか
ら列アドレスをアンロードする前に、行ポート出力レジ
スタからの情報を用いてオープンする。

【００１５】第２読取りポインタデバイスは、ダンプ候
補を選択するごとに、ダンプ候補に関連付けられたペー
ジングビットが格納されているシフトレジスタ内の記憶
領域によって決定されるオフセットの値を計算する。こ
のオフセット値を第１読取りポインタアドレスに追加す
ることによって、第２読取りポインタアドレスが生成さ
れる。第２読取りポインタアドレスは、関連付けられた
行アドレスが記憶されている第２ラッチ配列内の記憶領
域に対応する。このアドレスを用いて、第２読取りポイ
ンタデバイスは、選択された行アドレスを行ポート出力
レジスタに送り出す。

【００１６】本発明の別の実施形態では、列アドレスと
行アドレスの複数のバッチを、それぞれ第１ラッチ配列
および第２ラッチ配列に記憶することが出来る。この実
施形態によると、前記したタグに加えて、第２ラッチ配
列の各エントリが、バッチデリミタとして動作するバッ
チインディケータによってタグ付けされる。第２読取り
ポインタデバイスは、現行バッチと関連付けられていな
い行アドレスが行ポート出力レジスタに送出されるのを
阻止するために、このバッチインディケータを使用す
る。

【００１７】このように本発明のページングオーバヘッ
ド低減のためのグラフィックス記憶システム用インテリ
ジェンス内蔵ＦＩＦＯ記憶装置は、フレームバッファメ
モリのバンクに対する再ページングを隠してページング
オーバヘッドを低減できるようになる。

【００１８】本発明のその他の特徴と利点は、以下の説
明、図面および特許請求の範囲から明確になるであろ
う。

【００１９】

【発明の実施の形態】次に、本発明のページングオーバ
ヘッド低減のためのグラフィックス記憶システム用イン
テリジェンス内蔵ＦＩＦＯ記憶装置の実施の形態を図面
を参照して詳細に説明する。図１は本発明のページング
オーバヘッド低減のためのグラフィックス記憶システム
用インテリジェンス内蔵ＦＩＦＯ記憶装置の実施形態に
おける構成を示すブロック図であり、コンピュータグラ
フィックスディスプレイシステム１０のブロック図を示
している。図１において、このコンピュータグラフィッ
クスディスプレイシステム１０は、グラフィックス記憶
システム２０から出力されるグラフィックス情報を表示
するために、ホストＣＰＵ１２、ホストメモリ１４、ロ
ーカルバス１８、入出力（Ｉ／Ｏ）インターフェイスコ
ントローラ２５、高度グラフィックスポート／周辺コン
ポーネント相互接続（ＡＧＰ／ＰＣＩ）インターフェイ
スバス１６、グラフィックス記憶システム２０、および
表示装置２１を備えている。

【００２０】ホストＣＰＵ１２は、コンピュータグラフ
ィックスディスプレイシステム１０のコンソール（図示
せず）から受け取った入力データを処理し、ローカルバ
ス１８を通じてＩ／Ｏインターフェイスコントローラ２
５にコマンドおよびデータを出力する。Ｉ／Ｏインター
フェイスコントローラ２５は、ＰＣＩ／ＡＧＰインター
フェイスバス１６におけるプロトコルによってコマンド
およびデータをフォーマットする。ＰＣＩ／ＡＧＰイン
ターフェイスバス１６を通して受け取られた情報は、グ
ラフィックス記憶システム（ＧＭＳ）２０に入力され
る。続いて、グラフィックス記憶システム２０は、この
情報を処理し、グラフィックスイメージを表示装置２１
に表示する。

【００２１】図２は、本発明の好ましい実施形態に基づ
くグラフィックス記憶システム２０のブロック図であ
る。グラフィックス記憶システム２０は、ホストインタ
ーフェイスユニット（ＨＩＵ）３２，２Ｄおよび３Ｄの
マクロ関数ユニット（ＭＦＵ）３４および３６、オブジ
ェクト関数ユニット（ＯＦＵ）３８、フレームバッファ
コントローラ（ＦＢＣ）４０、並びに、ディスプレイコ
ントローラ４３を備えるグラフィックスディスプレイシ
ステムの典型的な構成である。このグラフィックスディ
スプレイシステムは、当業者にとっては、その動作を容
易に理解できるものである。

【００２２】ホストインターフェイスユニット３２は、
ＰＣＩ／ＡＧＰバス１６を通じてホストメモリ１４から
コマンドデータパケットおよびテクスチャマップをフェ
ッチする。続いて、ホストインターフェイスユニット３
２は、２Ｄマクロ関数ユニット３４へグラフィックス２
Ｄ情報を送出し、また、３Ｄマクロ関数ユニット３６に
グラフィックス３Ｄ情報を送出する。２Ｄマクロ関数ユ
ニット３４は、２Ｄベクトル、テキスト、および矩形ス
パンを生成する。３Ｄマクロ関数ユニット３６は、三角
形のセットアップ、３Ｄラスタ化、およびテクスチャマ
ッピングを行う。

【００２３】２Ｄおよび３Ｄのマクロ関数ユニット３４
および３６からの出力は、オブジェクト関数ユニット３
８に入力される。オブジェクト関数ユニット３８は、三
角形クリッピング、パターニング、フレームバッファ間
ブロック転送および矩形スパンの塗りつぶしを行う。オ
ブジェクト関数ユニット３８の出力が、フレームバッフ
ァコントローラ（ＦＢＣ）４０に入力される。フレーム
バッファコントローラ４０は、メモリコントローラ（Ｍ
Ｃ０）４１およびメモリコントローラ（ＭＣ１）４２に
要求をディスパッチし、メモリコントローラ４１および
４２に対してＲＡＭ４５とＲＡＭ４６に／から、ピクセ
ルカラーおよびＺ座標の書き込みと読み取りを行う。

【００２４】また、フレームバッファコントローラ４０
は、ディスプレイ情報をフェッチし、ディスプレイコン
トローラ４３に送出する。ディスプレイコントローラ４
３は、ディスプレイ情報を受け取って、赤色、緑色、お
よび青色（ＲＧＢ）のアナログデータに変換して表示装
置２１に送出する。

【００２５】図３は、本発明の好ましい実施形態に基づ
くフレームバッファコントローラ４０の構成を示すブロ
ック図である。オブジェクトレシーバ５１およびオブジ
ェクトビルダ５５の両方は、オブジェクト関数ユニット
３８との通信を行う。オブジェクトビルダ５５は、メモ
リコントローラ４１および４２を通じて、それぞれＲＡ
Ｍ４５およびＲＡＭ４６から読み出されたピクセルデー
タを受け取り、読み取ったデータをオブジェクト関数ユ
ニット３８に送出する。オブジェクトビルダ５５は、メ
モリコントローラ４１および４２のそれぞれから３２ビ
ットデータを受け取って、必要ならデータを再フォーマ
ットし、オブジェクト関数ユニット３８の使用する６４
ビットオブジェクトを作成する。

【００２６】オブジェクトレシーバ５１は、オブジェク
ト関数ユニット３８からＸ，ＹおよびＺ画面座標ととも
に、ＹＵＶまたはＲＧＢカラーデータを受け取り、必要
に応じてカラーデータをＲＧＢフォーマットに変換し、
座標データおよびＲＧＢカラーデータをタイルビルダ５
６に送出する。タイルビルダ５６は、３２ビットによる
Ｚ座標データおよびカラーデータであるタイルを作成
し、ＲＡＭ４５およびＲＡＭ４６内の記憶領域に応じて
ＸおよびＹ画面座標をタイルの行アドレスおよび列アド
レスにマッピングする。

【００２７】タイルビルダ５６は、Ｚデータおよびカラ
ーデータのタイルを、対応する行アドレスおよび列アド
レスとともに、メモリコントローラ４１および４２に出
力する。また、タイルビルダ５６は、ピクセルのコヒー
レントなバッチ（すなわち、バッチ内に同一のＸ，Ｙア
ドレスを有する２つのピクセルが存在しない）の最後の
タイルの後にバッチデリミタを挿入する。本発明の好ま
しい実施形態では、グラフィックス記憶システム２０に
は、２つのメモリコントローラおよび２つのＲＡＭ記憶
装置が実装される。

【００２８】なお、当業者において、本発明ではグラフ
ィックス記憶システム２０に実装されるメモリコントロ
ーラの数に制限がないことを理解できるものである。当
業者で理解されるように、複数のメモリコントローラを
使用すれば、グラフィックス記憶システム２０の性能が
向上する。本発明のバッチングアーキテクチャおよび技
術は、単一のメモリコントローラおよび単一のフレーム
バッファ記憶素子と共に使用することが出来る。

【００２９】メモリコントローラ４１，４２それぞれ
は、Ｚの行アドレスと列アドレス、ピクセルの行アドレ
スと列アドレス、およびピクセルカラーデータを受け取
る。ＲＡＭ記憶素子４５と４６のそれぞれは、画像バッ
ファ記憶領域（図示せず）およびＺバッファ記憶領域
（図示せず）を有している。ピクセルカラーデータは画
像バッファ記憶領域に記憶され、Ｚ座標データはＺバッ
ファ記憶領域に記憶される。したがって、Ｚ座標が色値
とインタリーブされずにＲＡＭの別個の領域に記憶され
るという意味で、本発明は分離型Ｚバッファリングを利
用している。

【００３０】本発明の好ましい実施形態では、バスの送
受反転時間、すなわち、ＲＡＭバス６１または６２が読
取トランザクションと書込トランザクションを切り換え
るために必要となる状態数が複数のピクセルにわたって
平滑化されるように、Ｚ座標データがメモリコントロー
ラ４１，４２によって、ＲＡＭ４５およびＲＡＭ４６か
らバッチで読み出される。複数のピクセルにわたってバ
スの送受反転時間を平滑化することによって、分離型Ｚ
バッファリングに関連する処理待ち時間が極小化され
る。更に、再ページングも複数のピクセルにわたって平
滑化され、ページングオーバヘッドが低減される。

【００３１】メモリコントローラ４１，４２の動作は同
一であり、ここではメモリコントローラ４１とＲＡＭ記
憶素子４５に関してのみ、本発明の好ましい実施形態に
基づくバッチングアーキテクチャおよび技術について説
明する。メモリコントローラ４１，４２はデータのバッ
チを同時に処理できる。したがって、メモリコントロー
ラ４２とＲＡＭ４６の対は、以下に説明するメモリコン
トローラ４１とＲＡＭ４５の対と同一の動作を並行して
実行できる。

【００３２】メモリコントローラ４１は、タイルビルダ
５６から受け取った新しいＺ座標データを、ＲＡＭ４５
から読み出したバッチＺ座標データと比較する。各Ｚ座
標が比較されると、その結果がＺ比較結果ＦＩＦＯ５８
の待ち行列に挿入され、これは比較されたＺ座標に対応
する新しい色を各メモリコントローラのＲＡＭに書き込
まなければならないか、または、破棄できるかを判断す
る際に、メモリコントローラ４１，４２のいずれかによ
って使用される。Ｚ比較結果ＦＩＦＯ５８の目的につい
ては、この後に図４を参照して詳細に説明する。

【００３３】バッチ内で多数のピクセルが処理されるた
め、ほとんどの場合に再ページングオーバヘッドが低減
される。小さいバッチでは、ほとんどの再ページング
が、ピクセルカラーの書き込みからＺ座標データの読み
取りまたは、Ｚ座標データの書き込みからピクセルカラ
ーの書き込みにアクセスが切り換えられる場合にのみ行
われる。大きいバッチでは、Ｚの読み取りＺの書き込
み、色の読み取りまたは色の書き込みのバッチ内で再ペ
ージングが必要な場合、余分な再ページングを「隠す」
ことが出来る。したがって、オーバヘッドが、ほとんど
または全く生じないことになる。

【００３４】ここで、本発明の好ましい実施形態に基づ
くバッチング技術について図４を参照して説明する。図
４は図３に示したメモリコントローラ４１の詳細なブロ
ック図である。バッチングシーケンスは、タイルビルダ
５６によるメモリコントローラ４１へのピクセルカラー
および対応のＺ座標データの書き込みをもって開始す
る。Ｚ座標は新規ＺＦＩＦＯ７１に書き込まれ、対応す
るＺ座標の行／列アドレスはＺ読取ＦＩＦＯ８６に書き
込まれる。新しいピクセルカラーの行／列アドレスおよ
びカラーデータは、新規ピクセルＦＩＦＯ７５に書き込
まれる。これらの書き込みは、新規ＺＦＩＦＯ７１およ
び新規ピクセルＦＩＦＯ７５が満杯になるまで継続され
る。これによって、現行バッチの処理中に複数のバッチ
のデータを待ち行列に入れておくことが出来る。

【００３５】本発明の好ましい実施形態では、バッチは
書き込み要求のグループから構成され、このグループ
は、データの一貫性を保証し、メモリコントローラ４１
のＦＩＦＯでのオーバーフローを阻止するために、サイ
ズが制限されている。バッチの各要求は、ＲＡＭ４５内
の異なるアドレスに対応している。バッチの境界は、バ
ッチデリミタによって識別され、バッチデリミタはバッ
チの終了の発生をメモリコントローラ４１に通知する。

【００３６】バッチの境界は、予め定められた基準に従
ってコンピュータグラフィックスディスプレイシステム
１０で定義される。このような基準は、当業者によって
理解されるように、実際的な考慮に基づいてシステム設
計者によって選択される。バッチデリミタは、当該分野
において一般的に知られている。したがって、この実施
形態ではバッチデリミタの使用についての詳細な説明は
行わない。本発明がバッチの境界を識別するための特定
の技術に限定されないことは、当業者では理解できるも
のである。

【００３７】本発明の好ましい実施形態では、メモリコ
ントローラ４１はバッチデリミタをバッチ処理中の制御
のために使用している。バッチデリミタは、新規ピクセ
ルＦＩＦＯ７５、ピクセル読取ＦＩＦＯ８３、およびＺ
読取ＦＩＦＯ８６に書き込まれる。一度ＺアドレスがＺ
読取ＦＩＦＯ８６に書き込まれると、ＲＡＭコントロー
ラ９１がＺ読取ＦＩＦＯ８６の内容を読み取り、対応す
るＺ座標データをＲＡＭ４５からメモリバス６１に対し
て読み出しを行い、メモリバス６１からＺ試験コンポー
ネント（Ｚ ＴＥＳＴ）７３に書き込む。ＲＡＭ４５か
らＺ試験コンポーネント７３に転送される全てのＺ座標
データについて、対応する新しいＺ座標データが新規Ｚ
ＦＩＦＯ７１からＺ試験コンポーネント７３に転送され
る。Ｚ試験コンポーネント７３は、これらの値（Ｚ座標
データ）を比較し、比較が正常であれば、新しいＺ座標
データがＺ書込ＦＩＦＯ８４に書き込まれる。

【００３８】ＲＡＭコントローラ９１がＺ読取ＦＩＦＯ
８６内にバッチデリミタを検出すると、Ｚ書込ＦＩＦＯ
８４に切り換わり、Ｚ書込ＦＩＦＯ８４は、バッチのＺ
比較が、整合している新しいＺ座標データの際に、この
Ｚ座標データを格納する。次に、Ｚ書込ＦＩＦＯ８４内
に有効なデータがあれば、ＲＡＭコントローラ９１によ
ってＲＡＭ４５に書き込まれる。Ｚ比較の一部または全
部が不合格になる可能性もあるため、どの時点でＺ書込
データに対する探索を停止すべきかをＲＡＭコントロー
ラ９１に通知するための何らかの機構が必要である。新
しいＺ書込データに対する探索を停止すべき時期をＲＡ
Ｍコントローラ９１が判断する上では、「タイムアウ
ト」機構の使用が好ましい。

【００３９】Ｚ比較試験の結果も、Ｚ書込ＦＩＦＯ８４
への書き込みと同時に、Ｚ試験コンポーネント７３によ
って、Ｚ比較結果ＦＩＦＯ５８に書き込まれる。Ｚ比較
結果ＦＩＦＯ５８に記憶される結果は、メモリコントロ
ーラ４１，４２のピクセル修正子コンポーネント（ＰＩ
Ｘ ＭＯＤ）７７に送出される。ピクセル修正子コンポ
ーネント７７は、入力されたＺ比較結果を、新規ピクセ
ルＦＩＦＯ７５での、対応する新しいピクセルカラーを
ピクセル修正子コンポーネント７７のパイプに渡すべき
か、または、破棄すべきかを決定するために使用する。
ピクセル修正子コンポーネント７７を通過する全てのピ
クセルカラーおよび対応するアドレスは、最終的にピク
セル書込ＦＩＦＯ８１にロードされる。

【００４０】上記の「タイムアウト」の後にＺ書込ＦＩ
ＦＯ８４が空になると、ＲＡＭコントローラ９１が、Ｚ
書込ＦＩＦＯ８４からピクセル書込ＦＩＦＯ８１に切り
換わって、新しいピクセルカラーがＲＡＭコントローラ
９１によってＲＡＭ４５に書き込まれる。ＲＡＭコント
ローラ９１がピクセル書込ＦＩＦＯ８１に切り換わるま
での間は、ピクセルカラーの書き込み要求が待ち行列に
挿入され、ピクセル書込ＦＩＦＯ８１に記憶されている
ピクセルアドレスとピクセルカラーのバッチは、ＲＡＭ
４５に書き込める状態になっている。

【００４１】また、ピクセル修正子コンポーネント７７
は、新しいピクセルカラーに対して、混色のような読み
取り／修正／書き込み（ＲＭＷ）のそれぞれの操作を行
うことが出来る。ＲＭＷ操作は、新しいピクセルカラー
と同じ画面座標に対応する古いピクセルカラーの使用を
必要とする。これらのＲＭＷ機能を実現するために、タ
イルビルダ５６によって新規ピクセルＦＩＦＯ７５に書
き込まれたピクセルアドレスが、ピクセル読取ＦＩＦＯ
８３にも書き込まれる。これらの操作タイプの一つが実
行される際に、ピクセル書込ＦＩＦＯ８１へのあらゆる
切り換えに先立って、ＲＡＭコントローラ９１がピクセ
ル読取ＦＩＦＯ８３に切り換わる。

【００４２】ピクセル読取ＦＩＦＯ８３に記憶されてい
るアドレスに対応する古いピクセルカラーが、ピクセル
修正子コンポーネント７７のためにフェッチされる。続
いて、修正されたピクセルカラーがピクセル書込ＦＩＦ
Ｏ８１に書き込まれる。これらのフェッチは、修正され
たピクセルカラーがピクセル書込ＦＩＦＯ８１の待ち行
列に入っている間にバッチ全体にわたって続行する。Ｒ
ＡＭコントローラ９１がピクセル読取ＦＩＦＯ８３内に
おいてバッチデリミタを検出すると、ＲＡＭコントロー
ラ９１はフェッチを停止し、ピクセル書込ＦＩＦＯ８１
に切り換わる。そして、ピクセル書込ＦＩＦＯ８１に記
憶されている修正されたピクセルカラーはＲＡＭ４５に
格納される。

【００４３】ＲＡＭコントローラ９１は、「書き込みパ
イプ空き」インディケータ（図示せず）が現行バッチの
完了を示すまで、新規または修正ピクセルカラーの書き
込みを続行する。現行バッチが完了すると、ＲＡＭコン
トローラ９１は、次のバッチの処理を開始するために、
必要に応じて切り換わる。

【００４４】本発明の好ましい実施形態では、ピクセル
書込ＦＩＦＯ８１、ピクセル読取ＦＩＦＯ８３、Ｚ書込
ＦＩＦＯ８４およびＺ読取ＦＩＦＯ８６は、ページング
オーバヘッド低減用のインテリジェンスを内蔵した本発
明のＦＩＦＯアーキテクチャを実装することが好まし
い。

【００４５】図５は本発明におけるＦＩＦＯ１００のブ
ロック図であり、ＦＩＦＯ１００のポートおよびポート
に入出力される情報を例示している。このＦＩＦＯ１０
０は、一つの入力ポート１０１と２つの出力ポート（す
なわち、行出力ポート１０２と列出力ポート１０３）を
有することが好ましい。この後の図６〜図８に関連して
詳しく説明するように、出力ポート１０２および１０３
は互いに独立して動作する。

【００４６】ＦＩＦＯ１００の入力ポート１０１は、デ
バイスに接続されている。図４に示すように、様々なＦ
ＩＦＯ８１，８３，８４および８６が、それぞれピクセ
ル修正子コンポーネント７７、タイルビルダ５６，Ｚ試
験コンポーネント７３およびタイルビルダ５６による供
給を受ける。すなわち、入力ポート１０１は、バス１０
４を通じてページングビット（「Ｐビット」）、バンク
ビット（「バンク」）、行アドレス、および列アドレス
を受け取る。ＦＩＦＯ１００の動作に対応し、ある状況
においては、ＦＩＦＯ１００の入力ポート１０１でバス
１０５を通じてコマンドとデータを受け取ることもあ
る。

【００４７】ＦＩＦＯ１００の入力ポート１０１および
ＦＩＦＯ１００に供給を行うデバイスには、制御線１０
７および１０８が接続されている。制御線１０７は、Ｆ
ＩＦＯ１００内に、より多量の情報を保持に利用できる
領域を有していることを示すために、ＦＩＦＯ１００に
供給を行うデバイスに対して「スペース／ＳＰＡＣＥ」
の表示を出力する。ＦＩＦＯ１００から「スペース」の
表示を受け取ると、ＦＩＦＯ１００に供給を行うデバイ
スは制御線１０８を通じてＦＩＦＯ１００にロード信号
「ＬＤ」を送出し、これによってＦＩＦＯ１００は入力
ポート１０１から情報をロードする。

【００４８】ＦＩＦＯ１００の出力ポート１０２は、行
アドレス「ＲＯＷ」および対応する行（ｂ）のバンク
「ＲＯＷ ＢＡＮＫ」をバス１１２上に適宜アンロード
する。これについては、この後の図６、図７、図８を参
照して詳細に説明する。ＦＩＦＯ１００が、ＦＩＦＯ１
００を利用しているメモリコントローラのＲＡＭコント
ローラからライン１１６を通じてアンロード信号「ＵＮ
ＬＤ」を受信すると、行アドレスおよび行バンクがアン
ロードされる。ＦＩＦＯ１００がライン１２１を通じて
アンロード信号「ＵＮＬＤ」を受信すると、ページング
同調ビット「ＰＳ」、列アドレス「ＣＯＬ」、任意のコ
マンド「ＣＭＤ」およびデータ「ＤＡＴＡ」並びに対応
する列のバンク「ＣＯＬ ＢＡＮＫ」が、ＦＩＦＯ１０
０からバス１１８上にアンロードされる。

【００４９】前記したように、本発明の好ましい実施形
態では、ＦＩＦＯ１００は図３に示すメモリコントロー
ラ４１および４２内に実装される。したがって、好まし
い実施形態によれば、ＦＩＦＯ１００の出力ポート１０
１および１０３は、ＦＩＦＯ１００の実装されているメ
モリコントローラ内のＲＡＭコントローラに接続され
る。メモリコントローラ相互および対応するＲＡＭコン
トローラ相互は同一であることが好ましい。したがっ
て、図３および図４に示すように、本明細書では一つの
ＲＡＭコントローラおよび一つのＲＡＭデバイス、具体
的には、ＲＡＭコントローラ９１およびＲＡＭ４５との
関連のみでＦＩＦＯ１００の説明を行う。

【００５０】ＲＡＭコントローラ９１は、ＦＩＦＯ１０
０の出力ポート１０２の情報をバス１１２にアンロード
すべき時期および出力ポート１０３の情報をバス１１８
にアンロードする時期をそれぞれ決定するロジックを有
している。バス１１２への情報のアンロードはバス１１
８への情報のアンロードと独立している。ＲＡＭコント
ローラ９１はライン１１６および１２１上のアンロード
信号をＦＩＦＯ１００の出力ポート１０２および１０３
に出力し、情報をＦＩＦＯ１００からバス１１２および
１１８にアンロードさせる。列アドレスおよび行アドレ
スをＦＩＦＯ１００からアンロードする時期をそれぞれ
決定するために、ＲＡＭコントローラ９１に状態機械を
実装するのが好ましい。

【００５１】このタスクを実行するためのに、ＲＡＭ４
５のバンク０向けトランザクション用として第１状態装
置をＲＡＭコントローラ９１に実装し、第１状態装置と
同一の第２状態装置をＲＡＭ４５のバンク１向けトラン
ザクション用に実装するのが好ましい。状態装置の機能
については、この後の図８を参照して詳細に説明する。
ページ同調ビット（ＰＳ）、ＲＯＷ ＢＡＮＫ、および
ＣＯＬ ＢＡＮＫの目的については、以下の図６、図
７、図８、図９、図１０、図１１を参照して詳細に説明
する。

【００５２】図６はＦＩＦＯ１００の内部機能コンポー
ネントのブロック図であり、ページングオーバヘッド低
減のためにＦＩＦＯ１００に内蔵されているインテリジ
ェンスを例示している。図５に示すバスは、ＦＩＦＯ１
００で受け取った情報がＦＩＦＯ１００の様々なコンポ
ーネントによってどのように利用されるかを図示するた
めに、場合によっては個々のラインによって置き換えて
ある。ＦＩＦＯ１００は、行アドレスを記憶するための
行ラッチ配列１３１およびＰビットと列アドレス並びに
コマンドとデータを記憶するための主ラッチ配列１４６
を有している。

【００５３】また、ＦＩＦＯ１００は、書込みポインタ
コンポーネント（ＷＲＴ ＰＴＲ）１３５、行読取りポ
インタコンポーネント（ＲＯＷ ＲＤ ＰＴＲ）１３４
および主読取りポインタコンポーネント（ＭＡＩＮ Ｒ
Ｄ ＰＴＲ）１５３を有している。書込みポインタコン
ポーネント１３５は、ラッチ配列１３１と主ラッチ配列
１４６の両方によって利用される。書込みポインタコン
ポーネント１３５は、ラッチ配列１３１および１４６内
で情報を記憶すべき場所を指し示している。主読取りポ
インタコンポーネント１５３は、主ラッチ配列１４６か
ら読み出すべき情報が記憶されている主ラッチ配列内の
場所を指し示している。行読取りポインタコンポーネン
ト１３４は、行ラッチ配列１３１から読み出すべき情報
が記憶されている行ラッチ配列１３１内の場所を示して
いる。

【００５４】行読取りポインタコンポーネント１３４
は、行ラッチ配列１３１内の記憶領域から行ポート出力
レジスタ１３６へ転送すべき行アドレスおよび行アドレ
スの転送時期を決定するために、三つの別々のシフトレ
ジスタからの情報を利用する。図７（ａ）、図７（ｂ）
および図７（ｃ）は、これらのシフトレジスタを示すブ
ロック図である。図７（ａ）に示すＰシフトレジスタ１
８０は、関連付けられている各行と列のエントリについ
てのページングビット「Ｐ」を含んでいる。Ｐシフトレ
ジスタ１８０に含まれる各ページングビットは、関連付
けられているアドレスにとって、ＲＡＭ４５内の指定の
バンクを再ページングすることが必要かどうかを指示す
る。

【００５５】Ｐシフトレジスタ１８０が下方から上方に
ロードされる場合、入力ポート１０１からのページング
ビットは、レジスタ１８０内にあって入力がＦＩＦＯ１
００にロードされる際に有効なエントリ（下記）を含む
記憶領域のすぐ上にある記憶領域にライン１８３を通じ
て格納される。これらのエントリの位置は、列アドレス
が列ポート出力レジスタ１３８からアンロードされるご
とに一つずつ下方に移動する。好ましい実施形態では、
値１を有するページングビットは、トランザクションに
とって再ページングが必要なことを示し、値０はトラン
ザクションにとって再ページングが必要ないことを示し
ている。

【００５６】好ましい実施形態では、ＦＩＦＯ１００は
１６または３２記憶領域に相当する深度を有し、このた
めにシフトレジスタがそれぞれ１６または３２記憶領域
の深度を持たなければならない。しかし、本発明のＦＩ
ＦＯ１００やシフトレジスタが特定のサイズに限定され
ないことは、当業者では理解できるものである。説明を
簡単にするために、図７（ａ）から図７（ｃ）の各レジ
スタには８記憶領域の深度を持たせてある。したがっ
て、この例においてはＦＩＦＯ１００も８記憶領域の深
度を有することになる。

【００５７】図７（ｂ）に示すｂシフトレジスタ２０３
は、関連付けられている各行と列のエントリについての
バンクビットｂを有している。各バンクビットは、アド
レスがＲＡＭ４５内のバンク０用かバンク１用かを示し
ている。好ましい実施形態では、０の値を有するバンク
ビットは、関連付けられているアドレスに係わるトラン
ザクションがバンク０向けであることを示し、１の値を
有するバンクビットは、関連付けられているアドレスに
係わるトランザクションがバンク１向けであることを示
している。ｂシフトレジスタ２０３が下方から上方にロ
ードされる場合、入力ポートからのバンクビットは、レ
ジスタ２０３内にあって入力がＦＩＦＯ１００にロード
される際に有効なエントリ（下記）を含む記憶領域のす
ぐ上にある記憶領域にライン２０４を通じて格納され
る。これらの有効なエントリの位置は、列アドレスが列
ポート出力レジスタ１３８からアンロードされるたび
に、一つずつ下方に移動する。

【００５８】図７（ｃ）に示すＶシフトレジスタ２３０
は有効性ビット「Ｖ」を有している。各有効性ビット
は、Ｐシフトレジスタ１８０の一つのエントリおよびｂ
シフトレジスタ２０３の一つのエントリと関連付けられ
ており、Ｐシフトレジスタ１８０およびｂシフトレジス
タ２０３の関連付けられたエントリが有効かどうかを示
している。

【００５９】好ましい実施形態においては、Ｖシフトレ
ジスタ２３０の記憶領域でのＶビットの値が０であれ
ば、他のシフトレジスタ１８０および２０３の対応する
エントリは有効でなく、Ｖシフトレジスタ２３０の記憶
領域でのＶビットの値が１であれば、他のシフトレジス
タ１８０および２０３の対応するエントリは有効であ
る。入力ポート１０１がロードされると、シフトレジス
タ２３０内にあって１の値を有する他のＶビットの記憶
領域のすぐ上にある記憶領域にライン２３２を通じて１
の値が格納される。これらの有効なエントリの位置は、
列アドレスが列ポート出力レジスタ１３８からアンロー
ドされるたびに、一つずつ下方に移動する。

【００６０】Ｐシフトレジスタ１８０にロードされるＰ
ビットも列アドレスとともに主ラッチ配列１４６に格納
される。主ラッチ配列１４６に格納される各列アドレス
は、Ｐシフトレジスタ１８０内の一つのエントリと関連
付けられる。列アドレスが列ポート出力レジスタ１３８
からアンロードされると、対応するＰビット（ＰＳ）も
主ラッチ配列１４６からアンロードされ、ページング同
調に使用される。ここで、ＦＩＦＯ１００によるＰビッ
ト、ｂビットおよびＶビットの利用についての用法につ
いて、図６から図８を参照して説明する。

【００６１】図８はインテリジェントなＦＩＦＯ１００
におけるページングオーバヘッド低減用ロジックを例示
するエントリを収容した図（表）である。表の列２６２
は八つの有効なページングビット（Ｐ）エントリを有し
ている。これらのエントリの妥当性を検査するＶビット
は、図を簡略化するために、その図示を省略した。表の
列２６２の各エントリは、シフトレジスタ１８０の記憶
領域に対応する。

【００６２】例えば、表の列２６２、行２７１に格納さ
れているＰビットエントリは、Ｐシフトレジスタ１８０
の記憶領域１８５に格納されているＰビットに対応す
る。同様に、表の列２６２、行２８２に格納されている
Ｐビットエントリは、Ｐシフトレジスタ１８０の記憶領
域１９６に格納されているＰビットに対応する。したが
って、表の底部近くのエントリは、表内の上に示される
エントリよりも時間的に早くロードされたことになる。

【００６３】表内のバンク（ｂ）ビットエントリも、ｂ
ビットシフトレジスタ２０３内の記憶領域に対応する。
表の列２６３において、表の底部の４行に示す０の値を
有するｂビットエントリは、バンク０向けのトランザク
ションに対応する。表内の行２７４と２７６に示される
１の値を有する次の２つのエントリは、バンク１向けの
トランザクションに対応する。表内の行２７１と２７２
に置かれていて０の値を有する上部２つのエントリは、
バンク０向けのトランザクションに対応する。表の列２
６２において、行２８２，２７６および２７２に示され
る１の値を有するＰビットエントリは、行ラッチ配列１
３１に含まれる関連付けられた行アドレスに対応するト
ランザクションを実行するために、ＲＡＭ４５を再ペー
ジングしなければならないことを示している。

【００６４】表のＣＡＮＤ０列、すなわち列２６５は、
バンク０の再ページング候補であるトランザクションに
対応する。好ましい実施形態では、この列の値が０であ
る場合に、対応する行アドレスはバンク０トランザクシ
ョンの再ページング候補ではなく、この列の値が１であ
る場合には、対応する行アドレスはバンク０トランザク
ションの再ページング候補であることを示している。

【００６５】表のＣＡＮＤ１列、すなわち列２６６は、
バンク１の再ページング候補であるトランザクションに
対応する。好ましい実施形態では、この列の値が０であ
る場合に、対応する行アドレスはバンク１トランザクシ
ョンの再ページング候補ではなく、この列の値が１であ
る場合に、対応する行アドレスはバンク１トランザクシ
ョンの再ページング候補であることを示している。ま
た、対応する行アドレスがバンク１トランザクションの
再ページング候補ではないことを示すために、この列に
０を入力し、対応する行アドレスがバンク１トランザク
ションの再ページング候補であることを示すためにこの
列に１を入力することも可能である。

【００６６】図７（ｃ）に示す有効性シフトレジスタ２
３０の全エントリが１に設定されている、すなわち、Ｐ
列２６２およびｂ列２６３の全エントリがそれぞれ有効
なトランザクションに対応すると想定して、表内の候補
エントリは、表の列２６２の行２８２，２７６および２
７２に値１を有するＰビットに関連付けられている。し
たがって、候補トランザクションは、対応するページン
グビットおよび有効性ビットが１に設定されているトラ
ンザクションである。再ページング候補は優先順位を付
けられ、表内で自己から下にバンク０向けの他のトラン
ザクションを持たないバンク０の再ページング候補のみ
が行選択プロセスにおいて引き続き考慮されるようにな
っている。同様に、表内で自己から下にバンク１向けの
他のトランザクションを持たないバンク１の再ページン
グ候補のみが行選択プロセスにおいて引き続き考慮され
る。

【００６７】列２６２、行２８２のＰビット値が１であ
れば、そのエントリと関連付けられているトランザクシ
ョンが再ページングを必要とすることを示し、列２６
３、行２８２のｂビット値が０であれば、トランザクシ
ョンを実行するためにはバンク０の再ページングが必要
なことを示す。Ｐビットとバンクビットがこれらの値を
取ると、表の列２６５、行２８２のＣＡＮＤ０の値は１
となり、対応するトランザクションがバンク０の再ペー
ジング候補であることを示す。

【００６８】列２６３、行２７６のｂビット値が１であ
れば、対応するトランザクションがバンク１向けである
ことを示す。列２６２、行２７６のＰビット値が１であ
れば、対応するトランザクションがバンク１の再ページ
ングを必要とすることを示す。Ｐビットとｂビットがこ
れらの値を取ると、表の列２６６、行２７６のＣＡＮＤ
１の値は１となり、対応するトランザクションがバンク
１の再ページング候補トランザクションであることを示
す。

【００６９】列２６３、行２７２のバンクビット値が０
であれば、対応するトランザクションがバンク０向けで
あることを示す。それに関連付けられた列２６２、行２
７２のＰビット値は１に設定されており、対応するトラ
ンザクションがバンク０の再ページングを必要とするこ
とを示す。列２６５、行２７２のＣＡＮＤ０の値は１と
なり、対応するトランザクションがバンク０の再ページ
ング候補であることを示す。

【００７０】前記したように、一度バンク０とバンク１
の候補が決定されると、表内で自己から下に当該バンク
向けの他のトランザクションを持たない特定のバンクの
候補のみが当該バンクの「ダンプ」候補になるように、
優先順位が付けられる。図８に示すように、列２６６、
行２７６のＣＡＮＤ１エントリの値は１であり、これよ
り下の表内にはバンク１向けの他のトランザクションは
ない。

【００７１】したがって、このエントリがバンク１のダ
ンプ候補である。しかし、行２７２のＣＡＮＤ０エント
リより下にバンク０トランザクションを有しているた
め、表内の行２７２より下にあるバンク０トランザクシ
ョン（すなわち、表の行２８２、２８１、２７９および
２７８のエントリに対応するトランザクション）の処理
が全て完了するまで、このダンプ候補は行選択プロセス
に参加できない。表の行２８２のエントリに関連付けら
れているトランザクションは、バンク０のダンプ候補で
あり、表内の行２８２より下にバンク０トランザクショ
ンがないので、引き続き行選択プロセスに参加する。

【００７２】この例のこの時点で、行選択プロセスに参
加できるダンプ候補は２つのみが残っている。一つはバ
ンク０用、すなわち行２８２であり、他の一つはバンク
１用、すなわち行２７６である。これらのダンプ候補
は、表の一方に対して下部の候補が最後に選択されるよ
うに優先順位が付けられる。本発明の好ましい実施形態
では、選択されたダンプ候補（この例では行２８２のＣ
ＡＮＤ０エントリ）は、オフセットを生成させる。オフ
セットの大きさは、シフトレジスタ１８０、２０３およ
び２３０内における選択された候補の位置によって決定
される。

【００７３】選択された候補の考えられる各位置に対応
して特定のオフセット値が付される。例えば、行２７６
は位置４にあるため、オフセット４が符号化される。オ
フセットは、ライン１５５を通じて行読取りポインタコ
ンポーネント１３４に送出される主読取りポインタの値
に追加され、これによって、対応のダンプ候補が選択さ
れる際に行読取りポインタが生成される。行読取りポイ
ンタコンポーネント１３４は、選択された行アドレスを
ダンプさせ、行ポート出力レジスタ１３６に転送させる
ために、この行読取りポインタを用いて行ラッチ配列１
３１をアドレス指定する。この行読取りポインタが様々
な方法で作成できる。すなわち、本発明が行読取りポイ
ンタの特定の生成方法に限定されないことは、当業者で
は容易に理解できるものである。

【００７４】最後の候補が選択され、行アドレスがダン
プされると、再び行選択プロセスに参加しないように、
Ｐシフトレジスタ１８０内の該当するＰビットがクリア
される。行２８２内のトランザクションのためにバンク
０が再ページングされ、行２８２のエントリと関連付け
られる行アドレスが行ポート出力レジスタ１３６からア
ンロードされると、表の行２７６と関連付けられている
行アドレス（バンク１用）を選択して行ポート出力レジ
スタ１３６に挿入できる。これによって、行２８１，２
７９および２７８のエントリに対応するバンク０トラン
ザクションが処理されている間にバンク１を再ページン
グすることが出来る。したがって、バンク１の再ページ
ングを「見えなくする／隠す」ことが出来るようにな
る。

【００７５】ＣＡＮＤ０列において、行２７２より下の
行に対応するバンク０トランザクションが全てアンロー
ドされると、ＣＡＮＤ０行２７２に対応するトランザク
ションが最後の行選択プロセスに参加できる。行２７６
のＣＡＮＤ１エントリに対応するＰビットがクリアされ
ると、これによって行２７２のＣＡＮＤ０エントリが選
択可能になる。この結果、表の行２７６および２７４に
対応するバンク１トランザクションが処理されている間
にバンク０を再ページングすることが出来るようにな
る。したがって、バンク０の再ページングを「見えなく
する」ことが出来る。

【００７６】本発明の好ましい実施形態では、ＦＩＦＯ
１００のインテリジェンスは、ＲＡＭ４５のバンクの再
ページングを見えなくするために、ＲＡＭコントローラ
９１でのロジックと連動する。この目的でＲＡＭコント
ローラ９１でのロジックは、バンク０トランザクション
用とバンク１トランザクション用に一つずつ、合計２つ
の状態装置（図示せず）の形で実施されることが好まし
い。これらの２つの状態装置は同一の機能を有している
ため、一方の状態装置の動作についてのみ詳細に説明す
る。また、状態装置のバンク０とバンク１に対する動作
は同一であるためバンク０トランザクションのみの状態
装置の動作について説明する。

【００７７】状態装置は三つの状態、すなわち状態０、
状態１および状態２を有している。状態０は、バンクの
ためにページがオープンされていない状態に対応する。
この状態は普通、起動時に発生する。一度ページがオー
プンされると、状態装置は状態１になる。状態１では、
ページはオープンされているが、そのページに対応する
列アドレスは、まだ列ポート出力レジスタ１３８からア
ンロードされていない。対応する列アドレスが列ポート
出力レジスタ１３８からバス１５８上に出力されると、
ＲＡＭコントローラ９１が列アドレスを処理し、状態装
置は状態２に入る。

【００７８】状態２においては、ページング同調ビット
（ＰＳ）に関連付けられているバンク０の列アドレスを
列ポート出力レジスタからアンロードすることは出来な
い。しかし、ＲＡＭコントローラ９１は、ページング同
調ビット（ＰＳ）に関連付けられていない列アドレス
を、列ポート出力レジスタ１３８からアンロードさせ
る。続いて、これらの列アドレスはＲＡＭコントローラ
９１によって処理される。当該バンク用の新しい行アド
レスが、行ポート出力レジスタ１３６からバス１５７上
にアンロードされると、状態装置は再び状態１になって
対応する列アドレスが列ポート出力レジスタ１３８から
アンロードされるのを待つ。

【００７９】ＲＡＭコントローラ９１でのコマンドディ
スパッチャ（図示せず）が、ライン１１４と１１９上の
行／列有効性インディケータ（ＶＡＬ）、ＲＯＷ ＢＡ
ＮＫ、ＣＯＬ ＢＡＮＫ、およびページング同調ビット
（ＰＳ）をモニタし、行ポート出力レジスタまたは列ポ
ート出力レジスタの情報をアンロードする時期を決定す
るために各バンクの状態装置をモニタすることによっ
て、行ポート出力レジスタ１３６および列ポート出力レ
ジスタ１３８のアンロードを管理する。一度ページがオ
ープンされると、すなわち、行アドレスが行ポート出力
レジスタ１３６からバス１５７上に出力されると、状態
装置は状態１になる。

【００８０】列ポート出力レジスタが、ページング同調
ビット（ＰＳ）に関連付けられた有効な列アドレスを有
し、かつ、状態装置が状態１にある場合、コマンドディ
スパッチャは列ポート出力レジスタ１３８のみをバス１
５８上にアンロードする。当該バンクの状態装置が状態
２にある場合には、コマンドディスパッチャは、ページ
ング同調ビット（ＰＳ）に関連付けられていない列アド
レスのみをアンロードする。

【００８１】行２８２にある最初のダンプ候補に関連付
けられているトランザクションのためにバンク０がオー
プンされると、行２７６にある２番目のダンプ候補が行
ポート出力レジスタ１３６に送出される。２番目のダン
プ候補に関連付けられているトランザクションのために
バンク１がオープンされ、３番目のダンプ候補より下に
ある全てのバンク０トランザクションがアンロードされ
ると、行２７２にある３番目のダンプ候補が行ポート出
力レジスタ１３６に送出される。したがって、図８に示
す例では、三つの行アドレス、すなわち、各再ページン
グ要求ごとに一つのアドレスのみが行ポートからアンロ
ードされる一方で各トランザクションに対応して一つず
つ合計八つの列アドレスがアンロードされる。

【００８２】本発明の代替実施形態では、本発明のイン
テリジェントなＦＩＦＯ１００が複数のバッチを自己の
待ち行列に入れておけるため、最初のバッチの処理が完
了すると、２番目のバッチの処理を開始できる。複数の
バッチを扱うために、Ｚ読取ＦＩＦＯ８６と新規Ｚ Ｆ
ＩＦＯ７１をこの実施形態に従ってインテリジェントな
ＦＩＦＯ１００として設計するのが好ましい。好ましい
実施形態でのＦＩＦＯ１００は、現在のバッチと次に処
理するバッチを区別できるように、図９に示すＢＡＴＣ
Ｈ（Ｂ）シフトレジスタ３００を利用する。

【００８３】説明上、シフトレジスタ３００は、深度８
語のＦＩＦＯのために八つの記憶領域を有するように示
してある。しかし、ＦＩＦＯ１００は１６語または３２
語の深度を有することが好ましく、Ｂシフトレジスタ３
００には１６ビットまたは３２ビットの記憶領域が必要
になる。ただし、当業者であれば、本発明が特定の深度
に限定されないことを理解できるものである。

【００８４】シフトレジスタ３００内の各記憶領域は、
特定のエントリが特定のバッチと関連付けられているか
を示すバッチ識別符号（ＩＤ）として機能する。バッチ
ＩＤは、各新規バッチごとに逆転する。例えば、現行バ
ッチのバッチＩＤが０である場合に、次に処理するバッ
チのバッチＩＤは１になる。現行バッチの処理が終了す
ると、次のバッチが現行バッチとなり、その現行バッチ
はバッチＩＤとして１を有する。したがって、バッチＩ
Ｄは新しいバッチごとに０と１の間で切り換わり、選択
プロセスのためにバッチ間のデリミタとして動作する。

【００８５】図１０に示すように、本実施形態による行
読取りポインタ３２１は、図６の行読取りポインタ１３
４に極めて類似している。行読取りポインタ３２１は、
行ラッチ配列１３１内の記憶領域から行ポート出力レジ
スタ１３６に転送すべき行アドレスおよびその転送時期
を決定するために、シフトレジスタ１８０，２０３およ
び２３０からの情報も利用する。行読取りポインタ３２
１の出力を行読取りポインタ１３４の出力と同一であ
る。

【００８６】行読取りポインタ１３４の場合と同様に、
行読取りポインタ３２１も主読取りポインタ１５８に追
加されるオフセットを計算する。このタスクを実行する
方法は、行読取りポインタ１３４による方法と実質的に
同一である。しかし、行読取りポインタ３２１は、現行
バッチに関連付けられているエントリのみが選択プロセ
スに対する処理を行うようにダンプ候補を選択する。

【００８７】自己が受け取る前記した他の情報に加え
て、行読取りポインタ３２１は、図９のＢシフトレジス
タ３００からの情報も利用する。この情報の流れを、図
１０ではライン３２０と大文字の「Ｂ」で示してある。
更に、行読取りポインタ３２１は、ＲＡＭコントローラ
９１から「現行バッチ」インディケータ３２２も受け取
る。行読取りポインタ３２１による「現行バッチ」イン
ディケータの利用方法は、以下で図１１の表に関連して
説明する。

【００８８】列が追加されていることおよび表のエント
リが異なることを除けば、図１１の表は図８の表と類似
している。列３３２，３３３，３３５および３３６の利
用方法は、図８を参照した説明と同一である。図１１の
列３３１は「バッチ」列であり、バッチシフトレジスタ
３００のエントリに対応する。この例では、バッチ列３
３１のエントリは、値１のエントリの一つを除き全て０
である。この例では、現行バッチＩＤは０である。

【００８９】したがって、列３３１、行３４６のエント
リの値１は、対応するトランザクションが異なるバッチ
のメンバであり、行３４６より下のエントリが現行バッ
チの最後のエントリであることを示す。「ＭＥＭ」列３
３４は、ＲＡＭコントローラ９１からライン３２２を通
じて行読取りポインタ３２１に入力される現行バッチＩ
Ｄ（この例では０）およびライン３２０を通じて行読取
りポインタ３２１に入力されるトランザクションバッチ
ＩＤ（Ｂ）に対して実行される論理演算に対応するエン
トリを有している。各トランザクションのＭＥＭエント
リを生成するために、そのトランザクションのバッチＩ
Ｄ（Ｂ）を現行バッチＩＤと比較する場合は、排他的否
定論理和（ＸＮＯＲ）演算を用いる。

【００９０】したがって、列３３１の行３５２，３５
１，３４９および３４８のエントリによって示されるよ
うに、ＲＡＭコントローラ９１から提供される現行バッ
チＩＤが０であり、Ｂシフトレジスタ３００から提供さ
れるバッチＩＤが０であるため、列３３４の行３５２，
３５１，３４９および３４８のエントリが全て１とな
る。

【００９１】列３３１、行３４６のエントリは１である
が、ＲＡＭコントローラ９１から提供される現行バッチ
ＩＤは引き続き０である。したがって、ＭＥＭ列３３４
の行３４６に示されるように、ＸＮＯＲ演算の結果は０
である。この０というエントリは、列３３１，行３４６
のエントリに対応するトランザクションが現行バッチの
一部でないことを示している。このＭＥＭ列３３４のエ
ントリ０は、列３３８および３３９においてＩＮＨ０お
よびＩＮＨ１によって表される抑止信号を生成させる。

【００９２】これらの抑止信号は、表内で当該エントリ
より上の行にあるエントリが実際に現行バッチのメンバ
になるまで、当該エントリより上の行にある候補に対応
する行アドレスが行ポート出力レジスタ１３６に送られ
るのを防止する。下部にある四つのページング候補（こ
の例では行３５２にある候補）のみが行ポートに送出さ
れる。列３３６の行３４４にあって値１を有するＣＡＮ
Ｄ１エントリは、表の下部５つのエントリに対応するト
ランザクションの処理が完了するまで行ポート出力レジ
スタ１３６に送出されない。

【００９３】現行バッチに対応する下部の四つのトラン
ザクションがアンロードされると、ＲＡＭコントローラ
９１が現行バッチＩＤを１に切り換えて、行３４６にあ
ってバッチＩＤとして１を有する５番目のトランザクシ
ョンが現行バッチのメンバとなる。このトランザクショ
ンがアンロードされると、ＲＡＭコントローラ９１は現
行バッチＩＤを再び０に切り換え、この切り換えによっ
て上部の四つのエントリが現行バッチのメンバとなる。

【００９４】列３３３のエントリも抑止信号を生成させ
る。列３３８の行３５２，３５１，３４９および３４８
に示すように、バンク０のための有効なエントリは抑止
０（ＩＮＨ０）信号を生成させ、抑止信号が、これらの
エントリより上の行にあるエントリに対応するバンク０
の行アドレスが行ポート出力レジスタ１３６に送出され
るのを阻止する。しかし、これらのエントリはバンク１
には係わらないため、列３３９の行３５２，３５１，３
４９および３４８のエントリが０であることから、バン
ク１は抑止されない。

【００９５】同様に、列３３９の行３４４，３４２およ
び３４１に示すように、バンク１のための有効なエント
リは抑止１（ＩＮＨ１）信号を生成させる。抑止信号
は、これらのエントリより上の行にあるエントリに対応
するバンク１の行アドレスが行ポート出力レジスタ１３
６に送出されるのを阻止する。しかし、これらのエント
リはバンク０には係わらないため、列３３８の行３４
４，３４２および３４１のエントリが０であることか
ら、バンク０は抑止されない。

【００９６】以上、好ましい実施形態について本発明に
ついて説明したが、本発明はこれらの実施形態に限定さ
れない。この好ましい実施形態は、本発明を例示する目
的であるが、当業者なら、本発明を様々な形で実施し
て、好ましい実施形態と同様の結果が得られることを理
解できるものである。また、本発明のインテリジェント
なＦＩＦＯ１００はグラフィックス記憶システムでの使
用に限定されない。このような文脈で説明したのは、単
にインテリジェントなＦＩＦＯ１００の利点と好ましい
用法を例示するのが目的であることも当業者には容易に
理解できるものである。

【００９７】以下に本発明の実施の形態を要約する。 １． ＦＩＦＯ（先入れ先出し）記憶装置（１００）に
おいて、当該ＦＩＦＯ記憶装置（１００）の入力ポート
から第１のエントリ集合を受け取り、書込みポインタデ
バイスによってアドレス指定される記憶領域に前記第１
のエントリ集合の各エントリを格納する第１記憶素子
（１４６）と、前記入力ポートから第２のエントリ集合
を受け取り、前記書込みポインタデバイスによってアド
レス指定される記憶領域に前記第２のエントリ集合の各
エントリを格納する第２記憶素子（１３１）と、前記第
１記憶素子（１４６）内の第１読取りポインタアドレス
を決定する手段であって、前記第１記憶素子（１４６）
内の記憶領域から前記第１のエントリ集合を読み出す際
に、前記第１読取りポインタアドレスが前記第１記憶素
子（１４６）内の記憶領域のアドレス指定に使用され、
前記第１記憶素子（１４６）から読み出されたエントリ
が当該ＦＩＦＯ記憶装置（１００）の第１出力ポート
（１０１）を介して当該ＦＩＦＯ記憶装置（１００）か
ら出力する第１読取りポインタデバイス（１５３）と、
前記第２のエントリ集合内にタグ付きエントリがあるか
を判断し、前記第２のエントリ集合内のタグ付きエント
リに基づいて第２読取りポインタアドレスを計算し、前
記第２読取りポインタアドレスを用いて前記第２のエン
トリ集合内の前記タグ付きエントリを前記第２記憶素子
（１３１）内の各記憶領域から読み出す手段であって、
前記第２記憶素子（１３１）から読み出された前記タグ
付きエントリが当該ＦＩＦＯ記憶装置（１００）の第２
出力ポート（１０２）を介して当該ＦＩＦＯ記憶装置
（１００）から出力される第２読取りポインタデバイス
（１３４）と、を有することを特徴とするＦＩＦＯ記憶
装置（１００）。

【００９８】２． 前記第２読取りポインタデバイス
（１３４）が前記第２のエントリ集合内にタグ付きエン
トリがあると判断すると、前記第２読取りポインタデバ
イス（１３４）は、タグ付きエントリと判断されたエン
トリに基づいてオフセットを計算し、前記オフセットが
前記第１読取りポインタアドレスの一つに追加されて前
記第２読取りポインタアドレスの一つが生成され、該生
成された第２読取りポインタアドレスは、前記タグ付き
エントリと判断されたエントリの記憶されている前記第
２記憶素子（１３１）内の記憶領域に対応する上記１記
載のＦＩＦＯ記憶装置（１００）。

【００９９】３． 優先順位が低いタグ付きエントリが
前記第２出力ポート（１０２）から出力される前に、優
先順位の最も高いタグ付きエントリが前記第２出力ポー
ト（１０２）から出力されるように、前記第２読取りポ
インタデバイス（１３４）がタグ付きエントリに優先順
位を付与する上記２記載のＦＩＦＯ記憶装置（１０
０）。

【０１００】４． 前記優先順位の最も高いタグ付きエ
ントリが前記第２出力ポート（１０２）から出力される
前に、前記第２記憶素子のポート出力レジスタ（１３
６）に送出され、当該ＦＩＦＯ記憶装置（１００）の外
部にあるコントローラ（９１）から前記第２読取りポイ
ンタデバイス（１３４）がアンロード信号を受け取った
際に、前記ポート出力レジスタ（１３６）にあるタグ付
きエントリが前記第２出力ポート（１０２）を介して当
該ＦＩＦＯ記憶装置（１００）から出力される上記３記
載のＦＩＦＯ記憶装置（１００）。

【０１０１】５． 前記第１記憶素子（１４６）に記憶
されている前記第１のエントリ集合内の各エントリが前
記第２記憶素子（１３１）に記憶されているエントリの
一つと関連付けられ、前記第１記憶素子（１４６）に記
憶されているエントリが前記第１出力ポート（１０１）
を通じて当該ＦＩＦＯ記憶装置（１００）から出力され
る前に、出力されるべきエントリが前記第１記憶素子
（１４６）のポート出力レジスタ（１３８）に格納さ
れ、前記コントローラ（９１）から前記第１読取りポイ
ンタデバイス（１５３）によってアンロード信号が入力
されると、前記第１記憶素子（１４６）の前記ポート出
力レジスタ（１３８）に格納されているエントリが第１
出力ポート（１０１）を介して当該ＦＩＦＯ記憶装置
（１００）から出力され、前記第１記憶素子（１４６）
の前記ポート出力レジスタ（１３８）内にある関連付け
られたエントリが前記第１出力ポート（１０１）から出
力される前に、前記第２記憶素子（１３１）の前記ポー
ト出力レジスタ（１３６）内にある関連付けられたエン
トリが前記第２出力ポート（１０２）に出力される上記
４記載のＦＩＦＯ記憶装置（１００）。

【０１０２】６． 前記第２のエントリ集合内の一つの
タグ付きエントリと関連付けられた前記第１のエントリ
集合内の一つのエントリもタグ付きであり、前記第１記
憶素子（１４６）の前記ポート出力レジスタ（１３８）
に格納されたエントリがタグ付きエントリであるかを前
記コントローラ（９１）が判断し、前記第２記憶素子
（１３１）の前記ポート出力レジスタ（１３６）に格納
された関連付けられたタグ付きエントリが前記第２記憶
素子（１３１）の前記ポート出力レジスタ（１３６）か
らアンロードされ、前記第２出力ポート（１０２）を介
して当該ＦＩＦＯ記憶装置（１００）から出力された後
に、初めて前記のコントローラ（９１）が前記第１読取
りポインタデバイス（１５３）に前記アンロード信号を
送出する上記５記載のＦＩＦＯ記憶装置（１００）。

【０１０３】７． グラフィックス記憶システム（２
０）に実装され、フレームバッファメモリデバイス（４
５）にアクセスするために前記グラフィックス記憶シス
テム（２０）内で使用され、前記フレームバッファメモ
リデバイス（４５）がメモリバンク０およびメモリバン
ク１を有し、前記第１のエントリ集合が前記フレームバ
ッファメモリデバイス（４５）内の列アドレスに対応
し、該列アドレスがバンク０の列アドレスおよびバンク
１の列アドレスを含み、前記第２のエントリ集合が前記
フレームバッファメモリデバイス（４５）内の行アドレ
スに対応し、該行アドレスがバンク０の行アドレスとバ
ンク１の行アドレスを含むとともに、前記バンク０の行
アドレスかバンク１の行アドレスかを示すために各行ア
ドレスがバンクビットによってタグ付けされ、前記バン
ク０の行アドレスがバンク０の再ページングを必要とす
るかを示すためにバンク０の各行アドレスがページング
ビットによってタグが付されており、前記バンク１の行
アドレスがバンク１の再ページングを必要とするかを示
すためにバンク１の各行アドレスがページングビットに
よってタグ付けされ、ページングビットでタグ付けされ
たバンク０とバンク１の行アドレスのみが前記第２出力
ポート（１０２）を介して当該ＦＩＦＯ記憶装置（１０
０）から出力される上記２記載のＦＩＦＯ記憶装置（１
００）。

【０１０４】８． 前記第２読取りポインタデバイス
（１３４）は、前記第２記憶素子（１３１）に記憶され
ページングビットでタグ付けされている前記バンク０の
行アドレス中の前記第２記憶素子（１３１）内に先行す
るバンク０の行アドレスを持たない行アドレスを判断す
ることによって、バンク０のダンプ候補を識別し、前記
第２記憶素子（１３１）に記憶されページングビットで
タグ付けされている前記バンク１の行アドレス中の前記
第２記憶素子（１３１）内に先行するバンク１の行アド
レスを持たない行アドレスを判断することによって、バ
ンク１のダンプ候補を識別し、最も高い優先順位を有す
る前記ダンプ候補を判断して前記ダンプ候補の一つを選
択する行アドレス選択プロセスに従ってタグ付きエント
リに優先順位を付与し、前記第２記憶素子（１３１）内
の選択された候補の記憶領域に基づいてオフセットが計
算され、前記オフセットを用いて生成される行アドレス
が前記第２記憶素子（１３１）の前記ポート出力レジス
タ（１３６）に送出され、選択された候補に対応する前
記ページングビットがクリアされ、次の選択された候補
を識別するために前記選択プロセスが繰り返され、前記
第２読取りポインタデバイス（１３４）によって前記コ
ントローラ（９１）からアンロード信号が受け取られる
と、前記第２記憶素子（１３１）の前記ポート出力レジ
スタ（１３６）に格納された行アドレスが前記第２出力
ポート（１０２）を介して前記第２記憶素子（１３１）
の前記ポート出力レジスタ（１３６）から出力され、前
記次の選択された候補に対応する行アドレスを前記第２
記憶素子（１３１）の前記ポート出力レジスタ（１３
６）に送出する上記７記載のＦＩＦＯ記憶装置（１０
０）。

【０１０５】９． 前記コントローラ（９１）が、前記
フレームバッファメモリデバイス（４５）のバンク０お
よびバンク１へのアクセスを制御するＲＡＭコントロー
ラ（９１）である上記８記載のＦＩＦＯ記憶装置（１０
０）。

【０１０６】１０． ページングビットによってタグ付
けされた各行アドレスが、該各行アドレスに関連付けら
れ、ページング同調ビットによってタグ付けされた列ア
ドレスを有し、前記第１読取りポインタデバイス（１５
３）によって生成される第１読取りポインタアドレス
を、前記列アドレスを第１記憶素子（１４６）内の各記
憶領域から先入れ先出し（ＦＩＦＯ）方式で読み出し、
前記第１記憶素子（１４６）の前記ポート出力レジスタ
（１３８）にロードさせるとともに、前記ＲＡＭコント
ローラ（９１）が、前記第１記憶素子（１４６）の前記
ポート出力レジスタ（１３８）での列アドレスがページ
ング同調ビットによってタグ付けされているかを判断
し、前記第１読取りポインタデバイス（１５３）に前記
アンロード信号を送り、前記タグ付けされた列アドレス
と関連付けられた前記第２記憶素子（１３１）の前記ポ
ート出力レジスタ（１３６）に格納された行アドレス
が、前記第２記憶素子（１３１）の前記ポート出力レジ
スタ（１３６）からアンロードされ、前記第２出力ポー
ト（１０２）を介して当該ＦＩＦＯ記憶装置（１００）
から出力された後に、前記アンロード信号が前記第１読
取りポインタデバイス（１５３）に送出される上記９記
載のＦＩＦＯ記憶装置（１００）。

【０１０７】

【発明の効果】以上の説明から明らかなように、本発明
のページングオーバヘッド低減のためのグラフィックス
記憶システム用インテリジェンス内蔵ＦＩＦＯ記憶装置
は、フレームバッファメモリのバンクに対する再ページ
ングを隠すことによって、ページングオーバヘッドを低
減できるようになる。

【図面の簡単な説明】

【図１】本発明の実施形態のグラフィックス記憶システ
ムを装備したコンピュータグラフィックスディスプレイ
システムの構成を示すブロック図である。

【図２】図１中のコンピュータグラフィックスディスプ
レイシステムに装備したグラフィックス記憶システムの
構成を示すブロック図である。

【図３】図２中のグラフィックス記憶システムに装備す
るフレームバッファコントローラの構成を示すブロック
図である。

【図４】図３のフレームバッファコントローラに装備す
るメモリコントローラの構成を示すブロック図である。

【図５】実施形態にあってＦＩＦＯポートおよびＦＩＦ
Ｏポートに入出力される情報のタイプを例示したＦＩＦ
Ｏのブロック図である。

【図６】図５中に示すページングオーバヘッド低減のた
めにＦＩＦＯに内蔵されているインテリジェンスを例示
したブロック図である。

【図７】（ａ）から（ｃ）実施形態にあってシフトレジ
スタのブロック図である。

【図８】図６に示すインテリジェントなＦＩＦＯにおけ
るページングオーバヘッド低減用ロジックを例示するエ
ントリを説明するための図である。

【図９】他の実施形態においてトランザクションが関連
付けられているバッチを指示するために使用されるシフ
トレジスタを示すブロック図である。

【図１０】図９中のシフトレジスタを用いた実施形態に
おけるインテリジェントＦＩＦＯの構成を示すブロック
図である。

【図１１】図１０中のインテリジェントＦＩＦＯにおけ
るロジックを例示するエントリを説明するための図であ
る。

【符号の説明】

２０ グラフィックス記憶システム ４５ ＲＡＭ ９１ ＲＡＭコントローラ １００ ＦＩＦＯ １０１ 入力ポート １０２ 行出力ポート １３１ 行ラッチ配列（記憶素子） １３４ 行読取りポインタコンポーネント １３６ 行ポート出力レジスタ １４６ 主ラッチ配列（記憶素子） １５３ 主読取りポインタコンポーネン（読取りポイン
タデバイス）

Claims (1)

【特許請求の範囲】
1. 【請求項１】 ＦＩＦＯ（先入れ先出し）記憶装置（１
   ００）において、当該ＦＩＦＯ記憶装置（１００）の入
   力ポートから第１のエントリ集合を受け取り、書込みポ
   インタデバイスによってアドレス指定される記憶領域に
   前記第１のエントリ集合の各エントリを格納する第１記
   憶素子（１４６）と、 前記入力ポートから第２のエントリ集合を受け取り、前
   記書込みポインタデバイスによってアドレス指定される
   記憶領域に前記第２のエントリ集合の各エントリを格納
   する第２記憶素子（１３１）と、 前記第１記憶素子（１４６）内の第１読取りポインタア
   ドレスを決定する手段であって、前記第１記憶素子（１
   ４６）内の記憶領域から前記第１のエントリ集合を読み
   出す際に、前記第１読取りポインタアドレスが前記第１
   記憶素子（１４６）内の記憶領域のアドレス指定に使用
   され、前記第１記憶素子（１４６）から読み出されたエ
   ントリが当該ＦＩＦＯ記憶装置（１００）の第１出力ポ
   ート（１０１）を介して当該ＦＩＦＯ記憶装置（１０
   ０）から出力する第１読取りポインタデバイス（１５
   ３）と、 前記第２のエントリ集合内にタグ付きエントリがあるか
   を判断し、前記第２のエントリ集合内のタグ付きエント
   リに基づいて第２読取りポインタアドレスを計算し、前
   記第２読取りポインタアドレスを用いて前記第２のエン
   トリ集合内の前記タグ付きエントリを前記第２記憶素子
   （１３１）内の各記憶領域から読み出す手段であって、
   前記第２記憶素子（１３１）から読み出された前記タグ
   付きエントリが当該ＦＩＦＯ記憶装置（１００）の第２
   出力ポート（１０２）を介して当該ＦＩＦＯ記憶装置
   （１００）から出力される第２読取りポインタデバイス
   （１３４）と、を有することを特徴とするＦＩＦＯ記憶
   装置（１００）。