Постановка задачи

Предлагается задача расчета Betweenness Centrality в неориентированном графе без весов.

Дан граф G = (V,E) , где V — множество вершин, E — множество ребер.

Цель задачи — для каждой вершины графа v вычислить значение Betweenness Centrality:

BC(v) = \sum\limits_{s \ne v \ne t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}} , где

\sigma_{st} — количество кратчайших путей между вершинами s \in V и t \in V ,

а \sigma_{st}(v) — количество кратчайших путей между вершинами s и t , проходящих через вершину v \in V .

Betweenness Centrality позволяет ранжировать вершины в графе, то есть оценить их важность с точки зрения количества проходящих через них путей.

Betweenness Centrality

На иллюстрации между каждой парой вершин в графе курсирует по одной частице; частицы двигаются только по кратчайшим путям. Каждый раз, когда через вершину графа проходит какая-либо частица, счетчик вершины увеличивается. Чем больше значение счетчика, тем больше радиус вершины, который характеризует "центральность" вершины.

Правила

  • Можно использовать любой язык и технологию программирования (рекомендуется C/C++, OpenMP, CUDA, MPI).
  • Реализация задачи может использовать любой алгоритм.
  • Участникам рекомендуется использовать пример реализации для решения на языках C/C++, при этом настоятельно не рекомендуется изменять главные файлы main.cpp, main_mpi.cpp. Разрешается изменять только функцию run.
  • В случае использования примера, по своему усмотрению разработчики могут менять внутреннее представление графа, используя различные структуры данных, но время преобразований должно включаться во время решения задачи, также как время всех предобработок.
  • Время копирования данных, а также инициализация на GPU должно включаться во время решения задачи.
  • В решении для кластера запрещено считывать граф из файла одновременно всеми MPI-процессами без учета этого во времени решения задачи.
  • Время расчета задачи для одного графа не должно превышать 2х минут.

Требования к результату работы реализации участника

Выходные данные должны содержать:

  • Массив со значениями Betweenness Centrality для каждой вершины (i-ый элемент массива содержит Betweenness Centrality для i-ой вершины).
  • Данный массив должен быть записан в файл <имя графа>.res в бинарном виде (реализовано в примере реализации).

Требования к оформлению решения участника

  • Исполняемый файл, который реализует алгоритм участника конкурса, должен называться solution (или solution_mpi для кластера).

  • В конце работы программы solution должна быть напечатана строчка, содержащая среднее время работы алгоритма:

    avg = <среднее время работы алгоритма>

Вычислительные системы

Предлагается две категории систем для реализации задачи:

  1. Мощный гибридный узел: 2x Intel Xeon E5-2683v3 2.00 ГГц (в сумме 28 ядер или 56 аппаратных потоков), NVIDIA GPU K20x, в узле 64 ГБ памяти.
  2. 36-узловой кластер "Ангара-К1", узлы которого объединены сетью Ангара с топологией 3D-тор.

Организаторы предоставляют вычислительные ресурсы для участников в обеих категориях. Поощряются реализации для других архитектур, такие результаты будут рассматриваться отдельно.

Тестирование

Для оценки производительности реализаций используются два вида синтетических графов: Random Uniform и RMAT.

  • Случайные графы Random Uniform являются одними из самых сложных для достижения высокой производительности.
  • R-MAT-графы хорошо моделируют реальные графы из социальных сетей, Интернета.

Корректность

Перед тестированием на производительность произодится тестирование решения на корректность на секретном наборе графов. При тестировании на корректность относительная или абсолютная погрешность должна быть меньше 10-6.

Положение в таблице результатов

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

В данный момент автоматическая система запускает решение с 1 итерацией, так как предполагается, что решение будет работать долго.

Проведение конкурса

Отправки решений в систему возможны, начиная с самого начала и вплоть до окончания конкурса. В общей онлайн-таблице отображается лучшее решение каждого из участников.

Заморозка таблицы

За несколько дней до окончания конкурса таблица замораживается, в ней остаются видны только лучшие отправки участников на момент заморозки. Решения участников, отправленные после заморозки таблицы, будут видны только автору решения. Дата заморозки таблицы объявляется за несколько дней до заморозки. Итоговые результаты конкурса объявляются на закрытии конференции GraphHPC.

Пример реализации

Пример на С++ включает в себя простое решение задачи, а также необходимую инфраструктуру для генерации графов и проверки решения можно скачать здесь:

  • GraphHPC-0.4-smp.tgz — пример реализации для одного вычислительного узла.
  • GraphHPC-0.4.tgz — полный пример реализации, включающий также решение для кластера.

Вопросы

Если у Вас возникли какие-то вопросы, просьба писать по адресу .

Литература

  1. U. Brandes. A Faster Algorithm for Betweenness Centrality. 2001. A Faster Algorithm for Betweenness Centrality (English paper, PDF).