概述

千里之行，始于足下

并发 or 并行

初学操作系统时有两个概念很容易搞混，无论是教师讲课还是课后习题总会出现这两个概念：并行和并发。并行的意思是程序在多个内核中同时运行；并发指的是在同一时间段同时发生，给人的感觉是多个程序同时运行。实际上并发是一个处理器运行多个程序，处理器给每个程序分配一个很小的时间段，从微观角度看是串行，从宏观角度看约是同时运行。用Erlang之父Joe Armstrong的图来描述。

再回过头来看看并发和并行的英文。并发是concurrent, 并行是parallel。看英文无论如何也不会混淆，为何中文翻译两个词如此接近！给人一种译者极不专业的感觉。我更愿意这样翻译，parallel是 并行，concurrent是 段发。每个概念在描述什么内容，一目了然。

好了，现在弄清楚了 并行 和 段发 概念。首先说明这里的 并行计算 或者 并行编程 不做区分。在接下来的文章中即有 道 也有 术。

并行计算是什么

串行程序

我们在用程序解决一个具体的问题时会考虑如下几个步骤：

• 解决此问题需要分成几步
• 这些步骤的执行顺序是什么
• 将上述步骤编码为程序
• 用一个处理器按照既定的步骤来执行程序

并行程序

考虑归并排序。将序列平分为两个，然后同时对两个序列进行排序，排序之后再合并两个有序序列。并行的思路解决一个问题一般要考虑：

• 将问题切分成几个可以同时执行的步骤
• 每个步骤都按照串行的方式执行
• 每个步骤在多个不同的处理器上执行

注意：并行计算和分布式计算有不同的地方：分布式计算更多的意味着在远程服务器上用分配的资源来并发的执行任务，并行计算是用多核处理器来同时处理一系列的任务。

并行计算的应用

在日常生活中并行思想的应用是很自然的一件事。

• 多窗口售票
• 多车道行驶
• ... ...

人类生活是需要科技推动的，并行计算在科学应用中也十分广泛。一些科学问题是极其复杂的，例如：

• 星系形成
• 行星运动
• 气候变换
• 交通预测
• 板块构造
• 天气预测

科学问题通常是有一些特点：

• 影响因素极其多
• 建模或仿真时的参数数以亿记
• 海量的数据需要处理
• 需要大量的计算资源

通过并行计算，能够合理利用计算资源、大幅度降低计算时间，在合理的时间和计算资源内得到结果。

在涉及到我的工作时，并行计算得应用就更加广泛、更加深入，甚至是润物细无声的：

• 所有深度学习模型的训练、评估，以及部署应用
• 机器学习的训练、评估，和部署应用
• 数字图像处理
• 矩阵计算
• 大数据处理
• ... ...

为什么用并行计算

上述的介绍已经说明了，在日常生活中方方面面都在使用并行的思想，在科学研究中，并行计算必不可少。在我的工作中则愈加重要，所以我不想只是简单的使用工具，我要掌握并行计算，用并行计算编程解决实际的问题。我要在道和术层面掌握并行计算。

另外，还有一件非常重要，但是容易忽略的事情：并行计算的思想是什么？

数据结构和算法人人都很熟悉，在用编程解决一个问题时，通常会考虑：

• 用什么数据结构表示更合理，如何在 O(1) 时间内解决问题
• 用什么算法更快，尽可能减少重复计算，用更少的计算步骤解决问题
• 如何在空间和时间之间做权衡
• 为了代码的可读性要不要牺牲算法的复杂性（往往会增加时间复杂度）
• ... ...

可以说对信息行业的从业者，数据结构和算法的概念深入人心，甚至是深入骨髓。但是这种编程训练往往是针对串行的算法，如果是用并行计算，那并行数据结构和算法的概念与串行的还一样吗？如果不一样，并行数据结构和算法是什么样的？

参考资料

Introduction parallel computing tutorial (opens new window)

台湾新竹清华大学 平行程式 (opens new window)