Паралелізм на рівні машинних команд

Паралелізм на рівні машинних команд

Суперскалярні процесори (ССП)

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

У більшості сучасних задач переважна частина змінних саме скалярні величини.

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

Суть суперскалярної організації полягає в можливості незалежно виконувати команди паралельно на різних конвеєрах.

Розвиток даної концепції привів до виникнення ідеї змінювати при необхідності порядок виконання команд в порівнянні з тим, в якому вони розміщені в машинному коді.

Рис. 1. Схема суперскалярної організації процесора В суперскалярній організації процесор має кілька функціональних вузлів, які паралельно виконують кілька машинних команд, причому кожен вузол організований у виді конвеєра. В даному процесорі одночасно можуть виконуватись дві арифметичні команди з цілими числами, 2 арифметичні команди з операндами з плаваючою крапкою, одна команда звернення до пам’яті.

Суперконвеєрна організація — альтернативний підхід до рішення проблеми підвищення продуктивності процесора.

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

Наведена на рис. 2 діаграма дозволяє порівняти:

§ Суперконвеєрний СК

§ Суперскалярний підходи СС У верхній частині діаграми показано як працює звичайний конвеєр по якому далі порівнюється швидкодія СК і СС підходів.

В базовій схемі в кожному черговому такті (основний або зовнішній такт) на конвеєр поступає одна машинна команда і на протязі такту на кожній позиції конвеєра виконується одна команда.

IF — добування команди;

DC — розшифровка команди;

FX — виконання команди;

WR — запис результату.

Внизу показано як працює суперскалярна схема в якій паралельно функціонують два конвеєри. Це суперскалярна схема степені 2.

На практиці зустрічаються СК і СС схеми і більш високих степенів.

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

Рис. 2. Часова діаграма роботи процесорів з суперконвеєрною і суперскалярною організацією.

Конвеєр має 4 робочі позиції, на яких виконуються наступні команди:

Обмеження СС

паралелізм суперскалярний процесор Продуктивність процесора з СС організацією залежить від того, на скільки можливо в конкретній програмі виконувати команди паралельно і незалежно одна від одної.

Під паралелізмом на рівні команд (instruction-level-parallelism) розуміють можливість паралельно виконувати команди у певній програмі.

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

Фундаментальні обмеження можливостей розпаралелення операцій в комп’ютері:

1. Взаємозалежність по даним;

2. Процедурна залежність;

3. Конфлікт у використанні ресурсів;

4. Залежність по виходу;

5. Зворотна залежність.

Взаємозалежність по даним

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

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

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

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

В процесорі з єдиним скалярним конвеєром виконання наведеної послідовності команд не викликає ніякої затримки.

Процедурна залежність

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

На рис. 4. i1 — команда умовного переходу. Тут наслідки для СС більш серйозні, ніж для одного конвеєра. Оскільки приходиться відкладати виконання великої кількості операцій.

Рис. 4. Вплив процедурної залежності на роботу суперскалярного процесора Ще один варіант процедурної залежності - виконання команд змінної довжини.

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

Конфлікт ресурсів

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

Приклади ресурсів:

— Пам'ять;

— Кеш;

— Системна магістраль;

— Порти набору регістрів;

— Вузли АЛП.

Конфлікт ресурсів проявляється на роботі конвеєра приблизно так само як залежність від даних.

Деяких конфліктів у боротьбі за деякі ресурси можна уникнути, якщо дублювати відповідні вузли, а усунути залежність між даними не можна.

Паралелізм на рівні команд

Даний паралелізм існує тоді, коли команди в послідовності незалежні і можуть виконуватись паралельно, з перекриттям.

Приклад: Load R1 < R2 Add R3 < R3

Add R3 < R3 Add R4 < R3

Add R4 < R4 Store [R4] < R0

В лівому фрагменті всі три команди незалежні, і теоретично їх можна виконувати паралельно.

В правому фрагменті кожна наступна команда використовує виконання попередньої. Тому дані команди прийдеться виконувати послідовно одну за одною.

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

Степінь паралелізму на рівні команд також визначається операційною латентністю (operational latency) — часом, до закінчення якого результат операції недоступний для використання в ролі операнда у наступних командах. Операційна латентність визначає затримку, яку вносять взаємозалежність по даним і процедурна залежність у процес виконання незалежних команд.

Апаратний паралелізм

Апаратний паралелізм — це міра здатності процесора отримувати переваги із паралелізму на рівні команд.

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

