技术摘要：
本发明提出一种面向基因比对的细粒度并行负载特征抽取分析方法及系统。本发明抽取的这些负载特征着眼于设计细节，以较细的粒度来分析基因比对的应用，从而使得加速器的结构更具有针对性、效率更高。很多加速器设计均着眼于应用的整体层面，着重刻画应用的“粗粒度”的  全部
背景技术：
随着生物技术的高速发展，其日新月异的突破正在引发农业、医药等方面新一轮 的产业革命 ，将会深刻地改变未来人类社会的生产生活方式。而生物信息学 (Bioinformatics)是生物技术研究的必要手段和重大前沿领域之一，它是随着生命科学和 计算机科学的迅猛发展，生命科学和计算机科学相结合形成的一门新学科，通过综合利用 生物学，计算机科学和信息技术而揭示大量而复杂的生物数据所赋有的生物学奥秘。基因 测序技术作为探索生命奥秘的重要手段，已经成为了生物信息学研究的重要分支，在物种 鉴别、基因检测、疾病诊断等方面有着广泛的应用，基因测序技术的飞速发展为精准医疗奠 定了坚实的基础。 二代测序成本的不断下降导致测序数据爆炸式增长，而基因序列比对作为基因测 序的必要环节以及基因数据处理流程的性能瓶颈，其与测序仪之间的速度差距就成为了一 个重大的挑战。由于计算和访存方面的特殊特征，又由于现有处理器平台与应用特征之间 存在矛盾，比对应用在通用处理器上效率低下，需要设计一种新的定制化的结构，来满足这 种日益增长的性能和功耗的需求。现有的对基因比对应用加速的方法大都着眼于应用的整 体层面，刻画了应用的“粗粒度”的特征，而定制结构的设计最终还要落在细节上，只有将应 用更“细粒度”的局部特征发掘出来并与结构设计相匹配，才能更有针对性、更高效。
技术实现要素：
针对目前传统处理器的能力无法满足基因比对应用日益增长的需求，以及一些新 的定制化的专用加速结构设计主要着眼于应用的整体层面，只刻画应用的“粗粒度”特征， 加速效果有限的问题，本发明提出了基因比对应用中存在的一些共性的核心部分，称之为 “基准程序”，并深入基准程序的局部，找出其在计算和访存方面的细粒度并行模式，并给出 与之相应的并行结构设计的方案，用以指导后续的加速器结构设计。 针对现有技术的不足，本发明提出一种面向基因比对的细粒度并行负载特征抽取 分析方法，其中 步骤1、获取待分析的基因向量和对应的待执行的分析任务，该分析任务由多个子 任务构成，按顺序从该分析任务中选择子任务，作为当前任务； 步骤2、判断该当前任务是否属于计算任务，若是则执行步骤3，否则执行步骤4； 步骤3、通过并发数据通路对该基因向量执行该当前任务，得到该基因向量的子分 析结果； 步骤4、判断该当前任务是否属于中间数据的临时存储任务，若是，则为临时任务 数据提供向量寄存器和/或预取缓存，否则执行步骤5； 5 CN 111584011 A 说　明　书 2/9 页 步骤5、判断该当前任务是否属于对某一局部连续地址空间内的内存访问任务，若 是，则在片上存储器内缓存连续地址或采用多端口片上存储器对局部访存数据进行缓存， 否则执行步骤6； 步骤6、判定该当前任务属于指被访问的数据结构超出片上存储资源的大跨度访 存任务，利用片上缓存预取该数据结构或并行访问该数据结构，按顺序从该分析任务中选 择下一个子任务，作为当前任务，再次执行步骤2，直到执行子任务全部执行完毕，输出该分 析任务的分析结果。 所述的面向基因比对的细粒度并行负载特征抽取分析方法，其中该步骤2包括： 步骤21、构建基于FM-index索引的反向计数模块，该计数模块用于通过控制循环 迭代的条件确定目标碱基的区间位置；构建用于确定参考序列中目标碱基精确位置的位置 判定模块；通过逆补序列的反向计数构建正向计数模块。 所述的面向基因比对的细粒度并行负载特征抽取分析方法，其中该步骤2包括： 步骤22、通过调用该反向计数模块和/或位置判定模块和/或正向计数模块，为基 因向量的每个元素单独设计运算器，并行完成该计算任务中的映射操作；通过调用该反向 计数模块和/或位置判定模块和/或正向计数模块，以树状结构实现基因向量归约，并发完 成该计算任务中的归约操作；通过调用该反向计数模块和/或位置判定模块和/或正向计数 模块，以为基因向量的每对元素单独设计运算器，并行完成该计算任务中的组合操作；通过 调用正向计数模块，以上层的并行分支以及下层的并行汇合构成的，每一层都通过不同功 能单元实现操作的并发结构，并行完成该计算任务中的分支-汇合操作；通过调用正向计数 模块，以定制的数据通路替代软件实现的指令开销和中间数据存取开销，并行完成该计算 任务中的链式操作。 所述的面向基因比对的细粒度并行负载特征抽取分析方法，其中该步骤2包括： 步骤23、通过调用该反向计数模块和/或位置判定模块和/或正向计数模块，按位 存储该基因向量，并行调整基因向量每一位的索引值，完成该计算任务中的双向移位操作； 通过调用该反向计数模块和/或位置判定模块，利用寄存器直连，直接在向量寄存器中按位 取出所需元素并送至相应位置进行处理，完成该计算任务中的按位取值操作；通过调用该 反向计数模块和/或位置判定模块和/或正向计数模块，将索引之后的所有碱基都转换为一 个固定碱基值，然后进行并发的Rank数据处理，最后从处理结果中减去该固定碱基值的累 计值，完成该计算任务中的边界掩藏操作。 所述的面向基因比对的细粒度并行负载特征抽取分析方法，其中该基因向量为经 过BWT算法压缩的向量。 本发明还提出了一种面向基因比对的细粒度并行负载特征抽取分析系统，包括： 模块1、获取待分析的基因向量和对应的待执行的分析任务，该分析任务由多个子 任务构成，按顺序从该分析任务中选择子任务，作为当前任务； 模块2、判断该当前任务是否属于计算任务，若是则执行模块3，否则执行模块4； 模块3、通过并发数据通路对该基因向量执行该当前任务，得到该基因向量的子分 析结果； 模块4、判断该当前任务是否属于中间数据的临时存储任务，若是，则为临时任务 数据提供向量寄存器和/或预取缓存，否则执行模块5； 6 CN 111584011 A 说　明　书 3/9 页 模块5、判断该当前任务是否属于对某一局部连续地址空间内的内存访问任务，若 是，则在片上存储器内缓存连续地址或采用多端口片上存储器对局部访存数据进行缓存， 否则执行模块6； 模块6、判定该当前任务属于指被访问的数据结构超出片上存储资源的大跨度访 存任务，利用片上缓存预取该数据结构或并行访问该数据结构，按顺序从该分析任务中选 择下一个子任务，作为当前任务，再次执行模块2，直到执行子任务全部执行完毕，输出该分 析任务的分析结果。 所述的面向基因比对的细粒度并行负载特征抽取分析系统，其中该模块2包括： 模块21、构建基于FM-index索引的反向计数模块，该计数模块用于通过控制循环 迭代的条件确定目标碱基的区间位置；构建用于确定参考序列中目标碱基精确位置的位置 判定模块；通过逆补序列的反向计数构建正向计数模块。 所述的面向基因比对的细粒度并行负载特征抽取分析系统，其中该模块2包括： 模块22、通过调用该反向计数模块和/或位置判定模块和/或正向计数模块，为基 因向量的每个元素单独设计运算器，并行完成该计算任务中的映射操作；通过调用该反向 计数模块和/或位置判定模块和/或正向计数模块，以树状结构实现基因向量归约，并发完 成该计算任务中的归约操作；通过调用该反向计数模块和/或位置判定模块和/或正向计数 模块，以为基因向量的每对元素单独设计运算器，并行完成该计算任务中的组合操作；通过 调用正向计数模块，以上层的并行分支以及下层的并行汇合构成的，每一层都通过不同功 能单元实现操作的并发结构，并行完成该计算任务中的分支-汇合操作；通过调用正向计数 模块，以定制的数据通路替代软件实现的指令开销和中间数据存取开销，并行完成该计算 任务中的链式操作。 所述的面向基因比对的细粒度并行负载特征抽取分析系统，其中该模块2包括： 模块23、通过调用该反向计数模块和/或位置判定模块和/或正向计数模块，按位 存储该基因向量，并行调整基因向量每一位的索引值，完成该计算任务中的双向移位操作； 通过调用该反向计数模块和/或位置判定模块，利用寄存器直连，直接在向量寄存器中按位 取出所需元素并送至相应位置进行处理，完成该计算任务中的按位取值操作；通过调用该 反向计数模块和/或位置判定模块和/或正向计数模块，将索引之后的所有碱基都转换为一 个固定碱基值，然后进行并发的Rank数据处理，最后从处理结果中减去该固定碱基值的累 计值，完成该计算任务中的边界掩藏操作。 所述的面向基因比对的细粒度并行负载特征抽取分析系统，其中该基因向量为经 过BWT算法压缩的向量。 由以上方案可知，本发明的优点在于： 本发明抽取的这些负载特征着眼于设计细节，以较细的粒度来分析基因比对的应 用，从而使得加速器的结构更具有针对性、效率更高。很多加速器设计均着眼于应用的整体 层面，着重刻画应用的“粗粒度”的特征，而定制结构的设计最终还是要落在细节上。此外， 这些细粒度的负载特征常常出现在多个基准程序或者应用软件中，本文对这些“共性”部分 进行归纳和抽象，对并行模式相同的特征给出统一的设计方案指导，这在一定程度上也提 升了结构设计方法的通用性。 7 CN 111584011 A 说　明　书 4/9 页 附图说明 图1是“映射”模式(a)程序片段示例和(b)并行结构图； 图2是“归约”模式(a)程序片段示例和(b)并行结构图； 图3是“组合”模式(a)程序片段示例和(b)并行结构图； 图4是“分支-汇合”模式(a)程序片段示例和(b)并行结构图； 图5是“链式”模式(a)程序片段示例和(b)并行结构图； 图6是“双向移位”模式(a)程序片段示例和(b)并行结构图； 图7是“按位取值”模式(a)程序片段示例和(b)并行结构图； 图8是“边界隐藏”模式(a)程序片段示例和(b)并行结构图； 图9是“中间寄存”模式及其结构图； 图10是小范围访存模式说明图； 图11是小范围访存并行结构图。