並列プログラミングの性能最適化

Tiffany Trader

並列計算とは、問題を計算によって解くために、複数のプロセッサーを同時に使うことである。大きな問題は小さな部品に分解され、それから、並行して解かれる。計算の長い歴史において、逐次計算が行われた。即ち、ある命令セットを実行し、そして次に進むのである。並列計算は、(CPUクロックの)周波数を上げても性能がスケーリングせず、消費電力が増大するという問題を解決するために興った。

過去10年間ほどの間、並列計算は支配的なコンピューティング・パラダイムに育ってきた。逐次計算から並列計算への移行は、1個のコアからマルチコア・プロセッサーへの移行と共に、より高性能な計算機への要求を実現するための鍵である。

最近、Michael McCool氏とArch Robinson氏とJames Reinders氏によってDr. Dobbsに書かれた記事によると、並列プログラミングの性能についての基本的な理論は、Amdahlの法則とGustafson-Barsisの法則に導かれる。これらの法則は、並列最適化と、ストロング・スケーリングとウィーク・スケーリングを示す。

並列性能の最適化は、主要な3個の変数に関連する。レイテンシーを減らし、スループットを上げ、CPUの消費電力を減らすことである。要素は互いに関連し、一つの改善で別の要素が悪化することもある。したがって、最大効率を得るために、3つの要素のバランスが、開発者の課題になる。開発者は、特定の計算問題のレイテンシーを図示でき、プロセッサーの数が増えるにつれて、「speed-up」が付いてくる割合を、実際に実行する前に調べられる。同じ規模の問題をより速く計算することは、ストロング・スケーリングとも呼ばれているAmdahlの法則が反映される。より大規模な問題を同じ時間で計算することは、ウィーク・スケーリングとも呼ばれ、Gustafson-Barsisの法則が反映される。

理想的には、測度向上は直線的であり、プロセッサーの数を2倍にすれば計算時間は半分になる。しかし、ほんの少しのアルゴリズムしか、このように高速化する方法が解っていない。一般的に、プロセッサーの数が少なければ、直線的に性能が向上するが、より多くのプロセッサーを追加すると、性能の向上が直線を下回る。様々な理由で、まれに、性能の向上が直線を上回るスーパー・リニアも起こる。

著者は指摘する。「速度の向上は、効果的でないが、並列計算機の宣伝の中に見るのは、速度の向上が大きな印象を与える数値だからである。効率は、特別な例外を除いて、100％を超えず、しばしばもっと低い値である。同じ1000コアの計算機と同じプログラムを使って、100％の高速化は、10％の高速化よりも良いことであると聞こえる」

Amdahlの法則は、並列プラットフォーム上でのアルゴリズムの潜在的な測度向上について述べる。Gene Amdahlによって1967年に提案された法則は、並列化による速度の向上が、プログラムの並列化できなかった部分によって制限されると示している。このAmdahlの法則から導かれることは、「プログラムの逐次処理の処理効率が伴わない限り、並列化に費やす努力は無駄になるということだ。」

Amdahlの法則は、問題の規模を固定して考えている。John L. Gufafsonによって1988年に示されたGuftafson-Barsisの法則は、問題の規模を増やせれば測度向上がどうなるかと考えている。John Gustafson自身の言葉によると、「問題の規模を固定してではなく、問題の規模とプロセッサーの数の組み合わせによって、高速化を測定すべきだ。」

記事は、著者らの書籍「Structured Parallel Programming: Patterns for Efficient Computation」のいくつかの章を元にしている。並列処理の基本を学び直したい方々にとって、この書籍はお勧めである。この分野の非常に尊敬される先覚者である著者らは、情報と関連する正確な方程式を明確に表現している。