Достоинства генератора Mersenne Twister

Производительность и ресурсоемкость алгоритма

· В работе [11] было проведено сравнение предложенного авторами алгоритма Mersenne Twister с другими популярными генераторами псевдослучайных чисел. Это сравнение показывает, что Mersenne Twister входит в число наиболее быстрых генераторов, производительности которых примерно одинаковы.

· Объём памяти, требуемый для генератора Mersenne Twister, определяется длиной инициализирующей последовательности {x₀, x₁, ¼, x_n-1}. В работе [11] при максимальном качестве случайного распределения значение n равнялось 624 числам, что много по сравнению с большинством других генераторов. Однако, при необходимости экономного использования памяти значение n можно уменьшить по крайней мере в 30 раз без принципиального ухудшения качества генератора (см. ниже, [15]).

Качество случайной последовательности

Одной из важных характеристик псевдослучайных последовательностей, создаваемых генератором Mersenne Twister, являются очень большие периоды, уже обсуждавшиеся выше.

Другим необходимым требованием к генератору псевдослучайных чисел являются равномерность и некоррелированность создаваемой им последовательности. Поскольку последовательности псевдослучайных чисел не являются абсолютно случайными, гарантировать применимость генератора для решения любой задачи невозможно. Тем не менее, существуют тесты (см., например, [12-13]), позволяющие обнаружить недостатки генераторов, влияющие на точность решения известных задач. Генератор Mersenne Twister удовлетворяет всем проводившимся тестам [11], в частности, тестам diehard [12], Load Tests и Ultimate Load Tests [13].

Сами авторы Mersenne Twister предлагают для оценки и сравнения качества генераторов псевдослучайных чисел наглядную количественную характеристику, называемую «равномерным распределением в k измерениях с w-битной точностью» [11]. Геометрический смысл этой характеристики состоит в следующем (рис. 1.3):

1. Рассматривается k-мерный куб с рёбрами единичной длины в каждом из измерений;

2. Генерируется последовательность случайных чисел {g_i} (g Î [0; 1], i = 0, 1, ¼, P−1) длины P, равной периоду генератора;

3. Для всех i = 0, 1, ¼, P−1 формируется P точек в k-мерном пространстве, таких, что координаты i-ой точки - (g_i, g_i+1, ¼, g_i+k-1), а при i+k > P вместо обычного сложения используется сложение по модулю P.

Рис. 1.3. Иллюстрация критерия равномерного распределения в k измерениях с w-битной точностью

4. Каждая ось единичного куба в k-мерном пространстве разбивается на 2^w интервалов, в соответствии с чем объём куба разбивается на 2^kw маленьких кубиков. Количество интервалов, равное 2^w, используется потому, что при этом в один и тот же интервал попадают все числа, у которых равны первые w-бит. Таким образом, числа сопоставляются с w-битной точностью.

5. Последовательность {g_i} является равномерно распределенной в k измерениях с w-битной точностью, если в каждый из 2^kw кубиков попадает одинаковое число точек, рассмотренных в п. 3 (на одну точку меньше для кубика, расположенного в начале координат).

Чем выше максимальные значения k(w), удовлетворяющие критерию п. 5, тем более качественным можно считать генератор псевдослучайных чисел. Как показано в работе [11], для генератора Mersenne Twister максимально достижимые (при наилучших сочетаниях всех параметров) значения k(w) даются формулой

,

где n, r - параметры генератора, w - длина используемых целых чисел в битах (у нас w = 32), совпадающая с максимальной точностью представления генерируемых случайных чисел. При n = 624, r = 31 (см. список параметров в п. 1.2.4) и w = w = 32 получается, что k_max(w) = 623. Поскольку указанные в п. 1.2.4 значения параметров [11] обеспечивают k(32) = k_max(32), генератор Mersenne Twister оказывается равномерно распределённым в 623 измерениях с 32-битной точностью.

1.2.6. Применение генератора Mersenne Twister для параллельных расчётов на графических процессорах

Параллельные генераторы с различающимися параметрами

Алгоритм Mersenne Twister может исполняться графическими процессорами архитектуры CUDA с высокой скоростью, поскольку используемая побитовая арифметика реализована в этих процессорах аппаратно.

Существует проблема, связанная с параллельным запуском нескольких (тем более многих) экземпляров одного и того же генератора псевдослучайных чисел. Даже при различных «инициализаторах» {x₀, x₁, ¼, x_n-1} такие генераторы могут создавать коррелирующие последовательности чисел, если имеют идентичные параметры (см. обсуждение в работе [11]). В частности, это справедливо и для генератора Mersenne Twister, поскольку он использует линейное рекуррентное соотношение [11].

Таким образом, экземпляры генератора Mersenne Twister, параллельно исполняемые в различных вычислительных потоках графического процессора, должны иметь различные наборы параметров (n, m, r, a, b, c, u, s, t, l). Эти параметры нельзя выбирать случайным или другим произвольным образом, во избежание ухудшения качества генератора [11]. По этой причине авторами генератора Mersenne Twister был разработан специальный алгоритм подбора параметров (DC [14]).

Алгоритм DC, в соответствии с идентификаторами вычислительных потоков, создаёт для каждого потока уникальные наборы параметров генератора, гарантирующие максимальные качество и период распределения [14]. При этом 16-битное значение идентификатора потока (ID) встраивается в параметр a, следующим образом:

.

Затем алгоритм DC подбирает значения параметров b и c, гарантирующие качественную работу генератора. Остальные параметры могут быть постоянными для всех генераторов.

Для ускорения моделирования методом Монте-Карло, наборы параметров для каждого из параллельных генераторов должны быть сгенерированы заранее и сохранены в виде массива. Это можно сделать с помощью программы на C, предложенной в работе [14]. Мы использовали реализацию этой программы на CUDA, разработанную компанией NVIDIA [15] для расчёта диффузии нейтронов через пластину.

Распределение памяти GPU между параллельными
генераторами

Отметим, что для параллельного запуска многих экземпляров Mersenne Twister на графическом процессоре плохо подходят параметры со значением n = 624 или того же порядка величины, из-за большого размера требуемой памяти. Действительно, каждому экземпляру генератора потребуется память для 3-х уникальных 32-битных параметров (a, b, c) и n 32-битных элементов инициализирующей последовательности {x₀, x₁, ¼, x_n-1}. Все эти значения необходимо хранить в регистрах GPU, для быстрого доступа.

Ниже мы рассмотрим подробности архитектуры графических процессоров, совместимых с CUDA. Сейчас отметим только, что эти GPU состоят из нескольких (на сегодня - от 1 до 30) мультипроцессоров, каждый из которых имеет 8192 либо 16384 доступных программисту 32-битных регистра. Таким образом, на каждом мультипроцессоре можно будет запустить не более 13 либо 26 параллельных генераторов c n = 624, а этого мало для полного использования ресурсов GPU. Нужны параметры с намного меньшими значениями n.

В примере параллельного генератора Mersenne Twister для CUDA [15] компанией NVIDIA предложен набор параметров {n = 19, m = 9, r = 1, u = 12, s = 7, t = 15, l = 18}. При n = 19 на каждом мультипроцессоре можно запустить 431 либо 862 параллельных генератора, чего достаточно для полной загрузки GPU. Указанные параметры сохраняют высокое качество получаемых равномерных распределений, поскольку при n = 19, m = 9 и r = 1 генератор по-прежнему имеет большой период, равный 2⁶⁰⁷ - 1 » 10¹⁸³, а также характеризуется равномерным распределением с 32-битной точностью в 18 измерениях.