问一个并行计算的问题

你这个显然别人也试过了，他是在有目的的调开关了。

【 在 chebyshev (......) 的大作中提到: 】
: 标 题: Re: 问一个并行计算的问题
: 发信站: BBS 未名空间站 (Thu Jul 8 14:07:02 2021, 美东)
:
: -Ofast比-O3又快很多。
: 【 在 netghost (Up to Isomorphism) 的大作中提到: 】
: : 他都上那一堆開關了，這個O3啥的他顯然試過了。
:
:
:
: --

沒有。我就直接用他的code。改了改n, repeat。
外面加了總的loop選不同的thread。
【 在 jmrf (daimao) 的大作中提到: 】
: 用O3要快一点.
: 你把编译指令写code里了吗? 只用 gcc p3.c -fopenmp -lm -O3 直接打回原形,要1.3 秒
: sum = 6992.953984, time = 0.216588 sec, np = 1
: sum = 6992.953984, time = 0.118749 sec, np = 2
: sum = 6992.953984, time = 0.104176 sec, np = 4
: sum = 6992.953984, time = 0.082472 sec, np = 8
: sum = 6992.953984, time = 0.092022 sec, np = 16
: sum = 6992.953984, time = 0.109844 sec, np = 32

不要纠结这些和讨论无关的东西。边界不会影响速度的。

【 在 chebyshev (......) 的大作中提到: 】
: loop次數不一樣。乘法和加法,sin次數不同了。
: OMP loop次數為n。
: MPI程序 loop數等於int sublength = (int)(ceil((double)(n) / (double)(np)));: np=8時，sin少算8次。這是兩個不同的程序了。

为什么不能确定是reduce的implementation造成的。
下面是我去掉reduce 以后测的时间。
这些结果当然是错误的，但运行时间是除了reduce之外的时间。

sum = 6992.953984, time = 0.413514 sec, np = 1
sum = 4097.978213, time = 0.248612 sec, np = 2
sum = 1967.810634, time = 0.152884 sec, np = 4
sum = 1121.367963, time = 0.091141 sec, np = 8
sum = 567.774710, time = 0.052051 sec, np = 16
sum = 113.105499, time = 0.027059 sec, np = 32

在我的下面的ｃｏｄｅ里有一个假的reduce function.
如果能实施一个高效的reduce　function，　我的问题就解决了。

#include
#include
#include
#include

double OMP_Allreduce_dsum0(double loc_sum, int tid, int np)
{
return loc_sum;
}

int main(int argc, char* argv[])
{

int n = 10000;
int repeat = 10000;

int np = 1;
if (argc > 1)
{
np = atoi(argv[1]);
}
omp_set_num_threads(np);

int nstart =0;
int sublength =n;

#pragma omp parallel
{
int i, j, k;
int my_rank = omp_get_thread_num();
double loc_dot = 0;
double sum = 1;

double time = -omp_get_wtime();

for (j = 0; j < repeat; j++)
{
#pragma omp for nowait
for (k = 0; k < sublength; k++)
{
double temp = sin((sum+ nstart +k +j)/(double)(n));
loc_dot += (temp * temp);
}
double dot = OMP_Allreduce_dsum0(loc_dot, my_rank, np);
sum += (dot/(double)(n));
loc_dot =0;
}
time += omp_get_wtime();
sum = OMP_Allreduce_dsum0(sum, my_rank, np);
#pragma omp single nowait
printf("sum = %f, time = %f sec, np = %dn", sum, time, np);
}

return 0;
}
【 在 netghost (Up to Isomorphism) 的大作中提到: 】
: 你始終在強調reduce，這東西只是一個high level概念，下面可以有一堆實現，並不是
: 你去掉了reduce結果變化了，就是reduce的implementation造成的。

没必要O3,关键是要向量化。

他这个代码说实话很无聊，90%的时间其实是在给数组赋值，dot product不花什么时间。
【 在 jmrf (daimao) 的大作中提到: 】
: 用O3要快一点.
: 你把编译指令写code里了吗? 只用 gcc p3.c -fopenmp -lm -O3 直接打回原形,要1.3 秒
: sum = 6992.953984, time = 0.216588 sec, np = 1
: sum = 6992.953984, time = 0.118749 sec, np = 2
: sum = 6992.953984, time = 0.104176 sec, np = 4
: sum = 6992.953984, time = 0.082472 sec, np = 8
: sum = 6992.953984, time = 0.092022 sec, np = 16
: sum = 6992.953984, time = 0.109844 sec, np = 32

你这个情况实际上还比我之前说的简单。

这么说吧，你把这一行：

double t, time = -omp_get_wtime();
移到你mpi程序的main开始（before MPI_INIT)，再run一下把结果贴上来，这样你该明白了。

【 在 llaalways (熊大) 的大作中提到: 】
: 为什么不能确定是reduce的implementation造成的。
: 下面是我去掉reduce 以后测的时间。
: 这些结果当然是错误的，但运行时间是除了reduce之外的时间。
: sum = 6992.953984, time = 0.413514 sec, np = 1
: sum = 4097.978213, time = 0.248612 sec, np = 2
: sum = 1967.810634, time = 0.152884 sec, np = 4
: sum = 1121.367963, time = 0.091141 sec, np = 8
: sum = 567.774710, time = 0.052051 sec, np = 16
: sum = 113.105499, time = 0.027059 sec, np = 32
: 在我的下面的ｃｏｄｅ里有一个假的reduce function.
: ...................

被O3坑过不敢随便. Ofast和O3 差不多
-march=native 去掉关系不大
用O3/Ofast 感觉 np=1 的时间变动加大 0.21-0.29 sec, 不如O2, 0.24 sec放心. 还
好sum一样
【 在 chebyshev (......) 的大作中提到: 】
: -Ofast比-O3又快很多。

