并行计算框架

《并行计算框架》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并行计算框架简述汪源目录•MPI•同步数据流:MapReduce,Spark,PrIter•数据流水线:Dryad/DryadLINQ,SCOPE•共享存储:Piccolo•图计算•BSP:Pregel,BPGL,ApacheGiraph/Hama,GPS•异步:DistributedGraphLabMPI•开源的基于消息传递的“裸”并行编程模型•库：MPI_Send/Recv/bcase/Alltoall•工具：mpirun•通信模型：点对点、组•以不共享存储为主，后期MPII/O增加了并行操作共享文件功能•性能非常

2、好•主要用于高性能计算，目前的分布式机器学习算法实现中也常用MapReduce(Google)•核心过程•Map：相当与本地的GROUPBY•Shuffle+Merge：相当于全局GROUPBY•Reduce：相当于聚集函数•无共享存储•开源：Hadoop迭代式MapReduce•Twister：开源•静态数据不重复load（如PageRank中的结构信息）•假设内存足够大，MR之间的结果数据可通过网络传递，不用save/reload•缓存Mapper/Reducer，不用每次重新生成•增加Combine操作汇集所有Re

3、ducer的结果，方便判断是否终止循环•Haloop•静态数据不重复load•调度时考虑静态数据的本地性•Map/Reduce输入输出缓存和索引MapReduce衍生系统•Hive：并行数据库OLAP•Pig：交互式陈述式操作语言•Mahout：机器学习Spark(1)•Berkeley•开源•数据模型：RDD(ResilientDistributedDatasets)•RDD：不可变、分区的对象集合，通过对原始数据进行一系列transformation得到•记录RDD的产生规则，不需要象MR那样物化中间结果，但也能容

4、错•RDD可被缓存起来重用•适合迭代计算：无需物化、RDD缓存重用•性能比Hadoop有几十倍提升•很通用，基于Spark很容易实现BSP模型，很高效计算PageRank•使用Scala实现算法非常简洁Spark(2)Spark(3)Spark(4)PageRankvallinks=spark.textFile(...).map(...).persist()varranks=//RDDof(URL,rank)pairsfor(i<-1toITERATIONS){//BuildanRDDof(targetURL,floa

5、t)pairs//withthecontributionssentbyeachpagevalcontribs=links.join(ranks).flatMap{(url,(links,rank))=>links.map(dest=>(dest,rank/links.size))}//SumcontributionsbyURLandgetnewranksranks=contribs.reduceByKey((x,y)=>x+y).mapValues(sum=>a/N+(1-a)*sum)}PrIter•开源•改进Map

6、Reduce的迭代性能，Reduce结果直接给下一个Map•流水线：Map输出一到，Reduce即可开始工作，不用收集齐所有Map结果并排序•优先调度高优先级的任务（优先级由用户程序制定）Dryad(Microsoft)•基于计算拓扑图的“通用”并行计算框架•程序=DAG（节点：计算，边：通信通道）Dryad衍生系统•DryadLINQ(Microsoft)•类似与SQL的陈述式操作语言或.Net类库•SCOPE(Microsoft)•StructuredComputationsOptimizedforParallel

7、Execution•数据模型：表格•并行数据库：提供JOIN、GROUPBY/HAVING/AGG等算子•允许自定义算子•extractor：从源文件中解析出结构化数据•processor：行级处理•reducer：分组处理•combiner：合并多个输入•基于代价的优化器Piccolo•编程模型•用户实现controlfn(全局唯一)和kernelfn，controlfn创建kernelfn•controlfn用barrier等待所有kernelfn完成•用用户定义的accumulationfunction来合并并发

8、update•数据模型•共享的KV存储•用户定义分区策略，且支持表（表指一类KV数据，不是关系表）之间的colocation•系统实现•会根据负载动态迁移数据分区BSP:BulkSynchronousParallel•系统模型:processers+communicationchannels•计算:superstep+•Super