AOM / Мельник А

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=2log₂ N-l
Сортувальна крайня зліва	3^logN-2^logN	N- 1
Сортувальна крайня справа	2^logN-2(log²N-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

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

Содержание