Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю
Виконано формалізацію алгоритму Данцига пошуку найкоротших шляхів у зв’язному орієнтованому графі з використанням математичного апарата модифікованих систем алгоритмічних алгебр В.М. Глушкова. Запропоновано концепції розпаралелювання для архітектур зі спільною пам’яттю, що ґрунтуються на мінімізації...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2009
|
| Назва видання: | Математичні машини і системи |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/47308 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю / С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, О.А. Верещинський // Мат. машини і системи. — 2009. — № 4. — С. 27-37. — Бібліогр.: 9 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-47308 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-473082013-07-12T03:06:13Z Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю Погорілий, С.Д. Мар’яновський, В.А. Бойко, Ю.В. Верещинський, О.А. Обчислювальні системи Виконано формалізацію алгоритму Данцига пошуку найкоротших шляхів у зв’язному орієнтованому графі з використанням математичного апарата модифікованих систем алгоритмічних алгебр В.М. Глушкова. Запропоновано концепції розпаралелювання для архітектур зі спільною пам’яттю, що ґрунтуються на мінімізації витрат на синхронізацію та паралельну обробку даних. Проведено трансформацію алгоритму, отримано набір паралельних схем та виконано їх порівняльний аналіз. Выполнена формализация алгоритма Данцига поиска кратчайших путей в связном ориентированном графе с использованием математического аппарата модифицированных систем алгоритмических алгебр В.М. Глушкова. Предложены концепции распараллеливания для архитектур с общей памятью, которые основаны на минимизации потерь на синхронизацию и параллельную обработку данных. Проведена трансформация алгоритма, получен набор параллельных схем и выполнен их сравнительный анализ. Formalization of Dantzig algorithm for the shortest ways search in connected oriented graph using mathematical means of V.M. Glushkov modified systems of algorithmic algebras is performed. Conceptions of paralleling for architectures with shared memory, which are based on minimization of loss on synchronization and parallel data proceeding are proposed. Transformation of algorithm is performed, set of parallel schemes are obtained and their comparative analysis is performed. 2009 Article Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю / С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, О.А. Верещинський // Мат. машини і системи. — 2009. — № 4. — С. 27-37. — Бібліогр.: 9 назв. — укр. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/47308 681.3 uk Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Обчислювальні системи Обчислювальні системи |
| spellingShingle |
Обчислювальні системи Обчислювальні системи Погорілий, С.Д. Мар’яновський, В.А. Бойко, Ю.В. Верещинський, О.А. Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю Математичні машини і системи |
| description |
Виконано формалізацію алгоритму Данцига пошуку найкоротших шляхів у зв’язному орієнтованому графі з використанням математичного апарата модифікованих систем алгоритмічних алгебр В.М. Глушкова. Запропоновано концепції розпаралелювання для архітектур зі спільною пам’яттю, що ґрунтуються на мінімізації витрат на синхронізацію та паралельну обробку даних. Проведено трансформацію алгоритму, отримано набір паралельних схем та виконано їх порівняльний аналіз. |
| format |
Article |
| author |
Погорілий, С.Д. Мар’яновський, В.А. Бойко, Ю.В. Верещинський, О.А. |
| author_facet |
Погорілий, С.Д. Мар’яновський, В.А. Бойко, Ю.В. Верещинський, О.А. |
| author_sort |
Погорілий, С.Д. |
| title |
Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю |
| title_short |
Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю |
| title_full |
Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю |
| title_fullStr |
Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю |
| title_full_unstemmed |
Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю |
| title_sort |
дослідження паралельних схем алгоритму данцига для обчислювальних систем зі спільною пам’яттю |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2009 |
| topic_facet |
Обчислювальні системи |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/47308 |
| citation_txt |
Дослідження паралельних схем алгоритму Данцига для обчислювальних систем зі спільною пам’яттю / С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко, О.А. Верещинський // Мат. машини і системи. — 2009. — № 4. — С. 27-37. — Бібліогр.: 9 назв. — укр. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT pogorílijsd doslídžennâparalelʹnihshemalgoritmudancigadlâobčislûvalʹnihsistemzíspílʹnoûpamâttû AT marânovsʹkijva doslídžennâparalelʹnihshemalgoritmudancigadlâobčislûvalʹnihsistemzíspílʹnoûpamâttû AT bojkoûv doslídžennâparalelʹnihshemalgoritmudancigadlâobčislûvalʹnihsistemzíspílʹnoûpamâttû AT vereŝinsʹkijoa doslídžennâparalelʹnihshemalgoritmudancigadlâobčislûvalʹnihsistemzíspílʹnoûpamâttû |
| first_indexed |
2025-07-04T07:04:55Z |
| last_indexed |
2025-07-04T07:04:55Z |
| _version_ |
1836699035309703168 |
| fulltext |
© Погорілий С.Д., Мар’яновський В.А., Бойко Ю.В., Верещинський О.А., 2009 27
ISSN 1028-9763. Математичні машини і системи, 2009, № 4
УДК 681.3
С.Д. ПОГОРІЛИЙ, В.А. МАР’ЯНОВСЬКИЙ, Ю.В. БОЙКО, О.А. ВЕРЕЩИНСЬКИЙ
ДОСЛІДЖЕННЯ ПАРАЛЕЛЬНИХ СХЕМ АЛГОРИТМУ ДАНЦИГА ДЛЯ
ОБЧИСЛЮВАЛЬНИХ СИСТЕМ ЗІ СПІЛЬНОЮ ПАМ’ЯТТЮ
Abstract: Formalization of Dantzig algorithm for the shortest ways search in connected oriented graph using
mathematical means of V.M. Glushkov modified systems of algorithmic algebras is performed. Conceptions of
paralleling for architectures with shared memory, which are based on minimization of loss on synchronization and
parallel data proceeding are proposed. Transformation of algorithm is performed, set of parallel schemes are obtained
and their comparative analysis is performed.
Key words: routing, Dantzig algorithm, modified systems of algorithmic algebras, parallel regular scheme, paralleling.
Анотація: Виконано формалізацію алгоритму Данцига пошуку найкоротших шляхів у зв’язному
орієнтованому графі з використанням математичного апарата модифікованих систем алгоритмічних
алгебр В.М. Глушкова. Запропоновано концепції розпаралелювання для архітектур зі спільною пам’яттю,
що ґрунтуються на мінімізації витрат на синхронізацію та паралельну обробку даних. Проведено
трансформацію алгоритму, отримано набір паралельних схем та виконано їх порівняльний аналіз.
Ключові слова: маршрутизація, алгоритм Данцига, системи алгоритмічних алгебр, паралельна регулярна
схема алгоритму, розпаралелювання.
Аннотация: Выполнена формализация алгоритма Данцига поиска кратчайших путей в связном
ориентированном графе с использованием математического аппарата модифицированных систем
алгоритмических алгебр В.М. Глушкова. Предложены концепции распараллеливания для архитектур с
общей памятью, которые основаны на минимизации потерь на синхронизацию и параллельную обработку
данных. Проведена трансформация алгоритма, получен набор параллельных схем и выполнен их
сравнительный анализ.
Ключевые слова: маршрутизация, алгоритм Данцига, системы алгоритмических алгебр, параллельная
регулярная схема алгоритма, распараллеливание.
1. Вступ
Однією із найважливіших і найактуальніших у сьогоденні областей застосування задачі пошуку
найкоротших шляхів у ґрафах є маршрутизація пакетів у комп’ютерних мережах. Деякі з перших
INTERNET-протоколів маршрутизації, наприклад, RIP (Routing Information Protocol) [1],
використовували так званий вектор відстаней. Така схема роботи гарантувала збіжність оцінених
маршрутизаторами відстаней до істинних по проходженні певного часу, надаючи, таким чином,
інформацію про найкращі шляхи. Для подолання певних проблем, пов’язаних з цим алгоритмом,
була розроблена маршрутизація з урахуванням станів каналів зв’язку (Link-State Routing). При такій
маршрутизації кожен маршрутизатор підтримує інформацію про ґрафове представлення топології
всієї мережі і обчислює свою таблицю маршрутизації, використовуючи алгоритм пошуку всіх
найкоротших шляхів у ґрафі. Недоліком такого підходу є додаткові витрати пам’яті та часу на
обчислення, але, не зважаючи на це, такий вид маршрутизації визнано ефективним і
формалізовано у вигляді протоколу маршрутизації з визначенням найкоротшого маршруту (Open
Shortiest Path First protocol, OSPF) [1].
Стрімке зростання досліджень у галузі комп’ютерних мереж, виникнення нових архітектур
сучасних мікропроцесорів дозволяють розв’язати задачу маршрутизації на якісно новому рівні. У
статті формуються паралельні схеми алгоритму Данцига для застосування у маршрутизаторах
нового покоління.
2. Системи зі спільною пам’яттю
Багатопроцесорні та багатоядерні системи на сьогоднішній день належать до класу систем, здатних
обробляти великі обсяги інформації в режимі реального масштабу часу. Одним із можливих
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 28
варіантів архітектури є системи зі спільною пам’яттю (Symetric Multiprocessing, SMP) [2]. Основна
ідея такої архітектури полягає у наявності спільної ділянки пам’яті для кількох процесорів. Вона
використовується для обміну інформацією, і всі процесори здійснюють однакову адресацію для всіх
комірок пам’яті. Саме тому така система називається симетричною.
Однією із найбільших переваг SMP є простота та універсальність у програмуванні. Звичайно
використовують модель кількох паралельних гілок (проте, зауважимо, ніщо не заважає організувати
міжпроцесорний обмін даними). Створюючи процеси (потоки) і плануючи їх роботу, можна досягти
значного виграшу в часі роботи. Уся підсистема працює під керуванням єдиної операційної системи.
Зокрема, у Windows підтримка SMP забезпечується, починаючи з версії NT 4.0 [3].
Типовим прикладом SMP є сучасні багатоядерні процесори фірми Intel (Core Duo, Core 2
Duo, Core 2 Quad тощо). Використання цих процесорів в універсальних обчислювальних системах,
де ступінь розпаралелювання є невеликим, дозволяє одержати суттєве підвищення коефіцієнта
продуктивності.
Таким чином, використання систем SMP дозволяє значно оптимізувати виконання
обчислень, що дозволяє успішно використовувати їх для розв’язку задач маршрутизації, особливо
при великих навантаженнях на локальні маршрутизатори.
3. Алгоритм Данцига
Опис алгоритму. Одним із найефективніших методів пошуку всіх найкоротших шляхів у зваженому
орієнтованому ґрафі є алгоритм Данцига [4, 5].
Розглянемо схему роботи алгоритму. Ідея полягає в послідовному обчисленні за допомогою
рекурентної процедури підматриць найкоротших шляхів mD зростаючої розмірності mm× . Кожна
така матриця, фактично, є матрицею найкоротших шляхів підґрафа з вершинами від 0 до 1−m .
Введемо низку позначень:
N – розмірність ґрафа, який відзеркалює топологію мережі; (1)
}..{ ki – множина цілих чисел від i до k ;
ijg – довжина ребра з вершини i в j ;
ijd – довжина найкоротшого знайденого шляху з i в j ;
m
ijd – шлях з вершини i до j через вершину m ;
),( jiisEdge – предикат, значенням якого буде істина, якщо існує ребро з вершини i в j ;
),( jiisWay – предикат, значенням якого буде істина, якщо існує шлях з вершини i в j ;
),( jiedgeNum – кількість ребер на шляху з i в j ;
),,( mjisetWay – встановлення шляху m
ijd .
Кожну ітерацію алгоритму можна розділити на три послідовні кроки:
1. Пошук найкоротших шляхів з вершини m до mj <<<< .
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 29
Шлях можна розбити на дві частини: від m до деякої проміжної вершини i )( mig та від i до j
)( ijd .
Тоді
{ }
( )ijmi
mi
mj dgd +=
−∈ 1,0
min . (2)
2. Пошук найкоротших шляхів з вершин mi <<<< до m .
Шлях можна розбити на дві частини: від i до деякої проміжної вершини j )( ijd та від j до m
)( jmg .
Тоді
{ }
( )jmij
mj
im gdd +=
−∈ 1,0
min . (3)
3. Пошук найкоротших шляхів з вершин mi <<<< до mj <<<< з урахуванням наявності нової вершини
m .
Шлях можна розбити на дві частини: від i до вершини m )( imd та від m до j )( mjd .
Тоді
( )ijmjimim dddd ,min += . (4)
Останній крок рекурентної процедури дає матрицю ND , яка, власне, і буде матрицею
найкоротших шляхів ґрафа.
Послідовна схема алгоритму. Формалізуємо алгоритм Данцига шляхом формування
схеми з використанням апарату систем алгоритмічних алгебр Глушкова(САА) [6–8].
Використовуючи позначення (1), сформуємо ряд кон’юнктивних умов для скорочення запису
формули алгоритму:
( ) ( ) ),(,,,1 jiisWayimisEdgejim ∧=α , (5а)
( ) ( ) ),(,,,2 jiisWaymjisEdgejim ∧=α , (5б)
( ) ( ) ),(,,,3 jmisWaymiisWayjim ∧=α . (5в)
Умови 1α , 2α , 3α вказують на існування відповідно шляхів i
mjd , j
imd , m
ijd .
Використовуючи (5), запишемо умови оптимальності шляхів i
mjd , j
imd , m
ijd на відповідному
кроці ітераційного процесу:
( )( ) ( )
( ), )),(1),(()(
,1
jmedgeNumjiedgeNumddg
ddgjmisWay
mjijmi
mjijmi
<+∧=+∨
∨<+∨=β
(6а)
( )( ) ( )
( ), )),(1),(()(
,2
miedgeNumjiedgeNumddg
ddgmiisWay
miijjm
miijjm
<+∧=+∨
∨<+∨=β
(6б)
( )( ) ( )
( ). )),(),(),(()(
,3
jiedgeNumjmedgeNummiedgeNumddd
dddjiisWay
ijmjim
ijmjim
<+∧=+∨
∨<+∨=β
(6в)
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 30
Під оптимальністю розуміється менша загальна довжина шляху або, якщо довжини
порівнюваних шляхів рівні, менша кількість ребер, які необхідно пройти.
Оперуючи умовами (5) та (6), запишемо кожен з кроків алгоритму у вигляді формули:
1.
{ } { }
)}()}())),,((({{)(
11..1..1
jiEEjimsetWaymSubDanc1
mimj
++×++×∨∨=
∉∉ βα
. (7а)
2.
{ } { }
)}()}())),,((({{)(
22..1..1
ijEEjmisetWaymSubDanc2
mjmi
++×++×∨∨=
∉∉ βα
. (7б)
3.
{ } { }
)}()}())),,((({{)(
33..1..1
ijEEmjisetWaymSubDanc3
mjmi
++×++×∨∨=
∉∉ βα
, (7в)
де операція )(++ означає інкрементацію змінної на одиницю.
Використовуючи позначення, можна сформувати послідовну регулярну схему(ПРС)
алгоритму Данциґа:
)}()()()(1{ mmSubDanc3mSubDanc2mSubDancDancig
Nm
++×××=
>
. (8)
Принцип обробки даних. У роботі виконується парадигма розпаралелювання алгоритму за
даними, тобто кожен потік обробляє певну частину інформаційної множини, не перетинаючись на
цьому етапі з іншими робочими потоками. Таким чином, для подальшої роботи необхідно
сформулювати деякі засади роботи алгоритму із даними, розміщеними в пам’яті.
Інформація про ґраф зберігається у вигляді двох матриць. Перша з них – матриця
суміжностей ґрафа. Вона являє собою набір вхідних даних для алгоритму і є незмінною до кінця
його роботи (доступ лише на читання). Друга матриця – матриця маршрутів. У комірці з
координатами ( )j,i зберігається номер вершини, до якої необхідно перейти після i -ої на шляху до
j . Таким чином, шлях розбивається на 2 частини: з i до деякої проміжної вершини k та з k до j .
Якщо jk = , необхідно пройти просто по відповідному ребру між вершинами. За допомогою цієї
матриці в динамічному режимі розраховуються довжини найкоротших шляхів між довільними
парами вершин. В остаточному варіанті одержана матриця і є результатом роботи алгоритму.
Як зазначено, алгоритм Данцига можна розбити на три незалежні кроки:
1. Пошук найкоротшого шляху i
mjd .
2. Пошук найкоротшого шляху j
imd .
3. Пошук найкоротшого шляху m
ijd .
Важливо відзначити, що крок 3 може бути виконаний лише після повного завершення двох
попередніх. Перші два етапи схематично зображені на рис. 1а та рис. 1б. Як бачимо, для обрахунку
кожного нового елемента i
mjd )( j
imd слід опрацювати цілий стовпчик (рядок) підматриці mD
(стрілками позначено дані, які слід прочитати для знаходження відповідного елемента). Отже, при
плануванні роботи кількох потоків оптимальним буде саме таке розбиття вхідних даних, що
дозволить уникнути зайвого обміну інформацією між потоками, а також зменшити затрати на
синхронізацію.
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 31
а)
б)
Рис. 1. Обробка даних на перших двох етапах алгоритму
Далі пропонується така схема роботи.
Нехай маємо 2 N робочих потоків. На першому етапі роботи вони рівномірно поділяють
матрицю на рядки (рис. 2а), а на другому – на стовпчики (рис. 2б). При цьому області даних, що
обробляються різними потоками, не перекриваються навіть при читанні, що теж може дещо
уповільнити роботу алгоритму.
а) б)
Рис. 2. Схема роботи алгоритму на перших двох етапах
Другий крок виконується лише після повного завершення першого, що змушує вводити
додаткову точку синхронізації. Для усунення цього доцільно дещо вдосконалити схему, зображену
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 32
на рис. 2. Розіб’ємо робочі потоки на 2 групи по N потоків. При цьому перша група виконує крок 1,
а друга, відповідно, крок 2. При цьому кількість інформації, яка припадає на один потік, зростає
(рис. 3).
На третьому кроці, на кожній ітерації циклу,
порівнюються лише 2 елементи матриці. Тому в даному
випадку розбиття може бути майже довільним, наприклад,
на квадратні підматриці.
Але для уникнення затримок, внаслідок
одночасного доступу різних потоків до одних і тих же
даних, оптимальним буде розбиття на рядки, як показано
на рис. 2а.
4. Формування паралельної схеми алгоритму Данцига
Розбиття матриці даних. Введемо деякі нові
поняття, які знадобляться при реалізації
розпаралелювання алгоритму.
Нехай потрібно розділити матрицю mm× на N
приблизно рівних частин прямокутної форми, як зображено на
рис. 4 [9].
ib позначає перший рядок i -ї частини, а ie – останній. Їх
можна обчислити за такими співвідношеннями:
] [ 1/)1(, +×−= Nmib Nm
i , (9)
] [Nmie Nm
i /, ×= . (10)
Таким чином, отримано межі областей, які визначатимуть
область пам’яті, що оброблятиметься одним із паралельних
потоків (зрозуміло, в аналогічний спосіб можна розбити
стовпчики матрицю на стовпчики).
Синхронізація потоків. Введемо узагальнену точку синхронізації кількох паралельних
потоків – фактично, бар’єр який затримує виконання потоків, поки їх не набереться достатня
кількість. Такий об’єкт можна представити формулою
×=××××××= ∏
≠
=
+−
N
ij
j
jiNiiiN STSSSSTiB
1
111 )()()(...)()(...)()()( λλλλλλλ , (11)
де )(λT – контрольна точка;
)(λS – точка синхронізації (може інтерпретуватися як порожній цикл);
N – кількість потоків;
i – номер потока, який синхронізується.
Рис. 3. Альтернативна схема роботи
Рис. 4. Розбиття матриці даних
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 33
Таким чином, кожен потік для
проходження бар’єра повинен
подолати ( )1−N точку синхронізації,
перед цим попередньо розблокувавши
свою власну. Схематично роботу
бар’єра зображено на рис. 5. Коли
будь-який з потоків потрапляє у бар’єр,
він не зможе подолати його, поки кожен
з решти потоків не розблокує власну
контрольну точку.
Рис. 5. Внутрішня організація бар’єра
Еквівалентні перетворення схеми алгоритму. Застосуємо апарат тотожніх перетворень
САА-М до схеми (8) [8].
Спочатку розв’яжемо деяку узагальнену задачу. Нехай маємо α-ітерацію (вважатимемо, що
на початку ітераційного процесу змінна i ініціалізується одиницею, а на кожному кроці циклу неявно
інкрементується на одиницю):
}{
}..1{
AI
Ni∉
= , (12)
де оператор A опрацьовує деяку частину вхідних даних. Введемо позначення:
}..{ ,, Nk
j
Nk
jj ebi ∉=γ , (13)
j
k
j
Ni γγ
1
}..1{
=
∧=∉= .
Таким чином, ми розбили інтервал }..1{ N на k приблизно однакових частин. Внесемо
умову γ всередину ітерації у вигляді фільтра:
}...{}...{}{ 2121 AAAI kk ×∨∨∨=×∧∧∧== γγγγγγγ
γγγ
. (14)
Скористаємося властивістю фільтрації для локально замкнутих умов iγ для розділення
фільтра, після чого винесемо оператор диз’юнкції за ітераційні дужки:
=∨∨∨=×∨∨∨= ∨
=
}{}...{})...({
1
2121 AAAAAI l
k
l
kk γγγγγγγ
γγγ
. (15)
Оскільки в кожний довільний момент часу може бути виконана лише одна з умов типу
}..{ ,, Nk
j
Nk
j ebi ∈ , то можна сказати, що ji,∀ :
iijji γδγγ ∧=∧ . (16)
Як бачимо з (16), істинність будь-якої з умов iγ виключає можливість істинності будь-якої
jγ при ji ≠ , що фактично є умовою локальної замкнутості. Тому можемо замінити умову ітерації
для кожної з гілок на відповідний фільтр:
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 34
= ∨
=
}{
1
AI
l
k
l γ
. (17)
Таким чином, цикл було розбито на k паралельних гілок за допомогою синхронної
диз’юнкції. Зауважимо, що кожна гілка працює лише зі своєю частиною інформаційної множини,
недоступною для інших. За означенням це власне і є асинхронна диз’юнкція:
= ∨
=
}{
1
AI
l
k
l γɺ
. (18)
Введемо об’єкт для синхронізації гілок:
×=
×××××××=
∨∨∨
=
+−
==
)(}{))(..).()(...)()((}{}{
1
11
11
lBASSSSTAA N
k
l
lllll
k
l
k
l lll γγγ
λλλλλ ɺɺɺ . (19)
Формула (19) являє собою асинхронну α -ітерацію обробки даних, яка виконується N
гілками, які, у свою чергу, синхронізуються після виконання операцій. Застосуємо її до послідовної
регулярної схеми (8). Це дозволить розбити кожен із трьох внутрішніх циклів на паралельні гілки:
{ } { }
( ). )(),2,(
)()}()}())),,((({{)(
2
2
1
2
..1..
2
1 11
lBlNmPSub1
lBjiEEjimsetWaymSubDanc1
N
N
l
N
miebj
N
l ll
×=
=
×++×++×∨∨=
∨
∨
=
∉∉=
ɺ
ɺ βα
(20)
{ } { }
( ). )(),2,(
)()}()}())),,((({{)(
2
2
1
2
..1..
2
1 22
lBlNmPSub2
lBijEEjmisetWaymSubDanc2
N
N
l
N
mjebi
N
l ll
×=
=
×++×++×∨∨=
∨
∨
=
∉∉=
ɺ
ɺ βα
(21)
{ } { }
( ). )(),2,(
)()}()}())),,((({{)(
2
2
1
2
..1..
2
1 33
lBlNmPSub3
lBijEEmjisetWaymSubDanc3
N
N
l
N
mjebi
N
l ll
×=
=
×++×++×∨∨=
∨
∨
=
∉∉=
ɺ
ɺ βα
(22)
Підставляючи вирази (20), (21) та (22) у (8), отримаємо
( ) ( )
( ) . )}()(),2,(
)(),2,()(),2,({
2
2
1
2
2
1
2
2
1
mlBlNmPSub3
lBlNmPSub2lBlNmPSub1Dancig
N
N
l
N
N
l
N
N
lNm
++×
××
×
××
×=
∨
∨∨
=
==>
ɺ
ɺɺ
(23)
Отримана формула (23) – паралельна схема алгоритму Данцига, яка представлена на
рис. 3. Як бачимо, всередині зовнішньої α -ітерації для виконання кожного з трьох послідовних
кроків відбувається розщеплення на паралельні гілки. Для покращання ефективності доцільно
винести асинхронну диз’юнкцію за межі ітераційного процесу:
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 35
( )
. )}()(
),2,()(),2,()(),2,({)}(
)(),2,()(),2,()(),2,({
2
22
2
1
222
2
1
mlB
lNmPSub3lBlNmPSub2lBlNmPSub1m
lBlNmPSub3lBlNmPSub2lBlNmPSub1Dancig
N
NN
Nm
N
l
NNN
N
lNm
++××
×××××=++×
××××××=
>=
=>
∨
∨
ɺ
ɺ
(24)
Схеми (23) та (24) можна
інтерпретувати, як зображено на рис. 6а та
рис. 6б, де умовно зображено одну ітерацію
багатопоточної обробки даних для кожного
випадку.
Використаємо (23) для отримання
схеми, зображеної на рис. 4.
Поділимо робочі потоки на дві групи:
перша буде виконувати крок 1 алгоритму, а
друга – крок 2. Введемо умову ω , істинність
якої означає належність до першої групи,
хибність – до другої. Запишемо
модифіковану схему (23):
( ) ( )
( ) . )}()(),2,(
)(),,()(),,({
2
2
1
)2(
1
)1(
1
mlBlNmPSub3
lBlNmPSub2lBlNmPSub1Dancig
N
N
l
N
N
l
N
N
lNm
++×
××
×
××
×=
∨
∨∨
=
==>
ɺ
ɺɺ
(25)
Введемо фіктивні гілки для вирівнювання кількості потоків та зведемо перші два кроки до
спільної диз’юнкції:
( )
( ) . )}()(),2,(
))(),,(())(),,(({
)}()(),2,(
))(),,(())(),,(({
2
2
1
)2()1(
2
1
2
2
1
)2(
2
1
)1(
2
1
mlBlNmPSub3
ElBlNmPSub2ElBlNmPSub1
mlBlNmPSub3
ElBlNmPSub2ElBlNmPSub1Dancig
N
N
l
NN
N
lNm
N
N
l
N
N
l
N
N
lNm
++×
××
×
∨××∨×=
=++×
××
×
∨××
∨×=
∨
∨
∨
∨∨
=
=>
=
==>
ɺ
ɺ
ɺ
ɺɺ
ωω
ωω
(26)
Перейдемо від α -диз’юнкцій до фільтрів, а потім скористаємося умовою дистрибутивності
синхронної диз’юнкції:
а) б)
Рис. 6. Варіанти розпаралелювання алгоритму
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 36
( )
( )
( )
( ) )}.()(),2,(
))(),,()(),,(({
)}()(),2,(
))(),,(())(),,(({
2
2
1
)2()1(
2
1
2
2
1
)2()1(
2
1
mlBlNmPSub3
lBlNmPSub2lBlNmPSub1
mlBlNmPSub3
ElBlNmPSub2ElBlNmPSub1Dancig
N
N
l
NN
N
lNm
N
N
l
NN
N
lNm
++×
××
×
×∨×=
=++×
××
×
∨××∨×=
∨
∨
∨
∨
=
=>
=
=>
ɺ
ɺ
ɺ
ɺ
ωω
ωωωω
(27)
Замінимо фільтри знову на α -диз’юнкцію й об’єднаємо бар’єри )1(
NB та )1(
NB , а також
винесемо оператор асинхронної диз’юнкції:
( )( ) . )}()(),2,(
)()),,(),,(({
2
2
2
1
mlBlNmPSub3
lBlNmPSub2lNmPSub1Dancig
N
N
Nm
N
l
++×××
×
×∨=
>=
∨
ωɺ (28)
Отриману формулу (28) схематично зображено на рис. 7. Основною її перевагою є менша
кількість синхронізацій у порівнянні із (23) та (24), що
безперечно покращить ефективність роботи алгоритму.
5. Висновки
У статті проаналізовано підхід до розв’язку задачі
маршрутизації у комп’ютерних мережах, який ґрунтується
на алгоритмі Данцига. Виконано формалізацію алгоритму
з використанням математичного апарату САА-М і
отримано послідовну регулярну схему (8).
Сформовано концепцію розпаралелювання
алгоритму для систем зі спільною пам’яттю.
Проаналізовано два підходи: в першому випадку
зменшується навантаження на кожну з паралельних гілок,
а в другому за рахунок зростання навантаження значно зменшуються витрати на синхронізацію
гілок. Виконано трансформацію ПРС (8) за допомогою САА-М. Паралельні регулярні схеми (23), (24)
представляють перший варіант, а (28) – другий.
Використання математичного апарату САА-М В.М. Глушкова дозволяє зосередитись на
концепціях та методах трансформації паралельних схем алгоритмів, абстрагуючись від конкретних
деталей програмної реалізації. При цьому отримані схеми є теоретичною базою для створення
відповідного програмного забезпечення.
СПИСОК ЛІТЕРАТУРИ
1. Сик Дж., Ли Л., Ламсдэйн Э. С++ Boost Graph Library. Библиотека программиста / Пер. с англ. Р. Сузи. –
СПб.: Питер, 2006. – 304 с.
2. Лісовець В., Цегелик Г. Метод M-паралельного послідовного пошуку записів у файлах баз даних і його
ефективність // Вісник Львівського університету. Сер. прикл. матем. та інформ. – 2007. – Вип. 13. – С. 177 –
186.
Рис. 7. Остаточна схема
розпаралелювання
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 37
3. Джонсон М. Харт Системное программирование под Windows / Пер. с англ. – 3-е изд. – М.: Издательский
дом «Вильямс», 2005. – 592 с.
4. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981. – 324 с.
5. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: Центр непрерывного
математического образования, 2000. – 960 с.
6.Погорілий С.Д. Програмне конструювання: Підручник / За ред. О.В. Третяка. – 2-е вид. – К.: Видавничо-
поліграфічний центр «Київський університет», 2005. – 483 с.
7. Погорілий С.Д., Калита Д.М. Оптимізація алгоритмів маршрутизації з використанням систем алгоритмічних
алгебр // УсиМ. – 2000. – № 4. – С. 20 – 30.
8. Многоуровневое структурное проектирование программ. Теоретические основы, инструментарий /
Е.Л. Ющенко, Г.Е. Цейтлин, В.П. Грицай и др. – М.: Финансы и статистика, 1989. – 342 с.
9. Богачёв К.Ю. Основы параллельного программирования. – М.: БИНОМ. Лаборатория знаний, 2003. – 342 с.
Стаття надійшла до редакції 28.05.2009
|