Preview

Моделирование и анализ информационных систем

Расширенный поиск
Том 29, № 1 (2022)
Скачать выпуск PDF

Algorithms 

6-19 114
Аннотация
Предложен алгоритм углового сверхразрешения на основе разложения Холецкого, представляющий собой модификацию алгоритма Кейпона. Показано, что предложенный алгоритм позволяет отказаться от обращения ковариационной матрицы входных сигналов. Проведено сравнение предложенного алгоритма с алгоритмом Кейпона по числу операций. Установлено, что предложенный алгоритм при большой размерности задачи обеспечивает некоторый выигрыш как при реализации на однопоточном, так и на многопоточном вычислителе. Получены численные оценки быстродействия предложенного и исходного алгоритма с использованием технологии параллельных вычислений CUDA NVIDIA. Установлено, что предложенный алгоритм обеспечивает экономию вычислительных ресурсов GPU и способен решать задачу построения пространственного спектра при увеличении размерности ковариационной матрицы входных сигналов почти в два раза.

Discrete Mathematics in Relation to Computer Science 

20-29 126
Аннотация

Численное исследование различных процессов приводит к необходимости уточнения (расширения) границ применимости вычислительных конструкций и инструментов моделирования. Для динамических систем данный вопрос может быть связан с обобщением понятия производной, сохраняющим актуальными применяемые конструкции. В настоящей статье вводится понятие слабой локальной дифференцируемости в пространстве интегрируемых по Лебегу функций и рассматриваются согласованность этого понятия с такими основополагающими вычислительными построениями как разложение Тейлора и конечные разности, а также свойства функций, обладающих данного вида дифференцируемостью на отрезке. Функцию f из L₁[a; b] назовём S-дифференцируемой в точке xₒ из (а; b), если существуют коэффициенты с и q, при которых выполняется fx₀x₀+h (f(x) - c - q·(x-x₀)) dx = o(h²). Найдены формулы для вычисления коэффициентов с и q, которые удобно обозначить fₛ(x₀) и fₛ ˊ(x₀) соответственно. Показано, что если функция f принадлежит W₁ⁿ⁻¹[a; b], n больше 1, и функция f⁽ⁿ⁻¹⁾ является S-дифференцируемой в точке хо из (а; b), то f приближается тейлоровским многочленом с точностью o((x-xₒ)ⁿ), а отношение Δⁿₕ(f, xₒ) к hⁿ стремится к fₛ⁽ⁿ⁾(xₒ) при стремлении h к 0. На основе частного Δⁿₕ (f, ·) и hⁿ строится последовательность {Ʌₘⁿ [f]} кусочно-постоянных функций, подчинённых разбиениям отрезка [а; b] на m равных частей. Показано, что для функции f из W₁ⁿ⁻¹[a; b], для которой определено значение f ₛ⁽ⁿ⁾(xₒ), { Ʌₘⁿ [f] (xₒ)} сходится к f ⁽ⁿ⁾(xₒ) при стремлении т к бесконечности, а для fЄ Wₚⁿ[a; b] последовательность { Ʌₘⁿ [f] } сходится к f⁽ⁿ⁾ по норме пространства Lₚ [I]. Место S-дифференцируемости в практическом и теоретическом плане определяется её двусторонними соотношениями с обычной дифференцируемостью. Доказан факт, что если f принадлежит W₁ⁿ⁻¹[I], и функция f⁽ⁿ⁻¹⁾ является равномерно S-дифференцируемой на I, то f принадлежит Cⁿ[f]. Рассмотренные построения имеют алгоритмический характер, и могут быть применены в численном исследовании на ЭВМ соответствующих моделей.

Software 

30-43 108
Аннотация
В работе предложен параллельный алгоритм решения задачи об изоморфизме граф-подграф и произведено экспериментальное исследование его эффективности. Задача является одной из самых известных NP-полных задач. Ее решение может потребоваться при решении многих практических задач, связанных с исследованием сложных структур. Мы решаем ее в постановке, в которой требуется найти все возможные изоморфизмы или доказать отсутствие таковых. Ввиду высокой трудоемкости задачи естественным является желание ускорить ее решение за счет распараллеливания алгоритма.Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Для проведения численного эксперимента использовалась открытая база данных из сети Интернет, специально разработанная для исследования алгоритмов поиска изоморфизмов. Также автором было разработано специальное приложение на языке C# для генерации собственных дополнительных наборов исходных данных с заданными характеристиками. Целью эксперимента было исследование ускорения, достигаемого за счет рекурсивно-параллельной организации вычислений. В работе приводится подробное описание предлагаемого алгоритма, а также полученных в ходе эксперимента результатов.

Theory of Computing 

44-59 121
Аннотация
В статье пересматриваются результаты работы, посвящённой задаче представления поведения программной системы в виде набора формул линейной темпоральной логики LTL с последующим использованием этого представления для проверки выполнимости программных свойств системы через процедуру доказательства справедливости логических выводов, выраженных в терминах логики LTL. В качестве программных систем, для спецификации поведения которых применяется логика LTL, рассматриваются счётчиковые машины Минского с ограничениями. Ранее при работе с темпоральной логикой LTL как с программной логикой фактически был введён специальный псевдооператор обращения к предыдущим значениям переменных, задействованных в элементарных высказываниях. Несмотря на то что этот псевдооператор легко реализуется в верификаторе Cadence SMV при доказательстве справедливости логических LTL-выводов, классическое определение логики LTL не предполагает его наличия. В данной статье для построения LTL-спецификации поведения ограниченной счётчиковой машины будут использоваться только бинарные переменные, а отслеживание их предыдущих значений будет осуществляться исключительно в рамках самой логики LTL посредством соответствующих формул.
60-72 109
Аннотация
Предложены методы повышения эффективности разработки СБИС на основе метода архитектурно-независимого проектирования. Рассмотрен маршрут высокоуровневого синтеза СБИС. Изложен принцип построения аппаратной модели СБИС на основе функционально-потоковой парадигмы программирования.Представлены результаты разработки методов и алгоритмов трансформации, функционально-потоковых параллельных программ в программы на языках описания аппаратуры, обеспечивающих поддержку процесса проектирования цифровых однокристальных систем. Рассмотрены принципы оценки и выделены классы ресурсов, требуемых для анализа проектных решений. Введены коэффициенты редукции и методики их расчета по каждому классу ресурсов. Предложен алгоритм расчета коэффициентов редукции и оценки требуемых ресурсов. Предложен алгоритм преобразования параллелизма с учетом заданных ограничений целевой платформы. Разработан механизм обмена метриками с архитектурно-зависимым уровнем. Приведены примеры редукции параллелизма для платформы ПЛИС и практическая реализация тестовых алгоритмов БПФ в базисе ПЛИС Virtex® UltraScale. Разработанные методы и алгоритмы позволяют использовать метод архитектурно-независимого синтеза для переноса проектов СБИС на различные архитектуры с помощью изменения параллелизма схемы и эквивалентных преобразований параллельных программ. Предложенный подход обеспечивает множество вариантов аппаратных решений для реализации на различных целевых платформах.


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


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)