分布式计算和并行计算的区别与联系在哪里？
关注者
339
被浏览
103,086
15 个回答
从理论计算机的角度看，主要区别应在通讯的延迟和成本上吧。
并行计算中不同单元之间的通信延迟和成本很低。常见的复杂度类中，NCₖ 的定义就是一种高度抽象的并行计算。不严格地讲，NCₖ 中的问题，如果用多项式多个核，可以在 O(log(n)ᵏ) 的时间内计算完。
而分布式计算中，一般认为通讯的延迟和/或成本很高。一种常用的抽象是假设节点内部的计算没有成本，算法的复杂度用节点之间的通讯量来衡量。节点之间的总通讯量被称为通讯复杂度（communication complexity）。值得一提的是，通讯复杂度这个概念是由姚期智引入的。
－－－－－－－－－－以下是私货－－－－－－－－－－
在密码学中，还有一个相关的问题是（可信/安全）多方计算，简称 MPC。与前两者的关系大概是这样
\begin{gathered} \boxed{\begin{gathered}\text{Parallel Computation}\\\text{并行计算}\end{gathered}} \\ \Downarrow\rlap{\text{瓶颈是通讯复杂度}} \\ \boxed{\begin{gathered}\text{Distributed Computation}\\\text{分布式计算}\end{gathered}} \\ \Downarrow\rlap{\text{部分节点不可信/不可靠}} \\ \boxed{\begin{gathered}\text{Secure Multi-Party Computation}\\\text{多方计算}\end{gathered}} \end{gathered}
在现实中，因为延迟的关系。通讯轮数经常比通讯量更重要。所以 MPC 中，一个关注的要点（也是一个 open problem）就是如何最小化通讯轮数。
我博士就是做hpc的fault tolerance的，可以说两边都搭边。两者现在基本在融合，以前做并行的一些思路现在也得往分布式上靠。
对待fault的态度曾经是两者最大的分水，并行hpc的做法上，程序逻辑是不考虑容错的，你写内存传变量，都可以认为是可靠操作。但是程序运行的越来越久，系统变大变复杂，mttf，mtbf参数已经到了不能忍受的临界点。那就开始做ft吧。
但是ft这个东西吧，分布式自打诞生第一天就是做这个的，可以说整个系统就是围绕fault的处理而建立的。
hpc要做大做稳就是要学会分布式的这些套路，软件框架和系统架构。做精做快就是芯片，acclerator，所以自身反倒是空心化了。有点尴尬的topic了。