PROSAGA码农传奇-调度引擎-OpenMP动态与引导式调度

<div class =“post-text”itemprop =“text”>
  <BLOCKQUOTE>
    
      是什么影响了引导式调度的运行时？
    
  </BLOCKQUOTE>
  
    需要考虑三种效果：
  
  <H1>
    1.负载平衡
  </H1>
  
    动态/引导调度的重点是在每个循环迭代不包含相同工作量的情况下改进工作分配。从根本上说：
  
  <UL>
    <LI>
       <code>
 schedule(dynamic, 1)
 </code>
       提供
      的
        最佳负载平衡
      </强>
    </LI>
    <LI>
       <code>
 dynamic, k
 </code>
       永远都会
      的
        相同或更好
      </强>
       负载均衡比
       <code>
 guided, k
 </code>
    </LI>
  </UL>
  
    标准要求每个块的大小
    的
      成比例的
    </强>
     到未分配的迭代次数除以团队中的线程数，
减少到
     <code>
 k
 </code>
    。
  
  
    该
    <a href="https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8e8270c597270a1a7967/libgomp/iter.c" rel="noreferrer">
      GCC OpenMP实现
    </A>
     从字面上看，忽略了
    
      成比例的
    
    。例如，对于4个线程，
     <code>
 k=1
 </code>
    ，它将32次迭代
     <code>
 8, 6, 5, 4, 3, 2, 1, 1, 1, 1
 </code>
    。现在恕我直言这是非常愚蠢的：如果前1 / n次迭代包含超过1 / n的工作，则会导致负载不平衡。
  
  <BLOCKQUOTE>
    
      具体例子？在某些情况下，为什么它比动态慢？
    
  </BLOCKQUOTE>
  
    好的，让我们看看一个简单的例子，其中内部工作随着循环迭代而减少：
  
   <pre>
 <code>
 #include <omp.h>

void work(long ww) {
 volatile long sum = 0;
 for (long w = 0; w < ww; w++) sum += w;
}

int main() {
 const long max = 32, factor = 10000000l;
 #pragma omp parallel for schedule(guided, 1)
 for (int i = 0; i < max; i++) {
 work((max - i) * factor);
 }
}

</code>
 </pre>
  
    执行看起来像这样
    
      1
    
    ：
  
  
    <a href="https://i.stack.imgur.com/8DsXa.png" rel="noreferrer">
      <img src =“https://i.stack.imgur.com/8DsXa.png”alt =“示例执行时间表”/>
    </A>
  
  
    如你看到的，
     <code>
 guided
 </code>
     在这里真的很糟糕
     <code>
 guided
 </code>
     对于不同类型的工作分配会做得更好。也可以不同地实施指导。 clang（IIRC源于英特尔）的实现是
    <a href="https://github.com/llvm-mirror/openmp/blob/9c1e6c9bc10be652b92c40129c43c027aadc57b6/runtime/src/kmp_dispatch.cpp" rel="noreferrer">
      更复杂
    </A>
    。我真的不明白GCC天真实施背后的想法。在我看来，如果你给予它，它有效地击败了动态负载消除的目的
     <code>
 1/n
 </code>
     工作到第一个线程。
  
  <H1>
    2.开销
  </H1>
  
    现在，由于访问共享状态，每个动态块都会对性能产生一些影响。的开销
     <code>
 guided
 </code>
     每块会略高一些
     <code>
 dynamic
 </code>
    ，因为有更多的计算要做。然而，
     <code>
 guided, k
 </code>
     总动态块数将少于
     <code>
 dynamic, k
 </code>
    。
  
  
    开销还取决于实施，例如，它是否使用原子或锁来保护共享状态。
  
  <H1>
    3.缓存和NUMA效果
  </H1>
  
    假设在循环迭代中写入整数向量。如果每个第二次迭代要由不同的线程执行，则向量的每个第二个元素将由不同的核心写入。这真的很糟糕，因为通过这样做，他们竞争包含相邻元素的缓存行（虚假共享）。如果您的小块大小和/或块大小不能很好地与缓存对齐，则会在块的“边缘”处获得不良性能。这就是为什么你通常喜欢大的好（
     <code>
 2^n
 </code>
    ）块大小。
     <code>
 guided
 </code>
     平均可以给你更大的块大小，但不是
     <code>
 2^n
 </code>
     （要么
     <code>
 k*m
 </code>
    ）。
  
  
    <a href="https://stackoverflow.com/a/10852852/620382">
      这个答案
    </A>
     （您已经引用过），详细讨论了NUMA方面的动态/引导调度的缺点，但这也适用于locality / caches。
  
  <H1>
    不要猜测，衡量
  </H1>
  
    鉴于预测细节的各种因素和难度，我只建议使用您的特定编译器在您的特定系统，特定配置中测量您的特定应用程序。不幸的是，没有完美的性能可移植性。我个人认为，这尤其如此
     <code>
 guided
 </code>
    。
  
  <BLOCKQUOTE>
    
      什么时候我会支持引导动态，反之亦然？
    
  </BLOCKQUOTE>
  
    如果您对开销/每次迭代工作有特定的了解，我会这么说
     <code>
 dynamic, k
 </code>
     给你选择一个好的最稳定的结果
     <code>
 k
 </code>
    。特别是，您并不太依赖于实现的巧妙程度。
  
  
    另一方面，
     <code>
 guided
 </code>
     可能是一个很好的初步猜测，具有合理的开销/负载平衡比，至少对于一个聪明的实现。要特别小心
     <code>
 guided
 </code>
     如果你知道后来的迭代时间更短。
  
  
    请记住，还有
     <code>
 schedule(auto)
 </code>
    ，它完全控制编译器/运行时，和
     <code>
 schedule(runtime)
 </code>
    ，允许您在运行时选择调度策略。
  
  <BLOCKQUOTE>
    
      一旦解释了这个，上面的来源是否支持您的解释？他们完全矛盾吗？
    
  </BLOCKQUOTE>
  
    拿一些来源，包括这个anser，用一粒盐。您发布的图表和我的时间线图片都不是科学上准确的数字。结果存在巨大差异，并且没有误差条，它们可能只是在这些极少数据点的地方。此图表结合了我提到的多重效果而没有透露
     <code>
 Work
 </code>
     码。
  
  
    [来自英特尔文档]
  
  <BLOCKQUOTE>
    
      默认情况下，块大小约为loop_count / number_of_threads。
    
  </BLOCKQUOTE>
  
    这与我的观察结果相矛盾，即icc更好地处理我的小例子。
  
  
    
      1：使用GCC 6.3.1，Score-P / Vampir进行可视化，两个交替的工作功能用于着色。
    
  
</DIV>