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

ストリーム・プロセッシング (英: stream processing) は、並列処理を実現するプログラミング手法の一つである。ストリームプロセッシングを用いることにより、コンピュータープログラマーはチップ上の多数の'コア'（あるいは、演算の単位）や、それぞれに接続されたバスやメモリ、I/Oなどを別々に管理せずにアクセスできる能力の恩恵を受けることができる。

概要

ストリーミングプロセッシングの計算モデルとは、ストリームと呼ばれる入力データセットの各要素に対し、カーネルと呼ばれる演算操作を作用するものである。カーネルはストリームに対してパイプライン化された形で動作し、入力および演算後の出力ストリームは外部のメインメモリでなくプロセッサ内のローカルストアに格納することで、カーネルをストリームに複数回作用させる場合のメモリアクセス時間の短縮を図っている。

理論上は複数のカーネルを持つことが可能であるようだが、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は、倍精度浮動小数点演算や複雑な間接命令をハードウェアでサポートしていない。

Systolic array パラダイム

別の並列データの演算に対するストリームプロセッシングのパラダイムとして、(通常はハードワイヤーの) Systolic arrayというものがあり、広く認知された Data stream と Super systolic array (再構成可能: 例えばrDPA: Reconfigurable datapath array) という用語の定義を含む。 この文章はSystolic arrayから派生したこれらのパラダイムについて十分考慮したものではない。

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

この記述の時点で (2005年9月12日)、ストリーム・プロセッシングに関する入手可能な文書は非常にとぼしく、ごく少数の機関しかこのモデルの潜在的なパワーを理解していない。スタンフォード大学は歴史的に、これに関する様々なプロジェクトに関係している。Stanford Shading languageに始まり、さらに進んでは、柔軟なスタンドアロンのストリームプロセッサImagineが行われた。それらのプロジェクトの結果、このパラダイムの潜在的な可能性の大きさが明らかになり、より大規模なプロジェクトMerrimacが開始された。Merrimacは、ストリームベースのスーパーコンピュータであり、現在研究が続行されている。 AT&Tで認識されているのは、ストリーム処理を拡張したプロセッサの広範な採用により、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 がストリームの処理を開始する際、すべての属性を単一のパラメータセット（大抵は、構造体や"魔法のグローバル変数"のような形式である）に集め、演算を実行し、次の処理（あるいは演算結果の回収）のためにメモリのどこかの領域に結果をばらまく。

まとめると、アプリケーション側にはより大きな柔軟性があるが、ストリームプロセッサ側では非常に秩序だった形式である。

汎用的なプロセッサのアーキテクチャ

歴史的には、外部メモリのバンド幅がわずかしか向上しないのに対して、CPU は性能が増大しつづけるため、複数の階層に渡ったメモリアクセスの最適化を実装してきた。このギャップが広がるにつれて、ダイの面積の非常に大きな部分がメモリのレイテンシを隠蔽するためだけに使用されている。わずかな ALU に対してデータと命令をフェッチすることが高価であるため、非常にわずかなダイの面積しか実際の数値演算処理を行う機構に使用されていない (大まかな見積もりで、たとえば 10% 以下程度と思えばよい)。

ストリームプロセッサでも同様の機構は存在するが、新しいプログラミングモデルのおかげで、(計算を行わない) 管理部分にのみ使用されるトランジスタの量は実際には非常に少ない。

システム全体の観点からストリームプロセッサは通常制御された環境の中に存在する。GPU は拡張ボードとして存在している (これは Imagine にも当てはまるようだ)。CPU はシステムリソースの管理や、アプリケーションなどを動作させる雑多な作業を行っている。

ストリームプロセッサは、通常、高速で効率のよい独自方式のメモリバスに接続されている（クロスバースイッチが現在では一般的で、かつてはマルチバスが採用されていた）。メモリレーンの正確な量はマーケットの範囲によって異なる。執筆の時点では、まだ (エントリーレベルでは) 64bit幅でインターコネクトがある。ほとんどのミッドレンジのモデルは 128bitのクロスバースイッチのマトリクス (4か2セグメント) を持っており、ハイエンドのモデルは膨大なサイズのメモリ (512MB程度まで) を、若干低速なクロスバースイッチを介して256bit幅で接続している。一方、PentiumやAthlon64などの標準的なプロセッサは、64bit幅のデータバスをひとつ持っているだけである (訳注:2005年時点?)。

メモリアクセスのパターンもかなりの部分予測可能である。配列は存在するが、カーネルの呼び出しにおいて、メモリの配置は固定的である。複数レベルのポインタによる間接参照にほぼ対応するのはindirection chainであるが、これは最終的に（ストリーム内の）特定のメモリ領域を読み書きすることが保証されているものである。

ストリームプロセッサの実行ユニット (ALUクラスタ) はその SIMD 的な性質から、読み書きの操作はまとめて行われることになっており、メモリは低レイテンシよりも高バンド幅に最適化される (これはたとえば、RambusとDDR SDRAMの違いである)。これはメモリバスの調停を効率的にする。

ストリームプロセッサのほとんど (90%) の作業はチップ内で行われ、全体のデータの1%のみがメモリに格納される。これが、カーネルの一時的な記憶と、依存関係を明らかにすることにより得られるものである。