np=8時。你的原始程序，MPI循環為sublength=10000/8=1250次。
OMP循環為10000次?

這怎麼比較呢。
【 在 llaalways (熊大) 的大作中提到: 】
: 为什么不能确定是reduce的implementation造成的。
: 下面是我去掉reduce 以后测的时间。
: 这些结果当然是错误的，但运行时间是除了reduce之外的时间。
: sum = 6992.953984, time = 0.413514 sec, np = 1
: sum = 4097.978213, time = 0.248612 sec, np = 2
: sum = 1967.810634, time = 0.152884 sec, np = 4
: sum = 1121.367963, time = 0.091141 sec, np = 8
: sum = 567.774710, time = 0.052051 sec, np = 16
: sum = 113.105499, time = 0.027059 sec, np = 32
: 在我的下面的ｃｏｄｅ里有一个假的reduce function.
: ...................

你的code版本太多，估计大家都没法follow了。
看不是不reduce的问题，比较下面两个:
1. 用OMP reduce
2. 不用OMP reduce, allocate一个数组，手动的让每个thread reduce local
variable到对应于rank的element
看看这两个时间有没有差异

【 在 llaalways (熊大) 的大作中提到: 】
: 为什么不能确定是reduce的implementation造成的。
: 下面是我去掉reduce 以后测的时间。
: 这些结果当然是错误的，但运行时间是除了reduce之外的时间。
: sum = 6992.953984, time = 0.413514 sec, np = 1
: sum = 4097.978213, time = 0.248612 sec, np = 2
: sum = 1967.810634, time = 0.152884 sec, np = 4
: sum = 1121.367963, time = 0.091141 sec, np = 8
: sum = 567.774710, time = 0.052051 sec, np = 16
: sum = 113.105499, time = 0.027059 sec, np = 32
: 在我的下面的ｃｏｄｅ里有一个假的reduce function.
: ...................

既然不是自己实现具体细节， 你试试不同的openmp reduction的实现。目前你的实现是
#pragma omp single
可以换成master, critical, atomic,。。。还有很多。

【 在 llaalways (熊大) 的大作中提到: 】
: 没找到更合适的版面讨论这个问题，就在这里问吧.
: 我发现OpenMP的reduction效率很差，做同样的两个向量的内积，MPI要比OpenMP还快。
: MPI是分布内存，需要信息交换才能完成reduction。 结果比使用共享内存的OpenMP还
: 快。
: 这说明OpenMP的reduction没有搞好。我不知道是我使用的系统的问题还是普遍问题。
: 有人有类似的经验吗？ 怎么解决？
: 我提供了一个code，然后再大家的反馈后做了修改。 现在把code也帖再这里。
: 省得大家爬楼。
: 现在的code 还是模仿dot product， 只不过 element都是compute on the fly.
: 所以code中没有大的数组，减少cache missing。
: ...................

如果只看楼主最初的code，前面不少人给出结论了：
OpenMP的timer比MPI的多了threading的overhead，所以scaling会差一些。
对于OpenMP，即便用了thread pool，每次outer loop都还是会重新wake up thread和
让thread sleep，这个overhead随着np增大会越来越明显。
而对于MPI，楼主忽略了初始化的时间，而mpi code的outer loop并没有这些overhead
，只有MPI_Allreduce的同步略微有些影响。

楼主可以试试Intel OpenMP的这个环境变量:
KMP_BLOCKTIME
设置成infinite防止thread sleep,应该可以减少每次outer loop的overhead
【 在 BacktoMars (supercalifragilisticexpiadocious) 的大作中提到: 】
: 你的code版本太多，估计大家都没法follow了。
: 看不是不reduce的问题，比较下面两个:
: 1. 用OMP reduce
: 2. 不用OMP reduce, allocate一个数组，手动的让每个thread reduce local
: variable到对应于rank的element
: 看看这两个时间有没有差异

我剛測了下。
這個link給的技術求dotproduct效果很穩定。儘管不是特別明顯。

另外就是math.h的sin極其昂貴。
sin dominate計算時間，會導致會看不出來多少提高。

"
What ATLAS did, and what I copied in the Unrolled version, is this:

dot1 += A[i] * B[i];
dot2 += A[i + 1] * B[i + 1];
dot3 += A[i + 2] * B[i + 2];
dot4 += A[i + 3] * B[i + 3];
This meant there was no longer any dependency between statements, and the
CPU’s out of order execution engine could run all four of these as soon as the data was available. In a sense, the CPU is vectorizing loops on the fly.
"

【 在 jmrf (daimao) 的大作中提到: 】
: 如果就是dot product你就应该用库，而不是自己写。里面涉及的寄存器，一级缓存，
: 二级缓存，SIMD, 都不是新手搞得定的。
: 我收回我的建议，dot product太简单了，SIMD手工优化可以比ATLAS好
: https://blog.theincredibleholk.org/blog/2012/12/10/optimizing-dot-product/

MPI是把memory当分布式处理。每个核循環1250次.
OMP８核一起循環10000次，　其中每核循环1250次.
每核工作量是一样的。

【 在 chebyshev (......) 的大作中提到: 】
: np=8時。你的原始程序，MPI循環為sublength=10000/8=1250次。
: OMP循環為10000次?
: 這怎麼比較呢。

MPI是把memory当分布式处理。每个核循環1250次.
OMP８核一起循環10000次，　其中每核循环1250次.
每核工作量是一样的。

【 在 chebyshev (......) 的大作中提到: 】
: np=8時。你的原始程序，MPI循環為sublength=10000/8=1250次。
: OMP循環為10000次?
: 這怎麼比較呢。

算是看懂了这篇文章, 认识到了为什么不该用atomichttps://coderwall.com/p/gocbhg/openmp-improve-reduction-techniques

thread array with for nowait 可以比 reduction 好点点, sum差异应该是round
error

