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

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

Метод Гаусса Москва, 2009 г. 3 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a11a12a13a14a15a16d1a11a12a13a14a15a16d1 a21a22a23a24a25a26d2a22a23a24a25a26d2 a31a22a33a34a35a36d3a33a34a35a36d3 a41a42a43a44a45a46d4a44a45a46d4 a51a52a53a54a55a56d5a55a56d5 a61a62a63a64a65a66d6a66d6 a11a12a13a14a15a16d1a11a12a13a14d1 a22a23a24a25a26d2a22a23a24d2 a22a33a34a35a36d3a33a34d3 a42a43a44a45a46d4a44d4 a52a53a54a55a56d5a55d5 a62a63a64a65a66d6a66d

Метод Гаусса, блочная схема Москва, 2009 г. 4 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a11a12a13a14a15a16d1a11a12a13a14a15a16d1 a21a22a23a24a25a26d2a22a23a24a25a26d2 a31a22a33a34a35a36d3a33a34a35a36d3 a41a42a43a44a45a46d4a44a45a46d4 a51a52a53a54a55a56d5a55a56d5 a61a62a63a64a65a66d6a66d6 a11a12a13a14a15a16d1a11a12a13a14d1 a22a23a24a25a26d2a22a23a24d2 a22a33a34a35a36d3a33a34d3 a42a43a44a45a46d4a44d4 a52a53a54a55a56d5a55d5 a62a63a64a65a66d6a66d

Метод Гаусса, послойная схема Москва, 2009 г. 5 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a11a12a13a14a15a16d1a11a12a13a14a15a16d1 a21a22a23a24a25a26d2a22a23a24a25a26d2 a31a22a33a34a35a36d3a33a34a35a36d3 a41a42a43a44a45a46d4a44a45a46d4 a51a52a53a54a55a56d5a55a56d5 a61a62a63a64a65a66d6a66d6 a11a12a13a14a15a16d1a11a12a13a14d1 a22a23a24a25a26d2a22a23a24d2 a22a33a34a35a36d3a33a34d3 a42a43a44a45a46d4a44d4 a52a53a54a55a56d5a55d5 a62a63a64a65a66d6a66d

Метод Гаусса Упреждающая рассылка Москва, 2009 г. 6 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a11a12a13a14a15a16d1a11a12a13a14a15a16d1 a21a22a23a24a25a26d2a22a23a24a25a26d2 a31a22a33a34a35a36d3a33a34a35a36d3 a41a42a43a44a45a46d4a44a45a46d4 a51a52a53a54a55a56d5a55a56d5 a61a62a63a64a65a66d6a66d6 a11a12a13a14a15a16d1a11d1 a22a23a24a25a26d2a22d2 a22a33a34a35a36d3a33d3 a41a42a43a44a45a46d4a44d4 a51a52a53a54a55a56d5a55d5 a61a62a63a64a65a66d6a66d

Одномерная разностная схема для уравнения диффузии

Решение одномерного уравнения на 9 моментов времени

Прогонка Москва, 2009 г. 9 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1a1a1c1d1 b2a2c2d2a2c2d2 b3a3c3d3a3c3d3 b4a4c4d4a4c4d4 b5a5c5d5a5c5d5 b6a6d6a6d6 a1a1c1d1a1a1c1d1 a2c2d2a2c2d2 a3c3d3a3c3d3 b4a4c4d4a4d4 b5a5c5d5a5d5 b6a6d6a6d

Прогонка на двух процессорах Москва, 2009 г. 10 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 b2a2c2d2 b3a3c3d3 b4a4c4d4 b5a5c5d5 b6a6c6d6 b7a7c7d7 b8a8c8d8 b9a9c9d9 b10a10c10d10 b11a11c11d11 b12a12d12

Встречная прогонка на двух процессорах Москва, 2009 г. 11 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 a2c2d2 b3a3c3d3 b4a4c4d4 b5a5c5d5 b6a6c6d6 b7a7c7d7 b8a8c8d8 b9a9c9d9 b10a10c10d10 b11a11d11 b12a12d12

Встречная прогонка на двух процессорах Москва, 2009 г. 12 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 a2c2d2 a3c3d3 b4a4c4d4 b5a5c5d5 b6a6c6d6 b7a7c7d7 b8a8c8d8 b9a9c9d9 b10a10d10 b11a11d11 b12a12d12

