СПОСОБ ГЕНЕРАЦИИ ПАРАЛЛЕЛЬНЫХ ПОТОКОВ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ И УСТРОЙСТВА ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ (2 ВАРИАНТА) Российский патент 2015 года по МПК G06F7/58 

Изобретение относится к вычислительной технике, а более конкретно к способам и устройствам параллельной генерации псевдослучайных чисел, в том числе генерации параллельных некоррелированных потоков псевдослучайных чисел. Область использования: решение задач с применением вычислительной техники, в которых необходимо использование псевдослучайных чисел, например, основанных на методе Монте-Карло и, в особенности, при выполнении на параллельных и гибридных суперкомпьютерных системах.

Известны два основных типа генераторов. Первые - это устройства, использующие стохастические свойства некоторых физических процессов, как входные сигналы для реализации способов оцифровывания и преобразования в машинное слово. Такие устройства носят название генераторы случайных чисел (ГСЧ). Вторые - это устройства, использующие способ преобразования машинных слов. Такие устройства носят название генераторы псевдослучайных чисел (ГПСЧ) (В.А. Успенский. Четыре алгоритмических лица случайности. - МЦНМО, 2006. - 48 с.).

Существующие ГСЧ производят последовательность (поток) случайных чисел, который не имеет начального значения, что делает их неприменимыми для целей отладки и верификации программных систем и программно-аппаратных комплексов. Для генерации N параллельных потоков случайных чисел с использованием существующих ГСЧ требуется наличие N параллельных ГСЧ либо устройства коммутации одного потока чисел на N программно-аппаратных модулей. В обоих подходах имеется недостаток, связанный с резким увеличением стоимости вычислительной техники и связанный также с не универсальностью комплекса. Во втором случае это также приводит к резкой потере производительности, что является существенным недостатком.

Существующие ГПСЧ могут производить последовательности случайных чисел хорошего качества. Основная проблема состоит в начальном значении последовательности. Для этого существуют устройства получения начального значения от случайного процесса, например устройство оцифровывания интенсивности хаотического полупроводникового лазера, описанного в источнике информации I. Reidler et al., Physical Review Letters том 103, статья 024102, 2009 г., 10.1103/PhysRevLett.103.024102. Недостаток применяемого в данном случае способа инициализации не позволяет достоверно получить N некоррелированных последовательностей псевдослучайных чисел.

Известен способ и устройство генерации последовательностей псевдослучайных чисел (ПСЧ) с произвольными фазами по патенту № US 0130420, дата приоритета 29.09.2000. Данный способ генерирования последовательностей ПСЧ с произвольными фазами уменьшает время, необходимое для корреляции поступающих сигналов от базовой станции в системе беспроводной связи, по которому идентифицируют текущий сдвиг ПСЧ.

Известны способ и устройство генерации ПСЧ по патенту № СА 2756430, дата приоритета 03.11.2010, в котором используются две электрические схемы для получения начального значения для генератора ПСЧ.

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

Известен генератор ПСЧ по авторскому свидетельству № SU 868734, дата приоритета 10.09.1979, в котором при помощи набора параллельных устройств добавляется смеситель сигналов, комбинирующий выходные данные от набора параллельных устройств в выходные ПСЧ. Недостаток данного решения состоит в короткой последовательности ПСЧ, а также в ограниченном числе параллельных потоков ПСЧ (не более 100).

Известны способ и устройство формирования стартового значения для генератора ПСЧ по патенту № RU 2292074, дата приоритета 27.09.2004, в соответствии с которыми стартовое значение для генератора ПСЧ формируется с помощью оценки скоростей источников и их классификации. Недостаток этого устройства состоит в отсутствии возможности формирования стартовых значений для N параллельных потоков ПСЧ.

Известен способ генерации случайных чисел по патенту № RU 2246129, дата приоритета 13.01.2003, относящийся к криптографии и средствам защиты информации от несанкционированных действий, в котором используются нелинейные обратные связи в последовательности ПСЧ. Недостатком этого метода является отсутствие качества непредсказуемости и наличие заметных корреляций в последовательности ПСЧ, что приводит к плохим статистическим свойствам ПСЧ.

Наиболее близким аналогом заявляемого изобретения является техническое решение по патенту № IL 177160 В, дата приоритета 26.02.2004. Устройство по данному патенту также, как и в предлагаемом изобретении, состоит из двух частей - генератор получения начального значения и генератор ПСЧ. Это устройство получает начальные данные от ГСЧ и использует их в ГСПЧ для генерации последовательности псевдослучайных чисел. В наиболее близком аналоге используется внешний источник случайности для генерации ПСЧ (на вход второго блока), в качестве дополнительного элемента при генерации ПСЧ используется смесительная логика.

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

Задачей, на решение которой направлено заявляемое изобретение, является обеспечение возможности повторения последовательности при генерации устройством параллельных некоррелированных потоков псевдослучайных чисел для их использования в суперкомпьютерах, в том числе гибридных (с использованием графических вычислительных процессоров, программируемых логических интегральных схем и других вычислительных устройств), для широкого круга применений.

