并行计算的参考题目

1、1、讨论某一种算法的可扩放性时，一般指什么？88答：讨论某一种算法的可扩放性时，实际上是指该算法针对某一特定机器结构的可扩放性2、使用“DoinParallel"语句时，表示的是什么含义105答：表示算法的若干步要并行执行3、并行计算机的存储访问类型有哪几种？26答：存储访问类型有：UMA（均匀存储访问）、NUMA（非均匀存储访问）、COMA（全高速缓存存储访问）、CC-NUMA（高速缓存一致性非均匀存储访问）、NORMAl（非远程存储访问）4、什么是同步？它有什么作用？如何实现？107答：同步是在时间上强使各执行进程在某一点必须相互等待。作用：确保个处理器的正确工作顺序以及对共享可

2、写数据的正确访问（互斥访问）。实现方法：用软件、硬件和固件的方法实现。5在并行加速比的计算中，常用的三种加速比定律分别是哪三种？（P83）答：常用的三种加速比定律分别是：适用于固定计算负载的Amdahl定律，适用于可扩放问题白GGustafson定律和受限于存储器的Sun和Ni定律。6、试比较Amdahl定律、Gustafson定律、Sun和Ni定律三种加速定律的应用场合。83答：Amdahl定律适用于固定计算负载的问题Gustafson定律适用于可扩放性问题Sun和Ni定律适用于受限于存储器的问题。7 .并行算法的基本设计技术有哪些？它们的基本思想是什么？139答：（1）基本技术有：划分设计

3、技术（又分为均匀划分技术、方根划分技术、对数划分技术和功能划分技术卜分治设计技术、平衡树设计技术、倍增设计技术、流水线设计技术等。（2）基本思想分别如下：a.划分设计技术：（P139）将一原始问题分成若干部分，然后各部分由相应的处理器同时执行。b.分治设计技术：（P144）将一个大二复杂的问题分解成若干特性相同的子问题分而治之。若所得的子问题规模仍嫌过大，可反复使用分治策略，直至很容易求解诸子问题为止。c.平衡树设计技术：（P149）将输入元素作为叶节点构筑一颗平衡二叉树，然后自叶向根往返遍历。d.倍增设计技术：（P151）又叫指针跳跃技术，特别适合处理以链表或有向有根树之类表示的数据结构。每

4、当递归调用时，所要处理的数据之间的距离将逐步加倍，经过k步后就可完成距离为2k（2的k次方）的所有数据的计算。e.流水线设计技术：（P153）将一个计算任务t分成一系列子任务t1,t2,t3,.,tm,使得一旦tm完成，后继的子任务就可立即开始，并以同样的速率进行计算。8 .并行计算模型一般可分为哪几种模型？108答：PRAM模型、APRAM模型、BSP模型、logP模型。9、主要的并行计算模型有哪些？它们的主要思想是什么？108答：并行计算模型主要有：PRAM模型、APRAM模型、BSP模型、logP模型。思想：PVP系统中使用了专门设计的高带宽的交叉开关网络将VP连向共享存储模块，存储器可

5、以兆字节每秒的速度向处理器提供数据。这样的机器通常不适用高速缓存，而是使用大量的向量寄存器和指令缓冲器。SMPSMP系统使用商品微处理器(具有片上或外置高速缓存)，它们经由高速总线(或交叉开关)连向共享存储器。系统是对称的，每个处理器可等同地访问共享存储器、IO设备和操作系统服务。正是对称，才能开拓较高的并行度；也正是共享存储，限制系统中的处理器不能太多(一般少于64个)，同时总线和交叉开关互连一旦做成也难于扩展。MPPMPP一般是指超大型计算机系统，它具有如下特性：1、处理节点采用商品微处理器；2、系统中有物理上的分布式存储器；3、采用高通信带宽和低延迟的互连网络(专门设计和定制的)；4、能

6、扩放至成百上千乃至上万个处理器；5、它是一种异步的MIMD机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息互相作用。DSMDSM和SMP的主要差别是，DSM在物理上有分布在各节点中的局存，从而形成了一个共享的存储器。对用户而言，系统硬件和软件提供了一个但地址的编程控件。DSM相对于MPP的优越性是编程较容易。COWCOW的重要界线和特征是：1、COW的每个节点都是一个完整的工作站，这样的节点有时叫做“无头工作站”，一个节点也可以是一台PC或SMP;2、各节点通过一种低成本的商品网路互连；3、各节点内总是有本地磁盘，而MPP节点内却没有；4、节点内的网络接口是松散耦合到I/

