Метрика Карпа – Флатта - Karp–Flatt metric

В Метрика Карпа – Флатта это мера распараллеливание кода в параллельный процессор системы. Этот показатель существует в дополнение к Закон Амдала и Закон Густафсона как показатель степени параллелизации конкретного компьютерного кода. Его предложили Алан Х. Карп и Гораций П. Флатт в 1990 году.

Описание

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

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

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

Обоснование

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

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

Где:

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

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

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

Что касается ускорение ${displaystyle psi }$ = ${displaystyle {frac {T(1)}{T(p)}}}$ :

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

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

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

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

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

Рекомендации

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

внешняя ссылка

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