并行Dijkstra

Question

我正在使用OpenMP来制作Dijkstra算法的并行版本.我的代码由两部分组成.第一部分仅由一个线程(主)执行.该线程从列表中选择新节点.第二部分由其他线程执行.这些线程改变了从源到其他节点的距离.我的代码中不幸的是错误,因为执行第二部分的许多线程之一突然"消失".可能数据同步存在问题,但我不知道在哪里.如果有人能告诉我我的错误在哪里,我将不胜感激.这是代码:

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)
            {
            }   
        }
    }       
}

}

Answer 1

我不知道你有什么信息,但是将不规则的,高度同步的算法与小任务并行化是最棘手的并行问题之一.研究团队可以专注于此类任务并获得有限的加速,或者无处可用.通常,这种算法仅适用于为并行化定制的特定体系结构,并且通过适当地设计数据结构已经消除了诸如错误共享之类的奇怪开销.

诸如此类的算法需要花费大量时间和精力来进行分析,测量和考虑.例如,参见本文.

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

现在,直接问题,由于您的算法高度同步且任务很小,您将遇到数据争用的副作用.要从并行算法中删除这些将是非常棘手的,这里没有人能为你做到这一点.

因此,您的第一个要点是查看可以帮助您检测数据竞争的工具,例如Valgrind和Intel线程检查程序.