可逆线性同余随机数发生器

Reversible linear congruential generator

摘要:

随机数的恢复是仿真系统实现时间回溯能力的关键问题之一，仿真系统通常包含大量随机数，为了恢复之前任意时刻的系统状态，就必须对随机数的状态演化进行跟踪和记录，这种跟踪和记录工作需要极大的时间和空间代价。为解决仿真系统中的随机数恢复问题，基于可逆计算的思想，提出一种可逆线性同余随机数发生器，并分别通过反函数、通项公式、逆分布函数实现该随机数发生器，使其既可正向生成任意分布的随机数列，又可反向恢复之前的随机数。实验结果表明该可逆随机数发生器在总的时空性能上较目前通用的Checkpointing实现方式优越。

Abstract:

The recovery of random numbers is one of the key issues for the simulation system to realize the time traceability. The simulation system usually contains a large number of random numbers. In order to restore the system state at any time before, it is necessary to track and record the state evolution of the random number. This kind of tracking and recording work requires a great time and space cost. In order to solve the problem of random number recovery in the simulation system, based on the idea of reversible computation, a reversible linear congruential random number generator is proposed, and the random number generator is realized through the inverse function, general term formula, and inverse distribution function, respectively. It can not only generate random numbers in the forward direction, but also recover the previous random numbers in the reverse direction. The experimental results show that the reversible random number generator is superior to the current general checkpointing implementation in terms of overall space-time performance.