Автоматизований топологічний синтез тороїдально-решітчастих комунікаційних мереж

Размещено на http://www.allbest.ru

Полтавський національний технічний університет імені Юрія Кондратюка

Факультет інформаційних та телекомунікаційних технологій і систем

Кафедра комп'ютерної інженерії

Пояснювальна записка

до дипломної роботи бакалавра

на тему

Автоматизований топологічний синтез тороїдально-решітчастих

комунікаційних мереж

Виконав: студент 4 курсу, групи 402-ТК

6.05010201 «Комп'ютерна інженерія»

Ярміш М.І.

Керівник: Тиртишніков О. І.

м. Полтава 2017

РЕФЕРАТ

Пояснювальна записка до дипломної роботи на тему «Автоматизований топологічний синтез тороїдально-решітчастих комунікаційних мереж» має __ сторінок формату А4. Вона складається з переліку скорочень і умовних позначень; вступу; трьох розділів; висновків; списку використаних джерел, містить 11 рисунків і 2 таблиці. В роботі використано 20 науково-технічних джерела, з них - 3 англомовних.

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

Об'єктом дослідження є КМ тороїдально-решітчастого типу масивно-паралельних МПКС.

Предметом дослідження є топологічні властивості КМ тороїдально-решітчастого типу довільної розмірності, можливості автоматизації їх топологічного синтезу.

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

Метод дослідження - аналітичний.

Основним науковим результатом дослідження є метод пошуку максимально компактної ТС тороїдально-решітчастого типу заданого розміру. Основні практичні результати - алгоритм та програма, що реалізують вказаний метод, а також обчислюють значення основних топологічних метрик знайденої структури.

Дипломна робота складається з одного розділу теоретичного характеру та двох практичних.

Ключові слова: тороїдально-решітчасті комунікаційні мережі, гіперкуб, гіперрешітка, гіпертор, топологічна структура комунікаційної мережі.



ABSTRACT

Explanatory note to the thesis on the subject "Automated topological synthesis of toroidal-lattice communication networks" have 51 pages of the A4 format. It consists of the list of reductions and symbols; to the introduction; 3-oh sections; conclusions; to the list of the used sources, contains 11 drawings and 2 tables. In work scientific and technical sources, from them - 21 English-speaking are used 3.

Modern massive-parallel multiprocessor computers system incorporate of toroidal-lattice communication networks, and the tendency concerning increase in dimension and a complication of structure of networks therefore the subject of work is rather urgent is observed.

Object of a research is toroidal-lattice network for massive-parallel multiprocessor computers systems.

Subject of research is topological properties of toroidal-lattice network any dimension, a possibility of automation of their topological synthesis.

The purpose of research is development generalized formalized approach for synthesis topological structure computer network of toroidal-lattice type of any dimension which creates possibilities of automation of topological synthesis of structures of the specified type.

Research method - analytical.

The main scientific result of research is method of search the most compact topological structure of toroidal-lattice type given size. The main practical results - the algorithm and the program that realize the specified method, and also calculate value of the main topological metrics of the found structure.

The thesis consists of one theoretical sections and two practical section.

Keywords: toroidal-lattice communication networks, hypercube, hyperlattice, hipertor, topological structure of communication network.



ПЕРЕЛІК СКОРОЧЕНЬ І УМОВНИХ ПОЗНАЧЕНЬ

КМ - комунікаційна мережа

КС - комп'ютерна система

МПКС - мультипроцесорна комп'ютерна система

ПЕ - процесорний елемент

ТС - топологічна структура

FIFO - first in, first out (першим увійшов, першим вийшов)



ВСТУП

На всьому протязі розвитку МПКС їх «еволюція» відбувалася у напрямку збільшення кількості процесорів (обчислювальних вузлів). Поступово стало очевидним, що у великих МПКС КМ є ключовою підсистемою з точки зору забезпечення високої продуктивності та надійності функціонування системи в цілому [1,4,6,12,19]. Вимоги до швидкодії, пропускної здатності та відмовостійкості КМ постійно підвищуються, тому для сучасних КМ МПКС характерно стрімке збільшення розмірів, порядку вузлів та, відповідно, ускладнення їх ТС [1,6,9,20].

