Подход к параллельному решению основной потоковой задачи большой размерности
З використанням математичного апарату модифікованих систем алгоритмічних алгебр (САА–М) виконано формалізацію алгоритму Едмондса–Карпа пошуку максимального потоку в мережі. Зважаючи на особливості розподілених систем, що зазвичай використовуються для розв’язання надскладних задач, формульовано крите...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2009 |
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44351 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Подход к параллельному решению основной потоковой задачи большой размерности / С.Д. Погорелый, Ю.В. Бойко, А.Д. Гусаров, С.И. Лозицкий // Кибернетика и системный анализ. — 2009. — № 2. — С. 146-152. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44351 |
|---|---|
| record_format |
dspace |
| spelling |
Погорелый, С.Д. Бойко, Ю.В. Гусаров, А.Д. Лозицкий, С.И. 2013-05-29T19:16:35Z 2013-05-29T19:16:35Z 2009 Подход к параллельному решению основной потоковой задачи большой размерности / С.Д. Погорелый, Ю.В. Бойко, А.Д. Гусаров, С.И. Лозицкий // Кибернетика и системный анализ. — 2009. — № 2. — С. 146-152. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44351 681.3 З використанням математичного апарату модифікованих систем алгоритмічних алгебр (САА–М) виконано формалізацію алгоритму Едмондса–Карпа пошуку максимального потоку в мережі. Зважаючи на особливості розподілених систем, що зазвичай використовуються для розв’язання надскладних задач, формульовано критерії оптимізації, на основі яких шляхом формальних перетворень САА-схем отримано сукупність паралельних САА–М–схем. The mathematics of modified systems of algorithmic algebras (SAA-M) is used to formalize the Edmonds-Karp algorithm of finding the maximum flow in a network. With account for the features of distributed systems usually used to solve complicated problems, the optimization criteria are formulated and used to obtain parallel SAA-M-schemes. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Подход к параллельному решению основной потоковой задачи большой размерности Підхід до паралельного розв’язку основної потокової задачі великої розмірності An approach to the parallel solution of a high-dimensional basic flow problem 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 |
2009 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Підхід до паралельного розв’язку основної потокової задачі великої розмірності An approach to the parallel solution of a high-dimensional basic flow problem |
| description |
З використанням математичного апарату модифікованих систем алгоритмічних алгебр (САА–М) виконано формалізацію алгоритму Едмондса–Карпа пошуку максимального потоку в мережі. Зважаючи на особливості розподілених систем, що зазвичай використовуються для розв’язання надскладних задач, формульовано критерії оптимізації, на основі яких шляхом формальних перетворень САА-схем отримано сукупність паралельних САА–М–схем.
The mathematics of modified systems of algorithmic algebras (SAA-M) is used to formalize the Edmonds-Karp algorithm of finding the maximum flow in a network. With account for the features of distributed systems usually used to solve complicated problems, the optimization criteria are formulated and used to obtain parallel SAA-M-schemes.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/44351 |
| citation_txt |
Подход к параллельному решению основной потоковой задачи большой размерности / С.Д. Погорелый, Ю.В. Бойко, А.Д. Гусаров, С.И. Лозицкий // Кибернетика и системный анализ. — 2009. — № 2. — С. 146-152. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT pogorelyisd podhodkparallelʹnomurešeniûosnovnoipotokovoizadačibolʹšoirazmernosti AT boikoûv podhodkparallelʹnomurešeniûosnovnoipotokovoizadačibolʹšoirazmernosti AT gusarovad podhodkparallelʹnomurešeniûosnovnoipotokovoizadačibolʹšoirazmernosti AT lozickiisi podhodkparallelʹnomurešeniûosnovnoipotokovoizadačibolʹšoirazmernosti AT pogorelyisd pídhíddoparalelʹnogorozvâzkuosnovnoípotokovoízadačívelikoírozmírností AT boikoûv pídhíddoparalelʹnogorozvâzkuosnovnoípotokovoízadačívelikoírozmírností AT gusarovad pídhíddoparalelʹnogorozvâzkuosnovnoípotokovoízadačívelikoírozmírností AT lozickiisi pídhíddoparalelʹnogorozvâzkuosnovnoípotokovoízadačívelikoírozmírností AT pogorelyisd anapproachtotheparallelsolutionofahighdimensionalbasicflowproblem AT boikoûv anapproachtotheparallelsolutionofahighdimensionalbasicflowproblem AT gusarovad anapproachtotheparallelsolutionofahighdimensionalbasicflowproblem AT lozickiisi anapproachtotheparallelsolutionofahighdimensionalbasicflowproblem |
| first_indexed |
2025-11-25T11:19:01Z |
| last_indexed |
2025-11-25T11:19:01Z |
| _version_ |
1850511224769347584 |
| fulltext |
ÓÄÊ 681.3
Ñ.Ä. ÏÎÃÎÐÅËÛÉ, Þ.Â. ÁÎÉÊÎ, À.Ä. ÃÓÑÀÐÎÂ, Ñ.È. ËÎÇÈÖÊÈÉ
ÏÎÄÕÎÄ Ê ÏÀÐÀËËÅËÜÍÎÌÓ ÐÅØÅÍÈÞ ÎÑÍÎÂÍÎÉ ÏÎÒÎÊÎÂÎÉ
ÇÀÄÀ×È ÁÎËÜØÎÉ ÐÀÇÌÅÐÍÎÑÒÈ
Êëþ÷åâûå ñëîâà: ñèñòåìà àëãîðèòìè÷åñêèõ àëãåáð, ôîðìàëèçàöèÿ àëãîðèòìîâ,
ïàðàëëåëüíûå ñõåìû àëãîðèòìîâ, ïàðàëëåëèçì ïî äàííûì, ðàñïðåäåëåííûå ñèñòåìû.
ÂÂÅÄÅÍÈÅ
Ðåøåíèå çàäà÷è ìàðøðóòèçàöèè â Internet âûïîëíÿåòñÿ ìèëëèîíû ðàç â ñóòêè,
ïîýòîìó âðåìÿ ïîèñêà îïòèìàëüíîãî ìàðøðóòà ñòàíîâèòñÿ êðèòè÷åñêèì ïàðàìåò-
ðîì àëãîðèòìîâ ìàðøðóòèçàöèè è îïðåäåëÿåò ýôôåêòèâíîñòü ôóíêöèîíèðîâàíèÿ
ñåòè â öåëîì. Ýòî, â ñâîþ î÷åðåäü, òðåáóåò ìàêñèìàëüíî âîçìîæíîãî ïîâûøå-
íèÿ ýôôåêòèâíîñòè ìàðøðóòèçàòîðîâ.
Âûâîäû ýêñïåðòîâ â îáëàñòè êîìïüþòåðíûõ òåõíîëîãèé ñõîäÿòñÿ â òîì, ÷òî
ðåñóðñ ýêñòåíñèâíîãî íàðàùèâàíèÿ ýôôåêòèâíîñòè ìèêðîïðîöåññîðíûõ ñèñòåì çà
ñ÷åò óâåëè÷åíèÿ ñëîæíîñòè è òàêòîâîé ÷àñòîòû ïðîöåññîðîâ ñåáÿ èñ÷åðïàë.  ïî-
ñëåäóþùèõ èññëåäîâàíèÿõ è ðàçðàáîòêàõ àêöåíò ïåðåíåñåí íà ñîçäàíèå ìíîãîÿäåð-
íûõ ïðîöåññîðîâ (îá ýòîì ñâèäåòåëüñòâóåò ïîÿâëåíèå òàêèõ ÷èïîâ îò Intel, AMD,
SUN Microsystems, IBM), ìóëüòèïðîöåññîðíûõ ñèñòåì è êëàñòåðîâ, à çíà÷èò è ïà-
ðàëëåëüíûõ àëãîðèòìîâ. Â ñâÿçè ñ ýòèì ãðóïïà ïî ðàçâèòèþ IRTF (Internet Research
Task Force), êîîðäèíèðóþùàÿ äîëãîñðî÷íûå èññëåäîâàòåëüñêèå ïðîåêòû ïî ñòåêó
ïðîòîêîëîâ TCP/IP, çàíèìàåòñÿ ñîçäàíèåì íîâûõ ïðîòîêîëîâ è ïîèñêîì
ïåðñïåêòèâíûõ ìåòîäîâ ðåøåíèÿ çàäà÷è ìàðøðóòèçàöèè ñ öåëüþ ïðåîäîëåíèÿ
ñóùåñòâóþùèõ íåäîñòàòêîâ íà êà÷åñòâåííî íîâîì óðîâíå.
Àëãîðèòì Ýäìîíäñà–Êàðïà [1], ÿâëÿþùèéñÿ îäíîé èç ïåðâûõ ðåàëèçàöèé ìå-
òîäà Ôîðäà–Ôàëêåðñîíà [2, 4], ðàññìàòðèâàåòñÿ êàê àëüòåðíàòèâíûé âàðèàíò èñ-
ïîëüçîâàíèÿ â ïåðñïåêòèâíûõ ïðîòîêîëàõ ìàðøðóòèçàöèè è ñåòåâûõ óñòðîéñòâàõ
[3, 10]. Ñóùåñòâóåò ìíîæåñòâî àðõèòåêòóð, ñïîñîáíûõ îáåñïå÷èòü ïîâûøåíèå ïðî-
äóêòèâíîñòè ýòîãî àëãîðèòìà, è âàæíûé êëàññ ñðåäè íèõ — ýòî ïàðàëëåëüíûå àðõè-
òåêòóðû. Ðàíåå [9] àâòîðàìè áûë ïðåäëîæåí ïîäõîä ê ðàñïàðàëëåëèâàíèþ è îïòè-
ìèçàöèè äàííîãî àëãîðèòìà äëÿ ïðèìåíåíèÿ íà âû÷èñëèòåëüíûõ ñèñòåìàõ ñ îáùåé
ïàìÿòüþ, ÷òî ìîæåò ïîçâîëèòü â ïîëíîé ìåðå èñïîëüçîâàòü ïðåèìóùåñòâà ñîâðå-
ìåííûõ ìíîãîÿäåðíûõ ïðîöåññîðîâ äëÿ ðåøåíèÿ îñíîâíîé ïîòîêîâîé çàäà÷è. Íî
òàêèå âû÷èñëèòåëüíûå ñèñòåìû îãðàíè÷èâàþò ìàêñèìàëüíóþ ðàçìåðíîñòü çàäà÷è
ñðàâíèòåëüíî íåáîëüøèì îáúåìîì äîñòóïíîé îïåðàòèâíîé ïàìÿòè. Ïîýòîìó äëÿ ðåøå-
íèÿ çàäà÷, îïåðèðóþùèõ áîëüøèìè îáúåìàìè äàííûõ, èñïîëüçóþòñÿ ðàñïðåäåëåííûå
ïàðàëëåëüíûå âû÷èñëèòåëüíûå àðõèòåêòóðû (êëàñòåðû).  ñâÿçè ñ ýòèì äàëåå áóäåì èç-
ëàãàòü ïðèìåíåíèå ìàòåìàòè÷åñêîãî àïïàðàòà ÑÀÀ–Ì [5] â êà÷åñòâå èíñòðóìåíòà äëÿ
ôîðìàëèçàöèè è ìîäèôèêàöèè àëãîðèòìà Ýäìîíäñà–Êàðïà ñ öåëüþ ïîëó÷åíèÿ ñïåêòðà
åãî ïàðàëëåëüíûõ ðåãóëÿðíûõ ñõåì, îïòèìèçèðîâàííûõ ïî êðèòåðèÿì, êîòîðûå îïðåäå-
ëÿþòñÿ îñîáåííîñòÿìè è îãðàíè÷åíèÿìè êëàñòåðíûõ ñèñòåì.
ÊÐÈÒÅÐÈÈ ÎÏÒÈÌÈÇÀÖÈÈ
Ìàòåìàòè÷åñêàÿ ìîäåëü ñåòè ïðåäñòàâëÿåò âçâåøåííûé ãðàô, êîòîðûé â äàííîì
ñëó÷àå óäîáíî çàïèñàòü â âèäå ìàòðèöû ñìåæíîñòåé. Òàêàÿ ñòðóêòóðà äàííûõ
ìîæåò áûòü ëåãêî ïðîìîäåëèðîâàíà â îïåðàòèâíîé ïàìÿòè êîìïüþòåðîâ, è ñ íåé
ëåãêî è óäîáíî ðàáîòàòü, îñîáåííî êîãäà ðå÷ü èäåò î ãåîìåòðè÷åñêîì ðàñïàðàë-
ëåëèâàíèè. Ïðè ýòîì íåîáõîäèìà ìàòðèöà ïîòîêîâ è ìàññèâ âåðøèí ãðàôà (ñì.
íèæå). Ïðè áîëüøîé ðàçìåðíîñòè çàäà÷è äëÿ ðàçìåùåíèÿ âñåõ ýòèõ äàííûõ ìî-
æåò ïîòðåáîâàòüñÿ çíà÷èòåëüíûé îáúåì îïåðàòèâíîé ïàìÿòè.
146 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2
� Ñ.Ä. Ïîãîðåëûé, Þ.Â. Áîéêî, À.Ä. Ãóñàðîâ, Ñ.È. Ëîçèöêèé, 2009
Îäíî èç îñíîâíûõ íàçíà÷åíèé ðàñïðåäåëåííûõ ñèñòåì — ðåøåíèå çàäà÷ áîëü-
øîé ðàçìåðíîñòè, êîãäà åñòü íåîáõîäèìîñòü îäíîâðåìåííî îïåðèðîâàòü òàêèì îáú-
åìîì äàííûõ, êîòîðûé íå ìîæåò áûòü ðàçìåùåí â îïåðàòèâíîé ïàìÿòè îòäåëüíîé
âû÷èñëèòåëüíîé ìàøèíû. Îòñþäà âûòåêàåò ïåðâûé êðèòåðèé: ïîñêîëüêó ðàçìåð-
íîñòü çàäà÷è áîëüøàÿ, àëãîðèòì äîëæåí èñêëþ÷èòü âîçìîæíîñòü ðàçìåùåíèÿ íà
îäíîì óçëå äàííûõ áîëüøå, ÷åì èìåþùåéñÿ â íåì äîñòóïíîé ïàìÿòè.  èäåàëüíîì
ñëó÷àå, åñëè çàäà÷à òðåáóåò îáúåìà ïàìÿòè Ì, à íà êàæäîì óçëå åå äîñòóïåí îáúåì
m M m( )� , òî êàæäóþ ñòðóêòóðó äàííûõ èç ïåðå÷èñëåííûõ âûøå ñëåäóåò ðàâíî-
ìåðíî ðàçáèòü è ðàçìåñòèòü íà n óçëàõ êëàñòåðà, ãäå n
M
m
�
�
��
�
� 1.
Óçëû â ðàñïðåäåëåííîé ñèñòåìå ñâÿçàíû ìåæäó ñîáîé êàíàëàìè, ïðîïóñêíàÿ
ñïîñîáíîñòü êîòîðûõ çíà÷èòåëüíî ìåíüøå, à çàäåðæêè íàìíîãî áîëüøå, ÷åì ñîîò-
âåòñòâóþùèå ïàðàìåòðû â ñèñòåìàõ ñ îáùåé ïàìÿòüþ. Ýòî îäèí èç îñíîâíûõ íå-
äîñòàòêîâ êëàñòåðíûõ ñèñòåì [6]. Òàêèì îáðàçîì, ìîæíî ñôîðìóëèðîâàòü âòîðîé
êðèòåðèé: íåîáõîäèìî ìèíèìèçèðîâàòü îáúåì äàííûõ, ïåðåäàâàåìûõ ìåæäó ïà-
ðàëëåëüíûìè ÷àñòÿìè àëãîðèòìà, à òàêæå óìåíüøèòü ÷àñòîòû òàêèõ ïåðåäà÷.
Ïîñêîëüêó îáìåí äàííûìè ìåæäó óçëàìè âñå æå çàíèìàåò çíà÷èòåëüíóþ ÷àñòü
âðåìåíè, ñëåäóåò ïî âîçìîæíîñòè íàãðóçèòü èõ ïîëåçíîé ðàáîòîé â ïðîöåññå òàêèõ
îáìåíîâ (òðåòèé êðèòåðèé).
Ñóùåñòâóþò äâå îñíîâíûå êîíöåïöèè ïàðàëëåëèçìà: ïàðàëëåëèçì ïî äàííûì
(îäèíàêîâûå äåéñòâèÿ âûïîëíÿþòñÿ îäíîâðåìåííî íàä ðàçíûìè íåïåðåñåêàþùè-
ìèñÿ ïîäìíîæåñòâàìè äàííûõ) è ïàðàëëåëèçì ïî êîäó (ðàçíûå äåéñòâèÿ ïîëíîñòüþ
èëè ÷àñòè÷íî ïàðàëëåëüíî âûïîëíÿþòñÿ íàä îäíèìè è òåìè æå äàííûìè). Íàñòîÿ-
ùàÿ ñòàòüÿ îñíîâàíà íà êîíöåïöèè ïàðàëëåëèçìà ïî äàííûì. Äëÿ ýòîãî ìàòðèöû
ðàçáèâàþòñÿ íà íåîáõîäèìîå êîëè÷åñòâî ïðèáëèçèòåëüíî îäèíàêîâûõ ÷àñòåé. Èõ
ðàçìåð îïðåäåëÿåòñÿ ïåðâûì êðèòåðèåì è êîëè÷åñòâîì äîñòóïíûõ óçëîâ, íà êîòî-
ðûõ ìîãóò ïðîèçâîäèòüñÿ âû÷èñëåíèÿ. Êàæäûé óçåë ñîäåðæèò îïðåäåëåííóþ ÷àñòü
äàííûõ è ïðè íåîáõîäèìîñòè äîïîëíèòåëüíîé èíôîðìàöèè äîëæåí èíèöèèðîâàòü
àêò îáìåíà äàííûìè ñ ñîñåäíèì óçëîì (èëè ñîñåäíèìè óçëàìè). Ñóùåñòâóåò ðÿä ñïî-
ñîáîâ ìîäåëèðîâàíèÿ ðàñïðåäåëåííûõ âû÷èñëåíèé, ñðåäè êîòîðûõ íàèáîëåå ðàñ-
ïðîñòðàíåííûìè ìîæíî íàçâàòü MPI [7, 8], ïàðàëëåëüíûå âèðòóàëüíûå ìàøèíû
PVM, Java è äðóãèå. Ñ ó÷åòîì îñîáåííîñòåé êàæäîãî èç íèõ ìîæíî ââåñòè äîïîëíè-
òåëüíûå êðèòåðèè îïòèìèçàöèè, ñïåöèôè÷íûå äëÿ êîíêðåòíîãî ñïîñîáà, íî ýòî óæå
âîïðîñ áîëåå òåõíè÷åñêîãî, ÷åì àëãîðèòìè÷åñêîãî õàðàêòåðà. Çäåñü âíèìàíèå áóäåò
ñîñðåäîòî÷åíî â îñíîâíîì íà êðèòåðèÿõ, îáùèõ äëÿ âñåõ ðàñïðåäåëåííûõ ñèñòåì.
ÔÎÐÌÈÐÎÂÀÍÈÅ ÑÀÀ-Ì-ÑÕÅÌ
Äàëåå èñïîëüçóþòñÿ ñëåäóþùèå îáîçíà÷åíèÿ: G G V E� ( , ) — îðèåíòèðîâàííûé
âçâåøåííûé ãðàô (ãðàôîèä); V V G� ( ) — ìíîæåñòâî âåðøèí ãðàôà (| |V n� );
E E G� ( ) — ìíîæåñòâî ðåáåð ãðàôà; s (source) – èñòîê; t (target) — ñòîê (s t� ;
s t V,
); ñ ñ e� ( ) — âåñ, èëè ïðîïóñêíàÿ ñïîñîáíîñòü ðåáðà å; f f e� ( ) — ïîòîê
÷åðåç ðåáðî å (å Å
); f 0 — ïîëíûé ïîòîê â ãðàôå G.
Îïðåäåëèì áàçîâûå íà÷àëüíûå óñëîâèÿ è èñõîäíûå äàííûå:
� äëÿ îïèñàíèÿ ðàáîòû àëãîðèòìà èñïîëüçóþòñÿ:
1) äâå ìàòðèöû n n� , õàðàêòåðèçóþùèå ñåòü: ìàòðèöó ñìåæíîñòåé (ñîäåðæèò
âåñà ðåáåð) è ìàòðèöó ïîòîêîâ (ñîäåðæèò ïîòîêè ÷åðåç âñå ðåáðà);
2) ìàññèâ, ñîäåðæàùèé âñå âåðøèíû ãðàôà;
3) î÷åðåäü FIFO äëÿ âðåìåííîãî õðàíåíèÿ âåðøèí â ïðîöåññå ïîèñêà ïóòè;
� âåðøèíû ïðîíóìåðîâàíû îò 0 äî n �1 â ïðîèçâîëüíîì ïîðÿäêå;
� ñ êàæäîé âåðøèíîé ãðàôà àññîöèèðóþòñÿ, êðîìå íîìåðà, åùå äâà ñâîéñòâà:
dad (ñîäåðæèò íîìåð âåðøèíû, èç êîòîðîé áûëà äîñòèãíóòà äàííàÿ âåðøèíà âî
âðåìÿ ïîèñêà ïóòè ê ñòîêó) è �std (visited, â êëàññè÷åñêîì àëãîðèòìå ïîèñêà â øè-
ðèíó ñâîéñòâî ìîæåò ïðèíèìàòü òîëüêî äâà çíà÷åíèÿ: true èëè false; âïîñëåäñòâèè
åãî òèï áóäåò èçìåíåí);
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2 147
� îáðàùåíèå ê ñâîéñòâàì ïðîâîäèòñÿ ïî àíàëîãèè ñ îáðàùåíèåì ê ïîëÿì
ñòðóêòóð â ÿçûêàõ ïðîãðàììèðîâàíèÿ; åñëè èäåíòèôèêàòîð âåðøèíû èñïîëüçóåòñÿ
áåç óêàçàíèÿ ñâîéñòâà, òî ïîäðàçóìåâàåòñÿ åå íîìåð.
 êðàòêîé ôîðìå àëãîðèòì Ýäìîíäñà–Êàðïà ìîæíî çàïèñàòü â âèäå ðåãóëÿð-
