作者:
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的成本太高