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

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

Факультет ВМК, МГУ им. М.В. Ломоносова
Весенний семестр 2023/2024, по понедельникам 10:30, ауд. 658
Преподаватель: А.С. Семенов, к.т.н.

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

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

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

СтудентВариантПроверка корректности 8.04 Масштабируемость 13.05Практ.заданиеЭкзамен
Гадиева ТамараMPI-1, точка-точка
Дунлян ЮаньSpark+++отлично
Килина Мария GPU
Куприй Роман MPI-1, Bsend+ 8.05++
Латыпов ШамильMPI-1, неблок.ф-ии+ 30.04++
Матвеев АлексейMPI-3+++отлично
Новиков Дмитрий charm4py+++отлично
Сетяев АлександрCharm+++-++отлично
Чернышов Николайmpi4py
Щербаков АнтонGraphX+++отлично
Элишаков ДаниилMPI-1, коллективные+++отлично

Задача. К экзамену необходимо сделать параллельную реализацию алгоритма дельта-степпинг решения задачи SSSP поиска всех кратчайших путей в ориентированном графе с весами. Без выполнения практического задания максимально возможная оценка на экзамене -- 3 балла.

Условия. Для реализации необходимо использовать архитектуру с распределенной памятью.

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

При соблюдении дедлайнов, а также реализации одной или нескольких оптимизаций студент получает экзамен автоматом!

Инфраструктура, включающая генератор случайного графа, RMAT-графа, реализацию наивного алгоритма для проверки правильности решения доступна здесь: 2024-PLGP-SSSP.zip.

Экзамен

Список вопросов для экзамена доступен здесь.

Материалы

  1. Занятие 1. Введение. Примеры задач обработки графов. Big Data и HPC c точки зрения задач обработки графов. (слайды)
  2. Занятие 2. Основные проблемы при суперкомпьютерной обработке графов. Алгоритмы обхода графов: поиск вширь, поиск вглубь. Задача поиска минимального остовного дерева в графе. Алгоритмы Прима, Крускала, Борувки. (слайды)
  3. Занятие 3. Программные модели BSP и vertex-centric. Алгоритм GHS поиска минимального остовного дерева. Технология параллельного программирования Charm++. (слайды)
  4. Занятие 4. Алгоритмы поиска всех кратчайших путей от заданной вершины: Дейкстры, Беллмана-Форда, Дельта-степпинг. Параллельная файловая система HDFS. Вычислительные модели MapReduce, Spark.(слайды)
  5. Занятие 5. Задача расчета Betweenness Centrality: наивный алгоритм, алгоритм Брандеса. (слайды)
  6. Занятие 6. Задача поиска сообществ в графе: лувенский алгоритм, алгоритм label propagation. Представление алгоритмов обработки графов при помощи операций линейной алгебры. GraphBLAS. (слайды)
  7. Занятие 7. Различные виды графов: Random Uniform, small-world, scale-free, RMAT, LFR, SSCA2. Форматы представления разреженных матриц: CRS, Coordinate list, ELLPACK, JDS, SELLPACK. Архитектура современного вычислительного узла: NUMA, многоядерность, длинные вектора. (слайды)
  8. Занятие 8. Проблемы и подходы к решению задач обработки больших графов в рамках одного узла. Принципы организации динамической памяти. (слайды)
  9. Занятие 9. Основные характеристики высокоскоростных коммуникационных сетей. Топологии сетей: тор, FatTree, Flattened Butterfly, Dragonfly. Высокоскоростная сеть Ангара. (слайды)
  10. Занятие 10. Односторонняя и двусторонняя модели передачи сообщений. Библиотека MPI-1, MPI-3. Протоколы передачи сообщений Eager и Rendezvous. Проблемы и подходы к решению задач обработки больших графов в рамках распределенной вычислительной системы. Распределение данных, организация внутриузлового параллелизма, коммуникационные паттерны, сжатие сообщений, балансировка нагрузки. (слайды)
  11. Литература

    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. V. Vineet, P.Harish, S. Patidar, and P. J. Narayanan. 2009. Fast Minimum Spanning Tree for Large Graphs on the GPU. In Proceedings of the Conference on High Performance Graphics 2009 (HPG '09). PDF.
    7. 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.
    8. А.В. Мазеев. Параллельный алгоритм поиска минимального остовного дерева в графе на суперкомпьютере с сетью "Ангара" // Суперкомпьютерные дни в России: Труды международной конференции (26-27 сентября 2016 г., г. Москва).– М.: Изд-во МГУ, 2016. – С.926-939. PDF.
    9. McCune R. R., Weninger T., Madey G. Thinking like a vertex: a survey of vertex-centric frameworks for distributed graph processing //arXiv preprint arXiv:1507.04405. – 2015. PDF
    10. Malewicz, G., Austern, M. H., Bik, A. J., Dehnert, J. C., Horn, I., Leiser, N., Czajkowski, G. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. 2010. pp. 135-146. PDF
    11. Blondel, Vincent D., et al. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008.10 (2008). PDF.
    12. U.Raghavan, R. Albert, S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. PDF.
    13. U. Brandes. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology, vol. 25, no. 2, pp. 163–177, 2001. PDF.
    14. J. Kepner et al. Mathematical foundations of the GraphBLAS. 2016 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 2016. PDF.
    15. A. Lumsdaine, D. Gregor. Challenges in parallel graph processing // Parallel Process. Lett. 17, 5, 2007. PDF.
    16. Что каждый программист должен знать о памяти, перевод Капустин С.В., М.Ульянов, Н.Ромоданов, 2009-2012. PDF. Оригинал U.Drepper, 2007. PDF.
    17. Головина Е.А., Семенов А.С., Фролов А.С. Исследование производительности задачи поиска вширь в графе на сопроцессорах семейства Intel Xeon Phi // Вычислительные методы и программирование. – 2014. – Т. 15. – С. 49-58. PDF.