翻译

浮点和指数均匀分布的资源节约型发生器

摘要

作为同类器件中容量FPGA可以很好的使用蒙特卡罗模拟等多种随机算法，

最大的，它允许执行不依赖循环的高级应用程序，深流水不循环携带依赖性和空间尺度在大型设备没有共享资源瓶颈。另一个重要优势是，随机数生成是非常便宜（相对于软件），并且可以进行定制以满足每个应用的性能和质量的需要。然而，在许多情况下这样的优势并不能发挥出来，要么是因为选用了一台简单的执行效率不高的发生器，或者是发生器的性能远远超过设备的需要。本文介绍了浮点和指数分布均匀，从而提供有效的资源使用发生器，同时保持足够的简单，因而吸引了众多使用者。

1简介

蒙特卡罗模拟利用大数法则来解决高维和非线性之类的棘手问题。首先一个问题是建立随机模型（即一个模型，包含一些不可预测性或随机性），则该模型被执行数百或数百万次，每次执行后提供不同的结果。底层模型的平均行为与因为模拟数的增加使底层模型估计的准确性增加了。

FPGA的似乎是应用蒙特卡罗的理想平台，因为众多问题有一个相类似的特性，这就允许应用程序可以很容易地在设备规模之间或者多功能设备中使用。这些FPGA的加速应用包括finance[5,9]，生化模拟[7]，放射性传热[3]造型。其成功的关键之一是，随机生成二进制数字在FPGA中是非常便宜的，但这些位之后必须由应用程序转换成所需的非均匀分布状。

在本课题中，我们研究了在FPGA模拟中日益显重要的两个密切相关的分布：浮点和指数均匀分布。这两个分布密切相关，如x = - ㏑（u），如果x是一个指数变量，这两个分布很容易产生使用硬件的浮点库，u则是一个浮点变量。

但是这是一种资源浪费：最近的一篇文章[8]中描述的使用ln（1 / u）的浮点输入来生成一个指数变量，需要3894个片量，13个乘法器和6个RAM。在这里，我们描述了如何使用特定领域的知识提高效率和显著性能。 我们主要研究的是：

显示出浮点数可以生成作为两个独立的部分，?对浮点硬件产生均匀随机数分析，

采用了几何变量，以确定指数，自主统一的重大随机位。

?将几何方法同传统的固定式算法作比较，很明显几何方法是面积减少了60％，无性能损失，的甚或性能上提高50％，同时减少使用10％的资源。

?一些随机产生指数可以分成几何变量和近似部分，综合分析这些数可以让其分别操作产生结果，然后相加组合即可。

?指数发生器的一个分区的一些执行情况的评价，能够表明高层次的发生器是否提供良好的效率和性能。

2浮点均匀分布

均匀分布在许多蒙特卡罗模拟中都会使用，而在固定点的情况中很容易被解释为是由一个固定点位编号统一向量生成的。然而，越来越多的应用使用基于FPGA的浮点运算，因此希望使用浮点均匀随机数。最简单的方法是使用固定到浮动的转换，但是这有两个缺点。

第一个问题是均匀分布的随机数都应该代表连续随机变量，尤其是零的概率应该是零。这一点尤其重要，当应用到随机数的计算有一个奇点零。一个常见的模式是x = - ㏑（u），其中u是一个统一的随机数。这种模式通常发生，因为在某些行为模拟比较热衷于u趋近于零，这导致x的值稀奇地大，如果u实际等于零（这应该是不可能的），则x将是 - ∞，这很可能导致应用程序中的错误。 图1显示了转换定点均匀值直接转换为浮点值的问题。上面的部分显示了一个带有三个显著位待要转换为浮点格式的简单分布，其中高度表示每个值的概率。在右边只有少数能够代表值接近1，但每个都有很高的概率，而在左边越接近零，其分辨率增大，但单个值的概率下降。