Встречная прогонка на двух процессорах Москва, 2009 г. 13 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 a2c2d2 a3c3d3 a4c4d4 b5a5c5d5 b6a6c6d6 b7a7c7d7 b8a8c8d8 b9a9d9 b10a10d10 b11a11d11 b12a12d12

Встречная прогонка на двух процессорах Москва, 2009 г. 14 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 a2c2d2 a3c3d3 a4c4d4 a5c5d5 b6a6c6d6 b7a7c7d7 b8a8d8 b9a9d9 b10a10d10 b11a11d11 b12a12d12

Встречная прогонка на двух процессорах Москва, 2009 г. 15 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 a2c2d2 a3c3d3 a4c4d4 a5c5d5 a6c6d6 b7a7d7 b8a8d8 b9a9d9 b10a10d10 b11a11d11 b12a12d12

Встречная прогонка на двух процессорах Москва, 2009 г. 16 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 a2c2d2 a3c3d3 a4c4d4 a5c5d5 a6c6d6 a7d7 b8a8d8 b9a9d9 b10a10d10 b11a11d11 b12a12d12

Встречная прогонка на двух процессорах Москва, 2009 г. 17 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 a2c2d2 a3c3d3 a4c4d4 a5c5d5 a6d6 a7d7 a8d8 b9a9d9 b10a10d10 b11a11d11 b12a12d12

Встречная прогонка на двух процессорах Москва, 2009 г. 18 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1c1d1 a2c2d2 a3c3d3 a4c4d4 a5d5 a6d6 a7d7 a8d8 a9d9 b10a10d10 b11a11d11 b12a12d12

a1a1c1d1 b2a2c2d2 b3a3c3d3 b4a4c4d4 b5a5c5d5 b6a6c6d6 b7a7c7d7 b8a8c8d8 b9a9c9d9 b10a10c10d10 b11a11c11d11 b12a12d12 Прогонка на трех процессорах Москва, 2009 г. 19 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1c1d1 a2c2d2 b3a3c3d3 b4a4c4d4 b5a5c5d5 f6a6c6d6 b7a7c7d7 b8a8c8d8 b9a9c9d9 f10a10c10d10 b11a11c11d11 b12a12d12 Прогонка на трех процессорах Москва, 2009 г. 20 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1c1d1 a2c2d2 a3c3d3 b4a4c4d4 b5a5c5d5 f6a6c6d6 f7a7c7d7 b8a8c8d8 b9a9c9d9 f10a10c10d10 f11a11c11d11 f12b12a12d12 Прогонка на трех процессорах Москва, 2009 г. 21 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1c1d1 a2c2d2 a3c3d3 a4c4d4 b5a5c5d5 f6a6c6d6 f7a7c7d7 f8a8c8d8 b9a9c9d9 f10a10c10d10 f11a11c11d11 f12a12d12 Прогонка на трех процессорах Москва, 2009 г. 22 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1c1d1 a2c2d2 a3g3d3 a4c4d4 b5a5c5d5 f6a6c6d6 f7a7g7d7 f8a8c8d8 b9a9c9d9 f10a10c10d10 f11a11d11 f12a12d12 Прогонка на трех процессорах Москва, 2009 г. 23 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1c1d1 a2g2d2 a3g3d3 a4c4d4 b5a5c5d5 f6a6g6d6 f7a7g7d7 f8a8c8d8 b9a9c9d9 f10a10d10 f11a11d11 f12a12d12 Прогонка на трех процессорах Москва, 2009 г. 24 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1g1d1 a2g2d2 a3g3d3 a4c4d4 b5a5g5d5 f6a6g6d6 f7a7g7d7 f8a8c8d8 b9a9d9 f10a10d10 f11a11d11 f12a12d12 Прогонка на трех процессорах Москва, 2009 г. 25 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1g1d1 a4c4d4 b5a5g5d5 f8a8c8d8 b9a9d9 f12a12d12 Прогонка на трех процессорах Москва, 2009 г. 26 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1c1d1 b2a2c2d2 b3a3c3d3 b4a4c4d4 b5a5c5d5 b6a6c6d6 b7a7c7d7 b8a8c8d8 b9a9c9d9 b10a10c10d10 b11a11c11d11 b12a12d12 Прогонка на трех процессорах Москва, 2009 г. 27 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. b6 b7 b8 c6 c5 c4

