とらえどころのないアルゴリズム – 並列スキャン (追記)

2015年6月4日

プログラマーの生産性を高める

この記事は、インテル® デベロッパー・ゾーンに公開されている「Elusive Algorithms – Parallel Scan」の日本語参考訳です。

先月、IDZ の MIC フォーラムでの問い合わせ “C 言語でインテル® Cilk™ Plus を使用して包括的なスキャンを行うには? に回答しました。

この例を並列化するのは、依存性の問題があります (直前の結果に依存する次の結果)。並列化は不可能ではありませんが、かなり困難でありいくらかの冗長性をもたらします。

熟練したプログラマーが知っているように、あることが “できない” という用語は滅多に用いられません。そして、”問題がある” という用語は、目標を達成するため作業をしなければならないことを意味します。包括的なスキャンは、時間の依存性を伴う 1 行のループです:

    float sum = 0;
    for ( int i = 0; i < N; i++ )
    {
        Res[ i ] = (sum += A[ i ]);
    }

"問題がある" と表明した後、問題への取り組みによる利点がそれを克服する作業を上回るかを確かめることができることを実証することが唯一の行動であると考えています。このリンク先にある PDF の記事を読んでいただくと、よく理解いただけます。

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

OpenMP* 関連のヒントこの記事は、インテル® ソフトウェア・サイトに掲載されている「OpenMP Related Tips」の日本語参考訳です。 OpenMP* ループの一重化各スレッドで処理される作業の粒度を減らすことで利用可能なスレッド全体で分割される反復の総数を増やすには、OpenMP* collapse […]
ループのベクトル化によるプログラムの最適化この記事は、インテル® デベロッパー・ゾーンに掲載されている「Program Optimization through Loop Vectorization」の日本語参考訳です。はじめにこの記事では、有限差分ステンシル計算を例に、インテル® メニー・インテグレーテッド・コア (インテル® MIC) […]
MPI と OpenMP* の併用によりハードウェアを活用するこの記事は、インテル® ソフトウェア・ネットワークに掲載されている「Mixing MPI and OpenMP, hugging hardware and dealing with it」の日本語参考訳です。今朝、私は珍しく時間がとれたため、Supercomputing […]
ポピュラーなオープンソース・プロジェクトのエラーを見つけるクイズに挑戦しようこの記事は、インテル® デベロッパー・ゾーンに公開されている「Let's Play a Game - find bugs in popular open-source projects」の日本語参考訳です。 PVS-Studio スタティック・コード・アナライザーの開発者達よって、プログラマー向けに C/C++ […]
ギャザーによる構造化されたデータのベクトル化この記事は、インテル® デベロッパー・ゾーンに掲載されている「Best Known Method: Coaxing the Compiler to Vectorize Structured Data via […]

関連記事