并行计算-期末考试模拟题原题

Reviewsonparallel考范及型110章）

并计英文复基本概解；

Translation(Chinese)问答题

Questionsandanswer算法的图述descriptiononalgorithms编程。Reviewsonparallel

并计基本概解；

Translation(Chinese)Parallelism,Networktopology,diameterofanetwork,width,decomposition,taskgraphsgranularityprocesslineararray,mesh,hypercube,reduction,prefix-sum,threadexclusionspace,theofDualofa

问答题

Questionsandanswer1第1章weneedparallelcomputing?1）什我需并计？答：explainarethemaindifferencebetweencomputingandsequential2解并计与行算算设计的要同在里答：1

2第2章areSIMD,SPMDMIMDdenote?1解释SPMD和MIMD是什含。答：drawtypicalarchitectureofSIMDatypicalarchitectureofMIMDtoexplan.2）请绘制一个典型的SIMD的系结构和MIMD架构。答：arethetwotypicalcommunicationmodelsofParallelPlatforms?giveashortonMassagePassingandaddressspacemodels.3）并行平台的两个典型的通信式是什么？你可以给一个简短的介绍信息传递和共享地址空间模型。能说出Massage和Sharedaddressspace两种通讯模型。答：idealparallelrandomaccessmachine(PRAM),themeaningofEREW,CREWand4）在理想并行计算模型中parallelrandommachine(PRAM),EREW,CREW,和CRCW表示意思是什么？答：3第3章abletoexplainatleast2kindsthebasicdecompositioni.e.,DatadecompositionandSpeculativedecomposition.2

1）能够解释的基本的把问题分技术，至少有种，如，递归分解，数据分解，探索分解和投分解。递分解，如快排序数分解，矩阵乘法，矩阵与向量的乘法，按行或格网的数据划分。探分解，人工智能中的状态空间的问题求解、如16数码问题。(4)投机分解，利处理器大多时间处于空闲的特点，把后面可以先计算的任务，提前计算出，在许多情况下会加速程序的运行。如对case,if句的句子同时计算出来。答：theworkbalanceoftasksbecomebed,isscheduledbasedondatadecomposition,methodscanimprovetheworkbalanceoftasks,block-cyclicdistribution,Randomizedblockandgraphpartitioning.2）当平衡工作的任务成为基于据分解，有什么方法可以改善平衡工作的任务。对稀疏矩阵或在同一数据集合上，操作密度不同的计算，如何达到调度平衡的问具方法是么：(1)block-cyclicdistribution（采在一个矩阵上循环安排任务计算完成的方法）(2)对阵的下标采用随机映射的方法(3)图划的方法答：4第4章familiarwiththebasiccommunicationoperationsaswellastheirimplementationsthemodels,lineararrayandmesh(graphicaldescription)1）熟悉的基本通信业务，以及他们的典型模式实现，超立方体，线性阵列和网状（图形描述）allbroadcast;allallallbroadcast;allallreductionscatter,allprefixsum，allallpersonalizedshift个人认为以下的更重要，算法实现没必要记住，但是要知道每个操作具体是怎么做的答：3

2)beabletousebasiccommunicationoperationtodesignparallelalgorithms,e.g.matrix-vectormultiplication,shortestpathtreesminimumspanningtree.2）能使用基本的通信操作设计行算法，例如：矩阵向量乘法，最短路径树和最小生成树。答：5第5章1)Theformulaeofspeedup,efficiencyandcostofparallelalgorithmandbeabletogiveashortexolaination.1）并行算法的加速，效率和成的计算公式，并能给出一个简短解释。知并行算法的分析测度，以及相应的测度计算公式。并算法并行加速比S，=Ts/Tp，Tp和Ts表示并行算法和串行算法的时间复杂性。效=E=S/p=Ts/（Tp*p）费cost=P*Tp答：2)TheproofonAmdahlIfaproblemofsizehasaserialWs,provethatW/Wsisanupperboundonitsspeedup,nomatterhowmanyprocessingelementsareused.2）Amdahl定的证明：设W表某算法求解问题的全部工作量W=Ws+Wp,其中Ws表示须串行计算的工作量Wp表可以并行计的工作量。试证明该算法的并行加速比的上界是W/Ws，无有多少个处理单元。答：4