Серед паралельних обчислювальних систем (суперкомп'ютерів) найбільш масштабними та потужними є масивно-паралельні КС. В них - від «історичних» до найсучасніших - широко застосовуються КМ, топології яких утворюють клас тороїдально-решітчастих структур - n-розмірні тори на основі прямокутних n-решіток або гіпертори (булеві гіперкуби або n-куби також можуть розглядатися як найпростіші тороїдально-решітчасті ТС змінної розмірності) [1-4]. Це обумовлено наступними властивостями ТС даного класу [1,5,6]:

- конфігурація решітчастих (або стільникових) ТС відповідає специфіці науково-технічних завдань, що вимагають оброблення великих масивів різної розмірності;

- неунівалентні n-решітки легко перетворюються на унівалентні n-тори шляхом введення в їх структуру додаткових зв'язків [6];

- основні топологічні метрики тороїдально-решітчастих КМ будь-якого розміру N можуть бути точно оцінені в процесі топологічного синтезу мережі за допомогою простих аналітичних виразів;

- тороїдально-решітчасті КМ надають широкі можливості їх оптимізації (вибору співвідношення між топологічною вартістю КМ та значеннями метрик, що характеризують її надійність і максимальну затримку передачі повідомлень);

- маршрутизація повідомлень в тороїдально-решітчастих КМ здійснюється на основі простої кубічної функції, що припускає схему адресації вузлів за допомогою рефлексивного коду Грея [1]. Відповідно, алгоритм маршрутизації ґрунтується на операції порозрядного порівнянні адрес вузла-відправника та вузла-приймача за допомогою логічної операцій XOR (виключне АБО, сума за модулем 2), що легко реалізується апаратним шляхом.

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

Об'єктом дослідження є КМ тороїдально-решітчастого типу масивно-паралельних МПКС.

Предметом дослідження є топологічні властивості КМ тороїдально-решітчастого типу типу довільної розмірності, можливості автоматизації їх топологічного синтезу.

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

Відповідно, досягнення мети дослідження передбачає розв'язання декількох задач, а саме:

- аналізу топологічних властивостей різноманітних тороїдально-решітчастих ТС довільної розмірності з метою визначення можливостей формалізації та автоматизації їх топологічного синтезу;

- уточнення постановки завдання топологічного синтезу тороїдально-решітчастих КМ довільної розмірності з урахуванням специфіки мереж даного типу;

- розробку методу пошуку максимально компактної ТС тороїдально-решітчастого типу типу заданого розміру при накладених обмеженнях на порядок вузлів мережі;

- розробку, на основі вказаного методу, алгоритму (та, відповідно, програми), що реалізує вказаний метод, а також обчислює значення основних топологічних метрик знайденої структури.

Метод дослідження - аналітичний.

Основним науковим результатом дослідження є метод пошуку максимально компактної ТС тороїдально-решітчастого типу заданого розміру. Основні практичні результати - алгоритм та програма, що реалізують вказаний метод, а також обчислюють значення основних топологічних метрик знайденої структури.

Робота була апробована на сьомій міжнародної науково-технічної конференції «Сучасні напрями розвитку інформаційно-комунікаційних технологій та засобів управління».

Дипломна робота складається з двох розділів - одного теоретичного характеру та двох практичних. В додатку приводяться матеріали, що підтверджують апробацію результатів дослідження, а також код розробленої програми.



1. ОСНОВНІ ПОНЯТТЯ ПРО КОМУНІКАЦІЙНІ МЕРЕЖІ МУЛЬТИПРОЦЕСОРНИХ СИСТЕМ. ВЛАСТИВОСТІ ТА ЗАСТОСУВАННЯ ТОРОЇДАЛЬНО-РЕШІТЧАСТИХ КОМУНІКАЦІЙНИХ МЕРЕЖ

1.1 Основні визначення, класифікація та топологічні метрики комунікаційних мереж

Одна з основних характеристик МПКС - здатність до обміну даними між її компонентами. Це забезпечується КМ, що з'єднує між собою вузли КС за допомогою каналів передачі даних. Вузол в мережі може бути термінальним (передавачем або приймачем), комутатором або виконувати обидві функції. Сучасні мікропроцесори, як правило, мають не більше 4 портів вводу-виводу. У випадках коли ТС КМ передбачає порядок вузла більше чотирьох, до вузла або групи вузлів, що об'єднані в обчислювальний кластер додається маршрутизатор або комутатор (вузол реалізується як сукупність обчислювального процесора та процесора повідомлень).

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

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

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

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

Організація внутрішніх зв'язків КМ називається її топологією [1]. Топологію КМ визначає множина вузлів, які об'єднані множиною каналів. Зв'язок між вузлами зазвичай реалізується по двоточковій схемі (кожен канал з'єднує один вузол-передавач з одним вузлом-приймачем). Будь-які два вузли, що безпосередньо з'єднані каналом зв'язку, називають суміжними вузлами або сусідніми.

Канал характеризується кількістю сигнальних ліній (шириною), затримкою - часом пересилання повідомлення від одного вузла до іншого, швидкістю передачі по кожній сигнальній лінії, смугою пропускання, кількістю напрямків передачі (однонапрямлений або двонапрямлений).

КМ МПКС розрізняють за наступними ознаками:

1. За стратегією синхронізації КМ можуть бути синхронними та асинхронними. У синхронних всі дії жорстко узгоджені в часі, що забезпечується шляхом використання єдиного генератора тактових імпульсів. В асинхронних КМ функції синхронізації розподілені по КС. Синхронні КМ звичайно повільніше, але в них легше запобігати конфліктів.

2. За стратегією комутації: КМ з комутацією пакетів та з комутацією з'єднань. У КМ з комутацією з'єднань шляхом відповідного встановлення КЕ КМ формується канал від вузла-джерела до вузла-приймача, що зберігається, поки пакет не досягне пункту призначення. В мережі з комутацією пакетів повідомлення “самостійно” знаходить шлях до місця призначення, маршрут кожного разу може бути іншим. Пакет послідовно проходить через вузли мережі, черговий вузол запам'ятовує прийнятий пакет у своєму буфері та аналізує. Залежно від завантаженості КМ ухвалюється рішення про можливість негайного пересилання пакету до наступного вузла і про подальший маршрут проходження пакету. Якщо всі можливі канали передачі зайняти, в буфері вузла формується черга пакетів, яка “розсмоктується” при вивільненні каналів. КМ з комутацією пакетів більш ефективно використовують ресурси мережі, але час доставки в них сильно залежить від змінних затримок переміщення пакетів.

3. За стратегією управління КМ можуть бути централізованими та децентралізованими. У деяких КМ, особливо з комутацію з'єднань, прийняте централізоване управління, при якому процесори посилають запит на обслуговування в контролер КМ, який проводить арбітраж запитів із врахуванням заданих пріоритетів і встановлює потрібний маршрут.

4. Залежно від того, чи залишається конфігурація зв'язків КМ незмінною в процесі функціонування КС, розрізняють статичні та динамічні КМ (відповідно, КС із фіксованими зв'язками та КС з реконфігурованими зв'язками). З'єднання в статичній КМ є фіксованими, тоді як в динамічній КМ вони можуть оперативно змінюватись в процесі функціонування КС.

Статичні КМ є простішими за побудовою та вимагають найменших апаратних витрат на їх реалізацію. Але вони мають і суттєві недоліки - в першу чергу, низьку надійність та відмовостійкість. Пошкодження єдиного порту вузла може унеможливити передачу повідомлень між деякими парами вузлів навіть при наявності в КМ декількох альтернативних шляхів передачі повідомлень.

Будь-яку динамічну КМ можна представити як сукупність статичних КМ, що змінюють одна одну за визначений час. Динамічні КМ можуть бути блокуючими або неблокуючими. Також розрізняють КМ повністю неблокуючи та неблокуючи з реконфігурацією.

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

Динамічні структури КМ часто надають можливість оптимізації за критерієм ефективність/вартість, тобто вибору між величиною апаратних витрат на реалізацію мережі та її властивостями (наприклад, надійністю та відмовостійкістю).

ТС КМ прийнято класифікувати за ознакою розмірності структури. Розмірність ТС КМ R можна визначити як мінімальну абсолютну зв'язність структури, тобто кількість альтернативних шляхів, що не перетинаються, будь-якої довжини між будь-якими двома вузлами, що мають мінімальний для даної структури ступінь d_min (мінімальний порядок) [16]. Геометрично мінімальну зв'язність можна представити як ширину того розрізу КМ, який перетинає мінімальну можливу кількість зв'язків (на відміну від ширини бісекції B, що визначається як ширина того розрізу структури, що розділяє її приблизно навпіл та перетинає мінімальну кількість зв'язків). Наприклад, розрізи, що визначають мінімальну абсолютну зв'язність структури (позначений літерою А) та ширину бісекції (позначений літерою Б) для решітки розміром N=16 показані на рис. 1.1 [16]. Якщо КМ побудована «правильно» (вузли мінімального порядку розташовані тільки на периферії ТС, вона не має з'єднань мостового типу, ширина бісекції B ? d_min), то для неї не можна побудувати розріз, що має ширину меншу за d_min. Тоді R= d_min [16].

Рис. 1.1 Дворозмірна решітка N=16

Поняття розмірності ТС КМ є об'єктивним показником, значення якого не залежить від способу візуалізації структури [16]. З іншого боку, воно є ї практично значимим показником, тому що для симетричних КМ (які мають всі вузли однакового порядку) співпадає з порядком вузлів, тобто кількістю їх комунікаційних портів [16].

ТС можуть бути регулярними (інші назви - симетричними, унівалентними), якщо порядок (ступень) всіх їхніх вузлів d однаковий або нерегулярними (асиметричними, неунівалентними) у протилежному випадку [1,20]. При побудові реальних неунівалентних КМ вважається доцільним, з точки зору оптимізації серійного виробництва, виготовляти всі ПЕ МПКС з однаковою (максимальною необхідною) кількістю комунікаційних портів, при цьому частина комунікаційних портів деяких ПЕ буде залишатися незадіяною. Відповідно, виникає надлишкова вартість незадіяних вузлових засобів комутації, що, очевидно, є небажаним з економічної токи зору. Саме тому в сучасних КС застосовуються тільки унівалентні ТС КМ.

