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

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

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

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

Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных

# 04, апрель 2015
DOI: 10.7463/0415.0764268
Файл статьи: SE-BMSTU...o214.pdf (1553.35Кб)
автор: Подольский В. Э.

УДК 004.2; 004.31

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

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

Список литературы
  1. Носков В.П., Рубцов И.В. Ключевые вопросы создания интеллектуальных мобильных роботов // Инженерный журнал: наука и инновации. 2013. № 3. Режим доступа:http://engjournal.ru/catalog/pribor/robot/629.html (дата обращения 01.03.2015).
  2. Евсеев А.А., Носков В.П., Платонов А.К. Электронная карта в системе управления автономным движением мобильного робота // Известия Тульского государственного университета. Сер. Вычислительная техника, информационные технологии, системы управления. 2006. Т. 1, вып. 3 «Системы управления». С. 166-169.
  3. Каляев А.В., Носков В.П., Чернухин Ю.В. Алгоритм управляющей структуры транспортного робота // Известия АН СССР. Техническая кибернетика . 1980. № 4. С. 64-72.
  4. Cherkassky B.V., Goldberg A.V., Radzik T. Shortest paths algorithms: theory and experimental evaluation // Mathematical Programming. Ser. A. 1996. Vol. 73, no. 2. P. 129-174. DOI: 10.1016/0025-5610(95)00021-6
  5. Abraham I., Fiat A., Goldberg A.V., Werneck R.F. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms // Proc. of the 21 annual ACM-SIAM Symposium on Discrete Algorithms (SODA’10). SIAM, 2010. P. 782-793.
  6. Abraham I., Delling D., Goldberg A.V., Werneck R.F. A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks // In: Experimental Algorithms. Proc. 10thInternational Symposium on Experimental Algorithms (SEA 2011). Springer Berlin Heidelberg , 2011. P. 230-241. DOI: 10.1007/978-3-642-20662-7_20
  7. Thorup M. Undirected single-source shortest paths with positive integer weights in linear time // Journal of the ACM (JACM). 1999. Vol . 46, no . 3. P . 362 - 394. DOI: 10.1145/316542.316548
  8. Попов А.Ю. Применение вычислительных систем с многими потоками команд и одним потоком данных для решения задач оптимизации // Инженерный журнал: наука и инновации. 2012. № 1. Режим доступа: http://engjournal.ru/catalog/it/hidden/80.html (дата обращения 01.03.2015).
  9. Попов А.Ю. О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных // Наука и Образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 9. С . 162-180. DOI: 10.7463/0914.0726416
  10. Харари Ф. Теория графов: пер. с англ. / под ред. Г.П. Гаврилова. М.: УРСС: ЛЕНАНД, 2015. 304 с.
  11. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных. Н. Новгород: Изд-во Нижегородского гос. ун-та, 2005. 307 с.
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



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