对基于随机上下文无关文法的RNA二级结构预测进行加速的方法

摘要

本发明公开了一种对基于随机上下文无关文法的RNA二级结构预测进行加速的方法，目的是加快使用SCFG进行RNA二级结构预测的速度。技术方案是先构建由主机和可重构算法加速器组成的异构计算机系统，接着主机将格式化后的CM模型和编码后的RNA序列发送至可重构算法加速器，可重构算法加速器的PE阵列执行无回溯CYK/inside算法计算，计算中采用“按区域分割”和“逐层按列并行处理”的任务划分策略实现细粒度并行计算，且n个PE采用SPMD方式同时计算位于矩阵不同列的n个数据，但计算时根据不同的状态类型采用不同的计算顺序；采用本发明实现了对基于SCFG模型的RNA序列二级结构预测应用加速，加速比高，成本低。

主权项

一种对基于随机上下文无关文法的RNA二级结构预测进行加速的方法，其特征在于包括以下步骤：第一步，构建由主机和可重构算法加速器组成的异构计算机系统，主机是一台个人计算机，可重构算法加速器与主机相连，主机上安装有多序列比对程序、CM模型构建程序、CM模型解析程序、可重构算法加速器逻辑下载程序和数据通讯程序；主机通过JTAG编程电缆对可重构算法加速器进行配置，将RNA序列和CM模型通过PCI-E接口加载至可重构算法加速器，并启动可重构算法加速器；可重构算法加速器完成无回溯的CYK/inside算法的计算，将比对结果返回给主机；可重构算法加速器由算法FPGA、动态存储器DRAM和PCI-E接口组成：DRAM与算法FPGA相连，用于存储原始数据-RNA序列和CM模型及中间状态的计算结果，PCI-E接口连接主机与算法FPGA；算法FPGA的JTAG配置端口通过JTAG编程电缆与主机相连，主机通过JTAG编程电缆对算法FPGA进行逻辑配置；算法FPGA与DRAM和PCI-E接口相连，算法FPGA从PCI-E接口接收数据和操作命令，并对操作命令进行解析：如果是数据写命令，将从PCI-E接口接收的数据存储在DRAM中；如果是启动命令，执行无回溯的CYK/inside计算，将计算结果存储在DRAM中并向主机返回计算完成信号；如果是数据读命令，将计算结果从DRAM中读出并通过PCI-E接口发送给主机；算法FPGA由IO接口控制器、DRAM存储控制器、PE阵列控制器、PE阵列、PE同步与写回控制器组成：IO接口控制器对外与PCI-E接口相连，对内与DRAM存储控制器、PE阵列控制器相连，IO接口控制器从PCI-E接口接收原始数据即CM模型和RNA序列，并向DRAM存储控制器发出数据写请求，将原始数据通过DRAM存储控制器写入DRAM；数据存储完成后，IO接口控制器将数据准备好信号发送给PE阵列控制器；IO接口控制器接收主机发出的启动命令，并转发给PE控制模块，启动PE阵列；计算完成后，IO接口控制器接收主机发出的的数据读命令，通过DRAM存储控制器将序列比对得分从DRAM中读出，通过PCI-E接口送回主机；DRAM存储控制器对外与DRAM相连，对内与IO接口控制器、PE阵列控制器、PE阵列、PE同步与写回控制器相连，它接收来自IO接口控制器的数据写请求，将原始数据写入DRAM；接收来自PE阵列控制器的数据读请求，将RNA序列从DRAM读出并发送至PE阵列；接收来自PE阵列的CM模型和数据读请求，将CM模型当前状态信息和计算所需的操作数从DRAM读出发送给PE阵列；接收来自PE同步与写回控制器的写请求，将由PE阵列产生的数据写回DRAM；PE阵列控制器与IO接口控制器、DRAM存储控制器、PE同步与写回控制器和PE阵列相连，它从IO接口控制器接收数据准备好信号后启动PE阵列，PE阵列控制器向DRAM存储控制器发数据读请求，使PE阵列从DRAM获得RNA序列；PE阵列控制器通过控制当前计算元素的下标i，j，k的值实现PE阵列的初始化并对三维矩阵M实施按列循环分配和对列元素实现由上至下或者由下至上的计算；PE阵列控制器在收到PE同步与写回控制器发出的PE同步与写回完成信号后产生PE控制信号，为PE阵列分配新的计算任务，更新PE计算元素的i，j，k，启动下一列元素的计算；PE同步与写回控制器与PE阵列和DRAM存储控制器相连，它根据当前元素的下标i，j，k判断PE的计算是否终止；当某个PE完成本列元素的计算后，PE同步与写回控制器控制该PE进入同步等待状态，并接收该PE发出的数据写回请求，按照先请求先服务的原则将PE阵列存储在数据缓存区中的计算结果读出，通过DRAM存储控制器写回DRAM；写回操作完成后，PE同步与写回控制器向PE阵列控制器发出同步与写回完成信号；PE阵列负责三维动态规划矩阵的并行计算，它由n个PE、n个数据传递寄存器组和n个数据缓存区构成，n为正整数，每个PE都有一片存放计算结果的数据缓存区，每个PE都与DRAM存储控制器、PE阵列控制器、PE同步与写回控制器相连，相邻PE之间通过一个数据传递寄存器组相连；n个PE串联构成线性阵列，第一个PE为主PE，其他PE都是从PE，称为第1从PE，第2从PE，...，第n-1从PE，只有主PE向DRAM存储控制器发送数据读请求，从PE都被动地从DRAM存储控制器接收数据；每个数据传递寄存器组与左右相邻的PE模块相连，最后一个数据传递寄存器组连接第n-1从PE和主PE，可以同时被本PE和下一个PE访问，用于缓存从前一个PE的数据缓存区中读出的数据；所有PE的数据缓存区都与PE同步与写回控制器相连，被本PE和下一个PE访问；PE由PE控制模块、分值计算模块、RNA序列存储器、CM模型存储器组成：分值计算模块对外与该PE的数据缓存区相连，从数据缓存区中读出当前状态的子状态数据，按照无回溯CYK/inside递归公式实现对三维动态规划矩阵元素的计算，并将计算结果写入数据缓存区；分值计算模块对内与CM模型存储器和PE控制模块相连，它从CM模型存储器中读出CM模型当前状态信息，从PE控制模块或者从数据缓存区中读出计算所需的子状态数据，写入分值计算模块内部的状态寄存器中；分值计算模块由结束状态计算模块、非分支状态计算模块和分支状态计算模块三个子模块构成，分别实现结束状态、非分支状态和分支状态层的计算；三个子模块彼此独立，但都与数据缓存区、CM模型存储器和PE控制模块相连；RNA序列存储器与PE控制模块和CM模型存储器相连，存储经过二进制编码后的RNA序列；CM模型存储器与RNA序列存储器和分支计算模块相连，存储CM模型当前状态下的相关信息，包括当前状态的类型Stype、编号State_id、最后一个父状态的类型P_last、父状态数量P_num、第一个子状态的类型C_first、子状态数量C_num以及RNA字符的生成概率ek和转移概率tk；PE控制模块对外与IO接口控制器、DRAM存储控制器和数据传递寄存器组相连，它接收IO接口控制器发出的启动命令，启动PE的计算；计算时通过DRAM存储控制器访问DRAM，读回CM模型、RNA序列及中间结果；如果当前状态为匹配、右插入和右匹配，PE控制模块还将访问前一个PE的数据缓存区，从数据传递寄存器组读回返回的数据；PE控制模块对内与RNA序列存储器、分值计算模块和PE同步与写回控制器相连；PE控制模块是一个控制状态机，负责控制PE的初始化、数据载入、分值计算、数据同步以及数据写回和缓存区数据替换；主机对算法FPGA的逻辑进行综合，生成配置文件，并通过JTAG编程电缆对算法FPGA进行配置，配置过程结束后，算法FPGA自动复位，可重构算法加速器进入正常工作状态，等待主机发出操作指令；第二步，主机使用多序列比对程序和CM模型构建程序将输入的一组同源RNA序列转换为CM模型，然后使用模型解析程序对CM模型进行格式化，并将格式化后的CM模型通过PCI-E接口发送至可重构算法加速器，可重构算法加速器将接收的CM模型存储在DRAM中；第三步，主机对输入的RNA序列进行二进制编码，使用2位二进制数00、01、10、11对RNA序列中的A、C、G、U字符进行编码，并将编码后的序列发送至可重构算法加速器的DRAM；第四步，主机向可重构算法加速器发送启动命令，启动算法FPGA，主机进入等待状态；算法FPGA接收到启动命令后启动PE阵列执行无回溯CYK/inside算法计算，计算过程包括以下步骤：4.1PE初始化，算法FPGA在收到主机发出的启动命令后，立即启动PE阵列的初始化过程，具体步骤如下：4.1.1所有PE在各自的数据缓存区中选择编号最小的一个空闲区域保存计算结果；4.1.2主PE通过DRAM存储控制器从DRAM中读出RNA序列，并将RNA序列发送至所有从PE，从PE接收RNA序列并存储在各自的RNA序列存储器中；4.1.3所有PE根据各自在PE阵列中的编号为将要计算的元素下标赋初始值：i＝P_id，j＝P_id，k＝K；i，j，k为元素在三维矩阵中的坐标，P_id为PE的编号，其中主PE的P_id＝1，从PE的P_id为2～n之间的整数，K为CM模型中的状态数量同时也是矩阵最底层的编号，n为PE的数量；4.2数据载入：各PE根据当前状态的类型将操作数载入分值计算模块，一共分为五种情况：●如果当前状态类型为S、D、IL、ML，则PE分值计算模块从该PE的数据缓存区中载入当前状态的所有子状态数据层中的第j列元素；●如果当前状态类型为分支状态，且P_id＝1，则PE从以下两个位置获得计算所需的操作数：1)从本地数据缓存区中载入分支状态右子状态层的第j列元素；2)向DRAM存储控制器发读请求，从DRAM中载入分支状态左子状态层的第i行元素，并将其广播至所有PE；●如果当前状态类型为分支状态，且2≤P_id≤n，则PE从以下两个位置获得计算所需的操作数：1)从本PE数据缓存区中载入右子状态数据层的第j列元素；2)等待接收主PE从DRAM中载入的左子状态数据层的第i行元素；●如果当前状态类型为IR、MR或者MP，且P_id＝1，则PE向DRAM存储控制器发读请求，从DRAM载入当前状态的所有子状态数据层的第j-1列元素；●如果当前状态类型为IR、MR或者MP，且2≤P_id≤n，则从前一个PE的数据缓存区中载入当前状态的所有子状态数据层的j-1列元素；4.3计算比对得分4.3.1对三维矩阵按状态层方向进行纵切，将其垂直分割为s个区域，s＝[L/n]，L为RNA序列的长度，每一个区域仍是一个三维矩阵，每个区域都包含K层，每一层包含n列元素；然后对每一个区域逐层计算：从第1个区域的第K层出发，当第K层计算完成后再算第K-1层，直到第1个区域的第1层算完，然后再计算第2个区域的第K层，第K-1层，...，第1层；之后再计算第3个区域...，直到最后一个区域的第1层算完；对每一层的计算而言，每个PE负责计算当前状态层中的一列，PE计算的元素的列号与PE在阵列中的序号P_id对应；主PE的编号P_id＝1，负责计算本区域第1列元素，从PE计算本区域的第2～n列元素；4.3.2阵列中的n个PE采用单程序多数据流方式同时计算位于矩阵不同列的n个数据，PE都使用无回溯CYK/inside算法的迭代公式对矩阵元素进行计算，但计算时根据不同的状态类型采用不同的计算顺序，方法是：4.3.2.1如果当前状态k是分支状态，则每一个PE都从各自列的顶部位置开始按照由上至下的顺序计算：当前状态层的计算启动时，主PE计算元素(1，j)，第1从PE计算元素(1，j+1)，...，第n-1从PE计算元素(1，j+n-1)，j为元素在矩阵中的列坐标，1≤j≤L；当第1行的n个元素计算完之后，所有PE同时更新元素的横坐标，计算下一行的n个元素；每一个PE由上至下串行计算本列元素，整个PE阵列每次完成本状态层中的一行元素的计算；当一个PE计算的元素坐标i＝j时，PE计算暂停，进入等待状态；由于三角矩阵每一列元素的个数不等，PE按编号顺序依次进入同步等待状态，直到收到最后一个从PE的计算完成信号；4.3.2.2如果当前状态k是非分支状态，则每一个PE都从各自列的底部位置开始，按照由下至上的顺序计算：当前状态层的计算启动时，所有PE计算的元素都位于三角矩阵的主对角线上：主PE计算元素(i，j)，第1从PE计算元素(i+1，j+1)，...，第n-1从PE计算元素(i+n-1，j+n-1)，1≤i≤L，i≤j≤L；当前对角线上的n个元素计算完之后，所有PE同时向上移动一个计算位置，主PE计算元素(i-1，j)，第1从PE计算元素(i，+1)，...，第n-1从PE计算元素(i+n-2，j+n-1)；当PE计算的元素行坐标i＝1时，PE计算暂停，PE按编号顺序依次进入同步等待状态；当一列元素计算完成后如果需要写回，则直接发出写回请求；4.4所有PE的列元素计算结果都保存在PE各自的数据缓存区中，PE根据状态类型确定是否将数据写回DRAM：4.4.1如果当前状态是分支状态的左子状态，则所有PE都将计算结果写回DRAM；4.4.2如果当前状态是匹配、右插入或者右匹配状态，则只有最后一个从PE将计算结果写回DRAM，其它PE的计算结果都保存在各自数据缓存区中；4.5对各PE进行同步；4.6加载新任务：当每个PE都收到第n-1从PE的计算完成信号时，PE阵列控制器将本区域中的下一个状态层加载至PE阵列，为每一个PE分配新状态层中的一列元素，即为变量i，j，k赋值：如果k＞0，则i＝P_id，j＝P_id，k＝k-1，载入CM模型的第k-1行数据；否则，i＝P_id，j＝j+n，k＝K，载入CM模型的第K行数据，随后PE控制状态机进入结束条件判断状态；如果j＞L，则转4.7进入结束状态，否则在数据缓存区寻找一个新的编号最小的空闲区域，然后转4.2；4.7当所有PE都进入结束状态后，主PE将最终的计算结果M(1，L，1)的值写回DRAM，算法FPGA向主机发计算完成信号，PE计算过程结束；PE控制模块将所有寄存器清0，回到开始状态，等待主机发新的启动命令；第五步，主机接收到可重构算法加速器返回的计算完成信号后通过PCI-E接口向可重构算法加速器发数据读命令，算法FPGA接收数据读命令将计算结果从DRAM中读出，通过PCI-E接口转发给主机，RNA序列比对过程结束。