【并行与分布式计算】复习笔记 LeeRinji

本笔记为合作笔记,各讲内容分别由下述成员完成:

第一讲:并行计算概览,内容要点

并行计算主要研究下面几个方面的内容

  1. 并行架构
  2. 并行算法
  3. 并行编程
  4. 并行性能
  5. 并行应用

相关基本概念

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

可并行的计算问题

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

计算资源

一般为:

  1. 具有多处理器/多核的单台主机;
  2. 通过网络连接的若干数量的主机

并行计算的优势

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

并行计算发展的驱动力

应用发展趋势

在硬件可达到的性能与应用对性能的需求之间存在正反馈(Positive Feedback Cycle)

大数据时代

架构发展趋势

发展过程

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

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

其中,有摩尔定律支持芯片行业的发展:“芯片上的集成晶体管数量每 18 个月增加一倍”

发展趋势的变化

发展趋势不再是高速的 CPU 主频,而是“多核”。(摩尔定律失效的原因之一)

如何提高 CPU 的处理速度

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

局限:最终出现“收益下降(diminishing returns)” 这种解决方法的优点:程序员并不需要知道这些过程的细节

2000 年之后的解决方式
  1. 时钟频率很难增加;
  2. SS 触到天花板出现“收益下降”;
  3. 利用额外的额外的晶体管在芯片上构建更多/更简单的处理器;

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

并行计算机

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

并行计算集群

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

LLNL 并行计算集群

Moore’s law 新解

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

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

Amdahl’s Law

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

\[Speedup = \frac{1thread\, execution \, time }{n\, thread \, execution \, time}\\ Speedup = \frac{1}{(1-p)+p/n}\\\]

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

第二讲:并行架构

并行架构

Flynn’s Taxonomy(分类法)

定义:一种并行架构的分类方法

A classification of computer architectures based on the number of streams of instructions and data

1561360604887

SISD Architecture

1561360717822

例如:单核计算机

SIMD Architecture:单指令多数据流

1561360792439

例子:vector processor,GPUs

1561360831768

延申:SPMD,对称多处理器

MISD Architecture

多指令单数据流

1561360975918

MIMD Architecture 多指令多数据流

1561361015494

单处理器并行(Uniprocessor Parallelism)

引入

How do uniprocessor computer architectures extract parallelism?

早期的目标

Goal of Computer Architects until about 2002:

Examples of ILP techniques 指令级并行的技术

流水线技术

Limits to Pipelining

  1. Overhead prevents arbitrary division (最小可划分部分的时间)
    • Cost of latches (between stages) limits what can do within stage
    • Sets minimum amount of work/stage
  2. 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

预测执行

最后得知结论,并行需要暴露给程序员,让软件来实现。

向量处理:VECTOR PROCESSING/SIMD

1. 向量编程模型图解

1561362873614

2. SIMD 架构示意图

1561362907979

多线程技术 MULTITHREADING:INCLUDING PTHREADS

相关概念

Thread Level Parallelism (TLP) :线程级并行

Concurrency vs Parallelism:并发和并行

介绍 POSIX Threads

定义POSIX: Portable Operating System Interface for UNIX

特点:共享堆,不共享栈

**线程调度:Thread Scheduling **

调度实现方式

ILP 与 TLP 关系是什么意思?没看懂

超线程“Simultaneous Multithreading”

定义:既有多线程,又有指令级的并行

超线程,可以更好的占用处理器资源

内存系统 UNIPROCESSOR MEMORY SYSTEMS

内存的限制
内存墙的问题

1561365381115

局部性原理 Principle of Locality
定义:

Program access a relatively small portion of the address space at any instant of time

分级存储 Memory Hierarchy

命中率,内存延迟

多核、多处理器 MULTICORE CHIPS

并行架构?WHAT IS PARALLEL ARCHITECTURE

并行领域:A PARALLEL ZOO OF ARCHITECTURES

MIMD Machines

  1. 定义:Multiple Instruction, Multiple Data (MIMD)

  2. 通信方式:

    • Shared memory: Communication through Memory

    • Message passing: Communication through Messages

For most machines, shared memory built on top of message passing network

举例

Symmetric Multiprocessor

1. Flynn’s 并行架构分类

2.1 SISD 架构:单核计算机 SIMD 架构:向量处理器,GPUs MISD 架构:(没有符合的知名系统。。) MIMD 架构:现代并行系统

2. 什么是 pipeline

  1. 流水线有助于带宽而不是延迟
  2. 带宽受限于最慢的流水线阶段
  3. 加速潜力 = 流水线级数
  4. MIPS 流水线的 5 个阶段:Fetch->Decode->Execute->Memory->Write Back
  5. 流水线 CPI < 1

开销防止任意划分

  1. 阶段之间锁存器的成本限制了阶段内能做什么
  2. 设置最小数量的阶段

冒险阻止下一条指令在其指定的时钟周期内执行

  1. 结构冒险:尝试同时使用相同的硬件执行两个不同的操作
  2. 数据冒险:指令取决于仍在流水线中先前指令的结果
  3. 控制冒险:由于控制流程(分支和跳跃)中的指令和决策获取之间的延迟而造成的

超标量增加的冒险的发生

更多冲突的指令(时钟周期)

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

通过在指令流中查找并行性,称为“指令级并行”,向程序员隐藏并行性。

  1. 流水线:指令的各个部分重叠
  2. 超标量执行:同时执行多个操作
  3. VLIW(极长指令字):让编译器指定哪些操作可以并行运行
  4. 向量处理:指定相似的操作组
  5. 乱序执行:允许长时间操作

动态调度,乱序执行

  1. 获取一堆指令,确定它们的依赖性并尽可能消除其依赖性,将它们全部扔到执行单元中,向前移动指令以消除指令间的依赖性。
  2. 如同按顺序执行

投机执行

  1. 猜测分支的结果,若猜测错误必须能够撤销结果
  2. 猜测的准确性随着流水线中同时运行的指令数量增加而降低

巨大的复杂性

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

4. 什么是 Pthreads

  1. 指令级并行利用循环或直线代码段内的隐式并行操作
  2. 线程级并行显式地表示为利用多个本质上是并行的线程执行
  3. 线程可被用于单处理器或多处理器上
  1. 并发性是指两个任务可以在重叠的时间段内启动、运行和完成。不一定意味着他们两个都会在同一时刻运行.例如在单线程机器上执行多任务。
  2. 并行性是指任务同时运行,例如多核处理器。
  1. POSIX: Portable Operating System Interface for UNIX
  2. Pthread: The POSIX threading interface
  3. Pthread 包括支持创建并行性、同步,不显式支持通信,因为共享内存是隐式的;指向共享数据的指针传递给线程。
  4. 只有堆上的数据可共享,栈上的数据不可共享。
  1. 在 main 之外声明的变量是共享的
  2. 可以共享堆上分配的对象(如果指针被传递)
  3. 栈上的变量是私有的,将指向这些变量的指针传递给其他线程可能会导致问题
  4. 通常通过创建一个大的“线程数据”结构体来完成,该结构体作为参数传递到所有线程中
  1. 在为 ILP 设计的数据路径中,由于代码中的阻塞或依赖关系,功能单元通常处于空闲状态。
  2. TLP 用作独立指令的来源,在暂停期间可能会使处理器繁忙。
  3. 当 ILP 不足时,TLP 被用于占用可能闲置的功能单元。

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

  1. 内存系统,而不是处理器速度,往往是许多应用程序的瓶颈。
  2. 内存系统性能主要由两个参数(延迟和带宽)影响。
  3. 延迟(Latency)是指从发出内存请求到处理器提供数据的时间。
  4. 带宽(Bandwidth)是存储系统将数据泵送到处理器的速率。
  1. 程序在任何时刻访问相对较小的地址空间。
  2. 时间局部性:如果一个项被引用,它很快就会再次被引用(例如循环、重用)。
  3. 空间局部性:如果引用了某个项,则其地址接近的项很快就会被引用(例如,直线代码、数组访问)。
  1. 以最便宜的技术呈现尽可能多的内存。
  2. 以最快的技术提供的速度提供访问。

