并行计算题目答案汇总文档格式.docx

并行计算题目答案汇总文档格式.docx

《并行计算题目答案汇总文档格式.docx》由会员分享，可在线阅读，更多相关《并行计算题目答案汇总文档格式.docx（23页珍藏版）》请在冰点文库上搜索。

在单向网络中，入射和出射边之各称为节点度。

第5题等效率函数的定义、作用及应用。

（P89）参考答案：

为了维持一定的效率E（介于0与1之间），当处理器数p增大时，需要相应地增大问题规模W的值。

由此定义函数fE（P）为问题规模W随处理器数P变化的函数，称此函数为等效率函数,，等效率函数是等效率度量标准，而等效率度量是并行计算可扩放性评测的依据之一。

应用举例：

按照等效率函数的定义，对于某一并行算法（或并行程序），为了维护运行效率保持不变，随着处理器数目的增加，若只需增加较小的工作量（即问题规模），比如说W随p呈线性或亚线性增长，则表示该算法具有良好的可扩放性；

若需要增加非常大的问题规模，比如说W随p呈指数级增长，则表示该算法是不可扩放的。

笫6題

等速度函数的定义，作用及应用答：

该题的答案在课本P90-P91面。

可以自行参考课本复习。

表面-容积效应的定义及应用答：

该题答案在课本P168面（2,3,4段）。

同学们可以参考复习。

笫7題页数：

P164

全局通信：

是指有很多任务参与交换数据的一种通信模式，全局通信中，每个任务与很多别的任务通信。

局部通信：

局部通信时，每个任务只与较少的几个近邻通信。

结构化通信：

结构化通信值，一个任务和其近邻形成规整结构（如树、网格等）。

非结构化通信：

非结构化通信中，通信网则可能是任意图。

笫8題表面一容积效应的定义、应用（P168）

答：

定义是一个任务的通信需求比例于它所操作的子域的表面积，而计算需求却比例于子域的容积。

其应用是：

表面—容积效应启发我们，在其他条件等同的情况下，高维分解一般更有效，因为相对于一个给定的容积（计算）它减少的表面积（通信），因此从效率的角度，增加力度的最好办法是在所有的维组合任务。

笫9題mpi编程模型中的基本通信概述

MPI（MessagePassingInterface）定义：

MPI是94年5月发布的一种消息传递接口。

它实际上是一个消息传递函数库的标志说明，吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一。

具有的优点：

具有可移植性和易用性，有完备的异步通信功能；

有正式和详细的精确定义。

何为通信体：

在基于MPI编程模型中，计算是由一个或多个彼此调用库函数进行消息收、发通信的进程所组成。

所谓通信体，就是一个进程组加上进程活动环境，其中进程组就是一组有限和有序的进程的集合。

最基本的MPI：

MPIINIT：

启动MPI计算;

MPIFINALIZE：

结束MPI计算;

MPI_COMMSIZE：

确定进程数；

MPICOMMRANK：

确定自己的进程的标识符；

MPISEND：

发送一条消息;

MPIRECV：

接受一条消息；

群体通信:

群体通信提供了MPI中独立的安全的消息传递。

不同的通信库使用了独立的通信依，它隔离了内部和外部的通信，避免了在通信库被调用的和退出时的同步，也保证了在同一通信体的通信操作胡不干扰。

点到点通信的数据传送有阻塞和非阻塞两者机制；

阻塞和非阻塞有四种通信模式：

1、标准模式；

2、缓冲模式；

3、同步模式；

4、就绪模式；

笫10题什么寧共享存储并行编程P323第二段

在共享存储的编程模式中，各个处理器可以对共享存储器中的数据进行存取，数据对每个处理器而言都是可访问到

的，不需要在处理器之间进行传送，即数据通信时通过读/写共享存储单元来完成.

它的基本思路是什么P323第三段粗体字

1任务划分；

2任务调度静态调度2.1.1确定模式2.1.2非确定模式动态调度3.任务同步4任务通信.

笫11题MPI基本函数有哪些每一个函数的作用及使用

参考：

352页。

每一函数的作用：

参考352〜353页

①有六个基本函数

MPIINIT:

启动MPI计算；

MPICOMMSIZE：

确定进程数;

确定自己的进程标识符；

MPI_SEND：

发送一条消息；

MPI_RECV：

接收一条消息；

第12题找不到

第13题MPI的基本函数有哪些每个函数的作用及使用

MPI中有

MPI_Wtime（void）取得当前时间，计时的精度有doubleMPIWtick（void）取得

