Исследование производительности задачи поиска вширь в графе на сопроцессорах семейства Intel Xeon Phi

Авторы

  • Е.А. Головина Научно-исследовательский центр электронной вычислительной техники (НИЦЭВТ)
  • А.С. Семенов Научно-исследовательский центр электронной вычислительной техники (НИЦЭВТ)
  • А.С. Фролов Научно-исследовательский центр электронной вычислительной техники (НИЦЭВТ)

Ключевые слова:

поиск вширь в графе, BFS, Intel Xeon Phi

Аннотация

Одним из важнейших алгоритмов обработки графов является поиск вширь, лежащий в основе рейтинга суперкомпьютеров Graph500. Графовые задачи характеризуются интенсивным нерегулярным доступом к памяти и обычно решаются на современных процессорах с низкой эффективностью. В статье представлены результаты исследования выполнения поиска вширь в графе на новых сопроцессорах семейства Intel Xeon Phi. Для получения высокой производительности применен потоковый подход с эффективным использованием пропускной способности памяти при последовательном доступе с сохранением нерегулярного доступа к памяти, при этом необходимо выполнение ручной развертки цикла и преднакачки данных в кэш. В сравнении с Intel Xeon E5-2660 для разных графов Intel Xeon Phi 7120P оказался в среднем быстрее на 37%, в лучшем случае — на 78%; Intel Xeon Phi 5110P быстрее Intel Xeon E5-2660 в лучшем случае на 34%, медленнее в худшем случае на 29%, в среднем производительность приблизительно одинаковая. Полученный на Intel Xeon Phi 7120P результат в 4366 миллионов пройденных дуг в секунду вошел в ноябрьскую редакцию рейтинга Graph500 (2013 г.) и занял 89-е место среди всех систем и 4-ое место среди исследовательских групп в классе одноузловых систем на базе платформы x86. Авторы благодарят компанию «Свет Компьютерс» за предоставленную расчетную систему IntellectDigital SciPhi 470 с сопроцессором Intel Xeon Phi 7120P.

Авторы

Е.А. Головина

Научно-исследовательский центр электронной вычислительной техники (НИЦЭВТ)
Варшавское шоссе, 125, 117587, Москва
• инженер-программист

А.С. Семенов

Научно-исследовательский центр электронной вычислительной техники (НИЦЭВТ)
Варшавское шоссе, 125, 117587, Москва
• начальник сектора

А.С. Фролов

Научно-исследовательский центр электронной вычислительной техники (НИЦЭВТ)
Варшавское шоссе, 125, 117587, Москва
• начальник отдела

Библиографические ссылки

  1. Graph500 benchmark (http://www.graph500.org/).
  2. Головина Е.А., Семенов А.С., Фролов А.С. Исследование производительности задачи поиска вширь в графе на сопроцессоре Intel Xeon Phi // Тр. Межд. суперкомпьютерной конференции «Научный сервис в сети Интернет: все грани параллелизма», 23-28 сентября 2013 г., г. Новороссийск. М.: Изд-во Моск. гос. ун-та, 2013. 135-141.
  3. Agarwal V., Petrini F., Pasetto D., Bader D. Scalable graph exploration on multicore processors // Proc. 2010 ACM/IEEE International Conference on High Performance Computing, Networking, Storage, and Analysis (SC’10). New York: IEEE Press, 2010. 1-11.
  4. Saule E., Catalyeurek U. An early evaluation of the scalability of graph algorithms on the Intel Phi architecture // IEEE 26th International Parallel and Distributed Processing Symposium Workshops &; PhD Forum (IPDPSW’12). New York: IEEE Press, 2012. 1629-1639.
  5. Hong S., Oguntebi T., Olukotun K. Efficient parallel graph exploration on multi-core CPU and GPU // Proc. Int. Conf. on Parallel Architectures and Compilation Techniques (PACT’11). New York: IEEE Press, 2011. 78-88.
  6. Beamer S., Asanoviacutec K., Patterson D. Direction-optimizing breadth-first search // Proc. Int. Conf. on High Performance Computing, Networking, Storage and Analysis (SC’12). New York: IEEE Press, 2012. 1-10.
  7. Saule E., Kaya K., Catalyurek U. Performance evaluation of sparse matrix multiplication kernels on Intel Xeon Phi // arXiv:1302.1078, 5 Feb 2013 (http://arxiv.org/pdf/1302.1078.pdf).
  8. Frolov A., Gilmendinov M. DISBench: benchmark for memory performance evaluation of multicore multiprocessor // Lecture Notes in Computer Science. Vol. 7979. Heidelberg: Springer, 2013. 197-207.
  9. Cuthill E., McKee J. Reducing the bandwidth of sparse symmetric matrices // Proc. 24th National Conference (ACM’69). New York: ACM Press, 1969. 157-172.
  10. Chakrabarti D., Zhan Y., Faloutsos C. R-MAT: a recursive model for graph mining // SIAM International Conference on Data Mining. Vol. 6. Philadelphia: SIAM, 2004. 442-446.
  11. Bader D., Madduri K. Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessor // Lecture Notes in Computer Science. Vol. 3769. Heidelberg: Springer, 2005. 465-476.
  12. Bader D., Madduri K. SNAP: Small-world network analysis and partitioning: an open-source parallel graph framework for the exploration of large-scale networks // Proc. Int. Parallel and Distributed Processing Symposium (IPDPS). New York: IEEE Press, 2008. 1-12.
  13. Bader D., Madduri K. GTGraph: a synthetic graph generator suite. 2006 // (http://www.cse.psu.edu/ madduri/software/GTgraph).
  14. Компания «Cвет Компьютерс» (http://svetcorp.net).

Загрузки

Опубликован

29-01-2014

Как цитировать

Головина Е.А., Семенов А.С., Фролов А.С. Исследование производительности задачи поиска вширь в графе на сопроцессорах семейства Intel Xeon Phi // Вычислительные методы и программирование. 2014. 15. 49-58

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения