|
次のページ
前のページ
目次へ
4. SIMD Within A Register(例えば MMX を利用)SIMD(Single Instruction stream, Multiple Data stream) Within A Register(SWAR)は、新しいアイディアではありません。k ビットの レジスタとデータパス、演算装置を持つマシンでは、一般的なレジスタ処理は、 SIMD の並列処理で動くことが知られています。 つまり k/n ビットの整数領域の値として n 個 実行できます。 しかし最近になって SWAR 技術によってマルチメディア処理が 2 倍から 8 倍 早くなったことで、この技術がコンピューティングのメインストリームで関心 が持たれるようになったのに過ぎません。1997 年時点でのマイクロプロセッサ のほとんどは、組み込みのハードウェアで SWAR をサポートしています。
新しいマイクロプロセッサが提供しているハードウェア機能には、極秘に なっていたり、あるフィールドの大きさのためだけに必要な操作のような おかしなものはほとんどありません。重要な点は、SWAR の操作を効率的行う のにいかなるハードウェアのサポートも必要がないということです。 例えば、論理的に 1 つのレジスタを分割しても、ビットごとの演算には影響が でません。 4.1 SWAR の何が優れているのか?最近のプロセッサであればどれでも多かれ少なかれ SWAR の並列処理 機能を生かせます。ただ残念なことに、SWAR で大幅に機能強化された命令セット が、汎用的に並列処理に適用できるわけではありません。実際には、皆さんも Pentium と「MMX Pentium」の性能の違いは、MMX が発売されたと同時に搭載 されたより大きな L1 キャッシュ等のおかげであることに気づかれていると 思います。本当のところ、SWAR(もしくは MMX)は何が良いのでしょうか?
これらの制約は深刻ですが、このタイプの並列性はマルチメディアの アプリケーションだけでなく、並列アルゴリズムではよく生じることです。 アルゴリズムのタイプが適切であれば、SWAR は、SMP や クラスタの並列性 より有効ですし、使用するに当ってまったく費用がかかりません。 4.2 SWAR プログラミング入門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 ビットの値のベクトル
があることを表しています。 この後ドキュメントでは 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 ビット操作を使って
加算( 通常の 32 ビット加算は正確な値になると思いますが、それはどの 8 ビット
フィールドも次のフィールドに影響を与えない場合です。したがって、最終的
にはそのような桁上がりがまったく起こらないことを保証しなければいけません。
k ビットのフィールドを加算すると、多くても k+1 ビット
値になるので、桁上がりは単にそれぞれのフィールドの最上位のビットを「マスク
をかけること」で防げます。これはそれぞれのオペランドに対して
t = ((x & 0x7f7f7f7f) + (y & 0x7f7f7f7f)); これで、それぞれのフィールドの最上位ビットを除いて正確な値がでました。
それぞれのフィールドの値を正確に計算するには、
(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 ビットのベクトルの加算は次のようになります。まず分割操作をする前に、
繰り上げ用領域に当るビット(
((x + y) & 0x7f7f7f7f) これで、4 つの加算がちょうど 2 つの命令で済み、はっきりと速度が向上 します。 鋭い読者の方なら、繰り上げ用領域のビットを 0 にすると減算演算がうまく
ないことに気づかれたと思います。しかしこれはとても簡単に修正できます。
(((x | 0x80808080) - y) & 0x7f7f7f7f) しかし、追加したビット論理和演算は、最後の操作である
どの方法を SWAR の分割処理として使うべきなのでしょうか? 答は簡単で、 「一番速度が速いものならどれでも」です。興味深いことに、同じプログラム を同じマシンで実行しても、フィールドのサイズが異なれば最適な方法も変わる かもしれません。 値間のやりとりと型変換操作並列計算の中には画素に対する演算などのように、あるベクトル中の i 番目の値がオペランド側のベクトルの i 番目の位置にある値とだけ 相関関係にある場合がありますが、必ずしもこのケースとはかぎりません。 例えば、スムージングのような画素の操作は、隣の画素の値をオペランドとして 必要としますし、FFT(fast Fourier transform 高速フーリエ変換)のような変形 は、さらに複雑な(局所的ではない)やりとりをする傾向にあります。 一次元の隣接する値のやりとりを分割操作ではないシフト操作で実現するのは
難しいことではありません。
例えば、
(x << 8) しかしいつもそれほど単純とは限りません。例えば、
((x >> 8) & 0x00ffffff) 「折り返してつなげる」方法をとると、シフト操作を分割せずにそこそこ
効率的に行えます。例えばこの方法を使って
((x << 8) | ((x >> 24) & 0x000000ff)) さらに一般的なパターンのやり取りを実装しなければならないとなると、問題
が大きくなります。HP の MAX での命令セットに限って言うと、任意に
フィールドを再配置する命令が単独で存在します。この命令を
繰り返し操作(還元、走査など) 繰り返し処理は、計算している値間に逐次的な関係がはっきりと認められる 計算のことを指します。しかし、繰り返し処理に結合操作がある場合は、 木構造の並列アルゴリズムを使って、計算を記録できる場合があります。 最も一般的なタイプの並列化した繰り返し処理には、結合還元(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 ビットの値としてマスクしてしまうからです。 走査は「並列化した単項演算」とも呼ばれていて、効率的に実装するのはいくぶん 困難です。還元とは異なり、走査の結果が分割されるからです。このような訳で、 走査はきっと連続した分割操作として実装できます。 4.3 Linux における MMX を使った SWARLinux にとって 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 つあります。
要約すると、MMX を使った SWAR はまだ使い物になりません。しかし少し努力 すれば上記 2 番目の方法は現在でも利用できます。主要なポイントをあげます。
上記があまりに扱いづらく、洗練されていないと感じるなら、それはその 通りでしょう。しかし MMX はまだできたばかりで…このドキュメントの 将来の版では、もっと優れた MMX による SWAR をプログラムを提示できる と思います。 次のページ 前のページ 目次へ |
[ |