НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o180.pdf (520.17Кб)

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

1. Попов А.Ю. Электронная вычислительная машина с многими потоками команд и одним потоком данных: пат. 71016 РФ. 2008. Бюл. № 5. 1 с.
2. Попов А.Ю. Реализация электронной вычислительной машины с аппаратной поддержкой операций над структурами данных // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2011. Спец. вып. Информационные технологии и компьютерные системы. С. 83-87.
3. Попов А.Ю. Электронная вычислительная машина с аппаратной поддержкой операций над структурами данных // Аэрокосмические технологии: тр. Второй Междунар. науч.-техн. конф., посвященной 95-летию со дня рождения академика В.Н. Челомея (РФ, Москва-Реутов, 19-20 мая 2009 г.). Т. 1/ ОАО «ВПК «НПО машиностроения»; МГТУ им. Н.Э. Баумана. М.: МГТУ им. Н.Э. Баумана, 2009. С. 296-301.
4. Попов А.Ю. Применение вычислительных систем с многими потоками команд и одним потоком данных для решения задач оптимизации // Инженерный журнал: наука и инновации. 2012. № 1. Режим доступа: http://engjournal.ru/catalog/it/hidden/80.html (дата обращения 01.08.2014).
5. Попов А.Ю. Исследование производительности процессора обработки структур в системе с многими потоками команд и одним потоком данных // Инженерный журнал: наука и инновации. 2013. № 11. Режим доступа: http://engjournal.ru/catalog/it/hidden/1048.html (дата обращения 01.08.2014).
6. Кнут Д. Искусство программирования. В 3 т. Т. 3. Сортировка и поиск: пер. с англ. 2-е изд. М.: Вильямс, 2000. 832 с.
7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2000. 960 с.
8. Попов А.Ю. Модели и алгоритмы автоматизированной декомпозиции схем ЭВМ: дис. … канд. техн. наук. М., 2003. 176 с.