(57)【特許請求の範囲】
【請求項１】
入力レジスタの内容を操作して、前記入力レジスタの前記内容の並べ換えを行った出力レジスタの内容を生成するための装置において、
前記入力レジスタを、夫々前記入力レジスタ中の位置及び１ビットを超える長さで特徴つけられる複数のサブワードに区分するための手段と、
命令に応答して、前記複数のサブワードの内の２つ以上それぞれを、前記入力レジスタ中で前記サブワードが占める前記位置とは異なる、前記出力レジスタの中の位置の１つ以上に振り当て、サブワードの繰り返しを伴う並べ替えを行うための手段と
を設けたことを特徴とする並べ換え装置。
【請求項２】
入力レジスタの内容を操作して、前記入力レジスタの前記内容の並べ換えを行った出力レジスタの内容を生成するための装置において、
前記入力レジスタを、夫々前記入力レジスタ中の位置及び１ビットを超える長さで特徴つけられる複数のサブワードに区分するための手段と、
命令に応答して、前記複数のサブワードの内の２つ以上それぞれを、前記入力レジスタ中で前記サブワードが占める前記位置とは異なる、前記出力レジスタの中の位置の１つ以上に振り当て、逆順並べ換え、シャッフル並べ換え、混合並べ換え、交番並べ換え、同報並べ換え、または交換並べ換えを行うための手段と
を設けたことを特徴とする並べ換え装置。
【請求項３】
前記命令が、前記出力レジスタの内容を指定するビット・パターンを含むこと
を特徴とする請求項１に記載の並べ換え装置。
【請求項４】
前記出力レジスタの前記内容が、前記命令によって識別されるワードによって指定されること
を特徴とする請求項１に記載の並べ換え装置。
【請求項５】
前記出力レジスタの前記内容が、前記命令中の値によって指定され、前記値が予め定められた並べ換え集合中の並べ換えの何れかを指定すること
を特徴とする請求項１に記載の並べ換え装置。
【請求項６】
前記並べ換え集合中の前記並べ換えの１つが、逆順並べ換え、シャッフル並べ換え、混合並べ換え、交番並べ換え、同報並べ換え、交換並べ換え、または条件付き交換並べ換えの何れかであること
を特徴とする請求項５に記載の並べ換え装置。
【請求項７】
前記振り当て手段が、前記入力レジスタ中のサブワードを前記出力レジスタ中の複数のサブワードの任意の１つに結合する複数のマルチプレクサを設けたこと
を特徴とする請求項１に記載の並べ換え装置。
【請求項８】
第１のステージと最終ステージを含む複数の順序付きマルチプレクサ・ステージを設け、
マルチプレクサの前記第１のステージが入力として前記入力レジスタの内容を与えられ、
マルチプレクサの前記最終ステージが出力として前記出力レジスタの前記内容を与え、
前記マルチプレクサが夫々入力と出力の間の接続を指定する制御ラインによって制御され、
シフト操作を行う際には前記各ステージ中の前記マルチプレクサが全て前記制御ライン上で同じ制御信号を受信する、入力レジスタの内容をシフトして出力レジスタの内容を生成するための装置
を備えたデータ処理システムにおいて、
前記入力レジスタの内容の並べ換えを指定する命令に応答して前記マルチプレクサの少なくとも１つのステージの前記制御ラインを別個に制御することによって、前記ステージ中の別のマルチプレクサに供給される前記制御信号とは異なる制御信号が、前記ステージ中の少なくとも１つのマルチプレクサに供給されるようにしたこと
を特徴とするデータ処理システム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、コンピュータに関連するものであり、とりわけ、それに用いられるシフタ装置に関するものである。
【０００２】
【従来技術及びその問題点】
コンピュータ・プロセッサは、一般に特定のワード・サイズについて最適化される。例えば、３２または６４ビットに対して最適化されたプロセッサが市販されている。プロセッサ・レジスタ及びデータ経路は、同様に、設計ワード幅と同じ幅のオペランドを効率よく処理するように設計されている。同じレジスタ及びデータ経路でそれより狭いオペランドの処理を行うことは可能であるが、データ経路の利用効率が悪くなる。
【０００３】
多くのアプリケーションについてのデータの精度は、データを操作するコンピュータのワードのビット・サイズよりも小さいことがしばしばある。このようなシステムの場合、複数のデータ項目を単一ワードにパックするのが有利である。これによって、データに必要とされる記憶域が減少し、メモリには、通常、ワード単位でアクセスするので、メモリのアクセス時間が短縮される。しかし、ワード中のデータ項目を再配列しなければならない場合には、それによって追加される処理時間が、データがワードにパックされなければ被るメモリ・アクセス時間より長くなるかもしれないので、この利点の多くが損なわれる。
【０００４】
例えば、イメージアプリケーションは、多数の短いデータ・ワードを取り扱うことがしばしばある。例えば、白黒イメージは、各ピクセルがイメージ中の１点の輝度を表す８ビットの整数である、ピクセル値のアレイとして表現されることがしばしばある。１０００×１０００のピクセル・イメージは、１００万バイトの記憶を必要とする。イメージ・データの効率的な記憶及び移動を行うため、データはより大きいワードにパックされることがしばしばある。例えば、６４ビット・データ・ワードについて最適化されたコンピュータ・システムでは、８つのピクセル値を、夫々６４ビット・ワードにパックすることができる。これにより、単一メモリ・サイクルで８ピクセルが移動できるようになり、同時に、イメージの記憶に必要なメモリ・ワード数が減少する。あいにく、個々のピクセル値について計算を実行しなければならない場合には、何らかの形のパック解除操作を利用して、残りのピクセル値から個々の値を分離しなければならない。
【０００５】
一般に、従来のコンピュータ・プロセッサは、２つのオペランドを利用する。このオペランドは、通常、２つのレジスタに記憶される。このプロセッサは、命令によって指定されたこれらのオペランドを変換し、次に、その結果を別のレジスタに書き戻す。レジスタに複数のオペランドをパックする場合、レジスタ内でこれらのオペランドの再配列つまり並べ換えを実行可能であることが望ましい場合が多い。先行技術によるシステムでは、プロセッサは、レジスタの内容を基本単位として取り扱うように最適化されているので、このような再配列は時間を浪費する。一般に、レジスタ内の指定されたフィールドは、一連のシフト及びマスキング操作によってしか抽出することはできない。例えば、レジスタ内の４つのデータ項目の一般的な並べ換えには、通常、大部分の汎用プロセッサではかなりの個数の命令を必要とする。
【０００６】
【目的】
本発明の目的は、一般に、改良された機能単位を提供することにある。
【０００７】
本発明のもう１つの目的は、データ・ワードのサブフィールドの並べ換えを、繰り返し付きで、あるいは繰り返しなしで、単一命令で行うことができる機能単位を提供することにある。
【０００８】
本発明の以上の及びその他の目的については、当業者には、本発明に関する下記の詳細な説明及び添付の図面から明らかになるであろう。
【０００９】
【概要】
本発明は、入力レジスタの内容に操作を加えて、入力レジスタの内容を並べ換えたものを含む出力レジスタの内容を生成するための装置である。この装置は、入力レジスタを、夫々入力レジスタ内の位置と１ビットを超える長さで指定される複数のサブワードに区分する。本発明は、入力レジスタの再配列を指定する命令に応答して、入力レジスタ内のサブワードの少なくとも１つを、入力レジスタ内でそのサブワードが占める位置とは異なるところの出力レジスタ内の位置に振り当てる。出力レジスタ内のこれらのサブワードの順序は、単一のシフト命令によって達成することのできる順序とは異なる。本発明の望ましい実施例では、本発明は、マルチプレクサの複数のレイヤを設けた従来のシフタを修正することによって実現される。この修正は、少なくとも１つのレイヤ中の少なくとも１つのマルチプレクサについての制御信号を独立してセッティングすることを含む。
【００１０】
【実施例】
本発明の動作方法については、本発明による並べ換えプロセッサ２０のブロック図である図１を参照することによって、より容易に理解することができるだろう。一般に、プロセッサ２０は、いくつかのデータ項目がパックされているソース・レジスタ１５の内容を操作する。図１に示す例では、各レジスタ中にはパックされた４つの項目が存在する。ソース・レジスタ１５中の項目は１１〜１４で示されている。並べ換えプロセッサ２０は、ソース・レジスタ１５中のデータ項目を再配置して、ターゲット・レジスタ２５中にデータ項目を生成する態様を指定した順序ワードを受け入れる。本発明の望ましい実施例では、並べ換えプロセッサ２０は、ターゲット・レジスタ、順序ワード、及びソース・レジスタを指定する命令を受け入れる。
【００１１】
並べ換えプロセッサ２０は、繰り返しを伴う並べ換えと繰り返しを伴わない並べ換えの両方をサポートする。繰り返しを伴わない並べ換えでは、ソース・レジスタ内のデータ項目はターゲット・レジスタ内で順序を付け直されるが、項目の複写または消去は行われない。図１に示す再配列は、繰り返しを伴わない並べ換えの例である。ソース・レジスタ１５には、データ要素「ａｂｃｄ」が含まれている。ソース・レジスタ１５の繰り返しを伴わない並べ換えは、「ｂｃａｄ」である。繰り返しを伴う並べ換えの例には、「ｃｂｂｄ」がある。繰り返しを伴う並べ換えは、「組み合わせ」の特定の例である。組み合わせでは、重要なのは各要素の繰り返し回数だけである。すなわち各要素の順序は重要ではない。例えば、「ａａｂｂ」及び「ａｂａｂ」は同じ組み合わせであるが、繰り返しを伴う異なる並べ換えである。本書で用いられる並べ換えという用語は、文脈中で別の指示がない限り、繰り返しを伴う並べ換え及び伴わない並べ換えと、組み合わせの両方を表している。
【００１２】
本発明の一実施例では、順序ワードは、ターゲット・レジスタに項目が現れるべき順序でこれらの項目が並んでいる、ターゲット・レジスタ中の項目のリストである。順序ワード中のビット数は、各レジスタにパック可能な最大データ項目数によって決まる。図１に示す例では、ソース・レジスタ及びターゲット・レジスタは、夫々４つのデータ項目を備えている。可能性のある４つのデータ項目の１つであるデータ項目を指定するには２ビットが必要になる。従って、この例では、順序ワードは、４つの２ビット・サブワードとして編成される８ビットを必要とする。ソース・レジスタ中の項目は、０〜ｎ−１とラベル付けされる。図１に示す並べ換えに関する順序ワードが、２６に示されている。同様に、「ａｂｃｄ」→「ｃｂｂｄ」という組み合わせ再配列は、（１０ ０１ ０１ １１）という順序ワードによって表現される。
【００１３】
本発明のこの実施例では、並べ換えプロセッサ２０は、ほぼ全ての汎用コンピュータの整数データ経路中に存在するシフタを修正したものを利用して実現される。本発明の望ましい実施例では、シフタは複数のマルチプレクサ・ステージを設けている。本発明の望ましい実施例において必要とされるのは、これらのマルチプレクサ・ステージの少なくとも１つにおいて、各マルチプレクサ毎に独立した制御が確立されることだけである。
【００１４】
しかし、従来のシフタを上述のように修正したものを利用した本発明の望ましい実施例について解説する前に、本発明による並べ換えプロセッサを実現したものに関するブロック図である図２を参照して、本発明の幾分単純な実施例について解説することにする。本発明のこの実施例は、単一のマルチプレクサ・レイヤ４５を用いて実施される。本発明のこの実施例では、ソース・レジスタ５５中の各サブワードは、対応するマルチプレクサによって、ターゲット・レジスタ６５中の可能性のある各サブワードに結合される。ソース・レジスタのサブワードが５１〜５４で示され、ターゲット・レジスタのサブワードが６１〜６４で示されている。本発明のこの実施例では、マルチプレクサはターゲット・レジスタのサブワードに対応づけられており、ターゲット・レジスタのサブワード６１〜６４に対応したマルチプレクサが夫々４１〜４４で示されている。各マルチプレクサは、上述の順序ワードを保持する順序レジスタ７５の異なるサブワードによって制御される。各マルチプレクサはサブワードを移動させる。従って、サブワードの長さが８ビットの場合、各マルチプレクサは８ビット幅のマルチプレクサである。
【００１５】
図２に示す実施例は比較的単純であるけれども、従来の汎用コンピュータで実現するには、汎用コンピュータの処理装置にハードウェアを追加することが必要になる。上述のように、本発明の望ましい実施例は、従来のシフタに既に存在するマルチプレクサを共用し、これによって、従来のコンピュータ設計にマルチプレクサを追加する必要をなくすことによって、図２に示す実施例に対して更なる利点が得られるようにする。
【００１６】
以下の説明を単純化するため、特定のワード・サイズを使用するが、当業者には明らかなように、この例の教示を利用して、他のワードサイズを実現することもできる。６４ビット・ワードを使用するコンピュータについて考察する。このようなコンピュータ中の従来のシフタは、図３に１００で示す３ステージの４：１マルチプレクサとして実現することができる。最初のステージは１６ビットの倍数、すなわち０、１６、３２、または４８ビットだけ入力をシフトする。第２ステージ１８５は、このステージへの入力を、４ビットの倍数、すなわち０、４、８、または１２ビットだけシフトする。最終ステージ１８６は、１ビット単位で０〜３ビットだけ入力をシフトする。シフタが、０〜６４ビットのシフトを行うものとして実現される場合、最終ステージは、入力を４ビットまで右にシフトする。しかし、単純化のため、以下の説明では０〜６３ビットのシフト範囲であると仮定する。
【００１７】
従来の制御ラインを変更してマルチプレクサの制御を順序レジスタの内容によって決まる値に設定できるならば、１６ビットのサブワードが並べ換えに用いられる場合、シフタ１００の最初のステージは図２に示す本発明の単純な実施例と全く同じになる。このような構成が図３に示されており、最初のステージのマルチプレクサ１４１〜１４４は順序レジスタ１７５の内容によって制御される。並べ換え生成器として用いられる場合、第２及び第３ステージのマルチプレクサの制御ラインはゼロにセットされる。シフタとして用いられる場合、順序レジスタは最初のステージマルチプレクサの夫々に同じ入力が供給されるようにセットされ、１８５及び１８６で示すマルチプレクサの第２及び第３ステージは従来の態様でセットされる。
【００１８】
以上の説明では、ソース・レジスタ１５５及びターゲット・レジスタ１６５は、並べ換えを実現するため、１６ビット以上のサブワードに分割されるものと仮定された。もっと短いサブワードが必要とされ、また並べ換えの全集合を生成しなければならない場合、本発明の望ましい実施例では、マルチプレクサの最初のステージがこのような並べ換えを実現できるようにシフタを再設計した、シフタの異なる実施例が使用される。例えば、８ビットのサブワードを使用すべき場合、上述の６４ビット・シフタは、２ステージのマルチプレクサとして実現できる。従って、最初のステージで、並べ換えの全集合を生成することができる。
【００１９】
全集合よりも小さい並べ換え集合しか生成する必要がないなら、並べ換えの所望の部分集合に応じて、第２ステージ及び／または第３ステージのマルチプレクサも使用するという設計もできる。この設計では、第２及び／または第３ステージのマルチプレクサの制御ラインは、許容される並べ換えの集合中の少なくとも１つの並べ換えに関して、これらのステージ中のマルチプレクサの少なくとも１つが、当該ステージ中の他のマルチプレクサとは異なる制御信号を受信するように設定される。
【００２０】
コンピュータ・プログラムの一部としてしばしば実行される、数学計算の実現にとりわけ有効ないくつかの並べ換えが存在する。これらについては、下記の表Ｉに要約されている。例示のため、ソース・レジスタは、「ａｂｃｄｅｆｇｈ」で表示の８つのサブワードに分割されるものと仮定する。
【００２１】
【表１】
0003891609.tif 000002
【００２２】
シャッフル並べ換え及び混合並べ換えは、入力レジスタを２つの４サブワード・レジスタとして取り扱う。第１のレジスタからの１つのサブワードと第２のレジスタからの１つのサブワードを交互に取り出すことによって、出力レジスタの内容がアセンブルされる。交番(alternate)並べ換えは、サブワードを１つおきに出力レジスタに移動し、次に残りのサブワードを移動する。同報並べ換えは、同じサブワードを出力レジスタの全ての位置でを繰り返す。上の表Ｉのリストには、可能性のある同報並べ換えのうちの２つだけしかないが、当業者には明らかなように、同報並べ換えは入力レジスタ中の任意のサブワードについて行うことができる。最後に、交換並べ換えはサブワード各対の順序を逆にする。
【００２３】
当業者には明らかなように、本発明に他の特殊な並べ換えを組み込むのが有利なこともある。例えば、条件付き交換を実現する、つまり並べ換えを指定する命令中の各サブワード対に対応するビット値に従ってサブワードを条件付きで並べ替える、こともできる。この実現形態は、８つのサブワードの１６通りの異なる特定の並べ換えのうち任意のものを４ビットだけで指定することができる。問題となる１６通りの並べ換え及び対応する４ビットを表ＩＩに示す。
【００２４】
【表２】
0003891609.tif 000003
【００２５】
本発明の上述の実施例は、命令に含まれる順序ワードを利用するものであるが、順序ワードが間接的に指定される実施例も可能である。順序ワードの長さが命令の許容可能な長さを超えるためにサブワード数が対応する順序ワードを１命令に収容する妨げとなるほどに多くなる場合には、このような実施例がとりわけ有効である。このような実施例では、順序ワードは、命令中で指定される１つまたは複数のレジスタに置くことができる。順序ワードは、命令に中で指定されたメモリのアドレスに置くこともできる。最後に、順序ワードは、予め定められたロケーションに置くこともできる。この場合、命令は順序ワードのロケーションを暗黙裡に指定する。
【００２６】
並べ換えの全集合を実現するのではない実施例では、実現される並べ換えに番号を付けてもよい。この場合、命令または命令によって指示されるレジスタが並べ換え番号を含む。すると、適切なマッピング・テーブルが並べ換え番号をそれと等価な順序ワードに変換する。
【００２７】
上述の実施例は、レジスタにストアされる順序ワードに関して説明したが、順序ワードが実際にはレジスタに入っていない実現形態も可能である。このような実現形態では、順序ワードの諸ビットは、マルチプレクサの適切な制御ラインによって直接生成される。例えば、並べ換えの部分集合しか実際には行われない実施例では、並べ換え番号を変換するマッピング回路は、並べ換えを実際に行うマルチプレクサに与えるための対応する論理信号を発生することしか必要とされない。これらの実施例では、「順序ワード」は適切ないくつかの信号ライン上の論理レベルの集合として存在するだけである。
【００２８】
以上の説明では、出力レジスタ中のサブワードの少なくとも１つが入力レジスタ中の対応するサブワードとは異なる並べ換えが強調されたが、当業者には明らかなように、本発明は入力レジスタと出力レジスタが同一になる恒等並べ換えもサポートする。
【００２９】
当業者には、以上の説明及び添付の図面から本発明に対する各種修正が明らかであろう。従って、本発明は請求の範囲によってのみ限定されるとしなければならない。
【００３０】
以下に本発明の実施の態様の例を列挙する。
【００３１】
［実施の態様１］入力レジスタの内容を操作して、前記入力レジスタの前記内容の並べ換えを行った出力レジスタの内容を生成するための装置において、
前記入力レジスタを、夫々前記入力レジスタ中の位置及び１ビットを超える長さで特徴つけられる複数のサブワードに区分するための手段と、
命令に応答して、前記サブワードの少なくとも１つを、前記入力レジスタ中で前記サブワードが占める前記位置とは異なる、前記出力レジスタ中の位置に振り当てるための手段
を設けたことを特徴とする並べ換え装置。
【００３２】
［実施の態様２］前記入力レジスタ中の前記サブワードの少なくとも１つが、前記出力レジスタに２回以上現れることを特徴とする、実施の態様１に記載の並べ換え装置。
【００３３】
［実施の態様３］前記命令が、前記出力レジスタの内容を指定するビット・パターンを含むことを特徴とする、実施の態様１に記載の並べ換え装置。
【００３４】
［実施の態様４］前記出力レジスタの前記内容が、前記命令によって識別されるワードによって指定されることを特徴とする、実施の態様１に記載の並べ換え装置
【００３５】
［実施の態様５］前記出力レジスタの前記内容が、前記命令中の値によって指定され、前記値が予め定められた並べ換え集合中の並べ換えの何れかを指定することを特徴とする、実施の態様１に記載の装置。
【００３６】
［実施の態様６］前記並べ換え集合中の前記並べ換えの１つが、逆順並べ換え、シャッフル並べ換え、混合並べ換え、交番並べ換え、同報並べ換え、交換並べ換え、または条件付き交換並べ換えの何れかであることを特徴とする、実施の態様５に記載の並べ換え装置。
【００３７】
［実施の態様７］前記振り当て手段が、前記入力レジスタ中のサブワードを前記出力レジスタ中の複数のサブワードの任意の１つに結合する複数のマルチプレクサを設けたことを特徴とする、実施の態様１に記載の並べ換え装置。
【００３８】
［実施の態様８］第１のステージと最終ステージを含む複数の順序付きマルチプレクサ・ステージを設け、マルチプレクサの前記第１のステージが入力として前記入力レジスタの内容を与えられ、マルチプレクサの前記最終ステージが出力として前記出力レジスタの前記内容を与え、前記マルチプレクサが夫々入力と出力の間の接続を指定する制御ラインによって制御され、シフト操作を行う際には前記各ステージ中の前記マルチプレクサが全て前記制御ライン上で同じ制御信号を受信する、入力レジスタの内容をシフトして出力レジスタの内容を生成するための装置を備えたデータ処理システムにおいて、
前記入力レジスタの内容の並べ換えを指定する命令に応答して前記マルチプレクサの少なくとも１つのステージの前記制御ラインを別個に制御することによって、前記ステージ中の別のマルチプレクサに供給される前記制御信号とは異なる制御信号が、前記ステージ中の少なくとも１つのマルチプレクサに供給されるようにしたことを特徴とするデータ処理システム。
【図面の簡単な説明】
【図１】本発明による並べ換えプロセッサのブロック図。
【図２】マルチプレクサの単一レイヤを用いて実現された、本発明による並べ換え及び組み合わせプロセッサの実施形態に関するブロック図。
【図３】本発明の実施例を与えるように修正された、従来のシフタの一部に関するブロック図。
【符号の説明】
１５：ソース・レジスタ
２０：並べ換えプロセッサ
２５：ターゲット・レジスタ
４１、４２、４３、４４：マルチプレクサ
４５：マルチプレクサ・レイヤ
５５：ソース・レジスタ
６５：ターゲット・レジスタ
７５：順序レジスタ
１００：シフタ
１４１、１４２、１４３、１４４：マルチプレクサ
１５５：ソース・レジスタ
１６５：ターゲット・レジスタ
１７５：順序レジスタ
【図１】
0003891609.tif 000004
【図２】
0003891609.tif 000005
【図３】
0003891609.tif 000006