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

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

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

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

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

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

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

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