Тема 12 — Комуникационни мрежи

1. Въведение

Едно от ключовите изисквания към паралелните компютри е наличието на ефективна среда за обмен на информация между процесорите. Тази среда се называ обобщено комуникационна мрежа. Недостатъчното бързодействие или ограничените комбинационни възможности на комуникационната мрежа могат съществено да намалят очаквания ефект от паралелната обработка — времето за комуникация се прибавя към изчислителното и така нараства общото време за решаване на задача.

Два подхода за намаляване на комуникационните загуби:

Оптимално разпределение на задачата (код и данни) по процесорите и/или модулите памет — обект на изследване при конструирането на паралелни алгоритми.
Повишаване на скоростта на комуникационната мрежа — чрез по-бързодействаща логика или подходяща структурна организация. Именно последният аспект е от архитектурен интерес.

В общия случай комуникационната мрежа е многополюсник с M входа и N изхода (по-нататък M = N). Изгражда се от комутиращи елементи и линии за връзка. Два основни класа:

Комуникационна мрежа с комутация по пространство — всеки активен предавател получава индивидуална линия за връзка към приемника. Висока сложност O(N²), малко време за трансфер O(1). Типични представители: матричен превключвател (crossbar) и пълно свързана мрежа.
Комуникационна мрежа с комутация по време — множество двойки предавател-приемник споделят обща линия в различни времеви слотове. Ниска сложност O(1), голямо време за трансфер O(N). Типичен представител: шина.

Третият клас — комбинирани комуникационни мрежи (по пространство и по време) — се стреми да съчетае предимствата на двата.

2. Характеристики на комуникационните мрежи

Комуникационните мрежи се характеризират по четири ключови параметъра:

Режим на работа. Три режима: синхронен (за SIMD-подобни транслационни операции), асинхронен (за динамично създавани връзки при MIMD) и комбиниран.

Стратегия на управление. Централизирано — специално устройство изчислява пътищата и управлява превключванията. Децентрализирано (разпределено) — самите комутиращи елементи извършват необходимите изчисления за маршрутизиране.

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

Мрежова топология. Ключовият фактор за архитектурните възможности на комуникационната мрежа — разглежда се подробно в следващата точка.

3. Топология на комуникационните мрежи

Топологията на комуникационните мрежи бива регулярна и нерегулярна. В паралелните компютри се използва само регулярна топология. Регулярните топологии са статични и динамични.

3.1. Статични комуникационни мрежи

Статичните комуникационни мрежи осигуряват непосредствена (директна) връзка само между определени двойки компоненти; останалите се постигат индиректно. Процесорите играят ролята на комутиращи елементи. За сравнение на топологиите служат следните параметри:

N — брой върхове (процесори).
D (диаметър) — максималното минимално разстояние между произволна двойка върхове.
P (средно разстояние) — средно разстояние от всеки връх до останалите при равновероятен избор.
T (натовареност на линията за връзка) — брой съобщения за единица време върху една линия за връзка = N × P / (брой линии за връзка).
U (относителна структурна сложност) — брой линии за връзка на един връх. При U = const системата е лесно мащабируема чрез добавяне на еднотипни компоненти.
Отказоустойчивост — наличие на алтернативни пътища при отказ на компоненти.

Тип комуникационна мрежа	Диаметър D
Линийка	N - 1
Кръг	N / 2
Квадратна решетка	2(√N - 1)
ILLIAC IV	√N - 1
Двоичен куб	log₂N

Конструкция на хиперкуб с нарастваща размерност: от 1D (ребро) до 4D (тесеракт). Всеки по-висш хиперкуб се получава от два по-ниши чрез добавяне на ребра между съответните им върхове.

3.2. Динамични комуникационни мрежи

Динамичните комуникационни мрежи осигуряват директна връзка между произволна двойка предавател-приемник чрез динамична реконфигурация на активните комутиращи елементи. Формално динамичната комуникационна мрежа е функция F: {N} → {N}, описваща пермутацията на входно-изходните адреси.

Динамичните комуникационни мрежи биват едностъпални (рециркулационни — данните могат да минат многократно) и многостъпални. Многостъпалните динамични комуникационни мрежи се делят на едностранни и двустранни, а двустранните — на:

Блокиращи — установяването на дадена двойка може да блокира друга (manulator, delta, omega, flip).
Напълно неблокиращи — всяка двойка може да се свърже без конфликт (мрежа на Клос, пълносвързана мрежа).
Неблокиращи с реконфигурация — всяка двойка може да се свърже, но понякога е необходима промяна на вече установени маршрути (мрежа на Бенес, битонална мрежа).

За оценка на динамичните комуникационни мрежи се използват: Вреемe за предаване O(k) при k стъпала, сегментируемост (разделяемост на независими подмрежи) и ширина на лентата на пропускане (очакван брой приети заявки за единица време).

4. Архитектура на комуникационния елемент

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

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

Най-разпространени са комутиращите елементи с 2 входа и 2 изхода. При 9-те възможни превключвателни конфигурации най-важни са:

Право предаване (П3, П6) — входовете се предават директно на изходите.
Размяна — входовете се разменят.
Трето състояние (П9) — необходимо в едностранни динамични комуникационни мрежи.
Разпръскване (П7, П8) — един вход се размножава към двата изхода.

Управление на комутиращите елементи чрез тяг (tag): T = X ⊕ Y, където X и Y са адресите на предавателя и приемника. Всеки комутиращ елемент превключва в зависимост от i-тия бит на тяга.

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

5. Примери за комуникационни мрежи

5.1. Комуникационна мрежа ILLIAC IV

Описва се от четири функции:

I+1(i) = (i + 1) mod N
I−1(i) = (i − 1) mod N
I+q(i) = (i + q) mod N, където q = √N
I−q(i) = (i − q) mod N

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

5.2. Двоичен хиперкуб

Брой входове N = 2^d. Функциите за превключване са d на брой:

cube_i(q[d-1]...q[i+1] q[i] q[i-1]...q[0]) = q[d-1]...q[i+1] q̄[i] q[i-1]...q[0]

т.е. всяка функция инвертира i-тия бит.

Свойства на хиперкуба:

Съдържа N = 2^d възела и d·2^(d-1) ребра.
Диаметър = d = log₂N; средно разстояние ≈ d/2.
Регулярен граф — структурата е идентична от всеки възел.
Съдържа множество подкубове с по-малка размерност, позволяващи ефективно мултипрограмиране.
Могат да се влагат дърво, кръг, решетка — избира се топология, минимизираща предаванията между несъседни възли.

Хиперкубът може да се реализира като статична комуникационна мрежа или като многостъпална динамична комуникационна мрежа (d стъпала, всяко съдържащо N/2 комутиращи елементи от тип 2×2).

5.3. Мрежа shuffle-exchange

Две функции:

Shuffle: shuffle(q[d-1]...q[1] q[0]) = q[d-2]...q[1] q[0] q[d-1] — цикличен ляв шифт.
Exchange: exchange(Q) = cube_0(Q) — инвертира най-малко значимия бит.

Реализира се като едностъпална (рециркулираща) или многостъпална мрежа с d стъпала.

5.4. Мрежа на Клос

Тристъпална структура с комутиращи елементи от тип n×m, r×r и m×n, където N = n·r. При m ≥ 2n − 1 мрежата е напълно неблокираща. Частният случай при m = n = r се нарича мрежа “Мемфис”.

5.5. Мрежа на Бенес

Симетрична структура с N входа и N изхода. Всяка половина съдържа рекурсивно вложена мрежа на Бенес с N/2 входа и изхода. Брой стъпала = 2log₂N − 1; общ брой комутиращи елементи = N(2log₂N − 1)/2. Отнася се към неблокиращите с реконфигурация, но установяването изисква O(N log₂N) операции, което прави динамичното съединяване непрактично.

Резюме

Комуникационната мрежа е критичен компонент на паралелните компютри: недостатъчната й пропускателна способност елиминира очакваното ускорение.
Статичните комуникационни мрежи (линийка, кръг, решетка, хиперкуб) осигуряват директни връзки само между строго определени двойки; процесорите изпълняват ролята на комутиращи елементи.
Двоичният хиперкуб с диаметър log₂N е особено привлекателен поради регулярна структура, множество подкубове и естественото влагане на дърво, кръг и решетка.
Динамичните комуникационни мрежи (delta, omega, Клос, Бенес) осигуряват пътища между произволни двойки; делят се на блокиращи, напълно неблокиращи и неблокиращи с реконфигурация.
Управлението на комутиращите елементи чрез тяг T = X ⊕ Y е просто и ефективно за многостъпални мрежи.
Съвременните интелигентни комутиращи елементи участват активно в координацията: регулират трафика, разпределят товара и синхронизират процеси.