[討論] 平行化計算質數數量

[noahleft (NoahLeft)]

*感謝版友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://www.ptt.cc/bbs/C_and_CPP/M.1625367765.A.505.html
→ EricTCartman: 版本一的做法怪怪的，一般都是用劃表的方式做
推 Schottky: https://bit.ly/3wkN76F 這方法不錯，供您參考
→ EricTCartman: 版本1動態記憶體配置太花時間, 容器也不方便平行化
→ EricTCartman: 你用篩法就能直接平行濾掉了
→ noahleft: 感謝 問題看來是一開始提的方法不適合平行化
※ 編輯: noahleft (118.166.216.124 臺灣), 07/04/2021 15:21:20
→ stucode: 你的篩法平行版本有點問題，vector<bool> 的特性可能會
→ stucode: 導致 data race
感謝提出data race  沒有留意到會有這個問題 :(
※ 編輯: noahleft (36.226.155.109 臺灣), 07/10/2021 20:51:58