高性能计算简要复习

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、常用静态网络/动态网络/标准互联网

静态网络

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

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

链路数：边数。

网络直径：任意两点之间最长距离（两点间如果有两个距离，距离短的才是距离）。

动态网络

不懂这一块。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）