Аналіз та врахування неоднорідності в системах розподільної обробки даних
В статті розглянуто відомі методи оцінки неоднорідності паралельних обчислювальних систем, зокрема, систем розподільної обробки даних (СРОД). Приведені можливі напрямки покращення кількісно-якісних оцінок неоднорідності таких систем та наведено підхід до створення виразів для оцінки кіль...
Saved in:
| Date: | 2003 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2003
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/729 |
| 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: | Аналіз та врахування неоднорідності в системах розподільної обробки даних / Князькова З.В. // Математичні машини і системи. – 2003. –-№ 2. – С. 136 – 139. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860021897717088256 |
|---|---|
| author | Князькова, З.В. |
| author_facet | Князькова, З.В. |
| citation_txt | Аналіз та врахування неоднорідності в системах розподільної обробки даних / Князькова З.В. // Математичні машини і системи. – 2003. –-№ 2. – С. 136 – 139. |
| collection | DSpace DC |
| description | В статті розглянуто відомі методи оцінки неоднорідності паралельних обчислювальних систем, зокрема, систем розподільної обробки даних (СРОД). Приведені можливі напрямки покращення кількісно-якісних оцінок неоднорідності таких систем та наведено підхід до створення виразів для оцінки кількісно-якісних характеристик рівня неоднорідності (СРОД). Бібліогр.: 7 назв.
В статье рассмотрены известные методы оценки неоднородности параллельных вычислительных систем, в частности, систем распределенной обработки данных (СРОД). Приведены возможные направления улучшения количественно-качественных оценок неоднородности таких систем и подход к созданию выражений для оценки количественно-качественных характеристик уровня неоднородности СРОД. Библиогр.: 7 назв.
In article known methods of an estimation of heterogeneity of parallel computing systems, in particular systems of distributed data processing (DDPS) are considered. Possible directions of improvement of quantitative - quality standards of heterogeneity of such systems are given and the approach is given in creation of expressions for an estimation of quantitative - qualitative characteristics of a level of heterogeneity DDPS. Refs.: 7 titles.
|
| first_indexed | 2025-12-07T16:47:52Z |
| format | Article |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2003, № 2
136
УДК 681.324
З.В. КНЯЗЬКОВА____________________________________________________________________
АНАЛІЗ ТА ВРАХУВАННЯ НЕОДНОРІДНОСТІ В СИСТЕМАХ РОЗПОДІЛЬНОЇ ОБРОБКИ ДАНИХ
Вступ
В наш час розподільні системи є одним з найперспективніших напрямків розвитку паралельних систем [1,2]. Їх
поширення обумовлено багатьма причинами, серед них: порівняно невисока ціна, надійність, легкість
збільшення потужності та природна розподільність даних. Розподілені системи використовуються для
моделювання складних процесів, створення розподілених баз даних, векторно-матричних обчислень та ін.
Використання розподілених обчислювальних систем на базі локальних і глобальних мереж для
виконання і організації паралельних обчислень та прагнення росту ефективності таких систем привело до
перегляду підходів вирішення задач організації обчислень, планування і диспетчеризації робіт. В неоднорідних
обчислювальних системах вимагає рішення також задача ефективного розподілу ресурсів системи. Ресурси
можна поділити на дві категорії [3]: фізичні та логічні ресурси. В розподіленій системі всі ресурси
розподіляються ще й у просторі. І фізичні, і логічні ресурси повинні бути керованими.
В загальному випадку визначення неоднорідності СРОД можна розділити на два етапи [4]: визначення
ваги (обчислювальної потужності) вузла та адекватну оцінку неоднорідності системи в цілому. Орієнтуючись на
обидві категорії ресурсів системи, при вирішенні задач призначення і розподілу виникає необхідність кількісних
та якісних оцінок неоднорідності як обчислювального середовища, так і множини обчислювальних задач, що
підлягають розподілу в цьому середовищі. Причому важливими є не лише адекватність оцінок, але й
обчислювальні затрати на їх визначення.
Вплив неоднорідності системи на організацію обчислень в СРОД
Визначення строго неоднорідних систем розподіленої обробки даних (НСРОД) введено в роботах по
дослідженню задач планування в паралельних машинних системах, що мають дві особливості: розподіленість
обробки інформації та характеристику неоднорідності не тільки для ресурсів, але й для завдань. Вирішуючи
задачу планування, в таких системах не можна не враховувати час передачі даних (вплив розподіленості), а
також проблему вибору оптимального розкладу із можливих варіантів (вплив неоднорідності) [3]. Цей фактор
ускладнює задачу планування та пошуку оптимізованого рішення. Ці задачі відносяться до класу NP-повних.
Неоднорідні системи розподіленої обробки даних
Неоднорідну систему розподіленої обробки даних (НСРОД) можна представити [3,4] у вигляді зв'язаного
графа:
( )RRRR WUWEUEGR ,,,= , (1)
де { }niME iR ,...,2,1| == – вузли обчислювальної системи; ( )iR MgWE = – ваги вузлів iM ;
( ){ }RjRijiR EMEMMMU ∈∈= |,, – ребра (зв'язки між вузлами системи); RU – відображення Г від
RE , тобто ( )RR EГU = , а ( )RR UfWU = – ваги ребер (наприклад, час, необхідний для передачі даних з
одного вузла в інший).
Основою для визначення ваги вузла є обчислювальна потужність, що залежить від швидкості
процесора, потужності системи вводу/виводу, розміру пам'яті, накладних витрат, що визначаються
операційною системою і застосовуються системою доступу до даних та іншими параметрами.
ISSN 1028-9763. Математичні машини і системи, 2003, № 2
137
Розрахунок відносної обчислювальної потужності iW машини iM в НСРОД для виконання програми P можна
виконати двома способами [3,4]. Перший спосіб полягає у співставленні швидкості даної машини зі швидкістю
найшвидшої машини в мережі [5].
n1,...,i
Smax
S
W j
Pi
i
Pf
i == , (2)
де
i
PS – швидкість машини iM при виконанні Р -ої програми.
Через час виконання P вагу відносної потужності можна представити як
n1,...,i
i
M
P
t
i
M
P
t
i
minf
i
W == , (3)
де i
M
Pt – це час виконання програми P на машині iM .
Інший спосіб полягає у співставленні швидкості даної машини зі швидкістю самої повільної машини в
системі:
n1,...,i
i
P
S
j
P
S
i
minS
i
W == . (4)
Аналогічно вираз для відносної швидкості:
n1,...,i
i
M
P
t
i
max
i
M
P
tS
i
W == . (5)
Відомі оцінки неоднорідності СРОД
Існує декілька способів визначення ступеня неоднорідності СРОД. Всі вони базуються на кількісних, якісних
або кількісно-якісних оцінках.
До оцінок, що враховують якісні особливості системи, можна віднести такі [6,7].
Обчислення середньоквадратичного відхилення потужності кожного вузла від середнього значення в
системі:
n
)W(W
H
2
jc р
n
0j
1
∑ −
= = , (6)
де срW – це середня відносна потужність НСРОД.
Обчислення абсолютного відхилення від середнього значення:
n
WW
H
jc р
n
0j
2
∑ −
= =
. (7)
Вирази (6) і (7) при розрахунку неоднорідності за основу при порівнянні використовують середню
величину набору даних. Таким чином, критичні зміни неоднорідності системи не викликають відповідних змін
ISSN 1028-9763. Математичні машини і системи, 2003, № 2
138
значень оцінок 1Н і 2Н , тоді, як при пропорційній зміні значень кожного з вузлів СРОД, оцінки 1Н і
2Н змінюють свої значення.
Обчислення міри неоднорідності системи через вагу потужності самої швидкої або самої повільної
машини в порівнянні з 1=iW :
n
(P))W(1
H
f
j
n
0j
3
∑ −
= =
; (8)
n
(P))W(1
H
s
j
n
0j
4
∑ −
= = . (9)
Альтернативною характеристикою є однорідність (ступінь гомогенності СРОД):
сргомо WH = . (10)
У оцінок 3H , 4H , гомоH відсутні недоліки оцінок 1H та 2H . Вони більш об’єктивно характеризують
неоднорідність СРОД і є досить простими при обчисленні. Однак ці оцінки приймають великі значення в разі,
коли система РОД однорідна за винятком одного вузла, що унеможливлює її використання при оцінці майже
однорідних або напіводнорідних систем.
Кількісні оцінки неоднорідності враховують лише кількість вузлів з однаковою обчислювальною
потужністю і тому не завжди дозволяють порівняти неоднорідні СРОД за їх оцінками.
Найбільш адекватними є кількісно-якісні оцінки [3], бо вони враховують не тільки абсолютні
характеристики кожного обчислювального вузла, що входить до неї, а й кількість обчислювальних вузлів, що
мають однакові якісні характеристики.
Маючи розподіл вузлів по групах згідно з їх якісними оцінками неоднорідності, можемо обчислити
q
H)
gr
H(1
gr
H
c
H ⋅−+= ,
(11)
де grH – кількісна оцінка неоднорідності, яка враховує кількість груп ( )grn з однаковою вагою вузлів; qH –
оцінка якості неоднорідності; iW '
– вага вузлів, що відносяться до i-ої групи:
n
1n
H gr
gr
−
= ; (12)
gr
n
1i
imid
q n
WW
H
gr
∑
=
′−
= .
(13)
Оцінка (11) є досить складною у використанні і потребує попереднього аналізу та групування
обчислювальних вузлів за потужністю. Більш того, використання однією із складових cH оцінки qH (що є
фактично оцінкою (1)) поширює усі недоліки оцінки 1H на cH .
Для усунення недоліків оцінок (6)-(11) може бути використана така кількісно-якісна оцінка неоднорідності
РСОД [4]:
( )
2
max
n
1i
2
icp
7 Wn
WW4
H
⋅
−
=
∑
= ,
(14)
ISSN 1028-9763. Математичні машини і системи, 2003, № 2
139
де maxW – найбільша вага обчислювального вузла СРОД; срW – середня вага обчислювальних вузлів СРОД.
Оцінка (14) враховує сумарний приріст кожного обчислювального вузла ( )iср WW −*2 по відношенню
до вузла з найбільшою потужністю. Кількісна складова виразу може бути представлена функцією ( )WF від
співвідношень
−
max
iср
W
WW
2 або
− iср
min
WW
W
2 . (15,16)
У даному випадку використана функція ( ) 2WWF = , що дає змогу оцінювати СРОД з великими
відхиленнями ваги обчислювальних вузлів у більшій мірі, ніж СРОД з малими відхиленнями (майже однорідні).
Для більшого розмежування може бути використана експоненційна залежність ( ) WeWF = , тоді вираз буде
мати вигляд
n
e
1e
H
n
1i
W
WW2
8
max
icp
∑
=
−
−
= .
(17)
Висновки
Усі приведені формули для розрахунку кількісних, якісних та кількісно-якісних оцінок неоднорідності мають свої
недоліки. Оцінки 1H , 2H неоднорідності за виразами (1) і (2) є найменш точними. Оцінки 3H , 4H або гомоH
більш об’єктивно характеризують неоднорідність СРОД і є досить простими при обчисленні, однак їх не можна
використовувати у випадку майже однорідних або напіводнорідних систем. Оцінка сН хоч і є кількісно-
якісною, але їй притаманні недоліки оцінки 1H , і вона потребує попереднього аналізу та групування
обчислювальних вузлів за потужністю. Оцінка ( )87 HH є найбільш точною. Використання різних функцій
( )WF дає змогу точно оцінювати неоднорідність СРОД з різним ступенем неоднорідності.
СПИСОК ЛІТЕРАТУРИ
1. Арапов Д. Можно ли превратить сеть в суперкомпьютер // Открытые системы. –1997. – № 4. (www.osp.ru).
2. Андреев А., Воеводин В., Жуматий С. Кластеры и суперкомпьютеры – близнецы или братья? // Открытые системы. –
2000. – № 5 – 6. (www.osp.ru).
3. Симоненко В. П., Демиденко А. А. Измерение неоднородности распределенных вычислительных систем // Вісник НТУУ
“КПІ”. Інформатика, управління та обчислювальна техніка. –1999. – № 32. – C. 53 – 58.
4. Сімоненко В. П., Осадчий О. Є. Оцінка рівня неоднорідності розподілених обчислювальних систем // Вісник НТУУ „КПІ”. –
2000. – C.35 – 41.
5. Zang X., Yan Y. Modeling and characterizing parallel computing performance on heterogonous networks of workstations // Proc. of
the Seventh IEEE Symposium on Parallel and Distributed Processing. – 1995. – Р. 25 – 34.
6. Pham Hong Hang, Valery Simonenko A new algorithm and simulation for task assignment in parallel distributed systems
// Conference ESM96. – Budapest. – 1996. – Р. 95 – 99.
7. Pham Hong Hang, Valery Simonenko Adaptation of algorithm for job-resource assignment in heterogeneous distributed systems
// Conference PDPTA "96, Sunnyvale. – California USA. –1996.
|
| id | nasplib_isofts_kiev_ua-123456789-729 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:47:52Z |
| publishDate | 2003 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Князькова, З.В. 2008-06-24T13:30:33Z 2008-06-24T13:30:33Z 2003 Аналіз та врахування неоднорідності в системах розподільної обробки даних / Князькова З.В. // Математичні машини і системи. – 2003. –-№ 2. – С. 136 – 139. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/729 681.324 В статті розглянуто відомі методи оцінки неоднорідності паралельних обчислювальних систем, зокрема, систем розподільної обробки даних (СРОД). Приведені можливі напрямки покращення кількісно-якісних оцінок неоднорідності таких систем та наведено підхід до створення виразів для оцінки кількісно-якісних характеристик рівня неоднорідності (СРОД). Бібліогр.: 7 назв. В статье рассмотрены известные методы оценки неоднородности параллельных вычислительных систем, в частности, систем распределенной обработки данных (СРОД). Приведены возможные направления улучшения количественно-качественных оценок неоднородности таких систем и подход к созданию выражений для оценки количественно-качественных характеристик уровня неоднородности СРОД. Библиогр.: 7 назв. In article known methods of an estimation of heterogeneity of parallel computing systems, in particular systems of distributed data processing (DDPS) are considered. Possible directions of improvement of quantitative - quality standards of heterogeneity of such systems are given and the approach is given in creation of expressions for an estimation of quantitative - qualitative characteristics of a level of heterogeneity DDPS. Refs.: 7 titles. uk Інститут проблем математичних машин і систем НАН України Програмно-технічні комплекси Аналіз та врахування неоднорідності в системах розподільної обробки даних Анализ и учет неоднородности в системах распределенной обработки данных Analyzing heterogenities and taking them into acount in distrbuted data processing systems Article published earlier |
| spellingShingle | Аналіз та врахування неоднорідності в системах розподільної обробки даних Князькова, З.В. Програмно-технічні комплекси |
| title | Аналіз та врахування неоднорідності в системах розподільної обробки даних |
| title_alt | Анализ и учет неоднородности в системах распределенной обработки данных Analyzing heterogenities and taking them into acount in distrbuted data processing systems |
| title_full | Аналіз та врахування неоднорідності в системах розподільної обробки даних |
| title_fullStr | Аналіз та врахування неоднорідності в системах розподільної обробки даних |
| title_full_unstemmed | Аналіз та врахування неоднорідності в системах розподільної обробки даних |
| title_short | Аналіз та врахування неоднорідності в системах розподільної обробки даних |
| title_sort | аналіз та врахування неоднорідності в системах розподільної обробки даних |
| topic | Програмно-технічні комплекси |
| topic_facet | Програмно-технічні комплекси |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/729 |
| work_keys_str_mv | AT knâzʹkovazv analíztavrahuvannâneodnorídnostívsistemahrozpodílʹnoíobrobkidanih AT knâzʹkovazv analiziučetneodnorodnostivsistemahraspredelennoiobrabotkidannyh AT knâzʹkovazv analyzingheterogenitiesandtakingthemintoacountindistrbuteddataprocessingsystems |