6. 内存分层

2

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

  1. 缓存是处理器和 DRAM 之间的小型快速内存元素。作为低延迟高带宽存储,如果重复使用一条数据,缓存可以减少该内存系统的有效延迟。
  2. 缓存满足的数据引用部分称为缓存命中率。由存储系统上的代码实现的缓存命中率通常决定其性能。

8. 新型存储系统的构成

3

9. 什么是并行架构

  1. 并行结构一般是指并行体系结构和软件架构采取并行编程。主要目的是使更多任务或数据同时运行。并行体系结构是指许多指令能同时进行的体系结构;并行编程一般有以下模式:共享内存模式;消息传递模式;数据并行模式。
  2. 并行计算机是一组处理元素的集合,它们协同快速地解决一些大问题。

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

  1. 对称多处理器:内置多个处理器,共享内存通信,每个处理器运行操作系统的拷贝,例如现在的多核芯片。
  2. 通过主机的独立 I/O 的非统一共享内存:多处理器,每个都有本地内存,通用可扩展网络,节点上非常轻的 OS 提供简单的服务,调度/同步,用于 I/O 的网络可访问主机。
  3. 集群:多台独立机接入通用网络,通过消息沟通。

11. MPP 架构的典型例子及主要构成

4

第三讲:并行编程模型

引入

开头举了许多并行编程的模型的例子:计算$\pi$

历史

  1. 1970s – early 1990s,并行机由它的并行模型和语言唯一决定。

    Historically (1970s – early 1990s), each parallel machine was unique, along with its programming model and language。

    • 架构(Architecture) = 编程模型(prog. model )+ 通信抽象 (comm. abstraction) + 机器(machine);
    • 并行架构依附于编程模型(parallel architectures tied to programming models);
  2. 并行架构发展迅猛:

    1561646967726

并行编程模型概述

从并行机器架构中分理出并行编程模型

什么是并行编程模型(感觉 ppt 上没有明确定义)

并行编程模型的主要包括哪些类型

并行编程模型主要包括哪几部分

1. Control 控制

2. Naming 变量声明

3. Operations 操作

4. Cost 开销

共享内存模型有哪些实现

1.共享内存的定义

Any processor can directly reference any memory location

2. 特点

3. 优缺点(相对于程序员而言)

4. 实现的两种方式

5. 实现的典型架构举例

1561687499864 1561687518616

共享内存之线程模型

1. 概述

2. 线程的特点

呃……操作系统也学了,不说了

算了还是说一下:

1561688227205

>1 插入内容:造成并行编程模型不能达到理想加速比

>2. 插入内容:Decomposition(解耦)

有下列两种含义:

注意事项:Considerations

3. 任务(Task)和线程(Thread)之间的关系

任务的特点:

1561689552306

任务有静态调度和动态调度。

4. 什么是线程竞争?如何解决

额…RC 问题,还不知道吗?那操作系统挂定了…

RC 问题
死锁

1. 什么是并行编程模型

  1. 历史上(70 年代至 90 年代初),每台并行机都是独一无二的,其编程模型和语言也是独一无二的。架构=程序模型+通信抽象+机器,并行架构与编程模型相关。
  2. 现在,我们将编程模型与底层的并行机器体系结构分离开来。
  3. 主要编程模型有:共享地址空间、消息传递、数据并行;其他类型有:数据流、收缩阵列。
  4. 通过扩展“计算机体系结构”以支持通信与合作。旧:指令集架构;新:通信架构。
  5. 定义:关键抽象、边界和接口;实现接口的组织结构。
  6. 编译器、库和操作系统是重要的桥梁。

2. 并行编程模型主要包括哪些类型,主要特点是什么

  1. 多道程序设计:无通信或同步,在程序级别
  2. 共享地址空间:如公告板
  3. 消息传递:如信件或电话,明确的点到点
  4. 数据并行:对数据进行更严格的全局操作,使用共享地址空间或消息传递实现
  1. 消息传递(message passing):封装本地数据的独立任务,任务通过交换消息进行交互。
  2. 共享内存(shared memroy):任务共享公用地址空间,任务通过异步读写此空间进行交互。
  3. 数据并行化(data parallelization):任务执行一系列独立的操作,数据通常在任务之间均匀分区,也被称为“令人尴尬的并行”。

3. 并行编程模型主要包括哪几部分

  1. 控制:如何创建并行性;应按什么顺序进行操作;不同的控制线程是如何同步的
  2. 命名:什么数据是私有的还是共享的;如何访问共享数据
  3. 操作:什么操作是原子操作
  4. 成本:我们如何计算运营成本

4. 共享内存模型有哪些实现

  1. 任何处理器都可以直接引用任何内存位置,由于加载和存储而隐式发生通信;方便;位置透明度;与单处理器时间共享类似的编程模型。
  2. 在这个编程模型中,任务共享一个公共地址空间,它们异步读写。可以使用各种机制,如锁/信号灯来控制对共享内存的访问。从程序员的角度来看,该模型的一个优点是缺乏数据“所有权”的概念,因此无需明确规定任务之间的数据通信。程序开发通常可以简化。在性能方面的一个重要缺点是,越来越难以理解和管理数据位置。将数据保持在处理器的本地,这样可以节省在多个处理器使用相同数据时发生的内存访问、缓存刷新和总线流量。不幸的是,控制数据位置很难理解,并且超出了普通用户的控制范围。
  1. SAS Machine Architecture
  2. Scaling Up

5. 造成并行编程模型不能达到理想加速比的原因

5

6. 任务和线程之间的关系

  1. 数据分解:将整个数据集分解为更小、离散的部分,然后并行处理它们
  2. 任务分解:根据独立子任务的自然集合划分整个任务
  1. 任务由数据及其进程组成,任务调度程序会将其附加到要执行的线程上。
  2. 任务操作比线程操作便宜得多。
  3. 通过窃取轻松平衡线程之间的工作量。
  4. 任务适合列表、树、地图数据结构

任务比线程多

  1. 更灵活地安排任务
  2. 轻松平衡工作量

任务中的计算量必须足够大,以抵消管理任务和线程的开销。

静态调度

任务是独立函数调用的集合,或者是循环迭代

动态调度

任务执行长度可变且不可预测 可能需要一个额外的线程来管理共享结构以保存所有任务

7. 什么是线程竞争,如何解决

  1. 线程之间“竞争”以获取资源;执行令被假定,但不能保证;存储冲突最常见;多个线程并发访问同一内存位置,至少有一个线程正在写入;可能在任何时候都不明显
  2. 注意事项:互斥和同步、临界区、原子操作
  1. 两个或多个线程等待彼此释放资源;一个线程等待一个永远不会发生的事件,比如挂起的锁。
  2. 注意事项:始终按相同顺序锁定和解除锁定,并尽可能避免层次结构;使用原子操作
  1. 它在多个线程同时执行期间正常工作。
  2. 非线程安全标志 访问全局/静态变量或堆 分配/重新分配/释放具有全局范围(文件)的资源 通过句柄和指针间接访问
  3. 注意事项

任何更改的变量必须是每个线程的本地变量 例程可以使用互斥来避免与其他线程冲突

  1. 所有线程以相同的方式处理数据,但一个线程分配了更多的工作,因此需要更多的时间来完成它并影响整体性能。
  2. 注意事项

使内环平行

向细粒倾斜 选择合适的算法 分而治之,master and work, work-stealing

  1. 较大实体的细分程度,粗粒意味着越来越少的成分,细粒度意味着越来越小的成分
  2. 注意事项:细粒度将增加任务调度程序的工作量;粗粒度可能导致工作负载不平衡;设定适当粒度的基准
  1. 保护共享数据并确保任务按正确顺序执行,使用不当会产生副作用
  2. 注意事项

选择适当的同步原语 使用非锁定锁 降低锁粒度 不要做一个锁中心 为共享数据引入并发容器

第四讲:并行编程方法论

什么是增量式并行化

Culler 并行设计流程

主要分四个步骤:(Decomposition)解耦、(Assignment)分派、(Orchestration)配置、(mapping)映射。

