想搞个分布式计算项目:SuperPi@home

我一直对圆周率的超精度计算很感兴趣,但知道靠自己一人的力量是没法完成. [em00]
      前几年接触到分布式计算,于是想到,用分布式计算来完成圆周率的超精度计算是很有希望的.于是,开始了漫长的自学编程之路.[em03]
      现在,希望把这个梦想早日实现.[em04]请大家畅所欲言各抒己见,谈谈看法.
      谢谢[em08]

[color=red]不好意思，因为给人原因一直没时间和精力来完成这个项目。但我对这个项目的热情丝毫没有减退，非常感谢大家的支持和关心，我会在忙完这阵子后重新进行这个项目！     2007.4.27添加[/color]

[[i] 本帖最后由 hackerboy 于 2007-4-27 14:31 编辑 [/i]]

好像不太现实,分布式计算最基本的要求就是要能将计算任务划分成小块.
pi的计算能否"断点续算"?

我觉得这个算了有什么用...

像 gimps 一样, 是数学爱好者的爱好,  但取精圆周率 也有意义, 在一些大型工程项目上.....  但只有在实施工程才去运算,

楼主是为了计算 而计算, 没有实际意义啊............

不是有一个软件是superpi吗，测试CPU的。

分布式计算是如何工作

看看这个

1、常见的分布式计算模型
分布式计算的两个主体是Server和许多的Client。中枢计算机——Server产生发送给工作站端的工作数据包，工作站端则根据工作数据包里的数据逐一进行计算，待计算结束后，结果数据包将回传给Server。
当前受欢迎的则是三层架构的模型，把Server的任务分成两层，一层产生工作数据包，另一层充当代理，负责和客户端的联系这是一个简单的能够处理负载量和具备错误保护功能的方法。
基于这种模型的Server必须要能够知道潜在客户端的存在，当每一个工作站开始运行时，Server都需要另一个信息以增加工作数据包的发送量并进一步完善工作数据包，因此每台Client开始工作时将会发送一个需要工作数据包的请求，Server收到这个请求后发送一个工作数据包到Client，随后客户端的软件开始计算。

[IMG]http://distributed.nease.net/distr/4.gif[/IMG]

例如：分布式网络的RC5-64号工程是一个破解加密信息的挑战。为了尝试到每一个可能存在的密钥，从0～264被一个一个的测试，直到我们找到英文文本。事实上，为了易于一次性探测到正确的密码，我们假设隐藏文本是以“密文是……”开始的。
在这种类型的搜索里，我们也许幸运的一开始就找到答案；也许不够走运以至于到最后才找到答案，这都很公平。然而完成RC5-64这一处理将花费掉单个Pentium 3处理器20万年的时间，显然，这超过了它的使用期限。相比之下，如果我们找200000台计算机来进行分工处理，那么也许只需花费一年的时间就能够顺利完成——待检测的密钥序列被化整为零分裂成一个个以228个密钥为单位的块，而每一个块被制成一个工作数据包。

[IMG]http://distributed.nease.net/distr/5.gif[/IMG]

2、Server与Client是如何交流的
要与工作站建立联系并交换数据，服务器产生的所有信息都需要被广播出去。Internet是无处不在的，而电子邮件和超文本传输协议等公用的传送机制都是可供选择的通信资源，至于如何选择取决于我们的分布式运算是以那种方式进行的。

3、工作站端干什么？
分布式计算提出了一个让工作站端能够在后台持许工作的方法，而用户完全不需关心任何东西。这种实现基于两个原则，其一是任务连续分配和空闲优先权，其二是写一个屏幕保护程序。现在的调度程序已经不错了，而空闲优先任务将在人们完全不用关心任何东西的情况下自动执行。利用屏幕保护程序可以利用计算机闲置的时间计算工作任务。

[IMG]http://distributed.nease.net/distr/6.gif[/IMG]

[IMG]http://distributed.nease.net/distr/7.gif[/IMG]

4、如何产生工作数据包？
工作数据包的产生依赖于工作站端的询问工作。在Distributed.net的例子中，这非常简单。从0～264的关键字区域被划分为大小为228的快。当一个工作站端请求一个工作包时，传给它一套10个数据快。这种处理非常简单——当工作端在执行时不能请求新的工作包，它会自发的选择一个数据块来进行计算。为什么要划分为228大小的数据块呢？228是一个比较适当的大小，包含232个关键字的数据块显得太大了，而包含224个关键字的数据块却又过快。

Pi 值计算并不需要很强的计算能力，一般的 PC 足够了。只是利用无穷级数不断从两端逼近而已，原理并不复杂。

现在一个普通的PC在能够接受的时间内算出的结果已经足够精确了

