Національна академія наук України
Інститут кібернетики імені В.М. Глушкова

БОРИСОВ Євген Сергійович

УДК 519.683.004.424

АВТОМАТИЗОВАНА СИСТЕМА РОЗПАРАЛЕЛЮВАННЯ ПОСЛІДОВНИХ ПРОГРАМ ДЛЯ ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЧІВ
З РОЗПОДІЛЕНОЮ ПАМ'ЯТТЮ

01.05.03 - математичне та програмне забезпечення
обчислювальних машин і систем

Автореферат
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук

Київ - 2005

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.

Науковий керівник: доктор фізико-математичних наук, професор
Капітонова Юлія Володимирівна,
Інститут кібернетики імені В.М.Глушкова НАН України,
завідуюча відділом.

Офіційні опоненти: доктор фізико-математичних наук, старший науковий співробітник
Клименко Віталій Петрович,
Інститут проблем математичних машин і систем НАН України,
заступник директора,

кандидат фізико-математичних наук, доцент
Гороховський Семен Самуїлович,
Національний університет ''Києво-Могилянська академія'',
директор Інформаційно-комп'ютерного центру.

Провідна установа: Київський національний університет імені Тараса Шевченка,
факультет кібернетики,
кафедра теоретичної кібернетики.

Захист відбудеться 24 лютого 2006 р. об 11 годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою:
03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий 18 січня 2006 р.

Учений секретар
спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Поява технологій, що дозволяють створювати відносно недорогі та досить потужні процесори, природно відкрила шлях до переходу на багатопроцесорні системи - від невеликих 2-8-процесорних систем до великих надпотужних обчислювачів, які містять в собі тисячі процесорів. Сьогодні ми є свідками появи персональних кластерних систем. Це, як і поява персональних комп'ютерів в 80-і роки ХХ століття, істотно змінює ситуацію в цілому. Рядовому користувачеві відкрився доступ до якісно нового, незрівнянно могутнішого, чим персональний комп'ютер, інструменту для вирішення його спеціальних проблем. Наведемо кілька прикладів актуальних завдань, що вимагають надпотужних обчислювальних систем.

У лабораторіях компанії Ford Motor активно використовуються векторні комп'ютери SGI/Cray T90, на яких досягнуто рекордного рівня швидкості (1 GFLOPS/sec) роботи системи моделювання процесів руйнування автомобіля при аварії - RADIOSS. За результатами випробування своїх автомобілів, Ford одержала в США високу оцінку по забезпеченню безпеки на дорогах.

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

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

Після землетрусу в Північній Каліфорнії (США) знаменитий міст Golden Gate Bridge залишився цілий, однак стало очевидно, що міст необхідно зміцнювати. На базі суперкомп'ютерного центра Сан-Дієго (SDSC) проведено детальний чисельний аналіз стану мосту. Для реалізації розрахунків використано суперкомп'ютер Cray. Було змодельовано близько 20 випробувань, кожне з яких зажадало від 6 до 8 годин машинного часу. Отримані результати допомогли підготувати інженерні рішення по реконструкції, а також оцінити вартість роботи.

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

У фармацевтичному дослідницькому центрі BioNumerik у Сан-Антоніо (США) встановлені суперкомп'ютери SGI/Cray, що дозволяють розробляти нові лікарські препарати за допомогою попереднього комп'ютерного моделювання. Завдяки суперкомп'ютерам загальний час доклінічної розробки препаратів знизився з 6 років до 18-24 місяців. У ході досліджень, менше чим за один рік, може бути зроблене моделювання поводження більше ніж 12 трильйонів різних хімічних сполук - кандидатів на використання як необхідних препаратів.

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

Зв'язок роботи з науковими програмами. Реалізація системи автоматизованого розпаралелювання була включена у державні програми України ''Створення та підготовка серійного виробництва ряду високопродуктивних інтелектуальних ЕОМ та спеціалізованого паралельного програмного забезпечення для розв'язання складних завдань в економіці, науці, безпеці та обороні України та інших галузях народного господарства'' (шифр В.К.245.20, номер держреєстрації 0104U008936), "Розробка математичної теорії взаємодії компонент комп'ютерного середовища та її застосування у системі програмування АПС" (шифр В.Ф.100.03, номер держреєстрації 0198U000320), "Розробка ефективних формалізмів для відображення процесів свідомої (інтелектуальної) діяльності у техногенному середовищі і засобів її комп'ютерної підтримки" (шифр В.Ф.100.04, номер держреєстрації 0198U001775), "Розробити дедуктивні методи верифікації теорем з математики та програмного забезпечення ЕОМ" (шифр В.Ф.100.05, номер держреєстрації 0102U000496), "Розробити методи та засоби продукування і маніпулювання знаннями у операційному середовищі інтелектуалізації інформаційних технологій" (шифр В.Ф.К.105.01, номер держреєстрації 0102U003204), "Розробити ефективні формалізми та засоби їх підтримки для розв'язання інтелектуальних задач у техногенному середовищі" (шифр В.Ф.100.06, номер держреєстрації 0103U000704).

