Въведение в паралелната обработка- Част 2

- Секция Компютри
5. Класификация на паралелните компютри

Всяка класификация трябва да притежава следните качества [10]:
а) Възможност да класифицира всичките съществуващи компютърни архитектури, а така също и да предвиди нови такива.
б) Диференциация на съществено различните изчислителни структури.
в) Еднозначна класификация на всеки компютър.
 
В голяма част от съществуващите схеми за класификация тези правила не са изпълнени. Някои твърде груби категории, използвани в такива схеми, не позволяват да се включат някои достатъчно жизнеспособни структури и еднозначно да се класифицират различните форми на конвейеризация.
 
· Класификация на Флин [2,4,10]. Една от първите и все още най-популярна класификация на компютрите е предложена от Флин през 1966 г. Класификацията на Флин се базира не на структурата на компютъра, а на това как в компютъра командите се обвързват с обработката на данните. Флин въвежда понятието поток и го дефинира така: последователност от елементи (данни и команди) изпълнявани или обработвани от процесорите. Във всеки компютър има два основни потока - единият от команди, а другият от данни. При срещата им се извършва обработка над данните.
В съответствие с това дали потоците от данни или команди са единични или представляват множество, възникват и следните четири големи класа:
 
SISD (Single Instruction Stream, Single Data Stream).
В този клас влизат обикновените фон Ноймановски компютри, които имат един поток команди и един поток данни, т.е. едно устройство за обработка на командите и едно изпълнително устройство (АЛУ).
 
SIMD (Single Instruction Stream, Multiple Data Stream).
В тези компютри се съхранява един поток от команди, но вече той е векторен, който инициира многочислени операции. Всеки елемент на вектора се разглежда като елемент на отделен поток от данни. В този клас се включват всички компютри с векторни команди, например CRAY-1, CRAY-2, CRAY X-MP, CRAY CS 6400, ILLIAC-IV, DAP на ICL, OMEN -64 и т.н.
 
Преди да се посочат проблемите на SIMD компютрите, трябва да се подчертае, че понятието "процесор", което е еднозначно определено при компютрите с фон Ноймановска архитектура, при паралелните компютри е размито. Различни автори [2-12], много често под понятието "процесор" включват различни по сложност компоненти, започвайки от прост изчислителен елемент, изпълняващ само основните аритметични операции, без възможност за извличане и декодиране на командите и достигат до напълно самостоятелен и независимо функциониращ компютър. В контекста на изложението на конкретна архитектура става ясно какви са функционалните изисквания на процесора.
Флин посочва следните проблеми, възникващи при разработката на SIMD компютрите:
 
а) Поддържане на комуникация между изчислителните елементи (процесори).
б) Необходимост от съответствие между размера на вектора от данни и размера на масива от процесори, който ще обработва този вектор.
в) Наличие на невекторни операции в програмите и появяване на допълнителна работа, свързана с подготовка за изпълнение на векторни операции.
г) Бездействие на голяма част от процесорите при наличие на условни преходи в програмата.
Решаването на една голяма част от тези проблеми се дискутират по-подробно в теми 7, 8, 12 и 13.

MISD
(Multiple Instruction Stream, Single Data Stream).
Към този клас компютри се отнасят компютри с множество потоци от команди и един поток от данни. Единствената архитектура, която с някакво основание може да бъде отнесена към този клас е конвейерната и то при условие, че всеки етап от изпълнението на командата се счита за една отделна команда. Но много по-естествено е да се отнесат конвейерите към класа SIMD. Действително самият конвейер може да се счита като система с архитектура MIMD, а по отношение на векторните операции той напомня архитектурата SIMD.

MIMD
(Multiple Instruction Stream, Multiple Data Stream).
Множеството потоци от команди означава съществуването на няколко устройства за обработка на командите в този клас компютри. Затова тука се включват всички форми на мултипроцесорни конфигурации - от обединени компютри до матрици от процесори. В конфигурациите са включени няколко независими и завършени (пълноценни) еднопроцесорни компютри, които в процеса на решаване на задачите контактуват помежду си чрез съобщения или използват обща памет. Тъй като всеки от процесорите има свое управляващо устройство и може да изпълнява собствена програма, то за даден момент от време отделните процесори имат възможност да изпълняват различни операции върху различни данни.

Следните проблеми са общи за всички MIMD компютри:
а) Необходимост от препращане на данни и команди между процесорите. Тези операции обикновено поглъщат много време и за тяхното осъществяване е необходима (в повечето случаи сложна и скъпо струваща) комуникационна мрежа.
б) Цената се повишава линейно (в най-добрия случай) с увеличаване на броя на процесорите, докато скоростта на обработка се повишава много по-бавно поради увеличаване на броя на конфликтите между процесорите, използващи общи ресурси.
в) Осигуряване на методи за динамична реконфигурация на ресурсите на системата за задоволяване на постоянно променящите се изисквания и заетост на процесорите.
Отново решаването на част от проблемите е дискутирано по-подробно в теми 9, 10, 12 и 13.

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

За подобряване на класификацията са се предлагали различни допълнения и изменения на основната Флинова класификация. Едно от тях използва два нови признака, отчитащи разрядната и символната обработка. Така се получават 8 класа - четири класа за обработка по думи и четири класа за обработка по битове. Това схематично е показано на фиг.3-4.
Друг опит е направен от Foutain [11] и отчита такива особености на архитектурата на паралелните компютри като типа на автономията (операционна, адресна и мрежова), топологията на свързване на процесорите и форматът на данните - Таблица 1.

Операционна автономия.

 
Осигурява в архитектура с масов паралелизъм възможност за изпълнение няколко различни операции върху мрежа от процесори. Това съвсем не означава, че всеки процесор работи по своя собствена програма, както при компютрите от тип MIMD; просто това означава, че не всички процесори изпълняват една и съща команда както е в традиционните SIMD компютри. Това се постига чрез:


Фиг.3-4. Разширена класификация на Флин, отчитащ начина на обработка - по думи (W) или по битове (B)
 
· Техниката на маската. Чрез техниката на маската се реализират преходи в паралелната програма. Този въпрос е разгледан по-подробно в тема 8.
· Освен бит за активност (както е в CLIP7) се използва многоразряден регистър, който може да се разглежда като регистър на разширения код на операцията. Благодарение на това, всяка команда се интерпретира по-различен начин от всеки процесор.
· В паралелните компютри MSIMD (Multiple SIMD) има няколко блока за програмно управление (програмни контролери), всеки от който е свързан с определена група процесори (кластер). Такъв тип операционна автономия е реализиран, напр. в йерархичните архитектури с пирамидална топология . Всяко ниво се управлява от отделен контролер, благодарение на което процесорите от едно ниво работят в режим SIMD, но на различни нива се изпълняват различни програми.
 
Адресна автономия.
 
Осигурява на всеки процесор в SIMD компютъра възможност за формиране адреса локално или да модифицира получения адрес, независимо от другите процесори. Така може да избере операнд от собствената памет по адрес, отличен от адреса на другите процесори. Тази автономия отдавна е призната за важна, защото тя същевременно облекчава програмирането на SIMD компютрите, трудността при които се заключава в необходимостта от обръщение на всички процесори към една и съща клетка от паметта при изпълнение на една и съща команда.
 
Мрежова автономия.
 
Това е принцип на организация на изчисленията, имаща за цел ефективно отразяване на графа на задачата (породен от даден алгоритъм за изпълнение) в структурата на връзките между процесорите. При това се преследват същите цели, както и в компютрите с реконфигуруема комуникационна мрежа , а именно осигуряване висок коефициент на използване на ресурсите.
 


Разбира се, съществуват и други способи за класификация на компютрите с паралелна архитектура несвързани с тази на Флин, а именно класификация по функционално предназначение, по способа на управление, по степен на свързаност на отделните процесори в компютъра, по степен на равноправие и т.н.
· По функционално предназначение се отделят две направления на развитие:
 
а) Създаване на компютри за изпълнение на различни инженерни разчети, основно ориентирани на бързо изпълнение на аритметични операции.
б) Създаване на компютри за системи с изкуствен интелект и бази знания.
 
· По способа за управление на паралелната работа се отделят три класа компютри:
а) С управление по потока управляващи оператори (control driven).
б) С управление по потока данни (data driven).
в) С управление по потока заявки (demand driven).
 
В компютрите от първия тип всяка изпълняема команда определя следващата подлежаща на изпълнение команда. В компютърът с управление по потока данни, наличието на необходимите аргументи стартира изпълнението на командата, използваща тези аргументи. В компютрите с управление по заявки, командата се изпълнява, когато нейния резултат е нужен за изпълнение на друга команда. На тези въпроси е посветена тема 11.
 
От посочените три класа компютри най-голямо разпространение са получели тези от първият клас. В зависимост от степента на независимост на работата на отделните процесори, тези компютри се подразделят два типа архитектури - архитектура от тип SIMD и архитектура тип MIMD. Типични представители от първия тип се явяват различните матрични процесори, използвани за научни и инженерни изчисления. Компютрите с архитектура MIMD, в която всеки процесор в съответствие със своя програма обработва свой поток от данни, притежават значително по-голяма мощност и гъвкавост, отколкото компютрите с архитектура тип SIMD.
 
· Класификацията по степен на свързаност на процесорите е показана схематично на фиг. 3-5.
В силно свързаните системи, процесорите (два или повече) са обединени в обща шина. При наличието в системата на един или два специализирани процесори, интензивния обмен на данни по локалната шина между процесорите не води до забележимо снижаване на производителността на системата. Но при увеличаване броя на процесорите, локалната шина става тясно място в системата. Използването на двувходови памети, свързани с единия си вход към локалната шина, а с другия към системната шина позволява до известна степен да се снизи интензивността на обмена на данните по локалната шина. При добро балансиране на интензивността на обмен на данните чрез двата входа и използването на прости алгоритми за разпределение на натоварването между процесорите, такава архитектура се оказва достатъчно ефективна.


Фиг.3-5. Класификация по степен на свързаност
 
Ако интензивността на потока данни между оперативната памет и "своя" процесор съществено превишава интензивността на потока данни между тази памет и другите процесори в системата, по-ефективно се оказва използването на система, състояща се от множество автономни компютъра, всеки от които работи под управлението на собствена операционна система. А най-слабо свързана система се състои от множество компютри, обединени от локална мрежа, информацията по която с предава във форма на пакети или съобщения.
 
· Класификация по степените на равноправие на процесорите е друга възможна класификация. В "автократичните" системи един от процесорите изпълнява ролята на управляващ (главен), а останалите - спомагателни функции. В "егалитарните" системи всички процесори са равноправни и всеки от тях може да започва изпълнението на нов, активен процес.
· Съществуват също така класификации и по способа на синхронизация на процесорите. Необходимо е да се отбележи, че синхронизацията може да бъде на различни нива - напр. на ниво команди или на ниво процедура и т.н.
 
В заключение трябва да се каже, че съществуват изключително голямо разнообразие от класификационни схеми и един и същ паралелен компютър може да се окаже в различни класове в зависимост от избрания параметър за класификация.
 
6. Разпределена обработка.
Отделно разглеждане заслужават и изчислителните мрежи, които се създават от териториално обособени центрове и могат да образуват разнообразни изчислителни схеми. Изчислителните центрове функционират автономно и взаимодействат помежду си чрез канали за връзка. Изчислителните мрежи се отличават съществено от другите типове паралелни изчислителни системи и имат ярка изразена специфика както по отношение на организацията на функционирането, така и по отношение на програмното осигуряване.
 
Различието между разпределените изчислителни системи (дискутирани в тема 11) и изчислителната мрежа е въпрос, свързан с разположението и функционирането на възлите, а също така и на начина на взаимодействие между отделните апаратни и програмни ресурси. Ако всичките компоненти на системата са относително зависими и локализирани, т.е. те могат да се считат като части на едно цяло, системата е разпределена такава. Ако компонентите са достатъчно сложни и независими, те се разглеждат като различни машини (компютри). Посредством канали за връзка и съответно апаратно и програмно осигуряване може да се изгради мрежа от изчислителни машини. Подобна мрежа също притежава разпределен изчислителен ресурс, но той не е локално разположен.
 
Първите опити за така нареченото "разпределено изчисление" датират от 70-те години на миналия век, когато започват да се създават първите мрежи от компютри [12]. Идеята е проста - множество компютри (няколко милиона), включени към някаква мрежа (напр. Интернет) да бъдат натоварени с решаването на една задача представляваща глобален интерес за цялото човечество - напр. намирането на извън земен разум. Това се осъществява чрез специално създадена програма, натоварваща процесорът, когато той е свободен. Тя е с максимално нисък приоритет и се активира единствено когато процесорът бездейства. Тя е невидима за потребителя и фактически не се отразява върху работата на компютъра. Освен това, в общия случай не оказва почти никакво влияние върху мрежовия трафик.
 
Информацията, която трябва да бъде обработена, се намира на сървъри в Интернет [13]. След като програмата установи връзка с Интернет, тя поема част от задачата по обработката. Общата задача се разпределя между отделните компютри, които са се включели в проекта - всеки от тях извършва самостоятелни изчисления, различни от изчисленията на другите компютри, и изпраща обратно резултатите си и взема нови задачи при всяко включване в Интернет. При това не е необходимо компютрите да бъдат през цялото време свързани в мрежата.
Кога е удачно да се използва "Интернет компютър" и кога суперкомпютър? Отговорът е прост: когато задачата е ограничена по размери е по-добре да се използва разпределена обработка, а когато е ограничена по време - централизирана.

Съдържание:
Въведение в паралелната обработка Част 1





Коментирай свободно: