2. Зниження втрат на виконання команд умовного переходу

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

Метод вичікування

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

Метод повернення

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

Невиконуємий умовний перехід	IF	ID	EX MEMWB
Команда i+1		IF	IDEXMEMWB
Команда i+2			IFIDEXMEMWB
Команда i+3			IFIDEXMEMWB
Команда i+4			IFIDEXMEMWB
Виконуємий умовний перехід	IF	ID	EX MEMWB
Команда i+1		IF	IDEXMEMWB
Команда i+2			stallIFIDEXMEMWB
Команда i+3			stallIFIDEXMEMWB
Команда i+4			stallIFIDEXMEM

Рис. 2. Діаграма роботи модернізованого конвеєра

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