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