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

         

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


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

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

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

(6.1)

где ai=(ai1,ai2,...,ain), 0i<m, есть i-я строка матрицы A (предполагается, что количество строк m кратно числу процессоров p, т.е. m = k·p). Во всех алгоритмах матричного умножения и умножения матрицы на вектор, которые будут рассмотрены в этой и следующей лекциях, применяется разделение данных на непрерывной основе.

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

(6.2)

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

2. Блочное разбиение матрицы. При блочном ( chessboard block) разделении матрица делится на прямоугольные наборы элементов – при этом, как правило, используется разделение на непрерывной основе. Пусть количество процессоров составляет p = s·q, количество строк матрицы является кратным s, а количество столбцов – кратным q, то есть m = k·s и n = l·q. Представим исходную матрицу A в виде набора прямоугольных блоков следующим образом:

где Aij — блок матрицы, состоящий из элементов:



(6.3)


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

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

Рис. 6.1.  Способы распределения элементов матрицы между процессорами вычислительной системы


Содержание раздела