3. Паралелізм рівня циклу: концепції та методи

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

Розглянемо наступний цикл:

for (i=1; i<=100; i=i+1) {

A[i+1] = A[i] + C[i]; /* S1 */

B[i+1] = B[i] + A[i+1];} /*S2*/

}

Припустимо, що A, B і C являють собою окремі, що не перекриваються масиви. (На практиці іноді масиви можуть бути тіж самі або перекриватися. Оскільки масиви можуть передаватися як параметри деякій процедурі, що містить цей цикл, визначення того, чи перекриваються масиви або вони збігаються, вимагає витонченого, межпроцедурного аналізу програми). Які залежності за даними мають місце між операторами цього циклу?

Є дві різних залежності:

1. S1 використає значення, що обчислює оператором S1 на більше ранній ітерації, оскільки ітерація i обчислює A[i+1], що зчитується в ітерації i+1. Те ж саме справедливо для оператора S2 для B[i] і B[i+1].

2. S2 використає значення A[i+1], що обчислює оператором S1 у тій же самій ітерації.

Ці дві залежності відрізняються друг від друга й мають різний ефект. Щоб побачити, чим вони відрізняються, припустимо, що в кожний момент часу існує тільки одна із цих залежностей. Розглянемо залежність оператора S1 від більше ранньої ітерації S1. Ця залежність (loop-carried dependence) означає, що між різними ітераціями циклу існує залежність за даними. Більше того, оскільки оператор S1 залежить від самого себе, послідовні ітерації оператора S1 повинні виконуватися впорядковано.

Друга залежність (S2 залежить від S1) не передається від ітерації до ітерації. Таким чином, якби це була єдина залежність, кілька ітерацій циклу могли б виконуватися паралельно, за умови, що кожна пара операторів в ітерації підтримується в заданому порядку.

Є третій тип залежностей за даними, що виникає в циклах, як показано в наступному прикладі.

Розглянемо цикл:

for (i=1; i<=100; i=i+1) {

A[i] = A[i] + B[i]; /* S1 */

B[i+1] = C[i] + D[i]; /* S2 */

}

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

Незважаючи на цю залежність, цей цикл може бути зроблений паралельним. Як і в більше ранньому циклі ця залежність не циклічна: жоден з операторів не залежить сам від себе й хоча S1 залежить від S2, S2 не залежить від S1. Цикл є паралельним, якщо тільки відсутня циклічна залежність.

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

1. Залежність від S1 до S2 відсутній. Якби вона була, то в залежностях з'явився б цикл і цикл не був би паралельним. Внаслідок відсутності інших залежностей, перестановка двох операторів не буде впливати на виконання оператора S2.

2. У першій ітерації циклу оператор S1 залежить від значення B[1], що обчислює перед початком циклу.

Ці два зауваження дозволяють нам замінити вище наведений цикл наступною послідовністю:

A[1] = A[1] + B[1];

for (i=1; i<=99; i=i+1) {

B[i+1] = C[i] + D[i];

A[i+1] = A[i+1] + B[i+1];

}

B[101] = C[100] + D[100];

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

Основна увага в частині, що залишилася, від нашого розгляду, зосереджена на методах виявлення паралелізму рівня команд. Залежності за даними у відкомпільованих програмах являють собою обмеження, які впливають на те, яка ступінь паралелізму може бути використана. Питання полягає в тім, щоб підійти до цієї межі шляхом мінімізації дійсних конфліктів і пов'язаних з ними призупинень конвеєра. Методи, які ми вивчаємо стають усе більше витонченими в прагненні використання всього доступного паралелізму при підтримці щирих залежностей за даними в коді програми. Як компілятор, так і апаратура тут грають свою роль: компілятор намагається усунути або мінімізувати залежності, у той час як апаратура намагається запобігти перетворенню залежностей у призупинення конвеєра.