Маршрутизатор з агрегацією з’єднань

Реферат: UA 77040 U UA 77040 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до систем передавання дискретної інформації, а саме до спеціальної техніки зв'язку в системах з пакетною комутацією, і призначена для побудови на її основі високопродуктивних маршрутизаторів для роботи, зокрема, в мережах на кристалі, що призначені для організації зв'язку між обчислювальними модулями інтегральних мікросхем (ІМС). Однією з характерних тенденцій, притаманних сучасним системам на кристалі (СнК), є постійне збільшення числа обчислювальних модулів при одночасному зростанні вимог до кількості та ємності міжмодульних з'єднань [1]. Внаслідок ускладнення внутрішньої структури СнК такі способи організації підсистеми зв'язку як "загальна шина" та "повнозв'язна архітектура" втрачають ефективність [2, 3]. Для вирішення проблеми обміну даними між підсистемами сучасних ІМС запропоновано використання концепції мережі на кристалі (МнК) [4]. Такий підхід має переваги масштабованості, паралелізму та високої тактової частоти [1]. МнК мають ряд відмінностей від своїх макроаналогів внаслідок обмежень за апаратурними ресурсами та споживаною потужністю. Якщо компонент комп'ютерної мережі може включати декілька мікросхем, то у випадку МнК все мережеве обладнання розміщується всередині однієї ІМС, що робить недоцільним використання великих обсягів буферної пам'яті, ресурсномістких методів маршрутизації та керування потоком. Оскільки для МнК характерне використання як буферної пам'яті коротких черг, довжина яких здебільшого менша за обсяг пакета даних, буферизація всього пакета перед передачею до наступного вузла мережі стає недоцільною. Замість цього використовують так звану wormhole технологію передачі даних. До сьогодні немає усталеного перекладу цього терміну на українську мову, тому надалі буде вживатися його назва на мові оригіналу. Суть wormhole передачі полягає в наступному: пакет даних розбивається на атомарні одиниці керування потоком, так звані фліти (flit-flow control unit), розмір яких дорівнює розрядності каналу передачі даних і які передаються неперервно один за одним. Це означає, що фліти двох різних пакетів не можуть почергово передаватися через одне фізичне з'єднання. Спочатку будуть передані фліти одного пакета, потім іншого. Під час wormhole передачі фліти просуваються через мережеве обладнання у міру можливості, не чекаючи приходу наступних флітів пакета, тому у кожний момент часу пакет може займати відразу декілька маршрутизаторів, на зразок черв'яка у червоточині, що і визначило назву методу передачі даних. Відомий wormhole маршрутизатор [5] для мереж на кристалі, що складається з модуля керування, комутатора та буферів, інформаційні виходи яких підключені до інформаційних входів комутатора, виходи якого є інформаційними виходами маршрутизатора, модуль керування якого з'єднаний з входом керування комутатора та з інтерфейсами керування буферів, в той час як інші виходи модуля керування є управляючими виходами маршрутизатора, а інші входи модуля керування є управляючими входами маршрутизатора, інформаційні входи якого підключені до інформаційних входів буферів (фіг. 1). До інформаційних та управляючих входів і виходів даного маршрутизатора підключені інші вузли мережі - маршрутизатори і мережеві інтерфейси. Останні використовують для узгодження формату і способу передачі даних між обчислювальними модулями та мережею. Недоліком мережі, побудованої на основі описаного вище маршрутизатора, є низьке значення порога насичення і, як наслідок, мала пропускна здатність. Поріг насичення характеризує величину прикладеного навантаження, при якому транспортна затримка мережі значно зростає (в десятки-сотні разів), а прикладене навантаження показує середню кількість флітів, яка водиться в мережу кожним обчислювальним модулем за цикл тактової частоти. Величина прикладеного навантаження лежить у межах від нуля до одиниці. Низьке значення порога насичення для описаного вище маршрутизатора обумовлене наступним фактором. Як було вже зазначено, виходячи із вимог wormhole передачі фліти кожного пакета повинні просуватися послідовно і неперервно один за одним. В описаному маршрутизаторі це досягається тим, що після приходу першого фліта пакета у вхідний буфер, з необхідним виходом комутатора укладається зв'язок, нерозривний до моменту передачі через встановлене з'єднання останнього фліта пакета. Протягом проміжку часу, коли вихід комутатора зайнятий певним вхідним буфером, інші вхідні буфери, що містять пакети, призначені для згаданого виходу комутатора, повинні чекати з'єднання і вважаються блокованими. Описане явище має назву "блокування голови колони" і значною мірою впливає на поріг насичення мережі, обмежуючи його зверху величиною 0.58, що підтверджено як теоретично [6], так і експериментально [7]. Іншим відомим засобом є wormhole маршрутизатор з віртуальними каналами [8], який складається з комутатора, модуля керування та вхідних модулів, кожен з яких містить буфери, виходи яких підключені до інформаційних входів мультиплексорів, виходи яких сполучені з 1 UA 77040 U 5 10 15 20 25 30 35 40 45 50 55 60 інформаційними входами комутатора, виходи якого є інформаційними виходами маршрутизатора, модуль керування якого з'єднаний з входом керування комутатора, входами керування мультиплексорів та демультиплексорів, а також з інтерфейсами керування буферів, в той час як інші виходи модуля керування є управляючими виходами маршрутизатора, а інші входи модуля керування є управляючими входами маршрутизатора, а кожен інформаційний вхід маршрутизатора підключений до інформаційних входів буферів відповідного вхідного модуля за допомогою демультиплексора (фіг. 2). Недоліком даного засобу є збільшення транспортної затримки маршрутизатора і зменшення порога насичення та пропускної здатності мережі внаслідок наступних факторів: - інформаційні входи всіх буферів (віртуальних каналів), що належать певному вхідному модулю, підключені за допомогою демультиплексора до єдиного інформаційного входу маршрутизатора і розділяють його пропускну здатність, оскільки в кожен момент часу через згаданий інформаційний вхід можна передавати дані лише до одного з буферів. Тому зі збільшенням числа буферів (віртуальних каналів) зростає період обслуговування кожного буфера (віртуального каналу), що призводить до збільшення часу, необхідного для передачі пакета через маршрутизатор і до зменшення кількості даних, що передаються через маршрутизатор за одиницю часу; - для підключення виходів всіх буферів (віртуальних каналів) всередині кожного вхідного модуля до одного з інформаційних входів комутатора використаний мультиплексор, що призводить до розділення пропускної здатності одного інформаційного входу комутатора між виходами всіх буферів (віртуальних каналів) одного вхідного модуля і, як наслідок, до збільшення транспортної затримки маршрутизатора і зменшення кількості даних, що передаються через маршрутизатор за одиницю часу; - у порівнянні з раніше описаним маршрутизатором [5] тепер необхідно не лише встановлювати з'єднання між виходами буферів та виходами комутатора, а й гарантувати рівномірний доступ виходів всіх буферів всередині одного вхідного модуля до певного інформаційного входу комутатора. Це додає ще один етап (тривалістю, як мінімум, один цикл тактової частоти) до конвеєризованої процедури обробки пакета даних. Найбільш близьким аналогом за технічною суттю до корисної моделі, що заявляється, є wormhole маршрутизатор з віртуальними каналами [9], який складається з модуля керування, комутатора та вхідних модулів, кожен з яких містить демультиплексор та буфери, виходи яких підключені до інформаційних входів комутатора, виходи якого є інформаційними виходами маршрутизатора, модуль керування якого з'єднаний з входом керування комутатора, входами керування демультиплексорів та з інтерфейсами керування вхідних буферів, в той час як інші виходи модуля керування є управляючими виходами маршрутизатора, а інші входи модуля керування є управляючими входами маршрутизатора, а кожен інформаційний вхід маршрутизатора підключений до інформаційних входів буферів відповідного вхідного модуля за допомогою демультиплексора (фіг. 3). Недоліком найближчого аналога є збільшення транспортної затримки маршрутизатора і зменшення порога насичення та пропускної здатності мережі за рахунок того, що інформаційні входи буферів кожного вхідного модуля підключені до єдиного відповідного їм інформаційного входу маршрутизатора за допомогою демультиплексора і, як наслідок, розділяють між собою пропускну здатність згаданого інформаційного входу маршрутизатора. В основу корисної моделі поставлена задача вдосконалення wormhole маршрутизатора [9] за рахунок того, що інформаційні входи маршрутизатора сполучені з інформаційними входами буферів за допомогою бієктивного зв'язку, що дозволяє забезпечити значне (більш ніж на 100 %) збільшення порога насичення wormhole мережі і, як наслідок, її пропускної здатності. Поставлена задача вирішується тим, що маршрутизатор і з агрегацією з'єднань, що складається з комутатора, модуля керування та N вхідних модулів, кожен з яких містить довільну кількість буферів, виходи яких підключені до інформаційних входів комутатора, виходи якого є інформаційними виходами маршрутизатора, модуль керування якого з'єднаний з входом керування комутатора та з інтерфейсами керування вхідних буферів, інші виходи модуля керування є управляючими виходами маршрутизатора, а інші входи модуля керування є управляючими входами маршрутизатора, згідно з корисною моделлю, інформаційні входи маршрутизатора сполучені з інформаційними входами буферів за допомогою бієктивного зв'язку. Це дозволяє для зв'язку з будь-яким із топологічно сусідніх вузлів мережі використовувати не одне фізичне з'єднання, а декілька, агрегованих в логічне з'єднання (фіг. 4, 5). Тепер кожному буферу відповідає власне (виділене) фізичне з'єднання, підключене до відповідного інформаційного входу маршрутизатора, тобто "віртуальні" з'єднання перетворюються на реальні (фізичні) з'єднання, що приводить до збільшення пропускної 2 UA 77040 U 5 10 15 20 25 30 35 40 45 50 55 60 здатності входів буферів в порівнянні з аналогами [8], [9], де дані, що належать різним буферам (віртуальним каналам) одного вхідного модуля мультиплексуються через єдиний інформаційний вхід маршрутизатора. Зі збільшення пропускної здатності буферів вхідних модулів зростає пропускна здатність маршрутизатора і всієї мережі в цілому, що забезпечує досягнення зазначеного технічного результату. Суть запропонованої корисної моделі пояснюється кресленнями, де: на фіг. 1 зображена структурна схема wormhole маршрутизатора; на фіг. 2 - структурна схема wormhole маршрутизатора з віртуальними каналами. Виходи буферів кожного вхідного модуля підключені до одного з входів комутатора за допомогою мультиплексора; на фіг. 3 - структурна схема wormhole маршрутизатора з віртуальними каналами. Виходи буферів кожного вхідного модуля підключені до входів комутатора за допомогою виділених з'єднань; на фіг. 4 - структурна схема корисної моделі, що заявляється (wormhole маршрутизатор з агрегацією з'єднань); на фіг. 5 - приклад wormhole мережі з агрегацією з'єднань (топологія - двовимірна решітка, розмірність решітки - 33); на фіг. 6 - приклад реалізації комутатора на базі мультиплексорів; на фіг. 7 - приклад позначення з'єднань маршрутизатора, призначеного для функціонування в мережі з топологією у вигляді двовимірної решітки; на фіг. 8 - приклад алгоритму, що реалізує завчасну (look-ahead) маршрутизацію; на фіг. 9 - приклад алгоритму, що реалізує покоординатну х у маршрутизацію; на фіг. 10 - структурна схема блока виділення доступу до виходів комутатора; на фіг. 11 - приклад реалізації арбітра з пріоритетами; на фіг. 12 - приклад реалізації складової частини арбітра з пріоритетами; на фіг. 13 - залежність середнього значення транспортної затримки мережі на кристалі з агрегацією з'єднань від прикладеного навантаження та кількості фізичних з'єднань всередині агрегованого логічного з'єднання (крива 1 - одне фізичне з'єднання, крива 2 - два фізичних з'єднання, крива 3 - чотири фізичних з'єднання); на фіг. 14 - залежність середнього значення транспортної затримки мережі на кристалі з віртуальними каналами від прикладеного навантаження та кількості віртуальних каналів на один вхідний модуль маршрутизатора (крива 1 - один віртуальний канал, крива 2 - два віртуальних канали, крива 3 - чотири віртуальних канали); на фіг. 15 - залежність транспортної затримки мережі від прикладеного навантаження для 1 - мережі на базі wormhole маршрутизаторів Hermes (2 віртуальні канали на кожен вхідний модуль маршрутизатора), 2 - мережі на базі wormhole маршрутизаторів з агрегацією з'єднань (2 фізичних з'єднання на кожне агреговане з'єднання). Wormhole маршрутизатор з агрегацією з'єднань (фіг. 4) складається із N вхідних модулів 1, кожен з яких містить MBXN буферів 2 для тимчасового зберігання даних (флітів), що надходять від інших вузлів мережі. Різним вхідним модулям 1 може відповідати різна кількість вхідних буферів 2. Інформаційний вхід кожного з буферів 2 зв'язаний з відповідним йому інформаційним входом маршрутизатора за допомогою взаємно однозначного зв'язку. Виходи буферів 2 підключені до інформаційних входів комутатора 3, виходи якого є інформаційними виходами маршрутизатора. Модуль керування 4 з'єднаний з входом керування комутатора 3 та з інтерфейсами керування буферів 2, інші виходи модуля керування 4 є управляючими виходами маршрутизатора, а Інші входи модуля керування 4 є управляючими входами маршрутизатора. Кількість вхідних модулів N може бути будь-яким числом, що більше за нуль, а сам термін "вхідний модуль" використовується для визначення інтерфейса, за допомогою якого агреговане логічне з'єднання підключене до маршрутизатора. Дане з'єднання пов'язує два топологічно сусідніх вузли мережі (маршрутизатор-маршрутизатор, маршрутизатор-мережевий інтерфейс, мережевий інтерфейс-маршрутизатор) по типу точка-точка і складається з кількох фізичних з'єднань. Фізичне з'єднання сполучає інформаційний вихід одного маршрутизатора та інформаційний вхід іншого маршрутизатора у відповідності до вибраної топології. Фізичне з'єднання супроводжується, наприклад, флітом та сигналом, який ініціює запис фліта у вхідний буфер приймача. Фліт в свою чергу може містити, наприклад, поле даних, а також біти "head" і "tail". Одиничне значення біта "head" вказує на те, що фліт є першим в пакеті. Одиничне значення біта "tail" вказує на те, що фліт - останній в пакеті. Пропускна здатність агрегованого логічного з'єднання дорівнює сумі пропускних здатностей фізичних з'єднань, що входять до його складу. Кількість вхідних модулів показує, скільки вузлів мережі можна з'єднати з даним маршрутизатором. Вибір кількості вхідних модулів залежить від топології, відповідно до якої 3 UA 77040 U 5 10 15 20 25 30 об'єднані вузли в мережі. Якщо використовувати, наприклад, топологію у вигляді двовимірної решітки (фіг. 5), у вузлах якої знаходяться маршрутизатори, місцезнаходження маршрутизатора в мережі з такою топологією буде визначатися двома індексами і тау в дискретній системі декартових координат на площині. Чотири вхідних модулі маршрутизатора використовуються для з'єднання з сусідніми маршрутизаторами відповідно до вибраної топології, а через п'яте агреговане логічне з'єднання, маршрутизатор за допомогою мережевого інтерфейса підключається до обчислювального модуля. В мережі з такою топологією маршрутизатор має п'ять вхідних модулів. Для забезпечення двосторонньої передачі даних між двома топологічно сусідніми вузлами мережі може використовуватись два агрегованих логічних з'єднання різної направленості (якщо необхідно забезпечити двонаправлену передачу даних), причому кількість фізичних з'єднань всередині цих агрегованих логічних з'єднань не обов'язково повинна бути однаковою. Таким чином, маршрутизатор, який можна реалізувати на основі винаходу, що заявляється, підключається до N вхідних агрегованих логічних з'єднань і N вихідних агрегованих логічних з'єднань. Вхідні агреговані логічні з'єднання підключаються до входів буферів відповідних їм вхідних модулів маршрутизатора, а вихідні агреговані логічні з'єднання підключаються до виходів комутатора. До задач вхідного модуля 1 також входить зберігання певної інформації (наприклад, в регістрах), асоційованої з кожним вхідним буфером, а саме: 1. Номер вихідного агрегованого логічного з'єднання, куди необхідно перенаправляти всі фліти пакета, що надходять у буфер. Назвемо цю змінну N_Aggregation_Channel; 2. Номер фізичного з'єднання всередині вихідного агрегованого з'єднання, який поставлений у відповідність вхідному буферу блоком виділення доступу до виходів комутатора, який є складовою частиною модуля керування 4. Назвемо цю змінну N_Physical_Channel; 3. Біт встановлення з'єднання. Дорівнює одиниці у випадку, коли для вхідного буфера визначене агреговане логічне з'єднання на виході маршрутизатора і поставлене у відповідність фізичне з'єднання всередині вибраного агрегованого логічного з'єднання. Назвемо цю змінну Connection_Valid. Комутатор 3 може бути реалізований, наприклад, у вигляді набору мультиплексорів (фіг. 6). До входів комутатора 3 підключаються виходи буферів 2 даного маршрутизатора, а до виходів комутатора 3 за допомогою фізичних з'єднань підключаються входи буферів 2 Інших вузлів мережі, топологічно сусідніх з даним маршрутизатором. Кількість входів даних ΚΒХ для кожного з мультиплексорів, а значить і для комутатора розраховується по формулі: N KВХ   MВХi , (1) I1 35 де N - кількість вхідних агрегованих логічних з'єднань для даного маршрутизатора (дорівнює кількості вхідних модулів); МВХі - кількість буферів всередині і-го вхідного модуля, тобто кількість фізичних з'єднань всередині агрегованого логічного з'єднання, яке підключається до і-го вхідного модуля маршрутизатора. Кількість виходів комутатора KВИХ, а значить і кількість мультиплексорів, необхідна для його реалізації, розраховується по формулі: K ВИХ  40 45 50 55 N  MВИХi , (2) I1 де N - кількість вихідних агрегованих логічних з'єднань для даного машрутизатора (дорівнює кількості вхідних агрегованих логічних з'єднань); М ВИХі - кількість фізичних з'єднань всередині іго вихідного агрегованого логічного з'єднання. Характеризує кількість виходів комутатора 3, до яких через фізичні з'єднання і-го агрегованого логічного з'єднання підключаються входи буферів 2 іншого вузла мережі. Вхідні буфери 2 можна реалізувати, наприклад, як синхронні черги з механізмом доступу "перший прийшов, перший вийшов". Кожна така черга містить інтерфейси для запису та зчитування даних, а також сигнали керування, наприклад: "черга повна" (встановлюється в одиницю, коли всі комірки черги заповнені даними, інакше - нуль), "черга порожня" (встановлюється в одиницю, коли всі комірки черги порожні, інакше - нуль), "записати до черги" (якщо одиниця, і черга не повна, то по передньому фронту сигналу синхронізації, дані, що подані на вхідний запис будуть поміщені в хвіст черги), "зчитати з черги" (якщо одиниця і черга не порожня, то по передньому фронту сигналу синхронізації, дані з голови черги будуть вилучені). Дані, що знаходяться в голові черги постійно присутні на виводах інтерфейсу зчитування. Як чергу можна використати, наприклад, мегафункцію компанії Altera під назвою "scfifo" [12]. Розрядність комірок черги (розрядність слова черги) дорівнює кількості розрядів фліта. 4 UA 77040 U 5 10 15 20 25 30 35 40 45 50 55 60 З'єднання всередині комутатора встановлюються у відповідності до сигналів, сформованих модулем керування 4, який зв'язаний також з головами та сигналами керування черг вхідних модулів та сигналами керування потоком і складається з наступних блоків: 1. блок маршрутизації; 2. блок керування потоком; 3. блок виділення доступу до виходів комутатора; 4. блок керування комутатором. Задача блока маршрутизації полягає у визначені для кожного вхідного буфера 2 номеру виходу маршрутизатора, на який необхідно перенаправляти всі фліти пакета, до якого застосовується маршрутизація. Оскільки у мережі з агрегацією з'єднань логічному зв'язку по типу точка-точка між двома мережевими вузлами відповідає декілька фізичних з'єднань, можна сформулювати задачу блока маршрутизації більш конкретно як таку, що полягає у визначені для кожного вхідного буфера 2 номера вихідного агрегованого логічного з'єднання, куди необхідно перенаправляти всі фліти пакета, до якого застосовується маршрутизація. Числові ідентифікатори агрегованих логічних з'єднань маршрутизатора, призначеного для функціонування в мережі з топологією у вигляді, наприклад, двовимірної решітки, показані на фіг. 7. Як видно з фіг. 7, кожному напрямку передачі поставлений у відповідність унікальний номер. Для реалізації блока маршрутизації можна використати, наприклад, так звану завчасну (look-ahead) маршрутизацію, принцип роботи якої докладно розібраний в [13] на с. 318 і полягає у тому, що маршрутна інформація для поточного вузла мережі визначається у попередньому вузлі і передається, як правило, у першому фліті пакета разом з координатами вузла мережі, до якого прямує даний пакет. Нагадаємо, що перший фліт пакета характеризується одиницею у службовому біті "head". Look-ahead маршрутизацію можна реалізувати, наприклад, за допомогою алгоритму, наведеного на фіг. 8. Для визначення агрегованого логічного з'єднання на виході наступного маршрутизатора можна використати, наприклад, так звану покоординатну x y маршрутизацію (фіг. 9), яка докладно описана в [13] та використовується у мережах з топологією у вигляді двовимірної решітки (фіг. 5) і полягає у тому, що пакет просувається спочатку в горизонтальному напрямку двовимірної решітки, а потім у вертикальному. Блок керування потоком використовується для вирішення наступних задач: 1. Визначення стану вхідних буферів 2 інших вузлів мережі, які підключені до виходів поточного маршрутизатора (під виходами маршрутизатора розуміють виходи його комутатора 3). З цією метою можна використати вектор бітів, де кожному виходу маршрутизатора відповідає один біт, який дорівнює одиниці, коли у вхідному буфері 2 наступного вузла мережі (приймача) є вільні комірки і дорівнює нулю, коли вхідний буфер 2 наступного вузла мережі повністю заповнений (не може приймати дані). 2. Оповіщення топологічно сусідніх вузлів мережі про стан вхідних буферів 2 даного маршрутизатора. Для того, щоб вузли мережі могли виконувати задачу із попереднього пункту, маршрутизатор повинен прямо чи опосередковано передавати сусіднім вузлам інформацію про стан своїх вхідних буферів 2. 3. Керування просуванням флітів через маршрутизатор. Для реалізації перших двох пунктів із вище згаданих можна використати, наприклад, так зване керування потоком на основі кредитів, яке докладно описане в [13] і полягає у тому, що кількості вільного місця в буфері 2 приймача відповідає певна кількість кредитів передавача (один фліт - один кредит), тобто кожному виходу комутатора 3 поставлена у відповідність певна кількість кредитів. У випадку звільнення комірки у вхідному буфері 2 приймача останній посилає сигнал (кредит) відповідному виходу передавача, після прийому якого кількість кредитів передавача для даного з'єднання інкрементується. У випадку відправлення передавачем фліта кількість кредитів для даного з'єднання зменшується на одиницю. Передача можлива лиш, коли кількість кредитів передавача не дорівнює нулю. В момент запуску системи кількість кредитів кожного передавача дорівнює кількості комірок у відповідному йому буфері 2 приймача. Сигнали кредитів передаються по лініях керування потоком між двома топологічно сусідніми маршрутизаторами від приймача флітів до їх передавача. Кожному фізичному з'єднанню відповідає одна лінія кредитів (тобто один біт). У випадку, коли вхідні буфери 2 реалізовані у вигляді черги і на вхід керування певною чергою "зчитати з черги" подана одиниця, необхідно також сформувати одиницю на лінії кредиту, що відповідає фізичному з'єднанню, яке сполучене з цією чергою. По передньому фронту наступного циклу тактової частоти фліт, що знаходиться в голові черги, буде вилучено з неї, а передавач флітів, підключений до входу черги, буде повідомлений про цей факт шляхом зчитування одиниці на відповідній лінії кредитів та інкрементувавши кількість кредитів, яка асоційована з відповідним вихідним фізичним з'єднанням. 5 UA 77040 U 5 10 15 20 25 30 35 40 45 50 55 60 Блок керування потоком може виконувати просування флітів через маршрутизатор, наприклад, наступним чином. До складу кожного фізичного з'єднання, окрім безпосередньо фліта, входить також службовий біт "valid", який вказує, коли записувати дані, присутні на лініях фізичного з'єднання у вхідний буфер 2 наступного вузла мережі. Якщо передатчик встановлює біт "valid" в одиницю, це означає, що приймач повинен зчитати дані, які присутні на лініях даного фізичного з'єднання і записати ці дані у відповідний буфер 2. Якщо буфери 2 реалізовані у вигляді черг, для реалізації цієї операції можна, наприклад, підключити біт "valid" фізичного з'єднання зі сторони приймача до входу запису до відповідної черги. При реалізації буферів 2 маршрутизатора на основі черги scfifo від компанії Altera [12], для якої запис і зчитування відбуваються за один такт, дані на лініях фізичного з'єднання будуть записані в чергу по передньому фронту наступного циклу тактової частоти після того, як сигнал "valid" буде встановлений в одиницю. Якщо з'єднання між виходом буфера 2 і виходом комутатора 3 встановлено (процедура встановлення з'єднання описана далі), для відправлення фліта до наступного маршрутизатора необхідно встановити "valid" на необхідному виході в одиницю (це можна реалізувати за допомогою, наприклад, комбінаційної схеми), а також вилучити фліт з буфера 2 даного маршрутизатора після того, як він буде записаний до буфера 2 наступного маршрутизатора. Якщо буфери 2 реалізовані у вигляді черги, для вилучення фліта можна, наприклад, з'єднати біт "valid" з сигналом "зчитати з черги". При реалізації буферів 2 маршрутизатора на основі черги scfifo від компанії Altera [12] у випадку, коли на певному такті біт "valid", пов'язаний з певним флітом, встановлений передавачем в одиницю, на наступному такті цей фліт буде вилучений з черги на вході даного маршрутизатора і записаний в чергу на відповідному вході наступного маршрутизатора. Біт "valid" певного фізичного з'єднання на виході маршрутизатора встановлюється в одиницю, коли одночасно виконуються наступні умови: 1. з'єднання між певним вхідним буфером 2 та певним виходом комутатора 3 для поточного маршрутизатора встановлене; 2. вхідний буфер містить дані для передачі (у випадку реалізації буферів у вигляді черг, сигнал "черга порожня" дорівнює нулю); 3. відповідний буфер 2 на вході наступного маршрутизатора (куди необхідно передавати фліти) не повністю заповнений (у випадку реалізації буферів 2 у вигляді черг, сигнал "черга повна" дорівнює нулю). Про стан буферів 2 наступного маршрутизатора поточний маршрутизатор дізнається за допомогою описаного вище механізму кредитів. З'єднання між виходом буфера 2 вхідного модуля маршрутизатора та виходом комутатора 3 встановлюється за допомогою блока виділення доступу до виходів комутатора 3 і блока керування комутатором 3. Блок виділення доступу до виходів комутатора 3 ставить у відповідність кожному вхідному буферу 2, який встановив сигнал запиту на з'єднання, один з виходів комутатора 3. Якщо на використання одного з виходів комутатора встановлені запити від декількох вхідних буферів 2, буде задоволений лише один з них. В такому випадку вхідний буфер 2, якому вже поставлений у відповідність вихід комутатора 3, знімає сигнал запиту на відміну від незадоволених запитів на цей вихід комутатора 3, які залишаються встановленими до часу задоволення їх блоком, що описується. Структурна схема блока виділення доступу до виходів комутатора 3 показана на фіг. 10 і складається з мультиплексорів 5, демультиплексорів 6, комбінаційних схем вибору 7, а також арбітрів 8 та 9. Блок має входи для формування запитів, число яких дорівнює кількості вхідних буферів 2 маршрутизатора. Один вхід формування запиту складається з безпосередньо лінії формування запиту (один біт) та номера вихідного агрегованого логічного з'єднання, до одного з фізичних з'єднань якого потрібно отримати доступ. Одиниця на лінії формування запиту відповідає запиту, а нуль - його відсутності. Номер агрегованого логічного з'єднання на виході поточного маршрутизатора для кожного з вхідних буферів 2 зчитується блоком маршрутизації з першого фліта пакету даних і запам'ятовується у змінній N_Aggregation_Channel для відповідного вхідного буферу 2. Формування запитів відбувається модулем керування 4, наприклад, за допомогою комбінаційної логіки для кожного першого фліта пакета (біт фліта "head" дорівнює одиниці). Одиниця на лінії формування запиту встановлюється, якщо біт встановлення з'єднання Connection_Valid для певного вхідного буферу 2 дорівнює нулю і буфер 2 містить фліт з одиничним значенням службового біту "head". У випадку, коли біт Connection_Valid приймає значення "одиниця", одиниця на лінії запиту перетворюється на нуль, тобто як тільки вхідному буферові 2 виділений вихід комутатору 3, відповідний запит знімається. Кожному входу для формування запитів відповідає один мультиплексор 5, один 6 UA 77040 U 5 10 15 20 25 30 35 40 45 50 55 60 демультиплексор 6, один арбітр 8 та одна комбінаційна схема вибору 7. Блок виділення доступу включає ΚНХ груп згаданих компонентів, ΚΒХ розраховується по формулі (1). Кожен арбітр 8 має Мmax входів, до яких підключено Мmax логічних елементів "і", які утворюють комбінаційну схему вибору 7. Мmax - це максимальне число фізичних з'єднань всередині вихідних агрегованих логічних каналів маршрутизатора. Якщо даний маршрутизатор з'єднується з топологічно сусідніми вузлами мережі за допомогою N вихідних агрегованих логічних з'єднань, М max розраховується по формулі: Мmax = max(МВИХ1, МВИХ2, …, МВИХN). Функція арбітра 8 полягає у наступному. Кожен з мультиплексорів 5 має N входів розрядністю Мmax. Кожен вхід мультиплексора 5 являє собою вектор бітів довжиною М max, кожен біт якого відповідає певному фізичному з'єднанню всередині агрегованого логічного каналу на виході маршрутизатора (тобто одному з виходів комутатору 3) і дорівнює одиниці, коли вихід комутатору 3 вільний і нулю, коли вихід комутатора 3 уже зайнятий одним з вхідних буферів 2. У відповідності до того, з яким з агрегованих логічних з'єднань на виході маршрутизатора хоче встановити зв'язок вхідний буфер 2 (ця інформація зберігається у змінній N_Aggregation_Channel для відповідного вхідного буфера 2), на входи комбінаційної схеми вибору 7 подаються сигнали про стан фізичних з'єднань обраного агрегованого логічного з'єднання на виході комутатора 3. Якщо на лінії запиту з'єднання від відповідного вхідного буфера 2 присутня одиниця, арбітр 8 обере один з незайнятих виходів комутатора 3 (тобто поставить його у відповідність даному вхідному буферу 2). Оскільки на цьому етапі кільком вхідним буферам 2 може бути поставлений у відповідність один і той же вихід комутатора 3, для встановлення однозначної відповідності використовується ще один рівень арбітражу на базі арбітрів 9. Кожен з арбітрів 9 має ΚΒХ входів, де ΚΒХ розраховується по формулі (1). Всього використовується KВИХ арбітрів 9, де KВИХ розраховується по формулі (2). Таким чином, кожному виходу комутатора 3 відповідає один арбітр 9. До виходів кожного арбітра 8 підключений вхід демультиплексора 6, що має кількість розрядів Мmax. Демультиплексор 6 має N виходів розрядністю Мmax, кожен з яких з'єднаний з входами арбітрів 9 таким чином, як це показано на фіг. 10. На вхід керування демультиплексором 6 подається така ж сама інформація, як і на вхід керування мультиплексором 5, а саме – номер вихідного агрегованого логічного з'єднання для відповідного вхідного буфера 2. Як тільки певному вхідному буферу 2 виділений вихід комутатору 3, біт Connection_Valid, що відповідає цьому буферу 2 повинен бути встановлений в одиницю. Арбітри 8 та 9 можуть бути реалізовані, наприклад, як арбітри зі зміною пріоритетів (roundrobin arbiter), принцип роботи яких докладно описаний в [12]. Структурна схема арбітра з пріоритетами показана на фіг. 11, а реалізація складової частини 10 такого арбітра показана на фіг. 12. Входи, між якими виконується арбітраж, позначені, як ri. Кожному входу ri відповідає вихід gi. Якщо запити присутні на декількох входах ri, арбітр вибере з цих запитів лише один, про що повідомить підтвердженням запиту ri на виході gi. Входи рі встановлюють пріоритет входу ri. Одиниця на вході рі сигналізує про те, що відповідний вхід ri має найвищий пріоритет. В кожен момент часу лише один біт вектора пріоритетів p дорівнює одиниці. Під час ініціалізації системи - це наймолодший біт р0. Пріоритет зменшується зі збільшенням індексу i, причому циклічно. Це значить, що якщо максимальний пріоритет має вхід ri, тобто біт р1 дорівнює одиниці, то мінімальний пріоритет буде у входу r0. Якщо вхід арбітра має максимальний пріоритет, це значить, що запит від нього буде задоволений в першу чергу (відносно входів з меншим пріоритетом). Для того, щоб не надавати переваги у задоволені запитів лише певному входу, після кожної процедури арбітражу пріоритети входів потрібно змінювати таким чином, щоб вхід, який щойно виграв арбітраж, отримував найменший пріоритет. Таку зміну пріоритетів можна реалізувати за допомогою наступної синтаксичної конструкції на мові System Verilog: assign next_p = |g? {g[n-2:0], g[n-1]}: p, де next_p - новий вектор пріоритетів входів; p - старий вектор пріоритетів входів; g - вектор бітів, що представляє виходи арбітра; n - кількість бітів у векторах next_p, ρ, g. Задача блока керування комутатором 3 полягає у формуванні таких сигналів для мультиплексорів комутатора 3 (фіг. 6), щоб з'єднати кожен вхід комутатора 3 з тим виходом, який поставлений йому у відповідність блоком виділення доступу до виходів комутатора 3. Для кожного вхідного буфера 2 інформація про вихідне агреговане логічне з'єднання зберігається у змінній N_Aggregation_Channel, а номер фізичного з'єднання всередині агрегованого з'єднання міститься у змінній N_Physical_Channel. Сигнали керування комутатором 3 можна формувати, наприклад, за допомого комбінаційної схеми, яка реалізує наступний алгоритм - для кожного 7 UA 77040 U 5 вхідного буфера 2, біт Connection Valid якого встановлений в одиницю, визначити номер виходу комутатора 3, з яким необхідно створити з'єднання і на вхід керування мультиплексором комутатора 3, що відповідає щойно визначеному виходу комутатора 3, подати номер вхідного буфера 2, для якого відбувається операція встановлення з'єднання. Номер виходу комутатора 3, з яким необхідно створити з'єднання визначається за допомогою наступної формули: NВИХ _ КОМ  10 15 20 25 30 35 40 45 50 55 N _ Aggregation _ Channel 1  MВИХi  N _ Physical _ Channel . i 1 З'єднання між вхідним буфером 2 та виходом комутатора 3 розривається після того, як з буфера 2 зчитується останній фліт пакета (біт "tail" дорівнює одиниці). Тепер згаданий вихід комутатора 3 вважається вільним і знову доступний для виділення одній з вхідних черг. У цьому випадку модуль керування 4 перетворює значення біту Connection_Valid для вхідної черги, з якої щойно було вилучено останній фліт пакета, з одиниці в нуль. Розглянемо принцип роботи корисної моделі, що заявляється. Для збільшення тактової частоти функціонування wormhole маршрутизатора з агрегацією з'єднань процедуру обробки пакета можна розбити на декілька операцій і виконати у вигляді конвеєра. Наприклад, можна використати три етапи конвеєра, на першому з яких виконується запис фліта до черги, на другому - операції маршрутизації та встановлення з'єднання, а на третьому - вибірка фліта з буфера маршрутизатора і передача та запис його до наступного вузла мережі. Тривалість кожного з етапів складає один цикл тактової частоти. Таким чином, для обробки (передачі) першого фліта пакета необхідно витратити три цикли тактової частоти, а для просування всіх наступних флітів лише один цикл тактової частоти (останній етап конвеєра). В даному випадку наявність першого етапу обумовлена використанням у якості черги модуля scfifo від компанії Altera [12], який відрізняється тим, що при записуванні в пусту чергу дані у її голові стануть доступними лише на наступному циклі тактової частоти (тобто, сигнал "черга порожня" перейде з одиниці в нуль). При використанні черги, дані на виході якої стають доступними на тому ж циклі тактової частоти, на якому відбувається запис, перший етап роботи конвеєра можна опустити. Для покращення частотних характеристик пристрою можна збільшити кількість етапів конвеєра, наприклад, конвеєризувати роботу блока виділення доступу до виходів комутатора 3, коли на одному такті виконується арбітраж першого рівня (арбітри 8), а на наступному такті - арбітраж другого рівня (арбітри 9). Виходи комутатора 3 можна сполучити з фізичними з'єднаннями за допомогою регістрів, кількість розрядів яких дорівнює кількості розрядів фізичного з'єднання, що також призведе до збільшення максимально допустимої тактової частоти функціонування пристрою. Потрібно мати на увазі, що збільшення кількості етапів конвеєра збільшує транспортну затримку маршрутизатора і приводить до зростанні транспортної затримки мережі. Розглянемо ситуацію, коли в порожній вхідний буфер 2, реалізований, наприклад, на основі черги, по передньому фронту першого циклу тактової частоти, записується фліт. Підставою для операції запису є одиниця, сформована виходом попереднього вузла мережі на лінії "valid" фізичного з'єднання, яка підключена до сигналу "записати до черги". У випадку реалізації вхідних черг на базі модуля scfifo від компанії Altera [12], щойно записані дані стануть доступними для зчитування з голови черги лише на наступному (другому) циклі тактової частоти, на що вкаже зміна сигналу "черга порожня" з одиниці на нуль. На початку другого циклу тактової частоти у випадку, якщо у вхідну чергу був записаний перший фліт пакету і біт Connection_Valid для цієї черги дорівнює нулю, модуль керування 4 сформує для такої черги запит на виділення вільного виходу комутатора 3 у вихідному агрегованому логічному з'єднанні, номер якого зчитується з першого фліта пакету у змінну N_Aggregation_Channel для даної черги. Протягом другого циклу тактової частоти триває операція виділення доступу до виходу комутатора 3 і одночасно з цим блоком маршрутизації проводиться обчислення маршрутної інформації для наступного вузла мережі у вигляді номеру агрегованого логічного з'єднання, куди необхідно перенаправляти фліти даного пакету. До кінця другого циклу тактової частоти дві згадані операції повинні завершитися. Якщо вхідній черзі успішно поставлений у відповідність вихід комутатора 3, його номер записується у змінну N_Physical_Channel для даної черги, значення біту Connection Valid для даної черги встановлюється в одиницю і запит на виділення доступу до комутатора 3 знімається. У протилежному випадку запит на виділення виходу комутатора 3 залишається і на наступному циклі тактової частоти знову буде зроблена спроба виконати цю операцію. Під час третього циклу тактової частоти блок керування комутатором налаштовує комутатор 3 на з'єднання між його входом, до якого підключена голова черги, та виходом, до якого підключене фізичне з'єднання з наступним вузлом мережі. Одночасно з цим у випадку, якщо у вхідному буфері 2 наступного вузла мережі є вільні комірки, модуль керування 4 встановлює сигнал "valid" відповідного фізичного з'єднання в одиницю (про 8 UA 77040 U 5 10 15 20 25 30 35 40 45 50 55 те, що у вхідній черзі наступного маршрутизатора є вільні місця, свідчить ненульове значення кількості кредитів у відповідного виходу комутатора 3). На сигнал зчитування з відповідної черги подається одиниця, а на лінії кредитів для фізичного з'єднання, яке відповідає вхідній черзі, формується одиниця, яка вказує попередньому вузлу мережі на те, що на наступному циклі тактової частоти у відповідній черзі з'явиться ще одна вільна комірка. В цей же час кількість кредитів для виходу комутатора 3, через який на наступному циклі тактової частоти буде передаватися фліт, зменшується на одиницю, вказуючи на те, що кількість вільних комірок у вхідному буфері 2 наступного вузла мережі зменшиться на одиницю на наступному циклі тактової частоти. На наступному (четвертому) циклі тактової частоти фліт буде вилучено з черги даного маршрутизатора і записано до вхідної черги наступного маршрутизатора. Одиничне значення біту "valid" зберігається, доки в голові вхідної черги маршрутизатора присутні доступні для зчитування фліти пакета даних і у вхідній черзі наступного маршрутизатора є вільні місця, що призводить до передачі в наступний маршрутизатор одного фліта на кожному циклі тактової частоти. У випадку, коли не виконуються умови встановлення біту "valid" в одиницю, фліт залишається у вхідному буфері 2 маршрутизатора і не передається до наступного вузла мережі. По передньому фронту циклу тактової частоти, коли останній фліт пакету (службовий біт "tail" встановлений в одиницю) вилучається з вхідної черги поточного маршрутизатора і записується у вхідний буфер 2 наступного вузла мережі, вихід комутатора 3 вважається вільним і знову доступний для виділення одній з вхідних черг. В цей же час значення біта Connection_Valid для вхідної черги поточного маршрутизатора, з якої щойно було вилучено останній фліт пакета, переходить з одиниці в нуль. Якщо в голові цієї черги присутній перший фліт наступного пакета даних, модуль керування 4 знову формує запит до блока виділення доступу до виходів комутатора 3, ініціюючи процедуру встановлення з'єднання. У протилежному випадку черга очікує приходу першого фліта пакета і описані вище дії повторюються. Якщо під час переднього фронту циклу тактової частоти на лінії кредитів, що відповідає певному виходу комутатора 3, присутня одиниця, це означає, що наступний маршрутизатор вказує на те, що у його вхідному буфері 2 з'явилася ще одна вільна комірка. В такому випадку кількість кредитів для цього виходу маршрутизатора збільшується на одиницю. Створений wormhole маршрутизатор, до якого можна підключити п'ять вхідних та п'ять вихідних агрегованих логічних з'єднань (кількість фізичних з'єднань всередині агрегованих з'єднань можна змінювати довільно). Створена wormhole мережа на кристалі з агрегацією з'єднань, яка складається з вище згаданих маршрутизаторів, сполучених відповідно до топології "двовимірна решітка" розмірністю 8  8 (тобто кількість маршрутизаторів в мережі дорівнює 64). Чотири вхідних модуля 1 маршрутизатора використані для сполучення з сусідніми маршрутизаторами відповідно до вибраної топології, а через п'яте агреговане логічне з'єднання маршрутизатор за допомогою мережевого інтерфейса підключається до обчислювального модуля. Топологічно сусідні вузли мережі сполучені за допомогою двох агрегованих логічних з'єднань різної направленості. Розрядність фліта складає 16 бітів. Для обчислення маршрутної інформації використана завчасна (look-ahead), покоординатна х у маршрутизація. Керування потоком реалізується за допомогою механізму кредитів. Вхідні буфери 2 реалізовані у вигляді черг на базі регістрів, для яких дані на виході з'являються в тому ж циклі тактової частоти, коли відбувається запис у чергу. Як арбітри 8, 9 використані арбітри зі зсувом пріоритетів (round-robin arbiters). Процедура виділення фізичного каналу не конвеєризується і виконується за один цикл тактової частоти. Всього використовується два етапи конвеєру. На першому етапі фліт записується до вхідної черги, відбуваються операції маршрутизації та виділення фізичного з'єднання у вихідному агрегованому з'єднанні, на другому етапі конвеєра комутатор 3 сполучає голову (вихід) вхідної черги та вибране фізичне з'єднання на виході маршрутизатора, модуль керування 4 формує необхідні сигнали для вилучення фліта з черги поточного маршрутизатора та запису його у вхідну чергу наступного вузла мережі по передньому фронту наступного циклу тактової частоти. Тривалість кожного етапу конвеєра - один цикл тактової частоти. Тому для просування першого фліта пакета крізь маршрутизатор потрібно мінімум два цикли тактової частоти, а для просування наступних флітів може бути достатньо одного циклу тактової частоти. Описана конфігурація дозволяє отримати найбільше значення порогу насичення мережі за рахунок малої кількості етапів конвеєра. Для опису апаратури маршрутизаторів використана синтезована множина конструкцій мови System Verilog, а синтез самої мережі на кристалі успішно виконаний у середовищі Quartus II. Для реалізації одного маршрутизатора в елементній базі FPGA мікросхеми сімейства Stratix IVEP4SGX230KF40C2 використано 2077 комбінаційних комірок (lookup tables) та 1083 D-тригера (конфігурація з чергами довжиною 4 фліта та двома фізичними з'єднаннями на агрегований 9 UA 77040 U 5 10 15 20 25 30 35 40 45 50 55 канал). За результатами програми TimeQuest Timing Analyzer максимальна тактова частота функціонування пристрою склала 170 МГц. Для оцінки характеристик створеної мережі на мові System Verilog описаний "тестбенч", який складається з генераторів та приймачів трафіку, які імітують функціонал мережевого інтерфейсу та обчислювального модуля. До кожного маршрутизатора за допомогою агрегованих логічних з'єднань підключаються один генератор та один приймач трафіку. Також згаданий "тестбенч" створює сигнал тактової частоти для роботи системи та виконує початкову ініціалізацію всіх підсистем. Генератор трафіку створює пакети даних та з інтенсивністю  вводить їх у відповідний маршрутизатор. Іншими словами  показує, скільки в середньому флітів введено в маршрутизатор за цикл тактової частоти. Середнє значення параметрів  для всіх генераторів трафіку характеризує прикладене до мережі навантаження. Інтервали часу між інжекцією пакетів розподілені за експоненціальним законом і в середньому дорівнюють 1/. Для збереження характеристик розподілення за часом створені пакети перед введенням в мережу ставляться в чергу. Необхідність такого рішення обґрунтована в [13] на с. 450 та с. 456. Генератори трафіку інжектують пакети в мережу лише по одному фізичному з'єднанню агрегованого логічного каналу (Інші фізичні з'єднання агрегованого каналу між генератором трафіку та маршрутизатором не використовуються). Використання більшої кількості фізичних з'єднань лише покращить характеристики мережі, оскільки призведе до збільшення пропускної здатності агрегованих зв'язків між генератором трафіку та маршрутизатором. Для визначення просторового розподілення паї сетів обрано рівномірно випадковий закон, коли для будь-якого джерела трафіку вірогідність вибору того чи іншого приймача однакова. При цьому для кожного наступного пакету визначається новий пункт призначення. Приймач трафіку отримує з мережі призначені для нього пакети та вираховує транспортну затримку кожного пакета як кількість циклів тактової частоти з моменту створення пакету до моменту прийому останнього його фліта у пункті призначення. Час створення передається всередині пакета. До задач приймача трафіку також входить розрахунок середнього значення транспортної затримки. Після початку моделювання кожен з генераторів трафіку створює по 1100 пакетів та вводить їх в мережу, а розрахунок транспортної затримки приймачами починається після прийому перших ста пакетів. Це зроблено для забезпечення переходу мережі в усталений режим роботи [13]. Моделювання закінчується після прийому всіх відправлених пакетів. Для проведення моделювання використано середовище ModelSim 6.5. Для отримання залежності транспортної затримки мережі від прикладеного навантаження необхідно декілька разів виконати процедуру моделювання системи. Автоматизувати цей процес можна за допомогою створеного bashскрипту, який функціонує в середовищі Cygwin 1.7.7 і виконує серію прогонів моделі для різних значень . На фіг. 13 приведені результати досліджень по встановленню залежності між транспортною затримкою, прикладеним навантаженням та кількістю фізичних з'єднань всередині агрегованих логічних каналів для описаної мережі з агрегацією з'єднань. Для даного дослідження довжина черг мазшрутизаторів та розмір пакету складають чотири та п'ять флітів відповідно. На фіг. 13 криві (1), (2), (3) характеризують конфігурації мережі з одним, двома та чотирма фізичним з'єднаннями всередині агрегованого логічного каналу відповідно. Видно, що подвоєння числа фізичних з'єднань в агрегованому каналі приводить до збільшення порога насичення мережі та її пропускної здатності в два рази. В даному випадку максимальне значення порога насичення досягається для конфігурації з чотирма фізичними з'єднаннями і складає 0.77 від ємності мережі. Для порівняння на фіг. 14 показана залежність транспортної затримки від прикладеного навантаження для мережі, побудованої на базі маршрутизатора з віртуальними каналами Netmaker [14], структурна схема якого показана на фіг. 2. Оскільки Netmaker має відкритий вихідний код, який можна вільно завантажити з [14], автори отримали результати, приведені на фіг. 14 самостійно, використовуючи середовище ModelSim 6.5. На фіг. 14 криві (1), (2), (3) характеризують конфігурації з одним, двома та чотирма віртуальними каналами на один порт маршрутизатора відповідно. Максимальне значення порога насичення на фіг. 14 досягається для конфігурації з чотирма віртуальними каналами і складає 0.34 ємності мережі, що на 126 % менше, ніж результат, отриманий під час агрегації чотирьох фізичних з'єднань. Порівнюючи фіг. 13 та фіг. 14 можна зробити висновок, що мережа з агрегацією з'єднань, побудована на базі корисної моделі, що заявляється, дозволяє отримати значно більші (на 126 %) значення порога 10 UA 77040 U 5 10 15 20 25 30 35 40 45 50 насичення і пропускної здатності у порівнянні з мережею, яка побудована на базі маршрутизаторів з віртуальними каналами. На фіг. 15 показані результати моделювання (залежність транспортної затримки від прикладеного навантаження) мережі з агрегацією з'єднань, побудованої на базі корисної моделі, що заявляється та мережі, побудованої на базі маршрутизаторів Hermes з віртуальними каналами. Дані про залежність транспортної затримки від прикладеного навантаження для мережі Hermes та умови проведення моделювання взяті з [15]. Для даного дослідження у відповідності з [15] довжина черг та розмір пакета дорівнюють вісім та тисячу флітів відповідно. Крива (1) характеризує мережу Hermes, крива (2) характеризує мережу з агрегацією з'єднань. З фіг.15 видно, що для мережі з агрегацією з'єднань поріг насичення на 152 % більший, ніж для Hermes мережі. Середнє значення транспортної затримки до порогу насичення для мережі, яка реалізована на базі корисної моделі, що заявляється (крива 1), в чотири рази менше, ніж для Hermes мережі. Таким чином, вище наведене свідчить про ефективність запропонованої корисної моделі маршрутизатора з агрегацією з'єднань і всієї мережі в цілому у порівнянні з існуючими підходами та забезпечує досягнення зазначеного технічного результату. Джерела інформації:: 1. Bjerregaard Т., Mahadevan S.A survey of research and practices of network-on-chip// ACM Compiling Surveys. - 2006. - Vol.38, №1. - P. 1-51. 2. Angiolini F., Meloni P., Benini L. A layout-aware analysis of networks-on-chip and traditional interconnects for mpsocs // IEEE Trans, on CAD of Integr. Circ. and Syst. - 2007. - Vol. 26, № 3. - P. 421-434. 3. Lee H.G., Ogras U.Y., Marculescu R. On-chip communication architecture exploration: A quantitative evaluation of point-to-point, bus and network-on-chip approaches // ACM Transactions on Design Automation of Electronic Systems. - 2007. - Vol. 12, № 3. - P. 1-20. 4. Dally W., Towles B. Route packets, not wires: on-chip interconnection networks // Proceedings of the 38th annual Design Automation Conference (June 2001). - Las Vegas, USA. - P. 684-689. 5. Ehliar Α., Liu D. An FPGA based open source network-on-chip architecture // Proceedings of Fields Programable Logic and Applications International Conference (Aug. 2007). - Amsterdam, Netherlands. - P. 800-803. 6. Karol M.J., Hluchyj M.G., Morgan S.P. Input Versus Output Queueing on a Space-Division Packet Switch // IEEE Transactions on Communications. - 1987. - Vol. 35, № 12. - P. 1347-1356. 7. Peh L.S., Dally W.J. A delay model and speculative architecture for pipelined routers // International Symposium on High-Performance Computer Architecture (Jan. 2001). - Nuevo Leone, Mexico. - P. 255-266. 8. Mullins R., West Α., Moore S. Low-latency virtual-channel routers for on-chip networks // Proceedings of 31-th International Symposium on Computer Architecture (June 2004). - Munich, Germany. - P. 188-197. 9. Kavaldjiev N., Smit G.J., Jansen P.G. A virtual channel router for on-chip networks // Proceedings of IEEE International SoC Conference (Sep. 2004). - Santa Clara, USA. - P. 289-293. 10. Link aggregation, IEEE Standart 802.3ad, 2000. 11. IEEE Standart for Local and Metropolitan Area Networks-Link Aggregation, IEEE Standart 802.1 ax, 2008. 12. http://www.altera.com/literature/ug/ug_fifo.pdf 13. Dally W.J. Principles and Practices of Interconnection Networks / William James Dally, Brian Patrick Towles. - San Francisco: Morgan Kaufmann Publishers, 2004. – 550 p. 14. Netmaker. http://www-dyn.cl.cam.ac.uk/~rdm34/wiki 15. Mello Α., Tedesco L., Calazans N., Moraes F. Virtual channels in networks on chip: implementation and evaluation on Hermes NoC // in Proceedings of 18th Symposium Integrated Circuits and System Design (2005). - New York, USA, - P. 178-183. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 55 Маршрутизатор з агрегацією з'єднань, що складається з комутатора, модуля керування та N вхідних модулів, кожен з яких містить довільну кількість буферів, виходи яких підключені до інформаційних входів комутатора, виходи якого є інформаційними виходами маршрутизатора, модуль керування якого з'єднаний з входом керування комутатора та з інтерфейсами керування вхідних буферів, інші виходи модуля керування є управляючими виходами маршрутизатора, а інші входи модуля керування є управляючими входами маршрутизатора, який відрізняється 11 UA 77040 U тим, що інформаційні входи маршрутизатора сполучені з інформаційними входами буферів за допомогою бієктивного зв'язку. 12 UA 77040 U 13 UA 77040 U 14 UA 77040 U 15 UA 77040 U 16 UA 77040 U 17 UA 77040 U 18 UA 77040 U 19 UA 77040 U Комп’ютерна верстка С. Чулій Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 20