1、 2013年博士论文开题报告高可扩展并行图处理技术高可扩展并行图处理技术及其基因组装应用研究及其基因组装应用研究 答辩人：孟金涛答辩人：孟金涛导导 师：冯圣中师：冯圣中内容提要1、选题依据2、研究现状与挑战3、研究内容、目标4、拟解决的关键问题5、拟采取的研究方案可行性分析6、现已取得进展7、实验计划及时间安排8、参考文献社会媒体社会媒体 图就是对现实生活中关系的一种抽象图就是对现实生活中关系的一种抽象 图图:百亿个顶点和边，点和边还有丰富的信息百亿个顶点和边，点和边还有丰富的信息广告服务广告服务科学研究科学研究互联网互联网PeopleFactsProductsInterestsIdeas3选
2、题依据-图是无处不在的研究现状-Hadoop图处理的方法和进展 基于Hadoop开发的图处理系统 Pegasus U Kang,ICDM09 主要方法：通用矩阵向量乘法(GIM-V)应用：连通分量，PageRank,图的直径 9 服务器，问题规模1.4B点，6.7B边，性能5X加速.HAMA Sangwon Seo,CloudCom10 主要方法：Hadoop上实现的矩阵乘法 应用：矩阵乘法，可矩阵运算表示的图算法 16 服务器(共32核),矩阵规模5k X 5K研究现状-Hadoop图处理的方法和进展Surfer Rishan Chen,SoCC2012 主要方法：适应网络带宽的图划分算法
3、简单应用：统计顶点的度，邻居个数，三角统计，PageRank 问题规模 508.7M 点，29.6G 边 32服务器(共128核),基于Windows操作系统 提供两个接口MapReduce and Propagation.图分割性能提升55%，图处理性能提升671%网络流量减少3095%，执行时间减少3085%研究现状-Hadoop图处理的问题 扩展性不高 服务器数目少于32台(Surfer)，核心数少于130核 问题规模不大 最大问题规模1.4B点,6B边(Pegasus)只能处理易并行问题 例如矩阵运算，统计点的度数，连通分量，PageRank等 一些复杂问题，例如：修改图的结构的算法(
4、图的初等收缩),紧耦合问题(网络流)等，访存冲突(List ranking)图计算依赖通讯 Hadoop依赖文件系统来交换数据 Hadoop基本运算单位是MapReduce迭代 每次迭代都很耗时,hadoop上算法设计的目标就是减少迭代次数研究现状-Hadoop图处理的问题 原因分析 数据不常驻内容，每次迭代中，那些没有修改的图的数据结构，由于没有存在内存中，而需要从mapper发送到reducers去 Hadoop基于文件系统(Disk)的计算,访问延迟比较高 需要额外的MapReuce Jobs来检查是否到达了收敛要求 编程模型接口简单,语言表达能力不足(RISC VS CISC)开始尝试
5、使用或者设计复杂高效的计算模型：BSP研究现状-基于BSP图处理 基于BSP图处理系统 PBGL(Parallel Boost Graph library)Gregor,POOSC05 主要方法：基于MPI通讯原语，使用C+泛型编程开发BOOST扩展图算法库 主要应用：单源最短路径(SSSP),连通分量,最新生成树,图着色.问题规模：1M个点，15M个边 处理器个数：128核 唯一一个用C+,MPI开发的图算法库研究现状-基于BSP图处理 Google Pregel G.Malewicz,SIGMOD10 应用领域 PageRank Semi-Clustering Single Source
6、Shortest path(SSSP)Minimum spanning Tree(MST)主要衍生系统 Giraph (2010)GPS (Semih,CMU,2012)GoldenOrb (2010)Spark (2012)工作机制 在Map-Reduce机制上加入消息通讯机制 In-Meomory 计算，减少文件IO操作 Pregel的Superstep使用BSP的大同步机制Pregel:G.Malewicz,Google,2010研究现状-基于BSP图处理 GPS&GreenMarl 应用领域 PageRank Betweenness Centrality 工作机制 Static Gra
7、ph Partition Dynamic Repartitioning Single Vertex and message objects Controlling message speed Combining Messages Message Buffer 特点 12 times faster than Giraph 顶点个数只有2G个 复杂算法依赖GreenMarl翻译器GPS:Semih Salihoglu,Stanford U,2012GreenMarl:Sungpack Hong,Oracle,2012Jennifer Widom,2012 未发表的工作1.Salihoglu S,W
8、idom J.GPS:A Graph Processing System.Technical Report,2012,http:/ilpubs.stanford.edu:8090/1039/7/full_paper.pdf2.Hong S,Salihoglu S,Widom J,Olukotun K.Compiling GreenMarl into GPS.Technical Report,November,2012.http:/ppl.stanford.edu/papers/tr_gm_gps.pdf研究现状与挑战 综述最好以指标、技术路线或挑战等来组织，这样脉络比较清晰.比如：图的分割，主
9、要的方法？取得的进展？存在的问题？等等.能够量化的就尽量用量化的结果说明问题.研究现状-Hadoop MapReduce Hadoop MapReduce 适合易并行的大数据计算 特征提取 交叉验证 统计排序 图结构难划分 Hadoop不负责数据划分策略，由用户定义 图计算依赖通讯 Hadoop依赖文件系统来交换数据 Hadoop基本运算单位是MapReduce迭代 每次迭代都很耗时,hadoop上算法设计的目标就是减少迭代次数Jeffrey Dean 2008年1.Jeffrey Dean,Sanjay Ghemawat,MapReduce:simplified data processin
10、gon large clusters,Communications of the ACM-50th anniversaryissue:1958-2008 Volume 51 Issue 1,January 2008,Pages 107-113ACM New York,NY,USA2.http:/hadoop.apache.org/研究现状-基于Hadoop的图处理系统Pegasus (U Kang,CMU,2010)适用于Graph Mining Spectral clustering Diameter estimation Connected components.Surfer (Risha
11、n Chen,PKU,2010)在MapReduce上的大图处理 提供两个接口MapReduce and propagation.统计顶点的度，邻居个数相比基于BSP的图系统有两个不高效的地方 每次迭代中，那些没有修改的图的数据结构，由于没有存在内存中，而需要从mapper发送到reducers去。需要额外的MapReuce Jobs来检查是否到达了收敛要求。Pegasus:U Kang,CMU,2010Sufer:Rishan Chen,PKU 20101.U Kang,Duen Horng Chau,and Christos Faloutsos.IEEE International Con
12、ference on Acoustics,Speech,and Signal Processing(ICASSP)2012,Kyoto,Japan2.Rishan 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)大数据的并行处理 适用于机器学习和数
13、据挖掘 K-Means,Fuzzy K-Means Clustering 基于随机森林决策树的分类器 用户和项目推荐 奇异值分解.1.Mahout,http:/mahout.apache.org/研究现状Data-Parallel Graph-Parallel交叉验证特征提取Map Reduce计算密集型频率统计，排序Graphical ModelsGibbs SamplingBelief PropagationVariational Opt.半监督学习半监督学习顶点扩散CoEM图分析图分析PageRankBFS,DFS图直径，图匹配Data MiningClusteringFilterMap
14、 ReduceBSP,eg PregelBarrier研究现状-大同步模型BSP&PregelComputeCommunicateValiant 90 研究现状-基于BSP的图算法库 基于BSP的图算法库 Parallel Boost Graph Library(PBGL).Boost C+库被互联网公司广泛使用 扩展性差 可扩展到128个核心，处理图的规模有限 处理顶点规模到百万.数据一致性保证 使用ghost node 并不能减少通讯，反而带来数据一致性的问题。Memory overhead 通讯延迟1.Gregor,A.Lumsdaine,The Parallel BGL:A Gener
15、ic Library forDistributed Graph Computations,in Proc.of ParallelObject-Oriented Scientific Computing(POOSC),July 2005.2.Gregor,A.Lumsdaine,Lifting Sequential Graph Algorithms forDistributed-Memory Parallel Computation.in Proceedings of the 20thannual ACM SIGPLAN conference on Object-oriented program
16、ming,systems,languages,and applications(OOPSLA05),October 2005,pp.423-437.3.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)应用领域 PageRank Semi-Clustering Single Source Shortest path(SSSP)Minimum sp
17、anning Tree(MST)主要衍生系统 Giraph (2010)HAMA (2011)GPS (Semih,CMU,2012)GoldenOrb (2010)Spark (2012)工作机制 在Map-Reduce机制上加入消息通讯机制 In-Meomory 计算，减少文件IO操作 Pregel的Superstep使用BSP的大同步机制Pregel:G.Malewicz,Google,2010研究现状-Pregel及其衍生系统 GPS&GreenMarl 应用领域 PageRank Betweenness Centrality 工作机制 Static Graph Partition D
18、ynamic Repartitioning Single Vertex and message objects Controlling message speed Combining Messages Message Buffer 特点 12 times faster than Giraph 顶点个数只有2G个 复杂算法依赖GreenMarl翻译器GPS:Semih Salihoglu,Stanford U,2012GreenMarl:Sungpack Hong,Oracle,2012Jennifer Widom,2012 未发表的工作1.Salihoglu S,Widom J.GPS:A G
19、raph Processing System.Technical Report,2012,http:/ilpubs.stanford.edu:8090/1039/7/full_paper.pdf2.Hong 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
20、algorithms图的并行计算研究现状Data-Parallel Graph-Parallel交叉验证特征提取Map Reduce计算密集型频率统计，排序Graphical ModelsGibbs SamplingBelief PropagationVariational Opt.半监督学习半监督学习顶点扩散CoEM图分析图分析PageRankBFS,DFS图直径，图匹配Data MiningClusteringFilterBSP,eg PregelAsynchronous图计算同步 v.异步研究现状-Trility&SPARQLTrility&SPARQL 应用领域在线查询（NoSQL,S
21、PARQL)图算法(BFS,DFS,Pagerank)图生成与显示工作机制数据模型：超图分布式图数据库：基于内存的图仓库，它有丰富的数据库特点Trinity支持以节点为基础的图形并行处理(Pregel)Trinity支持在节点上的操作以异步的方式进行(GraphLab)特点结构化的分布式图数据库，期望像查询SQL语言一样处理图算法支持 SPARQL 图查询语言.net开发，提供C#APITrility:Bin Shao,Haixun Wang,微软亚研,2012Trility 系统结构1.Bin Shao,Haixun Wang,Yatao Li,The Trinity Graph Engin
22、e,http:/ 研究现状-异步图处理系统GraphLab GraphLab(PowerGraph)应用领域 Graph Analytics Graph Vision Machine Learning 工作机制 异步通讯工作工作流程：Gather-Apply-Scatter 1.Yucheng Low,Joseph Gonzalez,Aapo Kyrola,Danny Bickson,Carlos Guestrin,Joseph M.Hellerstein,GraphLab:A New Framework for Parallel Machine Learning,CORR,vol.abs/1
23、006.4,20102.Joseph Gonzalez,Yucheng Low,Haijie Gu,Danny Bickson and Carlos Guestrin，PowerGraph:Distributed Graph-Parallel Computation on Natural GraphsGraphLab:Yucheng Low,CMU,2010图的并行研究主要挑战 问题规模 GraphLab(1G),GPS(2G),Trility(1G,200G?)可扩展性 GraphLab(1024 核),Trility(192 核-1024+)并行效率 Trility(BFS 100X Gi
24、raph,Windows)支持图算法或者应用种类 GraphLab(图算法，机器学习),HAMA(图算法),Trility(在线分析，图查询语言，可视化)研究现状与挑战-图的分割 经典图划分算法 不停的交换相邻节点:KL kernighan 72 and FM Fiduccia 82 退火算法 Johnson89 遗传算法 Bui96 处理几千节点的小图，收敛的算法复杂度高（但质量很好）多层划分策略 METIS Karypis95,Chaco Hendrickson and Scotch Pellegrini96 处理1M节点的图 并行多次图划分策略 ParMetis Karypis98 an
25、d Pt-Scotch Chevalier08.处理千万节点的图研究现状与挑战-图的分割 没有上亿规模的图分割策略 没有通用有效的分割策略，一种分割策略只对部分算法有效 分割图的复杂度超过一些任务本身的复杂度 用户的领域知识 在图分割策略上比较关键 部分图处理系统只是提供接口，让用户去设置图分割策略 另一部分图处理系统，默认选择使用随机分配策略难点和分歧1.图的划分VS不划分0,AGT (0100,1000),20,GTC,(0010,0001),20,GAG,(0010,0010),20,GGC,(0001,0001),21,CCT,(0100,0100),42,TCG,(1000,0110
26、),5 0,TTA,(0010,0000)1,CTT,(1000,0100),22,GCT,(0001,0100),32,TAG,(0001,1000),21.局部性差：每个顶点随机的和若干其他顶点相连2.图最优划分难度大：图的最优划分是NP难问题3.远程访问通讯代价高：图不同划分间随机访问依赖于网络通讯，而大规模的异地访存延迟实际是通讯延迟，访存带宽是通讯带宽问题和分歧2.计算竞争 领域翻译语言 VS 精简接口0,AGT (0100,1000),20,GTC,(0010,0001),20,GAG,(0010,0010),20,GGC,(0001,0001),21,CCT,(0100,0100
27、),42,TCG,(1000,0110),5 0,TTA,(0010,0000)1,CTT,(1000,0100),22,GCT,(0001,0100),32,TAG,(0001,1000),22.非本地读写互斥：远程读写要互斥，防止读脏数据3.访存一致性：本地数据和远程数据一致性1.随机访问：顶点访问是完全随机的问题和分歧3.并行效率 通用VS特殊优化策略 消除/减弱计算依赖 支持乱序执行 并行度最大化 可扩展性This is hard 如何判断一个大规模图上的操作是可以并行处理的 如何设计一个适合并行处理大规模图的计算模型 如何开发科处理大规模图上的常用算法的通用系统大图并行的解决方案高可
28、扩展并行图处理系统研究内容本课题针对高可扩展并行图处理系统在海量复杂生物数据的分析组装的应用，力图从以下3个方面展开研究：可扩展的图算法数学抽象可扩展的图算法数学抽象：使用基于群论的代数系统来抽象图算法，使得图算法上的边和点对应于计算机中的计算操作和访存地址，并将该读写操作规约为原子操作，使得多个这样的互斥的原子操作可以同时并发执行。可扩展的并行计算模型可扩展的并行计算模型:基于子集同步全局异步的并行计算模型。可扩展的并行图处理框架可扩展的并行图处理框架：基于子集同步计算模型，开发可自动挖掘潜在并行子集，自动回避读写冲突，尽可能的提高系统效率的并行图处理框架。在以上三方面进行深入的研究后，开发
29、性能优异的系统原型系统以运用于海量复杂生物数据的组装分析。研究目标 本课题将围绕高可扩展图处理系统的研究和开发，以海量复杂生物数据上的组装分析为应用，期望达到如下目标：使用代数系统的半群来抽象在大规模图结构上的现实问题。提出计算模型来处理一部分紧耦合难并行的大规模图算法。开发新的大规模图处理框架，其可处理的最大数据量可到100T,图顶点规模可达到200G，系统可运行于万颗核心。基于该图处理框架开发的生物数据的组装应用软件，可以在1小时内处理分析完人类数据，并达到现有最快的商业组装软件40倍加速。研究目标-可扩展性研究目标-图规模研究目标-计算时间拟解决的关键问题 本课题拟解决的4个关键问题：复
30、杂生物数据组装问题等价于一个代数系统上的半群 弱关联紧耦合的图算法可以用更加泛化的代数系统中的半群来描述 子集同步全局异步的计算模型 能够最大程度的挖掘半群中的可并行子集的图处理框架拟采取的研究方案-算法数学抽象 算法数学抽象：确定可解决问题的范围 图是弱关联的 图可以是紧耦合 求解的是全局问题 计算是规则的 确定计算抽象 抽象出原子计算 确定计算关联的数据 确定计算关联的集合生物组装抽象为边合并1.Jintao Meng,Jianrui Yuan,Yanjie Wei,Jiefeng Cheng,Shengzhong Feng,Small World Asynchronous Paralle
31、l Model for Genome Assembly,in 9th IFIP International Conference on Network and Parallel Computing(NPC 2012),Sep.6,Gwangju,Korea(EI)拟采取的研究方案-算法数学抽象 算法数学抽象：确定可解决问题的范围 图是弱关联的 图可以是紧耦合 求解的是全局问题 计算是规则的 确定计算抽象 抽象出原子计算 确定计算关联的数据 确定计算关联的集合迭代直到收敛：我的权重就是我邻居的权重的平均值拟采取的研究方案-计算模型 计算模型（路由协议）匹配数据和计算 缺失数据调取 数据一致性保证
32、 更新数据 以计算为核心 数据可随机分布 数据传输依赖网络 互斥协议保证 同步依赖于消息 互斥依赖于信令最大的人工网络：互联网唯一的计算就是路由其路由是实时自动计算的1.Liansheng Tan,Jintao Meng,Jie Li and Han-Chieh Chao,PH-MAC:A Periodically Hybrid MAC Protocol for Wireless sensor networks,Journal of Internet Technology,Taiwan,Nov 2007.(SCI,Impact Factor=0.508)拟采取的研究方案-计算模型 计算模型（路
33、由协议）匹配数据和计算 缺失数据调取 数据一致性保证 更新数据 以计算为核心 数据可随机分布 数据传输依赖网络 互斥协议保证 同步依赖于消息 互斥依赖于信令网络只负责路由（数据移动）网络不负责内容（计算）网络是自组织的网络是无尺度的1.Jintao Meng,Jianrui Yuan,Shengzhong Feng,Yanjie Wei.An Energy Efficient Clustering Scheme for Data Aggregation in Wireless Sensor Networks,(to appear)In Journal of Computer Science a
34、nd Technology,2013.(SCI 3区,Impact Factor=0.656)2.Jintao Meng,Jianrui Yuan,Shengzhong Feng,Liansheng Tan,A Power Adjusting Algorithm on Mobility Control in Mobile Ad Hoc Networks.Journal of Computer Science and Technology,2013,V28(1):42-53 (SCI,Impact Factor=0.656)拟采取的研究方案-系统开发应用 系统开发 计算模型的实现 系统框架的抽象
35、 统一接口的提供 系统应用 生物数据组装 单源最短路径（路由）双链表排序1.数据有组织的哈希随机分布2.每个进程既有通讯部，又有计算部系统抽象结构1.Jintao Meng,Jianrui Yuan,Yanjie Wei,Jiefeng Cheng,Shengzhong Feng,Small World Asynchronous Parallel Model for Genome Assembly,in 9th IFIP International Conference on Network and Parallel Computing(NPC 2012),Sep.6,Gwangju,Kore
36、a(EI)2.Jintao Meng,Bingqiang Wang,Yanjie Wei,Jiefeng Cheng,Shengzhong Feng,Pavan Balaji.SWAP-Assembler:A Scalable De Bruijn Graph Based Assembler for Massive Genome Data,in 17th annual international conference on research in computational molecular biology(RECOMB 2013),April,2013.(Poster)研究方案可行性分析通过
37、引入代数系统中的半群和子集同步全局异步的计算模型来提高图处理框架应用的针对性和系统的可扩展性。在开展本课题前我们做了如下可行性分析：1）分析现有的基于de Bruijn图的组装技术实现原理，简要介绍基于该策略实现的四种拼接软件的实现并对比分析其性能，这四个软件包括Velvet、SOAPdenovo、IDBA、ABySS；2）对生物数据组装的主要流程进行分析，找出其运算量最大的几个模块，并对需要并行计算的模块进行分析，找出并行切实可行的实现方案；3）针对当前基于de Bruijn图的组装方法并行化难度高的特点，设计优化的de Bruijn图结构，并对其并行可行性进行严格的分析与论证。4）由于序列
38、拼接问题本质是一个图的问题，而现有的图处理软件或者库，例如Boost Graph,Prajel,都无法扩展到1000个节点以上。所以设计新的适合图的计算模型以最大限度的挖掘图的计算问题中的潜在并行性。已取得进展-理论研究 可解问题归纳 若一个图算法可分解为一系列满足结合律的操作，那么该算法就可被定义为一个半群Q(V,+)上的活动ACT(V,)通过计算ACT(V,)即可完成对应的图算法。理论应用 生物数据组装可表示为双向多步De Bruijn图上的边合并操作。（二元计算）PageRank可表示为Web站点上的权重聚合操作（多元计算）已取得进展-理论研究Multi-step bi-directed
39、 graphInput readsAGTACTGTCGAC+C/T+TCGCGATAGCTA+T/A+A/A-GAGCTCCCTAGG+C/G-G/G+G/C+Reference SequenceYellow vertex can be extend furtherGray vertices can not be extended further(Neighbor=RC)Dotted edges can be merged 已取得进展-理论研究依赖图迭代My RankFriends Rank计算PageRank已取得进展-计算模型 异步计算模型 子集同步全局异步 自动寻找可并行子集 基于子集合
40、的计算可异步启动，乱序执行（满足结合律）并发读写操作自动互斥 使用改进的CDMA/CA（载波侦听多路复用/冲突避免）技术 互斥 使用Binary Backoff算法 进行冲突后回避ComputeLockUnlockSWAP 计算模型已取得进展-系统开发 系统开发 当前基于SWAP异步计算模型的图处理框架可扩展到1024个核心 SWAP图处理框架在处理海量生物数据组装应用时在1024核心内科达到近线性加速 系统应用 并行生物数据组装，可在1小时左右处理1T人类生物数据，处理速度是现有的最快的组装软件40倍。实验计划及时间安排2012.1-2012.6阅读文献归纳已有图处理系统2012.7-201
41、2.12用半群来抽象生物大数据应用2013.1-2013.6适合半群计算的异步计算模型2013.6-2013.12开发图处理框架测试其扩展性2014.1-2014.62014.6-2014.12图处理框架生物信息分析应用图处理通用框架论文撰写发表 参考文献1 Jintao Meng,Jianrui Yuan,Shengzhong Feng,Yanjie Wei.An Energy Efficient Clustering Scheme for Data Aggregation in Wireless Sensor Networks,(to appear)In Journal of Comput
42、er Science and Technology,2013.(SCI 3区,Impact Factor=0.656)2 Jintao Meng,Bingqiang Wang,Yanjie Wei,Jiefeng Cheng,Shengzhong Feng,Pavan Balaji.SWAP-Assembler:A Scalable De Bruijn Graph Based Assembler for Massive Genome Data,in 17th annual international conference on research in computational molecul
43、ar biology(RECOMB 2013),April,2013.(EI,Poster)3 Jintao Meng,Jianrui Yuan,Shengzhong Feng,Yanjie Wei.An Energy Efficient Clustering Scheme for Data Aggregation in Wireless Sensor Networks,In Journal of Computer Science and Technology,2013,28(1):42-53.(SCI,Impact Factor=0.656)4 Li Zeng,Jiefeng Cheng,J
44、intao Meng,Bingqiang Wang,Shengzhong Feng.Improved Parallel Processing of Massive De Bruijn Graph for Genome Assembly,in 15th Asia-Pacific web conference(APWeb 2013),April,2013,Sydney,Australia.5 Jintao Meng,Jianrui Yuan,Yanjie Wei,Jiefeng Cheng,Shengzhong Feng,Small World Asynchronous Parallel Mode
45、l for Genome Assembly,in 9th IFIP International Conference on Network and Parallel Computing(NPC 2012),Sep.6,Gwangju,Korea(EI)6 Jintao Meng,Jianrui Yuan,Yanjie Wei,Jiefeng Cheng,Shengzhong Feng,DGraph:Algorithms for Shortgun Reads Assembly Using De Bruijn Graph,in 9th IFIP International Conference on Network and Parallel Computing(NPC 2012),Sep.6,Gwangju,Korea(EI).7.Liansheng Tan,Jintao Meng,Jie Li and Han-Chieh Chao,PH-MAC:A Periodically Hybrid MAC Protocol for Wireless sensor networks,Journal of Internet Technology,Taiwan,Nov 2007.(SCI 4区,Impact Factor=0.508)Thanks
