OpenMP并行独立BFS最短路径实例运行缓慢原因排查

AI 小北

2026-7-22

OpenMP并行BFS性能异常问题

问题概述

针对含600,000个节点、2,000,000条边的图，对14k组独立节点对运行BFS求最短路径。测试结果显示：

串行迭代耗时30分钟
使用OpenMP并行迭代耗时50分钟，性能不升反降，未达到预期加速效果
代码无临界区或复杂瓶颈，修改BFS函数减少内存分配后问题仍存在
日志中出现重复任务，怀疑omp_get_thread_num()返回的线程号无效

代码片段

BFS函数

int bfs(int src, int dst, int thread) {
    const int _VERTEX = 600000; 
    std::stringstream msg;
    msg << "Finding shortest path using bfs from : " << src <<" to " << dst <<   " using thread " << thread << endl;
    
    cout << msg.str();
    
    std::vector<int>dist (_VERTEX,INT_MAX);
    std::vector<bool> visited(_VERTEX,false);
    
    std::queue <int> q;
    q.push(src);
    visited[src] = true;
    dist[src] = 0;
    
    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            int curr = q.front();
            q.pop();
            for (vector<int> ::iterator it = _ADJLST[curr].begin();  it != _ADJLST[curr].end(); ++it) {
                if (visited[*it]) {continue;}
    
                if (dist[*it] > dist[curr] +1) {
                    dist[*it] = dist[curr] + 1;
                    q.push(*it);
                }
                // if (curr == dst) {return dist[dst];}
                visited[*it] = 1;
            }
        }
    }
    return dist[dst];
}

主函数

int main() {

    int i, tid, nthreads;
    
    // #pragma omp parallel for private(i,tid,threads)  
    schedule(dynamic,1)
    #pragma omp parallel for private(i,tid,nthreads)
    for (i = 0 ; i < _PAIRLST.size(); i++) {
        int src = _PAIRLST[i].first ;
        int dst = _PAIRLST[i].second;
    
        tid = omp_get_thread_num();
        bfs(src,dst,tid);

}