图解如下:

1561854072547

1. Decomposition

定义

Break up problem into tasks that can be carried out in parallel.

核心思想、目的

创建最少任务且使得所有的机器上的执行单元都处于忙碌状态

关键方面

识别出依赖部分。(identifying dependencies)

负责的对象

一般是程序员来做这件事情。

2. Assignment

定义

分发任务给线程。

目标

负载均衡,减少通信开销。

特点

静态动态皆可,一般需要程序员来负责,也有非常多语言可以自动对此负责。

3. Orchestration(配置)

定义
目的

减少通信和同步的开销,保护数据的局部性,减少额外开销(overhead).

4. Mapping

定义

Mapping “threads” to hardware execution units.

执行对象

Foster 并行设计流程

分为四个部分:

图解:

1561857076709

1. 分解

定义

Dividing computation and data into pieces

三种不同实现方式及目的
Exploit data parallelism(实现数据并行)
Exploit task parallelism(实现任务并行)
Exploit pipeline parallelism(实现流水并行)
方式之一: Domain Partitioning (按域 / 数据分解)
过程
举例
方式之二:Functional (Task) Decomposition
过程
举例
方式之三:Pipelining
过程
举例
分解注意的问题

2. 通信 Communication

定义:

Determine values passed among tasks

分类:

注意事项

3. Agglomeration (整合、归并)

定义

Grouping tasks into larger tasks(小任务变大任务)

目标和意义

在消息传递型的编程模型中:In message-passing programming, goal often to create one agglomerated task per processor.

4. Mapping(映射)

定义

把任务分配到处理器上的过程:Process of assigning tasks to processors

目标矛盾
决策(树)

分两种情况:静态任务和动态任务

决策树如下:

1561861259361

并行设计举例——边界值-散热问题

第四讲:并行编程方法论,内容要点

  1. 什么是增量式并行化? Study a sequential program (or code segment) 研究串行程序(代码段) Look for bottlenecks & opportunities for parallelism 寻找并行性的瓶颈和机会 Try to keep all processors busy doing useful work 尽量让所有的处理器做有用的工作

  2. Culler 并行设计流程?

  3. Foster 并行设计流程? Partitioning(划分) communication(通信) Agglomeration(归并,组合) mapping(聚合)

  4. 按数据分解和按任务分解的特点? Exploit data parallelism 利用数据并行性 (Data/domain partitioning/decomposition) Divide data into pieces 将数据分成几部分 Determine how to associate computations with the data 确定如何将计算与数据相关联

    Exploit task parallelism 利用任务并行性 (Task/functional partitioning/decomposition) Divide computation into pieces 将计算任务分成几部分 Determine how to associate data with the computations 确定如何将数据与计算关联

  5. 并行任务分解过程中应该注意的问题有哪些? First, divide tasks among processors Second, decide which data elements are going to be accessed (read and/or written) by which processor

  6. 整合的意义是什么? Improve performance 提高性能 Maintain scalability of program 保持程序的可扩展性 Simplify programming (reduce soft ware engineering costs) 简化编程(降低软件成本)

  7. Mapping(映射)如何决策?
  8. 熟悉一些并行设计的例子。

第五讲:OpenMP 并行编程模型,内容要点

什么是 OpenMP

short version:Open Multi-Processing 开放多处理过程 long version: Open specifications for Multi-Processing via collaborative work between interested parties from the hardware and software industry, government and academia

OpenMP is an explicit (not automatic) programming model, offering the programmer full control over parallelization 一种显式(非自动)编程模型,为程序员提供对并行化程序的控制

OpenMP 的主要特点是什么

OpenMP programs accomplish parallelism exclusively (仅仅) through the use of threads 通过对线程的使用来完成程序的并行化

熟悉 OpenMP 的关键指令

#pragma omp parallel // 表明之后的结构化代码块被多个线程处理
#pragma omp parallel num_threads(thread_count) // 可自定义线程数量
omp_get_thread_num
omp_get_num_threads
#pragma omp critical // 只有一个线程能够执行对应代码块,并且第一个线程完成操作前,没有其他的线程能够开始执行这段代码
#pragma omp parallel for // parallel for 指令生成一组线程来执行后面的结构化代码块(必须是for循环)。

熟悉 OpenMP 关键指令的执行过程

第六讲:OpenMP 中的竞争和同步,内容要点

OpenMP 中为了保证程序正确性而采用哪些机制

barriers(障碍,屏障) memory fence(内存屏障) mutual exclusion(互斥)

什么是同步,同步的主要方式有哪些

The process of managing shared resources so that reads and writes occur in the correct order regardless of how the threads are scheduled 用户进程共享资源让读和写的操作以正确的顺序发生,无论线程是如何安排。

barriers mutual exclusion pthread_mutex_lock

OpenMP Barrier 的执行原理

A synchronization point at which every member in a team of threads must arrive before any member can proceed

OpenMP 中竞争的例子

double area, pni, x;
int i, n;
area = 0.0;
for (i = 0; i <n; i++) {
x = (i + 0.5)/n;
area += 4.0/(1.0 + x*x);
}
pi = area / n;

如果两个线程同时执行 area += 4.0/(1.0 + x*x);可能会在一个线程更新 area 的值之前另一个线程就对 area 进行读操作

- 这个for循环的并行会导致竞争的发生,原因是因为多个线程对同一个共享变量访问时间的非确定性导致结果可能出错,多个线程访问area += 4.0 / (1.0 + x*x)就可能导致竞争
```C
    double area, pni, x;
    int i, n;
    ...
    area = 0.0;
    #pragma omp for
    for (i = 0; i <n; i++) {
        x = (i + 0.5)/n;
        area += 4.0/(1.0 + x*x);
    }
    pi = area / n;
```

OpenMP 中避免数据竞争的方式有哪些

Scope variables to be private to threads 设置线程专用的范围变量 如: Use OpenMPprivate clause 使用 openmpprivate 子句 Variables declared within threaded functions 在线程函数中申明变量 Allocate on thread’s stack (pass as parameter) 在线程堆栈上分配(作为参数传递)

Control shared access with critical region 控制关键区域的共享访问 如: Mutual exclusion and synchronization 互斥和同步

- 1. 变量私有化
    - 使用OpenMP的private子句将变量变为私有
    - 在线程函数内声明变量,这样变量将属于这个线程
    - 在线程堆栈上进行分配

- 2、将共享变量放置进入临界区

-   3、互斥访问
    - 信号量
    - 互斥锁机制

OpenMP Critical 与 Atomic 的主要区别是什么

Critical 确保一次只有一个线程执行结构化代码。 atomic 只能用在形如 x = 、x++、x--之类的临界区中,他比普通的临界区执行速度快。

- #pragma omp critical该指令保护了
    1、WorkOne(i)的调用过程,也就是在WorkOne(i)函数内部也是临界区
    2、从内存中找到index[i]值的过程
    3、将WorkOne(i)的值加到index[i]的过程
    4、将内存中index[i]更新的过程
    后面跟的语句相当于串行执行
    ```C
    #pragma omp parallel for
    {
        for(int i = 0; i < n; i++) {
            #pragma omp critical
            x[index[i]] += WorkOne(i);
            y[i] += WorkTwo(i);
        }
    }
    ```

- Atomic指令只对一条指令形成临界区,而且语句的格式收到限制
    1、将WorkOne(i)的值加到index[i]
    2、更新内存中index[i]的值
    只将单一一条语句设置为临界区
    如果不同线程的index[i]非冲突的话仍然可以并行完成
    只有当两个线程的index[i]相等时才会触发使得这两个线程排队执行这条语句
    ```C
    #pragma omp parallel for
    {
        for(int i = 0; i < n; i++) {
            #pragma omp atomic
            x[index[i]] += WorkOne(i);
            y[i] += WorkTwo(i);
        }
    }
    ```

第七讲:OpenMP 性能优化,内容要点

什么是计算效率

核心利用率的衡量标准,计算公式为加速比/核心数

加速比:Speedup = 串行执行时间/并行执行时间

Efficiency(效率)

调整后的 Amdahl 定律如何理解

- 原来的 Amdahl 定律过于乐观

  1. 忽略了并行处理的开销,如创建/终止线程。而并行处理开销一般是关于线程数(核心 数)的增函数。
  2. 忽略了计算量难以均衡地分配到每个核心上,负载不均衡以及核心等待时间都是一种开销。

- 改进后的 Amdahl 定律

    n       问题规模
    p       核心数
    S(n,p)  问题的加速比
    Ts(n)   串行部分的时间花费
    Tp(n)   并行部分的时间花费
    Tr(n,p) 并行开销

    S(n,p)<=( Ts(n)+Tp(n) )/( Ts(n)+Tp(n)/p+Tr(n,p) )

    最大加速比:
    Tp(n)/p:假设并行计算部分可以在核心完美分配
    Tr(n,p)趋向于0

    加速比是关于问题规模的递增函数
- Amdahl太过乐观,很多并行处理开销并没有考虑
    1. 创建和终止线程所花费的时间,这是多线程并行的必须开销。
    2. 工作量在核心之间平均分配,但是在实际运行时,这并不成立,先执行完任务的核心等待时间是另一种形式的开销,即所谓的负载不均衡。

- 所以进行Amdahl公式的改进,加上线程开销部分,  为了获得最大的加速比,我们就需要将并行开销尽可能减小,同时使用更多的核,改进后的公式如下所示
$\psi(n,p) \leq \frac{\sigma(n) + \varphi(n)}{\sigma(n) + \frac{\varphi(n)}{p} + \kappa(n,p)}$
n - 问题规模
p - 核心数
$\psi(n,p)$ - 在问题规模为n核心数为p的情况下并行的加速比
$\sigma(n)$ - 代码串行部分执行时间
$\varphi(n)$ - 代码并行部分执行时间
$\kappa(n,p)$ - 并行开销


- 如下图表示当我们的问题规模达到一定程度后,并行程序的加速比主要由并行部分来决定,因为随着问题规模的增加,程序串行部分也会逐渐较少,同时并行部分将占据主要时间,可以忽略掉串行时间的影响,加速比主要由并行部分决定
![figure1](figure1.png)
![figure2](figure2.png)

OpenMP 中 Loop 调度的几种方式,执行过程

1. Static schedule

2. Dynamic schedule

3. Guided schedule

OpenMP 中 Loop 转换的方式包括哪几种?熟练掌握

1. Loop fission——循环拆分

2. Loop fusion——循环合并

3. Loop exchange(Inversion)——循环交换(反转)

第八讲:MPI 编程模型,内容要点

1. 什么是 MPI 编程模型?

每个独立的处理器(processor)都有独立私有的内存,通过互联网络连接起来的分布式内存系统,利用消息传递来编程的模型。

2. 消息传递性并行编程模型的主要原则是什么?

1. The logical view of a machine supporting the message passing paradigm consists of p processes, each with its own exclusive address space

支持消息传递模型的系统的逻辑由 p 个处理器组成,每个处理器都有自己专用的地址空间

2. CONSTRAINTS(限制)

3. These two constraints, while onerous (繁重), make underlying costs very explicit to the programmer

这两个约束虽然很繁重,但却使底层成本对程序员非常明确。

4. Message-passing programs are often written using the asynchronous or loosely synchronous paradigms

消息传递程序通常使用异步或松散同步的范例编写。

在异步模式中,所有并发任务都是异步执行的。

在松散同步模型中,任务或任务子集同步以执行交互。在这些交互之间,任务完全异步执行

5. Most message-passing programs are written using the single program multiple data (SPMD) model

大多数消息传递程序是使用单程序多数据(SPMD)模型编写的。

3. MPI 中的几种 Send 和 Receive 操作包括原理和应用场景。

1. Non-buffered blocking

2. Buffered blocking

Non-buffered blocking => Buffered blocking

Buffered blocking 的操作

注意:\

a、缓冲区大小可能对性能影响显著
b、由于接受操作块(send-recv)的存在,使用缓冲块仍然可能出现死锁

3. Non-blocking (非阻塞)

4. MPI 的 send

5. Sending and Receiving Messages

相应的数据结构包含

typedef struct MPI_Status {\
int MPI_SOURCE;\
int MPI_TAG;\
int MPI_ERROR; };
int MPI_Get_count(MPI_Status *status, MPI_Datatype datatype, int *count)

4. MPI 中的关键编程接口

MPI_Group_incl():进程集形成一个进程组\
MPI_Comm_create():为新的进程组创建一个通信子\
MPI_Comm_rank():为新的进程组定义序号\
MPI_Comm_free():释放进程组的资源\
MPI_Group_free():解进程组

5. 什么是通信子?

6. MPI 中解决死锁的方式有哪些

7. MPI 中的集群通信操作子有哪些?原理是什么?

int MPI_Barrier(MPI_Comm comm) (阻塞到所有进程完成调用)

The one-to-all broadcast operation is:

int MPI_Bcast(void *buf, int count, MPI_Datatype datatype,
int source, MPI_Comm comm)  The all-to-one reduction operation is:
int MPI_Reduce(void *sendbuf, void *recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, int target,
MPI_Comm comm)
int MPI_Reduce(void *sendbuf, void *recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, int target,
MPI_Comm comm)
  >>>int MPI_Allreduce(void *sendbuf, void *recvbuf,
  >>>int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm
comm)

int MPI_Allgather(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype,MPI_Comm comm)

8 - MPI 编程模型

​ * 可参考文件 MPI.md

  1. 什么是 MPI 编程模型

    MPI - the Message Passing Interface

    * 参考老师 PPT,加粗部分即为重点内容。

    MPI 是一个跨语言(编程语言如 C, Fortran 等)的通讯协议,用于编写并行计算机。支持点对点和广播。MPI 是一个信息传递应用程序接口,包括协议和和语义说明,他们指明其如何在各种实现中发挥其特性。MPI 的目标是高性能,大规模性,和可移植性。MPI 在今天仍为高性能计算的主要模型。与 OpenMP 并行程序不同,MPI 是一种基于信息传递的并行编程技术。消息传递接口是一种编程接口标准,而不是一种具体的编程语言。简而言之,MPI 标准定义了一组具有可移植性的编程接口。

  2. 消息传递并行编程模型的主要原则

    * CH-8 p6

    • 支持消息传递并行编程模型的设备,运行的多个进程应有自己独立的地址空间
    • 限制
      • 每个数据单元必须归属于某一片划分好的地址空间,因此,必须显式划分并分配(place)数据。
      • 无论是只读操作还是读写操作,都需要两个进程进行配合:拥有数据的进程以及操作发起的进程。
    • 消息传递程序常常是异步或者松弛同步(loosely synchronous)的。
      • 松弛同步:任务之间的交互同步进行,此外各个任务异步进行。
    • 绝大多数的消息传递程序是由 single program multiple data - SPMD(单程序多数据流) 模型写的。
  3. MPI 中的几种 Send 和 Receive 操作,包括原理和应用场景。

    * CH-8 p9

    Send 和 Receive 操作可分为以下三大类:

    1. Non-buffered blocking 无缓冲阻塞

      为保证传输安全,需要实现类似于“握手”的操作才能开始发送数据,容易导致空转和死锁

      1561710519522

    2. Buffered blocking 缓冲阻塞

      为了减轻空转和死锁现象,引入缓冲区。

      图片描述

      有通信硬件支持下:发送端不会中断接收方。

      无通信硬件支持下:发送端中断接收方,将数据存入接收端缓冲区。

    3. Non-blocking 非阻塞

      • 非阻塞的协议是不安全的。

      • 通常,非阻塞协议需要与状态检查操作(check-status operation)同步使用。

        参见 MPI_Get_count(), MPI_Status

        typedef struct MPI_Status {
        int MPI_SOURCE;
        int MPI_TAG;
        int MPI_ERROR; };
        
        int MPI_Get_count(MPI_Status *status,
                          MPI_Datatype datatype, int *count)
        
      • 若使用得当,非阻塞的原语能够将通信与有效计算重叠进行。(When used correctly, these primitives are capable of overlapping communication overheads with useful computations.)

      1561711363625

    总体比较:

    1561711504715

  4. MPI 中的关键编程接口

    参见 MPI.md - $2 MPI基本函数

  5. 什么是通信子

    参见 MPI.md - $4 MPI集群通信 - $4.0 组 & 通信子

  6. MPI 中解决死锁的方式有哪些?

    1. 重排代码,避免死锁。
    2. 在发送时,添加接收缓冲区
    3. 自己(发送端)的地址空间作为发送缓冲区。
    4. 使用非阻塞的 send/receive 方法。
  7. MPI 中的集群(群组)通信操作子有哪些?原理是什么?

    MPI 定义了一系列扩展函数以实现集群通信操作,这些操作都是基于一个与通信子关联的群组定义的。通信子中的所有处理器必须调用这些操作。

    参见 MPI.md - $4 MPI集群通信

