并行计算框架并行计算框架.pdfVIP

并⾏计算框架简述 汪源 ⺫录 • MPI • 同步数据流: MapReduce, Spark, PrIter • 数据流⽔线: Dryad/DryadLINQ, SCOPE • 共享存储: Piccolo • 图计算 • BSP: Pregel, BPGL, Apache Giraph/Hama, GPS • 异步: Distributed GraphLab MPI • 开源的基于消息传递的“裸”并⾏编程模型 • 库：MPI_Send/Recv/bcase/Alltoall • ⼯具：mpirun • 通信模型：点对点、组 • 以不共享存储为主，后期MPI I/O增加了并⾏操作共享 ⽂件功能 • 性能⾮常好 • 主要⽤于⾼性能计算，⺫前的分布式机器学习算法实 现中也常⽤ MapReduce(Google) • 核⼼过程 • Map ：相当与本地的 GROUP BY • Shuffle+Merge ：相当于全 局GROUP BY • Reduce ：相当于聚集函数 • ⽆共享存储 • 开源：Hadoop 迭代式MapReduce • Twister ：开源 • 静态数据不重复load （如PageRank中的结构信息） • 假设内存⾜够⼤，MR之间的结果数据可通过⺴络传递，不⽤save/ reload • 缓存Mapper/Reducer ，不⽤每次重新⽣成 • 增加Combine操作汇集所有Reducer的结果，⽅便判断是否终⽌循 环 • Haloop • 静态数据不重复load • 调度时考虑静态数据的本地性 • Map/Reduce输⼊输出缓存和索引 MapReduce衍⽣系统 • Hive ：并⾏数据库OLAP • Pig ：交互式陈述式操作语⾔ • Mahout ：机器学习 Spark(1) • Berkeley • 开源 • 数据模型：RDD(Resilient Distributed Datasets) • RDD ：不可变、分区的对象集合，通过对原始数据进⾏⼀系列 transformation得到 • 记录RDD的产⽣规则，不需要象MR那样物化中间结果，但也能容错 • RDD可被缓存起来重⽤ • 适合迭代计算：⽆需物化、RDD缓存重⽤ • 性能⽐Hadoop有⼏⼗倍提升 • 很通⽤，基于Spark很容易实现BSP模型，很⾼效计算PageRank • 使⽤Scala实现算法⾮常简洁 Spark(2) Spark(3) Spark(4) PageRank val links = spark.textFile(...).map(...).persist() var ranks = // RDD of (URL, rank) pairs for (i - 1 to ITERATIONS) { // Build an RDD of (targetURL, float) pairs // with the contributions sent by each page val contribs = links.join(ranks).flatMap { (url, (links, rank)) = links.map(dest = (dest, rank/links.size)) } // Sum contributions by URL and get new ranks ranks = contribs.reduceByKey((x,y) = x+y) .mapValues(sum = a/N + (1-a)*sum) } PrIter • 开源 • 改进M