并行计算题目答案汇总

1、精选优质文档-倾情为你奉上第题（1）什么是并行计算？（2）它的优点有哪些？（3）可以通过哪些结构完成并行计算？1并行计算就是在并行计算或分布式计算机等高性能计算系统上所做的超级计算。（P3）2计算极大地增强了人们从事科学研究的能力，大大地加速了把科技转化为生产力的过程，深刻地改变着人类认识世界和改造世界的方法和途径。计算科学的理论和方法，作为新的研究手段和新的设计与创造技术的理论基础，正推动着当代科学与技术向纵深发展。（P4）3单指令多数据流SIMD、对称多处理机SMP、大规模并行处理机MPP、工作站机群COW、分布共享存储DSM多处理机。（P22）第2题什么是网络计算？它的特点？它与分布式计

2、算、集群计算的关系？（P104）网络计算：在工作站机群COW环境下进行的计算称为网络计算。特点：网络计算结合了客户机/服务器结构的健壮性、Internet面向全球的简易通用的数据访问方式和分布式对象的灵活性，提供了统一的跨平台开发环境，基于开放的和事实上的标准，把应用和数据的复杂性从桌面转移到智能化的网络和基于网络的服务器，给用户提供了对应用和信息的通用、快速的访问方式。与分布式计算、集群计算的关系：分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。集群计算是使用多

3、个计算机，如典型的个人计算机或UNIX工作站；多个存储设备；冗余互联，来组成一个对用户来说单一的高可用性的系统。因此，网络计算与分布式计算和集群计算都是属于计算密集型，数据密集型和网络密集型应用。第3题 表征并行系统的性能指标有哪些？并行系统的加速比如何定义？它能否完全确定系统的性能？为什么？a. 表征并行系统的性能指标主要有：CPU和存储器的基本性能指标，通信开销以及系统机器的成本、价格与性价比，还有系统加速比和系统可扩放性（p88页3.3）；其中CPU和存储器的基本性能指标包括：工作负载，并行执行时间，存储器的层次结构和存储器的带宽。b. 并行系统的加速比，是指对于一个给定的应用，并行算法

4、的执行速度相对于串行算法的执行速度另快了多少倍。c. 加速比并不能完全确定系统的性能；因为评价并行计算性能的指标，除了加速比外，并行计算的可扩放性也是主要性能指标之一即并行系统性能随处理器数的增加而按比例提高的能力。（个人理解的，大家参考第三章吧）第4题 节点度的定义？它在并行计算中的作用。（第9页）作用：百度也没找到答案。定义：射入或射出一个节点的边数称为节点度。 在单向网络中，入射和出射边之各称为节点度。第5题 等效率函数的定义、作用及应用。（P89）参考答案：为了维持一定的效率E（介于0与1之间），当处理器数p增大时，需要相应地增大问题规模W的值。由此定义函数为问题规模W随处理器数P变化

5、的函数，称此函数为等效率函数。等效率函数是等效率度量标准，而等效率度量是并行计算可扩放性评测的依据之一。应用举例：按照等效率函数的定义，对于某一并行算法（或并行程序），为了维护运行效率保持不变，随着处理器数目的增加，若只需增加较小的工作量（即问题规模），比如说W随p呈线性或亚线性增长，则表示该算法具有良好的可扩放性；若需要增加非常大的问题规模，比如说W随p呈指数级增长，则表示该算法是不可扩放的。第6题 6.1 等速度函数的定义，作用及应用？答：该题的答案在课本P90-P91面。可以自行参考课本复习。6.2 表面-容积效应的定义及应用？答：该题答案在课本P168面（2，3，4段）。同学们可以参考

