并行计算复习资料答案

〔1〕比拟PVP,SMP,MPP,DSM,Cluster,ConstellationPVP:并行向量处理机系统中包含了少量的高性能专门设计定制的向量处理器VP〔VectorProcessor〕，每个至少具有1Gflops的处理能力。系统中使用了专门设计的高带宽的交叉开关网络向VP连向共享存储模块，存储器可以M/s字节的速度向处理器提供数据。这样的机器通常不使用高速缓存，而是使用大量的向量存放器和指令缓冲器。SMP:对称多处理机SMP系统使用商品微处理器〔具有片上或外置高速缓存〕，他们经由高速总线〔或交叉开关〕连向共享存储器。这种机器主要应用于商务，例如数据库、在线事务处理系统和数据仓库等。重要的是系统是对称的，每个处理器可等同地方问共享存储，限制系统中的处理器不能太多〔一般小于64个〕，同时总线和交叉开关互连一旦做成也难于扩展。MPP：大规模并行处理机MMP一般是指超大型〔VeryLarge-Scale〕计算机系统，他具有如下特征：①处理结点采用商用微处理器；②系统中有物理上的分布式存储器；③采用高通信带宽和低延迟的互联网络〔专门设计和定制的〕；④能扩放至成百上千乃至上万个处理器；⑤它是一种异步的MIMD机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用。MMP的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。DSM：分布式共享存储高速缓存目录DIR用以支持分布高速缓存的一致性。DSM和SMP的主要差异是，DSM在物理上有分布在各个节点中的局存，从而形成了一个共享的存储器。对用户而言，系统硬件和软件提供了一个单地址的编程空间。DSM相对于MPP的优越性是编程较容易。Cluster/Cow：工作站机群COW的重要界限和特征是：①COW的每一个节点都是一个完整的工作站〔不包括监视器、键盘、鼠标等〕，这样的节点有时叫做“无头工作站〞，一个节点也可以是一台PC或SMP；②各节点通过一种低本钱的商品〔标准〕网络〔如以太网、FDDI和ATM开关等〕互连〔有的商用机群也使用定做的网络〕；③各节点内总是有本地磁盘，而MPP节点内却没有；④节点内的网络接口是松散耦合到I/O总线上的，而MPP内的网络接口是连到处理节点的存储总线上的，因而可谓是紧耦合式的；⑤一个完整的操作系统驻留在每个节点中，而MPP中通常只有一个微核，COW的操作系统是工作站UNIX，加上一个附加的软件层，以支持单一系统映像、并行度、通信和负载平衡等。现今，MPP和COW之间的界限越来越模糊。机群相对于MPP有性能/价格比高的优势，所以在开展可扩放并行计算机方面呼声很高。〔2〕比拟UMA,NUMA,CC_NUMA,CORMA,NORMACoherent：一致的这里的DSM不太正确的感觉。〔3〕HPC,HPCC,Distributedcomputing,CloudcomputingHPC：高性能计算，HighPerformanceComputingHPCC：高性能计算和通信方案，HighPerformanceComputing&CommunicationDistributedcomputing：分布式计算Cloudcomputing:云计算〔4〕列出常用静态和动态网络的主要参数〔节点度、直径、对剖带宽和链路数〕以及复杂度、网络性能、扩展性和容错性等。常用的标准互联网络有哪些？并行机规模：并行机包含的结点总数，或者包含的CPU总数；结点度：互联网络拓扑结构中联入或联出的一个结点的边的条数，称为该结点的度；结点距离：两个结点之间跨越的图的边的条数；网络直径：网络中任意两个结点之间的最长距离；点对点带宽：图中边对应的物理联接的物理带宽；点对点延迟：图中任意两个结点之间的一次零长度消息传递必须花费的时间。延迟与结点间距离相关，其中所有结点之间的最小延迟称为网络的最小延迟，所有结点之间的最大延迟称为网络的最大延迟；折半宽度：对分网络成两个局部〔它们的结点个数至多相差1〕所必须去掉的边的网络带宽的总和；总通信带宽：所有边的带宽之和标准互连网络有：①光线分布式数据接口〔FDDI〕②快速以太网〔Ethernet〕③Myrinet④可扩放一致性接口〔SCI〕⑤InfiniBand⑥HiPPI〔5〕比拟并行计算模型PRAM、BSP和logP。评述它们的差异、相对优点以及在模型化真实并行计算机和应用时的局限性。BSP和logP相互比拟：1.现今最流行的并行计算模型是BSP和logP，已经证明两者本质上是等效的，且可以互相模拟；2.BSP为算法和程序提供了更多的方便，而logP却提供了较好的机器资源的控制；3.BSP所引起的精确度方面的损失比起其所提供的更结构化的编程风格的优点来是小的；4.BSP模型在简明性、性能的可预测性、可移植性和结构化可编程性等方面更受人欢送和喜爱。三者关系：LogP和PRAM模型是并行计算模型的两个极端.BSP模型可以看成是上述两个模型的折衷.相比之下,LogP模型过于复杂,缺乏有效的分析和性能预测的模型,而PRAM那么过于简单,无法真实地描述物理机器。BSP模型较好地综合了其它两个模型优点,在面向物理机器实现方面优于PRAM模型,而和LogP模型相比,又更加便于进行算法设计和性能预测。〔6〕比拟在PRAM模型和BSP模型上，计算两个N阶向量内积的算法及其复杂度。PRAM点积：BSP点积每个处理器处理A的N/P个数值和B的N/P个数值，共N/P次乘法和N/P-1次加法(7)什么是加速比〔speedup〕、并行效率〔efficiency〕和可扩展性〔scalability〕?如何描述在不同约束下的加速比？加速比：串行执行时间为Ts，使用q个处理机并行执行的时间为Tp(q)，那么加速比为Sp(q)=Ts/Tp(q)。简单的说，并行系统的加速比是指对于一个给定的应用，并行算法〔或并行程序〕的执行速度相对于串行算法〔或串行程序〕的执行速度快了多少倍。并行效率：设q个处理机的加速比为Sp〔q〕，那么并行算法的效率Ep〔q〕＝Sp〔q〕/q。反映了并行系统中处理器的利用程度。分母要固定，表达时间不变由于存储容量变大，所以可以利用更多的资源得出更精确的解，这时会增加并行工作量P129〔8〕如何进行并行计算机性能评测？什么是基准测试程序？〔9〕什么是可扩放性测量标准？等效率函数的涵义是什么？①等效率测度：效率：加速比/处理器数简单情况下能得分析结果②等速度测度速度：每秒处理的数据量便于通过实验数据得到结果③平均时延测度〔LatencyMetrics〕时延：理想并行时间与实际并行时间的差距便于通过实验数据得到结果〔10〕什么是分治策略的根本思想？举例说明如何应用平衡树方法、倍增技术和流水线技术。划分通信组合映射如何将全局通信转换为局部通信：可以使用分治策略来提高并行性。外表－容积效应：通讯量与任务子集的外表成正比，计算量与任务子集的体积成正比；增加重复计算有可能减少通讯量重复计算：重复计算减少通讯量，但增加了计算量，应保持恰当的平衡；重复计算的目标应减少算法的总运算时间映射的策略是什么可并发执行的任务放在不同的处理器上，增强并行度需要频繁通信的任务置于同一处理器上以提高局部性看书并行快排P176