高性能计算导论复习笔记

第一章

串行计算的定义

  • 软件在一台只有一个CPU的电脑上运行
  • 问题被分解成离散的指令序列
  • 指令被一条接一条的执行
  • 在任何时间CPU上最多只有一条指令在运行

**并行计算的定义

  • 是指同时使用多个计算资源去解决一个计算问题
  • 用多CPU来运行
  • 问题被分解成离散的部分可以被同时解决
  • 每一部分被细分成一系列指令
  • 每一部分的指令可以在不同的CPU上同时的执行

计算资源包括

  • 任意数量的CPU用网络连接起来
  • 多核CPU
  • 以上两者结合

并行计算的意义

  • 快速解决大型且复杂的计算问题
  • 节省时间和成本
  • 使用非本地资源

分布式计算的定义

  • 分布式计算将问题分解成许多小的部分,分配给多台计算机进行处理,把计算结果综合起来得到最终的结果

**分布式计算与并行计算的区别

  • 目的

    • 并行计算的目的是提供单处理器无法提供的性能,使用多处理器求解单个问题
    • 分布式计算的目的是提供方便,使用多计算机来解决问题
  • 交互特征

    • 并行计算:交互频繁、细粒度、低开销、可靠、注重短的执行时间
    • 分布式计算:交互不频繁、粗粒度、不可靠、注重长的正常运行时间

超级计算机的定义

  • 超级计算机(Super Computer) 通常是指由数百、数千甚至更多的处理器(机)组成的、能计算普通PC机和服务器不能完成的大型复杂课题的计算机

集群(Cluster)/机群/群集

  • 一般由高速网络连接起来的高性能工作站或PC机组成,集群在工作中像一个统一的整合资源,所有节点使用单一界面

**网格计算

  • 基于网格的问题求解
  • 网格:集成的计算与资源环境
  • 狭义的网格和网格计算:以分布的计算机作为主要资源,将分布的计算机组织起来解决复杂的科学和工程计算。

云计算

  • 云计算是并行计算、分布式计算和网格计算的发展,或者说是这些计算机科学概念的商业实现
  • 云计算是虚拟化、效用计算、IaaS(基础设施即服务)、PaaS(平台即服务)、SaaS(软件即服务)等概念混合演进并跃升的结果

网格计算和云计算比较

  • 网格计算

    • 异构资源
    • 不同机构
    • 虚拟组织
    • 科学计算为主
    • 高性能计算机
    • 紧耦合问题
    • 免费
    • 标准化
    • 科学界
  • 云计算

    • 同构资源
    • 单一结构
    • 虚拟机
    • 数据处理为主
    • 服务器/PC
    • 松耦合问题
    • 尚无标准
    • 商业社会

第二章

**并行计算的三个条件

  • 并行机:并行机至少包含两台或两台以上处理机,这些处理机通过互连网络相互连接,相互通信
  • 应用问题具有并行度:应用可以分解为多个子任务,这些子任务可以并行地执行
  • 并行编程:在并行机提供的并行编程环境上,具体实现并行算法,编制并行程序,并运行该程序

并行计算的功能

  • 快速解决大型且复杂的计算问题
  • 节省时间和成本
  • 使用非本地资源
  • 降低单个问题求解的时间
  • 增加问题求解规模
  • 提高问题求解精度

并行计算的基本定义

  • 粒度:并行执行过程中二次通讯之间每个处理机计算工作量大小的一个粗略描述,分为粗粒度、细粒度
  • 复杂性:不考虑通讯开销的前提下每个处理机的计算量最大者
  • 并行度:算法可以并行的程度
  • 加速比
  • 效率

Amdahl定律和Custafson定律

Amdahl.png

  • 阿姆达尔定律定义了串行系统并行化后加速比的计算公式与理论上限
  • 单纯地增加cpu处理器的数量并不一定可以有效地提高系统的性能,只有在提高系统内并行化模块比重的前提下,同时合理增加处理器的数量,才能以最小的投入得到最大的加速比
  • a(串行化程度)足够小,也即并行化足够高,那么加速比和cpu个数成正比

可扩展性

  • 如果增加进程数(线程数)和问题规模,并行效率保持不变,称该并行程序是可扩展的
  • 强可扩展:增加进程/线程数,不增加问题规模,可以维持固定的并行效率
  • 弱可扩展:增加进程/线程数,同时以相同倍率增加问题规模,可以维持固定的并行效率

