カテゴリー: Optimization

HadoopやGPGPU、FPGAなんかを使うほどじゃないけど、Many CoreのCPUを最大限に使うための考え方とか覚え書きしておく。

1.スレッドの構成

マルチスレッドで効率を高めるためには同じデータやデバイスへのアクセスが少なく、各スレッドの独立性が高いことが大事になる。もし独立性が低いと、同じデバイスやデータにアクセスすることによって、同期や排他、あるいはスヌーピング（CPUのキャッシュメモリの保持している内容と、メインメモリ上の内容が一致しなくなった時に、この同期をとるための動作）が発生して効率が上がらない。

マルチスレッドで効率良くデータを処理するためには、の設計パターンは３種類に集約される。

1.1.並列化（パラレル）

同一の処理を行うスレッドを複数作成する事で、スレッドに処理を分散する。言語レベルでサポートされている場合もあり、対応するのは容易。その代わり処理内容によってはスレッドの独立性が低くなり、効率が上がりにくい。

1.2.直列化（パイプライン）

一連の処理を何段階かのステップに分けて、ステップごとにスレッドを作成する。手前の処理を行うスレッドから、次の処理を行うスレッドへとデータを受け渡すことで処理を行う。各ステップごとの処理にかかる時間が一様ではないため、効率が上がりにくい。実際には並列化とあわせて、ステップ毎の処理量の差を吸収させるようになる。

1.3.星型（スター）

複数のデータ処理を行うスレッドと、データ処理を行うスレッドに対して処理要求を送るスレッドにて構成する。各スレッドのデータ処理量が一様で無くとも処理待ちになりにくく、スレッドの独立性も高いように設計しやすい。ただし処理速度が向上すると、処理要求を送るスレッドの処理能力がボトルネックとなるため、性能向上が頭打ちになる。

2.データの保持

HDDたデータベースなど低速なデバイスへのアクセスは大きなペナルティとなるので、可能な限りデータをメモリ上に保持する。メモリ上に保持したデータへの検索処理はハッシュテーブル等を使うとよい。最近はインメモリデータベースも多様な選択肢があるので検討する。

マルチスレッドを使った最適化のWEB記事を続けて見かけたのだが、みんなvolaileについてはスルーしているので補足してみる。volatileは変数単位でコンパイラの最適化機能を無効にする修飾詞です。C++にもC#にもJavaにも、主要な言語には大抵用意されています。volatile宣言を忘れると、Releaseビルドでしか発生しない、再現性の低い、達の悪いバグに襲われる事になります。
何故volatile宣言が必要なのかと言うと、最近のコンパイラは高度に最適化作業をおこないます。その結果として、プログラマが記述したとおりの順序で処理を実行しない事もあります。マルチスレッドで特に問題になるのが、命令の順番の入れ替えや、演算処理のループ外への移動です。
例えばループの中でA*B*2という計算をしていたとします。コンパイラは局所的に見て、ループ内で変数Bが変更される可能性が無い事を判断した場合、B*2演算をループの外に移動したりします。すると別スレッドで変数Bの値を変更しても、他スレッドのループ内の演算には反映されないという事になってしまいます。

コンパイラが最適化する前：
int a, b, d;
void funcA(void)
{
while (true)
{
a = funcB();
d = a * b * 2;
}
}

コンパイラが最適化した後：
int a, b, d;
void funcA(void)
{
int e = b * 2;
while (true)
{
a = funcB();
d = a * e;
}
}

実はVisual C++やC#ではstatic変数やグローバル変数を無条件にvolatileな変数として扱うようになっています。スレッド間で共有するような変数の多くはstatic変数やグローバル変数ですから、殆どの場合volatile宣言を忘れていても動いてしまいます。でもそのために、ケアが必要だと言う事も忘れがちなのです。

