ИСТИНА

Фундаментальная проблема высокопроизводительных вычислений – это необходимость аккуратного согласования структуры алгоритмов и программ с особенностями архитектуры компьютеров. Возможности современных компьютеров велики, но если хотя бы на одном из этапов процесса решения задачи согласования не будет, то и эффективность работы компьютера будет близка к нулю. Серьезнейшая проблема, решение которой ищут во всем мире. Компьютеры быстро меняются. За последние сорок лет сменилось уже шесть поколений архитектур, вызвавших необходимость кардинальных изменений в программном обеспечении. Векторные компьютеры, векторно-параллельные, массивно-параллельные, компьютеры с общей памятью, кластеры из машин с общей памятью, компьютеры с ускорителями... Вычислительное сообщество через это прошло, но каждый раз все программное обеспечение нужно было, по сути, переписывать заново. Cейчас нет никаких оснований надеяться, что ситуация в будущем изменится к лучшему. Уже сейчас рассматриваются перспективные варианты архитектур, где будут использованы легкие и/или тяжелые вычислительные ядра, ускорители, идеи SIMD и data-flow обработки, и очевидно, что для полного использования потенциала таких компьютеров нужно будет опять переписывать код. Основная идея, на которую опирается данный проект, состоит в том, что свойства самих алгоритмов никак не зависят от вычислительных систем, существующих сейчас или будущих. И с этой точки зрения детальное описание свойств алгоритмов имеет очень высокую самостоятельную ценность. Каждый раз, когда будет возникать задача эффективной реализации алгоритма на некотором компьютере, ответ на вопрос о потенциальных возможностях самого алгоритма будет содержаться в этом описании. Детальное описание алгоритма будет сделано один раз, после чего оно может быть многократно использовано для реализации данного алгоритма в различных программно-аппаратных средах. Не менее важна и вторая, машинно-зависимая часть данного исследования, которая посвящена описанию особенностей программной реализации алгоритмов с учетом конкретных программно-аппаратных платформ. Подобное деление на две части сознательно сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют перспективность их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ в конкретных программно-аппаратных средах. Что составит основу описания алгоритмов? Это серьезный вопрос, требующий исследования. Уже сейчас понятно, что в него войдут многие нетривиальные свойства: параллельная сложность алгоритма, ресурс и свойства параллелизма, особенности информационного графа, вычислительная мощность, анализ свойств локальности данных, анализ потенциала масштабируемости для систем со сверхвысокой степенью параллельности, список наиболее эффективных реализаций каждого алгоритма и многие другие. Помимо составления описания алгоритмов, не менее важная задача проекта – это первичное наполнение каталога. Помимо собственно описания целого множества алгоритмов и их реализаций для классов архитектур, это определит технологию формирования каталога, подключив к его наполнению все сообщество. Результат - wiki-энциклопедия, размещенная в Интернете, посвященная структуре алгоритмов и программ. Сейчас нет даже ее аналогов, но она крайне необходима. Умение эффективно работать со свойствами алгоритмов (выделять, описывать, анализировать, интерпретировать) станет широко востребованным уже через несколько лет. Это будет верно как для экзафлопсных суперкомпьютерных систем высшего диапазона производительности, так и для всех других компьютерных платформ: от серверных до мобильных.

