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

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

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

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

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

# 11, ноябрь 2014
DOI: 10.7463/1114.0741563
Файл статьи: SE-BMSTU...o554.Pdf (1005.85Кб)
авторы: профессор Иванова Г. С., Головков А. А.

УДК 004.051+519.168

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

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

Список литературы
  1. Овчинников В.А., Иванова Г.С., Ничушкина Т.Н. Выбор структур данных для представления графов при решении комбинаторно-оптимизационных задач // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2001. № 2 (43). C. 39-51.
  2. Иванова Г.С. Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычислительной техники: дис. … докт. техн. наук. М., 2007. 416 с.
  3. Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 10. Режим доступа: http://technomag.bmstu.ru/doc/132769.html (дата обращения 20.10.2014).
  4. Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем (часть 2) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 11. Режим доступа: http://technomag.bmstu.ru/doc/133223.html (дата обращения 20.10.2014).
  5. Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем (часть 3) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 12. Режим доступа: http://technomag.bmstu.ru/doc/134335.html (дата обращения 20.10.2014).
  6. Головков А.А. Представление графовых моделей в системах параллельной обработки // Молодежный научно-технический вестник. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 7. Режим доступа: http://sntbul.bmstu.ru/doc/727773.html (дата обращения 20.10.2014).
  7. Чернышев С.В. Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах больших размерностей: дис. … канд. техн. наук. М., 2011. 116 с.
  8. Leskovec J., Huttenlocher D., Kleinberg J. Predicting Positive and Negative Links in Online Social Networks // Proceedings of the 19th International Conference on World Wide Web (WWW’10). ACM, 2010. P. 641-650. DOI:10.1145/1772690.1772756
  9. Bullmore E., Sporns O. Complex brain networks: graph theoretical analysis of structural and functional systems // Nature Reviews Neuroscience. 2009. Vol. 10, no. 3. P. 186-198. DOI: 10.1038/nrn2575.
  10. deLorimier M. GRAph Parallel Actor Language — A Programming Language for Parallel Graph Algorithms. PhD Thesis. California Institute of Technology, Pasadena, California, 2013. 151 p. Available at: http://thesis.library.caltech.edu/7188/2/delorimier_Michael_2013.pdf, accessed 20.10.2014.
  11. Xin R.S., Crankshaw D., Crankshaw D., Dave A., Gonzalez J.E., Franklin M.J., Stoica I. GraphX: Unifying Data-Parallel and Graph-Parallel Analytics. UC Berkeley AMPLab, 2014. 5 p. Available at: http://www.researchgate.net/publication/260147249_GraphX_Unifying_Data-Parallel_and_Graph-Parallel_Analytics, accessed 20.10.2014.
  12. Harish Pawan, Narayanan P.J. Accelerating Large Graph Algorithms on the GPU Using CUDA // In: High Performance Computing –Proceedings of the 14th international conference on High performance computing (HiPC’07) / S. Aluru, et al. (eds.) . Springer Berlin Heidelberg, 2007. P. 197-208. (Ser. Lecture Notes in Computer Science; vol. 4873). DOI: 10.1007/978-3-540-77220-0_21
  13. Merrill D., Garland M., Grimshaw A. Scalable GPU Graph Traversal // Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPoPP'12). ACM, 2012. P. 117-128. DOI:10.1145/2145816.2145832
Поделиться:
 
ПОИСК
 
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)