Исследование производительности задачи поиска вширь в графе на сопроцессорах семейства 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.

Ключевые слова: поиск вширь в графе, BFS, Intel Xeon Phi.

Название статьи, аннотация и ключевые слова на английском языке

  • Головина Е.А. – Научно-исследовательский центр электронной вычислительной техники (ОАО "НИЦЭВТ"), Варшавское шоссе, 125, 117587, Москва; инженер-программист, e-mail: golovina@nicevt.ru
  • Семенов А.С. – Научно-исследовательский центр электронной вычислительной техники (ОАО "НИЦЭВТ"), Варшавское шоссе, 125, 117587, Москва; начальник cектора, e-mail: semenov@nicevt.ru
  • Фролов А.С. – Научно-исследовательский центр электронной вычислительной техники (ОАО "НИЦЭВТ"), Варшавское шоссе, 125, 117587, Москва; начальник отдела, e-mail: frolov@nicevt.ru