reduction
sum = 6992.953984, time = 0.219194 sec, np = 1
sum = 6992.953984, time = 0.117103 sec, np = 2
sum = 6992.953984, time = 0.105183 sec, np = 4
sum = 6992.953984, time = 0.078228 sec, np = 8
sum = 6992.953984, time = 0.087476 sec, np = 16
sum = 6992.953984, time = 0.343639 sec, np = 32
thread array with for nowait
sum = 6992.953984, time = 0.210598 sec, np = 1
sum = 6992.459277, time = 0.113893 sec, np = 2
sum = 6992.410753, time = 0.081251 sec, np = 4
sum = 6992.276900, time = 0.064732 sec, np = 8
sum = 6992.321792, time = 0.061637 sec, np = 16
sum = 6992.545499, time = 0.083507 sec, np = 32

#include
#include
#include
#include

int main(int argc, char *argv[])
{

int n = 10000;
int repeat = 10000;

int np = 1;
if (argc > 1) {
np = atoi(argv[1]);
}
omp_set_num_threads(np);

int nstart = 0;
int sublength = n;

double sum = 1;
double lca[np];
#pragma omp parallel default(none) shared(lca,np,sum,nstart,sublength,n,
repeat)
{
double loc_dot;
int i, j, k;
int tid = omp_get_thread_num();

double time = -omp_get_wtime();
int chunk = n / np;
for (j = 0; j < repeat; j++) {
loc_dot = 0.0;
#pragma omp for schedule(static, chunk) nowait
for (k = 0; k < sublength; k++) {
double temp = sin((sum + nstart + k + j) / (double)(n));
loc_dot += (temp * temp);
}
lca[tid] = loc_dot / (double)(n);
#pragma omp single
for (k = 0; k < np; k++) {
sum += lca[k];
}
}
time += omp_get_wtime();
#pragma omp single nowait
printf("sum = %f, time = %f sec, np = %dn", sum, time, np);
}

return 0;
}

【 在 jmrf (daimao) 的大作中提到: 】
: 还是比大佬你的差好多,还要点啥?
: Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz
: gcc t2.c -march=native -ffast-math -fassociative-math -ftree-vectorize -
msse
: -msse2 -mavx2 -fopenmp -o t2.x -O2 -lm
: sum = 6992.953984, time = 0.247078 sec, np = 1
: sum = 6992.953984, time = 0.160590 sec, np = 2
: sum = 6992.953984, time = 0.085497 sec, np = 4
: sum = 6992.953984, time = 0.087919 sec, np = 8
: sum = 6992.953984, time = 0.093634 sec, np = 16
: sum = 6992.953984, time = 0.108651 sec, np = 32
: ...................

thread array 在sum之前需要保证每个thread都已经赋值了。
这样就要加一个barrier，估计比atomic还差。
【 在 jmrf (daimao) 的大作中提到: 】
: 算是看懂了这篇文章, 认识到了为什么不该用atomic
: https://coderwall.com/p/gocbhg/openmp-improve-reduction-techniques
: thread array with for nowait 可以比 reduction 好点点, sum差异应该是round
: error
: reduction
: sum = 6992.953984, time = 0.219194 sec, np = 1
: sum = 6992.953984, time = 0.117103 sec, np = 2
: sum = 6992.953984, time = 0.105183 sec, np = 4
: sum = 6992.953984, time = 0.078228 sec, np = 8
: sum = 6992.953984, time = 0.087476 sec, np = 16
: ...................

下面总时间和loop时间都给出了， 并不影响结果。
OMP
np = 1 sum = 6992.953984, loop time = 0.408236 sec, total time = 0.412634
np = 2 sum = 6992.953984, loop time = 0.269403 sec, total time = 0.273937
np = 4 sum = 6992.953984, loop time = 0.184081 sec, total time = 0.188961
np = 8 sum = 6992.953984, loop time = 0.142919 sec, total time = 0.147943
np = 16 sum = 6992.953984, loop time = 0.156257 sec, total time = 0.162349
np = 32 sum = 6992.953984, loop time = 0.180854 sec, total time = 0.188388
MPI
np = 1 sum = 6992.953984, loop time = 0.388432 sec, total time = 0.398434
np = 2 sum = 6992.953984, loop time = 0.250379 sec, total time = 0.261760
np = 4 sum = 6992.953984, loop time = 0.157185 sec, total time = 0.170362
np = 8 sum = 6992.953984, loop time = 0.101224 sec, total time = 0.117841
np = 16 sum = 6992.953984, loop time = 0.061332 sec, total time = 0.084613
np = 32 sum = 6992.953984, loop time = 0.043481 sec, total time = 0.086247

【 在 netghost (Up to Isomorphism) 的大作中提到: 】
: 你这个情况实际上还比我之前说的简单。
: 这么说吧，你把这一行：
: double t, time = -omp_get_wtime();
: 移到你mpi程序的main开始（before MPI_INIT)，再run一下把结果贴上来，这样你该明
: 白了。

【 在 llaalways (熊大) 的大作中提到: 】
: 标 题: Re: 问一个并行计算的问题
: 发信站: BBS 未名空间站 (Thu Jul 8 22:35:30 2021, 美东)
:
: 下面总时间和loop时间都给出了， 并不影响结果。
: OMP
: np = 1 sum = 6992.953984, loop time = 0.408236 sec, total time = 0.412634
: np = 2 sum = 6992.953984, loop time = 0.269403 sec, total time = 0.273937
: np = 4 sum = 6992.953984, loop time = 0.184081 sec, total time = 0.188961
: np = 8 sum = 6992.953984, loop time = 0.142919 sec, total time = 0.147943
: np = 16 sum = 6992.953984, loop time = 0.156257 sec, total time = 0.162349: np = 32 sum = 6992.953984, loop time = 0.180854 sec, total time = 0.188388: MPI
: np = 1 sum = 6992.953984, loop time = 0.388432 sec, total time = 0.398434
: np = 2 sum = 6992.953984, loop time = 0.250379 sec, total time = 0.261760
: np = 4 sum = 6992.953984, loop time = 0.157185 sec, total time = 0.170362
: np = 8 sum = 6992.953984, loop time = 0.101224 sec, total time = 0.117841
: np = 16 sum = 6992.953984, loop time = 0.061332 sec, total time = 0.084613: np = 32 sum = 6992.953984, loop time = 0.043481 sec, total time = 0.086247~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
看這裏，明白了沒？
:
:
: 【 在 netghost (Up to Isomorphism) 的大作中提到: 】
: : 你这个情况实际上还比我之前说的简单。
: : 这么说吧，你把这一行：
: : double t, time = -omp_get_wtime();
: : 移到你mpi程序的main开始（before MPI_INIT)，再run一下把结果贴上来，这样你该明
: : 白了。
:
:
:
: --
: 🥧💌llaalways

