Как графовые алгоритмы ищут маршруты

Жители Москвы, Петербурга или Нижнего Новгорода практически каждый день встречаются с графами - схемами линий метрополитена. Это самый простой пример использования графа — способа визуализации связей между определенными объектами. И на самом деле таких примеров большое множество. С помощью графовых алгоритмов Яндекс.Карты ищут для нас оптимальный, а главное, быстрый маршрут, а социальные сети предлагают подружиться с друзьями наших друзей. Младший научный сотрудник Научно-исследовательского вычислительного центра МГУ Илья Афанасьев рассказывает, как работают графы и для чего они нужны.

- Чем занимается ваша лаборатория в НИВЦ МГУ?

- Лаборатория занимается суперкомпьютерными вычислениями, а также их сопровождением. Мы помогаем пользователям в оптимизации программ, что позволяет более эффективно использовать ресурсы суперкомпьютерного комплекса, а также разрабатываем собственные программы для суперкомпьютеров.

- Над чем работаете вы?

- Я работаю над несколькими проектами. Основная сфера моих научных интересов — анализ эффективности параллельных программ. Создавать программы на самом деле непросто. А когда дело касается суперкомпьютеров, управления множеством серверов, которые нужно синхронизировать, то это в разы сложнее. Кроме того, в современном мире существует множество различных типов процессоров, архитектур. Интересно изучать то, как разные классы приложений ведут себя на каждом из типов процессоров. Это важно знать при создании новых суперкомпьютерных центров — какие архитектуры лучше использовать для конкретного класса задач. Благодаря нашему богатому опыту оптимизации суперкомпьютерных приложений мы пытаемся  понять, на каких архитектурах те или иные классы задач работают лучше или хуже. Мне интересен подкласс графовых алгоритмов.

- Что собой представляют эти алгоритмы и для чего они нужны?

- Многие проходили графы в рамках курса школьной математики. Граф — это набор вершин, то есть точек, и некоторых связей между вершинами — ребер или соединений. На рисунке граф выглядит очень просто: это точки и, собственно, палочки, их соединяющие. С точки зрения математики, всё просто. Но с точки зрения реального мира, граф гораздо более сложный и важный объект. На самом деле в виде графа можно представить самые разные объекты окружающей нас действительности.

К примеру, мы с вами пользуемся социальными сетями. Связи между пользователями в социальной сети — это и есть граф. Например, во «ВКонтакте» есть отношения дружбы. Если вы добавите меня в друзья, то с точки зрения графа мы с вами будем вершинами графа, а отношение дружбы будет ребром нас соединяющим. Таким образом, вся социальная сеть, в которой миллионы пользователей и еще больше связей между ними, образует собой граф большого размера с высокой сложностью обработки. Сложность заключается в том, что такой граф очень неоднороден. Все пользователи разные. У меня, например, друзей немного. Но есть известные личности, у которых множество друзей и подписчиков. Это одна из причин, по которой графовые объекты сложно обрабатывать на современных системах.

- В каких еще случаях могут применяться эти алгоритмы?

- Например, графы часто применяются в навигации. Скажем, мы хотим создать эффективную карту, которая предскажет нам кратчайший путь из точки А в точку Б. Подобные сервисы предоставляют Google и Яндекс. Как здесь применяются графы? Любая транспортная сеть — это тоже граф, ведь у нее есть некоторые стыки. В случае дорожной сети города перекрестки — это вершины, а дороги, соединяющие перекрестки — ребра. Задача поиска кратчайшего пути — одна из самых распространенных для графов. И этих путей может быть несколько. Например, первый укажет кратчайший путь для пешехода, другой — в объезд пробок для автомобилиста. Поэтому мы ищем все кратчайшие пути и пытаемся оптимизировать маршрут пользователя.

- Как с этими алгоритмами работают специалисты по суперкомпьютерам?

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

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

Когда мы реализуем некий алгоритм на суперкомпьютере, мы сразу можем прогнать его на различных классах входных графов. У нас всегда есть на чем проверить наши алгоритмы. И мы пытаемся оптимизировать их, чтобы алгоритмы работали максимально быстро на различных целевых архитектурах. А доступен нам крайне широкий спектр суперкомпьютерных архитектур: центральные процессоры, графические ускорители, векторные компьютеры, что позволяет определять, какая из архитектур имеет больший потенциал для обработки графов.

- То есть уже существуют готовые графы, которыми можно пользоваться?

- Есть много готовых примеров. Конечно, если я захочу прогнать свою задачу на дорожном графе Москвы, то, возможно, я не разыщу такой граф. Но я легко могу отыскать граф дорог Нью-Йорка, который будет иметь похожие свойства. Ясно, что не для каждого объекта создан граф. Но для большинства типов объектов можно найти похожие примеры, на которых проверяются алгоритмы.

- Сколько времени уходит на создание графа?

- Время сильно зависит от предметной области. Конечно, граф социальной сети и граф дорог Нью-Йорка создаются абсолютно по-разному. В одном случае, например, специалисты скачивают страницы социальной сети, скачивают связи и генерируют граф. А в случае дорожного графа, возможно, приходится создавать его вручную.

- Для чего разрабатываются алгоритмы на основе графов?

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

