Автореферат

по теме:

"Исследование 4-х уровневой схемы управляющего автомата Мили в базисе стандартных БИС"

---

Содержание

Введение
Цель и задачи работы
Предполагаемая научная новизна
Планируемая практическая ценность
Обзор существующих разработок по теме
Текущие и планируемые результаты
Заключение и выводы
Список источников

---

Введение

Важнейшей частью любого цифрового устройства является управляющий автомат (УА). На практике УА часто реализуют в виде автомата с "жесткой" логикой (автоматы Мили и Мура). Алгоритмы управления операционным устройством, являющиеся исходными данными для синтеза схемы УА, задаются, как правило, в виде граф-схем, которые отличаются большим количеством характеристик. В последнее время все чаще для реализации схем управляющих автоматов применяются различные программируемые логические интегральные схемы (ПЛИС), которые обладают высокой стоимостью и сложностью. [1]

В настоящее время на практике возможна реализация сложных цифровых устройств на нескольких, или даже на одной большой интегральной схеме (БИС). Это связано с заметным за последние тридцать лет ростом плотности интеграции схем, что позволяет выпускать схемы, которые содержат на одном кристалле миллионы логических вентилей. БИС можно разделить на два класса: стандартные БИС и специализированные БИС. К первому классу относят микросхемы памяти, сигнальные процессоры и т.д. У второго класса выделяют несколько подклассов: полностью заказные, полузаказные и программируемые пользователем БИС.

В настоящее время широко применяются три класса ПЛИС: простые ПЛИС (зарубежный термин SPLD - simple programmable logic device), комплексные ПЛИС (зарубежный термин CPLD - complex programmable logic device) и программируемые пользователем вентильные матрицы (зарубежный термин FPGA - field programmable gate array). В классе SPLD выделяют два подкласса: программируемые логические матрицы (ПЛМ, зарубежный термин PLAs - programmable logic arrays) и программируемые матрицы логики (ПМЛ, зарубежный термин PALs – programmable array logics). SPLD состоят из двух матриц: матрицы "И" и матрицы "ИЛИ". В ПЛМ обе матрицы программируемые, а в ПМЛ - матрица "ИЛИ" фиксированная. CPLD состоят из блоков логических вентилей, объединенных программируемой коммутационной матрицей. Современные CPLD, как правило, являются электрически перепрограммируемыми и сохраняют логическую структуру после отключения питания. FPGA состоят из большого числа конфигурируемых логических блоков (зарубежный термин LUT) и трассировочных ресурсов, обеспечивающих их межсоединения. Из современных ведущих разработчиков микросхем CPLD и FPGA следует отметить фирмы Xilinx, Altera, Atmel, Lattice Semiconductor, Cypress Semiconductor. [2]

За последнее время наблюдаются две тенденции: одновременное увеличение сложности разрабатываемых цифровых устройств и повышение вычислительной мощности, гибкости аппаратных решений. Эти тенденции привели к появлению принципиально новых средств проектирования - систем автоматизированного проектирования (САПР). Сначала они имитировали ручную разработку аппаратных устройств инженером, далее с появлением микросхем класса FPGA и массовым выпуском ПЛИС появились первые языки описания аппаратуры и САПР с их поддержкой (80-е - 90-е годы XX века).

---

Цель и задачи работы

• анализ современного элементного базиса и существующих методов синтеза управляющих автоматов на ПЛУ для определения способов уменьшения стоимости логических схем УА;

• разработка четырехуровневой структуры УА и метода синтеза, ориентированного на уменьшение аппаратурных затрат в логической схеме;

• оценка сложности реализации разрабатываемой структуры и исследование с целью определения областей ее эффективного применения;

• разработка программного обеспечения, поддерживающего реализацию заданного метода синтеза управляющих автоматов.

---

Предполагаемая научная новизна

Научная новизна данной работы заключается в:

• исследовании заданной многоуровневой структуры управляющих автоматов и методов синтеза, направленных на уменьшение аппаратурных затрат в логической схеме путем комплексного применения замены логических переменных, максимального кодирования наборов микроопераций;

• определении закономерности изменения эффективности реализации разработанной структуры в зависимости от характеристик граф-схемы алгоритма;

• установлении области эффективного применения разрабатываемой структуры;

• разработке САПР, поддерживающей реализацию заданного метода синтеза управляющих автоматов.

---

Планируемая практическая ценность

Предполагаемая практическая ценность состоит в разработке и исследовании многоуровневой структуры управляющих автоматов с "жесткой" логикой в базисе ПЛУ, в логической схеме которой аппаратурные затраты уменьшены в сравнении с традиционными структурами. Разрабатываемое программное обеспечение можно будет использовать в образовательном процессе с целью обучения студентов по соответствующему курсу.

---

Обзор существующих разработок по теме

В наше время для описания логической структуры цифровых устройств, как правило, используются высокоуровневые языки описания оборудования (Hardware Description Languages - HDL). Наиболее распространенными среди них являются языки VHDL и Verilog. Однако в состав многих зарубежных САПР включены специальные инструменты, которые позволяют упростить разработку управляющих автоматов, т.к. непосредственная реализация управляющих автоматов на языках высокого уровня является трудоемким процессом. Так в состав САПР Active - HDL фирмы Aldec включен модуль FSM. Он обладает многофункциональным графическим интерфейсом для описания управляющих автоматов, однако форма записи управляющего автомата требует знания языка HDL, также в этом модуле отсутствует какая-либо оптимизация структуры получившегося автомата.

