楼主:
noahleft (NoahLeft)
2021-07-04 11:02:42*感谢版友EricTCartman和Schottky的建议 采用Sieve法来取质数*
*感谢版友stucode的建议 避免data race*
*更新Sieve法的benchmark*
问题：计算小于N的质数数量.
接续问题：改成平行化. 且注意load-balance.
版本1(非平行化): 所有质数不会被小于自己的质数整除
用一个vector存所有小于N的质数,
M=[2..N], 只要确认所有小于M的质数无法整除就好,
最后回传总数
版本2(非平行化): 所有质数不会被小于自己的整数整除
M=[2..N], 只确认所有小于M/2的数字无法整除
版本3(平行化): 将版本2用pthread实现
版本4(非平行化): Sieve法:质数的合数必不是质数
版本5(非平行化): 同上 只是将目标函式抽取出来
版本6(平行化): 将版本5以lock-free方式平行化且改为任何数的合数必不是质数
感谢版友stucode提到data race
为了避免data race, 每个thread不会取用到其他thread的资料
可编译版本可以看下面这个gist
https://gist.github.com/noahleft/27c52232932db6c77e78d78e09d2420d
Benchmark: N=1M
版本1: 22.82 sec
版本2:128.62 sec
版本3: 72.73 sec
Benchmark: N=100M
版本4: 9.33 sec
版本5: 9.52 sec
版本6: 13.24 sec
值得注意的是我有试着用mux方式去实作"选择下一个质数",
然而对这个题目而言,使用lock的成本太高