9 - MPI 与 OpenMP 联合编程(*)

  1. 如何利用 MPI 实现 Matrix-Vector 乘积

    对算式 $Ab=c$,有:

    1. 串行算法

    2. 三种并行算法

      • Row-wise block striped

        1. 将$A$各拆分,$b$不动,各个进程完成两个向量的內积得到$c_i$.
        2. 调用 MPI_Allgatherv(...)聚合计算结果。
        3. MPI_Allgatherv(...)参见 MPI.md - $4 MPI集群通信 - $4.3 多对多通信

        1561798268629

      • Column-wise block striped

        1. 将$A,b$各拆分,各个进程按图示工作。

          1561798901989

        2. 调用 MPI_Alltoall(...)传送计算结果。其中每个进程完成计算后得到上图中$c_{0j},c_{1j},c_{2j},c_{3j},c_{4j}$。最后分组加和。

        3. MPI_Alltoall(...)参见 MPI.md - $4 MPI集群通信 - $4.3 多对多通信

        1561799613528

      • Checkerboard block

        1. 将$A$棋盘化分块,按照行划分同样对 b 进行分段。

          1561800068796

        2. 需要注意,进程数 p 是否为完全平方数影响 b 分块的过程。

        3. 使用 MPI_Dims_create(...) 以及 MPI_Cart_create(...) 新建拓扑关系通信子

        4. MPI_Dims_create(...)MPI_Cart_create(...)参见 MPI.md - $5 MPI 逻辑分划

        5. 规约计算。

    3. 三种算法的性能比较

      1561791325876

  2. MPI 和 OpenMP 结合的优势是什么?

    1561788889804

    1. 运行较只使用 MPI 快。

      • 只使用 MPI 时,消息在m*k 个进程间传递;
      • 联合编程时,消息在m 个含有 k 个线程的进程间传递,代价较低。

      1561789520822

      • 特别地,考虑不同处理器数量的情况:

        • 2,4CPUs:MPI + OpenMP 较慢

          MPI + OpenMP 是共享内存带宽(memory bandwidth)的,MPI-only 不是。

        • 6,8CPUs:MPI + OpenMP 较快

          更低的通信开销。

    2. 程序的更多部分可以并行实现。

      只使用 MPI 时,不涉及消息传递的并行过程无法实现。

    3. 允许更多通信与有效计算的叠加(overlap)。

  3. 如何利用 MPI+OpenMP 实现高斯消元法

    * CH - 9 p53

    0 - 简介

    1. 高斯消元法(Gaussian Elimination )

      • 用于求解系数矩阵$A$是稠密(dense)矩阵的方程$Ax=b$
      • 化简得到三角矩阵系统$Tx=c$,$T$为三角矩阵
      • 回代求解$x$
    2. 稀疏矩阵系统(sparse system)

      • 高斯消元法对稀疏系统的适应性不好。
      • 高斯消元法使得稀疏矩阵新添很多非 0 元素
        • 增加了存储需求
        • 增加了操作次数
    3. 迭代方法(Iterative Methods)

      • 存储需求较高斯消元法更小。
      • 含有 0 元素的计算会被忽略,大大减少了计算量。
    4. 雅各比方法(Jacobi Method)

      1561808109540

    5. 收敛性(Convergence)

      • 一般只能达到较慢的收敛速度,很难实际应用。

    1 - 新方案思想

    • 对 MPI 进行概要分析(?Profile execution of MPI program)。
    • 致力于在计算密集型的函数或代码段处加入 OpenMP 指令。

    2 - 串行代码

    • find_steady_state()

      1561809331250

    • 无法并行执行最外层 for 循环的原因

      • for循环并不是规范形式(canonical form)
      • 包含 break 语句
      • 包含 MPI 功能函数
      • 迭代之间存在数据依赖
    • 并行化本段 for 循环

      1561809619336

      • 处理diff的更新(upadte)与检测(test)
        • 若考虑将if语句置入临界区(critical section),会增加额外开销并且降低加速比。(Putting if statement in a critical section would increase overhead and lower speedup.)
        • 考虑引入私有变量 tdiff
      • 在进行MPI_Allreduce()规约之前,检测tdiff代替之前检测diff的步骤。

    3 - 并行化代码

    1561810275605

    4 - 基准化测试

    考虑以下环境:

    系统:包含 4 个双核处理器节点的商业集群。

    • C+MPI 在 1,2, … ,8 进程上运行
    • C+MPI+OpenMP 在 1,2,3,4 进程上运行
      • 每个进程包含 2 个线程
      • 包含 2,4,6,8 线程

    结果示意:

    1561810989683

    总结分析

    1. Hybrid C+MPI+OpenMP program uniformly faster than C+MPI program.

      混合编程在速度上显著快于 MPI 编程。

    2. Computation/communication ratio of hybrid program is superior.

      混合编程的“计算通信比”更胜一筹。理解为单位通信次数/时间内有效计算量更大。

    3. Number of mesh points per element communicated is twice as high per node for the hybrid program.

      混合编程内每个通信元素的网格点数是程序节点数的两倍。

    4. Lower communication overhead leads to 19% better speedup on 8 CPU.

      混合编程在 8CPU 下通过减少通信开销实现了 19%的加速。

第九讲:MPI 与 OpenMP 联合编程,内容要点

1. 如何利用 MPI 实现 Matrix-vector 乘积?不同实现的特点是什么?

假设运算为 A*b=c,其中 A 为矩阵,b、c 为向量

1. Rowwise Block Striped Matrix —— 行分块条形矩阵

2. Columnwise Block Striped Matrix —— 列分块条形矩阵

3. Checkerboard Block Decomposition —— 块划分

2. MPI 和 OpenMP 结合的优势是什么?

MPI + OpenMP 可以执行的更快

3. 如何利用 MPI+OpenMP 实现高斯消元?

第十讲:GPGPU、CUDA 和 OpenCL 编程模型,内容要点

CUDA 的含义是什么

CUDA: Compute Unified Device Architecture

CUDA:计算统一设备架构

CUDA 的设计目标是什么,与传统的多线程设计有什么不同

Provide an inherently scalable environment for Data-Parallel programming across a wide range of processors (Nvidia only makes GPUs, however)

为跨多种处理器的数据并行编程提供内在可扩展的环境(不过,NVIDIA 只制造 GPU)。

Make SIMD hardware accessible to general-purpose programmers. Otherwise, large fractions of the available execution hardware are wasted!

使 SIMD 硬件对通用程序员可访问。否则,大部分可用的执行硬件都会被浪费掉!

PPT 上没找到很多与传统多线程设计的区别,但我觉得其实就很类似 SIMD 和 MIMD 的区别?(hhh)

Scalability(扩展性)

SIMD Programming

什么是 CUDA kernel

我个人的理解就是运行在设备上的 SPMD 核函数。

一个 kernel 结构如下:Kernel<<<Dg, Db, Ns, S>>>(param1, param2, ...)

CUDA 的编程样例

自己补充:CUDA 的操作概括来说包含 5 个步骤:

  1. CPU 在 GPU 上分配内存:cudaMalloc;
  2. CPU 把数据发送到 GPU:cudaMemcpy;
  3. CPU 在 GPU 上启动内核(kernel),它是自己写的一段程序,在每个线程上运行;
  4. CPU 把数据从 GPU 取回:cudaMemcpy;
  5. CPU 释放 GPU 上的内存:cudaFree。

