Автоматичне розпаралелювання – це конвертування коду в багатопотоковий, що працює на паралельному комп'ютері (наприклад, на комп'ютері з багатьма процесорами, процесорними ядрами або потоками виконання). Метою автоматизації розпаралелювання є звільнення програміста від трудомісткого процесу ручного розпаралелювання. Незважаючи на те, що якість автоматичного розпаралелювання значно покращилася за останні роки, повне розпаралелювання послідовних програм залишається занадто складним завданням, що вимагає дуже складних видів аналізу програм та ПЗ.[1]
Автоматичний паралелізатор зазвичай фокусується на таких керуючих конструкціях, як цикли, оскільки, в загальному випадку, більша частина виконання програми проходить всередині якихось циклів. Є два основні підходи до розпаралелювання циклів: конвеєрна багатопотоковість і циклічна багатопотоковість.[2]
Розглянемо, наприклад, цикл, який на кожній ітерації виконує 100 операцій, та має тисячу ітерацій. Це можна розглядати як табличку 100 стовпців на 1000 рядків, в цілому 100000 операцій.
Циклічна багатопотоковість — кожен рядок в іншому потоці.
Конвеєрна багатопотоковість — кожен стовпець в іншому потоці.
Циклічний багатопотоковий компілятор розпаралелювання намагається розділити цикл так, щоб кожна ітерація могла бути виконана на окремому процесорі одночасно.
Компілятор зазвичай проводить два проходи аналізу до фактичного розпаралелювання для того, щоб визначити наступне:
Перший прохід компілятора проводить аналіз залежність даних циклу щоб визначити, чи ітерації циклу можуть бути виконані незалежно один від одного.
Другий прохід намагається виправдати зусилля розпаралелювання шляхом порівняння теоретичного часу виконання коду після розпаралелювання з послідовним часом виконання. Хоч це й може звучати парадоксально, але вигода від паралельного виконання отримується не завжди. Додаткові накладні витрати, які можуть бути пов'язані з використанням декількох процесорів та особливості реалізації архітектури можуть нівелювати позитивний ефект прискорення.
Цикл називається 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
Тим не менш, компілятори розпаралелювання зазвичай не здатні автоматично зробити такі паралелізми, і сумнівно, що цей код отримає вигоду з паралелізації, в першу чергу.
Конвеєрний компілятор розпаралелювання намагається розбити послідовність операцій всередині циклу на послідовність кодових блоків, таких, що кожен блок коду може бути виконаним на окремих процесорах одночасно.
Є багато паралельних задач, які мають такі відносно самостійні блоки коду. Наприклад, при виробництві живого телевізійного мовлення, наступні завдання мають бути виконані повторно багато разів:
Конвеєрний компілятор розпаралелювання може призначити кожну з цих шести операцій на інший процесор.
Автоматичне розпаралелювання складно для компіляторів з причин:[3]
Через складність повного автоматичного розпаралелювання існує кілька підходів для його спрощення:
Багато ранніх компіляторів розпаралелювання працювали з програмами, написаними на Fortran, через його більш строгі обмеженя на перетин покажчиків (aliasing) в порівнянні з С. Крім того, на Fortran написано велику кількість програм обчислювальної математики, що вимагають великих ресурсів для своєї роботи. Приклади компіляторів:
Починаючи з стандарту Fortran 2008, ця мова програмування отримала архітектурно-незалежний вбудований синтаксис для паралельної декомпозиції даних та виконання інструкцій з допомогою комасивів, тому автоматичне розпаралелення з допомогою компілятора залишається корисною, але вже не надто важливою особливістю компіляторів мови фортран.