(57)【特許請求の範囲】
【請求項１】
複数（Ｍ個）のＳＩＭＤ動作するプロセッサエレメント（以下、「ＰＥ」という）を含むＰＥブロックを少なくとも三つ有するＰＥブロックアレイを備え、
少なくとも一つのＰＥブロックは、前記一つのＰＥブロックとは異なる少なくとも一つの他のＰＥブロックと、１本が所定ビットの、ＰＥブロック内のＰＥの個数と同数であるＭ本の第１の信号線で結ばれるとともに、前記一つのＰＥブロック及び前記他のＰＥブロックとは異なる少なくとも一つのさらに別のＰＥブロックと１本が所定ビットのＭ本の第２の信号線で結ばれ、
前記一つのＰＥブロックに含まれる前記ＰＥが、
前記Ｍ本の第１の信号線と前記Ｍ本の第２の信号線の中から１本の信号線を選択するセレクタ回路を備える、ことを特徴とするプロセッサアレイシステム。
【請求項２】
前記セレクタ回路が、
前記Ｍ本の第１の信号線から一本の信号線を選択する第１のセレクタ手段と、
前記Ｍ本の前記第２の信号線から一本の信号線を選択する第２のセレクタ手段と、
前記第１のセレクタ手段で選択された前記１本の信号線と、前記第２のセレクタ手段で選択された前記１本の信号線から、一本の信号線を選択する第３のセレクタ手段と、
を備える、ことを特徴とする請求項１記載のプロセッサアレイシステム。
【請求項３】
複数の前記ＰＥブロックは、一のＰＥブロックを一つのノードとする一次元結合又はリング結合の形態で接続され、
前記ＰＥブロックは、前記ＰＥブロックの一側で隣接するＰＥブロックと相互に前記Ｍ本の第１の信号線によって結ばれるとともに、前記ＰＥブロックの他側で隣接するＰＥブロックと相互に前記Ｍ本の第２の信号線によって結ばれる、ことを特徴とする請求項１記載のプロセッサアレイシステム。
【請求項４】
Ｎ個（ただし、Ｎは１より大きい自然数）の前記ＰＥに関して、
距離がＭ（ただし、Ｍは１より大きくＮより小さい自然数であり、Ｎの約数）のＰＥ同士を結合するＰＥ間での第１の転送方向及び第２の転送方向へのそれぞれの転送路を備え、
Ｍ個の隣接するＰＥが一個のＰＥブロックを構成し、前記ＰＥブロック内のＭ個のＰＥによる前記第１の転送方向への転送路が、前記Ｍ本の第１の信号線を構成し、
前記ＰＥブロック内の全Ｍ個のＰＥによる前記第２の転送方向への転送路が、前記Ｍ本の第２の信号線を構成する、ことを特徴とする請求項１記載のプロセッサアレイシステム。
【請求項５】
Ｎ個（ただし、Ｎは１より大きい自然数）の前記ＰＥが、一つのＰＥを一つのノードとする一次元結合又はリング結合の形態で接続され、
隣接ＰＥ間の結合線のほかに、さらに距離がＭ（ただし、Ｍは１より大きくＮより小さい自然数であり、Ｎの約数）のＰＥ同士を結合するＰＥ間での前記第１の転送方向及び前記第２の転送方向へのそれぞれの転送路を備え、
Ｍ個の隣接するＰＥが一つのＰＥブロックを構成し、
前記ＰＥブロック内のＭ個のＰＥによる第１の転送方向への転送路が前記Ｍ本の第１の信号線を構成し、
前記ＰＥブロック内のＭ個のＰＥによる第２の転送方向への転送路が前記Ｍ本の第２の信号線を構成する、ことを特徴とする請求項４記載のプロセッサアレイシステム。
【請求項６】
前記ＰＥブロック内の各ＰＥは、
前記ＰＥブロック内の全ＰＥに対する第１の転送方向の結合線及び第２の転送方向の結合線により、それぞれ、隣接するＰＥブロック内にある、自ＰＥから距離ＭのＰＥと結合されている、ことを特徴とする請求項３に記載のプロセッサアレイシステム。
【請求項７】
前記各ＰＥが、
前記ＰＥとの距離がＭのＰＥ同士を結合する前記第１の転送方向への転送路の転送データを格納する第１の転送バッファ手段と、
前記ＰＥとの距離がＭのＰＥ同士を結合する前記第２の転送方向への転送路の転送データを格納する第２の転送バッファ手段と、
前記ＰＥブロック内の複数の前記第１の転送バッファ手段の中から一つを選ぶ第１のセレクタ手段と、
前記ＰＥブロック内の複数の前記第２の転送バッファ手段の中から一つを選ぶ第２のセレクタ手段と、
転送方向情報を格納するレジスタ手段と、
転送路を利用して、距離Ｍの転送が全ＰＥ間で行われる度に、格納値の絶対値をＭだけ減少させ、格納値がＭよりも小さくなった時点で、前記格納値により、前記第１のセレクタ手段及び前記第２のセレクタ手段を制御して得られる選択結果のいずれかを、前記レジスタ手段の値に基づいて選択し、前記ＰＥへの転送結果として格納する転送結果バッファ手段と、
を含む、ことを特徴とする請求項４、５、６のいずれか一に記載のプロセッサアレイシステム。
【請求項８】
前記各ＰＥが、
前記ＰＥとの距離がＭのＰＥ同士を結合する前記第１の転送方向又は第２の転送方向への転送路の転送データを格納する転送バッファ手段と、
前記ＰＥブロック内の複数の前記転送バッファ手段の中から一つを選ぶセレクタ手段と、
転送路を利用して、距離Ｍの転送が全ＰＥ間で行われる度に、格納値の絶対値をＭだけ減少させ、前記格納値がＭよりも小さくなった時点で、前記格納値で、前記セレクタ手段を制御して得られる選択結果を、前記ＰＥへの転送結果として格納する転送結果バッファ手段と、
を含む、ことを特徴とする請求項４、５、６のいずれか一に記載のプロセッサアレイシステム。
【請求項９】
転送方向として、自ＰＥの前記第１の転送方向又は前記第２の転送方向の一方を正、他方を負とし、
最終的に自ＰＥに再配置されるデータＤを保有するＰＥの自ＰＥ位置からみた格子距離をＫ（但しＫは−Ｎ／２≦Ｋ≦Ｎ／２の任意の値であってよい）とした場合に、転送動作に参加するように各ＰＥの動作・非動作を決定するマスクレジスタを動作側に設定し、
前記第１の転送バッファ手段と前記第２の転送バッファ手段に、自ＰＥ上のデータを格納し、
前記格子距離が正の場合には、
前記レジスタ手段はオンとされ、
前記転送結果バッファ手段には、前記格子距離とＰＥブロック内で前記第１又は第２の転送方向側から数えた場合の自ＰＥ番号との加算結果が格納され、
前記格子距離が負の場合には、
前記レジスタ手段はオフとされ、
前記転送結果バッファ手段には、前記格子距離とＰＥブロック内で、前記第１又は前記第２の転送方向側から数えた場合の自ＰＥ番号との減算結果が格納される、ことを特徴とする請求項７に記載のプロセッサアレイシステム。
【請求項１０】
転送方向として、自ＰＥの前記第１の転送方向又は前記第２の転送方向の一方を正、他方を負とし、最終的に自ＰＥに再配置されるデータを保有するＰＥの自ＰＥ位置からみた格子距離をＫ（但しＫは０≦Ｋ≦Ｎ−１の任意の値であってよい）とした場合に、転送動作に参加するよう各ＰＥの動作・非動作を決定するマスクレジスタを動作側に設定し、
前記転送バッファ手段に自ＰＥ上のデータを格納し、
前記転送結果バッファ手段には、前記格子距離とＰＥブロック内で、前記第１又は前記第２の転送方向側から数えた場合の自ＰＥ番号との加算結果が格納される、ことを特徴とする請求項８に記載のプロセッサアレイシステム。
【請求項１１】
前記レジスタ手段がオンの場合には、
前記転送結果バッファ手段の値ＴがＭ以上であるとき、
Ｔ−Ｍの値が、前記転送結果バッファ手段に格納され、
前記転送結果バッファ手段の値ＴがＭよりも小さいときには、ＰＥブロック内で、前記第２の転送方向の一方の側から数えた場合のＰＥ番号がＴであるＰＥの前記第１及び前記第２の転送バッファ手段の内容を、前記第１のセレクタ手段で選んで、前記転送結果バッファ手段に格納し、
前記マスクレジスタを非動作に設定し、
前記レジスタ手段がオフの場合には、
前記転送結果バッファ手段の値Ｔが−Ｍ以下の場合、Ｔ＋Ｍの値を、前記転送結果バッファ手段に格納し、
Ｔが−Ｍより大きい場合、ＰＥブロック内で、前記第１及び第２の転送方向の一方側から数えた場合のＰＥ番号が−ＴのＰＥの前記第２の転送バッファ手段の内容を前記第２のセレクタ手段で選び、前記転送結果バッファ手段に格納し、前記マスクレジスタを非動作に設定し、
全ＰＥが前記第１の転送方向の結合線と前記第２の転送方向の結合線を利用し、Ｍ隣接する前記第１及び第２の転送方向のＰＥへそれぞれ、前記第１の転送バッファ手段と前記第２の転送バッファ手段の内容を転送すると共に、前記第１の転送バッファ手段と前記第２の転送バッファ手段とに、それぞれ、前記第１の転送方向にＭ隣接ＰＥと前記第２の転送方向にＭ隣接ＰＥから転送されてきたデータを格納する動作を、全ＰＥのマスクレジスタが非動作の設定になるまで、前記マスクレジスタが動作設定である各ＰＥが繰り返し行うように制御する手段を備えている、ことを特徴とする請求項７に記載のプロセッサアレイシステム。
【請求項１２】
前記転送結果バッファ手段の値ＴがＭ以上の場合には、Ｔ−Ｍの値を前記転送結果バッファ手段に格納し、
ＴがＭよりも小さい場合には、ＰＥブロック内で、前記第１及び第２の転送方向の一方側から数えた場合のＰＥ番号が、ＴのＰＥの前記第１の転送バッファ手段の内容を前記第１のセレクタ手段で選び、前記転送結果バッファ手段に格納し、前記マスクレジスタを非動作に設定し、
全ＰＥが前記第１の転送方向の結合線を利用し、前記第１の転送方向のＭ隣接ＰＥへ前記第１の転送バッファ手段の内容を転送すると共に、前記第１の転送バッファ手段に、前記第２の転送方向のＭ隣接ＰＥから転送されてきたデータを格納する動作を、全ＰＥの前記マスクレジスタが非動作の設定になるまで、前記マスクレジスタが動作設定である各ＰＥが繰り返し行うように制御する手段を備えている、ことを特徴とする請求項８に記載のプロセッサアレイシステム。
【請求項１３】
それぞれがＭ個のＳＩＭＤ動作するプロセッサエレメント（以下、「ＰＥ」という）からなる複数のＰＥブロックを有し、距離が、ＰＥブロック内のＰＥの個数と同数であるＭ（ただし、Ｍは１より大きい自然数）のＰＥ同士を結合するＰＥ間での第１の転送方向及び／又は第２の転送方向への転送路を備えたプロセッサアレイシステムを構成するＰＥであって、
前記第１の転送方向及び／又は前記第２の転送方向への転送路による、前記ＰＥが属するＰＥブロックへの複数の転送データの中から一つを選ぶセレクタ手段を含む、ことを特徴とするＰＥ。
【請求項１４】
前記ＰＥとの距離がＭのＰＥ同士を結合する前記第１の転送方向への転送路の転送データを格納する第１の転送バッファ手段と、
前記ＰＥとの距離がＭのＰＥ同士を結合する前記第２の転送方向への転送路の転送データを格納する第２の転送バッファ手段と、
前記ＰＥブロック内のＭ個の前記第１の転送バッファ手段の中から一つを選ぶ第１のセレクタと、
前記ＰＥブロック内のＭ個の前記第２の転送バッファ手段の中から一つを選ぶ第２のセレクタと、
転送方向情報を格納するレジスタ手段と、
転送路を利用して、距離Ｍの転送が全ＰＥ間で行われる度に、格納値の絶対値をＭだけ減少させ、格納値がＭよりも小さくなった時点で、前記格納値により、前記第１のセレクタ及び前記第２のセレクタを制御して得られる選択結果のいずれかを、前記レジスタ手段の値により選択し、前記ＰＥへの転送結果として格納する転送結果バッファ手段と、
を含む、ことを特徴とする請求項１３記載のＰＥ。
【請求項１５】
前記ＰＥとの距離がＭのＰＥ同士を結合する前記第１の転送方向又は第２の転送方向への転送路の転送データを格納する転送バッファ手段を備え、
前記セレクタ手段は、前記第１の転送方向又は第２の転送方向への転送路の転送データを格納する複数の前記転送バッファ手段の中から一つを選び、
転送路を利用して、距離Ｍの転送が全ＰＥ間で行われる度に、格納値の絶対値をＭだけ減少させ、前記格納値がＭよりも小さくなった時点で、前記格納値で、前記セレクタ手段を制御して得られる選択結果を、前記ＰＥへの転送結果として格納する転送結果バッファ手段を含む、ことを特徴とする請求項１３記載のＰＥ。
【請求項１６】
それぞれが複数のプロセッサエレメント（以下、「ＰＥ」という）を含み、一次結合又はリング結合される、複数のＰＥブロックを有し、
前記ＰＥとして、
第１の転送方向への結合線を介して、前記第１の転送方向に関して自ＰＥと予め定められた所定距離離間している、他のＰＥブロックのＰＥと接続され、
前記第１の転送方向と逆方向の第２の転送方向への結合線を介して、前記第２の転送方向に関して自ＰＥと予め定められた所定距離離間している、さらに別のＰＥブロックのＰＥと接続され、
前記第１及び第２の転送方向への結合線の転送データをそれぞれ格納する第１及び第２の転送バッファ手段と、
自ＰＥの前記第１の転送バッファ手段と、前記自ＰＥが属するＰＥブロック内の他のＰＥの前記第１の転送バッファ手段の中から一つを選択する第１のセレクタ手段と、
前記自ＰＥの前記第２の転送バッファ手段と、前記自ＰＥが属する前記ＰＥブロック内の他のＰＥの前記第２の転送バッファ手段の中から一つを選択する第２のセレクタ手段と、
前記結合線を利用した、前記所定距離離間したＰＥ間での転送動作が行われる度に、前記所定距離の値だけ格納値を更新し、前記格納値と前記所定距離の値とが予め定められた大小関係となった時点で、前記格納値により、前記第１のセレクタ手段及び前記第２のセレクタ手段を制御して得られる選択結果のいずれかを、転送方向にしたがって選択し、選択結果を自ＰＥへの転送結果として格納する転送結果バッファ手段と、
を含むＰＥを有する、ことを特徴とするプロセッサアレイシステム。
【請求項１７】
それぞれが複数のプロセッサエレメント（以下、「ＰＥ」という）を含み、一次結合又はリング結合される、複数のＰＥブロックを有し、
前記ＰＥとして、
結合線を介して、自ＰＥと予め定められた所定距離離間している、他のＰＥブロックのＰＥと接続され、
前記結合線の転送データを格納する転送バッファ手段と、
自ＰＥの前記転送バッファ手段と、前記自ＰＥが属するＰＥブロック内の他のＰＥの前記転送バッファの中から一つを選ぶセレクタ手段と、
前記結合線を利用した、前記所定距離離間したＰＥ間での転送動作が行われる度に、前記所定距離の値だけ格納値を更新し、前記格納値と前記所定距離の値とが予め定められた大小関係となった時点で、前記格納値により、前記セレクタ手段を制御して得られる選択結果を、自ＰＥへの転送結果として格納する転送結果バッファ手段と、
を含むＰＥを有する、ことを特徴とするプロセッサアレイシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オンチップ上に多数のプロセッシングエレメント（ＰＥ）を相互結合したプロセッサアレイシステムに関する。
【背景技術】
【０００２】
従来より、ビデオ信号などの画像処理用にオンチップ一次元プロセッサアレイあるいはそれに構成が類似したＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を有するメディアプロセッサが用いられている。例えば非特許文献１に提示されているビデオ画像認識処理に向けた一次元プロセッサアレイでは、図７に示すように、一端から順に画像を行単位で入力していき、そして隣接ＰＥ同士には隣接する１〜数列分の画像列を割り付けた上で、ＳＩＭＤ型制御に基づき、各ＰＥは、制御プロセッサ（ＣＰ）から放送される命令を自ローカルメモリ上のデータに適用することにより、ＰＥ数分だけの並列処理を実現する。
【０００３】
【特許文献１】
特開平５−３４２１８４号公報
【非特許文献１】
京  昭倫著「１２８個の４ウェイＶＬＩＷ型ＲＩＳＣコアを集積した車載向け動画認識ＬＳＩ」電子情報通信学会研究会報告、集積回路研究会（ＩＣＤ），  ２００３年５月、Ｖｏｌ．１０３，Ｎｏ．８９，ｐｐ．１９−２４
【発明の開示】
【発明が解決しようとする課題】
【０００４】
一方、画像処理の中でも、特に画像に対し認識処理を行う場合では、最初の段階でこそ全画素を対象に行われるエッジ検出処理などのように、処理すべき対象データが全ＰＥ上に平等に存在するが、処理が進むに連れ、処理すべき対象データがＰＥ間で均一でなくなってしまうことが多い。
【０００５】
例えば多くの画像認識処理では、それまでの処理で、画像内の幾つかの（矩形）領域を認識対象物が存在する箇所として特定すると、それらの候補領域のみが以降の処理対象となる。また、それらの候補領域が、例えば図８に模式的に示したように、お互いに重なりを持つような位置関係で多数見つかる場合が多いことも一つの特徴である。
【０００６】
ところが、例えば非特許文献１のように、画像列を単位にＰＥへのデータ割付けを行っている一次元プロセッサアレイでは、領域間で、列方向での位置的な重なりがあると、通常は重なりが発生した画像列の処理を受け持つＰＥ（例えば図９（ａ）のＰＥＮ−２）がそうでないＰＥと比べ、重なりの回数分に比例して処理量が増え、ＰＥ間で負荷が不均一な状態となり処理性能が低下する。
【０００７】
こうした処理負荷の不均一性を解消するためには、図９（ｂ）に示すように、複数の矩形領域内画素データを、そっくりＰＥ間で移動するという画素データの再配置処理を行う必要がある。従来の一次元プロセッサアレイ上で、そうした画素データ再配置処理を実現するためには、ＰＥ数が１行分の画素数と同様にＮであるとすると、図１０に示すように、ＣＰを介する形で、Ｎ個の画素を１個ずつ逐次的にＰＥからＰＥへと移動することが、最も効率のよい方法になる。
【０００８】
カウンタＣにＮをセットする（ステップ１０００）。
【０００９】
カウンタＣがゼロとなるまで繰り返す。ステップ１００１の判定においてカウンタＣが非ゼロの場合、以下の処理を行い、ゼロの場合終了する。
【００１０】
ＰＥ番号がＣのＰＥ上のＫをリードする（ステップ１００２）。
【００１１】
ＴＭＰをＣ＋Ｋとする（ステップ１００３）。
【００１２】
ＰＥ番号がＴＭＰのＰＥ上のＤをリードする（ステップ１００４）。
【００１３】
ＰＥ番号がＣのＰＥ上のＴにＤをライトする（ステップ１００５）。
【００１４】
ＣをＣ−１にセットし（ステップ１００６）、ステップ１００１の判定に戻る。
【００１５】
この場合、図１０の１００１〜１００６が示すように６つの処理ステップをＮ回繰り返すため、図１０の１０００を加えると、ＰＥ間で１行分の画素を再配置するのに、計６Ｎ＋１のステップ数が必要であり、効率が悪い、という課題が存在していた。
【００１６】
なお、この課題の一つの解決方法として、ＰＥ間結合に、１次元結合ではなく、例えば特許文献１に開示されているように、２次元トーラスあるいはハイパ・キューブといった、より高次元の結合形態を採用することで、ステップ毎のＰＥ間距離を減らすアプローチが考えられる。
［００１７］
しかし、結合の次元数を増やしてしまうと、チップ上でのレイアウトの自由度が減少したり、あるいはＰＥ間の配線距離が長くなってしまうという問題点が存在していた。
［００１８］
したがって、本発明の主たる目的は、ＰＥ間で画素などのデータを高速に再配置することにより処理の負荷分散を効率よく実現できるプロセッサアレイシステムを提供することにある。
課題を解決するための手段
［００１９］
本発明の第１の側面（アスペクト）に係るプロセッサアレイシステムは、複数（Ｍ個）のＳＩＭＤ動作するプロセッサエレメント（以下、「ＰＥ」という）を含むＰＥブロックを少なくとも三つ有するＰＥブロックアレイを備え、少なくとも一つのＰＥブロックは、前記一つのＰＥブロックとは異なる少なくとも一つの他のＰＥブロックと、１本が所定ビットの、ＰＥブロック内のＰＥの個数と同数であるＭ本の第１の信号線で結ばれるとともに、前記一つのＰＥブロック及び前記他のＰＥブロックとは異なる少なくとも一つのさらに別のＰＥブロックと１本が所定ビットのＭ本の第２の信号線で結ばれ、前記一つのＰＥブロックに含まれる前記ＰＥが、前記Ｍ本の第１の信号線と前記Ｍ本の第２の信号線の中から１本の信号線を選択するセレクタ手段を備える、ことを特徴とする。
［００２０］
本発明において、前記セレクタ手段は、前記Ｍ本の第１の信号線から一本の信号線を選択する第１のセレクタ手段と、前記Ｍ本の前記第２の信号線から一本の信号線を選択する第２のセレクタ手段と、前記第１のセレクタ手段で選択された前記１本の信号線と、前記第２のセレクタ手段で選択された前記１本の信号線から、一本の信号線を選択する第３のセレクタと、を備える。
［００２１］
本発明において、複数の前記ＰＥブロックは、一のＰＥブロックを一つのノードとする一次元結合又はリング結合の形態で接続され、前記ＰＥブロックは、前記ＰＥブロックの一側で隣接するＰＥブロックと相互に前記Ｍ本の第１の信号線によって結ばれるとともに、前記ＰＥブロックの他側で隣接するＰＥブロックと相互に前記Ｍ本の第２の信号線によって結ばれる。
［００２２］
本発明において、Ｎ個（ただし、Ｎは１より大きい自然数）の前記ＰＥに関して、距離がＭ（ただし、Ｍは１より大きくＮより小さい自然数であり、Ｎの約数）のＰＥ同士を結合するＰＥ間での第１の転送方向及び第２の転送方向へのそれぞれの転送路を備え、Ｍ個の隣接するＰＥが一個のＰＥブロックを構成し、前記ＰＥブロック内のＭ個のＰＥによる前記第１の転送方向への転送路が、前記Ｍ本の第１の信号線を構成し、前記ＰＥブロック内の全Ｍ個のＰＥによる前記第２の転送方向への転送路が、前記Ｍ本の第２の信号線を構成する。
【００２３】
本発明において、Ｎ個（ただし、Ｎは１より大きい自然数）の前記ＰＥが、一つのＰＥを一つのノードとする一次元結合又はリング結合の形態で接続され、隣接ＰＥ間の結合線のほかに、さらに距離がＭ（ただし、Ｍは１より大きくＮより小さい自然数であり、Ｎの約数）のＰＥ同士を結合するＰＥ間での前記第１の転送方向及び前記第２の転送方向へのそれぞれの転送路を備え、Ｍ個の隣接するＰＥが一つのＰＥブロックを構成し、前記ＰＥブロック内のＭ個のＰＥによる第１の転送方向への転送路が前記Ｍ本の第１の信号線を構成し、前記ＰＥブロック内のＭ個のＰＥによる第２の転送方向への転送路が前記Ｍ本の第２の信号線を構成する。
【００２４】
本発明において、前記ＰＥブロック内の各ＰＥは、前記ＰＥブロック内の全ＰＥに対する第１の転送方向の結合線及び第２の転送方向の結合線により、それぞれ、隣接するＰＥブロック内にある、自ＰＥから距離ＭのＰＥと結合されている。
【００２５】
本発明において、前記各ＰＥは、
前記ＰＥとの距離がＭのＰＥ同士を結合する前記第１の転送方向への転送路（Ｂ０）の転送データを格納する第１の転送バッファ手段（Ｌ）と、
前記ＰＥとの距離がＭのＰＥ同士を結合する前記第２の転送方向への転送路（Ｂ１）の転送データを格納する第２の転送バッファ手段（Ｒ）と、
前記ＰＥブロック内の複数の前記第１の転送バッファ手段の中から一つを選ぶ第１のセレクタ手段（ＬＳ）と、
前記ＰＥブロック内の複数の前記第２の転送バッファ手段の中から一つを選ぶ第２のセレクタ手段（ＲＳ）と、
転送方向情報を格納するレジスタ手段（Ｆ）と、
転送路を利用して、距離Ｍの転送が全ＰＥ間で行われる度に、格納値の絶対値をＭだけ減少させ、格納値がＭより小さくなった時点で、前記格納値により、前記第１のセレクタ手段（ＬＳ）および第２のセレクタ手段（ＲＳ）を制御して得られる選択結果のいずれかを、レジスタ手段（Ｆ）の値により選択し、前記ＰＥへの転送結果として格納する転送結果バッファ手段（Ｔ）と、を含む。
【００２６】
本発明において、前記各ＰＥは、前記ＰＥとの距離がＭのＰＥ同士を結合する第１転送方向または第２の転送方向への転送路の転送データを格納する転送バッファ手段（Ｌ）と、
前記ＰＥブロック内の複数の前記転送バッファ手段（Ｌ）の中から一つを選ぶセレクタ手段（ＬＳ）と、
転送路を利用して、距離Ｍの転送が全ＰＥ間で行われる度に、格納値の絶対値をＭだけ減少させ、前記格納値がＭより小さくなった時点で、前記格納値で、前記セレクタ手段（ＬＳ）を制御して得られる選択結果を、同ＰＥへの転送結果として格納する転送結果バッファ手段（Ｔ）と、を含む。
【００２７】
本発明において、自ＰＥの右方向または左方向を正、その逆を負とし、最終的に自ＰＥに再配置されるデータ（Ｄ）を保有するＰＥの自ＰＥ位置からみた格子距離をＫ（但しＫは−Ｎ／２≦Ｋ≦Ｎ／２の任意の値であってよい）とした場合に、転送動作に参加するよう各ＰＥの動作非動作を決定するマスクレジスタ（ＭＲ）を動作側に設定し、
前記第１の転送バッファ手段（Ｌ）と前記第２の転送バッファ手段（Ｒ）に、自ＰＥ上のデータ（Ｄ）を格納し、
格子距離（Ｋ）が正の場合は、レジスタ手段（Ｆ）をオンとし、前記転送結果バッファ手段（Ｔ）に格子距離（Ｋ）とＰＥブロック内で左または右から数えた場合の自ＰＥ番号との加算結果を格納し、
格子距離（Ｋ）が負の場合は、レジスタ手段（Ｆ）をオフとし、前記転送結果バッファ手段（Ｔ）に格子距離（Ｋ）とＰＥブロック内で右または左から数えた場合の自ＰＥ番号との減算結果を格納するように制御する。
【００２８】
本発明において、自ＰＥの右方向または左方向を正、その逆を負、最終的に自ＰＥに再配置されるデータＤを保有するＰＥの自ＰＥ位置からみた格子距離をＫ（但しＫは０≦Ｋ≦Ｎ−１の任意の値であってよい）とした場合に、転送動作に参加するよう各ＰＥの動作・非動作を決定するマスクレジスタ（ＭＲ）を動作側に設定し、
前記転送バッファ手段（Ｌ）に自ＰＥ上のデータ（Ｄ）を格納し、
前記転送結果バッファ手段（Ｔ）に、格子距離（Ｋ）とＰＥブロック内で左または右から数えた場合の自ＰＥ番号との加算結果を格納するように制御する。
【００２９】
本発明において、レジスタ手段（Ｆ）がオンの場合は、前記転送結果バッファ手段の値ＴがＭ以上ならばＴ−Ｍの値を前記転送結果バッファ手段（Ｔ）に格納し、前記転送結果バッファ手段（Ｔ）がＭより小さければＰＥブロック内で左から数えた場合のＰＥ番号がＴのＰＥの前記第１の転送バッファ手段（Ｌ）の内容を、前記第１のセレクタ手段（ＬＳ）で選び、前記転送結果バッファ手段（Ｔ）に格納し、マスクレジスタ（ＭＲ）を非動作に設定し、
レジスタ手段（Ｆ）がオフの場合には、前記転送結果バッファ手段（Ｔ）が−Ｍ以下ならばＴ＋Ｍの値を、前記転送結果バッファ手段（Ｔ）に格納し、Ｔが−Ｍより大きければＰＥブロック内で右から数えた場合のＰＥ番号が−ＴのＰＥの前記第２の転送バッファ手段（Ｒ）の内容を前記第２のセレクタ手段（ＲＳ）で選び、前記転送結果バッファ手段（Ｔ）に格納し、マスクレジスタ（ＭＲ）を非動作に設定した上、全ＰＥが、左結合線（Ｂ０）と右結合線（Ｂ１）を利用し、Ｍ隣接する左と右のＰＥへそれぞれ、前記第１の転送バッファ手段（Ｌ）や前記第２の転送バッファ手段（Ｒ）の内容を転送すると共に、前記第１の転送バッファ手段（Ｌ）と前記第２の転送バッファ手段（Ｒ）にそれぞれ右Ｍ隣接と左Ｍ隣接ＰＥから転送されてきたデータを格納する動作を、全ＰＥのマスクレジスタＭＲが非動作の設定になるまで、マスクレジスタ（ＭＲ）が動作設定である各ＰＥが繰り返し行うように制御する手段（制御プロセッサＣＰ）を備えている。
【００３０】
本発明において、前記転送結果バッファ手段（Ｔ）がＭ以上ならばＴ−Ｍの値を前記転送結果バッファ手段（Ｔ）に格納し、
ＴがＭより小さければＰＥブロック内で左から数えた場合のＰＥ番号がＴのＰＥの前記第１の転送バッファ手段（Ｌ）の内容を第１のセレクタ手段（ＬＳ）で選び前記転送結果バッファ手段（Ｔ）に格納し、マスクレジスタ（ＭＲ）を非動作に設定した上、全ＰＥが左結合線（Ｂ０）を利用し、Ｍ隣接する左のＰＥへ前記第１の転送バッファ手段（Ｌ）の内容を転送すると共に、前記第１の転送バッファ手段（Ｌ）に右Ｍ隣接ＰＥから転送されてきたデータを格納する動作を、全ＰＥのマスクレジスタ（ＭＲ）が非動作の設定になるまで、マスクレジスタ（ＭＲ）が動作設定である各ＰＥが繰り返し行うように制御する手段（制御プロセッサＣＰ）を備えている。
［００３１］
本発明の他の側面によれば、それぞれがＭ個のＳＩＭＤ動作するプロセッサエレメント（以下、「ＰＥ」という）からなる複数のＰＥブロックを有し、距離が、ＰＥブロック内のＰＥの個数と同数であるＭ（ただし、Ｍは１より大きい自然数）のＰＥ同士を結合するＰＥ間での第１の転送方向及び／又は第２の転送方向への転送路を備えたプロセッサアレイシステムを構成するＰＥであって、前記第１及び／又は第２の転送方向への転送路による前記ＰＥが属するＰＥブロックへの複数の転送データの中から一つを選ぶセレクタ手段を含むＰＥが提供される。
［００３２］
本発明のＰＥは、前記ＰＥとの距離がＭのＰＥ同士を結合する前記第１の転送方向への転送路の転送データを格納する第１の転送バッファ手段と、前記ＰＥとの距離がＭのＰＥ同士を結合する前記第２の転送方向への転送路の転送データを格納する第２の転送バッファ手段と、前記ＰＥブロック内のＭ個の前記第１の転送バッファ手段の中から一つを選ぶ第１のセレクタと、前記ＰＥブロック内のＭ個の前記第２の転送バッファ手段の中から一つを選ぶ第２のセレクタと、転送方向情報を格納するレジスタ手段と、転送路を利用して、距離Ｍの転送が全ＰＥ間で行われる度に、格納値の絶対値をＭだけ減少させ、格納値がＭよりも小さくなった時点で、前記格納値により、前記第１のセレクタ及び前記第２のセレクタを制御して得られる選択結果のいずれかを、前記レジスタ手段の値により選択し、前記ＰＥへの転送結果として格納する転送結果バッファ手段と、を含む。あるいは、本発明のＰＥは、前記ＰＥとの距離がＭのＰＥ同士を結合する前記第１の転送方向又は第２の転送方向への転送路の転送データを格納する転送バッファ手段を備え、前記セレクタ手段は、前記第１の転送方向又は第２の転送方向への転送路の転送データを格納する複数の前記転送バッファ手段の中から一つを選び、転送路を利用して、距離Ｍの転送が全ＰＥ間で行われる度に、格納値の絶対値をＭだけ減少させ、前記格納値がＭよりも小さくなった時点で、前記格納値で、前記セレクタ手段を制御して得られる選択結果を、前記ＰＥへの転送結果として格納する転送結果バッファ手段を含む。
［００３３］
本発明に係るシステムは、それぞれが複数のプロセッサエレメント（以下、「ＰＥ」という）を含み、一次結合又はリング結合される、複数のＰＥブロックを有し、前記ＰＥとして、
第１の転送方向への結合線を介して、前記第１の転送方向に関して自ＰＥと予め定められた所定距離離間している、他のＰＥブロックのＰＥと接続され、
前記第１の転送方向と逆方向の第２の転送方向への結合線を介して、前記第２の転送方向に関して自ＰＥと予め定められた所定距離離間している、さらに別のＰＥブロックのＰＥと接続され、
前記第１及び第２の転送方向への結合線の転送データをそれぞれ格納する第１及び第２の転送バッファ手段と、
自ＰＥの前記第１の転送バッファ手段と、前記自ＰＥが属するＰＥブロック内の他のＰＥの前記第１の転送バッファ手段の中から一つを選択する第１のセレクタ手段と、
前記自ＰＥの前記第２の転送バッファ手段と、前記自ＰＥが属する前記ＰＥブロック内の他のＰＥの前記第２の転送バッファ手段の中から一つを選択する第２のセレクタ手段と、
前記結合線を利用した、前記所定距離離間したＰＥ間での転送動作が行われる度に、前記所定距離の値だけ格納値を更新し、前記格納値と前記所定距離の値とが予め定められた大小関係となった時点で、前記格納値により、前記第１のセレクタ手段及び前記第２のセレクタ手段を制御して得られる選択結果のいずれかを、転送方向にしたがって選択し、選択結果を自ＰＥへの転送結果として格納する転送結果バッファ手段と、を含むＰＥを有する。あるいは、前記ＰＥとして、結合線を介して、自ＰＥと予め定められた所定距離離間している、他のＰＥブロックのＰＥと接続され、
前記結合線の転送データを格納する転送バッファ手段と、
自ＰＥの前記転送バッファ手段と、前記自ＰＥが属するＰＥブロック内の他のＰＥの前記転送バッファの中から一つを選ぶセレクタ手段と、
前記結合線を利用した、前記所定距離離間したＰＥ間での転送動作が行われる度に、前記所定距離の値だけ格納値を更新し、前記格納値と前記所定距離の値とが予め定められた大小関係となった時点で、前記格納値により、前記セレクタ手段を制御して得られる選択結果を、自ＰＥへの転送結果として格納する転送結果バッファ手段と、を含むＰＥを有する。
【発明の効果】
［００３４］
本発明によれば、処理の負荷分散を効率よく実現することができる。その理由は、本発明においては、Ｎ個のＰＥを有する一次元プロセッサアレイ型システム上でＰＥ間結合の次元数を増やさずに、１行分（＝Ｎ個）のデータをＰＥ間で相互に交換するのに要するステップ数を、短縮できるようにしたためである。また、本発明によれば、レイアウトの容易性を維持することができる。さらに、本発明によれば、ハードウェア規模を小さくすることができる。また、本発明によれば、ＳＩＭＤ制御で同期動作する全ＰＥが同時に送信するデータを、受信側ＰＥにローカルな情報、すなわち「自ＰＥと発信元ＰＥとの格子距離情報」や「自ＰＥ番号」のみで、正確に受け取ることが可能となり、ネットワークの規模（ビット数、複雑度）を低減できる。
【図面の簡単な説明】
［００３５］
［図１］本発明の一次元プロセッサアレイの概略構成を示すブロック図である。
［図２］本発明の一次元プロセッサアレイのＰＥブロック間結合線の構成を示すブロック図である。
［図３］本発明を実施するための最良の形態の構成を示すブロック図である。
［図４］本発明を実施するための最良の形態の動作の前半を示す流れ図である。
［図５］本発明を実施するための最良の形態の動作の後半を示す流れ図である。
［図６］本発明を実施するための最良の形態の動作の具体例を示す図である。
［図７］背景技術である既存の一次元プロセッサアレイの概略構成を示すブロック図である。
［図８］本発明が解決しようとする課題を説明するための図である。
［図９］本発明が解決しようとする課題を説明するための図である。
［図１０］従来技術の場合の動作の流れを示す図である。
［図１１］本発明の効果の一つを示す図である。
［図１２］本発明の第２の発明を実施するための最良の形態の動作の前半を示す流れ図である。
［図１３］本発明の第２の発明を実施するための最良の形態の動作の後半を示す流れ図である。
符号の説明
［００３６］
１００  一次元プロセッサアレイ（ＰＥアレイ）
１０１  ＰＥ（プロセッシング・エレメント）
１０２  ＰＥブロック（ＰＥの集合体）
１０３  右から左へのＰＥ間結合線Ｂ０（左結合線）
１０４  左から右へのＰＥ間結合線Ｂ１（右結合線）
１１０  制御プロセッサＣＰ
１１３  命令コード
３０１  Ｂ０からの転送データを格納するための転送バッファＬ
３０２  Ｂ１からの転送データを格納するための転送バッファＲ
３０３  セレクタ手段ＬＳ
３０４  セレクタ手段ＲＳ
３０５  転送結果バッファＴ
３０６  方向レジスタＦ
３０７  マスクレジスタＭＲ
３０８  命令デコーダＤＥ
３０９  レジスタファイルＲＦ
３１０  データメモリ
３１１  演算器
４００〜４０５、５００〜５１１、１０００〜１００６、１２００〜１２０２、１３００〜１３０６  ステップ
【発明を実施するための最良の形態】
【００３７】
上記した本発明についてさらに詳細に説述すべく添付図面を参照して以下に説明する。
【００３８】
はじめに、本発明の概要・動作原理を説明しておく。Ｎ個のＰＥを有する一次元プロセッサアレイ型システムは、Ｍをチップ開発時でのレイアウトの単位であるＰＥブロック内のＰＥ数、ＸをＰＥ間の単位転送バイト数とする。
【００３９】
図１、図３を参照すると、本発明のシステムは、
（Ａ）距離ＭのＰＥ同士を結合することによって得られるＰＥブロック単位で見た場合でのＭ本のＸバイト幅結合線手段（左結合線）Ｂ０（右から左へ）、及び、Ｍ本のＸバイト幅結合線手段（右結合線）Ｂ１（左から右へ）と、
（Ｂ）ＰＥブロック内の各ＰＥそれぞれに存在する、Ｂ０とＢ１からのデータを格納する転送バッファＬ及び転送バッファＲ、
（Ｃ）ＰＥブロック内にあるＭ個のＬとＲの中から１つを選ぶＭ入力１出力のセレクタＬＳ及びセレクタＲＳ、
（Ｄ）ＰＥの動作／非動作を制御するマスクレジスタＭＲ、
（Ｅ）転送結果の格納及びカウンタとしても用いられる転送結果バッファＴ、
（Ｆ）転送方向を記憶する方向レジスタＦ、
とを備えている。
【００４０】
上記構成のもとで、
・再配置対象をＮ個のＸバイトデータＤとし、
・自ＰＥの右方向を正、左方向を負とし、
・自ＰＥに再配置される予定のデータＤが存在するＰＥの自ＰＥ位置からみた格子距離をＫ（但しＫは−Ｎ／２≦Ｋ≦Ｎ／２の任意の値であってよい）とすると、
制御プロセッサＣＰは、ＰＥアレイに対して以下の制御を行う(図４参照）。
【００４１】
まず、各ＰＥが転送バッファＬとＲに、自ＰＥ上のデータＤを格納する（図４のステップ４００）。
【００４２】
格子距離Ｋが正又は０の場合には、格子距離Ｋに、ＰＥブロック内で左から数えた場合の自ＰＥ番号を加算した結果を、転送結果バッファＴに格納する（図４の４０２）。格子距離Ｋが負の場合は、格子距離Ｋに、ＰＥブロック内で右から数えた場合の自ＰＥ番号を減算した結果を転送結果バッファＴに格納する（図４の４０３）。格子距離Ｋが０以上の場合は方向レジスタＦに１をセットし（図４の４０２）、格子距離Ｋが負の場合には方向レジスタＦに０をセットし（図４の４０３）、マスクレジスタＭＲに１を格納する（図４の４０５）ように、ＰＥアレイを制御する。
【００４３】
次に、制御プロセッサＣＰは、全ＰＥのマスクレジスタＭＲをモニターし、全ＰＥのマスクレジスタＭＲが全てゼロになるまで、下記動作をステップ毎に繰り返すように、ＰＥアレイを制御する。
【００４４】
すなわち、マスクレジスタＭＲが非ゼロのＰＥ上は、転送結果バッファＴと方向レジスタＦの値に応じ、
方向レジスタＦが１の場合は、転送結果バッファＴがＭ以上である場合、Ｔ−Ｍの値を転送結果バッファＴに格納し（図５のステップ５０６）、転送結果バッファＴがＭより小さい場合、ＰＥブロック内で左から数えた場合のＰＥ番号がＴであるＰＥの転送バッファＬの内容を、セレクタＬＳで選び、転送結果バッファＴに格納し（図５のステップ５０３）、マスクレジスタＭＲをゼロにセットする（図５のステップ５０４）。
【００４５】
方向レジスタＦが０の場合、転送結果バッファＴが−Ｍ以下である場合、Ｔ＋Ｍの値を、転送結果バッファＴに格納し（図５のステップ５１１）、転送結果バッファＴが−Ｍより大きい場合、ＰＥブロック内で右から数えた場合のＰＥ番号が−ＴであるＰＥの転送バッファＲの内容をセレクタＲＳで選び、転送結果バッファＴに格納し（図５のステップ５０８）、かつマスクレジスタＭＲをゼロにセットする（図５のステップ５０９）ように制御する。なお、転送結果バッファ手段Ｔにおいて、方向レジスタＦが１のとき、セレクタＬＳで選択された出力を選択し、方向レジスタＦが０のとき、セレクタＲＳで選択された出力を選択する機能は、請求項２の第３のセレクタ手段に対応する。
【００４６】
その後、結合線Ｂ０と結合線Ｂ１を利用し、Ｍ隣接する左と右のＰＥへ転送バッファＬや転送バッファＲの内容を転送する（図５のステップ５０５、５１０）と共に、転送バッファＬと転送バッファＲに、それぞれ、右Ｍ隣接と左Ｍ隣接するＰＥから転送されてきたデータを格納するように動作する。
【００４７】
上記構成および動作により、最大１＋（Ｎ÷２Ｍ）ステップ後に、各ＰＥの転送結果バッファＴには、自ＰＥから距離ＫにあるＰＥ上のデータが格納される。
【００４８】
このため、図１０に示す従来の手法と比べると、約１２Ｍ倍の効率で、１行内にあるＮ個のＸバイトデータを再配置することができる。
【００４９】
すなわち、本発明によれば、従来のように、隣接ＰＥとではなく、距離ＭのＰＥと結合するＰＥ間結合線Ｂ０、結合線Ｂ１を有すると共に、各ＰＥが、最大（１＋（Ｎ÷２Ｍ））のステップ数の間の各ステップ中に、隣接ＰＥブロックから転送されて次々と自ＰＥブロックを経由していくステップ毎、２Ｍ個のデータの中から、構成要素として転送結果レジスタＴ、方向レジスタＦ、転送バッファＬ、転送バッファＳ、セレクタＬＳ、ＲＳ、そしてマスクレジスタＭＲを用いた、単純な動作で、保持しておくべきデータを抽出できるように構成されている。
【００５０】
このため、本発明によれば、Ｎ個のＰＥを有する一次元プロセッサアレイ型システム上でＰＥ間結合の次元数を増やさずに、１行分（＝Ｎ個）のデータをＰＥ間で相互に交換するのに要するステップ数が従来の最大（１＋６Ｎ）から最大（１＋（Ｎ÷２Ｍ））に短縮できる。
【００５１】
本発明によれば、レイアウトの容易性を維持することができる。すなわち、本発明においては、Ｍ個のＰＥからなるＰＥブロックをレイアウトの単位としていることから結合の一次元性が維持されており、多次元結合とした場合よりも、チップ上でのレイアウトが容易化している。
【００５２】
本発明において、Ｍ＝√Ｎとすると、ＰＥ間データ転送距離は最大で、約√Ｎ÷２となり、これは典型的な２次元結合である八方格子結合のそれと同等である。そして、ＰＥ毎に必要となるデータ転送用セレクタの規模は、八方格子結合の場合では、図１１（ａ）に示すように、８データから１つを選ぶセレクタが８つ必要なのに対し、本発明によれば、Ｎが１０２４（Ｍが３２）では八方格子結合と同じ８つ必要とするが、Ｎが１０２４よりも小さい場合、例えば２５６（Ｍが１６）では、図１１（ｂ）に示すように、その約半分の４つだけで済むため、実用的なＮの値域内ではハードウェア規模を小さくできる。
【００５３】
これは、本発明においては、転送方向が左右の２方向のみで済むため実現に要するハードウェアコストが低い一次元結合と、ＰＥ毎のローカルなセレクタを有効に組み合わせているためである。以下、実施の形態について説明する。
【００５４】
図１を参照すると、本発明の第１の実施の形態は、Ｎ個のＰＥ１０１を有するＰＥアレイ１００と、ＰＥアレイに命令を供給する制御プロセッサ１１０と、を有する。
【００５５】
ＰＥアレイ１００は、それぞれが、Ｍ個（ただし、ＭはＮの約数）のＰＥ１０１を含むＮ÷Ｍ個のＰＥブロック１０２と、隣接するＰＥブロック同士を接続する左結合線Ｂ０(１０３、右から左へ)と、右結合線Ｂ１(１０４、左から右へ)と、を備えている。
【００５６】
図２を参照すると、一つのＰＥブロック１０２内の各ＰＥ１０１は、隣接するＰＥブロック１０２内にある自ＰＥから距離Ｍ（図２ではＭが４）のＰＥと結合しており、Ｂ０とＢ１は、それぞれ、ＰＥブロック１０２内の全ＰＥに対する右から左、左から右への結合線の集合体である。
【００５７】
図３を参照すると、各ＰＥ１０１は、Ｂ０とＢ１のうちの対応する一部の結合線で転送されてきたデータを格納する転送バッファ手段Ｌ（３０１）とＲ（３０２）、
ＰＥブロック１０２内の全ＰＥのＬとＲの中から１つを選ぶＭ入力（図３ではＭが８）１出力のセレクタ手段ＬＳ（３０３）とＲＳ（３０４）、
転送結果の格納およびカウンターとしても用いられる転送結果バッファ手段Ｔ（３０５）、
転送方向を記憶する方向レジスタＦ（３０６）、
ＰＥの動作非動作を制御しかつ制御プロセッサＣＰ（１１０）からもアクセス可能なマスクレジスタＭＲ（３０７）、
とを含む。
【００５８】
また、ＰＥ１０１は、通常、その他に命令デコーダＤＥ（３０８）、レジスタファイルＲＦ（３０９）、データメモリ（３１０）、そして演算器  （３１１）を備えている。
【００５９】
転送結果バッファ手段Ｔ（３０５）は、その内容を、レジスタファイルＲＦ（３０９）に転送したり、データメモリ（３１０）へライトしたり、あるいは、直接に、演算器（３１１）のオペランドとして利用できるように構成されている。
【００６０】
これらの手段は、それぞれ概略つぎのように動作する。なお、自ＰＥの右方向を正、左方向を負とした場合に、自ＰＥに再配置される予定のデータＤが存在するＰＥの自ＰＥ位置からみた格子距離をＫ（但しＫは−Ｎ／２≦Ｋ≦Ｎ／２の任意の値であってよい）としている。この定義は逆でもかまわないが、以下では、この定義（自ＰＥの左方向を正、右方向を負）のもとでの各手段の概略動作を述べる。
【００６１】
制御プロセッサ１１０から「ＭＶＳＥＴ」という命令コード１１３が送られてくるものとする。各ＰＥ１０１は、自分が送出するデータをＤとすると、転送バッファ手段ＬとＲにＤを格納し、全てのＰＥのＭＲを１にセットする。
【００６２】
Ｋが正の場合は、方向レジスタＦに１、かつ転送結果バッファ手段Ｔに、ＫとＰＥブロック内で左から数えた場合の自ＰＥ番号との加算結果、Ｋが負の場合は、Ｆに０、かつ、転送結果バッファＴ手段に、ＫとＰＥブロック内で右から数えた場合の自ＰＥ番号との減算結果を格納する。通常これらの動作は、単純のため、１ステップで完了できる。
【００６３】
制御プロセッサ１１０から「ＭＶＬＲ」という命令コード１１３が送られてくると、マスクレジスタＭＲが１のＰＥは、
方向レジスタＦが１の場合には、
ＴがＭ以上ならば、Ｔ−Ｍの値をＴに格納し、
ＴがＭより小さければ、ブロック内で左から数えた場合のＰＥ番号がＴのＰＥのＬの内容をＬＳで選びＴに格納し、かつ、ＭＲをゼロにセットする。
【００６４】
方向レジスタＦが０の場合には、
Ｔが−Ｍ以下ならば、Ｔ＋Ｍの値をＴに格納し、
Ｔが−Ｍより大きければ、ブロック内で右から数えた場合のＰＥ番号が−ＴのＰＥのＲの内容をＲＳで選び、Ｔに格納し、かつＭＲをゼロにセットする。
【００６５】
次に、全ＰＥがＢ０とＢ１を利用し、Ｍ隣接する左と右のＰＥへＬやＲの内容を転送すると共に、ＬとＲに、それぞれ右Ｍ隣接と左Ｍ隣接ＰＥから転送されてきたデータを格納する。通常、これらの動作は単純のため１ステップで完了できる。
【００６６】
一方、制御プロセッサ１１０は、全ＰＥのＭＲがゼロになるまで、ステップ毎に同じ命令コード「ＭＶＬＲ」をＰＥに送り続ける。
【００６７】
次に、図４及び図５のフローチャートを参照して、本実施の形態の全体の動作について詳細に説明する。
【００６８】
図４は、「ＭＶＳＥＴ」命令コードが制御プロセッサ１１０から送られた場合の各ＰＥで実施される動作に係わるフローチャートである。
【００６９】
ＤをＬとＲにそれぞれセットする（ステップ４００）。
【００７０】
全ＰＥのＭＲに１をセットする（ステップ４０５）。
【００７１】
Ｋが０以上か否かを判定する（ステップ４０１）。
【００７２】
Ｋが０以上の場合には、方向レジスタＦに１をセットし、かつ、ＫにＰＥブロック内で左から数えた場合の自ＰＥ番号を加算した結果を、転送結果バッファＴに格納する（ステップ４０２）。
【００７３】
Ｋが０より小さい場合には、方向レジスタＦに０をセットし、転送結果バッファＴにＫにＰＥブロック内で右から数えた場合の自ＰＥ番号を加算した結果をＴに格納する（ステップ４０３）。
【００７４】
ステップ４００〜４０５の動作は単純であるため、通常１ステップで行うことができる。
【００７５】
図５は、「ＭＶＬＲ」命令コードに係わる、制御プロセッサ１１０および各ＰＥで実施される動作に係わるフローチャートである。
【００７６】
まず、制御プロセッサ１１０が、マスクレジスタＭＲが１であるＰＥが存在するか否かを調べる（ステップ５２０）。
【００７７】
そのようなＰＥが存在する場合にＰＥアレイ１００へ命令コード「ＭＶＬＲ」を送る（ステップ５００）。
【００７８】
ＰＥアレイ側では、マスクレジスタＭＲが１のＰＥ上において、方向レジスタＦが１であるか否かを判定する（ステップ５０１）。
【００７９】
方向レジスタＦが１の場合には、ステップ５０２〜５０５の動作、方向レジスタＦが０の場合には、ステップ５０７〜５１１の動作を行う。
【００８０】
転送結果バッファＴがＭより小さいか否かを判定する（ステップ５０２）。
【００８１】
転送結果バッファＴがＭより小さいければ、ＰＥブロック内で左から数えた場合のＰＥ番号がＴのＰＥ上のＬをＬＳで選び、転送結果バッファＴに格納する（ステップ５０３）。
【００８２】
マスクレジスタＭＲを０にセットする（ステップ５０４）。
【００８３】
結合線Ｂ０を用いて、Ｌ内データを左方向でＭだけ離れたＰＥの転送バッファＬに転送する（ステップ５０５）。
【００８４】
ＴがＭ以上の場合は、転送結果バッファＴをＴ−Ｍに更新する(ステップ５０６)。
【００８５】
Ｔが−Ｍより大きいか否かを判定する（ステップ５０７）。
【００８６】
Ｔが−Ｍより大きければ、ＰＥブロック内で右から数えた場合のＰＥ番号が−ＴのＰＥ上のＲをＲＳで選び、転送結果バッファＴに格納する（ステップ５０８）。
【００８７】
マスクレジスタＭＲを０にセットする（ステップ５０９）。
【００８８】
結合線Ｂ１を用いてＲ内データを右方向でＭだけ離れたＰＥの転送バッファＲに転送する（ステップ５１０）。
【００８９】
Ｔが−Ｍ以下の場合は、転送結果バッファＴをＴ＋Ｍに更新する(ステップ５１１)。
【００９０】
ステップ５０１〜５１１の動作は、単純であるため、通常１ステップで行うことができる。
【００９１】
次に、本実施の形態の効果について説明する。
【００９２】
本実施の形態では、ＰＥ同士を距離Ｍで双方向で結合しているため、ＰＥ数がＮにおいて、全ＰＥから送出されたＮ個の転送データＤは、１＋（Ｎ÷２Ｍ）のステップ数をかけて全ＰＥブロックを通過できる。
【００９３】
また、本実施の形態では、さらに各ＰＥが、ＰＥブロック内のＭ個のＰＥが有する転送バッファＬとＲの内容の中から一つを選ぶためのセレクタＬＳとＲＳ、およびそれらをどのタイミングで利用すべきかを指定するカウンターとしての役割も果たす転送結果バッファＴとを備えているため、Ｂ０やＢ１を使って、各ＰＥブロックを、右から左、および、左から右へと通過していく転送データＤ群の中から、所定のステップにおいて、タイミングで効率よく必要なものを選択し、自ＰＥのＴに取り込むことができる。
【００９４】
本実施の形態では、マスクレジスタＭＲを利用して全ＰＥが転送データを得た時点で処理を停止するようにしているため、さらに多くの場合では、１＋（Ｎ÷２Ｍ）よりも少ないステップ数で全動作を終えることができる。
【００９５】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。図１、図２、図３を参照すると、本発明の第２の実施の形態は、図１と図２において、右結合線Ｂ１が存在しない点、及び、図３において、転送バッファＲ、セレクタＲＳ、方向レジスタＦ、そして右結合線Ｂ１が存在しない点以外は、本発明の第１の実施の形態と同じ構成をもつ。これらの手段は、概略つぎのように動作する。なお、自ＰＥに再配置される予定のデータＤが存在するＰＥの自ＰＥ位置から右方向へみた場合の格子距離をＫ（但しＫは０≦Ｋ≦Ｎ−１の任意の値であってよい）とする。
【００９６】
制御プロセッサ１１０から「ＭＶＳＥＴ」という命令コード１１３が送られてくるものとする。各ＰＥ１０１は自分が送出するデータをＤとする。
【００９７】
転送バッファ手段ＬにＤを格納し、全てのＰＥのＭＲを１にセットし、転送結果バッファ手段ＴにＫとＰＥブロック内で左から数えた場合の自ＰＥ番号との加算結果を格納する。通常これらの動作は単純のため１ステップで完了できる。
【００９８】
制御プロセッサ１１０から、「ＭＶＬＲ」という命令コード１１３が送られてくると、ＭＲが非ゼロのＰＥは、
ＴがＭ以上ならば、Ｔ−Ｍの値を転送結果バッファＴに格納し、
ＴがＭより小さければ、ブロック内で左から数えた場合のＰＥ番号がＴのＰＥのＬの内容をＬＳで選び、転送結果バッファＴに格納し、かつ、マスクレジスタＭＲをゼロにセットする。
【００９９】
次に、全ＰＥがＢ０を利用しＭ隣接する左のＰＥへＬの内容を転送すると共に、Ｌに右Ｍ隣接ＰＥから転送されてきたデータを格納する。
【０１００】
また通常これらの動作は、単純のため１ステップで完了できる。
【０１０１】
一方、制御プロセッサ１１０は、全ＰＥのＭＲがゼロになるまで、サイクル毎に同じ命令コード「ＭＶＬＲ」をＰＥに送り続ける。
【０１０２】
次に、図１２及び図１３のフローチャートを参照して本発明の第２の発明の実施の形態の全体の動作について詳細に説明する。
【０１０３】
図１２は、「ＭＶＳＥＴ」命令コードが制御プロセッサ１１０から送られた場合の各ＰＥで実行される動作を説明するためのフローチャートである。
【０１０４】
Ｄを転送バッファＬにそれぞれセットする（ステップ１２０２）。
【０１０５】
全ＰＥのマスクレジスタＭＲに１をセットする（ステップ１２０１）。
【０１０６】
ＫにＰＥブロック内で左から数えた場合の自ＰＥ番号を加算した結果を転送結果バッファＴに格納する（ステップ１２００）。
【０１０７】
ステップ１２００〜１２０２の動作は単純であるため、通常１ステップで行うことができる。
【０１０８】
図１３は、「ＭＶＬＲ」命令コードに係わる、制御プロセッサ１１０および各ＰＥで実施される動作を説明するためのフローチャートである。
【０１０９】
まず、制御プロセッサ１１０が、ＭＲが１であるＰＥが存在するか否かを調べ（１３０１）、そのようなＰＥが存在する場合にＰＥアレイ１００へ命令コード「ＭＶＬＲ」を送る（ステップ１３００）。
【０１１０】
ＰＥアレイ側では、ＭＲが１のＰＥ上において、転送結果バッファＴがＭより小さいか否かを判定する（ステップ１３０２）。
【０１１１】
転送結果バッファＴがＭより小さいければ、ＰＥブロック内で左から数えた場合のＰＥ番号がＴのＰＥ上のＬをセレクタＬＳで選び、転送結果バッファＴに格納する（ステップ１３０３）。
【０１１２】
ＭＲを０にセットし（ステップ１３０４）、その後、結合線Ｂ０を用いて、Ｌ内データを左方向でＭだけ離れたＰＥの転送バッファＬに転送する（ステップ１３０５）。
【０１１３】
ＴがＭ以上の場合は、転送結果バッファＴをＴ−Ｍに更新する(ステップ１３０６)。
【０１１４】
また、ステップ１３０２〜１３０６の動作は単純であるため、通常１ステップで行うことができる。
【０１１５】
次に、本発明の第２の実施の形態の効果について説明する。
【０１１６】
本実施の形態では、ＰＥ同士を距離Ｍで結合しているため、ＰＥ数がＮにおいて、全ＰＥから送出されたＮ個の転送データＤは、１＋（Ｎ÷Ｍ）のステップ数をかけて全ＰＥブロックを通過できる。
【０１１７】
また、本実施の形態では、さらに、各ＰＥが、ＰＥブロック内のＭ個のＰＥが有する転送バッファＬの内容の中から一つを選ぶためのセレクタＬＳおよびＲＳを、どのタイミングで利用すべきかを指定するカウンターとしての役割も果たす転送結果バッファＴを備えているため、Ｂ０を使って各ＰＥブロックを右から左へと通過していく転送データＤ群の中から、所定のステップにおいて、タイミングで効率よく必要なものを選択し、自ＰＥのＴに取り込むことができる。
【０１１８】
本実施の形態では、マスクレジスタＭＲを利用して全ＰＥが転送データを得た時点で処理を停止するようにしているため、さらに多くの場合では、１＋（Ｎ÷Ｍ）よりも少ないステップ数で全動作を終えることができる。
【０１１９】
本発明の第２の実施の形態は、前記第１の実施の形態と比べると、１行分のＮ個の画素をＰＥ間で再配置するのに要するステップ数は２倍程度に増えるが、構成要素がより少ないため、ハードウェア規模の増加がより少ない、という効果がある。
【実施例】
【０１２０】
次に、具体的な実施例に即して説明する。図６は、上記した本発明の動作を具体的に説明するための図である。
【０１２１】
図６（ａ）では、各列で、１つのＰＥ上での設定を表現し、Ｎを１６、Ｍを４としている。また、簡単のため各ＰＥは自ＰＥ番号を送出データＤ、任意の−８〜７の値を、転送元ＰＥへの距離値Ｋとして設定した場合に、ＭＶＳＥＴ命令を発行した直後での、図４のフローチャート通りに、Ｋやブロック内での右からおよび左からのＰＥ番号を用いてＦ、Ｔ、Ｌ、Ｒ、ＭＲの値を設定した結果を示している。
【０１２２】
ここで、図６（ａ）のＴ欄が、同じ列に属するＫと各列の網目欄の内容を、Ｋが負の場合は減算、正の場合は加算することにより求めていることがわかる。例えば１列目のＴ＝−６は、Ｋ＝−３とブロック内右からのＰＥ＃＝３の減算で求められ、３列目のＴ＝４は、Ｋ＝２とブロック内左からのＰＥ＃＝２の加算で求められている。
【０１２３】
図６（ｂ）乃至図６（ｄ）は、ＭＶＬＲ命令の１回〜３回目の繰り返しを行った後の状態（但しＬとＲは更新前の値を表示）を、図６（ａ）と対応した表形式でそれぞれ示している。
【０１２４】
図６（ｂ）乃至図６（ｄ）では、図５のフローチャートに従い、Ｔの絶対値がＭを下回ったことにより、転送バッファＬまたはＲの値が、転送結果バッファＴへ格納されたＰＥについては、当該Ｔ欄およびＭＲ欄に網目を施して表示している。
【０１２５】
図６から、Ｋで指定された距離に位置するＰＥ上のＤの値が、図５のフローチャートに示した動作を３回（＝１＋１６／（４×２））繰り返した後に、転送結果バッファＴに格納されていることがわかる（図６（ｄ）のＴ欄参照）。
【０１２６】
図６（ｅ）は、図６（ｂ）乃至図６（ｄ）の間に行われたＰＥ間データ移動の様子（距離と方向）を矢線にて表現したものである。
【０１２７】
本発明によれば、高速にＰＥ間でデータを再配置することが可能な一次元プロセッサアレイの提供により、処理負荷をＰＥ間に分散させ一次元プロセッサアレイの性能を向上する用途に適用できる。また処理負荷の分散のみでなく、一次元プロセッサアレイの各ＰＥにマッピングされた画像の拡大・縮小・変形といった用途にも適用できる。以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図１】
0004483991.tif 000002
【図２】
0004483991.tif 000003
【図３】
0004483991.tif 000004
【図４】
0004483991.tif 000005
【図５】
0004483991.tif 000006
【図６】
0004483991.tif 000007
【図７】
0004483991.tif 000008
【図８】
0004483991.tif 000009
【図９】
0004483991.tif 000010
【図１０】
0004483991.tif 000011
【図１１】
0004483991.tif 000012
【図１２】
0004483991.tif 000013
【図１３】
0004483991.tif 000014