МЕТОДИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ДИНАМІЧНИХ ТОПОЛОГІЙ В МЕРЕЖАХ НА КРИСТАЛІ : МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ДИНАМИЧЕСКИХ ТОПОЛОГИЙ В СЕТЯХ НА КРИСТАЛЛЕ

Краткое описание

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»

На правах рукопису

ШПІЦЕР АНДРІЙ СТЕФАНОВИЧ

МЕТОДИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ДИНАМІЧНИХ ТОПОЛОГІЙ В МЕРЕЖАХ НА КРИСТАЛІ

Спеціальність 05.13.05 – «Комп‘ютерні системи та компоненти»

Дисертація на здобуття наукового ступеня кандидата технічних наук
Ідентичність всіх примірників дисертації засвідчую:
Вчений секретар спеціалізованої вченої ради
_________________ /Луцик Я.Т./
Науковий керівник
доктор технічних наук, професор
Дунець Роман Богданович

Львів-2013

ЗМІСТ
ВСТУП ................................................................................................................. 3
РОЗДІЛ 1. АНАЛІЗ НАПРЯМІВ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ МЕРЕЖ НА КРИСТАЛІ ........................................................................................... 11
1.1. Мережі на кристалі ................................................................................ 11
1.2. Топології МНК ....................................................................................... 13
1.3. Маршрутизація в МНК .......................................................................... 18
1.4. Аналіз алгоритмів маршрутизації ........................................................ 22
1.5. Аналіз алгоритмів сегментації .............................................................. 35
1.6. Висновки до розділу .............................................................................. 43
РОЗДІЛ 2. МЕТОД ПОШУКУ ТА ОБХОДУ СЕГМЕНТІВ МЕРЕЖІ НА КРИСТАЛІ ................................................................................................................. 44
2.1. Особливості алгоритму маршрутизації DyXY .................................... 44
2.2. Сегментація мереж на кристалі ............................................................ 49
2.3. Метод пошуку та обходу сегментів мережі на кристалі .................... 58
2.4. Оцінка пропускної здатності елементів у сегментованій мережі ..... 63
2.5. Оцінка ефективності методу SDyXY ................................................... 65
2.6. Висновки до розділу .............................................................................. 75
РОЗДІЛ 3. МЕТОД «ГОЛОВНИЙ-ПІДЛЕГЛИЙ» ........................................ 77
3.1. Задача усунення точок скупчення ........................................................ 77
3.2. Методи розв‘язання поставленої задачі ............................................... 80
3.3. Оцінка ефективності методу ................................................................. 91
3.4. Висновки до розділу .............................................................................. 95
РОЗДІЛ 4. СПЕЦІАЛІЗОВАНИЙ ПРОГРАМНИЙ ПРОДУКТ ОЦІНКИ ЕФЕКТИВНОСТІ АЛГОРИТМІВ МАРШРУТИЗАЦІЇ ДЛЯ МЕРЕЖ НА КРИСТАЛІ. ................................................................................................................ 96
4.1. Структура симулятора ........................................................................... 96
4.2. Графічний інтерфейс симулятора мережі на кристалі ..................... 105
4.3. Системні вимоги для симулятора MDTNoC. .................................... 113
4.4. Висновки до розділу. ........................................................................... 114
ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ. ............................... 115
ЛІТЕРАТУРА .................................................................................................. 117
ДОДАТКИ………………………………………………………………….126

ВСТУП
Актуальність теми. Тривалий час підвищення ефективності роботи комп‘ютерних систем та компонент проводилося в основному шляхом удосконалення технологій виробництва елементної бази, зокрема транзисторів. Із кожним роком мінімізація дозволяла підвищувати тактову частоту елементів, нарощувати кількість транзисторів на кристалі, а отже збільшувати продуктивність відповідно до закону Мура [1]. Проте з наближенням технології виробництва до молекулярного рівня збільшення продуктивності цим шляхом практично зупинилося. Тому протягом останніх десятиліть почали стрімко розвиватися методи побудови комп‘ютерних систем, що базуються на розпаралелюванні обчислень. У склад комп‘ютерних систем для підвищення продуктивності почали включати спеціалізовані пристрої (перемножувачі, кодери, відеоадаптери) [2, 3, 4, 5]. Більшість процесорів стали багатоядерними. Однак збільшення кількості таких пристроїв, у тому числі ядер процесорів, на практиці не перевищує 8-10, оскільки затрати часу на обмін інформацією між ними через системні шини суттєво зупиняють подальший ріст продуктивності [1].
В останні роки з метою підвищення ефективності комп‘ютерних систем з‘явилась тенденція до об‘єднання їх компонентів, що апаратно реалізуються в одному кристалі, в мережі, які отримали назву мережі на кристалі (МНК) [6]. Особливістю таких МНК є організація обміну інформацією між елементами мережі за допомогою пакетів даних, аналогічно обміну пакетами у глобальних та локальних комп‘ютерних мережах. Власне передачу пакетів даних забезпечують маршрутизатори комунікаційного середовища МНК, звільняючи при цьому від цієї роботи самі пристрої. Крім того, кількість елементів мережі в МНК обмежується лише технологічними можливостями їх реалізації в межах одного кристалу.
В першу чергу, праобразом мережі на кристалі є системи на кристалі.
4
Типова SoC вміщує [1]:
 мікроконтролер чи мікропроцесор. Деякі схеми обладнані більш ніж одним процесором (MPSoC – Multiprocessor System-on-Chip);
 блок пам'яті;
 кварцеві генератори тактових імпульсів;
 таймери, лічильники та ланцюги затримок;
 стандартні інтерфейси для зовнішніх пристроїв;
 цифро-аналогові і аналого-цифрові перетворювачі;
 регулятори напруги та стабілізатори живлення.
