13 / 17
Преимущества и недостатки декомпозиции информационного графа
программы (алгоритма) для ЭВМ МКОД
Преимущество
Недостаток
Способ устранения
недостатка
Возможность автоматиче-
ского проведения деком-
позиции информационно-
го графа.
Отсутствие единого кри-
терия оценки качества
полученного разбиения
информационного графа
программы.
Использование различных
критериев для оценки ка-
чества разбиения.
Высокоуровневое пред-
ставление программы по-
зволяет быстро выявлять
и устранять основные
зависимости частей де-
композируемого графа, а
также обеспечивать на-
глядное представление ре-
зультата для последующе-
го анализа.
Сложность обнаружения
проблем, связанных с рас-
параллеливанием на уров-
не команд (связи по дан-
ным между итерациями
циклов и пр.).
После (или во время)
декомпозиции проведение
модификации получен-
ных частей программы с
помощью существующих
средств анализа и устра-
нения зависимостей по
данным на низком уровне.
Использование минималь-
ного числа разновидно-
стей и вспомогательных
вершин в процессе деком-
позиции.
Не учитывается вариант
частичного выполнения
СП операторов обработки
структур данных.
Модификация и примене-
ние декомпозиции с пере-
носом в граф
G
AS
различ-
ных наборов вершин об-
работки структур данных
с последующим выбором
наиболее оптимальной де-
композиции согласно не-
которому критерию.
на рис. 4. Графы изоморфны соответствующим графам, приведенным
на рис. 3 (пакет “Rgraphviz” накладывает определенные ограничения
на визуализацию графов, поэтому получить визуально идентичные
графы невозможно). Формальное доказательство изоморфизма будет
проведено в будущих работах.
Для выполнения действий алгоритма на языке R над исходным
графом были заданы следующие атрибуты вершин графов:
•
GlobalT ype
=
{
instruction, data
}
— тип вершины (оператор,
данные);
•
T ypeOfData
=
{
simple, structure
}
— тип данных вершины, ли-
бо тип данных, обрабатываемых оператором в вершине (прими-
тивный, структурный);
•
T ypeOfNode
=
{
datanode, terminal, assignment, ComputeAnd
Condition, mergepoint, splitpoint, send, receive, tag, TEMP
}
—
тип вершины в графе (обычная вершина данных, терминальная
вершина, вершина присваивания, вершина вычисления условия
и ветвления, вершина слияния потоков управления, вершина
ветвления, вершина передачи данных другому процессору, вер-
шина получения данных от другого процессора, вершина тега,
вершина временных данных примитивного типа).
124 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1