2. Подальше зменшення зупинок по керуванню: буфера цільових адрес переходів
Розглянемо ситуацію, при якій на стадії вибірки команд перебуває команда переходу (на наступній стадії буде здійснюватися її дешифрація). Тоді щоб скоротити втрати, необхідно знати, по якій адресі вибирати наступну команду. Це означає, що нам якось треба з'ясувати, що ще недешифрована команда справді є командою переходу, і чому дорівнює наступне значення лічильника адрес команд. Якщо все це ми будемо знати, то втрати на команду переходу можуть бути зведені до нуля. Спеціальний апаратний кеш прогнозування переходів, що зберігає прогнозована адреса наступної команди, називається буфером цільових адрес переходів (branch-target buffer).
Кожний рядок цього буфера включає програмну адресу команди переходу, прогнозовану адреса наступної команди й передісторію команди переходу (рис. 4). Біти передісторії являють собою інформацію про виконання або невиконання умов переходу даної команди в минулому. Звертання до буфера цільових адрес переходу (порівняння з полями програмних адрес команд переходу) виробляється за допомогою поточного значення лічильника команд на етапі вибірки чергової команди. Якщо виявлено збіг (влучення в термінах кеш-пам'яті), то по передісторії команди прогнозується виконання або невиконання умов команди переходу, і негайно виробляється вибірка й дешифрація команд із прогнозованої гАЛПзі програми. Вважається, що передісторія переходу, яка містить інформацію про два попередні випадки виконання цієї команди, дозволяє прогнозувати розвиток подій із цілком достатньою ймовірністю.
Рис. 4. Буфер цільових адрес переходів
Існують і деякі варіації цього методу. Основний їхній зміст полягає в тому, щоб зберігати в процесорі одну або кілька команд із прогнозованої гАЛПзі переходу. Цей метод може застосовуватися як у сукупності з буфером цільових адрес переходу, так і без нього, і має дві переваги. По-перше, він дозволяє виконувати звертання до буфера цільових адрес переходу протягом більш тривалого часу, а не тільки протягом часу послідовної вибірки команд. Це дозволяє реалізувати буфер більшого обсягу. По-друге, буферизація самих цільових команд дозволяє використовувати додатковий метод оптимізації, який називається згортанням переходів (branch folding). Згортання переходів може використовуватися для реалізації нульового часу виконання самих команд безумовного переходу, а в деяких випадках і нульовому часі виконання умовних переходів. Розглянемо буфер цільових адрес переходу, що буферизує команди із прогнозованої гАЛПзі. Нехай до нього виконується обіг за адресою команди безумовного переходу. Єдиним завданням цієї команди безумовного переходу є заміна поточного значення лічильника команд. У цьому випадку, коли буфер адрес реєструє попадання й показує, що перехід безумовний, конвеєр просто може замінити команду, що вибирається з кеш-пам'яті (це і є сама команда безумовного переходу), на команду з буфера. У деяких випадках у такий спосіб вдається забрати втрати для команд умовного переходу, якщо код умови встановлений заздалегідь.
Ще одним методом зменшення втрат на переходи є метод прогнозування непрямих переходів, а саме переходів, адреса призначення яких змінюється в процесі виконання програми (в run-time). Компілятори мов високого рівня будуть генерувати такі переходи для реалізації непрямого виклику процедур, операторів select або case і операторів, що обчислюють, goto у Фортрані. Однак переважна більшість непрямих переходів виникає в процесі виконання програми при організації повернення із процедур. Наприклад, для тестових пакетів SPEC повернення із процедур у середньому становлять 85% загального числа непрямих переходів.
Хоча повернення із процедур можуть прогнозуватися за допомогою буфера цільових адрес переходів, точність такого методу прогнозування може виявитися низкою, якщо процедура викликається з декількох місць програми або виклики процедури з одного місця програми не локалізуються за часом. Щоб перебороти цю проблему, була запропонована концепція невеликого буфера адрес повернення, що працює як стек. Ця структура кешує останні адреси повернення: під час виклику процедури адреса повернення вштовхується в стек, а під час повернення він відтіля витягає. Якщо цей кеш досить великий (наприклад, настільки великий, щоб забезпечити максимальну глибину вкладеності викликів), він буде прекрасно прогнозувати повернення. На рис 5.показане виконання такого буфера повернень, що містить від 1 до 16 рядків (елементів) для декількох тестів SPEC.
Рис. 5. Точність прогнозу для адрес повернення
Точність прогнозу в цьому випадку є частина адрес повернення, передвіщених правильно. Оскільки глибина викликів процедур зазвичай невелика, за деякими виключеннями навіть невеликий буфер працює досить добре. В середньому повернення становлять 81% загального числа непрямих переходів для цих шести тестів.
Схеми прогнозування умовних переходів обмежені як точністю прогнозу, так і втратами у випадку неправильного прогнозу. Як ми бачили, типові схеми прогнозування досягають точності прогнозу в діапазоні від 80 до 95% залежно від типу програми й розміру буфера. Крім збільшення точності схеми прогнозування, можна намагатися зменшити втрати при невірному прогнозі. Звичайно це робиться шляхом вибірки команд по обох гАЛПзях (по передвіщеному й по непередвіщеному напрямку). Це вимагає, щоб система пам'яті була двопортовою, включала кеш-пам'ять із розшаруванням, або здійснювала вибірку по одному з напрямків, а потому по іншому (як це робиться в IBM POWER-2). Хоча подібна організація збільшує вартість системи, можливо це єдиний спосіб зниження втрат на умовні переходи нижче певного рівня. Інше альтернативне рішення, що використовується в деяких машинах, полягає в кешуванні адрес або команд із декількох напрямків (галузей) у цільовому буфері.