Графы, анализируемые в Facebook очень разноообразны, также мы работаем с множеством разных алгоритмов. Среди них, как классические page rank или поиск связных компонентов так и узкоспециализированные алгоритмы анализа графов.
Разнообразие алгоритмов и огромный размер данных ставят высокие требования к качеству инфраструктуры. Многие известные алгоритмы и системы обработки данных были разработаны и протестированы на графах размером в несколько миллиардов ребер. Графы, с которыми нам приходится работать часто в десятки и даже сотни раз больше по размеру.
В представленной работе мы описываем наш опыт масштабирования и добавленные расширения и улучшения системы с открытым исходным кодом Apache Giraph, которые позволили нам решать задачи на графах с триллионом и больше ребер. Помимо изменений внесенных в Apache Giraph мы представляем наш опыт управления кластером в многопользовательском окружении и результаты измерения производительности нашей системы.

В докладе рассматривается реализация задачи построения минимального остовного дерева в графе (MST) для суперкомпьютеров с распределенной памятью. В основе реализации лежит алгоритм GHS, специально разработанный для распределенных вычислительных систем, который авторам доклада удалось значительно оптимизировать. Исследование производительности производились на кластере "Ангара-К1" с сетью Ангара в сравнении с кластером МВС-10П с сетью Infiniband. На 32 узлах кластера "Ангара-К1" удалось оперативно обработать граф, состоящий из 0.5 млрд вершин и 17 млрд ребер.

Будет рассказано о задачах, исследуемых в нашей лаборатории, широкая востребованность которых хорошо известна. Это ­– кластеризация многодольного графа (каждый кластер представляет максимальное число долей и минимальное число вершин из одной доли), согласование большого числа деревьев в единое дерево, редакционное расстояние между CC-графами (такое расстояние между последовательностями широко используется, но между деревьями появилось недавно), оптимальное продолжение на всё дерево CC-графов, заданных в листьях дерева. CC-граф определяется как ориентированный граф с вершинами полной степени не более 2; исследование таких графов представляет большой прикладной интерес. Перечисленные задачи нами математически исследуются и реализованы для суперкомпьютера, результаты доступны на http://lab6.iitp.ru/. Некоторые из них нетривиально опираются на пакеты целочисленного линейного программирования. Отметим важность и нетривиальность компьютерного приготовления исходных графов в этих задачах, которая была бы невозможна без распараллеливания вычислений.

Многие графовые алгоритмы можно выразить через операцию умножения разреженных матриц. Например, задачи определения показателя центральности по посредничеству (betweenness centrality), нахождения компонент сильной связности, построения кратчайших путей в графе можно решить, выполнив последовательность умножений разреженных матриц. Адаптация конкретного алгоритма умножения разреженных матриц к определенной предметной области достигается путем выбора подходящего полукольца элементов матриц, над которыми выполняется умножение. В данном докладе мы представляем новый высокомасштабируемый алгоритм умножения разреженных матриц, основанный на методе средней точки. Мы покажем применение алгоритма для матриц над полем вещественных чисел в приложении к задаче построения матрицы плотности в теории электронной структуры. Вычислительные преимущества алгоритма связаны с тем, что распределение элементов матрицы по процессам и шаблон межпроцессных коммуникаций отражают структуру взаимодействия в атомной системе. Мы демонстрируем слабую масштабирумость алгоритма до 59,319 процессов MPI и сильную масштабируемость до 185,193 процессов MPI на суперкомпьютере IBM Blue Gene/Q. В фокусе данного доклада - устройство алгоритма, опубликованного в http://dx.doi.org/10.1021/acs.jctc.5b00382.

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

Доклад представляет продолжение работы по реализации распределенного поиска в ширину (BFS). В реализации добавлена многопоточность и модифицирован алгоритм оптимизации поиска в ширину по направлению. В докладе приведены результаты исследования производительности разработанной реализации на кластере "Ангара-К1" с высокоскоростной коммуникационной сетью Ангара. Работа выполнена в компании Т-Платформы.

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

В докладе рассматривается расширение программной модели Charm++ для повышения эффективности решения задач с мелкозернистым параллелизмом. Предлагаемое расширение заключается во введении нового типа объектов в программную модель Charm++ микрообъектов (или микро-chare объектов), которые позволяют осуществлять
декомпозицию задач на десятки или сотни тысяч объектов на одно процессорное ядро. Такая мелкая гранулярность характерна для графовых алгоритмов, реализованных в парадигме vertex-centric. Разработанный подход сравнивается с существующей методологией программирования параллельных задач на Charm++ на примере синтетического теста HPCC RandomAccess и одной из базовых графовых задач — поиск вширь (breadth-first search), более точно — ее асинхронной версией (asynchronous breadth-first search).

Трудности параллельного программирования усугубляются наличием различных платформ и парадигм, для каждой из которых приходится составлять программу практически с нуля. Существует потребность в языке высокого уровня, в котором можно было бы выразить только один раз математическую структуру алгоритма, а затем вывести приемлемый программный код для желаемой платформы. Предлагается проект такого языка, называемого PAMELA (Parallel MEtaLAnguage). Его семантика основана на парадигме потока данных (dataflow), в которой вычисления активизируются по готовности входных данных. Наряду с текстовой формой, этот язык имеет естественную графическую форму. Его возможности демонстрируются на примере параллельной версии Лувенского метода обнаружения сообществ в графах. Графическая форма дает наглядность и удобство не только для написания и восприятия программ, но также для содержательной отладки, анализа свойств, обсуждения возможных решений, выявления проблем с производительностью. Ясность и компактность определения языка открывают возможности выполнения эквивалентных преобразований, направленных на оптимизацию и эффективную трансляцию в различные целевые платформы.

Большие и реалистичные графы необходимы как для исследования алгоритмов так и для тестирования систем обработки данных. К сожалению, реальные графы доступные для исследователей на несколько порядков меньше графов с которыми приходится работать крупным компаниям. Предоставить доступ к реальным графам часто не представляется возможным из соображений безопасности данных пользователей. Генераторы синтетических графов являются решением одновременно гарантирующим сохранность пользовательских данных и обеспечивающим доступ к реалистичным графам. Практическое значение таких генераторов определяется их способностью производить графы с реалистичными свойствами, такими как распределение степеней вершин и локальных коэффициентов кластеризации. Кроме того, генераторы графов должны быть способны воспроизводить масштаб реальных графов, с миллиардами вершин и триллионами ребер. В этой работе мы предлагаем Darwini, геренератор графов способный воспроизвести множество ключевых характеристик реальных графов. В частности, Darwini воспроизводит распределения локальных коэффициентов кластеризации, степеней вершин и смежных вершин. В сравнении с другими алгоритмами генерации графов, Darwini лучше сохраняет другие метрики реальных графов, такие как, распределения значений page rank, собственные значения матрицы смежности и k-core декомпозицию. Помимо описания алгоритма, мы открываем доступ к исходному коду Darwini, реализованному на основе Apache Giraph и позволяющему создавать синтетические графы с триллионами ребер.