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

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

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

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

УДК 004.4'242; 004.432.2

АВТОРЕФЕРАТ

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

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

Левченко Роман

Ігорович

Київ - 2011

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

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

Науковий керівник доктор технічних наук, професор
Погорілий Сергій Дем'янович,

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

Офіційні опоненти: доктор фізико-математичних наук, професор
Кривий Сергій Лук'янович,

Київський національний університет імені Тараса Шевченка, професор кафедри інформаційних систем факультету кібернетики кандидат технічних наук, доцент Мухін Вадим Євгеніевич, Національний технічний університет України «КПІ», Міністерство освіти та науки України, доцент кафедри обчислювальної техніки

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

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

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

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

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

Актуальність теми. Сьогодні розвиток науки і техніки пов'язаний з новими складними у математичному плані задачами (ядерної, атомної, молекулярної фізики, хімії, квантової біохімії, генетики, медицини, метеорології тощо). Розв'язання цих задач уповільнюється недостатньою потужністю окремих однопроцесорних комп'ютерних архітектур. Висновки експертів у галузі комп'ютерних технологій збігаються в тому, що ресурс екстенсивного зростання продуктивності мікропроцесорів внаслідок підвищення складності архітектури та тактової частоти мікропроцесорів наразі себе вичерпав. В подальших дослідженнях та розробках акцент перенесено на створення багатоядерних процесорів (свідоцтвом тому є створення таких процесорів фірмами Intel, Oracle та IBM), систем із масовим паралелізмом. Тут однак з'являється інша проблема: для розв'язання відомих складних задач існують гарні послідовні алгоритми, які треба трансформувати для паралельного виконання, це потребує подальшої їх переробки у паралельні аналоги, що висуває коло наукових питань до методів зниження трудомісткості створення паралельних програм. Для систем із спільною пам'яттю ця задача є певною мірою вирішеною й такі системи як OpenMP є яскравим прикладом одного з варіантів розв'язання розглянутої задачі.

Дослідження розробки паралельних програм проводились у роботах: Абрамова С.М., Андріанова О.Н., Анісімова А.В., Воєводіна В.В., Воєводіна Вл.В., Глибовця М.М., Глушкова В.М., Дорошенка А.Ю., Кривого С.Л., Летичевського О.А., Перевозчикової О.Л., Погорілого С.Д., Святного В.А.,Фельдмана Л.П., Алілова А.І., Цейтліна Г.О., Ющенко К.Л., David J. Kuck., Dana Petcu, Lucio Grandinetti та ін.

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

У результаті, при реалізації систем динамічного розпаралелювання обчислень і при балансуванні навантаження використовується застарілий принцип: «чим менше в системі обчислювальних ресурсів, що простоюють, тим ефективніше працює паралельний алгоритм». Це обмежує розмірність ефективних паралельних рішень 20-30 потоками. Таким чином, пошук нових методів та підходів до створення програмних рішень з динамічним розпаралелюванням, на тлі зростаючої продуктивності багатопроцесорних систем та складності створюваних алгоритмів є актуальною задачею. Той факт, що для основних типів суперкомп'ютерних архітектур сьогодні ще не існує ефективного способу написання паралельних реалізацій алгоритмів, підкреслює актуальність розглянутої задачі.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках наступних науково-дослідних робіт: «Розроблення i впровадження GRID інфраструктури та програмних засобів високопродуктивних науково-технічних розрахунків для наукових та освітніх установ України», договір № IT/505-2007 від 22.08.2007 (номер реєстрації в університеті 07ДП-052-09), державний реєстраційний номер 0107U007659 (2007-2008 рр.); «Створення комплексної веб-орієнтованої системи віртуальних лабораторій в GRID-інфраструктурі високопродуктивних обчислень для наукових та освітніх установ України», договір № IТ/559-2009 від 20.07.09 (номер реєстрації в університеті 07ДП-052-06), державний реєстраційний номер 0109U006069 (2009-2010 рр.); «Розробка і впровадження Грід-технологій в моделювання нейросистем», державний реєстраційний номер 0110U005280; «Дослідження умов зведення моделей нейронної динаміки до меншої розмірності. Вивчення біфуркацій та хаосу в одно- та багатовимірних відображеннях, що виникають при зведенні зв'язаних систем Ходжкіна-Хакслі до дискретної динаміки» державний реєстраційний номер 0108U001412; початок 1 кв. 2008 р. - закінчення 4 кв. 2012 р.).

