Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408
Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных
# 04, апрель 2015 DOI: 10.7463/0415.0764268
Файл статьи:
SE-BMSTU...o214.pdf
(1553.35Кб)
В работе рассмотрена реализация алгоритмов Беллмана-Форда и Ли поиска кратчайшего пути в графе для вычислительной системы ЭВМ с многими потоками команд и одним потоком данных (МКОД). ЭВМ МКОД представляет собой ЭВМ, параллельно выполняющую команды арифметико-логической обработки (на центральном процессоре) и команды обработки структур (на процессоре структур) над одним потоком данных. Преобразование последовательных программ в программы для ЭВМ МКОД является трудоёмким процессом, поскольку требует вручную отделять поток арифметико-логической обработки от потока обработки структур. Алгоритмы, базирующиеся на обработке структур данных (например, алгоритмы на графах), показывают высокую производительность на ЭВМ МКОД. К таким алгоритмам относятся алгоритмы Беллмана-Форда и Ли поиска кратчайшего пути в графе, применяющиеся в робототехнике для автоматического планирования движения робота на местности. В рамках статьи впервые получена модификация алгоритмов Беллмана-Форда и Ли поиска кратчайшего пути в режиме сопроцессора МКОД, а также параллельная версия в режиме МКОД. Таким образом, настоящая статья продолжает ряд работ по исследованию преобразований последовательных алгоритмов в алгоритмы для ЭВМ МКОД (алгоритмы Дейкстры и Форда-Фалкерсона) и имеет ярко выраженный прикладной характер. Также в статье представлены результаты анализа алгоритмов Беллмана-Форда и Ли в режиме МКОД. Сформулированы основные направления развития методики распараллеливания алгоритмов на поток арифметико-логической обработки и поток обработки структур. В числе ключевых направлений будущих исследований выделено развитие математического подхода для последующей формализации и автоматизации процесса распараллеливания последовательных алгоритмов между процессором структур и центральным процессором МКОД. К числу математических моделей, которые могут быть использованы в будущих исследованиях, относятся графовые модели алгоритмов (например, граф зависимостей программы). В связи с высокой трудоёмкостью ручного распараллеливания последовательных программ для ЭВМ МКОД автоматическое распараллеливание становится ключевой задачей для развития новой архитектуры МКОД. Базис для решения этой задачи заложен в данной работе. Список литературы
Публикации с ключевыми словами: много потоков команд и один поток данных, процессор обработки структур, алгоритм Беллмана-Форда, алгоритм Ли, МКОД Публикации со словами: много потоков команд и один поток данных, процессор обработки структур, алгоритм Беллмана-Форда, алгоритм Ли, МКОД Смотри также:
Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||||
|