Preview

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

Расширенный поиск
Том 30, № 1 (2018)
Скачать выпуск PDF
7-24 128
Аннотация
Задача идентификации состояний в конечном автомате была и остается актуальной, поскольку используется во многих приложениях, в частности, при моделировании и тестировании дискретных управляющих систем. Для идентификации текущего состояния системы строятся так называемые установочные и синхронизирующие эксперименты с конечными автоматами, в то время как для идентификации начального состояния системы используются диагностические или различающие эксперименты. Установочные, синхронизирующие, диагностические или различающие эксперименты известны как «умозрительные» эксперименты с конечными автоматами, и методы синтеза входных последовательностей для таких экспериментов (если существуют) в настоящее время определены для недетерминированных и детерминированных, полностью и частично определенных автоматов, описывающих эталонное поведение системы. Известно, что проблема проверки существования и построения установочных, синхронизирующих, диагностических или различающих экспериментов существенно усложняется, если эталонное поведение системы описывается недетерминированным и частичным автоматом, что достаточно часто случается при описании сложных современных систем. Известно также, что в некоторых случаях сложность можно понизить, переключившись на адаптивный (условный) эксперимент с системой. В настоящей работе мы исследуем влияние частичности автомата и адаптивности эксперимента на сложность проверки существования и построения установочных, синхронизирующих, диагностических и различающих экспериментов для детерминированных и недетерминированных автоматов и иллюстрируем соответствующую сложность с использованием подходящих рисунков.
25-40 100
Аннотация
Конечные автоматы широко используются для анализа и синтеза дискретных систем. При описании систем, поведение которых зависит от времени, конечный автомат расширяется введением временных аспектов и вводится понятие временного автомата. В настоящей статье рассматривается проблема построения параллельной композиции для двух моделей временных автоматов, а именно, для автоматов с таймаутами и автоматов с временными ограничениями. Две эти формы временных автоматов не являются взаимозаменяемыми и являются более частными случаями общей модели временного автомата, содержащего как таймауты, так и временные ограничения. Мы также считаем, что все выше упомянутые модели временных автоматов имеют целочисленные выходные задержки (выходные таймауты). Автоматы-компоненты работают в режиме диалога, по завершении которого композиция выдаёт внешний выходной символ. При решении задач анализа для системы взаимодействующих конечных автоматов с использованием классических методов такая композиция обычно описывается единственным автоматом. В работе показывается, что в общем случае, в отличие от случая классических конечных автоматов, наличия «медленной внешней среды» и отсутствия осцилляций недостаточно для описания поведения композиции детерминированным автоматом с одной временной переменной, если входные символы могут поступать не только в целочисленные, но и рациональные моменты времени. Тем не менее, определяется класс систем, в которых каждое внешнее входное воздействие инициирует диалог между компонентами, что позволяет описать поведение такой композиции детерминированным автоматом с одной временной переменной. В частности, рассматривается последовательная композиция временных автоматов, которая удовлетворяет такому ограничению. Другое ограничение продиктовано наличием таймаутов, значение которого в каждом из состояний должно превышать величину выходной задержки при обработке любого перехода в этом состоянии.
41-54 80
Аннотация
В этой статье рассказывается о разрабатываемом нами веб-сервисе. Разрабатывая этот сервис, мы преследуем две цели. Первая - предложить исследователям платформу, где они могли бы проводить предварительные эксперименты с различными методами генерации тестов для цифровых схем, для проверки различных идей. Вторая - возможность «на лету» поделиться реализациями новых методов. Процедура разработки веб-сервиса была разделена на три этапа: дизайн архитектуры, реализация облегчённой версии и фактическая реализация. В этой статье рассказывается о первых двух этапах. Есть два типа архитектур веб-сервисов - с монолитным ядром и микроядром - и наша архитектура обладает свойствами обоих типов. Мы стремились к тому, чтобы получить монолитное ядро, поскольку желаемая функциональность не так уж трудно реализовать. Однако расширяемость реализациями новых методов подразумевает, что часть функций (а именно, реализации методов) должны быть разработаны как отдельные под-сервисы. Реализация легкой версии была выполнена для единственного метода: метода перебора области неисправности для модели константных неисправностей. Она показал, что разработанная архитектура жизнеспособна. Однако были обнаружены некоторые проблемы с ней. Механизм развертывания добавляемого «на лету» метода неясен, так как неясно, как удовлетворить возможные зависимости реализации. Кроме того, архитектура не соответствует классическому дизайну веб-сервиса: у сервиса есть состояния, которых не должно быть, если сервис классифицирован как классический. Решение этих вопросов остается на будущее.
55-68 187
Аннотация
В статье рассматривается проблема анализа приложений под ОС Андроид с целью выявления вредоносного поведения. Представлены методы анализа такого рода приложений, которые применялись при проведении реальных программно- и научно-технических экспертиз (статические, динамические проверки, отладка, декомпиляция, логирование). Описаны процесс анализа, существующие приложения, а также собственное программное обеспечение.
69-88 111
Аннотация
Эта статья представляет собой обзор серии работ авторов, посвящённых исследованию распределенных систем. Рассматривается асинхронная модель распределённой системы, представленную сильно связанным ориентированным корневым графом, с ограниченной емкостью дуги (в том смысле, что только ограниченное количество сообщений может быть отправлено по дуге за определенный интервал времени). Граф может быть статическим или динамическим, т.е. меняющимся во времени. Для статического графа предлагается алгоритм построения прямого и обратного остовных деревьев с оценкой времени O ( n / k + d ), размером памяти в вершине и сообщения O ( n d log D+), где n - число вершин графа, k - емкость дуги, d - длина максимального пути, D+ - максимальная полустепень исхода вершин. Построенные кушниренко используются в распределенном алгоритме вычисления функции от мультимножества значений, приписанных вершинам графа, за время не более 3 d . В динамическом графе предполагается, что k = 1, дуга может появляться, исчезать или менять свой конец. Предлагается алгоритм мониторинга динамического графа, который доставляет в корень информацию о каждом изменении в графе за время O ( n ) или O ( d ) после прекращения изменений. Также предлагается алгоритм сбора информации о вершинах графа и разметки графа за время O ( n ). Эта разметка используется в алгоритме вычисления функции от мультимножества на динамическом графе за время O ( n2) с размером сообщения O ( log n ) или за время O ( n ) с размером сообщения O ( n log n ).
89-102 847
Аннотация
Bitcoin является самой популярной криптовалютой на планете. В основе Bitcoin лежат криптография и пиринговая сеть. Будучи псевдоанонимной криптовалютой, Bitcoin очень часто используется преступным сообществом для отмывания денег или оплаты нелегальных товаров и услуг. В данной работе мы представляем ращличные методы для деанонимизации пользователей Bitcoin, что является чрезвычайно важной задачей при расследовании киберпреступлений и противодействию отмыванию денег.
103-114 70
Аннотация
Рассмотрен комплекс мер и средств автоматизации для обеспечения непрерывности бизнеса в жизненном цикле ответственных систем. Этот комплекс получил название система обеспечения жизненного цикла (СОЖЦ). Целью системы является снижение уровня рисков от проявления критических ошибок в системном и прикладном программном обеспечении на всем жизненном цикле ответственной системы, снижение эксплуатационных рисков и совокупной стоимости владения ответственными системами. СОЖЦ в терминах ISO/IEC/IEEE 15288 представляет собой обеспечивающую систему (enabling system). СОЖЦ создается для обеспечения деятельности организации-собственника ответственной системы.
115-126 110
Аннотация
В работе описывается применение наборов SIMD инструкций (Single Instruction Multiple Data) для параллелизации алгоритма генерации псевдослучайных чисел. Дан обзор расширений MMX, SSE, AVX2, AVX512, реализующих принцип SIMD. Приведен пример реализации генератора LFSR113 с использованием расширения AVX512. Приведен сравнительный анализ скоростей работы различных реализаций алгоритма.
127-136 79
Аннотация
Неполностью описанные объекты могут встретиться в самых разных предметных областях и приложениях - от медицины до управления космическими кораблями. Начиная работу по проектированию и разработке системы поддержки принятия решений, которая должна работать с неполностью описанными объектами, необходимо предварительно выбрать один из альтернативных подходов. В основе одного из двух подходов, рассматриваемых в этой статье, находится логический вывод по заранее зафиксированным правилам. В таком подходе интенсивно используются продукции вида "ЕСЛИ-ТО". Другой подход, который часто называется прецедентным, предполагает наличие базы прецедентов, наполненной реальными и/или искусственными (модельными) случаями. Для этого второго подхода правила и модели объектов не являются необходимыми, но он значительно ближе к модели принятия решений, которая используется человеком в процессе мышления.
137-160 161
Аннотация
После появления огромного количества научных данных, которые необходимо было хранить и обрабатывать, в мире баз данных возникла задача поддержки больших многомерных массивов. Стала необходимой разработка специальных баз данных, которые основывались бы на модели данных, "сердцем" которой было понятие массива (array). Разработка хорошо организованной системы управления базой данных, базирующейся на нетрадиционной модели данных, требовала решения следующих задач: формальное определение модели данных, основывающейся на понятии массива; построение формальной алгебры, работающей с объектами модели; разработка правил оптимизации запросов на логическом уровне, а затем и на физическом. Эти задачи уже решались создателями специальных баз данных, настроенных на обработку и хранение массивов (array databases). В данной работе рассматриваются понятия массива, формальные алгебры и методы оптимизации запросов в таких развитых базах данных, как RasDaMan, AML, SciDB - базах данных, ориентированных на хранение и обработку крупных многомерных массивов.
161-182 100
Аннотация
В статье рассматривается способ обработки распределённых страниц в Oracle Real Application Clusters (Oracle RAC) и проводится его сравнение с другими известными способами в контексте сравнения архитектур доступа к страницам. В результате выявления недостатков традиционного способа, применяемого в Oracle RAC, предлагается новый способ доступа, в основе которого лежит введение еще одного состояния страницы - состояния «разгрузки», повышающее эффективность обработки распределённых страниц за счёт снижения количества пересылок между узлами при обработке горячих страниц.
183-194 78
Аннотация
В работе проводится численное моделирование обтекания гармонически осциллирующих тонких пластин с разной формой торцов в диапазоне чисел Рейнольдса 10<Re<600. Для описания движения жидкости решается полная нестационарная система уравнений Навье-Стокса. Задача рассматривается в плоской постановке. Численная модель реализуется на базе открытой платформы OpenFOAM. Рассматривается вопрос о влиянии формы торцов на гидродинамическое сопротивление в режимах с интенсивным вихреобразованием. Проводится анализ структуры течения, распределения давления по поверхности пластин, выполняется расчет коэффициентов сопротивления для разных амплитуд колебания. Результаты исследования показывают, что изменение формы торцов приводит к смещению точек отрыва вихрей с пластины. Это сказывается на распределении давления по поверхности пластины. Так у усеченных пластин разница между измеренным давлением на правой и левой сторонах пластины в окрестности торцов оказывается меньше, чем у прямоугольных. Это, в конечном счете, приводит к снижению результирующего аэродинамического сопротивления усеченных пластин. В рассматриваемом диапазоне параметров значения коэффициента сопротивления для прямоугольной пластины лежат в среднем на 14% выше. Полученные результаты хорошо объясняют большой разброс данных между проведенными ранее экспериментальными и численными исследованиями, так как практически во всех численных исследованиях сечение пластины принимают прямоугольным. В тоже время в экспериментах обычно используются образцы с усеченными торцами. Соответствующие данные для каждого из этих типов пластин хорошо согласуются с полученными в рамках данного исследования результатами.
195-214 179
Аннотация
В данной работе проведено сравнение эффективности решателей разреженных систем линейных алгебраических уравнений, построенных на основе одних из наиболее быстрых итерационных методов, метода BiCGStab (метода бисопряженных градиентов со стабилизацией) и метода FGMRES (гибкого метода обобщенных минимальных невязок). В работе представлены оценки трудоемкости выполнения одной итерации рассматриваемых методов. Получено условие, которому должна удовлетворять размерность подпространства Крылова в методе FGMRES для того, чтобы трудоемкость одной итерации данного метода была меньше трудоемкости одной итерации метода BiCGStab. Кроме того представлена модификация метода FGMRES, позволяющая останавливать алгоритм до очередного рестарта в случае достижения заданной точности. На языке С++ на основе представленных алгоритмов методов BiCGStab и FGMRES (в том числе с ILU- и многосеточным предобуславливанием) разработаны решатели разреженных систем линейных алгебраических уравнений. Сравнение эффективности разработанных решателей проводилось на разностных аналогах уравнений Гельмгольца и Пуассона. Системы были взяты из тестовой задачи о моделировании обтекания кругового профиля, совершающего вынужденные поперечные колебания. Разностная схема для решения задачи строится на прямоугольной структурированной сетке интегро-интерполяционным методом LS-STAG - методом погруженных границ c функциями уровня. Вычислительные эксперименты показали, что метод FGMRES на задачах такого класса демонстрирует более высокую скорость сходимости по сравнению с методом BiCGStab. Время проведения расчета при использовании метода FGMRES сократилось более чем в 6.5 раз без предобуславливания и примерно в 3 раза с предобуславлванием. Реализация модифицированного алгоритма метода FGMRES также сравнивалась с аналогичным решателем из библиотеки Intel® Math Kernel Library. Вычислительные эксперименты показали, что разработанная реализация метода FGMRES позволила получить ускорение по сравнению с использованием Intel® MKL в 3.4 раза без предобуслвливания и в 1.4 раза при использовании ILU-предобуславливания.
215-226 85
Аннотация
Моделирование гидродинамических явлений, связанных с обтеканием подвижных деформируемых тел является актуальной инженерной задачей для различных технических приложений. В данной статье описан метод вихревых петель, позволяющий моделировать обтекание тел без необходимости предварительного задания линий схода завихренности. Приведено верифицирование методики на экспериментальных данных обтекания крыла конечного размаха и сферы. Показана точность, достаточная для применения программы и методики в инженерных приложениях. Сделаны выводы о возможности перехода к подвижным и деформируемым телам. Программа реализована на языке С++ с использованием библиотеки MPI для организации пересылки данных при параллельных вычислениях.


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


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