Допустим, вы пользуетесь сервисом по подбору друзей в «ВК». Социальная сеть предлагает вам варианты: «Возможно, вы знаете Алешу Попова». И вы думаете: «Действительно ли я знаю Алешу Попова? Ну, может, знаю, может, нет». По какому алгоритму это работает? Скорее всего, система анализирует ваше ближайшее окружение и кратчайшие пути пересечения. И так для каждого пользователя необходимо рассчитать все круги его общения, как они пересекаются, и попытаться эту информацию как-то агрегировать. При этом граф социальной сети постоянно меняется. Получается, что все расчеты необходимо проводить в реальном времени. Кто-то добавил Петю, а кто-то Ваню, и в зависимости от этого подсказки могут меняться.

Мы же пытаемся оптимизировать графовый алгоритм на суперкомпьютере, сделать его быстрее. Чем быстрее разработанный нами графовый алгоритм, тем быстрее компании, для которых актуальна подобная обработка данных, смогут предоставить информацию своим пользователям, и, возможно от этого их жизнь станет лучше. Именно поэтому важна быстрота.

- По этому же принципу работают стриминговые сервисы, предлагающие нам фильмы?

- Абсолютно верно. Как и музыка в «ВК» или Яндексе, когда вам предлагают композицию или плей-лист на основе прослушанного, пытаясь угадать, какая из композиций вам понравится. Ясно, что алгоритмы в каждом случае свои. Но необходимость в анализе эффективности фундаментальных алгоритмов всегда важна.

- Вы упомянули, что граф социальной сети постоянно меняется. Но как тогда хранится весь этот объем данных?

- Все опять же зависит от типа графа. Как правило, граф хранится в памяти компьютера. У суперкомпьютера оперативная память на порядок больше, чем у ноутбуков или смартфонов. Поэтому граф либо загружается в память компьютера полностью, либо с диска по частям. И обновление ребер происходит в режиме реального времени. Обычно, сохраняется список его  вершин, и для каждой вершины сохраняется список ребер. При такой структуре хранения добавить одно ребро не сложно — у одной из вершин прибавляется сосед. Поэтому такой формат вполне эффективен.

- Но граф тогда становится больше, тяжелее.

- Именно так. Изначально социальная сеть насчитывает несколько тысяч пользователей, соответственно и граф небольшой. Но по мере роста числа пользователей граф увеличивается. Однако зачастую мы работаем не с последней модификацией графа (текущей версией социальной сети), а с некоторым ее срезом по времени. То есть используем данные за определенный день, создаем из него граф и работаем с ним.

- Существуют ли альтернативы?

- В данном случае альтернативы ни к чему. Граф — это просто некоторая математическая модель. Конечно, ее можно представить аналогичными моделями, скажем, в виде разрежённой матрицы — таблички, в которой почти все числа — нули. Граф и разреженная матрица — тождественные понятия. То есть, графы можно представлять матрицами.

Но почему все используют именно графы? Потому что это удобная модель, которую легко приложить к конкретным задачам. Конечно, графовые алгоритмы не всегда бывают эффективными и не всегда работают быстро. Но граф всегда удобен при математическом описании конкретных задач. Вы не сможете предложить для кассового аппарата иную схему счета. Можете, конечно, но вряд ли  она будет настолько удобна. Так и в нашем случае, например, социальную сеть удобнее представить графом. И альтернативы не нужны.

Другой вопрос, что альтернатива есть на уровне разных графовых алгоритмов. Так, чтобы решить задачу по поиску кратчайших путей, можно использовать алгоритм Дейкстры, алгоритм Беллмана-Форда, алгоритм дельта-степпинга. И здесь альтернатива важна, поскольку выбор алгоритма для решения конкретной задачи сильно влияет на скорость решения.

- Какие главные задачи стоят сегодня перед специалистами, которые работают с графами?

- Сейчас наибольшую трудность вызывает растущий объем графов. Поэтому их все сложнее обрабатывать. Даже если мы запустим обработку графа на суперкомпьютере, это не всегда будет быстро и эффективно. Дело в том, что графовые алгоритмы крайне неэффективно работают на современных вычислительных системах. Что я имею в виду? У любого процессора есть пиковая производительность — количество операций в секунду или скорость загрузки данных из памяти. При обработке графовых структур данных пиковые показатели производительности никогда не достигаются. Почему? Потому что структура графов такова, что связи между вершинами графа в большинстве своем случайны.  При обработке данных связей между вершинами происходят случайные обращения к памяти. А случайные обращения к памяти компьютера — это всегда медленно. Именно поэтому графовые алгоритмы плохо ложатся на современные архитектуры, а процессоры используются неэффективно — большую часть времени работы алгоритма они простаивают, ожидая получения данных из памяти.

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

- Есть идеи как это сделать?

- Мы уже сейчас над ними работаем. Необходимо аккуратно исследовать фундаментальные графовые алгоритмы и стандартизировать (описать) всевозможные подходы к их оптимизации для различных архитектур. Это свяжет воедино графовые алгоритмы, архитектуры суперкомпьютеров и различные типы входных графов. Данная связь образует некий треугольник, на основе которого мы сможем понять, как, на каких архитектурах и какие алгоритмы выгодно решать, чтобы достичь максимальной быстроты и эффективности вычислений.