6、复习。第7题 页数：P164全局通信：是指有很多任务参与交换数据的一种通信模式，全局通信中，每个任务与很多别的任务通信。局部通信：局部通信时，每个任务只与较少的几个近邻通信。结构化通信：结构化通信值，一个任务和其近邻形成规整结构（如树、网格等）。非结构化通信：非结构化通信中，通信网则可能是任意图。第8题 表面容积效应的定义、应用？（P168）答：定义是一个任务的通信需求比例于它所操作的子域的表面积，而计算需求却比例于子域的容积。其应用是：表面容积效应启发我们，在其他条件等同的情况下，高维分解一般更有效，因为相对于一个给定的容积（计算）它减少的表面积（通信），因此从效率的角度，增加力度的最好办法

7、是在所有的维组合任务。第9题 mpi编程模型中的基本通信概述MPI(Message Passing Interface)定义：MPI是94年5月发布的一种消息传递接口。它实际上是一个消息传递函数库的标志说明，吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一。具有的优点：具有可移植性和易用性，有完备的异步通信功能；有正式和详细的精确定义。何为通信体：在基于MPI编程模型中，计算是由一个或多个彼此调用库函数进行消息收、发通信的进程所组成。所谓通信体，就是一个进程组加上进程活动环境，其中进程组就是一组有限和有序的进程的集合。最基本的MPI：MPI_INIT:启动MPI计算；MPI_

8、FINALIZE:结束MPI计算；MPI_COMM_SIZE：确定进程数；MPI_COMM_RANK：确定自己的进程的标识符；MPI_SEND:发送一条消息；MPI_RECV:接受一条消息；群体通信：群体通信提供了MPI中独立的安全的消息传递。不同的通信库使用了独立的通信体，它隔离了内部和外部的通信，避免了在通信库被调用的和退出时的同步，也保证了在同一通信体的通信操作胡不干扰。点到点通信的数据传送有阻塞和非阻塞两者机制；阻塞和非阻塞有四种通信模式：1、标准模式；2、缓冲模式；3、同步模式；4、就绪模式；第10题 什么事共享存储并行编程?P323 第二段在共享存储的编程模式中,各个处理器可以对共

9、享存储器中的数据进行存取,数据对每个处理器而言都是可访问到的,不需要在处理器之间进行传送,即数据通信时通过读/写共享存储单元来完成.它的基本思路是什么? P323 第三段粗体字1任务划分; 2任务调度 2.1静态 调度2.1.1确定模式 2.1.2非确定模式 2.2动态调度 3任务同步 4任务通信.第11题 MPI基本函数有哪些？每一个函数的作用及使用？参考：352页。每一函数的作用：参考352353页 有六个基本函数 MPI_INIT ：启动MPI计算；MPI_FINALIZE：结束MPI计算；MPI_COMM_SIZE：确定进程数； MPI_COMM_RANK：确定自己的进程标识符；MPI

10、_SEND：发送一条消息；MPI_RECV：接收一条消息；第12题 找不到第13题 MPI的基本函数有哪些？每个函数的作用及使用？MPI 中有 1.double MPI_Wtime(void) 取得当前时间， 计时的精度有 double MPI_Wtick(void) 取得C/C+ time.h 有 clock_t clock(void) 取得当前时间， 计时的精度有 常数 CLOCKS_PER_SEC 定义。2.Int MPI_Init(int *argc ,char *argv)MPI的初始化例行函数，用于初始化MPI运行的环境，必须调用，还是首先调用，仅调用一次。3.MPI_Finali

11、ze(void) 结束MPI执行的环境，该函数一旦被调用，就不能调用MPI的其它的函数（包括MPI_init）4.MPI_Send(void *buf,int count,MPI_Datatype datatype,int dest,int tag,MPI_Comm comm)将缓冲区的count个datatype数据类型的数据发送到目的进程阻塞型：需要等待指定的操作的实际完成，或至少所涉及的数据被MPI系统完全的备份后才返回 如：MPI_Send和MPI_Recv都是阻塞型的。5.MPI_Recv(void *buf,int count,MPI_Datatype datatype,int s

12、ource,int tag,MPI_Comm comm.,MPI_Status *status)从指定进程source接收信息，并且该数据的类型和本接收进程指定的数据类行一样6.MPI_Isend(void *buf,int count,MPI_Datatype datatype,int dest,int tag,MPI_Comm comm.,MPI_Requst *request)非阻塞地发送信息。在发送数据完成之前，对数据操作是把安全的，因为随时可能与正在后台执行的MPI操作发生冲突。所以用户使用非阻塞型发送数据必须调用其他函数来等待或查询操作完成的情况。该函数递交一个信息发送的请求MPI

13、系统在后台完成消息的发送，请求的句柄通过Request变量返回给MPI进程，供随后查询/等待消息的完成用注意：阻塞型和非阻塞型相差一个I。7.MPI_Wait(MPI_Request *request,MPI_Status *status) 通信请求的完成与检测MPI_Wait是阻塞型函数，必须等待通信的完成才返回。该检测函数等待，检测一个通信器请求的完成成功返回时，status中包含关于所完成的通信的信息，相应的通信请求被释放，request被程MPI_REQUST_NULL。8.MPI_Test(MPI_Request *request,int *flag,MPI_Status *stat

14、us)MPI_TEST 与MPI_Wait刚好相反的。MPI_TEST是非阻塞函数该函数检测指定的通信请求，不论通信是否完成都立刻返回9.MPI_Iprobe(int source ,int tag,MPI_Comm comm.,int *flag,MPI_Status *status)消息的探测函数 是属于非阻塞函数，它不论是否有符合条件的消息都立刻返回10.MPI_Probe(int source ,int tag,MPI_Comm comm.,MPI_Status *status) 消息的探测检查要接收的信息是否到达 信息到达了才能返回MPI_Probe属于阻塞型函数，它等待直到一个符合

15、条件的消息到达后才返回如果探测到符合条件的消息flag=true，否则flag=false11.MPI_Get_count(MPI_Status *status,MPI_Datatype datatype,int *count) 该函数返回以指定的数据类型为单位，接收到数据的个数，接收信息是使用的是最大个数，搞函数准确地知道接收信息的个数12.MPI_Type_contiguous(int count,MPI_Datatype oldtype,MPI_Datatype *newtype)新数据类型newtype由count个老数据类型olodtype按域（extent）连续存放构成.新定义数据

16、类型函数。如：count=5，OLDTYPE=INYTRGER，则新的数据类型NEWTYPE为5个整数13.MPI_Type_vector(int count,int blocklength,int stride,MPI_Datatype oldtype,MPI_Datatype *newtype)新数据类型newtype由count个数据块构成。每个数据块由blockelength个连续存放的oldtype构成。相邻的两个数据块的位移相差stride x extent（oldtype）个字节新定义数据类型 如：count=3，BLOCKLENGTH=2，STRIDE=3，OLDTYPE=IN

17、TEGER，则调用此函数后得到的新的数据类型NEWTYPE为6个整数组成，其中在原始数组中从开始取2个隔1隔再取2个，再隔一个取2个构成14.MPI_Type_indexed(int count,int array_of_blocklengths,int *array_of_displacements,MPI_Datatype, oldtype,MPI_Datatype *newtype)新的数据类型newtype由count个数据块构成，第i个数据块包含arry_of_blocklengths(i)个连续存放的oldtype，字节位移为arry_of_displacements(i)*ext

18、ent(oldtype)。ARRAY_OF_BLOCKLENTHS和ARRAY_OF_DLSPLACEMENRS由OLDTYPE定义的元素个数来度量注意：MPI_Type_indexed与MPI_Type_vector的区别在每个数据块的长度可以不同，数据块间也可以不等距15.MPI_Type_commit(MPI_Datatype *datatype)提交数据类型，一个数据类型被提交之后就可以和MPI的原始数据类型完全一样地在消息传递中使用使用自定义的数据类型之前，必须调用此函数16.MPI_Type_free(MPI_Datatype *datatype)释放指定的数据类型。函数返回后。D