C/C++有clock.tclock（void）取得当前时间，计时的精度有常数CLOCKS_PERSEC定义。

MPI_Init（int*argc,char***argv）

MPI的初始化例行函数，用于初始化MPI运行的环境，必须调用，还是首先调用，仅调用一次。

（void）结束MPI执行的环境，该函数一旦被调用，就不能调用MPI的其它的函数（包括MPIinit）

（void*buf,intcount,MPIDatatypedatatype,intdest,inttag,MPICommcomm）

将缓冲区的count个datatype数据类型的数据发送到目的进程阻塞型：

需要等待指定的操作的实际完成，或至少所涉及的数据被MPI系统

完全的备份后才返回如：

MPISend和MPI_Recv都是阻塞型的。

（void*buf,intcount,MPIDatatypedatatype,intsource,inttag,MPICommcomm.,MPIStatus*status）

从指定进程source接收信息，并且该数据的类型和本接收进程指定的数据类行一样

（void*buf,intcount,MPIDatatypedatatype,intdest,inttag,MPI.Commcomm.,MPIRequst*request）

非阻塞地发送信息。

在发送数据完成之前，对数据操作是把安全的，因为随时可能与正

在后台执行的MPI操作发生冲突。

所以用户使用非阻塞型发送数据必须调用其他函数

来等待或查询操作完成的情况。

该函数递交一个信息发送的请求MPI系统在后台完成消息的发送，请求的句柄通过

Request变疑返回给MPI进程，供随后查询/等待消息的完成用

注意：

阻塞型和非阻塞型相差一个I。

（MPIRequest*request,MPIStatus*status）

通信请求的完成与检测

MPI.Wait是阻塞型函数，必须等待通信的完成才返回。

该检测函数等待，检测一个通信器请求的完成

成功返回时，status中包含关于所完成的通信的信息，相应的通信请求被释放，request被程MPIREQUST一NULL。

（MPIRequest*request,int*flag.MPIStatus*status）

MPITEST与MPIWait刚好相反的。

MPI一TEST是非阻塞函数

该函数检测指定的通信请求，不论通信是否完成都立刻返回

（intsource,inttag,MPICommcomm.,int*flag,MPIStatus*status）

消息的探测函数是属于非阻塞函数，它不论是否有符合条件的消息都立刻返回

（intsource,inttag,MPICommcomm.,MPIStatus*status）消息的探测

检查要接收的信息是否到达信息到达了才能返回

MPI.Probe属于阻塞型函数，它等待直到一个符合条件的消息到达后才返回

如果探测到符合条件的消息flag=true,否则flag=false

函数类型

通信模式

HQ塞型

非阴塞型

标准模式

MPLScnd

MPLIscnd

消息发送说数

缓冲模武

MPlIbwncl

同步模式

MPJSsend

MPI」

就绪模或

MPIRsend

MFLIrund

MPlRecv

MPI^Irccv

消息給泗函数

MPIPrube

MFI」probe

MPIWait

MPLTest

MPLWaitall

纱I_Tc初1

N4PIWaiiany

MPlTesiany

MPITes（snme

徉放通信请求

MPIRequeufree

取消通信

MPI—Cancel

MPJTestcancelle<

l

（MPIStatus*statusfMPIDatatypedatatype,int*count）该函数返回以指定的数掲类型为单位，接收到数据的个数，接收信息是使用的是最大个数，搞函数准确地知道接收信息的个数

（intcount,MPIDatatypeoldtype,MPIDatatype*newtype）

新数据类型newtype由count个老数据类型olodtype按域（extent）连续存放构成

•新定义数据类型函数。

如：

count=5,0LDTYPE二INYTRGER,则新的数据类型NEWTYPE为5个整数

（intcount,intblocklength,intstride,MPIDatatypeoldtype.MPIDatatype*newtype）

新数据类型newtype由count个数据块构成。

每个数据块由blockelength个连续存放的oldtype构成。

相邻的两个数据块的位移相差stridexextent（oldtype）个字节

新定义数据类型如count=3,BLOCKLENGTH二2,STRIDE二3,OLDTYPE二INTEGER,则调用此函数后得到的新的数据类型NEWTYPE为6个整数组成，其中在原始数组中从开始取2个隔1隔再取2个，再隔一个取2个构成

14・・MPI_Type__indexed（intcount,intarrayofblocklengths.int*arrayofdisplacements,MPIDatatype,oldtype,MPIDatatype*newtype）

