（本文为新竹清华大学《并行计算与并行编程》课程笔记 ）
  关于分布式系统和并行计算，其实没有必要非得区分个一二来。当然它们各有侧重，分布式系统是基于网络的一种软件，而并行计算更像是一种概念，这个概念可以在硬件中出现，也可以在软件中出现。再比如分布式系统更偏向于管理一组计算机，而并行计算关注的是每一个计算节点即一个处理器、一个core。因此，一个CPU或GPU芯片也是并行计算施展的领域。
  在这门课程里，并行计算其实是在硬件、系统、编程模型和编程语言四个不同的层次上讨论的。
  它们的应用场景也很类似：如何把一件事分给许多计算单元并行去做，或者如何协调多个计算机完成一件事。也就是说，去处理一个从1到n的分发，或一个从n到1的收集。通常认为并行计算侧重于其中前者，即由一个manager向worker分发任务。那么站在manager的角度思考问题，核心就是：效率。即，并行计算是效率导向的设计。

1. 并行架构的分类

1.1 弗林分类法

  Flynn在指令（Instruction）和数据（Data）两个维度上，将并行计算机划分为四类：
（1）SISD
  单指令流、单数据流，其实就是串行机。在任一时钟周期内，只有一个数据流用作输入，且只有一个指令流被处理。
（2）SIMD
  单指令流、多数据流。在任一时钟周期内，所有处理单元指向相同的指令，但是可以用来处理不同的数据。GPU就是一种SIMD架构。
（3）MISD
  多指令流、单数据流。这个架构几乎没啥用，除非特殊需求。
（4）MIMD
  多指令流、多数据流。最常见的架构，现在的多核处理器都是MIMD的。

1.2 内存体系结构

（1）Shared Memory
  多个计算单元共享一个内存，多核CPU计算机一般都是这种结构。它又分为两类：

• Uniform Memory Access (UMA)
    统一内存访问，最常见的是对称多处理器架构（SMP），就是一块内存上连接了很多个相同的（理论上效率一致）的CPU。效率一致即 “对称” ，这是很好的设计，一旦算力出现异构，那要是想做到随机、平均地分配任务，要考虑的东西就多多了。一般的商业服务器都是UMA架构。
• Non-Uniform Memory Access (NUMA)
    通常做法是让多个SMP彼此相连，每个SMP节点内的CPU可以跨SMP访问其它SMP内的数据，这种访存方式当然远远不及SMP内部访存效率高。HPC（高性能机群）服务器一般是这种架构。

（2）Distributed memory
  Distributed memory就是我们所谓的一群计算机，它们各自有各自的内存，几十台规模的就是Cluster，上百台规模的可能就是超算，上千台规模的就是数据中心咯。它和NUMA最大的差异就是，NUMA的内存组件尽管是分开的，但是彼此相连（通过总线），硬件层面的相连当然就意味着物理上相连。
  不过尽管这些机器的内存在物理上彼此独立，但是这些机器通常也是摆在一起的。他们通过通信网络彼此连接，因此需要程序员去定义一些通信规则。

1.3 并行编程模型

  并行编程模型是一种硬件和内存架构之上的抽象。一般来说，不同的内存体系结构和不同的编程模型都是相互匹配的。比如共享内存编程模型就往往应用于共享内存架构，而消息传递模型则大多应用于分布式内存架构。但这也不意味着它们彼此间就是绑死的。
  消息传递模型就可以用在共享内存架构上，比如MPI，就可以用在单机上。反之亦可，只是在分布式内存中跑共享模型可能开销会很大。

（1）Shared Memory Programming Model
  共享模型其实就是常见的多线程，因此原理不再赘述。它有两种典型的实现，核心功能是相同的：

• POSIX Thread（Pthread）：一个库，通过调用库函数指向它的功能，它实际工作的层次要比OpenMP低一些；
• OpenMP：嵌入源代码里的一组预编译指令，在源码里加入OpenMP，就是一堆#语句。

  Shared Memory模型可以共享数据，然后仅仅是在串行代码里加入一些语句，实用比较方便，但是Scalable比较差。

（2）Message Passing Programming Model
  涉及到跨物理内存访存肯定就是网络了，主要是设计message passing的API，比如：send，recv，bcast，gather，scatter…最经典的实现就是MPI。当然，MPI也是定义了一些API，就像STL一样，由不同的厂商去实现，实现出来的东西称为MPI.library。
  Message Passing模型的问题在于，尽管能很好地扩展，但是原本部署在单机上的数据结构需要重新设计，并且可能由于某个节点阻塞导致程序崩溃，但这不会提示语法错误的，debug很难。还有就是在不同的机器上传递消息，可能有很多无聊的打包拆包代码的过程。

2. 计算单元

  这一部分其实主要了解一些关于CPU和GPU的常识就好。

• 用来测试计算机/系统性能的程序叫做benchmark，benchmark要能够代表这台机器或这个系统的设计需求，比如需求是设计一台科学计算的电脑，那benchmark肯定就是去做大量复杂的矩阵运算。
• 一般用来衡量CPU性能的指标是MIPS，对于超算来说，是FLOPS，因为处理的数量级更大。注意，FLOPS是衡量硬件效率的指标，可以理解为计算速度，而FLOPs表示计算量，是用来衡量算法/模型复杂度的指标，许多神经网络就需要计算FLOPs。
• 一般来说CPU核数越高，主频越低，因为很多人去做一件事，每个人都不需要那么卖力了。不过这就是一个经验，有厂家想做一个高核数高主频的片也是完全没问题的。
• GPU是一种流处理器（stream processor，or a vector processor）。

3. 网络拓扑

  分布式系统设计面临的三大问题：计算、存储、通信，同样是并行计算面临的难题。通信甚至对并行程序的性能影响最大，因为相较于存储和计算速度，网络通信速度是最慢的。需要知道以下衡量网络拓扑质量的参数：

• Diameter：衡量一个网络的延迟，所谓Diameter，直译为直径。链表中就是n-1，环形链表中是n/2，树中是2logn，这就很好理解了。Diameter越小越好。
• Bisection：衡量一个网络的可靠性，即断开这个网络中的多少条边，会彻底将其分成两部分。链表中是1，环形链表中是2。Bisection越大越好。
• Degree：衡量一个网络的可扩展性，即一个节点可以与几个节点相连。在链表和环形链表中都是2，树中是3.
• Links：衡量一个网络的物理开销，即一个网络内一共存在多少条连接。链表中是n-1，环形链表中就是n，在树中就是(2n-1)。

  网络设计不是本课程的重点，因此只需要了解一些相关常识：

• 2-D Mesh、2-D Torus、Hypercube等高维拓扑通常都有良好的参数和性能，只是Links可能也会更高。

4. 并行程序分析