レベル: 中級 Peter Seebach (developerworks@seebs.plethora.net), Freelance author, Plethora.net
2007年 8月 07日 Cell Broadband Engine (Cell/B.E.) プロセッサの Synergistic Processor Engine™ (SPE) は SIMD 専用アーキテクチャであり、スカラー演算能力を持っていません 全ての演算は 16 バイトのベクトルで行われます。プログラマは Cell/B.E. コンパイラがこのアーキテクチャを効果的に利用しやすいコードを設計する必要があります。
Cell/B.E. プロセッサの SPE は非常に特殊なアーキテクチャを持っています。それはスカラー演算能力を持っていない -- 全ての演算は 16 バイトのベクトルで行われるという、ユニークなものです。これによるパフォーマンスのトレードオフは多くの種類の計算には有利なものですが、適しない計算もあります。この点は開発者にとって隠れた挑戦課題です。
この記事では、通信モデルから少し離れ、SPE で実行されるコードの設計について特に見ていきます。
SPE については数多くの解説が公開されています (参考文献)。SPE のアーキテクチャは小さなダイ (訳注：半導体チップ) 面積で良いパフォーマンスを出すように構築されています。この目標を達成するための多くの方法のうちのひとつは、命令セットと命令と処理の機能を劇的に単純化して、いくつかの仕事はコンパイラと開発者に引き継ぐ (offload) ことです。非常によいコンパイラでさえ SPE の効率的な利用からは程遠いものです。
次のセクションでは SPE の構造に合わせた設計の内容を見ていきましょう。
SPE に適したタスク
まず第一には、明らかに他のプロセッサよりも SPE に適しているタスクがいくつかあります。あるタスクは容易に並列化でき、32 ビットの要素をグループとして実行するため、とてもぴったりはまります。多数の分岐が必要で主に単独のスカラーに対して演算をするようなタスクは、適しません。このようなタスクをオフロードすることは PPE だけを使用するよりはまだよいかもしれませんが、パフォーマンスがプロセッサの理論計算性能に近づくことはないでしょう。
SPE は標準的なプロセッサが通常使用する方法による、直接的なスカラー命令は持っていません。PPE はスカラーと SIMD 演算の両方が使用できますが、SPE は SIMD 演算だけしか持っていません。1 つの命令で 32 ビットの語の組を加え合わせることはできません。しかし、その必要性を考えたとき、この機能は多くの方法で代用できます。
最も高速な解法としては、単純に使われない 32 ビットの語を 3 つ、計算に使いたい後の付近に格納して SIMD 命令で計算すれば、その 3 つの語は無視されます。
容量が貴重なときは (ローカルストアは 256KB しかありません)、関心のある語を変更するときにマスク演算を使用して他の語をそのままにするという別の選択肢があります。
これらの選択肢はそれぞれ、適するアプリケーションもあれば、適しないアプリケーションもあります。ローカルストアはデータとコードで共有されるため、変更されるオブジェクトがやや大きなデータセットのひとつでない限りはマスク演算を使うことはめったにありません。さもなくば、複数のオブジェクトを与えられた 16 バイトの後に格納する時に節約できるスペースはコードサイズの増加によってすぐに使い尽くされてしまいます。
どちらの方法にしても、本来的なスカラー命令は存在しませんし、SPE では並列演算は常にタダで使えるのですから、複数の類似したタスクを同時に実行できる時はいつでも並列演算するべきです。
選択演算を使う
スカラープロセッサでは、(常にではありませんが)たいていは不要な演算の実行を避けることは実りある努力です。SIMD プロセッサでは、無条件に複数の演算を実行し、それからマスク演算を使って変更された値と変更されていない値をマージするほうが良いことがしばしばあります。
単純な例として、配列全体の絶対値を計算する関数を考えてみましょう。
リスト 1. Look at those abs()!
void
int_abs(int a[], int len) {
int i;
for (i = 0; i < len; ++i)
if (a[i] < 0)
a[i] = 0 - a[i];
}
|
簡潔さのため、値は常にこの演算が実行できる程度に小さいものとします。この解法は十分単純ですが、SPE でこれを実装するとひどく遅いでしょう。ループ毎の各反復は分岐を含んでおり、分岐は SPE の命令デコードバッファには扱いにくいものだからです。
SPU の組み込み関数を使用して書き直せば、分岐を削除することができます。
リスト 2. Using selection instead of branches
void
int_abs(vector signed int a[], int len) {
int i;
vector signed int z = spu_splats(0);
for (i = 0; i < len; ++i) {
vector int vec_abs = spu_sub(z, a[i]);
a[i] = spu_sel(a[i], vec_abs, spu_cmpgt(z, a[i]));
}
}
|
一見複雑に見えますが、実はそれほどでもありません。このコードでは、2 種類のコードパス (path) の間を分岐するよりも単純に、与えられたベクトルの全項目の反転を計算して、選択演算を用いて変更前の結果と反転した結果を混ぜ合わせます。比較演算は特別な選択マスクを作成するので、これを spu_sel() 組み込み命令が 2 つのベクトルから要素を選び出すための引数として使用します。この例では、a[i] の要素よりも 0 が大きいような全ての要素 (訳注：つまり、a[i] が負ならば) が、vec_abs() の対応する要素で置き換えられます。
反復タスク
後続ステップが前のステップの結果に依存するような、本質的に反復的でであるタスクもあります。このようなタスク単独では各ステップを並列化することはできませんが、このようなタスクをいくつか同時に実行することはできるかもしれません。実行されるタスク内容の項目によっていくつか種類があるような場合でも、2 つの異なるタスクを処理して結果をマージするために選択演算を使うことが十分に見合うこともあります。
 |
