高性能计算简要复习

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是指划分、通信、组合、映射。

文章导航

Hashcat使用秘籍