459

Багатоярусна комунікаційна мережа складається з деякої множини ярусів, побудо­ваних на двоходових КЕ, та об'єднаних між'ярусними зв'язками (МЗ), як це показано на рис. 12.37. Ці зв'язки можуть відображати одну з можливих функцій маршрутизації, таку як батерфляй, куб і т. д.

Існує цілий ряд багатоярусних комутуючих комунікаційних мереж. Структура ши­роко розповсюджених топологій мереж "Баньян" та "Омега" для N=8 показана відпо­відно на рис. 12.38 а та на рис. 12.38 B. Вона містить в кожному з log₂N ярусів по N/2 КЕ і N каналів зв'язку. Якщо кожен КЕ виконує перемикання прямо і навхрест, то така комунікаційна мережа може виконати 2^N/2IogNперестановок, що істотно менше за N! пе­рестановок, можливих в неблокуючій мережі. Проте ті перестановки, які вона виконує, є найбільш використовуваними в багатопроцесорних системах. Потрібно відзначити, що в даній КММ є можливість її розділення на комунікаційні мережі меншого розміру шляхом включення на передачу прямо КЕ в тих ярусах, що стоять перед цими комуніка­ційними мережами.

---

460

У топології "Баньян" (рис. 12.38 а) між кожним входом і виходом існує лише один шлях. Мережа NxN(N = 2^m) складається з Nm/2 комутуючих елементів. Для керування мережею пакет, що передається, містить в своєму заголовку трирозрядний двійковий но­мер вузла призначення. Дана мережа належить до мереж з самомаршрутизацією, оскіль­ки адреса пункту призначення не тільки визначає маршрут повідомлення до потрібно­го вузла, але і використовується для керування проходженням повідомлення по цьому маршруту. Кожен КЕ, до якого потрапляє пакет, проглядає один біт адреси і, залежно від його значення, направляє повідомлення на вихід 1 або 2. Стан КЕ першого ярусу мережі (лівий стовпець КЕ) визначається старшим бітом адреси вузла призначення. Середнім ярусом (другий стовпець) управляє середній біт адреси, а третім ярусом (правий стов­пець) - молодший біт. Якщо значення біта рівне 0, то повідомлення пропускається через верхній вихід КЕ, а при одиничному значенні - через нижній. На рисунку показаний маршрут повідомлення з вхідного вузла 2 (010) до вихідного вузла 5 (101).

Топологія "Омега" є підкласом топології "Баньян". Ці топології досить популярні че­рез те, що комутація забезпечується простими КЕ, що працюють з однаковою швид­кістю, а повідомлення передаються паралельно. Крім того, великі мережі можуть бути побудовані з мереж меншого розміру.

12.9.5.5. Багатоярусні неблокуючі комутуючі мережі з реконфігурацією

Розглянемо далі багатоярусні КММ, що забезпечують повний набір з N! перестано­вок. Дані КММ забезпечують одночасне безконфліктне з'єднання довільного виходу з довільним входом, і тому представляють підвищений інтерес.

Однією з найбільш відомих і вивчених КММ даного класу є КММ Бенеша, структура якої для N=8 наведена на рис. 12.39.

Для даної мережі W_KMM = N(log₂N - 1/2) двовходових КЕ, або W_KMM = 3N(log,N-l) вен­тилів, кількість ярусів m=2log₂N-l, а затримка T_KMM=2(2log₉N-l)t.

Існує цілий спектр інших неблокуючих комутуючих мереж із реконфігурацією з по­дібними до вищеописаної мережі функціями. Так, у КММ Ваксмана, що є модифікацією мережі Бенеша, кількість КЕ зменшена на N/2-1. КММ Фаня є багатоярусною комбіна­ційною схемою зсуву. Кількість ярусів для N=2^Pрівне Р+1. У першому ярусі забезпечу­ється зсув кожного входу на +/-2^Р-1 розрядів, в другому ярусі - на +/-2^Р-2 розрядів і т. д. На КММ з N входами необхідно N (log,N+l) тривходових КЕ, причому на кожний КЕ необхідно 15 вентилів, а його затримка рівна Зі. Для даної КММ W_KMM = 15N(log₂N + 1) вентилів, T_KMM = 3(log₂N + 1) t. Недолік КММ Фаня - складність керування і нерегуляр­ність зв'язків. У КММ Каутца, структура якої для N=6 наведена на рис. 12.40, витраті: обладнання рівні W_KMM = N(N-l)/2 двовходових КЕ, або W_KMM = 3N(N-1) вентилів, а за­тримка Т_KMM = 2(2N-3) t, яка визначається сумою затримок КЕ по найдовшому шляху проходження даних. Перевага даної мережі - однорідність і регулярність.

---

461