Техническим результатом от использования изобретения является возможность генерации N (N не менее миллиарда) начальных значений и отсутствие корреляций при их использовании между не менее N потоками ПСЧ. При этом имеется возможность создания эталонных последовательностей и их использования в целях тестирования и верификации программных и аппаратных систем и устройств. Устройство при этом является масштабируемым и имеет стандартный интерфейс связи с вычислительным устройством, что дает возможность его использования в широком классе вычислительных устройств без внесения изменений в их функциональные схемы.

Технический результат достигается при помощи способа генерации параллельных потоков псевдослучайных чисел, включающего способ генерации случайных чисел, в котором случайные числа генерируются после инициализации с помощью устройства генерации начальных значений, отличающегося тем, что входной интерфейс с вычислительным устройством осуществляет запись в промежуточную память заданных параметров способа генерации, осуществляет вычисление коэффициентов генерирующей функции в зависимости от заданных параметров способа генерации, осуществляет формирование начального значения для заданного числа потоков ПСЧ, осуществляет вычисление элементов (битов) ПСЧ из координат единичного квадрата при повторяющемся линейном преобразовании единичного квадрата, осуществляет формирование прообраза n-битного ПСЧ из n элементов (битов) ПСЧ с записью в промежуточный регистр, осуществляет формирование ПСЧ за счет использования сдвига регистра, осуществляет запись сформированного ПСЧ в элемент памяти для дальнейшего использования, осуществляет формирование потока ПСЧ из сформированных ПСЧ, осуществляет передачу потоков ПСЧ в вычислительное устройство.

Также технический результат достигается при использовании устройства генерации параллельных потоков псевдослучайных чисел, содержащего генератор получения начального значения и генератор ПСЧ, отличающегося тем, что содержит устройство формирования начального значения для N генераторов псевдослучайной последовательности чисел при отсутствии источника случайных данных, средство записи в промежуточную память параметров способа генерации, средство вычисления коэффициентов генерирующей функции в зависимости от заданных параметров способа генерации, средство формирования начального значения по коэффициентам генерирующей функции.

Также технический результат достигается при использовании устройства генерации параллельных потоков псевдослучайных чисел, содержащего генератор получения начального значения и генератор ПСЧ, отличающегося тем, что содержит устройство вычисления потока ПСЧ, средство вычисления элементов (битов) ПСЧ из координат единичного квадрата при повторяющемся линейном преобразовании единичного квадрата, средство формирования прообраза n-битного ПСЧ из n элементов (битов) ПСЧ, средство записи в промежуточные регистры, средство сдвига элементов (битов) регистра, элемент памяти, средство записи ПСЧ в элемент памяти, средство формирования потока ПСЧ из записанных в память ПСЧ, средство передачи потока ПСЧ в вычислительное устройство.

Изобретение иллюстрируется следующими чертежами: фиг. 1, на которой представлен алгоритм, т.е. последовательность операций заявляемого способа формирования начального значения; фиг. 2, на которой представлен алгоритм, т.е. последовательность операций заявляемого способа генерации последовательности ПСЧ; фиг. 3, на которой представлена структурная схема заявляемого устройства, осуществляющего способ формирования начального значения и способ генерации потока ПСЧ.

Как показано на фиг. 1, в соответствии с заявляемым способом параметры поступают на вход блока промежуточной памяти 1. Далее параметры поступают в блок вычисления коэффициентов генерирующей функции 2. Блок вычисления коэффициентов генерирующей функции вычисляет коэффициенты на основе параметров, поступивших из промежуточной памяти 1. Вычисленные коэффициенты используются в блоке формирования генерирующей функции 3. По сформированной генерирующей функции вычисляются N начальных значений в блоке вычисления начальных значений 4.

Как показано на фиг. 2, N начальных значений поступают на вход блока параллельной генерации N потоков последовательности ПСЧ 5. Блок коммутации 6 осуществляет передачу N-ного начального значения в соответствующее N-ному потоку устройство генерации потока ПСЧ 7.1-7.N. Каждое устройство генерации ПСЧ осуществляет операцию преобразования единичного квадрата, приводящего к генерации элемента (бита) ПСЧ 8.1-8.N. Блок формирования прообраза ПСЧ 9.1-9.N осуществляет формирование прообраза ПСЧ и его запись в промежуточный регистр 10.1-10.N. Блок сдвига осуществляет 11 сдвиг в промежуточном регистре. Блок коммутации 12 осуществляет выдачу значения ПСЧ вычислительному устройству с указанием номера потока в диапазоне от 1 до N.

Как показано на фиг. 3, устройство состоит из блока генерации начального значения 13, блока генерации потоков ПСЧ 14 и блока коммутации устройства 15 с вычислительным устройством.

Поток ПСЧ формируется в памяти за счет того, что при извлечении одного бита из n параллельно вычисляемых значений координаты единичного квадрата при его линейном преобразовании, записи этого бита в регистр на n-ную позицию, циклического сдвига битов регистра на величину целочисленного параметра S, записи сформированного значения в регистре ПСЧ в элемент памяти, при этом запись производится в последовательно расположенные ячейки памяти, адрес которых формируется счетчиком ПСЧ.

