ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
151
Цикл повторяется до полного опустошения структуры
Q
.
В ре-
зультате будут определены кратчайшие пути и их длины для всех
вершин. Состояние структур после выполнения всех итераций пред-
ставлено на рис. 4.
а
б
в
Рис. 4. Пример поиска кратчайших путей в графе (состояние структур
в конце работы алгоритма)
а
–
структура
G
;
б
–
структура
Q
;
в
–
граф
Используя указанные структуры можно преобразовать последо-
вательный вариант алгоритма Дейкстры в два параллельных потока
команд, исполняемые ЦП и СП. В приведенном ниже псевдокоде
приняты обозначения, поясняющие ход вычислительного процесса.
Операции ПОЛУЧИТЬ и ПЕРЕДАТЬ используются для обращения к
очередям данных и команд. Как показано ранее, обмен информацией
между двумя процессорами происходит посредством очередей, кото-
рые обеспечивают синхронизацию исполнения этих ветвей. Напри-
мер, если в алгоритме присутствует команда ПОЛУЧИТЬ, то устрой-
ство ожидает поступление данных, не выполняя других действий.
Идеология организации вычислений на основе передачи сообщений
через очереди позволяет использовать для описания таких процедур
синтаксис библиотеки MPI (Massage passing Interface), принятой в
качестве основы взаимодействия параллельных ветвей алгоритмов в
современных вычислительных системах. В представленном парал-
лельном варианте детализированы фазы инициализации и сохранения
результата.
АЛГОРИТМ ДЕЙКСТРЫ МКОД ЦП(G,s,Q,d,p)
//
Инициализация
ЦИКЛ ПОКА (для всех вершин u
∈
V & u
≠
s)
ПЕРЕДАТЬ (Q.KEY=(
∞
,
u), Q.DATA=(0))
ПЕРЕДАТЬ (G.KEY=(u),G.DATA=(Adj[u],w[u],
∞,0
,1))
ВСЕ ЦИКЛ
ПЕРЕДАТЬ (Q.KEY=(
0
,
s), Q.DATA=(0))
ПЕРЕДАТЬ (G.KEY=(s), G.DATA=(Adj[s],w[s],
0
,0,1))