LJgibbs · 2020年04月23日

以SM3算法为例,构建一个软硬协作算法加速器:性能分析与优化

衡量一款 ASIC 芯片可以从 PPA 三个角度进行。

PPA 指的是: Power/Performance/Area,功耗 / 性能 / 面积。

衡量 FPGA 设计同样可以参照 PPA,但又有所不同。

除非是专门针对功耗的优化,一般设计优化主要考虑的是 LUT / FF 等芯片资源使用情况(面积)以及应用的工作频率以及延迟(性能)。

就加速器而言,还会有一项指标:加速比。加速比参考对象一般是使用冯诺依曼架构的通用 CPU 或者 GPU。

SM3 性能指标

具体到 SM3 加速器的性能指标,我们可以将指标设定为消息吞吐量消息处理延迟以及相比于通用处理器运行高效 SM3 软件算法时的加速比

消息吞吐量 \= 消息比特长度 / 消息处理时间 (bit/s 或 bps)
消息处理延迟 = T 消息完成时间 - T 消息开始处理时间
加速比 = T 加速器上消息运算时间 / T 处理器软件消息运算时间

以本系列上一篇文章中提及的设计为例,假设其工作在 125 Mhz 的时钟下,假设处理一个消息的时钟周期为 64 个,那么系统的吞吐为

512b / (8ns * 64) = 1000Mbps

减少消息处理延迟

实际上基于 FPGA 的 SM3 设计本身就有低延迟的优势。相较于 CPU 或者 GPU 架构,基于指令集以及缓存机制的冯诺依曼架构,无指令的 FPGA 可以直接对输入消息进行处理并输出,系统的延时只会用于处理消息而不是用于指令或者缓存系统。FPGA 处理一个消息块的延迟可以低于 us 级别。

在设计中可以在延迟,吞吐,面积之间权衡。

比如在上一篇的开源实现中,消息填充模块以 512b 消息块为单位,在填充完成后,再将整个消息块输出。这样做减少了处理的复杂度,减少了逻辑面积。但在缓存块的过程中,会使系统增加 512/32 = 16 个周期延迟。

我们会在后续的文章中进一步讨论延迟相关的设计。

提升消息吞吐量

吞吐量是处理系统的关键指标,具体到 SM3 算法中,提高吞吐量有两种主要的途径

  • 优化算法硬件实现架构

我们可以根据算法的特点,通过优化实现架构来提高算法加速器的吞吐。一般架构的更改提高吞吐量是以增大面积作为代价。有以下两种主流的方法

1.实现流水线结构

部署 64 个实现单元,每个周期输入一个消息块。每个时钟周期, 64 个处理单元都处于工作状态。并能在每个周期输出一个消息块的哈希杂凑值,这样一来吞吐量会到一个大得恐怖的量级,那么代价是什么呢?电路的面积会非常大,其实功耗也会非常高。

2.逻辑展开

标准中,每一个消息块需要进行 64 轮迭代,每轮迭代处理一组输入。相邻轮迭代的输入之间没有依赖关系。所以可以通过复制一组处理逻辑,在每轮迭代中处理两组输入,将一个消息块的迭代周期降到 32 个,从而提升吞吐量。

理论上也可以把 64 轮逻辑全部展开到一个周期.... -\_-||

  • 提高系统工作频率

想要提高系统的工作频率,关键在于找出设计中的关键路径,并想办法缩短。关键路径指的是设计中两个触发器之间最长的组合逻辑路径。关键路径的长度决定了系统的工作频率。系统的工作周期不能小于关键路径。

优化关键路径的方法有几种:

通过寄存器进行调整,比如插入寄存器到组合逻辑之间,打断组合逻辑;比如平衡多个寄存器之间组合逻辑路径,减少关键路径长度等。

但这些方法的使用在 SM3 这样的周期迭代应用中受限。SM3 需要进行 64 轮迭代,每个周期迭代一次。如果在其中插入寄存器,会使处理周期增加。增加延迟的同时,增加的处理周期可能会抵消降低关键路径长度带来的吞吐提升。

调整综合和布局布线策略,优先对关键路径进行优化;这类和工具相关的优化作者也有使用,但对其中的原理和窍门还不太了解,将在后续的文章中讨论。

对关键路径上的组合进行优化,比如针对 SM3 算法的计算特点,优化算法运算微架构,如使用 CSA 替换路径中的加法器,减少一级加法器从而缩短路径;常量 Tj 在每轮迭代时循环移位,可以用 ROM 存储常量 Tj 每轮循环移位后的值,每轮迭代时使用查表法更新常量,减少循环移位带来的延迟,

结语

本文讨论了 SM3 加速器的性能指标以及提升吞吐等性能的策略。

后续文章中将详细讨论如何通过优化算法实现架构和提高工作频率等方法来提升吞吐。在下一篇文章中将讨论如何使用 CSA 加法器降低关键路径延迟,从而提升频率和吞吐。

推荐阅读
关注数
10605
内容数
562
FPGA Logic 二三事
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
安谋科技学堂公众号
关注安谋科技学堂
实时获取安谋科技及 Arm 教学资源
安谋科技招聘公众号
关注安谋科技招聘
实时获取安谋科技中国职位信息