Задача выявления сообществ в графах встречается во многих областях исследований: анализе социальных сетей, системной биологии, оптимизации электросетей. Масштабируемость и производительность существующих алгоритмов ограничена мелкозернистым характером коммуникаций и нерегулярностью шаблона доступа к памяти и интерконнекту. В данном докладе будет представлен алгоритм высокой степени масштабируемости, ориентированный на параллельные вычислительные системы с распределенной памятью. В описываемом методе используется новый оригинальный способ представления данных, позволяющий эффективно организовать обработку динамических графов. Будут рассмотрены результаты исследования масштабируемости алгоритма на суперкомпьютерах архитектуры Blue Gene/Q и Power7-IH для графов, включащих до сотен миллиардов ребер. Свойства сходимости данного алгоритма и эффективность его реализации дают возможность выявления сообществ в очень больших графах за время порядка нескольких секунд. Материалы для доклада любезно предоставлены доктором Fabrizio Petrini (IBM Research) и будут опубликованы в трудах конференции IPDPS-2015.

В докладе описывается разработанная в компании Т-Платформы оптимизированная структура для хранения графа, которая позволяет существенно повысить локальность доступа к памяти и упорядочить коммуникации между процессами, а также упрощает распараллеливание на потоки внутри каждого из процессов. Приводятся результаты для бенчмарка поиска вширь (BFS).

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

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. В докладе будет рассмотрена реализация алгоритма поиска в ширину (BFS) для обработки больших графов на кластерах с многоядерными процессорами и графическими ускорителями. Будут описаны оптимизации данного алгоритма на одном GPU, а также некоторые оптимизации для ускорения коммуникаций между узлами при использовании нескольких GPU.

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

Одним из важных вычислительных ядер в работе с разреженными матрицами является умножение матрицы на вектор. На GPU производительность этого ядра зависит от достигнутой пропускной способности памяти, которая в свою очередь, существенно зависит от порядка обработки элементов матрицы и структуры данных, выбранной для её хранения. В докладе описывается вариант формата SELLPACK с модификациями, позволяющими сократить объём памяти для хранения индексных данных матрицы. Кроме того, для максимизации производительности ядра может использоваться автотюнинг параметров структуры данных и GPU-ядер.

В докладе рассматривается задача переупорядочения вершин графа, построенного по портрету разреженной матрицы, с целью уменьшения заполнения фактора при разложении Холецкого. Для этого используются эвристические методы, основанные на применении алгоритмов теории графов. Существующие библиотеки, решающие данную задачу, имеют MPI-реализации для кластерных систем, однако не учитывают особенности архитектуры многоядерного узла. В докладе будет предложен параллельный алгоритм переупорядочения вершин графа, предназначенный для вычислительного узла с общей памятью. Алгоритм основан на параллельной обработке очереди задач. Для переупорядочения вершин графа используется модификация многоуровневого метода вложенных сечений. В докладе будут продемонстрированы результаты вычислительных экспериментов на матрицах из коллекции Университета Флориды, показывающие, что реализация предложенного алгоритма сравнима по скорости и качеству с широко используемой библиотекой ParMETIS.

Несмотря на наличие большого количества доступных наборов данных и средств для сбора данных из социальных сетей, актуальной является задача создания моделей случайных социальных графов и инструментов для генерации случайных графов с заданным набором свойств. Для обеспечения достоверного тестирования методы анализа социальных данных должны быть применены к множеству выборок с различными свойствами. Сбор реальных данных затруднён вследствие временных затрат на скачивание и обработку больших массивов слабоструктурированной информации. Кроме того, получение набора данных с конкретным множеством свойств зачастую нетривиально.
В докладе будут представлены инструменты для генерации случайных графов, обладающих основными свойствами социальных сетей: безмасштабность, структура сообществ и т.д. Полученные графы могут включать в себя (не)ориентированные рёбра, распределения пользователей по сообществам, пользовательские атрибуты, "лайки" и текстовый контент. Распределённая реализация, выполненная на основе фреймворка Apache Spark, позволяет создавать случайные графы большой размерности для тестирования производительности и качества результатов методов анализа социальных данных.

В докладе рассматривается задача бинарной классификации пользователя социальной сети, то есть отнесение его к одному из двух следующих классов: User, Spamer. В качестве исходных данных выступают граф друзей и дополнительные сведения о пользователях социальной сети Одноклассники. Для ускорения вычисления вектора признаков используется Apache Giraph, запускаемый на Hadoop – кластере, эффективно выполняющемся в многопроцессорной среде.

При построении неструктурированных расчетных сеток для сложных геометрий в инженерных газодинамических (CFD) кодах может возникнуть проблема разбалансировки направлений нормалей граней сетки. Для решения этой проблемы разработан алгоритм корректировки нормалей, основанный на обходе расчетной сетки методом поиска вширь в графе. Сравнение производительности алгоритма на Intel Xeon Phi 5110P и Intel Xeon E5-2660 показывает превосходство ускорителя Intel Xeon Phi на 41% на расчетной сетке, занимающей 4.7 ГБ в памяти.

Общепризнано значение задачи поиска похожих слов в длинных (до 10¹²) строках из большого набора (до 10⁸) строк. Она представляет интерес, если слова присутствуют почти во всех строках, попарно близки и обладают высокой сложностью (слабо сжимаются). Если слова-кандидаты изобразить вершинами, а их похожесть – весами рёбер, то задача эквивалентна поиску плотных массивных подграфов в графе, нередко содержащем 10²⁰ вершин, 10³⁰ рёбер; и даже большего размера. Нами предложен алгоритм с глубоким внутренним параллелизмом эффективного решения этой задачи: построения исходного графа такого размера и нахождения в нём указанных подграфов. В докладе будет изложен алгоритм и его применение в важных естественнонаучных задачах.

Одним из наиболее распространённых алгоритмов построения минимального остовного дерева является алгоритм Борувки. В докладе рассматриваются различные подходы к хранению графа при параллельной реализации алгоритма Борувки: сравнивается производительность и масштабируемость при использовании неизменяемого исходного массива рёбер, списков смежности с различными подходами к их слиянию, а так же списки списков смежностей, позволяющих быстрое объединение вершин. Тестирование реализаций проводилось на RMAT и SSCA2 графах.

В докладе представлен параллельный алгоритм поиска компонент связности в неориентированном графе. Реализованы два параллельных алгоритма: собственный асинхронный BFS (ABFS) и Shiloach-Vishkin (SV). На системе 2xIntel Xeon E5-2690 на различных графах ABFS значительно превосходит по производительность SV, однако на Intel Xeon Phi 7110X производительность ABFS сильно снижается ввиду частых промахов в кэше.