tprime 发表于 2008-7-4 13:24:19

孪生素数的计算

正在优化我的孪生素数筛程序, 主要受限于内存带宽
目前筛10^16内孪生素数需要3000小时
有望能在2400小时完成,正考虑用CUDA实现

无心人 发表于 2008-7-4 14:16:02

:b:

CUDA一次能达到多大的并行？？？

无心人 发表于 2008-7-4 14:17:38

tprime:
如果只筛10^4以下的素数
得到的筛子里
有多少候选？？

tprime 发表于 2008-7-4 14:39:57

时间需要10小时, 需要筛 7.81%的数
用CUDA心理没谱, 正在学习中,
CPU内存访问密集型应该能提高性能

tprime 发表于 2008-7-4 14:41:29

CUDA能同时运行512个线程, 如果程序设计很好
较少的分支, 访问连续性能会更好, 较好的情况
能达到主流CPU的10倍性能(内除带宽)

无心人 发表于 2008-7-4 15:01:41

你现在筛到多少？

是完全筛，还是筛完后，用算法测试候选？

tprime 发表于 2008-7-4 15:08:29

完全的筛而不存.
由于我的程序在开始就能精确预测总计算时间
(多次反复测试和结果误差不到 0.1% 时间)
目前只算了10^14的孪生素数
10^15的K = 4,5,6,7,8 生素数
10^16以内的6生素数
如果要算10^16以内孪生素数恐怕需要上并行机, 你可借用否?
国外都用并行计算好几个月.

tprime 发表于 2008-7-4 15:09:08

<pre>表格中有时间的是我算得
更详细的数据在我pc上

                                    Table of PI_X(10^n)( 2 <= X <= 7, 8 < n < 17)
__________________________________________________________________________________________________
|   x   |PI2(x)t2(s) | PI3(x)   t3(s) |PI4(x) t4(s) |PI5(x)    t5(s)| PI6(x) t6(s)| PI7(X)t(7)
---------------------------------------------------------------------------------------------------
| 10^09 |3424506   0.75|379508      0.55|28388   0.22 |3633       0.19|317      0.09| 54
|       |            0.25|379748      0.17|      0.08 |3588         |         0.03| 49
----------------------------------------------------------------------------------------------------
| 10^10 |27412679    7.24|2713347   4.63|1805291.64 |20203      1.28|1613   0.55| 234
|       |            2.37|2712226   1.56|      0.58 |20211      0.53|         0.17| 239 0.17
---------------------------------------------------------------------------------------------------
| 10^11 |224376048    112|20093124    64.7|1209318 19.3 |122457    12.95|8626    4.34|1183
|       |            26.3|20081601    17.9|      6.15 |122855   3.91|         1.50|1152 1.22
----------------------------------------------------------------------------------------------------
| 10^12 |18705852201005|152850135    580|8398278 186. |776237    117.2|50408   40.51|6056
|       |             255|152839134    156|      53.5 |775986   34.1|         12.4|591310.2
----------------------------------------------------------------------------------------------------
| 10^13 |15834664872   |1189795268      |60069713 2324|5108291      |303828    440|33395
|       |            4369|11898269662304|+877      685|5109269   381|          132|33066 102
----------------------------------------------------------------------------------------------------
| 10^14 |135780321665    |9443942337      |441296836    |34709176       |1911246      |193078
|       |         35694|9443899421 20344|         6440|34701400   3750|         1304|192731 988
----------------------------------------------------------------------------------------------------
| 10^15 |1177209242304   |76222348070(x)|3314576487   |242554539      |12431996   |1167688 +24
|       |                |                |+8790   96564|242526656 50564|+133    16116|1166385 +26 10563
----------------------------------------------------------------------------------------------------
| 10^16 |10304195697298|                |25379433651|               |83217782   |
|       |          3000h |                |             |               |       216236|
----------------------------------------------------------------------------------------------------
| 10^17 |                |                |             |               |482142192 (x)|
|       |                |                |             |               |+1170 3556211|
----------------------------------------------------------------------------------------------------
prime 4-tuples(10 ^ 16) = 25379433651,          time use 340h
prime 6-tuples(10 ^ 16) = 82942101 + 1170,      time use 55.01h
prime 6-tuples(10 ^ 15) = 12431996 + 133,       time use 16116.41s
prime 4-tuples(10 ^ 14) = 441295937+ 899,       time use 6439.90s
prime 4-tuples(10 ^ 15) = 3314576487,         time use 96563.25s
prime 2-tuples(10 ^ 14) = 135780262685 + 58980, time use 35693.32s
prime 8-tuples(10 ^ 15) = 116493,               time use 8427.10s // one of the patterns</pre>

tprime 发表于 2008-7-4 15:12:18

下面是运行的屏幕输出

Calcaute prime k-tuples: PI2(1.0e+16)
Copyright: 2008 by Huang Yuanbing
Version:2.11
Mailto: bailuzhou@163.com

[Make sure your cpu L2 > 1367k with 2 core,
-----or it'll very slow for cache miss]

POWTEN = 16, THREAD_NUM = 3, SP = 10
BLOCKSIZE = 892371480, MASK = 31,

memory use = 56023207, need memory = 31808700
at least need total memory : 135 M

step 0 : sievebuff size = 2525 k
Prime = 10000
step 1 : sievePrime n = 100000000
Prime = 99999989
sieve sqrt prime time use 498.68 ms

step 2 : sievePattern n = 223092870
pn = 7952175
prime mode = 223287305 , all pn = 31808700
sieve patterns time use 420.54 ms, percent = 7.1290

step 3 : sieveTuples n = 892371482
Prime = 29872
tuples = 3091491
sieve block kutples time use 5071.79 ms

Thread , finishing ... 0.00%, time remain : 9340631 s,       total need time : 2594.63 hours, segment ts = 339331
Thread , finishing ... 0.00%, time remain : 9419845 s,       total need time : 2616.63 hours, segment ts = 323542
Thread , finishing ... 0.00%, time remain : 9526731 s,       total need time : 2646.33 hours, segment ts = 346475
Thread , finishing ... 0.00%, time remain : 9558375 s,       total need time : 2655.13 hours, segment ts = 346535

gxqcn 发表于 2008-7-4 16:02:59

to tprime、无心人：

两位“顶帖”也应区分一下主贴啊，
虽然我知道你们的初衷并不是来“顶”的。

因为，若主题帖有问题，比如内容为广告、或犯低级错误等，
有可能被沉底、锁帖、删除处理（分立即执行或集中执行），
:tip: 一旦删主贴，其所有跟帖也将一并消失。


其实，凡是普通个人观点被移入“百家争鸣”的帖子，
大家都应谨慎留神，因为出错的可能性比较大，
有些错误甚至是很明显的，
设立该版是为了让他们可以有个言论讨论的地方，
让大家指出其不足。

需要强调的是，
本论坛对伪科学的、民科性的所谓“论文”坚决反对，
发现后将立即删除，并对发帖者永久性禁言！
页: [1] 2 3 4
查看完整版本: 孪生素数的计算