Обидва показники — і степінь паралелізму на рівні команд і степінь апаратного паралелізму — є важливими факторами підвищення продуктивності комп’ютера при виконанні прикладних задач певного класу.

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

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

Політика запуску команд

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

Під політикою запуску команд (instruction issue policy) розуміють протокол, використовуваний для ініціювання обробки команд у фіксованих вузлах процесора.

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

Три варіанти впорядкування команд при їх запуску:

1. порядок, в якому команди добуваються з пам’яті;

2. порядок, в якому команди виконуються процесором;

3. порядок, в якому команди поновлюють вміст певного регістру або комірки пам’яті.

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

Виходячи із сказаного, можна реалізувати різні варіанти політики запуску команд.

Варіанти політики:

1. прямий порядок запуску команд і прямий порядок їх завершення;

2. прямий порядок запуску команд і вільний порядок їх завершення,

3. Вільний порядок запуску команд і вільний порядок їх завершення.

Прямий порядок запуску команд і прямий порядок їх завершення

Найбільш простий варіант політики запуску команд полягає в тому, що команди запускаються на обробку в тій же послідовності в якій вини розміщені в початковій машинній програмі. (in-order issue) і результати записуються по призначенню в тому порядку (in-order completion).

Приклад:

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

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

Особливості команд фрагменту:

— Виконання команди i1 займає два такти;

— Для виконання команди i3 і i4 потрібний один і той же ресурс процесора — конфлікт у використанні ресурсів;

— Команда i5 залежить від результатів виконання команди i4.

— При виконанні i5 і i6 також виникає конфлікт у використанні функціонального вузла процесора.

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

В цьому варіанті організації процесора обробка фрагменту програми — від моменту розшифровки першої команди до запису результату останньої команди займає вісім тактів.

Прямий порядок запуску команді вільний порядок їх завершення

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

Приклад:

Виконання команди i2 завершується раніше, ніж i1. Це дозволяє завершити раніше на один такт і команду i3 і прискорити таким чином на один такт виконання всього фрагменту.

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

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

Вільний порядок запуску команд і вільний порядок їх завершення

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

Напрошується думка реалізувати вільний порядок запуску команд. Для цього потрібно між позиціями розшифровки і виконання команд вставити проміжний буфер, який прийнято називати вікном команд (instruction window). При такій організації команда, обробляється на позиції розшифровки і поміщається у вікно команд. До тих пір поки цей буфер не заповниться, процесор може продовжувати добувати і розшифровувати нові команди програми. Коли необхідний функціональний вузол стає доступним для виконання команди, вона добувається із вікна і передається на позицію виконання конвеєра. При цьому із вікна може бути добута люба команда, для виконання якої необхідний даний функціональний вузол і виконанню якої не перешкоджає яка-небудь залежність або конфлікт.

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

Реалізація такої політики схематично показана в наведеному прикладі .

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

Приклад:

Перейменування регістрів

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

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

Один із способів вирішення подібних конфліктів — традиційний: дублювання ресурсів. У даному контексті він називається перейменуванням регістрів. Фактично регістри розподіляються динамічно схемами процесора і зв’язуються з даними, які необхідні для виконання тих або інших команд в різні моменти часу. Коли формується нова величина, для зберігання якої необхідний регістр, з цією величиною зв’язується новий регістр. Наступні команди, в яких дана величина є операндом-джерелом, теж повинні пройти через процес перейменування — посилання на певний регістр в них повинні бути замінені посиланнями на регістр, виділений для цієї величини. Таким чином, регістр, позначений у вихідній програмі, яка сформована компілятором, стає логічним, а процесор на свій розсуд може асоціювати з ним фізичний регістр.

Обробка умовних переходів

В любому комп’ютері, в якому використовується конвеєр операцій, суттєва увага приділяється обробці команд умовного переходу. Наприклад в процесорі Intel 80 486 ця проблема рішається наступним чином: добувається як команда, яка безпосередньо слідує за командою розгалуження, так і команда, розміщена за адресою переходу. Але оскільки між добуванням і виконанням команда повинна пройти ще дві робочі позиції конвеєра, появляється затримка у два такти, перш ніж буде виявлено чи потрібно виконати перехід.

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

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

В деяких процесорах, наприклад PowerPC 620 і Pentium II, застосовуються динамічні методи добування команди у точці переходу з аналізом передісторії.

Виконання програми у суперскалярному процесорі

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

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