Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю

Побудовано регулярну схему алгоритму Йена з використанням апарату систем алгоритмічних алгебр, запропоновано підходи до паралельної реалізації алгоритму Йена для SMP–архітектур. Виконано фор-малізацію методу шаблонів шляхом формування паралельних схем з використанням математичного апарату модифікова...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автори:	Погорілий, С.Д., Трибрат, М.І., Бойко, Ю.В., Афанасьєв, Д.В.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2011
Теми:	Паралельне програмування
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/50958
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю / С.Д. Погорілий, М.І. Трибрат, Ю.В. Бойко, Д.В. Афанасьєв // Пробл. програмув. — 2011. — № 2. — С. 12-22. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-50958
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-509582025-02-23T17:39:00Z Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю Погорілий, С.Д. Трибрат, М.І. Бойко, Ю.В. Афанасьєв, Д.В. Паралельне програмування Побудовано регулярну схему алгоритму Йена з використанням апарату систем алгоритмічних алгебр, запропоновано підходи до паралельної реалізації алгоритму Йена для SMP–архітектур. Виконано фор-малізацію методу шаблонів шляхом формування паралельних схем з використанням математичного апарату модифікованих систем алгоритмічних алгебр. Реалізовано паралельний алгоритм Йена, наве-дено отримані експериментальні дані. 2011 Article Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю / С.Д. Погорілий, М.І. Трибрат, Ю.В. Бойко, Д.В. Афанасьєв // Пробл. програмув. — 2011. — № 2. — С. 12-22. — Бібліогр.: 11 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/50958 004.3 uk application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Паралельне програмування Паралельне програмування
spellingShingle	Паралельне програмування Паралельне програмування Погорілий, С.Д. Трибрат, М.І. Бойко, Ю.В. Афанасьєв, Д.В. Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю
description	Побудовано регулярну схему алгоритму Йена з використанням апарату систем алгоритмічних алгебр, запропоновано підходи до паралельної реалізації алгоритму Йена для SMP–архітектур. Виконано фор-малізацію методу шаблонів шляхом формування паралельних схем з використанням математичного апарату модифікованих систем алгоритмічних алгебр. Реалізовано паралельний алгоритм Йена, наве-дено отримані експериментальні дані.
format	Article
author	Погорілий, С.Д. Трибрат, М.І. Бойко, Ю.В. Афанасьєв, Д.В.
author_facet	Погорілий, С.Д. Трибрат, М.І. Бойко, Ю.В. Афанасьєв, Д.В.
author_sort	Погорілий, С.Д.
title	Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю
title_short	Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю
title_full	Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю
title_fullStr	Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю
title_full_unstemmed	Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю
title_sort	підходи до паралелізації алгоритму йєна для систем із спільною пам’яттю
publisher	Інститут програмних систем НАН України
publishDate	2011
topic_facet	Паралельне програмування
url	https://nasplib.isofts.kiev.ua/handle/123456789/50958
citation_txt	Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю / С.Д. Погорілий, М.І. Трибрат, Ю.В. Бойко, Д.В. Афанасьєв // Пробл. програмув. — 2011. — № 2. — С. 12-22. — Бібліогр.: 11 назв. — укр.
work_keys_str_mv	AT pogorílijsd pídhodidoparalelízacííalgoritmujênadlâsistemízspílʹnoûpamâttû AT tribratmí pídhodidoparalelízacííalgoritmujênadlâsistemízspílʹnoûpamâttû AT bojkoûv pídhodidoparalelízacííalgoritmujênadlâsistemízspílʹnoûpamâttû AT afanasʹêvdv pídhodidoparalelízacííalgoritmujênadlâsistemízspílʹnoûpamâttû
first_indexed	2025-11-24T05:36:08Z
last_indexed	2025-11-24T05:36:08Z
_version_	1849648814213824512
fulltext	Паралельне програмування 12 )( 3KnΟ ),( RXG УДК 004.3 С.Д. Погорілий, М.І. Трибрат, Ю.В. Бойко, Д.В. Афанасьєв ПІДХОДИ ДО ПАРАЛЕЛІЗАЦІЇ АЛГОРИТМУ ЙЕНА ДЛЯ СИСТЕМ ІЗ СПІЛЬНОЮ ПАМ’ЯТТЮ Побудовано регулярну схему алгоритму Йена з використанням апарату систем алгоритмічних алгебр, запропоновано підходи до паралельної реалізації алгоритму Йена для SMP–архітектур. Виконано фор- малізацію методу шаблонів шляхом формування паралельних схем з використанням математичного апарату модифікованих систем алгоритмічних алгебр. Реалізовано паралельний алгоритм Йена, наве- дено отримані експериментальні дані. Вступ Типові розв’язки задачі знаходжен- ня найкоротшого шляху в теорії графів до- зволяють отримати один шлях для пари вершин заданого графу. Практичні засто- сування вимагають накладення на знайдені шляхи специфічних вимог, задоволення яких відбувається за рахунок введення ря- ду обмежень у відомі алгоритми пошуку Процедура модифікації алгоритмів при- зводить до значного збільшення обчислю- ваних потужностей. Простішою виявляється задача ви- бору оптимального за заданими критерія- ми шляху з деякої множини доступних шляхів, тому актуальною є задача пошуку К – найкоротших між розглядуваними ве- ршинами шляхів. Безпосередньо дана за- дача виникає при пошуку альтернативних шляхів проходження пакету між маршру- тизаторами в комп’ютерній мережі. Її розв’язання дозволяє зменшити характерні часи збіжності в мережі. Вперше проблема знаходження К– найкоротших шляхів була поставлена в 1959 році Хоффманом і Певлі. В подаль- шому вона досліджувалася Сакаровичем, Белманом, Калабою, Епштейном та ін. У роботі [1] проведено експериментальний аналіз ефективності чотирьох алгоритмів розв’язку розглядуваної задачі – Йена, Ла- урера, Катоха і Хоффмана. Експеримента- льні залежності часу витраченого на по- шук від кількості вузлів у графі (в якості графа було розглянуто топологію системи European Optical Network [2] ) вказують на алгоритм Хоффмана як найбільш ефектив- ний серед розглядуваних. Але у даному алгоритмі на знайдені шляхи не наклада- ється умова простоти (ациклічності). На- томість, практичні застосування вимага- ють саме простих шляхів. Цим умовам за- довольняють алгоритми, у основі яких ле- жить алгоритм Йена. В літературі під на- звою алгоритм Йена зазвичай розуміють модифікацію цього алгоритму Лаулером. Складність даного алгоритму в найгіршо- му випадку для графа із додатними ребра- ми [3]. На сьогодні поширеною є практика розпаралелювання класичних алгоритміч- них задач, актуальність якої підживлюєть- ся напрямком розвитку комп’ютерної тех- ніки у бік збільшення кількості ядер на од- ному кристалі. Мета дослідження – аналіз існую- чих та розробка нових формалізованих пі- дходів до паралельної реалізації алгоритму Йена за рахунок їх опису з використанням математичного апарата модифікованих си- стем алгоритмічних алгебр В.М. Глушкова (САА-М) [4], а також експериментальна перевірка та аналіз ефективності парале- льних реалізацій алгоритму Йена для дво- ядерних і чотириядерних архітектур. 1. Формалізація алгоритму Для формального опису алгоритму введе- мо наступні позначення: = – визначає заданий граф; ),,( 1 nxxX K = – скінчена множина елементів, що називаються вузлами ; XXxxR ji ×⊆= )},{( – множина, що задає бінарне відношення на X , еле- мент такої множини R називається ребром © Погорілий С.Д., Трибрат М.І., Бойко Ю.В., Афанасьєв Д.В., 2011 ISSN 1727-4907. Проблеми програмування. 2011. № 2 Паралельне програмування 13 ),(, jiji xxr = , кожному з яких поставлене у відповідність число , що називається вагою ребра. При задані відношення R на X кожному елементу зіставимо певну пі- дмножину jiw , ix X , що позначимо її як ; iRx – послідовність вузлів така, що ребро називається шляхом з вузла в . Шлях буде простим, якщо Вузли назива- ються початковим і кінцевими вузлами шляху . визначає множину шляхів з вузла в у графі . Нехай і два вузли, що належать шляху , тоді кажуть підшлях , якщо він збігається з від до . Позначатиме- мо такий шлях ) . Кожному шляху ставиться у відповідність величина , яка носить назву вартості шляху, та величина , яка визначає кі- лькість вузлів, що входять у шлях ; >=< txxsp ,,, ' 2 ' 1 K ∃ Rxxr kkk ∈= + ),( ' 1 ' s p p pxxxx baba ∈∀≠ '''' ,, . ji xx , p ji xxP , ix jx G ax bx ji xxPp ,∈ ba xxPq ,∈ p p ax bx ,( bap xxsub ∑ ∈ = pba bawpw ),( ,)( )( pc p – об’єднання двох шляхів і , шлях з в , сфор- мований шляхом p та доповнений . qp <> ji xxPp ,∈ lj xxPq ,∈ ix lx q Алгоритм Йена є девіаційним алго- ритмом, який передбачає, що один з най- коротших шляхів уже знайдено за допо- могою базового алгоритму пошуку найко- ротшого шляху між заданими вершинами, який застосовується в найгіршому випадку Кn разів. Наступний шлях шукається на основі попередніх як відгалуження і має відрізнятися від попереднього хоча б од- ним ребром. – базовий алго- ритм пошуку найкоротшого шляху між вершинами , графа ; ),),(( 21 xxXGBSPA 1x 2x G – вузол девіації, тобто вузол батьківського для шляху , з якого вихо- дить дочірній шлях; )( pd p – вузол в шляху , який займає попередню позицію за відношен- ням до ; )(1 pd− p )( pd – кількість вузлів в шляху спільна з батьківським; )( pq p L – буфер шляхів – претендентів на звання найкоротшого шляху. Визначимо впорядковану множину K – найкоротших шляхів між заданими по- чатковою і кінцевою вершинами s t stKK PppP ⊆= }{ ,,1K шляхів таких, що : простий шлях, ; kp },,1{ Kk K∈ )()( 1+≤ kk pwpw , ; }1,,1{ −∈ Kk K визначений раніше . kp 1+kp Множина , побудована в такий спосіб представляє собою дерево із коре- нем у вершині ( рис. 1 ). KP s Рис. 1. Структура множини KP 2. Формування схеми алгоритму 2.1. Загальна схема роботи алго- ритму. Нехай відомий –ий найкоротший шлях з набору , тоді дії алгоритму виглядатимуть наступним чином : k kp KP перебір вершин останнього знайденого шляху включно до вузла девіації з метою пошуку дочірнього шля- ху, що збігається з в частині . За для унікальності від бать- ківського попередньо із множини R вида- ляється ребро ) , яке після відпра- цювання на заданому кроці базового алго- ритму знову відновлюється ; k ix kp kp ),( k ip xssub k ,( 1 k i k i xx + внесення знайдених шляхів у зага- льний буфер L кандидатів на ; 1k+p вибір найкоротшого шляху з буфера й доповнення ним . KP Паралельне програмування 14 алгоритм повинен працю З метою пошуку виключно ациклі- чних шляхів базовий вати на k –му кроці з множиною )}(,..{\ 1 kpdsXX −= (у цьому і полягає модифікація кл ичного алгоритму Йена езпечити унікальність дочірнього шляху, множина ас Лаулером). Щоб заб R має бути модифікована \|..., .};),((),),({(\ 121 21 kk xxx xpdxpdRR= ,,,..., ).. 21221 KPpppxp ⊂⊂⊂ що означає видалення з множини R ребер всіх шляхів, що отримані як відхилення від ія: == = kpL spdtsX } Поки ( ) k=k+1 ; L ; pk ; Поки ((( Kj j k Pppd ⊂∈ ; −k ; ) { } txBSPA k<> ; } p dssub k + ; ки k vpd+→ ; . ою особливістю реалізації оритму є порядок перебору вершин шляху : з метою підвищення ефектив- ності в ть деякого спільного батьківського. Детально алгоритм демонструє схему 1. Схема 1: Ініціалізац { .0};{ )();,),((GBSPA Kk0 ≠∧≠L { Lpw )(k minp ⊂= {LL −→ } ; }{X tpX +−→ ,v ))()) )}),({(RR j k vpd−→ (= pci 1) Поки ( )(x 1 k i kpd−≠ ; {XX k ix+→ ),,G(X)(),(pk xssub k i=L ipk ; }{pLL k L+→ )}(,({XX kp→ По ))()),((( Kj j k Ppvpd ⊂∈ )}j),({(RR } Важлив алг kp иконання прохід по вершинами має відбуватися в оберненому порядку, що за- безпечи оптимізацію витрат на видален- ня і повернення вершин у множину X [5]. Саме такий спосіб демонструє схема 1. 2.2. САА-схема алгоритму. Для формалізації алгоритму використову вся апарат САА. За своїми зображувальними можли ва востями він еквівалентний класич- ним алгоритмічним системам, таким як машини Тьюринга, рекурсивні функції, ланцюги Маркова та ін. Переваги САА – орієнтація на алгоритмічні задачі та розви- нена система засобів формальних перетво- рень, які застосовуються до формального запису алгоритму – його САА схеми. Дана алгебра є багатоосновною, основами якої слугують множина операторів та множина умов з визначеними на даних множинах сигнатурою операцій. Нехай: k – поточне значення потужності множини найкоротших шляхів ; KP x – поточна вершина графа; – поточний шлях; p g – кількість спільних ву івзл шляху з б ькі ерації алг итм В як аргумент ; у множині зада ший та передо- станній елементи parent – ш Визначим Опера ат вським на даному кроці іт ор у. изначимо допоміжні оператори: (.)next – наступний елемент у мно- жині заданій (.)previous – попередній елемент ній як аргумент ; (.)first , (.)last – пер у множині, заданій як аргумент; ( p лях, батьківський за відношенням до шляху p, який міститься в множині ) KP . о множини операторів і предикатів у відповідності до Схеми 1 : тори: };0 k , } p { L, s ) p ( d, ) t s, G, (BSPA p{ =====S };:,:,min:{pA c pPPpLLL KK=== =− + ));(( pfirstxF == ))(:( plastxL == ; ; ))(:( pnextxN == Паралельне програмування 15 previousxP == ; ; xtxRRR −== ; xtxRRE +== ; PAxssubK p <>+== ; == ; ; == . Предикати: ))(:( p ):(XC xX −== ; ):( xXXI +== )))(,(:( xne )))(,(:( xne )),,G(X)(),( L:L( txBS ))(:( pqgG ))(:( pparentpD == ):( gxxQ K);k0( ≠∧≠= Lα ))(( pfirstx ≠=γ ; ))(( gpq ==χ ; ));(( 1 pdx −≠=β ))(( plastx ≠=ε . Схема 2: идалення спільних ребер з множиниВ R : . (2.1) ідтворення видалених спільних ребep в χ}*{ RQDGCR = В множині R : CR . (2.2) Початкове видалення вузлів шляху p з множини X : }NC . (2.3) {FCN ε= я спільних : Відтворенн вузлів шляху p , з батьківським }{ NIFCN β= . (2.4) Пошук дочірніх шляхів, отриманих як від- хилення від батьківського: EKRILDEV β= ьних із попере- дньо визначеними найкоротшими ми, як }***{ P . (2.5) Формула (2.1) описує один із спо- собів видалення ребер, спіл шляха- ий базується на тому, що алгоритм Йена є девіаційним алгоритмом, а отже кожен наступний шлях отримується як ві- дгалуження від попереднього. Тоді остаточна регулярна схема ал- горитму Йена виглядатиме : }.CRCNDEV* CNCR{AS YEN α= (2.6) 3. Аналіз методів розпаралелю- вання алгоритму Йена для систем Йена вк до ро- зпарал коротших шляхів для поточного шляху для всіх паралельних гі- лок мн із спільною пам’яттю Описана в п.1 структура алгоритму азує на два можливі підходи елювання алгоритму: паралельна реалізація базового ал- горитму; реалізація паралельного пошуку до- чірніх най . Кожен із даних методів має працю- вати із спільними ожинами X і R , що визначає архі- тектуру обчислювальної системи, що задо- вольняє вимогам итму, як систему із спільною пам’яттю. 3.1. Паралельна реалізація базо- вого алгоритму. Осно алгор вне навантаження в алгори п тмі Йена створює алгоритм пошуку найкоротшого шляху, тому доцільно при аналізі паралельної реалізації алгоритму розглянути паралельну реалізацію базово- го алгоритму (рис. 2). Одним з найбільш продуктивних алгоритмів, що реалізує ба- зовий алгоритм є алгоритм Дейкстри, який розв’язує задачу пошуку найкоротших шляхів із заданої вершини у зваженому графі з невід’ємними ребрами до всіх ін- ших вершин. Він знайшов широке застосу- вання в мережевих технологіях: викорис- товується в протоколі маршрутизації OSPF (Open Shortest Path First ). В основі роботи алгоритму лежать о ерації з неспа- дною чергою з пріоритетами [6]. Склад- ність цих операцій визначається реалізаці- єю черги з пріорітетами. Можливі реаліза- ції – лінійний масив, біноміальна піраміда, Фібоначеева піраміда. Реалізація при представленні у вигляді біноміальної піра- міди має складність )nln)nm(( +Ο , m – потужність множини R. Відповідна склад- ність алгоритму бу е ))nln)nm((Kn( Йена д +Ο . Алгоритм Йена від- носить до задач по у найк шого заданими вершинами водночас як алгоритм Дейкстри є алгорит- ся шук орот шляху між двома Паралельне програмування 16 мом, який дозволяє знайти найкоротші шляхи від заданої вершини до всіх інших вершин графа. Рис. 2. Паралельний пошук найкоротшого шляху між x та t ...ПП – доступні Том ваної за- дачі умова в регулярній схемі алгоритму Дейкст i p0 паралельні процесори у в контексті розгляду ; ри, описаний в [7] )( VL ≠=δ пе- рейде в умову )(' tx ≠=δ , тобто пошук буде обриватися при досяг евої вершини. Описаний у [7, 8] метод паралельної реалізації ненні кінц алгоритму Дейкстри базується на розбитті початкової черги на p парале- льно оброблюваних черг, де величина p визначається кількістю паралельно за- пущених гілок виконання. Складність опи- ої у [7] паралельної реалізації алгорит- му становить сан ⎟⎟ ⎞ ⎜⎜ ⎛ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ +Ο p nlnn p m , де p – кі- лькість парал аних ілок. ⎠⎝ ельно виконув Відповідна складність алгоритму Йена – г ⎟ ⎟ ⎞ ⎜ ⎜ ⎛ ⎟⎟ ⎞ ⎜⎜ ⎛ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ +Ο p nlnn p mKn . ⎠⎝ ⎠⎝ 3.2. Паралельний пошук дочірніх найкоротших шляхів. Даний метод поля- гає в т ю ому, щоб для k -го найкоротшого шляху асинхронно проводити пошук дочі- рніх. Даний підхід безпосередньо опира- ється на структуру алгоритму Йена, тому саме така методика може бути названа па- ралельною реалізацією алгоритму Йена. Фактично підхід полягає у паралельному виконанні ітерацій циклу, що містить ба- зовий алгоритм для кожної вершини, що входить у батьківський шлях ( рис. 3 ). Ро- зглянемо батьківський шлях p , який представляє собою вектор вершин послі- довні переходи між якими і ут р ють шлях. во Рис. 3. Паралельний пошук дочірніх шляхів Розглянемо ли, які мають у масиві p порядкові номери два вуз jiji <:, . Для пошук ершині у ациклічного дочірнього шляху, отриманого відхиленням у в , не- обхідна відсутність у множині j X вершин, наявних у шляху p під номерами )1,1( −jK , тобто базовий алгоритм на да- ному кроці ітерації ма р цюв ти з мно- )},({ 1 ' −−= jpj pssubX , аналогіч- на ситуація виникає і з i -м відхиленням, яке пра i , причому 0\ '' ≠ji XX . Граф G вигляді м є п а цює із множиною X представляється у квадратної риці а жиною X ' ат A : n x n, яка носить назву і в матриц суміжності, елементи якої можна задати у игляді предиката )(, ijji Rxxa ∈= , кожному з яких поставле- но у відповідність числа jiw , . У такому випадку i-й рядок відповідає за вихідні для ребра ix , стовпець відповідно за вхідні. Фактично множина вершин X проекту- ється на рядки і стовпці матриці A . Саме із таким представленням граф працює ба- зовий алгоритм. Видалення вузла із множини а X до- сягається видаленням ребер із множини R , а відповідно стовпця із матриці A , які є вхідними за відношенням до нього. Отже, на перший погляд здається, що ітерації не можуть працювати із однією Паралельне програмування 17 спільною множиною X , оскільки викону- ють модифікацію множини R : для кож- ної із них необхідно ворювати власну, несумісну із множиною іншої ітерації множину ' jX , а відповідно із нею і множи- ну ' jR , що творюватиме високі накладні витрати на створення копій. Аналогічна проблема виникає і для спільних із бать- ківським шляхом ребер ),( 1 k i k i xx + . Рішення побудуємо за рахунок змі- нення порядку звертанн ут с я до елементів ма- триці A . Процес видалення вузлів з мат- риці суміжності представлений на (рис. 4). Рис. 4. Процедура видалення вузлів з поча- ткової матриці суміжності для k- го бать- між- ності на му кроці ітерації еквівалентно утворе i− форм вид ківського шляху на i- ій ітерації Видалення вузлів з матриці су i - нню нової квадратної матриці сумі- жності iA , що складається із всіх вузлів, що не належать шляху ),( 1 k ip xssub k − . Розмі- рність такої матриці буде )),(( k p k i xssubcnm k −= . атрицю можна ально ілити з матриці k 1 Дану м A , бл ну звернення до елементів шляхом створення ша о ),( 1 k ip xssub k − (доповнення мно- жини k psub ),( 1ixs k − до X ), який по суті є множи н iX Звернення до реб- ра матриці iA – ik відбуватиметься як ][][ bXaX ik ab i k i k rr = . Утворимо загальний шаб- на використовувати для по- хідного індивідуального шаб- лону для певного кроку ітерації. Структура шаблону має вигляд },\{ kk k ppXT = і до- пускає вільний поряд леме- нтів множини kpX \ . Множина kp має зберігати поряд аний порядк вер- шин у вихідному шляху, це дозволяє i -ій працювати з множиною k iX , а 1+i ітера- ція з множиною {1 k i xX + += . При- клад шаблону пока ною верши . будови необ ок входження е }X + зано на (рис. 5). k k abr лон, який мож ок зад ом 1 k i k i Рис. 5. Утворення шаблону для i-ї лгоритм Йена вимагає видалення на i-у а н У такий спосіб вдається незалежно реалізації становитиме ітерації k-го шляху А кроці ітерації ребра ),( 1 k i k i xx − для за- безпечення унікальності ого та уникнення з циклювань. Тут також наяв- ний зв’язок за даними між ітераціями. Але він може бути просто ліквідований. Алго- ритм Дейкстри для i-й ітерації шукатиме шлях між від k ix до d і у даному шляху має бути відсу ім р ро ),( 1 k i k i xx − . Алго- ритм Дейкстри на початко пі при- своює всім вершинам у графі значення до- сяжності з точки k ix рівним ∞ , а далі пе- ребираючи ребра, і йдуть до их вершин проводить процедуру релаксації [4], яка в кінцевому випадку полягає в зменшенні величини досяжності. Якщо на першій іте- рації алгоритму Дейкстри розглянути лише вершини шаблону k iX за виключенням k ix 1− , то в такий спос ож а буде проіг- увати ребро ),( 11 k i k i xx − всередині ітера- ції. корист дочірнь тн еб вому ета як ц іб м нор уватися єдиною матрицею A для кожного паралельного процесора, пов’язаного із відповідними ітераціями і тим самим створити умови для розробки паралельної схеми алгоритму. Складність ( )⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ +Ο nlnnm p nK . Паралельне програмування 18 хітектури САА-М схема алгоритму Йена фо- рму Д множи 4. САА-М схема алгоритму Йена для SMP - ар MCR{AS YEN 1CC ∨= ватиметься на основі формули (2.4). одамо нові елементи до інформаційної ни: T – загальний шаблон для поточно- го батьківського шляху. IT – індивідуальний шаблон для поточної ітерації пошуку дочірнього шля- ху. Додамо до множини операторів оператори: )}/{( pXpTM ∪== , (4.1) )),(( xTFormITIM == , (4.2) де операція формує індивідуа- визначається поточним елемен ),( xTForm льний шаблон для поточної ітерації, яка том x . ),,) IT G(( txA )),( L:L(/ BSPxssubK p <>+== : зпо- ділу ітерації між паралельними процесо- ного із них величи- ни, що ідентифікують індекси елеме масиві Тоді можна записати }{* / PKIMAMDEVM β= (4.3) Задля реалізації статичного ро рами введемо для кож нтів в p : ,1)( ,)( )1()( )( +−= −= + nipci nipci ppplast pppfirst (4.4) де i – номер паралельної гілки, num pqpc )( −n )( = – загальна вузлів найкоро- тші шляхи між якими необхідно лки, num – – кількість доступних паралельних гілок. Введемо буде знайти, i – номер паралельної гі деяку умову ))(( plastx iii ≠=β , де ix визначають по- точний лемент для i -ї паралельної гіл- ки. Тоді предикат е β може бути перепи- саний як pi βββββ ∧∧∧ K Введемо допоміжн ер ре хронних диз’юнкції: CC (4.6) Формула (4.6) ілюструє п е : ∧= K21 . ий оп атор: }*{ / PKIACC ii β= (4.5) Тоді (3.3) можна п дставити як сукуп- ність асин ∧ M numiCCCCMDEVM KK ∨∨= 1** аралельну частину САА-М алгоритму Йена. Тоді по- вна схема алгоритму виглядатим }.CR*numi CCCC KK ∨∨ α При роботі з SMP системами - стовується так звана парадигма програму- вання з пам'яттю, що розділяється (shared memory - дном грам 5. Технологія OpenMP викори paradigm), яка базується на приро у використанні паралельних потоків, які мають спільну область пам’яті під код та дані. POSIX – інтерфейс для створення потоків – Pthreads [9] підтримується май- же на всіх UNIX – системах (схожий за функціональними можливостями інтер- фейс підтримують і Windows платформи – Windows Threads), але такий інтерфейс більш трудомісткий для практичного па- ралельного програмування оскільки має дуже низький рівень програмування. Ви- сокорівневою надстройкою над Pthreads (та аналогічними бібліотеками) для SMP платформ, що масштабуюються, на сього- днішній день де-факто стала технологія програмування OpenMP (Open Multi- Processing )[10], що активно підтримується компанією Intel. У даній технології вико- ристовується модель програмування бли- зька до Pthreads: динамічне породження потоків, спільні та розділювані дані, меха- нізм “замків” для синхронізації. Для напи- сання програм, що підтримують стандарт OpenMP зі специфікаціями набору дирек- тив компілятора, службових функцій і змінних середовища, використовуються спеціальні компілятори. Основні переваги технології OpenMP: розробник не створює нову парале- льну програму, а додає в текст послідовної програми директиви ОpenMP; передбачається, що OpenMP – про- а на однопроцесорній платформі може бути використана у якості послідовної программ. Директиви компілятора ігнору- ватимуться гнучкість за рахунок можливості використання низькорівневих механізмів. Абстрактність інтерфейсу OpenMP дозволяє використовувати для алгоритмів природні поняття паралельного виконання операцій і дозволяє з легкістю провести формальний аналіз. Паралельне програмування 19 6. Е стю 50% ( кспериментальні результати З метою підтвердження ефективності роботи паралельних реалізацій алгоритму його було застосовано до щільно заповне- ного графа з щільні nnm ×≈ ). С с кладність у такому випадку буде для до- татньо великих розмірностей – )( 3KnΟ , а прогнозована складність паралельної вер- сії ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ Ο для вип n = {50, 100, 250, 500, 1000, 1500,2500, для кількості шляхів: , 300, 400, 500}; Д - ися підмат- сті у спосіб, що по- p nK 3 , p – кількість доступних па- ралельних процесорів. Результати були отримані а- дкових графів розмірностей: 3500, 4500, 5500, 6500, 7500}; K = {10, 20, 50, 100, 200 ля того, щоб забезпечити однорід- ність розглядуваних графів, використову валася одна матриця максимальної розмір- ності на основі якої формувал риці меншої розмірно казано на рис. 6. Рис. 6. Методика побудови підматриць Часи виконання послідовної версії програми в залежності від кількості вузлів у графі й K показано на рис. 7 та 8. кількості шукан поліноміаль- ний закон складності в лежності від роз- мірн ної та паралельної вер- сій. прис , Рис. 7. Часи виконання послідовної версії алгоритму в залежності від кількос- ті вузлів у матрицях для різних К Рис. 8. Часи виконання послідовної версії алгоритму в залежності від кількос- ті шуканих шляхів для матриць різних ро- змірностей З графіків видно збігаюче з теорією лінійний закон зростання складності від их шляхів, та за ості матриці. Паралельні реалізації тестувалися на вузлі кластеру КНУ ім. Т. Шевченка [11]. Аналіз проводився шляхом порівняння ре- зультатів послідов Залежності отриманих прискорень від розмірностей матриць для різних K пока- зано на рис. 9, а, б, та рис. 10, а, б. Порівняння графіків прискорення для двох паралельних реалізацій дозволяє стверджувати, що у версії з паралелізацією базового алгоритму вихід на максимальне корення відбувається повільно і дося- гається лише на матрицях великих розмір- ностей водночас як у алгоритмі з масками прискорення мало залежить від розмірнос- ті матриці суміжності. Це пояснюється тим, що у алгоритмі Дейкстри час витра- чається на створення та впорядкування p черг [8], які необхідні для незалежної ро- боти паралельних процесорів водночас як для алгоритму з масками всі підготовчі (створення масок, видалення спільних з попередніми шляхами ребер) операції ви- конуються до початку ітерацій. 0 1000 2000 3000 4000 5000 6000 7000 8000 0 200 400 600 1200 800 1000 Ча с ви ко на нн я K : ( се к ) 10 50 100 200 300 400 500 Кількість вузлів (n) 0 100 200 300 400 500 0 200 400 600 800 1000 1200 n : 100 500 1000 2000 3000 4000 5000 6000 7000 7500 Ч ас в ик он ан ня ( се к )) Кількість шляхів ( K ) Паралельне програмування 20 я систем- них в а – для д х потоків; Так п масок є більш ви оводить напряму паралелізацію ітерацій водночас як п шаблонів: а – для двох потоків; б – для чотирьох потоків В ос - хронізац м буде прогр чим я систем- них в а б Рис. 9. Прискорення отримані для версій з використанням паралельної реалізації алгоритму Дейкстри: а – для д х потоків; Так п масок є більш ви оводить напряму паралелізацію ітерацій водночас як п б Рис. 10. Прискорення отримані для версій з використанням шаблонів: а – для двох потоків; б – для чотирьох потоків В ос - хронізац м буде прогр чим Паралельна реалізація вимагає дода- ткових витрат часу на синхронізацію пото- ків між собою. Звернення до засобів син- хронізації вимагає використанн ція вимагає дода- ткових витрат часу на синхронізацію пото- ків між собою. Звернення до засобів син- хронізації вимагає використанн икликів, що вимагають значного ча- су. Кількість синхронізуючих елементів напряму залежить від рівня вкладеності блоків коду, що підлягають розпаралелю- ванню. икликів, що вимагають значного ча- су. Кількість синхронізуючих елементів напряму залежить від рівня вкладеності блоків коду, що підлягають розпаралелю- ванню. а б Рис. 9. Прискорення отримані для версій з використанням паралельної реалізації алгоритму Дейкстри: вово б – для чотирьох потоків б – для чотирьох потоків ідхід з використаннямідхід з використанням сокорівневим, оскільки прсокорівневим, оскільки пр аралельна реалізація базового алгори- тму виконується всередині окремої ітерації для внутрішніх ітерацій алгоритму Дейкс- три. аралельна реалізація базового алгори- тму виконується всередині окремої ітерації для внутрішніх ітерацій алгоритму Дейкс- три. 0 1000 2000 3000 4000 5000 6000 7000 8000 0,0 0,5 1,0 1,5 2,0 2,5 П ри ск ор ен ня ( 2 п от ок и ) Кількість шляхів ( n ) K : б Рис. 10. Прискорення отримані для версій з використанням танньому випадку засобів синтанньому випадку засобів син ії буде більше, а отже, більшиії буде більше, а отже, більши аш за часом. При цьомуаш за часом. При цьому 1,75 2,00 0 1000 2000 3000 4000 5000 6000 7000 8000 0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 5,0 П ри ск ор ен ня ( 4 п от ок и ) Кількість шляхів (n) K : 10 50 100 200 300 400 500 0 1000 2000 3000 4000 5000 6000 7000 8000 -0,25 0,00 0,25 0,50 0,75 1,00 1,25 1,50 10 K : 50 10 100 50 П ри ск ор ен ня ( 2 п от ок и ) Кількість шляхів (n) 100 200 200 300 300 400 400 500 0 1000 2000 3000 4000 5000 6000 7000 8000 0,0 0,5 1,0 1,5 2,0 2,5 500 а П ри ск ор ен ня ( 4 п от ок и ) Кількість шляхів ( n ) K : 10 50 100 200 300 400 500 Паралельне програмування 21 ільш низькорівнева паралелізація тим рі- вном ягають у використанні ад- ресац шаб- базового алгоритму – 4.4 рази. Можна Йена допус ну паралелізацію для SMP – с йованого пі схем 3 ) з використанням апарату САА, ю для форму- вання п зації а ритму пошуку най б ірніше навантаження на паралельні процесори і відповідно менший час очіку- вання завершення операцій всіма процесо- рами. Тому в даному сенсі метод шаблонів програє реалізації з паралельним алгорит- мом Дейкстри. Структура запропонованого парале- льного пошуку дочірніх шляхів також ви- магає накладних витрат на етапі виконання ітерації, які пол ії матриці суміжності за шаблоном, тобто непряме звертання до елементів ма- триці, що вимагає накладних витрат. З рис. 9, 10 видно, що в проведених експериментах максимальні прискорення склали: для двох потоків методу лонів – 1.6; для чотирьох потоків методу стверджувати, що алгоритм кає ефектив истем, але вимагає диференці- дходу до застосування різних паралелізації. Висновки 1. Побудовано регулярну схему алго- ритму Йена ( (KnΟ ) яка є вихідно них версій. аралель 2. Запропоновано два підходи до па- ралельної реалі лгоритму Йена для SMP – архітектур. Перший – паралельна реалізація базового алго коротшого шляху. Для другого розроб- лено метод шаблонів, який дозволяє про- вести асинхронний пошук дочірніх шляхів для заданого батьківського. 3. Проведено оцінки складностей за- пропонованих рішень. Перший підход дає теоретичну складність ⎟ ⎟ ⎠ ⎜ ⎝ ⎟⎟ ⎠ ⎜⎜ ⎝ ⎟⎟ ⎠ ⎜⎜ ⎝ + p lnn p Kn , другий – ⎞ ⎜ ⎛ ⎞⎛ ⎞⎛ nm Ο (⎜ ⎛ +Ο mnK ізацію )⎟⎟ ⎠ ⎞ ⎜ ⎝ nlnn p . 4. Виконано формал запропоно- ваного методу шаблонів шляхом форму- вання паралельних з використанням математичного апарата САА–М. схем 5. Реалізовано паралельный алгоритм Йена, використовуючи метод шаблонів і метод розпраралелювання базового алго- ритму, у якості якого було взято реаліза- цію алгоритму Дейкстри із складністю ).( nlnnm +Ο 6. Отримані експериментальні дані вказують на суттєвий приріст у швидкодії паралельних реалізацій у порівнянні з по- слідовною ерсією. в kshop. – 1995. . O’Mahony M.J, Sinclair M.C., Mikac B. 12. – P 33–45. 4. г т е основы, 6. мы: построение и ана- 7. Ю.В., Білоус Р.В. н х 8. етодов распараллели- вания алгоритмов решения некоторых за- 7. Паралельні реалізації алгоритму вимагають диференційованого підходу у застосуванні до архітектур із різною кіль- кістю ядер. На двопроцесорній системі ефективнішим виявляється застосування методу шаблонів, а на чотирьохпроцесор- ній – метод паралельного базового алгори- тму. 8. В обох паралельних схемах присут- ні накладні витрати, які призводять до від- хилень прискорень від теоретично очіку- ваних. 1. Brander A.W., Sinclair M.C. A comparative study of k-shortest path algorithms// In Proc. of 11th UK Performance Engineering Wor 2 Ultra-high capacity optical transmission network. European research project COST 239 // Information, Telecommunications, Autonata. – 1993. – 3. Кристофидес Н. Теория графов. – М.: Мир, 1978. – 432 с. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П. и др. Мно оуровневое с руктурное проекти- рование программ. Теоретически интсрументарий. – М.: Финансы и статис- тика, 1989. – 342 с. 5. Martins E., Pascoal M. A new imple- mentation of Yen’s ranking loopless paths a- lgorithm. – 2000. – 13 c. Кормен Т., Лейзерсон Х., Чарльз И., Штайн Л. Алгорит лиз, 2-е издание : Пер. с англ. – М.: «Виль- ямс», 2005. – 1296 с. Погорілий С.Д., Бойко Формува ня та аналіз паралельних с ем алгоритму Дейкстри // Математичні маши- ни і системи. – 2008. – № 4. – C. 62 – 72. Ефимов С.С. Обзор м Паралельне програмування 22 10. ng [Електронний ресурс] – Ре- 11. 8.12.2010 Об о октор технічних наук рофесор кафедри ко о факультету, наук, ету, ч, тет a, ua дач вычислительной дискретной матема- тики // Математические структуры и моде- лирование. – М.: Мир, 2007. – № 17. – C. 72–93. 9. POSIX Threads Programming [ Електронний ресурс ] / Blaise Barney, Lawrence Livermo- ?e National Laboratory – Режим доступу https://computing.llnl.gov/tutorials/pthreads/ The OpenMP API specification for parallel programmi жим доступу http://openmp.org/ Марьяновский В.А., Погорелый С.Д., Бойко Ю.В, и др. Программное обеспече- ние UAClaster // Управляющиесистемы и машины. – 2009. – № 5. – С. 76–80. Отримано 0 авторах: горілий Сергій Дем'янович, П д , мп’ютерної інженерії п радіофізичног Бойко Юрій Володимирович, тичнихкандидат фізико-матема начальник інформаційно-обчислювального центру, зав. кафедри комп’ютерної інже- ерії радіофізичного факультн Трібрат Михайло Ігорович, аспірант кафедри комп’ютерної інженерії радіофізичного факультету, фанасьєв Дмитро ВолодимировиА студент магістратури кафедри комп’ютерної інженерії радіофізичного факультету. Місце роботи авторів: Київський національний універси імені Тараса Шевченка, 1601, Київ-601, 0 вул. Володимирська, 60. ел.: (044)2590519, Т e-mail: sdp@univ.kiev.ua, .ua, mike3b@univ.kiev iv.kiev.uboyko@un afon_rff@univ.kiev.

Підходи до паралелізації алгоритму Йєна для систем із спільною пам’яттю

Репозитарії

Схожі ресурси