华南理工大学《高性能计算与云计算》复习资料

《高性能计算与云计算》复习资料2012计算机全英创新班黄炜杰(201230590051)1.解释并比较以下基本概念PVP,SMP,MPP,DSM,Cluster,ConstellationUMA,NUMA,CC_NUMA,CORMA,NORMAHPC,HPCC,Distributedcomputing,CloudcomputingPVP：并行向量处理机。系统中包含为数不多的高性能特制的向量处理器，使用专门设计的高带宽交叉开关网络将向量处理器连向共享存储模块。通常不使用高速缓存，而使用大量的向量寄存器和指令缓冲器。SMP：对称多处理机。节点包含两个或两个以上完全相同的处理器，在处理上没有主/从之分。每个处理器对节点计算资源享有同等访问权。SMP系统使用商品微处理器（具有片上或外置高速缓存），它们经由高速总线或交叉开关连向共享存储器。MPP：大规模并行处理机。节点传统上是由单一CPU、少量的内存、部分I/O、节点间的互联以及每个节点的操作系统的一个实例组成。节点间的互联(以及驻留于各节点的操作系统实例)不需要硬件一致性，因为每个节点拥有其自己的操作系统以及自己唯一的物理内存地址空间。因而，一致性是在软件中通过“消息传送”(messagepassing)实现的。交叉开关DSM：分布共享存储多处理机。在物理上有分布在各节点的局部存储器，从而形成一个共享的存储器。对用户而言，系统硬件和软件提供了一个单地址的编程空间。Cluster：集群。系统中的每个节点拥有小于16个处理器。Cluster是一种并行或分布式处理系统，由一系列通过网络互连的互相协同工作的单机组成，形成单一、整合的计算资源。Constellation：系统中的每个节点拥有大于或等于16个处理器。UMA：UniformMemoryAccess.均匀存储访问模型。特点：1.物理存储器被所有处理器均匀共享，所有处理器访问任何存储单元花费相同的时间；2.每台处理器可带私有高速缓存；3.外围设备也可以一定形式共享。NUMA：NonuniformMemoryAccess.非均匀存储访问模型。特点：1.被共享的存储器在物理上是分布在所有的处理器中的，组成全局地址空间；2.处理器访问存储器的时间是不同的，访问本地存储器或群内共享存储器较快，访问外地存储器或全局存储器较慢；3.每台处理器可带私有高速缓存，外设可以某种形式共享。CC_NUMA：Coherent-CacheNonuniformMemoryAccess.高速缓存一致性非均匀存储访问模型。实际上是将一些SMP机器作为一个单节点而彼此连接起来所形成的一个较大的系统。特点：1.使用基于目录的高速缓存一致性协议；2.保留SMP结构易于编程的优点，改善了常规SMP的可扩放性问题；3.实际上是一个分布共享存储的DSM多处理机系统；4.最显著的优点是程序员无需明确地在节点上分配数据，在运行时高速缓存一致性硬件会自动地将数据迁移到要用到的它的地方。COMA：Cache-OnlyMemoryAccess.全高速缓存存储访问。是NUMA的一种特例。特点：1.各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；2.利用分布的高速缓存目录进行远程高速缓存的访问；3.高速缓存容量一般大于2级高速缓存容量；4.使用COMA时，数据开始可以任意分配，因为在运行时它最终会被迁移到要用到的它的地方。NORMA：No-RemoteMemoryAccess.非远程存储访问模型。分布存储的多计算机系统，所有的存储器都是私有的，仅能由其处理器访问。绝大多数NORMA不支持远程存储器访问。HPC:HighPerformanceComputing高性能计算，即并行计算。在并行计算机或分布式计算机等高性能计算系统上所做的超级计算。HPCC：HighPerformanceComputingandCommunication高性能计算与通信。指分布式高性能计算、高速网络和Internet的使用。Distributedcomputing：分布式计算。在局域网环境下进行的计算。比起性能来说，它更注重附加功能。一个计算任务由多台计算机共同完成，由传统的人和软件之间的交互变成软件和软件之间的数据交互。Cloudcomputing：云计算是一种新兴的共享基础架构的方法，通过互联网将资源以“按需服务”的形式提供给用户，利用互联网连接的数据中心和服务器进行高效计算和信息存取的系统,使计算能力可以向电能一样提供给客户（高度可扩展）2.试比较SMP、MPP和Cluster并行机结构的不同点，并以典型系统举例说明。3.列出常用静态和动态网络的主要参数（节点度、直径、对剖带宽和链路数）以及复杂度、网络性能、扩展性和容错性等。常用的标准互联网络有哪些？常用的标准互联网络有：4.比较并行计算模型PRAM、BSP和logP。评述它们的差别、相对优点以及在模型化真实并行计算机和应用时的局限性。PRAM优缺点BSP优缺点logP优缺点5.比较在PRAM模型和BSP模型上，计算两个N阶向量内积的算法及其复杂度。PRAM模型BSP模型6.什么是加速比（speedup）、并行效率（efficiency）和可扩展性（scalability）?如何描述在不同约束下的加速比？加速比（Speedup）:对于一个给定的应用，并行算法（或并行程序）相对于串行算法（或串行程序）的性能提高程度.并行效率（ParallelEfficiency）：处理器的利用率Efficiency=(Sequentialexecutiontime)/(Numberofprocessors*Parallelexecutiontime)可扩展性（Scalability）：当系统和问题规模增大时，可维持相同性能的能力，即指应用、算法和结构能否充分利用不断增长的处理器的能力固定负载(Amdahl定律)：计算负载是固定不变,增加处理器数来提高计算速度。加速比为：(Ws串行分量，Wp可并行分量)带通信开销的计算公式式不带通信开销的计算公opspxpspsWp;/固定时间(Gustafson定律)：时间固定不变，为了提高精度加大计算量，相应的增多处理器数目。加速比为：（考虑额外开销）不考虑额外开销WoWpWspWpWsSWpWspWpWspWpWspWWsSpp')(/*'存储受限（Sun－Ni定律）：只要存储空间许可，尽量增大问题的规模以产生更好的或更精确的解，加速比为：（f:串行分量比例(Ws/W)G(p):存储容量增加到P倍）)(//)()1()()1(/)()1()()1(''S)(/)()1()()1(/)()1()()1(''考虑额外开销不考虑额外开销WWoppGffpGffWopWpGffWWpGffWppGffpGffpWpGffWWpGffWS7.如何进行并行计算机性能评测？什么是基准测试程序？并行计算机性能评测：通过CPU和存储器的某些基本性能指标、并行和通信开销分析、并行机的可用性与好用性以及机器成本、价格与性价比进行机器级性能测评；通过加速比、效率、扩展性进行算法级性能测评；通过Benchmark进行程序级性能测评。基准测试程序:用于测试和预测计算机系统的性能，揭示了不同结构机器的长处和短处，为用户决定购买和使用哪种机器最适合他们的应用要求提供决策。8.什么是可扩放性测量标准？等效率函数的涵义是什么？可扩放性测量标准：增加系统规模（处理器数）会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。等效率函数的涵义：如果问题规模W保持不变，处理器数p增加，开销To增大，效率E下降。为了维持一定的效率（介于0与1之间），当处理数p增大时，需要相应地增大问题规模W的值。由此定义函数fE(p)为问题规模W随处理器数p变化的函数，为等效率函数。9.什么是分治策略的基本思想？举例说明如何应用平衡树方法、倍增技术和流水线技术。分治策略的基本思想：将一个大而复杂的问题分解成若干特性相同的子问题分而治之。平衡树方法：可应用于求n个数的最大值：叶节点存放待处理的数据，内节点执行相应子问题计算，根节点给出问题的解。倍增技术：可以应用于求森林根，对于n个节点的树执行logn次指针跳跃即可找到树的根。流水线技术：可应用于执行一维脉动阵列上的DFT计算。10.什么是均匀划分、方根划分、对数划分和功能划分？如何用划分方法解决PSRS排序、归并排序和（m,n）选择问题？均匀划分：将n个元素分割成p段，每段含有n/p个元素且分配给一台处理器。方根划分：取每第i√n(i=1,2,…)个元素作为划分元素，而将序列划分成若干段，然后分段处理之。对数划分：取每第ilogn(i=1,2,….)个元素作为划分元素，而将序列划分成若干段，然后分段处理之。功能划分：将长为n的序列划分成等长的一些组，每组中的元素应大于或等于m（最后一组除外），然后各组可并行处理。采用均匀划分方法，解决PSRS排序：均匀划分待排序序列成n份，对每份作局部排序，再从每份中抽取n个样本，对n²个正则样本进行排序，选择主元然后对每部分进行主元划分，把每部分按段号进行全局交换，最后进行归并排序。采用方根划分方法，解决归并排序：先对序列进行方根划分，然后进行段间、段内比较，最后进行段组归并。采用功能划分方法解决(m,n)选择问题：先对序列进行功能划分，然后对每个子序列进行局部排序，将排序的各组进行两两比较，形成MIN序列，最后重复局部排序和两两比较直至出现m个最小者。11.并行算法设计的一般过程PCAM是指什么？各个步骤中的主要判据是什么？PCAM是Partitioning（划分）、Communication（通信）、Agglomeration（组合）和Mappin（映射）首字母的拼写，它们代表了使用此法设计并行算法的四个阶段。划分判据：划分是否具有灵活性？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解，是否合理？通信判据：所有任务是否执行大致相当的通信?是否尽可能的局部通信？通信操作是否能并行执行?同步任务的计算能否并行执行？组合判据：增加粒度是否减少了通信成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩展性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通信？有没有减少并行执行的机会？映射判据：采用集中式负载平衡方案，是否存在通信瓶颈？采用动态负载平衡方案，调度策略的成本如何？12.什么是域分解和功能分解？如何将全局通信转换为局部通信？什么是表面-容积效应和重复计算？映射的策略是什么？域分解：也叫数据划分。所要划分的对象是些数据，这些数据可以是算法（或程序的输入数据，计算的输出数据，或者算法所产生的中间结果。功能分解：划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解。将全局通信转换为局部通信：采用分治法。表面-容积效应:一个任务的通信需求比例与它所操作的子域的表面积，而计算需求却比例于子域的容积。重复计算：它也称为冗于计算。有时候可以采用不必要的多余的计算的方法来减少通信要求和/或执行时间。映射的策略：(1)使得任务可以被不同的处理器并发地执行，增强并发性（concurrency）(2)将通信频繁的任务放到同一个处理器上，增强局部性（locality）13.掌握算法6.2（并行快排序），6.5（点对最短路径算法），7.1（PSRS排序算法），7.8（求最大值算法），7.9（求前缀和算法），7.10（求元素表序算法），7.11（求森林根算法），9.5（Cannon算法），9.6（DNS算法）的基本原理和伪代码描述。6.26.57.17.87.97.107.119.59.614.比较并行矩阵乘法Cannon和DNS的时间复杂度和加速比。CannonDNS运行时间O(lo