感谢各位的意见，下面我谈谈我的看法：
一。首先我谈谈SuperPi的意义
   在历史方面，众所周知，中国的3。1415926……在世界领先了近千年。但在此之后，就没了身影。pi的记录20年来一直被日本保持。而且一直都是用超级计算机。
   在数学方面，圆周率的研究，推动了一些数学算法的发展。
   再者，圆周率的计算，是检验计算机总体性能的最好方法之一。将其引入分布式计算，能检验网络的总体情况。对下一代网络建设有一定指导作用。（这是我的初衷）

二。现在谈谈实现
   考虑再三，我想放弃C++和FORTRAN，而用JAVA2来实现。究其原因，我们不是因为计算而计算，所以不用在速度上太在意。而要考虑跨平台的可操作性。
   我所知的现在最新记录是日本金田教授在2002年创造的12111亿位，这只有用分布式计算才能打破。我做过分析：
   设经过k次迭代能算出n位有效值。如果用波耳温四级收敛式（至今最快的公式），则需要13.5n字节的存储空间（RAM），要经过(7+27k)*24n*log2 n次双精度运算.(使用多精度算法)
   要用分布式并行计算,必须将它分段.如果分为10段,就需要10的平方+1=101台pc来参加计算,
其间只要有1台出问题,就会前功尽弃. 如果计算到1000万位,每台pc就要100*1000万/10=100MB的RAM空间.总的信息交换量达2*101*100MB=202000MB!