该图中显示了5位固定点均匀分布，这是由五个独立的标准组合在一起的伯努利随机分布（随机二进制数字）。然而，该图的底部显示出了如果将固定点分布转换为浮点数会发生什么。右手边的分布大小是正确的，那里的定点表示分辨率比定点高。问题是在左手侧，那里的定点表示的分辨率远高于浮点。结果我们没能发现随着零的接近而出现逐渐密集的点，而只是一些由定点生成的粗糙数据。值得一提的是，零有一个极限概率（一般在将32位的整数转换为浮点数的情况下概率为2ˉ32），而在理想的浮点分布中概率为零。

即使用更广泛的定点输入，但是这势必会加 有一种方法可以解决这个问题，

剧定点到浮点转换的第二个缺点：效率。在转换过程中的定点数字必须正规化，这就需要一个转换号码平台（或硬件乘法器）。如果为了在零点附近能有一个强势的覆盖范围而采用广泛的定点输入，那么正规化平台也必须更广泛，并需要更多的渠道。

我们推荐使用的方法是模拟广泛定点数字转换过程，但因为其昂 在这里，

贵的规范化过程，导致没有实际执行这个标准的转换过程。图2显示了在一个高

层次的转换过程中，从15位定点转换成5位有效浮点数（有一个隐含的有效数字）。整个转换过程并都是从左往右扫描，先找到第一位，而它就是MSB中的那个隐含的有效数字。接下来四位则成为明确的有效位，而那些跳过的零的个数就作为指数。

值得注意的一点是，我们是要转换一个随机的定点数。这意味着，明确的有效位分布必须同指数不相关：我们先找到第一个位，有它来确定指数，然后从一个完全不同的随机数中取出剩下的有效位。更规范地说，如果随机定点极限精度r定义为b?，b?，...，那么每个位都会是一个标准的独立伯努利变量：

然后，我们可以将在转换过程中发现的第一个非零位的位置定义为e。那么设接下来的位的值位m，并定义所产生的浮点值f：

因为e的值只起决与b?….b,而与b……b无关，那么现在就可以确定浮点数的指数和有效位的相互独立性了，鉴于输入位的独立性（方程3），我们得到如下特性：

e的分布实际上是一个基于非负整数的标准离散几何分布，它记录了直到第一次成功时标准伯努利试验失败的次数。举例来说，这就好比是抛硬币，我们记录的是当人头朝上时所抛硬币的次数。如下给出了几何PMF的（概率质量函数）公式：

方程8的取值范围为正无穷大，从而确保我们能从一个无界的精确随机分布定点开始。事实中，在每个周期里我们只能看有限的位，因此有必要在某个宽度w中截断搜索。截断分布如下式：

给定w一个位宽载体u，而其分布可用线性优先编码器生成。例如，在韩德尔- C语言中的语句中一条语句：g=rmo（u），它就足以产生一个被截断的几何分布变量。宏变量rmo是标准库的一部分，它返回的是所设置索引的最低位（最右边位）。优先编码器的循环时间随着输入宽度的增加而增加，但在实际应用宽度范围内（w≤64），这似乎并不是一个问题（见表1）。

随机浮点值的产生过程可以概括为：产生一个被截断的几何分布样本，对其进行适当的偏移得到浮点指数，然后用独立随机位填充浮点有效位。列表1显示了韩德尔- C实现该操作的过程。参数w1和w2给出了浮点有效位的宽度和指数的容量值，这里假设指数的偏移量位2（同IEEE标准一样）。因为wg决定了浮点变量与零的接近度，因而其选择也决定了该分布的准确的性。 与传统的方法相比，不同之处在于我们用赛灵思CoreGen 9.1（版本3浮点模块）辅助测试该转换器。在这里，我们用一个128位的LUT的优化发生器[4]来生成随机位。一般来说，我们会主张更优质的发生器，比如具有更高周期LUT优化发生器—LUT-FIFO发生器[6]，或Mersenne Twister[1]。然而，在这种情况下，我们感兴趣的是资源和转换过程的性能。而且LUT的优化发生器有两个好处。首先，我们知道该发生器只需要128个LUT（查找表）和128的FFT（触发器），他们已经不能再优化了（虽然他们可能会重复），第二，不会受位发生器性能限制（通常是超过了全局时钟网）。

