Интернет Университет Суперкомпьютерных технологий Лекция 5 Параллельная генерация псевдослучайных чисел Учебный курс Введение в параллельные алгоритмы Якобовский М.В., д.ф.-м.н. Институт математического моделирования РАН, Москва

Численное моделирование –Методы молекулярной динамики –Генетические алгоритмы Численные методы –Многомерная многоэкстремальная оптимизация –Определение многомерных интегралов Принятие решения Игры Лотереи Задачи, решаемые с применением последовательностей псевдослучайных чисел Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 2 из 45

Определение площади фигуры Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 3 из 45

M=0; For(i=0;i

1. Каждый процессор определяет число m rank «своих» N/P точек, попавших внутрь фигуры 2. Найдем общее число точек, попавших внутрь фигуры 3. S=M/N; Параллельный алгоритм для P процессоров Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 5 из 45

Возможен большой дисбаланс нагрузки Другой параллельный алгоритм, на основе метода геометрического параллелизма Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 6 из 45

Должен ли ответ параллельной программы в точности совпадать с ответом последовательной версии? НЕТ Где взять нужное количество разных «своих» точек? Физический генератор? Нельзя обеспечить вопроизводимость. Как обеспечить уверенность в сохранении свойств генератора? ДА Каким образом на каждом из процессоров вычислить координаты именно «своих» точек, не вычисляя координаты чужих? Брать на процессоре с номером rank числа с номерами rank+P*I Как вычислять каждое P-ое число? Вычислять на процессоре с номером rank точки из диапазона (2N/P)*rank … (2N/P)*(rank+1)-1 Как попасть в начало диапазона? Вопросы Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 7 из 45

Если брать на процессоре с номером rank числа с номерами rank+P*j, то –При P=1: (0,1), (2,3), (4,5), (6,7), (8,9, (10,11) –При P=2: У первого процесса: (0,2), (4,6) (8,10) У второго процесса: (1,3), (5,7), (9,11). Идентичность точек нужна: –Для получения одинакового результата –Для упрощения отладки –Для сохранения свойств последовательности x1 x2 x3 x4 x5 x6 x7 x8 x9 … x2 x4 x6 x8 x10 … Нарушение идентичности размещения точек Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 8 из 45

9

Решетка p=100% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 10 из 45

Перколяционная решетка p=90% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 11 из 45

Перколяционная решетка p=80% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 12 из 45

Перколяционная решетка p=70% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 13 из 45

Перколяционная решетка p=60% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 14 из 45

Перколяционная решетка p=50% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 15 из 45

Перколяционная решетка p=40% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 16 из 45

Перколяционная решетка p=30% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 17 из 45

Перколяционная решетка p=20% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 18 из 45

Перколяционная решетка p=10% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 19 из 45

Перколяционная решетка p=0% Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 20 из 45

Генерация псевдослучайных чисел Согласованность определения множества открытых ребер при параллельной обработке Возможность определения любого элемента последовательности за короткое, не зависящее от номера элемента, время Достаточная длина периода последовательности псевдослучайных чисел Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 21 из 45

линейные конгруэнтные генераторы [Лемер, 1948] с=1mod2, a=1mod4, m=2 k -> T=m Генерация псевдослучайных чисел Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 22 из 45

Вычисление элемента с номером n, Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 23 из 45

Номер шага P 0+2P 0+3P 0+4P 1+P 1+2P 4+3P 1+4P 2+P 2+2P 3+3P 2+4P 3+P 3+2P 2+3P 3+4P 4+P 4+2P 1+3P 4+4P. Использование для векторных компьютеров Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 24 из 45

Как быстро вычислить? Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 25 из 45

За log(n) шагов Вычислить a^n Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 26 из 45

Бинарное умножение Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 27 из 45

Как вычислить быстро?, Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 28 из 45

Разложение дроби, Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 29 из 45

Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 30 из 45

Другой способ Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 31 из 45

Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. Другой способ 32 из 45

При с=0 d-мерные точки расположены не более чем в гиперплоскостях [G. Marsaglia 1968] Для RANDU(IBM 360/370) a= , m=2 31, c=0 Не более 16-ти плоскостей [ Richard P.Brent, 1992 ] Линейные конгруэнтные генераторы [Лемер, 1948] Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 33 из 45

Случайные точки Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. Последовательность 512 точек вида лежат на нескольких прямых 34 из 45

Случайные точки Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. Последовательность 1024 точки вида лежат менее регулярно 35 из 45

Генератор на сдвиговом регистре [ П.Хоровиц,У.Хилл, 1983 ] М-последовательности [ И.М. Соболь, 1973 ] М-последовательности Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 36 из 45

Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. ABCD F=(A+D)mod2 D=C C=B B=A A=F ABCD (A+D )% Москва, 2009 г. Генерация псевдослучайных чисел 37 из 45

Связь между и фрагментом M последовательности Если то Richard P. Brent On the period of generalized Fibonacci recurrences, 1992 Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 38 из 24

Генерация элемента с произвольным номером k Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 39 из 24

Порог перколяции размер сетки х х х размер сетки 800 х 800 х х 800 х х х х х Точное значение 0.5 Точное значение (5) [ Ю. Ю. Тарасевич, 2002] Ю. Ю. Тарасевич Н. Н. Медведев Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 40 из 24

P=0 P < P < P < P 0.99 P > 0.99 P > P > P=1 a bcdDCB A LRND SWBMWC MWC MIXRNDX MIXRNDXY BRND RAND Батарея тестов Diehard Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 41 из 45

Тестируемые последовательности BRND MIXRND рандомизация перемешиванием MWC генератор на основе метода умножения с переносом MWC, период 4*10^18 SWBMWC комбинированный генератор на основе методов умножения с переносом MWC и Фибоначчи с запаздыванием SWBG, период 4*10^364 Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 42 из 45

Сформулированы требования к генераторам псевдослучайных чисел для многопроцессорных сиcтем Рассмотрены параллельные алгоритмы генерации псевдослучайных чисел Заключение Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. Москва, 2009 г. 43 из 45

И.М.Соболь. Численные методы Монте-Карло. – М.: Наука, Richard P. Brent, Uniform Random Number Generators for Supercomputers, Computer Sciences Laboratory; Australian National University Appeared in Proceedings Fifth Australian Supercomputer Conference (Melbourne, December 1992), c 1992, 5ASC Organising Committee. Кнут Дональд Эрвин, искусство программирования, том.2. Получисленные алгоритмы, 3-е издание.: Пер с англ., : Уч пос - М.: Издательский дом, с., ил. G. Marsaglia, "Random numbers fall mainly on the planes", Proc. Nat. Acad. Sci. USA 61, 1 (1968), П.Хоровиц, У.Хилл. Искусство схемотехники: В 2-х томах. Пер. с англ. – М.: Мир, Т.2 590с. Л.Ю. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел, Безопасность информационных технологий, 2 (2005) Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел В.Жельников. Криптография от папируса до компьютера – М., ABF, 1996, ил., 336 с. Якобовский М.В. Библиотека генерации псевдослучайных чисел lrnd32. Дистрибутив. 2007, Литература Москва, 2009 г. Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. 44 из 45

Якобовский М.В. д.ф.-м.н., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей» Института математического моделирования Российской академии наук mail: web: Контакты Введение в параллельные алгоритмы: Параллельная генерация псевдослучайных чисел © Якобовский М.В. Москва, 2009 г. 45 из 45