マルチコア環境向け並列アプリケーションの最適化

この記事は、インテル® デベロッパー・ゾーンに掲載されている「Optimization of a Parallel Application for Multi-Core Environments」の日本語参考訳です。

(これは、筆者がインテル社でインターンシップをしていたときに取り組んでいたプロジェクトです。)

アムダールの法則から、マルチコア環境において、並列アプリケーションのパフォーマンスはシリアル領域によって制限されることが分かっています。並列アプリケーションには必ず並列でないシリアル領域があり、コア数を増やすことでパフォーマンスを向上しようとする際、これがボトルネックとなります。シリアル領域を並列化する方法を見つけるか、効率良いアルゴリズムとデータ構造によりシリアル領域のパフォーマンスを向上して高速化することで、これらのボトルネックの影響を抑える必要があります。

ここでは、シリアル領域によって制限された Canneal アプリケーションのパフォーマンスを向上する方法を考えてみます。

Canneal は、PARSEC Benchmarking Suite に含まれるアプリケーションです。PARSEC は、オープンソースのマルチプロセッサー・ベンチマーク・ツールです (http://parsec.cs.princeton.edu/)。このアプリケーションは、入力としてファイルからファンインとファンアウトを含む 250 万件のネットリストを受け取り、チップ設計の最短経路を計算します。最初にシリアルのグリッド構築フェーズ、次に並列の経路計算フェーズ、そして最後にシリアルの経路計算フェーズがあります。以下の図は、80 論理コアのシステムにおいて異なるスレッド数でアプリケーションを実行した際のパフォーマンス・スケーリングを表わしています。[パフォーマンス・スケーリング: 1 スレッドで実行したアプリケーションの実行時間/x スレッドで実行したアプリケーションの実行時間]。

図 1: 最適化前の Canneal アプリケーションのパフォーマンス・スケーリング

以下の図 2 は、80 スレッドでアプリケーションを実行した際の CPU 負荷 を示す MPSTAT データです。

図 2: CPU 負荷を示す MPSTAT データ

80 スレッドでアプリケーションを実行した際、シリアルのグリッド構築に実行時間全体の 67%、シリアルの経路計算に 14% が費やされていることが分かります。グリッド構築では、C++ STL の map を用いて、ネットリスト名に基づいて 250 万件のネットリストの格納と検索を行っています。ネットリスト名は、最長 5 文字の一意の文字列 (小文字) です。C++ STL の map は、データを格納するため、内部で赤黒木 (Red Black Tree) を使用しています。赤黒木の構築と検索には、それぞれ O(n log n) 時間と O(log n) 時間かかります。

次のセクションで、このアプリケーションを最適化する 1 つのアプローチについて述べます。

グリッド構築の最適化:
C++ STL の map の代わりに、5 次元配列を利用してネットリストの格納と検索を行います。配列のインデックスは、以下に示すようにネットリスト名に含まれる 1 文字に由来します。この配列ベースのアプローチは、検索に O(1) 時間、グリッド構築に O(n) 時間かかります。

const int ARRAY_MAX = 27;  const int INDEX_HASH = 96;
Netlist* _netlistArray[ARRAY_MAX][ARRAY_MAX][ARRAY_MAX][ARRAY_MAX][ARRAY_MAX];
Index1 = netlistName[0] – INDEX_HASH; Index2 = netlistName[1] – INDEX_HASH;
Index3 = netlistName[2] – INDEX_HASH; Index4 = netlistName[3] – INDEX_HASH;
Index5 = netlistName[4] – INDEX_HASH;

最後の経路計算の最適化:
コードを並列化して、250 万件のネットリスト配列をアプリケーション・スレッド間で分配し、経路値を合計します。最終経路値は、すべてのスレッドによって計算された経路値の合計になります。

以下の図は、これらの最適化を実装した Canneal アプリケーションと最適化前のアプリケーションのパフォーマンス・スケーリングの比較です。

図 3. 最適化した Canneal アプリケーションのパフォーマンス・スケーリング

上記の最適化アプローチにより、Canneal アプリケーションのパフォーマンスを 2.6 倍も向上することができました。

コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。