Оптимизация разбиения графа методом оптимального разреза вершин: целостный подход

Разбиение графа имеет ключевое значение в распределённых граф-параллельных вычислительных системах, и одновременно оптимизировать стоимость коммуникаций и балансировку нагрузки является сложной задачей. Современные передовые методы, такие как Powerlyra и TopoX, обеспечивают балансировку нагрузки путём случайного распределения рёбер вершин с высокой степенью, что неизбежно приводит к высокой и неограниченной стоимости коммуникаций. В этой статье предлагается модель разбиения графа, которая минимизирует стоимость коммуникаций при максимизации балансировки нагрузки. Конкретнее, мы моделируем разбиение графа как задачу комбинаторного проектирования. Предложенная модель обеспечивает качественное разбиение, которое гарантирует равномерное распределение вычислительной нагрузки между рабочими и минимизирует стоимость коммуникаций с близкой к оптимальной теоретической границей. На основе предложенной модели мы расширяем гибридный алгоритм разреза (hybrid-cut) для степенных (power-law) графов и предлагаем HCPD — гибридный алгоритм разбиения, основанный на комбинаторном проектировании. HCPD использует предложенную модель для одновременной оптимизации балансировки нагрузки и стоимости коммуникаций для вершин с высокой степенью и объединяет эти вершины с их соседями низкой степени на тех же рабочих узлах посредством распространения меток (label propagation) для снижения общей стоимости коммуникаций. Таким образом мы целостно разбием вершины низкой и высокой степени и дополнительно улучшим качество разбиения, в отличие от Powerlyra и TopoX, которые обрабатывают эти две части независимо. Наши эксперименты показывают, что HCPD превосходит Powerlyra в задаче PageRank и работает до 2× быстрее на реальных степенных графах с миллиардами рёбер.