ストリーム・プロセッシング

概要

ストリーミングプロセッシングの計算モデルとは、ストリームと呼ばれる入力データセットの各要素に対し、カーネルと呼ばれる演算操作を作用するものである。カーネルはストリームに対してパイプライン化された形で動作し、入力および演算後の出力ストリームは外部のメインメモリでなくプロセッサ内のローカルストアに格納することで、カーネルをストリームに複数回作用させる場合のメモリアクセス時間の短縮を図っている。
理論上は複数のカーネルを持つことが可能であるようだが、uniform streaming方式では、ストリームの各要素それぞれに適用されるカーネルは1つしか使用しない。uniform streamingの中でも特にSIMDでは、ストリームの連結は簡素化され、パフォーマンスの大きな向上が達成される。また、シンプルなプログラミングモデルはC言語による開発を可能にしつつ (アセンブラは必要ない)、ハードウェア上の最適なパフォーマンスを達成することができる。ストリームプロセッシングによるもう一つ重要な利点は、ストリームとカーネルの抽象化がデータの依存性を明示的にするため（ハードウェアでもDMAを起動するためのランタイムの評価機構などを備えることができるが）、コンパイラツールがチップ上で行う管理、たとえばストリームサイズの決定や割り当てを、完全に自動化し最適化することができる点である（依存関係が既知のため）。すなわち、ハードウェアキャッシュや DMA のマニュアル動作による管理の必要がなく、たとえば 一般的なDSPを用いた場合に処理時間の大部分を消費してしまうようなタスクは必要ない。オンチップメモリ ("ソフトウェア管理のキャッシュ") の効率の高さによりダイサイズが削減され、ALUに対してより多くの領域を確保できる。

従来の演算手法との比較　

初期のCPUは、1回に演算操作を1つ行うSingle Instruction, Single Dataが基本であった。その後、急速な計算量の増大に対しそのような逐次計算モデルでは要求を満たすことができないため、一つの命令で複数の値を計算するSingle Instruction, Multiple Dataが考案された。ほとんどの期間において、SIMDはSWAR環境 (SIMD Within A Register) で利用された。また、より複雑な構造を採用することにより、MIMD並列性をも備えるようになった。
これらの2つの方式は有効ではあるものの、実際に適用するとメモリアライメント問題から同期問題、並列性の制約に渡る様々な制約に悩まされた。2008年現在、SIMD専門のプロセッサはほとんどなく、汎用プロセッサにおける命令セットの一部として実装される場合が多い。
具体例として、100個の4次元ベクトルを順に並べ、400個の要素を持つ配列同士を加算するプログラムを考える。

逐次実行方式

一番単純な方法として、各配列の要素を先頭から順に一つずつ加算することを考える。
for (int i = 0; i < 100 * 4; i++)
    result[i] = source0[i] + source1[i];
この方法では、ループ内で加算命令が400回実行される他にも、forループのための条件分岐ジャンプやカウンタiの加算など多数の命令が実行される。

SIMDによる並列実行方式, レジスタパッキング(SWAR)

次に、システムに用意されたSIMD命令vector_sumを用いて、4次元ベクトルの計算を一度に行う方法を考える。以下に、ベクトルの次元数やデータ型を省略した簡潔なコードを示す。
for (int el = 0; el < 100; el++) // for each vector
    vector_sum(result[el], source0[el], source1[el]);
4つの加算を一度に行うvector_sumを用いることで、逐次実行方式に比べ加算命令および条件分岐命令が4分の1に減少している。
しかし、格納するデータ量にはSIMDレジスタのビット幅によって制限されるため、これ以上の並列性を得ることはできない。この場合、速度向上は4並列までに制限される。AltiVecおよびSSEでも同様の問題を抱えている。

並列ストリーム・パラダイム (SIMD/MIMD)

次に、並列ストリームパラダイムに基づく擬似コードを示す。
streamElements 100
streamElementFormat 4 numbers
elementKernel "@arg0+@arg1"
result = kernel(source0, source1)
4個の数値を1要素とし、その100要素それぞれに対して加算演算を行うカーネルを適用して演算を行うコードである。
言語上は単純になるが、カーネルは複雑となる。ループを展開すると100個の4ALUを持つカーネルが必要となる。
このSIMD/MIMDモデルはより柔軟なプログラミングを可能にするが、カーネルやStreamのサイズはストリームプロセッサのハードウェアによって制限される。例えば、一般的なGPUは、倍精度浮動小数点演算や複雑な間接命令をハードウェアでサポートしていない。

データの依存関係と並列性

