Балансировка нагрузки в ГПУ-реализации поиска в ширину на графе

Авторы

  • М.А. Черноскутов
  • Д.Г. Ермаков

Ключевые слова:

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

Аннотация

Параллельная обработка неструктурированных данных, представленных в виде графов, может вызвать серьезные трудности из-за значительных накладных расходов, обусловленных как нерегулярной природой графовых алгоритмов, так и аппаратными задержками интенсивного обращения к памяти вычислительной системы. Предложен метод балансировки нагрузки, реализованный на ГПУ и позволяющий существенно ускорить параллельную реализацию поиска в ширину на графе по сравнению со своим стандартным последовательным аналогом на ЦПУ. Работа поддержана грантами РФФИ 14–07–00435, УрО РАН 12–П–1–1029 и РЦП–13–П18. При проведении работ был использован суперкомпьютер «Уран» ИММ УрО РАН. Статья рекомендована к публикации Программным комитетом Международной научной конференции «Научный сервис в сети Интернет: все грани параллелизма» (http://agora.guru.ru/abrau2013).

Новые вычислительные технологии

Загрузки

Опубликован

2013-09-17

Выпуск

Том 14 (2013): Выпуск 3.

Раздел

Раздел 2. Программирование

Авторы

М.А. Черноскутов

Д.Г. Ермаков

Библиографические ссылки

  1. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to algorithms. Cambridge: MIT Press, 2001.
  2. Merril D., Garland M., Grimshaw A. High performance and scalable GPU graph traversal. Technical Report CS-2011-05. Charlottesville: University of Virginia, 2011.
  3. Luo L., Wong M., Hwu W. An effective GPU implementation of breadth-first search // Proc. of the 47th Design Automation Conference. New York: ACM Press, 2010. 52-55.
  4. Harish P., Narayanan P.J. Accelerating large graph algorithms on the GPU using CUDA // Proc. of the 14th International Conference on High Performance Computing. Berlin: Springer, 2007. 197-208.
  5. Hong S., Kim S.K., Oguntebi T., Olukotun K. Accelerating CUDA graph algorithms at maximum warp // Proc. of the 16th ACM Symposium on Principles and Practice of Parallel Programming. New York: ACM Press, 2011. 267-276.
  6. 10th DIMACS Implementation Challenge (http://www.cc.gatech.edu/dimacs10/index.shtml).
  7. Leskovec J., Chakrabarti D., Kleinberg J.M., Faloutsos C. Realistic, mathematically tractable graph generation and evolution using Kronecker multiplication // Proc. of the Conference on Principles and Practice of Knowledge Discovery in Databases. Porto, 2005. 133-145.
  8. Murphy R., Wheeler K., Barrett B., Ang J. Introducing the Graph 500. Cray User’s Group (CUG). Albuquerque: Sandia National Laboratory, 2010.