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

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