應(yīng)用案例分析-生物信息學(xué)課件

1、應(yīng)用案例分析-生物信息學(xué)周純葆中國科學(xué)院計算機網(wǎng)絡(luò)信息中心 超級計算中心應(yīng)用案例分析-生物信息學(xué)周純葆2022/10/122目錄生物信息學(xué)計算特點并行計算主要方法常用并行策略應(yīng)用案例分析2022/10/102目錄生物信息學(xué)計算特點2022/10/123生物信息學(xué)計算特點數(shù)據(jù)計算無相關(guān)性比對數(shù)據(jù)挖掘.2022/10/103生物信息學(xué)計算特點數(shù)據(jù)計算無相關(guān)性2022/10/124并行計算主要方法域分解（Domain decomposition）劃分的對象是數(shù)據(jù)?？梢允撬惴ǖ妮斎霐?shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)不同數(shù)據(jù)項同時完成相同操作可擴展性隨數(shù)據(jù)規(guī)模而增長2022/10/104并行計算主要方法域分解

2、（Domain 2022/10/125并行計算主要方法功能分解（Functional Decomposition）劃分的對象是計算。將計算劃分為不同的任務(wù)，其劃分對象出發(fā)點不同于域分解不同計算或任務(wù)同時完成的并行若任務(wù)數(shù)固定，并行性不可擴展2022/10/105并行計算主要方法功能分解（Functi2022/10/126常用并行策略對等模式：2022/10/106常用并行策略對等模式：2022/10/127常用并行策略主從模式：2022/10/107常用并行策略主從模式：2022/10/128常用并行策略兩種并行模式比較模式執(zhí)行代碼主進程特性對等模式一套可承擔(dān)基本控制任務(wù)承擔(dān)計算任務(wù)可擴展性好

3、，適合大規(guī)模并行主從模式兩套整個并行程序控制數(shù)據(jù)、計算任務(wù)分配可承擔(dān)或不承擔(dān)計算任務(wù)便于處理動態(tài)負(fù)載平衡的問題2022/10/108常用并行策略兩種并行模式比較模式執(zhí)行代2022/10/129常用并行策略靜態(tài)負(fù)載對等模式動態(tài)負(fù)載主從模式2022/10/109常用并行策略靜對動主2022/10/1210應(yīng)用案例分析-域分解序列長度相同序列長度不同2022/10/1010應(yīng)用案例分析-域分解序列長度相同序列2022/10/1211應(yīng)用案例分析-域分解算法介紹q1q2q3qmd1d2d3dnDatabase數(shù)據(jù)文件Query序列文件比對2022/10/1011應(yīng)用案例分析-域分解算法介紹q1q220

4、22/10/1212應(yīng)用案例分析-域分解程序介紹待測數(shù)據(jù)無相關(guān)性粗粒度數(shù)據(jù)分割數(shù)據(jù)采集QueryDatabase比對結(jié)果收集還有query嗎？結(jié)束blat，blast 等是否2022/10/1012應(yīng)用案例分析-域分解程序介紹待粗?jǐn)?shù)據(jù)2022/10/1213應(yīng)用案例分析-域分解并行思想所有數(shù)據(jù)之間不存在相關(guān)性，通過數(shù)據(jù)分割實現(xiàn)并行具有可行性假設(shè)有nd條數(shù)據(jù)d0,d1,dnd-1，如果僅使用一個進程，其計算負(fù)載將是S=d0+d1+dnd-1，若有np個進程參與計算，則每個進程的平均負(fù)載約為S/np，運行時間將隨著進程數(shù)量的增加而縮短根據(jù)序列長度不同，為保證計算負(fù)載均衡，分別使用對等和主從模式進行

5、并行優(yōu)化2022/10/1013應(yīng)用案例分析-域分解并行思想2022/10/1214應(yīng)用案例分析-域分解序列長度相當(dāng)，采用對等模式特點將nd條數(shù)據(jù)一次性地平均分配給np個進程進行運算次序分割交叉分割.計算過程中各進程地位平等，最后數(shù)據(jù)由某個進程（進程0）統(tǒng)一收集 并行程序維護一套代碼優(yōu)勢各個進程完成自身任務(wù)后，一個進程一次匯總結(jié)果，消息傳遞次數(shù)較少劣勢各進程分管數(shù)據(jù)一次劃分，可能會造成計算負(fù)載不平衡，引起的資源浪費2022/10/1014應(yīng)用案例分析-域分解序列長度相當(dāng)，采2022/10/1215應(yīng)用案例分析-域分解對等模式主要代碼residue = nd % np ; /* 計算余數(shù) */i