7、O总线上的，而MPP内的网络接口是练到处理节点的存储总线上的，因而可谓是紧耦合式的；5、一个完整的操作系统驻留在每个节点中，而MPP中通常只是个微核，COW的操作系统是工作站UNIX,加上一个附加的软件层，以支持单一系统映像、并行度、通信和负载平衡等。10 .根据处理器对共享存储单元同时读、同时写的限制，PRAM模型可以分为哪几种模型？P109答：不允许同时读和同时写(Exclusive-ReadandExclusive-Write)的PRAM模型，简记之为PRAM-EREW。(2)允许同时读不允许同时写(Concurrent-ReadandExclusive-Write)的PRAM模型，简记

8、之为PRAM-CREW。(3)允许同时读和同时写(Concurrent-ReadandConcurrent-Write)的PRAM模型，简记之为PRAM-CRCW。显然，允许同时写是不现实的，于是又对PRAM-CRCW模型做了进一步的约定：(1)只允许所有的处理器同时写相同的数，此时称为公共(Common)的PRAM-CRCW,简记之为CPRAM-CRCW;(2)只允许最优先的处理器先写，此时称为优先(Priority)的PRAM-CRCW,简记之为PPRAM-CRCW;允许任意处理器自由写，此时称为任意(Arbitrary)的PRAM-CRCW,简记之为APRAM-CRCW。11 .APRA

9、M模型中有四类指令，它们分别是哪些?110APRAM模型中有四类指令：全局读：将全局存储单元中的内容读入局存单元中；局部操作：对局存中的数执行操作，其结果存入局存中；全局写：将局存单元中的内容写入全局存储单元中；同步：同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序.12、并行计算的物质基础是什么？3答：并行计算的物质基础是高性能并行计算机(包括分布式网络计算机)。课本第一章大标题下面，第3页13 .在并行计算中，对于点对点的通信，测量开销一般使用的方法有哪些？(P80)对于点到点的通信，测量开销使用兵-乓方法：节点0发送M个字节给节点1;节点1从节点0接

10、收M个字节后，立即将消息发回节点0.总的时间除以2,即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。兵-乓方法可一般化为热土豆法，也称救火队法：节点0发送M个字节至节点1,节点1再将其发送给节点2,以此类推，最后节点N-1再将其返回给节点0,最后时间再除以N即可。14 .在Amdahl定律中，以f表示串行分量的比例，随着处理器数目的无限增大，并行系统所能够达到的加速上限是什么？83答：S=1/f15、并行计算机系统的互联有哪三种类型？9静态、动态和标准三类16、从并行程序设计的角度来看，分布存储系统的主要特点有哪些？这些特点导致了哪些并行编程模型？348答：从并行程序设计的角度来看

11、，分布存储系统的主要特点：系统通过互连网络将多个处理器连接起来，每个处理器均有自己的局部存储器，所有的局部存储器就构成了整个地址空间；整个地址空间有局部和全局两种编址方式。上述的特点，导致了分布存储系统的两种并行编程模型：数据并行模型和消息传递模型。17 .并行计算机的系统结构模型包括有哪几种？(P22)答：大型并行机系统一般分为六类：单指令多数据流SIMD并行向量处理机PVP对称多处理机SMP大规模并行处理机MPP工作站机群COW分布共享存储多处理机DSM18 .在分析并行算法的复杂度时，主要有哪些指标来分析的？106答：主要的指标有：(1)运行时间t(n)：运行时间就是算法运行在给定的模型

12、上求解问题所需的时间，通常包括计算时间和通信时间，分别用计算时间步和选路时间步作为单位(2)处理器数p(n)：它是求解给定问题所用的处理器数目(3)并行计算的成本c(n)：它定义为并行算法的运行时间t(n)与所需的处理器数目p(n)的乘积(4)总运算量W(n)：并行算法所完成的总的操作量。19 .对于高速并行计算主要有哪几种类型的应用需求？P5答：对高速并行计算的需求是广泛的，但归纳起来主要有三种类型的应用需求：1)计算密集型应用，如大型科学工程计算与数值模拟；2)数据密集型应用，如数字图书馆和数据仓库等；3)网络密集型应用，如协同工作、遥控和远程医疗诊断等。20 .什么是通信？它的功能是什么

