Створення паралельних версій дозволяє додаткам істотно підвищити швидкість обробки даних. Успіх паралелізації зазвичай визначається прискоренням роботи паралельної програми по відношенню до її послідовної версії. При цьому буває корисно провести порівняння отриманого результату з таким собі верхньою межею. Це можна зробити за допомогою законів Амдала (Amdahl's Law) і Густафсона (Gustafson's Law).
Вхідні дані
Менший час виконання програми дозволяє обробляти великі набори даних (наприклад, більшу кількість записів, пікселів, або використовувати фізичні моделі більшого масштабу) за прийнятний проміжок часу. Одним з показників підвищення такого роду продуктивності є прискорення (speedup).
Взагалі кажучи, прискорення - це відношення часу послідовного до часу паралельного виконання програми. Наприклад, якщо послідовне додаток виконується за 6720 секунд, а відповідне паралельне додаток за 126.7 секунд (при використанні 64 потоків і ядер), прискорення становить 53x (6720 / 126.7 = 53.038).
Для добре масштабованих моделей прискорення повинно зростати майже пропорційно збільшенню кількості ядер (потоків). Якщо вимірюється прискорення не збільшується пропорційно, а залишається на колишньому рівні або починає знижуватися, то це означає, що додаток погано масштабується на використовуваних наборах даних. Якщо ці набори даних є типовими для цього додатка, то воно не буде добре масштабироваться.
Близьке за змістом до показника прискорення варто метрика ефективності (efficiency). Якщо прискорення показує, наскільки паралельне виконання швидше послідовного, то ефективність показує, наскільки добре програма використовує обчислювальні ресурси системи. Для розрахунку ефективності паралельного додатка потрібно взяти спостерігається прискорення і розділити на кількість використовуваних ядер. Це число виражається у відсотках. Наприклад, 53-кратне прискорення на 64 ядрах дає ефективність в 82.8% (53/64 = 0.828). Це означає, що в середньому в процесі виконання кожне ядро простоює близько 17% часу.
Перед початком проекту по паралелізації розробнику може бути цікаво оцінити прискорення, яке він теоретично зможе досягти. Якщо відсоток послідовного коду, який можна виконувати паралельно, відомий (або оцінено), то він може використовувати закон Амдала для розрахунку верхньої межі прискорення додатки без необхідності попереднього написання будь-якого паралельного коду. У літературі є кілька варіантів формули закону Амдала. У кожній з них використовується відсоток (передбачуваного) часу паралельного виконання (pctPar), послідовного виконання (1 - pctPar), і кількість потоків / ядер (p). Нижче приведена проста формулювання закону Амдала для розрахунку прискорення паралельного додатка на p ядрах:
Ця формула є час послідовного виконання, нормалізоване до 1 і поділене на розрахунковий час паралельного виконання з використанням відсотка нормалізованого часу послідовного виконання. Час паралельного виконання розраховується як відсоток послідовного виконання (1 - pctPar) і відсоток паралельного виконання, поділені на кількість використовуваних ядер (pctPar / p). Наприклад, якщо 95% часу послідовного виконання може виконуватися паралельно на 8 ядрах, то оцінне прискорення, відповідно до закону Амдала, складе близько 6x (1 / (0.05 + 0.95 / 8) = 5.925).
На додаток до відношенню менше або дорівнює (≤) у формулі, формулювання закону Амдала має на увазі, що обчислення, які можна виконувати паралельно, будуть ділитися на нескінченну кількість ядер. Таке припущення видаляє другий член знаменника, що означає, що найвище можливе прискорення просто одно інверсії залишкового послідовного виконання.
Закон Амдала часто критикують за ігнорування витрат при комунікацію, синхронізацію і інших дій з управління потоками, а також за припущення про нескінченну кількість процесорів. На додаток до ігнорування витрат, властивих паралельним алгоритмам, одним з найсильніших зауважень є те, що при збільшенні кількості ядер кількість оброблюваних даних також зазвичай збільшується. Закон Амдала має на увазі використання фіксованого набору даних при будь-якій кількості ядер, і що відсоток часу послідовного виконання залишиться одним і тим же.
Якщо паралельне додаток при використанні восьми ядер здатне обробити набір даних обсягом у вісім разів більше, ніж раніше, збільшується при цьому час роботи послідовної частини? Навіть якщо і збільшується, то непропорційно росту обсягу даних. Реальна практика показує, що час послідовного виконання залишається практично постійним.
Закон Густафсона, також відомий як масштабується прискорення (scaled speedup). бере до уваги зростання обсягу даних в пропорції до зростання кількості ядер і розраховує (верхню межу) прискорення роботи програми, як якщо б більший обсяг даних міг бути оброблений послідовно. Формула масштабується прискорення виглядає так:
Як і у формулі закону Амдала, p означає кількість ядер. Для спрощення запису, s є відсотком часу послідовного виконання в паралельному додатку для зазначеного розміру набору даних. Наприклад, якщо 1% часу роботи на 32 ядрах виконується послідовно, то прискорення виконання такого додатка на тому ж наборі даних в порівнянні з виконанням на одному ядрі з одним потоком (передбачається, що це можливо) одно:
Подивимося, що б нам дав при таких припущеннях закон Амдала. Якщо відсоток послідовного виконання дорівнює 1%, то за законом Амдала - 1 / (0.01 + (0.99 / 32)) = 24.43x. Однак це помилковий результат, так як даний відсоток послідовного часу оцінений для виконання на 32 ядрах. З цього прикладу не видно, який відсоток послідовного виконання може бути для більшої чи меншої кількості ядер. Якщо код є ідеально масштабується і обсяг даних збільшується відповідно до кількості ядер, то цей відсоток може залишитися незмінним, а закон Амдала передбачатиме прискорення одноядерной завдання (фіксованого розміру) на 32 ядрах.
З іншого боку, якщо загальний час паралельного виконання відомо для 32 ядер, то час повністю послідовного виконання можна розрахувати, і прискорення цього завдання фіксованого розміру (маючи на увазі, що вона може бути розрахована на одному ядрі) можна передбачити за допомогою закону Амдала для 32 ядер. Припустивши, що загальний час виконання паралельного додатка становить 1040 секунд на 32 ядрах, тоді 1% цього часу буде послідовним, тобто 10.4 секунди. Помноживши кількість секунд (1029.6) паралельного виконання на 32 ядра, отримуємо, що загальний обсяг роботи, що виконується додатком, займає 1029.6 * 32 + 10.4 = 32957.6 секунд. Непаралельності час (10.4 секунди) становить 0.032% загального часу роботи. Використовуючи цей результат, закон Амдала дає нам прискорення в 1 / (0.00032 + (0.99968 / 32)) = 31.686x.
Оскільки для використання закон Густафсона необхідно знати відсоток послідовного часу при паралельному виконанні, то ця формула зазвичай використовується для розрахунку прискорення масштабується паралельного виконання (при збільшенні обсягів даних відповідно до кількості ядер), по відношенню до послідовного виконання завдання того ж розміру. З наведених вище прикладів слід, що суворе використання даних про виконання програми у формулі закону Амдала дає набагато більш песимістичну оцінку, ніж формула масштабується прискорення.
рекомендації
При розрахунку прискорення потрібно використовувати для порівняння найкращий послідовний алгоритм та найшвидший послідовний код. Часто буває, що легше распараллелить не найоптимальніший послідовний алгоритм. Навіть в цих випадках малоймовірно, що хтось буде використовувати будь-якої послідовний код, якщо існують швидші його версії. Таким чином, навіть якщо використовуються алгоритми розрізняються, для розрахунку прискорення відповідного паралельного додатка необхідно використовувати кращий час виконання найшвидшого коду.
При вказівці значення прискорення потрібно використовувати коефіцієнт множення. Раніше прискорення виражалося в процентах. У нашому випадку використання відсотків може призвести до плутанини. Наприклад, якщо йдеться про те, що паралельний код на 200% швидше послідовного, чи означає це, що він працює за половину часу послідовної версії, або за одну третину? Чи буде прискорення в 105% майже рівним послідовній роботі або в два рази швидше? Чи є базове послідовне час прискоренням в 0% або в 100%? З іншого боку, якщо паралельне додаток має прискорення в 2x, то ясно, що на роботу пішла половина часу (тобто паралельна версія змогла відпрацювати двічі за той час, поки послідовний код працює один раз).
У дуже рідкісних випадках прискорення додатки перевищує кількість ядер. Цей феномен відомий як суперлінейное прискорення. Стандартної причиною виникнення суперлінейного прискорення є те, що при декомпозиції блоки даних стали досить малі, щоб цілком поміщатися в локальний кеш ядер. При послідовній роботі дані повинні були постійно проходити через кеш і процесор був змушений очікувати появи в кеші потрібних даних. Якщо обсяг даних був досить великий, щоб витісняти попередні лінії кешу, то будь-яка наступна використання цих ліній кеша змушує процесор очікувати знову їх появи. Якщо дані розбиті на блоки, які цілком містяться в кеш ядра, то після завантаження всіх ліній кеша час на очікування вже не витрачається. Таким чином, використання декількох ядер може усувати деякі витрати, пов'язані з послідовним виконанням на одному ядрі. Занадто малі набори даних, менше, ніж стандартна, можуть давати помилкове відчуття поліпшення продуктивності.
Вказівки щодо застосування
Були запропоновані альтернативні моделі паралельного виконання, в деякій мірі проясняють присутні в простій моделі закону Амдала протиріччя.
Однак, через свою простоту і при розумінні, що це теоретична верхня межа, яку, швидше за все, не можна буде досягти або подолати, закон Амдала є простим і цінним дороговказом потенціалу прискорення в послідовному додатку.