ИСТИНА

Разработка эффективных реализаций графовых алгоритмов является чрезвычайно важной проблемой современной информатики, поскольку графы удачно моделируют многие объекты реального мира из различных прикладных областей. Так, обработка графов используется при анализе социальных сетей и веб-графов, социально-экономическом моделировании, решении инфраструктурных, биологических и многих других задач. Данный проект направлен на разработку и реализацию эффективного и одновременно простого в использовании архитектурно-независимого фреймворка, предназначенного для решения вычислительно сложных графовых задач. Данный фреймворк будет нацелен на различные классы современных суперкомпьютерных архитектур: векторные процессоры, графические ускорители NVIDIA и многоядерные центральные процессоры. Интерес к векторным архитектурам и графическим процессорам NVIDIA в данном проекте обуславливается тем, что они не только обладают высокой пиковой производительностью, но и зачастую оснащаются памятью с высокой пропускной способностью, что делает их интересными кандидатами для ускорения решения различных графовых задач, интенсивно использующих подсистему памяти. Однако реализации векторно-ориентированных и GPU-ориентированных графовых алгоритмов обычно крайне громоздки и сложны, да и существуют они далеко не для всех аппаратных платформ и типов алгоритмов, вследствие чего разработка графовых фреймворков имеет важное значение для данных архитектур. Кроме того, указанные архитектуры не подходят для решения ряда графовых задач, из-за чего многоядерные процессоры также необходимо часто задействовать для графовых вычислений. Разрабатываемый в ходе данного проекта фреймворк призван предоставить единый интерфейс для всех трех классов целевых архитектур, что позволяет легко переносить различные графовые приложения между разными платформами, доступными пользователю. Кроме того, разрабатываемый фреймворк нацелен на автоматизированную возможность динамического выбора наиболее подходящей целевой архитектуры для заданной графовой задачи и входных данных, что позволит обеспечивать высокую эффективность используемых реализаций.

Developing efficient graph algorithms implementations is an extremely important problem of modern computer science, since graphs are used to model various real-world objects from different application areas. For example, graphs are used for social networks and web-graphs analysis, solving infrastructure and biological problems, social-economic modelling and many others. This project is aimed to design and implement an efficient and simultaneously simple to use heterogeneous graph processing framework, aimed to solving computationally-intensive graph problems. The proposed framework targets multiple modern supercomputing architectures: vector processors, NVIDIA GPUs and multicore CPUs. Modern vector architectures and NVIDIA GPUs usually provide not only a high peak performance but also a high-bandwidth memory, what makes them interesting candidates for efficiently solving various large-scale graph processing problems, which are typically memory-bound. However, vector oriented and GPU-aware implementations of graph algorithms are usually bulky and complicated, thus developing graph frameworks is crucial for such architectures. In addition, these architectures are not suitable for solving some of graph processing problems, which is why multicore CPUs are also frequently used for graph computations. The developed framework is aimed to provide a unified interface for all 3 classes of architectures, which allows to easily port various graph applications between different target architectures available to user. In addition, the developed framework is intended to support dynamic selection of the most suitable target platform for a given graph processing problem and input data, which will ensure high efficiency of the implementations developed using the proposed framework.

В результате выполнения работ данного проекта будут получены следующие результаты: - Будут исследованы подходы к выбору набора графовых абстракций и их эффективной реализации для современных векторных систем с быстрой памятью (NEC SX-Aurora TSUBASA, A64FX, Intel KNL), на основе которых будут разработаны отдельные варианты высокопроизводительного фреймворков для современных векторных систем. Данные фреймворки позволят решать различные классы графовых задач существенно быстрее, чем существующие аналоги фреймворков для смежных классов архитектур — многоядерных центральных процессоров и графических ускорителей. Разработанные фреймворки будут объединены в общий фреймворк для векторных систем, использующий единый набор абстракций. - Будут разработаны высокопроизводительные реализации отдельных фреймворков для современных многоядерных центральных процессоров и графических ускорителей NVIDIA GPU, построенные на основе схожих наборов абстракций вычислений и данных, выбранных для векторных систем. Предложенные реализации фреймворков будут иметь более высокую производительность по сравнению с существующими аналогами для многих графовых задач и целевых архитектур. - На основе предложенного фреймворка будут созданы высокопроизводительные реализации алгоритмов решения не менее 12 фундаментальных графовых алгоритмов (поиска в ширину, поиска кратчайших путей, page rank, сильно связанных компонент, и др.), позволяющие решать широкий класс фундаментальных графовых задач. - Будет произведено объединение разработанных фреймворков для векторных систем, центральных процессоров и графических ускорителей в единый архитектурно-независимый фреймворк, работающий как минимум на следующих архитектурах: NEC SX-Aurora TSUBASA, A64FX, Intel KNL, IBM Power, Intel Xeon, NVIDIA GPU, и имеющий производительность не ниже, чем реализованные прототипы для каждой отдельной архитектуры. Данный фреймворк будет обладать тремя чрезвычайно важными и востребованными на практике свойствами: простотой создания новых графовых реализаций, высокой эффективностью создаваемых графовых программ, причем на всех рассматриваемых архитектурах, а также легкостью переноса полученных программ между различными типами архитектур. - В предложенном фреймворке будет реализована возможность динамического выбора целевой архитектуры и форматов хранения графов на основе либо методов машинного обучения, либо других типов рекомендательных систем. Это позволит существенно упростить крайне нетривиальный процесс выбора наиболее подходящей архитектуры для решения различных графовых задач, что, в свою очередь, позволит во многих случаях увеличить скорость решения подобных задач. - Будет проведен сравнительный анализ эффективности и производительности реализаций графовых алгоритмов на основе предложенного фреймворка как с существующими аналогами, так и между предложенными в ходе данного проекта реализациями для различных целевых архитектур.