13、？164答：所谓通信，就是为了进行并行计算，诸任务之间所需进行的数据传输。它的功能是进行数据交换与传输。21 .在BSP模型中，计算是如何实现的？112在BSP模型中，计算系由一系列用全局同步分开的周期为L的超级步(superstep)所组成。在各超级步中，每个处理器均执行局部计算，并通过选路器接收和发送消息；然后作一全局检查，以确定该超级步是否已由所有的处理器完成；若是，则前进到下一超级步，否则下一个L周期被分配给未曾完成的超级步。22 .用于获得等速度可扩性标准的方法有哪些？92答：1.测量法2 .计算法3 .预计法23.描述的，哪些参数可以用来描述logP模型？113答：l(Latenc

14、y)表示在网络中消息从源到目的地所遭到的延迟o(Overhead)表示处理器发送或接收一条消息所需的额外开销g(Gap)表示处理器可以连续进行消息发送或接收的最小时间间隔P(Processor)表示处理器/存储器模块数24、并行算法的一般设计过程可以分为那些步骤？160答：过程可分为四步，即是任务划分(Partitioning)通信(Communication)分析、任务组合(Agglomeration)、和处理器映射(Mapping),简称为PCAM设计过程。25、目前，并行软件与并行硬件的发展如何？答：并行硬件：包括对称处理机和大规模并行1、当代主流的并行计算机是可扩放的并行计算机,处理机

15、以及机群系统；2、机群技术是发展可扩放并行计算的主流趋势；3、并行硬件正在成为计算机处理技术中广为应用的一部分。并行软件：2861、并行软件的发展落后于并行硬件；2、和串行系统的应用软件比，现今的并行系统的软件甚少且不成熟;3、并行软件的缺乏是发展并行计算的主要障碍;4、不幸的是，这种状态似乎仍在继续着。26 .当在实际的并行机中设计并行程序时，绝大部分均是使用扩展的FORTRAN和C语言的方法，目前有哪些扩展的方法？(书上288页)目前的三种扩展方法：1.库函数法2.新语言结构法3.编译制导法27 .试比较Amdahl定律、Gustafon定律、Sun和Ni定律三种加速定律之间的关系？83A

16、mdahl定律和Gustafson定律都是通过增加处理器数量来达到提高计算速度的目的，而Sun和Ni定律是通过增加存储空间来求得更好或者更精确的解的。Sun和Ni定律是Amdahl定律和Gustafson定律的一般化，其加速比另两者高。28 .现在的并行编程风范有哪些？P290(1)相并行：一个并行程序是由一些超级步组成：每个超级步内，各个进程执行独自的计算，然后继之以交互作用。(2)分治并行：一个父进程将其工作负载分成一些小的负载并将它们指派给一些子进程，这些子进程并行地完成各自的计算，其计算结果由父进程归并之。(3)流水线并行：一些进程形成流水线作业法，诸进程在流水线的不同地段同时重叠地执

17、行操作以达到整体并行的效果。(4)主-从并行：这种并行也称之为放牧式并行。(5)工作池并行：这种并行的优点是易于达到负载平衡，因为工作负载是动态地分配给空间进程的。29.消息传递模型有哪些特点？P314答：消息传递模型具有以下特点：(1) 多线程：消息传递程序系由多个进程组成，每个进程都有其控制线和可执行不同的代码；控制并行和数据并行均可支持(2) 异步并行性：消息传递程序的诸线程彼此异步地执行，使用诸如路障和阻塞通信的方法来同步各线程。(3) 分开的地址空间：并行程序的进程驻留在不同的地址空间内。(4) 显式相互作用：程序员必须解决包括数据映射、通信、同步和聚合等相互作用问题;进程只在其拥有

18、的数据上执行计算(5) 显式分配：负载和数据均由用户分配给进程30、共享存储的编程模型的特点有哪些？317答：多线程性、异步性、单地址空间31.什么是logP模型？它的特点是什么？113logP模型是一种分布存储的、点到点通信的多处理机模型其中通信网络由一组参数来描述：l表示在网络中消息从源到目的地所遭到的延迟o表示处理器发送或接收一条消息所需的额外开销g表示处理器可连续进行消息发送或接收的最小时间间隔P表示处理器/存储器模块数特点：l.logP模型将现代和将来的并行机的特性进行了精确的综合，以少量的参数L、o、g和p刻画了并行机的主要瓶颈2.logP模型无须说明编程风格或通信协议，它可以等同

19、地用于共享存储、消息传递和数据并行等各种风范3.logP模型的可用性已经由诸如播送、求和、FFT、LU分解、排序、图的连通性等算法得以证实4.如果使logP模型中白参数g=0,L=0和o=0,则logP就等同于PRAM,同时logP模型也是BSP模型的改进和细化；在一个超级步中消息一旦到达处理器就可立即使用它，而不必像BSP那样一定要等到下一个超级步；logP模型全部采用消息同步而不像BSP那样要用专门的硬件支持32题：i述BSP和logP两个并行计算模型是否存在等效性？116答：两者本质上是等效的，且可以相互模拟：用BSP去模拟logP所进行的计算时，通常会慢常数倍，而用logP去模拟BSP

