互聯(lián)網(wǎng)數(shù)據(jù)工程重點(diǎn)試驗(yàn)室課件

1、 2013年博士論文開題報(bào)告高可擴(kuò)展并行圖處理技術(shù)及其基因組裝應(yīng)用研究 答辯人：孟金濤導(dǎo) 師：馮圣中內(nèi)容提要1、選題依據(jù)2、研究現(xiàn)狀與挑戰(zhàn)3、研究內(nèi)容、目標(biāo)4、擬解決的關(guān)鍵問題5、擬采取的研究方案可行性分析6、現(xiàn)已取得進(jìn)展7、實(shí)驗(yàn)計(jì)劃及時(shí)間安排8、參考文獻(xiàn)社會(huì)媒體圖就是對(duì)現(xiàn)實(shí)生活中關(guān)系的一種抽象圖: 百億個(gè)頂點(diǎn)和邊，點(diǎn)和邊還有豐富的信息廣告服務(wù)科學(xué)研究互聯(lián)網(wǎng)PeopleFactsProductsInterestsIdeas3選題依據(jù)-圖是無處不在的研究現(xiàn)狀-Hadoop圖處理的方法和進(jìn)展基于Hadoop開發(fā)的圖處理系統(tǒng)Pegasus U Kang,ICDM09主要方法：通用矩陣向量乘法(GIM

2、-V) 應(yīng)用：連通分量，PageRank, 圖的直徑9 服務(wù)器，問題規(guī)模1.4B點(diǎn)，6.7B邊，性能5X加速.HAMA Sangwon Seo, CloudCom10主要方法： Hadoop上實(shí)現(xiàn)的矩陣乘法應(yīng)用：矩陣乘法，可矩陣運(yùn)算表示的圖算法16 服務(wù)器(共32核), 矩陣規(guī)模5k X 5K研究現(xiàn)狀-Hadoop圖處理的方法和進(jìn)展Surfer Rishan Chen, SoCC2012主要方法：適應(yīng)網(wǎng)絡(luò)帶寬的圖劃分算法簡單應(yīng)用： 統(tǒng)計(jì)頂點(diǎn)的度，鄰居個(gè)數(shù)，三角統(tǒng)計(jì)，PageRank問題規(guī)模 508.7M 點(diǎn)， 29.6G 邊32服務(wù)器(共128核), 基于Windows操作系統(tǒng)提供兩個(gè)接口Ma

3、pReduce and Propagation.圖分割性能提升55%，圖處理性能提升671%網(wǎng)絡(luò)流量減少3095%，執(zhí)行時(shí)間減少3085%研究現(xiàn)狀-Hadoop圖處理的問題擴(kuò)展性不高服務(wù)器數(shù)目少于32臺(tái)(Surfer)，核心數(shù)少于130核問題規(guī)模不大最大問題規(guī)模1.4B點(diǎn),6B邊(Pegasus)只能處理易并行問題例如矩陣運(yùn)算，統(tǒng)計(jì)點(diǎn)的度數(shù)，連通分量，PageRank等一些復(fù)雜問題，例如：修改圖的結(jié)構(gòu)的算法(圖的初等收縮), 緊耦合問題(網(wǎng)絡(luò)流)等，訪存沖突(List ranking)圖計(jì)算依賴通訊Hadoop依賴文件系統(tǒng)來交換數(shù)據(jù)Hadoop基本運(yùn)算單位是MapReduce迭代每次迭代都很耗

4、時(shí),hadoop上算法設(shè)計(jì)的目標(biāo)就是減少迭代次數(shù)研究現(xiàn)狀-Hadoop圖處理的問題原因分析數(shù)據(jù)不常駐內(nèi)容，每次迭代中，那些沒有修改的圖的數(shù)據(jù)結(jié)構(gòu)，由于沒有存在內(nèi)存中，而需要從mapper發(fā)送到reducers去 Hadoop基于文件系統(tǒng)(Disk)的計(jì)算, 訪問延遲比較高需要額外的MapReuce Jobs來檢查是否到達(dá)了收斂要求編程模型接口簡單, 語言表達(dá)能力不足(RISC VS CISC)開始嘗試使用或者設(shè)計(jì)復(fù)雜高效的計(jì)算模型： BSP研究現(xiàn)狀-基于BSP圖處理基于BSP圖處理系統(tǒng)PBGL (Parallel Boost Graph library) Gregor, POOSC05主要方法