Мета і завдання дослідження.

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

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

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

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

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

4. Створити методику автоматичної побудови паралельного алгоритму на основі його розміченого послідовного аналога.

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

6. Експериментально дослідити ефективність розпаралелювання послідовних алгоритмів за допомогою запропонованого підходу.

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

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

Методи дослідження. При створенні методу автоматичного розпаралелювання графа алгоритму використовувався математичний апарат теорії графів, при формуванні методів динамічного балансування використовувався апарат теорії ймовірностей і математичної статистики. Розробка інтерфейсу системи вимагала використання теорії алгоритмічних мов. Дослідження характеристик розробленої системи виконувалося за допомогою теорії статистичного аналізу.

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

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

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

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

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

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

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

Практичне значення одержаних результатів:

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

1.1.Реалізовано та здійснено інтеграцію об'єднаних алгоритмів активного й пасивного аналізу динамічного графа.

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

1.3. Реалізовано нерозривний та функціонально завершений інтерфейс для стандарту мов програмування ANSI C та C++, з підтримкою Microsoft- та GNU- компіляторів.

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

Особистий внесок дисертанта. Усі положення, що становлять суть дисертаційного дослідження, сформульовані та вирішені автором самостійно. В роботах, які було опубліковано у співавторстві, здобувачеві належать: [1] - аналіз існуючих систем автоматичного та напівавтоматичного розпаралелювання, на основі якого висунуто вимоги до DDCI, сформовано основні характеристики системи, розроблено першу версію планувальника системи, проведене експериментальне тестування; [2] - вирішення задачі підвищення ефективності чистих функцій та розміру блоку у паралельних алгоритмах; [3] - експериментальне дослідження впливу розмірів функцій паралельних алгоритмів на їх ефективність; [4] - вимоги до інтерфейсу системи автоматичного розпаралелювання обчислень, методика перетворення послідовних алгоритмів у паралельні аналоги, вирішення задачі управління динамічним графом програми, класифікація планувальників обчислень; [5] - вирішення задачі динамічного балансування навантаження для транспортних каналів у багатопроцесорних комп'ютерних системах; [6] - методи автоматизації процесу планування обчислень у розподіленій системі; [7] - алгоритми динамічного планування обчислень, структурні схеми інтеграції цих алгоритмів у систему автоматичного динамічного розпаралелювання обчислень, та метод оптимізації динамічного графу програми; [8] - аналіз існуючих підходів, формулювання методів та принципів DDCI-системи та її порівняльний аналіз з MPI; [9] - організаційна структура системи моделювання великих мереж головного мозку у розподілених комп'ютерних системах; [10] - формулювання інтерфейсу для DDCI-системи; [11] - методи розширення системи моделювання частини головного мозку, що були застосовані для дослідження хвороби Паркінсона; [12] - створені централізована та децентралізована моделі DDCI-системи, завдяки тестуванню було показано ефективність створеного підходу; [13] - система автоматичного розпаралелювання обчислень.

Апробація результатів роботи. Результати проведених досліджень та основні положення роботи доповідалися та обговорювалися на 10-ти міжнародних наукових конференціях, останні:

* «Ninth international young scientists' conference on applied physics» (Київ, Україна, 17 червня 2009);

* «17th International Workshopon Nonlinear Dynamics of Electronic Systems» (Раперсвіль, Швейцарія, 21 червня 2009);

* «5-th IEEE International Workshopon Intelligent Data Acquisitionand Advanced Computing Systems: Technology and Applications» (Ренде (Косенза), Італія, 21 вересня 2009);

* «Third Vogt-Brodmann Symposium» (Юліх, Німеччина, 4 грудня 2009);

* «XVII Международная конференция студентов, аспирантов и молодых ученых “Ломоносов-2010”» (Москва, Росія, 15 березня 2010);

* «Second International Workshop-School CHAOS and DYNAMICS in BIOLOGICAL NETWORKS» (Кергіс (Корсика), Франція, 3 травня 2010);

* «7-th International Scientific and Practical Conferenceon Programming UkrPROG'2010» (Київ, Україна, 25 травня 2010);