第三章

**并行编程模式

  • 主-从式(Master-Slave)
  • 单程序多数据流(Single Program Multiple Data )
  • 多程序多数据流(Multiple Program Multiple Data )
  • 数据流水线(Data Pipelining)
  • 分治策略(Divide and Conquer)

**基本概念

  • 进程:是执行中一段程序,即一旦程序被载入到内存中并准备执行,它就是一个进程。进程是表示资源分配的的基本概念,又是调度运行的基本单位,是操作系统中独立存在的可执行的基本程序单位
  • 线程:单个进程中执行中每个任务就是一个线程,线程是进程中执行运算的最小单位
  • 一个线程只能属于一个进程,但是一个进程可以拥有多个进程
  • 线程的代价或开销比进程小
  • 线程没有地址空间,线程包含在进程的地址空间中;进程拥有的所有资源都属于线程,所有线程共享进程的内存和资源

主-从式(Master-Slave)

  • 将一个待求解任务分成一个主任务和一些从任务
  • 主进程负责任务的分解、派发和收集诸子任务的求解结果并最后汇总得到问题的最终解
  • 诸子进程接受主进程发来的消息,并行进行计算,向主进程发回各自的计算结果

单程序多数据流(SPMD)

  • 并行运行的进程均执行相同的代码段,但操作在各自不同的数据上
  • 没有主从进程之分,各个进程的地位是相同的
  • 通常进程0或多或少会担负一些基本控制任务
  • 由于没有明显的性能瓶颈并且便于有效利用MPI的聚合通信函数,并行可扩展性比较好适合大规模并行

**并行应用编程过程PCAM

  • 划分(Partitioning):分解成小的任务,开拓并发性
  • 通信(Communication):确定诸任务间的数据交换,监测划分的合理性
  • 组合(Agglomeration):依据任务的局部性,组合成更大的任务
  • 映射(Mapping):将每个任务分配到处理器上,提高并行性能

循环程序并行化的一般方法

第五章

什么是MPI(Message Passing Interface)

  • 是函数库规范,不是并行语言;操作如同库函数调用
  • 是一种标准和规范,而非某个对它的具体实现,与编程语言无关
  • 是一种消息传递编程模型,并成为这类编程模型的代表

MPI的目标

  • 较好的通信性能
  • 较好的程序可移植性
  • 强大的功能

MPI程序编译与运行

  • 程序执行过程中不能动态改变进程的个数
  • 申请的进程数np与实际处理器个数无关

MPI基本函数

#include <mpi.h>
void main (int argc, char *argv[]) {
    int np, rank, ierr;
    ierr = MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    MPI_Comm_size(MPI_COMM_WORLD,&np);
    /* Do Some Works */
    ierr = MPI_Finalize();
}

进程组(process group)

  • 指MPI程序的全部进程集合的一个有序子集

通信器(communicator)

  • 在一个进程组中进程间可以相互通信
  • 任何MPI通信函数必须在某个通信器内发生
  • 分为组内通信器和组间通信器

进程序号(rank)

  • 用来在一个进程组或通信器中标识一个进程
  • 序号的取值范围是[0, 进程数-1]
  • MPI程序中的进程由进程组或通信器序号唯一确定
  • 同一个进程在不同的进程组或通信器中可以有不同的序号
  • MPI_PROC_NULL 代表空进程

消息(message)

  • 分为数据(data)和包装(envelope)两个部分
  • 包装包括:接收/发送进程序号、消息标号、通信器
    数据包括:用户将要传递的内容

点对点通信

  • 两个进程之间的通信
  • 原进程发送消息到目标进程
  • 目标进程接收消息
  • 通信发生在同一个通信器中
  • 进程通过其在通信器内的标号表示

标准阻塞式通信(**代码)

  • 是否对发送数据进行缓存由MPI系统决定
  • 阻塞:

    • 发送成功:消息成功发送/消息被缓存
    • 接收成功:消息已被成功接收

int MPI_Send(void *buf, int count, MPI_Datatype datatype,int dest, int tag, MPI_Comm comm)

int MPI_Recv(void *buf, int count, MPI_Datatype datatype,int source, int tag, MPI_Comm comm, MPI_Status *status)

