Методи та засоби створення автоматизованої системи проектування паралельних алгоритмів

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

Київський національний університет імені Тараса Шевченка

УДК 004.4'242; 004.435

Методи та засоби створення автоматизованої системи проектування паралельних алгоритмів

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

машин і систем

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

кандидата технічних наук

ШКУЛІПА Ігор Юрійович

Київ 2011

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

Робота виконана на кафедрі комп'ютерної інженерії Київського національного університету імені Тараса Шевченка.

Науковий керівник: доктор технічних наук, професор Погорілий Сергій Дем'янович Київський національний університет імені Тараса Шевченка, професор кафедри комп'ютерної інженерії

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

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

Захист відбудеться «16» червня 2011 р., о «14» годині на засіданні спеціалізованої вченої ради Д 26.001.09 при Київському національному університеті імені Тараса Шевченка за адресою: 01601, Київ, проспект Академіка Глушкова, 4-д, ауд. 40.

З дисертацією можна ознайомитися в науковій бібліотеці Київського національного університету імені Тараса Шевченка за адресою: 01033, Київ, вул. Володимирська, 58

Автореферат розісланий «__» травня 2011 р.

Вчений секретар

спеціалізованої вченої ради

В.П.ШЕВЧЕНКО

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

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

Значний внесок у дослідження методів та засобів проектування паралельних алгоритмів проведено та проводиться у роботах під керівництвом Глушкова В.М., Редька В.Н., Летичевського О.А., Воєводіна В.В., Анісімова А.В., Ющенко К.Л., Перевозчикової О.Л., Цейтліна Г.О., Погорілого С.Д., Глибовця М.М., Дорошенка А.Ю., Фельдмана Л.П., Башкова Є.О., Святного В.А., Халімова А.І. та ін.

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

Алгоритмічний етап проектування паралельних застосувань є початковим та найменш технологічно забезпеченим. Однак, він впливає на весь подальший процес розробки та визначає її успіх в цілому. Інструментарії цього етапу проектування мають забезпечувати ефективні засоби опису алгоритмів функціонування систем паралельної обробки даних із врахуванням їх специфіки; можливість формальних еквівалентних перетворень алгоритмів з метою отримання нових більш швидких версій; засоби опису послідовних та паралельних фрагментів алгоритмів; можливість генерації асоційованих із досліджуваними алгоритмами програм для різних підходів паралельного програмування; зручні візуальні засоби проектування алгоритмів; можливість оцінки часових характеристик роботи алгоритмів перед їх використанням на цільових апаратно-програмних платформах.

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

Реалізація викладених вище вимог призвела до розробки інструментарію у вигляді системи автоматизованого параметричного проектування алгоритмів (САПП). Її призначення - це перетворення та оптимізація алгоритмів з подальшою генерацією програмного коду, що реалізує відповідний алгоритм цільовою мовою програмування.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась в рамках науково-дослідних робіт:

· „Фізичні основи елементної бази та ефекти взаємодії випромінювання з речовиною для розвитку напівпровідникової технології інформатизації” - держбюджетна тема 06БФ052-02 (2006 - 2010 р.р.), державний реєстраційний номер 0106U006545;

· „ Дослідження можливостей створення обчислювального кластеру на платформі WINDOWS^TM Compute Cluster Server 2003 (CCS) на базі класу персональних комп'ютерів” в рамках договору № 07-008/М укладеним між ТОВ «Майкрософт Україна» та Київським національним університетом імені Тараса Шевченка (2006 - 2007 р.р.);

· „ Локалізація Microsoft Share Point Learning Kit (SLK) та дослідження впливу локалізації на функціональність систем ” в рамках договору № 07-008/М укладеним між ТОВ «Майкрософт Україна» та Київським національним університетом імені Тараса Шевченка (2006 - 2007 р.р.).

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

Поставлена мета визначила наступні завдання дослідження:

1. Аналіз сучасних методів проектування алгоритмів для забезпечення можливості автоматизованого перетворення та створення паралельних версій алгоритмів.

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

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

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

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

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

Предмет дослідження - методи, методики та алгоритми автоматизованого перетворення алгоритмів та компіляції формалізованих схем алгоритмів у програмний код.

Методи досліджень. У роботі використано математичний апарат модифікованих систем алгоритмічних алгебр (САА-М) та еквівалентних перетворень у них як інструмент для створення методу генерації паралельних програм за схемами алгоритмів; математичний апарат кольорових мереж Петрі для моделювання роботи схем паралельних алгоритмів та експериментальні методи оцінки продуктивності програм.

Наукова новизна: алгоритм програма автоматизований критерій

1. Запропоновано новий підхід до автоматизованого перетворення схем алгоритмів на основі їх представлення у вигляді САА-М-схем.

2. Створено прототип автоматизованого генератора програмного коду для забезпечення автоматизованого синтезу асоційованих з алгоритмами програм на основі їх представлення у вигляді САА-М-схем. Новою особливістю цього прототипу є можливість параметричної генерації коду відповідно до різних підходів паралельного програмування та апаратно-програмних платформ.

3. Вперше інтегровано методику формалізованого проектування на основі САА-М-схем алгоритмів з методикою алгоритмічного проектування, яка ґрунтується на застосуванні UML-діаграм.

4. Вперше запропоновано та експериментально обґрунтовано методику редукції САА-М-схем алгоритмів до кольорових мереж Петрі для моделювання роботи алгоритмів та забезпечення можливості оцінки їх часових характеристик без прив'язки до апаратно-програмної платформи.

5. Реалізовано новий метод створення сценаріїв для управління процесом виконання програм, що дозволяє здійснити вибір найкращого алгоритму за заданими критеріями.

Особистий внесок дисертанта в роботах. Особистий внесок автора полягає: в роботах [1] - дослідження та створення паралельної версії алгоритму Прима, створення відповідного програмного забезпечення та моделювання його роботи; [2, 3, 4, 5, 9] - створення організаційної структури системи, створення моделі перетворювача схем алгоритмів, створення моделі компілятора САА-М-схем у програмний код та розробка концепції автоматизованого виконання програмних реалізацій алгоритмів; [6] - розробка методики формування паралельної схеми алгоритму проштовхування «передпотоку»; [7] - створення моделей автоматизованого синтезу САА-М-схем алгоритмів на основі їх подання у вигляді діаграм UML; [8] - розробка методики моделювання роботи схем алгоритмів за допомогою мереж Петрі.

Апробація результатів дисертації. Основні результати наукової роботи представлялися на науковому семінарі, присвяченому 90-річчю з дня народження Ющенко К.Л. (2009 р.), 7-й Міжнародній конференції з програмування УкрПРОГ-2010, п'ятій ювілейній науково-практичній конференції з міжнародною участю «Математичне та імітаційне моделювання систем. МОДС '2010», сьомій міжнародній науково-практичній конференції «Теоретичні та прикладні аспекти побудови програмних систем» - TAAPSD'2010 та на наукових семінарах радіофізичного факультету та факультету кібернетики Київського національного університету імені Тараса Шевченка.

Публікації. Основний зміст роботи викладено у 9 друкованих працях, серед яких 4 статті у фахових виданнях ВАК України, та 4 тези конференцій.

Практичне значення результатів роботи

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

2. За допомогою системи САПП було спроектовано та розпаралелено низку алгоритмів, що входять до діагностичної системи відділення токсикології дитячої клінічної лікарні “ОХМАТДИТ” (м. Київ). Створена методика використовується в науково-дослідній частині Донецького національного технічного університету (м. Донецьк) при проведенні комп'ютерного моделювання на базі обчислювального кластеру Microsoft Compute Cluster Server та на кластерах інформаційно-обчислювального центру Київського національного університету імені Тараса Шевченка (м. Київ).

3. Методика формування схем паралельних алгоритмів за допомогою системи автоматизованого параметричного проектування впроваджена в навчальний процес в рамках курсу «Програмне конструювання», що входить до навчальної програми кафедри комп'ютерної інженерії Київського національного університету імені Тараса Шевченка та курсу «Теорія і методи розподіленої обробки даних у комп'ютерних мережах» у Донецькому національному технічному університеті.

Структура та обсяг роботи.

