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

Принципы распараллеливания

Разработка алгоритмов (а в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную проблему. Здесь же мы будем полагать, что вычислительная схема решения нашей задачи умножения матрицы на вектор уже известна.

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

- выполнить анализ имеющейся вычислительной схемы и осуществить ее разделение (декомпозицию) на части (подзадачи), которые могут быть реализованы в значительной степени независимо друг от друга;

- выделить для сформированного набора подзадач информационные взаимодействия, которые должны осуществляться в ходе решения исходной поставленной задачи;

- для систем с общей памятью выполнить распределение выделенных подзадач по ВЭ.

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

Определение подзадач

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

Дадим кратко общую характеристику распределения данных для матричных. Наиболее общие и широко используемые способы разделения матриц состоят в разбиении данных на полосы (по вертикали или горизонтали) или на прямоугольные фрагменты (блоки).

1. Ленточное разбиение матрицы. При ленточном (block-striped) разбиении каждому процессору (ядру) выделяется то или иное подмножество строк (rowwise или горизонтальное разбиение) или столбцов (columnwise или вертикальное разбиение) матрицы (рис. 1.7а и 1.7б). Разделение строк и столбцов на полосы в большинстве случаев происходит на непрерывной (последовательной) основе. Притаком подходе для горизонтального разбиения по строкам, например, матрица A представляется в виде:

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