3.8.3 Конвейерна организация на операционните структури

Operating structures with pipeline organization

Стремежът към все по-висока производителност поражда най-разнообразни организационни идеи. Идеята за конвейеризация на протичащите процеси възниква още с първите технологични успехи в индустрията. Тя е естествена и се ражда неизбежно у всеки, който желае да използва възможно най-ефективно ресурсите с които разполага. Така например, ако имаме една машина ние бихме желали тя да работи, а не да престоява. Нека си спомним филма “Модерни времена“, в който работникът (Чарли Чаплин) работи в автомобилен завод, където на поточната линия за монтаж той има своя малка задача - да завие и затегне върху автомобилния възел “гайка №5”. Виждаме как работникът стои до конвейера, по който се придвижват автомобилните възли и когато пред него се установи нов възел, завива и затяга гайка №5. През същото време съседите му изпълняват своите операции. След определеното време конвейерът отново придвижва автомобилните възли (които са в различна степен на завършеност) и пред всеки работник се озовава нов възел. Върху новия възел героят на Чаплин трябва да изпълни за пореден път своята операция. Същото правят и неговите съседи. Тази весела филмова картина продължава и случващото се там за нас е много показателно, тъй като има пряко отношение към проблемите, които искаме да осветлим тук.

Търсенето на по-висока производителност на изчислителните структури въз основа на идеята за тяхната конвейерна организация се основава на факта, че протичащият в тях изчислителен процес е структурен процес, чиито елементи са отделните операции. Разбирането на изчислителния процес като структурен процес читателят може да си припомни от §2.1. Нашата задача тук ще бъде да поясним в какво се състои и как се постига конвейерната организация на операционните структури. Ще поясним също така и по какво тя се отличава от вече изложената последователностна организация.

Изчислителният процес, който протича в операционните структури, разгледани в предидущите параграфи, ние представяхме на микрооперационно ниво. На това ниво структурните елементи на изчислителния процес са микрооперациите и свързаните с тях логически възли. Изчислителният процес на микропрограмно ниво се осъществява в операционната част на изчислителните автомати, под непосредственото управление на тяхната управляваща част. Това разбиране за строежа на изчислителните автомати се основава на декомпозицията на Глушков (вижте фигура 2.2.5), според която управляващият автомат издава множество управляващи сигнали към операционната част, а тя от своя страна му отговаря с множество оповестяващи сигнали (флагове). Така изчислителният автомат представлява съвкупност от два елемента, затворени в един кръг чрез права и обратна връзка. На фигура 3.8.3.1 е показан познатият ни от началото на тази глава алгоритъм на операция от тип събиране. Вижда се, че в него има разклонение, в което се проверява признакът КОП. За реализация на този алгоритъм (дясната рисунка) към управляващото устройство, с помощта на отделен проводник, следва да се изпрати значението (логическата стойност) на признака КОП. Изпълнявайки алгоритъма, управляващото устройство ще издаде управляващ сигнал за реализиране на събиране или управляващ сигнал за реализиране на изваждане. Така в един “диалог”, между операционната и управляващата части, протича изчислителният процес.

Фиг. 3.8.3.1. Традиционна представа за изчислителен автомат

Нека в този дух дадем още един пример – фигура 3.8.3.2. Ще припомним, че алгоритъмът на Бут за операция умножение, изискваше изчисляването на две функции – за изместване c_i и за операция s_i. Всъщност това са признаци, които в качеството си на оповестяващи сигнали, се анализират в управляващия автомат, който взема решение за издаване на управляващите сигнали от съответния клон на алгоритъма.

Фиг. 3.8.3.2. Управление с помощта на логическите функции на Бут

Блок-схемата на изказаните микрооперации е илюстрирана на фигура 3.3.8.3.

Фиг. 3.8.3. Алгоритъм на Бут

Чрез изложеното по-горе разбиране за традиционното управление в изчислителните автомати искахме да заострим вниманието на читателя върху факта на диалога, т.е. върху наличието на двустранно насочените сигнали между управляващото устройство и операционната структура. Сега вече е време да кажем, че разбирането за конвейерна организация на изчислителния процес не възприема подобен диалог. Когато казваме, че някакво изчисление се провежда върху един конвейер, обикновено си представяме, че на вход се подават операндите и при тяхното преминаване през отделните степени на конвейера, на изхода му излиза резултат. При това естествената представа за управлението на този процес се свежда до необходимостта от ритмично придвижване на данните (междинните резултати) от степен към степен, в посока на изхода. Обърнете внимание, че в тази представа липсва диалог.

Тук отново е необходимо да поясним защо нашите очаквания от тази организация са положителни. На първо време можем да говорим за интуитивното усещане (убеденост), че веднъж поставили данните на входа на един конвейер, след тяхното “потъване” във вътрешността му, нищо не ни пречи, без да изчакваме резултата на изхода му, да поставим нова порция данни на входа. Естествен е изводът, че ако трябва да изпълним 100 пъти даденото изчисление, то при тази организация ние бихме завършили по-бързо.

Естествено стигаме до въпроса - възможно ли е да се постигне технически тази организация. Отговорът е положителен и той се основава на детерминираната във всеки алгоритъм еднозначна функционална връзка между стойността на всеки флаг и съответстващите й изходни управляващи сигнали [вижте в тази книга §7.1]. Тази функционалност може да бъде реализирана апаратно вместо програмно или с други думи – тя ще се реализира в операционната част на изчислителното устройство, вместо в управляващата. Това означава, че оповестяващите сигнали ще подготвят (автоматично) необходимите условия за изпълнение на съответната микрооперация, а управляващото устройство само ще я стартира в необходимия момент (такт), без да се интересува коя всъщност е тя.

Според изложеното по-горе, конструираното за първия пример решение (фиг. 3.8.3.1), ще изглежда както е показано на фигура 3.8.3.4. Представената рисунка и казаното по-долу се основават на синтезираната в §3.2 логическа структура на устройство за събиране на числа с фиксирана запетая.

Фиг. 3.8.3.4. Конвейеризирано ниво за операции събиране и изваждане

Както виждаме, флагът КОП, който се доставя заедно с операндите от предидущото ниво на конвейера, се използва да определи втория операнд Y, или (-Y), подаван естествено в допълнителен код. Така за управляващото устройство не остава нищо друго освен да запише получения на изхода на суматора резултат, без да се интересува от каква операция е той. В този смисъл управляващият алгоритъм се превръща от разклонен в линеен. Освен това, веднага можем да забележим, че докато четем резултата от изходния регистър, във входните регистри могат да постъпят следващите два операнда. При такова съвместяване на тактовете, процесът на последователни операции от тип събиране, се илюстрира с времедиаграмата от фигура 3.8.3.5.

Фиг. 3.8.3.5. Конвейерно изпълнение на операции събиране

Тази организация се характеризира още с това, че тя води до отпадане на буферния регистър в логическата структура на устройството за събиране и изваждане по десния вход на суматора (вижте фигура 3.2.1.1), при запазване на предпоставките, декларирани в началото на тази глава.

По аналогичен начин ще се приложи конвейерната организация и във втория пример.

Фиг. 3.8.3.6. Конвейеризиране на суматора в устройството за умножение по Бут

Както може да се види от рисунката, стойностите на функциите на Бут са такива, че автоматично и еднозначно определят втория операнд за всяка междинна сума в процеса на умножение. За управляващото устройство в текущия такт остава задачата да подаде управляващ сигнал за запис (с изместване) на новата междинна сума от изхода на суматора в изходния регистър (вижте фигура 3.2.2.1.1). Повтаряйки указаните микрооперации, управляващото устройство изпълнява цикъла на алгоритъма, чието тяло се модифицира от разклонена в линейна структура (вижте по-горе фигура 3.8.3.6).

Разсъждавайки по този начин стигаме до извода, че управляващият автомат може да бъде премахнат от структурата чрез подходяща модификация на операционната част. Не е трудно да се осъзнае, че същността на тази модификация се състои в нейната конвейерна форма на организация. Ако в една операционна структура например, трябва да се изпълнят 4 последователни действия според следния алгоритъм

Фиг. 3.8.3.7. Линейна алгоритмична структура

тя се свежда до следната 4-степенна линейна конвейерна структура, както е показано на следващата фигура 3.8.3.8

Фиг. 3.8.3.8. Линейна конвейерна структура

В структурата се виждат конвейерните регистри (регистри фиксатори) Ф(k), Ф(k+1), Ф(k+2) и Ф(k+3), чието предназначение е да поддържат във времето междинните резултати. Към изходите на регистрите са включени комбинационни операционни схеми К(k), К(k+1), К(k+2) и К(k+3), реализиращи по същество логическа преработка на данните. Съвкупността от регистър фиксатор и комбинационна операционна схема представлява в частност конвейерното звено (степен). Следователно под конвейер ще разбираме последователност от конвейерни звена.

Резултатите от преработката на данните във всяко звено се явяват на изходите на комбинационните схеми и в подходящия момент се записват в следващия регистър фиксатор. Тъй като микрооперация запис на данни в регистър е активна микрооперация, тя се постига чрез нарочно подавани управляващи сигнали УС_k, УС_k+1, УС_k+2 и УС_k+3. Тяхната последователност съответства на алгоритъма, изразен чрез блок-схемата от фигура 3.8.3.7. Тази последователност е пренесена (е реализирана) в логическата структура на конвейера чрез подходящото последователно подреждане на конвейерните звена. Посоката на придвижване или още на хода на изчислителния процес, която в блок-схемата се определя чрез алгоритмичните преходи, в конвейера се указва чрез насочените даннови връзки.

Конвейерната структура се характеризира с особен вид организация на функциониране, която се нарича също конвейерна. Конвейерната организация на функциониране е особен вид паралелно във времето функциониране на структурните елементи в конвейера. Функционирането се определя като паралелно поради липса на функционални връзки, които да влияят върху работата на отделните комбинационни схеми. При тази организация в отделните степени конвейерът изпълнява изчислителен процес върху множество задачи, но с различни начални данни. В конвейера тези задачи се намират в различна степен на завършеност. Ако конвейерът има 4 степени, това означава, че в него са заредени и се изпълняват 4 задачи. В един и същи момент в различните степени на конвейера се изпълняват изчисления върху тези различни задачи. Придвижването на задачите в конвейера е последователно от звено в звено при спазване на реда.

Основният параметър, характеризиращ конвейерната структура, е оценката за неговата производителност, в сравнение с последователното незастъпващо се във времето изпълнение на същия брой задачи. В условията на линеен алгоритъм от m на брой такта, получаването на резултат за една конкретна задача изисква същия брой тактове. Тогава за последователното изпълнение на n задачи ще са необходими Т_П=(n.m) на брой такта, ако приемем продължителността на един такт условно за константа единица. Ако същият брой задачи биват последователно зареждани за изпълнение в един m-степенен линеен конвейер от вида, показан на фигура 3.8.3.8, необходимото време за тяхното изпълнение ще се оцени така

Производителността Р ще оценим чрез отношението на продължителностите на изчислителния процес за двата варианта

За горната оценка твърдим, че има стойност, която клони към числото m, с нарастване на броя на изпълнените задачи

Резултатът (3.8.3.3) означава, че m-степенната конвейерна организация е m пъти по-производителна от последователната организация на изпълнение!

Управлението на конвейерната структура изисква единствено подходящо тактуване, при което резултатите, получени от едно звено, ще се предават като входни данни към следващото звено. Това тактуване може да бъде реализирано като общо и синхронно, с еднофазов тактов генератор (вариант Б) на фигура 3.8.3.8 или с многофазов (4-фазов) тактов генератор 4ФТГ (вариант А) на същата фигура). Синхронното управление може да има разнообразни реализации, които зависят от вида на тригерите, изграждащи регистрите фиксатори. Алтернативният вариант е асинхронно управление, което се постига с различни конвейерни автомати.

Освен последователната структура за изпълнение на операция умножение, която се характеризира с това, че съдържа само един суматор, тук (в пункт 3.2.5.5) бяха разгледани подходи за изграждане на еднотактни (схемни) умножители. Поради изключителната си сложност обаче (вижте книга [3] фигура 4.12), тези комбинационни схеми се характеризират със собствено време за превключване, което е в значителен дисбаланс спрямо типичното време за превключване на останалите логически възли. Под типично време за превключване обикновено се приема времето за изпълнение на микрооперация “запис в регистър”. В смисъла на конвейерното организиране на изчислителния процес, включването на такъв бавен логически възел като отделна степен на конвейера, сериозно възпрепятства ритмичното управление на последния. Ето защо, при известно отстъпление в бързодействието, с цел постигане на споменатата ритмичност, в схемния умножител могат да бъдат вмъкнат регистри - фиксатори на междинните суми. Така умножителят би имал например общата структура, показана по-долу на фигура 3.8.3.9. От фигурата може да се заключи, че записвайки междинните суми, фиксаторите така да се каже, “подравняват редиците” на придвижващите се към изхода междинни суми. С това се постигат различни ефекти. Освен ритмичност, появява се например, възможност да бъде преустановен процесът на умножение като се спре подаването на управляващите сигнали за запис. Поради големият брой нива в този конвейер, в него могат да бъдат стартирани последователно няколко операции умножение, така, че на всеки такт да излиза произведение, и в това се вижда възможността за повишаване на производителността като цяло, въпреки, че бързодействието на така структурирания умножител е понижено по сравнение с възможностите на комбинационния (еднотактен) умножител.

Фиг. 3.8.3.9. Конвейеризиране на схемен умножител с междинни фиксатори

Представената структура се характеризира още с това, че нейното управление е изключително опростено. Цикълът в алгоритъма за умножение от фигура 3.8.3.3 с комплексно условие в тялото, което се превърна в линейна структура (вижте фигура 3.8.3.6), в този последен вариант (фигура 3.8.3.9) изчезва като такъв. Може да кажем, че структурата реализира разгънат цикъл. Управлението на тази напълно конвейерна структура за умножение се свежда до едно синхронно тактуване (стига то да е разрешено), при това без всякакъв интерес към ставащото в отделните степени на конвейера. При всеки такт на изхода се получава ново произведение.

Ще приведем още един пример за конвейерна организация в операционните структури. Примерният конвейер, който ще изясним по-долу, е за обработка на числа представени във форма с плаваща запетая. Така читателят ще може да го сравни със синтезираната в пункт 3.3.5.2 логическа структура. Ще може да се види, че липсват обратните връзки от изходните към входните регистри; появяват се допълнителни регистри-фиксатори на междинните резултати; операндите постъпват във входните регистри и се движат от ниво към ниво в посока към изходните регистри; отделните нива съответстват на етапите по хода на алгоритъма; а самият алгоритъм за управление се свежда до синхронно придвижване на данните между отделните нива.

В нулевото ниво на конвейера (фигура 3.8.3.10) се намират входните регистри за операндите. Функционалността на първо ниво се реализира от суматора СМ1 и комбинационната схема КС1 Суматорът е длъжен да получи модула на разликата от порядъците, който инициализира програмируемата изместваща матрица ПИМ1 на следващото ниво. Схемата КС1 трябва да преобразува мантисите в необходимите машинни кодове и да изведе на левия си изход кода на мантисата с по-големия порядък (при операция от тип събиране). Мантисата по десния изход на КС1 се денормализира чрез ПИМ1. На това ниво се намира още мултиплексорът MUX, с помощта на който се избира по-голямата от двете характеристики като неокончателна стойност на характеристиката на резултата. Многофункционалната комбинационна схема на третото ниво, наречена АЛУ, се инициализира от управляващата комбинационна схема на конвейера. Тази схема определя и знака на резултата.

Функционалността на последното ниво се реализира от програмируемата изместваща матрица ПИМ2, с помощта на която се нормализира и закръгля мантисата на резултата. Параметрите за нормализацията се определят в дешифратора на старшите незначещи цифри ДСН. Схемата ДСН определя и корекцията W, а суматорът СМ2 получава окончателната стойност на характеристиката на резултата Z. Резултатът се сглобява в изходния регистър.

Схемите за формиране на признаците на резултата не са показани на фигурата.

Фиг. 3.8.3.10. Конвейер в устройство за работа с ПЗ

Не е необходимо да даваме други примери за да направим първите изводи от изложената концепция за конвейерна организация в операционните структури, а те са следните:

· Реализираните в операционните структури оповестяващи логически функции, изчисляват стойности, които в качеството си на признаци, определят хода на изчислителния процес, т.е. реализират разклоненията. Микропрограмната проверка обаче на тези стойности може да се замени с апаратна, резултатите от която могат да се използват за подготовка на двата алтернативни резултата в логическата структура;

· Опростяват се и се ускоряват микропрограмите, тъй като от тях отпадат условните преходи и съответните участъци в тях стават линейни. В резултат на това се опростяват структурите и функционалните възможности на микропрограмните управляващи устройства;

· В повечето случаи се налагат изменения и значителни допълнения в логическите структури на операционните устройства, свързани с промените в алгоритъма. Особено явно се откроява отстраняването на обратните логически връзки, с помощта на които се образуват натрупващи възли, както и въвеждането на допълнителни регистри-фиксатори;

· Благодарение на възможностите на съвременните технологии, като водещ за конструкторите критерий се определя изискването за висока производителност пред традиционно конкуриращия го критерий за минимум апаратни разходи.

В заключение можем да кажем, че в случая на безкрайно следващи една след друга еднотипни операции, изпълнявани в операционно устройство с конвейерна организация от k на брой нива, изчислителният процес би имал k пъти по-висока скорост в сравнение с изпълнението му върху устройство без конвейерна организация. Повишаването на скоростта се дължи на факта, че в устройството с конвейерна организация във всеки един момент (такт) се съдържат (т.е. са стартирани) k на брой операции, намиращи се в различни фази на завършеност. Това разбира се е идеализиран случай. Както читателят знае, изчислителният процес не е последователност от еднотипни операции и това естествено е източник на проблеми за конвейерната организация. Тези проблеми водят до усложняване на алгоритмите за управление на конвейерите. Нека например си представим ситуация, при която по някакви причини на входа на конвейера, подаването на операнди се забавя или е невъзможно да стане в текущия регулярен такт от управлението му. Това означава, че придвижването на всички данни във вътрешните нива на конвейера следва да се прекрати. Ако все пак тактуването продължи, заредените вече данни ще продължават да се придвижват от ниво към ниво, а от изхода ще излизат последователно на всеки такт съответните резултати. Ако нивата на конвейера са k на брой, след също толкова такта, от изхода му ще излязат k на брой резултата. В същото време всички нива, започвайки от входното към вътрешността на конвейера, ще се окажат “изпразнени от съдържание” или по-точно ще съдържат неактуална информация, тъй като на входа по време на тези тактове не са постъпвали данни. По тази причина във вътрешността на конвейера не са получавани смислени резултати. Така в резултат на този анализ се изявява необходимостта управлението на конвейера да се съобрази с тази възможна ситуация. Възможностите за адекватно управление по-принцип са две:

· или да се организира спиране на конвейера в буквалния смисъл, например чрез прекратяване на тактуването му;

· или, ако тактуването продължи, на изхода да се различават два вида резултати:

- актуален резултат;

- неактуален резултат.

И в двата случая в крайна сметка е на лице снижение на производителността.

Управлението на конвейерно организираните операционни структури надскача конкретната тема и е въпрос, който засяга тяхното проектиране, а последното не е обект на тази книга. Тези проблеми са разгледани от автора отделно и са изложени в книга [5]. Все пак можем да посочим следния аспект – от изказаната по-горе идеализирана представа следва тривиалният извод, че на колкото повече нива може да се конвейеризира алгоритъма на една операция, на толкова по-голяма производителност може да се разчита. За съжаление с нарастване броя на нивата в конвейера расте и вероятността за неговото спиране, което се дължи на нарастване на вероятността за зависимост между стартираните в него операции. Става дума за зависимост на дадена операция от резултата на предидуща операция, който тя трябва да използва в качеството му на операнд. Ето защо повишаването на производителността на конвейеризираното операционно устройство не е в права пропорционална зависимост от броя на нивата. Като един от малкото конкретни примера дадени в тази книга, ще посочим, че конвейерното АЛУ на Compaq Alpha 21064 има 2 нива, а това на Intel Pentium 4 – 20 нива. Тези параметри не са постоянни – моделите микропроцесори остаряват, появяват се нови, но при тяхното изучаване, а защо не и при тяхното проектиране, читателят ще бъде “въоръжен” с изложената тук непреходна фундаментална философия.

Както вече стана дума по-горе, допълнителен затормозяващ управлението на конвейерите фактор представляват различните времеви закъснения в логическите възли на отделните нива. Обикновено, при синхронен метод на управление, тактовата честота на конвейера се избира така, че типичната за АЛУ операция да завърши в рамките на един обобщен такт. Така по-продължителните операции се изпълняват в последователност от няколко такива такта.

Обръщаме внимание на читателя, че разгледаната в този пункт конвейерна организация, не е изчерпана по съдържание. Тук беше представена философията на тази най-стара форма на паралелизъм. В тази книга отново ще се говори за конвейрна организация, когато пренесем вниманието си на по-горното ниво – нивото на машинните команди, където се изявяват други проблеми, които ще бъдат разглеждани по-късно. А с проблемите и със синтеза на най-разнообразни конвейери, читателят може да се запознае като разгледа представената в този сайт книга [5].

Следващият раздел е:

3.8.4 Апаратно насищане ( Hardware concentrate )