Суперскалярный стековий процесор: схрещуємо вужа і їжака


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

Фактично, продовження 1 & 2.
Введення
Чому стекова машина?
Філіп Купман пише: “з теоретичної точки зору стек важливий сам по собі, оскільки це основний і найбільш природний механізм для виконання добре структурованого коду… стекові машини істотно ефективніше регістрових процесорів при роботі з кодом, мають високу модульність. Крім того, вони дуже прості і демонструють відмінну продуктивність при досить скромних вимогах до залозу."

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

Вдалими зразками комп'ютерів з стекової архітектурою можна назвати Burroughs B5000 (1961...1986) і HP3000 (1974...2006). Не забудемо і про радянські Эльбрусы.

Так чому ж стекові машини зараз витіснені регістровими процесорами на узбіччя прогресу? Причини, думається, в наступному:
  1. Існують дві «крайні» реалізації стекових процесорів: з фіксованим апаратним стеком і стеком, розташованим в пам'яті. Обидві ці крайності мають суттєві вади: у разі стека фіксованого розміру, ми маємо проблеми з компілятором і/або операційною системою, які зобов'язані думати про те, що станеться, якщо стек переповниться або спорожніє і як відпрацювати відповідне переривання. Якщо обробка переривання відсутня, ми маємо справу з мікроконтролером, приреченим на те, щоб бути програмованим вручну. При наявності обробника такого переривання, апаратний стек грає роль «вікна» до пам'яті з швидким доступом, при цьому зрушення цього «вікна» — процедура досить дорога. В результаті ми маємо непередбачувану поведінку програми, що не дозволяє використовувати такий процесор, наприклад, в системах реального часу, хоча, з точки зору Купмана, це як раз екологічна ніша подібних процесорів.
  2. У разі ж стека, розміщеного цілком у пам'яті, ми платимо зверненням до пам'яті за практично кожну виконувану інструкцію. Таким чином, загальна продуктивність системи обмежена зверху пропускною здатністю пам'яті.
  3. Складність процесора давно перестала бути стримуючим фактором у розвитку.
  4. Апаратно реалізований стек передбачає сувору послідовність подій, що відбуваються, а, отже, і неможливість використовувати неявний паралелізм програм. Якщо суперскалярні процесори самі розподіляють інструкції з конвеєрів у відповідності з наявними ресурсами, а VLIW процесори чекають, що ця робота вже виконана за них компілятором, то для стекових машин спроба знайти в коді прихований паралелізм стикається з майже непереборними труднощами. Іншими словами, ми знову стикаємося з ситуацією, коли технологія може дати більше, ніж архітектура може собі дозволити. Що дивно.
  5. Програмування для регістрових машин «технологічно». Маючи всього лише кілька регістрів загального призначення, «вручну» легко можна створити код, який буде звертатися до пам'яті лише тоді, коли цього справді не можна уникнути. Зазначимо, що у разі стекової машини досягти цього набагато важче. І, хоча оптимальний розподіл тимчасових змінних по регістрах NP-повною задачею, існує кілька недорогих, але дієвих евристик, що дозволяють створювати цілком пристойний код за розумний час.
Були, звичайно і спроби сховати реєстрову машину всередині стекової обгортки, наприклад, Ignite або ICL2900, але комерційного успіху вони не мали, т. к. фактично, лише заради зручності компіляції, користувачі повинні були нести постійні витрати в runtime.

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

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

Розглянемо простий приклад, обчислення виразу x+y*z+u.
При побудові дерева розбору компілятором воно виглядає так:

Асемблерний код (x86) для цього виразу виглядає так:
mov eax,dword ptr [y] 
imul eax,dword ptr [z] 
mov ecx,dword ptr [x] 
add ecx,eax 
mov eax,ecx 
add eax,dword ptr [u] 

Для гіпотетичної стекової машини псевдокод такий:
push x
push y
push z
multiply
add
push u
add

Різниця наочна і очевидна, крім 4-х звернень до пам'яті, додавання і множення, у кожній інструкції регістрового процесора присутні ідентифікатори регістрів.

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

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