5、： 基于MPI通訊原語，使用C+泛型編程開發(fā)BOOST擴(kuò)展圖算法庫主要應(yīng)用： 單源最短路徑(SSSP), 連通分量, 最新生成樹,圖著色.問題規(guī)模： 1M個(gè)點(diǎn)，15M個(gè)邊處理器個(gè)數(shù)： 128核唯一一個(gè)用C+, MPI開發(fā)的圖算法庫研究現(xiàn)狀-基于BSP圖處理Google Pregel G. Malewicz , SIGMOD10應(yīng)用領(lǐng)域PageRankSemi-ClusteringSingle Source Shortest path (SSSP)Minimum spanning Tree (MST)主要衍生系統(tǒng)Giraph (2010)GPS (Semih, CMU, 2012)GoldenO

6、rb (2010)Spark (2012)工作機(jī)制在Map-Reduce機(jī)制上加入消息通訊機(jī)制In-Meomory 計(jì)算， 減少文件IO操作Pregel的Superstep使用BSP的大同步機(jī)制Pregel: G.Malewicz, Google, 2010研究現(xiàn)狀-基于BSP圖處理GPS & GreenMarl應(yīng)用領(lǐng)域PageRankBetweenness Centrality工作機(jī)制Static Graph PartitionDynamic RepartitioningSingle Vertex and message objectsControlling message speedCom

7、bining MessagesMessage Buffer特點(diǎn)12 times faster than Giraph頂點(diǎn)個(gè)數(shù)只有2G個(gè)復(fù)雜算法依賴GreenMarl翻譯器GPS: Semih Salihoglu, Stanford U, 2012GreenMarl: Sungpack Hong, Oracle, 2012Jennifer Widom, 2012 未發(fā)表的工作Salihoglu S, Widom J. GPS: A Graph Processing System. Technical Report, 2012, :8090/1039/7/full_paper.pdfHong S,

8、 Salihoglu S, Widom J, Olukotun K. Compiling GreenMarl into GPS. Technical Report, November, 2012. /papers/tr_gm_gps.pdf研究現(xiàn)狀與挑戰(zhàn)綜述最好以指標(biāo)、技術(shù)路線或挑戰(zhàn)等來組織，這樣脈絡(luò)比較清晰. 比如：圖的分割，主要的方法？取得的進(jìn)展？存在的問題？等等. 能夠量化的就盡量用量化的結(jié)果說明問題. 研究現(xiàn)狀-Hadoop MapReduceHadoop MapReduce適合易并行的大數(shù)據(jù)計(jì)算特征提取交叉驗(yàn)證統(tǒng)計(jì)排序圖結(jié)構(gòu)難劃分Hadoop不負(fù)責(zé)數(shù)據(jù)劃分策略，由用戶定義圖計(jì)算依賴通

9、訊Hadoop依賴文件系統(tǒng)來交換數(shù)據(jù)Hadoop基本運(yùn)算單位是MapReduce迭代每次迭代都很耗時(shí),hadoop上算法設(shè)計(jì)的目標(biāo)就是減少迭代次數(shù)Jeffrey Dean 2008年Jeffrey Dean, Sanjay Ghemawat, MapReduce: simplified data processingon large clusters, Communications of the ACM - 50th anniversaryissue: 1958 - 2008 Volume 51 Issue 1, January 2008, Pages 107-113ACM New York,

10、 NY, USA/ 研究現(xiàn)狀-基于Hadoop的圖處理系統(tǒng)Pegasus (U Kang, CMU, 2010)適用于Graph MiningSpectral clusteringDiameter estimationConnected components.Surfer (Rishan Chen, PKU, 2010)在MapReduce上的大圖處理提供兩個(gè)接口MapReduce and propagation.統(tǒng)計(jì)頂點(diǎn)的度，鄰居個(gè)數(shù)相比基于BSP的圖系統(tǒng)有兩個(gè)不高效的地方 每次迭代中，那些沒有修改的圖的數(shù)據(jù)結(jié)構(gòu)，由于沒有存在內(nèi)存中，而需要從mapper發(fā)送到reducers去。 需要額外的

11、MapReuce Jobs來檢查是否到達(dá)了收斂要求。Pegasus: U Kang, CMU, 2010Sufer: Rishan Chen, PKU 2010U Kang, Duen Horng Chau, and Christos Faloutsos. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2012, Kyoto, JapanRishan Chen,Xuetian Weng,Bingsheng He,Mao Yang, Large graph processing