内部的には、ストリームプロセッサは通信や管理用の機能を備えるが、興味深いのは Stream Register File (SRF) である。これは概念的にはストリームデータを外部のメモリにバルク転送するために格納する大規模なキャッシュである。各種の ALU 向けのキャッシュのようなソフトウェア制御の機構と同じく、SRF はすべての ALU クラスタ間で共有される。Stanford の Imagine チップにおいて基本となる考え方と、ここで行われた革新的な技法は、コンパイラに高度なフロー解析を施し、SRF を最適にパックし、DMA を自動化して、カーネルとデータの依存関係が、プログラミングモデル全体を通じて明らかであることである。ハードウェアは、カーネルのアウトオブオーダー実行を可能にするためのランタイムの同期処理を行うことができる。一般に、キャッシュと DMA の管理は処理時間のほとんどを使ってしまうようなものであるが、ストリームプロセッサ (少なくともImagine) は、これを完全に自動化する。Stanford で行われたテストでは、メモリのスケジューリングにおいて、手間をかけて手動でチューンした場合より、コンパイラが同等かそれ以上の結果を出せることを示した。

クラスタ間の通信が稀であることが前提である場合のみ、クラスタは多数存在することができることが立証されている。しかし、内部的にクラスタ間の通信が多数ある場合には、効率が高いことが求められ、各クラスタが少数の ALU しか効率的に使えない。

ALU がデータをフェッチした状態に保つには、各 ALU はローカルレジスタファイル (LRF) を持つ必要があり、基本的にはこれらが使用可能なレジスタである。

この3階層形式のデータアクセス形態は、低速なデータメモリから一時的なデータを駆逐し、シリコン上の実装を効率的にし、消費電力を低減させる。

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の市場をターゲットとしている。

Graphics Processing Unit

パーソナルコンピュータに搭載されるGraphics Processing Unit (GPU) は、一般消費者向けのストリームプロセッサと見ることができる。NVIDIAおよびAMD (旧ATI) が、グラフィックスだけでなく汎用的なストリームプロセッシング用途 (GPGPU) にも活用可能な高性能なGPUを製造している。かつてはS3 Graphicsもコンシューマー向けGPUを手掛けていたが撤退している。

NVIDIA GeForce/NVIDIA Quadro/NVIDIA Tesla

G80以降でストリームプロセッシング開発環境CUDAが利用可能になった。

AMD Radeon/AMD FirePro/FireStream

R6xxで倍精度浮動小数点演算に対応し、R7xx (RV770PRO) で1チップでは世界初の1TFLOPSを達成。

S3 Chrome

Chrome 400 / 500シリーズにてOpenCL 1.0に対応したことによりGPGPUへの活用の幅が広がった。

Cell

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

ストリームプログラミング言語

大半のストリームプロセッサ用言語はCやC++から出発し、アプリケーション開発者にカーネルやストリームをタグする特定の命令を追加している。これにはシェーディング言語も当てはまり、一定の範囲内のストリームプログラミング言語の一種だと考えることができる。また多くの並行論理プログラミング言語はストリームを使って並行計算を行う。

商用のものでないストリームプログラミング言語の例としては以下のものがある。

• スタンフォード大学の Brook 言語
• ウォータールー大学 の Sh ライブラリ
• MIT の StreamIt
• オープンソースの Shallows プロジェクト
• Concurrent Prolog
• GHCとKL1
• PARLOG
• Strand

商用の実装は、汎用であるか、あるいはベンダーのハードウェア専用である。汎用の言語の例としては以下のものがある。

• PeakStream。Brookプロジェクトのスピンアウトである (2007年6月にGoogleに買収された)
• Sh を商用化した RapidMind

ベンダー固有の言語には以下のようなものがある。

• NVIDIAのCUDA (Compute Unified Device Architecture)
• AMD/ATIのATI Stream、Close to Metal (CTM) およびBrook+
• Stream Processors, IncのStreamC。スタンフォードのImagineの商用化である

ハードウェアを抽象化した標準規格には以下のようなものがある。

• クロノス・グループのOpenCL (OpenCL C/C++)
• マイクロソフトのDirectCompute (HLSLコンピュートシェーダー)
• クロノス・グループのOpenGL (GLSLコンピュートシェーダー)
• C++ AMP
• OpenACC

関連項目

• ベクトルプロセッサ
• SIMD
• MIMD
• GPGPU
• OpenCL
• 並列コンピューティング

参考文献

1. ^ Khailany, Dally, Rixner, Kapasi, Owens and Towles: "Exploring VLSI Scalability of Stream Processors", Stanford and Rice University.
2. ^ Gummaraju and Rosenblum, "Stream processing in General-Purpose Processors", Stanford University.
3. ^ Venkatasubramanian, "The Graphics Card as a Stream Computer", AT&T Labs - research.
4. ^ Kapasi, Dally, Rixner, Khailany, Owens, Ahn and Mattson, "Programmable Stream Processors", Universities of Stanford, Rice, California (Davis) and Reservoir Labs.

外部リンク

• Electronics Weekly の記事 がストリームプロセッサ技術を開発している Stream Processors, Inc. (SPI) を特集している。
• EE Times の記事 がストリームプロセッサ技術を開発している Stream Processors, Inc. (SPI) を特集している。
• EDN の 記事 がストリームプロセッサ技術を開発している Stream Processors, Inc. (SPI) を特集している。
• San Jose Mercury News の記事 がストリームプロセッサ技術を開発している Stream Processors, Inc. (SPI) を特集している。
• プレスリリース で、AMD の R580 GPU に基づいたエンタープライズ用途の専用ストリームプロセッシングユニットの出荷情報を公開している。