第六讲 并行算法设计与并行模式 课程网站：CourseGrading http://judge.buaa.edu.cn 主讲教师： 赵长海 主讲教师： 赵长海 办公室： 新主楼G910 Email: zch@buaa.edu.cn Spring 2013

本章内容 6.1 并行算法设计基本方法 6.2 常用的并行模式 6.3 Google的MapReduce编程框架

分解（decompositon） 执行 6.1 并行算法设计基本方法 并行设计关键步骤 将计算分成很多小的计算 将计算分到不同处理器上并行执行

例 数据分解 (Data Decomposition) 一.数据分解 第四讲的矩阵相乘 第五讲的统计数组中10的个数 即，数据并行。将数据分成很多块，每个计算任务处理一部分数据 数据分解 (Data Decomposition) 第四讲的矩阵相乘 第五讲的统计数组中10的个数 例 Google的MapReduce

数据分解方法：

例 功能分解 (Functional Decomposition) 二.功能分解 Office Word QQ ... 即，任务并行。将计算根据功能划分，每个任务处理整个工作的一部分。 功能分解 (Functional Decomposition) Office Word 例 QQ ...

6.2 并行模式 流水线并行（pipeline） 常用的并行模式 主从（Master/worker） 线程池（thread pool） 分而治之（Divide & Conquer）

流水线并行模式 一.流水线 流水线是生产者-消费链。数据流通过一串计算任务，前一计算任务的输出是下一个计算任务的输入。 Stage 1 Time C1 C2 C3 C4 4个阶段的流水线

流水线分类： 线性流水线 非线性流水线 Stage 1 Stage 2 Stage 3 Stage 4 Stage 1 Stage 2

主从(master-worker)并行模式： 二.主从 一个进程（线程）作为master,其它进程(线程)作为worker: master产生和管理任务； master调度并分派任务给worker； worker完成分派的任务之后，向master请求更多 的任务 主从(master-worker)并行模式： A B D E tasks queue C master worker

线程池(thread pool)并行模式： 四.线程池 创建一定数量线程，配备一个任务队列，存放其它线程提交的任务。线程池内的线程从队列中取任务执行，如果队列中没任务，线程池内的线程挂起。 线程池(thread pool)并行模式：

应用 消除频繁创建撤销线程的开销 较快的响应速度 避免过量占用系统资源（相比每到达一个任务就创建一个线程的方式） 使用线程池的优势 Web服务器，例如Tomcat服务器可以配置线程池内的线程数 应用

例：TCP服务器 创建线程池 int main(int argc, char **argv) { …… 参考：Network Programming Volume 1, Third Edition: The Sockets Networking API 创建线程池 int main(int argc, char **argv) { …… listenfd = Tcp_listen(argv[1], argv[2], &addrlen); for (i = 0; i < nthreads; i++) Pthread_create(&tptr[i].thread_tid, NULL, &thread_main, (void *) i); Signal(SIGINT, sig_int); for ( ; ; ) pause(); /* everything done by threads */ }

一个线程处理一个客户端的请求 void * thread_main(void *arg) { int connfd; void web_child(int); socklen_t clilen; struct sockaddr *cliaddr; cliaddr = Malloc(addrlen); for ( ; ; ) { clilen = addrlen; Pthread_mutex_lock(&mlock); connfd = Accept(listenfd, cliaddr, &clilen); Pthread_mutex_unlock(&mlock); web_child(connfd); /* process request */ Close(connfd); }

分而治之 (divide & conquer)并行模式： 五.分而治之模式 将问题被分成许多并行的子问题，最后合并结果。 分而治之 (divide & conquer)并行模式： problem subproblem Compute solution merge split

思 考 6.3 Google的MapReduce分布式编程框架 编写一个能够在数千台机器运行，处理数TB~PB数据的并行程序，有哪些关键问题或难点 思 考

编写能够在上千节点上执行，且可扩展的并行程序难点 并行控制 机器故障 负载均衡 数据I/O 网络瓶颈

MapReduce： MapReduce等同于分而治之并行模式，Google创造性的实现了基于该并行模式的分布式编程框架，简化并行编程难度。 copy/sort/merge阶段 数据split 阶段 Map阶段 Reduce阶段

MapReduce实现的单词计数伪代码 map(String key, String value) {     // key: document name     // value: document contents     for each word w in value:         EmitIntermediate(w, “1”); } reduce(String key, Iterator values) {     // key: a word     // values: a list of counts     int result = 0;     for each v in values:         result += ParseInt(v);     Emit(AsString(result)); }

MapReduce深入学习 学习路线 http://hadoop.apache.org/ 1. 学会安装配置 2. 运行例子程序 3. 了解系统架构 4. 读MapReduce源代码

本 章 内 容 小 结

2. 并行模式 4. Google的MapReduce 并行算法设计与 并行模式 1. 并行算法设计 数据分解 功能分解 流水线并行 1. 并行算法设计 数据分解 功能分解 并行算法设计与 并行模式 2. 并行模式 流水线并行 主从模式 线程池 分而治之 4. Google的MapReduce 简化编写大规模并行程序的难度 隐藏并行控制、故障处理、负载均衡、数据I/O MapReduce的限制 不是一个通用的编程框架，只适合分而治之并行模式的应用