低延迟乘法器和密码难题

在简街，我们有一些将FPGA用于低延迟系统的经验-FPGA是一种可编程硬件，可以获得专用集成电路(ASIC)的速度，而不需要致力于烧录到芯片中的设计。就在不久以前，FPGA还很昂贵和罕见，但现在，你可以在亚马逊AWS云上以每小时不到3美元的价格租到一张5000美元的卡。

最近，我参加了一个数十年来的谜题竞赛，展示了如何巧妙地使用FPGA来突破低延迟计算的界限。

早在1999年，麻省理工学院的计算机科学和人工智能实验室就创造了一个时间胶囊，其中包括一个由Ron Rivest(RSA中的“R”)设计的密码拼图。难题是计算22t(Mod N)，t=79,685,186,856,218和2048位半素数n。(半素数是两个素数相乘的结果。)。提示符很有说服力地指出，问题可以通过从2开始反复平方t乘以mod n来解决。例如(从提示符中)：

假设n=11*23=253，然后我们可以计算：2^(2^1)=2^2=4(Mod 253)2^(2^2)=4^2=16(Mod 253)2^(2^3)=16^2=3(Mod 253)2^(2^4)=3^2=9(Mod 253)2^(2^5)=9^2=81(Mod 253)2^(2^6)=81^2=236(Mod 253)。2^(2^t)=2^(2^10)=202^2=71(Mod 253)。

Rivest的团队选择了平方t的数量，这样，如果摩尔定律成立，这个谜题将需要大约35年的时间才能破解。

我们可以预期，到2012年，当时钟速率达到约10 GHz时，内部芯片速度总体上将提高约13倍。在那之后，改进似乎更加困难，但我们估计到2034年可能会实现另一个5倍的目标。因此，到2034年，总的计算速度应该会经历大约6倍的翻番。

但后来在2019年宣布，比利时程序员BernardFabrothad在短短三年半的时间里就破解了这个谜题，比原计划提前了十年半。他的方法没有什么魔术。只是里维斯特最初的估计差了十倍。虽然我们的台式机中没有10 GHz的CPU(主要是由于散热问题)，但是CPU和多核架构已经取得了显著的进步。在伯纳德宣布他解决了这个难题几周后，另一个名为Cryptophage的组织宣布，他们也在短短两个月内使用了FPGA。

这个谜题的一个有趣的方面是，虽然它的计算成本很高，但对于谜题的设计者来说，验证解决方案的成本很低。这是因为如果你知道n的因子p和q的两个素数p和q，你就可以用欧拉函数来计算φ(N)=(p-1)(q-1)。一旦有了它，大指数就可以从22t(Modn)减少到更快的计算22t(modphi(N))(Modn)。

这些类型的密码难题是一类可验证延迟函数(VDF)的一部分：这些问题需要一些中等到大量的非并行工作来计算，但可以很快得到验证。它们在去中心化的区块链系统中很有用，例如用于随机性信标、投票和复制证明。虽然Rivest的难题需要秘密知识来快速验证结果，但有许多建议的构造允许VDF在没有秘密知识的情况下进行公开验证。

2019年末，VDF联盟开始竞相寻找VDF问题可实现的最低延迟-类似于Ron Rivest 1999年的谜题。这个想法是，通过将这样的问题提交给激烈的竞争，你可以帮助依赖VDF的战斗测试系统。

比赛要求参赛者解决Rivest拼图的缩小版，t值为~2 33，而不是2 46，模数为1024位。参赛者也事先得到了p。

第一轮VDF联盟竞赛的获胜者是使用Ozturk多路复用器架构的EricPearson。这种类型的乘法器利用了FPGA可以非常高效地完成GPU或CPU无法做到的几个技巧：

