Loop:LDF0,0(R1)
ADDF4,F0,F2
SD0(R1),F4
SUBR1,R1,#8
BNEZR1,Loop
Для спрощення вважаємо, що масив починається з адреси 0. Якщо б він знаходився у іншому місці, цикл вимагав би наявності ще однієї додаткової цілочисельної команди для виконання порівняння з R1.
Розглянемо роботу цього циклу при виконанні на простому конвеєрі із вищевказаними затримками. Якщо не робити ніякого планування, робота циклу буде виглядати наступним чином:
Такт видачі
Loop:LDF0,0(R1)1
Зупинка2
ADDF4,F0,F23
Зупинка4
Зупинка5
SD0(R1),F46
SUBR1,R1,#87
BNEZR1,Loop8
Зупинка9
Для виконання потрібно 9 тактів на ітерацію: одна зупинка для команди LD, дві для команди ADD, та одна для затриманого переходу. Але можна спланувати цикл таким чином:
Такт видачі
Loop:LDF0,0(R1)1
Зупинка2
ADDF4,F0,F23
SUBR1,R1,#84
BNEZR1,Loop5Затриманий перехід
SD0(R1),F46
Час виконання зменшився з 9 до 6 тактів. Зауважимо, що для планування затриманого переходу компілятор повинен з‘ясувати, що він може поміняти місцями команди SUB та SD шляхом зміни адреси в команді запису SD: адреса була 0(R1), а тепер 8(R1). Це не тривіальна задача, оскільки більшість компіляторів будуть бачити що команда SD залежить від команди SUB, і відмовляться від їх перестановок. Ланцюжок залежностей від команд LD до команди ADD та далі до команди SD визначає кількість тактів, необхідних для даного циклу.
У наведеному прикладі ми завершуємо одну ітерацію циклу та виконуємо запис одного елемента вектора кожні 6 тактів, але дійсна робота по обробці елемента вектора займає 3 такти (завантаження, додавання, запис). Решта 3 такти складають накладні витрати для організації циклу. Для того щоб зменшити накладні витрати потрібно збільшити кількість операцій в кожному циклі. Для цього служить метод розгортання циклів. Він не зменшує абсолютну кількість тактів на накладні витрати, але робить витрати відносно меншими. Таке розгортання здійснюється шляхом чисельної реплікації (повторення) тіла циклу.
Розгортання циклу може також використовуватись для покращання планування. У цьому випадку ми можемо збільшити паралелізм шляхом створення багатьох незалежних команд в тілі циклу. Потім компілятор може використовувати ці команди для розміщення в слот затримки. Якщо при розгортанні просто дублювати тіло циклу, результуючі залежності по іменах можуть завадити ефективно спланувати цикл. Таким чином для різних ітерацій потрібно використовувати різні регістри, що збільшує потрібну кількість регістрів.
Розгорнемо цикл на 4 ітерації:
Loop:LDFO,0(R1)
ADDF4,F0,F2
SD0(R1),F4
LDF6,-8(R1)
ADDF8,F6,F2
SD-8(R1),F8
LDF10,-16(R1)
ADDF12,F10,F2
SD-16(R1),F14
LDF14,-24(R1)
ADDF16,F14,F2
SD-24(R1),F16
SUBR1,R1,#32
BNEZR1,Loop
Ми ліквідували 3 умовних переходи та 3 операції декременту R1. Адреси команд завантаження та запису були скоректовані таким чином, що з‘явилась можливість користуватись R1 для всіх звернень до пам‘яті. При відсутності планування за кожною командою буде йти залежна команда, що приведе до затримок. Цей цикл буде виконуватись за 27 тактів, або по 6.8 тактів на кожний елемент масиву.
В реальних програмах верхня межа циклу невідома. Припустимо, що вона рівна n і ми хотіли б розгорнути цикл таким чином щоб мати k копій тіла циклу. Замість одного розгорнутого циклу ми генеруємо 2: один виконується n mod k раз, другий – n div k, причому він охоплює перший цикл.
У цьому прикладі розгортання циклу збільшує швидкодію за рахунок усунення команд, пов‘язаних з накладними витратами циклу, хоча це суттєво збільшує розмір коду. Як покращиться швидкодія, якщо цикл буде оптимізований?
Нижче представлений розгорнутий цикл з попереднього прикладу після оптимізації:
Loop:LDF0,0(R1)
LDF6,-8(R1)
LDF10,-16(R1)
LDF14,-24(R1)
ADDF4,F0,F2
ADDF8,F6,F2
ADDF12,F10,F2
ADDF16,F14,F2
SD0(R1),F4
SD-8(R1),F8
SD-16(R1),F12
SUBR1,R1,#32
BNEZLoop
SD8(R1),F16
Час виконання зменшився до 14 тактів, або до 3.5 тактів на елемент масиву.
Виграш від оптимізації розгорнутого циклу навіть більший ніж від оптимізації нерозгорнутого тому що розгортання циклу виявило більшу кількість команд котрі не залежать одна від іншої.
Розгортання циклу представляє собою простий але дуже корисний метод підвищення розміру лінійного кодового сегменту, який може ефективно оптимізуватися.
Найпростішою схемою динамічного прогнозування напрямку умовних переходів є буфер прогнозування умовних переходів (branch prediction buffer) або таблиця "історії" переходів. Буфер прогнозування умовних переходів представляє собою невелику пам‘ять, що адресується молодшими розрядами адреси команди умовного переходу. Кожна комірка цієї пам‘яті містить 1 біт, який містить інформацію про те, був попередній перехід виконаний чи ні. Це найпростіший тип такого буфера, в ньому відсутні теги, і він корисний тільки для скорочення затримки переходу у тому випадку, коли ця затримка більша, ніж час потрібний для обчислення цільового значення умовного переходу. Ми не знаємо, чи є цей прогноз коректним (значення у відповідну комірку буфера могла занести зовсім інша команда). Але це не має значення. Прогноз – це тільки передбачення, яке розглядається як коректне, і вибірка команд починається із спрогнозованої адреси. Якщо прогноз виявився невірним, відповідний біт інвертується.
Але проста однобітова схема має недостатню ефективність. Розглянемо, наприклад, команду умовного переходу в циклі яка 9 разів виконувалась, а на 10 раз не виконалась. Напрямок переходу буде невірно спрогнозовано на 1 та на останній ітерації. Невірний прогноз останньої ітерації неминучий, оскільки перехід виконувався 9 разів підряд. Таким чином точність прогнозу була 80% (8 правильних та 2 неправильних прогнози).
Для виправлення цього стану часто використовується схема двобітового прогнозу. У двобітовій схемі прогноз має 2 рази бути неправильний, щоб напрямок прогнозування змінився на протилежний. Двобітова схема є частковим випадком більш загальної схеми, яка в кожній строчці буфера прогнозування має n-бітовий регістр. Цей регістр може приймати значення від 0 до 2n-1. Тоді схема прогнозування буде такою:
- якщо значення регістра буде більше або рівне 2n-1 то напрямок прогнозується як виконуваний. Якщо напрямок було передбачено вірно, до значення додається 1 (якщо значення не досягло максимального значення), інакше віднімається 1.
- якщо значення регістра буде меншим ніж 2n-1 то напрямок прогнозується як невиконуваний. Якщо напрямок було передбачено вірно, від значення віднімається 1 (якщо значення не досягло 0), інакше додається 1.
Дослідження n-бітових схем прогнозування показали, що вони працюють не набагато краще ніж 2-бітові.
Буфер прогнозування може бути реалізований як невелика кеш-пам‘ять, доступ до якої відбувається за допомогою адреси команди під час стадії IF. Якщо команду декодовано як команду переходу, і якщо перехід спрогнозовано як виконуваний, вибір команд починається з цільової адреси як тільки ця адреса стане відомою.
Точність прогнозу залежить від того, наскільки часто прогноз є виконуваним або невиконуваним. Якщо строка в буфері ідентифікована невірно (прогноз зовсім іншої команди переходу), прогнозування все рівно виконується, оскільки така ситуація не може бути розпізнана процесором на ранніх стадіях обробки команди, але навіть у цьому випадку прогноз може бути вірним.
Як показують практичні тести, 2-бітовий буфер розміром 4096 комірок дає точність прогнозування від 99% до 82% в залежності від типу програмного забезпечення.
Але одного знання про точність прогнозування недостатньо для того, щоб з‘ясувати вплив переходів на швидкодію машини, навіть якщо відомі час виконання переходу та втрати часу при невдалому прогнозі. Необхідно враховувати частоту переходів в програмі, оскільки важливість точного прогнозу більша в програмах з великим числом переходів. Наприклад, цілочисельні програми li, eqntott, expresso та gcc мають більшу частоту переходів, ніж значно простіші для прогнозування програми розрахунку nasa7, matrix300 та tomcatv. Оскільки головною метою є використання якомога більшого паралелізму програми, точність прогнозу напрямку переходів стає дуже важливою.
Схеми з 2-бітовою структурою розглядають попередні результати переходів для прогнозування наступних. Можливо, вдасться підвищити точність прогнозу, якщо розглядати не тільки одну команду переходу, як і інші пов‘язані з нею. Розглянемо, наприклад фрагмент програми:
If(aa == 2)
aa = 0;
if(bb == 2)
bb = 0;
if(aa != bb) { ………
Нижче наведений лістінг команд згенерованих компілятором з цього фрагменту (aa знаходиться в R1, bb знаходиться в R2):
SUBR3,R1,#2
BNEZR3,L1
SUBR1,R0,R0
L1:SUBR3,R2,#2
BNEZR3,L2
SUBR2,R0,R0
L2:SUBR3,R1,R2
BEQZR3,L3
Позначимо команди переходу як п1, п2, п3. Можна помітити, що команда переходу п3 корелює з командами п1 та п2. Якщо обидва переходи п1 та п2 будуть виконуваними, то перехід п3 буде виконуваним, оскільки значення змінних рівні. Розглянута схема прогнозування, яка розглядає тільки історію поведінки тільки одного переходу, ніколи це не врахує.
Схеми прогнозування, які для передбачення переходу використовують поведінку інших команд переходу, називаються корельованими або дворівневими схемами прогнозування. Схема прогнозування називається прогнозом (1,1) якщо вона використовує поведінку одного останнього переходу для вибору з пари однобітових схем прогнозування на кожний перехід. В загальному випадку схема прогнозування (m,n) використовує поведінку останніх m переходів для вибору з 2m схем прогнозування, кожна з якої представляє собою n-бітову схему прогнозування для кожного окремого переходу. Перевага такого типу корельованих схем полягає в тому, що вони можуть давати більший відсоток правильних прогнозів, ніж проста схема та потребують невеликого ускладнення апаратних засобів. Простота апаратних засобів пояснюється тим, що історія останніх m переходів може бути записана в регістр зсуву розрядності m, у кожний розряд якого заноситься інформація, був цей перехід виконаний чи ні. Тоді буфер прогнозування переходів може адресуватись конкатенацією регістру зсуву та молодших бітів адреси команди переходу. На малюнку зображена схема прогнозування (2,2):