其中关键是第 3 步,能否写出合适的 kernel,决定了能否正确解决问题和能否高效的解决问题。

CUDA 的线程分层结构

Cuda 对线程做了合适的规划,引入了 grid 和 block 的概念,block 由线程组成,grid 由 block 组成,一般说 blocksize 指一个 block 放了多少 thread;gridsize 指一个 grid 放了多少个 block。

Parallelism in the Cuda Programming Model is expressed as a 4-level Hierarchy

Cuda 编程模型中的并行性被表示为一个 4 层的层次结构。

CUDA Thread

CUDA Warp

Cuda Thread Block

Cuda Grid

Cuda Stream

CUDA 的内存分层结构

CUDA 中的内存访问冲突

Using Per-Block Shared Memory

Atomic Memory Operations

cuda 提供了原生的原子操作,例如

Voluntary Memory Consistency

OpenCL 运行时编译过程

Platform

Running time

资源回收

第十一讲:MapReduce 并行编程模型,内容要点

MapReduce

Some MapReduceTerminology

一些 MapReduce 终端(猜测翻译成专有名词更合适?)。

为什么会产生 MapReduce 并行编程模型

Motivation: Large Scale Data Processing

动机:大规模数据处理。

MapReduce 与其他并行编程模型如 MPI 等的主要区别是什么

MapReduce 的主要流程是什么

Map

Reduce

MapReduce 的简单实现。如 Hello World 例子

使用 python 实现的分词程序。

map.py

import sys
import time
import re

p = re.compile(r'\w+')
for line in sys.stdin:
        ss = line.strip().split(' ')
        for s in ss:
        #time.sleep(1)
        if len(p.findall(s))<1:
            #print s
            continue
        s = p.findall(s)[0].lower()
            if s.strip() != "":
                print "%s\t%s" % (s, 1)

reduce.py

import sys

current_word = None
sum = 0

for line in sys.stdin:
    word, val = line.strip().split('\t')

    if current_word == None:
        current_word = word

    if current_word != word:
        print "%s\t%s" % (current_word, sum)
        current_word = word
        sum = 0
    sum += int(val)
print "%s\t%s" % (current_word, str(sum))

MapReduce 具有哪些容错措施

MapReduce 存在哪些优化点

Optimizations

MapReduce 可以解决的问题有哪些

Greatly reduces parallel programming complexity

Typical Problems Solved by MapReduce

第十二讲:基于 Spark 的分布式计算,内容要点

SPARK 初识

Spark 与 Hadoop 的区别和联系

它扩展了广泛使用的 MapReduce 计算模型。高效的支撑更多计算模式,包括交互式查询和流处理。spark 的一个主要特点是能够在内存中进行计算,及时依赖磁盘进行复杂的运算,Spark 依然比 MapReduce 更加高效。

传统 MapReduce 的主要缺点是什么

MapReduce is great at one-pass computation, but inefficient for multi-pass algorithms. No efficient primitives for data sharing

MapReduce 在单程计算方面很好,但对于多路算法效率较低。没有有效的数据共享原语。

Spark 中的 RDD 如何理解

  1. RDD 是 Spark 的核心数据模型,但是个抽象类,全称为 Resillient Distributed Dataset,即弹性分布式数据集。
  2. RDD 在抽象上来说是一种元素集合,包含了数据。它是被分区的,分为多个分区,每个分区分布在集群中的不同节点上,从而让 RDD 中的数据可以被并行操作。(分布式数据集)
  3. RDD 通常通过 Hadoop 上的文件,即 HDFS 文件或者 Hive 表,来进行创建;有时也可以通过应用程序中的集合来创建。
  4. RDD 最重要的特性就是,提供了容错性,可以自动从节点失败中恢复过来。即如果某个节点上的 RDDpartition,因为节点故障,导致数据丢了,那么 RDD 会自动通过自己的数据来源重新计算该 partition。这一切对使用者是透明的。
  5. RDD 的数据默认情况下存放在内存中的,但是在内存资源不足时,Spark 会自动将 RDD 数据写入磁盘。(弹性)

Spark 样例程序

In this example, we use a few transformations to build a dataset of (String, Int) pairs called counts and then save it to a file.

text_file = sc.textFile("hdfs://...")
counts = text_file.flatMap(lambda line: line.split(" ")) \
             .map(lambda word: (word, 1)) \
             .reduceByKey(lambda a, b: a + b)
counts.saveAsTextFile("hdfs://...")

第十三讲:离散搜索与负载均衡

1. 深度优先搜索的主要流程

