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

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

ストリームプロセッシングは、並列処理を実現するためのプログラミング手法の一つです。この手法を用いることで、プログラマーはチップ上の多数の演算ユニット（コア）や、それらに接続されたバス、メモリ、I/Oなどを個別に管理することなく、効率的にアクセスできるようになります。

ストリームプロセッシングの概要

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

理論上は複数のカーネルを使用できますが、uniform streaming方式では、ストリームの各要素に適用されるカーネルは一つだけです。特にSIMD（Single Instruction, Multiple Data）においては、ストリームの連結が簡素化され、パフォーマンスが大幅に向上します。また、シンプルなプログラミングモデルにより、アセンブラを使用せずにC言語での開発が可能となり、ハードウェアの性能を最大限に引き出すことができます。

ストリームプロセッシングの重要な利点の一つは、ストリームとカーネルの抽象化によってデータの依存関係が明確になることです。これにより、コンパイラツールは、ストリームサイズの決定や割り当てなどのチップ上の管理を自動化し最適化できます。その結果、ハードウェアキャッシュやDMAのマニュアル操作による管理が不要となり、例えば一般的なDSPで処理時間の大部分を占めていたタスクが不要になります。また、オンチップメモリの効率性の高さにより、チップサイズが削減され、より多くの領域をALUに割り当てることができます。

従来の演算手法との比較

初期のCPUは、1度に1つの演算操作を行うSingle Instruction, Single Data（SISD）が基本でした。しかし、急速な計算量の増大に対応するため、1つの命令で複数の値を計算するSingle Instruction, Multiple Data（SIMD）が考案されました。SIMDは、SWAR（SIMD Within A Register）環境で利用されることが多く、より複雑な構造を採用することで、MIMD（Multiple Instruction, Multiple Data）並列性も備えるようになりました。

これらの方式は有効であるものの、実際にはメモリアライメント問題や同期問題、並列性の制約など、様々な課題がありました。2008年現在、SIMD専用のプロセッサはほとんど存在せず、汎用プロセッサの命令セットの一部として実装されることが一般的です。

具体例

100個の4次元ベクトルを順に並べ、400個の要素を持つ配列同士を加算するプログラムを例に、従来の逐次実行方式、SIMDによる並列実行方式、並列ストリームパラダイムについて比較します。

逐次実行方式

最も単純な方法は、各配列の要素を先頭から一つずつ加算していく方法です。この場合、ループ内で加算命令が400回実行されるだけでなく、forループの条件分岐ジャンプやカウンタの加算など、多数の命令が実行されます。

SIMDによる並列実行方式

次に、SIMD命令を用いて、4次元ベクトルの計算を一度に行う方法を考えます。この場合、4つの加算を一度に行うことで、逐次実行方式に比べて加算命令および条件分岐命令が1/4に減少します。しかし、格納するデータ量はSIMDレジスタのビット幅によって制限されるため、これ以上の並列性を得ることはできません。速度向上は4並列までに制限されます。

並列ストリームパラダイム

並列ストリームパラダイムでは、4個の数値を1要素とし、その100要素それぞれに対して加算演算を行うカーネルを適用して演算を行います。言語上は単純になりますが、カーネル自体は複雑になります。ループを展開すると、100個の4ALUを持つカーネルが必要になります。このSIMD/MIMDモデルはより柔軟なプログラミングを可能にしますが、カーネルやストリームのサイズはストリームプロセッサのハードウェアによって制限されます。

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

ストリームプログラミングモデルの大きな利点は、独立かつ局所的なデータの使い方を定義するカーネルから生まれます。カーネルの動作は、入出力の両方でデータの単位を定義します。これにより、ハードウェアはリソースを効率的に割り当て、グローバルのI/Oをスケジュールできます。データ単位の定義は通常カーネル内で明示的であり、入出力が明確に定義されている必要があります。

各計算ブロックを明確に独立したものとして定義することで、まとまった量の読み書き操作が可能になり、キャッシュやメモリバスの効率性が向上します。データの局所性もカーネル内で明示的に定義され、カーネルの呼び出しごとに有効期間の短い値を識別します。一時的なデータはカーネルの呼び出しに対して局所的であると仮定することで、ハードウェアやソフトウェアはそれらを高速なレジスタに割り当てることができます。これにより、並列性を向上できます。

