Branch Predictor: gshare & 2-Bit Saturating Counters

Чому існує прогнозування переходів

Пipelined процесори розбивають виконання інструкцій на етапи, такі як отримання (fetch), декодування, виконання та запис назад (writeback), щоб одночасно виконувалися кілька інструкцій на різних етапах. Це перекриття дозволяє чіпу видавати інструкцію майже щоразу циклу, замість того, щоб чекати, поки одна повністю завершиться, перш ніж починати наступну. Проблема полягає в тому, що умовні переходи не розкривають свого результату до відносно пізнього етапу конвеєра, часто на етапі виконання (execute), тоді як етап отримання потребує негайного знання, яка інструкція має бути отримана наступною. Без будь-якого прогнозування конвеєр повинен був би повністю зупинятися в кожному переході до вирішення умови, що на конвеєрі з 15–20 етапами могло б витрачати величезний відсоток загального часу виконання, оскільки переходи відбуваються приблизно кожні п’ять або сім інструкцій у типовому коді. Прогнозування переходів перетворює цю зупинку на ставку: вгадуйте напрямок, продовжуйте отримувати та виконувати інструкції спекулятивно та наражайтеся на штраф лише тоді, коли помиляєтесь. Оскільки більшість переходів дуже схилені, кінцеві точки циклів майже завжди приймаються, а багато умов if послідовно віддають перевагу одному результату, добре спроектований прогнозатор може бути правильним більше ніж на 90% від випадків на реальних робочих навантаженнях, перетворюючи те, що було серйозною вузькою точкою, на незначну.

Двобітна Сатурнуюча Лічильник

Найпростіший корисний прогноз – один біт на кожен випадок розгалуження: прийнято чи відхилено, оновлений відповідно до останнього результату. Але один біт перевертає прогноз після лише однієї аномалії, що шкодить циклам, які приймаються на кожному етапі, крім останнього, оскільки остаточний вихід призводить до помилкового прогнозування, а наступний вхід у цикл також помилково передбачається, оскільки біт змінився. Виправлення, запропоноване в ранніх дослідженнях прогнозів і яке все ще використовується як будівельний блок сьогодні, – двобітна сатурнуюча лічильник – невеликий автомат стану з чотирма станами, зазвичай позначений як «сильно-відхилено», «слабко-відхилено», «слабко-прийнято» та «сильно-прийнято». Кожне правильне прийняття прогнозує переміщує лічильник у бік «сильно-прийнято», а кожне правильне відхилення – у бік «сильно-відхилено», але лічильник насичується на крайніх значеннях, а не обертається. Важливо те, що одна помилкова ситуація лише переміщує лічильник на один крок, наприклад, з «сильно-прийнято» в «слабко-відхилено», замість того, щоб повністю перевернути прогноз. Це означає, що цикл, який приймається 99 разів і відхиляється один раз, буде помилково передбачати лише в тому аномальному ітерації, потім негайно знову починати правильно передбачати прийняття, замість того, як би наївний однобітний механізм передбачив дві помилки поспіль. У симуляції спостерігайте за значенням лічильника, коли цикл виконується, і зверніть увагу, як воно піднімається та опускається, а також як воно потребує двох послідовних неправильних результатів в одному напрямку перед тим, як прогноз фактично змінюється.

Від простих лічильників до gshare

Таблиця з 2-бітовими лічильниками, індексованими виключно за адресою гілки, яка називається бімодальним передбачувачем, добре працює для гілок, поведінка яких приблизно постійна, але не може вловити кореляції між гілками. Багато реальних гілок залежать від контексту: результат умовного оператора може залежати від того, чи була прийнята раніше інша гілка кілька інструкцій раніше. Передбажувач gshare, представлений Скотом Макфарлінгом у 1993 році, вловлює саме цю кореляцію недорого. Він підтримує глобальний реєстр історії, що містить зсувну бітову послідовність, яка записує, чи була прийнята кожна з останніх N гілок будь-де в програмі, і поєднує цю історію з власною адресою програми гілки за допомогою операції XOR для отримання індексу у таблицю лічильників. Оскільки індекс тепер залежить як від ідентифікатора гілки, так і від нещодавнього глобального шаблону результатів гілок, gshare може розрізняти одну й ту саму гілку, яка з'являється в різних поведінкових контекстах, по суті надаючи їй набагато більший, більш спеціалізований набір лічильників без необхідності окремої таблиці для кожної гілки. XOR хешування також допомагає розподілити різні гілки по таблиці, щоб зменшити руйнівне перекриття, коли дві непов'язані гілки потрапляють на одну й ту саму лічильну комірку та пошкоджують прогнози один одного. Цей глобальний підхід до історії був значним кроком вперед порівняно з чисто первинними схемами для кожної гілки і безпосередньо вплинув на турнірні та TAGE передбачувачі, які використовуються в сучасних високопродуктивних процесорах.

Вартість Неправильного Прогнозування

Неправильне прогнозування не є безкоштовним, і його вартість прямо пропорційна глибині та ширині конвеєра. Коли гілка нарешті вирішується на етапі виконання та не збігається з попереднім прогнозом, кожне отримане та частково виконане інструкцію вздовж неправильного шляху необхідно «здути», їхній вплив відкидається перед тим, як вони можуть модифікувати архітектурний стан, і передній кінець повинен перезапустити отримання з правильної адреси цілі. Затримка до моменту, коли корисні інструкції починають протікати через конвеєр знову, називається штрафом за неправильне прогнозування, і на сучасних багатоядерних ядрах вона часто становить від 10 до 20 циклів, іноді більше для дуже глибоких конвеєрів. Якщо гілка помилково прогнозується навіть 5% часу та з’являється кожні шість інструкцій, середній наклад витрат циклів на інструкцію від неправильного прогнозування може конкурувати з вартістю затримок пам'яті. Саме тому дизайнери мікросхем інвестують величезні бюджети транзисторів, часто більше площі кремнія, ніж арифметичні блоки, в все більш складних прогнозників: на основі перцептронів, TAGE з кількома довжинами історії та прогнозники циклів, які безпосередньо виявляють фіксовану кількість ітерацій. Симуляція візуалізує цю штрафну затримку явно, показуючи, як етапи конвеєра спорожнічуються та поповнюються після неправильного припущення, щоб абстрактний цикл став видимою затримкою, яку можна спостерігати.

Чому програмне забезпечення відчуває різницю

Прогнозування переходів невидиме в сенсі того, що ніколи не змінює правильність програми, лише її швидкість. Однак цей вплив на швидкість достатньо великий, щоб формувати те, як пишуть код, орієнтований на продуктивність. Сортування вже відсортованого масиву значно швидше, ніж сортування випадкового, частково тому, що порівняльні переходи стають дуже передбачуваними після упорядкування даних. Заміна непередбачуваного переходу на код без переходів, використовуючи бітову арифметику або інструкції умовного переміщення для обчислення обох результатів і вибору між ними, може бути справжньою оптимізаційною технікою саме тому, що вона повністю усуває джерело очищення черги. Компілятори також використовують оптимізацію на основі профілів, щоб розташувати код таким чином, щоб загальний шлях переходу проходив безпосередньо в пам'яті, що добре поєднується з прогнозуванням, спрощуючи шаблон отримання даних. Інтерпретатори та віртуальні машини особливо сильно страждають від помилок прогнозування переходів у своїх циклах розгортання, оскільки центральна операція перемикання великого, важко передбачуваного непрямого переходу в операторі `switch` у байт-код інтерпретатора – одна з причин існування таких технік, як компіляція під час виконання (JIT) та багатопотокове розгортання. Навіть двигуни запитів баз даних і відеокодеки налаштовуються з урахуванням передбачуваності переходів. Як ця симуляція показує, коли ви можете побачити, що помилка прогнозування відкидає реальну виконану роботу та зупиняє всю чергу на десятки циклів і більше, постійна порада писати передбачувані переходи перестає бути міфом і стає прямим, механічним наслідком того, як фактично виконується ваш код.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Branch Predictor: gshare & 2-Bit Saturating Counters і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.