Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів

Розглянуто мережеву топологію Flat Neighborhood Network (FNN), орієнтовану на створення вартісно-ефективних кластерних суперкомп’ютерів. Представлено метод побудови FNN-конструкцій та запропоновано критерії їх оцінювання....

Full description

Saved in:

Bibliographic Details
Date:	2004
Main Authors:	Мар’янович, Т.П., Кошулько, О.А.
Format:	Article
Language:	Ukrainian
Published:	Інститут проблем математичних машин і систем НАН України 2004
Series:	Математичні машини і системи
Subjects:	Обчислювальні системи
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/83927
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів / Т.П. Мар’янович, О.А. Кошулько // Мат. машини і системи. — 2004. — № 4. — С. 3-12. — Бібліогр.: 3 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-83927
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-839272025-02-09T12:58:11Z Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів Применение сетевой топологии Flat Neighborhood Network для построения кластерных суперкомпьютеров Application of The Flat Neighborhood Network topology for cluster supercomputer designing Мар’янович, Т.П. Кошулько, О.А. Обчислювальні системи Розглянуто мережеву топологію Flat Neighborhood Network (FNN), орієнтовану на створення вартісно-ефективних кластерних суперкомп’ютерів. Представлено метод побудови FNN-конструкцій та запропоновано критерії їх оцінювання. Рассмотрена сетевая топология Flat Neighborhood Network (FNN), ориентированная на создание эффективных в ценовом отношении суперкомпьютеров. Представлен метод построения FNN-конструкций и предложены критерии их оценки. The Flat Neighborhood Network (FNN) topology for the cost-effective cluster supercomputer designing is considered. The method of building the FNN designs and criteria of quality of the FNN designs are presented. 2004 Article Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів / Т.П. Мар’янович, О.А. Кошулько // Мат. машини і системи. — 2004. — № 4. — С. 3-12. — Бібліогр.: 3 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83927 004.27 uk Математичні машини і системи application/pdf Інститут проблем математичних машин і систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Обчислювальні системи Обчислювальні системи
spellingShingle	Обчислювальні системи Обчислювальні системи Мар’янович, Т.П. Кошулько, О.А. Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів Математичні машини і системи
description	Розглянуто мережеву топологію Flat Neighborhood Network (FNN), орієнтовану на створення вартісно-ефективних кластерних суперкомп’ютерів. Представлено метод побудови FNN-конструкцій та запропоновано критерії їх оцінювання.
format	Article
author	Мар’янович, Т.П. Кошулько, О.А.
author_facet	Мар’янович, Т.П. Кошулько, О.А.
author_sort	Мар’янович, Т.П.
title	Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів
title_short	Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів
title_full	Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів
title_fullStr	Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів
title_full_unstemmed	Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів
title_sort	застосування мережевої топології flat neighborhood network для побудови кластерних суперкомп’ютерів
publisher	Інститут проблем математичних машин і систем НАН України
publishDate	2004
topic_facet	Обчислювальні системи
url	https://nasplib.isofts.kiev.ua/handle/123456789/83927
citation_txt	Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів / Т.П. Мар’янович, О.А. Кошулько // Мат. машини і системи. — 2004. — № 4. — С. 3-12. — Бібліогр.: 3 назв. — укр.
series	Математичні машини і системи
work_keys_str_mv	AT marânovičtp zastosuvannâmereževoítopologííflatneighborhoodnetworkdlâpobudoviklasternihsuperkompûterív AT košulʹkooa zastosuvannâmereževoítopologííflatneighborhoodnetworkdlâpobudoviklasternihsuperkompûterív AT marânovičtp primeneniesetevojtopologiiflatneighborhoodnetworkdlâpostroeniâklasternyhsuperkompʹûterov AT košulʹkooa primeneniesetevojtopologiiflatneighborhoodnetworkdlâpostroeniâklasternyhsuperkompʹûterov AT marânovičtp applicationoftheflatneighborhoodnetworktopologyforclustersupercomputerdesigning AT košulʹkooa applicationoftheflatneighborhoodnetworktopologyforclustersupercomputerdesigning
first_indexed	2025-11-26T01:29:24Z
last_indexed	2025-11-26T01:29:24Z
_version_	1849814492431515648
fulltext	ISSN 1028-9763. Математичні машини і системи, 2004, № 4 3 УДК 004.27 Т.П. МАР’ЯНОВИЧ, О.А. КОШУЛЬКО ЗАСТОСУВАННЯ МЕРЕЖЕВОЇ ТОПОЛОГІЇ FLAT NEIGHBORHOOD NETWORK ДЛЯ ПОБУДОВИ КЛАСТЕРНИХ СУПЕРКОМП’ЮТЕРІВ Abstract: The Flat Neighborhood Network (FNN) topology for the cost-effective cluster supercomputer designing is considered. The method of building the FNN designs and criteria of quality of the FNN designs are presented. Key words: cost-effective supercomputer, network topology, cyclic shift method. Анотація: Розглянуто мережеву топологію Flat Neighborhood Network (FNN), орієнтовану на створення вартісно-ефективних кластерних суперкомп’ютерів. Представлено метод побудови FNN-конструкцій та запропоновано критерії їх оцінювання. Ключові слова: вартісно-ефективний суперкомп’ютер, мережева топологія, метод циклічного зсуву. Аннотация: Рассмотрена сетевая топология Flat Neighborhood Network (FNN), ориентированная на создание эффективных в ценовом отношении суперкомпьютеров. Представлен метод построения FNN- конструкций и предложены критерии их оценки. Ключевые слова: стоимостно-эффективный суперкомпьютер, сетевая топология, метод циклического сдвига. 1. Вступ При побудові кластерних суперкомп’ютерів виникає проблема створення швидких каналів зв’язку для обчислювальних вузлів кластера. Відомо, що серед найбільших у світі обчислювальних кластерів є такі, що забезпечують лише 20% від пікової швидкодії на тестових задачах через низьку швидкість передачі даних між вузлами системи [1]. Добре відомі мережеві технології, такі як Myrinet, cLAN, SCI, InfiniBand, що застосовуються для зв’язування вузлів кластерних суперкомп’ютерів. Головним чином вони покладаються на швидкість передаючих та комутуючих пристроїв, які повинні впоратись з потоком обміну даними за рахунок своєї високої пропускної спроможності. Використання надшвидких пристроїв має ряд переваг та один суттєвий недолік – високу вартість. Забезпечення вузла кластера таким мережевим пристроєм іноді коштує в 2 рази дорожче, ніж коштує сам обчислювальний вузол. Для порівняння: на оснащення обчислювального вузла розповсюдженим мережевим інтерфейсом, таким як Fast Ethernet або Gigabit Ethernet, необхідно витратити від 1% до 10% вартості вузла. Досить часто економічний чинник у питаннях розробки суперкомп’ютерів залишається поза увагою, але не можна не враховувати те, що швидкий розвиток у цій галузі відбувається разом і завдяки такому ж швидкому здешевленню 1 GFLOPS обчислювальної потужності. В свою чергу, це досягається завдяки впровадженню нових вартісно-ефективних технологій замість надто коштовних або надто складних технічно. 2. Сутність та переваги Flat Neighborhood Network Альтернативний шлях подолання проблеми створення каналів зв’язку полягає у встановленні в кожен обчислювальний вузол декількох відносно недорогих мережевих адаптерів з метою розпаралелювання процесу комутації. Прикладом такого підходу є технологія Channel bonding (об’єднання каналів), що достатньо ефективна, поки всі вузли кластера можна підключити до одного комутатора, і поки час зв’язування будь-якої пари вузлів залежить від затримки лише одного ISSN 1028-9763. Математичні машини і системи, 2004, № 4 4 комутатора. Одна з простих топологічних схем такого з’єднання зображена на рис. 1. Для пояснення цього та інших рисунків перелічимо позначення: Рис. 1. Мережева топологія Channel bonding Написами №1, №2, №3 і т.д. позначені комп’ютери (вузли), що входять до обчислювального кластера. В усіх прикладах вони мають по два мережевих адаптера (приєднуються до двох комутаторів). Комутатори позначені Switch 1, Switch 2 і т.д., а кольором позначається їх належність до окремої мережі. Всі комутатори мають по чотири порти (можуть об’єднувати до чотирьох вузлів або інших комутаторів). Отже, кожен з обчислювальних вузлів кластера на рис. 1 приєднується до двох незалежних мереж. Обидві мережі (або канали) можуть використовуватись одночасно (паралельно), внаслідок чого при рівномірному розподілі навантаження пропускна спроможність мережевої конструкції дорівнює сумі пропускних спроможностей окремих мереж. Кількість вузлів при такому підключенні не перевищує кількості портів одного комутатора. Швидкість передачі пакета даних від вузла до вузла залежить від часу проходження пакетом одного комутатора. Якщо ж вузлів більше, ніж місць в одному комутаторі, для організації Channel bonding прийдеться об’єднувати комутатори кожного каналу в ієрархії (рис. 2). Тоді не уникнути появи маршрутів, швидкість проходження яких складатиме три (можливо більше) затримки комутатора, внаслідок чого швидкість передачі даних в такій мережі значно знизиться і ефективність підходу стає сумнівною. У 2000 році університетом штату Кентуккі (США) було представлено мережеву технологію Flat Neighborhood Network (FNN) [2], назву якої можна перекласти як “Однорівневе мережеве оточення”. Ця технологія дає можливість зв’язати більше вузлів на схожих з Channel bonding принципах, ніж здатен об’єднати один комутатор, і зберегти унарну затримку на всіх маршрутах передачі даних (рис. 3), втративши лише дублювання частини маршрутів. Крім того, якщо для більшості технологій, орієнтованих на побудову кластерів, збільшення конструкції кластера означає зменшення питомої пропускної спроможності мережі (із розрахунку на один вузол системи), то у випадку FNN збільшення розмірів конструкції призведе лише до поглиблення розпаралелювання комутації, внаслідок чого для будь-якого вузла питома пропускна спроможність мережі не зменшується. ISSN 1028-9763. Математичні машини і системи, 2004, № 4 5 З моменту представлення у 2000 році технології FNN на її основі було створено три суперкомп’ютери (два в Університеті Кентуккі (США) та один в Австралійському національному університеті, м. Канберра), а НДОЦ МДУ (www.parallel.ru/computers/interconnects.html) зарахував технологію FNN до провідних кластерних комунікаційних розробок. Зауважимо, що під мережевою технологією слід розуміти топологічну схему мережі, програмне налаштування маршрутизації і ряд заходів, спрямованих на досягнення сумісності між апаратною архітектурою та системним програмним забезпеченням для кластерів. Рис. 2. Мережева топологія Channel bonding з утворенням ієрархій комутаторів Рис. 3. Мережева топологія FNN Порівняємо рисунки 2 та 3: Комп’ютери в кількості 6=N об’єднуються двома мережами у випадку Channel bonding та трьома – у випадку FNN, але кожен з комп’ютерів приєднано лише до двох мереж. Щоб об’єднати 6 комп’ютерів попарно, знадобиться щонайменше 15=L маршрутів: 2 )1( −⋅= NN L . (1) ISSN 1028-9763. Математичні машини і системи, 2004, № 4 6 Для паралельної передачі даних Channel bonding утворює 30 маршрутів (по 2 на кожну пару комп’ютерів), а FNN – 18 (лише деякі пари мають два маршрути). Однак на практиці системне програмне забезпечення часто не дозволяє одночасно передавати дані по всіх маршрутах. Тому кількість маршрутів стає менш важливою, ніж швидкість їх проходження. Отже, будь-які два комп’ютери на рис. 3 з’єднуються за допомогою одного із комутаторів (унарна затримка маршрутизації). Натомість, на рис. 2 лише дванадцять із тридцяти можливих маршрутів мають унарну затримку – решта проходять через три комутатори (потрійна затримка). Кількість комутаторів, що знадобились для побудови FNN-конструкції, 3, Channel bonding – 6. Звичайно, використовуючи FNN, можна будувати і значно більші мережеві конструкції, ніж на рис. 3. Наприклад, при використанні тринадцяти 48-портових комутаторів та вузлів з чотирма мережевими адаптерами максимальна кількість вузлів в FNN-конструкції становитиме 156 (із збереженням унарної затримки). Крім того, спеціальне розширення технології FNN дозволяє збільшити максимальну кількість вузлів до 500 і більше. На жаль, лише у випадку малої кількості вузлів та комутаторів структуру FNN-конструкції можна легко підібрати. Для більшості випадків пошук FNN-конструкцій є серйозною, хоча і добре відомою математичною задачею покриття графів, що формулюється через більш загальну задачу покриття множин (множина ребер покриває множину вершин). Як правило, розв’язок цієї задачі не єдиний, і застосування різних методів побудови конструкцій може давати неоднакові результати. Тому існують критерії оптимальності розв’язків. 3. Математична постановка задачі пошуку FNN-конструкцій Наведемо ряд визначень з теорії множин: ( )tkvA ,, покриття – це сімейство k -елементних підмножин, що називають блоками, взятих із v -елементної вибірки таким чином, що кожна t -елементна підвибірка міститься хоча б в одному блоці. Кількість блоків у покритті називають розміром і позначають ( )tkvC ,, . Кількість елементів v називають потужністю покриття. Крім того, позначимо найбільшу кількість однакових елементів у покритті як n . Зауважимо, що тут і надалі термін елемент вживається як елемент множини, і під елементами покриття будемо розуміти елементи тієї первинної множини, з якої складаються блоки покриття. Актуальною проблемою є мінімізація або максимізація певного функціоналу, що містить параметри v , k , t . Типовою є задача знаходження покриття найменшого розміру, що називають оптимальним. Приклад 1. Покриття A(7,3,2) розміру С(7,3,2)=7, побудоване методом циклічного зсуву (МЦЗ) [3], є оптимальним і у вигляді матриці записується таким чином: ISSN 1028-9763. Математичні машини і системи, 2004, № 4 7                       327 216 175 764 653 542 431 . Рядки матриці є блоками. Будь-яка двохелементна підмножина первинної семиелементної множини {1, 2, 3, 4, 5, 6, 7} міститься в одному з блоків. Елементи первинної множини повторюються не більше, ніж 3=n рази. Побудова FNN-конструкцій є проблемою пошуку покриття ( )2,,kvA , де 6≤n із міркувань доцільності. Як правило, цільовою функцією стає досягнення найменшого розміру покриття при заданій потужності. Стосовно FNN, блоки покриття будуть комутаторами в кількості ( )2,,kvC , елементи блоків – номерами підключених вузлів (загальною кількістю v ), кожен з яких має n або менше мережевих адаптерів. Також визначимо зв’язність вузла як кількість маршрутів з унарною затримкою, в яких даний вузол бере участь. На практиці важливу роль відіграє максимальна довжина блоку – кількість портів комутатора, що досить обмежена. Крім того, дещо складним є втілення конструкцій з 4>n . Тому цільовою функцією також може бути максимізація потужності покриття при заданій максимальній довжині блока та обмеженому згори n . В [3] зібрано 9 методів побудови ( )tkvA ,, покриттів, але жоден з методів не дає оптимальних конструкцій для всіх наборів параметрів. Тому існує депозитарій найменших за розміром ( )tkvA ,, покриттів (www.ccrwest.org), що отримані різними методами. В тому числі, депозитарій містить деякі FNN-конструкції (розв’язки ( )2,,kvA задач), у яких кількість елементів (що тотожна кількості обчислювальних вузлів) менша 32. Для пошуку більших конструкцій необхідно застосовувати той із відомих методів, що дає кращий розв’язок (фактично прийдеться порівняти всі методи при заданому наборі параметрів), або винайти універсальний метод, що комбінує чи модифікує існуючі методи (або є новим), який знаходитиме близькі до оптимального розв’язки при будь-якому вхідному наборі параметрів. Так, автори технології FNN для пошуку FNN-конструкцій розробили спеціальний Генетичний алгоритм (принцип дії якого не розголошується), що містить елементи неповного комбінаторного перебору. Через комбінаторну природу його вихід має тим вищу якість, чим довше продовжується пошук. Як повідомляється в [2], великі конструкції (128 вузлів і більше), що мають прийнятну якість, відшукуються за його допомогою на протязі декількох діб, при роботі на потужному суперкомп’ютері, що є значним недоліком алгоритму. Переваги Генетичного алгоритму полягають у тому, що він дозволяє планувати та формувати групи вузлів з підвищеною зв’язністю, а також дозволяє ISSN 1028-9763. Математичні машини і системи, 2004, № 4 8 формувати мережеву конструкцію з урахуванням територіального розміщення вузлів у шафах і мінімізувати кількість кабелів, що перетинають шафи (тобто реалізовано практичний підхід). Однак, як показали дослідження, приведені нижче, на базі модифікованого методу циклічного зсуву (ММЦЗ) можна побудувати детермінований алгоритм, що даватиме достатньо якісні покриття, витрачаючи незначний обчислювальний ресурс та час. 4. Модифікований метод циклічного зсуву Спочатку розглянемо звичайний метод циклічного зсуву. Для побудови покриття потужності v беруть деяку k -елементну підвибірку як 1-ий блок та 1−v її циклічних зсувів як наступні блоки. Спробувати це для усіх можливих k -елементних підвибірок практично просто і часто це дає покриття. Для отримання покриття потужності vs ⋅ потрібно спочатку побудувати покриття потужності v , а потім підмінити кожен елемент готового покриття групами із s різних елементів. При цьому довжина блоків збільшиться до ks ⋅ . Приклад 2. Отримаємо покриття потужності 62 =v , що лежить в основі конструкції на рис. 3, із покриття потужності 3=v заміною елементів {1}=>{1, 2}, {2}=>{3, 4}, {3}=>{5, 6}:           23 12 31 =>           4365 2143 6521 . Очевидно, МЦЗ не може будувати покриття з довжиною блока не кратною до n , що негативно впливає на оптимальність конструкцій тим більше, чим більше n , а також накладається умова кратності s на потужність покриття. Тому, застосовуючи метод циклічного зсуву для побудови FNN-конструкцій, введемо ряд модифікацій: По-перше, через умови, що накладаються на параметри FNN-конструкції, всі можливі перші блоки покриттів з 1=s можна дати у вигляді табл. 1, та ряд виключень в табл. 2, що мають місце лише при деяких комбінаціях n та ( )2,,kvC . У випадку, якщо потрібного блоку не існує, слід використовувати наступний існуючий блок та відповідний йому розмір покриття. Таблиця 1. Блоки, що визначають ( )2,,kvA Таблиця 2. Блоки-виключення для 6≤n n 1-й блок ( )2,,kvC n 1-й блок ( )2,,kvC 1 1 1 4 1, 2, 4, 8 12 2 1, 2 3≤ 5 – 20 3 1, 3, 4 7≤ 6 1, 2, 3, 6, 10, 16 26 4 1, 3, 4, 8 13≤ 6 1, 6, 7, 8, 11, 19 27 5 1, 3, 8, 9, 12 21≤ 6 1, 6, 8, 14, 15, 18 28 6 1, 2, 4, 9, 13, 19 31≤ 6 – 29 6 – 30 ISSN 1028-9763. Математичні машини і системи, 2004, № 4 9 Припустимо, що відомо: довжина блоків (кількість портів комутатора) – k ; бажана потужність покриття (кількість вузлів кластера) – v ; значення n – кількість мережевих адаптерів одного вузла. Шукатимемо оптимальне покриття для перелічених параметрів. Розрахуємо розмір покриття за формулою      +   = k vn sign k vn kvC )2,,( , (2) де [ ] – ціла частина числа, а { } – дробова. Після розрахунку розміру покриття потрібно звернути увагу на необхідну умову існування FNN-конструкції: 1)1()2,,( +−≤ nnkvC . (3) Якщо умова (3) порушується, то шуканої FNN-конструкції не існує. Співвідношення (3) випливає із наступних міркувань: Елементи покриття при заданому n можуть брати участь лише у n блоках довжини k , тому потужність покриття не може перевищувати кількість елементів, які можна розмістити в цих блоках. Кількість цих елементів, враховуючи те, що один елемент розташовано в усіх n блоках, становить 1)1( +−= knv . Оскільки побудова будь-якого покриття за ММЦЗ починається з побудови покриття МЦЗ при 1=s , в якому kn = та ( ) vkvC =2,, , то матимемо, що максимальний розмір покриття залежить лише від n , про що й говорить (3). Якщо k кратне n , модифікація МЦЗ полягатиме лише в тому, що у випадку некратності v до k , місця більших за v елементів в блоках необхідно заповнити порожніми елементами (позначатимемо їх “0”). Для покриття із прикладу 2, зі зменшеною кількістю елементів до 5=v , це матиме вигляд           4305 2143 0521 . Якщо k некратне до n , тимчасово замінимо довжину блоків на tempk – найменше кратне до n число, що більше k . Тоді матимемо в кожному блоці tempk - k тимчасових елементів. Заповнимо отриману тимчасову конструкцію згідно з МЦЗ. Задамо вектор X довжини ( )2,,kvC , всі елементи якого рівні tempk - k . Виконаємо процедуру зменшення кількості тимчасових елементів, викладену нижче. Проглядаючи покриття, оберемо блок ib з таким індексом i , що 0>ix . Знайдемо в ньому елемент je , вага якого jw найбільша поміж інших (або перша з найбільших): ∑ ∈    ≤∀− >∀ =+= ij bei i ii iij x xx yykw : 0,1 0, ),( . (4) ISSN 1028-9763. Математичні машини і системи, 2004, № 4 10 Для кожного ib , де зустрічається je , замінимо його на порожній елемент та зменшимо на одиницю ix . В усіх блоках, що містять максимальний елемент покриття, замінимо його на je . Повторюватимемо процедуру зменшення кількості тимчасових елементів доти, поки існуватиме 0>ix . Тоді в кожному блоці з’явиться не менше порожніх елементів, ніж було додано тимчасових. Прибравши з покриття всі порожні елементи та блоки з одним непорожнім елементом, отримаємо розв’язок задачі. У випадку, коли потужність отриманого покриття менше запланованої (що іноді трапляється), слід збільшити на одиницю ( )2,,kvC і, якщо умова (3) не порушується, повторити побудову покриття з моменту “Якщо k некратне до n ...”. Зауважимо, що порушення умови (3) на цій стадії алгоритму означає лише те, що ММЦЗ не може побудувати покриття із заданими параметрами, тобто не можна стверджувати, що покриття існує або не існує (не вистачає достатньої умови існування). 5. Випробування модифікованого методу циклічного зсуву Використаємо ряд покриттів ( )2,,kvА з депозитарію www.ccrwest.org як еталонні за розміром FNN-конструкції. Майже всі вони взяті з наукових публікацій і відомо, що вони оптимальні за розміром. Окрім очевидного критерію якості FNN – розміру конструкції, що позначатимемо С , пропонуються орієнтовані на практичну цінність FNN-конструкцій критерії: 1. Нехай для кожної пари вузлів підраховано кількість маршрутів, що їх зв’язує, і результат занесено в матрицю зв’язності G розміром vv× . Тоді можемо підрахувати нормоване квадратичне відхилення від середньої попарної зв’язності вузлів U : ∑∑ ∑ = = = →        −⋅−−⋅ −− = v i v j ij v p ip jisigngpisigng vv U 1 2 1 1 2 min\|\|\|)\|( 1 1 )1( 1 , (5) де Gg ij ∈ . Використання сігнум функції дозволяє не враховувати тривіальні маршрути, тобто такі, що з’єднують вузол сам із собою. Критерій є важливим для FNN-кластерів з системним програмним забезпеченням, що використовує мережеві адаптери паралельно. 2. Надлишковість попарної зв’язності вузлів R : min→−= L LL R A , (6) де L – кількість необхідних маршрутів для даного покриття за формулою (1); AL – загальна кількість маршрутів покриття. ISSN 1028-9763. Математичні машини і системи, 2004, № 4 11 Значення цього критерію фактично є більш точною характеристикою оптимальності, ніж ( )2,,kvC , покращується разом із зменшенням C при фіксованому v , але для покриттів однакового розміру дає менше значення там, де менше n . Таблиця 3. Порівняння покриттів депозитарію та МЦЗ при 1=s Депозитарій МЦЗ v k C R U C R U 4 3 3 0,5 0,222 4 1 0 5 3 4 0,2 0,375 5 0,5 0,313 6 3 6 0,2 0,192 6 0,2 0,192 7 3 7 0 0 7 0 0 8 4 6 0,286 0,397 8 0,714 0,233 9 4 8 0,333 0,427 9 0,5 0,281 10 4 9 0,2 0,395 10 0,333 0,247 11 4 11 0,2 0,176 11 0,2 0,176 12 4 12 0,091 0,09 12 0,091 0,09 13 4 13 0 0 13 0 0 Порівняємо спочатку ряд покриттів МЦЗ з 1=s , оскільки вони визначають якість ММЦЗ покриттів з більшими значеннями s . Застосовувати модифікації в цьому випадку потреби не виникає, тому порівняння говорить лише про властивості та доцільність використання МЦЗ. Також обмежимо 4≤≤ kn , оскільки практичне застосування FNN-конструкцій з 4>n дещо сумнівне. Результати порівняння для покриттів депозитарію та МЦЗ, що відповідають перерахованим вище умовам, приведено в табл. 3. Аналізуючи табл. 3, можемо сказати, що за критерієм C , а тому і за R , МЦЗ досягає якості покриттів із депозитарію в половині випадків, що досить добре (адже з ним конкурують 8 інших методів) . За значенням критерію U , МЦЗ постійно виграє, оскільки високу рівномірність зв’язності закладено в самих принципах методу. Оскільки для FNN рівномірність зв’язності вузлів U набагато важливіша за оптимальність ( )2,,kvC , то в цілому, порівняння свідчить на користь МЦЗ як такого, що відповідає вимогам до засобів побудови FNN-конструкцій. Таблиця 4. Результати порівняння для A(15,7,2) Депозитарій ММЦЗ                       15141312321 131298765 13121110432 15141110765 151498432 13121110981 7654321                       9865147 6532101311 321471514 14710131112 101311151498 0015141265 00129832 n C R U n C R U ≤ 4 7 0,4 0,504 3 7 0,19 0,362 ISSN 1028-9763. Математичні машини і системи, 2004, № 4 12 Таблиця 5. Результати порівняння для A(18,8,2) Депозитарій ММЦЗ                       181615106431 17161197541 161413128421 18171412111072 171513118763 15141296532 18131098531                       987651416 0065321817 321416151413 14161817121110 1817151413987 15141312111065 12111098732 n C R U n C R U ≤ 4 7 0,281 0,404 3 7 0,196 0,371 Тепер порівняємо покриття, що вимагають застосування ММЦЗ і відповідають за параметром k характеристикам мережевого обладнання. Аналіз табл. 4 та 5 показує рівність ММЦЗ за критерієм C із розв’язками депозитарію та перевагу ММЦЗ за критеріями R і U . Це говорить про те, що оптимальність за розміром покриттів депозитарію не забезпечує практичну цінність розв’язку для FNN-конструкцій. Тому створення окремого універсального методу побудови покриттів для розробки конструкцій кластерних суперкомп’ютерів є обґрунтованим та необхідним практично. Програмній реалізації ММЦЗ, використаній в усіх порівняльних випробуваннях вище, присвячено сторінку www.icyb.kiev.ua/~kai/oleksiy/fnn. 6. Висновки Орієнтована на побудову вартісно-ефективних кластерних суперкомп’ютерів мережева технологія FNN може бути особливо корисною у випадках, коли потреба у високопотужних комп’ютерах існує, але фінансові можливості для їх створення досить скромні. Адже проекти на основі цієї технології коштують на порядок менше, ніж рівні за потужністю суперкомп’ютери у промисловому виконанні. Поява відкритого методу розробки мережевих FNN-конструкцій та створення критеріїв їх оцінки сприятиме поширенню мережевої топології FNN та появі нових суперкомп’ютерів на її основі. Запропонований модифікований метод циклічного зсуву для побудови FNN-конструкцій показав досить високу якість розв’язків на його основі у порівнянні з еталонними ( )2,,kvА покриттями як за традиційними, так і за нововведеними критеріями. У цілому, шлях подолання проблеми низької пропускної спроможності міжвузлових мережевих каналів в обчислювальному кластері через розпаралелювання процесу комутації вбачається перспективним і таким, що відповідає концепції побудови вартісно-ефективних обчислювальних кластерів. СПИСОК ЛІТЕРАТУРИ 1. Кошулько О., Кошулько А. Высокопроизводительные вычислительные кластеры // ЭКиС. – 2004. – № 6. – С. 39–41. 2. Dietz H.G., Mattox T.I. KLAT2’s Flat Neighborhood // Proc. of the 4th Annual Linux Showcase and Conference. – Atlanta, GA, USA. – 2000. – October 12. (www.linuxshowcase.org). 3. Gordon D.M., Kuperberg G., Patashnik O. New Constructions for Covering Designs // Journal of Combinatorial Designs. – 1995. – N 3. – P. 269–284.

Застосування мережевої топології Flat Neighborhood Network для побудови кластерних суперкомп’ютерів

Institution

Similar Items