|
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“Київський політехнічний інститут”
Чионг Хонг Хань
(В’єтнам)
На правах рукопису
УДК 681.3
Топологічна організація великомасштабних відмовостійких
обчислювальних систем
Спеціальність 05.13.13 - Обчислювальні машини, системи та мережі
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Київ-2000
Дисертація є рукопис.
Робота виконана у Національному технічному університеті України “Київський політехнічний інститут” на кафедрі обчислювальної техніки
Науковий керівник - доктор технічних наук, професор,
завідувач кафедри обчислювальної
техніки Національного технічного
університету України “КПІ”
Луцький Георгій Михайлович
Офіційні опоненти: доктор технічних наук, професор,
начальник управління перспективного
розвитку інформатизації Держкомзв’язку
України Печурін Микола Капітонович
кандидат технічних наук, доцент кафедри
обчислювальних машин, систем та мереж
Київського міжнародного університету
цивільної авіації Балашов Андрій Юрійович
Провідна організація: Інститут проблем моделювання в
енергетиці Національної академії наук
України, відділ технічної діагностики.
Захист відбудеться 20 березня 2000 р. о 14.30 годині на засіданні
спеціалізованої вченої ради Д 26.002.02 в Національному Технічному Університеті України “Київський політехнічний інститут”
252056, Київ-56, пр. Перемоги, 37, корп. 18 , ауд.306
Відгуки на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати за адресою: 252056, пр. Перемоги, 37, НТУУ “КПІ”, Вченому секретарю НТУУ “КПІ”
З дисертацією можна ознайомитись у бібліотеці Національного технічного університету України “КПІ”.
Автореферат розісланий 18.03.2000 р.
Вчений секретар спеціалізованої
ради Д 26.002.02
кандидат технічних наук,
доцент Орлова М.М.
АНОТАЦІЯ
Метою дисертаційної роботи є підвищення ефективності взаємодії процесорних модулів у великомасштабних паралельних обчислювальних системах на основі подальшого розвитку їх топологічної організації з урахуванням питань відмовостійкості та алгоритмів реалізації різних видів маршрутизації.
Для досягнення поставленої мети в дисертації вирішуються такі задачі:
1. Аналіз тенденцій побудови високопродуктивних обчислювальних систем, способів і засобів підвищення їх ефективності.
2. Виділення основних показників якості топологічних організацій паралельних обчислювальних систем і аналіз існуючих топологічних організацій.
3. Аналіз способів побудови відмовостійких топологічних мереж.
4. Формування основних підходів до побудови ефективних відмовостійких топологій і синтез оптимальних топологічних мереж.
5. Розробка відмовостійких алгоритмів маршрутизації для запропонованих топологічних мереж.
6. Порівняльний аналіз параметрів ефективності існуючих і запропонованих топологічних мереж.
Автор захищає такі положення і результати:
1. Методику побудови відмовостійких топологічних мереж.
2. Відмовостійкі топологічні організації великомасштабних паралельних обчислювальних систем.
3. Алгоритми реалізації різних видів маршрутизації в запропонованих топологічних мережах.
4. Методику формування множини альтернативних шляхів в запропонованих топологіях.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. На сьогодні переважна більшість користувачів має доступ до ПЕОМ класу IBM PC, у яких досить обмежені обчислювальні можливості. У той же час, для вирішення багатьох, важливих з погляду науки і практики задач, потрібно мати істотньо більші потужні обчислювальні засоби з продуктивністю порядку мільярдів операцій в секунду (GFLOPS), а для значної їх частини, що прийнято називати “задачами великого виклику”, потрібні системи з продуктивністю порядку трильйонів операцій в секунду ( TFLOPS ).
Комп'ютери з такими рівнями продуктивності називають суперкомп’ютерами. До них звичайно належать надвисокопродуктивні мультипроцесорні, мультикомп’ютерні та векторно-конвейєрні обчислювальні системи. Ці системи показують надвисоку продуктивність на самому широкому класі задач, однак, відрізняються від інших високою вартістю.
Особливий клас суперкомп’ютерів складають обчислювальні системи з масовим паралелізмом, які можуть містити в собі сотні і тисячі мікропроцесорів. Такі суперкомп’ютери мають дуже високу пікову продуктивність, яка вже сьогодні досягає продуктивності порядку TFLOPS. Переваги даних систем визначаються такими причинами:
широкі функціональні можливості, що дозволяють вирішувати великомасштабні науково-технічні задачі;
можливість варіювання обчислювальною потужністю практично безмежена;
стандартне конструктивне виконання і можливість настроювання системи програмним способом на ефективне виконання різних задач.
Дані особливості, у свою чергу, дозволяють варіювати ступенем і рівнем розпаралелювання при розв’язанні кожної окремої задачі і тим створюють передумови для досягнення лінійної залежності показників продуктивності від числа процесорів.
До основних проблем, що виникають при розробці великомасштабних обчислювальних систем, відносяться питання міжпроцесорної взаємодії, ефективність якої залежить від параметрів топологічних мереж, які використовуються, та алгоритмів розв’язання задач маршрутизації повідомлень. Такі питання є предметом досліджень дисертаційної роботи.
Методи дослідження базуються на використанні теорії графів, комбінаторики, теорії паралельного програмування, теорії побудови паралельних обчислювальних систем, теорії організації обчислювальних процесів, теорії імовірності і математичної статистики.
Наукова новина полягає в розробці нового підходу до побудови ефективних топологічних мереж, який базується на дзеркальних кодових перетвореннях, і розв’язанні задач синтезу нових топологічних організацій, а також у розробці алгоритмів розв’язання задач маршрутизації та формування множини альтернативних шляхів для даного класу топологій.
Практична цінність результатів дисертаційний роботи полягає в тому, що використання запропонованого підходу, розроблених алгоритмів, засобів топологічного аналізу і побудови топологічних мереж дозволяє спростити процес розробки як мультикомп’ютерних систем, так і систем паралельної обробки в цілому.
Достовірність теоретичних результатів підтверджується доказом основних положень, висновків і рекомендацій, а також результатами моделювання.
Реалізація результатів роботи. Основні результати дисертаційної роботи використані при виконанні науково-дослідної роботи кафедри обчислювальної техніки: Державна наукова програма “Розробка високопродуктивного обчислювального модуля для паралельних і персональних ЕОМ”, заключний звіт по НДР № ГР 0196U003537; у навчальному процесі кафедри обчислювальної техніки в курсі “Обчислювальні системи”.
Апробація роботи. Основні наукові результати дисертаційної роботи доповідалися і обговорювалися:
На міжнародній конференції “Комп'ютерні системи і мережі”, Вища школа інформатики і керування м. Жешов, Польща, 1998.
На міжнародній конференції “Комп'ютерні системи і мережі”, Вища школа інформатики і керування м. Жешов, Польща, 1999.
Публікації. По темі дисертації опубліковано 3 роботи в наукових журналах.
Структура та об'єм роботи. Дисертаційна робота складається з вступу, чотирьох розділів, списку літератури і додатку. Зміст дисертаційної роботи викладено на 135 сторінках друкованого тексту, вона включає 10 таблиць, 35 малюнків.
У вступі дається обгрунтування актуальності дисертаційної роботи, формулюється мета і задачі досліджень, а також основні положення, що виносяться на захист.
У першому розділі розглядається область дослідження, визначаються особливості і переваги систем масового розпаралелювання, їх топологічні особливості, розглядаються задачі побудови відмовостійких паралельних систем.
В другому розділі пропонується нова методика синтезу топологічних організацій. Розглядаються основні параметри запропонованих топологій такі, як ступінь, діаметр, число вузлів.
У третьому розділі розглядаються питання маршрутизації і відмовостійкості в запропонованих топологічних організаціях.
Четвертий розділ присвячений моделюванню запропонованих топологічних організацій з метою експериментальної перевірки теоретичних результатів, отриманих у другому та третьому розділах.
У висновку сформульовані основні висновки і результати дисертаційної роботи.
У додатку наведена програма моделювання запропонованих топологічних організацій.
Стислий зміст роботи
На сьогодні запропоновано велику кількість топологічних організацій, які орієнтовані на побудову систем масового розпаралелювання. Однак при зростанні числа процесорних модулів в паралельних системах запропоновані топологічні організації часто виявляються неприйнятними, оскільки значення діаметра і ступеня при їх використанні зростуть до таких значень, які будуть недосяжні технологічно і недоцільні в плані взаємодії процесорних модулів. Отже з'являється необхідність дослідження нових підходів до топологічних побудов, які дозволяли б варіювати значеннями даних параметрів з урахуванням технологічних та організаційних вимог.
Для розв’язання задач топологічного синтезу вводимо такі позначення. Нехай число вершин у мережній топології дорівнює , де r - основа системи числення, .
Будь-яка i-та вершина мережної топології представлена таким чином:
,
де ,
Для вершин
і ,
де , введені відношення виду f , g і h.
Приклад
;
Приклад
Приклад при r=4.
Швидко нарощувана топологічна мережа (ШНТМ).
На основі розглянутих відображень конструювання топології здійснюється таким способом.
На першому етапі, відповідно до відображення i = f(j), формується мережа нульового рівня , де , F0={<i,j>|i=f(j)}, яка характеризується такими параметрами:
Мережа даного рівня складається з r елементів і є повнозв’язною.
Починаючи з другого рівня, мережа де (), формується у відповідності з такими правилами:
1. Для формування мережі використовується мереж , де - число вершин у . При цьому .
2. Нумерація вершин у мережі формується на основі конкатенації номера мережі у і номера вершини в .
3. Остаточне формування мережі здійснюється шляхом додавання нових зв'язків між симетричними вершинами мережі . При цьому спочатку використовується відображення g , а далі, якщо існує таке i, при якому i= g(i), використовується відображення h . Надалі ці зв'язки будемо визначати відношенням : , де .
Формально дану мережу можна визначити таким способом:
Gn =(Xn,Fn) , де ;
, де ;
,
де ; ; ;
; ; .
1. Граф Gn не має петель.
2. Між двома підграфами Gn-1 існує, як мінімум, один зв'язок.
3. Для Gn є справедливим таке:
;
;
,
де Nn, Dn, Sn відповідно є число вершин, діаметр та ступень топології Gn.
На мал. 1 наведено приклад ШНТМ.
Помірно нарощувана топологічна мережа (ПНТМ).
Розглянуті вище відношення f, g, h дозволяють конструювати ще один клас топологій - .
Топологією першого рівня, як і у випадку з ШНТМ, є повнозв’язний граф.
Мал. 1. Швидко нарощувана топологічна мережа (ШНТМ)
для r = 4 , n = 1.
Починаючи з другого рівня мережа , де () формується у відповідності з такими правилами:
1. Мережа Gl формується з r мереж -го рівня, причому , що і визначає принципову відмінність між ШНТМ та ПНТМ.
2. Нумерація вузлів у мережі Gl формується на основі конкатенації номера мережі Gl-1 у Gl і номера вузла в Gl-1.
3. Формування мережі Gl на основі мереж Gl-1 здійснюється шляхом прокладання нових зв'язків між симетричними вузлами мережі Gl. При цьому спочатку використовується відображення g , а далі, якщо існує таке i, що i= g(i), то використовується відображення h. Зв'язки даного типу будемо визначати відношенням , де . На мал.2 наведено приклад ПНТМ.
Топологія Gn може бути визначена таким чином:
Gn =(Xn,Fn) ,
де ;
| 
