Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Виконано формалізацію алгоритму Флойда-Уоршала з використанням математичного апарату модифікованих систем алгоритмічних алгебр. Покроково створено низку схем, розглянуто їх особливості і можливі проблеми експериментальної реалізації. Створено узагальнену паралельну регулярну схему алгоритму, що врах...
Збережено в:
| Опубліковано в: : | Системні дослідження та інформаційні технології |
|---|---|
| Дата: | 2010 |
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/49687 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Формування узагальнених паралельних схем алгоритму Флойда-Уоршала / С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель // Систем. дослідж. та інформ. технології. — 2010. — № 1. — С. 52-68. — Бібліогр.: 7 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-49687 |
|---|---|
| record_format |
dspace |
| spelling |
Погорілий, С.Д. Мар’яновський, В.А. Бойко, Ю.В. Вітель, Д.Ю. 2013-09-24T20:33:59Z 2013-09-24T20:33:59Z 2010 Формування узагальнених паралельних схем алгоритму Флойда-Уоршала / С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель // Систем. дослідж. та інформ. технології. — 2010. — № 1. — С. 52-68. — Бібліогр.: 7 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/49687 681.3 Виконано формалізацію алгоритму Флойда-Уоршала з використанням математичного апарату модифікованих систем алгоритмічних алгебр. Покроково створено низку схем, розглянуто їх особливості і можливі проблеми експериментальної реалізації. Створено узагальнену паралельну регулярну схему алгоритму, що враховує особливості як систем зі спільною пам’яттю, так із розподіленою. Выполнена формализация алгоритма Флойда-Уоршалла с использованием математического аппарата модифицированных систем алгоритмических алгебр. Создан пошагово набор схем, рассмотрены их особенности и возможные проблемы экспериментальной реализации; а также обобщенная параллельная регулярная схема алгоритма, которая учитывает особенности как систем с разделяемой памятью, так и с распределенной. Floyd-Warshall’s algorithm is formalized using the mathematical tool of modified algorithmic algebras systems. A set of schemes is created step-by-step, and their features and possible problems in using them are considered along with a generalized parallel regular algorithm scheme which takes into account the peculiarities of systems with shared and distributed memory. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Формування узагальнених паралельних схем алгоритму Флойда-Уоршала Формирование общих паралельных схем алгоритма Флойда-Уоршала Formation of generalized parallel schemes for Floyd-Warshall’s algorithm Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала |
| spellingShingle |
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала Погорілий, С.Д. Мар’яновський, В.А. Бойко, Ю.В. Вітель, Д.Ю. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| title_short |
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала |
| title_full |
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала |
| title_fullStr |
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала |
| title_full_unstemmed |
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала |
| title_sort |
формування узагальнених паралельних схем алгоритму флойда-уоршала |
| author |
Погорілий, С.Д. Мар’яновський, В.А. Бойко, Ю.В. Вітель, Д.Ю. |
| author_facet |
Погорілий, С.Д. Мар’яновський, В.А. Бойко, Ю.В. Вітель, Д.Ю. |
| topic |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| topic_facet |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| publishDate |
2010 |
| language |
Ukrainian |
| container_title |
Системні дослідження та інформаційні технології |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
Формирование общих паралельных схем алгоритма Флойда-Уоршала Formation of generalized parallel schemes for Floyd-Warshall’s algorithm |
| description |
Виконано формалізацію алгоритму Флойда-Уоршала з використанням математичного апарату модифікованих систем алгоритмічних алгебр. Покроково створено низку схем, розглянуто їх особливості і можливі проблеми експериментальної реалізації. Створено узагальнену паралельну регулярну схему алгоритму, що враховує особливості як систем зі спільною пам’яттю, так із розподіленою.
Выполнена формализация алгоритма Флойда-Уоршалла с использованием математического аппарата модифицированных систем алгоритмических алгебр. Создан пошагово набор схем, рассмотрены их особенности и возможные проблемы экспериментальной реализации; а также обобщенная параллельная регулярная схема алгоритма, которая учитывает особенности как систем с разделяемой памятью, так и с распределенной.
Floyd-Warshall’s algorithm is formalized using the mathematical tool of modified algorithmic algebras systems. A set of schemes is created step-by-step, and their features and possible problems in using them are considered along with a generalized parallel regular algorithm scheme which takes into account the peculiarities of systems with shared and distributed memory.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/49687 |
| citation_txt |
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала / С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель // Систем. дослідж. та інформ. технології. — 2010. — № 1. — С. 52-68. — Бібліогр.: 7 назв. — укр. |
| work_keys_str_mv |
AT pogoríliisd formuvannâuzagalʹnenihparalelʹnihshemalgoritmufloidauoršala AT marânovsʹkiiva formuvannâuzagalʹnenihparalelʹnihshemalgoritmufloidauoršala AT boikoûv formuvannâuzagalʹnenihparalelʹnihshemalgoritmufloidauoršala AT vítelʹdû formuvannâuzagalʹnenihparalelʹnihshemalgoritmufloidauoršala AT pogoríliisd formirovanieobŝihparalelʹnyhshemalgoritmafloidauoršala AT marânovsʹkiiva formirovanieobŝihparalelʹnyhshemalgoritmafloidauoršala AT boikoûv formirovanieobŝihparalelʹnyhshemalgoritmafloidauoršala AT vítelʹdû formirovanieobŝihparalelʹnyhshemalgoritmafloidauoršala AT pogoríliisd formationofgeneralizedparallelschemesforfloydwarshallsalgorithm AT marânovsʹkiiva formationofgeneralizedparallelschemesforfloydwarshallsalgorithm AT boikoûv formationofgeneralizedparallelschemesforfloydwarshallsalgorithm AT vítelʹdû formationofgeneralizedparallelschemesforfloydwarshallsalgorithm |
| first_indexed |
2025-11-27T08:10:44Z |
| last_indexed |
2025-11-27T08:10:44Z |
| _version_ |
1850807730828214272 |
| fulltext |
© С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель, 2010
Системні дослідження та інформаційні технології, 2010, № 1 52
УДК 681.3
ФОРМУВАННЯ УЗАГАЛЬНЕНИХ ПАРАЛЕЛЬНИХ СХЕМ
АЛГОРИТМУ ФЛОЙДА-УОРШАЛА
С.Д. ПОГОРІЛИЙ, В.А. МАР’ЯНОВСЬКИЙ, Ю.В. БОЙКО, Д.Ю. ВІТЕЛЬ
Виконано формалізацію алгоритму Флойда-Уоршала з використанням матема-
тичного апарату модифікованих систем алгоритмічних алгебр. Покроково
створено низку схем, розглянуто їх особливості і можливі проблеми експери-
ментальної реалізації. Створено узагальнену паралельну регулярну схему ал-
горитму, що враховує особливості як систем зі спільною пам’яттю, так із роз-
поділеною.
ВСТУП
Ефективність функціонування сучасних комп’ютерних мереж значною мі-
рою визначається успішним розв’язанням задачі маршрутизації. Для оцінки
алгоритму маршрутизації використовують різноманітні критерії якості, такі,
як коректність, ефективність, складність, стійкість, адаптивність, справед-
ливість (щодо вузлів, які обслуговуються) тощо. Алгоритм Флойда-Уоршала
є одним із методів вирішення задачі маршрутизації, який відповідає назва-
ним критеріям.
Із появою багатоядерних процесорів та парадигми паралельних класте-
рних обчислень з’явилась можливість оптимізувати роботу алгоритму за
критерієм часу, використовуючи технології розпаралелювання. Конкретна
реалізація паралельного алгоритму суттєво залежить від методів роботи з
пам’яттю і може спиратись або на системи з розподіленою пам’яттю, або зі
спільною. При застосуванні математичного апарату модифікованих систем
алгоритмічних алгебр В.М. Глушкова (САА-М) [1, 2] вдається формалізува-
ти логіку роботи алгоритму таким чином, щоб абстрагуватися від конкрет-
ної парадигми і розглядати їх як часткові випадки більш загальної абстракт-
ної схеми.
У роботі з використанням САА-М виконано формування узагальнених
паралельних схем алгоритму Флойда-Уоршала [3] для різних парадигм
паралельного програмування з метою його застосування, в тому числі й у
маршрутизаторах нового покоління.
ОПИС АЛГОРИТМУ
Алгоритм використовує поняття проміжної вершини — вершини, що нале-
жить простому шляху },,...,,,{ 1321 NN vvvvv − , проте відрізняється від 1v та
Nv . Нехай граф складається з n вузлів: },...,3,2,1{ nV = . Розглянемо деяку
підмножину вузлів },...,3,2,1{ k для певного k . Для довільної пари вершин
ji, , що належать V , аналізуємо усі можливі шляхи від i до j , що мають
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Системні дослідження та інформаційні технології, 2010, № 1 53
проміжні вершини з обраної підмножини. Нехай серед цих шляхів p —
шлях з найменшою вагою. Використаємо взаємозв’язок між p та найко-
ротшим шляхом, що має проміжні вершини з підмножини }1,...,3,2,1{ −k .
Якщо k не проміжна вершина на шляху p , то усі проміжні вузли p нале-
жать до }1,...,3,2,1{ −k . Отже, найкоротший шлях з i в j , що має проміжні
вершини з },...,3,2,1{ k , збігається з найкоротшим шляхом між тими самими
вершинами, проміжні вузли якого належать }1,...,3,2,1{ −k . Якщо k — про-
міжна вершина p , то цей шлях можна розбити у такий спосіб: jki
pp
→→ 21 , де
1p — найкоротший шлях з i до k , всі проміжні вузли якого належать до
},...,3,2,1{ k , але k не може бути проміжною вершиною даного шляху. Тому
усі проміжні вузли 1p належать }1,...,3,2,1{ −k . Аналогічно і для 2p [3].
Рекурсивне визначення ваги шляхів, що відповідає зробленому вище заува-
женню, наступне:
⎪⎩
⎪
⎨
⎧
≠
−
−−− 0.,min
;0 при ребра говідповідно вага
111
)(
k)d+d,(d
=kw
=d )(k
kj
)(k
ik
)(k
ij
ijk
ij
Елементи )(
ijd 0 складають матрицю D , яка є набором вхідних даних
алгоритму. Далі введено рекурсивне визначення матриці передування, яка
після виконання алгоритму повертає набір останніх проміжних вершин на
найкоротшому шляху від i до j .
⎩
⎨
⎧ ∞==
=
випадку.іншому в
або при )0
i
,wjiNIL
π ij(
ij
⎪⎩
⎪
⎨
⎧ ≤
= −
−−−−
випадку. іншому в
, при
1
1111
)(k
kj
)(k
kj
)(k
ik
)(k
ij
)(k
ij(k)
ij π
d+ddπ
π
Формування інформаційної множини M у багатьох випадках зале-
жить від конкретної задачі та умов її виконання. За умови вважатимемо сам
факт виконання алгоритму в системі з обмеженими ресурсами (часу, пам’яті
тощо), а також логічну організацію (архітектуру) системи (дає вимогу ство-
рення САА-схем у її термінах (наприклад, схем синхронізації та обміну да-
ними). З цієї причини інформаційна множина для схеми послідовного алго-
ритму та паралельної регулярної схеми (ПРС) можуть суттєво відрізнятися.
Інформаційна множина послідовного алгоритму. Робота алгоритму
Флойда-Уоршала ґрунтується на обробці масивів даних, які є, в свою чергу,
матрицею передування P ( i,jP містить номер вершини, що передує вершині
j на шляху від i до j ) та матрицею ваги найкоротших шляхів D . Тому P
і D належать M . Знаходження необхідних значень цих матриць відбува-
ється ітеративно. На кожному кроці знаходяться проміжні матриці kk DP , .
До інформаційної множини також належать індекси ji, (призначені для про-
ходження по P і D ) та індекс k — параметр (крок) виконання алгоритму.
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 54
Оператори та умови. Розглянемо набір операторів і умов із САА-
схеми алгоритму, спираючись на загальну думку (без деталізації проблем
реалізації у системах з обмеженими ресурсами). Основні оператори алго-
ритму такі:
;1
,,
−=≡ k
ji
k
jiD DDA ;1
,,
−=≡ k
ji
k
jiP PPA
;1
,
1
,,
−− +=≡ k
jk
k
ki
k
jiD DDDB .1
,,
−=≡ k
jk
k
jip PPB
З цього місця індекси біля операторів (типу D , P чи q ) визначатимуть
підмножину інформаційної множини, на якій оператор здійснює зміни.
Введемо допоміжні оператори, дія яких полягає у зміні (інкременті) па-
раметрів циклічних процесів:
Xinc , де kjiX ,,= — оператори інкременту (збільшення на одиницю)
відповідного параметра.
InitTemps — оператор для ініціалізаціїї тимчасових даних. Вигляд
оператора не будемо конкретизувати. Він може бути і тотожним оператором
E . Поява цього оператора пов’язана з можливою наявністю механізму зме-
ншення об’ємів використовування пам’яті. Введемо умови:
ZnXkjiXX ∪∈≡= ],1[),, де(α — умова виходу із циклу (альфа-
умова);
)1,;,,( −==∞≠≡ kkXjiZYD X
YZXYZβ — умова перевірки на нескін-
ченність елементів матриці з вагою шляхів (бета-умова);
)(
)(
1
,
1
,
1
,
1
,
1
,
1
,
−−−
=
−−−
+≤≡
+<≡
k
jk
k
ki
k
ji
k
jk
k
ki
k
ji
DDD
DDD
γ
γ
— умови вибору найкоротшого шляху (гам-
ма-умови).
Однією з проблем реалізації подібних алгоритмів є необхідність моде-
лювання ребра графа із нескінченною вагою. Виходом з цього становища є
введення певної критичної величини метрики (найбільшого можливого зна-
чення для ваги). Таке введення було реалізовано ще в протоколі RIP [4], де
нескінченність дорівнювала 16-ти. Проте існують й інші методи позбутися
цієї проблеми (використання вказівників). Метод моделювання порожнього
ребра ребром з великою вагою має ряд переваг та недоліків. Виявляється,
що при застосуванні цього методу зникає необхідність перевірки бета-умови
ijk )1( −β на кожному кроці внутрішньої альфа-ітерації без жодних ускладнень
схем алгоритму. Крім того, можна взагалі позбутись від бета-умов, проте
схеми алгоритму в цьому випадку потребуватимуть змін (введення додатко-
вих операторів обробки вхідної та вихідної матриць алгоритму) для збере-
ження можливості роботи алгоритму у великому діапазоні графів. У наступ-
них схемах було використано моделювання порожнього ребра за допомогою
певної критичної величини метрики.
Для алгоритму Флойда-Уоршала залишається актуальною проблема
знаходження всіх можливих найкоротших шляхів. Схема, що розглядати-
меться поспіль, знаходить лише один найкоротший шлях між двома верши-
нами. Який саме шлях буде обрано, залежить від вибору гамма-умови. Якщо
обирати умову =γ , то отримаємо найкоротший шлях із найменшою кількіс-
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Системні дослідження та інформаційні технології, 2010, № 1 55
тю вузлів (схема (1)). Для умови γ кількість вузлів, навпаки, буде максима-
льною. За наявності великої кількості шляхів із найменшою вагою, всіх їх
можна отримати, комбінуючи умови γ і =γ для різних кроків ітерації по k .
ФОРМУВАННЯ САА-СХЕМИ ПОСЛІДОВНОГО АЛГОРИТМУ
Створимо САА-схему алгоритму, використовуючи введені оператори і умо-
ви (з урахуванням зауважень 1 та 2). Найпростіші логічні міркування підво-
дять до такої схеми [3]:
*)( [( {*)1({*)1(*InitTemps{*)1(
)1()1(
DD BAjik
kjkikkjik
∨
∧
===
=−− γββααα
}.inc*}inc*}inc*])*[)](* KIJAABA PDPP ∨∨
=γ
(1)
В ітераціях по kji ,, здійснюється послідовна обробка матриць P і D .
Залежно від того, чи справедливі бета-умови нескінченності, обирається
відповідна гілка обрахунку. При умові, що A і B не змінюють істинності
гамма-умов (що вірно для даного кроку ітерації), справедлива формула:
]).[][()(*)( PPDDPPDD BABABABA ∨∨∨=∨∨
=== γγγ
Тепер позбудемось від повторення складеного оператора PD AA * в по-
чатковій схемі алгоритму. Для цього скористаємось тим фактом, що опера-
тор PD BB * виконується лише у випадку істинності умови kjkikk )1()1( −− ∧ ββ
і хибності гамма-умови. Тому справедлива така формула:
=∨∨
∧ =−−
) ]*[])*[]*[( (
)1()1(
PDPDPD AABBAA
kjkikk γββ
) ]*[]*[ (
)1()1(
PDPD AABB
kjkikk
∨
∧∧
=
=−− γββ
.
Отже, отримуємо остаточну послідовну схему алгоритму:
∨
∧∧
===
=−−
]*[ ( {*)1({*)1(*InitTemps{*)1(
)1()1(
PD
kjk
BBjik
ikkjik γββααα
}inc*}inc*}inc*) ]*[ KIJAA PD∨ . (2)
Для спрощення введемо умову: .)1()1( =−− ∧∧≡ γββδ kjkikk
Якщо у внутрішній ітерації бета-умова, що не залежить від індексу j ,
дорівнюватиме нулю, то на кожній ітерації по j виконуватиметься друга
гілка альфа-диз’юнкції. Проте схема (2) передбачає перевірку дельта-умови
на кожному кроці ітерації, що значно сповільнить обчислювальний процес.
Для уникнення цього, слід винести бета-умову за альфа-ітерацію по j :
=∨
=−− ∧∧
) ]*[]*[ (
)1()1(
PDPD AABB
kjkikk γββ
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 56
) ]*[) ]*[]*[ ( (
)1()1(
PDPDPD AAAABB
kjkikk
∨∨=
=−− ∧γββ
=∨∨==
=−− ∧
}inc*) ]*[) ]*[]*[ ( ({*)1()2(
)1()1(
JAAAABBj PDPDPD
kjkikkJ γββα
∨∨==
=−− ∧
}]inc*) ]*[]*[ ( {*)1[((
)1()1(
JAABBj PDPD
kjkJikk γβαβ
*)1(*InitTemps{*)1() }]inc*]*[{*)1[( ====∨ ikJAAj
kJ
PD
αα
∨∨
∧
=
=−−
}]inc*) ]*[]*[ ( {*)1[(({*
)1()1(
JAABBj PDPD
kjkjikki γβαβα
.}inc*}inc*) }]inc*]*[{*)1[( KIJAAj PD
jα
=∨ (3)
ФОРМУВАННЯ КОНЦЕПЦІЇ РОЗПАРАЛЕЛЮВАННЯ ЗА ДАНИМИ
Ідея розпаралелювання полягає у розбитті інформаційної множини M на
підмножини, що не перетинаються, з метою їх асинхронної обробки. Подіб-
ні міркування реалізовані у алгоритмі Туега [5], основою якого і є алгоритм
Флойда-Уоршала. За цим алгоритмом кожний маршрутизатор X обробляє
масив даних ],[ YXD , де Y — набір усіх інших вузлів мережі. Дані переси-
лаються між відповідними маршрутизаторами після зміни топології мережі
чи виникнення певної проблеми. В загальному випадку кожна паралельна
гілка є оператором , що працює лише на певній підмножині M .
Розбиття інформаційної множини включає поділ матриць P і D на
підматриці (з можливим введенням нових індексів до M для кожної пара-
лельної гілки). Розглянемо спочатку розбиття по координаті j . Введемо но-
ві умови в множину умов САА:
.1 ,1 ,],1[ ,],1[ ),,[ 01 +==∪∈∪∈∈≡ − naaNnaNsxaaj sxxxjxα
Тоді справедлива така формула:
....
1
1321 xss j
s
x
jjjjjj ααααααα ∧
=
=∧∧∧∧∧=
−
Перейдемо від схеми (2) до синхронної обробки матриць:
}inc*}inc*} {*)1({*)1(*InitTemps{*)1( KIXjik
jsk ααα
=== , (4)
].inc*) ( :оператор складeний[ JiABXX ∨=−
δ
Скористаємось тотожністю САА-М [2] 12 *}{*}{}{
2121
αα
αααα
AAA ∨=
∧
з уточненням, що полягає у специфіці самих операторів і умов. Перед вико-
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Системні дослідження та інформаційні технології, 2010, № 1 57
нанням будь-якого циклу в (4) спочатку відбувається ініціалізація індексу.
Оператор A ( X в схемі (4)) містить його інкремент. Отже, зважаючи на
альфа-умови по j , які було введено раніше, лише одна з
xjα буде хибною
за кожної перевірки значення jα . Якщо jα не хибне, то і усі 1=
xjα . Вла-
стивість випливає з неперетинності множин розбиття і означає виконання
лише одної з синхронних гілок в певний момент часу. Розглядаючи вико-
нання синхронної диз’юнкції в цілому, слід зазначити: при переході
10
1
→=
−xjα під час ітеративного процесу відбувається перехід =
xjα
01→= . Це призводить до миттєвого припинення виконання ( 1−x ) гілки і
народження x -ї; ( 1−x )-а гілка дорівнюватиме невизначеному оператору
[1], x -а — ні, і виконання диз’юнкції буде дією операторів з x -ої гілки:
∨==== )*...***} {[(*)1({*)1(*InitTemps{*)1(
32
1
s
jik
jjjXjik ααα
ααα
…∨∨ )*...***} {(
31
2
s
j
jjjX ααα
α
=∨
−
}inc*}inc*)]*...***} {(
121
KIX
s
js
jjj ααα
α
…
Як уже зазначалося, при переході від одної гілки до іншої своє значен-
ня змінює лише наступна альфа-умова
xjα (попередня є ( 1−x ) гілкою).
Тоді можна позбутися від надлишкових альфа-фільтрів в САА-схемі, що
наведена вище. Також зауважимо, що дія оператора X в кожній гілці від-
бувається на підмножині інформаційної множини, яка не перетинається з
будь-якою підмножиною інших гілок. Позначимо ці підмножини через
., ...,, 1321 ss qqqqq −
∨==== )*} {[(*)1({*)1(*InitTemps{*)1(
21
1
jqXjik
jik
α
ααα
=∨∨∨ }inc*}inc*})] {(...)*} {(
32
2
KIXX
s
jsj
qjq
αα
α
*)1(*InitTemps{*)1( === ik
kα
}.inc*}inc*}] {)*} {([*)1({* 1
1
1
KIXXj
s
js
xx
jxi
qjq
s
x ααα
α ∨=
+
−
=
∨ (5)
Наступним кроком є зведення у часі виконання паралельних гілок
САА-схеми (5). Розглянемо спочатку її часову діаграму (рис. 1).
Схема (5) потребує подальших удосконалень, оскільки експеримента-
льна реалізація вимагає часу на створення кожної гілки, що призводить до
сповільнення дії алгоритму.
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 58
СТВОРЕННЯ АСИНХРОННОЇ ПРС АЛГОРИТМУ
Асинхронне виконання процесів передбачає створення операторів та
об’єктів синхронізації в інформаційній множині. Причому, гілки мають дія-
ти незалежно і обмінюватися даними через оператори обміну. Це постає з
рівноправності усіх гілок щодо обробки матриць інформаційної множини.
Тобто, утворена схема має бути симетричною до гілок виконання. Як було
вже зазначено, доцільніше, з метою економії часового ресурсу програми,
використати дублювання деяких елементів M (наприклад, створити набори
індексів для кожної гілки), аніж постійно передавати їх по мережі.
Перейдемо до асинхронної обробки P і D із збереженням часової схе-
ми (рис. 1). Для цього введемо синхронізацію у вигляді контрольних точок і
циклів очікування. Спочатку перетворимо схему (5) шляхом внесення опе-
ратора 1=j до першої гілки диз’юнкції:
∨==
+
−
=
∨ )*} {([{*)1(*InitTemps{*)1(
1
1
2 xx
jxik
jq
s
x
Xik α
ααα
}inc*}inc*}] {)*} {*)1((
21
1
KIXXj
s
jsj
qjq
αα
α ∨=∨ .
До цього часу ресурс j був спільним для усіх асинхронних гілок. Але
означення асинхронної диз’юнкції вимагає, щоб q -множини, на яких вико-
нуються оператори її гілок, були неперетинні. Тому введемо сукупність ін-
дексів, замість j в інформаційній множині. Змінюються наступні умови і
оператори:
1 ,1 ,],1[ ,],1[ ),,[ ; 01 +==∪∈∪∈∈≡→ − naaNnaNsxaajjj sxxxxjx x
α ;
}{;incinc xxxx jqqJJ ∪→→ .
5=s№ процесу
1
2
3
4
5
1t∆ 12 tt ∆∆ ≠
Рис. 1. Часова діаграма схеми (5)
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Системні дослідження та інформаційні технології, 2010, № 1 59
Крім того, виникає необхідність у залученні нових операторів. Щоб
зберегти поведінку виконання схеми (5), необхідно ввести: 1−= xx jj для
1≠x . Тоді отримуємо таку схему:
∨===
+−
−
=
∨ )*} {*)(([{*)1(*InitTemps{*)1(
11
1
2 xx
jxik
jqxx
s
x
Xjjik α
ααα
}inc*}inc*})] {*)(()*} {*)11(( 121
1
KIXjjXj
s
jsj
qssjq
αα
α −=∨=∨ . (6)
Оператори синхронізації мають бути не прив’язані до конкретної реалі-
зації. Їх дія полягає в очікуванні одних гілок обрахункового процесу деякої
події в інших. Такі оператори потребують введення додаткових умов, що
стають істинними у випадку виконання необхідної події (крім того можлива
поява в інформаційній множині об’єктів синхронізації, стан яких і генерує
подію). Оператори синхронізації в загальному випадку є складеними опера-
торами і можуть бути представлені як композиції операторів встановлення
події (умови), очікування, скидання умови. Аналогом останніх можуть ви-
ступати оператори контрольної точки T , циклу очікування S та оператор
R (Reset), що протилежний по дії до T . R , S , T можуть бути рознесені по
САА-схемі із збереженням загальної синхронізації гілок. Як умови очіку-
вання введемо нові умови контрольних точок: xτ -умови, що встановлюють-
ся в одиницю при дії оператора )( xT τ і скидаються у нуль при дії )( xR τ .
При використанні асинхронної диз’юнкції на момент переходу до нової
гілки виконується присвоювання індексу цієї гілки значення індексу попе-
редньої на момент виходу із неї. Оскільки інформаційні підмножини цих
гілок неперетинні, то для виконання оператора необхідно передати значення
індексу шляхом обміну між гілками. Проте можна скористатися тим фактом,
що значення відповідного індексу при переході на нову гілку вже відоме (це
ліва межа відповідного відрізку, на які було розбито розмірність j ):
1−= xx aj . Тому, враховуючи специфіку роботи синхронної і асинхронної
диз’юнкції, справедлива формула:
∨=∨=
+−
−
=
∨ )*} {*)1(()*} {*)(([
21
1
1 11
1
2 jqjqxx
s
x
XjXjj
j
xx
jx
αα
αα
==∨ − })] {*)(( 1 s
js
qss Xjj
α
∨= −−−
=
∨= ))(*)(*} {*(*)(*)(([ )1112 sxqxxxx
s
x
STXajRS
x
jx
ττττ
α
))](*)(*)(*} {*)(( 101 1
1
ssq RSTXaj
j
τττ
α
=∨ , (7)
де S — оператор циклу очікування істинності відповідної умови. Ця схема
справедлива лише для систем виконання зі спільною пам’яттю, оскільки не
передбачає обміну даними між гілками під час свого виконання.
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 60
У синхронній диз’юнкції схем (6) і (7) виконання гілок відбувається
послідовно. В асинхронній диз’юнкції схеми (7) наступна гілка очікує вико-
нання умови, що встановлюється попередньою. Крім того, кожна гілка очі-
кує виконання останньої ( s -ї) після відповідної альфа-ітерації:
*} {*)(*)(*)(([{*)1(*InitTemps{*)1( 1112 x
jxik
qxxxx
s
x
XajRSik
ααα
ττ −−−
=
=== ∨
.}inc*}inc*))](*)(*)(*}{*)(())(*)(* 101 1
1
KIRSTXajST ssqsx
j
τττττ
α
=∨ (8)
Тепер зведемо у часі процеси асинхронної диз’юнкції, перетворивши
модель синхронізації. Не всі паралельні гілки рівноправні (це випливає з
того, що до народження гілок існував їхній «батьківський» процес). Має іс-
нувати мінімум одна гілка, оператори якої б не відповідали порядку опера-
торів чи взагалі операторам інших (порушення симетрії гілок). Вона назива-
ється основним чи серверним процесом. Оскільки в нашому випадку
виділено тільки перший і останній процеси, то оберемо як серверний процес
саме перший. Ідея полягає у тому, що він має керувати синхронною робо-
тою інших гілок. При роботі на системі з розподіленими ресурсами є мож-
ливість створення симетричної схеми без виділення процесу. Положення
операторів T в схемі (8) визначає послідовний характер виконання схеми.
Переміщення кожного з операторів T на початок виконання кожного про-
цесу (розміщення T після R ) призведе до паралельного виконання гілок.
Гілка 1 запускає другий процес на паралельне виконання, гілка 2 запускає
третю і т.п. Але оскільки всі процеси з другого по останній є рівноправними,
то слід привести схему (8) до симетричної щодо цих процесів. Для того, щоб
зберегти правильність виконання наступних схем, введемо тимчасовий опе-
ратор TMP , що зупиняє виконання відповідної гілки, поки інші процеси не
почнуть його виконувати:
*)(*)(*)(([{*)1(*InitTemps{*)1( 1112 −−−
=
=== ∨ xxxx
s
x
ajRSik
ik
ττ
αα
∨)*)(*)(*} {* TMPSTX sxqx
jx
ττ
α
.}inc*}inc*)]*)(*)(*)(*} {*)(( 101 1
1
KITMPτRτSτTXaj ssq
jα
=∨
Перенесемо оператор )( xT τ на початок композиції операторів гілки.
Він змінює лише стан умов xτ і жодним чином не впливає на інші елементи
множини M . Крім того, оператори композиції, які не пов’язані із синхроні-
зацією, не впливають на істинність xτ , а TMP оперує з іншим набором син-
хронізуючих умов. Тому справедлива наступна схема:
*)(*)(*)(([{*)1(*InitTemps{*)1( 11
2
xxx
s
x
TRSik
ik
τττ
αα
−−
=
∨==
∨= − )*)(*} {*)(* 1 TMPSXaj sqxx x
jx
τ
α
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Системні дослідження та інформаційні технології, 2010, № 1 61
.}inc*}inc*)]*} {*)(*)(*)(*)((
1
1
011 KITMPXajRST qss
jα
τττ =∨ (9)
Отриманий механізм синхронізації ще не забезпечує необхідної зупин-
ки гілок виконання, яку надає оператор TMP . Із схеми бачимо, що певна
гілка почне виконання лише тоді, коли попередня досягне відповідного опе-
ратора T (це не стосується першого процесу). Як і раніше, серверний про-
цес запускає на виконання усі інші і чекає відгуку останнього. Процеси вво-
дять по ланцюгу: перший запускає другий, другий — третій тощо. Після
запуску відповідної гілки, остання скидає свою умову очікування. Це необ-
хідно для багаторазового використання такої моделі синхронізації. Проте,
для бажаного очікування гілок іншим даної схеми не достатньо. Так, якщо
виконання першої та другої гілок набагато випереджає третю, це призводить
до проходження другого процесу у новий цикл ітерації з можливим викори-
станням неправильних даних (позбавитись цього недоліку можна, подвоїв-
ши утворений складений оператор )**(** RSTTRS у тілі схеми). Введемо
оператор:
)(Sync αx — оператор синхронізації, α — вектор умов синхронізації.
Для схеми (9):
),(),(*)(*)(*)(*)(*)()(Sync 111 sssssx RSTRST τταττττττα =≡ при 1=x ;
),(),(*)(*)(*)(*)(*)()(Sync 11111 −−−−− =≡ xxxxxxxxx TRSTRS τταττττττα
— в іншому випадку.
Такий оператор абстрагується від конкретної схеми синхронізації. Те-
пер із схеми можна прибрати оператор TMP , після чого отримаємо:
*)(Sync([{*)1(*InitTemps{*)1(
1
α
αα
x
s
x
ik
ik
=
∨==
}inc*}inc*})] {*)(* 1 KIXaj
x
jx
qxx
α
−= . (10)
Схема є симетричною щодо будь-якої гілки. У загальному випадку
оператор Sync призводить до очікування відповідної гілки дії операторів
Sync інших гілок. На рис. 2 зображена часова діаграма виконання процесів
за схемою (10), що не враховує додаткові витрати часу, які зумовлені обме-
женістю апаратних та програмних ресурсів системи (наприклад, мала кіль-
кість процесорів, втрата часу на ініціалізацію об’єктів синхронізації в інфо-
рмаційній множині тощо).
Системи із спільною пам’яттю надають можливість використання тієї ж
самої ділянки пам’яті у всіх потоках (гілках обчислень). У даному випадку
оператори xInitDE надають змогу використовувати створений канал в x -
гілці, InitDE наразі створює канал обміну. Відповідно оператори DelDE ,
xDelDE призначені для знищення каналу обміну. Оператор xDE у цій мо-
делі є тотожним оператором, оскільки використання відповідного елемента
іншої гілки передбачає пряме звернення до нього. Щоб задовольнити озна-
чення асинхронної диз’юнкції, враховуємо те, що елемент іншої гілки вико-
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 62
ристовується тільки для читання. Тоді можна вважати, що процеси викорис-
товують не безпосередньо елементи інших гілок, а їхні копії, отримання
яких можливе за рахунок моделі спільної памяті.
Системи із розподіленою пам’яттю не надають можливості використо-
вувати прямий доступ до елементів. Вони вимагають передачі даних від од-
них процесів до інших. Оператори ініціювання каналу і його знищення збе-
рігають попередній зміст. Дія xDE залежить від x і може бути як
передачею даних у відповідні гілки, так і їх отриманням. Оператори InitDE
і DelDEможуть бути тотожними операторами (наприклад, при використан-
ні MPI [6]).
Узгоджено схему (10) із схемою використання обміну даними. Для цьо-
го розмістимо оператор InitDE перед усіма альфа-ітераціями, DelDE —
після усіх операторів, оскільки будь-яке інше розміщення буде призводити
до додаткових витрат часу при кожній ініціалізації і знищенні каналу.
xInitDE і xDelDE мають бути розташовані в паралельних гілках до та піс-
ля використання процесу обміну даними. Не слід розташовувати їх в альфа-
ітерації по j . Обмін даними xDE виконується до їх використання і може
розміщуватися як в циклічному процесі, так і поза ним ( від цього залежить
об’єм даних, що передаються. При розміщені xDE в циклі, відбувається
обмін малою кількістю даних (2 елементи на кожній ітерації)). Щоб уникну-
ти багаторазового обміну, слід винести xDE за межі альфа-ітерації. Введені
оператори впливають лише на стан нововведених об’єктів — каналу та бу-
ферів. Отримуємо:
*DE*)(Sync*InitDE([{*)1(*InitTemps{*)1(*InitDE
1 xxx
s
x
ik
ik α
αα =
∨==
DelDE*}inc *}inc*)]DelDE*} {*)(* 1 KIXaj xqxx x
jxα
−= .
5=s№ процесу
1
2
3
4
5
1t∆ 12 tt ∆∆ ≠
Час виконання однієї ітерації по i
t
Рис. 2. Часова діаграма схеми (10)
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Системні дослідження та інформаційні технології, 2010, № 1 63
Виконаємо оптимізацію за індексом i аналогічно:
IXajY xqxxxxx
s
xM x
jx
inc*)]DelDE*} {*)(*DE*)(Sync*InitDE([ 11 α
α −
=
=≡ ∨ .
Як і для j , розіб’ємо відрізок ],1[ n значень індексу на p інтервалів, що
не перетинаються:
1,1,],1[,],1[),,[ 01 +==∪∈∪∈∈≡ − nbbNnbNpxbbi pxxxixα .
Перейдемо до схеми (11) із синхронною диз’юнкцією, використавши
співвідношення САА-М: .*}{*}{}{ 12
2121
αα
αααα
AAA ∨=
∧
∨==
+
−
=
∨ )*}{ ([*)1(*InitTemps{*)1(*InitDE
1
1
1 xx
ixk
il
p
x
Yik α
αα
DelDE*}inc* }]{ KY
p
ip
l
α
∨ . (11)
У схемі (11) pp lllll ,,...,,, 1321 − — позначення підмножин виконання
оператора Y .
Рис. 3 ілюструє виконання схеми (11) для відповідних значень ps, .
Паралельні процеси (стрілки на рис. 3) є гілками, що були утворені при оп-
тимізації за індексом j . Їхня структура у збільшеному вигляді показана на
рис. 2. Ресурс i — спільний для усіх гілок.
При формуванні формули (8) вигляд X не був конкретизований. Тому
цю послідовність міркувань можна використати щодо оператора Y . Слід
№ процесу
1 2 3
t
Відповідає процесу 1i
Крок ітерації по k
2,5,3 321 ==== sssp
Рис. 3. Часова діаграма виконання схеми (11)
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 64
ввести набір індексів pp iiiii ,, ,...,, 1321 − замість одного індексу і аналогічно
змінити відповідні оператори, умови, множини.
Крім того, тимчасово вводиться новий набір умов синхронізації, циклів
очікування, контрольних точок і операторів скидання умов. Отже, отримує-
мо аналог формули (10):
*)1(*InitTemps{*)1(*InitDE == ik
kα
DelDE*}inc* })]{*)(*)(Sync [* 11
( KYbi
x
ix
lxx
i
x
p
x α
α −
=
=∨ . (12)
У схемі (12) введено набір нових операторів синхронізації, які за своєю
дією аналогічні попереднім, проте можуть бути реалізовані по-іншому (про
що свідчить верхній індекс у цих операторах). На відміну від схеми (10),
формула не потребує введення операторів обміну, оскільки останні присутні
в .Y
Схема (12), після розкриття складної дії Y , перетвориться на схему (13):
*)(*)(Sync [*)1(*InitTemps{*)1(*InitDE 11
( −
=
=== ∨ yy
i
y
p
y
biik
k
α
α
*)(*DE*)(Sync*InitDE([{* ,1,,,,1 yxyxyxyxyx
s
x
aj
iy
−
=
=∨ α
α
DelDE*}inc* })]inc*)]DelDE*} {* , KIX yyxqxy
jxyα
. (13)
Оператори у внутрішніх гілках асинхронної диз’юнкції набувають до-
даткового індексу, що з’явився за рахунок розбиття по .i Цей факт свідчить,
що для кожного зовнішнього процесу ( y -процесу) може існувати власні
синхронізація, оператори обміну даними і своє розбиття за індексом j : на-
бір індексів j , введених до інформаційної множини ( yxj , ). Отже, кількість
можливих варіантів розбиття за індексом j у схемі дорівнює кількості об-
ластей розбиття розмірності i . Оператор X для кожного x , y має однако-
ву реалізацію, проте виконуються на різних підмножинах інформаційної
множини. Справедлива наступна САА-тотожність [1, с. 143]:
=∆∆∨∆∆ )}(*)(*)(*)(*{ 1221 STBSTA
α
)}(*)(*{)}(*)(*{ 1221 ∆∆∨∆∆= STBSTA
αα
, (14)
де 21,∆∆ — локально замкнуті в ітераціях умови.
Введена вище формула (14) враховує скидання (окрім останньої ітера-
ції) умов 21,∆∆ після дії відповідних операторів очікування. Поведінка
отриманих в роботі схем дещо відрізняється від класичних за рахунок наяв-
ності R — оператора скидання умов. Це одночасно надає можливість прак-
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Системні дослідження та інформаційні технології, 2010, № 1 65
тичного використання схем в багатьох системах, оскільки дії S і R у пев-
них випадках можна об’єднати. Тому використаємо формулу (14) з ураху-
ванням більш загальної моделі синхронізації. При винесенні диз’юнкції за
межі ітерації слід враховувати збільшення кількості ітераторів в інформа-
ційній множині. Кожна гілка x містить підгілку y , що має власний індекс
yxi , . Як і для випадку утворення ітераторів j , має місце модифікування від-
повідних умов альфа-ітерацій і операторів інкремента:
)}(Sync*{)}(Sync*{)}(Sync*)(Sync*{ 2121 αααα
ααα
BABA ∨=∨ .
*)(*)(Sync [[*)1(*InitTemps{*)1(*InitDE 1
11
( −
==
=== ∨∨ yy
i
y
s
x
p
y
biik
k
α
α
*)(*DE*)(Sync*InitDE{* ,1,,,, yxyxyxyxyx aj
iy
−=α
α
DelDE*}inc* ]})]inc**} {* ,, KIX xyyxqxy
jxyα
. (15)
Остання схема (15) включає також у гілки x -диз’юнкції оператори
синхронізації та ініціалізації, що отримують при цьому інший індекс. Для
синхронізації це означає лише те , що її модель залежить від конкретної ро-
бочої гілки, яких тепер psss +++ ...21 (всі процеси рівноправні).
У формулі (15) гілка зупиняється двічі: вперше — після моменту ство-
рення на новому кроці за індексом k ; вдруге — при кожному вході в цикл
за індексом i . Остання зупинка є надлишковою, оскільки алгоритм вимагає,
щоб процеси входили синхронно лише в кожну нову ітерацію за k . Тому,
позбавившись від операторів )(Sync , αyx , досягнемо покращення часових
параметрів алгоритму, оскільки час на створення надлишкових елементів
синхронізації буде дорівнювати нулю:
*)(*)(Sync ([[*InitTemps{*)1(*InitDE ,1,,
11
xyxy
i
xy
s
x
p
y
bik
y
k
−
==
== ∨∨ α
α
*} {*)(**InitDE{* ,1,,, xy
jxyiyx
qyxyxyxyx XajDE
αα
−=
DelDE*}inc* })]]inc*DelDE* ,, KI xyyx .
Витрати часу виникають за рахунок постійної ініціалізації каналу
зв’язку за входження гілки в цикл за локальним індексом .i Це питання ви-
рішується винесенням операторів ініціалізації і знищення каналу за межі
циклу. Власне оператор обміну DE може бути теж винесений за альфа-
ітерацію, але він тоді набуває іншого змісту. DE обмінюється вже не окре-
мими векторами, а цілими матрицями даних:
*)(*)(Sync ([[*InitTemps{*)1(*InitDE ,1,,
11
xyxy
i
xy
s
x
p
y
bik
y
k
−
==
== ∨∨ α
α
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 66
*}inc*} {*)({**InitDE* ,,1,,, xyqyxyxyxyx IXajDE
xy
jxyiyx αα
−=
DelDE*}inc* )]]DelDE* , Kyx . (16)
Наступним кроком пришвидшення алгоритму є внесення оператора
ініціалізації тимчасових даних і альфа-ітерації по k до асинхронних
диз’юнкцій. Це призводиить до розширення інформаційної множини відпо-
відним набором індексів yxk , і проміжних змінних алгоритму. Кожна гілка
тепер матиме повний власний набір ресурсів і дані передаються лише за ра-
хунок операторів обміну. Саме таку схему можна реалізувати в системах із
розподіленою пам’яттю (попередні схеми мали неявний спільний ресурс —
параметр циклу k і тимчасові змінні):
*)(*)(Sync*InitTemps{ *)1(([[*DEInit ,1,,
11
xyxy
i
xy
s
x
p
y
bik
k
y
−
==
==∨∨ α
α
*}inc*} {*)({*DE*InitDE* ,,1,,, xyqyxyxyxyx IXaj
xy
jxyiyx αα
−=
DelDE* )]]}inc*DelDE* , Kyx .
Останній крок до створення остаточної ПРС алгоритму — використан-
ня тотожності: 43214321 )()( AAAAAAAA ∨∨∨=∨∨∨ .
Тоді маємо:
*)(*)(Sync*InitTemps{ *)1(([*InitDE ,1,,11 xyxy
i
xy
s
x
p
y
bik
k
y
−
==
==∨∨ α
α
**}inc*} {*)({*DE*InitDE* ,,1,,, xyqyxyxyxyx IXaj
xy
jxyiyx αα
−=
DelDE* )]}inc*DelDE , Kyx (17)
Для систем із розподіленою пам’яттю InitDE , DelDE можуть бути
«одиничними» операторами (наприклад, MPI). Для систем із спільною
пам’яттю ці оператори створюють необхідну область пам’яті спільного ко-
ристування.
Часова діаграма роботи алгоритму зображена на рис. 4. Аналіз схеми
(17) свідчить, що немає сенсу утворювати процеси із суттєво різним наван-
таженням. За наявності такої конфігурації час виконання алгоритму визна-
чатиметься часом обробки цими гілками великих масивів даних. Проте, ін-
коли цей випадок використовують для фонового виконання операцій. Тобто,
гілки з низьким навантаженням можуть виконувати не основний алгоритм, а
певні інші дії (підготовка даних для обміну, тощо).
Процес оптимізації зводиться нанівець при розбитті основної матриці
D таким чином, що існуватиме одна велика сукупність даних для одної гіл-
ки і малі набори для інших.
Формування узагальнених паралельних схем алгоритму Флойда-Уоршала
Системні дослідження та інформаційні технології, 2010, № 1 67
Рівномірного розподілу навантаження можна досягти через схеми роз-
биття, зображені на рис. 5 ( nproces — це кількість процесів).
Ці розбиття можуть містити процеси з меншим навантаженням, порів-
няно з іншими гілками. Але кількість даних у них буде близька до кількості
даних у інших. Тому ці схеми найкраще збалансовані [7].
ВИСНОВКИ
У роботі з використанням математичного апарату САА-М виконано форма-
лізацію алгоритму Флойда-Уоршала. Покроково створено низку схем цього
алгоритму (від послідовної до паралельних); розглянуто їх особливості і
можливі проблеми експериментальної реалізації. Використання САА-М
В.М. Глушкова надає можливість формалізувати паралельну схему алгорит-
му, не прив’язуючись до архітектури конкретної системи, на якій вона ви-
конуватиметься. Саме тому створена ПРС є загальним випадком як для
№ процесу
1 2 3
t
Процес з координатами ),( yx
Крок ітерації по k
...
Очікування за
рахунок синхронізації
Рис. 4. Часова діаграма роботи ПРС алгоритму (17)
nprocess
n
nprocess
n
Рис. 5. Схема розбиття вхідного масиву
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, Д.Ю. Вітель
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 68
архітектури систем зі спільною пам’яттю, так і з розподіленою. Експериме-
нтальна реалізація схеми (17) вимагає конкретизації взаємодії між гілками.
Перетворення САА-схем — потужний механізм оптимізації паралель-
них алгоритмів, який вимагає врахування специфіки поставленої задачі.
Схема (17) теоретично дає пришвидшення алгоритму в ∑
=
p
y
ys
1
разів, але при
експериментальній реалізації останнє обмежується фізичними характерис-
тиками системи (кількістю вузлів обчислення, швидкістю обміну даними
між ними та витратами часу на створення об’єктів синхронізації).
ЛІТЕРАТУРА
1. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П., Терзян Т.К. Многоуровневое струк-
турное проектирование программ. — М.: Финансы и статистика, 1989. —
192 с.
2. Погорілий С.Д., Камардіна О.О. Дослідження та створення інструментальних
засобів автоматизованої трансформації схем алгоритмів // Проблемы про-
граммирования. — 2004. — № 1–2. —С. 417–421.
3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, построение и анализ. — М.:
МЦНМО, 2000. — С. 719–725.
4. Столлингс В. Современные компьютерные сети. — СПб.: Питер, 2003. —
С. 479–486.
5. Захаров В.А. Курс лекцій: розподілені алгоритми. — http://mathcyb.cs.msu.su/
courses/distr_alg.html.
6. Богачев К.Ю. Основы параллельного программирования. — М.: БИНОМ.
Лаборатория знаний, 2003. — С. 232–292.
7. Погорілий С.Д., Камардіна О.О., Бавикін О.І. Про підхід до розпаралелювання
алгоритму Флойда-Уоршала // Математичні машини і системи. — 2005. —
Вып. 3. — С. 91–101.
Поступила 01.06.2009
|