Огляд архітектури IBM PC-сумісного комп'ютера

Основні визначення

Під архітектурою процесора розуміється його програмна модель, тобто властивості, які є доступними програмно. Під мікроархітектурою розуміється внутрішня реалізація цієї програмної моделі. Для однієї і тієї ж архітектури (Intel Architecture 32 bit, IA-32) різними фірмами і у різних поколіннях застосовуються принципово різні мікроархітектурні реалізації.

У мікроархітектурі процесорів 5-го і 6-го поколінь - Pentium, PentiumPro, PentiumMMX, PentiumII - суттєве значення має реалізація різних способів конвеєризації і розпаралелювання обчислювальних процесів, а також інших технологій, не притаманних процесорам попередніх поколінь.

Конвеєризація (pipelining) - передбачає розбиття виконання кожної інструкції на декілька етапів, при цьому кожний етап виконується на своїй ступені конвеєра процесора. Під час виконання інструкція пересувається по конвеєру по мірі звільнення наступних ступіней.

Скалярним називають процесор з єдиним конвеєром (усі процесори Intel до 486 включно). Суперскалярний процесор має більше одного конвеєра (Pentium - 2, PentiumPro - 3), здатних обробляти інструкції паралельно.

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

Переміщення даних (data forwarding) передбачає початок виконання інструкції до готовності усіх операндів.

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

Виконання по припущенню, або спекулятивне виконання (speculative execution) - передбачені після переходу інструкції не тільки декодуються, але й по можливості виконуються до перевірки умови переходу.

Виконання зі зміною послідовності інструкцій (out-of-order execution) - змінюється порядок внутрішнього маніпулювання даними, а зовнішні (шинні) операції введення-виведення і запису в пам'ять виконуються, звичайно, у порядку передбаченому програмним кодом.

Існуючі на даний час процесорні архітектури поділяються на 2 глобальні категорії - RISC і CISC.

Покоління процесорів x86

Сімейство x86 нараховує 7 поколінь процесорів:

Перше покоління (процесори 8086, 8080 і математичний сопроцесор 8087) заклало архітектурну основу - набір нерівноправних 16-розрядних регістрів, сегментну систему адресації пам'яті у межах 1Мбайт з великим різноманіттям режимів, систему команд, систему переривань та ін. В процесорах застосовувалась „мала" конвеєризація - поки одні вузли виконували поточну інструкцію, блок попередньої вибірки вибирав з пам'яті наступну. На виконання інструкції було потрібно в середньому 12 тактів процесорного ядра.

Друге покоління (80286 із сопроцесором 80287) принесло захищений режим, що дозволяє задіяти віртуальну пам'ять розміром до 1Гбайт для кожної задачі, користуючись адресованою фізичною пам'яттю у межах 16Мбайт. Захищений режим є основою для побудови багатозадачних операційних систем, в яких жорстко регламентуються взаємовідношення задач з пам'яттю. На виконання інструкції - в середньому 4,5 тактів.

Третє покоління (386/387 DX і SX) - перехід до 32-розрядної архітектури IA-32. Збільшився об'єм адресованої пам'яті (до 4Гбайт реальної, 64Тбайт віртуальної). В систему команд введено можливість переключення розрядності адресації і даних. На виконання інструкції - ті самі 4,5 тактів, але тактова частота досягла 40МГц.

Четверте покоління (486 DX і SX) у видиму архітектурну модель великих змін не внесло, але було прийнято ряд заходів для збільшення продуктивності. Значно ускладнений виконавчий конвеєр - основні операції виконує RISC-ядро, „завдання" для якого готуються з вхідних CISC-інструкцій. На виконання інструкції - в середньому 2 такти. Введено швидкодіючий первинний кеш об'ємом 8-16Кбайт. Відмовились від зовнішнього математичного сопроцесора: тепер він розміщується на одному кристалі з центральним (FPU - Floating-Point Unit), або відсутній взагалі. Тактова частота досягла 100МГц (Intel) і 133МГц (AMD).

П'яте покоління (IntelPentium, AMDK5) привнесло суперскалярну архітектуру. Після блоків попередньої вибірки і першої стадії декодування інструкцій є два конвеєра, U-конвеєр і V-конвеєр. Кожен з них має ступіні кінцевого декодування, виконання інструкцій і буфер запису результатів. На виконання інструкції - в середньому 1 такт. Застосовується блок передбачення розгалужень. Для швидкого забезпечення конвеєрів інструкціями і даними з пам'яті шина даних процесорів є 64-розрядною. З'являється розширення MMX (Multimedia Extensions), яке застосовує принцип SIMD: одна інструкція виконує дії одразу з декількома (2, 4 або 8) комплектами операндів.

Шосте покоління процесорів Intel (мікроархітектура P6: PentiumPro, PentiumII, PentiumIII, Celeron, Xeon). Характерна риса - динамічне виконання, під котрим розуміється виконання інструкцій не в тому порядку (out of order), як передбачено програмним кодом, а в тому, як „зручно" процесору. Інструкції, які поступають на конвеєр, розбиваються на мікрооперації ?-ops, які надалі виконуються суперскалярним процесорним ядром у порядку, зручному процесору. Результати „невпорядкованого" виконання операції збираються в упорядкувальному буфері та в коректному порядку записуються в пам'ять (і порти в/в). Застосовується апаратне перейменування регістрів. Реалізовано виконання по припущенню. Середня кількість тактів на інструкцію (PentiumPro) скоротилося до 0,5. Введено подвійну незалежну шину (DIB), яка зв'язує процесор із вторинним кешем, що знаходиться в одній упаковці з процесором. AMD у своїх процесорах 6-го покоління (K6) реалізувала невпорядковане виконання, а подвійна шина з'явилася лише в K6-III. Шосте покоління отримало потокове розширення 3DNow! (AMD) і SSE - Streaming SIMD Extension (Intel).

Сьоме покоління (у AMD) почалося з процесора Athlon, в якому суперскалярність і суперконвеєрність охопили блок FPU. Intel розпочала 7 покоління процесором Pentium4.

1.1 Архітектура системи команд. Класифікація процесорів (CISC та RISC)

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

Двома основними архітектурами набору команд, що використовуються сучасною комп`ютерною промисловістю є архітектури CISC та RISC. Винахідником архітектури CISC можна вважати компанію IBM з її серією /360, ядро якої використовується з 60-х років і у теперішній час у машинах серії ES/9000.

Лідером в розробці мікропроцесорів з повним набором команд (CISC - Complete Instruction Set Computer) вважається компанія Intel із серією Pentium. Ця архітектура практично є стандартною для ринку мікрокомп`ютерів. Характерні ознаки CISC-процесорів: невелика кількість регістрів загального призначення; велика кількість машинних інструкцій, деякі з них навантажені семантичним значенням подібним до операторів високорівневих мов програмування, які виконуються за декілька тактів; велика кількість методів адресації; велика кількість форматів команд різної розрядності; перевага двоадресного формату команд; наявність команд обробки типу регістр-пам`ять.

Основою архітектури сучасних робочих станцій та серверів є архітектура із скороченим набором команд (RISC - Reduced Instruction Set Computer). Ця архітектура базується на комп`ютерах серії CDC6600, розробники якої (Торнтон, Крей та інші) вважали за доцільне спростити набір команд процесора для підвищення швидкодії. Кінцеве формування поняття RISC архітектури сформувалось на базі 3 проектів: процесора 801 компанії IBM, процесора RISC університету Берклі, процесора MIPS Стенфордського університету.

Розробка експериментального проекту почалася компанією IBM в кінці 70-х років, але його результати опубліковано не було і комп`ютер на його основі в промислових масштабах не використовувався. У 1980 р. Д. Паттерсон зі своїми колегами з Берклі почали свій проект і виготовили 2 машини, які мали назву RISC-I та RISC-II. Головною ідеєю цих машин було відокремлення повільної пам`яті від швидких регістрів та використання регістрових вікон. У 1980 р. Дж. Хеннессі зі своїми колегами опублікував опис стенфордської машини MIPS, основним аспектом розробки якої була ефективна реалізація конвеєрної обробки за допомогою планування команд компілятором.

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

Інші особливості архітектури RISC: великий об`єм регістрового файлу (у сучасних процесорах по 32 регістра цілочисельних та математичних), що спрощує роботу компілятора по розміщенню даних в регістрах. Для обробки як правило використовуються трьоадресний формат команд.

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

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

Слід зауважити, що у останніх розробках компанії Intel а також у її конкурентів (AMD, Cyrix, NexGen) широко використовуються ідеї RISC-процесорів, таким чином різниця між цими двома архітектурами поступово зникає.

1.2 Найпростіша організація конвеєра та оцінка його продуктивності

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

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

Далі для ілюстрації принципів роботи процесорів будемо розглядати найпростішу архітектуру: 32 цілочисельних регістра R0 - R31, 32 регістра для роботи з плаваючою комою F0 - F31 та вказівник команд РС. Будемо вважати, що набір команд такого процесора включає арифметичні та логічні операції, операції з плаваючою комою, операції пересилки даних, операції керування потоком команд та системні операції. У арифметичних командах використовується троьхадресний формат, типовий для RISC-процесорів, а для звернення до пам`яті використовуються операції завантаження та запису вмісту регістру в пам`ять.

Виконання типової команди можна розділити на такі етапи:

вибір команди (IF) з адреси, на яку вказує вказівник команд;

декодування команди / вибір операндів з регістрів (ID);

виконання операції / обчислення ефективної адреси у пам`яті (EX);

звернення до пам`яті (MEM);

запис результату (WB).

Розглянемо схему виконання команд на найпростішому процесорі без використання конвеєра (нехай на виконання команди потрібно 5 тактів):

Як бачимо, для виконання двох команд знадобилось 10 тактів, тобто загальна кількість тактів необхідна для виконання фрагменту з N машинних команд буде N*M, де М - кількість тактів, необхідних для виконання однієї команди. Для того, щоб застосувати конвеєризацію, потрібно розділити виконання команд на означені етапи. Хоча у такому випадку час обробки однієї команди все рівно буде складати 5 тактів, апаратура процесора одночасно буде виконувати 5 команд:

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

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

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

Структурні конфлікти, які виникають внаслідок конфліктів по ресурсах, коли апаратні засоби не можуть підтримувати всі комбінації команд у режимі одночасного виконання із суміщенням;

Конфлікти по даних, що виникають у випадку, коли виконання наступної команди залежить від результатів виконання попередньої;

Конфлікти по керуванню, які виникають при конвеєризації команд переходів які змінюють значення вказівника команд.

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

1.3 Структурні конфлікти та способи їх мінімізації

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

Структурні конфлікти можуть виникати, наприклад у машинах, які мають єдиний конвеєр пам`яті для команд та даних. У цьому випадку коли команда буде містити звернення до пам`яті за даними, воно буде конфліктувати з вибіркою наступної команди з пам`яті. Щоб вирішити таку проблему, достатньо просто призупинити конвеєр на один такт, коли відбувається звернення до пам`яті за даними. Подібна зупинка називається "конвеєрною бульбашкою" оскільки бульбашка проходить по конвеєру, займаючи місце, але не виконуючи ніякої корисної роботи:

В загальному випадку, машина без структурних конфліктів буде мати менший CPI (середня кількість тактів на виконання однієї інструкції). Виникає питання: чому розроблювачі процесорів допускають появу структурних конфліктів? Є дві причини для цього: зменшення ціни на процесор та зменшення затримок пристрою. Конвеєризація всіх функціональних пристроїв може бути дуже коштовною. Машини, що мають можливість одночасного звернення до пам`яті, мають подвоєну пропускну здатність пам`яті наприклад шляхом розділення кешей для даних та для команд. Як правило, можливо спроектувати не конвеєрний або не повністю конвеєрний пристрій, який би мав менший CPI ніж повністю конвеєрний пристрій. Наприклад, розроблювачі машин CDC7600 та MIPS R2010 віддали перевагу меншій затримці виконання конвеєрних операцій замість повної конвеєризації.

1.4 Конфлікти по даних, реалізація механізмів обходів

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

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

У цьому прикладі всі команди, що слідують за командою ADD, використовують результат її виконання. Команда ADD записує результат у R1, а команда SUB читає його значення. Якщо не вживати ніяких заходів, команда SUB може прочитати невірне значення і використати його. Ця проблема може бути вирішена за допомогою достатньо простої апаратної техніки, яка називається пересилкою або переміщенням даних (data forwarding). Ця апаратура працює наступним чином: Результат операції АЛП з вихідного регістра завжди пересилається назад на входи АЛП. Якщо апаратура з`ясовує, що попередня операція записує результат у регістр, який є одним з операндів наступної, читається значення передане на вхід АЛП, а не значення регістрового файлу.

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

Конфлікти по даних, що ведуть до зупинки конвеєра

Нажаль, не всі потенційні конфлікти по даних можуть оброблятися за допомогою механізмів "обходу". Розглянемо послідовність команд:

Команда завантаження R1 з пам`яті має затримку, яка не може бути ліквідована звичайною "пересилкою". Замість цього нам потрібна додаткова апаратура, що називається апаратурою внутрішнього блокування конвеєра для того, щоб забезпечити коректне виконання прикладу. Взагалі така апаратура виявляє конфлікт і призупиняє конвеєр доки конфлікт не буде ліквідовано.

1.5 Методика планування компілятора для усунення конфліктів по даних

Багато типів зупинок конвеєра можуть траплятися досить часто. Наприклад, для оператора A = B + C компілятор генерує таку послідовність команд:

Зрозуміло, виконання команди ADD має бути зупинено до тих пір, доки не стане доступним операнд С.

Для даного простого прикладу компілятор ніяк не може покращити ситуацію, але у багатьох інших випадках компілятор може досить суттєво впливати на ситуацію за допомогою перестановок команд. Ця техніка називається плануванням завантаження конвеєра (pipeline scheduling) або плануванням потоку команд (instruction scheduling), використовується з 60-х років і розвинулась у окрему галузь у 80-х коли з`явилась велика кількість конвеєрних машин.

Наприклад, маємо 2 оператора на мові програмування С: a = b + c; d = e - f; Яким чином можна згенерувати послідовність команд для зменшення конфліктів по даних?

В результаті ліквідовано блокування (командою LW Rc,c команди ADD Ra,Rb,Rc та командою LW Rf,f команди SUB Rd,Re,Rf). Мається залежність між операцією АЛП та операцією запису до пам`яті, але структура конвеєру дозволяє запис результатів за допомогою ланцюгів обходу. Використання різних регістрів для першого та другого операторів було критичним для реалізації правильного планування. В загальному випадку планування може потребувати великої кількості регістрів. Це особливо суттєво для машин, які можуть одночасно виконувати декілька команд за один такт.

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

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

Основними засобами динамічної оптимізації є

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

Буферизація команд, що очікують вирішення конфлікту, та видача наступних, логічно не зв`язаних команд в "обхід" буфера;

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

1.6 Метод перейменування регістрів

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

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

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

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

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

1.7 Скорочення втрат на виконання команд переходу та мінімізація конфліктів по керуванню

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

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

Наприклад, якщо конвеєр буде зупинено на 3 такти на кожної стадії умовного переходу, то це може суттєво вплинути на швидкодію процесора. При частоті команд умовного переходу 30% та ідеальному CPI = 1 машина буде мати тільки половину прискорення конвеєрної обробки. Таким чином, зниження втрат від команд умовного переходу є критичним питанням. Число тактів, що втрачаються у зупинках викликаних переходами може бути зменшено двома шляхами:

Виявлення виконуваності чи невиконуваності переходу на ранніх стадіях обробки;

Обчислення адреси переходу для виконуваного переходу на ранніх стадіях.

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

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

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

Четверта схема, яка використовується у деяких машинах має назву "затриманих переходів". У затриманому переході такт виконання із затримкою переходу довжиною в n є:

Команда умовного переходу

Наступна команда 1

Наступна команда 2

……………………..

Наступна команда n

Цільова адреса при виконуваному переході

Команди 1 - n знаходяться в слотах (часових інтервалах) затриманого переходу. Задача програмного забезпечення полягає у тому, щоб зробити команди, що слідують за командою умовного переходу, дійсними та корисними. Апаратура гарантує реальне виконання цих команд перед командою переходу. Тут використовуються декілька методів оптимізації.

Планування затриманих переходів ускладнюється:

Наявністю обмежень на команди, розміщення яких планується в слотах затримки

Необхідністю передбачати під час компіляції, чи буде перехід виконуваним.

Практика свідчить, що біля 50% всіх слотів є заповненими, і 80% їх є корисними. Це може здатися дивним, оскільки 53% умовних переходів не практиці виконуються. Але високий відсоток поясняється тим, що приблизно половина слотів заповнюється командами, виконання яких необхідно без залежності від переходу.

1.8 Проблеми реалізації точного переривання в конвеєрі

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

Як і в безконвеєрних машинах двома основними проблемами реалізації переривань є:

переривання виникає у процесі виконання деякої команди;

необхідний механізм повернення з переривання для продовження виконання програми.

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

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

У послідовність команд що поступають на обробку в конвеєр, треба вставити команду переходу на підпрограму обробки переривання;

Доки виконується команда переходу на переривання, задовольнити всі потреби запису команди, що викликала переривання, а також всіма командами що слідують в конвеєрі за нею;

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

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

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

1.9 Основи планування завантаження конвеєра та розгортання циклів

