Toward Accurate and Highly Performant Simulations with BRODA* Sobol Quasi-random Number Generator

Published: 01/01/2020

Powered by Intel® oneAPI Math Kernel Library

BRODA* Ltd.
@IntelDevTools


Quasi-random number generators are widely used in the different artificial intelligence algorithms (for example, particle swarm optimization) and in quasi Monte Carlo simulations (popular in finance and risk management) as a source of low-discrepancy random number sequences. The Sobol’ sequence produced by SobolSeq65536 generator (developed by BRODA*1) satisfies uniformity conditions (Property A and Property A'). These conditions lead to better convergence of numerical integration and outperforms all other known quasi-random number generators both in speed and accuracy2.

Intel® oneAPI Math Kernel Library (oneMKL) is the fastest and most-used math library for Intel®-based systems. It accelerates math processing routines, increases application performance, and reduces the development time3. SobolSeq65536_MKL is the recently developed version of SobolSeq65536 sequence generator integrated with oneMKL. SobolSeq65536_MKL uses the direction numbers of SobolSeq65536 so that it has the same statistical properties. oneMKL significantly enhances BRODA* Sobol’s sequence generation performance on the Intel® hardware, which is a critical characteristic for the massive simulations. oneMKL also allows to run the SobolSeq65536 generator on Intel® Iris® Xe graphics hardware through oneMKL DPC++ APIs.

 

Statistical Properties of SobolSeq65536 and SobolSeq65536_MKL Generators

The low-discrepancy sequence of Sobol produced by SobolSeq65536 generator has better statistical properties than the output sequences of the other known generators. This article compares BRODA’s SobolSeq65536 generator and Sobol’ sequence generator with direction numbers of S. Joe and F. Y. Kuo (Joe&Kuo)4 for the well-known financial benchmarks, European option pricing, and Asian option pricing.

We consider pricing of the European option call with the following parameters: S0 = 100, K= 100, = 0.0, = 0.2, T = 1y. The theoretical Black-Scholes price at the money call (ATM) is = 7.965667455. For the standard algorithm, the price of the option is presented as d-dimensional integral:

standard algorithm, the price of the option is presented as d-dimensional integral

For Asian option pricing, we consider pricing of a geometric average Asian call option with the following parameters S0 = 100, K= 100, = 0.05, = 0.2, T = 0.5y. For the standard algorithm the price of a geometric average Asian call option can be written as the following d-dimensional integral:

For the standard algorithm the price of a geometric average Asian call option can be written as the following d-dimensional integral

Figure 1 shows the root mean square error (RMSE) integration result (averaged over 20 runs) for European option pricing and Asian option pricing benchmarks (dimension d =1024).

Figure 1. RMSE integration of the ATM call

Figure 1. RMSE integration of the ATM call

 

Figure 2. RMSE integration of the Asian call

Figure 2. RMSE integration of the Asian call

 

A comparison of BRODA’s generator with Joe&Kuo's generators shows that Joe&Kuo’s generator is much less efficient than BRODA’s generator in the case of the Standard scheme, and it's even less efficient than the random number generator (MC method). In the case of the Brownian bridge (BB), both generators show similar performance.

 

Performance Acceleration by oneMKL

oneMKL Vector Statistics component provides a set of commonly used random number generators including implementation of Sobol’ quasi-random number generator (with Intel® CPUs and Xe graphics support), which also accepts registration of user-defined parameters during the initialization5. This fact formed the basis of oneMKL integration into the BRODA’s SobolSeq65536 sequence generator.

SobolSeq65536_MKL (SobolSeq65536 with oneMKL underneath) has two variants: single-point version with a point-by-point access, and a block version, which allows to obtain several Sobol’ vectors in a single function call.

Figure 3 shows the performance results (averaged over 10 runs) for 2^20 quasi-random numbers produced by SobolSeq65536 and SobolSeq65536_MKL.

Figure 3 shows the performance results 01

Figure 3 shows the performance results 02

Figure 3 shows the performance results 03

Figure 3 shows the performance results 04

Figure 3. Performance comparison of SobolSeq65536 and SobolSeq65536_MKL

 

The charts show that a block version of SobolSeq65536_MKL significantly outperforms SobolSeq65536. The best acceleration of SobolSeq65536_MKL versus SobolSeq65536 was achieved in cases of 10 dimensions – 4X, 100 dimensions – 4X, 1000 dimensions – 7.9X, 16384 – 27.7X, and 65535 dimension – 52.7X.

 

Conclusion

BRODA’s SobolSeq65536 sequence generator is a 65536-dimensional Sobol’ low-discrepancy sequence generator, which outperforms all other known generators both in speed and sequence statistical properties. SobolSeq65536_MKL is a recently developed version of the SobolSeq65536 sequence generator integrated with oneMKL. Based on the performance results introduced, the block mode of SobolSeq65536_MKL generator has significant performance benefits in comparison with the single-point mode because it helps to use vectorization opportunities of Intel® hardware.

 

References

  1. BRODA Ltd.
  2. Sobol’ I., Asotsky D., Kreinin A., Kucherenko S. Construction and Comparison of High-Dimensional Sobol’ Generators, Wilmott, Nov:64-79, 2011
  3. Intel® oneAPI Math Kernel Library
  4. Joe S., Kuo FY. Constructing Sobol sequences with better two-dimensional projections. SIAM Journal on Scientific Computing. 2008;30(5):2635-54
  5. Intel® oneAPI Math Kernel Library Vector Statistics – Sobol quasi-random number generator
  6. Bianchetti M., Kucherenko S., Scoleri S., Pricing and Risk Management with High-Dimensional Quasi Monte Carlo and Global Sensitivity Analysis, Wilmott, July, pp. 46-70, 2015

 

______

You May Also Like 

 

Solve Enhanced Math Problems on GPUs: Linear Algebra, Sparse Matrices, and RNGs

Watch

 

Now Available: Additional oneAPI Open-Source Math Library Interfaces

Read

 

Intel® oneAPI Math Kernel Library
Accelerate math processing routines, including matrix algebra, fast Fourier transforms (FFT), and vector math. Part of the Intel® oneAPI Base Toolkit.

Get It Now

See All Tools

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.