(57)【特許請求の範囲】
【請求項１】
基本プロセッサ（３）を含み、各基本プロセッサ（３）が、少なくとも１つの計算ユニットと、メモリワードを含む少なくとも１つのメモリと、を含み、かつトポロジ内の予め定められた位置となるようにトポロジに従って配置され、
かつ異なるデータに対して同じ命令を同時に実行することができ、前記命令が、少なくとも１つのオペランドの読み出しを含み、かつ／または少なくとも１つの結果の書き込みを含む並列プロセッサであって、
前記命令は、並列プロセッサに含まれる各基本プロセッサのそれぞれが行う読み出しのセットおよび／または書き込みのセットを示すものであり、
前記命令は、読み出しおよび／または書き込みが行われる対象を示す動作フィールドを定義するものであり、
前記動作フィールドは、各基本プロセッサのそれぞれが読み出しおよび／または書き込みを行う対象であるメモリワードのセットを示すものであり、
各基本プロセッサのそれぞれが読み出しおよび／または書き込みを行う対象であるメモリワードは、並列プロセッサに含まれるいずれかの基本プロセッサのメモリに配置されるものであり、
前記命令のオペランドのための前記動作フィールドは、各基本プロセッサのそれぞれによって読み出される前記メモリワードのセットを示すものであり、
前記命令の結果のための前記動作フィールドは、各基本プロセッサのそれぞれによって書き込まれる前記メモリワードのセットを示すものであり、
前記命令は、前記オペランドおよび／または前記結果用に、前記動作フィールドの位置に関する情報を含むものであり、
前記動作フィールドの位置は、Ｎ次元タイプのテーブルの一意のデータ構造内の位置として定義されるものであり、
前記Ｎは１以上の整数であり、
前記Ｎ次元タイプのテーブルの一意のデータ構造は、並列プロセッサに含まれる異なる基本プロセッサのメモリにわたって分配して配置されるものである、
ことを特徴とする並列プロセッサ。
【請求項２】
各基本プロセッサ内の各オペランドおよび／または各結果のアドレスを、前記動作フィールドの位置および前記トポロジ内の前記基本プロセッサの位置の関数として計算する手段を含むことを特徴とする、請求項１に記載の並列プロセッサ。
【請求項３】
前記アドレスを計算する前記手段に接続された、前記動作フィールドの位置を前記情報の関数として計算する手段（５０）を含むことを特徴とする、請求項２に記載の並列プロセッサ。
【請求項４】
各基本プロセッサ内の前記アドレスを計算する前記手段（４１、４２、４３）が、各基本プロセッサのレベルで局在化されることを特徴とする、請求項２または３に記載の並列プロセッサ。
【請求項５】
各基本プロセッサ内の前記アドレスを計算する前記手段が、各基本プロセッサのレベルで部分的に局在化され、かついくつかの基本プロセッサ間で部分的にグループ化されることを特徴とする、請求項２または３に記載の並列プロセッサ。
【請求項６】
前記動作フィールドの位置を計算する前記手段が、
− 前記基本プロセッサの全てに共通か、または
− 前記オペランドおよび／または前記結果のアドレスを計算する前記手段のレベルで完全にまたは部分的に局在化されることを特徴とする、請求項３に記載の並列プロセッサ。
【請求項７】
前記基本プロセッサが、Ｐ次元を有するトポロジに従って配置され、Ｐが、１以上の整数であることを特徴とする、請求項１〜６のいずれか一項に記載の並列プロセッサ。
【請求項８】
前記基本プロセッサが、少なくとも１つの次元を有するトポロジに従って配置され、各次元に対し、前記次元に従ってｘ座標がｐである基本プロセッサに関連する前記データ構造の要素のアドレスを計算する前記手段が、前記動作フィールドの位置に関連する値および前記基本プロセッサの位置に関連する値の関数として前記アドレスを得るものであることを特徴とする、請求項２〜６のいずれか一項に記載の並列プロセッサ。
【請求項９】
前記動作フィールドが、自身の座標によって定義される端部を有し、前記動作フィールドの位置が、これらの端部の線形結合によって得られた重心の位置によって定義され、前記端部の有意性の合計が１に等しいことを特徴とする、請求項１〜８のいずれか一項に記載の並列プロセッサ。
【請求項１０】
前記動作フィールドが、自身の座標によって定義される端部を有し、前記動作フィールドの位置が、座標が最小である前記端部の位置によって定義されることを特徴とする、請求項１〜８のいずれか一項に記載の並列プロセッサ。
【請求項１１】
前記動作フィールドが、自身の座標によって定義される端部を有し、前記動作フィールドの位置が、座標が最小である前記端部の位置によって定義され、
前記基本プロセッサが、１つの次元を有するトポロジに従って配置され、各次元に対し、前記次元に従ってｘ座標がｐである前記基本プロセッサに関連する前記データ構造の要素のアドレスを計算する前記手段が、
Ａｄ＝Ｉｎｔ（（Ｗｍｉｎ＋Ｎｐ−１−ｐ）／Ｎｐ）
を計算する手段を含み、
Ｎｐが、前記次元における問題の基本プロセッサの数であり、Ｗｍｉｎが、前記動作フィールドに含まれる前記データ構造の要素のうちの各次元における座標が最小である要素の前記位置の座標の関数として定義されるものであり、Ｉｎｔは引数の整数部分を指し示す関数であり、Ａｄはｘ座標がｐである基本プロセッサに関連する前記データ構造の要素の、当該要素が配置される並列プロセッサに含まれるいずれかの基本プロセッサのメモリ内のアドレスであることを特徴とする、請求項２〜６、８のいずれか一項に記載の並列プロセッサ。
【請求項１２】
前記基本プロセッサが、１つの次元を有するトポロジに従って配置され、前記データ構造が１次元であることと、前記動作フィールドの位置が、ＸｍｉｎおよびＷｍｉｎ＝Ｘｍｉｎによって定義されることと、を特徴とする、請求項１１に記載の並列プロセッサ。
【請求項１３】
Ｎｐが２の累乗であり、Ａｄを計算する前記手段が、
− Ｘｍｉｎおよび（Ｎｐ−１−ｐ）を加算し、
− Ｘｍｉｎと（Ｎｐ−１−ｐ）を加算した結果である和から、Ｎｐの底２の対数をＬＮｐとしたときの、最後のＬＮｐビットを削除する
ための手段を含むことを特徴とする、請求項１２に記載の並列プロセッサ。
【請求項１４】
前記基本プロセッサが、１つの次元を有するトポロジに従って配置され、前記データ構造が２次元で、ＸおよびＹの関数として定義され、Ｘに沿った前記データ構造の寸法が、所定値Ｌｘより小さいことと、ＸｍｉｎとＹｍｉｎがそれぞれ、前記動作フィールドに含まれる前記データ構造の要素のうちのＸ次元における座標とＹ次元における座標が最小である要素の前記位置のＸ座標とＹ座標であるとしたときに、前記動作フィールドの位置が、Ｘｍｉｎ、ＹｍｉｎおよびＷｍｉｎ＝Ｘｍｉｎ＋Ｌｘ＊Ｙｍｉｎによって定義されることと、を特徴とする、請求項１１に記載の並列プロセッサ。
【請求項１５】
ＮｐおよびＬｘが２の累乗であり、
Ｎｐの底２の対数をＬＮｐとし、Ｌｘの底２の対数をＬＬｘとし、
Ａｄを計算する前記手段が、
−  Ｘｍｉｎと（Ｎｐ−１−ｐ）を加算し、
−  Ｘｍｉｎと（Ｎｐ−１−ｐ）を加算した結果である和から、最後のＬＮｐビットを削除し、
−  前記和から最後のＬＮｐビットを削除した量であって、ＬＬｘ−ＬＮｐビットにわたって表された量を最下位位置に置いて、及び、Ｙｍｉｎを最上位位置に置いて、これらの最下位位置と最上位位置を連結してＡｄとする
ための手段を含むことを特徴とする請求項１４に記載の並列プロセッサ。
【請求項１６】
前記基本プロセッサが、１つの次元を有するトポロジに従って配置され、前記データ構造が３次元で、Ｘ、ＹおよびＺの関数として定義され、ＸおよびＹに沿った前記データ構造の寸法が、所定値ＬｘおよびＬｙより小さいことと、
ＸｍｉｎとＹｍｉｎとＺｍｉｎがそれぞれ、前記動作フィールドに含まれる前記データ構造の要素のうちのＸ次元における座標とＹ次元における座標とＺ次元における座標が最小である要素の前記位置のＸ座標とＹ座標とＺ座標であるとしたときに、前記動作フィールドの位置が、Ｘｍｉｎ、Ｙｍｉｎ、ＺｍｉｎおよびＷｍｉｎ＝Ｘｍｉｎ＋Ｌｘ＊（Ｙｍｉｎ＋Ｌｙ＊Ｚｍｉｎ）によって定義されることと、を特徴とする、請求項１１に記載の並列プロセッサ。
【請求項１７】
Ｎｐ、ＬｘおよびＬｙが２の累乗であり、
Ｎｐの底２の対数をＬＮｐとし、Ｌｘの底２の対数をＬＬｘとし、Ｌｙの底２の対数をＬＬｙとし、
Ａｄを計算する前記手段が、
−  Ｘｍｉｎと（Ｎｐ−１−ｐ）を加算し、
−  Ｘｍｉｎと（Ｎｐ−１−ｐ）を加算した結果である和から、最後のＬＮｐビットを削除し、
−  前記和から最後のＬＮｐビットを削除した量であって、ＬＬｘ−ＬＮｐビットにわたって表された量を最下位位置に置いて、ＬＬｙビットにわたって表されるＹｍｉｎを中間位位置に置いて、及び、Ｚｍｉｎを最上位位置に置いて、これらの最下位位置と中間位位置と最上位位置を連結してＡｄとする
ための手段を含むことを特徴とする請求項１６に記載の並列プロセッサ。
【請求項１８】
前記基本プロセッサが、１つの次元を有するトポロジに従って配置され、前記データ構造が４つの次元を有して、Ｘ、Ｙ、ＺおよびＴの関数として定義され、Ｘ、ＹおよびＺによる前記データ構造の寸法が、所定値Ｌｘ、ＬｙおよびＬｚよりそれぞれより小さいことと、ＸｍｉｎとＹｍｉｎとＺｍｉｎとＴｍｉｎがそれぞれ、前記動作フィールドに含まれる前記データ構造の要素のうちのＸ次元における座標とＹ次元における座標とＺ次元における座標とＴ次元における座標が最小である要素の前記位置のＸ座標とＹ座標とＺ座標とＴ座標であるとしたときに、前記動作フィールドの位置が、Ｘｍｉｎ、Ｙｍｉｎ、Ｚｍｉｎ、ＴｍｉｎおよびＷｍｉｎ＝Ｘｍｉｎ＋Ｌｘ＊（Ｙｍｉｎ＋Ｌｙ＊（Ｚｍｉｎ＋Ｌｚ＊Ｔｍｉｎ））によって定義されることと、を特徴とする、請求項１１に記載の並列プロセッサ。
【請求項１９】
前記基本プロセッサがＸ次元とＹ次元の２つの次元を有するトポロジに従って配置され、かつ、Ｘ次元方向にはＮｘ個の基本プロセッサが配置され、Ｙ次元方向にはＮｙ個の基本プロセッサが配置されることにより、並列プロセッサ全体ではＮｘ＊Ｎｙ個の基本プロセッサが配置され、
前記データ構造が２次元で、ＸおよびＹの関数として定義され、
前記データ構造のＸ次元に沿った寸法が所定値Ｌｘより小さく、
ＸｍｉｎとＹｍｉｎがそれぞれ、前記動作フィールドに含まれる前記データ構造の要素のうちのＸ次元における座標とＹ次元における座標が最小である要素の前記位置のＸ座標とＹ座標であるとしたときに、前記動作フィールドの前記位置が、ＸｍｉｎとＹｍｉｎによって定義された並列プロセッサにおいて、
Ｘ次元におけるｘ座標がｐｘでありＹ次元におけるｙ座標がｐｙである基本プロセッサに関連する前記データ構造の要素の、当該要素が配置される並列プロセッサに含まれる基本プロセッサのいずれかのメモリ内のアドレスであるＡｄを計算する手段を備え、
Ａｄを計算する前記手段は、Ｉｎｔを引数の整数部分を指し示す関数であるとしたときに、
Ａｄｘ＝Ｉｎｔ（（Ｘｍｉｎ＋Ｎｘ−１−ｐｘ）／Ｎｘ）
Ａｄｙ＝Ｉｎｔ（（Ｙｍｉｎ＋Ｎｙ−１−ｐｙ）／Ｎｙ）
からなる式に基づき、ＡｄｘとＡｄｙを求め、さらに、ＡｄｘとＡｄｙの値の組み合わせを引数とする関数を用いてＡｄを求めるものである、
ことと、を特徴とする、請求項１に記載の並列プロセッサ。
【請求項２０】
前記データ構造のＹ次元に沿った寸法が所定値Ｌｙより小さく、
Ｎｘ、Ｎｙ、ＬｘおよびＬｙが２の累乗であり、
Ｎｘの底２の対数をＬＮｘとし、Ｎｙの底２の対数をＬＮｙとし、Ｌｘの底２の対数をＬＬｘとし、Ｌｙの底２の対数をＬＬｙとする並列プロセッサであって、
前記Ａｄを計算する前記手段は、
−  Ｘｍｉｎと（Ｎｘ−１−ｐｘ）を加算し、
−  Ｘｍｉｎと（Ｎｘ−１−ｐｘ）を加算した結果である和から、最後のＬＮｘビットを削除して、ＬＬｘ−ＬＮｘビットのＡｄｘを得て、
−  Ｙｍｉｎと（Ｎｙ−１−ｐｙ）を加算し、
−  Ｙｍｉｎと（Ｎｙ−１−ｐｙ）を加算した結果である和から、最後のＬＮｙビットを削除して、ＬＬｙ−ＬＮｙビットのＡｄｙを得て、
−  ＬＬｘ−ＬＮｘビットにおいて表されるＡｄｘを最下位位置に置いて、および、ＬＬｙ−ＬＮｙビットにおいて表されるＡｄｙを最上位位置に置いて、これらの最下位位置と最上位位置を連結することによりＡｄを得るものである、ことを特徴とする、請求項１９に記載の並列プロセッサ。
【請求項２１】
前記基本プロセッサが、Ｘ次元、Ｙ次元、Ｚ次元を少なくとも有する３次元以上のトポロジに従って配置され、かつ、Ｘ次元方向にはＮｘ個の基本プロセッサが配置され、Ｙ次元方向にはＮｙ個の基本プロセッサが配置され、Ｚ次元方向にはＮｚ個の基本プロセッサが配置され、
前記データ構造が３次元以上であり、少なくともＸ、Ｙ、Ｚを引数とする関数として定義され、
前記データ構造のＸ次元に沿った寸法が所定値Ｌｘより小さく、前記データ構造のＹ次元に沿った寸法が所定値Ｌｙより小さく、前記データ構造のＺ次元に沿った寸法が所定値Ｌｚより小さく、
Ｌｘ、Ｌｙ、Ｌｚ、Ｎｘ、Ｎｙ及びＮｚは２の累乗であり、
Ｎｘの底２の対数をＬＮｘとし、Ｎｙの底２の対数をＬＮｙとし、Ｎｚの底２の対数をＬＮｚとし、Ｌｘの底２の対数をＬＬｘとし、Ｌｙの底２の対数をＬＬｙとし、Ｌｚの底２の対数をＬＬｚとする並列プロセッサにおいて、
Ｘ次元におけるｘ座標がｐｘでありＹ次元におけるｙ座標がｐｙでありＺ次元におけるｚ座標がｐｚである基本プロセッサに関連する前記データ構造の要素の、当該要素が配置される並列プロセッサに含まれる基本プロセッサのいずれかのメモリ内のアドレスであるＡｄを計算する手段を備え、
Ａｄを計算する前記手段は、
−  前記動作フィールドに含まれる前記データ構造の要素のうちの各次元における座標が最小である要素の前記位置の座標の各次元の値を連結して、ＬＬｘ＋ＬＬｙ＋ＬＬｚ＋…ビットの単一ワードとしてｗを得て、
−  ｗのビットの順序を入れ替えて、ｗ’を得て、
−  ｗ’を、ＬＬｘ、ＬＬｙ、ＬＬｚ…ビットのワードに分割して、ｗｘ’、ｗｙ’、ｗｚ’を得るものであり、
さらに、
−  （Ｎｘ−１−ｐｘ）とｗｘ’を加算し、
−  （Ｎｘ−１−ｐｘ）とｗｘ’を加算した結果である和から、最後のＬＮｘビットを削除して、Ａｄｘ’を得て、
−  （Ｎｙ−１−ｐｙ）とｗｙ’を加算し、
−  （Ｎｙ−１−ｐｙ）とｗｙ’を加算した結果である和から、最後のＬＮｙビットを削除して、Ａｄｙ’を得て、
−  （Ｎｚ−１−ｐｚ）とｗｚ’を加算し、
−  （Ｎｚ−１−ｐｚ）とｗｚ’を加算した結果である和から、最後のＬＮｚビットを削除して、Ａｄｚ’を得て、
−  以下、Ｘ、Ｙ、Ｚ以外の次元が存在するならば、同様の計算を行い、
Ａｄｘ’、Ａｄｙ’、Ａｄｚ’…を得たら、
−  Ａｄｘ’、Ａｄｙ’、Ａｄｚ’…のビットの順序を入れ替えて、Ａｄｘ、Ａｄｙ、Ａｄｚ…を得て、
−  Ａｄｘ、Ａｄｙ、Ａｄｚ…を連結して、Ａｄを得るものである、
ことを特徴とする、請求項１記載の並列プロセッサ。
【請求項２２】
前記並列プロセッサがＳＩＭＤ型のコンピュータであることを特徴とする、請求項１〜２１のいずれか一項に記載の並列プロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特にＳＩＭＤ型の並列コンピュータに適用可能な、並列プロセッサ用のアドレス指定装置に関する。
【０００２】
用語ＳＩＭＤは、Ｆｌｙｎｎによって導入された並列コンピュータの部類を指す。それは、単一命令複数データ流（ＳＩＭＤ）型の並列コンピュータを示す。
【背景技術】
【０００３】
過去において、ＳＩＭＤを実現するためには１つまたは複数の電子基板が必要だった。現在、ＳＩＭＤは、単一の集積回路、例えばＦＰＧＡまたはＡＳＩＣに配置することができる。
【０００４】
図１に関連して説明するＳＩＭＤには、
単一のシーケンサ１と、
単一の命令メモリ２と、
多数の基本プロセッサ３または処理要素（ＰＥ）と、
が含まれる。
【０００５】
各ＰＥ３には、
演算論理ユニット（ＡＬＵ）３１と、
メモリおよび／またはデータレジスタのセット３２と、
が含まれる。
【０００６】
各サイクルにおいて、シーケンサは、
次の命令を決定し、それを命令メモリから読み出し、
この命令を全てのＰＥに送信する。
【０００７】
ほとんどの命令は、
実行される演算と、
演算の各オペランドをフェッチするアドレスＡｄと、
結果を記憶する１つまたは複数のアドレスＡｄと、
を定義する。
【０００８】
実行される演算には、１つまたは複数のオペランドが含まれる。この演算は、１つまたは複数のオペランドを含む基本演算（例えば、符号反転か、加算か、条件判断か、もしくは最大値計算）に制限することができ、またはそれは、いくつかの基本演算の組み合わせ（例えば、乗算とそれに続く加算）とすることができる。同様に、結果は、１つまたは複数のアドレスに記憶することができる。
【０００９】
各ＰＥは、同時に、しかしこの例ではメモリおよび／またはＰＥに属するレジスタのセットにおける異なるデータに関して、この同じ命令を実行する。
【００１０】
当然ながら、表現「各サイクルにおいて」は、論理サイクル、すなわちその実行が、従来のパイプライン技術によるいくつかの物理サイクルにわたり得る論理サイクルを指す。重要なことは、新しい命令が各サイクルにおいて開始されること、および新しい命令が各サイクルにおいて完了されることである。命令の実行がいくつかのサイクルにわたるかどうかは、問題ではない。
【００１１】
命令Ｒ（２３）＝Ｒ（８）＋Ｒ（３）＊Ｒ（１９）を例にとる。これが意味するのは、レジスタ３の内容を読み出し、それにレジスタ１９の内容を乗算し、この乗算の結果をレジスタ８の内容に加算し、この加算の結果をレジスタ２３に書き込むことである。この同じ命令は、ＰＥの全てによって並列に実行される。しかしながら、各ＰＥは、それに属するレジスタセットにおいて、この命令を実行する。全部で１２８のＰＥがある場合には、命令の実行は、１２８のレジスタ３が読み出され、１２８のレジスタ１９が読み出され、１２８のレジスタ８が読み出されることに帰着し、１２８の乗算が、２×１２８の異なる値に対して実行され、１２８の加算が、２×１２８の異なる値に対して実行され、１２８の異なる結果が、１２８のレジスタ２３に書き込まれる。
【００１２】
ＳＩＭＤの効率は、この高度な並列性からもたらされる。
【００１３】
一般に、ＳＩＭＤにおいて、各ＰＥは、それに属するメモリおよび／またはレジスタのセットからだけでなく、そのネイバーの１つに属するメモリおよび／またはレジスタのセットの全てもしくはいくつかから、命令のオペランドを読み出す、すなわちフェッチする可能性を有する。補完または代替になり得る変形は、各ＰＥが、それに属するメモリおよび／またはレジスタだけでなく、そのネイバーの１つに属するメモリおよび／またはレジスタに、命令の結果を書き込む可能性を有するということである。
【００１４】
ＰＥ間の隣接の概念は、ＳＩＭＤのアーキテクチャによって、より正確にはＰＥ間の相互接続トポロジによって定義される。ＰＥ間のいくつかの相互接続トポロジが、提案された。最も複雑な相互接続トポロジは、ＰＥ間の真の相互接続ネットワークである。最も単純な相互接続トポロジは、ＰＥの垂直列である。別の単純なトポロジは、ＰＥの２次元格子である。また、ＰＥの多次元格子を想定することが可能である。一般に、これらの最後の３つの場合には、端部は「再結合」される。したがって、１次元トポロジでは、ＰＥの垂直列は、ＰＥの円（用語「ＰＥのリング」がしばしば用いられる）になる。この再結合ゆえに、ＰＥの最も南のサウスネイバー（Ｓｏｕｔｈ  ｎｅｉｇｈｂｏｒ）は、最も北のＰＥであり、ＰＥの最も北のノースネイバー（Ｎｏｒｔｈ  ｎｅｉｇｈｂｏｒ）は、最も南のＰＥである。同様に、２次元トポロジでは、ＰＥの格子は、トロイドになる。最後に、多次元トポロジでは、多次元格子は、多次元トロイドになる。
【００１５】
１次元トポロジ（ＰＥの垂直列またはリング）の場合には、各ＰＥが、（ノースおよびサウスの代わりに）ＮおよびＳと呼ばれる２つのネイバーを有する。２次元トポロジ（ＰＥの２次元格子またはトロイド）の場合には、各ＰＥは、（ノース、サウス、イーストおよびウェストの代わりに）Ｎ、Ｓ、Ｅ、Ｗと呼ばれる４つのネイバーを有する。多次元トポロジ（ＰＥの多次元格子または多次元トロイド）の場合には、各ＰＥは、２ｎのネイバーを有し、ここでｎは、空間次元である。
【００１６】
本明細書の残りでは、１次元トポロジの場合が１番目と見なされ、次が２次元トポロジの場合、次が多次元トポロジの場合と見なされる。
【００１７】
現代のＳＩＭＤにおける典型的な命令は、全てのＰＥ（またはそれらのいくつか）に、いくつかのオペランドに関連する演算（全てのＰＥに対して同じ演算）を実行し、かつ結果を１つまたは複数の位置に記憶するように要求する。前の例に戻ると、命令Ｒ（２３）＝Ｒ（８）＋Ｒ（３）＊Ｒ（１９）は、全てのＰＥに、３つのオペランドに関連する演算を実行し、かつ結果を１つの位置に記憶するように要求する。
【００１８】
ほとんどのＳＩＭＤにおいて、命令は、各オペランドおよび各結果について、異なるＰＥがオペランドを読み出す（または結果を記憶する）アドレスを定義する。したがって、アドレスは、所与の結果位置と同様に所与のオペランドに関し、全てのＰＥに対して必ず同じである。
【００１９】
かかるアプローチは、特に、画像処理、画像圧縮、合成画像生成、信号処理、または偏微分方程式を解くためのある技術のような典型的な用途において、問題を生じる。例えば、これらの用途が、画素がそのネイバーから計算されるアルゴリズムを用い、ＰＥのトポロジが１次元、２次元または多次元であろうとなかろうと、そうする場合である。
【００２０】
この困難を示すために、リングに構成された１６ＰＥのＳＩＭＤを考えながら、画像処理を用いる例をとって分析する。
【００２１】
本明細書の残りの全てにおいて、数式を単純化するために、プロセッサは、０から始まって番号を付けられる。データ構造（信号、画像またはボリューム）の行および列も同様である。
【００２２】
画像の画素を異なるＰＥのメモリに配置する従来の方法は、画像の行０を記憶および処理するためにＰＥ０（ＰＥ  Ｎ°０）を用い、行１を記憶および処理するためにＰＥ１（ＰＥ  Ｎ°１）を用い、そして行１５を記憶および処理するためのＰＥ１５（ＰＥ  Ｎ°１５）まで同様である。画像には一般に１６を超える行が含まれるので、ユーザは、画像の行０、１６、３２、４８、６４、８０、．．．を記憶および処理するためにＰＥ０を用い、画像の行１、１７、３３、４９、６５、８１、．．．を記憶および処理するためにＰＥ１を用い、そして画像の行１５、３１、４７、６３、７９、９５、．．．を記憶および処理するためのＰＥ１５まで同様である。
【００２３】
この記憶システムでは、ＮｐがＰＥの数を示す場合、およびＬｘが、処理される画像の幅を示す場合には、座標（ｘ、ｙ）を有する画素は、次の式に従ってアドレスＡｄにおいてプロセッサｐに記憶される。
ｐ＝ｙ  Ｍｏｄ  Ｎｐ
Ａｄ＝ｘ＋Ｌｘ＊Ｉｎｔ（ｙ／Ｎｐ）、（Ｉｎｔ（ｚ）は、ｚの整数部を示す）
【００２４】
この記憶システムを図２に示す。この図は、幅６４画素の画像の場合を考え、それを、リングトポロジで構成された１６ＰＥのＳＩＭＤに記憶する通常の方法を示す。この図では、列は、画像の列を表し、行は、画像の行を表し、ＰＥの番号は、各行の左端に示され、各画素が記憶されるアドレスは、各ボックスの内部に示される。この図では、続く２つの図におけるように、同一アドレスを備えたゾーン（全てのＰＥにおいて同じアドレスを有するゾーン）間の境界は、黒線によって示される。
【００２５】
慣例により、画像の左が、低ｘ座標を有する画素によって構成されるのに対して、画像の上部が、低ｙ座標を有する画素によって構成される視覚表現が選択された。したがって、エッジが座標の軸と並行な正方形の左上コーナーは、最低ｘ座標および最低ｙ座標のポイントであるのに対して、右下コーナーは、最高ｘ座標および最高ｙ座標のポイントである。この慣例は、以下で用いられる。
【００２６】
この記憶システムは、ＳＩＭＤをＰＥの垂直リングと見なすことになる。ＳＩＭＤをＰＥの垂直リングとしてではなく水平リングとして見なし、かつもはや画像の行を記憶するためではなく、画像の列を記憶するためにＰＥを用いることに存する逆の選択が、明らかになし得る。図３は、この記憶システムを示す。実際には、それは、単に、機械のレベルでは事実上何も変更しない、プログラマの視覚表現の選択の問題である。以下で、行における表現に関して説明されることは、明らかに列における表現に適用可能である。
【００２７】
上記した、ＰＥへの画像の行の割り当てにおけるタイプは、それが、２つの画像の加算、２つの画像の乗算、定数による画像の乗算、行マスクによる画像の畳み込み．．．のような単純な演算の問題である場合、実際には、それが、オペランドとして働く画素および結果画素が同じＰＥによって記憶される単純な演算の問題である場合には、いかなる問題ももたらさない。
【００２８】
それが、オペランドとして働く画素および結果画素が異なるＰＥによって記憶される演算の問題である場合には、事態はより複雑になる。例えば、２次元マスクによる画像の畳み込みの場合において、結果画素を記憶するのに関与するＰＥは、それに属するメモリおよび／またはレジスタにおいてだけでなく、隣接するＰＥに、またはネイバーのネイバーにさえ、またはさらに遠くにさえ属するメモリおよび／またはレジスタにおいて、それがその計算を実行するために必要とするオペランドをフェッチしなければならない。
【００２９】
左上コーナーが座標ｘ＝８、ｙ＝４を有し、かつ右下コーナーが座標ｘ＝３９、ｙ＝３５を有する３２×３２正方形において３×３畳み込みを実行すること、およびその結果を、左上コーナーが座標ｘ＝８、ｙ＝６８を有し、かつ右下コーナーが座標ｘ＝３９、ｙ＝９９を有する３２×３２正方形に記憶することが望ましいと仮定する。上述のように、問題のｘｙ基準では、ｘ軸は、左から右へ増加し、ｙ軸は、上から下に増加することが想起される。
【００３０】
ａ（−１、−１）、ａ（０、−１）、ａ（１、−１）、ａ（−１、０）、ａ（０、０）、ａ（１、０）、ａ（−１、１）、ａ（０、１）およびａ（１、１）を畳み込みフィルタの９つの係数とする。
【００３１】
Ｉ（ｘ、ｙ）をオリジナル画像の画素とする。
【００３２】
Ｒ（ｘ、ｙ＋６４）を結果画像の画素とする。
【００３３】
８および３９間のｘの各値、ならびに４および３５間のｙの各値のために実行される計算は、次のとおりである。
Ｒ（ｘ、ｙ＋６４）＝ａ（−１、−１）＊Ｉ（ｘ−１、ｙ−１）＋ａ（０、−１）＊Ｉ（ｘ、ｙ−１）＋ａ（１、−１）＊Ｉ（ｘ＋１、ｙ−１）＋ａ（−１、０）＊Ｉ（ｘ−１、ｙ）＋ａ（０、０）＊Ｉ（ｘ、ｙ）＋ａ（１、０）＊Ｉ（ｘ＋１、ｙ）＋ａ（−１、１）＊Ｉ（ｘ−１、ｙ＋１）＋ａ（０、１）＊Ｉ（ｘ、ｙ＋１）＋ａ（１、１）＊Ｉ（ｘ＋１、ｙ＋１）
【００３４】
第１の演算は、上端部が座標ｘ＝８、ｙ＝４を有し、かつ底端部が座標ｘ＝８、ｙ＝１９を有する１６×１垂直セグメントに対してこの畳み込みを実行することである。このセグメントは、図２に濃い灰色で示す。この第１の演算の第１のステップは、上端部が座標ｘ＝７、ｙ＝３を有し、かつ底端部が座標ｘ＝７、ｙ＝１８を有する１６×１垂直セグメントを読み出すことである。このセグメントは、図２に薄い灰色で示す。読み出された１６画素のそれぞれは、畳み込みマスクの第１の係数によって乗算される。次のステップは、上端部が座標ｘ＝８、ｙ＝３を有し、かつ底端部が座標ｘ＝８、ｙ＝１８を有する１６×１垂直セグメントを読み出すことである。読み出された１６画素のそれぞれは、畳み込みマスクの第２の係数によって乗算され、この第２の乗算の結果は、第１の乗算の結果に加算される。この手順は、この方法で、畳み込みマスクの９つの係数（３×３畳み込みが例としてとられたので９つの係数である）に対して継続する。したがって、この結果は、上端部が座標ｘ＝８、ｙ＝６８を有し、かつ底端部が座標ｘ＝８、ｙ＝８３を有する１６×１垂直セグメントに記憶される。このようにして、第１の演算は完了する。次に、処理される正方形の上半分の残りの３１列を処理するために、３１の同様の演算があり、次に、この正方形の下半分の３２列を処理するために、３２の同様の演算がある。
【００３５】
第１の演算の第１のステップから困難が現れる。次に、それは、全ての演算の全てのステップに対して同じである。この第１のステップに対して、上端部が座標ｘ＝７、ｙ＝３を有し、かつ底端部が座標ｘ＝７、ｙ＝１８を有する１６×１垂直セグメントを読み出すことが必要である。図に示すように、ＰＥ３〜１５用に読み出される画素はアドレス７に記憶され、一方でＰＥ０〜２用に読み出される画素はアドレス７１に記憶されている。
【００３６】
しかしながら、従来のＳＩＭＤでは、シーケンサは、全てのＰＥに同じアドレスを送信する。
【００３７】
選択された例は、エッジが同一アドレスのゾーン間の境界と整列していない矩形、すなわち、ＰＥの数の倍数でないｙ座標を上端部が有する矩形に関連することに、異議を唱えることが可能である。この異議は、分析に耐えられない。一方では、かかる矩形を処理しなければならないケースは、画像処理において頻繁にあるケースである。他方では、たとえ、結果画像を含む矩形が、同一アドレスのゾーン間の境界と整列したエッジを有している場合でも、それでもやはり、３×３畳み込みの様々なステップを処理するために、端部が、全て、同一アドレスのゾーン間の境界と整列しているわけではない１６×１垂直セグメントをオペランドとしてフェッチすることが必要であろう。
【００３８】
この困難を克服するためのいくつかの技術が提案された。
【００３９】
第１の技術は、ＰＥの条件付き作動を伴う、２つの段階におけるローディングである。第１の段階では、アドレス７で読み出さなければならないＰＥだけが、実際に読み出し演算を実行する。第２の段階では、アドレス７１で読み出さなければならないＰＥだけが、実際に読み出し演算を実行する。したがって、次の事実を管理しなければならないのは、演算のプログラマである。すなわち、この第１のステップを実行するために、あるＰＥは、それらがアドレス７に記憶した画素をオペランドとしてロードしなければならないのに対して、他のＰＥは、それらがアドレス７１に記憶した画素をオペランドとしてロードしなければならないという事実である。このことから、この種の機械をプログラムする際の大きな困難が生じる。また、実行される余分な命令ゆえに、実行効率がより低くなる。
【００４０】
第２の技術は、各ＰＥ内に間接レジスタを実装することである。間接レジスタは、このレジスタにアドレスが含まれているワードにアクセスすることを可能にするレジスタである。この間接レジスタゆえに、各ＰＥは、それ自身のものであるアドレスを計算し、それを間接レジスタにロードし、それを、それ自身のメモリにアクセスするために使用することができる。しかしながら、第１の技術と同様に、再び、一方では、追加的なプログラミングの困難があり（なぜなら、この困難を処理しなければならないのはアプリケーションプログラマであるからである）、他方では、実行される余分な命令ゆえに、実行効率がより低くなる。
【００４１】
他の技術を検討した。それらの全ては、一方では、追加的なプログラミングの困難を生じ、他方では、実行される余分な命令ゆえに実行効率の低下を生じるという事実を共通に有する。
【００４２】
２次元トポロジに従って構成されたＳＩＭＤが用いられる場合には、困難はさらに大きくなる。図４ａおよび４ｂは、幅６４画素の画像の同じ例を再び用いるが、しかし４×４トロイドトポロジに従って構成された１６ＰＥのＳＩＭＤを用いる。第１の演算の第１のステップ用に、左上コーナーが座標ｘ＝７、ｙ＝３を有し、かつ右下コーナーが座標ｘ＝１０、ｙ＝６を有する４×４正方形を読み出すことが必要である。この正方形は、図４ａに薄い灰色で示す。図４ｂに示すように、読み出される画素は、もはや以前のように２つの異なるアドレスに記憶されているのではなく、４つの異なるアドレス、すなわち、ＰＥ１５用のアドレス１、ＰＥ１２、１３および１４用のアドレス２、ＰＥ３、７および１１用のアドレス１７、ならびに他のＰＥ用のアドレス１８に記憶されている。
【００４３】
多次元トポロジに従って構成されたＳＩＭＤが用いられる場合には、困難は再び増加する。例えば、読み出される画素は、異なるアドレスの数がより低い特別な場合（読み出されるかまたは書き込まれるゾーンの特定の位置）を除いて、３次元トポロジでは８つの異なるアドレスに記憶され、４次元トポロジでは１６の異なるアドレスに記憶されている。
【発明の概要】
【発明が解決しようとする課題】
【００４４】
本発明の目的は、これらの欠点を克服することである。
【課題を解決するための手段】
【００４５】
本発明は、次の事実に基づいている。すなわち、命令は、各基本プロセッサがそれ自身のメモリにおいて読み出すかまたは書き込むアドレスを示すことによって基本プロセッサの読み出しのセットおよび／または書き込みのセットを定義するのではなく、基本プロセッサのそれぞれの、それ自身のメモリにおける読み出しおよび／または書き込みのセットを、動作フィールドにおける読み出しおよび／または書き込みとして定義する。
【００４６】
ユーザが見て取れるように、基本プロセッサセットのメモリワードのセットは、Ｎ次元タイプのテーブルの一意のデータ構造として見なされるが、このテーブルは、信号（１次元）または画像（２次元）またはボリューム（３次元）または．．．を表すことができる。動作フィールドは、このデータ構造を参照して、かつこのデータ構造のサブセットとして、命令によって定義される。
【００４７】
用語「動作フィールド」は、基本プロセッサ当たり１メモリワードの割合におけるメモリワードのセットを指すが、このメモリワードは、基本プロセッサのメモリに位置し、オペランドの動作フィールドは、このオペランドを得るために、それぞれがそれ自身のメモリにある、基本プロセッサによって読み出されるメモリワードのセットであり、結果の動作フィールドは、この結果を記憶するために、それぞれがそれ自身のメモリにある、基本プロセッサによって書き込まれるメモリワードのセットである。
【００４８】
命令には、各オペランドおよび／または各結果用に、この動作フィールドの位置に関する情報が含まれるが、この位置は、異なる基本プロセッサのメモリにわたって分配された、Ｎ次元タイプ（信号または画像またはボリュームまたは、．．．）のテーブルの一意のデータ構造内の位置として定義され、Ｎは、１以上の整数である。以下では、データ構造は、Ｎ次元タイプのテーブルのこの一意のデータ構造を指す。
【００４９】
動作フィールドの位置は、各基本プロセッサが、オペランドにおいて自身に関連するメモリワードを自身のメモリで読み出し、かつ／または結果において自身に関連するメモリワードを自身のメモリに書き込まなければならないアドレスを、計算できるようにする。
【００５０】
現代のＳＩＭＤにおける典型的な命令は、全てのＰＥまたはそれらのいくつかに、いくつかのオペランドに関して同じ演算を全てが実行し、かつ結果を１つまたは複数の位置に記憶することを要求する。
【００５１】
再び図２の例をとると、第１の演算の第１のステップは、上端部が座標ｘ＝７、ｙ＝３を有し、かつ底端部が座標ｘ＝７、ｙ＝１８を有する１６×１垂直セグメントの読み出しを必要とする。オペランドＩ（ｘ−１、ｙ−１）の動作フィールドは、座標（ｘ＝７、ｙ＝３）、（ｘ＝７、ｙ＝４）、（ｘ＝７、ｙ＝５）、．．．、（ｘ＝７、ｙ＝１８）を有する画素から構成される。図に示すように、ＰＥ３〜１５に対して読み出される画素はアドレス７に記憶され、一方で、ＰＥ０〜２に対して読み出される画素は、アドレス７１に記憶されている。
【００５２】
従来のＳＩＭＤコンピュータでは、命令は、各オペランドおよび各結果に対して、異なるＰＥがオペランドを読み出すかまたは結果を記憶するアドレスを定義する。したがって、従来のＳＩＭＤは、単に、同一アドレス指定ゾーンに対応する動作フィールドを考慮する方法を知っているだけである。例えば、従来のＳＩＭＤでは、上端部が座標ｘ＝７、ｙ＝０を有し、かつ底端部が座標ｘ＝７、ｙ＝１５を有する動作フィールドを考慮することが可能である（なぜなら、これらの画素の全てがアドレス７に記憶されているから）か、または上端部が座標ｘ＝７、ｙ＝１６を有し、かつ底端部が座標ｘ＝７、ｙ＝３１を有する動作フィールドを考慮することが可能である（なぜなら、これらの画素の全てがアドレス７１に記憶されているから）が、しかし上端部が座標ｘ＝７、ｙ＝３を有し、かつ底端部が座標ｘ＝７、ｙ＝１８を有する動作フィールドを考慮することは可能ではない（なぜなら、ある画素がアドレス７に記憶され、他の画素がアドレス７１に記憶されているからである）。換言すれば、従来のＳＩＭＤでは、動作フィールドが、同一でないアドレスのゾーンにまたがる場合には、動作フィールドを考慮することが不可能である。
【００５３】
本発明に従って設計された並列プロセッサによって、命令の様々なオペランドまたは結果が、同一アドレスのゾーンに必ずしも対応しない動作フィールドを考慮することが可能になる。
【００５４】
より正確には、本発明の主題は、基本プロセッサＰＥを含む並列プロセッサであるが、各ＰＥは、少なくとも１つの計算ユニットと、メモリワードを含む少なくとも１つのメモリと、を含み、所定の位置を自身の内に備えたトポロジに従って配置され、かつ異なるデータに対して同じ命令を同時に実行することができ、この命令は、少なくとも１つのオペランドの読み出しを含み、かつ／または少なくとも１つの結果の書き込みを含む。この並列プロセッサは、主として次のことを特徴とする。すなわち、命令が、それぞれがそれ自身のメモリにある、基本プロセッサの読み出しのセットおよび／または書き込みのセットを、動作フィールドにおける読み出しおよび／または書き込みとして定義し、動作フィールドが、基本プロセッサ当たり１メモリワードの割合におけるメモリワードのセットであり、このメモリワードが、基本プロセッサのメモリに位置し、オペランドの動作フィールドが、このオペランドを得るために、それぞれがそれ自身のメモリにある、基本プロセッサによって読み出されるメモリワードのセットであり、結果の動作フィールドが、この結果を記憶するために、それぞれがそれ自身のメモリにある、基本プロセッサによって書き込まれるメモリワードのセットであることと、命令が、各オペランドおよび／または各結果用に、この動作フィールドの位置に関連する情報を含むことと、動作フィールドの位置が、Ｎ次元タイプのテーブルの一意のデータ構造内の位置として定義され、Ｎが、１以上の整数であることと、このテーブルが、異なる基本プロセッサのメモリにわたって分配されることと、を特徴とする。
【００５５】
提案の並列プロセッサは次の原理を用いる。すなわち、結果が記憶されるデータ構造の各オペランドおよび各要素に対して、命令は、ＰＥがオペランドを読み出すかまたは結果を書き込まなければならないアドレスではなく、データ構造内のオペランドまたは結果の動作フィールドの位置を定義できるようにする情報を定義する。この情報および各ＰＥの位置に関連する値を用いて、計算手段は、各ＰＥが、それがオペランドを読み出すかまたは結果を書き込まなければならないアドレスを知ることができるようにする。
【００５６】
このようにして、各ＰＥが、それ自身のメモリにおいて直接読み出すかまたは書き込むアドレスは、計算によって得られ、この計算は、動作フィールドの位置、およびトポロジ内のＰＥの位置に従って実行される。
【００５７】
これらの動作フィールドの形状（水平もしくは垂直セグメント、正方形、長方形または平行六面体）は、ＰＥのトポロジをモデルに作られるので、従来のＳＩＭＤにおけるのと同じである。
【００５８】
他方では、動作フィールドの位置は、従来のＳＩＭＤにおけるよりもはるかに柔軟な方法で定義される。特に、かかる並列プロセッサによって、画像処理の例において言及し、かつ図２、３および４によって図示したものなどの動作フィールドを考慮することが可能になり、これは、たとえこれらの動作フィールドを構成するセルが、ＰＥに依存して異なるアドレスに位置しても、そのとおりである。
【００５９】
しかしながら、提案の並列プロセッサの利点は、さらに広く及ぶ。例として、画素がそのネイバーから計算されるアルゴリズムを用いる用途は全てが、それから利益を得ることができる。それは、信号処理、画像処理、画像圧縮、合成画像生成、および偏微分方程式を解くためのある技術にも及ぶ。典型的な例は、有限差分法を用いて３次元空間における偏微分方程式を解くことである。
【００６０】
これらの用途には二重の利益がある。
−  アルゴリズムのプログラミングが、単純化される。なぜなら、プログラマは、もはや、同一アドレスのゾーン間の境界の概念にとらわれる必要がないからである。
−  実行される命令がより少ないので、実行が加速される。
【００６１】
本発明の特徴によれば、並列プロセッサには、アドレスを計算する手段に接続された、前記情報の関数として動作フィールドの位置を計算する手段が含まれる。
【００６２】
動作フィールドの位置の関数として、各基本プロセッサ内でアドレスを計算する手段は、
各基本プロセッサのレベルに完全に局在化するか、または
各基本プロセッサのレベルに部分的に局在化し、かついくつかの基本プロセッサ間で部分的にグループ化することができる。
【００６３】
本発明による並列プロセッサには、場合により、前記情報の関数として動作フィールドの位置を計算する手段が含まれる。動作フィールドの位置を計算するこれらの手段は、
−  全てのＰＥ間で完全にグループ化するか、または
−  各基本プロセッサのレベルで完全に局在化するか、または
−  いくつかのＰＥ間で部分的にグループ化し、他の基本プロセッサのレベルで部分的に局在化することができる。
【００６４】
一般に、基本プロセッサは、Ｐ次元を有するトポロジに従って配置されるが、Ｐは１以上の整数であり、かつ／または処理されるデータは、Ｎ次元を有する空間における構造に属し、Ｎが、１以上の整数である。
【００６５】
本発明の特徴によれば、各次元に対して、前記次元によるｘ座標ｐの基本プロセッサに関連するデータ構造における要素のアドレスの計算は、フィールドの位置に関連する値、および基本プロセッサの位置に関連する値の組み合わせによって得られる。
【００６６】
本発明の一実施形態によれば、動作フィールドは、その座標によって定義される端部を有する。動作フィールドの位置は、例えば、座標が最小である端部の位置によって定義される。
【００６７】
本発明の特徴によれば、各次元に対して、前記次元に従ってｘ座標がｐである基本プロセッサに関連するデータ構造における要素のアドレスを、動作フィールドの位置の関数として計算する手段は、
Ａｄ＝Ｉｎｔ（（Ｗｍｉｎ＋Ｎｐ−１−ｐ）／Ｎｐ）
を計算する手段を含むが、Ｎｐは、前記次元における問題の基本プロセッサの数であり、Ｗｍｉｎは、前記位置の座標の関数として前記次元において定義される。
【００６８】
並列プロセッサは、例えばＳＩＭＤ型である。
【００６９】
本発明の他の特徴および利点は、非限定的な例として与えられた下記の詳細な説明を読み、添付の図面を参照することによって、明らかになろう。
【図面の簡単な説明】
【００７０】
【図１】既に説明したが、先行技術によるＳＩＭＤコンピュータの例における概略図である。
【図２】既に説明したが、リングとして構成された１６ＰＥを備えたＳＩＭＤコンピュータにおける画像の６４×６４画素の記憶を示す。
【図３】既に説明したが、リングとして構成された１６ＰＥを備えたＳＩＭＤコンピュータにおける画像の６４×６４画素の別の記憶を示す。
【図４ａ】既に説明したが、４×４トロイドとして構成された１６ＰＥを有するＳＩＭＤコンピュータにおける画像の６４×６４画素の記憶を示し、問題のＰＥを表す。
【図４ｂ】既に説明したが、４×４トロイドとして構成された１６ＰＥを有するＳＩＭＤコンピュータにおける画像の６４×６４画素の記憶を示し、ＰＥ内のアドレスを表す。
【図５】本発明による並列プロセッサの例における概略図である。
【図６ａ】１次元並列プロセッサおよび１次元データ構造本発明によるアドレス計算手段のハードウェア実施形態の例の概略図である。
【図６ｂ】１次元並列プロセッサおよび２次元データ構造本発明によるアドレス計算手段のハードウェア実施形態の例の概略図である。
【図６ｃ】１次元並列プロセッサおよび多次元データ構造本発明によるアドレス計算手段のハードウェア実施形態の例の概略図である。
【図６ｄ】２次元並列プロセッサおよび２次元データ構造本発明によるアドレス計算手段のハードウェア実施形態の例の概略図である。
【図６ｅ】２次元並列プロセッサおよび２次元データ構造本発明によるアドレス計算手段のハードウェア実施形態の例の概略図である。
【発明を実施するための形態】
【００７１】
全ての図において、同じ要素は、同じ参照符号によって示される。
【００７２】
本発明によれば、命令は、各ＰＥがオペランドを読み出すかまたは結果を書き込まなければならないアドレスではなく、処理されたデータ構造内の動作フィールドの位置に関する情報を定義する。この位置は、絶対値で、または前の位置に対する相対値で定義することができる。したがって、そこから各ＰＥに適したアドレスを引き出すために、ある数の計算ステップが必要である。
【００７３】
第１のステップは、動作フィールドの位置が命令によって絶対値として定義されていない場合に、実行されている命令から動作フィールドの位置を計算することを含む。この第１のステップの終わりにおいて、結果はＰＥから独立している。
【００７４】
第２のステップは、各ＰＥがオペランドを読み出すかまたは結果を書き込まなければならないアドレスを、動作フィールドの位置から計算することを含む。以下の例で分かるように、アドレスは、動作フィールドの位置に関連する値およびＰＥの位置に関連する値の加算または減算によって得られる。この第２のステップの終わりにおいて、結果はＰＥに依存する。
【００７５】
最適化が求められているかどうか（例えば、より正確に言えばワイヤの数、またはより正確に言えばゲートの数）に依存して、これらの計算は、最大限まで集中的に、したがって一度だけ実行していくつかのＰＥ間で共有するか、または反対に各ＰＥのレベルで最大限までローカルに実行するか、またはある共通計算をグループ化する任意の中間方法を実行することができる。多数の変形があるので、それらの全て説明することは不可能であり、説明は、少数の例に限定される。
【００７６】
したがって、図５に示す実装例は、動作フィールドの位置を計算手段５０によって集中的に計算することを含むことができ、一方で、各ＰＥは、この情報を用い、自身のメモリおよび／またはレジスタセットにおけるアドレスＡｄをこの情報から引き出すようにする。このアドレスは、各ＰＥのアドレス計算手段４１、４２、４３によって得られる。この原理の利点は、それが、各ＰＥにおいて実行される計算量ひいてはハードウェアの量を最小にするということである。
【００７７】
非局在化が極端に推し進められる場合には、別の実装例が、各ＰＥのレベルで全て、すなわち動作フィールドの位置および対応アドレス、を計算することを含み得る。この変形の欠点は、それが、各ＰＥにおいて実行される計算量ひいてはハードウェアの量を増加させるということである。しかしながら、それによって、全てのＰＥに送信される情報量ひいては回路におけるワイヤの数を低減することが可能になり、これは、場合によっては有利になり得る。
【００７８】
この反対に、各ＰＥにおいて実行される計算量ひいてはハードウェアの量を最小限まで低減することが、望ましくなり得る。したがって、別の実装例が、ＰＥのグループレベルで、またはたとえ集中的であっても、いくつかのＰＥに共通のある計算を相互化することを含み得る。この例は、第４の例示的な実施形態において見られる。
【００７９】
各ＰＥのアドレス計算手段４１、４２、４３は、ハードワイヤードハードウェア、またはより柔軟なハードウェア、例えばプログラム可能なプロセッサによって作成することができる。計算はまた、各ＰＥが間接レジスタを有するという条件で、ＰＥのＡＬＵによって純粋にソフトウェアで、したがって、いかなる追加のハードウェアも加えずに実行することができる。かかる実装例は、ハードウェアにおいてさらに経済的であり、用途によっては有利になり得る。
【００８０】
動作フィールドの位置、例えばフィールドの中心または前に定義された方向における端部、を定義する情報に関して、異なる選択が可能である。これらの選択の全てが忠実な翻訳に相当し、一方から他方への変化がわずかなので、この問題は、より詳細には説明しない。実際に、これらの選択は、動作フィールドの位置が、端部の線形結合によって得られた重心の位置によって定義され、端部の重みの合計（ｓｕｍ  ｏｆ  ｔｈｅ  ｓｉｇｎｉｆｉｃａｎｃｅｓ）が１に等しいという事実を共通に有する。例示的な実施形態を説明するために、動作フィールドの位置を定義するために選択される情報が、座標の全てが最小であるフィールドポイントである場合が選択された。換言すれば、このポイントから無限大への方向におけるフィールドの端部は、各座標において−∞に等しい。図２、３および４において、座標（７、３）を有するポイントを、第１の演算の第１のステップ用に用いるものとする。
【００８１】
本発明は、１次元、２次元、３次元または多次元トポロジを有する並列プロセッサに、かつこれらのトポロジのそれぞれにおいて、１次元（例えば、信号）、２次元（例えば、画像）、３次元（例えば、偏微分方程式を解くための３Ｄボリューム）もしくは多次元であるデータ構造に、かつまた並列プロセッサの各タイプにおいて各データ構造を記憶するための様々な方法に、適用することができる。
【００８２】
本発明はまた、異なるデータに対して同じ処理を実行する多数の基本プロセッサを用いる処理アーキテクチャに、このアーキテクチャがＳＩＭＤカテゴリに属さない場合を含めて、適用することができる。例えば、制御構造が、シーケンサでもプログラム可能でない場合、またはプログラミングが、命令よりも高いレベルで実行される場合である。
【００８３】
ここで、実施形態のいくつかの例を詳細に説明する。
【００８４】
実施形態の第１の例は、例えばリング構造を備えた１次元並列プロセッサ、および１次元データ構造、例えば信号の場合に関する。
【００８５】
ユーザが、次のように、自分のデータを並列プロセッサに記憶する場合を考える。信号の要素ｘは、アドレスＡｄにおいてＰＥ  Ｎ°ｐに記憶され、ここで、
ｐ＝ｘ  Ｍｏｄ  Ｎｐ
Ａｄ＝Ｉｎｔ（ｘ／Ｎｐ）
Ｎｐは、ＰＥの数である。
【００８６】
この場合に、ＰＥセットは、幅Ｎｐのセグメントと見なされ、動作フィールドは、幅Ｎｐのセグメントである。それは、Ｎｐ要素を含む。
【００８７】
フィールドの位置を定義するために用いられる情報が、フィールドの左端部のｘ座標である場合、すなわちｘ座標が最小である場合を考える。Ｘｍｉｎをこのｘ座標とする。したがって、動作フィールドは、ＸｍｉｎからＸｍｉｎ＋Ｎｐ−１まで及ぶ。各ＰＥは、これらの要素の１つのみに関係する。
【００８８】
フィールド内のＰＥ  Ｎ°ｐに関連する要素のアドレスの計算を可能にする式は、次のとおりである。
Ａｄ＝Ｉｎｔ（（Ｘｍｉｎ＋Ｎｐ−１−ｐ）／Ｎｐ）
【００８９】
この式は、純粋なハードウェアから純粋なソフトウェアに及ぶ多数の実装例を生み出すことができる。
【００９０】
しかしながら、Ｎｐが２の累乗である場合における特に単純なハードウェア実装について言及する。実際に、この場合、ＬＮｐがＮｐの底２の対数を示す場合には、ＸｍｉｎからＡｄを計算する方法は、次のとおりである。
【００９１】
Ｘｍｉｎおよび（Ｎｐ−１−ｐ）を加算する。さらに、各ＰＥに対して、（Ｎｐ−１−ｐ）が、ｐの２の補数（これは、ｐの全てのビットを反転させることによって得られる）に等しい定数であること、およびこの定数が、ＰＥ  Ｎ°ｐにおけるメモリに保持できることが観察される。
【００９２】
結果の最後のＬＮｐビットを削除する。
【００９３】
合計では、ＰＥごとに１回の加算がある。
【００９４】
この実装例は、Ｎｐ＝１６、ＬＮｐ＝４に対して図６ａに示され、Ｘｍｉｎは、１２ビットである。それは、ＰＥがオペランドを読み出すかまたはアドレスを書き込まなければならないアドレスは、フィールドの位置に関連する値およびＰＥの位置に関連する値の加算（または減算）によって得られるという事実を特徴とする。
【００９５】
この特に単純なタイプの実装例は、説明される例示的な実施形態の全てにわたって変換することができる。より一般的には、それは、１次元、２次元、３次元または多次元トポロジを用いて構成された任意のタイプの並列プロセッサに関して、かつこれらのトポロジのそれぞれにおいて１次元（例えば、信号）、２次元（例えば、画像）、３次元（例えば、３Ｄボリューム）、または多次元タイプのデータ構造に関して、変換することができる。実際には、並列プロセッサのタイプ、データ構造および選択された記憶に従って計算を手直しし、次に、それに応じて実装を適合させることで十分である。
【００９６】
第２の例示的な実施形態は、例えばリング構造を備えた１次元並列プロセッサ、および２次元データ構造、例えば画像の場合に関する。
【００９７】
１次元データ構造のために用いられる計算は、それを２次元データ構造において変換することによって再び用いることができる。式は、これから導き出され、用途は、それに応じて適合される。
【００９８】
また、１次元データ構造用に上で分析した場合に戻ることによって、２次元データ構造を処理できるようにする方法を用いることが可能である。
【００９９】
ＮｐをＰＥの数とし、Ｌｘを処理される画像の幅、すなわち各行における画素数とし、Ｌｙをその高さ、すなわち各列における画素数とする。より正確には、それは、ＰＥの数と、各行および各列における画素数との上限の問題である。実際には、ほとんどの場合、ハードウェアを単純化する目的で、処理される画像をより大きな画像の内部に配置すること、ひいては、処理される画像の寸法より大きなＬｘおよびＬｙの値を選択することが好ましい。一方では、異なるサイズのいくつかの画像を処理しなければならない場合には、それらの中で最も大きなものの処理を可能にする単一の選択を行うことが好ましい場合がある。他方では、実装を単純化するために、それがハードウェア実装である場合には、２の累乗がしばしば選択される。
【０１００】
１次元データ構造に戻る１つの方法（換言すれば、画素をＰＥに記憶する方法）は、各画素（ｘ、ｙ）に対して、
ｗ＝ｘ＋Ｌｘ＊ｙ
を書き込むことである。
【０１０１】
図３に示すこのタイプの記憶は、ＰＥセットをＰＥの水平ブロックと見なすことになり、各ＰＥは、１列またはいくつかの列に関与する。それは、前に分析し図２に示した記憶と異なるが、図２の記憶は、ＰＥセットをＰＥの垂直ブロックと見なすことになり、各ＰＥは、１行またはいくつかの行に関与する。この場合には、各画素（ｘ、ｙ）に対して
ｗ＝ｙ＋Ｌｙ＊ｘ
を書き込むことが必要である。
【０１０２】
これらの２つの式を比較すれば、１つの記憶システムからもう一方の記憶システムに変わる方法を容易に理解することができる。さらに、１つの記憶システムから別の記憶システムに変わる一般的な方法に以下で言及する。差し当たり、説明は、図３で用いられ、かつ変換、
ｗ＝ｘ＋Ｌｘ＊ｙ
によって特徴づけられる第１の記憶システムに制限される。
【０１０３】
この変換によって、第１の実施形態に対してなされたように、画素を並列プロセッサに記憶することが可能になる。信号の要素ｗは、アドレスＡｄにおいてＰＥ  Ｎ°ｐに記憶され、ここで、
ｐ＝ｗ  Ｍｏｄ  Ｎｐ
Ａｄ＝Ｉｎｔ（ｗ／Ｎｐ）
である。
【０１０４】
この場合に、動作フィールドは、幅Ｎｐの水平セグメントである。
【０１０５】
例として、フィールドの位置を定義するために用いられる情報が、座標が最小であるフィールド端部の位置である場合を考える。
【０１０６】
Ｘｍｉｎ、Ｙｍｉｎをこのポイントの座標とする。
【０１０７】
Ｗｍｉｎ＝Ｘｍｉｎ＋Ｌｘ＊Ｙｍｉｎ
と仮定する。
【０１０８】
ＰＥ  Ｎ°ｐが、フィールド内で自身が関係する画素のアドレスを計算できるようにする式は、次のとおりである。
Ａｄ＝Ｉｎｔ（（Ｗｍｉｎ＋Ｎｐ−１−ｐ）／Ｎｐ）
【０１０９】
これは、第１の実施形態におけるのと同じ式である。単に、ＷｍｉｎがＸｍｉｎに取って代わるだけである。したがって、１次元構造用に使用可能な任意の実装、および特に、説明した実装を、２次元データ構造に変換する単純な方法がある。ＮｐおよびＬｘが２の累乗である場合には、ＰＥ当たり１つの単一の加算があるだけである。ＬＮｐおよびＬＬｘが、それらのそれぞれの対数を示すようにする。この実施形態をさらに単純化するために、この加算をＷｍｉｎに対して実行するのではなく、実際には、この加算が、Ｘｍｉｎだけ、すなわちＬｘビットだけに影響することに注目する。他の演算は、ビットの連結であり、加算よりはるかに単純である。このように単純化すると、Ｘｍｉｎ、ＹｍｉｎからＡｄを計算する方法は、次のとおりである。
Ｘｍｉｎおよび（Ｎｐ−１−ｐ）を加算する。
結果の最後のＬＮｐビットを削除する。
ＬＬｘ−ＬＮｐビットで表された前述の量を最下位位置において、およびＹｍｉｎを最上位位置において連結する。
【０１１０】
この実装例は、Ｎｐ＝１６、ＬＮｐ＝４、６ビットのＸｍｉｎおよびＹｍｉｎに対して、図６ｂに示す。
【０１１１】
第３の例示的な実施形態は、（例えばリング構造を備えた）１次元並列プロセッサ、および２を超える次元のデータ構造の場合である。
【０１１２】
最初に、３次元データ構造（例えば３Ｄボリューム）の場合を考える。
【０１１３】
Ｌｘを処理されるボリュームの幅とし、Ｌｙをその深さとし、Ｌｚをその高さとするか、またはより正確には、前に示した理由で、これらの３つの量の上限とする。
【０１１４】
１次元データ構造に戻る１つの方法は（換言すれば、ＰＥに画素を記憶する方法）は、各画素（ｘ、ｙ、ｚ）に対して、
ｗ＝ｘ＋Ｌｘ＊（ｙ＋Ｌｙ＊ｚ）
を書き込むことである。
【０１１５】
記憶システムｗ＝ｘ＋Ｌｘ＊（ｙ＋Ｌｙ＊ｚ）は、以下で検討する。
【０１１６】
この推論は、
ｗ＝ｘ＋Ｌｘ＊（ｚ＋Ｌｚ＊ｙ））
ｗ＝ｙ＋Ｌｙ＊（ｘ＋Ｌｘ＊ｚ））
ｗ＝ｙ＋Ｌｙ＊（ｚ＋Ｌｚ＊ｘ））
ｗ＝ｚ＋Ｌｚ＊（ｘ＋Ｌｘ＊ｙ））
ｗ＝ｚ＋Ｌｚ＊（ｙ＋Ｌｙ＊ｘ））
などの他の記憶システムに容易に変換することができる。
【０１１７】
この変換ゆえに、画素は、それらが第１の実施形態に対してあったように、並列プロセッサに記憶することができる。信号の要素ｗは、アドレスＡｄにおいてＰＥ  Ｎ°ｐに記憶され、ここで、
ｐ＝ｗ  Ｍｏｄ  Ｎｐ
Ａｄ＝Ｉｎｔ（ｗ／Ｎｐ）
である。
【０１１８】
この場合に、ＰＥセットは、幅Ｎｐの水平セグメントと見なされ、動作フィールドは、幅Ｎｐの水平セグメントである。
【０１１９】
例として、動作フィールドの位置を定義するために用いられる情報が、座標が最小であるフィールド端部の位置である場合を考える。Ｘｍｉｎ、Ｙｍｉｎ、Ｚｍｉｎをこのポイントの座標とする。
【０１２０】
Ｗｍｉｎ＝Ｘｍｉｎ＋Ｌｘ＊（Ｙｍｉｎ＋Ｌｙ＊Ｚｍｉｎ）
と仮定する。
【０１２１】
ＰＥ  Ｎ°ｐが、フィールド内で自身に関係する画素のアドレスを計算できるようにする式は、次のとおりである。
Ａｄ＝Ｉｎｔ（（Ｗｍｉｎ＋Ｎｐ−１−ｐ）／Ｎｐ）
【０１２２】
これは、第１の実施形態におけるのと同じ式である。単に、ＷｍｉｎがＸｍｉｎに取って代わるだけである。したがって、１次元データ構造用に使用可能な任意の実装、および特に、説明した実装を、３次元データ構造に変換する単純な方法がある。Ｎｐ、ＬｘおよびＬｙが２の累乗である場合には、ＰＥごとに単一の加算があるだけである。ＬＮｐ、ＬＬｘおよびＬＬｙが、それらのそれぞれの対数を示す。この実施形態をさらに単純化するために、この加算をＷｍｉｎに対して実行するのではなく、実際には、この加算が、Ｘｍｉｎだけ、すなわちＬｘビットだけに関することに注目する。他の演算は、ビットの連結であり、加算よりはるかに単純である。このように単純化すれば、Ｘｍｉｎ、Ｙｍｉｎ、ＺｍｉｎからＡｄを計算する方法は、次のとおりである。
Ｘｍｉｎおよび（Ｎｐ−１−ｐ）を加算する。
結果の最後のＬＮｐビットを削除する。
ＬＬｘ−ＬＮｐビットで表された前述の量を最下位位置において、Ｌｙビットで表されたＹｍｉｎを中位位置において、およびＬｚビットで表されたＺｍｉｎを最上位位置において連結する。
【０１２３】
同じ原理は、何であれ任意の次元のデータ構造に適用することができる。したがって、４次元に関し、
各画素（ｘ、ｙ、ｚ、ｔ）に対して、
ｗ＝ｘ＋Ｌｘ＊（ｙ＋Ｌｙ＊（ｚ＋Ｌｚ＊ｔ））
を書き込み、
Ｘｍｉｎ、Ｙｍｉｎ、Ｚｍｉｎ、Ｔｍｉｎを用いて、動作フィールドの位置を定義し、
Ｗｍｉｎ＝Ｘｍｉｎ＋Ｌｘ＊（Ｙｍｉｎ＋Ｌｙ＊（Ｚｍｉｎ＋Ｌｚ＊Ｔｍｉｎ））を仮定し、
最後に、各ＰＥ用に、
Ａｄ＝Ｉｎｔ（（Ｗｍｉｎ＋Ｎｐ−１−ｐ）／Ｎｐ
を計算することで十分である。
【０１２４】
実施形態の第４の例は、例えばトロイド構造を備えた２次元並列プロセッサ、および２次元データ構造、例えば画像の場合である。
【０１２５】
Ｎｘをｘ軸におけるＰＥの数とし、Ｎｙをｙ軸におけるＰＥの数とし、したがってＮｘ＊ＮｙをＰＥの合計数とする。Ｌｘを処理される画像の幅とし、かつＬｙをその高さとするか、または前に示したように、これらの２つの量の上限とする。好ましくは、ＬｘおよびＬｙは、ＮｘおよびＮｙの倍数からそれぞれ選択される。（ｐｘ、ｐｙ）は、ＰＥのトロイドにおいて座標（ｐｘ、ｐｙ）を有するＰＥを示す。
【０１２６】
例として、ユーザが自分のデータを並列プロセッサに以下のように記憶した場合を考える。画像の画素（ｘ、ｙ）は、アドレスＡｄにおいてＰＥ（ｐｘ、ｐｙ）に記憶され、ここで、
ｐｘ＝ｘ  Ｍｏｄ  Ｎｘ
ｐｙ＝ｙ  Ｍｏｄ  Ｎｙ
Ａｄｘ＝Ｉｎｔ（ｘ／Ｎｘ）
Ａｄｙ＝Ｉｎｔ（ｙ／Ｎｙ）
Ａｄ＝Ａｄｘ＋（Ｌｘ／Ｎｘ）＊Ａｄｙ
である。
【０１２７】
図４ａおよび４ｂに用いられる記憶システムの場合には、ＰＥセットは、幅Ｎｘおよび高さＮｙの矩形と見なされ、動作フィールドは、幅Ｎｘおよび高さＮｙの矩形である。
【０１２８】
この記憶システムが、１次元データ構造用に用いられる記憶システムをモデルに作られていることが観察される。実際に、それは、空間の２つの方向のそれぞれにこの記憶システムを再現する。したがって、処理装置は、正確に同じだが、空間の２つの方向のそれぞれに適用されなければならない。
【０１２９】
例として、次の場合を再び考える。すなわち、フィールドの位置を定義するために用いられる情報が、座標が最小であるフィールドのコーナーである、すなわちポイントから無限大への方向におけるフィールドの端部が、各座標において−∞に等しい場合である。Ｘｍｉｎ、Ｙｍｉｎをこのポイントの座標とする。
【０１３０】
ＰＥ（ｐｘ、ｐｙ）が、フィールド内で自身に関係する要素のアドレスを計算できるようにする式は、次のとおりである。
Ａｄｘ＝Ｉｎｔ（（Ｘｍｉｎ＋Ｎｘ−１−ｐｘ）／Ｎｘ）
Ａｄｙ＝Ｉｎｔ（（Ｙｍｉｎ＋Ｎｙ−１−ｐｙ）／Ｎｙ）
Ａｄ＝Ａｄｘ＋（Ｌｘ／Ｎｘ）＊Ａｄｙ
【０１３１】
第１の実施形態に現れ、かつ提案された装置を特徴とする式は、繰り返して２度見出される。１度はｘ軸上であり、１度はｙ軸上である。前述のように、これは、純粋なハードウェアから純粋なソフトウェアに及ぶ、多数の実装を生み出すことができる。
【０１３２】
しかしながら、前述の実施形態に対して行ったように、Ｎｘ、Ｎｙ、ＬｘおよびＬｙが２の累乗である場合における特に単純なハードウェア実装について言及する。ＬＮｘが、Ｎｘの底２の対数を示し、ＬＮｙが、Ｎｙの底２の対数を示し、ＬＬｘが、Ｌｘの底２の対数を示し、ＬＬｙが、Ｌｙの底２の対数を示す場合には、Ｘｍｉｎ、ＹｍｉｎからＡｄを計算する方法は、次のとおりである。
【０１３３】
Ｘｍｉｎおよび（Ｎｘ−１−ｐｘ）を加算する。Ｘｍｉｎ、Ｎｘおよびｐｘが、ＰＥの列に共通の値であることが注目される。したがって、この計算は、ＰＥの列ごとに一度だけ実行すればよい。さらに、量（Ｎｘ−１−ｐｘ）は、ＰＥの列のための定数である。それは、ＰＥの１つの列のために単一のメモリに保持することができる。
【０１３４】
結果の最後のＬＮｘビットを削除する→ＬＬｘ−ＬＮｘビットにおけるＡｄｘ。
【０１３５】
Ｙｍｉｎおよび（Ｎｙ−１−ｐｙ）を加算する。Ｙｍｉｎ、Ｎｙおよびｐｙが、ＰＥの行に共通の値であることが注目される。したがって、この計算は、ＰＥの行ごとに一度だけ実行すればよい。さらに、量（Ｎｙ−１−ｐｙ）は、ＰＥの行のための定数である。それは、ＰＥの１つの行のために単一のメモリに保持することができる。
【０１３６】
結果の最後のＬＮｙビットを削除する→ＬＬｙ−ＬＮｙビットにおけるＡｄｙ。
【０１３７】
Ａｄ＝Ａｄｘ＋（Ｌｘ／Ｎｘ）＊Ａｄｙであり、これは、ＬＬｘ−ＬＮｘビットにわたって表されるＡｄｘを最下位位置において、およびＬＬｙ−ＬＮｙビットにわたって表されるＡｄｙを最上位位置において連結することになる。
【０１３８】
前のタイプの実施形態の変換が可能だったことが確認される。これからは、ＰＥの行ごとの単一の加算およびＰＥの列ごとの単一の加算がある。さらに、これらの加算は、ビットにほとんど影響しない。したがって、前の実施形態において必要な実装よりさらに経済的な実装がある。この実装例は、Ｎｘ＝４、Ｎｙ＝４、ＬＮｘ＝２、ＬＮｙ＝２、６ビットにわたるＸｍｉｎおよびＹｍｉｎに対して、図６ｃに示す。
【０１３９】
例として選択された４つの実施形態を連続的に分析した。
−  １次元並列プロセッサおよび１次元データ構造
−  １次元並列プロセッサおよび２次元データ構造プロセッサ
−  １次元並列プロセッサおよび多次元データ構造
−  ２次元並列プロセッサおよび２次元データ構造。
【０１４０】
しかしながら、提案された原理は、１次元、２次元、３次元または多次元トポロジで構成された並列プロセッサ、およびこれらのトポロジのそれぞれにおける１次元、２次元、３次元または多次元データ構造に適用することができる。
【０１４１】
次の一般化を行うことができる。ｎをデータ構造の次元とし、ｐを並列プロセッサのトポロジの次元とする。
【０１４２】
ｎ＝ｐの場合には、この原理は、まさにｎ＝２（第４の実施形態）に対して見られるように、ｐ方向のそれぞれにおいて適用される。
【０１４３】
ｎ>ｐの場合には、第２および第３の実施形態の場合に見られるように、構造の次元は、２つの軸（ｐ次元の構造が得られるまで、次に２つの他の軸、次に２つの他の軸、．．．、）を選択すること、および下記のタイプの式を適用することによりこれらの２つの軸を単一の軸に変えること、によって低減される。
ｗ＝ｘ＋Ｌｘ＊ｙ
【０１４４】
ｎ<ｐの場合には、構造の次元は、１つの軸（ｐ次元の構造が得られるまで、次に別の軸、次に別の軸、．．．、）を選択することによって増加され、この軸は、それを２つに分けるためにスライスに分解される。したがって、１つのｘ座標から２つの座標ｗ１およびｗ２に変えるために、スライスＬｘの幅が選択され、次のタイプの式が適用される。
ｗ１＝ｘ  Ｍｏｄ  Ｌｘ
ｗ２＝Ｉｎｔ（ｘ／Ｌｘ）
【０１４５】
これまで、軸（例えばｘ軸）における２つの連続要素が、２つの異なるＰＥによって保持および処理される記憶システムを用いる実施形態を分析してきた。典型的には、１次元の場合（第１の実施形態）において、例として、ユーザが信号のｘ要素をアドレスＡｄにおいてＰＥに記憶した場合を考えたが、ここで、
ｐ＝ｘ  Ｍｏｄ  Ｎｐ
Ａｄ＝Ｉｎｔ（ｘ／Ｎｐ）
である。
【０１４６】
同様に、２次元の場合（第２の実施形態）において、例として、ユーザが画素（ｘ、ｙ）をアドレスＡｄにおいてＰＥ  Ｎ°ｐに記憶した場合を考えたが、ここで、
ｗ＝ｘ＋Ｌｘ＊ｙ
ｐ＝ｗ  Ｍｏｄ  Ｎｐ
Ａｄ＝Ｉｎｔ（ｗ／Ｎｐ）
である。
【０１４７】
これらは、単に例である。この方法は、他の多くの記憶モードに適用することができる。
【０１４８】
したがって、１次元の場合にとどまるために、ユーザは、サイズＬｘを定義し、信号のｘ要素をアドレスＡｄにおいてＰＥ  Ｎ°ｐに記憶しようと望んでもよく、ここで、
ｘ１＝ｘ  Ｍｏｄ  Ｌｘ
ｘ２＝Ｉｎｔ（ｘ／Ｌｘ）
ｐ＝ｘ２  Ｍｏｄ  Ｎｐ
Ａｄ＝ｘ１＋Ｌｘ＊Ｉｎｔ（ｘ２／Ｎｐ）
である。
【０１４９】
これは、ｘ軸におけるＬｘ連続要素のセグメントが同じＰＥによって保持および処理され、一方で、次のＰＥが次のセグメントを保持および処理する記憶モードである。
【０１５０】
ＰＥ  Ｎ°ｐが、フィールド内で自身に関係する要素のアドレスをＸｍｉｎから計算できるようにする式は、次のとおりである。
Ｘｍｉｎ１＝Ｘｍｉｎ  Ｍｏｄ  Ｌｘ
Ｘｍｉｎ２＝Ｉｎｔ（Ｘｍｉｎ／Ｌｘ）
Ａｄ＝Ｘｍｉｎ１＋Ｌｘ＊Ｉｎｔ（（Ｘｍｉｎ２＋Ｎｐ−１−ｐ）／Ｎｐ）
【０１５１】
見て分かるように、これは、Ｘｍｉｎ１には関わらずに、Ｘｍｉｎ２に方法を適用することになる。
【０１５２】
ＬｘおよびＮｐが２の累乗であり、かつ特に単純なハードウェア実装が可能な場合を考える。ＬＮｐおよびＬＬｘは、それらのそれぞれの対数を示す。上記の式は、以下のように解釈することができる。
Ｘｍｉｎを２つの部分、すなわちＸｍｉｎ１を構成するＬＬｘビットにわたる最下位位置およびＸｍｉｎ２を構成する最上位位置、に分割する。
第１の実施形態において提案された手順をＸｍｉｎ２に適用する。結果は、Ｉｎｔ（Ｘｍｉｎ２＋Ｎｐ−１−ｐ）／Ｎｐ）である。
Ｌｘビットにわたる最下位位置におけるＸｍｉｎ１、および最上位位置における手順の結果を連結する。
【０１５３】
換言すれば、ＬｘおよびＮｐが２の累乗である場合には、
ＸｍｉｎのＬＬｘ最下位ビットを取っておくことと、
Ｘｍｉｎの他のビットに手順を適用することと、
最下位位置において、取っておかれたＬＬｘビットを手順の結果と連結することと、
が必要である。
【０１５４】
この拡張は、前の段落で言及した拡張からは完全に独立している。それは、前の段落の拡張と結合することができる。したがって、それは、並列プロセッサのトポロジおよびデータ構造の両方に対して、多次元の場合に当てはまる。それを次元のそれぞれに適用することで十分である。したがって、この方法は、ｘ軸におけるサイズＬｘ、ｙ軸におけるＬｙ、．．．の平行六面体が、同じＰＥによって保持および処理され、一方で、（並列プロセッサトポロジ用の）隣接するＰＥが、（データ構造のトポロジ用の）隣接する平行六面体を保持および処理する任意の記憶モードに当てはまる。
【０１５５】
他の記憶システムに対して一般化を行うことができる。それは、各方向におけるデータ構造のサイズ（Ｌｘ、Ｌｙ、Ｌｚ、．．．）およびプロセッサの数（Ｎｘ、Ｎｙ、Ｎｚ、．．．）が２の累乗である場合を仮定することによって、多次元の場合で示される。２の累乗を選択するという事実によって、実行される演算を２進表現で説明することが可能になり、これが最も単純な場合であるが、しかし何であれ、Ｌｘ、Ｌｙ、Ｌｚ、．．．、Ｎｘ、Ｎｙ、Ｎｚ、．．．の任意の値のための一般化は、前の例で言及したように、２進表現で記載した演算を、乗算、除算、モジュロ、および整数部分を用いる数式と置き換えることによって可能になる。データ構造を並列プロセッサに記憶し、次に、この記憶システムに方法を適用するために、以下のように進むことが可能である。
【０１５６】
フィールドの位置の定義するために用いられるポイントの様々な座標をＬＬｘ＋ＬＬｙ＋ＬＬｚ＋．．．ビットの単一ワードに連結する。これは、前にｗと呼ばれたものを形成することになる。
【０１５７】
ｗのビットの順序を変更する（可能な並べ替えと同数の可能な記憶システムがある）。ｗ’を、このようにして得られたワードとする。
【０１５８】
ｗ’を、サイズＬＬｘ、ＬＬｙ、ＬＬｚ、．．．ビットのワードに分割する。ｗｘ’、ｗｙ’、ｗｚ’、．．．を、このようにして得られたワードとする。
【０１５９】
並列プロセッサの次元のそれぞれにおいて方法を適用する。すなわち、
−  （Ｎｘ−１−ｐｘ）をｗｘ’に加算する、
−  結果の最後のＬＮｘビットを削除する。Ａｄｘ’が得られる、
−  （Ｎｙ−１−ｐｙ）をｗｙ’に加算する、
−  結果の最後のＬＮｙビットを削除する。Ａｄｙ’が得られる、
−  並列プロセッサの各方向において同様である。
【０１６０】
前の並べ替えには必ずしも関係しない並べ替えに従って、Ａｄｘ’、Ａｄｙ’、Ａｄｚ’、．．．のビットの順序を再び変更する。このようにして、並列プロセッサの方向のそれぞれにおける記憶アドレスＡｄｘ、Ａｄｙ、Ａｄｚが得られる。
【０１６１】
各ＰＥ内のフィールドに関係するアドレスを表す単一ワードＡｄにおけるこれらのアドレスを連結する。
【０１６２】
これを例示するために、図２が示す例を再び用いる。この例が、リング構造を有する１６ＰＥの１次元並列プロセッサに関連すること、データ構造が、サイズＬｘ＝６４およびＬｙ＝６４の画像であること、および画像の画素が、行に記憶されていることが思い出される。したがって、この場合は、次のとおりである。
Ｎｐ＝１６→ＬＮｐ＝４
Ｌｘ＝６４→ＬＬｘ＝６
Ｌｙ＝６４→ＬＬｙ＝６
【０１６３】
Ｘｍｉｎ、ＹｍｉｎからＡｄへ変わる演算は、次のとおりである。
【０１６４】
Ｘｍｉｎ、Ｙｍｉｎを６＋６＝１２ビットの単一ワードに連結する。ｗを、このようにして得られたワードとする。
【０１６５】
ｗの６つの最下位ビットおよび６つの最上位ビットを交換する。ｗ’を、このように得られたワードとする。
【０１６６】
１次元並列プロセッサの場合において方法を適用する。すなわち、
−  （１６−１−ｐ）をｗ’に加算する、
−  結果の最後の４ビットを削除する。Ａｄ’が得られる、
−  Ａｄ’の２つの最下位ビットおよび６つの最上位ビットを交換する。このようにして得られたワードが、アドレスＡｄである。
【０１６７】
これは、例示するのが望ましい一般化の文脈内に入る。この実装例は、Ｎｘ＝４、Ｎｙ＝４、ＬＮｘ＝２、ＬＮｙ＝２、６ビットのＸｍｉｎおよびＹｍｉｎに対して、６ｄに示す。これは、記憶モードの修正を伴う６ｂの変形実施形態である。
【０１６８】
図６ｄは、装置を少しも修正せずに、ワイヤを減少させることによって、読みやすくできることが観察される。図６ｅは、このようにして得られる。
【０１６９】
他の多くの記憶モードが可能である。例えば、最も単純な変形は、式における符号を変更することか、またはＰＥの順序を変更することを含む。それら全てに言及することは不可能である。
【図１】
0005608932.tif 000002
【図２】
0005608932.tif 000003
【図３】
0005608932.tif 000004
【図４ａ】
0005608932.tif 000005
【図４ｂ】
0005608932.tif 000006
【図５】
0005608932.tif 000007
【図６ａ】
0005608932.tif 000008
【図６ｂ】
0005608932.tif 000009
【図６ｃ】
0005608932.tif 000010
【図６ｄ】
0005608932.tif 000011
【図６ｅ】
0005608932.tif 000012