高性能计算简要复习

1、概念

集群

PVP:Player VS Player PVP拥有多个高性能向量处理器,有向量寄存器和指令缓冲,不用高速缓存,共享内存。

SMP:对称多处理机,拥有多个完全相同处理器,共享内存,拥有高速缓存。

MPP:大规模并行处理机。有多个内存不共享的节点。

DSM:分布共享存储多处理机。虽然物理上独立,但逻辑上共享内存。

Cluster:每个节点拥有小于16个的处理器,由网络整合。(MPP和DSM用特别设计的网络,Cluster用普通网络)

Constellation:每个节点拥有大于等于16个处理器,由自定或普通网络整合。

存储模型

UMA:Uniform Memory Access,均匀存储访问模型。物理存储器被所有处理器共享(不位于处理器中),任意处理器访问任意内存单元时间相同,处理器可带高速缓存。

NUMA:非均匀存储访问模型。存储器分布在处理器中,因而访问不同存储空间时间不同,处理器可带高速缓存。

CC-NUMA:Coherent-Cache Not Uniform Memory Acess,高速缓存一致性非均匀存储访问模型。由多个SMP机器组成,基于目录保持高速缓存一致。实际上是DSM。由于高速缓存一致性,程序员无需特别分配数据。

COMA:Cache-Only Memory Access,全高速缓存存储访问,NUMA的特例,只有高速缓存组成的内存。

NORMA:No-Remote Memory Access,非远程存储访问模型。所有存储器私有,不支持远程访问存储器。

学科

HPC:高性能计算。并行计算、超级计算。

HPCC:高性能计算与通信。配合高速网络的使用。

Distribute Computing:分布式计算。比起性能更注重功能。

Cloud Computing:云计算。按需提供资源,使计算像电力一样提供。

2、SMP/MPP/Cluster比较

SMP使用共享变量(单地址空间),而MPP和Cluster依赖消息传递通信(多地址空间)。

SMP的访问模型是UMA,其他两者是NORMA。

SMP使用总线、交叉开关连接,其余两者用网络。

3、常用静态网络/动态网络/标准互联网

静态网络

节点度:节点最多连接几个节点。

对剖宽度:最少拆去多少条边能让网络只剩一半。

链路数:边数。

网络直径:任意两点之间最长距离(两点间如果有两个距离,距离短的才是距离)。

名称规模节点度网络直径对剖宽度对称链路数
线性阵列N2N-11/N-1
环形N2双向N/22N
二叉树N32(logN - 1)1N-1

动态网络

不懂这一块。w和f是什么意思啊。

总线系统:硬件复杂度n+w,每个处理器宽带wf/n到wf之间。

多级互联网络:w*n*(logk n),每个处理器宽带wf。

交叉开关:硬件复杂度w*n^2,每个处理器宽带wf。

标准互联网

HiPPI、SCI、Myrinet、Ethernet、Infiniband

4、PRAM/BSP/logP比较

BSP和PRAM使用简单,同步,更容易编程,logP资源利用率高,支持异步编程,但难以描述、设计、分析算法。

5、PRAM和BSP模型上计算N阶向量内积

其实不懂。

PRAM:每个处理器2N/p个加法和乘法,树规约方式计算局部和的复杂度logP。2N/p+logP。

BSP:计算本地和2N/p,logp(g+l+1)是加法合并的复杂度。

6、加速比/并行效率/可扩展性

加速比:并行算法相对于串行算法的性能提高程度。

并行效率:处理器的利用率。

可扩展性:当系统和问题规模扩大时,维持性能的能力。即算法能否充分利用资源。

固定负载、固定时间和存储受限下的加速比我已经推导过了就不写了。

7、并行计算机评测/基准测试

并行计算机性能评测:通过CPU基本性能指标、并行和通信开销分析、可用性、性价比等方面进行机器性能测评。通过加速比、效率、扩展性进行算法级性能测评。通过Benchmark进行程序级性能测评。

基准测试程序:用于测试和预测计算机系统性能,揭示不同结构机器长处和短处,便于决策。

8、可扩放性测量标准/等效率函数

可扩放性测量标准:问题和机器规模扩大时,会增大通信开销和降低利用率,程序和算法维持性能的能力就是可扩放性,度量的指标就是测量标准。

等效率函数:如果问题规模W不变,处理器P增加,开销To增大,效率E下降。为了维持效率,需要相应增大问题规模,定义函数fE(P)为一定效率下问题规模W随处理器P增加的函数。

9、分治策略/平衡树方法/倍增技术/流水线技术

分治策略:将一个大而复杂的问题拆解成若干个性质相同的子问题分而治之。

平衡树方法:叶子节点存放数据,中间节点计算,根节点给出问题的解。比如求最大值。

倍增技术:可用于求森林根,对n节点的树只需执行logn次指针跳跃。

流水线技术:这个不懂。可用于执行一维脉动阵列上的DFT计算。

10、均匀划分/方根划分/对数划分/功能划分+PSRS排序/归并排序/选择问题

这里不懂,Mark一下。

均匀划分:将n个元素分割成p段,每段n/p个元素且分配给1个处理器。

方根划分:取i*sqrt(n)作为划分元素。

对数划分:取i*logn作为划分元素。

功能划分:不是很懂,感觉应该是按功能或性质划分?除了最后一组,都划成大于等于m的组,各组并行处理。

PSRS排序:不是很清楚为什么要这样做。先均匀划分成n份,再局部排序,然后每一组选n个样本,对n^2个样本排序,选择主元(快排中的pivot)后对每个部分进行主元划分,每部分按段号交换,最后归并排序。

