4.3.1. Ленточный алгоритм

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

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

4.3.2. Блочные алгоритмы Фокса и Кэннона

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

1. каждый из процессоров решетки отвечает за вычисление одного блока матрицы C;

2. в ходе вычислений на каждом из процессоров располагается по одному блоку исходных матриц A и В;

3. при выполнении итераций алгоритмов блоки матрицы А последовательно сдвигаются вдоль строк процессорной решетки, а блоки матрицы B — вдоль столбцов решетки;

4. в результате вычислений на каждом из процессоров получается блок матрицы С, при этом общее количество итераций алгоритма равно (где р – число процессоров).

4.4. Решение систем линейных уравнений

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

Линейное уравнение с n неизвестными x0, x1, ..., xn-1 может быть определено при помощи выражения

a0x0+a1x1+...+an-1xn-1=b,

где величины a0, a1, ..., an-1 и b представляют собой постоянные значения.

Множество n линейных уравнений

a0,0x0 + a0,1x1 + ... + a0,n-1xn-1 = b0

a1,0x0 + a1,1x1 + ... + a1,n-1xn-1 = b1

. . .

an-1,0x0 + an-1,1x1 + ... + an-1,n-1xn-1 = bn-1

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

Ax=b,

где A=(ai,j) есть вещественная матрица размера n×n, а векторы b и x состоят из n элементов.

Под задачей решения системы линейных уравнений для заданных матрицы А и вектора b понимается нахождение значения вектора неизвестных x, при котором выполняются все уравнения системы.

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