Яка плата за таку уніфікацію?
  1. З точки зору супер-скалярного процесора. Ось, наприклад, стаття від Intel, дослівно:
    Суперскаляр на ходу розпаралелює послідовний код. Але цей процес розпаралелювання занадто трудомісткий навіть для нинішніх процесорних потужностей, і саме він обмежує продуктивність машини. Робити це перетворення швидше певної кількості команд за такт неможливо. Можна зробити більше, але при цьому впаде тактова чистота – такий підхід, очевидно, бессмысленнен
    Ось ще з улюбленого:
    Біда не в самому суперскаляре, а в поданні програм. Програми представлені послідовно, і їх потрібно під час виконання перетворювати в паралельне виконання. Головна проблема суперскаляра – в непристосованості вхідного коду до його потреб. Є паралельний алгоритм роботи ядра і паралельно організована апаратна частина. Однак між ними, по середині знаходиться якась бюрократична організація – послідовна система команд
  2. З точки зору компілятора. Звідти ж:
    Компілятор перетворює програму в послідовну систему команд; від тієї послідовності, в якій він це зробить, буде залежати загальна швидкість процесу. Але компілятор не знає в точності, як працює машина. Тому, взагалі кажучи, робота компілятора сьогодні – це шаманство
    Компілятор докладає титанічних зусиль, щоб втиснути програму в задане число регістрів, а це число фіктивно. Весь виявлений у програмі паралелізм компілятор намагається (як канат у вушко голки) протягти крізь обмеження архітектури. Значною мірою безуспішно.
Що робити?
Проблема позначена — невідповідність інтерфейсу/архітектури сучасним вимогам.
Які ці нові вимоги?
  1. Весь відомий компілятору паралелізм повинен бути переданий без втрат.
  2. Витрати на розпаковування залежностей між інструкціями повинні бути мінімальними.
Знову звернемося до прикладу з компіляцією виразу x+y*z+u.
х86 стекова машина
mov eax,dword ptr [y]
imul eax,dword ptr [z]
mov ecx,dword ptr [x]
add ecx,eax
mov eax,ecx
add eax,dword ptr [u]
push x
push y
push z
multiply
add
push u
add
Регістри х86 призначені для вказівки зв'язку між різними інструкціями. А що в стекової машині, як там реалізовані ці залежності? Неявно, через положення в стеку. Кожна інструкція знає число своїх аргументів і чекає перед виконанням знайти їх на вершині стека.

А що, якщо, коли ми говоримо про вершині стека, це зовсім не обов'язково стек даних, а, швидше, стек операцій мікрооперацій, мдн-ів).
  • Зовні приходять стекові інструкції, але процесор насправді — регістровий, він вміє виконувати тільки цілком традиційні 'add r1 r2 r3'. Ось ці 'add ...' ми і звемо мопами. Якщо завгодно, мдн — універсальна заготівля під внутрішню інструкцію регістрового процесора.
  • У процесора є пул мопів, спочатку всі вони вільні, доступ по індексу.
  • мопа є супутня інформація, лінки — номери батьківських мопів, число предків, ...
  • Отже, першою прийшла інструкція 'push x' (x в даному випадку — адреса), декодером це транслюється в 'lload R?, 0x.....', у цього мопа немає вхідних аргументів, тільки вихідний.
  • Моп взято з пулу вільних, коли вільні мопи закінчуються, декодер призупиняє роботу.
  • Спочатку це 'lload R?, 0x.....' т. к. регістр не визначений.
  • Ось цей наш 'lload R?, 0x.....' ми поміщаємо на вершину стека індексів мопів.
  • Далі йдуть 'push y;push z' з ними ми проробляємо те ж саме. Тепер в стеку мопів три завантаження.
  • Далі йде 'multiply', для неї декодер робить моп 'lmul R? R? R?'.
  • Оскільки декодер знає, що для цієї інструкції потрібні 2 аргумент, він бере (і видаляє) з вершини стека два верхніх мопа і линкует з даними. Після чого індекс мопа 'multiply' заноситься на вершину стека.
  • Далі йде 'add' з ним все аналогічно, тільки що один аргумент — завантаження з пам'яті, другий — множення.
  • Коли індекс мопа пішов з стека, його (моп) можна намагатися виконати. Перший у нас 'push x', який тепер 'lload R?, 0x.....'
  • Для вихідного аргумента беремо перший-ліпший регістр (R1, наприклад) і позначаємо його як зайнятий. Оскільки цей моп нікого не чекає, що його можна ставити на конвеєр на виконання.
  • Після того, як цей моп виповнився, ми сповіщаємо спадкоємця (тільки одного, це ж дерево), якщо є, при цьому у нього визначається номер регістра аргументу і зменшується лічильник батьківських мопів.
  • Якщо вхідні аргументи утримують регістр(и), їх (регістр(и)) можна звільнити
  • Якщо лічильник очікуваних мопів (у дочірнього мопа) став дорівнює 0, то цей моп теж можна перекладати у відповідний конвеєр.
  • ...
Які бувають типи мопів?
  1. Операції з регістрами, наприклад, додавання: значення двох регістрів підсумовуються і поміщаються у третій. Ці мопи бувають двійкові — перед приміщенням в стек з нього видаляються посилання на два верхніх мопа і заноситься посилання на цей. А також унарні — зміна знака, наприклад. При створенні такої операції її посилання заміщує собою посилання на вершині стека.
  2. Операції з пам'яттю — завантаження значення з пам'яті в регістр і навпаки. Завантаження з пам'яті не має попередників і просто заноситься в стек мопів. Вивантаження в пам'ять прибирає один елемент стека. Завантаження з пам'яті додає в стек своє посилання.
  3. Особлива операція — pop, це просто вказівка декодеру прибрати елемент з вершини стека.
  4. Інші — розгалуження, виклики функцій, службові, поки не будемо розглядати
Для операцій з пам'яттю виникає особливий вид зв'язку між мопами — через адресу, наприклад, ми завантажили значення в пам'ять і тут же читаємо його з пам'яті в регістр. Формально між цими операціями немає зв'язку через регістр, фактично вона є. Іншими словами, буде непогано перед читанням дочекатися кінця запису. Тому для мопів в кеші декодера необхідно відстежувати подібні залежності. За межами кешу ця проблема вирішується серіалізацією через шину доступу до пам'яті.

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

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

Не будемо поспішати і потренуємося на чому — небудь простому, наприклад
long d1, d2, d3, d4, d5, d6, d7, d8;
d1 = 1; d2 = 2;
d3 = 3; d4 = 4;
d5 = 5; d6 = 6;
d7 = 7; d8 = 8;
print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); // налагоджувальна функція друку

Але перш варто визначитися з параметрами моделі процесора.
  1. 32 цілочисельних регістру
  2. декодується 4 інструкції за такт
  3. один конвеєр для роботи з пам'яттю, завантаження і вивантаження слова в/з регістра займає 3 такту
  4. 2 конвеєра з АЛУ, операція додавання/віднімання займає 3 такту, порівняння — 1 такт
Тут і надалі показано інструкції в момент закінчення їх виконання (коли регістри вже визначені) в тому, конвеєрі, де вони справдилися:
такт конв. пам'яті конв. N1 конв. N2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
32
35
LLOAD r3
LLOAD r2
LLOAD r1
LLOAD r0
LLOAD r7
LLOAD r6
LLOAD r5
LLOAD r4
LSTORE r3
LSTORE r2
LSTORE r1
LSTORE r0
LSTORE r7
LSTORE r6
LSTORE r5
LSTORE r4
LLOAD r11
LLOAD r10
LLOAD r8
LLOAD r15
LLOAD r12
LLOAD r19
LLOAD r17
LLOAD r16

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
LADD r10 r11 -> r9
 
LADD r8 r15 -> r14
 
LADD r12 r19 -> r18
LADD r9 r14 -> r13
LADD r16 r17 -> r23
LADD r18 r23 -> r22
LADD r13 r22 -> r21
                              
І в регістрі 21 до 35 такті отримуємо значення заповітне 36.
Дані з тієї ж таблиці, але у вигляді діаграми залежностей мопів, в дужках [] — номер такту завершення мопа (x&y тут не мають сенсу, значення є тільки у напрямку стрілок).

Що ми бачимо?
  • перші 8 інструкцій LLOAD — завантаження констант
  • далі 8 LSTORE — ініціалізація змінних константами. Може здатися дивним, що вони сериализовались подібним чином, адже спочатку вони (LOAD&STORE) були упереміш. Але варто згадати, що завантаження константи з пам'яті йде 3 такту, по 4 інструкції за такт. Поки перша константа чекає завантаження, операції LSTORE в силу своєї залежності опинилися в конвеєрі позаду LLOAD. ТОВ в дії, до речі.
  • Здається дивним, що маючи 2 конвеєра і очевидний паралелізм ми не змогли завантажити обидва конвеєра. З іншого боку, остання завантаження з пам'яті закінчилася через 26 тактів (8*3+2). Дерево виразу має глибину три по три такти на крок. Сумарно, 26 + 9 = 35 тактів, швидше обчислити це неможливо в принципі. Тобто для обчислення даного коду максимально швидким способом досить і одного цілочисельного конвеєра.
