Суперскалярный стековий процесор: подробиці



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

Попередні статті:
1 — опис роботи на лінійному шматку
2 — виклик функцій, зберігаємо регістри

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

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

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


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

Однак, є проблема з тим, що декодер встигне обробити код після виклику функції, якщо він незалежний за даними. Наприклад:
int i, j, k;
...
i = foo (i + 1);
j += k;
bar (i, j);

Після повернення з foo ми не можемо покладатися ні на те, що j встигла вычислиться і збережена (а потім відновлена) в контексті поточної задачі, ні на те, що збереглися мопи від j += k; якщо вычислиться вона не встигла.

Припустимо, побачивши виклик функції декодер припиняє свою роботу аж до повернення з цієї функції. Тоді як бути з такою ситуацією:
int i, j, k;
...
bar (foo (i + 1), j += k);

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

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

Добре, давайте поглянемо на Sandy Bridge від Intel (спасибі Таситу Мурки aka Felid
а також тут

Sandy Bridge.

Імовірно, фронтенд Sandy Bridge,

  • виконуваний код потрапляє в буфер предекодера (у лівому верхньому куті схеми) з кешу інструкцій першого рівня (L1I)
  • предекодер вміє обробляти до 7 інструкцій за такт залежно від їх сукупної довжини і складності
  • розмічені команди потрапляють в одну з двох черг (IQ) команд — по одній на потік (hyperthreading), на 20 команд кожна
  • декодер поперемінно читає команди з черг і переводить їх в мопи
  • в залежності від типу команди, декодер використовує різні типи трансляторів
  • результат декодування надходить в кеш мопів і два буфера мопів (hyperthreading)
  • кешуються вирівняні шматки (порції) по 32 байти вихідного коду, при цьому:
    • ключем є точка входу в порцію, якщо в одну порцію були переходи в різні місця, ця порція буде розмножена в кеші
    • декодування порції починається з її точки входу

    • кешуються тільки порції, які породили не більше 18 мопів — 3 рядки по 6 мопів
    • інструкція, розділена кордоном двох порцій, відноситься до першої з них
    • з порції дозволено мати не більше 6 переходів, тільки один з них може бути безумовним і останнім одночасно. Це важливо т. к. виклик функції — безумовний перехід і все що відбувається після нього не потрапить у поточну одиницю кешування, а значить і не буде виконуватися до тих пір, поки ми не спробуємо повернутися назад.
    • якщо порція не закінчується безумовним переходом, відбувається перехід на першу інструкцію наступного за адресою секції
    • кеш мопів (L0m) синхронізований з L1I, в останньому рядок кеша — 64 байта, так що при витісненні рядка L1I, з L0m видаляється все що стосується двох порцій
    • просто цікаво, L1I працює з фізичними адресами, L0m — з віртуальними
  • Що стосується спекулятивного виконання:
    • провісник переходів (BPU) уміє для мопа умовного переходу повідомляти ймовірність настання події цього переходу

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

      • все, що може викликати виключення (ділення на 0, наприклад), позначається відповідним чином і також блокується, втім, це узагальнення попереднього пункту. Тепер при настанні переходу ми можемо чесно рестартовать заблоковані мопи
      • і, звичайно, варто нагадати, що все це лише припущення, реальну картину знає тільки Інтел
Як же відбувається виклик функції?
Розглянемо наступний приклад
int i, j, k, l, m, n;
...
i = 1 + foo (1 + bar (1 + biz (1 + baz (1 + j) + k) + l) + m) + n;

Будемо наївно припускати, що весь цей код розміститься в одну 32 байтовую порцію і порядок генерації коду (при відключеному оптимізаторі) буде відповідати порядку тексту. Розмітимо код у відповідності з тим, якою примірник секції він потрапить в кеші L0m:
int i, j, k, l, m, n;
...
1> i = 1 + 
4> foo (
1> 1 + 
3> bar (
1> 1 + 
2> biz (
1> 1 + 
1> baz (1 + j) 
2> + k) 
3> + l) 
4> + m) 
5> + n;
Цей фрагмент займе, мабуть 5 рядків кеша з 256 наявних.
Не дивно, що компілятор з усіх сил намагається инлайнить невеликі функції.

Висновки
Отже, ми розглянули як викликаються функції в одній з вельми витончених мікро-архітектур, яку користь можна з цього отримати?

Виділимо об'єктивні моменти:
  • Кеш інструкцій потрібен, без цього ніякої виразний процесор неможливий.
  • Кеш має гранулярність, на даний момент типовий розмір — рядок 64 байта.
  • Декодування (для x86_64, принаймні)- досить дорога операція, є сенс кешувати декодований код у вигляді рядків мопів
  • Доступ по точці входу — чудова ідея, чи можна при цьому обійтися без розмноження записів — питання реалізації
  • Не більше одного обов'язкового виходу — просте і природне рішення, рятує від купи проблем
Може здатися, що це спрацює і для нашої архітектури з стековим фронтендом. Але є нюанс.
Пояснимо на прикладі. Ось функція Аккермана:
int a(int m, int n)
{
if (m == 0)
return n + 1;
if (n == 0)
return a(m - 1, 1);
return a(m - 1, a(m, n - 1));
}
Виглядає просто, але демонструє чудеса рекурсії. Нижченаведений графік показує динаміку глибини вкладеності для виклику a(3, 5), x — номер кроку, по y — глибина виклику.

Оскільки ми вирішили розглядати виклик функції як узагальнену інструкцію з довільною кількістю параметрів, у випадку m*n != 0, перший аргумент (m-1) залишиться в стеку мопів, в той час як буде обчислюватись другий аргумент: a(m, n-1). Добре, якщо перший аргумент встигне вычислиться і його значення буде збережено при виклику в регистровом стеку. Але може так статися, що вираз для першого аргументу буде обчислюватися довше, ніж аргументи дочірнього виклику у другому аргументі. І тоді у нас зависнуть у чималих кількостях недоработавшие мопи.
Моп батьківського виклику теж буде чекати, поки не відпрацює дочірній виклик. Глибина викликів легко може досягти (десятків) тисяч одиниць, в SandyBrige, приміром, просто немає стільки мопів.

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

Але ми не звикли так легко здаватися, тому в справу вступає план Б.

План Б
Реєстрові суперскалярні процесори не мають подібних проблем т. к. виявлення зв'язків між мопами відбувається пізніше — на етапі перейменування регістрів.
У нас же ці зв'язки зберігаються в стеку індексів мопів.

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

І тут ми стикаємося з тими ж самими проблемами, які зустрічали при спробі зберегти регістри. А саме, при єдиній (для всіх функцій) ідентифікації мопів:
  • порядок використання мопів залежить від передісторії викликів
  • всередині функції він визначається динамічно
  • немає жодних гарантій, що після операції FILL ми не отримаємо конфлікт з вже зайнятим мопом
Спосіб вирішення цих проблем пропонується той самий:
  • кільцевої буфер мопів
  • для кожної функції своя нумерація мопів, наприклад, 0...
  • FILL і SPILL робляться для цілої функції, що дозволяє при необхідності прив'язати стек регістрів і стек мопів до однієї області пам'яті
  • FILL і SPILL робляться тільки для мопів, які очікують завершення, отже, в стек укладається ще й маска (або перерахування) серіалізовать мопів
  • стек індексів мопів ми теж повинні зберегти
На перший погляд необхідність проганяти через пам'ять декодированные мопи видається жахливою. Але коли катехоламины догоряють, стає зрозуміло, що масштаб катастрофи не так вже й великий.
  1. хоча в сучасних процесорах параметри (принаймні їх частина) передаються через регістри, при рекурсивном виклик зберегти параметри і ніде, крім як в стеку, крім того:
    • адреса повернення і frame pointer також зберігаються в стеку
    • volatile регістри зберігаються в стеку викликає стороною
    • non-volatile регістри теж зберігаються в стеку, але вже викликається стороною
  2. вирази типу 'a(m — 1, a(m, n — 1))' компілятор може розвалити, вводячи (явно чи побічно) тимчасову змінну, що дорівнює a(m, n — 1). При цьому зменшується кількість мопів, які треба зберігати.
  3. всі неспрацьовані умовні гілки до моменту безумовного переходу, яким є виклик функції, ми вже викинули
  4. всі мопи за прийдешнім викликом ми також можемо викинути або просто не завантажувати їх, користуючись технікою, аналогічної такої в SandyBridge
  5. а можемо залишити, тоді після повернення з функції, бонусом отримаємо готовий до виконання чи вже навіть частково виконаний (незалежний за даними) код
  6. в самому 'економному' варіанті в стек потрапить тільки один сериализованный моп виклику, а це вже мало відрізняється від передачі адреси frame-fuffer'а, наприклад
  7. (де)серіалізація мопів не виглядає витратною операцією, до того ж, вона може проводитися у фоновому режимі, заздалегідь, не блокуючи поточний повернення з функції
  8. збереження мопів в стеку спільно з завантаженням за припущенням є альтернативою кешу l0m, який тепер просто не потрібен
  9. розмір сериализованного мопа не занадто великий, для SandyBridge початковий розмір мопа оцінюється максимум в 147 біт, в стислому вигляді — 85 біт (а там ще й x87, SSE і AVX всіх мастей)
  10. сам факт, що зовні стають доступні технологічні особливості процесора і можуть бути скомпрометовані які-небудь технічні секрети, автора не лякає. Зрештою, нехай процесор xor іт ці дані з допомогою одноразового блокнота.


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

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

0 коментарів

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