Методы синтеза многоуровневых автоматов на счетчиках.
Актуальность работы. В настоящее время любая цифровая система включает устройство управления, от эффективности которого зависит основные характеристики системы в целом []. Устройство управления может быть реализовано либо как автомат с “жесткой” логикой, основанный на классической модели структурного автомата, либо как автомат с программированной логикой, основанный на операционно- адресном способе представления микрокоманд []. Кроме того, возможно объединение этих автоматов в одну систему, называемую композиционное микропрограмное устройство управления []. Одной из важных задач, возникающих при синтезе логических схем устройств управления (УУ) является минимизация аппаратурных затрат и, как следствие, стоимости устройства. Методы решения этой задачи зависят от элементного базиса, на котором реализуется схема УУ.
Элементный базис УУ прошел в своем развитии ряд этапов от транзисторов до схем с миллионами транзисторов на одном кристалле. Изменение базисов влечет за собой и изменение методов синтеза и оптимизации характеристик логических схем УУ. В настоящее время для синтеза УУ широко используются программируемые логические устройства (ПЛУ) []. Представители этого класса обладают большим разнообразием характеристик и функциональных возможностей, что значительно усложняет алгоритм синтеза УУ.
Одним из эффективных методов оптимизации схем УУ является их представление в виде многоуровневых структур []. Число уровней в схем УУ может достигать пяти [] , причем каждый из уровней обычно реализуется на разных элементах. Увеличение числа уровней приводит к необходимости формирования некоторых дополнительных переменных для связи между уровнями, что вызывает дополнительные требования к характеристикам ПЛУ. Этого недостатка лишены PR-автоматы [], основанные на зависимости выходных функций УУ от пары <исходное состояние, состояние перехода>.
Если граф-схема алгоритма (ГМА), по которой синтезируется УУ, является линейной (содержит в своем составе более 75% операторных вершин), то дальнейшая оптимизация схемы возможна за счет замены регистра памяти счетчиком []. При этом возникает ряд специфических задач, связанных с оптимальным кодированием состояний. Переход к новому типу устройств управления вызывает необходимость разработки новых методов решения оптимизационных задач.
В настоящей работе рассматривается задача синтеза логической схемы PR-автомата на счетчике в базисе ПЛУ. В силу всего сказанного выше работа является актуальной на современном этапе развития теории синтеза цифровых систем.
Область исследований. Областью исследований являются формализованные методы синтеза многоуровневых схем автоматов с ''жесткой'' логикой в базисе программируемых логических устройств. В качестве метода реализации выбраны PR-автоматы, обладающие рядом преимуществ по сравнению с другими методами организации многоуровневых структур. Основное преимущество PR-автоматов – отсутствие дополнительных переменных для связи между различными уровнями. В качестве основной модели рассматривается PR-автомат с преобразователем кодом состояний, память которого реализована на счетчике. Исходной информацией для синтеза является линейные граф-схемы алгоритма, что делает целесообразным применение счетчика. Так как оптимизационные задачи кодирования состояний для автоматов на счетчиках и PR-автоматов являются различными, то для устранения этих противоречий в схеме используется преобразователь кодов состояний.
Цель исследований. Целью работы является разработка методов синтеза PR-автоматов с преобразователем кодов состояний на счетчике. Элементным базисом для синтеза схемы автомата являются программируемые логические матрицы (ПЛМ) и программируемые постоянные запоминающие устройства (ППЗУ).
Задачи исследований. В процессе исследований необходимо решить следующие задачи:
Методы исследований. Методы исследований основаны на использовании теории конечных автоматов, теории структурного синтеза и теории графов. Исходной информацией для синтеза и теории графов. Исходной информацией для синтеза является линейные граф-схемы алгоритмы.
Структура работы и краткая характеристика каждой главы. Работа состоит из введения, трех глав и заключения, содержит список литературы из 22 наименований.
В первой главе рассматриваются методы синтеза автоматов Мили и определяются основные задачи исследований. Рассмотрены методы синтеза многоуровневых структур автоматов на ПЛУ, ПЗУ, ПЛИС и элементах среднего уровня интеграции (мультиплексоры, дешифраторы). Рассмотрены методы синтеза PR-автоматов, основанный на зависимости системы микроопераций от пар <исходное состояние, состояние перехода >. Рассмотрены методы оптимизации числа микросхем в логической схеме PR-автомата, основанные на копировании состояний и преобразовании кодов состояний. Рассмотрены общие принципы синтеза схем УУ на счетчиках. В конце главы сформулированы основные задачи, возникающие при синтезе PR-автоматов с ПКС на счетчиках.
Во второй главе предлагаются методы решения основных задач синтеза. Предлагается метод синтеза PR-автомата с ПКС на счетчике, позволяющий совместно решать оптимизационные задачи кодирования состояний. Предлагается метод синтеза PR-автомата с ПКС, основанный на разделении кодов последовательностей состояний и состояний в последовательностях. Рассматриваются методы реализации PR-автоматов на заказных матрицах.
В третьей главе проводятся исследования эффективности предложенных методов синтеза. Выведены формулы оценки аппаратурных затрат при синтезе различных схем автоматов на заказных матрицах, основанные на вероятностном подходе к заданию характеристик алгоритма. Исследованы три пары структур: <PY-автомат, PR-автомат с ПКС на счетчике >, <PY-автомат, PR-автомат с ПКС на счетчике с разделением кодов состояний >, <PR-автомат с ПКС на счетчике, PR-автомат с ПКС на счетчике с разделением кодов состояний >. Найдены области эффективного применения предложенных методов.