Одночасне довільне з'єднання всіх виходів КММ з всіма входами забезпечують КММ, створені на базі структур сортувальних мереж, що запропоновано та описано в працях авто­ра даної книги. Потрібно відзначити, що можна синтезувати велику кількість структур бага­тоярусних КММ на базі сортувальних мереж з кількістю ярусів від log₂N(log₂N+l)/2 до N-1. Вибір конкретної структури залежить від вимог по швидкодії, обмежень за апаратною складністю, а також, можливо, і обмежень на топологію КММ. Розглянемо два крайні ви­падки даних структур. Структура КММ мінімальної швидкодії з даного класу, назвемо її крайньою зліва, аналогічна структурі відповідного графа сортування (рис. 12.41 а), має характеристики: W_KMM = 6(3^logN - 2^logN ) вентилів, T_KMM = 2(N - l)t. Швидша КММ, назвемо її крайньою справа, відповідна графу сортування Бетчера (рис. 12.41b), має характеристи­ки: W_KMM =6 2^logN-2(log²N - log N + 4) - 1 вентилів, Т_KMM = logN (logN + l)t.

---

462

Проведемо порівняння розглянутих багатоярусних неблокуючих комутуючих ме­реж з реконфігурацією за апаратною та часовою складностями. В табл. 12.3 наведено кількість КЕ та кількість ярусів залежно від числа входів N розглянутих КММ. Видно, що найвигіднішими за даними критеріями є КММ Бенеша і гранична справа КММ на основі сортувальної мережі Бетчера.

		Таблиця 12.3
Тип мережі	Кількість КЕ	Кількість ярусів
Бенеша	N(logN- 1/2)	m=2log N-l
Каутца	N(N-l)/2	2N-3
Фаня	5/3N(log,N+ 1)	log N + 1
Ваксмана	N(logN- 1)	m=2log2 N-l
Сортувальна крайня зліва	3logN-2logN	N- 1
Сортувальна крайня справа	2logN-2(log2N-logN+4)	IogN(logN+ 1).2

Розглянемо принципи керування багатоярусними КММ. У матричній одноярусній КММ керуючий код для кожного з N мультиплексорів (приймемо, що кількість входів КММ рівна кількості виходів) займає log₂N розрядів. Він дешифрується дешифратором мультиплексора і пропускає на вихід КММ інформацію з необхідного входу. У багатоярусних КММ кількість бітів керуючої інформації також рівна Nlog₂N, але в них log₂N-poзpядний код рухається ра­зом з інформаційним кодом і настроює КЕ на необхідний вид перемикань. Раніше був опи­саний принцип керування багатоярусною мережею "Баньян" (рис. 12.38а). Подібно в КММ "узагальнений куб" тег T=T_m T_m-1 ...Т₀ формується як сума за модулем два двійкових номерів джерела S=S_mS_m-1...S₀ і приймача D = D_mD_m-1....D , тобто Т = S + D. Кожний розряд тега посту­пає на відповідний його номеру КЕ і настроює його на режим роботи прямо, якщо Т.=0, або навхрест, якщо Т_i.=1.

Ефективно розв'язується питання керування в КММ, побудованих на базі сортуваль­них мереж, що запропоновано та описано в працях автора даної книги. В цьому випад­ку КЕ, спочатку працюючи в режимі сортування, налаштовується на необхідний режим перемикання, а потім працює в режимі комутації. У режимі сортування на входи КММ поступають адреси виходів, з якими дані входи повинні бути з'єднані. Дані адреси ру­хаються по елементах мережі і сортуються, а в кожному елементі запам'ятовується стан керуючого коду (розряду). При цьому немає потреби використовувати окремі шини для подачі керуючих сигналів на комутуючі елементи. На рис. 12.41 жирною лінією показано один із маршрутів при подачі на вхід мережі наведених керуючих кодів.

Проведений вище аналіз дозволяє зробити наступні висновки:

• одноярусні матричні КММ відрізняються гранично високою швидкодією, проте мають недостатню надійність, нерегулярну структуру, вимагають здійснення дуже вели­кої кількості зв'язків між елементами, що утруднює їх реалізацію. Крім того, вони мають велику апаратну складність;

• багатоярусні КММ відрізняються регулярністю і однорідністю структури, а також локальністю зв'язків, що особливо важливо при їх реалізації у вигляді НВІС. Крім того. в більшості структур багатоярусних КММ вихід з ладу одного або декількох КЕ практич­но не впливає на їх працездатність;

---

463

---

Смотрите также файлы

• Екологія посібник.doc

• LR3_[5405].doc

• Питання до модуля 1 з АК.doc

• Питання до 1 модуля з КЕ.doc

• ДБН В.3.2-2-2009_Жил_здания_реконст_кап_ремонт.doc