OpenMP动态调度的使用及其对性能的影响--如何查找细节

Question

当运行不使用调度和使用调度的算法时，性能差异很大--对于调度，算法在4秒内完成，而非在14秒内完成。我认为perf会提供一些关于为什么会发生这种情况的洞察力，但是这些数据非常相似。

假设通过处理动态调度，我解决了一些负载平衡问题，这是安全的吗？我希望能在细节上找到线索。下面是细节，以防万一有帮助。也是用于Pagerank的代码，其中使用调度..。

    # pragma omp parallel for schedule(dynamic, 64)
    for (int u = 0; u < vertex_count; u++) {
        int* in_edge = G.getAdjList(u);
        double sum = 0.0;
        for (int j = 0; j < in_edge_counts[u]; j++) {
            int v = in_edge[j];
            sum += conntrib[v];
        }
        pr_temp[u] = sum * damp + adj;
    }

利用时间安排

     107470.977295      task-clock (msec)         #    1.743 CPUs utilized
             1,187      context-switches          #    0.011 K/sec
                44      cpu-migrations            #    0.000 K/sec
         2,279,522      page-faults               #    0.021 M/sec
   255,920,277,205      cycles                    #    2.381 GHz                      (20.00%)
    17,116,048,117      stalled-cycles-frontend   #    6.69% frontend cycles idle     (20.02%)
   153,944,352,418      stalled-cycles-backend    #   60.15% backend cycles idle      (20.02%)
   148,412,677,859      instructions              #    0.58  insn per cycle
                                                  #    1.04  stalled cycles per insn  (30.01%)
    27,479,936,585      branches                  #  255.696 M/sec                    (40.01%)
       321,470,463      branch-misses             #    1.17% of all branches          (50.01%)
    78,562,370,506      L1-dcache-loads           #  731.010 M/sec                    (50.00%)
     2,075,635,902      L1-dcache-load-misses     #    2.64% of all L1-dcache hits    (49.99%)
     3,100,740,665      LLC-loads                 #   28.852 M/sec                    (50.00%)
       964,981,918      LLC-load-misses           #   31.12% of all LL-cache hits     (50.00%)

不使用日程安排

      106872.881349      task-clock (msec)         #    1.421 CPUs utilized
             1,237      context-switches          #    0.012 K/sec
                69      cpu-migrations            #    0.001 K/sec
         2,262,865      page-faults               #    0.021 M/sec
   254,236,425,448      cycles                    #    2.379 GHz                      (20.01%)
    14,384,218,171      stalled-cycles-frontend   #    5.66% frontend cycles idle     (20.04%)
   163,855,226,466      stalled-cycles-backend    #   64.45% backend cycles idle      (20.03%)
   149,318,162,762      instructions              #    0.59  insn per cycle
                                                  #    1.10  stalled cycles per insn  (30.03%)
    27,627,422,078      branches                  #  258.507 M/sec                    (40.03%)
       213,805,935      branch-misses             #    0.77% of all branches          (50.03%)
    78,495,942,802      L1-dcache-loads           #  734.480 M/sec                    (50.00%)
     2,089,837,393      L1-dcache-load-misses     #    2.66% of all L1-dcache hits    (49.99%)
     3,166,900,999      LLC-loads                 #   29.632 M/sec                    (49.98%)
       929,170,535      LLC-load-misses           #   29.34% of all LL-cache hits     (49.98%)

Answer 1

schedule(dynamic, 64)告诉OpenMP不要假设每一个内环迭代都需要相同的时间，IIRC。

因此，静态调度将工作分解为u值范围，但您的线程之一必须得到比其他线程更多的总工作(或由于某种原因需要很长时间)，从而延迟所有线程完成的总时间。

它运行在一个有四个AMD Opterons的计算机服务器上。这台机器当时大多是闲置的。两者之间唯一的区别是调度的使用。我省略了时间，因为时间包含了一个预处理步骤，这两个步骤都会发生，但仍然有10秒的差异。

在这种情况下，1.4对1.7个CPU的总体利用率可以解释为在4/ 14秒内使用了更多的CPU。您可以通过使程序在并行部分之前退出，并对其进行分析，从而近似于有趣部分的结果。从你的总数中减去这些数，得到一个非常粗略的近似。

IDK为什么工作是不平衡的；这是您的代码+数据；G.getAdjList(u)可能要花费更多的时间，或者更有可能的是，对于某些线程来说，in_edge_counts[u]更大。

conntrib[in_edge[j]]的局部性差异可能会造成很大的差异，当不同的in_edge元素接近以前的值时，会导致对分散读取或缓存命中的缓存丢失。

当不同的内核竞争内存+最后一级的缓存带宽时，延迟为in_edge值的缓存行提供服务将比对一行conntrib[]的延迟响应更糟糕，因为CPU需要in_edge[]数据，才知道更多的conntrib数据需要哪些缓存线。因此，in_edge缓存丢失减少了内存并行性，可能会使线程获得更少的内存带宽。

看看这些影响会有多大程度的平衡。更有可能的是，您的数据分布不均匀。

不幸的是，AMD没有高效的AVX2收集，因为您的数据是完美的vpgatherdd ymm。这并不是说它对公平或任何事情都有帮助，只是(在Skylake上)给出一个可能的小加速比标量集合。

Answer 2

perf stat不是理解多线程程序中动态调度的性能影响的合适工具。为此，您需要一个工具，它允许您在分析期间区分线程和时间。

perf timechart可能值得一试，但它并没有特别注意到OpenMP。通过使用专门针对OpenMP的分析工具，您将获得最好的洞察力。此外，为了获得动态，我建议使用跟踪/时间线工具，而不是只显示摘要的分析工具。这样一个工具的例子是英特尔VTune或分-P (跟踪)/ 范皮尔 (可视化)。