消息传输成功的条件:

  • 发送进程需指定一个有效的目标接收进程
  • 接收进程需指定一个有效的源发送进程
  • 接收和发送消息的进程要在同一个通信器内
  • 接收和发送信息的tag要相同
  • 接收缓存区要足够大

数据环状传送

数据环状传送.jpg

安全的MPI程序

Safe-MPI.jpg

阻塞式消息发送模式

标准消息发送函数(MPI_Send)

  • 发送操作不管接收操作是否启动,都可以开始
  • 发送返回条件

    • 发送数据被MPI系统存入系统缓存
    • 不缓存,数据被接收到接收缓存区

缓存消息发送函数(MPI_Bsend)

  • 发送操作不管接受操作是否启动,都可以开始
  • 直接对缓冲区进行控制,用户直接对通信缓冲区进行申请、使用、释放

    • 发送消息前必须有足够的缓存区可以,否则发送失败
    • 缓存发送返回后,不意味申请的缓存区可自由使用,须等待消息发送出去方可
  • 优势:发送操作在缓存发送数据后可以立即返回

同步消息发送函数(MPI_Ssend)

  • 同步通信模式的开始不依赖于接收进程相应的接收操作是否已经启动
  • 发送返回条件:在标准模式上确认接收方已经开始接收数据
  • 优势:发送和接收最为安全

就绪信息发送函数(MPI_Rsend)

  • 发送操作必须要求接收操作启动才可以开始
  • 优势:减少消息发送时间的开销,可能获得好的计算性能

四种模式比较

  • 标准模式(standard mode):大部分MPI系统预留了一定大小的缓冲区,当发送的消息长度小于缓冲区大小时会将消息缓冲然后立即返回;否则,当部分或全部消息发送完成后才返回,可能与接收方联络 ——> 非局部
  • 缓冲模式(buffered mode):用户必须确保所提供的缓冲区大小足以容下采用缓冲模式发送的消息,无需与接收方联络——> 局部
  • 同步模式(synchronous mode):在标准模式的基础上要求确认接收方已经开始接收数据后函数调用才返回 ——>非局部
  • 就绪模式(ready mode):发送时必须确保接收方已经处于就绪状态(正在等待接收该消息)

阻塞式与非阻塞式通信

阻塞式与非阻塞式.jpg

非阻塞式通信函数

通信请求的释放(阻塞型)

int MPI_Request_free(MPI_Request *request)

  • 如果通信尚未完成,则阻塞等待完成后返回

通信请求的取消(非阻塞型)

int MPI_Cancel(MPI_Request *request)

  • 若没有开始,释放通信占用资源,通信取消

数据类型创建函数

MPI_Type_contiguous.jpg

数据类型的使用

数据类型的使用.jpg

数据打包与拆包

数据打包拆包.jpg

广播函数

广播.jpg

规约函数

规约.jpg

第六章

OpenMP

  • OpenMP(Open Multi-Processing)是共享存储体系结构上的一个并行编程模型。适合于SMP共享内存多处理机系统和多核处理器体系结构。
  • 由一组编译制导语句、运行时库函数和环境变量组成
  • 基于线程的并行编程模型
  • 通过对串行程序添加制导语句实现并行化

指导语句

  • 制导标识符(!$OMP 、#pragma omp)
  • 制导名称(parallel, DO/for, section等)
  • 子句(private, shared, reduction, copyin)
  • 格式:制导标识符 制导名称 [Clause, ...]

调度子句SCHEDULE

  • 在for任务分配中,任务的划分称为调度
  • 该子句给出迭代循环划分后的块大小和线程执行的块范围
  • schedule (kind [, chunksize])

数据竞争

数据竞争.jpg

SECTION制导

  • 用于非迭代计算的任务分配,它将sections语句里的代码用section制导指令划分成几个不同的段,由不同的线程并行执行

Single制导

  • 为了减少并行域创建和撤销的开销,将多个临近的parallel并行域合并
  • 合并后,原来并行域之间的串行代码可以用single指令加以约束只用一个线程来完成

Master制导与Single制导的区别

  • master制导包含的代码段由主线程执行,而single由任一线程执行
  • master制导在结束处没有隐私同步,也不能指定nowait从句

运行库函数

  • int omp_get_num_threads() 得到线程队列中的线程数
  • int omp_get_thread_num() 得到执行线程的线程号
  • omp_set_num_threads() 设定执行线程的数量