|
Вычислительные методы и программирование, 2013, том 14, выпуск 3, страницы 54–62
(Mi vmp152)
|
|
|
|
Программирование
Балансировка нагрузки в ГПУ-реализации поиска в ширину на графе
М. А. Черноскутов, Д. Г. Ермаков Институт математики и механики им. Н.Н Красовского Уральского отделения РАН (ИММ УрО РАН)
Аннотация:
Параллельная обработка неструктурированных данных, представленных в виде графов, может вызвать серьезные трудности из-за значительных накладных расходов, обусловленных как нерегулярной природой графовых алгоритмов, так и аппаратными задержками интенсивного обращения к памяти вычислительной системы. Предложен метод балансировки нагрузки, реализованный на ГПУ и позволяющий существенно ускорить параллельную реализацию поиска в ширину на графе по сравнению со своим стандартным последовательным аналогом на ЦПУ. Работа поддержана грантами РФФИ 14-07-00435, УрО РАН 12-П-1-1029 и РЦП-13-П18. При проведении работ был использован суперкомпьютер “Уран” ИММ УрО РАН. Статья рекомендована к публикации Программным комитетом Международной научной конференции “Научный сервис в сети Интернет: все грани параллелизма” (http://agora.guru.ru/abrau2013).
Ключевые слова:
поиск в ширину; параллельный алгоритм; графические процессоры.
Поступила в редакцию: 25.08.2013
Образец цитирования:
М. А. Черноскутов, Д. Г. Ермаков, “Балансировка нагрузки в ГПУ-реализации поиска в ширину на графе”, Выч. мет. программирование, 14:3 (2013), 54–62
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmp152 https://www.mathnet.ru/rus/vmp/v14/i3/p54
|
|