Low discrepancy sequences for Monte Carlo simulations on reconfigurable platforms
Low discrepancy sequences for Monte Carlo simulations on reconfigurable platforms
复制标题
可重构平台上蒙特卡罗模拟的低差异序列
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. Harwayne
中科院分区：
文献类型：
--
作者：
I. Dalal;D. Stefan;J. Harwayne
低差异序列，也称为ldquoquasi-randomrdquo序列，是在给定体积中比伪随机数更好地均匀分布的数字。高维积分的计算在科学领域以及其他领域（如金融）中通常需要，并且通过随机蒙特卡罗模拟来执行。与使用常规伪随机数的仿真相比，使用准随机数的仿真可以实现更快的收敛和更好的精度。这种模拟被称为准蒙特卡罗。传统的蒙特卡罗模拟越来越多地实现在可重构设备，如FPGA，由于其固有的并行性质。这对于准蒙特卡罗模拟是不可能的，因为据我们所知，以前在硬件中没有产生过低差异序列。我们提出了FPGA优化的可扩展设计，以生成三种不同的常见低差异序列：Sobol、Niederreiter和Halton。我们实现这三个发电机的Virtex-4 FPGA上不同程度的细粒度并行化，虽然我们的想法可以应用到更广泛的一类序列。我们得出结论，从一个实际的准蒙特卡罗模拟从集成电路中提取部分电感的实施结果。
Low-discrepancy sequences, also known as ldquoquasi-randomrdquo sequences, are numbers that are better equidistributed in a given volume than pseudo-random numbers. Evaluation of high-dimensional integrals is commonly required in scientific fields as well as other areas (such as finance), and is performed by stochastic Monte Carlo simulations. Simulations which use quasi-random numbers can achieve faster convergence and better accuracy than simulations using conventional pseudo-random numbers. Such simulations are called Quasi-Monte Carlo. Conventional Monte Carlo simulations are increasingly implemented on reconfigurable devices such as FPGAs due to their inherently parallel nature. This has not been possible for Quasi-Monte Carlo simulations because, to our knowledge, no low-discrepancy sequences have been generated in hardware before. We present FPGA-optimized scalable designs to generate three different common low-discrepancy sequences: Sobol, Niederreiter and Halton. We implement these three generators on Virtex-4 FPGAs with varying degrees of fine-grained parallelization, although our ideas can be applied to a far broader class of sequences. We conclude with results from the implementation of an actual Quasi-Monte Carlo simulation for extracting partial inductances from integrated circuits.