|
|
很长时间没露面了~~~
最近参加微软的嵌入式比赛，比较忙
ChinaPI还在继续做，但是目前遇到了一个技术问题，比原定的进度慢了不少
这学期我们计算引论让写篇论文，我于是写了篇ChinaPI的介绍，有一小段引用了网站中的内容
现在贴在这里，供大家参考（图和公式省略）：
[题目]利用空闲计算资源进行分布式计算的实例ChinaPI
[分类]计算理论导论论文
[作者]郝佳男33060609
[日期]2005.2.20
[关键词]分布式计算 PI
[摘要]
本文简要剖析了一个利用空闲计算资源进行分布式计算的实例，该实例为作者于2004.8开发的一个项目，旨在用分布式计算进行PI值的计算。本文将从一个分布式计算设计者的角度阐述分布式计算的概念、原理及其重要意义
[正文]
一、 空闲资源与分布式计算
每时每刻，全世界都有无数台计算机正在工作，然而绝大多数的时间这些计算机并不处于100%的工作状态，且很多近乎于空闲，这样就造成了严重的计算资源浪费。把这些空闲资源汇总并加以利用，就能造就巨大的计算资源。
分布式计算为整合这些资源提供了理论依据和实践方案。通过分布式计算，一个庞大的计算任务可以被分解为若干子任务，通过网络主机（主任务的发起者）将这些子任务根据一定策略分配给具有空闲资源的计算机，空闲资源被用于计算这些子任务，并将这些任务的结果返回主机。依靠空闲资源的数量优势，主任务在很短的时间就可以执行完毕。这使得一些在原来的被认为不可计算的问题（如NP）可以在被接受的时间内完成。
二、 国外的相关项目
目前国外已经有相当多的利用空闲计算资源进行分布式计算的项目，下面简要介绍一下：
 SETI@home是世界上最大的分布式计算项目。它通过使用联网的计算机下载程序分析射电望远镜所收到的讯号，来搜索地球外的生命迹象。
 Folding@home是一个研究蛋白质折叠，误解，聚合及由此引起的相关疾病的分布式计算工程。它使用联网式的计算方式和大量的分布式计算能力来模拟蛋白质折叠的过程，并指引我们近期对由折叠引起的疾病的一系列研究。
 Climateprediction.net工程是把最新的气候预测模型通过家庭、学校、办公室的计算机来进行计算。这些计算完成的结果将会组成世界最大的气象预测模型。