19、atatype将被置成MPI_DATATYPE_NULL。17.MPI_Barrier(MPI_Comm comm)该函数用于进程间的同步。一个进程调用该函数后将等待直到通信器comm中的所有进程都调用了该函数才返回18.MPI_Bcast(void *buffer,int count,MPI_Datatype datatype,int root,MPI_Comm comm)广播数据 通信器comm中进程号为root的进程（根进程）将自己buffer中的内容同时发送给通信器的所有其他的进程。19.MPI_Gather(void *sendbuf,int sendcount,MPI_Dataty

20、pe sendtype,void *recvbuf,int recvcount,MPI_Datatype recvtype,int root,MPI_Comm comm)收集数据 所有进程（包括根进程）将sendbuf中的数据发送给根进程。根进程将这些数据按进程号的顺序依次接收到recvbuf中，发送数据和接收的数据类型与长度必须相匹配。即发送的类型必须具有相同的序列。20.MPI_Scatter(void *sendbuf,int sendcount,MPI_Datatype sendtype,void *recvbuf,int recvcount,MPI_Datatype recvtype

21、 ,int root, MPI_Comm comm)分散数据。指根进程将一个大的数据块分成小块分别散发给各个进程（包括根进程自己）它是数据收集的逆操作21.MPI_Allgather(void *sendbuf,int sendcount,MPI_Datatype sendtype,void *recvbuf,int recvcount,MPI_Datatype recvtype ,MPI_Comm comm)22.MPI_Alltoall(void *sendbuf,int sendcount,MPI_Datatype sendtype,void *recvbuf,int recvcount

22、,MPI_datatype recvtype ,MPI_Comm comm)全部到全部 每个进程散发自己的一个数据块，并且收集并装所有进程散发过来的数据块，我们称该操作为数据的“全散发收集”，它既被认为是数据的全收集的扩展，也可以被认为是数据的散发扩展。23.MPI_Reduce(void *sendbuf ,void *recvbuf,int count,MPI_Datatype datatype,MPI_Op op ,Int root,MPI_Comm comm)在组内所有的进程中，执行一个规约操作，并把结果存放在指定的进程中24.MPI_Allreduce(void *sendbuf ,

23、Void *recvbuf,int count,MPI_Datatype datatype,MPI_Op op,MPI_Comm comm)全规约25.MPI_Comm_size(MPI_Comm comm.,int *size) 该函数返回与该组通信因子相关的进程数26.MPI_Comm_rank(MPI_Comm comm.,int *rank)该函数返回该进程在指定通信因子中的进程号，每个进程在不同的通信因子中的进程号可能不同。27.MPI_Comm_dup(MPI_Comm comm.,MPI_Comm * newcomm)复制通信因子到newcomm，若复制comm被破坏，原来的co

24、mm仍然保存28.MPI_Comm_split(MPI_Comm comm.,int color,int key,MPI_Comm* newcomm)该函数划分comm所对应的进程组为不相交的字进程组，每个进程组中包含color相同的所有的进程29.MPI_Comm_free(MPI_Comm *comm) 释放通信因子30.MPI_Intercomm_create(MPI_Comm local_comm,int local_leader.MPI_Comm peer_comm,int remote_leader,int tag,MPI_Comm *newintercomm)第14题 倍增设计技

25、术与流水线设计技术的定义和异同？P151倍增技术又叫指针跳跃技术，特别适合处理以链表或有向有根数之类表示的数据结构。每当递归调用时，所要处理的数据之间的距离将逐步加倍，经过K步后就可完成距离2的k次方的所有数据的计算。流水线技术基本思想是将一个计算任务t分成一系列子任务t1，t2，tm使得一旦t1完成，后继的子任务就可立即开始，并以同样的速率进行计算。第15题 什么是PVP、MPP、COW？它们的异同点。PVP并行向量处理机MPP大规模并行处理机，它是指由成百上千乃至上万个处理器组成的大型计算机系统。COW工作站机群，指的是并行计算系统将一群工作站用某种结构的网络互连起来，充分利用各工作站的资

