Результаты конкурса
Первое место в номинации одного узла занял студент факультета ВМиК МГУ Александр Колганов с результатом 1105 MTEPS на ускорителе NVIDIA GTX Titan. За первое место был вручен SSD-диск на 240 ГБ (Intel 530 Series). Максимальный результат в номинации многоузловой системы был получен сотрудником компании Т-Платформы Антоном Коржом на 512 узлах суперкомпьютера «Ломоносов» и составил 16900 MTEPS (вне конкурса). Все участники конкурса получили памятные сертификаты, а также сувениры от IBM и NVIDIA. Нескольким участникам, получившим хорошие результаты, были вручены книги о программировании на CUDA от NVIDIA.
Результаты конкурса: одноузловая система
| Система | Участник | Организация | Реализация | # ядер | Масштаб | MTEPS | |
| 1 | GTX Titan | А. Колганов | ВМиК МГУ | Б.-Форд, CUDA | 2688 | 19 | 1105 |
| 2 | 2хIntel Xeon E5-2630 | Ф. Минюк | Европлан | Дельта-ст., Pthreads/C++ | 12 | 19 | 424 |
| 3 | 2xIntel Xeon E5-2670 | А. Корж | Т-Платформы | Дельта-cт., DISLIB | 16 | 20 | 354 |
| 4 | 2хIntel Xeon E5-2630 | А. Корж | Т-Платформы | Дельта-ст., DISLIB | 8 | 15 | 237 |
| 5 | Intel Xeon Phi 5110P | Е. Головина, А. Семенов | DISLab ОАО «НИЦЭВТ» |
Дельта-cт., OpenMP | 60 | 20 | 177 |
| 6 | 2хIntel Xeon E5-2630 | В. Зайцев | НовосибГУ | Б.-Форд., Pthreads | 9 | 20 | 137 |
| 7 | 2хIntel Xeon E5-2630 | A. Фролов | DISLab ОАО «НИЦЭВТ» |
Green-Marl | 12 | 24 | 21 |
| 8 | 2хIntel Xeon E5-2630 | A. Фролов | DISLab ОАО «НИЦЭВТ» |
Yappi | 12 | 24 | 1.5 |
Результаты конкурса: кластер
| Система | Участник | Организация | Реализация | # узлов | # ядер | Масштаб | MTEPS | |
| 1 | Ломоносов | А. Корж | Т-Платформы | Дельта-cт., DISLIB | 512 | 4096 | 31 | 16900 |
| 2 | Nicevt-cluster | А. Корж | Т-Платформы | Дельта-cт., DISLIB | 8 | 64 | 20 | 820 |
| 3 | Nicevt-cluster | А. Кувшинников | ВМиК МГУ | Б-Форд., MPI |
8 | 192 | 16 | 170 |
| 4 | Nicevt-cluster | Е. Алехова | ИПМех РАН | Дельта-cт., PBGL | 8 | 16 | 15 | 15 |
| 5 | Nicevt-cluster | А. Фролов | DISLab ОАО «НИЦЭВТ» |
Yappi | 8 | 16 | 24 | 4.8 |
| 6 | Nicevt-cluster | А. Фролов | DISLab ОАО «НИЦЭВТ» |
GraphLab | 8 | 16 | 24 | 4.3 |
| 7 | Nicevt-cluster | А. Фролов | DISLab ОАО «НИЦЭВТ» |
Giraph | 8 | 16 | 24 | 3 |
Новости
21.01.2014. В описании на данной странице добавлена информация об используемых RMAT-графах. В новой версии GraphHPC-0.4.tgz примера реализации изменен алгоритм подсчета пройденных дуг и исправлена ошибка в параллельной генерации графа с использованием MPI.
Конкурс
В рамках семинара GraphHPC-2014 проводится конкурс на самую быструю реализацию задачи поиска кратчайших путей от заданной вершины ко всем остальным в графе с весами Single Source Shortest Paths (SSSP). Предполагается несколько номинаций: реализации на системе, ограниченной одним заданным вычислительным узлом, и реализации на заданном многоузловом кластере, а также на других архитектурах по выбору участников. Заданный вычислительный узел — это или 2 6-ядерных процессора Intel Xeon E5-2630, объем памяти — 64 ГБ, или узел с GPU-картой Tesla K20X, объем памяти — 6 ГБ. Заданный кластер — 8 узлов с процессорами Intel Xeon E5-2660, сеть — Infiniband 4x FDR. По запросу будет предоставляться удаленный доступ на эти системы. Поощряются реализации для других архитектур, такие результаты будут рассматриваться отдельно. Победители и творчески отличившиеся участники получат возможность рассказать на семинаре о своей реализации и, конечно, ценные призы.
Описание задачи
Предлагается задача Single Source Shortest Paths (SSSP) поиска кратчайших путей от заданной вершины ко всем остальным в графе с весами, значения которых являются действительными неотрицательными числами. Подробнее можно прочитать в книге Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание. — М.: «Вильямс», 2013. — 1328 с.
Для тестирования реализации задачи SSSP выполняются следующие шаги:
- Генерация RMAT-графа и создание внутреннего представления графа, используемого при решении задачи.
- Генерация набора случайных вершин, используемых в качестве стартовых в задаче SSSP, а также расчет количества пройденных дуг при поиске с каждой стартовой вершины.
- Для каждой вершины из случайного набора запускается реализация задачи SSSP. Измеряется время каждого запуска. Производительностью запуска является количество пройденных дуг, посчитанное на шаге 2, разделенное на измеренное время.
Для тестировании реализаций используются синтетические RMAT-графы, которые хорошо моделируют реальные графы из социальных сетей, Интернета: R-MAT: A Recursive Model for Graph Mining (English paper, PDF). В конкурсе рассматриваются неориентированные RMAT-графы со средней степенью связности вершины 32, количество вершин является степенью двойки. Участники конкурса могут самостоятельно выбирать размер графа. Параллельный и последовательный генераторы графов встроены в пример реализации.
Использование при расчете производительности заранее рассчитанного количества пройденных дуг необходимо для корректного сравнения реализаций, разные алгоритмы могут проходить разное количество дуг для решения той же задачи. Реализация SSSP может использовать любой алгоритм. По своему усмотрению разработчики могут менять внутреннее представление графа, не используя информацию о вершинах, с которых будет происходить поиск. Время построения собственного внутреннего представления при подсчете производительности не учитывается. Запрещается выполнять поиск с разных стартовых вершин параллельно, также нельзя передавать информацию от вызова функции поиска с одной стартовой вершины к вызову функции поиска с другой стартовой вершины.
Для проверки правильности работы реализованных алгоритмов предусмотрена процедура валидации: для одной из стартовых вершин производится запись в файл массива с расстояниями от стартовой вершины до всех остальных. Этот массив можно затем сравнить при помощи специальной утилиты с таким же массивом, полученным для тех же входных данных на тестовой реализации, входящей в состав примера реализации.
Пример реализации
Доступна версия 0.4 примера последовательной реализации алгоритма SSSP, а также инфраструктуру для последовательной (одноузловой) и распределенной генерации графа, проверки правильности работы алгоритмов можно скачать здесь.
Заявки
Заявки на участие в конкурсе принимаются до 28 (26) февраля включительно по адресу graphHPC@dislab.org. В заявке должны быть указаны: фамилия, имя и отчество участника; организация; архитектура системы; размер графа и полученная производительность. Также должны быть приложены исходные коды реализации, с помощью которой получены результаты. По этому же адресу принимаются запросы на удаленный доступ к системам, на которых проводится конкурс.
Вопросы
Если у Вас возникли какие-то вопросы, просьба писать по адресу graphHPC@dislab.org.