(57)【要約】【課題】多次元映像データを処理するためのシステム、データ構造、および方法を提供する。【解決手段】多次元データを処理するためのシステム、プロセッサ、データ構造、および方法が提供される。第１の多次元データ配列の部分配列内において異なる次元に格納されている複数のデータ要素が互いに相関していると特定または判断される。異なる次元に存在する複数の相関データ要素は、第２のデータ配列の単一次元内にて順序付けられた位置にマッピングされる。単一次元に順番に格納された複数のデータ要素は、少なくともすべての相関データ要素が取得されるまで、各演算サイクルでデータ配列から反復的に取得される。その後、これらの相関データ要素が処理される。【選択図】図１
2011138511.tif 000002
【特許請求の範囲】
【請求項１】
多次元データを処理するための方法であって、
コンピュータメモリ内にある多次元の第１のデータ配列の部分配列内にて異なる次元に格納されている複数の相関データ要素を特定すること、
前記第１のデータ配列からの前記複数の相関データ要素を、前記コンピュータメモリ内にある第２のデータ配列の単一次元内に順序付けられた位置にマッピングすること、
前記第２のデータ配列の前記単一次元に順番に格納されいてる複数のデータ要素を、少なくともすべての前記相関データ要素が取得されるまで各演算サイクルで反復的に取得すること、
前記相関データ要素を処理すること、
を備える方法。
【請求項２】
すべての前記相関データ要素が一緒に処理される、請求項１に記載の方法。
【請求項３】
前記取得された複数のデータ要素と相関する前記相関データ要素の一部が前記コンピュータメモリから取得されていない場合には、前記取得された各データ要素が処理されない、請求項１に記載の方法。
【請求項４】
前記第１のデータ配列の第１の部分配列内に格納されているデータ要素が、前記部分配列内における行の順序で一度に１行ずつ、かつ前記部分配列の各行に順番にリストされている順序で、前記第２のデータ配列の単一次元にマッピングされる、請求項１に記載の方法。
【請求項５】
前記第１のデータ配列の第１の部分配列からマッピングされるデータ要素は、前記第１のデータ配列の異なる第２の部分配列からマッピングされる任意の２つの相関データ要素間における前記第２のデータ配列の単一次元内には位置しておらず且つその単一次元内とは相関していない、請求項１に記載の方法。
【請求項６】
前記第１のデータ配列の第１の部分配列内に垂直にスタックされている複数行のデータ要素が、前記第２のデータ配列の単一次元内に並んで整列している、請求項１に記載の方法。
【請求項７】
前記多次元データが映像または画像データである、請求項１に記載の方法。
【請求項８】
前記多次元の第１のデータ配列と前記単一次元の第２のデータ配列との両方に含まれる各データ要素が、映像フレームまたは画像における個別のピクセルに対応する、請求項７に記載の方法。
【請求項９】
多次元データを処理するためのシステムであって、
多次元の第１のデータ配列の部分配列内において異なる次元に複数の相関データ要素を格納するためのコンピュータメモリと、
前記第１のデータ配列からの前記複数の相関データ要素を、前記コンピュータメモリにおける第２のデータ配列の単一次元内に順序付けられた位置にマッピングするマッピング部と、
前記第２のデータ配列の前記単一次元に順番に格納されている複数のデータ要素を、少なくともすべての前記相関データ要素が取得されるまで各演算サイクルで反復的に取得し、前記相関データ要素を処理するプロセッサと、
を備えるシステム。
【請求項１０】
前記プロセッサがすべての前記相関データ要素を一緒に処理する、請求項９に記載のシステム。
【請求項１１】
前記取得されたデータ要素と相関する前記相関データ要素の一部が前記コンピュータメモリから取得されていない場合には、前記プロセッサは、前記取得された各データ要素を処理しない、請求項９に記載のシステム。
【請求項１２】
前記マッピング部は、前記第１のデータ配列の第１の部分配列内に格納されている前記データ要素を、前記部分配列内における行の順序で一度に１行ずつ、かつ前記部分配列の各行に順番にリストされている順序で、前記第２のデータ配列の単一次元にマッピングする、請求項９に記載のシステム。
【請求項１３】
前記第１の部分配列内に格納されているデータ要素は、前記第１のデータ配列の異なる第２の部分配列内に格納されているデータ要素と相関しておらず、前記マッピング部は、前記第２の部分配列から前記第２のデータ配列の単一次元にマッピングされる任意の２つの相関データ要素間には前記第１の部分配列からのデータ要素をマッピングしない、請求項９に記載のシステム。
【請求項１４】
前記マッピング部は、前記第１のデータ配列の第１の部分配列内に垂直にスタックされている複数行のデータ要素を前記第２のデータ配列の単一次元内に並べて整列する、請求項９に記載のシステム。
【請求項１５】
前記多次元データが映像または画像データである、請求項９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像および画像アプリケーションに関し、より詳細には、映像および撮像アプリケーションなどにおける多次元データを処理する方法に関する。
【背景技術】
【０００２】
映像および撮像アプリケーションは、コンピュータメモリからデータを処理し得る。映像および撮像データは、多次元データ配列に格納され得る。多次元データ配列内の各データ要素は、画像または映像フレーム内のピクセルと一意に関連付けられた値を有し得る。多次元データ配列は、ブロックまたは部分配列に分割されることがあり、各々が多次元データ配列内の複数の行と列とにまたがる。各部分配列内のデータ要素は、従前の映像処理メカニズムに従って部分配列内のすべてのデータ要素がグループとして一緒に処理されるように関連し、相関し、または共依存し得る。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
プロセッサは、データ要素のバースト、バンドルまたはグループという形でコンピュータメモリから映像または画像データを取得し得る。バーストは、多次元データ配列の行で順番に並べられた複数のデータ要素を含み得る。例えば、多次元データ配列の単一行に順番にリストされている８個または１６個のデータ要素からなるバーストが各フェッチ動作で取得され得る。データ要素は１行ずつ順番に取得されるため、（単一行に順番にリストされている）取得されたデータ要素のバーストまたはグループは（部分配列の複数行にまたがる）相関データ要素のグループに対応しない場合が多い。そのため、一緒に処理される各部分配列内のデータをすべて取得するために、プロセッサは複数回のフェッチ動作を繰り返して、部分配列の各行が相関しているデータのグループを適切に処理し得る。
【０００４】
さらに、バーストサイズが部分配列の行に存在するデータ要素の数よりも大きい場合には、各バーストで取得されたデータは、部分配列外の行にデータ要素を順番に含み得る。部分配列外のデータ要素は該部分配列内のデータ要素と相関していないため、相関データ集合を処理するためのプロセッサリソースが浪費され得る。
【課題を解決するための手段】
【０００５】
本発明の一態様は、多次元データを処理するための方法である。当該方法は、コンピュータメモリ内にある多次元の第１のデータ配列の部分配列内にて異なる次元に格納されている複数の相関データ要素を特定すること、前記第１のデータ配列からの前記複数の相関データ要素を、前記コンピュータメモリ内にある第２のデータ配列の単一次元内に順序付けられた位置にマッピングすること、前記第２のデータ配列の前記単一次元に順番に格納されている複数のデータ要素を、少なくともすべての前記相関データ要素が取得されるまで各演算サイクルで反復的に取得すること、前記相関データ要素を処理すること、を備える。
【０００６】
本発明の別の態様は、多次元データを処理するためのシステムである。当該システムは、多次元の第１のデータ配列の部分配列内において異なる次元に複数の相関データ要素を格納するためのコンピュータメモリと、前記第１のデータ配列からの前記複数の相関データ要素を、前記コンピュータメモリにおける第２のデータ配列の単一次元内に順序付けられた位置にマッピングするマッピング部と、前記第２のデータ配列の前記単一次元に順番に格納されている複数のデータ要素を、少なくともすべての前記相関データ要素が取得されるまで各演算サイクルで反復的に取得し、前記相関データ要素を処理するプロセッサと、を備える。
【０００７】
本発明の構成および動作方法は、本発明の目的、特徴、および利点と共に、添付の図面に従って、以下の詳細な説明を参照することによって最も良好に理解され得る。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態にかかるシステムの模式図である。
【図２】本発明の実施形態を理解する上で有用な映像および撮像データを格納するための多次元データ配列である。
【図３】本発明の実施形態にかかる映像および画像データを格納するためのデータ構造の模式図である。
【図４】本発明の実施形態にかかる方法のフローチャートである。
【発明を実施するための形態】
【０００９】
以下、本発明の具体的な実施形態について図面を参照して説明する。説明の簡潔化および明確化のため、図示する要素は必ずしも正確な尺度で描かれてはいない。例えば、一部の要素の寸法が、明確化のために他の要素に比して誇張されている場合がある。さらに、対応要素または類似要素を示す場合には、適宜、参照番号を図中で繰り返す。
【００１０】
以下では、本発明の各種態様について説明する。本発明をより理解するために、具体的な構成および詳細が記載されているが、本明細書に明示されているこれらの具体的な詳細によらずに本発明を実現し得ることも、当業者には明らかである。さらに、本発明を曖昧にしないために、周知の特徴は省略または単純化される場合がある。
【００１１】
別段の記載がない限り、以下の説明から明らかなように、明細書の説明全体にわたり「処理する」、「演算する」、「計算する」、「判断する」などの用語が用いられている場合には、演算システムのレジスタおよび／またはメモリ内で電子的な量など物理的な量として表されるデータを操作したり、これらのデータをコンピューティングシステムのメモリ、レジスタ、あるいは他のかかる情報記憶装置、伝送装置、または表示装置内の物理的な量として同様に表される他のデータに変換したりするコンピュータあるいは演算システム、または同様の電子コンピューティング装置の動作および／または処理を言及する。
【００１２】
本発明の実施形態は、（例えば図２に示すような）多次元部分配列内の複数行全体にリストされるすべての相関要素が、（例えば図３に示すような）一次元データ配列の単一行に順番に並ぶようにデータ要素を並べたり、マッピングしたりするシステム、プロセッサ、および方法を含む。プロセッサは、コンピュータメモリまたは単一行に存在するバーストまたは順番にリストされている複数の要素からデータ要素を取得するので、その一次元または単一行のデータ配列を使用する際には、単一部分配列からすべての相関要素が順に取得され、これにより、他の部分配列からの中間データ要素がその間で取得されないようになっている。例えば、マッピング部は、複数（例えば１６個）のデータ要素を多次元（例えば２Ｄ）のデータ配列の多次元部分配列（例えば４×４個）から一次元の行またはデータ配列（例えば１×１６個）のセグメントに並べ替え、マッピング、または順番に変換し得る。プロセッサは、１６個のデータ要素で構成される１個のバーストまたは各々８個のデータ要素で構成される２個のバーストにおける一次元行セグメント内にリストされたデータ要素を順番に取得し得る。
【００１３】
図１は、本発明の実施形態にかかる装置例の模式図である。
装置１００は、コンピュータ装置、映像あるいは画像のキャプチャあるいは再生装置、携帯装置、または携帯電話、パーソナル携帯情報機器（ＰＤＡ）、テレビゲーム機など、その他任意のデジタル装置を含み得る。装置１００は、映像または画像データを記録、保存、格納、処理、編集、表示、投影、受信、転送、あるいはその他の方法で使用または操作するための一連の命令を実行することのできる任意の装置を含み得る。装置１００は、入力装置１０１を含み得る。装置１００が記録機能を備えている場合、入力装置１０１は、物理的対象物から発せられる光波の反射を経てその物理的対象物の画像をキャプチャするためのビデオカメラなどの撮像装置、および／または音声波の投影を記録するための音声記録装置を含み得る。撮像装置は、イメージャ、１つ以上のレンズ、プリズム、またはミラーなどを含み、音声記録装置は、音声レコーダやマイクロフォンなどを含む。
【００１４】
装置１００が画像処理機能を備えている場合には、入力装置１０１は、ポインティング装置、クリックホイールすなわちマウス、キー、タッチスクリーン、音声認識を使用したレコーダ／マイクロフォン、他の入力コンポーネントを含み得る。これらはユーザが映像または画像の処理動作を制御、修正、または選択するためのものである。装置１００は、プロセッサ１によって実行される一連の命令に従ってユーザインターフェースに映像または画像データを表示するための出力装置１０２（例えばモニタ、プロジェクタ、スクリーン、プリンタ、またはディスプレイ）を含み得る。
【００１５】
例示の装置１００は、プロセッサ１を含み得る。プロセッサ１は、中央処理装置（ＣＰＵ）、デジタル信号プロセッサ（ＤＳＰ）、マイクロプロセッサ、コントローラ、チップ、マイクロチップ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）あるいはその他任意の集積回路（ＩＣ）、またはその他任意の適切な多目的あるいは具体的なプロセッサまたはコントローラを含み得る。
【００１６】
装置１００は、データメモリ部２とメモリコントローラ３とを含み得る。メモリコントローラ３は、例えば１つ以上のデータバス８を介して、プロセッサ１と、メモリ部２と、出力装置１０２との間で行われるデータの転送を制御し得る。装置１００は、例えば１つ以上のデータバス９を介して、出力装置１０２に表示されるデータの転送を制御するためのディスプレイコントローラ５を含み得る。
【００１７】
装置１００は、記憶部４を含み得る。記憶部４が映像または画像データを圧縮された形態で格納し得るのに対し、データメモリ部２は、映像または画像データを圧縮されていない形態で格納し得る。ただし、圧縮データまたは非圧縮データは、記憶部４およびメモリ部２のいずれにも格納することができ、データをメモリに格納するための他の機器が使用されてもよい。各非圧縮データ要素が画像または映像フレーム内の単一ピクセルと一意に関連付けられた値を有し得るのに対し、各圧縮データ要素は、映像ストリームまたは動画の連続フレームにおけるピクセル値の変化または変更を表し得る。本明細書で使用された場合には、別段の記載がない限り、データ要素といえば、例えば、単一の画像フレームにおけるピクセル値に関連する非圧縮データ要素を一般に言及し、例えば、連続的な画像フレームにおけるピクセル値の変更に関連する非圧縮データ要素を言及しない。非圧縮データが（例えば図２のような）多次元データ配列または（例えば図３のような）一次元データ配列で表され得るのに対し、圧縮データは、データストリームまたは一次元（１Ｄ）のデータ配列（図示せず）として表され得る。
【００１８】
データメモリ部２が長期または短期のメモリユニットであり得るのに対し、記憶部４は長期のメモリユニットであり得る。記憶部４は、映像、音声、および／または画像レコーダなどの外部装置内に含まれるディスクあるいはテープドライブまたはメモリなど、１つ以上の外部ドライブを含み得る。データメモリ部２および記憶部４は、例えば、ランダムアクセスメモリ（ＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、フラッシュメモリ、キャッシュメモリ、揮発性メモリ、不揮発性メモリ、またはその他適切なメモリユニットあるいは記憶ユニットを含み得る。データメモリ部２および記憶部４は、分離型（例えば「オフチップ」）または統合型（例えば「オンチップ」）のメモリユニットとして実装され得る。マルチレベルメモリすなわちメモリ階層が存在するいくつかの実施形態では、記憶部４がオフチップでデータメモリ部２がオンチップである場合がある。例えば、データメモリ部２は、Ｌ−１キャッシュまたはＬ−２キャッシュを含み得る。Ｌ−１キャッシュが、Ｌ−２キャッシュよりもプロセッサ１との統合性が比較的強い場合があり、プロセッサ・クロック・レートで動作し得るのに対し、Ｌ−２キャッシュは、Ｌ−１キャッシュよりもプロセッサ１との統合性が比較的弱い場合があり、プロセッサ・クロック・レートとは異なるレートで動作し得る。一実施形態において、プロセッサ１は、ダイレクトメモリアクセス（ＤＭＡ）ユニットを使用して、データメモリ部２および／または記憶部４などのメモリユニットとの間でデータを読み込み、書き込み、および／または転送し得る。その他のメモリアーキテクチャまたは追加メモリアーキテクチャも使用され得る。
【００１９】
プロセッサ１は、フェッチ部１２と、デコード部６と、実行部１１とを含み得る。プロセッサ１は、データメモリ部２および／または記憶部４に対してデータをリクエストし、そこからデータを取得し、処理し、一般に、そのデータに対して実行される動作のパイプラインフローを制御し得る。フェッチ部１２は、各フェッチ動作または演算サイクルによって、データメモリ部２に格納されているデータ構造の単一行に含まれるバーストまたは順序付けられたデータ要素を取得またはフェッチし得る。あるいは、フェッチ部１２は、各フェッチ動作で、データメモリ部２に格納されているデータ構造の単一列（または斜めあるいは別の所定パターン）に含まれる順序付けられたデータ要素を取得し得る。フェッチ部１２は、命令をディスパッチ、デコード、または実行する前に、ローカルキューに入っているフェッチされたデータを並べ得る。プロセッサ１は、フェッチされたデータをただちに処理、デコード、および／または実行する場合、あるいはフェッチされたデータを、そのデータと相関しているすべてのデータ要素がデータメモリ部２からフェッチされるまでバッファまたはキャッシュなどの一時記憶部１３に格納し得る。
【００２０】
全ての相関データ要素集合がプロセッサ１によってフェッチおよびディスパッチされると、デコード部６がそのデータをデコードして、次に実行部１１がそのデータを実行し得る。プロセッサ１は、命令ごとに、例えば以下の順序付けられたパイプライン段階を実行し得る。
【００２１】
段階（ａ）：メモリアドレス（プロセッサ１とメモリコントローラ３とによって行われる）。
段階（ｂ）：データメモリのフェッチ（フェッチ部１２によって行われる）。
【００２２】
段階（ｃ）：命令のディスパッチ（プロセッサ１によって行われる）。
段階（ｄ）：命令のデコード（デコード部６によって行われる）。
段階（ｅ）：実行、データメモリアクセス、データ再書き込み（実行部１１、プロセッサ１、およびメモリコントローラ３によって行われる）。
【００２３】
ただし、当業者であれば、本発明の実施形態が特定の順序に制限されることはなく、他のパイプライン段階または付加的なパイプライン段階、および操作装置の構成部品が使用され得ることを理解し得る。
【００２４】
多次元の映像または画像データを処理する際、その多次元の１つの次元に含まれる各データ要素は、その多次元の他の次元に含まれるデータ要素と相関し得るか一緒に処理され得る。相関データ集合が多次元によって定義されている場合には、その多次元の全座標が、任意の適切な映像処理メカニズムに従ってグループとして一緒に処理され、完全なまたは正確なデータを生成する。デカルト空間（ｘｙｚ）における点位置が、（ｘ）だけでなく、（ｘ）、（ｙ）、および（ｚ）のすべての値によって定義され得るのと同じように、一片の多次元の映像または画像データは、相関しているすべての多次元データ要素によって定義され得る。
【００２５】
多次元の映像または画像データは、多次元データ構造に格納され得る。多次元データ構造は、複数の多次元部分配列を含み、その各々が、個別の相関データ要素集合またはその個別の集合と関連付けられたピクセルに一意に対応している。各部分配列に含まれる相関データ要素は、多次元データ部分配列の複数の行と列とに配置され得る。
【００２６】
装置１００は、データメモリ部２に格納されているデータ要素の並べ替え、マッピング、あるいは（例えば図２に示すような）多次元データ配列から（例えば図３に示すような）一次元データ構造への変換を行うためのマッピング部７を含み得る。マッピング部７は、データメモリ部２に格納されているデータ要素を、そのメモリ内の１つの箇所またはアドレスから別の箇所またはアドレスまで移すことが可能であると共に、データ要素自体を実際に移したり再配置したりすることなくデータ要素のアドレスまたはポインタを並べ替えあるいは変換することが可能である。いくつかの実施形態では、データ要素の並べ替え、マッピング、または変換は、各データ要素を処理するデコード段階で実行されることや、あるいは、上述したデータ処理の段階に加え、別の処理段階もしくは個別のマッピング段階で実行される場合がある。マッピング部７は、制御モジュールまたはアプリケーションとして、独立した形またはプロセッサ１に統合された形で実装され得る。
【００２７】
図２は、本発明の実施形態を理解する上で役立つ映像および撮像データを格納するための二次元（２Ｄ）データ配列を模式的に表している。この二次元（２Ｄ）データ配列は、例えば４×４のデータ要素部分配列などのブロックまたは部分配列を含み、各々が個別の相関データ要素集合を含む。例えば、（４×４）の各部分配列に含まれるすべての相関データ要素がメモリから取得され、例えば順序付けられたパイプラインスロットで処理される。
【００２８】
相関データを取得するために、プロセッサは、複数回のフェッチ動作サイクルを実行して、部分配列の複数行の各々に含まれるデータ要素を個別にフェッチする。例えば、プロセッサは、異なるそれぞれのバーストまたはフェッチサイクルにおいて、図２の（４×４）の各部分配列を構成する「４つ」の行の各々から一度に１行ずつデータ要素を取得し得る。したがって、（４×４）の部分配列を構成する「４つ」の行に含まれる「１６個」の相関データ要素をすべて取得するには、プロセッサが、「４回」の個別バーストまたは演算サイクルでデータメモリにアクセスする。
【００２９】
各行に含まれる最初の「４個」の順序付けられたデータ要素だけが相関しているため、各バーストに含まれるデータ要素の数を増やして、例えば８個または１６個のように「４個」よりも大きくすると、かかるプロセッサは、（例えば部分配列内にある）最初の「４個」のデータ要素と相関していない（例えば部分配列外にある）各行に含まれるデータ要素を取得することになる。したがって、従来のプロセッサを使用した場合には、バーストサイズを増やしても、相関データ要素を取得するために必要なフェッチサイクルの数には影響を与えず、この実施例では、各バーストで取得されるデータ要素の数に関係なく同じ（例えば４回）である。
【００３０】
図３は、本発明のいくつかの実施形態に従って映像および画像データを格納するためのデータ構造を模式的に表している。図３では、データ構造が、（例えば図２における同じ部分配列と関連付けられている）すべての相関データ要素を単一の次元または行に順番にリストされている。
【００３１】
図２に示すメカニズムとは対照的に、本発明の実施形態にかかる図３では、相関データ要素がデータメモリ部２に一次元データ構造として格納されている。図３に示す実施形態では、「１６個」の相関データ要素の各集合が一次元（１×１６）のデータ配列または行に配置されている。プロセッサ１は、単一行に順番に格納されているデータ要素のバーストにおいて各フェッチサイクルでデータ要素を取得し、（１×１６）行から全「１６個」の相関データ要素を取得するので、バーストが「１６個」または「８個」のデータ要素を含む場合には、プロセッサ１が、それぞれ「１回」または「２回」のバーストまたはフェッチサイクルでデータメモリにアクセスし得る。したがって、「１６個」の相関データ要素の集合をメモリから取得するのに、図２に示す配置だと「４回」の個別バーストまたはフェッチサイクルを使用する必要があるのに対し、本発明の実施形態では、「１回」または「２回」のバーストまたはフェッチサイクルを使用し得るに過ぎないことから、演算の時間および効率という点で大きく有利となる。
【００３２】
図２の上記実施例では、プロセッサが、２Ｄデータ配列から４回の個別バーストまたはフェッチサイクルでデータを取得し得る。例えば、図２において８個の要素のバーストの場合、バースト１は行１の要素０〜７を含み、バースト２は行２の要素１９２０〜１９２７を含み、バースト３は行３の要素３８４０〜３８４７を含み、バースト４は行４の要素５７６０〜５７６７を含み得る。プロセッサによって取得されたデータ要素の半分のみが相関するものとなる。本発明の実施形態によれば、プロセッサ１は、８個または１６個の要素のバーストに対して、それぞれ「２回」または「１回」のバーストまたはフェッチサイクルでデータを取得する。
【００３３】
図３において、８個の要素のバーストを使用した場合、バースト１は、単一行すなわち一次元配列の要素０、１、２、３、１９２０、１９２１、１９２２、および１９２３を含み、バースト２は、単一行すなわち一次元配列の要素３８４０、３８４１、３８４２、３８４３、５７６０、５７６１、５７６２、および５７６３を含み得る。図３において、単一の１６要素バーストは、単一行すなわち一次元配列の要素０、１、２、３、１９２０、１９２１、１９２２、１９２３、３８４０、３８４１、３８４２、３８４３、５７６０、５７６１、５７６２、および５７６３を含み得る。本発明の実施形態によれば、「１回」または「２回」のバーストでプロセッサ１によって取得されたデータ要素がすべて相関している。
【００３４】
すなわち、図２の配列を使用するプロセッサは、各フェッチサイクルで、例えば、図３の配列を使用して本発明の実施形態に従い動作するプロセッサと同じ総数のデータ要素を取得し得るが、相関データ要素と非相関データ要素との両方を取得しているのに対して、本発明の実施形態に従い動作するプロセッサは相関データ要素のみを取得する。したがって、本発明の実施形態は、より少ない連続のバーストとフェッチサイクルとを使用して、全相関データ集合を取得することができる。例えば、４つのバーストが各々８個の要素を有する場合、両方法で、２つの相関データ集合が取得される。しかしながら、個々の相関データ集合を取得するのに、従来の方法では４回のクロックサイクルを要するものの、本発明の実施形態によれば１回または２回のクロックサイクルしか要しない。各データ要素は、それらと相関しているすべてのデータ要素が処理された後に共に処理される可能性があるに過ぎないので、本発明の実施形態に従って動作するシステムは、データを処理するのに使用するフェッチサイクルが、従来のシステムよりも（例えば２回または４回）少なく、待ち時間も短い。
【００３５】
いくつかの実施形態では、データ要素がまず、図３の一次元データ構造としてデータメモリ部２に格納されている。他の実施形態では、データ要素がまず、（例えば図２に示すような）多次元データ配列としてデータメモリ部２に格納され、（図１のマッピング部７などの）ユニットがデータ要素を並べ替え、マッピング、変換、連続化、拡張、または再配列して、（例えば図３に示すような）一次元データ構造を形成し得る。例えば、データ要素は、各データ要素を処理するデコード段階で変換され得る。
【００３６】
一実施例では、多次元データ配列にリストされている行の順序で、一度に１行ずつ各行に順番にリストされているデータ要素は、（例えば図１のマッピング部７によって）一次元配列の単一行における線形的な順序で変換またはマッピングされ得る。すなわち、多次元の部分配列またはグリッドで垂直に「スタック」されているデータ要素の行は、一次元配列の単一行に含まれる一連の要素として横方向に展開または整列される。一般に、（Ｎ×Ｍ）の部分配列では、ａｉｊ、１≦ｉ≦Ｍ、１≦ｊ≦Ｎという相関データ要素が、例えばａ１１．．．．ａ１Ｎ、ａ２１、…、ａ２Ｎ、…、ａ３１、…、ａ３Ｎ、…、ａＭ１、…、ａＭＮという順序で行に配列され得る。別の実施形態では、任意の２つの相関データ要素の間に、（例えば異なる部分配列からの）非相関データ要素が存在しない限り、（例えば同じ多次元部分配列からの）相関データ要素が一次元の部分配列で任意の順序で配列され得る。
【００３７】
バーストは単一行に配列された順序付けられたエントリと説明されているが、単一列で複数行にまたがる順序付けられたエントリということもあり得る。かかる実施形態では、多次元データ配列にリストされている列の順序で、各列に順番にリストされているデータ要素が、一度に１列ずつ、一次元配列の単一行または単一列に線形的な順序でマッピングされ得る。したがって、任意の２つの相関データ要素の間に非相関データ要素が位置することなく、各バーストで相関データ要素が取得され得る。
【００３８】
なお、本発明の実施形態は４×４の部分配列を有する２Ｄデータ配列に関して述べられているが、例えば４×８、８×４、８×８、４×１６、１６×１６など、任意の次元部分配列が使用され得る。さらには、例えば３次元（３Ｄ）など、さらに高次元のデータ配列も使用される場合があり、その場合には、３Ｄマトリックスまたはテンソルデータ構造によって表され得る。一実施例では、ＬＵＭＡデータ要素が２Ｄデータ配列で表され得るのに対し、クロマ（Chroma）データ要素は２Ｄまたは３Ｄデータ配列で表され得る。
【００３９】
４×４×４という（６４）個の相関データ要素で構成される部分配列に分割された３Ｄデータ配列の場合、マッピング部（例えば図１のマッピング部７）は、図２および図３に関連して既述のとおり、例えば、第１の変換を使用して各々の３Ｄ部分配列を、順番になっている４つの２Ｄ＿４×４部分配列にマッピングし、第２の変換を使用して各々の２Ｄ＿４×４部分配列を１Ｄ＿１×１６部分配列にマッピングし得る。したがって、４×４×４の各部分配列は、１×６４の行から成る順序付けられたデータ要素として一次元データ配列にリストされ得る。１×６４の行セグメントに含まれている６４個のデータ要素を取得するために、プロセッサ１は、バーストが１６個または８個のデータ要素を含む場合であれば、それぞれ４回または８回のバーストまたはフェッチサイクルでデータメモリ部２にアクセスすればよい。
【００４０】
対照的に、従来の非効率的なプロセッサであれば、各フェッチサイクルで単一の４×４の配列の単一行からデータ要素が取得される場合に、（１×６４の行からでなく）４×４×４の部分配列からデータ要素を取得し得る。かかるプロセッサは、６４個の要素を取得するために、１６回のフェッチサイクルを使用して異なる１６行にアクセスする。この数字は、本発明の実施形態にかかる同一データを取得する目的で使用される４回または８回のサイクルと比較すると、演算サイクル数としては相当に多い。
【００４１】
他の、あるいは異なる次元、行、列、配列または部分配列、部分配列における他の、あるいは異なる相関要素数または要素数、バーストサイズおよびフェッチ、またはクロックサイクル数も使用され得る。
【００４２】
図４は、本発明の実施形態にかかる方法のフローチャートである。動作４００では、プロセッサ（例えば図１のプロセッサ１）が、相関データ要素集合すなわち複数の相関データ要素を特定し得る。例えば、予め指定された数の相関データ要素が、予め指定された次元をデータメモリ部（例えばデータメモリ部２）に有する部分配列に格納され得る。例えば、４×４の各次元部分配列が、（例えば図２で説明したように）個別の相関データ要素集合を含むように事前に指定され得る。別の例では、プロセッサが、例えばメモリアドレスによって相関データ要素を示すメモリからレジスタファイルを読み込み得る。相関データ要素は一緒に処理される場合もあるが、一部の相関データ要素がメモリから取得されないと処理されない場合もある。
【００４３】
動作４１０では、マッピング部は、（例えば図２に示すような）各多次元データ配列に含まれる相関データ要素集合を、（例えば図３に示すような）一次元データ構造に変換する。いくつかの実施形態では、マッピング部は、各部分配列からの順序付けられたデータ要素を、一次元データ構造における順序付けられた位置にマッピングし得る。部分配列に含まれる順序付けられたデータ要素は、要素が行の順序で各行に一度に１行ずつリストされている順序で配列されたデータ要素であり得る。図２に示す実施例を参照すると、（「１」と示された）第１の部分配列に含まれる順序付けられたデータ要素は、要素０、１、２、３、１９２０、１９２１、１９２２、１９２３、３８４０、３８４１、３８４２、３８４３、５７６０、５７６１、５７６２、および５７６３である。これらの要素は、変換されると、単一行に順番にリストされる。
【００４４】
動作４２０では、プロセッサが、例えばフェッチ部（例えば図１のフェッチ部１２）を使用して、データメモリ部からデータ要素を取得する。各々のフェッチまたは取得サイクルで、プロセッサは、データ「バースト」、つまり動作４１０の変換済みデータ構造の行で順番にリストされている複数のデータ要素を取得し得る。動作４００で相関していると識別されたデータ要素は動作４１０の変換済みデータ構造内で順番にリストされているため、取得された各データバーストは相関データだけを含み得る。データバーストのサイズすなわち１回のフェッチサイクルで取得される順序付けられたデータ要素の数に応じて、相関データを取得する目的で１回以上の連続フェッチサイクルが使用され得る。いくつかの実施形態では、１本のプロセッサパイプラインにおいて、単一の部分配列から変換された相関データがすべて取得されるまで、かかる相関データだけが取得され、非相関データが途中で一切取得されないこともある。
【００４５】
動作４３０では、プロセッサは、単一部分配列から変換された相関データがすべて取得されたことを判断する。したがって、相関データのデータ集合は完全なものとなり、適切に処理される。動作４４０では、プロセッサが、例えば命令を実行するなど、動作４３０の全ての相関データ集合を処理する。動作４５０では、ディスプレイ（例えば図１の出力装置１０２）に、動作４４０で処理された相関データが表示される。他の動作または他の一連の動作も使用され得る。
【００４６】
本発明の実施形態は映像または画像データに関して記載されているが、同一または同様のデジタル構造を有しつつも異なるデータ型に関連する任意のデータが使用されることが、当業者によって理解される。同様のデジタル構造は、相関値または共依存値の集合、同一データについて相互あるいは共同で説明している集合、または、多次元データの個々の次元の構成要素集合を有するデータを含み得る。
【００４７】
本発明の実施形態は、メモリ内のある箇所またはアドレスから別の箇所またはアドレスにデータ要素を移すことによって、メモリまたは記憶装置内のデータ要素を配列し、並べ、または変換するためのマッピング部（例えば図１のマッピング部７）について説明しているが、本発明の他の実施形態では、そのようなマッピング部が、例えばデータ要素自体を実際に移したり、配置し直したりすることなく、アドレスまたはポインタをそのメモリまたは記憶装置に等しく並べたり変換したりしてもよいことが、当業者によって理解される。いくつかの実施形態では、図１のプロセッサ１が、（例えば図２に示すような）多次元データ配列からデータ要素を新しい順序でフェッチし得る。例えば、本発明の実施形態は、多次元データ配列の単一行から各サイクルで順番にデータ要素を取得するシステムではなく、データ要素が各行にリストされている順序で、一度に１行ずつ、各サイクルで各部分配列の複数行からデータ要素を取得してもよい。本実施形態では、図１のプロセッサ１が、データ要素の元の順序または位置を維持しながら、非相関要素を間に有することなく相関データ要素だけを取得し得る。
【００４８】
本発明の実施形態は、コンピュータまたはプロセッサによる読み出しが可能な媒体などの物品、メモリ、ディスクドライブ、ＵＳＢフラッシュメモリなどのコンピュータ記憶媒体またはプロセッサ記憶媒体、プロセッサまたはコントローラ（例えば図１のプロセッサ１）によって実行された場合に、本明細書に開示されている方法を実行するエンコード命令、組み込み命令、または記憶命令を含み得る。
【００４９】
以上説明した特定の実施形態は、本発明が関係する多数の分散システムに有用であることが理解されるであろうが、本発明の更なる変更も当業者によって行われる。かかるすべての変更は、添付の特許請求の範囲によって定義される本発明の範囲および思想内にあるとみなされる。
【符号の説明】
【００５０】
１：プロセッサ、２：メモリ部、３：メモリコントローラ、４：記憶部、５：ディスプレイコントローラ、６：デコード部、７：マッピング部、８：データバス、９：データバス、１０：装置、１１：実行部、１２：フェッチ部、１３：一時記憶領域、１００：装置、１０１：入力装置、１０２：出力装置。
【図１】
2011138511.tif 000003
【図２】
2011138511.tif 000004
【図３】
2011138511.tif 000005
【図４】
2011138511.tif 000006