Спосіб генерації паралельних потоків псевдовипадкових чисел і пристрою для його здійснення (2 варіанти)

 

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

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

Існуючі ГВЧ виробляють послідовність (потік) випадкових чисел, який не має початкового значення, що робить їх непридатними для цілей діагностики і верифікації проЕпользованием існуючих ГВЧ потрібна наявність 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).

Відомі спосіб і пристрій формування стартового значення для генератора ПСЧ за патентом № UA 2292074, дата пріоритету 27.09.2004, у відповідності з якими стартове значення для генератора ПСЧ формується з допомогою оцінки швидкостей джерел та їх класифікації. Недолік цього пристрою полягає у відсутності можливості формування стартових значень N паралельних потоків ПСЧ.

Від�едствам захисту інформації від несанкціонованих дій, в якому використовуються нелінійні зворотні зв'язки в послідовності ПСЧ. Недоліком цього методу є відсутність якості непередбачуваності і наявність помітних кореляцій в послідовності ПСЧ, що призводить до поганих статистичними властивостями ПСЧ.

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

Недоліком цього способу і пристрою є відсутність можливості генерації пристроєм паралельних потоків псевдовипадкових чисел, спосіб при цьому не робить можливим повторення послідовності, що важливо при верифікації програмних продуктів, в яких такий пристрій могло б бути використане, до примеѵчение можливості повторення послідовності при генерації пристроєм паралельних некорельованих потоків псевдовипадкових чисел для їх використання в суперкомп'ютерах, у тому числі гібридних (з використанням графічних обчислювальних, програмованих логічних інтегральних схем та інших обчислювальних пристроїв), для широкого кола застосувань.

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

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

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

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

Як показано на фіг. 1, згідно з заявленим способом параметри надходять на вхід блоку проміжної памфициентов генеруючої функції обчислює коефіцієнти на основі параметрів, надійшли з проміжної пам'яті 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-ну позицію, циклічного зсуву бітів регістра на величину цілочисельного параметра 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-НЕ, які застосовуються для такого моделювання, але не вичерпується ним, як моделювання атмосферних явищ, моделювання газодинаміки обтікання літальних та судноплавних тіл, моделювання процесів проходження випромінювання через речовину, моделювання процесів у земній корі та моделювання фізичних задач методом Монте-Карло, в яких при моделюванні використовуються послідовності псевдовипадкових чисел.

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

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

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



 

Схожі патенти:

Генератор випадкових чисел

Даний винахід відноситься до генератора випадкових чисел для надання випадкового числа і/або комбінації випадкових чисел та/або матриці випадкових чисел. Технічний результат полягає в підвищенні достовірності даних, що надаються і які відображаються під час гри. Генератор випадкових чисел містить пристрій спостереження для спостереження за щонайменше одним пристроєм професійної/майстерні спортивної гри, в якому професійна/майстерня спортивна гра може здійснюватися щонайменше одним учасником, яка надає щонайменше один результат гри, при цьому пристрій спостереження містить засіб визначення результату гри для визначення результату гри, і пристрій визначення для визначення випадкового числа і/або комбінації випадкових чисел та/або матриці випадкових чисел з ще одних певних результатів ігор. 16 з.п. ф-ли, 3 іл.

Генератор нелінійних псевдовипадкових послідовностей

Винахід відноситься до обчислювальної техніки і може бути використане у цифрових обчислювальних пристроях для формування кодових послідовностей. Технічний результат полягає в розширенні функціональних можливостей за рахунок розширення класу формованих послідовностей шляхом додавання на h-розрядний вихід пристрою-прототипу модуля, що містить h/3 нелінійних перетворювачів, кожен з яких має три двійкових входу і двухбитовий вхід, а також блоку з h мультиплексорів з двома входами даних кожен і з спільним керуючим входом. Технічний результат досягається за рахунок того, що в генератор нелінійних псевдовипадкових послідовностей введені h/3 однотипних нелінійних перетворювача з трьома входами даних і двома виходами, hmod3=0, і блок з h мультиплексорів з двома входами даних кожен і з спільним керуючим входом, кожен з нелінійних перетворювачів містить інвертор, чотири функціональних перетворювача і чотири конъюнктора на два входи і два дизъюнктора на два входи. 3 іл., 1 табл.

Генератор корельованих випадкових сигналів

Винахід відноситься до області обчислювальної техніки і може бути використане для створення широкосмугових випадкових стаціонарних сигналів з заданими власними та взаємними спектральними густинами потужності. Технічним результатом є генерування двох випадкових сигналів із заданою функцією когерентності. Пристрій містить однопроцесорний комп'ютер, програмне забезпечення для формування за заданими спектральними щільності Sx(f) і Sy(f) випадкових сигналів у формі розкладання Райса-Пірсона з випадковими на кожній гармоніці fi фазами Θi і Ωi, що визначаються методом випадкової вибірки випадкової величини, одна з яких - Θi для сигналу x(f) рівномірно розподілена в діапазоні [-π, π], а інша - Ωi для другого сигналу y(t), визначається як сума Ωi=Θi+Δφi випадкової величини Θi і випадкової величини Δφi, рівномірно розподіленої в діапазоні [-φi, φi], межі якого визначаються через взаємну спектральну щільність Sxy(f) випадкових сигналів x(t) і y(t) з подальшим виконанням процедури ОБПФ, модуля цифро-аналогового перетворювача для перекладу сформованих цифрових сигналів в аналогові сигнали генератора. 1 іл.

Спосіб формування корельованих випадкових сигналів

Винахід відноситься до способів створення широкосмугових випадкових процесів із заданими власними та взаємними спектральними густинами потужності і може бути використане в приладобудуванні, машинобудуванні, обчислювальної техніки для створення, зокрема, багатоканальних автоматичних систем, випробування на вібростійкість до впливів випадкової вібрації. Технічним результатом є генерування двох випадкових сигналів із заданою функцією когерентності. Спосіб включає формування у часовій області за заданими спектральними щільності Sx(f) і Sy(f) стаціонарних випадкових сигналів x(f), y(t) у формі розкладання Райса-Пірсона з випадковими на кожній гармоніці fi фазами Θi і Ωi, що визначаються методом випадкової вибірки випадкової величини, одна з яких - Θi для сигналу x(t) рівномірно розподілена в діапазоні [-π, π], а інша - Ωi для другого сигналу y(t) визначається як сума Ωi=Θi+Δφi випадкової величини Θi і випадкової величини Δφi, рівномірно розподіленої в діапазоні [-φi, φi], межі якого визначаються через взаємну спектральну щільність Sxy(f) випадкових сигналів x(t) і y(t). 1 іл.

Генератор випадкової послідовності

Винахід відноситься до обчислювальної техніки і призначене для генерації випадкової послідовності значень заданої множини значень з необхідними характеристиками генерується послідовності. Технічним результатом є створення генератора, що забезпечує генерацію послідовності значень заданої множини значень з урахуванням наявності ймовірнісної зв'язку кожного чергового значення з попереднім. Пристрій містить перший селектор-мультиплексор, другий селектор-мультиплексор, перший регістр, джерело випадкових чисел, оперативне запам'ятовуючий пристрій, K≥2 блоків зберігання меж інтервалів, K блоків порівняння, шифратор пріоритетів, N≥1 інверторів, другий регістр. 2 іл.

Спосіб і пристрій детектування

Пропоновані спосіб і пристрій відносяться до галузі електронних детекторів, які реєструють зміни електромагнітного фону навколишнього середовища. Основна сфера застосування - визначення емоційного стану свідомості, розваги та електронні ігри з інтерактивним управлінням, технічні засоби для рішень в області декоративних і дизайнерських робіт, для облаштування інтер'єрів, пристроїв освітлення і підсвічування. Досягнутий технічний результат - підвищення чутливості та достовірності детектування. Спосіб детектування характеризується тим, що задають вихідний електричний сигнал від джерела шуму, який шляхом посилення, фільтрації перетворюють у випадкову імпульсну послідовність, що складається з імпульсів високого і низького рівня напруги, яку перетворюють в послідовність числових значень, здійснюють вибірку числових значень з цієї послідовності на певному проміжку часу та шляхом аналізу числових значень у вибірці одержують детектируемий сигнал, при цьому послідовність числових значень отримують шляхом обчислення в заданому проміжку часу різниці між тривалістю імпульсів високого і низького рівня нап�і числових значень у вибірці. Пристрій містить джерело шумового сигналу, три підсилювача, мікропроцесорний блок, який здійснює обчислення дисперсії і її аналіз, дві частотно-залежні ланцюга і світлодіодний індикатор. 2 н. і 4 з.п. ф-ли, 4 іл.

Спосіб нелінійного тривимірного многораундового перетворення даних dozen

Винахід відноситься до обчислювальної техніки та електрозв'язку, призначений для вирішення завдань захисту комп'ютерної інформації, може використовуватися при побудові генераторів псевдовипадкових чисел, а також криптографічних примітивів хешування, блочного і потокового шифрування. Досягнутий технічний результат - підвищення криптостійкості і швидкодії нелінійного перетворення. Спосіб включає представлення вхідних 1 і 2 вихідних блоків даних, всіх проміжних результатів S перетворень і раундових ключів (RoundKeys) 30, 31, 32, 33 у вигляді кубічного масиву байтів 4×4×4, визначення поняття шару 4 (Layer) - квадратного масиву байтів 4×4, подання i-го раундового ключа у вигляді чотирьох підключів (RoundSubKeys) 3i0, 3i1, 3i2, 3i3, i=1, 2, 3, кожен з яких суть квадратний масив байтів 4×4, додавання 10 (XOR) блоку 1 даних з раундовим ключем 30, тривимірне перетворення блоку даних по верствам 4x0, 4x1, 4х2, 4x3, 4у0, 4у1, 4у2, 4у3, 4z0, 4z1, 4z2, 4z3 відповідно вздовж осей x, у, z, включення до складу операції двомірного перетворення шару (T-Layer) 5 чотирьох кроків: заміну 6 байтів (SubBytes), перемішування 7 рядків (MixRows), перемішування 8 стовпців (MixColumns), додавання (XOR) 9 з раундовим підключеням (AddRoundSubKey). 4 іл., 1 табл.

Генератор випадкових чисел на основі тризначної логіки

Винахід відноситься до обчислювальної техніки і може бути використане при обчисленнях методом Монте-Карло і для генерації випадкових ключів у схемах шифрування. Технічним результатом є збільшення швидкості роботи генератора. Пристрій складається з однакових комбінаційних схем, що працюють в трійкової логіки, що мають два входи і один вихід, об'єднаних в кільцеву схему, при цьому вихід кожної схеми з'єднаний з входом цієї схеми і з входом наступної схеми в кільцевому з'єднанні. Трійчастий сигнал з рівномірним розподілом знімається з будь-якого виходу схеми. 2 іл., 2 табл.

Генератор коливань гиперхаотических

Винахід відноситься до радіотехніки і може бути використано в якості джерела гиперхаотических електромагнітних коливань

Спосіб формування регулярних послідовностей з елементами, складеними з двійкових сигналів

Винахід відноситься до цифрової техніки і може бути використаний для генерації випадкових чисел і перетворення даних, обробки шумоподібних сигналів, ідентифікації, аутентифікації та авторизації в стохастичних системах і пристроях, системах подання та відображення інформації, інформаційно-комунікаційних та сенсорних пристроях і системах
Up!