* «Сьома міжнародна науково-практична конференція «Теоретичні та прикладні аспекти побудови програмних систем»» (Київ, Україна, 7 жовтня 2010).

Публікації. Матеріали дисертації та всі основні положення повністю викладено в 13 опублікованих наукових працях - 4 статті в наукових фахових виданнях [1-4],
2 статті в інших наукових виданнях [5-6] та 7 робіт в матеріалах і тезах доповідей на наукових конференціях [7-13]. Одна наукова праця написана одноосібно [13].

Структура й об'єм дисертаційної роботи. Дисертація складається із вступу, чотирьох розділів, висновків, що містять основні результати роботи, списку використаної літератури з 129 найменувань, 58 рисунків, 4 додатків (додаток Г містить 4 акти впровадження дисертаційної роботи). Повний об'єм дисертації складає 210 сторінок, з них 149 сторінок основного тексту.

2. ОСНОВНИЙ ЗМІСТ

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

Перший розділ присвячений огляду найпоширеніших методів розробки паралельних програм. Неавтоматизоване статичне розпаралелювання, на прикладі бібліотек MPI та PVM, зустрічається значно частіше інших підходів при створенні ефективних паралельних алгоритмів. Причина такої ситуації пов'язана з більшою ефективністю «ручного» розпаралелювання в порівнянні з іншими підходами.

Наприкінці 1990 років з'явилося працездатне покоління напівавтоматичних систем розпаралелювання, таких як OpenMP та DVM. У результаті цих розробок спростився процес розпаралелювання певного класу задач для невеликих систем із загальною пам'яттю. Останнім з цього напрямку став підхід DVM+OpenMP який дозволяє розробляти паралельні рішення для систем з розподіленою пам'яттю але його використання та налагодження ускладнене.

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

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

З працездатних представників пасивного автоматичного динамічного розпаралелювання, однією з найбільш вдалих систем такого класу можна вважати Т-Систему. Загалом, для задач з 20-30 потоками у гомогенних багатопроцесорних систем з високошвидкісними каналами зв'язку такий підхід можна вважати вдалим. Єдиним його недоліком є далеко не ідеальна ефективність розпаралелювання через активний протокол обміну повідомленнями між станціями, та відсутність динамічного балансування навантаження. Але цей підхід нездатний ефективно використовувати розподілені системи зі змішаною архітектурою пам'яті.

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

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

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

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

Запропонованому комплексу, що складається з методу розпаралелювання обчислень та методики реалізації цього методу, було дано назву «DDCI»(Dynamic Distribution Calculations Interface). Система DDCI розроблена на основі побудови та аналізу графів послідовних програм, що динамічно змінюються. Особливість такого підходу полягає в тому, що система динамічного розпаралелювання обчислень (DDCI) бачить алгоритм послідовної програми як граф, що складається з позначених чистих функцій (вершини графа) та потоків даних між ними (ребра графа). За ефективне динамічне розпаралелювання обчислень відповідає планувальник.

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

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

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

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

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

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

Основні характеристики DDCI-системи:

– Підтримка C++ та розширення для інших послідовних мов програмування.

– Підтримка Windows, Linux та інших POSIX-сумісних платформ.

– Можливість налагодження паралельних рішень у класичних середовищах розробки.

– Підтримка різних багатопроцесорних архітектур.

– Підтримка динамічного балансування навантаження.

– Спостереження за динамічними змінами в обчислювальній системі.

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

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

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

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

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

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

Порядок, у якому елементи будуть додаватися в динамічний граф програми, також показаний на схемі (нумерація з позначкою «11»).

Методика створення централізованої та децентралізованої архітектури.

У роботі були запропоновані та теоретично обґрунтовані принципові схеми побудови серверної (рис. 3) та розрахункової (рис. 4) станцій DDCI-системи. інтерфейс автоматичний розпаралелювання обчислення

Рис. 3. Принципова схема побудови серверної станції DDCI-системи

На приведених принципових схемах можна бачити наступні нововведення у динамічне розпаралелювання обчислень: використання одночасно пасивного та активного планувальників; підтримка різнопріоритетного транспортного рівня; інтеграція централізованих алгоритмів «прибирання сміття» та «системи фонового копіювання»; урахування змін продуктивності обчислювальних станцій за допомогою «систем моніторингу».

