使用 OpenMP 优化大图遍历

Question

我正在尝试优化此功能，根据 perf 工具，这是接近线性缩放的归档瓶颈。当线程数量增加时，性能会变得更差，当我向下钻取由 perf 生成的汇编代码时，它显示大部分时间都花在检查已访问和未访问的顶点上。我已经进行了大量的谷歌搜索以提高性能但无济于事。有没有办法提高这个功能的性能？或者是否有实现此功能的线程安全方法？提前感谢您的帮助！

void bfs_step(Graph &g, vidType *depth, SlidingQueue<vidType> &queue) {
  #pragma omp parallel
  {
    QueueBuffer<vidType> lqueue(queue);

    #pragma omp for
    
    for (auto q_iter = queue.begin(); q_iter < queue.end(); q_iter++) {
      auto src = *q_iter;
      for (auto dst : g.N(src)) {
        //int curr_val = parent[dst];
        auto curr_val = depth[dst];
        if (curr_val == MYINFINITY) { // not visited
          //if (compare_and_swap(parent[dst], curr_val, src)) { 
          if (compare_and_swap(depth[dst], curr_val, depth[src] + 1)) {
            lqueue.push_back(dst);
          }
        }
      }
    }
    lqueue.flush();
  }
}