Щодо мережі на кристалі, то перехід від шини до мережі цілком закономірний. Підтвердженням цього є розвиток телекомунікаційних мереж: радіоефір – типова «шина», телефонні мережі – комутація каналів за допомогою матричних комутаторів, інтернет – комутація пакетів. Так само розвивалась і комп'ютерна периферія – сучасна шина PCI Express насправді зовсім не шина, а мережа з топологією типу зірка [7]. Так само розвиваються і процесори – спочатку прямі з'єднання між блоками, потім шини і матричні комутатори і, нарешті, мережі.
В архітектурі МНК кожне ядро або блок процесора розділений на безпосередньо обчислювальний пристрій та маршрутизатор. Маршрутизатор забезпечує спілкування з іншими блоками та об'єднує в мережу, по якій пакети даних відпраляються від одного блоку до іншого, так само як пакети у звичайній комп'ютерній мережі [9-11]. Як наслідок, розробники цифрових технологій отримали суттєве спрощення топологій мікросхеми та потужний потенціал щодо масштабування. Було проведено низку комп'ютерних моделювань та досліджено зразки багатоядерних процесорів. Отримані дані продемонстрували, що при великій кількості ядер така архітектура перевершує традиційну за багатьма показниками [12].
Природно, немає потреби та й безглуздо безпосередньо переносити логіку, протоколи та принципи роботи інтернету чи просто локальних мереж всередину кристалу. Тут зовсім інші технологічні обмеження та завдання:
5
жорсткі вимоги до затримок і енергоспоживання, стабільна архітектура та топологія, повністю контрольований та прогнозований процес роботи. Комутатори повинні працювати з наносекундними затримками і бути дуже економічними. Витрати енергії на передачу даних між блоками складають значну частину загального споживання сучасних кристалів. Комутатори на кристалі повинні займати мало місця, а значить не можуть мати складну логіку і великий розмір буфера.
Дослідженнями МНК займаються провідні компанії та університети світу. Так, у 2007 році Intel розробила експериментальний процесор із 80-ма ядрами і продуктивністю 1 терафлопс при енергоспоживанні всього 62 Вт. У 2010 був представлений 48-ядерний «Хмарний комп'ютер на кристалі» (Single chip cloud computer). У квітні цього року була опублікована робота групи вчених MIT, які створили прототип 16-ядерного процесора, в якому були застосовані специфічні для МНК-систем оптимізації - віртуальний обхід (virtual bypassing) і сигнали з малою амплітудою (low-swing signaling). Ці технології дозволили наблизитися до теоретичних меж пропускної здатності і затримок та помітно знизити енергоспоживання.
Чималий внесок у розвиток теорії побудови систем та мереж на кристалі зробили відомі українські та зарубіжні вчені В.С. Глухов, Р.Б. Дунець, А.О. Мельник, Я.М. Николайчук, В.П. Тарасенко, В.С. Харченко, Wael Badawy, Graham Jullien, Pieter Hooijmans, Bill Krenik.
Основну увагу в їхніх працях приділено створенню методів та засобів побудови власне високоефективних спеціалізованих пристроїв, проте значно менше уваги було надано методам маршрутизації пакетів у мережах на кристалі. Для обміну пакетами даних застосовувались відомі алгоритми маршрутизації, які враховували стани завантаженості лише сусідніх елементів і фактично переносили логіку роботи маршрутизаторів глобальних чи локальних мереж на МНК. У випадку, коли кількість елементів МНК перевищує півтора десятка, система комутації пакетів починає зменшувати загальну продуктивність МНК за рахунок втрат часу на переміщення пакетів у мережі. З
6
огляду на це актуальною є наукова задача зі створення ефективних методів маршрутизації пакетів у мережах на кристалі з матричною топологією.
Принцип роботи мереж на кристалі полягає у такому: маршрутизатор елемента-отримувача зберігає отриманий пакет у буфер, аналізує його заголовок і вирішує, передати його процесорному елементу чи відправити далі та куди його відправити. Virtual bypassing – одна з новинок у технології проектування комп‘ютерних мереж, що дозволяє передати пакет практично без затримок, завдяки тому, що заголовок надсилається заздалегідь, і комутатор встигає зробити потрібні перемикання ланцюгів до того моменту, як прийде тіло пакета. Таким чином, пакет іде без зупинок, минаючи буфер. Low-swing signaling ще одна новинка – дозволяє зменшити різницю між напругою логічних 0 і 1 в провіднику, завдяки тому вдалося додатково скоротити енергоспоживання. У сумі ці вдосконалення підвищують пропускну здатність і економічність більш ніж у півтора раза.
Крім покращення таких характеристик, як енергоспоживання і швидкість, архітектура МНК дозволяє легко об'єднувати не тільки однорідні ядра, а й взагалі будь-які блоки на одному кристалі. Таким чином, розробники отримали можливість проектувати складні обчислювальні середовища, майже не витрачаючи часу на розробку ефективної архітектури, топології чи найкращого трасування зв‘язків. Як і в комп'ютерних мережах, фізичний і транспортний рівні працюють однаково для будь-яких типів даних і протоколів. Можна без особливих проблем поставити на місце одного або декількох універсальних обчислювальних ядер будь-який інший IP-блок, наприклад, графічне ядро, спеціалізований сигнальний процесор або контролер будь-якого пристрою. І так само як і в мережах, можна реалізувати підтримку Quality of Service на рівні кристала, що може бути корисно для систем реального часу і віртуалізації.
МНК для об'єднання ядер процесорів поки що мають експериментальний статус, однак для об'єднання різнорідних блоків у системах на кристалі МНК розробляються і застосовуються досить давно. Рішення таких компаній, як Sonics або Arteris використовуються в мікросхемах Samsung, Qualcomm і навіть
7
Intel. Можливо, вже скоро мережева архітектура почне витісняти шини з багатоядерних центральних процесорів. І тоді число ядер знову почне стрімко зростати. Так що закон Мура може отримати нове дихання.
Для вирішення специфічних завдань використовуються мережі з неоднорідною топологією [6].
Незважаючи не велику кількість топологій, домінуючою є матрична (сітка). Матриця дозволяє легко налаштувати систему на задану задачу, проста в обслуговуванні, логічно зрозуміла, найлегше масштабується та реконфігурується. До того ж матриця лежить в основі більшості інших топологій, таких як тор, складчастий тор чи навіть гіперкуб. Саме тому маршрутизації в матричних топологіях приділено чи не найбільшу увагу. Як наслідок, найбільшого розвитку зазнав алгоритм XY, спеціалізований під матричну топологію. На його основі створене ціле сімейство алгоритмів, які розглядаються нижче. Кожен із цих алгоритмів намагається вирішити основні завдання, які стоять перед розробником мережі на кристалі: мінімізація вартості апаратного забезпечення, оскільки існує гостра потреба мінімізувати споживання енергії та площі мікросхеми, скоротити час розробки, спростити процес розробки та ін.
Проте задача розробки ефективних алгоритмів маршрутизації для мереж на кристалі залишається актуальною і в нас час. Маршрутизація в мережах на кристалі характеризується затримкою пакетів у мережі і пропускною здатністю.
Маршрутизація вважається доброю, якщо:
 вдається зменшити затримку пакетів;
 збільшити пропускну здатність;
 оминути перевантажені вузли.
