(57)【特許請求の範囲】
【請求項１】
複数の要素を含む第一ベクトルデータと、前記第一ベクトルデータと同じ数の要素を含む第二ベクトルデータとを使用して、前記第一ベクトルデータに含まれる要素と、前記第二ベクトルデータに含まれる要素とを、対応する要素ごとに比較し、その比較結果に基づいて、前記第一ベクトルデータと前記第二ベクトルデータの一方の要素を選択し、選択された要素で構成される第三ベクトルデータを生成するベクトル比較選択手段と、
前記第一ベクトルデータに含まれる各要素に対応するインデックスを含む第一インデックス・ベクトルと、前記第二ベクトルデータに含まれる各要素に対応するインデックスを含む第二インデックス・ベクトルと、前記比較結果とを使用して、前記比較結果に基づいて、前記第一インデックス・ベクトルと前記第二インデックス・ベクトルの一方の要素を選択し、選択された要素で構成される第三インデックス・ベクトルを生成するインデックス・ベクトル選択手段と、
前記第一ベクトルデータの最初の要素に対応する開始インデックスに基づいて、前記第一インデックス・ベクトルを生成し、前記インデックス・ベクトル選択手段へ出力するインデックス・ベクトル生成手段と、
前記開始インデックスに基づいて、次の開始インデックスを算出する更新手段と
を備え、
前記インデックス・ベクトル生成手段は、スケールファクタと入力データ数とを含む制御信号を受け取り、前記開始インデックスへ前記スケールファクタの数値の倍数を加算して、前記入力データ数のインデックスを生成し、生成したインデックスを結合して前記第一インデックス・ベクトルを生成する並列比較選択演算装置。
【請求項２】
前記ベクトル比較選択手段は、
前記第一ベクトルデータに含まれる一つの要素と前記第二ベクトルデータに含まれる一つの要素とを比較し、その比較結果に基づいて、二つの要素の一方を選択する複数の要素比較選択手段を備えること、
を特徴とする請求項１記載の並列比較選択演算装置。
【請求項３】
前記ベクトル比較選択手段は、前記第一ベクトルデータの要素の数と等しい数の要素比較選択手段を備え、
前記ベクトル比較選択手段は、
前記第一ベクトルデータを複数の要素に分割し、分割した複数の要素を前記複数の要素比較選択手段へ出力する第一ベクトル分割手段と、
前記第二ベクトルデータを複数の要素に分割し、分割した複数の要素を前記複数の要素比較選択手段へ出力する第二ベクトル分割手段と、
前記複数の要素比較選択手段が選択する要素を結合して前記第三ベクトルデータを生成するベクトル結合手段と、をさらに備えること、
を特徴とする請求項２記載の並列比較選択演算装置。
【請求項４】
前記インデックス・ベクトル選択手段は、
前記第一ベクトルデータに含まれる一つの要素に対応するインデックス、及び前記第二ベクトルデータに含まれる一つの要素に対応するインデックスを使用して、前記要素比較選択手段が生成した比較結果に基づいて、二つのインデックスの一方を選択する複数のインデックス選択手段を備えること、
を特徴とする請求項２または３記載の並列比較選択演算装置。
【請求項５】
前記インデックス・ベクトル選択手段は、
前記第一インデックス・ベクトルを複数のインデックスに分割し、前記複数のインデックス選択手段へ出力する第一インデックス分割手段と、
前記第二インデックス・ベクトルを複数のインデックスに分割し、前記複数のインデックス選択手段へ出力する第二インデックス分割手段と、
前記複数のインデックス選択手段が選択するインデックスを結合して前記第三インデックス・ベクトルを生成するインデックス結合手段と、をさらに備えること、
を特徴とする請求項４記載の並列比較選択演算装置。
【請求項６】
前記ベクトル比較選択手段は、前記複数の要素比較選択手段が生成した比較結果を結合し、比較結果ベクトルを生成する比較結果結合手段を備え、
前記インデックス・ベクトル選択手段は、前記比較結果ベクトルに含まれる複数の要素比較結果を前記複数のインデックス選択手段に出力する比較結果分割手段を備えること、
を特徴とする請求項４または５記載の並列比較選択演算装置。
【請求項７】
請求項１乃至６のいずれか一項に記載の並列比較選択演算装置を備えるプロセッサ。
【請求項８】
複数の要素を含む第一ベクトルデータと、前記第一ベクトルデータと同じ数の要素を含む第二ベクトルデータと、前記第一ベクトルデータの最初の要素に対応する開始インデックスを含む第一インデックス情報と、前記第二ベクトルデータに含まれる各要素に対応するインデックスで構成された第二インデックス・ベクトルと、スケールファクタと入力データ数とを含む制御信号とを使用して、
前記第一ベクトルデータに含まれる要素と、前記第二ベクトルデータに含まれる要素とを、対応する要素ごとに比較し、
比較結果に基づいて、前記第一ベクトルデータと前記第二ベクトルデータの一方の要素を選択し、
選択された要素で構成される第三ベクトルデータを生成し、
前記比較結果と、前記第一インデックス情報と、前記第二インデックス・ベクトルとに基づいて、前記第三ベクトルデータに含まれる各要素に対応するインデックスを選択し、
選択された複数のインデックスで構成される第三インデックス・ベクトルを生成し、
前記開始インデックスに基づいて、前記開始インデックスへ前記スケールファクタの数値の倍数を加算して、前記入力データ数のインデックスを生成し、前記第一ベクトルデータの各要素に対応するインデックスで構成された第一インデックス・ベクトルを生成し、
前記第三ベクトルデータの各要素に対応するインデックスを、前記比較結果に基づいて、前記第一インデックス・ベクトルと前記第二インデックス・ベクトルから選択すること、
を特徴とする並列比較選択演算方法。
【請求項９】
前記開始インデックスに基づいて、次の開始インデックスを算出すること、
を特徴とする請求項８記載の並列比較選択演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最大値あるいは最小値とそのインデックスを高速に探索可能なＳＩＭＤ（Single Instruction Multiple Data）型並列比較選択演算装置あるいはプロセッサに関する。
【背景技術】
【０００２】
ＳＩＭＤ命令とは複数のデータに対して同一の演算を並列に実行する命令である。一般的に、演算に使用される複数のデータは一つのレジスタに格納される。レジスタに格納された複数のデータの一つ一つはサブワードと呼ばれる。一つのレジスタに格納されるサブワードの一般的な数は２Ｎ個である。代表的なＳＩＭＤ命令として、レジスタに格納された４つのサブワードを使った加算演算を実行するＳＩＭＤ命令が考えられる。ＳＩＭＤ命令は画像処理のようなたくさんのデータを並列に処理できるような性質を持つアプリケーションに適している。【０００３】
たくさんのデータの中から最も大きな値を探す処理や最も小さな値を探す処理を考える。最大値あるいは最小値の探索処理に適したＳＩＭＤ命令を備えるプロセッサが非特許文献１、２に紹介されている。例えば非特許文献２のＰｏｗｅｒＰＣ（登録商標）のＶＭＡＸＳＷという命令は、二つの入力ベクトルデータの対応する位置にある要素を比較して、大きい方を選択し、選択した要素からなるベクトルデータを出力する。ＶＭＡＸＳＷのような命令は最大値だけを探す場合には便利であるが、最大値とそのインデックスを探したい場合には役に立たない。【０００４】
たくさんのデータの中から最大値とそのインデックスとを求めるには、（１）データを現在の最大値と比較する処理と、（２）比較結果に基づいて現在の最大値を置き換える処理と、（３）比較結果に基づいて現在のインデックスを置き換える処理と、を繰返し実行する。従来のプロセッサのＶＭＡＸＳＷのような命令は処理（１）と（２）を実行できるが、処理（３）を実行することができない。そのため、プロセッサは、処理（１）を命令Ａで、処理（２）を命令Ｂで、処理（３）を命令Ｃで、というように、処理（１）から（３）をそれぞれ別々の命令で実行する。【０００５】
例えば、ＰｏｗｅｒＰＣというプロセッサでは、処理（１）にはＶＣＭＰＧＴＳＷ（非特許文献２参照）という命令を使用し、処理（２）と（３）にはそれぞれＶＳＥＬという命令を使用する。ＶＣＭＰＧＴＳＷは二つのベクトルデータを比較し、比較結果に応じて０あるいは−１を出力する命令である。ＶＳＥＬは制御情報に基づいて二つのベクトルデータのどちらかを１ビットごとに選択する命令である。ＶＳＥＬのような命令がない場合には、論理積演算と論理和演算を使ってＶＳＥＬと等価な処理を行なう。ＰｏｗｅｒＰＣにおける処理例を示したが、他の従来のプロセッサでも同じことが言える。つまり、従来のプロセッサは処理（１）から（３）をそれぞれ個別の命令で実行するために、処理（１）から（３）を実行するためのステップ数が多くなってしまう。【０００６】
また、特許文献１には、順序づけられた一連のベクトルデータを入力として、このベクトルデータの中の最大値または最小値とこの最大値または最小値に対応した要素番号とを検索し出力するベクトルデータ検索装置が開示されている。しかしながら、特許文献１に開示された技術は、複数個の要素を同時に比較する演算器を用いるものであり、入力の数に応じた演算器を必要としていた。このため、三以上の入力がある場合、入力数に応じた多入力の比較演算器を使用する必要があった。また、三以上の多入力の比較演算器は、二入力の比較演算器を使用する場合に比べ処理遅延が生じていた。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特公平８−３３８１０号公報
【非特許文献】
【０００８】
【非特許文献１】FreescaleTM semiconductor, "AltiVecTM Technology Programming Environments Manual", AltiVec Instructions, ALTIVECPEM, Rev.3, April, 2006, Page index 6-61 (173rd page from the top) of Chapter 6
【非特許文献２】FreescaleTM semiconductor, "AltiVecTM Technology Programming Environments Manual", AltiVec Instructions, ALTIVECPEM, Rev.3, April, 2006, Page index 6-75 (187th page from the top) of Chapter 6
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従来のプロセッサでは、インデックスをともなう最大値探索あるいは最小値探索を効率良く実行できないという課題があった。
そこで、本発明は、インデックスをともなう最大値探索あるいは最小値探索を効率良く実行する並列比較選択演算装置及びその方法を提供することを目的の一つとする。
【課題を解決するための手段】
【００１０】
本発明に係る並列比較選択演算装置の一態様は、複数の要素を含む第一ベクトルデータと、前記第一ベクトルデータと同じ数の要素を含む第二ベクトルデータとを使用して、前記第一ベクトルデータ及び前記第二ベクトルデータに含まれる各要素を対応する要素ごとに比較し、その比較結果に基づいて、前記第一ベクトルデータと前記第二ベクトルデータの一方の要素を選択し、選択された要素で構成される第三ベクトルデータを生成するベクトル比較選択ユニットと、前記第一ベクトルデータに含まれる各要素に対応するインデックスを含む第一インデックス・ベクトルと、前記第二ベクトルデータに含まれる各要素に対応するインデックスを含む第二インデックス・ベクトルと、前記比較結果とを使用して、前記比較結果に基づいて、前記第一インデックス・ベクトルと前記第二インデックス・ベクトルの一方の要素を選択し、選択された要素で構成される第三インデックス・ベクトルを生成するインデックス・ベクトル選択ユニットと、を備える。【００１１】
また、本発明に係るプロセッサの一態様は、上述した並列比較選択演算装置を備える。【００１２】
さらに、本発明に係る並列比較選択演算方法の一態様は、複数の要素を含む第一ベクトルデータと、前記第一ベクトルデータと同じ数の要素を含む第二ベクトルデータと、前記第一ベクトルデータのインデックスに関する第一インデックス情報と、前記第二ベクトルデータに含まれる各要素に対応するインデックスで構成された第二インデックス・ベクトルとを使用して、前記第一ベクトルデータ及び前記第二ベクトルデータに含まれる各要素を対応する要素ごとに比較し、比較結果に基づいて、前記第一ベクトルデータと前記第二ベクトルデータの一方の要素を選択し、選択された要素で構成される第三ベクトルデータを生成し、前記比較結果と、前記第一インデックス情報と、前記第二インデックス・ベクトルとに基づいて、前記第三ベクトルデータに含まれる各要素に対応するインデックスを選択し、選択された複数のインデックスで構成される第三インデックス・ベクトルを生成すること、を特徴とする。
【発明の効果】
【００１３】
本発明によれば、インデックスをともなう最大値探索あるいは最小値探索を効率良く実行することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の模範的な実施形態におけるプロセッサの構成を示す図である。
【図２】プロセッサの第一の実施形態における並列比較選択演算ユニットの構成例を示す図である。
【図３】図２の並列比較選択演算ユニットのベクトル比較選択ユニットの構成例を示す図である。
【図４】図２の並列比較選択演算ユニットなどで使用される分割ユニットの構成例を示す図である。
【図５】図２の並列比較選択演算ユニットなどで使用される結合ユニットの構成例を示す図である。
【図６Ａ】図３のベクトル比較選択ユニットで使用される比較選択ユニットの構成例を示す図である。
【図６Ｂ】図６Ａの比較選択ユニットの比較ユニットの動作を示す図である。
【図６Ｃ】図６Ａの比較選択ユニットの選択ユニットの動作を示す図である。
【図７】図２の並列比較選択演算ユニットあるいは図１５の並列比較選択演算ユニットで使用されるインデックス・ベクトル選択ユニットの構成例を示す図である。
【図８】本発明の模範的な実施形態における最大値あるいは最小値の探索処理の概念を表す図である。
【図９】図８の概念に基づいて最大値あるいは最小値の探索処理を、本発明の模範的な実施形態で実行するためのフローチャートを表す図である。
【図１０】第一の実施形態における図９のフローチャートのｓｔｅｐ１の具体的な処理内容を表す図である。
【図１１】第一の実施形態における図９のフローチャートのｓｔｅｐ５の具体的な処理内容を表す図である。
【図１２】第一の実施形態において、図２の並列比較選択演算ユニットを動作させるための命令として利用可能な命令を表す図である。
【図１３】第一の実施形態において、プロセッサが、１６ビットの１６個のデータから最大値あるいは最小値とそのインデックスを求めるようすを表す図である。
【図１４】図９のフローチャートのｓｔｅｐ６の具体的な処理例を表す図である。
【図１５】プロセッサの第二の実施形態における並列比較演算ユニットの構成例を示す図である。
【図１６Ａ】図１５の並列比較選択演算ユニットで使用されるインデックス・ベクトル生成ユニットの構成例を示す図である。
【図１６Ｂ】図１６Ａのインデックス・ベクトル生成ユニットの制御信号の意味を示す図である。
【図１７Ａ】図１５の並列比較選択演算ユニットで使用される更新ユニットの構成例を示す図である。
【図１７Ｂ】図１７Ａの更新ユニットの制御信号とｓｔｅｐとの関係を示す図である。
【図１８】第二の実施形態における図９のフローチャートのｓｔｅｐ１の具体的な処理内容を表す図である。
【図１９】第二の実施形態における図９のフローチャートのｓｔｅｐ４とｓｔｅｐ５の具体的な処理内容を表す図である。
【図２０】第二の実施形態において、図１５の並列比較選択演算ユニットを動作させるための命令として利用可能な命令を表す図である。
【図２１】第二の実施形態において、プロセッサが、１６ビットの１６個のデータから最大値あるいは最小値とそのインデックスを求めるようすを表す図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について、図面を参照しながら説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略、及び簡略化がなされている。各図面において同一の構成または機能を有する構成要素および相当部分には、同一の符号を付し、その説明は省略する。
以下の説明において、ベクトルデータは、複数の要素（データ）の集合である。また、インデックス・ベクトルは、ベクトルデータに含まれる各要素の番号（要素番号）の集合である。ベクトルデータの中の要素（データ）の番号をインデックスと呼ぶことにする。
【００１６】
本発明の実施の形態について図面を参照して説明する。図１を参照すると、本発明の模範的な実施形態は、プロセッサ２００と、メモリ（記憶ユニット）１００とを含む。プロセッサ２００は、命令デコーダ２１０と、命令実行ユニット２２０と、レジスタバンク（一時記憶ユニット）２３０と、並列比較選択演算ユニット（並列比較選択演算装置）２４０と、を備える。メモリ１００にはプロセッサ２００のためのプログラムやデータが格納される。プログラムは複数の命令から構成される。レジスタバンク２３０は複数のレジスタをもつ。メモリ１００における命令の読み出しアドレスを格納するためのプログラムカウンタもレジスタバンク２３０に含まれる。
【００１７】
命令デコーダ２１０は、クロック信号に同期して、レジスタバンク２３０に存在するプログラムカウンタが示すアドレスを使ってメモリ１００から命令を読み込み、その命令をデコードし、命令実行ユニット２２０あるいは並列比較選択演算ユニット２４０へ命令の命令コードや入力オペランドや出力などの情報を伝える。命令デコーダ２１０がどちらのユニットへ情報を伝えるかは命令コードに依存する。命令コードが並列比較選択演算ユニット２４０で実行される演算を表すならば、その命令コードなどの情報は並列比較選択演算ユニット２４０へ伝えられる。さらに、命令デコーダ２１０はその命令の語長をレジスタバンク２３０に存在するプログラムカウンタへ加算する。
【００１８】
命令デコーダ２１０から与えられた命令コードやオペランドなどの情報に基づいて、命令実行ユニット２２０は入力オペランドの内容をレジスタバンク２３０あるいはメモリ１００から読み込み、命令コードに対応する演算を実行し、演算結果を出力オペランドであるレジスタバンク２３０あるいはメモリ１００へ書き込む。
【００１９】
並列比較選択演算ユニット２４０を除くと、命令デコーダ２１０と命令実行ユニット２２０とレジスタバンク２３０とメモリ１００は一般的なプロセッサシステムの構成要素である。
並列比較選択演算ユニット２４０は、ベクトルデータとそれに対応するインデックス・ベクトルに関する比較と選択を実行する。並列比較選択演算ユニット２４０は、入力となるベクトルデータとインデックス・ベクトルをレジスタバンク２３０から読み込む。並列比較選択演算ユニット２４０の出力データはベクトルデータとインデックス・ベクトルであり、並列比較選択演算ユニット２４０はそれらをレジスタバンク２３０へ書き込む。
【００２０】
（第一の実施形態）
図２を参照しながら、第一の実施形態における並列比較選択演算ユニット２４０を説明する。第一の実施形態の並列比較選択演算ユニット２４０は、ベクトル比較選択ユニット２４２と、インデックス・ベクトル選択ユニット２４３と、で構成される。第一の実施形態における並列比較選択演算ユニット２４０の入力信号は、命令デコーダ２１０から入力される制御信号と、レジスタバンク２３０から入力される四つのデータである。この四つのデータとは、ベクトルデータ１（第一ベクトルデータ）、ベクトルデータ２（第二ベクトルデータ）、インデックス・ベクトル１（第一インデックス・ベクトル）、インデックス・ベクトル２（第二インデックス・ベクトル）、である。第一の実施形態における並列比較選択演算ユニット２４０の出力信号は、ベクトルデータ３（第三ベクトルデータ）と、インデックス・ベクトル３（第三インデックス・ベクトル）と、である。
【００２１】
ベクトル比較選択ユニット２４２は、ベクトルデータ１とベクトルデータ２とを比較し、その比較結果を比較結果ベクトルとしてインデックス・ベクトル選択ユニット２４３へ出力するとともに、比較結果に基づいてベクトルデータ１とベクトルデータ２とから適切な要素を選択し、選択した要素をベクトルデータ３として出力する。
【００２２】
インデックス・ベクトル選択ユニット２４３は、ベクトル比較選択ユニット２４２から与えられた比較ベクトルに基づいて、インデックス・ベクトル１とインデックス・ベクトル２から適切な要素を選択し、選択した要素をインデックス・ベクトル３として出力する。
【００２３】
図３を参照しながら、ベクトル比較選択ユニット２４２を説明する。ベクトル比較選択ユニット２４２は、二つの分割ユニット１０、１１と、二つの結合ユニット２０、２１と、複数の比較選択ユニット３０〜３３と、で構成される。図３は比較選択ユニットの数が４個の場合を表している。ベクトル比較選択ユニット２４２の入力信号は、命令デコーダ２１０からの制御信号と、レジスタバンク２３０からのベクトルデータ１とベクトルデータ２と、である。ベクトル比較選択ユニット２４２の出力信号は、比較結果ベクトルと、ベクトルデータ３と、である。
【００２４】
一方の分割ユニット（第一ベクトル分割ユニット）１０は、ベクトルデータ１を受けとり、制御信号に基づいてベクトルデータ１をいくつかの要素に分割し、それらを一つずつ比較選択ユニット３０〜３３へ出力する。分割ユニット１０への制御信号は分割数を表す。同様に、もう一方の分割ユニット（第二ベクトル分割ユニット）１１は、ベクトルデータ２を受けとり、制御信号に基づいてベクトルデータ２をいくつかの要素に分割し、それらを一つずつ比較選択ユニット３０〜３３へ出力する。図３では、分割ユニット１０は、ベクトルデータ１とベクトルデータ２のそれぞれを四つの要素に分割し、各要素を比較選択ユニット３０〜３３へ送る。
【００２５】
比較選択ユニット３０〜３３は、制御信号と、一方の分割ユニット１０から与えられた要素ａと、もう一方の分割ユニット１１とから与えられた要素ｂと、に基づいて、比較結果ｃと選択要素ｘとを出力する。すなわち、比較選択ユニット３０〜３３それぞれは、制御信号に基づいて、ベクトルデータ１及びベクトルデータ２のＰ番目（Ｐは０以上の整数）の二つの要素を比較する。図３において、Ｐは、要素ａ（ａ０〜ａ３）、要素ｂ（ｂ０〜ｂ３）に付加されている数値０〜３と一致する。
一方の結合ユニット（ベクトル結合ユニット）２１は、比較選択ユニット３０〜３３から与えられた選択要素ｘを複数個結合して、それをベクトルデータ３として出力する。もう一方の結合ユニット（比較結果結合ユニット）２０は、複数の比較選択ユニット３０〜３３から与えられた比較結果ｃを複数個結合して、それを比較結果ベクトルとして出力する。図３では、一方の結合ユニット２０は四つの比較選択ユニット３０〜３３から与えられた要素ｘ０、ｘ１、ｘ１、ｘ２、ｘ３を結合し、それをベクトルデータ３として出力し、もう一方の結合ユニット２１は四つの比較選択ユニット３０〜３３から与えられた比較結果ｃ０、ｃ１、ｃ２、ｃ３を結合し、それを比較結果ベクトルとして出力している。
【００２６】
本明細書では、異なる符号をつけた同じ名称の構成要素、例えば、分割ユニット１０〜１４で示す複数の分割ユニットは、同様の機能を有する。また、結合ユニット２０〜２３、比較選択ユニット３０〜３３についてもそれぞれ同じ名称の構成要素は同様の機能を有する。さらに、後述する選択ユニット４０〜４４、比較ユニット５０についても同様である。以降の説明において、各構成要素を一つの符号を用いて、説明することがある（例えば、図４の分割ユニット１０など）。
【００２７】
図４を参照しながら、分割ユニット１０を説明する。分割ユニット１０は、制御信号ｄｎｕｍ（ｄｎｕｍ＞０の整数）に基づいて、ｍ（ｍ＞０の整数）ビットの入力データをｄｎｕｍ個の（ｍ／ｄｎｕｍ）ビットのデータへ分割する。制御信号ｄｎｕｍは分割後のデータの数を表す。図４では、制御信号ｄｎｕｍは４であり、分割ユニット１０がｍビットの入力データを四つの（ｍ／４）ビットのデータへ分割する様子を表している。
【００２８】
図５を参照しながら、結合ユニット２０を説明する。結合ユニット２０は、制御信号ｄｎｕｍに基づいて、ｄｎｕｍ個のｎ（ｎ＞０の整数）ビットの入力データを（ｄｎｕｍ＊ｎ）ビットのデータへ結合する。制御信号ｄｎｕｍは結合前のデータの数を表す。図５では、制御信号ｄｎｕｍは４であり、結合ユニット２０がｎビットの四つの入力データを一つの（４＊ｎ）ビットのデータへ結合する。
【００２９】
図６Ａ、６Ｂ、６Ｃを参照しながら、比較選択ユニット３０を説明する。図６Ａに示すように、比較選択ユニット３０は、選択ユニット４０と、比較ユニット５０と、で構成される。比較選択ユニット３０の入力信号は、制御信号ｃｍｏｄｅと、データａと、データｂと、である。比較選択ユニット３０の出力信号は、選択データｘと、比較結果ｃと、である。比較ユニット５０は、制御信号ｃｍｏｄｅに基づいてデータａとデータｂとを比較し、比較結果ｃを出力する。
【００３０】
制御信号ｃｍｏｄｅと比較式と比較結果の関係は図６Ｂの表に示す通りである。比較ユニット５０への制御信号は比較式を表す。比較ユニット５０は、制御信号に応じた比較式を用いてデータａとデータｂとを比較する。比較式は、ａ＜ｂ、ａ＜＝ｂ、ａ＞ｂ、ａ＞＝ｂ、の四種類である。この比較式が満たされれば比較結果ｃは１となり、そうでなければ比較結果ｃは０となる。制御信号ｃｍｏｄｅとデータａとｂと比較結果ｃの関係を関数ｃｏｍｐａｒｅ（）を使って、ｃ＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ、ａ、ｂ）というように表す。このように、比較ユニット５０の動作を関数ｃｏｍｐａｒｅ（）を用いて表すことができる。
【００３１】
選択ユニット４０は、比較ユニット５０から与えられた比較結果ｃを選択信号として使用し、データａとデータｂのいずれかを選択し、選択データｘとして出力する。選択信号（比較結果ｃ）と選択データｘとの関係は図６Ｃの表に示す通りである。選択ユニット４０は選択信号に応じて入力信号aかｂのどちらかを選択して出力する。具体的には、選択信号ｃが０ならばデータａが選択され、それ以外ならばデータｂが選択され、選択されたデータが選択データｘとなる。選択信号ｃとデータａとｂとの関係を関数ｓｅｌｅｃｔ（）を使って、ｘ＝ｓｅｌｅｃｔ（ｃ、ａ、ｂ）というように表す。このように、選択ユニット４０の動作を関数ｓｅｌｅｃｔ（）を用いて表すことができる。
【００３２】
図７を参照しながら、インデックス・ベクトル選択ユニット２４３を説明する。インデックス・ベクトル選択ユニット２４３は、三つの分割ユニット１２〜１４と、複数の選択ユニット４１〜４４と、一つの結合ユニット２２と、で構成される。図７は選択ユニットの数が４個の場合を表している。インデックス・ベクトル選択ユニット２４３の入力信号は、制御信号と、インデックス・ベクトル１と、インデックス・ベクトル２と、比較結果ベクトルと、である。インデックス・ベクトル選択ユニット２４３の出力信号はインデックス・ベクトル３である。
【００３３】
図７の分割ユニット（第一インデックス分割ユニット）１２は制御信号に基づいてインデックス・ベクトル１を複数の要素へ分割する。同様に、図７の分割ユニット（第二インデックス分割ユニット）１３はインデックス・ベクトル２を、図７の分割ユニット（比較結果分割ユニット）１４は比較結果ベクトルを、それぞれ制御信号に基づいて複数の要素へ分割する。選択ユニット４１〜４４は、分割ユニット１４から与えられた要素ｃ（比較結果ｃ）を選択信号として、分割ユニット１２から与えられた要素ｇと、分割ユニット１３から与えられた要素ｈと、のどちらかを選択し、それを要素ｚとして出力する。結合ユニット２２は複数の選択ユニット４１〜４４から与えられた要素ｚを制御信号に基づいて一つのベクトルに結合し、それをインデックス・ベクトル３として出力する。
【００３４】
続いて、第一の実施形の動作を図面を参照しながら説明する。以降では、複数個のデータの中から最大値あるいは最小値とそのインデックスを探索する処理を「最大値あるいは最小値の探索処理」と呼ぶことにする。図８は最大値あるいは最小値の探索処理の概念を表す。
まず、（１）において、Ｎ（Ｎ＞０の整数）個のデータをＳ０、Ｓ１、Ｓ２、・・・、ＳＮ−１とする。次に、（２）において、Ｎ個のデータをｄｎｕｍ個のグループに分割する。データのインデックスをｄｎｕｍで割った余りが等しくなるようにＮ個のデータを分割する。ｄｎｕｍは任意の正の整数であるが、実装を容易にするためにｄｎｕｍは２のべき乗であることが望ましい。
【００３５】
次に、（３）において、各グループ内の最大値あるいは最小値とそのインデックスを探索する。すると、各グループで一つのデータとそのインデックスが選択される。最後に、（４）において、ｄｎｕｍ個の選択されたデータの中から、最大値あるいは最小値とそのインデックスを探索する。図８の概念では（３）においてｄｎｕｍ個の探索処理を並列に実行可能である。本発明の実施形態は図８の概念に基づいて最大値あるいは最小値の探索処理を実行する。
【００３６】
図９は、図８の概念に基づいて最大値あるいは最小値の探索処理を、本発明の模範的な実施形態で実行するためのフローチャートである。このフローチャートは図１のプロセッサ２００のためのプログラムの処理内容を表す。そのプログラムは図１のメモリ１００に格納される。プロセッサ２００はそのプログラムを実行することによって、複数個のデータの中から最大値あるいは最小値とそのインデックスを探索する。複数個のデータはメモリ１００に格納される。
【００３７】
第一の実施形態における最大値あるいは最小値の探索処理は六つのステップで構成される。
ｓｔｅｐ１は探索処理の初期化を行なうステップである。
ｓｔｅｐ２は未処理のデータが残っているかどうかを調べるステップである。
ｓｔｅｐ３はデータを読み込むステップである。
ｓｔｅｐ４はデータのインデックスを更新するステップである。
ｓｔｅｐ５は二つのベクトルを対応する要素ごとに比較し、大きい方かもしくは小さい方の要素を選択するステップである。  要素が選択される際には、その要素に対応するインデックスも選択される。
未処理のデータがなくなるまでｓｔｅｐ２からｓｔｅｐ５は繰り返される。ｓｔｅｐ２からｓｔｅｐ５の繰返しは図８の（２）と（３）に相当する。
【００３８】
ｓｔｅｐ５で比較されるベクトルは各要素のレジスタ内の位置でグループ分けされ、各グループ毎に比較と選択が実行される。選択された要素は再びレジスタへ格納され、次回のｓｔｅｐ５で使用される。ｓｔｅｐ２からｓｔｅｐ５の繰返しが終了すると、ｓｔｅｐ５によって選択された各グループの最大値あるいは最小値が一つのベクトルとして結合され、そのベクトルがレジスタに格納される。これは図８の（３）が終了した状態である。
最後に実行されるｓｔｅｐ６は一つのベクトルの全ての要素の中から最大値あるいは最小値を選択するステップである。最大値あるいは最小値が選択される際には、その値に対応するインデックスも選択される。ｓｔｅｐ６は図８の（４）に相当する。
ｓｔｅｐ１からｓｔｅｐ６までのステップによって、複数のデータの中から最大値あるいは最小値とそのインデックスを求める事ができる。
【００３９】
以降の説明では、簡単のために、図９の概念におけるｄｎｕｍが４で、データ数Ｎが１６で、各データは１６ビットの整数であると仮定して説明する。図１のプロセッサ２００のレジスタバンク２３０は複数の６４ビットレジスタを含むと仮定する。レジスタバンク２３０の四つの６４ビットレジスタをレジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄと呼ぶことにする。レジスタに格納されたｄｎｕｍ個のデータをベクトルと呼ぶことにする。ベクトルの一つ一つの要素がデータである。また、以降の動作の説明及び図面（図１０、１１、１３）において、ｓｔｅｐ１〜ｓｔｅｐ６は、図９に示した同じステップ番号の処理と対応する。
【００４０】
図１０を参照しながら、第一の実施形態におけるｓｔｅｐ１を説明する。ｓｔｅｐ１において、プロセッサ２００は、レジスタバンク２３０のレジスタＲｃへｄｎｕｍ個の初期選択値（選択値の初期値）を、レジスタＲｄへそれらに対応するｄｎｕｍ個のインデックスを、それぞれ格納する。図１０では、ｄｎｕｍ個の初期選択値はメモリ１００に格納されているｓ０、ｓ１、ｓ２、ｓ３であり、それらのインデックスは０、１、２、３である。
【００４１】
第一の実施形態におけるｓｔｅｐ２において、プロセッサ２００は未処理のデータの数を計算し、それが０より大きいならばｓｔｅｐ３へ移行し、そうでないならばｓｔｅｐ６へ移行する。図１０において、ｓｔｅｐ１が終った直後の状態では、Ｎ個のデータのうちｄｎｕｍ個を初期選択値として使用したので、未処理のデータの数はＮ−ｄｎｕｍ個である。データ数Ｎを１６、分割数をｄｎｕｍ、と仮定しているので、Ｎ−ｄｎｕｍ＝１６−４＝１２、となって、未処理データはまだ残っていることになる。
【００４２】
第一の実施形態におけるｓｔｅｐ３において、プロセッサ２００は、次のｄｎｕｍ個のデータをメモリ１００から読み込み、それらをレジスタＲａへ格納する。図１０では、次のｄｎｕｍ個のデータはｓ４、ｓ５、ｓ６、ｓ７である。
第一の実施形態におけるｓｔｅｐ４において、プロセッサ２００は、次のｄｎｕｍ個のデータのインデックスをレジスタＲｂへ格納する。図１０では、次のｄｎｕｍ個のデータはｓ４、ｓ５、ｓ６、ｓ７なので、それらのインデックスは４、５、６、７である。
【００４３】
図１１を参照しながら、第一の実施形態におけるｓｔｅｐ５を説明する。ｓｔｅｐ５において、プロセッサ２００は、図２の並列比較選択演算ユニット２４０を動作させ、ベクトル間比較選択処理を行なう。ベクトル間比較選択処理は、二つのベクトルデータを対応する要素ごとに比較し、大きい方かもしくは小さい方の要素を選択し、さらに選択した要素に対応するインデックスも選択する、という処理である。二つのベクトルデータをベクトルデータ１、ベクトルデータ２として、それらに対応するインデックス・ベクトルをインデックス・ベクトル１、インデックス・ベクトル２とする。図１１では、ベクトルデータ１がレジスタＲａに、インデックス・ベクトル１がレジスタＲｂに、ベクトルデータ２がレジスタＲｃに、インデックス・ベクトル２がレジスタＲｄに、それぞれ格納されている。
【００４４】
ｓｔｅｐ５において、プロセッサ２００は並列比較選択演算ユニット２４０を動作させるための命令をメモリ１００から読み込む。そして、命令デコーダ２１０はその命令をデコードし、その命令の命令コードやオペランドの情報を制御信号として並列比較選択演算ユニット２４０へ送る。命令デコーダ２１０からの制御信号を受けて、並列比較選択演算ユニット２４０は、レジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄからベクトルデータ１、インデックス・ベクトル１、ベクトルデータ２、インデックス・ベクトル２を読み出し、ベクトル比較選択ユニット２４２とインデックス・ベクトル選択ユニット２４３を動作させて、ベクトルデータ３とインデックス・ベクトル３をレジスタＲｃとＲｄへそれぞれ出力する。
【００４５】
ここで、並列比較選択演算ユニット２４０の動作を、図１１に示したデータと関数表記とを用いて具体的に説明する。まず、ベクトル比較選択ユニット２４２の動作を図３、図６Ａ、６Ｂ、６Ｃ及び図１１を用いて説明する。
分割ユニット１０、１２（図３）は、ベクトルデータ１、ベクトルデータ２を要素毎に分割する。図１１では、分割ユニット１０は、ベクトルデータ１をｓ４〜ｓ７の各要素に、分割ユニット１１は、ベクトルデータ２をｓ０〜ｓ３の各要素に分割する。
続いて、複数の比較選択ユニット３０〜３３（図３）は、各要素について比較選択処理を実施する。複数の比較選択ユニット３０〜３３内の比較ユニット５０（図６Ａ）は、関数ｃｏｍｐａｒｅ（）でレジスタＲａとレジスタＲｃに格納されたデータを比較する。具体的には複数の比較選択ユニット３０〜３３内の比較ユニット５０は、次の関数を用いて比較する。ｃｍｏｄｅは比較選択ユニット３０〜３３への制御信号を表す。
ｃ０＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ，ｓ０，ｓ４）
ｃ１＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ，ｓ１，ｓ５）
ｃ２＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ，ｓ２，ｓ６）
ｃ３＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ，ｓ３，ｓ７）
【００４６】
続いて、複数の比較選択ユニット３０〜３３内の選択ユニット４０は、比較ユニット５０が比較した比較結果を使って関数ｓｅｌｅｃｔ（）でレジスタＲａとＲｃから適切なデータを選択する。具体的には、選択ユニット４０は、次の関数を用いて選択する。
ｘ０＝ｓｅｌｅｃｔ（ｃ０，ｓ０，ｓ４）
ｘ１＝ｓｅｌｅｃｔ（ｃ１，ｓ１，ｓ５）
ｘ２＝ｓｅｌｅｃｔ（ｃ２，ｓ２，ｓ６）
ｘ３＝ｓｅｌｅｃｔ（ｃ３，ｓ３，ｓ７）
ここで、ｃ０〜ｃ３、ｘ０〜ｘ３は、図３の同じ符号のデータと対応する。
結合ユニット２０は、ｘ０〜ｘ３を結合し、ベクトルデータ３を生成する。結合ユニット２１は、ｃ０〜ｃ３を結合し、比較結果ベクトルを生成し、インデックス・ベクトル選択ユニット２４３へ出力する。
【００４７】
次に、インデックス・ベクトル選択ユニット２４３の動作を図７及び図１１を用いて説明する。
分割ユニット１２、１３（図７）は、インデックス・ベクトル１、インデックス・ベクトル２を要素毎（インデックス毎）に分割する。図１１では、分割ユニット１２は、ベクトルデータ１をｉ４〜ｉ７の各要素に、分割ユニット１３は、ベクトルデータ２をｉ０〜ｉ３の各要素に分割する。分割ユニット１４は、比較結果ベクトルをｃ０〜ｃ３の各要素へ分割する。
選択ユニット４１〜４４（図７）は、ベクトル比較選択ユニット２４２の選択ユニット４０（図６Ａ）と同様にレジスタＲｂとＲｄから適切なデータを選択する。具体的には、選択ユニット４１〜４４は、次の関数を用いて選択する。
ｚ０＝ｓｅｌｅｃｔ（ｃ０，ｉ０，ｉ４）
ｚ１＝ｓｅｌｅｃｔ（ｃ１，ｉ１，ｉ５）
ｚ２＝ｓｅｌｅｃｔ（ｃ２，ｉ２，ｉ６）
ｚ３＝ｓｅｌｅｃｔ（ｃ３，ｉ３，ｉ７）
ここで、ｚ０〜ｚ３は、図７の同じ符号のデータと対応する。
結合ユニット２２は、ｚ０〜ｚ３を結合し、インデックス・ベクトル３を生成する。
【００４８】
上述のように、ベクトル比較選択ユニット２４２が生成したベクトルデータ３は、レジスタＲｃへ格納される。また、インデックス・ベクトル選択ユニット２４３が生成したインデックス・ベクトル３はレジスタＲｄへ格納される。
第一の実施形態では、ベクトルデータ３とインデックス・ベクトル３をレジスタＲｃとレジスタＲｄに格納する。従って、図１１に示すように、レジスタＲａに読み出したベクトルデータを比較対象データ、レジスタＲｃに設定されたデータを現在の選択値と呼ぶ。
【００４９】
ｓｔｅｐ５において、並列比較選択演算ユニット２４０を動作させるための命令として利用可能な命令を図１２に示す。図１２には、８個の命令の、シンタックスと、その命令によって命令デコーダ２１０が並列比較選択演算ユニット２４０へ送る二つの制御信号と、命令の説明と、を示している。二つの制御信号は、並列比較選択演算ユニット２４０の中の比較選択ユニット３０〜３３へ送られる制御信号ｃｍｏｄｅと、並列比較選択演算ユニット２４０の中の分割ユニット１０と結合ユニット２０へ送られる制御信号ｄｎｕｍ、である。
例えば、ＭＡＸ．Ｈという命令は比較式（Ｒａ＜Ｒｃ）を使って１６ビットの値を比較し、大きい方の値を選択する命令である。ＭＡＸ．Ｈ命令の場合のｃｍｏｄｅの値は０である。図６Ｂによると、ｃｍｏｄｅ＝０は比較演算＜を意味する。ＭＡＸ．Ｈ命令の場合のｄｎｕｍの値は４である。ｄｎｕｍは分割後あるいは結合前のデータの数を表す。
【００５０】
１６ビットの１６個のデータから最大値あるいは最小値とそのインデックスを求める様子を図１３に示す。図１３の右上から処理が始まる。
ｓｔｅｐ１において、プロセッサ２００は、初期選択値のベクトルデータとそれに対応するインデックス・ベクトル（初期インデックス）をそれぞれレジスタＲｃ、Ｒｄへ格納する。
ｓｔｅｐ２において（図１３には図示されていない）、プロセッサ２００は、未処理のデータが１２個残っているので、ｓｔｅｐ３へ移行する。
ｓｔｅｐ３において、プロセッサ２００は、比較対象のデータ４個をレジスタＲａへ読み込む。
ｓｔｅｐ４において、プロセッサ２００は、比較対象のデータ４個のインデックスをレジスタＲｂへ格納する。
ｓｔｅｐ５において、プロセッサ２００は、レジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄを使って、１回目のレジスタ間比較選択処理を実行する。１回目のレジスタ間比較選択処理によって選択されたデータとインデックスはレジスタＲｃとＲｄへそれぞれ格納される。この１回目のレジスタ間比較選択処理に（１）という番号をつける。
【００５１】
この後は、ｓｔｅｐ２を省略すると、以下のように処理が進む。
（２）ｓｔｅｐ３：データ読み込み２回目
（３）ｓｔｅｐ４：インデックス更新
（４）ｓｔｅｐ５：レジスタ間比較選択処理２回目
（５）ｓｔｅｐ３：データ読み込み３回目
（６）ｓｔｅｐ４：インデックス更新
（７）ｓｔｅｐ５：レジスタ間比較選択処理３回目
【００５２】
（２）のｓｔｅｐ３において、プロセッサ２００は、新たなデータ４個をレジスタＲａへ読み込む。
（３）のｓｔｅｐ４において、プロセッサ２００は、レジスタＲｂのインデックスを利用して、新たなデータ４個のインデックスを計算し、それをレジスタＲｂへ格納する。インデックス更新の計算方法は、レジスタＲｂの各要素へ４を加算する、というものである。
（４）のｓｔｅｐ５において、プロセッサ２００は、２回目のレジスタ間比較選択処理を実行する。
同様にして、（５）、（６）、（７）が実行される。
【００５３】
図１４を参照しながら、ｓｔｅｐ６を説明する。ｓｔｅｐ６は一つのレジスタに格納されたベクトルの全ての要素の中かから最大値あるいは最小値を探し、その値に対応するインデックスをもう一つのレジスタから取り出すステップである。
ｓｔｅｐ６において、プロセッサ２００が最大値あるいは最小値のどちらを探すかは、メモリ１００に格納されたプログラムによって決定される。
【００５４】
図１４では、四つのグループから選ばれた選択値がレジスタＲｃに、四つのグループから選ばれた選択値のインデックスがレジスタＲｄに、それぞれ格納されている。
ｓｔｅｐ６において、プロセッサ２００は、レジスタＲｃに格納された四つの選択値ｘ０"、ｘ１"、ｘ２"、ｘ３"と、レジスタＲｄに格納された四つのインデックスｚ０"、ｚ１"、ｚ２"、ｚ３"と、を一つ一つ別々のレジスタへ格納する。
【００５５】
プロセッサ２００は、四つの選択値の中からひとつの値をさらに選択するために，比較選択処理を３回行なう。
１回目の比較選択処理において、プロセッサ２００は、ｘ０"とｘ１"とを比較し、比較条件を満たす方の値を選択する。  比較条件はｓｔｅｐ６のプログラムの中に記述されているものとする。
例えば、比較条件を＜とすると、ｘ０"＜ｘ１"が真ならばｘ１"が選択され、そうでないならばｘ０"が選択される。比較条件としては、＜、＜＝、＞、＞＝、などが利用可能である。
ｘ０"とｘ１"の比較結果に基づいて、プロセッサ２００は、ｚ０"かｚ１"のどちらかのインデックスを選択する。
例えば、もしｘ０"＜ｘ１"が真ならばｚ０"が選択され、そうでないならばｚ１"が選択される。
ｓｔｅｐ６には３回の比較選択処理があるが、どの比較選択処理にも同じ比較条件が使われる。
【００５６】
同様にして、１回目の比較選択処理において、プロセッサ２００は、ｘ２"とｘ３"とを比較し、比較条件を満たす方の値を選択する。
ｘ２"とｘ３"の比較結果に基づいて、プロセッサ２００は、ｚ２"かｚ３"のどちらかのインデックスを選択する。
【００５７】
１回目と２回目の比較選択処理によって選択された値をｘ０'''とｘ１'''として、それらのインデックスをｚ０'''とｚ１'''とする。これらの値とインデックスを使って、プロセッサ２００は、３回目の比較選択処理を行なう。
プロセッサ２００は、ｘ０'''とｘ１'''とを比較し、比較条件を満たす方の値を選択する。
ｘ０'''とｘ１'''の比較結果に基づいて、プロセッサ２００は、ｚ０'''かｚ１'''のどちらかのインデックスを選択する。
３回目の比較選択処理で選択された値とインデックスをｘ０""とｚ０""とする。
ｘ０""はｓｔｅｐ６においてプロセッサ２００がｘ０"、ｘ１"、ｘ２"、ｘ３"の中から選択した最大値あるいは最小値であり、全てのデータの中の最大値である。そして、ｚ０""はｘ０""のインデックスである。
【００５８】
以上説明したように、第一の実施形態の並列比較選択演算ユニットは、ベクトルデータ１と、ベクトルデータ２と、ベクトルデータ１の各要素のインデックスで構成されたインデックス・ベクトル１と、ベクトルデータ２の各要素のインデックスで構成されたインデックス・ベクトル２と、を入力信号とする。並列比較選択演算ユニットは、ベクトルデータ１とベクトルデータ２の各要素を比較し、その比較結果に基づいてベクトルデータ１とベクトルデータ２のどちらかを要素毎に選択したベクトルデータ３を生成する。また、並列比較選択演算ユニットは、比較結果に基づいてインデックス・ベクトル１とインデックス・ベクトル２のどちらかを要素毎（インデックス毎）に選択し、選択された複数個の要素をインデックス・ベクトル３として生成する。そして、並列比較選択演算ユニットは、ベクトルデータ３とインデックス・ベクトル３とを出力する。
【００５９】
本実施形態の並列比較選択演算ユニットによれば、二つのベクトルデータを要素毎に比較し、比較結果に基づいて一方の要素を選択するとともに、選択した要素に対応するインデックスを選択することができる。また、本実施形態の並列比較選択演算ユニットを備えるプロセッサは、インデックスをともなう最大値探索あるいは最小値探索を効率よく実行することができる。
また、プロセッサは、本実施形態の並列比較選択演算ユニットを備えることにより、ベクトル間比較選択処理を効率よく実施し、ベクトル関比較選択処理の結果を用いて、最大値あるいは最小値を取得することが可能になる。
【００６０】
なお、第一の実施形態では、ベクトル比較選択ユニット２４２内の比較選択ユニット３０〜３１が出力する比較結果を、複数の比較結果の集合である比較結果ベクトルとしてインデックス・ベクトル選択ユニット２４３へ出力する場合を説明した（図２、３、７）。この構成に限られることはなく、複数の比較結果を複数の選択信号として、ベクトル比較選択ユニット２４２からインデックス・ベクトル選択ユニット２４３へ出力する構成であってもよい。この場合、結合ユニット２１（図３）及び分割ユニット１４（図７）を備えなくてもよい。
一方で、比較結果ベクトルを用いることにより、ベクトルに含まれる要素数が変化した場合に対応しやすいという利点がある。具体的には、ベクトル比較選択ユニット２４２からインデックス・ベクトル選択ユニット２４３へ出力する選択信号（比較結果ベクトル）の数を変更する必要がない。ベクトル比較選択ユニット２４２内の比較選択ユニット数、インデックス・ベクトル選択ユニット２４３内の選択ユニットの数、並びに関係する信号線等を変更することにより、要素数の変化に対応することが可能となる。
すなわち、分割ユニットや結合ユニットを使うと，ベクトルデータの各要素のデータ幅を可変にすることができる。例えば、１６ビットのデータ幅をもつ要素で構成されるベクトルデータを処理したり、８ビットのデータ幅をもつ要素で構成されるベクトルデータを処理したり、ということが可能になる。ただし，ひとつのベクトルデータの中の全ての要素のデータ幅は同じにする必要がある。これに対して、分割ユニットや結合ユニットを使わない場合には，あらかじめ決めたデータ幅の要素で構成されるベクトルデータだけを処理することができる。それ以外のデータ幅の要素で構成されるベクトルデータを処理することはできない。
【００６１】
（第二の実施形態）
図１５を参照しながら、第二の実施形態における並列比較選択演算ユニット２４０ａを説明する。第二の実施形態では、図１に示すプロセッサ２００は、並列比較選択演算ユニット２４０に替えて図１５に示す並列比較選択演算ユニット２４０ａを用いる。本実施形態では、第一の実施形態において用いたインデックス・ベクトル１に替えて、ベクトルデータ１のインデックスに関する情報（第一インデックス情報）を用いる場合を説明する。具体的には、第一インデックス情報として、ベクトルデータ１の最初の要素（０番目の要素）のインデックスを用いる場合を説明する。以下、最初の要素のインデックスを開始インデックス１という。
【００６２】
第二の実施形態の並列比較選択演算ユニット２４０ａは、ベクトル比較選択ユニット２４２と、インデックス・ベクトル選択ユニット２４３と、インデックス・ベクトル生成ユニット２４１と、更新ユニット２４４と、で構成される。
第二の実施形態における並列比較選択演算ユニット２４０ａの入力信号は、命令デコーダ２１０からの制御信号と、レジスタバンク２３０からの四つのデータである。この四つのデータとは、ベクトルデータ１、ベクトルデータ２、開始インデックス１、インデックス・ベクトル２、である。第二の実施形態における並列比較選択演算ユニット２４０ａの出力信号は、ベクトルデータ３と、開始インデックス１である。
【００６３】
第一の実施形態と第二の実施形態の違いは二つある。一つは、インデックス・ベクトル生成ユニット２４１を使って、第二の実施形態は開始インデックス１からインデックス・ベクトル１を生成することである。もう一つは、更新ユニット２４４を使って開始インデックス１の値を変更し、変更した値を出力することである。
第二の実施形態におけるベクトル比較選択ユニット２４２とインデックス・ベクトル選択ユニット２４３の構成や動作は第一の実施形態のそれと同じである。
【００６４】
図１６Ａ、１６Ｂを参照しながら、インデックス・ベクトル生成ユニット２４１を説明する。図１６Ａに示すように、インデックス・ベクトル生成ユニット２４１は結合ユニット２３を含む。インデックス・ベクトル生成ユニット２４１の入力信号は、命令デコーダ２１０からの制御信号と、レジスタバンク２３０からの開始インデックス１と、である。インデックス・ベクトル生成ユニット２４１の出力信号はインデックス・ベクトル１である。
【００６５】
インデックス・ベクトル生成ユニット２４１は、制御信号に基づいて、開始インデックス１からインデックス・ベクトル１を生成する。制御信号と開始インデックス１とインデックス・ベクトル１の関係は図１６Ｂの表に示す通りである。
開始インデックス１をｉｄｘとすると、インデックス・ベクトル生成ユニット２４１は、ｉｄｘ＋１＊ｓ、ｉｄｘ＋２＊ｓ、ｉｄｘ＋３＊ｓ、という三つのデータを計算し、ｉｄｘと合わせて四つのデータを結合ユニット２０へ送る。さらに、インデックス・ベクトル生成ユニット２４１は、制御信号に基づいて、ｄｎｕｍという信号を結合ユニット２３へ送る。
【００６６】
ここで、ｓ（ｓ＞０の整数）はスケールファクタであり、ｄｎｕｍは結合ユニット２０が結合すべきデータの数を表す信号である。もし制御信号が０ならば、ｓは２である。図１６Ｂにおいて、もし制御信号が１ならば、ｓは４である。もし制御信号が０ならば、結合ユニット２０は、ｉｄｘ、ｉｄｘ＋２、ｉｄｘ＋４、ｉｄｘ＋６、という四つのデータを結合し、それをインデックス・ベクトル１として出力する。もし制御信号が１ならば、結合ユニット２０は、ｉｄｘ、ｉｄｘ＋４、という二つのデータを結合し、それをインデックス・ベクトル１として出力する。
【００６７】
図１７Ａ、１７Ｂを参照しながら、更新ユニット２４４を説明する。更新ユニット２４４への入力信号は、開始インデックス１と、制御信号と、である。更新ユニット２４４の出力信号は開始インデックス１である。更新ユニット２４４は開始インデックス１をインクリメントする。インクリメントの増分はｓｔｅｐという値である。ｓｔｅｐは制御信号によって決定される。制御信号とｓｔｅｐの関係は図１７Ｂの表に示す通りである。もし制御信号が０ならば、ｓｔｅｐは２である。もし制御信号が１ならば、ｓｔｅｐは４である。
【００６８】
続いて、第二の実施形態の動作を図面を参照しながら説明する。第二の実施形態では、プロセッサ２００の並列比較選択演算ユニット２４０ａが図１５のように構成される。第二の実施形態は、第一の実施形態と同様に、図８の概念と図９のフローチャートとに基づいて、複数個のデータの中から最大値あるいは最小値とそのインデックスを探索する。
【００６９】
以降の説明では、簡単のために、図９の概念におけるｄｎｕｍが４で、データ数Ｎが１６で、各データは１６ビットの整数であると仮定して説明する。図１のプロセッサ２００のレジスタバンク２３０は複数の６４ビットレジスタを含むと仮定する。レジスタバンク２３０の四つの６４ビットレジスタをレジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄと呼ぶことにする。レジスタに格納されたｄｎｕｍ個のデータをベクトルと呼ぶことにする。ベクトルの一つ一つの要素がデータである。また、以降の動作の説明及び図面（図１８、１９、２１）において、ｓｔｅｐ１〜ｓｔｅｐ６は、図９に示した同じステップ番号の処理と対応する。
【００７０】
図１８を参照しながら、第二の実施形態におけるｓｔｅｐ１を説明する。
第二の実施形態におけるｓｔｅｐ１は第一の実施形態におけるｓｔｅｐ１と異なる。ｓｔｅｐ１において、プロセッサ２００は、レジスタバンク２３０のレジスタＲｃへｄｎｕｍ個の初期選択値を、レジスタＲｄへそれらに対応するｄｎｕｍ個のインデックスを、それぞれ格納する。さらに、レジスタＲｃへ格納したｄｎｕｍ個の次のデータのインデックスを開始インデックスとしてレジスタＲｂへ格納する。開始インデックスをレジスタＲｂへ格納することが第一の実施形態におけるｓｔｅｐ１とは異なる。
図１８では、ｄｎｕｍ個の初期選択はメモリ１００に格納されているｓ０、ｓ１、ｓ２、ｓ３であり、それらのインデックスは０、１、２、３である。そして、次のデータはｓ４なので、開始インデックスは４である。
【００７１】
第二の実施形態におけるｓｔｅｐ２は第一の実施形態におけるｓｔｅｐ２と全く同じである。第二の実施形態におけるｓｔｅｐ２において、プロセッサ２００は未処理のデータの数を計算し、それが０より大きいならばｓｔｅｐ３へ移行し、そうでないならばｓｔｅｐ６へ移行する。
図１８において、ｓｔｅｐ１が終った直後の状態では、Ｎ個のデータのうちｄｎｕｍ個を初期選択値として使用したので、未処理のデータの数はＮ−ｄｎｕｍ個である。データ数Ｎを１６、分割数をｄｎｕｍ、と仮定しているので、Ｎ−ｄｎｕｍ＝１６−４＝１２、となって、未処理データはまだ残っていることになる。
【００７２】
第二の実施形態におけるｓｔｅｐ３は第一の実施形態におけるｓｔｅｐ３と全く同じである。第二の実施形態におけるｓｔｅｐ３において、プロセッサ２００は、次のｄｎｕｍ個のデータをメモリ１００から読み込み、それらをレジスタＲａへ格納する。
図１８では、次のｄｎｕｍ個のデータはｓ４、ｓ５、ｓ６、ｓ７である。
【００７３】
第二の実施形態におけるｓｔｅｐ４とｓｔｅｐ５は並列に実行される。図１９を参照しながら、第二の実施形態におけるｓｔｅｐ４とｓｔｅｐ５を説明する。ｓｔｅｐ４とｓｔｅｐ５において、プロセッサ２００は、図１５の並列比較選択演算ユニット２４０ａを動作させ、インデックス更新とベクトル間比較選択処理とを行なう。すなわち、第二の実施形態では、並列比較選択演算ユニット２４０ａがｓｔｅｐ４とｓｔｅｐ５とを並列して実行する。
【００７４】
第二の実施形態におけるベクトル間比較選択処理について説明する。ベクトル間比較選択処理は、二つのベクトルデータを対応する要素ごとに比較し、大きい方かもしくは小さい方の要素を選択し、さらに選択した要素に対応するインデックスも選択する、という処理である。これは第一の実施形態にけるベクトル間比較選択処理と同じである。第一の実施形態と異なるのは、一方のベクトルデータのインデックスの与え方である。第二の実施形態では、一方のベクトルデータの最初の要素のインデックスを開始インデックスとしてレジスタへ格納する。図１５の並列比較選択演算ユニット２４０ａは開始インデックスから一方のベクトルデータの全てのインデックスを生成する。
【００７５】
二つのベクトルデータをベクトルデータ１、ベクトルデータ２として、ベクトルデータ１の最初の要素のインデックスを開始インデックス１として、ベクトルデータ２に対応するインデックス・ベクトルをインデックス・ベクトル２とする。図１９では、ベクトルデータ１がレジスタＲａに、開始インデックス１がレジスタＲｂに、ベクトルデータ２がレジスタＲｃに、インデックス・ベクトル２がレジスタＲｄに、それぞれ格納されている。
【００７６】
ｓｔｅｐ４とｓｔｅｐ５において、プロセッサ２００は、図１５の並列比較選択演算ユニット２４０ａを動作させるための命令をメモリ１００から読み込む。そして、命令デコーダ２１０はその命令をデコードし、その命令の命令コードやオペランドの情報を制御信号として図１５の並列比較選択演算ユニット２４０ａへ送る。命令デコーダ２１０からの制御信号を受けて、並列比較選択演算ユニット２４０ａは、レジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄからベクトルデータ１、開始インデックス１、ベクトルデータ２、インデックス・ベクトル２を読み出し、インデックス・ベクトル生成ユニット２４１と、ベクトル比較選択ユニット２４２と、インデックス・ベクトル選択ユニット２４３と、更新ユニット２４４と、を動作させて、ベクトルデータ３と開始インデックス３をレジスタＲｃとＲｄへそれぞれ出力する。
【００７７】
ここで、図１５の並列比較選択演算ユニット２４０ａのｓｔｅｐ５の動作を、図１９に示したデータと関数表記とを用いて具体的に説明する。なお、並列比較選択演算ユニット２４０ａの動作は第一の実施形態のｓｔｅｐ５の動作と同様であるため、主に関数表記について説明し、他の動作については省略する。
ベクトル比較選択ユニット２４２において、複数の比較選択ユニット３０〜３３（図３）は、各要素について比較選択処理を実施する。複数の比較選択ユニット３０〜３３内の比較ユニット５０（図６Ａ）は、関数ｃｏｍｐａｒｅ（）でレジスタＲａとレジスタＲｃに格納されたデータを比較する。具体的には複数の比較選択ユニット３０〜３３内の比較ユニット５０は、次の関数を用いて比較する。ｃｍｏｄｅは比較選択ユニット３０〜３３への制御信号を表す。
ｃ０＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ，ｓ０，ｓ４）
ｃ１＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ，ｓ１，ｓ５）
ｃ２＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ，ｓ２，ｓ６）
ｃ３＝ｃｏｍｐａｒｅ（ｃｍｏｄｅ，ｓ３，ｓ７）
【００７８】
続いて、複数の比較選択ユニット３０〜３３内の選択ユニット４０は、比較ユニット５０が比較した比較結果を使って関数ｓｅｌｅｃｔ（）でレジスタＲａとＲｃから適切なデータを選択する。具体的には、選択ユニット４０は、次の関数を用いて選択する。
ｘ０＝ｓｅｌｅｃｔ（ｃ０，ｓ０，ｓ４）
ｘ１＝ｓｅｌｅｃｔ（ｃ１，ｓ１，ｓ５）
ｘ２＝ｓｅｌｅｃｔ（ｃ２，ｓ２，ｓ６）
ｘ３＝ｓｅｌｅｃｔ（ｃ３，ｓ３，ｓ７）
ここで、ｃ０〜ｃ３、ｘ０〜ｘ３は、図３の同じ符号のデータと対応する。
結合ユニット２０は、ｘ０〜ｘ３を結合し、ベクトルデータ３を生成する。結合ユニット２１は、ｃ０〜ｃ３を結合し、比較結果ベクトルを生成し、インデックス・ベクトル選択ユニット２４３へ出力する。
【００７９】
次に、インデックス・ベクトル選択ユニット２４３において、選択ユニット４１〜４４（図７）は、ベクトル比較選択ユニット２４２の選択ユニット４０（図６Ａ）と同様にレジスタＲｂとＲｄから適切なデータを選択する。具体的には、選択ユニット４１〜４４は、次の関数を用いて選択する。
ｚ０＝ｓｅｌｅｃｔ（ｃ０，ｉ０，ｉ４）
ｚ１＝ｓｅｌｅｃｔ（ｃ１，ｉ１，ｉ４＋１）
ｚ２＝ｓｅｌｅｃｔ（ｃ２，ｉ２，ｉ４＋２）
ｚ３＝ｓｅｌｅｃｔ（ｃ３，ｉ３，ｉ４＋３）
ここで、ｚ０〜ｚ３は、図７の同じ符号のデータと対応する。
結合ユニット２２は、ｚ０〜ｚ３を結合し、インデックス・ベクトル３を生成する。
【００８０】
上述のように、ベクトル比較選択ユニット２４２が生成したベクトルデータ３は、レジスタＲｃへ格納される。また、インデックス・ベクトル選択ユニット２４３が生成したインデックス・ベクトル３はレジスタＲｄへ格納される。
なお、関数ｃｏｍｐａｒｅ（）と関数ｓｅｌｅｃｔ（）の中身（処理内容）は第一の実施形態と同じである。
【００８１】
ｓｔｅｐ４とｓｔｅｐ５において、並列比較選択演算ユニット２４０ａを動作させるための命令として利用可能な命令を図２０に示す。図２０には、８個の命令の、シンタックスと、その命令によって命令デコーダ２１０が図１５の並列比較選択演算ユニット２４０ａへ送る三つの制御信号と、命令の説明と、を示している。三つの制御信号は、図１５並列比較選択演算ユニット２４０ａの中の比較選択ユニット３０〜３３へ送られる制御信号ｃｍｏｄｅと、図１５の並列比較選択演算ユニット２４０ａの中の分割ユニット１０と結合ユニット２０へ送られる制御信号ｄｎｕｍと、図１５の並列比較選択演算ユニット２４０ａのインデックス・ベクトル生成ユニット２４１への制御信号、である。
【００８２】
例えば、図２０のＭＡＸ．Ｈという命令は比較式（Ｒａ＜Ｒｃ）を使って１６ビットの値を比較し、その比較結果に基づいて大きい方の値を選択し、開始インデックスへ４を加算する命令である。ＭＡＸ．Ｈ命令の場合のｃｍｏｄｅの値は０である。図６Ｂによると、ｃｍｏｄｅ＝０は比較演算＜を意味する。ＭＡＸ．Ｈ命令の場合のｄｎｕｍの値は４である。ｄｎｕｍは分割後あるいは結合前のデータの数を表す。ＭＡＸ．Ｈ命令の場合のインデックス・ベクトル生成ユニット２４１への制御信号は０である。これは開始インデックス１へ４を加算する事を表す。
【００８３】
１６ビットの１６個のデータから最大値あるいは最小値とそのインデックスを求めるようすを図２１に示す。図２１の右上から処理が始まる。
ｓｔｅｐ１において、プロセッサ２００は、初期選択値のベクトルデータとそれに対応するインデックス・ベクトル（初期インデックス）をそれぞれレジスタＲｃ、Ｒｄへ格納し、１回目の開始インデックスをレジスタＲｂへ格納する。
ｓｔｅｐ２において（図２１には図示されていない）、プロセッサ２００は、未処理のデータが１２個残っているので、ｓｔｅｐ３へ移行する。
【００８４】
ｓｔｅｐ３において、プロセッサ２００は、比較対象のデータ４個をレジスタＲａへ読み込む。
ｓｔｅｐ４とｓｔｅｐ５において、プロセッサ２００は、レジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄを使って、１回目のインデックス更新とレジスタ間比較選択処理を実行する。１回目のインデックス更新によって更新された開始インデックスはレジスタＲｂに格納される。１回目のレジスタ間比較選択処理によって選択されたデータとインデックスはレジスタＲｃとＲｄへそれぞれ格納される。この１回目のインデックス更新とレジスタ間比較選択処理に（１）という番号をつける。
【００８５】
この後は、ｓｔｅｐ２を省略すると、以下のように処理が進む。
（２）ｓｔｅｐ３：データ読み込み２回目
（３）ｓｔｅｐ４とｓｔｅｐ５：インデックス更新とレジスタ間比較選択処理２回目
（４）ｓｔｅｐ３：データ読み込み３回目
（５）ｓｔｅｐ４とｓｔｅｐ５：インデックス更新とレジスタ間比較選択処理３回目
【００８６】
（２）のｓｔｅｐ３において、プロセッサ２００は、新たなデータ４個をレジスタＲａへ読み込む。
（３）のｓｔｅｐ４とｓｔｅｐ５において、プロセッサ２００は、２回目のインデックス更新とレジスタ間比較選択処理を実行する。
同様にして、（４）、（５）が実行される。
【００８７】
図２１の（５）の後に、ｓｔｅｐ６が実行される。第二の実施形態におけるｓｔｅｐ６は第一の実施形態におけるｓｔｅｐ６と全く同じである。
ｓｔｅｐ６において、プロセッサ２００は、一つのレジスタに格納されたベクトルの全ての要素の中かから最大値あるいは最小値を探し、その値に対応するインデックスをもう一つのレジスタから取り出す。
ｓｔｅｐ６が実行されると、全てのデータの中の最大値あるいは最小値とそのインデックスが求まる。
【００８８】
以上説明したように、第二の実施形態の並列比較選択演算ユニットは、ベクトルデータ１と、ベクトルデータ２と、ベクトルデータ１の最初の要素のインデックスを表す開始インデックス１と、ベクトルデータ２の各要素のインデックスで構成されたインデックス・ベクトル２と、を入力信号とする。並列比較選択演算ユニットは、ベクトルデータ１とベクトルデータ２の各要素を比較し、その比較結果に基づいてベクトルデータ１とベクトルデータ２のどちらかを要素ごとに選択したベクトルデータ３を生成する。また、並列比較選択演算ユニットは、開始インデックス１に基づいてベクトルデータ１の他の要素のインデックスを生成し、生成されたインデックスと開始インデックス１とをインデックス・ベクトル１とし、比較結果に基づいてインデックス・ベクトル１とインデックス・ベクトル２のどちらかを要素ごとに選択し、選択された複数個の要素をインデックス・ベクトル３として生成し、ベクトルデータ１の要素の数と開始インデックス１の和を開始インデックス３として算出する。そして、並列比較選択演算ユニットは、ベクトルデータ３と、インデックス・ベクトル３と、開始インデックス３と、を出力する。
【００８９】
本実施形態の並列比較選択演算ユニットによれば、第一の実施形態に加え、次の効果を得ることができる。
まず、開始インデックスを用いることにより、インデックス・ベクトルを保持するレジスタの容量を削減することができる。具体的には図１のレジスタバンク２３０の容量を削減することができる。これは、第一の実施形態では、比較対象データのインデックスとして、要素数のインデックスを保持していたが、第二の実施形態では、開始インデックス一つに削減できるからである。
次に、更新ユニットを備えることにより、処理時間を削減することができる。具体的には、第一の実施形態では、プロセッサ２００が命令を実行することによりインデックスの更新（図８のｓｔｅｐ４）を実施していた。第二の実施形態では、インデックスの更新を並列比較選択ユニット内の更新インデックスによって実行させる。すなわち、ハードウェアによって実行させる。従ってプロセッサ２００が実行する命令の数を削減する。従って、全体の処理時間を削減することができる。
【００９０】
以上のように、本発明に係る実施形態の一態様によれば、インデックスをともなう最大値探索あるいは最小値探索のための並列比較選択演算装置を提供することができる。この並列比較選択演算装置及びその方法は、二つのベクトルデータを要素ごとに比較し、比較結果に基づいてどちらかの要素を選択するとともに、さらに比較結果に基づいて二つのベクトルデータに対応するインデックスについてもどちらかを要素毎に選択することができる。また、この並列比較選択演算装置を備えるプロセッサはインデックスをともなう最大値探索あるいは最小値探索を効率良く実行することができる。
【００９１】
また、本発明に係る実施形態の一態様によれば、複数の要素を含むベクトルの最大値または最小値及び対応するインテックスを、二入力の比較演算器を複数個使用して、効率よく探索することができる。
具体的には、複数の要素をレジスタに読み込み比較する。これにより、レジスタからベクトルの複数の要素を読み込むときの効率を向上させることができる。
また、二つの値を比較する比較演算器を複数個備え、二入力の比較演算器を複数個使用してベクトルの各要素を並列して比較し、ベクトルの最大値または最小値を探索する。二入力の比較演算器を複数個使用することは、多入力の比較演算器を使用する場合に比べ、処理遅延を小さくすることができる。また、回路の製造においても、二入力の比較演算器を複数個作ることは、多入力の比較演算器を作ることに比べて容易である。これによりコストを削減することも期待できる。
【００９２】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記によって限定されるものではない。本願発明の構成や詳細には、発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００９３】
この出願は、２００９年２月２日に出願された日本出願特願２００９−０２１１９９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００９４】
本発明を使用すれば、複数のデータの中から最大値あるいは最小値とそのインデックスを効率良く探す事ができる。最大値あるいは最小値を探索する処理はさまざまな情報処理分野で使われる基本的な処理である。従って、最大値あるいは最小値を効率良く探索可能な本発明は情報処理分野で幅広い応用が可能である。
【符号の説明】
【００９５】
１００  メモリ
２００  プロセッサ
２１０  命令デコーダ
２２０  命令実行ユニット
２３０  レジスタバンク
２４０、２４０ａ  並列比較選択演算ユニット
２４１  インデックス・ベクトル生成ユニット
２４２  ベクトル比較選択ユニット
２４３  インデックス・ベクトル選択ユニット
２４４  更新ユニット２４４
１０〜１４  分割ユニット
２０〜２３  結合ユニット
３０〜３３  比較選択ユニット
４０〜４４  選択ユニット
５０  比較ユニット
【図１】
0005500652.tif 000002
【図２】
0005500652.tif 000003
【図３】
0005500652.tif 000004
【図４】
0005500652.tif 000005
【図５】
0005500652.tif 000006
【図６Ａ】
0005500652.tif 000007
【図６Ｂ】
0005500652.tif 000008
【図６Ｃ】
0005500652.tif 000009
【図７】
0005500652.tif 000010
【図８】
0005500652.tif 000011
【図９】
0005500652.tif 000012
【図１０】
0005500652.tif 000013
【図１１】
0005500652.tif 000014
【図１２】
0005500652.tif 000015
【図１３】
0005500652.tif 000016
【図１４】
0005500652.tif 000017
【図１５】
0005500652.tif 000018
【図１６Ａ】
0005500652.tif 000019
【図１６Ｂ】
0005500652.tif 000020
【図１７Ａ】
0005500652.tif 000021
【図１７Ｂ】
0005500652.tif 000022
【図１８】
0005500652.tif 000023
【図１９】
0005500652.tif 000024
【図２０】
0005500652.tif 000025
【図２１】
0005500652.tif 000026