Генерация псевдослучайных чисел на графических процессорах

Генераторы псевдослучайных чисел используются в множестве вычислительных приложений, таких как моделирование стохастических систем, численном анализе, вероятностных алгоритмах и т.д. Численное моделирование биологических систем и процессов, например, полноатомные МД симуляции в неявном растворителе [1, 2], симуляции Ланжевена [14], и симуляции Монте-Карло [4] — все это требует большого числа независимых случайных переменных на каждом шаге моделирования. Мы разработали два подхода для реализации генераторов случайных чисел (ГСЧ) на графическом процессоре (ГП). В подходе «один-ГСЧ-на-поток», один ГСЧ создает поток случайных числел в каждой нити, тогда как подход «один-ГСЧ-на-все-потоки» построен на возможности нитей взаимодействовать друг с другом, разделяя, таким образом, начальные состояния генератора на всем устройстве. ГСЧ выдаёт последовательность случайных чисел ui, которые, как предполагается, должны представлять независимые и равномерно распределенные случайные величины из интервала (0, 1). Существует три основных требования для численных реализаций ГСЧ: (1) хорошие статистические характеристики, (2) высокая скорость вычисления, и (3) низкое потребление памяти. Поскольку детерменированная последовательность случайных чисел в конечном счете приходит в исходную точку, un+p = un, ГСЧ должен также иметь большой период p[3]. Кроме того, ГСЧ должен пройти строгие статистические тесты на независимость и равномерность, а также несколько определённых прикладных тестов, которые используют точное решение для проверки результатов [3, 8-10]. Действительно, использование статистически плохих случайных чисел может приводить к недостаточности выборок, нефизичным корреляциям и даже к нереалистичным результатам, что может вызвать грубые ошибкам при применении на практике. Мы разработали реализации на ГП нескольких ГСЧ, которые дают хначения высокого статистического качества, используя идею циклического деления [13].

Методы

Существует много методов получения нормально распределённых случайных чисел ui (i = 1, 2, … n) [5-7]. Мы адаптировали самый широко используемый метод преобразования Бокса-Мюллера [7]. В подходе «один-ГСЧ-на-поток» основная идея заключается в разделении одной последовательности случайных чисел между множеством нитей, выполняющихся параллельно на ГП таким образом, чтобы каждая нить сама генерировала поток случайных чисел. Так как большинство алгоритмов ГСЧ, включая LCG, Ran2, и Hybrid Taus основаны на последовательной трансформации текущего состояния [4], то самый простой способ разделения последовательности — снабдить все нити собственными различными начальными состояниями ГСЧ, кроме того, разделяя нити таким образом, чтобы не возникали межпотоковые корреляции (рис. 1, слева). С другой стороны, некоторые генераторы, включая алгоритмы Mersenne Twister и Lagged Fibonacci, использующие рекурсивные преобразования, позволяют получить (n+1)-е число не зная n-го числа [12]. Количество получаемых таким методом чисел, которое, в общем случае, зависит от выбора параметров для ГСЧ, должно быть равно числу потоков N или кратному ему числу M×N. Тогда все случайные числа можно получить одновременно, т.е. j-ая нить получает числа j, j+N, j+2N,… и т.д. В конце каждого шага симуляции нити необходимо синхронизировать для обновления текущего состояния ГСЧ. Таким образом, одно и то же состояние ГСЧ может быть использовано всеми потоками, каждый из которых обновляет только один элемент состояния. Мы называем этот подход «один-ГСЧ-на-все-потоки».

Рис.1. Упрощенная схема подходов «один-ГСЧ-на-поток» (слева) и «один-ГСЧ-на-все-потоки» (справа). В первом подходе один генератор выдает дает набор псевдослучайных чисел для каждого потока, т.е. один и тот же алгоритм ГСЧ (реализованный несколькими ГСЧ) выполняется каждой нитью, создавая различные подпоследовательности одной и той же последовательности случайных чисел. Второй подход построен на возможности взаимодействия нитей, и, таким образом, возможности разделения состояния генератора на всем устройстве.

Мы использовали эти методы, чтобы разработать реализации алгоритмов линейного конгруэнтного генератора (LCG) [4] и Ran2 [4], Hybrid Taus [4, 11] и аддитивного алгоритма Lagged Fibonacci [4, 12] для ГП. Эти генераторы были встроены в программу симуляций динамики Ланжевена для биомолекул, полностью реализованную на ГП. Полученное для ГП ~250-кратное ускорение, позволяет нам проводить молекулярные симуляции в стохастическом термостате. Теперь, используя это ускорение, мы можем проводить, к примеру, измерения динамики изменения силы для одной молекулы in silico для того чтобы исследовать механические свойства больших молекулярных образований, таких как димер фибриногена (Fb)2 и бактериофаг HK97, в экспериментальной временной шкале до секунды используя экспериментальные силовые нагрузки.

Результаты тестов производительности генераторов случаных чисел, реализованых на ГП можно найти здесь.
Литература

[1] Brooks BR, Bruccoleri RE, Olafson BD, States DJ, Swaminathan S, Karplus M. CHARMM: A program for macromolecular energy, minimization, and dynamics calculations J Comput. Chem. 1983; 4: 187–217.

[2] Haberthür U, Caflisch A. FACTS: Fast analytical continuum treatment of solvation, J. Comput. Chem. 2008; 29: 701–715.

 [3] L’ Ecuyer P, Simard R. TestU01: A C library for empirical testing of random number generators, ACM T. Math. Software. 2007; 33: 22.

 [4] Press WH, Teukolsky SA, Vetterling WT, Flannery BP. Numerical Recipes in C, 2nd ed. The Art of Scientific Computing; Cambridge University Press, 1992.

 [5] Tsang WW, Marsaglia G. The Ziggurat Method for Generating Random Variables, J. Stat. Softw. 2000; 5.

 [6] Marsaglia G, Bray TA. A convenient method for generating normal variables, SIAM Rev. 1964; 6: 260–264.

 [7] Box GEP, Mueller ME. A note on the generation of normal random deviates, Ann. Math. Stat. 1958; 29: 610–611.

 [8] Marsaglia G. DIEHARD: A battery of tests of Randomness, 1996 (http://stat.fsu.edu/geo/diehard.html).

 [9] Mascagni, M.; Srinivasan, A. Algorithm 806: SPRNG: A scalable library for pseudorandom number generation, ACM T. Math. Software. 2000; 26: 436–461.

 [10] Soto J. Statistical testing of random number generators, 1999 (http://csrc.nist.gov/rng/).

 [11] Tausworthe RC. Random numbers generated by linear recurrence modulo two, Math. Comput. 1965; 19: 201–209.

 [12] Mascagni M, Srinivasan A. Parameterizing parallel multiplicative lagged Fibonacci generators, Parallel Comput. 2004; 30: 899–916.

 [13] Zhmurov A, Rybnikov K, Kholodov Y, Barsegov V. Genereation of randon numbers on graphics processors: Forced identation in silico of the bacteriophage HK97, (accepted to J. Phys. Chem. B.)

 [14] Zhmurov A, Dima RI, Kholodov Y, Barsegov V. SOP-GPU: Accelerating biomolecular simulations in the centisecond timescale using graphics processors. Proteins 2010; 78: 2984–2999,

[15] A.А. Жмуров, В.А. Барсегов, С.В. Трифонов, Я.А. Холодов, А.С. Холодов. Эффективные генераторы псевдослучайных чисел при молекулярном моделировании на видеокартах // Компьютерные исследования и моделирование. 2011. Т. 3. № 3, с. 287–308.