Лаборатория Data-Intensive Supercomputing

Спецкурс "Параллельная обработка больших графов"

Факультет ВМК, МГУ им. М.В. Ломоносова
Осенний семестр 2016/2017, по пятницам 18:00, aуд. 609
Преподаватель: А.С. Семенов

Обработка больших графов, которая стала очень востребованной за последние 5-10 лет, невозможна без применения суперкомпьютеров. Однако нерегулярная структура графов, большой размер, преобладание операций доступа к данным над вычислениями приводит к тому, что задачи обработки графов являются одними из самых сложных для эффективной реализации на суперкомпьютерах. Спецкурс посвящен всем аспектам параллельной обработки графов от алгоритмов до их эффективной реализации на суперкомпьютерных архитектурах с общей и распределенной памятью, отдельное внимание будет уделено технологиям Big Data.

Задание к экзамену/зачету

Задача. Для зачета/экзамена необходимо сделать параллельную реализацию алгоритма Брандеса решения задачи расчета Betweenness Centrality для неориентированного графа без весов.

Инфраструктура, включающая генератор RMAT-графа, реализацию наивного алгоритма для проверки правильности решения доступна здесь: PLGP_exam-0.1.tgz.

Задача Betweenness Centrality будет поставлена на конкурсе конференции GraphHPC-2017.

Условия. Для реализации допускается любая параллельная архитектура: общая память (SMP), ускоритель (GPU) или распределенная память.

При сдаче задаче необходимо продемонстрировать работающую параллельную программу и ускорение решения задачи при фиксированном объеме данных в зависимости от увеличения числа параллельных процессов. Реализация должна быть масштабируемой по памяти (т.е. не должно требоваться O(N) памяти на каждый дополнительный параллельный поток, где N - число вершин в графе. Поэтому распараллеливание по источникам поиска в самом внешнем цикле алгоритма Брандеса, скорее всего, не подойдет). Также необходимо будет ответить на вопросы по исходному коду. Плагиат карается незачетом!

Для тех, кому необходим оценка экзамена по спецкурсу, в дополнение к зачетной задаче состоится устный экзамен по вопросам из программы спецкурса.

Доступ. По запросу (присылайте также открытый ключ для доступа) на alxdr.semenov at gmail com может быть предоставлен доступ на мощный SMP-узел для выполнения зачетной задачи:

Лекции

  1. 7.10. Введение. Примеры задач обработки графов. Big Data и HPC c точки зрения задач обработки графов. (слайды)
  2. 14.10. Основные проблемы при суперкомпьютерной обработке графов. Алгоритмы обхода графов: поиск вширь, поиск вглубь. Алгоритмы поиска всех кратчайших путей от заданной вершины: Дейкстры, Беллмана-Форда, Дельта-степпинг. (слайды)
  3. 28.10. Задача поиска минимального остовного дерева в графе. Алгоритмы Прима, Крускала, Борувки, GHS. (слайды)
  4. 11.11. Задача поиска сообществ в графе: лувенский алгоритм, алгоритм label propagation. Задача расчета betweenness centrality: наивный алгоритм, алгоритм Брандеса. (слайды)
  5. 18.11. Различные виды графов: Random Uniform, small-world, scale-free, RMAT, LFR, SSCA2. Форматы представления разреженных матриц: CRS, Coordinate list. Архитектура современного вычислительного узла: NUMA, многоядерность, длинные вектора. (слайды)
  6. 25.11. Проблемы и подходы к решению задач обработки больших графов в рамках одного узла. (слайды)
  7. 2.12. Архитектура современной вычислительной системы с распределенной памятью. Односторонняя и двусторонняя модели передачи сообщений. Библиотека MPI. Протоколы передачи сообщений Eager и Rendezvous. (слайды)
  8. 9.12. Недостатки и преимущества системной буферизации в MPI. Общие рекомендации для эффективной реализации программ с использованием библиотеки MPI. (слайды)
  9. 16.12. Проблемы и подходы к решению задач обработки больших графов в рамках распределенной вычислительной системы. Распределение данных, организация внутриузлового параллелизма, коммуникационные паттерны,сжатие сообщений, балансировка нагрузки. (слайды)

Литература

  1. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание. — М.: «Вильямс», 2013. — 1328 с.
  2. D. Reed, J. Dongarra. Exascale Computing and Big Data: The Next Frontier,Communications of the ACM, Vol. 58 No. 7, P. 56-68. PDF.
  3. U. Meyer, P. Sanders. Delta-Stepping: A Parallel Single Source Shortest Path Algorithm. In Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98), Venice, Italy, August, 24 - 26, 1998, 393-404. PDF.
  4. V. Chakaravarthy, F. Checconi, F. Petrini, and Y. Sabharwal. Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems. In Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS '14). IEEE Computer Society, Washington, DC, USA, 889-901. PDF.
  5. K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak. An Experimental Study of A Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances,'' Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, January 6, 2007. PDF.
  6. Gallager R. G., Humblet P. A., Spira P. M. A distributed algorithm for minimum-weight spanning trees // ACM Transations on Programming Languages and Systems. 1983. vol. 77. PDF.
  7. А.В. Мазеев. Параллельный алгоритм поиска минимального остовного дерева в графе на суперкомпьютере с сетью "Ангара" // Суперкомпьютерные дни в России: Труды международной конференции (26-27 сентября 2016 г., г. Москва).– М.: Изд-во МГУ, 2016. – С.926-939. PDF.
  8. Описание лувенского алгоритма.
  9. U.Raghavan, R. Albert, S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. PDF.
  10. U. Brandes. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology, vol. 25, no. 2, pp. 163–177, 2001. PDF.
  11. A. Lumsdaine, D. Gregor. Challenges in parallel graph processing // Parallel Process. Lett. 17, 5, 2007. PDF.
  12. Головина Е.А., Семенов А.С., Фролов А.С. Исследование производительности задачи поиска вширь в графе на сопроцессорах семейства Intel Xeon Phi // Вычислительные методы и программирование. – 2014. – Т. 15. – С. 49-58. PDF.