Статьи журнала - Труды Института системного программирования РАН
Все статьи: 115
Обзор современных методов планирования движения
Статья научная
Автоматизация технологически сложных процессов в машиностроении, энергетике, транспорте, медицине, строительстве, а также создание новых продуктов и сервисов невозможны без решения задач планирования движения. В последнее время интерес к ним заметно возрос в связи с развитием средств компьютерного моделирования и становлением таких дисциплин как комплексное планирование индустриальных программ, реалистичная анимация трехмерных сцен, роботизированная хирургия, навигация в динамическом окружении, автоматическая сборка продуктов, организация транспортных потоков в мегаполисах. Данная работа посвящена обзору и сравнительному анализу современных математических методов планирования движения.
Бесплатно
Обнаружение ошибок, возникающих при использовании динамической памяти после её освобождения
Статья научная
Существенная часть программного обеспечения написана на языках программирования C/C++. Программы на этих языках часто содержат ошибки: использования памяти после освобождения (Use After Free, UAF), переполнения буфера (Buffer Overflow) и др. В статье предложен метод обнаружения ошибок UAF, основанный на динамическом анализе. Для каждого пути выполнения программы предлагаемый метод проверяет корректность операций создания и доступа, а также освобождения динамической памяти. Поскольку применяется динамический анализ, поиск ошибок производится только в той части кода, которая была непосредственно выполнена. Используется символьное исполнение программы с применением решателей SMT (Satisfiability Modulo Theories) [12]. Это позволяет сгенерировать данные, обработка которых приводит к обнаружению нового пути выполнения.
Бесплатно
Объектно-ориентированная среда для разработки приложений планирования движения
Статья научная
Обсуждаются принципы организации и функционирования инструментальной среды для программной реализации моделей, методов и приложений теории планирования движения. Среда предоставляет развитый набор готовых к использованию программных компонентов для автоматического построения бесконфликтных траекторий для робота, перемещаемого в статическом и динамическом трехмерном окружении. Организация среды в виде объектно-ориентированного каркаса обеспечивает развитие, адаптацию и гибкое конфигурирование разработанных программных компонентов в составе целевых приложений. Благодаря выделенным интерфейсам разного уровня и предусмотренным точкам расширения среда допускает интеграцию со сторонними прикладными системами.
Бесплатно
Объектно-ориентированный каркас для программной реализации приложений теории расписаний
Статья научная
Статья адресована вопросам программной реализации моделей, методов и приложений теории расписаний с использованием объектно-ориентированного каркаса. Каркас представляет собой систему классов вместе с предусмотренными механизмами взаимодействия и расширения, что обеспечивает эволюционную разработку серий приложений на единой методологической, программной и инструментальной основе. В статье детально обсуждаются принципы организации и функционирования разработанного каркаса, а также его возможности для разработки приложений теории расписаний и, в частности, перспективных систем календарно-сетевого планирования и управления проектами.
Бесплатно
Онтология предметной области "Удобство использования программного обеспечения"
Статья научная
В статье представлена онтология предметной области «Удобство использования программного обеспечения». Описываются преимущества, которые может дать ее использование при анализе и оценке удобства использования программных продуктов. Представлены диаграмма классов предлагаемой онтологии и текстовое описание входящих в ее состав классов, объектных свойств и свойств данных. Приводятся примеры вопросов, на которые может отвечать онтология. Предлагается классификация возможных методик анализа и оценки удобства использования на основе представленной онтологии и описываются некоторые из них.
Бесплатно
Оптимизация динамической загрузки библиотек на архитектуре ARM
Статья научная
В статье рассматривается подход к оптимизации вызовов внешних функций в позиционно-независимом коде, основанный на выдаче вызовов непосредственно через глобальную таблицу смещений (GOT), минуя таблицу компоновки процедур (PLT). Стандартные механизмы кодогенерации на операционной системе Linux предполагают создание PLT не только для основного модуля (который является позиционно-зависимым и полагается на механизм PLT для вызовов внешних процедур), но и для динамических библиотек, где PLT используется также для организации ленивого связывания; однако использование PLT требует дополнительной инструкции перехода, может иметь низкую локальность по кешу и на некоторых архитектурах накладывает дополнительные ограничения на работу компилятора в месте вызова. Реализация вызовов внешних функций в виде косвенных переходов на адреса, загруженные непосредственно из GOT в месте вызова, позволяет избежать недостатков вызовов через PLT ценой отказа от возможности ленивого связывания и, возможно, увеличения размера кода. Была исследована реализация этой оптимизации для архитектур x86 и ARM в компиляторе GCC. Было обнаружено, что на архитектуре ARM отсутствуют типы релокаций, которые позволили бы генерировать оптимальный код для загрузок из GOT. Для решения этой проблемы в GCC и Binutils (в ассемблере и компоновщике) были реализованы недостающие типы релокаций, позволяющие построить адрес позиции в GOT относительно счетчика команд, используя инструкции movt, movw. Проведенное тестирование свидетельствует, что предложенная оптимизация позволяет получить увеличение производительности, несмотря на увеличение размеров динамических библиотек.
Бесплатно
Статья научная
Рассматривается задача синтеза самопроверяемой схемы встроенного контроля с оптимизацией структурной избыточности на основе использования метода логического дополнения до равновновесного кода «2 из 4». Разработан способ доопределения значений контрольных функций, позволяющий пошагово устанавливать их вид и при этом обеспечивать решение задачи тестирования соответствующих элементов сложения по модулю два и схемы тестера. При этом в значения функций вводятся неопределенности, что позволяет минимизировать сами функции, и соответственно, упрощать схему блока контрольной логики.
Бесплатно
Статья научная
Описывается методика, позволяющая реализовать поиск дефектов достаточно общего и произвольного вида при использовании межпроцедурного анализа методом резюме при анализе исходного кода программы на высокоуровневых языках программирования, таких как C и C++. Основное внимание уделено трудностям, возникающим при построении и применении резюме в процессе анализа исходного кода (по сравнению с анализом низкоуровневого представления программы), а также достижению гибкости метода анализа, необходимой для поиска дефектов произвольного вида.
Бесплатно
Перекрытие коммуникаций и вычислений в итерационных методах решения систем линейных уравнений на GPU
Статья научная
Методы подпространства Крылова, такие как метод сопряжённых градиентов и стабилизированный метод бисопряжённых градиентов, давно используются для решения симметричных и несимметричных систем линейных алгебраических уравнений. Это находит широкое применение при численном решении дифференциальных уравнений, которые возникают, например, в задачах вычислительной физики. Однако при увеличении размеров расчетной сетки и, соответственно, количества вычислительных процессов значительную часть времени работы могут занимать коммуникации, во время которых расчёты простаивают. Это происходит из-за того, что в оригинальных формулировках методов результат скалярного произведения, которое требует редукции, требуется уже на следующем шаге метода, что приводит к барьерной синхронизации всех потоков. При значительном количестве итераций это может привести к деградации производительности. В статье рассматривается использование альтернативных формулировок методов подпространства Крылова, позволяющих перекрыть часть вычислений и параллельных коммуникаций, часто за счет увеличения объема вычислений. Нами предложены собственные реализации этих подходов для использования гибридного решателя с графическими ускорителями, использующими технологию CUDA, в рамках программного пакета OpenFOAM, а также описаны особенности их переноса на акселераторы. Для дальнейшей оптимизации используются асинхронные коллективные операции, предоставленные стандартом межпроцессного взаимодействия MPI-3, которые позволяют избавиться от барьерной синхронизации и снизить латентность операций обмена. Представлены результаты тестирования нашего подхода на одной из станадартных задач пакета OpenFOAM с расчётными сетками в 2 и 4 миллиона ячеек c использованием нескольких графических ускорителей.
Бесплатно
Поддержка стандарта OpenMP4.0 для архитектуры NVIDIA PTX в компиляторе GCC
Статья научная
В статье описывается реализация стандарта OpenMP версии 4.0 для акселераторов NVIDIA PTX в компиляторе GCC. Особое внимание уделяется вопросам генерации корректного и эффективного кода для прагм OpenMP с учетом ограничений архитектуры PTX. Поскольку реализация опирается на существующую в GCC трансляцию OpenMP и интеграцию с библиотекой libgomp, для PTX реализованы вторичные программные стеки, позволяющие организовать общий для синхронной группы стек в глобальной памяти и передавать адреса на данные в таких стеках между нитями. Описывается схема организации выполнения одной OpenMP-нити в 32 синхронных потоках выполнения в PTX вне OpenMP SIMD-регионов за счет легковесной инструментации некоторых инструкций. Представлены результаты тестирования на микротестах и сравнение с реализацией стандарта OpenACC.
Бесплатно
Статья научная
Среди методов анализа программ на наличие дефектов выделяют методы статического и динамического анализа. В данной статье мы предлагаем комбинированный подход, заключающийся в применении динамического символьного исполнения для определения достижимости дефектов, найденных при помощи статического анализа. Предлагаемый подход является развитием ранее предложенного подхода определения достижимости определенной инструкции в программе методами динамического символьного исполнения, примененном последовательно для нескольких точек в программе, включающих точки инициализации дефекта, условные переходы в трассе дефекта и точку реализации дефекта. С начала производится статический анализ исполняемого кода программы с целью выделения путей исполнения, которые приводят к точке инициализации дефекта. Далее производится вычисление входных данных, приводящих к точке инициализации дефекта методом динамического символьного исполнения и прохождения базовых блоков, лежащих на трассе дефекта, включая точку реализации дефекта. Выбор наиболее перспективного пути для исполнения программы производится при помощи метрики минимального расстояния от пути исполнения на предыдущей итерации до следующей точки на трассе дефекта. Метрика вычисляется на основе путей в графе вызовов в программе, расширенного графом потока управления функций на путях исполнения, приводящих к реализации дефектов. Предлагаемый подход был проверен на нескольких программах с открытым исходным кодом из комплекта утилит командной строки операционной системы Debian Linux. В результате экспериментальной проверки было подтверждена возможность применения данного подхода к классификации дефектов, найденных при помощи статического анализа программ. Также, были обнаружены некоторые ограничения, препятствующие внедрению данного подхода в промышленные инструменты анализа. Одним из направлений дальнейших исследований может быть выбрано исследование подходов к снятию этих ограничений.
Бесплатно
Поиск ошибок доступа к буферу в программах на языке C/ C++
Статья научная
В статье рассматривается алгоритм статического анализа для поиска в исходном коде программы ошибок доступа к буферу. Алгоритм использует символьное исполнение с объединением состояний и является чувствительным к путям. Рассматриваются только обращения к буферам, имеющим известный в момент компиляции размер и размещённым в статической памяти либо на стеке. В работе приведено формальное определение ошибки доступа к буферу, возникающей при прохождении некоторой последовательности рёбер графа потока управления программы. Приведён алгоритм, позволяющий для переменных программы суммировать информацию о возможных значениях по всем путям с учётом совместности условий переходов, взаимосвязи переменных через арифметические операции, инструкции преобразования типов, бинарные отношения в условиях переходов. Для инструкций доступа к буферу с помощью вычисленной для переменной индекса информации о возможных значениях вычисляются достаточные условия выхода за границы. Выполнимость достаточных условий проверяется SMT-решателем и, в случае нахождения модели, с её помощью обнаруживается ошибочный путь и выдаётся предупреждение. На основе данного подхода в инструменте статического анализа Svace был реализован межпроцедурный чувствительный к путям детектор ошибок доступа к буферу, способный обнаруживать новые, не покрытые предыдущими реализациями детекторов типы ошибок.
Бесплатно
Преобразование типизированных функций в реляционную форму
Статья научная
Реляционное программирование является подходом, позволяющим исполнять программы в различных "направлениях" для получения различных сценариев поведения по одной реляционной спецификации. В данной статье рассмотрена задача автоматического преобразования функциональных программ в реляционные. Представлен метод преобразования типизированных функций в реляционную форму, а также доказательство его статической и динамической корректности. Также в статье обсуждаются ограничения предложенного метода, представлена реализация метода для подмножества языка OCaml и проведена оценка эффективности метода на ряде реалистичных примеров.
Бесплатно
Статья научная
Главной целью современного гемодинамического моделирования является предсказание поведения давления крови в артериях, а также изучение комплексного воздействия разнообразных факторов на характеристики сердечно-сосудистой системы. Наиболее популярными при этом являются квазиодномерные модели течения крови по сосудам, позволяющие моделировать кровоток во всей сосудистой системе. Поскольку полномасштабное моделирование сердечно-сосудистой системы требует больших вычислительных затрат, актуальной является задача распараллеливания вычислений. В данной работе проведено исследование эффективности распараллеливания вычислений при численном моделировании кровотока в квазиодномерном приближении. Для простоты рассмотрена задача о моделировании течения крови в отдельном кровеносном сосуде. При построении параллельного алгоритма был применен метод декомпозиции области. В каждой подобласти задача на каждом шаге по времени расщепляется на гиперболическую и параболическую подзадачи. Для решения гиперболической подзадачи используется интегро-интерполяционный метод, основанный на схеме MUSCL. Для интегрирования по времени применяются методы Рунге-Кутты и Адамса-Башфорта второго порядка. Для решения параболической подзадачи используется метод Кранка-Николсона. На стыках подобластей интерфейсные условия образуют нелинейные системы с тремя неизвестными. Эти системы решаются при помощи метода Ньютона. С помощью профилировщика AMD CodeAnalyst была определена структура временных затрат при решении тестовой задачи в последовательном режиме. При помощи закона Амдала получены оценки максимально возможного ускорения при распараллеливании наиболее дорогостоящих с вычислительной точки зрения операций. При реализации полученного алгоритма в разработанном авторами настоящей работы программном комплексе использовались технология OpenMP и библиотека MPI. Расчеты проводились на учебно-вычислительном кластере кафедры ФН-2 «Прикладная математика» МГТУ им. Н.Э. Баумана. Результаты вычислительных экспериментов показали, что выигрыш по времени, достигаемый за счет использования библиотеки MPI, не превышает нескольких процентов по сравнению с применением технологии OpenMP. В связи с этим, принимая во внимания простоту распараллеливания алгоритмов посредством OpenMP, можно остановить выбор на данной технологии, однако использование MPI позволяет сделать программный комплекс универсальным -работающим как на системах с общей памятью, так и на системах с распределенной памятью.
Бесплатно
Статья научная
Проведено прямое численное моделирование распространения внутренних волн и образования волновых аттракторов в трапецеидальном контейнере, заполненном устойчиво стратифицированным раствором соли с постоянной частотой плавучести. Левая вертикальная стенка контейнера совершает монохроматические колебания в форме половины косинусоиды на высоту контейнера, правая стенка расположена под углом к вертикали и обеспечивает фокусировку внутренних волн, две другие границы горизонтальны. На верхней границе задано условие отсутствия касательных напряжений, на остальных условие прилипания. Рассчитываются уравнения Навье-Стокса в приближении Буссинеска в трёхмерной и двумерной постановке. Прямое численное моделирование проведено с помощью метода спектральных элементов 8-го порядка и модифицированного кода nek5000. С помощью применения преобразований Гильберта и частотно-временных диаграмм к результатам численного моделирования аттракторов внутренних волн удалось получить временные и пространственные волновые характеристики, в частности волновые векторы, соответствующие временным частотам, полученным с помощью частотно-временных диаграмм. При этом используется преобразование Гильберта с фильтрацией по узкому диапазону частот. Частотно временные диаграммы для режимов со слабой надкритичностью показывают возникновение дочерних волн на частотах, соответствующих триадному волновому резонансу. Выполнение триадного резонанса для дочерних частот демонстрируется с помощью биспектров, на которых произведение амплитуд показано на декартовом произведении частотных диапазонов. После фильтрации пространственных полей горизонтальной компоненты скорости по полученным частотам получены соответствующие волновые векторы, также удовлетворяющие условиям триадного резонанса волновых векторов. Результаты хорошо соответствуют данным экспериментов, проводимых в ENS de Lyon.
Бесплатно
Проблема отката в ориентированной распределенной системе
Статья научная
Для распределенной системы, в основе которой лежит ориентированный граф без кратных ребер и петель, рассматривается проблема отката (backtracing problem): как передать сообщение от конца дуги в ее начало. Ставится задача создания на графе структуры, позволяющей передавать сообщение из конца любой дуги в ее начало по кратчайшему пути. Такая структура в каждой вершине a задаётся отображением номера вершины b в номер исходящей дуги, через которую проходит кратчайших путь от a к b. В частности, такое отображение позволяет симулировать в ориентированных распределенных системах алгоритмы решения задач на графе, разработанные для неориентированных распределенных систем. Это увеличивает время работы таких алгоритмов (в тактах, где время пересылки сообщения по дуге не превосходит 1 такт) не более чем в k раз, где k диаметр графа, k 2) и N = O (1), где T - время (в тактах) работы алгоритма, N - число сообщений, одновременно передаваемых по дуге. В разделе 9 доказано, что эти оценки времени не улучшаемые. В разделе 10 «быстрый» алгоритм модифицируется для синхронной модели с N =1. Заключение подводит итоги и намечает направления дальнейших исследований.
Бесплатно
Программное обеспечение для создания адаптивных сеток
Статья научная
В этой статье мы представляем программный пакет для создания адаптивных конечно-разностных сеток через представление гидромеханических переменных разреженным рядом вейвлетов. Приводятся технические детали реализации. В частности, описаны используемые структуры данных и способ распараллеливания вычислений. Также представлены результаты решения некоторых физических задач с привлечением данного пакета.
Бесплатно
Статья научная
В статье описываются функциональные возможности и структура программного модуля для автоматизированной адаптации интерфейсов веб-приложений. Особое внимание уделяется идентификации и различению псевдоанонимных пользователей веб-приложений для адаптации интерфейса под конкретного пользователя. Разработанный подход обеспечивает возможность псевдоидентификации киберсущностей в контексте поведения пользователей и автоматизированную адаптацию интерфейсов под особенности выделенного пользователя в зависимости от поставленных задач.
Бесплатно
Равномерное распределение нагрузки аппаратно-программного ядра в UNIX-системах
Статья научная
В данной статье рассматривается задача максимального увеличения пропускной способности сетевого стека при взаимодействии с аппаратно-программным ядром для обеспечения стабильности работы физического сервера. Разработаны алгоритмы и программные коды для оптимизации распределения нагрузки на центральные процессоры методом параллелизации ядра. Также рассмотрены статистические данные повышающейся мощности распределенных атак, влияющих на сетевую инфраструктуру. Показано влияние приложений, имеющих выход во внешнюю глобальную сеть, на производственную часть физического сервера, представляемую в виде физических ресурсов. С помощью разработанного и реализованного алгоритма (на языке « BASH »), произведено распределение нагрузочной способности по физическим ядрам сервера с целью дальнейшего снижения нагрузочной способности на вычислительную мощность центрального процессора. Продемонстрированы блок-схемы алгоритмов, а также итоговые результаты тестирования каждого этапа разработки. Реализована оптимизация сетевого режима « AF_PACKET », благодаря которой появилась возможность принимать внешние сетевые пакеты без каких-либо блокировок, что, в свою очередь, повышает эффективность достижения заданной цели (при запросе от сервера к клиенту). Анализируется возможность принимать до десяти миллионов входящих сетевых пакетов с помощью программных средств физического сервера, что позволяет обеспечить стабильную обработку информации для бесперебойной работы при DDoS -атаках « SYN -флуда», у которых реализована возможность перегрузки многомиллионными сетевыми пакетами. Подобное количество входящих сетевых пакетов может привести к заполнению внешнего сетевого канала с последующим повышением нагрузочной способности сетевого TCP/IP стека, что перекрывает возможность зоны удаленного управления физическим сервером в кратчайшие сроки, а также нарушает работоспособность рабочей среды.
Бесплатно
Распараллеливание реализаций сугубо последовательных алгоритмов
Статья научная
Работа посвящена теме распараллеливания программ в особо сложных случаях - когда используемый алгоритм является сугубо последовательным, параллельных альтернатив используемому алгоритму нет, а время его выполнения неприемлемо велико. Рассматриваются различные методы распараллеливания программных реализаций таких алгоритмов и балансировки получающейся вычислительной нагрузки, позволяющие получить значительное ускорение выполнения прикладных программ, в которых используются сугубо последовательные алгоритмы. Приведенные методы иллюстрируются практикой их применения к двум алгоритмам, используемым в среде динамического анализа программ. Основная цель данной работы - показать, что использование в программной реализации сугубо последовательного алгоритма не означает неизбежность его последовательного выполнения. Предложенные методы распараллеливания реализаций таких алгоритмов и балансировки получающейся вычислительной нагрузки могут способствовать созданию эффективной параллельной программы, полностью использующей предоставленные ей аппаратные возможности современных вычислительных систем.
Бесплатно
