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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метрика Карпа-Флатта (англ. Karp–Flatt metric)  використовується для вимірювання можливостей розпаралелення коду у паралельних обчислювальних системах. Ця метрика доповнює закон Амдала і закон Густавсона, як характеристика здатності до розпаралелення певного коду. Вона була запропонована Аланом Карпом і Горацієм Флаттом у 1990 році.

Опис[ред.ред. код]

Враховуючи, що паралельне обчислення визначається, як прискорення на процесорів, де > 1, експериментально визначена послідовність (позначена як метрика Карпа-Флатта) дорівнюватиме:

Чим менше значення , тим краще розпаралелювання.

Обґрунтування[ред.ред. код]

Є багато способів виміряти продуктивність паралельного алгоритму, виконуваного паралельним процесором. Метрика Карпа-Флатта виявляє аспекти продуктивності, які непросто визначити за допомогою інших метрик. Псевдо-«підсумок», згідно вирахувань, здійснених за законом Амдала, можна записати як:

Де:

  •  — це загальний час виконання коду у -процесорній системі
  •  — це час виконання чергової частини поточного коду
  •  — це час, потрібний для виконання паралельної частини коду на одному процесорі
  •  — це число процесорів

Здійснимо підстановку = 1, отримаємо . Отож, якщо ми визначимо чергову частину = , то далі рівняння можна перезаписати як

У виразі прискорення =  :

Розв'язавши послідовність ми отримаємо метрику Карпа-Флатта, що зображена вище. Зауважте те, що це не є «підсумком» із закону Амдала, тому що ліва частина є метрикою, а не величиною, що виводиться математично. Вищенаведені дії просто показують, що метрика Карпа-Флатта узгоджується із законом Амдала.

Використання[ред.ред. код]

Незважаючи на те, що послідовність часто згадується у науковій комп'ютерній літературі, вона рідко використовується як діагностичний інструмент для пришвидшення та покращення ефективності алгоритму. Карп і Флатт сподівалися це виправити, запропонувавши цю метрику. Дана метрика усуває недоліки інших законів і величин, використовуваних для вимірювання розпаралелювання комп'ютерного коду (наприклад, закон Амдала не враховує нюансів балансування навантаження та не бере до уваги накладні витрати. Використання послідовності як метрики створює певні переваги над рештою, зокрема тоді, коли число процесорів зростає.

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

Див. також[ред.ред. код]

Література[ред.ред. код]

  • 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. 

Посилання[ред.ред. код]