Метрика Карпа – Флатта

Метрика Карпа-Флатта является мерой распараллеливания кода в параллельных процессорных системах. Эта метрика существует в дополнение к закону Амдала и закону Густавсона и служит показателем степени распараллеливания конкретного компьютерного кода. Он был предложен Аланом Х. Карпом и Горацием П. Флаттом в 1990 году.

Описание

Учитывая параллельные вычисления, демонстрирующие ускорение $\psi$ на $p$ процессоры, где $p$ > 1, экспериментально определенная серийная доля $e$ определяется как метрика Карпа – Флатта, а именно:

$e={\frac {{\frac {1}{\psi }}-{\frac {1}{p}}}{1-{\frac {1}{p}}}}$

Чем ниже значение $e$, тем лучше распараллеливание.

Обоснование

Существует множество способов измерения производительности параллельного алгоритма, работающего на параллельном процессоре. Метрика Карпа-Флатта определяет метрику, которая раскрывает аспекты производительности, которые нелегко отличить от других метрик. Своего рода псевдо-"вывод" следует из закона Амдала , который можно записать как:

$T(p)=T_{s}+{\frac {T_{p}}{p}}$

Где:

• $T(p)$ общее время, затраченное на выполнение кода в $p$-процессорная система
• $T_{s}$ это время, необходимое для выполнения последовательной части кода
• $T_{p}$ это время, необходимое для выполнения параллельной части кода на одном процессоре
• $p$ это количество процессоров

с результатом, полученным заменой $p$ = 1 т.е. $T(1)=T_{s}+T_{p}$, если мы определим порядковую дробь $e$ = ${\frac {T_{s}}{T(1)}}$ то уравнение можно переписать как

$T(p)=T(1)e+{\frac {T(1)(1-e)}{p}}$

В плане ускорения $\psi$ = ${\frac {T(1)}{T(p)}}$ :

${\frac {1}{\psi }}=e+{\frac {1-e}{p}}$

Решая серийную дробь, мы получаем метрику Карпа – Флатта, как указано выше. Обратите внимание, что это не «вывод» из закона Амдала, поскольку левая часть представляет собой метрику, а не математически полученную величину. Приведенное выше рассмотрение просто показывает, что метрика Карпа – Флатта соответствует закону Амдала.

Использовать

Хотя серийная дробь e часто упоминается в литературе по информатике , она редко используется в качестве диагностического инструмента, как ускорение и эффективность . Карп и Флатт надеялись исправить это, предложив эту метрику. Эта метрика устраняет недостатки других законов и величин, используемых для измерения распараллеливания компьютерного кода. В частности, закон Амдала не учитывает вопросы балансировки нагрузки и не учитывает накладные расходы . Использование серийной доли в качестве показателя дает определенные преимущества перед другими, особенно по мере роста числа процессоров.

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

Ссылки

• Карп, Алан Х. и Флатт, Гораций П. (1990). «Измерение производительности параллельного процессора» . Коммуникации АКМ . 33 (5): 539–543. дои : 10.1145/78607.78614 .
• Куинн, Майкл Дж. (2004). Параллельное программирование на C с использованием MPI и OpenMP . Бостон: МакГроу-Хилл. ISBN  0-07-058201-7 .

Внешние ссылки

• Конспект лекций по метрике Карпа – Флатта - Технологический институт Вирджинии