ПРИМЕР РЕШЕНИЯ ЗАДАЧИ УМНОЖЕНИЯ МАТРИЦ С ПОМОЩЬЮ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

Будем считать, что система – полный граф.

(1)

n – количество процессоров.

Исходные матрицы А, В разрезаются на n горизонтальных и вертикальных полос:

Т.о. для 1-го вычислителя:

Строки:

Столбцы:

Для L-го вычислителя:

Строки

Столбцы

n-й вычислитель:

строки

столбцы

Параллельный вычислительный процесс организуется следующим образом: сначала первый вычислитель передает остальным вычислителям первую строку из своей полосы матрицы А. После этого, все вычислители используют формулу (1). Осуществляется параллельный расчет целой части элементов первой строки матрицы С. Затем первый вычислитель рассылает всем остальным вычислителям вторую строку своей матрицы и производится расчет элементов 2ой строки матрицы С и тд. До тех пор пока 1ый вычислитель не перешлет свои строки матрицы А. После этого пересылками будут заниматься последовательно 2ой, 3ий …nый вычислители. Матрица получается распределенной по вычислителям, причем в каждом будет своя вертикальная полоса. Вследствие однородного распределения данных получены одинаковые ветви параллельного алгоритма, однако эти ветви используют различные части данных, т.к. для каждой ветви своих данных недостаточно, то ветви вступают во взаимодействие.

Аналогичным образом решается итерационным методом система линейных уравнений:

ПОКАЗАТЕЛИ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ. КОЭФФИЦИЕНТ НАКЛАДНЫХ РАСХОДОВ, КОЭФФИЦИЕНТ УСКОРЕНИЯ. ПОНЯТИЕ О СЛОЖНЫХ ЗАДАЧАХ.

1. Коэффициент накладных расходов: ,

где t – время, расходуемое ВС на вспомогательные операции (организация обмена информацией, настройку вычислителей и д.р.);

T – время, требуемое на выполнение арифметической и логической операции при выполнении алгоритма.

Оценим эффективность умножения матриц:

– умножений

– сложений

Если К очень большое, то эти величины приблизительно равны .

– время пересылки данных.

- время сложения двух чисел

- время умножения двух чисел

следовательно, max накладных расходов, когда , т.е. M=n.

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

Коэффициент ускорения

, где - время выполнения алгоритма на одном вычислителе,

- время выполнения алгоритма на n вычислителях.

, где - лучший последовательный алгоритм.

1. Понятие о сложных задачах

Представим коэффициент накладных расходов в развернутом виде:

V – Количество операций, которые необходимо выполнить при решении задачи на ВС.

n – Число вычислителей на ВС

k – эмпирический коэффициент: , то задача считается сложной.

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