ストリームプログラミングモデルの大きな長所は、独立かつ局所的なデータの使い方を定義するカーネルから生まれる。
カーネルの動作は、基本的なデータの単位を、入出力両方で定義する。これにより、ハードウェアがうまくリソースを割り当て、グローバルの I/O をスケジュールできる。
通常プログラミングモデルからは見えないが、ストリームプロセッサ（少なくともGPUでは）I/O の動作は相当に進歩した物であるようだ。I/O 操作自体も通常パイプライン化されており、チップの機構によりレイテンシの隠蔽を補助する。
データ単位の定義は通常カーネルにおいて明示的であり、すなわち十分定義された入力 (たとえば構造体の使用が推奨されている) と出力を期待されている。いくつかの環境では、出力の値は固定である (たとえばGPUでは、特に条件を緩和しなければ固定された出力情報が存在する)。
それぞれの計算ブロックを明確に独立で定義づけられたものにすることで、まとまった量の読み込みや書き込みの操作が、キャッシュやメモリバスの効率性を著しく向上させる。
データの局所性もカーネルにおいて明示的である。この概念は、通常カーネル局所性と呼ばれ、単一のカーネルの呼び出しのため寿命が短い値をすべて識別する。すべての一時的なデータは単純にそれぞれのカーネルの呼び出しに対して局所的であると仮定することで、ハードウェアやソフトウェアはこれらを高速なレジスタに割り当てることができる。このことは、利用できる並列性の度合いと厳密に関わっている。
各カーネルの内部では、個々の生産-消費の関係をくくりだすことができる（カーネルが次々と連結されていく場合には、この関係はモデルによって与えられる）。
これにより、カーネルBがカーネルAの出力を必要とするとき、AはBが実行できるようになる前に完了していなければならないことは明らかである（少なくとも使用されているデータ単位については）ため、スケジューリング上の決定を簡単に行うことができる。
Imagine チップのオンボードストリームコントローラーモジュールは、カーネルの依存関係（コンパイラより与えられる）のスコアボードを保った状態でカーネルのロードをランタイムにハードウェアで行い、ストールを最小化するアウトオブオーダー実行ができるようにする。これは、高性能の演算処理に置ける新たなパラダイムである。Cellがこれをたとえば複数の SPE 間でデータを回送しながら行うということを示す情報もある。これと比較して、Imagine は純粋なSIMDマシンであり、クラスタ間の通信やカーネルの実行は常に明示的で、Cell のような MIMD マシンと比べてシリコンの面積も小さい。
昨今、CPU ベンダーがマルチコアやマルチスレッディングを推進している。このトレンドは平均的なユーザーにとっては役立つ物になるが、標準的な CPU が並列計算においてストリームプロセッサの性能に近づく余地はないだろう。
二つのカーネルインスタンスの並列性はスレッドレベル並列性と類似している。
各カーネルの内部で、さらに命令レベル並列性を用いることも可能である。
タスクレベルの並列性 (オーバーラップしたI/Oなど) は起こりうる。カーネルインスタンスを何千個も持つことはたやすいが、同数のスレッドを持つことは単純に不可能である。これがストリームの力である。

プログラミングモデルに関して

SIMD プログラミングモデルの欠点の一つは、構造体の配列 (AoS) と配列の構造体 (SoA) の問題である。プログラマーはデータ構造の定義にデータの論理的な意味を反映したがる。例えば：
// 三次元空間上の微粒子struct particle_t {
    float x, y, z; // 配列にもなっていない！
    byte color[3]; // チャンネルあたり8bitで、RGBのみ考えている
    float size;
    // ...以下、それ以外の属性が続く...};
このような構造体はメモリにうまく配置されるように、配列にアセンブルされることになる。
これがAoSである。この構造体がメモリに配置される際、コンパイラはインターリーブされたデータを生成する。つまりすべての構造体が連続しているが、一つの構造体の例えば "size" 属性と、次の構造体の同じ属性には固定値のオフセットが存在する。
オフセットは構造体の定義に依存する（ここでは考慮していないコンパイラの配置ポリシーなどもある）。
他の問題もある。例えば、三つの位置変数は同じように SIMD 化することができない。なぜなら連続したメモリ空間に配置されるかどうかが不明なためである。SIMD 演算が動作するようにするには、パックされた配置とするか、最低でも配列内になければならない。
更なる問題は、"color"と"xyz"が3要素のベクトル量として定義されている点である。SIMD プロセッサは通例4要素の演算のみサポートする（いくつかの例外はあるが）。
この種の問題や制約は、通常の CPU での SIMD による高速化を非常に汚いものにしてしまう。
SoAでの解決策は以下のようになるだろう：
struct particle_t {
    float *x, *y, *z;
    byte *colorRed, *colorBlue, *colorGreen;
    float *size;};