Канали зв'язку між вузлами КМ можуть бути однонапрямленими або двонапрямленими. Існують мережі з повним з'єднанням (повнозв'язні КМ) та мережі з обмеженим з'єднанням (неповнозв'язні КМ).

Процес синтезу КМ МПКС можна умовно представити у вигляді наступних основних етапів:

- топологічний синтез КМ;

- вибір схеми адресації вузлів;

- вибір функцій, правила та алгоритму маршрутизації.

Схемою адресації називають систему відповідності між адресами суміжних вузлів, функцією маршрутизації - алгоритм маніпулювання бітами адреси поточного вузла-відправника для визначення адреси чергового вузла-приймача.

Спосіб маршрутизації повідомлень (пакетів) в КМ -- це правило вибору чергового вузла, якому передається повідомлення. Виходячи з адрес вузлів (відправника та приймача), вибирається існуюче з'єднання вузлів в статичних КМ або здійснюється їх комутація в динамічних мережах [6,20].

Алгоритми маршрутизації визначають шлях передачі даних від вузла-відправника повідомлення до вузла-приймача. Серед можливих способів рішення даної задачі розрізняють [6,20]:

- оптимальні, що визначають завжди найкоротші шляхи передачі даних, і неоптимальні алгоритми маршрутизації;

- детерміновані і адаптивні методи вибору маршрутів (адаптивні алгоритми визначають шляхи передачі даних в залежності від існуючого завантаження комунікаційних каналів).

До числа найбільш поширених оптимальних алгоритмів відноситься клас методів покоординатної маршрутизації (dimension-ordered routing), в яких пошук шляхів передачі даних здійснюється по черзі для кожної розмірності топології КМ.

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

Функція маршрутизації однозначно визначає схему адресації вузлів та топологію КМ, але узагальнених методів побудови функцій маршрутизації, що гарантовано приводять до отримання ТС з найкращими значеннями основних метрик, не існує.

Базовим етапом при проектуванні МПКС є вибір топології КМ і, відповідно, оцінювання її метрик та властивостей [1,6].

Топологію взаємозв'язків КМ МПКС зручно представляти в вигляді графа (найчастіше, неорієнтованого), G = (V, E), де V -- множина вершин, що представляють обчислювальні елементи мережі і E -- множина ребер, що представляють зв'язки між обчислювальними елементами.

Використання вказаної моделі дозволяє представити топологічні метрики КМ як відповідні властивості графів [3,17]. Метрики даної групи називають статичними, тому що їх можна визначити для будь-якої ТС, знаючи лише кількість вузлів, зв'язків та відношення між ними. До статичних метрик відносяться [20]:

1. Кількість вузлів КМ (N) або розмір КМ. Також цю величину називають порядком графу:

N =| V | (1.1)

де V - кількість вузлів КМ.

2. Загальна кількість зв'язків (каналів або ребер графу) між всіма вузлами КМ (I). Дана величина іноді використовується як наближена оцінка топологічної вартості КМ. Вона визначається виразом (1.2) (a - для неунівалентних ТС, b - для унівалентних ТС).

(1.2)

3. Максимальний діаметр (D) - найкоротший шлях між двома найбільш віддаленими вузлами КМ (максимальна кількість переходів між сусідними вузлами, які має пройти повідомлення, щоб досягти місця призначення). Може використовуватися для оцінювання максимальної затримки проходження повідомлень в мережі.

4. Порядок або ступень вузла (d) - кількість його суміжних вузлів. Фактично це кількість портів комутуючого вузла (маршрутизатора). Бажано, щоб порядок всіх вузлів КМ був однаковим, що є ознакою унівалентної ТС. Максимальний порядок вузла в графі визначає порядок самого графа:

(1.3)

5. Ширина бісекції КМ (B). Якщо визначити поняття зрізу КМ С(N₁,N₂) як множини каналів, розрив яких розділяє множину вузлів мережі N на дві підмножини N₁, N₂, що не перетинаються, тоді бісекція КМ - це зріз мережі, що розділяє її приблизно навпіл, тобто

(1.4)

Ширина бісекції - це мінімальна кількість каналів КМ, що розриваються при всіх можливих бісекціях мережі:

(1.5)

6. Коефіцієнт симетрії [14] або унівалентності (K_S) -- відношення кількості задіяних портів КМ p=2I до загальної (максимально можливої) кількості портів в регулярній мережі с той самою кількістю вузлів P=Nd_max.

(1.6)

Даний показник дозволяє оцінити ступень асиметричності (неунівалентності) КМ при визначеній кількості вузлів, а також аналізувати тенденцію змінювання цього ступеню при збільшенні кількості вузлів (масштабуванні мережі). Очевидно, для всіх унівалентних КМ d=d_max (порядок всіх вузлів однаковий), тому для них Ks=1.

7. Складність -- вимірюється кількістю обладнання, необхідного для реалізації КМ.

8. Здатність до розширення (масштабування) - властивість, що характеризує можливість додавання нових вузлів до ТС.

9. Надійність - властивість, яка характеризує ймовірність збереження працездатності КМ при виході з ладу одного чи кількох вузлів або при втраті зв'язку між працездатними вузлами.

10. Зв'язність (абсолютна) КМ (Q) - мінімальна кількість паралельних (альтернативних) шляхів між будь-якою парою вузлів. Характеризує стійкість КМ до пошкоджень.

Інші метрики визначаються не тільки топологічними властивостями КМ, а також властивостями каналів зв'язку, способу передачі, протоколів обробки інформації. Ці метрики називають динамічними тому, що вони можуть бути отримані лише при проведенні статистичних досліджень певної КМ з визначеною топологією при розв'язанні задачі визначеного класу та при відомому складі устаткування. Наприклад [20]:

1. Затримка (T) - час проходження повідомлення від вузла-відправника до вузла-приймача. В КМ, де час передачі повідомлень залежить від маршруту, визначають мінімальну, середню та максимальну затримку.

2. Пропускна здатність (W) - кількість інформації, яка може бути передана через КМ за одиницю часу.

3. Середня дистанція або комунікаційна відстань (м) -- середня кількість зв'язків, які мають бути задіяні при проходженні між будь-якими двома вузлами.

(1.7)

де Pi позначає кількість шляхів найкоротшої довжини i між усіма парами різних вузлів [1].

1.2 Застосування тороїдально-решітчастих комунікаційних мереж в масивно-паралельних мультипроцесорних комп'ютерних системах

Серед паралельних обчислювальних систем (суперкомп'ютерів) найбільш масштабними та потужними є масивно-паралельні КС. В них - від «історичних» до найсучасніших - широко застосовуються КМ, топології яких утворюють клас тороїдально-решітчастих структур - n-розмірні тори на основі прямокутних n-решіток або гіпертори (булеві гіперкуби або n-куби також можуть розглядатися як найпростіші тороїдально-решітчасті ТС змінної розмірності) [1-4]. Це обумовлено наступними властивостями ТС даного класу [1,5,6]:

- конфігурація решітчастих (або стільникових) ТС відповідає специфіці науково-технічних завдань, що вимагають оброблення великих масивів різної розмірності;

- неунівалентні n-решітки легко перетворюються на унівалентні n-тори шляхом введення в їх структуру додаткових зв'язків [6];

- тороїдально-решітчасті КМ надають широкі можливості їх оптимізації (вибору співвідношення між топологічною вартістю КМ та значеннями метрик, що характеризують її надійність і максимальну затримку передачі повідомлень);

- маршрутизація повідомлень в тороїдально-решітчастих КМ здійснюється на основі простої кубічної функції, що припускає схему адресації вузлів за допомогою рефлексивного коду Грея [1]. Відповідно, алгоритм маршрутизації ґрунтується на операції порозрядного порівнянні адрес вузла-відправника та вузла-приймача за допомогою логічної операцій XOR (виключне АБО, сума за модулем 2), що легко реалізується апаратним шляхом.

Головна перевага простих решітчастих ТС - масштабованість (велика матриця може бути отримана з матриці меншого розміру простим додаванням вузлів без переустановлення існуючих зв'язків) [1, 2,4,6,8,10].

Двомірні решітчасті ТС застосовувалися в багатьох КС наприклад, Intel Paragon та Intel Touchstone Delta, Goodyear Aerospace, J-Machine Масачусетського технологічного інституту [8]. Але, прості решітки, як вже вказувалося раніше, є неунівалентними, що й обумовило поступову відмову від їх використання та перехід до тороїдально-решітчастих ТС.

ILLIAC IV - суперкомп'ютер сімейства ILLIAC (ILLInois Automated Computer) 1965 р. випуску. Був побудований університетом Іллінойсу спільно з корпорацією Burroughs за замовленням NASA. Архітектурно ILLIAC IV являв собою МПКС с деякими характерними рисами систолічних матриць та масово-паралельних систем. Топологія КМ ILLIAC (див. рис. 1.2) - двомірний тор, де операція скручування застосована тільки до рядків матриці [6,8]

Рис. 1.2 Топологія КМ ILLIAC

Двомірний тор реалізований, наприклад, в КС iWarp. КМ топології трьохмірний тор - в КС Cray T3D. КМ лінійки суперкомп'ютерів IBM Blue Gene (Blue Gene/L, Blue Gene/P) також побудовані на основі топології «тривимірний тор» [6,8]. Blue Gene/L є першим із названої лінійки. Максимальна конфігурація КМ системи, що може містити від 1024 до 65536 обчислювальних вузлів, - трьохмірний тор розміром 64х32х32.

КС SpiNNaker, розроблена в Манчестерському університеті у Великобританії, призначена для моделювання дуже великих, біологічно реалістичних нейронних мереж в режимі реального часу. КС має властивості масового паралелізму та високої відмовостійкості [18].

Система включає до свого складу 65 536 ідентичних 18-ядерних процесорів (всього 1 179 648 ядер). Кожен процесор реалізований у вигляді спеціально розробленої мікросхеми (має власний маршрутизатор та 128 Мб пам'яті для зберігання синаптичних даних), підключений до шести сусідів, утворюючи тороїдальную мережу. Принцип побудови КМ КС SpiNNaker пояснюється рис. 1.3.

Рис. 1.3 Схематичне представлення топології КМ БПКС SpinNaker [11]

Взагалі в сучасних БПКС спостерігається тенденція щодо збільшення розмірності КМ тороїдально-решітчастих топологій. Наприклад, КС Blue Gene/Q використовує вже п'ятивимірний тор.

Мікропроцесорні гіперкуби уперше почала створювати компанія IMS Associates. Спочатку розповсюдженню гіперкубічних КМ суттєво заважала їх основна негативна риса - стрімке зростання порядку вузлів зі збільшенням розміру мережі. Перші розробники гіперкубічних КМ намагалися зменшити обсяг комунікаційного обладнання, модифікуючи гіперкуб шляхом введення у нього ієрархічних структур, але ці спроби не виходили за межі університетських лабораторій з причини неготовності елементної бази і, як наслідок, занадто великого обсягу устаткування, необхідного для реалізації практично значимих КМ.

Ситуація стала мінятися на початку вісімдесятих, коли з'явилися потужні 16/32-розрядні процесори і мікросхеми пам'яті з ємністю від сотні кілобайт і вище. Тільки тоді в 1983 році в Каліфорнійському технологічному інституті вдалося створити справжній працюючий гіперкуб Cosmic Cube розміром 64 вузли.

Поява Cosmic Cube стимулювала і Intel до створення в 1985-му «персонального суперкомп'ютера» iPSC/1 (Intel Personal Supercomputer) з кількістю вузлів до 128. Подібну КС System/14 представила компанія Ametek, теж на 8086/87, але з удвічі більшою кількістю вузлів. В 1985 році з'явилося кілька КС (Caltech/JPL Mark III, Connection Machine, Intel iPSC-VX, Floating Point Systems T Series), КМ яких мала гіперкубічну топологію. Гіперкубічна КМ також була реалізована в КС Intel iPSC.

Великих успіхів в свій час досягла компанія nCube. КС nCube/ten (1985 р.) має у своєму складі десятирозмірний гіперкуб (1024 вузли). КМ nCube-2 (1989 р.) вже була побудована на основі гіперкуба розмірністю 13 та містила 8192 процесора. Розмірність гіперкуба в останній версії системи nCube -3 (1995 р.) досягла 16, кількість процесорів, відповідно - 65536.

Одним із останнім досягненням в цій сфері став збудований в кінці 2011 року японський суперкомп'ютер - K Computer компанії Fujitsu, що мав 88128 процесорів (705024 ядер). Продуктивність системи на тесті Linpack досягла 10,51 Пфлопс. Пікова швидкодія комплексу досягає 11,28 квадрильйона операцій з плаваючою комою в секунду.

На сьогоднішній день Китай став лідером у всесвітній гонці розрахункової потужності суперкомп'ютерів. Його три суперкомп'ютери Tianhe-1A, Tianhe-2 та Sunway TaihuLight стали самими потужними в своєму роді та в свій час. Tianhe-1A був запущений в кінці 2010 року, мав 7168 графічних процесорів Nvidia Tesla M2050 і 14336 серверних процесорів Intel Xeon, швидкість його розрахунків дорівнює 2,57 Пфлопс. В 2013 році був запущений Tianhe-2, в своєму складі він мав 3,12 мільйонів ядер(384 тисячі процесорів Ivy Bridge і 2736 тисячі Intel Xeon Phi), практична швидкість розрахунків - 33,86 Пфлопс, теоретична - 54,9 Пфлопс. Самим останнім та на даний час найпотужнішим суперкомп'ютером в світі став Sunway TaihuLight. Він був запущений в кінці 2016року, має 40960 процесорів SW26010 власного виробництва, тобто всього комплекс має в своєму розпорядженні 10,6496 мільйонів ядер. Його практична продуктивність становить 93 Пфлопс, за тестом LINPACK, а теоретична пікова швидкість - 125,43 Пфлопс.

1.3 Основні властивості тороїдально-решітчастих комунікаційних мереж

Тороїдально-решітчасті ТС(k, m, l) отримуються замиканням у кільця ребер решіток додатковими зв'язками за умови не дублювання тороїдальними зв'язками ребер одиничної довжини. Операції утворення тороїдальних зв'язків в будь-якому випадку не вимагають введення додаткових вузлів [15, 20]. Введення тороїдальних зв'язків в решітчасті ТС суттєво покращує їх властивості: порядок всіх вузлів збільшується до максимального та стає однаковим (неунівалентні ТС перетворюються на унівалентні); максимальний діаметр зменшується майже удвічі; ширина бісекції збільшується також удвічі.

Таким чином, введення в неунівалентні ТС КМ тороїдальних зв'язків є універсальним методом, що дозволяє перетворювати їх на унівалентні з одночасним зменшенням максимального діаметру та збільшенням ширини бісекції [15, 20].

Як приклад, в таблиці 1.1. показані декілька нескладних тороїдально-решітчастих ТС та приведені вирази для визначення деяких їх метрик.



Таблиця 1.1 Приклади простих тороїдально-решітчастих ТС

Загальний вигляд	Основні метрики
Тороїдально-решітчаста топологія ТС(k>2, 2, 2)	I=8k=2N; B=4, d=4.
Тороїдально-решітчаста топологія ТС(k>2, m>2, 2)	I=5km=2,5N; B=min[4k,4m,km], d=5.
Тороїдально-решітчаста топологія ТC(k>2, m>2, l>2)	I=3kml=3N; B=2min[km,kl,lm], d=6.

Булевий гіперкуб [1,6,8,10,20] є окремим (найпростішім) випадком багаторозмірної тороїдально-решітчастої структури коли в кожному її ребрі є тільки два вузли. «Відрізок» (канал, що з'єднує два вузли) може розглядатися як найпростіший однорозмірний гіперкуб. «Квадрат», утворений чотирма вузлами - дворозмірниим гіперкубом, а куб з восьми вузлів - трирозмірним гіперкубом і т.д.

Завдяки рекурсивній природі гіперкубів, n-розмірний гіперкуб можна отримати копіюванням (n-1) - розмірного гіперкуба з наступним з'єднанням відповідних вузлів, як показано на рис. 1.4.

Рис. 1.4 Принцип побудови n-розмірного гіперкуба

Гіперкуб розмірності n = log2N має такі метрики: D = d = n; I = nN/2; B = N/2. Збільшення розмірності гіперкуба на одиницю веде до подвоєння кількості його вузлів, збільшення порядку вузлів і діаметра мережі на одиницю.

На основі простого гіперкуба можуть утворюватися більш складні гіперкубічні структури [20], але всі бінарні гіперкуби складаються з N=2ⁿ вузлів. мають регулярний ступінь n, що визначає загальну кількість з'єднань, тому порядок вузлів дуже швидко збільшується зі збільшенням розміру структури. Саме стрімке збільшення порядку вузлів при масштабуванні гіперкубічної КМ вважаться основним недоліком даної ТС.

1.4 Задача синтезу тороїдально-решітчастої комунікаційної мережі

Традиційно завдання топологічного синтезу узагальненої КМ розглядається як розподіл визначеної кількості зв'язків I ? N-1 між заданою кількістю вузлів N таким чином, щоб мінімізувати або максимізувати значення деяких топологічних метрик отриманої ТС (найчастіше, мінімізувати максимальний діаметр КМ D). Але така узагальнена постановка завдання не враховує деякі особливості побудови реальних КМ МПКС, а саме:

- необхідність забезпечення унівалентності ТС з метою забезпечення відсутності надлишкової топологічної вартості вузлових комунікаційних засобів (незадіяних комунікаційних портів);

- обмеження зверху на значення порядку вузлів (кількість вузлових комунікаційних портів);

- можливість реалізації простої та зручної функції маршрутизації.

Також слід зазначити, що розмір реальних КМ МПКС практично завжди вибирається рівним 2ⁿ, що забезпечує використання повного набору двійкових n-розрядних вузлових адрес (повну відповідність кількості можливих комбінацій адресного коду реальній кількості вузлів та відсутність заборонених адрес, що не асоційовані із жодним вузлом).

Таким чином, уточнене завдання синтезу тороїдально-решітчастої КМ можна сформулювати як пошук оптимального варіанту розподілу кількості зв'язків I=Nd/2=d2^n-1 між N=2ⁿ вузлами при обмеженому значенні порядку вузлів d за умови збереження кубічної функції маршрутизації таким чином, щоб мінімізувати максимальний діаметр D та максимізувати ширину бісекції (В).



Висновки до розділу 1

1. На протязі всієї еволюції масивно-паралельних КС в них широко застосовуються КМ, топології яких утворюють клас тороїдально-решітчастих структур - n-розмірні тори на основі прямокутних n-решіток та гіперкуби, що можуть розглядатися як найпростіші тороїдально-решітчасті ТС змінної розмірності, що обумовлено багатьма їх привабливими властивостями, а саме:

- їх конфігурація відповідає специфіці науково-технічних завдань, що вимагають оброблення великих масивів різної розмірності;

- неунівалентні n-решітки легко перетворюються на унівалентні n-тори шляхом введення в їх структуру додаткових зв'язків;

- тороїдально-решітчасті КМ надають широкі можливості їх оптимізації (вибору співвідношення між топологічною вартістю КМ та значеннями метрик, що характеризують її надійність і максимальну затримку передачі повідомлень);

- маршрутизація повідомлень в тороїдально-решітчастих КМ здійснюється на основі простої кубічної функції.

2. В сучасних МПКС спостерігається тенденція щодо збільшення розмірності та ускладнення структури КМ тороїдально-решітчастих топологій, тому актуальним є пошук формалізованих та узагальнених методів опису, а також дослідження можливостей автоматизації топологічного синтезу різноманітних ТС вказаного типу.

3. Проведене уточнення завдання синтезу тороїдально-решітчастої КМ як пошуку оптимального варіанту розподілу кількості зв'язків I=Nd/2=d2^n-1 між N=2ⁿ вузлами при обмеженому значенні порядку вузлів d за умови збереження кубічної функції маршрутизації таким чином, щоб мінімізувати максимальний діаметр D та максимізувати ширину бісекції (В).

4. На основі проведеного аналізу властивостей тороїдально-решітчастих ТС КМ можна сформулювати наступні задачі дослідження:

- пошук методу вибору оптимальної, за критерієм мінімального значення D та максимального значення В, тороїдально-решітчастої ТС для заданих значень розміру КМ N=2ⁿ та обмеженому зверху значенні порядку вузлів d;

- реалізацію метода у вигляді алгоритму та відповідної програми.



2. МОЖЛИВОСТІ АВТОМАТИЗАЦІЇ ТОПОЛОГІЧНОГО СИНТЕЗУ ТОРОЇДАЛЬНО-РЕШІТЧАСТИХ КОМУНІКАЦІЙНИХ МЕРЕЖ

2.1 Основні топологічні метрики тороїдально-решітчастих комунікаційних мереж

Узагальнені вирази для метрик гіперрешіток та гіперторів на їх основі отримані методом математичної індукції на основі відомих виразів для вказаних структур невеликої (1-6) розмірності.

Вирази для метрик n- розмірної кубічної решітки ():

,

,

, (2.1)

,

.

Вирази для метрик 2n- розмірних торів на основі n- розмірних кубічних решіток:

,

,

, (2.2)

,

.

Прямокутні («не кубічні») гіперрешітки та тори на їх основі, на відміну від гіперкубів, надають можливість масштабування ТС КМ без збільшення порядку її вузлів, але значення основних метрик таких структур будуть завжди гіршими, ніж у гіперкубів відповідного розміру. Взагалі, булеві гіперкуби можна розглядати як «елементарні комірки» гіперторів на основі решіток відповідної розмірності.

Очевидно, розмір багаторозмірних прямокутних (не «кубічних» решіток) можна визначити як:

.

Відповідно, вирази для метрик n- розмірної прямокутної гіперрешітки:

,

,

, (2.3)

,

,

Вирази для метрик узагальненого 2n- розмірного гіпертора на основі n- мірної прямокутної решітки:



,

,

, (2.4)

,

,

З виразів (2.3), (2.4) неважко отримати вирази (2.1), (2.2), що підтверджує правильність отриманих результатів.

Із аналізу виразів (2.1 - 2.4) можна зробити наступні висновки:

a. Основні топологічні метрики тороїдально-решітчастих КМ будь-якого розміру N можуть бути точно оцінені в процесі топологічного синтезу мережі за допомогою простих аналітичних виразів;

b. При фіксованому розмірі ТС її максимальний діаметр зменшується, а ширина бісекції збільшується зі збільшенням розмірності (та, відповідно, зі збільшенням порядку її вузлів);

c. Будь-які гіперрешітки та тори на їх основі мають мінімальний діаметр за умови, що кількість вузлів однакова у всіх вимірах структури (ТС є «кубічною»).

d. Прямокутні («не кубічні») гіперрешітки та тори на їх основі, на відміну від гіперкубів та «кубічних» структур вказаного типу, надають можливість масштабування ТС КМ без збільшення порядку її вузлів, але значення основних метрик таких структур будуть завжди гіршими, ніж у гіперкубів відповідного розміру.



2.2 Задача і метод пошуку максимально компактної тороїдально-решітчастої структури

Як вже вказувалося раніше, будь-які гіперрешітки та тори на їх основі мають мінімальний діаметр за умови, що кількість вузлів однакова у всіх вимірах структури (ТС є «n-кубічною», тобто ).

З урахуванням того, що звичайно N=2ⁿ, кількість вузлів в одному ребрі ТС також має бути рівною цілому ступеню 2: m=2^l. Відповідно,

Таким чином, умову «n-кубічного» розташування заданої кількості вузлів можна визначити як:

(3.1)

Якщо на значення порядку вузлів тороїдально-решітчастої ТС накладено обмеження d<d_ncube, її подання в «n-кубічному» вигляді неможливе. Відсіля витікає завдання пошуку максимально компактної ТС розміру N=2ⁿ при заданому значенні d<d_ncube.

Для її розв'язання запропонований наступний метод.

i. Для заданих розміру N та ступеня вузлів d=2n знаходимо значення Якщо воно є цілим, шукана максимально компактна ТС є «n-кубічною» з кількістю вузлів у ребрі m. На рис 3.1, де зображений загальний алгоритм, що реалізує запропонований метод, даній ситуації відповідає ліва гілка розгалуження.



Рис. 2.1. Загальний алгоритм

ii. Якщо значення не є цілим числом, це свідчить про неможливість подання шуканої максимально компактної ТС в «n-кубічному» вигляді. Даній ситуації відповідає права гілка алгоритму (позначена як процедура «Цикл № 1». Процедура пошуку максимально компактної ТС не «n-кубічного» типу ґрунтується на припущенні, що в разі неможливості отримання «n-кубічної» ТС максимально компактною буде структура, у який кількість вузлів у d/2-1 вимірах однакова, і тільки в одному вимірі є більшою або меншою у два рази. Це припущення може бути реалізовано нескладною рекурентною процедурою:

- отримане значення m округлюється до найближчого цілого значення m_n=2^l (в результаті маємо кількість вузлів у першому вимірі ТС);

- ділимо N на m_n, тобто знаходимо кількість вузлів структури меншої (на 2) розмірності, копіювання якої m_n разів (зі з'єднанням відповідних вузлів) приводить до вихідної ТС.

- знаходимо , тобто приблизну кількість вузлів у другому вимірі шуканої ТС.

- всього процедура повторюється d/2 разів.

Алгоритм, що реалізує дану процедуру, зображений на рис. 3.2.

Висновки до розділу 2

В даному розділі:

1. На основі проведеного аналізу виразів для основних топологічних метрик тороїдально-решітчастих структур (2.1 - 2.4) зроблені наступні висновки:

- основні топологічні метрики тороїдально-решітчастих КМ будь-якого розміру N можуть бути точно оцінені в процесі топологічного синтезу мережі за допомогою простих аналітичних виразів;

- при фіксованому розмірі ТС її максимальний діаметр зменшується, а ширина бісекції збільшується зі збільшенням розмірності (та, відповідно, зі збільшенням порядку її вузлів);

- будь-які гіперрешітки та тори на їх основі мають мінімальний діаметр за умови, що кількість вузлів однакова у всіх вимірах структури (ТС є «кубічною»).

- прямокутні («не кубічні») гіперрешітки та тори на їх основі, на відміну від гіперкубів та «кубічних» структур вказаного типу, надають можливість масштабування ТС КМ без збільшення порядку її вузлів, але значення основних метрик таких структур будуть завжди гіршими, ніж у гіперкубів відповідного розміру.



Рис. 2.2. Алгоритм циклу №1 (пошуку максимально компактної «некубічної» ТС

2. Запропонований метод пошуку максимально компактної ТС розміру N=2ⁿ при заданому значенні d<d_ncube, що може бути реалізований у вигляді нескладної рекурентної процедури. Процедура пошуку максимально компактної ТС не «n-кубічного» типу ґрунтується на припущенні, що в разі неможливості отримання «n-кубічної» ТС максимально компактною буде структура, у який кількість вузлів у d/2-1 вимірах однакова, і тільки в одному вимірі є більшою або меншою у два рази. Метод формалізований у вигляді алгоритму, що надає можливість створення відповідної програми.



3. ОПИС ПРОГРАМИ АВТОМАТИЗОВАНОГО ТОПОЛОГІЧНОГО СИНТЕЗУ ТОРОЇДАЛЬНО-РЕШІТЧАСТИХ КОМУНІКАЦІЙНИХ МЕРЕЖ ТА РЕЗУЛЬТАТИ ЇЇ ТЕСТУВАННЯ

3.1 Інтерфейс та функції програми

Програма була написана мовою C++, за допомогою оболонки С/С++ Builder 6 Borland. Сама програма по структурі являється віконним додатком. Виконує на даний момент єдину функції - аналітично розрахувати КМ за вхідними даними та вивести її на екран.

Інтерфейс програми Max_Com простий та дружній для користувача. При запуску програми відкривається вікно «привітання» (див. рис. 3.1), на ньому розташовані 3 кнопки: «Про програму» - при натисненні на неї з'являється нове вікно на якому відображується інформація про програму, її розробника та контактами розробника, «Вихід» - при натисненні на неї програма закривається та завершується процес в системі (ці два вікна також супроводжуються і на інших вікнах), «Старт» - при натисненні відкривається вікно для роботи та виконання запрограмованого завдання (див. рис.3.2).

Рис. 3.1. Стартове вікно програми

У вікні для роботи міститься два поля для вводу вхідних даних (кількості процесорів та їх порядку), поле для виводу розрахунків на екран, дві кнопки для початку розрахунків та для розрахунків метрик (вона не активна доки не буде розрахована система) також вікно має чотири приховані об'єкти для коректування вхідних даних - два для кількості вузлів і два для їх порядку (див. рис. 3.3).

Рис. 3.2. Інтерфейс програми

Рис. 3.3. Функції програми

Для початку роботи потрібно у відповідних полях ввести кількість вузлів N майбутній системі та їх порядок d. Якщо вхідні дані були введені не коректно або ж не відповідають умові N=2ⁿ, програма допоможе вибрати найближчий коректний варіант див. рис. 3.4).

Рис. 3.4. Корекція розміру N

Розмір N обмежений максимальним значенням - , чого достатньо для будь-яких практичних застосувань. Уведений порядок вузла d перевіряється на парність та належність діапазону

Якщо уведені коректні вихідні дані, програма пропонує для них максимально компактний варіант ТС (у вигляді розкладання N на співмножники, що є значеннями кількості вузлів у всіх вимірах структури) та обчислює значення її основних топологічних метрик за виразами (2.2, 2.4). Приклад результату розрахунків показаний на рис 3.5.



Рис. 3.5. Вивід результатів розрахунків параметрів та метрик ТС

Результати тестування програми представлені таблицею 3.1.

Таблиця 3.1. Результати тестування програми

№ з/п	Кількість вузлів	Порядок вузлів	Варіанти побудови ТС	Розміри максимально компактної ТС	Метрики знайденої ТС
1.	32	4	2*16 4*8	4*8	I = 64, D = 12, B = 8
2.	512	6	2*2*128 2*4*64 2*8*32 2*16*16 4*4*32 4*8*16 8*8*8	8*8*8	I = 64, D = 12, B = 8
3.	2048	4	2*1024 4*512 8*256 16*128 32*64	32*64	I = 4096, D = 96, B = 64
4.	32768	8	2*2*2*4096 2*2*4*2048 2*2*8*1024 2*2*16*512 2*2*32*256 2*2*64*128 2*4*4*1024 2*4*8*512 …	16*16*8*16	I = 131072, D = 112, B = 4096

Видно, що програма правильно вибирає, серед всіх можливих варіантів, максимально компактну структуру та обчислює її основні метрики.

Висновки до розділу 3

В даному розділі описана програма, що реалізує запропонований в другому розділі метод пошуку максимально компактної ТС розміру N=2ⁿ при заданому значенні d та обчислює значення її основних топологічних метрик за виразами (2.2, 2.4). Представлені результати тестування програми, що підтверджують правильність її функціонування.



ВИСНОВКИ

В першому розділі дипломної роботи, на основі аналізу основних властивостей тороїдально-решітчастих КМ та особливостей їх застосування в масивно-паралельних МПКС:

1. Обґрунтований висновок про те, в сучасних МПКС спостерігається тенденція щодо збільшення розмірності та ускладнення структури КМ тороїдально-решітчастих топологій, тому пошук формалізованих та узагальнених методів опису, а також дослідження можливостей автоматизації топологічного синтезу різноманітних ТС вказаного типу є актуальними.

2. Проведене уточнення завдання синтезу тороїдально-решітчастої КМ як пошуку оптимального варіанту розподілу кількості зв'язків I=Nd/2=d2^n-1 між N=2ⁿ вузлами при обмеженому значенні порядку вузлів d за умови збереження кубічної функції маршрутизації таким чином, щоб мінімізувати максимальний діаметр D та максимізувати ширину бісекції (В).

3. Сформулювані наступні задачі дослідження:

- пошук методу вибору оптимальної, за критерієм мінімального значення D та максимального значення В, тороїдально-решітчастої ТС для заданих значень розміру КМ N=2ⁿ та обмеженому зверху значенні порядку вузлів d;

- реалізацію метода у вигляді алгоритму та відповідної програми.

В другому розділі обґрунтовані наступні висновки:

1. Основні топологічні метрики тороїдально-решітчастих КМ будь-якого розміру N можуть бути точно оцінені в процесі топологічного синтезу мережі за допомогою простих аналітичних виразів.

2. При фіксованому розмірі ТС її максимальний діаметр зменшується, а ширина бісекції збільшується зі збільшенням розмірності (та, відповідно, зі збільшенням порядку її вузлів).

4. Будь-які гіперрешітки та тори на їх основі мають мінімальний діаметр за умови, що кількість вузлів однакова у всіх вимірах структури (ТС є «кубічною»).

4. Прямокутні («не кубічні») гіперрешітки та тори на їх основі, на відміну від гіперкубів та «кубічних» структур вказаного типу, надають можливість масштабування ТС КМ без збільшення порядку її вузлів, але значення основних метрик таких структур будуть завжди гіршими, ніж у гіперкубів відповідного розміру.

Також у другому розділі запропонований метод пошуку максимально компактної ТС розміру N=2ⁿ при заданому значенні d<d_ncube, що може бути реалізований у вигляді нескладної рекурентної процедури. Метод формалізований у вигляді алгоритму.

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