Балансировка нагрузки в ГПУ-реализации поиска в ширину на графе
Черноскутов М.А., Ермаков Д.Г.

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

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

Название статьи, аннотация и ключевые слова на английском языке

Черноскутов М.А., ст. программист, e-mail: mach@imm.uran.ru;   Ермаков Д.Г., ст. науч. сотр., e-mail: ermak@imm.uran.ru – Институт математики и механики им. Н.Н. Красовского Уральского отделения РАН (ИММ УрО РАН), ул. Софьи Ковалевской, 16, 620990, г. Екатеринбург