Рис. 4. Принципова схема побудови розрахункової станції DDCI-системи.

Були запропоновані архітектурні рішення для об'єднання серверних та обчислювальних станцій DDCI-системи у централізовану та децентралізовану моделі. Централізовану схему запропоновано використовувати для розпаралелювання програмних рішень для 20-50 потоків (в залежності від складності кінцевої задачі), ця схема приведена на рис. 5, для обчислювальних станцій «1», «3» та їх серверної станції «2». Досягти децентралізованої схеми запропоновано за допомоги об'єднання декількох централізованих схем як рівноправних (рис. 5), тобто сервери «2», «5» є рівноправними, але кожен з них самостійно відповідає за свої обчислювальні станції та розпаралелює окрему частину кінцевої задачі.

Рис. 5. Схема побудови паралельної програми для шести станцій з двома серверами

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

Інтерфейс DDCI-системи для специфікацій ANSI C++ та Microsoft С++ виконано на рівні бібліотеки.

Позначення на рис. 6: argc та argv - параметри, передані при виклику функції main (), ці параметри використовуються для ініціалізації MPI бібліотеки, scheduler - дозволяє вказати тип планувальника, який повинна використовувати DDCI-система. Інтегровані планувальники DDCI-системи були експериментально протестовані на наступних багатопроцесорних обчислювальних архітектурах: системи зі спільною пам'яттю, гомогенні системи з розподіленою пам'яттю, великі гетерогенні системи.

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

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

2. Помітка змінних, які відповідають за пересилання даних між DDCI-функціями, за допомогою контейнерів (рис. 8).

Планувальник DDCI-системи.

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

Таблиця 1 Характеристики розроблених алгоритмів планування

Назва алгоритму	Поліноміальна складність алгоритму
	Для систем із загальною пам'яттю	Додатковий множник для систем з розподіленою пам'яттю
«Швидкий»		-
«Стандартний»
«Повільний»

Примітки: m - кількість обчислювальних станцій у системі;

n - кількість вершин у динамічному графі на даний момент.

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

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

Де - пріоритет функції Fi;

- множина вершин графа, що очікують виконання функції Fi;

- час, затрачений на виконання функції Fi;

- час, затрачений на передачу даних по транспортних каналах від функції Fi до функції Fj.

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

Інтеграція алгоритмів планування у DDCI-систему проводиться по двох схемах:

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



Рис. 9. Схема інтеграції пасивного планувальника в DDCI-систему (два сервера)

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

Рис. 10. Схема інтеграції активного планувальника в DDCI-систему (два сервера)

Рис. 11. Схема інтеграції оптимізатора графа

Четвертий розділ містить результати експериментального дослідження та застосування DDCI-системи.

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

Перед дослідженням ефективності розпаралювання, завдяки зміні розмірів малих блоків матриць, було оптимізовано навантаження на процесорний кеш (рис. 12). У тесті використовувалися матриці розмірністю 12000*12000 елементів, з розміром малих блоків 25*25. Усі результати були усереднені не менш ніж по 10 ідентичних експериментах. Для моделювання (рис. 13) використовувалися чотирьохядерні обчислювальні станції на основі процесорів Intel (R) Xeon (TM) CPU 3.20Ghz, з об'ємом оперативної пам'яті 4Гб. Усі станції були об'єднані мережею GigabitEthernet, з підтримкою OpenMPI 1.2.8. Для компіляції використовувався компілятор GCC з наступною оптимізацією: «-m64 - O3 - mtune=opteron».

Рис. 12. Графік зміни часу роботи алгоритму добутку двох матриць залежно від розміру малих блоків



Рис. 13. Графік зміни часу роботи паралельної програми залежно від числа потоків

У результаті дослідження було виявлено зменшення часу роботи послідовного алгоритму з 3 години 17 хвилин, до 7 хвилин 20 секунд для паралельної реалізації на 32 процесорах. Тобто прискорення послідовного алгоритму завдяки автоматичному динамічному розпаралелюванню досягло на 32 процесорах близько 27 одиниць, з урахуванням транспортних обмежень прискорення було максимально можливим.

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



Рис. 14. Демонстрація принципу нагромадження затримок у паралельних алгоритмах, на прикладі рішення системи диференційних рівнянь

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

Рис. 15. Розподіл імовірності тимчасових втрат при роботі сильно зв'язкового паралельного алгоритму на основі MPI бібліотеки



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

