Параллельные алгоритмы решения линейных уравнений

Задачи по Python с решениями

Свежие записи

Параллельные алгоритмы решения систем линейных уравнений. Результаты вычислительных экспериментов

На этом шаге мы приведем результаты выполнения последовательного и параллельного алгоритма, а также тексты приложений.

Приведем результаты вычислительных экспериментов, выполненных для оценки времени выполнения рассмотренного параллельного алгоритма Гаусса
для решения систем линейных уравнений (таблица 1).

Таблица 1. Результаты вычислительных экспериментов для параллельного алгоритма Гаусса решения систем линейных уравнений (время выполнения приведено в миллисекундах)

Число уравнений Последовательный алгоритм

Приведем реализации последовательного и параллельных алгоритмов.

Файлы этих проектов можно взять здесь.

Со следующего шага мы начнем рассматривать параллельные алгоритмы обработки графов.

Параллельные алгоритмы решения линейных уравнений

В данном разделе приводятся примеры параллельных алгоритмов решения следующих задач: умножения матрицы на матрицу, задача Дирихле, решение систем линейных уравнений (СЛАУ) методом Гаусса и методом простой итерации. Здесь рассматривается простой вариант сеточной задачи (задача Дирихле), когда шаг сетки в пространстве вычислений одинаков и не меняется в процессе вычислений. При динамически изменяющемся шаге сетки потребовалось бы решать такую задачу параллельного программирования, как перебалансировка вычислительного пространства между компьютерами, для выравнивания вычислительной нагрузки компьютеров, а эта задача здесь не рассматривается.

В этой главе приводятся только общие схемы решения указанных задач, а тексты программ приведены в следующих разделах, т.к. для понимания общих схем решения знать MPI не обязательно. Приведенные здесь параллельные алгоритмы решения задач являются иллюстрационными, демонстрирующими применение и возможности функций MPI , а не универсальными, предназначенными для библиотек алгоритмов.

Рассматриваемые задачи распараллеливаются крупнозернистыми методами. Для представления алгоритмов используется SPMD — модель вычислений ( распараллеливание по данным). Однородное распределение данных по компьютерам – основа для хорошего баланса времени, затрачиваемого на вычисления, и времени, затрачиваемого на взаимодействия ветвей параллельной программы. При таком распределении преследуется цель: равенство объёмов распределяемых частей данных и соответствие нумерации распределяемых частей данных нумерации компьютеров в системе. Исходными данными рассматриваемых здесь алгоритмов являются матрицы, векторы и 2 D (двумерное) пространство вычислений. В этих алгоритмах применяются следующие способы однородного распределения данных: горизонтальными полосами, вертикальными полосами и циклическими горизонтальными полосами. При распределении горизонтальными полосами матрица, вектор или 2 D пространство «разрезается» на полосы по строкам (далее слово «разрезанная» будем писать без кавычек и матрицу, вектор или 2 D пространство обозначать для краткости словом — данные). Пусть M – количество строк матрицы, количество элементов вектора или количество строк узлов 2 D пространства, P – количество виртуальных компьютеров в системе, С1 = М / Р – целая часть от деления, С2 = М % Р – дробная часть. Данные разрезаются на Р полос. Первые (Р–С2) полос имеют по С1 строки, а остальные С2 полосы имеют по С1+1 строки. Полосы данных распределяются по компьютерам следующим образом. Первая полоса помещается в компьютер с номером 0, вторая полоса – в компьютер 1, и т. д. Такое распределение полос по компьютерам учитывается в параллельном алгоритме. Распределение вертикальными полосами аналогично предыдущему, только в распределении участвуют столбцы матрицы или столбцы узлов 2 D пространства. И, наконец, распределение циклическими горизонтальными полосами. При таком распределении данные разрезаются на количество полос значительно большее, чем количество компьютеров. И чаще всего полоса состоит из одной строки. Первая полоса загружается в компьютер 0, вторая – в компьютер 1, и т.д., затем, Р-1-я полоса снова в компьютер 0, Р-я полоса в компьютер 1, и т.д.

Приведенные два алгоритма решения СЛАУ методом Гаусса показывают, что однородность распределения данных сама по себе еще недостаточна для эффективности алгоритма. Эффективность алгоритмов зависит еще и от способа распределения данных. Разный способ представления данных влечет, соответственно, и разную организацию алгоритмов, обрабатывающих эти данные.

2.1 Запуск параллельной программы

Под виртуальным компьютером понимается программно реализуемый компьютер. Виртуальный компьютер работает в режиме интерпретации его физическим процессором. В одном физическом компьютере, в общем случае, может находиться и работать одновременно виртуальных компьютеров — столько, сколько позволяет память физического компьютера. На системе МВС1000 в одном физическом компьютере создается только один виртуальный. Под виртуальной топологией здесь понимается программно реализуемая топология связей между виртуальными компьютерами на физической системе.

Создаваемая пользователем виртуальная среда позволяет обеспечивать хорошую переносимость параллельных программ, а значит и независимость от конкретных вычислительных систем. Для пользователя очень удобно решать свою задачу в рамках виртуальной среды, использовать столько компьютеров, сколько необходимо для решения его задачи и задавать такую топологию связей между компьютерами, какая необходима.

Запуск параллельной программы продемонстрируем на примере. Допустим, требуется решить задачу program.c . Алгоритм задачи распараллелен на N процессов, независимо выполняющихся и взаимодействующих друг с другом. Задана нужная для решения задачи топология связей между этими процессами: — top (например, двумерная решетка). Для решения этой задачи было бы оптимально иметь вычислительную систему из N компьютеров (Для МВС1000 должно быть N ), с той же структурой связей, что и top . Далее в каждый компьютер необходимо загрузить по одному исполняемому модулю, реализующему ветвь параллельной программы, и стартовать эти модули. Ветви параллельной программы могут реализовываться копиями одной и той же программы (для МВС1000), а могут реализовываться разными программами (в общем случае). Опции и подробности загрузки нужно смотреть в соответствующих инструкциях.

Программа предварительно компилируется:

mpicc [ ] -o program.exe program.c

В квадратных скобках стоят опции нужной оптимизации. Для разных программ, разных компьютеров в вычислительной системе, для одинаковых компьютеров, но с разными операционными системами, нужно осуществлять отдельную компиляцию.

Здесь рассматривается команда запуска параллельной программы на системе МВС1000. Предполагается, что ветви параллельной программы реализуются копиями одной и той же программы. Необходимое количество физических компьютеров и виртуальных компьютеров задаются пользователем в командной строке:

mpirun -np N program.exe

N = <1,2,3,…>— указывает количество виртуальных компьютеров, необходимых для решения рассматриваемой программы с именем — program.exe . По этой команде система MPI создает (в оперативной памяти системы из N физических компьютеров) N виртуальных компьютеров, объединенных виртуальными каналами связи со структурой полный граф. И этой группе виртуальных компьютеров присваивается стандартное системное имя MPI_COMM_WORLD . После чего пользовательская программа program.exe загружается в память каждого из созданных виртуальных компьютеров и стартует.

Отображение виртуальных компьютеров и структуры их связи на конкретную физическую систему осуществляется системой MPI автоматически, т.е. пользователю не нужно переделывать свою программу для разных физических систем (с другими компьютерами и другой архитектурой). (Рассматриваемая версия MPI не позволяет пользователю осуществлять это отображение, либо осуществлять пересылку виртуальных компьютеров в другие физические компьютеры, т.е. не позволяет перераспределять виртуальные компьютеры по физическим компьютерам).

2.2 Умножение матрицы на матрицу

Умножение матрицы на вектор и матрицы на матрицу являются базовыми макрооперациями для многих задач линейной алгебры, например итерационных методов решения систем линейных уравнений и т. п. Поэтому приведенные алгоритмы можно рассматривать как фрагменты в алгоритмах этих методов. В этой секции приведено три алгоритма умножения матрицы на матрицу. Разнообразие вариантов алгоритмов проистекает от разнообразия вычислительных систем и размеров задач. Рассматриваются и разные варианты загрузки данных в систему: загрузка данных через один компьютер; и загрузка данных непосредственно каждым компьютером с дисковой памяти. Если загрузка данных осуществляется через один компьютер, то данные считываются этим компьютером с дисковой памяти, разрезаются и части рассылаются по остальным компьютерам. Но данные могут быть подготовлены и заранее, т.е. заранее разрезаны по частям и каждая часть записана на диск в виде отдельного файла со своим именем; затем каждый компьютер непосредственно считывает с диска, предназначенный для него файл.

2.2.1 Алгоритм 1

Заданы две исходные матрицы A и B . В ычисляется произведение C = А х B , где А — матрица n₁ х n₂ , и B — матрица n₂ х n₃ . Матрица результатов C имеет размер n₁ х n₃ . Исходные матрицы предварительно разрезаны на полосы, полосы записаны на дисковую память отдельными файлами со своими именами и доступны всем компьютерам. Матрица результатов возвращается в нулевой процесс.

Реализация алгоритма выполняется на кольце из p₁ компьютеров. Матрицы разрезаны как показано на рисунке 2.1: матрица А разрезана на p₁ горизонтальных полос, матрица B разрезана на p₁ вертикальных полос, и матрица результата C разрезана на p₁ полосы. Здесь предполагается, что в память каждого компьютера загружается и может находиться только одна полоса матрицы А и одна полоса матрицы B .

Параллельные методы решения систем линейных уравнений

Смотреть на youtube || на ИНТУИТ в качестве: низком | среднем | высоком

Подскажите, пожалуйста, планируете ли вы возобновление программ высшего образования? Если да, есть ли какие-то примерные сроки?

1) Можно ли экстерном получить второе высшее образование «Программная инженерия» ?

2) Трудоустраиваете ли Вы выпускников?

3) Можно ли с Вашим дипломом поступить в аспирантуру?