OpenMP动态调度的使用及其对性能的影响——如何查找详情
The use of OpenMP dynamic scheduling and its impact on performance - how to find detail
当 运行 一个不使用调度的算法和使用调度的算法时，性能差异是巨大的 - 使用调度，算法在 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%)
perf stat 不是了解多线程程序中动态调度的性能影响的正确工具。为此，您需要一个允许您在分析期间区分线程和时间的工具。
perf timechart may be worth a shot, but it is not aware of OpenMP specifically. You will get the best insight by using a analysis tool that is made specifically for OpenMP. Furthermore to get the dynamics, I recommend using a tracing / timeline tool as opposed to a profiling tool that only shows you a summary. Example of such a tool would be Intel VTune or Score-P (tracing) / Vampir（可视化）。
schedule(dynamic, 64) 告诉 OpenMP 不要假设每个内循环迭代花费相同的时间，IIRC。
因此静态调度将工作分解为 u 值的范围，但是您的一个线程最终必须完成比其余线程更多的总工作（或由于某种原因需要很长时间），从而延迟了所有线程的总时间完成。
It was running on a compute server with Four AMD Opterons. The machine was mostly idle at the time. The only difference between the two is the use of scheduling. I left out the time because the time is inclusive of a pre processing step that both incur but it still differs by 10 seconds.
在那种情况下，1.4 与 1.7 CPU 的总体利用率可以用您所说的 4 / 14 秒期间的更多利用率来解释。您可以通过使程序在并行部分之前退出并对其进行分析来近似有趣部分的结果。从总计数中减去这些计数以获得非常粗略的近似值。
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 上）相对于标量收集提供可能较小的加速。
当 运行 一个不使用调度的算法和使用调度的算法时，性能差异是巨大的 - 使用调度，算法在 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%)
perf stat 不是了解多线程程序中动态调度的性能影响的正确工具。为此，您需要一个允许您在分析期间区分线程和时间的工具。
perf timechart may be worth a shot, but it is not aware of OpenMP specifically. You will get the best insight by using a analysis tool that is made specifically for OpenMP. Furthermore to get the dynamics, I recommend using a tracing / timeline tool as opposed to a profiling tool that only shows you a summary. Example of such a tool would be Intel VTune or Score-P (tracing) / Vampir（可视化）。
schedule(dynamic, 64) 告诉 OpenMP 不要假设每个内循环迭代花费相同的时间，IIRC。
因此静态调度将工作分解为 u 值的范围，但是您的一个线程最终必须完成比其余线程更多的总工作（或由于某种原因需要很长时间），从而延迟了所有线程的总时间完成。
It was running on a compute server with Four AMD Opterons. The machine was mostly idle at the time. The only difference between the two is the use of scheduling. I left out the time because the time is inclusive of a pre processing step that both incur but it still differs by 10 seconds.
在那种情况下，1.4 与 1.7 CPU 的总体利用率可以用您所说的 4 / 14 秒期间的更多利用率来解释。您可以通过使程序在并行部分之前退出并对其进行分析来近似有趣部分的结果。从总计数中减去这些计数以获得非常粗略的近似值。
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 上）相对于标量收集提供可能较小的加速。