这些设计都是在韩德尔- C中描述的，并且把Xilinx的核应用到使用接口。我们使用“最高流水线”的内核版本，因为没有任何关于界面和速度权衡究竟是什么的指导的文件或用户接口。韩德尔- C的设计是为Virtex – 2工程编译的，该类工程使用Celoxica公司的DK5（服务包3），既没有综合目标速度，也不具备275兆赫的速度。由于要重定时，目标速度会影响界面速度的综合设计，但对预合成的Xilinx核无影响。这些设计为Virtex - 2 xc2v1000（-6）（使用ISE9.1，ISE9.1都设置为默认值）布局和布线。任何设计的布局和布线工具都是不受时间约束的。

表1显示了在性能和资源使用情况方面对比的结果。请注意，LUT和FF数目反映的仅仅是在转换中所使用的资源，由此我们知道这个128位随机数发生器到底有多少个LUT和FF。然而，还没有办法确定是否发生器与转换进程共享片量，所以我们只记录整个浮点随机数生成器的总片量。

我们发现，当几何转换器为优先区域（即无重定时）编译时，其所需要的LUT和FF只相当于其他定点-浮点转换器的三分之一。即使没有任何重新定时，该方法的速度也大致与的“最高性能”的内核的版本相当。当重新定时，发生器的几何性能有明显的提高，在最常见的情况下（32位单），时钟率提高25％，，而在更复杂的情况下可能增加50％。要实现此性能是以牺牲面积为代价的（尤其是FF），但重定时几何发生器所用资源仍不到CPU的百分之九十。在实际应用中，人们可以快速地定位的最高时速耗时的过程支持浮点数，让工具使该地区

高速的权衡。

3指数分布

该指数分布广泛用在离散事件仿真，它是用来模型中的等待时间分布，直到一些事件发生。据估计，如果某些事件发生在rateλper单位时间，例如在上

averageλshoppers每小时到达排队结账，那么之间的事件给予的时间与速度parameterλ指数分布的概率密度函数（PDF）F和累积分布函数（CDF）的F：

指数分布可以通过产生的反演方法，即民防部队是倒，提供了一个指数和随机输入公式：

这是在第2节，所述的情况的例子，这是至关重要的价值观非常接近零，可产生，但零本身永远不会产生的。通常一个处理不同的价值观ofλwithin通过生成标准指数分布随机数，其中λ= 1，然后由不同的值除以模拟ofλfor不同的发生率。 一个完整的对数功能单位代表的硬件资源大量投资，因而它不是一种资源，指数生成随机数的有效方法。但是它具有方便的巨大优势，并已在一些模拟7]。另一种方法是使用简单的表，查询[8]，但是这需要较大的表，并在分配的尾部穷人的覆盖面。在这里，我们将开发一些也很容易使用，但它们提供更好的效率的简单方法。

对高效发电的关键是要注意公式11可分割成几个部分：

这仅仅是经典的乘法减少，这通常用于计算对数。然而，不使用现成的对数单位的好处是我们可以治疗发生器分开两半：不是的缓冲数据，以确保该延迟在整个数数据路径一样，他每延迟针对部分可以用来匹配最大化潜伏期没有资源的速度。

我们必须 论代很简单，因为我们已经知道如何生成一个标准的几何分布K表。

决定在哪个值较高截断提供更大的覆盖范围值的分布尾部的分布。一个保守的选择，选择= 62，给予0，§ K，一个§ 63，这意味着缺少尾部有概率，机管局2。但是，应用程序开发人员可以选择使用较低的值，如果他们知道了广泛的尾巴覆盖并不重要。

查表特别是在诸如的Virtex 他们用乘法 - 可以实现任何一个常数乘数或查表。

