Definição e significado de 分布式计算

分布式计算是一种把需要进行大量计算的工程数据分割成小块，由多台计算机分别计算，在上传运算结果後，將結果统一合并得出数据结论的科学。

目前常见的分布式计算项目通常使用世界各地上千万志愿者计算机的闲置计算能力，通过互联网进行数据传输。如分析计算蛋白质的内部结构和相关药物的Folding@home项目，該项目結構庞大，需要惊人的计算量，由一台电脑计算是不可能完成的。即使现在有了计算能力超强的超级电脑，但是一些科研机构的经费却又十分有限。

  一些分布式计算的例子

• Climateprediction.net：模拟百年以来全球气象变化，并计算未来地球气象，以对付未来可能遭遇的灾变性天气。
• D2OL：研究新药物。
• DPAD：设计粒子加速器。
• Einstein@Home：於2005年(定為 世界物理年)的這一年開始的計畫，預計是要找出脈衝星的重力波，驗證愛因斯坦的相對論預測。
• Find-a-Drug：并行运行一系列项目，用来寻找一些危害人类健康的重大疾病的药物。项目目标包括疟疾、艾滋病、癌症、呼吸道系统疾病等等。
• FightAIDS@home：研究艾滋病的生理原理和相关药物。
• Folding@home：了解蛋白质折叠、聚合以及相关疾病。
• GIMPS：寻找新的梅森素数。
• SETI@home：通过运行屏幕保护程序或后台程序来分析世界上最大的射电望远镜所收到的、可能含有外星智能讯号的射电波。
• SOB：解决谢尔宾斯基问题。
• United Devices：综合科学性运算，主攻医药领域，以寻找抗癌药物和天花疫苗为主。
• Distributed.net：2002年10月7日，以破解加密术而著称的Distributed.net宣布，在经过全球33.1万名电脑高手共同参与，苦心研究了4年之后，他们已于2002年9月中旬破解了以研究加密算法而著称的美国RSA数据安全实验室开发的64位密匙——RC5-64密匙。目前正在进行的是RC5-72密匙。
• 最优Golomb尺问题（OGR）。所谓Golomb尺是指在一个固定整数长度的尺上不等长地划分最少的刻度，并且不存在这样的两对刻度使得每对刻度量出的长度相等的问题。例如OGR-6是在6cm的尺上按0、1、4、6划分刻度，即可连续量度1、2、3、4、5、6cm的每一距离。最优Golomb尺OGR-22、23、24、25(Phase1)均已解决，目前正在进行的是OGR-25(Phase2)。

可参见网格计算。

  主流分布式计算项目列表

• 正在运行中的分布式计算项目
• Sun Grid Engine - 昇陽電腦所研發的分布式計算機集群軟件。

  复杂性衡量

在并行算法中，对资源的要求除了时间和空间之外，还包括计算机的数量。通常，运行时间和计算机数量之间有个权衡：在并行系统中，更多的计算机会使得问题解决得更加快速（见speedup）。如果一个决策问题通过使用一个多项式数的处理器在综合对数时间内被解决，那么，称这个问题属于NC类。NC类可以用并行随机存取机的形式或者布尔电路来等价——并行随机存取机可以有效地仿真布尔电路，反之亦然。

在分布式算法分析中，人们更加关注的是计算机间的通信而不是算法步骤。同步系统可能算是最简单的分布式系统了，因为它里面所有的节点步调一致。在每一轮通信中，所有节点并行：

（1）从他们邻居节点接受最新消息。

（2）执行任意的本地计算。

（3）给邻居节点发送信息。

在中系统中，核心计算复杂度在于完成任务所需要的同步通信轮数上。

算法复杂度和网络的直径有密切关系。设网络直径为D。一方面，在同步分布式系统中，任何计算问题几乎都可以在2D轮通信之内完成：收集信息到一个本地节点（D轮通信），然后计算，再把计算结果告诉邻居节点（D轮通信）。

另一方面，如果运行时间远远小于D轮通信，这时候，网络中的节点还没来得及获取网络中远处的信息，就得产生输出。换句话说，节点只有在获取了邻居节点之后才能对网络做出决定。很多的分布式算法运行时间都远远小于D轮通信，在这种情况下，明白什么问题能用这类算法来解就是这个领域的核心问题了。

其他的衡量措施是网络上传输的比特总数（cf. communication complexity）。

  參考資料

  外部链接

• 中国分布式计算总站
• 中国分布式计算论坛

查 · 論 · 編 并行计算 概论 高性能计算 · 计算机集群 · 分布式计算 · 网格计算  · 雲端運算 方式 Bit-level parallelism · Instruction level parallelism · Data parallelism · 任务并行 理论 Speedup · Amdahl定理 · Flynn's taxonomy (SISD • SIMD • MISD • MIMD) · Cost efficiency · Gustafson定理 · Karp-Flatt metric 元素 进程 · 线程 · Fiber · PRAM模型 协调 多處理 · 多執行緒 · 超執行緒 · 内存一致性 · Cache coherency · Barrier · 同步化 · Application checkpointing 编程 Programming model · Implicit parallelism · Explicit parallelism 硬件 贝奥武夫机群 · 对称多处理机 · Asymmetric multiprocessing · Simultaneous multithreading · 内存 （非均匀访存模型 · Cache only memory architecture · 共享内存 · Distributed memory · Distributed shared memory ） Massively parallel processing · 超纯量 · 向量处理机 · 超级计算机 · Stream processing · 通用圖形處理器 (GPGPU) APIs POSIX Threads · OpenMP · 訊息傳遞介面 (MPI) · Intel Threading Building Blocks 问题 Embarrassingly parallel · Grand Challenge · Software lockout · 可扩放性 · 競爭危害 · 死锁 · 确定性算法