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

同カテゴリーの次の記事

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

この記事は、インテル® デベロッパー・ゾーンに公開されている「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* 関連のヒント この記事は、インテル® ソフトウェア・サイトに掲載されている「OpenMP Related Tips」の日本語参考訳です。 OpenMP* ループの一重化 各スレッドで処理される作業の粒度を減らすことで利用可能なスレッド全体で分割される反復の総数を増やすには、OpenMP* collapse […]
  • ループのベクトル化によるプログラムの最適化ループのベクトル化によるプログラムの最適化 この記事は、インテル® デベロッパー・ゾーンに掲載されている「Program Optimization through Loop Vectorization」の日本語参考訳です。 はじめに この記事では、有限差分ステンシル計算を例に、インテル® メニー・インテグレーテッド・コア (インテル® MIC) […]
  • インテル® Parallel Debugger Extensionインテル® Parallel Debugger Extension この記事は、インテル® ソフトウェア・ネットワークに掲載されている「Intel® Parallel Debugger Extension」の日本語参考訳です。 はじめに この記事では、インテル® Parallel Studio 2011、インテル® Parallel Studio XE 2011、インテル® […]
  • GCC 5.0 での x86 向けの最適化新機能GCC 5.0 での x86 向けの最適化新機能 この記事は、インテル® デベロッパー・ゾーンに公開されている「New optimizations for X86 in upcoming GCC 5.0」の日本語参考訳です。パート 1 ロード/ストアグループのベクトル化GCC 5.0 […]
  • MPI と OpenMP* の併用によりハードウェアを活用するMPI と OpenMP* の併用によりハードウェアを活用する この記事は、インテル® ソフトウェア・ネットワークに掲載されている「Mixing MPI and OpenMP, hugging hardware and dealing with it」の日本語参考訳です。 今朝、私は珍しく時間がとれたため、Supercomputing […]