Российская команда имеет большой опыт создания высокопроизводительных реализаций графовых алгоритмов для векторных архитектур. Так, в рамках завершенного совместного с японскими коллегами гранта РФФИ №18-57-50005 были разработаны реализации 5 фундаментальных графовых алгоритмов для векторной архитектуры NEC SX-Aurora TSUBASA, демонстрирующих существенно более высокую производительность по сравнению с библиотечными существующими реализациями для многоядерных центральных процессоров и графических ускорителей NVIDIA. Также российская команда имеет обширный и многолетний опыт по анализу структуры программ и алгоритмов, который опирается на цикл фундаментальных и прикладных исследований мирового уровня членов авторского коллектива. Разработана и апробирована на практике во многих проектах теория анализа тонкой информационной структуры программ и алгоритмов. Важно и то, что коллектив российских исполнителей проекта имеет многолетний опыт сопровождения одного из крупнейших в России суперкомпьютерных центров, которым является Суперкомпьютерный комплекс Московского университета. С российской стороны будут использоваться созданные за последние годы методы, технологии и программные средства для глубокого исследования динамических свойств программно-аппаратных сред суперкомпьютеров. Реальная загрузка процессоров, кэш-промахи, особенности работы с памятью, число выполненных инструкций, оценка разного рода задержек, загрузка коммуникационной сети, порождение параллельных процессов и нитей, работа приложения с областью свопинга, анализ интенсивности обмена страницами памяти и многое другое – все это доступно через использование комплекса специальных систем (Octotron, Octoshell, JobDigest, TASC и другие), разработанных в последние годы в НИВЦ МГУ. Данный комплекс апробирован на суперкомпьютерах Московского университета самого разного масштаба, от небольших суперкомпьютеров до петафлопсного суперкомпьютера МГУ «Ломоносов-2».

В рамках данного проекта были получены следующие результаты. Был сформулирован список характеристик и свойств всех целевых архитектур (рассматривались NEC SX-Aurora TSUBASA, многоядерные процессоры x86 с векторными расширениями Intel Xeon, процессоры ARM, Intel KNL, Fujitsu A64FX, графические ускорители NVIDIA), которые позволяют данным архитектурам с различной степенью эффективности решать различные классы графовых задач. Примеры данных свойств: теоретическая пропускная способность оперативной памяти, объем кэш-памяти последнего уровня, скорость доступа к удаленной памяти и др. Был сформирован список из 9 фундаментальных графовых задач и 17 алгоритмов, на решение которых будет нацелен разрабатываемый фреймворк. Примерами данных алгоритмов являются: top-down алгоритм поиска в ширину, алгоритм Шиллоаха-Вышкина поиска связных компонент, алгоритм Белммана-Форда поиска кратчайших путей в графе и др. Были детально исследованы алгоритмические структуры, а также структуры данных, присутствующие в различных графовых алгоритмах из сформированного списка. На основе проведенного исследования были выделены четыре основные алгоритмические абстракции (advance, compute, reduce и generate new frontier) и две структуры данных (граф и подмножество вершин в графе), на основе которых могут быть реализованы рассмотренные графовые алгоритмы. Для данных абстракций были предложены подходы к их эффективной реализации, а также были разработаны прототипы фреймворков на их основе для каждой из целевых архитектур. Учитывая схожесть реализованных подходов, была продемонстрирована возможность использования единого набора абстракций для всех рассматриваемых архитектур. Разработанные прототипы фреймворков для различных архитектур были объединены в единый архитектурно-независимый фреймворк VGL, использующий единый набор абстракций вычислений и данных. Исходные коды разработанного фреймворка доступны для свободного скачивания на GitHub по ссылке: https://github.com/afanasyev-ilya/VectorGraphLibrary. На основе предложенного фреймворка были разработаны реализации всех выбранных графовых алгоритмов. Было проведено исследование области применимости разработанного фреймворка, которое показало, что данный фреймворк применим для большого класса различных графовых алгоритмов и на многих современных архитектурах. Также было проведено тестирование разработанного решения на различных реальных задачах, которое показало корректность его работы. Был проведен детальный анализ производительности разработанного фреймворка на различных платформах, а также сравнение его производительности с существующими аналогами. Данное сравнение показало, что разработанный фреймворк VGL показывает в среднем заметно более высокую производительность, нежели реализации с помощью сторонних фреймворков. Также было проведено исследование применения методов машинного обучения для динамического выбора формата хранения графа в случае конкретно поставленной графовой задачи, а также для автоматизированного выбора целевой архитектуры. В результате были получены решения, которые позволяют в большинстве случаев выбрать оптимальный вариант среди рассмотренных, и применение предложенных методов на практике позволяет увеличить производительность реализаций рассмотренных графовых алгоритмов. Разработанный фреймворк реализован в виде готового решения, и сторонним пользователям предоставлен доступ как к самому решению, так и к существующим реализациям графовых алгоритмов на его основе.