5.3.3.5. Динамічне передбачення переходу

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

При реалізації методів динамічного передбачення створюється таблиця історії пере­ходів.

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

Таблиця історії переходів реалізується в складі буфера адрес переходу (рис. 5.12). Ко­жен рядок буфера адрес переходу включає адресу команди переходу, прогнозовану адре­су наступної команди (адресу переходу) і передісторію команди переходу (рис. 5.18). Біти передісторії є інформацією про виконання або невиконання умов переходу даної коман­ди у минулому. Звернення до буфера адрес переходу (порівняння з полями адрес команд переходу) проводиться за допомогою поточного значення програмного лічильника на етапі вибірки чергової команди. За передісторією команди прогнозується виконання або

186

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

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

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

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

187

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

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

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

188

шляхом об'єднання адреси команди переходу та вмісту регістру глобальної історії. Для такого об'єднання використовується або операція конкатенації (зчеплення) (рис. 5.19в), або операція додавання за модулем 2. При цьому можуть використовуватися як всі роз­ряди адреси команди переходу та вмісту регістру глобальної історії, так і лише деяка 'їх кількість.

Потрібно відзначити, що в якості таблиці історії переходів зазвичай використовуєть­ся асоціативна пам'ять, що дозволяє суттєво прискорити пошук коду переходу.

Наведені схеми названі однорівневими, оскільки в них задіяно один рівень таблиць. Такі схеми передбачення використані в наступних комп'ютерах: Alpha 21064 та 21064, AMD K5, R10000, Power PC620, UltraSPARC та інших.

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

Для різних програм різні стратегії передбачення дають різну точність. Тому в ряді комп'ютерів застосовуються гібридні схеми передбачення переходів, коли в кожному конкретному випадку застосовується та схема передбачення, від якої очікується найви­ща точність передбачення. Структура такої гібридної схеми показана на рис. 5.21.

189

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

5.4. Покращена структура комп'ютера із спрощеною системою команд

На основі проведеного вище аналізу конфліктів у конвеєрі та способів їх мініміза­ції можна провести покращання структури комп'ютера із спрощеною системою команд. В якості прикладу на рис. 5.22 подано покращену структуру тракту виконання команд комп'ютера DLX.

190

Структура додатково містить:

• суматор ADD,який прискорено, вже на сходинці ID,обраховує цільову адресу пе­реходу;

• вузол Zeroперенесено на один ярус вперед, щоб прискорити реакцію конвеєра на команду умовного переходу та синхронізувати цю реакцію з обрахуванням цільової адреси переходу. В результаті зменшено на такт затримку переходу;

• введено додаткові інформаційні шини, що дозволяють прискорено надсилати до вузлів процесора коди операндів при реалізації випередження. При цьому кількість вхо­дів мультиплексорів АЛП збільшено.

Кольорами відтінені відповідності станів вузлів конвеєра командам, які цей конвеєр опрацьовує.

5.5. Особливості запобігання конфліктам в суперскалярних процесорах

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

Під впорядкованим поступленням команд та впорядкованим завершенням команд розуміють таким чином впорядковану черговість поступлення команд на виконання та черговість завершення команд, яка визначена програмою. В іншому випадку говорять про невпорядковане поступлення команд та невпорядковане завершення команд.

В перших супєрскалярних процесорах типу Pentiumбуло реалізоване впорядковане поступлення команд і впорядковане завершення команд. Такий підхід був досить про­стим, оскільки при виникненні конфліктів у одному з конвеєрів процесора призупиня­лась робота іншого конвеєра до зняття конфлікту, з тим, щоб не порушувати порядок поступлення та завершення команд. Однак це вимагало великих часових втрат.

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

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

197

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

Буферна пам'ять, яка називається вікном команд, може бути реалізована двома спо­собами - як інтегрована та як розподілена.

Інтегрована буферна пам'ять реалізується на основі асоціативної пам'яті. Вона опе­ративно виявляє і подає на виконання команди, для виконання яких є всі необхідні опе-ранди та ресурси. Для кожної команди в цій пам'яті виділяється одна комірка. В цій ко­мірці зберігається декодована команда, яка має наступні поля: декодоване поле операції (О), поля операндів (ПО), які вміщують або самі операнди, або адреси їх знаходження, поле, яке вказує місце розміщення результату (ПР), а також поле розрядів достовірності (РД). Для аналізу доступності та виконання розподілу команд до вільних функціональ­них пристроїв (ФП) в процесорі використовується пристрій диспетчеризації, в якому є регістр зайнятості функціональних пристроїв процесора (рис. 5.23).

Команда зчитується з інтегрованої буферної пам'яті на виконання лише після того, коли в полях операндів ПО1 та П02 присутні значення операндів або їх адрес (тобто в полі розрядів достовірності Рді та РД2 записані одиниці), та коли потрібні для її ви­конання функціональні пристрої є вільними (тобто в регістрі зайнятості записані оди­ниці). Результат виконання команди записується до відповідного регістру регістрово­го файла. Оновлення інформації про зайнятість функціональних пристроїв процесора здійснюється в кожному його циклі.

Якщо вікно команд реалізується як розподілена буферна пам'ять, то на вході кожно­го функціонального блоку розміщується буфер декодованих команд, який називається блоком резервування (БР). Після вибірки та декодування команди поступають до того блоку резервування, в якому вони будуть виконуватися (рис. 5.24). Робота кожного

192

блоку резервування є аналогічною роботі інтегрованої буферної пам'яті, тобто коман­да поступає на виконання при готовності операндів та незайнятості функціонального пристрою.

Оскільки метод резервування орієнтований на подання на опрацювання одночасно декількох команд, використання розподіленої буферної пам'яті (вікна команд) для забез­печення перевпорядкуванням команд є значно простішим порівняно з використанням багатопортової інтегрованої буферної пам'яті. Подібну розподілену буферну пам'ять вперше запропонував Р. Томасуло в комп'ютерній системі ІВМ360/91 у 1967 році, тому описаний метод резервування носить його ім'я.

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

5.6. Комп'ютери з довгим форматом команди

Раніше розглянуті суперскалярні процесори характеризуються високою продуктив­ністю при забезпеченні безконфліктного виконання команд. Але це вимагає значних до­даткових затрат обладнання. На рис. 5. 25 показано кристал суперскалярного процесора MIPSR10000,на якому позначені вузли процесора та виділено апаратні засоби пристрою керування, які забезпечують невпорядковане виконання команд. Видно, що ці засоби зайняли більше ЗО відсотків площі кристала.

193

Розглянемо далі архітектури комп'ютерів, у яких відсутні конфлікти команд. До них, зокрема, належать комп'ютери з довгим форматом команди

Архітектура комп'ютерів з довгим форматом команди (КДФК), англійський еквіва­лент VLIW (Very Long Instruction Word), бере свій початок від паралельного мікрокоду, що застосовувався в комп ютерах CDC6600 і IBM 360/91. У 70-х роках багато комп'ютер­них систем оснащувалися додатковими векторними процесорами обробки сигналів, що використовували довгий формат команди. Зокрема, до таких процесорів належали про­цесори АР-120В, AP-190Lта інші фірми FPS.

Першими універсальними комп'ютерами з архітектурою КДФК стали міні-супер-комп ютери, випущені на початку 1980-х років компаніями MultiFlow,Cullerі Cydrome,але вони не мали комерційного успіху. Наприклад, комп'ютер компанії MultiFlow 7/300 використовував два арифметико-логічні пристрої для цілих чисел, два арифметико-ло-гічні пристрої для чисел з рухомою комою і блок логічного галуження. Його 256-роз-рядний довгий формат команди містить поля для восьми 32-розрядних команд. В цих комп'ютерах були використані планувальник обчислень і програмна конвеєризація, які є основою технологи компілятора КДФК

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

194

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

Компілятор визначає ділянку програми без циклів, яка стає кандидатом для форму­вання в'язанки команд. Для збільшення розміру тіла циклу широко використовується методика розкручування циклів, що призводить до утворення великих фрагментів про­грами, що не містять зворотних дуг.

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

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

З погляду архітектурних ідей комп'ютер з довгим форматом команди можна розгля­дати як розширення архітектури комп'ютера з простою системою команд, Оскільки тут

195

також довжина команди є сталою, апаратні ресурси плануються статично, та віддається перевага програмному вирішенню конфліктів.

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

Таким чином, розпаралелювання у комп'ютерах з довгим форматом команди вико­нується виключно на етапі компіляції під час формування в язанок команд, тобто ста­тично. Так як неможливо наперед передбачити розв'язання усіх видів залежностей, від-компільовані програми вимагають ретельного налагоджування. Негативно впливають також ефекти невпорядкованого завершення виконання команд. Саме тому надійність виконання програми тут зменшена порівняно з суперскалярним варіантом архітектури комп'ютера. Тобто, цей підхід дозволяє досягти максимуму продуктивності, але є прий­нятним лише у певних застосуваннях комп'ютерних засобів. Перевага КДФК в потенцій­ній продуктивності найбільш відчутна в серверних задачах, де паралельно опрацьовують декілька процесів (ниток), в наукових задачах, задачах тривимірної візуалізації та в за­дачах обробки сигналів (де, зокрема, застосовуються процесори ADSP21XX фірми Analog Devices та TMS320C6X фірми Texas Instruments, які належать до вказаної архітектури).

Архітектуру КДФК запроваджено у новітніх процесорах Alpha фірми DEC та ІА-64 фірми Intel. Останній процесор оптимізовано для виконання серверних задач Як приклад на рис. 5.27 приведено структуру ядра процесора TMS320C6Xфірми TexasInstruments,в якому використано довгий формат команди. В'язанка команд цього процесора склада­ється з восьми 32-розрядних команд. Тут використано два тракти обробки даних А та В, кожний з яких має по 4 функціональні блоки та свій багатопортовий регістровий файл.

Тракти обробки даних А і В є однотипними та мають в своєму складі наступні функ­ціональні пристрої: L- АЛП, S- пристрій зсуву та АЛП, М - перемножувач, D- фор­мувач адрес пам'яті. В'язанка команд зчитується з пам'яті команд (On-Chip Program Memory) та поступає до блоку диспетчеризації (Dispatch Unit), який здійснює розподіл команд у відповідні функціональні пристрої.

196