T-GPS обрабатывает граф с триллионом ребер на одном компьютере? Моделирование обработки графиков в масштабе триллиона на одном компьютере представляет новую концепцию обработки графиков

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

В настоящее время для многих промышленных приложений требуется алгоритм графа для обработки крупномасштабного графа (e.грамм., один триллион граней). Таким образом, при разработке и тестировании алгоритмов графа, например, для крупномасштабного графа, обычно используется синтетический граф вместо реального графа. Это связано с тем, что совместное использование и использование крупномасштабных реальных графиков очень ограничено из-за того, что они являются собственностью или их практически невозможно собрать.
Обычно разработка и тестирование алгоритмов графа выполняется с помощью следующего двухэтапного подхода: создание и сохранение графа и выполнение алгоритма на графе с использованием механизма обработки графов.

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

На втором этапе сохраненный граф загружается в основную память механизма обработки графов, такого как Apache GraphX, и выполняет заданный алгоритм графа на движке. Поскольку размер графа слишком велик, чтобы поместиться в основной памяти одного компьютера, механизм графа обычно работает в кластере из нескольких десятков или сотен компьютеров. Следовательно, стоимость обычного двухэтапного подхода очень высока.
Команда исследователей решила задачу традиционного двухэтапного подхода.

Он не генерирует и не хранит крупномасштабный синтетический график. Вместо этого он просто загружает начальный небольшой реальный граф в основную память. Затем T-GPS обрабатывает алгоритм графа на маленьком реальном графе, как если бы крупномасштабный синтетический граф, который должен быть сгенерирован из реального графа, существует в основной памяти. После выполнения алгоритма T-GPS возвращает тот же результат, что и традиционный двухэтапный подход.

Ключевая идея T-GPS заключается в создании только той части синтетического графа, к которой алгоритм должен обращаться на лету, и модификации механизма обработки графов для распознавания части, сгенерированной на лету, как части фактически сгенерированного синтетического графа.
Исследовательская группа показала, что T-GPS может обрабатывать граф из 1 триллиона ребер, используя один компьютер, в то время как традиционный двухэтапный подход может обрабатывать только граф из 1 миллиарда ребер, используя кластер из одиннадцати компьютеров с одинаковой спецификацией. Таким образом, T-GPS превосходит традиционный подход в 10000 раз по вычислительным ресурсам. Команда также показала, что скорость обработки алгоритма в T-GPS до 43 раз выше, чем при традиционном подходе.

Это связано с тем, что T-GPS не имеет накладных расходов на сетевую связь, в то время как традиционный подход имеет много накладных расходов на связь между компьютерами.
Проф. Ким считает, что эта работа окажет большое влияние на ИТ-отрасль, где почти каждая область использует графические данные, добавляя: «T-GPS может значительно увеличить как масштаб, так и эффективность разработки нового графического алгоритма.»

Эта работа была поддержана Национальным исследовательским фондом (NRF) Кореи и Институтом планирования и оценки информационных и коммуникационных технологий (IITP).