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

Powered by Intel® oneAPI Math Kernel Library

BRODA* Ltd.
@IntelDevTools

Get the Latest on All Things CODE
Sign Up

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 the SobolSeq65536 generator (developed by BRODA¹) 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 accuracy.²

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 time.³ 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 the BRODA Sobol sequence-generation performance on Intel® hardware, which is a critical characteristic for the massive simulations. oneMKL also allows to run the SobolSeq65536 generator on Intel® Iris® X^e graphics hardware through oneMKL Data Parallel C++ (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 the BRODA SobolSeq65536 generator and Sobol’ sequence generator with direction numbers of S. Joe and F. Y. Kuo (Joe&Kuo)⁴ for the well-known financial benchmarks, European option pricing, and Asian option pricing.

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:

For Asian option pricing, 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:

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 2. RMSE integration of the Asian call

A comparison of the BRODA generator with Joe&Kuo's generators shows that Joe&Kuo’s generator is much less efficient than the BRODA 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

The Vector Statistics component in oneMKL provides a set of commonly used random number generators including implementation of Sobol’ quasi-random number generator (with Intel® CPUs and graphics support for X^e Architecture), which also accepts registration of user-defined parameters during the initialization.⁵ This fact formed the basis of oneMKL integration into the BRODA 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. 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

The BRODA 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. Construction and Comparison of High-Dimensional Sobol’ Generators
3. oneMKL
4. Joe S., Kuo FY, "Constructing Sobol Sequences with Better Two-Dimensional Projections," SIAM Journal on Scientific Computing 2008;30(5):2635-54
5. oneMKL Vector Statistics: Sobol Quasi-random Number Generator
6. Pricing and Risk Management with High-Dimensional Quasi-Monte Carlo and Global Sensitivity Analysis

______

You May Also Like