互联网数据工程重点实验室 - 高性能计算技术研究中心.ppt
《互联网数据工程重点实验室 - 高性能计算技术研究中心.ppt》由会员分享,可在线阅读,更多相关《互联网数据工程重点实验室 - 高性能计算技术研究中心.ppt(51页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、,2013年博士论文开题报告,高可扩展并行图处理技术及其基因组装应用研究 答辩人:孟金涛导 师:冯圣中,内容提要,1、选题依据2、研究现状与挑战3、研究内容、目标4、拟解决的关键问题5、拟采取的研究方案可行性分析6、现已取得进展7、实验计划及时间安排8、参考文献,社会媒体,图就是对现实生活中关系的一种抽象图: 百亿个顶点和边,点和边还有丰富的信息,广告服务,科学研究,互联网,3,选题依据-图是无处不在的,研究现状-Hadoop图处理的方法和进展,基于Hadoop开发的图处理系统Pegasus U Kang,ICDM09主要方法:通用矩阵向量乘法(GIM-V) 应用:连通分量,PageRank,
2、 图的直径9 服务器,问题规模1.4B点,6.7B边,性能5X加速.HAMA Sangwon Seo, CloudCom10主要方法: Hadoop上实现的矩阵乘法应用:矩阵乘法,可矩阵运算表示的图算法16 服务器(共32核), 矩阵规模5k X 5K,研究现状-Hadoop图处理的方法和进展,Surfer Rishan Chen, SoCC2012主要方法:适应网络带宽的图划分算法简单应用: 统计顶点的度,邻居个数,三角统计,PageRank问题规模 508.7M 点, 29.6G 边32服务器(共128核), 基于Windows操作系统提供两个接口MapReduce and Propaga
3、tion.图分割性能提升55%,图处理性能提升671%网络流量减少3095%,执行时间减少3085%,研究现状-Hadoop图处理的问题,扩展性不高服务器数目少于32台(Surfer),核心数少于130核问题规模不大最大问题规模1.4B点,6B边(Pegasus)只能处理易并行问题例如矩阵运算,统计点的度数,连通分量,PageRank等一些复杂问题,例如:修改图的结构的算法(图的初等收缩), 紧耦合问题(网络流)等,访存冲突(List ranking)图计算依赖通讯Hadoop依赖文件系统来交换数据Hadoop基本运算单位是MapReduce迭代每次迭代都很耗时,hadoop上算法设计的目标就
4、是减少迭代次数,研究现状-Hadoop图处理的问题,原因分析数据不常驻内容,每次迭代中,那些没有修改的图的数据结构,由于没有存在内存中,而需要从mapper发送到reducers去 Hadoop基于文件系统(Disk)的计算, 访问延迟比较高需要额外的MapReuce Jobs来检查是否到达了收敛要求编程模型接口简单, 语言表达能力不足(RISC VS CISC),开始尝试使用或者设计复杂高效的计算模型: BSP,研究现状-基于BSP图处理,基于BSP图处理系统PBGL (Parallel Boost Graph library) Gregor, POOSC05主要方法: 基于MPI通讯原语,
5、使用C+泛型编程开发BOOST扩展图算法库主要应用: 单源最短路径(SSSP), 连通分量, 最新生成树,图着色.问题规模: 1M个点,15M个边处理器个数: 128核唯一一个用C+, MPI开发的图算法库,研究现状-基于BSP图处理,Google Pregel G. Malewicz , SIGMOD10应用领域PageRankSemi-ClusteringSingle Source Shortest path (SSSP)Minimum spanning Tree (MST)主要衍生系统Giraph (2010)GPS (Semih, CMU, 2012)GoldenOrb (2010)S
6、park (2012)工作机制在Map-Reduce机制上加入消息通讯机制In-Meomory 计算, 减少文件IO操作Pregel的Superstep使用BSP的大同步机制,Pregel: G.Malewicz, Google, 2010,研究现状-基于BSP图处理,GPS & GreenMarl应用领域PageRankBetweenness Centrality工作机制Static Graph PartitionDynamic RepartitioningSingle Vertex and message objectsControlling message speedCombining
7、MessagesMessage Buffer特点12 times faster than Giraph顶点个数只有2G个复杂算法依赖GreenMarl翻译器,GPS: Semih Salihoglu, Stanford U, 2012GreenMarl: Sungpack Hong, Oracle, 2012Jennifer Widom, 2012 未发表的工作,Salihoglu S, Widom J. GPS: A Graph Processing System. Technical Report, 2012, http:/ilpubs.stanford.edu:8090/1039/7/f
8、ull_paper.pdfHong S, Salihoglu S, Widom J, Olukotun K. Compiling GreenMarl into GPS. Technical Report, November, 2012. http:/ppl.stanford.edu/papers/tr_gm_gps.pdf,研究现状与挑战,综述最好以指标、技术路线或挑战等来组织,这样脉络比较清晰. 比如:图的分割,主要的方法?取得的进展?存在的问题?等等. 能够量化的就尽量用量化的结果说明问题.,研究现状-Hadoop MapReduce,Hadoop MapReduce适合易并行的大数据计算
9、特征提取交叉验证统计排序图结构难划分Hadoop不负责数据划分策略,由用户定义图计算依赖通讯Hadoop依赖文件系统来交换数据Hadoop基本运算单位是MapReduce迭代每次迭代都很耗时,hadoop上算法设计的目标就是减少迭代次数,Jeffrey Dean 2008年,Jeffrey Dean, Sanjay Ghemawat, MapReduce: simplified data processingon large clusters, Communications of the ACM - 50th anniversaryissue: 1958 - 2008 Volume 51 Is
10、sue 1, January 2008, Pages 107-113ACM New York, NY, USAhttp:/hadoop.apache.org/,研究现状-基于Hadoop的图处理系统,Pegasus (U Kang, CMU, 2010)适用于Graph MiningSpectral clusteringDiameter estimationConnected components.Surfer (Rishan Chen, PKU, 2010)在MapReduce上的大图处理提供两个接口MapReduce and propagation.统计顶点的度,邻居个数相比基于BSP的图
11、系统有两个不高效的地方 每次迭代中,那些没有修改的图的数据结构,由于没有存在内存中,而需要从mapper发送到reducers去。 需要额外的MapReuce Jobs来检查是否到达了收敛要求。,Pegasus: U Kang, CMU, 2010Sufer: Rishan Chen, PKU 2010,U Kang, Duen Horng Chau, and Christos Faloutsos. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2012, Kyoto, Ja
12、panRishan Chen,Xuetian Weng,Bingsheng He,Mao Yang, Large graph processing in the cloud, in Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010,研究现状-基于Hadoop的图处理系统,Mahout (2010)大数据的并行处理适用于机器学习和数据挖掘K-Means, Fuzzy K-Means Clustering基于随机森林决策树的分类器用户和项目推荐奇异值分解.,Mahout
13、, http:/mahout.apache.org/,研究现状,Data-Parallel Graph-Parallel,交叉验证,特征提取,Map Reduce,计算密集型频率统计, 排序,Graphical ModelsGibbs SamplingBelief PropagationVariational Opt.,半监督学习顶点扩散CoEM,图分析PageRankBFS, DFS图直径,图匹配,Data MiningClusteringFilter,Map Reduce,BSP, eg Pregel,研究现状-大同步模型BSP & Pregel,Compute,Communicate,V
14、aliant 90,研究现状-基于BSP的图算法库,基于BSP的图算法库Parallel Boost Graph Library (PBGL).Boost C+ 库被互联网公司广泛使用扩展性差可扩展到128个核心,处理图的规模有限处理顶点规模到百万.数据一致性保证使用ghost node 并不能减少通讯,反而带来数据一致性的问题。Memory overhead通讯延迟,Gregor, A. Lumsdaine, The Parallel BGL: A Generic Library forDistributed Graph Computations, in Proc. of ParallelO
15、bject-Oriented Scientific Computing (POOSC), July 2005.Gregor, A. Lumsdaine, Lifting Sequential Graph Algorithms forDistributed-Memory Parallel Computation. in Proceedings of the 20thannual ACM SIGPLAN conference on Object-oriented programming,systems, languages, and applications (OOPSLA05), October
16、 2005, pp.423-437.http:/www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/index.html,Douglas Gregor 2005年,研究现状-Pregel及其衍生系统,Google Pregel (G. Malewicz , google, 2010)应用领域PageRankSemi-ClusteringSingle Source Shortest path (SSSP)Minimum spanning Tree (MST)主要衍生系统Giraph (2010)HAMA (2011) GPS (S
17、emih, CMU, 2012)GoldenOrb (2010)Spark (2012)工作机制在Map-Reduce机制上加入消息通讯机制In-Meomory 计算, 减少文件IO操作Pregel的Superstep使用BSP的大同步机制,Pregel: G.Malewicz, Google, 2010,研究现状-Pregel及其衍生系统,GPS & GreenMarl应用领域PageRankBetweenness Centrality工作机制Static Graph PartitionDynamic RepartitioningSingle Vertex and message objec
18、tsControlling message speedCombining MessagesMessage Buffer特点12 times faster than Giraph顶点个数只有2G个复杂算法依赖GreenMarl翻译器,GPS: Semih Salihoglu, Stanford U, 2012GreenMarl: Sungpack Hong, Oracle, 2012Jennifer Widom, 2012 未发表的工作,Salihoglu S, Widom J. GPS: A Graph Processing System. Technical Report, 2012, ht
19、tp:/ilpubs.stanford.edu:8090/1039/7/full_paper.pdfHong S, Salihoglu S, Widom J, Olukotun K. Compiling GreenMarl into GPS. Technical Report, November, 2012. http:/ppl.stanford.edu/papers/tr_gm_gps.pdf,图的并行计算研究现状-效率低,BSP model provably inefficient for some Graph algorithms,图的并行计算研究现状,Data-Parallel Gra
20、ph-Parallel,交叉验证,特征提取,Map Reduce,计算密集型频率统计, 排序,Graphical ModelsGibbs SamplingBelief PropagationVariational Opt.,半监督学习顶点扩散CoEM,图分析PageRankBFS, DFS图直径,图匹配,Data MiningClusteringFilter,BSP, eg Pregel,Asynchronous,图计算同步 v.异步,研究现状-Trility & SPARQL,Trility & SPARQL 应用领域在线查询(NoSQL, SPARQL)图算法(BFS,DFS,Pagera
21、nk)图生成与显示工作机制数据模型:超图分布式图数据库: 基于内存的图仓库,它有丰富的数据库特点Trinity支持以节点为基础的图形并行处理 (Pregel)Trinity支持在节点上的操作以异步的方式进行 (GraphLab)特点结构化的分布式图数据库,期望像查询SQL语言一样处理图算法支持 SPARQL 图查询语言.net开发,提供C# API,Trility: Bin Shao, Haixun Wang, 微软亚研, 2012,Trility 系统结构,Bin Shao, Haixun Wang, Yatao Li, The Trinity Graph Engine, http:/ (P
22、owerGraph)应用领域Graph AnalyticsGraph VisionMachine Learning工作机制异步通讯工作流程: Gather-Apply-Scatter,Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, Joseph M. Hellerstein, GraphLab: A New Framework for Parallel Machine Learning, CORR, vol. abs/1006.4, 2010Joseph Gonzalez, Yucheng L
23、ow, Haijie Gu, Danny Bickson and Carlos Guestrin, PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs,GraphLab: Yucheng Low, CMU, 2010,图的并行研究主要挑战,问题规模GraphLab (1G), GPS(2G), Trility(1G, 200G?)可扩展性GraphLab(1024 核), Trility (192 核 - 1024 +)并行效率Trility (BFS 100X Giraph, Windows)支持图算法或者
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 互联网 数据 工程 重点实验室 性能 机能 计算 技术研究 中心
限制150内