12、 in the cloud, in Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010研究現(xiàn)狀-基于Hadoop的圖處理系統(tǒng)Mahout (2010)大數(shù)據(jù)的并行處理適用于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘K-Means, Fuzzy K-Means Clustering基于隨機(jī)森林決策樹的分類器用戶和項(xiàng)目推薦奇異值分解.Mahout, /研究現(xiàn)狀Data-Parallel Graph-Parallel交叉驗(yàn)證特征提取Map Reduce計(jì)算密集型頻率統(tǒng)計(jì)， 排序Graphical

13、ModelsGibbs SamplingBelief PropagationVariational Opt.半監(jiān)督學(xué)習(xí)頂點(diǎn)擴(kuò)散CoEM圖分析PageRankBFS, DFS圖直徑，圖匹配Data MiningClusteringFilterMap ReduceBSP, eg PregelBarrier研究現(xiàn)狀-大同步模型BSP & PregelComputeCommunicateValiant 90 研究現(xiàn)狀-基于BSP的圖算法庫基于BSP的圖算法庫Parallel Boost Graph Library (PBGL).Boost C+ 庫被互聯(lián)網(wǎng)公司廣泛使用擴(kuò)展性差可擴(kuò)展到128個(gè)核心，處理

14、圖的規(guī)模有限處理頂點(diǎn)規(guī)模到百萬.數(shù)據(jù)一致性保證使用ghost node 并不能減少通訊，反而帶來數(shù)據(jù)一致性的問題。Memory overhead通訊延遲Gregor, A. Lumsdaine, The Parallel BGL: A Generic Library forDistributed Graph Computations, in Proc. of ParallelObject-Oriented Scientific Computing (POOSC), July 2005.Gregor, A. Lumsdaine, Lifting Sequential Graph Algorith

15、ms forDistributed-Memory Parallel Computation. in Proceedings of the 20thannual ACM SIGPLAN conference on Object-oriented programming,systems, languages, and applications (OOPSLA05), October 2005, pp.423-437./doc/libs/1_53_0/libs/graph_parallel/doc/html/index.html Douglas Gregor 2005年研究現(xiàn)狀-Pregel及其衍生

16、系統(tǒng)Google Pregel (G. Malewicz , google, 2010)應(yīng)用領(lǐng)域PageRankSemi-ClusteringSingle Source Shortest path (SSSP)Minimum spanning Tree (MST)主要衍生系統(tǒng)Giraph (2010)HAMA (2011) GPS (Semih, CMU, 2012)GoldenOrb (2010)Spark (2012)工作機(jī)制在Map-Reduce機(jī)制上加入消息通訊機(jī)制In-Meomory 計(jì)算， 減少文件IO操作Pregel的Superstep使用BSP的大同步機(jī)制Pregel: G.M

17、alewicz, Google, 2010研究現(xiàn)狀-Pregel及其衍生系統(tǒng)GPS & GreenMarl應(yīng)用領(lǐng)域PageRankBetweenness Centrality工作機(jī)制Static Graph PartitionDynamic RepartitioningSingle Vertex and message objectsControlling message speedCombining MessagesMessage Buffer特點(diǎn)12 times faster than Giraph頂點(diǎn)個(gè)數(shù)只有2G個(gè)復(fù)雜算法依賴GreenMarl翻譯器GPS: Semih Salihogl

18、u, Stanford U, 2012GreenMarl: Sungpack Hong, Oracle, 2012Jennifer Widom, 2012 未發(fā)表的工作Salihoglu S, Widom J. GPS: A Graph Processing System. Technical Report, 2012, :8090/1039/7/full_paper.pdfHong S, Salihoglu S, Widom J, Olukotun K. Compiling GreenMarl into GPS. Technical Report, November, 2012. /pape

19、rs/tr_gm_gps.pdf圖的并行計(jì)算研究現(xiàn)狀-效率低BSP model provably inefficient for some Graph algorithms圖的并行計(jì)算研究現(xiàn)狀Data-Parallel Graph-Parallel交叉驗(yàn)證特征提取Map Reduce計(jì)算密集型頻率統(tǒng)計(jì)， 排序Graphical ModelsGibbs SamplingBelief PropagationVariational Opt.半監(jiān)督學(xué)習(xí)頂點(diǎn)擴(kuò)散CoEM圖分析PageRankBFS, DFS圖直徑，圖匹配Data MiningClusteringFilterBSP, eg PregelA

