5 / 17
сленные ранее команды обработки структур (возможно, за меньшее
время). Поэтому,
O
СП
⊂
O
ЦП
.
Основная цель проекта ЭВМ МКОД — разработка аппаратных ме-
ханизмов, повышающих эффективность вычислительной системы в
целом при обработке структур данных, множеств, графов. Полагая та-
кой результат возможным, примем, что СП затрачивает на обработку
действий меньше ресурсов (времени, рассеиваемой мощности, удель-
ной стоимости) по сравнению с ЦП. Тогда можно выделить ключе-
вую задачу подготовки программы для ЭВМ МКОД как задачу ми-
нимизации мощности множества операторов, которые действительно
выполняются в ЦП, за счет выполнения как можно большего числа
операторов в СП. Обозначим множество возможных значений опера-
торов обработки структур
O
∗
S
возм
(его компоненты — базовые операции
теории множеств, приведенные выше).
Для формализации задачи декомпозиции информационного гра-
фа алгоритма введем несколько дополнительных обозначений:
O
действ
ЦП
,
O
действ
СП
— множества операторов, которые действительно выполняются
ЦП и СП после осуществления декомпозиции;
O
↔
=
O
→
∪
O
←
— мно-
жество операторов обмена данными между ЦП и СП (
O
→
— множество
операторов пересылки данных;
O
←
— множество операторов получе-
ния данных). Следует отметить, что
O
↔
∩
O
=
∅
, поэтому введем по-
нятие полного множества операторов ЭВМ МКОД:
O
МКОД
=
O
∪
O
↔
.
Аналогично выделим виды обрабатываемых программой данных.
Множество обрабатываемых данных
D
представлено подмножествами
структур данных (
D
S
⊂
D
) и данных примитивного типа (
D
P
⊂
D
).
Таким образом, получим
D
=
D
S
∪
D
P
. Поскольку структуры дан-
ных состоят из элементов данных (примитивного типа) и отношений
между ними, каждая структура данных может быть представлена в
виде
d
S
i
= (
DE
i
, R
i
)
, где
DE
i
— множество элементов данных при-
митивного типа
i
-й структуры данных;
R
i
— множество отношений
между отдельными элементами
DE
i
i
-й структуры данных,
d
S
i
∈
D
S
,
DE
i
∈
D
P
.
Опишем детализированную модель в терминах теории графов для
получения формализованного представления результата декомпози-
ции информационного графа программы. Введем дополнительные
обозначения:
X
S
— множество вершин обработки структур данных,
O
действ
СП
↔
X
S
,
X
S
⊂
X
;
X
I
— множество вершин обработки данных
примитивных типов,
O
∗
I
↔
X
I
,
X
I
⊂
X
;
X
C
— множество вершин вы-
числения условий,
O
∗∗
↔
X
C
,
X
C
⊂
X
;
X
МКОД
— полное множество
вершин информационного графа программы для ЭВМ МКОД, пред-
ставляющее собой отображение
O
∪
O
↔
↔
X
МКОД
,
X
⊂
X
МКОД
;
X
↔
—
множество операторов обмена данными между ЦП и СП,
O
↔
↔
X
↔
,
X
↔
⊂
X
МКОД
;
X
IC
↔
— множество вершин обработки элементов дан-
ных, данных примитивных типов и вычисления условий, а также
116 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1