Автоматичне розпаралелення

Автоматичне розпаралелювання – це конвертування коду в багатопотоковий, що працює на паралельному комп'ютері (наприклад, на комп'ютері з багатьма процесорами, процесорними ядрами або потоками виконання). Метою автоматизації розпаралелювання є звільнення програміста від трудомісткого процесу ручного розпаралелювання. Незважаючи на те, що якість автоматичного розпаралелювання значно покращилася за останні роки, повне розпаралелювання послідовних програм залишається занадто складним завданням, що вимагає дуже складних видів аналізу програм та ПЗ.^[1]

Автоматичний паралелізатор зазвичай фокусується на таких керуючих конструкціях, як цикли, оскільки, в загальному випадку, більша частина виконання програми проходить всередині якихось циклів. Є два основні підходи до розпаралелювання циклів: конвеєрна багатопотоковість і циклічна багатопотоковість.^[2]

Визначення циклу, котрий може бути розпаралелений

Розглянемо, наприклад, цикл, який на кожній ітерації виконує 100 операцій, та має тисячу ітерацій. Це можна розглядати як табличку 100 стовпців на 1000 рядків, в цілому 100000 операцій.

Основні поняття

Циклічна багатопотоковість — кожен рядок в іншому потоці.

Конвеєрна багатопотоковість — кожен стовпець в іншому потоці.

Циклічна багатопотоковість

Циклічний багатопотоковий компілятор розпаралелювання намагається розділити цикл так, щоб кожна ітерація могла бути виконана на окремому процесорі одночасно.

Аналіз компілятора розпаралелювання

Компілятор зазвичай проводить два проходи аналізу до фактичного розпаралелювання для того, щоб визначити наступне:

Чи безпечно розпаралелити цикл? Відповідаючи на це питання необхідний точний аналіз залежностей (Dependence analysis^[en]) і аналіз незалежності вказівників (alias analysis^[en]).
Чи варто розпаралелювати його? Ця відповідь вимагає надійної оцінки (моделювання) робочого навантаження програми і потенціалу паралельної системи.

Перший прохід компілятора проводить аналіз залежність даних циклу щоб визначити, чи ітерації циклу можуть бути виконані незалежно один від одного.

Другий прохід намагається виправдати зусилля розпаралелювання шляхом порівняння теоретичного часу виконання коду після розпаралелювання з послідовним часом виконання. Хоч це й може звучати парадоксально, але вигода від паралельного виконання отримується не завжди. Додаткові накладні витрати, які можуть бути пов'язані з використанням декількох процесорів та особливості реалізації архітектури можуть нівелювати позитивний ефект прискорення.

Приклад

Цикл називається DOALL, якщо всі його ітерацій, в тому чи іншому виклику, можуть бути виконані паралельно. Fortran код нижче DOALL, і може бути автоматично розпаралелений компілятором, тому що кожна ітерація не залежить від інших, і кінцевий результат масиву z буде правильним незалежно від порядку виконання інших ітерацій.

   do i = 1, n
     z(i) = x(i) + y(i)
   enddo

З іншого боку, наступний код не може бути автоматично розпаралелений, оскільки значення z(i) залежить від результату попередньої ітерації, z(i - 1).

   do i = 2, n
     z(i) = z(i - 1)*2
   enddo

Це не означає, що код не може бути розпаралелений. Дійсно, це еквівалентно

   do i = 2, n
     z(i) = z(1)*2**(i - 1)
   enddo

Тим не менш, компілятори розпаралелювання зазвичай не здатні автоматично зробити такі паралелізми, і сумнівно, що цей код отримає вигоду з паралелізації, в першу чергу.

Конвеєрна багатопотоковість

Конвеєрний компілятор розпаралелювання намагається розбити послідовність операцій всередині циклу на послідовність кодових блоків, таких, що кожен блок коду може бути виконаним на окремих процесорах одночасно.

Є багато паралельних задач, які мають такі відносно самостійні блоки коду. Наприклад, при виробництві живого телевізійного мовлення, наступні завдання мають бути виконані повторно багато разів:

Зчитати кадр вихідних пікселів від датчика зображення,
зробити MPEG компенсацію руху для вихідних даних,
зробити ентропійне стиснення даних data,
розбити стиснені дані на пакети,
додати відповідну корекцію помилок і зробити ШПФ для перетворення пакетів даних в COFDM сигнали, і
надіслати COFDM сигнали на телевізійну антену.

Конвеєрний компілятор розпаралелювання може призначити кожну з цих шести операцій на інший процесор.

Труднощі

Автоматичне розпаралелювання складно для компіляторів з причин:^[3]