- 5和Stratix - 3 FPGA的最新的吸引力，因为这两种体系结构有6 - LUT的，让每个表位被映射到一个对照表。即使在旧的4 LUT的体系结构查表仍然有效，与每四个LUT表位需要，或更少，如果减少到48或32。

机管局[0.5， 其中M的生成，1）是更有趣的，需要将资源的使用情况和统计之

间的质量作出的选择。最简单和最不发达国家的资源密集型的选择，是制表x在M的等距值，然后执行表查找。这种方法的缺点是，发生器，星光大道分布稀疏点集，并能生产出最显着的价值。这是特别明显，在第一部分（k = 0时），它意味着50％的时间只不同的值会发生。这是否是有问题的稀疏取决于应用程序消耗的随机数字，对查找表的大小。如果一个应用程序产生随机数比较（例如早期之间作出选择的两个事件），那么这个方法可能是不恰当的，因为这将是比较普遍的两台发生器以产生相同的随机时间。但是，如果只是一个指数随机数是在模拟器使用，那么这种方法可能是不够的，特别是如果一个大的块RAM可以使用。例如，使用= 18的Virtex - 5 RAMB 36允许有用= 11，而在Stratix - 3 M144K提供了一个非常令人尊敬的威胁下，在相同的宽度13。

一个更精确的方法是升级到线性插值，基本上从0度表移动到一个degree1表。我们首先选择表以提供最大限度的民防部队在段边界的准确度0系数，然后选择度- 1的系数将跨越之间的界限。它不会提供一个极大极小近似，但它具有简单的优点。幸运的范围是[0.5，1相对平稳），因此给予256或多个表项的近似相当接近。在硬件资源方面，乘法累加为度，一到诸如自然多项式的Virtex - 5 DSP48E的DSP模块的地图需要。

表2总结了基于表格的发生器性能和线性发生器。一如以往，切片计数包括用来产生均匀输入位的资源，而资源的数量和FF LUT的反映只是在指数发生器使用的资源。一个关键的一点是针对从高层次的韩德尔- C是非常有效的DSP48E架构，充分利用乘累加寄存器的数据路径和由此产生的资源，而无需直接实例化。这样可以达到约400MHz到在Virtex - 5，保持家庭无关的代码的速度。

这些指数发生器偏爱统计质量的速度和效率，因此它是重要的特点是什么造成的质量。我们使用的安德森，亲爱的测试，以衡量质量，它使用一个数据样本经验民防部队估计的可能性，将数据从一个给定分布来（在我们的情况下，指数分布）。的可能性为0和1之间的值所，称为p值，与P -值非常接近于零，这表明数据不遵循指数分布。图4给出的P -方法的两代值增加样本大小。

出人意料的是，线性方法其实比表法更糟的是，未能通过测试样品的果断左右，而表的方法达到。这似乎是因为从线性插值产生民防系统偏差，该测试可以检测，而表格的方法有一个准确的（但非常低的分辨率）民防部队。该表的编制方法最终失败，因为测试发现，该恒星的分布是离散的，造成了指数民防部队从不同类型的偏差。尽管如此，仍然有直线发生器的价值，因为它提供了一个密集点集，所以给出了一个连续变量，这在一些关键的应用更好的印象。 4结论

随机数生成器的蒙特卡罗模拟的基本构建块，其效率会影响内部器件的并行度，可以通过空间尺度实现。虽然往往是产生浮点和指数分布随机使用硬件浮点库方便的方法，论证了有显着的效率和性能在这样做的意义。不过，我们已经表明，更复杂的方法并不需要很复杂，并可能导致在资源使用减少了75％，或者50％的性能提高。

未来的工作将审查产生指数分布，包括替代方法来近似0.5至1如CORDIC，更复杂的方法。我们还打算研究方法的不同，质量的影响，试图在效率的特点，性能和质量方面的统计发生器。 致谢

在英国工程和物理科学研究理事会（批准引用EP/D062322/1和EP/C549481/1，阿尔法数据，Celoxica和赛灵思的支持表示感谢。

本文来源：https://www.bwwdw.com/article/4ch6.html