Windows と C++
高性能アルゴリズムについて調べる
Kenny Kerr
同時実行領域では、調整、非同期動作、応答性、スケーラビリティなどの問題が最大の注意点になっています。これらは、アプリケーションのデザイン時に開発者が検討する上位レベルのトピックです。ただし、おそらくは経験不足や優れたパフォーマンス ツールがないために、同じように重要なトピックがしばしば見過ごされます。その適例が高性能アルゴリズムです。
エンタープライズ レベルでは、開発者は分散ファイル システムとキャッシュ、クラスタ、メッセージ キュー、データベースなどの問題について熟考します。しかし、根本的にアルゴリズムとデータ構造が不十分な場合は、それらが何の役に立つでしょうか。
アルゴリズムの効率は、皆さんが考えるほど簡単ではありません。シングル プロセッサ上の適切にデザインされたアルゴリズムは、複数プロセッサ上の不十分な実装よりもパフォーマンスが高い場合がよくあります。しかし、今日の適切にデザインされたアルゴリズムは、複数プロセッサが使用可能な場合にもかなりのスケーラビリティと効率を示す必要があります。問題をさらに複雑にするのは、シングル プロセッサ用に最適化されたアルゴリズムは並列化が難しいことが多く、若干効率の劣るアルゴリズムの方が複数プロセッサ上で高いパフォーマンスを示す可能性があることです。
たとえば、ここでは Visual C++ を使用し、かなり単純なアルゴリズムの開発を紹介しますが、これは一見するほど簡単ではありません。実装する必要のある内容を次に示します。
void MakeGrayscale(BYTE* bitmap,
const int width,
const int height,
const int stride);
bitmap パラメータは、ピクセルあたり 32 ビットで構成されるイメージを指します。これについてもこの記事で注目します。stride の絶対値は、メモリ内の 1 行のピクセルから次の行までのバイト数を示します。各行の終わりには埋め込み文字が存在する場合があります。stride の符号は、これらの行がメモリ内で正のストライドを持つトップダウンであるか、負のストライドを持つボトムアップであるかを示します。
まず、基本事項を見てみましょう。次の構造体を使用して、メモリ内のピクセルを表すことができます。
typedef unsigned char BYTE; // from windef.h
struct Pixel
{
BYTE Blue;
BYTE Green;
BYTE Red;
BYTE Alpha;
};
簡単な Web 検索で、特定の色ピクセルに 30% の赤、59% の緑、および 11% の青を混合すると合理的なグレー スケール値を取得できることがわかります。次に、1 つのピクセルのみをグレー スケールに変換する単純な関数を示します。
void MakeGrayscale(Pixel& pixel)
{
const BYTE scale = static_cast<BYTE>(0.30 * pixel.Red +
0.59 * pixel.Green +
0.11 * pixel.Blue);
pixel.Red = scale;
pixel.Green = scale;
pixel.Blue = scale;
}
ビットマップ内の特定のピクセルのバイト オフセットは、水平位置とピクセル サイズの積、および垂直位置とストライドの積を計算し、それらの値を加算することで取得できます。
offset = x * sizeof(Pixel) + y * stride
次に、MakeGrayscale 関数を実装するにはどうすればよいでしょうか。深く考えずに進んだ場合は、図 1 に示すようなアルゴリズム行を作成する可能性があります。一見したところ、このコードは合理的なように思え、小さなビットマップが渡された場合はかなりうまく機能するように見える可能性があります。では、より大きなビットマップについてはどうでしょう。20,000 × 20,000 ピクセルのビットマップについてはどうでしょうか。
図 1 非効率的なシングルスレッド アルゴリズム
void MakeGrayscale(BYTE* bitmap,
const int width,
const int height,
const int stride)
{
for (int x = 0; x < width; ++x)
for (int y = 0; y < height; ++y)
{
const int offset = x * sizeof(Pixel) + y * stride;
Pixel& pixel = *reinterpret_cast<Pixel*>(bitmap + offset);
MakeGrayscale(pixel);
}
}
筆者は Quad-Core Intel Xeon X3210 プロセッサを搭載した Dell PowerEdge を持っています。このマシンのクロック速度は 2.13 GHz であり、1066 MHz のフロントサイド バス、8 MB の L2 キャッシュ、およびその他さまざまなすばらしい機能を搭載しています。確かに、これは最新の Intel Xeon プロセッサではありませんが、侮れるものではありません。64 ビット バージョンの Windows Server 2008 で駆動され、パフォーマンス テストでは優れた結果を出しています。
その全能力を利用して、図 1 のアルゴリズムを幅 20,000 ピクセル、高さ 20,000 ピクセルのビットマップに対して実行しました。10 回の反復で平均約 46 秒かかりました。確かに、このビットマップはかなり大きく、1.5 GB ほどになります。しかし、それが問題でしょうか。筆者のサーバーには 4 GB の RAM があるため、ディスクにページングされることはありません。しかし、図 2 では、プロセッサ使用状況の見慣れたビューが示されています。
.gif)
図 2 非効率的なシングルスレッド アルゴリズムのプロセッサ使用状況 (クリックすると拡大画像が表示されます)
アルゴリズムは猛烈に動作しますが、コンピュータの処理能力の 4 分の 1 しか使用していません。この解決方法は明らかです。最も一般的な対応は、問題を解決するためにより多くのスレッドを投入することです。これは合理的な見解です。結局のところ、アルゴリズムは 1 つのスレッドしか使用しないため、テスト システムの 4 つのコアのうち 1 つしか使用されていません。図 3 のコードではスレッドを追加します。
図 3 非効率的なマルチスレッド アルゴリズム
void MakeGrayscale(BYTE* bitmap,
const int width,
const int height,
const int stride) {
#pragma omp parallel for
for (int x = 0; x < width; ++x)
for (int y = 0; y < height; ++y) {
const int offset = x * sizeof(Pixel) + y * stride;
Pixel& pixel = *reinterpret_cast<Pixel*>(bitmap + offset);
MakeGrayscale(pixel);
}
}
違いは、OpenMP プラグマの追加だけです。外側の for ループはスレッドに分割されるため、並列で実行でき、ビットマップの異なる部分を変換します。OpenMP では、既定でプロセッサあたり 1 つのスレッドが作成されます (OpenMP の使用にこだわる必要はありません。これは for ループを各スレッドに分割する非常に簡単な方法であるというだけです。コンパイラとランタイムに応じて、同じ結果を実現するための手法が他にもあります)。図 4 に示されるように、このわずかな変更によって大きな違いが現れます。
.gif)
図 4 非効率的なマルチスレッド アルゴリズムのプロセッサ使用状況 (クリックすると拡大画像が表示されます)
しかし結果は理想的とは言えません。シングルスレッド バージョンの 46 秒に比べて、マルチスレッド アルゴリズムでは約 30 秒かかっています。34% のパフォーマンス向上は、処理コストの 300% の増加に値するとはとうてい思えません。ここで、効率的な実装では、(同じテスト システムで) シングルスレッドのみ使用すると約 2 秒で完了し、複数スレッドを利用すれば約 0.5 秒で完了すると言ったらどうでしょう。これは 30 秒よりもはるかに高速です。
思っているよりも簡単です。アルゴリズムを実行している物理ハードウェアと、メモリ内でのデータの編成方法について考えるだけです。開発者は、コードを最終的に実行するハードウェアに対して無関心になりがちです。効率的なアルゴリズムについて説明し、それがはるかに優れている理由を説明します。
図 5 を見てください。違いは、for ループの順序だけであることに驚かれるかもしれません。つまり、外側のループが Y 軸に対して反復し、内側のループが X 軸に対して反復するように図 3 のアルゴリズムを変更しました。このように一見些細な変更で、時間が 30 秒から 1 秒未満に短縮されるのはなぜでしょうか。その答えは、アルゴリズムが操作対象のデータの形状と局所性、およびハードウェアの特性によって深刻な影響を受ける可能性があるという事実に基づきます。
図 5 効率的なアルゴリズム
void MakeGrayscale(BYTE* bitmap,
const int width,
const int height,
const int stride) {
#pragma omp parallel for
for (int y = 0; y < height; ++y)
for (int x = 0; x < width; ++x) {
const int offset = x * sizeof(Pixel) + y * stride;
Pixel& pixel = *reinterpret_cast<Pixel*>(bitmap + offset);
MakeGrayscale(pixel);
}
}
これを理解するために、アルゴリズムの操作対象のデータ構造を再検証する必要があります。ビットマップのメモリ バッファは、論理的にピクセルの行を含みます。明らかに、メモリは表形式ではなく、特定の座標のピクセルを簡単かつ効率的にアドレス指定する方法が必要です。行について考えると、これを概念化するのに役立ちます。ただし、各行の先頭を適切に揃えるために必要な埋め込み文字がこれらの行に含まれる場合、特に、インデックス付きのカラー テーブルを持つビットマップを使用している場合には、この抽象化によって、その物理的な実装が明らかになります (図 6 を参照)。
.gif)
図 6 行と埋め込み文字 (ボトムアップ) (クリックすると拡大画像が表示されます)
Y 軸の方向は、負のストライドで示されるボトムアップ レイアウトを示します。理論的には、この方向がパフォーマンスに影響する可能性もありますが、非常に優れたツール サポートがないと測定は困難です。
優れた同時実行の経験則によると、離れた位置にあるメモリはシングル プロセッサでまとめて使用するべきではなく、近くにあるメモリは異なるプロセッサで使用するべきではありません。つまり、共に使用するデータは近くに保持し、別々に使用されるデータは十分に離れた位置に保持します。このようにすると、ハードウェア キャッシュ マネージャは、競合を発生させずに、異なるプロセッサによって使用されるデータをキャッシュできます。
メモリ レイアウトがパフォーマンスにどのように影響するかを把握するには、メモリが表形式ではなく連続的であることを覚えておく必要があります。仮想アドレス空間はフラットです。図 7 に、図 3 の非効率的なアルゴリズムを使用するとビットマップがどのように分割されるかを示します。
.gif)
図 7 非効率的なデータ分割 (クリックすると拡大画像が表示されます)
これで、このアルゴリズムのパフォーマンスが非常に悪い理由が明らかになりました。ループ実行の依存性はありませんが、アルゴリズムはハードウェア キャッシュ レベルでの競合がほぼ確実に発生するような方法で並列化されています。大きなビットマップでは競合が低減する可能性がありますが、反復的なキャッシュ ミスにより、キャッシュ マネージャはキャッシュ ラインを絶えず再読み込みせざるを得ないため、パフォーマンスに影響します。シングル プロセッサ上でも、キャッシュ ライン内のデータを絶えず置換する必要があるため、パフォーマンスが非常に劣悪になります。図 8 に、その局所性の欠陥をより明確に示します。パターンは、ビットマップ内の行と同じ数だけ繰り返されます。
.gif)
図 8 非効率的なデータ分割 (反復) (クリックすると拡大画像が表示されます)
対照的に、図 5 の効率的なアルゴリズムは、ビットマップを Y 軸に沿って分割するため、各プロセッサは、近くにあるピクセルのストリームを処理し、離れた場所にあるピクセルは他のプロセッサによって処理されます。このため、キャッシュ マネージャは、競合を発生させずにプロセッサ間でビットマップを共有できます (図 9 および 10 を参照)。特に、図 10 は、各プロセスが単一の連続メモリ ブロックを処理し、検索とキャッシングのパフォーマンスが大幅に向上することを示しています。
.gif)
図 9 効率的なデータ分割 (クリックすると拡大画像が表示されます)
.gif)
図 10 効率的なデータ分割 (反復なし) (クリックすると拡大画像が表示されます)
前述の 0.5 秒の目標に達することは、既定で OpenMP により使用される静的スケジューリングでは困難です。OpenMP は、アルゴリズムからこれらの最後の数ミリ秒を搾り出すために使用できる動的なガイド付きスケジューリングも提供します。基本的な問題は、コンピュータはバックグラウンドでいくつかの小さなタスクを実行しているため、作業を使用可能なプロセッサ間で完全に分割しても、最適な結果が得られない可能性があるということです。これにより、スレッドの一部が他のスレッドよりも前に完了し、遅いスレッドの完了を待機している間アイドル状態になる場合があります。
一方、別のアルゴリズムやデータ構造を使用して、これをより高速にすることができます。ビットマップ パーティションを Non-uniform Memory Access (NUMA) システムの個々のノードの物理メモリに読み込むことができます。Windows Server ハイ パフォーマンス コンピューティング (HPC) グリッドの別のノードに送信することもできます。非効率的なアルゴリズムでは、このいずれも不可能です。ポイントは、データ構造とアルゴリズムについて、また実行するハードウェアによってパフォーマンスがどのような影響を受けるかについて少々考えることにより、パフォーマンスを劇的に改善できるということです。
Kenny Kerr は、Windows 向けのソフトウェア開発を専門にしているソフトウェア設計者です。彼はプログラミングおよびソフトウェア設計に関して執筆を行い、開発者を指導しています。連絡先は
weblogs.asp.net/kennykerr です。