20、synchronous圖計(jì)算同步 v.異步研究現(xiàn)狀-Trility & SPARQLTrility & SPARQL 應(yīng)用領(lǐng)域在線查詢（NoSQL, SPARQL)圖算法(BFS,DFS,Pagerank)圖生成與顯示工作機(jī)制數(shù)據(jù)模型：超圖分布式圖數(shù)據(jù)庫： 基于內(nèi)存的圖倉庫，它有豐富的數(shù)據(jù)庫特點(diǎn)Trinity支持以節(jié)點(diǎn)為基礎(chǔ)的圖形并行處理 (Pregel)Trinity支持在節(jié)點(diǎn)上的操作以異步的方式進(jìn)行 (GraphLab)特點(diǎn)結(jié)構(gòu)化的分布式圖數(shù)據(jù)庫，期望像查詢SQL語言一樣處理圖算法支持 SPARQL 圖查詢語言.net開發(fā)，提供C# APITrility: Bin Shao, Haixun

21、 Wang, 微軟亞研, 2012Trility 系統(tǒng)結(jié)構(gòu)Bin Shao, Haixun Wang, Yatao Li, The Trinity Graph Engine, /pubs/161291/Trinity.pdf 研究現(xiàn)狀-異步圖處理系統(tǒng)GraphLabGraphLab (PowerGraph)應(yīng)用領(lǐng)域Graph AnalyticsGraph VisionMachine Learning工作機(jī)制異步通訊工作流程： Gather-Apply-Scatter Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos

22、 Guestrin, Joseph M. Hellerstein, GraphLab: A New Framework for Parallel Machine Learning, CORR, vol. abs/1006.4, 2010Joseph Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson and Carlos Guestrin， PowerGraph: Distributed Graph-Parallel Computation on Natural GraphsGraphLab: Yucheng Low, CMU, 2010圖的并行研究

23、主要挑戰(zhàn)問題規(guī)模GraphLab (1G), GPS(2G), Trility(1G, 200G?)可擴(kuò)展性GraphLab(1024 核), Trility (192 核 - 1024 +)并行效率Trility (BFS 100X Giraph, Windows)支持圖算法或者應(yīng)用種類GraphLab(圖算法，機(jī)器學(xué)習(xí)), HAMA(圖算法), Trility(在線分析，圖查詢語言，可視化)研究現(xiàn)狀與挑戰(zhàn)-圖的分割經(jīng)典圖劃分算法不停的交換相鄰節(jié)點(diǎn): KL kernighan 72 and FM Fiduccia 82 退火算法 Johnson89 遺傳算法 Bui96 處理幾千節(jié)點(diǎn)的小圖，

24、 收斂的算法復(fù)雜度高 （但質(zhì)量很好）多層劃分策略METIS Karypis95, Chaco Hendrickson and Scotch Pellegrini96 處理1M節(jié)點(diǎn)的圖并行多次圖劃分策略ParMetis Karypis98 and Pt-Scotch Chevalier08. 處理千萬節(jié)點(diǎn)的圖研究現(xiàn)狀與挑戰(zhàn)-圖的分割沒有上億規(guī)模的圖分割策略沒有通用有效的分割策略，一種分割策略只對(duì)部分算法有效分割圖的復(fù)雜度超過一些任務(wù)本身的復(fù)雜度用戶的領(lǐng)域知識(shí) 在圖分割策略上比較關(guān)鍵部分圖處理系統(tǒng)只是提供接口，讓用戶去設(shè)置圖分割策略另一部分圖處理系統(tǒng)，默認(rèn)選擇使用隨機(jī)分配策略難點(diǎn)和分歧1. 圖的劃

25、分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), 5 0, TTA, (0010,0000)1, CTT, (1000,0100), 22, GCT, (0001,0100), 32, TAG, (0001,1000), 21.局部性差： 每個(gè)頂點(diǎn)隨機(jī)的和若干其他頂點(diǎn)相連2. 圖最優(yōu)劃分難度大： 圖的最優(yōu)劃分是NP難問題3. 遠(yuǎn)程訪問通訊代價(jià)高：圖不同劃分間隨機(jī)訪問依賴于網(wǎng)絡(luò)