Visual Studio 2005から標準でMMX、SSE、SSE2命令を有効にした最適化をおこなえるようになりました。これらマルチメディア拡張命令を使用することで高速化を試みてみましょう。プロジェクトのプロパティを開き、C/C++のコード生成で「拡張命令セットを有効にする」のオプションを変更します。
SHA-256のサンプルプログラムを実行してみました。以下はその実行速度です。
設定なし・・14103ms
SSE・・・・・13604ms(3.5%)
SSE2・・・・12932ms(8.3%)
SSE2を有効にしただけで、8%ほどパフォーマンスが改善されています。
VC++コンパイラのSSE対応は一部の演算命令をSSE2のものに置き換えているだけで、Intel製のC++コンパイラように自動でベクトルか化を行うものではありません。ただしSSE命令を使用することによって使用できるレジスタの値が増え、その結果メモリ転送量が減って高速化する場合があるという程度のようです。
SHA-256のサンプルプログラムをベクトル化してみました。以下はその実行速度です。
SSE2(ベクトル化)・・・・17532ms
むしろ遅くなっています。
SHA256アルゴリズムはもともとベクトル化にはあまり向いていません。4ブロック128ビット分を一度に演算していますが、ベクトル化できるのは途中までで、最後に手前のブロックとの演算結果との計算は単純に4ブロック分を一度に演算するわけにはいかないからです。それを別にしてもあまりにも遅くなっている気がします。
実はSSE命令にはいくつかパフォーマンス上の欠点があります。
一つ目は16バイト分のメモリに一度にアクセスするため、キャッシュにヒットしない場合の性能低下が大きくなるのです。
二つ目はアライメントの問題。16バイト境界にアライメントされていないメモリへのアクセスは非常に遅くなるのです。
ハッシュ値の計算もととなるバイト列は都合が良いようにはアライメントされていません。これを128bit変数にセットする部分のオーバーヘッドが大きくてベクトル化の恩恵を相殺してしまっています。
SHA-256のサンプルプログラムにSSEの_mm_prefetch命令を4行ほど追加してみました。
SSE2(プリフェッチ)・・・・11918ms(15.5%)
SSEにはCPU内部のメモリキャッシュ動作を制御する命令が追加されています。大量のデータにアクセスする場合、キャッシャ制御命令を使ってメモリバスが使われていない隙間の時間に、データをキャッシュメモリに読みだすことができます。1ブロック分の処理中に、次に使用するブロックをキャッシュに読み込むことで、6%以上高速化しています。
IntelのCPUではキャッシュメモリを32バイトごとに管理しています。_mm_prefetch命令を導入する場合には32バイト毎に、メモリアドレスを指定する必要があります。
AES暗号のサンプルプログラムで「拡張命令セットを有効にする」のオプションを同じように実行してみました。以下はその実行速度です。
設定なし・・36052ms
SSE・・・・・45021ms(-24.8%)
SSE2・・・・45817ms(-27.0%)
むしろ遅くなっています。最適化の成否を高度に判断するものではないようです。よって使用する場合にはソースごとに適用するか否かをプログラマがハンダする必要があるようです。

マルチコアの性能を十分に引き出すためには、処理を複数のスレッドに分割すると共に、それぞれのスレッドが並列して動作するようにスレッドの独立性を高める必要があります。いくつか基本となるスレッド間の連携方法を紹介します。
コマンダー
ほぼどのような形の処理にも適用することができます。
ひとつの制御スレッドと、複数の作業スレッドからなります。制御スレッドからキューを通して処理の要求を作業スレッドに送ります。各作業スレッドはキューから作業内容を取得し、その結果を制御スレッドに返します。
CPUコア数と同じ数の作業スレッドを作ることでCPUを有効的に使用することができます。作業スレッドの数が増えると制御スレッドの負荷が高くなり、制御スレッドの動作速度が律速となります。
パイプライン
マルチメディアなどストリームデータの処理に適しています。
一連の処理を、前段、中段、後段のように複数の段階に分割し、それぞれの段階をスレッドにします。前段の処理が終了したら処理結果を中段に送り、前段は次のデータの処理を開始します。中段も同様に処理が終了したら処理結果を後段におくり、前段から次のデータを受け取って処理を開始します。
適当な処理単位で旨く分割することができれば、CPUコア数の増加に応じて処理速度を高めていくことができます。しかし処理を均等に分割することが難しく、もっとも負荷の大きい段階が律速となります。