Для підтримання максимальної завантаженості конвеєра повинен використовуватись паралелізм рівня команд, оснований на виявлені послідовності незв`язаних команд, які можуть виконуватися в конвеєрі із суміщенням. Щоб уникнути зупинки конвеєра залежна команда повинна бути відокремлена від вихідної команди на відстань у тактах, не меншу ніж затримка конвеєра для цієї команди. Для прикладів будемо вважати, що умовні переходи мають затримку в 1 такт. Затримки для інших типів команд:

У даному розділі ми розглянемо яким чином компілятор може збільшити ступінь паралелізму за допомогою розгортання циклу. Для прикладу будемо розглядати простий цикл, який додає до вектора в пам`яті скалярну величину. Такий цикл є повністю паралельним, оскільки залежність між його ітераціями відсутня. Припускаємо, що R1 містить адресу останнього елементу вектора, а F2 - скаляр, який потрібно додати до вектора. Програма яка не використовує переваги конвеєризації буде виглядати таким чином:

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 тактів на елемент масиву.

Виграш від оптимізації розгорнутого циклу навіть більший ніж від оптимізації нерозгорнутого тому що розгортання циклу виявило більшу кількість команд котрі не залежать одна від іншої.

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

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

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

Але проста однобітова схема має недостатню ефективність. Розглянемо, наприклад, команду умовного переходу в циклі яка 9 разів виконувалась, а на 10 раз не виконалась. Напрямок переходу буде невірно спрогнозовано на 1 та на останній ітерації. Невірний прогноз останньої ітерації неминучий, оскільки перехід виконувався 9 разів підряд. Таким чином точність прогнозу була 80% (8 правильних та 2 неправильних прогнози).

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

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

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

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

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

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

Як показують практичні тести, 2-бітовий буфер розміром 4096 комірок дає точність прогнозування від 99% до 82% в залежності від типу програмного забезпечення.

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

1.11 Схеми корельованого прогнозування переходів

Схеми з 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 переходів для вибору з 2^m схем прогнозування, кожна з якої представляє собою n-бітову схему прогнозування для кожного окремого переходу. Перевага такого типу корельованих схем полягає в тому, що вони можуть давати більший відсоток правильних прогнозів, ніж проста схема та потребують невеликого ускладнення апаратних засобів. Простота апаратних засобів пояснюється тим, що історія останніх m переходів може бути записана в регістр зсуву розрядності m, у кожний розряд якого заноситься інформація, був цей перехід виконаний чи ні. Тоді буфер прогнозування переходів може адресуватись конкатенацією регістру зсуву та молодших бітів адреси команди переходу. На малюнку зображена схема прогнозування (2,2):

1.12 Одночасна видача декількох команд для виконання та динамічне планування

Методи мінімізації зупинок у роботі конвеєра, пов`язаних із логічною залежністю команд, були націлені на досягнення ідеального СРІ рівного 1. Щоб ще більше підвищити швидкодію машини треба цей коефіцієнт зробити меншим ніж 1. Зрозуміло, що цього не можна досягти якщо у одному такті обробляється максимум одна команда. Тобто необхідна паралельна обробка декількох команд за один такт. Існує два типа таких машин, що можуть виконувати більше ніж одну команду за такт: суперскалярні машини та VLIW-машини. Суперскалярні машини можуть виконувати за один такт змінне число команд, а робота їх конвеєрів може плануватись як програмно за допомогою компілятора, так і апаратно засобами процесора. На відміну від суперскалярних машин, VLIW-машини видають на виконання фіксоване число команд та планування виконання відбувається тільки статично за допомогою компілятора.

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

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

У простих процесорах використовується підхід, коли може бути одночасно виконані дві команди: команда із плаваючою комою та цілочисельна команда. У реальних моделей процесорів може бути виконано одночасно дві довільні команди, якщо вони не є логічно залежні одна від іншої (Pentium, PA7100, HyperSPARC). У більшості потужних моделей процесорів реалізовано видачу до 4 команд в одному такті (MIPS R10000, UltraSPARC, PowerPC 620).

Видача двох команд в одному такті потребує одночасної вибірки та декодування як мінімум 64 біт. Щоб спростити декодування, можна припустити що команди розташовані парами та вирівняні по границі 64 біт. У противному випадку необхідно аналізувати команди у процесі вибірки та можливо міняти їх місцями при пересилці у цілочисельний АЛП та АЛП з плаваючою комою. При цьому постають додаткові вимоги до схем виявлення конфліктів. У будь якому випадку друга команда може видаватись, якщо може видаватись перша команда. На діаграмі представлена робота двох конвеєрів у ідеальному випадку, коли пари команд можуть виконуватись одночасно:

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