SIMD(Single Instruction stream, Multiple Data stream) Within A Register(SWAR)は、新しいアイディアではありません。k ビットの レジスタとデータパス、演算装置を持つマシンでは、一般的なレジスタ処理は、 SIMD の並列処理で動くことが知られています。 つまり k/n ビットの整数領域の値として n 個 実行できます。 しかし最近になって SWAR 技術によってマルチメディア処理が 2 倍から 8 倍 早くなったことで、この技術がコンピューティングのメインストリームで関心 が持たれるようになったのに過ぎません。1997 年時点でのマイクロプロセッサ のほとんどは、組み込みのハードウェアで SWAR をサポートしています。
【訳註：VIA の Web サイトはオンラインドキュメントの提供を停止しています】
【訳註：MAX は MVIという名称に変更されています】
新しいマイクロプロセッサが提供しているハードウェア機能には、極秘に なっていたり、あるフィールドの大きさのためだけに必要な操作のような おかしなものはほとんどありません。重要な点は、SWAR の操作を効率的行う のにいかなるハードウェアのサポートも必要がないということです。 例えば、論理的に 1 つのレジスタを分割しても、ビットごとの演算には影響が でません。
最近のプロセッサであればどれでも多かれ少なかれ SWAR の並列処理 機能を生かせます。ただ残念なことに、SWAR で大幅に機能強化された命令セット が、汎用的に並列処理に適用できるわけではありません。実際には、皆さんも Pentium と「MMX Pentium」の性能の違いは、MMX が発売されたと同時に搭載 されたより大きな L1 キャッシュ等のおかげであることに気づかれていると 思います。本当のところ、SWAR(もしくは MMX)は何が良いのでしょうか？
【訳註：2001.3 現在、Cyrix(現 VIA 傘下)のプロセッサでこの機能を 実装しているものはありませんし、予定も発表されていません】
x[y](y インデックスの配列)のようなベクトル
を集めてくる処理はとても重くなるこれらの制約は深刻ですが、このタイプの並列性はマルチメディアの アプリケーションだけでなく、並列アルゴリズムではよく生じることです。 アルゴリズムのタイプが適切であれば、SWAR は、SMP や クラスタの並列性 より有効ですし、使用するに当ってまったく費用がかかりません。
SWAR(SIMD Within A Register)の基本的なコンセプトは、ワード長レジスタ の操作を nk/n ビットのフィールド値を SIMD の並列演算をすることで、計算速度を向上させる点にあります。しかし、 SWAR 技術は扱いづらく、実際 SWAR の演算は同様な演算を行う順次演算を連続 して行ったのと比べて重くなります。それは SWAR の演算には、フィールドを 分割する命令がさらに加わるためです。
この点を説明するのに、SWAR のしくみをかなり単純化して考えてみること にしましょう。4 つの 8 ビットフィールド長を持つ 32 ビットのレジスタ があるとします。 2 つのレジスタの値は、下記のようになります。
PE3 PE2 PE1 PE0
+-------+-------+-------+-------+
Reg0 | D 7:0 | C 7:0 | B 7:0 | A 7:0 |
+-------+-------+-------+-------+
Reg1 | H 7:0 | G 7:0 | F 7:0 | E 7:0 |
+-------+-------+-------+-------+
この簡単な図はそれぞれのレジスタに 4 つの独立した 8 ビットの値のベクトル
があることを表しています。A と E が Reg0 と Reg1 の
プロセッシングエレメント 0(PE0)、B と F を PE1 の
レジスタ値とも見なせます。その他の項目も同様です。
この後ドキュメントでは SIMD 並列処理を分類し、ベクトルを扱う関数が どのように実装されているかをこの整数ベクトルを元にして概観していき ます。
SWAR の操作のいくつかは、通常の 32 ビット整数の操作そのままに処理 します。しかし実際には、この操作が並列して独立に 8 ビットのフィールド を操作することとは無関係です。このような SWAR の操作のことをポリモフィックと呼んでいます。その操作がフィールドのタイプ(サイズ) に影響されないためです。
どのフィールドがゼロでないかをテストするのは、すべてに対してビット論理
演算をする点でポリモフィックな操作と言えます。例えば、通常のビット論理
積演算(C の & 演算子)はフィールドの大きさがいくつであっても、
ビット演算となります。単純なビット論理積演算を上記のレジスタで行うと下記
のようになります。
PE3 PE2 PE1 PE0
+---------+---------+---------+---------+
Reg2 | D&H 7:0 | C&G 7:0 | B&F 7:0 | A&E 7:0 |
+---------+---------+---------+---------+
ビット論理積演算は常にオペランド・ビットの k という値に だけ左右されて k というビット値になるので、フィールドの大 きさはすべて同じ 1 つの命令を使ってカバーできます。
あいにく SWAR 操作で重要なものの中にも、ポリモフィックでない操作が たくさんあります。 四則演算のような算術演算では、フィールド間で桁の上げ下げをする必要が あります。 そのような操作を SWAR で行うことを「分割する」と呼んでいます。 理由は、そのような操作が事実上オペランドや結果を分割して、フィールド 間のやりくりを防がなければならないからです。実際この効果を生むのには 3 つの異なる手法が取られます。
おそらく、分割操作の中で最も理解しやすい実装方法は、「分割並列命令 (partitioned parallel instruction)」をハードウェアでサポートすることで しょう。これでフィールド間の桁の上げ下げを排除します。この方法を使えば パフォーマンスは文句なく上がりますが、プロセッサの命令セットが変更 されたり、フィールドの大きさに対しての制限が増えてしまいます (例えば、8 ビットのフィールドはサポートしても、12 ビットは駄目であるとか)。
AMD や Cyrix、Intel の MMX や Digital の MAX、HP の MAX、 Sun の VIS すべては、分割命令の実装に制限があります。残念なことに、それぞれの 命令セット拡張は制限事項についても著しく異なっているので、それらの間 では若干ですがアルゴリズムに移植性がなくなっています。例えば、下記で 分割命令の一部を見てみましょう。
Instruction AMD/Cyrix/Intel MMX DEC MAX HP MAX Sun VIS +---------------------+---------------------+---------+--------+---------+ | Absolute Difference | | 8 | | 8 | +---------------------+---------------------+---------+--------+---------+ | Merge Maximum | | 8, 16 | | | +---------------------+---------------------+---------+--------+---------+ | Compare | 8, 16, 32 | | | 16, 32 | +---------------------+---------------------+---------+--------+---------+ | Multiply | 16 | | | 8x16 | +---------------------+---------------------+---------+--------+---------+ | Add | 8, 16, 32 | | 16 | 16, 32 | +---------------------+---------------------+---------+--------+---------+
この表では数字がフィールドの大きさをビットで表していて、この値でそれぞれ の操作が可能になっています。もっと興味深い命令など多くの命令が表には 載っていませんが、この表だけでも違いの大きさは明らかです。結論としては、 明らかに高級言語(HLL)はプログラミング・モデルとしてまったく役に立たず、 移植性もほとんどないことです。
分割命令を使った分割操作を実装すれば確かに効果が上がりますが、もし必要 としている分割操作をハードウェアがサポートしていなかったらどうなる でしょう？ 答は、通常の命令群を使ってフィールド間で桁の上げ下げを行う 操作を行い、フィールド間での余計なやりとりを正します。
この手段はまさにソフトウェアによるもので、修正によるオーバーヘッド が加わります。しかし、これで汎用的にフィールドの分割が可能になります。 この方法は非常に汎用的で、ハードウェア毎の分割命令の違いを埋めるだけ でなく、まったくハードウェアのサポートのないマシンに対しても機能をフル に提供できます。実際には、C のようなプログラミング言語でコードを書く ことで、SWAR プログラムはとても移植しやすくなります。
ここで疑問が沸いてきます。SWAR の分割操作を使わずにコードを修正して シミュレートした場合、正確にどのくらい効率が落ちるのでしょうか？ いいところを突いた質問です…しかし、皆さんが思っているほど難しい操作が 多いわけではありません。
4 つの要素を持つ 8 ビットの整数ベクトル 2 つを 32 ビット操作を使って
加算(x+y)を実現することを考えてみましょう。
通常の 32 ビット加算は正確な値になると思いますが、それはどの 8 ビット
フィールドも次のフィールドに影響を与えない場合です。したがって、最終的
にはそのような桁上がりがまったく起こらないことを保証しなければいけません。
k ビットのフィールドを加算すると、多くても k+1 ビット
値になるので、桁上がりは単にそれぞれのフィールドの最上位のビットを「マスク
をかけること」で防げます。これはそれぞれのオペランドに対して 0x7f7f7f7f をビット単位で論理積を取った後、通常の 32 ビット加算をすれば OK です。
t = ((x & 0x7f7f7f7f) + (y & 0x7f7f7f7f));
これで、それぞれのフィールドの最上位ビットを除いて正確な値がでました。
それぞれのフィールドの値を正確に計算するには、x と y
2 つに分割された最上位の 1 ビットの値を 7 ビットで計算した t
に加算するだけです。都合のいいことに、分割した 1 ビットの加算は通常の
排他論理和演算として実装されています。
つまり、結果は単純に下記のように求められます。
(t ^ ((x ^ y) & 0x80808080))
そんなにやさしくはないですね。結局ちょうど 4 つの加算に 6 回の操作が 必要でした。しかし、操作の回数はフィールドの数がどのくらいあるか…と いうこととは関係ないことに注意してください。フィールドが増える程速度 が上がります。とにかく実際に速度が向上します。それはフィールドを 1 回 の操作(整数ベクトル)でロードやストアすることで、レジスタを利用する割合 が増え、動的にコードを実行するのに必要なスケジューリングの依存関係が ほとんどなくなるからです(部分的なワードへの参照を避けられるため)。
上記 2 つの方法とも、分割操作でレジスタを最大限利用するように実行する のに対して、この方法ではフィールドの値を制御することで、より効率的に 計算を行い、フィールド間の桁の上げ下げが決して起こらないようにします。 例えば、加算したフィールドすべてにおいてオーバーフローが生じないことが わかっている場合、分割操作の加算は通常の加算命令を使って実行できます。 実際この制約下で通常の加算命令はポリモフィックとなり、コードを修正する ことなしにどんなフィールドの大きさでも利用できることになります。ここで 問題なのは、どうしたらフィールドの値間で桁の上下げを起こさないかを確認 する方法です。
この特性を確認する方法の 1 つは、フィールドの値の範囲を制約する分割命令 を実装することです。Digital の MAX にあるベクトル最小最大命令は、 ハードウェアでこれをサポートしているようで、フィールドの値をある範囲で カットして、フィールド間で桁の上げ下げを起こさないようにしています。
しかし、フィールドの値の範囲を効率的に制限する分割命令がない場合は どうなるでしょうか…桁の上げ下げで隣のフィールドに影響を与えていない ことを手軽に保証する十分条件はあるのでしょうか？ その答は演算の特性 を分析することにあります。k ビットの 2 つの数を加算すると、 結果は多くても k+1 ビットです。したがって、k+1 ビットのフィールドなら、通常の命令を使っていても問題なく収まります。
つまり先にあげた例を 8 ビットのフィールドを 7 ビットに 1 ビットの 「桁の上げ下げ用の領域」を加えたものとしてみましょう。
PE3 PE2 PE1 PE0
+----+-------+----+-------+----+-------+----+-------+
Reg0 | D' | D 6:0 | C' | C 6:0 | B' | B 6:0 | A' | A 6:0 |
+----+-------+----+-------+----+-------+----+-------+
7 ビットのベクトルの加算は次のようになります。まず分割操作をする前に、
繰り上げ用領域に当るビット(A' や B'、C'、
D')すべてが 0 であると想定します。単純に通常の加算演算を行う
とすべてのフィールドは正しい 7 ビット分の値になります。しかし、繰り上げ
用領域のビットには、1 という値が入っているものが出てくるかもしれません。
これを修正するには、もう 1 回だけ通常の操作を行います。それは繰り上げ
用領域のビットにマスクをかけることです。7 ビット分の整数のベクトル加算
x+y はこのようになります。
((x + y) & 0x7f7f7f7f)
これで、4 つの加算がちょうど 2 つの命令で済み、はっきりと速度が向上 します。
鋭い読者の方なら、繰り上げ用領域のビットを 0 にすると減算演算がうまく
ないことに気づかれたと思います。しかしこれはとても簡単に修正できます。
x-y を計算するには、初期状態で x の繰り上げ
用領域のビットがすべて 1 で y がすべて 0 であることを保証すれば
いいのです。最悪の場合でもこのようにすれば良いはずです。
(((x | 0x80808080) - y) & 0x7f7f7f7f)
しかし、追加したビット論理和演算は、最後の操作である
& 0x7f7f7f7f の部分よりも x に
| 0x80808080 で値を出す操作のところで最適化できます。
どの方法を SWAR の分割処理として使うべきなのでしょうか？ 答は簡単で、 「一番速度が速いものならどれでも」です。興味深いことに、同じプログラム を同じマシンで実行しても、フィールドのサイズが異なれば最適な方法も変わる かもしれません。
並列計算の中には画素に対する演算などのように、あるベクトル中の i 番目の値がオペランド側のベクトルの i 番目の位置にある値とだけ 相関関係にある場合がありますが、必ずしもこのケースとはかぎりません。 例えば、スムージングのような画素の操作は、隣の画素の値をオペランドとして 必要としますし、FFT(fast Fourier transform 高速フーリエ変換)のような変形 は、さらに複雑な(局所的ではない)やりとりをする傾向にあります。
一次元の隣接する値のやりとりを分割操作ではないシフト操作で実現するのは
難しいことではありません。
例えば、PEi の値を PE(i+1) に移動
するには、単純なシフト操作で十分です。
フィールドが 8 ビットの大きさであれば、下記のようになります。
(x << 8)
しかしいつもそれほど単純とは限りません。例えば、PEi
を PE(i-1) に移動するには単純なシフト操作で十分で
あるかもしれません…が、C ではシフト操作が符号ビットを正しく維持できて
いるかどうかを確認できませんし、マシンの中には符号化シフトしか正しく
行えないものもあります。つまり一般的には、符号ビットのコピーを行って、
それを 0 に設定しておく必要があります。
((x >> 8) & 0x00ffffff)
「折り返してつなげる」方法をとると、シフト操作を分割せずにそこそこ
効率的に行えます。例えばこの方法を使って PEi を
PE(i+1)に移動するには、下記のようにします。
((x << 8) | ((x >> 24) & 0x000000ff))
さらに一般的なパターンのやり取りを実装しなければならないとなると、問題
が大きくなります。HP の MAX での命令セットに限って言うと、任意に
フィールドを再配置する命令が単独で存在します。この命令を Permute
と呼んでいます。Permute 命令という名付け方は不適切で、任意に
並べ替えを行うだけでなく、繰り返しもできてしまいます。つまり、自由に
x[y] 演算が可能になっています。
x[y] という操作は、そのような単独命令なしでは実現することが
非常に困難です。処理するコードが長くなるだけでなく、効率も下がります。
実際には順次処理になってしまいます。これではどうしようもありません。
x[y] 演算を比較的高速に行えるシステムが、MasPar の MP1/MP2
や Thinking Machines の CM1/CM2/CM200 という SIMD スーパーコンピュータ
であることがこれを裏付けています。しかし、そのようなスーパーコンピュータ
であっても、x[y] は隣り合ったフィールドとのやりとりと比べて常に
遅く、できるだけ x[y] 演算を必要としないようにアルゴリズムを設計
する場合がほとんどです。つまりハードウェアのサポートがなければ、
x[y] は演算として不適切と言っても…まあ少なくとも安価に実現できる
わけではありません。
繰り返し操作(還元、走査など) 繰り返し処理は、計算している値間に逐次的な関係がはっきりと認められる 計算のことを指します。しかし、繰り返し処理に結合操作がある場合は、 木構造の並列アルゴリズムを使って、計算を記録できる場合があります。
最も一般的なタイプの並列化した繰り返し処理には、結合還元(associative reduction)と言われるものがあります。例えばベクトルの合計を計算するのに、 C のコードで単に逐次処理すると下記のようになります。
t = 0; for (i=0; i<MAX; ++i) t += x[i];
しかし、加算の順序が意味を持つことはまれです。浮動小数点や飽和演算では、 加算の順序が違うと結果が変わってしまいますが、通常のラップラウンドな整数 の加算は順序によって結果に影響がでません。したがって、順次に実行する形 から木構造で並列に合計を出すコードに書き換えられます。こうすると、まず 最初に対となる値を加算し、それが合計値の一部となり…ということを繰り返し て、最終的に 1 つの合計値になるまで計算します。8 ビットの値を 4 つで構成 したベクトルならば、ちょうど 2 回の加算が必要となります。最初に 2 つの 8 ビットの値を加算して、16 ビットのフィールド 2 つに結果が入ります (フィールドそれぞれに 9 ビットの結果が入っています)。
【訳註：飽和演算とは、あらかじめ演算結果の範囲を決めておき、 その範囲を越えた演算結果になった場合にあらかじめ用意した結果に置き換える 処理です】
t = ((x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff));
その次に、16 ビットのフィールドに入っている 9 ビットの値を 2 つ加算して、 10 ビットの結果を 1 つ得ることになります。
((t + (t >> 16)) & 0x000003ff)
実際ここでは、16 ビットのフィールドを 2 つ加算したことになります…が、 先頭の 16 ビットの加算は意味がありません。というのは、結果を 1 つの 10 ビットの値としてマスクしてしまうからです。
走査は「並列化した単項演算」とも呼ばれていて、効率的に実装するのはいくぶん 困難です。還元とは異なり、走査の結果が分割されるからです。このような訳で、 走査はきっと連続した分割操作として実装できます。
Linux にとって IA32 プロセッサは一番の関心事です。AMD や Cyrix、 intel すべてが同じ MMX 命令を実装しているのは素晴らしいことです。 しかし、MMX のパフォーマンスにはばらつきがあります。例えば、K6 は MMX のパイプラインを 1 つしか持っていないのに対して、MMX Pentium は 2 つ 持っています。ただ intel がいまだにへんてこりんなコマーシャルをやっている のにはうんざりしていますが… ;-)
【訳註：2001.3 現在 Intel および AMD の高性能デスクトップ PC 用 プロセッサである PentiumIII と Athlon は整数演算の高速化である MMX を 拡張し、それぞれ SSE(internet streaming SIMD extensions)、Enhanced 3DNow! を実装し、浮動小数点演算の高速化をはかりました。 浮動小数点演算に関しては Pentium III の方が Athlon より高速と言われています が、浮動小数点の SIMD 命令については Athlon の方が高速と言われています。 大きな理由は、SSE が 64 ビットの演算装置で 128 ビットのオペランドを処理 するので 2 サイクルかかるのに対し、Enhanced 3DNow! は 64 ビットの演算装置 で 64 ビットのオペランドを処理するので 1 サイクルで済むためです】
SWAR に MMX を活用する方法は 3 つあります。
【訳註：2001.3 現在、Linux 用の MMX や 3DNow!、SSE のライブラリ 及びコンパイラ関連は、 The SWAR Homepage at Purdue University にあります】
要約すると、MMX を使った SWAR はまだ使い物になりません。しかし少し努力 すれば上記 2 番目の方法は現在でも利用できます。主要なポイントをあげます。
inline extern
int mmx_init(void)
{
int mmx_available;
__asm__ __volatile__ (
/* Get CPU version information */
"movl $1, %%eax\n\t"
"cpuid\n\t"
"andl $0x800000, %%edx\n\t"
"movl %%edx, %0"
: "=q" (mmx_available)
: /* no input */
);
return mmx_available;
}
unsigned long long を
呼び出した場合にそれを保持する。つまりメモリベースのこの型の変数は、
MMX モジュールとそれを呼び出した C プログラム間のやりとりの手段となる。
その一方で、MMX データを 64 ビットにアラインしたデータ構造として宣言
できる(unsigned long long の大きさを持つ union
として型宣言することで、簡単に 64 ビットにアラインされていることを保証
できる)
.byte を使って MMX
コードが書け、命令をエンコードできる。
これは手作業では骨が折れるが、コンパイラでコードを生成するのは難しく
ない。例えば、MMX 命令の PADDB MM0,MM1 は GCC のインライン・
アセンブラのコードで下記のようにエンコードできる
__asm__ __volatile__ (".byte 0x0f, 0xfc, 0xc1\n\t");
EMMS 命令を実行する。
エンコードすると下記のようになる
__asm__ __volatile__ (".byte 0x0f, 0x77\n\t");
上記があまりに扱いづらく、洗練されていないと感じるなら、それはその 通りでしょう。しかし MMX はまだできたばかりで…このドキュメントの 将来の版では、もっと優れた MMX による SWAR をプログラムを提示できる と思います。