20、所进行的计算时，通常也会慢对数倍。33、在并行计算算法设计中，什么是循环映射？173循环映射也就是采用某种枚举方法，轮流地将各处理器分配给诸计算任务。这种方法可能使负载平衡，但牺牲了局部性且通信可能会增加。此外，块循环分配也是一种可能的处理器映射方法，此时，任务按块的形式轮流分配给处理器。34 .在并行算法的基本操作中，彳f么是数据交换方式？183答：数据交换方式可以归结为处理器之间的通信操作，而通信操作各式各样，包括研究通信操作与处理器之间的互联拓扑，通信选择策略和消息传递机制关系。参考第八章前言35 .对称多处理机SMP的主要结构特性有哪些？40答：对称性；但地址空间；高速缓存及其一致性；

21、低通信延迟。36 .设计大规模并行处理机MPP系统时，应该考虑那些问题？P49答:应考虑以下问题：1.可扩放性2.系统成本3.通用性和可用性4.通信要求5.存储器和I/O能力37.在并行计算技术发展过程中，大力发展工作站机群COW的原因是什么？65答：大力发展工作站机群COW的原因有：COW在实用上有以下明显的优点：1.投资风险小。2.编程方便。3.系统结构灵活。4.性能、价格比高。5.能充分利用分散的计算资源。6.可扩放性好。（具体详见课本P65）38、工作负载的度量物理量有哪些？78答：工作负载即计算操作的数目，其度量物理量有执行时间、浮点运算数和指令数。8539 .在gustafson定

22、律中，其基本出发点是什么？从该定律中可以得出什么结论?答:Gustafson加速定律的基本出发点是：(1)对于很多大型计算，精度要求很高，即此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理数才能维持时间不变；(2)除非学术研究，在实际应用中没有必要固定工作负载而使计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。从定律中我们可以知道，随着处理器数目的增加，加速几乎与处理器数成比例的线性增加，串行比例f不再是程序的瓶颈。40 .在并行加速比白计算中，Sun和Ni定律的基本思想是什么？86答:其基本思想是只要存

23、储空间许可，应尽量增大问题规模以产生更好或更精确的解(此时可能使执行时间略有增加)。41、MPI中的六个基本函数?基本函数：MPI_INITMPI_FINALIZEMPI_COMM_SIZEMPI_COMM_RANKMPI_SENDMPI_RECVpage352功能：启动MPI计算结束MPI计算确定进程数确定自己的进程标识符发送一条消息接收一条消息42、什么是并行计算？实施并行计算有什么作用？104答：并行计算就是在并行计算机或分布式计算机等高性能计算系统上所做的超级计算。实施并行计算的作用有：快速解决大型且复杂的计算问题，利用非本地资源，节约成本一使用多个廉价”计算资源取代大型计算机，同时克

24、服单个计算机上存在的存储器限制。43、什么是节点度、网络直径？9答：射入或射出一个节点的边数称为节点度，在单向网络中，入射和出射边之和称为节点度。网络中任何两个节点之间的最长距离，即最大路径数称为网络直径。拓展：对分网络各半所必须移去的最少边数称为对剖宽度。44 .设计并行算法一般有哪些策略？它们的主要思想是什么？101策略：并行化、全新法、借用法。思想：并行化法就是直接讲一个串行算法并行化；全新法就是根据问题的特性，从头开始设计一个新的并行算法；借用法就是借用已知某类问题的现有算法，球解另一类与之有内在相似性的问题。45 .什么是工作站机群COW,它有哪些优势？P64工作站机群COW是实现并

25、行计算的一种新主流技术，是属于分布式存储的MIMD并行计算机结构，系由工作站和互联网络两部分组成。即它是将一群工作站用某种结构的网络互联起来，充分利用各工作站的资源，统一调度、协调处理，以实现高效并行计算。优势：投资风险小，变成方便，系统结构灵活，性价比高，可扩放性好，能充分利用分散的计算资源。46 .并行系统的加速比是什么？它的作用是什么？（P83）并行系统的加速比是对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。加速比的作用对科学研究和工程应用有所不同；科学研究中使用绝对加速：即对给定问题，最佳串行算法所用的时间除以同一问题其并行算法