Аналіз залежностей складний для коду, що використовує непряму адресацію, вказівники, рекурсію, виклики функцій, особливо непрямі виклики (наприклад, віртуальні функції заздалегідь невідомого класу);
цикли можуть мати невідому заздалегідь кількість ітерацій. Через це ускладнюється вибір циклів, що вимагають розпаралелювання;
доступ до глобальних ресурсів важко координувати з точки зору розподілу пам'яті, вводу-виводу і загальних змінних;

Обхід труднощів

Через складність повного автоматичного розпаралелювання існує кілька підходів для його спрощення:

Дати програмістам можливість додавати до програми підказки компілятору, щоб впливати на процес розпаралелювання (або щоб спростити аналізи, позначивши вказівники як непересічні, або вказавши «гарячі» цикли). Серед рішень, що вимагають досить докладних інструкції для компілятора, можна вказати High Performance Fortran для систем з розподіленою пам'яттю і OpenMP для систем зі спільною пам'яттю.
Створити інтерактивну систему компіляції, в роботі якої брала би участь людина. Такі системи створені в рамках підпроєкту SUIF Explorer, в компіляторах Polaris і ParaWise.
Апаратна підтримка speculative multithreading.

Ранні компілятори розпаралелювання

Багато ранніх компіляторів розпаралелювання працювали з програмами, написаними на Fortran, через його більш строгі обмеженя на перетин покажчиків (aliasing) в порівнянні з С. Крім того, на Fortran написано велику кількість програм обчислювальної математики, що вимагають великих ресурсів для своєї роботи. Приклади компіляторів:

Paradigm compiler
Polaris compiler
Rice Fortran D compiler
SUIF compiler
Vienna Fortran compiler

Починаючи з стандарту Fortran 2008, ця мова програмування отримала архітектурно-незалежний вбудований синтаксис для паралельної декомпозиції даних та виконання інструкцій з допомогою комасивів, тому автоматичне розпаралелення з допомогою компілятора залишається корисною, але вже не надто важливою особливістю компіляторів мови фортран.

Сучасні компілятори з підтримкою розпаралелювання

Посилання

↑ Fox, Geoffrey; Roy Williams; Paul Messina (1994). Parallel Computing Works!. Morgan Kaufmann. с. 575, 593. ISBN 978-1-55860-253-3.
↑ Simone Campanoni, Timothy Jones, Glenn Holloway, Gu-Yeon Wei, David Brooks. «The HELIX Project: Overview and Directions» [Архівовано 27 травня 2015 у Wayback Machine.]. 2012.
↑ Automatic parallelism and data dependency. Архів оригіналу за 14 липня 2014. Процитовано 27 травня 2015.
↑ ^а ^б ^в Patrick Lam (10 лютого 2011). Lecture 12. We'll talk about automatic parallelization today (PDF). ECE459: Programming for Performance. Архів оригіналу (PDF) за 27 травня 2015. Процитовано 17 листопада 2013. [Архівовано 2015-05-27 у Wayback Machine.]
↑ ^а ^б Robert van Engelen (3 жовтня 2012). High-Performance Computing and Scientific Computing. HPC @ Florida State University. Архів оригіналу за 27 травня 2015. Процитовано 17 листопада 2013. [Архівовано 2015-05-27 у Wayback Machine.]

[pcworks-1] Fox, Geoffrey; Roy Williams; Paul Messina (1994). Parallel Computing Works!. Morgan Kaufmann. с. 575, 593. ISBN 978-1-55860-253-3.

[2] Simone Campanoni, Timothy Jones, Glenn Holloway, Gu-Yeon Wei, David Brooks. «The HELIX Project: Overview and Directions» [Архівовано 27 травня 2015 у Wayback Machine.]. 2012.

[3] Automatic parallelism and data dependency. Архів оригіналу за 14 липня 2014. Процитовано 27 травня 2015.

[lam2011-L12-4] а ^б ^в Patrick Lam (10 лютого 2011). Lecture 12. We'll talk about automatic parallelization today (PDF). ECE459: Programming for Performance. Архів оригіналу (PDF) за 27 травня 2015. Процитовано 17 листопада 2013. [Архівовано 2015-05-27 у Wayback Machine.]

[engelen12-5] а ^б Robert van Engelen (3 жовтня 2012). High-Performance Computing and Scientific Computing. HPC @ Florida State University. Архів оригіналу за 27 травня 2015. Процитовано 17 листопада 2013. [Архівовано 2015-05-27 у Wayback Machine.]

[1]

[2]

[3]

[4]

[5]