Решение задачи поиска минимальных остовных деревьев ( mst minimum spanning tree) является распространенной задачей в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей

Масштаб (2^N)	Количество вершин	Количество ребер (2 * M)
Размер графа, ГБ
		RMAT	SSCA2
16	65 536	2 097 152	~2 100 000	~ 0.023
21	2 097 152	67 108 864	~67 200 000	~ 0.760
24	16 777 216	536 870 912	~537 000 000	~ 6.3
25	33 554 432	1 073 741 824	~1 075 000 000	~ 12.5
26	67 108 864	2 147 483 648	~2 150 000 000	~ 25.2
27	134 217 728	4 294 967 296	~4 300 000 000	~ 51.2

Видно, что граф масштаба 16 достаточно мал (порядка 25 МБ) и даже без преобразований легко помещается в кэш одного современного процессора Intel Xeon. А так как веса графа занимают 2/3 от общего количества, то фактически необходимо обрабатывать порядка 8 МБ, что всего примерно в 5 раза больше L2 кэша GPU. Однако большие графы требуют достаточного количества памяти и даже граф 24 масштаба уже не помещается в память тестируемого GPU без сжатия. Исходя из представления графа, 26 масштаб является последним, у которого количество ребер помещается в unsigned int, что является некоторым ограничением алгоритма для дальнейшего масштабирования. Данное ограничение легко обходится путем расширения типа данных. Как мне кажется, пока это не так актуально, так как обработка одинарной точности (unsigned int) осуществляется во много раз быстрее, чем двойной (unsigned long long) и количество памяти пока достаточно мало. Производительность будет измеряться в количестве обработанных ребер в секунду (traversed edges per second — TEPS).

Компиляция осуществлялась с использованием NVidia CUDA Toolkit 7.0 с опциями -O3 -arch=sm_35, Intel Composer 2015 с опциями -O3. Максимальную производительность реализованного алгоритма можно увидеть на графике ниже:

На графике видно, что с использованием всех оптимизаций SSCA2 графы показывают хорошую эффективность: чем больше граф, тем лучше производительность. Данный рост сохраняется до тех пор, пока все данные помещаются в память GPU. На 25 и 26 масштабах был использован механизм Unified Memory, который позволил получить результат, правда с более низкой скоростью (но как будет продемонстрировано ниже, быстрее, чем только на CPU). Если бы расчет выполняется на Tesla k40 с 12ГБ памяти и отключенным ECC и процессором Intel Xeon E5 V2/V3, то вполне возможно можно было бы достичь порядка 3000 MTEPS на графе SSCA2 масштаба 25, а также попытаться обработать не только граф 26го масштаба, но и 27. Для RMAT графа такой эксперимент не проводился, в силу его сложной структуры и плохой адаптации алгоритма.

Сравнение производительности различных алгоритмов

Данная задача решалась в рамках конкурса конференции GraphHPC 2015. Я бы хотел привести сравнение с программой, написанной Александром Дарьиным, который по мнению авторов занял первое место в данном конкурсе.
Так как в общей таблице есть результаты на тестовой платформе, предоставленной авторами, то не лишним было бы привести графики на CPU и GPU на описанной платформе (GTX Titan + Xeon E5 v2). Ниже представлены результаты для двух графов:



Из приведенных графиков видно, что описанный в данной статье алгоритм больше оптимизирован для SSCA2 графов, в то время как алгоритм, реализованный Александром Дарьиным, хорошо оптимизирован для RMAT графов. В данном случае нельзя сказать однозначно какая из реализаций является лучшей, потому что у каждой есть свои преимущества и недостатки. Также не ясен критерий, по которому надо оценивать алгоритмы. Если говорить про обработку больших графов, то тот факт, что алгоритм может обработать графы 24-26 масштаба, является большим плюсом и преимуществом. Если говорить о средней скорости обработки графов любой величины, то не ясно, какую именно среднюю величину считать. Ясно только одно — один алгоритм хорошо обрабатывает SSCA2 графы, второй — RMAT. Если объединить две эти реализации, то средняя производительность будет порядка 3200 MTEPS для 23 масштаба. Презентация описания некоторых оптимизаций алгоритма Александра Дарьина можно посмотреть здесь.

Из зарубежных статей можно выделить следующие.
1) [13] Из данной статьи были использованы некоторые идеи при реализации описанного алгоритма. Напрямую сравнивать полученные авторами результаты нельзя, так как тестирование производилось на старой NVidia Tesla S1070. Достигнутая авторами производительность на GPU колеблется от 18-36 MTEPS. Опубликована в 2009 и в 2013 годах.
2) [14] реализация алгоритма Прима на GPU.
3) [15] реализация k NN-Boruvka на GPU.
Также существуют некоторые параллельные реализации на CPU. Но высокой производительности в зарубежных статьях я так и не смог найти. Может кто-нибудь из читателей сможет подсказать, если я что-то упустил. Также стоит отметить, что в России публикаций по этой теме практически нет (за исключением Зайцева Вадима), что очень печально, как мне кажется.