Случайные числа и их генерация жизненно важны практически для любого программного обеспечения производственного уровня. Они широко используются в играх, искусственном интеллекте, функциональном тестировании и многом другом. Тем не менее, несмотря на широкое распространение в таком широком спектре приложений, алгоритмы и средства их создания практически не изменились за последние 25 лет. Как правило, генераторы псевдослучайных чисел (PRNG) делятся на две категории: криптографические и некриптографические, которые служат балансом между случайностью и скоростью. Первый из них, используемый для некриптографических вариантов использования, называется вихрем Мерсенна.

Твистер Мерсенна был первоначально разработан Макото Мацумото и Такудзи Нисимура в 1997 году. Он основан в первую очередь на концепции использования простого числа Мерсенна в качестве своего периода. Твистер Мерсенна используется в качестве генератора случайных чисел в различных популярных языках программирования, а также во многих коммерческих приложениях. Это зависит от довольно большого состояния и дает достаточную производительность. Можно ли это улучшить? Может ли PRNG превзойти производительность Mersenne Twister с минимальными жертвами случайности и использования памяти?

Я попытаюсь ответить на этот вопрос, используя другой алгоритм для генерации случайных чисел. Уникальное свойство этого альтернативного алгоритма, называемого FY5Z, заключается в том, что его можно полностью оптимизировать с помощью встроенных инструкций SIMD. Мы оценим как производительность, так и эффективность случайности по сравнению с твистером Мерсенна.

FY5Z: Перетасовка вперед

Инструкции SIMD, такие как широко распространенный набор SSE2 на машинах x86, позволяют выполнять векторные операции со 128 битами данных за раз. В случае целых чисел это означает либо два 64-битных целых числа, либо четыре 32-битных целых числа в каждом векторе одновременно. Базовые операции, такие как сложение или вычитание, обычно занимают менее одного такта на инструкцию на большинстве процессоров. Однако использования простейших операций недостаточно для эффективного или приемлемого уровня случайности. Принесение в жертву любого существенного случайного распределения ради скорости полностью противоречит цели ГПСЧ. Таким образом, необходимы более эффективные операции.

Наборы инструкций SIMD, такие как SSE2, обеспечивают специальные операции, называемые перемешиванием, которые не имеют прямого эквивалента в обычном ассемблере. Перемешивание на высоком уровне — это операции, которые изменяют порядок данных в соответствии с маской или управляющим целым числом. Думайте об этом как о параллельном обмене. Для набора SSE2 перемешивание поддерживается только для 16- или 32-битных целых чисел. Эти два типа операций, сложение и перетасовка, могут использоваться для создания эффективно большого состояния с меньшим периодом. Это работает путем переноса подсостояния перетасовки в некоторое состояние большего размера, такое как массив целых чисел. Одно перемешивание четырех 32-битных целых чисел можно представить следующим образом:

Каждая группа из четырех целых чисел перемешивается с использованием восьмибитной управляющей маски, так что каждые два бита маски представляют собой слот, который целое число в индексированном слоте должно быть помещено после операции. Например, если первое двухбитовое целое число в маске равно 3, это означает, что первое 32-битное целое число в 128-битном векторе перемещается в последний слот результирующего вектора.

Допустим, есть вектор из n 32-битных целых чисел. Чтобы перетасовать все целые числа, нужно перетасовать каждые четыре целых числа, пока мы не перемешаем всего n целых чисел. Однако цель состоит в том, чтобы создавать псевдослучайные числа, а не просто их перемешивать. Для увеличения так называемого периода в генераторах случайных чисел требуется какая-то другая операция, т. е. количество поколений, предшествующих повторению числа. В этом случае будет использоваться добавление перетасованных целых чисел к другому вектору, который сохраняет свое состояние из поколения в поколение. Это гарантирует, что будет большая изменчивость и распространение.

Две операции могут быть объединены в то, что называется прямым тасованием, вектором, который формируется суммой всех операций тасования по большему вектору состояния. Такую операцию можно представить следующим образом:

Тест: производительность

Первый тест, чтобы победить твистер Мерсенна, касается производительности. Можно ли написать PRNG для более быстрой генерации псевдослучайных чисел? В этом тесте сравниваются реализации Mersenne Twister и Fy5z на четырехъядерном процессоре Intel Haswell i7. Для реализации Fy5z порядок прямого перетасовывания проверяется как линейно, где каждая часть состояния вектора тасуется и суммируется последовательно, так и в версии блочного шифра, где порядок перетасовки находится в хаотическом порядке. Для дополнительной энтропии и случайности используется дополнительная маска над значениями, которые добавляются к перемешанным целым числам. Таким образом, вместо того, чтобы просто добавлять перемешанные целые числа обратно к предыдущему вектору, они добавляются к маске, а затем сохраняются в векторе состояния. Реализация Fy5z ниже:

Эта реализация будет протестирована против стандартной реализации вихря Мерсенна на языке C, которую можно найти здесь. Результаты, усредненные по 50 попыткам генерации 10 миллионов случайных чисел в микросекундах, таковы:

Running: 'Mersenne Twister' took 109224 u/s
Running: 'fy5z' took 62958 u/s
Running: 'fy5z_block' took 67703 u/s

К счастью, реализация Fy5z превосходит Mersenne Twister. Почему это может быть? Во-первых, MT работает на целочисленной основе, это скалярный алгоритм. Где это новое перетасовка вперед выполняется параллельным векторным способом. Учитывая, что это не попытка использовать AVX и более поздние инструкции SIMD, риск разгона на уровне ЦП практически отсутствует. Здесь действительно кажется, что «блочный» вариант работает несколько медленнее, чем неблочный вариант. Это может быть по ряду причин, но, в первую очередь, дополнительные накладные расходы на индексирование массива static скалярным способом (без векторизации) могут снизить производительность.

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

Тест: Случайность

Мы можем проверить реализации PRNG на случайность несколькими способами. Однако наиболее ярким и подробным способом является графическое и графическое тестирование. Для этого теста оба PRNG будут генерировать некоторый эквивалент случайных двумерных координат. Эти координаты будут использоваться для нанесения черных точек на оранжевый «холст». Цель состоит в том, чтобы создать картину того, как выглядит вывод каждого генератора, а также распределение и расположение каждого генерируемого вывода.

Для этого можно использовать проект cmake и простую программу на C, которая использует libpng, оригинальную библиотеку, разработанную для обработки и редактирования изображений Portable Network Graphics (PNG), для графика сгенерированных случайных чисел. Изображения, которые вы видите ниже, представляют собой изображения в формате png с глубиной цвета 1 бит и палитрой из 2 цветов. Это означает, что каждый пиксель представлен одним битом, что обеспечивает высокую степень сжатия. Первый результат для Fy5z:

Затем результат Mersenne Twister:

Как видно, между ними есть заметная разница. Хотя версия Fy5z по-прежнему обеспечивает псевдослучайное распределение, она имеет редко видимые линии и, по сравнению с изображением Mersenne Twister, перекрывающиеся координаты. Вихрь Мерсенна, с другой стороны, почти не имеет заметных закономерностей и выглядит более рандомизированным.

Почему это так ? Один из возможных вариантов — это период. Fy5z имеет более короткий период, чем Mersenne Twister, что может привести к большему количеству столкновений за то же количество поколений. В целом, эти тесты показывают, что более быстрые реализации ГПСЧ действительно возможны. Тем не менее, это может привести к снижению случайности, и требуется больше должной осмотрительности для создания PRNG, которые отличаются максимальной производительностью и случайностью.