Программа
Программа в формате PDF
Слайды докладов единым архивом (14 МБ)
9:30-10:00 |
Регистрация участников
|
10:00-10:15 |
Приветствие участников GraphHPC-2015
|
10:35-10:55 |
Задача выявления сообществ в графах встречается во многих областях исследований: анализе социальных
сетей, системной биологии, оптимизации электросетей. Масштабируемость и производительность
существующих алгоритмов ограничена мелкозернистым характером коммуникаций и нерегулярностью шаблона
доступа к памяти и интерконнекту. В данном докладе будет представлен алгоритм высокой степени
масштабируемости, ориентированный на параллельные вычислительные системы с распределенной памятью. В
описываемом методе используется новый оригинальный способ представления данных, позволяющий
эффективно организовать обработку динамических графов. Будут рассмотрены результаты исследования
масштабируемости алгоритма на суперкомпьютерах архитектуры Blue Gene/Q и Power7-IH для графов,
включащих до сотен миллиардов ребер. Свойства сходимости данного алгоритма и эффективность его
реализации дают возможность выявления сообществ в очень больших графах за время порядка нескольких
секунд. Материалы для доклада любезно предоставлены доктором Fabrizio Petrini (IBM Research) и будут
опубликованы в трудах конференции IPDPS-2015.
|
10:55-11:15 |
В докладе описывается разработанная в компании Т-Платформы оптимизированная структура для хранения
графа, которая позволяет существенно повысить локальность доступа к памяти и упорядочить коммуникации
между процессами, а также упрощает распараллеливание на потоки внутри каждого из процессов.
Приводятся результаты для бенчмарка поиска вширь (BFS).
|
12:45-13:05 |
Автоматическая специализация программ - давно применяемая практика оптимизации кода, основанная на
использовании информации о конкретном применении программы. В докладе пойдет речь о новом методе
автоматической специализации программ под различные реализации абстрактных типов данных. В качестве
примера будут рассмотрены графовые алгоритмы.
Определяя абстрактный тип данных для описания вычислений с графами, можно не фиксировать внутреннее
представление, а лишь определить допустимые операции, такие как добавление ребер/вершин, поиск
соседей и т.д.
Выразив алгоритм в терминах операций над абстрактным графом, можно его затем автоматически
трансформировать в алгоритм оперирующий с любой конкретной реализацией графа, такой как матрица
смежности или список смежных вершин, используя при этом преимущества конкретного представления данных
и выполняя проблемно-ориентированные оптимизации кода.
В докладе будет рассказано о предлагаемом методе, как и почему он работает, а также описаны
результаты его применения к некоторым графовым алгоритмам.
|
11:15-11:45 |
Кофе-брейк
|
11:45-12:05 |
В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях.
Потребность их использования обусловлена их относительно высокой производительностью и более низкой
стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так
или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют
неструктурные сетки. Примером такой задачи является Breadth First Search (BFS) — поиска в ширину в
неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. В докладе будет
рассмотрена реализация алгоритма поиска в ширину (BFS) для обработки больших графов на кластерах с
многоядерными процессорами и графическими ускорителями. Будут описаны оптимизации данного алгоритма
на одном GPU, а также некоторые оптимизации для ускорения коммуникаций между узлами при использовании
нескольких GPU.
|
12:05-12:25 |
В основе метрики центральности по подграфам лежит математический аппарат, дающий возможность отличать вершины в графе друг от друга лучше, чем это позволяют сделать некоторые другие метрики. Однако алгоритм вычисления метрики центральности по подграфам обладает кубической сложностью в зависимости от количества вершин в графе. Данный факт сильно затрудняет точный расчет значений данной метрики для каждой вершины в динамически меняющемся графе. В данной работе представлен эвристический алгоритм позволяющий выполнять динамическое обновление метрики центральности по подграфам для некоторых типов графов.
|
12:25-12:45 |
Одним из важных вычислительных ядер в работе с разреженными матрицами является умножение матрицы на вектор. На GPU производительность этого ядра зависит от достигнутой пропускной способности памяти, которая в свою очередь, существенно зависит от порядка обработки элементов матрицы и структуры данных, выбранной для её хранения. В докладе описывается вариант формата SELLPACK с модификациями, позволяющими сократить объём памяти для хранения индексных данных матрицы. Кроме того, для максимизации производительности ядра может использоваться автотюнинг параметров структуры данных и GPU-ядер.
|
14:45-15:05 |
В докладе рассматривается задача переупорядочения вершин графа, построенного по портрету разреженной матрицы, с целью
уменьшения заполнения фактора при разложении Холецкого. Для этого используются эвристические методы, основанные на
применении алгоритмов теории графов. Существующие библиотеки, решающие данную задачу, имеют MPI-реализации для
кластерных систем, однако не учитывают особенности архитектуры многоядерного узла. В докладе будет предложен
параллельный алгоритм переупорядочения вершин графа, предназначенный для вычислительного узла с общей памятью. Алгоритм
основан на параллельной обработке очереди задач. Для переупорядочения вершин графа используется модификация
многоуровневого метода вложенных сечений. В докладе будут продемонстрированы результаты вычислительных экспериментов на
матрицах из коллекции Университета Флориды, показывающие, что реализация предложенного алгоритма сравнима по скорости и
качеству с широко используемой библиотекой ParMETIS.
|
13:05-14:05 |
Обед
|
14:05-14:25 |
Несмотря на наличие большого количества доступных наборов данных и средств для сбора данных из
социальных сетей, актуальной является задача создания моделей случайных социальных графов и
инструментов для генерации случайных графов с заданным набором свойств. Для обеспечения достоверного
тестирования методы анализа социальных данных должны быть применены к множеству выборок с различными
свойствами. Сбор реальных данных затруднён вследствие временных затрат на скачивание и обработку
больших массивов слабоструктурированной информации. Кроме того, получение набора данных с конкретным
множеством свойств зачастую нетривиально.
В докладе будут представлены инструменты для генерации случайных графов, обладающих основными
свойствами социальных сетей: безмасштабность, структура сообществ и т.д. Полученные графы могут
включать в себя (не)ориентированные рёбра, распределения пользователей по сообществам,
пользовательские атрибуты, "лайки" и текстовый контент. Распределённая реализация, выполненная на
основе фреймворка Apache Spark, позволяет создавать случайные графы большой размерности для
тестирования производительности и качества результатов методов анализа социальных данных.
|
14:25-14:45 |
В докладе рассматривается задача бинарной классификации пользователя социальной сети, то есть отнесение его к одному из
двух следующих классов: User, Spamer. В качестве исходных данных выступают граф друзей и дополнительные сведения о
пользователях социальной сети Одноклассники. Для ускорения вычисления вектора признаков используется Apache Giraph,
запускаемый на Hadoop – кластере, эффективно выполняющемся в многопроцессорной среде.
|
15:05-15:25 |
При построении неструктурированных расчетных сеток для сложных геометрий в инженерных газодинамических (CFD) кодах
может возникнуть проблема разбалансировки направлений нормалей граней сетки. Для решения этой проблемы разработан
алгоритм корректировки нормалей, основанный на обходе расчетной сетки методом поиска вширь в графе. Сравнение
производительности алгоритма на Intel Xeon Phi 5110P и Intel Xeon E5-2660 показывает превосходство ускорителя Intel
Xeon Phi на 41% на расчетной сетке, занимающей 4.7 ГБ в памяти.
|
10:15-10:35 |
Общепризнано значение задачи поиска похожих слов в длинных (до 1012) строках из большого
набора (до 108) строк. Она представляет интерес, если слова присутствуют почти во всех
строках, попарно близки и обладают высокой сложностью (слабо сжимаются). Если слова-кандидаты
изобразить вершинами, а их похожесть – весами рёбер, то задача эквивалентна поиску плотных
массивных подграфов в графе, нередко содержащем 1020 вершин, 1030 рёбер; и
даже большего размера.
Нами предложен алгоритм с глубоким внутренним параллелизмом эффективного решения этой задачи:
построения исходного графа такого размера и нахождения в нём указанных подграфов. В докладе будет
изложен алгоритм и его применение в важных естественнонаучных задачах.
|
15:25-15:45 |
Кофе-брейк
|
15:45-16:05 |
Одним из наиболее распространённых алгоритмов построения минимального остовного дерева является
алгоритм Борувки. В докладе рассматриваются различные подходы к хранению графа при параллельной
реализации алгоритма Борувки: сравнивается производительность и масштабируемость при использовании
неизменяемого исходного массива рёбер, списков смежности с различными подходами к их слиянию, а так
же списки списков смежностей, позволяющих быстрое объединение вершин. Тестирование реализаций
проводилось на RMAT и SSCA2 графах.
|
16:05-16:25 |
В докладе представлен параллельный алгоритм поиска компонент связности в
неориентированном графе. Реализованы два параллельных алгоритма: собственный асинхронный BFS (ABFS) и
Shiloach-Vishkin (SV). На системе 2xIntel Xeon E5-2690 на различных графах ABFS значительно превосходит по
производительность SV, однако на Intel Xeon Phi 7110X производительность ABFS сильно снижается ввиду частых промахов в кэше.
|
16:25-16:55 |
Объявление итогов конкурса GraphHPC-2015
|
16:55 |
Закрытие GraphHPC-2015. Фуршет
|