新的数捋类型newtype由count个数据块构成，第i个数据块包含arryofblocklengths（i）个连续存放的oldtype,字节位移为arryof_displacements（i）*extent（oldtype）o

ARRAYOFBLOCKLENTHS和ARRAYOFDLSPLACEMENRS由OLDTYPE定义的元素个数来度疑

MPITypeindexed与MPITypevector的区别在每个数据块的长度可以不同，数据块间也可以不等距

15..MPI_Type_commit（MPIDatatype*datatype）

提交数据类型，一个数据类型被提交之后就可以和MPI的原始数据类型完全一样地在消息传递中使用使用自定义的数据类型之前，必须调用此函数

16..MPI_Type_free（MPIDatatype*datatype）

释放指定的数据类型。

函数返回后。

Datatype将被置成MPIDATATYPE.NULLo

17..MPIBarrier（MPICommcomm）

•MM

该函数用于进程间的同步。

一个进程调用该函数后将等待直到通信器comm中的所有进程都调用了该函数才返回

18..MPI_Bcast（void*buffer,intcount,MPIDatatypedatatype,introot,MPICommcomm）

广播数据通信器comm中进程号为root的进程（根进程）将自己buffer中的内容同时发送给通信器的所有其他的进程。

19・・MPI_Gather（void*sendbuf,intsendcount.MPIDatatypesendtype,void*recvbuftint

recvcount,MPIDatatyperecvtype,introot,MPICommcomm）

收集数据所有进程（包括根进程）将sendbuf中的数据发送给根进程。

根进程将这些数据按进程号的顺序依次接收到recvbuf中，发送数据和接收的数据类型与长度必须相匹配。

即发送的类型必须具有相同的序列。

20・・MPI_Scatter（void*sendbuf■intsendcount,MPIDatatypesendtype,void*recvbuftint

recvcounttMPIDatatyperecvtype,introottMPICommcomm）

分散数据。

指根进程将一个大的数据块分成小块分别散发给各个进程（包括根进程自己）

它是数摇收集的逆操作

（void*sendbuf,intsendcount,MPIDatatypesendtype,void*recvbuf,intrecvcount,MPIDatatype

recvtypetMPICommcomm）

（void*sendbuf,intsendcount,MPIDatatypesendtype,void*recvbuftintrecvcount,MPI_datatype

全部到全部每个进程散发自己的一个数据块，并且收集并装所有进程散发过来的数据块，我们称该操作为数据的“全散发收集”，它既被认为是数据的全收集的扩展，也可以被认为是数据的散发扩展。

（void*sendbuf,void*recvbuf,intcount,MPI_Datatypedatatype,MPIOpop.

IntroottMPLCommcomm）

在组内所有的进程中，执行一个规约操作，并把结果存敖在指定的进程中

（void*sendbuf,Void*recvbuf,intcount,MPIDatatypedatatype,MPIOpop,MPICommcomm）

全规约

（MPICommcomm.,int*size）该函数返回与该组通信因子相关的进程数（MPICommcomm.,int*rank）该函数返回该进程在指定通信因子中的进程号，每个进程在不同的通信因子中的进程号可能不同。

（MPICommcomm・.MPI_Comm*newcomm）

复制通信因子到newcomm,若复制comm被破坏，原来的comm仍然保存

（MPICommcomm・，intcolor,intkey,MPIComm*newcomm）

该函数划分comm所对应的进程组为不相交的字进程组，每个进程组中包含color相同的所有的进程

（MPIComm*comm）释放通信因子

（MPICommlocalcomm,intpeercomm,intremoteleader,inttag.MPIComm*newintercomm）

笫14题倍增设计技术与流水线设计技术的定义和异同P151

倍增技术又叫指针跳跃技术，特别适合处理以链表或有向有根数之类表示的数据结构。

每当递归调用时，所要处理的

数据之间的距离将逐步加倍，经过K步后就可完成距离2的k次方的所有数据的计算。

流水线技术基本思想是将一个计算任务t分成一系列子任务tl,t2,・・・，使得一旦tl完成，后继的子任务就可立即开始，并以同样的速率进行计算。

笫15題什么是PVP、MPP,COW它们的异同点。

PVP——并行向量处理机

MPP——大规模并行处理机，它是指由成百上千乃至上万个处理器组成的大型计算机系统。

COW——工作站机群，指的是并行计算系统将一群工作站用某种结构的网络互连起来，充分利用各工作站的资源，统一调度、协调处理，以实现高效并行计算。

异同点：

（P25）

属性

PVP

MPP

COW

结构类型

MIMD

处理器类型

专用定制

商用

互连网络

定制交叉开关

定制网络

商用网络

通信机制

共享变量

消息传递

地址空间

单地址空间

多地址空间

系统存储器

集中共享

分布非共享

访存模型

UMA

NORMA

第16题SMP的特点及应用结构P40

共享存储的SMP系统结构具有如下特怀：

对称性、单地址空间、高速缓存及其一致性.低通信延迟

缺点：

欠可靠.可观的延迟、慢速增加的带宽、不可扩放性

应用结构：

P24

SMP系统使用商品微处理器（具有片上或外置高速缓存），它们经由高速总线（或交叉开关）连向共享存储器。

第17题：

Amdahl定律主要内容应用范围及主要结论

Gustafson定律主要内容应用范围及主要结论

Sun和Ni定律主要内容应用范围及主要结论

以上三个定律之间的异同点

M：

（P83至P88）

1）Amdahl定律主要内容：

P83

应用范围及主要结论:

应用范围：

对于很多科学计算，实时性要求很高，即在有些类应用中时间是个关键因素，而计算负载是固定不变的。

主要结论:

意味着随着处理器数目的无限増大，并行系统所能达到的加速之上限为1/f.

2）Gustafson定律：

P85

flVGFi/fGF/7fvv

/VVGF1ZfGF/^V//;

应用范围及主要结论：

对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。

它意味若随着处理器数目的增加，加速几乎与处理器数成比例的线性增加，串行比例f不再是程序的瓶颈，这对并行系统的发展是个非常乐观的结论。

2）Sun和Ni定律：

P86

s，t%合卩呦t%合”呦

%6p'

Wp!

pws（^wp……

只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。

主要结论：

G（p）=1时就是Amdahl加速定律；

G（p）=p变为f+p（1-f）,就是Gustafson加速定律

G（p）>

p,相应于计算机负载比存储要求增加得快，此时Sun和Ni加速均比Amdahl加速和Gustafson加速为高。

笫18题并行编程模型有哪些它们中每一种模型的特点应用范围

PRAM模型P109-110异步PRAM模型P110-111BSP模型Plll-113logP模型P113-115

笫19题什么是并行计算的系统结构模型他的分类每一种系统结构模型的主要特点比较它们的异同点目前常用的有哪些结构模型为什么

1.什么是并行计算的系统结构模型答：

没有找到

2.他的分类（P22）

并行计算的系统结构分两大类：

单指令多数据流SIMD和多指令多数据流MIMD；

其中多指令多数据流MIMD包括：

并行向量处理机PVP、对称多处理机SMP、大规模并行处理机HPP、工作站机群COW和分布共享存储DSM多处理机。

3.每一种系统结构模型的主要特点（P22-P24）

PVP：

课本没有讲到（平行向量处理机最大的特点是系统中的CPU是专门定制的向量处理器（VP）。

系统还提供共享存储器以及与YP相连的高速交叉开关一一维基百科）

SHP：

课本没有讲到（对称多处理机最主要的特征是系统的对称性，即每个处理器可以以同等代价访问各个共享存储器——维基百科）

MPP：

（P24第二段）它具有如下特性：

a.处理节点采用商用处理器；

b.系统中有物理上的分布式存储器；

c.采用高通信带宽和低延迟的互联网络（专门设计和定制的）；

d.能扩放至成百上千乃至上万个处理器。

e.它是一种异步的M1MD机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息互相作用。

DSM：

课本没有讲到，网络没找到

COW：

（P24第四段）COW的重要界限和特征是：

a.COW的每个节点都是一个完整的工作站，这样的节点有时叫作“无头工作站”，一个节点也可以是一台PC或SHP；

b.各节点通过一种低成本的商品（标准）网络（如以太网、FDDI和ATM开关等）互连（有的商用机群也使用定做的网络）；

c.给节点内总是有本地磁盘，而MPP节点却没有；

d.节点内的网络接口是松散耦合到10总线上的，而MPP内的网络接口是连到处理器节点的存储总线上的，因而可以是紧耦合式的；

e.一个完整的操作系统驻留在每个节点中，而HPP中通常只是个微核，COW的操作系统是工作站UNIX,加上一个附加的软软件层，以支持单一系统镜像、并行度、通信和负载平衡等。

4.目前常用的有哪些结构模型为什么

课本没讲（P24最后一段，机群相对于MPP有性能/价格比高的优势，所以在发展可扩敖并行计算机方面呼声很高。

）

第20题什么是串行程序设计（286页，第二段）

它的优缺点（2