Collatz conjecture
The Collatz conjecture (seeresources) is an unsolved conjecture in mathematics named after Lothar Collatz who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanislaw Ulam), the Syracuse problem, as the hailstone sequence or hailstone numbers, or as Wondrous numbers as per Gödel, Escher, Bach. It asks whether a certain kind of number sequence always ends in the same way, regardless of the starting number. Although the conjecture has not been proven, most mathematicians who have looked into the problem believe intuitively that the conjecture is true due to one or both of two reasons:
- Experimental evidence. The conjecture has been checked by computer for all start values up to 10 X 258 ≈ 2.88 X 1018. While impressive, such computer bounds are of very limited evidential value since several conjectures have turned out to have exceptionally large-valued counterexamples (such as the Pólya conjecture).
- Probabilistic evidence. If you consider only the odd numbers in the sequence generated by the Collatz process, then you can argue that on average (specifically, the geometric mean of the ratios) the next odd number should be about 3/4 of the previous one which suggests that they should decrease in the long run (although this is not evidence against cycles, only against divergence).
|
|
どのような種類のタスクが良い例になるか前もって予測することは難しいのですが、私が好きなおもしろい数学的課題はこの種のタスクのよい例です。x が奇数のときに (3x+1)、x が偶数のときは (x/2) と定義されているある数学関数 f(x) が定義されているとします。 コラッツの問題 (Collatz conjecture) とは、すべての整数 x に対して、十分反復を繰り返すとこの f(x) が 1 に収束するというものです。10x2^58 までのすべての x については確認されており、これは 32bit の符号付き型に格納できるすべての値では予想が正しいことを意味しています。値が 1 になるまでの反復回数は (訳注：x の初期値によって) 非常に幅があり、与えられた値が必要とする反復回数を計算するには、反復処理が必要です。
リスト 3. Scratching that iterative process
int
series(int x) {
int i = 0;
while (x != 1) {
++i;
if (x % 2 == 0) {
x = x / 2;
} else {
x = x * 3 + 1;
}
}
return i;
}
|
これは簡単のため意図的な例ですが、必要な反復回数を計算するコードが表現できない点で、並列化にとって興味深い例です。ベクトルとして与えられた各項目ごとに必要な反復回数も異なるかもしれないからです。
次の実装は最上級の最適化とは言えませんが、カギとなるテクニックを示しています。
リスト 4. The Collatz sequence done on a vector
vector signed int
collatz(vector signed int x) {
vector signed int unity = spu_splats(1);
vector signed int i = spu_splats(0);
vector signed int timesthreeplusone;
vector signed int divtwo;
vector unsigned int done;
vector unsigned int odd;
vector unsigned int donesum = spu_splats(0u);
done = spu_cmpeq(x, unity);
while (spu_extract(donesum, 0) != -4) {
/* add one to i for values which aren't 1 */
i = spu_sel(spu_add(i, unity), i, done);
/* odd values have 1 bits set */
odd = spu_cmpeq(spu_and(x, unity), unity);
timesthreeplusone = spu_addx(x, spu_add(x, x), unity);
divtwo = spu_convts(spu_convtf(x, 1), 0);
x = spu_sel(spu_sel(divtwo, timesthreeplusone, odd), x, done);
done = spu_cmpeq(x, unity);
donesum = spu_add(done, spu_rlqwbyte(done, 8));
donesum = spu_add(donesum, spu_rlqwbyte(donesum, 4));
}
return i;
}
|
この関数 (*) は定数1が多数格納された unity という名前の特別なベクトルを使います。これは、ベクトル i の要素をインクリメントして入力されたベクトルの各メンバーに対して実行された反復回数を数えることと、反復計算が完了したかどうかの、2 つの意味で使われています。インクリメント演算は spu_sel() を使用して、i とインクリメントされたベクトルをマージすることで行われます。でき上ったベクトルはループが完了したかの決定にも使われます。ベクトルの個々のメンバーはすべてのビットがゼロかまたは全てのビットが 1 です。ベクトルと自身を 8 バイトローテートしたものを足し合わせ、さらにその結果と結果を 4 バイトローテートしたものとを足し合わせることで、ベクトルの中の 4 つのコンポーネントが done という名前のベクトルの全 4 つのメンバの総和であるようなベクトルができあがります。4 つ全ての項目の全てのビットが 1 であれば、-4 と等しくなります (訳注： -1 を 2 の補数表現すると、全ビットが 1 になる)。
*訳注：リスト 3 は 1 個の x について反復回数を調べるがリスト 4 はベクトルに含まれる 4 個の x について同時に調べるものであることに注意。
次のステージは関数の計算です。3 つの場合があります。与えられたベクトルが既に完了している場合 (このようなケースでは、要素はそのままにする)、奇数の場合、そして偶数の場合です。結果は奇数の場合と偶数の場合両方を計算し、奇数であるかを表すベクトルによって選択します。そして、x のうちすでに完了したと識別されていない位置にマージします。
この関数はいくつかの点で最大限効率的というわけではありませんが、各要素ごとにスカラー演算を実行するよりは大幅に効率がよくなっています。多数の演算が無駄であるように見えますが、SPE ではスカラーコードであっても複数のデータ要素に演算を並列に繰り返すので、実際、何の損失もありません。
並列化バージョンによる唯一の追加コストは、未完了の要素のみを変更するための選択演算です。それ以外はすべてスカラーコードにも何らかの形で現れます。2 での除算は 4 つの語に一度に行われますし (たとえ 3 つは空白であっても)、同じことが他の計算にも言えます。float へ変換して (2^1 でスケールして) 逆変換を使っているのは、代わりに右シフト演算を使う方が合理的かもしれません。
ちょっと脇道へ
並列コードの仕事をするときに何が効率的か現実を直視することは、スカラー演算に慣れた人々には少し難しいことです。しかし、少々の並列命令を使うようにアルゴリズムを変更することは十分簡単です。扱いにくいところにはいつもスカラーコードを使えばいいのです。
スカラープロセッサでは、分岐はある表現を行うにはたいてい唯一の分別ある方法です。しかし、あるアウトオブオーダー実行システムは、演算をその結果を使うかどうか計算する分岐よりも前に行うことがあります。これは SPE の選択命令による効果と実によく似ています。
スカラープロセッサでは、望まない演算の実行はほとんどいつもパフォーマンス低下となります。SPE では、しばしば大幅なパフォーマンス向上になりえます。分岐命令の代わりに選択命令を使うコードは一般により小さくより速いのです。分岐を用いて演算をスキップすることは、計算して結果を捨てることよりも高価なのです。
もしおそらく関連する演算を並列に行うことができないようにみえても、より高水準の並列化機会がないかどうか考えることから始めましょう。私が発見した特筆すべき例の一つは、maximizing the power of the Cell Broadband Engine processor (参考文献)という以前の記事として、developerWorksに公開されています。3次元処理に共通する課題はポリゴンの細分割です。これらを並列化する一つの戦略は三角形処理のループをアンロールしてみることですが、これはコードサイズの顕著な増加と引き換えに得られる速度の改善をはいくらかのものです。しかし、複数の三角形を並列に処理するずっと単純なアルゴリズムならば、ずっと高速に、大幅に少ないコード領域で実行できます。一つの三角形に対する処理を並列化するのは難しいですが、複数の三角形を並列に実行する単純なアルゴリズムなら簡単に実行できます(そしてたぶんバグも出にくい！)。
SPU はデータ項目を非常に効率よくシャッフルするため手段を持っています。これを使えば、ベクトルをまたがるオブジェクト (オブジェクトの要素がすべて 1 つのベクトルに格納されている) から並列化された配列(複数のオブジェクトの対応する要素が一つのベクトルに格納されている) に変換する作業が簡単に行えます。シャッフルの必要性がある時でさえ、(訳注：並列化による) パフォーマンスの増加とアルゴリズムの単純さは非常に魅力的です。
最後に、言い忘れていましたが、最初の人物がアルゴリズムがもっと高速に実行できるかどうか悩んでから、あらゆる最適化の努力をしたように、あなたがデータ最適化が問題になるような現実のデータに出会うまでは、はじめは正しさに注力し、特定の部分最適化に多くの時間をかけないことです。開発者の時間は貴重であり、目も眩むほど高速であっても動かないコードは無用なのです。
次回：現実のプログラム
次回は、実際のプログラムとして、単純でかつ反復的な関数であるフラクタルジェネレーターについて深く調べてみます。それからジョブキューモデルを用いて単一のタスクを複数の SPE にベクトル化する方法について説明します。
参考文献 学ぶために
製品や技術を入手するために
議論するために
著者について | 
| | Peter Seebach has a better motto than the US Postal Service: "He always delivers!" That often means "better ways for more effective communication." |
記事の評価
| 