26、通訊，而大規(guī)模的異地訪存延遲實(shí)際是通訊延遲，訪存帶寬是通訊帶寬問題和分歧2. 計(jì)算競爭 領(lǐng)域翻譯語言 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), 5 0, TTA, (0010,0000)1, CTT, (1000,0100), 22, GCT, (0001,0100), 32, TAG, (0001,1000), 22. 非本地讀寫互斥： 遠(yuǎn)程讀寫要互斥，防止讀臟數(shù)

27、據(jù)3. 訪存一致性：本地?cái)?shù)據(jù)和遠(yuǎn)程數(shù)據(jù)一致性1. 隨機(jī)訪問：頂點(diǎn)訪問是完全隨機(jī)的問題和分歧3. 并行效率 通用VS特殊優(yōu)化策略消除/減弱計(jì)算依賴支持亂序執(zhí)行并行度最大化可擴(kuò)展性This is hard如何判斷一個(gè)大規(guī)模圖上的操作是可以并行處理的如何設(shè)計(jì)一個(gè)適合并行處理大規(guī)模圖的計(jì)算模型如何開發(fā)科處理大規(guī)模圖上的常用算法的通用系統(tǒng)大圖并行的解決方案高可擴(kuò)展并行圖處理系統(tǒng)研究內(nèi)容本課題針對(duì)高可擴(kuò)展并行圖處理系統(tǒng)在海量復(fù)雜生物數(shù)據(jù)的分析組裝的應(yīng)用，力圖從以下3個(gè)方面展開研究：可擴(kuò)展的圖算法數(shù)學(xué)抽象：使用基于群論的代數(shù)系統(tǒng)來抽象圖算法，使得圖算法上的邊和點(diǎn)對(duì)應(yīng)于計(jì)算機(jī)中的計(jì)算操作和訪存地址，并將該讀寫

28、操作規(guī)約為原子操作，使得多個(gè)這樣的互斥的原子操作可以同時(shí)并發(fā)執(zhí)行?？蓴U(kuò)展的并行計(jì)算模型: 基于子集同步全局異步的并行計(jì)算模型。可擴(kuò)展的并行圖處理框架：基于子集同步計(jì)算模型，開發(fā)可自動(dòng)挖掘潛在并行子集，自動(dòng)回避讀寫沖突，盡可能的提高系統(tǒng)效率的并行圖處理框架。在以上三方面進(jìn)行深入的研究后，開發(fā)性能優(yōu)異的系統(tǒng)原型系統(tǒng)以運(yùn)用于海量復(fù)雜生物數(shù)據(jù)的組裝分析。研究目標(biāo)本課題將圍繞高可擴(kuò)展圖處理系統(tǒng)的研究和開發(fā)，以海量復(fù)雜生物數(shù)據(jù)上的組裝分析為應(yīng)用，期望達(dá)到如下目標(biāo)： 使用代數(shù)系統(tǒng)的半群來抽象在大規(guī)模圖結(jié)構(gòu)上的現(xiàn)實(shí)問題。 提出計(jì)算模型來處理一部分緊耦合難并行的大規(guī)模圖算法。開發(fā)新的大規(guī)模圖處理框架，其可處理的

29、最大數(shù)據(jù)量可到100T, 圖頂點(diǎn)規(guī)?？蛇_(dá)到200G，系統(tǒng)可運(yùn)行于萬顆核心?；谠搱D處理框架開發(fā)的生物數(shù)據(jù)的組裝應(yīng)用軟件，可以在1小時(shí)內(nèi)處理分析完人類數(shù)據(jù)，并達(dá)到現(xiàn)有最快的商業(yè)組裝軟件40倍加速。研究目標(biāo)-可擴(kuò)展性研究目標(biāo)-圖規(guī)模研究目標(biāo)-計(jì)算時(shí)間擬解決的關(guān)鍵問題本課題擬解決的4個(gè)關(guān)鍵問題：復(fù)雜生物數(shù)據(jù)組裝問題等價(jià)于一個(gè)代數(shù)系統(tǒng)上的半群弱關(guān)聯(lián)緊耦合的圖算法可以用更加泛化的代數(shù)系統(tǒng)中的半群來描述 子集同步全局異步的計(jì)算模型 能夠最大程度的挖掘半群中的可并行子集的圖處理框架擬采取的研究方案-算法數(shù)學(xué)抽象算法數(shù)學(xué)抽象：確定可解決問題的范圍圖是弱關(guān)聯(lián)的圖可以是緊耦合求解的是全局問題計(jì)算是規(guī)則的確定計(jì)算抽

