并行复习笔记（1） - Max.C的博客

第一讲：并行计算概览

内容要点：

什么是并行计算

并行计算的优势

并行计算的主要用途

并行计算的主要推动力

并行计算的粒度

并行编程的难点

Amdahl Law计算

1、基本概念

并行计算可以简单定义为同时利用多个计算资源解决一个计算问题

程序运行在多个 CPU 上；
一个问题被分解成离散可并发解决的小部分；
每一小部分被进一步分解成一组指令序列；
每一部分的指令在不同的 CPU 上同时执行；
需要一个全局的控制和协调机制；

可并行的计算问题

可分解成同时计算的几个离散片段；
在任意时刻可同时执行多条指令；
多计算资源所花的时间少于单计算资源；

计算资源

一般为：

具有多处理器／多核的单台主机；
通过网络连接的若干数量的主机

2、并行计算的优势

在自然界，很多复杂的、交叉发生的事件是同时发生的，但是又在同一个时间序列中；
与串行计算相比，并行计算更擅长建模、模拟、理解真实复杂的现象；
节省时间和花费
- 理论上，给一个任务投入更多的资源将缩短任务的完成时间，减少潜在的代价；
- 并行计算机可以由多个便宜、通用计算资源构成；
解决更大／更复杂问题：很多问题很复杂，不实际也不可能在单台计算机上解决。
实现并发处理：单台计算机只能做一件事情，而多台计算机却可以同时做几件事情（例如协作网络，来自世界各地的人可以同时工作）
利用非本地资源：当本地计算资源稀缺或者不充足时，可以利用甚至是来自互联网的计算资源。
更好地发挥底层并行硬件
1. 现代计算机甚至笔记本都具有多个处理器或者核心；
2. 并行软件就是为了针对并行硬件架构出现的；
3. 串行程序运行在现代计算机上会浪费计算资源；

3、并行计算的用途

科学与工程计算
- 大气、地球、环境
- 核能、粒子模拟、高分子
- 生物科技、遗传学
工业和商业应用
- 大数据、数据挖掘
- 石油勘探
- 搜索引擎
- 医学图像处理
全球范围的应用

4、并行计算发展的驱动力

并行计算驱动力可分为两大方面：应用发展趋势和构架发展趋势。

（1）应用发展趋势

在硬件可达到的性能与应用对性能的需求之间存在正反馈（Positive Feedback Cycle）：应用需求提升促进硬件性能提升，反之提高性能需求。

大量用户、设备、内容涌现，大数据时代：

云计算兴起
应用种类繁多
负载异构型增加

（2）架构发展趋势

发展过程

迄今为止，CPU 架构技术经历了四代即：电子管（Tube）、晶体管（Transistor）、集成电路（IC）和大规模集成电路（VLSI），这里只关注 VLSI。

VLSI 最的特色是在于对并行化的利用，不同的 VLSI 时代具有不同的并行粒度：

bit 级并行
指令集并行
线程水平的并行

其中，有摩尔定律支持芯片行业的发展：「芯片上的集成晶体管数量每 18 个月增加一倍」。

发展趋势的变化

发展趋势不再是高速的 CPU 主频，而是「多核」。（摩尔定律失效的原因之一）

（3）如何提高 CPU 的处理速度

1990 年之前的解决方式

增加时钟频率（扩频）
1. 深化流水线（采用更多／更短的流水阶段）
2. 芯片的工作温度会过高
推测超标量（Speculative Superscalar, SS）多条指令同时执行（指令级的并行，ILP）：
1. 硬件自动找出串行程序中的能够同时执行的独立指令集合；
2. 硬件预测分支指令；在分支指令实际发生之前先推测执行；

局限：最终出现「收益下降（diminishing returns）」

这种解决方法的优点：程序员并不需要知道这些过程的细节

2000 年之后的解决方式

时钟频率很难增加；
SS 触到天花板出现「收益下降」；
利用额外的额外的晶体管在芯片上构建更多／更简单的处理器；

后来发展，延申出了并行计算机和并行计算集群。

5、并行计算机

从硬件角度来讲，今天的单个计算机都是并行计算机，主要体现为：

多个功能单元（L1 Cache、L2 Cache、Branch、Prefetch、GPU 等）；
多个执行单元或者核心
多个硬件线程

并行计算集群

多个单独的计算机通过网络连接起来形成计算集群

LLNL 并行计算集群

每个节点都是一个多处理器并行机；
多个计算节点通过 Infiniband 网络连接；

Moore’s law 新解

每两年芯片上的核心数目会翻倍；
时钟频率不再增加，甚至是降低；
需要处理具有很多并发线程的系统；
需要处理芯片内并行和芯片之间的并行;
需要处理异构和各种规范（不是所有的核都相同）；

最后得出结论，需要程序员学会并行编程。

6、并行编程

并行编译器局限

编译器仅做到了有限的并行检测和程序转换；

需要程序员手动进行并行编程。

并行编程难点

找到尽可能多的并行点；
并行粒度：函数及、线程级、进程级；
局部性：并行后能否使用局部数据；
负载均衡;
协作与同步；
性能模型；

与串行编程比较

代价不同、优势不同；
需要不同的算法；
需要利用不同问题的抽象；
更为复杂；
难以控制不同组件之间的交互；
掌握更多编程工具；

并行程序：任务并行（计算密集型）、数据并行（数据密集型）

7、Amdahl’s Law

用于度量并行程序的加速效果：

$Speedup = \frac{1thread\, execution \, time }{n\, thread \, execution \, time}\ $

$Speedup = \frac{1}{(1-p)+p/n}$

其中，p 表示程序可并发的部分占整个程序的比例。\

应用程序只有一部分进行并行；
大量串行代码降低并行性能；

第二讲：并行架构

1、Flynn’s Taxonomy（费林分类）

高效能计算机的分类方式：根据资讯流（information stream）可分成指令（Instruction）和数据（Data）两种。据此又可分成四种计算机类型：SISD, SIMD, MISD, and MIMD.

注意：费林分类是划分计算机的，不是划分CPU的。

SISD Architecture

例如：单核计算机

SIMD Architecture:单指令多数据流

例子：vector processor,GPUs

延申：SPMD,对称多处理器

MISD Architecture

多指令单数据流

MIMD Architecture 多指令多数据流

例子：现代并行系统

2、单处理器并行(Uniprocessor Parallelism)

指令级并行的技术

（流水线）Pipelining: Overlapping individual parts of instructions
（超标量执行）Superscalar execution: Do multiple things at same time
VLIW: Let compiler specify which operations can run in parallel
（向量处理）Vector Processing: Specify groups of similar (independent) operations
（乱序执行） Out of Order Execution (OOO): Allow long operations to happen

流水线技术

限制

Overhead prevents arbitrary division (最小可划分部分的时间)
- Cost of latches (between stages) limits what can do within stage（锁存的成本（阶段之间）限制了阶段内的功能）
- Sets minimum amount of work/stage（设置了最小任务）
Hazards prevent next instruction from executing during its designated clock cycle（结构竞争、数据竞争、控制竞争）
- 结构 Structural hazards: Attempt to use the same hardware to do two different things at once（使用同一硬件）
- 数据 Data hazards: Instruction depends on result of prior instruction still in the pipeline（指令依赖的数据还在流水线中）
- 控制 Control hazards: Caused by delay between the fetching of instructions and decisions about changes in control flow (branches and jumps)（跳转、分支造成的阻塞）
超标量增加了竞争现象的发生
- 更多冲突的指令（时钟周期）

乱序执行 Out-of-Order (OOO) Execution

允许指令在阻塞后继续执行，动态调度指令。

预测执行

利用处理器的空闲时间提前执行一些将来 “可能用得上，但也可能被放弃” 的计算（包括分支预测、预读内存和文件数据），从而极大提升系统的整体运行速度。

推测分支结果、依赖关系、甚至值

如果正确，则不需要为结果而暂停→提高性能
如果不正确，则浪费时间和功率
- 如果猜测错误，必须能够撤销一个结果
问题：猜测的准确性随着流水线中同时出现的指令数量的增加而降低
巨大的复杂性：多个组件的复杂度可以扩展为$n^2$、功耗大。

