多核cpu和gpu系统上motif发现并行算法研究

《多核cpu和gpu系统上motif发现并行算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士硕士学位论文张静多核CPU和GPU系统上Motif发现多核并行算法研究和系统上张静发现并行算法研究二○一四年六月CPUGPUMotif2014分类号密级UDC硕士学位论文多核CPU和GPU系统上Motif发现并行算法研究张静学科专业计算机软件与理论指导教师钟诚教授李智研究员论文答辩日期2014年5月24日学位授予日期答辩委员会主席葛丽娜教授广西大学学位论文原创性和使用授权声明本人声明所呈交的论文，是本人在导师的指导下独立进行研究所取得的研究成果。除已特别加以标注和致谢的地方外，论文不包含任何其他个人或集体已经发表或撰写的研究成果，也不包含本人或他人为获得广西大学或其它

2、单位的学位而使用过的材料。与我一同工作的同事对本论文的研究工作所做的贡献均已在论文中作了明确说明。本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属广西大学。本人授权广西大学拥有学位论文的部分使用权，即：学校有权保存并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或其它复制手段保存、汇编学位论文。本学位论文属于：□保密，在年解密后适用授权。□不保密。(请在以上相应方框内打“√”)论文作者签名：指导教师签名：作者联系电话：日期：日期电子邮箱：多核CPU和GPU系统上Mo

3、tif发现并行算法研究摘要Motif（模体）是指DNA序列中长度较短、具有保守功能的序列片段，Motif发现即从DNA序列中寻找出Motif的过程，该问题是生物信息学中一个基础而重要的研究课题。利用计算机技术来解决该问题的目标是寻找更长l的Motif。因此，在多核CPU和GPU系统上研究设计访存高效、加速比高、可扩展性好的(l，d)-Motif发现并行算法具有现实意义。本文结合多核计算机的多级缓存存储结构特点，设计实现了一种访存高效、加速比高、可扩展性好的线程级并行(l，d)-Motif发现算法。充分利用多核结构的共享三级缓存、私有二级和一级缓存容量大小，将求解(l，d)-Motif发

4、现问题过程中产生的大量不同位置组合的数据，以多轮方式调度分配到各级缓存中，使得各个核心在并行求解(l，d)-Motif发现问题时，大大减少了数据在主存和缓存之间的交换次数，实现了并行算法的访存高效；同时，通过线程绑定平衡了各计算核心的负载、减少了线程迁移开销。实验测试综合考虑了不同(l，d)-Motif发现问题规模、处理核心数、线程数目、各级缓存可利用大小等多种因素对多核计算机上(l，d)-Motif发现并行算法性能的影响。实验结果表明，随着处理核心数的增加，本文多核计算机上(l，d)-Motif发现并行算法表现出越高的效率，具有良好的加速比和可扩展性，在并行求解较长l的(l，d)-M

5、otif发现问题时，其所需的运行时间明显少于同类研究的其他算法。I根据GPU的结构特点以及存储器特点，将求解(l，d)-Motif发现问题过程中产生的大量不同位置组合的数据和候选序列集合绑定到纹理存储器中，通过缓存加速访问，减少访存时间；对不同的(l，d)-Motif发现问题规模，依据组合数据大小设置GPU端线程块的尺寸，设计实现了多核CPU与单GPU混合机器上(l，d)-Motif发现并行算法，为提高处理较大规模(l，d)-Motif发现问题的加速效果，同时设计实现了多核CPU与多GPU混合机器上(l，d)-Motif发现并行算法。实验测试综合考虑了不同(l，d)-Motif发现问题

6、规模、不同线程块尺寸、GPU数目等多种因素对多核CPU与GPU混合机器上(l，d)-Motif发现并行算法性能的影响。实验结果表明，与多核计算机上(l，d)-Motif发现并行算法相比，多核CPU与单GPU混合机器上的(l，d)-Motif发现并行算法具有更高的加速比，当求解更长l的(l，d)-Motif发现问题时，多核CPU与多GPU混合机器上(l，d)-Motif发现并行算法的运行时间更短，效果更优。关键词：(l,d)-Motif发现多核计算机多核CPU与GPU系统多级缓存线程级并行纹理缓存访存高效线程绑定IISTUDYONPARALLELALGORITHMSFORMO

7、TIFFINDINGONMULTI-CORECPUANDGPUSYSTEMSABSTRACTMotifisafragmentofDNAsequencewithshorterlengthandhasconservedfunction.MotiffindingproblemistheprocessoflookingMotiffromtheDNAsequenceanditisafundamentalandimportantresearchtopici