OpenMP 基准并行计算
OpenMP benchmarking parallel computations
我正在尝试对 f(x) 的计算进行基准测试，同时在每次迭代中改变线程数。
f(x) = c * ln(x) * cos(x)
n=10000000
for (int pp = 2; pp<17; pp++)
{
p = pp;
int chunk = n/p; //acts like floor
omp_set_num_threads(p);
double start_parallel = omp_get_wtime();
//start parallel
#pragma omp parallel shared(tt,chunk) private (i)
{
//printf("thread number %d\n",omp_get_thread_num());
#pragma omp for schedule(dynamic,chunk) nowait
for(i=0; i<n; i++)
{
//tt[i] = f(tt[i]);
tt[i] = f1(tt[i]); //the speed up is much higher with f1 since log and cos
//computations are polynomial; see function.
}
} //end parallel
double end_parallel = omp_get_wtime();
double cpu_time_used_parallel = (double) (end_parallel - start_parallel);
printf("parallel: for n=%d, p=%d, time taken=%f, speedup=%f\n",
n,p,cpu_time_used_parallel,
cpu_time_used_seq/cpu_time_used_parallel);
}
结果：
Started varying threads:
parallel: for n=10000000, p=2, time taken=0.153774, speedup=3.503831
parallel: for n=10000000, p=3, time taken=0.064447, speedup=8.360370
parallel: for n=10000000, p=4, time taken=0.044694, speedup=12.055239
parallel: for n=10000000, p=5, time taken=0.048700, speedup=11.063550
parallel: for n=10000000, p=6, time taken=0.039009, speedup=13.811989
parallel: for n=10000000, p=7, time taken=0.041735, speedup=12.910017
parallel: for n=10000000, p=8, time taken=0.041268, speedup=13.055919
parallel: for n=10000000, p=9, time taken=0.039032, speedup=13.804157
parallel: for n=10000000, p=10, time taken=0.038970, speedup=13.825767
parallel: for n=10000000, p=11, time taken=0.039843, speedup=13.522884
parallel: for n=10000000, p=12, time taken=0.041356, speedup=13.028237
parallel: for n=10000000, p=13, time taken=0.041039, speedup=13.128763
parallel: for n=10000000, p=14, time taken=0.047433, speedup=11.359218
parallel: for n=10000000, p=15, time taken=0.048430, speedup=11.125202
parallel: for n=10000000, p=16, time taken=0.051950, speedup=10.371477
注意：这里的加速是根据顺序算法计算的（线程数=1）
加速似乎并没有真正受到 p（线程数）变化的影响。
我这样做对吗，或者原因来自于线程数的非有效增加（即理论上改变p不会严重影响O(myprogram) ) ?
由于 omp pragma 中的 nowait 子句，您的结果不正确。通常，一个 parallel 的结束代表一个同步点，但是没有等待，第一个完成的线程不会等待其他线程，所以你将执行 double end_parallel = omp_get_wtime(); 而其他线程仍在做一些事情计算。如果你去掉nowait，你应该观察到完全不同的结果。
Q : Am I doing this right...?
A : No, sorry, you do not happen to do this right. Let's analyse the reasons and let's sketch some hints for HPC-grade performance benchmarking together :
好吧，您已经知道最初的基准设计不是精心设计的。附加成本的影响，在当代 criticism of the original, overhead-naive Amdahl-law has more details on this 和时序细节中得到了很好的证明，因为实例化成本越来越小，相对于其他 类 处理和 I/O-related 成本，因为如下所示。
原因？
与 "computation" 部分相比，该代码具有巨大的附加开销成本。这是对其他合法语法构造器（这里是 OpenMP，其他地方是 map-reduce，其他情况下是列表理解，其他地方是其他一些语法加糖技巧）的技术能力使用有缺陷的最有力标志）
最终性能是一种平衡的艺术（正确 - 平衡成本和收益 - 任何一种不平衡都意味着失去性能优势）。
成本？这里？查看结果的情况::
第二个罪过是忽略 "behind-scene" [TIME] 域对 [SPACE] 域缩放的惩罚。 n 越大，分配的内存就越大，（可怕的）高速缓存行效率低下带来的惩罚就越多，所有这些都具有零保护，不会掉入地狱般的内存交换：
n=1E3 1E4 1E5 1E6 1E7 1E8 1E9 :
______________________________________________________________________________:_____
1.000 1.000 1.000 1.000 1.000 1.000 1.000 : p= 1
0.930 1.403 0.902 1.536 1.492 1.517 0.356 : p= 2
1.075 2.319 2.207 1.937 2.001 1.991 1.489++ : p= 3
1.497+++++ 2.636++++ 1.563 1.657 2.571 2.144 0.687 : p= 4
1.226++ 2.548+++ 0.957 2.025 2.357 1.731 1.569++++ : p= 5
1.255+++ 1.805 2.704 2.020 2.348 1.502 0.989 : p= 6
0.957 0.581 3.104++ 2.124 2.486 2.002 0.838 : p= 7
1.151 1.376 2.449 2.154 2.573 1.536 0.776 : p= 8
1.135 1.685 2.388 2.506+++ 2.852++++ 2.311 1.676+++++ : p= 9
1.285++++ 2.492++ 2.497 2.568++++ 2.647+ 2.467 1.413+ : p=10
1.177 2.314+ 2.709+ 2.174 2.688+++ 2.634++++ 0.606 : p=11
1.216+ 2.293 2.442 2.287 2.550 2.551++ 1.256 : p=12
1.034 2.148 1.802 2.361++ 2.635 2.554+++ 1.181 : p=13
0.999 0.440 3.672+++++ 2.774+++++ 2.927+++++ 2.839+++++ 1.496+++ : p=14
1.091 1.217 3.285++++ 2.284 2.525 2.356 1.005 : p=15
0.937 2.850+++++ 3.185+++ 2.334+ 2.655++ 2.508+ 0.889 : p=16
提高性能的技巧？
如果基准计算，基准计算和避免MEM-I/O
如果进行基准测试，请始终检查整个景观，感觉（更好学习如何avoid/evict 任何此类偏离测量结果）缓存中 副作用
始终避免任何形式的共享（可以避免 - 将处理映射到 tt[]，但覆盖 "whole" tt[]，缓存行一致块，以避免错误共享和 "at least" 重新使用已获取数据块中的任何数据您已经支付了 MEM-I/O 获取的费用（如果基于矢量的 LOAD/STORE 确实是必须的 - 见上文）
允许并积极利用 FMA4/SIMD/AVX512 可用的任何 HPC 矢量化技巧
我正在尝试对 f(x) 的计算进行基准测试，同时在每次迭代中改变线程数。
f(x) = c * ln(x) * cos(x)
n=10000000
for (int pp = 2; pp<17; pp++)
{
p = pp;
int chunk = n/p; //acts like floor
omp_set_num_threads(p);
double start_parallel = omp_get_wtime();
//start parallel
#pragma omp parallel shared(tt,chunk) private (i)
{
//printf("thread number %d\n",omp_get_thread_num());
#pragma omp for schedule(dynamic,chunk) nowait
for(i=0; i<n; i++)
{
//tt[i] = f(tt[i]);
tt[i] = f1(tt[i]); //the speed up is much higher with f1 since log and cos
//computations are polynomial; see function.
}
} //end parallel
double end_parallel = omp_get_wtime();
double cpu_time_used_parallel = (double) (end_parallel - start_parallel);
printf("parallel: for n=%d, p=%d, time taken=%f, speedup=%f\n",
n,p,cpu_time_used_parallel,
cpu_time_used_seq/cpu_time_used_parallel);
}
结果：
Started varying threads:
parallel: for n=10000000, p=2, time taken=0.153774, speedup=3.503831
parallel: for n=10000000, p=3, time taken=0.064447, speedup=8.360370
parallel: for n=10000000, p=4, time taken=0.044694, speedup=12.055239
parallel: for n=10000000, p=5, time taken=0.048700, speedup=11.063550
parallel: for n=10000000, p=6, time taken=0.039009, speedup=13.811989
parallel: for n=10000000, p=7, time taken=0.041735, speedup=12.910017
parallel: for n=10000000, p=8, time taken=0.041268, speedup=13.055919
parallel: for n=10000000, p=9, time taken=0.039032, speedup=13.804157
parallel: for n=10000000, p=10, time taken=0.038970, speedup=13.825767
parallel: for n=10000000, p=11, time taken=0.039843, speedup=13.522884
parallel: for n=10000000, p=12, time taken=0.041356, speedup=13.028237
parallel: for n=10000000, p=13, time taken=0.041039, speedup=13.128763
parallel: for n=10000000, p=14, time taken=0.047433, speedup=11.359218
parallel: for n=10000000, p=15, time taken=0.048430, speedup=11.125202
parallel: for n=10000000, p=16, time taken=0.051950, speedup=10.371477
注意：这里的加速是根据顺序算法计算的（线程数=1）
加速似乎并没有真正受到 p（线程数）变化的影响。
我这样做对吗，或者原因来自于线程数的非有效增加（即理论上改变p不会严重影响O(myprogram) ) ?
由于 omp pragma 中的 nowait 子句，您的结果不正确。通常，一个 parallel 的结束代表一个同步点，但是没有等待，第一个完成的线程不会等待其他线程，所以你将执行 double end_parallel = omp_get_wtime(); 而其他线程仍在做一些事情计算。如果你去掉nowait，你应该观察到完全不同的结果。
Q : Am I doing this right...?
A : No, sorry, you do not happen to do this right. Let's analyse the reasons and let's sketch some hints for HPC-grade performance benchmarking together :
好吧，您已经知道最初的基准设计不是精心设计的。附加成本的影响，在当代 criticism of the original, overhead-naive Amdahl-law has more details on this 和时序细节中得到了很好的证明，因为实例化成本越来越小，相对于其他 类 处理和 I/O-related 成本，因为如下所示。
原因？
与 "computation" 部分相比，该代码具有巨大的附加开销成本。这是对其他合法语法构造器（这里是 OpenMP，其他地方是 map-reduce，其他情况下是列表理解，其他地方是其他一些语法加糖技巧）的技术能力使用有缺陷的最有力标志）
最终性能是一种平衡的艺术（正确 - 平衡成本和收益 - 任何一种不平衡都意味着失去性能优势）。
成本？这里？查看结果的情况::
第二个罪过是忽略 "behind-scene" [TIME] 域对 [SPACE] 域缩放的惩罚。 n 越大，分配的内存就越大，（可怕的）高速缓存行效率低下带来的惩罚就越多，所有这些都具有零保护，不会掉入地狱般的内存交换：
n=1E3 1E4 1E5 1E6 1E7 1E8 1E9 :
______________________________________________________________________________:_____
1.000 1.000 1.000 1.000 1.000 1.000 1.000 : p= 1
0.930 1.403 0.902 1.536 1.492 1.517 0.356 : p= 2
1.075 2.319 2.207 1.937 2.001 1.991 1.489++ : p= 3
1.497+++++ 2.636++++ 1.563 1.657 2.571 2.144 0.687 : p= 4
1.226++ 2.548+++ 0.957 2.025 2.357 1.731 1.569++++ : p= 5
1.255+++ 1.805 2.704 2.020 2.348 1.502 0.989 : p= 6
0.957 0.581 3.104++ 2.124 2.486 2.002 0.838 : p= 7
1.151 1.376 2.449 2.154 2.573 1.536 0.776 : p= 8
1.135 1.685 2.388 2.506+++ 2.852++++ 2.311 1.676+++++ : p= 9
1.285++++ 2.492++ 2.497 2.568++++ 2.647+ 2.467 1.413+ : p=10
1.177 2.314+ 2.709+ 2.174 2.688+++ 2.634++++ 0.606 : p=11
1.216+ 2.293 2.442 2.287 2.550 2.551++ 1.256 : p=12
1.034 2.148 1.802 2.361++ 2.635 2.554+++ 1.181 : p=13
0.999 0.440 3.672+++++ 2.774+++++ 2.927+++++ 2.839+++++ 1.496+++ : p=14
1.091 1.217 3.285++++ 2.284 2.525 2.356 1.005 : p=15
0.937 2.850+++++ 3.185+++ 2.334+ 2.655++ 2.508+ 0.889 : p=16
提高性能的技巧？
如果基准计算，基准计算和避免MEM-I/O
如果进行基准测试，请始终检查整个景观，感觉（更好学习如何avoid/evict 任何此类偏离测量结果）缓存中 副作用
始终避免任何形式的共享（可以避免 - 将处理映射到
tt[]，但覆盖 "whole"tt[]，缓存行一致块，以避免错误共享和 "at least" 重新使用已获取数据块中的任何数据您已经支付了 MEM-I/O 获取的费用（如果基于矢量的 LOAD/STORE 确实是必须的 - 见上文）允许并积极利用 FMA4/SIMD/AVX512 可用的任何 HPC 矢量化技巧