Дисертація складається зі вступу, чотирьох розділів, висновків, 5-ти додатків та переліку використаної літератури зі 125 посилань. Загальний обсяг дисертації 168 сторінок, з яких 133 сторінки основного тексту, що містить 40 рисунків та 5 таблиць.

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

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

У першому розділі проведено аналіз існуючих підходів до створення паралельних застосувань. Розглянуто підходи паралельного програмування та їх застосування для різних апаратно-програмних платформ, проаналізовано переваги та недоліки кожної з них. Запропоновано підхід до автоматизації етапу алгоритмічного проектування паралельних застосувань на базі формальних методів подання алгоритмів, проведено аналіз існуючих засобів формалізованого подання алгоритмів та обґрунтовано вибір модифікованих систем алгоритмічних алгебр В.М.Глушкова (САА-М), як основи для етапу автоматизованого створення паралельних версій алгоритмів. Також наведено методику подання алгоритмів у вигляді формалізованих САА-М-схем на прикладі алгоритму Прима, що використовується для знаходження мінімального покривного дерева графа.

Обґрунтовано доцільність застосування уніфікованої мови моделювання (UML) для нотації алгоритмів на етапі їх проектування. Запропоновано використання математичного апарату мереж Петрі для моделювання та аналізу роботи паралельних алгоритмів.

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

Першим етапом перетворення схеми алгоритму є автоматизований аналіз схеми. Автоматизований аналізатор схем алгоритмів призначений для попереднього аналізу вхідної САА-М-схеми алгоритму та виводу рекомендацій щодо її перетворення. На вхід аналізатора подається САА-М-схема алгоритму, а на виході отримуються рекомендації щодо її перетворення у форматі:

· частина схеми алгоритму, що може бути перетворена;

· еквівалентне перетворення, що може бути застосоване до схеми;

· модифікована схема алгоритму, що буде отримана після застосування перетворення;

· оціночне прискорення модифікованої схеми у відсотках відносно часу виконання вхідної.

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

Оціночне прискорення обраховується за наступним алгоритмом:

Час роботи схеми обраховується за наступним співвідношенням:

,

де

· N_p - кількість операторів, що виконуються поза циклами;

· t_i - часи виконання операторів, що виконуються поза циклами. Задаються користувачем або за замовчанням дорівнюють 1;

· N_oc - кількість циклів, що присутні у схемі;

· t_{oc j} - часи виконання операторів, що виконуються в циклі;

· N_бj - кількість ітерацій циклів, що задається вручну користувачем або за замовчанням дорівнює 100.

Якщо у схемі присутня паралельна частина, то час її виконання обраховується наступним чином:

,

у випадку, якщо у операторів відсутній зв'язок за даними, та

,

де t_s - час виконання оператора синхронізації, а N_c - кількість операторів у циклі, Тоді відносне прискорення модифікованої схеми алгоритму у порівнянні з вхідною буде дорівнювати

,

де T₀ - час виконання вхідної схеми алгоритму, T_m - час роботи модифікованої схеми.

Визначимо перетворювач САА-М-схем алгоритмів, як недетермінований скінченний автомат (НСА), що задається наступним визначенням:

SAATransformer=(Q,E,d,q₀),

де

· Q - скінченна множина станів автомата, являє собою множину схем, що можуть бути отримані шляхом застосування до вхідної всіх еквівалентних перетворень у всіх можливих послідовностях;

· E - множина вхідних символів нотації схем алгоритмів;

· q₀ - початковий стан НСА, визначається вхідною САА-М-схемою алгоритму;

· d - функція переходів, аргументами якої є стан автомата з Q, та вхідна схема алгоритму з Е, а значенням - деяка підмножина з множини Q. Функція переходів схематично зображена у вигляді діаграми на рис.1.

Рис. 1 Функція переходів SAATransformer

Рис. 1 ілюструє обробку вхідних даних автоматом. На вході маємо схему алгоритму та набір еквівалентних перетворень. Очевидно, що деякі з перетворень не можуть бути застосовані до вхідної схеми, тому зі стану q₀ автомат може перейти або у стан q₀, що являє собою власне вхідну схему алгоритму, або у стан q₁₁, що матиме на виході нову схему алгоритму, яку отримано шляхом застосування до вхідної відповідного еквівалентного перетворення. Далі зі станів q₀ і q₁₁ автомат може перейти у стани, що відповідають застосуванню наступних за списком еквівалентних перетворень цей процес відбуватиметься до ти пір, доки не будуть застосовані всі можливі перетворення і не буде отримано низку відповідних САА-М-схем алгоритмів. Групи станів q₁₁ - q_m1 відповідають застосуванню до вхідної схеми еквівалентних перетворень, група станів q₁₂ - q_m2 відповідає застосуванню наступного за списком еквівалентного перетворення до групи станів q₁₁ - q_m1.

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

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

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

Запропоновано модель генератора програмного коду. В свою чергу генератор коду представляє собою НСА, на вхід якого подається САА-М-схема алгоритму з додатковими конкретизаціями використовуваних умов та операторів, а на виході отримується програма вибраною цільовою мовою програмування із застосуванням вибраного підходу паралельного програмування.

CodeGenerator=(Q,E,d,q₀),

де E, q₀ та d аналогічно позначенням у співвідношенні для SAATransformer, а Q - скінченна множина припустимих станів автомата, що в загальному випадку представляє собою множину коректних програм. Функція переходів схематично зображена у вигляді діаграми на рис. 2.

Рис. 2 Функція переходів CodeGenerator

Кінцеві стани НСА генератора коду відповідають згенерованим програмам мовою С з застосуванням підходів паралельних процесів, паралельних потоків та МРІ, та мовою Java з застосуванням паралельних потоків Java.

Наведено приклад роботи НСА генератора коду на основі алгоритму Прима.

Наведено алгоритм роботи генератора програмного коду. Розглянуто деякі особливості реалізації лексичного аналізу та побудови дерева розбору САА-М-схеми. Запропоновано підхід до автоматизованого виконання програм на основі сценаріїв виконання.

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

Розроблено та експериментально обґрунтовано підхід до інтеграції процесу проектування алгоритмів на основі UML-діаграм та автоматизованого синтезу САА-М-схем, що дозволяє інтегрувати процес проектування САА-М-схеми алгоритму із сучасним засобом алгоритмічного проектування - UML-діаграмами. Описано процес проектування діаграми алгоритму для забезпечення можливості подальшого автоматизованого синтезу САА-М-схеми. Запропоновано алгоритм автоматизованого перетворення UML-діаграми в САА-М-схему, який полягає у покроковому обході діаграми алгоритму та синтезі відповідних конструкцій САА-М на кожному кроці.

1. Починається обхід всіх елементів UML по переходах, починаючи з початкового.

2. Визначається тип поточного елементу.

· Якщо цей елемент - розділення, що не знаходиться в тілі циклу while, то це умовний оператор, тобто б-диз'юнкція. Визначаються умови переходів й виконується п. 2 для обох гілок.

· Якщо елемент - розділення, що знаходиться в циклі while, й зворотнім переходом в цей цикл є перехід із розділення, то фіксується кінець циклу while, визначається умова закінчення циклу.

· Якщо елемент - об'єднання, що не знаходиться всередині умовного оператора, то це є цикл while, тобто б -ітерація. Обхід продовжується вздовж вихідної гілки, доки не буде досягнуто розділення із зворотним переходом в поточне об'єднання.

· Якщо елемент - об'єднання, що знаходимося в середині умовного оператора, фіксується його кінець.

· Якщо елемент - стан дії, то до списку операторів додається композиція та п. 2 повторюється для вихідного переходу.

· Якщо елемент - кінцевий стан, обхід зупиняється.

3. Формується рядок, що відповідає САА-М-схемі алгоритму.

Роботу підсистеми генерації САА-схем на основі UML-діаграм продемонстровано на прикладі алгоритму Прима. В якості прикладу взято послідовну версію алгоритму Прима та введено відповідні позначення для умов і операторів.

Описано методику моделювання САА-М-схем на основі мереж Петрі, що полягає у автоматизованому синтезі кольорових мереж Петрі на основі САА-М-схем алгоритмів та подальшому моделюванні їх роботи за допомогою пакету CPN Tools. Запропоновано алгоритм автоматизованого синтезу мереж Петрі на основі САА-М-схем, який складається з наступних кроків:

1. Прочитати вхідний файл опису САА-М-схеми, виділити код САА-М-схеми.

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

3. Створити, за допомогою описаної вище процедури головний модуль мережі Петрі. Записати вказівник на цей модуль у кореневий елемент модульного дерева.

4. Викликати процедуру формування модуля для головного модуля мережі Петрі.

5. Процедура формування модуля завершена. Всі модулі мережі Петрі та список моніторів сформовані. До списку декларацій додати декларацію булевих змінних.

6. Відкрити вихідний файл, записати вступну частину.

7. Послідовно зчитуючи список декларацій, записати в вихідний файл розділ декларацій.

8. Послідовно зчитуючи список моніторів, записати в вихідний файл розділ моніторів.

9. Записати вступну частину розділу модулів. У порядку префіксного обходу модульного дерева записати в розділ модулів опис модулів мережі Петрі. Порядок описів у підрозділах модуля відповідає порядку елементів у відповідних списках модуля. Записати завершальну частину розділу модулів.

10. Записати завершальну частину вихідного файлу. Закрити вхідний та вихідний файли. Алгоритм завершено.

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

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

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

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

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

Етап 2. Синтез вхідної САА-М-схеми алгоритму. На цьому етапі з діаграми діяльності алгоритму автоматично формується САА-М-схема алгоритму.

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

Етап 4. Синтез та моделювання мереж Петрі. На цьому етапі відбувається автоматизований синтез та моделювання роботи мереж Петрі, що моделюють роботу заданого алгоритму, відповідно до методики, викладеної у підрозділі 3.2 дисертації. На основі моделювання, вибирається найкраща за часовими характеристиками САА-М-схема алгоритму.

Етап 5. Генерація програм. Після отримання низки САА-М-схем алгоритму, необхідно вибрати цільові мови програмування та підходи паралельного програмування, для подальшої генерації програм, що реалізують заданий алгоритм.

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

Детально технологічний ланцюжок роботи з системою зображено на рис. 4.

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

Рис. 3 Організаційна структура САПП

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

Рис. 4 Технологічний ланцюжок роботи з САПП

Експериментальна реалізація САПП виконана на платформі Microsoft.Net Framework мовою програмування C#. Як система керування базами даних використовується Microsoft Office Access 2007. Платформа Microsoft.Net має вбудовані потужні засоби для обробки регулярних виразів, засоби для побудови дерев та роботи з базами даних.

Тестування САПП та її експериментальні випробування проводяться на кластерах Київського національного університету імені Тараса Шевченка під управлінням платформ Windows та Linux.

В якості середовища для моделювання мереж Петрі використовується CPN Tools.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ

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

Це включає в себе такі результати:

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

2. Розроблено і досліджено модель автоматизованого перетворювача алгоритмів на основі їх представлення у вигляді САА-М-схем для подальшого перетворення схем алгоритмів та формування їх паралельних версій. В основу моделі покладено механізм перетворення схем з використанням апарату регулярних виразів.

3. Запропоновано і вивчено властивості моделі генератора програмного коду на основі представлення алгоритмів у вигляді САА-М-схем, із забезпеченням двох рівнів параметризації: за цільовою мовою програмування та за підходом паралельного програмування. Наявність таких рівнів параметризації суттєво спрощує міграцію застосувань на різні апаратно-програмні платформи.

4. Створено та реалізовано методику синтезу САА-М-схем алгоритмів на основі їх представлення у вигляді UML-діаграм, що дозволяє інтегрувати методику формалізованого подання САА-М-схем паралельних алгоритмів з поширеними засобами алгоритмічного проектування на основі UML-діаграм.

5. Розроблено та експериментально обґрунтовано методику моделювання роботи САА-М-схем паралельних алгоритмів за допомогою математичного апарату кольорових мереж Петрі для забезпечення можливості оцінки часових характеристик їх роботи ще до реалізації на певній програмно-апаратній платформі. Методика передбачає синтез кольорових мереж Петрі на основі САА-М-схем паралельних алгоритмів та подальше моделювання їх роботи за допомогою пакету CPN Tools.