[align=right][color=#000066][此贴子已经被作者于2004-3-6 14:54:41编辑过][/color][/align]

我不是心血来潮,而是"蓄谋以久",我相信会成功的,虽然要走的路还很长.
希望能得到大家的支持与帮助!
谢谢!!!

[quote][b]以下是引用[i]烦人在2004-3-4 14:07:52[/i]的发言：[/b]
好像不太现实,分布式计算最基本的要求就是要能将计算任务划分成小块.
pi的计算能否"断点续算"?
[/quote]
因为是迭代计算,所以目前还没找到断点续算的方法,所以只有将每一次的迭代值备份.


[align=right][color=#000066][此贴子已经被作者于2004-3-6 14:56:01编辑过][/color][/align]

[quote][b]以下是引用[i]mopz0506在2004-3-5 20:38:33[/i]的发言：[/b]
Pi 值计算并不需要很强的计算能力，一般的 PC 足够了。只是利用无穷级数不断从两端逼近而已，原理并不复杂。

[/quote]

1000万位的话一般pc一小时就能算完,1亿位呢?1000万位要135MB的RAM,而1亿位则要1.35GM的RAM,一般pc没那么大,只有调用硬盘做虚拟内存,这样所需时间成指数增加.
那么我们要计算10000亿位呢?

计算圆周率是不错的想法，还可以测试机子，再说了分布式并不是用C++、JAVA这种语言编写的，主要还是如何把数据包分发给用户和如何回收并组合这些数据包，需要有一整套的机制来完成，并不是你想的那么简单，想法不错（希望能实现吧）

你可以看看这本书介绍分布式是如何编写的等。
http://www.dearbook.com.cn/Book/ViewBook.aspx?pno=TS001248

[IMG]http://www.dearbook.com.cn/book/images/711108574401.jpg[/IMG]

[quote][b]以下是引用[i]heroufo在2004-3-6 15:23:21[/i]的发言：[/b]
计算圆周率是不错的想法，还可以测试机子，再说了分布式并不是用C++、JAVA这种语言编写的，主要还是如何把数据包分发给用户和如何回收并组合这些数据包，需要有一整套的机制来完成，并不是你想的那么简单，想法不错（希望能实现吧）

你可以看看这本书介绍分布式是如何编写的等。
http://www.dearbook.com.cn/Book/ViewBook.aspx?pno=TS001248

[IMG]http://www.dearbook.com.cn/book/images/711108574401.jpg[/IMG]
[/quote]


JAVA2已对分布式计算有了很好的支持。
现在我想尽快和中科院联系上，取得他们的帮助。（中科院曾也搞过这样的项目。我也曾和一位中科院教授取得了联系，和他探讨了一些高精度Pi值的问题。）[em06]

Ubero 就是用JAVA实现的

楼主弓虽,支持.好好干吧.

不知这是否能上BOINC?

你先要搞起来再上boinc呀

我们一直支持你！

[quote][b]以下是引用[i]Lightalt在2004-3-6 20:16:55[/i]的发言：[/b]
我们一直支持你！

[/quote]

谢谢！！！[em00]

现在打算先做个单机版的，先检验其演算核心。

楼主的意思不是为了计算多少位pi值~~~而是为了搭建并验证一个分布式计算网络~~~
我也想过如何搭建的问题,并且也是想以计算pi为试验内容,并不是想算多少位,也不是为了打破什么记录.只是用于验证分布式网络计算!!!
硬件方面,我曾经看到过老外用老旧计算机搭建分布式(没有明确指明,我猜是)网络的报道,这样作为试验已经够用了,我觉得第一步可以搭建一个局域网模拟一下,硬件用淘汰的486,老奔腾赛扬?系统用linux系列?可惜我既不是学硬件的也不是学软件的.............
不过可以探讨探讨,出个主意还是可以地~~我qq 121701362

我支持你这位老兄,分布式计算中国也的有自己的项目,既然政府不搞,我们民间可以研究嘛,计算PI是个不错的提议,对PI的计算我有点浅薄的研究,对PI的分布式计算已经有人研究出成果拉,叫
bailey-borwein-plouffe算法  .这个公式简称BBP公式，由David Bailey, Peter Borwein和Simon Plouffe于1995年共同发表。它打破了传统的圆周率的算法，可以计算圆周率的任意第n位，而不用计算前面的n-1位。这为圆周率的分布式计算提供了可行性。公式为
     ∞
PI=∑(4/8n+1 - 2/8n+4 - 1/8n+5 -1/8n+6)*1/16^n
    n=0
1997年，Fabrice Bellard找到了一个比BBP快40％的公式

               ∞
PI=1/64 * ∑(-1/1024)^n * (-32/4N+1 - 1/4n+3 + 256/10n+1  - 64/10n+3 - 4/10n+5 -
              n=0
4/10n+7 + 1/10n+9)

但是上述公式也有明显的问题就是越算到后面越难,这样个人电脑是很难在很短时间完成这计算的.要是能把计算再分就好办拉.而且这些都是大数计算,不是SETI那种FFT快速傅立叶变换.中途短开对计算影响也很大,不过我好象在图书馆看到有方法可以解决,我有空再去找找.希望这项目不要沉下去

一个数分怎么开来算？

[quote][b]以下是引用[i]问鼎在2004-3-16 15:22:42[/i]的发言：[/b]
我支持你这位老兄,分布式计算中国也的有自己的项目,既然政府不搞,我们民间可以研究嘛,计算PI是个不错的提议,对PI的计算我有点浅薄的研究,对PI的分布式计算已经有人研究出成果拉,叫
bailey-borwein-plouffe算法  .这个公式简称BBP公式，由David Bailey, Peter Borwein和Simon Plouffe于1995年共同发表。它打破了传统的圆周率的算法，可以计算圆周率的任意第n位，而不用计算前面的n-1位。这为圆周率的分布式计算提供了可行性。公式为
      ∞
PI=∑(4/8n+1 - 2/8n+4 - 1/8n+5 -1/8n+6)*1/16^n
     n=0
1997年，Fabrice Bellard找到了一个比BBP快40％的公式

                ∞
PI=1/64 * ∑(-1/1024)^n * (-32/4N+1 - 1/4n+3 + 256/10n+1  - 64/10n+3 - 4/10n+5 -
               n=0
4/10n+7 + 1/10n+9)


[/quote]


感谢这位前辈！！！
BBP是一种分段算法，它可以轻易的从任意一位开始算起。
但它的收敛速度只有一级。没法跟波尔温4级式比。所以我想就选波尔温4级，它可是现在最快的公式呀！[em01]

[quote][b]以下是引用[i]问鼎在2004-3-16 15:28:54[/i]的发言：[/b]
但是上述公式也有明显的问题就是越算到后面越难,这样个人电脑是很难在很短时间完成这计算的.要是能把计算再分就好办拉.而且这些都是大数计算,不是SETI那种FFT快速傅立叶变换.中途短开对计算影响也很大,不过我好象在图书馆看到有方法可以解决,我有空再去找找.希望这项目不要沉下去
[/quote]


想选用FFT快速傅立叶变换。
现在最大 的难题是怎样保证数据在网络上的不丢失。

[quote][b]以下是引用[i]lcl121在2004-3-16 18:10:36[/i]的发言：[/b]
一个数分怎么开来算？
[/quote]

现在圆周率的概念不再单单是一个分数。
这说起来话就长了……它涉及的很多高等数学知识。

请大家原谅，还有80天就要高考了，所以最近很忙，这个计划可能要暂时放一放。
等高考完后，我就将全身心的投入到这个计划中来。
我不会放弃的，我回一直坚持下去，这是我的一个梦想，我已经为之奋斗了好几年。
希望大家继续支持，继续帮助，继续关注！！！

hackerboy:这位兄弟啊,你现在还是好好读书把,还有80天拉,高考对人生很重要,一个好学校对自己考研和以后发展都很重要,一个好学校有很好的老师,有很多优良的教学资源.同时我也预祝你考上好大学,一定要上985工程的学校啊.对于此项目我也会尽力给你收集资料,我以前对大数运算有些研究,我们会支持你.有空你留下你的联系方式.我的QQ: 32445
E-MAIL:32445@QQ.com