Машиностроение
Приборостроение
Методическая периодика: проблемы и решения
Организация производства (промышленность)

Ключевые слова
Аннотации
Архив рубрик

регистрация
забыли пароль?

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

электронный научно-технический журнал

ИНЖЕНЕРНЫЙ ВЕСТНИК

Издатель: Общероссийская общественная организация "Академия инженерных наук им. А.М. Прохорова".

Структура данных для представления графов на параллельных вычислительных системах и параллельные алгоритмы операций над графами

Инженерный вестник # 11, ноябрь 2014
УДК: 004.051+519.168

Файл статьи:

Ivanova_G.pdf (1292.87Кб)

авторы: Головков А. А., профессор Иванова Г. С.

В данной статье с целью увеличения быстродействия алгоритмов решения графовых задач выполнен анализ структур данных, используемых для представления графов в машинной памяти, и предложена структура, ориентированная на параллельные вычислительные системы. Описаны необходимые свойства такой структуры. Оценена ее емкостная сложность, выявлены достоинства и недостатки. Приведена реализация параллельного алгоритма операции добавления вершины в граф на основе предложенной структуры на графическом процессоре CUDA. Выполнено сравнение времен работы последовательного и параллельного алгоритмов рассматриваемой операции. Экспериментальные данные позволили сделать вывод об эффективности применения параллельных операций с использованием предлагаемой структуры данных для представления графов, ориентированной на параллельные вычислительные системы.

Список литературы
1.    Овчинников В.А., Иванова Г.С., Ничушкина Т.Н. Выбор структур данных для пред-ставления графов при решении комбинаторно-оптимизационных задач // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. 2001. № 2(43). C. 39-51.
2.    Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 10. Режим доступа: http://technomag.bmstu.ru/doc/132769.html (дата обращения 12.08.2014).
3.    Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем (часть 2) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 11. Режим доступа: http://technomag.bmstu.ru/doc/133223.html (дата обращения 12.08.2014).
4.    Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем (часть 3) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 12. Режим доступа: http://technomag.bmstu.ru/doc/134335.html (дата обращения 12.08.2014).
5.    Rob Farber. CUDA Application Design and Development. Waltham: Morgan Kaufmann, MA, USA. 2011. 336 p.