Исследование производительности архитектурно-независимого фреймворка VGL для эффективной реализации графовых алгоритмов

Аннотация

В настоящее время графовые алгоритмы очень часто применяются для решения различных задач моделирования, поскольку многие реальные объекты хорошо моделируются графами (например, дорожная сеть или социальные связи). При этом эффективная реализация таких алгоритмов зачастую очень сложна, что связано, в частности, с нерегулярным доступом к памяти при работе с графами и огромным размером входных графов. Помочь с решением этой проблемы могут графовые фреймворки — программные среды для решения графовых задач. Ранее был разработан архитектурно-независимый фреймворк VGL (Vector Graph Library), позволяющий эффективно реализовывать графовые алгоритмы на различных аппаратных платформах (на многоядерных процессорах с векторными расширениями, графических ускорителях и векторных процессорах NEC). В данной работе было проведено изучение производительности VGL на разных платформах, выполнено сравнение производительности с существующими аналогами, а также предложен и апробирован подход для автоматического выбора формата входного графа на основе методов машинного обучения.