前言
本文为布里斯托大学推出的52 Things Every PhD Student Should Know to do Cryptography系列学习笔记中的第二篇。原文连接：52 Things: Number 2: What is the difference between a multi-core processor and a vector processor?。
核心问题
本篇文章讨论的核心问题可以概括为以下内容：
- 多核处理器与矢量处理器的区别
- 并行计算问题
并行计算
对于传统的串行处理模型，其解决问题的方法是将计算问题分解为多个指令步骤，在处理器上按照特定的顺序先后执行。执行过程中，处理器分别处理每条指令，最后得出解决问题的答案。尽管这种处理方式良好地解决了对应问题，但它的处理过程凸显出总体计算速度受到单个处理器计算能力的限制这一瓶颈。当需要解决的问题不大时，这一限制表现得并不明显。但是当处理的问题较大时，整个系统的计算效率就会明显地降低，于是我们引入并行计算的方法来突破处理器计算瓶颈，从而加快计算速度。
并行计算将需要解决的问题分割为许多小问题的集合，对于集合中的每个子问题，同时进行单独计算。通过这种方法，我们将待解决问题分成许多小问题并并行地解决子问题，从而大大加快了计算速度——具体效能由算法和阿姆达尔定律共同决定。为了实现并行计算，我们引入多核处理器与矢量处理器并进行二者区别的相关讨论。
多核处理器
多核处理器是单个的计算组件，该组件通过调度多个串行处理器使其同时执行不同的操作来实现并行计算。通过此种调度方法，我们可以轻松地解决前面提到的大问题划分而成的子问题集。这就如同多个人合作项目，每个人各司其职，但所有人都在为该项目做贡献。尽管该种方法可能需要一些额外的组织工作，即统筹调度各个“核”（串行处理器）需要消耗一些时间，但完成项目的总体速度将会更快。
向量处理器
尽管向量处理器和串行处理器一样每次处理单条指令，但与在单个数据集上运行的标准串行处理器不同的是，向量处理器的数据集包含许多以一维数组排列的数据并同时对其执行相关指令。如果需要对程序中不同数据集多次执行相同指令，可以考虑引入向量处理器，从而一次性地完成指令执行，大大提高计算效率。通常使用首字母缩写SIMD(Single Instruction Multiple Data)来表示以这种方式工作的指令。
二者区别
下面来讨论多核处理器与向量处理器的区别。经过上面的描述我们可以很明确地得出，多核处理器在计算问题层面进行处理，将大的计算问题进行分解，计算分解后的子问题；向量处理器在数据集层面进行处理，将多个需要执行同一指令的数据集进行合并，本质上没有处理计算问题本身。
我们使用更形象的例子进行解释。假设我们要在一条道路上滚动四块石头，每次滚动需要一分钟。串行处理器将其一一滚动，因此需要四分钟。双核处理器等价为有两个人同时滚动石头，对于每个人来说只需要滚动两块石头，这两个人同时进行滚动作业，总共需要耗费两分钟。而向量处理器相当于制造一块长木板，将其放在四块石头的后面，推动木板以实现四块石头同时滚动，这样只耗时一分钟便将四块石头滚动到对侧。
简而言之，多核处理器具有多个工作程序，而矢量处理器同时对多个事件执行相同的操作方式。
阿姆达尔定律
阿姆达尔定律用来计算将一个运算过程的某一部分并行化后，该运算速度的提升幅度。
相关定义
阿姆达尔定律将一个可并行化的程序或算法分成两个部分：
- 不能被并行化的部分
- 可以被并行化的部分
例如，对于处理硬盘文件的程序来说，这个程序可能有一小部分负责扫描目录并创建文件列表内存对象，随后每个文件对象被发送给另一个单独的线程进行处理。在这个程序中，负责扫描目录和创建文件列表的那部分不能被并行化，但负责处理文件的部分可以。
我们定义以串行方式执行这个程序时消耗的时间为T,T为可并行化部分和不可并行化部分的时间之和，其中不可并行化部分消耗时间为B，则可并行化部分消耗时间为T-B。
按照阿姆达尔定律，当可并行化部分使用N个线程或CPU执行时，程序的总体执行时间可由以下公式表示：
1 | T(N) = B + (T - B) / N |
其中T(N)表示以N个并行因子执行时程序的所耗时间；T也可以写作T(1)(可以等同看做以1个并行因子执行时的所耗时间)。如果使用T(1)而不是T表示的话，阿姆达尔定律的形式变为：
1 | T(N) = B + ( T(1) - B ) / N |
算法优化
从阿姆达尔定律来看，显然，可并行部分可以通过增加硬件数量来提升其执行速度，而不可并行化部分则只能通过优化算法来提升。也就是说，优化不可并行部分也可以提升整体执行速度，甚至可能的话，将不可并行化部分中的部分工作划分到可并行化部分，以使程序的不可并行化部分变得更小。
优化不可并行部分
在优化不可并行化部分时，可以应用阿姆达尔定律来计算程序优化后的预期执行时间。如果不可并行化部分B的优化因子为O，则其阿姆达尔定律的计算公式为：
1 | T(O,N) = B / O + (1 - B / O) / N |
注意，现在不可并行化部分的所耗时间为B / O 了，相应地可并行化部分的所耗时间应为 1 - B / O 。
执行时间和加速比
目前为止，我们仅仅用阿姆达尔定律计算了一个程序（或算法）在优化或并行化之后的执行所耗时间。但阿姆达尔定律不仅限于此，我们还可以用它计算加速比(speedup)，所谓加速比，就是优化后的算法（或程序）相对于旧的算法在速度上的提升倍数。
假设旧的程序(或算法)的执行时间是T，则加速比可表示为：
1 | Speedup = T / T(O,N) |
通常我们将T设为1，加速比为相对于它的分数形式，则加速比的公式变为：
1 | Speedup = 1 / T(O,N) |
如果我们再将T(O,N)进行代入，则代入后的公式为：
1 | Speedup = 1 / ( B / O + (1 - B / O) / N ) |
定律理论性
虽然阿姆达尔定律使你能够通过计算得出一个并行化后的算法的预期速度提升值，但是不要过于依赖这样一种计算。因为在实践中，当你优化或者并行化一个算法时，可能会有许多其他因素产生影响。
例如：内存、CPU缓存，及硬盘、网卡等（如果算法需要与硬盘和网卡交互的话），这些硬件的速度可能也会是一种限制因素。如果并行化一个算法后，引起了大量的“CPU缓存丢失”问题的话，你可能甚至得不到期望的提速效果——“增加N倍的CPU则得到的N倍的速度”；或者，如果优化后的算法最终会导致内存空间、硬盘、网卡、网络连接被占满的话，同样也会得不到预期效果。
最重要的一点是，有时候一个高度串行化的算法可能胜过并行算法。这是因为串行化算法没有并行算法的协调消耗，而且单一CPU算法更适应底层硬件的工作方式。
