Тема: ОПТИМИЗАЦИЯ КОМПОНЕНТОВ МНОГОМОДУЛЬНЫХ СИСТЕМ НА ОСНОВЕ РЕШЕНИЯ АВТОМАТНЫХ УРАВНЕНИЙ

Актуальность проблемы. Автоматная модель [1] используется для описания систем, которые переходят из состояния в состояние под действием входных воздействий, производя при этом выходные реакции. Соответственно, понятие автомата используется в различных областях для описания поведения различных управляющих систем, работающих в режиме «запрос-ответ». Описав поведение некоторой системы автоматом, можно оптимизировать реализацию системы, что в настоящее время становится все более актуальной задачей, особенно для систем с ограниченными вычислительными возможностями. Общим трендом является стремление сделать такие системы меньше, надежнее, и оптимизация компонентов относительно различных параметров направлена именно на это. Примером может служить Internet of Things (IoT,«интернет вещей») [2], в котором активно используются различные компоненты, которые можно было бы эффективно оптимизировать [2].
Оптимизация многомодульных систем часто осуществляется итеративно. В общем случае для оптимизации компонента в композиции можно использовать решение автоматного уравнения вида A• X =. A• B[3], где автомат А описывает совместное поведение остальных компонентов и часто называется контекстом. Однако сложность решения такого уравнения является очень высокой [4]. С другой стороны, известно [3], что можно выделить «окно», в котором находится последовательная композиция, а затем оптимизировать хвостовой компонент данной композиции, и в этом случае сложность оптимизации будет существенно ниже. В работе [5] применяется также «оконный подход», но выделяются «окна», где композиция не обязательно последовательная, что вносит дополнительные сложности в оптимизацию компонента; также в работе [5] практически не обсуждается оптимизация относительно числа состояний оптимизируемого компонента, а обсуждается оптимизация относительно других критериев: линий связи, отказоустойчивости относительно определенных неисправностей (fault-tolerance) и др., тогда как мы обсуждаем оптимизацию относительно числа элементов в логической схеме компонентов, т.е. оптимизацию относительно аппаратных реализаций автоматных сетей. В работе [6] описывается оптимизация сетей из структурных автоматов с использованием внутренних «безразличных» последовательностей (don't-cares)на основе решения задачи выполнимости булевых формул; мы же в нашей работе опираемся на построение сетевого эквивалента для хвостового компонента по алгоритму, представленному в [7]. Работа [8] также затрагивает тему оптимизации, но в ней авторы рассматривают не только входные «безразличные» последовательности, но и выходные «безразличные» последовательности, нахождение которых значительно более трудоемко. В работе [9] обсуждается оптимизация на основе решения автоматных уравнений и показывается, что иногда эффективнее решать не одно автоматное уравнение, а систему таких уравнений. Таким образом, исследования, проводимые в данной работе по оптимизации компонентов автоматных композиций, являются актуальными.
Целью работы является разработка метода оптимизации на основе выделения «окон» в композиции конечных автоматов, содержащих последовательную композицию компонентов системы, для последующей минимизации аппаратных реализаций выделенных компонентов.
Для достижения поставленной цели необходимо решить следующие задачи.
Задачи: исследование методов покомпонентной оптимизации дискретных управляющих систем, поведение которых описано синхронной композицией автоматов; анализ достоинств и недостатков различных методов; разработка метода оптимизации на основе выделения «окон» в композиции конечных автоматов, содержащих последовательную композицию компонентов системы; разработка метода итеративного выделения таких «окон» в синхронной композиции конечных автоматов; проведение экспериментов по оптимизации аппаратных реализаций компонентов многомодульных систем, заданных конечными автоматами.
Методы исследования. Для достижения поставленной цели в работе используется аппарат дискретной математики, в частности, методы теории автоматов.
Научная новизна.
Предложен новый метод для покомпонентной оптимизации автоматных сетей, основанный на итеративном выделении «окон» в многомодульной системе, которые содержат последовательную композицию компонентов, и построении сетевого эквивалента хвостового компонента.
Основные положения, выносимые на защиту.
1. Экспериментальная оценка сложности реализации конечного автомата и его минимальной формы с использованием ПЛИС.
2. Метод итеративного выделения «окон» в композиции конечных автоматов, которые содержат последовательную композицию компонентов, и экспериментальные результаты по оптимизации компонентов последовательной композиции.
Достоверность результатов. Все научные положения и выводы, содержащиеся в работе, основаны на утверждениях, доказанных с использованием аппарата классической теории автоматов.
Практическая ценность. Предложенный в работе метод может быть использован при логическом проектировании многокомпонентных дискретных систем, а именно для оптимизации компонентов таких систем.
Апробация работы. Основные положения и результаты, представленные в работе, обсуждались на двух конференциях, в частности, на конференции с международным участием «Новые информационные технологии в исследовании сложных структур» («ICAM») на Алтае и на Всероссийской конференции студенческих научно-исследовательских инкубаторов («СНИИ») в Томске. По результатам работы опубликовано 2 работы в изданиях, индексируемых в базе данных РИНЦ [10][11].
Структура и объем работы. Магистерская диссертация разделена на 4 главы.
Во введении обсуждаются актуальность и цель работы, сформулированы положения, выносимые на защиту.
Первая глава содержит основные определения и обозначения, которые используются в работе. Первая глава содержит определения конечного автомата, синхронной композиции автоматов; описывается аппаратная реализация конечных автоматов.
Конечный автомат (или просто автомат) представляет собой преобразователь последовательностей в одном алфавите в последовательности в другом алфавите [12]. Такая модель позволяет описать поведение систем, которые переходят из состояния в состояние под действием входных символов и производят при этом выходные символы; в этом случае часто говорят, что система реализует некоторую последовательностную функцию, отображая последовательности в одном (входном) алфавите в последовательности в другом (выходном) алфавите. Автомат называется полностью определенным, если из каждого его состояния по каждому входному символу возможен переход в некоторое состояние. Достаточно часто рассматривают инициальные автоматы, т.е. автоматы, в которых выделено начальное состояние. Инициальные полностью определенные автоматы называются эквивалентными, если эти автоматы в начальных состояниях под воздействием любой входной последовательности выдают одинаковые выходные последовательности.
При синтезе сложных (в том числе дискретных) управляющих систем важную роль играет представление системы в виде композиции других, более простых, в некотором смысле, подсистем. В настоящей работе рассматриваются системы, поведение которых можно описать синхронной композицией полностью определенных детерминированных автоматов [3]; в синхронной композиции обработка каждого входного сигнала происходит за один такт, и такая композиция обычно используется при описании поведения систем из аппаратных или аппаратно-программных компонентов. Аппаратной реализацией конечного автомата в нашей работе является логическая схема из адаптивных логических модулей (Adaptive Logic Module, ALM), которые представляют собой базовые логические элементы платформы Altera Cyclone V GX [13].
В настоящей работе рассматривается два подхода к покомпонентной оптимизации синхронной композиции автоматов. В первом случае компоненты оптимизируются как «самостоятельные» конечные автоматы независимо от других компонентов; в этом случае компонент можно заменить на любой эквивалентный ему автомат, и при этом чаще всего используется приведенная форма автомата-компонента. Однако известно [3], что поведение автоматной сети может остаться прежним, даже если автомат-компонент заменяется на неэквивалентный ему автомат. Поэтому компоненты можно оптимизировать в зависимости от поведения других компонентов; для такой оптимизации обычно привлекается явное или неявное решение автоматных уравнений.
Во второй главе рассматриваются вышеупомянутые подходы к покомпонентной оптимизации синхронной композиции автоматов. Для первого подхода в главе описывается алгоритм минимизации полностью определенных детерминированных автоматов. В другом случае компоненты оптимизируются в зависимости от поведения других компонентов. Для второго подхода в главе описываются алгоритм построения сетевого эквивалента хвостового компонента и алгоритм минимизации частичных детерминированных автоматов. Все вышеупомянутые алгоритмы были реализованы программно; данная глава также содержит описание особенностей программных реализаций.
В третьей главе рассматривается минимизация компонентов в композиции автоматов, поскольку, как отмечено выше, поведение автоматной сети может остаться прежним, даже если автомат-компонент заменяется на неэквивалентный ему автомат (подобный пример приведен в разделе 2.2). Поэтому компоненты можно оптимизировать в зависимости от поведения других компонентов; для такой оптимизации обычно привлекается явное или неявное решение автоматных уравнений. Общее решение автоматного уравнения вида A• X = A• B[3], где автомат А описывает совместное поведение всех компонентов, за исключение оптимизируемого компонента B, можно рассматривать как резервуар для выбора оптимального решения (относительно заданного критерия оптимизации). Однако сложность решения такого уравнения является очень высокой [4], и для понижения сложности такой покомпонентной оптимизации достаточно часто используется так называемый оконный подход (window approach) [3], который показал себя достаточно эффективным относительно различных критериев оптимизации. Поскольку в нашей работе мы оптимизируем компоненты относительно последующей аппаратной минимизации, то достаточно эффективным является итеративное выделение «окна», в котором находится последовательная композиция двух компонентов. В этом случае общее решение уравнения для хвостового компонента строится достаточно просто и является детерминированным частичным автоматом, минимальная форма которого, реализованная аппаратно, может заменить данный компонент без изменения внешнего поведения всей системы.
Последовательность «окон» можно выделять итеративно, т.е. выделить «окно», провести оптимизацию хвостового компонента, а затем выделить еще одно «окно», головным компонентом которого будет первое «окно», а хвостовым - соседний последовательный модуль, который не был оптимизирован. Такой алгоритм итеративного построения «окон» представлен в данной главе.
В четвертой главе описываются экспериментальные результаты. Для аппаратной реализации компонентов автоматной сети использовалась платформа Altera Cyclone V GX [13].
В ходе выполнения данной работы была исследована сложность аппаратных реализаций компонентов сети как независимых автоматов, так и в зависимости от поведения соседних компонентов. Экспериментально показано, что минимизация автомата-компонента не всегда приводит к оптимизации соответствующей аппаратной реализации, т.е. примерно в 5% случаев исходный неминимальный автомат имеет в реализации большее число базовых элементов аппаратной платформы. Однако в 95% случаев минимизация компонента приводит к уменьшению числа базовых элементов в его аппаратной реализации в среднем примерно на 20%. Соответственно, при оптимизации автомата как компонента сети представляется полезным прибегнуть к такой минимизации перед следующим шагом оптимизации на основе выделения «окон» с последовательной композицией и построения сетевого эквивалента хвостового компонента последовательной композиции. Сетевой эквивалент строится по алгоритму, описанному в разделе 2.2; минимизация сетевого эквивалента осуществляется с помощью алгоритма, описанного в разделе 2.3. Экспериментально показано, что в 80% случаев минимизация сетевого эквивалента приводит к более простой реализации по числу базовых элементов. Также показано, что предложенный в главе 3 подход к покомпонентной итеративной оптимизации представляется действенным для автоматных сетей.
В заключении кратко приводятся полученные в диссертации результаты, а также обсуждаются перспективы дальнейших научных исследований.

Купить

В процессе работы рассмотрены задачи оптимизации FPGA реализаций компонентов синхронной композиции конечных автоматов, которая широко используется для представления дискретных систем в виде композиций других, более простых в некотором смысле подсистем. В частности, предложен алгоритм выделения «окон» в композиции, содержащих последовательную композицию из двух компонентов. Проведены эксперименты по оптимизации компонентов автоматной сети как независимых автоматов, так и в зависимости от соседних компонентов. Показано, что в некоторых достаточно редких случаях независимая минимизация конечного автомата не приводит к оптимизации аппаратной реализации соответствующего компонента сети, однако в большинстве случаев представляется полезным прибегнуть к такой минимизации перед итеративной оптимизацией. Также показано, что построение сетевого эквивалента хвостового компонента по алгоритму, описанному в главе 2, в большинстве случаев приводит, по крайней мере, к оптимизации числа переходов в хвостовом компоненте, что в свою очередь приводит к оптимизации FPGA реализации данного компонента. Показано, что предложенный в главе 3 подход к покомпонентной итеративной оптимизации представляется действенным для автоматных сетей; для последовательных сетей наиболее действенной оказывается оптимизация компонентов близких к хвостовому компоненту в сети, поскольку поведение их сетевого эквивалента обуславливается конфигурацией всей схемы.
В дальнейшем планируется изучить влияние свойств автоматов на сложность их аппаратных реализаций; рассмотреть различные виды композиций с обратными связями и влияние топологии композиции на предложенный метод покомпонентной оптимизации.
Автор выражает искреннюю благодарность асп. РФФ ТГУ Широковой Екатерине Владимировне за полезные дискуссии и помощь в подготовке диссертации.

Купить