The fundamental problem of high-performance computing is the necessity for accurate coordination of algorithm and program structure with hardware features leading to high efficiency. Capabilities of modern computers are great, but if there is no coordination between the algorithmic implementation on the given hardware platform the resulting efficiency of the implementation can be very low. This is a very serious problem, and its solution is being investigated worldwide. Computers systems have been changing rapidly. Six generations of computer architectures have caused fundamental changes in algorithmic and software implementations over the past forty years. These changes have led to architectures changing from vector to vector-parallel to massive-parallel computers to clusters of shared memory machines to computers with accelerators. The computational community has struggled to keep pace, but in each case much of the underlying software had to be rewritten to achieve the desired performance levels. There is currently no reason to expect the situation will change for the better in future. Promising new types of architectures with light/heavy computational cores, accelerators, data-flow and SIMD data processing are already being considered, and it’s has become obvious that in order to achieve full potential of such computers we will have to rewrite application software again and again. The basic idea behind this project is that features of algorithms are independent from any computational system. From this point of view a detailed description of an algorithm’s features is essential. If there is an issue of providing an efficient implementation of the algorithm on a given computer, the answer to the question about the potential of the algorithm will be contained in this description. A detailed description of a given algorithm will be done once, and after that it can be used repeatedly for implementations of this algorithm on different computing platforms. Equally important is the second, machine-dependent part of this research, which is devoted to describing features of an algorithm’s software implementation concerning a particular software-hardware platform. This separation of machine-dependent features is made intentionally in order to separate these features of algorithms, which define their perspective implementations on parallel computational systems from a range of questions associated with consequent stages of programming and execution of the resulting programs on particular computing systems. The basis of such descriptions will be critical to this investigation. It is clear that such a description will include many non-trivial features such as: parallel algorithm complexity, resource of parallelism and its properties, features of an informational graph, computational power of the algorithm, data locality analysis as well as analysis of scalability potential for highly-parallel systems, and many others. In addition to the description of the algorithm , a critical feature of this project is a catalogue of such algorithmic features. We expect the scientific computing community to participate in building and describing the wide range of algorithms and their implementations on different computational platforms. This will build the basic catalogue by involving the scientific community. The result will be an online wiki-encyclopedia, devoted to algorithmic and programming structures. There is currently no system inexistence, and it is highly needed. The ability to work efficiently with algorithmic features, such as categorizing, describing, analyzing, and interpreting, will become highly in-demand and lead to better productivity by programmers and lead to greater efficiency of implementation. This will be true for both exascale supercomputers of the highest performance range and for all other computer platforms ranging from server to mobile.

В результате выполнения данного проекта будут получены следующие результаты. - На основе исследования и формализации процесса отображения алгоритмов на архитектуру параллельных вычислительных систем будут выделены этапы, составные части, взаимосвязи и особенности процесса отображения. Это, в частности, предполагает, что будут выделены фундаментальные свойства алгоритмов, определяющие эффективность их реализации на современных компьютерных платформах; будут выделены машинно-зависимые и машинно-независимые свойства программ, определяющие эффективность их реализации на современных компьютерных платформах; будут разработаны методы анализа степени масштабируемости алгоритмов и программ, а также методы анализа степени локальности использования данных. - На основе проведенного исследования процесса отображения будет разработана технология описания алгоритмов, их свойств и особенностей, влияющих на эффективность из выполнения на различных суперкомпьютерах; описание алгоритмов будет построено так, что будут выделены отдельно машинно-независимая и машинно-зависимая части описания. - На основе разработанной технологии будет выполнено описание свойств целого множества реальных алгоритмов и их реализаций для классов архитектур; данные описания составят стартовый вариант контента для энциклопедии по свойствам алгоритмов, а разработанная технология описания алгоритмов станет технологией его получения. - Крайне важный результат исследований – это собственно открытая энциклопедия в сети Интернет по свойствам алгоритмов и особенностям их реализации на различных программно-аппаратных платформах с возможностью коллективной работы над энциклопедией мирового вычислительного сообщества.

В авторский коллектив проекта входят крупные специалисты в области численных методов линейной алгебры, параллельных вычислений, методов решении задач на компьютерах с параллельной архитектурой, в области систем и средств для суперкомпьютеров. В частности, Д.Донгарра, сыграл принципиальную роль в разработке широко распространенных в мире пакетов и систем: EISPACK, LINPACK, BLAS, LAPACK, ScaLAPACK, Netlib, PVM, MPI, ATLAS, PAPI. Вл.В.Воеводин - руководитель проектов Parallel.ru, V-Ray, АГОРА, X-Com, является одним из организаторов суперкомпьютерного комплекса МГУ. Д.Донгарра является одним из организаторов списка Top500 самых мощных суперкомпьютеров мира, а Вл.В.Воеводин - списка Top50 самых мощных суперкомпьютеров СНГ. Авторским коллективом проведены исследования по разработке подходов к определению тонкой информационно структуры программ. Спроектирован комплекс инструментальных средств, направленный на автоматизацию создания эффективных параллельных программ для параллельных вычислительных систем с общей и распределенной памятью. Разработана комплексная методология статического и динамического анализа структуры программ, методология выявления по исходному тексту многоступенчатой иерархической структуры больших программных комплексов. На основе обнаруживаемых информационных связей в программах построены новые критерии, в том числе, неулучшаемые, для установления параллелизма вычислений, выполнения эквивалентных преобразований программ, выявления большого числа нетрадиционных свойств программ и т.п. Созданы эффективные методы практической реализации данных критериев. У авторского коллектива проекта есть значительный задел и в области исследования динамических характеристик программно-аппаратных сред. Разработана система мониторинга данных системного уровня, позволяющая для каждого приложения определять как типичные значения характеристик поведения, так и обнаруживать аномалии, сигнализирующие о деградации реальной производительности суперкомпьютерных систем.

