4

私はOpenMPを使用してダイクストラアルゴリズムの並列バージョンを作成しています。私のコードは2つの部分で構成されています。最初の部分は1つのスレッド（マスター）によってのみ実行されます。このスレッドは、リストから新しいノードを選択します。2番目の部分は他のスレッドによって実行されます。これらのスレッドは、ソースから他のノードへの距離を変更します。残念ながら、私のコードでは、2番目の部分を実行する多くのスレッドの1つが突然「消える」ため、エラーが発生します。おそらくデータ同期に問題がありますが、どこにあるのかわかりません。誰かが私の間違いがどこにあるか教えてくれたらありがたいです。コードは次のとおりです。

map<int, int> C;
map<int, int> S;
map<int, int> D;
int init;
int nu;
int u;
int p = 3;//omp_get_num_threads();
int d;
int n = graph->getNodesNum();

#pragma omp parallel shared(n, C, d, S, init, nu, u, D, graph, p) num_threads(p)
{
    int myId = omp_get_thread_num();
    if (myId == 0)
    {
        init = 0;
        nu = 0;

        u = to;
        while (init < p - 1)
        {
        }

        while (u != 0)
        {
            S[u] = 1;
            while (nu < p - 1)
            {
            }
            u = 0;
            d = INFINITY;
            for (int i = 1; i <= p - 1; ++i)
            {
                int j = C[i];
                if ((j != 0) && (D[j] < d))
                {
                    d = D[j];
                    u = j;
                }
            }
            nu = 0; 
        }
    }
    else
    {
        for (int i=myId; i<=n; i += p-1)
        {
            D[i] = INFINITY;
            S[i] = 0;
        }

        D[u] = 0;

        ++init; 
        while (init < p-1)
        {
        }
        while (u != 0)
        {
            C[myId] = 0;
            int d = INFINITY;

            for (int i = myId; i<=n; i+=p-1)
            {
                if (S[i] == 0)
                {
                    if (i != u)
                    {
                        int cost = graph->getCostBetween(u, i);
                        if (cost != INFINITY)
                        {
                            D[i] = min(D[i], D[u] + cost);
                        }
                    }
                    if ((d > D[i])) 
                    {                           
                        d = D[i];
                        C[myId] = i;
                    }
                }
            }
            ++nu;
            while (nu != 0)
            {
            }   
        }
    }       
}

}

4

1 に答える 1

11

あなたがどのような情報を持っているかはわかりませんが、不規則で高度に同期化されたアルゴリズムを小さなタスクで並列化することは、最も困難な並列問題の 1 つです。研究チームは、そのようなタスクに専念し、限られたスピードアップしか得られないか、まったく役に立たない可能性があります。多くの場合、このようなアルゴリズムは、並列化用に調整された特定のアーキテクチャでのみ機能し、データ構造を適切に設計することで、偽共有などの風変わりなオーバーヘッドが排除されています。

このようなアルゴリズムは、プロファイリング、測定、検討に多くの時間と労力を必要とします。たとえば、この論文を参照してください。

ww2.cs.fsu.edu/~flin/ppq_report.pdf

さて、あなたの直接的な質問に移りますが、あなたのアルゴリズムは高度に同期化されており、タスクが小さいため、データ競合の副作用が発生しています。これらを並列アルゴリズムから削除するのは非常に難しい作業であり、誰もあなたのためにそれを行うことはできません。

そのため、最初に呼び出すポイントは、Valgrind や Intel スレッド チェッカーなどのデータ競合を検出するのに役立つツールを調べることです。

于 2012-07-02T18:04:43.740 に答える