Конвеєрна та суперскалярна обробка
Нижче представлена сторінка, лише частина величезного сайту присвяченого різної комп'ютерної документації, на сайті зібрано більше 800 мб інформації. Якщо Ви не знайшли в цій статті, то, що Ви шукаєте, спробуєте подивитися тут, запитати на форумі або пошукати необхідну Вам інформацію в нашому каталозі посилань сайтів комп'ютерної тематики.
Якщо ж Ви хочете придбати паперову копію представлених тут матеріалів, звертайтесь до нашої книгарні.
З повагою, команда розробників eManual.ru
| Сучасні високопродуктивні комп'ютери - Конвеєрна та суперскалярна обробка |
Конвеєрна та суперскалярна обробка
Паралелізм на рівні виконання команд, планування завантаження конвеєра та методика розгортання циклів
У попередньому розділі ми розглянули засоби конвеєризації, які забезпечують суміщений режим виконання команд, коли вони є незалежними одна від одної. Це потенційне поєднання виконання команд називається паралелізмом лише на рівні команд. У цьому розділі ми розглянемо низку методів розвитку ідей конвеєризації, заснованих на збільшенні ступеня паралелізму, що використовується під час виконання команд. Ми почнемо з розгляду методів, що дозволяють знизити вплив конфліктів за даними та управління, а потім повернемося до теми розширення можливостей процесора з використання паралелізму, закладеного в програмах. Потім ми обговоримо сучасні технології компіляторів, які використовуються для збільшення рівня паралелізму рівня команд.
Для початку запишемо вираз, що визначає середню кількість тактів для виконання команди в конвеєрі:
CPI конвеєра = CPI ідеального конвеєра +
+ Призупинення через структурні конфлікти +
+ Призупинення черезконфліктів типу RAW+
+ Призупинення через конфлікти типу WAR +
+ Призупинення через конфлікти типу WAW +
+ Призупинення через конфлікти з управління
CPI ідеального конвеєра є нічим іншим, як максимальна пропускна спроможність, досяжна під час реалізації. Зменшуючи кожне з доданків у правій частині виразу, ми мінімізуємо загальний CPI конвеєра і таким чином збільшуємо пропускну здатність команд. Цей вираз дозволяє також охарактеризувати різні методи, які будуть розглянуті в цьому розділі, за тим компонентом загального CPI, який зменшує відповідний метод. На рис. 6.1 показано деякі методи, які будуть розглянуті, та їх вплив на величину CPI.
Перш ніж розпочати розгляд цих методів, необхідно визначити концепції, на яких ці методи побудовані.
Паралелізм рівня команд: залежності та конфлікти за даними
Усі методи, що розглядаються в цьому розділі, використовують паралелізм, закладений у послідовності команд. Як ми встановили вище, цей тип паралелізму називається паралелізмом рівня команд або ILP. Ступінь паралелізму, доступна всередині базового блоку (лінійної послідовності команд, переходи з-за якої дозволені тільки на її вхід, а переходи всередині якої дозволені тільки на її вихід) досить мала. Наприклад, середня частота переходів у цілих програмах становить близько 16%. Це означає, що в середньому між двома переходами виконується приблизно п'ять команд. Оскільки ці п'ять команд можливо взаємозалежні, то ступінь перекриття, який ми можемо використовувати всередині базового блоку, може бути меншим ніж п'ять. Щоб отримати суттєве покращення продуктивності, ми повинні використовувати паралелізм рівня команд одночасно длякількох базових блоків.
| Метод | Знижує |
| Розгортання циклів | Призупинення управління |
| Базове планування конвеєра | Призупинення RAW |
| Динамічне планування з централізованою схемою управління | Призупинення RAW |
| Динамічне планування з перейменуванням регістрів | Призупинення WAR та WAW |
| Динамічне прогнозування переходів | Призупинення управління |
| Видача кількох команд в одному такті | Ідеальний CPI |
| Аналіз залежностей компілятором | Ідеальний CPI та призупинення за даними |
| Програмна конвеєризація та планування трас | Ідеальний CPI та призупинення за даними |
| Виконання за припущенням | Усі призупинення за даними та управління |
| Динамічне усунення неоднозначності пам'яті | Призупинення RAW, пов'язане з пам'яттю |
Найпростіший і загальний спосіб збільшення рівня паралелізму, доступного лише на рівні команд, є використання паралелізму між ітераціями циклу. Цей тип паралелізму часто називається паралелізмом рівня ітеративного циклу. Нижче наведено простий приклад циклу, що виконує додавання двох 1000-елементних векторів, який є повністю паралельним:
for (i = 1; i n - 1. Тоді схема прогнозу буде наступною:
- Якщо значення лічильника більше або дорівнює 2 n-1 (точка на середині інтервалу), перехід прогнозується як виконуваний. Якщо напрям переходу передбачено правильно, до значення лічильника додається одиниця (якщо воно не досягло максимальної величини); якщо прогноз був неправильним, значення лічильника віднімається одиниця.
- Якщо значення лічильника менше, ніж 2 n-1 то перехід прогнозується як невиконуваний. Якщо напрям переходу передбачено правильно, значення лічильника віднімається одиниця (якщо не досягнуто значення 0); якщо прогноз був невірним, значення лічильника додається одиниця.
Дослідження n-бітових схем прогнозування показали, що двобітова схема працює майже також добре, і тому в більшості систем застосовуються двобітові схеми прогнозу, а не n-бітові.
Як згадувалося, точність двобітової схеми прогнозування залежить від цього, наскільки часто прогноз кожного переходу є правильним і як часто рядок у буфері прогнозування відповідає команді переходу. Якщо рядок не відповідає даній команді переходу, прогноз у будь-якому випадку робиться, оскільки жодна інша інформація не доступна. Навіть якщо цей рядок відповідає зовсім іншій команді переходу, прогноз може бути вдалим.
Яку точність можна очікувати від буфера прогнозування переходів на реальних додатках при використанні 2 біти на кожен рядок буфера? Для набору оціночних тестів SPEC-89 буфер прогнозування переходів із 4096 рядками дає точність прогнозу від 99% до 82%, тобто. відсоток невдалих прогнозів становить від 1% до 18% (див. рис. 6.9). Слід зазначити, що буфер ємністю 4К рядків вважається дуже великим. Буфери меншого обсягу дадуть найгірші результати.
Однак одного знання точності прогнозу недостатньо для того, щоб визначити вплив переходів на продуктивність машини, навіть якщо відомий час виконання переходу та втрати при невдалому прогнозі. Необхідно враховувати частоту переходів у програмі, оскільки важливість правильного прогнозу більша у програмах з більшою частотою переходів.Наприклад, цілі програми li, eqntott, expresso і gcc мають більшу частоту переходів, ніж значно простіші для прогнозування програми плаваючої точки nasa7, matrix300 і tomcatv.
Оскільки головним завданням є використання максимально доступного рівня паралелізму програми, точність прогнозу напряму переходів стає дуже важливою. Як видно із рис. 6.9, точність схеми прогнозування для цілих програм, які зазвичай мають більш високу частоту переходів, менше, ніж для наукових програм з плаваючою точкою, в яких інтенсивно використовуються цикли. Можна вирішувати цю проблему двома способами: збільшенням розміру буфера та збільшенням точності схеми, яка використовується для виконання кожного окремого прогнозу. Буфер із 4К рядками вже досить великий і, як свідчить рис. 6.9 працює практично також, що і буфер нескінченного розміру. З цього малюнка стає зрозуміло, що коефіцієнт попадань буфера перестав бути лімітуючим чинником. Як згадувалося, збільшення числа біт у схемі прогнозу також має малий ефект.
Мал. 6.9. Порівняння якості 2-бітового прогнозу
Розглянуті двобітові схеми прогнозування використовують інформацію про недавню поведінку команди умовного переходу для прогнозу майбутньої поведінки цієї команди. Ймовірно, можна покращити точність прогнозу, якщо враховувати не лише поведінку того переходу, який ми намагаємося передбачити, але розглядати також і недавню поведінку інших команд переходу. Розглянемо, наприклад, невеликий фрагмент із тексту програми eqntott тестового пакета SPEC92 (це найгірший випадок для двобітової схеми прогнозу):
Нижче наведено текст згенерованої програми (передбачається, що aa та bb розміщені в регістрах R1 та R2):
BNEZ R3, L1; перехід b1 (aa! = 2)
ADD R1, R0, R0; aa=0
BNEZ R3, L2; перехід b2 (bb! = 2)
ADD R2, R0, R0; bb=0
L2: SUB R3, R1, R2; R3=aa-bb
BEQZ R3, L3; branch b3 (aa==bb).
Позначимо команди переходу як b1, b2 та b3. Можна помітити, що поведінка переходу b3 корелює переходи b1 і b2. Зрозуміло, що й обидва переходу b1 і b2 є невыполняемыми (тобто. обидві умови if оцінюються як істинні і обом змінним aa і bb присвоєно значення 0), то перехід b3 буде виконуваним, оскільки aa і bb очевидно рівні. Схема прогнозування, яка для передбачення напрямку переходу використовує тільки минулу поведінку того самого переходу ніколи цього не врахує.
Мал. 6.10. Буфер прогнозування переходів (2,2)
Наприклад, двобітова схема прогнозування без світової історії є просто схема (0,2). Скільки бітів потрібно для реалізації схеми прогнозування (0,2), яку ми розглядали раніше? Скільки біт використовується у схемі прогнозування, показаної на рис. 6.10?
Схема на рис. 6.10. має 2 2 (2 (16 = 128 біт.)
Щоб порівняти продуктивність схеми корелюваного прогнозування з простою двобітовою схемою прогнозування, продуктивність якої була представлена на рис. 6.8, потрібно визначити кількість рядків у схемі корелюваного прогнозування.
Таким чином, ми повинні визначити кількість рядків, що вибираються командою переходу у схемі прогнозування (2,2), яка містить 8К біт у буфері прогнозування.
2 2 ( 2 ( кількість рядків, що вибираються
командою переходу = 8К
Кількість рядків, що вибираються командою
На рис. 6.9 представлені результати для порівняння простої двобітової схеми прогнозування з 4К рядками та схеми прогнозування(2,2) з 1К рядками. Як можна бачити, ця остання схема прогнозування не тільки перевершує просту двобітову схему прогнозування з тією ж кількістю біт стану, але часто перевершує навіть двобітову схему прогнозування з необмеженим (нескінченним) кількістю рядків. Є широкий спектр кореляційних схем прогнозування, серед яких схеми (0,2) та (2,2) є найцікавішими.