Залежності

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

Тому, якщо між двома командами існує взаємозалежність, то вони не є паралельними. Є три типи залежностей: залежності по даним, залежності по іменах і залежності по керуванню. Команда j залежить за даними від команди i, якщо має місце кожне з наступних умов:

• команда i виробляє результат, що використовує команда j

• команда j є залежною за даними від команди k, а команда k є залежною за даними від команди i

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

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

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

Дані можуть передаватися від команди до команди або через регістри, або через комірки пам'яті. Коли дані передаються через регістри, виявлення залежностей значно спрощується, оскільки імена регістрів зафіксовані в командах (хоча цей процес стає більше складним, якщо втручаються умовні переходи). Залежності за даними, які передаються через комірки пам'яті, виявити значно складніше, оскільки дві адреси можуть відноситись до однієї й тієї ж комірці пам'яті, але зовні виглядають по різному (наприклад, 100(R4) і 20(R6) можуть визначати одну адресу). Крім того, ефективна адреса команди завантаження або записи може мінятися від одного виконання команди до іншого (так що 20(R4) і 20(R4) будуть визначати різні адреси), ще більше ускладнюючи виявлення залежності. Ми розглянемо як апаратні, так і програмні методи виявлення залежностей за даними, які пов'язані з комірками пам'яті. Методи компіляції для виявлення таких залежностей є дуже важливими при виявленні паралелізму рівня циклу.

Другим типом залежностей у програмах є залежності по іменах. Залежності по іменах виникають коли дві команди використовують те саме ім'я (або регістра, або комірки пам'яті), але при відсутності передачі даних між командами. Є два типи залежності імен між командою i, що передує команді j у програмі:

1. Антизалежність між командою i і командою j виникає тоді, коли команда j записує в регістр або комірку пам'яті, котрий(у) команда i зчитує й команда i виконується першою. Антизалежність відповідає конфлікту типу WAR, і виявлення конфліктів типу WAR означає впорядковування виконання пари команд із антизалежністю.

2. Залежність по виходу виникає коли команда i і команда j записують результат у той самий регістр або в ту саму комірку пам'яті. Порядок виконання цих команд повинен зберігатися. Залежності по виходу зберігаються шляхом виявлення конфліктів типу WAW.

