Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

Глава 12. Расширенные методы построения параллельных 
алгоритмов 
 
12.1. Генерация псевдослучайных чисел
Последовательности случайных чисел (ПСЧ) используются при 
решении задач многомерной многоэкстремальной оптимизации, при 
вычислении кратных интегралов, при изучении поведения сложных систем 
методами имитационного моделирования и молекулярной динамики, при 
разработке игр и анализе стратегий поведения, при создании реалистичных 
сцен виртуальной реальности и во многих других приложениях. 
Использование случайных чисел, предполагает проведение множества 

---

115 
вычислительных экспериментов с уникальным набором случайных чисел для 
каждого эксперимента. Ответ формируется путем обработки результатов 
экспериментов и точность его тем выше, чем больше экспериментов 
проведено. Данная модель вычислений характеризуется наличием 
внутреннего параллелизма. Независимые эксперименты могут быть 
выполнены одновременно, каждый на своем процессоре. При этом 
необходимо указать метод формирования на каждом из процессоров 
уникального набора случайных чисел, с тем, что бы эксперименты, 
выполненные на разных процессорах, не дублировали друг друга 
Требования к генераторам псевдослучайных чисел для МВС 
При решении задач стохастическими (недетерминированными, 
использующими случайные числа или их имитацию) методами используется 
два вида генераторов последовательностей чисел:
-
генераторы случайных чисел, основанные на некоторых физических 
принципах;
-
генераторы 
псевдослучайных 
чисел, 
основанные 
на 
детерминированных алгоритмах.
Генераторы случайных чисел, основанные на физических 
принципах: 
-
обеспечивают 
формирование 
произвольно 
длинных 
последовательностей случайных чисел; 
-
обеспечивают формирование на различных процессорах различных 
последовательностей;
-
не обеспечивают воспроизводимость результатов, что является 
преимуществом с точки зрения криптографических приложений и является 
недостатком с точки зрения удобства отладки вычислительных приложений. 
Отсутствие воспроизводимости затрудняет отладку приложений; 
-
свойства формируемых последовательностей могут меняться в 
зависимости от таких параметров окружающей среды. Например, класс 
физических генераторов, основанных на комбинации простых осцилляторов, 

---

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