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

1Reviewsonparallelprogramming并行计算英文班复习考试范围及题型：（1—10章）1基本概念解释；Translation(Chinese)2问答题。Questionsandanswer3算法的画图描述。Graphicaldescriptiononalgorithms4编程。AlgorithmsReviewsonparallelprogramming并行计算1基本概念解释；Translation(Chinese)SMPMPPClusterofWorkstationParallelism,pipelining,Networktopology,diameterofanetwork,Bisectionwidth,datadecomposition,taskdependencygraphsgranularityconcurrencyprocessprocessor,lineararray,mesh,hypercube,reduction,prefix-sum,gather,scatter,threads,mutualexclusionsharedaddressspace,synchronization,thedegreeofconcurrency,Dualofacommunicationoperation,2问答题。QuestionsandanswerChapter1第1章1)Whyweneedparallelcomputing?1）为什么我们需要并行计算？答：2)Pleaseexplainwhatarethemaindifferencebetweenparallelcomputingandsequentialcomputing2）解释并行计算与串行计算在算法设计中的主要不同点在那里？答：2Chapter2第2章1)WhatareSIMD,SPMDandMIMDdenote?1）解释SIMD,SPMD和MIMD是什么含义。答：2)PleasedrawatypicalarchitectureofSIMDandatypicalarchitectureofMIMDtoexplan.2）请绘制一个典型的SIMD的体系结构和MIMD的架构。答：3)WhatarethetwotypicalcommunicationmodelsofParallelPlatforms?YoucangiveashortintroductiononMassagePassingandSharedaddressspacemodels.3）并行平台的两个典型的通信模式是什么？你可以给一个简短的介绍信息传递和共享地址空间模型。能说出MassagePassing和Sharedaddressspacemodels两种通讯模型。答：4)Intheidealparallelrandomaccessmachine(PRAM),whatarethemeaningofEREW,CREWandCRCW?4）在理想并行计算模型中（parallelrandomaccessmachine(PRAM),EREW,CREW,和CRCW表示的意思是什么？答：Chapter3第3章1)Beabletoexplainatleast2kindsofthebasicdecompositiontechniques,i.e.,Recursivedecomposition,Datadecomposition,ExplorationdecompositionandSpeculativedecomposition.31）能够解释的基本的把问题分解技术，至少有2种，例如，递归分解，数据分解，探索分解和投机分解。(1)递归分解，如快速排序(2)数据分解，矩阵乘法，矩阵与向量的乘法，按行或格网的数据划分。(3)探索分解，人工智能中的状态空间的问题求解、如16数码问题。(4)投机分解，利用处理器大多数时间处于空闲的特点，把后面可以先计算的任务，提前计算出，在许多情况下会加速程序的运行。如对case,if语句的句子同时计算出来。答：2)Whentheworkbalanceoftasksbecomebed,whichisscheduledbasedondatadecomposition,whatmethodscanimprovetheworkbalanceoftasks,block-cyclicdistribution,Randomizedblockdistributionsandgraphpartitioning.2）当平衡工作的任务成为基于数据分解，有什么方法可以改善平衡工作的任务。对稀疏矩阵或在同一数据集合上，操作密度不同的计算，如何达到调度平衡的问题,具体方法是什么：(1)block-cyclicdistribution（采用在一个矩阵上循环安排任务计算完成的方法）(2)对矩阵的下标采用随机映射的方法(3)图划分的方法答：Chapter4第4章1)Befamiliarwiththebasiccommunicationoperationsaswellastheirimplementationsonthetypicalmodels,hypercube,lineararrayandmesh(graphicaldescription)1）熟悉的基本通信业务，以及对他们的典型模式实现，超立方体，线性阵列和网状（图形描述）onetoallbroadcast;alltoonereductionalltoallbroadcast;alltoallreductionscatter,gather,allreduce,prefixsum，alltoallpersonalizedcommunication.Circularshift个人认为以下的1-4更为重要，算法实现没必要记住，但是要知道每个操作具体是怎么做的答：42)beabletousebasiccommunicationoperationtodesignparallelalgorithms,e.g.matrix-vectormultiplication,shortestpathtreesandminimumspanningtree.2）能使用基本的通信操作设计并行算法，例如：矩阵向量乘法，最短路径树和最小生成树。答：Chapter5第5章1)Theformulaeofspeedup,efficiencyandcostofaparallelalgorithmandbeabletogiveashortexolaination.1）并行算法的加速，效率和成本的计算公式，并能给出一个简短解释。(1)知道并行算法的分析测度，以及相应的测度计算公式。(2)并行算法并行加速比S，S=Ts/Tp，Tp和Ts表示并行算法和串行算法的时间复杂性。(3)效率E=E=S/p=Ts/（Tp*p）,(4)费用cost=P*Tp答：2)TheproofonAmdahl’slaw:IfaproblemofsizeWhasaserialcomponentWs,provethatW/Wsisanupperboundonitsspeedup,nomatterhowmanyprocessingelementsareused.2）Amdahl定理的证明：设W表示某算法A求解问题的全部工作量，W=Ws+Wp,其中Ws表示必须串行计算的工作量；Wp表示可以并行计算的工作量。试证明该算法的并行加速比的上界是W/Ws，无论有多少个处理单元。答：5Chapter6第6章1)BeabletodescribetheprogramarchitectureofaMPIprogram.1）能够来描述程序的MPI程序架构。#includempi.hMain(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_Initestablishingaparallelcomputationalenvironmentb)MPI_Finalizeclosesallparalleltasksc)MPI_Comm_sizegetthenumberofprocessesavailabled)MPI_Comm_rankgettheidofprocesse)MPI_sendmessagesendingfunctionsf)MPI_Recvmessagereceivingfunctions2）了解MPI的基本函数1）MPI_INIT建立一个并行计算环境2）MPI_Finalize关闭所有并行任务3）MPI_Comm_size获得可用的进程数4）MPI_Comm_rank得到进程ID5）MPI_send消息发送功能6）MPI_Recv消息接收功能3)Blockingandnon-blockmessagepassinginMPI_Send.a)ReturnonlyafterthecorrespondingMPI_Recvhavebeenissuedandthemessagehasbeensenttothereceiver(blocking)completely.b)Initializeaprocesstocopythemessageintoabufferofthedestinationandthenreturn(non-blockingwithabuffer)withoutwaitingthefinishofthedatatransformation.PleasegivethecorrespondingsentencesforthetwokindsofmassagepassinginMPI.3）能说明在MPI_Send中的阻塞的消息传递（blockingMessagePassing）和无阻塞的消息传递（Non-blockingMessagePassing）的含义和具体如何实现的。1)只返回相应的MPI_Recv后已经下达,消息被发送到接收器(阻塞)完全。2)初始化一个流程来复制到缓冲区的消息的目的地,然后返回(无阻塞/非阻塞方式的缓冲区)无需等待完成的数据转换。请给相应的句子的两种消息传入MPI。答：6Chapter7第7章1)BeabletodescribetheprogramarchitectureofaPthreadprogram1）说明一般利用Pthread编程的程序基本结构（包含那几个语句）。答：IEEE指定的一个标准的线程API，POSIXAPI。POSIX也称为Pthread线程的创建、终止pthread_createpthread_exit等待所有线程运行完毕以便完成结果的合并pthread_join#include{pthread.hintpthread_create(pthread_t*thread_handle,//idofthethreadconstpthread_attr_t*attribute,void*(*thread_function)(void*),/*themainprogramcontent*/void*arg）；/*thepointerforthecalculatedresult*/intpthread_join(pthread_tthread,void**ptr)intpthread_exit()2)Beabletointroducethemethodsforsynchronization,e.g.implementingcriticalsectionandatomicoperations.Beabletowritethecorrespondingsenten