基于多GPU并行计算的高通量抗体序列比对研究

基于多GPU并行计算的高通量抗体序列比对研究 厦门大学学位原创性声明 兹呈交的学位论文,是本人在导师指导下独立完成的研究成果。本人在 论文写作中参考的其他个人或集体己经发表的研究成果,均在文中以适当方 式明确标明,并符合法律规范和《厦门大学研究生学术活动规范试行》。 本人依法享有和承担由此论文产生的权利和责任。 声明人签名: 觚 年月孑日 砂厦门大学学位论文著作权使用声明 本人同意厦门大学根据《中华人民共和国学位条例暂行实施办 法》等规定保留和使用此学位论文,并向主管部门或其指定机构送交 学位论文包括纸质版和电子版,允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索,将学位论文的标和 摘要汇编出版,采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于: .经厦门大学保密委员会审查核定的保密学位论文, 于 日解密,解密后适用上述授权。 年/月 .不保密,适用上述授权。 请在以上相应括号内打“?”或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文,未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的,默认 为公开学位论文,均适用上述授权。 日期:切埠月日 作者签名: 导师签名: 日期:砂年月日 觚铡 叶妒要的意义。在对抗体序列多样性分析中,关键步骤之一就是如何利 用有效 的序列比对方法,将原始的未经识别的抗体序列与已知的模板序列 进行比对,并能正确分类。随着新一代高通量测序技术在单位时间内测得 的序列条数大量增加,需要分析的抗体序列规模已经达到了几十万到几千 万条。因此,寻找高效处理高通量序列比对问题的方式,成为目前生物信息学 研 究的重要内容。 目前,利用图形处理器搭建的统一计算架构,为实现高 度并行化计算提供了一个高性能和相对低成本的计算平台,并在很多领域实 现了 高性能并行计算的成功案例。基于该平台,部分基于单的生物序列比对算 架构和最新 法也被提出,并获得了较好的加速效果。随着新一代 通用计算开发包 .的发布,并行编程性能得到更大提升,并 且多程序开发也变得更简单,让更多的编程人员能够方便的利用单甚 至多个来实现程序的高效运行。因此,针对抗体序列比对问题设计一种特 定适用的并行计算流程具有重要的意义。 本文在对高性能计算技术和高通量抗体序列处理的研究基础上, 讨论了如何利用实现高通量抗体序列的比对,分析了多并行计 算方式,给出了多间的线程问通信和数据存储方式,设计实现了多进 行高通量抗体序列的比对程序。在相同的计算机硬件条件下,针对两种动物 的高 通量抗体序列比对问题,采用多并行计算方式、单计算方式, 以及单线程和多线程计算方式分别进行计算比较,结果表明是多并行 计算方式提高了处理速度,为高通量序列处理提供了启发和进一步结合生 物问题的研究必要。 关键词:多;序列比对;抗体 ’ ’.’, 、析., .,. ,, 谢 . , ., .., . , ? , , . , ?,,. ., . ; :;; ................................................................. ............................目录。 ........................................................?...?.... ?.........................? 第一章绪论??. .研究背景与意义 .国内外研究现状 。 .论文的研究目标和主要工作? ? .论文的组织结构。 第二章抗体序列比对问题?. 。 .抗体多样性分析流程 。 .抗体基本知识介绍 ? 抗抗抗 体体体 的基的 构重样一排性 结因多 .抗体组合分类. 第三章多并行计算研究.. . 背景及发展现状. .通用计算模型??. .. 架构.. .. 编程模型??一 .. 存储器模型. 并行算法设计原则. ..一般原则 ..性能优化建议? 目录? .多并行特点??. .. .? ..多线程通信..多数据存储??. .多算法评价指标. 第四章基于多的抗体序列比对方式??. .并行化的算法。 .基于单的算法并行实现 ..并行化策略?。 ..存储器优化?.. .基于多的序列比对流程设计.优化策略 第五章实验与分析 .测试条件 ..实验数据来源~ ..硬件参数指标? .性能匕较? ..单与单线程比较? ..双与单比较??。 ..双与多线程比较? .结果分析. 第六章总结与展望. .总结。 .展望。..。。... 参考文献?. 攻读硕士学位期间发表的学术论文?. 致射??. ............................................................... ..??.??.. . 。 . ............? ..?..?..??.?. ..?. ... ..?.. . ....?............? .. ..?.. ..??..?. .. ?.. ...??.. ..?..?. ... .? .. . 陀。 ..?.. .?...?.??........................................................ ............................................................:; .??..? . ...??. .... ...??.. . ???.... .......?.??..... ............................................... ...... .??.?.....??..??. ?...?.. ..?. ..?.. .??..?.. ..??. ..?。 ..?. .??川??????川? ? .?... ...................................................... ...??.??...... .?...?...??.....??. .......................................?......................... ............................;; .................. .........................?....................................... ................ 绪论 第一章绪论 .研究背景与意义 生物序列比对是生物信息学和遗传学研究中最常用的研究方法之一。随着 测序技术的快速发展,新一代高通量测序技术在单位时间内一次可测得几 十万、甚至上千万条的基因序列。一方面,如此大规模的生物序列为生物学家提 供了更丰富的研究数据。另一方面,它也带来了处理的难题,其中最亟待解决的 问题就是,如何快速有效的处理这些高通量序列的比对问题,并得到我们需要的 结果。 以前在上的序列比对方式在处理这类海量的分析数据时,通常运行在 价值上万甚至更贵的计算机集群上,如果用台式计算机来处理将需要更多的计算 时间和更高的计算机性能。随着多核计算技术的飞速发展和技术的不断成 熟,人们开始寻找解决这些问题的新,将原始的串行算法改写为并行算法的 思路慢慢形成。并行计算可以充分利用现有计算机硬件的处理能力,目前 并行已经在很多领域得到了应用,其中不乏生物序列比对问题。 相对于,在计算吞吐量和内存带宽上都有明显的优势,并且成本 和功耗上都相对低很多。高度的并行性,惊人的计算能力,低廉的价格, 较低的功耗,良好的可编程性以及商业界和学术研究人员的大力支持和推广,使 其成为一个新的并行计算平台,将会被越来越广泛的应用于高性能计算领域。因 此,在并行计算平台上研究高通量序列的比对问题,有利于推动生物信息 科学相关领域的发展,具有深远的研究意义。 研究自然免疫系统抗体库的特征,分析免疫系统抗体库的多样性和寻找这种 多样性机制产生的原因,一直是生物学家和遗传学家致力解决的问题【】。抗体分 子作为机体免疫防御系统的重要组成部分,以其特有的基因结构和重排机制形成 了巨大的多样性,其组成的抗体库也具有很高的可塑性。研究表明,动物的抗体 数量理论上可以达到种,由此产生的可以同各种不同的抗原特异性结合的特 性,使抗体成为机体内最为复杂的分子【】。基于多并行计算的高通量抗体序列比对研究 处理抗体序列关键的步骤就是明确其属于哪一类组合,为了正确的分 类抗体序列,可以利用双序列比对方法,让其与已知的模板序列进 行比对计算。而在对海量数据的抗体序列比对这一类问题的处理上,目前 还没有一种特定适用的并行计算流程。因此,本文基于多并行计算平 台研究高通量抗体序列比对问题有着重要的实际意义。 .国内外研究现状 作为生物信息学的基础学科,生物序列比对算法在几十年前就已经被提 出。这些算法经过很多科学工作者的研究和改进,已经发展出了许多不同的生物 序列比对方法,包括基于动态规划或启发式的算法,如图所示。 图生物序列比对算法分类 序列比对根据同时进行比对的序列数目不同,分为双序列比对和多序列比 对。序列比对从序列间的相似性范围考虑可分为全局比对和局部比对。 和于年提出了基于动态规划的双序列全局比对 绪论 算法【。年,和在算法的基础 上,提出了改进的双序列局部比对算法。上述两种算法 的比对结果精度很高,已经被公认为经典的双序列比对算法,然而他们的执行过 程复杂,计算时间很长且对计算机性能的要求非常高,因此提高这两种算法的执 行效率一直是许多研究组致力解决的问题【。 为了降低计算时间,一些启发式算法被相继提出,如和】, 它们虽然能够加快计算的速度,但却牺牲了一定的计算精度。在这种情况下,使 用高性能架构,特别是利用新兴的加速器技术和多核架构技术改进和两 种序列比对算法成为近年来的一个研究趋势。文献【】、】、【】、都是利用 大规模计算机集群实现了算法的并行计算,而基于单个计算机多线程并行程 序也 、、,并使和 相继提出,如、/ 算法并行的效率得到了更大提高。 目前,利用公司的图形处理器搭建的统一计算架构 ,为实现高度并行化计算提供了高性能和相对低成本的计算平台。基 于该平台,已有许多可获得较高性能的生物序列比对算法改进方案。表.比较 了利用多核计算平台将串行的和算法程序并行化实现的相关研究成果。 等人最先提出了基于的.?算法., 其计算速度比以往算法在通用硬件上的计算速度快了到倍【】;和 等人借鉴了前者的经验,通过深入探索可支持的硬件的 计算能力,为.蛋白质数据库检索做出了新的贡献,并且最 近发布的软件.在单个 显卡上计算性能最大可 达 .等人则尝试了利用多 ,】;个显卡对长度大于的序列的比对进行计算,其性能最高达到 . 。基于多并行计算的高通量抗体序列比对研究 表多核计算平台下的部分和并行算法比较 输出结果 精确度 文献 提出的算法 并行架构 并行方式 , 【】 / , 入 【 / / 【】 , ./ 【】 、?五的 ,/ 】 】 / , 【】 勋 萄. 【】 /, , 【】另外针对其他比对算法,等人利用技术提出针对基于后缀树 的全基因组比对算法,其速度比其版本加快了倍【】; 、和等人分别带领他们的课题组提出了不同的基于的 计算方法,计算速度比.的计算速度快了~倍,并且等 人的方法在提高计算速度的情况下,还保证了结果与.的一致 】。上述利用技术实现的序列比对算法明显可加快比对速度,但目 前有许多序列比对问题还需要研究特定适用的并行计算流程。 绪论 在国内,针对并行计算的研究在一些科研院校和商业机构也逐步开展 起来。清华大学、中科院计算技术研究所、国防科技大学等也相继利用并 行计算进行研究,并取得了很多成果【。 年月在北京举行的亚洲技术大会上,身为全球最大的基因组研 究机构中国华大基因宣布,该机构研究人员与合作人员已经开发出三款可由 加速的基因组数据分析应用程序:将短序列与现有的参考基因组序列 进行比对的程序,可基因组中单个核甘酸多态性变种的 程序,以及高分辨率基因型分析工具。利用这些基于的服务器群加 速应用程序,研究人员大幅缩短了工作时间,使分析序列数据的时间从将 近四天缩短至短短六个小时。 随着可编程能力和并行处理能力的不断提升,应用范围的不断扩展, 发挥的高性能计算能力对生物信息计算的关键问题进行深入研究,将为进 一步加快生物信息学发展,为科学计算和生物分析提供新型的计算资源起到 重要 的作用。 .论文的研究目标和主要工作 本文以如何高效处理高通量抗体序列的比对问题为目标,针对以下几 个问题进行了研究: 目前基于的并行编程模型是否适用于海量抗体序列比对问 题。 研究针对一般性问题设计并行算法的原则,讨论多并行计算 的特点和最优实现方式。 给出一种通用的基于多并行计算的高通量抗体序列比对流程。 本文主要工作是,在对高性能计算技术和高通量抗体序列处理的 研究基础上,讨论了如何利用实现高通量抗体序列的比对,分析了 多并行计算方式,给出了多间的线程间通信和数据存储方式,设计实 现了多进行高通量抗体序列的比对程序。在相同的计算机硬件条件下,针 对两种动物的高通量抗体序列比对问题,采用多并行计算方式、单 计算方式,以及单线程和多线程计算方式分别进行计算比较。 基于多并行计算的高通量抗体序列比对研究 .论文的组织结构 全文分六章,本文的结构安排如下: 第一章绪论。概述了本文的研究背景与意义,国内外研究现状,研究目标和 主要工作,以及文章的组织结构。 第二章抗体序列比对问题。首先描述了高通量抗体序列多样性比对分析的一 般流程,并阐明了论文所要分析的关键问题;然后详细介绍了生物抗体序列 比对 的相关知识,包括抗体的结构、抗体基因重排过程以及抗体多样性产生原因; 最 后介绍了对抗体序列组合分类的方法。 第三章多并行计算研究。详细介绍了计算模型,主要包括 架构、编程模型和存储器模型,并探讨了并行算法的设计原则,分析了多 算法并行的特点及评价指标。 第四章基于多的抗体序列比对方式。首先研究了.算法 的并行化实现方法,然后针对该算法的并行特点设计并实现了基于并行的 实现方式,并提出了一种通用的基于多并行计算的高通量抗体序列比对流 程。最后介绍相关的优化策略。 第五章实验与分析。以两种动物的抗体序列为测试数据,分别用多 并行计算方式、单计算方式,以及单线程和多线程计算方式进行了计 算与比较分析。 最后是全文的总结和展望。 第二章抗体序列比对问题 第二章抗体序列比对问题 为了阐明论文所要分析的关键问题,建立涉及生物信息领域的相关概念、基 本知识,本章简要介绍了生物抗体库多样性分析的一般流程,其中对抗体序 列的 比对计算是该流程中的关键步骤;然后介绍了生物抗体序列的相关知识,包 括抗 体的结构、基因重排、多样性产生原因,以及抗体组合分类。 .抗体多样性分析流程 研究免疫系统抗体库的多样性,即需要研究抗体库中的抗体序列到底有多少 种,这么多种抗体序列的存在有没有一定的趋同性或互异性。目前研究的生 物抗 体序列都是通过高通量测序技术得到的,高通量测序技术是对传统测序技术 的一 次革命性改变,其可实现一次性对几十万到上千万条分子进行序列测定, 因此称为下一代测序技术州。高通量测序技术使得对一个物种的转录组和基 因 组进行细致全貌的分析成为可能。 由于经高通量测序仪测序得到的序列数量大且存在一定的噪声数据,随着研 究的目的不同,需要对高通量抗体序列进行预处理和序列比对后的后续处理, 以 满足序列多样性分析的需要。如图.所示,对高通量抗体序列多样性比对分析 的主要流程如下: 比对前数据预处理 对高通量测序得到的原始抗体序列进行数据预处理,包括低质量序列过滤、 相同序列合并等。预处理后得到的抗体序列将作为查询序列集,而固定的// 基因模板序列将作为目标序列集,等待执行比对计算。 利用比对算法比对 查询序列和目标序列分别被传输到计算机内存中,然后利用基于动态规划的 全局或局部比对算法,如.算法和.算法进行序 列比对计算。由于抗体序列是由//三种基因模版组合而成的,为了正确识别 序列上对应的//相似性区域,我们利用.局部比对算法进行 计算。该部分的计算也是整个流程中最耗时的部分。 基于多并行计算的高通量抗体序列比对研究 原始高通量抗体序列 上 低质量序列过滤 土 相同序列合并 士 预处理后的序列 //基因模版 作为查询序列集 作为目标序列集 每条查询序列鼍暑霁妻目标序列进行 士 相似片段 比对得分值 上 上 标记参数信息,并将抗体序列正确分 类组合 土 序列统计后续分析 图高通量抗体序列多样性比对分析流程 抗体序列正确分类 序列比对计算输出的结果一般为查询序列与目标序列间的相似性得分值,只 有与查询序列相似性得分最大的目标序列才是组成该条抗体序列的//基因 片段。得到的最佳匹配结果将作为参数信息标记到对应的序列标签中。 序列统计后续分析 根据比对结果,将每条抗体序列分类到正确的组合中,并确定序 列上相似区域的起始位置。然后利用统计分析工具对每种组合的抗体序列进 行后 续的统计分析。 由于待比对的抗体 分,因此寻找一种更高 正确地组合分类是抗体多样性分析中的首要任务。 .抗体基本知识介绍 ..抗体的结构 抗体是指机体在抗原物质刺激下,由细胞分化成的浆细胞所 产生的、可与相应抗原发生特异性结合反应的免疫球蛋白阅。主要存在于脊 椎 动物的组织液及外分泌液中。 抗体共分为五种类型: ,,,,,每一种类型与不同的 免疫反应有关。每个抗体都由两种类型的肽链组成:相对分子量较大且长度 较长 的两条重链链和相对分子量较小且长度较短的两条轻链链。如图? 所示,整个抗体分子又分为可变区 和恒定区 两个部分,可变区包含了高度多样化的抗原结合区域,决定了抗体结合抗原 的特 异性,其中重链在免疫过程中发挥着最主要的作用【引。 区 图抗体分子结构 基于多并行计算的高通量抗体序列比对研究 ..抗体基因重排 抗体重链序列是由、、和四种基因片段经过一系列的重排事件产生 的,其中撕为编码可变区,有个种类;为编码高 变区,有个种类;为编码连接和的结合区,有个种 类;为编码恒定区,仅有一个种类【。 一条原始的抗体重链基因序列上,所有种类的、和基因片段是串联在 一起的,在重排时,这些片段将按照先与结合后与结合的顺序,从、 和片段中各自随机的选择一段进行组合,从而产生出一条新的抗体重链序 列。 图.展示了一条抗体重链序列产生的基因重排过程。 . ???? ??? 争?? ???一 图一条抗体重链序列产生的基因重排过程 ..抗体的多样性 抗体分子最显著的特点是和抗原结合的专一性,以及这种专一性的多样性。 有人证明对于同一种抗原可能产生几百、甚至上千种不同的抗体。对于抗体 多样 性的遗传控制问题,曾经存在种假说:种系学说又称胚系学说,主张 编码所有抗体的基因全部存在于生殖细胞的基因组内。抗体分子的多样性是通过 长期进化形成的,并通过生殖细胞从亲代传给子代;体细胞突变学说,认为 生殖细胞内只存在为数不多的抗体基因。抗体多样性主要是由于个体发育过程 中,体细胞突变的结果;区基因相互作用学说,抗体分子可变区是由 第二章抗体序列比对问题 基因片段、基因片段和基因片段三种拼接组成,抗体多样性的产生主要是因 为、、基因的相互连接。从目前的研究结果来看,抗体多样性不能简 单地归因于上述种学说的某一种,但是每种学说也为其形成原因提供了一定的 理论依据。 抗体的多样性受细胞系统的遗传基因控制。从理论上来说,动物的机体可 以产生针对所有抗原的抗体,抗体结合抗原的多样性是由其可变区结构上的多样 性决定的,而基因多样性又决定了抗体可变区结构的多样性。当前主要的研究一 致认为抗体基因序列的多样性主要由以下几个因素所导致: 基因重排 一条原始的抗体基因序列通过图.描述的重排方式和组合过程,可以 得到很多数量的新的抗体序列。假设、和基因片段的种类数分别为、 和.,种,那么理论上可能发生全部抗体序列重排事件的组合数有,×.,种。 连接的多样性 基因片段的连接位置虽然相对固定必须在各片段的端部连接,且片 段仅在其’端连接,但有在几个核苷酸范围内移位的自由度。例如,即使 相同、基因片段的连接,由于其连接位置的随机性也每次都稍有不同, 因此在连接处的碱基将产生不同的遗传密码。另外,与基因片段之间以 及与基因片段之间,还有其他来源的核苷酸序列插入。这些核苷酸序 列不存在于任何生殖细胞的基因片段中,被称为非生殖细胞因子,亦称区 或序列。 因此,、.基因片段连接处核苷酸的缺失、插入和连接位置移动, 能共同增加抗原结合部位的多样性,但也有很多的情况,造成遗传密码的位 相错误,致使重组后的基因片段不能翻译为氨基酸,而成为残品。 基因片段上的碱基突变 当复制时,基因片段中部分碱基会产生很多点突变,点突变的位 置主要发生于重排后的可变区基因’端和’端上个左右的碱基内。点突 变的产生也导致了不同抗体序列数目的增加。基于多并行计算的高通量抗体 序列比对研究 .抗体组合分类 为了将一条抗体序列正确的分类到对应的组合中,可以利用基于动态规 划的全局或局部比对算法,如经典的.算法和 算法,将每条未分类的抗体序列与固定的、和基因模板序列进行相似性比 对计算,找到序列上与基因模板最佳匹配的每个片段和区域,然后进行正确 的 组合分类。 如图.所示,抗体序列比对的计算过程可描述为: 采用统一的得分矩阵匹配得分,错配得.分,抗体序列首先 将与所有模板序列和模板序列通过.算法进行序列比对 计算,并分类到不同的/组合。 分离出介于最后一个与模板序列匹配的碱基和第一个与模板 序列匹配的碱基之间未匹配的子序列即区域,分别与所有模板序列 进行比对分类。 返回的结果为,与每条抗体序列最佳匹配的//模板序列和抗体 序列中对应各//片段的起始位置;最后将结果作为标记信息储存到每条 序列标签中。 ‘?。。, 伯 【?豳瞄?豳豳’,:??????? ?????豳???一 帅??豳圈圈豳豳翻豳?????????? 图抗体序列的比对计算过程 第三章多并行计算研究 第三章多并行计算研究 . 背景及发展现状 即为图形处理单元,是由英伟达公司在年发布 图形处理芯片时首先提出的 概念。计算机在 对图形处理时,可以分担部分原本由来做的工作,降低显卡对 的依赖性。由于人们对实时图像的强大要求,演变成了一个具有强大浮点 数编程和计算能力的处理器。在计算吞吐量和内存带宽上,现代的远远超 过,这使得成为能够加速数据并行的理想的处理器。 开发的非图像应用早在年就开始了。通过使用绘制语言,如 ,和,许多数据并行算法开始在上取得成效,例如蛋白 质的折叠,股票定价,数据库查询,核磁共振图像重建在上 都实现了明显的加速【】。这些早期的编程是使用图像实现通用目的计算的, 即我们通常所说的编程。 模型证明了其具有很高的加速比,但是它仍然有几个缺点:.要求编 程人员精通图像和架构的知识。.所要解决的问题必须使用顶点坐标, 纹理和阴影程序表达,大大增大了编程的复杂性。.基本的编程属性如对内存 的 随机读写是不支持的,明显限制了编程模型。.缺乏对双精度的支持意味着一 些 科学计算不能使用加速。 为了解决这些问题,之后的可以使用多种高级语言进行编程,兼有了 软件和硬件属性,程序员不需要再使用那些专用于图形单元的图形编程, 而是可以使用 语言进行编程以达到通用目的即大规模并行处理,这种 新的编程被称之为计算模型“ 一这意味着支 持更广泛的应用,支持更广的编程语言同时和早期的“模型区分开来。 这些改进使得与相比,对于特定数据的处理有其特殊的优势。作 为一种通用处理器,既要兼顾数据运算和程序执行的平衡性、通用性,又 要保证满足数据并行运算和指令并行执行的设计原则,使得有强大的复杂 逻辑控制计算能力,而运算单元相对所占比例较少;而鉴于图形渲染的并基 于多并行计算的高通量抗体序列比对研究 行性,其内部拥有大量重复设计的运算单元,如图.所示。这些运算单元可以 被分成很多独立的数值计算,而且数据间没有复杂的逻辑关联性。因此, 的这些特点使得它比更适合处理大规模的并行化数据集,并且提供的计算 能力与相同时,所需要的成本和功耗都要小很多。 嗣口工工口工工【圆 工口工工口皿 溢工工口】工工团 薹噩噩韪噩蕊 工工工置口工工团 溢工工 口工工皿 图 比投入更多晶体管用于数据处理? 现在如何改善现有的应用程序和的可编程能力,已经是开发人员设计 新一代产品时一直面临的问题;同时,快速发展的应用程序也推动了 在可编程性上的快速发展,这使得成为现代最具有潜力的并行处理器。 .通用计算模型 .. 架构 编程模型与传统程序有着巨大的差别,在开发过程中特别要求开 发人员对的硬件架构有一定的了解。近年来,和两大显卡制 、 造商都各自推出了用于通用计算的开发平台如公司的 苹果公司的和公司的,其中的新一代 架构已经可以支持多种编程语言,如、、语言、等, 并可实现超级计算特性与性能【】。因此本文以最新的 架构为 例进行研究。 年月份基于架构的显卡产品正式上市。自从以来, 架构是架构发展的最有意义的可称得上革命性的跨越。是第一款统一 第三章多并行计算研究 图形和计算架构的并行处理器,是对在编程和功能方面的扩展,而 是基于之前的两种处理器和所有基于它们编写的应用程序的基础上开发 的,其使用了一种全新的方式创造了世界一流的计算性,表.展示了三代 架构的特性比较。 表 、和三代架构的特性比较 架构特点 晶体管 .亿 亿 亿 内核总数 个数/ 单元数/ 双精度浮点数性能无 个数/周期 嗄/周期 四/周期 /周期 单精度浮点数性能 调度/或 共享存储器大、/ , , 寄存器文件个数/ , 缓存/ 无 无 或 缓存 无 无 支持统一的地址 三种, 三种 指针地址空间类型 空间 , 功能 无 无 支持 无 无 支持,最多 并发 无 无 支持 分支预测 , 实时调度的线程个数 , , 基于的新一代架构拥有亿个晶体管,个内核,其 硬件架构如图.所示。每个内核在一个时钟周期内执行一个线程或 中的一个浮点数或整数指令,个内核是按照个含有个基于多并行计算的高通 量抗体序列比对研究 内核的进行组织的。拥有个的显存分区,因此支持.的 显存接口。最大支持的类型的显存容量,和之间是通过 .总线连接的,千兆线程管理器负责将线程块分发到中。 整个架构由两部分组成,分别是流处理器阵列和存储器系统, 他们之间通过一个片上互连网络连接。流处理器阵列的结构可以分为两层: 第一 层是若干个线程处理器群;第二层是每个线程处理器群中的个流多处 理器。每个流多处理器又包含个标量流处理器,以及少量的其他 计算单元。 图 硬件架构【 架构的主要特点是: 采用第三代的流多处理器 每个拥有个处理器,每个处理器拥有完整的整数运 的缓存或者配置为的共享存储器和的缓存。对于需要 使用共享存储器的程序来说,三倍大小的共享存储器可以明显提高程序的性 能, 尤其是当带宽成为某个程序的瓶颈的时候。对于不需要使用共享存储器或者 使用 共享存储充当缓存的程序而言,它们可以充分利用到硬件缓存和,在使用 缓存带来的好处的同时还可以获得至少的共享存储器以满足线程之间的 通信。最大的好处是,不使用共享存储器的程序可以得到缓存带来的好处。 采用第二代的并行线程计算指令集架构,完整支持 基于多并行计算的高通量抗体序列比对研究 是第一个支持并行线程计算.指令集的架构。是一个底层 的虚拟机和,其支持并行线程处理。在程序运行的时候,指令就会被 驱动程序翻译为机器指令从而被执行。 .引入了几个新的特性可以大大改善的可编程性、精度和性能, 主要包括:完整支持.浮点数计算、统一的地址空间以支持所有的变量 和指针、支持“寻址并为和 增加了新指令。最重要 的是,.进行了专门的设计完全支持编程语言。 使用统一地址空间,可以完整支持抖编程。在中,所有的变量 和函数都是以对象形式组织的,对象是通过指针传递的。如图.所示,在. 版本中,使用统一的指针可以在统一的地址空间中找到其它空间上的对象, 然后 统一地址空间中的对象再由硬件自动正确的映射到实际的三种不同的地 址空间上。 独立地址空间’一 ? \ 、 ? 、 卜甜;:习 ? ‘ 统一地址空间 ? 卜’:嘞:,、,曲?’’一一。。‘习 图统一指针映射在统一地址空间中查找其它对象 第三章多并行计算研究 支持错误检查与纠正功能 是第一款支持基于存储器数据保护的错误检查与纠正功能: 的架构。在高性能计算应用中,可以提高数据的一 致性。尤其是在医学影像和大规模集群计算中,是非常重要的。在存储器 中存储数据的时候,激光束可能会引起“层面的改变,从而导致软件层面的错 误。技术在错误影响到系统之前便检测并修复单个“引起的错误。由于这 种激光导致的错误随着系统的增大而线性增大,因此,对于大型集群,技 术是必不可少的。 支持单“错误的修复和双错误的检测. . :。 可以修复任何单引起的错误。 同时,确保能够检测出所有双“和多引起的错误并报告提示以便重新运行 程序而不是带着错误的数据继续执行程序。 的寄存器文件、共享存储器、缓存、缓存和都支持 的保护,这不仅使得变得非常强大,而且非常的可靠。另外,对于 片上的数据传输支持数据校验。所有的 都支持.,支持 ,. 一粤掣一’ 链接层面数据再发送的循环冗余校验。还支持存储器总线上数据 再发送的校验。 支持多个并发执行 支持并发的执行,同一上下文的不同可以同时在 上执行,如图所示。并发可以使程序同时执行一定数量的小的 以便充分利用整个的资源。例如,物理程序可能会涉及到流体 和固体的计算,如果串行的执行,仅能利用一半的处理器,但是如果并行的话 就 可以完全利用整个处理器资源。在架构中,相同上下文的不同 可以并发执行以最大化的利用的资源。由于架构提高了上下文切换 性能,不同上下文的可以高效的串行执行。 基于多并行计算的高通量抗体序列比对研究 。。 “。、’, ~灿“~?一??????十?“一一一一一一一?“啼??????~?砷????十 ,。 ’ 毖鬈彭主二蜘:璺麓烹薯:露弱寸蠡 知。中一一;一岛一一一一?争吩寸囊专 ; ;缓缓;;;;;;; 铡 鬟。《“糕滋溅蹇 ;,.二 锄;;五五二;;;象八;; ”: :“《 奠:::,:、 ??: 。‖:? ; ;;:“?“, ; ;;;; 二 稳;; 眩,;; ;;,;,;,;?,, 五 ;,。; ;; ;;;。, 串行执行 并发执行 图 支持并发的执行 像一样,通过上下文切换也支持多任务执行,即每个程序都可以 获得处理器资源的一部分时间采用分时的方式利用处理器的计算资源。 架构的指令流水线经过优化可以将应用程序上下文切换时间降低到以下, 比有了很大的改善。除了性能的改进,这种快速切换可以使开发者创建 更好的需要进行频繁的..通信的应用程序,比如图形和物理应用程 序之间细粒度的相互配合。 .. 编程模型统一计算架构的简称,是 是 一种使用类语言进行通用计算的开发环境和软件体系。其编程模型将 作为主机,作为适合并行化数据处理的计算设备,如图.所示, 在执行模型中,与协同工作,负责进行逻辑性强的事务 处理和串行计算,则专注于执行高度线程化的并行处理任务,主机和 设备之间的数据传输通过总线来实现。第三章多并行计算研究 图. 执行模型中与协同工作 运行在上的并行计算函数称为内核函数,如图.所 示,内核函数以线程网络的形式组织,每个线程网络由若干个线程块 组成,而每个线程块由最多个线程组成。内核函数在被 调用时,它将被条不同的线程并行执行次,每个线程都有自己的 和用于与其他线程区分。任何内核程序被主程序调用之前,必 须确定线程块的数目和每个线程块中的线程数,以及共享内存的大小。 在实际运行时,一个内核函数以线程块为单位执行,属于同一个线程块的线 程不仅能够并行执行,而且能够通过共享存储器来共享数据,并利用栅栏同 步实 现数据共享。 基于多并行计算的高通量抗体序列比对研究 图 架构中的线程组织形式 .. 存储器模型 为了编写高效的程序,除了编程模型之外还必须了解一些底层 硬件架构的基本属性,特别是存储器空间管理。如图.,存储器模型有 种类型的存储器:局部存储器、共享存储器、全局存储器、常数存储器、纹 理 存储器和寄存器。存储空间较小 共享存储器 被同一个线程块中的所有线程共享 访问速度与寄存器相当 ?存储空间较小 全局存储器 能被网格中的所有线程共享 ?可以被、共同读写访问 ?拥有最大的存储空间与显存的大小相当基于多并行计算的高通量抗体序列 比对研究 延迟较高、带宽低于片上存储器 没有缓存 常数存储器 为只读存储器 可以被同一个网格中的所有线程访问 一存储空间较小 当中的所有线程访问同一个地址时,访问速度较快 纹理存储器 为只读存储器 可以被同一个网格中的所有线程访问 有缓存 存储空间较大,且取决于全局存储器的大小 寄存器 只被每个线程所私有 ?存储速度最快 访问延迟极低 . 并行算法设计原则 虽然有高速的计算能力,但其自产生以来就是专门针对图形计算所设计 的,通用性远不及于,为了使亟待提升性能的应用计算能够移植到上 并且达到很好的效果,必须遵循一定的设计原则。 ..一般原则 最好处理大规模数据 首先,大的数据量对计算机缓存的作用要求较低,而对存储器带宽要求 较高;其次,大规模数据的格式都非常地统一,且一般按照大规模的矩阵存 储,使得数据划分变得很容易。这使得对数据处理的方式可以保持高 度一致。 对于数据规模非常小的数据来说,虽然并行计算可以带来一定的加速效第三 章多并行计算研究 果,但是由于连接主机端和设备端的总线的带宽限制,数据从 内存传输到存储器,以及计算结果从存储器传回主机内存,需要 消耗较多的时间,对总的时间计算影响较大,反而没有明显加速效果。 最好处理对运算精度要求不高的计算 当前大多数芯片仅支持单精度位浮点小数的运算,只有少 数的新产品开始支持双精度位浮点运算,而且这种支持并非是靠流处 理器来完成的。暂时无法支持非规范数字,并且与浮点运算能力可达到 位的相比,其位宽的寄存器对于浮点运算,计算能力要小很多。 因此对于一些特别要求计算速度,同时可以忽略部分计算精度的应用来说, 是一个很好的选择。但是基于设计的算法也要尽量避免由于精度 问题而带来的严重后果。 保证任务划分后的运算过程高度统一 利用计算时,都需要将一个完整的任务划分为许多个小型任务,而 且要保证中负责每个单元任务的线程束的运算过程高度统一,以避免 任务重合和程序等待。程序分支需要仔细考虑,代码执行过程中同一个线程 束内存在不同分支的情况应该尽量避免。这种线程束内的分支并不会使得程 序出错,但是会大幅度地降低效率。 ..性能优化建议 设计一个性能良好的算法,还需要开发人员针对不同的数据自己进行 一些优化,本文给出的优化建议主要有: 除了编程模型外,开发人员还必须了解底层架构的一些基本属性。最 重要的方面主要集中在,以单个线程性能为代价的吞吐量通过深层多线 程,以此透彻理解细粒度的并行性实现。其他重要的方面是线程束,线程 块中执行的角色?的执行只集中在数据的并行,而不是任务并 行和线程束的相关控制和缺少线程的专有局部存储器每个线程只有少量 的寄存器,就要求有效利用其他快速的局部存储器每个线程块中的共享 存储器,常数存储器和纹理存储器。 开发人员必须找到应用程序的数据结构对应于模型的有效映射。基于多并行 计算的高通量抗体序列比对研究 对于像数据结构一样的矩阵,这很简单。反向传播算法也提出了一个简单的 非结构化网格映射,但对于更复杂和不规则的有复杂的结构间接的应用程 序,会不直观。即使这样的应用程序也可表现出高度数据并行性。 开发人员必须认识到算法执行的数据局部性和内存访问模式,以便发 挥内存层次结构的优势。最重要的因素是局部的数据访问模式,线程 块的内部线程间的通信和的局部数据存储单元内。对于常用的访问,只 读的值被一个线程束共享,带缓存的常量存储器是一个不错的选择;每个线 程块共享存储器很小,但内存访问的延迟时间比全局存储器要低很多;考虑 到延迟和带宽,过多的访问全局存储器都是不可取的。很多程序的实 现几乎都使用了共享存储器。 对于大的,只读的数据结构,利用纹理缓存的优势将这些数据结构绑 定到纹理存储器上是很有用的。为了能够利用纹理缓存的优势,程序员需要 确保数据重用是局部的只在一个线程块中的线程之间,并且在一个线程 束的许多线程接触相同的缓存行。并且应尽可能的避免全局同步的开销,使 用指令可以对性能产生很大影响。 .多并行特点 . .. 最近公司发布的新版通用计算开发包 .为并行编程 加入了新特性和新功能,使并行编程变得更加容易,并且让研究人员可以把 更多 应用程序移植到平台上来,其中最重要的突破是让多程序开发变得更 简单【引。 .的主要特性包括: 简化并行程序移植多个线程共享??多个主线程能够在一个上 共享运行环境。 ?单线程访问多??一个主线程可以访问系统内的所 有。第三章多并行计算研究 ?非锁定的系统内存拷贝??系统内存地址可以直接映射给 ,不需要拷贝。 ?新的 /语言特性??能够提供一系列强大的开源 并行算法和数据结构。 ?模块化的语言库??与使用标准模板库以及线程 构件时相比,通过利用,并行排序等例程的速度可 提升至倍。 ?图像/视频处理库多层纹理 加速多编程 ? 统一虚拟寻址??能够提供给主机内存和显卡显存一个合并 的存储器地址空间。.实现点对点通信??支持一台服务器或工作 站内多之间的点对点通信。 改进后的新开发工具 ?自动性能分析 ?调试 ?为调试 ? 二进制的反汇编 ..多线程通信 在以前的多平台环境下,每个与内存之间可以直接进行数 据交换,但之间不能共享显存,并没有直接联系,当数据需要从一个 显存传送到另一个显存时,必须先将数据传送到主机内存,再从主机内存 传送到另一个显存。如图.所示,这种传输顺序可以描述为: ..。在桌面级应用中,一个程序往往只能调用某一个 核心,如果要驱动多个在同一系统内执行同一个任务,只有专业的并行编 程环境才能实现,所以多通信在以前的版本中需要付出较高的代价。