30、象抽象出原子計(jì)算確定計(jì)算關(guān)聯(lián)的數(shù)據(jù)確定計(jì)算關(guān)聯(lián)的集合生物組裝抽象為邊合并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) 擬采取的研究方案-算法數(shù)學(xué)抽象算法數(shù)學(xué)抽象：

31、確定可解決問題的范圍圖是弱關(guān)聯(lián)的圖可以是緊耦合求解的是全局問題計(jì)算是規(guī)則的確定計(jì)算抽象抽象出原子計(jì)算確定計(jì)算關(guān)聯(lián)的數(shù)據(jù)確定計(jì)算關(guān)聯(lián)的集合迭代直到收斂：我的權(quán)重就是我鄰居的權(quán)重的平均值擬采取的研究方案-計(jì)算模型計(jì)算模型 （路由協(xié)議）匹配數(shù)據(jù)和計(jì)算缺失數(shù)據(jù)調(diào)取數(shù)據(jù)一致性保證更新數(shù)據(jù)以計(jì)算為核心數(shù)據(jù)可隨機(jī)分布數(shù)據(jù)傳輸依賴網(wǎng)絡(luò)互斥協(xié)議保證同步依賴于消息互斥依賴于信令最大的人工網(wǎng)絡(luò)： 互聯(lián)網(wǎng)唯一的計(jì)算就是路由其路由是實(shí)時(shí)自動(dòng)計(jì)算的Liansheng Tan, Jintao Meng, Jie Li and Han-Chieh Chao, PH-MAC: A Periodically Hybrid MAC

32、 Protocol for Wireless sensor networks, Journal of Internet Technology, Taiwan, Nov 2007. (SCI, Impact Factor = 0.508)擬采取的研究方案-計(jì)算模型計(jì)算模型 （路由協(xié)議）匹配數(shù)據(jù)和計(jì)算缺失數(shù)據(jù)調(diào)取數(shù)據(jù)一致性保證更新數(shù)據(jù)以計(jì)算為核心數(shù)據(jù)可隨機(jī)分布數(shù)據(jù)傳輸依賴網(wǎng)絡(luò)互斥協(xié)議保證同步依賴于消息互斥依賴于信令網(wǎng)絡(luò)只負(fù)責(zé)路由（數(shù)據(jù)移動(dòng)）網(wǎng)絡(luò)不負(fù)責(zé)內(nèi)容（計(jì)算）網(wǎng)絡(luò)是自組織的網(wǎng)絡(luò)是無尺度的Jintao Meng, Jianrui Yuan, Shengzhong Feng, Yanjie Wei.

33、 An Energy Efficient Clustering Scheme for Data Aggregation in Wireless Sensor Networks, (to appear) In Journal of Computer Science and Technology, 2013. (SCI 3區(qū), Impact Factor = 0.656)Jintao Meng, Jianrui Yuan, Shengzhong Feng, Liansheng Tan, A Power Adjusting Algorithm on Mobility Control in Mobil

34、e Ad Hoc Networks. Journal of Computer Science and Technology, 2013,V28(1): 42-53 (SCI, Impact Factor = 0.656)擬采取的研究方案-系統(tǒng)開發(fā)應(yīng)用系統(tǒng)開發(fā)計(jì)算模型的實(shí)現(xiàn)系統(tǒng)框架的抽象統(tǒng)一接口的提供系統(tǒng)應(yīng)用生物數(shù)據(jù)組裝單源最短路徑（路由）雙鏈表排序1. 數(shù)據(jù)有組織的哈希隨機(jī)分布2. 每個(gè)進(jìn)程既有通訊部， 又有計(jì)算部系統(tǒng)抽象結(jié)構(gòu)Jintao Meng, Jianrui Yuan, Yanjie Wei, Jiefeng Cheng, Shengzhong Feng, Small World As

35、ynchronous Parallel Model for Genome Assembly, in 9th IFIP International Conference 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 Assembl

36、er for Massive Genome Data, in 17th annual international conference on research in computational molecular biology (RECOMB 2013), April, 2013. (Poster) 研究方案可行性分析通過引入代數(shù)系統(tǒng)中的半群和子集同步全局異步的計(jì)算模型來提高圖處理框架應(yīng)用的針對(duì)性和系統(tǒng)的可擴(kuò)展性。在開展本課題前我們做了如下可行性分析：1）分析現(xiàn)有的基于de Bruijn圖的組裝技術(shù)實(shí)現(xiàn)原理，簡要介紹基于該策略實(shí)現(xiàn)的四種拼接軟件的實(shí)現(xiàn)并對(duì)比分析其性能，這四個(gè)軟件包括Velve