26、源，统一调度、协调处理，以实现高效并行计算。异同点：（P25）属性PVPMPPCOW结构类型MIMDMIMDMIMD处理器类型专用定制商用商用互连网络定制交叉开关定制网络商用网络通信机制共享变量消息传递消息传递地址空间单地址空间多地址空间多地址空间系统存储器集中共享分布非共享分布非共享访存模型UMANORMANORMA代表机器Cray C-90，Cray T-90，银河1号IntelParagon,IBMOption White曙光-1000/2000Berkeley NOW，Alpha Farm第16题 SMP的特点及应用结构？P40 答：共享存储的SMP系统结构具有如下特怀：对称性、单地址

27、空间 、高速缓存及其一致性、低通信延迟 缺点：欠可靠、可观的延迟、慢速增加的带宽、不可扩放性总线或交叉开关P/CP/CP/CSMSMI/O66应用结构：P24SMP系统使用商品微处理器（具有片上或外置高速缓存），它们经由高速总线（或交叉开关）连向共享存储器。其系统是对称的，每个处理器可等同地访问共享存储器、I/O设备和操作系统服务！结构如下所示：P23第17题：Amdahl定律主要内容？ 应用范围及主要结论？ Gustafson定律主要内容？ 应用范围及主要结论？Sun和Ni定律主要内容？ 应用范围及主要结论？以上三个定律之间的异同点？ 解：(P83 至 P88)1）Amdah1定律主要内容：

28、P83 固定负载的加速公式：应用范围及主要结论：应用范围：对于很多科学计算，实时性要求很高，即在有些类应用中时间是个关键因素，而计算负载是固定不变的。主要结论：意味着随着处理器数目的无限增大，并行系统所能达到的加速之上限为1/f.2）Gustafson 定律： P85应用范围及主要结论：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。它意味着随着处理器数目的增加，加速几乎与处理器数成比例的线性增加，串行比例f不再是程序的瓶颈，这对并行系统的发展是个非常乐观的结论。2）Sun和Ni定律: P86 应用范围及主要结论：只要存储空间许可，应尽量增大问题规模以产

29、生更好和更精确的解（此时可能使执行时间略有增加）。主要结论：G（p）=1时就是Amdahl加速定律； G（p）=p 变为 f + p（1-f），就是Gustafson加速定律G（p）p，相应于计算机负载比存储要求增加得快，此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。第18题 并行编程模型有哪些？它们中每一种模型的特点？应用范围？PRAM模型 P109-110 异步PRAM模型 P110-111 BSP模型 P111-113 logP模型 P113-115第19题 什么是并行计算的系统结构模型？他的分类？每一种系统结构模型的主要特点？比较它们的异同点？目

30、前常用的有哪些结构模型？为什么？1什么是并行计算的系统结构模型？答：没有找到2他的分类？(P22)答：并行计算的系统结构分两大类：单指令多数据流SIMD和多指令多数据流MIMD；其中多指令多数据流MIMD包括：并行向量处理机PVP、对称多处理机SMP、大规模并行处理机MPP、工作站机群COW和分布共享存储DSM多处理机。3每一种系统结构模型的主要特点？(P22-P24)PVP：课本没有讲到（平行向量处理机最大的特点是系统中的CPU是专门定制的（VP）。系统还提供共享存储器以及与VP相连的高速交叉开关维基百科）SMP：课本没有讲到（对称多处理机最主要的特征是系统的对称性，即每个可以以同等代价访问

31、各个共享存储器维基百科）MPP：（P24第二段）它具有如下特性：a. 处理节点采用商用处理器；b. 系统中有物理上的分布式存储器；c. 采用高通信带宽和低延迟的互联网络（专门设计和定制的）；d. 能扩放至成百上千乃至上万个处理器。e. 它是一种异步的机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息互相作用。DSM：课本没有讲到，网络没找到COW：（P24第四段）COW的重要界限和特征是：a. COW的每个节点都是一个完整的工作站，这样的节点有时叫作“无头工作站”，一个节点也可以是一台PC或SMP；各节点通过一种低成本的商品（标准）网络（如以太网、FDDI和开关等）互连（有