6、f ( residue = 0 ) /* 如果能平均分配 */ num = nd / np ; start = num * myid ;else /* 如果不能平均分配，進程號靠前的每個進程多處理一條數(shù)據(jù) */ if ( myid residue ) num = nd / np + 1 ; start = num * myid ; else num = nd / np ; start = num * myid + residue ; 2022/10/1015應(yīng)用案例分析-域分解對等模式主要代碼2022/10/1216應(yīng)用案例分析-域分解序列長度不等，采用主從模式特點有一個主進程進行任務(wù)調(diào)度，其

7、他進程作為從進程完成計算任務(wù)主進程不進行計算，從進程之間地位平等，且從進程之間沒有相互通信并行程序維護兩套代碼優(yōu)勢動態(tài)分配任務(wù)，計算負(fù)載相對平衡劣勢主進程要實時為從進程分配計算任務(wù)，進程間消息傳遞開銷較大，致并行效率下降2022/10/1016應(yīng)用案例分析-域分解序列長度不等，采2022/10/1217應(yīng)用案例分析-域分解主從模式主進程主要代碼for( i = np - 1; i = nd ) break; /* 任務(wù)已全部分配，退出 */2022/10/1018應(yīng)用案例分析-域分解主從模式從進程主2022/10/1219應(yīng)用案例分析-域分解若分割后單位數(shù)據(jù)的計算量不同甚至差別很大，則會嚴(yán)重影

8、響負(fù)載平衡性，造成并行效率低下按照（預(yù)估）所需計算時間從大到小排列query序列，會盡量達(dá)到負(fù)載平衡2022/10/1019應(yīng)用案例分析-域分解若分割后單位數(shù)據(jù)2022/10/1220應(yīng)用案例分析-功能分解2022/10/1020應(yīng)用案例分析-功能分解2022/10/1221應(yīng)用案例分析-功能分解算法介紹后驗概率似然先驗概率數(shù)據(jù)非條件概率 D 數(shù)據(jù) T 樹拓?fù)浣Y(jié)構(gòu)2022/10/1021應(yīng)用案例分析-功能分解算法介紹后驗概2022/10/1222應(yīng)用案例分析-功能分解程序介紹 Generate initial state S0 S(t)= S(0)=, t=0Propose new state

9、 S Evaluate S Compute R and UU max generationNoYesEnd2022/10/1022應(yīng)用案例分析-功能分解程序介紹 Ge2022/10/1223應(yīng)用案例分析-功能分解程序介紹Generate S1(0)t=0Generate S2(0)t=0Generate S3(0)t=0Generate S4(0)t=0Propose &Update S1(t) Propose &Update S2(t) Propose &Update S3(t) Propose &Update S4(t) choose two chains to swapCompute R

10、 and UURSwap the two selected chainst=t+1t=t+1t=t+1t=t+1YesNoNo2022/10/1023應(yīng)用案例分析-功能分解程序介紹Gen2022/10/1224應(yīng)用案例分析-功能分解并行思想每條Markov鏈的計算量相同，并且鏈之間不存在相關(guān)性，只在信息交換時才產(chǎn)生聯(lián)系，通過計算任務(wù)分割實現(xiàn)并行具有可行性假設(shè)有nd條Markov鏈m0,m1,mnd-1，如果僅使用一個進程，其計算負(fù)載將是S=m0+m1+mnd-1，若有np個進程參與計算，則每個進程的平均負(fù)載約為S/np，運行時間將隨著進程數(shù)量的增加而縮短，進程數(shù)量受計算任務(wù)數(shù)量的限制由于計算任

11、務(wù)的限制，為保證計算負(fù)載均衡，使用對等模式進行并行優(yōu)化2022/10/1024應(yīng)用案例分析-功能分解并行思想2022/10/1225應(yīng)用案例分析-功能分解每條Markov鏈計算量相同，每個處理器負(fù)責(zé)相同數(shù)量Markov鏈計算2022/10/1025應(yīng)用案例分析-功能分解每條Marko2022/10/1226應(yīng)用案例分析-功能分解主要代碼for(i=0; iiteration; i+) /iteration為迭代的總次數(shù) doMCMC(); /每個進程各自執(zhí)行MCMC計算 /* 隨機產(chǎn)生需要交換的Markov鏈標(biāo)號 */ i = Rnk(); j = Rnk(); /* Markov鏈i和j交換

12、信息，信息存儲在message中 */ MPI_Recv( &message, 1, MPI_INT, source, 0, MPI_COMM_WORLD, &status ); MPI_Send( &message, 1, MPI_INT, dest, 1, MPI_COMM_WORLD );匯總結(jié)果文件;2022/10/1026應(yīng)用案例分析-功能分解主要代碼2022/10/1227應(yīng)用案例分析-功能分解若每個進程分配的Markov鏈數(shù)量不同，進程之間的計算量相差很大，則會嚴(yán)重影響負(fù)載平衡性，造成并行效率低下平均分配Markov鏈會盡量達(dá)到負(fù)載平衡2022/10/1027應(yīng)用案例分析-功能分

