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

The problems of volume-scheduling of distribution tasks and transportation of data packets in a distributed computing network were studied. The mathematical statement was made, effective computational algorithms were developed, and approximate solutions of these problems were obtained. The efficienc...

Full description

Saved in:

Bibliographic Details
Date:	2016
Main Authors:	Krasniuk, Roman P., Tsegelyk, Grygoriy G.
Format:	Article
Language:	Ukrainian
Published:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016
Subjects:	оптимізація розподілена обчислювальна мережа математичне моделювання обчислювальні алгоритми
Online Access:	https://journal.iasa.kpi.ua/article/view/50455
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	System research and information technologies
Download file:

Institution

System research and information technologies

_version_	1866391894950412288
author	Krasniuk, Roman P. Tsegelyk, Grygoriy G.
author_facet	Krasniuk, Roman P. Tsegelyk, Grygoriy G.
author_sort	Krasniuk, Roman P.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2018-03-30T15:27:05Z
description	The problems of volume-scheduling of distribution tasks and transportation of data packets in a distributed computing network were studied. The mathematical statement was made, effective computational algorithms were developed, and approximate solutions of these problems were obtained. The efficiency was shown of the proposed computational algorithms to build an approximate solution for single- and multi optimization problems on the basis of a comparative analysis of the application of these algorithms using test examples. The conclusion was made about the time complexity of proposed algorithms.
doi_str_mv	10.20535/SRIT.2308-8893.2016.2.08
first_indexed	2025-07-17T10:19:18Z
format	Article
fulltext	© Р.П. Краснюк, Г.Г. Цегелик, 2016 Системні дослідження та інформаційні технології, 2016, № 2 81 УДК 519.7, 519.8 DOI: 10.20535/SRIT.2308-8893.2016.2.08 ОПТИМІЗАЦІЯ ПЛАНУВАННЯ РОЗПОДІЛУ ЗАВДАНЬ І ТРАНСПОРТУВАННЯ ПАКЕТІВ ДАНИХ У РОЗПОДІЛЕНІЙ ОБЧИСЛЮВАЛЬНІЙ МЕРЕЖІ Р.П. КРАСНЮК, Г.Г. ЦЕГЕЛИК Розглянуто задачі об’ємно-календарного планування розподілу завдань і тран- спортування пакетів даних у розподіленій обчислювальній мережі. Виконано математичну постановку, сформульовано ефективні обчислювальні алгоритми та отримано наближені розв’язки цих задач. Показано ефективність запропо- нованих обчислювальних алгоритмів щодо побудови наближеного розв’язку одно- та багатокритеріальних задач оптимізації на основі порівняльного аналі- зу застосування цих алгоритмів на тестових прикладах. Зроблено висновок про обчислювальну ефективність запропонованих алгоритмів зі збільшенням роз- мірностей задач. ВСТУП Інтеграція інформаційних та обчислювальних ресурсів в єдине середовище та організація ефективного доступу до них є одним з основних напрямів ро- звитку сучасних інформаційних технологій. Першочерговою стає проблема ефективного використання обчислювальних ресурсів кожного вузла мережі для вирішення складних наукових, виробничих і технологічних завдань. Тому одним з актуальних завдань сьогодення є ефективне керування обчис- лювальними ресурсами у розподіленому середовищі. Зростання кількості ресурсних центрів, що становлять розподілену інфраструктуру, за відсутно- сті або низької ефективності підсистеми планування, яка забезпечує керу- вання потоком задач, не тільки знижує продуктивність використання усієї розподіленої інфраструктури, але й може зробити беззмістовним її створен- ня. Крім того, розподілені системи характеризуються динамічним розвит- ком, що унеможливлює вирішення завдань продуктивного керування ресур- сами у статичному середовищі без використання методів та підходів, які розроблялися для динамічних задач. Упровадження більш дійових алгоритмів керування розподіленим се- редовищем у безпосередньо вже створеній розподіленій інфраструктурі ускладнено і зумовлено додатковими витратами та недостатнім завантажен- ням ресурсних центрів, а через масштабність ресурсного середовища взагалі неможливе. Тому актуальним завданням є створення систем моделювання розподіленої комп’ютерної інфраструктури й ефективних моделей та мето- дів оптимізації, які дозволяють адекватно оцінити поведінку мережі за змі- нюваних умов і на підставі цього покращити стратегії керування потоками завдань. Мета роботи — дослідити проблему планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі. Для досягнення поставленої мети вирішено такі завдання: Р.П. Краснюк, Г.Г. Цегелик ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 82 − сформульовано та досліджено математичні моделі оптимального планування розподілу завдань і транспортування пакетів даних; − розроблено ефективні обчислювальні алгоритми пошуку наближено- го розв’язку одно- та двокритеріальних оптимізаційних задач; − досліджено ефективність сформульованих алгоритмів за результата- ми числових експериментів на тестових прикладах та порівняно з точними розв’язками. ОГЛЯД ЛІТЕРАТУРНИХ ДЖЕРЕЛ Актуальність досліджень оптимізації розподілу завдань у комп’ютерних ме- режах зумовила появу значної кількості публікацій, присвячених цій тема- тиці. Зокрема, у праці [1] побудовано та досліджено математичні моделі роз- поділу потоків обмежених ресурсів у енергетичних системах. Розроблено методи розв’язання задач розподілу потоків, що базуються на поєднанні екст- ремальних підходів до розрахунку мереж. Оптимізація упорядкування пере- давання повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіку досліджено у праці [2]. Для розв’язання задачі запропоновано кри- терій максимальної тривалості доставлення пакета, що мінімізується. З використанням імітаційної моделі вузла мережі проведено числові експе- рименти оптимізації упорядкування передавання повідомлень у вузлах ме- режі для різної кількості черг. Числові методи отримання парето- оптимальних точок, що ґрунтуються на зведенні багатокритеріальних задач до «скаляризованих» задач оптимізації зі спеціальними цільовими функція- ми, розглянуто у праці [3]. Сформовано алгоритм, згідно з яким вихідна за- дача зі знаходження ефективної точки зводиться до послідовного розв’язання задач квадратичного програмування. У фундаментальній праці [4] проаналізовано ефективні архітектури си- стем розподілених обчислень, наведено моделі та технології їх функціону- вання. Моделюванню та оптимізації доступу до інформаційних файлів баз даних для одно- та багатопроцесорних систем присвячено працю [5], у якій розглянуто групу нових та ефективних математичних моделей оптимізації розподілу завдань у системах розподілених обчислень. У монографії [6] ви- світлюється питання моделювання бізнес-процесів за допомогою розподіле- них систем обчислень. Досліджено методи прийняття рішень щодо оптимі- зації за заданим критерієм. ЗАДАЧА КАЛЕНДАРНОГО ПЛАНУВАННЯ РОЗПОДІЛУ ЗАВДАНЬ В ОБЧИСЛЮВАЛЬНІЙ МЕРЕЖІ Розглянемо обчислювальну систему, що складається з деякої множини вуз- лів, у якій розподіляються пакети завдань, які необхідно виконати за період планування. Відома максимальна кількість завдань, яка може бути виконана у вузлах на кожному кроці планування; мінімально допустима кількість за- вдань, яка має бути виконана у вузлах за кожним пакетом; максимальний обсяг завдань, який може бути виконаний у вузлах на кожному кроці плану- вання; мінімально допустима і максимально необхідна кількість завдань, що Оптимізація планування розподілу завдань і транспортування пакетів даних … Системні дослідження та інформаційні технології, 2016, № 2 83 повинна бути виконана у вузлах для кожного пакета. Необхідно визначити на заданий період планування програму виконання пакетів завдань, що за- безпечує ефективне функціонування обчислювальної мережі таку, яка задо- вольняє обмеження можливих обсягів роботи. Нехай I — множина вузлів обчислювальної мережі, J — множина пакетів, T — множина кроків планування. Позначимо через tA максималь- ну сумарну кількість завдань, які можуть бути виконані в обчислювальній мережі за всіма пакетами на кроці планування t ; jB — мінімально допус- тиму кількість завдань, які мають бути виконані у вузлі за пакетом j протя- гом усього часу планування; itC — максимальну кількість завдань, які мо- жуть бути виконані у вузлі i на кроці планування t ; − ijD , + ijD — мінімально допустиму і максимально необхідну кількість завдань, які повинні бути ви- конані у вузлі i для пакета j , Ii∈ , Jj∈ , Tt∈ . Позначимо через ijtx цілочислову кількість завдань, які виконуються на кроці t для пакета j у вузлі i , Ii∈ , ,Jj∈ Tt∈ . Тоді математична модель календарного планування складається з такої системи обмежень: ,,∑∑ ∈ ∈ ∈≤ Ii t Jj ijt TtAx (1) (загальна кількість задач на кожному кроці планування не повинна переви- щувати максимально допустиму кількість); ∑∑ ∈ ∈ ∈≥ Ii j Jj ijt JjBx ,, (2) (загальна кількість задач за кожним із пакетів має бути не меншою за міні- мальну допустиму кількість); ,,,∑ ∈ ∈∈≤ jj itijt TtIiCx (3) (загальна кількість задач для кожного вузла на кожному кроці планування не може перевищувати максимально допустиму кількість); ∑ ∈ +− ∈∈≤≤ Tt ijijtij JjIiDxD ,,, (4) (обмеження мінімально допустимої та максимально необхідної кількості завдань у кожному вузлі за кожним пакетом); ,0 ijtx≤ ,Ii∈ ,Jj∈ ,Tt ∈ (5) (природні обмеження на змінні). Критерії оптимальності можуть залежати від різних показників необ- хідної програми виконання завдань, наприклад, від кількості виконуваних завдань за пакетами та кількості завдань у вузлах обчислювальної мережі. Тоді досліджувана задача календарного планування полягатиме у ви- значенні такої програми виконання завдань, для якої виконуються обмежен- ня (1)–(5) і набувають екстремальних значень критерії: Р.П. Краснюк, Г.Г. Цегелик ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 84 ,,, JjBxf Ii j Jj ijtj ∈ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∑∑ ∈ ∈ ,,,, TtIiCx it Jj ijtit ∈∈ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ Θ ∑ ∈ що визначають умови ефективного виконання завдань за пакетами та ефек- тивності функціонування вузлів обчислювальної мережі. ОПТИМІЗАЦІЙНА ЗАДАЧА ПЛАНУВАННЯ ТРАНСПОРТУВАННЯ ПАКЕТІВ ЗАВДАНЬ Розглядається складна розподілена обчислювальна система, основними еле- ментами якої є: − вузли, які генерують пакети завдань; − вузли, які ретранслюють пакети завдань; − комунікаційні зв’язки між вузлами обчислювальної системи. Схема функціонування процесу транспортування пакетів завдань включає в себе формування пакетів у вузлах, що обмежують обсяги ресурсів пам’яті; транспортування пакетів за різними комунікаційними зв’язками, які обмежують пропускну здатність та проходження пакетів завдань через ре- трансляційні вузли, кожен з яких, у свою чергу, має обмежену «потужність» (пропускну здатність) ретрансляції. Актуальною для подібних систем є така задача планування: за заданих обмежень обсягів пакетів, які формуються, обмежень пропускної здатності комунікаційних ліній зв’язку та відомих «потужностей» ретрансляційних вузлів необхідно на заданий період планування за «стандартних» умов ви- значити максимально можливі обсяги транспортування пакетів у наявній системі за мінімальних видатків на її обслуговування. У постановці цієї за- дачі передбачаються «стандартними» умови як умови безаварійної роботи, за яких довільно задані для елементів системи характеристики можуть бути досягнуті. Нехай mi ,1= — номери ретранслюючих вузлів; ikqj ,1= — номери комунікаційних зв’язків, які сполучають вузол з номером i з вузлом з номе- ром ;k mi ,1= , mk ,1= ; jikW — максимально можлива пропускна здатність лінії зв’язку з номером j , що сполучає вузол i з вузлом k ; ikqj ,1= , mi ,1= , mk ,1= ; jikG — максимальна «потужність» ретрансляції вузла i , що обслуговує j -у лінію зв’язку, яка сполучає ретранслюючі вузли з номе- рами i та k ; ikqj ,1= , mi ,1= , mk ,1= ; iQ — пропускна «потужність» вуз- ла з номером i ; mi ,1= ; ijkc — витрати на траспортування одиниці пакета даних у вузлі ,i що обслуговує j -у комунікаційну лінію від i -го до k -го вузла; ikqj ,1= , mi ,1= , mk ,1= ; iV — обсяг пакетів даних, який може над- ходити у вузол з номером i , 0≥iV , mi ,1= . У випадку, якщо вузол здійснює тільки ретрансляцію пакетів, то 0=iV , mi ,1= . Будемо вважати, що про- Оптимізація планування розподілу завдань і транспортування пакетів даних … Системні дослідження та інформаційні технології, 2016, № 2 85 пускна здатність комунікаційних ліній зв’язку та «потужність» ретранслю- ючих вузлів вимірюються в одних і тих самих одиницях. Позначимо через ijkx обсяг даних, який буде переданий по комуніка- ційній лінії зв’язку з номером j від вузла i до вузла k , ikqj ,1= , mi ,1= , mk ,1= . Тоді можна сформувати обмеження математичної моделі: ∑∑ = = ≤ m k i q j jik Qx ik 1 1 , mi ,1= (6) (обсяг даних, що передається від вузла з номером i , не повинен перевищу- вати його «потужності»); ∑ ∑∑∑ = = == += m k m k q j jiki q j jik ikik xVx 1 1 11 , mi ,1= (7) (рівняння балансу — обсяг даних, який передається від ретрансляційного вузла з номером i , дорівнює обсягу даних, сформованого у вузлі i , і той обсяг даних, що надходить транзитом у вузол з номером i ); ),(min jikjikjik WGx ≤ , ,,1 ikqj = ,,1 mi = mk ,1= (8) (обсяг даних, який передається комунікаційною лінією зв’язку j , не пови- нен перевищувати максимальну «потужність» вузла, що обслуговує цю лі- нію зв’язку, і пропускну здатність j -ї комунікаційної лінії зв’язку, що спо- лучає i -й та k -й вузли); 0≥jikx , ikqj ,1= , mi ,1= , mk ,1= (9) (природні умови на змінні). Наведена загальна математична модель планування транспортування пакетів даних (6)–(9) становить систему лінійних обмежень транспортного типу. Критерії оптимальності задачі планування можна сформулювати як maxmin)( 1 1,1 → ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ∑∑ = == m k q j jik mi ik xXF , (10) (сумарний обсяг даних, що передається у розподіленій обчислювальній ме- режі, має бути максимально можливим); ∑∑∑ = = = →= m i m k q j jikjik ik xcXQ 1 1 1 min)( (11) (сумарні видатки на транспортування пакетів даних мають бути мінімаль- ними). Задача (6)–(11) є двокритеріальною задачею оптимального планування за критеріями максимізації обсягу транспортування пакетів даних та мінімі- зації видатків на їх транспортування. Р.П. Краснюк, Г.Г. Цегелик ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 86 ФОРМУВАННЯ ОБЧИСЛЮВАЛЬНИХ АЛГОРИТМІВ Застосування точних методів до побудови розв’язків задач оптимізації може ускладнюватися для розв’язання задач великої розмірності через значні часові витрати. Загалом задовільні для практичного використання результа- ти можна отримати, застосувавши евристичні алгоритми, такі як «жадібні» та генетичні алгоритми, що дають наближений розв’язок поставленої задачі [7, 8]. Відповідно до «жадібного» методу розв’язок задачі розмірності n шу- каємо у вигляді вектора ],...,[ 1 nxxX = . Початковий розв’язок може бути будь-яким, наприклад нульовим: ]0,...,0[=X . На кожному кроці вибираєть- ся ix з умов задач: зокрема для задачі (1)–(5) — це умова ефективного ви- конання завдань за пакетами, для задачі (6)–(9) — умови (10)–(11). Крім то- го, значення ix має бути таким, щоб розв’язок задачі задовольняв додаткові обмеження, які накладаються при формулюванні оптимізаційної задачі. Точність розв’язку задач з використанням «жадібного» алгоритму оці- нюється за формулою g a Z ZW 100⋅ = , (12) де aZ — екстремальне значення цільової функції, знайдене з використанням наближеного методу; gZ — екстремальне значення цільової функції, отри- мане точним методом. Оцінку точності (табл. 1) отримано для оптимізаційних задач (1)–(5) і (6)–(11), розв’язок яких знайдено з використанням «жадібного» алгоритму. Оцінка розрахована як середнє значення за ста розв’язками поставлених за- дач оптимізації, вхідні дані для яких задавалися випадковим чином. Т а б л и ц я 1 . Оцінка точності використання «жадібного» алгоритму в задачах планування розподілу завдань і транспортування пакетів даних Задача Середній коефіцієнт точності %,W Кількість задач, розв’язків для яких не знайдено (1)–(5) 87,0 12 (6)–(11) 71,5 15 Іншим ефективним методом побудови наближеного розв’язку є вико- ристання генетичних алгоритмів [8]. Вхідними даними для реалізованих у роботі генетичних алгоритмів є два початкові розв’язки, батьківські хро- мосоми, ],...,[ 1 nxxX = та ],...,[ 1 nyyY = ; X і Y можуть визначатися випад- ково чи бути результатом попереднього розв’язку задачі іншим оптиміза- ційним методом, наприклад, з використанням «жадібних» алгоритмів. Необхідна умова для X і Y — задоволення додаткових обмежень, які на- кладаються при формулюванні оптимізаційної задачі. Після задання X і Y відбувається схрещування, тобто взаємний обмін елементами (генами) векторів X і ,Y що містяться на однакових позиціях. Оптимізація планування розподілу завдань і транспортування пакетів даних … Системні дослідження та інформаційні технології, 2016, № 2 87 У реалізованому в роботі програмному додатку обмінюються два елементи. Елементи для обміну вибираються випадково. Наприклад, за розмірності задачі, яка дорівнює трьом, із батьківських хромосом ],,[ 321 xxxX = і ],,[ 321 yyyY = після визначення випадковим чином генів, що підлягають взаємному обміну, зокрема першого і третього, проявляють дві дочірні хро- мосоми: ],,[1 321 yxyYX = і ],,[2 321 xyxYX = . Після схрещування відбувається мутація хромосом, тобто заміна зна- чення генів, які обираються випадково. У реалізованих у роботі генетичних алгоритмах до мутації схильні дочірні і батьківські хромосоми і змінюється значення єдиного гена. Імовірність того, що мутація відбудеться, у реалізо- ваних алгоритмах можна змінювати, задаючи значення відповідного коефі- цієнта. Для розглянутого прикладу, після обрання випадковим чином генів, які можуть бути змінені в усіх хромосомах, наприклад, перший ген у ,X другий ген в 1YX , третій ген в 2YX , а Y не піддалася мутації, отримуємо такий набір хромосом: батьківські: ],,[ 321 xxxX = та ],,[ 321 yyyY = ; дочірні: ],,[1 321 yxyYX = та ],,[2 321 xyxYX = , коли верхні риски позначають логічне заперечення. Після мутації відбува- ється селекція, тобто з чотирьох розв’язків ,X ,Y 1YX , 2YX залишаються тільки два, для яких значення fitness-функції є максимальним. Fitness- функція може задаватися довільно [8]. Після селекції генетичний алгоритм запускається з початку: два отри- мані за селекції розв’язки використовуються як батьківські хромосоми, оскільки генетичні алгоритми належать до типу рекурсивних. Процес може повторюватися задану кількість разів (поколінь) або зупинятися з настанням певної події, наприклад, отримання розв’язку, що забезпечує додаткові об- меження оптимального значення цільової функції. Для числового експерименту обрано побудову наближеного розв’язку задачі (6)– (11) з використанням генетичного алгоритму, коли при схрещу- ванні обмінюються два гени; мутації застосовувалися як до дочірних, так і до батьківських хромосом; за випадкової мутації відбувалася зміна одного гена і ймовірність мутації хромосом обрано рівною 0,5. Для порівняння fitness-функція )(XF визначалася чотирма залежностями: 1) =)(XF )( 1000 2 )(1 Xf Xf = ; 2) )( )( 2 )(1 Xf eXF Xf = ; 3) )( )()( 2 1 Xf XfXF = ; 4) )( 1 2 )()( Xfe XfXF = , коли X — розв’язок оптимізаційної задачі («хромосоми»); )(1 Xf і )(2 Xf — цільові функції у формулах (10), (11). Умовою припинення обчислень у реалізації генетичного алгоритму стало отримання в наборі хромосом, що пройшли селекцію, при цьому кіль- кість поколінь має бути більшою за тисячу. Із досягненням кількості поко- лінь десять тисяч та за відсутності в наборі хромосом, що пройшли селек- цію, алгоритм припиняє виконання з видачею повідомлення про відсутність розв’язку. Для чотирьох, наведених вище варіантів fitness-функції )(XF , виконано оцінку точності розрахунку за формулою (12) (табл. 2). Оцінку розраховано як середнє значення тисячі розв’язків поставленої задачі опти- мізації, вхідні дані для якої задавалися випадково. Р.П. Краснюк, Г.Г. Цегелик ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 88 Т а б л и ц я 2 . Оцінка точності використання генетичного алгоритму в задачі (6)–(11) оптимізації транспортування пакетів даних у розподіленій обчислювальній мережі Fitness-функція )(xF Середній коефіцієнт точності %,W Кількість задач, розв’язків для яких не знайдено за десятьма тисячами поколінь 1 76,1 5 2 77,3 22 3 68,6 10 4 82,7 137 Ще одним ефективним методом побудови наближеного розв’язку дво- критеріальної оптимізаційної задачі є застосування методу мінімального відхилення від ідеальної точки. Цей метод є різновидом загального методу згортання цільової функції [9], але істотно відрізняється від нього за харак- тером інтерпритації отриманого результату. Основна ідея методу полягає в попередньому відшуканні ідеальної точки задачі багатокритеріальної оп- тимізації і розв’язанні деякої нової задачі однокритеріальної оптимізації. У цьому випадку як нову задачу оптимізації розглядають задачу мінімізації відхилення від знайденої ідеальної точки в деякій визначеній метриці [9]. Отриманий розв’язок беруть за остаточний розв’язок вихідної задачі багато- критеріальної оптимізації. Ідеальною точкою задачі (6)–(11) багатокри- теріальної оптимізації є сукупність значень * ijkijk xx = , для якої виконується умова )(min)( lijkl x ijkl fxfxf ijk == , 2,1=l ; mi ,...,2,1= ; ikqj ,...,2,1= ; mk ,...,2,1= . Як метрику, що використовується для розрахунку відхилення від ідеа- льної точки, вибирають метрику s l s lijkllijkls fxffxf 1 2 1 )()),(( ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −=ρ ∑ = , ,...2,1=s Коли 1=s , отримаємо ∑ = −=ρ 2 1 1 )()),(( l lijkllijkl fxffxf . За умови 2=s , отримаємо евклідову метрику: 2 1 2 1 2 2 )()),(( ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −=ρ ∑ =l lijkllijkl fxffxf , (13) а за умови ∞=s — рівномірну метрику ** )((max)),(( lijkll l lijkl fxfffxf −=ρ∞ , .2,1=l Оптимізація планування розподілу завдань і транспортування пакетів даних … Системні дослідження та інформаційні технології, 2016, № 2 89 Як наслідок розв’язок багатокритеріальної задачі можна звести до розв’язку однокритеріальної задачі оптимізації ijkx lijkls fxf min)),(( * →ρ (14) за умов (6)–(9). Алгоритм методу мінімального відхилення від ідеальної точки, що орі- єнтований на розв’язок задачі багатокритеріальної оптимізації у постановці (14), (6)–(9), має ітерактивний характер і полягає у виконанні таких кроків: Крок 1. Попереднє знаходження ідеальної точки. Одним з можливих методів (наприклад, «жадібним» чи генетичним алгоритмом) розв’язати су- купність однокритеріальних задач оптимізації (6)–(11). Будуть розраховані оптимальні значення * lf для кожної цільової функції. Крок 2. Формування нової цільової функції. Як нову функцію цілі роз- глядати, наприклад, вираз (13). Крок 3. Розв’язок нової оптимізаційної задачі. Одним з методів (як і раніше, «жадібним» чи генетичним) побудувати розв’язок нової однокри- теріальної задачі оптимізації (14), (6)–(9), тобто знайти сукупність значень * ijkijk xx = , для яких обчислити значення функції цілі * )( lijkl fxf = . Скорис- тавшись формулою для метрики, аналогічною до тієї, яка використовувала- ся для формування нової цільової функції на кроці 2, сформулюємо умову припинення обчислень. Наприклад, для випадку 2=s отримаємо ε< ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −=ϕ ∑ = 2 1 2 1 2**** ),( l llll ffff , (15) де ε — похибка обчислень. Якщо умова (15) виконується, то результатом розв’язання багатокритеріальної задачі є сукупність значень * ijkijk xx = , а оп- тимальні значення цільових функцій становлять .)( * lijkl fxf = У випадку порушення умови (15) переприсвоюються * ll ff = , 2,1=l і відбувається повернення до кроку 2. Для трьох варіантів метрик, наведених вище, виконано оцінку серед- ньої кількості кроків розрахунку розв’язку задачі (14), (6)–(9) за ста варіан- тами вхідних даних, які задавалися випадково (табл. 3). Т а б л и ц я 3 . Оцінка кількості кроків у методі відхилення від ідеальної точки за побудови розв’язку оптимізаційної задачі (6)–(11) Степінь метрики Середнє значення кількості кроків алгоритму за умов 510−=ε , 10=m 1=s 50 2=s 27 ∞=s 34 Р.П. Краснюк, Г.Г. Цегелик ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 90 Для побудови розв’язків однокритеріальних оптимізаційних задач ви- користовувалися модифіковані «жадібні» та генетичні алгоритми. Як пока- зав аналіз отриманих результатів, ефективним варіантом є використання «жадібного» алгоритму внаслідок меншої кількості ітерацій для досягнення необхідної точності наближеного розв’язку. У середньому кількість ітерацій з використанням «жадібного» алгоритму складала 30, коли розрахунок гене- тичним алгоритмом відповідно становив 42 ітерації за умов ,10 5−=ε 10=m та вибору метрики (13). ВИСНОВКИ Переважна більшість практичних задач оптимального керування у розподі- лених обчислювальних мережах не мають аналітичного розв’язку у формі розрахункових формул. Тому стає актуальним формування, дослідження та вибір обчислювальних методів для практичного розв’язування задач багато- критеріальної оптимізації. На вибір методів і засобів впливає характер ма- тематичної моделі та математичні властивості множини допустимих альтер- натив. У першому випадку клас задач, до якого належить розглядувана математична модель, як правило, визначає вибір методу та алгоритму розв’язання відповідної задачі оптимізації. У другому випадку така характе- ристика множини допустимих альтернатив, як, наприклад, розмірність вихід- них даних, істотно впливає на можливість отримання точного чи наближе- ного розв’язку. Виходячи з аналізу досліджених у роботі математичних моделей опти- мізації планування розподілу завдань і транспортування пакетів даних у роз- поділеній обчислювальній мережі та розуміння великої розмірності вихід- них даних, що випливає з розгляду архітектури розподіленої мережі, виконано побудову, аналіз, адаптацію та практичну перевірку наближених методів розв’язання задач оптимізації: «жадібних», генетичних та відхилен- ня від ідеальної точки алгоритмів. Застосування цих алгоритмів показало ефективність побудови наближеного розв’язку. Наведено відповідні алгори- тми та виконано порівняльний аналіз ефективності застосування методів у тестових прикладах, вихідні дані для яких задавались випадково, оцінено обчислювальну точність алгоритмів відносно точних розв’язків задач. У ви- падку розрахунків за алгоритмом методу відхилення від ідеальної точки проведено низку числових експериментів за умови вибору метрики, що дозволило зробити висновок про обчислювальну ефективність евклідової метрики зі збільшенням розмірності задач. Проведений аналіз дозволяє використовувати адаптовані алгоритми як самостійно для отримання розв’язків із задовільною для практичного засто- сування точністю результатів, так і як основу для розроблення комплексних алгоритмів у комбінації з іншими методами. Сформульовані та досліджені математичні моделі оптимізації розподі- лу ресурсів та адаптовані до цих моделей наближені методи розв’язання за- дач оптимізації можуть бути покладені в основу створення програмних ком- плексів керування розподіленою комп’ютерною інфраструктурою, що і є предметом подальших досліджень. Оптимізація планування розподілу завдань і транспортування пакетів даних … Системні дослідження та інформаційні технології, 2016, № 2 91 ЛІТЕРАТУРА 1. Кірік О.Є. Розподіл ресурсів у розподільчих системах з оптимальним перероз- поділом навантаження постачальників продукту / О.Є. Кірік // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 38–51. 2. Пустовойтов П.Е. Оптимизация порядка передачи сообщений в узлах компь- ютерных сетей с учетом динамики трафика / П.Е. Пустовойтов, Л.Г. Раскин // Системні дослідження та інформаційні технології. — 2013. — № 3. — С. 53–57. 3. Александрова В.М. Деякі методи знаходження ефективних точок багатокрите- ріальної задачі оптимізації / В.М. Александрова, Л.О. Соболенко // Систе- мні дослідження та інформаційні технології. — 2014. — № 4. — С. 100–110. 4. Куссуль Н.Н. Grid-системы для задач иследования Земли. Архитектура, модели и технологи / Н.Н. Куссуль, А.Ю. Шелестов . — К.: Наук. думка. — 2008. — 452 с. 5. Цегелик Г.Г. Моделювання та оптимізація доступу до інформації файлів баз даних для однопроцесорних та багатопроцесорних систем / Г.Г. Цегелик. — Львів: ЛНУ імені Івана Франка. — 2010. — 192 с. 6. Томашевський О.М. Інформаційні технології та моделювання бізнес-процесів: навч. посіб. / О.М. Томашевський, Г.Г. Цегелик, М.Б. Вітер, В.І. Дубук. — К.: Вид-во «Центр учбової літератури». — 2012. — 296 с. 7. Ахо А.В. Структуры даных и алгоритмы / А.В. Ахо, Д.Э. Хонкрофт, Д.Д. Уль- ман. — М.: Издат. дом «Вильямс», 2003. — 426 с. 8. Сигал И.Х. Введение в прикладное дискретное программирование: модели и вычислительные методы / И.Х. Сигал, А.П. Иванова. — М.: Физматлит, 2002. — 320 с. 9. Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков. — СПб.: Питер, 2011. — 526 с. Надійшла 20.09.15
id	journaliasakpiua-article-50455
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:19:18Z
publishDate	2016
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/07/beda2f76edf481b0731e3d0fbf322f07.pdf
spelling	journaliasakpiua-article-504552018-03-30T15:27:05Z The planning optimization of tasks distribution and data packets transportation in a distributed computer network Оптимизация планирования распределения заданий и транспортировки пакетов данных в распределенной вычислительной сети Оптимізація планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі Krasniuk, Roman P. Tsegelyk, Grygoriy G. optimization distributed computing network mathematical modeling numerical algorithms оптимизация распределенная вычислительная сеть математическое моделирование вычислительные алгоритмы оптимізація розподілена обчислювальна мережа математичне моделювання обчислювальні алгоритми The problems of volume-scheduling of distribution tasks and transportation of data packets in a distributed computing network were studied. The mathematical statement was made, effective computational algorithms were developed, and approximate solutions of these problems were obtained. The efficiency was shown of the proposed computational algorithms to build an approximate solution for single- and multi optimization problems on the basis of a comparative analysis of the application of these algorithms using test examples. The conclusion was made about the time complexity of proposed algorithms. Рассмотрены задачи объёмно-календарного планирования распределения заданий и транспортировки пакетов данных в распределенной вычислительной сети. Выполена математическая постановка, сформулированы эффективные вычислительные алгоритмы и получены приближенные решения этих задач. Показана эффективность предложенных вычислительных алгоритмов при построении приближенного решения одно- и многокритериальных задач оптимизации на основании сравнительного анализа использования этих алгоритмов на тестовых примерах. Сделан вывод относительно вычислительной эффективности предложенных алгоритмов с увеличением размерности задач. Розглянуто задачі об’ємно-календарного планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі. Виконано математичну постановку, сформульовано ефективні обчислювальні алгоритми та отримано наближені розв’язки цих задач. Показано ефективність запропонованих обчислювальних алгоритмів щодо побудови наближеного розв’язку одно- та багатокритеріальних задач оптимізації на основі порівняльного аналізу застосування цих алгоритмів на тестових прикладах. Зроблено висновок про обчислювальну ефективність запропонованих алгоритмів зі збільшенням розмірностей задач. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016-06-21 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/50455 10.20535/SRIT.2308-8893.2016.2.08 System research and information technologies; No. 2 (2016); 81-91 Системные исследования и информационные технологии; № 2 (2016); 81-91 Системні дослідження та інформаційні технології; № 2 (2016); 81-91 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/50455/71249 Copyright (c) 2021 System research and information technologies
spellingShingle	оптимізація розподілена обчислювальна мережа математичне моделювання обчислювальні алгоритми Krasniuk, Roman P. Tsegelyk, Grygoriy G. Оптимізація планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі
title	Оптимізація планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі
title_alt	The planning optimization of tasks distribution and data packets transportation in a distributed computer network Оптимизация планирования распределения заданий и транспортировки пакетов данных в распределенной вычислительной сети
title_full	Оптимізація планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі
title_fullStr	Оптимізація планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі
title_full_unstemmed	Оптимізація планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі
title_short	Оптимізація планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі
title_sort	оптимізація планування розподілу завдань і транспортування пакетів даних у розподіленій обчислювальній мережі
topic	оптимізація розподілена обчислювальна мережа математичне моделювання обчислювальні алгоритми
topic_facet	optimization distributed computing network mathematical modeling numerical algorithms оптимизация распределенная вычислительная сеть математическое моделирование вычислительные алгоритмы оптимізація розподілена обчислювальна мережа математичне моделювання обчислювальні алгоритми
url	https://journal.iasa.kpi.ua/article/view/50455
work_keys_str_mv	AT krasniukromanp theplanningoptimizationoftasksdistributionanddatapacketstransportationinadistributedcomputernetwork AT tsegelykgrygoriyg theplanningoptimizationoftasksdistributionanddatapacketstransportationinadistributedcomputernetwork AT krasniukromanp optimizaciâplanirovaniâraspredeleniâzadanijitransportirovkipaketovdannyhvraspredelennojvyčislitelʹnojseti AT tsegelykgrygoriyg optimizaciâplanirovaniâraspredeleniâzadanijitransportirovkipaketovdannyhvraspredelennojvyčislitelʹnojseti AT krasniukromanp optimízacíâplanuvannârozpodíluzavdanʹítransportuvannâpaketívdanihurozpodíleníjobčislûvalʹníjmereží AT tsegelykgrygoriyg optimízacíâplanuvannârozpodíluzavdanʹítransportuvannâpaketívdanihurozpodíleníjobčislûvalʹníjmereží AT krasniukromanp planningoptimizationoftasksdistributionanddatapacketstransportationinadistributedcomputernetwork AT tsegelykgrygoriyg planningoptimizationoftasksdistributionanddatapacketstransportationinadistributedcomputernetwork

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

Institution

Similar Items