向量处理：VECTOR PROCESSING/SIMD

SIMD 架构

中央控制器广播指令给处理单元：Central controller broadcasts instructions to multiple processing elements (PEs)
- 只需一个中央控制器 Only requires one controller for whole array
- 只需要内存存程序的一份代码 Only requires storage for one copy of program
- 计算异步 All computations are fully synchronized
GPU（图形处理单元）有SIMD属性；
但是，也有多核行为，所以存在SIMD和MIMD的混合；

3、多线程技术 MULTITHREADING:INCLUDING PTHREADS

POSIX Threads

定义：Portable Operating System Interface for UNIX（UNIX的可移植操作系统接口）

特点：共享堆，不共享栈；不支持显式通信，因为共享内存是隐式的。

**线程调度：Thread Scheduling **

调度实现方式：

多道程序设计 Multitasking operating system
硬件多线程
切换线程的时机

超线程「Simultaneous Multithreading」

定义：既有多线程，又有指令级的并行

可以更好的占用处理器资源

4、内存系统 UNIPROCESSOR MEMORY SYSTEMS

内存的限制

Memory system, and not processor speed, is often the bottleneck for many applications.（内存系统，而不是处理器速度，往往是许多应用程序的瓶颈）
Memory system performance is largely captured by two parameters, latency and bandwidth.（内存系统性能主要由两个参数来获取，延迟和带宽。）
Latency is the time from the issue of a memory request to the time the data is available at the processor.（从发出内存请求到数据在处理器上可用的时间）
Bandwidth is the rate at which data can be pumped to the processor by the memory system（内存系统将数据泵送到处理器的速率）

局部性原理 Principle of Locality

定义：

Program access a relatively small portion of the address space at any instant of time（程序在任何时刻访问地址空间的一小部分）

时间局部性
空间局部性

分级存储 Memory Hierarchy

缓存对性能影响巨大
- 不考虑内存层次就不能考虑性能
简单程序的实际性能可能是体系结构的复杂功能
- 体系结构的微小变化或程序的性能显著改变
- 要编写快速的程序，需要考虑体系结构
- 我们需要简单的模型来帮助我们设计高效的算法
提高缓存性能的常用技术，称为分块或平铺
- 思想：用分而治之的方法定义一个适用于寄存器/L1缓存/L2缓存的问题
自动调整：通过实验处理复杂性
- 生成几种不同版本的代码
- 可以（原则上）在复杂的设计选项中进行优化

命中率，内存延迟

5、并行架构：WHAT IS PARALLEL ARCHITECTURE

Machines with multiple processors（多核心计算机）
A parallel computer is a collection of processing elements that cooperate to solve large problems fast Some broad issues（并行计算机是一组处理元素的集合，它们合作快速地解决一些大的问题）
Resource Allocation（资源分配）
- 一个集合有多大
- 元素的计算力如何
- 有多少内存
Data access, Communication and Synchronization（数据访问、通信、同步）
Performance and Scalability（性能和可扩展性）

并行领域：A PARALLEL ZOO OF ARCHITECTURES

MIMD Machines

定义：Multiple Instruction, Multiple Data (MIMD)
通信方式：
- Shared memory: Communication through Memory（共享内存）
- Message passing: Communication through Messages（消息传递）

对于大多数机器来说，共享内存建立在消息传递网络之上

共享内存
分布式内存
集群

内容要点

1. Flynn’s 并行架构分类

基于指令流和数据流数量的计算机体系结构分类

2. 什么是 pipeline

Pipelining

流水线有助于提高带宽而不是降低时延

带宽受限于最慢的流水线阶段

加速潜力 = 流水线级数

MIPS 流水线的 5 个阶段：Fetch->Decode->Execute->Memory->Write Back

流水线 CPI < 1

流水线的限制

3. 有哪些形式的指令级并行

单处理器计算机体系结构如何提取并行性?

通过在指令流中查找并行性，称为「指令级并行」，向程序员隐藏并行性。

