华南理工大学云计算试卷

1.关于MapReduce的执行过程，以下那个观察是错误的？A.在map完成之前可以启动reduceB.任务调度是基于数据存储位置而进行的C.如果map的worker在reduce完成之前失败，任务必须完全重新运行D.Master必须知道中间文件的存储位置2.在Hadoop中，Map/Reduce算法分为Map、Combine和Reduce三个步骤。对下面三句话进行词频统计（WordCount），请分别写出上面三个步骤的输入和输出（假设启用3个mapworker和2个Reduceworker）。“HelloWorldByeWorld”“HelloSCUTByeSCUT”“HelloWorldHelloSCUTInput:HelloWorldByeWorldHelloSCUTByeSCUTHelloWorldHelloSCUTMap:Hello,1World,1Bye,1World,1Hello,1SCUT,1Bye,1SCUT,1Hello,1World,1Hello,1SCUT,1Sort:Bye,1Bye,1Hello,1Hello,1Hello,1Hello,1SCUT,1SCUT,1SCUT,1World,1World,1World,1Combine:Bye,1,1Hello,1,1,1,1SCUT,1,1,1World,1,1,1Reduce:Bye,2Hello,4SCUT,4World,33.一个kkN2)1(个节点的蝶形网络如图所示。试问：（1）此网的节点度、网络直径和网络对剖宽度分别为多少？（2）对如下的蝶式求全和的通信图，分析当处理器数为p时的计算和通信次数。行0行1行2行34.分布式文件系统GFS的系统架构5.用PSRS（ParallelSortingbyRegularSampling）算法排序n=27的一个序列，即{6,37,8,2,7,15,27,14,32,91,17,20,42,5,25,4,53,13,18,55,26,9,39,12,45,63,58}，p=3，p为处理机个数。给出算法的主要步骤及结果输出。6.对于如右图的有向加权图，求最短路径长度矩阵nnijdD)(，ijd为顶点iv到顶点jv的最短路径长度，n为顶点个数。（1）试设计一个算法，求出最短路径长度矩阵D中各元素ijd；（2）对该算法进行并行化，并给出并行算法的伪码表示；（3）分析并行算法的时间复杂度，是否成本最优？为什么？7.已知4331A，8765B，试用DNS方法，求出矩阵乘积22211211ccccC，并图示说明。8．计算两个N阶向量内积的串行代码段如下：Sum=0;for(i＝0;iN;i++)Sum=Sum+A[i]*B[i];（1）在p个处理器的BSP模型（计算参数w，带宽参数g，同步障参数l）上计算，试写出p=8时各超级步的计算过程及执行时间；（2）用OpenMP编程语言，写出计算内积的并行代码段。（3）用MPI编程语言，写出计算内积的并行代码段。9.一个并行算法的计算时间如下式表示：wcptntpnT23串行执行时间是cetnT3，存储需求是2n。（1）求固定负载时的加速比并讨论其结果；（2）求固定时间时的加速比并讨论其结果；（3）求存储受限时的加速比并讨论其结果。10.假设集合A=（4,6,7,10,12,15,18,20），B=（3,9,16,21），采用对数划分技术，得到A和B两个子集合分别是：AA.A0＝（4,6,7），A1＝（10,12,15,18,20），B0＝（3,9），B1＝（16,21）B.A0＝（4,6,7），A1＝（10,12,15,18,20），B0＝（3），B1＝（9,16,21）C.A0＝（4,6,7,10），A1＝（12,15,18,20），B0＝（3,9），B1＝（16,21）D.A0＝（4,6,7,10），A1＝（12,15,18,20），B0＝（3），B1＝（9,16,21）V0V2V1624113V0V2V1624113