6. Створену САПП впроваджено на інформаційно-обчислювальному центрі Київського національного університету імені Тараса Шевченка, у Донецькому національному технічному університеті та при створенні діагностичної системи у відділенні токсикології дитячої клінічної лікарні «ОХМАТДИТ».

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЙНОЇ РОБОТИ

Статті у наукових фахових виданнях

1. Бойко Ю.В. Дослідження паралельних схем алгоритму Прима / Бойко Ю.В., Погорілий С.Д., Шкуліпа І.Ю.// Математичні машини і системи. 2007. №2. стор. 77-89.

2. Погорелый С.Д. Концепция создания автоматизированной параметрической системы проектирования параллельных алгоритмов и их программных реализаций / Погорелый С.Д., Шкулипа И.Ю. // Кибернетика и системный анализ. 2009. №6. стр. 118-124.

3. Шкуліпа І.Ю. Методика автоматизованої трансформації схем алгоритмів / Шкуліпа І.Ю., Погорілий С.Д. // Проблеми програмування. 2010. № 2-3. спеціальний випуск. Матеріали міжнародної конференції УкрПРОГ 2010. стор. 349-354.

4. Шкулипа И.Ю. Автоматизированный синтез программ на основе САА-М-схем / Шкулипа И.Ю., Погорелый С.Д // Управляющие системы и машины. 2010. №3. Стор. 58-64.

Статті в інших виданнях

5. S.D.Pogorilyy A conception for creating a system of parametric design of parallel algorithms and their software implementations / S.D.Pogorilyy, I.Yu.Shkulipa // Cybernetics and System Analysis. 2009. Vol. 45. No. 6. Р. 952-958.

Тези наукових доповідей

6. I.U. Shkulipa Automated parametric algorithm transformation system / I.U. Shkulipa, O.V. Kuzmin, S.D. Pogorilyy // 9th international young scientists' conference on applied physics. Kyiv. 2009. p. 104.

7. Igor Yu. Shkulipa Automated synthesis of SAA-schemes based on UML-diagrams / Igor Yu. Shkulipa, Anton Yu. Vladyka, Sergey D. Pogoriliy // 10th international young scientists' conference on applied physics. Kyiv. 2010. P. 216-217.

8. Шкуліпа І.Ю. Моделювання роботи САА-М-схем за допомогою мереж Петрі / Шкуліпа І.Ю., Погорілий С.Д., Климко Я.І. // П'ята ювілейна науково-практична конференція з міжнародною участю «Математичне та імітаційне моделювання систем. МОДС '2010». Київ. 2010. стор. 264.

9. Шкуліпа І.Ю. Система автоматизованого параметричного проектування алгоритмів / Шкуліпа І.Ю., Погорілий С.Д. // Сьома міжнародна науково-практична конференція «Теоретичні та прикладні аспекти побудови програмних систем» - TAAPSD'2010. Київ. 2010. стор. 495-501.

АНОТАЦІЯ

Шкуліпа І.Ю. Методи та засоби створення автоматизованої системи проектування паралельних алгоритмів. - Рукопис.

Дисертація на здобуття вченого ступеня кандидата технічних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем - Київський національний університет імені Тараса Шевченка, Київ, 2011.

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

У роботі проведено аналіз існуючих підходів до створення паралельних застосувань. Розглянуто підходи паралельного програмування та їх застосування для різних апаратно-програмних платформ, проаналізовано переваги та недоліки кожної з них. Запропоновано підхід до автоматизації етапу алгоритмічного проектування паралельних застосувань на базі формальних методів подання алгоритмів, проведено аналіз існуючих засобів формалізованого подання алгоритмів та обґрунтовано вибір модифікованих систем алгоритмічних алгебр В.М.Глушкова (САА-М), як основи для етапу автоматизованого створення паралельних версій алгоритмів.

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

Ключові слова: САА-М, формальні методи, алгоритмічні алгебри, UML, мережі Петрі, компілятор, автоматизація, паралельний алгоритм, кластер, паралельне програмування, процес, потік, Java, MPI.

АННОТАЦИЯ

Шкулипа И.Ю. Методы и средства создания автоматизированной системы проектирования параллельных алгоритмов. - Рукопись

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем - Киевский национальный университет имени Тараса Шевченко, Киев, 2011.

Диссертация посвящена разработке методов и средств создания автоматизированной системы проектирования параллельных алгоритмов.

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

Обоснована актуальность темы исследований, сформулированы цель работы и задачи исследования, указаны научная новизна и практическая значимость полученных результатов, а также представлена информация о личном вкладе соискателя, апробация результатов работы, публикации и внедрения.

Предложен подход к автоматизации этапа алгоритмического проектирования параллельных приложений на базе формальных методов представления алгоритмов, проведен анализ существующих средств формализованного представления алгоритмов и обоснован выбор модифицированных систем алгоритмических алгебр В. М. Глушкова (САА-М), как основы для этапа автоматизированного создания параллельных версий алгоритмов. Также приведена методика представления алгоритмов в виде формализованных САА-М-схем на примере алгоритма Прима, который используется для нахождения минимального остовного дерева графа.

Приведена методика автоматизированной трансформации схем алгоритмов и генерации ассоциированных с ними программ.

Описан процесс проектирования диаграммы алгоритма для обеспечения возможности автоматизированного синтеза САА-М-схемы. Предложен алгоритм автоматизированного преобразования UML-диаграммы в САА-М-схему. И приведен пример генерации САА-М-схемы на основе алгоритма Прима.

Описана методика моделирования САА-М-схем на основе сетей Петри. Предложен алгоритм автоматизированного синтеза сетей Петри на основе САА-М-схем.

Проиллюстрирована экспериментальная проверка работы автоматизированной системы преобразования алгоритмов. Описаны особенности реализации предложенных методов.

Сформирована организационная структура системы проектирования программного обеспечения для параллельных систем. Предложена и реализована модель автоматического преобразователя алгоритмов на основе их представление в виде САА-М-схем. Предложена и реализована модель автоматизированного генератора программного кода на основе представления алгоритмов в виде САА-М-схем, с обеспечением параметризации генерации кода по подходам параллельного программирования и аппаратно-программным платформам. Создана методика автоматического синтеза САА-М-схем алгоритмов на основе их представление в виде UML-диаграмм. Предложена методика моделирования работы САА-М-схем алгоритмов с помощью аппарата цветных сетей Петри для обеспечения возможности оценки временных характеристик их работы без привязки к аппаратно-программной платформе.

Ключевые слова: САА-М, формальные методы, алгоритмические алгебры, UML, сети Петри, компилятор, автоматизация, параллельный алгоритм, кластер, параллельное программирование, процесс, поток, Java, MPI.

ABSTRACT

Shkulipa I.Yu. Methods and means of creating an automated system for designing parallel algorithms. - Manuscript.

Ph.D. thesis on technical sciences, specialty 01.05.03 - mathematical and software computer systems - National Taras Shevchenko University of Kyiv, Kyiv, 2011.

The thesis is dedicated to the improvement of methods and means for creating an automated system for designing parallel algorithms.

The paper analyzes the existing approaches to create parallel applications. A paradigm of parallel programming and applications for various hardware and software platforms, and analyzed the advantages and disadvantages of each. An approach to automation of algorithmic design phase of parallel applications based on formal methods of representation algorithms, analysis of existing formal presentation of the choice of algorithms and modified systems of algorithmic algebras Glushkov (SAA-M) as the basis for phase automatic creation of parallel versions of algorithms.

Formed organizational structure design system software for parallel systems, proposed and implemented the model of the converter automatic algorithms based on their representation in the form of SAA-M-circuits. A model and implemented automated code generator based on the representation of algorithms in the form of SAA-M-schemes of parameterization software code generation for parallel programming paradigms and hardware / software platforms. The method of automatic synthesis of SAA-M-schemes of algorithms based on their representation in the form of UML-diagrams. The method of simulation of M-SAA-schemes are offered by the apparatus of colored Petri nets to enable assessment of temporal characteristics of their work without reference to the hardware and software platform.

Keywords: SAA-M, formal methods, algorithmic algebra, UML, Petri net, compiler, automation, parallel algorithm, cluster, parallel programming, process, thread, Java, MPI.

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

...