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