マルチコアCPU向けに最適化する場合、CPUキャッシュが複数ある事を踏まえて、データ構造を工夫する必要があります。
･CPUキャッシュメモリの動作
CPUにはキャッシュメモリがあり、プログラムの使用するデータがキャッシュされています。複数のCPUコアがある場合、CPUコアごとにキャッシュメモリを持っています。もしCPU Aがメモリにデータを書き込んだ時に、同じメモリをCPU Bがキャッシュしていた場合、そのままではCPU AとCPU Bがそれぞれ持つキャッシュメモリの一貫性（キャッシュコヒーレンシ）が失われてしまいます。そこで多くのCPUではキャッシュメモリと実データの一貫性が失われた事を他のCPUに通知し、キャッシュデータを破棄して再取得するための仕組みが用意されています。しかしその為には低速なCPU外部バスにアクセスしなければならず、プログラムの実行速度を大きくそこないます。マルチコアCPUの性能を引き出すためには、メモリの一貫性を破壊しないようにデータ構造を最適化しておく必要があるのです。
原則はスレッド毎の独立性を高めることです。各スレッド間で交換しなければならないデータ量を減らします。その上で各スレッドから変更する可能性のある変数が、同一メモリブロックに配置されないように、なおかつ、最小で済むようにデータ構造を工夫します。多くのCPUではキャッシュメモリを64バイト～128バイト程度のメモリブロック（キャッシュライン）に分けて管理していますから、このサイズも意識する必要があります。
注意が必要なデータ構造
･変数の共有
同一の変数を複数のスレッドから参照するのは、もっとも容易で安易な方法です。ですが変数を参照する箇所が少なかったり、あるいは更新頻度が少ない場合には必要十分な方法です。
ただし、その変数の前後で宣言されている変数が同一のキャッシュメモリブロックに配置される可能性が高い事を考慮する必要があります。もし変数に頻繁に書き込みをおこなえば、その前後で宣言された参照しかしていない変数も同時に影響を受けることになります。
影響を防ぐにはスレッドの初期処理でスタック変数に値をコピーし、スレッド内部ではコピーした値を使用します。スタックは各スレッドごとに用意され、他のスレッドと同じキャッシュメモリに配置される可能性はありません。これにより書き換えられる変数と同一のキャッシュメモリブロックに配置される可能性がなくなり、キャッシュのミスマッチに伴う動作速度の低下をなくせます。
･配列の使用
各スレッドが配列の異なる要素を参照している場合です。異なるデータに対して同じ計算を繰返しおこなう場合、データの管理や状況の管理が容易なので良く行われる方法です。
ただし配列の要素サイズが小さい場合、前後の要素が同じキャッシュメモリブロックに属する可能性があります。もし要素１の内容を書き換えた場合、他のスレッドで参照していた要素２でのキャッシュミスマッチが発生してしまいます。
メモリに余裕がある場合には配列の要素サイズがキャッシュメモリブロックの整数倍になるようにパディングをおこないます。キャッシュメモリブロックのサイズはCPUの種類ごとに異なるため、128バイトか256バイト程度の切の良いサイズにすることになります。
メモリに余裕が無い場合にはリンクリストなどを使い、要素ごとにヒープメモリ領域に格納します。コンパイラのメモリマネジメントにより同一メモリブロックに配置されてしまう可能性もありますが、回避できない要因として無視します。

typedef struct{
DWORD val1;
DWORD val2;
BYTE padding[xxx]; // 要素サイズが128バイトになるようにパディング
}PARAM;

int target = 16;
int param1;
int param2;
PARAM data[16];

void ThreadA(void)
{
int localParam1 = param1; // 変数をスタックに複製
int localParam2 = param2; //
int localTarget;
while (target > 0)
{
localTarget = target – 1;
target –;
data[localTarget].xxxx = ….;
}
}