OpenMP Task构造无法随线程数扩展的性能问题问询

我使用OpenMP task构造并行化二叉树应用，但运行性能显示单线程实现优于多线程实现，该如何解读此结果？

实现代码 #

size_t N = 1 << 16;
size_t *D = new size_t [N];
size_t threads = 1;  // 1, 2, 4, 8, 16

std::vector<std::vector<int>> mat1(128); // 二维矩阵
std::vector<std::vector<int>> mat2(128); // 二维矩阵

for(size_t i = 0; i < mat1.size(); ++i){
  mat1[i].resize(128);
  mat2[i].resize(128);
}

#pragma omp parallel num_threads(threads)
{
  #pragma omp single
  {
    for(size_t i = 1; i < N; ++i) {

      size_t p = i / 2;
      size_t l = i * 2;
      size_t r = l + 1;

      if(l < N && r < N) {
        #pragma omp task firstprivate(i) depend(out:D[l], D[r]) depend(in:D[p])
        {
          // 执行矩阵乘法
          for(size_t x = 0; x < 128; ++x) {
            for(size_t y = 0; y < 128; ++y) {
              size_t sum = 0;
              for(size_t z = 0; z < 128; ++z) {
                //sum += mat1[x][z] * mat2[z][y];
                sum += mat1[x][z] * mat2[y][z]; // 转置mat2以优化内存访问模式
              }
            }
          }     
        }
      }
      else {
        #pragma omp task firstprivate(i) depend(in:D[p])
        {           
          // 执行矩阵乘法
          for(size_t x = 0; x < 128; ++x) {
            for(size_t y = 0; y < 128; ++y) {
              size_t sum = 0;
              for(size_t z = 0; z < 128; ++z) {
                //sum += mat1[x][z] * mat2[z][y];
                sum += mat1[x][z] * mat2[y][z]; // 转置mat2以优化内存访问模式
              }
            }
          }     
        }
      }
    }
  }
}

delete [] D;

实验现象 #

• 将矩阵乘法替换为sleep后，运行性能随线程数增加具备良好扩展性
• 矩阵乘法的性能曲线图：
  
• sleep的性能曲线图：
  
• 若将矩阵乘法替换为轻量操作（如size_t sum = i * 1000，其中i为每个task的私有值），则观察到与矩阵乘法相同的无扩展性表现

运行环境与预期 #

代码使用gcc-12编译并开启-O3优化，运行环境为Ubuntu 19.10，配备80核Intel Xeon Gold 6138 CPU（2.00GHz）及256GB内存。原本预期性能与线程数呈凸曲线，最优值出现在4或8线程。

原因解读 #

1. 任务调度开销远超计算收益 #

OpenMP Task的创建、依赖关系维护、线程间任务分发/窃取都存在固定开销。当每个Task内部的计算量（无论是128x128矩阵乘法还是简单算术操作）较小时，这些调度开销的占比会极高，导致多线程的总耗时超过单线程直接执行的时间。

而sleep属于阻塞型任务，线程在sleep期间不占用CPU，调度开销相对于sleep时长可以忽略，因此多线程能有效利用空闲CPU资源，展现出扩展性。

2. 数据局部性与缓存竞争问题 #

矩阵乘法中，mat1和mat2是全局共享的二维vector，多线程并发访问时容易出现伪共享（false sharing），导致缓存行频繁失效，大幅降低内存访问效率。单线程下数据访问的局部性更好，缓存命中率更高，计算效率自然优于多线程。

3. 任务依赖限制了并行度 #

每个Task都依赖父节点的D[p]，形成链式依赖关系。OpenMP Runtime需要维护这些依赖，可能导致线程无法及时获取可执行的Task，出现空闲等待；而单线程无需处理依赖调度，直接按顺序执行，避免了等待开销。

4. 编译器优化的差异 #

开启-O3后，单线程下的矩阵乘法会被编译器进行深度优化（如循环展开、向量化、内联等）；但多线程Task的边界会限制编译器的跨Task优化，导致Task内的代码优化不充分，进一步拉大了单线程与多线程的性能差距。

优化建议 #

• 合并小任务：将多个相邻二叉树节点的计算合并为单个Task，减少任务创建和调度的总开销，让每个Task的计算量足以覆盖调度成本。
• 优化数据局部性：为每个线程分配独立的矩阵副本，避免共享数据的缓存竞争；改用一维数组代替二维vector，提升内存访问的连续性和缓存命中率。
• 调整依赖策略：评估是否需要严格的依赖关系，若可放松依赖则减少depend子句的使用，降低Runtime的依赖维护开销。
• 使用Taskloop简化任务创建：对于二叉树遍历这类场景，#pragma omp taskloop比手动创建Task更高效，Runtime能自动平衡任务粒度。

内容的提问来源于stack exchange，提问作者chchiu