Про підхід до розпаралелювання алгоритму Флойда-Уоршалла

Виконано формалізацію алгоритму Флойда-Уоршалла з використанням математичного апарату систем алгоритмічних алгебр модифікованих. Запропоновано стратегії розпаралелювання та одержано паралельну регулярну схему алгоритму. Виконано низку еквівалентних перетворень і отримано спектр модифікованих с...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2005
Автори:	Погорілий, С.Д., Камардіна, О.О., Бавикін, О.І.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут проблем математичних машин і систем НАН України 2005
Назва видання:	Математичні машини і системи
Теми:	Моделювання і управління великими системами
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/58453
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Про підхід до розпаралелювання алгоритму Флойда-Уоршалла / С.Д. Погорілий, О.О. Камардіна, О.І. Бавикін // Мат. машини і системи. — 2005. — № 3. — С. 91-101. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-58453
record_format	dspace
spelling	irk-123456789-584532014-04-05T09:40:49Z Про підхід до розпаралелювання алгоритму Флойда-Уоршалла Погорілий, С.Д. Камардіна, О.О. Бавикін, О.І. Моделювання і управління великими системами Виконано формалізацію алгоритму Флойда-Уоршалла з використанням математичного апарату систем алгоритмічних алгебр модифікованих. Запропоновано стратегії розпаралелювання та одержано паралельну регулярну схему алгоритму. Виконано низку еквівалентних перетворень і отримано спектр модифікованих схем алгоритму Флойда-Уоршалла. Выполнена формализация алгоритма Флойда-Уоршалла с использованием математического аппарата систем алгоритмических алгебр модифицированных. Предложены стратегии распараллеливания и получена параллельная регулярная схема алгоритма. Выполнена цепь эквивалентных преобразований и получен спектр модифицированных схем алгоритма Флойда-Уоршалла. Floyd-Warshall’s algorithm formalization is executed with the use of mathematical means of the systems of algorithmic algebras modified. Conversion strategies of basic algorithm into a parallel one are offered and the parallel regular chart of algorithm is obtained. The chain of equivalent transformations is executed and the spectrum of the modified charts of Floyd-Warshall’s algorithm is got. 2005 Article Про підхід до розпаралелювання алгоритму Флойда-Уоршалла / С.Д. Погорілий, О.О. Камардіна, О.І. Бавикін // Мат. машини і системи. — 2005. — № 3. — С. 91-101. — Бібліогр.: 11 назв. — укр. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/58453 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	2005
topic_facet	Моделювання і управління великими системами
url	http://dspace.nbuv.gov.ua/handle/123456789/58453
citation_txt	Про підхід до розпаралелювання алгоритму Флойда-Уоршалла / С.Д. Погорілий, О.О. Камардіна, О.І. Бавикін // Мат. машини і системи. — 2005. — № 3. — С. 91-101. — Бібліогр.: 11 назв. — укр.
series	Математичні машини і системи
work_keys_str_mv	AT pogorílijsd propídhíddorozparalelûvannâalgoritmuflojdauoršalla AT kamardínaoo propídhíddorozparalelûvannâalgoritmuflojdauoršalla AT bavikínoí propídhíddorozparalelûvannâalgoritmuflojdauoršalla
first_indexed	2025-07-05T09:41:17Z
last_indexed	2025-07-05T09:41:17Z
_version_	1836799469531693056
fulltext	ISSN 1028-9763. Математичні машини і системи, 2005, № 3 91 УДК 681.3 С.Д. ПОГОРІЛИЙ, О.О. КАМАРДІНА, О.І. БАВИКІН ПРО ПІДХІД ДО РОЗПАРАЛЕЛЮВАННЯ АЛГОРИТМУ ФЛОЙДА-УОРШАЛЛА Abstract: Floyd-Warshall’s algorithm formalization is executed with the use of mathematical means of the systems of algorithmic algebras modified. Conversion strategies of basic algorithm into a parallel one are offered and the parallel regular chart of algorithm is obtained. The chain of equivalent transformations is executed and the spectrum of the modified charts of Floyd-Warshall’s algorithm is got. Key words: routing, routing protocols, Floyd-Warshall’s algorithm, data parallelism, parallel regular chart of algorithm, schemes’ equivalent transformations, process. Анотація: Виконано формалізацію алгоритму Флойда-Уоршалла з використанням математичного апарату систем алгоритмічних алгебр модифікованих. Запропоновано стратегії розпаралелювання та одержано паралельну регулярну схему алгоритму. Виконано низку еквівалентних перетворень і отримано спектр модифікованих схем алгоритму Флойда-Уоршалла. Ключові слова: маршрутизація, протоколи маршрутизації, алгоритм Флойда-Уоршалла, розпаралелювання за даними, паралельна регулярна схема алгоритму, еквівалентні перетворення схем, процес. Аннотация: Выполнена формализация алгоритма Флойда-Уоршалла с использованием математического аппарата систем алгоритмических алгебр модифицированных. Предложены стратегии распараллеливания и получена параллельная регулярная схема алгоритма. Выполнена цепь эквивалентных преобразований и получен спектр модифицированных схем алгоритма Флойда-Уоршалла. Ключевые слова: маршрутизация, протоколы маршрутизации, алгоритм Флойда-Уоршалла, распараллеливание по данным, параллельная регулярная схема алгоритма, эквивалентные преобразования схем, процесс. 1. Вступ Актуальною задачею мереж є задача маршрутизації і ефективність їх функціонування, що значною мірою визначається методом розв’язання цієї задачі. Дослідження в цій галузі проводяться вже тривалий час і деякі їх результати розглянуто в [1–7]. Незважаючи на велику увагу, яку приділяють проблемі маршрутизації, всі сучасні алгоритми мають певні недоліки: – неефективність використання у великих мережах; – протокол, в основу якого покладено той чи інший алгоритм, функціонує в межах домену або між доменами; – алгоритм використовує фіксовану метрику; – алгоритм не враховує альтернативні маршрути тощо [1–3]. Крім того, задача маршрутизації в Internet розв’язується мільйони разів на добу. Тому час виконання пошуку оптимального маршруту стає критичним параметром алгоритмів маршрутизації. Вимагається максимально можливе підвищення продуктивності. У зв’язку з цим група з розвитку Internet IRTF (Internet Research Task Force), яка координує довгострокові дослідницькі проекти за стеком протоколів TCP/IP, займається створенням нових протоколів та пошуком нових, перспективних методів розв’язання задачі маршрутизації для подолання існуючих недоліків на якісно новому рівні. Алгоритм Флойда-Уоршалла розглядається як альтернативний варіант застосування в перспективних протоколах маршрутизації (Floyd-Warshall) [4, 5]. Це обумовлено тим, що він: – є ефективним на щільних графах; ISSN 1028-9763. Математичні машини і системи, 2005, № 3 92 – дозволяє знайти найкоротші шляхи для всіх пар вершин орієнтованого графа; – час знаходження найкоротших шляхів у графі, що має n вершин, є сталим і пропорційний 3n . Існує багато архітектур, що можуть забезпечити підвищення швидкодії алгоритму. Важливим класом серед них є паралельні. Метою цієї роботи є мінімізація часу виконання алгоритму Флойда-Уоршалла за рахунок його розпаралелювання. Для цього в роботі запропоновано застосування математичного апарату модифікованих систем алгоритмічних алгебр В.М. Глушкова (САА-М). 2. Формалізація алгоритму Флойда-Уоршалла Алгоритм Флойда-Уоршалла (детально алгоритм розглянуто у [4, 5]) дозволяє розв’язати задачу знаходження найкоротшого шляху для мережі, що містить n вершин, за 3n ітерацій. Алгоритм не забороняє ребра від’ємної ваги, але виключає цикли від’ємної ваги. Для алгоритму важливо, які вершини використовуються як проміжні. Характеристикою шляху є максимальний номер проміжної вершини (у фіксованій нумерації вершин) [4]. Алгоритм використовує три матриці: 1. W – матриця суміжності, що відображає топологію мережі. 2. D – матриця ваги найкоротших шляхів: – ijd – елемент матриці D , що знаходиться в i -тому стовпчику та j -тому рядку; − )0(D – матриця, всі елементи якої визначаються за правилом: ,),(0 jijiребраВагаdij ≠= якщо у графі існує ребро (дуга) ),( ji ; − вазі ребра k ijd на k -тому кроці присвоюється найменше з двох можливих значень: − вага ребра ),( ji на 1−k кроці ( )1( −k ijd ); − вага суми ребер ),(),( jkki + на 1−k кроці )( )1()1( −− + k kj k ik dd ; − )(nD – результуюча матриця ваги найкоротших шляхів. 3. П – матриця передування, що містить найкоротші шляхи: − ijπ – елемент матриці П , що знаходиться в i -тому стовпчику та j -тому рядку; − )(k ijπ – вершина, яка передує вершині j на найкоротшому шляху з вершини i у вершину j з проміжними вершинами з множини },...,2,1{ k ; − )0(П – матриця, всі елементи якої визначаються за правилом:    ∞<≠ ∞= .),(, ;),(,)0( jiребравагатаjiякщоi дорівнюєjiребравагаабоjiякщоnil ijπ Процедура, яка реалізує послідовний алгоритм Флойда-Уоршалла, виглядає так [4]: Floyd-Warshall (W) ISSN 1028-9763. Математичні машини і системи, 2005, № 3 93 . )()( ),min( 1 1 1 ][ )( )1()()1()( )1()1()1()( )0( n k kj k ij k ij k ij k kj k ik k ij k ij Dreturn dddddo ntojfordo ntoifordo ntokfor WD Wrowsn −− −−− =∨= +← ← ← ← ← ← ππππ Входом даної процедури є матриця W ваги ребер графа nn × . Виходом є результуюча матриця )(nD ваги найкоротших шляхів. Підходи до одержання поряд з матрицею )(nD самих шляхів розглянуті в [4]. Нижче наведено приклад мережі з дев’ятьма вузлами. Ваги ребер представлені на рис. 1. Матриця суміжності )0(D , що відображає цей граф, та матриця передування )0(П мають такий вигляд: 1 13 7 10 7 1 1 23 0 11 4 12 7 6 6 20 9 3 5 1 1 2 3 5 8 7 9 6 4 25 5 0 1 9 3 9 5 8 Рис. 1. Граф, що ілюструє мережу з дев’яти вузлів ISSN 1028-9763. Математичні машини і системи, 2005, № 3 94                             ∞∞∞∞∞ ∞∞∞∞∞∞ ∞∞∞∞∞ ∞∞ ∞∞∞∞∞∞ ∞∞∞∞∞∞ ∞∞∞∞ ∞∞∞∞ ∞∞∞∞∞∞ = 0930 2307 0510 1125020128 0910 1304 971130 567130 510 )0(D ;                             = nilnilnilnilnilnil nilnilnilnilnilnilnil nilnilnilnilnilnil nilnilnil nilnilnilnilnilnilnil nilnilnilnilnilnilnil nilnilnilnilnil nilnilnilnilnil nilnilnilnilnilnilnil П 999 88 777 666666 55 44 3333 2222 11 )0( . Матриці )9(D та )9(П , які є результатом роботи алгоритму Флойда-Уоршалла, для вищезазначеного графа такі:                             = 089783510 2302924716221817 680788510 1110084621 1618221709151110 91113101101449 971613113079 57146781005 6815788510 )9(D ;                             = nil nil nil nil nil nil nil nil nil П 69229119 85585555 26223777 66989999 26425115 26422949 33443349 26922999 26922311 )9( . Для дослідження алгоритму, трансформації та розпаралелювання виконаємо його формалізацію. Запишемо алгоритм у вигляді параметричної регулярної схеми з використанням модифікованих систем алгоритмічних алгебр САА-М. Формалізована версія алгоритму має такий вигляд (V – множина вершин графа): ),,(* )})( )}( )}( )()((),min(({{{* )( )( ))(( 0 )()( )1()()1()()1()1()1()( )0( )0( )1()1()1( kn k kj k ij ddd k ij k ij k kj k ik k ij k ij VinjViniVink ПD k i j ППППdddd П WD Vn A return вузолнаступний вузолнаступний вузолнаступний формування card k kj k ik k ij     =∨=+= = = − +≤ −−−− −−− де оператори: ISSN 1028-9763. Математичні машини і системи, 2005, № 3 95 • )(Vcardn = ; • )1()( −= k kj k ij ПП ; • WD =)0( ; • ( j =наступний вузол); • формування )0(П ; • ( i =наступний вузол); • ),min( )1()1()1()( −−− += k kj k ik k ij k ij dddd ; • ( k =наступний вузол); • )1()( −= k ij k ij ПП ; • )()( , kn ПDreturn . Предикати: • Vini ; • Vink ; • Vinj ; • )1()1()1( −−− +≤ k kj k ik k ij ddd . Застосуємо САА-М для оптимізації алгоритму Флойда-Уоршалла. 3. Розпаралелювання алгоритму Можливі різні підходи до еквівалентних перетворень вихідного алгоритму (рис. 2). Підхід, що відповідає рис. 2а, є більш доцільним, тому що алгоритм проектується з урахуванням майбутньої роботи на паралельній архітектурі і враховуватиме її специфіку. Підхід, що відповідає рис. 2б, буде направлений на створення алгоритму для послідовної архітектури. Наступне «перетворення» такої схеми в паралельну не буде враховувати деяких особливостей паралельної архітектури, як при першому підході. Першим кроком у перетворенні вихідного послідовного алгоритму в паралельний є розробка стратегії розпаралелювання. Виходячи з парадигм паралельного програмування, одним із видів паралелізму є паралелізм за даними. Відповідно до цього розглянемо один з можливих варіантів розпаралелювання алгоритму Флойда-Уоршалла, який базується на однорозмірному розбитті матриці D по L процесорах. а б Рис. 2. Підходи до еквівалентних перетворень вихідного алгоритму Послідовний алгоритм Паралельний алгоритм Спектр схем Перетворення з використанням апарату Перетворення з використанням апарату Спектр схем Паралельний алгоритм Послідовний алгоритм ISSN 1028-9763. Математичні машини і системи, 2005, № 3 96 6...543210 N 6 5 4 3 2 1 0 N Блок суміжних рядків процесу а 6...543210 N 6 5 4 3 2 1 0 N Блок суміжних рядків процесу б k-тий рядок що передається всім іншим процесам Кожний процесор обслуговуватиме «свій» процес. Необхідно розподілити по блоках суміжні рядки матриці )0(D по L процесах. Для кожного такого блока визначається номер першого рядка блока та кількість рядків у блоці. На рис. 3а наведено розміщення даних одного процесу у вигляді блока суміжних рядків. На рис. 3б зображено k -тий крок алгоритму із власним блоком суміжних рядків процесу та k -тим рядком, що передається з іншого процесу. На кожному кроці один з процесів передає один рядок всім іншим процесам. Спочатку нульовий процес )0(P передає свій перший рядок, після чого всі процеси виконують операцію .,min( )1()1()1()( −−− += k kj k ik k ij k ij dddd Потім )0(P передає наступний рядок і т.д. Коли процес )0(P передасть усі свої рядки, починає передачу процес )1(P . Процес закінчується, коли останній процес передасть свій останній рядок. Спочатку нульовий процес )0(P передає свій перший рядок, після чого всі процеси виконують операцію .,min( )1()1()1()( −−− += k kj k ik k ij k ij dddd Потім )0(P передає наступний рядок і т.д. Коли процес )0(P передасть усі свої рядки, починає передачу процес )1(P . Процес закінчується, коли останній процес передасть свій останній рядок. Графічно цей підхід та його відмінність від послідовного варіанта показано на рис. 4. Розглянемо інший підхід до розпаралелювання алгоритму, що базується на дворозмірному розбитті матриці D . Матриця )(kD розбивається на p блоків розміром )()( pnpn × . Кожен блок оброблятиметься одним з p процесів. Процесу ijP відповідає блок матриці )(kD , верхній лівий кут якого )1/)1(,1/)1(( +−+− pnjpni , а правий нижній кут – )/,/( pjnpin . Кожний процес модифікує «свою» частину матриці протягом ітерації. На рис. 5 зображено техніку дворозмірного розбиття Рис. 3. Розподіл даних по процесах ISSN 1028-9763. Математичні машини і системи, 2005, № 3 97 матриці. Для мережі, що містить N вершинта обчислювальної системи з P процесорами ЧАС Паралельна програма Послідовна програма 0 N3 P P0 P1 P2 P3 P4 ... Pn 0 1 2 N3 Для мережі, що містить N вузлів та системи з одним процесором чергова ітерація послідовного алгоритму ; чергова ітерація паралельного алгоритму; занесення до буфера рядка для передачі іншим процесам; отримання рядка з буфера; P0 Pn процес за номером n. де Рис. 4. Паралельний та послідовний варіанти алгоритму (1,1) (1,2) (2,1) p/n p/n (i,j) (i-1) p/n +1,(j-1) p/n +1 i( p/n ),j( p/n ) а б Рис. 5. Розподіл даних по процесах при дворозмірному розбитті матриці D На k -тій ітерації алгоритму кожен процес ijP потребує певних сегментів k -того рядка та k - того стовпчика матриці )1( −kD . Наприклад, для обчислення )( , k rld процес повинен отримати блоки )1( , −k kld та )1( , −k rkd . Як показано на рис. 6, блок )1( , −k kld належить процесу, розташованому в тому ж рядку, а блок )1( , −k rkd – процесу, розташованому в тому самому стовпчику, що і процес ijP . Дані між процесами ISSN 1028-9763. Математичні машини і системи, 2005, № 3 98 передаються таким чином: на k -тій ітерації кожний з p процесів, маючи тільки частину k -того рядка, посилає її 1−p -шому процесу, що знаходиться в k -тому стовпчику. Відповідно кожний з p процесів, маючи тільки частину k -того стовпчика, посилає її 1−p -шому процесу, що знаходиться в k -тому рядку. а б k стовпчик k стовпчик k рядок d(k-1)l,k d(k-1)k,r d(k-1)l,r Рис. 6. Пересилки даних між процесами Інший підхід ґрунтується на факті відсутності у внутрішньому циклі процедури, що реалізує алгоритм Флойда-Уоршалла, залежності за даними. Таким чином, всі ітерації цього циклу можна виконувати паралельно. 4. Еквівалентні перетворення паралельної регулярної схеми алгоритму ),,()}))}#(()}(* )()((),min(({{#)#(#{ )( )( ))(( 1 )()( )1()()1()()1()1()1()( )0( )0( )1()1()1( kn k kj k ij ddd k ij k ij k kj k ik k ij k ij Vinjnrnrltonrli i Vink ПDreturnвузолнаступнийkвузолнаступнийiвузолнаступнийj ППППddddbufP Пформування WD Vcardn A k kj k ik k ij     =∨=+== = = − +≤ −−−− += −−− де nrl – номер першого рядка у блоці; nr – загальна кількість рядків у блоці. В результаті перетворення схеми послідовного алгоритму до схеми паралельного видно, що складність алгоритму залишилась на рівні 3V , але кількість ітерацій одного з внутрішніх циклів зменшилась. Формалізуємо деякі фрагменти схеми A0.1. Введемо таку систему позначень: )1()1()()1()()1()1()1()1()1()1()( ,]([::),min( −−−−−−−−− +==+<=+= k kj k ik k ij k ij k ij k kj k ik k ij k kj k ik k ij k ij dddddddddddd . ISSN 1028-9763. Математичні машини і системи, 2005, № 3 99 Для спрощення сприйняття та наступних перетворень одразу ж перейдемо до неінтерпретованої схеми: 1 )1()1()1( :: Uddd k kj k ik k ij =+< −−− ; Add k ij k ij == − ::)1()( ; Bddd k kj k ik k ij =+= −− ::)1()1()( . Тоді прийдемо до такої короткої форми: ),]([::),min( 1 )1()1()1()( BAUdddd k kj k ik k ij k ij =+= −−− . Позначимо: FbufPi == :: ; 2 )1()1()( :: Uddd k kj k ik k ij =+≤ −− ; GПП k ij k ij == − ::)1()( ; HПП k kj k ij == − ::)1()( ; 3:: UVink = ; 4:: UVinj = ; 5:: Unrnrli =+< ; KПDreturn kn =::, )()( . З урахуванням наведених інтерпретацій перейдемо від частково інтерпретованої схеми A0.1 до неінтерпретованої схеми A0.2: .} }#* )}),](([),]]([{[ ]{[# #]#{[ 2.0 214 5 3 K EHGUBAUU U FU A ∨ Введемо ще одне позначення: NEHGUBAU =∨ ::)),](([),]([ 21 ; .}}}#]]{[{[##]#{[ 1.2.0 453 KNUUFU A В результаті таких перетворень ми прийшли до неінтерпретованої схеми. Скористаємося властивостями операторних конструкцій САА-М [8]. }]{[}]{[\|\|}}]{[][ CACBACBA λβλλβλ = . Тоді ISSN 1028-9763. Математичні машини і системи, 2005, № 3 100 }]}}#{[]]{[{[#\|\|}}}#]]{[{[##]#{[ 34533453 FUNUUFUUNUUFU = . Після наведеного вище перетворення перейдемо до схеми .}]}}#{[]]{[{[#\|\| 3.0 34533 KFUNUUFUU A У цій схемі ми зробили з двох вкладених циклів два послідовних цикли, що зменшило складність обчислень. Скориставшись цим співвідношенням ще раз, позбавимось другого вкладеного циклу, перейшовши до схеми A0.3.1: ;}#]{[}]{[\|\|# }#]{[}]{[\|\|#}#}]{[]{[#}}#]]{[{[# 5455 54554545 EUNUUU EEUENUEUUENUEUNUU = === .}#]#})#{[]{[}]{[\|\|(###\|\| 1.3.0 3545533 KFUEUNUUUFUU A Детально розглянувши цю схему, можна побачити, що }]{[ 5 EU не має сенсу, оскільки тіло циклу є тотожний оператор. Тож цей цикл може бути вилученим зі схеми. .}#]#})#{[]{[\|\|(###\|\| 2.3.0 345533 KFUNUUUFUU A Скориставшись властивістю циклу }{\|\|}{}{ BABA ααα = , перейдемо до схеми ;})#]#})#{[),](([),]]([{[\|\|(###\|\| 3.3.0 32145533 KFUEHGUBAUUUUFUU A ∨ .}#]#)}))#{[),](]([{[\|\|)},]]([({[\|\|(###\|\| 4.3.0 324145533 KFUEHGUUBAUUUUFUU A ∨ На цьому етапі маємо можливість розпаралелити альтернативу з використанням фільтру EUHGUEHGU \|\|)(),]([ 222 ∨=∨ . Підставивши праву частину співвідношення в попередню формулу, отримаємо .}#]#)}))#{[\|\|)(]({[\|\|)},]]([({[\|\|(###\|\| 5.3.0 3224145533 KFUEUHGUUBAUUUUFUU A ∨ Можна побачити, що конструкція )\|\|)(( 22 EUHGU ∨ є надлишковою. Виконання другої паралельної гілки не має жодного сенсу. Тобто альтернативу )),](([ 2 EHGU ∨ зі схеми A0.3.4 можна замінити на менш складну операцію )(2 HGU ∨ завдяки використанню операції фільтрації. ;}#]#))}))#{[(]({[\|\|)},]]([({[\|\|(###\|\| 6.3.0 324145533 KFUHGUUBAUUUUFUU A ∨ ISSN 1028-9763. Математичні машини і системи, 2005, № 3 101 ;}#]#))}))#{[(]{[\|\|)},]]([({[\|\|(###\|\| 7.3.0 324145533 KFUHGUUBAUUUUFUU A ∨∨ ;})#]#)}))#({[]({[\|\|)}\|\|]({[\|\|(##\|\| 8.3.0 3241145533 KFUHGUUBUAUUUUFUU A ∨∨ .})#]#({[* )}))#]({[\|\|)}]{[\|\|}](({[\|\|(###\|\| 9.3.0 3 244144145533 KFU HGUUUBUUUAUUUUFUU A ∨∨∨∨ На виході трансформації одержано САА-М схему модифікованого паралельного алгоритму Флойда- Уоршалла. 5. Висновки 1. Обґрунтовано доцільність використання алгоритму Флойда-Уоршалла для формування перспективних протоколів маршрутизації. 2. Виконано формалізацію алгоритму з використанням САА-М і отримано регулярну схему алгоритму (А0). 3. Запропоновано стратегії розпаралелювання алгоритму Флойда-Уоршалла, які ґрунтуються на однорозмірному та дворозмірному розбитті матриці суміжності та на факті відсутності у циклі алгоритму залежності за даними. 4. Отримано паралельну регулярну схему алгоритму Флойда-Уоршалла та, з використанням еквівалентних перетворень, спектр модифікованих схем алгоритму (А0.2.1, А0.3.2, А0.3.9). СПИСОК ЛІТЕРАТУРИ 1. Семёнов Ю.А. Телекоммуникационные технологии http://citforum.ru/nets/semenov/ (ГНЦ ИТЭФ). 2. Погорілий С.Д., Калита Д.М. Про підхід до формалізації протоколів маршрутизації на прикладі протоколу OSPF // Вестник МСУ. – 2000. – № 4. – С. 79–85. 3. Іванова Д., Калита Д. Дослідження, аналіз та трансформація алгоритму Беллмана-Форда // Вісник Міжнародного Соломонового Університету «МАГІСТЕРІУМ». – 2004. – № 9. – С. 109–118. 4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, построение и анализ. – М.: МЦНМО, 2000. – С. 510–535. 5. Седжвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах. – СПб.: ООО «Диасофт ЮП», 2002. – С. 304–310. 6. Англо-русский толковый словар по комп’ютерам и Интернет http://termin.narod.ru/r/routing.htm http://termin.narod.ru/p/protocol.htm. 7. Погорілий С.Д., Калита Д.М. Оптимізація алгоритмів маршрутизації з використанням систем алгоритмічних алгебр // УсиМ. – 2000. – № 4. – С. 20–30. 8. Погорілий С.Д., Камардіна О.О. Дослідження та створення інструментальних засобів автоматизованої трансформації схем алгоритмів // Проблемы программирования. – 2004. – № 1–2. – С. 417–421. 9. Погорілий С.Д. Автоматизація наукових досліджень. Основоположні математичні відомості. Програмне забезпечення / Під ред. академіка АПН України О.В. Третяка. – К.:«ВПЦ Київський університет», 2002. – 290 с. 10. Grama А., Gupta А., Karypis G., Kumar V. Introduction to Parallel Computing, Second Edition. – Addison Wesley, 2003. – ISBN- 0-201-64865-2. – 856 p. 11. Internet Research Task Force (IRTF) http://www.irtf.org.

Про підхід до розпаралелювання алгоритму Флойда-Уоршалла

Репозитарії

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