7 / 17
В результате декомпозированный информационный граф програм-
мы представляет собой систему из двух графов
Dec
(
G
A
) =
G
AI
{
X
IC
↔
, Y
P
}
, F
1
X
IC
↔
, F
−
1
1
X
IC
↔
,
F
2
X
IC
↔
, F
−
1
2
X
IC
↔
, F
3
Y
P
, F
−
1
3
Y
P
;
G
AS
{
X
S
↔
, Y
S
}
, F
1
X
S
↔
, F
−
1
1
X
S
↔
, F
2
X
S
↔
,
F
−
1
2
X
S
↔
, F
3
Y
S
, F
−
1
3
Y
S
.
(2)
Здесь
G
AI
— информационный граф алгоритма арифметико-логической
обработки данных примитивного типа;
G
AS
— информационный граф
алгоритма обработки структур данных.
Декомпозиция информационного графа программы, представлен-
ного на рис. 2, в соответствии с введенными выше понятиями приве-
дена на рис. 3.
Для получения декомпозированного информационного графа про-
граммы
Dec
(
G
A
)
, соответствующего программе для ЭВМ МКОД, не-
обходимо определить методику преобразования графа
G
A
в пару гра-
фов
(
G
AS
, G
AI
)
. Таким образом, ключевая задача заключается в поиске
Рис. 2. Пример информационного
графа алгоритма:
— терминальные блоки (
х
1
—
начало,
х
9
— конец);
— обработка
данных;
— объединенный блок
вычисления условий и ветвления;
— ветвление потоков управления;
— слияние потоков управления
некоторого преобразования или со-
вокупности преобразований
Par
вида
Par
:
G
A
→
(
G
AS
, G
AI
)
.
(3)
Преобразование (или совокупность
преобразований) графа
Par
(3) по-
зволяет за конечное число шагов
получить из информационного гра-
фа последовательного алгоритма
G
A
два графа
G
AS
и
G
AI
таких, что
операторы в вершинах графа
G
AS
будут выполняться в СП, а операто-
ры в вершинах графа
G
AI
— в ЦП.
Декомпозиция информацион-
ного графа программы и кри-
терии получения оптимальной
декомпозиции информационно-
го графа алгоритма.
Основой
декомпозиции информационного
графа программы должно стать
преобразование,
выполняющее
удаление вершин-операторов
X
S
,
которые отвечают за обработку
структур данных, из исходного ин-
формационного графа алгоритма.
118 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1