Моя работа посвящена актуальной задаче исследования методов синтеза структур управляющих автоматов с "жесткой" логикой, которые ориентированы на уменьшение стоимости логической схемы устройства и учитывают характерные особенности реализуемого алгоритма управления и элементного базиса. В качестве управляющего автомата с "жесткой" логикой выбран автомат Мили, а в качестве структуры управляющего автомата - четырехуровневая структура MPFY-автомата, которая в наше время не достаточно исследована.

Оптимизация схемы УА Мили может выполняться путем уменьшения как числа входов, так и числа выходов, а также совместно. Такой комплексный подход порождает многоуровневые структуры управляющих автоматов. В MPFY-автомате оптимизация выполняется путем замены входных переменных (MP), кодирования строк прямой структурной таблицы (таблицы переходов) (PF) и кодирования наборов микроопераций (FY). Структура управляющего MPFY-автомата показана на рисунке 1. M-подсхема реализуется на мультиплексорах, P-подсхема – на ПЛИС (PAL и CPLD), F-подсхема и Y-подсхема – на элементах памяти PROM.

Рисунок 1. Структура управляющего MPFY-автомата Мили (анимация, 5 кадров, 1.4 к/с, 6 повторений, 44 Кбайт)

Известны, однако, и другие методы оптимизации структуры автоматов на ПЛИС. Классификация этих методов [1] приведена на рисунке 2.

Рисунок 2. Классификация методов оптимизации автоматов

Однако в последнее время появление новых, более быстродействующих и содержащих большее количество логических ячеек на кристалле FPGA смещает приоритет при разработке устройств с минимизации аппаратурных затрат в полученной устройстве или максимизации быстродействия на обеспечение надежности работы полученного устройства при максимально коротком цикле разработки. Один из способов решения этой проблемы является использование средств, основанных на ранее разработанных средствах проектирования сложных систем для ПО, таких как управляемой моделями архитектуры (MDA – Model - Driven Architecture) и унифицированного языка моделирования (UML – Unified Modeling Language).

---

Текущие и планируемые результаты

На первом этапе работы над магистерской работой был исследован метод оптимизации четырехуровневой структуры УА, называемой в литературе MPFY-автомат. В процессе синтеза автомата использованы несколько методов оптимизации в комплексе: структурная редукция, гетерогенная реализация, алгоритмические преобразования. [4] Метод синтеза автомата Мили с MPFY-структурой включает следующие этапы:

• формирование таблицы замены переменных;

• оптимальное кодирование состояний автомата;

• максимальное кодирование микроопераций;

• синтез логической схемы устройства.

Далее была проведена оценка сложности реализации разрабатываемой структуры и исследование с целью определения областей ее эффективного применения. Методика исследования заключается в следующем:

• вывод формул для получения аналитических оценок площади заданной структуры УА;

• определение и исследование относительной сложности реализации заданной структуры.

Исследования проводились на основании формул для заданного управляющего автомата с использование программы EXCEL пакета MS Office. Были получены множество графиков, показывающих зависимость изменения стоимости и относительной сложности реализации заданной структуры от различных параметров граф-схемы алгоритма (числа вершин в ГСА, числа микроопераций, доли операторных вершин, коэффициента разветвленности и т.д.).

В дальнейшем предполагается разработка программного продукта, которое позволит синтезировать заданный автомат в базисе стандартных БИС для реализации граф-схем различных конфигураций. Данная САПР по результатам своей работы будет формировать VHDL-код программы, с помощью которого возможно будет дальнейшее исследование заданной структуры УА в среде Active-HDL. Входными данными для САПР будет являться текстовый файл с основными характеристиками исследуемой граф-схемы алгоритма. Структура разрабатываемого программного продукта приведена на рисунке 3.

Рисунок 3. Структура разрабатываемой САПР

Также в рамках данной магистерской работы предполагается на основе всех проделанных исследований сделать выводы о целесообразности применения заданной структуры УА для различных граф-схем алгоритмов, выявить недостатки и достоинства MPFY-автомата в сравнении с другими структурами УА Мили (двухуровневая, трехуровневая и т.д.).

---

Заключение и выводы

Результатом работы будет получение многоуровневой структуры управляющих автоматов с "жесткой" логикой в базисе ПЛУ, в логической схеме которой аппаратурные затраты уменьшены в сравнении с традиционными структурами. Разработанное программное обеспечение будет реализовывать заданный метод синтеза управляющих автоматов и генерацию кода на языке HDL. Программный код будет сгенерирован с учетом заданного алгоритма оптимизации управляющих автоматов. Входными данными для САПР будет являться текстовый файл с основными характеристиками исследуемой граф-схемы алгоритма.

---

Список источников

1. А.А. Баркалов Синтез устройств управления на программируемых логических устройствах. - Донецк. 2002.

2. В.В. Соловьев. Проектирование цифровых систем на основе программируемых логических интегральных схем. - Москва. 2001.

3. В.М. Карпов. Теория автоматов. СПб. Питер. 2002.

4. И.Я. Зеленева - "Методы синтеза многоуровневых структур управляющих автоматов на программируемых логических устройствах" - диссертационная работа.

5. Е.В. Малюк "Исследование четырехуровневой структуры управляющего автомата Мили в базисе стандартных БИС"

---

При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение: январь 2008 г. Полный текст работы и все материалы по теме могут быть получены у автора или руководителя после указанной даты.