ИСТИНА

Проект направлен на исследование потенциала векторной обработки данных для использования в архитектуре будущих компьютеров. Рассматривается применение идей векторной обработки как для конструирования перспективных высокопроизводительных вычислительных систем, так и для разработки методов решения экстремально больших задач, оперирующих большими объёмами данных и интенсивно взаимодействующих с памятью. Векторная обработка имеет значительный потенциал, и его развитие может привнести серьезное новое позитивное качество в разрабатываемые сейчас архитектуры экзафлопсных вычислительных систем. В рамках проекта будет проведен анализ теории и практики векторной обработки данных, особенностей ее аппаратной реализации и поддержки со стороны стека программного обеспечения. Созданные методы будут апробированы на комплексе алгоритмов, ориентированных на обработку графов сверхбольших размеров, содержащих миллиарды вершин и дуг. Все направления исследований данного проекта будут проецироваться на основные классы современных компьютеров, имеющих в своей архитектуре элементы векторной обработки: суперкомпьютеры 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 в векторизованные.