Программа

Программа в формате PDF
Слайды докладов единым архивом (14 МБ)

9:30-10:00
Регистрация участников
10:00-10:15
Приветствие участников GraphHPC-2015
Сулимов В.Б., д.ф.-м.н., НИВЦ МГУ
Симонов А.С., к.т.н., ОАО «НИЦЭВТ»
10:35-10:55
Позднеев А.В., к.ф.-м.н., IBM
Задача выявления сообществ в графах встречается во многих областях исследований: анализе социальных сетей, системной биологии, оптимизации электросетей. Масштабируемость и производительность существующих алгоритмов ограничена мелкозернистым характером коммуникаций и нерегулярностью шаблона доступа к памяти и интерконнекту. В данном докладе будет представлен алгоритм высокой степени масштабируемости, ориентированный на параллельные вычислительные системы с распределенной памятью. В описываемом методе используется новый оригинальный способ представления данных, позволяющий эффективно организовать обработку динамических графов. Будут рассмотрены результаты исследования масштабируемости алгоритма на суперкомпьютерах архитектуры Blue Gene/Q и Power7-IH для графов, включащих до сотен миллиардов ребер. Свойства сходимости данного алгоритма и эффективность его реализации дают возможность выявления сообществ в очень больших графах за время порядка нескольких секунд. Материалы для доклада любезно предоставлены доктором Fabrizio Petrini (IBM Research) и будут опубликованы в трудах конференции IPDPS-2015.
10:55-11:15
Дарьин А.Н., к.ф.-м.н., Т-Платформы
В докладе описывается разработанная в компании Т-Платформы оптимизированная структура для хранения графа, которая позволяет существенно повысить локальность доступа к памяти и упорядочить коммуникации между процессами, а также упрощает распараллеливание на потоки внутри каждого из процессов. Приводятся результаты для бенчмарка поиска вширь (BFS).
12:45-13:05
Слесаренко А.В.; Филиппов А.Н.; Романов А.В.; Зотов Ю.А., к.ф.-м.н., Huawei Russian Research Center
Автоматическая специализация программ - давно применяемая практика оптимизации кода, основанная на использовании информации о конкретном применении программы. В докладе пойдет речь о новом методе автоматической специализации программ под различные реализации абстрактных типов данных. В качестве примера будут рассмотрены графовые алгоритмы.
Определяя абстрактный тип данных для описания вычислений с графами, можно не фиксировать внутреннее представление, а лишь определить допустимые операции, такие как добавление ребер/вершин, поиск соседей и т.д.
Выразив алгоритм в терминах операций над абстрактным графом, можно его затем автоматически трансформировать в алгоритм оперирующий с любой конкретной реализацией графа, такой как матрица смежности или список смежных вершин, используя при этом преимущества конкретного представления данных и выполняя проблемно-ориентированные оптимизации кода.
В докладе будет рассказано о предлагаемом методе, как и почему он работает, а также описаны результаты его применения к некоторым графовым алгоритмам.
11:15-11:45
Кофе-брейк
11:45-12:05
Колганов А.С., ИПМ РАН
В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. В докладе будет рассмотрена реализация алгоритма поиска в ширину (BFS) для обработки больших графов на кластерах с многоядерными процессорами и графическими ускорителями. Будут описаны оптимизации данного алгоритма на одном GPU, а также некоторые оптимизации для ускорения коммуникаций между узлами при использовании нескольких GPU.
12:05-12:25
Черноскутов М.А., ИММ УрО РАН; C. Bekas, PhD; Y. Ineichen, PhD, IBM Research
В основе метрики центральности по подграфам лежит математический аппарат, дающий возможность отличать вершины в графе друг от друга лучше, чем это позволяют сделать некоторые другие метрики. Однако алгоритм вычисления метрики центральности по подграфам обладает кубической сложностью в зависимости от количества вершин в графе. Данный факт сильно затрудняет точный расчет значений данной метрики для каждой вершины в динамически меняющемся графе. В данной работе представлен эвристический алгоритм позволяющий выполнять динамическое обновление метрики центральности по подграфам для некоторых типов графов.
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
Семенов А.С., к.т.н.; Головина Е.А.; Мукосей А.В., DISLab/ОАО «НИЦЭВТ»
При построении неструктурированных расчетных сеток для сложных геометрий в инженерных газодинамических (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. Фуршет