この記事は、インテル® デベロッパー・ゾーンに公開されている「Elusive Algorithms – Parallel Scan」(https://software.intel.com/en-us/blogs/2015/05/22/elusive-algorithms-parallel-scan) の日本語参考訳です。
先月、IDZ の MIC フォーラムでの問い合わせ “C 言語でインテル® Cilk™ Plus を使用して包括的なスキャンを行うには?” (https://software.intel.com/en-us/forums/topic/545054) に回答しました。
この例を並列化するのは、依存性の問題があります (直前の結果に依存する次の結果)。並列化は不可能ではありませんが、かなり困難でありいくらかの冗長性をもたらします。
熟練したプログラマーが知っているように、あることが “できない” という用語は滅多に用いられません。そして、”問題がある” という用語は、目標を達成するため作業をしなければならないことを意味します。包括的なスキャンは、時間の依存性を伴う 1 行のループです:
float sum = 0;
for ( int i = 0; i < N; i++ )
{
Res[ i ] = (sum += A[ i ]);
}
"問題がある" と表明した後、問題への取り組みによる利点がそれを克服する作業を上回るかを確かめることができることを実証することが唯一の行動であると考えています。このリンク先にある PDF の記事を読んでいただくと、よく理解いただけます。
コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください
