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

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

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

M=0; For(i=0;i

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

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

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

Если брать на процессоре с номером 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 … Нарушение идентичности размещения точек Введение в параллельные алгоритмы: Последовательности псевдослучайных чисел для МВС © Якобовский М.В. Москва, 2010 г. 8 из 51

9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Номер шага 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. Использование для векторных компьютеров Введение в параллельные алгоритмы: Последовательности псевдослучайных чисел для МВС © Якобовский М.В. Москва, 2010 г. 24 из 51

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 Введение в параллельные алгоритмы: Последовательности псевдослучайных чисел для МВС © Якобовский М.В. Москва, 2010 г. 45 из 51

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

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

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 Введение в параллельные алгоритмы: Последовательности псевдослучайных чисел для МВС © Якобовский М.В. Москва, 2010 г. 48 из 51

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

И.М.Соболь. Численные методы Монте-Карло. – М.: Наука, 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, Литература Введение в параллельные алгоритмы: Последовательности псевдослучайных чисел для МВС © Якобовский М.В. Москва, 2010 г. 50 из 51

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