この記事は、インテル® デベロッパー・ゾーンに公開されている「Elusive Algorithms – Parallel Scan」(https://software.intel.com/en-us/articles/elusive-algorithms-parallel-scan) の日本語参考訳です。
並列プログラミングに関するこの記事は、一見するとベクトル化や並列化が不可能に思われる、「見つけにくいアルゴリズム」のいずれかを選択します。この記事の目標は、特定のアルゴリズムに対処するだけでなく、むしろ類似するアルゴリズムに向けたアプローチを提供することです。この記事における「とらえどころのないアルゴリズム」は、次のような包括的なスキャンです:
In: 1 2 3 4 5 6 7 8 …
Out: 1 3 6 10 15 21 28 36 …
ここで、出力は前の出力の和 (最初は 0) であり、入力値です。このループは、ベクトル化と並列化を妨げる時間の依存性を持っています。次の記事では、このようなケースにベクトル化と並列化の両方を実現する方法について説明しています:
とらえどころのないアルゴリズム – parallel scan.pdf (452.39 KB)
(https://software.intel.com/sites/default/files/managed/10/a4/Elusive%20Algorithms%20-%20parallel%20scan.pdf)
コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください
