Комуникационни мрежи- Част 1

- Секция Компютри
1. Въведение

Една от особеностите на паралелните компютри е необходимостта на обмен на информацията между процесорите за да се получи крайното решение на задачата. За целта се използува комуникационна мрежа (КМ), от чиито характеристики до голяма степен зависи общата производителност на паралелния компютър. Недостатъчното бързодействие и/или ограничените комбинационни възможности на КМ могат съществено да снижат очаквания паралелен ефект. Съществуват два основни подхода за съкращаване на комуникационните загуби:
 
· За сметка на оптимално разпределение на решаваната задача (код и данни) по процесорите и/или по модулите памет.
· За сметка на повишаване на скоростта на работа на самата КМ.
 
Първият подход е обект на изследване при конструирането на паралелните алгоритми и поради това по-нататък няма да се дискутира, независимо от тясната връзка между паралелната архитектура и паралелния алгоритъм. Вторият подход, от своя страна също се реализира по два начина:
 
· Чрез апаратни средства с използването на по-бързодействаща логика.
· Подходяща структурна организация на КМ.
 
От гледна точка на архитектурата на паралелния компютър именно последния подход представлява най-голям интерес, ето защо по-надолу ще се разглежда само този подход. Ясно е обаче, че на практика трябва да се намери общ баланс между посочените по-горе подходи, за да се изгради КМ с най-висока ефективност.
 
В общия случай КМ представлява MxN многополюсник, входните M полюси на който са присъединени към предавателите, а изходните N полюси - към приемниците. КМ се изграждат от комутиращи елементи (КЕ) и линии за връзка (ЛВ). С помощта на КЕ се осъществява свързването на ЛВ и така се осигурява път за предаване на информацията. По-нататък ще се разглежда само случая когато M=N.
 
КМ могат да осигуряват комутация:
· по пространство;
· по време.
 
Характерен признак на КМ с комутация по пространство е наличието на индивидуални ЛВ между източниците и приемниците на информацията. При едновременна работа на няколко източника, за всеки от тях се формира принадлежащи само на него ЛВ, свързващи го с приемника и така се установява индивидуалното съединение. Типичен представител на този клас КМ е матричния превключвател (cross-bar мрежата)и свързването всеки с всеки (пълно свързаната мрежа) - фиг.12-1.. За този клас КМ е характерно висока сложност - О(N2) и малко време за трансфер - O(1). За големи стойности на N този тип КМ става прекалено скъпа.
 
При КМ с комутацията по време, източниците и приемниците са свързани с обща линия, като всяка двойка предавател-приемник я заемат по различно време. Типичен представител на този клас КМ е шината. За този клас КМ е характерно ниска сложност - O(1) и голямо време за трансфер - О(N).
 


Фиг.12-1. Типични представители на КМ по пространство:
 
Стремежът да се съчетаят положителните страни на двата класа КМ води до трети клас КМ с комутация по пространство и по време.
 
2. Характеристики на КМ
 
КМ могат да бъдат характеризирани по решаването на четирите основни въпроса:
· режим на работа;
· стратегия на управление;
· метод на превключване;
· топология на мрежата.
 
Режим на работа. Два типа КМ могат да бъдат посочени: синхронна и асинхронна. Синхронна комуникация е необходима за процеси, в които комутационните връзки са установени синхронно за транслационно предаване на данни (команди) или предаване на функции за обработка върху данните. Асинхронна комуникация е необходима при множество процеси, за които връзките се създават динамично. КМ може да бъде проектирана така, че да улеснява и двата режима. Следователно има три режима на работа - синхронен, асинхронен и комбиниран.
 
Стратегия на управление. Чрез комуникационни функции, специфични за всяка КМ, се определя пътят за свързване между i-тия вход и j-тия изход на мрежата. Тези комуникационни функции влияят върху състоянието на КМ. В зависимост от това къде се изчисляват тези комуникационни функции, управлението може да бъде централизирано и децентрализирано. В първият случай има специално устройство, което управлява превключванията в мрежата. Във вторият случай такова устройство няма, а самите КЕ извършват необходимите изчисления. Последната технология се нарича още разпределено управление.
 
Превключваща методология. Има две методологии - схемно превключване (канал) и програмно превключване (пакетно превключване).При схемното превключване физическия път е действително установен между източника и приемника. При програмното превключване данните се поставят в пакет и се предвижват през КМ без да се установява физически път. Обобщено схемното превключване не е много подходящо за предаване на голям обем от данни, а програмното превключване - при къси съобщения.
 
Мрежова топология. КМ може да бъде описана като граф, чийто върхове съответстват на КЕ, а дъгите - на ЛВ. Мрежовата топология се явява ключов фактор в определянето на възможностите на КМ от гледна точка на архитектурата, затова на нея ще се спрем по-подробно.
 
3. Топология на КМ
 
Топологията на КМ бива; регулярна и нерегулярна. В паралелните компютри намира приложение само регулярната топология, ето защо по-надолу се разглежда само тя. От своя страна, топологиите, които са регулярни биват статични и динамични.
 
3.1. Статични комуникационни мрежи
 
Статичните комуникационни мрежи (СКМ) осигуряват непосредствена връзка само между строго определени компоненти на мрежата. Връзки с останалите компоненти се осигуряват индиректно. Като правило СКМ работят с комуникация на пакети, при което процесорите играят ролята на КЕ. СКМ биват едномерни, двумерни, тримерни,… многомерни. На фиг.12-2 са дадени някои примери на най-често срещаните СКМ.
 
За сравнителна оценка на различните топологии СКМ се използват най често следните параметри:
 
Брой на върховете в мрежата - N.
Това на практика е броя на процесорите в паралелния компютър.
 
Диаметър на мрежата - D.
Дефинира се като максималното разстояние между произволна двойка върхове в пътя свързващ двата върха. В случая под разстояние се разбира минималния брой на дъгите, свързващ двата върха. Например, за СКМ тип "кръг" от фиг.12-2б, D=4, a за СКМ тип "решетка" - фиг.14-2в, D=6 и т.н.
 
Средно разстояние - P.
Определя се като средно разстояние на пътищата от всеки връх до всички останали върхове, при предположение, че с еднаква вероятност всеки връх може да бъде предавател, а всички останали - приемници.
 



Фиг.12-2. Примери на статични комуникационни мрежи.
 
Натовареност на линиите за връзка -Т.
Определя се като брой съобщения за единица време върху една линия за връзка, т.е.
T = NxP/(общ брой на линиите за връзка в мрежата).
 
Относителна структурна сложност -U.
Това е броят на линиите за връзка отнесени за един връх. Когато U=const и не зависи от N, нарастването (намаляването) на СКМ се постига чрез просто добавяне (отнемане) на еднотипни КЕ (процесори). От гледна точка на технологията това е изключително примамливо, защото дава възможност за намаляване на общата цена на КМ, чрез използуване на унифицирани компоненти (процесори).
 
Отказоустойчивост на КМ.
В много случаи е важно КМ да съхранява работоспособността си в условията на отказ на отделните компоненти. За тази цел е необходимо да съществуват алтернативни пътища между произволна двойка предавател-приемник, за да бъде заобиколен отказалия компонент. Това напр. е възможно в топология "решетка", но не и в топология "кръг" или "двоично дърво".
 
За някои от КМ съществуват аналитични изрази за определяне на основните параметри, най-вече на D - виж таблица 12-1, но за по-голямата част от тях определянето им се реализира чрез използуването на известен алгоритъм за намиране на пътищата в граф, напр. на Форд или Дейкстра.
 
 
Ако се придържаме към оптималната маршрутизация на пакетите, то времето за обмен в мрежата е О(D). Във връзка с това, от изключителен интерес е задачата за построяване на плътни графове, съдържащи (при зададени D и U) максимален брой върхове - Nmax.
 
3.2. Динамични комуникационни мрежи
 
Динамичните комуникационни мрежи (ДКМ) дават възможности за промяна на комуникационните връзки посредством реконфигурация на активните КЕ. Те осигуряват директна връзка между компонентите на паралелния компютър и са еднакво подходящи както за схемна комутация, така и за пакетна комутация. ДКМ могат формално да се обозначат като F:{N}{N}, което се тълкува като размяна F на множеството размествания {N} от N елемента. ДКМ биват [3]:
 
· едностъпални
· многостъпални.
· матричен превключвател
 
Едностъпалните мрежи - фиг.12-3, се наричат още рециркулационни, тъй като при реализация на информационния обмен може да възникне необходимост съобщенията да циркулират многократно през стъпалото до достигане на местоназначението.
 


Фиг.12-2. Едностъпална КМ 8х8 от тип shuffle-exchange
 
Като правило, едностъпалните ДКМ намират приложение при изграждането на по-сложните, многостъпални мрежи.
Многостъпалните мрежи осигуряват пълна система на връзките в рамките на паралелната структура. Те от своя страна се разделят на:
 
· едностранни
· двустранни.
 
Едностранните мрежи използуват двупосочни ЛВ, а двустранните имат входна страна и изходна страна. Последните от своя страна се разделят на блокиращи, неблокиращи с реконфигурация и напълно неблокиращи.
В блокиращите ДКМ независимото присъединяване на повече от една двойка предавател-приемник може да предизвика конфликт в използуването на мрежата за друга двойка предавател-приемник. Най-известни представители на този тип ДКМ са манипулатор, делта, омега, флип и др. Напълно неблокиращите ДКМ, както подсказва името им, не страдат от този недостатък. Примери за такива мрежи са мрежата на Клос и пълносвързаната мрежа. В неблокиращите мрежи с реконфигурация също е възможна реализация на съединенията между произволна двойка предавател-приемник, но за това е необходимо да се измени маршрута на връзките за съединените вече двойки терминали. Примери за такива мрежи са мрежата на Бенес, битоналната мрежа и др.
 
Построяването на многостъпални КМ е свързано с необходимостта от използуване на по-прости (в структурно отношение) КЕ. При това за намаляване на апаратната част трябва да се "плати" с увеличаване на задръжките при предаване на съобщенията през k на брой стъпала и с усложнен алгоритъм за управление. Модел на двустранна ДКМ при k=3 стъпала е показан на фиг.12-4.
 


Фиг.12-4. Обобщен модел на многостъпална КМ.
 
Първото (входно) стъпало се състои от r1 комутатора с размерност n1xm (при това r1xn1=N), междинното стъпало се състои от m комутатора с размерност r1xr2 и последното трето стъпало (изходното) се състои от r2 комутатора с размерност mxr2 (при това r2xn2=N).
 
Връзките между КЕ в различните стъпала се определят от вътрешно системните функции за връзка, които в крайна сметка дефинират и различните видове ДКМ (мрежа на Клос, мрежа на Бенес, омега мрежа, делта мрежа, сигма мрежа, Мемфис мрежа и т.н.).
 
В матричния превключвател всеки вход се свързва с всеки свободен изход без блокиране фиг.12-1а. Той използва N2 КЕ. Времето за задръжка на сигнала между входа и изхода се определя само от задръжката на един КЕ.
За оценяване на различните топологии ДКМ се използват най-често следните параметри:
 
Сегментиране. Това е разделяне на ДКМ на независими подмрежи с различни размери. Всяка подмрежа трябва да има всички възможности за връзки на цялата мрежа от същия тип и размер.
 
Много автори подчертават важността на този параметър. Различни изследвания показват, че едностъпалната мрежа като shuffle-exchange или мрежата ILLIAC IV не могат да се сегментират, докато data manipulator може.
 
Ширина на лентата на пропускане. Този параметър се дефинира като очакван брой заявки приети за единица време. Тъй като системната шина не може да осигури широка лента на пропускане за голям брой процесори, а матричния комутатор е скъп, то е интересно и важно да се знае как варира лентата на пропускане при различните ДКМ за различните случаи. Най-често тези оценки се получават с помощта на подходящи имитационни модели.
 

 






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