Мета і завдання дослідження. Мета дисертаційної роботи - створення автоматизованої системи розпаралелювання послідовних програм для паралельних обчислювачів з розподіленою пам'яттю. Для досягнення поставленої мети в роботі були розв'язані такі основні задачі:
побудована модель послідовної програми;
побудована модель паралельної програми;
побудоване відображення послідовної програми в паралельну;
показана коректність цього відображення;
у відповідності до отриманих алгебраїчних моделей побудована реалізація транслятора- розпаралелювача послідовних програм мовою C.

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

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

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

Методи дослідження. У дисертації застосовується алгебродинамічний підхід до побудови математичних моделей паралельних обчислень, який ґрунтується на алгебрі алгоритмів Глушкова та роботах Ю.В. Капітонової, О.А. Летичевського, І.В. Сергієнко,
О.Л. Перевозчикової, С.С. Гороховського, А.Ю. Дорошенко. Для опису функціонування моделей будемо використовувати поняття теорії дискретних динамічних систем.

З метою реалізації моделі автоматизованої системи розпаралелювання послідовних програм використовується апарат теорії формальних мов і генератори лексичних і синтаксичних аналізаторів lex, yacc.

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

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

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

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

? показано коректність перетворення послідовної програми у паралельну, доведена дедуктивна еквівалентність моделей послідовної та паралельної програм;

? реалізований транслятор-розпаралелювач delta, що перетворює програму розширеною мовою C у паралельну MPI-програму мовою C.

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

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

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

На відміну від цього класу систем в даній роботі представлена реалізація системи розпаралелювання, що ґрунтується на відомій мові програмування C, яка дозволяє без особливих проблем розпаралелити вже існуючі програми та істотно спрощує освоєння системи користувачами.

На основі алгебродинамічної моделі, описаній в цій роботі, реалізований транслятор- розпаралелювач delta, що перетворює програму розширеною мовою C у паралельну MPI-програму мовою C. Важливою особливістю даної системи є ''гладкий синтаксис''. Граматика мови відрізняється від стандартного C додаванням лише одного ключового слова. Програма для розпаралелювача delta може (без істотних змін) оброблятися звичайним (послідовним) транслятором мови C, при цьому отримуємо звичайну (послідовну) програму.

Особистий внесок. Всі зазначені результати отримані автором самостійно. Моделі ґрунтуються на алгебродинамічному підході, відомих принципах асинхронного виклику підпрограми та неготового значення.

Апробація результатів. Реалізація системи автоматизованого розпаралелювання була включена у державну програму по розробці кластерної системи СКИТ та успішно випробувана на кластері Інституту кібернетики імені В.М.Глушкова НАН України.

Публікації. Результати за темою дисертаційної роботи відображені у 5 публікаціях: 3 статті у наукових журналах та 2 публікації в тезах наукових конференцій.

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

ОСНОВНИЙ ЗМІСТ РОБОТИ

Робота присвячена проблемі розпаралелювання послідовних програм.

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

У першому розділі ''Паралельні обчислення'' показано сучасний стан технологій та засобів паралельних обчислень.

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

У підрозділі 1.2 розглянуто методи та засоби для побудови високопродуктивних паралельних обчислювачів. Описано архітектури паралельних обчислювачів за класифікаціями Флінна та Джонсона, розглянуто методи паралельного програмування та оцінки ефективності роботи паралельної програми, балансування завантаження паралельної системи. Наведено загальну трирівневу схему паралельного обчислювача; зроблено порівняльний аналіз та класифікація апаратних засобів для паралельних обчислень (SMP, MPP, NUMA, кластерні та інші системи), а також порівняльний аналіз найбільш відомих комунікаційних бібліотек (PVM, OpenMP, MPI та ін.). Описано порядок роботи з бібліотекою MPI на кластерній системі. Розглянуто засоби автоматизованого розпаралелювання.

