![]() |
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Проект направлен на исследование потенциала векторной обработки данных для использования в архитектуре будущих компьютеров. Рассматривается применение идей векторной обработки как для конструирования перспективных высокопроизводительных вычислительных систем, так и для разработки методов решения экстремально больших задач, оперирующих большими объёмами данных и интенсивно взаимодействующих с памятью. Векторная обработка имеет значительный потенциал, и его развитие может привнести серьезное новое позитивное качество в разрабатываемые сейчас архитектуры экзафлопсных вычислительных систем. В рамках проекта будет проведен анализ теории и практики векторной обработки данных, особенностей ее аппаратной реализации и поддержки со стороны стека программного обеспечения. Созданные методы будут апробированы на комплексе алгоритмов, ориентированных на обработку графов сверхбольших размеров, содержащих миллиарды вершин и дуг. Все направления исследований данного проекта будут проецироваться на основные классы современных компьютеров, имеющих в своей архитектуре элементы векторной обработки: суперкомпьютеры NEC, микропроцессоры Intel Xeon, Intel Xeon Phi, IBM Power, ARM. Решение основной задачи данного проекта - исследование потенциала векторной обработки данных для суперкомпьютеров будущего, будет идти сразу по двум встречным направлениям, что идеально отвечает принципам суперкомпьютерного кодизайна. Российская научная группа, НИВЦ МГУ имени М.В.Ломоносова, Россия, в большей степени проводит исследования в области алгоритмов и программного обеспечения. Японская часть совместного коллектива, университет Тохоку, Япония, имея значительный опыт в разработке векторных процессоров, используемых в суперкомпьютерах NEC, делает акцент на проектировании архитектуры векторного процессора следующего поколения.
This project aims to study the potential of vectorized data-processing in future generations of supercomputing architectures. Vectorized data-processing is important both for designing high-performance computing systems and for efficient solving of extremely large-scale problems, which operate with large volumes of data and heavily stress memory hierarchy of target systems. An important subclass of such problems — graph algorithms, which, due to their extremely irregular structure, are incredibly complex to implement efficiently on vector systems, are studied in this project. Within the project, a detailed analysis of theory and practice of vectorized data-processing, implemented in various modern vector architectures such as NEC SX-Aurora TSUBASA vector supercomputers, Intel Xeon microprocessors, Intel Xeon Phi, IBM Power and ARM, is provided. In order to develop efficient vector programs, a new method has been proposed, which is based on a consistent selection of algorithms and their modifications, vector-oriented data structures and different optimization approaches. Each stage of the proposed method is based on a detailed analysis of properties of vector architectures and implementations, including the analysis of vector applications dynamic characteristics, fundamental algorithms properties, and the locality characteristics of proposed data structures. The proposed method has been used to develop efficient vector-friendly implementations of multiple fundamental graph algorithms. The developed implementations, due to the efficient usage of hardware resources of target vector architectures, demonstrate significantly higher performance compared to existing world most well-known graph-processing frameworks and libraries for adjacent classed of supercomputing architectures — multicore CPUs and NVIDIA GPUs. In addition, this project studies SIMD-relationship of modern vector architectures and NVIDIA GPUs: a significant number of common properties and data-processing principles of these architecture classes were identified. The identified common properties open the possibility of porting various classed of applications between vector processors and GPUs, sometimes using automatic conversion tools.
Планируется получить результаты по трем направлениям. Первое направление – это глубокий и критический анализ существующих подходов к реализации идей векторной обработки в архитектуре современных процессоров и компьютеров. Подобный анализ предполагает выделение как сильных сторон реализаций, их конкурентных преимуществ над представителями других классов вычислительных систем, так и проблемных мест, вызывающих падение производительности и определяющих узкие места для классов алгоритмов или же для архитектуры в целом. Второе направление - изучние взаимосвязей, лежащих в основе векторизации и методов обработки, характерных для графических процессоров. В настоящее время графические процессоры широко распространены, в том числе и для высокопроизводительных вычислений, для них создано большое число эффективных программ и инструментов, и развитие активно продолжается. Вместе с этим, векторная обработка и архитектурные особенности графических процессоров имеют много общего, опираясь на общие принципы SIMD-обработки. Особенности этой общности и предполагается исследовать в рамках данного проекта. Третье направление объединяет теорию с практикой и связано с апробацией выполненных исследований и разработанных методов в рамках первых двух направлений. За основу берется исключительно сложный для эффективной реализации класс алгоритмов для решения множества задач на графах и исследуется качество работы программ, использующих доступные элементы векторной обработки.
Участники проекта имеют обширный и многолетний опыт по анализу структуры программы и алгоритмов, который опирается на цикл фундаментальных и прикладных исследований мирового уровня членов авторского коллектива. Разработана и апробирована на практике во многих проектах теория анализа тонкой информационной структуры программ и алгоритмов. На основе как данной теории, так и опыта выполнения большого числа проектов, реализован уникальный проект AlgoWiki, позволяющий описать свойства и особенности параллельной структуры алгоритмов из самых разных областей. Важно и то, что коллектив исполнителей проекта имеет многолетний опыт сопровождения крупнейшего в России суперкомпьютерного центра, которым является суперкомпьютерный комплекс Московского университета. Глубокое понимание законов функционирования предельно больших суперкомпьютерных комплексов, особенностей их работы и сопровождения, тонких деталей и нюансов их архитектуры, потенциальных узких мест - всё это составит основу для успешной совместной работы с японскими коллегами над выполнением данного проекта. Японские партнеры имеют многолетний опыт работы с крупнейшими векторными суперкомпьютерными системами, установленными в центре кибернетических наук (CyberScience Center) университета Тохоку, входящего в число 7 ведущих суперкомпьютерных центров Японии. Более того, руководитель проекта с японской стороны, профессор Хироаки Кобаяши являлся в 2008-2016 годах директором данного центра. Японские соисполнители проекта за последние годы выполнили множество крупных суперкомпьютерных проектов, тесно соприкасающихся по тематике с настоящим проектом. В частности, профессор Хироаки Кобаяши был руководителем национального проекта “Исследование возможностей будущих суперкомпьютерных систем для приложений, интенсивно работающих с памятью” (“Feasible study of a future HPC system for memory-intensive applications”), инициированного Министерством Образования, Культуры, Спорта, Науки и Технологий Японии.
Был проведен анализ существующих подходов к реализации идей векторной обработки на современных суперкомпьютерных системах, демонстрирующий, что векторные вычисления позволяют существенно ускорить compute-bound задачи, а так же многие memory-bound в случае наличия в векторных архитектурах быстрой памяти. В ходе работы были выделены наиболее важные характеристики, сопровождающие векторную обработку данных: латентность доступа к памяти, длина векторных инструкции и конвейера, характер обращений к подсистеме памяти внутри векторных инструкций, а так же шаблон обращений к памяти элементов векторных инструкций. Было детально исследовано влияние данных характеристик на эффективность векторных программ. Были детально рассмотрены модели анализа качества и эффективности векторных программ: cache-aware roofline и top-down модели. Было показано, как данные модели позволяют определить текущие узкие места векторных программ, потенциал дальнейшей оптимизации, а так же эффект от применения векторизации и других оптимизаций. Была детально исследована взаимосвязь векторных систем и современных графических процессоров NVIDIA, существующая в силу принадлежности обеих данных архитектур к классу SIMD. Были детально исследованы и проиллюстрированы схожие и различные принципы вычислений и обработки данных для рассматриваемых классов архитектур на примерах различных типовых вычислительных шаблонов векторных программ. Был сформирован набор из 5 фундаментальных графовых задач (PR, BFS, SSSP, CC, SSWP), для которых в соответствии с принципом суперкомпьютерного кодизайна были разработаны эффективные реализации для современных векторных систем. Для данных задач были детально проанализированы существующие алгоритмы их решения (беллмана-форда, Шиллоаха-Вышкина, top-down, bottom-up и direction-optimizing BFS) и выбраны максимально подходящие для реализации на векторных системах. . Были предложены соответствующие модификации алгоритмов, например изменение порядка обхода ребер графа для эффективного задействования SIMD потенциала архитектур, а так же выбраны векторно-ориентированные форматы хранения графа и дополнительных структур данных (подробнее в разделе 7 приложенного полного отчета). Для разработанных векторных реализаций была детально исследована производительность и эффективность на основе выделенного набора динамических характеристик приложений. Было сформировано множество критических факторов в структуре алгоритмов и приложений, препятствующих векторизации. Наконец, была продемонстрирована возможность автоматической или автоматизированной конвертации GPU-программ, реализованных на основе модели OpenACC в векторизованные.
университет Тохоку | Соисполнитель |
грант РФФИ |
# | Сроки | Название |
1 | 1 января 2018 г.-8 февраля 2019 г. | Исследование потенциала векторной обработки данных для вычислительных систем и приложений с предельными характеристиками |
Результаты этапа: В ходе исследований был проведен критический анализ существующих подходов к реализации идей векторной обработки данных на современных архитектурах. Были выделены как сильные стороны реализаций, их конкурентные преимуществ над представителями смежных классов вычислительных систем, так и проблемные места, вызывающие падение производительности, определяющие узкие места для классов алгоритмов или же для архитектуры в целом. Так же был проведен сравнительный анализ основных критически важных характеристик, сопровождающих векторную обработку, таких как латентность, длина конвейера, расположение элементов вектора в памяти, параметры работы с памятью и ряда других характеристик. Помимо этого был приведен обзор существующих методов, средств и инструментов повышения эффективности, таких как FTrace, Intel Parallel Studio и NVProf. По результатам первичного анализа был сформирован набор графовых алгоритмов (поиска в ширину, поиска минимального сточного дерева, поиска кратчайших путей и поиска сильно связанных компонент), для которых былы выполнены эталонные реализации. Данные реализации были разработаны на основе принципов суперкомпьютерного кодизайна, учитывающих характеристики алгоритмов и особенности архитектуры векторных платформ с учетом ориентации на обработку входных графов предельно большого размера. Кроме того, были исследованы взаимосвязи между векторной обработкой данных и методами обработки данных, характерными для графических процессоров. | ||
2 | 9 февраля 2019 г.-8 июня 2020 г. | Исследование потенциала векторной обработки данных для вычислительных систем и приложений с предельными характеристиками |
Результаты этапа: В ходе исследования был уточнен список графовых задач и алгоритмов, которые могут быть эффективно реализованы на векторных архитектурах: были реализованы алгоритмы решения задач поиска в ширину, поиска кратчайших путей, ранжирования вершин в графе (page rank), поиска связанных компонент и поиска самого широкого пути в графе. Основной акцент при реализации был сделан на новейшую архитектуру SX-Aurora TSUBASA, позволяющую, за счет сочетания быстрейшей в мире пропускной способности памяти, а так же принципов векторной обработки данных, достигнуть существенного ускорения по сравнению с референсными библиотечными реализациями для современных процессоров архитектуры Intel Skylake (10-20 раз), а так же для графических ускорителей NVIDIA V100 GPU (2-5 раз). Эффективность реализованных графовых алгоритмов для векторной архитектуры SX-Aurora TSUBASA была исследована на основе ряда метрик, включающих в себя среднюю длину вектора, используемую пропускную способность памяти, количества промахов в LLC кэш. Данные метрики были собраны с использованием средств профилирвоки (ftrace) для архитектуры SX-Aurora TSUBASA, что позволило продемонстрировать эффективность выполнения созданных реализаций на данной архитектуре: для рада синтетических и графов реального мира разработанные алгоритмы позволяют использовать больше половины пиковой пропускной способности памяти, а так же имеют максимально возможную среднюю длину векторных инструкций. Аналогичным образом с использования средств мониторинга и профилировки (nvprof, vtune) были собраны аналогичные динамические характеристики для архитектур Intel Skylake и NVIDIA GPU, с которыми было произведено сравнение. Так же в ходе исследования была проанализирована взаимосвязь основных принципов и архитектурных особенностей, присущих классической векторной обработке, а так же обработки данных на графических ускорителях NVIDIA GPU. Было продемонстрировано, что, несмотря на наличие ряда общих свойств (SIMD обработка данных, использование быстрой HBM2 памяти, построения систем на основе сопроцессоров), оба класса архитектур так же имеют ряд фундаментальных отличий (в структуре иерархии памяти, подходах к маскированию вычислений, подходов к синхронизациям и обменов данными между различными ядрами и элементами векторной инструкции), что не всегда позволяет реализовывать различные программы и алгоритмы схожим образом с одинаковой степенью эффективности. Так, принципиально различную эффективность для данных классов архитектур будут иметь операции редукции, вычисления преффиксной суммы, ряда графовых алгоритмов, в то время как схожую эффективность будут иметь многие операции линейной алгебры, а так же ряд сеточных задач. Кроме того, были рассмотрены вопросы переноса простейших приложений между архитектурами NVIDIA GPU и SX-Aurora TSUBASA, реализованных на основе параллельных технологий OpenACC и OpenMP соотвественно. В ходе исследования была так же комплексно исследована взаимосвязь между структурой алгоритмов и эффективностью их выполнения на компьютерных системах, опирающихся на векторную обработку. Было показано, что основной причиной падения производительности на векторных архитектурах являются зависимости по данным, нерегулярность структур данных, а так же работы с сильно разреженными структурами данных. Так же были приведены примеры различных графовых алгоритмов, которые не могут быть эффективно реализованы на векторных архитектурах (например подсчет числа треугольников в графе). По результатам работы был сформирован подробный отчет, отвечающий всем заявленным требованиям. |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".