íîé ÑÀÀ–ñõåìû
Edmonds Karp f Update
BFS
� � �( : )* { }
( )
0 0
�
, (1)
ãäå ïðåäèêàò �( )BFS ïðèíèìàåò çíà÷åíèå èñòèíà, åñëè â ðåçóëüòàòå ïîèñêà â
îñòàòî÷íîé ñåòè íå íàéäåíî ïóòè èç s â t; îïåðàòîð Update âêëþ÷àåò â ñåáÿ íå-
îáõîäèìûå ìîäèôèêàöèè â ìàòðèöå ïîòîêîâ è â ïîëíîì ïîòîêå f 0 . Îòëè÷èòåëü-
íîé è êëþ÷åâîé îñîáåííîñòüþ àëãîðèòìà (1) ÿâëÿåòñÿ îòûñêàíèå àóãìåíòàëüíîãî
ïóòè, ãäå èñïîëüçóåòñÿ àëãîðèòì ïîèñêà â øèðèíó ( )BFS [4], êëàññè÷åñêèé âàðè-
àíò êîòîðîãî ìîæíî ïîäàòü ñëåäóþùåé ðåãóëÿðíîé èíòåðïðåòèðîâàííîé
ÑÀÀ-ñõåìîé:
BFS Q s q s Reset isited1 1� � �( { })* ( )* *: : _ � (2)
*
[ ] [ . ]
{
Q t std�� � �
( : )* [( , ) ( )] [ . ] [ ( , ) ( , )]
[ ]
� � � � � �
�
�
� � �
�
0 {
n
q E G std c q f q
( ( , ) ) * ( ) * ( , )Include Q inc Exclude Q q� �� CE }
}
Çäåñü Q — î÷åðåäü, � — ïóñòîå ìíîæåñòâî, q âñåãäà óêàçûâàåò íà ãîëîâó î÷å-
ðåäè; Reset isited_ � 1 ïðèñâàèâàåò çíà÷åíèå false ñâîéñòâó �std âñåõ âåðøèí, êðî-
ìå s, êîòîðàÿ ïîëó÷àåò çíà÷åíèå true; CE îáîçíà÷àåò òîæäåñòâåííûé îïåðàòîð;
ñ q( , )� — âåñ ðåáðà (q, )� ; f q( , )� — ïîòîê ÷åðåç ñîîòâåòñòâóþùåå ðåáðî; îïåðà-
òîð Include Q( , )� ïîìåùàåò â êîíåö î÷åðåäè Q âåðøèíó ñ íîìåðîì �, ïîìå÷àåò åå
êàê ïîñåùåííóþ ( . : )� �std true� è çàïîìèíàåò, ÷òî îíà áûëà äîñòèãíóòà èç âåð-
øèíû q dad q( . : )� � ; inc( )� óâåëè÷èâàåò � íà åäèíèöó; îïåðàòîð Exclude Q q( , )
èçâëåêàåò âåðøèíó èç ãîëîâû î÷åðåäè.
Êðèòè÷åñêèì ìåñòîì àëãîðèòìà (1) ÿâëÿåòñÿ àëãîðèòì ïîèñêà ïóòè, ò.å. BFS ,
ãäå ïðèñóòñòâóåò ìàêñèìàëüíàÿ âëîæåííîñòü öèêëîâ (�-èòåðàöèé), ïîýòîìó âíèìà-
íèå ñîñðåäîòî÷åíî íà îïòèìèçàöèè èìåííî ýòîé ÷àñòè. Ïðèìåíåíèå êîíöåïöèè ïà-
ðàëëåëèçìà ïî äàííûì â ñõåìå (2) îïèñàíî â [9]. Â àëãîðèòìå èç [9] áûë èçìåíåí
òèï ñâîéñòâà �std. Êðîìå òîãî, ïðè ðàñïàðàëëåëèâàíèè íà äâà çâåíà â êàæäîå èç íèõ
áûëà ââåäåíà áóôåðíàÿ î÷åðåäü Q Q1 2( ) äëÿ âðåìåííîãî õðàíåíèÿ âåðøèí, íàé-
äåííûõ çâåíîì, à òàêæå èñïîëüçîâàíû ñèíõðîíèçàòîðû. Âíåñåíèå óêàçàííûõ
ìîäèôèêàöèé ïîçâîëèëî ñôîðìèðîâàòü ïàðàëëåëüíóþ ñõåìó àëãîðèòìà ïîèñêà â
øèðèíó
BFS Q s q s Reset isited true2 21 2 1 2� � � �( { })* ( )*: : _ * ( :, ,� � )* (3)
*
[ . ]
{
� � �1 2 0� � �t std
S search lock Q Q Q Q( )* * *[ ](( : )*�1 1 1 12 � � � �
* * ( : ) *nextq true nextq1 2 1� � �
*[ ](( : ) ))*q false unlock1 1� � � �� CE
�
�
S search lock Q Q Q Q( )* * *[ ](( : )*�2 2 2 22 � � � �
* * ( : ) *nextq true nextq2 1 2� � �
*[ ](( : ) ) )*q false unlock2 2� � � �� CE
}
Çäåñü q q1 2, — ëîêàëüíûå â êàæäîì ïðîöåññå ïåðåìåííûå, êîòîðûå ñîäåðæàò
ýëåìåíò î÷åðåäè Q, îáðàáàòûâàåìûé â äàííûé ìîìåíò â ñîîòâåòñòâóþùåì çâåíå;
148 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2
îïåðàöèè next q next q1 2, ïðèñâàèâàþò ïåðåìåííûì q q1 2, ñëåäóþùèå ýëåìåíòû
èç îáùåé î÷åðåäè â òîì ïîðÿäêå, â êîòîðîì îíè â íåå ïîñòóïàëè. Åñëè ñëåäóþ-
ùèé ýëåìåíò îòñóòñòâóåò, òî ïðèñâàèâàåòñÿ çíà÷åíèå � . Îïåðàòîðíûå ñêîáêè
lock...unlock âûäåëÿþò êðèòè÷åñêèå ñåêöèè àëãîðèòìà, ãäå ïðîèñõîäèò ðàáîòà
ñ îáùåé î÷åðåäüþ. Ïîñêîëüêó ïàðàëëåëüíûå âåòâè ðàáîòàþò àñèíõðîííî
(â ÑÀÀ-Ì îáîçíà÷àåòñÿ îïåðàöèåé àñèíõðîííîé äèçúþíêöèè �
�
), äëÿ èõ ñèíõðî-
íèçàöèè èñïîëüçîâàí ñèíõðîíèçàòîð S ( )� , êîòîðûé â ÑÀÀ-Ì îïðåäåëåí ñëåäóþ-
ùèì îáðàçîì: S
def
( ) { }�
�
� CE . Îïåðàöèÿ search search1 22 2( ) ïðîèçâîäèò ïîèñê
âåðøèí â ñâîåì ïîäìíîæåñòâå V V1 2( ) , äîñòèæèìûõ èç q q1 2( ) , è ñòàâèò èõ
â êîíåö î÷åðåäè. Ýòè îïåðàöèè ìîæíî ïðåäñòàâèòü ñëåäóþùèìè ñõåìàìè:
search Q q E
inV
1 1 1 1 1 1 12 0
1 1
� � � �
�( : )* ( : )* ([( , ) ] [ .� � �
�
{ �std � �0]
� � �[ ( , ) ( , )]( ( , ) )* ( )c q f q Include Q inc1 1 1 1 1 1 1� � � �CE },
search Q
n
q E
inV
2 2 2 2 22
2
2 2
� � � �
�
��
�
( : )* ( : )* ([( , )� �
�
{ 2 2 0] [ . ]� � �� �std
� � �[ ( , ) ( , )]( ( , ) )* ( )c q f q Include Q inc2 2 2 2 2 2 2� � � �CE }.
 ñâÿçè ñ èçìåíåíèåì òèïà ñâîéñòâà �std (òåïåðü åãî òèï ñîâïàäàåò ñ òèïîì
çíà÷åíèé ïðîïóñêíûõ ñïîñîáíîñòåé ñ å( )) â ñõåìå (3) èñïîëüçîâàíà íîâàÿ îïåðàöèÿ
Reset isited_ � 2 , êîòîðàÿ ïðèñâàèâàåò çíà÷åíèå 0 ñâîéñòâó �std âñåõ âåðøèí, êðîìå s,
ïîëó÷àþùåé ìàêñèìàëüíî âîçìîæíîå çíà÷åíèå; â îïåðàöèè Include Q( , )� ïîëå
� �. std âìåñòî true òåïåðü ïðèíèìàåò çíà÷åíèå min ( . , ( , ))q std c q f q,� ��� � � .  ðå-
çóëüòàòå ïðè íàõîæäåíèè î÷åðåäíîãî ïóòè â îñòàòî÷íîì ãðàôå çíà÷åíèå t std.� ðàâ-
íî ìàêñèìàëüíîé âåëè÷èíå, íà êîòîðóþ ìîæíî óâåëè÷èòü ïîòîê âäîëü ýòîãî ïóòè è
ñîîòâåòñòâåííî ïîëíûé ïîòîê. Ñ ó÷åòîì ýòîãî îïåðàòîð Update ìîæíî ïîäàòü ñëå-
äóþùåé ÑÀÀ-ñõåìîé:
Update f f t std t d dad
s
� � � � �
�
( : . )* ( : )* ( : . )*0 0 � � �
�
{
*( ( , ): ( , ) . )* ( ( , ): ( , )– . )* (f d f d t std f d f d t std� � � � � �� � � �: )}� d .
Èñõîäÿ èç ïåðâîãî êðèòåðèÿ, äîïîëíèòåëüíûå ëîêàëüíûå ïåðåìåííûå ( , )qi i�
è ìíîæåñòâà ( , )Q Vi i äîëæíû ôèçè÷åñêè ðàñïîëàãàòüñÿ íà òåõ âû÷èñëèòåëüíûõ ìà-
øèíàõ, ãäå âûïîëíÿåòñÿ ïðîöåññ, ñ êîòîðûì îíè àññîöèèðîâàíû, è âñå ïàðàëëåëü-
íûå ïðîöåññû âûíóæäåíû îáìåíèâàòüñÿ äàííûìè ñ î÷åðåäüþ Q. Òàêèì îáðàçîì, â
êàêîì áû ìåñòå íè íàõîäèëàñü î÷åðåäü Q, îïåðàöèè äîáàâëåíèÿ ê íåé íàéäåííûõ
âåðøèí áóäóò ñâÿçàíû ñ ïåðåäà÷åé äàííûõ ìåäëåííûìè êàíàëàìè ñâÿçè.
Ïðåäëàãàåòñÿ äâà âàðèàíòà ðàçìåùåíèÿ îáùåé î÷åðåäè.
1. Ðàçìåùåíèå íà îòäåëüíîì óçëå (ðèñ. 1).  ýòîì ñëó÷àå ðàáîòà àëãîðèòìà
ïðèîáðåòàåò îñîáåííîñòè êëèåíò–ñåðâåðíîãî ïðèëîæåíèÿ, ïîñêîëüêó âñåì çâåíüÿì,
õðàíÿùèì è îáðàáàòûâàþùèì ÷àñòè ãðàôà, ïðèäåòñÿ îáðàùàòüñÿ ê óçëó, ñîäåðæà-
ùåìó î÷åðåäü, ÷òîáû ïîìåñòèòü èëè èçâëå÷ü âåðøèíó. Ïðè òàêîì ïîäõîäå êàæäàÿ
ïàðàëëåëüíàÿ âû÷èñëèòåëüíàÿ ÷àñòü (êëèåíòñêàÿ) îáìåíèâàåòñÿ äàííûìè òîëüêî ñ
îäíèì çâåíîì (ñåðâåðíûì) è â ñëó÷àå äîáàâëåíèÿ âåðøèí â î÷åðåäü, è ïðè
èçâëå÷åíèè èõ èç î÷åðåäè.
2. Êàæäîå çâåíî ñîäåðæèò ñâîþ êîïèþ î÷åðåäè (ðèñ. 2).  ýòîì ñëó÷àå îïåðà-
öèÿ ïîìåùåíèÿ íîâûõ âåðøèí â î÷åðåäü áóäåò ñâÿçàíà ñ ïåðåñûëêîé îäíèõ è òåõ
æå äàííûõ íà âñå óçëû. Ïðåèìóùåñòâî òàêîãî ïîäõîäà çàêëþ÷àåòñÿ â òîì, ÷òî êàæ-
äîå çâåíî ñîäåðæèò âåñü íàáîð âåðøèí, ïîñåùàåìûõ â ïðîöåññå ïîèñêà ïóòè, è ìî-
æåò ïðîñìàòðèâàòü èõ áåç íåîáõîäèìîñòè îáìåíà ìåæäó óçëàìè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2 149
Àíàëîãè÷íà ðåàëèçàöèÿ è äëÿ ïåðâîãî âàðèàíòà, åñëè èç îñíîâíîé î÷åðåäè
áðàòü íå ïî îäíîé âåðøèíå, à ñðàçó âñå âåðøèíû, íå îáðàáîòàííûå äàííûì çâåíîì.
Äåòàëè îïåðàöèè áóäóò çàâèñåòü îò êîíêðåòíîé ðåàëèçàöèè àëãîðèòìà, ÿçûêà ïðî-
ãðàììèðîâàíèÿ è âîçìîæíîñòåé ñèñòåìû. Íåçàâèñèìî îò ðàçìåùåíèÿ î÷åðåäè ñî-
ãëàñíî âòîðîìó êðèòåðèþ ñóùåñòâóåò íåîáõîäèìîñòü ìèíèìèçàöèè òðàôèêà ìåæäó
ïðîöåññàìè è êîëè÷åñòâîì îïåðàöèé, çàêëþ÷åííûõ â êðèòè÷åñêèå ñåêöèè. Äëÿ ýòî-
ãî ïðåäëàãàåòñÿ ìîäèôèöèðîâàòü ñõåìó (3) òàê, ÷òîáû êðèòè÷åñêàÿ ñåêöèÿ (âàæíåé-
øåé ÷àñòüþ êîòîðîé ÿâëÿåòñÿ äîáàâëåíèå â îáùóþ î÷åðåäü íîâûõ âåðøèí)
âûïîëíÿëàñü ëèøü òîãäà, êîãäà ïðîöåññîì ïåðåñìîòðåíû âñå äîñòóïíûå âåðøèíû
èç îáùåé î÷åðåäè:
BFS Q s q s Reset isited true3 21 2 1 2� � � �( { })* ( )*: : _ * ( :, ,� � )*
*
[ . ]
{
� � �1 2 0� � �t std
S search nextq q lock Q( )* * *[ ]( *[ ]�1 1 1 1 12 � � � �
(( : )* ( : ) ( : ))* )Q Q Q true false unlock� � � � � �1 2 1� � CE
�
�
S search nextq q lock Q( )* * *[ ]( *[ ]�2 2 2 2 22 � � � �
(( : )* ( : ) ( : ))* )Q Q Q true false unlock� � � � � �2 1 2� � CE
}
Î÷åâèäíî, ÷òî ñ ìàòåìàòè÷åñêîé òî÷êè çðåíèÿ ìîäèôèêàöèÿ ñâîäèòñÿ ê âûíå-
ñåíèþ çà ñêîáêè îïåðàöèè âûáîðêè ñëåäóþùåé âåðøèíû èç îáùåé î÷åðåäè
next q next q1 2( ) , ÷òî ïîçâîëÿåò òåïåðü íå âûïîëíÿòü ïðîöåäóðó îáìåíà äàííûìè,
åñëè ïðîöåññó íåîáõîäèìî âûïîëíÿòü äàëüíåéøèå äåéñòâèÿ.
Àíàëèçèðóÿ ðàññìîòðåííûå ïîäõîäû, ìîæíî çàêëþ÷èòü, ÷òî ïðèíöèïèàëüíî
èìåþòñÿ âñå ïðåäïîñûëêè óâåëè÷èòü êîëè÷åñòâî ïàðàëëåëüíûõ çâåíüåâ àëãîðèòìà.
Äëÿ ýòîãî ââåäåì ïåðåìåííóþ ð, êîòîðàÿ ïàðàìåòðèçóåò ñõåìó ïî êîëè÷åñòâó
çâåíüåâ (â ïðåäûäóùèõ ñõåìàõ ð � 2). Äàëåå íåîáõîäèìî ðàçáèòü äàííûå íà îïðåäå-
ëåííîå êîëè÷åñòâî ÷àñòåé, ðàçäåëèâ öèêë ïî � â ñõåìå (2) íà èíòåðâàëû
� i
n i
p
n i
p
�
�
�
�
��
�
�
�
�[
*
,
* ( )
]
1
1 è îáåñïå÷èòü ñèíõðîíèçàöèþ, îïîâåùàÿ î äîáàâëåíèè
ê îáùåé î÷åðåäè íîâûõ âåðøèí. Ïðåæäå ÷åì çàïèñàòü ïàðàìåòðèçîâàííóþ ñõåìó,
èñêëþ÷èì ãðîìîçäêèå îáîçíà÷åíèÿ, ïåðåéäÿ ê íåèíòåðïðåòèðîâàííîé ñõåìå:
A ( { })* (for to do )*� � � � �
def
kQ s k p q s Reset isited: : : _0 1 2�
B for to do� � � �
def
kk p true: :0 1 � (îïîâåcòèòü âñå ïðîöåññû)
L �
def
lock
U �
def
unlock
150 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2
Ðèñ. 1 Ðèñ. 2
Ci
def
iInclude Q Q� ( , )
Di
def
inextq�
R(� �i
def
i false) ( : )� �
� ��
�
�
�
def
k
k
p
: 0
1
(óñëîâèå òîãî, ÷òî ïóòü íå ìîæåò áûòü íàéäåí)
� �� �
def
t std[ . ]0
i
def
iQ� � �[ ]
i
def
iq� � �[ ]
Gi
def
i iQ
n i
p
� � � �
�
�
�
�
[ : ]* ( :
*
)�
� �i
def
i
n i
p
� �
��
�
�
�
[
* ( )
]
1
(óñëîâèå âûõîäà çà ïðåäåëû ïîäìíîæåñòâà Vi )
� � � �i
def
i i i iq E std�
� � �[( , ) ] [ . ]0 (óñëîâèå òîãî, ÷òî âåðøèíó � i
� �[ ( , ) ( , )]c q f qi i i i� � íóæíî äîáàâèòü â î÷åðåäü)
Ii
def
i iInclude Q� ( , )�
Hi
def
iinc� ( )�
P �
def
Update
Ñ ó÷åòîì èçëîæåííîãî îïòèìèçèðîâàííóþ ïàðàìåòðèçîâàííóþ ðåãóëÿðíóþ
ÑÀÀ–Ì–ñõåìó àëãîðèòìà Ýäìîíäñà–Êàðïà äëÿ p ïàðàëëåëüíûõ çâåíüåâ çàïèøåì
â ñëåäóþùåì âèäå:
E K p� � � {
A* B* {
� ��
S ( ) [ ](� �
�
0 0
0
* G * { I CE )* H }* D *0 0 0 0�
*[ ] [ ]( ))� �0 0 0(L* C * B R( * U CE )0 � �
�
�
...�
�
S i i i i i i
i
( )* * [ ]( * *� �
�
G { I CE )* H } D�
[ ]( *[ ]( ))*� �i i i iL C * B R( U CE )� �
�
�
...�
�
S p p p p p p
p
( )* * [ ]( *� �
�
� � � � � �
�
�1 1 1 1 1 1
1
G { I CE )* H }* D
*[ ]( *[ ]( * ))*� �p p p p� � � �� �1 1 1 1L C B R( U CE)
}*
*P}
�
 ïîñëåäíåé ñõåìå ó÷òåíû ïåðâûõ äâà êðèòåðèÿ îïòèìèçàöèè. Î÷åâèäíî, ÷òî-
áû óäîâëåòâîðèòü òðåòèé êðèòåðèé, íåîáõîäèìî âûïîëíèòü íåêîòîðîå ëîêàëüíîå
ðàñïàðàëëåëèâàíèå íà êàæäîì óçëå, ïîñêîëüêó óçåë äîëæåí îäíîâðåìåííî îáìåíè-
âàòüñÿ äàííûìè ñ ñîñåäíèìè óçëàìè è âûïîëíÿòü îïðåäåëåííûå âû÷èñëåíèÿ. Âîç-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2 151
ìîæíîñòè áèáëèîòåêè ÌÐI [7, 8] ïîçâîëÿþò ðåàëèçîâàòü ôîíîâûé îáìåí ñîîáùåíè-
ÿìè, âî âðåìÿ êîòîðîãî èñïîëíåíèå îñíîâíîãî êîäà íå áëîêèðóåòñÿ, ÷òî ìîæåò
áûòü èñïîëüçîâàíî â êà÷åñòâå äîïîëíèòåëüíîé îïòèìèçàöèè ïðè ìîäåëèðîâàíèè
ñõåìû.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå ïîëó÷åíû ñõåìû àëãîðèòìà Ýäìîíäñà–Êàðïà, îðèåíòèðîâàí-
íûå íà ïðèìåíåíèå â ðàñïðåäåëåííûõ ïàðàëëåëüíûõ àðõèòåêòóðàõ, èñïîëüçîâà-
íèå êîòîðûõ ñòàíîâèòñÿ âñå áîëåå àêòóàëüíûì, à èíîãäà è áåñêîìïðîìèññíûì.
Áëàãîäàðÿ ïðèìåíåíèþ ÑÀÀ-Ì â êà÷åñòâå èíñòðóìåíòà ôîðìàëèçàöèè àëãîðèòìà
ñòàíîâÿòñÿ äîñòóïíûìè ìîùíûå ñðåäñòâà äëÿ ãåíåðàöèè ïî ôîðìàëèçîâàííîé
ðåãóëÿðíîé ñõåìå ïðîãðàììíîãî êîäà, ìîäåëèðóþùåãî àëãîðèòì ñðåäñòâàìè êîí-
êðåòíîãî ÿçûêà ïðîãðàììèðîâàíèÿ (íàïðèìåð, Ñè, Ñè++). Ñëåäóåò îòìåòèòü, ÷òî
ïîëó÷åííûå ñõåìû áûëè ðåàëèçîâàíû íà ÿçûêå ïðîãðàììèðîâàíèÿ Ñè ñ èñïîëü-
çîâàíèåì ïàðàäèãìû ÌÐI è ïðîìîäåëèðîâàíû íà ðàçëè÷íûõ êëàñòåðàõ. Ðåçóëüòà-
òû ïîäòâåðäèëè ýôôåêòèâíîñòü ïîäõîäîâ è ïðåäëîæåííûõ êðèòåðèåâ îïòèìèçà-
öèè ïðè ðåøåíèè îñíîâíîé ïîòîêîâîé çàäà÷è áîëüøîé ðàçìåðíîñòè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. E d m o n d s J . , K a r p R . M . Theoretical improvements in algorithmic efficiency for network flow
problems // J. Assoc. Comput. Mach. — 1972.— N 19. — P. 248–264.
2. F o r d L . R . , F u l k e r s o n D . R . Maximal flow through a network // Canadian J. of Math. — 1956.—
N 8. — P. 399–404.
3. Ï î ã î ð ³ ë è é Ñ . Ä . Ïðîãðàìíå êîíñòðóþâàííÿ. — Ê.: ÂÏÖ «Êè¿âñüêèé óí³âåðñèòåò», 2005. —
440 ñ.
4. Ñ ý ä æ â è ê Ð . Ôóíäàìåíòàëüíûå àëãîðèòìû íà Ñ++. ×. 5: Àëãîðèòìû íà ãðàôàõ. — ÑÏá: ÎÎÎ
DiaSoft, 2002. — 496 ñ.
5. Þ ù å í ê î Å . Ë . , Ö å é ò ë è í Ã . Å . , Ã ð è ö à é Â . Ï . , Ò å ð ç ÿ í Ò . Ê . Ìíîãîóðîâíåâîå
ñòðóêòóðíîå ïðîåêòèðîâàíèå ïðîãðàìì: Òåîðåòè÷åñêèå îñíîâû, èíñòðóìåíòàðèé. — Ì.: Ôèíàíñû è
ñòàòèñòèêà, 1989. — 208 ñ.
6. Ò à í å í á à ó ì Ý . , â à í Ñ ò å å í Ì . Ðàñïðåäåëåííûå ñèñòåìû. Ïðèíöèïû è ïàðàäèãìû. — ÑÏá:
Ïèòåð, 2003. — 877 ñ.
7. Á à ã à ÷ ¸ â Ê . Þ . Îñíîâû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ. — Ì.: ÁÈÍÎÌ. Ëàáîðàòîðèÿ çíàíèé,
2003. — 342 ñ.
8. http://www–unix.mcs.anl.gov/mpi
9. P o g o r i l y y S . D . , G u s a r o v A . D . Paralleling of Edmonds–Karp net flow algorithm // Appl.
Comput. Math. — 2006. — 5, N 2 — P. 121–130.
10. M e k k i t t i k u l A . , M c K e o w n N . Scheduling VOQ switches under non-uniform traffic, CSL Tech-
nical report, CSL-TR-97-747, Stanford University, 1997.
Ïîñòóïèëà 27.03.2008
152 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2
|