Методы ПАРАЛЛЕЛЬНОГО ВЫЧиСЛЕНИЯ

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

Начнем рассмотрения этих вопросов с задачи LU-разложения матриц. Под LU-разложением матрицы A понимается её представление в виде A=LU, где L – нижняя треугольная матрица с единичными элементами по диагонали, а U – верхняя треугольная матрица. Для получения решения исходной системы уравнений нужно сначала решить систему Ly=b, а затем Ux=y. Пусть размер матрицы A есть n×n, пусть она является ленточной с шириной, равной p, и для неё существует LU разложение.

Тогда задача в развернутой форме имеет следующий вид

a₁₁

a₁₂

a₁₃

a₁₄

u₁₁

u₁₂

u₁₃

u₁₄

a₂₁

a₂₂

a₂₃

a₂₄

a₂₅

l₂₁

u₂₂

u₂₃

u₂₄

u₂₅

a₃₁

a₃₂

a₃₃

a₃₄

a₃₅

l₃₁

l₃₂

u₃₃

u₃₄

u₃₅

a₄₁

a₄₂

a₄₃

l₄₁

l₄₂

l₄₃

a₅₂

a₅₃

l₄₂

l₄₃

Рекуррентные соотношения, которые можно использовать при LU-разложении, раскрываются при i, j=1,…,n следующим образом:

Для решения первой части задачи можно воспользоваться гексагональной подсистемой, в которой каждый ЭМ имеет 6 связей

Для решения второй части задачи, то есть уравнений Ly=b и Ux=y удобно применить линейную подсистему.

Для вычисления y_i, 1,…,n, используется вспомогательная переменная z_i, причем z_i равны сначала 0 и поступают с правого конца подсистемы (в ЭМ D) и продвигаются налево. Причем y_i и b_i поступают в ЭМ A и y_i продвигается вправо. l_i_,_i поступает углом сверху.

ЭМ A специализируется на вычислении y_i = (b_i - z_i)/l_i_,_i, остальные машины участвуют в вычислении вспомогательной переменной z_i, которая при достижении ЭМ A имеет значение .

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

Приведем пример организации этих подсистем. Особенность их рассмотрения состоит в том, что они непосредственно премыкают к периметру структуры всей системы и этим самым обеспечивают ввод матрицы A и вектора b из внешней памяти, когда это возложено на крайние ЭМ.

Далее необходимо определить, где и когда решать уравнение Ux=y. Ясно, что рациональнее всего решать его там, где будут находится элементы матрицы U и тогда, когда все они будут вычислены. Готовые значения элементов получаются в нижних элементарных машинах подсистемы, реализующей LU-разложение. Если эти машины имеют емкости ОЗУ достаточной для хранения столбцов U, то на НЭМ и нужно организовывать подсистему, решающую уравнение Ux=y. При отсутствии требуемой емкости ОЗУ возникает необходимость обращения к внешней памяти. Этого можно избежать, если имеется достаточное количество свободных ЭМ. В последнем случае вычисленные элементы матрицы U записываются в память свободных ЭМ. При этом число элементов, записываемых в ОЗУ одной машины, определяется возможностями ОЗУ.

Реализация этого метода возможна следующим образом.

Для решения в НЭМ уравнения Ux=y способом, ориентированным на нижнетреугольную матрицу, входные данные поступают путем реверсирования потоков данных, организованных при записи.

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

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