Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Non-uniform random number generation through piecewise linear approximations

Non-uniform random number generation through piecewise linear approximations

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

A hardware architecture for non-uniform random number generation, which allows the generator's distribution to be modified at run-time without reconfiguration is presented. The architecture is based on a piecewise linear approximation, using just one table lookup, one comparison and one subtract operation to map from a uniform source to an arbitrary non-uniform distribution, resulting in very low area utilisation and high speeds. Customisation of the distribution is fully automatic, requiring less than a second of CPU time to approximate a new distribution, and typically around 1000 cycles to switch distributions at run-time. Comparison with Gaussian-specific generators shows that the new architecture uses less than half the resources, provides a higher sample rate and retains statistical quality for up to 50 billion samples, but can also generate other distributions. When higher statistical quality is required and multiple samples are required per cycle, a two-level piecewise generator can be used, reducing the RAM required per generated sample while retaining the simplicity and speed of the basic technique.

References

    1. 1)
      • finance.yahoo.com. ‘Microsoft daily close price (log-returns)’, march 1986 to march 2006.
    2. 2)
      • G. Marsaglia , W.W. Tsang . The ziggurat method for generating random variables. Journal of Statistical Software , 8 , 1 - 7
    3. 3)
      • UEFA, ‘European Cup: points scored’, www.european-footballstatistics.co.uk, 2006.
    4. 4)
      • D. Lee , J. Villasenor , W. Luk , P. Leong . A hardware gaussian noise generator using the box-muller method and its error analysis. IEEE Trans. Comput. , 6 , 659 - 671
    5. 5)
      • A.J. Walker . An efficient method for generating discrete random variables with general distributions. ACM Trans. Math. Softw. , 253 - 256
    6. 6)
      • A. Bowman , A. Azzalini . (1997) Applied smoothing techniques for data analysis.
    7. 7)
      • Zhang, G.L., Leong, P.H.W., Ho, C.H., Tsoi, K.H., Lee, D.-U., Cheung, R.C.C., Luk, W.: `Reconfigurable acceleration for Monte Carlo based financial simulation', Proc. Int. Conf. Field- Programmable Technology, 2005, IEEE Computer Society Press, p. 215–224.
    8. 8)
      • (2005) Stratix II Device Handbook, Volume 1.
    9. 9)
      • Bower, J.A., Thomas, D.B., Luk, W., Mencer, O.: `A reconfigurable simulation framework for financial computation', Proc. ReConFig. '06, 2006.
    10. 10)
      • George, M., Alfke, P.: `Linear feedback shift registers in Virtex devices', Tech. Rep. 2001, 2001.
    11. 11)
      • P. L'Ecuyer , R. Simard . TestU01 random number test suite.
    12. 12)
      • A.S. Weigend , B.A. Huberman , D.E. Rumelhart . (1992) Predicting sunspots and exchange rates with connectionist networks, Nonlinear modeling and forecasting.
    13. 13)
      • W.H. Press , S.A. Teukolsky , W.T. Vetterling , B.P. Flannery . (1992) Numerical recipes.
    14. 14)
      • Negoi, A., Zimmermann, J.: `Monte Carlo hardware simulator for electron dynamics in semiconductors', Int. Annual Semiconductor Conf., 1996, Sinaia, Romania, p. 557–560.
    15. 15)
      • C.S. Wallace . Fast pseudorandom generators for normal and exponential variates. ACM Trans. Math. Software , 1 , 119 - 127
    16. 16)
      • Yahoo! finance, http://finance.yahoo.com, daily closing data as of 24th of March 2007.
    17. 17)
      • Zhang, G.L., Leong, P.H., Lee, D.-U., Villasenor, J.D., Cheung, R.C., Luk, W.: `Ziggurat-based hardware gaussian random number generator', Proc. Int. Conf. Field Programmable Logic and Applications, 2005, IEEE Computer Society Press, p. 275–280.
    18. 18)
      • D.-U. Lee , W. Luk , J.D. Villasenor , G. Zhang , P.H. Leong . A hardware gaussian noise generator using the wallace method. IEEE Trans. VLSI Syst. , 8 , 911 - 920
    19. 19)
      • J. Leydold . Short universal generators via generalized ratio-of-uniforms method. Math. Comp. , 243 , 1453 - 1471
    20. 20)
      • P. L'Ecuyer . Maximally equidistributed combined tausworthe generators. Math. Comp. , 213 , 203 - 213
    21. 21)
      • W. Hörmann , J. Leydold . Continuous random variate generation by fast numerical inversion. ACM Trans. Modeling Comput. Simulation , 4 , 347 - 362
    22. 22)
      • G. Marsaglia . (1997) The Diehard random number test suite.
    23. 23)
      • E. Boutillon , J.-L. Danger , A. Ghazel . Design of high speed AWGN communication channel emulator. Analog Integrated Circuits and Signal Process. , 2 , 133 - 142
    24. 24)
      • L. Devroye . (1986) Non-uniform random variate generation.
    25. 25)
      • Thomas, D.B., Luk, W.: `Efficient hardware generation of random variates with arbitrary distributions', Proc. IEEE Sym. on FPGAs for Custom Computing Machines, 2006.
    26. 26)
      • McCollum, J.M., Lancaster, J.M., Bouldin, D.W., Peterson, G.D.: `Hardware acceleration of pseudo-random number generation for simulation applications', IEEE Southeastern Symp. on System Theory, 2003, p. 299–303.
    27. 27)
      • Shackleford, B., Tanaka, M., Carter, R.J., Snider, G.: `FPGA implementation of neighborhood-of-four cellular automata random number generators', Proc. ACM/SIGDA Int. Sym. Field- Programmable Gate Arrays, 2002, New York, USA, ACM Press, p. 106–112.
    28. 28)
      • Thomas, D.B., Luk, W.: `High quality uniform random number generation through lut optimised linear recurrences', Proc. Int. Conf. Field-Programmable Technology, IEEE Computer Society.
    29. 29)
      • Kabal, P.: `Generating gaussian pseudo-random deviates', Tech. Rep., 2000.
    30. 30)
      • (2000) Virtex-II Platform FPGAs: Complete Data Sheet.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt_20060188
Loading

Related content

content/journals/10.1049/iet-cdt_20060188
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address