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

Метрика Карпа — Флатта (англ. Karp–Flatt metric) використовується для вимірювання можливостей розпаралелення коду у паралельних обчислювальних системах. Ця метрика доповнює закон Амдала і закон Густавсона як характеристика здатності до розпаралелення певного коду. Вона була запропонована Аланом Карпом і Горацієм Флаттом у 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$ часто згадується у науковій комп'ютерній літературі, вона рідко використовується як діагностичний інструмент для пришвидшення та покращення ефективності алгоритму. Карп і Флатт сподівалися це виправити, запропонувавши цю метрику. Дана метрика усуває недоліки інших законів і величин, використовуваних для вимірювання розпаралелювання комп'ютерного коду (наприклад, закон Амдала не враховує нюансів балансування навантаження та не бере до уваги накладні витрати. Використання послідовності як метрики створює певні переваги над рештою, зокрема тоді, коли число процесорів зростає.

Щодо проблеми фіксованого розміру, ефективність паралельного розрахунку зазвичай зменшується тоді, коли число процесорів збільшується. Використовуючи послідовність, отриману експериментально за допомогою метрики Карпа — Флатта, ми можемо виявити причину зниження ефективності: обмеження можливостей паралелізму чи збільшення алгоритмічних або архітектурних накладних витрат.

Див. також

• Закон Амдала
• Закон Густавсона — Барсіса

Література

• Karp, Alan H. & Flatt, Horace P. (1990). Measuring Parallel Processor Performance. Communication of the ACM. 33 (5): 539—543. doi:10.1145/78607.78614.
• Quinn, Michael J. (2004). Parallel Programming in C with MPI and OpenMP. Boston: McGraw-Hill. ISBN 0-07-058201-7.

Посилання

• Лекції на тему «Метрика Карпа-Флатта» — Політехнічний інститут і університет штату Вірджинія