32、的商用机群也使用定做的网络）；给节点内总是有本地磁盘，而节点却没有；节点内的网络接口是松散耦合到IO总线上的，而MPP内的网络接口是连到处理器节点的存储总线上的，因而可以是紧耦合式的；一个完整的操作系统驻留在每个节点中，而MPP中通常只是个微核，COW的操作系统是工作站，加上一个附加的软软件层，以支持单一系统镜像、并行度、通信和负载平衡等。目前常用的有哪些结构模型？为什么？答：课本没讲（最后一段，机群相对于有性能价格比高的优势，所以在发展可扩放并行计算机方面呼声很高。）第20题 什么是串行程序设计？（286页，第二段）它的优缺点？（286页，第三段，点）并行程序设计与串行程序设计的异同点？（2

33、87页，表12.1）为什么从串行程序设计会发展到并行程序设计？（没找到） 能否以一个样例程序来分析？（没找到）第21题 并行计算的性能评测分类与作用：P78全页，P88第二段第22题 试分析在现今科技及经济社会发展中，有哪些并行需求的模型1计算密集型 2 数据密集型 3 网络密集型第23 题 什么是并行计算的性能评测？它有什么作用？分作哪几类？说说每一类性能测评的思路、特点。答：并行计算的性能评测与并行计算机体系结构、并行算法和并行程序设计一道构成了并行研究的四大分支。它是指依据某些性能指对并行计算的性能进行评估和测试。并行计算的性能与所使用的并行计算机本身的性能有关。大致可分为机器级的性能评

34、测、算法级的性能评测和程序级的性能评测。机器机的性能评测主要包括CPU和存储器的成本、价格和性/价比等；算法级的性能评测主要包括加速、效率和可扩放性等；程序级的性能评测主要包括基本测试程序、数学库测试程序和并行测试程序等。（77页）第24题 并行算法的基本设计技术？它又如何分类？每一类的定义？特点和思路？（P140）基本技术：划分设计技术，分治设计技术，平衡树设计技术，倍增设计技术，流水线设计技术如何分类：从使用并行处理操作最朴素的思想出发，就可以导出所谓划分设计技术，它是将一原始问题分成若干个部分，然后各部分由响应的处理器同时执行。从求解问题的方法学和求解策略出发，则可导出所谓分治设计技术，

35、它是将是一个大而复杂的问题分解成若干个特性相同的子问题，然后使用各个击破的方法求解之。从针对求解问题的特性出发，也可导出一些有效的并行算法设计技术，包括平衡树技术和倍增技术等。每一类的定义、特点、思路：划分设计技术：P140，分治设计技术：P144，平衡树设计技术：P149，倍增设计技术：P151 流水线设计技术：P153第25题 概括对共享存储单元间的读/写的限制。可以如何对并行存储访问模型分类？各类模型的主要特点？答：高速缓存目录DIR用以支持分布高速缓存的一致性，在物理上有分布在各节点的局存，从而形成了一个共享的存储器。对用户而言，系统硬件和软件提供了一个单地址的编程空间。模型分类：（）

36、均匀存储访问。特点：1、物理存储器被所有处理器均匀共享 2、所有处理器访问任何存储单元取相同的时间3、每台处理器可带私有高速缓存 4、外围设备也可以以一定形式共享（）非均匀存储访问特点：1、被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间2、处理器访问存储器的时间是不一样的3、每台处理器照例可私带有高速缓存，且外设也可以以某种形式共享。COMA（CacheOnly Memory Access）全高速缓存访问特点1）各处理器节点没有存储层次结构，全部高速缓存组成了全局地址空间2）利用分布的高速缓存目录D进行远程高速缓存的访问3）中的高速缓存容量一般都大于

