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

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

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

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

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

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

Одномерная разностная схема для уравнения диффузии Москва, 2010 г. 7 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

Одномерная разностная схема для уравнения диффузии Москва, 2010 г. 8 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

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

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

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

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

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

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

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

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

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

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

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

Встречная прогонка на двух процессорах Москва, 2010 г. 20 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В. a1a1d1 a2d2 a3d3 a4d4 a5d5 a6d6 a7d7 a8d8 a9d9 a10d10 a11d11 a12d12

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

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

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

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

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

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

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

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

Три процессора – редуцированная система Москва, 2010 г. 29 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

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

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

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

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

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

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

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

Три процессора – редуцированная система Москва, 2010 г. 37 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

a1a1g1d1 a2g2d2 a3g3d3 a4d4 f5a5g5d5 f6a6g6d6 f7a7g7d7 a8d8 f9a9g9d9 f10a10g10d10 f11a11g11d11 a12d12 Прогонка на трех процессорах – три независимые Москва, 2010 г. 38 Введение в параллельные алгоритмы: Решение систем линейных уравнений © Якобовский М.В.

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

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

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

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