冗余位表示(RBR)。这意味着您的1024位数字被分成n个大小相等的字(在本例中，n=64个字，每个字16位)，但是每个字都有一个额外的冗余位。这样做的好处是，当您累加乘法的所有部分积时，您不需要在整个2048位结果中传播进位-您只需要将其传播到相邻的字。在FPGA上，电路可以运行的最大速度将受到最慢路径的限制--通常是进位链。这有助于使方程式的平方部分尽可能快地运行。当我们平方时，我们使用相同的算法作为乘法，除了一半的部分乘积是相同的。我们不需要计算两次：我们只需将它们移位1位，基本上免费地将它们加倍。

使用查找表进行模约简。设置超过1024位模边界的每一位都可以作为模p值来预计算并加回到原始结果上-例如，22000变成22000%p。这样，2048位的结果可以被还原为1024+log2(预计算字树的高度)位的模p值。在这种方式下，可以将2048位的结果还原为1024+log2(预计算字树的高度)位的模p值。这在FPGA上占用了大量内存，但允许您在三个时钟周期内计算模p：两个时钟周期用于查找RAM，一个时钟周期用于将偏移量折回到结果中。这项技术和使用RBR都有助于加速VDF方程所要求的最终“模p”。

Eric的实现利用了生成FPGA(6个输入)中的LUT大小来更有效地映射乘法器部分积累加中的内存减少元素和压缩树。为了减少模数，她使用了速度更快的LUTRAM，而不是块RAM，这进一步节省了一个时钟周期；利用这个节省的时钟周期，将更多的流水线添加到158.6 MHz工作频率(总共4级流水线)的关键定时允许的路径。这意味着VDF的单次迭代可以在25.2 ns内完成。该设计跨越大部分FPGA，跨越多个超级逻辑区(缩写为SLR，这些是用于形成一个大芯片的单个硅管芯)，并且需要电源管理才能运行。Eric在他的意见书中评论说，FPGA在AWS云中运行时实际上消耗了高达48W的功率。

在第三轮也是最后一轮的比赛中，鼓励采用更现实的方法来解决问题-Ozturk乘法器代码实际上是以基本形式提供给第一轮的，所以确保不存在可能比Ozturk更快的替代设计是很重要的。(最初，没有人想把时间花在试图从头开始实现一些东西上，结果发现它没有那么好。)。这对我来说听起来很有趣，所以我想出了一个新颖的“预测性蒙哥马利乘数”建筑，它是最后的获胜者。

蒙哥马利与RBR的乘法。我决定使用蒙哥马利的算法来实现模约简方案，该算法需要变换到蒙哥马利域，但是模p变成了固定的比特移位，这可以在FPGA的Ino(1)时间上完成。我只在2n循环的开始和结束时转换进出蒙哥马利域，所以开销并不明显。我还修改了算法，使之与RBR一起使用-这使得每个单独的步骤都稍微快了一点。

蒙哥马利乘法只涉及乘法、加法和位移位-所有这些都很容易在RBR中实现，并将受益于较短的进位链。我还添加了一个额外的RBR字，这样总共有65个字，每个字17位来表示一个1024位的数字。这种改变允许对Montgomery算法进行修改，从而保证其产生的结果不会超过p(传统的Montgomery算法只会使结果小于2p)。通过使用蒙哥马利乘法，我可以节省大量的FPGA面积，因为VDF方程的模运算变得容易得多。

具有快速进位功能的LOG-3压缩电路。我决定使用FPGA DSP(数字信号处理器，FPGA上用于高效执行乘法的小型专用资源)将乘法器实现为简单的叉积乘法器。选择的RBR位宽度为17意味着一个部分积只占用1个DSP资源，然后是使用通用FPGA LUT的最终部分积累加阶段。所用树的最大高度需要128列，每列包含129个部分乘积，每列17位宽相加在一起。我用不同的对数值进行了实验，发现折叠树的大小为3，并且使用FPGA加法器快速进位(而不是使用没有使用快速进位的压缩器树)可以得到最好的结果。这种用RBR实现的压缩器使我可以比以前从乘法器中挤出更多的性能。

预测性分支。蒙哥马利乘法需要完整的1024位平方运算，然后是1024位乘法，其中我只关心结果的低1024位，然后是1024位乘法、加法和位向下移位(所以我实际上只关心结果的高1024位)。

这里的问题是，FPGA上的单个SLR只有2280个DSP-我真的很想在这个预算中工作，因为与多个SLR通信会使整个设计变慢。一个平方需要大约2120个DSP，但是一个完整的相乘将需要4225个。为了解决这个问题，我使用了预测分支：乘法器根据输入Fedin通过纵横线计算部分乘积，其中选择输入，因此我只计算一个完整的正方形、较低的65+x个字或较高的65+x个字。这里的x是超过边界的字数，我进行了计算，以确保考虑到由于我们的RBR表单而可能被错误地包含或丢弃的任何进位溢出。

如果我在边界字中检测到可能存在这种情况(由全1检测到，并且没有可用位来吸收进位)，我将进行分支并计算完整的2048位(130字)结果，同时完全传播。这种情况非常罕见，几乎不会影响性能，但是这种预测分支的风格允许我们使用单个SLR和2272个DSP来实现整个蒙哥马利RBR算法。我还利用了部分乘积树，并在不添加流水线外阶段的情况下简化了额外的添加。

更慢、更短的管道。通常，可以添加流水线级以允许设计实现更高的频率和更高的吞吐量。但是，由于这是为了实现低延迟，您实际上不需要额外的流水线-额外的流水线会增加FPGA中信号的路由延迟，因为它们现在需要进行“凹坑停顿”来访问寄存器。在我的设计中，主数据路径循环在预测乘法器的输出上只有一个流水线级，预测乘法器直接反馈到乘法器交叉开关。这一改进不仅有助于改进，而且还降低了设计中使用的总体功耗。更低的时钟意味着单个信号将以更低的频率切换，这将导致FPGA功耗的平方降低。

我的乘法器设计运行在65 MHz，花了46 ns(3个时钟周期)来完成VDF的一次迭代。它可以完全在FPGA的一个单反上实现(FPGA的三分之一，比Ozturk设计少2.3倍)，并且不需要任何特殊的电源管理，因为它的功耗低3.7倍(两种设计都在FPGA设计软件Vivado中进行了仿真)。因为我的设计较小，所以更容易放大。如果这个设计被放大(通过使用FPGA上的所有3个单反)来解决Ron Rivest最初35年的难题，那么我们将花费两个多月的时间！

下表显示了两种1024位体系结构的比较，括号中显示了改善比率(因此越高越好)，其中Ozturk乘数为基数1.0x。与Ozturk乘法器体系结构相比，我的设计具有最低的延迟，赢得了我参与竞争的这一轮，并且功耗(在表中我们以每次操作消耗的焦耳为单位)和面积效率更高，但总体来说Eric的第二轮设计能够实现更低的绝对效率(在表格中，我们显示的是每次操作所消耗的能量以焦耳表示)，并且与Ozturk乘法器体系结构相比，面积效率更高。

所有这些都与我们在简街所做的工作没有直接联系，尤其是，我们不太可能在短期内在我们的基础设施中使用VDF。但是，使用可重构硬件构建比普通CPU快几个数量级的解决方案的广泛方法是我们团队所做工作的核心。而且，正如这个示例所强调的那样，构建最高效的解决方案需要您考虑全新的体系结构、资源约束和功能，而不是您通常在软件中考虑的体系结构、资源约束和功能。

还有其他模约简算法，例如Barret约简和中国剩余定理，以及其他可用于实际底层乘法器的体系结构，如Toom-Cook、Booth和Karatsuba。我研究了所有这些方法，但发现由于各种原因，它们在FPGA上也没有映射到这个问题(即，Barret的算法需要减法，这会使RBR更复杂和更慢)。