Ускорение, эффективность, загрузка и качество

Рассмотрим параллельное выполнение программы со следующими характеристиками:

· О(п) — общее число операций (команд), выполненных на п-процессорной системе;

· Т(п) — время выполнения O(п) операций на «-процессорной системе в виде числа квантов времени.

В общем случае Т(п) < O(п), если в единицу времени п процессорами выполняется более чем одна команда, где п > 2. Примем, что в однопроцессорной системе T(1) = O(1).

Ускорение (speedup), или точнее, среднее ускорение за счет параллельного выполнения программы — это отношение времени, требуемого для выполнения наилучшего из последовательных алгоритмов на одном процессоре, и времени параллельного вычисления на п процессорах. Без учета коммуникационных издержек ускорение S(n) определяется как

Как правило, ускорение удовлетворяет условию S(n) < п.

Эффективность (efficiency) n-процессорной системы — это ускорение на один процессор, определяемое выражением

Эффективность обычно отвечает условию 1/п ≤ Е(п) ≤ п. Для более реалистичного описания производительности параллельных вычислений необходимо промоделировать ситуацию, когда параллельный алгоритм может потребовать больше операций, чем его последовательный аналог.

Довольно часто организация вычислений на п процессорах связана с существенными издержками. Поэтому имеет смысл ввести понятие избыточности (redundancy) в виде

Это отношение отражает степень соответствия между программным и аппаратным параллелизмом. Очевидно, что 1 < R(n) < п.

Определим еще одно понятие, коэффициент полезного использования или утилизации (utilization), как

Тогда можно утверждать, что

и .

Рассмотрим пример. Пусть наилучший из известных последовательных алгоритмов занимает 8с, а параллельный алгоритм занимает на пяти процессорах 2с. Тогда:

· S(n) = 8/2 = 4;

· E(n) = 4/5 = 0,8;

· R(n) = 1/0,8 – 1 = 0,25.

Собственное ускорение определяется путем реализации параллельного алгоритма на одном процессоре.

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

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

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

Другая причина повышенного ускорения иллюстрируется примером. Пусть нам нужно выполнить логическую операцию А₁ v А₂, где как А₁, так и А₂ имеют значение «Истина» с вероятностью 50%, причем среднее время вычисления А_i, обозначенное как T(А_i), существенно различается в зависимости от того, является ли результат истинным или ложным.

Пусть T(А_i)= 1c для А_i = 1; T(А_i)= 100c для А_i = 0. Теперь получаем четыре равновероятных случая (Т — «истина», F — «ложь», таблица 9).

Таблица 9
А₁	А₂	Последовательный	Параллельный
Т Т F F	Т F Т F	1с + 0 1с + 0 100 с + 1с 100 с +100 с	1 с 1с 1с 100с
∑	303/4с ≈ 76с	103/4с ≈ 26с

Таким образом, параллельные вычисления на двух процессорах ведут к среднему ускорению:

Отметим, что суперлинейное ускорение вызвано жесткостью последовательной обработки, так как после вычисления еще нужно проверить A₂. К факторам, ограничивающим ускорение, следует отнести:

· Программные издержки. Даже если последовательные и параллельные алгоритмы выполняют одни и те же вычисления, параллельным алгоритмам присущи добавочные программные издержки — дополнительные индексные вычисления, неизбежно возникающие из-за декомпозиции данных и распределения их по процессорам; различные виды учетных операций, требуемые в параллельных алгоритмах, но отсутствующие в алгоритмах последовательных.

· Издержки из-за дисбаланса загрузки процессоров. Между точками синхронизации каждый из процессоров должен быть загружен одинаковым объемом работы, иначе часть процессоров будет ожидать, пока остальные завершат свои операции. Эта ситуация известна как дисбаланс загрузки. Таким образом, ускорение ограничивается наиболее медленным из процессоров.

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

Еще одним показателем параллельных вычислений служит качество параллельного выполнения программ — характеристика, объединяющая ускорение, эффективность и избыточность. Качество определяется следующим образом:

Поскольку как эффективность, так и величина, обратная избыточности, представляют собой дроби, то Q(n) < S(n). Поскольку Е(п) — это всегда дробь, a R(n) — число между 1 и п, качество Q(n) при любых условиях ограничено сверху величиной ускорения S(n).