Preview

Труды Института системного программирования РАН

Расширенный поиск
Том 30, № 2 (2018)
Скачать выпуск PDF
7-24 128
Аннотация
В научной литературе широко представлено исследование возможностей интерпретируемого выполнения компьютерных программ. При этом противоположный подход, основанный на элиминации любых проявлений интерпретируемости, насколько можно судить, никем всерьез не исследовался. В настоящей статье рассматривается подход, предполагающий отделение всего происходящего во время исполнения программы от инструментов, использующихся программистом при ее написании, и намечается путь к построению универсального (равно пригодного как для системных, так и для прикладных задач) языка программирования.
25-44 100
Аннотация
Работа посвящена теме распараллеливания программ в особо сложных случаях - когда используемый алгоритм является сугубо последовательным, параллельных альтернатив используемому алгоритму нет, а время его выполнения неприемлемо велико. Рассматриваются различные методы распараллеливания программных реализаций таких алгоритмов и балансировки получающейся вычислительной нагрузки, позволяющие получить значительное ускорение выполнения прикладных программ, в которых используются сугубо последовательные алгоритмы. Приведенные методы иллюстрируются практикой их применения к двум алгоритмам, используемым в среде динамического анализа программ. Основная цель данной работы - показать, что использование в программной реализации сугубо последовательного алгоритма не означает неизбежность его последовательного выполнения. Предложенные методы распараллеливания реализаций таких алгоритмов и балансировки получающейся вычислительной нагрузки могут способствовать созданию эффективной параллельной программы, полностью использующей предоставленные ей аппаратные возможности современных вычислительных систем.
45-64 85
Аннотация
Реляционное программирование является подходом, позволяющим исполнять программы в различных "направлениях" для получения различных сценариев поведения по одной реляционной спецификации. В данной статье рассмотрена задача автоматического преобразования функциональных программ в реляционные. Представлен метод преобразования типизированных функций в реляционную форму, а также доказательство его статической и динамической корректности. Также в статье обсуждаются ограничения предложенного метода, представлена реализация метода для подмножества языка OCaml и проведена оценка эффективности метода на ряде реалистичных примеров.
65-80 65
Аннотация
В работе предложен метод автоматизированной генерации декодеров машинных команд широкого класса процессорных архитектур с использованием транслятора языка ассемблера целевой архитектуры. Реализована программная система, использующая предложенный метод для генерации декодеров машинных команд различных архитектур. Система была протестирована на нескольких микроконтроллерах: PIC16F877A, AVR, Tricore, H8/300H.
81-98 106
Аннотация
Визуализация больших трехмерных сцен занимает существенное время. Для сокращения количества обрабатываемых объектов используются методы удаления невидимых поверхностей. В статье рассматривается семейство интерактивных методов удаления невидимых поверхностей, обладающих пространственной и временной когерентностью. Наиболее распространенным является метод с использованием аппаратных запросов видимости. Однако посылка и получение результатов запросов видимости занимают значительное время при большом количестве объектов. Предлагается алгоритм удаления невидимых поверхностей на основе программных проверок видимости относительно составленного на графическом процессоре буфера глубины. Предлагается эвристика для определения высоты иерархии, соответствующей наибольшей эффективности проверок видимости. Предложенный алгоритм позволяет сократить количество команд визуализации, что улучшает производительность визуализации трехмерных сцен с большим количеством объектов по сравнению с алгоритмом, основанным на аппаратных запросах видимости.
99-112 76
Аннотация
Рассматривается задача синтеза самопроверяемой схемы встроенного контроля с оптимизацией структурной избыточности на основе использования метода логического дополнения до равновновесного кода «2 из 4». Разработан способ доопределения значений контрольных функций, позволяющий пошагово устанавливать их вид и при этом обеспечивать решение задачи тестирования соответствующих элементов сложения по модулю два и схемы тестера. При этом в значения функций вводятся неопределенности, что позволяет минимизировать сами функции, и соответственно, упрощать схему блока контрольной логики.
113-148 135
Аннотация
Данная статья представляет собой обзор расширяемого протокола аутентификации (Extensible Authentication Protocol, EAP), специфицированного комитетом Internet Engineering Task Force, IETF, и предоставляющего эффективный механизм встраивания в него различных методов аутентификации, а также обзор собственно методов аутентификации EAP, часть из которых была стандартизована в спецификациях IETF. Показано разнообразие механизмов, используемых для реализации сервиса аутентификации. Работа выполнялась при поддержке РФФИ, проект № 16-07-00603 «Верификация функций безопасности и оценка устойчивости к атакам реализаций протокола аутентификации EAP».
149-166 95
Аннотация
Графы используются в качестве структуры данных для представления больших объемов информации в компактной и удобной для анализа форме в различных областях - биоинформатике, графовых базах данных, статическом анализе кода и др. При этом оказывается необходимо вычислять запросы к большим графам с целью выявления зависимостей между их вершинами. Ответом на такие запросы обычно является множество всех троек (A, m , n ), для которых существует путь в графе от вершины m до вершины n такой, что метки на ребрах этого пути образуют строку, выводимою из нетерминала A в некоторой контекстно-свободной грамматике. Говорят, что такой тип запросов вычисляется с использованием реляционной семантики запросов. Кроме того, существуют конъюнктивные грамматики, образующие более широкий класс грамматик, чем традиционные контекстно-свободные грамматики. Использование конъюнктивных грамматик в задаче синтаксического анализа графов позволяет формулировать более сложные запросы к графу и решать более широкий круг задач. Известно, что задача вычисления запросов к графу с использованием реляционной семантики и конъюнктивных грамматик является неразрешимой. В данной работе предлагается алгоритм, вычисляющий приближенное решение этой задачи, а именно, аппроксимацию сверху. Предложенный алгоритм основан на матричных операциях, и проведенные эксперименты показывают, что его производительность может быть существенно повышена, благодаря использованию вычислений на графическом процессоре.
167-194 58
Аннотация
Для распределенной системы, в основе которой лежит ориентированный граф без кратных ребер и петель, рассматривается проблема отката (backtracing problem): как передать сообщение от конца дуги в ее начало. Ставится задача создания на графе структуры, позволяющей передавать сообщение из конца любой дуги в ее начало по кратчайшему пути. Такая структура в каждой вершине a задаётся отображением номера вершины b в номер исходящей дуги, через которую проходит кратчайших путь от a к b . В частности, такое отображение позволяет симулировать в ориентированных распределенных системах алгоритмы решения задач на графе, разработанные для неориентированных распределенных систем. Это увеличивает время работы таких алгоритмов (в тактах, где время пересылки сообщения по дуге не превосходит 1 такт) не более чем в k раз, где k диаметр графа, k < n , и n - число вершин графа. В разделе 2 описывается используемая асинхронная модель распределенной системы. Раздел 3 содержит основные определения и обозначения, а раздел 4 - постановку задачи. В разделе 5 описываются два вспомогательных алгоритма коррекции поддеревьев, применение которых позволяет строить остовные деревья кратчайших путей: прямого дерева, ориентированного от корня графа, и обратного дерева, ориентированного к корню графа. Раздел 6 содержит описание различных способов передачи сообщений по графу. В разделе 7 предлагаются два алгоритма построения в памяти автомата корня графа описаний прямого и обратного остовных деревьев кратчайших путей, а в разделе 8 - основанные на них алгоритмы построения требуемого отображения: «быстрый» алгоритм с оценками T = O ( n ) и N = O ( n ) и «экономный» алгоритм с оценками T = O ( n2) и N = O (1), где T - время (в тактах) работы алгоритма, N - число сообщений, одновременно передаваемых по дуге. В разделе 9 доказано, что эти оценки времени не улучшаемые. В разделе 10 «быстрый» алгоритм модифицируется для синхронной модели с N =1. Заключение подводит итоги и намечает направления дальнейших исследований.
195-214 85
Аннотация
В статье представлена онтология предметной области «Удобство использования программного обеспечения». Описываются преимущества, которые может дать ее использование при анализе и оценке удобства использования программных продуктов. Представлены диаграмма классов предлагаемой онтологии и текстовое описание входящих в ее состав классов, объектных свойств и свойств данных. Приводятся примеры вопросов, на которые может отвечать онтология. Предлагается классификация возможных методик анализа и оценки удобства использования на основе представленной онтологии и описываются некоторые из них.
215-250 77
Аннотация
Качественные аннотированные коллекции являются ключевым элементом при построении систем, использующих машинное обучение. В большинстве случаев создание таких коллекций предполагает привлечение к разметке данных людей, а сам процесс является дорогостоящим и утомительным для аннотаторов. Для оптимизации этого процесса был предложен ряд методов, использующих активное обучение и краудсорсинг. В статье приводится обзор существующих подходов, обсуждается их комбинированное применения, а также описываются существующие программные системы, предназначенные для упрощения процесса разметки данных.
251-262 90
Аннотация
В работе рассматривается бесконтактный метод анализа сердечной активности человека, основанный на регистрации и обработке баллистокардиографичекого сигнала. В измерительной установке для фиксации микроскопических движений тела используется пьезоэлектрический датчик высокой чувствительности. Появляющийся вследствие высокой чувствительности шум, существенно превышающий полезный сигнал, в дальнейшем фильтруется математическими методами. Для выделения кардио компоненты используется полосный фильтр Баттерворта. Этот подход к фильтрации полезного сигнала является более экономичным с точки зрения необходимых вычислительных ресурсов, чем сравнимые по точности методы, основанные на машинном обучении, и может быть реализован на граничном (промежуточном) вычислительном узле, к которому подключены несколько датчиков. Качество полученной после фильтрации кардио компоненты позволяет с высокой точностью выделить на ней циклы сердечной активности (сердцебиения). Предлагаемый в работе алгоритм выделения сердцебиений также обладает достаточно низкой вычислительной стоимостью, чтобы быть использованным на граничном вычислительном узле. После фильтрации данные передаются выше - в центр обработки данных (облако)
263-284 81
Аннотация
Получены необходимые соотношения для реализации алгоритма моделирования осесимметричных течений вязкой несжимаемой жидкости в методе конечных элементов с частицами PFEM-2. Осесимметричная модель реализована в программном комплексе c открытым исходным кодом Kratos на основе существующего модуля для решения плоских задач. Была проведена валидация осесимметричной модели на тестовых задачах. В качестве модельных рассмотрены задачи о течении в трубе (задача Пуазейля) и задача о моделировании падения капли в глубокий слой жидкости. Численное решение, полученное методом конечных элементов с частицами, для задачи Пуазейля показало удовлетворительное согласие с аналитическим; решение задачи о падении капли в слой глубокий жидкости в комплексе Kratos сравнивалось с результатом моделирования в программном пакете Gerris с открытым исходным кодом. Результаты расчетов также удовлетворительно согласуются.
285-300 136
Аннотация
Работа посвящена поиску приближенного решения системы уравнений газовой динамики методом RKDG (Runge - Kutta Discontinuous Galerkin), который характеризуется высоким порядком точности по сравнению с классическим методом конечных объёмов (МКО). Вычислительный алгоритм реализован на языке C++ и верифицирован на тестовых задачах. Результаты моделирования акустического импульса на достаточно грубой сетке с кусочно-линейной аппроксимацией хорошо согласуются с аналитическим решением, в отличие от численного приближения с помощью МКО. Для задачи Сода приводится сравнение зависимости схемы от выбора численных потоков, индикатора проблемных ячеек и лимитера.
301-316 73
Аннотация
Главной целью современного гемодинамического моделирования является предсказание поведения давления крови в артериях, а также изучение комплексного воздействия разнообразных факторов на характеристики сердечно-сосудистой системы. Наиболее популярными при этом являются квазиодномерные модели течения крови по сосудам, позволяющие моделировать кровоток во всей сосудистой системе. Поскольку полномасштабное моделирование сердечно-сосудистой системы требует больших вычислительных затрат, актуальной является задача распараллеливания вычислений. В данной работе проведено исследование эффективности распараллеливания вычислений при численном моделировании кровотока в квазиодномерном приближении. Для простоты рассмотрена задача о моделировании течения крови в отдельном кровеносном сосуде. При построении параллельного алгоритма был применен метод декомпозиции области. В каждой подобласти задача на каждом шаге по времени расщепляется на гиперболическую и параболическую подзадачи. Для решения гиперболической подзадачи используется интегро-интерполяционный метод, основанный на схеме MUSCL. Для интегрирования по времени применяются методы Рунге-Кутты и Адамса-Башфорта второго порядка. Для решения параболической подзадачи используется метод Кранка-Николсона. На стыках подобластей интерфейсные условия образуют нелинейные системы с тремя неизвестными. Эти системы решаются при помощи метода Ньютона. С помощью профилировщика AMD CodeAnalyst была определена структура временных затрат при решении тестовой задачи в последовательном режиме. При помощи закона Амдала получены оценки максимально возможного ускорения при распараллеливании наиболее дорогостоящих с вычислительной точки зрения операций. При реализации полученного алгоритма в разработанном авторами настоящей работы программном комплексе использовались технология OpenMP и библиотека MPI. Расчеты проводились на учебно-вычислительном кластере кафедры ФН-2 «Прикладная математика» МГТУ им. Н.Э. Баумана. Результаты вычислительных экспериментов показали, что выигрыш по времени, достигаемый за счет использования библиотеки MPI, не превышает нескольких процентов по сравнению с применением технологии OpenMP. В связи с этим, принимая во внимания простоту распараллеливания алгоритмов посредством OpenMP, можно остановить выбор на данной технологии, однако использование MPI позволяет сделать программный комплекс универсальным -работающим как на системах с общей памятью, так и на системах с распределенной памятью.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)