Количественные и качественные характеристики процесса суперкомпьютерного кодизайна: от свойств алгоритмов до особенностей архитектуры компьютеровНИР

The analysis of quantitative and qualitative characteristics of supercomputing co-design: from properties of algorithms to supercomputer design features

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

грант РФФИ

Этапы НИР

# Сроки Название
1 1 октября 2019 г.-4 сентября 2021 г. Количественные и качественные характеристики процесса суперкомпьютерного кодизайна: от свойств алгоритмов до особенностей архитектуры компьютеров
Результаты этапа: Одним из основных результатов проекта является предложенный метод, основанный на принципах суперкомпьютерного кодизайна, который позволяет создавать эффективные реализации графовых алгоритмов для современных суперкомпьютерных архитектур с общей памятью. Основная идея предложенного метода заключается в согласованном выборе целевой архитектуры, а так же важнейших атрибутов программной реализации — алгоритма, модификаций алгоритма, форматов хранения данных, и оптимизаций. В ходе проекта были рассмотрены следующие архитектуры: графические ускорители NVIDIA GPU, векторные процессоры NEC SX-Aurora TSUBASA, а также многоядерные серверные процессоры Intel Xeon (микроархитеткур Skylake и Cascadelake) и ARM Kunpeng 920. Различия в данных свойствах позволяют рассмотренных архитектурам с принципиально различной степенью эффективности и производительности решать различные графовые задачи. К примеру, графические ускорители NVIDIA и векторные процессоры NEC SX-Aurora TSUBASA оборудованы быстрой HBM2 памятью (с пропускной способностью до 10-12 раз превышающей пропускную способность DDR4 памяти, устанавливаемой во многие многоядерные центральные процессоры), что позволяет данным архитектурам существенно ускорить решение различных графовых задач, относящихся к классу memory-bound. Однако, далеко не все графовые алгоритмы подходят для реализации на данных архитектурах, вследствие необходимости использовать SIMD (векторные вычисления), эффективно задействовать множество ядер, а также использовать специализированные шаблоны доступа к памяти. Кроме того, для данных архитектур необходимо использовать специализированные оптимизации и структуры данных, подробно описанные в приложенном полном отчете. Этап (1) предложенного метода заключается в выборе наиболее подходящий целевой архитектуры для решения конкретно поставленной графовой задачи на основе совместного анализа свойств существующих алгоритмов решения данной задачи, а также свойств исследуемых суперкомпьютерных архитектур. Так, в работе были выделены основные свойства алгоритмов, необходимые для их эффективной реализации на современных архитектурах с быстрой памятью. Так же были выделены типовые шаблоны в информационных графах алгоритмов, препятствующие эффективной реализации графовых алгоритмов на рассматриваемых архитектурах с быстрой памятью. На этапах (2) и (3), производится выбор алгоритма, наиболее подходящего для реализации на выбранной целевой архитектуре. Данный выбор производится на основании анализа ряда свойств алгоритмов, в том числе последовательной и параллельной сложности, ширине ярусно-параллельной формы, анализа свойств информационного графа и ряда других. После этого производится модификация выбранного алгоритма, позволяющая более эффективно производить его последующую параллельную реализацию для конкретной целевой архитектуры (к примеру, при необходимости изменяется/уточняется порядок обхода вершин и ребер графа). На (4) этапе предложенного метода производится выбор формата хранения графа и других сопутствующих дополнительных структур данных, подходящих для выбранной целевой архитектуры. На данном этапе проекта был проведен детальный анализ существующих традиционных форматов хранения графов — CSR, списка ребер, и матрицы смежности, однако было показано, что без значительных изменений данные форматы плохо подходят для архитектур с быстрой памятью. Поэтому, был детально исследован эффект от применения нескольких модификаций данных форматов. Для этого несколько из исследуемых графовых алгоритмов были реализованы для всевозможных рассмотренных форматов хранения графов, после чего было проведено сравнение производительности полученных реализаций. Проведенное исследование показало, что использование данных модификаций форматов хранения графов позволяет значительно ускорить реализации графовых алгоритмов для некоторых архитектур. Так, разница в производительности между CSR форматом и VectCSR форматом в среднем составляет от 5 до 8 раз для NEC SX-Aurora TSUBASA и 1-6 раз для NVIDIA GPU. В тоже время для центральных процессоров Intel Xeon данная разница значительно меньше — всего 1–1.5 раз. Таким образом, в рамках предложенного метода удалось сформулировать рекомендации, какой из форматов с большой долей вероятности лучше использовать для определенных архитектур. На (5) этапе предложенного метода производится выбор и применение необходимых оптимизаций графовых алгоритмов, на основе сформированного списка типовых оптимизаций графовых алгоритмов для рассматриваемых архитектур, а также применение дополнительных микроархитектурных оптимизаций. Выбор и оценка эффекта от применения различных оптимизаций производится за счет анализа динамических характеристик программ, в подробности описанных для графических ускорителей NVIDIA, процессоров Intel Xeon и ARM Kunpeng, а также векторных процессоров NEC SX-Aurora TSUBASA. Наконец, на (6) этапе производится всесторонняя оценка производительности, эффективности и энергоэффективности разработанных реализаций на основе метрик TEPS (Traversed Edges Per Second) и используемой пропускной способности памяти (GB/s). Метрика производительности TEPS позволяет сравнивать реализации между собой (например при использовании различных форматов хранения графов), в то время как метрика используемой пропускной способности памяти позволяет оценить эффективность использования подсистемы памяти целевой архитектуры, что, в свою очередь, позволяет дать оценку эффективности реализации, поскольку графовые алгоритмы относится к классу memory-bound, а значит их производительность и эффективность определяются скоростью работы с памятью. Наконец, для сравнения энергоэффективности используется метрика TEPS per watt. Важным результатом, полученным в ходе выполнения проекта, является то, что были предложены принципиально новые оптимизации для рассматриваемых архитектур, позволяющие получить более высокую производительность по сравнению с существующими библиотечными аналогами. Так, для графических ускорителей NVIDIA GPU была исследована возможность применения оптимизации на основе динамического параллелизма для балансировки параллельной нагрузки для части вершин графа с высокой степенью связанности, использование unified-памяти для обработки графов, размер которых не позволяет разместить их в памяти GPU, а так же использование multi-задачности (CUDA streams) для конкурентной обработки групп вершин с различной степенью связанности. Для векторных архитектур (на примере NEC SX-Aurora TSUBASA) были предложены оптимизации на основе использования векторно-ориентированного формата хранения графа VectCSR и изменения порядка обхода ребер графа, позволяющего обрабатывать графы с использованием векторных инструкции максимальной длины, каждая из которых имеет последовательный либо локализованный шаблон доступа к памяти. Кроме того, существующие известные оптимизации были классифицированы, после чего была изучена необходимость их применения для различных рассматриваемых в работе архитектур. Подробные рекомендации о том, для каких архитектур наиболее принципиально применение каждой из рассмотренных оптимизаций. При этом эффект от применения оптимизаций каждой из групп для различных архитектур был исследован как с точки зрения получаемого ускорения за счет применения каждой конкретной оптимизации, так и за счёт анализа различных динамических характеристик работы программ. К примеру, была исследована взаимосвязь оптимизации кластеризации графа (в графе изменяется порядок вершин с целью повышения эффективности использования кэш-памяти при обработке косвенных адресаций) с такими метриками как L2/texture efficiency для архитектуры NVIDIA GPU, а так же метриками из утилиты ftrace для NEC SX-Aurora TSUBASA, характеризующими эффективность использования различных уровней иерархии кэш-памяти. Другой пример — исследование взаимосвязи оптимизации балансировки параллельной нагрузки (когда для вершин с различной степенью выделяется различное количество CUDA-нитей или CPU/векторных ядер) с метриками warp_execution_efficeincy, achieved_occupancy и др., а также метриками утилиты ftrace. Предложенный метод был применен для разработки эффективных реализаций выбранного набора из пяти фундаментальных графовых алгоритмов (поиск кратчайших путей, поиск в ширину, поиск связанных компонент, Page Rank), на примерах которых будет продемонстрировано, что предложенный метод позволяет разрабатывать реализации графовых алгоритмов с производительностью, близкой к пиковым возможностям для рассматриваемых целевых архитектур. Разработанные реализации графовых алгоритмов была были исследованы на большом числе входных графов (как синтетических, так и реальных) с точки зрения метрик производительности, эффективности и энергоэффективности. Было показано, что во многих случаях разработанные реализации демонстрируют более высокую производительность в сравнении с библиотечными аналогами (Ligra, Galois, GAP Benchmark Suite, Medusa, Gunrock) за счет аккуратного согласования свойств, выбора оптимизаций и использования ключевых архитектурных особенностей исследуемых вычислительных систем. На основе проведенного исследования в диссертационном совете МГУ.01.19 аспирантом была защищена кандидатская диссертация «Исследование и разработка методов эффективной реализации графовых алгоритмов для современных векторных архитектур» по специальности 05.13.11.

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

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