高性能计算与云计算复习
高性能计算与云计算复习
互联网络
互联网络分为静态互联网络和动态互联网络。
静态网络是指各节点之间有固定连接的一类网络。程序执行期间,网络连接不改变。动态网络是用开关单元构成的,可以动态改变连接状态的网络。
静态互联网络的特征
网络规模:网络的节点个数
节点度数:单向网络中,入射和出射边之和称为节点度
网络直径:任意两个节点之间的最长距离
对剖宽度:将网络对分所必须移除的边的数目,如果是奇数个的话理解成可以把某个点切开,如二叉树,N=3的线性阵列
对称:从任何一个节点观看网络都一样,称为对称。(有限个网络的场景,网孔、线性阵列是非对称的)
静态互联网络特征比较
网络名 | 网络规模 | 节点度数 | 网络直径 | 对剖宽度 | 对称 | 链路数 |
---|---|---|---|---|---|---|
线性阵列 | N | 2 | N-1 | 1 | 非 | N-1 |
环形 | N | 2 | ==$\lfloor N/2 \rfloor$== | 2 | 是 | N |
==2D网孔== | $N=n^2$ | 4 | ==2(n-1)== | n | 非 | ==$2(N-n)$==先补再减 |
==Illiac网孔== | $N=n^2$ | 4 | n-1 | 2n | 非 | $2n$ |
==2D环绕== | $N=n^2$ | 4 | $2 \lfloor n/2 \rfloor$ | 2n | 是 | $2n$ |
二叉树 | N | 3 | $2(\lceil log_2N \rceil-1)$ | 1 | 非 | N-1 |
星型 | N | n-1或1 | 2 | $\lfloor N/2 \rfloor$ | 非 | N-1 |
超立方 | $N=2^n$ | $log_2N=n$ | n | N/2 | 是 | nN/2 |
k-立方环 | $N=k*2^k$ | 3 | $2k-1+\lfloor k/2 \rfloor$ | N/(2k) | 是 | 3N/2 |
并行计算的分类
Flynn分类
又叫指令流/数据流分类法,即费林(Flynn)分类法。先来看一些概念:
- 指令流:机器执行的指令序列
- 数据流:指令调用的数据序列,包括输入数据、中间结果等
- 多倍性:在系统性能平静部件上同时处于同一执行阶段的指令或数据的最大可能个数。
于是,根据指令流和数据流的不同组织形式,将计算机系统分为四类:
- 单指令单数据流(SISD):硬件不支持任何形式的并行计算
- 单指令多数据流(SIMD):有多个处理单元,按照同一指令流的要求为他们分配各不相同的数据流并进行处理。
- 多指令单数据流(MISD):每个处理单元按照多条不同的指令要求同时对同一数据流作不同处理。
- 多指令多数据流(MIMD):能将指令,数据任务等全方面并行计算的系统,将主任务分解成众多子任务以缩短时间。
MIMD计算机细分
MIMD计算机的主要分类如下:
共享内存和分布式内存的系统架构如下:
共享内存的工作原理:具有一个所有处理器都可以访问的全局物理内存,具备有如下性质:
- 对称性:系统中的任何处理器等效访问内存和IO
- 单地址:内存中的每个位置都有唯一地址值
- 低通信延迟:处理器之间的通信可以利用共享内存来交换数据
- 高速缓存及其一致性:多级缓存可以提高速度,==一致性由硬件来增强(?)==
两种模型的分类大致如下,下面将会详细介绍这五种内存访问模型:
并行计算机五种访存模型
并行计算机访存模型主要有以下五种:
- UMA(Uniform Memory Access):均匀存储访问模型
共享内存属于一种经典的均匀访问模型。主要特点:**对称多处理(Symmetric Multiprocessing, SMP)**,使用的是微处理器和高速缓存。每台处理器可以带有私有的Cache,外围设备也可以共享。发生访存竞争的时候,仲裁策略对所有节点平等。所以叫做均匀存储访问模型。(就是计算机组成中的经典模型)
在SMP中,内存模块和处理器对称地分布在互联网络的两侧。并且只有单一的操作系统镜像,负责处理各个处理器的负载,动态将进程分配到不同的处理器,保持各处理器之间的负载平衡。
- NUMA(Non-Uniform Memory Access):非均匀存储访问模型
被共享的存储器在物理上是分布存储在所有处理器中的,其所有本地存储器的集合就组成了全局地址空间。处理器访问存储器的时间是不一样的。
存储器的访问时间是指从发起访问请求到数据可用的时间间隔。简单理解就是,处理器访问离自己比较近的内存速度比其他内存更快。
如果缓存一致性能够得到维护,那么就可以成为CC-NUMA,否则成为NCC-NUMA。
- CC-NUMA(Coherent-Cache Nonuniform Memory Access):高速缓存一致性 非均匀存储访问模型
CC-NUMA使用基于目录的高速缓存一致性协议;保留了SMP结构易于编程的优点,改善常规SMP的可扩放性。实际上是一个分布式共享存储的DSM多处理机系统,最显著的优点是程序员无需明确在节点上分配数据,在运行期间,高速缓存一致性硬件会自动将数据迁移到需要用到的地方。
- COMA(Cache-Only Memory Access):全高速缓存存储访问
COMA各个处理器节点==没有存储层次结构==。对比NUMA和CC-NUMA,发现:COMA只有cache,NUMA只有memory,CC-NUMA二者兼有,而UMA则是将内存连接在总线上的。
- NORMA(No-Remote Memory Access):非远程存储访问模型。属于分布式内存模型。
架构图如下:
优点:内存可以随着CPU的数量进行等比例扩展;各个处理器可以无冲突地快速访问自己的内存,不存在维护缓存一致性的开销;可以使用商用、现成的处理器和网络。
局限性:程序员要负责所有处理器之间的数据通信细节问题;很难从基于全局内存空间建立其分布式内存管理的映射,写一个程序有一个全局的地址空间,程序员需要建立全局地址空间到分布式内存的管理,也就是解决什么数据去哪里取的问题;非一致性的内存访问时间使远程节点访问比本地节点访问需要更长的时间。
大规模并行处理机(Massively Parallel Processor, MPP)
由大规模的紧密互联的节点组成,内存访问属于非远程存储访问模型(NORMA),也就是属于分布式存储系统。
每个节点配有局部cache,并通过局部总线与局部内存、局部IO相连,通过互联网络与IO相连。各节点之间的内存模块相互独立,且不存在全局内存单元的统一硬件编址。
每个节点都有不同的操作系统映像。
仅支持消息传递等程序设计(如MPI),不支持全局共享的OpenMP并行程序设计模式。
集群(机群)
集群是一种松耦合的计算机组成方式,采用分布式存储,每一个节点是完整的计算机。
集群的优点是:投资风险小、系统结构灵活、能充分利用分散的计算资源
集群的缺点是:通信性能和并行编程环境不佳
和MPP的比较如下图,左边是MPP,右边是Cluster,重点关注:有无磁盘、总线类型
Cluster有磁盘,MPP没有;Cluster各点连接在IO总线(IOB)上,而MPP各点连接在存储总线MB上。
DSM(Distributed Shared Memory)
属于非一致性内存访问模型(NUMA),内存模块放在各个节点的内部,并且被所有节点共享。这样,可以较好改善多处理共享存储并行机的可扩展能力。
节点之间通过高性能互联网络连接,内存模块分布在各节点中,避免了SMP中的访问总线的带宽瓶颈。具有单一的内存地址空间(硬件统一编址,各个节点可以相互访问)。
注意和MPP对比,多了一个DIR:Cache Directory。
总结
各种访存模型:
五种结构特性:
并行计算模型(LogP重点)
将并行计算机的基本特征抽象出来,形成一个抽象的计算模型,作为并行算法分析、设计和性能预测的基础。
主要的并行计算模型有:PRAM模型、BSP模型和logP模型。
- PRAM模型:又称SIMD-SM模型,有一个集中的共享存储器和一个指令器,通过SM的R/W交换数据,隐式同步计算。模型的架构图如下:
优点是适合并行算法的表示和复杂性分析,易于使用,隐藏了并行机的通讯、同步等区别。
缺点是不适合MIMD并行机,忽略了SM的竞争、通讯延迟等因素。
- BSP模型
“块”同步模型,异步MIMD-DM模型,支持消息传递系统,块内异步并行,块间显式同步。
- LogP模型(重点掌握)
一种分布存储的、点到点通讯的多处理机模型,其中通讯由一组参数描述,实行隐式同步。
模型参数:
- L: latency网络延迟
- o: 接收和发送时间
- g: gap=1/bandwidth,两个连续通信的最小间隔
- P: 处理器数量
前面三个都是表示时间的参数,它们之间的关系如下图:
点到点通信事件:L+2o
读取远程地址:2L+4o
性能评测
算法性能评测
加速比:$S_p=\dfrac{串行执行时间}{并行执行时间}$
并行效率:$E=\dfrac{加速比}{核数}$
由于通信等因素,一般来说并行效率不会超过1。如果超过了1,那就是超线性加速比。那么什么时候会出现超线性加速比呢?
可能出现超线性加速比的成因主要是不同处理器的高速缓存足以提供计算需要的存储量,属于硬件特性。
不同约束条件下的加速比:
- 固定问题规模
- 固定时间
- 固定存储
Amdahl定律
描述了规模固定的加速比。
该定律指出,系统中对于某一部件采用更快的执行方式所能获得的性能改进程度,取决于这种执行方式被使用的频率。
$W_s$是串行化部分运行的时间,$W_p$是并行化部分采用串行化的方法需要的时间。f是使用串行化的任务占比,p是并行核数。
$S_{pc}=\dfrac{优化前耗时}{优化后耗时}=\dfrac{W_s+W_p}{W_s+W_p/p}=\dfrac{f+(1-f)}{f+\frac{1-f}{p}}=\dfrac{p}{1+f(p-1)}$,当p->$\infin$时,等于$1/f$。
例如,上图中,f=1/3,p=2,那么加速比就是:Spc=6/5,也就是300/250。
增强的Amdahl定律,考虑了并行和通信的开销,推导式如下:
所以,Amdahl定律用一句话总结就是:==并行计算模型的加速比不会超过串行化占比的倒数==。
Gustafson定律
描述了时间固定的加速比。
Gustafson定律也表明处理器个数、并行比例和加速比之间的关系。它描述了,在串行部分比例固定的前提下,加速比会随着处理器个数增加而增加。
见公式Amdahl推导式的$\dfrac{W_s+W_p}{W_s+W_p/p}$,当p变大的时候,加速比自然变大,但是有渐近线逼近。
考虑到并行开销的Gustafson定律,了解即可。
Sun&Ni定律
描述了存储受限的加速比。
推导公式:$\begin{aligned}S_{MC}=\frac{Work(p)/Time(p)}{Work(l)/Time(l)}=\frac{fW+(1-f)G(p)W}{fW+(1-f)G(p)W/p}=\frac{f+(1-f)G(p)}{f+(1-f)G(p)/p}\end{aligned}$
当G(p)=1的时候就是Amdahl加速定律,G(p)=p时变为f+p(1-f),就是Gustafson加速定律。
可扩展性评测标准
增加系统规模(处理器个数)会增大额外开销和降低处理器利用率,所以对于一个特定的并行处理系统(算法或程序),它们能否有效利用不断增加的处理器的能力应是受限的,而度量这种能力的就是可扩展性这一指标。可扩展性更关心在==系统规模和数据规模==变化时的==执行时间==,是{性能、系统规模、数据规模}的综合量度。
可扩展性的三种量化方式:
- 等效率=$\dfrac{加速比}{处理器数}$,分析简单
- 等速度:每秒处理的数据量,便于通过实验数据得到结果。
- 平均时延:理想并行时间和实际并行时间的差距,便于通过实验数据得到结果。
等效率函数
考虑有并行开销的并行效率,加速比$\begin{aligned}S=\dfrac{T_e}{T_p}=\dfrac{T_e}{\dfrac{T_e+T_o}p}=\dfrac{P}{1+\dfrac{T_o}{T_e}}=\dfrac{P}{1+\dfrac{W_o}W}\end{aligned}$,等效率:$\begin{aligned}E=\frac{S}{P}=\frac{1}{1+\dfrac{T_o}{T_e}}=\frac{1}{1+\dfrac{W_o}{W}}\end{aligned}$。
如果保持问题规模W不变,处理器数目p增加,开销$T_o$增大,$W_o$增大,效率E下降。为了维持等效率,在增加处理器的时候,问题规模W也应该增大。
下图是等效率曲线。曲线1表示可扩放性较好,曲线2表示算法可以扩放,曲线3表示算法不可扩放。
按照等效率函数的定义,对于某一并行算法(或并行程序),为了维持运行效率保持不变,随着处理器数目的增加,若只需增加较小的工作量(即问题规模),比如说$W$随$P$呈线性或亚线性增长,则表示该算法具有良好的可扩放性;若需增加非常大的问题规模,比如说$W$随$P$呈指数级增长,则表示该算法是不可扩放的。
PCAM设计方法学
划分
划分可以分为两类划分:域分解(数据分解)和功能分解。域分解划分的是数据,功能分解划分的是计算。
划分之后,研究不同任务所需要的数据。如果这些数据不相交,则划分是成功的,否则需要重新进行域分解。
划分的标准:
- 划分的任务数,是否至少高于目标机上处理器数量一个量级。(灵活性)若否,则后续的设计步骤缺少灵活性。
- 是否避免冗余的计算和存储要求(可扩放性)若否,算法的扩放性较差。
- 划分的任务尺寸是否大致相当(均衡)若否,分配处理器时难以做到工作量均衡。
- 任务数是否与问题尺寸成正比,理想情况下,问题尺寸的增加应该引起任务数的增加而不是任务尺寸的增加。
通信
功能分解决定了各个任务之间的数据流,各任务是并发执行的,通信则限制了这种并发性。
四种通信模式:局结态步
- 局部/全局通信
局部通信是指通信限制在一个邻域内,只与较少的几个近邻通信。
全局通信是指许多任务参与的通信,例如星型,全相联的图。
- 结构化/非结构化通信
结构化通信:每个任务的通信模式是相同的。
非结构化通信:每个任务的通信模式不同,无统一的结构。
- 静态/动态通信
静态通信是指通信伙伴的身份不会随着时间的改变而改变的通信。
动态通信伙伴的身份由计算时的数据决定,并且是可变的。
- 同步/异步通信
同步通信:双方知道何时进行通信,发送方显式地发给接收方
异步通信:接收方明确的从发送方请求数据。
了解通信的标准。
组合
组合是抽象到具体的过程,使得任务在同一类并行机上有效地执行。
合并小尺寸的任务,减少任务数,如果任务数恰好等于处理器数量,也就完成了映射的过程。
通信量与任务子集的表面成正比,计算量与任务子集的体积成正比。
增加重复计算有可能减少通讯量。
映射
每个任务需要映射到具体的处理器上,定位到运行机器上,存在负载均衡和任务调度的问题。实际上是一个NP完全问题。
映射的目标:减少算法的执行时间。主要有两点原则:
- 并发的任务:分配到不同的处理器
- 高通信的任务:分配到相同的处理器
- 负载均衡的算法:
矩阵乘法
有三种并行算法,分别是简单分块算法、Cannons算法和DNS算法,主要学习Cannon矩阵乘法。
Cannon矩阵乘法
起始对准:A矩阵第i行左移i位(i从0开始),B矩阵第i列上移i位(i从0开始)。
循环位移:每次A向左移动,B向上移动一个单位,再做一次乘法然后相加。
OpenMP并行编程
OpenMP是==共享存储体系==上的一个编程模型,应用于unix, Windows等多种平台上。OpenMP的API是基于==编译制导==,具备简单、移植性好和可扩展等优点,是共享存储系统编程(主要针对SMP平台)的一个工业标准。
编译制导(compiler directive)是一种特殊的注释或指令,用于指导编译器在源代码的编译过程中进行特定的处理或优化。
OpenMP使用FORK-JOIN并行执行模型,所有的OpenMP程序开始于一个单独的主线程,直到遇见第一个并行域,然后并行域中的代码在不同的线程组中并行执行(FORK)。当各个线程在并行域执行完成之后,最后只有主线程在执行(JOIN)。
OpenMP基本用法
当计算机上安装了gcc之后,就可以直接开始OpenMP编程了。下面是一个hello_world代码示例:
1 |
|
private(nthreads, tid)
: 这个子句定义了私有变量。在并行执行期间,每个线程都会拥有自己的私有副本。在这个例子中,nthreads
和tid
是私有变量,私有副本避免了竞争条件。其中由# pragma omp
开头的语句就是编译制导语句,编译制导语句格式解释如下:
并行域的写法如下:
一个并行域就是一个能够被多个进程执行的程序块当一个线程运行到parallel的时候,会创建一个线程组并成为该组的主线程,tid为0。当并行域开始时,程序代码被复制,==每个线程都会执行该代码==。
并行的线程数按照如下因素决定,优先级递减:
- 使用库函数omp_set_num_threads
- 设置环境变量OPM_NUM_THREADS
- 由实现决定的默认值
共享任务结构
共享任务结构将它所包含的代码划分给线程组内各个成员执行,不产生新的线程,在共享任务结构的入口处没有路障,但是在任务结束处有一个隐含的路障。共享任务结构有三种类型:
- for:线程组共享一个循环,表现出“数据并行性”
- sections:把任务分成离散段,每段由一个线程执行,表现“功能并行性”
- single:串行执行一段代码
for结构
语句格式:
schedule子句描述如何将循环的迭代划分给线程组中的线程。其参数type为static类型的时候,循环会被划分成大小为chunk的块,静态分配给各线程,若未指定chunk,则会被尽可能均衡地划分。
下面是一个使用for结构并行计算一个向量的案例:
1 | void main(){ |
section结构
sections编译制导语句是非迭代共享任务结构,指定内部的代码划分给线程组中的各线程。嵌套在sections语句中的每个section编译制导语句,由线程组中的一个线程执行。
语句格式:
使用两个section计算向量加法,分别计算前后半段。
1 | void main(){ |
single结构
single编译制导的语句制定内部的代码只有线程组中的一个线程执行,对于非线程安全的代码(比如输入/输出),这个语句比较有用。除非是用了nowait语句,否则线程组中没有执行single语句的线程会一直等到代码块结束。
代码格式:
parallel for
创建一个并行域并包含一个for语句,也就是把parallel和for结合起来。
parallel section
创建一个并行域并包含一个sections语句。
同步结构
- master
master语句指定的代码段将只由主线程执行,该线程组中的其他线程将忽略该代码段。
- critical
critical指定的代码段在同一时刻只能有一个线程执行。
- barrier
barrier语句用来同步线程组中的所有线程,在barrier语句处先到达的线程将会被阻塞,直到所有线程到达。
- atomic
指定的存储单元将被原子地更新,而不允许多个线程同时执行更新操作。
- flush
用于表示一个同步点,确保所有线程都看到一致的存储器视图。
- ordered
被指定地代码段如同在船形的处理器上执行,任何时候只能有一个线程执行被ordered所限定的部分。只能出现在for中。
- reduction
语法reduction([ reduction-modifier, ] reduction-identifier : list)
。归约(reduction)操作用于将多个线程或进程计算得到的部分结果合并为一个最终结果,可以看成是一个不会丢失修改的多线程加法。
计算PI的openMP程序
1 | static long steps = 1000000000; |
MPI编程
MPI(Message Passing Interface)是==分布存储并行模型==下的一个消息传递接口。MPI不是一个独立的自包含系统,而是建立在本地并行程序设计环境之上,进程管理和IO均由本地并行程序设计环境提供的。
安装、编译、运行
安装:以Debian为例,使用apt安装
1 | apt install mpich |
编译:使用mpicc编译
1 | mpicc -o out/$1 $1.c |
运行:使用mpirun运行
1 | mpirun -np $2 out/$1 |
可用参数:
-np:指定进程数
-host:指定主机列表
-npernode:每个计算节点的进程数
基本结构
一个MPI程序有六个基本函数:
- MPI启动:调用该函数进入MPI环境,完成初始化工作。
1 | int MPI_Init(int *argc, char ***argv) |
- MPI结束:调用该函数从MPI环境中退出,是MPI程序的最后一个调用。
1 | int MPI_Finalize(void) |
- 获取进程编号:获取当前进程在指定通信域中的编号
1 | int MPI_Comm_rank(MPI_Comm comm, int *rank)// 结果存储在rank中,而不是返回值的int |
- 获取进程数:获取指定通信域中的进程个数
1 | int MPI_Comm_size(MPI_Comm comm, int *size)// 结果存储在size中 |
- 消息发送:MPI_send函数用于发送一个消息到目标进程,将起始地址为buf的count个datatype类型的数据发送给目标进程。
1 | int MPI_Send(const void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) |
- 消息接收:MPI_Recv用于接收数据,如果数据大于缓冲区,则会
1 | int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status) |
MPI_Comm是MPI中表示通信域(communication domain)的数据类型。它用于定义进程之间的通信关系,指定通信操作的参与进程组。通信域可以是全局通信域(MPI_COMM_WORLD)或自定义的子通信域。通信域定义了一组进程,它们可以通过发送和接收消息进行相互通信。
MPI_Status是MPI中表示通信状态的数据类型。它用于在MPI通信操作中存储有关消息的信息,如发送者、接收者、消息长度等。定义如下,了解即可。
1 | typedef struct MPI_Status { |
一个MPI程序:
1 | int main(int argc, char **argv) |
Docker和hadoop
Hadoop 是一个开源的分布式计算框架,它可以处理大规模数据集并将其分配到多台计算机上进行处理。Hadoop主要掌握两个核心组件、Map/Reduce的思想。
Hadoop的两个核心,就是HDFS和MapReduce。HDFS为海量数据提供了存储,而MapReduce为海量数据提供了计算框架。
Hadoop的生态圈示意图如下:
![](https://www.eduxiji.net/assets/files/2020-04-30/1588236269-937828-hadoop-0.png)
Map/Reduce
- 整体结构:
extends Mapper<Object, Text, Text, IntWritable>
,四个范型参数是输入键、输入值、输出键、输出值。
重写void map(Object key, Text value, Context context)
。
extends Reducer<Text, IntWritable, Text, IntWritable>
,四个范型参数是输入键、输入值、输出键、输出值。
重写void reduce(Text key, Iterable<IntWritable> values, Context context)
。
- 两种数据类型:
IntWritable
整形,Text
表示字符串,这两种数据结构可以放在context中。
- 处理逻辑:
map函数
1 | StringTokenizer itr = new StringTokenizer(value.toString()); |
reduce函数
1 | int sum = 0; |
主函数:JJ,MCR,KV,IO
1 | Configuration conf = new Configuration(); |
Docker
Docker是开源的容器引擎。容器技术是一种虚拟化技术,用于将应用程序及其所有依赖项打包成独立的运行时环境,称为容器。每个容器都是相互隔离的,拥有自己的文件系统、进程空间和网络接口。容器可以理解成为“运行在一个操作系统上的一个独立系统”。
和虚拟机的区别:
部署速度、资源消耗、隔离性、部署管理
服务器虚拟化由多种技术架构,其中主要的四种如下:
云计算关键技术:
虚多弹分分