归并排序:先进行方根划分,然后段间、段内比较,最后段组归并。

(m,n)选择问题:先对序列进行功能划分,对子序列局部排序,将排序各组两两比较,形成MIN序列,重复局部排序和两两比较直到出现m个最小者。

11、PCAM

PCAM是指划分Partitioning、通信Communication、组合Agglomeration、映射Mapping。

划分:灵活性、避免冗余计算和存储、任务尺寸相当、功能分解合理

通信:任务通信相当、尽可能局部通信、并行通信

组合:增加粒度是否减少通信成本、是否保持灵活性和可扩展性,组合任务是否与问题规模成比例,是否保持了类似的计算和通信,有没有减少并行执行的机会,重复计算是否已权衡利弊

映射:集中式负载平衡是否存在通信瓶颈,动态负载的调度成本如何

12、域分解/功能分解+全局通信转局部通信+表面容积效应和重复计算+映射策略

域分解:数据划分。

功能分解:划分计算,将计算划分为不同任务,出发点不同域分解。

全局通信转局部通信:分治法。

表面-容积效应:通信需求比例于表面积,计算需求比例于子域容积。

重复计算:冗余计算。不必要的计算有时可以减少通信时间。

映射策略:1.使得任务可以被不同处理器并发执行,增强并发性。2.将通信频繁的任务放到同一处理器上,增强局部性。

13、并行快排序/点对最短路径算法/PSRS排序算法/求最大值算法/求前缀和算法/求元素表序算法/求森林根算法/Cannon算法/DNS算法

我挂了

14、Cannon/DNS时间复杂度和加速比

还没看。

Cannon算法串行部分n^3,并行开销(p^1/2)*n^2。

DNS算法时间logn。

15、进程通信的同步方式和聚集方式+通信模式

同步方式:原子同步(操作不可分)、控制同步(路障,临界区,进程所有操作必须等待到达控制状态)、数据同步(锁,条件临界区,事件,监控程序,程序执行必须等到某一数据状态)

聚集方式:归约(reduction)、扫描(scan)

主要通信模式:点对点SendRecv、广播Bcast、散播Scatter(与广播不同,它把一些内容分别发送给不同进程)、收集Gather、全交换Allgather、移位(置换,多对多)、归约Reduce、扫描Scan(多对多,先reduce再发送给所有进程)

16、共享存储编程模型/分布存储编程模型

共享存储编程模型:多线程,异步,单一地址空间,显式同步,隐式数据分布,隐式通信(读写共享变量)

分布式存储编程模型:多地址空间,消息传递通信,编程、移植困难,可伸缩性好,也可以单地址空间

17、OpenMP

编程模型:基于线程的并行编程模型,基于编译制导,支持嵌套并行化,支持动态线程,使用Fork-Join并行执行模型。

体系结构:应用、用户——编译制导、环境变量——运行库例程(对外提供功能、服务的接口的集合)——OS线程

控制结构:并行域(parallel)、共享任务(sections,for,single)、组合的并行共享工作(parallel for,parallel section)、同步结构(master,critical,barrier,atomic,flush,ordered)

数据域子句:显示定义变量作用范围(private、shared、default、firstprivate、lastprivate、copyin、reduction)

18、MPI消息/数据类型/通信域+MPI扩展数据类型

MPI消息:一个消息指在进程间进行的一次数据交换,MPI中消息由通信器、源地址、目的地址、消息标签和数据构成。

MPI数据类型:包括预定义类型和派生数据类型。

MPI通信域:包括进程组和通信上下文,描述进程间通信关系。

应用扩展数据类型:MPI可以处理不连续的数据,通过用户自定义的数据类型。

19、MPI阻塞通信/非阻塞通信+点到点通信模式+MPI集群通信模式

阻塞通信:一个通信过程的请求完成依赖某个事件。

非阻塞通信:一个通信过程的完成不需要等待任何通信事件的完成就可以返回。

点到点通信:标准通信模式、缓冲通信模式、同步通信模式、就绪通信模式

群集通信:广播、收集、散播、全局收集、全局交换

20、用OpenMP和MPI计算Pi的程序

Pi=sqrt(6*(1+1/4+1/9+...+1/n^2))

不同处理器计算一个区间内的平方,最后用Reduce加起来。

如果用OpenMP,需要在for循环前写#pragma amp parallel for reduction(+:sum) private(x)

21、内积、排序、串匹配、Cannon和DNS等算法的MPI和OpenMP实现

好烦啊,怎么这么多。

22、Map/Reduce

体系结构:Input split—map—shuffle—reduce—output

23、Word Count算法的Map/Reduce实现

24、GFS

一个GFS集群由一个master和大量chunkserver构成,被许多Client访问。

client负责将应用程序指定的文件名和偏移转换成固定大小的块索引,然后向master发送该请求,master回应位置,client缓存文件名和块索引,client向最近的chunk server发请求,缓存期间不需要client与master交互。

25、虚拟化

虚拟化:同时运行多个操作系统,将实体资源抽象。

虚拟化的类型:拆分(提高资源利用率)、整合(通过整合获得高性能满足特定数据计算要求)、迁移(将一台逻辑服务器中闲置部分加入到另一台逻辑服务器中,目的是实现资源共享以及跨系统应用)。

26、典型云平台

Hadoop(Google)与OpenStack(Amazon)

发表评论

电子邮件地址不会被公开。