基于英特尔多核及众核平台的全局序列比对算法研究

发布时间：2020-10-25 05:48

　　 随着测序技术的发展,基因序列的数量得到了迅猛的增长,为了有效地利用这些序列数据,我们往往需要将它们与已知的基因组进行比对,从而获取序列间的相似性以及同源性等信息,为后续的进一步分析打下基础。传统的序列比对算法由于自身算法复杂度的限制,在处理海量序列的比对时,往往难以达到期望的效果。近年来随着硬件和软件技术的发展,尤其是众核架构的出现,高性能计算在自然语言处理、人工智能、计算生物学等领域发挥着越来越重要的作用。将高性能计算应用于序列比对,可以显著地改善比对的速度,提高序列分析的效率。本文主要基于英特尔的多核和众核平台,针对全局序列比对问题进行研究,利用多核及众核平台的高速计算能力对全局序列比对算法进行加速优化,进一步提升算法的性能。目前常用的全局序列比对算法是Needleman-Wunsch算法,在此算法的基础上衍生出两种基于位并行优化的比对算法:Myers和BitPAl,它们在功能性上做了一些削减,以获取更高的性能。我们主要从两个维度对上述算法进行了优化:线程并行和SIMD并行,线程并行主要利用多线程技术,将序列数据划分为多个数据块,每个线程并行地处理一块数据。在线程内部,我们利用SSE、AVX2、KNC和AVX512等SIMD指令进行更加细粒度的并行优化。为了提升系统的可扩展性,我们设计并实现了一个模块化的并行框架,我们将系统中的功能进行拆分细化,划分出多个独立的功能性模块,模块间相互协作,共同完成指定的任务。比对算法的逻辑被抽象为一个计算模块,其他的模块只需向该模块中传入数据,然后获取对应的计算结果,无需关心计算模块的具体实现,这样如果需要往并行框架中加入新的比对算法,我们只需修改计算模块的实现,便可以复用框架的其他功能,保证了系统具有良好的扩展性。同时为了解决SIMD指令集不统一的问题,我们设计了虚拟SIMD指令,并实现了对应的指令解释器,利用虚拟SIMD指令,我们只需维护一份代码,通过虚拟指令解释器,我们可以将其翻译为针对不同指令集的代码,可以极大地提高开发效率。我们在不同的平台上对我们的并行算法做了测试,实验证明我们的并行算法取得了很好的加速效果,同时我们和其他的并行实现做了对比,我们的算法取得了更加优异的性能。
【学位单位】：山东大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：Q811.4;TP38
【部分图文】：

ＡＶＸ２、ＫＮＣ和ＡＶＸ５１２指令集优化的算法。??３．１框架概述??图３－１展示了并行框架的整体架构图，我们的并行框架大概分为以下几个部??分：??？输入模块，用来读取序列数据，解析数据格式，并转换成预处理模块需要??的中间数据结构。??？预处理模块，该模块会对序列数据进行进一步的处理，生成更加适合并行??处理的数据结构，以便在计算模块中可以充分发挥硬件的计算能力。??？数据传输模块，该模块主要针对ＫＮＣ平台，用来保障ＣＰＵ和ＫＮＣ之间??的高效数据传输。??？任务分发模块，处理设备以及线程间的任务分发工作，该模块需要尽量保??证设备以及线程间的负载均衡，以充分利用计算资源。??？计算模块，执行核心比对算法，返回计算结果。??？输出模块

们的工作线程就会一直处于工作状态，可以充分发挥硬件的计算能力。这里我??们使用Ｐｔｈｒｅａｄｓ?（ＰＯＳＩＸ?Ｔｈｒｅａｄｓ）来创建输入和输出线程，利用条件变量和互??斥锁来实现同步控制器。图３－３展示了该实现的示意图。??；输入缓冲区ｉ?丨输出缓冲区ｉ??＿一?＿?丨＿＿＾—围??＇?ｉ缓冲区２１?！?ｉ缓冲区４?！?＾??＼?ｉ?—??＇?＞?，?Ａ?ｖ—＇?’?１丨?／??Ｎ?、?＇?、?Ｉ?？?、?ｊ?ｆ??Ｖ?＿＿?／??＼?＾?Ｉ?岑、?Ｚ??仏４“．??■ＢＢＰ＊??图３－３流水线实现示意图??３．３任务分发模块??任务分发模块主要用来在设备以及线程间进行比对任务的分配，在单独的??ＣＰＵ或者ＫＮＬ平台上，我们可以借助于ＯｐｅｎＭＰ?（Ｏｐｅｎ?Ｍｕｌｔｉ－Ｐｒｏｃｅｓｓｉｎｇ）提??供的调度功能来实现线程间的负载均衡。但是在由ＣＰＵ和ＫＮＣ构成的异构平??台中，ＣＰＵ和ＫＮＣ会同时参与到计算，因此我们需要保证各设备间的负载均??衡，以充分发挥各个设备的计算性能。关于ＯｐｅｎＭＰ的相关内容我们会在下一??章中进行详细的叙述，这里主要介绍一下我们针对多设备设计的任务分发框架。??因为每个设备的计算能力不同，所以我们不能简单的为每个设备分配相同的任??务。我们维护了一个任务划分的比例表

