ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ИНХС РАН |
||
Компьютеры быстро меняются. С середины 70-х годов сменилось уже шесть поколений архитектур, вызвавших необходимость кардинальных изменений в программном обеспечении, что не только крайне затратно, но и значительно сдерживает развитие других областей. Этот процесс продолжается и сегодня. В настоящее время рассматриваются варианты архитектур, которые составят основу новых поколений. Планируется использование легких и/или тяжелых вычислительных ядер, ускорителей, идей SIMD, векторной и data-flow обработки. Известны планы компании Intel по тесной интеграции классических многоядерных процессоров с FPGA-сегментом на одном кристалле. Суперкомпьютер Sunway TaihuLight, являющийся лидером текущего списка Top500 самых мощных суперкомпьютеров мира, объединяет более 10 миллионов ядер – беспрецедентная степень параллельности. Вместе с этим, в его архитектуре появилось немало особенностей, диктующих специальный стиль написания эффективных программ. Очевидно, что для полного использования потенциала таких компьютеров нужно будет опять заново проектировать и переписывать исходный код. Все эти факты четко показывают, насколько важно знание свойств и особенностей параллельной структуры алгоритмов как сегодня, так и в будущем. Опираясь на сформированный задел, были выбраны следующие три основные задачи, на решение которых и будет направлен Проект-2017. Первая задача – это разработка методов и технологий формирования “архитектурных срезов” в описании алгоритмов. Занимаясь решением задачи на компьютере, разработчику программ, безусловно, нужно знать общие базовые свойства алгоритма, определяющие основу программной реализации. Вместе с этим, не менее важно понимать и степень соответствия свойств данного алгоритма особенностям архитектуры вычислительных систем. Опираясь на эту информацию, уже на начальном этапе разработки приложения можно будет оценить качество будущей реализации на различных архитектурах и принять обоснованное решение в пользу того или иного алгоритмического подхода. Вторая задача отражает удивительную возможность, которую дает Проект-2014 для разработки методики оценки производительности компьютеров. Проблема существует давно, но её удовлетворительного решения к настоящему времени не предложено. Вариант решения этой давней проблемы может быть получен на основе результатов Проекта-2014. В рамках Проекта-2017 будет разработана технология, позволяющая в описании каждого (!) алгоритма AlgoWiki формировать свой независимый топ-список, показывающий качество реализации именно этого алгоритма на различных вычислительных платформах. Вместо трех списков Top500, Graph500 и HPCG, представляющих лишь три точки на всем множестве алгоритмов, расширенный вариант AlgoWiki поможет понять возможности любого компьютера с точки зрения любого описанного алгоритма. С учетом массового сбора и представления параметров работы большого числа компьютеров на множестве алгоритмов всем вычислительным сообществом, предложенное расширение методики Top500 на основе проекта AlgoWiki позволит сказать, что проблема оценки производительности компьютеров закрыта. Третье направление Проекта-2017 является логическим развитием проекта AlgoWiki, расширяющим анализ конкретных алгоритмов экспертной оценкой качества возможных подходов к решению отдельных задач. Для решения каждой задачи можно использовать, как правило, несколько различных алгоритмических подходов. Каждый подход обладает своими особенностями, и те алгоритмы, которые хорошо подходят для одного класса компьютеров, далеко не всегда подходят для другого. В проекте AlgoWiki появится новое измерение, позволяющее перейти с уровня анализа отдельных алгоритмов к анализу различных алгоритмических подходов решения задач. Все три сформулированные выше новые задачи Проекта-2017, как и задачи исходного Проекта-2014, обладают научным единством. Все они опираются на единую основу: технологию полного описания свойств алгоритмов и созданную на этой основе энциклопедию AlgoWiki.
Computers change fast. There have already been six generation changes of computing architectures since the mid-seventies that have caused radical changes in software, which are not just very costly, but also slow down the development of other areas. This process continues today. Scientists are currently examining architectures that will potentially set the foundation for new generations of computers. Light and/or heavy computing cores, accelerators, SIMD, vector and data-flow processing ideas are all being contemplated. Intel is known to be working on a closer integration of classical multicore CPUs with the FPGA segment on the same silicon. The Sunway TaihuLight supercomputer, the current leader on the Top500 list, consists of more than 10 million cores – an unprecedented degree of parallelism. At the same time, its architecture has obtained a few features that dictate the need to follow a special style when writing efficient programs. It is obvious that the full utilization of this computing capacity would require redesigning and rewriting of existing source code. These facts clearly show the importance of knowing the properties and peculiarities of parallel algorithm structures, today and in the future. Based on the existing developments, we selected three key objectives for Project-2017 to address. The first objective is to develop methods and technologies for building “architectural profiles” in algorithm descriptions. When dealing with a task on a computer, the software developer definitely needs to know the general properties of the algorithm that form the basis of software implementation. At the same time, it is just as important to understand the correlation between the properties of this algorithm and the properties of the computing system architecture. With this information in hand, it is easy to assess the future implementation quality on various architectures early on in development, and make an easily justified choice for a given algorithmic approach. The second objective reflects a unique opportunity which Project-2014 enabled for developing a methodology to assess computer performance. The problem has been around for a long time, but no satisfactory solution has been offered to date. One solution to this long-standing problem can be achieved using the Project-2014 results. Project-2017 will develop a technology that allows an independent Top list to be built within a description of each (!) algorithm in AlgoWiki, which would show this specific algorithm’s implementation quality on various computing platforms. Instead of three lists (Top500, Graph500 and HPCG), showing just three spots over the vast expanse of algorithms, this expanded version of AlgoWiki will give a clear view of each computer’s performance from the viewpoint of each algorithm described. Given that the parameters have been collected and represented by the entire computing community for a large number of computers and a variety of algorithms, the proposed expansion of the Top500 methodology on the basis of the AlgoWiki project will basically close out the issue of evaluating computer performance. The third objective for Project-2017 is a logical extension of the AlgoWiki project, expanding the analysis of specific algorithms with an expert evaluation of the quality of approaches offered to solve individual tasks. Each task can typically be addressed with several different algorithmic approaches. Each approach has its own features, and those algorithms that fit one class of computers well aren’t always suitable for another class. In fact, a new dimension will be added to the AlgoWiki project, which moves from analyzing individual algorithms to analyzing various algorithmic approaches to addressing a specific task. All three new objectives for Project-2017 as formulated above, represent scientific unity, along with the goals for Project-2014. They are all based on the same concept: the technology for completely describing algorithm properties and the AlgoWiki encyclopedia built around this idea.
За время выполнения Проекта-2017 будут получены следующие результаты. 1. Будут разработаны методы и технологии формирования архитектурных срезов в описании алгоритмов в рамках энциклопедии AlgoWiki. Опираясь на эту информацию, уже на начальном этапе разработки приложений можно будет оценить качество будущих реализаций применительно к различным архитектурам и принять обоснованное решение в пользу того или иного алгоритма. 2. Будут разработаны методы формирования оценки, показывающей степень соответствия алгоритмов классам архитектуры; будет сформирована шкала оценки; будут отработаны методы разметки описания алгоритмов в соответствии со степенью его соответствия классам архитектуры в рамках энциклопедии AlgoWiki. 3. В рамках Проекта-2017 будет разработана технология, позволяющая в описании каждого алгоритма AlgoWiki формировать свой независимый топ-список, показывающий качество реализации алгоритма на различных вычислительных платформах. С учетом массового сбора и представления параметров работы большого числа компьютеров на множестве алгоритмов всем вычислительным сообществом, предложенное расширение методики Top500 на основе проекта AlgoWiki позволит сказать, что проблема оценки производительности компьютеров закрыта. 4. Будет выполнен принципиально важный переход, расширяющий анализ конкретных алгоритмов экспертной оценкой качества возможных алгоритмических подходов к решению отдельных задач. Будет сформирован набор количественных и качественных оценок преимущества одного алгоритмического подхода над другим, отражающих как теоретический потенциал алгоритмов, так и особенности реализации. Данный результат, который будет реализован и апробирован в AlgoWiki, даст качественно новый взгляд на методы сравнительного анализа разных алгоритмических подходов решения задач применительно к различным классам архитектур вычислительных систем. Являясь естественным продолжением Проекта-2014, новый проект значительно расширяет масштабность применения результатов. Это в полной мере относится как к новому подходу к оценке производительности вычислительных систем (AlgoWiki + списки типа Top500), так и к разработке методов анализа разных алгоритмических подходов к решению задач. Научная значимость поставленных задач определяется тем, что для их решения будут выделены наиболее существенные свойства, присущие как алгоритмам, так и архитектурам компьютеров, на основе чего будут разработаны методы их совместного анализа, что востребовано во многих смежных областях. Важно и то, что все сформулированные положения будут верны как для экзафлопсных суперкомпьютерных систем высшего диапазона производительности, так и для всех других компьютерных платформ: от серверных до мобильных. Причина такой уверенности – это высокая степень параллелизма, которая уже сейчас присуща всем платформам, и которая со временем будет только расти.
Есть значительная степень уверенности в успешном решении поставленных задач и получении запланированных результатов. Авторский коллектив проекта обладает опытом реальной работы на всех классах современных компьютерных систем, начиная от мобильных платформ и заканчивая суперкомпьютерами петафлопсного уровня производительности. Выполнено множество проектов, которые позволили выделить и оценить влияние особенностей архитектуры компьютеров на эффективность выполнения параллельных приложений. Авторский коллектив обладает серьезным заделом в анализе тонкой информационной структуры алгоритмов и программ, который расширился за время выполнения Проекта-2014. В авторский коллектив проекта входят два основных организатора и инициатора списков Top500 (Дж.Донгарра) и Топ50 (Вл.В.Воеводин), что позволит успешно расширить эту методику в соответствии с поставленными в проекте задачами. Запланированы консультации с организаторами и активными участниками списков Graph500 (D.Bager) и HPCG (M.Heroux). Выполняя проекты по разработке суперкомпьютерных приложений, авторами накоплен богатый реальный опыт сравнения различных алгоритмических подходов решения широкого класса задач, что будет активно использоваться в текущей работе. Отметим, что деятельность руководителя проекта в данном направлении была высоко оценена научным сообществом: в октябре 2016 года Дж.Донгарра был избран иностранным членом Российской академии наук. Все ожидаемые результаты проекта будут находиться на мировом уровне.
грант РНФ |
# | Сроки | Название |
1 | 5 мая 2017 г.-31 декабря 2017 г. | Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем |
Результаты этапа: За время выполнения проекта в 2017 получены следующие результаты. Выделены характерные особенности архитектуры современных вычислительных систем (доминирование тяжелых процессорных ядер, использование ускорителей), выполнено их качественное и количественное описание. Сформированы базовые классы архитектуры компьютеров (PROC, PROC^n, n*PROC) с указанием набора особенностей, характерных для каждого класса. Разработаны методы формирования производных классов архитектуры на основе базовых с использованием операций “+”, “*”, “,” и дополнительных модификаторов, сформированы производные классы. Выделены две группы особенностей классов архитектур, определяющих как методы достижения высокой производительности, так и причины ее снижения. Разработана технология исследования взаимосвязи особенностей классов архитектуры со свойствами алгоритмов, опирающаяся на разработанную в Проекте-2014 структуру описания алгоритмов. По каждому пункту описания алгоритмов указано, что в данном месте описания должно быть отражено касательно каждого класса архитектуры. Спроектирован и сформирован набор характерных примеров, иллюстрирующих как хорошее, так и плохое соответствие свойств алгоритма особенностям архитектуры компьютера. Проведены численные эксперименты на компьютерах с различной архитектурой (Multi-core CPU, NVIDIA GPU K40, Intel Xeon Phi (KNL)) с отражением результатов в AlgoWiki. Разработаны методы формирования оценки, показывающей степень соответствия алгоритмов базовым и производным классам архитектуры. Сформирована шкала оценки. Разработана методика выполнения архитектурной разметки. Исследованы технологии построения и осуществлена привязка существующих списков Top500, Graph500 и HPCG к энциклопедии AlgoWiki. Исследованы методы интеграции энциклопедии AlgoWiki с методикой составления классических списков типа Top500. Определен набор элементов структуры описания алгоритмов, которые могут стать основой для формирования множества классических списков типа Top500 в AlgoWiki. Определены способы представления многомерных данных, описывающих свойства алгоритмов по отношению к различным классам архитектур, в рамках энциклопедии AlgoWiki. Предложен вариант метода связанного представления различных алгоритмических подходов решения одной и той же задачи в рамках энциклопедии AlgoWiki. Цепочка "задача-метод-алгоритм-реализация" является основой для описания любой предметной области в рамках Открытой энциклопедии свойств алгоритмов AlgoWiki. Выполнено связанное представление различных алгоритмических подходов на примере одной реально востребованной на практике задачи (цепочка, ведущую от группы задач "Разложения матриц" до алгоритма "Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант"). Показан пример сравнения свойств алгоритмов по нанесенной архитектурной разметке (для графовых алгоритмов, реализующих нахождения кратчайших путей в графе (SSSP), поиск в ширину (BFS), нахождение компонент сильной связности (SCC), поиск мостов (Bridges), нахождение минимального остовного дерева (MST), нахождение транзитивного замыкания (TC)). Таким образом, в ходе выполнения проекта в 2017 году получены все запланированные в отчетном году научные результаты в точном соответствии с планом работ. | ||
2 | 1 января 2018 г.-31 декабря 2018 г. | Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем |
Результаты этапа: За время выполнения проекта в 2018 получены следующие результаты. Показана взаимосвязь понятия локальности программ и свойств алгоритмов; получен список признаков проявления пространственной и временнОй локальности в алгоритмах; описано влияния свойств алгоритмов на свойства локальности в программах. В целом полученные результаты подтверждают сделанные ранее выводы о локальности и производительности работы с памятью. Используемый Top-down подход позволяет подробно оценить, как на практике проявляется разная степень локальности в программах. Показана взаимосвязь понятия масштабируемости программ и свойств алгоритмов; получен список свойств алгоритмов, препятствующих масштабируемости программ; сформирован набор свойств алгоритмов, поддерживающих хорошую масштабируемость программ. Основные факторы, влияющие на масштабируемость приложений: Исследование характеристик коммуникационной сети. 1) Латентность коммуникационной сети 2) Пропускная способность коммуникационной сети 3) Топология коммуникационной сети Исследование компонентов вычислительного узла компьютера. 4) Влияние обращений к жёсткому диску 5) Характеристики оперативной памяти 6) Объём и характеристики кэш-памяти Факторы, связанные с характеристиками примененного алгоритма или исследуемой программы. 7) Дисбаланс вычислительной нагрузки 8) Предел декомпозиции данных Разработаны методы интеграции архитектурных срезов энциклопедии AlgoWiki с возможностью связанного представления различных алгоритмических подходов решения задач. Реализуемая в рамках проекте AlgoWiki разметка алгоритмов согласно их соответствию архитектуре компьютеров является основой для построения методов сравнения разных алгоритмов между собой, что нужно для перехода от анализа отдельных алгоритмов к анализу алгоритмических методов решения задач. Имея подобную разметку, уже можно сравнивать качество соответствия алгоритмов особенностям архитектуры конкретных компьютеров, понять преимущества каждого подхода по отношению к другим, сравнить теоретический потенциал разных алгоритмических подходов решения одной и той же задачи, а также сделать множество других выводов. Реализованы методы интеграции энциклопедии AlgoWiki с разработанной на первом этапе оценкой, показывающей степень соответствия алгоритмов базовым и производным классам архитектуры. Разработаны и реализованы методы формирования архитектурных срезов энциклопедии AlgoWiki. Разработанная на первом этапе проекта оценка, показывающая степень соответствия алгоритмов базовым и производным классам архитектуры, интегрируется в энциклопедию AlgoWiki в идее набора шаблонов, позволяющих размечать страницы описаний в соответствии с определёнными классами соответствия. При этом архитектурные срезы AlgoWiki реализуются на базе этих шаблонов таким образом, чтобы в получившиеся подмножества вошли только страницы энциклопедии AlgoWiki с заданным уровнем соответствия. Реализованы методики построения списков типа Top500, позволяющие исследовать не только наилучшие достигнутые значения характеристик (время, производительность, эффективность и т.п.), но и значения характеристик в произвольном диапазоне числа процессоров/ядер и размеров задачи. Обеспечена возможность проецирования данных значений на характеристики реальных приложений. Проект AlgoWiki является хорошей основой для естественного расширения методики Top500, используемой сегодня для сравнения вычислительных систем. Опираясь на потенциал AlgoWiki, мы переходим от трех точек, отвечающих Linpack, Graph500 и HPCG, к анализу на основе десятков и сотен самых разных алгоритмов. Среди алгоритмов из AlgoWiki для детального анализа и сравнения мы можем брать не все, а выбирать только те, которые интересуют в первую очередь. Если нужный алгоритм в AlgoWiki отсутствует, его можно добавить, стартовав формирование нового, отвечающего ему рейтинга. Исследованы методы интеграции расширенных списков типа Top500 энциклопедии AlgoWiki с ее архитектурными срезами для получения данных по конкретным классам архитектур. Когда данные о выполнении алгоритма на некоторой вычислительной системе заносятся в энциклопедию AlgoWiki, то сохраняется информация обо всей цепочке от задачи до вычислительной платформы. Это дает дополнительную свободу для проведения сравнения и анализа. Получены результаты необходимых численных экспериментов на компьютерах различных классов для первичного наполнения вариантов списков типа Top500, интегрированных с энциклопедией AlgoWiki. Представлены первые версии списков по двум алгоритмам. В реализованных в AlgoWiki примерах (http://top53.parallel.ru/algo_results/task/29, http://top53.parallel.ru/algo_results/task/32 и др.) конкретные значения производительности получены пользователями AlgoWiki и, во многом, определяются их опытом и усердием. Они не обязаны быть максимально возможными: что человек на практике получил, то он здесь и указывает. Требование лишь одно: при занесении данных в базу AlgoWiki пользователи должны указать всю необходимую информацию, которая может потребоваться для воспроизведения и проверки этих результатов, и, возможно, их последующего улучшения. Разработаны методы сравнительного анализа различных алгоритмических подходов решения одной и той же задачи; сформирован набор количественных и качественных оценок преимущества одного алгоритмического подхода над другим, отражающих как теоретический потенциал алгоритмов, так и особенности реализации для различных классов архитектур. В любых звеньях указанной выше цепочки: задача, метод, алгоритм, реализация, вычислительная платформа, можно зафиксировать нужные значения, а остальные можно менять и на этой основе строить новые рейтинги или же находить те комбинации, которые удовлетворяют заданным условиям. Апробированы разработанные методы связанного представления различных алгоритмических подходов на двух новых примерах задач. Выполнена интеграция составленных за время проекта связанных представлений в энциклопедию AlgoWiki. Архитектурные срезы представлены в энциклопедии AlgoWiki. Одной из основных целей создания Открытой энциклопедии алгоритмов AlgoWiki является возможность предоставления пользователю возможности заранее во всех деталях представить всю описываемую цепочку от задачи до реализации, и выбрать те методы и алгоритмы, которые приведут к наиболее эффективным решениям. Таким образом, в ходе выполнения проекта в 2018 году получены все запланированные в отчетном году научные результаты в точном соответствии с планом работ. |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".