单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Supercomputing Center of Chinese Academy of Sciences,Title,Unit Name,Date,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,应用案例分析,-,生物信息学,周纯葆,中国科学院计算机网络信息中心 超级计算中心,应用案例分析-生物信息学周纯葆,2024/11/16,2,目录,生物信息学计算特点,并行计算主要方法,常用并行策略,应用案例分析,2023/10/62目录生物信息学计算特点,2024/11/16,3,生物信息学计算特点,数据计算无相关性,比对,数据挖掘,.,2023/10/63生物信息学计算特点数据计算无相关性,2024/11/16,4,并行计算主要方法,域分解,（,Domain decomposition,）,划分的对象是数据,。可以是算法的输入数据、中间处理数据和输出数据,不同数据项同时完成相同操作,可扩展性随数据规模而增长,2023/10/64并行计算主要方法域分解（Domain d,2024/11/16,5,并行计算主要方法,功能分解,（,Functional Decomposition,）,划分的对象是计算,。将计算划分为不同的任务，其划分对象出发点不同于域分解,不同计算或任务同时完成的并行,若任务数固定，并行性不可扩展,2023/10/65并行计算主要方法功能分解（Functio,2024/11/16,6,常用并行策略,对等模式：,2023/10/66常用并行策略对等模式：,2024/11/16,7,常用并行策略,主从模式：,2023/10/67常用并行策略主从模式：,2024/11/16,8,常用并行策略,两种并行模式比较,模式,执行代码,主进程,特性,对等模式,一套,可承担基本控制任务,承担计算任务,可扩展性好，适合大规模并行,主从模式,两套,整个并行程序控制,数据、计算任务分配,可承担或不承担计算任务,便于处理动态负载平衡的问题,2023/10/68常用并行策略两种并行模式比较模式执行代码,2024/11/16,9,常用并行策略,静,态,负,载,对,等,模,式,动,态,负,载,主,从,模,式,2023/10/69常用并行策略静对动主,2024/11/16,10,应用案例分析,-,域分解,序列长度相同,序列长度不同,2023/10/610应用案例分析-域分解序列长度相同序列长,2024/11/16,11,应用案例分析,-,域分解,算法介绍,q,1,q,2,q,3,q,m,d,1,d,2,d,3,d,n,Database,数据文件,Query,序列文件,比对,2023/10/611应用案例分析-域分解算法介绍q1q2q,2024/11/16,12,应用案例分析,-,域分解,程序介绍,待,测,数,据,无,相,关,性,粗,粒,度,数,据,分,割,数据采集,Query,Database,比对结果收集,还有,query,吗？,结束,blat,，,blast,等,是,否,2023/10/612应用案例分析-域分解程序介绍待粗数据采,2024/11/16,13,应用案例分析,-,域分解,并行思想,所有数据之间不存在相关性，通过数据分割实现并行具有可行性,假设有nd条数据,d,0,d,1,d,nd-1,，,如果仅使用一个进程，其计算负载将是,S=,d,0,+,d,1,+,d,nd-1,，若有,np,个进程参与计算，则每个进程的平均负载约为,S/np,，运行时间将随着进程数量的增加而缩短,根据序列长度不同，为保证计算负载均衡，分别使用对等和主从模式进行并行优化,2023/10/613应用案例分析-域分解并行思想,2024/11/16,14,应用案例分析,-,域分解,序列长度相当，采用,对等模式,特点,将nd条数据一次性地平均分配给np个进程进行运算,次序分割,交叉分割,.,计算过程中各进程地位平等，最后数据由某个进程（进程,0,）统一收集,并行程序维护一套代码,优势,各个进程完成自身任务后，一个进程一次汇总结果，消息传递次数较少,劣势,各进程分管数据一次划分，可能会造成计算负载不平衡，引起的资源浪费,2023/10/614应用案例分析-域分解序列长度相当，采用,2024/11/16,15,应用案例分析,-,域分解,对等模式主要代码,residue=nd%np;/*,计算余数,*/,if(residue=0),/*,如果能平均分配,*/,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;,2023/10/615应用案例分析-域分解对等模式主要代码,2024/11/16,16,应用案例分析,-,域分解,序列长度不等，采用,主从模式,特点,有一个主进程进行任务调度，其他进程作为从进程完成计算任务,主进程不进行计算，从进程之间地位平等，且从进程之间没有相互通信,并行程序维护两套代码,优势,动态分配任务，计算负载相对平衡,劣势,主进程要实时为从进程分配计算任务，进程间消息传递开销较大，致并行效率下降,2023/10/616应用案例分析-域分解序列长度不等，采用,2024/11/16,17,应用案例分析,-,域分解,主从模式主进程主要代码,for(i=np-1;i=nd)break;/*,任务已全部分配，退出,*/,2023/10/618应用案例分析-域分解主从模式从进程主要,2024/11/16,19,应用案例分析,-,域分解,若分割后单位数据的计算量不同甚至差别很大，则会严重影响负载平衡性，造成并行效率低下,按照（预估）所需计算时间从大到小排列,query,序列，,会,尽量达到,负载平衡,2023/10/619应用案例分析-域分解若分割后单位数据的,2024/11/16,20,应用案例分析,-,功能分解,2023/10/620应用案例分析-功能分解,2024/11/16,21,应用案例分析,-,功能分解,算法介绍,后验概率,似然,先验概率,数据非条件概率,D,数据,T,树拓扑结构,2023/10/621应用案例分析-功能分解算法介绍后验概率,2024/11/16,22,应用案例分析,-,功能分解,程序介绍,Generate initial state S,0,S,(t),=S,(0),=,t=0,Propose new state S,Evaluate S,Compute R and U,U max generation,No,Yes,End,2023/10/622应用案例分析-功能分解程序介绍 Gen,2024/11/16,23,应用案例分析,-,功能分解,程序介绍,Generate S,1,(0),t=0,Generate S,2,(0),t=0,Generate S,3,(0),t=0,Generate S,4,(0),t=0,Propose&,Update S,1,(t),Propose&,Update S,2,(t),Propose&,Update S,3,(t),Propose&,Update S,4,(t),choose two chains to swap,Compute R and U,UR,Swap the two selected chains,t=t+1,t=t+1,t=t+1,t=t+1,Yes,No,No,2023/10/623应用案例分析-功能分解程序介绍Gene,2024/11/16,24,应用案例分析,-,功能分解,并行思想,每条,Markov,链的计算量相同，并且链之间不存在相关性，只在信息交换时才产生联系，通过计算任务分割实现并行具有可行性,假设有nd条,Markov,链,m,0,m,1,m,nd-1,，,如果仅使用一个进程，其计算负载将是,S=,m,0,+,m,1,+,m,nd-1,，若有,np,个进程参与计算，则每个进程的平均负载约为,S/np,，运行时间将随着进程数量的增加而缩短，进程数量受计算任务数量的限制,由于计算任务的限制，为保证计算负载均衡，使用对等模式进行并行优化,2023/10/624应用案例分析-功能分解并行思想,2024/11/16,25,应用案例分析,-,功能分解,每条,Markov,链计算量相同，每个处理器负责相同数量,Markov,链计算,2023/10/625应用案例分析-功能分解每条Markov,2024/11/16,26,应用案例分析,-,功能分解,主要代码,for(i=0;iiteration;i+)/iteration,为迭代的总次数,doMCMC();/,每个进程各自执行,MCMC,计算,/*,随机产生需要交换的,Markov,链标号,*/,i=Rnk();,j=Rnk();,/*,Markov,链,i,和,j,交换信息，信息存储在,message,中,*,/,MPI_Recv(,&,message,1,MPI_INT,source,0,MPI_COMM_WORLD,MPI_Send(,&message,1,MPI_INT,dest,1,MPI_COMM_WORLD);,汇总结果文件,;,2023/10/626应用案例分析-功能分解主要代码,2024/11/16,27,应用案例分析,-,功能分解,若,每个进程分配的,Markov,链数量不同，进程之间的计算量相差很大,，则会严重影响负载平衡性，造成并行效率,低下,平均分配,Markov,链,会,尽量达到,负载平衡,2023/10/627应用案例分析-功能分解若每个进程分配的,2024/11/16,28,应用案例分析,-,域分解与功能分解,算法介绍,2023/10/628应用案例分析-域分解与功能分解算法介绍,2024/11/16,29,应用案例分析,-,域分解与功能分解,程序介绍,待,计,算,数,据,无,相,关,性,粗,粒,度,数,据,分,割,数据采集,Nodes,DNA,似然计算,还有,DNA,吗？,是,否,生成树,2023/10/629应用案例分析-域分解与功能分解程序介绍,2024/11/16,30,应用案例分析,-,域分解与功能分解,并行思想,DNA,序列各个位点,之间不存在相关性，通过数据分割实现并行具有可行性,假设有,DNA,序列长度为,n,d,n,0,n,1,n,nd-1,，,如果仅使用一个进程，其计算负载将是,S=,n,0,+,n,1,+,n,nd-1,，若有,np,个进程参与计算，,则每个,进程,的平均负载约为,S/np,，,运行时间将随着,进程,数量的增加而缩短,由于,DNA,序列平均分配，不同进程之间仅相差最多一个位点，因此使用对等模式即可,2023/10/630应用案例分析-域分解与功能分解并行思想,2024/11/16,31,应用案例分析,-,域分解与功能分解,对等模式,2023/10/631应用案例分析-域分解与功能分解对等模式,2024/11/16,32,应用案例分析,-,域分解与功能分解,域分解对等模式主要代码,residue=nd%np;/*,计算余数,*/,if(residue=0),/*,如果能平均分配,*/,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;,2023/10/632应用案例分析-域分解与功能分解域分解对,2024/11/16,33,应用案例分析,-,域分解与功能分解,并行思想：,多条,Markov,链由多个进程同时进行计算,单条,Markov,链内