Создание архитектурно-независимого фреймворка для эффективной реализации графовых алгоритмов на современных массивно-параллельных архитектурах c быстрой памятьюНИР

Research and Development of An Architecture-independent Framework for Efficient Graph Algorithm Implementations

Источник финансирования НИР

грант РФФИ

Этапы НИР

# Сроки Название
1 28 января 2021 г.-28 февраля 2022 г. Создание архитектурно-независимого фреймворка для эффективной реализации графовых алгоритмов на современных массивно-параллельных архитектурах c быстрой памятью
Результаты этапа: На первом этапе проекта был сформулирован список характеристик и свойств всех целевых архитектур, которые позволяют данным архитектурам с различной степенью эффективности решать различные классы графовых задач. Примеры данных свойств: теоретическая пропускная способность оперативной памяти, обьем кэш-памяти последнего уровня, скорость доступа к удаленной памяти, и др. Был сформирован список из 11 фундаментальных графовых задач и 17 алгоритмов на решение которых будет нацелен разрабатываемый фреймворк. Примерами данных алгоритмов являются: top-down алгоритм поиска в ширину, алгоритм Шиллоаха-Вышкина поиска связных компонент, алгоритм Белммана-Форда поиска кратчайших путей в графе, и др. Были детально исследованы алгоритмические структуры, а так же структуры данных, присутствующие в различных графовых алгоритмах из сформированного списка. На основе проведенного исследования были выделены 4 основные алгоритмические структуры: advance, compute, reduce и generate new frontier, а также следующие структуры данных: граф, подмножество вершин в графе, массив вершин и массив ребер. Для данных абстракций были предложены подходы к их эффективной реализации на массивно-параллельных векторных архитектурах NEC SX-Aurora TSUBASA, A64FX и Intel KNL, а также были разработаны прототипы фреймворков на их основе для каждой из целевых архитектур. Учитывая схожесть реализованных подходов была продемонстрирована возможность использования единого набора абстракций для всех рассматриваемых архитектур. Разработанные прототипы фреймворков для различных архитектур были объединены в единый архитектурно-независимый фреймворк, использующий единый набор абстракций вычислений и данных. На его основе были разработаны реализации 17 графовых алгоритмов, для которых было показно, что реализации на основе фреймворка существенно опережают существующие аналоги для многоядерных центральных процессоров. Кроме того, для фреймворка была реализована поддержка систем, использующих для вычислений несколько ускорителей SX-Aurora TSUBASA. Наконец, для разработанных реализаций графовых алгоритмов была проведена детальная оценка производительности и корректности.
2 1 марта 2022 г.-17 мая 2023 г. Создание архитектурно-независимого фреймворка для эффективной реализации графовых алгоритмов на современных массивно-параллельных архитектурах c быстрой памятью
Результаты этапа:

Прикрепленные к НИР результаты

Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".