(57)【特許請求の範囲】
【請求項１】
ソート対象データを記憶する記憶手段を有し、一次元結合された複数のプロセッシングエレメントと、
ソート制御情報を供給する制御情報出力手段と、
該制御情報出力手段から入力される前記ソート制御情報に基づいて、前記複数のプロセッシングエレメントのうちの、所定の１つの前記プロセッシングエレメントの前記記憶手段の前記ソート対象データと所定の他の前記プロセッシングエレメントの前記記憶手段の前記ソート対象データとを交換する前記プロセッシングエレメント毎のデータ交換手段とを備えることを特徴とするＳＩＭＤ型並列データ処理装置。
【請求項２】
ソート対象データを記憶する記憶手段を有し、一次元結合された複数のプロセッシングエレメントと、
ソート制御情報を供給する制御情報出力手段と、
該制御情報出力手段から入力される前記ソート制御情報に基づいて、前記複数のプロセッシングエレメントのうちの、ペアとなる一方の前記プロセッシングエレメントの前記記憶手段の前記ソート対象データと前記ペアとなる他方の前記プロセッシングエレメントの前記記憶手段のソート対象データとを交換する前記プロセッシングエレメント毎のデータ交換手段とを備えることを特徴とするＳＩＭＤ型並列データ処理装置。
【請求項３】
前記制御情報出力手段は、第１のソート制御情報を供給する第１の制御情報出力手段及び第２のソート制御情報を供給する第２の制御情報出力手段を有し、前記データ交換手段は、第１のデータ選択手段及び第２のデータ選択手段を有し、前記第１のデータ選択手段は、前記第１のソート制御情報に基づいて前記ペアとなる前記プロセッシングエレメントの前記記憶手段のうちのいずれか一方の前記ソート対象データを選択して出力する手段であり、前記第２のデータ選択手段は、前記第２のソート制御情報に基づいて前記第１のデータ選択手段及び自己の前記プロセッシングエレメントの前記記憶手段ののうちのいずれか一方の前記ソート対象データを選択して自己の前記プロセッシングエレメントの前記記憶手段に供給する手段であることを特徴とする請求項２記載のＳＩＭＤ型並列データ処理装置。
【請求項４】
前記第１の制御情報出力手段は、前記複数のプロセッシングエレメントに接続される制御装置で実行される命令に基づいて前記第１のソート制御情報を生成して出力することを特徴とする請求項３記載のＳＩＭＤ型並列データ処理装置。
【請求項５】
前記複数のプロセッシングエレメントのうちの偶数プロセッシングエレメントの前記第２の制御情報出力手段は、自己の前記プロセッシングエレメントの前記記憶手段から出力される前記ソート対象データと、前記第１のデータ選択手段から出力される前記ソート対象データと、前記第１のソート制御情報と、前記第１のソート制御情報の生成と共に生成される第３のソート制御情報とに基づいて前記第２のソート制御情報を生成して出力することを特徴とする請求項３記載のＳＩＭＤ型並列データ処理装置。
【請求項６】
前記複数のプロセッシングエレメントのうちの奇数プロセッシングエレメントの前記第２の制御情報出力手段は、該奇数プロセッシングエレメントの両隣の前記プロセッシングエレメントで生成される前記第２のソート制御情報に基づいて第２のソート制御情報を生成して出力することを特徴とする請求項３記載のＳＩＭＤ型並列データ処理装置。
【請求項７】
前記第１のソート制御情報は、前記複数のプロセッシングエレメントを制御する制御プロセッサで実行される減算交換命令に予め埋め込められている動作指定情報であり、前記第３のソート制御情報は、前記減算交換命令に予め埋め込められている動作モードフラグ及び前記動作指定情報に基づいて設定されるマスク情報であることを特徴とする請求項５記載のＳＩＭＤ型並列データ処理装置。
【請求項８】
前記第２の制御情報出力手段は、減算論理回路と、動作モードフラグレジスタと、マスクレジスタとからなり、前記減算論理回路は、前記第１のデータ選択手段から出力される前記ソート対象データと、自己の前記プロセッシングエレメントの前記記憶手段の前記ソート対象データと、前記動作指定情報と、前記動作モードフラグレジスタの動作モードフラグと、前記マスクレジスタのマスク情報とに基づいて前記第２のソート制御情報を生成して出力する手段であることを特徴とする請求項７記載のＳＩＭＤ型並列データ処理装置。
【請求項９】
前記偶数プロセッシングエレメントのうちの、最初の偶数プロセッシングエレメントを除く前記偶数プロセッシングエレメントにおける前記マスク情報は、前記動作指定情報の如何に関係なしに第１の所定の情報として設定されるが、前記動作指定情報が予め決められる情報であるとき前記偶数プロセッシングエレメントのうちの、最初の偶数プロセッシングエレメントにおける前記マスク情報は、前記第１の所定の情報とは異なる情報として設定されることを特徴とする請求項８記載のＳＩＭＤ型並列データ処理装置。
【請求項１０】
制御情報出力手段からソート制御情報の供給を受け、
供給される前記ソート制御情報に基づいて、ソート対象データを記憶する記憶手段を有し、一次元結合された複数のプロセッシングエレメントのうちの所定のプロセッシングエレメント間で両プロセッシングエレメントの前記記憶手段のソート対象データを交換することを特徴とするＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１１】
制御情報出力手段からソート制御情報の供給を受け、
供給される前記ソート制御情報に基づいて、ソート対象データを記憶する記憶手段を有し、一次元結合された複数のプロセッシングエレメントのうちのペアとなる一方のプロセッシングエレメントと前記ペアとなる他方のプロセッシングエレメントとの間で両プロセッシングエレメントの前記記憶手段の前記ソート対象データを交換することを特徴とするＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１２】
前記制御情報出力手段は、第１及び第２のソート制御情報を出力し、前記第１のソート制御情報に基づいて前記ペアとなる前記プロセッシングエレメントの前記記憶手段ののうちのいずれか一方の前記ソート対象データを選択して出力し、前記第２のソート制御情報に基づいて選択出力された前記一方のソート対象データ及び前記ペアのうちの、自己の前記プロセッシングエレメントの前記記憶手段の前記ソート対象データのいずれか一方を選択して自己の前記プロセッシングエレメントの前記記憶手段に供給することを特徴とする請求項１１記載のＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１３】
前記第１のソート制御情報は、前記複数のプロセッシングエレメントに接続される制御装置で実行される命令に基づいて生成されることを特徴とする請求項１１記載のＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１４】
前記複数のプロセッシングエレメントのうちの偶数プロセッシングエレメントのための前記第２のソート制御情報は、自己の前記プロセッシングエレメントの前記記憶手段から出力される前記ソート対象データと、前記第１のソート制御情報に基づいて出力される前記ソート対象データと、前記第１のソート制御情報と、前記第１のソート制御情報の生成と共に生成される第３のソート制御情報とに基づいて生成されることを特徴とする請求項１２記載のＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１５】
前記複数のプロセッシングエレメントのうちの奇数プロセッシングエレメントのための前記第２のソート制御情報は、該奇数プロセッシングエレメントの両隣の前記プロセッシングエレメントで生成される前記第２のソート制御情報に基づいて生成されることを特徴とする請求項１２記載のＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１６】
前記第１のソート制御情報は、前記複数のプロセッシングエレメントを制御する制御プロセッサで実行される減算交換命令に予め埋め込められている動作指定情報であり、前記第３のソート制御情報は、前記減算交換命令に予め埋め込められている動作モードフラグ及び前記動作指定情報に基づいて設定されるマスク情報であることを特徴とする請求項１４記載のＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１７】
前記第２のソート制御情報は、前記第１のソート制御情報に基づいて出力される前記ソート対象データと、自己の前記プロセッシングエレメントの前記記憶手段の前記ソート対象データと、前記動作指定情報と、動作モードフラグと、マスク情報とに基づいて生成されることを特徴とする請求項１６記載のＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１８】
前記偶数プロセッシングエレメントのうちの最初の偶数プロセッシングエレメントを除く前記偶数プロセッシングエレメントにおける前記マスク情報は、前記動作指定情報の如何に関係なく第１の所定の情報として設定されるが、前記動作指定情報が予め決められる情報であるとき前記偶数プロセッシングエレメントのうちの、最初の偶数プロセッシングエレメントにおける前記マスク情報は、前記第１の所定の情報とは異なる情報として設定されることを特徴とする請求項１７記載のＳＩＭＤ型並列データ処理装置におけるデータソート方法。
【請求項１９】
ソート制御情報を受信する制御情報入力手段と、
該制御情報入力手段から出力される前記ソート制御情報に基づいて、一次元結合された複数のプロセッシングエレメントのうちの、所定の前記プロセッシングエレメントの記憶手段に設定されるソート対象データと自己の前記プロセッシングエレメントの前記記憶手段に設定されるソート対象データとを交換するデータ交換手段とを備えることを特徴とするプロセッシングエレメント。
【請求項２０】
ソート制御情報を受信する制御情報入力手段と、
該制御情報入力手段から出力される前記ソート制御情報に基づいて、一次元結合された複数のプロセッシングエレメントのうちの、ペアとなる一方の前記プロセッシングエレメントの記憶手段に設定されるソート対象データと前記ペアとなる他方の前記プロセッシングエレメントの前記記憶手段に設定されるソート対象データとを交換するデータ交換手段とを備えることを特徴とするプロセッシングエレメント。
【請求項２１】
前記制御情報入力手段は、第１のソート制御情報を供給する第１の制御情報供給手段及び第２のソート制御情報を供給する第２の制御情報供給手段を有し、前記データ交換手段は、第１のデータ選択手段及び第２のデータ選択手段を有し、前記第１のデータ選択手段は、前記第１のソート制御情報に基づいて前記ペアとなる前記プロセッシングエレメントの前記記憶手段のうちの、いずれか一方の前記ソート対象データを選択して出力する手段であり、前記第２のデータ選択手段は、前記第２のソート制御情報に基づいて前記第１のデータ選択手段及び自己の前記プロセッシングエレメントの前記記憶手段のうちのいずれか一方の前記ソート対象データを選択して自己の前記プロセッシングエレメントの前記記憶手段に供給する手段であることを特徴とする請求項２０記載のプロセッシングエレメント。
【請求項２２】
前記第１の制御情報入力手段は、前記複数のプロセッシングエレメントに接続される制御装置で実行される命令に基づいて生成される前記第１のソート制御情報を受信することを特徴とする請求項２０記載のプロセッシングエレメント。
【請求項２３】
前記プロセッシングエレメントが、前記複数のプロセッシングエレメントのうちの偶数プロセッシングエレメントであるとき、該偶数プロセッシングエレメントの前記第２の制御情報供給手段は、自己の前記プロセッシングエレメントの前記記憶手段から出力される前記ソート対象データと、前記第１のデータ選択手段から出力される前記ソート対象データと、前記第１のソート制御情報と、前記第１のソート制御情報の生成と共に生成される第３のソート制御情報とに基づいて前記第２のソート制御情報を生成して出力することを特徴とする請求項２１記載のプロセッシングエレメント。
【請求項２４】
前記プロセッシングエレメントが前記複数のプロセッシングエレメントのうちの、奇数プロセッシングエレメントであるとき、該奇数プロセッシングエレメントの前記第２の制御情報供給手段は、該奇数プロセッシングエレメントの両隣の前記プロセッシングエレメントで生成される前記第２のソート制御情報に基づいて第２のソート制御情報を生成して出力することを特徴とする請求項２１記載のプロセッシングエレメント。
【請求項２５】
前記第１のソート制御情報は、前記複数のプロセッシングエレメントを制御する制御プロセッサで実行される減算交換命令に予め埋め込められている動作指定情報であり、前記第３のソート制御情報は、前記減算交換命令に予め埋め込められている動作モードフラグ及び前記動作指定情報に基づいて設定されるマスク情報であることを特徴とする請求項２３記載のプロセッシングエレメント。
【請求項２６】
前記第２の制御情報供給手段は、減算論理回路と、動作モードフラグレジスタと、マスクレジスタとからなり、前記減算論理回路は、前記第１のデータ選択手段から出力される前記ソート対象データと、自己の前記プロセッシングエレメントの前記記憶手段の前記ソート対象データと、前記動作指定情報と、前記動作モードフラグレジスタの動作モードフラグと、前記マスクレジスタのマスク情報とに基づいて前記第２のソート制御情報を生成して出力する手段であることを特徴とする請求項２５記載のプロセッシングエレメント。
【請求項２７】
前記偶数プロセッシングエレメントのうちの、最初の偶数プロセッシングエレメントを除く前記偶数プロセッシングエレメントにおける前記マスク情報は、前記動作指定情報の如何に関係なしに第１の所定の情報として設定されるが、前記動作指定情報が予め決められる情報であるとき前記偶数プロセッシングエレメントのうちの最初の偶数プロセッシングエレメントにおける前記マスク情報は、前記第１の所定の情報とは異なる情報として設定されることを特徴とする請求項２６記載のプロセッシングエレメント。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＳＩＭＤ型並列データ処理装置及びＳＩＭＤ型並列データ処理装置におけるデータソート方法並びにプロセッシングエレメントに関し、詳しくは、ソート処理を改良したＳＩＭＤ型並列データ処理装置及びＳＩＭＤ型並列データ処理装置におけるデータソート方法並びにプロセッシングエレメントに関する。
【背景技術】
【０００２】
ビデオ信号等の画像処理においては、従来からＳＩＭＤ（Single Instruction Multiple Data）型並列計算装置（ＳＩＭＤ型並列プロセッサ）を用いることが知られている。このＳＩＭＤ型計算装置は、複数のプロセッシングエレメント（Processing Element）ＰＥと制御プロセッサとから概略構成される。その一次元ＳＩＭＤ型並列計算装置の電気的構成をブロック図で示せば図２のようになる。一次元ＳＩＭＤ型並列計算装置の全ＰＥに１つずつ数値データを設定し、それら数値データからなる数値データの集合を昇順又は降順にソートする方法としては、いわゆる「奇偶変換ソート方式」が有効であることが知られている。【０００３】
この奇偶変換ソート方式をＳＩＭＤ型並列計算装置に適用して数値データの集合のソートを行う場合に、ＰＥ数をｎとし、入力数値データ列Ｓ＝｛x(0),ｘ(1)，…，ｘ(n-1)｝とし、ｘ(i)がＰＥ(i)に割り付けられているとすると、先ず、第１ステップでは、各偶数番目のＰＥ(i)がその右隣のＰＥ(i+1)からｘ(i+1)のコピーを受け取り、そしてもしもｘ(i)>ｘ(i+1) ならば、ＰＥ(i)及びＰＥ(i+1)は保持している数値データｘ(i)とｘ(i+1)とを交換する。
次に、第２ステップでは、最左端となっている番号０のＰＥを除く各偶数番目のＰＥ(i)がその左隣のＰＥ(i-1)からｘ(i-1)を受け取り、ｘ(i-1)>ｘ(i) ならば、ＰＥ(i-1)及びＰＥ(i)は保持している数値データｘ(i)とｘ(i-1)とを交換する。【０００４】
これらの２ステップを逐次に反復実行することにより、最大（ｎ＋１）／２回の反復後に、それ以上数値データの交換は起こらず、入力数値データ列Ｓのソートは完成する。
図４に、奇偶変換ソート方式を適用したＳＩＭＤ型並列計算装置でのソート例を示す。このソート例は、ＰＥ数を７とし、降順の数値データ７、６、５、４、３、２、１を昇順の数値データにソートする例で、そのソートは、上述した２つのステップを合わせたソート動作を１回の反復とみなした場合に、その反復を繰り返すことで昇順の数値データ１、２、３、４、５、６、７を得るようにしている。【０００５】
非特許文献１には、上述した２つのステップ（１回の反復）を一次元ＳＩＭＤ型並列計算装置において実現する関連技術が記載されている。この関連技術は、各ＰＥが一般的な命令セットでしか処理を実行し得ない場合において、上述の奇偶変換ソート方式をその装置に実装するため、それぞれ異なる形で相隣り合う２つのＰＥをペア（対）として取り扱った上、そのペア内で互いに異なる動作を行わせる仕組みを採用している。
すなわち、例えば、昇順にソートする場合には、第１ステップでは偶数ＰＥが小さい値を受け取る一方、当該偶数ＰＥとペアとなる右隣のＰＥ（奇数ＰＥ）が大きい値を受け取り、そして第２ステップでは上記偶数ＰＥが大きい値を受け取る一方、当該偶数ＰＥとペアとなる左隣のＰＥ（奇数ＰＥ）が大きい値を受け取る、というような動作を生じさせ、所定のソートを得ようとするものである。【０００６】
しかしながら、ＰＥペア内に、上述したような互いに異なる動作（上述の第１ステップの動作Ａと第２ステップの動作Ｂ）を行わせようとすると、同一の命令ストリームに従って動作する一次元ＳＩＭＤ型並列計算装置の場合には、一般的に、ＰＥを動作不動作に指定するマスクレジスタ（ｍｒ）（以下、ｍｒ＝１が動作を、また、ｍｒ＝０が不動作を表すとする）を用いて、動作Ａを指定する命令コードが制御プロセッサ（ＣＰ）から放送されている間は、一方のＰＥのｍｒを１とし他方のＰＥのｍｒを０とするのに対して、動作Ｂを指定する命令コードがＣＰから放送されている間は、一方のＰＥのｍｒを０とし他方のＰＥのｍｒを１とするように設定する。
すなわち、ｍｒの値をＰＥ毎にその都度変更し、かつ、動作Ａと動作Ｂとに対応する命令コードをそれぞれＣＰから放送しなければならない。【０００７】
このことを非特許文献１に記載される関連技術について、具体的に言えば、上述した第１ステップ及び第２ステップの処理を遂行するのに以下に述べる７つのシーケンスを辿ることになる。この７つのシーケンスは次のようになる。
その第１のシーケンス１）は、全ＰＥが右隣ＰＥの数値データを自ＰＥへ転送する、第２のシーケンス２）は、１）での転送で獲得した数値データと自ＰＥ上の数値データとの大小比較（引き算）を行う、第３のシーケンス３）は、偶数ＰＥのみを動作させるようにｍｒを１に設定する、第４のシーケンス４）は、ｍｒ＝１のＰＥ（偶数ＰＥ）は引き算結果のキャリフラグの値が１ならば、２）にて右隣ＰＥから届いた数値データを自ＰＥの数値データに代入する、第５のシーケンス５）は、全ＰＥが「自ＰＥの数値データ」及び「キャリフラグの値とｍｒとの論理積の値」を右隣ＰＥへ転送する、第６のシーケンス６）は、全ＰＥでｍｒを反転させて偶数ＰＥを不動作、奇数ＰＥを動作に設定する、第７のシーケンス７）は、動作の設定となった奇数ＰＥは、今度は上記５）により自ＰＥに転送されて来た論理積の値が１ならば、５）にて転送されて来た数値データを自ＰＥの数値データに代入する。【０００８】
上述した１）〜７）のシーケンスを辿ることにより、ようやく奇偶変換ソート方式における第１ステップの処理が実現する。
これと同様に、奇偶変換ソート方式における第２ステップの処理も実現することができる。そのためには、上述した１）〜７）での「右隣」を「左隣」に、また、３）の「偶数PEのみ」を「最左端ＰＥを除く偶数ＰＥのみ」に読み替えた上で、１）〜７）のシーケンスを辿るように構成する必要がある。【０００９】
特許文献１には、ＳＩＭＤ型マイクロプロセッサについて関連技術が記載されている。この関連技術は、複数のプロセッサエレメントをＳＩＭＤ型マイクロプロセッサにおいて、各プロセッサエレメントの特定のレジスタに格納されるデータと、オペランド指示されたソースレジスタに格納されるデータとの大小比較を第１のインストラクションで行い、両データのうちの大きいデータを上記特定のレジスタに格納する一方、小さいデータをソースレジスタに格納するか若しくはソースレジスタ以外のオペランド指示されたディスティネーションレジスタに格納し、更に、各プロセッサエレメントの特定のレジスタに格納されるデータと、オペランド指示されたソースレジスタに格納されるデータとの大小比較を第２のインストラクションで行い、両データのうちの小さいデータを上記特定のレジスタに格納する一方、大きいデータをソースレジスタに格納するか若しくはソースレジスタ以外のオペランド指示されたディスティネーションレジスタに格納し、上記格納のためのソースレジスタ及びディスティネーションレジスタとしてプロセッサエレメントのソートバッファレジスタを用いるように構成し、データのソート処理を高速に行う技術に係るものである。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００７−１０２７９９号公報
【非特許文献】
【００１１】
【非特許文献１】京  昭倫著「１２８個の４ウェイVLIW型RISCコアを集積した車載向け動画認識ＬＳＩ」電子情報通信学会研究会報告、集積回路研究会（ICD），２００３年５月、Vol.103,No.89,pp.19-24
【発明の概要】
【発明が解決しようとする課題】
【００１２】
ところで、上述した非特許文献１では、一次元結合ＳＩＭＤ型並列計算装置において奇偶変換ソート方式を実行するように構成すれば、ｎ個の数値データを最大（ｎ＋１）／２回の反復でソートすることはできる。
しかしながら、１回の反復毎に多くの命令実行でそのソートを行えるに過ぎず、処理時間が長く、効率が悪いという技術的課題がある。
また、特許文献１は、複数のプロセッサエレメントをＳＩＭＤ型マイクロプロセッサにおける各プロセッサエレメント毎でのソート処理を行う仕組みを取り入れており、複数のプロセッサエレメントの中の他のプロセッサエレメントとの関係については何ら触れるところはない。
したがって、ソート処理の効率化において、なお解決すべき問題がある。【００１３】
この発明は、上述の事情に鑑みてなされたもので、ソート対象データの効率良いソートを達成し得るＳＩＭＤ型並列データ処理装置及びＳＩＭＤ型並列データ処理装置におけるデータソート方法並びにプロセッシングエレメントを提供することを目的としている。
【課題を解決するための手段】
【００１４】
上記課題を解決するために、この発明の第１の構成は、ソート対象データのソートを行うＳＩＭＤ型並列データ処理装置に係り、ソート対象データを記憶する記憶手段を有し、一次元結合された複数のプロセッシングエレメントと、ソート制御情報を供給する制御情報出力手段と、該制御情報出力手段から入力される上記ソート制御情報に基づいて、上記複数のプロセッシングエレメントのうちの所定の１つのプロセッシングエレメントの上記記憶手段の上記ソート対象データと所定の他のプロセッシングエレメントの上記記憶手段の上記ソート対象データとを交換するプロセッシングエレメント毎のデータ交換手段とを備えることを特徴としている。【００１５】
この発明の第２の構成は、ＳＩＭＤ型並列データ処理装置におけるデータソート方法に係り、制御情報出力手段からソート制御情報の供給を受け、供給される上記ソート制御情報に基づいて、ソート対象データを記憶する記憶手段を有し、一次元結合された複数のプロセッシングエレメントのうちの所定のプロセッシングエレメント間で両プロセッシングエレメントの上記記憶手段のソート対象データを交換することを特徴としている。【００１６】
この発明の第３の構成は、ＳＩＭＤ型並列データ処理装置に用いるプロセッシングエレメントに係り、ソート制御情報を受信する制御情報入力手段と、該制御情報入力手段から出力される上記ソート制御情報に基づいて、一次元結合された複数のプロセッシングエレメントのうちの所定の上記プロセッシングエレメントの記憶手段に設定されるソート対象データと自己の上記プロセッシングエレメントの上記記憶手段に設定されるソート対象データとを交換するデータ交換手段とを備えることを特徴としている。
【発明の効果】
【００１７】
この発明によれば、減算交換命令を単純な演算の少ない組み合わせで実現させているので、奇偶変換ソート方式の各ステップを単一マシンサイクルで実装することが可能になる。したがって、ハードウェアコストの増加を僅かに抑えつつ、奇偶変換ソート方式に基づくデータのソート処理を効率良く実現することが可能になる。
【図面の簡単な説明】
【００１８】
【図１】図１は、この発明の実施形態１であるＳＩＭＤ型並列プロセッサの電気的構成の主要部を示すブロック図である。
【図２】同ＳＩＭＤ型並列プロセッサの電気的構成全体を示すブロック図である。
【図３】同ＳＩＭＤ型並列プロセッサのプロセッシングエレメントで用いる減算論理回路のブロック図である。
【図４】同ＳＩＭＤ型並列プロセッサのプロセッシングエレメント数とソート対象データ数が同一である場合の動作説明図である。
【図５】この発明の実施形態２であるＳＩＭＤ型並列プロセッサのプロセッシングエレメント数がソート対象データ数よりも少ない場合の動作説明図である。
【発明を実施するための形態】
【００１９】
この出願は、２００９年１月１３日に出願された日本出願特願２００９−００４３８０を基礎とする優先権を主張し、その開示の全てがここに取り込まれている。
【実施形態１】
【００２０】
図１は、この発明の実施形態１であるＳＩＭＤ型並列プロセッサの電気的構成の主要部を示すブロック図、図２は、同ＳＩＭＤ型並列プロセッサの電気的構成全体を示すブロック図、図３は、同ＳＩＭＤ型並列プロセッサのプロセッシングエレメントで用いる減算論理回路のブロック図、図４は、同ＳＩＭＤ型並列プロセッサのプロセッシングエレメント数とソート対象データ数が同一である場合の動作説明図である。
この実施形態のＳＩＭＤ型並列プロセッサ１０は、奇偶変換ソート方式の第１ステップ及び第２ステップの各各を単一のマシンサイクルで実行し得る装置に係り、その主要部は、図１に示すように、複数のプロセッシングエレメントが一次元結合された（双方向にリング状に接続された）複数のプロセッシングエレメント（以下、ＰＥと略記する）１１ｉ（ｉ＝０、１、２、…、Ｎのうちの１つ）で構成され、さらに、これらのＰＥからなるＰＥアレイに命令をＰＥ間結合線３０（図２）を介して放送する制御プロセッサ（ＣＰ）４０（図２）を有し、制御プロセッサ４０で実行される命令セット内に以下に説明する減算交換命令をプログラムしてその減算交換命令の実行でＰＥアレイを制御して所定のソート処理を達成し得るようにしてその全体が構成されている。
【００２１】
その減算交換命令の機能は、概括的に言えば、次の通りである。上述した偶奇変換ソート方式における第１ステップを実行するのに１つの減算交換命令を用いて該命令の実行で生成される交換決定情報（交換決定ビット）xchg=１なら自ＰＥのソート対象データをその右隣のＰＥのソート対象データで更新すると同時に、該右隣のＰＥのソート対象データを上記自ＰＥのソート対象データで更新し、次いで、上述した偶奇変換ソート方式における第２ステップを実行するのにもう１つの減算交換命令を用いて該命令の実行で生成される交換決定ビットxchg=１なら自ＰＥのソート対象データをその左隣のＰＥのソート対象データで更新すると同時に、左隣のＰＥのソート対象データを自ＰＥのソート対象データで更新するという動作を生じさせることにある。
上記減算交換命令には、後述する動作指定情報Ｉ及び動作モードフラグflgが予め埋め込められている。
【００２２】
次に、今説明した動作を行うＰＥ１１ｉの各各の構成について説明する。
ＰＥ１１ｉのいずれも、レジスタ（src）１２ｉ、セレクタ１４ｉ及びセレクタ１６ｉを有して構成される。以下の説明では、ｉは偶数番目を表すものとする。
これに加えて、偶数番目のＰＥ１１ｉには、さらに、減算論理回路２０ｉ、動作モードフラグ（flg）レジスタ２２ｉ及びマスクレジスタ（mr）２４ｉが設けられる一方、奇数番目のＰＥ１１ｉ−１及びＰＥ１１ｉ＋１には、さらに、セレクタ１８ｉ−１及びセレクタ１８ｉ＋１が設けられて構成されている。
【００２３】
偶数番目のＰＥ１１ｉのセレクタ１４ｉ及び減算論理回路２０ｉのセレクタ２０３ｉ（後述）、並びに奇数番目のＰＥ１１ｉ−１及びＰＥ１１ｉ＋１のセレクタ１４ｉ−１、セレクタ１４ｉ＋１、セレクタ１８ｉ−１及びセレクタ１８ｉ＋１の各選択制御入力に、制御プロセッサ４０からＰＥ間結合線３０を介して動作指定信号（動作指定ビットともいう）Ｉが供給される。
【００２４】
偶数番目のＰＥ１１ｉのレジスタ１２ｉには、セレクタ１６ｉの出力が接続されている。セレクタ１４ｉには、左隣のＰＥ１１ｉ−１の出力（レジスタ１２ｉ−１の出力）及び右隣のＰＥ１１ｉ＋１の出力（レジスタ１２ｉ＋１の出力）が接続されてそのいずれか一方がそこに入力される動作指定信号Ｉの値に応じて選択的に出力されるように構成されている。偶数番目のＰＥ１１ｉのセレクタ１６ｉには、レジスタ１２ｉ及びセレクタ１４ｉの出力が接続され、セレクタ１６ｉの選択制御入力に減算論理回路２０ｉのから出力される交換決定信号（交換決定ビットともいう）xchgが選択制御信号２１ｉとして入力され、選択制御信号２１ｉの値に応じてレジスタ１２ｉ又はセレクタ１４ｉの数値データが選択されて出力されるように構成されている。
【００２５】
奇数番目のＰＥ１１ｉ−１及びＰＥ１１ｉ＋１のレジスタ１２ｉ−１及びレジスタ１２ｉ＋１には、それぞれ、セレクタ１６ｉ−１及びレジスタ１６ｉ＋１の出力が接続されている。セレクタ１４ｉ−１には、左隣のＰＥ１１ｉ−２の出力（レジスタ１２ｉ−２の出力）及び右隣のＰＥ１１ｉの出力（レジスタ１２ｉの出力）が接続されてそのいずれか一方がそこに入力される動作指定信号Ｉの値に応じて選択的に出力されるように構成されている。また、セレクタ１４ｉ＋１には、左隣のＰＥ１１ｉの出力（レジスタ１２ｉの出力）及び右隣のＰＥ１１ｉ＋２の出力（レジスタ１２ｉ＋２の出力）が接続されてそのいずれか一方がそこに入力される動作指定信号Ｉの値に応じて選択的に出力されるように構成されている。
【００２６】
また、奇数番目のＰＥ１１ｉ−１及びＰＥ１１ｉ＋１のセレクタ１６ｉ−１及びセレクタ１６ｉ＋１の選択制御入力には、セレクタ１８ｉ−１及びセレクタ１８ｉ＋１から出力される交換決定信号が選択制御信号１９ｉ−１及び選択制御信号１９ｉ＋１として供給される。
ここで、レジスタ１２ｉ−１から出力される数値データをsrc-left１２Ｌで表し、レジスタ１２ｉ＋１から出力される数値データをsrc-right１２Ｒで表すのに用いるが、また、src-left１２Ｌ及びsrc-right１２Ｒなる表記は、着目しているＰＥを基準として左側のＰＥのレジスタの数値データにもsrc-left１２Ｌを、また、右側のＰＥのレジスタの数値データにもsrc-right１２Ｒを用いることとする。
【００２７】
偶数番目のＰＥ１１ｉのセレクタ１４ｉ及びセレクタ１６ｉの選択動作は次の通りである。
セレクタ１４ｉは、例えば、動作指定ビットＩの値が１ならば、src-right１２Ｒを、また、動作指定ビットＩの値が０ならば、src-left１２Ｌを選択して出力する。
セレクタ１６ｉは、例えば、選択制御信号２１ｉの値が０ならば、セレクタ１４ｉの数値データをレジスタ１２ｉへ選択して出力してレジスタ１２ｉの更新を行い、また、選択制御信号２１ｉの値が１ならば、レジスタ１２ｉの数値データをレジスタ１２ｉへ選択出力する、つまり更新は行わない。
偶数番目のＰＥ１１ｉのセレクタ１４ｉ及びセレクタ１６ｉの選択動作について説明したところは、奇数番目のセレクタ１４ｉ−１、セレクタ１４ｉ＋１及びセレクタ１６ｉ−１、セレクタ１６ｉ＋１にも同等に当て嵌まる。
【００２８】
ＰＥ１１ｉ−１及びＰＥ１１ｉ＋１のセレクタ１８ｉ−１及びセレクタ１８ｉ＋の選択動作は次の通りである。
セレクタ１８ｉ−１及びセレクタ１８ｉ＋１には、両隣の偶数ＰＥの減算論理回路、すなわち、減算論理回路２０ｉ−２及び減算論理回路２０ｉ＋２の出力に接続され、動作指定ビットＩの値に応じて上記２つの減算論理回路２０ｉ−２及び２０ｉ＋２から出力される交換決定ビットxchg-left２０Ｌ及びxchg-right２０Ｒのいずれか一方を選択して選択制御信号１９ｉ−１及び選択制御信号１９ｉ＋１として出力するように構成されている。セレクタ１８ｉ−１及びセレクタ１８ｉ＋１は、例えば、動作指定ビットＩの値が０ならば、xchg-right２０Ｒを、また、動作指定ビットＩの値が１ならば、xchg-left２０Ｌを選択して出力する。
セレクタ１８ｉ−１及びセレクタ１８ｉ＋１から選択して出力される信号は、各別に、当該奇数番目のＰＥに設けられるセレクタ１６ｉ−１及びセレクタ１６ｉ＋１の選択制御入力に選択制御信号１９ｉ−１及び選択制御信号１９ｉ＋１として供給される。
【００２９】
減算論理回路２０ｉは、レジスタ１２ｉ及びセレクタ１４ｉからの数値データと、動作指定ビットＩと、動作モードフラグ（flg）レジスタ２２ｉからの動作モードフラグ（flg）及びマスクレジスタ（mr）２４ｉからのマスク値とに基づいて交換決定信号（ビット）xchgを生成する回路であり、図３に示すように、減算回路（ＳＵＢ）２０１ｉ、反転回路（ＮＯＴ）２０２ｉ、セレクタ２０３ｉ、排他的論理和回路（ＸＯＲ）２０４ｉ及び論理積回路（ＡＮＤ）２０５ｉから構成される。交換決定信号xchgは自ＰＥ１１ｉのセレクタ１６ｉの選択制御入力に供給される選択制御信号２１ｉとして用いられる。
【００３０】
減算回路２０１ｉには、レジスタ１２ｉ及びセレクタ１４ｉの出力が接続され、セレクタ２０３ｉには、減算回路２０１ｉ及び反転回路２０２ｉの出力が接続されてそのいずれか一方がそこに入力される動作指定ビットＩの値に応じて選択的に出力されるように構成されている。例えば、セレクタ２０３ｉへの動作指定ビットＩが１のとき、減算回路２０１ｉからの出力信号（キャリーフラグcf）を選択し、また、動作指定信号Ｉが０のとき、反転回路２０２ｉからの出力信号を選択する。排他的論理和回路２０４ｉには、セレクタ２０３ｉ及び動作モードフラグ（flg）レジスタ２２ｉの出力が接続され、論理積回路２０５ｉには、排他的論理和回路２０４ｉ及びマスクレジスタ（mr）２４ｉの出力が接続されている。論理積回路２０５ｉからの出力信号が、ＰＥ１１ｉで生成される交換決定信号xchgとなる。
【００３１】
動作モードフラグ（flg）レジスタ２２ｉは、動作モードフラグ（flg）を記憶するレジスタであり、動作モードフラグはソートの種別を表すフラグである。動作モードフラグ（flg）は、減算交換命令が制御プロセッサ４０で実行されるときにＰＥ間結合線３０を介して偶数ＰＥに放送されて動作モードフラグ（flg）レジスタ２２ｉにセットされる。
マスクレジスタ（mr）２４ｉは、減算交換命令が制御プロセッサ４０で実行されるときにＰＥ間結合線３０を介して偶数ＰＥに放送される動作指定ビットＩの値に応じて設定される。例えば、動作指定信号Ｉの値が１ならば、偶数ＰＥのマスクレジスタ（mr）２４ｉに１が自動的にセットされるのに対して、動作指定信号Ｉの値が０ならば、最左端のＰＥ１１0のマスクレジスタ２４０に０が自動的にセットされ、また、そのほかの偶数ＰＥのマスクレジスタ２４ｉには１が自動的にセットされる。マスク値は、ＰＥの動作不動作を指定する情報である。
【００３２】
次に、図１乃至図４を参照して、この実施形態の動作について説明する。
ＳＩＭＤ型並列プロセッサ１０は、そのＰＥの数が７で構成され、ＳＩＭＤ型並列プロセッサ１０におけるデータ処理において、これらのＰＥ１１ｉ（ｉ＝０，１，…，６のうちの１つ）のレジスタ（src）１２ｉに図４に示すような降順の数値データ７、６、５、４、３、２、１が設定されるものとし、これらの数値データを昇順の数値データにソートする場合について説明する。以下においては、便宜上、ＰＥ１１０乃至ＰＥ１１６をＰＥ０乃至ＰＥ６として表すことにする。
そして、上記データ処理を行うプログラムの中で上記ソート処理の第１ステップを行う第１の減算交換命令には、動作指定信号Ｉの値として１が、また、動作モードフラグflgの値として０が予め設定されている。また、上記ソート処理の第２ステップを行う第２の減算交換命令には、動作指定信号Ｉの値として０が、また、動作モードフラグflgの値として０が予め設定されている。
なお、この第１ステップでは、その第１の減算交換命令に動作指定信号Ｉの値として１を予め設定するとしているが、動作指定信号Ｉの値として０を予め設定しても、同様の結果が得られる。
【００３３】
上記第１の減算交換命令が実行されると、各ＰＥには１の動作指定信号Ｉが供給され、偶数ＰＥｉの動作モードフラグレジスタ２２ｉには０の動作モードフラグflgが設定される。
そして、動作指定信号Ｉの値は１であるから、偶数ＰＥのマスクレジスタ（mr）２４ｉに１が自動的にセットされる。
【００３４】
上述のステップ１の処理において、ＰＥ０のレジスタ１２０に設定されている数値データは７である一方、動作指定信号の値は１であるから、セレクタ１４０から出力される数値データは、src-right(=6)となる。したがって、減算論理回路２００の減算回路２０１０から１のキャリーフラグcfが出力される。
このステップ１では、動作モードフラグレジスタ２２０には、既に、０の動作モードフラグflgtが設定されており、セレクタ２０３０は、１の動作指定信号Ｉにより１のキャリーフラグcfを選択して出力しているから、排他的論理和回路２０４０から１の信号が出力される。また、このステップ１では、マスクレジスタ２４０には、既に、１のマスク情報mrが設定されているから、論理積回路２０５０から１の交換決定信号xchgを出力する。
【００３５】
減算論理回路２００から出力される１の交換決定信号xchgは、ＰＥ０では１の選択制御信号２１０としてＰＥ０のセレクタ１６０へ供給される。そのセレクタ１６０はセレクタ１４０から出力されている数値データ、このステップ１では６を選択して出力する。この数値データ（＝６）は、レジスタ１２０に書き込まれる。
【００３６】
一方、ＰＥ０の右隣のＰＥ１では、ＰＥ０からの１の交換決定信号xchgがセレクタ１８１へ入力されるが、このステップ１ではそこに供給される動作指定信号Ｉの値も１であるから、セレクタ１８１で選択する交換決定信号xchgは、xchg-rightではなく、xchg-leftを選択するから、ＰＥ１での選択制御信号１９１も１となる。この１の選択制御信号１９１がセレクタ１６１に供給される。セレクタ１６１に入力される２つの数値データは、セレクタ１４１から出力されるsrc-left（すなわち、レジスタ１２０に設定されている数値データ７）とレジスタ１２１の数値データである。セレクタ１６１は、１の選択制御信号１９１により、src-left１２Ｌ、すなわち、数値データ７を選択する。その数値データ７がレジスタ１２１に書き込まれる。
【００３７】
他方、ＰＥ０の左隣となる最右端のＰＥ（この設例ではＰＥ６）では、ＰＥ０で生成された１の交換決定信号xchgは、最右端のＰＥ６ではxchg-rightとなるが、ＰＥ６の動作指定信号Ｉの値も１であるから、ＰＥ６のセレクタ１８６ではxchg-rightは選択されず、したがって最右端のＰＥ６のレジスタ１２６への書き込み値は、ＰＥ０から出力される交換決定信号xchgの値によっては影響されない。
【００３８】
このステップ１におけるＰＥ２での動作を説明すると次のようになる。
ＰＥ２のレジスタ１２２に設定されている数値データは５である一方、動作指定信号Ｉの値は１であるから、セレクタ１４２から出力される数値データは、ＰＥ３から出力されるsrc-right(=４)となる。したがって、減算論理回路２０２の減算回路２０１２から１のキャリーフラグcfが出力される。
このステップ１では、動作モードフラグレジスタ２２２には、既に、０の動作モードフラグflgtが設定されており、セレクタ２０３２は、動作指定信号Ｉが１であることにより、１のキャリーフラグcfを選択して出力しているから、排他的論理和回路２０４２から１の信号が出力される。このステップ１では、マスクレジスタ２４２には、既に、１のマスク情報mrが設定されているから、論理積回路２０５２から１の交換決定信号xchgを出力する。
【００３９】
減算論理回路２０２から出力される１の交換決定信号xchgは、ＰＥ２では１の選択制御信号２１２としてＰＥ２のセレクタ１６２へ供給される。そのセレクタ１６２は、選択制御信号２１２が１であることにより、セレクタ１４２から出力されている数値データ、このステップ１ではＰＥ３のレジスタ１２３の数値データ（すなわち、src-right１２Ｒ）４を選択して出力する。この数値データ（＝４）は、レジスタ１２２に書き込まれる。
【００４０】
一方、ＰＥ２の右隣のＰＥ３では、このステップ１ではそこに供給される動作指定信号Ｉの値も１であるから、セレクタ１８３で選択する交換決定信号xchgは、xchg-rightではなく、xchg-leftを選択するから、ＰＥ３での選択制御信号１９３も１となる。この１の選択制御信号１９３がセレクタ１６３に供給される。このとき、セレクタ１４３は動作指定信号Ｉが１であることにより、そこに入力されるsrc-left、すなわち、レジスタ１２２に設定されている数値データ５を選択して出力する。そして、セレクタ１６３は、選択制御信号１９３が１であることにより、セレクタ１４３から出力される数値データ５を選択して出力する。その数値データ５がレジスタ１２３に書き込まれる。
【００４１】
他方、ＰＥ２の左隣のＰＥ１では、ＰＥ２で生成された交換決定信号xchgは、ＰＥ１ではxchg-rightとなるが、ＰＥ１の動作指定信号Ｉの値も１であるから、ＰＥ１のセレクタ１８１ではxchg-rightは選択されず、したがってＰＥ１のレジスタ１２１への書き込み値は、ＰＥ２から出力される交換決定信号xchgの値によっては影響されない。
【００４２】
そして、ＰＥ０及びＰＥ２とこれら左右隣のＰＥについて説明した動作が、ＰＥ４とこの左右隣のＰＥに対しても、同様にして、ステップ１の処理のためにプログラムされた第１の減算交換命令の実行の中で同時的に生ぜしめられる。したがって、その逐一の説明は省略する。
また、ＰＥ６においては、交換決定信号xchgは、ＰＥ０及びＰＥ２について説明したところに従うと１になり、したがって、セレクタ１６６への選択制御信号２１６は１になるから、セレクタ１６６でレジスタ１２６の数値データ、ここでは１が選択されてその数値データがレジスタ１２６に書き込まれる。レジスタ１２６の数値データは変更されない。
第１回目の反復におけるステップ１の処理が完了したときの状態を図４に示す。そのソート状態は、図４では、第１回目の反復（１st iteration）の中の第１のステップ（Step１）を示す横欄に示すようになる。すなわち、ＰＥ０、ＰＥ１、ＰＥ２、ＰＥ３、ＰＥ４、ＰＥ５及びＰＥ６に保持される数値データは、それぞれ、６、７、４、５、２、３及び１となる。
【００４３】
上述したステップ１の処理に続いて第１回目の反復におけるステップ２の処理が開始される。このステップ２のための第２の減算交換命令が、上述したプログラムの中で第１の減算交換命令に続いて置かれている。この第２の減算交換命令に設定される動作指定信号Ｉは０に設定される。動作モードフラグflgの値は、第１の減算交換命令と同様、０に設定される。
【００４４】
ステップ２の処理に入り、第２の減算交換命令が制御プロセッサ４０で実行されるときの、ＰＥ０のレジスタ１２０に既に設定されている数値データは６である一方、動作指定信号Ｉの値は０であるから、セレクタ１４０から出力される数値データは、最右端のＰＥ(ＰＥ６)から出力されるsrc-left(=１)となる。したがって、減算論理回路２００の減算回路２０１０から１のキャリーフラグcfが出力される。
【００４５】
第２の減算交換命令でも、動作モードフラグレジスタ２２０には、既に、０の動作モードフラグflgが設定されており、動作指定信号Ｉの値は０であるから、セレクタ２０３０は１のキャリーフラグcfを反転して出力する反転回路２０３０の出力信号値０を選択して出力するので、排他的論理和回路２０４０から０の信号（０の排他的論理和）が出力される。
【００４６】
そして、動作指定信号Ｉの値が０である場合には、偶数ＰＥのうち、最左端のＰＥであるＰＥ０に限り、マスクレジスタ２４０には、既に、０のマスク情報mrが設定されているから、キャリーフラグcfと動作モードフラグflgとの排他的論理和の値が１となったとしても、排他的論理和とマスク情報ｍｒとの論理積は必ず０となる。したがって、減算論理回路２００が出力する交換決定信号xchgは、常に０となる。
【００４７】
その０の交換決定信号xchgが、選択制御信号２１０としてＰＥ０のセレクタ１６０へ供給される。そのセレクタ１６０はレジスタ（src）１２０から出力されている数値データ、ここでは６を選択して出力する。この数値データ（＝６）がレジスタ１２０に書き込まれるので、レジスタ１２０の数値データは変更されない。
【００４８】
一方、ＰＥ０の右隣のＰＥ１では、第２のステップではそこに供給される動作指定信号Ｉの値も０であるから、セレクタ１８１で選択する交換決定信号xchgは、xchg-leftではなく、xchg-rightを選択するから、ＰＥ１での選択制御信号２１１も１となる。この１の選択制御信号２１１の生成も、ステップ１で説明したところに準じて行われる。
この１の選択制御信号２１１がセレクタ１６１に供給されるから、セレクタ１６１は、セレクタ１４１からの数値データを選択して出力する。セレクタ１４１で選択される数値データは、ステップ１の処理でＰＥ２のレジスタ１６２に設定された数値データ、ここでは４である。この数値データ４がレジスタ１２１に書き込まれる。
【００４９】
他方、ＰＥ０の左隣となる最右端のＰＥ（この設例ではＰＥ６）では、ＰＥ０で生成された０の交換決定信号xchgは、最右端のＰＥ６ではxchg-rightとなり、ＰＥ６の動作指定信号Ｉの値も０であるから、ＰＥ６のセレクタ１８６から０のxchg-rightが選択され、その０の選択制御信号２１６がセレクタ１６６へ供給される。このとき、セレクタ１４６は、src-left、すなわち、レジスタ１２５の数値データ３を選択して出力する。したがって、最右端のＰＥ６では、セレクタ１６６でレジスタ１２５の数値データ、ここでは３が選択されてレジスタ１２６へ供給されてそこに書き込まれる。
【００５０】
第１回目の反復におけるステップ２の中で生ずるＰＥ２での動作を説明すると次のようになる。
ＰＥ２のレジスタ１２２に設定されている数値データは４である一方、動作指定信号Ｉの値は０であるから、セレクタ１４２から出力される数値データは、ＰＥ１から出力されるsrc-left(=７)となる。したがって、減算論理回路２０２の減算回路２０１２から０のキャリーフラグcfが出力される。
このステップ２においても、動作モードフラグレジスタ２２２には、既に、０の動作モードフラグflgが設定されており、セレクタ２０３２が０のキャリーフラグcfを反転回路２０２２で反転した１の信号を選択して出力しているから、排他的論理和回路２０４２から１の信号が出力される。このステップ２でも、マスクレジスタ２４２には、既に、１のマスク情報mrが設定されているから、論理積回路２０５２から１の交換決定信号xchgを出力する。
【００５１】
減算論理回路２０２から出力される１の交換決定信号xchgは、ＰＥ２では１の選択制御信号２１２としてＰＥ２のセレクタ１６２へ供給される。また、上述したように動作指定信号Ｉとして０がセレクタ１４２に供給されているから、セレクタ１４２は、src-leftの数値データであるＰＥ１のレジスタ１２１に設定されている数値データ、すなわち、７を選択して出力する。
したがって、セレクタ１６２はセレクタ１４２から出力されている数値データ（＝７）を選択して出力する。この数値データ（＝７）は、レジスタ１２２に書き込まれる。
【００５２】
一方、ＰＥ２の右隣のＰＥ３では、このステップ２ではそこに供給される動作指定信号Ｉの値も０であるから、セレクタ１８３で選択する交換決定信号xchgは、xchg-leftではなく、xchg-rightを選択するから、ＰＥ３の動作は、ＰＥ２から出力される交換決定信号xchgには影響されない。
ＰＥ３で用いられる選択制御信号としは、上述のようにして選択されたxchg-right、すなわち、上述のところに準じて処理されて出力される０の交換決定信号が用いられる。このとき、セレクタ１４３が選択するのは、src-rightである。そして、０の選択制御信号がセレクタ１６３に供給されるから、セレクタ１６３から選択出力する数値データは、セレクタ１４３から出力されるsrc-right、すなわち、レジスタ１２４に設定されている数値データ２である。この数値データ２がレジスタ１２３に書き込まれる。
【００５３】
他方、ＰＥ２の左隣のＰＥ１では、ＰＥ２で生成された交換決定信号xchgは、ＰＥ１ではxchg-rightとなるが、ＰＥ１の動作指定信号Ｉの値も０であるから、ＰＥ１のセレクタ１８１では１のxchg-rightが選択されると共に、セレクタ１４１でもsrc-right、すなわち、ＰＥ２のレジスタ１２２に設定されている数値データ（＝４）を選択する。
したがって、ＰＥ１のレジスタ１２１の書き込み値は、数値データ（＝４）となり、レジスタ１２１の数値データは、４に書き換わる。
【００５４】
そして、ＰＥ０、ＰＥ１、ＰＥ２及びＰＥ３について説明した動作が、ＰＥ４、ＰＥ５及びＰＥ６でも、同様にして、ステップ２の処理のためにプログラムされた第２の減算交換命令の実行の中で同時的に生ぜしめられる。したがって、それらの逐一の説明は省略する。
第１回目の反復の中のステップ２の処理が完了したときの状態を図４に示す。そのソート状態は、図４では、第１回目の反復の中の第２のステップ（Step２）を示す横欄に示すようになる。すなわち、ＰＥ０、ＰＥ１、ＰＥ２、ＰＥ３、ＰＥ４、ＰＥ５及びＰＥ６に保持される数値データは、それぞれ、６、４、７、２、５、１及び３となる。
【００５５】
上述した第１回目の反復の実行により、各ＰＥに初期的に設定保持される数値データの入れ替え（交換）がＰＥ間で行われる。
同様の数値データの入れ替えが、第２回目の反復以降でも行われる。それらの反復により、上述した数値データ例の場合には、図４に示すように、４回の反復で昇順のソート処理が完了する、すなわち、それ以上の数値データの入れ替え動作は発生しないことが判る。
このソート状態、すなわち、全ＰＥのレジスタ（src）の数値データが変化しなくなったことを、制御プロセッサ４０が検知して減算交換命令の発行ループから抜け出して実行中のプログラムの次の処理に進むようにすればよい。
【００５６】
なお、上記実施形態では、動作モードフラグ（flg）が０である、すなわち、昇順で数値データをソートする例について説明したが、動作モードフラグ（flg）が１である、すなわち、降順で数値データをソートし得ることは、上記の説明から自明となるところであるので、その逐一の説明は省略する。
【００５７】
前述の減算交換命令の発行ループから抜け出すプログラム処理を以下に説明する。
上述のＳＩＭＤ型並列プロセッサ１０で使用可能な命令セットには、減算交換命令以外に、ＰＥ上で第１オペランドが指定するレジスタ値を第２オペランドが指定するレジスタへ転送する命令ＭＶと、ＰＥ上で第１オペランドが指定するレジスタ値と第２オペランドが指定するレジスタ値とを減算しその結果を第３オペランドが指定するレジスタに格納すると共に、減算結果が０ならゼロフラグに１を設定する命令ＳＵＢと、第１オペランドが指定する種類のＰＥ上の条件フラグの値の全ＰＥに渡る論理和として得られる１ビット情報を制御プロセッサ（ＣＰ）上のマスクレジスタに格納する動作を指定する命令ＳＴＳと、制御プロセッサ上のマスクレジスタの値が１ならば分岐せず０ならば分岐する動作を指定する条件分岐命令ＢＲＮＭとが存在することを必要とする。
【００５８】
これらの条件に加えて、プログラムの記述の中での“．．”なる記述は、その両隣の命令が同一サイクルに動作することを指定することを意味し、／＊／＊で囲まれた部分や／／以降行末までをコメントとする。また、：で終る文字列は、当該文字列の出現位置の番地を示し、分岐命令のオペランドとして同ラベルを指定した場合は、同番地を意味するものとする。
また、src,origは、ＰＥ上でデータを格納するレジスタの識別子とし、ソート対象となるＰＥ数に等しい個数のデータが１個ずつ各ＰＥのレジスタ（src）に格納されており、かつ制御プロセッサＰＣ上のマスクレジスタの値は前もって０にセットされているとする。その他、減算交換命令（SUBXCHG命令）に対する第１オペランドとして動作指定信号Ｉの値を、第２オペランドとしてソート対象データを格納するデータレジスタの識別子srcを指定するものとする。また、この例では、ソート対象データを昇順でソートすることを想定しているので、動作モードフラグ（flg）レジスタに０が設定されているとする。
【００５９】
次に、上記条件に従うプログラムの例を記述する。
ＡＧＡＩＮ：
／＊番地Ａ＋０＊／SUBXCHG命令 １，src．．／＊番地Ａ＋１＊／MV src,orig／／step１を実行すると共にsrcの元の値を退避する
／＊番地Ａ＋２＊／SUBXCHG命令 ０，src／／step２を実行する
／＊番地Ａ＋３＊／SUBXCHG命令 １，src．．／＊番地Ａ＋４＊／SUB   src,orig／／step１を実行すると共にsrcの値と元の値とを比較する
／＊番地Ａ＋５＊／SUBXCHG命令 ０，src．．／＊番地Ａ＋６＊／STS   ％Ｚ／／step２を実行すると共に、比較結果のゼロフラグをＣＰへ送付する
／＊番地Ａ＋７＊／SUBXCHG命令 １，src／／step１を実行する
／＊番地Ａ＋８＊／BRNM
AGAIN．．／＊番地Ａ＋９＊／SUBXCHG命令
０，src／／step２を実行すると共に、比較結果のゼロフラグをＣＰへ送付する
／＊番地Ａ＋１０＊／
【００６０】
このプログラムコードの場合、／＊番地Ａ＋１＊／のMV命令により srcの値がレジスタ（orig）にコピーされる。／＊番地Ａ＋３＊／〜／＊番地Ａ＋９＊／のループでは、繰り返し毎にSUBXCHG命令を計６回発行し、ソート処理の反復回数としては３反復を実施している中で、同時に各ＰＥ上でSUB命令を発行することでsrc値とorig値とが同一、すなわち、反復を一度実施しても、srcの値に変化が現れなかったかどうかの判定が行われ、かつ、ＳＴＳ命令を用いることで当該判定結果を表す条件フラグＺの値の全ＰＥに渡る論理和がＣＰ上のマスクレジスタに格納され、論理和が０、すなわち、srcの値に変化が現れた場合、／＊番地Ａ＋８＊／BRNMの実行に際し分岐が成立し、次サイクルには／＊番地Ａ＋１０＊／ではなく／＊番地Ａ＋０＊／へ飛ぶように動作する。
【００６１】
一方、論理和が１、すなわち、srcの値に変化が現れなかった場合は、分岐を行わずに／＊番地Ａ＋１０＊／へ進み、ループから抜け出す。
このようにループ終了判定を行う間でも、毎サイクルで減算交換命令を発行することができるため、減算交換命令を繰り返すループを抜けるためのＣＰによる終了判定処理は、全体の処理サイクル数に最小限の影響のみしか与えないようにすることができる。
【００６２】
このように、この実施形態によれば、減算交換命令を単純な演算の少ない組み合わせで実現させているので、減算交換命令を持たない、例えば、上述の「非特許文献」に記載されているＳＩＭＤ型並列計算装置において減算交換命令相当の処理を行うのに７程度のマシンサイクルが掛かるのに対して、上記実施形態では奇偶変換ソート方式の各ステップを単一マシンサイクルで実装することが可能になる。したがって、減算交換命令を有するＳＩＭＤ型並列計算装置では、ハードウェアコストの増加を僅かに抑えつつ、奇偶変換ソート方式に基づくデータのソート処理を効率良く実現することが可能になる。
【実施形態２】
【００６３】
図５は、この発明の実施形態２であるＳＩＭＤ型並列プロセッサのプロセッシングエレメント数がソート対象データ数よりも少ない場合の動作説明図である。
この実施形態の構成が、実施形態１のそれと大きく異なる点は、ソート対象となるデータ数がＰＥ数よりも多くてもソート処理全体を高速化し得るようにした点である。
この実施形態のＳＩＭＤ型並列プロセッサは、その各ＰＥに２つ以上のソート対象データを割り当てた上で、それらソート対象データについてのソート処理を「ＰＥ内での」奇偶変換ソート処理と「ＰＥ間での」奇偶変換ソート処理とに分け、後者の奇偶変換ソート処理について実施形態１で説明した奇偶変換ソート処理を実施してソート処理全体の高速化を達成するようにして構成される。
【００６４】
例えば、図５の動作説明図では、ＰＥ数を７とし、そのＰＥ数の倍に当たる１４個の数値データのソートを行う例を示している。図５中の（１）のマークでは同一ＰＥ内（ＰＥinternal）でのデータ交換では、従来のＰＥアレイが有する命令セットを利用して実現する一方、図５中の（２）及び（３）のマークでは、ＰＥ間のデータ交換を実施形態１で説明したデータ交換を利用して実現する。なお、図５中の（２）及び（３）のマークで示すデータ交換は、順次的でも、また、同時的で実施してもよい。
【００６５】
上述したデータ交換によれば、ＰＥ間のデータ交換を効率良く実現できない従来のＳＩＭＤ型並列計算装置に比して、奇偶変換方式に基づくソート処理をより高速に行うことができる。
【００６６】
以上、この発明の実施形態を、図面を参照して詳述してきたが、この発明の具体的な構成は、これらの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計の変更等があってもそれらはこの発明に含まれる。
例えば、実施形態１及び実施形態２では、ソート対象データとして、数値データを例にして説明したが、これに限らず、データの順序性を有するその他のデータについてのソートにも、この発明を適用し得る。
また、実施形態１及び実施形態２では、動作指定情報Ｉ及び動作モードフラグflgは、減算交換命令に予め埋め込められている例について説明したが、減算交換命令より前に実行される所要の命令の実行時に設定保持しておき、減算交換命令の実行時に保持されている各情報を対応する記憶保持手段、例えば、レジスタにセットしてこの発明のソート処理に用いるようにしてこの発明を実施することも可能である。
また、実施形態１及び実施形態２では、動作指定情報Ｉ、動作モードフラグflg及びマスク値ｍｒの値を１又は０とする例について説明したが、その他の所定の値としてもよい。
【産業上の利用可能性】
【００６７】
ここに開示しているＳＩＭＤ型並列データ処理装置及びＳＩＭＤ型並列データ処理装置におけるデータソート方法並びにプロセッシングエレメントは、データのソートを必要とする各種のデータ処理装置に利用し得る。
【符号の説明】
【００６８】
１０      ＳＩＭＤ型並列プロセッサ（ＳＩＭＤ型並列データ処理装置）
１１０〜１１６      プロセッシングエレメント
１４０〜１４６      セレクタ（データ交換手段の一部、第１のデータ選択手段）
１６０〜１６６      セレクタ（データ交換手段の残部、第２のデータ選択手段）
２００、２０２、…、２０６      減算論理回路（制御情報出力手段の一部、第２の制御情報供給手段）
３０      ＰＥ間結合線（制御情報入力手段、第１の制御情報供給手段）
４０      制御プロセッサ（制御情報出力手段の残部）
【図１】
0005445469.tif 000002
【図２】
0005445469.tif 000003
【図３】
0005445469.tif 000004
【図４】
0005445469.tif 000005
【図５】
0005445469.tif 000006