并行硬件和软件

1. 概述

并行程序设计：将大任务分解为多个可同时执行的子任务，从而利用多核处理器或多台计算机实现更高效的计算

计算类型

并行程序：专门设计用来在并行系统上运行的程序，从而可以充分发挥多核性能

并行系统：在单个芯片上放置多个相对简单的处理器形成的集成电路

并行扩展

类型	用途	特点
消息传递接口（Message-Passing Interface, MPI）	用于分布式内存系统，通过消息传递进行进程间通信	适合大规模并行计算，但需要显式管理通信导致编程相对复杂
POSIX线程（Pthreads）	用于共享内存系统，通过线程实现并行计算	能够细粒度控制并行执行，但需要实现同步和互斥
OpenMP	用于共享内存系统，基于编译器指令的方式实现并行化	适合逐步并行化现有的串行代码，但实现十分复杂

冯诺依曼体系：CPU 通过读取主存中的指令和数据来执行任务，计算机按照取指-译码-执行-存储这一顺序循环执行

指令级并行（Instruction-Level Parallelism, ILP）：在同一时间内执行多条指令

线程级并行（Thread-Level Parallelism, TLP）：在同一时间内执行多个线程

硬件多线程（Hardware Multithreading, HMT）：处理器支持在硬件层面管理和切换多个线程，使得当一个线程阻塞时，其他线程可以继续执行
同步多线程（Simultaneous Multithreading, SMT）：允许多个线程同时共享和利用处理器的各个执行单元

TLP提供的是粗粒度的并行性，ILP提供的是细粒度的并行性

类型	定义	特点	适用
单指令多数据流系统（Single Instruction Multiple Data, SIMD）	一个控制单元向多个算术逻辑单元广播同一条指令，各 ALU 分别在不同的数据上执行这条指令	指令同步执行，数据并行	向量处理器，图像处理单元
多指令多数据流系统（Multiple Instruction Multiple Data, MIMD）	每个处理单元都有自己的控制单元和算术逻辑单元，可以独立执行不同的指令流，对各自的数据进行操作	独立运行，异步运行	共享内存系统、分布式内存系统

共享内存互连网络

分布式内存互连网络

单程序多数据流（Single Program Multiple Data, SPMD）：所有进程或线程运行同一份程序代码，但在不同的数据子集上工作

方式

加速比（Speedup）：是串行执行时间与并行执行时间的比值， $S(p) = \frac{T_{\text{串行}}}{T_{\text{并行}}}$ ，其中 p 是核的数量

不可能获得线性加速比即 S 不可能等于 p

效率 (Efficiency)：反映了并行系统中每个处理单元在加速比中所发挥的贡献， $E(p) = \frac{S(p)}{p} = \frac{T_{\text{串行}}}{p \times T_{\text{并行}}}$

效率较低表明并行化过程中存在较多额外开销或者负载不均

问题规模越大，加速比和效率增加：随着问题规模变大，额外开销时间比串行执行时间增长得慢，线程需要花费更多精力做任务，而协调进程/线程到工作的时间就相对变少了

阿姆达尔定律：除非一个串行程序全部都并行化，否则不论有多少核，并行度有多高，串行部分都会成为性能提升的瓶颈，所产生的加速比具有上限，即如果只有 F% 实现了理想并行化，那么最大加速比为 $S_{\max} = \frac{1}{1-F}$

可扩展性：程序在增加进程或线程数的同时，如果问题规模也按相同比例增长，程序的效率或性能提升能够保持稳定不变