ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
148
Рис. 1. Вычислительная система МКОД с раздельным хранением ко-
манд управления
Очевидно, что такая схема построения МКОД системы обеспечи-
вает параллельную загрузку команд в оба процессора в ходе вычис-
лительного процесса, а значит позволяет достичь максимальной па-
раллельности при выполнении потоков. Однако для этой системы
следует разделить последовательную программу на две взаимосвя-
занные программы, что требует применения специализированных
средств компиляции.
Для пояснения принципов работы системы рассмотрим реализа-
цию алгоритма Дейкстры для поиска кратчайших путей на графе.
Этот алгоритм используется, в частности, для сетевой маршрутиза-
ции и поиска кратчайших маршрутов в навигационных системах. За-
дача формулируется следующим образом. Для взвешенного ориенти-
рованного графа
G
(
V
,
E
)
без петель и дуг отрицательного веса найти
кратчайшие пути от некоторой вершины до всех остальных. Пусть:
w
[
u
][
v
] –
вес ребра, соединяющего вершину
u
и
v
;
Adj
[
u
] –
множество
вершин, смежных с
u
;
s
–
исходная вершина;
Q
–
множество вершин,
которые осталось рассмотреть для поиска кратчайших путей;
d
[
u
] –
расстояние от вершины
s
до вершины
u
;
p
[
u
] –
вершина, предше-
ствующая вершине
u
в кратчайшем пути от
s
до
u
.
Рассмотрим работу алгоритма для систем с одним потоком ко-
манд и одним потоком данных (ОКОД). В начальный момент време-
ни множество
Q
состоит из всех вершин графа:
Q
=
V
.
Алгоритм
предполагает на каждом шаге поиск в множестве
Q
вершины u с
наименьшим значением
d
[
u
],
ее удалению из
Q
,
а также вычислению
значений
d
[
v
]
для всех связанных с
u
вершин, входящих в
Q
.
Если
полученная длина пути короче ранее найденной, то она модифициру-
ется и сохраняется новый маршрут
p
[
v
]
через вершину
u
.
В итоге, ко-