Последната актуализация на този раздел е от 2020 година.

5.3.1 Същност на допълнителните организационни принципи. Паралелизъм

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

Принцип за съвместяване на операциите

Пионер в разработката на едни от най-напредничавите компютърни архитектури, руският академик Лебедев, С. А., още в средата на миналия век предлага и реализира принципа на “съвместените операции”. Този принцип се разбира като съвкупност от две понятия:

· Паралелизъм и ;

· Конвейризация.

Много автори не различават в своите произведения тези две понятия, а те са свързани с два различни подхода. Съвместяването на различни операции чрез паралелизъм се постига чрез насищане на процесора с операционни устройства, включително еднотипни. В тези условия еднотипни операции могат да се изпълняват едновременно (паралелно във времето) от различни копия на едно и също по вид устройство.

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

Паралелизъм, паралелни процеси

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

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

Има процеси, които се явяват и изчезват. Такива процеси имат две крайни състояния – изходно или начално и окончателно или крайно. Има процеси, които са активни непрекъснато. Те нямат крайни състояния. Командният цикъл например е непрекъснат процес. Във вида в който беше представен, той е съставен от последователни процеси (етапи). Няколко последователни процеса могат да се разглеждат като един цялостен процес. Във времето, според състоянията на процесите, същите се характеризират като последователно разположени и паралелно разположени (частично или напълно).

В областта на програмирането се различават:

· Цялостни (пълновесни) процеси (tasks – задачи). Тези процеси имат собствено виртуално адресно пространство и разполагат със собствени и защитени области в оперативната памет ;

· Частични процеси (threads – нишки). Тези процеси не разполагат със собствени защитени области в паметта.

Два паралелни процеса се определят като зависими когато между тях съществува поне едно казуално отношение. Казуално отношение между два процеса съществува, когато преходът към дадено състояние в единия от процесите е възможен при условие, че вторият процес е достигнал и се намира в свое определено състояние.

Зависимите процеси се синхронизират във времето помежду си в дискретни моменти. Това е задължително само в точката на казуалната връзка. В останалото време процесите протичат асинхронно.

Между зависими процеси съществуват в общ план главно два вида отношения:

· Коопериращи отношения, при които два процеса работят паралелно върху обща задача и се синхронизират, като си поделят паралелните дейности ;

· Конкуриращи се отношения, при които два процеса работят върху различни задачи, но в условия на общи ресурси. При едновременен опит за заемане на общ ресурс възниква конфликт.

Между паралелни процеси се налага синхронизиращи отношения в следните разновидности:

· Общ начален старт. Един процес може да бъде декомпозиран на няколко независими паралелни процеса, които стартират едновременно. Процесите могат да протичат с различна скорост и да имат различна продължителност. Преход към следващ общ начален старт е възможен само когато завършат всички паралелни процеси. Тук става дума за изчакване и синхронизиране на началните състояния ;

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

При паралелни процеси с отношения конкуренция, както бе посочено по-горе, възникват конфликти. Съществуват няколко ситуации, които са формално изявени:

· Критичен ресурс. Ресурсът се определя като критичен, ако неговото използване в даден момент е определено (разрешено) само за един процес. Типичен е ресурсът “общи данни”. Критичността, проблемността в този случай се изразява в необходимостта от валидни за всеки процес данни във всеки един момент. Валидността на данните за всички процеси се обезпечава чрез специално управление на достъпа. Широко прилаган е така нареченият семафор. На даден процес е разрешено да използва данните само ако семафорът показва, че те са валидни. В условията на обща оперативна памет и множество процесори с локална буферна (кеш) памет проблемът за достоверността на общите данни се нарича кохерентност и е разгледан в глава 6, пункт 6.3.2.2 ;

· Критична секция. Тази ситуация се характеризира с наличието на обща за процесите част (секция), която се изпълнява без прекъсване от даден процес, при условие че тя е изключена (е невъзможна) за останалите процеси ;

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

За описание на събития свързани с предаване на съобщения между процесите се използва понятието канал. Различават се следните видове канали:

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

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

· Асинхронни канали. Двете операции – тази за предаващия и тази за приемащия процеси са асинхронни, т.е. те завършват изведнъж. Операцията на предаващия процес се изпълнява както в горния вид канал. Операцията в приемащия процес обикновено връща някакво съобщение, указващо как е завършила операцията – било ли е прието или не съобщението. Някои реализации на трансферни операции активизират допълнителни специализирани процеси (съпроцеси), които приемат и отправят съобщения като използват временни буфери и съответни синхронни операции. В този случай се реализира еще една синхронизираща операция, задачата на която е да блокира процеса докато не завършат всички инициирани операции на канала.

При работа на каналите трябва да се следи на не се получи блокада между взаимодействащите си процеси. Типичен пример е ситуацията, когато процес F не може да предаде съобщение на процес G, тъй като последният е в състояние на очакване на съобщение от процес F, за това че той от своя страна е завършил получаването на съобщение от процес G. В по-сложни ситуации такива блокади могат да се разпространят върху циклически зависимости.

Модели на паралелни изчисления

Паралелното програмиране е източник на допълнителни сложности – налага се да бъдат управлявани хиляди процесори, да се координират милиони междупроцесорни взаимодействия. За решаване на една задача върху паралелен компютър е необходимо да се разпределят изчисленията между процесорите така, че всеки процесор да е зает с отделна тяхна част. Необходимо е още да се минимизира междупроцесорния трансфер на данни, тъй като комуникационните операции са значително по-бавни. Често възникват конфликти между степента на разпаралелване и обема на комуникациите. Средата за паралелно програмиране трябва да осигурява адекватно управление на разпределението и на трансфера на данните. Поради сложната структура и организация на паралелните процесори не е възможно да се приложат версиите на традиционните езици за програмиране. Тук ще се задоволим само с изложението на основните модели на паралелното програмиране.

1. Модел Процесс/канал (Process/Channel).

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

2. Модел Обмен чрез съобщения (Message Passing).

При този модел програмите (възможно е да бъдат различни, написани на традиционен последователен език за програмиране) се изпълняват върху отделните процесори на паралелния компютър. Всяка програма има достъп до локалната памет на изпълняващия я процесор. Програмите обменят данни използвайки подпрограми приемане/предаване на данни на отделна комуникационна система ;

3. Модел Пралелизъм на данните (Data Parallel).

При този модел една единствена програма задава разпределението на данните между всички процесори на компютъра както и операциите върху тях. Разпределените данни обикновено представляват масиви. Като правило, езиците за програмиране, поддържащо този модел, допускат операции върху масиви като позволяват изрази върху масиви и/или срезове от масиви. Компилаторът от езика генерира съответния код ;

4. Модел Обща памет (Shared Memory)

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

Паралелно програмиране

Една програма се състои от процеси, които могат да се изпълняват последователно или конкурентно. При изпълнение на програмата в среда за последователно програмиране програмата представлява един процес и резултатите, които тя получава при едни и същи данни са винаги едни и същи, а изпълнението на всяка команда е последователно и независимо от изпълнението на други команди.

При изпълнение на програмата в мултипрограмна среда тя представлява един процес. В такава среда управлението между отделните процеси се предава последователно. Между отделните процеси съществува зависимост по време на изпълнение, но резултатът от изпълнението се запазва.

При изпълнение на програмата в среда за паралелно програмиране тя се състои от множество процеси. Нейният машинен код (текст) освен необходимите, включва още и допълнителни команди за синхронизация и взаимодействие между процесите, които съставят нейния планиращ процес (scheduler). Резултатът от изпълнението на паралелната програма може да зависи от работата на нейния планиращ процес. Процеси, изпълняващи програмата, могат да бъдат алтернативно:

· Реплики – еднакви програми, работещи върху различни данни – модел SPMD (single program multiple data). Синхронизацията между процесите в този модел се извършва на ниво програма (сегмент) ;

· Различни подпрограми – модел MPMD (multiple program multiple data). Отделните процеси при този модел се пораждат като дъщерни на един главен процес.

Средствата за създаване на паралелни програми се различават по начините за задаване на паралелизма – експлицитно или имплицитно, например езици за задаване на паралелизма (FORTRAN90) или компилатори, които разделяйки последователната програма, създават планиращ процес. Езиците за паралелно програмиране имат същите функции като операционните системи – за създаване, координация и обмен между процесите, но са машинно независими, преносими и с по-високи изисквания относно разбираемостта на кода и средствата за настройка. Тези езици представляват обикновено разширение на езиците за последователно програмиране, като съдържат средства за деклариране на общи ресурси и междупроцесни комуникации. Могат да описват цялостни и частични процеси (задачи и нишки). Съдържат средства за изключващ контрол и планиране на последователни процеси. Използват записи и конструкции за описание на паралелизма ИЛИ и използват специален синтаксис, който не налага последователност в конкуриращи се събития.

За разкриване на паралелизма най-често се прилага граф на процесите. Така се изявяват паралелните зависимости по данни и по управление. Графите могат да изразяват процеси на различни нива – блок, израз, променлива. Зависимостите могат да бъдат:

· Зависимост по данни (data flow) ;

· Антизависимост (anti-dependence) ;

· Зависимост по изход (data output) ;

· Зависимост по вход (data input) ;

· Зависимост по управление (data control) .

Типичният паралелизъм по данни се изявява при множествен тип структури – матрици, вектори, характеризиращи се еднакъв тип на елементите и еднакви операции върху тях.

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

При планиране на алгоритмите за паралелна обработка (mapping) се използват различни подходи, но най-често се използват такива, базирани на преобразуване на графи. Планирането на един алгоритъм се извършва за конкретна паралелна архитектура и включва следните задачи:

· Избор на типа паралелизъм – по данни или по управление ;

· Декомпозиция на проблема (определяне на грануларността) ;

· Комплементиране (разпределение процес-възел) ;

· Оценка и минимизиране на междупроцесорните комуникации.

Грануларността е най-вече качествена характеристика на декомпозицията на проблема. Грануларността се определя като:

· Едра – приложима е при паралелизъм по данни и на ниво програма ;

· Средна – приложима на ниво процедура или блок ;

· Фина – приложима на ниво израз или команда.

Краткото изложение по същността на понятието паралелизъм в изчислителния процес, което направихме, показва огромното количество съдържащи се в него различни възможности за организиране на високопроизводителни системи за изчисления. Към настоящия момент максималното оползотворяване на съществуващия в един изчислителен процес паралелизъм се преследва на всички нива – на микрооперационно, на командно, на архитектурно. Докато на последното трудно може да се влияе, то на програмно ниво възможностите са по-гъвкави. Тук се разработват езици за паралелно програмиране, нови компилатори и в обратен ред се търсят и изследват нови по-удобни за програмиста архитектурни структури. В това направление съвременните научни и производствени звена, свързани с компютърните науки, полагат големи усилия. Тук, в тази книга, нашите цели са по-скромни. Като имаме предвид, че организирането и структурирането на различни архитектури за паралелни процесори е самостоятелна тематика, която излиза извън интересите на тази книга, ние не дискутираме нейната същност тук. Част от останалите принципи вече са разгледани в съответно посочените места на тази книга, така че тук остава да се съсредоточим най-вече върху конвейерната организация и свързаните с нея разновидности.

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

5.3.2 Конвейерна организация на изпълнението на машинните команди