В течение трёх этапов выполнения проекта No 14-11-00190 «Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем» в 2014-2016 годах были произведены работы в точном соответствии с намеченным планом работ. Данные работы позволили успешно завершить выполнение проекта, достигнув всех намеченных при старте проекта целей. Основная задача, которая ставилась в данном проекте – это разработка фундаментальных основ и формализация процесса отображения алгоритмов на архитектуру параллельных вычислительных систем. основным результатом проводимых исследований является публичная энциклопедия в сети Интернет по свойствам алгоритмов с возможностью коллективной работы всего вычислительного сообщества. На первом этапе были выделены фундаментальные свойства алгоритмов, определяющие эффективность их реализации на современных компьютерных платформах. Всё множество этих свойств разделено на машинно-зависимые и машинно-независимые свойства, определяющие эффективность их реализации на современных компьютерных платформах. В результате проведенных исследований окончательно сформировалась структура описания алгоритма, которая состоит из трёх основных разделов. Первый раздел посвящён описанию машинно-независимых свойств алгоритмов, второй - описанию машинно-зависимых свойств последовательных и параллельных реализаций. Явно выделен третий раздел для списка литературы по описываемому алгоритму, которую авторы использовали при подготовке конкретного описания, причём здесь же приводятся ссылки на первоисточники и классические работы в этой области. В начале описания алгоритма помещается карточка алгоритма, в которую выносятся основные свойства, характеризующие данный алгоритм. 1. Свойства и структура алгоритмов 1.1 Общее описание алгоритма 1.2 Математическое описание алгоритма 1.3 Вычислительное ядро алгоритма 1.4 Макроструктура алгоритма 1.5 Схема реализации последовательного алгоритма 1.6 Последовательная сложность алгоритма 1.7 Информационный граф 1.8 Ресурс параллелизма алгоритма 1.9 Входные и выходные данные алгоритма 1.10 Свойства алгоритма 2 Программная реализация алгоритма 2.1 Особенности реализации последовательного алгоритма 2.2 Локальность данных и вычислений 2.3 Возможные способы и особенности параллельной реализации алгоритма 2.4 Масштабируемость алгоритма и его реализации 2.5 Динамические характеристики и эффективность реализации алгоритма 2.6 Выводы для классов архитектур 2.7 Существующие реализации алгоритма 3 Литература Разработана технология описания свойств и особенностей алгоритмов, влияющих на эффективность выполнения результирующих программ на различных программно-аппаратных платформах. Выполнена отработка методов визуального представления многомерных графов алгоритма и графов алгоритмов с большой сложностью, выделены и сформулированы свойства графа алгоритма, определяющие его сложность. Все методы отрисовки графов алгоритмов подразумевают их визуализацию для небольшого фиксированного объёма входных данных. Разработаны методы исследования локальности использования данных в приложениях. В рамках данной работы акцент сделан на изучении локальности на уровне исходного кода программы. Также предложен второй метод, основанный на двух количественных оценках работы с памятью. Описана методика описания локальности данных в программе, которая основана на указанных методах исследования с помощью визуального анализа и количественных оценок. Данная методика позволяет в едином стиле описывать свойства работы с памятью независимо от особенностей выбранного алгоритма и его реализации. Разработана метрика масштабируемости и показана её применимость для ряда параллельных программ, реализующих задачи из различных областей физических и химических задач, задач линейной алгебры и графовых алгоритмов. Показана возможность сравнения масштабируемости для любых параллельных приложений, основываясь на анализе изменения эффективности реализации приложения. Разработана методика проведения исследования масштабируемости. Получены описания свойств более 30 реальных алгоритмов согласно текущему варианту технологии описания. Полученные на всех этапах выполнения проекта описания алгоритмов включены в текущий вариант энциклопедии. К описанию алгоритмов в рамках Открытой энциклопедии свойств алгоритмов AlgoWiki подключаются внешние пользователи, не входящие в число членов авторского коллектива данного проекта. Всего на 1 декабря 2016 года в проекте зарегистрировано более 300 участников, силами которых уже описано более 200 алгоритмов из самых разных научных областей. Практика описания алгоритмов из самых разных предметных областей в рамках Открытой энциклопедии свойств алгоритмов AlgoWiki показала применимость и универсальность разработанного подхода. Несмотря на ориентацию данного проекта в сторону мощных суперкомпьютерных систем, исследование и детальное описание свойств алгоритмов актуально для всех компьютерных платформ, вплоть до мобильных телефонов и планшетов, которые сейчас также стали параллельными. Были определены требования и спроектирована архитектура электронной энциклопедии по свойствам алгоритмов AlgoWiki в сети Интернет. В качестве основы реализации был выбран программный механизм MediaWiki, реализующий систему управления контентом в стиле так называемой «вики»-технологии. Вики-технология предоставляет возможность создать сайт в сети Интернет, структуру и содержимое которого могут самостоятельно изменять пользователи с помощью предоставленных инструментов. Для форматирования текста и вставки различных объектов предлагается специальная разметка. На базе этой технологии построены Википедия и многие другие сайты. В MediaWiki присутствует возможность поддерживать работу на нескольких языках, что используется нами для развития одновременно русскоязычной и англоязычной версии библиотеки алгоритмов. Что важно, использованная технология позволяет использовать общие ресурсы без необходимости их дублирования. На данный момент в проект включены описания алгоритмов на русском (https://algowiki-project.org/ru/) и английском (https://algowiki-project.org/en) языках, и при необходимости возможно лёгкое добавление других языков на базе уже реализованных средств. Представленные в AlgoWiki статьи с описанием свойств алгоритмов по научной составляющей приближаются к статьям из научных журналов. Это подтверждается многочисленными публикациями с результатами проведенных исследований в материалах российских и зарубежных конференций, а также в статьях, опубликованных в реферируемых журналах. В статьях AlgoWiki сохраняется авторство для всех людей, внёсших существенный вклад в их написание. Главная часть Открытой энциклопедии свойств алгоритмов находится в разделе «Классификация алгоритмов». В этом разделе доступ ко всем описаниям алгоритмов производится по группам, соответствующим типам выполняемых операций. Эта классификация со временем видоизменяется и пополняется по мере подключения к проекту специалистов, описывающих алгоритмы из других научных областей. Раздел «Глоссарий» содержит описание основных терминов, связанных с описанием свойств алгоритма для правильного понимания терминов, которое зачастую являются не вполне однозначным. Раздел «Руководства» содержит инструкции по заполнению отдельных разделов описания алгоритма. Раздел «Справка» содержит материалы, необходимые для обеспечения работы с проектом внешних пользователей. Запущен полнофункциональный вариант открытой энциклопедии в сети Интернет по свойствам алгоритмов и особенностям их реализации на различных программно-аппаратных платформах с возможностью коллективной работы над энциклопедией мирового вычислительного сообщества. В текущей версии Открытой энциклопедии свойств алгоритмов AlgoWiki реализована вся функциональность, запланированная к реализации при старте данного проекта. Для оптимизации доступа пользователей к Открытой энциклопедии свойств алгоритмов AlgoWiki, её веб-сайт был добавлен в систему аналитики поисковой системы Google. Указание корректной информации о веб-сайте в этой системе позволяет повысить релевантность поиска информации, расположенной на сайте, а также позволяет нам оценивать аудиторию и посещаемость AlgoWiki. По данным системы статистики Google Analytics на конец 2016 года среднее число заходов на страницы проекта в день превышает 200. Создаваемая Открытая энциклопедия свойств алгоритмов AlgoWiki не имеет прямых аналогов в мировой практике. Проблема тут не в том, чтобы сделать и опубликовать энциклопедию, работающую на принципах вики-технологий. Проблема в том, что нет не только адекватного контента, но даже понимания, как подобный контент можно было бы формировать. Энциклопедия посвящена свойствам алгоритмов и предоставляет возможность коллективной работы всего вычислительного сообщества над ее пополнением и совершенствованием. В целом, проект оказался исключительно удачным, затронув крайне важную для всего вычислительного сообщества тему. Его результаты заложили прочную основу как для формирования единого подхода для описания базовых и тонких свойств алгоритмов, так и для выполнения исследований и разработок по целому множеству новых направлений в будущем. Адрес Открытой энциклопедии свойств алгоритмов AlgoWiki в сети Интернет: http://algowiki- project.org