=Paper= {{Paper |id=Vol-1576/149 |storemode=property |title=Parallel high performance graph processing |pdfUrl=https://ceur-ws.org/Vol-1576/149.pdf |volume=Vol-1576 |authors=Mikhail Chernoskutov }} ==Parallel high performance graph processing== https://ceur-ws.org/Vol-1576/149.pdf

Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)

agora.guru.ru/pavt

Параллельная высокопроизводительная обработка
графов\ast
1,2
М.А. Черноскутов

1
Институт математики и механики им. Н.Н. Красовского УрО РАН,
2
Уральский Федеральный Университет имени первого Президента России

Б.Н. Ельцина

В работе описаны методы, позволяющие значительно ускорить работу парал-
лельного поиска в ширину на графе. Основным препятствием для эффективного
распараллеливания поиска в ширину на графе являются дисбаланс вычислитель-
ной нагрузки внутри отдельных вычислительных узлов, а также значительный
объем передаваемых в конце каждой итерации алгоритма. Для устранения этих
препятствий в данной статье предлагается два метода. Первый метод позволя-
ет распределить нагрузку между отдельными OpenMP-потоками внутри одного
узла. Второй метод позволяет, путем гибридизации обхода графа, добиться сни-
жения общего объема передаваемых данных.
Ключевые слова: параллельные вычисления, обработка графов, балансировка на-
грузки

1. Введение

Алгоритмы на графах применяются в различных научных и практических приложени-
ях. Во многих случаях, большие размеры графов предполагают их параллельную обработку
на многопроцессорных вычислительных системах [1]. Однако, эффективному распаралле-
ливанию алгоритмов на графах препятствуют такие обстоятельства как интенсивный до-
ступ к памяти и заранее неизвестное (в общем случае) распределение данных по узлам
вычислительной системы, что делает подобные алгоритмы типичными представителями
задач класса «data intensive» [2].
Интенсивный доступ к памяти является узким местом в практической реализации ал-
горитмов на графах, т.к. чаще всего, работа таких алгоритмов не сопряжена с большим
количеством арифметических вычислений. Этот факт позволяет, с одной стороны, значи-
тельно снизить требования к производительности центральных процессоров, но, с другой
стороны, повышаются требования к эффективности и скорости работы канала доступа к
данным.
Неизвестное распределение данных также значительно осложняет эффективную реа-
лизацию параллельных алгоритмов на графах на многоузловых вычислительных системах.
В общем случае, заранее неизвестно, на каком вычислительном узле расположены данные
о той или иной вершине. Поэтому, возникает потребность в опросе других узлов на предмет
наличия на них требуемых данных. Другой вариант — заранее распределять данные между
узлами в соответствии с каким-либо правилом.
Объектом исследования данной работы является параллельный поиск в ширину на гра-
фах с неравномерным распределением степей вершин и малым диаметром (как правило,
не более 10). Такие графы возникают, например, при анализе социальных сетей и прило-
жений физического и математического моделирования [3]. Основной особенностью таких
графов является очень малое количество вершин с большими степенями на фоне большого
количества вершин со всего лишь несколькими инцидентными ребрами.
\ast
Работа поддержана грантом РФФИ №14-07-00435. При выполнении работ использовался суперкомпью-

тер «Уран»

736
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)

agora.guru.ru/pavt

2. Параллельный поиск в ширину

Для распараллеливания поиска в ширину на графе используются синхронизированные
по уровням алгоритмы. Как видно из названия, данные алгоритмы обрабатывают каждый
уровень (или итерацию) алгоритма последовательно и независимо от других уровней. На
практике это означает, что, в случае поиска в ширину, обработка уровня N + 1 начнется
только после того, как будет полностью завершена обработка уровня N . При этом вершины
и ребра графа как на уровне N , так и на уровне N + 1 могут обрабатываться параллельно.
На данный момент существует два наиболее распространенных версии синхронизиро-
ванного по уровням поиска в ширину:
\bullet прямой обход графа («top-down»);
\bullet обратный обход графа [4] («bottom-up»).
Версия поиска в ширину с прямым обходом графа — «стандартный» вариант данного
алгоритма. Этот вариант обхода предполагает, что активные на текущей итерации вершины
будут помечать своих соседей. Псевдокод алгоритма параллельного поиска в ширину с
прямым обходом графа представлен на рис. 1.

1 f o r each u i n dist
2 dist [ u ] := -1
3 dist [ s ] := 0
4 level := 0
5 do
6 p a r a l l e l f o r each vert i n V . this_node
7 i f dist [ vert ] = level
8 f o r each neighb i n vert . neighbors
9 i f neighb i n V . this_node
10 i f dist [ neighb ] = -1
11 dist [ neighb ] := level + 1
12 pred [ neighb ] := vert
13 else
14 vert_batch_to_send . push ( neighb )
15
16 send ( vert_batch_to_send )
17 receive ( vert_batch_to_receive )
18
19 p a r a l l e l f o r each vert i n vert_batch_to_receive
20 i f dist [ vert ] = -1
21 dist [ vert ] := level + 1
22 pred [ vert ] := vert . pred
23 level ++
24 w h i l e (! check_end ())
Рис. 1. Псевдокод параллельного алгоритма поиска в ширину на графе с прямым обходом

В строках 1–4 проходит инициализация массива расстояний до корневой вершины. Да-
лее расположен основной цикл поиска в ширину, который выполняется, пока в графе име-
ются непомеченные вершины. Сначала, в строках 6–14 происходит разметка тех вершин,
которые расположены на данном вычислительном узле. Затем, в строках 16 и 17 выполняет-
ся, соответственно, точечная рассылка и прием сообщений, содержащих данные о вершинах,
которые должны быть помечены на других узлах. Наконец, в строках 19–22 выполняется
разметка вершин, данные о которых были получены путем приема сообщений. Выполне-
ние итерации завершается увеличением номера текущего уровня на единицу в строке 23 и
проверкой на наличие непомеченных вершин в строке 24.
Версия поиска в ширину с обратным обходом предполагает, что неактивные вершины
будут просматривать свои списки соседей и будут помечаться только в том случае, если
среди их соседей имеется активная на текущей итерации вершина. Псевдокод алгоритма
параллельного поиска в ширину с обратным обходом графа представлен на рис. 2.

737
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)

agora.guru.ru/pavt

1 f o r each u i n dist
2 dist [ u ] := -1
3 dist [ s ] := 0
4 level := 0
5 do
6 p a r a l l e l f o r each vert i n V . this_node
7 i f dist [ vert ] = -1
8 f o r each neighb i n vert . neighbors
9 i f bitmap_current . neighb = 1
10 dist [ vert ] := level + 1
11 pred [ vert ] := neighb
12 bitmap_next . vert := 1
13 break
14
15 all_gather ( bitmap_next )
16 swap ( bitmap_current , bitmap_next )
17
18 level ++
19 w h i l e (! check_end ())
Рис. 2. Псевдокод параллельного алгоритма поиска в ширину на графе с обратным обходом

Аналогично алгоритму на рис. 1, в строках 1–4 выполняется инициализация поиска в
ширину, а в строках 18 и 19 — обновление номера уровня и проверка завершения алгоритма.
По иному построена процедура разметки вершин — в случае обратного обхода необходимо
знать информацию обо всех активных на данной итерации вершинах. Удобнее всего это
сделать с помощью использования битовой маски, длина которой (в битах) равна количе-
ству вершин в графе. Таким образом, синхронизация данных на каждой итерации проходит
путем обновления битовой маски с помощью коллективных коммуникаций (строки 15 и 16).

3. Оптимизация производительности параллельного поиска в

ширину

Для ускорения параллельного алгоритма поиска в ширину на графе предлагается ис-
пользование двух методов:
\bullet гибридизация обхода графа;
\bullet распределение вычислительной нагрузки между потоками.

3.1. Гибридизация обхода

Данный метод предполагает сочетание различных разновидностей параллельного ал-
горитма поиска в ширину для выполнения различных итераций алгоритма. В частности,
«top-down» версия алгоритма характеризуется пиками вычислительной нагрузки и нагруз-
ки на подсистему передачи данных на промежуточных итерациях алгоритма. В то же время,
начальные и заключительные итерации в прямом обходе графа выполняются значительно
быстрее и практически не нагружают сеть передачи данных. Несколько иная ситуация об-
стоит с «bottom-up» версией алгоритма вследствие использования коллективных операций
синхронизации данных. В данном варианте алгоритма поиска в ширину, обмены данными
на каждой итерации занимают примерно одинаковое время. Однако, разметка вершин на
первых итерациях происходит гораздо дольше, чем на последующих.
Учитывая тот факт, что результат выполнения каждой из итераций алгоритма поиска
в ширину, независимо от направления обхода, одинаков, то имеет смысл комбинировать
различные варианты обхода графа для достижения максимальной производительности. В
данной работе предлагается следующая схема:
\bullet первые две итерации — «top-down»;

738
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)

agora.guru.ru/pavt

\bullet следующие три итерации — «bottom-up»;

\bullet все остальные итерации — «top-down».

3.2. Распределение нагрузки

При обработке графов с неравномерным распределением степеней вершин заранее неиз-
вестно (в общем случае), какие вершины будет обрабатывать тот или иной вычислительный
поток. Известным может быть лишь общее количество вершин, которые необходимо обрабо-
тать в данном потоке. При этом общий объем нагрузки определяется не самим количеством
вершин, а количеством инцидентных данным вершинам ребер. Это приводит к дисбалансу
нагрузки между потоками, что приводит к большим накладным расходам при распаралле-
ливании синхронизированного по уровням поиска в ширину.
Для устранения дисбаланса нагрузки предлагается перейти от просмотра массива вер-
шин на каждой итерации алгоритма к просмотру массива ребер. Для этого массив ребер
необходимо логически разделить на равные части размером max_edges элементов. Для то-
го, чтобы каждый поток мог «знать», к какой вершине принадлежит тот или иной элемент
в каждой из равных частей массива ребер, необходимо создать новый массив part_column,
в каждой ячейке которого будут храниться номера вершин, инцидентные первому элементу
в каждой из частей массива ребер. Параллельная разметка массива part_column представ-
лена на рис. 3.

1 parallel f o r each i i n V . this_node
2 first := V . this_node [ i ]
3 last := V . this_node [ i +1]
4 index := round_up ( first / max_edges )
5 current := index * max_edges
6 w h i l e ( current < last )
7 part_column [ index ] := i
8 current := current + max_edges
9 index ++

Рис. 3. Псевдокод параллельного алгоритма разметки массива part_column

Псевдокод новой версии цикла разметки вершин (см. строки 6–14 в алгоритме на рис. 1
и строки 6–13 на рис. 2) с использованием массива part_column для прямого варианта
обхода графа приведен на рис. 4, для обратного варианта обхода графа — на рис. 5.

1 // preparation ...
2 p a r a l l e l f o r each i i n part_column
3 first_edge := i * max_edges
4 last_edge := ( i +1)* max_edges
5 curr_vert := part_column [ i ]
6 f o r each edge i n [ first_edge ; last_edge )
7 i f neighbors o f curr_vert i n [ first_edge ; last_edge )
8 i f dist [ curr_vert ] = level
9 f o r each k i n neighbors o f curr_vert
10 i f dist [ k ] = -1
11 dist [ k ] := level + 1
12 pred [ k ] := curr_vert
13 curr_vert ++
14 // data synchronization ...
Рис. 4. Псевдокод цикла разметки вершин в алгоритме поиска в ширину на графе (прямой обход)

739
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)

agora.guru.ru/pavt

1 // preparation ...
2 p a r a l l e l f o r i i n part_column
3 first_edge := i * max_edges
4 last_edge := ( i +1)* max_edges
5 curr_vert := part_column [ i ]
6 f o r each edge i n [ first_edge ; last_edge )
7 i f neighbors o f curr_vert i n [ first_edge ; last_edge )
8 i f dist [ curr_vert ] = -1
9 f o r each k i n neighbors o f curr_vert
10 i f bitmap_current . k = 1
11 dist [ curr_vert ] := level + 1
12 pred [ curr_vert ] := k
13 bitmap_next . vert := 1
14 break
15 curr_vert ++
16 // data synchronization ...
Рис. 5. Псевдокод цикла разметки вершин в алгоритме поиска в ширину на графе (обратный обход)

4. Тестирование производительности параллельного поиска в

ширину

Оба описанных выше метода были встроены в собственную (custom) реализацию теста
производительности Graph500 [5]. Ядро данного теста представляет собой параллельный
поиск в ширину на большом графе, размер которого определяется параметром scale, рав-
ным логарифму по основанию 2 от количества вершин в графе. При этом средняя степень
вершин всегда равна 16. Основным показателем производительности является скорость об-
хода графа, выраженная в количестве пройденных в секунду ребер (Traversed Edges Per
Second — TEPS).
Разработанная custom-реализация использует MPI (один процесс на вычислительный
узел) для передачи сообщений между узлами и OpenMP (восемь потоков на вычислитель-
ный узел) для работы с общей памятью внутри узла.
Тестирование проводилось для графов разного размера на 1, 2, 4 и 8 узлах суперком-
пьютера «Уран», расположенного в ИММ УрО РАН. Каждый узел оборудован CPU Intel
Xeon X5675 и 46 ГБ ОЗУ. Производительность custom-реализации сравнивалась со стан-
дартными реализациями, которые предоставляются оргкомитетом рейтинга Graph500:

\bullet simple (представляет собой «top-down» вариант поиска в ширину);

\bullet replicated (представляет собой «bottom-up» вариант поиска в ширину).

Результаты тестирования представлены на рис. 6. Как видно, custom-реализация зна-
чительно превосходит по производительности simple и replicated-реализации. При этом, в
случае с 8-ю узлами видно, что custom-реализация сохраняет потенциал дальнейшей мас-
штабируемости.

5. Заключение

Эффективное распараллеливание поиска в ширину на графах с неравномерным распре-
делением степеней затруднено из-за дисбаланса вычислительной нагрузки, а также больших
объемов передаваемых данных на малом количестве итераций алгоритма, что создает пик
вычислительной нагрузки.
В данной работе предложены методы распределения нагрузки и гибридизации обхода,
позволяющие значительно (более чем в три раза) повысить скорость параллельного поис-
ка в ширину на графе по сравнению со своими стандартными «top-down» и «bottom-up»
аналогами.

740
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)

agora.guru.ru/pavt

1 узел 2 узла
custom replicated simple custom replicated simple

1000 2000
Скорость обхода, MTEPS

Скорость обхода, MTEPS
800
1500
600
1000
400
200 500

0 0
20 21 22 23 24 25 20 21 22 23 24 25
Scale Scale

4 узла 8 узлов
custom replicated simple custom replicated simple

3000 5000

Скорость обхода, MTEPS
Скорость обхода, MTEPS

2500 4000
2000
3000
1500
2000
1000
500 1000
0 0
20 21 22 23 24 25 20 21 22 23 24 25
Scale Scale

Рис. 6. Результаты тестирования производительности

В качестве направлений дальнейшей работы выбрано изучение масштабируемости пред-
ставленного алгоритма на графах, имеющих различный размер и различную среднюю сте-
пень вершин. Актуальной задачей также является модификация custom-реализации для
использования ускорителей вычислений с целью повышения эффективности алгоритма.

Литература

1. Mark E.J. Newman. The structure and function of complex networks. SIAM review,
45(2):167–256, 2003.
2. Andrew Lumsdaine, Douglas Gregor, Bruce Hendrickson, and Jonathan Berry. Challenges
in parallel graph processing. Parallel Processing Letters, 17(01):5–20, 2007.
3. Bruce Hendrickson and Jonathan W. Berry. Graph analysis with high-performance
computing. Computing in Science and Engg., 10(2):14–19, March 2008.
4. Scott Beamer, Krste Asanović, and David Patterson. Direction-optimizing breadth-first
search. In Proceedings of the International Conference on High Performance Computing,
Networking, Storage and Analysis, SC ’12, pages 12:1–12:10, Los Alamitos, CA, USA,
2012. IEEE Computer Society Press.
5. Richard C. Murphy, Kyle B. Wheeler, Brian W. Barrett, and James A. Ang. Introducing
the graph 500. 2010.

741
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)

agora.guru.ru/pavt

Parallel high performance graph processing
1,2
M.A. Chernoskutov

1
Institute of Mathematics and Mechanics UB RAS,
2
Ural Federal University

Paper describes methods devoted to drastically speedup parallel breadth-first search
algorithm. Main obstacle on the way to effectively parallelize breadth-first search is
workload imbalance within computing nodes as well as significant volume of transferred
data in the end of every iteration of the algorithm. Two methods are suggested in
this paper to overcome these challenges. First method allows to distribute workloads
between OpenMP threads in single node. Second method allows to reduce data
transfer volume by using the hybrid graph traversal.
Keywords: parallel computing, graph processing, workload balancing

References

1. Mark E.J. Newman. The structure and function of complex networks. SIAM review,
45(2):167–256, 2003.

2. Andrew Lumsdaine, Douglas Gregor, Bruce Hendrickson, and Jonathan Berry. Challenges
in parallel graph processing. Parallel Processing Letters, 17(01):5–20, 2007.

3. Bruce Hendrickson and Jonathan W. Berry. Graph analysis with high-performance
computing. Computing in Science and Engg., 10(2):14–19, March 2008.

4. Scott Beamer, Krste Asanović, and David Patterson. Direction-optimizing breadth-first
search. In Proceedings of the International Conference on High Performance Computing,
Networking, Storage and Analysis, SC ’12, pages 12:1–12:10, Los Alamitos, CA, USA,
2012. IEEE Computer Society Press.

5. Richard C. Murphy, Kyle B. Wheeler, Brian W. Barrett, and James A. Ang. Introducing
the graph 500. 2010.

742