Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах
Запропоновано один із можливих підходів до розробки моделей та сценаріїв процесів пошуку оптимальних рішень з використанням кластерних обчислювальних систем. Розглянуто особливості реалізації зазначеного підходу на прикладі острівної моделі паралельного генетичного алгоритму. Предложен один из возмо...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84733 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах / О.О. Криковлюк // Компьютерная математика. — 2013. — № 1. — С. 93-99. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859824683671617536 |
|---|---|
| author | Криковлюк, О.О. |
| author_facet | Криковлюк, О.О. |
| citation_txt | Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах / О.О. Криковлюк // Компьютерная математика. — 2013. — № 1. — С. 93-99. — Бібліогр.: 10 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Запропоновано один із можливих підходів до розробки моделей та сценаріїв процесів пошуку оптимальних рішень з використанням кластерних обчислювальних систем. Розглянуто особливості реалізації зазначеного підходу на прикладі острівної моделі паралельного генетичного алгоритму.
Предложен один из возможных подходов к разработке моделей и сценариев процессов поиска оптимальных решений с использованием кластерных вычислительных систем. Рассмотрено особенности реализации указанного подхода на примере островной модели параллельного генетического алгоритма.
An approach to a design of models and scenarios of optimal decisions searching processes with the use of cluster computing systems is proposed. The applications of this approach on the example of island model of parallel genetic algorithm are considered.
|
| first_indexed | 2025-12-07T15:27:58Z |
| format | Article |
| fulltext |
Компьютерная математика. 2013, № 1 93
Запропоновано один із можливих
підходів до розробки моделей та
сценаріїв процесів пошуку опти-
мальних рішень з використанням
кластерних обчислювальних сис-
тем. Розглянуто особливості реа-
лізації зазначеного підходу на при-
кладі острівної моделі паралель-
ного генетичного алгоритму.
._________________________
О.О. Криковлюк, 2013
ÓÄÊ 519.711,519.81
Î.Î. ÊÐÈÊÎÂËÞÊ
ÎÑÎÁËÈÂÎÑÒ² ÐÅÀ˲ÇÀÖ²¯ ÑÕÅÌ
ÐÎÇÏÀÐÀËÅËÞÂÀÍÍß ÏÐÎÖÅѲ ÏÎØÓÊÓ
ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ
ÍÀ ÊËÀÑÒÅÐÍÈÕ ÀÐÕ²ÒÅÊÒÓÐÀÕ
Вступ. Однією з основних тенденцій, що на-
мітились останнім часом у світовій та вітчи-
зняній практиці комп’ютерного моделюван-
ня, є використання HPC-технологій (High
Perfor-mance Computing). Такі технології, як
правило, реалізуються на платформах супер-
потужної обчислювальної техніки, представ-
лених мережними, кластерними або грід ар-
хітектурами. Широке впровадження даного
класу обчислювальної техніки сприяло роз-
витку нових методологій імітаційного моде-
лювання, зокрема методології Data Farming.
Ця методологія була розроблена в США при
реалізації проекту ALBERT і за останні роки
набула статусу одного з найбільш ефектив-
них інструментаріїв у галузі імітаційного мо-
делювання складних стохастичних систем.
Відмінною рисою даної методології є інтег-
рація методів імітаційного моделювання, оп-
тимізації та технологій високопродуктивних
обчислень [1 – 4].
В Інституті кібернетики імені В.М. Глуш-
кова НАН України накопичено певний дос-
від дослідження складних стохастичних сис-
тем за умов використання мережних архі-
тектур та спеціально розробленої системи
NEDISOPT_D. Зазначена система інтегрує
можливості методів імітаційного моделюван-
ня, оптимізації та технологій розподілених
обчислень і забезпечує направлений пошук
відповідних оптимальних рішень [5 – 7].
Оскільки оптимізаційна стратегія системи
NEDISOPT_D базується на концепціях пара-
лельного генетичного алгоритму, то один із
О.О. КРИКОВЛЮК
94 Компьютерная математика. 2013, № 1
основних аспектів розробки даної системи був пов’язаний із вибором та реаліза-
цією на мережних архітектурах моделі розпаралелювання процесів пошуку оп-
тимальних рішень. Такою моделлю була обрана модель розпаралелювання на
основі декомпозиції даних (на рівні окремих альтернатив, представлених відпо-
відними хромосомами-рішеннями). Для підтримки зазначеної моделі розроблені
спеціальні сценарії, які забезпечують проведення відповідних розподілених оп-
тимізаційно-імітаційних експериментів із можливістю вибору заданих типів
операторів генетичного алгоритму щодо селекції, схрещування, мутації та
форматів представлення пошуку оптимальних рішень.
На рис. 1 показана узагальнена схема процесів пошуку оптимальних рішень
із використанням функціональних можливостей основних компонент системи
NEDISOPT_D – оптимізатора та імітатора. При цьому всі модулі підтримки оп-
тимізатора розміщуються на головному комп’ютері мережі, а на периферійних
комп’ютерах – система розподіленого імітаційного моделювання NEDIS_D [8].
S1 S2 S3 S4 S5
Послідовні сегменти Паралельні сегменти
РИС. 1. Узагальнена схема функціонування системи NEDISOPT_D
Допускається розміщення всіх компонент системи NEDISOPT_D на одному
процесорі. За таких умов система функціонує у режимі послідовного (однопро-
цесорного) моделювання.
Функціональні модулі підтримки групи сегментів S1 забезпечують ввід
управляючої інформації для сесії моделювання. Зауважимо, що оптимізаційно-
імітаційні експерименти на базі NEDISOPT_D реалізуються у форматі сесій мо-
делювання. Модулі групи S2 підтримують формування початкової популяції та
оцінювання хромосом останньої. У загальному випадку множина зазначених
модулів може бути використана для підтримки оптимізаційної стратегії на осно-
ві методу послідовного перебору варіантів. Модулі групи сегментів S3 відобра-
жають реалізацію однопопуляційного, паралельного генетичного алгоритму.
Модулі сегменту S4 виконують оцінювання статистичної достовірності резуль-
татів пошуку оптимальних рішень. Сегменти групи S5 призначені для підтримки
процесів видачі окремих сесій моделювання в заданих форматах [9].
ОСОБЛИВОСТІ РЕАЛІЗАЦІЇ СХЕМ РОЗПАРАЛЕЛЮВАННЯ ПРОЦЕСІВ ПОШУКУ …
Компьютерная математика. 2013, № 1 95
1. Постановка задачі. За умов широкого розповсюдження HPC-технологій
актуальною стає проблема використання в практиці вітчизняного комп’ютер-
ного моделювання високопродуктивних обчислювальних систем, зокрема таких,
як кластерні архітектури. При цьому виникає потреба у виборі або розробці но-
вих моделей для підтримки оптимізаційних стратегій. Так, однопопуляційні мо-
делі паралельного генетичного алгоритму, які були реалізовані в рамках системи
NEDISOPT_D і ефективно використовувались при проведенні експериментів на
мережних архітектурах, мають бути замінені новими моделями паралельного
генетичного алгоритму, більш адаптованими до особливостей організації клас-
терних архітектур.
Мета роботи полягає у розробці нового підходу до реалізації процесів по-
шуку оптимальних рішень на кластерних архітектурах за умов використання
концепцій методології Data Farming, моделей паралельного багатопопуляційно-
го генетичного алгоритму та досвіду розробки системи оптимізаційно-іміта-
ційного моделювання NEDISOPT_D.
2. Особливості реалізації сценарію пошуку оптимальних рішень на кла-
стерних архітектурах. Першочерговою тут є проблема відображення парале-
лізму, властивого алгоритмам пошуку оптимальних рішень на основі паралель-
ного генетичного алгоритму на конфігурацію виділених для конкретних сесій
моделювання ресурсів кластерних систем.
Зменшення часових витрат на взаємодію паралельних процесів, що базуєть-
ся на обміні повідомленнями, робить доцільним вибір такої оптимізаційної стра-
тегії, яка мінімізує зазначені витрати. Типовим прикладом такого роду оптимі-
заційної стратегії є острівна модель паралельного генетичного алгоритму. Осно-
вна ідея тут полягає у розділенні великих за об’ємом множин хромосом-рішень
на однакові за розміром підпопуляції. Процес еволюції кожної підпопуляції реа-
лізується на окремому ядрі кластера (острові) за допомогою одного з можливих
сценаріїв послідовного (непаралельного) генетичного алгоритму. Через деяку
кількість поколінь підпопуляцій відбувається обмін домінантними хромосомами
рішеннями (міграція хромосом), що в цілому підвищує ефективність оптиміза-
ційних стратегій на основі паралельного генетичного алгоритму.
Особливості реалізації сценарію підтримки обраної стратегії на основі ост-
рівної моделі можуть бути сформульовані наступним чином:
− використання концепцій популяція та підпопуляція хромосом-рішень;
− використання концепцій методології Data Farming щодо декомпозиції да-
них, представлених багатовимірним простором параметрів – характеристик оці-
нюваних альтернатив, та реалізації імітаційних експериментів на основі мульти-
сценарних обчислень;
− адаптація структури та об’єму підпопуляцій до конфігурації реальної апа-
ратури (виділених на дану сесію моделювання ресурсів кластера);
− стратегія ініціалізації початкових підпопуляцій та розпаралелювання про-
цесів пошуку оптимальних рішень базуються на так званій моделі збалансованої
декомпозиції даних;
О.О. КРИКОВЛЮК
96 Компьютерная математика. 2013, № 1
− використання концепції міграції для реалізації обміну домінантними хро-
мосомами між островами;
− реалізація прогонів імітаційних моделей у рамках оцінювання кожного
покоління підпопуляції виконується в режимі послідовного (однопроцесорного)
моделювання на відповідних ядрах кластера;
− використання бібліотеки MPI для підтримки схем розпаралелювання про-
цесів пошуку оптимальних рішень;
− сценарії пошуку оптимальних рішень мають забезпечити рівномірне і, за
можливістю, максимальне завантаження процесорів кластера;
− використання ядра з номером 0 для розміщення головного процесора Р0
сценарію пошуку оптимальних рішень на кластерних архітектурах;
− використання СКІТ3 як експериментального полігону для оцінювання ро-
зробленого підходу [10].
Узагальнена схема підтримки запропонованої оптимізаційної стратегії пока-
зана на рис. 2. Тут прийняті наступні позначення: Sij – модулі, які підтримують
операції, аналогічні операціям однопопуляційного генетичного алгоритму, реа-
лізованого в системі NEDISOPT_D. Блоки з позначенням Smij визначають моду-
лі, призначені для модифікації сценарію однопопуляційного генетичного алго-
ритму з метою перетворення його на багатопопуляційний паралельний генетич-
ний алгоритм для підтримки нової оптимізаційної стратегії; N – кількість ядер
кластера, виділених на дану сесію моделювання.
Керуюча інформація для сесій моделювання має включати множину фраг-
ментів, що визначається кількістю виділених на дану сесію моделювання ядер
кластера. До складу вказаних фрагментів обов’язково включається інформація,
яка визначає відповідний сценарій генетичного паралельного алгоритму, що ре-
алізується на кожному окремому ядрі кластерного вузла. Такі сценарії будуть
відрізнятися схемами селекції, операторами схрещування та мутації. До зазначе-
них фрагментів також має включатися інформація про параметри вибраної
моделі міграції.
Після формування та оцінювання поточного покоління підпопуляції хромо-
сом аналізуються умови виконання міграції. За виконання цих умов реалізується
однонаправлений обмін домінантними хромосомами за кільцевим маршрутом
між ядрами кластера. При цьому хромосоми-імігранти витісняють з даної підпо-
пуляції хромосоми з більш низькими показниками якості. В противному випадку
хромосоми іммігранти не включаються до складу підпопуляції на даному ядрі.
Після виконання міграції виконується перевірка умов завершення еволюції.
У разі невиконання умов процес еволюції продовжується.
По завершенню еволюції на всіх ядрах кластера головному процесу Р0 пере-
силається група домінантних хромосом кінцевого покоління кожної підпопуля-
ції. Спеціально розроблений модуль Sm70 (характеристичний порівнювач) ана-
лізує множину таких хромосом з метою вибору найбільш оптимальної.
Для оцінки показників статистичної достовірності оптимальної альтернати-
ви (модуль S40) відбувається багатократний прогін імітаційної моделі з викори-
станням характеристик такої альтернативи як факторів останньої.
ОСОБЛИВОСТІ РЕАЛІЗАЦІЇ СХЕМ РОЗПАРАЛЕЛЮВАННЯ ПРОЦЕСІВ ПОШУКУ …
Компьютерная математика. 2013, № 1 97
Запуск N паралельних процесів
Підготовка початкових підпопуляцій
Ініціалізація керуючих параметрів
сесії моделювання
Формування та оцінювання
початкової підпопуляції
Визначення та оцінювання
поточного покоління підпопуляції
Перевірка умов міграції хромосом
Міграція
Перевірка умов завершення еволюції
Видача результатів сесії моделювання
Вибір оптимальної альтернативи
Оцінювання статистичної достовірності
показників оптимальної альтернативи
Завершення сесії моделювання
Р1
РN –1
Р0
S10
Sm10
Sm20
S20
Sm30
Sm40
Sm50
Sm60
Sm70
S40
S50
Sm80
…
РИС. 2. Узагальнена схема розпаралелювання процесів пошуку оптимальних рішень
на кластерних архітектурах
Модуль S50 забезпечує видачу кінцевих результатів сесії моделювання у
форматах, визначених управляючою інформацією до сесії моделювання.
Модуль Sm80 виконує операції по завершенню паралельних процесів та се-
сії моделювання в цілому.
О.О. КРИКОВЛЮК
98 Компьютерная математика. 2013, № 1
При використанні засобів бібліотеки МРІ щодо розпаралелювання процесів
пошуку оптимальних рішень на всі, виділені для даної сесії моделювання, ядра
кластера симетрично завантажуються всі модулі зазначеного сценарію.
Зауважимо, що всі модулі сценарію виконуються тільки на ядрі з номером 0.
На інших ядрах виконуються множина модулів, обведена дефіс-контуром. Така
схема виконання регулюється управляючою інформацією до сесії моделювання.
Висновки. Розроблено один із можливих підходів до підвищення ефектив-
ності оптимальних рішень за умов використання паралельного генетичного ал-
горитму як оптимізаційної стратегії та можливостей кластерних обчислюваль-
них систем. Зазначені засоби можуть бути використані при дослідженні різного
роду складних стохастичних систем на відповідних кластерних архітектурах.
Одним із перспективних напрямків розвитку виконаних досліджень є роз-
ширювання класу моделей оптимізаційних стратегій та використання можливос-
тей графічних прискорювачів (GPU) у процесах направленого пошуку опти-
мальних рішень використанні кластерних архітектур, зокрема СКІТ-4.
Е.А. Криковлюк
ОСОБЕННОСТИ РЕАЛИЗАЦИИ СХЕМ РАСПАРАЛЛЕЛИВАНИЯ ПРОЦЕССОВ ПОИСКА
ОПТИМАЛЬНЫХ РЕШЕНИЙ НА КЛАСТЕРНЫХ АРХИТЕКТУРАХ
Предложен один из возможных подходов к разработке моделей и сценариев процессов
поиска оптимальных решений с использованием кластерных вычислительных систем.
Рассмотрено особенности реализации указанного подхода на примере островной модели
параллельного генетического алгоритма.
O.O. Krikovluik
FEATURES OF PARALLEL PROCESS REALISATION SCHEMES OF OPTIMAL DECISIONS
SEARCHING ON CLUSTER ARCHITECTURES
An approach to a design of models and scenarios of optimal decisions searching processes with the
use of cluster computing systems is proposed. The applications of this approach on the example of
island model of parallel genetic algorithm are considered.
1. Horne G.E., Meyer T.E. Data Farming: Discovering Surprise // Proc. of the Winter Simulation
Conf. – 2005. – P. 1082–1087.
2. Horne G.E., Schwierz K.-P. Data Farming around the world overview // Proc. of the Winter
Simulation Conf. – 2008. – P. 1442–1447.
3. Choo C.S., Ng E.C., Ang Dave, Chua C.L. Data Farming in Singapore: a brief history // Pro-
ceedings of the 2008 Winter Simulation Conf. – 2008. – Р. 1448–1455.
ОСОБЛИВОСТІ РЕАЛІЗАЦІЇ СХЕМ РОЗПАРАЛЕЛЮВАННЯ ПРОЦЕСІВ ПОШУКУ …
Компьютерная математика. 2013, № 1 99
4. SEED Center for Data Farming: http://harvest.nps.edu/
5. M. Fu: Optimization for Simulation: Theory and Practice. INFORMS // J. on Computing. –
2002. – 14(3). – P. 192 – 215.
6. April J., Glover F., Kelly J.P., Laguna M. Practical introduction to simulation optimization.
Proc. of the 2003 Winter Simul. Conf. – 2003. – P. 71 – 78.
7. Галаган Т.Н., Пепеляев В.А., Сахнюк М.А. Особенности реализации многослойного сце-
нария распределенного поиска оптимальных решений // Проблеми програмування. –
2008. – № 2–3. – C. 636 – 640.
8. Пепеляев В.А., Сахнюк М.А., Черный Ю.М. Параллельная реализация процессов направ-
ленного поиска оптимальных решений // Проблеми програмування. – 2010. – № 2–3. –
С. 572 – 576.
9. Гусев В.В., Галаган Т.Н., Яценко Н.М. Технологическая система распределенного имита-
ционного моделирования NEDIS_D // Тр. Первой научно-практической конф. «Матема-
тичне та імітаційне моделювання систем – МОДС 2006». – 2006. – С. 139 – 143.
10. Суперкомп’ютер ІК НАН України http://icybcluster.org.ua/
Одержано 04.02.2013
Ïðî àâòîðà:
Криковлюк Олена Олександрівна,
аспірантка Інституту кібернетики імені В.М. Глушкова НАН України.
|
| id | nasplib_isofts_kiev_ua-123456789-84733 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:27:58Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Криковлюк, О.О. 2015-07-14T11:53:13Z 2015-07-14T11:53:13Z 2013 Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах / О.О. Криковлюк // Компьютерная математика. — 2013. — № 1. — С. 93-99. — Бібліогр.: 10 назв. — укр. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84733 519.711,519.81 Запропоновано один із можливих підходів до розробки моделей та сценаріїв процесів пошуку оптимальних рішень з використанням кластерних обчислювальних систем. Розглянуто особливості реалізації зазначеного підходу на прикладі острівної моделі паралельного генетичного алгоритму. Предложен один из возможных подходов к разработке моделей и сценариев процессов поиска оптимальных решений с использованием кластерных вычислительных систем. Рассмотрено особенности реализации указанного подхода на примере островной модели параллельного генетического алгоритма. An approach to a design of models and scenarios of optimal decisions searching processes with the use of cluster computing systems is proposed. The applications of this approach on the example of island model of parallel genetic algorithm are considered. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах Особенности реализации схем распараллеливания процессов поиска оптимальных решений на кластерных архитектурах Features of parallel process realisation schemes of optimal decisions searching on cluster architectures Article published earlier |
| spellingShingle | Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах Криковлюк, О.О. Оптимизация вычислений |
| title | Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах |
| title_alt | Особенности реализации схем распараллеливания процессов поиска оптимальных решений на кластерных архитектурах Features of parallel process realisation schemes of optimal decisions searching on cluster architectures |
| title_full | Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах |
| title_fullStr | Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах |
| title_full_unstemmed | Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах |
| title_short | Особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах |
| title_sort | особливості реалізації схем розпаралелювання процесів пошуку оптимальних рішень на кластерних архітектурах |
| topic | Оптимизация вычислений |
| topic_facet | Оптимизация вычислений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84733 |
| work_keys_str_mv | AT krikovlûkoo osoblivostírealízacííshemrozparalelûvannâprocesívpošukuoptimalʹnihríšenʹnaklasterniharhítekturah AT krikovlûkoo osobennostirealizaciishemrasparallelivaniâprocessovpoiskaoptimalʹnyhrešeniinaklasternyharhitekturah AT krikovlûkoo featuresofparallelprocessrealisationschemesofoptimaldecisionssearchingonclusterarchitectures |