JP3776202B2 - アドレス衝突検出回路 - Google Patents
アドレス衝突検出回路Info
- Publication number
- JP3776202B2 JP3776202B2 JP11673297A JP11673297A JP3776202B2 JP 3776202 B2 JP3776202 B2 JP 3776202B2 JP 11673297 A JP11673297 A JP 11673297A JP 11673297 A JP11673297 A JP 11673297A JP 3776202 B2 JP3776202 B2 JP 3776202B2
- Authority
- JP
- Japan
- Prior art keywords
- address
- latest
- access
- memory
- received
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
- G06F9/3824—Operand accessing
- G06F9/3834—Maintaining memory consistency
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0875—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with dedicated cache, e.g. instruction or stack
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Software Systems (AREA)
- Memory System (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明はコンピュータ・システムに関するもので、特にコンピュータ・システムにおけるグラフィック表示装置の画像表示のためグラフィック・コントローラ内のフレーム・バッファにアクセスする場合に発生する可能性のあるキャッシュ衝突を検出するグラフィック・コントローラに関するものである。
【０００２】
【従来の技術】
グラフィックス・コントローラ・カードの複雑性はますます増加し、単一のコマンドから複合的演算を実行するケースが増加して来ている。このような複合演算は、指定された規則に従って、表示装置にデータを表示するために使用されるフレーム・バッファ・メモリの現在の内容を変更することをしばしば必要とする。これらの複合演算は、その性質上、フレーム・バッファ・メモリに対する複数のアクセス、特にフレーム・バッファ・メモリの範囲内の同一位置に対する複数のアクセがそれらが元々指定されたものと同じ順序で実行されるべきことを必要とする。フレーム・バッファ・メモリのアクセスにはターンアラウンド・タイムがあるので、１回の読取りおよびそれに続く１回の書込みに要する時間は、２つの連続した読取りまたは２つの連続した書込みの場合よりも長い。従って、フレーム・バッファ・メモリを修正する際に最高の処理性能を達成するため、多くの場合、コントローラは可能な限り多くの演算を待ち行列化し、次に、フレーム・バッファ・メモリからデータを読み取る連続読取り演算を発し、読み取ったデータに関する修正を実行し、次にフレーム・バッファ・メモリに新しいデータを書き戻す連続書込み演算を発する。
【０００３】
より迅速な処理性能に対する要求と複合演算の要件を合致させるため、コントローラーは、ある所与のメモリ・アクセスが以前のアクセスと「衝突する」か否かを検出する機能を有していなければならない。すなわち、現在次アクセスと同じメモリ・アドレスに関して、以前のアクセスによって取得されたデータが既に待ち行列に保持されているか否かを検出することができなければならない。そのような衝突が検出されれば、コントローラは、新しいメモリ・アクセスを実行する前にその待ち行列を消去するか、あるいは、以前のアクセスによるデータに関してなされる修正結果を新しいアクセスが使用することができるようになにがしかのタグを付けなければならない。これらの操作のいずれを実行するにしても、衝突、すなわち、現在時アクセスと同じメモリ・アドレスに対して行われた以前のメモリ・アクセスによるデータが待ち行列に存在することを検出するメカニズムが必要となる。
【０００４】
メモリ・アドレスの衝突を検出するための典型的な方法は、コンテント・アドレッサブル・メモリとも呼ばれる連想メモリを使用する。連想メモリにおいては、各アクセスのアドレスが、データおよび有効性を示す「タグ」ビットと共に記憶される。新しいメモリ・アクセスが実行される場合、新しいメモリ・アクセスのアドレスが、連想メモリに現在保有されているすべての有効エントリのアドレスと連想メモリによって並列的に比較される。これと同じメカニズムは、従来からあるキャッシュ・システムおよび仮想メモリ・システム内部のプロセッサにおいても使用されている。
【０００５】
【発明が解決しようとする課題】
連想メモリは非常によく機能するとはいえ、並列比較を実行するために必要とされるハードウェアは非常に高価である。従って、メモリからデータを読み取る際に発生する可能性のあるキャッシュ衝突を効率的に検出する方法または装置が必要とされる。更に、連想メモリにおいて使用されている高価な並列比較を使用しない衝突検出方法または装置が必要とされる。
【０００６】
【課題を解決するための手段】
本発明は、１つの局面において、メモリからデータを読み取る際に発生する可能性のあるキャッシュ衝突を検出する手段を提供する。別の局面において、本発明は、グラフィック・オブジェクトに関する演算を実行する場合に上記のような衝突を検出する手段を提供する。
【０００７】
上記手段を実現するため、本発明は、例えばコンピュータ・システムのグラフィック表示サブシステム内におけるフレーム・バッファ・メモリとして使用される２次元メモリ・アレイ内での衝突の可能性を検出する衝突検出システムによって達成される。本発明の上記システムにおいて、メモリに対する最も最近のアクセスのアドレスまたはキャッシュ・バッファを消去した後のメモリに対する最初のアクセスのアドレスが保持される。その後、本発明の衝突検出システムは、後続のフレーム・バッファ・メモリ・アクセスの相対的位置のみに関心を持つ。本システムは、以前のフレーム・バッファ・メモリ・アクセスのすべての相対的位置を追跡し、メモリ・アクセスの流れが衝突を発生させる可能性があるような形態で以前のアクセス位置の方向へ戻る場合に潜在的衝突または「キャッシュ・ヒット」フラグをたてる。
【０００８】
これを達成するため、本発明のシステムは、フレーム・バッファ・メモリに対する最新アクセスのアドレスのＸおよびＹ位置と共に、当該メモリ・アクセスのアドレスに対して左右上下または斜め左上、右上、左下あるいは右下の位置で当該メモリ・アクセスより以前にメモリ・アクセスが行われたことがあることを標示する９個の状態ビットを保持する。本システムは、次に、現在時メモリ・アクセスのＸおよびＹ両成分のアドレスを上記最新メモリ・アクセス・アドレスＸおよびＹ成分と比較して、最新メモリ・アクセスに対する現在時メモリ・アクセスの方向を決定する。本システムは、方向を決定した後、この方向を上記９個の状態ビットの１つと比較して、その方向におけるメモリ・アクセスが既にあったことを該状態ビットが標示する場合、システムは潜在的ヒットを識別する。本システムは、各メモリ・アクセスの後、状態ビットが最後にリセットされた時以後のすべてのアクセスのアドレス位置を標示するように９個の状態ビットを更新する。
【０００９】
本発明の１つの局面において、本システムは、メモリを１次元のみを持つものとみなし、現在時アクセスに比較して高低のアクセスを追跡し、フレーム・バッファ・メモリに対するすべての以前のアクセスの相対的位置を保持し、メモリ・アクセスの流れが衝突を発生させる可能性があるような形態で以前のアクセス位置の方向へ戻る場合に、潜在的衝突または「キャッシュ・ヒット」を示すフラグをたてる方法を含む。
【００１０】
【発明の実施の形態】
以下は、本発明を実施する現時点で最良のものと考えられる形態を記述するものである。以下の記述は、本発明の一般的理念を記述するためにのみ行うものであり、本発明をその記述内容に限定する意図を持つものではない。
【００１１】
図１は、本発明を実施するグラフィック・コントローラを含むコンピュータ・システムを示す。コンピュータ・システム１００は、システム・バス１０４を経由してコンピュータ・システム１００の他のエレメントと通信する処理エレメント１０２を含む。キーボード１０６およびグラフィック・ロケータ装置１０８はコンピュータ・システム１００への入力を提供し、一方、グラフィック・コントローラ１０９および表示装置１１０はコンピュータ・システム１００からの出力を提供する。本発明は、グラフィック・コントローラ１０９の範囲内に含まれる。
【００１２】
データ記憶装置１１２が典型的にはコンピュータ・システム１００の範囲内のデータおよびソフトウェアを記憶し、メモリ１１６は、オペレーティング・システム１１８、およびグラフィック・コントローラ１０９のサービスを利用するアプリケーション・プログラム１２０を典型的には含む。
【００１３】
図２は、グラフィック・コントローラ１０９の回路部分を示す。オブジェクト分解回路２０２は、システム・バス１０４からデータおよびコマンドを受け取り、これら複合コマンドをメモリ・コントローラ２１２が実行することができる比較的単純な演算に分解する。これら比較的単純な演算は、フレーム・バッファ・メモリ２１０に対する多数のread-modify-write(読取り−修正−書込み)演算を含む。フレーム・バッファ・メモリ２１０のアクセスにはターンアラウンド・タイムがあるので、１回の読取りおよびそれに続く１回の書込みに要する時間は、２つの連続した読取りまたは２つの連続した書込みの場合よりも長い。
【００１４】
フレーム・バッファ・メモリを修正する際に最高の処理性能を達成するため、メモリ・コントローラ２１２は可能な限り多くの演算を待ち行列化する。メモリ・コントローラ２１２は、次に、連続読取り演算を発してフレーム・バッファ・メモリからデータを読み取って、このデータをキャッシュ２０６に記憶する。次いで、メモリ・コントローラ２１２は、キャッシュ２０６のデータに対する修正を実行し、フレーム・バッファ・メモリ２１０に新しいデータを書き戻す連続書込み演算を実行する。
【００１５】
しかしながら、この高い処理性能を達成するため、メモリ・コントローラ２１２は、フレーム・バッファ２１０から取り出されキャッシュ２０６に記憶されるべきデータのアドレスがキャッシュ２０６内に既に保持されているデータのアドレスと「衝突する」か否かを検出する衝突検出回路２１４を必要とする。この「衝突」は、潜在的衝突が起きる可能性のある時は必ずヒット信号２１６を送信する衝突検出回路２１４によって標示される。すなわち、本発明の衝突検出回路２１４は、衝突が発生したこと、あるいは、衝突が発生する可能性のあることを検出する。
【００１６】
本発明の好ましい実施形態は、２次元フレーム・バッファ・メモリを使用するが、代替的には１次元メモリを使用する。この代替的実施形態においては、図３に示されるように、衝突検出回路２１４は、３個の方向状態ビットおよび１つの最新アクセス・レジスタのみを持つ。最新アクセス・アドレス・レジスタ３０２は、最新のメモリ・アクセスのアドレスを記憶し、中央状態ビット３０６は、最新アクセス・アドレス・レジスタ３０２が有効アドレスを含むか否かを標示する。低位アクセス方向状態ビット３０４は、最新アクセス・アドレス・レジスタ３０２に含まれるアドレスより低位のアドレスを持つアクセスが以前に発生したことがあることを標示し、高位アクセス方向状態ビット３０８は、最新アクセス・アドレス・レジスタ３０２に含まれるアドレスより高位のアドレスを持つアクセスが以前に発生したことがあることを標示する。
【００１７】
この代替実施形態において、コントローラは、最新メモリ・アクセス・アドレス・レジスタに任意の値を記憶しすべての３つの状態ビットをクリアした状態で、処理を開始する。最初のメモリ・アクセスが受け取られると、システムは、状態ビットがすべてクリアされていることを検出し、従って以前の履歴が状態ビット内に存在しないので、メモリ・アクセスの発生を許容する。次に、システムはこのメモリ・アクセスのアドレスを最新アクセス・アドレス・レジスタ３０２に記憶し、また、中央状態ビット３０６をセットして最新アクセス・アドレス・レジスタ３０２が有効値を含むことを標示する。
【００１８】
中央状態ビット３０６がセットされた後、現在時アクセスと呼ばれる別のメモリ・アドレスが受け取られると、システムは、現在時アクセスのアドレスを最新アクセス・アドレス・レジスタ３０２の値と比較する。それらが等しければ、システムはヒットを宣言する。それらが等しくない場合、システムは、現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より低いか高いかを判断する。例えば、現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より高いと仮定すれば、システムは高位アクセス方向状態ビット３０８を検査して、ここでは高位アクセス方向状態ビット３０８はセットされてないので、そのアクセスは許容される。アクセスを許容した後、システムは、現在時アクセスのためのメモリ・アドレスを最新アクセス・アドレス・レジスタ３０２に記憶し、低位アクセス方向状態ビット３０４をセットして、最新アクセス・アドレス・レジスタ３０２に現在含まれる値より低いアドレスを持つアクセスが以前に発生したことを標示する。低位アクセス状態ビットがセットされる理由は、現在時アクセスのアドレスが今や最新アクセス・アドレス・レジスタ３０２に記憶され、それより前すなわち現在時アクセスが発生する前に記憶されていたアドレスが現在時アクセス・アドレスより低かったためである。
【００１９】
次に新しい別のメモリ・アドレスが受け取られると、システムは、この現在時アクセス・アドレスを最新アクセス・アドレス・レジスタ３０２に記憶された値と比較する。それらが等しければ、当然のことながらシステムはヒットを宣言する。等しくなければ、システムは現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より低いか高いかを判断する。ここで例えば現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より高いと仮定すれば、高位アクセス方向状態ビット３０８がセットされてないので、そのアクセスは許容される。しかし、現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より低いと仮定すれば、(低位アクセス状態ビットがセットされていることによって)最新アクセス・アドレス・レジスタ３０２の値より低いアドレスを持つアクセスが以前に発生していることが標示されているので、ヒットが宣言される。新しいメモリ・アクセスの値が最後アクセス・レジスタ３０２の値より高い限りは、衝突が発生する可能性はないので、アクセスは許容され続ける。アドレスが等しいかまたは低いアクセスを最初に受け取った時、衝突が発生する可能性があるので、ヒットが宣言される。
【００２０】
このシステムは保守的であり、実際に何も存在しない場合にヒットを標示する可能性がある。例えば、第１のアクセスがアドレスＸで発生し、第２のアクセスがＸ＋１で発生したと仮定すれば、次に第３のアクセスがＸ−１で発生すれば、システムは衝突を標示するであろう。なぜならば、アドレスＸ＋１における第２のアクセスがシステムが記憶する最新のアクセス・アドレスであるが、システムは、Ｘ＋１より低位のアドレスに対する少くとも１つのアクセス(実際にはアドレスＸへのアクセス)があったことをも記憶している。従って、アドレスＸ−１が受け取られると、Ｘ−１はＸ＋１より低いので、システムは、ヒットを標示するフラグをたてる。システムはＸ−１がＸより低位にあることすなわち実際にはヒットが発生しないことを判断しない。Ｘ＋１より低位のいかなるアクセスもヒットを派生することをシステムが判断できれば十分である。
【００２１】
本発明の好ましい実施形態の２次元フレーム・バッファに関しては、９個の状態ビットが使用される。図４には、以前のアクセスを標示するために使用される９つの方向状態ビットが示されている。９つの方向状態ビットは、最新アクセス・アドレス・レジスタが有効なＸおよびＹ位置を含むか否かを標示する中央有効性ビット４１０を含む。中央上方向状態ビット４０４は、以前のアクセスが最新アクセス・アドレスより上の位置で発生したこと、すなわち、ボックス４０４内の記号「＝Ｘ」および「＜Ｙ」で示されているように以前のアクセスのＸアドレスは同じでＹアドレスが低位であることを標示する。同様に、中央左方向状態ビット４０８は、以前のアクセスが最新アクセス・アドレスより左の位置で発生したこと、すなわち、ボックス４０８内の記号「＜Ｘ」および「＝Ｙ」で示されているように以前のアクセスのＸアドレスは低位でＹアドレスが同じであることを標示する。中央右方向状態ビット４１２は、以前のアクセスが最新アクセス・アドレスより右の位置で発生したこと、すなわち、ボックス４１２内の記号「＞Ｘ」および「＝Ｙ」で示されているように以前のアクセスのＸアドレスは高位でＹアドレスが同じであることを標示する。中央下方向状態ビット４１６は、以前のアクセスが最新アクセス・アドレスより下の位置で発生したこと、すなわち、ボックス４１６内の記号「＝Ｘ」および「＞Ｙ」で示されているように以前のアクセスのＸアドレスは同じでＹアドレスが高位であることを標示する。
【００２２】
更に他の４つの方向状態ビットは、以前のアクセスが最新アクセスに対して斜め方向で発生したか否かを標示する。左上方向状態ビット４０２は、以前のアクセスが最新アクセス・アドレスに対して左上の位置で発生したこと、すなわち、ボックス４０２内の記号「＜Ｘ」および「＜Ｙ」で示されているように以前のアクセスのＸアドレスは低位でＹアドレスも低位であることを標示する。同様に、右上方向状態ビット４０６は、ボックス４０６内の記号「＞Ｘ」および「＜Ｙ」で示されているように、以前のアクセスが最新アクセス・アドレスに対して右上のアドレスで発生したことを標示する。左下方向状態ビット４１４は、ボックス４１４内の記号「＜Ｘ」および「＞Ｙ」で示されているように、以前のアクセスが最新アクセス・アドレスに対して左下のアドレスで発生したことを標示し、右下方向状態ビット４１８は、ボックス４１８内の記号「＞Ｘ」および「＞Ｙ」で示されているように、以前のアクセスが最新アクセス・アドレスに対して右下のアドレスで発生したことを標示する。
【００２３】
注：本明細書および添付図面において、左、右、上、下、左上、右上、左下、右下および中央の位置を、それぞれ次の( )内の略称として、ＣＬ(Center Left)、ＣＲ(Center Right)、ＡＣ(Above Center)、ＢＣ(Below Center)、ＡＬ(Above Left)、ＡＲ(Above Right)，ＢＬ(Below Left)、ＢＲ(Below Right)およびＣ(Center)という記号で表す場合がある。
【００２４】
以下の例は、図４で示された状態ビットが本発明の衝突検出回路によって使用される様態を示す。この例では、ピクセルを左から右へ上から下へ処理して各ピクセルを変更することによって、１つの長方形がラスタ化または描出される。本処理例の開始時において、以前のアクセス履歴がないことを標示するため、すべての９つの状態ビットがクリアされる。この動作は、システムの起動時またはキャッシュがすべて消去された時のいずれかに行われる。
【００２５】
メモリ・アクセスがオブジェクト分解装置２０２から受け取られる時、中央ビット４１０が有効な以前のアクセス履歴が存在しないことを標示するので、衝突検出システムは比較を行わない。システムは、このメモリ・アクセスのアドレスをＸおよびＹレジスタに記憶し、中央ビット４１０をセットして、最新メモリ・アクセスの履歴が存在することを標示する。
【００２６】
後続のメモリ・アクセスは、長方形の描出の典型的順序に従って、左から右、上から下へ進む。現在時アクセスと呼ばれる別のメモリ・アクセスが受け取られると、このアクセスのアドレスは最新のメモリ・アクセスの右にある、すなわち、Ｘアドレス位置は最新のメモリ・アクセスより大きくＹアドレス位置は最新のメモリ・アクセスと同じである。衝突検出システムがこの現在時アクセス・アドレスを受け取ると、アドレスのＸおよびＹ部分を最新のメモリ・アクセス・アドレスと比較し、Ｘ比較は「より大」をＹ比較は「等しい」を示す。上記の比較の結果、システムは「＞Ｘ」および「＝Ｙ」条件を示す中央右ビット４１２を検査し、中央右位置４１２がセットされていないことを認識する。従って、システムはこのアクセスを許容する。
【００２７】
上記アクセスが実行された後、システムは、(中央)左ビットをセットすることによって図４の状態ビット４０８を更新する。この結果、新たに更新された現在時アクセス・アドレスに対するアクセスより以前に現在時アクセス・アドレスの左側の位置でアクセスが行われたことがあることが標示される。システムは、今受け取ったアドレスをＸおよびＹアドレス・レジスタに記憶し、ＸおよびＹレジスタが有効であることを標示する中央ビット４１０をセットする。このようにして、２つのアクセスの後、システムは、前のアクセスがＸおよびＹアドレス・レジスタに記憶された最新のアクセス・アドレスのどこか左側にあったことを記憶する。メモリ・アクセスが左から右へ移動するにつれ、システムは、上述の通り、先行アクセスが現在位置の左側にすべてあったことを認識する。長方形の最初の行の最新のピクセルが書き込まれた後、(図２の)オブジェクト分解装置２０２は、処理を長方形の次の行の最左端のピクセルへ移動する。
【００２８】
次の行の最初のピクセルに関するメモリ・アドレスが受け取られると、システムはそのアドレスを検査し、当該アクセスが最新のアクセスの左下であると判断する。従って、システムは左下ビット４１４を検査し、このビットがセットされていないことがわかるので、該アクセスは許容される。このアクセスの後、システムは諸ビットを更新し、右上ビットをセットして、今や現在時アクセス・アドレス(具体的には最新のアクセス)の右上で発生したアクセスがあることを示す。前の状態が最新のアクセス・アドレスの左側に対するアクセスが存在したことを示していたので、中央上および左上ビットがそれら領域における可能なアクセス履歴を示すようにセットされる。実際には最新のアクセスの上および左でアクセスは発生していないけれども、最新のアクセスに先行するアクセスの左でアクセスが発生しているので、システムは、上および左のアクセスのすべてを、発生したものとしてフラグを立てなければならない。すなわち、以前の位置の左に何らかのアクセスが発生したが、システムは、どれ程左側に発生したかわからないので、以前の位置の左に位置していたすべてのアクセスが今や最新のアクセスの上および左にあることを示すようにフラグをたてる。しかし、システム方向状態ビットは、現在時メモリ・アクセス・アドレスの行の左側にも右側にもアクセスがなかったこと、また、現在時メモリ・アクセス・アドレスの下側にもアクセスがなかったことを標示する。
【００２９】
今や、ラスタ化処理は長方形の２行目の左から右へ継続し、コントローラは衝突なしのフラグを立て続ける。衝突なしのフラッグをたてるこの処理は長方形の最下部まで続く。
【００３０】
第２の例は、本発明のシステム内でヒットが発生する場合を示すものである。この例は、長方形の輪郭を描画する場合で、左上のコーナーから始まって、長方形の周囲の処理を時計回りに進めるものである。処理の開始時に、コントローラはすべての状態ビットをリセットする。最初のアドレスがＸおよびＹレジスタに記憶され、中央ビットが以前のアクセスがあったことを示すようにセットされる。アクセスが左から右へ進むにつれ、コントローラはアクセスが行の左側にアクセスがあったことを記憶するが、すべての新しいアクセスが最新のアクセスの右側にあるので、コントローラはヒットを示すフラグをたてない。
【００３１】
最上行セグメントが終了すると、オブジェクト分解装置は、最上行の最新のピクセル位置の直下からアクセスを開始する。長方形の右辺におけるアクセスは、それらが最新のアクセスの下にあるので、許容される。コントローラは、アクセスが上にあったこと、および左上方向のどこかにアクセスがあったことを認識する。長方形の右辺の処理を終了すると、オブジェクト分解装置は、長方形の底辺に沿って左へのステッピングを開始する。現在、コントローラはアクセスが同じ行の右側および上方のどこかにあったことを認識している。しかし、長方形の右側で底辺ピクセルの左に対しするアクセスがなかったので、長方形の底辺を規定する底辺ピクセルの左へ移動するアクセスは許容される。
【００３２】
最後に、長方形の底辺の処理を終了すると、オブジェクト分解装置は、長方形の左辺に沿って上昇するアクセスを開始する。長方形の左辺をのぼる最初のピクセルがアクセスされると、システムは、現在の「最新の」アドレスの真上である可能性のあるなんらかの上および左方向アクセスが既に発生していることを認める。
【００３３】
この時点においてキャッシュは消去され、方向状態ビットおよびＸ、Ｙアドレス・レジスタがクリアされる。次に、オブジェクト分解装置は、長方形の左辺をのぼるピクセルをアクセスする。キャッシュの消去後のすべての新しいアクセスは、衝突の可能性のない上方向への一線上の移動であるので、長方形の左辺上の処理の間、ヒットを示すフラグはたたない。
【００３４】
図５は、図２の好ましい実施形態の衝突検出回路部分のブロック図を示す。
フレーム・バッファ・アドレスバス２０４は、(図２の)オブジェクト分解装置２０２から(図２の)フレーム・バッファ２１０へメモリ・コントローラ２１２を経由して送付されるアドレスを受け取る。フレーム・バッファ・アドレスの「Ｘ」部分が、２つの比較器５０６よび５０８に回送され、そこで、アドレスのＸ部分が最新Ｘレジスタ５０２に記憶されている最新Ｘアドレス値と比較される。比較器５０６および５０８の出力は、ＥＱＸ信号５１４およびＬＴＸ信号５１６であり、これらの信号は、ＮＯＲゲートを使用して結合され、ＧＴＸ信号５１６が作成される。これらの３つの信号は、フレーム・バッファ・アドレス・バス２０４上のアドレスのＸ部分が、最新Ｘレジスタ５０２に記憶されている最新のＸアドレス値に等しい(ＥＱＸ)か、それより大(ＧＴＸ)かあるいは小(ＬＴＸ)であるか否かを標示する。
【００３５】
同様に、フレーム・バッファ・アドレスの「Ｙ」部分が、２つの比較器５１０よび５１２に回送され、そこで、アドレスのＹ部分が最新Ｙレジスタ５０４に記憶されている最新Ｙアドレス値と比較される。比較器５１０および５１２の出力は、ＥＱＹ信号５１８およびＬＴＹ信号５２０であり、これらの信号は、ＮＯＲゲートを使用して結合され、ＧＴＹ信号５１９が作成される。これらの３つの信号は、フレーム・バッファ・アドレス・バス２０４上のアドレスのＹ部分が、最新Ｙレジスタ５０４に記憶されている最新のＹアドレス値に等しい(ＥＱＹ)か、それより大(ＧＴＹ)かあるいは小(ＬＴＹ)であるか否かを標示する。
【００３６】
これらの６つの信号ＥＱＸ５１４、ＧＴＸ５１５、ＬＴＸ５１６、ＥＱＹ５１８、ＧＴＹ５１９およびＬＴＹ５２０は、アクセスが許容されるか否かを判断するため図４の状態ビットのいずれを検査しなければならないかを判断するために必要な信号を提供する。図５の残りの回路部分は、到来信号がＸより小さくＹより小さい場合ヒットが発生したか否かを判断するために使用される。
【００３７】
左上ラッチ５２２は、(図４の)左上ビット４０２を記憶する。ＡＮＤゲート５２４は、左上ラッチ５２２内の状態値を、ＬＴＸ信号５１６およびＬＴＹ信号５２０と結合する。フレーム・バッファ・アドレス２０４のＸ部分が、最新のＸ値５０２より小さい場合、ＬＴＸ信号５１６は論理値１である。同様に、フレーム・バッファ・アドレス２０４のＹ部分が、最新のＹ値５０４より小さい場合、ＬＴＹ信号５２０は論理値１である。左上ラッチ５２２が左上方向で既にアクセスが発生したことを標示するようにセットされていれば、上記２つの論理値の組み合わせはヒットを意味する。従って、すべての３つのビットが論理値１であれば、ＡＮＤゲート５２４の出力は論理値１となり、これにより、ＡＮＤゲートの出力である論理値１がその他の比較結果のその他のビットとＯＲゲート５２６によって論理ＯＲされると、この新しいアクセスが許容される前にキャッシュが消去されなければならないことを標示するヒット信号２１６がセットされる。
【００３８】
その他の８つの状態ビットに関する回路は、図４の方向状態ビット定義に従って比較器出力信号ＥＱＸ５１４、ＧＴＸ５１５、ＬＴＸ５１６、ＥＱＹ５１８、ＧＴＹ５１９とＬＴＹ５２０という異なる信号を使用することを当然除いて、上記の左上ラッチ５２２およびＡＮＤゲート５２４と同様である。ＯＲゲート５２６は状態比較のすべての出力を結合して、ヒット信号２１６を生成する。
【００３９】
アクセスが発生する都度、図４に示される９個の状態ビットのすべては更新されなければならない。アクセスが許容されなければ、キャッシュは消去され、すべての状態ビットはクリアされる。アクセスが許容される場合、下記表１に示される式に従って、各タイプのアクセスの発生後９つの状態ビットの各々が更新される。例えば、表１の最初のエントリは、前のアクセスの左上にアクセスが発生した後に９個の状態ビットを更新するための式を示し、第２のエントリは、前のアクセスのすぐ上にアクセスが発生した後に９個の状態ビットを更新するための式を示し、以下のエントリも同様にそれぞれ対応する状態ビットを更新する式を示す。
【００４０】
下記表２は、左上の状態ビットを更新するための式を示す。この式は、表１に示されている左上の状態ビットに対する更新のすべてを論理ＯＲ演算を使用して結合することによって作成されている。その他の８個の状態ビットを更新する式も、同様に、表１に示されているそれぞれの状態ビットに対する更新のすべてを論理ＯＲ演算を使用して結合することによって作成される。表１および表２の式において、記号"＋"は論理ＯＲ演算を示し、記号"・"は論理ＡＮＤ演算を示す。記号"＜＝"は「...によって置き換えられる」を意味する。
【００４１】
【表１】
// 新しいアクセスが左上の場合
AL <= AL
AC <= AL
AR <= AC + AR
CL <= AL
C <= '1'
CR <= AC + AR
BL <= CL + BL
BC <= CL + BL
BR <= C + CR + BC + BR
// 新しいアクセスが真上の場合
AL <= AL
AC <= AC
AR <= AR
CL <= AL
C <= '1'
CR <= AR
BL <= BL + CL
BC <= BC + C
BR <= BR + CR
// 新しいアクセスが右上の場合
AL <= AL + AC
AC <= AR
AR <= AR
CL <= AL + AC
C <= '1'
CR <= AR
BL <= BL + CL + C + BC
BC <= BR + CR
BR <= BR + CR
// 新しいアクセスが真左の場合
AL <= AL
AC <= AL
AR <= AR + AC
CL <= CL
C <= '1'
CR <= CR + C
BL <= BL
BC <= BL
BR <= BR + BC
// 新しいアクセスが最新アクセスと同じ場合
AL <= AL
AC <= AC
AR <= AR
CL <= CL
C <= '1'
CR <= CR
BL <= BL
BC <= BC
BR <= BR
// 新しいアクセスが真右の場合
AL <= AL + AC
AC <= AR
AR <= AR
CL <= CL + C
C <= '1'
CR <= CR
BL <= BL + BC
BC <= BR
BR <= BR
// 新しいアクセスが左下の場合
AL <= AL + CL
AC <= AL + CL
AR <= AL + AR + C + CR
CL <= BL
C <= '1'
CR <= BC + BR
BL <= BL
BC <= BL
BR <= BC + BR
// 新しいアクセスが真下の場合
AL <= AL + CL
AC <= AC + C
AR <= AR + CR
CL <= BL
C <= '1'
CR <= BR
BL <= BL
BC <= BC
BR <= BR
// 新しいアクセスが右下の場合
AL <= AL + AC + CL + C
AC <= AR + CR
AR <= AR + CR
CL <= BL + BC
C <= '1'
CR <= BR
BL <= BL + BC
BC <= BR
BR <= BR
【００４２】
【表２】
AL <= LTX・LTY・AL
+ EQX・LTY・AL
+ GTX・LTY・(AL + AC)
+ LTX・EQY・AL
+ EQX・EQY・AL
+ GTX・EQY・(AL + AC)
+ LTX・GTY・(AL + CL)
+ EQX・GTY・(AL + CL)
+ GTX・GTY・(AL + AC + CL + C)
【００４３】
図６は、左上の状態ビットをセットする表２の式の論理の流れを示す。その他の８個の状態ビットに関して表１の式を結合することによって同様の論理を作成することが可能である点は当業者に認められることであろう。また、ブール代数定理を使用することによって、表２の論理式を縮小して、図６に示される論理よりも小さい論理セットを提供することが可能である点も当業者に認められることであろう。
【００４４】
３次元あるいはｎ次元のメモリでの使用のため本発明を拡張することができる点は当業者に認められることであろう。３次元の実施のためには、３次元の各々について２７ビットの記憶域および比較器が必要とされる。ｎ次元の実施のためには、ｎ次元の各々について３nビットの記憶域および比較器が必要とされる。
【００４５】
以上、本発明の好ましい実施形態を記述したが、上記記述は本発明をそのような実施形態に限定する意図を有するものではない。本発明の理念を逸脱することなく本発明の実施形態および構成に種々の変更および修正を加えることが可能である点は当業者に認められることであろう。
【００４６】
本発明には、例として次のような実施様態が含まれる。
（１）メモリに対する複数アクセスの間に発生するアドレス衝突を検出し、衝突が検出される場合ヒット信号を送信する回路であって、受け取った最新アドレスを保持する最新アドレス・レジスタと、以前のメモリ・アクセスが第１の方向で発生したという標識を記憶する第１方向状態ビットと、現在時メモリ・アドレスを上記最新アドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスに対して第１の方向に位置することを標示する比較器回路と、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスに対して第１の方向に位置することを上記比較器回路が標示し、かつ、上記第１方向状態ビットが以前のメモリ・アクセスが上記第１の方向で発生したことを標示する場合、ヒット信号を送信するヒット検出回路と、を備えるアドレス衝突検出回路。
（２）以前のメモリ・アクセスが上記第１の方向とは反対の第２の方向で発生したという標識を記憶する第２方向状態ビットと、現在時メモリ・アドレスを上記最新アドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスに対して第２の方向に位置することを標示する第２比較器回路と、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスに対して第２の方向に位置することを上記第２比較器回路が標示しかつ上記第２方向状態ビットが以前のメモリ・アクセスが上記第２の方向で発生したことを標示する時第２ヒット信号を送信する第２ヒット検出回路と、を更に備える上記（１）に記載のアドレス衝突検出回路。
（３）上記最新アドレス・レジスタ、上記第１方向状態ビットおよび上記第２方向状態ビットにおける状態情報の存在を標示する中央状態ビットを更に備える上記（２）に記載のアドレス衝突検出回路。
（４）現在時メモリ・アドレスを上記最新アドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスと等しいことを標示する第３比較器回路と、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスと等しいことを上記第３比較器回路が標示する時第３ヒット信号を送信する第３ヒット検出回路と、を更に備える上記（３）に記載のアドレス衝突検出回路。
【００４７】
（５）第１の次元としてＸアドレスを持ち第２の次元としてＹアドレスを持つ２次元アレイとして構成されるメモリにおける複数メモリ・アクセス間のアドレス衝突を検出し、衝突が検出される場合ヒット信号を送信する回路であって、受け取った最新アドレスを記憶する最新Ｘアドレス・レジスタと、受け取った最新アドレスを記憶する最新Ｙアドレス・レジスタと、以前のメモリ・アクセスが上、下、左または右方向で発生したという標識を記憶する４個の方向状態ビットと、現在時メモリ・アドレスを上記最新Ｘアドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスに対して左または右の方向に位置することを標示するＸ比較器回路と、現在時メモリ・アドレスを上記最新Ｙアドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対して上または下の方向に位置することを標示するＹ比較器回路と、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対して上、下、左または右の方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示し、上記ＸおよびＹ比較器回路によって標示される方向に対応する上記４個の方向状態ビットの１つが以前のメモリ・アクセスが上記対応する方向で発生したことを標示する時ヒット信号を送信するヒット検出回路と、を備えるアドレス衝突検出回路。
（６）上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタにおける状態情報の存在を標示する中央状態ビットを更に備える上記（５）に記載のアドレス衝突検出回路。
【００４８】
（７）現在時メモリ・アドレスが上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し下方向に位置することを上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが上方向で発生したことを標示するように上記４個の方向状態ビットの１つをセットする上状態更新回路と、現在時メモリ・アドレスが上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し上方向に位置することを上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが下方向で発生したことを標示するように上記４個の方向状態ビットの１つをセットする下状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスに対し右方向に位置することを上記Ｘ比較器回路が標示する時、以前のメモリ・アクセスが左方向で発生したことを標示するように上記４個の方向状態ビットの１つをセットする左状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスに対し左方向に位置することを上記Ｘ比較器回路が標示する時、以前のメモリ・アクセスが右方向で発生したことを標示するように上記４個の方向状態ビットの１つをセットする右状態更新回路と、を更に備える上記（５）に記載のアドレス衝突検出回路。
（８）以前のメモリ・アクセスが左上、左下、右上または右下の方向で発生したという標識を記憶する第２の４個の方向状態ビットと、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対して左上、左下、右上または右下の方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示し、上記ＸおよびＹ比較器回路によって標示される方向に対応する上記第２の４個の方向状態ビットの１つが以前のメモリ・アクセスが上記対応する方向で発生したことを標示する時ヒット信号を送信する第２ヒット検出回路と、を更に備える上記（５）に記載のアドレス衝突検出回路。
【００４９】
（９）現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し右下方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが左上方向で発生したことを標示するように上記第２の４個の方向状態ビットの１つをセットする左上状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し左上方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが右下方向で発生したことを標示するように上記第２の４個の方向状態ビットの１つをセットする右下状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し右上方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが左下方向で発生したことを標示するように上記第２の４個の方向状態ビットの１つをセットする左下状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し左下方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが右上方向で発生したことを標示するように上記第２の４個の方向状態ビットの１つをセットする右上状態更新回路と、を更に備える上記（８）に記載のアドレス衝突検出回路。
【００５０】
【発明の効果】
本発明によって、連想メモリにおいて使用されている高価な並列比較を使用せずに、メモリからデータを読み取る際に発生する可能性のあるキャッシュ衝突を効率的に検出する方法および装置を実現することができる。
【図面の簡単な説明】
【図１】本発明を実施するグラフィック・コントローラを含むコンピュータ・システムのブロック図である。
【図２】図１のグラフィック・コントローラのブロック図である。
【図３】本発明の代替実施形態において使用される３個の状態ビットおよび１つのアドレス・レジスタを示すブロック図である。
【図４】本発明の好ましい実施形態において、以前のアクセスを示すために使用される９個の状態ビットを示すブロック図である。
【図５】本発明の好ましい実施形態である図２の衝突検出回路部分示すブロック図である。
【図６】本発明の好ましい実施形態である図２の衝突検出回路部分の論理ブロック図である。
【符号の説明】
１００ コンピュータ・システム
１０２ 処理エレメント
１０４ システム・バス
１０６ キーボード
１０８ グラフィック・ロケータ装置
１０９ グラフィック・コントローラ
１１０ 表示装置
１１２ データ記憶装置
１１６ メモリ
１１８ オペレーティング・システム
１２０ アプリケーション・プログラム
２０２ オブジェクト分解回路
２０４ フレーム・バッファ・アドレス・バス
２０６ キャッシュ・メモリ
２１０ フレーム・バッファ
２１２ メモリ・コントローラ
２１４ 衝突検出回路
２１６ ヒット信号
３０２ 最新アクセス・アドレス・レジスタ
３０４ 低位アクセス状態ビット
３０６、４１０ 中央状態ビット
３０４ 高位アクセス状態ビット
４０２ 左上アクセス状態ビット
４０４ 上アクセス状態ビット
４０６ 右上アクセス状態ビット
４０８ 左アクセス状態ビット
４１２ 右アクセス状態ビット
４１４ 左下アクセス状態ビット
４１６ 下アクセス状態ビット
４１８ 右下アクセス状態ビット
５０２ 最新Ｘアドレス・レジスタ
５０４ 最新Ｙアドレス・レジスタ
５０６、５１０ Ｘアドレス比較器
５０８、５１２ Ｙアドレス比較器
５２２ 左上ラッチ器
５２４ ＡＮＤゲート
５２６ ＯＲゲート
【発明の属する技術分野】
本発明はコンピュータ・システムに関するもので、特にコンピュータ・システムにおけるグラフィック表示装置の画像表示のためグラフィック・コントローラ内のフレーム・バッファにアクセスする場合に発生する可能性のあるキャッシュ衝突を検出するグラフィック・コントローラに関するものである。
【０００２】
【従来の技術】
グラフィックス・コントローラ・カードの複雑性はますます増加し、単一のコマンドから複合的演算を実行するケースが増加して来ている。このような複合演算は、指定された規則に従って、表示装置にデータを表示するために使用されるフレーム・バッファ・メモリの現在の内容を変更することをしばしば必要とする。これらの複合演算は、その性質上、フレーム・バッファ・メモリに対する複数のアクセス、特にフレーム・バッファ・メモリの範囲内の同一位置に対する複数のアクセがそれらが元々指定されたものと同じ順序で実行されるべきことを必要とする。フレーム・バッファ・メモリのアクセスにはターンアラウンド・タイムがあるので、１回の読取りおよびそれに続く１回の書込みに要する時間は、２つの連続した読取りまたは２つの連続した書込みの場合よりも長い。従って、フレーム・バッファ・メモリを修正する際に最高の処理性能を達成するため、多くの場合、コントローラは可能な限り多くの演算を待ち行列化し、次に、フレーム・バッファ・メモリからデータを読み取る連続読取り演算を発し、読み取ったデータに関する修正を実行し、次にフレーム・バッファ・メモリに新しいデータを書き戻す連続書込み演算を発する。
【０００３】
より迅速な処理性能に対する要求と複合演算の要件を合致させるため、コントローラーは、ある所与のメモリ・アクセスが以前のアクセスと「衝突する」か否かを検出する機能を有していなければならない。すなわち、現在次アクセスと同じメモリ・アドレスに関して、以前のアクセスによって取得されたデータが既に待ち行列に保持されているか否かを検出することができなければならない。そのような衝突が検出されれば、コントローラは、新しいメモリ・アクセスを実行する前にその待ち行列を消去するか、あるいは、以前のアクセスによるデータに関してなされる修正結果を新しいアクセスが使用することができるようになにがしかのタグを付けなければならない。これらの操作のいずれを実行するにしても、衝突、すなわち、現在時アクセスと同じメモリ・アドレスに対して行われた以前のメモリ・アクセスによるデータが待ち行列に存在することを検出するメカニズムが必要となる。
【０００４】
メモリ・アドレスの衝突を検出するための典型的な方法は、コンテント・アドレッサブル・メモリとも呼ばれる連想メモリを使用する。連想メモリにおいては、各アクセスのアドレスが、データおよび有効性を示す「タグ」ビットと共に記憶される。新しいメモリ・アクセスが実行される場合、新しいメモリ・アクセスのアドレスが、連想メモリに現在保有されているすべての有効エントリのアドレスと連想メモリによって並列的に比較される。これと同じメカニズムは、従来からあるキャッシュ・システムおよび仮想メモリ・システム内部のプロセッサにおいても使用されている。
【０００５】
【発明が解決しようとする課題】
連想メモリは非常によく機能するとはいえ、並列比較を実行するために必要とされるハードウェアは非常に高価である。従って、メモリからデータを読み取る際に発生する可能性のあるキャッシュ衝突を効率的に検出する方法または装置が必要とされる。更に、連想メモリにおいて使用されている高価な並列比較を使用しない衝突検出方法または装置が必要とされる。
【０００６】
【課題を解決するための手段】
本発明は、１つの局面において、メモリからデータを読み取る際に発生する可能性のあるキャッシュ衝突を検出する手段を提供する。別の局面において、本発明は、グラフィック・オブジェクトに関する演算を実行する場合に上記のような衝突を検出する手段を提供する。
【０００７】
上記手段を実現するため、本発明は、例えばコンピュータ・システムのグラフィック表示サブシステム内におけるフレーム・バッファ・メモリとして使用される２次元メモリ・アレイ内での衝突の可能性を検出する衝突検出システムによって達成される。本発明の上記システムにおいて、メモリに対する最も最近のアクセスのアドレスまたはキャッシュ・バッファを消去した後のメモリに対する最初のアクセスのアドレスが保持される。その後、本発明の衝突検出システムは、後続のフレーム・バッファ・メモリ・アクセスの相対的位置のみに関心を持つ。本システムは、以前のフレーム・バッファ・メモリ・アクセスのすべての相対的位置を追跡し、メモリ・アクセスの流れが衝突を発生させる可能性があるような形態で以前のアクセス位置の方向へ戻る場合に潜在的衝突または「キャッシュ・ヒット」フラグをたてる。
【０００８】
これを達成するため、本発明のシステムは、フレーム・バッファ・メモリに対する最新アクセスのアドレスのＸおよびＹ位置と共に、当該メモリ・アクセスのアドレスに対して左右上下または斜め左上、右上、左下あるいは右下の位置で当該メモリ・アクセスより以前にメモリ・アクセスが行われたことがあることを標示する９個の状態ビットを保持する。本システムは、次に、現在時メモリ・アクセスのＸおよびＹ両成分のアドレスを上記最新メモリ・アクセス・アドレスＸおよびＹ成分と比較して、最新メモリ・アクセスに対する現在時メモリ・アクセスの方向を決定する。本システムは、方向を決定した後、この方向を上記９個の状態ビットの１つと比較して、その方向におけるメモリ・アクセスが既にあったことを該状態ビットが標示する場合、システムは潜在的ヒットを識別する。本システムは、各メモリ・アクセスの後、状態ビットが最後にリセットされた時以後のすべてのアクセスのアドレス位置を標示するように９個の状態ビットを更新する。
【０００９】
本発明の１つの局面において、本システムは、メモリを１次元のみを持つものとみなし、現在時アクセスに比較して高低のアクセスを追跡し、フレーム・バッファ・メモリに対するすべての以前のアクセスの相対的位置を保持し、メモリ・アクセスの流れが衝突を発生させる可能性があるような形態で以前のアクセス位置の方向へ戻る場合に、潜在的衝突または「キャッシュ・ヒット」を示すフラグをたてる方法を含む。
【００１０】
【発明の実施の形態】
以下は、本発明を実施する現時点で最良のものと考えられる形態を記述するものである。以下の記述は、本発明の一般的理念を記述するためにのみ行うものであり、本発明をその記述内容に限定する意図を持つものではない。
【００１１】
図１は、本発明を実施するグラフィック・コントローラを含むコンピュータ・システムを示す。コンピュータ・システム１００は、システム・バス１０４を経由してコンピュータ・システム１００の他のエレメントと通信する処理エレメント１０２を含む。キーボード１０６およびグラフィック・ロケータ装置１０８はコンピュータ・システム１００への入力を提供し、一方、グラフィック・コントローラ１０９および表示装置１１０はコンピュータ・システム１００からの出力を提供する。本発明は、グラフィック・コントローラ１０９の範囲内に含まれる。
【００１２】
データ記憶装置１１２が典型的にはコンピュータ・システム１００の範囲内のデータおよびソフトウェアを記憶し、メモリ１１６は、オペレーティング・システム１１８、およびグラフィック・コントローラ１０９のサービスを利用するアプリケーション・プログラム１２０を典型的には含む。
【００１３】
図２は、グラフィック・コントローラ１０９の回路部分を示す。オブジェクト分解回路２０２は、システム・バス１０４からデータおよびコマンドを受け取り、これら複合コマンドをメモリ・コントローラ２１２が実行することができる比較的単純な演算に分解する。これら比較的単純な演算は、フレーム・バッファ・メモリ２１０に対する多数のread-modify-write(読取り−修正−書込み)演算を含む。フレーム・バッファ・メモリ２１０のアクセスにはターンアラウンド・タイムがあるので、１回の読取りおよびそれに続く１回の書込みに要する時間は、２つの連続した読取りまたは２つの連続した書込みの場合よりも長い。
【００１４】
フレーム・バッファ・メモリを修正する際に最高の処理性能を達成するため、メモリ・コントローラ２１２は可能な限り多くの演算を待ち行列化する。メモリ・コントローラ２１２は、次に、連続読取り演算を発してフレーム・バッファ・メモリからデータを読み取って、このデータをキャッシュ２０６に記憶する。次いで、メモリ・コントローラ２１２は、キャッシュ２０６のデータに対する修正を実行し、フレーム・バッファ・メモリ２１０に新しいデータを書き戻す連続書込み演算を実行する。
【００１５】
しかしながら、この高い処理性能を達成するため、メモリ・コントローラ２１２は、フレーム・バッファ２１０から取り出されキャッシュ２０６に記憶されるべきデータのアドレスがキャッシュ２０６内に既に保持されているデータのアドレスと「衝突する」か否かを検出する衝突検出回路２１４を必要とする。この「衝突」は、潜在的衝突が起きる可能性のある時は必ずヒット信号２１６を送信する衝突検出回路２１４によって標示される。すなわち、本発明の衝突検出回路２１４は、衝突が発生したこと、あるいは、衝突が発生する可能性のあることを検出する。
【００１６】
本発明の好ましい実施形態は、２次元フレーム・バッファ・メモリを使用するが、代替的には１次元メモリを使用する。この代替的実施形態においては、図３に示されるように、衝突検出回路２１４は、３個の方向状態ビットおよび１つの最新アクセス・レジスタのみを持つ。最新アクセス・アドレス・レジスタ３０２は、最新のメモリ・アクセスのアドレスを記憶し、中央状態ビット３０６は、最新アクセス・アドレス・レジスタ３０２が有効アドレスを含むか否かを標示する。低位アクセス方向状態ビット３０４は、最新アクセス・アドレス・レジスタ３０２に含まれるアドレスより低位のアドレスを持つアクセスが以前に発生したことがあることを標示し、高位アクセス方向状態ビット３０８は、最新アクセス・アドレス・レジスタ３０２に含まれるアドレスより高位のアドレスを持つアクセスが以前に発生したことがあることを標示する。
【００１７】
この代替実施形態において、コントローラは、最新メモリ・アクセス・アドレス・レジスタに任意の値を記憶しすべての３つの状態ビットをクリアした状態で、処理を開始する。最初のメモリ・アクセスが受け取られると、システムは、状態ビットがすべてクリアされていることを検出し、従って以前の履歴が状態ビット内に存在しないので、メモリ・アクセスの発生を許容する。次に、システムはこのメモリ・アクセスのアドレスを最新アクセス・アドレス・レジスタ３０２に記憶し、また、中央状態ビット３０６をセットして最新アクセス・アドレス・レジスタ３０２が有効値を含むことを標示する。
【００１８】
中央状態ビット３０６がセットされた後、現在時アクセスと呼ばれる別のメモリ・アドレスが受け取られると、システムは、現在時アクセスのアドレスを最新アクセス・アドレス・レジスタ３０２の値と比較する。それらが等しければ、システムはヒットを宣言する。それらが等しくない場合、システムは、現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より低いか高いかを判断する。例えば、現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より高いと仮定すれば、システムは高位アクセス方向状態ビット３０８を検査して、ここでは高位アクセス方向状態ビット３０８はセットされてないので、そのアクセスは許容される。アクセスを許容した後、システムは、現在時アクセスのためのメモリ・アドレスを最新アクセス・アドレス・レジスタ３０２に記憶し、低位アクセス方向状態ビット３０４をセットして、最新アクセス・アドレス・レジスタ３０２に現在含まれる値より低いアドレスを持つアクセスが以前に発生したことを標示する。低位アクセス状態ビットがセットされる理由は、現在時アクセスのアドレスが今や最新アクセス・アドレス・レジスタ３０２に記憶され、それより前すなわち現在時アクセスが発生する前に記憶されていたアドレスが現在時アクセス・アドレスより低かったためである。
【００１９】
次に新しい別のメモリ・アドレスが受け取られると、システムは、この現在時アクセス・アドレスを最新アクセス・アドレス・レジスタ３０２に記憶された値と比較する。それらが等しければ、当然のことながらシステムはヒットを宣言する。等しくなければ、システムは現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より低いか高いかを判断する。ここで例えば現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より高いと仮定すれば、高位アクセス方向状態ビット３０８がセットされてないので、そのアクセスは許容される。しかし、現在時アクセスが最新アクセス・アドレス・レジスタ３０２の値より低いと仮定すれば、(低位アクセス状態ビットがセットされていることによって)最新アクセス・アドレス・レジスタ３０２の値より低いアドレスを持つアクセスが以前に発生していることが標示されているので、ヒットが宣言される。新しいメモリ・アクセスの値が最後アクセス・レジスタ３０２の値より高い限りは、衝突が発生する可能性はないので、アクセスは許容され続ける。アドレスが等しいかまたは低いアクセスを最初に受け取った時、衝突が発生する可能性があるので、ヒットが宣言される。
【００２０】
このシステムは保守的であり、実際に何も存在しない場合にヒットを標示する可能性がある。例えば、第１のアクセスがアドレスＸで発生し、第２のアクセスがＸ＋１で発生したと仮定すれば、次に第３のアクセスがＸ−１で発生すれば、システムは衝突を標示するであろう。なぜならば、アドレスＸ＋１における第２のアクセスがシステムが記憶する最新のアクセス・アドレスであるが、システムは、Ｘ＋１より低位のアドレスに対する少くとも１つのアクセス(実際にはアドレスＸへのアクセス)があったことをも記憶している。従って、アドレスＸ−１が受け取られると、Ｘ−１はＸ＋１より低いので、システムは、ヒットを標示するフラグをたてる。システムはＸ−１がＸより低位にあることすなわち実際にはヒットが発生しないことを判断しない。Ｘ＋１より低位のいかなるアクセスもヒットを派生することをシステムが判断できれば十分である。
【００２１】
本発明の好ましい実施形態の２次元フレーム・バッファに関しては、９個の状態ビットが使用される。図４には、以前のアクセスを標示するために使用される９つの方向状態ビットが示されている。９つの方向状態ビットは、最新アクセス・アドレス・レジスタが有効なＸおよびＹ位置を含むか否かを標示する中央有効性ビット４１０を含む。中央上方向状態ビット４０４は、以前のアクセスが最新アクセス・アドレスより上の位置で発生したこと、すなわち、ボックス４０４内の記号「＝Ｘ」および「＜Ｙ」で示されているように以前のアクセスのＸアドレスは同じでＹアドレスが低位であることを標示する。同様に、中央左方向状態ビット４０８は、以前のアクセスが最新アクセス・アドレスより左の位置で発生したこと、すなわち、ボックス４０８内の記号「＜Ｘ」および「＝Ｙ」で示されているように以前のアクセスのＸアドレスは低位でＹアドレスが同じであることを標示する。中央右方向状態ビット４１２は、以前のアクセスが最新アクセス・アドレスより右の位置で発生したこと、すなわち、ボックス４１２内の記号「＞Ｘ」および「＝Ｙ」で示されているように以前のアクセスのＸアドレスは高位でＹアドレスが同じであることを標示する。中央下方向状態ビット４１６は、以前のアクセスが最新アクセス・アドレスより下の位置で発生したこと、すなわち、ボックス４１６内の記号「＝Ｘ」および「＞Ｙ」で示されているように以前のアクセスのＸアドレスは同じでＹアドレスが高位であることを標示する。
【００２２】
更に他の４つの方向状態ビットは、以前のアクセスが最新アクセスに対して斜め方向で発生したか否かを標示する。左上方向状態ビット４０２は、以前のアクセスが最新アクセス・アドレスに対して左上の位置で発生したこと、すなわち、ボックス４０２内の記号「＜Ｘ」および「＜Ｙ」で示されているように以前のアクセスのＸアドレスは低位でＹアドレスも低位であることを標示する。同様に、右上方向状態ビット４０６は、ボックス４０６内の記号「＞Ｘ」および「＜Ｙ」で示されているように、以前のアクセスが最新アクセス・アドレスに対して右上のアドレスで発生したことを標示する。左下方向状態ビット４１４は、ボックス４１４内の記号「＜Ｘ」および「＞Ｙ」で示されているように、以前のアクセスが最新アクセス・アドレスに対して左下のアドレスで発生したことを標示し、右下方向状態ビット４１８は、ボックス４１８内の記号「＞Ｘ」および「＞Ｙ」で示されているように、以前のアクセスが最新アクセス・アドレスに対して右下のアドレスで発生したことを標示する。
【００２３】
注：本明細書および添付図面において、左、右、上、下、左上、右上、左下、右下および中央の位置を、それぞれ次の( )内の略称として、ＣＬ(Center Left)、ＣＲ(Center Right)、ＡＣ(Above Center)、ＢＣ(Below Center)、ＡＬ(Above Left)、ＡＲ(Above Right)，ＢＬ(Below Left)、ＢＲ(Below Right)およびＣ(Center)という記号で表す場合がある。
【００２４】
以下の例は、図４で示された状態ビットが本発明の衝突検出回路によって使用される様態を示す。この例では、ピクセルを左から右へ上から下へ処理して各ピクセルを変更することによって、１つの長方形がラスタ化または描出される。本処理例の開始時において、以前のアクセス履歴がないことを標示するため、すべての９つの状態ビットがクリアされる。この動作は、システムの起動時またはキャッシュがすべて消去された時のいずれかに行われる。
【００２５】
メモリ・アクセスがオブジェクト分解装置２０２から受け取られる時、中央ビット４１０が有効な以前のアクセス履歴が存在しないことを標示するので、衝突検出システムは比較を行わない。システムは、このメモリ・アクセスのアドレスをＸおよびＹレジスタに記憶し、中央ビット４１０をセットして、最新メモリ・アクセスの履歴が存在することを標示する。
【００２６】
後続のメモリ・アクセスは、長方形の描出の典型的順序に従って、左から右、上から下へ進む。現在時アクセスと呼ばれる別のメモリ・アクセスが受け取られると、このアクセスのアドレスは最新のメモリ・アクセスの右にある、すなわち、Ｘアドレス位置は最新のメモリ・アクセスより大きくＹアドレス位置は最新のメモリ・アクセスと同じである。衝突検出システムがこの現在時アクセス・アドレスを受け取ると、アドレスのＸおよびＹ部分を最新のメモリ・アクセス・アドレスと比較し、Ｘ比較は「より大」をＹ比較は「等しい」を示す。上記の比較の結果、システムは「＞Ｘ」および「＝Ｙ」条件を示す中央右ビット４１２を検査し、中央右位置４１２がセットされていないことを認識する。従って、システムはこのアクセスを許容する。
【００２７】
上記アクセスが実行された後、システムは、(中央)左ビットをセットすることによって図４の状態ビット４０８を更新する。この結果、新たに更新された現在時アクセス・アドレスに対するアクセスより以前に現在時アクセス・アドレスの左側の位置でアクセスが行われたことがあることが標示される。システムは、今受け取ったアドレスをＸおよびＹアドレス・レジスタに記憶し、ＸおよびＹレジスタが有効であることを標示する中央ビット４１０をセットする。このようにして、２つのアクセスの後、システムは、前のアクセスがＸおよびＹアドレス・レジスタに記憶された最新のアクセス・アドレスのどこか左側にあったことを記憶する。メモリ・アクセスが左から右へ移動するにつれ、システムは、上述の通り、先行アクセスが現在位置の左側にすべてあったことを認識する。長方形の最初の行の最新のピクセルが書き込まれた後、(図２の)オブジェクト分解装置２０２は、処理を長方形の次の行の最左端のピクセルへ移動する。
【００２８】
次の行の最初のピクセルに関するメモリ・アドレスが受け取られると、システムはそのアドレスを検査し、当該アクセスが最新のアクセスの左下であると判断する。従って、システムは左下ビット４１４を検査し、このビットがセットされていないことがわかるので、該アクセスは許容される。このアクセスの後、システムは諸ビットを更新し、右上ビットをセットして、今や現在時アクセス・アドレス(具体的には最新のアクセス)の右上で発生したアクセスがあることを示す。前の状態が最新のアクセス・アドレスの左側に対するアクセスが存在したことを示していたので、中央上および左上ビットがそれら領域における可能なアクセス履歴を示すようにセットされる。実際には最新のアクセスの上および左でアクセスは発生していないけれども、最新のアクセスに先行するアクセスの左でアクセスが発生しているので、システムは、上および左のアクセスのすべてを、発生したものとしてフラグを立てなければならない。すなわち、以前の位置の左に何らかのアクセスが発生したが、システムは、どれ程左側に発生したかわからないので、以前の位置の左に位置していたすべてのアクセスが今や最新のアクセスの上および左にあることを示すようにフラグをたてる。しかし、システム方向状態ビットは、現在時メモリ・アクセス・アドレスの行の左側にも右側にもアクセスがなかったこと、また、現在時メモリ・アクセス・アドレスの下側にもアクセスがなかったことを標示する。
【００２９】
今や、ラスタ化処理は長方形の２行目の左から右へ継続し、コントローラは衝突なしのフラグを立て続ける。衝突なしのフラッグをたてるこの処理は長方形の最下部まで続く。
【００３０】
第２の例は、本発明のシステム内でヒットが発生する場合を示すものである。この例は、長方形の輪郭を描画する場合で、左上のコーナーから始まって、長方形の周囲の処理を時計回りに進めるものである。処理の開始時に、コントローラはすべての状態ビットをリセットする。最初のアドレスがＸおよびＹレジスタに記憶され、中央ビットが以前のアクセスがあったことを示すようにセットされる。アクセスが左から右へ進むにつれ、コントローラはアクセスが行の左側にアクセスがあったことを記憶するが、すべての新しいアクセスが最新のアクセスの右側にあるので、コントローラはヒットを示すフラグをたてない。
【００３１】
最上行セグメントが終了すると、オブジェクト分解装置は、最上行の最新のピクセル位置の直下からアクセスを開始する。長方形の右辺におけるアクセスは、それらが最新のアクセスの下にあるので、許容される。コントローラは、アクセスが上にあったこと、および左上方向のどこかにアクセスがあったことを認識する。長方形の右辺の処理を終了すると、オブジェクト分解装置は、長方形の底辺に沿って左へのステッピングを開始する。現在、コントローラはアクセスが同じ行の右側および上方のどこかにあったことを認識している。しかし、長方形の右側で底辺ピクセルの左に対しするアクセスがなかったので、長方形の底辺を規定する底辺ピクセルの左へ移動するアクセスは許容される。
【００３２】
最後に、長方形の底辺の処理を終了すると、オブジェクト分解装置は、長方形の左辺に沿って上昇するアクセスを開始する。長方形の左辺をのぼる最初のピクセルがアクセスされると、システムは、現在の「最新の」アドレスの真上である可能性のあるなんらかの上および左方向アクセスが既に発生していることを認める。
【００３３】
この時点においてキャッシュは消去され、方向状態ビットおよびＸ、Ｙアドレス・レジスタがクリアされる。次に、オブジェクト分解装置は、長方形の左辺をのぼるピクセルをアクセスする。キャッシュの消去後のすべての新しいアクセスは、衝突の可能性のない上方向への一線上の移動であるので、長方形の左辺上の処理の間、ヒットを示すフラグはたたない。
【００３４】
図５は、図２の好ましい実施形態の衝突検出回路部分のブロック図を示す。
フレーム・バッファ・アドレスバス２０４は、(図２の)オブジェクト分解装置２０２から(図２の)フレーム・バッファ２１０へメモリ・コントローラ２１２を経由して送付されるアドレスを受け取る。フレーム・バッファ・アドレスの「Ｘ」部分が、２つの比較器５０６よび５０８に回送され、そこで、アドレスのＸ部分が最新Ｘレジスタ５０２に記憶されている最新Ｘアドレス値と比較される。比較器５０６および５０８の出力は、ＥＱＸ信号５１４およびＬＴＸ信号５１６であり、これらの信号は、ＮＯＲゲートを使用して結合され、ＧＴＸ信号５１６が作成される。これらの３つの信号は、フレーム・バッファ・アドレス・バス２０４上のアドレスのＸ部分が、最新Ｘレジスタ５０２に記憶されている最新のＸアドレス値に等しい(ＥＱＸ)か、それより大(ＧＴＸ)かあるいは小(ＬＴＸ)であるか否かを標示する。
【００３５】
同様に、フレーム・バッファ・アドレスの「Ｙ」部分が、２つの比較器５１０よび５１２に回送され、そこで、アドレスのＹ部分が最新Ｙレジスタ５０４に記憶されている最新Ｙアドレス値と比較される。比較器５１０および５１２の出力は、ＥＱＹ信号５１８およびＬＴＹ信号５２０であり、これらの信号は、ＮＯＲゲートを使用して結合され、ＧＴＹ信号５１９が作成される。これらの３つの信号は、フレーム・バッファ・アドレス・バス２０４上のアドレスのＹ部分が、最新Ｙレジスタ５０４に記憶されている最新のＹアドレス値に等しい(ＥＱＹ)か、それより大(ＧＴＹ)かあるいは小(ＬＴＹ)であるか否かを標示する。
【００３６】
これらの６つの信号ＥＱＸ５１４、ＧＴＸ５１５、ＬＴＸ５１６、ＥＱＹ５１８、ＧＴＹ５１９およびＬＴＹ５２０は、アクセスが許容されるか否かを判断するため図４の状態ビットのいずれを検査しなければならないかを判断するために必要な信号を提供する。図５の残りの回路部分は、到来信号がＸより小さくＹより小さい場合ヒットが発生したか否かを判断するために使用される。
【００３７】
左上ラッチ５２２は、(図４の)左上ビット４０２を記憶する。ＡＮＤゲート５２４は、左上ラッチ５２２内の状態値を、ＬＴＸ信号５１６およびＬＴＹ信号５２０と結合する。フレーム・バッファ・アドレス２０４のＸ部分が、最新のＸ値５０２より小さい場合、ＬＴＸ信号５１６は論理値１である。同様に、フレーム・バッファ・アドレス２０４のＹ部分が、最新のＹ値５０４より小さい場合、ＬＴＹ信号５２０は論理値１である。左上ラッチ５２２が左上方向で既にアクセスが発生したことを標示するようにセットされていれば、上記２つの論理値の組み合わせはヒットを意味する。従って、すべての３つのビットが論理値１であれば、ＡＮＤゲート５２４の出力は論理値１となり、これにより、ＡＮＤゲートの出力である論理値１がその他の比較結果のその他のビットとＯＲゲート５２６によって論理ＯＲされると、この新しいアクセスが許容される前にキャッシュが消去されなければならないことを標示するヒット信号２１６がセットされる。
【００３８】
その他の８つの状態ビットに関する回路は、図４の方向状態ビット定義に従って比較器出力信号ＥＱＸ５１４、ＧＴＸ５１５、ＬＴＸ５１６、ＥＱＹ５１８、ＧＴＹ５１９とＬＴＹ５２０という異なる信号を使用することを当然除いて、上記の左上ラッチ５２２およびＡＮＤゲート５２４と同様である。ＯＲゲート５２６は状態比較のすべての出力を結合して、ヒット信号２１６を生成する。
【００３９】
アクセスが発生する都度、図４に示される９個の状態ビットのすべては更新されなければならない。アクセスが許容されなければ、キャッシュは消去され、すべての状態ビットはクリアされる。アクセスが許容される場合、下記表１に示される式に従って、各タイプのアクセスの発生後９つの状態ビットの各々が更新される。例えば、表１の最初のエントリは、前のアクセスの左上にアクセスが発生した後に９個の状態ビットを更新するための式を示し、第２のエントリは、前のアクセスのすぐ上にアクセスが発生した後に９個の状態ビットを更新するための式を示し、以下のエントリも同様にそれぞれ対応する状態ビットを更新する式を示す。
【００４０】
下記表２は、左上の状態ビットを更新するための式を示す。この式は、表１に示されている左上の状態ビットに対する更新のすべてを論理ＯＲ演算を使用して結合することによって作成されている。その他の８個の状態ビットを更新する式も、同様に、表１に示されているそれぞれの状態ビットに対する更新のすべてを論理ＯＲ演算を使用して結合することによって作成される。表１および表２の式において、記号"＋"は論理ＯＲ演算を示し、記号"・"は論理ＡＮＤ演算を示す。記号"＜＝"は「...によって置き換えられる」を意味する。
【００４１】
【表１】
// 新しいアクセスが左上の場合
AL <= AL
AC <= AL
AR <= AC + AR
CL <= AL
C <= '1'
CR <= AC + AR
BL <= CL + BL
BC <= CL + BL
BR <= C + CR + BC + BR
// 新しいアクセスが真上の場合
AL <= AL
AC <= AC
AR <= AR
CL <= AL
C <= '1'
CR <= AR
BL <= BL + CL
BC <= BC + C
BR <= BR + CR
// 新しいアクセスが右上の場合
AL <= AL + AC
AC <= AR
AR <= AR
CL <= AL + AC
C <= '1'
CR <= AR
BL <= BL + CL + C + BC
BC <= BR + CR
BR <= BR + CR
// 新しいアクセスが真左の場合
AL <= AL
AC <= AL
AR <= AR + AC
CL <= CL
C <= '1'
CR <= CR + C
BL <= BL
BC <= BL
BR <= BR + BC
// 新しいアクセスが最新アクセスと同じ場合
AL <= AL
AC <= AC
AR <= AR
CL <= CL
C <= '1'
CR <= CR
BL <= BL
BC <= BC
BR <= BR
// 新しいアクセスが真右の場合
AL <= AL + AC
AC <= AR
AR <= AR
CL <= CL + C
C <= '1'
CR <= CR
BL <= BL + BC
BC <= BR
BR <= BR
// 新しいアクセスが左下の場合
AL <= AL + CL
AC <= AL + CL
AR <= AL + AR + C + CR
CL <= BL
C <= '1'
CR <= BC + BR
BL <= BL
BC <= BL
BR <= BC + BR
// 新しいアクセスが真下の場合
AL <= AL + CL
AC <= AC + C
AR <= AR + CR
CL <= BL
C <= '1'
CR <= BR
BL <= BL
BC <= BC
BR <= BR
// 新しいアクセスが右下の場合
AL <= AL + AC + CL + C
AC <= AR + CR
AR <= AR + CR
CL <= BL + BC
C <= '1'
CR <= BR
BL <= BL + BC
BC <= BR
BR <= BR
【００４２】
【表２】
AL <= LTX・LTY・AL
+ EQX・LTY・AL
+ GTX・LTY・(AL + AC)
+ LTX・EQY・AL
+ EQX・EQY・AL
+ GTX・EQY・(AL + AC)
+ LTX・GTY・(AL + CL)
+ EQX・GTY・(AL + CL)
+ GTX・GTY・(AL + AC + CL + C)
【００４３】
図６は、左上の状態ビットをセットする表２の式の論理の流れを示す。その他の８個の状態ビットに関して表１の式を結合することによって同様の論理を作成することが可能である点は当業者に認められることであろう。また、ブール代数定理を使用することによって、表２の論理式を縮小して、図６に示される論理よりも小さい論理セットを提供することが可能である点も当業者に認められることであろう。
【００４４】
３次元あるいはｎ次元のメモリでの使用のため本発明を拡張することができる点は当業者に認められることであろう。３次元の実施のためには、３次元の各々について２７ビットの記憶域および比較器が必要とされる。ｎ次元の実施のためには、ｎ次元の各々について３nビットの記憶域および比較器が必要とされる。
【００４５】
以上、本発明の好ましい実施形態を記述したが、上記記述は本発明をそのような実施形態に限定する意図を有するものではない。本発明の理念を逸脱することなく本発明の実施形態および構成に種々の変更および修正を加えることが可能である点は当業者に認められることであろう。
【００４６】
本発明には、例として次のような実施様態が含まれる。
（１）メモリに対する複数アクセスの間に発生するアドレス衝突を検出し、衝突が検出される場合ヒット信号を送信する回路であって、受け取った最新アドレスを保持する最新アドレス・レジスタと、以前のメモリ・アクセスが第１の方向で発生したという標識を記憶する第１方向状態ビットと、現在時メモリ・アドレスを上記最新アドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスに対して第１の方向に位置することを標示する比較器回路と、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスに対して第１の方向に位置することを上記比較器回路が標示し、かつ、上記第１方向状態ビットが以前のメモリ・アクセスが上記第１の方向で発生したことを標示する場合、ヒット信号を送信するヒット検出回路と、を備えるアドレス衝突検出回路。
（２）以前のメモリ・アクセスが上記第１の方向とは反対の第２の方向で発生したという標識を記憶する第２方向状態ビットと、現在時メモリ・アドレスを上記最新アドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスに対して第２の方向に位置することを標示する第２比較器回路と、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスに対して第２の方向に位置することを上記第２比較器回路が標示しかつ上記第２方向状態ビットが以前のメモリ・アクセスが上記第２の方向で発生したことを標示する時第２ヒット信号を送信する第２ヒット検出回路と、を更に備える上記（１）に記載のアドレス衝突検出回路。
（３）上記最新アドレス・レジスタ、上記第１方向状態ビットおよび上記第２方向状態ビットにおける状態情報の存在を標示する中央状態ビットを更に備える上記（２）に記載のアドレス衝突検出回路。
（４）現在時メモリ・アドレスを上記最新アドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスと等しいことを標示する第３比較器回路と、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新アドレス・レジスタに記憶されている最新アドレスと等しいことを上記第３比較器回路が標示する時第３ヒット信号を送信する第３ヒット検出回路と、を更に備える上記（３）に記載のアドレス衝突検出回路。
【００４７】
（５）第１の次元としてＸアドレスを持ち第２の次元としてＹアドレスを持つ２次元アレイとして構成されるメモリにおける複数メモリ・アクセス間のアドレス衝突を検出し、衝突が検出される場合ヒット信号を送信する回路であって、受け取った最新アドレスを記憶する最新Ｘアドレス・レジスタと、受け取った最新アドレスを記憶する最新Ｙアドレス・レジスタと、以前のメモリ・アクセスが上、下、左または右方向で発生したという標識を記憶する４個の方向状態ビットと、現在時メモリ・アドレスを上記最新Ｘアドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスに対して左または右の方向に位置することを標示するＸ比較器回路と、現在時メモリ・アドレスを上記最新Ｙアドレス・レジスタに記憶されている最新アドレスと比較し、上記現在時メモリ・アドレスが上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対して上または下の方向に位置することを標示するＹ比較器回路と、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対して上、下、左または右の方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示し、上記ＸおよびＹ比較器回路によって標示される方向に対応する上記４個の方向状態ビットの１つが以前のメモリ・アクセスが上記対応する方向で発生したことを標示する時ヒット信号を送信するヒット検出回路と、を備えるアドレス衝突検出回路。
（６）上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタにおける状態情報の存在を標示する中央状態ビットを更に備える上記（５）に記載のアドレス衝突検出回路。
【００４８】
（７）現在時メモリ・アドレスが上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し下方向に位置することを上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが上方向で発生したことを標示するように上記４個の方向状態ビットの１つをセットする上状態更新回路と、現在時メモリ・アドレスが上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し上方向に位置することを上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが下方向で発生したことを標示するように上記４個の方向状態ビットの１つをセットする下状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスに対し右方向に位置することを上記Ｘ比較器回路が標示する時、以前のメモリ・アクセスが左方向で発生したことを標示するように上記４個の方向状態ビットの１つをセットする左状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスに対し左方向に位置することを上記Ｘ比較器回路が標示する時、以前のメモリ・アクセスが右方向で発生したことを標示するように上記４個の方向状態ビットの１つをセットする右状態更新回路と、を更に備える上記（５）に記載のアドレス衝突検出回路。
（８）以前のメモリ・アクセスが左上、左下、右上または右下の方向で発生したという標識を記憶する第２の４個の方向状態ビットと、衝突を検出する機能を持ち、上記現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタに記憶されている最新アドレスおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対して左上、左下、右上または右下の方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示し、上記ＸおよびＹ比較器回路によって標示される方向に対応する上記第２の４個の方向状態ビットの１つが以前のメモリ・アクセスが上記対応する方向で発生したことを標示する時ヒット信号を送信する第２ヒット検出回路と、を更に備える上記（５）に記載のアドレス衝突検出回路。
【００４９】
（９）現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し右下方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが左上方向で発生したことを標示するように上記第２の４個の方向状態ビットの１つをセットする左上状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し左上方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが右下方向で発生したことを標示するように上記第２の４個の方向状態ビットの１つをセットする右下状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し右上方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが左下方向で発生したことを標示するように上記第２の４個の方向状態ビットの１つをセットする左下状態更新回路と、現在時メモリ・アドレスが上記最新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジスタに記憶されている最新アドレスに対し左下方向に位置することを上記Ｘ比較器回路および上記Ｙ比較器回路が標示する時、以前のメモリ・アクセスが右上方向で発生したことを標示するように上記第２の４個の方向状態ビットの１つをセットする右上状態更新回路と、を更に備える上記（８）に記載のアドレス衝突検出回路。
【００５０】
【発明の効果】
本発明によって、連想メモリにおいて使用されている高価な並列比較を使用せずに、メモリからデータを読み取る際に発生する可能性のあるキャッシュ衝突を効率的に検出する方法および装置を実現することができる。
【図面の簡単な説明】
【図１】本発明を実施するグラフィック・コントローラを含むコンピュータ・システムのブロック図である。
【図２】図１のグラフィック・コントローラのブロック図である。
【図３】本発明の代替実施形態において使用される３個の状態ビットおよび１つのアドレス・レジスタを示すブロック図である。
【図４】本発明の好ましい実施形態において、以前のアクセスを示すために使用される９個の状態ビットを示すブロック図である。
【図５】本発明の好ましい実施形態である図２の衝突検出回路部分示すブロック図である。
【図６】本発明の好ましい実施形態である図２の衝突検出回路部分の論理ブロック図である。
【符号の説明】
１００ コンピュータ・システム
１０２ 処理エレメント
１０４ システム・バス
１０６ キーボード
１０８ グラフィック・ロケータ装置
１０９ グラフィック・コントローラ
１１０ 表示装置
１１２ データ記憶装置
１１６ メモリ
１１８ オペレーティング・システム
１２０ アプリケーション・プログラム
２０２ オブジェクト分解回路
２０４ フレーム・バッファ・アドレス・バス
２０６ キャッシュ・メモリ
２１０ フレーム・バッファ
２１２ メモリ・コントローラ
２１４ 衝突検出回路
２１６ ヒット信号
３０２ 最新アクセス・アドレス・レジスタ
３０４ 低位アクセス状態ビット
３０６、４１０ 中央状態ビット
３０４ 高位アクセス状態ビット
４０２ 左上アクセス状態ビット
４０４ 上アクセス状態ビット
４０６ 右上アクセス状態ビット
４０８ 左アクセス状態ビット
４１２ 右アクセス状態ビット
４１４ 左下アクセス状態ビット
４１６ 下アクセス状態ビット
４１８ 右下アクセス状態ビット
５０２ 最新Ｘアドレス・レジスタ
５０４ 最新Ｙアドレス・レジスタ
５０６、５１０ Ｘアドレス比較器
５０８、５１２ Ｙアドレス比較器
５２２ 左上ラッチ器
５２４ ＡＮＤゲート
５２６ ＯＲゲート
Claims (11)
- メモリに対する複数アクセスの間に発生するアドレス衝突を検出し、衝突が検出される場合ヒット信号を送信する回路であって、
受け取った最新アドレスを保持する最新アドレス・レジスタと、
以前のメモリ・アクセスが第１の方向で発生したという標識を記憶する第１方向状態ビットと、
現在時メモリ・アドレスを前記最新アドレス・レジスタに記憶されている最新アドレスと比較し、前記現在時メモリ・アドレスが前記最新アドレス・レジスタに記憶されている最新アドレスに対して第１の方向に位置することを示す比較器回路と、
前記現在時メモリ・アドレスが前記最新アドレス・レジスタに記憶されている最新アドレスに対して第１の方向に位置することを前記比較器回路が示し、かつ、前記第１方向状態ビットが以前のメモリ・アクセスが前記第１の方向で発生したことを示す場合、衝突を検出してヒット信号を送信するヒット検出回路と、
を備えるアドレス衝突検出回路。 - 以前のメモリ・アクセスが前記第１の方向とは反対の第２の方向で発生したという標識を記憶する第２方向状態ビットと、
現在時メモリ・アドレスを前記最新アドレス・レジスタに記憶されている最新アドレスと比較し、前記現在時メモリ・アドレスが前記最新アドレス・レジスタに記憶されている最新アドレスに対して第２の方向に位置することを示す第２比較器回路と、
前記現在時メモリ・アドレスが前記最新アドレス・レジスタに記憶されている最新アドレスに対して第２の方向に位置することを前記第２比較器回路が示し、かつ前記第２方向状態ビットが以前のメモリ・アクセスが前記第２の方向で発生したことを示す時、衝突を検出して第２ヒット信号を送信する第２ヒット検出回路と、
を更に備える請求項１に記載のアドレス衝突検出回路。 - 前記ヒット信号と前記第２ヒット信号を結合ヒット信号にまとめる論理ＯＲ回路をさらに備える請求項２に記載のアドレス衝突検出回路。
- 前記現在時メモリ・アドレスが前記最新アドレス・レジスタに記憶されている前記最新アドレスから前記第２の方向に位置することを前記比較器回路が示す時、前記第１方向状態ビットをセットし、前記現在時メモリ・アドレスが前記最新アドレス・レジスタに記憶されている前記最新アドレスから前記第１の方向に位置することを前記比較器回路が示す時、前記第２方向状態ビットをセットする、状態更新回路をさらに備える請求項２に記載のアドレス衝突検出回路。
- 前記最新アドレス・レジスタ、前記第１方向状態ビットおよび前記第２方向状態ビットにおける状態情報の存在を示す中央状態ビットを更に備える請求項２に記載のアドレス衝突検出回路。
- 現在時メモリ・アドレスを前記最新アドレス・レジスタに記憶されている最新アドレスと比較し、前記現在時メモリ・アドレスが前記最新アドレス・レジスタに記憶されている最新アドレスと等しいことを示す第３比較器回路と、
前記現在時メモリ・アドレスが前記最新アドレス・レジスタに記憶されている最新アドレスと等しいことを前記第３比較器回路が示す時、衝突を検出して第３ヒット信号を送信する第３ヒット検出回路と、
を更に備える請求項５に記載のアドレス衝突検出回路。 - メモリに対する複数アクセスの間に発生するアドレス衝突を検出し、衝突が検出される場合ヒット信号を送信する方法であって、
（ａ）受け取った最新アドレスを保持するステップと、
（ｂ）以前のメモリ・アクセスが第１の方向で発生したことを示す第１方向標識を記憶するステップと、
（ｃ）受け取った現在時アドレスを前記受け取った最新アドレスと比較し、前記受け取った現在時アドレスが前記受け取った最新アドレスに対して第１の方向に位置することを示すステップと、
（ｄ）前記受け取った現在時アドレスが前記受け取った最新アドレスに対して第１の方向に位置することを前記ステップ（ｃ）が示し、かつ、前記第１方向標識が以前のメモリ・アクセスが前記第１の方向で発生したことを示す場合、衝突を検出してヒット信号を送信するステップと、
を備える方法。 - （ｅ）以前のメモリ・アクセスが前記第１の方向とは反対の第２の方向で発生したという第２の標識を記憶するステップと、
（ｆ）前記受け取った現在時アドレスを前記受け取った最新アドレスと比較し、前記受け取った現在時アドレスが前記受け取った最新アドレスから前記第２の方向に位置することを示すステップと、
（ｇ）前記受け取った現在時アドレスが前記受け取った最新アドレスから第２の方向に位置することを前記ステップ（ｆ）が示し、かつ前記第２方向標識が以前のメモリ・アクセスが前記第２の方向で発生したことを示す場合、衝突を検出して第２ヒット信号を送信するステップと、
を更に備える請求項７に記載の方法。 - （ｈ）前記ヒット信号と前記第２ヒット信号を結合ヒット信号にまとめるステップをさらに備える請求項８に記載の方法。
- （ｈ）前記受け取った現在時アドレスが前記受け取った最新アドレスから前記第２の方向に位置することを前記比較するステップが示す時、前記第１方向標識をセットするステップと、
（ｉ）前記受け取った現在時アドレスが前記受け取った最新アドレスから前記第１の方向に位置することを前記比較するステップが示す時、前記第２方向標識をセットするステップと、
をさらに備える請求項８に記載の方法。 - （ｅ）前記受け取った最新アドレスが保持されたことを示す中央標識を保存するステップを更に備える請求項７に記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/655,054 US5777628A (en) | 1996-05-29 | 1996-05-29 | Method and apparatus for detecting cache collisions in a two dimensional memory |
| US655,054 | 1996-05-29 |
Publications (3)
| Publication Number | Publication Date |
|---|---|
| JPH1083346A JPH1083346A (ja) | 1998-03-31 |
| JPH1083346A5 JPH1083346A5 (ja) | 2005-03-17 |
| JP3776202B2 true JP3776202B2 (ja) | 2006-05-17 |
Family
ID=24627312
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11673297A Expired - Fee Related JP3776202B2 (ja) | 1996-05-29 | 1997-05-07 | アドレス衝突検出回路 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5777628A (ja) |
| JP (1) | JP3776202B2 (ja) |
Families Citing this family (27)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6577776B1 (en) * | 1999-02-24 | 2003-06-10 | Media 100, Inc. | Transforming video images |
| ATE346342T1 (de) * | 2002-11-05 | 2006-12-15 | Koninkl Philips Electronics Nv | Datenverarbeitungsvorrichtung mit adressenumlenkung als reaktion auf periodische adressenmuster |
| GB2415060B (en) * | 2004-04-16 | 2007-02-14 | Imagination Tech Ltd | Dynamic load balancing |
| US8743142B1 (en) | 2004-05-14 | 2014-06-03 | Nvidia Corporation | Unified data fetch graphics processing system and method |
| US8687010B1 (en) | 2004-05-14 | 2014-04-01 | Nvidia Corporation | Arbitrary size texture palettes for use in graphics systems |
| US8860722B2 (en) * | 2004-05-14 | 2014-10-14 | Nvidia Corporation | Early Z scoreboard tracking system and method |
| US8736628B1 (en) | 2004-05-14 | 2014-05-27 | Nvidia Corporation | Single thread graphics processing system and method |
| US7079156B1 (en) * | 2004-05-14 | 2006-07-18 | Nvidia Corporation | Method and system for implementing multiple high precision and low precision interpolators for a graphics pipeline |
| US8432394B1 (en) | 2004-05-14 | 2013-04-30 | Nvidia Corporation | Method and system for implementing clamped z value interpolation in a raster stage of a graphics pipeline |
| US8711155B2 (en) * | 2004-05-14 | 2014-04-29 | Nvidia Corporation | Early kill removal graphics processing system and method |
| US8736620B2 (en) * | 2004-05-14 | 2014-05-27 | Nvidia Corporation | Kill bit graphics processing system and method |
| US8416242B1 (en) | 2004-05-14 | 2013-04-09 | Nvidia Corporation | Method and system for interpolating level-of-detail in graphics processors |
| US8411105B1 (en) | 2004-05-14 | 2013-04-02 | Nvidia Corporation | Method and system for computing pixel parameters |
| US20060007234A1 (en) * | 2004-05-14 | 2006-01-12 | Hutchins Edward A | Coincident graphics pixel scoreboard tracking system and method |
| US7847755B1 (en) * | 2005-05-23 | 2010-12-07 | Glance Networks | Method and apparatus for the identification and selective encoding of changed host display information |
| US8537168B1 (en) | 2006-11-02 | 2013-09-17 | Nvidia Corporation | Method and system for deferred coverage mask generation in a raster stage |
| US8441497B1 (en) | 2007-08-07 | 2013-05-14 | Nvidia Corporation | Interpolation of vertex attributes in a graphics processor |
| US9183607B1 (en) | 2007-08-15 | 2015-11-10 | Nvidia Corporation | Scoreboard cache coherence in a graphics pipeline |
| US9256514B2 (en) | 2009-02-19 | 2016-02-09 | Nvidia Corporation | Debugging and perfomance analysis of applications |
| US9411595B2 (en) | 2012-05-31 | 2016-08-09 | Nvidia Corporation | Multi-threaded transactional memory coherence |
| US9824009B2 (en) | 2012-12-21 | 2017-11-21 | Nvidia Corporation | Information coherency maintenance systems and methods |
| US10102142B2 (en) | 2012-12-26 | 2018-10-16 | Nvidia Corporation | Virtual address based memory reordering |
| US9323534B2 (en) | 2013-03-15 | 2016-04-26 | Freescale Semiconductor, Inc. | Method and apparatus for detecting a collision between multiple threads of execution for accessing a memory array |
| US9367437B2 (en) | 2013-03-15 | 2016-06-14 | Freescale Semiconductor, Inc. | Method and apparatus for reducing the number of speculative accesses to a memory array |
| US9477575B2 (en) | 2013-06-12 | 2016-10-25 | Nvidia Corporation | Method and system for implementing a multi-threaded API stream replay |
| US9116799B2 (en) | 2013-06-30 | 2015-08-25 | Freescale Semiconductor, Inc. | Method for detecting bank collision at a memory and device therefor |
| US9569385B2 (en) | 2013-09-09 | 2017-02-14 | Nvidia Corporation | Memory transaction ordering |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB8700092D0 (en) * | 1987-01-05 | 1987-02-11 | Crosfield Electronics Ltd | Image processing |
| US5287446A (en) * | 1990-10-15 | 1994-02-15 | Sierra On-Line, Inc. | System and methods for intelligent movement on computer displays |
| US5513307A (en) * | 1992-11-20 | 1996-04-30 | Sega Of America, Inc. | Video game with switchable collision graphics |
-
1996
- 1996-05-29 US US08/655,054 patent/US5777628A/en not_active Expired - Lifetime
-
1997
- 1997-05-07 JP JP11673297A patent/JP3776202B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH1083346A (ja) | 1998-03-31 |
| US5777628A (en) | 1998-07-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5777628A (en) | Method and apparatus for detecting cache collisions in a two dimensional memory | |
| EP0168121B1 (en) | Memory access method and apparatus in multiple processor systems | |
| US5133058A (en) | Page-tagging translation look-aside buffer for a computer memory system | |
| EP0052370A2 (en) | A virtual storage data processing system | |
| JPH06342403A (ja) | 予測キャッシングシステム | |
| JP3012541B2 (ja) | ３次元グラフィックス空間におけるオブジェクト識別および衝突検知のための方法および装置 | |
| US6931495B2 (en) | Processor and method of arithmetic processing thereof | |
| JP2575598B2 (ja) | マルチプロセッサ・コンピュータ・システムのシステム・メモリの並行性を増大する方法およびシステム | |
| US5226132A (en) | Multiple virtual addressing using/comparing translation pairs of addresses comprising a space address and an origin address (sto) while using space registers as storage devices for a data processing system | |
| US5293622A (en) | Computer system with input/output cache | |
| US5619673A (en) | Virtual access cache protection bits handling method and apparatus | |
| US6356988B1 (en) | Memory access system, address converter, and address conversion method capable of reducing a memory access time | |
| EP0153109A2 (en) | Cache coherence system | |
| US7333106B1 (en) | Method and apparatus for Z-buffer operations | |
| JP3060988B2 (ja) | 画像データ処理装置 | |
| JPS629945B2 (ja) | ||
| JPH0697393B2 (ja) | ビットマップ処理装置 | |
| JP2540959B2 (ja) | 情報処理装置 | |
| JP2773458B2 (ja) | ベクトル制御装置 | |
| JPH06103477B2 (ja) | 並列キャッシュメモリ | |
| JPH04153753A (ja) | キャッシュメモリ制御方式 | |
| JP2771350B2 (ja) | 画像処理装置 | |
| JPH05289932A (ja) | グラフィックメモリの制御方法および制御装置 | |
| JPH087663B2 (ja) | コンピユータ・システムおよびその記憶装置アクセス方法 | |
| JPH0548498B2 (ja) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040426 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20040426 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20060207 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20060215 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20060222 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100303 Year of fee payment: 4 |
|
| LAPS | Cancellation because of no payment of annual fees |