Модифікація циклів підвищення продуктивності паралельної обробки даних, Intel® Software
Зазвичай у додатках з паралельною обробкою даних основний обсяг обчислень посідає цикли, тому оптимізація циклів безпосередньо впливає на загальну продуктивність програми. У разі вкладених циклів, продуктивність знаходиться у прямій залежності від ступеня розбиття (granularity) обчислень по потоках. Такі перетворення, як розкладання та об'єднання вкладених циклів можуть суттєво спростити розпаралелювання та підвищити його ефективність.
Опис проблеми
Оптимізація циклів є важливим фактором у підвищенні продуктивності додатків з паралельною обробкою даних. Такі оптимізації, як об'єднання, перестановка і розгортання циклів, зазвичай використовуються для поліпшення ступеня розбиття, балансу навантаження та ефективної локалізації даних, і при цьому тягнуть за собою незначні витрати пов'язані з синхронізацією та іншими витратами паралелізму. Основне правило - для розпаралелювання найкраще підходять цикли з великою кількістю ітерацій. Велика кількість ітерацій дозволяє покращити баланс навантаження завдяки наявності більшої кількості завдань для розподілу між потоками. Також слід враховувати обсяг роботи, який виконується за одну ітерацію. Якщо у статті окремо не обговорюється інше, ми маємо на увазі, що обсяг обчислень у кожній ітерації циклу (приблизно) однаковий для всіх ітерацій цього циклу.
Розглянемо приклад оптимізації циклу за допомогою директиви OpenMP* for, яка використовується для розподілу роботи, як показано в наведеному нижче прикладі. У цьому випадку невелика кількість ітерацій призводить до нерівномірності навантаження (load imbalance), якщо ітерації циклу розподіляються між чотирма потоками.Якщо одна ітерація займає лише кілька мілісекунд, така нерівномірність не призведе до серйозних наслідків. Однак, якщо кожна ітерація займатиме близько години, то три потоки простоюватимуть протягом 60 хвилин, очікуючи на завершення четвертого. Порівняйте це з ситуацією, коли аналогічний цикл включає 1003 ітерації тривалістю по годині, що виконуються на чотирьох потоках. У цьому випадку простоювання протягом години після десяти днів виконання не має суттєвого значення.
Рекомендації
У разі безлічі вкладених циклів, при паралелізації найкраще вибирати зовнішній і при цьому безпечний для розпаралелювання цикл. Такий підхід у більшості випадків дозволяє отримати найвищий ступінь розбиття. Якщо при цьому рівномірне розбиття неможливе (зовнішній цикл має замало ітерацій), більш підходящим кандидатом на розпаралелювання може стати більш внутрішній цикл з більшим числом ітерацій. Як приклад розглянемо наступний код із чотирма вкладеними циклами:
Якщо кількість потоків не дорівнює п'яти, то розпаралелювання зовнішнього циклу призведе до нерівномірності навантаження та простою потоків. Втрата продуктивності може бути ще серйознішою, якщо розмірності масивів imx , jmx і kmx будуть дуже великими. У цьому випадку кращим варіантом стане розпаралелювання одного з внутрішніх циклів. Від використання неявних бар'єрів в кінці конструкції розподілу роботи слід відмовитися, якщо це не складно. Всі директиви OpenMP для розподілу роботи (for, sections, single) мають неявний бар'єр наприкінці структурованого блоку. У цій точці всі потоки повинні зустрітися для синхронізації, перш ніж виконання коду продовжиться. У ряді випадків такі бар'єри не потрібні та можутьнегативно позначатися на продуктивності. Можна використовувати параметр OpenMP nowait, щоб заборонити бар'єри, як у наведеному нижче прикладі:
Оскільки обчислення у самому внутрішньому циклі незалежні один від одного, немає жодних причин для того, щоб потоки очікували синхронізації у неявного бар'єру, перш ніж переходити до наступної ітерації k. Якщо кількість роботи у різних ітераціях різна, параметр nowait дозволить потокам продовжувати виконання корисної роботи, не затримуючись у точці неявного бар'єру.
Якщо циклі є циклічно породжена залежність (loop-carried dependence), яка заважає виконанню циклу в паралельному режимі, можна розбити тіло циклу деякі менші цикли, які будуть виконуватися паралельно. Таке розбиття циклу на два і більше називається "розкладанням циклу". У наведеному нижче прикладі ми використовуємо розкладання циклу, що має залежність, щоб створити кілька циклів, які можуть виконуватися паралельно:
Надання значень елементам масиву a виконується незалежно, не враховуючи знак відповідних елементів масиву b . Кожне привласнення елементу масиву b не залежить від інших, але при цьому залежить від того, чи присвоювання завершеному необхідному елементу масиву a . При використанні такого варіанту коду розглянутий цикл не може бути розпаралеленний.
Розбивши цикл на дві незалежні операції, ми можемо виконувати ці операції у паралельному режимі. Наприклад, можна застосувати до кожного з них алгоритм parallel_for algorithm з бібліотеки Intel Threading Building Blocks (Intel TBB), як показано нижче:
Повернення першого виклику parallel_for перед виконанням другого гарантує, що всі оновлення в масиві a будуть завершені до того, як розпочнуться оновлення в масиві b.
Розкладання циклу також можна використовувати для локалізації даних (data locality). Розглянемо наступний приклад коду, що працює за принципом решета:
Зовнішній цикл вибирає початковий індекс елемента та крок внутрішнього циклу з масиву prime. Потім внутрішній цикл проходить по всій довжині масиву marked, розміщуючи у вибраних елементах значення «1». Якщо масив marked досить великий, виконання внутрішнього циклу може призвести до витіснення з кеш-ліній елементів масиву marked, що прораховуються в першу чергу, які будуть потрібні для подальшої ітерації зовнішнього циклу. Результатом цього стане низька частота успішних звернень до кешу як у послідовній, і у паралельної версії циклу.
Якщо вдатися до розкладання циклу, ітерації внутрішнього циклу можуть бути розбиті на блоки (chunks), які краще поміщатися в кеш і повторно використовувати рядки кешу, після того як були заповнені. Для того щоб застосувати розкладання в цьому випадку, додамо інший цикл, який контролюватиме діапазон, що охоплюється самим внутрішнім циклом:
На кожну ітерацію зовнішнього циклу в наведеному вище прикладі буде виконуватися повний набір ітерацій i-циклу. З обраного елемента масиву prime, знаходимо початковий і кінцевий індекси в блоці масиву marked (контрольованого зовнішнім циклом). Ці обчислення укладені всередину підпрограм f() та g(). Таким чином, той же блок у масиві marked буде оброблений до того, як відбудеться перехід до наступного. З огляду на те, що обробка кожного блоку виконується незалежно від інших, ітерації зовнішнього циклу можуть бути переведені в паралельний режим.
Ще одним способом оптимізації, що допомагає ефективно розпаралелювати ітерації, є об'єднання вкладених циклів для збільшення числа ітерацій. Уяк приклад розглянемо наведений зліва фрагмент коду з двома вкладеними циклами, число ітерацій яких становить 23 і 1000 відповідно. Оскільки 23 є простим числом, ітерації зовнішнього циклу неможливо ефективно розділити; крім того, обсяг роботи в 1000 ітерацій може виявитися недостатньо для того, щоб істотно скоротити витрати на розпаралелювання тільки внутрішнього циклу. З іншого боку, можна злиття цих циклів в один цикл з 23 000 ітераціями (див. приклад справа), що дозволить пом'якшити труднощі, що виникають при розпаралелювання початкового варіанту коду.
У той же час, якщо кожна зі змінних ітерації використовується всередині тіла циклу (наприклад, для індексації масивів), новий лічильник циклів повинен бути переведений назад до відповідних значень параметрів, що тягне за собою додаткові витрати, які у вихідному алгоритмі були відсутні.
Щоб підвищити ступінь розбиття і ефективної локалізації даних, при цьому скорочуючи непродуктивні витрати на розпаралелювання, можна використовувати об'єднання циклів з аналогічними індексами. Два перші цикли з прикладу, що наводиться ліворуч, легко піддаються об'єднанню:
Об'єднання цих циклів збільшує обсяг роботи на ітерацію (тобто ступінь розбиття) та скорочує пов'язані з циклом витрати. Здійснити злиття третього циклу не так просто, оскільки він має інше число ітерацій. Що ще важливіше, між третім циклом та двома попередніми циклами існує залежність за даними.
Використовуйте OpenMP if, щоб вибрати послідовний або паралельний режим залежно від інформації часу виконання (runtime information). У деяких випадках кількість ітерацій циклу не може бути встановлена до часу виконання. Якщо виконанняпаралельної області OpenMP у кількох потоках негативно впливає на продуктивність (наприклад, мале число ітерацій), для досягнення стабільної продуктивності слід задати мінімальний поріг (threshold), як у наведеному нижче прикладі:
У цьому прикладі цикл виконується в паралельному режимі тільки в тому випадку, якщо кількість ітерацій перевищує встановлений програмістом мінімальний поріг.
Враховуючи, що аналогічний механізм Intel TBB відсутній, для того, щоб визначити, який режим виконання коду використовувати (послідовний або паралельний), можна ввести явну перевірку умови. З іншого боку, можна викликати паралельний алгоритм та надати планувальнику завдань Intel TBB можливість використання одного потоку для малих значень N. Слід зазначити, що останній варіант пов'язаний із деякими непродуктивними витратами.