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

 
u [num (rank)]… u[num (rank+1) –
1
]. Каждый 
процессор использует большой непрерывный фрагмент одной и той же 
последовательности 
u
(skip-
ahead метод). Если рассмотреть применение 
метода в пределах приведенного выше примера с точками, то метод 
позволяет использовать в первом процессе числа с номерами (0,…,8), во 
втором ‒
(9,…,17), формируя тот же набор пространственных точек, что и 
при последовательной обработке. Эффективные параллельные методы 
требуют возможности формирования фрагментов последовательности, 
начинающихся в
требуемых местах, без вычисления на каждом процессоре 
всех предшествующих фрагменту элементов исходной последовательности. 
Требования, предъявляемые к генераторам псевдослучайных 
чисел, предназначенных для использования на многопроцессорных 
системах
:

---

119 
1) возможность формирования последовательности достаточно 
большой длины; 
2) возможность определения любого элемента последовательности за 
короткое время без вычисления всех ее предыдущих членов.
Линейно
-
конгруэнтные генераторы
 
Линейные конгруэнтные генераторы (22) позволяют с помощью 
соотношений (23) 
- 
(24) одновременно вычислять на векторном компьютере, 
оснащенном 
k 
процессорами, очередные 
k 
элементов последовательности, 
используя для вычисления каждого элемента порядка 
O(1)
операций [2].
Для этого достаточно один раз предварительно вычислить величины
 a
k
 mod m
и
Выражение (23) позволяет вычислять элементы с произвольным 
номером n, используя порядка 
O(logn)
операций.
Например, понизим вдвое 
степени стоящих в скобках слагаемых. Используя (25), можно преобразовать 
(23) к виду (26) где