37、级高速缓存容量）使用COMA时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用它的地方。CCNUMA（CoherentCache）高速缓存一致性非均匀存储访问特点：（） 绝大多数商用CCNUMA多处理机系统都使用基于目录的高速缓存一致性协议（） 它在保留SMP结构易于编程的优点的同时，也改善了常规SMP的可扩放性问题（） CCNUMA实际上是一个分布共享存储的多处理机系统（） 它最显著的优点是程序员无需明确地在节点上分配数据。（）非远程存储访问特点1.所有存储器均是私有的 2.绝大多数都不支持远程存储器的访问 3.在中，就消失了。页码：页第26题 并行算法的基本设计技术？它又如何分类？

38、每一类的定义？特点与思路？并行算法的基本设计技术：从使用并行处理操作最朴素的思想出发，就可导出所谓划分设计技术，它是将一问题分成若干个部分，然后各部分由相应的处理器同时执行，这就是最基本的设计技术。它的分类：均匀划分技术、方根划分技术、对数划分技术、功能划分技术。均匀划分技术定义、特点与思路（140页 6.1.1）方根划分技术定义、特点与思路（141页 6.1.2）对数划分技术定义、特点与思路（142页 6.1.3）功能划分技术定义、特点与思路（143页 6.1.4）第27题 如何对并行算法的设计过程分步？每一步的主要内容是什么？P161162答：首先尽量开拓算法的并行性和满足算法的可扩放性；

39、然后着重优化算法的通信成本和全局执行时间，同时通过必要的整个过程的反复回溯，以期最终达到一个满意的设计选择。也即分为四步：任务划分、通信分析、任务组合和处理器映射。划分：将整个计算分解成一些小的任务，其目的是尽量开拓并行执行的机会通信：确定诸任务执行中所需交换的数据和协调诸任务的执行，由此可检测上述划分的合理性组合：按性能要求和实现的代价来考察前两阶段的结果，必要时可将一些小的任务组合成更大的任务以提高性能或减少通信开销映射：将每个任务分配到一个处理器上，其目的是最小化全局执行时间和通信成本以及最大化处理器的利用率第28题 在矩阵划分中，有哪些划分方法？每一方法的细节内容？(课本202页)答：

40、（1）在矩阵划分中，有两种常见的划分方法：带状划分（又称行列划分）和棋盘划分（又称块状划分）。 （2）带状划分的细节内容：带状划分分为块带状划分和循环带状划分。所谓块状带状划分，就是将矩阵整行或整列地分成若干个组，每组指派给一个处理器。所谓循环带状划分，就是将若干行或若干列指派给一个处理器，而且这些行和列可以是连续的，也可以是等距相间。 棋盘划分的细节内容：所谓棋盘划分，就是将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此时任一处理器均不包含整行或整列。棋盘划分分为块棋盘划分和循环棋盘划分。矩阵划分成棋盘状可和处理器连成二维网孔相对应。和带状划分相比，棋盘划分可开发更高的并行度。第29

41、题 并行计算中，点到点通信的含义？测量方法及方法的内容？点到点通信是指两台之间相互交换信息，它具有安全、快捷、直观、同步和经济的特点（网上概念）P359第30题 系统的可扩放性与算法的可扩放性的定义是？特点是？ 评价并行计算性能的指标之一，在确定的应用背景下，计算机系统性能随处理器数的增加而按比例提高的能力。一般情况下，增加处理器数，是会增大额外开销和降低处理器的利用率的，所以对于一个特定的并行系统、并行算法货并行程序，它们能否有效利用不断增加的处理器的能力影视受限的，度量这种能力就是可扩放性。可扩放性是算法和结构的组合。 p86第31题 什么是并行算法的复杂度？复杂度作用？可以通过哪些指标来

