Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах
Побудовано математичну модель оптимального розподілу потужностей ЕОМ в обчислювальній мережі при розв’язуванні фіксованої кількості задач різного типу. Модель враховує час виконання задач кожного типу на ЕОМ різних вузлів, обмеження на час використання ЕОМ кожного вузла. При цьому вважається, що ЕОМ...
Збережено в:
| Дата: | 2005 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
2005
|
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/20919 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах / Р. Тичковський, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 179-184. — Бібліогр.: 4 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-20919 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-209192011-07-29T21:38:13Z Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах Тичковський, Р. Цегелик, Г. Побудовано математичну модель оптимального розподілу потужностей ЕОМ в обчислювальній мережі при розв’язуванні фіксованої кількості задач різного типу. Модель враховує час виконання задач кожного типу на ЕОМ різних вузлів, обмеження на час використання ЕОМ кожного вузла. При цьому вважається, що ЕОМ різних вузлів можуть мати різну потужність. За критерій оптимальності вибрано сумарний час розв’язування задач. Отримана математична модель зводиться до узагальненої задачі про призначення. Для реалізації моделі запропоновано евристичний алгоритм. Проведено програмну реалізацію цього алгоритму та числовий експеримент. The mathematical model for optimal distribution powers of computers in computing networks for solving fixed count of different types’ tasks is made. The model considers time performance of solving tasks on computers in different network nodes, time of using of computers nodes. The computer in different network nodes could have different powers. The total time of solving tasks is chosen for criterion of optimality. The obtained mathematical model is reduced to the generalized assignment problem. The heuristic algorithm for realization this model is proposed. The program realization of this algorithm and numerical experiments are made. Построена математическая модель оптимального распределения мощностей ЭВМ в вычислительной сети при решении фиксированного количества задач каждого типа. Модель учитывает время выполнения задач на ЭВМ различных узлов, ограничения на время использования ЭВМ каждого узла. При этом считается, что ЭВМ различных узлов могут иметь разную мощность. В качестве критерия оптимальности выбрано суммарное время решения задач. Полученная математическая модель сводится к обобщённой задаче о назначениях. Для реализации модели предложен эвристический алгоритм. Приведена программная реализация этого алгоритма и численный эксперимент. 2005 Article Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах / Р. Тичковський, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 179-184. — Бібліогр.: 4 назв. — укр. 1816-1545 http://dspace.nbuv.gov.ua/handle/123456789/20919 519.6 uk Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Побудовано математичну модель оптимального розподілу потужностей ЕОМ в обчислювальній мережі при розв’язуванні фіксованої кількості задач різного типу. Модель враховує час виконання задач кожного типу на ЕОМ різних вузлів, обмеження на час використання ЕОМ кожного вузла. При цьому вважається, що ЕОМ різних вузлів можуть мати різну потужність. За критерій оптимальності вибрано сумарний час розв’язування задач. Отримана математична модель зводиться до узагальненої задачі про призначення. Для реалізації моделі запропоновано евристичний алгоритм. Проведено програмну реалізацію цього алгоритму та числовий експеримент. |
| format |
Article |
| author |
Тичковський, Р. Цегелик, Г. |
| spellingShingle |
Тичковський, Р. Цегелик, Г. Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах |
| author_facet |
Тичковський, Р. Цегелик, Г. |
| author_sort |
Тичковський, Р. |
| title |
Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах |
| title_short |
Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах |
| title_full |
Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах |
| title_fullStr |
Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах |
| title_full_unstemmed |
Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах |
| title_sort |
математичне моделювання оптимального розподілу потужностей еом в обчислювальних мережах |
| publisher |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| publishDate |
2005 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/20919 |
| citation_txt |
Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах / Р. Тичковський, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 179-184. — Бібліогр.: 4 назв. — укр. |
| work_keys_str_mv |
AT tičkovsʹkijr matematičnemodelûvannâoptimalʹnogorozpodílupotužnostejeomvobčislûvalʹnihmerežah AT cegelikg matematičnemodelûvannâoptimalʹnogorozpodílupotužnostejeomvobčislûvalʹnihmerežah |
| first_indexed |
2025-07-02T21:28:32Z |
| last_indexed |
2025-07-02T21:28:32Z |
| _version_ |
1836572174896332800 |
| fulltext |
Математичне моделювання оптимального розподілу
потужностей ЕОМ в обчислювальних мережах
Роман Тичковський 1, Григорій Цегелик 2
1 асистент, Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів, 79000,
e-mail: kafmmsep@franko.lviv.ua
2 д. ф.-м. н., професор, Львівський національний університет імені Івана Франка, вул. Університетська, 1,
Львів, 79000, e-mail: kafmmsep@franko.lviv.ua
Побудовано математичну модель оптимального розподілу потужностей ЕОМ в обчис-
лювальній мережі при розв’язуванні фіксованої кількості задач різного типу. Модель
враховує час виконання задач кожного типу на ЕОМ різних вузлів, обмеження на час
використання ЕОМ кожного вузла. При цьому вважається, що ЕОМ різних вузлів можуть
мати різну потужність. За критерій оптимальності вибрано сумарний час розв’язування
задач. Отримана математична модель зводиться до узагальненої задачі про призначення.
Для реалізації моделі запропоновано евристичний алгоритм. Проведено програмну ре-
алізацію цього алгоритму та числовий експеримент.
Ключові слова: математичне моделювання, розподілене розв’язування за-
дач, евристичний алгоритм.
Вступ. Однією з основних проблем проектування і реалізації систем розподіле-
ної обробки інформації є проблема оптимального розподілу інформаційних ре-
сурсів серед вузлів обчислювальної мережі (ОМ) [1, 2, 4]. Однак експлуатація
ОМ може передбачати не тільки доступ користувачів до інформаційних ресурсів
кожного вузла, а й можливість використання потужностей ЕОМ у будь-якому
вузлі. З огляду на це виникає проблема побудови математичних моделей опти-
мального (на основі певного критерію) використання потужностей ЕОМ в ОМ і
методів їхньої реалізації. Саме побудові таких математичних моделей та методам
їхньої реалізації і присвячена дана праця.
1. Формулювання задачі
Нехай n — кількість вузлів ОМ; m — кількість різних типів задач, призначених
до розв’язування; im — кількість задач i-го типу; jK — j-й вузол ОМ; iZ — і-та
задача; ijt — час виконання задачі iZ на ЕОМ вузла jK ; jt — час, протягом
якого можна використати ЕОМ вузла jK .
Треба так розподілити задачі між ЕОМ у мережі, щоб сумарний час розв’я-
зування задач був мінімальний.
УДК 519.6
179
Роман Тичковський, Григорій Цегелик
Математичне моделювання оптимального розподілу потужностей ЕОМ…
180
2. Побудова математичної моделі
У [3] побудовано математичну модель оптимального використання потужностей
ЕОМ у мережі для випадку, коли треба розв’язувати тільки по одній задачі кожного
типу. В цьому разі шукані змінні можуть набувати значень 0 або 1. У даній роботі
розглядається випадок розв’язування фіксованої кількості задач кожного типу.
Нехай ijx — кількість задач i-го типу, які планують розв’язати на ЕОМ вузла jK .
Тоді математичну модель можна записати у такому вигляді
min
1 1
→=∑∑
= =
m
i
n
j
ijij xtL (1)
за умов
);,1(
1
njtxt j
m
i
ijij =≤∑
=
(2)
);,1(
1
mimx i
n
j
ij ==∑
=
(3)
).,1;,1(},1{ njmimx iij ==∈ (4)
У цьому випадку цільова функція (1) виражає сумарний час, необхідний
для розв’язування задач; ліва частина нерівності (2) визначає час, упродовж яко-
го використовується ЕОМ вузла jK ; умова (3) означає, що кожна задача iZ роз-
в’язується на ЕОМ одного з вузлів.
Для реалізації математичної моделі запропоновано евристичний алгоритм.
3. Евристичний алгоритм реалізації математичної моделі
Зазначимо спочатку, таке: якщо сумарний час, призначених для розв’язування на
ЕОМ задач в окремому вузлі є більший ніж час, протягом якого можна вико-
ристати ЕОМ цього вузла, то такий вузол будемо називати переповненим.
Евристичний алгоритм, який пропонуємо використати для реалізації мате-
матичної моделі, складається з двох етапів. На першому етапі знаходимо почат-
ковий розподіл задач між вузлами. Цей розподіл буде завжди оптимальним, якщо
не враховувати умову (2). На другому — перерозподілимо задачі, якщо для по-
чаткового розподілу існує хоча б один індекс j = r такий, що умова (2) не
справджується. Другий етап складається з низки кроків, до того ж на кожному
кроці перерозподіляємо одну задачу з переповненого вузла так, щоб досягти мі-
німального збільшення значення цільової функції. Другий етап алгоритму вико-
нуємо доти, доки не буде знайдено розподіл, який задовольняє умову (2). Опи-
шемо обидва етапи алгоритму.
Перший етап. Знаходження початкового розподілу.
1. Для всіх ),1( mii = визначаємо isns
t
≤≤1
min . Нехай
iisisns
tt =
≤≤1
min ),1( mi = .
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2005, вип. 2, 179-184
181
2. Знаходимо початковий розподіл задач, тобто визначаємо матрицю
[ ]
nmijx
,
=X , де
( );,1 mimx iisi
==
( )),(),(;,1;,10 iis sisinsmix ≠=== .
Розподіл X завжди буде оптимальним, якщо не враховувати умову (2).
Другий етап. Перерозподіл задач між вузлами.
1. Формуємо вектор ознак ( )neeeE ,...,, 21= , де ( )nje j ,10 == . Елементи
вектора ознак, які будуть дорівнювати 0, визначатимуть ті стовпці матриці Х,
елементи яких можна змінювати, а елементи вектора ознак, які будуть дорівню-
вати 1, визначатимуть ті стовпці матриці Х, які надалі змінюватись не будуть.
Якщо деякий вузол переповнений, то в процесі роботи алгоритму відбувається
перерозподіл задач із цього вузла в інші. Після перерозподілу відповідному еле-
менту je вектора E присвоюємо значення 1 і вузол вважаємо закритим для пере-
розподілу.
2. Для всіх індексів j, таких що ( )nje j ,10 == , перевіряємо виконання
умови (2). Якщо ця умова для всіх j справджується, то на цьому робота алгорит-
му завершується. Розподіл X є оптимальний. Якщо для деякого індексу j = r
умова (2) не виконується, то переходимо до пункту 3.
3. Для кожного i, для якого 0≠irx , знаходимо ( )iriss
tt −min , де мінімум
беремо по тих індексах rs ≠ , для яких 0=se . Нехай ( ) .min irisirsis
tttt
i
−=−
Далі визначаємо ( )irisi
tt
i
−min , де мінімум беремо по тих індексах i, для
яких 0≠irx . Нехай ( ) .min
0: qrqsirisxi
tttt
qi
ir
−=−
≠
Тоді в матриці Х приймаємо
,1+=
qq qsqs xx 1−= qrqr xx . Це означає, що задача qZ із вузла rK скеровується у
вузол
qsK . Такому перерозподілу відповідає мінімальне збільшення цільової
функції.
4. Превіряємо умову (2) для j = r. Якщо вона не виконується, то переходи-
мо до пункту 3. Якщо умова виконується, то вузол вважаємо закритим для пере-
розподілу задач, елементу re присвоюємо значення 1 і переходимо до пункту 5.
5. Для всіх j , таких, що 0=je , перевіряємо виконання умови (2). Якщо
для всіх j умова виконується, то робота алгоритму завершується. Розподіл X
приймаємо за розв’язок задачі. Якщо для деякого індексу j = r умова (2) не
справджується, то переходимо до пункту 3.
Отже, алгоритм дає змогу за скінченну кількість кроків знайти оптималь-
ний або майже оптимальний розподіл задач між вузлами в обчислювальній
мережі. Результатом роботи алгоритму є матриця Х.
Роман Тичковський, Григорій Цегелик
Математичне моделювання оптимального розподілу потужностей ЕОМ…
182
Визначимо максимально можливу кількість кроків. Для кожного знайде-
ного r існує не більше ніж m елементів lrx , значення яких можна зменшити на 1,
тобто здійснити перерозподіл однієї задачі з r-го вузла в інший (виконуючи
пункт 3 другого етапу алгоритму). Оскільки значення lrx може бути не більше
lm , то таких перерозподілів можна зробити не більше ніж lm . Сумарно для кож-
ного знайденого r можна зробити не більше ніж ∑
=
m
l
lm
1
перерозподілів. Усіх
індексів r, для яких не виконується умова (2), може бути не більше ніж n (до того
ж після перегляду (n–1)-го індексу всі вузли будуть закриті для перерозподілу),
то максимальна кількість кроків буде не більше ніж ∑
=
−
m
l
lmn
1
)1( .
4. Числовий експеримент
Числовий експеримент виконано для різних наборів вхідних даних. Тут подано
результати роботи алгоритму для таких вхідних даних n = 10, m = 20,
)10,1(10 == imi , )20,11(5 == imi ; 1000,1 =t 00,012 =t 0,2003 =t 2000, 4 =t
2000, 5 =t 3000, 6 =t 4000, 7 =t 4000, 8 =t 4000, 9 =t 4000 10 =t .
10 15 20 25 30 35 40 45 50 55
20 30 40 50 60 70 80 90 100 110
30 45 60 75 90 105 120 135 150 165
40 60 80 100 120 140 160 180 200 220
50 75 100 125 150 175 200 225 250 275
60 90 120 150 180 210 240 270 300 330
70 105 140 175 210 245 280 315 350 385
80 120 160 200 240 280 320 360 400 440
90 135 180 225 270 315 360 405 450 495
100 150 200 250 300 350 400 450 500 550
20 30 40 50 60 70 80 90 100 110
30 45 60 75 90 105 120 135 150 165
70 105 140 175 210 245 280 315 350 385
80 120 160 200 240 280 320 360 400 440
90 135 180 225 270 315 360 405 450 495
100 150 200 250 300 350 400 450 500 550
10 15 20 25 30 35 40 45 50 55
20 30 40 50 60 70 80 90 100 110
30 45 60 75 90 105 120 135 150 165
[ ijt ] =
40 60 80 100 120 140 160 180 200 220
Після виконання першого етапу алгоритму отримано такий розподіл задач
між вузлами обчислювальної мережі
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2005, вип. 2, 179-184
183
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
[ ijx ] =
5 0 0 0 0 0 0 0 0 0
При цьому значення цільової функції L = 7950. Зауважимо, що отриманий
розподіл не задовольняє умову (2).
Після виконання другого етапу алгоритму отримано такий розподіл
0 0 0 0 0 0 0 0 0 10
0 0 0 0 0 0 0 0 0 10
0 0 0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 7 3 0
0 0 0 0 0 0 2 8 0 0
0 0 0 0 0 0 10 0 0 0
0 0 0 0 0 6 4 0 0 0
0 0 0 1 8 1 0 0 0 0
0 0 7 3 0 0 0 0 0 0
5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 5 0
0 0 0 0 0 5 0 0 0 0
0 0 0 5 0 0 0 0 0 0
0 1 4 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 4 1
0 0 0 0 0 0 0 0 5 0
[ ijx ] =
0 0 0 0 0 0 0 5 0 0
Тут значення цільової функції L = 25100. Значення цільової функції зросло, але
отриманий допустимий розподіл уже задовольняє умову (2). При виконанні друго-
го етапу алгоритму було здійснено 888 перерозподілів задач з одних вузлів у інші.
Зазначимо, що при розв’язуванні цієї ж задачі алгоритмом гілок і меж було
отримано таке оптимальне значення цільової функції L = 24865. Бачимо, розпо-
діл отриманий за допомогою евристичного алгоритму не є оптимальним, але він
близький до оптимального. Перевага евристичного алгоритму над алгоритмом гілок і
меж полягає в простоті реалізації. Крім того, евристичний алгоритм вимагає
значно меншого часу при розв’язуванні задач.
Роман Тичковський, Григорій Цегелик
Математичне моделювання оптимального розподілу потужностей ЕОМ…
184
Висновки. Побудовано математичну модель оптимального розподілу задач серед
ЕОМ вузлів обчислювальної мережі. За критерій оптимальності вибрано сумарний
час розв’язування задач. Математичною моделлю задачі є узагальнена задача про
призначення, для розв’язування якої запропоновано евристичний алгоритм. Цей
алгоритм дає змогу за скінченну кількість кроків знайти оптимальний або майже
оптимальний розподіл задач серед вузлів ОМ. Недоліком алгоритму є те, що він
не дає гарантії отримання оптимального розподілу в разі розв’язування задачі.
Література
[1] Демидович О. В. Математичні моделі оптимального розподілу інформаційних ре-
сурсів серед вузлів обчислювальних мереж і методи їх реалізації: Автореф. дис.
канд. техн. наук: 01.05.02 / НУ «Львівська Політехніка»— Львів, 2001. — 20 с.
[2] Цегелик Г. Г. Системы распределённых баз даных. — Львов: Свит, 1990. — 186 с.
[3] Цегелик Г. Г., Тичковський Р. О. Математичне моделювання оптимального вико-
ристання потужностей ЕОМ в обчислювальних мережах // Вісник Львівського уні-
верситету. Сер. прикл. матем. та інформ. — 2003. — Вип 6. — С. 178-181.
[4] Lee H., Jang G. Data file and workload allocation on a local multi-access computer
networks: incorporating local processing and communication overhead // Int. Journal of
System Science. — 1996. — Vol. 27, № 9. — P. 831-837.
The Mathematical Modeling for Optimal Distribution
of Computers Power in Computing Networks
Roman Tychkovskiy, Grigoriy Tsegelyk
The mathematical model for optimal distribution powers of computers in computing networks for
solving fixed count of different types’ tasks is made. The model considers time performance of
solving tasks on computers in different network nodes, time of using of computers nodes. The
computer in different network nodes could have different powers. The total time of solving tasks is
chosen for criterion of optimality. The obtained mathematical model is reduced to the generalized
assignment problem. The heuristic algorithm for realization this model is proposed. The program
realization of this algorithm and numerical experiments are made.
Математическое моделирование оптимального распределения
мощностей ЭВМ в вычислительних сетях
Роман Тычковский, Григорий Цегелык
Построена математическая модель оптимального распределения мощностей ЭВМ в вы-
числительной сети при решении фиксированного количества задач каждого типа. Модель
учитывает время выполнения задач на ЭВМ различных узлов, ограничения на время
использования ЭВМ каждого узла. При этом считается, что ЭВМ различных узлов могут
иметь разную мощность. В качестве критерия оптимальности выбрано суммарное время
решения задач. Полученная математическая модель сводится к обобщённой задаче о
назначениях. Для реализации модели предложен эвристический алгоритм. Приведена
программная реализация этого алгоритма и численный эксперимент.
Отримано 06.09.05
|