0

parallel_for を使用してアルゴリズムを実装しました。しかし、私は主に同期セクションを使用しているため、利益はありません。たぶん、より良いオプションがありますか？

    tbb::parallel_for (tbb::blocked_range<int>(1, m * n), apply_transform(d, j, this, m, n));

    void apply_transformation(int * d, int i, int j, int n){
        int elem1 = (*v1)[i];
        int elem2 = (*v2)[j];
        if(elem1 == elem2){
            dLock.acquire(dMutex);
            d[i*n + j] = d[(i-1)*n + j-1];       // no operation required
            dLock.release();
        } else {
            dLock.acquire(dMutex);
            d[i*n + j] = std::min(std::min(d[(i-1)*n + j] + 1, //deletion
                    d[i*n + j-1] + 1), //insertion
                    d[(i-1)*n + j-1] + 1); //substitution
            dLock.release();
        }
    }

    class apply_transform{
        int * array;
        int m_j;
        Levenstein * m_l;

        int m, n;
        public:
            apply_transform (int* a, int j, Levenstein * l, int width, int height):
                array(a), m_j(j), m_l(l), m(width), n(height) {}

            void operator()(const tbb::blocked_range<int>& r ) const {
                for (int i=r.begin(); i!=r.end(); i++ ){
                    m_l->apply_transformation(array, i, m_j, n);
                }
            }
    };
4

1 に答える 1

5

レーベンスタイン距離の計算は本質的に波面パターンであり、 の計算には、、およびd(i,j)の知識が必要です。これらの依存関係は、タスクの DAG を自然に形成します。計算するタスクは、すべての先行タスク (およびその先行タスクなど) が完了したときにのみ実行できます。すべての依存関係が解決され、相互に依存していないタスク (と など) は、並行して処理できます。依存関係に従うことを除いて、他の同期は必要ありません。d(i-1,j-1)d(i-1,j)d(i,j-1)d(i,j)d(1,2)d(2,1)

TBB で波面パターンを表現する方法はいくつかあります。低レベルのタスク (複雑で推奨されません) を使用する方法parallel_doと、アトミック カウンターを使用する方法 ( TBB 設計パターンのドキュメントで説明されているように、そこで使用されている例は、あなたが行うことに非常に近いものです)およびフロー グラフ ( TBB ブログで説明されているように) を使用します。これらのドキュメントを調べて、独自の実験を行うことをお勧めします。

d(i,j)また、シングルを計算するための作業量は、並列実行のオーバーヘッドを正当化するには小さすぎることに注意してください。スピードアップを達成するには、長方形の計算ブロックを 1 つのタスクに集約し、タスク内でブロック要素を順次処理します。ブロックは同じ依存パターンを持ちます。ただし、作成するブロックが大きいほど、使用できる並列処理が少なくなるため、最適なパフォーマンスを得るためにブロック サイズを試してみることをお勧めします。

于 2012-12-19T21:22:28.977 に答える