Реализация алгоритма BFS на GPU

Аннотация

В данной статье хочу рассказать как можно эффективно распараллелить алгоритм BFS — поиск в ширину в графе с использованием графических ускорителей. В статье будет приведен подробный анализ полученного алгоритма. Вычисления выполнялись на одном GPU GTX Titan архитектуры Kepler.

Введение

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Решение данной задачи рассмотрено мной в этой статье. Вторым примером задачи на неструктурных сетках является задача Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. Также она немного проще, чем поиск кратчайшего пути. На данный момент алгоритм BFS используется как основной тест для рейтинга Graph500. Далее рассмотрим, как можно использовать идеи решения задачи SSSP в задаче BFS. Про архитектуру GPU компании Nvidia и об упомянутых алгоритмах уже много написано, поэтому в этой статье я не стану дополнительно писать про это. Так же, надеюсь, что понятия warp, cuda блок, SMX, и прочие базовые вещи, связанные с CUDA читателю знакомы.

Формат используемых данных

Так же как и в задаче SSSP будем использовать те же самые преобразования, для того, чтобы увеличить нагрузку на один SMX и снизить количество одинаковых данных, находящихся в глобальной памяти GPU. Основное отличие — для алгоритма BFS не нужны веса в графе. Так же стоит отметить, что нам необходимо хранить не кратчайшие расстояния, а номер уровня, в котором находится данная вершина:

После проведения тестовых запусков выяснилось, что количество уровней в RMAT графах со средней степенью связности 32 не превосходит 10. Поэтому для хранения данных значений будет достаточно unsigned char. Тем самым массив уровней будет занимать в 8 раз меньше места, чем массив расстояний, что очень важно, так как размер кэша в архитектуре Kepler всего 1,5МБ.

Реализация алгоритма на CPU

На CPU был реализован нативный вариант алгоритма обхода в ширину, а именно создание очереди еще не просмотренных вершин. Код CPU реализации выглядит следующим образом:

queue<vertex_id_t> q;
bool *used = new bool[G->n];
for (unsigned i = 0; i < G->n; ++i)
	used[i] = false;
used[root] = true;
q.push(root);
dist[root] = 0;
while (!q.empty())
{
	vertex_id_t nextV = q.front();
	q.pop();
	for (unsigned k = G->rowsIndices[nextV]; k < G->rowsIndices[nextV + 1]; ++k)
	{
		if (used[G->endV[k]] == false)
		{
			used[G->endV[k]] = true;
			q.push(G->endV[k]);
			dist[G->endV[k]] = dist[nextV] + 1;
		}
	}
}

Данный код достаточно прост и, вполне возможно, не оптимален. Он был использован для проверки правильности работы алгоритма на GPU. Цели написать оптимальный алгоритм на CPU не было, поэтому производительность на CPU будет получена данным алгоритмом. Хочу добавить, что на данный момент оптимальных CPU реализаций много и их легко найти. Также предложено множество других подходов и идей реализации алгоритма BFS.

Реализация алгоритма на GPU

За основу реализации был взят все тот же алгоритм Форда-Беллмана и ядро в рассмотренной задаче SSSP. Основное вычислительное ядро для BFS будет выглядеть следующим образом:

if(k < maxV)
{
	unsigned en = endV[k];
	unsigned st = startV[k];
	if(levels[st] == iter)
	{
		if(levels[en] > iter)
		{
			levels_NR[en] = iter + 1;
			modif[0] = iter;
		}
	}
	else if(levels[en] == iter)
	{
		if(levels[st] > iter)
		{
			levels_NR[st] = iter + 1;
			modif[0] = iter;
		}
	}
}

