复习重点

C. 如果map的worker 在reduce完成之前失败，任务必须完全重新运行 D. Master必须知道中间文件的存储位置

2. 在Hadoop中，Map/Reduce算法分为Map、Combine和Reduce三个步骤。对下面三句话进行词频统计（Word Count），请分别写出上面三个步骤的输入和输出（假设启用3个map worker和2个Reduce worker）。

“Hello World Bye World” “Hello SCUT Bye SCUT” “Hello World Hello SCUT

Map数据的输入 map1的输入（0，Hello World Bye World） Map2的输入 （0，Hello SCUT Bye SCUT） Map3 的输入 （0，Hello World Hello SCUT） Map数据的输出和Combine的输入

map1 Hello 1 World 1 Bye 1 Word 1 Map2 Hello 1 SCUT 1 Bye 1 SCUT 1 Map3 Hello 1 World 1 Hello 1 SCUT 1 Combine的输出和Reduce的输入

map1 Hello 1 World 2 Bye 1 Map2 Hello 1 SCUT 2 Bye1 Map3 Hello 2 World1 SCUT 1

Reduce的输出

Reduce1 Hello2 World 2 Bye1

Reduce2 Hello 2 Bye 1 SCUT 3 World 1

3. 一个N(k1)2k个节点的蝶形网络如图所示。试问：

（1）此网的节点度、网络直径和网络对剖宽度分别为多少？

（2）对如下的蝶式求全和的通信图，分析当处理器数为p时的计算和通信次数。

节点度为k 网络直径为2k 对剖宽度2k

假设pn/2k，则每个处理器最初要存入2k个输入数据，所以要执行

2k1logn个并行蝶式计算步，链接函数C要重复2k1次，总的并行数据传输

次数为24. 分布式文件系统

k1(lognk)次

GFS的系统架构

一 个GFS由一个master和大量的chunkserver构成，并被许多客户（Client）访问。如图1所示。

Master和 chunkserver通常是运行服务进程的Linux机器。只要资源和可靠性允许，chunkserver和client可以运行在同一个机器 上。文件被分成固定大小的块。每个块由一个不变的、全局唯一的位的chunk－handle标识，chunk－handle是在块创建时 由 master分配的。ChunkServer将块当作Linux文件存储在并可以读和写由chunk－handle和位区间指定的数据。出于可靠 性考虑，每一个块被复制到多个chunkserver上。默认情况下，保存3个副本，但这可以由用户指定。

Master维护文件系统所以的元 数据（metadata），包括名字空间、访问控制信息、从文件到块的映射以及块的当前位置。它也控制系统范围的活动，如块租约（lease）管理，孤儿 块的垃圾收集，chunkserver间的

块迁移。Master定期通过HeartBeat消息与每一个 chunkserver通信，给chunkserver传递指令并收集它的状态。

与每个应用相联的GFS客户代码实现了文件系统的API并与master和chunkserver通信以代表读和写数据。客户与master的交换只限于对元数据（metadata）的操作，所有数据方面的通信都直接和chunkserver联系。

客 户和chunkserver都不缓存文件数据。因为用户缓存的益处微乎其微，这是由于数据太多或太大而无法缓存。不缓存数据简化了客户程序和整个系统，因为不必考虑缓存的一致性问题。但用户缓存元数据（metadata）。Chunkserver也不必缓存文件，因为块是作为本地文件存储的。

5. 用

PSRS（Parallel Sorting by Regular Sampling）算法排序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为处理机个数。给出算法的主要步骤及结果输出。 第一步2,6,7,8,14,15,27,32,37 4,5,13,17,20,25,42,53,91 9,12,18,26,39,45,55,58,63 第二步 7,15 13,25 18,45 第三步 7,13,15,18,25,45 第四步 选择13 18为主元

第五步 第一段分为2,6,7,8; 14,15; 27,32,37; 第二段分为 4,5,13; 17; 20,25,42,53,91;

第三段分为 9,12; 18; 26,39,45,55,58,63; 第六步 第一段2,4,5,6,7,8,9,12,13 第二段 14,15,17,18

第三段 20,25,26,27,32,37,39,42,45,53,55,58,63,91

第七步 合并为2，4，5，6，7，8，9，12，13，14，15，17，18，20，25，26，27，32，37，39，42，45，53，55，58，63，91

6. 对于如右图的有向加权图，求最短路径长度矩阵D(dij)nn，dij为顶点vi到顶点vj的最短路径长度，n为顶点个数。

（1）试设计一个算法，求出最短路径长度矩阵D中各元素dij； V0（2）对该算法进行并行化，并给出并行算法的伪码

63表示；

114（3）分析并行算法的时间复杂度，是否成本最优？

为什么？

V13567. 已知A，B78，试用DNS方法，34V221求出矩阵乘积Cc11c21c12，并图示说明。 c228．计算两个N阶向量内积的串行代码段如下：

Sum=0;

for(i＝0; i（1）在p个处理器的BSP模型（计算参数w，带宽参数g，同步障参数l）上计算，试写出p=8时各超级步的计算过程及执行时间； （2）用OpenMP编程语言，写出计算内积的并行代码段。 （3）用MPI编程语言，写出计算内积的并行代码段。 9. 一个并行算法的计算时间如下式表示： 串行执行时间是Ten3tc，存储需求是n2。 （1）求固定负载时的加速比并讨论其结果； （2）求固定时间时的加速比并讨论其结果； （3）求存储受限时的加速比并讨论其结果。

10. 假设集合A=（4, 6, 7, 10, 12, 15, 18, 20），B=（3, 9, 16, 21），

采用对数划分技术，得到A和B两个子集合分别是：A

A. 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, 21）

D. A0＝（4, 6, 7, 21）

），A1＝（12, ），A1＝（12, 18, 20），B0＝（3, 9），B1＝（16,

18, 20），B0＝（3），B1＝（9, 16,

1015, 1015,