指令级并行的例子

流水线：指令的各个部分重叠

超标量执行：同时执行多个操作

VLIW（极长指令字）：让编译器指定哪些操作可以并行运行

向量处理：指定相似的操作组

乱序执行：允许长时间操作

现代指令级并行的特点

动态调度，乱序执行

获取一堆指令，确定它们的依赖性并尽可能消除其依赖性，将它们全部扔到执行单元中，向前移动指令以消除指令间的依赖性。

如同按顺序执行

预测执行

预测分支的结果，若猜测错误必须能够撤销结果

预测的准确性随着流水线中同时运行的指令数量增加而降低

巨大的复杂性

许多组件的复杂性按 n² 来衡量

4. 什么是 Pthreads

线程级并行

指令级并行利用循环或直线代码段内的隐式并行操作

线程级并行显式地表示为利用多个本质上是并行的线程执行

线程可被用于单处理器或多处理器上

并发和并行

并发性是指两个任务可以在重叠的时间段内启动、运行和完成。不一定意味着他们两个都会在同一时刻运行.例如在单线程机器上执行多任务。

并行性是指任务同时运行，例如多核处理器。

POSIX 线程概述

POSIX: Portable Operating System Interface for UNIX

Pthread: The POSIX threading interface

Pthread 包括支持创建并行性、同步，不显式支持通信，因为共享内存是隐式的；指向共享数据的指针传递给线程。

只有堆上的数据可共享，栈上的数据不可共享。

数据共享和线程

在 main 之外声明的变量是共享的

可以共享堆上分配的对象（如果指针被传递）

栈上的变量是私有的，将指向这些变量的指针传递给其他线程可能会导致问题

通常通过创建一个大的「线程数据」结构体来完成，该结构体作为参数传递到所有线程中

ILP 和 TLP 的联系

在为 ILP 设计的数据路径中，由于代码中的阻塞或依赖关系，功能单元通常处于空闲状态。

TLP 用作独立指令的来源，在暂停期间可能会使处理器繁忙。

当 ILP 不足时，TLP 被用于占用可能闲置的功能单元。

5. 内存局部性原则有哪些

内存系统性能的限制

内存系统，而不是处理器速度，往往是许多应用程序的瓶颈。

内存系统性能主要由两个参数（延迟和带宽）影响。

延迟（Latency）是指从发出内存请求到处理器提供数据的时间。

带宽（Bandwidth）是存储系统将数据泵送到处理器的速率。

局部性原则

程序在任何时刻访问相对较小的地址空间。

时间局部性：如果一个项被引用，它很快就会再次被引用（例如循环、重用）。

空间局部性：如果引用了某个项，则其地址接近的项很快就会被引用（例如，直线代码、数组访问）。

局部性原则的优点

以最便宜的技术呈现尽可能多的内存。

以最快的技术提供的速度提供访问。

6. 内存分层

7. Caches 在内存分层结构中的重要作用

缓存是处理器和 DRAM 之间的小型快速内存元素。作为低延迟高带宽存储，如果重复使用一条数据，缓存可以减少该内存系统的有效延迟。

缓存满足的数据引用部分称为缓存命中率。由存储系统上的代码实现的缓存命中率通常决定其性能。

8. 新型存储系统的构成

9. 什么是并行架构

并行结构一般是指并行体系结构和软件架构采取并行编程。主要目的是使更多任务或数据同时运行。并行体系结构是指许多指令能同时进行的体系结构；并行编程一般有以下模式：共享内存模式；消息传递模式；数据并行模式。

并行计算机是一组处理元素的集合，它们协同快速地解决一些大问题。

10. MIMD 的并行架构包括哪些实现类型

对称多处理器：内置多个处理器，共享内存通信，每个处理器运行操作系统的拷贝，例如现在的多核芯片。

通过主机的独立 I/O 的非统一共享内存：多处理器，每个都有本地内存，通用可扩展网络，节点上非常轻的 OS 提供简单的服务，调度/同步，用于 I/O 的网络可访问主机。

集群：多台独立机接入通用网络，通过消息沟通。