三、 ChinaPI的起源
2004年7月，我计划写一个简单的分布式计算（并行计算）程序在报刊上发表来向公众介绍分布式计算的原理。为了寻找相关资料，通过搜索引擎找到中国分布式计算总站www.equn.com。在论坛中无意中发现一条“为什么没有中国组织的分布式计算的讨论”，回复“为什么不自己做？”后短时间内就收到很多响应。正是在此时，我萌生了开发中国自主知识产权的分布式计算平台的想法。随后的日子里，我定下了开发规划，其第一个项目定为一个专用分布式计算项目，它只对一个特定的计算任务提供分布式计算，旨在对分布式计算系统的基本功能进行测试，为了简便计算，也为了使项目具有一定的实际意义，我选择了对PI值的计算作为分布式计算的计算任务。
同年8月，ChinaPI正式立项，进入实施阶段，第一个版本，即架构测试版开始研发。由于系统结构复杂，涉及技术领域众多，开发十分艰难。众多分布式计算爱好者为我提供了测试数据，并给予我极大的支持。
同年9月，ChinaPI的基础架构搭建完成。我建立了一个小的任务，由网友进行测试。不久后，测试完毕，测试结果未见异常。
此后，ChinaPI不断对一些部分进行关键更新，以便在适当时推出下一个测试版。
四、 ChinaPI的可行性分析
1、 计算复杂度分析
BBP公式（如下图），由David Bailey, Peter Borwein和Simon Plouffe于1995年共同发表。它打破了传统的圆周率的算法，可以计算圆周率的任意第n位，而不用计算前面的n-1位。这为圆周率的分布式计算提供了可行性。
1997年，Fabrice Bellard找到了一个比BBP快40％的公式（如下图）。ChinaPI中所使用的计算PI值的公式就是这种公式
ChinaPI的设计目标是计算PI小数点后 位（二进制位），对公式变形，两边同乘以 ：
这样变形后，等式右边的小数部分就是从PI小数点后 位（二进制位）开始的数字，只要精度足够，就可以得到PI小数点后 位（二进制位）附近的值。其计算核心实质为计算a^b mod c的值。
若在单机上实现这个算法，则时间复杂度为O（K ），K为常数，空间复杂度为常数。
由于所求为级数之和，故可对其运算顺序进行任意调整，具有极高的并行性。若将其分解为若干子序列之和则各个子序列相互之间互不影响，无任何依赖关系，故可认为其用于同步的时间费用可忽略不计。
设有M台性能相近的计算机资源参与计算，则时间复杂度为O（ ），随着M的增大，时间复杂度随之反比降低。
由此得到结论，只要M足够大，任务计算就可以在允许的时间内结束。
2、 技术可行性
ChinaPI的技术设计要求包括：
1) 准确：要保证所的结果的准确性，降低误差，防止因有意或无意的篡改
2) 高效：在准确的前提下应保证计算的速度尽可能的快
3) 安全：由于要在Internet上进行数据传输，应保证数据的安全和参与计算者的安全
4) 容错：能够对已知或未知的灾难进行一定程度的恢复，对于长时间未完成的子任务进行回收再分配
针对准确性的要求，在编程时要保留足够的精度。例如，在计算过程中，除最终的除法-求和使用FPU的80位扩展浮点表示，其余步骤结果均用64位整数储存，中间运算使用128位整数。在防止数据篡改方面，使用了HASH效验，用户-任务包关联的方法，在一定程度上遏制了数据篡改。
在高效运算方面，除对算法进行优化外，对于关键核心代码，运用汇编语言，使用FPU、SSE等指令集进行优化。
安全方面，使用TCP连接保证数据一定程度上的完整，并进行HASH效验。
容错方面，对于每一个实质的计算任务，创建两个相同的计算任务，并分配给不同的计算者进行计算，并对返回的计算结果进行比较，验证其准确性。计算过程中，对中间的计算结果定期保存，使计算可以随时暂停-继续。服务端（负责调度分配）的数据库定期备份。
3、 空闲资源分析
前面已经提到，时间复杂度O（ ）的大小取决于M的大小，即空闲资源的多少。既然是取名为ChinaPI，我更多的希望中国用户对它的支持。
根据中国互联网信息中心的统计信息，中文网民人数占世界的比重已经增长到了12%左右，并且还在快速增长着。这里所说的中文网民包括大陆、香港、澳门、台湾和海外华人。但是相比于互联网在中国的快速发展，中国的分布式计算却发展缓慢。SETI@home是世界上最大的分布式计算项目。从中国的参与人数来看，它在中国也是最著名的项目，目前的参与人数为几万人，这主要是因为分布式计算在中国还没有普及。
ChinaPI的另一个设计初衷就是在中国普及分布式计算。以目前的情况看，需要 至 的参与者。宣传分布式计算的概念将成为决定ChinaPI成败的重要任务。
五、 ChinaPI的架构
ChinaPI架构测试版的简明架构图如下所示：
（图略）
可见，数据库是系统的核心，它记录着当前的用户信息，任务分配状况，分配策略等重要信息，是重点保护对象，因此要做到数据库与Internet无直接连接。网络方面使用成熟的C/S方式，协议为TCP/IP。
六、 ChinaPI的现状
目前架构测试版已经完成测试，证明整体架构可行。与设计目标相比，尚有下列问题需要解决：
1） 目前的算法只能计算PI值 位（二进制），这主要是由于精度问题引起的，引入128位中间计算可以解决，但效率会下降很多，需要大力优化。
2） 当前数据库的设计过于冗余，造成数据库过大
3） 网络连接方面稳定度需要加强，预计Socket部分用C重写后可以解决
4） 防止数据篡改的技术还没有加入
5） 宣传的方案需要制定
6） 如何解决投产所需的资金
七、 利用空闲计算资源进行分布式计算的重要意义
利用空闲计算资源进行分布式计算是一种低成本的大规模计算解决方案，是对当今网络、数据库、加密、数值运算等诸多技术的整合。它不需要像巨型机那样的巨额初期投入和运行时的维护成本，而且即使计算已经开始，也可以添加/减少投入的计算资源，具有很强的伸缩性。由于计算资源是大量的，即使少量的计算资源出现不可预期的错误依然不会对整个计算任务产生影响。
在中国，这种计算模式尤其适合，因为中国的计算机用户很多，空闲计算资源相当多。许多科学研究都需要巨大的计算能力，而只有很少的有足够的资金去使用巨型机，将这种需求与空闲计算资源相结合，应用分布式计算就能够产生巨大的效益。
21世纪，计算能力将成为一个企业乃至一个国家的战略资源。希望ChinaPI能成为这方面的先行者。
[参考文献]中国分布式计算总站（http://www.equn.com） |
|
发表于 2005-2-24 18:33:05
发表于 2005-2-24 20:04:26
