![]() |
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Фундаментальная проблема высокопроизводительных вычислений – это необходимость аккуратного согласования структуры алгоритмов и программ с особенностями архитектуры компьютеров. Возможности современных компьютеров велики, но если хотя бы на одном из этапов процесса решения задачи согласования не будет, то и эффективность работы компьютера будет близка к нулю. Серьезнейшая проблема, решение которой ищут во всем мире. Компьютеры быстро меняются. За последние сорок лет сменилось уже шесть поколений архитектур, вызвавших необходимость кардинальных изменений в программном обеспечении. Векторные компьютеры, векторно-параллельные, массивно-параллельные, компьютеры с общей памятью, кластеры из машин с общей памятью, компьютеры с ускорителями... Вычислительное сообщество через это прошло, но каждый раз все программное обеспечение нужно было, по сути, переписывать заново. 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
грант РНФ |
# | Сроки | Название |
1 | 15 августа 2014 г.-31 декабря 2014 г. | Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем |
Результаты этапа: На первом этапе выполнения проекта № 14-11-00190 «Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем» в 2014 году были произведены работы в точном соответствии с намеченным планом работ. Основная задача, которая ставится в данном проекте – это разработка фундаментальных основ и формализация процесса отображения алгоритмов на архитектуру параллельных вычислительных систем. Основным результатом проводимых исследований должна стать публичная энциклопедия в сети Интернет по свойствам алгоритмов с возможностью коллективной работы всего вычислительного сообщества. На данном этапе были выделены фундаментальные свойства алгоритмов, определяющие эффективность их реализации на современных компьютерных платформах. Всё множество этих свойств разделено на машинно-зависимые и машинно-независимые свойства, определяющие эффективность их реализации на современных компьютерных платформах. Для формирования структуры описания свойств алгоритмов был проведён анализ и выделены ключевые особенности основных классов архитектур параллельных вычислительных систем и суперкомпьютеров, определяющие эффективность реализации алгоритмов. В процессе формирования Структуры описания свойств алгоритмов были решены следующие задачи: - Отработаны способы выделения и описания вычислительных ядер алгоритмов. - Разработаны методы представления макроструктуры алгоритмов, комбинирующие описание как на уровне крупных блоков, так и на уровне микроопераций. - Выработаны и использованы в описании информационных графов алгоритмов общие стандарты для описания полной информационной структуры алгоритмов через покрывающие функции на множестве опорных многогранников. - Разработаны методы и подходы для нахождения и описания параллельной сложности алгоритмов в рамках концепции неограниченного параллелизма. - Разработаны методы определения и описания вычислительной мощности алгоритмов. Эти методы и подходы позволяют определить все необходимые свойства исследуемого алгоритма, как традиционные, так и связанные с использованием параллелизма. Ориентация на использование графа алгоритма гарантирует полноту определения ресурса параллелизма. - Отработка и стандартизация методов визуального представления графа алгоритма (информационной структуры алгоритмов и программ). - Разработаны методы отображения свойств вершин и дуг, отображения параллельных свойств графа. - Иллюстрации описания свойств алгоритмов выполнены согласно разработанным методам визуализации. Разработаны подходы и методы построения профилей использования памяти программами, описаны свойства профилей конкретных алгоритмов, вошедших в пилотную версию Открытой энциклопедии свойств алгоритмов. Метод для получения профиля использования памяти основан на инструментировании исходного кода программы, написанной на языке С/С++. Также решены следующие задачи: - Разработаны методы исследования масштабируемости алгоритмов и программ. - Определена взаимосвязь между масштабируемостью программ, свойствами алгоритмов и особенностями архитектуры параллельных вычислительных систем. - Отработана технология практического исследования масштабируемости и эффективности реализаций алгоритмов на различных программно-аппаратных платформах. - Выполнена серия экспериментов на платформах в диапазоне от малой степени параллелизма (десятки вычислительных ядер) до умеренной (порядка тысячи ядер) и высокой (порядка десятка тысяч ядер) степени параллелизма. - На базе разработанных методов и подходов произведено описание динамических свойств и особенностей реализаций алгоритмов, вошедших в пилотную версию Открытой энциклопедии свойств алгоритмов. В результате проведенных исследований получилась следующая структура описания свойств алгоритмов. 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 Существующие реализации алгоритма Пилотный вариант технологии описания свойств и особенностей алгоритмов отработан при исследовании и описании свойств более 10 реальных алгоритмов согласно текущему варианту технологии описания. На данном этапе основной упор сделан на алгоритмах линейной алгебры. На данный момент выполнено описание структуры следующих приложений: - Разложение Холецкого (метод квадратного корня) для положительно определенных матриц - Суммирование сдваиванием - Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант - Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант - High Performance Conjugate Gradient (HPCG) Benchmark - LINPACK Benchmark - Последовательно-параллельный метод суммирования - Быстрое преобразование Фурье для степеней двойки - Умножение плотных матриц - Умножение плотной матрицы на вектор - Метод Гаусса решения СЛАУ (прямой ход) При описании данных алгоритмов был проанализирован потенциал технологии описания. Составлен ряд изменений и дополнений к данной структуре, направленных на большее соответствие формируемых описаний запросам конечных пользователей. Полученные описания алгоритмов включены в текущий вариант энциклопедии. Были определены требования и спроектирована архитектура электронной энциклопедии по свойствам алгоритмов Algowiki в сети Интернет, выполнено программирование нижнего уровня. В качестве основы реализации используется вики-технология, предоставляющая возможность для организации коллективной работы над проектом. Пилотная версия энциклопедии в сети Интернет находится по адресу http://algowiki-project.org. В настоящее время описания в рамках энциклопедии выполнены на русском языке, в планах создание англоязычной версии и предоставление возможности поддержки двух языков. Главная часть Открытой энциклопедии свойств алгоритмов находится в разделе «Классификация алгоритмов». В этом разделе доступ ко всем описаниям алгоритмов производится по группам, соответствующим типам выполняемых операций. Предполагается, что эта классификация будет со временем видоизменяться и пополняться по мере подключения к проекту специалистов, описывающих алгоритмы из других научных областей. На данный момент классификация алгоритмов имеет такой вид: 1. Векторные операции 2. Умножение матрицы на вектор 3. Матричные операции 4. Разложения матриц 4.1 Треугольные разложения 4.2 Унитарно-треугольные разложения 4.3 Разложения на унитарные и хессенберговы матрицы 4.4 Разложения на унитарные и диагональные матрицы 5. Решение систем линейных уравнений 6. Тесты производительности компьютеров 7. Преобразование Фурье 8. Алгоритмы на графах 9. Алгоритмы поиска 10. Алгоритмы сортировки 11. Вычислительная геометрия 12. Компьютерная графика 13. Криптографические алгоритмы 14. Нейронные сети 15. Алгоритмы оптимизации 16. Алгоритмы теории игр 17. Алгоритмы моделирования квантовых систем 17.1 Алгоритмы моделирования квантовых вычислений 18. Другие алгоритмы Выполненное описание свойств реальных алгоритмов положило основу Открытой энциклопедии свойств алгоритмов Algowiki в сети Интернет. Энциклопедия посвящена свойствам алгоритмов и предоставляет возможность коллективной работы всего вычислительного сообщества над ее пополнением и совершенствованием. Адрес проекта: http://algowiki-project.org | ||
2 | 1 января 2015 г.-31 декабря 2015 г. | Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем |
Результаты этапа: На втором этапе выполнения проекта № 14-11-00190 «Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем» в 2015 году были произведены работы в точном соответствии с намеченным планом работ. Процесс отображения алгоритмов на архитектуру параллельных вычислительных систем весьма сложен и трудно формализуем. Должно учитываться множество факторов, связанных как со структурой самого алгоритма, так и с характеристиками целевой программно-аппаратной среды. На первом этапе выполнения проекта была предложена структура описания алгоритма, максимально учитывающая эти факторы. На данном этапе выполнения проекта это описание было уточнено. Для некоторых разделов описания разработаны пошаговые методики их заполнения. Другие разделы описания сильно зависят от особенностей алгоритмов и их реализаций, для их заполнения предложен ряд образцов на основе описаний конкретных алгоритмов. На текущем этапе выполнения работы была выполнена отработка методов визуального представления многомерных графов алгоритма и графов алгоритмов с большой сложностью. Граф алгоритма - это ориентированный граф, вершины которого соответствуют срабатываниям операций в алгоритме, а дуги – информационным зависимостям. На первом этапе выполнения проекта были разработаны методы визуального отображения простейших графов алгоритмов, однако структура графа алгоритма может быть сколь угодно сложной, а размер – сколь угодно большим, что делает его визуальное представление громоздким и непонятным. Часто граф алгоритма является сложным многомерным объектом, а многие его свойства становятся понятными только при его удачном визуальном отображении. Задачей данного этапа было придумать подход, позволяющий отобразить все особенности графа, максимально сохранив при этом простоту и интуитивность его визуального представления. В текущем году были выделены и сформулированы свойства графа алгоритма, определяющие его сложность. Кроме того, чётко определено понятие многомерного графа алгоритма, разработаны методы, позволяющие визуально отображать сложные и многомерные графы алгоритма. Непосредственный размер графа алгоритма напрямую зависит от входных данных алгоритма. Все методы отрисовки графов алгоритмов подразумевают их визуализацию для небольшого фиксированного объёма входных данных. На текущем этапе выполнения работы были разработаны методы исследования локальности использования данных в приложениях. В рамках данной работы акцент сделан на изучении локальности на уровне исходного кода программы. Для каждой программы собирается профиль обращений в память. Под профилем обращений понимается последовательность выполняемых в программе обращений к данным в памяти, расположенных в том порядке, в котором обращения происходят в программе. Для сбора профиля необходимо выполнить инструментирование исходного текста программы – заменить тип исследуемых структур данных на специальный С++ класс (на данный момент поддерживаются только программы на языке С/С++). При выполнении инструментированной программы виртуальный адрес каждого обращения к замененной структуре данных фиксируется в лог-файл. Одним из самых простых, но при этом достаточно действенных методов исследования локальности является визуальный анализ профиля обращений. Изучение общего профиля позволяет увидеть качественную картину в целом, поскольку зачастую сам пользователь не представляет, каково поведение его программы с точки зрения работы с памятью. Переходя ко всё более детальному анализу профиля, можно изучить его строение вплоть до отдельных обращений. Это позволяет хорошо понять на качественном уровне локальность, то есть близость обращений. Однако для сравнения локальности разных программ, да и для более тщательного анализа, такого подхода недостаточно. Было предложено два метода исследования локальности использования данных в приложениях, основанные на средствах визуального анализа и на применении количественных оценок. В рамках первого метода выполняется изучение построенного визуального представления профиля обращений. Такой анализ зачастую полезен, поскольку позволяет пользователю увидеть и оценить общую структуру работы с памятью; при этом с его помощью можно простыми методами, хотя и достаточно грубо, определить свойства пространственной и временной локальности в программе. Для второго метода были разработаны две количественные оценки работы с памятью. Первая оценка cvg вычисляет локальность на основе данных из профиля обращений. Для этого фиксируется «окно» профиля (N идущих подряд обращений в профиле), для которого вычисляется разброс виртуальных адресов обращений. Затем этот разброс вычисляется для всех «окон» профиля, и полученное среднее является оценкой cvg. Отметим, что cvg является машинно-независимой оценкой, поскольку вычисляется на основе профиля обращений, который практически не изменяется при переходе между стандартными аппаратными платформами или при выборе различных настроек выполнения программ. Также была разработана и апробирована оценка daps, которая вычисляет производительность работы с памятью на основе аппаратных счетчиков. Данная оценка является аналогом оценки flops и равна числу выполненных обращений в память в секунду. Такая оценка оценивает работу с памятью в случае конкретной выбранной аппаратной платформы и также предназначена для сравнительного анализа свойств локальности в различных программах. Отметим, что оценки cvg и daps характеризуют работу с памятью с разных точек зрения и на разных уровнях абстракции: daps предназначена для описания производительности работы с памятью на конкретной целевой платформе, в то время как cvg применяется для общей оценки локальности. Также на данном этапе была описана методика описания локальности данных в программе, которая основана на указанных методах исследования с помощью визуального анализа и количественных оценок. Данная методика позволяет в едином стиле описывать свойства работы с памятью независимо от особенностей выбранного алгоритма и его реализации. На текущем этапе выполнения проекта была разработана метрика масштабируемости и показана ее применимость для ряда параллельных программ, реализующих задачи из различных областей физических и химических задач, задач линейной алгебры и графовых алгоритмов. Показана возможность сравнения масштабируемости для любых параллельных приложений, основываясь на анализе изменения эффективности реализации приложения, как отношения полученной реальной производительности к пиковой для использованного аппаратного обеспечения. Разработана формула для выведения оценки масштабируемости для проведения анализа масштабируемости программ с произвольным числом параметров запуска. Проведены исследования для ряда приложений с различными параметрами запуска и показана возможность сравнения масштабируемости таких приложений при наличии общих параметров запуска. Разработана методика проведения исследования масштабируемости. Показана применимость разработанной методики на ряде параллельных реализаций алгоритмов из различных областей физики, математики и химии. Показана возможность определения при помощи собранных данных имеющихся проблем с масштабируемостью. Разработана технология описания свойств и особенностей алгоритмов, влияющих на эффективность выполнения результирующих программ на различных программно-аппаратных платформах. Сайт Открытой энциклопедии свойств алгоритмов AlgoWiki находится в сети Интернет по адресу http://algowiki-project.org. В качестве основы реализации был выбран программный механизм MediaWiki, реализующий систему управления контентом в стиле так называемой «вики»-технологии. Вики-технология предоставляет возможность создать сайт в сети Интернет, структуру и содержимое которого могут самостоятельно изменять пользователи с помощью предоставленных инструментов. Для форматирования текста и вставки различных объектов предлагается специальная разметка. На базе этой технологии построены Википедия и многие другие сайты. На данном этапе выполнения проекта получены описания свойств 10 реальных алгоритмов согласно текущему варианту технологии описания. Полученные описания алгоритмов продемонстрировали огромный потенциал данной технологии. В реализованных описаниях максимально полно отражены все свойства, необходимые для эффективной реализации алгоритма на параллельных вычислительных системах. Полученные на данном этапе выполнения проекта описания алгоритмов были включены в текущий вариант энциклопедии. В настоящее время пользователь по ссылке http://algowiki-project.org попадает на русскоязычную страницу Открытой энциклопедии свойств алгоритмов AlgoWiki. В дальнейшем предполагается одновременное наполнение как русскоязычной, так и англоязычной версий энциклопедии. Пилотная версии энциклопедии прошла апробацию, к её использованию подключены ряд внешних пользователей, внесены корректировки в требования к Открытой энциклопедии свойств алгоритмов AlgoWiki и архитектуру, выполнен выпуск в ограниченное использование пилотной версии энциклопедии с полной функциональностью. Создаваемая Открытая энциклопедия свойств алгоритмов AlgoWiki не имеет прямых аналогов в мировой практике. Проблема тут не в том, чтобы сделать и опубликовать энциклопедию, работающую на принципах вики-технологий. Проблема в том, что нет не только адекватного контента, но даже понимания, как подобный контент можно было бы формировать. Первая версия Открытой энциклопедии свойств алгоритмов AlgoWiki не является окончательной и будет модифицироваться и совершенствоваться. Однако на ней отрабатываются те принципы, которые хочется заложить в окончательный вариант энциклопедии, наполняемой мировым вычислительным сообществом. Адрес проекта: http://algowiki-project.org | ||
3 | 1 января 2016 г.-31 декабря 2016 г. | Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем |
Результаты этапа: На третьем этапе выполнения проекта No 14-11-00190 «Открытая энциклопедия свойств алгоритмов: от мобильных платформ до экзафлопсных суперкомпьютерных систем» в 2016 году были произведены работы в точном соответствии с намеченным планом работ. Работы, выполненные на данном этапе, позволили успешно завершить выполнение проекта, достигнув всех намеченных при старте проекта целей. На данном этапе произведена окончательная формализации процесса отображения алгоритмов на архитектуру параллельных вычислительных систем и разработки технологии описания свойств и особенностей алгоритмов. Окончательно сформировалась структура описания алгоритма, которая состоит из трёх основных разделов. Первый раздел посвящён описанию машинно-независимых свойств алгоритмов, второй - описанию машинно-зависимых свойств последовательных и параллельных реализаций. Явно выделен третий раздел для списка литературы по описываемому алгоритму, которую авторы использовали при подготовке конкретного описания, причем здесь же приводятся ссылки на первоисточники и классические работы в этой области. В начале описания алгоритма помещается карточка алгоритма, в которую выносятся основные свойства, характеризующие данный алгоритм. В разделе «Классификация алгоритмов» все описываемые алгоритмы раскладываются по тематическим разделам. Эта классификация со временем видоизменяется и пополняется по мере подключения к проекту специалистов, описывающих алгоритмы из других научных областей. Раздел «Глоссарий» содержит описание основных терминов, связанных с описанием свойств алгоритма для правильного понимания терминов, которое зачастую являются не вполне однозначным. Раздел «Руководства» содержит инструкции по заполнению отдельных разделов описания алгоритма. Раздел «Справка» содержит материалы, необходимые для обеспечения работы с проектом внешних пользователей. Практика описания алгоритмов из самых разных предметных областей в рамках Открытой энциклопедии свойств алгоритмов AlgoWiki показала применимость и универсальность разработанного подхода. Несмотря на ориентацию данного проекта в сторону мощных суперкомпьютерных систем, исследование и детальное описание свойств алгоритмов актуально для всех компьютерных платформ, вплоть до мобильных телефонов и планшетов, которые сейчас также стали параллельными. На данном этапе выполнения проекта был произведён критический анализ всех основных элементов созданных технологий. Показано, что предложенная структура описания позволяет представить подробное математическое описание алгоритма, описать его информационную структуру и свойства (в первую очередь связанные с использованием ресурса параллелизма), разобрать особенности его реализации на различных архитектурах, исследовать его динамические свойства, включая локальность, масштабируемость, эффективность и многие другие, а также привести конкретные результаты расчетов для различных программно-аппаратных платформ. На основании проведённого анализа сделаны предложения по возможным направлениям дальнейшего развития проекта. В течение отчётного года была выполнена корректировка разработанных технологий с учетом накопленного опыта, текущих требований и реакции пользователей. Были разработаны новые технологии визуализации информационных графов и их представления в проекте. В конечном варианте версия MediaWiki была обновлена до 1.26.4, что потребовало переустановки ряда модулей системы. Была выполнена синхронизация wiki-шаблонов, используемых в русскоязычной и англоязычной версиях AlgoWiki. На данном этапе выполнения проекта получены описания свойств 10 реальных алгоритмов согласно текущему варианту технологии описания. К описанию алгоритмов в рамках Открытой энциклопедии свойств алгоритмов AlgoWiki подключаются внешние пользователи, не входящие в число членов авторского коллектива данного проекта. Всего на 1 декабря 2016 года в проекте зарегистрировано более 300 участников, силами которых уже описано более 200 алгоритмов из самых разных научных областей. Полученные описания алгоритмов продемонстрировали огромный потенциал данной технологии. Взятые в качестве образца алгоритмы представляют самые разные области науки: алгоритмы линейной алгебры, алгоритмы работы с большими графами, алгоритмы моделирования квантовых систем. В реализованных описаниях максимально полно отражены все свойства, необходимые для эффективной реализации алгоритма на параллельных вычислительных системах. Полученные на данном этапе выполнения проекта описания алгоритмов включены в текущий вариант энциклопедии. Запущен полнофункциональный вариант открытой энциклопедии в сети Интернет по свойствам алгоритмов и особенностям их реализации на различных программно-аппаратных платформах с возможностью коллективной работы над энциклопедией мирового вычислительного сообщества. В текущей версии Открытой энциклопедии свойств алгоритмов AlgoWiki реализована вся функциональность, запланированная к реализации при старте данного проекта. Использованная технология MediaWiki поддерживает одновременную работу множества пользователей. Меняя какую-то информацию в Алговики, пользователи создают свою собственную копию этого документа и работают уже с ней. Впоследствии, новая информация может быть автоматически или вручную добавлена в основную версию энциклопедии. Вся история и авторство изменений сохраняется, что позволяет легко исправить любой вандализм или неумышленные ошибки. В MediaWiki присутствует возможность поддерживать работу на нескольких языках, что используется нами для развития одновременно русскоязычной и англоязычной версии библиотеки алгоритмов. Что важно, использованная технология позволяет использовать общие ресурсы без необходимости их дублирования. На данный момент в проект включены описания алгоритмов на русском (https://algowiki-project.org/ru/) и английском (https://algowiki-project.org/en) языках, и при необходимости возможно лёгкое добавление других языков на базе уже реализованных средств. Для оптимизации доступа пользователей к Открытой энциклопедии свойств алгоритмов AlgoWiki, её веб-сайт был добавлен в систему аналитики поисковой системы Google. Указание корректной информации о веб-сайте в этой системе позволяет повысить релевантность поиска информации, расположенной на сайте, а также позволяет нам оценивать аудиторию и посещаемость AlgoWiki. По данным системы статистики Google Analytics на конец 2016 года среднее число заходов на страницы проекта в день превышает 200. Представленные в AlgoWiki статьи с описанием свойств алгоритмов по научной составляющей приближаются к статьям из научных журналов. Это подтверждается многочисленными публикациями с результатами проведенных исследований в материалах российских и зарубежных конференций, а также в статьях, опубликованных в реферируемых журналах. В статьях AlgoWiki сохраняется авторство для всех людей, внёсших существенный вклад в их написание. В целом, проект оказался исключительно удачным, затронув крайне важную для всего вычислительного сообщества тему. Его результаты заложили прочную основу как для формирования единого подхода для описания базовых и тонких свойств алгоритмов, так и для выполнения исследований и разработок по целому множеству новых направлений в будущем. Адрес Открытой энциклопедии свойств алгоритмов AlgoWiki в сети Интернет: http://algowiki- project.org |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".