データ値の多次元アレイへのパラレルなアクセスを提供するデータ処理装置
【課題】より効率的なキャッシュの使用をサポートする２次元アレイとして構成されるデータを処理する装置を提供する。
【解決手段】メインメモリに格納される画素値を利用して、位置の多次元領域の移動の時点を規定する処理のため、画素値がキャッシュされる。画素値に対してキャッシュミスが発生すると、キャッシュ位置におけるデータのキャッシュ置換が実行され、領域外の画像における位置に対する画素データを格納する位置が、領域内部の画像における画素データ位置を格納する置換キャッシュ位置から選択的に免除する置換のために選択される。実施例では、領域内部及び外部のデータ値をキャッシュするため異なるタイプのキャッシュ構成が利用され、キャッシュ位置に関してはキャッシュ位置より高いレベルの出力並列化をサポートし、内部の位置のキャッシュでは画像からの各ラインに対するデータはバンク上で循環的に繰り返すようにして分散される。
【解決手段】メインメモリに格納される画素値を利用して、位置の多次元領域の移動の時点を規定する処理のため、画素値がキャッシュされる。画素値に対してキャッシュミスが発生すると、キャッシュ位置におけるデータのキャッシュ置換が実行され、領域外の画像における位置に対する画素データを格納する位置が、領域内部の画像における画素データ位置を格納する置換キャッシュ位置から選択的に免除する置換のために選択される。実施例では、領域内部及び外部のデータ値をキャッシュするため異なるタイプのキャッシュ構成が利用され、キャッシュ位置に関してはキャッシュ位置より高いレベルの出力並列化をサポートし、内部の位置のキャッシュでは画像からの各ラインに対するデータはバンク上で循環的に繰り返すようにして分散される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置に関し、より詳細には映像データ処理装置に関する。
【背景技術】
【０００２】
米国特許第５，５３０，４８１号は、ＭＰＥＧエンコーダを記載している。ＭＰＥＧでは、いくつかの画像が、隣接画像からの画素ベクトルブロックを更新画像の選択された一に配置することによって、隣接画像に対する更新として符号化される。ＭＰＥＧ符号化は、ブロックの当初の位置から選択された位置への移動の距離及び方法を記述する動きベクトルの選択を伴う。
【０００３】
ＭＰＥＧ符号化は、典型的には、更新により復号化される画像内の異なるブロックの画素コンテンツを隣接画像内のあるブロックのコンテンツと比較することによって、有用な動きベクトルを検索する。このため、これらの画像の少なくとも１つを格納するのに画像メモリが必要とされる。
【０００４】
米国特許第５，５３０，４８１号は、動きベクトルの検索を高速化するのにどのようにバッファメモリが利用可能であるかを記載している。バッファメモリは、ゼロの動きベクトルに対応するブロックを含み、包囲する画素領域についての画素データを格納する。適切な動きベクトルが選択されると、典型的には以前の領域の大部分と重複する新たな領域が処理され、それに対して、この新たな領域の境界部分の画素データのみがバッファメモリにフェッチされる必要がある。同様の形式の領域ベースのアクセスが、パターンマッチング処理のフィルタリングなど他の画像処理に必要とされる。
【０００５】
米国特許第６，１２５，４３２号は、同様の動きベクトル推定を、この目的のためのキャッシュメモリを利用して実行する。当該特許には詳細には記載されていないが、データをフェッチするのに利用可能なアドレスに対応して、メインメモリからのデータを格納するキャッシュメモリ位置を有するキャッシュメモリは周知である。データがキャッシュメモリ位置に格納されるアドレスは変更可能である。典型的には、データがキャッシュメモリに格納されていない新たなアドレスがアドレス指定されると、当該データはメインメモリからフェッチされ、古いアドレスに対して使用されたキャッシュメモリ位置が、この新たなアドレスと対応するデータについて再利用される。
【０００６】
このタイプの画像処理のパフォーマンス特性は、領域からの画素データのためのメモリの構成によって大きな影響を受ける。動きベクトルの検索中に必要とされる領域のすべての画素を格納するための容量を備えた大きなキャッシュバッファメモリを利用し、当該領域が変更される毎にすべての新しい画素を予めフェッチすることは、キャッシュミスが回避されるという効果を有する。このアプローチの問題点は、より大きな検索領域が必要とされるとき、より大きなバッファメモリが必要となるということである。他には、領域からの画素の一部のみが格納され、他の画素が、当該他の画素が動きベクトルの検索中にアドレス指定されるとき、キャッシュされている画素を置換するのに利用される小さなキャッシュメモリを使用するというものがある。この代替は、キャッシュメモリサイズを低減するが、キャッシュミスによる電力消費と遅延を増大させる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明の課題は、画像処理装置を提供することであり、より一般には、より効率的なキャッシュの使用をサポートする２次元アレイとして構成されるデータを処理する装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明によるデータ処理装置は、請求項１に記載される。データ処理ユニットは、データ値のアレイを処理し、当該アレイのスライドする位置領域を規定する。この領域は、連続的な時間のインターバルにおける連続的な位置を想定する。各時間インターバル中、処理ユニットは、当該時間インターバルにおいて想定される領域内及びその周囲の位置からのデータ値を利用する。データ値をキャッシュするのにキャッシュメモリユニットが設けられる。キャッシュメモリユニットは、処理されるデータアレイにおけるアドレスに適応的に関連付けされたキャッシュ位置を有する。キャッシュ管理は、アドレスの置換による関連付けされたアドレスの変更を可能にする。各時間インターバル中、異なる処理が、当該時間インターバルに想定された領域からのデータ値と、当該領域周辺からのデータ値とに与えられる。当該領域からのデータ値を格納するキャッシュ位置はキャッシュ置換から免除される（ｅｘｅｍｐｔｅｄ）一方、当該領域の周囲からのデータ値を格納するキャッシュ位置はキャッシュ置換される。
【０００９】
キャッシュサイズは、一般には、当該領域が想定される時間インターバル中に当該領域の周囲の位置からプロセッサが必要とするすべての位置のデータ値をキャッシュするのに必要なものより小さい。従って、当該領域の周辺の位置のデータ値は、一般には処理中に置換される。処理ユニットによって使用されるアドレッシングシーケンスに応じて、特定位置のデータ値をリロードすることさえ必要になるかもしれない。このように、キャッシュ位置が効率的に使用され、領域内の頻繁に使用されるデータ値の免除はキャッシュミスを減少させ、領域外のキャッシュ置換の使用は必要とされるキャッシュサイズを低減する。
【００１０】
典型的には、領域のサイズは、例えば、動きベクトルの推定のため一致するマクロブロックの検索中など、処理ユニットがアクセス単位として利用するブロック（すなわち、ブロック及び複数のブロックを含むマクロブロック）のサイズを超える。一例では、当該領域は、中心のマクロブロックと、この中心のマクロブロックの上下左右の隣接するマクロブロックの半分を含む。従って、各マクロブロックがキャッシュミスのリスクなくアドレス指定可能な互いに重複する複数のマクロブロックが領域に適合する一方、中心のマクロブロックからより遠くにあるマクロブロックは部分的にキャッシュミスのリスクがあり、さらに遠くにあるマクロブロックは、完全にキャッシュミスのリスクがある。好ましくは、キャッシュメモリユニットが、アドレス指定されたブロック（又はより一般にはマクロブロック）から複数のデータ値をパラレルに出力するよう構成される。アドレス指定されたブロックが重複しているとき、データ値の境界部分の領域は免除されたキャッシュ位置からのものであるかもしれず、一部は免除されていないキャッシュ位置からのものであるかもしれない。
【００１１】
好ましくは、予測される以降の領域からのデータ値が、メインメモリから免除されるキャッシュ位置に予めフェッチされる。より好ましくは、ウィンドウが移動する際、免除されているキャッシュ位置へのコピー前に予めフェッチされたデータ値を格納するためのプリフェッチバッファが設けられる。
【００１２】
好ましくは、所定のキャッシュ位置セットを利用して、現在領域のデータ値を格納する。この結果、これらのキャッシュ位置の構成は、領域外の位置に対する他のキャッシュ位置の構成とは異なるものになるかもしれず、当該キャッシュ位置が置換を免除されているという知識を利用して、例えば、領域外のデータを格納するキャッシュ位置に対するものよい、領域内のデータを格納するキャッシュ位置に対するより大きなキャッシュメモリ位置（より多くの位置からのデータ値に対する）を利用することによって、領域内のデータに対するキャッシュ位置の構成を最適化する。
【００１３】
一実施例では、所定の位置に対して使用されるキャッシュメモリが、各々がパラレルな異なるｙ−アドレスの第１の個数のラインセグメントに対するデータ値を生成するよう構成される。残りのキャッシュ要素について、１つのｙ−アドレスの１つのみのラインセグメント又は第１の個数より少ない第２の個数のｙ−アドレスの第２の個数のラインセグメントに対するデータ値を生成可能な他のタイプのキャッシュメモリが使用される。所定の位置にデータ値が格納されているウィンドウの完全な範囲内の位置のブロックがアドレス指定されると、データプロセッサは、第１の個数のラインからのデータ値がパラレルに受付される第１モードにスイッチする（「受け付ける」とは、例えば、パラレルな参照値と比較して、又はそうでない場合には、パラレルに処理されることを意味する）。当該ブロックがウィンドウの境界を超えて延伸したり、又はウィンドウの完全に範囲外にあるとき、プロセッサは１つのラインのみのデータ値をパラレルに受け付け、又は第２の個数のラインのみをパラレルに受け付ける第２モードにスイッチする。従って、高度な並列化がウィンドウ内の最も頻繁に出現するブロックについて実現され、より低いレベルの並列化が遠くにあるブロックについて実現される。
【００１４】
ある実施例では、高度な並列化を実現するため、中心のウィンドウからのデータを格納する所定のキャッシュ位置は、例えば、各々が異なるラインに対する複数のラインユニットセットとして、又は他のラインユニットのセットとインタリーブされるラインセットとして構成されるかもしれない。この実施例では、各ラインユニットは、あるラインのデータ値をパラレルに出力するための複数のメモリバンクを有するようにしてもよく、バンクの個数は、いくつかのデータ値をパラレルに出力するのに十分なものであって、アドレス指定されるブロックの幅Ｂｘのデータ値の個数以上である。さらなる実施例では、Ｗ個の連続するｘ−アドレスに対するデータ値が、あるラインセグメントからのデータ値が、Ｗ個の位置内に適合するラインセグメントの何れかのｘ−位置においてパラレルに読むことが可能となるように、上記バンク上に循環的に分散されるようにしてもよい。好ましくは、各メモリバンクの各メモリ位置は、連続するｘ−位置におけるＧ個のデータ値のグループを格納するよう構成され（例えば、Ｇ＝４など）、あるラインユニットのバンクの個数Ｓは、Ｓ＊Ｇが当該ブロックのラインセグメントの幅Ｂｘを超えるくらいに大きなものである。これは、Ｂｘのデータ値の指定されたラインセグメントの出力が、Ｂｘ／Ｇが整数である場合にはＢｘ／Ｇ個のメモリバンクを、そうでない場合には、Ｂｘ／Ｇを超える次に大きな整数個のメモリバンクを要求するように、グループ内のラインセグメントのスタートアドレスを指定することを可能にする。Ｓ＊Ｇ＞Ｂｘとなるように、ラインユニットにおいて十分大きなバンクの個数Ｓを使用することによって、十分なグループからのデータ値がメモリバンクから常にパラレルに出力することが可能となることが保証される。好ましくは、メモリバンクからのデータ値の後の選択が、アドレス指定されたブロックのみのラインセグメントに対するデータ値に出力を揃えさせる。このタイプのキャッシュメモリはまた、自ら、すなわち、他のタイプのキャッシュメモリとの組み合わせでなく、又は通常のメモリとして（キャッシュメモリでなく）利用されてもよい。このように、アクセスされた「ウィンドウ」（又は領域）がデータアレイにおいて移動する場合、ほとんど負担なく高いレベルの並列化を実現することが可能である。
【００１５】
その他のキャッシュ位置は、より低い並列化を可能にするよりシンプルな構成とされてもよい。しかしながらあるいは、画像メモリ又は画像キャッシュ全体が、このより複雑な構成を有するようにしてもよい。
【００１６】
本発明の上記及び他の課題及び効果が、以下の図面を用いて非限定的な具体例により説明される。
【発明の効果】
【００１７】
本発明によると、より効率的なキャッシュの使用をサポートする２次元アレイとして構成されるデータを処理する装置を提供することができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、画像処理装置を示す。
【図２】図２は、位置アレイの一部を示す。
【図３】図３は、キャッシュ要素を示す。
【図４】図４は、画像処理装置を示す。
【図５】図５は、キャッシュ要素を示す。
【図６】図６は、画像処理装置を示す。
【図６ａ】図６ａは、画像処理装置を示す。
【図７】図７は、メモリ構成を示す。
【発明を実施するための形態】
【００１９】
以下、図面に基づいて本発明の実施の形態を説明する。
図１は、処理ユニット１０と、メインメモリ１２と、キャッシュメモリユニット１４とを有する画像処理システムを示す。処理ユニット１０は、キャッシュメモリユニット１４に接続されるアドレス出力とデータ入力とを有する。キャッシュメモリユニット１４は、メインメモリ１２とのデータ及びアドレス接続を有する。動作について、処理ユニット１０は、画像処理演算、すなわち、ｘアドレス及びｙアドレスの組み合わせによりアドレス指定可能な画素データを利用する演算を実行する。処理ユニット１０は、このタイプの組み合わせを表すアドレスをキャッシュメモリユニット１４に供給し、キャッシュメモリユニット１４は、アドレス指定された画素データを返す。このアドレス指定された画素データがキャッシュメモリユニット１４に格納されると、キャッシュメモリユニット１４は、データを直接返す。そうでない場合には、キャッシュメモリユニット１４はまず、メインメモリ１２の画素データをフェッチする。
【００２０】
図２ａは、画像のある領域におけるブロックを示す。この領域は、ｘ方向に１０個のブロックとｙ方向に６個のブロックである。各ブロックは、例えば、８つの水平方向に連続する画素の８つの垂直方向に連続する行を含む。一実施例では、アドレス指定の単位はブロックである。本実施例では、アドレスは、ｘブロックアドレスとｙブロックアドレスの組み合わせを含みさえすればよい（例えば、ｘ画素アドレスとｙ画素アドレスから３つの最下位ビットを省略している）。
【００２１】
キャッシュメモリ１４は、各キャッシュ位置に対するいくつかのキャッシュ要素１４２と、キャッシュコントローラ１４０と、出力セレクタ１４４とを有する。各キャッシュ要素１４２は、ｘ−ｙ画素アドレスに係るｘ−ｙブロックに対する画素データ、又はキャッシュされているブロックのｘ−ｙブロックアドレスをキャッシュするよう構成される。経時的に、関連付けされたｘ−ｙアドレスが変更されるように、異なるブロックがキャッシュ要素１４２にキャッシュされる。処理ユニット１０がキャッシュ要素１４２の何れにも格納されていないブロックにおける画素又は画素ブロックをアドレス指定すると、キャッシュメモリユニット１４は、キャッシュ要素１４２の１つを選択し、当該キャッシュ要素１４２に格納されているブロックを新たにアドレス指定されたブロックと置換する（メインメモリ１２から当該新たにアドレス指定されたブロックをフェッチした後）。その後、キャッシュ要素１４２は、新たにフェッチされたブロックのｘ−ｙアドレスをキャッシュされたデータと関連付ける。
【００２２】
キャッシュコントローラ１４０は、本来的には、キャッシュ要素１４２を管理するプログラムと、キャッシュ要素１４２に格納されるブロックのｘｙ−アドレスを表すメモリを備えた小さなプロセッサとして実現可能である。キャッシュコントローラ１４０は、新たにフェッチされたブロックが格納されるキャッシュ要素１４２の選択を制御する。例えば、最も以前に使用されたキャッシュ要素のデータを置換するＬＲＵなどの何れかの選択アルゴリズムが利用されてもよい。しかしながら、キャッシュコントローラ１４０は、ｘ−ｙアドレスの２次元領域からｘ−ｙアドレスを有する画素ブロックを格納するキャッシュ要素１４２に特別な処理を与える。図２ａの斜線部分２０により示される当該領域は、ｘ方向とｙ方向のそれぞれに複数のブロック行及び列まで拡張される。この領域２０は、処理ユニット１０により選択され、処理ユニット１０が当該領域が移動すべきであると通知すると、当該領域を繰り返し右方向に移動する（当該領域の最も低いブロックのｘアドレスを増大させる）などの処理中に、定期的に更新される。
【００２３】
キャッシュコントローラ１４０は、領域２０からのブロックをキャッシュするキャッシュ要素１４２を通常の置換（すなわち、領域２０の移動することなく行われる置換）から免除する。キャッシュ要素１４２が領域２０を移動させることなく新たにアドレス指定されたブロックを格納するよう選択される必要があるとき、キャッシュコントローラ１４０は、免除されたキャッシュ要素１４２の何れも含まないキャッシュ要素１４２の一部から当該キャッシュ要素１４２を選択する。通常の置換中の免除は、例えば、キャッシュ置換中に免除される所定のキャッシュ要素１４２に領域２０からのブロックを格納することによって、又は、領域２０からのブロックを格納するキャッシュ要素１４２に対するロックフラグを設定することによって、又は領域２０のｘ−ｙアドレス境界と各キャッシュ要素１４２に係るｘ−ｙアドレスとを比較することによってなど何れか便利な方法により実現可能である。
【００２４】
処理ユニット１０がキャッシュコントローラ１４０に領域２０がある方向（所定の方向又は処理ユニット１０によって選択及び指示される方向）に移動しなければならないことを通知すると、キャッシュコントローラ１４０は、キャッシュ置換から免除されたブロックセットを変更する。所定のキャッシュ要素１４２が通常の置換中に免除される実施例では、この変更は、新しい領域には含まれるが、古い領域には含まれないブロックに対する画素データを、古い領域には含まれるが、新しい領域には含まれないキャッシュされているブロックのキャッシュ要素１４２に移動することによって実現される。例えば、水平方向の移動の場合、これは、同一のｘアドレスで異なるｙアドレスを有するブロックの列を格納するキャッシュ要素１４２に関係する。キャッシュ要素１４２がロックフラグにより通常の置換中に免除される実施例では、ロックフラグは、新しい領域に含まれるが、古い領域には含まれないブロックに対して設定され、古い領域に含まれるが、新しい領域には含まれないキャッシュブロックのキャッシュ要素１４２に対してクリアされる。この実施例では、関連するブロックがキャッシュ要素１４２にロードされると、フラグが設定されるかもしれない。
【００２５】
好ましくは、キャッシュコントローラ１４０は、領域２０が移動すると、領域２０に新たに含まれるブロックを予めフェッチするよう構成される。当該実施例では、当該領域が所定の方向に毎に、キャッシュコントローラ１４０は、領域の前の動きをトリガーする信号に応答して予めフェッチすることを開始するかもしれない。処理ユニット１０が方向を選択する実施例では、処理ユニット１０が好ましくはまず送信し、キャッシュコントローラ１４０が、好ましくは、まず、当該領域を移動するための信号の送信前に、予めのフェッチ処理をイネーブルにする方向信号を受信する。
【００２６】
図２ｂは、予めのフェッチ処理を示す。この図では、図２ａの領域２０を２ブロックの幅だけ右方向に移動することによって取得される斜線領域２２が示される。この場合、領域２２の１６個のブロックの内の８つが（当初の領域に属しないブロック）、予めフェッチされる必要がある。
【００２７】
所定のキャッシュ要素１４２が通常の置換中に置換を免除される実施例では、これら所定の免除されたキャッシュ要素１４２は、好ましくは、現在領域２０からのすべてのブロックを格納するのに十分なキャッシュ要素と、予めフェッチされたブロック、すなわち、図２ａの例の２４個のブロックを格納するための追加的なキャッシュ要素１４２を加えてものを有する。ロックフラグが使用される実施例では、キャッシュコントローラ１４０は、当該領域が移動される前に予めフェッチされたブロックをロックする。
【００２８】
好ましくは、キャッシュメモリユニット１４は、処理ユニット１０とパラレルにあるブロックからの複数の画素位置に対する画素値（好ましくは、当該ブロックのある行からのすべての画素値）を出力し、当該ブロックの他の連続する複数の画素（例えば、連続的な行など）を連続的に出力する。キャッシュ要素１４２は、好ましくは、キャッシュ要素１４２があるブロックからの画素データをキャッシュするとき、キャッシュ要素１４２が当該ブロックからのすべての画素値をキャッシュするように、その全体のブロックをキャッシュするよう構成される。この場合、１つのｘ−ｙブロックアドレスは、当該ブロックに対するすべての画素値をキャッシュするキャッシュ要素１４２を識別するのに利用されるかもしれない。１つのｘ−ｙブロックアドレスに応答して、キャッシュ要素１４２は、その後に、同じｘ−アドレスであって、連続する他のｙ−アドレスの画素値の出力に続いて、異なるｘ−アドレスと１つのｙ−アドレスに対する画素値を同時にパラレルに出力するかもしれない。
【００２９】
さらなる実施例では、処理ユニット１０は、マクロブロック、すなわち、ｎ＝ｍ＝２などによるｎ×ｍ個のブロックからなる矩形状などの複数のブロックを含むブロックを利用する。この実施例では、各ブロックをマクロブロックに格納するｎ個のキャッシュ要素１４２が、好ましくは、画素値をパラレルに出力するよう構成される。典型的には、マクロブロックは、領域２０又は免除されたブロックのサイズより小さい。例えば、４×４のブロック領域と、２×２のブロックマクロブロックが利用されてもよい。
【００３０】
図３は、このためのキャッシュ要素の実現形態の一例を示す。キャッシュ要素は、アドレスタグメモリ３０と、アドレス入力３１と、複数のアドレス比較器３２と、データメモリ３４とを有する。さらに、複数のキャッシュ要素により共有可能なラインカウンタ３６が示される。動作について、データメモリ３４は、あるブロックからの画素データを格納する。アドレスタグメモリは、そこからデータが格納されるブロックのｘ−ｙブロックアドレスを格納する処理ユニット１０（図示せず）は、あるマクロブロックのｘ−ｙアドレスをアドレス入力３１に適用する。比較器３２は、処理ユニット１０（図示せず）からのｘ−ｙアドレスとアドレスタグメモリ３０からのアドレスとを比較し、これにより、各比較器３２は、アドレスタグメモリ３０がアドレスマクロブロックに含まれるある行のブロックの各ブロックを含むかチェックする。すなわち、第１比較器は、アドレスタグメモリ３０からのアドレスＡ＝（Ａｘ，Ａｙ）が、処理ユニット１０からのマクロブロックのアドレスＢ＝（Ｂｘ，Ｂｙ）に等しいかチェックする。第２比較器は、ＡｘがＢｘ＋ｄとＡｙ＝Ｂｙに等しいか（ただし、ｄはブロックのｘの幅である）チェックする。あるマクロブロックがｎ×ｍ個のブロックを含むとき、ＡｘがＢｘ＋ｉ＊ｄに等しいかチェックするｎ個の比較器がある。ここでは、各比較器が、０からｎ−１までの各整数ｉの値についてチェックする。
【００３１】
比較器３２は、選択器１４４（図示せず）に接続される出力を有する。選択器１４４は、ｎ個のキャッシュ要素のデータメモリ３４からの画素データをパラレルに出力するよう構成される。選択器１４４は、このためにｎ個の出力を有する。各比較器３２は、各出力に対応し、比較器３２がアドレスの一致を検出する場合、対応する出力においてデータメモリ３４からのデータを選択器に出力させる。ラインカウンタ３６は、処理ユニット１０のアドレス指定処理により開始され、ｙ−アドレスをカウントアップする。ラインカウンタ３６は、これらｙ−アドレスをデータメモリ３４に供給し、マクロブロックアドレスに応答して、データメモリに選択器１４４を介し当該ブロックの連続するラインに対する画素データを連続的に処理ユニット１０に出力させる。
【００３２】
ｎ×ｍのマクロブロックの高さｍが１より大きい場合、ｙ−アドレスはカウント中にブロック境界とクロスする。この場合、ラインカウンタ３６はまた、好ましくは、ブロックのｙ−アドレスのサブマクロブロック部分を供給するため、比較器３２に接続される出力を有する。ラインアドレスがブロック境界をクロスするとき、異なるキャッシュ要素が選択され、垂直方向に連続するブロックからの画素データが選択器１４４を介し出力される。マクロブロック内の各ブロックのアドレス指定中、通常の置換を免除されているブロックから免除されていないブロックに、又はその反対のアドレス指定がクロスする可能性があるということが理解されるべきである。これは、同時にパラレルに出力される所与のｙアドレス値に対する画素データのライン内、又は１つのｙ−アドレス値の１つのラインから他のラインへの遷移中に行われるかもしれない。これは、マクロブロックに対するキャッシュミス又は部分的なキャッシュミスを引き起こすかもしれない。選択器１４４の出力に対応する比較器の何れもが応答しないとき、このことがキャッシュコントローラ１４０に通知される。これは、あるマクロブロック内のブロックがキャッシュメモリに存在しないことを示す。キャッシュコントローラ１４０は、メインメモリ１２から関連するブロックをフェッチし、キャッシュ要素１４２（免除されているマクロブロック内のブロックを格納するキャッシュ要素）を選択し、当該ブロックの画素データを選択されたキャッシュ要素１４２のデータメモリ３４に、そしてそれのｘ−ｙブロックアドレスを当該キャッシュ要素１４２のアドレスタグメモリ３０に書き込むことによって応答する。必要に応じて、キャッシュコントローラ１４０は、このようにして複数のブロックをフェッチする。キャッシュコントローラ１４０は、処理ユニット１０にすべての必要なブロックが利用可能になるまで待機させる。
【００３３】
予めのフェッチ処理が、免除された領域２０のロックされたブロックについて用いられる場合、当該ブロックにはキャッシュミスは発生しない。しかしながら、マクロブロックが当該領域からのブロックを含む場合であっても、マクロブロックが領域２０の境界を超える場合、キャッシュミスが発生するかもしれない。
【００３４】
さらなる実施例では、キャッシュコントローラは、アドレス指定されたマクロブロック内のより大きなｙアドレスに対するブロックがキャッシュ要素において利用可能であるか予めチェックするよう構成される。そうでない場合、より小さいｙ−アドレスのブロックからの画素データが処理ユニット１０に出力されている間、キャッシュコントローラ１４０は任意的に上記ブロックを予めフェッチする。
【００３５】
効果的には、通常の置換を免除されるブロックが連続しているという知識が利用される（当該領域外のキャッシュされているブロックは、連続している必要はない）。一実施例では、所定のキャッシュ要素１４２のセットが、領域２０からのブロックを格納するのに利用される。
【００３６】
図４は、アクティブ領域のブロックに対するコアキャッシュ４０と、当該領域外のブロックに対する周辺キャッシュ４２の２つのキャッシュメモリ４０と４２がこのために利用される実施例を示す。アクティブ領域２０からのブロックがシステマティックにコアキャッシュ４０に維持されることが保証されているため、それらはまたシステマティックに格納されてもよい。この結果、コアキャッシュ４０の構成を簡単化することができる。アクティブ領域２０のブロック列毎に１つのキャッシュ要素で十分である。すなわち、連続するｙ値によるブロックに対する個々のキャッシュ要素は必要でない。当該領域がｈの高さのブロックである場合、コアキャッシュ４０のキャッシュ要素のデータメモリ３４は、コアキャッシュ４０内の各ｙ−アドレスに対してｈ倍以下の画素値のラインしか有しない。このことは、より少ないアドレス比較器で十分であることを意味する。
【００３７】
図５は、このためのキャッシュ要素を示す。本実施例では、アドレス入力は、１つのライン内のブロックを選択するため、処理ユニット１０からのｙ−アドレスのブロックアドレス部分の一部をデータメモリ３４へのアドレスとして適用するための部分５０を有する。好ましくは、領域２０からの各ラインが、それのｙアドレスのデータメモリのライン数の法（ｍｏｄｕｌｏ）の最下位の剰余に対応するデータメモリのｙアドレスに格納される。すなわち、領域２０の位置に応じて、当該領域の先頭に関する所与のｙ−オフセットにあるラインが、常にそれらの絶対ｙ−アドレスに従って異なるメモリ位置に格納されるかもしれない。
【００３８】
アドレス比較の回数は、領域２０からのブロック列のキャッシュ要素１４２への所定の循環的割当てを利用することによって、さらに減らすことができる。この場合、１回のみの比較（マクロブロックが領域と重複しているか検出するため）と減算（当該ブロックのｘアドレスを循環的割当てにおけるある列のキャッシュ要素のアドレスに変換するため）が、コアキャッシュ４０のキャッシュ要素の何れがブロックをアドレス指定するのに利用されるべきか判断するのに必要とされる。
【００３９】
上述されたように、別個のコアキャッシュ４０と周辺キャッシュ４２の利用は、新たな領域からのブロックが、処理ユニット１０が当該領域を移動するよう通知した後、コアキャッシュ４０に存在する必要があることを意味する。これらのブロックは、可能な限り周辺キャッシュ４２からコピーされてもよいが、好ましくは、当該ブロックが周辺キャッシュ４２に存在するか否かに関係なく、コアキャッシュ４０に存在しない新たな領域からのすべてのブロックがメインメモリ１２からフェッチされる。好ましくは、これらのブロックが予めフェッチされる。この場合、キャッシュ管理ユニット１４０は、次の領域２２がどのようなものとなるか予測し、あるいは、処理ユニット１０は、新たな領域への移動を実際に通知する前に、新たな領域２２がどのようなものになるか予め通知する。所定のステップだけ水平方向にスライドする領域の場合、この予測はシンプルであるが、もちろん、より複雑な移動パターンが使用されてもよい。
【００４０】
図６は、プリフェッチバッファ６０がコアキャッシュ４０とメインメモリ１２との間に（キャッシュコントローラ１４０を介し）も受けられる実施例を示す。本実施例では、キャッシュコントローラは、メインメモリ１２から予測された以降の領域２２の新たなブロックを予めフェッチし、これらのブロックをプリフェッチバッファ６０に格納するよう構成される。処理ユニット１０からウィンドウを移動するための信号を受信すると、キャッシュコントローラ１４０は、予めフェッチされたブロックをプリフェッチバッファ６０からコアキャッシュ４０の選択されたキャッシュ位置にコピーさせる。本実施例は、予めのフェッチ処理が通常のキャッシュ処理との干渉を引き起こさないという効果を有する。
【００４１】
他の実施例では、領域２０について厳密に必要なものより多くのキャッシュ位置が、コアキャッシュ４０に設けられる。本実施例では、以降の領域２２の新たなブロックが、現在領域２０については使用されないキャッシュ位置に直接的に予めフェッチされる。ある実施例では、キャッシュコントローラ１４０は、これらのブロックがコアキャッシュの残りから予めフェッチされるキャッシュ要素を分離し、これにより、当該キャッシュ要素への書き込みは、メイン処理ユニット１０による読み出しとは独立に進行することが可能である。
【００４２】
予めフェッチが行われないとき、周辺キャッシュ４２にある新たな領域２０からのこれらのブロックは、好ましくは、コアキャッシュ４０に移動され、任意的にはそれらがメイン処理ユニット１０によりアドレス指定されるときに限って、その他のブロックがメインメモリ１２からフェッチされる。
【００４３】
ある実施例では、コアキャッシュ４０と周辺キャッシュ４２は、位置のブロックに対するデータ値の出力中、異なるレベルの並列化をサポートするよう構成されるかもしれない。
【００４４】
図６ａは、コアキャッシュ４０がブロックの異なるｙ−アドレスを有する複数のラインセグメントに対するデータ値をパラレルに出力するよう構成されるこのタイプの実施例の一例を示す。対照的に、周辺キャッシュ４２は、１つのラインセグメントが一度にアドレス指定されることを可能にするキャッシュ要素を含む。コアキャッシュ４０は、パラレルにデータ処理ユニット１０に接続される第１出力を有する。コアキャッシュ４０と周辺キャッシュ４２の組み合わせがまた、処理ユニット１０に接続される。
【００４５】
動作について、領域２０の内部に完全にあるブロックがアドレス指定されると、コアキャッシュは、当該ブロックのライン上の位置に対するデータ値を処理ユニットにパラレルに出力する。領域２０の境界を超えて延長するブロック、又は当該領域２０の外部にあるブロックがアドレス指定されると、データ処理ユニット１０は、データ処理ユニットが当該ブロックからの１つのラインの位置に対するものであって、少なくとも部分的に周辺キャッシュ４２からのデータ値を一度に受け付けるモードにスイッチする（ここで使用される受付とは、データ値と参照値のパラレルな比較や他の処理演算のパラレルな実行などに関するものである）。これは、大部分の時間において発生する、コアキャッシュ４０内のブロックがアドレス指定されるとき、高速のパラレル処理が利用可能であるという効果を有する。周辺ブロックがアドレス指定されると、低速モードが利用される。ブロックアドレスとキャッシュされた領域２０との比較の結果として、又は遠くの動きベクトルが検討される場合の動きベクトルの検索中など、処理ユニット１０により内部的に、モード切替がアドレッシングユニット（図７）によりトリガーすることが可能である。
【００４６】
画像処理中、当該ブロックが領域２０の内部にあるとき、処理ユニット１０は画素ブロック単位によりデータ値を読み込む。各画素ブロックは複数のラインセグメントを有し、連続するラインセグメントは、「Ｂｙ」個の連続するｙ−アドレスを有し、各ラインセグメントは連続するｘ−アドレスを有する「Ｂｘ」個の位置を有する。処理を高速化するため、アドレス指定されたブロックからの複数の位置に対するデータ値を処理ユニット１０にパラレルに出力するため、好ましくは、画像メモリ１４が構成される。好ましくは、画像メモリが、連続するｙアドレスを有する複数のラインセグメントの位置からのすべてのデータ値をパラレルに出力するよう構成される。これは、大量のパラレルアクセスを意味する。例えば、１６×１６の位置ブロックが使用され、４つのラインがパラレルに出力される必要がある場合、６４のデータ値がパラレルに出力される必要がある。
【００４７】
図７は、この大量並列化をサポートするメモリ構成を示す。メモリは、アドレッシングユニット７０と、複数のラインユニット７２と、出力スイッチ７４とを有する。アドレッシングユニット７０は、処理ユニット１０（図示せず）に接続されるアドレス入力７１を有する。出力スイッチ７４は、それぞれが画像の画素ブロックのラインセグメントに対応する位置からのＢｘのデータ値のパラレルな出力のための複数のラインセグメント出力７６を有する。各ラインユニット７２（１つのみがより詳細に示される）は、複数のメモリバンク７２０とバンクスイッチ７２２とを有する。バンク７２０は、アドレッシングユニット７０に接続されるアドレス入力を有する。バンクスイッチ７２２は、メモリバンク７２０のデータ出力に接続されるデータ入力と、アドレッシングユニット７０に接続される制御入力とを有する。出力スイッチ７４は、ラインユニット７２のバンクスイッチ７２２のデータ出力に接続されるデータ入力と、アドレッシング回路７０に接続される制御入力とを有する。
【００４８】
各メモリバンク７２０は、複数のアドレス指定可能な位置を有し、各位置は、画像の異なる画素位置に対する複数のＧ個のデータ値（Ｇ＝４など、Ｇ＞１）を格納するよう構成される。各ラインユニット７２は複数のＳ個のバンク（Ｓ＞１）を有し、これにより、これらのバンクは一緒になって、異なる画素に対するＧ＊Ｓ個のデータ値を出力する。ラインスイッチ７２２が、アドレッシング回路の制御の下、メモリバンク７２０からのＧ＊Ｓのデータ値から選択されたＢｘ（Ｂｘ＝あるラインセグメントの画素位置数）個のデータ値（Ｂｘ＜Ｇ＊Ｓ）を出力するよう構成される。出力スイッチ７４は、ラインスイッチ７２２からのデータ値をラインセグメント出力７６に出力するよう構成され、アドレッシングユニット７０は、何れのラインスイッチ７２２が何れのラインセグメント出力７６に接続されるか制御する。ラインユニット７２はＮ個ある（Ｎ＝４など）。典型的には、ラインユニットの個数Ｎは、セグメント出力７６の個数に等しい。
【００４９】
処理中、キャッシュコントローラ１４０は、ラインユニット７２のメモリバンク７２０にデータ値を書き込むか、あるいは、アドレッシングユニット７０がこのためにキャッシュ管理ユニットとして利用される。書き込みは、初期的に、又は領域２０の位置が変更されると行われる。この場合、キャッシュ管理ユニットとして動作するアドレッシングユニット７０は、メインメモリ１２からデータ値をフェッチし、フェッチされたデータ値をメモリバンク７２０の選択されたアドレスと共に、選択されたラインユニット７２の選択されたメモリバンク７２０に適用する。
【００５０】
キャッシュコントローラ１４０又はアドレッシングユニット７０によるキャッシュ管理は、各ラインユニット７２がそれのメモリバンク７２０に格納され、各ｙ−アドレス又はｙ−アドレスセットを有する位置に対するデータ値は、当該ラインユニット７２に一意的であり、いくつかの連続するｙ−アドレスに対するデータ値がラインユニットの組み合わせに格納されるように構成される。すなわち、例えば、第１ラインユニット７２は、ｙアドレスがｙとなる位置に対するデータ値を格納し、第２ラインユニット７２は、ｙアドレスがｙ＋１となる位置に対するデータ値を格納するなどである。各ラインユニットがｙ−アドレスセットに対するデータ値を格納する場合、当該セットは、あるセット内のｙの値の間の距離が各セットに対して同一となり、ラインユニット７２の個数Ｎの整数倍に等しくなるようにインタリーブされる。例えば、第１ラインユニット７２は、ｙアドレスがｙ、ｙ＋Ｎ、ｙ＋２Ｎ等となる位置に対するデータ値を格納し、第２ラインユニット７２は、ｙ−アドレスがｙ＋１、ｙ＋Ｎ＋１、ｙ＋２Ｎ＋１等となる位置に対するデータ値を格納するなどである。
【００５１】
各ｙ−アドレスについて、ラインユニット７２は、「ｗ」個の連続するｘ−アドレスによる複数の位置に対するデータ値を格納する。ただし、連続するｘアドレスの個数ｗは、画素ブロックのラインセグメントサイズＢｘを超え（ｗ＞Ｂｘ）、またラインユニット７２のバンクがパラレルに出力可能な個数Ｇ＊Ｓを超える（ｗ＞Ｇ＊Ｓ）。テーブルＩは、異なるｘ−アドレスを有するデータ値のラインユニット７２のメモリバンク７２０への割当ての一例を示す。この例では、ラインユニット７２のメモリバンク７２０の個数Ｓは５とされ（Ｓ＝５）、メモリバンク７２０の各位置のデータ値の個数Ｇは４とされる（Ｇ＝４）。データ値が格納された連続するｘ−アドレスの個数ｗは、本例では３２とされる（ｗ＝３２）。テーブルの各列は、メモリバンク７２０に対応する。テーブルの各フィールド（第１行のフィールドを除いて）は、当該フィールドの列に対応するメモリバンクの１つのメモリ位置に格納されているｘ−アドレスを表す。
【００５２】
【表１】
ｘ−アドレスの割当ては静的なものではない。処理ユニット１０が処理中に画像のあるラインに沿って右方向に進捗すると、以前のアドレスの右側に新たなｘ−アドレスに対するデータ値がロードされ、左側のデータ値を以前に格納したバンクに格納される。テーブルＩＩは、異なるｘ−アドレスを有するデータ値のメモリバンク７２０への割当てが経時的にどのように進化するかの一例を示す。
【００５３】
【表２】
バンク０の１つのメモリ位置に対するデータ値（当初は、ｘ−アドレスｘ、ｘ＋１、ｘ＋２、ｘ＋３に対する）が、新たなｘ−アドレス（ｘ−アドレスｘ＋３２、ｘ＋３３、ｘ＋３４、ｘ＋３５）、すなわち、当初のｘアドレスよりｗ（ｗ＝３２など）だけ大きなｘ−アドレスに対するデータ値と置換されたことに留意すべきである。同様のことがバンク１の１つのメモリ位置についてなされるが、その他のバンクは不変とされる。処理がラインに沿って進められると、データ値がバンク２と３において置換され、その後にバンク４と０などのように循環的に行われる。データ値が占有するバンクのメモリ位置は常に同一に維持されるが、格納されているデータ値の画素位置のアドレスは変更される。
【００５４】
テーブルＩＩＩは、複数のｙ−アドレスのセットが各メモリバンク７２０に格納される実施例を示す。
【００５５】
【表３】
バンク０は、ｙアドレスｙ、ｙ＋Ｎ、ｙ＋２Ｎなどに対するデータ値を格納することに留意すべきである。バンク１は、ｙ−アドレスｙ＋１、ｙ＋Ｎ＋１、ｙ＋２Ｎ＋１などに対するデータ値を格納する。各ｙ−アドレスに対して、連続する異なるｘ−アドレスに対するデータ値が、前述の表に示されるように、メモリバンク７２０に循環的に分散される。
【００５６】
テーブルＩとＩＩの場合と同様に、メモリ位置のデータ値のアドレスは静的ではない。このことは、テーブルＩＶに示されている。
【００５７】
【表４】
本実施例では、所与のｙ−アドレスを有するデータ値に対して用いられる位置セットは、同じままであり、あるｘ−アドレスとｙアドレスを有する位置に対する各データ値は、同一のｙ−アドレスとｘアドレスｘ−ｗを有するデータ値を置換する。さらに、テーブルＩＩＩ及びＩＶの実施例に示されるように、異なるＹアドレスを有する位置に対するデータ値のセットの間にはギャップはない。本実施例のメモリバンク７２０では、ｘｙアドレスｘ，ｙ＋Ｎを有する位置に対するデータ値が、多数のｘアドレスに対するデータ値がメモリバンク７２０に同時に存在する場合、ｘｙアドレスｘ＋ｗ，ｙを有する位置に対するデータ値により占有される位置に格納される。
【００５８】
この格納スキームは、大量のパラレルアクセスと画素位置のウィンドウに対するデータ値の回転する置換の組み合わせを容易にするよう構成される。ウィンドウが移動すると、ウィンドウの外側の画素位置に対するデータ値は、ウィンドウの内側の画素位置に対するデータ値により置換される。
【００５９】
アドレッシングユニット７０は、画像内の画素位置のブロックからのデータ値が、処理ユニット１０（図示せず）にパラレルに出力されることを保証する。ブロックのｘｙ−アドレスを受け取ると、アドレッシングユニット７０は、当該ブロックのラインセグメントに対するデータ値が、異なるメモリバンク７２０から読み込まれるメモリバンク内アドレスを計算する。アドレッシングユニット７０は、これらのアドレスをメモリバンク７２０に適用する。さらに、アドレッシングユニット７０は、メモリバンク７２０の何れがブロックなのラインセグメントの何れの位置からのデータ値を格納するか計算する。アドレッシングユニット７０は、ラインスイッチの出力の各部分が、受け付けた当該ブロックのｘｙ−アドレスに対して、各自の所定のｘ−オフセットにおける位置に対するデータ値を出力することを保証するため、対応する制御信号をラインスイッチ７２２に供給する。最終的に、アドレッシングユニット７０は、何れのラインユニット７２が何れのラインセグメントを出力するか計算する。アドレッシングユニット７０は、各セグメント出力７６が受け付けたブロックのｘｙ−アドレスに対して、各自の所定のｙ−オフセットにおけるラインセグメントに対するデータ値を出力することを保証するため、対応する制御信号を出力スイッチ７４に供給する。
【００６０】
アドレス指定の実施例のより詳細な具体例が説明される。本例では、アドレッシングユニット７０に供給されるｘｙ−アドレスは、Ａｘ Ａｙにより示される。ここで、Ａｘはｘ−アドレス部分であり、Ａｙはｙ−アドレス部分である。本実施例では、ウィンドウコーナーアドレスＷｘ、Ｗｙからスタートし、水平方向にｗ個の画素位置だけ連続する画素位置のウィンドウに対するデータ値を格納する。アドレッシングユニット７０は、ウィンドウのコーナーアドレスのデータ値が格納されるメモリバンク７２０のメモリ位置ＭとバンクＢを示すオフセットカウンタ値Ｂ，Ｍを維持する。さらに、アドレッシングユニットは、ウィンドウの連続するラインの最も左の位置からのデータ値を格納するメモリバンク７２０のメモリ位置のアドレスＺ間のオフセットであるＤに関する情報を表す（ここで、Ｚは複合アドレスＺ＝ｑ＋ｒ＊Ｓであり、ｑはメモリ位置を含むメモリバンク７２０のシーケンス番号であり、ｒは当該バンクのアドレスである）。テーブルＩＩとＩＶの例では、Ｄ＝８となる。
【００６１】
この情報から、アドレッシングユニット２０は、（ａ）アドレス指定されたブロックの左上のコーナーに対するデータ値が格納されるメモリバンク７２０のメモリ位置内の位置Ｉと、（ｂ）アドレス指定されたブロックの左上のコーナーに対するデータ値が格納されるバンクのシーケンス番号Ｃと、（ｃ）アドレス指定されたブロックの左上のコーナーに対するデータ値が格納されるメモリバンク７２０内のアドレスＲとを計算する。Ｉ、Ｃ及びＲは、アドレス指定されたブロックの左上のコーナーに対するデータ値が格納されるメモリバンク７２０内のアドレスとメモリバンク７２０を示す位置の値Ｐに関して表すことが可能である。
【００６２】
Ｐ＝Ｂ＋Ａｘ−Ｗｘ＋Ｄ＊（Ａｙ−Ｗｙ）
位置の値Ｐは、
Ｉ＝Ｐ ｍｏｄ Ｇ
に従って、メモリバンク７２０のメモリ位置内の位置Ｉを規定するのに利用可能である。（ここで、「ｍｏｄ」は、モジュロ（法）関数を示し、すなわち、Ｇで除した後のＰの剰余である。）同様に、メモリバンク７２０のシーケンス番号Ｃは、
Ｃ＝［（Ｐ−Ｉ）／Ｇ］ｍｏｄ Ｓ
に従って規定することができる。
【００６３】
メモリバンク７２０内のアドレスＲは、
Ｒ＝［（Ｐ−Ｃ＊Ｇ−Ｉ）／（Ｓ＊Ｇ）］
に従って規定することができる。
【００６４】
アドレッシングユニット７０は、この情報を以下のように利用する。各ラインユニット７２において、アドレッシングユニットは、通常、Ｃ以上のシーケンス番号を有するメモリバンク７２０をアドレスＲによりアドレス指定し、（存在する場合）Ｃ未満のシーケンス番号を有するメモリバンクをアドレスＲ＋１によりアドレス指定する。アドレッシングユニットは、入力から出力までデータ値の割当てをＧ＊Ｃ＋Ｉだけ回転するようラインスイッチ７２２を制御する。すなわち、出力にシーケンス番号ｊ＝０，１，．．．，Ｂｘ−１が割り当てられる場合、ラインスイッチ７２２は、シーケンス番号ｊによるそれの出力に、
Ｋ＝（Ｉ＋ｊ）ｍｏｄ Ｇ
に従ってメモリバンク７２０内の位置Ｋからのデータ値を出力させる。メモリバンク７２０は、
Ｌ＝（Ｉ＋ｊ−Ｋ）／Ｇ
に従ってシーケンス番号Ｌによりデータ値が選択されるメモリバンクである。
【００６５】
最後に、アドレッシングユニット７０は、何れのラインユニット７２が何れのラインセグメント出力７６に接続されるか判断するため、出力スイッチ７４を制御する。ラインセグメント出力７６にシーケンス番号ｉ＝０，１，．．．，Ｎ−１が割り当てられ、ラインユニット７２にシーケンス番号ｉ’＝０，．．．，Ｎ−１が割り当てられる場合、出力スイッチ７２２は、シーケンス番号ｉを有するそれのラインセグメント出力に、
ｉ’＝［ｉ＋Ａｙ−Ｗｙ］ｍｏｄ Ｎ
に従ってシーケンス番号ｉ’を有するラインユニット７２からのラインセグメントを出力させる。
【００６６】
Ｎ個のセグメント出力７６が、少なくとも垂直ブロックサイズＢｙに等しい場合（Ｎ≧Ｂｙ）、位置ブロックのすべてのデータ値がパラレルに出力される。垂直ブロックサイズがより大きい場合（Ｂｙ＞Ｎ）、いくつかの連続する時間サイクルが当該ブロックの連続する部分に対するデータ値を連続的に出力するのに必要とされる。この場合、アドレッシングユニット７０は、連続するサブブロックから読み出し、Ｎ＊Ｂｘ個の位置のサブブロックを効果的に出力し、連続するサブブロックがｘｙ−アドレス（Ａｘ，Ａｙ）、（Ａｘ，Ａｙ＋Ｎ），（Ａｘ，Ａｙ＋２Ｎ）などにおいてスタートすることにより、あるアドレスに応答する。
【００６７】
ここまで、メモリの構成が、ブロックアドレスに応答して画像内の画素位置の２次元ブロックから大量のデータ値をパラレルに出力し、同時にウィンドウがスライドするとき、データ値の過剰なロード処理なしに画素位置のスライドするウィンドウからのデータ値の格納を受け入れることを可能にする。このブロックアドレスは、何れかの画素位置に配置することが可能である。
【００６８】
データ値がパラレルに出力されるラインセグメントと少なくとも同程度のラインユニット７２（Ｎ個のラインユニット）が存在することに留意することが重要である。この結果、異なるｙ−アドレスを有するＮ個のラインセグメントからのデータ値は、パラレルに出力されるかもしれない。
【００６９】
各ラインユニットは、パラレルに出力されるラインセグメントからのデータ値の個数を出力するのに厳密に必要なものより、少なくとも１だけ多いメモリバンク７２０を有する（（Ｓ＋１）＊Ｇ≧Ｂｘ）。これは、メモリバンク７２０の各メモリ位置のデータ値の個数Ｇの整数倍となるｘ−アドレスを有する位置だけでなく、任意の画素位置においてラインセグメントをスタートさせることを可能にする。ラインセグメントのスタートｘ−アドレスがこのような整数倍である場合、これらのメモリバンク７２０のＢｘ／Ｇのみがラインユニット７２において読み出されるだけでよく、しかしながら、アドレスが揃っていない場合、１＋Ｂｘ／Ｇ個のメモリバンク７２０がラインユニット７２において読み出される必要がある。これらのメモリバンク７２０の２つからのデータ値のみが、部分的に処理ユニット１０に出力される。
【００７０】
各ラインユニット７２は、好ましくは、Ｎ（ラインユニット７２の個数）アドレスだけ離れたｙ−アドレスの自らのラインセットからのデータ値を格納する。連続するラインユニットは、連続する中間のラインからのデータ値を格納する。これは、固定されたｙ−アドレス値又はいあるベース距離の倍数だけでなく、任意のｙ−アドレス値Ｗｙを有するブロックを抽出することを可能にする。
【００７１】
画像メモリの実施例が説明されたが、多数の代替が可能であるということに留意すべきである。例えば、一実施例では、メモリバンクの異なるラインセグメントに対するデータ値の間にギャップが存在するかもしれない。言い換えると、本例ではオフセットＤは、データ値が格納されているウィンドウのｘ−アドレスの個数ｗに等しくされているが、いくつかの実施例では、Ｄ＞ｗとなってもよい。他の例として、異なるｙ−アドレスのラインセグメントが、メモリバンク７２０の任意の位置に格納されてもよく、何れかのアドレス変換機構（キャッシュメモリにおいて使用されるタイプのものなど）が、所望の位置をアドレス指定するのに利用される。
【００７２】
他の例として、本実施例では、データ値がパラレルに出力される各ラインセグメントの位置の個数Ｍが、水平方向のブロックサイズＢｘに等しくされるが、他の実施例では、この数Ｍは、Ｂｘ（（Ｓ＋１）＊Ｇ≧Ｍ）より小さくてもよく、ブロックのラインセグメントの一部のみがパラレルに出力されるということが理解されるであろう。この場合、より少ない個数Ｓのバンクは、各ラインユニット７２において利用されてもよいが、もちろん、複数のラインセグメント部分が、処理ユニット１０がブロック全体からのデータ値を必要とする場合には、連続的に出力される必要がある。
【００７３】
さらなる他の例として、ラインＳ’ユニット７２のグループが同じアドレス値について使用されてもよく、それぞれが、連続するセグメントがより大きなセグメントを一緒になって構成するように、連続するｘ−アドレスのセグメントに対するデータ値を格納する。このような実施例の構成は、図７の構成と類似している。相違点は、ラインユニットのメモリバンク７２０がグループに構成され、バンクシーケンス番号が各グループにおいて包み込んでいるということである。この場合、さらなる出力スイッチが、異なるグループからの各位置にわたるラインセグメントに対するデータ値を構成するよう追加されてもよい。テーブルＶは、このことを示す。
【００７４】
【表５】
簡単化のため、小さなグループと少数のグループが使用されたが、実際には、より多くのより大きなグループが利用可能であるということは理解されるであろう。本実施例では、ラインスイッチ７２２は、２つのグループからブロックアドレスに応じてグループ上に拡がるｘ−アドレスの範囲を有する位置に拡がるラインセグメントになど、様々なグループからのデータ値を合成するよう構成される。
【００７５】
あるいは、これは、図７に示されるような複数のメモリユニットをパラレルに設け、出力スイッチ７４と処理ユニット１０との間にさらなるスイッチを挿入することによって実現されるかもしれない。本実施例では、各メモリユニットは、ある範囲のｘ−アドレス（範囲（ｘ．．ｘ＋ｗ−１），（ｘ＋ｗ．．ｘ＋２ｗ−１），．．．など）に対するデータ値を格納する。さらなるスイッチは、異なるメモリユニットからのデータ値を異なるメモリユニットの出力からの連続するｘ−アドレスのラインセグメントに対するデータ値に合成する。
【００７６】
さらに、異なるｘ−アドレスとある特定のｙ−アドレスを有する位置に対するデータ値がメモリバンク７２０の同一のメモリ位置のセットを占有し続ける実施例が説明されたが、他の実施例では、異なるｙ−アドレスに対するメモリ位置が循環するようにしてもよい。これは、テーブルＩＩＩから進化したものであるが、テーブルＩＶと比較して異なるアドレス指定スキームによるテーブルＶＩに示される。
【００７７】
【表６】
テーブルＩＩＩと比較することによりわかるように、最終ラインセグメントの新たなｘ−アドレスに対するデータ値が（ｙ−アドレスｙ＋ＨからＨ個の下方のライン）、ここで最初の２つのメモリバンクの第１メモリ位置に格納される。第１ラインセグメント（ｙ−アドレスｙ）の新たなｘ−アドレスに対するデータ値が、次のライン（ｙ−アドレスｙ＋１）などの古いｘ−アドレスについて使用された位置に格納される。
【００７８】
本実施例では、アドレスブロックの第１のｘ−アドレスを含むバンクのシーケンス番号とバンク内の位置のアドレスを計算するための異なる方法が必要とされる。
【００７９】
さらに、本例は正のｘ−方向への８つの画素位置のステップによるウィンドウの移動について説明されたが、任意のサイズ及び任意の方向の移動が利用されてもよいということは理解されるであろう。例えば、正のｘ−方向へのより大きなステップ又はより小さなステップは、単により多く又はより少ないメモリバンク７２０にデータ値を上書きすることを要求するにすぎない。負のｘ方向へのステップは、テーブルＶＩに示されるように、最後の位置に対するデータ値の置換を要求する。
【００８０】
【表７】
ｙ方向へのウィンドウの移動ステップは、古いｙ−アドレスに対するデータの置換を伴う。正のｙ方向への１ラインのステップの場合、これは、最も小さなｙの値に対するデータ値を格納する１つのラインユニット７２のメモリバンク７２０におけるデータ値との置換を伴う。
【００８１】
テーブルＶＩＩＩは、ｙ方向の移動の例に対するこのタイプの置換を示す。本例では、まずＨは、メモリバンクに格納されるウィンドウのライン数である。
【００８２】
【表８】
より大きなステップについては、古いｙ−アドレスに対するデータ値が、より多くのラインユニット７２において置換される。可能な移動ステップは、ｘとｙ方向へのステップに限定されるものではない。斜めのステップが、ｘとｙステップの組み合わせとして実現可能である。
【００８３】
これらのデータ値は、典型的には、画像全体を格納するメインメモリ１２（図示せず）からフェッチされる。このため、ラインユニットには、ラインユニットに格納される必要のあるラインセグメントのアドレスに与えられる関連するデータ値をフェッチするためのメインメモリとの接続が設けられるかもしれない。ある実施例では、メインメモリはまた、各々がＮラインだけ離れた各ｙ−アドレスセットに対するラインを格納する複数のユニットに構成される。この場合、各ラインユニット７２は、メインメモリの各ユニットに接続されるかもしれない。
【００８４】
図７の画像メモリは、様々な方法により図１のキャッシュ構成と組み合わされるかもしれないということが理解されるべきである。最もシンプルな実現形態では、図７のメモリユニットが、図７に示されるタイプである必要はないが、領域２０のコアキャッシュ及び領域２０を包囲する位置に対する任意のタイプの周辺キャッシュメモリとして利用される。この周辺キャッシュメモリが複数のラインセグメントに対するデータ値をパラレルに出力することができないタイプのものである場合、コアキャッシュのパフォーマンスは、アドレスブロックがコアキャッシュと周辺キャッシュの両方の位置に拡がる場合、コアキャッシュから１回に１つのラインを利用することによって、単に劣化される。
【００８５】
他の実施例では、バンク内のアドレスは、適応可能なｘ及び／又はｙアドレスと関連付けされるかもしれない。本実施例では、メモリユニット（アドレッシングユニット７０又はメモリバンク７２０など）は、受け付けた各アドレスを利用して、何れかの関連付けされたアドレスにおいて、当該アドレスに対するデータ値がメモリバンク７２０に格納されるかチェックする。ミスの場合、データ値はメインメモリ１２からフェッチされ、そうでない場合には、データ値は関連付けされたアドレスからフェッチされる。これは、例えば、異なるラインユニット７２に対して独立に、又は同じラインユニット７２の中の異なるメモリバンク７２０に対して独立に、データのｙ−アドレス部分にのみ適用されてもよい。この場合、ラインユニット７２に格納されているラインセグメントのｙ−アドレス間より大きなギャップが存在するかもしれないということに留意すべきである。典型的には、このギャップはＮの整数倍であるが、他のギャップもまた利用可能である。このタイプのキャッシュ処理は、メモリバンク７２０の異なる位置が異なるラインセグメント（ｘ−アドレスの異なる範囲）に対するデータ値を格納するようｘ−アドレスに適用されてもよい。
【００８６】
他の実施例では、図７に示されるようないくつかのメモリ構成がキャッシュ要素としてパラレルに利用され、その後、さらなる出力スイッチが、メモリ構成のそれぞれからの信号からのラインセグメントを結合する。本実施例では、メモリ構成は、キャッシュメモリに対する従来のアソシエイティブマッピング（ａｓｓｏｃｉａｔｉｖｅ ｍａｐｐｉｎｇ）技術を利用して、画像内の各サブウィンドウと関連付けされてもよい。あるブロックがアドレス指定されると、関連するデータを格納するこれらのメモリ構成が起動され、当該ブロックに対するデータ値が、起動されたメモリ構成からパラレルに出力される。
【００８７】
これら複数のメモリ構成にないデータ値を有するブロックがアドレス指定されると、ミスしたデータ値がメインメモリ１２からフェッチされ、これらの構成の１つに格納され、以前のデータ値を置換する。本実施例では、アクティブ領域２０からのデータ値を格納する選択されたメモリ構成が、好ましくは、置換から免除される。
【００８８】
他の実施例では、図１のすべてのキャッシュ要素が、各ラインユニット７２として実現される。本実施例のラインユニットでは、テーブルＶに示されるタイプのデータ値分散スキームが利用可能であり、ラインユニット７２には、共通のラインスイッチ７２２に接続されるそれらの出力を有するラインユニットのグループにアソシエイティブに割り当てされるかもしれない。好ましくは、ラインユニット７２の第１のサブセットが、アクティブ領域２０に対するすべてのデータ値を格納し、ラインユニット７２の第２のサブセットが、アクティブ領域２０の周囲の選択されたサブウィンドウに対するデータ値を格納する。第２のサブセットのサブウィンドウのアドレスは、図１に関して説明されるように置換が行われる。この結果、異なるラインユニットに格納されるサブウィンドウは、所定の空間的関係を有しない。
【符号の説明】
【００８９】
１０ 処理ユニット
１２ メインメモリ
１４ キャッシュメモリユニット
１４０ キャッシュコントローラ
１４４ 出力セレクタ
【技術分野】
【０００１】
本発明は、データ処理装置に関し、より詳細には映像データ処理装置に関する。
【背景技術】
【０００２】
米国特許第５，５３０，４８１号は、ＭＰＥＧエンコーダを記載している。ＭＰＥＧでは、いくつかの画像が、隣接画像からの画素ベクトルブロックを更新画像の選択された一に配置することによって、隣接画像に対する更新として符号化される。ＭＰＥＧ符号化は、ブロックの当初の位置から選択された位置への移動の距離及び方法を記述する動きベクトルの選択を伴う。
【０００３】
ＭＰＥＧ符号化は、典型的には、更新により復号化される画像内の異なるブロックの画素コンテンツを隣接画像内のあるブロックのコンテンツと比較することによって、有用な動きベクトルを検索する。このため、これらの画像の少なくとも１つを格納するのに画像メモリが必要とされる。
【０００４】
米国特許第５，５３０，４８１号は、動きベクトルの検索を高速化するのにどのようにバッファメモリが利用可能であるかを記載している。バッファメモリは、ゼロの動きベクトルに対応するブロックを含み、包囲する画素領域についての画素データを格納する。適切な動きベクトルが選択されると、典型的には以前の領域の大部分と重複する新たな領域が処理され、それに対して、この新たな領域の境界部分の画素データのみがバッファメモリにフェッチされる必要がある。同様の形式の領域ベースのアクセスが、パターンマッチング処理のフィルタリングなど他の画像処理に必要とされる。
【０００５】
米国特許第６，１２５，４３２号は、同様の動きベクトル推定を、この目的のためのキャッシュメモリを利用して実行する。当該特許には詳細には記載されていないが、データをフェッチするのに利用可能なアドレスに対応して、メインメモリからのデータを格納するキャッシュメモリ位置を有するキャッシュメモリは周知である。データがキャッシュメモリ位置に格納されるアドレスは変更可能である。典型的には、データがキャッシュメモリに格納されていない新たなアドレスがアドレス指定されると、当該データはメインメモリからフェッチされ、古いアドレスに対して使用されたキャッシュメモリ位置が、この新たなアドレスと対応するデータについて再利用される。
【０００６】
このタイプの画像処理のパフォーマンス特性は、領域からの画素データのためのメモリの構成によって大きな影響を受ける。動きベクトルの検索中に必要とされる領域のすべての画素を格納するための容量を備えた大きなキャッシュバッファメモリを利用し、当該領域が変更される毎にすべての新しい画素を予めフェッチすることは、キャッシュミスが回避されるという効果を有する。このアプローチの問題点は、より大きな検索領域が必要とされるとき、より大きなバッファメモリが必要となるということである。他には、領域からの画素の一部のみが格納され、他の画素が、当該他の画素が動きベクトルの検索中にアドレス指定されるとき、キャッシュされている画素を置換するのに利用される小さなキャッシュメモリを使用するというものがある。この代替は、キャッシュメモリサイズを低減するが、キャッシュミスによる電力消費と遅延を増大させる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明の課題は、画像処理装置を提供することであり、より一般には、より効率的なキャッシュの使用をサポートする２次元アレイとして構成されるデータを処理する装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明によるデータ処理装置は、請求項１に記載される。データ処理ユニットは、データ値のアレイを処理し、当該アレイのスライドする位置領域を規定する。この領域は、連続的な時間のインターバルにおける連続的な位置を想定する。各時間インターバル中、処理ユニットは、当該時間インターバルにおいて想定される領域内及びその周囲の位置からのデータ値を利用する。データ値をキャッシュするのにキャッシュメモリユニットが設けられる。キャッシュメモリユニットは、処理されるデータアレイにおけるアドレスに適応的に関連付けされたキャッシュ位置を有する。キャッシュ管理は、アドレスの置換による関連付けされたアドレスの変更を可能にする。各時間インターバル中、異なる処理が、当該時間インターバルに想定された領域からのデータ値と、当該領域周辺からのデータ値とに与えられる。当該領域からのデータ値を格納するキャッシュ位置はキャッシュ置換から免除される（ｅｘｅｍｐｔｅｄ）一方、当該領域の周囲からのデータ値を格納するキャッシュ位置はキャッシュ置換される。
【０００９】
キャッシュサイズは、一般には、当該領域が想定される時間インターバル中に当該領域の周囲の位置からプロセッサが必要とするすべての位置のデータ値をキャッシュするのに必要なものより小さい。従って、当該領域の周辺の位置のデータ値は、一般には処理中に置換される。処理ユニットによって使用されるアドレッシングシーケンスに応じて、特定位置のデータ値をリロードすることさえ必要になるかもしれない。このように、キャッシュ位置が効率的に使用され、領域内の頻繁に使用されるデータ値の免除はキャッシュミスを減少させ、領域外のキャッシュ置換の使用は必要とされるキャッシュサイズを低減する。
【００１０】
典型的には、領域のサイズは、例えば、動きベクトルの推定のため一致するマクロブロックの検索中など、処理ユニットがアクセス単位として利用するブロック（すなわち、ブロック及び複数のブロックを含むマクロブロック）のサイズを超える。一例では、当該領域は、中心のマクロブロックと、この中心のマクロブロックの上下左右の隣接するマクロブロックの半分を含む。従って、各マクロブロックがキャッシュミスのリスクなくアドレス指定可能な互いに重複する複数のマクロブロックが領域に適合する一方、中心のマクロブロックからより遠くにあるマクロブロックは部分的にキャッシュミスのリスクがあり、さらに遠くにあるマクロブロックは、完全にキャッシュミスのリスクがある。好ましくは、キャッシュメモリユニットが、アドレス指定されたブロック（又はより一般にはマクロブロック）から複数のデータ値をパラレルに出力するよう構成される。アドレス指定されたブロックが重複しているとき、データ値の境界部分の領域は免除されたキャッシュ位置からのものであるかもしれず、一部は免除されていないキャッシュ位置からのものであるかもしれない。
【００１１】
好ましくは、予測される以降の領域からのデータ値が、メインメモリから免除されるキャッシュ位置に予めフェッチされる。より好ましくは、ウィンドウが移動する際、免除されているキャッシュ位置へのコピー前に予めフェッチされたデータ値を格納するためのプリフェッチバッファが設けられる。
【００１２】
好ましくは、所定のキャッシュ位置セットを利用して、現在領域のデータ値を格納する。この結果、これらのキャッシュ位置の構成は、領域外の位置に対する他のキャッシュ位置の構成とは異なるものになるかもしれず、当該キャッシュ位置が置換を免除されているという知識を利用して、例えば、領域外のデータを格納するキャッシュ位置に対するものよい、領域内のデータを格納するキャッシュ位置に対するより大きなキャッシュメモリ位置（より多くの位置からのデータ値に対する）を利用することによって、領域内のデータに対するキャッシュ位置の構成を最適化する。
【００１３】
一実施例では、所定の位置に対して使用されるキャッシュメモリが、各々がパラレルな異なるｙ−アドレスの第１の個数のラインセグメントに対するデータ値を生成するよう構成される。残りのキャッシュ要素について、１つのｙ−アドレスの１つのみのラインセグメント又は第１の個数より少ない第２の個数のｙ−アドレスの第２の個数のラインセグメントに対するデータ値を生成可能な他のタイプのキャッシュメモリが使用される。所定の位置にデータ値が格納されているウィンドウの完全な範囲内の位置のブロックがアドレス指定されると、データプロセッサは、第１の個数のラインからのデータ値がパラレルに受付される第１モードにスイッチする（「受け付ける」とは、例えば、パラレルな参照値と比較して、又はそうでない場合には、パラレルに処理されることを意味する）。当該ブロックがウィンドウの境界を超えて延伸したり、又はウィンドウの完全に範囲外にあるとき、プロセッサは１つのラインのみのデータ値をパラレルに受け付け、又は第２の個数のラインのみをパラレルに受け付ける第２モードにスイッチする。従って、高度な並列化がウィンドウ内の最も頻繁に出現するブロックについて実現され、より低いレベルの並列化が遠くにあるブロックについて実現される。
【００１４】
ある実施例では、高度な並列化を実現するため、中心のウィンドウからのデータを格納する所定のキャッシュ位置は、例えば、各々が異なるラインに対する複数のラインユニットセットとして、又は他のラインユニットのセットとインタリーブされるラインセットとして構成されるかもしれない。この実施例では、各ラインユニットは、あるラインのデータ値をパラレルに出力するための複数のメモリバンクを有するようにしてもよく、バンクの個数は、いくつかのデータ値をパラレルに出力するのに十分なものであって、アドレス指定されるブロックの幅Ｂｘのデータ値の個数以上である。さらなる実施例では、Ｗ個の連続するｘ−アドレスに対するデータ値が、あるラインセグメントからのデータ値が、Ｗ個の位置内に適合するラインセグメントの何れかのｘ−位置においてパラレルに読むことが可能となるように、上記バンク上に循環的に分散されるようにしてもよい。好ましくは、各メモリバンクの各メモリ位置は、連続するｘ−位置におけるＧ個のデータ値のグループを格納するよう構成され（例えば、Ｇ＝４など）、あるラインユニットのバンクの個数Ｓは、Ｓ＊Ｇが当該ブロックのラインセグメントの幅Ｂｘを超えるくらいに大きなものである。これは、Ｂｘのデータ値の指定されたラインセグメントの出力が、Ｂｘ／Ｇが整数である場合にはＢｘ／Ｇ個のメモリバンクを、そうでない場合には、Ｂｘ／Ｇを超える次に大きな整数個のメモリバンクを要求するように、グループ内のラインセグメントのスタートアドレスを指定することを可能にする。Ｓ＊Ｇ＞Ｂｘとなるように、ラインユニットにおいて十分大きなバンクの個数Ｓを使用することによって、十分なグループからのデータ値がメモリバンクから常にパラレルに出力することが可能となることが保証される。好ましくは、メモリバンクからのデータ値の後の選択が、アドレス指定されたブロックのみのラインセグメントに対するデータ値に出力を揃えさせる。このタイプのキャッシュメモリはまた、自ら、すなわち、他のタイプのキャッシュメモリとの組み合わせでなく、又は通常のメモリとして（キャッシュメモリでなく）利用されてもよい。このように、アクセスされた「ウィンドウ」（又は領域）がデータアレイにおいて移動する場合、ほとんど負担なく高いレベルの並列化を実現することが可能である。
【００１５】
その他のキャッシュ位置は、より低い並列化を可能にするよりシンプルな構成とされてもよい。しかしながらあるいは、画像メモリ又は画像キャッシュ全体が、このより複雑な構成を有するようにしてもよい。
【００１６】
本発明の上記及び他の課題及び効果が、以下の図面を用いて非限定的な具体例により説明される。
【発明の効果】
【００１７】
本発明によると、より効率的なキャッシュの使用をサポートする２次元アレイとして構成されるデータを処理する装置を提供することができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、画像処理装置を示す。
【図２】図２は、位置アレイの一部を示す。
【図３】図３は、キャッシュ要素を示す。
【図４】図４は、画像処理装置を示す。
【図５】図５は、キャッシュ要素を示す。
【図６】図６は、画像処理装置を示す。
【図６ａ】図６ａは、画像処理装置を示す。
【図７】図７は、メモリ構成を示す。
【発明を実施するための形態】
【００１９】
以下、図面に基づいて本発明の実施の形態を説明する。
図１は、処理ユニット１０と、メインメモリ１２と、キャッシュメモリユニット１４とを有する画像処理システムを示す。処理ユニット１０は、キャッシュメモリユニット１４に接続されるアドレス出力とデータ入力とを有する。キャッシュメモリユニット１４は、メインメモリ１２とのデータ及びアドレス接続を有する。動作について、処理ユニット１０は、画像処理演算、すなわち、ｘアドレス及びｙアドレスの組み合わせによりアドレス指定可能な画素データを利用する演算を実行する。処理ユニット１０は、このタイプの組み合わせを表すアドレスをキャッシュメモリユニット１４に供給し、キャッシュメモリユニット１４は、アドレス指定された画素データを返す。このアドレス指定された画素データがキャッシュメモリユニット１４に格納されると、キャッシュメモリユニット１４は、データを直接返す。そうでない場合には、キャッシュメモリユニット１４はまず、メインメモリ１２の画素データをフェッチする。
【００２０】
図２ａは、画像のある領域におけるブロックを示す。この領域は、ｘ方向に１０個のブロックとｙ方向に６個のブロックである。各ブロックは、例えば、８つの水平方向に連続する画素の８つの垂直方向に連続する行を含む。一実施例では、アドレス指定の単位はブロックである。本実施例では、アドレスは、ｘブロックアドレスとｙブロックアドレスの組み合わせを含みさえすればよい（例えば、ｘ画素アドレスとｙ画素アドレスから３つの最下位ビットを省略している）。
【００２１】
キャッシュメモリ１４は、各キャッシュ位置に対するいくつかのキャッシュ要素１４２と、キャッシュコントローラ１４０と、出力セレクタ１４４とを有する。各キャッシュ要素１４２は、ｘ−ｙ画素アドレスに係るｘ−ｙブロックに対する画素データ、又はキャッシュされているブロックのｘ−ｙブロックアドレスをキャッシュするよう構成される。経時的に、関連付けされたｘ−ｙアドレスが変更されるように、異なるブロックがキャッシュ要素１４２にキャッシュされる。処理ユニット１０がキャッシュ要素１４２の何れにも格納されていないブロックにおける画素又は画素ブロックをアドレス指定すると、キャッシュメモリユニット１４は、キャッシュ要素１４２の１つを選択し、当該キャッシュ要素１４２に格納されているブロックを新たにアドレス指定されたブロックと置換する（メインメモリ１２から当該新たにアドレス指定されたブロックをフェッチした後）。その後、キャッシュ要素１４２は、新たにフェッチされたブロックのｘ−ｙアドレスをキャッシュされたデータと関連付ける。
【００２２】
キャッシュコントローラ１４０は、本来的には、キャッシュ要素１４２を管理するプログラムと、キャッシュ要素１４２に格納されるブロックのｘｙ−アドレスを表すメモリを備えた小さなプロセッサとして実現可能である。キャッシュコントローラ１４０は、新たにフェッチされたブロックが格納されるキャッシュ要素１４２の選択を制御する。例えば、最も以前に使用されたキャッシュ要素のデータを置換するＬＲＵなどの何れかの選択アルゴリズムが利用されてもよい。しかしながら、キャッシュコントローラ１４０は、ｘ−ｙアドレスの２次元領域からｘ−ｙアドレスを有する画素ブロックを格納するキャッシュ要素１４２に特別な処理を与える。図２ａの斜線部分２０により示される当該領域は、ｘ方向とｙ方向のそれぞれに複数のブロック行及び列まで拡張される。この領域２０は、処理ユニット１０により選択され、処理ユニット１０が当該領域が移動すべきであると通知すると、当該領域を繰り返し右方向に移動する（当該領域の最も低いブロックのｘアドレスを増大させる）などの処理中に、定期的に更新される。
【００２３】
キャッシュコントローラ１４０は、領域２０からのブロックをキャッシュするキャッシュ要素１４２を通常の置換（すなわち、領域２０の移動することなく行われる置換）から免除する。キャッシュ要素１４２が領域２０を移動させることなく新たにアドレス指定されたブロックを格納するよう選択される必要があるとき、キャッシュコントローラ１４０は、免除されたキャッシュ要素１４２の何れも含まないキャッシュ要素１４２の一部から当該キャッシュ要素１４２を選択する。通常の置換中の免除は、例えば、キャッシュ置換中に免除される所定のキャッシュ要素１４２に領域２０からのブロックを格納することによって、又は、領域２０からのブロックを格納するキャッシュ要素１４２に対するロックフラグを設定することによって、又は領域２０のｘ−ｙアドレス境界と各キャッシュ要素１４２に係るｘ−ｙアドレスとを比較することによってなど何れか便利な方法により実現可能である。
【００２４】
処理ユニット１０がキャッシュコントローラ１４０に領域２０がある方向（所定の方向又は処理ユニット１０によって選択及び指示される方向）に移動しなければならないことを通知すると、キャッシュコントローラ１４０は、キャッシュ置換から免除されたブロックセットを変更する。所定のキャッシュ要素１４２が通常の置換中に免除される実施例では、この変更は、新しい領域には含まれるが、古い領域には含まれないブロックに対する画素データを、古い領域には含まれるが、新しい領域には含まれないキャッシュされているブロックのキャッシュ要素１４２に移動することによって実現される。例えば、水平方向の移動の場合、これは、同一のｘアドレスで異なるｙアドレスを有するブロックの列を格納するキャッシュ要素１４２に関係する。キャッシュ要素１４２がロックフラグにより通常の置換中に免除される実施例では、ロックフラグは、新しい領域に含まれるが、古い領域には含まれないブロックに対して設定され、古い領域に含まれるが、新しい領域には含まれないキャッシュブロックのキャッシュ要素１４２に対してクリアされる。この実施例では、関連するブロックがキャッシュ要素１４２にロードされると、フラグが設定されるかもしれない。
【００２５】
好ましくは、キャッシュコントローラ１４０は、領域２０が移動すると、領域２０に新たに含まれるブロックを予めフェッチするよう構成される。当該実施例では、当該領域が所定の方向に毎に、キャッシュコントローラ１４０は、領域の前の動きをトリガーする信号に応答して予めフェッチすることを開始するかもしれない。処理ユニット１０が方向を選択する実施例では、処理ユニット１０が好ましくはまず送信し、キャッシュコントローラ１４０が、好ましくは、まず、当該領域を移動するための信号の送信前に、予めのフェッチ処理をイネーブルにする方向信号を受信する。
【００２６】
図２ｂは、予めのフェッチ処理を示す。この図では、図２ａの領域２０を２ブロックの幅だけ右方向に移動することによって取得される斜線領域２２が示される。この場合、領域２２の１６個のブロックの内の８つが（当初の領域に属しないブロック）、予めフェッチされる必要がある。
【００２７】
所定のキャッシュ要素１４２が通常の置換中に置換を免除される実施例では、これら所定の免除されたキャッシュ要素１４２は、好ましくは、現在領域２０からのすべてのブロックを格納するのに十分なキャッシュ要素と、予めフェッチされたブロック、すなわち、図２ａの例の２４個のブロックを格納するための追加的なキャッシュ要素１４２を加えてものを有する。ロックフラグが使用される実施例では、キャッシュコントローラ１４０は、当該領域が移動される前に予めフェッチされたブロックをロックする。
【００２８】
好ましくは、キャッシュメモリユニット１４は、処理ユニット１０とパラレルにあるブロックからの複数の画素位置に対する画素値（好ましくは、当該ブロックのある行からのすべての画素値）を出力し、当該ブロックの他の連続する複数の画素（例えば、連続的な行など）を連続的に出力する。キャッシュ要素１４２は、好ましくは、キャッシュ要素１４２があるブロックからの画素データをキャッシュするとき、キャッシュ要素１４２が当該ブロックからのすべての画素値をキャッシュするように、その全体のブロックをキャッシュするよう構成される。この場合、１つのｘ−ｙブロックアドレスは、当該ブロックに対するすべての画素値をキャッシュするキャッシュ要素１４２を識別するのに利用されるかもしれない。１つのｘ−ｙブロックアドレスに応答して、キャッシュ要素１４２は、その後に、同じｘ−アドレスであって、連続する他のｙ−アドレスの画素値の出力に続いて、異なるｘ−アドレスと１つのｙ−アドレスに対する画素値を同時にパラレルに出力するかもしれない。
【００２９】
さらなる実施例では、処理ユニット１０は、マクロブロック、すなわち、ｎ＝ｍ＝２などによるｎ×ｍ個のブロックからなる矩形状などの複数のブロックを含むブロックを利用する。この実施例では、各ブロックをマクロブロックに格納するｎ個のキャッシュ要素１４２が、好ましくは、画素値をパラレルに出力するよう構成される。典型的には、マクロブロックは、領域２０又は免除されたブロックのサイズより小さい。例えば、４×４のブロック領域と、２×２のブロックマクロブロックが利用されてもよい。
【００３０】
図３は、このためのキャッシュ要素の実現形態の一例を示す。キャッシュ要素は、アドレスタグメモリ３０と、アドレス入力３１と、複数のアドレス比較器３２と、データメモリ３４とを有する。さらに、複数のキャッシュ要素により共有可能なラインカウンタ３６が示される。動作について、データメモリ３４は、あるブロックからの画素データを格納する。アドレスタグメモリは、そこからデータが格納されるブロックのｘ−ｙブロックアドレスを格納する処理ユニット１０（図示せず）は、あるマクロブロックのｘ−ｙアドレスをアドレス入力３１に適用する。比較器３２は、処理ユニット１０（図示せず）からのｘ−ｙアドレスとアドレスタグメモリ３０からのアドレスとを比較し、これにより、各比較器３２は、アドレスタグメモリ３０がアドレスマクロブロックに含まれるある行のブロックの各ブロックを含むかチェックする。すなわち、第１比較器は、アドレスタグメモリ３０からのアドレスＡ＝（Ａｘ，Ａｙ）が、処理ユニット１０からのマクロブロックのアドレスＢ＝（Ｂｘ，Ｂｙ）に等しいかチェックする。第２比較器は、ＡｘがＢｘ＋ｄとＡｙ＝Ｂｙに等しいか（ただし、ｄはブロックのｘの幅である）チェックする。あるマクロブロックがｎ×ｍ個のブロックを含むとき、ＡｘがＢｘ＋ｉ＊ｄに等しいかチェックするｎ個の比較器がある。ここでは、各比較器が、０からｎ−１までの各整数ｉの値についてチェックする。
【００３１】
比較器３２は、選択器１４４（図示せず）に接続される出力を有する。選択器１４４は、ｎ個のキャッシュ要素のデータメモリ３４からの画素データをパラレルに出力するよう構成される。選択器１４４は、このためにｎ個の出力を有する。各比較器３２は、各出力に対応し、比較器３２がアドレスの一致を検出する場合、対応する出力においてデータメモリ３４からのデータを選択器に出力させる。ラインカウンタ３６は、処理ユニット１０のアドレス指定処理により開始され、ｙ−アドレスをカウントアップする。ラインカウンタ３６は、これらｙ−アドレスをデータメモリ３４に供給し、マクロブロックアドレスに応答して、データメモリに選択器１４４を介し当該ブロックの連続するラインに対する画素データを連続的に処理ユニット１０に出力させる。
【００３２】
ｎ×ｍのマクロブロックの高さｍが１より大きい場合、ｙ−アドレスはカウント中にブロック境界とクロスする。この場合、ラインカウンタ３６はまた、好ましくは、ブロックのｙ−アドレスのサブマクロブロック部分を供給するため、比較器３２に接続される出力を有する。ラインアドレスがブロック境界をクロスするとき、異なるキャッシュ要素が選択され、垂直方向に連続するブロックからの画素データが選択器１４４を介し出力される。マクロブロック内の各ブロックのアドレス指定中、通常の置換を免除されているブロックから免除されていないブロックに、又はその反対のアドレス指定がクロスする可能性があるということが理解されるべきである。これは、同時にパラレルに出力される所与のｙアドレス値に対する画素データのライン内、又は１つのｙ−アドレス値の１つのラインから他のラインへの遷移中に行われるかもしれない。これは、マクロブロックに対するキャッシュミス又は部分的なキャッシュミスを引き起こすかもしれない。選択器１４４の出力に対応する比較器の何れもが応答しないとき、このことがキャッシュコントローラ１４０に通知される。これは、あるマクロブロック内のブロックがキャッシュメモリに存在しないことを示す。キャッシュコントローラ１４０は、メインメモリ１２から関連するブロックをフェッチし、キャッシュ要素１４２（免除されているマクロブロック内のブロックを格納するキャッシュ要素）を選択し、当該ブロックの画素データを選択されたキャッシュ要素１４２のデータメモリ３４に、そしてそれのｘ−ｙブロックアドレスを当該キャッシュ要素１４２のアドレスタグメモリ３０に書き込むことによって応答する。必要に応じて、キャッシュコントローラ１４０は、このようにして複数のブロックをフェッチする。キャッシュコントローラ１４０は、処理ユニット１０にすべての必要なブロックが利用可能になるまで待機させる。
【００３３】
予めのフェッチ処理が、免除された領域２０のロックされたブロックについて用いられる場合、当該ブロックにはキャッシュミスは発生しない。しかしながら、マクロブロックが当該領域からのブロックを含む場合であっても、マクロブロックが領域２０の境界を超える場合、キャッシュミスが発生するかもしれない。
【００３４】
さらなる実施例では、キャッシュコントローラは、アドレス指定されたマクロブロック内のより大きなｙアドレスに対するブロックがキャッシュ要素において利用可能であるか予めチェックするよう構成される。そうでない場合、より小さいｙ−アドレスのブロックからの画素データが処理ユニット１０に出力されている間、キャッシュコントローラ１４０は任意的に上記ブロックを予めフェッチする。
【００３５】
効果的には、通常の置換を免除されるブロックが連続しているという知識が利用される（当該領域外のキャッシュされているブロックは、連続している必要はない）。一実施例では、所定のキャッシュ要素１４２のセットが、領域２０からのブロックを格納するのに利用される。
【００３６】
図４は、アクティブ領域のブロックに対するコアキャッシュ４０と、当該領域外のブロックに対する周辺キャッシュ４２の２つのキャッシュメモリ４０と４２がこのために利用される実施例を示す。アクティブ領域２０からのブロックがシステマティックにコアキャッシュ４０に維持されることが保証されているため、それらはまたシステマティックに格納されてもよい。この結果、コアキャッシュ４０の構成を簡単化することができる。アクティブ領域２０のブロック列毎に１つのキャッシュ要素で十分である。すなわち、連続するｙ値によるブロックに対する個々のキャッシュ要素は必要でない。当該領域がｈの高さのブロックである場合、コアキャッシュ４０のキャッシュ要素のデータメモリ３４は、コアキャッシュ４０内の各ｙ−アドレスに対してｈ倍以下の画素値のラインしか有しない。このことは、より少ないアドレス比較器で十分であることを意味する。
【００３７】
図５は、このためのキャッシュ要素を示す。本実施例では、アドレス入力は、１つのライン内のブロックを選択するため、処理ユニット１０からのｙ−アドレスのブロックアドレス部分の一部をデータメモリ３４へのアドレスとして適用するための部分５０を有する。好ましくは、領域２０からの各ラインが、それのｙアドレスのデータメモリのライン数の法（ｍｏｄｕｌｏ）の最下位の剰余に対応するデータメモリのｙアドレスに格納される。すなわち、領域２０の位置に応じて、当該領域の先頭に関する所与のｙ−オフセットにあるラインが、常にそれらの絶対ｙ−アドレスに従って異なるメモリ位置に格納されるかもしれない。
【００３８】
アドレス比較の回数は、領域２０からのブロック列のキャッシュ要素１４２への所定の循環的割当てを利用することによって、さらに減らすことができる。この場合、１回のみの比較（マクロブロックが領域と重複しているか検出するため）と減算（当該ブロックのｘアドレスを循環的割当てにおけるある列のキャッシュ要素のアドレスに変換するため）が、コアキャッシュ４０のキャッシュ要素の何れがブロックをアドレス指定するのに利用されるべきか判断するのに必要とされる。
【００３９】
上述されたように、別個のコアキャッシュ４０と周辺キャッシュ４２の利用は、新たな領域からのブロックが、処理ユニット１０が当該領域を移動するよう通知した後、コアキャッシュ４０に存在する必要があることを意味する。これらのブロックは、可能な限り周辺キャッシュ４２からコピーされてもよいが、好ましくは、当該ブロックが周辺キャッシュ４２に存在するか否かに関係なく、コアキャッシュ４０に存在しない新たな領域からのすべてのブロックがメインメモリ１２からフェッチされる。好ましくは、これらのブロックが予めフェッチされる。この場合、キャッシュ管理ユニット１４０は、次の領域２２がどのようなものとなるか予測し、あるいは、処理ユニット１０は、新たな領域への移動を実際に通知する前に、新たな領域２２がどのようなものになるか予め通知する。所定のステップだけ水平方向にスライドする領域の場合、この予測はシンプルであるが、もちろん、より複雑な移動パターンが使用されてもよい。
【００４０】
図６は、プリフェッチバッファ６０がコアキャッシュ４０とメインメモリ１２との間に（キャッシュコントローラ１４０を介し）も受けられる実施例を示す。本実施例では、キャッシュコントローラは、メインメモリ１２から予測された以降の領域２２の新たなブロックを予めフェッチし、これらのブロックをプリフェッチバッファ６０に格納するよう構成される。処理ユニット１０からウィンドウを移動するための信号を受信すると、キャッシュコントローラ１４０は、予めフェッチされたブロックをプリフェッチバッファ６０からコアキャッシュ４０の選択されたキャッシュ位置にコピーさせる。本実施例は、予めのフェッチ処理が通常のキャッシュ処理との干渉を引き起こさないという効果を有する。
【００４１】
他の実施例では、領域２０について厳密に必要なものより多くのキャッシュ位置が、コアキャッシュ４０に設けられる。本実施例では、以降の領域２２の新たなブロックが、現在領域２０については使用されないキャッシュ位置に直接的に予めフェッチされる。ある実施例では、キャッシュコントローラ１４０は、これらのブロックがコアキャッシュの残りから予めフェッチされるキャッシュ要素を分離し、これにより、当該キャッシュ要素への書き込みは、メイン処理ユニット１０による読み出しとは独立に進行することが可能である。
【００４２】
予めフェッチが行われないとき、周辺キャッシュ４２にある新たな領域２０からのこれらのブロックは、好ましくは、コアキャッシュ４０に移動され、任意的にはそれらがメイン処理ユニット１０によりアドレス指定されるときに限って、その他のブロックがメインメモリ１２からフェッチされる。
【００４３】
ある実施例では、コアキャッシュ４０と周辺キャッシュ４２は、位置のブロックに対するデータ値の出力中、異なるレベルの並列化をサポートするよう構成されるかもしれない。
【００４４】
図６ａは、コアキャッシュ４０がブロックの異なるｙ−アドレスを有する複数のラインセグメントに対するデータ値をパラレルに出力するよう構成されるこのタイプの実施例の一例を示す。対照的に、周辺キャッシュ４２は、１つのラインセグメントが一度にアドレス指定されることを可能にするキャッシュ要素を含む。コアキャッシュ４０は、パラレルにデータ処理ユニット１０に接続される第１出力を有する。コアキャッシュ４０と周辺キャッシュ４２の組み合わせがまた、処理ユニット１０に接続される。
【００４５】
動作について、領域２０の内部に完全にあるブロックがアドレス指定されると、コアキャッシュは、当該ブロックのライン上の位置に対するデータ値を処理ユニットにパラレルに出力する。領域２０の境界を超えて延長するブロック、又は当該領域２０の外部にあるブロックがアドレス指定されると、データ処理ユニット１０は、データ処理ユニットが当該ブロックからの１つのラインの位置に対するものであって、少なくとも部分的に周辺キャッシュ４２からのデータ値を一度に受け付けるモードにスイッチする（ここで使用される受付とは、データ値と参照値のパラレルな比較や他の処理演算のパラレルな実行などに関するものである）。これは、大部分の時間において発生する、コアキャッシュ４０内のブロックがアドレス指定されるとき、高速のパラレル処理が利用可能であるという効果を有する。周辺ブロックがアドレス指定されると、低速モードが利用される。ブロックアドレスとキャッシュされた領域２０との比較の結果として、又は遠くの動きベクトルが検討される場合の動きベクトルの検索中など、処理ユニット１０により内部的に、モード切替がアドレッシングユニット（図７）によりトリガーすることが可能である。
【００４６】
画像処理中、当該ブロックが領域２０の内部にあるとき、処理ユニット１０は画素ブロック単位によりデータ値を読み込む。各画素ブロックは複数のラインセグメントを有し、連続するラインセグメントは、「Ｂｙ」個の連続するｙ−アドレスを有し、各ラインセグメントは連続するｘ−アドレスを有する「Ｂｘ」個の位置を有する。処理を高速化するため、アドレス指定されたブロックからの複数の位置に対するデータ値を処理ユニット１０にパラレルに出力するため、好ましくは、画像メモリ１４が構成される。好ましくは、画像メモリが、連続するｙアドレスを有する複数のラインセグメントの位置からのすべてのデータ値をパラレルに出力するよう構成される。これは、大量のパラレルアクセスを意味する。例えば、１６×１６の位置ブロックが使用され、４つのラインがパラレルに出力される必要がある場合、６４のデータ値がパラレルに出力される必要がある。
【００４７】
図７は、この大量並列化をサポートするメモリ構成を示す。メモリは、アドレッシングユニット７０と、複数のラインユニット７２と、出力スイッチ７４とを有する。アドレッシングユニット７０は、処理ユニット１０（図示せず）に接続されるアドレス入力７１を有する。出力スイッチ７４は、それぞれが画像の画素ブロックのラインセグメントに対応する位置からのＢｘのデータ値のパラレルな出力のための複数のラインセグメント出力７６を有する。各ラインユニット７２（１つのみがより詳細に示される）は、複数のメモリバンク７２０とバンクスイッチ７２２とを有する。バンク７２０は、アドレッシングユニット７０に接続されるアドレス入力を有する。バンクスイッチ７２２は、メモリバンク７２０のデータ出力に接続されるデータ入力と、アドレッシングユニット７０に接続される制御入力とを有する。出力スイッチ７４は、ラインユニット７２のバンクスイッチ７２２のデータ出力に接続されるデータ入力と、アドレッシング回路７０に接続される制御入力とを有する。
【００４８】
各メモリバンク７２０は、複数のアドレス指定可能な位置を有し、各位置は、画像の異なる画素位置に対する複数のＧ個のデータ値（Ｇ＝４など、Ｇ＞１）を格納するよう構成される。各ラインユニット７２は複数のＳ個のバンク（Ｓ＞１）を有し、これにより、これらのバンクは一緒になって、異なる画素に対するＧ＊Ｓ個のデータ値を出力する。ラインスイッチ７２２が、アドレッシング回路の制御の下、メモリバンク７２０からのＧ＊Ｓのデータ値から選択されたＢｘ（Ｂｘ＝あるラインセグメントの画素位置数）個のデータ値（Ｂｘ＜Ｇ＊Ｓ）を出力するよう構成される。出力スイッチ７４は、ラインスイッチ７２２からのデータ値をラインセグメント出力７６に出力するよう構成され、アドレッシングユニット７０は、何れのラインスイッチ７２２が何れのラインセグメント出力７６に接続されるか制御する。ラインユニット７２はＮ個ある（Ｎ＝４など）。典型的には、ラインユニットの個数Ｎは、セグメント出力７６の個数に等しい。
【００４９】
処理中、キャッシュコントローラ１４０は、ラインユニット７２のメモリバンク７２０にデータ値を書き込むか、あるいは、アドレッシングユニット７０がこのためにキャッシュ管理ユニットとして利用される。書き込みは、初期的に、又は領域２０の位置が変更されると行われる。この場合、キャッシュ管理ユニットとして動作するアドレッシングユニット７０は、メインメモリ１２からデータ値をフェッチし、フェッチされたデータ値をメモリバンク７２０の選択されたアドレスと共に、選択されたラインユニット７２の選択されたメモリバンク７２０に適用する。
【００５０】
キャッシュコントローラ１４０又はアドレッシングユニット７０によるキャッシュ管理は、各ラインユニット７２がそれのメモリバンク７２０に格納され、各ｙ−アドレス又はｙ−アドレスセットを有する位置に対するデータ値は、当該ラインユニット７２に一意的であり、いくつかの連続するｙ−アドレスに対するデータ値がラインユニットの組み合わせに格納されるように構成される。すなわち、例えば、第１ラインユニット７２は、ｙアドレスがｙとなる位置に対するデータ値を格納し、第２ラインユニット７２は、ｙアドレスがｙ＋１となる位置に対するデータ値を格納するなどである。各ラインユニットがｙ−アドレスセットに対するデータ値を格納する場合、当該セットは、あるセット内のｙの値の間の距離が各セットに対して同一となり、ラインユニット７２の個数Ｎの整数倍に等しくなるようにインタリーブされる。例えば、第１ラインユニット７２は、ｙアドレスがｙ、ｙ＋Ｎ、ｙ＋２Ｎ等となる位置に対するデータ値を格納し、第２ラインユニット７２は、ｙ−アドレスがｙ＋１、ｙ＋Ｎ＋１、ｙ＋２Ｎ＋１等となる位置に対するデータ値を格納するなどである。
【００５１】
各ｙ−アドレスについて、ラインユニット７２は、「ｗ」個の連続するｘ−アドレスによる複数の位置に対するデータ値を格納する。ただし、連続するｘアドレスの個数ｗは、画素ブロックのラインセグメントサイズＢｘを超え（ｗ＞Ｂｘ）、またラインユニット７２のバンクがパラレルに出力可能な個数Ｇ＊Ｓを超える（ｗ＞Ｇ＊Ｓ）。テーブルＩは、異なるｘ−アドレスを有するデータ値のラインユニット７２のメモリバンク７２０への割当ての一例を示す。この例では、ラインユニット７２のメモリバンク７２０の個数Ｓは５とされ（Ｓ＝５）、メモリバンク７２０の各位置のデータ値の個数Ｇは４とされる（Ｇ＝４）。データ値が格納された連続するｘ−アドレスの個数ｗは、本例では３２とされる（ｗ＝３２）。テーブルの各列は、メモリバンク７２０に対応する。テーブルの各フィールド（第１行のフィールドを除いて）は、当該フィールドの列に対応するメモリバンクの１つのメモリ位置に格納されているｘ−アドレスを表す。
【００５２】
【表１】
ｘ−アドレスの割当ては静的なものではない。処理ユニット１０が処理中に画像のあるラインに沿って右方向に進捗すると、以前のアドレスの右側に新たなｘ−アドレスに対するデータ値がロードされ、左側のデータ値を以前に格納したバンクに格納される。テーブルＩＩは、異なるｘ−アドレスを有するデータ値のメモリバンク７２０への割当てが経時的にどのように進化するかの一例を示す。
【００５３】
【表２】
バンク０の１つのメモリ位置に対するデータ値（当初は、ｘ−アドレスｘ、ｘ＋１、ｘ＋２、ｘ＋３に対する）が、新たなｘ−アドレス（ｘ−アドレスｘ＋３２、ｘ＋３３、ｘ＋３４、ｘ＋３５）、すなわち、当初のｘアドレスよりｗ（ｗ＝３２など）だけ大きなｘ−アドレスに対するデータ値と置換されたことに留意すべきである。同様のことがバンク１の１つのメモリ位置についてなされるが、その他のバンクは不変とされる。処理がラインに沿って進められると、データ値がバンク２と３において置換され、その後にバンク４と０などのように循環的に行われる。データ値が占有するバンクのメモリ位置は常に同一に維持されるが、格納されているデータ値の画素位置のアドレスは変更される。
【００５４】
テーブルＩＩＩは、複数のｙ−アドレスのセットが各メモリバンク７２０に格納される実施例を示す。
【００５５】
【表３】
バンク０は、ｙアドレスｙ、ｙ＋Ｎ、ｙ＋２Ｎなどに対するデータ値を格納することに留意すべきである。バンク１は、ｙ−アドレスｙ＋１、ｙ＋Ｎ＋１、ｙ＋２Ｎ＋１などに対するデータ値を格納する。各ｙ−アドレスに対して、連続する異なるｘ−アドレスに対するデータ値が、前述の表に示されるように、メモリバンク７２０に循環的に分散される。
【００５６】
テーブルＩとＩＩの場合と同様に、メモリ位置のデータ値のアドレスは静的ではない。このことは、テーブルＩＶに示されている。
【００５７】
【表４】
本実施例では、所与のｙ−アドレスを有するデータ値に対して用いられる位置セットは、同じままであり、あるｘ−アドレスとｙアドレスを有する位置に対する各データ値は、同一のｙ−アドレスとｘアドレスｘ−ｗを有するデータ値を置換する。さらに、テーブルＩＩＩ及びＩＶの実施例に示されるように、異なるＹアドレスを有する位置に対するデータ値のセットの間にはギャップはない。本実施例のメモリバンク７２０では、ｘｙアドレスｘ，ｙ＋Ｎを有する位置に対するデータ値が、多数のｘアドレスに対するデータ値がメモリバンク７２０に同時に存在する場合、ｘｙアドレスｘ＋ｗ，ｙを有する位置に対するデータ値により占有される位置に格納される。
【００５８】
この格納スキームは、大量のパラレルアクセスと画素位置のウィンドウに対するデータ値の回転する置換の組み合わせを容易にするよう構成される。ウィンドウが移動すると、ウィンドウの外側の画素位置に対するデータ値は、ウィンドウの内側の画素位置に対するデータ値により置換される。
【００５９】
アドレッシングユニット７０は、画像内の画素位置のブロックからのデータ値が、処理ユニット１０（図示せず）にパラレルに出力されることを保証する。ブロックのｘｙ−アドレスを受け取ると、アドレッシングユニット７０は、当該ブロックのラインセグメントに対するデータ値が、異なるメモリバンク７２０から読み込まれるメモリバンク内アドレスを計算する。アドレッシングユニット７０は、これらのアドレスをメモリバンク７２０に適用する。さらに、アドレッシングユニット７０は、メモリバンク７２０の何れがブロックなのラインセグメントの何れの位置からのデータ値を格納するか計算する。アドレッシングユニット７０は、ラインスイッチの出力の各部分が、受け付けた当該ブロックのｘｙ−アドレスに対して、各自の所定のｘ−オフセットにおける位置に対するデータ値を出力することを保証するため、対応する制御信号をラインスイッチ７２２に供給する。最終的に、アドレッシングユニット７０は、何れのラインユニット７２が何れのラインセグメントを出力するか計算する。アドレッシングユニット７０は、各セグメント出力７６が受け付けたブロックのｘｙ−アドレスに対して、各自の所定のｙ−オフセットにおけるラインセグメントに対するデータ値を出力することを保証するため、対応する制御信号を出力スイッチ７４に供給する。
【００６０】
アドレス指定の実施例のより詳細な具体例が説明される。本例では、アドレッシングユニット７０に供給されるｘｙ−アドレスは、Ａｘ Ａｙにより示される。ここで、Ａｘはｘ−アドレス部分であり、Ａｙはｙ−アドレス部分である。本実施例では、ウィンドウコーナーアドレスＷｘ、Ｗｙからスタートし、水平方向にｗ個の画素位置だけ連続する画素位置のウィンドウに対するデータ値を格納する。アドレッシングユニット７０は、ウィンドウのコーナーアドレスのデータ値が格納されるメモリバンク７２０のメモリ位置ＭとバンクＢを示すオフセットカウンタ値Ｂ，Ｍを維持する。さらに、アドレッシングユニットは、ウィンドウの連続するラインの最も左の位置からのデータ値を格納するメモリバンク７２０のメモリ位置のアドレスＺ間のオフセットであるＤに関する情報を表す（ここで、Ｚは複合アドレスＺ＝ｑ＋ｒ＊Ｓであり、ｑはメモリ位置を含むメモリバンク７２０のシーケンス番号であり、ｒは当該バンクのアドレスである）。テーブルＩＩとＩＶの例では、Ｄ＝８となる。
【００６１】
この情報から、アドレッシングユニット２０は、（ａ）アドレス指定されたブロックの左上のコーナーに対するデータ値が格納されるメモリバンク７２０のメモリ位置内の位置Ｉと、（ｂ）アドレス指定されたブロックの左上のコーナーに対するデータ値が格納されるバンクのシーケンス番号Ｃと、（ｃ）アドレス指定されたブロックの左上のコーナーに対するデータ値が格納されるメモリバンク７２０内のアドレスＲとを計算する。Ｉ、Ｃ及びＲは、アドレス指定されたブロックの左上のコーナーに対するデータ値が格納されるメモリバンク７２０内のアドレスとメモリバンク７２０を示す位置の値Ｐに関して表すことが可能である。
【００６２】
Ｐ＝Ｂ＋Ａｘ−Ｗｘ＋Ｄ＊（Ａｙ−Ｗｙ）
位置の値Ｐは、
Ｉ＝Ｐ ｍｏｄ Ｇ
に従って、メモリバンク７２０のメモリ位置内の位置Ｉを規定するのに利用可能である。（ここで、「ｍｏｄ」は、モジュロ（法）関数を示し、すなわち、Ｇで除した後のＰの剰余である。）同様に、メモリバンク７２０のシーケンス番号Ｃは、
Ｃ＝［（Ｐ−Ｉ）／Ｇ］ｍｏｄ Ｓ
に従って規定することができる。
【００６３】
メモリバンク７２０内のアドレスＲは、
Ｒ＝［（Ｐ−Ｃ＊Ｇ−Ｉ）／（Ｓ＊Ｇ）］
に従って規定することができる。
【００６４】
アドレッシングユニット７０は、この情報を以下のように利用する。各ラインユニット７２において、アドレッシングユニットは、通常、Ｃ以上のシーケンス番号を有するメモリバンク７２０をアドレスＲによりアドレス指定し、（存在する場合）Ｃ未満のシーケンス番号を有するメモリバンクをアドレスＲ＋１によりアドレス指定する。アドレッシングユニットは、入力から出力までデータ値の割当てをＧ＊Ｃ＋Ｉだけ回転するようラインスイッチ７２２を制御する。すなわち、出力にシーケンス番号ｊ＝０，１，．．．，Ｂｘ−１が割り当てられる場合、ラインスイッチ７２２は、シーケンス番号ｊによるそれの出力に、
Ｋ＝（Ｉ＋ｊ）ｍｏｄ Ｇ
に従ってメモリバンク７２０内の位置Ｋからのデータ値を出力させる。メモリバンク７２０は、
Ｌ＝（Ｉ＋ｊ−Ｋ）／Ｇ
に従ってシーケンス番号Ｌによりデータ値が選択されるメモリバンクである。
【００６５】
最後に、アドレッシングユニット７０は、何れのラインユニット７２が何れのラインセグメント出力７６に接続されるか判断するため、出力スイッチ７４を制御する。ラインセグメント出力７６にシーケンス番号ｉ＝０，１，．．．，Ｎ−１が割り当てられ、ラインユニット７２にシーケンス番号ｉ’＝０，．．．，Ｎ−１が割り当てられる場合、出力スイッチ７２２は、シーケンス番号ｉを有するそれのラインセグメント出力に、
ｉ’＝［ｉ＋Ａｙ−Ｗｙ］ｍｏｄ Ｎ
に従ってシーケンス番号ｉ’を有するラインユニット７２からのラインセグメントを出力させる。
【００６６】
Ｎ個のセグメント出力７６が、少なくとも垂直ブロックサイズＢｙに等しい場合（Ｎ≧Ｂｙ）、位置ブロックのすべてのデータ値がパラレルに出力される。垂直ブロックサイズがより大きい場合（Ｂｙ＞Ｎ）、いくつかの連続する時間サイクルが当該ブロックの連続する部分に対するデータ値を連続的に出力するのに必要とされる。この場合、アドレッシングユニット７０は、連続するサブブロックから読み出し、Ｎ＊Ｂｘ個の位置のサブブロックを効果的に出力し、連続するサブブロックがｘｙ−アドレス（Ａｘ，Ａｙ）、（Ａｘ，Ａｙ＋Ｎ），（Ａｘ，Ａｙ＋２Ｎ）などにおいてスタートすることにより、あるアドレスに応答する。
【００６７】
ここまで、メモリの構成が、ブロックアドレスに応答して画像内の画素位置の２次元ブロックから大量のデータ値をパラレルに出力し、同時にウィンドウがスライドするとき、データ値の過剰なロード処理なしに画素位置のスライドするウィンドウからのデータ値の格納を受け入れることを可能にする。このブロックアドレスは、何れかの画素位置に配置することが可能である。
【００６８】
データ値がパラレルに出力されるラインセグメントと少なくとも同程度のラインユニット７２（Ｎ個のラインユニット）が存在することに留意することが重要である。この結果、異なるｙ−アドレスを有するＮ個のラインセグメントからのデータ値は、パラレルに出力されるかもしれない。
【００６９】
各ラインユニットは、パラレルに出力されるラインセグメントからのデータ値の個数を出力するのに厳密に必要なものより、少なくとも１だけ多いメモリバンク７２０を有する（（Ｓ＋１）＊Ｇ≧Ｂｘ）。これは、メモリバンク７２０の各メモリ位置のデータ値の個数Ｇの整数倍となるｘ−アドレスを有する位置だけでなく、任意の画素位置においてラインセグメントをスタートさせることを可能にする。ラインセグメントのスタートｘ−アドレスがこのような整数倍である場合、これらのメモリバンク７２０のＢｘ／Ｇのみがラインユニット７２において読み出されるだけでよく、しかしながら、アドレスが揃っていない場合、１＋Ｂｘ／Ｇ個のメモリバンク７２０がラインユニット７２において読み出される必要がある。これらのメモリバンク７２０の２つからのデータ値のみが、部分的に処理ユニット１０に出力される。
【００７０】
各ラインユニット７２は、好ましくは、Ｎ（ラインユニット７２の個数）アドレスだけ離れたｙ−アドレスの自らのラインセットからのデータ値を格納する。連続するラインユニットは、連続する中間のラインからのデータ値を格納する。これは、固定されたｙ−アドレス値又はいあるベース距離の倍数だけでなく、任意のｙ−アドレス値Ｗｙを有するブロックを抽出することを可能にする。
【００７１】
画像メモリの実施例が説明されたが、多数の代替が可能であるということに留意すべきである。例えば、一実施例では、メモリバンクの異なるラインセグメントに対するデータ値の間にギャップが存在するかもしれない。言い換えると、本例ではオフセットＤは、データ値が格納されているウィンドウのｘ−アドレスの個数ｗに等しくされているが、いくつかの実施例では、Ｄ＞ｗとなってもよい。他の例として、異なるｙ−アドレスのラインセグメントが、メモリバンク７２０の任意の位置に格納されてもよく、何れかのアドレス変換機構（キャッシュメモリにおいて使用されるタイプのものなど）が、所望の位置をアドレス指定するのに利用される。
【００７２】
他の例として、本実施例では、データ値がパラレルに出力される各ラインセグメントの位置の個数Ｍが、水平方向のブロックサイズＢｘに等しくされるが、他の実施例では、この数Ｍは、Ｂｘ（（Ｓ＋１）＊Ｇ≧Ｍ）より小さくてもよく、ブロックのラインセグメントの一部のみがパラレルに出力されるということが理解されるであろう。この場合、より少ない個数Ｓのバンクは、各ラインユニット７２において利用されてもよいが、もちろん、複数のラインセグメント部分が、処理ユニット１０がブロック全体からのデータ値を必要とする場合には、連続的に出力される必要がある。
【００７３】
さらなる他の例として、ラインＳ’ユニット７２のグループが同じアドレス値について使用されてもよく、それぞれが、連続するセグメントがより大きなセグメントを一緒になって構成するように、連続するｘ−アドレスのセグメントに対するデータ値を格納する。このような実施例の構成は、図７の構成と類似している。相違点は、ラインユニットのメモリバンク７２０がグループに構成され、バンクシーケンス番号が各グループにおいて包み込んでいるということである。この場合、さらなる出力スイッチが、異なるグループからの各位置にわたるラインセグメントに対するデータ値を構成するよう追加されてもよい。テーブルＶは、このことを示す。
【００７４】
【表５】
簡単化のため、小さなグループと少数のグループが使用されたが、実際には、より多くのより大きなグループが利用可能であるということは理解されるであろう。本実施例では、ラインスイッチ７２２は、２つのグループからブロックアドレスに応じてグループ上に拡がるｘ−アドレスの範囲を有する位置に拡がるラインセグメントになど、様々なグループからのデータ値を合成するよう構成される。
【００７５】
あるいは、これは、図７に示されるような複数のメモリユニットをパラレルに設け、出力スイッチ７４と処理ユニット１０との間にさらなるスイッチを挿入することによって実現されるかもしれない。本実施例では、各メモリユニットは、ある範囲のｘ−アドレス（範囲（ｘ．．ｘ＋ｗ−１），（ｘ＋ｗ．．ｘ＋２ｗ−１），．．．など）に対するデータ値を格納する。さらなるスイッチは、異なるメモリユニットからのデータ値を異なるメモリユニットの出力からの連続するｘ−アドレスのラインセグメントに対するデータ値に合成する。
【００７６】
さらに、異なるｘ−アドレスとある特定のｙ−アドレスを有する位置に対するデータ値がメモリバンク７２０の同一のメモリ位置のセットを占有し続ける実施例が説明されたが、他の実施例では、異なるｙ−アドレスに対するメモリ位置が循環するようにしてもよい。これは、テーブルＩＩＩから進化したものであるが、テーブルＩＶと比較して異なるアドレス指定スキームによるテーブルＶＩに示される。
【００７７】
【表６】
テーブルＩＩＩと比較することによりわかるように、最終ラインセグメントの新たなｘ−アドレスに対するデータ値が（ｙ−アドレスｙ＋ＨからＨ個の下方のライン）、ここで最初の２つのメモリバンクの第１メモリ位置に格納される。第１ラインセグメント（ｙ−アドレスｙ）の新たなｘ−アドレスに対するデータ値が、次のライン（ｙ−アドレスｙ＋１）などの古いｘ−アドレスについて使用された位置に格納される。
【００７８】
本実施例では、アドレスブロックの第１のｘ−アドレスを含むバンクのシーケンス番号とバンク内の位置のアドレスを計算するための異なる方法が必要とされる。
【００７９】
さらに、本例は正のｘ−方向への８つの画素位置のステップによるウィンドウの移動について説明されたが、任意のサイズ及び任意の方向の移動が利用されてもよいということは理解されるであろう。例えば、正のｘ−方向へのより大きなステップ又はより小さなステップは、単により多く又はより少ないメモリバンク７２０にデータ値を上書きすることを要求するにすぎない。負のｘ方向へのステップは、テーブルＶＩに示されるように、最後の位置に対するデータ値の置換を要求する。
【００８０】
【表７】
ｙ方向へのウィンドウの移動ステップは、古いｙ−アドレスに対するデータの置換を伴う。正のｙ方向への１ラインのステップの場合、これは、最も小さなｙの値に対するデータ値を格納する１つのラインユニット７２のメモリバンク７２０におけるデータ値との置換を伴う。
【００８１】
テーブルＶＩＩＩは、ｙ方向の移動の例に対するこのタイプの置換を示す。本例では、まずＨは、メモリバンクに格納されるウィンドウのライン数である。
【００８２】
【表８】
より大きなステップについては、古いｙ−アドレスに対するデータ値が、より多くのラインユニット７２において置換される。可能な移動ステップは、ｘとｙ方向へのステップに限定されるものではない。斜めのステップが、ｘとｙステップの組み合わせとして実現可能である。
【００８３】
これらのデータ値は、典型的には、画像全体を格納するメインメモリ１２（図示せず）からフェッチされる。このため、ラインユニットには、ラインユニットに格納される必要のあるラインセグメントのアドレスに与えられる関連するデータ値をフェッチするためのメインメモリとの接続が設けられるかもしれない。ある実施例では、メインメモリはまた、各々がＮラインだけ離れた各ｙ−アドレスセットに対するラインを格納する複数のユニットに構成される。この場合、各ラインユニット７２は、メインメモリの各ユニットに接続されるかもしれない。
【００８４】
図７の画像メモリは、様々な方法により図１のキャッシュ構成と組み合わされるかもしれないということが理解されるべきである。最もシンプルな実現形態では、図７のメモリユニットが、図７に示されるタイプである必要はないが、領域２０のコアキャッシュ及び領域２０を包囲する位置に対する任意のタイプの周辺キャッシュメモリとして利用される。この周辺キャッシュメモリが複数のラインセグメントに対するデータ値をパラレルに出力することができないタイプのものである場合、コアキャッシュのパフォーマンスは、アドレスブロックがコアキャッシュと周辺キャッシュの両方の位置に拡がる場合、コアキャッシュから１回に１つのラインを利用することによって、単に劣化される。
【００８５】
他の実施例では、バンク内のアドレスは、適応可能なｘ及び／又はｙアドレスと関連付けされるかもしれない。本実施例では、メモリユニット（アドレッシングユニット７０又はメモリバンク７２０など）は、受け付けた各アドレスを利用して、何れかの関連付けされたアドレスにおいて、当該アドレスに対するデータ値がメモリバンク７２０に格納されるかチェックする。ミスの場合、データ値はメインメモリ１２からフェッチされ、そうでない場合には、データ値は関連付けされたアドレスからフェッチされる。これは、例えば、異なるラインユニット７２に対して独立に、又は同じラインユニット７２の中の異なるメモリバンク７２０に対して独立に、データのｙ−アドレス部分にのみ適用されてもよい。この場合、ラインユニット７２に格納されているラインセグメントのｙ−アドレス間より大きなギャップが存在するかもしれないということに留意すべきである。典型的には、このギャップはＮの整数倍であるが、他のギャップもまた利用可能である。このタイプのキャッシュ処理は、メモリバンク７２０の異なる位置が異なるラインセグメント（ｘ−アドレスの異なる範囲）に対するデータ値を格納するようｘ−アドレスに適用されてもよい。
【００８６】
他の実施例では、図７に示されるようないくつかのメモリ構成がキャッシュ要素としてパラレルに利用され、その後、さらなる出力スイッチが、メモリ構成のそれぞれからの信号からのラインセグメントを結合する。本実施例では、メモリ構成は、キャッシュメモリに対する従来のアソシエイティブマッピング（ａｓｓｏｃｉａｔｉｖｅ ｍａｐｐｉｎｇ）技術を利用して、画像内の各サブウィンドウと関連付けされてもよい。あるブロックがアドレス指定されると、関連するデータを格納するこれらのメモリ構成が起動され、当該ブロックに対するデータ値が、起動されたメモリ構成からパラレルに出力される。
【００８７】
これら複数のメモリ構成にないデータ値を有するブロックがアドレス指定されると、ミスしたデータ値がメインメモリ１２からフェッチされ、これらの構成の１つに格納され、以前のデータ値を置換する。本実施例では、アクティブ領域２０からのデータ値を格納する選択されたメモリ構成が、好ましくは、置換から免除される。
【００８８】
他の実施例では、図１のすべてのキャッシュ要素が、各ラインユニット７２として実現される。本実施例のラインユニットでは、テーブルＶに示されるタイプのデータ値分散スキームが利用可能であり、ラインユニット７２には、共通のラインスイッチ７２２に接続されるそれらの出力を有するラインユニットのグループにアソシエイティブに割り当てされるかもしれない。好ましくは、ラインユニット７２の第１のサブセットが、アクティブ領域２０に対するすべてのデータ値を格納し、ラインユニット７２の第２のサブセットが、アクティブ領域２０の周囲の選択されたサブウィンドウに対するデータ値を格納する。第２のサブセットのサブウィンドウのアドレスは、図１に関して説明されるように置換が行われる。この結果、異なるラインユニットに格納されるサブウィンドウは、所定の空間的関係を有しない。
【符号の説明】
【００８９】
１０ 処理ユニット
１２ メインメモリ
１４ キャッシュメモリユニット
１４０ キャッシュコントローラ
１４４ 出力セレクタ
【特許請求の範囲】
【請求項１】
第１及び第２次元における複数の位置に対して拡がるブロック及びアレイについて、多次元の位置の前記アレイにおける位置の前記ブロックに対するデータ値のパラレルな抽出のための方法であって、
前記第１次元に沿って拡がるＷ個の連続する位置を有するラインセグメントを有する前記アレイにおける位置のウィンドウを規定するステップと、
前記ウィンドウにおける連続する位置の個数Ｗより小さい積Ｓ＊Ｇについて、前記第１次元において連続する複数のＧ個の各位置に対するデータ値を各々が格納するアドレス指定可能な位置を各々が有する複数のＳ個のメモリバンクを各々が有する複数のラインユニットを提供するステップと、
前記メモリバンクの前記ウィンドウにおけるラインセグメントからのデータ値であって、前記ラインセグメントに対するデータ値が格納される前記ラインユニットのＳ個のメモリバンク上にＳ個のグループの循環により循環的に分散され、格納される各ラインセグメントのＧ個の位置の連続するグループに対するデータ値であって、前記ラインユニットのそれぞれに格納される前記第２次元について連続的な各ラインセグメントに対するデータ値を格納するステップと、
前記ブロックの２次元アドレスを受け付けるステップと、
異なる連続するラインセグメントに対するデータ値を出力するため、データ値を格納する複数のメモリバンクが前記ラインセグメント内でパラレルにアドレス指定され、複数のラインユニットをパラレルにアドレス指定するステップと、
前記アドレス指定されたメモリバンクによって出力されるデータ値から、前記ラインセグメントに対するデータ値を選択するステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
各出力が、前記ブロックのアドレスの第１の次元に関する所定のオフセットによる位置に対するデータ値を出力するように、前記ラインセグメントに対するデータ値が格納される前記メモリバンクにおけるスタートアドレスに対する前記ブロックのアドレスに応じて、前記アドレス指定されたメモリバンクからのデータ値を各自の出力に送るステップと、
各出力が、前記ブロックのアドレスの第２の次元に関する所定のオフセットによる位置に対するデータ値を出力するように、前記第２の次元の最も小さなアドレスを有するデータ値が格納されるラインユニットのシーケンス番号に対する前記ブロックのアドレスに応じて、各自のラインユニットからのデータ値を前記各自の出力に送るステップと、
を有することを特徴とする方法。
【請求項３】
請求項２記載の方法であって、
前記移動されたウィンドウの位置の一部が、前記当初のウィンドウの位置に一致するように、前記アレイのおける前記ウィンドウの位置を移動して、前記ウィンドウを再規定するステップと、
前記ウィンドウが連続的に移動されるとき、前記ウィンドウに対するデータ値のスタートアドレスが、前記ラインユニットのメモリバンクを循環するように、前記メモリバンクにおいて、前記移動されたウィンドウに属しない位置に対するデータ値を前記移動されたウィンドウに属するが、前記当初のウィンドウには属しない位置に対するデータ値と置換するステップと、
前記規定されたウィンドウに関する所定の相対位置における位置に対するデータ値が格納されるメモリバンク及び／又はラインユニットを示す情報を維持するステップと、
を有することを特徴とする方法。
【請求項４】
第１及び第２次元に拡がる多次元のデータ値のアレイを処理するデータ処理装置であって、
各ラインユニットが、複数のＧ個のデータ値を各位置が格納するアドレス指定可能な位置を各メモリバンクが有する複数のＳ個の各自のメモリバンクを有する複数のラインユニットと、
前記ラインユニットのメモリバンクに前記アレイからのデータ値を書き込むよう構成されるキャッシュ管理ユニットであって、前記アレイにおける前記第１方向に沿って拡がる各自のラインに沿った位置に対する、又はこのようなラインの各自のインタリーブされたセットに対するデータ値が、各自のラインユニットに書き込まれ、前記メモリバンクの各自のアドレス指定可能な位置が、それぞれ前記ラインに沿ったＧ個の連続する位置の各グループに対するデータ値を格納し、連続するグループが、前記グループが属するラインに対するデータ値を格納する前記ラインユニットにおけるメモリバンク上に循環的に繰り返される方法により分散され、前記キャッシュ管理ユニットが、前記アレイにおける位置のスライドウィンドウに対するデータ値を維持するよう構成され、前記ウィンドウの移動により前記ウィンドウから離脱した古い位置に対するデータ値は、前記メモリバンクにおいて、前記古い位置として同一のライン又はインタリーブされたラインのセットからの前記ウィンドウにおける新たなデータ値と置換されるキャッシュ管理ユニットと、
前記ラインユニットに接続される抽出回路であって、当該抽出回路は、前記アレイにおける位置のブロックのアドレスを受け付けるアドレス入力と、前記ブロックにおける位置に対するデータ値をパラレルに出力する出力とを有し、前記ブロックは、前記第１次元に沿った積Ｇ＊Ｓより小さなＷ個の連続する位置をそれぞれ有するラインセグメントを有し、前記ブロックのアドレスは、グループ内解像度を有し、当該抽出ユニットは、複数のラインユニットから前記ラインセグメントのそれぞれに対するブロックからのデータ値をパラレルに抽出し、前記ラインユニットのメモリバンクから前記ラインセグメントからの少なくとも１つの位置を有する各グループに対する前記ブロックからのデータ値をパラレルに抽出するよう構成され、当該抽出ユニットは、あるグループの位置が前記ブロックと部分的に重複する場合、前記あるグループ内のデータ値のサブセットを出力のため選択し、前記抽出されたデータ値をパラレルに出力するよう構成される抽出回路と、
を有することを特徴とする装置。
【請求項５】
請求項４記載のデータ処理装置であって、
前記抽出回路は、
前記ブロックに対する各自の所定の位置における位置に対するデータ値を前記出力の所定の各出力に送るよう構成されるスイッチ回路と、
前記抽出回路のアドレス入力に接続されるブロックアドレス入力と、前記ラインユニットに接続されるアドレス出力と、前記スイッチ回路に接続される制御出力とを有し、前記ウィンドウにおける所定の位置に対するデータ値が格納されるメモリアドレスの循環的オフセットを表す情報を維持し、該情報と前記所定の位置に関する前記アドレス指定されたブロックの相対位置に応じて、アドレスを選択されたメモリブロックに供給するよう構成されるアドレッシングユニットと、
を有することを特徴とする装置。
【請求項１】
第１及び第２次元における複数の位置に対して拡がるブロック及びアレイについて、多次元の位置の前記アレイにおける位置の前記ブロックに対するデータ値のパラレルな抽出のための方法であって、
前記第１次元に沿って拡がるＷ個の連続する位置を有するラインセグメントを有する前記アレイにおける位置のウィンドウを規定するステップと、
前記ウィンドウにおける連続する位置の個数Ｗより小さい積Ｓ＊Ｇについて、前記第１次元において連続する複数のＧ個の各位置に対するデータ値を各々が格納するアドレス指定可能な位置を各々が有する複数のＳ個のメモリバンクを各々が有する複数のラインユニットを提供するステップと、
前記メモリバンクの前記ウィンドウにおけるラインセグメントからのデータ値であって、前記ラインセグメントに対するデータ値が格納される前記ラインユニットのＳ個のメモリバンク上にＳ個のグループの循環により循環的に分散され、格納される各ラインセグメントのＧ個の位置の連続するグループに対するデータ値であって、前記ラインユニットのそれぞれに格納される前記第２次元について連続的な各ラインセグメントに対するデータ値を格納するステップと、
前記ブロックの２次元アドレスを受け付けるステップと、
異なる連続するラインセグメントに対するデータ値を出力するため、データ値を格納する複数のメモリバンクが前記ラインセグメント内でパラレルにアドレス指定され、複数のラインユニットをパラレルにアドレス指定するステップと、
前記アドレス指定されたメモリバンクによって出力されるデータ値から、前記ラインセグメントに対するデータ値を選択するステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
各出力が、前記ブロックのアドレスの第１の次元に関する所定のオフセットによる位置に対するデータ値を出力するように、前記ラインセグメントに対するデータ値が格納される前記メモリバンクにおけるスタートアドレスに対する前記ブロックのアドレスに応じて、前記アドレス指定されたメモリバンクからのデータ値を各自の出力に送るステップと、
各出力が、前記ブロックのアドレスの第２の次元に関する所定のオフセットによる位置に対するデータ値を出力するように、前記第２の次元の最も小さなアドレスを有するデータ値が格納されるラインユニットのシーケンス番号に対する前記ブロックのアドレスに応じて、各自のラインユニットからのデータ値を前記各自の出力に送るステップと、
を有することを特徴とする方法。
【請求項３】
請求項２記載の方法であって、
前記移動されたウィンドウの位置の一部が、前記当初のウィンドウの位置に一致するように、前記アレイのおける前記ウィンドウの位置を移動して、前記ウィンドウを再規定するステップと、
前記ウィンドウが連続的に移動されるとき、前記ウィンドウに対するデータ値のスタートアドレスが、前記ラインユニットのメモリバンクを循環するように、前記メモリバンクにおいて、前記移動されたウィンドウに属しない位置に対するデータ値を前記移動されたウィンドウに属するが、前記当初のウィンドウには属しない位置に対するデータ値と置換するステップと、
前記規定されたウィンドウに関する所定の相対位置における位置に対するデータ値が格納されるメモリバンク及び／又はラインユニットを示す情報を維持するステップと、
を有することを特徴とする方法。
【請求項４】
第１及び第２次元に拡がる多次元のデータ値のアレイを処理するデータ処理装置であって、
各ラインユニットが、複数のＧ個のデータ値を各位置が格納するアドレス指定可能な位置を各メモリバンクが有する複数のＳ個の各自のメモリバンクを有する複数のラインユニットと、
前記ラインユニットのメモリバンクに前記アレイからのデータ値を書き込むよう構成されるキャッシュ管理ユニットであって、前記アレイにおける前記第１方向に沿って拡がる各自のラインに沿った位置に対する、又はこのようなラインの各自のインタリーブされたセットに対するデータ値が、各自のラインユニットに書き込まれ、前記メモリバンクの各自のアドレス指定可能な位置が、それぞれ前記ラインに沿ったＧ個の連続する位置の各グループに対するデータ値を格納し、連続するグループが、前記グループが属するラインに対するデータ値を格納する前記ラインユニットにおけるメモリバンク上に循環的に繰り返される方法により分散され、前記キャッシュ管理ユニットが、前記アレイにおける位置のスライドウィンドウに対するデータ値を維持するよう構成され、前記ウィンドウの移動により前記ウィンドウから離脱した古い位置に対するデータ値は、前記メモリバンクにおいて、前記古い位置として同一のライン又はインタリーブされたラインのセットからの前記ウィンドウにおける新たなデータ値と置換されるキャッシュ管理ユニットと、
前記ラインユニットに接続される抽出回路であって、当該抽出回路は、前記アレイにおける位置のブロックのアドレスを受け付けるアドレス入力と、前記ブロックにおける位置に対するデータ値をパラレルに出力する出力とを有し、前記ブロックは、前記第１次元に沿った積Ｇ＊Ｓより小さなＷ個の連続する位置をそれぞれ有するラインセグメントを有し、前記ブロックのアドレスは、グループ内解像度を有し、当該抽出ユニットは、複数のラインユニットから前記ラインセグメントのそれぞれに対するブロックからのデータ値をパラレルに抽出し、前記ラインユニットのメモリバンクから前記ラインセグメントからの少なくとも１つの位置を有する各グループに対する前記ブロックからのデータ値をパラレルに抽出するよう構成され、当該抽出ユニットは、あるグループの位置が前記ブロックと部分的に重複する場合、前記あるグループ内のデータ値のサブセットを出力のため選択し、前記抽出されたデータ値をパラレルに出力するよう構成される抽出回路と、
を有することを特徴とする装置。
【請求項５】
請求項４記載のデータ処理装置であって、
前記抽出回路は、
前記ブロックに対する各自の所定の位置における位置に対するデータ値を前記出力の所定の各出力に送るよう構成されるスイッチ回路と、
前記抽出回路のアドレス入力に接続されるブロックアドレス入力と、前記ラインユニットに接続されるアドレス出力と、前記スイッチ回路に接続される制御出力とを有し、前記ウィンドウにおける所定の位置に対するデータ値が格納されるメモリアドレスの循環的オフセットを表す情報を維持し、該情報と前記所定の位置に関する前記アドレス指定されたブロックの相対位置に応じて、アドレスを選択されたメモリブロックに供給するよう構成されるアドレッシングユニットと、
を有することを特徴とする装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図６ａ】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図６ａ】
【図７】
【公開番号】特開２０１１−１５４７０９（Ｐ２０１１−１５４７０９Ａ）
【公開日】平成２３年８月１１日（２０１１．８．１１）
【国際特許分類】
【出願番号】特願２０１１−６６４８６（Ｐ２０１１−６６４８６）
【出願日】平成２３年３月２４日（２０１１．３．２４）
【分割の表示】特願２００７−５０９０４８（Ｐ２００７−５０９０４８）の分割
【原出願日】平成１７年４月２１日（２００５．４．２１）
【出願人】（５１１０３０４９３）
【Ｆターム（参考）】
【公開日】平成２３年８月１１日（２０１１．８．１１）
【国際特許分類】
【出願日】平成２３年３月２４日（２０１１．３．２４）
【分割の表示】特願２００７−５０９０４８（Ｐ２００７−５０９０４８）の分割
【原出願日】平成１７年４月２１日（２００５．４．２１）
【出願人】（５１１０３０４９３）
【Ｆターム（参考）】
[ Back to top ]