在single前加 barrier, 可以消除sum差异, 之前的确没有同步

#pragma omp barrier
#pragma omp single

thread array with for nowait and barrier before single
可以做得比reduction 好一点儿, 也可以差一点

reduction
sum = 6992.953984, time = 0.218412 sec, np = 1
sum = 6992.953984, time = 0.120420 sec, np = 2
sum = 6992.953984, time = 0.090650 sec, np = 4
sum = 6992.953984, time = 0.081235 sec, np = 8
sum = 6992.953984, time = 0.092800 sec, np = 16
sum = 6992.953984, time = 0.107621 sec, np = 32
thread array with for nowait and barrier before single
sum = 6992.953984, time = 0.208075 sec, np = 1
sum = 6992.953984, time = 0.118550 sec, np = 2
sum = 6992.953984, time = 0.078497 sec, np = 4
sum = 6992.953984, time = 0.082000 sec, np = 8
sum = 6992.953984, time = 0.089179 sec, np = 16
sum = 6992.953984, time = 0.097233 sec, np = 32

another run
reduction
sum = 6992.953984, time = 0.212445 sec, np = 1
sum = 6992.953984, time = 0.116725 sec, np = 2
sum = 6992.953984, time = 0.096100 sec, np = 4
sum = 6992.953984, time = 0.080756 sec, np = 8
sum = 6992.953984, time = 0.095057 sec, np = 16
sum = 6992.953984, time = 0.107498 sec, np = 32
thread array with for nowait and barrier before single
sum = 6992.953984, time = 0.217186 sec, np = 1
sum = 6992.953984, time = 0.118578 sec, np = 2
sum = 6992.953984, time = 0.106688 sec, np = 4
sum = 6992.953984, time = 0.079233 sec, np = 8
sum = 6992.953984, time = 0.084670 sec, np = 16
sum = 6992.953984, time = 0.146309 sec, np = 32

【 在 llaalways (熊大) 的大作中提到: 】
: thread array 在sum之前需要保证每个thread都已经赋值了。
: 这样就要加一个barrier，估计比atomic还差。

為何你的np=1比我還要慢？我這個game laptop四年前800刀買的。
timeX = 180326,sum = 6992.953984, time = 0.180324 sec, np = 1
難道說碰到了神機？

【 在 jmrf (daimao) 的大作中提到: 】
: 在single前加 barrier, 可以消除sum差异, 之前的确没有同步
: #pragma omp barrier
: #pragma omp single
: thread array with for nowait and barrier before single
: 可以做得比reduction 好一点儿, 也可以差一点
: reduction
: sum = 6992.953984, time = 0.218412 sec, np = 1
: sum = 6992.953984, time = 0.120420 sec, np = 2
: sum = 6992.953984, time = 0.090650 sec, np = 4
: sum = 6992.953984, time = 0.081235 sec, np = 8
: ...................

Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz. CPU First Seen on Charts: Q4 2014.
No avx512f, no turbo
【 在 chebyshev (......) 的大作中提到: 】
: 為何你的np=1比我還要慢？我這個game laptop四年前800刀買的。
: timeX = 180326,sum = 6992.953984, time = 0.180324 sec, np = 1
: 難道說碰到了神機？

我的是 Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
樓主花了0.4秒for np=1。也許是gcc flag沒弄對吧。
【 在 jmrf (daimao) 的大作中提到: 】
: Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz. CPU First Seen on Charts: Q4
2014.
: No avx512f, no turbo

很简单，你的timer只算了一次MPI processes初始化时间，但是算了10000次OMP的
threads wakeup/sleep时间。
如果要做fair comparison，把n改成100000000，repeat改成1
你再看看MPI和OMP的scaling
【 在 llaalways (熊大) 的大作中提到: 】
: 下面总时间和loop时间都给出了， 并不影响结果。
: OMP
: np = 1 sum = 6992.953984, loop time = 0.408236 sec, total time = 0.412634
: np = 2 sum = 6992.953984, loop time = 0.269403 sec, total time = 0.273937
: np = 4 sum = 6992.953984, loop time = 0.184081 sec, total time = 0.188961
: np = 8 sum = 6992.953984, loop time = 0.142919 sec, total time = 0.147943
: np = 16 sum = 6992.953984, loop time = 0.156257 sec, total time = 0.162349: np = 32 sum = 6992.953984, loop time = 0.180854 sec, total time = 0.188388: MPI
: np = 1 sum = 6992.953984, loop time = 0.388432 sec, total time = 0.398434
: ...................

確切來說，是OMP的thread management是黑盒，創建了多少次，怎麼wakeup都是
implementation dependent的。具體他這個情況，我倒是覺得wakeup時間不算主要的，其實就是他沒算建立線程的時間，這個在他自己覺得沒區別的測試裏面已經很清楚了：

MPI：
np = 32 sum = 6992.953984, loop time = 0.043481 sec, total time = 0.086247