У розробці алгоритмів маршрутизації моделювання є одним із основних етапів. Зважаючи на складність об'єкта дослідження, доцільно використати імітаційне моделювання.
8
Зв'язок роботи з науковими програмами, планами, темами. Тема дисертаційної роботи відповідає науковому напряму кафедри спеціалізованих комп‘ютерних систем. У дисертаційній роботі розробка методів підвищення ефективності динамічних топологій у мережах на кристалі виконувалася в межах науково-дослідницької роботи «Вдосконалення теорії проектування NoC з матричною топологією» (номер державної реєстрації 0112U006717).
Мета і задачі дослідження. Метою дисертаційної роботи є підвищення ефективності роботи мережі на кристалі з матричною топологією шляхом вдосконалення маршрутизації пакетів із врахуванням поточного стану елементів мережі та сегментів. Для досягнення поставленої мети у роботі потрібно вирішити такі основні задачі:
 вдосконалити алгоритм DyXY, забезпечивши йому можливість проводити аналіз стану завантаженості не тільки безпосередніх елементів, а й цілих сегментів мережі;
 розробити метод сегментації мереж на кристалі для виявлення критичних зон та прийняття рішень для їх усунення;
 розробити методи уникнення точок скупчення, як у межах одного елемента, так і цілих сегментів.
Об’єктом дослідження є засоби маршрутизації в мережах на кристалі з матричною топологією.
Предметом дослідження є методи та алгоритми маршрутизації в мережах на кристалі та точки скупчення.
Методи дослідження ґрунтуються на математичних моделях Дейкстри, Белмана-Форда, Флойда-Уоршелла, теорії комп‘ютерних систем та мереж, теорії моделювання, теорії алгоритмів.
Наукова новизна одержаних результатів. Завдяки проведеним дослідженням розв‘язано наукову задачу підвищення ефективності маршрутизації в мережах на кристалі з матричною топологією на основі обробки даних про роботу мережі в цілому та її складових елементів. При цьому отримано такі результати:
9
 вперше запропоновано метод уникнення точок скупчення та забезпечення рівномірного завантаження мережі за принципом «Головний-Підлеглий» шляхом аналізу завантаженості безпосередніх сусідів елементу, що дозволило розвантажити локальні ділянки мережі на кристалі, залучивши до обчислювальних процесів низько завантажених сусідів;
 вперше запропоновано метод уникнення точок скупчення шляхом організації опосередкованих зв‘язків у однорідних топологіях мереж на кристалі з високим трафіком, що дозволило знаходити альтернативні легко прохідні шляхи та зменшити час руху пакета опосередкованими зв‘язками;
 вдосконалено метод сегментації, що базується на алгоритмі Краскала, шляхом введення критерію завантаженості елементів мережі, що дало змогу виявляти сегменти елементів мережі на кристалі з однаковим рівнем їх завантаженості;
 вдосконалено метод маршрутизації DyXY шляхом аналізу стану завантаженості сусідніх елементів та секторів, що дало можливість уникати ділянок мережі на кристалі з високим ризиком виникнення тупиків і затримок та отримати у загальному випадку підвищення ефективності близько 5%, а в окремих випадках – до 30%.
Практичне значення одержаних результатів полягає у такому:
Розроблено та впроваджено систему пошуку оптимальних маршрутів у транспортній логістиці на основі створеного методу сегментації мережі, що дало змогу локалізувати сегменти, які можуть спричиняти простої транспортних засобів.
Методи покращення ефективності маршрутизації в мережах використані в програмних засобах для вирішення задач керування трафіком на серверах системи SalesWorks для розв‘язку тестових задач у компанії «СофтСерв».
Запропоновано спосіб рівномірного завантаження залізничних вузлів ДТГО «Львівська залізниця», що ґрунтується на системі «Головний-Підлеглий», який моніторить стан залізничного сполучення та на основі
10
отриманих даних розвантажує критичні вузли шляхом пошуку обхідних маршрутів та залучення до роботи вузлів із нижчою завантаженістю.
Методи, представлені в дисертаційній роботі, також можуть бути застосовані в підприємствах: «Конекс», Львівському відділенні НКАУ, «Прості програмні системи», можуть бути адаптовані до будь-яких логістичних програмних чи апаратних засобів систем із маршрутизацією.
Особистий внесок здобувача. Основні наукові і практичні результати дисертаційної роботи були отримані автором особисто. У роботах, написаних у співавторстві, дисертантові належать: [72] розроблено теоретичне підґрунтя застосування принципу «Головний-Підлеглий» для розв‘язання проблеми точок скупчення; [76] розроблено теоретичне підґрунтя вдосконалення алгоритму маршрутизації DyXY для забезпечення йому можливості аналізу завантаженості не тільки сусідніх елементів, а й цілих сегментів; [77] розглянуто особливості матричних топологій та обґрунтовано доцільність їх використання в дослідженні як базових для інших найпоширеніших топологій.
Апробація результатів дисертації. Основні положення й результати роботи прозвучали в доповідях і були обговорені на таких науково-технічних конференціях: First International Workshop Critical Infrastructure Safety and Security CrISS-DESSERT 2011 (Kharkiv, 2011); 6th International Conference DESSERT‘12 «Characteristics of complexity of multiplication devices» (Sevastopol, 2012); Міжнародній науково-практичній конференції «Інформаційні технології в освіті, науці і виробництві», (Луцьк, 2011); 5-th International Conference Advanced Computer System and Networks: Design and Application, (Lviv, 2011); XVI международном молодежном форуме «Радиоэлектроника и молодежь в ХХІ веке» (г. Харьков, 2012); Науковому семінарі Секції інформатики при Західному науковому центрі НАН України та МОН України (Львів, 2013) та наукових семінарах кафедри спеціалізованих комп‘ютерних систем.
Публікації. За темою дисертаційної роботи надруковано 8 наукових праць, із них 6 у фахових виданнях (з них одноосібних – 5) та 2 публікації у матеріалах наукових конференцій.

Список литературы

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ.
У роботі розв‘язано актуальну наукову задачу підвищення ефективності роботи мережі на кристалі з матричною топологією шляхом вдосконалення маршрутизації з урахуванням поточного стану елементів мережі та отримано такі результати:
1. Проаналізовано основні напрямки підвищення ефективності мереж на кристалі і показано, що одним із перспективних шляхів є вдосконалення методів маршрутизації, а також проведено аналіз динамічних топологій мереж на кристалі та виділено для дослідження матричну топологію, яка є базовою для решти динамічних топологій.
2. На основі аналізу відомих алгоритмів маршрутизації зроблено висновок про те, що базовим алгоритмом для мереж на кристалі з матричною топологією є алгоритм DyXY. Проаналізовано особливості алгоритму DyXY і показано, що збільшення ефективності його роботи може бути досягнуто шляхом сегментації мережі.
3. На основі аналізу відомих алгоритмів сегментації визнано найбільш придатним для подальших досліджень алгоритм Краскала, який модифіковано шляхом введення критерію завантаженості, що дало змогу виявляти сегменти елементів мережі на кристалі з однаковим рівнем їх завантаженості.
4. Вдосконалено метод пошуку та обходу сегментів шляхом аналізу стану зайнятості не тільки сусідніх елементів, але й цілих сегментів, що дало змогу уникати ділянок маршрутів на кристалі з високим ризиком тупиків та затримок.
5. Отримано аналітичні вирази оцінки пропускної здатності елемента у сегментованій мережі та пропускної здатності сегментів, що дало змогу проводити оцінку пропускної здатності альтернативних маршрутів.
6. Показано, що метод SDyXY у загальному випадку забезпечує підвищення ефективності близько 5% порівняно з методом DyXY, а в окремих випадках – 30%.
116
7. Розроблено метод за принципом системи «Головний-Підлеглий» шляхом аналізу завантаженості безпосередніх сусідів елемента, що дозволило уникати точки скупчення та забезпечития рівномірне завантаження мережі.
8. Проведено моделювання даного методу та визначені умови найбільш ефективного використання даної системи, а саме: середня завантаженість мережі повинна бути низькою або слабо завантаженою (переважна більшість елементів мережі повинна мати завантаженість меншу за 80%); кількість пакетів повинна бути достатньою, щоб забезпечити роботою всіх вільних підлеглих сусідів (якщо вільних підлеглих є n, то пакетів повинно бути не менше ніж n+1); параметр time to live повинен бути достатнім, щоб система змогла розпаралелити роботу. В таких умовах можливо досягнути покращення ефективності приблизно вдвічі.
9. Розроблено метод уникнення точок скупчення шляхом організації опосередкованих зв‘язків в однорідних топологіях мереж на кристалі з високим трафіком, що дозволило знаходити альтернативні легко прохідні шляхи та зменшити час руху пакета опосередкованими зв‘язками майже вдвічі.
10. Розроблено програмне забезпечення симулятора мережі на кристалі MDTNoC та описано структурну та функціональну будову програмного продукту, яка організована за модульним принципом, що дає змогу модернізувати чи використовувати альтернативні програмні продукти та компоненти. Розроблені зручні, інтуїтивно зрозумілі користувацькі інтерфейси: панелі керування; панелі відображення поточних результатів; модуля сегментації; елемента та пакета; системи автотестування. Програмний продукт розроблений для використання в середовищі Microsoft Windows та потребує встановлення .Net фреймворку 4,0 або вище та офісного пакету Microsoft Office, зокрема компоненти Excel.

ЛІТЕРАТУРА
1. Николайчук Я.М. Проектування спеціалізованих комп‘ютерних систем: навчальний посібник / Я.М.Николайчук, Н.Я.Возна, І.Р.Пітух. – Тернопіль: ТзОВ «Терно-граф», 2010. – 392с.
2. Паралельные вычисления на GPU. Архитектура и програмная модель CUDA: Учебное пособие / А.В.Боресков и др. Предисл.: В.А.Садовничий. – М.: Издательство Московского университета, 2012. – 336 с.
3. Мельник А.О. Персональні суперкомп‘ютери: архітектура, проектування, застосування / А.О.Мельник, В.А.Мельник. – Львів: Видавництво Львівської політехніки, 2013. – 516 с.
4. Мельник А.О. Технологія проектування комп‘ютерних пристроїв для високопродуктивних реконфігурованих прискорювачів / А.О.Мельник // Радіоелектронні та комп‘ютерні системи. – 2008. – №6(33). – С. 88-92.
5. Глухов В.С. Оцінювання апаратних витрат на реалізацію багаторівневої комп‘ютерної системи з врахуванням закону Амдаля / В.С. Глухов // Комп‘ютерні науки та інформаційні технології. – Львів: Видавництво Львівської політехніки, 2010. – С. 17-23.
6. E. Bolotin QNoC: QoS architecture and design process for network on chip // Journal of Systems Architecture. – 2004. - vol. 50, no. 2–3. - P. 105–128
7. Дунець Р.Б. Аналіз та синтез топологій комп‘ютерних видавничо-поліграфічних систем: Монографія / Р.Б.Дунець. - Львів: НВФ «Українські технології», 2003. – 192 с.
8. Structured interconnect architecture: a solution for the non-scalability of busbased SoCs / C.Grecu, P. P.Pande, A.Ivanov, R.Saleh. – New Jersey: Press Piscataway, 2004. – 192-195 pp.
9. Основи побудови перспективних безпроводових сенсорних мереж: Монографія / М.Д.Гераїмчук, О.В.Івахів, М.І.Паламар, Б.М.Шевчук. – Київ: ЕКМО, 2010. – 124 с.
118
10. Varescaux. Т.М. Mapping and management of communication services on MP-SoC platforms / T.M. Varescaux. – Eindhoven: Technische Universitet Eindhoven, 2007. – с. 305
11. Столлингс В. Современные компьютерные сети: 2-е изд. / В. Столлингс. - СПб.: Питер, 2003. - 783 с.
12. Benini L. Networks on chips: a new SOC paradigm / L.Benini and G.D.Micheli. – Italy: Bologna Univerіiat, 2002. - Computer №35 (1). – P.70-78
13. Rantala V. Network on Chip Routing Algorithms / V. Rantala, T. Lehtonen, J. Plosila // TUCS Technical Report. – Turku: University of Turku, 2006. - №779. – 34 p.
14. Арсенюк, І. Р. Комп‘ютерні мережі. Ч. 2 : навчальний посібник / І. Р. Арсенюк, А. А. Яровий. – Вінниця: ВНТУ, 2010. – 145 с.
15. Cisco CCIE Fundamentals: Network Design and Case Studies, Chapter 14 [Електронний ресурс]. – Режим доступу: http://www.cisco.com/
16. Badawy W. System-on-chip for real-time applications / W. Badawy, G. Jullien. – Kluwer: Springer, 2003. – 456 p.
17. Multiprocessor-based real-time control of a moving object / O. Nakov, P. Borovska, N. Kuchmova, D. Andreeva // 8th WSEAS Int. Conf. on Applied Computer and Applied Computational Science. – Hangzhou: Zhejiang University of Technology, 2009. – 495-499 p.
18. Understanding of Human Interferon Gamma Binding / L. Litov, P. Petkov, S. Markov, N. Ilieva. – Kavala: Computer Science Conference and International Workshop on BioComputing, 2008. – p. 37-42
19. SonicsSX On-Chip Network. Datasheet [Електронний ресурс]. – 2012. - Режим доступу: http://sonicsinc.com/wp-content/uploads/2012/10/Sonics_Datasheet_SonicsSX.pdf
20. Swain A.K. Design and verification of wishbone bus interface for soc integration / A.K. Swain . – Orissa: National Institute of Technology, 2010. – 138 р.
119
21. Дунець Р.Б. Аналіз та синтез топологій комп‘ютерних видавничо-поліграфічних систем: Монографія / Р.Б.Дунець - Львів: НВФ «Українські технології», 2003. – 192 с.
22. Дунець Б.Р. Базові архітектури пристроїв комутації пакетів з багатоканальною вхідною буферизацією / Р.Б Дунець // Збірник наукових праць: Комп‘ютерні технології друкарства №11. – Львів, 2004. – С.43-49.
23. Дунець Б.Р. Архітектура контролера доступу до багатоблокової пам‘яті // Р.Б Дунець / Збірник наукових праць: Комп‘ютерні технології друкарства №8. - Львів, 2002. - С.33-39.
24. Dally W.J. The torus routing chip. Distriduted Computing / W.J. Dally and C.L. Seitz // Journal of Distriduted Computing. – California: California Institute of Technology, 1986. – P. 187-196
25. Cisco Systems Руководство Cisco по междоменной многоадресатной маршрутизации. — М.: «Вильямс», 2004. — С. 320. — ISBN 5-8459-0605-9.
26. Ant Colony Based Routing Architecture for Minimizing Hot Spots in NOCs / M.Daneshtalab, A.Sobhani, M. D.Mottaghi, A.A.Kusha, Z.Navabi, O.Fatemi // Proceedings of the 19th annual symposium on Integrated circuits and systems design. – Tehran: University of Tehran, 2006. - P. 56-61.
27. Patooghy A. XYX: A Power & Performance Efficient Fault-Tolerant Routing Algorithm for Network on Chip / A. Patooghy, S.G. Miremadi // Proceedings of the17th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing. – Weimar: Sharif University of Technology, 2009. – P. 245-251
28. Evaluation of pseudo adaptive XY routing using an object oriented model for NOC / M. Dehyadgari, M. Nickray, A. Afzali-kusha, Z. Navabi // Proceedings of the17th International Conference on Microelectronics. – Tehran: University of Tehran, 2005. - 361 p.
29. A NoC Simulation & Verification Platform based onSystemC / S. Chai, C. Wu, Y. Li, Z. Yang // Proceedings of the International Conference on Computer
120
Science and Software Engineering. – Hubei: University of Electronic Science and Technology of China, 2008. – 471 p.
30. A Light Weight Parallel Router for FPGA based Networks on Chip / B. Sethuraman, P. Bhattacharya, J. Khan, R. Vemuri // Proceedings of the 15th ACM Great Lakes symposium on VLSI. - New York:ACM, 2005. – P. 452-457
31. Towles B. Worst-case Traffic for Oblivious Routing Functions / B. Towles, W. J. Dally // Computer Architecture Letters №1 (1). – Stanford: Stanford University, 2002. – P.4
32. DyXY: a proximity congestion-aware deadlock-free dynamic routing method for network on chip / M.Li, Q.Zeng, W.Jone // Proceedings of the 43rd annual Design Automation Conference. - San Francisco: CA, 2006. – P. 849 - 852
33. Di Caro G. AntNet: Distributed Stigmergetic Control for Communications Networks / G.Di Caro, M.Dorigo // Journal of Artificial Intelligence Research. – Brussels: IRIDIA, 1998. - №9. - P. 317-365
34. Bolotin E. QNoC: QoS Architecture and Design Process for Networks on Chip / E. Bolotin I. Cidon, R. Ginosar, A. Kolodny // Journal of system architecture. – Haifa: Technion––Israel Institute of Technology, 2004. – 18 p.
35. Modares H. Solving nonlinear optimal control problems using a hybrid IPSO–SQP algorithm / H. Modares, M.Sistani // Engineering Applications of Artificial Intelligence. – Mashhad: Ferdowsi University of Mashhad, 2011. – №24 (3). – P. 476–484.
36. Adaptive Stochastic Routing in Fault-tolerant On-chip Networks / W.Song, D. Edwards, J.Nu˜nez-Ya˜nez, S.Dasgupta // Proceedings of the3 rd ACM/IEEE International Symposium on Networks-on-Chip. - San Diego: University of Manchester, 2009. – P.32-37
37. Application Specific Routing Algorithms for Networks on Chip / M. Palesi, R. Holsmark, S. Kumar, V. Catania // Parallel and Distributed Systems, IEEE Transactions on. – Catania: University of Catania. - № 20 (3). – P. 316-330
38. Routing Table Minimization for Irregular Mesh NoCs / E. Bolotin, I. Cidon, R. Ginosar, A. Kolodny // Proceedings of Design, Automation & Test in
121
Europe Conference & Exhibition. – Canada: EDA Consortium San Jose, 2007. – P. 942-947
39. Yan S. Joint multicast routing and network design optimisation for networks-on-chip / S.Yan B.Lin // Proceedings of the IET Computers & Digital Techniques. – London: Institution of Engineering and Technology, 2008. – P. 443 - 459
40. A New Routing Algorithm for Irregular Mesh NoCs / V. Samadi Bokharaei, A.Shamaei, H.Sarbaziazad, M.Abbaspour // Proceedings of the International SoC Design Conference. – Busan: Institute of Electrical and Electronics Engineers ( IEEE ), 2008. – P.260-264
41. Fully Adaptive Fault-Tolerant Routing Algorithm for Network-on-Chip Architectures / T. Schonwald, J. Zimmermann, O. Bringmann, W. Rosenstiel // Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools. – Lubeck: Institute of Electrical and Electronics Engineers ( IEEE ), 2007. – P. 527 – 534
42. Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs / A. Mejia, M. Palesi, J. Flich, S. Kumar, P. López // Transactions on very large scale integration (vlsi) systems VOL. 17, NO. 3, - Institute of Electrical and Electronics Engineers ( IEEE), - 2009. – P.156 – 369
43. A Predominant Routing for On-Chip Networks / A. Asad, M. Seyrafi, A. Zonouz, M. Soryani, M. Fathy // Proceedings of the 4th International Design and Test Workshop (IDT).- Riyadh: Institute of Electrical and Electronics Engineers ( IEEE ), 2009. – P. 1-6
44. Kohler A. Fault Tolerant Network on Chip Switching With Graceful Performance Degradation / A.Kohler, G.Schley, M. Radetzki // EEE Transactions on Computer-Aided Design of Integrated Circuits and Systems - Special issue on the 2009 ACM/IEEE international symposium on networks-on-chip. – New Jersey: Press Piscataway, 2010. – P. 883-896
45. Мудров В.И. Задача о коммивояжере / В.И. Мудров. — Москва.: «Знание», 1969. — 62 с.
122
46. Ананий В. Метод грубой силы: Задача коммивояжера / В. Ананий, И. Левитин // Алгоритмы: введение в разработку и анализ — Москва: Вильямс, 2006. — С. 159-160
47. Шпіцер А.С. Стислий огляд методів сегментації та адаптація одного з них для рішення задачі сегментації мережі за критерієм завантаженості елементів / А.С.Шпіцер // Науково-технічний журнал «Радіоелектронні і комп‘ютерні системи». – Харків: НАУ ХАІ, 2012. - С.95-99
48. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - Москва: МЦНМО, 1990. – 325 с.
49. Загоруйко Н. Г. Гипотезы компактности и -компактности в методах анализа даннях / Н.Г. Загоруйко // Сибирский журнал индустриальной математики. - Новосибирск: Институт математики при финансовой поддержке ФЦП ―Интеграция‖, 1998. – С. 114–126.
50. Гонсалес Р. Цифровая обработка зображений / Р. Гонсалес, Р.Вудс. – Москва: Техносфера, 2005. – 621 с.
51. Прэтт У. Цифровая обработка зображений / У. Прэтт. – Москва: Мир, 1982. – т. 1-2. - 311-479 с.
52. Робертс Л. Автоматическое восприятие трехмерных объектов / Л. Робертс // Интегральные роботы. – Москва: Мир, 1973. – т.1. – С.162–208
53. Sob el I. E. Camera Models and Machine Perception. Ph.D. thesis / I.E.Sob el. - Alto, Calif.: Stanford University, 1970. – 99 p.
54. Prewitt J. M. S. Object Enhancement and Extraction. Picture Processing and Psychopictorics. - New York: Academic Press, 1970. - pp. 75–150.
55. Фурман Я. А. Введение в контурный анализ и его приложения к обработке изображений и сигналов / Фурман Я. А., Кревецкий А. В., Передреев А. К., и др. – Москва: Физматлит, 2003. – 297 с.
56. Clark J. J. Authenticating Edges Produced by Zero-Crossing Algorithms / J.J. Clark // IEEE Trans. Pattern Analysis Machine Intelligence. – Washington: IEEE Computer Society Washington, 1989. - №12 (8). – pp. 830–831.
123
57. Rosenfeld A. Digital Picture Processing / A. Rosenfeld, A. C. Kak. - New York: Academic Press, 1982. - vol. 1 and 2. – 435 p
58. Serra J. / Image Analysis and Mathematical Morphology // New York: Academic Press, 1988 - vol. 2. – 610 p
59. Gasteratos A. Special issue on Mathematical Morphology and Nonlinear Image Processing. Pattern Recognition / A.Gasteratos, I. Andreadis // Journal of Systems Architecture. – North-Holland,2000. - №6 (33). - pp. 875–1117.
60. A Survey of Thresholding Techniques. Computer Vision, Graphics, Image Processing / P.K. Saho, S. Soltani, A.K.C. Wong, Y.C. Chan. India: Allied Publishers Private Limited. – 1988. - vol. 4. - pp. 233–260.
61. Jain R. Machine Vision / R. Jain, R. Kasturi, B. Schunk. - New York: McGraw-Hill, 1995. – p.549
62. Fu K.S. A Survey of Image Segmentation. Pattern Recognition / K.S.Fu, J.K.Mui. – Berlin: Springer, 1981. - №1 (13). - pp. 3–16.
63. Haralick R.M. Image Segmentation Techniques. Computer Vision, Graphics, Image Processing / R.M. Haralick, L.G. Shapiro. Massachusetts: Academic Press, 1985. - №2 (29). – pp. 100–132
64. Haralick R.M. Computer and Robot Vision / R.M. Haralick, L.G. Shapiro. - Addison-Wesley: MA, 1993. - vol. 2. - 672 p. 65. Shapiro L.G. Computer Vision: A Modern Approach / L.G. Shapiro, G.C. Stockman. – Ney Jersey: Prentice Hall, Upp er Saddle River, 2001. – 610 p.
66. Дуда Р. Распознавание образов и анализ сцен / Р.Дуда, П.Харт. – Москва: Мир, 1976. – 509 с.
67. Jain A.K. Algorithms for Clustering Data / A.K. Jain, R.C. es Dub. – New Jersey: Prentice Hall, 1988. – 320p.
68. Matas J. Spatial and Feature Space Clustering: Applications in Image Analysis / J. Matas, J. Kittler // Proceedings of the 6th International Conference on Computer Analysis and Patterns. – Prague: Springer, 1995. – 960 p.
69. Батько Ю.М. Метод сегментації зображень на основі попередніх розміток зображення / Ю.М. Батько, О.М. Березький, Г.М. Мельник //
124
Матеріали 4-ї Міжнародної науково-технічної конференції: Комп‘ютерні науки та інформаційні технології 2009. – Львів, 2009. – С. 48-51.
70. Батько Ю.М. Метод і алгоритми сегментації біомедичних зображень на основі попередніх розміток / Ю.М. Батько // «Штучний інтелект» – Донецьк, 2010. – №4. - С. 140-149.
71. Шпіцер А.С. Інструментальний засіб сегментації мережі на кристалі / А.С. Шпіцер // Материалы XVI международного молодежного форума «Радиоелектроника и молодежь в ХХІ веке». – Харків, 2012. – С.15-16.
72. Шпіцер А.С. Метод підвищення продуктивності роботи мереж на кристалі на основі рівномірного завантаження її сегментів / А.С. Шпіцер, Ю.І. Бережанський, Р.Б. Дунець // Вісник Національного університету «Львівська політехніка». - Львів: Видавництво національного університету «Львівська політехніка», 2010. - № 688. - 224-228 с.
73. Мatlab. Primer [Електронний ресурс]. – МathWorks, 2013. – Режим доступу: http://www.mathworks.com/help/pdf_doc/matlab/getstart.pdf
74. Baudin M. Introduction to Scilab / M. Baudin. – France: The Scilab Consortium – Digiteo, 2010. – 87 c.
75. Шпіцер А.С. Аналіз ефективності алгоритму комутації пакетів у NoC з врахуванням інформації про стани елементів / А.С.Шпіцер, Р.Б.Дунець // Міжвузівський збірник «Комп‘ютерно інтегровані технології: освіта, наука, виробництво». - Луцьк: Видавництво Луцького національно-технічного університету, 2011. - №5. – С.308-316.
76. Spitzer A. Method of switching packets in networks on chip with matrix topology / A. Spitzer, R. Dunets // Journal of Information, Control and Management Systems. – Slovakia: Faculty of Computer Science and Informatics at Žilina university, 2012. - vol 10, № 1. – P.105-111.
77. Шпіцер А.С. Метод розв‘язання проблеми hot-spot в алгоритмах на базі XY алгоритму шляхом організації системи головний-підлеглий А.С.Шпіцер // Науковий вісник Чернівецького університету імені Юрія
125
Федьковича. – Чернівці: Видавництво Чернівецького національного університету, 2013. – № 636. – С.48-53.
78. Шпіцер А.С. Метод підвищення продуктивності роботи мереж на кристалі на основі пошуку слабо завантажених сегментів – коридорів А.С. Шпіцер // Матеріали конференції Сучасні комп‘ютерні системи та мережі: розробка та використання (ACSN 2011). – Львів: Видавництво національного університету «Львівська політехніка», 2011. – С.72-74.
79. Дунець Р.Б. Метод передачі пакетів у мережах на кристалі з матричною топологією / Р.Б.Дунець // Комп‘ютерні системи та мережі. – Львів: Видавництво національного університету «Львівська політехніка», 2010. – С. 101-105.