Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна
Запропоновано метод трансформації алгоритму Голдберга–Тар’яна, який розв’язує важливу мережну задачу пошуку максимального потоку в орієнтованому графі. Сформовано концепцію його паралельної реалізації, а також відповідної схеми алгоритму, з використанням математичного апарату модифікованих систем ал...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2008 |
| Main Authors: | , , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/209321 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна / С.Д. Погорелый, Ю.В. Бойко, С.И. Лозицкий, А.Д. Гусаров // Проблемы управления и информатики. — 2008. — № 5. — С. 110-120. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859687728729292800 |
|---|---|
| author | Погорелый, С.Д. Бойко, Ю.В. Лозицкий, С.И. Гусаров, А.Д. |
| author_facet | Погорелый, С.Д. Бойко, Ю.В. Лозицкий, С.И. Гусаров, А.Д. |
| citation_txt | Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна / С.Д. Погорелый, Ю.В. Бойко, С.И. Лозицкий, А.Д. Гусаров // Проблемы управления и информатики. — 2008. — № 5. — С. 110-120. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Запропоновано метод трансформації алгоритму Голдберга–Тар’яна, який розв’язує важливу мережну задачу пошуку максимального потоку в орієнтованому графі. Сформовано концепцію його паралельної реалізації, а також відповідної схеми алгоритму, з використанням математичного апарату модифікованих систем алгоритмічних алгебр Глушкова (САА-М). Отримано дві удосконалені схеми алгоритму для запропонованого підходу.
This paper presents the method of the optimization of Goldberg–Tarjan’s algorithm that solves an important maximum flow problem in a directed graph. A theoretical synthesis of the corresponding parallel scheme of the algorithm is done with the means of systems of modified algorithmic algebras developed by V.M.Glushkov. Two optimized schemes are obtained for the offered approach.
|
| first_indexed | 2025-11-30T22:51:46Z |
| format | Article |
| fulltext |
© С.Д. ПОГОРЕЛЫЙ, Ю.В. БОЙКО, С.И. ЛОЗИЦКИЙ, А.Д. ГУСАРОВ, 2008
110 ISSN 0572-2691
УДК 681.3
С.Д. Погорелый, Ю.В. Бойко, С.И. Лозицкий, А.Д. Гусаров
ФОРМАЛИЗОВАННЫЕ МЕТОДЫ
РАСПАРАЛЛЕЛИВАНИЯ
АЛГОРИТМА ГОЛДБЕРГА–ТАРЬЯНА
Вступление
Большое количество важнейших задач в области информационных техноло-
гий сводится к моделям потоков в сетях. К ним можно отнести такие общие груп-
пы практических задач, как задачи распределения (distribution), сочетания (matching)
и разрезания (cut).
Особого внимания заслуживает задача поиска максимального потока в сети.
Суть ее заключается в отыскании пути из одной точки сети в другую, который
обеспечивает максимальную пропускную способность из всех путей, соединяю-
щих эти точки. Эффективное решение такой задачи очень важно, когда есть по-
требность в передаче большого количества информации на значительное расстоя-
ние с использованием существующей структуры сети, например когда в сети осу-
ществляется передача данных с использованием коммутации пакетов.
Во второй половине ХХ столетия создано множество ставших уже классиче-
скими алгоритмов для решения указанной задачи [1–3]. Исследования в сфере эф-
фективного поиска максимального потока имеют ключевое значение и сегодня. Об
этом свидетельствует тот факт, что последний алгоритм решения рассматриваемой
задачи предложен еще в 1997 году [4]. Следует отметить, что все классические ал-
горитмы разрабатывались для последовательной реализации на классическом ком-
пьютере. Современные микропроцессоры уже достигли верхнего предела своей
производительности, который определяется физическими ограничениями их полу-
проводниковых элементов. В то же время необычайно быстрыми темпами растут
масштабы реальных задач, требующих эффективного решения. Сегодня появился
еще один путь усовершенствования и повышения производительности классиче-
ских алгоритмов — это их распараллеливание и применение в современных конку-
рентных системах, популярность которых быстро возрастает.
Подходы к распараллеливанию алгоритмов составляют отдельное направление
современной компьютерной науки и включают в себя как теоретические пути ис-
следований, так и практические. Особого внимания заслуживают направления, реа-
лизующие теоретическое и формальное распараллеливания [5, 6]. Именно поэтому
цель настоящей работы состоит в распараллеливании алгоритма Голдберга–Тарьяна
с использованием математического аппарата модифицированных систем алгорит-
мических алгебр [7].
Алгоритм Голдберга–Тарьяна
Алгоритм Голдберга–Тарьяна основан на использовании метода проталкива-
ния предпотока. Оценка его быстродействия составляет О(n
3
) [8].
Исходными данными алгоритма служат ориентированный граф G (V, E);
функция пропускных способностей ребер ),( vuc ;),( Evu функция предпото-
ка ),( vuf ;),( Evu соответствующая ей функция избытка потока )(ve
Vv и функция высоты вершины )(vh .Vv В исходной сети заданы вер-
шины истока и стока — соответственно s и t.
В основе работы алгоритма лежат две операции:
1) push(u, v) — увеличение/уменьшение потока от вершины u к вершине v в
остаточной сети );,( ff EVG
Проблемы управления и информатики, 2008, № 5 111
2) relabel(u) — изменение значения функции высоты в вершине u; операция
выполняет обновление функции высоты, используя информацию инцидентных
вершин в остаточной сети.
Операция push(u, v) может быть применена только в том случае, когда ребро
(u, v) допустимо, т.е. удовлетворяются следующие условия:
e(u) > 0 — условие того, что вершина активна;
r(u, v) с(u, v) – f (u, v) > 0 — условие существования ребра в остаточной
сети;
h(u) h(v)+1 — проталкивание предпотока возможно только «вниз»,
т.е. к вершинам, имеющим меньшее значение функции высоты ; если все усло-
вия удовлетворены, то вдоль ребра r(u, v) проталкивается поток величиной
q min (e(v), r(u, v)), после этого соответствующим образом изменяются значения
функции предпотока, избытка и остаточной пропускной способности;
f (u, v) f (u, v) q;
f (v, u) f (v, u) – q;
e(v) e(v) – q;
e(u) e(u) q;
r(u, v) r(u, v) – q;
r(v, u) r(v, u) q.
Операция relabel(u) может быть выполнена, когда удовлетворяются следую-
щие условия:
— e(u) > 0 — условие того, что вершина активна;
— h(u) ≤ h(v) v таких, что r(u, v) > 0 (операция push(u) не может быть вы-
полнена).
Если эти условия удовлетворены, то значение функции высоты вершины u
меняется следующим образом:
).),(1)(min()( fEvuvhuh
Для обработки текущей активной вершины используется операция
push_relabel(u, v), в основе которой лежат две предыдущие операции.
Пусть a(u) — список вершин, инцидентных вершине u в остаточной сети, а
(u, v) — текущее ребро из этого списка. Возможны два варианта:
I. Если операция push(u, v) разрешена, то выполняем ее, при этом в случае,
когда вершина v становится активной, добавляем ее в конец очереди активных
вершин fifo.
II. Если операция push(u, v) не разрешена и (u, v) — не последняя дуга в спи-
ске a(u), то текущей становится следующая дуга в этом списке; если же (u, v) —
последняя дуга в списке, то выполняется операция relabel(u).
Подходы, применяемые в данной работе, состоят в следующем.
Инициализация. В смежные с истоком вершины посылается максимальный
поток, который равен пропускным способностям ребер. На всех остальных ребрах
поток нулевой. Все активные вершины добавляются в очередь fifo. Осуществля-
ется начальная инициализация функции высоты.
Основной цикл. Пока очередь fifo непустая, над ее активной вершиной вы-
полняется операция push_relabel(u, v). Если вершина не перестала быть активной,
то она отправляется в конец очереди.
Выполним распараллеливание алгоритма Голдберга–Тарьяна на формальном
уровне с целью повышения его быстродействия. В работе [9] математический ап-
парат модифицированных систем алгоритмических алгебр Глушкова (САА-М)
применен для формализованного распараллеливания алгоритма Тарьяна, который
решает важнейшую задачу выделения сильных компонент в ориентированном
112 ISSN 0572-2691
графе. Результаты подтвердили эффективность и целесообразность использования
формального подхода для исследования и усовершенствования других алгорит-
мов. Поэтому в настоящей работе применяется математический аппарат САА-М.
Формализация последовательной регулярной схемы
алгоритма Голдберга–Тарьяна
Для формирования регулярных схем алгоритма (РСА) необходимо конкрети-
зировать структуры данных, с которыми работает алгоритм Голдберга–Тарьяна.
Для этого используем объектно-ориентированную модель структур данных. Та-
ким образом, исходный граф представляется в виде объекта g, который включает
все свойства графа и методы их обработки.
Граф g имеет следующие свойства:
m — матрица смежностей графа размером ;nn каждое ребро (i, j) графа g
представляется как элемент матрицы m[i][ j], который содержит числовое значе-
ние пропускной способности ребра;
f — матрица потока, каждый элемент f[i][ j] которой отображает поток от
вершины i к вершине j;
e — вектор размерности n, который представляет функцию избытка потока
в каждой вершине графа;
d — вектор размерности n, который представляет функцию высоты;
s и t — вершины истока и стока соответственно.
Обращение к описанным свойствам графа осуществляется с использованием
полных имен.
Введена очередь активных вершин типа FIFO как объект с именем fifo. Над
очередью определены такие операции:
а) push(v) — добавить вершину с номером v в конец очереди активных вер-
шин;
б) pop — обработать следующую вершину в очереди (операция возвращает
номер вершины);
в) isempty — проверить, не пуста ли очередь активных вершин (возвращает
значение true, когда очередь пуста, в противном случае — false).
Перейдем к формализации последовательной регулярной схемы классическо-
го алгоритма Голдберга–Тарьяна, применяя аппарат САА-М. В качестве базовых
операций алгоритма используем операции push(v, u) и relabel(v).
РСА операции проталкивания предпотока формализуется следующим образом:
)],[],[(])][[]][[],[(min(),(push quvfuvfwvfuvmvequv
)).][][()][][()],[],[( queueqveveqvufvuf (1)
В РСА использована функция min (a, b), которая возвращает минимальное
значение из множества своих аргументов. Величина q — максимально возможное
количество потока, которое можно протолкнуть по ребру (v, u) в остаточной сети.
РСА операции обновления функции высоты для вершины v имеет следую-
щий вид:
)])[,tempmin(temp({temp()(relabel Eudv nu
)).1temp][(}1 vduu (2)
Здесь введены обозначения для условий:
условие запрета проталкивания потока от вершины v к вершине u
];[][),( udvduv (3)
оно свидетельствует о том, что операция push(v, u) не может быть выполнена;
Проблемы управления и информатики, 2008, № 5 113
условие существования ребра (v, u) в остаточной сети
.0])][[]][[(),( uvfuvmuv (4)
В схеме (2) -итерация обрабатывает все допустимые ребра (v, u) в остаточ-
ной сети для определения минимальной высоты d[u] из множества смежных с
v вершин. Дальше происходит обновление метки высоты вершины v.
Используя РСА (1) и (2), получаем регулярное выражение для операции
push_relabel (v):
push_relabel
)(fifo.push(),(push(({()( )(0][),(),(ttr0][
uuvv uueuvuvve
)).)(relabel()))}truettr0(1()) ttr1 EvuuuE nu (5)
В РСА (5) использованы такие обозначения условий:
условие допустимости по высоте ребра (v, u) для операции push(v, u)
;1][][),( udvduv (6)
условие того, что вершина v не является вершиной истока s или стока t:
).()()( tvsvv (7)
-Итерация в схеме (5) проталкивает поток по всем допустимым ребрам
(условие допустимости )),,(),( uvuv пока справедливо условие .ttr0][ ve
Если во время выполнения операции push(v, u) вершина u становится активной и
не является истоком или стоком (условие )),(0][ uue то она добавляется в
конец очереди fifo.
Переменная ttr представляет собой булевый маркер того, что для вершины v
операция relabel(v) может быть выполнена, т.е. операция push(v, u) невыполнима
для всех допустимых ребер (v, u) в остаточной сети. Во время каждого вызова
операции relabel(v) переменная ttr инициализируется значением false.
РСА инициализации запишем следующим образом:
]][[]][[]][[({)fifo,(init 0]][[0 sufqusfusmqg usmu
}.11][)))(fifo.push(][ )( uunsdEuqueq u (8)
В качестве входных данных для инициализации используется граф g и оче-
редь fifo. -Итерация в РСА инициализации (8) выполняет наполнение ребер, ко-
торые выходят из истока. Вершины, ставшие активными, добавляются в конец
очереди. Инициализируется также функция высоты для всех вершин графа.
На основе схем (5) и (8) получена схема последовательного алгоритма опре-
деления максимального потока, для которого входными данными служат граф g
и очередь fifo:
)fifo,(init)fifo,(flow gg
].[flow)})(fifo.push()(elpush_relabfifo.pop{ 0][tyfifo.isemp
teEuuu ue (9)
Сначала выполняется инициализация алгоритма. Затем основная итерация
убирает активную вершину u из очереди fifo, выполняет операцию push_relabel(u)
и, если вершина не перестала быть активной, снова добавляет ее в конец очереди.
Алгоритм останавливается при выполнении условия fifo.isempty, которое свиде-
тельствует об отсутствии активных вершин. РСА (9) возвращает значение макси-
мального потока в сеть.
114 ISSN 0572-2691
Концепция распараллеливания алгоритма Голдберга–Тарьяна.
Получение параллельной РСА
В основе классического алгоритма Голдберга–Тарьяна лежит модифициро-
ванный поиск в ширину (breath-first-search, BFS) [2], который дополнительно вы-
полняет обработку соответствующих ребер и вершин. Схема (9) обрабатывает ак-
тивные вершины с помощью операции push_relabel(u), используя очередь fifo для
аккумуляции.
Рассмотрим -итерацию в РСА (9), выполняющую обработку вершин до тех
пор, пока не удовлетворено условие .tyfifo.isemp Обозначим D — множество
вершин, которые побывали в очереди алгоритма за все время его работы. Разде-
лим его на подмножества ,,,, 21 kDDD которые представляют собой последо-
вательные части очереди fifo. Другими словами, вершины множества D1 обраба-
тываются первыми, множества D2 вторыми и т.д. Множества Di могут пересе-
каться, а их наполнение не конкретизируется. Используя приведенные
обозначения и модифицируя -итерацию в схеме (9), получаем:
)(elpush_relabfifo.pop{)})(fifo.push(
)(elpush_relabfifo.pop{)fifo,(init)fifo,(flow
0][
1
uuEu
uugg
kDuue
Du
].[flow)})(fifo.push(0][ teEuue (10)
В схеме (10) полная -итерация обработки очереди активных вершин пред-
ставлена последовательностью итераций по множествам Dk.
Множества Dk несколько абстрактны и введены лишь для теоретической мо-
дификации схем. Главное их свойство состоит в том, что эти множества могут об-
рабатываться в любом порядке, хотя при этом будет меняться их качественное
наполнение. Это позволяет делать перестановку итераций в формуле (10).
Таким образом, появляется возможность выполнить k -итераций параллельно.
Каждая такая итерация может быть выделена в отдельную конкурентную задачу.
РСА (10), используя асинхронную дизъюнкцию из сигнатуры операций аппа-
рата САА-М, преобразуем к виду
)fifo,(serv)fifo,(serv)fifo,(init)fifo,(flow 21 gggg
],[flow)fifo,(serv tegk (11)
где каждая -итерация выделена в отдельную задачу servi (g, fifo), которая форма-
лизуется следующим образом:
)(elpush_relabfifo.pop{)fifo,(serv
tyfifo.isemp
uugi
].[flow)})(fifo.push(0][ teEuue (12)
В РСА (12) происходит возвращение к условию окончания -итерации fifo.isempty и
исключаются все условия, связанные с подмножествами Di. Следовательно, кон-
кретное наполнение этих подмножеств было несущественным.
Для задач, представленных РСА (12), остаются общие объекты — очередь
активных вершин fifo и граф g. Неконтролируемый одновременный доступ к об-
щим объектам может повлечь за собой потери данных и сбой в работе алгоритма.
Для исключения подобных ситуаций необходимо ввести синхронизацию над об-
щими объектами.
Проблемы управления и информатики, 2008, № 5 115
Для синхронизации работы с очередью активных вершин введем очередь sfifo
в качестве альтернативы очереди fifo. Она имеет все те же свойства и операции,
что и fifo, за исключением того, что операции реализованы с учетом синхрониза-
ции. Таким образом, операции push(v), pop и isempty — взаимно исключающие.
Для синхронизированного доступа к свойствам, связанным с вершинами и
ребрами, введем две операции.
1. Заблокировать вершину v — lock(v). Задача, вызвавшая данную операцию,
блокирует вершину v с целью монопольного использования для записи всех ре-
сурсов графа, связанных с этой вершиной (d[v], e[v], f [v][u], f [u][v]). Любая другая
задача, попытавшаяся вызвать операцию lock(v), добавляется в конец очереди
ожидания, связанной с вершиной v.
2. Разблокировать вершину v — unlock(v). Задача, вызвавшая эту операцию,
освобождает вершину v для доступа других задач. При этом активизируется сле-
дующая задача из очереди ожидания вершины v.
Доступ и перезаписывание свойств графа осуществляется внутри операций
push(v, u) и relabel(v), которые выражаются соответственно согласно РСА (1) и (2).
Анализируя РСА (1), приходим к выводу, что именно в этой операции осу-
ществляется перезаписывание всех ресурсов графа, связанных с вершинами v и u
(за исключением функции высоты для соответствующих вершин — d[v] и d[u]).
Таким образом, конкретная задача перед попыткой изменить какое-либо из этих
свойств должна сначала заблокировать доступ как к вершине v, так и к вершине u.
С учетом изложенного модифицируем схему (1):
],[],[],[])][[]][[],[(min
)(lock)(lock(),(push_par
vufquvfuvfwvfuvmve
quvuv
)).(unlock)(unlock][][][][],[ vuqueueqveveqvuf (13)
В операции relabel(v) осуществляется запись только функции высоты верши-
ны v. Поэтому, задача должна блокировать только ту часть РСА, где происходит
изменение. РСА (2) модифицируется следующим образом:
}1)])[,tempmin(temp({temp()(el_parrelab uuEudv nu
)).(unlock1temp][)(lock vvdv (14)
Как можно видеть из РСА (14), блокирование вершины v в рамках всей
-итерации недопустимо, поскольку это может вызвать взаимную блокировку за-
дач (dead lock).
Опираясь на РСА (13), (14) и (5), формализуем РСА для модифицированной
операции push_relabel(v):
)))}truettr0(1()))(sfifo.push(
),(push_par(({()(el_parpush_relab
1)(0][
),(),(ttr0][
uuuEu
uvv
nuuue
uvuvve
)).)(rrelabel_pa(ttr Ev (15)
Общая логика работы РСА (15) осталась такой же, как и схемы (5). В ней
лишь используются соответствующие формулы для базовых операций в парал-
лельном контексте. Учитывая РСА (12) и (15), для конкретной задачи получаем:
)(el_parpush_relabsfifo.pop{)sfifo,(serv
typsfifo.isem
uugi
)}.)(sfifo.push(0][ Euue
(16)
116 ISSN 0572-2691
Таким образом, реализована синхронизация разделяемых ресурсов с исполь-
зованием новой очереди sfifo и модифицированных схем (13)–(15) для базовых
операций.
Окончательную параллельную РСА (ПРСА) получаем из схемы (11):
)sfifo,(serv)sfifo,(init)sfifo,(flow_par 1 ggg
],[flow)sfifo,(serv)sfifo,(serv2 tegg k (17)
где каждая задача servi представляется формулой (16).
На рис. 1 изображена структура взаимодействия задач ПРСА (17). Критиче-
ским общим ресурсом для параллельных задач остается очередь sfifo. Каждая из
конкурентных веток РСА выполняет синхронизированный доступ к этому ресурсу
для считывания и добавления активных вершин.
sfifo
v pop
...
push (v, u)
...
relabel (v)
...
serv1
...
push (v, u)
...
relabel (v)
...
servk
push (u, v)
...
Рис. 1
Недостаток ПРСА (17) заключается в одновременном выполнении всех задач
с очередью sfifo, что очень ресурсоемко с точки зрения времени исполнения алго-
ритма, поскольку все операции синхронизированы. Эта проблема особенно обо-
стряется в случае увеличения количества параллельных задач. Поэтому следую-
щий шаг на пути повышения быстродействия алгоритма — уменьшение нагрузки
на очередь активных вершин.
Усовершенствование полученной ПРСА Голдберга–Тарьяна
Синхронизированное взаимодействие с очередью sfifo большого количества
задач одновременно осложняет работу ПРСА (17) и значительно снижает быстро-
действие алгоритма. Целесообразно разгрузить работу с очередью активных вер-
шин. Предлагается два теоретических подхода к решению этой проблемы.
Первый подход базируется на использовании специальных буферных ресур-
сов для каждой из задач, в которых во время работы ПРСА аккумулируются ак-
тивные вершины. Очередь sfifo остается общим ресурсом для всех задач, но чте-
ние и запись в нее осуществляется блоками. Для реализации этого подхода необ-
ходимо определить новые структуры данных, которые будут играть роль
буферных ресурсов. С целью сохранения общей логики работы алгоритма вход-
ной буфер целесообразно реализовать в виде очереди типа FIFO: buf_in[i] —
входная буферная очередь задачи с номером i. Это основная рабочая очередь от-
дельного звена ПРСА и локальный ресурс для каждой из конкурентных задач.
Над очередями buf_in[i] определены следующие операции:
add(sub_fifo) — добавить в конец очереди buf_in[i] очередь sub_fifo, не на-
рушая порядок FIFO;
pop — обработать следующую вершину очереди (операция не синхронизи-
рована);
Проблемы управления и информатики, 2008, № 5 117
isempty — проверить, не пуста ли очередь.
Аналогично реализуется выходной буфер: buf_out[i] — выходная буферная
очередь задачи с номером i. В очереди накапливаются новосозданные активные
вершины. Над буферами buf_out[i] определены следующие операции:
push(u) — поместить в конец очереди вершину с номером u;
clean — очистить очередь (удаляются все элементы выходной очереди).
Введенные ресурсы исключительно локальны для каждой параллельной за-
дачи и не требуют синхронизации.
Для обеспечения нового взаимодействия задач с общей очередью sfifo над
ней определены дополнительные операции:
get(count) — удалить и вернуть в параметр подочередь sfifo размером в
count элементов с сохранением порядка;
put(sub_fifo) — добавить в конец очереди sfifo подочередь sub_fifo.
Обе операции синхронизированы и реализуют взаимное исключение задач при
работе с sfifo. Учитывая, что теперь главная рабочая очередь активных вершин
для каждой параллельной задачи — входная локальная очередь buf_in[i], а вы-
ходной буфер — очередь buf_out[i], РСА (15) для операции push_relabel_par (v)
модифицируем следующим образом:
1()))(push].[buf_out(
),(push_par(({(),(el_parpush_relab
1)(0][
),(),(ttr0][
uuEui
uviv
nuuue
uvuvve
)).)(rrelabel_pa()))}truettr0( ttr Evu (18)
В РСА (18), в отличие от (15), новые активные вершины накапливаются в
выходную буферную очередь. Кроме того, дополнительно введен параметр i, обо-
значающий номер конкретной параллельной задачи. Операции push_par(v, u) и
relabel_par(v) не изменяются и описываются соответственно схемами (13) и (14).
Трансформируем РСА (16), реализующую каждую из конкурентных задач
servi:
)})(push].[buf_out(),(el_parpush_relab
pop].[buf_in{)(sub_fifoadd].[buf_in
)count(sfifo.getsub_fifo{)countsfifo,,(serv
0][
isempty].[buf_in
])[][(
Euiiu
iui
g
ue
i
tesei
}.clean].[buf_out])[buf_out(sfifo.put ii (19)
ПРСА (19) работает так. Сначала из общего для всех задач ресурса sfifo счи-
тывается подочередь sub_fifo размером в count элементов и добавляется к вход-
ному буферу buf_in[i]. Далее обрабатываются все вершины из входного буфера, а
новые активные вершины добавляются к выходному буферу. По окончании рабо-
ты внутренней -итерации содержимое ресурса buf_out[i] помещается в общую
очередь sfifo. Такая последовательность действий повторяется, пока справедливо
условие внешней -итерации (e[s] ≠ e[t]), свидетельствующее о том, что макси-
мальный поток в сети еще не найден. Указанное условие использует равенство
суммарного потока, выходящего из истока, и суммарного потока, входящего в
сток. Переход к такому условию теоретически обоснован и сделан вследствие то-
го, что условие ptysfifo.isem более не может быть необходимым и достаточным
условием завершения работы всего параллельного алгоритма.
Общая же логика работы алгоритма не изменилась, поэтому в схему (17) вне-
сены незначительные модификации:
118 ISSN 0572-2691
)1,sfifo,(serv)sfifo,(init)sfifo,(flow_par 1 ggg
],[flow),sfifo,(serv)2,sfifo,(serv2 tekgg k (20)
задачи servi реализуются схемой (19). На рис. 2 представлена структура взаимо-
действия задач ПРСА (20).
buf_in [k]
vbuf_in[k].pop
...
push_relabel (v)
...
buf_out [k].push (u, v)
buf_out [k]
sfifo
buf_in [k]
vbuf_in[k].pop
...
push_relabel (v)
...
buf_out [k].push (u, v)
buf_out [k]
serv1 servk
sfifo.put (buf_out [1]) buf_in[k].add(sfifo.get(count))
)
...
Рис. 2
Описанный метод позволяет разгрузить общий ресурс sfifo, что должно пози-
тивно отразиться на быстродействии алгоритма в целом.
Второй подход к усовершенствованию ПРСА (17) частично базируется на
использовании распараллеливания по данным. Это позволяет снять нагрузку при
работе с очередью sfifo, а также уменьшить накладные расходы по синхронизации
работы нескольких задач с основными ресурсами графа (матрицей потоков, векто-
рами функций избытка потока и расстояний). Суть подхода состоит в том, чтобы
множество вершин графа разделить на непересекающиеся подмножества. Дополни-
тельно соответствующим образом выполняется разделение матриц смежностей и
потоков. Каждое подмножество вершин v1 и v2 (в случае двух параллельных задач)
и соответствующие части матриц g и f закрепляются за своими задачами (рис. 3).
Предложенное разбиение данных не означает, что конкретное множество
вершин и ребер становится локальным для соответствующей задачи. Все другие
задачи тоже имеют синхронизированный доступ ко всем ресурсам.
Такой подход позволяет полностью исключить из ПРСА (17) очередь sfifo и
вместо нее ввести вектор очередей vfifo[k], k — общее количество параллельных
задач. Следовательно, каждый элемент vfifo[i] выступает в роли главной рабочей
очереди для задачи с номером i и содержит только закрепленные за этой задачей
активные вершины. Это означает, что любая задача может добавлять элементы к
любой очереди vfifo. Однако обрабатывать вершины из очереди vfifo[i] может
лишь задача с номером i. И это позволяет снять синхронизацию с операции
vfifo[i].pop, что также позитивно повлияет на быстродействие ПРСА.
serv1
Вершины
serv2
v
v1
v2
Задачи Матрицы g и f
1v
2v
v
Рис. 3
Проблемы управления и информатики, 2008, № 5 119
Учитывая особенности второго подхода, перейдем к трансформациям ПРСА.
Для идентификации номера задачи, которой принадлежит определенная верши-
на v, опишем функцию, возвращающую номер задачи-владельца:
./)(serv_num nkvv (21)
В схеме (20) все вершины графа равномерно распределены между всеми k задачами.
Схема (15) для операции push_relabel_par модифицируется следующим образом:
)))(push].sid[vfifo)(serv_numsid(
),(push_par(({()(el_parpush_relab
)(0][
),(),(ttr0][
Euu
uvv
uue
uvuvve
)),)(rrelabel_pa()))}truettr0(1( ttr1 Evuuunu (22)
операция serv_num представляется соотношением (21). Особенность последней
ПРСА в том, что при появлении новой активной вершины сначала идентифицирует-
ся номер задачи, к которой ее следует привязать, а потом она добавляется в конец
соответствующей очереди. Вследствие преобразований формула (16) принимает вид
pop].[vfifo{)sfifo,(serv
])[][(
iug
tesei
)},)(push].[vfifo()(el_parpush_relab 0][ Euiu ue (23)
где учтено, что задача servi работает лишь со своей очередью vfifo[i], а операция
push_relabel_par представляется соотношением (22).
Вследствие замены общей очереди на вектор очередей модификации потре-
буются и в РСА инициализации (8):
)(serv_numsid(][]][[
]][[]][[({)vfifo,(init
)(
0]][[0
uqueqsufq
usfusmqg
u
usmu
}.11][)))(push].sid[vfifo uunsdEu (24)
В соотношении (24) входным параметром служит вектор очередей активных
вершин, внесены также соответствующие изменения при инициализации. Таким
образом, новую ПРСА получаем из (17) с учетом (23) и (24):
)vfifo,(serv)vfifo,(init)vfifo,(flow_par 1 ggg
].[flow)vfifo,(serv)vfifo,(serv2 tegg k (25)
Графически взаимодействие задач ПРСА (25) изображено на рис. 4, где вни-
мание акцентируется на основных моментах взаимодействия параллельных задач
с общими ресурсами.
vfifo [k]
...
push (v, u)
...
relabel (v)
...
serv1 servk
vvfifo[1].pop
...
vfifo[1]
...
push (v, u)
...
relabel (v)
...
vfifo[k].push (u)
vfifo [1].push (u, v)
Рис. 4
120 ISSN 0572-2691
Выводы
1. В результате исследования алгоритма Голдберга–Тарьяна сформирована
концепция его распараллеливания.
2. Формализована соответствующая параллельная регулярная схема в САА-М.
3. В результате анализа формализованной ПРСА получены два ее модифици-
рованных варианта.
4. Первые реализации ПРСА (17) на платформе Java для систем с общей па-
мятью показали увеличение быстродействия в сравнении с РСА (9): на 20 % для
двух задач и на 40 % — для четырех.
С.Д. Погорілий, Ю.В. Бойко, С.І. Лозицький, А.Д. Гусаров
ФОРМАЛІЗОВАНІ МЕТОДИ РОЗПАРАЛЕЛЮВАННЯ
АЛГОРИТМУ ГОЛДБЕРГА–ТАР’ЯНА
Запропоновано метод трансформації алгоритму Голдберга–Тар’яна, який роз-
в’язує важливу мережну задачу пошуку максимального потоку в орієнтованому
графі. Сформовано концепцію його паралельної реалізації, а також відповідної
схеми алгоритму, з використанням математичного апарату модифікованих сис-
тем алгоритмічних алгебр Глушкова (САА-М). Отримано дві удосконалені
схеми алгоритму для запропонованого підходу.
S.D. Pogorelyi, Y.V. Boyko, S.I. Lozitskiy, A.D. Gusarov
FORMALIZED METHODS OF PARALLELING
OF GOLDBERG–TARJAN’S ALGORITHM
This paper presents the method of the optimization of Goldberg–Tarjan’s algorithm
that solves an important maximum flow problem in a directed graph. A theoretical
synthesis of the corresponding parallel scheme of the algorithm is done with the
means of systems of modified algorithmic algebras developed by V.M.Glushkov.
Two optimized schemes are obtained for the offered approach.
1. Ford L.R. Jr., Fulkerson D.R. Maximal flow through a network // Canadian J. of Math. — 1956. —
8. — P. 399–404.
2. Диниц Е.А. Алгоритм решения задачи о максимальном потоке сети со степенной оценкой //
Докл. АН СССР. — 1970. — 194, № 4. — С. 754–757.
3. Edmonds J., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow
problems // J. Assoc. Comput. Mach. — 1972. — 19. — P. 248–264.
4. Goldberg A.V., Rao S. Flows in undirected unit capacity networks // SIAM J. on Decscrete Math-
ematics. — 1999. — 12, N 1. — P. 1–5.
5. Воеводин В.В., Воеводин Вл. Параллельные вычисления. — С.-Пб. : БХВ-Петербург,
2004. — 608 с.
6. Погорілий С.Д. Програмне конструювання. — К. : ВПЦ «Київський університет», 2007. —
438 c.
7. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П., Терзян Т.К. Многоуровневое структурное проек-
тирование программ. — М. : Финансы и статистика. — 1989. — 156 с.
8. Goldberg A.V., Tarjan R.E. A new approach to the maximum flow problem // J. Assoc. Comput.
Mach. — 1988. — 35. — P. 921–940.
9. Pogorilyi S.D., Lozytskyi S.I. Finding strongly connected components in parallel // Appl. and
Computational Mathematics. — 2007. — 6, № 2. — P. 236–246.
Получено 21.03.2008
Статья представлена к публикации членом редколлегии Ф.Г. Гаращенко.
|
| id | nasplib_isofts_kiev_ua-123456789-209321 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-11-30T22:51:46Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Погорелый, С.Д. Бойко, Ю.В. Лозицкий, С.И. Гусаров, А.Д. 2025-11-18T17:02:17Z 2008 Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна / С.Д. Погорелый, Ю.В. Бойко, С.И. Лозицкий, А.Д. Гусаров // Проблемы управления и информатики. — 2008. — № 5. — С. 110-120. — Бібліогр.: 9 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209321 681.3 10.1615/JAutomatInfScien.v40.i9.60 Запропоновано метод трансформації алгоритму Голдберга–Тар’яна, який розв’язує важливу мережну задачу пошуку максимального потоку в орієнтованому графі. Сформовано концепцію його паралельної реалізації, а також відповідної схеми алгоритму, з використанням математичного апарату модифікованих систем алгоритмічних алгебр Глушкова (САА-М). Отримано дві удосконалені схеми алгоритму для запропонованого підходу. This paper presents the method of the optimization of Goldberg–Tarjan’s algorithm that solves an important maximum flow problem in a directed graph. A theoretical synthesis of the corresponding parallel scheme of the algorithm is done with the means of systems of modified algorithmic algebras developed by V.M.Glushkov. Two optimized schemes are obtained for the offered approach. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна Формалізовані методи розпаралелювання алгоритму Голдберга–Тар’яна Formalized methods of paralleling the Goldberg−Tarjan algorithm Article published earlier |
| spellingShingle | Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна Погорелый, С.Д. Бойко, Ю.В. Лозицкий, С.И. Гусаров, А.Д. Методы обработки информации |
| title | Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна |
| title_alt | Формалізовані методи розпаралелювання алгоритму Голдберга–Тар’яна Formalized methods of paralleling the Goldberg−Tarjan algorithm |
| title_full | Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна |
| title_fullStr | Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна |
| title_full_unstemmed | Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна |
| title_short | Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна |
| title_sort | формализованные методы распараллеливания алгоритма голдберга–тарьяна |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/209321 |
| work_keys_str_mv | AT pogorelyisd formalizovannyemetodyrasparallelivaniâalgoritmagoldbergatarʹâna AT boikoûv formalizovannyemetodyrasparallelivaniâalgoritmagoldbergatarʹâna AT lozickiisi formalizovannyemetodyrasparallelivaniâalgoritmagoldbergatarʹâna AT gusarovad formalizovannyemetodyrasparallelivaniâalgoritmagoldbergatarʹâna AT pogorelyisd formalízovanímetodirozparalelûvannâalgoritmugoldbergatarâna AT boikoûv formalízovanímetodirozparalelûvannâalgoritmugoldbergatarâna AT lozickiisi formalízovanímetodirozparalelûvannâalgoritmugoldbergatarâna AT gusarovad formalízovanímetodirozparalelûvannâalgoritmugoldbergatarâna AT pogorelyisd formalizedmethodsofparallelingthegoldbergtarjanalgorithm AT boikoûv formalizedmethodsofparallelingthegoldbergtarjanalgorithm AT lozickiisi formalizedmethodsofparallelingthegoldbergtarjanalgorithm AT gusarovad formalizedmethodsofparallelingthegoldbergtarjanalgorithm |