ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 2, с. 41-49
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 004.312.4
КОМПЛЕКСНЫЙ МЕТОД МИНИМИЗАЦИИ КОНЕЧНЫХ АВТОМАТОВ ПРИ ИХ РЕАЛИЗАЦИИ НА ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМАХ* © 2014 г. В. В. Соловьев
Польша, Белосток, Белостокский технологический ун-т Поступила в редакцию 15.07.13 г., после доработки 28.10.13 г.
Рассмотрен комплексный метод минимизации конечных автоматов при их реализации на программируемых логических интегральных схемах, когда еще на этапе минимизации внутренних состояний учитываются такие критерии оптимизации, как стоимость реализации, потребляемая мощность и быстродействие. Предлагаемый метод позволяет также учитывать параметры элементной базы и используемый при синтезе метод кодирования внутренних состояний. Кроме того, метод позволяет минимизировать число переходов и входных переменных конечного автомата. Метод основан на последовательном склеивании двух внутренних состояний. Для этого на каждом шаге находится множество всех возможных пар состояний, допускающих склеивание, из которого для склеивания выбирается пара, которая в наибольшей степени удовлетворяет критериям оптимизации. Приводятся алгоритмы вычисления оценок критериев оптимизации, а также описываются особенности программной реализации метода.
Б01: 10.7868/80002338814020152
Введение. Широкое распространение цифровых систем во все сферы человеческой деятельности накладывает все более жесткие ограничения на параметры проектируемой аппаратуры. К таким параметрам на этапе логического синтеза относятся стоимость реализации, быстродействие и потребляемая мощность (энергопотребление). Причем в зависимости от конкретных условий в качестве главного оптимизирующего параметра может выступать каждый из них. Конечный автомат является математической моделью, которая широко используется при проектировании различных вычислительных структур, таких как последовательностные схемы, контроллеры, микропроцессорные схемы управления, цифровые телекоммуникационные системы, итеративные сети, телекоммуникационные протоколы и др. Поэтому актуальной является задача оптимизации конечных автоматов по указанным выше параметрам.
Традиционный подход при синтезе конечных автоматов включает следующие последовательно выполняемые этапы: минимизацию внутренних состояний, кодирование внутренних состояний, а также синтез комбинационной части конечного автомата. Последняя обычно представляется в виде системы булевых функций (СБФ), синтез которой выделяется в отдельную задачу и, как правило, не рассматривается при синтезе конечных автоматов. Таким образом, при традиционном подходе у разработчика имеется только два способа оптимизации конечного автомата: путем минимизации внутренних состояний и путем кодирования внутренних состояний.
Однако такой подход часто противоречит задачам оптимизации конечного автомата на этапе логического синтеза, поскольку как минимизация внутренних состояний, так и их кодирование абсолютно не учитывают особенности элементной базы и требования задач логического синтеза, в частности ограничения на параметры проектируемого устройства (по стоимости, быстродействию и энергопотреблению). На этапе синтеза комбинационной части конечного автомата решить указанные выше задачи оптимизации становится очень трудно или вообще невозможно. Часто даже точное решение задачи минимизации внутренних состояний не позволяет решить задачи оптимизации на этапе логического синтеза. Поэтому приходится прибегать к операции расщепления внутренних состояний [1], например, для ограничения числа аргументов функций [2],
* Работа выполнена при частичной финансовой поддержке Белостокского технического университета (Польша), грант № S/WI/1/2013.
выполнения необходимых условий реализации, приведения конечного автомата к определенному классу [3] и др.
Первые попытки совместить две проектные процедуры минимизации и кодирования внутренних состояний конечных автоматов были предприняты в [4—6]. В [4] задача рассматривается для асинхронных автоматов, при этом минимизируется длина кода состояний. Метод [5] работает только для небольших автоматов с числом состояний не более 10. В [6] представлена программа минимизации и кодирования состояний, позволяющая формировать коды состояний с неопределенными значениями.
В работах [7—13] при кодировании внутренних состояний решается задача минимизации занимаемой площади (стоимости реализации) и потребляемой мощности. В большинстве этих работ [8—11, 13] применяются генетические алгоритмы. В [7] задача решается для двухуровневых схем типа программируемых логических матриц (Programmable Logic Array — PLA). В [12] используется процедура расщепления состояний, причем отмечается, что для решения указанной задачи минимальное число внутренних состояний конечного автомата не требуется.
Задача одновременной минимизации площади и задержки сигналов на критическом пути рассматривается в работах [14—16]. В [14] предлагается структурная модель конечного автомата, названная MAR-моделью, которая состоит из конечного автомата и комбинационной схемы с триггерами в цепях обратной связи. В [15] для решения задачи используются коды с двумя (two-hot) и тремя (three-hot) единицами. В [16] применяется декомпозиция конечных автоматов.
В [17] рассматривается задача минимизации мощности и задержки для асинхронных конечных автоматов. Предлагается концепция полусинхронного конечного автомата, который работает на высокой частоте, потребляет мало мощности, а реализуется и тестируется как обычный синхронный автомат. В [18] с целью минимизации мощности, площади и задержки предлагается двухуровневая структурная модель, на первом уровне которой располагаются последователь-ностные блоки, а на втором — комбинационные блоки ограниченного размера. В [19] рассматривается традиционный подход к синтезу конечных автоматов, при котором последовательно выполняются минимизация и кодирование внутренних состояний, затем с применением программы ESPRESSO строятся дизъюнктивные нормальные формы (ДНФ) реализуемых функций, после чего вычисляются оценки стоимости, энергопотребления и быстродействия. Предлагается набор алгоритмов, с помощью которых можно выбирать лучшее кодирование внутренних состояний для минимизации указанных параметров.
Проведенный анализ известных работ показал, что отсутствуют работы, когда еще на этапе минимизации внутренних состояний конечного автомата одновременно выполняется минимизация занимаемой площади, потребляемой мощности и задержки сигналов на критическом пути. Методы, в которых утверждается, что одновременно учитывается несколько критериев оптимизации, фактически сводятся к традиционному подходу, на каждом этапе которого предлагается несколько алгоритмов. Отсутствуют также сведения об использовании генетических алгоритмов для решения указанной задачи.
В данной работе предлагается эвристический метод минимизации неполностью определенных конечных автоматов, который впервые позволяет уже на этапе минимизации внутренних состояний учитывать параметры элементной базы, используемый при синтезе метод кодирования внутренних состояний, а также оптимизировать такие параметры, как стоимость реализации, быстродействие и энергопотребление. Рассматриваемый подход ориентирован на реализацию конечных автоматов на программируемых логических интегральных схемах (ПЛИС). Поскольку в настоящее время наибольшее распространение получили два типа ПЛИС: CPLD (Complex Programmable Logic Device) с архитектурой двух программируемых матриц и FPGA (Field Programmable Gate Array) с архитектурой множества функциональных генераторов типа LUT (LUT — Look-Up Table), то оценки стоимости реализации и быстродействия приводятся для каждого типа ПЛИС. В микросхемах систем на одном программируемом кристалле (System on One Programmable Chip — SOPC) программируемая часть имеет архитектуру CPLD или FPGA, поэтому предлагаемый метод может быть также использован и при реализации конечных автоматов на SOPC.
1. Суть предлагаемого подхода. Пусть A = {а1, ..., aM} — множество внутренних состояний конечного автомата, X = {х1, ..., xL} — множество входных переменных, Y = {y1, ..., yN} — множество выходных переменных, D = {d1,..., dR} — множество функций возбуждения элементов памяти, где R — число элементов памяти (число разрядов кодов внутренних состояний), R е [intlog2M, M].
Предлагаемый подход основан на методе минимизации внутренних состояний неполностью определенных конечных автоматов [20]. Суть метода [20] заключается в последовательном скле-
ивании двух состояний. Для этого на каждом шаге находится множество G всех пар внутренних состояний конечного автомата, для которых выполняются условия склеивания. Затем для каждой пары состояний множества G выполняется пробное склеивание. Окончательно для склеивания выбирается такая пара (a, a), которая оставляет наибольшие возможности для склеивания других пар состояний множества G.
В отличие от [20], в предлагаемом подходе на каждом шаге из множества G выбирается такая пара (a,, a), которая в наибольшей степени удовлетворяет критериям оптимизации по стоимости, быстродействию и энергопотреблению, а также оставляет наибольшие возможности для склеивания других пар состояний множества G. Данный процесс повторяется до тех пор, пока удается склеить хотя бы одну пару состояний конечного автомата.
Пусть (as, a) — некоторая пара состояний множества G; Cst — оценка стоимости реализации конечного автомата при склеивании пары состояний (as, at); Tst — оценка задержки сигналов на критическом пути комбинационной части конечного автомата; Pst — оценка потребляемой мощности конечного автомата; Mst — оценка возможности минимизации других состояний. Тогда с учетом вышеизложенного минимизация конечных автоматов имеет следующий вид.
Алгоритм 1 (общий алгоритм минимизации конечных автоматов).
1. С помощью метода [20] определяется множество G пар состояний, которые допускают склеивание. Если G = 0, где 0 — пустое множеств, то (нет пары для склеивания) идти к п. 5.
2. Для каждой пары состояний (as, at) множества G
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.