根据ｉ？对数据块进行划分，将数据分配给相应的设备，当处理完成之后，我们??会收集各设备的处理时间，然后更新在处理下一个数据块时使用更新后的??Ｈ进行数据划分。图３－４展示了任务分发模块的运行流程。??动态调节??Ｖ?＞?、??；?一一｜??：?Ｉ?丨?；??图３－４任务分发模块示意图??下面我们来看下动态调节尺的过程。我们首先定义几个符号，??？州，Ｍｂ表示在处理第ｊ个数据块时，第ｉ个设备分配到的任务量和第１??个设备的比例，其中有？三１。??？?Ｔ，?７＾表示在处理第ｊ个数据块时，第ｉ个设备耗费的计算时间：。??假设我们有ｎ个设备，在处理第ｊ个数据块时，我们会首次计算出丨Ｖ的??值，然后根据公式３．１来计算出７？的值。??Ｒｉ?＝?＾７）—，７７?（３．１）??２＾＝１?”？??在理想情况下
【相似文献】

相关期刊论文 前10条

1 王进科;冯萍;康继昌;陈亚东;;基于布尔逻辑的双序列比对协处理器的设计与实现[J];西北工业大学学报;2011年01期

2 张永;王瑞;;生物信息学中的序列比对算法[J];电脑知识与技术;2008年01期

3 张涛涛;郭茂祖;邹权;;参数序列比对算法研究(英文)[J];生物信息学;2008年02期

4 唐玉荣;生物信息学中一个优化的全局双序列比对算法[J];计算机应用;2004年S1期

5 张敏;生物序列比对算法研究现状与展望[J];大连大学学报;2004年04期

6 单路超;王建章;许德森;李东垣;赵鹏;王国相;褚腾飞;;基于局部序列比对的漏洞挖掘技术研究[J];微型机与应用;2017年03期

7 杨洁;刘海;;生物序列比对算法的研究现状[J];中国科技信息;2011年09期

8 叶笑春;林伟;范东睿;张浩;;蛋白质序列比对算法在众核结构上的并行优化[J];软件学报;2010年12期

9 骆嘉伟;陈斐;彭东海;;基于混合行为的蚁群双序列比对方法[J];计算机工程与应用;2009年11期

10 吴德敏;陈俊;;双序列比对的算法研究[J];计算机工程与应用;2008年36期

相关博士学位论文 前10条

1 唐玉荣;生物信息学中的序列比对算法研究[D];中国农业大学;2004年

2 李玉岗;生物大分子序列比对和蛋白质结构分类算法[D];中国科学院研究生院（计算技术研究所）;2004年

3 陈科;最优化方法在生物序列比对中的应用与研究[D];电子科技大学;2010年

4 向旭宇;基因序列与结构的信息分析及应用算法研究[D];湖南大学;2010年

5 马爽;多功能雷达电子情报信号处理关键技术研究[D];国防科学技术大学;2013年

6 刘广臣;若干统计计算模型研究及其在生物医学信息处理中的应用[D];山东大学;2016年

7 李想;多重序列比对上的RNA相互作用问题[D];南开大学;2013年

8 曹永忠;新城疫病毒生物信息分析系统的构建及其全基因组的比较研究[D];扬州大学;2009年

9 Sagheer Atta;[D];西南大学;2011年

10 杨凡;生物序列分析中若干问题的研究[D];电子科技大学;2011年

相关硕士学位论文 前10条

1 黄丹青;基于混合化学反应优化算法的序列比对研究[D];湖南大学;2014年

2 张彩华;模糊隐马氏模型及其在生物序列比对中的应用[D];山东大学;2018年

3 张吉凯;基于英特尔多核及众核平台的全局序列比对算法研究[D];山东大学;2018年

4 郭睿东;基于变长种子的找全测序序列比对算法研究及优化[D];中国科学技术大学;2018年

5 姜鲜桃;双序列比对Needleman-Wunsch算法研究[D];内蒙古农业大学;2017年

6 何万双;双序列比对算法研究[D];国防科学技术大学;2006年

7 李川;双序列比对算法研究与并行优化[D];西安电子科技大学;2011年

8 林敏;新一代则序技术中的短序列比对和组装算法[D];福建农林大学;2011年

9 纪文娟;生物同源序列比对算法研究及其实现[D];江南大学;2009年

10 冯百龙;双序列比对Needleman-Wunsch算法的分布式并行优化研究[D];内蒙古农业大学;2015年

本文编号：2855558