Методика декомпозиции информационного графа программы для организации параллельной обработки данных на ЭВМ МКОД

В МГТУ им. Н.Э. Баумана разрабатывается принципиально новая вычислительная система со многими потоками команд и одним потоком данных (МКОД), в составе которой имеются аппаратные средства для ускорения алгоритмов дискретной оптимизации. В ходе проведенных исследований полученной системы стало очевидно, что для ее эффективного внедрения необходимо модифицировать существующие алгоритмы и адаптировать их под архитектурные особенности МКОД-системы. Однако модификация каждого последовательного алгоритма к требуемому параллельному виду является трудоемким процессом. Поэтому актуальна разработка формальных подходов для автоматизированного преобразования алгоритмов. Предложен способ представления алгоритма МКОД в виде графовой модели, показано решение задачи декомпозиции информационного графа последовательной программы на графы арифметико-логической обработки и обработки структур данных, приведен пример представления информационного графа алгоритма на языке R.

Литература

[1] Clements A. Principles of Computer Hardware. OUP Oxford, 2006. 672 p.

[2] Попов А.Ю. Электронная вычислительная машина с многими потоками команд и одним потоком данных. Пат. № 71016. Российская Федерация. 2008. Бюл. № 5.

[3] Попов А.Ю. Электронная вычислительная машина с аппаратной поддержкой операций над структурами данных // Аэрокосмические технологии. 2009. Т. 1. Тр. Второй Междунар. научно-техн. конф., посвященной 95-летию со дня рождения академика В.Н. Челомея. ВПК "НПО машиностроения". МГТУ им. Н.Э. Баумана. Москва, 2012. С. 296-301.

[4] Попов А.Ю. Применение вычислительных систем с многими потоками команд и одним потоком данных для решения задач оптимизации // Инженерный журнал: наука и инновации. 2012. Вып. 1. URL: http://engjournal.ru/catalog/it/hidden/80.html

[5] Попов А.Ю. О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 9. С. 162-180. URL: http://technomag.bmstu.ru/doc/726416.html DOI: 10.7463/0914.0726416

[6] Подольский В.Э. Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование. МГТУ им. Н.Э. Баумана. 2015. № 4. URL: http://technomag.bmstu.ru/doc/764268.html

[7] Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 423 с.

[8] Овчинников В.А., Иванова Г.С. Методика формального синтеза комбинированных структур данных для представления графов // Инженерный журнал: наука и инновации. 2012. № 1. С. 135-145. URL: http://engjournal.ru/articles/79/79.pdf DOI: 10.18698/2308-6033-2012-1-79

[9] Овчинников В.А., Иванова Г.С. Оптимизирующие преобразования алгоритмов, использующие свойства множеств, предикатов и операций над нами // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2013. № 4. С. 53-66.

[10] Gentleman R., Whalen E., Huber W., Falcon S. Graph: graph: A package to handle graph data structures. R package version 1.44.1. Technical document. May 2015. URL: http://www.bioconductor.org/packages/release/bioc/manuals/graph/man/graph.pdf (дата обращения: 25.05.2015).

[11] Hansen K.D., Gentry J., Long L., Gentleman R., Falcon S., Hahne F., Sarkar D. Rgraphviz: Provides plotting capabilities for R graph objects. R package version 2.10.0. Technical document. May 2015. URL: http://master.bioconductor.org/packages/release/bioc/manuals/Rgraphviz/man/Rgraphviz.pdf (дата обращения: 25.05.2015).