КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
ІМЕНІ ТАРАСА ШЕВЧЕНКА
ДЕРЕВ’ЯНЧЕНКО ОЛЕКСАНДР ВАЛЕРІЙОВИЧ
УДК 681.3
РОЗРОБКА ПАРКС-JAVA ТЕХНОЛОГІЇ
ПАРАЛЕЛЬНОГО ПРОГРАМУВАННЯ
НА КОМП’ЮТЕРНИХ МЕРЕЖАХ
Спеціальність 01.05.03 – математичне та програмне забезпечення
обчислювальних машин і систем
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ-2005
Дисертацією є рукопис.
Робота виконана на кафедрі математичної інформатики
факультету кібернетики Київського національного
університету імені Тараса Шевченка.
Науковий керівник: доктор фізико-математичних наук, професор
Анісімов Анатолій Васильович,
Київський національний університет імені Тараса Шевченка,
завідувач кафедри
Офіційні опоненти: доктор фізико-математичних наук, професор
Дорошенко Анатолій Юхимович, Національний технічний
університет України “Київський політехнічний інститут”, професор
кандидат фізико-математичних наук, старший науковий співробітник
Гороховський Семен Самуїлович, Національний університет
“Києво-Могилянська академія”, МОН України, доцент
Провідна установа: Інститут кібернетики ім. В.М. Глушкова НАН України,
відділ автоматизації програмування
Захист дисертації відбудеться 15 грудня 2005 року о “ 14 “ годині на засіданні
спеціалізованої вченої ради Д 26.001.09 Київського національного
університету імені Тараса Шевченка
(03127, м. Київ, пр. Глушкова, 2, корп. 6, ф-т кібернетики, ауд. 40.
Тел. 521-33-66. Факс 259-70-44. E-mail: rada1@unicyb.kiev.ua)
З дисертацією можна ознайомитися у Науковій бібліотеці Київського
національного університету імені Тараса Шевченка
(01033, м. Київ, вул. Володимирська, )
Автореферат розісланий 15 листопада 2005 року.
Вчений секретар спеціалізованої вченої ради,
кандидат фізико-математичних наук, доцент В.П.Шевченко
Загальна характеристика роботи
Актуальність теми дослідження. Бурхливий прогрес в комунікаційних технологіях та надзвичайна складність обчислювальних задач спричиняють поширення розподілених інформаційних сервісів. Поява і швидке розповсюдження мов програмування нового покоління, таких, як JAVA, спричинило появу нового напрямку в дослідженнях проблем програмування мультиплатформних розподілених і паралельних застосувань. Все це зумовило необхідність створення універсальних інформаційних систем паралельної обробки інформації (СПОІ) нового типу.
Проблемам моделювання та побудови систем паралельної обробки інформації були присвячені роботи Глушкова В.М., Анісімова А.В., Дорошенка А.Ю., ЛавріщевоїК.М., Летичевського О.А. та ін. Їх дослідження сприяли як математичному вдосконаленню традиційних алгоритмів паралельної обробки інформації, так і появі відповідних програмних систем.
На початку 80-х років ХХ століття виникла концепція керуючого простору (КП). Це була спроба створити метод опису і керування функціонуванням систем, які складаються з взаємодіючих паралельних обчислювальних процесів, склад та зв’язки між якими можуть динамічно змінюватись. Протягом останніх двадцяти років розуміння ролі та способів використання КП зазнало еволюційного розвитку. На основі цих досліджень Анісімовим А.В. було запропоновано технологію ПАРКС (Паралельні Асинхронні Рекурсивно Керовані Системи), як універсальний засіб побудови СПОІ. Проблематикою створення СПОІ займаються впливові світові дослідницькі наукові центри у різних куточках світу. На сьогодні запропоновано досить багато програмних засобів різного рівня для опису паралельно функціонуючих та взаємодіючих систем. Базовими серед них є MPI, MPICH, HPF, OpenMP, DVM та ін .
В даний час ця тематика бурхливо розвивається, тому важливою задачею дисертаційного дослідження стало вивчення властивостей та архітектурних особливостей систем паралельної обробки інформації, зокрема вивчення процесів розпаралелювання та взаємозв'язку між вузлами системи, що мають адекватно враховувати специфічні умови таких систем. Для дослідження практичного застосування СПОІ була створена система підтримки паралельних обчислень ПАРКС-JAVA.
Спектр застосування СПОІ є надзвичайно широким і охоплює усі актуальні задачі соціально значущого розподіленого інформаційного простору. Це передусім задачі економічного характеру, проблеми технологічного передбачення, задачі економічного прогнозу, що особливо важливо для економіки перехідного періоду. Наші екологічні проблеми потребують постійного і всебічного моніторингу. Важливими є також задачі розвитку наукових досліджень, питання ефективного використання супутників Землі для розвитку народного господарства, проблеми проектування складних машин (літаків, енергетичних котлів, ракетної техніки), задачі військового комплексу.
Зв’язок з науковими програмами, планами, темами. Дисертаційне дослідження виконувалося в рамках наукової теми “Створення технології програмування для перспективних паралельних обчислювальних комплексів” (державний реєстраційний номер 0197U014604) та теми “Розробка систем інтелектуалізації інформаційних технологій та дистанційного навчання” (державний реєстраційний номер 0101U002170), які виконувались на кафедрі математичної інформатики факультету кібернетики Київського національного університету імені Тараса Шевченка.
Мета та завдання дослідження. Метою дослідження є моделювання та побудова системи паралельної обробки інформації, розробка методики реалізації паралельних програм та демонстрація можливостей їх практичного застосування. У відповідності до поставленої мети визначено такі основні завдання дослідження:
проаналізувати відомі сучасні системи паралельної обробки інформації та зроблено порівняння з технологією ПАРКС; виявити найбільш ефективні засоби реалізації СПОІ;
розробити методику побудови СПОІ на основі вивчених та формалізованих в ході дослідження технологічних підходів;
специфікувати спеціальну прикладну формальну модель для моделювання паралельних програм і вивчити її властивості;
створити програмну систему на базі мови програмування JAVA, що реалізує побудовану математичну модель;
на основі викладеної методики спроектувати архітектуру СПОІ;
розробити програмну архітектуру із застосуванням ПАРКС-технології для паралельної обробки даних на комп’ютерних мережах.
Об’єктом дослідження дисертації є паралельні обчислювальні системи та паралельні програми.
Предметом дослідження виступають методи побудови паралельних обчислювальних систем і способи їх практичної реалізації. Основна увага приділена аналізу розпаралелювання програм та їх формалізації.
Методи дослідження базуються на використанні сучасних теорій побудови розподілених та паралельних обчислювальних систем, засобів теорії графів та математичної логіки.
Наукова новизна дослідження полягає в наступному:
вперше досліджено можливості ПАРКС технології, як класу розподілених інформаційних систем паралельної обробки інформації на комп’ютерних мережах та кластерах;
створено та обґрунтовано загальну методику проектування та реалізації паралельних обчислювальних систем з застосуванням технології ПАРКС для паралельної обробки інформації на комп'ютерних мережах;
розширено базову мову програмування JAVA засобами для написання паралельних програм;
специфіковано формальну модель паралельної програми у вигляді спеціальної прикладної термінальної програми(ТП) і досліджено її властивості; на базі цієї моделі побудовані нові алгоритми розпаралелювання програм.
створено ефективні алгоритми керування паралельними обчислювальними процесами; математично досліджені оцінки часової складності розроблених алгоритмів;
розроблено нову архітектуру та побудовано паралельну обчислювальну систему ПАРКС- JAVA.
Практичне значення дослідження. Результати роботи можуть бути використаними при створенні різноманітних мережевих обчислювальних комплексів. Реалізація даної системи може застосовуватися для розв’язування широкого класу задач, що потребують паралельної обробки. Це такі задачі, як обробка зображень, розв’язання диференціальних рівнянь, моделювання довготривалих процесів, у тому числі й у реальному часі, багато інших наукових та інженерних задач, а також інші види потокової обробки даних. Представлені у додатку програмні модулі ПАРКС-JAVA дозволяють писати паралельні програми, як на машинах з одним процесором, так і з застосуванням локальних та глобальних мереж і кластерів.
Матеріали дослідження використовуються в навчальному процесі факультету кібернетики Київського національного університету імені Тараса Шевченка.
Особистий внесок здобувача. Всі основні результати дисертації одержані автором самостійно. У спільно виконаних з науковим керівником роботах Анісімову А.В. належить загальна постановка задачі та участь в обговоренні результатів дослідження. У спільно виконаній роботі [3] Лялецькому О.О. належить порівняння різних підходів для побудови формальної моделі програми. В роботі [5] Медведєву М. Г. належить ідея маршрутизації на мережі. У спільно виконаній роботі [8] Літвінову Д.В. належить аналіз та дослідження тестування моделей паралельної обробки інформації за допомогою мови ПАРКС-JAVA.
Апробація результатів. Результати дослідження доповідалися на семінарах факультету кібернетики Київського національного університету імені Тараса Шевченка, Інституту кібернетики НАН України, а також міжнародних наукових конференціях:
"Тheoretical and applied aspects of program systems development", Україна, Київ, жовтень 2004р.;
Міжнародна науково-практична конференція "Интеллектуальные и многопроцессорные системы", Крим, Кацевелі, вересень 2004р.;
IV міжнародна науково-практична конференція "УкрПРОГ'2004", Україна, Київ, червень 2004р.;
Міжнародна науково-практична конференція "Интеллектуальные и многопроцессорные системы", Росія, Дивноморське, вересень 2003р.
Публікації. Основні результати дисертації опубліковано в 9 роботах, з яких 6 робот у фахових наукових виданнях.
Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, основної частини з п’яти розділів, висновків, списку використаних джерел з 110 найменувань та 2 додатків. Загальний обсяг дисертації - 155 сторінок, обсяг основного тексту - 110 сторінок, ілюстрованих 5 таблицями та 10 рисунками.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У Вступі обґрунтовується актуальність теми, зв’язок з науковими програмами, формулюються мета і завдання дослідження, предмет, об’єкт і методи дослідження, відзначається наукова новизна й практичне значення, а також апробація отриманих результатів, характеризується структура роботи.
У першому розділі “Огляд систем паралельної обробки інформації” дається визначення паралельних та розподілених систем ЕОМ та досліджуються властивості та методи побудови та застосування систем даного класу.
У підрозділі 1.1 надаються основні поняття та означення СПОІ, розвиток яких сприяв розвитку даної тематики.
Паралельний комп’ютер – це набір процесорів, що можуть працювати спільно при вирішенні обчислювальних задач.
Паралельне обчислення складається з одної або більше задач, що одночасно виконуються.
Система паралельної обробки інформації – це обчислювальна система паралельної дії, що забезпечує одночасне виконання операцій за однією, або кількома програмами. Вона складаються з трьох основних складових: процесорів (процесорних блоків), блоків пам’яті та мережі каналів (комутації).
У підрозділі 1.2 розглядаються архітектури обчислювальних систем, які ми будемо класифікувати за типами потоків команд та даних. Будемо розрізняти чотири класи обчислювальних систем, які були наведені М. Дж. Флінном. Зроблено їх порівняльний аналіз.
У підрозділі 1.3. наводяться основні моделі паралельних обчислень:
процес/канал (Process/Channel);
обмін повідомленнями (Message Passing);
паралелізм даних (Data Parallel);
загальної пам’яті (Shared Memory).
Вказуються відповідні архітектури систем паралельних обчислень.
У підрозділі 1.4. наведено основні сучасні системи та мови паралельних обчислень MPI та MPICH, OpenMP, DVM, HPF, mpC. Розглядаються практичні проблеми, що з ними пов’язані. Переваги використання того або іншого підходу визначають наступні фактори:
легкість програмування;
ефективність розроблених програм;
можливість переносу і повторного використання програм;
якість засобів налаштування програм.
На основі одержаних результатів пропонується та обґрунтовується методика побудови СПОІ.
Розглянуті тенденції розвитку архітектури і використання комп’ютерних мереж дозволяють припустити, що у майбутньому паралельні обчислення можливо буде виконувати не тільки на суперкомп’ютерах, але й на персональних комп’ютерах в мережі ЕОМ.
У другому розділі "Формальне представлення теорії паралельних обчислень" вивчаються та формалізуються процеси розпаралелювання в СПОІ, які мають специфічний характер згідно властивостей досліджуваного класу систем.
Конкретний приклад застосування даної методики наведений у розділі 4 дисертаційної роботи на прикладі створення СПОІ на основі ПАРКС-JAVA системи паралельного програмування.
Однією з основних проблем сучасного програмування є така задача:
Розглядаються “складні” обчислювальні пристрої U, складені з декількох своїх обчислювальних підпристроїв, не обов'язково з рівними за потужністю характеристиками. Для кожної програми P і обчислювального пристрою U написати алгоритм, який під час виконання програми P обчислювальним пристроєм U так розподіляє виникаючі завдання між його підпристроями, щоб кількість тактів виконання цієї програми була найменшою.
В підрозділі 2.1. надається формальне представлення програми –термінальна програма (ТП). Ця формалізація має ще одну перевагу: в ній явно виписуються всі функціональні символи; при оцінці складності з фіксованою семантикою цих символів функціям, які їм відповідають, можуть бути явно приписані їх коефіцієнти “складності”.
Синтаксис визначається таким чином. Спочатку фіксується алфавіт A; він у нашому випадку завжди складається з множини символів, типізованих таким чином: f0, f1, ... – функціональні символи, p0, p1, ... – предикатні символи, символи S, C, *, які ми будемо називати символами відповідно операції суперпозиції, операції (умовного) розгалуження і операції (умовного) циклування, а також з допоміжних символів: ( – лівою дужки, ) –правої дужки і , – звичайної коми. Взагалі кажучи, ми не вважаємо сукупності функціональних і предикатних символів не більше ніж зліченими; проте, для наочності ми, як правило, будемо при позначенні цих символів використати тільки натуральні числа.
Поняття терму (ТП-терму) в алфавіті A визначимо за індукцією:
1) кожен функціональний символ fi є терм;
2) якщо t, t1, ... , tn - терми, то слово S (t, t1, ..., tn) – терм;
3) якщо t0 і t1 – терми і pi – предикатний символ, то C(pi, t0, t1) – терм;
4) якщо t0 – терм і pi – предикатний символ, то *(pi, t0) – терм;
5) слово у алфавіті A є термом тоді і тільки тоді, коли воно може бути побудовано за допомогою правил 1– 4 і тільки їх.
Фактично, терм – це синтаксична формалізація поняття "мета- програми": фіксуючи значення символів S, C і *, як деякі спеціальні функціонали і фіксуючи значення символів, що входять у запис терму, таким чином поставимо у відповідність функціональним символам операції, предикатним символам – предикати і, нарешті, символам відношення порядку – відношення повного порядку, ми зможемо одержувати конкретні приклади програм. Значення всіх цих символів створюють семантику терму, що розглядається.
Зафіксуємо деяку множину M. Задати інтерпретацію функціонального символу fi на множині M – це означає поставити у відповідність йому деяку, можливо, часткову операцію Fi довільної арності на множині M. Аналогічно, під інтерпретацією предикатного символу pi на множині M будемо розуміти будь-який, можливо, частковий предикат Pi довільної арності, заданий на M. Якщо t0 – терм у деякому алфавіті A і {f , ..., f , p, ..., p} – множина всіх функціональних і предикатних символів терму t0, а також його символів відношення порядку, то інтерпретацією терму t у множині M називається будь-яке відображення , в якому кожному функціональному символу f , 1 j m і предикатному символу p, 1 k n відповідають їх деякі інтерпретації F і P у M.
Кожному ТП-терму буде поставлена у відповідність функція, арність якої істотно вважати арністю терму (при фіксованій інтерпретації).
Для кожною терму t0 індукцією по його побудові визначимо, що таке значення терму t0 при його деякій фіксованій інтерпретації . Нехай t0 – терм у алфавіті A і його інтерпретація у деякій множині M. Тоді:
1) якщо терм t0 має найпростіший вигляд, тт. fi, де fi – функціональний символ, то значення терму t0 при інтерпретації визначається, як Fi, де Fi – значення функціонального символу fi при інтерпретації ;
2) якщо терм t0 має вигляд S(t, t1, ..., tn), причому терми t, t1, ..., tn мають значення при інтерпретації , рівні T, T1, ..., Tn відповідно, і якщо, крім того, арність операції T дорівнює n, то значенням терму t0 при інтерпретації називається функція, яка на кожному елементі m множини M приймає значення, рівне T (T1 (m), ..., Tn (m)), а якщо арність операції T відмінна від n, то значенням цього терму вважаємо невизначеним;
3) якщо терм t0 має вигляд С(pi, t1, t2), де pi – предикатний символ з значенням при інтерпретації , рівним Pi, а терми t1 і t2 мають значення при інтерпретації , рівні T1 і T2 відповідно, то значенням терму t0 при інтерпретації називається функція T0, яка на кожному елементі m множини M приймає значення, рівне:
T1(m), якщо елемент m задовольняє частковому предикату Pi;
T0 (m) = T2 (m), якщо m не задовольняє предикату Pi;
невизначеності, якщо значення предиката Pi на m невизначено;
4) якщо терм t0 має вигляд *(pi, t1), де pi – предикатний символ, а t1 - терм з значеннями при інтерпретації , рівними Pi і T1 відповідно, то значенням терму t0 при інтерпретації називається функція T0, яка для кожного елементу m множини M визначається таким чином: якщо у послідовності m, Т1(m), T1 (T1 (m)), ..., T1(..., (T1(m)), ... ), ... елемент T1(..., (T1(m)), ... ) – є перший її такий елемент, що на ньому предикат Pі приймає значення істина, то вважаємо T0(m) рівним значенням цього елементу, якщо ж такого елементу T1(..., (T1(m)), ... ) немає, то значення T0(m) вважаємо невизначеним.
Кожен терм, що розглядається разом з деякою його фіксованою інтерпретацією, виступає у якості моделі поняття термінальної програми. Моделлю називається упорядкована трійка <M, Op, Pr >, де M – деяка множина, Op і Pr – сукупності заданих над нею частковими операціями і частковими предикатами відповідно; множину M ми будемо також називати носієм моделі. Зрозуміло, що якщо розглядається алфавіт символів A і якщо з кожним функціональним і предикатними символами цього алфавіту зв'язати відповідно часткову операцію з Op і частковий предикат з Pr моделі <M,Op,Pr>, то для кожного терму з алфавіту A можна природнім чином однозначно визначити його інтерпретацію. При цьому остання називається інтерпретацією терму у моделі; значення терму при інтерпретації, яка задається деякою фіксованою моделлю, ми будемо називати значенням терму у моделі.
Теорема 2.1. В синтаксичному дереві, яке відповідає довільному ТП-терму будь-яка вершина, яка не є листком, по-перше, помічена одним з символів S, C,* і по-друге має хоча б одну послідовність син-листок.
В підрозділі 2.2. показаний взаємозв'язок ТП-формалізації і теорії частково рекурсивних функцій, при цьому операторові суперпозиції відповідає він сам, операторові мінімізації відповідає оператор циклування і оператор примітивної рекурсії буде виражається через суперпозицію, розгалуження і циклування.
Теорема 2.2. (Відповідності) Нехай множина функціональних символів, що містить елементарні операції 0, S, (n, m N) і множина предикатних символів, що містить символи pf , pf,0, де f, причому їх інтерпретації Pf та Pf,0 відповідно задані:
Pf(х1, ..., хn, y)=TRUE F(х1, ..., хn)= y,
Pf,0(х1, ..., хn)=TRUE F(х1, ..., хn)= 0;
То сукупність операцій на N, які можливо задати за допомогою ТП- формалізації співпадає, з точністю до фіктивних змінних, з сукупністю частково рекурсивних функцій.
Підрозділ 2.3. присвячений побудова формальної моделі паралельних обчислювальних середовищ.
Під функцією складності будемо розуміти будь-яку функцію s:{1, ..., n}(FP)N, якщо n=+, то ця функція s має вигляд N(FP)N. Цю функцію можна розуміти як таку, яка кожному функціональному символу fi (предикатному символу pi) і "найпростішому" обчислювачу з номером n ставить у відповідність час, який займе обчислення кожного значення часткова операція Fi (часткового предиката Pi), де Fi – це інтерпретація символу fi (Pi – це інтерпретація символу pi) у моделі, що розглядається.
Упорядковану четвірку <A, M, n, s>, де A – алфавіт, M – модель, що інтерпретує символи алфавіту A, n – елемент множини (N\{0}){}, s – це функція складності, ми будемо називати обчислювальним середовищем.
Під позначеним деревом ми будемо розуміти упорядковану пару вигляду , де - "звичайне" дерево (з фіксованим коренем), а - будь-яка функція, визначена на вершинах дерева. Елементи множини значень ми будемо називати мітками позначеного дерева . Якщо - дерево, то для будь-якої множини {a} під {a} будемо розуміти (єдине) дерево, ізоморфне відносно взаємно однозначного відображення, яке кожній вершині v дерева відносить пару .
Поставимо у відповідність кожному обчислювальному середовищу, кожному терму в ньому і кожному вхідному значенню спеціальне позначене дерево, яке при цих вхідних значеннях вказує, коли і скільки раз повинні обчислюватись інтерпретації входжень функціональних і предикатних символів у терм, що розглядається.
Індукцією за довжиною терму t0 будуємо спеціальне позначене дерево , мітками якого є пари-елементи множини (FP Terms(S))N, де Terms(S) позначає множину всіх термів у обчислювальному середовищі S.
Збудоване позначене дерево ми будемо називати деревом обчислення терму t0 у обчислювальному середовищі S при інтерпретації, що визначається послідовністю .
Конфігураційною функцією обчислювального середовища <A, M, n, s> ми будемо називати будь-яку часткову функцію k, яка діє з множині {1, ..., n} у множину (FP ({#})N і таку, що для будь-якого m 1 n, k (m) = <x, 0> тоді і тільки тоді, коли x =# . Поняття конфігурації ми будемо ототожнювати з поняттям конфігураційної функції. Змістовно, кожна конфігураційна функція k показує, який "найпростіший" обчислювач, яку операцію або предикат, що відповідає функціональному символу з алфавіту A, виконує у деякий момент часу; якщо Fi – операція, відповідна функціональному символу fi, і k(mi)=< fi, ti>, де ti означає час, який необхідно витратити mi "найпростішому" обчислювачу, щоб завершити виконання операції Fi (аналогічно для предикатів). При цьому, якщо ti= 0, означає, що у цей деякий момент часу жодний з "найпростіших" обчислювачів не виконує ніяку з операцій Fi і предикатів Pj.
Підрозділ 2.4. присвячений побудові Алгоритму розпаралелювання обчислення терму та дослідженню його властивостей.
Нехай S= <A, M, n, s> – обчислювальне середовище, t0 – терм у алфавіті A і – вхідні дані для цього терму і T= відповідне дерево обчислення терму t0. Вагою W(V) кожної гілки V такого дерева T будемо називати число, що визначається по формулі {(W (v) * k(v)) | v (V}, де k(v) – таке число, що <v,k(v)>T, причому якщо v FP, то W(v)=s(v,1).
Нехай S=<A, M, n, s> – монотонне обчислювальне середовище, обчислювачі якого розташовані за спаданням ефективності їх роботи. Якщо відомо, що для кожного підтерму ti , що має вигляд *(pi, ti), терму t0 відповідний цикл триває не більше ніж li ітерацій, то розглядаємо наступний процес, який ми будемо називати базовим Алгоритмом розпаралелювання обчислення терму (або просто алгоритмом розпаралелювання):
1) будуємо дерево з дерева виконуючи t0 у S шляхом заміни всіх його позначок вигляду <pi, k> (таким чином вершин, що "відповідають" за цикли) на вершини <pi, li>;
2) у дереві обираємо всі його максимальні гілки ( тт. гілки, які не містяться ні у яких інших гілках) і розташовуємо їх у список S1 згідно з їх вагою відносно цього дерева;
3) вважаємо k0 (m) = (#, 0) для кожного m, nN+, m n;
4) якщо послідовність конфігураційних функцій k0, k1, ..., ki вже побудована, T' – піддерево дерева , і "є вільні" обчислювачі, т.ч. існують такі m, що ki(m) = <q,1>, то обчислювач з таким мінімальним числом m "завантажуємо", самою нижньою першою гілкою з списку Si, операцією або предикатом, потім віднімаємо від приписаного до неї (до нього) праворуч числа одиницю і заново впорядковуємо список (перетворених) максимальних гілок дерева у цьому дереві або предикаті; перебираємо таким чином всі гілки. Повторюємо так до тих пір, поки не залишиться "вільних" вершин – таким чином ми однозначно визначили k i+1;
5) якщо послідовність k0, k1, ..., ki є обчисленням терму t0, то алгоритм закінчує свою роботу, інакше переходить до пункту 4.
Теорема 2.3. За допомоги базового алгоритму розпаралелювання можливо обчислити терм не більш ніж за О(n2 log n) тактів, де n - кількість вершин у позначеному дереві обчислень.
Гілкою без розгалужень називатимемо послідовність вершин дерева, кожна з яких, крім останньої має одного нащадка, а остання є листком.
Вагою листка називатимемо суму ваг усіх вершин, що розташовані на шляху до нього від кореня, із коренем та листком включно.
Вагою гілки без розгалужень вважатимемо суму ваг її вершин.
Твердження 2.4. Для оптимального обчислення пари гілок дерева без розгалужень за допомогою пари обчислювачів необхідно, щоб вони були завантажені весь час.
Теорема 2.5. Заміна обчислювачів за умов Твердження 2.4. буде необхідна, коли хі=(k2pi-kpi+1)/(k2-1), де k= si./ si+1 – коефіцієнт прискорення обчислень, xі – вага заміни обчислювача і.
Алгоритм (розпаралелювання обчислення терму для пари гілок без розгалужень)
1) Обчислюємо вагу листків і впорядковуємо всі листки за вагою за спаданням.
2) Впорядковуємо всі обчислювачі за потужністю за спаданням (s1 – найпотужніший обчислювач).
3) i-му обчислювачу призначаємо гілку без розгалужень, що відповідає i-му листку. Можливо, залишаться гілки без обчислювачів або обчислювачі без гілок.
4) Розглядаємо сусідні пари обчислювачів: (s1, s2),(s3, s4),… . Нехай (pi, pi+1) – ваги гілок без розгалужень, що відповідають обчислювачам (si, si+1).
Якщо обидві ці гілки містять більше однієї вершини, то виконуємо крок 4а, інакше – 4б.
4а) Обчислюємо xі – вагу заміни обчислювача і – за формулою
хі=(k2pi-kpi+1)/(k2-1), де k=si./si+1 – коефіцієнт прискорення обчислень.
На i-й гілці без розгалужень знаходимо вершину v, таку, що величина |W(v)-xi| є мінімальною, де W(v) – сума ваг вершин, що розташовані на шляху від листка до вершини v.
Обчислювач si обчислюватиме гілку і від листка до вершини v включно. Обчислювач si+1 обчислюватиме гілку і+1 доти, доки обчислювач si працює над гілкою i. Обчислення мають бути організовані так, щоб si+1 завершив роботу над гілкою і+1 не пізніше, ніж si завершить роботу над гілкою і. Тобто, si+1 може деякий час простоювати. Коли si завершить роботу над гілкою без розгалужень і, він переходить до гілки і+1, а si+1 в цей час переходить до гілки і.
4б) Обчислюємо гілки i та i+1 на обчислювачах si та si+1.
5) Коли хоча б 1 обчислювач завершить обробку гілки без розгалужень, переходимо до кроку 1.
Третій розділ роботи “Побудова паралельних обчислювальних систем за технологією ПАРКС” присвячений опису ПАРКС технології.
У підрозділі 3.1. Керуючий простір розглядається, як модель асинхронних обчислень, яку можна розглянути, як мережу алгоритмічних модулів певної природи, в якій уточнені закони взаємодії між модулями та їх структурне розміщення.
Базисний алгоритмічний модуль – це послідовний скінчений дискретний перетворювач (можливо недетермінований), що має керуючу та інформаційну частини, а також засоби взаємодії та синхронізації з іншими модулями.
Керуючий простір - це множина точок , що задані разом зі своєю пів-групою переходів , Вважаємо, що в виділена система базисних переходів - що утворюють пів-групи . Перехід із точки в точку простора здійснюється тільки за допомогою базисних переходів. Пів-група називається пів-групою координат. В кожний момент часу в точках керуючого простору виконуються деякі алгоритмічні модулі, базисні чи складені. Таким чином в кожний момент часу процес, який характеризується функцією, що відображає в множину поточних станів обчислень в точках. Модулі можуть мати імена і, таким чином, здійснювати обмін даними по командам вводу-виводу незалежно від їх розташування в точках простору. При цьому, якщо модулі можуть динамічно породжуватися та передаватися одночасно в декілька точок простору, то для одночасної локалізації процесів при вводі-виводі необхідно використовувати координати точок. Окрім обмінів подібного типу, вважаємо, що повинні бути передачі інформаційного середовища та керування з точки в точку керуючого простору , тобто обчислення, локалізоване в точці , може передаватися в іншу точку , де . Таким чином, алгоритмічні модулі можуть змінювати своє місцезнаходження в керуючому просторі. При одночасній передачі декількох обчислень або середовищ в одну й ту ж точку керуючого простору здійснюється вибір інформації по закону, що залежить від конкретної реалізації.
Підрозділ 3.2. присвячений розгляду композиції алгоритмічних модулів та операції взаємодії їх з керуючим простором. Поняття базисного алгоритмічного модуля уточнювати не будемо, так як воно залежить від орієнтації на конкретну реалізацію. Необхідно пам’ятати, що базисний алгоритмічний модуль – це послідовний (можливо недетермінований) алгоритм, в якому виділено керування та оброблюване середовище. Крім того, в керуючій частині допускаються команди вводу-виводу, що розглядалися вище. Шляхом певних композицій з базисних алгоритмічних модулів можна побудувати більш складні складені алгоритмічні модулі.
Підрозділ 3.3. вказані особливості ПАРКС-технології. Система програмування ПАРКС, як і система паралельного програмування на трансп’ютерах – це сукупність програмних засобів, що підтримують процес розробки і реалізації алгоритмів паралельної обробки інформації за рахунок розширення базових алгоритмічних мов (JAVA, С, Pascal, Fortran, Modula-2). Відмінність системи програмування ПАРКС полягає в тому, що пропоновані нею програмні засоби сполучать найбільш могутні алгоритмічні концепції - рекурсію і паралельність і призначені для опису взаємодій зі змінною комутацією зв'язків і рекурсивно-паралельного розвитку процесів, ядра яких описуються на основі конструкцій базової мови. Акцент робиться на програмні засоби опису динамічного паралелізму.
Основними термінами ПАРКС-технології програмування є:
керуючий простір (КП);
точка;
програмний канал (ПК);
алгоритмічний модуль (АМ).
ПАРКС-технологія програмування базується на концепції керуючого простору Рис.3.1. КП — динамічний граф, за допомогою якого описується логічна й комунікаційна структура досліджуваної задачі (системи) і відображаються динамічні зміни в ній. Завдяки КП ПАРКС - технологія дозволяє:
підтримувати структурне паралельне програмування на основі як статичного, так і динамічного паралелізму;
використовувати розвинуті засоби опису рекурсії за даними і рекурсії по керуванню, розглядати, у залежності від ситуації, керування як дані, а дані - як керування (з урахуванням можливої ефективної реалізації), забезпечувати за допомогою взаємодій не тільки синхронізацію й комунікацію, але і видозміну керування (на основі засобів базової мови);
на логічному рівні в явному вигляді описувати розподіл ресурсів, схеми комутації і перекомутації зв'язків (з урахуванням рекурсивного розгортання алгоритмів) чи одержувати логічну структуру системи, розподіл ресурсів і схему перекомутації неявно, як результат обробки й побудови КП;
будувати систему віртуальних ПАРКС-машин, що забезпечують можливість паралельної обробки інформації на різних рівнях деталізації; ефективна реалізація отриманої системи віртуальних ПАРКС-машин можлива на широкому класі паралельних і спеціалізованих ЕОМ.
Підрозділ 3.5. розглядається ПАРКС-система програмування – сукупність програмних засобів, що забезпечують процес розробки і реалізації алгоритмів паралельної обробки інформації. Ця система може використовуватися при створенні програмного забезпечення паралельних ЕОМ, а також логічної структури паралельних і спеціалізованих ЕОМ, що забезпечують найбільш ефективну реалізацію розробленого програмного забезпечення. Подібні розробки здійснюються користувачами в звичному для них програмному середовищу, природнім чином розширеним досить ємним і простим набором відповідних ПАРКС-засобів.
ПАРКС-система програмування пропонує набір програмних засобів розширення базових алгоритмічних мов (JAVA, С, Modula-2, Pascal, Fortran і т.п..) і підтримку одержуваного мовного середовища, названої відповідно ПАРКС-JAVA, ПАРКС-С, ПАРКС- Pascal і т.п.
Таким чином, програма на деякій умовній мові алгоритмічних модулів складається з наступних частин.
Опис структури чи типу керуючого простору.
Програма настройки керуючого простору. (При виконанні цієї програми відбувається розподілення алгоритмічних модулів по точкам простору.)
Опис локальних алгоритмічних модулів та опис функціонування всього керуючого простору.
Підрозділ 3.6. Описує програмні засоби розширення базових алгоритмічних мов. Алгоритмічні моделі, розроблені засобами ПАРКС-системи програмування, будемо називати ПАРКС-моделями. Розробка ПАРКС-моделей здійснюється на базі ієрархічної структури віртуальних ПАРКС-машин. Розглянемо програмні засоби й можливості, надані кожною віртуальною ПАРКС-машиною для розширення базової алгоритмічної мови:
Рівень 1. Програмні засоби, що забезпечують побудову й модифікацію КП.
Рівень2. Програмні засоби, що забезпечують збереження й передачу інформації за допомогою КП.
Рівень3. Програмні засоби, що забезпечують роботу з алгоритмічними модулями.
Рівень4. Програмні засоби, що забезпечують процедурно та об’єктно-орієнтоване паралельне програмування.
Вибирається програмна конструкція базової мови. Обрана конструкція розглядається як опис AM. Розходження між пакетами й задачами визначається на рівні КП при приписці активних копій AM у точки різних типів (монітори їх задають відповідно правилу обробки звертань до пакетів і задач). Уніфікований виклик процедур і точок входів транслюється на рівень 3, де розписується за допомогою програмних засобів, що забезпечують взаємодію активних копій AM. На наступних рівнях розробляються програмні засоби, використання яких забезпечує автоматичну генерацію паралельних програм по їхніх специфікаціях.
Четвертий розділ роботи "Реалізація системи ПАРКС засобами мови програмування JAVА" присвячений розробці архітектури ПАРКС для комп'ютерних мереж. Надається обґрунтування вибору мови програмування JAVA. Описуються основні класи мови ПАРКС-JAVA. Особливу увагу приділено процесу тестування продуктивності комп’ютерів в системі.
Система ПАРКС-JAVA реалізується на основі локальної чи глобальної комп'ютерної мережі обробки інформації, надаючи можливість користувачам малопотужних комп’ютерів використовувати ресурси мультипроцесорних комплексів, або ресурси комп’ютерної мережі. В обох випадках програмне забезпечення підтримує процеси взаємодії різних вузлів мережі між собою на основі обміну повідомленнями по мережі.
Розглянемо модулі системи ПАРКС-JAVA, які зображені на рис.4.1.
Бібліотека parcs містить класи та методи, що використовуються всіма компонентами системи, в тому числі і алгоритмічними модулями;
Програма Daemon запускається в фоновому режимі на машинах, які підключаються до обчислювальної мережі. Вона виконує запуск алгоритмічних модулів обчислювальних задач, а також тестування продуктивності машин.
Сервер хостів HostsServer є централізованою службою для управління та обліку задач та точок. Сервер зберігає інформацію про підключені машини, продуктивність та кількість точок на кожному хосту, і згідно цієї інформації виділяє машини для створення нових точок, а також відмічає видалення точок, початок та завершення задач.
Обчислювальна задача, що поставляється у вигляді одного чи декількох jar-файлів, або окремих класів алгоритмічних модулів. На обчислення запускається початковий алгоритмічний модуль задачі. В процесі виконання початкового АМ він завантажує з фізичного диску програмний код інших алгоритмічних модулів.
RMI-сервер ParcsLauncher використовується для віддаленого запуску програми на виконання. RMI-клієнт для запуску програми повинен передати код обчислювальної задачі, запакований в jar-архів, та може вказати чи потрібно чекати кінець обчислення перш, ніж повернути управління клієнту.
На всіх машинах, що призначені для обчислення, запускається по одному екземпляру програми Daemon, а початковий АМ та HostsServer можуть запускатися або на тих же, або на інших машинах. В окремому випадку навіть всі три елементи системи можуть бути запущені в одному місці. Файл server використовується початковим АМ для знаходження машини, на якій запущений HostsServer. В єдиному його рядку знаходиться ім’я або IP-адреса цього хосту. В файлі даних (одному або декількох) знаходяться вихідні дані для виконання обчислень, результати записуються в файл результату. При створенні нової точки алгоритмічні модулі звертаються до сервера хостів, щоб отримати адресу машини (найменш завантаженої) для запуску нового АМ. Список доступних машин зберігається в файлі hosts.list.
Рис.4.1 Функціональна схема системи ПАРКС-JAVA
Перспективним напрямком розвитку системи ПАРКС-JAVA, яка не залежить від платформи, є можливість створення серверу у мережі Інтернет, що буде роздавати обчислювальні підзадачі машинам, власники яких бажають прийняти участь в обчислювальних проектах, і при цьому такий сервер зможе працювати з будь-якими клієнтами, незалежно від архітектури їх машин, необхідна тільки підтримка клієнтом JAVA, яка сьогодні знаходить все ширшу підтримку в операційних системах.
В п’ятому розділі роботи "Застосування системи ПАРКС-JAVA для вирішення задач паралельного програмування" розглядаються можливості побудови засобами мови ПАРКС-JAVA різних моделей КП: “ДЕРЕВО”, “КІЛЬЦЕ”,“КУБ ”. На прикладі класичної задачі множення матриць великої розмірності моделюється КП та досліджується динаміка залежності між часом розв’язання задачі та кількістю процесорів від 1-8 (рис.5.4).
Ефективність роботи паралельної обчислювальної системи ПАРКС-JAVA залежить не тільки від її конкретної структури, а й від того, як реалізується її виконання на конкретній обчислювальній системі, і від багатьох зовнішніх факторів.
Рис. 5.4 Графік залежності часу обчислень від розмірності матриць для різної кількості комп’ютерів в локальній мережі від 1-8 та реалізації на різних мовах.
Система ПАРКС-JAVA дає певний механізм для написання паралельних програм. Користувачу потрібно тільки, застосовуючи методи системи, описувати предметне середовище. Цікавим є той факт, що всі класи які були створені при реалізації попередніх паралельних алгоритмів можна використовувати при формуванні наступних паралельних програм. Таким чином формується база класів АМ.
У додатку А надається програма, написана на мові JAVA, що реалізує базові класи системи ПАРКС-JAVA. У додатку Б на мові ПАРКС-JAVA запрограмовані АМ для побудови КП задачі множення матриць великої розмірності та класичне вирішення цієї задачі на мові JAVA та С.
ВИСНОВКИ
Головним результатом дисертації є проведене математичне дослідження спеціалізованого класу розподілених обчислювальних систем – систем паралельної обробки інформації, що дає змогу розв’язувати важливі обчислювальні задачі і має істотне значення для розробки нових компьютерно-комунікаційних систем та сервісів.
В процесі створення системи паралельної обробки інформації ПАРКС-JAVA були вирішені наступні задачі:
можливість підтримки великих за обчисленням задач, що потребують застосування потужних обчислювальних систем та паралельної обробки інформації;
можливість контролю та управління інформаційними потоками в системах паралельної обробки інформації;
можливість накопичення бази даних алгоритмів (алгоритмічних модулів) паралельного програмування для їх подальшого застосування.
В результаті проведеного дослідження було отримано такі результати:
Розроблено прикладну формальну модель – ТП для моделювання паралельних програм та досліджено її властивості.
Створено ефективні алгоритми керування паралельними обчислювальними процесами. Математично досліджені оцінки часової складності розроблених алгоритмів.
Запропоновано практичне застосування технології ПАРКС для паралельної обробки інформації на комп'ютерних мережах та кластерах. Розроблено архітектуру ПАРКС для комп'ютерних мереж.
Розроблено розширення базової мови програмування JAVA засобами для реалізації паралельних обчислень. Створено програмний продукт ПАРКС-JAVA, що може виконувати реальні обчислювальні задачі на комп'ютерних мереж, дозволяє будувати динамічну чи статичну структуру керуючого простору та різні його конфігурації.
Експериментально обґрунтована ефективність алгоритмів для побудови різних моделей керуючого простору та відповідних паралельних програм на мові ПАРКС-JAVA.
ОСНОВНІ РЕЗУЛЬТАТИ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ПРАЦЯХ:
Анисимов А.В., Деревянченко А.В. Система ПАРУС-JAVA для параллельных вычислений на компьютерных сетях // Кибернетика и системный анализ. - 2005. - №1.- С.25-36.
Дерев'янченко О.В. Моделювання паралельних програм за допомогою системи ПАРКС-JAVA // Наукові записки НаУКМА, Комп'ютерні науки. - 2005р.- С.47-58.
Деревянченко А.В., Лялецкий А.А. О проблеме распараллеливания вычислений // Математические машины и системы. - 2004.- №2.-С.3-14.
Анісімов А.В., Дерев'янченко О.В.
