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

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

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

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

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

СтудентВариант
Андрей ПаокинMPI-1 (может быть +CUDA?)
Вадим ПилюгинMPI-3
Михаил ШубинMPI Graph API
Александр РязановOpenSHMEM
Илья КосаревCharm++
Михаил КозловApache Spark+GraphX / BigData

Литература

  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. Описание лувенского алгоритма.
  10. U.Raghavan, R. Albert, S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. PDF.
  11. U. Brandes. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology, vol. 25, no. 2, pp. 163–177, 2001. PDF.
  12. A. Lumsdaine, D. Gregor. Challenges in parallel graph processing // Parallel Process. Lett. 17, 5, 2007. PDF.
  13. Головина Е.А., Семенов А.С., Фролов А.С. Исследование производительности задачи поиска вширь в графе на сопроцессорах семейства Intel Xeon Phi // Вычислительные методы и программирование. – 2014. – Т. 15. – С. 49-58. PDF.