В рамках семинара пройдет обсуждение проблем обработки больших графов с использованием современных суперкомпьютеров. Главная задача семинара – привлечь внимание специалистов в области HPC к данной теме и обсудить дальнейшие шаги по продвижению технологий параллельной обработки графов. Семинар является дополнением к конференции GraphHPC.

Семинар состоится 26 сентября с 14:10 до 15:50.

Программа семинара

Параллельное разбиение распределенного графа
Н.В. Старостин, А.В. Филимонов, ННГУ

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

Технология решения больших графовых задач на неоднородных вычислительных платформах
И.В. Афанасьев, Вл.В. Воеводин, А.Н. Дарьин, Д. Донгарра, Д.А. Никитенко, А.М. Теплов, МГУ / Yandex Technology GmbH

В работе предложена технология решения графовых задач на гибридных архитектурах. В качестве примера подробно рассмотрены задачи построения минимального основного дерева и поиска кратчайших путей. Для каждой задачи приведено точное математическое описание, а так же результат исследования информационной структуры, на основе чего предлагается алгоритм решения задачи и его эффективная параллельная реализация. Ориентир на гибридные вычисления позволяет эффективно использовать все доступные ресурсы – как многоядерных CPU, так и GPU. Так же для вычислений используется out-of-core алгоритм, позволяющий обрабатывать графы, размер которых значительно превышает объем доступной памяти. Проведены экспериментальные исследования, показавшие высокую производительность и хорошую масштабируемость предложенного решения. Данный подход может быть расширен и на другие задачи над большими графами, актуальность которых в последнее время существенно возросла.

Опыт использования асинхронных программных моделей на базе активных сообщений для решения графовых задач
А.С. Фролов, АО «НИЦЭВТ»

В докладе будут представлены результаты экспериментального исследования нескольких программных моделей (Charm++, ActivePebbles, Grappa), основанных на концепции активных сообщений, на базовых графовых задачах, таких как PageRank, поиск вширь (BFS), поиск кратчайших путей (SSSP) и поиск связных компонент (CC).

Исследование и моделирование параллельных методов расчёта характеристик связности случайных графов
Д.А. Мигов, Д.В. Винс, С.Н. Нестеров, ИВМиМГ СО РАН

В докладе представлены параллельные методы расчёта для двух показателей сетевой надёжности. Предполагается, что отказам подвержены каналы связи, тогда как узлы являются абсолютно надёжными. Для описания подобных сетей используются случайные графы. В качестве показателей надёжности сети рассмотрены характеристики связности соответствующего случайного графа – вероятность связности всех узлов сети и вероятность связности каждой пары полюсов путём ограниченной длины. Точный расчёт показателей сетевой надёжности представляет собой NP-трудную задачу. Экспериментальное исследование предлагаемых параллельных методов позволило настроить параметры алгоритмов оптимальным образом и значительно повысить их масштабируемость. Разработаны модели выполнения указанных параллельных методов. Разработаны и исследованы мультиагентные модели выполнения указанных параллельных методов.

Cовременные коммуникационные сети и технологии Big Data
А.С. Семенов, А.А. Агарков, А.С. Фролов, АО «НИЦЭВТ»

В докладе будет представлен обзор современных технологий Big Data, а также результаты экспериментального исследования влияния характеристик коммуникационной сети кластера на производительность базовых операций и прикладных задач, реализованных с использованием технологии Apache Spark.

Научные направления

Тематика семинара включает следующие вопросы (но не ограничивается ими):

• Параллельные алгоритмы анализа графов
• Приложения, использующие теорию графов
• Модели параллельного программирования и инструментальные средства для разработки графовых приложений
• Исследование производительности вычислительных систем на графовых задачах и синтетических тестах (бенчмарках)
• Графовые задачи и архитектура вычислительных систем, экзафлопсные вычисления
• Графовые задачи и Big Data
• Визуализация графов

Правила представления работ и важные даты

Правила представления работ и важные даты совпадают с общими правилами и датами основной конференции. При подаче статей необходимо выбрать соответствующий трек в системе EasyChair.

Программный комитет

• Воеводин В.В., чл.-корр. РАН, НИВЦ МГУ (сопредседатель)
• Симонов А.С., к.т.н., АО «НИЦЭВТ» (сопредседатель)
• Фролов А.С., DISLab (АО «НИЦЭВТ»)
• Семенов А.С., к.т.н., DISLab (АО «НИЦЭВТ»)
• Позднеев А.В., к.ф.-м.н., IBM
• Дарьин А.Н., к.ф.-м.н., Yandex
• Корж А.А., к.ф.-м.н., Micron
• Черноскутов М.А., ИММ УрО РАН

Контакты

Фролов Александр Сергеевич, DISLab (АО «НИЦЭВТ»), e-mail: alexndr.frolov at gmail com
Семенов Александр Сергеевич, DISLab (АО «НИЦЭВТ»), e-mail: alxdr.semenov at gmail com