37、t、SOAPdenovo、IDBA、ABySS；2）對(duì)生物數(shù)據(jù)組裝的主要流程進(jìn)行分析，找出其運(yùn)算量最大的幾個(gè)模塊，并對(duì)需要并行計(jì)算的模塊進(jìn)行分析，找出并行切實(shí)可行的實(shí)現(xiàn)方案；3）針對(duì)當(dāng)前基于de Bruijn圖的組裝方法并行化難度高的特點(diǎn)，設(shè)計(jì)優(yōu)化的de Bruijn圖結(jié)構(gòu)，并對(duì)其并行可行性進(jìn)行嚴(yán)格的分析與論證。4）由于序列拼接問題本質(zhì)是一個(gè)圖的問題，而現(xiàn)有的圖處理軟件或者庫，例如Boost Graph, Prajel, 都無法擴(kuò)展到1000個(gè)節(jié)點(diǎn)以上。所以設(shè)計(jì)新的適合圖的計(jì)算模型以最大限度的挖掘圖的計(jì)算問題中的潛在并行性。 已取得進(jìn)展-理論研究可解問題歸納若一個(gè)圖算法可分解為一系列滿足結(jié)合律

38、的操作，那么該算法就可被定義為一個(gè)半群Q(V, +)上的活動(dòng)ACT(V,)通過計(jì)算ACT(V,)即可完成對(duì)應(yīng)的圖算法。理論應(yīng)用生物數(shù)據(jù)組裝可表示為雙向多步De Bruijn圖上的邊合并操作。（二元計(jì)算）PageRank可表示為Web站點(diǎn)上的權(quán)重聚合操作（多元計(jì)算）已取得進(jìn)展-理論研究Multi-step bi-directed graphInput readsAGTACTGTCGAC+ C/T +TCGCGATAGCTA+ T/A+ A/A -GAGCTCCCTAGG+ C/G - G/G + G/C +Reference SequenceYellow vertex can be extend

39、 furtherGray vertices can not be extended further (Neighbor = RC)Dotted edges can be merged 已取得進(jìn)展-理論研究依賴圖迭代My RankFriends Rank計(jì)算PageRank已取得進(jìn)展-計(jì)算模型異步計(jì)算模型子集同步全局異步自動(dòng)尋找可并行子集基于子集合的計(jì)算可異步啟動(dòng)，亂序執(zhí)行 （滿足結(jié)合律）并發(fā)讀寫操作自動(dòng)互斥使用改進(jìn)的CDMA/CA（載波偵聽多路復(fù)用/沖突避免）技術(shù) 互斥使用Binary Backoff算法 進(jìn)行沖突后回避ComputeLockUnlockSWAP 計(jì)算模型已取得進(jìn)展-系統(tǒng)開發(fā)系

40、統(tǒng)開發(fā)當(dāng)前基于SWAP異步計(jì)算模型的圖處理框架可擴(kuò)展到1024個(gè)核心SWAP圖處理框架在處理海量生物數(shù)據(jù)組裝應(yīng)用時(shí)在1024核心內(nèi)科達(dá)到近線性加速系統(tǒng)應(yīng)用并行生物數(shù)據(jù)組裝， 可在1小時(shí)左右處理1T人類生物數(shù)據(jù)，處理速度是現(xiàn)有的最快的組裝軟件40倍。實(shí)驗(yàn)計(jì)劃及時(shí)間安排2012.1-2012.6閱讀文獻(xiàn)歸納已有圖處理系統(tǒng)2012.7-2012.12用半群來抽象生物大數(shù)據(jù)應(yīng)用2013.1-2013.6適合半群計(jì)算的異步計(jì)算模型2013.6-2013.12開發(fā)圖處理框架測試其擴(kuò)展性2014.1-2014.62014.6-2014.12圖處理框架生物信息分析應(yīng)用圖處理通用框架論文撰寫發(fā)表 參考文獻(xiàn)1 J

41、intao 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 and Technology, 2013. (SCI 3區(qū), Impact Factor = 0.656) 2 Jintao Meng, Bingqiang Wang, Yanjie Wei, Jiefeng Cheng, Shengzhong Feng, Pavan Balaji. SWAP-Assembler: A Scalabl