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)支持图算法或者
24、应用种类GraphLab(图算法，机器学习), HAMA(图算法), Trility(在线分析，图查询语言，可视化),研究现状与挑战-图的分割,经典图划分算法不停的交换相邻节点: KL kernighan 72 and FM Fiduccia 82 退火算法 Johnson89 遗传算法 Bui96 处理几千节点的小图， 收敛的算法复杂度高 （但质量很好）多层划分策略METIS Karypis95, Chaco Hendrickson and Scotch Pellegrini96 处理1M节点的图并行多次图划分策略ParMetis Karypis98 and Pt-Scotch Cheval
25、ier08. 处理千万节点的图,研究现状与挑战-图的分割,没有上亿规模的图分割策略没有通用有效的分割策略，一种分割策略只对部分算法有效分割图的复杂度超过一些任务本身的复杂度用户的领域知识 在图分割策略上比较关键部分图处理系统只是提供接口，让用户去设置图分割策略另一部分图处理系统，默认选择使用随机分配策略,难点和分歧1. 图的划分VS不划分,0, AGT (0100,1000), 2,0, GTC, (0010,0001), 2,0, GAG, (0010,0010), 2,0, GGC, (0001,0001), 2,1, CCT, (0100,0100), 4,2, TCG, (1000,0
26、110), 5,0, TTA, (0010,0000),1, CTT, (1000,0100), 2,2, GCT, (0001,0100), 3,2, TAG, (0001,1000), 2,1.局部性差： 每个顶点随机的和若干其他顶点相连,2. 图最优划分难度大： 图的最优划分是NP难问题,3. 远程访问通讯代价高：图不同划分间随机访问依赖于网络通讯，而大规模的异地访存延迟实际是通讯延迟，访存带宽是通讯带宽,问题和分歧2. 计算竞争 领域翻译语言 VS 精简接口,0, AGT (0100,1000), 2,0, GTC, (0010,0001), 2,0, GAG, (0010,0010)
27、, 2,0, GGC, (0001,0001), 2,1, CCT, (0100,0100), 4,2, TCG, (1000,0110), 5,0, TTA, (0010,0000),1, CTT, (1000,0100), 2,2, GCT, (0001,0100), 3,2, TAG, (0001,1000), 2,2. 非本地读写互斥： 远程读写要互斥，防止读脏数据,3. 访存一致性：本地数据和远程数据一致性,1. 随机访问：顶点访问是完全随机的,问题和分歧3. 并行效率 通用VS特殊优化策略,消除/减弱计算依赖支持乱序执行并行度最大化可扩展性,This is hard,如何判断一个大
28、规模图上的操作是可以并行处理的如何设计一个适合并行处理大规模图的计算模型如何开发科处理大规模图上的常用算法的通用系统,大图并行的解决方案,高可扩展并行图处理系统,研究内容,本课题针对高可扩展并行图处理系统在海量复杂生物数据的分析组装的应用，力图从以下3个方面展开研究：可扩展的图算法数学抽象：使用基于群论的代数系统来抽象图算法，使得图算法上的边和点对应于计算机中的计算操作和访存地址，并将该读写操作规约为原子操作，使得多个这样的互斥的原子操作可以同时并发执行。可扩展的并行计算模型: 基于子集同步全局异步的并行计算模型。可扩展的并行图处理框架：基于子集同步计算模型，开发可自动挖掘潜在并行子集，自动回
29、避读写冲突，尽可能的提高系统效率的并行图处理框架。在以上三方面进行深入的研究后，开发性能优异的系统原型系统以运用于海量复杂生物数据的组装分析。,研究目标,本课题将围绕高可扩展图处理系统的研究和开发，以海量复杂生物数据上的组装分析为应用，期望达到如下目标： 使用代数系统的半群来抽象在大规模图结构上的现实问题。 提出计算模型来处理一部分紧耦合难并行的大规模图算法。开发新的大规模图处理框架，其可处理的最大数据量可到100T, 图顶点规模可达到200G，系统可运行于万颗核心。基于该图处理框架开发的生物数据的组装应用软件，可以在1小时内处理分析完人类数据，并达到现有最快的商业组装软件40倍加速。,研究目
30、标-可扩展性,研究目标-图规模,研究目标-计算时间,拟解决的关键问题,本课题拟解决的4个关键问题：复杂生物数据组装问题等价于一个代数系统上的半群弱关联紧耦合的图算法可以用更加泛化的代数系统中的半群来描述 子集同步全局异步的计算模型 能够最大程度的挖掘半群中的可并行子集的图处理框架,拟采取的研究方案-算法数学抽象,算法数学抽象：确定可解决问题的范围图是弱关联的图可以是紧耦合求解的是全局问题计算是规则的确定计算抽象抽象出原子计算确定计算关联的数据确定计算关联的集合,生物组装抽象为边合并,Jintao Meng, Jianrui Yuan, Yanjie Wei, Jiefeng Cheng, Sh
31、engzhong Feng, Small World Asynchronous Parallel Model for Genome Assembly, in 9th IFIP International Conference on Network and Parallel Computing (NPC 2012), Sep.6, Gwangju, Korea (EI),拟采取的研究方案-算法数学抽象,算法数学抽象：确定可解决问题的范围图是弱关联的图可以是紧耦合求解的是全局问题计算是规则的确定计算抽象抽象出原子计算确定计算关联的数据确定计算关联的集合,迭代直到收敛：我的权重就是我邻居的权重的平均
32、值,拟采取的研究方案-计算模型,计算模型 （路由协议）匹配数据和计算缺失数据调取数据一致性保证更新数据以计算为核心数据可随机分布数据传输依赖网络互斥协议保证同步依赖于消息互斥依赖于信令,最大的人工网络： 互联网唯一的计算就是路由其路由是实时自动计算的,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 20
33、07. (SCI, Impact Factor = 0.508),拟采取的研究方案-计算模型,计算模型 （路由协议）匹配数据和计算缺失数据调取数据一致性保证更新数据以计算为核心数据可随机分布数据传输依赖网络互斥协议保证同步依赖于消息互斥依赖于信令,网络只负责路由（数据移动）网络不负责内容（计算）网络是自组织的网络是无尺度的,Jintao Meng, Jianrui Yuan, Shengzhong Feng, Yanjie Wei. An Energy Efficient Clustering Scheme for Data Aggregation in Wireless Sensor Net
34、works, (to appear) In Journal of Computer Science and Technology, 2013. (SCI 3区, Impact Factor = 0.656)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
35、(SCI, Impact Factor = 0.656),拟采取的研究方案-系统开发应用,系统开发计算模型的实现系统框架的抽象统一接口的提供系统应用生物数据组装单源最短路径（路由）双链表排序,1. 数据有组织的哈希随机分布2. 每个进程既有通讯部， 又有计算部,系统抽象结构,Jintao Meng, Jianrui Yuan, Yanjie Wei, Jiefeng Cheng, Shengzhong Feng, Small World Asynchronous Parallel Model for Genome Assembly, in 9th IFIP International Conf
36、erence on Network and Parallel Computing (NPC 2012), Sep.6, Gwangju, Korea (EI) 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 resear
37、ch in computational molecular biology (RECOMB 2013), April, 2013. (Poster),研究方案可行性分析,通过引入代数系统中的半群和子集同步全局异步的计算模型来提高图处理框架应用的针对性和系统的可扩展性。在开展本课题前我们做了如下可行性分析：1）分析现有的基于de Bruijn图的组装技术实现原理，简要介绍基于该策略实现的四种拼接软件的实现并对比分析其性能，这四个软件包括Velvet、SOAPdenovo、IDBA、ABySS；2）对生物数据组装的主要流程进行分析，找出其运算量最大的几个模块，并对需要并行计算的模块进行分析，找出并
38、行切实可行的实现方案；3）针对当前基于de Bruijn图的组装方法并行化难度高的特点，设计优化的de Bruijn图结构，并对其并行可行性进行严格的分析与论证。4）由于序列拼接问题本质是一个图的问题，而现有的图处理软件或者库，例如Boost Graph, Prajel, 都无法扩展到1000个节点以上。所以设计新的适合图的计算模型以最大限度的挖掘图的计算问题中的潜在并行性。,已取得进展-理论研究,可解问题归纳若一个图算法可分解为一系列满足结合律的操作，那么该算法就可被定义为一个半群Q(V, +)上的活动ACT(V,)通过计算ACT(V,)即可完成对应的图算法。理论应用生物数据组装可表示为双向
39、多步De Bruijn图上的边合并操作。（二元计算）PageRank可表示为Web站点上的权重聚合操作（多元计算）,已取得进展-理论研究,Multi-step bi-directed graph,Input reads,AGTACT,GTCGAC,+ C/T +,TCGCGA,TAGCTA,+ T/A+,+ A/A -,GAGCTC,CCTAGG,+ C/G -,- G/G +,+ G/C +,Reference Sequence,Yellow vertex can be extend further,Gray vertices can not be extended further (Nei
40、ghbor = RC),Dotted edges can be merged,已取得进展-理论研究,依赖图,PageRank,已取得进展-计算模型,异步计算模型子集同步全局异步自动寻找可并行子集基于子集合的计算可异步启动，乱序执行 （满足结合律）并发读写操作自动互斥使用改进的CDMA/CA（载波侦听多路复用/冲突避免）技术 互斥使用Binary Backoff算法 进行冲突后回避,SWAP 计算模型,已取得进展-系统开发,系统开发当前基于SWAP异步计算模型的图处理框架可扩展到1024个核心SWAP图处理框架在处理海量生物数据组装应用时在1024核心内科达到近线性加速系统应用并行生物数据组装，
41、 可在1小时左右处理1T人类生物数据，处理速度是现有的最快的组装软件40倍。,实验计划及时间安排,2012.1-2012.6,阅读文献归纳已有图处理系统,2012.7-2012.12,用半群来抽象生物大数据应用,2013.1-2013.6,适合半群计算的异步计算模型,2013.6-2013.12,开发图处理框架测试其扩展性,2014.1-2014.6,2014.6-2014.12,图处理框架生物信息分析应用,图处理通用框架论文撰写发表,参考文献,1 Jintao Meng, Jianrui Yuan, Shengzhong Feng, Yanjie Wei. An Energy Efficie
42、nt Clustering Scheme for Data Aggregation in Wireless Sensor Networks, (to appear) In Journal of Computer 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
43、Based Assembler for Massive Genome Data, in 17th annual international conference on research in computational molecular 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 Se
44、nsor Networks, In Journal of Computer Science and Technology, 2013, 28(1):42-53. (SCI, Impact Factor = 0.656)4 Li Zeng, Jiefeng Cheng, Jintao Meng, Bingqiang Wang, Shengzhong Feng. Improved Parallel Processing of Massive De Bruijn Graph for Genome Assembly, in 15th Asia-Pacific web conference (APWeb
45、 2013), April, 2013, Sydney, Australia.5 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, Korea (EI) 6 Jintao Meng, Ji
46、anrui 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,