26、所用的时间；工程应用使用相对加速：即对给定问题，同一个算法在单处理器上运行的时间除以在多个处理器上运行的时间。47、什么是可扩放性？它的作用是什么？如何衡量其优劣？88答：可扩放性是指在确定的应用背景下，计算机系统（或算法或编程等）性能随处理器数的增加而按比例提高的能力。作用：用来描述并行算法能够有效利用可扩充的处理器数的能力。可用等效率、等速度和平均延迟方法来衡量它的优劣。48 .什么是等效率函数，其作用是什么？89答：为了维持一定的效率（介于0与1之间），当处理器P增大时，需要相应地增大问题规模W的值，由此定义函数fE（p）为问题规模W随处理器P变化的函数，称此函数为等效率函数。作用是：根

27、据等效率函数可以判定某个函数是否具有扩放性。49 .什么是域分解嗯功能是什么?162答:域分解也叫数据划分，所要划分的对象是数据，这些数据可以是算法的输入数据，计算的输出数据，或者算法所产生的中间结果.它首先分解与问题相关的数据（尽可能大致相等，其次将每个计算关联到它所操作的数据上.功能:把原计算问题分割成一些小的计算任务，以充分揭示并行执行的机会.50、在并行算法的设计过程中，细粒度任务、粗粒度任务与并行算法的关系是什么？答：在设计过程的划分阶段，致力于定义尽可能多的任务以增大并行执行的机会。但是定义大量的细粒任务不一定能产生一个有效地并行算法，因为大量细粒度任务有金额能增加通讯代价和任务创

28、建代价。如果每个任务的通讯伙伴是少的，则增加划分粒度能减少通讯次数，同时还能减少总通讯量。对同一计算问题，粗粒度划分的通讯次数和通讯量均比细粒度划分是有所下降。因此，在其他条件同等的情况下，对于一个给定的计算，高维分解减少了通讯。因此从效率的角度，增加粒度的最好办法是在所有的维组合任务。（P168）细粒度并发性好，粗粒度通信开销低51.在并行计算中，什么是处理器映射？它的作用是什么？171答：处理器映射：在并行算法设计最后阶段中，我们要指定每个任务要到哪个处理器上执行。作用：减少并行算法的总执行时间。52、什么是全局通信？它的主要特点是什么？166答：全局通信系指有很多任务参与交换数据的一种通

29、信模式。主要特点：每个任务与很多别的任务通信。53、什么是分布算法？实施它的优点是什么？104分布算法是指算法的诸进程的执行不必相互等待的一类并行算法。54、什么是网络计算？104答：网络计算（Networkcomputing）是指计算机在网络上一起工作。55、何为网络对称？9答：如果从任一节点观看网络都一样，则称网络为对称的。56.一个n立方中，它有多小个顶点？10有2的N次方个顶点的！57、MPP和机群相比，它的性能/价格比如何？请比较答：MPP性价比一般，而机群的性价比比较高。58、串行计算模型有理想的模型吗？并行计算有理想的模型吗？为什么？109答：串行计算模型有理想的模型，冯诺依曼机

30、是理想的串行计算模型；并行计算没有理想的模型，因为由于并行机在飞速发展之中，尚未定型，故目前尚没有所谓的通用并行计算模型，也就没有理想的模型。（来源网络）59、什么是PRAM模型，它的特点是什么？108答：PRAM模型即并行随即存取机器，也称之为共享存储的SIMD模型，是一种抽象的并行计算模型。特点：它是假设有一个无限大容量的共享存储器，并且有多个功能相同的处理器，在任意时刻处理器可以访问共享存储单元。60、在什么情况下可以称一个并行算法是成本最优的？106答：假设有p个处理器，Ts是串行最优执行时间，Tp是并行最优执行时间，则当Tp的渐进度和Ts的渐进度是相同的话，那么称这个算法的成本是最优

31、的。61 .异步PRAM模型的主要特点是什么？109答：分相PRAM模型是一个异步的PRAM模型，简记之为APRAM,系由p个处理器组成，其特点是每个处理器都有其局存、局部时钟和局部程序；处理器间的通信经过共享全局存储器；无全局时钟，各处理器异步地独立执行各自的指令；处理器任何时间依赖关系需明确地在各处理器的程序中加入同步（路）障；一条指令可在非确定（无界）但有限的时间内完成。参考课本P11062 .当代主流的并行计算机是可扩放的吗？为什么？（p39,p88）答：是可扩放的；因为这些并行计算机的性能都可以随着处理器数的增加而按比例提高。63、在Amdahl定律中，串行分量、并行额外开销与加速的关系？84答：串行分量越大和并行额外开销越大，则加速越小10364、并行算法的设计与某一特定的并行计算模型关系如何?答：任何并行算法的设计都是基于某一特定的并行计算模型的，而并行计算模型都是从各种具体的并行机中抽象出来的，它能在一定程度上反