2. Динамічна оптимізація із централізованою схемою виявлення конфліктів

У конвеєрі з динамічним плануванням виконання команд всі команди проходять через щабель видачі строго в порядку, запропонованому програмою (упорядкована видача). Однак вони можуть припинятися і обходити один одного на другому щаблі (щаблі читання операндів) і тим самим надходити на щаблі виконання неупорядковано. Централізована схема виявлення конфліктів являє собою метод, що допускає неупорядковане виконання команд при наявності достатніх ресурсів і відсутності залежностей за даними. Уперше подібна схема була застосована в комп'ютері CDC 6600.

Перш ніж почати обговорення можливості застосування подібних схем, важливо помітити, що конфлікти типу WAR, відсутні в простих конвеєрах, можуть з'явитися при неупорядкованому виконанні команд. У раніше наведеному прикладі регістром результату для команди SUBD є регістр R8, що одночасно є джерелом операнда для команди ADDD. Тому тут між командами ADDD і SUBD має місце антизалежність: якщо конвеєр виконає команду SUBD раніше команди ADDD, він порушить цю антизалежність. Цей конфлікт WAR можна обійти, якщо виконати два правила: (1) читати регістри тільки під час стадії читання операндів і (2) поставити в чергу операцію ADDD разом з копією її операндів. Щоб уникнути порушень залежностей по виходу конфлікти типу WAW (наприклад, це могло відбутися, якби регістром результату команди SUBD був б регістр F10) усе ще повинні виявлятися. Конфлікти типу WAW можуть бути усунуті за допомогою припинення видачі команди, регістр результату якої збігається із уже використовуваним у конвеєрі.

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

Машина CDC 6600 мала 16 окремих функціональних пристроїв (4 пристрою для операцій із плаваючою крапкою, 5 пристроїв для організації звертань до основної пам'яті й 7 пристроїв для цілочисельних операцій). У нашому випадку централізована схема виявлення конфліктів має сенс тільки для пристрою плаваючої крапки. Припустимо, що є два множителя, один суматор, один пристрій ділення і один цілочисельний пристрій для всіх операцій звертання до пам'яті, переходів і цілочисельних операцій. Хоча пристроїв у цьому прикладі набагато менше, ніж в CDC 6600, він досить потужний для демонстрації основних принципів роботи. Оскільки як наша машина, так і CDC 6600 є машинами з операціями регістр-регістр (операціями завантаження/запису), в обох машинах методика практично однакова. На рис.1 показана подібна машина.

Рис. 1. Централізована схема керування

Кожна команда проходить через централізовану схему виявлення конфліктів, що визначає залежності за даними; цей крок відповідає стадії видачі команд і заміняє частина стадії ID у нашому конвеєрі. Ці залежності визначають потім моменти часу, коли команда може читати свої операнди та починати виконання операції. Якщо централізована схема вирішує, що команда не може негайно виконуватися, вона стежить за всіма змінами в апаратурах і вирішує, коли команда зможе виконуватися. Ця ж централізована схема визначає також коли команда може записати результат у свій регістр результату. Таким чином, всі схеми виявлення і розв’язання конфліктів тут виконуються пристроєм центрального керування.

Кожна команда проходить чотири стадії свого виконання. (Оскільки в цей момент ми цікавимося операціями плаваючої крапки, ми не розглядаємо стадію звертання до пам'яті). Розглянемо ці стадії спочатку неформально, а потім детально розглянемо як централізована схема підтримує необхідну інформацію, що визначає обробку при переході з однієї стадії на іншу. Наступні чотири стадії заміняють стадії ID, EX і WB у стандартному конвеєрі:

1. Видача. Якщо функціональний пристрій, необхідне для виконання команди, вільно й ніяка інша команда, що виконується, не використовуэ той же самий регістр результату, централізована схема видає команду у функціональний пристрій і обновляє свою внутрішню структуру даних. Оскільки ніякий інший працюючий функціональний пристрій не може записати результат у регістр результату нашої команди, ми гарантуємо, що конфлікти типу WAW не можуть з'являтися. Якщо існує структурний конфлікт або конфлікт типу WAW, видача команди блокується й ніякі наступні команди не будуть видаватися на виконання доти, поки ці конфлікти існують. Ця стадія заміняє частину стадії ID у нашому конвеєрі.

2. Читання операндів. Централізована схема стежить за можливістю вибірки джерел операндів для відповідної команди. Операнд-источник доступний, якщо відсутня виконуюча команда, що записує результат у цей регістр або якщо в цей момент часу в регістр, що містить операнд, виконується запис із працюючого функціонального пристрою. Якщо операнди-джерела доступні, централізована схема повідомляє функціональному пристрою про необхідність читання операндів з регістрів і початку виконання операції. Централізована схема дозволяє конфлікти RAW на цій стадії динамічно й команди можуть посилати для виконання не в порядку, запропонованому програмою. Ця стадія, спільно зі стадією видачі, завершує роботу стадії ID простого конвеєра.

3. Виконання. Функціональний пристрій починає виконання операції після одержання операндів. Коли результат готовий він повідомляє централізовану схему керування про те, що він завершив виконання операції. Ця стадія заміняє стадію EX і займає кілька тактів у розглянутому раніше конвеєрі.

4. Запис результату. Коли централізована схема керування дізнається про те, що функціональний пристрій завершив виконання операції, вона перевіряє існування конфлікту типу WAR. Конфлікт типу WAR існує, якщо є послідовність команд, аналогічно представленій в нашому прикладі з командами ADDF і SUBF. У тім прикладі ми мали наступну послідовність команд:

DIVF F0,F2,F4

ADDF F10,F0,F8

SUBF F8,F8,F14

Команда ADDF має операнд-джерело F8, що є тим же самим регістром, що й регістр результату команди SUBF. Але в дійсності команда ADDF залежить від попередньої команди. Централізована схема керування буде блокувати видачу команди SUBF доти, поки команда ADDF не прочитає свої операнди. Тоді в загальному випадку команді, що завершується, не дозволяється записувати свої результати якщо:

• є команда, що не прочитала свої операнди,

• один з операндів є регістром результату команди, що завершується.

Якщо цей конфлікт типу WAR не існує, централізована схема керування повідомляє функціональному пристрою про необхідність запису результату в регістр призначення. Ця стадія заміняє стадію WB у простому конвеєрі.

Ґрунтуючись на своїй власній структурі даних, централізована схема керування управляє просуванням команди з одного щабля на іншу взаємодіючи з функціональними пристроями. Але є невелике ускладнення: у регістровому файлі є тільки обмежене число магістралей для операндів-джерел і магістралей для запису результату. Централізована схема керування повинна гарантувати, що кількість функціональних пристроїв, яким дозволено продовжувати роботу на щаблях 2 і 4 не перевищує числа доступних шин. Ми не будемо вдаватися в подальші подробиці й згадаємо лише, що CDC 6600 вирішувала цю проблему шляхом об'єднання 16 функціональних пристроїв один з одним у чотири групи й підтримки для кожної групи пристроїв набору шин, називаних магістралями даних (data trunks). Тільки один пристрій у групі міг читати операнди або записувати свій результат протягом одного такту.

Загальна структура регістрів стану пристрою централізованого керування показана на рис.2. Вона складається з 3-х частин:

1. Стан команди - показує кожний із чотирьох етапів виконання команди.

2. Стан функціональних пристроїв - є 9 полів, що описують стан кожного функціонального пристрою:

Зайнятість - показує, зайняті пристрій або вільний Op - виконувана в пристрої операція F_i - регістр результату F_j, F_k - регістри-джерела операндів Q_j, Q_k - функціональні пристрої, що виробляють результат для запису в регістри F_j, F_k R_j, R_k - ознаки готовності операндів у регістрах F_j, F_k

1. Стан регістрів результату - показує функціональний пристрій, що буде записувати в кожний з регістрів. Це поле встановлюється в нуль, якщо відсутні команди, що записують результат у даний регістр.

Цікавим питанням є вартість і переваги централізованого керування. Розроблювачі CDC 6600 оцінюють поліпшення продуктивності для програм на Фортрані в 1.7 рази, а для вручну запрограмованих мовою асемблера програм в 2.5 рази. Однак ці оцінки робилися в той час, коли були відсутні програмні засоби планування завантаження конвеєра, напівпровідникова основна пам'ять і кеш-пам'ять (з малим часом доступу). Централізована схема керування CDC 6600 мала приблизно стільки ж логічних схем, що й один з функціональних пристроїв, що напрочуд мало. Основна вартість визначалася більшою кількістю шин (магістралей) - приблизно в чотири рази більше в порівнянні з машиною, що виконувала б команди в строгому порядку, заданому програмою.

Централізована схема керування не обробляє кілька ситуацій. Наприклад, коли команда записує свій результат, залежна команда в конвеєрі повинна чекати дозволу звертання до регістрового файлу, оскільки всі результати завжди записуються в регістровий файл і ніколи не використовується методика "прискореного пересилання". Це збільшує затримку й обмежує можливість ініціювання декількох команд, що очікують результату. Що стосується CDC 6600, то конфлікти типу WAW є дуже рідкими, так що припинення, які вони викликають, можливо не є істотними. Однак у наступному розділі ми побачимо, що динамічне планування дає можливість сполученого виконання декількох ітерацій циклу. Щоб це робити ефективно, потрібна схема обробки конфліктів типу WAW, які ймовірно збільшуються по частоті при сполученні виконання декількох ітерацій.

Стан команд
Команда			Видача			Читання операндів Завершення виконанняЗапис результата
LD	F6,34(R2)		(			(((
LD	F2,45(R3)		(			((
MULTD	F0,F2,F4		(
SUBD	F8,F6,F2		(
DIVD	F10,F0,F6		(
ADD	F6,F8,F2
Стан функціональних пристроїв
Им’я	Зайнятість	Op			Fi	FjFkQjQkRjRk
Integer	Так	Load			F2	R3
Mult1	Так	Mult			F0	F2F4 Ні Так
Mult2	Ні
Add	Так	Sub			F8	F6F2 Integer Та Ні
Divide	Ні	Div			F10	F0F6Mult1 Ні Так
Стан регістра результату
	F0	F2		F4		F6F8F10F12. . .F30
FU	Mult1	Integer				AddDivide

Рис. 2. Регістри стану централізованої схеми керування

Контрольні запитання

1. У чому полягає основна ідея динамічної оптимізації?

2. Які труднощі створює неупорядковане завершення команд при конвеєрній обробці?

3. У чому полягає основне завдання централізованої схеми виявлення конфліктів?

4. Які стадії проходить команда при використанні централізованої схеми виявлення конфліктів?

5. У чому головний недолік використання централізованої схеми виявлення конфліктів?

Рекомендована література

1. Самофалов и др. Основы теории многоуровневых конвеерных вычислительных систем. – К.,”Техніка”, 1980.

Лекція 10. Усунення залежностей по даним і механізми динамічного планування (продовження)

План лекції

1. Динамічне планування за методом Томасуло.

Виклад лекції

1. Динамічне планування за методом Томасуло

Інший підхід до паралельного виконання команд при наявності конфліктів був використаний у пристрої плаваючої крапки в машині IBM 360/91. Ця схема приписується Р. Томасуло й названа його ім'ям. Розробка IBM 360/91 була завершена через три роки після випуску CDC 6600, перш ніж кеш-пам'ять з'явилася в комерційних машинах. Завданням IBM було досягнення високої продуктивності на операціях із плаваючою крапкою, використовуючи набір команд і компілятори, розроблені для всього сімейства 360, а не тільки для додатків з інтенсивним використанням плаваючої крапки. Архітектура 360 передбачала тільки чотири регістри плаваючої крапки подвійної точності, що обмежувало ефективність планування коду компілятором. Цей факт був інший мотивацією підходу Томасуло. Нарешті, машина IBM 360/91 мала великий час звертання до пам'яті і більші затримки виконання операцій плаваючої крапки, перебороти які і був покликаний розроблений Томасуло алгоритм. Наприкінці розгляду ми побачимо, що алгоритм Томасуло може також підтримувати сполучене виконання декількох ітерацій циклу.

Ми пояснимо цей алгоритм на прикладі пристрою ПК. Основне розходження між нашим конвеєром ПК і конвеєром машини IBM/360 полягає в наявності в останній машині команд типу регістр-пам'ять. Оскільки алгоритм Томасуло використовує функціональний пристрій завантаження, не потрібно значних змін, щоб додати режими адресації регістр-пам'ять; основне додавання - інша шина. IBM 360/91 мала також конвеєрні функціональні пристрої, а не кілька функціональних пристроїв. Єдина відмінність між ними полягає в тім, що конвеєрний функціональний пристрій може починати виконання тільки однієї операції в кожному такті. Оскільки реально відсутні фундаментальні відмінності, ми описуємо алгоритм, як якби мали місце кілька функціональних пристроїв. IBM 360/91 могла виконувати одночасно три операції додавання ПК і дві операції множення ПК. Крім того, у процесі виконання могли перебувати до 6 операцій завантаження ПК, або звертань до пам'яті, і до трьох операцій запису ПК. Для реалізації цих функцій використовувалися буфери дані завантаження і буфери дані записи. Хоча ми не будемо обговорювати пристрій завантаження і запису, необхідно додати буфера для операндів.

Схема Томасуло має багато загального зі схемою централізованого керування CDC 6600, однак є й істотні відмінності. По-перше, виявлення конфліктів і керування виконанням є розподіленими - станції резервування (reservation stations) у кожному функціональному пристрої визначають, коли команда може почати виконуватися в даному функціональному пристрої. В CDC 6600 ця функція централізована. По-друге, результати операцій посилають прямо у функціональні пристрої, а не проходять через регістри. В IBM 360/91 є загальна шина результатів операцій (яка називається загальною шиною даних (common data bus - CDB)), що дозволяє робити одночасне завантаження всіх пристроїв, що очікують операнда. CDC 6600 записує результати в регістри, за які функціональні пристрої, що очікують, можуть суперничати. Крім того, CDC 6600 має кілька шин завершення операцій (дві в пристрої ПК), а IBM 360/91 - тільки одну.

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

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

1. Видача - Берет команду із черги команд ПК. Якщо операція є операцією ПК, видає її при наявності вільної станції резервування й посилає операнди на станцію резервування, якщо вони перебувають у регістрах. Якщо операція є операцією завантаження або запису, вона може видаватися при наявності вільного буфера. При відсутності вільної станції резервування або вільного буфера виникає структурний конфлікт і команда припиняється доти, поки не звільниться станція резервування або буфер.

2. Виконання - Якщо один або більше операндів команди не доступні по якимось причинам, контролюється стан CDB і очікується завершення обчислення значень потрібного регістра. На цій стадії виконується контроль конфліктів типу RAW. Коли обидва операнди доступні, виконується операція.

3. Запис результату - Коли стає доступним результат, він записується на CDB і звідти в регістри й будь-який функціональний пристрій, що очікує цей результат.

Хоча ці кроки в основному схожі на аналогічні кроки в централізованій схемі керування, є три важливих відмінності. По-перше, відсутній контроль конфліктів типу WAW і WAR - вони усуваються як побічний ефект алгоритму. По-друге, для трансляції результатів використається CDB, а не схема очікування готовності регістрів. По-третє, пристрої завантаження й запису розглядаються як основні функціональні пристрої.

Структури даних, використані для виявлення й усунення конфліктів, зв'язані зі станціями резервування, регістровим файлом і буферами завантаження й записи. Хоча з різними об'єктами зв'язана різна інформація, всі пристрої, за винятком буферів завантаження, містять у кожному рядку поле тегу. Це поле тегу являє собою чотирьохбітне значення, що позначає одну з п'яти станцій резервування або один із шести буферів завантаження. Поле тегу використається для опису того, який функціональний пристрй буде надавати результат, потрібний як джерело операнда. Значення, що не використовуються, такі як нуль, показують що операнд вже доступний. Важливо пам'ятати, що теги в схемі Томасуло посилаються на буфери або пристрої, які будуть поставляти результат; коли команда видається в станцію резервування номера регістрів виключаються з розгляду.

Рис. 1. Структура пристрою ПК на основі алгоритму Томасуло

Кожна станція резервування містить шість полів:

• O_p - Операція, що повинна виконуватися над джерелами операндів S₁ і S₂;

• Q_j,Q_k - станції резервування, які будуть виробляти відповідний операнд-джерело; нульове значення показує, що операнд-джерело вже доступний в V_j або V_k, або не є обов'язковим. IBM 360/91 називає їх SINKunit і SOURCEunit.

• V_j,V_k - значення операндів-джерел. Вони називаються SINK і SOURCE в IBM 360/91. Помітимо, що для кожного операнда є дійсними тільки одне з полів або поле V, або поле Q.

• Зайнято - Показує, що дана станція резервування і її відповідний функціональний пристрій зайнятий.

Регістровий файл і буфер запису мають поле Q_i:

• Q_i - номер функціонального пристрою, що буде виробляти значення, яке треба записати в регістр або пам'ять. Якщо значення Q_i дорівнює нулю, то це означає, що жодна поточна активна команда не обчислює результат для даного регістра або буфера. Для регістра це означає, що значення визначається вмістом регістра.

В кожному з буферів завантаження й запису потрібне поле зайнятості, що показує коли відповідний буфер стає доступним завдяки завершенню завантаження або запису, призначених на цей буфер. Буфер запису має також поле V для зберігання значення, що повинне бути записане на згадку.

Перш, ніж ми досліджуємо алгоритм у деталях, давайте подивимося як виглядають системні таблиці для наступної послідовності команд:

1. LF F6,34(R2)

2. LF F2,45(R3)

3. MULTD F0,F2,F4

4. SUBD F8,F6,F2

5. DIVD F10,F0,F6

6. ADDD F6,F8,F2

Рис. 2. описує станції резервування, буфера завантаження і записи і регістрові теги. До імен add, mult і load додані номери, що стоять за тегами для цієї станції резервування - Add1 є тегом для результату з першого пристрою додавання. Стан кожної операції, що видана для виконання, зберігається в станції резервування.

Стан команд
Команда					Видача	ВиконанняЗапис результата
LD	F6,34(R2)				(	((+
LD	F2,45(R3)				(	(
MULTD	F0,F2,F4				(
SUBD	F8,F6,F2				(
DIVD	F10,F0,F6				(
ADDD	F6,F8,F2				(
Станції резервування
Им’я	Занятість		Op		Vj	VkQjQk
Add1	Да		SUB		Mem[34+Regs[R2]]	Load2
Add2	Да		ADD			Add1Load2
Add3	Нет
Mult1	Да		MULT			Regs[F4]Load2
Mult2	Да		DIV			Mem[34+Regs[R2]]Mult1
Стан регістрів
Поле	F0	F2		F4		F6F8F10F12. . .F30
Qi	Mult1	Load2				Add2Add1Mult2

Рис. 2. Теги станцій резервування й регістрів

Є дві важливих відмінності від централізованої схеми керування, які помітні в цих таблицях. По-перше, значення операнда зберігається в станції резервування в одному з полів V як тільки воно стає доступним; воно не зчитується з регістрового файлу під час видачі команди. По-друге, команда ADDD видана для виконання. Її видача була заблокована в централізованій схемі керування через наявність структурного конфлікту.

Великі переваги схеми Томасуло полягають в (1) розподілі логіки виявлення конфліктів, і (2) усунення припинень, пов'язаних з конфліктами типу WAW і WAR. Перша перевага виникає через наявність розподілених станцій резервування й використання CDB. Якщо кілька команд очікують той самий результат і кожна команда вже має свій інший операнд, то команди можуть видаватися одночасно за допомогою трансляції по CDB. У централізованій схемі керування команди, що очікують, повинні читати свої операнди з регістрів коли стануть доступними регістрові шини.

Конфлікти типу WAW і WAR усуваються шляхом перейменування регістрів використовуючи станції резервування. Наприклад, у нашій кодовій послідовності на рис.2. ми видали на виконання як команду DIVD, так і команду ADDD, навіть хоча був конфлікт типу WAR по регістру F6. Конфлікт усувається одним із двох способів. Якщо команда, що поставляє значення для команди DIVD, завершилася, тоді V_k буде зберігати результат, дозволяючи DIVD виконуватися незалежно від команди ADDD. З іншого боку, якщо виконання команди LF не завершилося, то Q_k буде вказувати на LOAD1 і команда DIVD буде незалежною від ADDD. Таким чином, у кожному разі команда ADDD може бути видана й почати виконуватися. Будь-яке використання результату команди MULTD буде вказувати на станцію резервування, дозволяючи ADDD завершити й записати своє значення в регістри без впливу DIVD. Незабаром ми побачимо приклад усунення конфлікту типу WAW.

Щоб зрозуміти повну потужність усунення конфліктів типу WAW і WAR за допомогою динамічного перейменування регістрів ми повинні розглянути цикл. Розглянемо наступну просту послідовність команд для множення елементів вектора на скалярну величину, що перебуває в регістрі F2:

Loop: LD F0,0(R1)

MULTD F4,F0,F2

SD 0(R1),F4

SUBI R1,R1,#8

BNEZ R1,Loop ; умовний перехід при R1 /=0

Зі стратегією виконуваного переходу використання станцій резервування дозволить відразу ж продовжити виконання декількох ітерацій цього циклу. Ця перевага дається без статичного розгортання циклу програмними засобами: у дійсності цикл розвертається динамічно апаратурою. В архітектурі 360 наявність усього 4 регістрів ПК сильно обмежувало б використання статичного розгортання циклу. (Незабаром ми побачимо, що при статичному розгортанні й плануванні виконання циклу для обходу взаємних блокувань потрібно значно більше число регістрів). Алгоритм Томасуло підтримує виконання з перекриттям декількох копій того самого циклу при наявності лише невеликого числа регістрів, що використовуються програмою.

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

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

Стан команд
Команда					Номер ітерації					ВидачаВиконанняЗапис результата
LD	F0,0(R1)				1					((
MULTD	F4,F0,F2				1					(
SD	0(R1),F4				1					(
LD	F0,0(R1)				2					((
MULTD	F4,F0,F2				2					(
SD	0(R1),F4				2					(
Станція резервування
Им’я	Зайнятість			Fm				Vj		VkQjQk
Add1	Ні							Mem[34+Regs[R2]]
Add2	Ні
Add3	Ні
Mult1	Так			MULT						Regs[F2]Load1
Mult2	Так			MULT						Regs[F2]Load2
Стан регистрів
Поле	F0	F2				F4				F6F8F10F12. . .F30
Qi	Load2					Mult2
Буфери завантаження										Буфера запису
Поле	Load1		Load2						Load3	ПолеStore1Store2Store3
Адрес	Regs[R1]		Regs[R1]-8							QiMult1Mult2
Зайнятість	Так		Так						Ні	ЗайнятістьДаДаНет
										АдресRegs[R1]Regs[R1]-8

Рис. 3. Стан станцій резервування, регістрів та буферів завантаження/запису

Ця динамічна схема може досягати дуже високої продуктивності за умови того, що вартість переходів може підтримуватися невелика. Це питання ми будемо розглядати в наступному розділі. Головний недолік цього підходу полягає в складності схеми Томасуло, яка вимагає для своєї реалізації дуже великого обсягу апаратури. Особливо це стосується великої кількості пристроїв асоціативної пам'яті, яка повинна працювати з високою швидкістю, а також складної логіки керування. Нарешті, збільшення продуктивності обмежується наявністю однієї шини завершення (CDB). Хоча додаткові шини CDB можуть бути додані, кожна CDB повинна взаємодіяти з усією апаратурою конвеєра, включаючи станції резервування. Зокрема, апаратури асоціативного порівняння необхідно дублювати на кожній станції для кожної CDB.

У схемі Томасуло комбінуються дві різні методики: методика переіменування регістрів буферизація операндів-витоків з регістрового файлу. Буферизація джерел операндів дозволяє конфлікти типу WAR, які виникають коли операнди доступні в регістрах. Як ми побачимо пізніше, можливо також усувати конфлікти типу WAR за допомогою переіменування регістра разом з буферизацією результату доти, доки залишаються звертання до старої версії регістра; цей підхід буде використовуватися, коли ми будемо обговорювати апаратне виконання по припущенню.

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

Ключовими компонентами збільшення паралелізму рівня команд в алгоритмі Томасуло є динамічне планування, переіменування регістрів і динамічне усунення неоднозначності звертань до пам'яті. Важко оцінити значення кожної з цих властивостей окремо.

Динамічній апаратній техніці планування завантаження конвеєра при наявності залежностей за даними відповідає і динамічна техніка для ефективної обробки переходів. Ця техніка використовується для двох цілей: для прогнозування того, чи буде перехід виконуваним, і для можливо більш раннього знаходження цільової команди переходу. Ця техніка називається апаратним прогнозуванням переходів.

Контрольні запитання

1. Які основні складові схеми, запропонованої Томасуло?

2. Які істотні відмінності між централізованою схемою виявлення конфліктів і схемою Томасуло?

3. Які стадії виконання команд за схемою алгоритма Томасуло?

4. У чому полягають переваги схеми Томасуло перед централізованою схемою виявлення конфліктів?

5. Який головний недолік схеми Томасуло?

Рекомендована література

1. Самофалов и др. Основы теории многоуровневых конвеерных вычислительных систем. – К.,”Техніка”, 1980.

Лекція 11. Апаратне прогнозування напрямку переходів і зниження втрат на організацію переходів

План лекції

1. Буфера прогнозування умовних переходів.

2. Подальше зменшення зупинок по керуванню: буфера цільових адрес переходів.

Виклад лекції

1. Буфера прогнозування умовних переходів

Найпростішою схемою динамічного прогнозування напрямку умовних переходів є буфер прогнозування умовних переходів (branch-prediction buffer) або таблиця "історії" умовних переходів (branch history table). Буфер прогнозування умовних переходів являє собою невелику пам'ять, яка адресується за допомогою молодших розрядів адреси команди переходу. Кожний осередок цієї пам'яті містить один біт, що говорить про те, чи був попередній перехід виконуваним чи ні. Це найпростіший вид такого роду буфера. У ньому відсутні теги, і він виявляється корисним тільки для скорочення затримки переходу у випадку, якщо ця затримка більше, ніж час, необхідний для обчислення значення цільової адреси переходу. У дійсності ми не знаємо, чи є прогноз коректним (цей біт у відповідний осередок буфера могла встановити зовсім інша команда переходу, що мала те ж саме значення молодших розрядів адреси). Але це не має значення. Прогноз - це тільки припущення, що розглядається як коректне, і вибірка команд починається по прогнозованому напрямку. Якщо ж припущення виявиться невірним, біт прогнозу інвертується. Звичайно такий буфер можна розглядати як кеш-пам'ять, кожне звертання до якої є попаданням, і продуктивність буфера залежить від того, наскільки часто прогноз застосовувався і наскільки він виявився точним.

Однак проста однобітова схема прогнозу має недостатню продуктивність. Розглянемо, наприклад, команду умовного переходу в циклі, що була виконуваним переходом послідовно дев'ять разів підряд, а потому один раз невиконуваним. Напрямок переходу буде неправильно передвіщатися при першій і при останній ітерації циклу. Невірний прогноз останньої ітерації циклу неминучий, оскільки біт прогнозу буде говорити, що перехід "виконуваний" (перехід був дев'ять разів підряд виконуваним). Неправильний прогноз на першій ітерації відбувається через те, що біт прогнозу інвертується на попередньому виконанні останньої ітерації циклу, оскільки в цій ітерації перехід був невиконуваним. Таким чином, точність прогнозу для переходу, що виконувався в 90% випадків, склала тільки 80% (2 некоректних прогнози й 8 коректних). У загальному випадку, для команд умовного переходу, використовуваних для організації циклів, перехід є виконуваним багато разів підряд, а потому один раз виявляється невиконуваним. Тому однобітова схема прогнозування буде неправильно пророкувати напрямок переходу двічі (при першій і при останній ітерації).

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

Рис. 1. Діаграма стану двобітової схеми прогнозування

Двобітова схема прогнозування в дійсності є частковим випадком більш загальної схеми, що у кожному рядку буфера прогнозування має n-бітовий лічильник. Цей лічильник може приймати значення від 0 до 2ⁿ - 1. Тоді схема прогнозу буде наступною:

• Якщо значення лічильника більше або дорівнює 2^n-1 (крапка на середині інтервАЛП), то перехід прогнозується як виконуваний. Якщо напрямок переходу передвіщений правильно, до значення лічильника додається одиниця (якщо тільки воно не досягло максимальної величини); якщо прогноз був невірним, зі значення лічильника віднімається одиниця.

• Якщо значення лічильника менше, ніж 2^n-1, то перехід прогнозується як невиконуваний. Якщо напрямок переходу передвіщений правильно, від значення лічильника віднімається одиниця (якщо тільки не досягнуте значення 0); якщо прогноз був невірним, до значення лічильника додається одиниця.

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

Буфер прогнозування переходів може бути реалізований у вигляді невеликої спеціальної кеш-пам'яті, доступ до якої здійснюється за допомогою адреси команди під час стадії вибірки команди в конвеєрі (IF), або як пари бітів, пов'язаних з кожним блоком кеш-пам'яті команд і обраних з кожною командою. Якщо команда декодується як команда переходу, і якщо перехід прогнозований як виконуваний, вибірка команд починається із цільової адреси як тільки стане відомим нове значення лічильника команд. У противному випадку триває послідовна вибірка й виконання команд. Якщо прогноз виявився невірним, значення бітів прогнозу міняється відповідно до рис. 1. Хоча ця схема корисна для більшості конвеєрів, розглянутий нами найпростіший конвеєр з'ясовує приблизно за той самий час обидва питання: чи є перехід виконуваним і яка цільова адреса переходу (передбачається відсутність конфлікту при звертанні до регістра, визначеному у команді умовного переходу. Нагадаємо, що для найпростішого конвеєра це справедливо, оскільки умовний перехід виконує порівняння вмісту регістра з нулем під час стадії ID, під час якої обчислюється також і ефективна адреса). Таким чином, ця схема не допомагає у випадку простих конвеєрів, подібних розглянутому раніше.

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

Яку точність можна чекати від буфера прогнозування переходів на реальних додатках при використанні 2 біт на кожний рядок буфера? Для набору оцінних тестів SPEC-89 буфер прогнозування переходів з 4096 рядками дає точність прогнозу від 99% до 82%, тобто відсоток невдалих прогнозів становить від 1% до 18% (див. мал. 6.9). Слід зазначити, що буфер ємністю 4К рядків вважається дуже великим. Буфери меншого розміру дадуть гірші результати.

Однак одного знання точності прогнозу не досить для того, щоб визначити вплив переходів на продуктивність машини, навіть якщо відомі час виконання переходу й втрати при невдалому прогнозі. Необхідно враховувати частоту переходів у програмі, оскільки важливість правильного прогнозу більше в програмах з більшою частотою переходів. Наприклад, цілечисленні програми li, eqntott, expresso і gcc мають більшу частоту переходів, ніж значно простіші для прогнозування програми плаваючої крапки nasa7, matrix300 і tomcatv.

Оскільки головним завданням є використання максимально доступного ступеня паралелізму програми, точність прогнозу напрямку переходів стає дуже важливою. Як видно з рис.2, точність схеми прогнозування для цілечисленних програм, які звичайно мають більше високу частоту переходів, менше, ніж для наукових програм із плаваючою крапкою, у яких інтенсивно використовуються цикли. Можна вирішувати цю проблему двома способами: збільшенням розміру буфера й збільшенням точності схеми, що використовується для виконання кожного окремого прогнозу. Буфер з 4К рядками вже досить великий і, як показує рис.2, працює практично так само, як і буфер нескінченного розміру. Із цього малюнка стає також ясно, що коефіцієнт влучень буфера не є лімітуючим чинником. Як ми згадували вище, збільшення числа біт у схемі прогнозу також має малий ефект.

Рис. 2. Порівняння якості 2-бітового прогнозу

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

if (aa==2)

aa=0;

if (bb==2)

bb=0;

if (aa!=bb) {

Нижче наведений текст сгенерованої програми (передбачається, що aa і bb розміщено в регістрах R1 і R2):

SUBI R3,R1,#2

BNEZ R3,L1 ; перехід b1 (aa!=2)

ADD R1,R0,R0 ; aa=0

L1: SUBI R3,R2,#2

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).

...

L3:

Позначимо команди переходу як b1, b2 і b3. Можна помітити, що поведінка переходу b3 корелює з переходами b1 і b2. Ясно, що якщо обидва переходи b1 і b2 є невиконуваними (тобто обидві умови if оцінюються як істинні й обом змінним aa і bb присвоєне значення 0), те перехід b3 буде виконуваним, оскільки aa і bb очевидно рівні. Схема прогнозування, яка для пророкування напрямку переходу використовує тільки минулу поведінка того ж переходу, ніколи цього не врахує.

Схеми прогнозування, які для пророкування напрямку переходу використовують поведінку інших команд переходу, називаються корельованими або дворівневими схемами прогнозування. Схема прогнозування називається прогнозом (1,1), якщо вона використовує поведінку одного останнього переходу для вибору з пари однобітових схем прогнозування на кожний перехід. У загальному випадку схема прогнозування (m,n) використовує поведінку останніх m переходів для вибору з 2^m схем прогнозування, кожна з яких являє собою n-бітову схему прогнозування для кожного окремого переходу. Привабливість такого типу корельованих схем прогнозування переходів полягає в тому, що вони можуть давати більший відсоток успішного прогнозування, ніж звичайна двобітова схема, і вимагають дуже невеликого обсягу додаткових апаратур. Простота апаратної схеми визначається тим, що глобальна історія останніх m переходів може бути записана в m-бітовому регістрі зсуву, кожний розряд якого запам'ятовує, чи був перехід виконуваним чи ні. Тоді буфер прогнозування переходів може індексуватися конкатенацією (об'єднанням) молодших розрядів адреси переходу з m-бітовою глобальною історією. Наприклад, на рис. 3. показана схема прогнозування (2,2) і організація вибірки бітів прогнозу.

Рис. 3. Буфер прогнозування переходів (2,2)

У цій реалізації є тонкий ефект: оскільки буфер прогнозування не є кеш-пам'яттю, лічильники, які індексуються єдиним значенням глобальної схеми прогнозування, можуть у дійсності в деякий момент часу відповідати різним командам переходу; це не відрізняється від того, що ми бачили й раніше: прогноз може не відповідати поточному переходу. На рис.3 з метою спрощення розуміння буфер зображений як двовимірний об'єкт. У дійсності він може бути реалізований просто як лінійний масив двобітової пам'яті; індексація виконується шляхом конкатенації бітів глобальної історії й відповідним числом біт, необхідних від адреси переходу. Наприклад, на рис.2 у буфері (2,2) із загальним числом рядків, рівним 64, чотири молодших розряди адреси команди переходу й два біти глобальної історії формують 6-бітовий індекс, що може використовуватися для звертання до 64 лічильників.

Наскільки краще схеми з кореляцією переходів працюють у порівнянні зі стандартною двобітовою схемою? Щоб їх справедливо зрівняти, потрібно зіставити схеми прогнозування, що використовують однакове число біт стану. Число біт у схемі прогнозування (m,n) дорівнює 2^m ( n ( кількість рядків, обраних за допомогою адреси переходу.

Наприклад, двобітова схема прогнозування без глобальної історії є просто схема (0,2). Скільки біт потрібно для реалізації схеми прогнозування (0,2), що ми розглядали раніше? Скільки біт використовується в схемі прогнозування, показаної на рис.3?

Раніше ми розглядали схему прогнозування з 4К рядками, обраними адресою переходу. У такий спосіб загальна кількість біт дорівнює: 2⁰ ( 2 ( 4K)) = 8K.

Схема на рис.3. має 2² ( 2 ( 16)) = 128 біт.

Щоб зрівняти продуктивність схеми корельованого прогнозування із простою двобітовою схемою прогнозування, продуктивність якої була представлена на рис.1, потрібно визначити кількість рядків у схемі корельованого прогнозування.

Таким чином, ми повинні визначити кількість рядків, обраних командою переходу в схемі прогнозування (2,2), що містить 8К біт у буфері прогнозування.

Ми знаємо, що

2² ( 2 ( кількість рядків, обраних

командою переходу)) = 8К

Тому

Кількість рядків, обраних командою

переходу = 1К.

На рис.2 представлені результати для порівняння простої двобітівої схеми прогнозування з 4К рядками й схеми прогнозування (2,2) з 1К рядками. Як можна бачити, ця остання схема прогнозування не тільки перевершує просту двобітівую схему прогнозування з тією ж самою кількістю біт стану, але часто перевершує навіть двобітівую схему прогнозування з необмеженою (нескінченною) кількістю рядків. Є широкий спектр кореляційних схем прогнозування, серед яких схеми (0,2) і (2,2) є найцікавішими.