(57)【特許請求の範囲】
【請求項１】
第一の方向に沿って並んで配置される少なくとも２つのデータメモリと、
データ割り当て回路と、
隣接する前記データメモリの対応するアドレスのデータに対する同一命令の実行を順序付けるように構成された命令ルーティング回路と、
前記データメモリのそれぞれに接続された少なくとも２つの命令実行ユニットと、
前記命令ルーティング回路を経由して全ての前記命令実行ユニットに接続されたマスタープロセッサユニットと、を備え、
前記データメモリのそれぞれは、前記第一の方向に実質的に垂直な第二の方向に沿って少なくとも２つの同じ大きさの領域に分割されており、
前記領域の数は２の累乗であり、
前記データ割り当て回路は、二次元配列の要素を表すデジタル符号化したデータを受け取り、第一のデータメモリの第一の領域内の連続した隣接するメモリ位置に、前記配列の第一の次元に沿って、あらかじめ設定された数であって１より大きい数の隣接する要素の第一のシーケンスを表すデータを格納し、前記データメモリの隣接する領域のそれぞれに対応する連続した隣接するメモリ位置に、前記配列の第二の次元に沿って、あらかじめ設定された数の前記配列の前記第一の次元に沿った隣接する要素の、隣接するシーケンスを表すデータを格納するように構成されており、
前記第一のシーケンスを含む、前記第一のデータメモリの領域に格納されたデータが表す前記隣接するシーケンスの数は、前記第一のデータメモリの領域数と同じであり、
前記少なくとも２つのデータメモリのうち第二のデータメモリの領域に格納されたデータは、隣接するシーケンスと同じ数を表しており、
隣接するデータメモリの対応する領域に格納されたデータが表すシーケンスは、前記配列の前記第二の次元に沿って前記第一のデータメモリの前記領域数に等しい数の前記要素の数の分だけずれており、
前記同一命令の実行は、前記第一の方向に沿って隣接するデータメモリごとに、１クロックサイクルずつずれており、
前記命令実行ユニットは、前記データメモリのそれぞれに格納されるデータが表わす要素に対する演算命令を前記命令ルーティング回路から受け取って実行するように構成されており、
前記マスタープロセッサユニットは、前記データメモリに格納されたデータが表す要素に対する演算命令を、格納し、取り出し、供給するように構成されている、データ処理システム。
【請求項２】
前記第一のシーケンスとそれに隣接するシーケンスとが、前記配列のそれぞれのコラムの一部を含む、請求項１に記載のデータ処理システム。
【請求項３】
前記データメモリのそれぞれの領域数が４であり、
前記データメモリのそれぞれに格納されたデータが表す前記隣接するシーケンスの数が４であり、
隣接するデータメモリの対応する領域に格納されたデータが表すシーケンスは、前記配列の前記第二の次元に沿って４要素分だけずれている、請求項１に記載のデータ処理システム。
【請求項４】
前記データメモリのそれぞれの領域数が８であり、
前記データメモリのそれぞれに格納されたデータが表す前記隣接するシーケンスの数が８であり、
隣接するデータメモリの対応する領域に格納されたデータが表すシーケンスは、前記配列の前記第二の次元に沿って８要素分だけずれている、請求項１に記載のデータ処理システム。
【請求項５】
前記データメモリのそれぞれの領域数が１６であり、
前記データメモリのそれぞれに格納されたデータが表す前記隣接するシーケンスの数が１６であり、
隣接するデータメモリの対応する領域に格納されたデータが表すシーケンスは、前記配列の前記第二の次元に沿って１６要素分だけずれている、請求項１に記載のデータ処理システム。
【請求項６】
前記二次元配列の前記要素は前記配列を表すのに用いるフォーマットと一致するような可変型であり、
異なる領域内の対応する相対的なメモリ位置に格納されたデータが同じ型の要素を表す、請求項１に記載のデータ処理システム。
【請求項７】
前記配列の前記要素が画像の画素値を含む、請求項６に記載のデータ処理システム。
【請求項８】
前記配列の前記要素が物理量の値を含む、請求項１に記載のデータ処理システム。
【請求項９】
データプロセッサであって、
同じ大きさの少なくとも２つの領域に分割されたデータメモリと、
プログラム命令を受け取るための命令バッファと、
前記データメモリの領域に格納したデータを用いてプログラム命令を実行するように構成されたプロセッサ論理回路と、
水平アドレス成分を使って、前記データプロセッサと、相互接続した追加のデータプロセッサのグループのいずれかとの間でのデータアクセス要求のルートを指定するように構成されたリモートアクセス回路とを備え、
前記領域の数が２の累乗であり、
前記相互接続した追加のデータプロセッサの各々は、追加のデータメモリを備え、
前記水平アドレス成分は、前記相互接続した追加のデータプロセッサのグループのうちターゲットデータプロセッサの識別子と、前記ターゲットデータプロセッサの前記追加のデータメモリのターゲット領域の識別子と、を含む、データプロセッサ。
【請求項１０】
前記データプロセッサによって実行中の前記プログラム命令のサブグループの識別子を格納する領域状態論理回路をさらに備える、請求項９に記載のデータプロセッサ。
【請求項１１】
前記領域状態論理回路が、前記プログラム命令のサブグループを実行する際に使うデータを、前記データメモリのどの領域が含むかという指標を格納するようにさらに構成されている、請求項１０に記載のデータプロセッサ。
【請求項１２】
前記プログラム命令のサブグループが、前記データメモリと前記データメモリの外部に位置するメモリ位置との間でのデータ移動を要求する命令で終了する、請求項１０に記載のデータプロセッサ。
【請求項１３】
前記命令バッファから取り出した命令をデコードし、同時に、隣接するデータプロセッサの命令バッファにその命令を伝達するように構成された命令ルーティング回路をさらに備える、請求項９に記載のデータプロセッサ。
【請求項１４】
実行されるプログラム命令を格納する命令メモリと、
命令ルーティング回路と、
実行制御回路とを備えるデータプロセッサであって、
前記命令ルーティング回路が、前記命令メモリから取り出した命令をデコードし、同時に、隣接するデータプロセッサの命令バッファにその命令を伝達するように構成されており、
前記実行制御回路が、前記隣接したデータプロセッサの分割されたデータメモリの対応する連続領域のそれぞれに格納されたデータを使って実行するための命令サブグループを、前記隣接するデータプロセッサに繰り返し伝達するように構成されており、
前記分割されたデータメモリは、１より大きな数の領域に分割されており、
前記命令サブグループは、前記分割されたデータメモリ内の領域数と同じ回数だけ前記隣接するデータプロセッサに伝達される、データプロセッサ。
【請求項１５】
前記プログラム命令のサブグループが、前記データメモリと前記データメモリの外部に位置するメモリ位置との間でのデータ移動を要求する命令で終了する、請求項１４に記載のデータプロセッサ。
【請求項１６】
前記分割されたデータメモリの１つの領域に書かれた各データ要素に対し、前記データ要素の書き込みを実行した前記命令サブグループのそれぞれの指標を格納するように構成された制御メモリをさらに備える、請求項１４に記載のデータプロセッサ。
【請求項１７】
少なくとも２つの同じ大きさの領域に分割されたデータメモリと、データプロセッサ間のデータアクセス要求を取り扱うリモートアクセス論理回路とを備える、少なくとも２つのデータプロセッサと、
前記少なくとも２つのデータプロセッサのうちの第一のデータプロセッサに対して、前記第一のデータプロセッサの前記データメモリの１つのみの領域内のデータを使用して実行するために、プログラム命令を伝達するように構成されたマスタープロセッサであって、前記第一のデータプロセッサは、前記プログラム命令をデコードし、前記プログラム命令を前記少なくとも２つのデータプロセッサのうちの第二のデータプロセッサに伝達するように構成されている、マスタープロセッサと、
命令を前記マスタープロセッサから前記第一のデータプロセッサおよび前記第二のデータプロセッサへ順に伝達するために、前記マスタープロセッサと前記データプロセッサとを接続する命令パイプラインとを備える、データ処理システム。
【請求項１８】
前記データプロセッサのそれぞれに対応するマルチプレクサを備えるデータプロセッサ相互接続構造をさらに備え、
前記マルチプレクサのそれぞれからの出力は、前記データプロセッサのそれぞれの前記リモートアクセス論理回路の入力につながっており、前記データプロセッサのローカルグループのそれぞれの前記リモートアクセス論理回路からの出力は、前記マルチプレクサのそれぞれへの入力を形成する、請求項１７に記載のデータ処理システム。
【請求項１９】
前記ローカルグループ内のデータプロセッサの数は前記マルチプレクサのそれぞれが取り扱う入力の数と等しく、
前記マルチプレクサのそれぞれが１つの出力を有する、請求項１８に記載のデータ処理システム。
【請求項２０】
前記相互接続構造がさらに、前記データプロセッサの前記ローカルグループのそれぞれに対するもう１つのリモートアクセスマルチプレクサを含み、
前記リモートアクセスマルチプレクサの出力は１つで、入力の数は前記ローカルグループ内の前記データプロセッサの数と同じであり、
前記データプロセッサの前記ローカルグループのそれぞれの前記リモートアクセス論理回路からの出力は、前記リモートアクセスマルチプレクサの入力に接続される、請求項１９に記載のデータ処理システム。
【請求項２１】
データメモリの分割された同一の領域へ、二次元配列の要素を表すデータを格納する方法であって、
予め定められた数であって１より大きい数の、前記配列の第一の次元に沿った隣接する要素のシーケンスを表すデータを、前記データメモリの第一の領域の、対応する連続した隣接するメモリ位置に格納することと、
予め定められた数の要素の、前記配列の第二の次元に沿って隣接する要素のシーケンスを表すデータを、前記データメモリの連続した隣接する領域の、対応する連続した隣接するメモリ位置へ格納することとを備え、
前記データメモリの領域に格納されたデータで表されるシーケンスの数は、前記データメモリの領域の数と同じである、方法。
【請求項２２】
前記シーケンスとそれに隣接するシーケンスとが、前記配列のそれぞれのコラムの一部を含む、請求項２１に記載の方法。
【請求項２３】
前記シーケンスとそれに隣接するシーケンスとが、前記配列のそれぞれのコラムの全体を含む、請求項２２に記載の方法。
【請求項２４】
追加の隣接するシーケンスを、追加の分割したデータメモリの連続した隣接する領域の、対応する連続した隣接するメモリ位置に格納することをさらに含み、
前記データメモリを領域に分割した方向に対して実質的に垂直な方向に沿って、すべての前記データメモリが並べて配置される、請求項２１に記載の方法。
【請求項２５】
多数の同じ大きさの領域に分割されたデータメモリを含む少なくとも２つのデータプロセッサに接続されたマスタープロセッサでプログラムを実行する方法であって、
前記マスタープロセッサの命令メモリから第一の命令を取り出すことと、
前記少なくとも２つのデータプロセッサのうちの第一のデータプロセッサのデータメモリの第一の領域のみのデータを用いて実行するために、前記第一のデータプロセッサの命令バッファに前記第一の命令を伝達することと、
前記第一のデータプロセッサによる前記第一の命令の実行が、前記第一のデータプロセッサの前記データメモリと異なるデータプロセッサのデータメモリとの間で、データ移動を必要とするかどうか判断することと、
前記第一の命令の実行が、前記第一のデータプロセッサと前記異なるデータプロセッサとの間でのデータ移動を必要としない場合、次の命令を取り出して前記命令バッファに伝達し、伝達した命令がデータプロセッサ間での前記データ移動を必要とすると判断されるまで、この動作を続けることと、
前記伝達した命令の実行が前記第一のデータプロセッサと前記異なるデータプロセッサとの間でのデータ移動を必要とすると判断すると、前記第一のデータプロセッサのデータメモリの連続した隣接領域のみのデータを使って実行するために、前記第一の命令を取り出し、前記第一のデータプロセッサの命令バッファに前記第一の命令を再び伝達することと、を備える方法。
【請求項２６】
前記第一の命令を取り出し、前記第一の命令を伝達した後に、前記第一のデータプロセッサの前記データメモリの隣接する領域のそれぞれに対し、それぞれの領域に格納されたデータを使用して実行するために、前記第一の命令から、データプロセッサ間で前記データ移動を必要とする命令に達するまでの命令のシーケンスの伝達を繰り返すこととを備える、請求項２５に記載の方法。
【請求項２７】
命令バッファと少なくても２つの同一領域に分割されたデータメモリを含むデータプロセッサであって、隣接するデータプロセッサと、マスタープロセッサとに接続されたデータプロセッサによるプログラム実行の方法であって、
前記命令バッファにおいて前記マスタープロセッサからプログラム命令を受け取ることと、
前記プログラム命令をデコードし、前記命令を前記隣接するデータプロセッサの命令バッファに伝達することと、
前記データメモリの第一の領域のみのデータを使って前記プログラム命令を実行することと、
前記命令の実行が前記データプロセッサの前記データメモリと、異なるデータプロセッサのデータメモリとの間でデータ移動を必要とするかどうか判断することと、
前記命令の実行が前記データプロセッサと前記異なるデータプロセッサとの間でデータ移動を必要としない場合、実行した命令がデータプロセッサ間で前記データ移動へのアクセスを必要とすると判断するまで、前記データメモリの同じ領域のデータを用いて、前記命令バッファに受け取った次の命令を実行し続けることとを備える、方法。
【請求項２８】
実行した命令が前記データプロセッサと前記異なるデータプロセッサとの間でデータ移動を必要すると判断すると、前記データメモリの次の隣接する領域のみに格納されたデータに対して、次に受け取った命令を実行することと、
前記データメモリの隣接する領域のそれぞれに対し、それぞれの領域にのみ格納したデータを使って、データプロセッサ間で前記データ移動を必要とする命令で終了する命令シーケンスの実行を繰り返すこととをさらに備える、請求項２７に記載の方法。
【請求項２９】
前記第一のデータプロセッサは、同じクロックサイクルの間に、前記プログラム命令をデコードし、前記プログラム命令を前記第二のデータプロセッサに伝達するように構成されている、請求項１７に記載のデータ処理システム。
【請求項３０】
前記少なくとも２つのデータプロセッサは実質的に同じ構成である、請求項１７に記載のデータ処理システム。
【請求項３１】
前記第一のデータプロセッサは、前記第一の命令をデコードし、前記第一の命令を前記少なくとも２つのデータプロセッサのうちの第二のデータプロセッサに伝達するように構成されている、請求項２５に記載の方法。
【請求項３２】
前記プログラム命令をデコードし、前記命令を前記隣接するデータプロセッサの命令バッファに伝達することは、同じクロックサイクル内で実行される、請求項２７に記載の方法。
【請求項３３】
前記第一のデータプロセッサは、同じクロックサイクルの間に、前記第一の命令をデコードし、前記第一の命令を前記第二のデータプロセッサに伝達するように構成されている、請求項３１に記載の方法。
【請求項３４】
前記少なくとも２つのデータプロセッサは実質的に同じ構成である、請求項２５に記載の方法。
【発明の詳細な説明】
【背景技術】
【０００１】
多数のアプリケーションが二次元データセットを扱っている。映像処理アプリケーションはその一例である。ここで用いる「映像処理」という用語は、画像と映像の画の要素（「画素」）、およびそれに関連するデータ処理の汎用クラスを指す。画像強調と画素フォーマット変換、動き検出と追跡、静止画や動画フレーム内の特徴および物体認識等のアプリケーションが映像処理に含まれる。その他の二次元で表現されるデータセットを扱うアプリケーションには、力や電磁場等の物理量のモデル化が含まれる。三次元データセットを二次元データセットとして表現できるケースもある。二次元平面への投影あるいは変換として、あるいは隣接する多数の二次元データセットとして表現できるケースである。先行技術による解決法では次の２つの方法の１つを採用する。１）処理コアを用いたプログラム可能な解決法 、２）ハードウエア論理ゲートを用いたハードウエア（あるいは設定可能なハードウエア）による解決法。これらのオプションには次のような相違点がある。プログラム可能な解決法は、柔軟性があり、改良が容易で、様々なアプリケーションに適用できるが、ハードウエアによる解決法に比べて性能がかなり劣る。ハードウエアによる解決法は、容易に要求性能を満たすことができるが、設計、保守、および新しい要求を満たすための改良が非常に難しい。
【０００２】
プログラム可能な処理の利点とハードウエアによる処理の利点をあわせ持ち、かつそれぞれの欠点を持たない解決法を得ることが望ましい。一例として、映像処理アプリケーションの場合を考えてみる。ここで用いる「ビジュアルコンピューティング」という用語は、汎用プロセッサを使用する場合とは対照的に、映像処理に特化したコンピューティングアーキテクチャーに基づく、プログラム可能な解決法を指す。ビジュアルコンピューティングの解法例は多数存在するが、すべての解法には性能に関して基本的な制約がある。この制約は、最先端のセンサーとディスプレイの解像度や、増加するフレームレート（１秒あたりのフレーム数）に対して特に問題となる。
【０００３】
この制約の本質を理解するには、まず映像処理に対する一般的な要求を理解する必要がある。図１に、デジタルカメラにおける静止画の一般的な処理ステージを示す。センサー１００からの入力はベイヤモザイクの赤、緑、青の画素値、すなわちデータ要素を含んでいる（このフォーマットには、緑の情報量が赤と青の２倍含まれている。これは人間の目が緑の情報に敏感だからである）。画質向上とフォーマット変換の処理が施され、ＹＵＶデータ１０８が生成される。ＹＵＶデータはＪＰＥＧの様な標準画像フォーマットを生成するのに使用できる（ＹＵＶは輝度と色情報を表す３画素である）。この例ではベイヤパターンが示されているが、一般的にはベンダが所有権を有する独自の非標準フォーマットが多数存在する。これが、様々なフォーマットを１つの共通な解法で処理できる、プログラム可能な解法の１つのモティベーションなっている。
【０００４】
画素処理は、一般的に近隣の画素値を基にして与えられた場所の画素値を生成する。例えば、ノイズ除去ステージ１０４は、与えられた画素とその近隣の同じフォーマットの画素間で、値を比較することに基づいている。近隣画素値の平均である予測値からいくつかの閾値を求め、画素値が閾値よい大きいか小さい時は、レンズの不純物あるいはセンサーの欠陥等によるノイズによるものと判断する。この場合、画素値を予測値で置き換える。その他の処理ステージも、ホワイトバランスステージ１０６のように、近隣画素の値を考慮する同じ手法を一般的に用いる。黒レベル補正１０２は例外である。黒レベル補正は、あらかじめ決められたオフセット値を各画素値から単に差し引き、画素値に含まれる真の黒に相当するゼロ入力からのドリフト分を補正している。
【０００５】
このような処理方法は、処理ステージ間で、入力と出力に図２に示すような関係をもたらす。この例では、画素出力は画素の近隣領域に依存すると仮定している。ここでは、中央の画素は、右側の画素２列と左側の画素２列、および上の画素２行と下の画素２行に依存している。全入力領域は、幅５画素、高さ５画素（５ｘ５）の画素ブロックで、このブロックの中央の画素が出力に相当する。この例では、図１に示す処理ステージには連続番号が振られていると仮定する。処理ステージＮに対する９ｘ９の入力領域２００から５ｘ５の出力領域２０２が生成される。この領域は処理ステージＮ＋１に対する入力となり、この５ｘ５領域が今度は処理ステージＮ＋１の出力として１画素２０４を生成する。
【０００６】
入力として必要な画素の領域で、対応する出力を持たない領域をエプロンと呼ぶ。エプロンの要求は、処理ステージの結果領域の大きさが、入力領域よりも小さくなる原因となっている。縮小率が高いほど、処理はより複雑となり、従ってより高い品質となる。より高い品質は、より大きな数の処理のステージと、各ステージで出力を生成するのに使用されるより多くのエプロン画素を必要とする。
【０００７】
図２の処理ステージに相当する、先行技術による代表的な映像処理ハードウエアの動作を図３に示す。ステージＮへの入力はメモリバッファ３００が提供する。このバッファはエプロン要求を満足するのに必要なコンテキストを保持し、入力として一度に画素１セットを提供する。この例では、画素１セットは４画素３０２のような４つの画素のセットである。画素１セットの入力がバッファを一杯にし、バッファ中央の画素に対するエプロン要求を満足するため、入力画素の各セットは出力画素１セットを生成するのに十分である。例えば、画素セット３０２の入力はバッファを一杯にし、５ｘ５領域の中央に位置する画素セット３０４に対するエプロン要求を満足する。５ｘ５領域は、それぞれの方向に４つの画素のセット５つを保持する。走査ハードウエア３０６はこの５ｘ５領域の画素をアクセスし、ステージＮの演算ハードウエア３０８に入力として提供する。各々の入力セットは画像内の異なる位置にあり、ステージＮで必要な画素のバッファ３００内での相対位置は入力セットによって変化するため、走査ハードウエアが必要となる。同様にステージＮの出力は併合ハードウエア３１０によって処理される。併合ハードウエアは複数セットの入力画素に対するステージＮの出力をバッファ３１２に書く。この時、このバッファに書き込む結果を以前に走査した画素セットに対する演算から保護するような方法で書き込む。バッファ３１２は、このバッファ内の画素の、バッファ３００内の画素に対する相対位置を明確にするオフセットを示している。画素３０２によって生成された出力が、バッファ３１２内の画素３１４を更新し、さらに、バッファ３１２内の画素領域３１６に相当するステージＮ＋１の入力を生成する。
【０００８】
全てのハードウエア処理ステージが並列に動作する（走査線に沿って異なる位置の画素に対して）のに対し、ソフトウエアプログラムは一度に１つの命令を実行し、並列動作を管理できないため、図３に示したハードウエアの構成は、ソフトウエアプログラムでは模擬できない。ハードウエアのそれぞれのステージは、他のステージと並列に動作するために、配線で接続されているか、あるいは配線による限定的な設定機能を有する。処理ステージのスループットは、通常１処理サイクルにつき画素１セットである。そこで、例えば４５０メガヘルツで動作するハードウエアは、毎秒４５０メガ画素のスループットを提供できる。このスループットは、解像度が３０メガ画素でフレームレートが毎秒１５フレームの最先端のセンサーに対して要求されるものである。しかしながら、処理ステージは配線で接続されているため、柔軟性のない解決法である。
【０００９】
プログラム可能な解決法はこの柔軟性の低さを克服する。しかし、プログラムの実行は本質的に逐次的であるから、プログラムは、入力からある程度の数の逐次処理ステップ、すなわちサイクルの後、１セットの出力を生成する。サイクル数は、処理のステージ数とそれぞれのステージでの演算の複雑さによって決まる。代表的なサイクル数は１０００から２０００サイクルのオーダーである。従って、４５０メガヘルツで動作するプログラム可能な解決法は、たかだか毎秒０．４５メガ画素のスループットを提供する。これは、ハードウエアのスループットよりはるかに劣っている。
【００１０】
プログラム可能な映像処理のスループットを改善するには、プログラムは各処理ステージにおいて、多数の画素を処理して出力しなければならない。例えば、実行に１０００サイクル必要なプログラムが、１セットの入力画素に対して１０００セットの出力画素を生成すれば、ハードウエア処理と同等のスループットを達成できる。しかしながら、エプロン要求のため、このような出力を生成するのに必要な入力は、図４に示すような理想的なケースを仮定しない限り、１０００セットの入力よりかなり多くなる。この概念図では、全画像の画素幅と同じ数の処理データパス４０２が存在し、これと同じ幅のメモリ４００内のデータに対して動作する。各データパスはこのメモリの水平領域にアクセスでき、水平方向のエプロンアクセスに十分である。例えば、５ｘ５の領域に対し、右側の２画素と左側の２画素にアクセスできる。さらに、データはバッファに編成されている。バッファの深さは、垂直方向のエプロンアクセスに十分なライン数である。例えば、５ｘ５の領域に対し、深さは５ラインである。
【００１１】
この理想的な解決法では、走査線全体が入力として一度に提供され、一番古い走査線を破棄する。これらの線はメモリ４００で水平方向の線４０４で表現され、この例では、ベイヤフォーマットの画素の色に応じて分類されている。プログラムは同じ演算をすべての画素に対して同時に実行する。正しい結果を得るためにはこれらは同じフォーマットでなければならないから、類似したフォーマット（色）の画素は、別のバッファになければならない。プログラムは必要なサイクル数をかけて実行し、データパスの数に比例した多数の画素を生成する。ハードウエアと同等なスループットを得るためには、データパスの数は数千のオーダーでなければならない。なお、この例は説明のためだけだと理解すべきである。これほど多くのデータパスを同時に動作させることは物理的に不可能で、いかなるケースでも非常に高価なものとなる。
【００１２】
一般的な実装では、物理的な制限がデータパスの数を制限し、結果的に図５に示すような構成になる。図４の概念的なメモリとデータパスバンクは、無理なく実装し得るデータパスの数に応じて、データパスバンク５１０−５１６とメモリセグメント５００−５０６に分割されている。この数は通常３２か６４である。しかし、入力から出力まで、プログラムの全範囲に渡ってこれらのデータパスバンクを動作させると、「ｘ」で示した灰色の斜線領域が表すように、実行効率に容認できないほどの損失を被る。「ｘ」は各処理ステージでのエプロン要求が原因で、有効出力を失ったことを意味する。例えば、１０ステージの処理があり、それぞれのステージが５ｘ５の入力領域を必要とするならば、各データパスバンクは、各ステージで水平方向の有効なコンテキストを４画素失う。このため、最終ステージの出力は入力よりも４０画素狭くなる。データパスが６４の場合、出力の幅は２４画素となる。これは、並列データパスの効率が３８％（２４／６４）であることを意味する。これを避けるためには、データパスバンク５１０−５１６間でメモリ５００−５０６のデータを共有する必要がある。しかし、データパスが同じ演算を同時に行うことを保障できないし、従って、データパスにとってローカルではない他のメモリのデータパスがアクセスした時に、データが有効であることを保障できないため、データの共有は不可能である。
【００１３】
図６に示すように、すべてのステージを連続して実行するのではなく、一度に１つの処理ステージだけを実行することによって、分割したデータパスで出力データが減少する前述の問題に、先行技術は対処している。Ｎステージの後、Ｎステージの出力はシステムデータ移動処理によりグローバル共有メモリ６００へ書き込まれる。これに続き、システムデータ移動処理により、データパスのローカルメモリ（図５の５００−５０６）へ再度データが読み込まれる。この再読み込み操作を使って、データバンクに読み込む走査線の一部をオーバーラップすることにより、内部データバンクでのデータ損失を最小限に抑えることができる。データバンクの終端付近のデータ要素を、近接するバンクの始端で繰り返すと、それぞれのバンクが必要とするエプロンが提供され、境界でのデータ損失が無くなる。処理ステージごとのデータ損失は、走査線の両端が原因となるものだけで、例えば４画素となる。すべての処理ステージを実行した場合に比べて、この損失のデータパスの幅に対する比率は非常に小さく、並列処理の効率は６０／６４＝９４％である。しかし、Ｎステージの出力とＮ＋１ステージの入力をコピーするには、追加のサイクルが必要となる。このサイクルが実効実行時間に加算され、スループットも制限する。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
ここで今述べた２つの例では、プログラム可能なビジュアルコンピューティングの解決法には、基本的なスループットの制限がある。これは、エプロン要求を満たすためのデータを共有できないため、並列動作の効率が悪い、あるいは、グローバルメモリの共有コンテキストを改編するために必要なサイクルが加算される、といういずれか一方が原因となっている。
【００１５】
データセットの１要素に対する演算が、データセットの１つかそれ以上の他の要素にアクセスする必要がある場合、すなわち、少なくとも与えられた演算に対してはデータセット内の要素が互いに関係がある場合は、効率的なソフトウエア処理が困難であることを上の議論は示している。ハードウエアでこの演算を実装すると、走査過程で必要な入力要素を繰り返し取得することにより、この状況を効率的に取り扱える。二次元データセットの相互関係のある要素に対する演算をソフトウエアで実装するための効率の良い方法を得ることが望ましい。
【課題を解決するための手段】
【００１６】
１つのプログラムを実行することにより、任意の多数の演算を並列に実行するように処理データパスを構成したシステム、プロセッサ、あるいは方法によって、上で述べた問題をうまく扱うことができる。これらのデータパスは、どんな命令セットアーキテクチャにでも基づくことができる。命令を順序付ける新規な方法を用いて、各々のデータパスは同じシーケンスの命令を実行する。そして、データパスはその数に関係なく、同期して実行する効果を有する。システムは、水平および垂直の定められた範囲で、すべてのデータを共有できる相互接続ネットワークを含み、その結果、通常の使用では処理サイクルを増加させることなく、任意のデータパスと他の任意のデータパスのメモリとが接続される。このアプローチにより、ハードウエアによる解決法に近いスループットのプログラム可能なビジュアルコンピューティングが可能となる。
【００１７】
ここで述べるデータ処理システムの実施例では、少なくとも２つのデータメモリを、第一の方向に沿って並べて配置する。第一の方向にほぼ垂直な第二の方向に沿って、それぞれのデータメモリを少なくとも２つの同じ大きさの領域に分割する。システムは、二次元配列の要素を表すデジタル符号化したデータを、第一のデータメモリの第一の領域内の連続した隣接メモリ位置に格納するのに適した、データ割り当て回路も含む。第一の領域に格納されたデータは、配列の第一の次元に沿った、予め定められた数の隣接要素の第一のシーケンスを表していてもよい。
【００１８】
さらに、データ割り当て回路は、配列の第二の次元に沿った、第一のシーケンスに隣接するシーケンスを表すデータを、データメモリの第一の領域に隣接する各領域の、連続した隣接メモリ位置に格納するのに適している。第一のデータメモリの領域に格納したデータが表す隣接するシーケンスの数が、第一のデータメモリの領域の数と同じになるように、データを格納する。これに加えて、第二のデータメモリの領域に格納されるデータは同じ数の隣接するシーケンスを表し、隣接するデータメモリの対応する領域に格納されたデータが表すシーケンスは、第一のデータメモリの領域の数と同じ数の要素分だけ、配列の第二の次元に沿って位置がずれている。
【００１９】
実施例では、データ処理システムは、隣接するデータメモリの対応するアドレスのデータに対する同一命令の実行を順序付けるのに適した、命令ルーティング回路も含む。ここで、同一命令の実行は、第一の方向に沿って隣接するデータメモリごとに、１クロックサイクルずつずれている。システムは、それぞれが少なくとも２つのデータメモリに接続した、少なくとも２つの命令実行ユニットを含んでいてもよい。命令実行ユニットは、各々のデータメモリに格納されるデータが表わす要素に対する演算命令を受け取って実行するのに適している。データ処理システムは、さらに、全ての命令実行ユニットに接続するマスタープロセッサユニットを含んでいてもよい。マスタープロセッサユニットは、データメモリに格納されたデータが表す要素に対する演算命令を、格納し、取り出し、供給するのに適している。
【００２０】
もう１つのデータ処理システムの実施例は、少なくとも２つの同一のデータプロセッサを含む。各データプロセッサは、少なくとも２つの同一領域に分割されたデータメモリと、データプロセッサ間のデータアクセス要求を取り扱うリモートアクセス論理回路とを含んでいる。システムは、少なくとも２つの同一のデータプロセッサの第一のプロセッサにプログラム命令を伝達するのに適した、マスタープロセッサも含んでいる。ここで、命令は、第一のデータプロセッサのデータメモリの１つの領域内のデータを使用して実行するために伝達される。システムは、マスタープロセッサとデータプロセッサを直列に接続する命令パイプラインと、同一データプロセッサ各々に対し１つのマルチプレクサとを有する、データプロセッサの相互接続構造も含む。各マルチプレクサからの出力は、各データプロセッサのリモートアクセス論理回路の入力につながっている。そして、データプロセッサの各ローカルグループのリモートアクセス論理回路からの出力は、各マルチプレクサへの入力を形成する。このデータ処理システムの更なる実施例では、ローカルグループ内のデータプロセッサの数はそれぞれのマルチプレクサが取り扱う入力の数と等しく、それぞれのマルチプレクサは１つの出力を有する。システムのもう１つの実施例では、相互接続構造も、データプロセッサの各ローカルグループに対し、もう１つのリモートアクセスマルチプレクサを含む。リモートアクセスマルチプレクサの出力は１つで、入力の数はローカルグループ内のデータプロセッサの数と同じである。ローカルグループの各データプロセッサのリモートアクセス論理回路からの出力は、リモートアクセスマルチプレクサの入力に接続される。
【００２１】
ここに記述するデータプロセッサの１つの実施例は、同じ大きさの少なくとも２つ、あるいは２の累乗数の領域に分割したデータメモリ、プログラム命令を受け取る命令バッファ、データメモリの領域内に格納されたデータを使ってプログラム命令を実行するのに適したプロセッサ論理回路、データプロセッサとその他の相互接続したデータプロセッサの任意のグループ間のデータアクセス要求のルートを、水平アドレス成分を使って指定するのに適したリモートアクセス回路を含む。この実施例を「タイルプロセッサ」と称してもよい。更なる実施例では、データプロセッサは、データプロセッサで実行中のプログラム命令のサブグループの識別子を格納するために、領域状態論理回路を含んでいてもよい。これに加えて、領域状態論理回路は、プログラム命令のサブグループを実行する際に使うデータを、データメモリのどの領域が含むかという指標を格納していてもよい。プログラム命令のそのようなサブグループは、データメモリとデータメモリの外部に位置するメモリ間でのデータ移動を要求する命令で終わるかもしれず、ここでは「タスク間隔」と称してもよい。さらに別の実施例では、データプロセッサは、命令バッファから取り出した命令をデコードし、同時に、隣接するデータプロセッサの命令バッファにこの命令を伝達するのに適した命令ルーティング回路を含んでいてもよい。
【００２２】
異なるデータプロセッサの実施例は、実行するプログラム命令を格納する命令メモリ、命令メモリから命令を取り出してデコードし、同時に隣接するデータプロセッサの命令バッファに命令を伝達するのに適した命令ルーティング回路、および隣接したデータプロセッサの分割されたデータメモリの対応する連続領域が格納するデータを使って実行するための命令サブグループを、隣接するデータプロセッサに繰り返し伝達するのに適した実行制御回路を含む。この実施例をここでは「マスタータイルプロセッサ」と称してもよい。更なる実施例では、データプロセッサは、分割されたデータメモリの１つの領域に書かれた各データ要素に対し、どの命令サブグループがデータ要素の書き込みを実行したかという指標を格納するのに適した、制御メモリも含んでいてもよい。
【００２３】
データプロセッサとデータ処理システムに加えて、データ処理方法をここで考える。当業者に知られている技術を使用し、プログラム命令によってこの方法が実装されてもよい。マスタープロセッサでプログラムを実行する方法の実施例は、マスタープロセッサの命令メモリから第一の命令を取り出し、マスタープロセッサに接続する第一のデータプロセッサの命令バッファに第一の命令を伝達することを含む。ここで、第一のデータプロセッサは、マスタープロセッサに接続する少なくとも２つのデータプロセッサのうちの１つであり、各々のデータプロセッサは多数の同一領域に分割されたデータメモリを含んでいる。更にこの方法は、第一のデータプロセッサによる第一の命令の実行が、第一のデータプロセッサのデータメモリと異なるデータプロセッサのデータメモリ間で、データ移動を必要とするかどうか判断することを含む。第一の命令の実行が、第一のプロセッサと異なるデータプロセッサ間のデータ移動を必要としない場合、この方法は、次の命令を取り出して命令バッファに伝達し、伝達した命令がデータプロセッサ間でのデータ移動を必要とすると判断されるまで、この動作を続けることを含む。
【００２４】
マスタープロセッサのプログラム実行方法の更なる実施例は、伝達された命令の実行が第一のデータプロセッサと異なるデータプロセッサ間でのデータ移動を必要とすると判断すると、第一のデータプロセッサのデータメモリの連続した隣接領域のデータを使って実行するために、第一の命令を取り出し、第一のデータプロセッサの命令バッファに第一の命令を伝達する。この方法では、第一のデータプロセッサのデータメモリの各隣接領域に対し、それぞれの領域に格納されたデータを使用して実行するために、第一の命令からデータプロセッサ間でデータ移動を必要とする命令に達するまでの命令のシーケンスを伝達し続ける。
【００２５】
データプロセッサによるプログラムの実行方法の実施例は、命令バッファのプログラム命令を受け取り、プログラム命令をデコードし、それと同時に命令を隣接する同一のデータプロセッサの命令バッファに伝達し、データメモリの第一の領域のデータを使ってプログラム命令を実行することを含む。この方法は更に、命令の実行がデータプロセッサのデータメモリと異なるデータプロセッサのデータメモリ間で、データ移動を必要とするかどうか判断することを含む。命令の実行がデータプロセッサと異なるデータプロセッサ間で、データ移動を必要としない場合、この方法は、実行した命令がデータプロセッサ間のデータ移動を必要とすると判断するまで、データメモリの同じ領域のデータを用いて、命令バッファに受け取った次の命令を実行し続けることを含む。
【００２６】
データプロセッサによるプログラムの実行方法の更なる実施例は、実行した命令がデータプロセッサと異なるデータプロセッサ間でデータ移動を必要とすると判断すると、データメモリの次の隣接領域に格納されたデータに対し、次に受け取った命令を実行することを含む。データメモリの各隣接領域に対し、この方法は、それぞれの領域に格納したデータを使って命令シーケンスを実行し、データプロセッサ間でデータ移動を必要とする命令で実行を終了することを含む。
【００２７】
データメモリの分割された領域へデータを格納する方法もここで考える。ここでは、データは二次元配列の要素を表す。この方法の実施例は、予め定められた数の、配列の第一の次元に沿った隣接要素のシーケンスを表すデータを、データメモリの第一の領域の、対応する連続した隣接メモリ位置に格納することを含む。この方法は、更に、予め定められた数の要素の、配列の第二の次元に沿って隣接するシーケンスを表すデータを、データメモリの連続した隣接する領域の、対応する連続した隣接メモリ位置へ格納することを含む。第一のデータメモリの領域に格納されたデータで表される、隣接するシーケンス数は、第一のシーケンスを含めて、第一のデータメモリの領域の数と同じである。ある実施例では、第一のシーケンスとその隣接シーケンスは、二次元の配列のそれぞれのコラムの一部である。更なる実施例では、第一のシーケンスとその隣接シーケンスは、配列のそれぞれのコラム全体である。もう１つの実施例では、この方法はさらに、さらなる隣接シーケンスを、さらなる分割したデータメモリの連続した隣接する領域の、対応する連続した隣接メモリ位置に格納することを含む。このような実施例では、データメモリを領域に分割た方向に対し、ほぼ垂直な方向に沿って、データメモリをすべて並べて配置する。
【００２８】
ここで述べたシステム、プロセッサ、および方法は、並列に動作する最大４０９６のデータパスを効率的に使用する、プログラム可能な画像と視覚の処理に適用できる。プロセッサは、高級言語で記述した逐次プログラムを実行することが望ましい。アプリケーションの条件によって、データパスは１つのデータパス単位で割り当てられてもよい。実施例では、ここに記述される技術を、既存のいかなる命令セットやＣ＋＋コンパイラにでも採用できる。データパスは、待ち時間が０サイクルで完全なコヒーレンシーをサポートし、完全に相互接続した二点間リンクに類似した効果を持ち、画像または映像フレームのいかなる範囲の視覚データをも完全に共有するように実装してもよい。計算は、すべてのデータパス間で共有された、グローバルな共有データ、ルックアップテーブル、およびヒストグラムを含むこともできる。
【図面の簡単な説明】
【００２９】
以下で開示する様々な実施例の明細書は、次の添付図を参照する。
【図１】図１は一般的な静止画処理のパイプラインを示す。
【図２】図２は画像処理の入力と出力コンテキストの関係を示す。
【図３】図３は一般的なハードウエア処理パイプラインを示す。
【図４】図４は理想的だが、実現不可能なプログラム可能な解決法を示す。
【図５】図５は並列視覚処理が困難であることを説明する。
【図６】図６は先行技術の並列視覚処理へのアプローチを示す。
【図７】図７は二次元アレイプロセッサすなわち「タイルプロセッサ」の選択した構成要素を示す。
【図８】図８はタイルプロセッサのローカルグループを示す。
【図９】図９はタイル相互接続ルーティングユニットの構成を示す。
【図１０】図１０はルーティングユニットによるルーティング階層の構成を示す。
【図１１】図１１はタイル相互接続ルーティングの階層構造を示す。
【図１２】図１２はタイルプロセッサのデータメモリ分割の構成を示す。
【図１３Ａ】図１３Ａは画素データの走査線の４領域に分割したデータメモリへのマッピングを示す。
【図１３Ｂ】図１３Ｂは画素データの二次元アレイの図１３Ａに示されるデータメモリへのマッピングを示す。
【図１４】図１４は画素データの走査線の８領域に分割したデータメモリへのマッピングを示す。
【図１５】図１５は画素データの走査線の１６領域に分割したデータメモリへのマッピングを示す。
【図１６Ａ】図１６Ａはどのようにタイル相互接続のルートを決定するかを示す。
【図１６Ｂ】図１６Ｂはどのようにタイル相互接続のルートを決定するかを示す。
【図１６Ｃ】図１６Ｃはどのようにタイル相互接続のルートを決定するかを示す。
【図１６Ｄ】図１６Ｄはどのようにタイル相互接続のルートを決定するかを示す。
【図１６Ｅ】図１６Ｅはどのようにタイル相互接続のルートを決定するかを示す。
【図１７Ａ】図１７Ａはマスタータイルプロセッサの構成を示す。
【図１７Ｂ】図１７Ｂはここに記述されるプロセッサが実行する代表的なタスク間隔を示す。
【図１７Ｃ】図１７Ｃはマスタータイルプロセッサがプログラムを実行する方法を説明する。
【図１７Ｄ】図１７Ｄはマスタータイルプロセッサがプログラムを実行する方法を説明する。
【図１７Ｅ】図１７Ｅはタイルプロセッサがプログラムを実行する方法を説明する。
【図１８Ａ】図１８Ａは命令の順序付けが、どのように待ち時間による遅延を回避するかを示す。
【図１８Ｂ】図１８Ｂは命令の順序付けが、どのように待ち時間による遅延を回避するかを示す。
【図１９Ａ】図１９Ａは相互接続がルートを決めるタイミングを示す。
【図１９Ｂ】図１９Ｂは相互接続がルートを決めるタイミングを示す。
【図１９Ｃ】図１９Ｃは相互接続がルートを決めるタイミングを示す。
【図１９Ｄ】図１９Ｄは相互接続がルートを決めるタイミングを示す。
【図２０】図２０は依存関係のグラフの例を示す。
【図２１】図２１は依存関係を解決して遅延を回避するタイミングを示す。
【発明を実施するための形態】
【００３０】
特定のシステム構成要素を参照する以下の説明と特許請求の範囲全体に渡って、特定の用語を使用する。当業者であれば理解するように、会社によっては１つの構成要素を異なる名前で参照することがある。この文書では、名前は異なるが機能は同じである構成要素を区別する意図はない。以下の議論と特許請求において、用語「含む」と「構成する」は、制限のない意味で使われ、したがって、「含むが、これに限定されるものではない」ことを意味すると解釈されなければならない。また、「接続する」という用語は、間接的あるいは直接的な電気接続を意味している。したがって、第一の装置が第二の装置に接続するならば、その接続は直接的な電気接続か、あるいは、他の装置や接続を経由した間接的な電気接続のいずれかである。
【００３１】
以下の議論は、ここに記述されるシステム、プロセッサと方法のいろいろな実施例を対象としている。これらの実施例の１つかそれ以上が推奨されるかもしれないが、開示した実施例を、特許請求を含めて開示の範囲を制限するものと解釈したり、さもなければ制限したりするために使用すべきものではない。これに加えて、当業者は、以下の説明には幅広いアプリケーションがあり、いかなる実施例に関する議論もその実施例の単なる代表例であることを意味し、特許請求を含む開示の範囲がその実施例に限られることを示唆するものではないことを理解するであろう。
【００３２】
図７は、視覚タイルの基本的な処理要素の構成要素から選択したものを示す。「タイル」という用語は直線領域、あるいは、フレーム内の画素の二次元の配列で、幅が４、８または１６画素で、高さが最大２５６画素の配列を指す。各々の処理要素すなわちタイルプロセッサは、画素の一意的なタイルを操作し、隣接したタイルは隣接したタイルプロセッサにマップされる。このマッピングの仕方は、基本的なプロセッサの構成について説明した後に述べる。ここでは主に、画像処理のアプリケーションに対するタイル処理について述べるが、開示する実施例は、二次元データセット、特に二次元相関のあるデータセットのデータ処理に関わる、いかなるアプリケーションにでも適していると考えられることを理解すべきである。
【００３３】
命令メモリと命令フェッチ論理回路を持たないという顕著な例外はあるが、タイルプロセッサ７０１は、従来のプロセッサと同じように多くの部品を備えている。図７は、タイルプロセッサ７０１の従来にはない構成要素を説明することを目的とし、複数のタイルプロセッサ７０１のグループ化を図８で容易に説明できるように描かれている。タイルプロセッサ７０１の構成要素の配置は、構成要素間のすべての相互接続を反映しないかもしれない。ここでは、特に断らないかぎり、タイルプロセッサ７０１は従来のプロセッサの構成要素を含み（たとえば、電源を含む）、技術的に知られているような、従来のプロセッサの方法で相互接続されている。
【００３４】
従来の命令メモリと命令フェッチ論理回路を使う代わりに、タイルプロセッサ７０１は、以下に記述するように、マスタータイルプロセッサが取得し、命令パイプラインを用いて配布する命令を使う。命令パイプラインは連続命令バッファ（Ｉ−バッファ）レジスタ７００から成り、すべてのタイルプロセッサを同じシーケンスの命令に接続する。Ｉ−バッファレジスタはダブルバッファである。そのため、ローカルタイルプロセッサでの処理を中断させるすべての機能停止は、次の命令を提供するタイルプロセッサだけに伝播する。複数の機能停止サイクルに対しては、機能停止は隣接したプロセッサが次のプロセッサへと伝播させて行く。この命令の取得方法は、機能停止を制御するグローバル信号を使っていない。グローバル信号は、信号の伝達遅延のため、高周波数で多数のタイルプロセッサを動作させることはできない。
【００３５】
デコード論理回路７０２は、Ｉ−バッファ７００で受け取った命令をデコードし、演算器７０６がバンクレジスタファイル（ｂａｎｋｅｄ  ｒｅｇｉｓｔｅｒ−ｆｉｌｅ）７０８のレジスタの内容に対して演算を実行する。この際、ロードとストアによってオペランドを取得し、分割されたデータメモリ７１０（ＤＭＥＭ）に結果を書き込む。これらは、当業者に知られた従来のプロセッサの特徴であろう。タイルプロセッサの新規な特徴は、領域状態論理回路７０４、レジスタファイルのバンキングメカニズム７０８、データメモリの分割メカニズム７１０、リモートアクセス論理回路７１２、タイルの相互接続ネットワーク７１４とこれらの組合せを含む。ネットワーク７１４は、全てのタイルプロセッサと他の全てのタイルプロセッサのＤＭＥＭとを接続する完全接続ネットワークを意味するため、別々のハードウエアブロックとして示されていない。これらの構成要素は、システム構成に関連して、以下で詳細に記述する。
【００３６】
図７に示す構成のタイルプロセッサ４台からなるローカルグループのための、タイルの相互接続を図８に示す。各々のタイルプロセッサのリモートアクセス論理回路７１２はローカルアクセス相互接続８００に接続している。ローカルアクセス相互接続は、４台のどのタイルプロセッサからの要求でも、１サイクルで他のいずれかに送り届ける。リモートアクセス論理回路８０２は、同時に、いずれかの要求が、ローカルグループのプロセッサに宛てられていないかどうかを判断し、そのような要求を、非ローカルタイル相互接続８０４に提示する。非ローカルタイル相互接続は、非ローカル要求を最終的な目的地に接続する。ローカルアクセス相互接続８００、リモートアクセス論理回路８０２、および非ローカルタイル相互接続８０４は、図７に示す相互接続ネットワーク７１４の特定なレベルである。
【００３７】
ローカルアクセス相互接続８００とリモートアクセス論理回路８０２の実施例の構造を図９に詳述する。記述を明確にするため、図９では、相互接続したタイルプロセッサの各々のリモートアクセス論理回路７１２だけを示す。ローカルアクセス相互接続は、マルチプレクサ（ＭＵＸ）９００−９０６の、特に、第一の４つの８００で表される各ＭＵＸへの入力によって実現する。図から分かるように、これは、グループのどのタイルプロセッサからの要求または応答でも、他のどのタイルプロセッサと完全に結合する。リモートアクセス相互接続８０２は、ＭＵＸ９０８とＭＵＸ９００−９０６への５番目の入力によって実現する。ＭＵＸ９０８は、出て行く非ローカル要求または応答を、非ローカルタイル相互接続へ接続する。ＭＵＸ９００−９０６は、非ローカルタイル相互接続から入って来る非ローカル要求または応答を、ローカルグループ内の目的地となるプロセッサに接続する。ＭＵＸ９００−９０８は、あわせてルーティングユニット９１０を構成する。ルーティングユニットは、４つのローカル要求と１つの非ローカル要求のルートを１サイクルで指定することができる。図８と図９の実施例では、図８に示すローカルグループ内の４つのタイルプロッセサーは、図９に示すリモートアクセスマルチプレクサ９０８の４つの入力に対応している。
【００３８】
図８と図９の実施例に続いて図１０では、ルーティングユニット９１０を階層的に結合してルーティング層１００４を構成する。ルーティング層は、ルーティングユニット９１０の同一のインスタンスを５つ含む。４つのインスタンスは、図９に示すように、ローカルと非ローカルのアクセス（要求または応答）のルートを指定し、ルーティングレベルと呼ばれる。５番目のインスタンスは、第一の４つのインスタンスからの４つの非ローカルアクセスのルートを指定し、次ルーティングレベルと呼ばれる。この次レベルは、ローカル要求のように、第一のレベルからのアクセスを他の第一のレベルのルーティングユニットへ接続することができる。あるいは、アクセスを何段か高いルーティング層に接続しなければならないと決めることができる。次の層での、これらの非ローカルアクセスはアクセスバッファ１０００と１００２に置かれる。バッファ１０００は出て行くアクセスをバッファし、バッファ１００２は入って来るアクセスをバッファする。レジスタ１０００と１００２は、図７に示すＩ−バッファレジスタ７００のようにダブルバッファで、機能停止は、グローバルではなく次の１レベルだけに伝播する。
【００３９】
図１０に示すように、ルーティング層１００４の構成は、ルーティング層にとってのローカルアクセス１６個と非ローカルアクセス１つのルートを１サイクルで指定できる。可能なローカルアクセスの数が非常に多いのに比べて、非ローカルの帯域幅が不十分に見えるかもしれないが、Ｉ−バッファレジスタ７００のため、タイルプロセッサは１サイクル遅れて対応するアクセス命令を実行し、そのため、ルーティングレベルには一度に１つのアクセスを提示することを理解するべきである。したがって、アクセスルートの要求は、時間的に均一に分布する。
【００４０】
図１１は、図８−１０の実施例で、いかなる組み合わせにおいても、２つのタイルプロセッサを完全に接続するアクセスを実装するために、ルーティングユニット９１０をどのように構築しているかを説明する。ローカル相互接続１１００、レベル１相互接続１１０２、およびレベル１アクセスバッファ１１０４の結合は、ルーティング層１００４のインスタンスを２５６個含んでいる。これは、ローカルルーティングのためのルーティングユニット９１０のインスタンス１０２４個（「１０２４ｘ」）、レベル１相互接続のためのルーティングユニット９１０のインスタンス２５６個（「２５６ｘ」）、およびレベル１相互接続からの非ローカルアクセスとレベル１相互接続への非ローカルアクセスのためのアクセスバッファ１０００と１００２のインスタンス２５６個を含む。同様に、レベル２相互接続１１０６、レベル３相互接続１１０８、およびレベル３アクセスバッファ１１１０の結合は、ルーティング層１００４のインスタンスを１６個含む。相互接続１１０６と１１０８のためのルーティングユニット９１０のインスタンス数とバッファ１１１０のためのアクセスバッファ１０００と１００２のインスタンス数を図に示す。トップレベルは、レベル４相互接続１１１２、レベル５相互接続１１１４、およびレベル５アクセスバッファ１１１６を結合し、ルーティングユニット１００４のインスタンスを１つ含んでいる。レベル５での非ローカル要求は、システムインターフェース１１２０へ向けられ、残りのシステムとデータを接続するか、あるいは、グローバルテーブルランダムアクセスメモリ（ＲＡＭ）１１１８へ向けられ、全てのタイルプロセッサで共有するテーブルとデータを接続する。このＲＡＭ１１１８は、グローバルパラメター、ルックアップテーブル、および、いろいろなデータ値の頻度、例えば、画像全体の輝度を記録するヒストグラムを格納する。
【００４１】
図８−１１は、ここで述べた二次元データ処理システムで使用した、階層相互接続ルーティングの構成の１つの実施例を示しているにすぎないということを理解すべきである。このルーティングの構成は、階層的でマルチプレクサに基づいている。そのため、以下でさらに議論するように、適切なビット数を持つタイルプロセッサのインデックスを用いて、特定のタイルプロセッサを選択できる。しかしながら、使用する相互接続のレベル数やマルチプレクサの大きさ（すなわち、マルチプレクサの入力数）等の詳細は、特定のアプリケーションのコストや要求性能に基づき、当業者によって異なるかもしれない。また、その他の変更や強化が、当業者によって用いられるかもしれない。たとえば、データパスを広げ、接続を減らすため、ルーティング構成内の選択した点において、ルーティングユニットとバッファのいずれか一方あるいは両方の多数の複製を含むかもしれない。
【００４２】
図１１の代表的な実施例から容易に分かるように、ルーティングとバッファユニット１１００−１１１６から成るタイル相互接続は、どのタイルプロセッサからのアクセスでも他のどのタイルプロセッサのＤＭＥＭと完全に接続するよう実装されている。各々のルーティング層は、アクセスバッファ間が２レベルの多重化から成っているので、通常、この相互接続間の転送のタイミングはクリティカルではない。この相互接続のタイミングへの耐性が、実装の１つの構成要素となって、多数のタイルに渡る視覚分散処理をサポートしている。その他の構成要素として次の３つが含まれる。１）相互接続全体でアクセスのアドレスとルートを指定するメカニズム。２）相互接続での待ち時間（サイクル数）が、タイルプログラムの実行を遅くすることを避けるメカニズム。３）アクセスしたデータが正しいことを保障するコヒーレンシーメカニズム。３）では、有効な計算がなされるまで値をアクセスしないことと、ある値を必要とする全てのプロッセサーがアクセスする前にその値を上書きしないことが要求される。これらの３つの構成要素は以下で順次議論する。
【００４３】
タイル相互接続でのアドレス指定とルーティングの基本は、図７に示すＤＭＥＭ７１０の分割である。３つの代表的な分割の構成の概念を図１２に示す。例えば、与えられた領域に対する相対アクセスを設定するベースアドレスレジスタを用いて、ＤＭＥＭ７１０は同じ大きさの領域に分割されている。各々の領域はタイルの垂直方向の１セットの画素（すなわち、画素の二次元配列の列）を保持し、隣接する領域はタイルの水平方向の幅（二次元配列の行に沿った）を構成する。プログラムは一度に１つの領域の中で演算を行うが、全領域に渡って、すなわちタイルを横断して水平方向に、順番に演算を繰り返す。領域の数は、タイルの幅に応じた２の累乗数である。図１２の実施例では、領域は１６進数の番号が順番に振られている。１２００の構成は４つの領域を持ち、０−３の番号が振られている。１２０２の構成は８つの領域を持ち、０−７の番号が振られている。１２０４の構成は１６個の領域を持ち、０−Ｆの番号が振られている。プログラムのメモリ要求によっては、領域に割り当てる必要のない、付加的なメモリがあることがある。このメモリは、全てのプログラムが一時的な値のために用いる共有のスピル／フィル領域１２０６を構成でき、全ての領域にこのメモリを複製することを防いでいる。
【００４４】
画素の領域へのマッピングを明確にするため、図１３Ａ、図１４、および図１５はそれぞれ、１２００、１２０２、および１２０４の構成における、走査線内の隣接する画素の、隣接するタイル内の対応する領域へのマッピングを示す。タイル内の多数の画素は、対応する数の領域にマッピングされる。そのため、水平方向の幅は部分ごとに、各々のタイルプロセッサのＤＭＥＭ７１０内で垂直方向にマッピングされる。フレームの垂直方向の高さは、各領域内で直接マッピングされることを理解しなければならない。そのため、例えば、水平位置が同じで垂直位置が異なる画素は同一領域内にある。二次元画素データのこのマッピングを図１３Ｂに示す。以下でさらに議論するように、実行は、画素タイル間では並列であるが、各々のタイル内では連続的である。
【００４５】
領域間でのアクセスの生成は、二段階のアドレス指定を含む。第一段階はインデックスを使って画素の水平位置を指定し、第二段階はインデックスを使って垂直位置を指定する。この方式のアドレス指定は、１つのプロセッサで二次元配列をアクセスするのに用いられるアドレス指定と全く同じように実行されると、当業者は認識するだろう。従来の方法では、１つのインデックスを２つの配列サイズの１つ（行数か列数のどちらか一方）と掛け合わせ、２つ目のインデックスを加えることにより、これら２つのインデックスの値を結合して一次元のアドレスとし、最終結果を配列のべースアドレスに加える。これは、二次元配列は線形メモリの連続したセットに割り当てられるためである。対照的に、ここで記述されるプロセッサでは、これらのアドレス構成要素は別々のままである。水平インデックスは、タイルとタイル内の列の位置から該当する領域を指定し、垂直インデックスは、画素値の領域内での位置を領域のベースアドレスに対する相対値として表し、領域内のメモリ位置を指定する。
【００４６】
水平インデックスだけを用いてタイル相互接続でのアクセスルートを決定する。図１６Ａ、１６Ｂ、１６Ｃ、１６Ｄおよび１６Ｅは、図８−１１の実施例のルーティング構成で、ルーティングを行うためにこのインデックスをどのように解釈するかという例を提供する。図１６では、水平、すなわち列インデックスは１６ビットの値１６０６で表されている。この値は、領域の構成が図１２の１２００、１２０２、あるいは１２０４のどれであるかによって、それぞれ図１６Ｂのインデックス１６００、図１６Ｃのインデックス１６０２、あるいは図１６Ｄのインデックス１６０４と解釈される。いずれの場合も、下位数ビットを領域番号の選択のために使用する。全領域を選択するのに必要なビット数は、領域数が４、８、あるいは１６構成のとき、それぞれ２、３、あるいは４ビットである。したがって、図１６Ｂの領域インデックス１６１０は２ビット、図１６Ｃの領域インデックス１６１２は３ビット、図１６Ｄの領域インデックス１６１４は４ビットである。
【００４７】
各水平インデックスの次の１２ビットは、ターゲットプロセッサインデックス１６１６を形成する。隣接するタイルプロセッサは画素の隣接するタイルに対応するので、ターゲットプロセッサインデックス１６１６は、図８−１１のルーティング構成によって接続された４０９６個のタイルプロセッサの１つを識別する（その結果、水平インデックス１６００と１６０２に示すように、水平インデックスの１ビットか２ビットは使用しない）。例えば、フレームの一番左のタイルはタイルプロセッサ０に、次のタイルはタイルプロセッサ１のように対応している。これらの１２ビットは、ターゲットプロセッサの番号を形成し、タイル相互接続間のアクセスルートを直接決定する。水平インデックス１６０８のこのフィールドの構成を図１６Ｅに示す。ターゲットプロセッサインデックス１６１６は、ルーティングレベルに対応する２ビットのルーティングレベルフィールド１６１８を６つ含む。ここで、より上位のビットが、より上位のルーティンングレベルに対応する。ルーティンングレベルは、図では「ｌｏｃａｌ」、「Ｌ１」等と表示してある。どのレベルにおいても、２ビットフィールド１６１８は、図９に示すＭＵＸ９００−９０６のＭＵＸ入力８００に応じた、ローカルアクセス相互接続のＭＵＸセレクトを形成する。ＭＵＸ９００−９０６の４つの入力のアドレス指定には、２ビットのフィールドで十分であるが、より大きなマルチプレクサを使用した実施例では、より多くのビットが必要である。任意の２ビットフィールド１６１８よりも上位のビットは、アクセスがローカルか非ローカルかに関係なく、図８と図９で示すリモートアクセス論理回路８０２でデコードに用いられる。例えば、一番左の位置から第一の４つのタイルでは、全フィールドＬ１−Ｌ５はゼロである。これらのフィールドのいずれかがゼロでないならば、このグループにとってアクセスは非ローカルである。この場合、フィールドＬ２−Ｌ５の値がゼロで、アクセスがその階層内であると決まったら、レベル１のローカルアクセス相互接続に対して、Ｌ１フィールドを使ってレベル１のルートを指定する。フィールドＬ２−Ｌ５のいずれかがゼロでないなら、アクセスはレベル１に対して非ローカルであり、図１１に示すアクセスバッファ１０００に置かれる。
【００４８】
図１１のレベル５の相互接続１１１４を含む全ての階層に渡ってアクセスのルートを指定するためには、ターゲットのタイルプロセッサ番号の上位フィールドを順次使用してこの処理を続けることを理解すべきである。レベル５では、アクセスを開始した命令のタイプを用いて、アクセスがレベル５に対してローカルか非ローカルかを識別する。他の任意のタイルプロセッサに対するアクセスはローカルと認識し、グローバルテーブルＲＡＭ１１８あるいはシステムインターフェース１１２０へのアクセスは非ローカルと認識する。プロセッサ設計の当業者に知られているシグナリング方法のいずれかを用いて、水平インデックスとは違った別の信号により、命令タイプを通知するように実装する。
【００４９】
タイルプロセッサのアクセス要求のケースに戻る。ひとたびターゲットのタイルプロセッサのインデックスが、ターゲットのタイルプロセッサにアクセスできるルーティングユニットを有する相互接続レベルに到達すると、それ以上アクセス要求をデコードする必要はない。ルーティングレベルフィールド内のビットは、該当するルーティングレベルにおけるマルチプレクサへの入力として働く。このようにして階層の高いレベルから低いレベルへと、アクセス要求のルートが指定される。例えば、レベル５のローカルルートは、水平インデックス１６０８の「Ｌ５」のビットを用いて、図９のＭＵＸ９００−９０６のＭＵＸ入力８００に相当するＭＵＸセレクトを形成する（このルーティングユニット９１０は、図に示すローカルグループのためではなく、レベル５のためのルーティングユニットであると理解する）。これによって、アクセスがレベル４のルーティングユニットにリモートアクセス入力として接続される。この時点で、図９のリモートアクセス論理回路８０２のリモートアクセス入力に相当するＭＵＸ入力のうち、どの入力をレベル３に対して選択するかを１６０８の「Ｌ４」ビットで選ぶ。これによって図１０に示すように、選択したレベル３の入力用アクセスバッファ１００２にアクセスは書き込まれる。このアクセスバッファは、図１１のアクセスバッファ１１１０の１６個のインスタンスの１つである。この時点で、ターゲットのタイルプロセッサ番号のより下位のフィールドを順次使用して処理を続け、最終的な転送先のタイルプロセッサへのアクセスのルートを全ての階層に渡って指定する。転送先のタイルプロセッサでは、領域番号によってアクセスのベースアドレスを選び、それにアクセスの垂直インデックスを加算してＤＭＥＭのデータにアクセスする。ストアアクセスではアクセスに付随するデータをＤＭＥＭに書き込む。ロードアクセスは、アクセスを実行したタイルプロセッサと領域を識別するリターンインデックスを伴っている。ＤＭＥＭの指定したアドレスからデータを読み出し、ここで説明したルーティング処理を用いて、アクセスのソースへ送り返す。アクセスのソース側で受け取ったデータは、図７に示すバンクレジスタファイル７０８に書き込まれる。レジスタは第一のロード命令で明示され、レジスタバンクはソースの領域から特定される。バンクレジスタファイルは、領域ごとに同じ構成のレジスタの集合を含んでいる。レジスタは領域ごとに独立して使用するため、ロードしたデータは領域にとって一意的なレジスタに書き込まれる。
【００５０】
タイル相互接続のアドレス指定とルーティングのメカニズムについて説明してきた。ここでは、この相互接続間のロードアクセスの待ち時間に起因する、パフォーマンスの問題に話題を転じる。タイル相互接続を通過するデータ応答にかかるサイクル数に加えて、タイル相互接続を通過するアクセス要求にかかるサイクル数は、通常は１サイクルで終了する従来のロードにかかるサイクル数よりかなり大きいということは当業者にとって明白である。これらのサイクルは、ロードによってアクセスしたデータを必要とする全ての命令の実行を、ほぼ同じ数のサイクルだけ遅らせる。これらのロードはおそらく全命令の２０％のオーダーで比較的頻繁に実行されるので、５サイクルの増加が、全プログラムのサイクル数を倍増しかねない。これは大きな性能低下を意味するが、ここで記述するシステムでは、命令順序付けの新規な方式を導入して性能低下を防いでいる。この方式ではロード命令と、ロード操作によってアクセスされたデータに依存する後続の全ての命令の間に、大きな時間差を挿入する。
【００５１】
図１７Ａに示すマスタータイルプロセッサ１７０１はこの命令順序付けを実装し、タイルプロセッサ７０１の第一のインスタンスに接続される。第一のタイルプロセッサ７０１は、図８に示すように次のタイルプロセッサに順番に接続される。この接続を相互接続されたタイルプロセッサグループ全てに渡って継続する。図８−１１に示すルーティングの構成では、この接続は全部で最大４０９６個のタイルプロセッサを含む。マスタータイルプロセッサ１７０１が実行する命令のシーケンスを、タスク間隔と呼び、図１７Ｂに示す。タイルプロセッサ７０１の番号を振っていない構成要素は、図７に示す他のタイルプロセッサの構成要素と同一である。番号が振ってある構成要素はマスタータイルプロセッサにとって一意的である。これは、命令メモリ（ＩＭＥＭ）１７００、命令フェッチ論理回路１７０２、プログラムカウンタ（ＰＣ）ＭＵＸ１７０４、命令ＭＵＸ１７０６、第一のタスク命令を格納するレジスタ１７１０、および二番目のタスク命令のＰＣを格納するレジスタ１７１２を含む。
【００５２】
図１７Ｂのタスク間隔の命令シーケンスでは、第一のタスク命令１７１４を第一タスク命令レジスタ１７１０にロードする。二番目のタスク命令１７１６のプログラムカウンタの値を第二ＰＣタスク命令レジスタ１７１２にロードする。マスタータイルプロセッサ１７０１による命令の実行とそれに付随するタイルプロセッサアレイについて、図１７Ｃと１７Ｄのフローチャートと関連付けながらより詳細に記述する。
【００５３】
図１７Ｃと１７Ｄのフローチャートはマスタータイルプロセッサ１７０１によるプログラムの実行手順の実施例を示す。プログラムを開始するために命令フェッチ論理回路１７０２は、ＭＵＸ１７０４の入力で「Ｂｒａｎｃｈ ＰＣ」を選び、第一の命令のアドレスを用いて（これは全てのプロセッサにとって、従来の操作である）プログラムの第一の命令を取り出す（図１７Ｃのステップ１７２０）。命令ＭＵＸ１７０６は、ＩＭＥＭ１７００から取り出した命令を選択し、命令のデコードと実行を行う第一のタイルプロセッサのＩ−バッファレジスタへ命令を伝達する（図１７Ｃのステップ１７２２）。タイルプロセッサ７０１による命令の実行について、図１７Ｅのフローチャートと関連付けながら以下でより詳細に記述する。命令は、デコードされると同時に、次に隣接するタイルプロセッサのＩ−バッファへ伝達される。同様に、このプロセッサが命令をデコードし、次に隣接するプロセッサへ命令を伝達する。このようにして、全てのタイルプロセッサは同じ命令のシーケンスを実行するが、連続するタイルプロセッサは、各々１サイクルだけずれている。
【００５４】
この第一の命令をＩ−バッファに書き込む時、第一のタスク命令レジスタ１７１０にも同時に書き込む（図１７Ｃのステップ１７２４）。次のサイクルで、命令フェッチ論理回路１７０２は、ＰＣ  ＭＵＸ１７０４でインクリメントした次のＰＣ「ＰＣ＋１」を選び、連続する次の命令をアクセスする（図１７Ｃのステップ１７２６）。この間第一の命令はデコードされ、隣接するタイルプロセッサへ伝達される。このサイクルの最後に、「ＰＣ＋１」の値を第二タスク命令ＰＣレジスタ１７１２に書き込む（図１７Ｃのステップ１７２８）。二番目の命令も第一のタイルプロセッサのＩ−バッファレジスタへ送り、実行する（図１７Ｃのステップ１７３０）。レジスタ１７１０に格納した命令とレジスタ１７１２に格納したＰＣの組み合わせは、命令フェッチ論理回路１７０２がＭＵＸ１７０６でレジスタ１７１０を選んでＩ−バッファに送り、次のサイクルでレジスタ１７１２を選んで次に読み出す命令のＰＣとすることにより、タスク間隔の実行を再始動することを可能とする。
【００５５】
タスク間隔の最後は、リモートアクセスを必要とする命令によって定義される。ここで、リモートアクセスは、タイル相互接続を使って実行することを意図し、領域間、およびレベル５におけるシステムとテーブルへのアクセスを含む。これは、図１７Ｂで「Ｉｎｓｔ  Ｍ」と表わされている。マスタータイルプロセッサはこのような命令をデコードサイクル中に検出し（図１７Ｃの検出ブロック１７３２）、検出した場合は（ブロック１７３２の結果が「ｙｅｓ」）、命令フェッチ論理回路に通達する。その結果、命令フェッチ論理回路は次の命令としてレジスタ１７１０を選択し、タスク間隔を第一の命令から再始動する。これは図１７Ｄのフローチャートの一部、ステップ１７４４と１７４６に対応する。次のサイクルで、レジスタ１７１２を使ってタスク間隔の二番目の命令にアクセスする（図１７Ｄのステップ１７４８）。そこから再びタスク間隔の最後の命令に達するまで実行は連続的であり、最後の命令に到達すると再度タスク間隔を実行する。この実行は、図１７Ｄのステップ１７３４、１７３６、および１７３８を含めて、図１７Ｃの決定ブロック１７３２の「いいえ」分岐に対応している。
【００５６】
繰り返されたタスク間隔のそれぞれは、次の４つから識別できる。異なるデータセットを使って実行する。ＤＭＥＭの一意的な領域を使って実行する。レジスタファイル内のレジスタの一意的なバンクを使って実行する。領域０から始め、連続する領域番号の順に実行する。図１７Ｃと図１７Ｄの実施例では、この連続領域に渡る実行は、タスク間隔の最後に達した時に領域カウンタをインクリメントすることによって成し遂げられる（図１７Ｃのステップ１７４０）。これはタイルを横断してタスク間隔を効果的に繰り返す。プログラムは全ての水平位置に対して実行しなければならないので、これは正しい動作に必要である。この繰り返しは、設定の中で最も大きな番号が付いた領域でタスク間隔が終了するまで続く（図１７の決定ブロック１７４２）。この時点で、ＭＵＸ１７０４は「ＰＣ＋１」を選び（図１７のステップ１７５２）、命令の実行は継続して命令「Ｎｅｘｔ１」へ進む。これは次のタスク間隔の開始であり、レジスタ１７１０と１７１２を設定する過程を繰り返して、このタスク間隔も間隔の最後を検出したら再始動できるようにする。この命令順序付けのやり方は、プログラムの最後まで続く（図１７Ｃの決定ブロック１７５０の「はい」分岐）。図１７Ｃの１７５４から１７６２のステップは、さらに以下で議論するコヒーレンシーメカニズムの実施例を実装する。
【００５７】
マスタータイルプロセッサは全てのタイルプロセッサの命令シーケンスを決定するので、全てのタイルプロセッサは複数の領域に渡って同じ命令を実行する。この領域に渡る繰り返しはプログラムの実行時間を長くするが、増えた分のサイクルは増えた結果に振り分けるので、スループットを低下させることはない。例えば、４領域に渡る繰り返しは、４つの中間結果を生成し、スループットはプログラムの一回の繰り返しと同じである（４／４＝１）。
【００５８】
しかしながら、図１８Ａに示すように、この繰り返しにはタイル相互接続によるロードを、ロードによってアクセスしたデータの使用から大きく分離するという有益な効果がある。図は２つのタスク間隔、タスク間隔１８００（「ａ」）とタスク間隔１８０２（「ｂ」）の実行を表している。全ての間隔１８００は同じ命令のシーケンスであり、間隔１８０２も同様であるから同じ番号が振ってある。すでに述べたように、これらのタスク間隔は全ての領域（この例では４領域）と、２つの隣接するタイルプロセッサ「Ｎ」と「Ｎ＋１」において繰り返される。図では、垂直方向に時間は経過している。異なる領域でのタスク間隔の実行を、「ａ−０」から「ａ−３」および「ｂ−０」から「ｂ−３」と識別し、それぞれのタイルプロセッサの領域０−３での実行を表すものとする。隣接するタイルプロセッサにおける同じタスク間隔の実行は、命令を図７のＩ−バッファ７００を通して配布するため、１サイクルずれている。タスク間隔１８００は、タスク間隔の最後を定義するリモートロード（「ｌｏａｄ」）で終了する。タスク間隔１８０２は、ロードしたデータを使用する命令（「ｕｓｅ」）で開始する。
【００５９】
図１８Ａは隣接するタイルプロセッサとそれぞれのデータメモリの領域を、空間的に表現している。図１８Ｂに示す、同じ命令の実行の時間に基づく表現も有用であろう。図１８Ｂでは、ｙ軸は命令を実行するタイルプロセッサのデータメモリの領域を示し、ｘ軸はクロックサイクルを示している。上の図はタイルプロセッサＮを表し、下の図は隣接するタイルプロセッサＮ＋１を表す。斜めの線は４つの命令から成るタスク間隔１８００内を推移していくことを表している。まずタイルプロセッサのデータメモリの領域０内の適切なデータに対して実行し、次に同じ命令セットを領域１、２、３のデータメモリに対して順番に実行する。タスク間隔１８００の最後の命令「ｌｏａｄ」が４つの領域全てで実行されると、次の命令セット（タスク間隔１８０２）の実行が領域０に戻って開始される。プロセッサＮでの実行より１クロックサイクル遅れていることを除いて、全く同じシーケンスをプロセッサＮ＋１で実行する。図１８Ｂは、この実施例では各々の命令は１クロックサイクル必要とし、データメモリの新しい領域で実行を開始したり、新しい命令セットの実行を開始したりするのに関連したクロックサイクルは必要とされないと仮定している。
【００６０】
図１８Ａと図１８Ｂの実施例でのタスク間隔は、命令の長さ４である。実際のタスク間隔は一般的にはもっと長いが、ソフトウエアの最適化によってタスク間隔が、４命令長のように最短であることを保障できる。これが可能なのは、コンパイラがタスクを終了する命令のタイプを決定でき、タスク間隔が望ましい数の命令を含むようにコードの移動最適化を行えるからである。図から分かるように、少なくとも長さが４命令のタスク間隔を使えば、リモートロードを少なくとも１２サイクル（他の３領域それぞれで４サイクル）「ｕｓｅ」から離すことができる。これは図１８Ｂの間隔１８０４で示され、タイルプロセッサＮの領域０のロード命令の実行から、同じ領域で次の命令シーケンスを実行し、ロードしたデータを使用するまでの時間を表している。従って、ロード動作が１２サイクルで終了すれば、このデータを使用する命令の実行に遅延は生じない。使用できる時間が、領域の数とともに増加することは明らかである。８領域であれば、ロードは２８サイクル（４ｘ７）で終了すればよいし、１６領域であれば、６０サイクル（４ｘ１５）で終了すればよい。
【００６１】
長さが４命令のタスク間隔を実行するのに必要なアクセスの待ち時間に関し、図１８は待ち時間が最小となる最悪のケースを表している。図１８のタイミングが、リモートアクセスによってプログラムの実行が遅れるのを防ぐのに十分であることを説明するため、タイル相互接続間の様々なルーティング経路が必要とするサイクル数を図１９に示す。必要なサイクル数は、ルーティングを行うのに必要な相互接続のレベルに依存しており、ターゲットとなるタイルプロセッサへの要求のルートを指定するサイクル、ターゲットでＤＭＥＭをアクセスするサイクル、および応答データのルートを指定するサイクルを含んでいる。図１９Ａは、ローカルとレベル１の相互接続を通るルートを指定できる、シーケンス１９００のアクセスに必要なサイクルを示す。サイクル１でロードを実行した時から、要求のローカルとレベル１のルート指定（Ｌｏｃａｌ／Ｌ１）、ＤＭＥＭアクセス（ＤＭＥＭ  Ａｃｃｅｓｓ）、応答のローカルとレベル１のルート指定（Ｌｏｃａｌ／Ｌ１）、およびレジスタ書き込み（Ｗｒｉｔｅ  Ｒｅｇｉｓｔｅｒ）の各動作に１サイクルずつ使用する。レジスタに書き込むときに、データはレジスタファイルをバイパスして実行に使うこともできる。このため、プログラムの実行を遅らせないために、間に挟まれたサイクル２−４の３つの命令だけが必要である。図１９Ｂのシーケンス１９０２は、レベル２とレベル３の相互接続を通るルートで指定できるアクセスの場合で、シーケンス１９００に必要なサイクルに追加のレベルを通るのに必要な４サイクルが加算される。遅れを防ぐためは全部で７つの間に挟まれた命令が必要である。
【００６２】
図１９Ｃのシーケンス１９０４はグローバルＲＡＭのアクセスの場合である。レベル４とレベル５を通るルート指定を含み、シーケンス１９００に必要なサイクルに４サイクルを加算し、７つの間に挟まれた命令が必要である。最後に、図１９Ｄのシーケンス１９０６は、要求と応答の両者のルート指定に全てのレベルを必要とする最悪のケースである。シーケンス１９０２に必要なサイクルに４サイクルを加算し、遅れを防ぐためには１１個の間に挟まれた命令が必要である。タイルプロセッサのデータメモリ領域に渡るタスク間隔の実行繰り返しは、図１８から分かるように、少なくとも１２個の間に挟まれた命令を提供するのに対し、図１９Ｄの操作に１１個が要求されるので、最悪ケースの待ち時間に対してでさえ、プログラムの実行を遅らせることなく、タイル相互接続を利用してアクセスを遂行できる。より多くの領域を使用する場合は、より多くの間に挟まれた命令が提供されるので(８領域で２８、１６領域で６０)、タイミングはよりクリティカルでなくなる。
【００６３】
ここで、コヒーレンシーの問題に議論を移す。タイル相互接続を通してアクセスのルートを指定でき、ロードアクセスの待ち時間のためにプログラムの実行を遅らせないだけでは十分ではない。タイルプロセッサの実行には、Ｉ−バッファや領域に渡る繰り返しによって、ずれが生じている。ロードでアクセスしたデータが、逐次命令の実行においてロード以前で一番最近のストアによって書き込まれたデータであって、それ以前のストアやロードの後のストアによるものではないと、保障するメカニズムがなければならない。換言すれば、要求したデータは、要求した操作が使用するのにちょうどよい時に到着するだけではなく、正しいデータでなければならない。このストアとロードの仮想上の逐次シーケンスは、タイルの実行が逐次的でなくても、コヒーレンシーメカニズムによって効率的に再構築されなければならない。
【００６４】
コヒーレンシーメカニズムの動作は、依存グラフによって記述できる。依存グラフの例を図２０に示す。グラフではメモリ内のデータをブロック２０００−２００４で表す。ブロック２０００と２００２はシステムメモリのデータを表し、ブロック２００４はタイルプロセッサのＤＭＥＭに保持するデータを表す。グラフノード（円）２００６−２０１６は命令操作を表す（これは依存グラフの従来の表記法である）。命令の入力はノード上部の「ｕｓｅ」と書いた点に入る矢印で表し、出力はノード下部の「ｄｅｆ」（「値の定義」の意味）と書いた点から出る矢印で定義する。１つのノードから次のノードへの矢印はアークで、出る矢印で定義される結果値を、入る矢印に対する入力オペランド値として使用する。アークは結果値とオペランド値の依存関係を定義する。
【００６５】
全てのタイルプロセッサは同一の命令シーケンスを実行するので、依存グラフは全てのプロセッサに対して同一で、データ値のみが異なる。図２０は、Ｎ、Ｍ、およびＰと表示した３つのタイルプロセッサを示している。これらのプロセッサは、必ずしも隣接する必要はなく、画像フレーム(あるいは他の二次元配列)の水平方向のどの位置のデータを保持しても良い。これは、依存グラフはタイルプロセッサのいかなる範囲にでもまたがることができるということを強調し、コヒーレンシーメカニズムが扱う問題の本質を説明している。タイルプロセッサＮのアークには、ノード２００６から２０１２、ノード２０１０から２０１２、あるいはノード２０１２から２０１６へのアークのように、タイルプロセッサにとってローカルとなる依存アークがある。タイルプロセッサＭが実行するノード２０１４からタイルプロセッサＮが実行するノード２０１６、あるいはタイルプロセッサＰが実行するノード２００８からタイルプロセッサＮが実行するノード２０１０へのアークのように、その他のアークは非ローカルである。この例では、記述を明確にするため、タイルプロセッサＮの依存関係に焦点を当てるが、図２０の実施例の全てのタイルプロッセサーは、番号を付けたノードに応じた依存関係を有すると理解すべきである。
【００６６】
リモートでアクセスする値を定義する命令はタスク間隔の最後を定義し、また全ての領域は同じ命令シーケンスを実行しているため、この命令が同じタスク間隔内で全てのタイルプロセッサと領域において発生することを認識することは、コヒーレンシーのメカニズムを理解する上で、重要な点である。さらに、全てのタスク間隔は前のタスク間隔に連続的に続くので、プログラムの開始時に０から始まり、タスク間隔が全ての領域で実行されたときに増加するカウンタを用いて、タスク間隔を識別することができる。これをタスク間隔のタスクＩＤと呼ぶ。
【００６７】
コヒーレンシーのメカニズムを理解する上で、もう１つの重要な点は、映像データは共有されているので、プロセッサと周辺デバイス間で共有される全てのデータに当てはまる２つの性質を有していることである。これは、単一プロセッサシステムのような単純なケースにでさえ当てはまる。第一の性質は、データはプログラムの繰り返し中に、一度だけ書き込まれる（「ライトワンス」）ということである。これは、周辺デバイスへの逐次出力中に、データが一度だけ書き出されるのに似ている。この性質がなければ、垂直方向にデータを共有する必要がある繰り返し間（プログラムの繰り返しは垂直方向であるから）で、データを共有するのは不可能であろう。例えば、図２０の保持されたデータ２００４を、格納するメモリ位置に２回書き込んだら、二回目に書き込んだ値のみが次のシーケンスの繰り返しのために保存され、第一の値は次のシーケンスの繰り返しでは正しく共有されないであろう。これは典型的な処理パイプライン（例えば図１の処理を参照）によってサポートされる。なぜなら、データは処理ステージ間でバッファされ、１つのステージで出力として書き出され、他のステージで入力として読み込まれるからである。第二の性質は共有するデータは揮発性であるということである。これは、データ値はＤＭＥＭに反映されなければならず、プロセッサのレジスタを介して命令間のみで通信してはならないということを意味し、周辺デバイスへの出力データは周辺デバイスへ書き込まなければならないという要求に似ている。
【００６８】
依存グラフで定義される値は使用回数にかかわらず唯一であることを、ライトワンスという性質は保障する。さらに、揮発性の性質は、全てのタイルプロセッサと全ての領域において、各々で定義された値に応じたストアが存在することを保障する。ここで、各々で定義された値が異なっていてもかまわない。これらのストアは一意的に番号付けしたタスク間隔で実行されるという事実を考えあわせると、以下が当てはまらなければならない。依存グラフ内の全てのアークは、タスクＩＤで一意に識別できなければならない。このタスクＩＤには唯一のストア命令が存在する。全てのプロセッサにおいて、たとえタイルプロセッサと領域に渡ってこの命令が何回実行されても、同一の該当するストア命令は同一のタスクＩＤを有する。
【００６９】
図１７に戻る。マスタータイルプロセッサはこれまでに説明しなかったスカラー制御ＲＡＭ１７０８を含んでいる。また、図７に戻ると、それぞれのタイルプロセッサはこれまでに説明しなかった領域状態論理回路７０４を含む。スカラー制御ＲＡＭ１７０８（関連する制御論理回路１７１４と共に）と領域状態論理回路７０４は共にコヒーレンシープロトコルを実装する。スカラー制御ＲＡＭは映像データ（あるいは他の二次元データ要素）に関連するスカラーデータを格納する。ここで記述するシステムの実施例では、映像データをＣ＋＋プログラミング言語のオブジェクトによって表す。これらのオブジェクトは、オブジェクトの大きさとアドレス指定変数等のスカラー情報とベクトル情報すなわち画素やそれに関係するデータを表す映像データを含む。スカラー情報はマスタータイルプロセッサのスカラー制御ＲＡＭにのみ格納される。ベクトル情報はタイルプロセッサのＤＭＥＭに渡って分散している。この２つの間の関係は、スカラーデータがＤＭＥＭ内の全ての領域の映像データへのアドレスポインターを含んでいるということである。ここに、アドレスポインターは、各々の領域のベースアドレスからのオフセットを表す。
【００７０】
これは、依存グラフで値を定義するストアと、この値を使うロードとを関連付けるメカニズムを提供する。映像オブジェクトがストアで書き込まれた時、このストアは、第一のタイルプロセッサの領域０で第一に実行される。映像ベクトルデータ（この領域では、ベクトルの多くの値の中の１つで、スカラーである)を書くと同時に、マスタータイルプロセッサはオブジェクトのタスクＩＤ変数をスカラー制御ＲＡＭ１７０８に書く。この変数は、各々のオブジェクトのインスタンスに対して一意的であり、オブジェクトにストアを実行したタスク間隔のタスクＩＤを記録する。ストアで書いたデータを使用する次のシーケンスのいかなる命令をも実行する前に、ストアはＤＭＥＭの全ての領域で実行されるので、このタスクＩＤの書き込みは、ＤＭＥＭの最後の領域でストアが実行された後、一回だけ行われる。図１７Ｃの実施例では、ステップ１７６０と１７６２がこの処理を示している。ロードが映像オブジェクトを読む時は、マスタータイルプロセッサがこのタスクＩＤ変数を読み、ロード命令に関連づける。ロード命令は、全てのタイルプロセッサに配布され、全ての領域で実行される。このロード命令とタスクＩＤの関連付けは、図１７Ｃの実施例でステップ１７５４から１７５８で実装するように、各々のリモートロード命令に対して行われる。
【００７１】
タイルプロセッサでは、領域状態論理回路７０４は２つの値を維持する。実行中の命令の現在のタスクＩＤを識別する値と、どの領域が該当するタスク間隔を終了したかを示す二進数の値である。図１７Ｅに、タイルプロセッサによるプログラム実行の手順の実施例を説明するフローチャートを示す。Ｉ−バッファから入ってくる命令をデコードする間、タイルプロセッサは、また、隣接するタイルプロセッサのＩ−バッファへ命令を伝達する（図１７Ｅのステップ１７８２と１７８４）。タイルプロセッサは、リモートアクセス命令がタスク間隔の終了を引き起こすまで、入ってくる命令を実行する（ステップ１７６８と１７７０に示す）。ＤＭＥＭの１つの領域でタスク間隔が終了すると、どの領域でタスク間隔が終了したかという記録を保持する（ステップ１７７２）。図１７Ｅの実施例では、タスクＩＤカウンタを使ってこの記録を保持する。つづいて、全ての領域でタスク間隔が実行されるまで（決定ブロック１７７６）、同じタスク間隔の実行がＤＭＥＭの後続の領域で繰り返される（ステップ１７７４、１７７６、１７６８、および１７７０）。この時点でマスタータイルプロセッサから受け取る次の命令は、次のタスク間隔のためであり、次のタスク間隔も全ての領域に渡って実行される。
【００７２】
タイルプロセッサにおけるコヒーレンシー要求は、リモート相互接続からのリモート要求を別の操作で取り扱うことにより維持している。ロードがコヒーレンシー要求を満たすかどうかの基準は、ロードのターゲットとなるタイルプロセッサと領域において、領域がロードに関連付けられたタスクＩＤに応じたタスク間隔を終了していなければならないということである。これはロードのタスクＩＤと領域で終了したタスクＩＤを比較することによって分かる。領域のタスクＩＤはロードに関連付けられたタスクＩＤ以上でなければならない。これはストアを実行したタスク間隔のタスクＩＤであるため、この基準は、ターゲット領域はストアの時点を越えて実行され、領域には正しい値が書かれていることを保障する。
【００７３】
もしこの基準を満たさなければ、アクセスはターゲットタイルプロセッサで基準を満たすまで保留され、おそらく結果として機能停止を引き起こす。この機能停止は実行を遅らせるが、めったにそういう事態には至らない。これは図２１の例から分かる。この図は、図１８Ａに似ているが、９個のタイルプロセッサと４つの領域に渡る３つのタスクの実行を示している。タスク間隔２１００（記述を明確にするため、タイルプロセッサＮ＋８についてのみ示してあるが、全てのタイルプロセッサに対して同一である）は、データの値を定義するストアで終了している。タスク間隔２１０２は、その値を読み込むロードで終了している。タスク間隔２１０４（この例では領域０に対してのみ示す）は、ロードした値を使用するところから始まる。タスク間隔は目盛りで示され、各々の間隔に対して４命令だと仮定する。隣接するタイルプロセッサは同じ命令を１サイクル違いで実行するので、図２１の実施例では、タイルプロセッサＮ＋４はタスク間隔２１００をタイルプロセッサＮより４サイクル後に開始する。このため、タイルプロセッサＮ＋４が領域０で実行を開始すると同時に、タイルプロセッサＮ＋１が領域３で実行を開始する。「Ｌ４／Ｌ５」と「Ｌ２／Ｌ３」と表示した矢印は、それぞれ、タイル相互接続のレベル４とレベル５を通過するロードとレベル２とレベル３を通過するロードに対する依存アークを表す。（９個のタイルプロセッサが隣接するが、もしプロセッサのグループがプロセッサのローカルグループ間の境界をまたぐと、タイルプロセッサ間のアクセスは相互接続の多数のレベルを要求し得る。）アークは実行に遅延が生じない、アクセスの最大の範囲を表す。この範囲はＬ４／Ｌ５ルートでは２２個の領域であり、Ｌ２／Ｌ３ルートでは３４個の領域である。記述を明確にするため、この図には示してないが、ローカルとレベル１ルートでは、範囲は６４個の領域までである。これらの範囲は、それぞれ２２、３４、および６４画素のエプロンアクセスに相当する。これらは、一般的に映像処理で要求される範囲よりかなり広い。ストア、ロード、およびロードしたデータの使用は、通常は図に示したよりもはるかに多くの命令によって隔てられているので、この範囲は通常はもっと大きいということも理解すべきである。さらに、８か１６領域の設定では、この範囲はもっと大きくなる。
【００７４】
ここで議論した、システム、プロセッサ、および方法は、タイルプロセッサ間での映像データの結合、ロードアクセスの待ち時間による性能劣化を避ける命令順序付け、およびデータ依存による性能劣化をたいていの場合避けられるコヒーレンシーメカニズムを提供する。ここで提供した説明は、本発明の原理と様々な実施例の実例となるはずである。ひとたび上記の開示を完全に理解すれば、多数の変形および変更は当業者にとって明白なものとなる。以下の特許請求は、そのような変形および変更をすべて包含するものと解釈されることを意図している。
【図１】
0006388865.tif 000002
【図２】
0006388865.tif 000003
【図３】
0006388865.tif 000004
【図４】
0006388865.tif 000005
【図５】
0006388865.tif 000006
【図６】
0006388865.tif 000007
【図７】
0006388865.tif 000008
【図８】
0006388865.tif 000009
【図９】
0006388865.tif 000010
【図１０】
0006388865.tif 000011
【図１１】
0006388865.tif 000012
【図１２】
0006388865.tif 000013
【図１３Ａ】
0006388865.tif 000014
【図１３Ｂ】
0006388865.tif 000015
【図１４】
0006388865.tif 000016
【図１５】
0006388865.tif 000017
【図１６Ａ】
0006388865.tif 000018
【図１６Ｂ】
0006388865.tif 000019
【図１６Ｃ】
0006388865.tif 000020
【図１６Ｄ】
0006388865.tif 000021
【図１６Ｅ】
0006388865.tif 000022
【図１７Ａ】
0006388865.tif 000023
【図１７Ｂ】
0006388865.tif 000024
【図１７Ｃ】
0006388865.tif 000025
【図１７Ｄ】
0006388865.tif 000026
【図１７Ｅ】
0006388865.tif 000027
【図１８Ａ】
0006388865.tif 000028
【図１８Ｂ】
0006388865.tif 000029
【図１９Ａ】
0006388865.tif 000030
【図１９Ｂ】
0006388865.tif 000031
【図１９Ｃ】
0006388865.tif 000032
【図１９Ｄ】
0006388865.tif 000033
【図２０】
0006388865.tif 000034
【図２１】
0006388865.tif 000035