42、分析？（复杂度的概念在课本并没有找到，以下为百度并个人总结后的答案）概念：并行算法复杂度指执行并行算法时计算机所需占用消耗的资源。作用：复杂度用来衡量一个算法的优劣，以便选择合适算法和改进算法。通过以下几个指标（第106页）1、运行时间t(n)：即算法运行在给定模型上求解问题所需的时间，通常包含计算时间和通信时间。2、处理器数p(n)：求解给定问题所用的处理器数目3、并行算法的成本c(n)：定义为算法运行时间t(n)与所需处理器数p(n)的乘积，即c(n)=t(n)*p(n)4、总运算量W(n)：即并行算法所完成的总的操作数量。第32题 在并行计算中，有哪些方法可以实现同步？什么是同步？它有什

43、么作用？参考答案：有同步（Synchronization）是在时间上强使各执行进程在某一点必须相互等待。在并行计算的各进程异步执行过程中为了确保各处理器的正确工作顺序以及对共享可写数据的正确访问（互斥访问），程序员需在算法的适当点设置同步点。同步可用软件、硬件和固件的办法来实现，如，在logP模型中的路障是由硬件支持的；在MIMD-SM多处理器系统中用同步语句lock和unlock来确保对共享可写数据的互斥访问。（P107）第33题 现有哪些并行编程的风格？每一种特点？答：本人认为该题答案在课本P290面。不过不是十分的肯定。共有五种并行编程的风范：第一：相并行；第二：分治并行；第三：流水线并

44、行；第四：主-从并行；第五：工作池并行每一种的特点书里面P290 面有详细的解释，可以参考复习。第34题 论述并行软件与并行硬件发展的关系？（P286）答：关系：1、并行软件的发展落后于并行硬件；2、和串行系统的应用软件相比，现今的并行系统甚少且不成熟；3、并行软件的缺乏是发展并行计算的主要障碍；4、不幸的是，这种状态似乎仍在继续着。第35题 现有哪些并行编程风范 每一种的特点现在主要有以下机制并行编程规范：一：OpenMP编程是基于线程的并行编程模型；一个共享存储的进程由多个线程组成，OpenMP就是基于已有的线程共享编程模型；其次OpenMP是一个外部的编程模型，而不是自动编程的模型。特点

45、是:简单，移植性好，可扩展性好等；二：MPI并行编程；特点以下：具有可移植性和易用性；具有完备的异步通信功能；有正式和详细的精确地定义。三：PVM（parallel virtual machine)并行编程:较为容易修改。四：基于数据并行的并行编程：能对大量的数据进行相同的，彼此独立的操作。五：HPF（high performance Fortran）并行编程；特点：1、数据并行制导，2、数据映射制导，3、新内部函数和库函数；第36题 找不到第37题 什么是PCAM设计方法学？它包括哪些内容？ 参考：160页PCMA：从给定问题的描述出发，通过四个步骤，即任务划分、通信分析、任务组合和处理器映

46、射，最终设计出一个能展示出并发性、可扩放行、局部性和模块性的并行算法。此过程简称为PCAM设计过程，它是一种设计方法学。内容参考书本：第七章第38题 网络结构的对称与非对称判定？各自特点？（找不到）第39题 什么是PCAM设计方法学，它包括哪些内容？不同阶段，主要完成的任务？P160P161 答：PCAM设计方法学是实际设计并行算法的自然过程。其基本要点是：首先尽量开拓算法的并发性和满足算法的可扩放性，然后着重优化算法的通信成本和全局执行时间，同时通过必要的整个过程的反复回溯，以期最终达到一个满意的设计选择。PCAM是 Partitioning 、Communication 、Agglomeration 和Mapping首字母的拼写，它们代表了使用此法设计并行算法的四个阶段！这四个阶段包括：划分、通信、组合、映射。在设计的第一和第二阶段，关注的是并发性和可扩放性，并寻求开发出具有这些特性的并行算法。在设计的第三和第四阶段，把注意力转移到局部和别的与性能有关的问题上。第题并行编程工具与串行编程工具的发展关系？答：没有找到。第41题 一到一传输：是指开始时p（处理器）中保存的信包m，只能按照播送路线发送到临近的一个处理器，然后再通过该处理器发送到下一个处理器，最后将信包