13、解若每個進程分配2022/10/1228應(yīng)用案例分析-域分解與功能分解算法介紹2022/10/1028應(yīng)用案例分析-域分解與功能分解算法介2022/10/1229應(yīng)用案例分析-域分解與功能分解程序介紹待計算數(shù)據(jù)無相關(guān)性粗粒度數(shù)據(jù)分割數(shù)據(jù)采集NodesDNA似然計算還有DNA嗎？是否生成樹2022/10/1029應(yīng)用案例分析-域分解與功能分解程序介2022/10/1230應(yīng)用案例分析-域分解與功能分解并行思想DNA序列各個位點之間不存在相關(guān)性，通過數(shù)據(jù)分割實現(xiàn)并行具有可行性假設(shè)有DNA序列長度為ndn0,n1,nnd-1，如果僅使用一個進程，其計算負(fù)載將是S=n0+n1+nnd-1，若有np個進

14、程參與計算，則每個進程的平均負(fù)載約為S/np，運行時間將隨著進程數(shù)量的增加而縮短由于DNA序列平均分配，不同進程之間僅相差最多一個位點，因此使用對等模式即可2022/10/1030應(yīng)用案例分析-域分解與功能分解并行思2022/10/1231應(yīng)用案例分析-域分解與功能分解對等模式2022/10/1031應(yīng)用案例分析-域分解與功能分解對等模2022/10/1232應(yīng)用案例分析-域分解與功能分解域分解對等模式主要代碼residue = nd % np ; /* 計算余數(shù) */if ( residue = 0 ) /* 如果能平均分配 */ num = nd / np ; start = num *

15、myid ;else /* 如果不能平均分配，進程號靠前的每個進程多處理一條數(shù)據(jù) */ if ( myid residue ) num = nd / np + 1 ; start = num * myid ; else num = nd / np ; start = num * myid + residue ; 2022/10/1032應(yīng)用案例分析-域分解與功能分解域分解2022/10/1233應(yīng)用案例分析-域分解與功能分解并行思想：多條Markov鏈由多個進程同時進行計算單條Markov鏈內(nèi)部似然由多個進程同時進行計算避免了僅利用任務(wù)分解造成的擴展性不好的問題任務(wù)分解受到Markov鏈數(shù)量的

16、限制，域分解與數(shù)據(jù)相關(guān)由于任務(wù)分解和域分解相結(jié)合，進程組織較復(fù)雜2022/10/1033應(yīng)用案例分析-域分解與功能分解并行思2022/10/1234應(yīng)用案例分析-域分解與功能分解進程虛擬拓?fù)浣Y(jié)構(gòu)2022/10/1034應(yīng)用案例分析-域分解與功能分解進程虛2022/10/1235應(yīng)用案例分析-域分解與功能分解任務(wù)分解主要代碼for(i=0; iiteration; i+) /*iteration為迭代的總次數(shù)*/ doMCMC(); /*每個進程各自執(zhí)行MCMC計算，域分解部分*/ /* 隨機產(chǎn)生需要交換的Markov鏈標(biāo)號 */ i = Rnk(); j = Rnk(); if(myrank=

17、i | myrank=j) /* Markov鏈i和j交換信息，信息存儲在message中 */ MPI_Recv( &message, 1, MPI_INT, source, 0, MPI_COMM_WORLD, &status ); MPI_Send( &message, 1, MPI_INT, dest, 1, MPI_COMM_WORLD ); 匯總結(jié)果文件;2022/10/1035應(yīng)用案例分析-域分解與功能分解任務(wù)分2022/10/1236應(yīng)用案例分析-域分解與功能分解域分解主要代碼residue = nd % np ; /* 計算余數(shù) */if ( residue = 0 ) /* 如果能平均分配 */ num = nd / np ; start = num * myid ;else /* 如果不能平均分配，進程號靠前的每個進程多處理一條數(shù)據(jù) */ if ( myid residue ) num = nd