并行计算（2月12日）

串行计算 serial computing

一个问题是由一系列指令完成，指令依次执行，只需要一个处理器，一个时间点只有一条指令执行

并行计算 paralle computing

一个问题分解成不同部分，每个部分由一系列指令构成，需要多个处理器，需要一个总体调控机制

并行计算有要求：计算问题可分，可以同时执行，可以随时执行多条指令，并行计算的时候，确保使用并行要快于串行

stand-alone computers

一个独立电脑，多个功能单元、多个执行单元，多个硬件线程

经过网络连接多个计算机/计算结点建立起来非常大的并行计算集群

为什么用并行计算？

节省时间/金钱

解决更大、更复杂的问题

提供并行

充分利用非本地资源

充分挖掘并行硬件的能力

并行计算用在哪？科学研究、工程应用、商业（大数据）

概念和术语：

冯诺依曼体系：匈牙利，1945年首次提出，沿用至今天，内存、控制，算术逻辑单元、IO

Flynn's Classification ：SISD、SIMD、MISD、MIMD 指令、数据两个维度

超级计算/高性能计算

节点：一个独立的盒子里的电脑，通常由多个CPU/处理器核心，存储器，网络接口等组成，节点联网在一起构成超级计算机

CPU/插槽/处理器核心：

任务：逻辑上离散计算的工作部分

流水线：

共享内存：

堆成多处理器（SMP）

分布式内存：

通讯：

同步：

粒度：

观察加速：观察到已经并行化的代码的加速

并行开销：任务启动时间、同步、数据通信、并行语言、库、OS等引起的软件开销、任务终止时间

大规模并行

可扩展性

并行编程的局限和开销

amdahl‘s Law 加速比由可并行化的代码来决定

1987 —— Gustafsun's Law

1993 —— Sun-Li

并行程序的可移植性问题：

Strong scaling（Amdahl’s law，阿姆达尔定律）

speedup= 1 / ( s + p / N ) 1/(s+p/N) 1/(s+p/N)，其中s是可以不能并行计算的部分所用时间的比例，p是可以并行部分所用时间的比例，N是处理器个数。

该定律描述的是在问题规模一定时，增加计算资源时的scaling能力。

Weak scaling:（Gustafson’s law，古斯塔夫森定律）

speedup= s + p ∗ N s+p*N s+p∗N，参数意义同3。

该定律描述的是在问题规模和计算资源同时增加时的scaling能力。

内存架构模式：

共享内存：

UMA：Uniform Memory Access

NUMA：Non-Uniform Memory Access

分布式存储：

Hybird Distributed-Shared Memory混合分布式共享内存