Идея алгоритм в следующем. Пусть массив levels изначально заполнен максимальным для выбранного типа значением (255 для unsigned char). Будем передавать в ядро номер текущей итерации — iter. Далее необходимо просмотреть все ребра и проверить, является ли начальная или конечная вершина текущим родителем, то есть принадлежит ли она уровню iter. Если да, то необходимо пометить противоположную вершину просматриваемой дуги значением на единицу больше, чтобы «включить» эту вершину в список родителей на следующей итерации. Также как и в SSSP, остается переменная modif, показывающая необходимость продолжения разметки графа.
Данный код уже содержит примененные оптимизации в задаче SSSP — использование const __restrict для массива levels и использование другой ссылки levels_NR, указывающей на тот же самый участок памяти, необходимой для записи. Вторая оптимизация в виде перестановки для лучшей локализации данных в кэше тоже была использована. Для алгоритма BFS длина оптимальной кэш линии равна 1024КБ или примерно 1млн элементам массива levels (1024 * 1024) независимо от размера графа.

Анализ полученных результатов

Для тестирования использовались синтетические неориентированные RMAT-графы, которые хорошо моделируют реальные графы из социальных сетей и Интернета. Графы имеют среднюю связность 32, количество вершин является степень двойки. В таблице ниже приведены графы, на которых проводилось тестирование:

Из-за использования самого маленького типа данных для хранения значений уровня, для графа с количеством вершин 2²⁰ необходимо 1МБ для кэширования массива levels, в то время как для такого же графа в задаче SSSP необходимо 8МБ. Тестирование производилось на GPU Nividia GTX Titan, у которого 14 SMX и 2688 CUDA-ядер и на процессоре Intel core i7 3го поколения с частотой 3,4ГГц и 8МБ кэша. Для сравнения производительности на CPU использовалась нативная реализация алгоритм поиска в ширь. Никаких оптимизаций в виде перестановки данных перед работой на CPU не производились. Вместо времени показателем производительности будем считать количество дуг, обработанных за секунду времени. В данном случае, необходимо поделить полученное время на количество дуг в графе. В качестве конечного результата бралось среднее значение по 32 точкам. Также вычислялись максимальное и минимальное значения. Для компиляции использовались компиляторы Intel 13й версии и NVCC CUDA 5.5 с флагами –O3 –arch=sm_35.
График средней производительности различных вариантов на GPU и CPU выглядит следующим образом:

На данном графике изображены кривые средней производительности для следующих алгоритмов:

• cache && restrict on — алгоритм GPU со всеми оптимизациями (1)
• cache off — алгоритм GPU без оптимизации перестановок для улучшенного кэширования (2)
• restrict off — алгоритм GPU без оптимизации текстурного кэша (3)
• cache && restrict off — базовый алгоритм GPU без оптимизаций (4)
• CPU — базовый алгоритм на CPU

Первое, что бросается в глаза — одинаковое поведение алгоритмов (1) — (2) и (3) — (4). Как было отмечено выше, это связано с тем, что массив levels для графов с количеством вершин до 2²⁰ помещается в L2 кэш. Поэтому можно не делать перестановку дуг, если рассматривать алгоритмы (1) и (2), и не использовать текстурный кэш в случае (3) и (4).
Далее, можно заметить, что как только массив levels не помещается в L2 кэш, отключение перестановки дает сильный проигрыш в производительности, несмотря на то, что используется const __restrict. Это связано прежде всего со случайным доступом в массив levels. Аналогичная картина наблюдается и в случае отключения опции const __restirict.
Не плавный график в районе степеней 15-16-17 для самого лучшего алгоритма — следствие еще одной маленькой оптимизации — упаковки двух вершин одной дуги в одну переменную типа unsigned int. Так как максимальный номер вершины занимает 16 бит, а unsigned int — 32 бита, то можно упаковать данные о ребре заранее в один unsigned int, а в ядре делать его распаковку, считывая при этом в два раза меньше данных из глобальной памяти GPU.
В итоге, удалось достичь средней производительности в 3,6 GTEPS. Почти пиковая средняя производительность достигается на графах с количеством вершин 2¹⁶ — 2²³, что довольно не плохо для данной архитектуры. Максимальная производительность получена на графе с количеством вершин 2¹⁹ — 4,2 GTEPS.
Полученное ускорение по сравнению с нативной реализацией на CPU оказалось весьма не однозначным:

Общая тенденция видна — постепенный рост ускорения. Скорее всего это связано с не эффективной реализаций и ограниченным размером кэша CPU.

Детальный анализ реализованного ядра

В заключение хотел бы показать на сколько эффективен данный подход с точки зрения использования ресурсов GPU. Данный раздел представлен только для интереса и, может быть, для тех, кто в будущем захочет сравнить свой алгоритм с тем, что приведен в данной статье. Рассмотрим детально все то, что выводит профилировщик NVVP для двух графов — 2¹⁹ и 2²². Я выбрал такие графы, потому что у первого массив levels полностью помещается в L2 кэш, а у второго нет. В начале рассмотрим общую информацию:

Учитывалось копирование массивов вершин на GPU до начала счета и копирование результата на CPU после окончания. Из таблицы видно, что копирование занимает примерно в два раза больше времени, чем весь счет. Далее рассмотрим по итерациям для каждого графа.

Граф 2¹⁹

Расшифровка:

• GL Eff — Global Load efficiency
• GS Eff — Global Store efficiency
• WE Eff — Warp Execution efficiency
• NP WE Eff — Non-predicated Warp Execution efficiency
• Occupancy — количество реально активных варпов / максимальное количество варпов на SMX

Из таблицы видно, что наибольшее количество вершин обрабатывается на 3 и 4 итерациях. Из-за этого на 4й итерации виден спад использования пропускной способности L2 и глобальной памяти GPU. Стоит отметить, что по специфике алгоритма на последней итерации не происходит никаких записей. Она необходима для определения завершенности разметки графа. Эффективность исполнения варпов находится в пределах 93-100 % и 85% на самой «загруженной» итерации.
Для сравнения, ниже приведена таблица для графа с 2²² вершинами, размер массива levels которого не помещается целиком в L2 кэш GPU.

Граф 2²²

Расшифровка приведена выше. На данном графе наблюдается примерно такая же картина, как и на 2¹⁹. Пик приходится на 4-5 итерации. По мнению профилировщика NVVP пропускная способность L2 кэша 560 GB/s является высокой (есть низкая, средняя, высокая, максимальная), а глобальной памяти 117 GB/s является средней (есть низкая, средняя, высокая, максимальная).

Заключение

В результате проделанной работы был реализован и оптимизирован алгоритм поиска в ширину на RMAT-графах со средней степенью связности вершин 32. Была достигнута пиковая производительность 4,2 GTEPS и средняя 3,6 GTEPS. Как известно, важна не только производительность, но и энергоэффективность. Наряду с рейтингом Graph500 есть рейтинг Green Graph500, показывающий энергоэффективность. Самое первое место в рейтинге Graph500 по производительности на март 2014 года занимает BlueGene/Q, Power BQC 16C 1.60 GHz с количеством ядер 1048576 и количеством узлов 65536 с производительностью 15363 GTEPS. Потребляемая мощность такой системы составляет 340kW (взято из рейтинга топ 500). Эффективность полученного результата GTEPS/ kW для BlueGene/Q составляет 45. Для реализованного мной алгоритма получается порядка 18 (для расчета бралась общая мощность в 200Вт и средняя производительность 3,6 GTEPS, так как в работе участвует всего одно ядро CPU из 4х и пиковая нагрузка на GPU не достигается).
Еще хотелось бы отметить, что в рейтинге Graph500 есть похожая система Xeon E5-2650 v2, GeForce GTX TITAN, которая на графе 2²⁵ получила производительность в 17 GTEPS. К сожалению информации о том, какой был использован граф не приведена. На март 2014 года эта система находится на 58 позиции в рейтинге.

Автор: ALEX_k_s

Источник