9 / 17
на структура данных, или
x
i
∈
X
S
:
∃
y
j
|
y
j
|
Y
S
, F
−
1
2
x
i
=
y
j
.
(4)
Не нарушая общности дальнейших выводов, предположим, что
в примере графа, приведенного на рис. 2,
Y
S
=
{
y
1
, y
4
}
. Согласно
(4), в критерии 2 получим
X
S
=
{
x
2
, x
5
, x
6
}
, поскольку
F
−
1
2
x
2
=
=
{
y
1
, y
2
}
, y
1
∈
Y
S
;
F
−
1
2
x
5
=
{
y
3
, y
4
}
, y
4
∈
Y
S
;
F
−
1
2
x
6
=
{
y
4
}
, y
4
∈
Y
S
.
Необходимо на приведенных рисунках визуально отличать вершины
информационного графа программы, принадлежащие множествам
X
S
и
Y
S
, поэтому они закрашены серым цветом. Поскольку ЦП прово-
дит обработку структуры данных, возможны различные конфигурации
множества
X
S
. Состав множества
X
S
должен определяться исходя из
баланса уменьшения времени обработки от включения очередной вер-
шины в множество
X
S
и издержек по времени, возникающих при
передаче данных СП ЦП. Проблема выбора наиболее оптимальной
конфигурации
X
S
будет подробно рассмотрена в будущих работах.
Последовательность действий в рамках методики декомпозиции
информационного графа программы для ЭВМ МКОД представлена
ниже.
Декомпозиция информационного графа программы для ЭВМ
МКОД.
Рассмотрим два этапа декомпозиции: подготовительный этап;
этапы преобразования графов
G
(1)
A
и
G
(2)
A
.
Подготовительный этап.
Шаг 1. Для декомпозиции осуществля-
ется дублирование исходного информационного графа программы:
G
(1)
A
←
G
A
,
G
(2)
A
←
G
A
. Впоследствии в ходе выполнения преобра-
зования граф
G
(1)
A
будет приведен к виду
G
AI
, а граф
G
(2)
A
— к виду
G
AS
.
Преобразования графа
G
(
1
)
A
.
Шаг 2. Пусть определено подмноже-
ство
Y
S
⊂
Y
вершин-структур данных. Тогда для графа
G
(1)
A
подмноже-
ство вершин-операторов обработки структур данных есть
X
S
=
{
x
i
}
,
i
= 1 :
|
X
S
|
:
F
−
1
2
x
i
=
Y
0
, Y
0
⊂
Y
S
.
Шаг 3. Для каждой вершины
x
i
∈
X
S
, если
y
j
∈
F
−
1
2
x
i
и
y
j
∈
Y
\
Y
S
,
X
←
X
∪ {
x
→
}
,
F
1
x
i
−
1
←
F
1
x
i
−
1
∪ {
x
→
}
,
F
−
1
1
x
i
←
F
−
1
1
x
i
∪ {
x
→
}
и
F
−
1
2
x
→
←
y
j
. В этом действии осуществляется вставка в граф
G
(1)
A
вершины-оператора передачи данных примитивного типа СП.
Шаг 4. Для каждой вершины
x
i
∈
X
S
, если
y
j
∈
F
2
x
i
и
y
j
∈
Y
\
Y
S
,
X
←
X
∪ {
x
←
}
,
F
1
x
i
←
F
1
x
i
∪ {
x
←
}
,
F
−
1
1
x
i
+1
←
F
−
1
1
x
i
+1
∪ {
x
←
}
и
F
2
x
←
←
y
j
. В этом действии выполняется вставка в граф
G
(1)
A
вершины-оператора получения результатов работы операторов в СП
данных примитивного типа. Вершина получения данных
x
←
от СП
не может иметь дублей в графе в силу построения, поскольку такая
вершина добавляется для каждой вершины
x
i
∈
X
S
, записывающей
некоторое новое значение в вершину
y
j
∈
Y
\
Y
S
.
120 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1