Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных

# 09, сентябрь 2014
DOI: 10.7463/0914.0726416
Файл статьи: SE-BMSTU...o180.pdf (520.17Кб)
автор: Попов А. Ю.

УДК 004.2; 004.31

Россия,  МГТУ им. Н.Э. Баумана

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

Список литературы
  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 с.
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2022 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)