应用案例分析-生物信息学课件.ppt

1、 TitleUnit NameDateSupercomputing Center of Chinese Academy of Sciences2022-11-1121.生物信息学计算特点2.并行计算主要方法3.常用并行策略4.应用案例分析Supercomputing Center of Chinese Academy of Sciences2022-11-113数据计算无相关性 比对 数据挖掘.Supercomputing Center of Chinese Academy of Sciences2022-11-114域分解（Domain decomposition）划分的对象是数据。可以是算

2、法的输入数据、中间处理数据和输出数据 不同数据项同时完成相同操作 可扩展性随数据规模而增长Supercomputing Center of Chinese Academy of Sciences2022-11-115功能分解（Functional Decomposition）划分的对象是计算。将计算划分为不同的任务，其划分对象出发点不同于域分解 不同计算或任务同时完成的并行 若任务数固定，并行性不可扩展Supercomputing Center of Chinese Academy of Sciences2022-11-116对等模式：Supercomputing Center of Chin

3、ese Academy of Sciences2022-11-117主从模式：Supercomputing Center of Chinese Academy of Sciences2022-11-118两种并行模式比较模式执行代码主进程特性对等模式一套1.可承担基本控制任务2.承担计算任务可扩展性好，适合大规模并行主从模式两套1.整个并行程序控制2.数据、计算任务分配3.可承担或不承担计算任务便于处理动态负载平衡的问题Supercomputing Center of Chinese Academy of Sciences2022-11-119静态负载对等模式动态负载主从模式Supercomp

4、uting Center of Chinese Academy of Sciences2022-11-1110序列长度相同序列长度不同Supercomputing Center of Chinese Academy of Sciences2022-11-1111算法介绍q1q2q3qmd1d2d3dnDatabase数据文件Query序列文件比对Supercomputing Center of Chinese Academy of Sciences2022-11-1112程序介绍待测数据无相关性粗粒度数据分割数据采集QueryDatabase比对结果收集还有query吗？结束blat，blas

5、t 等是否Supercomputing Center of Chinese Academy of Sciences2022-11-1113并行思想 所有数据之间不存在相关性，通过数据分割实现并行具有可行性 假设有nd条数据d0,d1,dnd-1，如果仅使用一个进程，其计算负载将是S=d0+d1+dnd-1，若有np个进程参与计算，则每个进程的平均负载约为S/np，运行时间将随着进程数量的增加而缩短 根据序列长度不同，为保证计算负载均衡，分别使用对等和主从模式进行并行优化Supercomputing Center of Chinese Academy of Sciences2022-11-111

6、4序列长度相当，采用对等模式对等模式特点 将nd条数据一次性地平均分配给np个进程进行运算 次序分割 交叉分割.计算过程中各进程地位平等，最后数据由某个进程（进程0）统一收集 并行程序维护一套代码优势 各个进程完成自身任务后，一个进程一次汇总结果，消息传递次数较少劣势 各进程分管数据一次划分，可能会造成计算负载不平衡，引起的资源浪费Supercomputing Center of Chinese Academy of Sciences2022-11-1115对等模式主要代码residue=nd%np;/*计算余数*/if(residue=0)/*如果能平均分配*/num=nd/np;start

7、=num*myid;else /*如果不能平均分配，进程号靠前的每个进程多处理一条数据*/if(myid residue)num=nd/np+1;start=num*myid;else num=nd/np;start=num*myid+residue;Supercomputing Center of Chinese Academy of Sciences2022-11-1116序列长度不等，采用主从模式主从模式特点 有一个主进程进行任务调度，其他进程作为从进程完成计算任务 主进程不进行计算，从进程之间地位平等，且从进程之间没有相互通信 并行程序维护两套代码优势 动态分配任务，计算负载相对平衡劣

8、势 主进程要实时为从进程分配计算任务，进程间消息传递开销较大，致并行效率下降Supercomputing Center of Chinese Academy of Sciences2022-11-1117主从模式主进程主要代码for(i=np-1;i=nd)break;/*任务已全部分配，退出*/Supercomputing Center of Chinese Academy of Sciences2022-11-1119若分割后单位数据的计算量不同甚至差别很大，则会严重影响负载平衡性，造成并行效率低下按照（预估）所需计算时间从大到小排列query序列，会尽量达到负载平衡Supercomput

