JPH1083346A - アドレス衝突検出回路 - Google Patents
アドレス衝突検出回路Info
- Publication number
- JPH1083346A JPH1083346A JP9116732A JP11673297A JPH1083346A JP H1083346 A JPH1083346 A JP H1083346A JP 9116732 A JP9116732 A JP 9116732A JP 11673297 A JP11673297 A JP 11673297A JP H1083346 A JPH1083346 A JP H1083346A
- Authority
- JP
- Japan
- Prior art keywords
- address
- access
- latest
- memory
- register
- 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.)
- Granted
Links
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)
Abstract
(57)【要約】
【課題】コンピュータの２次元メモリ・アレイから以前
に取り出されたデータと現在時アクセスの間でのアドレ
ス衝突の可能性を、連想メモリを使用せずに、検出する
システムを提供する。 【解決手段】受け取った最新アドレスを最新アドレス・
レジスタに記憶し、以前のメモリ・アクセスが最新アド
レスに対し上下左右、左上、右上、左下または右下で発
生したことがあるという標識をそれぞれの方向状態ビッ
トに記憶し、現在時メモリ・アドレスの位置が上記最新
アドレス・レジスタに記憶されている最新アドレスに対
し特定の方向にあることを識別し、その方向に対応する
上記方向状態ビットの１つが以前にその方向でアクセス
があったことをを標示する場合、衝突が発生した可能性
のあることを標示する。
に取り出されたデータと現在時アクセスの間でのアドレ
ス衝突の可能性を、連想メモリを使用せずに、検出する
システムを提供する。 【解決手段】受け取った最新アドレスを最新アドレス・
レジスタに記憶し、以前のメモリ・アクセスが最新アド
レスに対し上下左右、左上、右上、左下または右下で発
生したことがあるという標識をそれぞれの方向状態ビッ
トに記憶し、現在時メモリ・アドレスの位置が上記最新
アドレス・レジスタに記憶されている最新アドレスに対
し特定の方向にあることを識別し、その方向に対応する
上記方向状態ビットの１つが以前にその方向でアクセス
があったことをを標示する場合、衝突が発生した可能性
のあることを標示する。
Description
【０００１】
【発明の属する技術分野】本発明はコンピュータ・シス
テムに関するもので、特にコンピュータ・システムにお
けるグラフィック表示装置の画像表示のためグラフィッ
ク・コントローラ内のフレーム・バッファにアクセスす
る場合に発生する可能性のあるキャッシュ衝突を検出す
るグラフィック・コントローラに関するものである。
テムに関するもので、特にコンピュータ・システムにお
けるグラフィック表示装置の画像表示のためグラフィッ
ク・コントローラ内のフレーム・バッファにアクセスす
る場合に発生する可能性のあるキャッシュ衝突を検出す
るグラフィック・コントローラに関するものである。
【０００２】
【従来の技術】グラフィックス・コントローラ・カード
の複雑性はますます増加し、単一のコマンドから複合的
演算を実行するケースが増加して来ている。このような
複合演算は、指定された規則に従って、表示装置にデー
タを表示するために使用されるフレーム・バッファ・メ
モリの現在の内容を変更することをしばしば必要とす
る。これらの複合演算は、その性質上、フレーム・バッ
ファ・メモリに対する複数のアクセス、特にフレーム・
バッファ・メモリの範囲内の同一位置に対する複数のア
クセがそれらが元々指定されたものと同じ順序で実行さ
れるべきことを必要とする。フレーム・バッファ・メモ
リのアクセスにはターンアラウンド・タイムがあるの
で、１回の読取りおよびそれに続く１回の書込みに要す
る時間は、２つの連続した読取りまたは２つの連続した
書込みの場合よりも長い。従って、フレーム・バッファ
・メモリを修正する際に最高の処理性能を達成するた
め、多くの場合、コントローラは可能な限り多くの演算
を待ち行列化し、次に、フレーム・バッファ・メモリか
らデータを読み取る連続読取り演算を発し、読み取った
データに関する修正を実行し、次にフレーム・バッファ
・メモリに新しいデータを書き戻す連続書込み演算を発
する。
の複雑性はますます増加し、単一のコマンドから複合的
演算を実行するケースが増加して来ている。このような
複合演算は、指定された規則に従って、表示装置にデー
タを表示するために使用されるフレーム・バッファ・メ
モリの現在の内容を変更することをしばしば必要とす
る。これらの複合演算は、その性質上、フレーム・バッ
ファ・メモリに対する複数のアクセス、特にフレーム・
バッファ・メモリの範囲内の同一位置に対する複数のア
クセがそれらが元々指定されたものと同じ順序で実行さ
れるべきことを必要とする。フレーム・バッファ・メモ
リのアクセスにはターンアラウンド・タイムがあるの
で、１回の読取りおよびそれに続く１回の書込みに要す
る時間は、２つの連続した読取りまたは２つの連続した
書込みの場合よりも長い。従って、フレーム・バッファ
・メモリを修正する際に最高の処理性能を達成するた
め、多くの場合、コントローラは可能な限り多くの演算
を待ち行列化し、次に、フレーム・バッファ・メモリか
らデータを読み取る連続読取り演算を発し、読み取った
データに関する修正を実行し、次にフレーム・バッファ
・メモリに新しいデータを書き戻す連続書込み演算を発
する。
【０００３】より迅速な処理性能に対する要求と複合演
算の要件を合致させるため、コントローラーは、ある所
与のメモリ・アクセスが以前のアクセスと「衝突する」
か否かを検出する機能を有していなければならない。す
なわち、現在次アクセスと同じメモリ・アドレスに関し
て、以前のアクセスによって取得されたデータが既に待
ち行列に保持されているか否かを検出することができな
ければならない。そのような衝突が検出されれば、コン
トローラは、新しいメモリ・アクセスを実行する前にそ
の待ち行列を消去するか、あるいは、以前のアクセスに
よるデータに関してなされる修正結果を新しいアクセス
が使用することができるようになにがしかのタグを付け
なければならない。これらの操作のいずれを実行するに
しても、衝突、すなわち、現在時アクセスと同じメモリ
・アドレスに対して行われた以前のメモリ・アクセスに
よるデータが待ち行列に存在することを検出するメカニ
ズムが必要となる。
算の要件を合致させるため、コントローラーは、ある所
与のメモリ・アクセスが以前のアクセスと「衝突する」
か否かを検出する機能を有していなければならない。す
なわち、現在次アクセスと同じメモリ・アドレスに関し
て、以前のアクセスによって取得されたデータが既に待
ち行列に保持されているか否かを検出することができな
ければならない。そのような衝突が検出されれば、コン
トローラは、新しいメモリ・アクセスを実行する前にそ
の待ち行列を消去するか、あるいは、以前のアクセスに
よるデータに関してなされる修正結果を新しいアクセス
が使用することができるようになにがしかのタグを付け
なければならない。これらの操作のいずれを実行するに
しても、衝突、すなわち、現在時アクセスと同じメモリ
・アドレスに対して行われた以前のメモリ・アクセスに
よるデータが待ち行列に存在することを検出するメカニ
ズムが必要となる。
【０００４】メモリ・アドレスの衝突を検出するための
典型的な方法は、コンテント・アドレッサブル・メモリ
とも呼ばれる連想メモリを使用する。連想メモリにおい
ては、各アクセスのアドレスが、データおよび有効性を
示す「タグ」ビットと共に記憶される。新しいメモリ・
アクセスが実行される場合、新しいメモリ・アクセスの
アドレスが、連想メモリに現在保有されているすべての
有効エントリのアドレスと連想メモリによって並列的に
比較される。これと同じメカニズムは、従来からあるキ
ャッシュ・システムおよび仮想メモリ・システム内部の
プロセッサにおいても使用されている。
典型的な方法は、コンテント・アドレッサブル・メモリ
とも呼ばれる連想メモリを使用する。連想メモリにおい
ては、各アクセスのアドレスが、データおよび有効性を
示す「タグ」ビットと共に記憶される。新しいメモリ・
アクセスが実行される場合、新しいメモリ・アクセスの
アドレスが、連想メモリに現在保有されているすべての
有効エントリのアドレスと連想メモリによって並列的に
比較される。これと同じメカニズムは、従来からあるキ
ャッシュ・システムおよび仮想メモリ・システム内部の
プロセッサにおいても使用されている。
【０００５】
【発明が解決しようとする課題】連想メモリは非常によ
く機能するとはいえ、並列比較を実行するために必要と
されるハードウェアは非常に高価である。従って、メモ
リからデータを読み取る際に発生する可能性のあるキャ
ッシュ衝突を効率的に検出する方法または装置が必要と
される。更に、連想メモリにおいて使用されている高価
な並列比較を使用しない衝突検出方法または装置が必要
とされる。
く機能するとはいえ、並列比較を実行するために必要と
されるハードウェアは非常に高価である。従って、メモ
リからデータを読み取る際に発生する可能性のあるキャ
ッシュ衝突を効率的に検出する方法または装置が必要と
される。更に、連想メモリにおいて使用されている高価
な並列比較を使用しない衝突検出方法または装置が必要
とされる。
【０００６】
【課題を解決するための手段】本発明は、１つの局面に
おいて、メモリからデータを読み取る際に発生する可能
性のあるキャッシュ衝突を検出する手段を提供する。別
の局面において、本発明は、グラフィック・オブジェク
トに関する演算を実行する場合に上記のような衝突を検
出する手段を提供する。
おいて、メモリからデータを読み取る際に発生する可能
性のあるキャッシュ衝突を検出する手段を提供する。別
の局面において、本発明は、グラフィック・オブジェク
トに関する演算を実行する場合に上記のような衝突を検
出する手段を提供する。
【０００７】上記手段を実現するため、本発明は、例え
ばコンピュータ・システムのグラフィック表示サブシス
テム内におけるフレーム・バッファ・メモリとして使用
される２次元メモリ・アレイ内での衝突の可能性を検出
する衝突検出システムによって達成される。本発明の上
記システムにおいて、メモリに対する最も最近のアクセ
スのアドレスまたはキャッシュ・バッファを消去した後
のメモリに対する最初のアクセスのアドレスが保持され
る。その後、本発明の衝突検出システムは、後続のフレ
ーム・バッファ・メモリ・アクセスの相対的位置のみに
関心を持つ。本システムは、以前のフレーム・バッファ
・メモリ・アクセスのすべての相対的位置を追跡し、メ
モリ・アクセスの流れが衝突を発生させる可能性がある
ような形態で以前のアクセス位置の方向へ戻る場合に潜
在的衝突または「キャッシュ・ヒット」フラグをたて
る。
ばコンピュータ・システムのグラフィック表示サブシス
テム内におけるフレーム・バッファ・メモリとして使用
される２次元メモリ・アレイ内での衝突の可能性を検出
する衝突検出システムによって達成される。本発明の上
記システムにおいて、メモリに対する最も最近のアクセ
スのアドレスまたはキャッシュ・バッファを消去した後
のメモリに対する最初のアクセスのアドレスが保持され
る。その後、本発明の衝突検出システムは、後続のフレ
ーム・バッファ・メモリ・アクセスの相対的位置のみに
関心を持つ。本システムは、以前のフレーム・バッファ
・メモリ・アクセスのすべての相対的位置を追跡し、メ
モリ・アクセスの流れが衝突を発生させる可能性がある
ような形態で以前のアクセス位置の方向へ戻る場合に潜
在的衝突または「キャッシュ・ヒット」フラグをたて
る。
【０００８】これを達成するため、本発明のシステム
は、フレーム・バッファ・メモリに対する最新アクセス
のアドレスのＸおよびＹ位置と共に、当該メモリ・アク
セスのアドレスに対して左右上下または斜め左上、右
上、左下あるいは右下の位置で当該メモリ・アクセスよ
り以前にメモリ・アクセスが行われたことがあることを
標示する９個の状態ビットを保持する。本システムは、
次に、現在時メモリ・アクセスのＸおよびＹ両成分のア
ドレスを上記最新メモリ・アクセス・アドレスＸおよび
Ｙ成分と比較して、最新メモリ・アクセスに対する現在
時メモリ・アクセスの方向を決定する。本システムは、
方向を決定した後、この方向を上記９個の状態ビットの
１つと比較して、その方向におけるメモリ・アクセスが
既にあったことを該状態ビットが標示する場合、システ
ムは潜在的ヒットを識別する。本システムは、各メモリ
・アクセスの後、状態ビットが最後にリセットされた時
以後のすべてのアクセスのアドレス位置を標示するよう
に９個の状態ビットを更新する。
は、フレーム・バッファ・メモリに対する最新アクセス
のアドレスのＸおよびＹ位置と共に、当該メモリ・アク
セスのアドレスに対して左右上下または斜め左上、右
上、左下あるいは右下の位置で当該メモリ・アクセスよ
り以前にメモリ・アクセスが行われたことがあることを
標示する９個の状態ビットを保持する。本システムは、
次に、現在時メモリ・アクセスのＸおよびＹ両成分のア
ドレスを上記最新メモリ・アクセス・アドレスＸおよび
Ｙ成分と比較して、最新メモリ・アクセスに対する現在
時メモリ・アクセスの方向を決定する。本システムは、
方向を決定した後、この方向を上記９個の状態ビットの
１つと比較して、その方向におけるメモリ・アクセスが
既にあったことを該状態ビットが標示する場合、システ
ムは潜在的ヒットを識別する。本システムは、各メモリ
・アクセスの後、状態ビットが最後にリセットされた時
以後のすべてのアクセスのアドレス位置を標示するよう
に９個の状態ビットを更新する。
【０００９】本発明の１つの局面において、本システム
は、メモリを１次元のみを持つものとみなし、現在時ア
クセスに比較して高低のアクセスを追跡し、フレーム・
バッファ・メモリに対するすべての以前のアクセスの相
対的位置を保持し、メモリ・アクセスの流れが衝突を発
生させる可能性があるような形態で以前のアクセス位置
の方向へ戻る場合に、潜在的衝突または「キャッシュ・
ヒット」を示すフラグをたてる方法を含む。
は、メモリを１次元のみを持つものとみなし、現在時ア
クセスに比較して高低のアクセスを追跡し、フレーム・
バッファ・メモリに対するすべての以前のアクセスの相
対的位置を保持し、メモリ・アクセスの流れが衝突を発
生させる可能性があるような形態で以前のアクセス位置
の方向へ戻る場合に、潜在的衝突または「キャッシュ・
ヒット」を示すフラグをたてる方法を含む。
【００１０】
【発明の実施の形態】以下は、本発明を実施する現時点
で最良のものと考えられる形態を記述するものである。
以下の記述は、本発明の一般的理念を記述するためにの
み行うものであり、本発明をその記述内容に限定する意
図を持つものではない。
で最良のものと考えられる形態を記述するものである。
以下の記述は、本発明の一般的理念を記述するためにの
み行うものであり、本発明をその記述内容に限定する意
図を持つものではない。
【００１１】図１は、本発明を実施するグラフィック・
コントローラを含むコンピュータ・システムを示す。コ
ンピュータ・システム１００は、システム・バス１０４
を経由してコンピュータ・システム１００の他のエレメ
ントと通信する処理エレメント１０２を含む。キーボー
ド１０６およびグラフィック・ロケータ装置１０８はコ
ンピュータ・システム１００への入力を提供し、一方、
グラフィック・コントローラ１０９および表示装置１１
０はコンピュータ・システム１００からの出力を提供す
る。本発明は、グラフィック・コントローラ１０９の範
囲内に含まれる。
コントローラを含むコンピュータ・システムを示す。コ
ンピュータ・システム１００は、システム・バス１０４
を経由してコンピュータ・システム１００の他のエレメ
ントと通信する処理エレメント１０２を含む。キーボー
ド１０６およびグラフィック・ロケータ装置１０８はコ
ンピュータ・システム１００への入力を提供し、一方、
グラフィック・コントローラ１０９および表示装置１１
０はコンピュータ・システム１００からの出力を提供す
る。本発明は、グラフィック・コントローラ１０９の範
囲内に含まれる。
【００１２】データ記憶装置１１２が典型的にはコンピ
ュータ・システム１００の範囲内のデータおよびソフト
ウェアを記憶し、メモリ１１６は、オペレーティング・
システム１１８、およびグラフィック・コントローラ１
０９のサービスを利用するアプリケーション・プログラ
ム１２０を典型的には含む。
ュータ・システム１００の範囲内のデータおよびソフト
ウェアを記憶し、メモリ１１６は、オペレーティング・
システム１１８、およびグラフィック・コントローラ１
０９のサービスを利用するアプリケーション・プログラ
ム１２０を典型的には含む。
【００１３】図２は、グラフィック・コントローラ１０
９の回路部分を示す。オブジェクト分解回路２０２は、
システム・バス１０４からデータおよびコマンドを受け
取り、これら複合コマンドをメモリ・コントローラ２１
２が実行することができる比較的単純な演算に分解す
る。これら比較的単純な演算は、フレーム・バッファ・
メモリ２１０に対する多数のread-modify-write(読取り
−修正−書込み)演算を含む。フレーム・バッファ・メ
モリ２１０のアクセスにはターンアラウンド・タイムが
あるので、１回の読取りおよびそれに続く１回の書込み
に要する時間は、２つの連続した読取りまたは２つの連
続した書込みの場合よりも長い。
９の回路部分を示す。オブジェクト分解回路２０２は、
システム・バス１０４からデータおよびコマンドを受け
取り、これら複合コマンドをメモリ・コントローラ２１
２が実行することができる比較的単純な演算に分解す
る。これら比較的単純な演算は、フレーム・バッファ・
メモリ２１０に対する多数のread-modify-write(読取り
−修正−書込み)演算を含む。フレーム・バッファ・メ
モリ２１０のアクセスにはターンアラウンド・タイムが
あるので、１回の読取りおよびそれに続く１回の書込み
に要する時間は、２つの連続した読取りまたは２つの連
続した書込みの場合よりも長い。
【００１４】フレーム・バッファ・メモリを修正する際
に最高の処理性能を達成するため、メモリ・コントロー
ラ２１２は可能な限り多くの演算を待ち行列化する。メ
モリ・コントローラ２１２は、次に、連続読取り演算を
発してフレーム・バッファ・メモリからデータを読み取
って、このデータをキャッシュ２０６に記憶する。次い
で、メモリ・コントローラ２１２は、キャッシュ２０６
のデータに対する修正を実行し、フレーム・バッファ・
メモリ２１０に新しいデータを書き戻す連続書込み演算
を実行する。
に最高の処理性能を達成するため、メモリ・コントロー
ラ２１２は可能な限り多くの演算を待ち行列化する。メ
モリ・コントローラ２１２は、次に、連続読取り演算を
発してフレーム・バッファ・メモリからデータを読み取
って、このデータをキャッシュ２０６に記憶する。次い
で、メモリ・コントローラ２１２は、キャッシュ２０６
のデータに対する修正を実行し、フレーム・バッファ・
メモリ２１０に新しいデータを書き戻す連続書込み演算
を実行する。
【００１５】しかしながら、この高い処理性能を達成す
るため、メモリ・コントローラ２１２は、フレーム・バ
ッファ２１０から取り出されキャッシュ２０６に記憶さ
れるべきデータのアドレスがキャッシュ２０６内に既に
保持されているデータのアドレスと「衝突する」か否か
を検出する衝突検出回路２１４を必要とする。この「衝
突」は、潜在的衝突が起きる可能性のある時は必ずヒッ
ト信号２１６を送信する衝突検出回路２１４によって標
示される。すなわち、本発明の衝突検出回路２１４は、
衝突が発生したこと、あるいは、衝突が発生する可能性
のあることを検出する。
るため、メモリ・コントローラ２１２は、フレーム・バ
ッファ２１０から取り出されキャッシュ２０６に記憶さ
れるべきデータのアドレスがキャッシュ２０６内に既に
保持されているデータのアドレスと「衝突する」か否か
を検出する衝突検出回路２１４を必要とする。この「衝
突」は、潜在的衝突が起きる可能性のある時は必ずヒッ
ト信号２１６を送信する衝突検出回路２１４によって標
示される。すなわち、本発明の衝突検出回路２１４は、
衝突が発生したこと、あるいは、衝突が発生する可能性
のあることを検出する。
【００１６】本発明の好ましい実施形態は、２次元フレ
ーム・バッファ・メモリを使用するが、代替的には１次
元メモリを使用する。この代替的実施形態においては、
図３に示されるように、衝突検出回路２１４は、３個の
方向状態ビットおよび１つの最新アクセス・レジスタの
みを持つ。最新アクセス・アドレス・レジスタ３０２
は、最新のメモリ・アクセスのアドレスを記憶し、中央
状態ビット３０６は、最新アクセス・アドレス・レジス
タ３０２が有効アドレスを含むか否かを標示する。低位
アクセス方向状態ビット３０４は、最新アクセス・アド
レス・レジスタ３０２に含まれるアドレスより低位のア
ドレスを持つアクセスが以前に発生したことがあること
を標示し、高位アクセス方向状態ビット３０８は、最新
アクセス・アドレス・レジスタ３０２に含まれるアドレ
スより高位のアドレスを持つアクセスが以前に発生した
ことがあることを標示する。
ーム・バッファ・メモリを使用するが、代替的には１次
元メモリを使用する。この代替的実施形態においては、
図３に示されるように、衝突検出回路２１４は、３個の
方向状態ビットおよび１つの最新アクセス・レジスタの
みを持つ。最新アクセス・アドレス・レジスタ３０２
は、最新のメモリ・アクセスのアドレスを記憶し、中央
状態ビット３０６は、最新アクセス・アドレス・レジス
タ３０２が有効アドレスを含むか否かを標示する。低位
アクセス方向状態ビット３０４は、最新アクセス・アド
レス・レジスタ３０２に含まれるアドレスより低位のア
ドレスを持つアクセスが以前に発生したことがあること
を標示し、高位アクセス方向状態ビット３０８は、最新
アクセス・アドレス・レジスタ３０２に含まれるアドレ
スより高位のアドレスを持つアクセスが以前に発生した
ことがあることを標示する。
【００１７】この代替実施形態において、コントローラ
は、最新メモリ・アクセス・アドレス・レジスタに任意
の値を記憶しすべての３つの状態ビットをクリアした状
態で、処理を開始する。最初のメモリ・アクセスが受け
取られると、システムは、状態ビットがすべてクリアさ
れていることを検出し、従って以前の履歴が状態ビット
内に存在しないので、メモリ・アクセスの発生を許容す
る。次に、システムはこのメモリ・アクセスのアドレス
を最新アクセス・アドレス・レジスタ３０２に記憶し、
また、中央状態ビット３０６をセットして最新アクセス
・アドレス・レジスタ３０２が有効値を含むことを標示
する。
は、最新メモリ・アクセス・アドレス・レジスタに任意
の値を記憶しすべての３つの状態ビットをクリアした状
態で、処理を開始する。最初のメモリ・アクセスが受け
取られると、システムは、状態ビットがすべてクリアさ
れていることを検出し、従って以前の履歴が状態ビット
内に存在しないので、メモリ・アクセスの発生を許容す
る。次に、システムはこのメモリ・アクセスのアドレス
を最新アクセス・アドレス・レジスタ３０２に記憶し、
また、中央状態ビット３０６をセットして最新アクセス
・アドレス・レジスタ３０２が有効値を含むことを標示
する。
【００１８】中央状態ビット３０６がセットされた後、
現在時アクセスと呼ばれる別のメモリ・アドレスが受け
取られると、システムは、現在時アクセスのアドレスを
最新アクセス・アドレス・レジスタ３０２の値と比較す
る。それらが等しければ、システムはヒットを宣言す
る。それらが等しくない場合、システムは、現在時アク
セスが最新アクセス・アドレス・レジスタ３０２の値よ
り低いか高いかを判断する。例えば、現在時アクセスが
最新アクセス・アドレス・レジスタ３０２の値より高い
と仮定すれば、システムは高位アクセス方向状態ビット
３０８を検査して、ここでは高位アクセス方向状態ビッ
ト３０８はセットされてないので、そのアクセスは許容
される。アクセスを許容した後、システムは、現在時ア
クセスのためのメモリ・アドレスを最新アクセス・アド
レス・レジスタ３０２に記憶し、低位アクセス方向状態
ビット３０４をセットして、最新アクセス・アドレス・
レジスタ３０２に現在含まれる値より低いアドレスを持
つアクセスが以前に発生したことを標示する。低位アク
セス状態ビットがセットされる理由は、現在時アクセス
のアドレスが今や最新アクセス・アドレス・レジスタ３
０２に記憶され、それより前すなわち現在時アクセスが
発生する前に記憶されていたアドレスが現在時アクセス
・アドレスより低かったためである。
現在時アクセスと呼ばれる別のメモリ・アドレスが受け
取られると、システムは、現在時アクセスのアドレスを
最新アクセス・アドレス・レジスタ３０２の値と比較す
る。それらが等しければ、システムはヒットを宣言す
る。それらが等しくない場合、システムは、現在時アク
セスが最新アクセス・アドレス・レジスタ３０２の値よ
り低いか高いかを判断する。例えば、現在時アクセスが
最新アクセス・アドレス・レジスタ３０２の値より高い
と仮定すれば、システムは高位アクセス方向状態ビット
３０８を検査して、ここでは高位アクセス方向状態ビッ
ト３０８はセットされてないので、そのアクセスは許容
される。アクセスを許容した後、システムは、現在時ア
クセスのためのメモリ・アドレスを最新アクセス・アド
レス・レジスタ３０２に記憶し、低位アクセス方向状態
ビット３０４をセットして、最新アクセス・アドレス・
レジスタ３０２に現在含まれる値より低いアドレスを持
つアクセスが以前に発生したことを標示する。低位アク
セス状態ビットがセットされる理由は、現在時アクセス
のアドレスが今や最新アクセス・アドレス・レジスタ３
０２に記憶され、それより前すなわち現在時アクセスが
発生する前に記憶されていたアドレスが現在時アクセス
・アドレスより低かったためである。
【００１９】次に新しい別のメモリ・アドレスが受け取
られると、システムは、この現在時アクセス・アドレス
を最新アクセス・アドレス・レジスタ３０２に記憶され
た値と比較する。それらが等しければ、当然のことなが
らシステムはヒットを宣言する。等しくなければ、シス
テムは現在時アクセスが最新アクセス・アドレス・レジ
スタ３０２の値より低いか高いかを判断する。ここで例
えば現在時アクセスが最新アクセス・アドレス・レジス
タ３０２の値より高いと仮定すれば、高位アクセス方向
状態ビット３０８がセットされてないので、そのアクセ
スは許容される。しかし、現在時アクセスが最新アクセ
ス・アドレス・レジスタ３０２の値より低いと仮定すれ
ば、(低位アクセス状態ビットがセットされていること
によって)最新アクセス・アドレス・レジスタ３０２の
値より低いアドレスを持つアクセスが以前に発生してい
ることが標示されているので、ヒットが宣言される。新
しいメモリ・アクセスの値が最後アクセス・レジスタ３
０２の値より高い限りは、衝突が発生する可能性はない
ので、アクセスは許容され続ける。アドレスが等しいか
または低いアクセスを最初に受け取った時、衝突が発生
する可能性があるので、ヒットが宣言される。
られると、システムは、この現在時アクセス・アドレス
を最新アクセス・アドレス・レジスタ３０２に記憶され
た値と比較する。それらが等しければ、当然のことなが
らシステムはヒットを宣言する。等しくなければ、シス
テムは現在時アクセスが最新アクセス・アドレス・レジ
スタ３０２の値より低いか高いかを判断する。ここで例
えば現在時アクセスが最新アクセス・アドレス・レジス
タ３０２の値より高いと仮定すれば、高位アクセス方向
状態ビット３０８がセットされてないので、そのアクセ
スは許容される。しかし、現在時アクセスが最新アクセ
ス・アドレス・レジスタ３０２の値より低いと仮定すれ
ば、(低位アクセス状態ビットがセットされていること
によって)最新アクセス・アドレス・レジスタ３０２の
値より低いアドレスを持つアクセスが以前に発生してい
ることが標示されているので、ヒットが宣言される。新
しいメモリ・アクセスの値が最後アクセス・レジスタ３
０２の値より高い限りは、衝突が発生する可能性はない
ので、アクセスは許容され続ける。アドレスが等しいか
または低いアクセスを最初に受け取った時、衝突が発生
する可能性があるので、ヒットが宣言される。
【００２０】このシステムは保守的であり、実際に何も
存在しない場合にヒットを標示する可能性がある。例え
ば、第１のアクセスがアドレスＸで発生し、第２のアク
セスがＸ＋１で発生したと仮定すれば、次に第３のアク
セスがＸ−１で発生すれば、システムは衝突を標示する
であろう。なぜならば、アドレスＸ＋１における第２の
アクセスがシステムが記憶する最新のアクセス・アドレ
スであるが、システムは、Ｘ＋１より低位のアドレスに
対する少くとも１つのアクセス(実際にはアドレスＸへ
のアクセス)があったことをも記憶している。従って、
アドレスＸ−１が受け取られると、Ｘ−１はＸ＋１より
低いので、システムは、ヒットを標示するフラグをたて
る。システムはＸ−１がＸより低位にあることすなわち
実際にはヒットが発生しないことを判断しない。Ｘ＋１
より低位のいかなるアクセスもヒットを派生することを
システムが判断できれば十分である。
存在しない場合にヒットを標示する可能性がある。例え
ば、第１のアクセスがアドレスＸで発生し、第２のアク
セスがＸ＋１で発生したと仮定すれば、次に第３のアク
セスがＸ−１で発生すれば、システムは衝突を標示する
であろう。なぜならば、アドレスＸ＋１における第２の
アクセスがシステムが記憶する最新のアクセス・アドレ
スであるが、システムは、Ｘ＋１より低位のアドレスに
対する少くとも１つのアクセス(実際にはアドレスＸへ
のアクセス)があったことをも記憶している。従って、
アドレスＸ−１が受け取られると、Ｘ−１はＸ＋１より
低いので、システムは、ヒットを標示するフラグをたて
る。システムはＸ−１がＸより低位にあることすなわち
実際にはヒットが発生しないことを判断しない。Ｘ＋１
より低位のいかなるアクセスもヒットを派生することを
システムが判断できれば十分である。
【００２１】本発明の好ましい実施形態の２次元フレー
ム・バッファに関しては、９個の状態ビットが使用され
る。図４には、以前のアクセスを標示するために使用さ
れる９つの方向状態ビットが示されている。９つの方向
状態ビットは、最新アクセス・アドレス・レジスタが有
効なＸおよびＹ位置を含むか否かを標示する中央有効性
ビット４１０を含む。中央上方向状態ビット４０４は、
以前のアクセスが最新アクセス・アドレスより上の位置
で発生したこと、すなわち、ボックス４０４内の記号
「＝Ｘ」および「＜Ｙ」で示されているように以前のア
クセスのＸアドレスは同じでＹアドレスが低位であるこ
とを標示する。同様に、中央左方向状態ビット４０８
は、以前のアクセスが最新アクセス・アドレスより左の
位置で発生したこと、すなわち、ボックス４０８内の記
号「＜Ｘ」および「＝Ｙ」で示されているように以前の
アクセスのＸアドレスは低位でＹアドレスが同じである
ことを標示する。中央右方向状態ビット４１２は、以前
のアクセスが最新アクセス・アドレスより右の位置で発
生したこと、すなわち、ボックス４１２内の記号「＞
Ｘ」および「＝Ｙ」で示されているように以前のアクセ
スのＸアドレスは高位でＹアドレスが同じであることを
標示する。中央下方向状態ビット４１６は、以前のアク
セスが最新アクセス・アドレスより下の位置で発生した
こと、すなわち、ボックス４１６内の記号「＝Ｘ」およ
び「＞Ｙ」で示されているように以前のアクセスのＸア
ドレスは同じでＹアドレスが高位であることを標示す
る。
ム・バッファに関しては、９個の状態ビットが使用され
る。図４には、以前のアクセスを標示するために使用さ
れる９つの方向状態ビットが示されている。９つの方向
状態ビットは、最新アクセス・アドレス・レジスタが有
効なＸおよびＹ位置を含むか否かを標示する中央有効性
ビット４１０を含む。中央上方向状態ビット４０４は、
以前のアクセスが最新アクセス・アドレスより上の位置
で発生したこと、すなわち、ボックス４０４内の記号
「＝Ｘ」および「＜Ｙ」で示されているように以前のア
クセスのＸアドレスは同じでＹアドレスが低位であるこ
とを標示する。同様に、中央左方向状態ビット４０８
は、以前のアクセスが最新アクセス・アドレスより左の
位置で発生したこと、すなわち、ボックス４０８内の記
号「＜Ｘ」および「＝Ｙ」で示されているように以前の
アクセスのＸアドレスは低位でＹアドレスが同じである
ことを標示する。中央右方向状態ビット４１２は、以前
のアクセスが最新アクセス・アドレスより右の位置で発
生したこと、すなわち、ボックス４１２内の記号「＞
Ｘ」および「＝Ｙ」で示されているように以前のアクセ
スのＸアドレスは高位でＹアドレスが同じであることを
標示する。中央下方向状態ビット４１６は、以前のアク
セスが最新アクセス・アドレスより下の位置で発生した
こと、すなわち、ボックス４１６内の記号「＝Ｘ」およ
び「＞Ｙ」で示されているように以前のアクセスのＸア
ドレスは同じでＹアドレスが高位であることを標示す
る。
【００２２】更に他の４つの方向状態ビットは、以前の
アクセスが最新アクセスに対して斜め方向で発生したか
否かを標示する。左上方向状態ビット４０２は、以前の
アクセスが最新アクセス・アドレスに対して左上の位置
で発生したこと、すなわち、ボックス４０２内の記号
「＜Ｘ」および「＜Ｙ」で示されているように以前のア
クセスのＸアドレスは低位でＹアドレスも低位であるこ
とを標示する。同様に、右上方向状態ビット４０６は、
ボックス４０６内の記号「＞Ｘ」および「＜Ｙ」で示さ
れているように、以前のアクセスが最新アクセス・アド
レスに対して右上のアドレスで発生したことを標示す
る。左下方向状態ビット４１４は、ボックス４１４内の
記号「＜Ｘ」および「＞Ｙ」で示されているように、以
前のアクセスが最新アクセス・アドレスに対して左下の
アドレスで発生したことを標示し、右下方向状態ビット
４１８は、ボックス４１８内の記号「＞Ｘ」および「＞
Ｙ」で示されているように、以前のアクセスが最新アク
セス・アドレスに対して右下のアドレスで発生したこと
を標示する。
アクセスが最新アクセスに対して斜め方向で発生したか
否かを標示する。左上方向状態ビット４０２は、以前の
アクセスが最新アクセス・アドレスに対して左上の位置
で発生したこと、すなわち、ボックス４０２内の記号
「＜Ｘ」および「＜Ｙ」で示されているように以前のア
クセスのＸアドレスは低位でＹアドレスも低位であるこ
とを標示する。同様に、右上方向状態ビット４０６は、
ボックス４０６内の記号「＞Ｘ」および「＜Ｙ」で示さ
れているように、以前のアクセスが最新アクセス・アド
レスに対して右上のアドレスで発生したことを標示す
る。左下方向状態ビット４１４は、ボックス４１４内の
記号「＜Ｘ」および「＞Ｙ」で示されているように、以
前のアクセスが最新アクセス・アドレスに対して左下の
アドレスで発生したことを標示し、右下方向状態ビット
４１８は、ボックス４１８内の記号「＞Ｘ」および「＞
Ｙ」で示されているように、以前のアクセスが最新アク
セス・アドレスに対して右下のアドレスで発生したこと
を標示する。
【００２３】注：本明細書および添付図面において、
左、右、上、下、左上、右上、左下、右下および中央の
位置を、それぞれ次の( )内の略称として、ＣＬ(Center
Left)、ＣＲ(Center Right)、ＡＣ(Above Center)、Ｂ
Ｃ(Below Center)、ＡＬ(AboveLeft)、ＡＲ(Above Righ
t)，ＢＬ(Below Left)、ＢＲ(Below Right)およびＣ(Ce
nter)という記号で表す場合がある。
左、右、上、下、左上、右上、左下、右下および中央の
位置を、それぞれ次の( )内の略称として、ＣＬ(Center
Left)、ＣＲ(Center Right)、ＡＣ(Above Center)、Ｂ
Ｃ(Below Center)、ＡＬ(AboveLeft)、ＡＲ(Above Righ
t)，ＢＬ(Below Left)、ＢＲ(Below Right)およびＣ(Ce
nter)という記号で表す場合がある。
【００２４】以下の例は、図４で示された状態ビットが
本発明の衝突検出回路によって使用される様態を示す。
この例では、ピクセルを左から右へ上から下へ処理して
各ピクセルを変更することによって、１つの長方形がラ
スタ化または描出される。本処理例の開始時において、
以前のアクセス履歴がないことを標示するため、すべて
の９つの状態ビットがクリアされる。この動作は、シス
テムの起動時またはキャッシュがすべて消去された時の
いずれかに行われる。
本発明の衝突検出回路によって使用される様態を示す。
この例では、ピクセルを左から右へ上から下へ処理して
各ピクセルを変更することによって、１つの長方形がラ
スタ化または描出される。本処理例の開始時において、
以前のアクセス履歴がないことを標示するため、すべて
の９つの状態ビットがクリアされる。この動作は、シス
テムの起動時またはキャッシュがすべて消去された時の
いずれかに行われる。
【００２５】メモリ・アクセスがオブジェクト分解装置
２０２から受け取られる時、中央ビット４１０が有効な
以前のアクセス履歴が存在しないことを標示するので、
衝突検出システムは比較を行わない。システムは、この
メモリ・アクセスのアドレスをＸおよびＹレジスタに記
憶し、中央ビット４１０をセットして、最新メモリ・ア
クセスの履歴が存在することを標示する。
２０２から受け取られる時、中央ビット４１０が有効な
以前のアクセス履歴が存在しないことを標示するので、
衝突検出システムは比較を行わない。システムは、この
メモリ・アクセスのアドレスをＸおよびＹレジスタに記
憶し、中央ビット４１０をセットして、最新メモリ・ア
クセスの履歴が存在することを標示する。
【００２６】後続のメモリ・アクセスは、長方形の描出
の典型的順序に従って、左から右、上から下へ進む。現
在時アクセスと呼ばれる別のメモリ・アクセスが受け取
られると、このアクセスのアドレスは最新のメモリ・ア
クセスの右にある、すなわち、Ｘアドレス位置は最新の
メモリ・アクセスより大きくＹアドレス位置は最新のメ
モリ・アクセスと同じである。衝突検出システムがこの
現在時アクセス・アドレスを受け取ると、アドレスのＸ
およびＹ部分を最新のメモリ・アクセス・アドレスと比
較し、Ｘ比較は「より大」をＹ比較は「等しい」を示
す。上記の比較の結果、システムは「＞Ｘ」および「＝
Ｙ」条件を示す中央右ビット４１２を検査し、中央右位
置４１２がセットされていないことを認識する。従っ
て、システムはこのアクセスを許容する。
の典型的順序に従って、左から右、上から下へ進む。現
在時アクセスと呼ばれる別のメモリ・アクセスが受け取
られると、このアクセスのアドレスは最新のメモリ・ア
クセスの右にある、すなわち、Ｘアドレス位置は最新の
メモリ・アクセスより大きくＹアドレス位置は最新のメ
モリ・アクセスと同じである。衝突検出システムがこの
現在時アクセス・アドレスを受け取ると、アドレスのＸ
およびＹ部分を最新のメモリ・アクセス・アドレスと比
較し、Ｘ比較は「より大」をＹ比較は「等しい」を示
す。上記の比較の結果、システムは「＞Ｘ」および「＝
Ｙ」条件を示す中央右ビット４１２を検査し、中央右位
置４１２がセットされていないことを認識する。従っ
て、システムはこのアクセスを許容する。
【００２７】上記アクセスが実行された後、システム
は、(中央)左ビットをセットすることによって図４の状
態ビット４０８を更新する。この結果、新たに更新され
た現在時アクセス・アドレスに対するアクセスより以前
に現在時アクセス・アドレスの左側の位置でアクセスが
行われたことがあることが標示される。システムは、今
受け取ったアドレスをＸおよびＹアドレス・レジスタに
記憶し、ＸおよびＹレジスタが有効であることを標示す
る中央ビット４１０をセットする。このようにして、２
つのアクセスの後、システムは、前のアクセスがＸおよ
びＹアドレス・レジスタに記憶された最新のアクセス・
アドレスのどこか左側にあったことを記憶する。メモリ
・アクセスが左から右へ移動するにつれ、システムは、
上述の通り、先行アクセスが現在位置の左側にすべてあ
ったことを認識する。長方形の最初の行の最新のピクセ
ルが書き込まれた後、(図２の)オブジェクト分解装置２
０２は、処理を長方形の次の行の最左端のピクセルへ移
動する。
は、(中央)左ビットをセットすることによって図４の状
態ビット４０８を更新する。この結果、新たに更新され
た現在時アクセス・アドレスに対するアクセスより以前
に現在時アクセス・アドレスの左側の位置でアクセスが
行われたことがあることが標示される。システムは、今
受け取ったアドレスをＸおよびＹアドレス・レジスタに
記憶し、ＸおよびＹレジスタが有効であることを標示す
る中央ビット４１０をセットする。このようにして、２
つのアクセスの後、システムは、前のアクセスがＸおよ
びＹアドレス・レジスタに記憶された最新のアクセス・
アドレスのどこか左側にあったことを記憶する。メモリ
・アクセスが左から右へ移動するにつれ、システムは、
上述の通り、先行アクセスが現在位置の左側にすべてあ
ったことを認識する。長方形の最初の行の最新のピクセ
ルが書き込まれた後、(図２の)オブジェクト分解装置２
０２は、処理を長方形の次の行の最左端のピクセルへ移
動する。
【００２８】次の行の最初のピクセルに関するメモリ・
アドレスが受け取られると、システムはそのアドレスを
検査し、当該アクセスが最新のアクセスの左下であると
判断する。従って、システムは左下ビット４１４を検査
し、このビットがセットされていないことがわかるの
で、該アクセスは許容される。このアクセスの後、シス
テムは諸ビットを更新し、右上ビットをセットして、今
や現在時アクセス・アドレス(具体的には最新のアクセ
ス)の右上で発生したアクセスがあることを示す。前の
状態が最新のアクセス・アドレスの左側に対するアクセ
スが存在したことを示していたので、中央上および左上
ビットがそれら領域における可能なアクセス履歴を示す
ようにセットされる。実際には最新のアクセスの上およ
び左でアクセスは発生していないけれども、最新のアク
セスに先行するアクセスの左でアクセスが発生している
ので、システムは、上および左のアクセスのすべてを、
発生したものとしてフラグを立てなければならない。す
なわち、以前の位置の左に何らかのアクセスが発生した
が、システムは、どれ程左側に発生したかわからないの
で、以前の位置の左に位置していたすべてのアクセスが
今や最新のアクセスの上および左にあることを示すよう
にフラグをたてる。しかし、システム方向状態ビット
は、現在時メモリ・アクセス・アドレスの行の左側にも
右側にもアクセスがなかったこと、また、現在時メモリ
・アクセス・アドレスの下側にもアクセスがなかったこ
とを標示する。
アドレスが受け取られると、システムはそのアドレスを
検査し、当該アクセスが最新のアクセスの左下であると
判断する。従って、システムは左下ビット４１４を検査
し、このビットがセットされていないことがわかるの
で、該アクセスは許容される。このアクセスの後、シス
テムは諸ビットを更新し、右上ビットをセットして、今
や現在時アクセス・アドレス(具体的には最新のアクセ
ス)の右上で発生したアクセスがあることを示す。前の
状態が最新のアクセス・アドレスの左側に対するアクセ
スが存在したことを示していたので、中央上および左上
ビットがそれら領域における可能なアクセス履歴を示す
ようにセットされる。実際には最新のアクセスの上およ
び左でアクセスは発生していないけれども、最新のアク
セスに先行するアクセスの左でアクセスが発生している
ので、システムは、上および左のアクセスのすべてを、
発生したものとしてフラグを立てなければならない。す
なわち、以前の位置の左に何らかのアクセスが発生した
が、システムは、どれ程左側に発生したかわからないの
で、以前の位置の左に位置していたすべてのアクセスが
今や最新のアクセスの上および左にあることを示すよう
にフラグをたてる。しかし、システム方向状態ビット
は、現在時メモリ・アクセス・アドレスの行の左側にも
右側にもアクセスがなかったこと、また、現在時メモリ
・アクセス・アドレスの下側にもアクセスがなかったこ
とを標示する。
【００２９】今や、ラスタ化処理は長方形の２行目の左
から右へ継続し、コントローラは衝突なしのフラグを立
て続ける。衝突なしのフラッグをたてるこの処理は長方
形の最下部まで続く。
から右へ継続し、コントローラは衝突なしのフラグを立
て続ける。衝突なしのフラッグをたてるこの処理は長方
形の最下部まで続く。
【００３０】第２の例は、本発明のシステム内でヒット
が発生する場合を示すものである。この例は、長方形の
輪郭を描画する場合で、左上のコーナーから始まって、
長方形の周囲の処理を時計回りに進めるものである。処
理の開始時に、コントローラはすべての状態ビットをリ
セットする。最初のアドレスがＸおよびＹレジスタに記
憶され、中央ビットが以前のアクセスがあったことを示
すようにセットされる。アクセスが左から右へ進むにつ
れ、コントローラはアクセスが行の左側にアクセスがあ
ったことを記憶するが、すべての新しいアクセスが最新
のアクセスの右側にあるので、コントローラはヒットを
示すフラグをたてない。
が発生する場合を示すものである。この例は、長方形の
輪郭を描画する場合で、左上のコーナーから始まって、
長方形の周囲の処理を時計回りに進めるものである。処
理の開始時に、コントローラはすべての状態ビットをリ
セットする。最初のアドレスがＸおよびＹレジスタに記
憶され、中央ビットが以前のアクセスがあったことを示
すようにセットされる。アクセスが左から右へ進むにつ
れ、コントローラはアクセスが行の左側にアクセスがあ
ったことを記憶するが、すべての新しいアクセスが最新
のアクセスの右側にあるので、コントローラはヒットを
示すフラグをたてない。
【００３１】最上行セグメントが終了すると、オブジェ
クト分解装置は、最上行の最新のピクセル位置の直下か
らアクセスを開始する。長方形の右辺におけるアクセス
は、それらが最新のアクセスの下にあるので、許容され
る。コントローラは、アクセスが上にあったこと、およ
び左上方向のどこかにアクセスがあったことを認識す
る。長方形の右辺の処理を終了すると、オブジェクト分
解装置は、長方形の底辺に沿って左へのステッピングを
開始する。現在、コントローラはアクセスが同じ行の右
側および上方のどこかにあったことを認識している。し
かし、長方形の右側で底辺ピクセルの左に対しするアク
セスがなかったので、長方形の底辺を規定する底辺ピク
セルの左へ移動するアクセスは許容される。
クト分解装置は、最上行の最新のピクセル位置の直下か
らアクセスを開始する。長方形の右辺におけるアクセス
は、それらが最新のアクセスの下にあるので、許容され
る。コントローラは、アクセスが上にあったこと、およ
び左上方向のどこかにアクセスがあったことを認識す
る。長方形の右辺の処理を終了すると、オブジェクト分
解装置は、長方形の底辺に沿って左へのステッピングを
開始する。現在、コントローラはアクセスが同じ行の右
側および上方のどこかにあったことを認識している。し
かし、長方形の右側で底辺ピクセルの左に対しするアク
セスがなかったので、長方形の底辺を規定する底辺ピク
セルの左へ移動するアクセスは許容される。
【００３２】最後に、長方形の底辺の処理を終了する
と、オブジェクト分解装置は、長方形の左辺に沿って上
昇するアクセスを開始する。長方形の左辺をのぼる最初
のピクセルがアクセスされると、システムは、現在の
「最新の」アドレスの真上である可能性のあるなんらか
の上および左方向アクセスが既に発生していることを認
める。
と、オブジェクト分解装置は、長方形の左辺に沿って上
昇するアクセスを開始する。長方形の左辺をのぼる最初
のピクセルがアクセスされると、システムは、現在の
「最新の」アドレスの真上である可能性のあるなんらか
の上および左方向アクセスが既に発生していることを認
める。
【００３３】この時点においてキャッシュは消去され、
方向状態ビットおよびＸ、Ｙアドレス・レジスタがクリ
アされる。次に、オブジェクト分解装置は、長方形の左
辺をのぼるピクセルをアクセスする。キャッシュの消去
後のすべての新しいアクセスは、衝突の可能性のない上
方向への一線上の移動であるので、長方形の左辺上の処
理の間、ヒットを示すフラグはたたない。
方向状態ビットおよびＸ、Ｙアドレス・レジスタがクリ
アされる。次に、オブジェクト分解装置は、長方形の左
辺をのぼるピクセルをアクセスする。キャッシュの消去
後のすべての新しいアクセスは、衝突の可能性のない上
方向への一線上の移動であるので、長方形の左辺上の処
理の間、ヒットを示すフラグはたたない。
【００３４】図５は、図２の好ましい実施形態の衝突検
出回路部分のブロック図を示す。フレーム・バッファ・
アドレスバス２０４は、(図２の)オブジェクト分解装置
２０２から(図２の)フレーム・バッファ２１０へメモリ
・コントローラ２１２を経由して送付されるアドレスを
受け取る。フレーム・バッファ・アドレスの「Ｘ」部分
が、２つの比較器５０６よび５０８に回送され、そこ
で、アドレスのＸ部分が最新Ｘレジスタ５０２に記憶さ
れている最新Ｘアドレス値と比較される。比較器５０６
および５０８の出力は、ＥＱＸ信号５１４およびＬＴＸ
信号５１６であり、これらの信号は、ＮＯＲゲートを使
用して結合され、ＧＴＸ信号５１６が作成される。これ
らの３つの信号は、フレーム・バッファ・アドレス・バ
ス２０４上のアドレスのＸ部分が、最新Ｘレジスタ５０
２に記憶されている最新のＸアドレス値に等しい(ＥＱ
Ｘ)か、それより大(ＧＴＸ)かあるいは小(ＬＴＸ)であ
るか否かを標示する。
出回路部分のブロック図を示す。フレーム・バッファ・
アドレスバス２０４は、(図２の)オブジェクト分解装置
２０２から(図２の)フレーム・バッファ２１０へメモリ
・コントローラ２１２を経由して送付されるアドレスを
受け取る。フレーム・バッファ・アドレスの「Ｘ」部分
が、２つの比較器５０６よび５０８に回送され、そこ
で、アドレスのＸ部分が最新Ｘレジスタ５０２に記憶さ
れている最新Ｘアドレス値と比較される。比較器５０６
および５０８の出力は、ＥＱＸ信号５１４およびＬＴＸ
信号５１６であり、これらの信号は、ＮＯＲゲートを使
用して結合され、ＧＴＸ信号５１６が作成される。これ
らの３つの信号は、フレーム・バッファ・アドレス・バ
ス２０４上のアドレスのＸ部分が、最新Ｘレジスタ５０
２に記憶されている最新のＸアドレス値に等しい(ＥＱ
Ｘ)か、それより大(ＧＴＸ)かあるいは小(ＬＴＸ)であ
るか否かを標示する。
【００３５】同様に、フレーム・バッファ・アドレスの
「Ｙ」部分が、２つの比較器５１０よび５１２に回送さ
れ、そこで、アドレスのＹ部分が最新Ｙレジスタ５０４
に記憶されている最新Ｙアドレス値と比較される。比較
器５１０および５１２の出力は、ＥＱＹ信号５１８およ
びＬＴＹ信号５２０であり、これらの信号は、ＮＯＲゲ
ートを使用して結合され、ＧＴＹ信号５１９が作成され
る。これらの３つの信号は、フレーム・バッファ・アド
レス・バス２０４上のアドレスのＹ部分が、最新Ｙレジ
スタ５０４に記憶されている最新のＹアドレス値に等し
い(ＥＱＹ)か、それより大(ＧＴＹ)かあるいは小(ＬＴ
Ｙ)であるか否かを標示する。
「Ｙ」部分が、２つの比較器５１０よび５１２に回送さ
れ、そこで、アドレスのＹ部分が最新Ｙレジスタ５０４
に記憶されている最新Ｙアドレス値と比較される。比較
器５１０および５１２の出力は、ＥＱＹ信号５１８およ
びＬＴＹ信号５２０であり、これらの信号は、ＮＯＲゲ
ートを使用して結合され、ＧＴＹ信号５１９が作成され
る。これらの３つの信号は、フレーム・バッファ・アド
レス・バス２０４上のアドレスのＹ部分が、最新Ｙレジ
スタ５０４に記憶されている最新のＹアドレス値に等し
い(ＥＱＹ)か、それより大(ＧＴＹ)かあるいは小(ＬＴ
Ｙ)であるか否かを標示する。
【００３６】これらの６つの信号ＥＱＸ５１４、ＧＴＸ
５１５、ＬＴＸ５１６、ＥＱＹ５１８、ＧＴＹ５１９お
よびＬＴＹ５２０は、アクセスが許容されるか否かを判
断するため図４の状態ビットのいずれを検査しなければ
ならないかを判断するために必要な信号を提供する。図
５の残りの回路部分は、到来信号がＸより小さくＹより
小さい場合ヒットが発生したか否かを判断するために使
用される。
５１５、ＬＴＸ５１６、ＥＱＹ５１８、ＧＴＹ５１９お
よびＬＴＹ５２０は、アクセスが許容されるか否かを判
断するため図４の状態ビットのいずれを検査しなければ
ならないかを判断するために必要な信号を提供する。図
５の残りの回路部分は、到来信号がＸより小さくＹより
小さい場合ヒットが発生したか否かを判断するために使
用される。
【００３７】左上ラッチ５２２は、(図４の)左上ビット
４０２を記憶する。ＡＮＤゲート５２４は、左上ラッチ
５２２内の状態値を、ＬＴＸ信号５１６およびＬＴＹ信
号５２０と結合する。フレーム・バッファ・アドレス２
０４のＸ部分が、最新のＸ値５０２より小さい場合、Ｌ
ＴＸ信号５１６は論理値１である。同様に、フレーム・
バッファ・アドレス２０４のＹ部分が、最新のＹ値５０
４より小さい場合、ＬＴＹ信号５２０は論理値１であ
る。左上ラッチ５２２が左上方向で既にアクセスが発生
したことを標示するようにセットされていれば、上記２
つの論理値の組み合わせはヒットを意味する。従って、
すべての３つのビットが論理値１であれば、ＡＮＤゲー
ト５２４の出力は論理値１となり、これにより、ＡＮＤ
ゲートの出力である論理値１がその他の比較結果のその
他のビットとＯＲゲート５２６によって論理ＯＲされる
と、この新しいアクセスが許容される前にキャッシュが
消去されなければならないことを標示するヒット信号２
１６がセットされる。
４０２を記憶する。ＡＮＤゲート５２４は、左上ラッチ
５２２内の状態値を、ＬＴＸ信号５１６およびＬＴＹ信
号５２０と結合する。フレーム・バッファ・アドレス２
０４のＸ部分が、最新のＸ値５０２より小さい場合、Ｌ
ＴＸ信号５１６は論理値１である。同様に、フレーム・
バッファ・アドレス２０４のＹ部分が、最新のＹ値５０
４より小さい場合、ＬＴＹ信号５２０は論理値１であ
る。左上ラッチ５２２が左上方向で既にアクセスが発生
したことを標示するようにセットされていれば、上記２
つの論理値の組み合わせはヒットを意味する。従って、
すべての３つのビットが論理値１であれば、ＡＮＤゲー
ト５２４の出力は論理値１となり、これにより、ＡＮＤ
ゲートの出力である論理値１がその他の比較結果のその
他のビットとＯＲゲート５２６によって論理ＯＲされる
と、この新しいアクセスが許容される前にキャッシュが
消去されなければならないことを標示するヒット信号２
１６がセットされる。
【００３８】その他の８つの状態ビットに関する回路
は、図４の方向状態ビット定義に従って比較器出力信号
ＥＱＸ５１４、ＧＴＸ５１５、ＬＴＸ５１６、ＥＱＹ５
１８、ＧＴＹ５１９とＬＴＹ５２０という異なる信号を
使用することを当然除いて、上記の左上ラッチ５２２お
よびＡＮＤゲート５２４と同様である。ＯＲゲート５２
６は状態比較のすべての出力を結合して、ヒット信号２
１６を生成する。
は、図４の方向状態ビット定義に従って比較器出力信号
ＥＱＸ５１４、ＧＴＸ５１５、ＬＴＸ５１６、ＥＱＹ５
１８、ＧＴＹ５１９とＬＴＹ５２０という異なる信号を
使用することを当然除いて、上記の左上ラッチ５２２お
よびＡＮＤゲート５２４と同様である。ＯＲゲート５２
６は状態比較のすべての出力を結合して、ヒット信号２
１６を生成する。
【００３９】アクセスが発生する都度、図４に示される
９個の状態ビットのすべては更新されなければならな
い。アクセスが許容されなければ、キャッシュは消去さ
れ、すべての状態ビットはクリアされる。アクセスが許
容される場合、下記表１に示される式に従って、各タイ
プのアクセスの発生後９つの状態ビットの各々が更新さ
れる。例えば、表１の最初のエントリは、前のアクセス
の左上にアクセスが発生した後に９個の状態ビットを更
新するための式を示し、第２のエントリは、前のアクセ
スのすぐ上にアクセスが発生した後に９個の状態ビット
を更新するための式を示し、以下のエントリも同様にそ
れぞれ対応する状態ビットを更新する式を示す。
９個の状態ビットのすべては更新されなければならな
い。アクセスが許容されなければ、キャッシュは消去さ
れ、すべての状態ビットはクリアされる。アクセスが許
容される場合、下記表１に示される式に従って、各タイ
プのアクセスの発生後９つの状態ビットの各々が更新さ
れる。例えば、表１の最初のエントリは、前のアクセス
の左上にアクセスが発生した後に９個の状態ビットを更
新するための式を示し、第２のエントリは、前のアクセ
スのすぐ上にアクセスが発生した後に９個の状態ビット
を更新するための式を示し、以下のエントリも同様にそ
れぞれ対応する状態ビットを更新する式を示す。
【００４０】下記表２は、左上の状態ビットを更新する
ための式を示す。この式は、表１に示されている左上の
状態ビットに対する更新のすべてを論理ＯＲ演算を使用
して結合することによって作成されている。その他の８
個の状態ビットを更新する式も、同様に、表１に示され
ているそれぞれの状態ビットに対する更新のすべてを論
理ＯＲ演算を使用して結合することによって作成され
る。表１および表２の式において、記号"＋"は論理ＯＲ
演算を示し、記号"・"は論理ＡＮＤ演算を示す。記号"
＜＝"は「...によって置き換えられる」を意味する。
ための式を示す。この式は、表１に示されている左上の
状態ビットに対する更新のすべてを論理ＯＲ演算を使用
して結合することによって作成されている。その他の８
個の状態ビットを更新する式も、同様に、表１に示され
ているそれぞれの状態ビットに対する更新のすべてを論
理ＯＲ演算を使用して結合することによって作成され
る。表１および表２の式において、記号"＋"は論理ＯＲ
演算を示し、記号"・"は論理ＡＮＤ演算を示す。記号"
＜＝"は「...によって置き換えられる」を意味する。
【００４１】
【表１】 // 新しいアクセスが左上の場合 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ビットの記憶域および比較器が必要とされる。
ため本発明を拡張することができる点は当業者に認めら
れることであろう。３次元の実施のためには、３次元の
各々について２７ビットの記憶域および比較器が必要と
される。ｎ次元の実施のためには、ｎ次元の各々につい
て３nビットの記憶域および比較器が必要とされる。
【００４５】以上、本発明の好ましい実施形態を記述し
たが、上記記述は本発明をそのような実施形態に限定す
る意図を有するものではない。本発明の理念を逸脱する
ことなく本発明の実施形態および構成に種々の変更およ
び修正を加えることが可能である点は当業者に認められ
ることであろう。
たが、上記記述は本発明をそのような実施形態に限定す
る意図を有するものではない。本発明の理念を逸脱する
ことなく本発明の実施形態および構成に種々の変更およ
び修正を加えることが可能である点は当業者に認められ
ることであろう。
【００４６】本発明には、例として次のような実施様態
が含まれる。 （１）メモリに対する複数アクセスの間に発生するアド
レス衝突を検出し、衝突が検出される場合ヒット信号を
送信する回路であって、受け取った最新アドレスを保持
する最新アドレス・レジスタと、以前のメモリ・アクセ
スが第１の方向で発生したという標識を記憶する第１方
向状態ビットと、現在時メモリ・アドレスを上記最新ア
ドレス・レジスタに記憶されている最新アドレスと比較
し、上記現在時メモリ・アドレスが上記最新アドレス・
レジスタに記憶されている最新アドレスに対して第１の
方向に位置することを標示する比較器回路と、衝突を検
出する機能を持ち、上記現在時メモリ・アドレスが上記
最新アドレス・レジスタに記憶されている最新アドレス
に対して第１の方向に位置することを上記比較器回路が
標示し、かつ、上記第１方向状態ビットが以前のメモリ
・アクセスが上記第１の方向で発生したことを標示する
場合、ヒット信号を送信するヒット検出回路と、を備え
るアドレス衝突検出回路。 （２）以前のメモリ・アクセスが上記第１の方向とは反
対の第２の方向で発生したという標識を記憶する第２方
向状態ビットと、現在時メモリ・アドレスを上記最新ア
ドレス・レジスタに記憶されている最新アドレスと比較
し、上記現在時メモリ・アドレスが上記最新アドレス・
レジスタに記憶されている最新アドレスに対して第２の
方向に位置することを標示する第２比較器回路と、衝突
を検出する機能を持ち、上記現在時メモリ・アドレスが
上記最新アドレス・レジスタに記憶されている最新アド
レスに対して第２の方向に位置することを上記第２比較
器回路が標示しかつ上記第２方向状態ビットが以前のメ
モリ・アクセスが上記第２の方向で発生したことを標示
する時第２ヒット信号を送信する第２ヒット検出回路
と、を更に備える上記（１）に記載のアドレス衝突検出
回路。 （３）上記最新アドレス・レジスタ、上記第１方向状態
ビットおよび上記第２方向状態ビットにおける状態情報
の存在を標示する中央状態ビットを更に備える上記
（２）に記載のアドレス衝突検出回路。 （４）現在時メモリ・アドレスを上記最新アドレス・レ
ジスタに記憶されている最新アドレスと比較し、上記現
在時メモリ・アドレスが上記最新アドレス・レジスタに
記憶されている最新アドレスと等しいことを標示する第
３比較器回路と、衝突を検出する機能を持ち、上記現在
時メモリ・アドレスが上記最新アドレス・レジスタに記
憶されている最新アドレスと等しいことを上記第３比較
器回路が標示する時第３ヒット信号を送信する第３ヒッ
ト検出回路と、を更に備える上記（３）に記載のアドレ
ス衝突検出回路。
が含まれる。 （１）メモリに対する複数アクセスの間に発生するアド
レス衝突を検出し、衝突が検出される場合ヒット信号を
送信する回路であって、受け取った最新アドレスを保持
する最新アドレス・レジスタと、以前のメモリ・アクセ
スが第１の方向で発生したという標識を記憶する第１方
向状態ビットと、現在時メモリ・アドレスを上記最新ア
ドレス・レジスタに記憶されている最新アドレスと比較
し、上記現在時メモリ・アドレスが上記最新アドレス・
レジスタに記憶されている最新アドレスに対して第１の
方向に位置することを標示する比較器回路と、衝突を検
出する機能を持ち、上記現在時メモリ・アドレスが上記
最新アドレス・レジスタに記憶されている最新アドレス
に対して第１の方向に位置することを上記比較器回路が
標示し、かつ、上記第１方向状態ビットが以前のメモリ
・アクセスが上記第１の方向で発生したことを標示する
場合、ヒット信号を送信するヒット検出回路と、を備え
るアドレス衝突検出回路。 （２）以前のメモリ・アクセスが上記第１の方向とは反
対の第２の方向で発生したという標識を記憶する第２方
向状態ビットと、現在時メモリ・アドレスを上記最新ア
ドレス・レジスタに記憶されている最新アドレスと比較
し、上記現在時メモリ・アドレスが上記最新アドレス・
レジスタに記憶されている最新アドレスに対して第２の
方向に位置することを標示する第２比較器回路と、衝突
を検出する機能を持ち、上記現在時メモリ・アドレスが
上記最新アドレス・レジスタに記憶されている最新アド
レスに対して第２の方向に位置することを上記第２比較
器回路が標示しかつ上記第２方向状態ビットが以前のメ
モリ・アクセスが上記第２の方向で発生したことを標示
する時第２ヒット信号を送信する第２ヒット検出回路
と、を更に備える上記（１）に記載のアドレス衝突検出
回路。 （３）上記最新アドレス・レジスタ、上記第１方向状態
ビットおよび上記第２方向状態ビットにおける状態情報
の存在を標示する中央状態ビットを更に備える上記
（２）に記載のアドレス衝突検出回路。 （４）現在時メモリ・アドレスを上記最新アドレス・レ
ジスタに記憶されている最新アドレスと比較し、上記現
在時メモリ・アドレスが上記最新アドレス・レジスタに
記憶されている最新アドレスと等しいことを標示する第
３比較器回路と、衝突を検出する機能を持ち、上記現在
時メモリ・アドレスが上記最新アドレス・レジスタに記
憶されている最新アドレスと等しいことを上記第３比較
器回路が標示する時第３ヒット信号を送信する第３ヒッ
ト検出回路と、を更に備える上記（３）に記載のアドレ
ス衝突検出回路。
【００４７】（５）第１の次元としてＸアドレスを持ち
第２の次元としてＹアドレスを持つ２次元アレイとして
構成されるメモリにおける複数メモリ・アクセス間のア
ドレス衝突を検出し、衝突が検出される場合ヒット信号
を送信する回路であって、受け取った最新アドレスを記
憶する最新Ｘアドレス・レジスタと、受け取った最新ア
ドレスを記憶する最新Ｙアドレス・レジスタと、以前の
メモリ・アクセスが上、下、左または右方向で発生した
という標識を記憶する４個の方向状態ビットと、現在時
メモリ・アドレスを上記最新Ｘアドレス・レジスタに記
憶されている最新アドレスと比較し、上記現在時メモリ
・アドレスが上記最新Ｘアドレス・レジスタに記憶され
ている最新アドレスに対して左または右の方向に位置す
ることを標示するＸ比較器回路と、現在時メモリ・アド
レスを上記最新Ｙアドレス・レジスタに記憶されている
最新アドレスと比較し、上記現在時メモリ・アドレスが
上記最新Ｙアドレス・レジスタに記憶されている最新ア
ドレスに対して上または下の方向に位置することを標示
するＹ比較器回路と、衝突を検出する機能を持ち、上記
現在時メモリ・アドレスが上記最新Ｘアドレス・レジス
タに記憶されている最新アドレスおよび上記最新Ｙアド
レス・レジスタに記憶されている最新アドレスに対して
上、下、左または右の方向に位置することを上記Ｘ比較
器回路および上記Ｙ比較器回路が標示し、上記Ｘおよび
Ｙ比較器回路によって標示される方向に対応する上記４
個の方向状態ビットの１つが以前のメモリ・アクセスが
上記対応する方向で発生したことを標示する時ヒット信
号を送信するヒット検出回路と、を備えるアドレス衝突
検出回路。 （６）上記最新Ｘアドレス・レジスタおよび上記最新Ｙ
アドレス・レジスタにおける状態情報の存在を標示する
中央状態ビットを更に備える上記（５）に記載のアドレ
ス衝突検出回路。
第２の次元としてＹアドレスを持つ２次元アレイとして
構成されるメモリにおける複数メモリ・アクセス間のア
ドレス衝突を検出し、衝突が検出される場合ヒット信号
を送信する回路であって、受け取った最新アドレスを記
憶する最新Ｘアドレス・レジスタと、受け取った最新ア
ドレスを記憶する最新Ｙアドレス・レジスタと、以前の
メモリ・アクセスが上、下、左または右方向で発生した
という標識を記憶する４個の方向状態ビットと、現在時
メモリ・アドレスを上記最新Ｘアドレス・レジスタに記
憶されている最新アドレスと比較し、上記現在時メモリ
・アドレスが上記最新Ｘアドレス・レジスタに記憶され
ている最新アドレスに対して左または右の方向に位置す
ることを標示するＸ比較器回路と、現在時メモリ・アド
レスを上記最新Ｙアドレス・レジスタに記憶されている
最新アドレスと比較し、上記現在時メモリ・アドレスが
上記最新Ｙアドレス・レジスタに記憶されている最新ア
ドレスに対して上または下の方向に位置することを標示
するＹ比較器回路と、衝突を検出する機能を持ち、上記
現在時メモリ・アドレスが上記最新Ｘアドレス・レジス
タに記憶されている最新アドレスおよび上記最新Ｙアド
レス・レジスタに記憶されている最新アドレスに対して
上、下、左または右の方向に位置することを上記Ｘ比較
器回路および上記Ｙ比較器回路が標示し、上記Ｘおよび
Ｙ比較器回路によって標示される方向に対応する上記４
個の方向状態ビットの１つが以前のメモリ・アクセスが
上記対応する方向で発生したことを標示する時ヒット信
号を送信するヒット検出回路と、を備えるアドレス衝突
検出回路。 （６）上記最新Ｘアドレス・レジスタおよび上記最新Ｙ
アドレス・レジスタにおける状態情報の存在を標示する
中央状態ビットを更に備える上記（５）に記載のアドレ
ス衝突検出回路。
【００４８】（７）現在時メモリ・アドレスが上記最新
Ｙアドレス・レジスタに記憶されている最新アドレスに
対し下方向に位置することを上記Ｙ比較器回路が標示す
る時、以前のメモリ・アクセスが上方向で発生したこと
を標示するように上記４個の方向状態ビットの１つをセ
ットする上状態更新回路と、現在時メモリ・アドレスが
上記最新Ｙアドレス・レジスタに記憶されている最新ア
ドレスに対し上方向に位置することを上記Ｙ比較器回路
が標示する時、以前のメモリ・アクセスが下方向で発生
したことを標示するように上記４個の方向状態ビットの
１つをセットする下状態更新回路と、現在時メモリ・ア
ドレスが上記最新Ｘアドレス・レジスタに記憶されてい
る最新アドレスに対し右方向に位置することを上記Ｘ比
較器回路が標示する時、以前のメモリ・アクセスが左方
向で発生したことを標示するように上記４個の方向状態
ビットの１つをセットする左状態更新回路と、現在時メ
モリ・アドレスが上記最新Ｘアドレス・レジスタに記憶
されている最新アドレスに対し左方向に位置することを
上記Ｘ比較器回路が標示する時、以前のメモリ・アクセ
スが右方向で発生したことを標示するように上記４個の
方向状態ビットの１つをセットする右状態更新回路と、
を更に備える上記（５）に記載のアドレス衝突検出回
路。 （８）以前のメモリ・アクセスが左上、左下、右上また
は右下の方向で発生したという標識を記憶する第２の４
個の方向状態ビットと、衝突を検出する機能を持ち、上
記現在時メモリ・アドレスが上記最新Ｘアドレス・レジ
スタに記憶されている最新アドレスおよび上記最新Ｙア
ドレス・レジスタに記憶されている最新アドレスに対し
て左上、左下、右上または右下の方向に位置することを
上記Ｘ比較器回路および上記Ｙ比較器回路が標示し、上
記ＸおよびＹ比較器回路によって標示される方向に対応
する上記第２の４個の方向状態ビットの１つが以前のメ
モリ・アクセスが上記対応する方向で発生したことを標
示する時ヒット信号を送信する第２ヒット検出回路と、
を更に備える上記（５）に記載のアドレス衝突検出回
路。
Ｙアドレス・レジスタに記憶されている最新アドレスに
対し下方向に位置することを上記Ｙ比較器回路が標示す
る時、以前のメモリ・アクセスが上方向で発生したこと
を標示するように上記４個の方向状態ビットの１つをセ
ットする上状態更新回路と、現在時メモリ・アドレスが
上記最新Ｙアドレス・レジスタに記憶されている最新ア
ドレスに対し上方向に位置することを上記Ｙ比較器回路
が標示する時、以前のメモリ・アクセスが下方向で発生
したことを標示するように上記４個の方向状態ビットの
１つをセットする下状態更新回路と、現在時メモリ・ア
ドレスが上記最新Ｘアドレス・レジスタに記憶されてい
る最新アドレスに対し右方向に位置することを上記Ｘ比
較器回路が標示する時、以前のメモリ・アクセスが左方
向で発生したことを標示するように上記４個の方向状態
ビットの１つをセットする左状態更新回路と、現在時メ
モリ・アドレスが上記最新Ｘアドレス・レジスタに記憶
されている最新アドレスに対し左方向に位置することを
上記Ｘ比較器回路が標示する時、以前のメモリ・アクセ
スが右方向で発生したことを標示するように上記４個の
方向状態ビットの１つをセットする右状態更新回路と、
を更に備える上記（５）に記載のアドレス衝突検出回
路。 （８）以前のメモリ・アクセスが左上、左下、右上また
は右下の方向で発生したという標識を記憶する第２の４
個の方向状態ビットと、衝突を検出する機能を持ち、上
記現在時メモリ・アドレスが上記最新Ｘアドレス・レジ
スタに記憶されている最新アドレスおよび上記最新Ｙア
ドレス・レジスタに記憶されている最新アドレスに対し
て左上、左下、右上または右下の方向に位置することを
上記Ｘ比較器回路および上記Ｙ比較器回路が標示し、上
記ＸおよびＹ比較器回路によって標示される方向に対応
する上記第２の４個の方向状態ビットの１つが以前のメ
モリ・アクセスが上記対応する方向で発生したことを標
示する時ヒット信号を送信する第２ヒット検出回路と、
を更に備える上記（５）に記載のアドレス衝突検出回
路。
【００４９】（９）現在時メモリ・アドレスが上記最新
Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジ
スタに記憶されている最新アドレスに対し右下方向に位
置することを上記Ｘ比較器回路および上記Ｙ比較器回路
が標示する時、以前のメモリ・アクセスが左上方向で発
生したことを標示するように上記第２の４個の方向状態
ビットの１つをセットする左上状態更新回路と、現在時
メモリ・アドレスが上記最新Ｘアドレス・レジスタおよ
び上記最新Ｙアドレス・レジスタに記憶されている最新
アドレスに対し左上方向に位置することを上記Ｘ比較器
回路および上記Ｙ比較器回路が標示する時、以前のメモ
リ・アクセスが右下方向で発生したことを標示するよう
に上記第２の４個の方向状態ビットの１つをセットする
右下状態更新回路と、現在時メモリ・アドレスが上記最
新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レ
ジスタに記憶されている最新アドレスに対し右上方向に
位置することを上記Ｘ比較器回路および上記Ｙ比較器回
路が標示する時、以前のメモリ・アクセスが左下方向で
発生したことを標示するように上記第２の４個の方向状
態ビットの１つをセットする左下状態更新回路と、現在
時メモリ・アドレスが上記最新Ｘアドレス・レジスタお
よび上記最新Ｙアドレス・レジスタに記憶されている最
新アドレスに対し左下方向に位置することを上記Ｘ比較
器回路および上記Ｙ比較器回路が標示する時、以前のメ
モリ・アクセスが右上方向で発生したことを標示するよ
うに上記第２の４個の方向状態ビットの１つをセットす
る右上状態更新回路と、を更に備える上記（８）に記載
のアドレス衝突検出回路。
Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レジ
スタに記憶されている最新アドレスに対し右下方向に位
置することを上記Ｘ比較器回路および上記Ｙ比較器回路
が標示する時、以前のメモリ・アクセスが左上方向で発
生したことを標示するように上記第２の４個の方向状態
ビットの１つをセットする左上状態更新回路と、現在時
メモリ・アドレスが上記最新Ｘアドレス・レジスタおよ
び上記最新Ｙアドレス・レジスタに記憶されている最新
アドレスに対し左上方向に位置することを上記Ｘ比較器
回路および上記Ｙ比較器回路が標示する時、以前のメモ
リ・アクセスが右下方向で発生したことを標示するよう
に上記第２の４個の方向状態ビットの１つをセットする
右下状態更新回路と、現在時メモリ・アドレスが上記最
新Ｘアドレス・レジスタおよび上記最新Ｙアドレス・レ
ジスタに記憶されている最新アドレスに対し右上方向に
位置することを上記Ｘ比較器回路および上記Ｙ比較器回
路が標示する時、以前のメモリ・アクセスが左下方向で
発生したことを標示するように上記第２の４個の方向状
態ビットの１つをセットする左下状態更新回路と、現在
時メモリ・アドレスが上記最新Ｘアドレス・レジスタお
よび上記最新Ｙアドレス・レジスタに記憶されている最
新アドレスに対し左下方向に位置することを上記Ｘ比較
器回路および上記Ｙ比較器回路が標示する時、以前のメ
モリ・アクセスが右上方向で発生したことを標示するよ
うに上記第２の４個の方向状態ビットの１つをセットす
る右上状態更新回路と、を更に備える上記（８）に記載
のアドレス衝突検出回路。
【００５０】
【発明の効果】本発明によって、連想メモリにおいて使
用されている高価な並列比較を使用せずに、メモリから
データを読み取る際に発生する可能性のあるキャッシュ
衝突を効率的に検出する方法および装置を実現すること
ができる。
用されている高価な並列比較を使用せずに、メモリから
データを読み取る際に発生する可能性のあるキャッシュ
衝突を効率的に検出する方法および装置を実現すること
ができる。
【図１】本発明を実施するグラフィック・コントローラ
を含むコンピュータ・システムのブロック図である。
を含むコンピュータ・システムのブロック図である。
【図２】図１のグラフィック・コントローラのブロック
図である。
図である。
【図３】本発明の代替実施形態において使用される３個
の状態ビットおよび１つのアドレス・レジスタを示すブ
ロック図である。
の状態ビットおよび１つのアドレス・レジスタを示すブ
ロック図である。
【図４】本発明の好ましい実施形態において、以前のア
クセスを示すために使用される９個の状態ビットを示す
ブロック図である。
クセスを示すために使用される９個の状態ビットを示す
ブロック図である。
【図５】本発明の好ましい実施形態である図２の衝突検
出回路部分示すブロック図である。
出回路部分示すブロック図である。
【図６】本発明の好ましい実施形態である図２の衝突検
出回路部分の論理ブロック図である。
出回路部分の論理ブロック図である。
１００ コンピュータ・システム １０２ 処理エレメント １０４ システム・バス １０６ キーボード １０８ グラフィック・ロケータ装置 １０９ グラフィック・コントローラ １１０ 表示装置 １１２ データ記憶装置 １１６ メモリ １１８ オペレーティング・システム １２０ アプリケーション・プログラム ２０２ オブジェクト分解回路 ２０４ フレーム・バッファ・アドレス・バス ２０６ キャッシュ・メモリ ２１０ フレーム・バッファ ２１２ メモリ・コントローラ ２１４ 衝突検出回路 ２１６ ヒット信号 ３０２ 最新アクセス・アドレス・レジスタ ３０４ 低位アクセス状態ビット ３０６、４１０ 中央状態ビット ３０４ 高位アクセス状態ビット ４０２ 左上アクセス状態ビット ４０４ 上アクセス状態ビット ４０６ 右上アクセス状態ビット ４０８ 左アクセス状態ビット ４１２ 右アクセス状態ビット ４１４ 左下アクセス状態ビット ４１６ 下アクセス状態ビット ４１８ 右下アクセス状態ビット ５０２ 最新Ｘアドレス・レジスタ ５０４ 最新Ｙアドレス・レジスタ ５０６、５１０ Ｘアドレス比較器 ５０８、５１２ Ｙアドレス比較器 ５２２ 左上ラッチ器 ５２４ ＡＮＤゲート ５２６ ＯＲゲート
Claims (1)
- 【請求項１】メモリに対する複数アクセスの間に発生す
るアドレス衝突を検出し、衝突が検出される場合ヒット
信号を送信する回路であって、 受け取った最新アドレスを保持する最新アドレス・レジ
スタと、 以前のメモリ・アクセスが第１の方向で発生したという
標識を記憶する第１方向状態ビットと、 現在時メモリ・アドレスを上記最新アドレス・レジスタ
に記憶されている最新アドレスと比較し、上記現在時メ
モリ・アドレスが上記最新アドレス・レジスタに記憶さ
れている最新アドレスに対して第１の方向に位置するこ
とを標示する比較器回路と、 衝突を検出する機能を持ち、上記現在時メモリ・アドレ
スが上記最新アドレス・レジスタに記憶されている最新
アドレスに対して第１の方向に位置することを上記比較
器回路が標示し、かつ、上記第１方向状態ビットが以前
のメモリ・アクセスが上記第１の方向で発生したことを
標示する場合、ヒット信号を送信するヒット検出回路
と、 を備えるアドレス衝突検出回路。
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 true JPH1083346A (ja) | 1998-03-31 |
| JPH1083346A5 JPH1083346A5 (ja) | 2005-03-17 |
| JP3776202B2 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 |
| 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 |
| US8860722B2 (en) * | 2004-05-14 | 2014-10-14 | Nvidia Corporation | Early Z scoreboard tracking system and method |
| US8736620B2 (en) * | 2004-05-14 | 2014-05-27 | Nvidia Corporation | Kill bit graphics processing system and method |
| US8743142B1 (en) | 2004-05-14 | 2014-06-03 | Nvidia Corporation | Unified data fetch 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 |
| US8411105B1 (en) | 2004-05-14 | 2013-04-02 | Nvidia Corporation | Method and system for computing pixel parameters |
| US8736628B1 (en) | 2004-05-14 | 2014-05-27 | Nvidia Corporation | Single thread graphics processing system and method |
| US20060007234A1 (en) * | 2004-05-14 | 2006-01-12 | Hutchins Edward A | Coincident graphics pixel scoreboard tracking system and method |
| US8711155B2 (en) * | 2004-05-14 | 2014-04-29 | Nvidia Corporation | Early kill removal graphics processing system and method |
| US8687010B1 (en) | 2004-05-14 | 2014-04-01 | Nvidia Corporation | Arbitrary size texture palettes for use in graphics systems |
| US8416242B1 (en) | 2004-05-14 | 2013-04-09 | Nvidia Corporation | Method and system for interpolating level-of-detail in graphics processors |
| US8386628B1 (en) * | 2005-05-23 | 2013-02-26 | Glance Networks, Inc. | Method and apparatus for reducing the amount of information that must be transmitted to slower viewers over a remote viewing session |
| 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 |
| 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 |
| 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 |
| 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 |
|---|---|
| US5777628A (en) | 1998-07-07 |
| JP3776202B2 (ja) | 2006-05-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3776202B2 (ja) | アドレス衝突検出回路 | |
| US5430841A (en) | Context management in a graphics system | |
| US4561051A (en) | Memory access method and apparatus in multiple processor systems | |
| JP3172950B2 (ja) | 予測キャッシングシステム | |
| JPH0212523A (ja) | コンピユータ・デイスプレイ・システム | |
| US6931495B2 (en) | Processor and method of arithmetic processing thereof | |
| JPH0547851B2 (ja) | ||
| JP2866153B2 (ja) | 文字処理装置及び方法 | |
| US5473348A (en) | Apparatus and method of controlling paging unit of coprocessor built in display control system | |
| US7333106B1 (en) | Method and apparatus for Z-buffer operations | |
| JP2002041358A (ja) | プロセッサシステム | |
| JPH0697393B2 (ja) | ビットマップ処理装置 | |
| JP2773458B2 (ja) | ベクトル制御装置 | |
| JPH0520195A (ja) | キヤツシユメモリ制御装置 | |
| JPH10261076A (ja) | 画像データ処理装置 | |
| JP3525771B2 (ja) | バス・スヌープ制御回路 | |
| JPH06149680A (ja) | アドレス変換装置 | |
| KR940001013B1 (ko) | 영상처리 장치 및 그것을 사용하는 시스템 | |
| KR880005504A (ko) | 버스 접속 제어기능을 가지는 그래픽 처리장치 | |
| JP2964504B2 (ja) | 文書処理装置 | |
| JPH02241267A (ja) | 画像情報処理装置 | |
| JPH05120139A (ja) | キヤツシユメモリ装置 | |
| JPS6063650A (ja) | バッファメモリ一致制御方式 | |
| JPS63243990A (ja) | 文字転送方式 | |
| JPH0659651A (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 |