GATK软件pairhmm算法FPGA加速（altera arria 10芯片 xilinx Kintex ultrascale ku115芯片） 硬件负责人 2017.9 - 2018.9

GATK是MIT博德研究所研发的基因数据挖掘的软件套件。其中pairhmm算法部分是一个计算密集型的矩阵运算。据统计，针对肿瘤基因数据，原版软件该部分耗时占总耗时约90%.该算法经过FPGA加速以后，速度提升了42倍。成果得到了北京吉因家公司的认可。本人主要工作如下： （原版66.73h fpga 8channelpu16 96min）

• 使用对角线计算方式，并采用流水线结构。多通道并行加速核心计算部分
• 使用多级分发结构将数据分发至每个通道。达到高度并行计算的效果
• 设计与PC端的传输协议（传输接口为PCIE，使用DDR4作为一个ring buffer，核心算法模块使用AXI4接口操作DDR4）
• 负责整个从altera平台迁移至xilinx平台的移植工作

设计亮点：

• pairhmm用于计算两条序列的比对情况的似然概率,输入是一条参考基因序列称为halotype以及一条实际基因序列称为read。由AGCT组成。read的每一个碱基都会对应一组共4个质量信息。分别标志碱基的错误概率，插入概率与删除概率

难点：

• 如何充分的使用板上资源，开辟更多的通道，通道开多了以后，由于资源有限，布线紧张，时序常常不通过，这个时候需要各种策略去改善时序。包括更改实现策略，对关键路径进行多级寄存器处理。减小组合逻辑。复制关键寄存器。比如状态机。
• 工程太大一次编译的时间太久，最高长达9个小时
• 调试的困难，因为必须使用各种各样的数据进行测试，仿真的局限性太大。所以必须上板测试。经常在测试的时候卡死在一个数据计算到几个小时的时候。所以定位难度很大。而且中间出现很多卡死的问题并不是因为当时那个数据的问题。而是前面计算的数据有问题在FPGA内部造成了一些残留。影响到了下一个正常数据的计算。

pairhmm硬件版本移植华为云FPGA服务器 （平台华为云vu9pFPGA云服务器）主要负责人 2018.9 - 2018.12

将上一个工程移植到华为云的vu9pFPGA云服务器的DPDK平台。在华为云FPGA套件开发人员的大力支持下成功移植。依托华为云的VU9P平台丰富的资源将计算通道数成功提升了3分之一。本人主要工作如下：

• 使用华为云提供的FPGA开发套件进行开发
• 外部接口逻辑大幅修改适配华为云FPGA套件提供接口
• 配合华为云FPGA套件开发人员在调试过程中找出了一些华为云FPGA套件代码中的小bug （什么bug？）

smith-waterman算法FPGA加速 （xilinx Kintex ultrascale ku115芯片 ）硬件负责人 2019.1 - 至今

是一种进行局部序列比对（相对于全局比对）的算法，用于找出两个核苷酸序列或蛋白质序列之间的相似区域。其本质还是矩阵运算。FPGA加速以后的运算速度与纯软件在相同CPU下满负荷运行速度相比提升了20倍。本人负责所有FPGA模块开发主要工作包括：

• 继承并修改paihmm FPGA版本的数据传输模块
• FPGA核心运算模块设计
• 软硬件联调

叙述顺序：

GATK算法是生物业界非常成熟的基因分析套件。pairhmm算法是其中非常重要的一步。用来计算两个基因序列的匹配最大似然概率。该算法是一个浮点矩阵运算。计算密集型。在原软件中大概占50%以上的耗时，对于肿瘤基因数据而言，耗时更多。所以我们决定在FPGA上对该部分进行加速
总体介绍。整个工程的工作流程是由PC通过PCIE接口传输数据到FPGA，然后FPGA使用数据进行计算，然后通过FPGA回传计算结果。

具体来说，整个工程划分分为PC与FPGA通信模块，数据分发模块，核心算法模块，结果回传模块。

通信模块

PC与FPGA通信模块中。我主要用xilinx提供的PCIE-DMA IP管理接口。然后一个4GByte的DDR4作为buffer。我们再该buffer内部划分出了两块1Gbyte的区域作为ringbuffer用于数据下行和数据上行。PC通过xilinx官方提供的API可以向DDR内写入数据或者读取数据。FPGA片上逻辑通过AXI接口对DDR进行访问。

数据解析分发模块

当PC向DDR发送数据后，片上的数据分发模块会读取DDR中的待处理数据然后进行解析，将源数据包解析为。并发送到8个不同的计算通道。使8个计算通道可以并行计算。

核心计算模块

