![]() |
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Задача суперкомпьютерного кодизайна крайне нетривиальна: алгоритмы обладают различными свойствами, что в совокупности с большим разнообразием архитектур компьютеров и определяет сложность создания эффективных приложений. Показательный пример – это графовые алгоритмы, при реализации которых необходимо учитывать целое множество параметров: собственно алгоритм, модификации алгоритма, программные и микроархитектурные оптимизации, формат хранения и представления графа, а так же модификации структур данных, учитывающие особенности архитектуры конкретных компьютеров. Данный проект направлен на то, чтобы сделать процесс суперкомпьютерного кодизайна более четким и конструктивным, выделив набор качественных и количественных характеристик. В дальнейшем именно этот набор характеристик позволит оценить, как подойти к анализу алгоритмов, программ, входных данных и архитектуры компьютеров, чтобы на выходе получить параллельное приложение, эффективно использующее возможности целевого компьютера. Апробация разработанных подходов будет выполнена на примере компьютеров с общей памятью, что является распространенной вычислительной платформой для графовых алгоритмов. Архитектуры для анализа: многоядерные, векторные, графические. Алгоритмы для анализа: алгоритмы для решения не менее 5 графовых задач.
Co-design problem is extremely important in modern supercomputing: various algorithms have different properties, which together with a large variety of available computer architectures determine the complexity of developing efficient applications. Graph algorithms is an important family of algorithms for this research, since their implementations require the developer to consider many implementation features: the algorithm itself, algorithm modifications, software and micro-architectural optimisations, graph storage format, as well as modifications of data structure. All these implementation features must be carefully coordinated with specific properties of target architectures. The aim of this project is to make the process of supercomputer co-design more clear and constructive, highlighting a set of qualitative and quantitative characteristics. This set of characteristics will allow to analyse algorithms, program, input data and computer architecture properties, in order to develop a parallel application, which efficiently utilises capabilities of target platform. The developed approaches will be verified on shared memory systems, which are frequently used for implementation of graph algorithms. Architectures for analysis: multi-core, vector computers, GPUs. Algorithms for analysis: algorithms for solving at least 5 graph problems.
грант РФФИ |
# | Сроки | Название |
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. |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".