同态加密算力开销如何弥补？港科大提出同态加密算法硬件加速方案( 三 ) 机器之心专栏作者：杨照雄、

由图一所示，蒙哥马利模乘算法由内外两重循环构成，我们将单次内部循环操作封装为如图三所示的处理单元，每个处理单元中包含两个乘法器，分别用于计算x*y和q*m ，两个乘法结果与外层循环的上一轮计算结果

文章图片
以及进位（图中未画出）执行加法操作。同时，为了避免HLS编译代码展开循环后，造成乘法器资源大幅膨胀，需要使用ALLOCATION指令将处理单元的个数限制为1个。

文章图片
图三：算法1内部循环处理单元。

文章图片
图四：Karatsuba快速乘法。
在处理单元的设计中，同时采用了Karatsuba算法，如图四所示。根据乘法运算的原理，容易看出，乘法运算操作数的位宽减半，则总计算时间将减少至原先的四分之一左右。 Karatsuba算法将整数乘法拆分为了三个位宽仅为原来一半的整数乘法，从而节省了计算时间。根据该算法的原理，可以相应地使用DSP资源例化出所需的乘法器。
在RAM的使用方面，不难注意到，用于加密的输入数据大多是由浮点数编码而成的，与大整数位宽相比，其有效数字很少。因此，可以将输入数据存储为稀疏向量，即只记录非零元素和它们的索引，减少存储占用。
时序分析
时序分析在FPGA开发中的重要性，丝毫不亚于对算法的优化以及逻辑资源的分配。从电路的角度简单来说，如果没有合理的逻辑设计和资源布局，不仅会使得信号传递时间过长，还有可能出现多组信号争抢相同硬件资源，导致局部堵塞的问题。
通常来说，开发者可操控的最小粒度的FPGA工作时间为一个时钟周期，而FPGA完成一个时钟周期所需的时间由时钟频率决定，即

文章图片
因此，在降低时钟周期数的同时提高时钟频率，是提升FPGA运算性能的有效手段。
一般来说，实现一套算法所需要的时钟周期数由其关键路径所决定，所谓关键路径，就是工作流程中，时间延迟最大的一条路径。通过观察蒙哥马利模乘运算的两重循环，可以整理出，整个运算包含

文章图片
次乘法，因此，如果我们例化了n个乘法器，每个乘法器需要运行t个时钟周期，则理想中整个蒙哥马利模乘的
时钟周期为

文章图片
。考虑到之前所介绍的内部循环处理单元中的两个乘法可以并行执行，我们可以例化两个乘法器同时进行计算；但是，由于不同的循环之间存在数据依赖关系，因此只能串行执行循环。
因此，系统设计的目标是让总时钟周期接近

文章图片
。为了实现这一目标，系统中进行了以下三项优化。
展开内层循环：展开内层循环的最大好处就是将内层循环从一个单一的整体拆解为多个组成部分，从而实现多次迭代中无数据依赖部分之间的时间交叠（overlap），进而最大程度地压缩整体运行时间。该操作可以通过HLS中的UNROLL指令实现。将q的运算插入内层循环中：蒙哥马利算法中q是执行内层循环的前提，但是从q的表达式中可以发现，只依赖于S_i的部分比特位，因此，当某次迭代中S_i的这些比特位计算完毕后，即可同时开始进行下一次迭代q中的计算。从而节省这部分的时间开销。流水线处理外层循环：通过展开内层循环，并且使用HLS中的PIPELINE指令，设置流水线初始化间隔为内层循环的迭代次数，内层循环将自动地根据拆解的操作执行流水线调度。该流水线处理示意图如图五所示。内层循环展开后被拆分为四个部分S_0 ， S_1,S_2和S_3 。当S_0计算完毕后，即可开启下次迭代中q的计算。而q计算完毕后，下一次迭代计算即可开始。