Як антизалежності, так і залежності по виходу є залежностями по іменах, на відміну від залежностей за даними, оскільки в них відсутня передача даних від однієї команди до іншої. Це означає, що команди, зв'язані залежністю по іменах, можуть виконуватися одночасно або можуть бути з, якщо ім'я (номер регістра або адреса комірки пам'яті), що використовується в командах змінюється так, що команди не конфліктують. Це перейменування може бути виконане більш просто для регістрових операндів і називається перейменуванням регістрів (register renaming). Перейменування регістрів може виконуватися або статично компілятором, або динамічно апаратними засобами.

Як приклад розглянемо наступну послідовність команд:

ADD R1,R2,R3

SUB R2,R3,R4

AND R5,R1,R2

OR R1,R3,R4

У цій послідовності є антизалежність по регістру R2 між командами ADD і SUB, що може привести до конфлікту типу WAR. Її можна усунути шляхом перейменування регістра результату команди SUB, наприклад, на R6 і зміни всіх наступних команд, які використають результат команди вирахування, для використання цього регістра R6 (у цьому випадку це тільки останній операнд у команді AND). Використання R1 у команді OR приводить як до залежності по виходу з командою ADD, так і до антизалежності між командами ADD і AND. Обидві залежності можуть бути усунуті шляхом заміни регістра результату або команди ADD, або команди OR. У першому випадку повинна змінитися кожна команда, що використовує результат команди ADD перш ніж команда OR запише в регістр R1 (а саме, другий операнд команди AND у даному прикладі). У другому випадку при заміні регістра результату команди OR, всі наступні команди, що використають її результат, повинні також змінитися. Альтернативою перейменуванню в процесі компіляції є апаратне перейменування регістрів, що може бути використане в ситуаціях, коли виникають умовні переходи, які можливо складні або неможливі для аналізу компілятором; у наступному розділі ця методика обговорюється більш докладно.

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

if p1 {

S1;

};

if p2 {

S2;

}

S1 є залежним по керуванню від p1, а S2 залежить по керуванню від p2 і не залежить від p1.

Є два обмеження, пов'язані із залежностями по керуванню:

1. Команда, що залежить по керуванню від умовного переходу, не може бути в результаті переміщення поставлена перед командою умовного переходу так, що її виконання більше не управлялося б цим умовним переходом. Наприклад, ми не можемо взяти команду із частини "then" оператора if і поставити її перед оператором if.

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

Наступний приклад ілюструє ці два обмеження:

ADD R1,R2,R3

BEQZ R12,skipnext

SUB R4,R5,R6

skipnext: OR R7,R1,R9

MULT R13,R1,R4

У цій послідовності команд є наступні залежності по керуванню (передбачається, що переходи не затримуються). Команда SUB залежить по керуванню від команди BEQZ, оскільки зміна порядку проходження цих команд змінить і результат обчислень. Якщо поставити команду SUB перед командою умовного переходу, результат команди MULT не буде тим же самим, що й у випадку, коли умовний перехід є виконуваним. Аналогічно, команда ADD не може бути поставлена після команди умовного переходу, оскільки це приведе до зміни результату команди MULT, коли перехід є виконуваним. Команда OR не є залежною по керуванню від умовного переходу, оскільки вона виконується незалежно від того, чи є перехід виконуваним чи ні. Оскільки команда OR не залежить за даними від попередніх команд і не залежить по керуванню від команди умовного переходу, вона може бути поставлена перед командою умовного переходу, що не приведе до зміни значення, що обчислює цією послідовністю команд. Звичайно це припускає, що команда OR не викликає ніяких побічних ефектів (наприклад, виникнення виняткової ситуації). Якщо ми хочемо з команди з подібними потенційними побічними ефектами, потрібен додатковий аналіз компілятором або додатковою апаратною підтримкою.

Звичайно залежності по керуванню зберігаються за допомогою двох властивостей простих конвеєрів, подібних розглянутим попередньо. По-перше, команди виконуються в порядку, запропонованому програмою. Це гарантує, що команда, що стоїть перед командою умовного переходу, виконується перед переходом; таким чином, команда ADD у вище наведеній послідовності буде виконуватися перед умовним переходом. По-друге, засоби виявлення конфліктів по керуванню або конфліктів умовних переходів гарантують, що команда, залежна по керуванню від умовного переходу, не буде виконуватися доти, поки не відомий напрямок умовного переходу. Зокрема команда SUB не буде виконуватися доти, поки машина не визначить, що умовний перехід є невиконуваним.

Хоча збереження залежностей по керуванню є корисним і простим способом забезпечення коректності програми, сама по собі залежність по керуванню не є фундаментальним обмеженням продуктивності. Можливо ми були б раді виконувати команди, які не повинні виконуватися, тим самим порушуючи залежності по керуванню, якби могли це робити не порушуючи коректність програми. Залежність по керуванню не є критичною властивістю, що повинне зберігатися. У дійсності, двома властивостями, які є критичними з погляду коректності програми і які звичайно зберігаються за допомогою залежностей по керуванню, є поводження виняткових ситуацій (exception behavior) і потік даних (data flow).

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

BEQZ R2,L1

LW R1,0(R2)

L1:

У цьому випадку, якщо ми ігноруємо залежність по керуванню й ставимо команду завантаження перед командою умовного переходу, команда завантаження може викликати виняткову ситуацію по захисту пам'яті. Помітимо, що тут залежність за даними, що перешкоджає перестановці команд BEQZ і LW, відсутній, це тільки залежність по керуванню. Подібна ситуація може виникнути й при виконанні операції із ПК, що може викликати виняткову ситуацію. У кожному разі, якщо перехід виконується, то виняткова ситуація не виникне, якщо команда не ставиться вище команди умовного переходу. Щоб дозволити переупорядкування команд ми хотіли б саме ігнорувати виняткову ситуацію, якщо перехід не виконується.

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

ADD R1,R2,R3

BEQZ R4,L

SUB R1,R5,R6

L: OR R7,R1,R8

У цьому прикладі значення R1, використовується командою OR, залежить від того, виконується або не виконується умовний перехід. Однієї залежності за даними не досить для збереження коректності програми, оскільки вона має справу тільки зі статичним порядком читання й запису. Таким чином, хоча команда OR залежить по даним як від команди ADD, так і від команди SUB, цього недостатньо для коректного виконання. Коли виконуються команди, повинен зберігатися потік даних: якщо перехід не виконується, то команда OR повинна використати значення R1, обчислене командою SUB, а якщо перехід виконується - значення R1, обчислене командою ADD. Перестановка команди SUB на місце перед командою умовного переходу не міняє статичної залежності, але вона виразно вплине на потік даних і в такий спосіб приведе до некоректного виконання. При збереженні залежності по управлінню команди SUB від умовного переходу, ми запобігаємо незаконній зміні потоку даних. Виконання команд по припущенню та умовні команди, які допомагають вирішити проблему виняткових ситуацій, дозволяють також змінити залежність по керуванню, підтримуючи при цьому правильний потік даних.

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

ADD R1,R2,R3

BEQZ R12,skipnext

SUB R4,R5,R6

ADD R5,R4,R9

skipnext: OR R7,R8,R9

Припустимо, що ми знаємо, що регістр результату команди SUB (R4) не використовується після команди, позначеної міткою skipnext. (Властивість, що визначає, чи буде значення використовуватися наступними командами, називається живучістю (liveness) і ми незабаром визначимо його більш формально). Якби регістр R4 не використався, то зміна значення R4 прямо перед виконанням умовного переходу не вплинуло б на потік даних. Таким чином, якби регістр R4 не використався і команда SUB не могла виробити виняткову ситуацію, ми могли б помістити команду SUB на місце перед командою умовного переходу, оскільки на результат програми ця зміна не впливає. Якщо перехід виконується, команда SUB виконається й буде марна, але вона не вплине на результат програми. Цей тип планування коду іноді називається плануванням по припущенню (speculation), оскільки компілятор в основному робить ставку на результат умовного переходу; у цьому випадку передбачається, що умовний перехід звичайно є невиконуваним.

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

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