ВИСНОВКИ

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

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

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

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

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

5. Вперше розроблено та застосовано у DDCI-системі алгоритми переносу централізованих методів динамічного аналізу графів програм на децентралізовану мультисерверну архітектуру, що працює на базі пасивних протоколів міжсерверної синхронізації. Такій підхід дозволив досягати ефективного розпаралелювання обчислень у великих багатопроцесорних комп'ютерних системах (понад 50-100 обчислювачів), при умові що послідовний алгоритм теоретично можливо розпаралелити на таку кількість потоків.

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

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

1. Левченко Р. И. Система автоматического динамического распараллеливания вычислений для многопроцессорных компьютерных систем со слабой связью (DDCI) / Левченко Р. И., Судаков А. А., Погорелый С. Д., Бойко Ю. В. // Управляющие системы и машины. - 2008. - № 3. - С. 66-72.

2. Левченко Р. И. Проблемы эффективности автоматического динамического распараллеливания вычислений для многопроцессорных систем со слабой связью / Левченко Р. И., Судаков А. А., Погорелый С. Д., Бойко Ю. В. // Проблеми програмування. - 2010. - № 2-3. - Спец. вип. : Матеріали міжнар. конф. УкрПРОГ 2010. - С. 178-184.

3. Левченко Р. И. Влияние временных характеристик параллелизуемых блоков последовательных алгоритмов на эффективность автоматического динамического распараллеливания в многопроцессорных системах со слабой связью / Левченко Р. И., Судаков А. А., Погорелый С. Д., Бойко Ю. В. // Наукові праці ДонНТУ. Серія «Інформатика, кібернетика та обчислювальна техніка». - 2010. - № 12 (165). - С. 52-59.

4. Левченко Р. И. Объединение преимуществ пассивной и активной балансировки нагрузки в рамках комплексной системы планирования для динамически распараллеливаемых программ / Левченко Р. И., Судаков А. А., Погорелый С. Д., Бойко Ю. В. // Математичні машини і системи. - 2010. - № 4. - С. 24-32.

5. Левченко Р. І. Проблеми динамічного балансування навантаження для транспортних каналів у багатопроцесорних комп'ютерних системах зі слабким зв'язком / Левченко Р. І., Погорілий С. Д., Бойко Ю. В. // Вісник університету «Україна». - К. : видавництво університет «Україна», 2010. - № 2. - С. 128-132.

6. Сальніков А. О. Архітектура веб-орієнтованої системи віртуальних лабораторій в Грід-інфраструктурі / Сальніков А. О., Слюсар Є. А., Анісімов М. І., Левченко Р. І., Мар'яновський В. А., Десятник Н. П, Чередарчук А. І., Судаков О. О. Бойко Ю. В. // Зб. наук. праць «Інформаційні технології в освіті». - Х. : Видавництво ХДУ, 2009. - № 4. - С. 31-39.

7. Погорелый С. Д. Решение задачи централизованного планирования для систем динамического распараллеливани явычислений / Погорелый С. Д., Левченко Р. И. // Сьома міжнар. наук.-практ. конф. «Теоретичні та прикладні аспекти побудови програмних систем», 4-8 жовт. 2010 р. - К., 2010. - С. 388-398.

8. Levchenko R. I. DDCI: Dynamic parallelizing system for high performance computing clusters / Levchenko R. I., Sudakov O. O. // Proceedings of theseventh international young scientists' conference on applied physics, June 13-15, 2007. - Kyiv (Ukraine), 2007. - P. 147-148.

9. Levchenko R. I. Parallel software for modelling dynamics of Large Neuronal Networks / Levchenko R. I., Sudakov O. O. // Proc. 4-th International Conference «Electronics and applied physics». October 23-25, 2008. - Kyiv (Ukraine), 2008. - P. 87-88.

10.Levchenko R. I. DDCI: Interface for Transparent parallelizing of calculations / Levchenko R. I., Sudakov O. O., Pogorelij S. D. // Proceedings of theninth international young scientists' conference on applied physics, June 17-20, 2009, - Kyiv (Ukraine), 2009. - P. 12.

11.Levchenko R. I. Parallel software for modeling complex dynamics of large neuronal networks / Levchenko R. I., Sudakov O. O., Maistrenko Yu. L. // Proc. 17th International Workshop on Nonlinear Dynamics of Electronic Systems, June 21-24, 2009. - Rapperswil (Switzerland), 2009. - P. 34-37.

12.Levchenko R. I. DDCI: Simple Dynamic Semiautomatic Parallelizing for Heterogeneous Multicomputer Systems / Levchenko R. I., Sudakov O. O., Pogorelij S. D. // Proceedings of the 5-th IEEE International Workshop on Intelligent Data Acquisition and Advanced Computing Systems : Technology and Applications, September 21-23, 2009. - Cosenza (Italy), 2009. - P. 208-211.

13.Левченко Р. И. Автоматическое динамическое распараллеливание вычислений для гетерогенных многопроцессорных компьютерных систем / Левченко Р. И. // Материалы докладов XVII Междунар. конф. студ., асп. и молодых ученых «Ломоносов», 15-20 марта 2010 г. - М. : МГУ им. М. В. Ломоносова, 2010. - С. 23-24.

АНОТАЦІЇ

Левченко Р. І. Метод автоматичного динамічного розпаралелювання обчислень для гетерогенних багатопроцесорних комп'ютерних систем зі слабким зв'язком. - Рукопис.

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

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

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

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

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

Левченко Р. И. Метод автоматического динамического распараллеливания вычислений для гетерогенных многопроцессорных компьютерных систем со слабой связью. - Рукопись.

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

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

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

Во втором разделе диссертационной работы формируются основные идеи предложенного метода. Выделяются приоритетные классы задач, распараллеливание которых должно быть одновременно простым и эффективным. К таким классам относятся: сеточные алгоритмы, работа с матрицами, алгоритмы перебора, решение систем дифференциальных уравнений, алгоритмы поиска. Формируются новые интерфейсные требования для системы автоматического распараллеливания вычислений. Требования строятся исходя из того, что изменения в последовательном программном коде должны быть минимальны, но этого при необходимости достаточно для частичного управления процессом автоматического распараллеливания вычислений. На основе новых интерфейсных требований создаются интерфейс DDCI-системы и методика трансформации последовательных алгоритмов в параллельные аналоги.

DDCI (интерфейс динамического распараллеливания вычислений, dynamic distribution calculations interface) представляет собой реализацию разработанного в диссертации метода автоматического динамического распараллеливания вычислений для языка программирования С++, и операционных систем Windows, Linuxи других имеющих поддержку MPI и POSIX.

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

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

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

Во втором экспериментальном исследовании проверялась уместность использования динамической балансировки нагрузки в гомогенных многопроцессорных компьютерных системах с распределённой памятью. В эксперименте учитывалось влияние активности системных служб и пользователей на скорость работы параллельных алгоритмов. В результате была показана необходимость использования динамической балансировки нагрузки даже в гомогенных системах, так как это позволило в 10-15 раз уменьшить влияние сторонней активности на время работы параллельной программы. Было экспериментально установлено, что параллельный алгоритм на 32 процессорной системе вследствие сторонней активности, составляющей менее 0,5 % от общей производительности системы, может работать на 5-30 % медленнее ожидаемого времени.

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

Levchenko R. I. A method of automatic dynamic parallelizing of calculations for heterogeneous multiprocessing computer systems with weak connection. - Manuscript.

Thesis on competition of Candidate of Technical Sciences degree in speciality 01.05.03 - Mathematical and software support of computer machines and systems. - Taras Shevchenko National University of Kyiv, Kyiv, 2011.

The dissertation is devoted to development and evaluation of a new method for dynamic parallelizing of calculations for various multiprocessor computing systems.

Analytical overview of existing methods for parallel computing solutions development is provided. Evaluation of advantages and limitations of the methods is performed.

The goal of the dissertation work involves creation of method for minimizing complexity of parallel program development process and improving performance of resulting parallel solutions running on various multiprocessor architectures. Interface requirements for sequential programs, that can be automatically parallelized and the technique for the program transformations into parallel ones are introduced.

The task of unification of active and passive dynamic parallelizing technique advantages and development of centralized and decentralized dynamically parallelizable algorithms is solved. Experimental investigation of the proposed method is conducted.

Keywords: parallel calculations, automatic dynamic parallelizing, multiprocessor computer systems, load balancing

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