作者noahleft (NoahLeft)
看板C_and_CPP
标题[讨论] 平行化计算质数数量
时间Sun Jul 4 11:02:42 2021
*感谢版友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的成本太高
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.166.216.124 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1625367765.A.505.html
1F：→ EricTCartman: 版本一的做法怪怪的，一般都是用划表的方式做 07/04 11:41
3F：→ EricTCartman: 版本1动态记忆体配置太花时间, 容器也不方便平行化 07/04 11:42
4F：→ EricTCartman: 你用筛法就能直接平行滤掉了 07/04 11:43
5F：→ noahleft: 感谢 问题看来是一开始提的方法不适合平行化 07/04 11:54
※ 编辑: noahleft (118.166.216.124 台湾), 07/04/2021 15:21:20
6F：→ stucode: 你的筛法平行版本有点问题，vector<bool> 的特性可能会 07/05 19:43
7F：→ stucode: 导致 data race 07/05 19:43
感谢提出data race 没有留意到会有这个问题 :(
※ 编辑: noahleft (36.226.155.109 台湾), 07/10/2021 20:51:58