|
Регистрация участников. Кофе
|
|
Приветствие участников GraphHPC-2018
|
|
А.С. Семенов, А.С. Фролов, АО «НИЦЭВТ»
|
|
Опыт программирования квантового процессора на примере приближенного алгоритма комбинаторной оптимизации
А.В. Позднеев, IBM
Cкрыть
С квантовыми компьютерами связана фундаментально иная парадигма вычислений. Известен ряд задач, для которых существуют квантовые алгоритмы, являющиеся более эффективными, чем классические. Где еще квантовые компьютеры могут быть быстрее? Как писать для них программы? С появлением первых прототипов квантовых процессоров на эти теоретические вопросы можно начинать искать практические ответы. В данном докладе на примере приближенного квантового алгоритма комбинаторной оптимизации будут представлены возможности инструментария QISKit по выражению квантовых алгоритмов на языке Python и их отображению на конкретный квантовый процессор, а также рассмотрено поведение данного алгоритма на прототипе квантового процессора, доступного через облачный сервис IBM Q experience.
|
|
Р.А. Исрафилов, Intel
Cкрыть
Ускорения математических приложений может быть осуществленно различными способами таким как распределённая обработка, распараллеливание и низкоуровневая архитектурно-специфичная оптимизация, например с помощью векторизации. На сегодняшний день Intel имеет целый ряд математических программных библиотек, использующих данные техники. Cреди них библиотека Intel Math Kernel Library (Intel MKL), которая содержит высоко оптимизированные базовые математические операции, часто встречающиеся в приложениях. В отдельную группу можно выделить приложения связанные с анализом данных и машинным обучением. Intel Data Analytics Acceleration Library (Intel DAAL) – библиотека предназначенная для решения таких задач. В ней представлены типичные строительные блоки, необходимые для создания конвейера по анализу данных. В презентации будет проведён обзор основных особенностей Intel MKL и Intel DAAL, показаны замеры производительности и программные интерфейсы.
|
|
Кофе-брейк
|
|
М.И. Арсаев, NVIDIA
|
|
В.А. Любецкий, К.Ю. Горбунов, ИППИ РАН
Cкрыть
Предлагается линейный по времени и памяти алгоритм, который строит минимальную по суммарной цене последовательность операций, преобразующих любой ориентированный граф из непересекающихся циклов в любой такого же типа граф. Разрешены операции: двойной переклейки вершин, вставки и удаления связного участка рёбер, последние две из них имеют равные цены. Приводится полное доказательство того, что алгоритм находит соответствующий минимум. Рассматриваемая задача является нетривиальным частным случаем общей задачи о преобразовании одного графа в другой, которая, в свою очередь, является примером трудной оптимизационной задачи на графах. В этой общей задаче, которая является NP-полной, графы имеют степень каждой вершины не больше двух и рёбра с теми же именами могут неограниченно повторяться, а операции принадлежат хорошо известному списку. Описаны результаты, полученные авторами для общей задачи. Также авторы получили точный алгоритм оптимальной реконструкции (продолжения) графов из общей задачи с листьев дерева на его внутренние верщины. Все решения имеют два варианта: точный прямой алгоритм и сведение к линейному программированию.
|
|
В.В. Головков, В.А. Чернов, А.В. Портнов, ООО «НитросДэйта Рус»
Cкрыть
Большинство известных SQL СУБД испытывают проблемы при обработке распределенных JOIN запросов. Анализ используемых алгоритмов при разных вариантах распределения данных показывает, что во многих случаях происходит резкая деградация производительности из-за необходимости пересылки по сети слишком больших объемов данных. Анализ каждого конкретного случая показывает, что наиболее эффективным способом обработки JOIN запросов в подобных случаях является использование специального индекса для представления ссылок. Подобные индексы широко используются для представления ссылок или разреженных матриц в разных системах обработки графовых данных. Построение мультимодельной СУБД, объединяющей методы обработки как графовых так и реляционных данных позволило бы существенно повысить эффективность обработки JOIN запросов и существенно расширить области применения распределенных графовых систем.
|
|
Р.А. Исрафилов, Intel
Cкрыть
На сегодняшний день язык программирования Python получил широкое распространение, в первую очередь, за счёт роста доли приложений связанных с анализом данных и машинным обучением. Для этого языка были разработано большое количество математических пакетов, которые стали де-факто стандартами для научных вычислений в Python. Данные пакеты предоставляют удобный и лаконичный интерфейс, однако их производительность зачастую не может сравниться с производительностью кода на C/C++. Поэтому для ускорения существующего кода на Python создан собственный дистрибутив интерпретатора этого языка – Intel Distribution for Python, в который включены оптимизированные с помощью Intel MKL и Intel DAAL популярные математические пакеты. В презентации мы проведём обзор Intel Distribution for Python, покажем примеры использования и продемонстрируем процесс решение прикладной задачи с использованием оптимизированных математических пакетов.
|
|
Обед
|
|
М.А. Черноскутов, ИММ УрО РАН, Уральский федеральный университет
Cкрыть
В докладе описана архитектура системы параллельной обработки графов, позволяющей разрабатывать архитектурно-независимые приложения для обработки графов. Кроме того, система позволяет пользователю абстрагироваться от деталей реализации формата хранения графа. Использование данной системы может быть полезным в различных приложениях науки о сетях.
|
|
А.С. Колганов, ИПМ РАН им. М.В. Келдыша / МГУ им. М.В. Ломоносова
Cкрыть
Поиск в ширину (BFS) является одним из основных алгоритмов обхода графа и базовым для многих алгоритмов анализа графов более высокого уровня. Поиск в ширину на графах является задачей с нерегулярным доступом к памяти и с нерегулярной зависимостью по данным, что сильно усложняет его распараллеливание на все существующие архитектуры. В докладе будет рассмотрена реализация алгоритма поиска в ширину (основного теста рейтинга Graph500) для обработки больших графов на различных архитектурах: Intel х86, IBM Power8+, Intel KNL и NVidia GPU. Будут показаны особенности реализации алгоритма на общей памяти, а также преобразования графа, которые позволяют достичь рекордных показателей производительности и энергоэффективности на данном алгоритме среди всех одноузловых систем рейтинга Graph500 и GreenGraph500.
|
|
С.Л. Блюмин, А.С. Приньков, Липецкий государственный технический университет
Cкрыть
В данной работе рассматриваются практические аспекты графоструктурного моделирования в задачах описания и анализа больших данных, а также развитие матричного представления обобщённых графовых структур. Изложены полученные результаты предварительных исследований и обозначены перспективы дальнейших. Описывается теоретико-множественный и матричный варианты представления графовых структур в контексте
оптимизации вычислений в задачах описания и анализа больших данных. На этом основании показана обоснованность мотивации использования обобщённых графовых структур в таких задачах. Приведён эвристический алгоритм, использующий матричное представ-
ление, преобразования произвольного графа в метаграф.
|
|
А.В. Мазеев, А.С. Семенов, Д.И. Дорофеев, АО «НИЦЭВТ»/МФТИ
Cкрыть
Необходимость выявления аномалий в графах обусловлена потребностью нахождения необычных объектов и действий в различных прикладных задачах (информационная безопасность, финансовые рынки и др.).
Большой интерес представляют методы выявления аномалий без учителя, так как при решении реальных задач не всегда имеется обучающая выборка.
В докладе будут рассмотрены методы выявления аномалий в графах без учителя, а также результаты сравнения этих методов для определенного набора графов.
|
|
Закрытие GraphHPC-2018. Фуршет
|