Источник: http://www.chipinfo.ru/literature/chipnews/200303/4.html
Синтез на ПЛИС совмещенных моделей конечных автоматов
Рассматривается новый подход к проектированию конечных автоматов на ПЛИС, когда в рамках одной структурной модели, названной совмещенной, объединяется несколько различных моделей конечных автоматов. Это позволяет наиболее полно использовать архитектурные возможности ПЛИС и положительные качества каждой модели для реализации конечных автоматов. Экспериментальные исследования показали, что применение метода синтеза совмещTнных моделей, по сравнению с методами пакетов MAX+PLUSII фирмы Altera и WebPack фирмы Xilinx, позволяет снизить стоимость реализации, в среднем, в 2v3,5 раза, а для отдельных примеров ? в 9 раз, а также повысить быстродействие, в среднем, в 2 раза, а для отдельных примеров ? в 6 раз.
Введение
В предыдущих статьях данной серии были рассмотрены оригинальные структуры конечных автоматов, позволяющие использовать триггеры выходных макроячеек ПЛИС [1] (автоматы классов C и D) и входных буферов ПЛИС [2] (автоматы классов E и F) в качестве элементов памяти конечных автоматов. Автоматы классов C-F показали высокую эффективность как по стоимости реализации, так и по быстродействию. Однако на практике конечные автоматы классов C-F в "чистом" виде встречаются редко. Обычно синтезируемый конечный автомат частично обладает свойствами сразу нескольких классов автоматов C-F. Поэтому возникает необходимость совмещения в рамках одной модели нескольких классов автоматов с тем, чтобы максимально использовать положительные качества каждого класса C-F, а также архитектурные возможности ПЛИС для реализации конечных автоматов.
Совмещать в одной структуре несколько моделей различных классов конечных автоматов можно только в случае совпадения временных параметров выходных сигналов каждой модели. В противном случае, может сложиться ситуация, когда значения выходных сигналов, формируемых в одном и том же состоянии конечного автомата, на выходе схемы будут появляться в различных тактах автоматного времени. Из анализа временного функционирования автоматов классов A-F [3] следует, что допустимы следующие четыре совмещTнные модели конечных автоматов: ADE, AD, AE и BF. На основании этих четырTх совмещTнных моделей путTм установки регистров на входы и/или выходы, а также защTлок на входы, можно построить ещT 20 совмещTнных моделей конечных автоматов, допускающих эффективную реализацию на ПЛИС.
Структуры совмещенных моделей конечных автоматов
Структуры совмещTнных моделей показаны на рис. 1. Здесь комбинационная схема CL реализует выходные функции и функции возбуждения элементов памяти; регистр RGEF служит для хранения кодов состояний, определяемых входными наборами (автоматы классов E и F); регистр RGD - для хранения кодов состояний, определяемых выходными наборами (автомат класса D), и регистр RGAB - для хранения кодов состояний автоматов классов A и B. В совмещTнных моделях содержимое входного регистра RGEF определяется значениями входных переменных множества X = {x1,...,xL}, содержимое выходного регистра RGD определяется значениями выходных переменных множества Y = {y1,...,yN} и содержимое внутреннего регистра RGAB определяется значениями функций переходов множества D = {d1,...,dR}. Коды внутренних состояний конечного автомата определяются значениями переменных множеств G = = {g1,...,gL}, Z = {z1,...,zN} и E = {e1,...,eR}, формируемых на выходах регистров RGEF, RGD и RGAB, соответственно.
Рисунок 1. Структуры совмещенных моделей конечных автоматов: ADE (а), AD (б), AE и BF (в)
Отметим, что в совмещTнных моделях конечных автоматов регистр RGEF реализуется входными буферами, регистр RGD - выходными макроячейками, а регистр RGAB - скрытыми макроячейками ПЛИС.
Кодирование внутренних состояний совмещенных моделей конечных автоматов
Вначале рассмотрим кодирование внутренних состояний конечных автоматов для совмещTнной модели ADE, а затем уточним этот метод для моделей AD, AE и BF.
Суть кодирования заключается в том, чтобы сделать все внутренние состояния различимыми между собой, то есть все коды внутренних состояний конечного автомата должны быть взаимно ортогональны. Входные и выходные наборы конечного автомата, определяемые значениями переменных множеств G = {g1,...,gL} и Z = {z1,...,zN}, частично решают эту задачу. Дальнейшее решение заключается во введении минимального числа R дополнительных переменных e1,...,eR множества E и кодировании отдельных групп состояний двоичными кодами.
Пусть, как и прежде [1,2], конечный автомат задан таблицей переходов, столбцы которой имеют обозначения am, aы, X(am,aы) и Y(am,aы). Для решения задачи кодирования внутренних состояний совмещTнной модели ADE строится троичная матрица W. Строки матрицы соответствуют внутренним состояниям конечного автомата, а столбцы - переменным множеств G и Z. На пересечении строки, соответствующей некоторому состоянию ai, ai € A, и столбца, соответствующего переменной gj, gj € G, ставится единица, если входная переменная xj входит в условие X(ai) в прямом значении, ноль - в инверсном, и неопределTнное значение (дефис), если переменная xj не входит в условие X(ai), где X(ai) - условие перехода в состояние ai. Значение X(ai) определяется следующим образом: если все переходы в состояние ai, ai € A, осуществляются под воздействием одного и того же входного набора X(am,ai), то полагается X(ai) := := X(am,ai), иначе полагается X(ai) := пустое множество. На пересечении строк, соответствующих состоянию ai, ai € A, и столбца, соответствующего переменной zj, zj € Z, ставится единица, если yj € Y(ai), и ноль в противном случае, где Y(ai) - подмножество выходных переменных, принимающих единичные значения на переходах в состояние ai. Значение Y(ai) определяется следующим образом: если на всех переходах в состояние ai, ai € A, формируется один и тот же выходной набор Y(am,ai), то полагается Y(ai) := Y(am,ai), иначе полагается Y(ai) := пустое множество. Теперь задачу кодирова ния внутренних состояний совмещенной модели конечного автомата можно сформулировать следующим образом.
Задача 1. Ввести минимальное число R дополнительных переменных e1,...,eR и закодировать строки матрицы W таким образом, чтобы все строки матрицы W были взаимно ортогональны.
Для решения задачи 1 строится граф H ортогональности строк матрицы W. Вершины графа H соответствуют строкам матрицы W (то есть внутренним состояниям конечного автомата). Две вершины i и j графа H соединяются ребром, если строки i и j матрицы W ортогональны между собой. Теперь задача 1 сводится к нахождению в графе H минимального числа T полных подграфов H1,...,HT, вершины которых не пересекаются, и приписывании этим подграфам двоичных кодов, определяемых значениями переменных e1,...,eR.
На основании вышеизложенного для решения задачи 1 может быть предложен следующий алгоритм.
Метод синтеза совмещенных моделей конечных автоматов
Метод синтеза совмещTнных моделей конечных автоматов рассмотрим на примере модели ADE, а затем уточним этот метод для моделей AD, AE и BF. Использование совмещенной модели автоматов преследует две основные цели:
минимизацию числа R дополнительных элементов памяти;
упрощение функций переходов и выходов, то есть упрощение комбинационной части конечного автомата.
Обе цели достигаются путTм широкого использования моделей автоматов классов D и E, а также операции расщепления состояний. В предлагаемом ниже алгоритме синтеза расщепление состояний прекращается, как только это приводит к увеличению значения R, а в качестве окончательного принимается решение, которое последний раз вызвало уменьшение R.
Пусть A - множество всех внутренних состояний конечного автомата. Определим множество AE, AE Н A, состояний автомата класса E, то есть множество состояний, коды которых определяются входными наборами. Обозначим через U(ai) множество всех условий переходов в состояние ai, ai € A:
U(ai) = {X(am,ai) | am € B(ai)}, (1)
где B(ai) - множество состояний, переходы из которых оканчиваются в состоянии ai.
Состояние ai, ai € A, является состоянием автомата класса E, то есть ai € AE, если выполняются условия:
|U(ai)| = 1 и (2)
U(ai) U(aj) = пустое множество (3)
при i j для всех aj € A.
Выполнение (2) обеспечивает, что все переходы в состояние ai осуществляются по одному и тому же условию перехода, а выполнение (3) обеспечивает, что условия переходов в состояние ai не вызывают переходов в другие состояния автомата.
Удовлетворение условиям (2) выполняется путTм расщепления состояний. Удовлетворение условиям (3) осуществляется путTм введения дополнительных переменных обратных связей и соответствующих им элементов памяти для различия кодов внутренних состояний автомата.
Пусть UE(ai) - множество условий переходов в состояние ai, ai € A, которые не встречаются на переходах в другие состояния, то есть для которых выполняется условие (3), UE(ai) U(ai). Обозначим через A*E множество состояний, для которых нарушено условие (2), то есть множество состояний, которые можно расщеплять с целью получения состояний автомата класса E.
Пусть V(ai) - множество наборов выходных переменных, формируемых на переходах в состояние ai, ai € A:
V(ai) = {Y(am,ai) | am € B(ai)}. (4)
Состояние ai, ai € A, является состоянием автомата класса D, то есть ai € AD, если выполняются условия:
|V(ai)| = 1 и (5)
V(ai) V(aj) = пустое множество (6)
при i j для всех aj € A.
Выполнение условия (5) обеспечивает, что на всех переходах в состояние ai формируется один и тот же выходной набор, а выполнение (6) обеспечивает, что выходной набор V(ai) не встречается на переходах в другие состояния конечного автомата.
Пусть VD(ai) - множество наборов выходных переменных, формируемых на переходах в состояние ai, ai € A, которые не встречаются на переходах в другие состояния, то есть VD(ai) - подмножество множества V(ai), VD(ai) V(ai), для которого выполняется условие (6). Пусть также A*D - множество состояний, для которых нарушено условие (5), то есть множество состояний, которые можно расщеплять с целью получения состояний автомата класса D.
Определим стоимость S(ai) расщепления состояния ai как число строк, на которое увеличивается таблица переходов в результате расщепления состояния ai, ai € A*D A*E:
S(ai) = |V(ai) v 1|·|P(ai)|, если ai € A*,D, (7)
S(ai) = |U(ai) v 1|·|P(ai)|, если ai € A*E,
где P(ai) - множество переходов из состояния ai. В процессе синтеза конкретное значение S(ai) выбирается в зависимости от того, каким образом производится расщепление: по выходным (ai € A*D) или по входным (ai € A*E) наборам.
На основании вышеизложенного, обобщTнный алгоритм синтеза совмещенной модели конечных автоматов ADE можно представить следующим образом.
Алгоритм 2
Полагается R* := 1000.
Строится матрица кодирования внутренних состояний W, решается задача 1, определяется значение R.
Если R > R*, то выполняется переход к пункту 7. Иначе, если R < R*, то полагается R* := R и запоминаются результаты синтеза (таблица переходов и коды состояний).
Определяются множества V(ai), VD(ai), U(ai) и UE(ai), ai € A, а также множества A*D и A*E. Если A*D И A*E = пустое множество,то выполняется переход к пункту 7, иначе - к пункту 5.
Для всех состояний ai, ai € A*D A*E, определяется цена H(ai), H(ai) = max(|VD(ai)|, |UE(ai)|), эффективности использования автоматов классов D или E в случае расщепления состояния ai. Для расщепления выбирается состояние ai, ai € A*D A*E, по следующим критериям: 1) H(ai) = max, 2) S(ai) = min. Первый критерий обеспечивает наибольшую эффективность использования автоматов классов D или E, а второй - минимальное увеличение строк таблицы переходов.
Выполняется расщепление состояния ai, выбранного в пункте 5. Если |VD(ai)| |UE(ai)|, то расщепление производится во выходным наборам множества V(ai), иначе - по входным наборам множества U(ai).
Выполняется переход к пункту 2.
В качестве результата синтеза принимается решение, запомненное в пункте 3.
Строится структурная таблица переходов конечного автомата, определяются логические уравнения реализуемых функций.
Конец.
Отметим, что в начале выполнения алгоритма 2 значение R* принимается заведомо большим, чем необходимо, поэтому в пункте 3 по крайней мере один раз выполнится запоминание результатов синтеза.
Пример. Рассмотрим работу алгоритма 2 на примере синтеза совмещTнной модели конечного автомата Мили, таблица переходов которого приведена в табл. 1. Решение задачи 1 приводит к определению значения R* = 2. Множества V(ai), VD(ai), U(ai) и UE(ai) для данного примера приведены в табл. 2, на основании которых определяются следующие множества: AD = {a4}; A*D = {a3,a5}; AE = {a1,a2,a3} и A*E = {a4,a5}. Для расщепления выбирается состояние a5, поскольку |VD(a5)| = |UE(a5)| = max = 3. Результаты расщепления состояния a5 по выходным наборам множества V(a5) приведены в табл. 3. Матрица W, построенная для решения задачи 1, приведена в табл. 4 (первые восемь столбцов). Граф H ортогональности строк матрицы W показан на рис. 2.
Таблица 1. Таблица переходов исходного конечного автомата
Таблица 2. Множества V(ai), VD(ai), U(ai) и UE(ai)
Таблица 3. Таблица переходов после расщепления состояния a5
Таблица 4. Матрица W для кодирования внутренних состояний
Рисунок 2. Граф H ортогональности строк матрицы W
Вначале из графа H удаляется вершина a2, связанная со всеми остальными вершинами графа. Затем в графе H последовательно выделяются два полных подграфа H1 и H2, для которых A1 = {a1, a4, a5?, a5?, a5?} и A2 = {a3}. Поскольку два подграфа можно закодировать одной двоичной переменной, то имеем R = 1. Дальнейшее расщепление состояний не приводит к уменьшению R, поэтому полученное решение принимается за окончательное. В матрицу W добавляется один столбец, соответствующий дополнительной переменной e1. Строки таблицы W, соответствующие подграфу H1, кодируются нулевым значением переменной e1, а подграфу H2 - единичным. На основании содержимого строк матрицы W определяются следующие значения кодов внутренних состояний автомата:
