Топологічна організація великомасштабних відмовостійких обчислювальних систем

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

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

“Київський політехнічний інститут”

ЧионгХонгХань

(В'єтнам)

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

УДК 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 - основа системи числення.

Формально дану мережу можна визначити таким способом:

G_n =(X_n,F_n)

Помірно нарощувана топологічна мережа (ПНТМ).

Розглянуті вище відношення f, g, hдозволяють конструювати ще один клас топологій.

Топологією першого рівня, як і у випадку з ШНТМ, є повнозв'язний граф.

Починаючи з другого рівня мережа , де() формується у відповідності з такими правилами:

1. Мережа G_l формується з r мереж-го рівня, причому , що і визначає принципову відмінність між ШНТМ та ПНТМ.

2. Нумерація вузлів у мережі G_l формується на основі конкатенації номера мережіG_l-1 уG_l і номера вузла в G_l-1.

3. Формування мережі G_l на основі мереж G_l-1 здійснюється шляхом прокладання нових зв'язків між симетричними вузлами мережі G_l. При цьому спочаткувикористовується відображення g , а далі, якщо існує такеi,щоi= g(i), то використовується відображення h. Зв'язки даного типу будемо визначати відношенням, де . На мал.2 наведено приклад ПНТМ.

ТопологіяG_n може бутивизначена таким чином:

G_n =(X_n,F_n)

Размещено на Allbest.ru