У підрозділі 1.3 описані методи та математичні моделі паралельних обчислень, а також методи побудови розподілених систем, до яких належать високопродуктивні паралельні обчислювачі з розподіленою пам'яттю. Розглянуто алгебродинамічний підхід до побудови моделей для паралельних обчислень на основі алгебри алгоритмів Глушкова. Описані моделі пам'яті для паралельних обчислень; зроблено порівняльний аналіз різних алгебродинамічних моделей паралельних програм, огляд методів побудови трансляторів. Ці методи та засоби безпосередньо використані при реалізації моделі розпаралелювача, описаного в цій роботі.

Перший розділ завершується підрозділом “Висновки”, в якому підсумовується викладене.

У другому розділі сформульована та вирішена проблема розпаралелювання послідовних програм.

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

У підрозділі 2.2 побудована алгебраїчна модель автоматизованої системи розпаралелювання послідовних програм для паралельного обчислювача з розподіленою пам'яттю.

Рис. 1. Асинхронний виклик підпрограми

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

Система автоматизованого розпаралелювання описується трьома основними алгебродинамічними моделями :

S - модель вхідної послідовної програми, що складається з певної множини підпрограм; P- модель паралельної програми. Дана модель побудована на основі парадигми обміну повідомленнями і описує статичне розпаралелювання, тобто кількість компонентів паралельної програми фіксовано; P орієнтована на системи з розподіленою пам'яттю без спільної зовнішньої пам'яті (наприклад, кластерна система на основі мережі персональних комп'ютерів); - відображення послідовної програми S в паралельну програму P.

Модель послідовної програми визначається як упорядкована множина пар S. Кожна така пара визначає підпрограму в S:

, | (1)

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

Додатково визначені оператори виклику підпрограми та повернення з підпрограми:

? оператор виклику підпрограми : , де - ім'я програми, що викликається; - вхідні параметри; - результати;

? оператор повернення з підпрограми : де - результати.

Процес виконання послідовної багатокомпонентної програми S описується дискретною динамічною системою:

,

де ? S- послідовна багатокомпонентна програма (див. (1));

? - множина станів ; стан визначимо так : , де b- стан пам'яті; R- стан керування (залишкова програма); - список викликів підпрограм ;

? - початковий стан;

? - множина заключних станів;

? - відношення переходів.

Модель паралельної програми визначена як впорядкована множина пар P. Кожна така пара визначає паралельний процес:

, | (2)

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

Додатково визначені два типи операторів обміну даними між компонентами паралельної програми:

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

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

Процес виконання послідовної багатокомпонентної програми P описується дискретною динамічною системою:

,

де ? P - паралельна програма (див. (2));

? - множина станів ; стан визначимо так :

,

де - ім'я компонента паралельної програми P; - стан пам'яті компоненти ; - стан керування компонентом (залишкова програма при виконанні ); - матриця (тут n - кількість компонентів в P), де - черга значень змінних із внутрішньої пам'яті компоненти на передачу в компоненту ; ;

? - початковий стан ;

? - множина заключних станів ;

? - відображення переходів.

Модель транслятора-розпаралелювача оформлена у вигляді чотирьох доведених тверджень.

Лема 1. послідовної програми S виду (1) існує відображення , де P - паралельна програма виду (2).

Лема 2. паралельної програми P виду (2) існує відображення , де S - послідовна програма виду (1).

Лема 3. послідовної програми S виду (1) справедливо .

Означення 1. Ланцюжки регулярних програм P та S в алгебрі алгоритмів назвемо дедуктивно еквівалентними якщо існують перетворення такі що та .

Теорема 4. Послідовна програма виду (1) та паралельна програма виду (2) дедуктивно еквівалентні.

У третьому розділі “Реалізація” описується реалізація вищеописаної, автоматизованої системи розпаралелювання послідовних програм для мови C і стандарту побудови паралельних програм MPI.

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

Рис.2. Схема роботи delta

У даній роботі обрано шлях розпаралелювання програм популярною мовою C. На основі алгебродинамічних моделей, описаних в цій роботі, реалізовано транслятор-розпаралелювач delta, що перетворює програму розширеною мовою C у паралельну MPI- програму мовою C.

У підрозділі 3.1 описана система автоматизованого розпаралелювання delta, яка являє собою транслятор текстів програм мовою . Результатом роботи delta є текст паралельної MPI-програми мовою C (рис.2).

Важливою особливістю даної системи є ''гладкий синтаксис''. Граматика мови відрізняється від стандартного C додаванням лише одного ключового слова - asyncron, яке визначає функцію, що може викликатися асинхронно, тобто виконуватися паралельно з іншими частинами програми. Програма для розпаралелювача delta може (без істотних змін) оброблятися звичайним (послідовним) транслятором мови C, для чого досить додати в заголовок програми макрос-заглушку #define asyncron, у цьому випадку виходить звичайна (послідовна) програма (рис. 3).

Текст розпаралелювача delta можна отримати на сайті http://www.mechanoid.kiev.ua.

Рис. 3. Спрощена схема роботи delta

У підрозділі 3.2 описано спосіб використання системи розпаралелювання delta. Для того, щоб скористатися системою автоматизованого розпаралелювання delta, необхідно пройти такі етапи:

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

asyncron int my_big_func() { /* just do it :) */ return 0; }

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

2. Трансляція виконується командою delta. Крім тексту MPI-програми, транслятор видає кількість паралельних компонентів цієї програми. Це число використовується утилітою mpirun, яка запускає паралельні MPI- програми.

$ delta myprog.c > myprog_mpi.c

components : 4

$ mpicc myprog_mpi.c -o myprog_mpi

$ mpirun -machinefile machines -np 4 myprog_mpi

У підрозділі 3.3 наведені приклади використання системи автоматизованого розпаралелювання delta: обчислення як суми ряду та множення матриць.

? Число обчислюється як інтеграл

,

де ; ; ; час роботи на 1 процесорі 108 с, на 2 процесорах - 57 с.

? Множення матриць розміру , час роботи на 1 процесорі 12 хв.,
на 2 процесорах - 7 хв.

ВИСНОВКИ

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

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

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

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

4. Показано коректність перетворення послідовної програми у паралельну. Доведена дедуктивна еквівалентність моделей послідовної та паралельної програм.

5. Реалізований транслятор-розпаралелювач delta, що перетворює програму розширеною мовою C у паралельну MPI-програму на C.

6. Наведені приклади використання системи автоматизованого розпаралелювання delta: обчислення як суми ряду та множення матриць розміру .

7. Реалізація системи автоматизованого розпаралелювання була включена у державні програми України.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ:

1. Борисов Е.С. Полуавтоматическая система декомпозиции последовательных программ для параллельных вычислителей с распределенной памятью // Кибернетика и системный анализ. - 2004. - 3, - C. 139.

2. Борисов Е.С. Использование языка MC# для реализации параллельных алгоритмов в 3D моделировании // Там же. - 2004. - 1. - C. 165.

3. Борисов Е.С. Использование языка MC# для реализации параллельного классификатора образов // Там же. - 2005. - 3. - C. 179.

4. Борисов Е.С. Многомашинный вычислительный комплекс на аппаратной базе ЛВС ПК // Информационные технологии в XXI веке: Сб. докл. и тез. - Днепропетровск, 2003. - C. 51.

5. Борисов Е.С. Декомпозиция последовательных программ при параллельных вычислениях // Материалы третьего междунар. науч.-практ. семинара ''Высокопроизводительные параллельные вычисления на кластерных системах''. - Нижний Новгород, 2003. - C. 25.

АНОТАЦІЇ

Борисов Є.С. Автоматизована система розпаралелювання послідовних програм для паралельних обчислювачів з розподіленою пам'яттю. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем. - Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2005.

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

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

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

Ключові слова: кластер, паралельні обчислення, паралельне програмування, розпаралелювання, MPI.

Борисов Е.С. Автоматизированная система распараллеливания последовательных программ для параллельных вычислителей с распределенной памятью. - Рукопись.

Диссертация на соискание научной степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. - Институт кибернетики имени В.М. Глушкова НАН Украины. Киев, 2005.

Возможности наращивания производительности вычислителей путем совершенствования их элементной базы имеют естественный предел, определяемый физическими свойствами материалов, из которых изготовляются процессор, память и другие устройства, составляющие компьютер. Используя этот подход вряд ли возможно бесконечное увеличение вычислительной мощности. К тому же существенное увеличение производительности отдельных процессоров связаны со значительным увеличением стоимости аппаратуры. Естественным решением этой проблемы стало использование многопроцессорных архитектур и методов параллельной обработки данных.

Обратной стороной высокой производительности суперкомпьютеров является сложность их использования. Для параллельных вычислителей необходимо создавать специальные программы. В тексте такой программы определяются части (ветки), которые могут выполняться параллельно, а также алгоритм их взаимодействия. Причем распараллелить задачу можно далеко не единственным способом. При написании и использовании параллельных программ возникает ряд затруднений, например проблемы, связанные с переносимостью и оптимизацией для конкретной параллельной системы. Кроме того, написание низкоуровневых параллельных программ требует от программиста специальной подготовки. Поиск решения этих проблем в конечном итоге приводит к идее создания автоматизированных систем распараллеливания задач и оптимизации параллельных систем.

Работа посвящена проблеме распараллеливания последовательных программ. Основным результатом этой работы является алгебраическая модель, описывающая подход к созданию систем распараллеливания, который обеспечивает корректность преобразования.

Сформулирована и решена проблема распараллеливания последовательных программ для параллельных вычислителей с распределенной памятью.

В этой работе применяется алгебродинамический подход к построению математических моделей параллельных вычислений, который основывается на алгебре алгоритмов Глушкова. Для описания функционирования моделей использована теория дискретных динамических систем. В основе этих моделей лежат принцип асинхронного вызова подпрограммы и принцип неготового значения.

Построены: математическая модель последовательной программы; математическая модель параллельной программы для параллельных вычислителей с распределенной памятью; отображение последовательной программы в параллельную программу, которое описывается дискретной динамической системой. Показана корректность преобразования последовательной программы в параллельную программу. Доказана дедуктивная эквивалентность моделей последовательной и параллельной программ.

В соответствии с построенной математической моделью реализована система автоматизированного распараллеливания delta, которая преобразует программу на расширенном языке C в параллельную MPI-программу на языке C. Важной особенностью данной системы является ''гладкий синтаксис'', грамматика языка отличается от стандартного C добавлением всего лишь одного ключевого слова. Программа для распараллеливателя может, без существенных изменений, обрабатываться обычным (последовательным) транслятором языка C, в этом случае получается обычная (последовательная) программа. Приведены примеры использования delta: вычисление суммы ряда и умножение матриц.

Реализация системы автоматизированного распараллеливания была включена в государственную программу Украины ''Створення та підготовка серійного виробництва ряду високопродуктивних інтелектуальних ЕОМ та спеціалізованого паралельного програмного забезпечення для розв'язання складних завдань в економіці, науці, безпеці та обороні України та інших галузях народного господарства'' (шифр В.К.245.20, номер госрегистрации 0104U008936) и в другие программы. Cистема распараллеливания delta успешно опробована на кластере Института кибернетики имени В.М. Глушкова НАН Украины.

Ключевые слова: кластер, параллельные вычисления, параллельное программирование, распараллеливание, MPI

Evgeny S. Borisov Automatic system of pararalelizing sequential programs for parallel computers with distributed memory. - Manuscript.

Thesis for a candidate degree on physics and mathematics (Ph.D.) by speciality
01.05.03 - computer software. - V.M. Glushkov Institute of Cybernetics of The National Academy of Sciences of Ukraine, Kiev, 2003.

The dissertation is devoted to problem of parallelizing sequential programs. Main result of this work is algebraic model, which described creation method of parallelizing systems, corrected result are guarantee.

Main results: created mathematical model of sequential program, Glushkov algebra and algebra-dynamic method are used; created mathematical model of parallel program for parallel computers with distributed memory; created model of translator from sequential to parallel program, transition systems are used. Correctness of translator model are demonstrate.

Automatic system of pararalelizing delta are realized, which translate sequential programs on programming language C to MPI parallel programs on programming language C. Examples for translator delta are included.

Translator delta are included in Ukrainian government program ''Створення та підготовка серійного виробництва ряду високопродуктивних інтелектуальних ЕОМ та спеціалізованого паралельного програмного забезпечення для розв'язання складних завдань в економіці, науці, безпеці та обороні України та інших галузях народного господарства'' (code В.К.245.20, registration number 0104U008936), and other programs.

Keywords: cluster, parallel calculations, parallel programming, parallelizing, MPI.

Підп. до друку 09.12.2005. Формат 60x84/16. Офс. друк.
Папір офс. Ум. друк. арк. 0,93. Ум. фарбо-відб. 1,16.
Обл.-вид.арк. 1,0. Зам. 238. Тираж 110 прим.

Редакційно-видавничий відділ з поліграфічною дільницею
Інституту кібернетики імені В.М. Глушкова НАН України
03680, МСП, Київ-187, проспект Академіка Глушкова, 40