6第6章1)BeabletodescribethearchitectureofaMPI1）能够来描述程序的MPI程序构。#include<mpi.h>Main(intargc,char*argv[]){intnpes,myrank;MPI_init(&argc,&argv);MPI_Comm_szie(MPI_COMM_WORLD,&npes);MPI_Comm_rank(MPI_COMM_WORLD,&myrank);并行程序代码部分通讯结束部分MPI_Finilize()}2)fundimentalfunctionsforMPIa)MPI_Initestablishingparallelcomputationalenvironmentb)MPI_Finalizeclosesallparalleltasksc)MPI_Comm_sizegetthenumberofprocessesavailabled)MPI_Comm_rankgettheidofprocesse)MPI_sendmessagesendingfunctionsf)MPI_Recvmessagereceivingfunctions2）了解MPI的本函数1）MPI_INIT建一个并行计算环境2）关闭所有并行务3）MPI_Comm_size获可用的程数4）MPI_Comm_rank得进程ID5）MPI_send消发送功能6）MPI_Recv消接收功能3)Blockingandnon-blockmessageinMPI_Send.a)ReturnonlyaftercorrespondingMPI_Recvhavebeenissuedandthemessagehasbeensenttothereceiver(blocking)completely.b)Initializeaprocesstocopythemessageintoabufferofthedestinationandthenreturn(non-blockingwithabuffer)withoutwaitingthefinishofthedatatransformation.Pleasegivethecorrespondingsentencesthetwokindsofmassagepassingin3）能说明在MPI_Send中阻塞的消息传递（blockingMessagePassing）无阻塞的消传递（Non-blockingPassing的含义和具体如何实现的。1)只返回相应的后经下,消息被发送到接收阻塞完全。2)初化一个流程来复制到缓冲的消息的目的地,后返回(无塞/非塞方式的缓冲区)无等待完成的数据转换。请给相应的句子的两种消息传入MPI答：5

7第7章1)BeabletodescribethearchitectureofaPthreadprogram1）说明一般利用Pthread编的程序基本结构（包含那几个语句答指的一个标准的线程API，POSIX。也称为Pthread线程的创建、终止pthread_create等待所有线程运行完毕以便完成结果的合并#include{pthread.h>intpthread_create(pthread_t*thread_handle,ofthreadconstpthread_attr_t*attributevoid*(*thread_function)(void*),/*theprogramcontent*/void*arg/*thepointerforcalculatedintpthread_joinpthread_tthread,void**ptr)intpthread_exit()2)Beabletointroducethemethodsforsynchronization,e.g.implementingcriticalsectionandatomicoperations.Beabletowritethecorrespondingsentences2）介绍同步的方法，例如：实的关键部分和原子操作。能够写出相应的句子。答：3)BeabletowriteOpenMPprogramsmatrixmultiplication,πcomputationandso3）能编写OpenMP程的矩阵乘法π计等。答：4)BeabletocomparetheadvantageandshortcomingofThreadandOpenMPprogramming.4）能够比较Thread和OpenMP编程的优点和缺点。答：6

8第8章1)Algorithmsformatrixtransposition1）矩阵转置算法算法：①按mesh接进行块转置(不同处理器间②进行块内转置同一处理器内)答：2)Algorithmsformatrixmultiplications2）矩阵乘法算法答：并发实现矩阵与向量的乘法。9第9章Befamiliarwithatleastonesortingnetworkasaparallelsortingalgorithm.熟悉至少一个排序网络，以及一个并行排序算法。答：奇偶排序的并行算法双调序7

第10章Algorithmsshortestpaths,MinimumSpanningTree,ConnectedComponents,IndependentSet.最短路径，最小生成树，连接组件，极大独立集的算法。答：Graphicalonalgorithms3.对法图描述1)Mesh,hypercubeaswellasthenodenumbering1）格网，超