カーネル間の依存関係が明確になることで、スケジューリングが容易になります。例えば、カーネルBがカーネルAの出力を必要とする場合、Aが完了するまでBは実行できません。これにより、ハードウェアはカーネルをアウトオブオーダーで実行し、ストールを最小限に抑えることができます。

プログラミングモデル

SIMDプログラミングモデルの欠点の一つは、構造体の配列（AoS）と配列の構造体（SoA）の問題です。プログラマーはデータ構造の定義にデータの論理的な意味を反映させたいと考えます。例えば、構造体はメモリに効率的に配置されるように、配列にアセンブルされます。しかし、AoSでは構造体の各属性がメモリ上でインターリーブされるため、SIMD演算が効率的に実行できません。

SoAでは、各属性を独立した配列に格納することでこの問題を解決しようとしますが、今度は異なる属性がメモリ上に分散してしまい、キャッシュミスが発生する可能性があります。ストリームプロセッサでは、構造体を使うことが推奨されており、アプリケーションの観点から、すべての属性を柔軟に定義できます。

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

従来の汎用プロセッサでは、外部メモリのバンド幅の向上に比べてCPUの性能が大幅に向上し続けてきたため、メモリレイテンシを隠蔽するためにダイの面積の大部分が使用されています。ストリームプロセッサでは、新しいプログラミングモデルにより、管理部分に使用されるトランジスタの量が大幅に削減されています。ストリームプロセッサは通常、高速で効率的な独自のメモリバスに接続されており、メモリアクセスパターンも予測可能です。

ストリームプロセッサの実行ユニットはSIMD的な性質を持ち、メモリは低レイテンシよりも高バンド幅に最適化されています。ストリームプロセッサの処理の大部分はチップ内で行われ、メモリに格納されるデータは全体のわずか1%程度です。これはカーネルの一時的な記憶と依存関係を明らかにすることによって得られます。

ストリームプロセッサの内部には、通信や管理のための機能とともに、Stream Register File（SRF）があります。SRFは、ストリームデータを外部メモリにバルク転送するための大規模なキャッシュであり、すべてのALUクラスタ間で共有されます。コンパイラが高度なフロー解析を行い、SRFを最適にパックし、DMAを自動化することで、カーネルとデータの依存関係が明確になり、ハードウェアはカーネルのアウトオブオーダー実行を可能にします。

ハードウェアにおける課題

ストリームプロセッシングは、大幅なスピード向上が期待できますが、すべてのアプリケーションが恩恵を受けられるわけではありません。通信のレイテンシが大きな課題となります。また、小さなデータセットでは、カーネルの切り替えが高価な操作となるため、逆効果になることがあります。この現象は「short stream effect」として知られています。

代表的なストリームプロセッサ

Imagine

スタンフォード大学のWilliam Dally教授が率いるImagineは、非常に柔軟なアーキテクチャを持ち、高速かつエネルギー効率が高いことが示されています。

Merrimac

同じくスタンフォード大学によるプロジェクトMerrimacは、ストリーム型のスーパーコンピュータの開発を目指しています。

Storm-1

Stream Processors, IncによるStorm-1ファミリは、スタンフォード大学のImagineプロジェクトからスピンオフしたもので、ハイエンドDSP市場をターゲットとしています。

Graphics Processing Unit（GPU）

パーソナルコンピュータに搭載されるGPUは、一般消費者向けのストリームプロセッサと見なすことができます。NVIDIAやAMDは、グラフィックスだけでなく、汎用的なストリームプロセッシング用途（GPGPU）にも活用可能な高性能なGPUを製造しています。

Cell

ソニー、東芝、IBMが開発したCellは、適切なソフトウェアのサポートのもと、ストリームプロセッサのように動作できるハードウェアアーキテクチャです。Cellは、Power Processing Elementと、複数のSynergistic Processor Element（SIMDコプロセッサ）から構成され、実質的なMIMDマシンです。

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

多くのストリームプロセッサ用言語は、CやC++をベースにしており、カーネルやストリームをタグするための命令が追加されています。商用および非商用のストリームプログラミング言語の例としては、Brook、Sh、StreamIt、CUDA、OpenCLなどがあります。

まとめ

ストリームプロセッシングは、データ並列処理を効率的に行うための強力な手法です。適切なハードウェアとソフトウェアを利用することで、さまざまなアプリケーションにおいて高いパフォーマンスを発揮できます。

もう一度検索