12 / 17
Шаг 22. Выполняется перенумерация вершин в множестве
Y
по
порядку, так что обозначение каждой вершины приобретает вид
y
Si
, а
само множество
Y
переходит в множество
Y
S
.
Шаг 23. Полученный граф является графом обработки структур
данных:
G
AS
←
G
(2)
A
.
Среди характерных свойств полученных графов
G
AS
и
G
AI
мож-
но выделить их структурное сходство с исходным информационным
графом последовательного алгоритма, в том числе то, что они также
представляют собой объединение графа и ориентированного двудоль-
ного графа. Более важное свойство — полное отсутствие у получен-
ных графов общих дуг, что позволяет в дальнейшем восстановить
по графам исходный код программы, которая может быть выполнена
на ЭВМ МКОД: граф
G
AS
соответствует программе, которая будет
выполняться СП, а граф
G
AI
— программе, которая будет выполнять-
ся ЦП. Несмотря на эту верхнеуровневую независимость, делающую
возможной выполнение программы, описываемой графами, на ЭВМ
МКОД между графами и программами для ЦП и СП имеются зависи-
мости по данным, показанные наличием вершин передачи данных
x
←
и
x
→
в графах. Снижение числа вершин передачи данных может рас-
сматриваться как один из критериев качества получаемого разбиения
информационного графа последовательной программы на два графа.
Рассмотрим некоторые ключевые преимущества и недостатки про-
веденной декомпозиции информационного графа последовательной
программы для ЭВМ МКОД (таблица).
Проведенная декомпозиция в полной мере позволяет решить за-
дачу декомпозиции информационного графа последовательной про-
граммы для ЭВМ МКОД. Тем не менее декомпозиция обладает не-
достатками, устранение которых позволит получить более качествен-
ное разбиение информационного графа последовательного алгоритма.
Возможности улучшения способов декомпозиции информационного
графа будут рассмотрены в будущих работах.
Подход к программной реализации методики декомпозиции
информационного графа программы для ЭВМ МКОД.
Для про-
граммной реализации описанной методики декомпозиции информа-
ционного графа последовательной программы для ЭВМ МКОД бы-
ло применено аналитическое описание графов и операций над ними.
Основные типы графов и их компоненты, операции над ними на языке
теории множеств, а также подходы к визуализации описаны в пакетах
“graph” и “Rgraphviz” интерпретируемого языка программирования R,
предназначенного для анализа массивов и структур данных [10, 11].
Методика декомпозиции была реализована на языке R и протестирова-
на на примере графа, представленного на рис. 2. В результате тестиро-
вания получены части информационного графа алгоритма, показанные
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1 123