核心算法模块包含控制模块和计算模块。一个控制模块功能是接收分发的一个矩阵数据并对该矩阵的计算过程进行全程控制。计算模块接受控制模块发出的数据进行计算，一个计算模块的基础计算单元简称为PE每12个周期可以计算出矩阵中一个点的值。根据这个特点。采用流水线结构。一个PE可以同时计算12个矩阵。所以每个计算通道。都可以同时计算12个矩阵。也就是整个系统可以同时计算12x8=96个矩阵。然后根据该算法的特点可以采用伸缩阵列的方法，将计算复杂度由m*n降为m+n。

回传模块

计算出来的结果逐级上传。最后汇总然后存入DDR的上行区域。然后PC将数据可以直接取走。

难点：

• 接口：对我来说PCIE-DMA，DDR4，AXI4的调试相当费工夫。先仿真。然后再上板。我们是在xilinx提供样例的基础上进行修改。然后一步步调试

• 提升速度：提升速度可以分三步走，一是从逻辑层面做优化，提升单通道性能。这里我们采用了Systolic Arrays（收缩阵列）流水线：实现计算模块内部的流水线。。二是充分利用片上资源，尽可能多的铺设通道，但是资源消耗上去以后，布线紧张，时序很难收敛。这里需要采用优化时序的各种方法（缩短关键路径，减小扇出，采用不同的实现策略）这里消耗了大量的时间。因为实现一次消耗大量时间。三是提升频率，实际上资源消耗很多以后，频率很难往上再提。这里我们为了达成目标，将核心计算模块的频率提升，然后将数据传输模块的频率降低。使用异步FIFO来做跨异步处理.提升到了250Mhz

• 调试很难： 基因数据多种多样，每一个数据包的长度以及内容都会有所不同，而且跑完一个完整的数据包需要的时间很长，有时候会卡在运行到几个小时的位置，所以排查起来耗时费力。需要事先分析几个可能卡住的位置，然后使用在线调试，设置触发条件去一个个检查，直到找到解决办法为止

频率的提升，和片上资源的充分利用（最高跑到250Mhz,回传模块使用100Mhz）,如何让implementation的时序过关。
采用过的方法：尝试各种实现策略。（本地采用perfomance explore 华为云采用 Net_delay_low）
复制寄存器，以及组合逻辑中间添加寄存器。都是采用过的手段。

实际上我的第一个项目隶属于我们实验室所做的一个大项目。即下一代基因测序分析加速。目前流行的基因分析套件是GATK。该套件将测序仪测得的片段基因匹配到参考基因序列上去。然后通过计算得到测试基因可能存在的变异位点。从而找出测试人基因中可能存在的变异。然后医生根据测试结果即可使用特定靶向药。所有该技术对精准医疗有极大的意义。但是目前的GATK存在的一个问题就是计算速度太慢。原版软件做一个癌症分析，需要70小时左右。其中百分之80的时间是耗费在了pairhmm算法这一步。然后这一步算法主要是计算两条基因序列的极大似然概率，如果输入基因序列长度为m，参考基因序列长度长度为n,那么我们就需要完成m*n轮计算。而且每一轮计算都包含了12次浮点运算。所以这个计算量相当大。

经过加速后

这12次的浮点运算按照计算的先后顺序，可以分为2步完成。按照我们对浮点运算器的配置，这两步计算一共需要12个周期来完成

8_channel_code_PU16.png

图像畸变IP设计

应用场景是VR显示。我们的芯片是一个VR硅基OLED驱动芯片。如果我们的芯片在安装的时候出现些许偏差。当然这个偏差不会很大。但是少许的偏差就会导致图像出现畸变。那么我们的IP就是要对这个畸变做一个补偿。输入是4个控制点的原坐标以及补偿以后的4个控制点坐标。
为了实现这个IP我将开发阶段分了三个步骤。
第一个步骤是算法验证。首先高级语言验证算法的正确性。这一步我是在MATLAB上完成的。因为后面的双线性插值步骤涉及到小数处理。这里我们采用定点数来处理小数。最终经过反复的测试使用了两套定点化的方案，其中一个是12，有两个数使用了18来表示。在这个定点化的方案下，实现的效果和浮点实现的效果一致。算法验证的最后阶段是使用投影仪做实际验证。先调整投影仪的角度，使投影仪投射一个畸变的图像。然后通过我们的MATLAB平台处理一张补偿后的图片。然后通过投影仪去显示。最终投影仪显示的是一个完好的图像。这一步也已完成

难点：

1.除法器的实现：
我最终选择的方式是使用查找表的方式来将除法转化为乘法。根据测试我们发现。除数的范围是在0.875-1.25之间。然后我们采用的定点精度是用12位来表示小数。所以如果用完整的表来实现需要1024+512个表项。这个开销不小。为了减小表的大小。我们采用了插值法。把每个表项之间的间距为8.然后通过插值实现间距为1的效果。

2. Line Buffer的实现
   给我的是一个单读端口RAM。但是双线性插值需要一个插值点周围4个pixel的灰阶。那么如何实现一个周期内获得4个点的坐标是一个具有挑战性的问题