Статьи журнала - Труды Института системного программирования РАН
Все статьи: 115
Распределённые алгоритмы на корневых неориентированных графах
Статья научная
Рассматриваются распределённые алгоритмы решения задач на неориентированных графах. В разделе 2 определяется используемая модель, особенностью которой является наличие корня, с которого начинается и в котором заканчивается работа алгоритма. Описываются синхронная и асинхронная разновидности модели. В разделе 3 предлагаются алгоритмы решения любых задач, основанные на сборе информации о всём графе в корне или в каждой вершине, а также, если необходимо, разметке графа (его вершин и/или рёбер). Акцент сделан на времени работы алгоритма, а при минимальном времени - на экономии памяти в вершинах и суммарном объёме пересылаемых сообщений. В остальной части статьи рассматриваются оптимизации для конкретных задач: построение максимального независимого множества (MIS - Maximal Independent Set), поиск множества всех мостов в графе (FSB - Finding Set of Bridges), построение минимального остовного дерева во взвешенном графе (MST - Minimum Spanning Tree). В разделе 4 предлагается модификация общих алгоритмов для этих задач, уменьшающая оценки размера памяти вершин и сообщений. Раздел 5 содержит нижние оценки сложности решения этих задач. В разделе 6 для синхронной модели уменьшается время работы алгоритмов с разметкой графа до нижней границы для задач с однозначным решением, зависящим только от простых циклов графа, в частности, FSB, MST и задачи поиска гальмильтонова цикла. В разделе 7 рассматриваются оптимальные по времени алгоритмы для FSB и MST для обеих моделей: синхронной и асинхронной. Заключение подводит итоги и намечает направления дальнейших исследований.
Бесплатно
Статья научная
Метод погруженных границ LS-STAG и его модификации для решения сопряженных задач гидроупругости c использованием моделей турбулентности Смагоринского, Спаларта - Аллмараса, и SST в рамках RANS, LES и DES подходов к моделированию турбулентности реализованы в программном комплексе «LS-STAG_turb» для моделирования движения профилей в потоке вязкой несжимаемой среды. Комплекс позволяет моделировать обтекание движущихся профилей произвольной формы и систем из любого числа профилей, имеющих одну или две степени свободы, например, авторотацию роторов ветроэнергетических установок, ветровой резонанс систем профилей. Для сокращения затрат машинного времени на проведение расчетов разработана параллельная версия алгоритмов и проведена оптимизация участков последовательного кода. Использованы такие технологии параллельного программирования, как Intel® Cilk™ Plus, Intel® Threading Building Blocks и OpenMP.
Бесплатно
Свободное программное обеспечение для моделирования жидкости со свободной поверхностью
Статья научная
Задачи течения вязкой несжимаемой жидкости со свободной поверхностью представляют собой отдельный класс задач механики сплошной среды и имеют большую практическую значимость. При моделировании таких процессов исследователь сталкивается с достаточно большим числом особенностей и ограничений, критически важных для получения корректного решения. Целью данной работы является обзор существующих численных методов, которые можно применить к решению задач течения жидкости со свободной поверхностью, и программных комплексов с открытым исходным кодом, в которых эти методы реализованы, а также выявление границ применимости рассмотренных программных комплексов. Были рассмотрены несколько численных методов (Volume of Fluid, Smoothed Particle Hydrodynamics, Particle Finite Element Method v.2), реализованные в пяти разных пакетах программ с открытым исходным кодом: OpenFOAM, Gerris, pySPH, DualSPHysics, Kratos. В качестве тестовых задач были выбраны следующие примеры: обрушение колонны жидкости и падение капли в слой жидкости. Решения, полученные в выбранных пакетах, были сопоставлены с известными результатами экспериментов. Проводилось сравнение времени, затраченного на решение задач в различных пакетах. Наилучшие результаты для выбранных тестов показали пакеты OpenFOAM и Gerris: в них содержатся необходимые для решения задач инструменты - возможность расчета задач в двумерной, трехмерной либо осесимметричной постановке, а также корректный учет поверхностного натяжения жидкости. При этом пакет Gerris дает существенное ускорение решения "крупных" задач за счет использования динамически перестраиваемых сеток. Пакет DualSPHysics направлен на решение задач прибрежной инфраструктуры, где рассматривают, как правило, трехмерные задачи и нет необходимости учета поверхностного натяжения. Пакет pySPH разрабатывался с целью наглядной демонстрации работы численного метода SPH, поэтому исходный код записан на языке Python без оптимизации. Пакет Kratos, в частности, модуль PFEM-2, в настоящий момент находится в разработке, поэтому некоторые возможности в нем еще не реализованы.
Бесплатно
Статья научная
Резюме: JetOS - перспективная бортовая операционная система реального времени (ОСРВ), разработка которой в настоящее время ведется в рамках научно-исследовательской работы ГосНИИАС. В статье указаны предпосылки появления JetOS и рассмотрены работы, ведущиеся по направлению создания ОСРВ. ОСРВ разрабатывается в соответствии с DO-178C и ARINC 653, учтена возможность работы с OpenGL SC. В статье приведены аппаратные аспекты создания ОСРВ - поддержка многоядерности, платформонезависимость и другие. Одной из важнейших задач при разработке ОСРВ является получение сертификационного пакета, соответствующего DO-178C, благодаря чему JetOS можно будет применять при создании и модернизации авионики для гражданской авиации.
Бесплатно
Синтаксический анализ графов с использованием конъюнктивных грамматик
Статья научная
Графы используются в качестве структуры данных для представления больших объемов информации в компактной и удобной для анализа форме в различных областях - биоинформатике, графовых базах данных, статическом анализе кода и др. При этом оказывается необходимо вычислять запросы к большим графам с целью выявления зависимостей между их вершинами. Ответом на такие запросы обычно является множество всех троек (A, m, n ), для которых существует путь в графе от вершины m до вершины n такой, что метки на ребрах этого пути образуют строку, выводимою из нетерминала A в некоторой контекстно-свободной грамматике. Говорят, что такой тип запросов вычисляется с использованием реляционной семантики запросов. Кроме того, существуют конъюнктивные грамматики, образующие более широкий класс грамматик, чем традиционные контекстно-свободные грамматики. Использование конъюнктивных грамматик в задаче синтаксического анализа графов позволяет формулировать более сложные запросы к графу и решать более широкий круг задач. Известно, что задача вычисления запросов к графу с использованием реляционной семантики и конъюнктивных грамматик является неразрешимой. В данной работе предлагается алгоритм, вычисляющий приближенное решение этой задачи, а именно, аппроксимацию сверху. Предложенный алгоритм основан на матричных операциях, и проведенные эксперименты показывают, что его производительность может быть существенно повышена, благодаря использованию вычислений на графическом процессоре.
Бесплатно
Статья научная
При синтезе современных интегральных схем разработчики все чаще прибегают к услугам сторонних фирм для реализации тех или иных компонент системы (Intellectual Property cores, перепрограммируемых компонент на базе FPGA и т.д.) с целью снижения ее стоимости. В компонентах, изготовленных сторонними фирмами, могут быть спрятаны вредоносные подсхемы (Trojan circuits) c целью разрушения системы или извлечения из нее конфиденциальной информации. Trojan Circuits (TCs) обычно действуют в ситуациях, которые возникают в работающей системе чрезвычайно редко, поэтому они не обнаружимы ни в процессе верификации системы, ни в процессе ее тестирования. В работе предлагается подход к проектированию частично программируемых схем из вентилей, программируемых блоков памяти (LUTs) и программируемых мультиплексоров (MUXs), ориентированный на маскирование ТCs. Такой подход к синтезу позволяет либо замаскировать действие TC в случае ее обнаружения, либо получить схему, в которой эффективное введение TCs становится невозможным. Предложен способ перепрограммирования блоков памяти LUTs для маскирования TC. Сформулировано требование к замещающей функции, поступающей на свободный вход программируемого блока, основанное на анализе частичных функций внутренних полюсов комбинационной схемы. Построение частичных функций выполняется с использованием операций над Reduced Ordered Binary Decision Diagrams (ROBDD-графами), строящимися для фрагментов схемы. Операции характеризуются полиномиальной сложностью.
Бесплатно
Система автоматов: композиция по графу связей
Статья научная
Статья посвящена проблеме моделирования и композиции составных систем. Компоненты системы моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга - каналу связи, соединяющему выход одного автомата со входом другого автомата. Автомат в вершине графа в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Входы (выходы) автоматов, которые не соединяются с выходами (входами) автоматов, являются внешними, через них осуществляется связь системы с её окружением. Автоматы системы работают синхронно: на каждом такте каждый автомат выполняет один переход. Переход автомата, предъявляя требования к состоянию всех входов и выходов автомата (указываются сообщения на них), отдельно указывает ту часть входов и выходов, по которым сообщения соответственно принимаются и посылаются, соответственно. Синхронность взаимодействия автоматов означает, что для каждого соединения требования автоматов, связанных этим соединением, должны быть согласованы. Это даёт возможность описывать более широкий спектр поведений автомата. Например, приоритетный приём сообщений: если на входах автомата имеется несколько сообщений, автомат может принять сообщения с наивысшим приоритетом, не принимая остальные сообщения. Также это позволяет автомату выполнять приём сообщений независимо от того, удаётся или не удаётся одновременно послать некоторое сообщение на некоторый выход. Определяется композиция автоматов системы по графу связей и доказывается её ассоциативность. В заключение определяются направления дальнейших исследований.
Бесплатно
Система автоматов: условия детерминизма и тестирование
Статья научная
Статья посвящена проблеме тестирования составных систем, компоненты которых моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга - каналу связи, соединяющему выход одного автомата со входом другого автомата. Предполагается выполненной следующая гипотеза о связях: граф связей статический, а отображаемая им структура связей не содержит ошибок. Автомат, находящийся в вершине графа, в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Определяется ассоциативная композиция автоматов системы. Показывается, при каких ограничениях на автоматы и граф связей их композиция, т.е. сама система, детерминирована. Целью тестирования является покрытие переходов автоматов компонентов, которые достижимы при работе этих автоматов в системе. Предполагается, что при тестировании возможно наблюдение изменения состояний автоматов системы и передаваемых между ними сообщений. Полное тестирование системы автоматов без учёта гипотезы о связях может потребовать число тестовых воздействий порядка произведения чисел состояний автоматов компонентов, а с учётом гипотезы о связях - порядка суммы этих чисел. При равном числе состояний всех автоматов это даёт экспоненциальное уменьшение числа тестовых воздействий. При условии выполнения гипотезы о связях для детерминированной системы предлагается алгоритм генерации тестов, основанный на фильтрации тестов, генерируемых для покрытия всех переходов композиции. Тест отбрасывается, если он покрывает только такие переходы в компонентах системы, которые покрываются остающимися тестами. В заключение определяются направления дальнейших исследований.
Бесплатно
Сравнительный анализ двух подходов к статическому анализу помеченных данных
Статья научная
В настоящее время одним из наиболее эффективных средств поиска проблем безопасности ПО является анализ помеченных данных. Он может быть реализован на основе статического анализа и успешно обнаруживать ошибки, приводящие к уязвимостям, таким как внедрение кода или утечка непубличных данных. Возможны несколько существенно различных подходов к реализации алгоритма распространения пометок по внутреннему представлению программы: на основе анализа потоков данных или на базе символьного исполнения. В данной работе описаны особенности реализации обоих подходов в рамках существующей инфраструктуры статического анализатора для поиска ошибок в программах на С#, а также проведено сравнение этих подходов в различных аспектах: область применения, качество результатов, производительность и требовательность к ресурсам. Поскольку оба подхода используют единую инфраструктуру доступа к информации о программе и реализованы одной командой разработчиков, результаты сравнения близки к объективным и могут быть использованы при выборе оптимального варианта в контексте поставленной задачи.
Бесплатно
Тестирование системы автоматов с буферизацией сообщений
Статья научная
Статья посвящена проблеме тестирования составных систем, компоненты которых моделируются конечными автоматами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершины которого соответствуют автоматам компонентов, а дуги - каналам связи. Предполагается выполненной следующая гипотеза о связях: граф связей статический, а отображаемая им структура связей не содержит ошибок. Автомат, находящийся в вершине графа, в каждом состоянии может принимать несколько сообщений по входным дугам (не более одного по каждой дуге) и посылать несколько сообщений по выходным дугам (не более одного по каждой дуге). Целью тестирования является покрытие переходов автоматов компонентов, которые достижимы при работе этих автоматов в системе. Предполагается, что при тестировании возможно наблюдение изменения состояний автоматов в вершинах графа и сообщений на дугах графа. Сначала рассматривается упрощённая модель системы, в которой циркулирует только одно сообщение. На её примере показывается, что гипотеза о связях позволяет существенно сократить время тестирования. Полное тестирование системы автоматов без учёта гипотезы о связях может потребовать число тестовых воздействий порядка произведения чисел состояний автоматов компонентов, а с учётом гипотезы о связях - порядка суммы этих чисел. При равном числе состояний всех автоматов это даёт экспоненциальное уменьшение числа тестовых воздействий. Затем рассматривается более общая модель, когда в системе может быть одновременно много сообщений, но не более одного на каждой дуге. Определяется композиция автоматов системы и показывается, при каких ограничениях на автоматы их композиция детерминирована. Для детерминированной композиции предлагается алгоритм генерации тестов, основанный на фильтрации тестов, генерируемых для покрытия всех переходов композиции. Тест отбрасывается, если он покрывает только такие переходы в компонентах системы, которые покрываются остающимися тестами. В заключение определяются направления дальнейших исследований.
Бесплатно
Трансляция вложенных сетей Петри в классические сети Петри для верификации разверток
Статья научная
Вложенные сети Петри являются одним из удобных формализмов для моделирования и анализа поведения распределенных мультиагентных систем. Они естественным образом представляют структуру мультиагентных систем, так как фишки в системной сети сами являются классическими сетями Петри и могут иметь автономное поведение. Мультиагентные системы являются системами с высоким уровнем параллелизма. При верификации таких систем методами проверки модели (model checking) возникают серьезные трудности, связанные с взрывным ростом числа промежуточных состояний системы (state-space explosion problem). Для решения этой проблемы в литературе был предложен подход, основанный на построении развертки поведения системы. Ранее была изучена применимость разверток для верификации вложенных сетей Петри и предложен метод построения разверток для безопасных консервативных вложенных сетей Петри. В этой работе предлагается другой метод построения разверток для безопасных консервативных вложенных сетей Петри, основанный на трансляции таких сетей в классические сети Петри. Для классических сетей Петри затем применяются стандартные методы построения разверток. Также в работе обсуждаются сравнительные достоинства двух подходов.
Бесплатно
Численное исследование теплоотдачи в каналах с неглубокими подковообразными лунками
Статья научная
Работа посвящена численному исследованию теплоотдачи в прямоугольных каналах с односторонним нанесением неглубоких лунок. Математическое моделирование выполнено на базе уравнения Навье-Стокса, уравнения неразрывности, уравнения энергии. Для замыкания системы уравнений использована k-w-sst модель турбулентности. Численное решение получено с помощью программного пакета Code Saturne, распространяемого на основе свободной лицензии. Для построения сетки использовался программный пакет Salome. В работе рассмотрены вопросы верификации получаемого численного решения. На базе выполненного численного исследования проведена оценка теплогидравлической эффективности неглубоких лунок различной конфигурации для прямоугольных каналов с односторонним нанесением неглубоких лунок.
Бесплатно
Численное моделирование течения в канале с неглубокими лунками с использованием Code Saturne
Статья научная
Работа посвящена построению модели и численному исследованию течения в прямоугольном канале с неглубокими лунками. Математическое моделирование выполняется на базе дифференциальных уравнений движения, энергии и состояния. Численное решение получено с использованием метода конечных объемов на базе программного пакета с открытым программным кодом Code Saturne. Построение сетки, учитывающей особенности течения вблизи лунок, выполнено в программном пакете Salome со свободной лицензией. В работе рассмотрены вопросы создания сетки, показана зависимость получаемого решения от размерности сетки, проведен анализ влияния типа сетки на время ее генерирования и качество получаемого численного решения для течения в прямоугольном канале с неглубокими лунками.
Бесплатно
Чистая компиляция как парадигма программирования
Статья научная
В научной литературе широко представлено исследование возможностей интерпретируемого выполнения компьютерных программ. При этом противоположный подход, основанный на элиминации любых проявлений интерпретируемости, насколько можно судить, никем всерьез не исследовался. В настоящей статье рассматривается подход, предполагающий отделение всего происходящего во время исполнения программы от инструментов, использующихся программистом при ее написании, и намечается путь к построению универсального (равно пригодного как для системных, так и для прикладных задач) языка программирования.
Бесплатно
Статья научная
В статье описывается практический опыт разработки перспективной системы визуального планирования проектов на основе объектно-ориентированного каркаса. Используемый каркас представляет собой систему классов и интерфейсов, предназначенных для программной реализации моделей, методов и приложений теории расписаний. Благодаря наличию готовых компонентов для решения типовых задач, а также предусмотренным механизмам их конфигурирования и расширения, создание приложений осуществляется относительно просто. Применение каркаса позволило реализовать в целевой системе необходимый функционал проектного планирования, а также обеспечить его последующее развитие путем обобщения условий задач и расширения арсенала алгоритмов, применяемых для их решения.
Бесплатно
