基于Xeon Phi的超长序列比对算法设计与实现

发布时间：2021-01-01 18:33

　　基因是指控制生物性状的遗传信息,通常由DNA序列承载,可以视作基本遗传单位。基因的产物可以是蛋白质和RNA,从而控制生物个体的性状差异表现。而两个基因的相似度有多高,演化上是否可能同源。归结到计算上,就是如何找到两个序列的最优或近似最优的比对。随着人类基因组计划的测序工作的完成,生物信息科学的研究重点放在了探明基因序列的功用上。而在高通量测序技术快速进展的背景之下,生物数据呈现指数型增长。因此产生了对大量生物信息数据进行高效准确分析的需求。基因序列决定了生物的性状,查找出基因差异性对于人类克服疾病具有深远的意义。本文在Xeon Phi众核架构上,设计并实现了一个全新的超长序列比对算法SLPal。该算法的计算核心是基于位并行的BitPAI算法。在粗粒度上,为了实现多线程并行,我们将超大规模的矩阵进行了划分。在垂直和水平方向上分别进行划分,将矩阵分成了网格。然后通过Intel TBB并行编程库构建了有向无环图模型来实现该网格中矩阵块之间的并行。在细粒度上,我们用Xeon Phi上的指令集编写了 Intrinsic指令。SLPal中的一些操作没有对应的向量化实现,我们采用手动编写函数来实现了... 

【文章来源】：山东大学山东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：59 页

【学位级别】：硕士

【部分图文】：

图3一2位向量刁扩的计算实例

?山东大学硕士学位论文???ＣＰＵ数量等优势，而且ＴＢＢ拥有并行循环，并行排序，流的并行和并行容器，??以及可扩展的内存分配，动态任务调度器。所以最终本人选择ＴＢＢ来编写本人??的程序。任务调度器是线程构建模块的核心组件，它是通过线程来提升性能的。??在ＴＢＢ的任务调度中，一个任务作为一个基本计算单元，由调度器将线程与任??务结合在一起，并且将任务分派到物理线程进行执行。任务调度器拥有一个全??局线程池，进行任务调度之前，需要初始化线程构建模块，然后任务调度器会??根据这个线程池自动管理任务，将每个任务动态分配到压力较小的物理线程上，??实现负载均衡。??

由于计算超长序列的全局序列比对，相当于要计算一个ＭＸＮ的动态规划矩??阵，其中Ｍ和Ｎ分别为所对比的２个序列的长度。且Ｍ和Ｎ可能长为１００Ｍ大小，??所以为了充分利用多线程资源，本人将所要计算的矩阵划分为如图３－６所示的??子矩阵，并且其中每一个子矩阵都是一个任务类的实现，也就是ＳＬＰａｌＴＵｅ??类的实例，ＳＬＰａｌＴｉｌｅ继承自ｔｂｂ：：ｔａｓｋ类。并且ｔａｓｋ类交由ＴＢＢ［４６］任务管??理器ｔａｓｋ＿ｓｃｈｃｄｕｌｃｒ＿ｉｎｉｔ进行管理。根据前面说明的ＢｉｔＰＡｌ算法可以得知，??计算每个单元格的数据依赖仅仅存在于上方和左侧的单元格，所以ｔａｓｋ之间的??３０??


本文编号：2951784