Устройство вычисления потока ПСЧ формируется при параллельном линейном преобразовании n единичных квадратов, средство вычисления n элементов (битов) ПСЧ на основе n координат единичного квадрата, средство формирования прообраза n-битного ПСЧ из n элементов (битов) ПСЧ, средство записи битов в n-ую битовую позицию промежуточного регистра, средство сдвига элементов (битов) регистра, элемент памяти, средство записи ПСЧ в элемент памяти, средство формирования потока ПСЧ за счет записи в память последовательных значений ПСЧ, сформированных в регистре, средство передачи потока ПСЧ в вычислительное устройство за счет передачи адреса начального ПСЧ в последовательных ячейках памяти.

Запись входным интерфейсом заданных параметров способа генерации в промежуточную память, существенными из которых являются коэффициенты линейного преобразования единичного квадрата, число n бит в ПСЧ и величина циклического сдвига.

Линейное преобразование координат единичного квадрата осуществляется блоком формирования генерирующей функции (описано в источнике информации, ставшем общедоступным до даты приоритета заявленного изобретения L. Barash, L.N. Shchur, Periodic orbits of the ensemble of Sinai-Arnold cat maps and pseudorandom number generation, Phys. Rev. E 73, 036701 2006 г., ), используются заданные через внешний интерфейс параметры способа генерации.

Таким образом, предлагаемый в качестве изобретения способ гарантирует отсутствие корреляций как вдоль каждого потока, так и между потоками, при использовании на компьютерах вплоть до экзафлопного масштаба. Архитектура устройства адаптирована под новый способ генерации параллельных потоков ПСЧ и обеспечивает генерацию начальных значений потоков.

Изобретение предназначено для использования в параллельных и гибридных суперкомпьютерных системах, таких как Jaguar-Cray ХТ5-НЕ, которые применяются в для такого моделирования, но не исчерпывается им, как моделирование атмосферных явлений, моделирование газодинамики обтекания летательных и плавательных тел, моделирование процессов прохождения излучения через вещество, моделирование процессов в земной коре и моделирования физических задач методом Монте-Карло, в которых при моделировании используются последовательности псевдослучайных чисел.

Изобретение относится к вычислительной технике и может быть использовано для генерации потоков псевдослучайных чисел (ПСЧ). Техническим результатом является возможность генерации N начальных значений и отсутствие корреляций при их использовании между не менее N потоками ПСЧ. Устройство содержит генератор получения начального значения и генератор ПСЧ, который содержит устройство вычисления потока ПСЧ, средство вычисления битов ПСЧ из координат единичного квадрата, средство формирования прообраза n-битного ПСЧ из n битов ПСЧ, средство записи в промежуточные регистры, средство сдвига битов регистра, элемент памяти, средство записи ПСЧ в элемент памяти, средство формирования потока ПСЧ из записанных в память ПСЧ, средство передачи потока ПСЧ в вычислительное устройство. 3 н.п. ф-лы, 3 ил.

1. Способ генерации параллельных потоков псевдослучайных чисел, включающий способ генерации случайных чисел, в котором случайные числа генерируются после инициализации с помощью устройства генерации начальных значений, отличающийся тем, что входной интерфейс с вычислительным устройством осуществляет запись в промежуточную память заданных параметров способа генерации, осуществляет вычисление коэффициентов генерирующей функции в зависимости от заданных параметров способа генерации, осуществляет формирование начального значения для заданного числа потоков ПСЧ, осуществляет вычисление битов ПСЧ из координат единичного квадрата, осуществляет формирование прообраза n-битного ПСЧ из n битов ПСЧ с записью в промежуточный регистр, осуществляет формирование ПСЧ за счет использования сдвига регистра, осуществляет запись сформированного ПСЧ в элемент памяти, осуществляет формирование потока ПСЧ из сформированных ПСЧ, осуществляет передачу потоков ПСЧ в вычислительное устройство.

2. Устройство генерации параллельных потоков псевдослучайных чисел, содержащее генератор получения начального значения и генератор ПСЧ, отличающееся тем, что генератор получения начального значения содержит устройство формирования начального значения для N генераторов псевдослучайной последовательности чисел при отсутствии источника случайных данных, средство записи в промежуточную память параметров способа генерации, средство вычисления коэффициентов генерирующей функции в зависимости от заданных параметров способа генерации, средство формирования начального значения по коэффициентам генерирующей функции.

3. Устройство генерации параллельных потоков псевдослучайных чисел, содержащее генератор получения начального значения и генератор ПСЧ, отличающееся тем, что генератор ПСЧ содержит устройство вычисления потока ПСЧ, средство вычисления битов ПСЧ из координат единичного квадрата, средство формирования прообраза n-битного ПСЧ из n битов ПСЧ, средство записи в промежуточные регистры, средство сдвига битов регистра, элемент памяти, средство записи ПСЧ в элемент памяти, средство формирования потока ПСЧ из записанных в память ПСЧ, средство передачи потока ПСЧ в вычислительное устройство.