Для анализа будем использовать следующие показатели:

• T1 - оценка трудоемкости решения задачи на одном процессоре.
• Tp(calc) - оценка трудоемкости решения задачи на p процессорах.
• Tp(comm) - оценка трудоемкости выполняемых операций передачи данных.

Oбщая трудоемкость последовательного алгоритма является пропорциональной n^3:

T1 = n^3

Cложность параллельного алгоритма без учета затрат на передачу данных может быть определена при помощи выражения:

Tp = n^3 / p

С учетом этой оценки показатели ускорения и эффективности принимают вид:

S = n^3 / (n^3/p) = p;
E = S /p = n^3 / p*(n^3 / p) = 1

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

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

• Количество операций умножения
  в процессе на каждой итерации хранится n/p строк матрицы А и n/p строк матрицы В. Для одной строки матрицы А производим n/p (по числу строк матрицы В) операций умножения на n элементов. Для n/p строк матрицы А получим:
  n/p * n/p *n
  операций умножения.
• Kоличество операций сложения
  для n/p элементов одной строки матрицы А будет произведено (n/p - 1)*n операций сложения, для n/p строк матрицы А получим:
  n/p * (n/p-1) * n
  операций

Для р итераций получим:

Tp(calc) = p*(n^3/p^2 + n^2/p * (n/p-1))*t = (n^3/p + n^2 * (n/p-1))*t = n^2*(n/p + n/p -1) *t = n^2 * (2n/p - 1) * t,

t есть время выполнения одной операции сложения или умножения(считается равным).

Для оценки коммуникационной сложности параллельных вычислений будем предполагать, что все операции передачи данных между процессорами в ходе одной итерации алгоритма могут быть выполнены параллельно. Объем передаваемых данных между процессорами определяется размером полос и составляет n/p строк длины n. Общее количество параллельных операций передачи сообщений на единицу меньше числа итераций алгоритма. Тем самым, оценка трудоемкости выполняемых операций передачи данных может быть определена как

Tp(comm) = (p - 1) * ( a + w * n * (n/p) / b),

где a – латентность, b – пропускная способность сети передачи данных, а w есть размер элемента матрицы в байтах.

Тогда ускорение может быть получено как:

S = T1/(Tp(calc) + Tp(comm)) = n^3 / (n^2 * (2n/p - 1)*t + (p - 1)*(a + w*n*(n/p) /b)),

a эффективность E = S / p .