9、ing Center of Chinese Academy of Sciences2022-11-1120Supercomputing Center of Chinese Academy of Sciences2022-11-1121算法介绍)()()|()|(DPTPTDPDTP后验概率似然先验概率数据非条件概率 D 数据 T 树拓扑结构Supercomputing Center of Chinese Academy of Sciences2022-11-1122程序介绍 Generate initial state S0 S(t)=S(0)=,t=0Propose new state S

10、Evaluate S Compute R and UU max generationNoYesEndSupercomputing Center of Chinese Academy of Sciences2022-11-1123程序介绍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

11、 and UURSwap the two selected chainst=t+1t=t+1t=t+1t=t+1YesNoNoSupercomputing Center of Chinese Academy of Sciences2022-11-1124并行思想 每条Markov链的计算量相同，并且链之间不存在相关性，只在信息交换时才产生联系，通过计算任务分割实现并行具有可行性 假设有nd条Markov链m0,m1,mnd-1，如果仅使用一个进程，其计算负载将是S=m0+m1+mnd-1，若有np个进程参与计算，则每个进程的平均负载约为S/np，运行时间将随着进程数量的增加而缩短，进程数量受计

12、算任务数量的限制 由于计算任务的限制，为保证计算负载均衡，使用对等模式进行并行优化Supercomputing Center of Chinese Academy of Sciences2022-11-1125每条Markov链计算量相同，每个处理器负责相同数量Markov链计算Supercomputing Center of Chinese Academy of Sciences2022-11-1126主要代码for(i=0;iiteration;i+)/iteration为迭代的总次数 doMCMC();/每个进程各自执行MCMC计算 /*随机产生需要交换的Markov链标号*/i=Rnk

13、();j=Rnk();/*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);汇总结果文件;Supercomputing Center of Chinese Academy of Sciences2022-11-1127若每个进程分配的Markov链数量不同，进程之间的计算量相差很大，则会严重影响负载平衡性，造成并行效率低下平均分配Markov链会尽量达到负载平衡S

14、upercomputing Center of Chinese Academy of Sciences2022-11-1128算法介绍Supercomputing Center of Chinese Academy of Sciences2022-11-1129程序介绍待计算数据无相关性粗粒度数据分割数据采集NodesDNA似然计算还有DNA吗？是否生成树Supercomputing Center of Chinese Academy of Sciences2022-11-1130并行思想 DNA序列各个位点之间不存在相关性，通过数据分割实现并行具有可行性 假设有DNA序列长度为ndn0,n1

15、,nnd-1，如果仅使用一个进程，其计算负载将是S=n0+n1+nnd-1，若有np个进程参与计算，则每个进程的平均负载约为S/np，运行时间将随着进程数量的增加而缩短 由于DNA序列平均分配，不同进程之间仅相差最多一个位点，因此使用对等模式即可Supercomputing Center of Chinese Academy of Sciences2022-11-1131对等模式Supercomputing Center of Chinese Academy of Sciences2022-11-1132域分解对等模式主要代码residue=nd%np;/*计算余数*/if(residue=0

16、)/*如果能平均分配*/num=nd/np;start=num*myid;else /*如果不能平均分配，进程号靠前的每个进程多处理一条数据*/if(myid residue)num=nd/np+1;start=num*myid;else num=nd/np;start=num*myid+residue;Supercomputing Center of Chinese Academy of Sciences2022-11-1133并行思想：多条Markov链由多个进程同时进行计算 单条Markov链内部似然由多个进程同时进行计算 避免了仅利用任务分解造成的扩展性不好的问题 任务分解受到Mark

17、ov链数量的限制，域分解与数据相关 由于任务分解和域分解相结合，进程组织较复杂Supercomputing Center of Chinese Academy of Sciences2022-11-1134进程虚拟拓扑结构Supercomputing Center of Chinese Academy of Sciences2022-11-1135任务分解主要代码for(i=0;iiteration;i+)/*iteration为迭代的总次数*/doMCMC();/*每个进程各自执行MCMC计算，域分解部分*/*随机产生需要交换的Markov链标号*/i=Rnk();j=Rnk();if(my

18、rank=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);汇总结果文件;Supercomputing Center of Chinese Academy of Sciences2022-11-1136域分解主要代码residue=nd%np;/*计算余数*/if(residue=0)/*如果能平均分配*/num=nd/np;start=

19、num*myid;else /*如果不能平均分配，进程号靠前的每个进程多处理一条数据*/if(myid residue)num=nd/np+1;start=num*myid;else num=nd/np;start=num*myid+residue;Supercomputing Center of Chinese Academy of Sciences2022-11-1137任务分解示意图Supercomputing Center of Chinese Academy of Sciences2022-11-1138域分解示意图Supercomputing Center of Chinese Academy of Sciences2022-11-1139