這總時間裏面有一半在create線程，沒啥好叫的。

【 在 BacktoMars (supercalifragilisticexpiadocious) 的大作中提到: 】
: 很简单，你的timer只算了一次MPI processes初始化时间，但是算了10000次OMP的
: threads wakeup/sleep时间。
: 如果要做fair comparison，把n改成100000000，repeat改成1
: 你再看看MPI和OMP的scaling

change
: #pragma omp barrier
: #pragma omp single
to
#pragma omp barrier
#pragma omp master

could speed up at np>=4,
sum = 6992.953984, time = 0.231183 sec, np = 1
sum = 6992.977972, time = 0.114765 sec, np = 2
sum = 6992.913879, time = 0.069948 sec, np = 4
sum = 6992.896652, time = 0.054346 sec, np = 8
sum = 6992.866811, time = 0.044499 sec, np = 16
sum = 6992.232058, time = 0.052284 sec, np = 32

the time are closer to openmpi now.

however another barrier is necessary to make the sum right. It slow it down, but still faster than reduction at larger np.

#pragma omp barrier
#pragma omp master
for (k = 0; k < np; k++) {
sum += lca[k];
}
#pragma omp barrier

sum = 6992.953984, time = 0.213375 sec, np = 1
sum = 6992.953984, time = 0.117005 sec, np = 2
sum = 6992.953984, time = 0.093248 sec, np = 4
sum = 6992.953984, time = 0.064866 sec, np = 8
sum = 6992.953984, time = 0.070267 sec, np = 16
sum = 6992.953984, time = 0.078379 sec, np = 32

【 在 jmrf (daimao) 的大作中提到: 】
: 在single前加 barrier, 可以消除sum差异, 之前的确没有同步
: #pragma omp barrier
: #pragma omp single
: thread array with for nowait and barrier before single
: 可以做得比reduction 好一点儿, 也可以差一点
: reduction
: sum = 6992.953984, time = 0.218412 sec, np = 1
: sum = 6992.953984, time = 0.120420 sec, np = 2
: sum = 6992.953984, time = 0.090650 sec, np = 4
: sum = 6992.953984, time = 0.081235 sec, np = 8
: ...................

沒什麼大的意義，樓主一定要把算法設計成每隔CPU喂不飽還順序執行這件事情是無解
的。

【 在 jmrf (daimao) 的大作中提到: 】
: change
: to
: #pragma omp barrier
: #pragma omp master
: could speed up at np>=4,
: sum = 6992.953984, time = 0.231183 sec, np = 1
: sum = 6992.977972, time = 0.114765 sec, np = 2
: sum = 6992.913879, time = 0.069948 sec, np = 4
: sum = 6992.896652, time = 0.054346 sec, np = 8
: sum = 6992.866811, time = 0.044499 sec, np = 16
: ...................

Moore' law早就失效了。都是在拼core的數目。server CPU的優勢在於core多，cache
多，帶寬大。問題是這些東西都不是像之前升級cpu直接就變快的，core再多不會用也
沒效果。

單core性能，你的比他強，而且他還沒有turbo，這樣等於是3.5Ghz在和2.4Ghz的比。
這還不算樓主這個程序任務一個就一點點，server cpu的那些個cache也沒啥用。

【 在 chebyshev (......) 的大作中提到: 】
: 為何你的np=1比我還要慢？我這個game laptop四年前800刀買的。
: timeX = 180326,sum = 6992.953984, time = 0.180324 sec, np = 1
: 難道說碰到了神機？

我在自己玩,顺便学点东西 ^_^
1. for loop 要能加nowiat
np 太多的情况下
2. atomic 靠不住
3. single 不如 barrier/ master/ barrier 可靠

4. 怎么把openmp写成openmpi一样分块明确. 不用 omp for; 时间跟 for nowait 差不多.
多谢指点.
【 在 netghost (Up to Isomorphism) 的大作中提到: 】
: 沒什麼大的意義，樓主一定要把算法設計成每隔CPU喂不飽還順序執行這件事情是無解
: 的。

所以gpu那么火是必然的。现在只要run session比较长，用Python写，jit优化一下效
率还是很高的。

【在 netghost(Up to Isomorphism)的大作中提到：】
：Moore' law早就失效了。都是在拼core的數目。server CPU的優勢在於core多，cache
：多，帶寬大。問題是這些東西都不是像之前升級cpu直接就變快的，core再多不會用也

taichi 看写法感觉很类似. 是不是也是jit差不多大的技术,只是更关注于图像? https://github.com/taichi-dev/taichi
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: 所以gpu那么火是必然的。现在只要run session比较长，用Python写，jit优化一下效
: 率还是很高的。
: ：Moore' law早就失效了。都是在拼core的數目。server CPU的優勢在於core多，
: cache
: ：多，帶寬大。問題是這些東西都不是像之前升級cpu直接就變快的，core再多不會
用也

GPU火是intel自己被自己限制住了。其實nvidia能塞那麼多core是因爲每個shader非常簡單。但是Intel 這種CPU賣太好的只能往SSE這個方向搞。

【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: 所以gpu那么火是必然的。现在只要run session比较长，用Python写，jit优化一下效
: 率还是很高的。
: 【在 netghost(Up to Isomorphism)的大作中提到：】
: ：Moore' law早就失效了。都是在拼core的數目。server CPU的優勢在於core多，
: cache
: ：多，帶寬大。問題是這些東西都不是像之前升級cpu直接就變快的，core再多不會
用也

openmp這種東西只是接口，實現上面很難控制。玩玩和一般應用還是可以，serious的
計算我覺得沒啥優勢。

MPI本來就是用來做科學計算的，一來就fork一堆這個對general的應用不現實。所以
openmp不走那個路線也可以理解。