从图中某顶点 v 出发: (1)访问顶点 v; (2)依次从 v 的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和 v 有路径相通的顶点都被访问; (3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。(百度)

时间复杂度$\theta(b^k)$, 空间复杂度$\theta(k)$, b 为宽度, k 为深度

2. 深度优先搜索的复杂度

假设状态空间树中的平均分支因子(每个节点的子节点数(平均值))为 b,搜索一棵深度为 k 的树需要检索:7个结点。空间复杂度为 Θ(k)

3. 并行深度优先搜索的主要设计思想

每个处理器处理一个子树

  1. Send nodes near the bottom of the stack(发送堆栈底部附近的结点),适用于均匀搜索空间;分配成本低。
  2. Send nodes near the cutoff depth(发送截止深度附近的结点),使用强启发式(尝试分配搜索空间中可能包含解决方案的部分)可以获得更好的性能。
  3. Send half the nodes between the bottom and the cutoff depth(发送底部和截止深度之间的一半结点),适用于均匀不规则的搜索空间。

4. 动态负载均衡的三种方法,以及每种方法的额外开销复杂度

均衡负载

  1. Asynchronous round robin(ARR),异步循环,每个进程维护一个计数器并以循环方式发出请求。
  2. Global round robin(GRR),全局循环,系统维护一个全局计数器,并以循环方式在全局发出请求。
  3. Random polling(RP),随机轮询,请求随机选择的工作流程。

额外开销复杂度

我们将 v(p)定义为每个处理器在收到至少一个工作请求之后的工作请求总数;假设任意点的最大工作量是 W;则工作请求总数为 O(V(p)logW)。

  1. ARR:V(p) = O(p²)在最坏情况下
  2. GRR:V(p) = p
  3. RP:

    最坏情况下 V(p)是无穷的。 平均状况下 V(p) = O(plogp)

  1. ARR:W = O(p²logp)
  2. GRR:最坏情况下 W = O(p²logp)
  3. RP:W = O(plog²p)
  1. ARR 性能较差,因为它会发出大量的工作请求。
  2. GRR 调度由于计数器上的争用而性能较差,尽管它发出的请求数最少。
  3. RP 是一个理想的折衷办法。

5. 最优搜索的处理过程

6. 并行最优搜索的主要思想的实现方式

7. 什么是加速比异常,主要份哪几类

  1. 由于处理器探索的搜索空间是在运行时动态确定的,实际工作可能会有很大的差异。
  2. 使用 P 处理器产生大于 P 的加速的执行被称为加速异常。使用 P 处理器的小于 P 的加速被称为减速异常。
  3. 加速异常也表现在最佳优先搜索算法中。
  4. 如果启发式函数是好的,那么并行的 best-first 搜索中所做的工作通常比串行搜索中所做的工作要多。

性能优化综合

负载均衡

  1. 负载均衡主要有哪些方式?分别有什么特点?
  2. 静态、动态负载均衡适用的场景是什么?
  3. 如何选择任务的粒度?

理想情况下, 所有处理器在程序运行时同时计算, 并同时结束他们被分派的任务.

问题: 实现更好的负载均衡

静态分派与动态分派

方式

静态分派(Static assignment)
静态负载均衡

在每个线程运行前, 每个线程被分派的任务规模已经被确定. 即预先分派每个线程执行的任务. 这可以在编译期间分派, 也可以在运行期间依据运行参数分派(比如数据大小, 线程数量).

特点
适用场景

任务的开销(执行时间)和任务的数量是可预测的

半静态分派(“Semi-static” assignment)

周期性地进行预测并再动态分派, 在相邻再分配的时间间隔内, 为静态分派

适用场景

任务的开销在较近的未来是可预测的.

动态分派(Dynamic assignment)

程序在运行时动态地分派任务.

适用场景

任务的开销和数量是不可预测的

动态负载均衡的优化

任务的粒度

考虑用工作队列的方式实现动态分派. 一个共享的工作队列, 里面有一些待完成的任务.

1561644969249

worker thread 可以执行两种操作

我们来分析一下任务的粒度对这种动态负载均衡方式的影响

粒度小
粒度大
如何选择任务的粒度

理想的粒度还取决于许多因素.

长尾现象(long pole)

考虑下列任务

1561645738150

如果简单地进行分派, 可能造成负责不均衡

1561645773909

解决的办法

  1. 将任务划分为大量的小人物
    • 可能将大任务切分为小任务, 使得负载更均衡
    • 增加同步开销
    • 可能没效果(如果长任务是连续的)
  2. 先分派大任务执行
    • 执行大任务的线程相比其他线程可能执行的任务的数量更少.
    • 需要能预测任务的开销
使用分布式队列减少同步开销

这样可以避免所有 workers 需要进行同时同步.

1561680402403

当 worker 线程队列为空时, 会从别的队列中偷(steal)任务

特点
问题
任务依赖

1561680741080

减少通信开销

  1. Latency 和 Throughput 的定义
  2. 通信时间的计算方法
  3. 并行程序中通信产生的原因
  4. 什么是天然通信?什么是人为通信?举例
  5. 什么是运算密度?
  6. 人为通信包括哪些?
  7. 减少通信代价的方式有哪些?

减少通信代价方法

  • Reduce overhead of communication to sender/receiver
    • Send fewer messages, make messages larger (amortize overhead)
    • Coalesce (合并)many small messages into large ones
  • Reduce delay
    • Application writer: restructure code to exploit locality
    • HW implementor: improve communication architecture
  • Reduce contention
    • Replicate contended resources (e.g., local copies, fine-grained locks)
    • Stagger access to contended resources
  • Increase communication/computation overlap
    • Application writer: use asynchronous communication (e.g., async messages)
    • HW implementor: pipelining, multi-threading, pre-fetching, out-of-order exec
    • Requires additional concurrency in application (more concurrency than number of execution units)

优化通信

  • Inherent vs. artifactual communication
    • Inherent communication is fundamental given how the problem is decomposed and how work is assigned
    • Artifactual communication depends on machine implementation details (often as important to performance as inherent communication)
  • Improving program performance
    • Identify and exploit locality: communicate less (increase arithmetic intensity)
    • Reduce overhead (fewer, large messages)
    • Reduce contention
    • Maximize overlap of communication and processing (hide latency so as to not incur cost)

阻塞型 send/recieve

1561681923093

阻塞型 send/recv 如何避免死锁

1561681996839

非阻塞型 send/recv

1561682240146

Latency 与 Throughput

传输延迟(Latency): 一个操作完成需要的时间.

1561682739048

吞吐量(Throughput/Bandwidth): 操作执行时的速度

1561682752366

增加吞吐量的方法

  1. 加快传输速度

    1561682810347

  2. 加大带宽

    1561682822715

通信与 pipline

上一节的讨论让我们知道, 虽然不可用减少 latency, 但可以增加 pipline 程度来提高 throughput.

对于无 pipline 的通信而言, 开销如下

\[T(n)=T_0+\frac{n}{B}\]

对于以下情景考虑 pipline 方式

1561683205266

1561683218826

通信开销

通信时间=本地开销+传输开销+传播开销+异地开销

通信开销=通信时间-overlap 部分

运算密度(Arithmetic intensity)

运算密度: 运算数量/通信数量

通信产生的原因

天然通信(Inherent communication)

并行算法中必须要的通信, 是算法的组成部分

information that fundamentally must be moved between processors to carry out the algorithm given the specified assignment (assumes unlimited capacity caches, minimum granularity transfers, etc.)

如何减少? 通过改进算法

1561684086835

1561684065267

1561684100528

人为通信(artifactual communication)

all other communication (artifactual communication results from practical details of system implementation)

增强局部性

  1. Cache 冲突包含哪些类型?
  2. 提高 Cache 局部性的方式有哪些?

Cache 冲突类型

1561685417531

减少 Cache Miss

改变访问顺序

考虑 row-major traversal 的访问方法

1561685513851

其中蓝色为在 Cache 中的部分, 所以我们需要 change grid traversal order

1561685557966

融合循环

1561685619379

本地处理器共享数据

减少数据竞争

  1. 减少数据竞争的方式有哪些?

Contention occurs when many requests to a resource are made within a small window of time

解决方法

parallelize over cells

One possible answer is to decompose work by cells: for each cell, independently compute particles within it (eliminates contention because no synchronization is required)

1561686552619

parallelize over particles

assign one particle to each CUDA thread. Thread computes cell containing particle, then atomically updates list.

1561686580689

use finer-granularity locks

Alleviate contention for single global lock by using per-cell locks

1561686602014

compute partial results + merge

第十四讲:性能优化之一,内容要点

1. 负载均衡主要有哪些方式?分别有什么他特点?

2. 静态、动态负载均衡适用的场景是什么?

3. 如何选择任务的粒度?

有用比处理器更多的任务(很多小任务可以通过动态分配好工作负载平衡)
Useful to have many more tasks* than processors (many small tasks enables good workload balance via dynamic assignment)

  1. 激发小粒度的任务:
    Motivates small granularity tasks
    但希望尽可能少的任务的开销最小化管理任务
    But want as few tasks as possible to minimize overhead of managing the assignment
  2. 激发大粒度任务
    Motivates large granularity tasks
    理想的粒度取决于许多因素(在这门课中共同的主题:必须知道你的工作量,和你的机器)
    Ideal granularity depends on many factors (Common theme in this course: must know your workload, and your machine)

4. Cilk_spawn 的原理是什么?

  1. cilk_spawn foo (args);语义:调用 foo,但与标准函数调用不同,调用者可以继续异步执行 foo。
  2. 注意,cilk_spawn 抽象没有指定如何或何时计划执行派生调用。只是它们可以与调用者并发运行(以及由调用者生成的所有其他调用)
  1. cilk_spawn foo(args); Semantics: invoke foo, but unlike standard function call, caller may continue executing asynchronously with execution of foo.
  2. notice that the cilk_spawn abstraction does not specify how or when spawned calls are scheduled to execute. only that they may be run concurrently with caller(and with all other calls spawned by caller)

5. Cilk_sync 的原理是什么?

  1. 语义:当当前函数生成的所有调用都已完成时返回。(与派生调用“同步”) 注意:在包含 cilk_spawn 的每个函数的末尾都有一个隐式 cilk_sync(含义:当一个 Cilk 函数返回时,与该函数相关的所有工作都完成了)
  2. cilk_sync 确实是调度上的一个约束。所有派生调用必须在 cilk_sync 返回之前完成。
  1. Semantics: returns when all calls spawned by current function have completed. (“sync up” with the spawned calls) Note: there is an implicit cilk_sync at the end of every function that contains a cilk_spawn (implication: when a Cilk function returns, all work associated with that function is complete)
  2. cilk_sync does serve as a constraint on scheduling. All spawned calls must complete before cilk_sync returns.

6. Cilk_spawn 的调度方式有哪些?各自有什么特点?

7. Cilk_spawn 中任务在不同线程之间 steal 的过程。

8. Cilk_sync 的几种实现方式。

Click 框架简介

Reference

  1. Cilk_spawn 的原理是什么?
  2. Cilk_sync 的原理是什么?
  3. Cilk_spawn 的调度方式有哪些?各自有什么特点?
  4. Cilk_spawn 的任务在不同线程之间 steal 的过程
  5. Cilk_sync 的几种实现方式

Scheduling fork-join parallelism

常见的并行编程范式有两种

Fork-join pattern: Natural way to express independent work in divide-and-conquer algorithms

Cilk 框架的几个重要函数

注意

例子

1561876200052

1561876231140

1561876237049

1561876244416

1561876251458

1561876256252

1561877309802

并行化快速排序

1561876444352

如何编写 fork-join 程序

Cilk 的 fork-join 的调度

The Cilk Plus runtime maintains pool of worker threads

cilk_spawn将程序划分为两部分

1561876644011

以下是几个实现的细节

那么, 现在有个问题, 当一个线程cilk_spawn后, 它是先执行spawned child还是continuation

以这个代码为例

for (int i = 0; i < N; i++) {
    cilk_spawn foo(i);
}
cilk_sync;

1561877004670

执行顺序为 0, 1, 2 …

1561877015674

执行顺序为 N-1, N-2, N-3 …

work stealing 的实现

sync 的实现

descriptor

对于每个由cilk_spawncilk_sync界定的代码块, 创建一个descriptor, 来描述这个代码块任务的完成情况

1561877608737

greedy policy

所有线程如果无事可做, 都会试图去偷任务. nitiated spawn thread 不一定是在 sync 后继续执行 work 的 initiated spawn thread

第十五讲:性能优化之二,内容要点

1. Latency 和 Throughput 的定义。

2. 通信时间的计算方法。

通信时间 = 程序通信时间+占有时间+网络延迟\

3. 并行程序中通信产生的原因。

  1. 处理器与其缓存之间的通信
  2. 处理器与存储器之间的通信。(内存在同一台机器上)
  3. 处理器和远程存储器之间的通信。(集群中另一个节点上的内存,通过发送网络消息访问)

4. 什么是天然通信?什么是人为通信?举例说明。

天然通信:根据指定的分配(假设无限容量缓存、最小粒度传输等),必须在处理器之间移动才能执行算法的信息
Inherent communication: information that fundamentally must be moved between processors to carry out the algorithm given the specified assignment (assumes unlimited capacity caches, minimum granularity transfers, etc.)

人为通信:所有其他通信(人为沟通源于系统实现的实际细节)
Artifactual communication: all other communication (artifactual communication results from practical details of system implementation)

5. 什么是运算密度?

图片描述 图片描述

6. 人为通信包含哪些?

Program loads one 4-byte float value but entire 64-byte cache line must be transferred from memory (16x more communication than necessary)

7. Cache 冲突包含哪些种类?

8. 提高 Cache 局部性的方式有哪些?

  1. 通过改变网格遍历顺序来改进时间局部性
  2. 通过融合循环改进时间局部性
  3. 通过共享数据提高算法强度
  1. Improving temporal locality by changing grid traversal order
  2. Improving temporal locality by fusing loops
  3. Improve arithmetic intensity by sharing data

9. 减少数据竞争的方式有哪些?

  1. 分布式工作队列可以减少争用
  2. 在大型并行机器上创建粒子数据结构网格
  3. 粒子层次并行化
  4. 使用细粒度锁
  1. distributed work queues serve to reduce contention
  2. create grid of particles data structure on large parallel machine
  3. parallelize over particles
  4. use finer-granularity locks

10. 减少通信代价的方式有哪些?

第十六讲:并行图计算,内容要点

1. Prim 算法的基本流程。

  1. 求 MST 的 Prim 算法是一种贪婪算法。
  2. 首先选择一个任意的顶点,将它包含到当前的 MST 中。
  3. 通过插入最接近其中一个的顶点来增长当前 MST 顶点已经在当前 MST 中。
  1. Prim’s algorithm for finding an MST is a greedy algorithm.
  2. Start by selecting an arbitrary vertex, include it into the current MST.
  3. Grow the current MST by inserting into it the vertex closest to one of the vertices already in current MST.

2. 并行 Prim 算法的基本流程及复杂度。

  • 该算法在 n 个外部迭代中工作,很难同时执行这些迭代。
  • 内循环相对容易并行化
    • 假设 p 为进程数,n 为顶点数。
  • 邻接矩阵采用一维分块的方式进行分块,距离向量 d 进行相应的分块。
  • 在每个步骤中,处理器选择本地最近的节点,然后进行全局约简以选择全局最近的节点。
  • 这个节点被插入到 MST 中,并选择广播给所有处理器。每个处理器本地更新其 d 向量的一部分。
  • The algorithm works in n outer iterations - it is hard to execute these iterations concurrently.
  • The inner loop is relatively easy to parallelize
    • Let p be the number of processes, and let n be the number of vertices.
  • The adjacency matrix is partitioned in a 1-D block fashion, with distance vector d partitioned accordingly.
  • In each step, a processor selects the locally closest node, followed by a global reduction to select globally closest node.
  • This node is inserted into MST, and the choice broadcast to all processors. Each processor updates its part of the d vector locally.

图片描述

3. 单源最短路径 Dijkstra 的并行版本及复杂度。

图片描述

4. 并行连接图算法原理。

  1. 跨进程划分图形,并在每个处理器上运行独立的连接组件算法。在这一点,我们有 p 个森林。
  2. 在第二步中,跨越森林两两合并,直到只剩下一个跨越森林。
  1. partition the graph across processes and run independent connected component algorithms on each processor. At this point, we have p spanning forests.
  2. In the second step, spanning forests are meged pairwise until only one spanning forest remains.

最小生成树算法

串行算法

1561874811015

最小生成树(代价之和最小的生成树)

构造准则

普里姆(Prim)算法

算法流程

注意

实现

设置辅组数组 closedge[]

流程

  1. 初始化, 将 lowcost 初始化为$\infty$, adjvex 初始化为 0.
  2. 从 lowcost[v]$\neq$0 的点(选择一个属于 V-U 的点), 选择一个 lowcost[v]最小的顶点(如果全为$\infty$, 任选一个点作为出发点, 如果有点不为$\infty$, 此时选取到的点是 V-U 到 U 权值最小的边的点)
  3. 将 adjvex[v] 改为-1, 表示它已加入生成树顶点集合。
  4. 将边 (adjvex[v], v, lowcost[v] ) 加入生成树的边集合。
  5. lowcost[i] = min{ lowcost[i], Edge[v][i] }, 即用生成树顶点集合外各顶点 i 到刚加入该集 合的新顶点 v 的距离 Edge[v][i] 与原来它们到 生成树顶点集合中顶点的最短距离 lowcost[i] 做比较, 取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离
  6. 如果生成树顶点集合外顶点 i 到刚加入 该集合的新顶点 v 的距离比原来它到生成树顶点集合中顶点的最短距离还要近, 则修改 adjvex[i] : adjvex[i] = v。表示生成树外顶点 i 到生成树内顶点 v 当前距离最近。

并行算法

并行算法流程

1561875015024

时间复杂度

并行算法每次迭代的时间复杂度为$O(n/p+logp)$

总时间复杂度为$O(n^2/p+nlogp)$

单源最短路径算法

最短路径(Shortest Path algorithms)

最短路径问题: 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。

问题解法

Dijkstra 算法

本质上是贪心算法.

算法流程

  1. 初始化: S ← { v 0 }; dist[j] ← Edge[0][j], j = 1, 2, ..., n-1;
  2. 求出最短路径的长度: dist[k] ← min { dist[i] }, i in V- S; S ← S U { k };
  3. 修改: dist[i] ← min{ dist[i], dist[k] + Edge[k][i] }, 对于每一个 i in V- S ;
  4. 判断:若 S = V, 则算法结束,否则转 2。

并行版本

和 Prim 的优化非常近似, 分析和完全考虑 Prim 的并行版本

All-pairs 最短路径算法

Dijkstra

使用的话, 复杂度为$O(n^3)$, 并行化有两种方法

Floyd’s Algorithm

1561875383130

1561875392849

Floyd’s Algorithm (1-D Block Mapping)

1561875458517

Floyd’s Algorithm (2-D Block Mapping)

1561875477302

1561875489573

1561875524495

Floyd’s Algorithm: Communications

1561875513775

Connected Components

可以使用 DFS 寻找图的连通分量

并行化可以使图在不同的处理器上运行不同生成树 DFS, 最后再合并.