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

Лабораторная работа №4

Методические рекомендации к лабораторной работе №4

по курсу «Основы параллельного программирования»

Составил А.В.Селихов

ЦЕЛЬ: разработка параллельной программы для решения СЛАУ методом Гаусса с использованием блочного распределения матрицы по процессам.

ИСПОЛЬЗУЕМЫЕ СРЕДСТВА:

1)  Язык «Си»

2)  Библиотека параллельного программирования MPI и ее реализация MPICH

ЗАДАЧИ:

1)  Представление последовательного алгоритма для метода Гаусса.

2)  Определение путей распараллеливания процесса решения СЛАУ, выделение независимых данных и независимых действий над данными, которые можно выполнять параллельно.

3)  Разработка схемы распределения работы и взаимодействий между параллельными процессами.

4)  Разработка параллельной программы.

5)  Тестирование и получение контрольных результатов.

РЕКОМЕНДАЦИИ К ВЫПОЛНЕНИЮ

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

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

1. Деление всех элементов 0-й строки расширенной матрицы на 0-й диагональный элемент. В результате деления получается «1» на месте 0-го диагонального элемента.
2. Вычитание из 1-й строки 0-й строки, умноженной на 0-й элемент 1-й строки. В результате 0-й элемент 1-й строки содержит «0», т.е. он «исключен».
3.  Исключение 0-го элемента во всех нижележащих строках расширенной матрицы.
4. Повторение шагов a-c для возрастающего номера строки (1,2,…,N-1)

В результате получается верхнедиагональная матрица и последний корень СЛАУ. Шаги алгоритма, реализующего обратный ход:

1. Из значения элемента, полученного в правой части после прямого хода, вычитаются значения всех уже полученных корней, умноженных на соответствующие коэффициенты матрицы. В результате первого выполнения этого шага для строки N-2 получается предпоследний (N-2-й) корень СЛАУ на месте предпоследнего элемента правой части расширенной матрицы и модифицированные значения остальных правых частей.
2. Шаг «а» применяется для строк N-3,…,0. В результате получаем остальные корни СЛАУ.

Определение путей распараллеливания процесса решения СЛАУ, выделение независимых данных и независимых действий над данными, которые можно выполнять параллельно

Из представленного описания алгоритма видно, что во время прямого хода алгоритма производятся операции над строками расширенной матрицы. При этом из шага «b» видно, что его выполнение для каждой отдельной строки требует наличия только самой этой строки и строки, поделенной на свой диагональный элемент на данном шаге («корневой» строки). Следовательно, после получения «корневой» строки, все остальные строки расширенной матрицы могут обрабатываться независимо. Строки расширенной матрицы являются данными задачи, поэтому найденный тип возможного параллелизма является параллелизмом по данным (ср. ISMD) Кроме разделения данных задачи на независимо обрабатываемые части, выполнение каждой такой независимой обработки – вычитание векторов – может также производиться независимо над каждым элементом вектора, что позволяет реализовать более глубокий параллелизм по данным. Если бы в алгоритме требовалось выполнить различные, зависимые только по входному данному – вектору, операции, эти операции можно было бы выполнять параллельно, а тип реализуемого параллелизма назывался бы «параллелизм по управлению». В рамках лабораторной работы необходимо реализовать только параллелизм по данным самого верхнего уровня, т.е. без распараллеливания вычитания векторов.

Точно также можно увидеть, что в обратном ходе метода Гаусса операции получения «частичных» корней в правой части могут выполняться независимо, если для каждой строки расширенной матрицы есть значения элементов этой строки и значение последнего вычисленного на данном шаге корня.

Разработка схемы распределения работы и взаимодействий между параллельными процессами

Исходя из намеченных путей распараллеливания задачи, можно выделить два основных этапа для прямого хода: вычисление «корневой» строки и использование этой строки для независимого преобразования остальных строк расширенной матрицы. Аналогично и для обратного хода: получение корня и использование этого корня для частичного вычисления оставшихся корней. Пусть для решения задачи может использоваться P процессов, P<N-1 (где N-1 – количество строк матрицы). В данной лабораторной работе строки матрицы распределены по процессам блоками, т.е. процесс 0 обрабатывает строки 0,1,…,k, процесс 1 – строки k+1,k+2,…,k+s, …, процесс P-1 – строки t,t+1,…,N-1. Количество строк для каждого процесса может быть различным. Поскольку каждый процесс содержит в своей памяти только свои строки и не имеет доступа к памяти другого процесса, получение «корневой» строки теми процессами, которые ее не содержат, осуществляется путем пересылки этой строки всем «нуждающимся» процессам. При этом процесс, сформировавший «корневую» строку, использует ее для преобразования остальных своих строк.

Исходя из этого, схема работы процесса параллельной программы может быть представлена следующим образом:

• Процесс Pk, вычисливший «корневую» строку k, рассылает ее всем процессам, которым она необходима, т.е. процессам Pi, i>k. Процессы Pi получают «корневую» строку и преобразуют свои строки, процесс Pk также преобразует свои оставшиеся строки l>k. Номер процесса Pk меняется при переходе вычисления «корневой» строки на множество строк, расположенном в другом процессе. Этот этап завершается получением верхнедиагональной матрицы, т.е. реализует прямой ход метода.
• Во время обратного хода метода, последний процесс уже имеет один корень, поэтому он может разослать его всем процессам Pi, i<P-1, после чего каждый процесс может независимо вычислять окончательное или частичное значение своих корней. Этот этап продолжается до получения всех корней и реализует обратный ход метода.

Разработка параллельной программы

При разработке параллельной программы рекомендуется использовать функции синхронной небуферизированной пересылки сообщений MPI_Send и MPI_Recv библиотеки MPI.

Тестирование и получение контрольных результатов

Каждый процесс получает свою часть данных – строки расширенной матрицы – путем чтения из файла или генерации в самой программе. Для упрощения задачи рекомендуется выбирать количество строк, кратное количеству процессов. Рекомендуемое количество процессов – от 4 до 8. Для тестирования и отладки программы рекомендуется использовать функции вывода printf(“%d: …”, iMyRank), iMyRank – номер процесса. Более удобным может оказаться вывод результатов в файлы, каждый из которых формируется отдельным процессом. В качестве контрольных результатов рекомендуется вывести для каждого процесса его исходную часть расширенной матрицы, результат прямого хода и окончательный результат решения задачи.