【 在 jmrf (daimao) 的大作中提到: 】
: 我在自己玩,顺便学点东西 ^_^
: 1. for loop 要能加nowiat
: np 太多的情况下
: 2. atomic 靠不住
: 3. single 不如 barrier/ master/ barrier 可靠
: 4. 怎么把openmp写成openmpi一样分块明确. 不用 omp for; 时间跟 for nowait 差不
: 多.
: 多谢指点.

多谢各位回复。 我找到目前最佳reduce了。


OMP performance：
np = 1 sum = 6992.953984, loop time = 0.246376 sec, total time = 0.250978
np = 2 sum = 6992.953984, loop time = 0.160334 sec, total time = 0.164939
np = 4 sum = 6992.953984, loop time = 0.105096 sec, total time = 0.110154
np = 8 sum = 6992.953984, loop time = 0.074775 sec, total time = 0.080252
np = 16 sum = 6992.953984, loop time = 0.049352 sec, total time = 0.057083
np = 32 sum = 6992.953984, loop time = 0.101747 sec, total time = 0.109425

我的最佳redcution 实施
#include
#include
#include
#include

double darr[2][32];
int nreduce=0;
#pragma omp threadprivate(nreduce)

double OMP_Allreduce_dsum(double loc_dot,int tid,int np)
{
darr[nreduce][tid]=loc_dot;
#pragma omp barrier
double dsum =0;
int i;
for (i=0; i {
dsum += darr[nreduce][i];
}
nreduce=1-nreduce;
return dsum;
}

int main(int argc, char* argv[])
{

int np = 1;
if (argc > 1)
{
np = atoi(argv[1]);
}
omp_set_num_threads(np);
double ttime = -omp_get_wtime();

int n = 10000;
int repeat = 10000;

int nstart =0;
int sublength =n;

#pragma omp parallel
{
int i, j, k;
int tid = omp_get_thread_num();

double sum = 1;
double time = -omp_get_wtime();

for (j = 0; j < repeat; j++)
{
double loc_dot = 0;
#pragma omp for nowait
for (k = 0; k < sublength; k++)
{
double temp = sin((sum+ nstart +k +j)/(double)(n));
loc_dot += (temp * temp);
}
double dot =OMP_Allreduce_dsum(loc_dot,tid,np);
sum +=(dot/(double)(n));
}
time += omp_get_wtime();
#pragma omp single
ttime += omp_get_wtime();
#pragma omp single nowait
printf("np = %d sum = %f, loop time = %f sec, total time = %f n", np, sum, time, ttime);
}

return 0;
}

在我的機器上比你原來的代碼慢啊。

這個新代碼在我機器上，最快的仍然是np=4.但是要0.06秒。

【 在 llaalways (熊大) 的大作中提到: 】
: 多谢各位回复。 我找到目前最佳reduce了。
:
: OMP performance：
: np = 1 sum = 6992.953984, loop time = 0.246376 sec, total time = 0.250978
: np = 2 sum = 6992.953984, loop time = 0.160334 sec, total time = 0.164939
: np = 4 sum = 6992.953984, loop time = 0.105096 sec, total time = 0.110154
: np = 8 sum = 6992.953984, loop time = 0.074775 sec, total time = 0.080252
: np = 16 sum = 6992.953984, loop time = 0.049352 sec, total time = 0.057083: np = 32 sum = 6992.953984, loop time = 0.101747 sec, total time = 0.109425: 我的最佳redcution 实施
: ...................

在俺这儿也是比老代码慢
这个新代码就是用了double buffer手动reduce，俺是看不出来有啥优势。
还是楼主改了编译选项？

PS, 你的机器是4核，所以np=4最快也是预料之中
【 在 chebyshev (......) 的大作中提到: 】
: 在我的機器上比你原來的代碼慢啊。
: 這個新代碼在我機器上，最快的仍然是np=4.但是要0.06秒。

他這個程序主要時間其實都在1萬次sin計算。別的時間極小。
mpi之sin計算會不會有trick？

【 在 BacktoMars (supercalifragilisticexpiadocious) 的大作中提到: 】
: 在俺这儿也是比老代码慢
: 这个新代码就是用了double buffer手动reduce，俺是看不出来有啥优势。
: 还是楼主改了编译选项？
: PS, 你的机器是4核，所以np=4最快也是预料之中

每次reduce由原来的2次sync变成1次。
原来在omp for reduction 结束是要sync一次（implicit barrier）
在omp single 结束是要sync一次（implicit barrier）
有人建议用omp master, 结束后加一个barrier， 效果基本是一样的。

新的code，只在所有thread 给shared数组darr赋值后有一个barrier，
其他都用重复计算代替barrier。
这样没有omp master 或 omp single.
所有线程create以后就不休息，一直active。

我的compiling flags是这样的
icc -O3 -qopenmp -march=native -ffast-math reduction_mpi.c -o reduction_mpi -lm


【 在 BacktoMars (supercalifragilisticexpiadocious) 的大作中提到: 】
: 在俺这儿也是比老代码慢
: 这个新代码就是用了double buffer手动reduce，俺是看不出来有啥优势。
: 还是楼主改了编译选项？
: PS, 你的机器是4核，所以np=4最快也是预料之中

np=4基本上已經最優了。我所需時間為0.051。
np=1時,我把n設成2500。所需時間為0.047。

單線程算2500個sin需要時間0.047。
1萬個sin，4 core，最佳時間顯然也在此附近。

你總歸要算1萬個sin。分到四個核心。除此而外，別的優化都是扯。
因為sin極其昂貴。其他的乘法加法相比之下什麼也不是。

（所以我非常不理解他那個mpi為何好那麼多。
我機器上mpi版本亂了，rank總是不變。沒法測。）
【 在 BacktoMars (supercalifragilisticexpiadocious) 的大作中提到: 】
: 在俺这儿也是比老代码慢
: 这个新代码就是用了double buffer手动reduce，俺是看不出来有啥优势。
: 还是楼主改了编译选项？
: PS, 你的机器是4核，所以np=4最快也是预料之中

我覺得沒差別的。
1萬次sin dominate了所有的東西。相比於這一萬次sin之計算。
其他的東西略等於無。所以計算量就在於如何分配這1萬次sin到不同的core。
沒有別的任務時，平均分配為最佳。

我試過了改一點程序，變成只需要計算五千次sin。
仍然是1萬個loop。結果基本上就是減40%的時間。
【 在 llaalways (熊大) 的大作中提到: 】
: 每次reduce由原来的2次sync变成1次。
: 原来在omp for reduction 结束是要sync一次（implicit barrier）
: 在omp single 结束是要sync一次（implicit barrier）
: 有人建议用omp master, 结束后加一个barrier， 效果基本是一样的。
: 新的code，只在所有thread 给shared数组darr赋值后有一个barrier，
: 其他都用重复计算代替barrier。
: 这样没有omp master 或 omp single.
: 所有线程create以后就不休息，一直active。
: 我的compiling flags是这样的
: icc -O3 -qopenmp -march=native -ffast-math reduction_mpi.c -o reduction_
mpi
: ...................

用轮换数组来换一个barrier的主意不错. 不过也说明np大了以后,求和比求dot
product 还慢.
不过我还是很不喜欢加法那一部分,要是np=1024,4096怎么办?但是要合作求和,必须加
法都同步,好像不现实;感觉起码需要硬件支持.
不知道GPU是怎么处理的?有没有可能block内步合作一下,然后共享.
【 在 llaalways (熊大) 的大作中提到: 】
: 多谢各位回复。 我找到目前最佳reduce了。
:
: OMP performance：
: np = 1 sum = 6992.953984, loop time = 0.246376 sec, total time = 0.250978
: np = 2 sum = 6992.953984, loop time = 0.160334 sec, total time = 0.164939
: np = 4 sum = 6992.953984, loop time = 0.105096 sec, total time = 0.110154
: np = 8 sum = 6992.953984, loop time = 0.074775 sec, total time = 0.080252
: np = 16 sum = 6992.953984, loop time = 0.049352 sec, total time = 0.057083: np = 32 sum = 6992.953984, loop time = 0.101747 sec, total time = 0.109425: 我的最佳redcution 实施
: ...................

你们试过omp simd吗？
我用其换掉reduction。没什么大区别。
还是np=4最快。0.05几秒。

【 在 jmrf(daimao) 的大作中提到: 】

: 用轮换数组来换一个barrier的主意不错. 不过也说明np大了以后,求和比求dot
: product 还慢.

: 不过我还是很不喜欢加法那一部分,要是np=1024,4096怎么办?但是要合作求和,
必须加

: 法都同步,好像不现实;感觉起码需要硬件支持.

: 不知道GPU是怎么处理的?有没有可能block内步合作一下,然后共享.

我正在写一个log(np)的code, 完全不需要barrier, 也不要隐式barrier.
希望能有更好的performance.

【 在 jmrf (daimao) 的大作中提到: 】
: 用轮换数组来换一个barrier的主意不错. 不过也说明np大了以后,求和比求dot
: product 还慢.
: 不过我还是很不喜欢加法那一部分,要是np=1024,4096怎么办?但是要合作求和,必须加
: 法都同步,好像不现实;感觉起码需要硬件支持.
: 不知道GPU是怎么处理的?有没有可能block内步合作一下,然后共享.
: 【 在 llaalways (熊大) 的大作中提到: 】
: : 多谢各位回复。 我找到目前最佳reduce了。
: :
: : OMP performance：
: : np = 1 sum = 6992.953984, loop time = 0.246376 sec, total time = 0.
250978
: : np = 2 sum = 6992.953984, loop time = 0.160334 sec, total time = 0.
164939
: : np = 4 sum = 6992.953984, loop time = 0.105096 sec, total time = 0.
110154
: : np = 8 sum = 6992.953984, loop time = 0.074775 sec, total time = 0.
080252
: : np = 16 sum = 6992.953984, loop time = 0.049352 sec, total time = 0.
057083
: : np = 32 sum = 6992.953984, loop time = 0.101747 sec, total time = 0.
109425
: : 我的最佳redcution 实施
: : ...................

2005年左右我做了一个矩阵乘法的项目，大概是最多十多万列乘几千行的矩阵自乘 T * T',得到方阵。大概要算几十分钟到几个小时。我用了多线程。在TACC上96个芯片大概加速48倍以上。其中就用了循环内部手动展开8个乘法的方法可以超标量吧。也遇到过
O3结果不对的问题。

你这个循环最后不到一秒结束，看不出哪里是瓶颈。但是到我那个数量级，又有cache
大小的限制了。

【 在 llaalways (熊大) 的大作中提到: 】
: 没找到更合适的版面讨论这个问题，就在这里问吧.
: 我发现OpenMP的reduction效率很差，做同样的两个向量的内积，MPI要比OpenMP还快。
: MPI是分布内存，需要信息交换才能完成reduction。 结果比使用共享内存的OpenMP还
: 快。
: 这说明OpenMP的reduction没有搞好。我不知道是我使用的系统的问题还是普遍问题。
: 有人有类似的经验吗？ 怎么解决？
: 我提供了一个code，然后再大家的反馈后做了修改。 现在把code也帖再这里。
: 省得大家爬楼。
: 现在的code 还是模仿dot product， 只不过 element都是compute on the fly.
: 所以code中没有大的数组，减少cache missing。
: ...................

“循环内部手动展开8个乘法”
這個可否展開說說？

【 在 bihai (学得不好) 的大作中提到: 】
: 2005年左右我做了一个矩阵乘法的项目，大概是最多十多万列乘几千行的矩阵自乘 T *
: T',得到方阵。大概要算几十分钟到几个小时。我用了多线程。在TACC上96个芯片大概
: 加速48倍以上。其中就用了循环内部手动展开8个乘法的方法可以超标量吧。也遇到过
: O3结果不对的问题。
: 你这个循环最后不到一秒结束，看不出哪里是瓶颈。但是到我那个数量级，又有
cache
: 大小的限制了。

就是循环内部进行8个乘法，而不是1个，那么循环变量要每次加8。这样做，循环次数
可以减少，那么循环变量增加且比较那个指令相对于加法就少了。这个技巧前面几个帖子说过了。

【 在 guvest (我爱你老婆Anna) 的大作中提到: 】
: “循环内部手动展开8个乘法”
: 這個可否展開說說？
: *
: cache

就是循环内部进行8个乘法，而不是1个，那么循环变量要每次加8。这样做，循环次数
可以减少，那么循环变量增加且比较那个指令相对于加法就少了。这个技巧前面几个帖子说过了。

【 在 guvest (我爱你老婆Anna) 的大作中提到: 】
: “循环内部手动展开8个乘法”
: 這個可否展開說說？
: *
: cache

哦。循環變量一次加8這個辦法我也試了。
確實有一致的提高。
【 在 bihai (学得不好) 的大作中提到: 】
: 就是循环内部进行8个乘法，而不是1个，那么循环变量要每次加8。这样做，循环次数
: 可以减少，那么循环变量增加且比较那个指令相对于加法就少了。这个技巧前面几个帖
: 子说过了。

已经实施了这个tree-base reduce，结果稍好一点，但还是不理想。
写code并调试，搞了一整天。
np = 1 nt = 1 sum = 6992.953984, loop time = 0.246602 sec, total time = 0.
261854
np = 1 nt = 2 sum = 6992.953984, loop time = 0.150202 sec, total time = 0.
165216
np = 1 nt = 4 sum = 6992.953984, loop time = 0.101883 sec, total time = 0.
116406
np = 1 nt = 8 sum = 6992.953984, loop time = 0.070848 sec, total time = 0.
085032
np = 1 nt = 16 sum = 6992.953984, loop time = 0.053922 sec, total time = 0.
070401
np = 1 nt = 32 sum = 6992.953984, loop time = 0.048791 sec, total time = 0.
104547

【 在 llaalways (熊大) 的大作中提到: 】
: 我正在写一个log(np)的code, 完全不需要barrier, 也不要隐式barrier.
: 希望能有更好的performance.
: 250978
: 164939
: 110154
: 080252
: 057083
: 109425

我覺得你的機器理論最快速度=單線程時間/核心數×調度損耗係數。
核心越多，調度損耗係數越大。我猜用別的問題可以測量出來調度損耗係數。
0.24是單線程之結果。我的4核心laptop此係數為4/3.2。

問題規模大，則越接近:
單線程時間/核心數×調度損耗係數

【 在 llaalways (熊大) 的大作中提到: 】
: 已经实施了这个tree-base reduce，结果稍好一点，但还是不理想。
: 写code并调试，搞了一整天。
: np = 1 nt = 1 sum = 6992.953984, loop time = 0.246602 sec, total time = 0.: 261854
: np = 1 nt = 2 sum = 6992.953984, loop time = 0.150202 sec, total time = 0.: 165216
: np = 1 nt = 4 sum = 6992.953984, loop time = 0.101883 sec, total time = 0.: 116406
: np = 1 nt = 8 sum = 6992.953984, loop time = 0.070848 sec, total time = 0.: 085032
: ...................

timeX = 24748,sum = 4663.721598, time = 0.024740 sec, np = 1
timeX = 17010,sum = 4663.721598, time = 0.016904 sec, np = 2
timeX = 14825,sum = 4663.721598, time = 0.013061 sec, np = 4
timeX = 206982,sum = 4663.721598, time = 0.205362 sec, np = 8
timeX = 658506,sum = 4663.721598, time = 0.656862 sec, np = 16
timeX = 2003551,sum = 4663.721598, time = 2.003309 sec, np = 32
timeX = 5061292,sum = 4663.721598, time = 5.060614 sec, np = 64

另外你看下n=1000，而不是一萬時，我機器的結果。比率只有1.8.
明顯4核心之提高遠小於n=10000的情況。
多線程最好的情況，其比數遠遠不到3.11。（此為n=1萬的比數。）

【 在 guvest (我爱你老婆Anna) 的大作中提到: 】
: 我覺得你的機器理論最快速度=單線程時間/核心數×調度損耗係數。
: 核心越多，調度損耗係數越大。我猜用別的問題可以測量出來調度損耗係數。
: 0.24是單線程之結果。我的4核心laptop此係數為4/3.2。
: 問題規模大，則越接近:
: 單線程時間/核心數×調度損耗係數

n=100,R=1.14。多核對小任務幾乎沒有提高。
n=10萬時，比數為3.51
n=百萬，比數為3.52

以100，1000，1萬，十萬，百萬的比數而言。規律似乎是明顯的。
【 在 guvest (我爱你老婆Anna) 的大作中提到: 】
: timeX = 24748,sum = 4663.721598, time = 0.024740 sec, np = 1
: timeX = 17010,sum = 4663.721598, time = 0.016904 sec, np = 2
: timeX = 14825,sum = 4663.721598, time = 0.013061 sec, np = 4
: timeX = 206982,sum = 4663.721598, time = 0.205362 sec, np = 8
: timeX = 658506,sum = 4663.721598, time = 0.656862 sec, np = 16
: timeX = 2003551,sum = 4663.721598, time = 2.003309 sec, np = 32
: timeX = 5061292,sum = 4663.721598, time = 5.060614 sec, np = 64
: 另外你看下n=1000，而不是一萬時，我機器的結果。
: 明顯4核心之提高遠小於n=10000的情況。
: 多線程最好的情況，其比數遠遠不到3.11。（此為n=1萬的比數。）