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、常用静态网络/动态网络/标准互联网
静态网络
节点度：节点最多连接几个节点。
对剖宽度：最少拆去多少条边能让网络只剩一半。
链路数：边数。
网络直径：任意两点之间最长距离（两点间如果有两个距离，距离短的才是距离）。
| 名称 | 规模 | 节点度 | 网络直径 | 对剖宽度 | 对称 | 链路数 |
| 线性阵列 | N | 2 | N-1 | 1 | / | N-1 |
| 环形 | N | 2 | 双向N/2 | 2 | 是 | N |
| 二叉树 | N | 3 | 2(logN – 1) | 1 | 是 | N-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）