ここで"*"はC言語でいうところのポインターである。要するに、別途割り当てることになる配列の先頭へのアドレスがここに入る。読者がJavaプログラマーなら"*"を"[]"で読み替えてくれればだいたい同じ意味になる。
ここでの問題点は、様々な属性がメモリ上に分散してしまうことである。キャッシュミスを発生させないようにするため、すべての "red" を書き換え、次にすべての "green" とすべての "blue" を書き換えなければならない。結果的にそれほど悪くないようにも見えるが、ストリームプロセッサが提供するものと比べると制約が強すぎる。
ストリームプロセッサに対しては、構造体を使うことが推奨されている。アプリケーションの観点から見ると、すべての属性が多少柔軟性を持って定義できる。
GPU を例とすると、多数の属性（最低でも16の）が利用できる。各々の属性について、アプリケーションはコンポーネントの数とフォーマット（現状は基本型のみがサポートされている）を宣言できる。次に、ある要素が点在しているのか連続しているのかを定義しながら、様々な属性がメモリブロックに割り当てられ、事実上インターリーブされたデータ形式を許容している。
GPU がストリームの処理を開始する際、すべての属性を単一のパラメータセット（大抵は、構造体や"魔法のグローバル変数"のような形式である）に集め、演算を実行し、次の処理（あるいは演算結果の回収）のためにメモリのどこかの領域に結果をばらまく。
まとめると、アプリケーション側にはより大きな柔軟性があるが、ストリームプロセッサ側では非常に秩序だった形式である。

Hardware-in-the-loop 問題

1桁大きなスピードの向上が期待できる (ストリーミングの方法で計算を行えば、メインストリームのGPUでさえ) が、すべてのアプリケーションが恩恵を受けられるわけではない。通信のレイテンシが通常最大の問題である。PCI Expressが双方向通信を改善させたが、GPU (あるいは、一般的なストリームプロセッサ) を動作させるには、まだ長い時間が必要と思われる。
これは、小さなデータセットに対して使うのは逆効果であることを意味する。ストリームアーキテクチャは小さなストリームに対してペナルティがあり、この振る舞いはshort stream effectとして公式に認知されている。これは、基本的にはカーネルを切り替えることが高価な操作であるために起こる。
パイプライン化は、ストリームプロセッサでは定着した方法であり、GPU では 200 ステージを超えるパイプラインを備える。ある設定を切り替えるためのコストは、変更される設定に依存するが、基本的に高価だとみなされている。切り替えのコストを下げるために努力が行われているが、そうすぐに現実にならないとも予測されている。こうした問題をパイプラインの様々なレベルで避けるため、"uber shaders"や"texture atlases"のような多数のテクニックが導入されている。これらのテクニックは GPU の性質からゲームに向いたものだが、その考え方は、汎用のストリームプロセッシングでも興味深い。

Imagine

スタンフォード大学のWilliam Dally教授が率いるImagine は、非常に柔軟なアーキテクチャで高速かつエネルギー効率が高いことが示されている。1996年に発想されたプロジェクトには、アーキテクチャ、ソフトウェアツール、VLSI の実装および開発ボードが含まれ、DARPA、インテル、テキサス・インスツルメンツに資金を提供されていた。2002年に登場したファーストシリコンは 3.5GFPS の性能をコアの消費電力わずか 1.6 ワットで達成した。

Merrimac

別の スタンフォード大学 によるプロジェクト Merrimac は、ストリーム型のスーパーコンピュータの開発を目的としている。Merrimac はストリームアーキテクチャと高度な通信ネットワークを用いて、同じような技術で構築されたクラスタ型の科学計算用コンピュータに対して一桁大きい性能/コストを実現する。

Imagine

Stream Processors, Incによる Storm-1 ファミリは、Standford の Imagine プロジェクトからスピンオフしたもので、ISSCC 2007の基調講演で発表された。このファミリには 30～220 16bit GOPS (毎秒10億回の演算)の範囲に4つのメンバーがあり、すべてTSMCの130ナノメータープロセスで生産される。これらはビデオ会議、プリンタ複合機や映像監視装置などを含むハイエンドDSPの市場をターゲットとしている。

Cell

ソニー・コンピュータエンタテインメント、東芝、IBMが開発したCellは、適切なソフトウェアのサポートのもとストリームプロセッサのように動作できるハードウェアアーキテクチャである。Cellは、Power Processing Elementと、Synergistic Processor Elementと呼ばれる複数の SIMD コプロセッサからなり、それぞれが独立したプログラムカウンタとローカルストア領域を持つ、実質的な MIMDマシンである。ネイティブのプログラミングモデルでは、すべてのDMAおよびプログラムのスケジューリングはプログラマが行う。ハードウェアはローカル通信のため高速なプロセッサ間のリングバスを提供する。命令とデータを配置するローカルメモリは256KiBと小さいため、このアーキテクチャを有効に活かすことができるプログラムは、メモリ消費が小さいか、ストリームプログラミングモデルに忠実なもののみである。適切なアルゴリズムの元では、Cellの性能は純粋なストリームプロセッサに比肩するが、これにはアルゴリズムとソフトウェアの完全な再設計が必ずと言っていいほど必要となる。(PS3はメインCPUにストリームプロセッサが据えられている点でPCのアーキテクチャとは大きく異なると言える。)