Спробуємо те ж, але без явної ініціалізації змінних.
long d1, d2, d3, d4, d5, d6, d7, d8;
print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); // налагоджувальна функція друку
такт конв. пам'яті конв. N1 конв. N2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LLOAD r3
LLOAD r2
LLOAD r0
LLOAD r7
LLOAD r4
LLOAD r11
LLOAD r9
LLOAD r8

 
 
 
 
LADD r3 r2 -> r1
 
LADD r0 r7 -> r6
 
LADD r4 r11 -> r10
LADD r1 r6 -> r5
LADD r8 r9 -> r15
 
 
LADD r10 r15 -> r14
 
 
LADD r5 r14 -> r13
                              
Обчислення зайняло 8+2 + 3*3 = 19 тактів, мінімальне з можливого, знову одного конвеєра виявилося достатньо.

Тепер спробуємо прибрати всі дужки і просто підсумувати змінні.
long d1, d2, d3, d4, d5, d6, d7, d8;
print_long (d1+d2+d3+d4+d5+d6+d7+d8); // налагоджувальна функція друку
такт конв. пам'яті конв. N1 конв. N2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
LLOAD r3
LLOAD r2
LLOAD r0
LLOAD r6
LLOAD r4
LLOAD r10
LLOAD r8
LLOAD r14

 
 
 
 
LADD r3 r2 -> r1
 
 
LADD r1 r0 -> r7
 
 
LADD r7 r6 -> r5
 
 
LADD r5 r4 -> r11
 
 
LADD r10 r11 -> r9
 
 
LADD r8 r9 -> r15
 
 
LADD r14 r15 -> r13
 
                              
В даному випадку є залежність за даними і неможливість повноцінно завантажити конвеєр призвела до зайвих 6 тактів.

Як щодо вивернути вираз навиворіт?
long d1, d2, d3, d4, d5, d6, d7, d8;
print_long (d1+(d2+(d3+(d4+(d5+(d6+(d7+d8))))))); // тестова функція друку
Це коштувало ще додаткових тактів т. к. завантаження даних йде не в оптимальному порядку.

Дивно що при наявності явного паралелізму і двох цілочисельних конвеєрів, другий з них простоює. Спробуємо поворухнути систему. Повернемося при цьому до
long d1, d2, d3, d4, d5, d6, d7, d8;
print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); // налагоджувальна функція друку

Спробуємо збільшити швидкість доступу до пам'яті, нехай читання в регістр відбувається за 1 такт. Цікаво, але мало що змінилося. Загальний час зменшилася на 2 такти, точніше, вся картина зрушилася вгору на 2 такти. Воно і зрозуміло, пропускна здатність пам'яті не змінилася, ми просто прибрали затримку до отримання першого результату.

Можливо, підсумовування йде занадто швидко. Нехай воно робиться 7 тактів замість 3.
Загальний час зросла до 29 (8+3*7) тактів, але принципово нічого не змінилося, другий конвеєр простоює.

Спробуємо підсумувати пірамідкою 16 чисел і введемо 2 конвеєра пам'яті. Загальний час — 36 тактів (16/2+4*7). Другий числовий конвеєр не був задіяний. Числа тепер надходять парами, всі 8 підсумовувань першого рівня стартують з затримкою в такт і цього достатньо, щоб все вклалося в одному конвеєрі.

І тільки якщо ввести 4 конвеєра пам'яті і дозволити 6 декодирований за такт, справа доходить до другого числового конвеєра (в ньому здійснилися аж 3 (sic!) інструкції), загальний час тим не менше — 33 такту. Тобто ефективність власне підсумовувань навіть погіршилася.

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

Розподіл регістрів
У наведених вище прикладах призначення регістрів відбувалося в момент створення мопів. В результаті карта використання регістрів при підсумовуванні змінних пірамідкою виглядає так (вихідні параметри — 4 інструкції декодуються за такт, один конвеєр пам'яті, по три такти на читання і підсумовування):
8 змінних 16 змінних
Якщо ж призначати регістри в момент постановки інструкції в конвеєр, картина виглядає помітно краще:
8 змінних 16 змінних
Для контролю варто навести і діаграми залежностей інструкцій (8 цифр):
Виклик функцій
Із загальних міркувань у описуваної архітектури очікуються проблеми з викликом функцій. Справді, після повернення з функції ми очікуємо і повернення стану регістрів в контексті поточної функції. В сучасних регістрових архітектурах для цього регістри діляться на дві категорії — за збереження одних відповідає викликає сторона, інших — викликається.

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

Втім, вирішувати цю проблему ми будемо в наступній статті.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.