МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ
ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ
МАШИН, КОМПЛЕКСОВ И
КОМПЬЮТЕРНЫХ СЕТЕЙ
DOI: 10.18698/0236-3933-2016-1-112-128
УДК 004.2:004.31
МЕТОДИКА ДЕКОМПОЗИЦИИ ИНФОРМАЦИОННОГО ГРАФА
ПРОГРАММЫ ДЛЯ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ
ДАННЫХ НА ЭВМ МКОД
В.Э. Подольский
1
,
2
,
А.Ю. Попов
1
1
МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
e-mail:
alexpopov@bmstu.ru2
ИБС Софт, Москва, Российская Федерация
e-mail:
v.e.podolskiy@gmail.comВ МГТУ им. Н.Э. Баумана разрабатывается принципиально новая вычислитель-
ная система со многими потоками команд и одним потоком данных (МКОД),
в составе которой имеются аппаратные средства для ускорения алгорит-
мов дискретной оптимизации. В ходе проведенных исследований полученной
системы стало очевидно, что для ее эффективного внедрения необходимо мо-
дифицировать существующие алгоритмы и адаптировать их под архитек-
турные особенности МКОД-системы. Однако модификация каждого после-
довательного алгоритма к требуемому параллельному виду является трудо-
емким процессом. Поэтому актуальна разработка формальных подходов для
автоматизированного преобразования алгоритмов. Предложен способ пред-
ставления алгоритма МКОД в виде графовой модели, показано решение задачи
декомпозиции информационного графа последовательной программы на графы
арифметико-логической обработки и обработки структур данных, приведен
пример представления информационного графа алгоритма на языке
R
.
Ключевые слова
:
МКОД-система, процессор обработки структур, информаци-
онный граф алгоритма, декомпозиция графа.
GRAPH DECOMPOSITION FOR PARALLEL DATA PROCESSING
ON MISD COMPUTER
V.E. Podolsky
1
,
2
,
A.Yu. Popov
1
1
Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail:
alexpopov@bmstu.ru2
IBS Soft, Moscow, Russian Federation
e-mail:
v.e.podolskiy@gmail.comA conceptually new computing system dealing with multiple instruction stream
and single data stream (MISD) is being developed at Bauman Moscow State
Technical University. The system contains the hardware to accelerate discrete
optimization algorithms. The MISD studies resulted in the conclusion that its effective
implementation demands to modify the occurring algorithms and adapt them to the
112 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1