a1a1c1d1 b2a2c2d2 b3a3c3d3 b4a4c4d4 b5a5c5d5 f6a6c6d6 f7a7c7d7 f8a8c8d8 b9a9c9d9 b10a10c10d10 b11a11c11d11 b12a12d12 Прогонка на трех процессорах Москва, 2009 г. 28 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. b6 b7 b8 c6 c5 c4

a1a1c1d1 b2a2c2d2 b3a3c3d3 b4a4c4d4 b5a5c5d5 f6a6g6d6 f7a7c7d7 f8a8c8d8 b9a9c9d9 b10a10c10d10 b11a11c11d11 b12a12d12 Прогонка на трех процессорах Москва, 2009 г. 29 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. b6 b7 b8 c6 c5 c4

a1a1c1d1 b2a2c2d2 b3a3c3d3 b4a4c4d4 b5a5g5d5 f6a6g6d6 f7a7c7d7 f8a8c8d8 b9a9c9d9 b10a10c10d10 b11a11c11d11 b12a12d12 Прогонка на трех процессорах Москва, 2009 г. 30 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. b6 b7 b8 c6 c5 c4

a1a1c1d1 b2a2c2d2 b3a3c3d3 b4a4g4d4 b5a5g5d5 f6a6g6d6 f7a7c7d7 f8a8c8d8 b9a9c9d9 b10a10c10d10 b11a11c11d11 b12a12d12 Прогонка на трех процессорах Москва, 2009 г. 31 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. b6 b7 b8 c6 c5 c4

a1a1g1d1 a2g2d2 a3g3d3 a4g4d4 f5a5g5d5 f6a6g6d6 f7a7g7d7 f8a8g8d8 f9a9g9d9 f10a10g10d10 f11a11g11d11 f12a12d12 Прогонка на трех процессорах Москва, 2009 г. 32 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. b6 b7 b8 c6 c5 c4

a4g4d4 f8a8g8d8 f12a12d12 Прогонка на трех процессорах Москва, 2009 г. 33 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

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

Явная разностная схема для уравнения диффузии

Решение одномерного уравнения на 9 моментов времени

Москва, 2009 г. 37 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. Стратегии балансировки загрузки W i j - вычислительная нагрузка, ассоциированная с узлом сетки i на шаге j W i j = W i j – не зависит от времени W i j W i j-1 – меняется медленно W i j W i j-1 – меняется значительно и не прогнозируемо Статическая Динамическая диффузная Динамическая?

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

Стена Фокса Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. Какой объем работ забрать у среднего процессора и кому его передать? 39 из 26

Неэффективность предварительного тестирования Необходимость принятия решения непосредственно во время расчета Динамическая балансировка загрузки Правило вычисления перераспределяемых объемов –Централизованное –Децентрализованное Целевая функция и стратегия перераспределения Москва, 2009 г. 40 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

Хищник - жертва жертвы хищники

Сечение профиля концентраций

Эволюция популяций Хищники Жертвы

Исходная система уравнений Квадратная решетка размера 300x300 N(t=0,x,y)=1-0.08*sqrt((x-15)^2+(y-15)^2) M(t=0,x,y)= *sqrt((x-15)^2+(y-15)^2) N(t, граница )=0 M(t, граница )=0

Решение трехдиагональных систем методом параллельной прогонки (и ленточных систем аналогичными методами) достаточно эффективно Использование большого числа процессоров, позволяет решать системы большего размера или за меньшее время ценой частичной потери эффективности Для суперкомпьютеров предпочтительно использовать явные разностные схемы, по двум основным причинам: –их большее соответствие физике изучаемых процессов –большая эффективность параллельных алгоритмов Заключение Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. Москва, 2009 г. 45

Дж. Ортега. Введение в параллельные и векторные методы решения линейных систем. Пер. с англ. - М.: Мир, 1991., 368 с. Высокопроизводительные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ: Пер. с англ./ Под ред. Я. Ковалика.- М.: Радио и связь, с., ил. Литература Москва, 2009 г. Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. 46

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