TY - JOUR

T1 - Parallelizable efficient large order multiple recursive generators

AU - Deng, Lih Yuan

AU - Winter, Bryan R.

AU - Shiau, Jyh Jen Horng

AU - Lu, Henry Horng Shing

AU - Kumar, Nirman

AU - Yang, Ching Chi

N1 - Publisher Copyright:
© 2023 Elsevier B.V.

PY - 2023/9

Y1 - 2023/9

N2 - The general multiple recursive generator (MRG) of maximum period has been thought of as an excellent source of pseudo random numbers. Based on a kth order linear recurrence modulo p, this generator produces the next pseudo random number based on a linear combination of the previous k numbers. General maximum period MRGs of order k have excellent empirical performance, and their strong mathematical foundations have been studied extensively. For computing efficiency, it is common to consider special MRGs with some simple structure with few non-zero terms which requires fewer costly multiplications. However, such MRGs will not have a good “spectral test” property when compared with general MRGs with many non-zero terms. On the other hand, there are two potential problems of using general MRGs with many non-zero terms: (1) its efficient implementation (2) its efficient scheme for its parallelization. Efficient implementation of general MRGs of larger order k can be difficult because the kth order linear recurrence requires many costly multiplications to produce the next number. For its parallelization scheme, for a large k, the traditional scheme like “jump-ahead parallelization method” for general MRGs becomes highly computationally inefficient. We proposed implementing maximum period MRGs with many nonzero terms efficiently and in parallel by using a MCG constructed from the MRG. In particular, we propose a special class of large order MRGs with many nonzero terms that also have an efficient and parallel implementation.

AB - The general multiple recursive generator (MRG) of maximum period has been thought of as an excellent source of pseudo random numbers. Based on a kth order linear recurrence modulo p, this generator produces the next pseudo random number based on a linear combination of the previous k numbers. General maximum period MRGs of order k have excellent empirical performance, and their strong mathematical foundations have been studied extensively. For computing efficiency, it is common to consider special MRGs with some simple structure with few non-zero terms which requires fewer costly multiplications. However, such MRGs will not have a good “spectral test” property when compared with general MRGs with many non-zero terms. On the other hand, there are two potential problems of using general MRGs with many non-zero terms: (1) its efficient implementation (2) its efficient scheme for its parallelization. Efficient implementation of general MRGs of larger order k can be difficult because the kth order linear recurrence requires many costly multiplications to produce the next number. For its parallelization scheme, for a large k, the traditional scheme like “jump-ahead parallelization method” for general MRGs becomes highly computationally inefficient. We proposed implementing maximum period MRGs with many nonzero terms efficiently and in parallel by using a MCG constructed from the MRG. In particular, we propose a special class of large order MRGs with many nonzero terms that also have an efficient and parallel implementation.

KW - Automatic generation method (AGM)

KW - Equi-distribution

KW - Matrix congruential generator (MCG)

KW - Spectral test

UR - http://www.scopus.com/inward/record.url?scp=85165182886&partnerID=8YFLogxK

U2 - 10.1016/j.parco.2023.103036

DO - 10.1016/j.parco.2023.103036

M3 - Article

AN - SCOPUS:85165182886

SN - 0167-8191

VL - 117

JO - Parallel Computing

JF - Parallel Computing

M1 - 103036

ER -