Распродажа

Электронные компоненты со склада по низким ценам, подробнее >>>

Содержание ChipNews

2003: 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
2002: 
1, 5, 6, 7, 8, 9
2001: 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
2000: 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1999: 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Новости электроники

В 14 раз выросло количество россиян на MediaTek Labs ? проекте по созданию устройств "интернета вещей" и "носимых гаджетов"

Сравнив статистику посещения сайта за два месяца (ноябрь и декабрь 2014 года), в MediaTek выяснили, что число посетителей ресурса из России увеличилось в 10 раз, а из Украины ? в 12. Таким образом, доля русскоговорящих разработчиков с аккаунтами на labs.mediatek.com превысила одну десятую от общего количества зарегистрированных на MediaTek Labs пользователей.

Новое поколение Джобсов или как MediaTek создал свой маленький "Кикстартер"

Амбициозная цель компании MediaTek - сформировать сообщество разработчиков гаджетов из специалистов по всему миру и помочь им реализовать свои идеи в готовые прототипы. Уже сейчас для этого есть все возможности, от мини-сообществ, в которых можно посмотреть чужие проекты до прямых контактов с настоящими производителями электроники. Начать проектировать гаджеты может любой талантливый разработчик - порог входа очень низкий.

Семинар и тренинг "ФеST-TIваль инноваций: MAXIMум решений!" (14-15.10.2013, Новосибирск)

Компания Компэл, приглашает вас принять участие в семинаре и тренинге ?ФеST-TIваль инноваций: MAXIMум решений!?, который пройдет 14 и 15 октября в Новосибирске.

Мне нравится

Комментарии

дима пишет в теме Параметры биполярных транзисторов серии КТ827:

люди куплю транзистар кт 827А 0688759652

тамара плохова пишет в теме Журнал Радио 9 номер 1971 год. :

как молоды мы были и как быстро пробежали годы кулотино самое счастливое мое время

Ивашка пишет в теме Параметры отечественных излучающих диодов ИК диапазона:

Светодиод - это диод который излучает свет. А если диод имеет ИК излучение, то это ИК диод, а не "ИК светодиод" и "Светодиод инфракрасный", как указано на сайте.

Владимир пишет в теме 2Т963А-2 (RUS) со склада в Москве. Транзистор биполярный отечественный:

Подскажите 2т963а-2 гарантийный срок

Владимир II пишет... пишет в теме Параметры биполярных транзисторов серии КТ372:

Спасибо!

Синтез на ПЛИС совмещенных моделей конечных автоматов.

В. Соловьев, А. Климович

Синтез на ПЛИС совмещенных моделей конечных автоматов

Рассматривается новый подход к проектированию конечных автоматов на ПЛИС, когда в рамках одной структурной модели, названной совмещенной, объединяется несколько различных моделей конечных автоматов. Это позволяет наиболее полно использовать архитектурные возможности ПЛИС и положительные качества каждой модели для реализации конечных автоматов. Экспериментальные исследования показали, что применение метода синтеза совмещ╦нных моделей, по сравнению с методами пакетов MAX+PLUSII фирмы Altera и WebPack фирмы Xilinx, позволяет снизить стоимость реализации, в среднем, в 2√3,5 раза, а для отдельных примеров ≈ в 9 раз, а также повысить быстродействие, в среднем, в 2 раза, а для отдельных примеров ≈ в 6 раз.

Введение

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

Совмещать в одной структуре несколько моделей различных классов конечных автоматов можно только в случае совпадения временных параметров выходных сигналов каждой модели. В противном случае, может сложиться ситуация, когда значения выходных сигналов, формируемых в одном и том же состоянии конечного автомата, на выходе схемы будут появляться в различных тактах автоматного времени. Из анализа временного функционирования автоматов классов A-F [3] следует, что допустимы следующие четыре совмещ╦нные модели конечных автоматов: ADE, AD, AE и BF. На основании этих четыр╦х совмещ╦нных моделей пут╦м установки регистров на входы и/или выходы, а также защ╦лок на входы, можно построить ещ╦ 20 совмещ╦нных моделей конечных автоматов, допускающих эффективную реализацию на ПЛИС.

Структуры совмещенных моделей конечных автоматов

Структуры совмещ╦нных моделей показаны на рис. 1. Здесь комбинационная схема CL реализует выходные функции и функции возбуждения элементов памяти; регистр RGEF служит для хранения кодов состояний, определяемых входными наборами (автоматы классов E и F); регистр RGD - для хранения кодов состояний, определяемых выходными наборами (автомат класса D), и регистр RGAB - для хранения кодов состояний автоматов классов A и B. В совмещ╦нных моделях содержимое входного регистра 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 (в)

Структуры совмещенных моделей конечных автоматов: ADE (а), AD (б), AE и BF (в).

Отметим, что в совмещ╦нных моделях конечных автоматов регистр RGEF реализуется входными буферами, регистр RGD - выходными макроячейками, а регистр RGAB - скрытыми макроячейками ПЛИС.

Кодирование внутренних состояний совмещенных моделей конечных автоматов

Вначале рассмотрим кодирование внутренних состояний конечных автоматов для совмещ╦нной модели ADE, а затем уточним этот метод для моделей AD, AE и BF.

Суть кодирования заключается в том, чтобы сделать все внутренние состояния различимыми между собой, то есть все коды внутренних состояний конечного автомата должны быть взаимно ортогональны. Входные и выходные наборы конечного автомата, определяемые значениями переменных множеств G = {g1,...,gL} и Z = {z1,...,zN}, частично решают эту задачу. Дальнейшее решение заключается во введении минимального числа R дополнительных переменных e1,...,eR множества E и кодировании отдельных групп состояний двоичными кодами.

Пусть, как и прежде [1,2], конечный автомат задан таблицей переходов, столбцы которой имеют обозначения am, aы, X(am,aы) и Y(am,aы). Для решения задачи кодирования внутренних состояний совмещ╦нной модели ADE строится троичная матрица W. Строки матрицы соответствуют внутренним состояниям конечного автомата, а столбцы - переменным множеств G и Z. На пересечении строки, соответствующей некоторому состоянию ai, ai € A, и столбца, соответствующего переменной gj, gj € G, ставится единица, если входная переменная xj входит в условие X(ai) в прямом значении, ноль - в инверсном, и неопредел╦нное значение (дефис), если переменная 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 может быть предложен следующий алгоритм.

Алгоритм 1

  1. Строится граф H ортогональности строк матрицы W.
  2. Из графа H удаляются вершины, связные со всеми другими вершинами графа (соответствующие им стоки матрицы W ортогональны всем другим строкам).
    Полагается t := 0.
  3. Полагается t := t + 1. В графе H отыскивается максимальный полный подграф Ht.
  4. Из графа H удаляются вершины подграфа Ht. Если множество вершин графа H пусто, то выполняется переход к пункту 5, иначе - к пункту 3.
  5. Определяется число R дополнительных переменных e1,...,eR, R = intlog2T, где T - число полных подграфов.
  6. Для каждого подграфа Ht определяется цена Ct следующим образом:

    где At - множество внутренних состояний конечного автомата, соответствующих вершинам подграфа Ht, t = 1,T; C(ai) - множество переходов, которые оканчиваются в состоянии ai, ai € A.

  7. Каждому подграфу Ht, t = 1,T, ставится в соответствие двоичный код, определяемый значениями переменных e1,...,eR, прич╦м коды с минимальным числом единиц в первую очередь приписываются подграфам, для которых Ct = min.
  8. В матрицу W добавляются столбцы, соответствующие переменным e1,...,eR. Содержимое этих столбцов определяется кодами соответствующих подграфов.
  9. Определяются коды внутренних состояний конечного автомата. Каждый код K(ai) внутреннего состояния ai, ai € A, определяется содержимым строки i матрицы W. Если на пересечении строки i и столбца j находится единица, то переменная, соответствующая столбцу j, входит в код K(ai) состояния ai в прямом значении, ноль - в инверсном, дефис - переменная не входит в код K(ai) состояния ai.
  10. Конец.

Рассмотренный метод без всяких изменений может быть примен╦н при кодировании внутренних состояний конечных автоматов моделей AE и BF. При кодировании внутренних состояний конечных автоматов совмещ╦нной модели AD троичная матрица W будет содержать столбцы, соответствующие только переменным множества Е.

Метод синтеза совмещенных моделей конечных автоматов

Метод синтеза совмещ╦нных моделей конечных автоматов рассмотрим на примере модели ADE, а затем уточним этот метод для моделей AD, AE и BF. Использование совмещенной модели автоматов преследует две основные цели:

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

Обе цели достигаются пут╦м широкого использования моделей автоматов классов 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) выполняется пут╦м расщепления состояний. Удовлетворение условиям (3) осуществляется пут╦м введения дополнительных переменных обратных связей и соответствующих им элементов памяти для различия кодов внутренних состояний автомата.

Пусть 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) √ 1|·|P(ai)|, если ai € A*,D, (7)
S(ai) = |U(ai) √ 1|·|P(ai)|, если ai € A*E,

где P(ai) - множество переходов из состояния ai. В процессе синтеза конкретное значение S(ai) выбирается в зависимости от того, каким образом производится расщепление: по выходным (ai € A*D) или по входным (ai € A*E) наборам.

На основании вышеизложенного, обобщ╦нный алгоритм синтеза совмещенной модели конечных автоматов ADE можно представить следующим образом.

Алгоритм 2

  1. Полагается R* := 1000.
  2. Строится матрица кодирования внутренних состояний W, решается задача 1, определяется значение R.
  3. Если R > R*, то выполняется переход к пункту 7. Иначе, если R < R*, то полагается R* := R и запоминаются результаты синтеза (таблица переходов и коды состояний).
  4. Определяются множества V(ai), VD(ai), U(ai) и UE(ai), ai € A, а также множества A*D и A*E. Если A*D И A*E = пустое множество,то выполняется переход к пункту 7, иначе - к пункту 5.
  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, а второй - минимальное увеличение строк таблицы переходов.
  6. Выполняется расщепление состояния ai, выбранного в пункте 5. Если |VD(ai)| |UE(ai)|, то расщепление производится во выходным наборам множества V(ai), иначе - по входным наборам множества U(ai).
    Выполняется переход к пункту 2.
  7. В качестве результата синтеза принимается решение, запомненное в пункте 3.
  8. Строится структурная таблица переходов конечного автомата, определяются логические уравнения реализуемых функций.
  9. Конец.

Отметим, что в начале выполнения алгоритма 2 значение R* принимается заведомо большим, чем необходимо, поэтому в пункте 3 по крайней мере один раз выполнится запоминание результатов синтеза.

Пример. Рассмотрим работу алгоритма 2 на примере синтеза совмещ╦нной модели конечного автомата Мили, таблица переходов которого приведена в табл. 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. Таблица переходов исходного конечного автомата

am X(am,as) as Y(am,as)
a1 x1
x1
a2
a3
y3,y4
y3,y4
a2 x1 x2
x1 x2
x1
a5
a4
a3
y4
y3
a3 x3
x3
a4
a5
y3
y4
a4 x4
x4
a5
a1
y2
a5 x4
x4
5
a1
y1

Таблица 2. Множества V(ai), VD(ai), U(ai) и UE(ai)

ai V(ai) VD(ai) U(ai) UE(ai)
a1 {Пустое множество} Пустое множество {¯x4} {¯x4}
a2 {y3,y4} Пустое множество {x1} {x1}
a3 {y3,y4},{Пустое множество} Пустое множество {¯x1} {¯x1}
a4 {y3} {y3} {x1,x2},{x3} {x1,¯x2},{x3}
a5 {y1},{y2},{y4} {y1},{y2},{y4} {x1,x2},{x3},{x4} {x1,x2},{¯x3},{x4}

Таблица 3. Таблица переходов после расщепления состояния a5

am X(am,as) as Y(am,as)
a1 x1
¯x1
a2
a3
y3,y4
y3,y4
a2 x1 x2
x1 ¯x2
¯x1
a51
a4
a3
y4
y3
a3 x3
¯x3
a4
a51
y3
y4
a4 x4
¯x4
a5²
a1
Y2
a5¹ x4
¯x4
a5³
a1
Y1
a x4
¯x4
a5³
a1
Y1
a5³ x4
¯x4
a5³
a1
Y1

Таблица 4. Матрица W для кодирования внутренних состояний

  g1 g2 g3 g4 z1 z2 z3 z4 e1
a1 - - - 0 0 0 0 0 0
a2 1 - - - 0 0 1 1 -
a3 0 - - - - - - - 1
a4 - - - - 0 0 1 0 0
a5¹ - - - - 0 0 0 1 0
a5² - - - 1 0 1 0 0 0
a5³ - - - 1 1 0 0 0 0

Рисунок 2. Граф H ортогональности строк матрицы W

Граф 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 определяются следующие значения кодов внутренних состояний автомата:

K(a1) = ¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1;
K(a2) = g1╥¯z1╥¯z2╥z3╥z4;
K(a3) = ¯g1╥e1;
K(a4) = ¯z1╥¯z2╥z3╥¯z4╥¯e1;
K(a) = ¯z1╥¯z2╥¯z3╥z4╥¯e1;
K(a5²) = g4╥¯z1╥z2╥¯z3╥¯z4╥¯e1;
K(a5³) = g4╥z1╥¯z2╥¯z3╥¯z4╥¯e1.

Структурная таблица переходов представлена в табл. 5, на основании которой составляются следующие логические уравнения реализуемых функций:

d1 = ¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1╥¯x1 + g1╥¯z1╥¯z2╥¯z3╥z4╥¯x1;
y1 = ¯z1╥¯z2╥¯z3╥z4╥¯e1╥x4 + g4╥¯z1╥z2╥¯z3╥¯z4╥¯e1╥x4 + + g4╥z1╥¯z2╥¯z3╥¯z4╥¯e1╥x4;
y2 = ¯z1╥¯z2╥z3╥¯z4╥¯e1╥x4;
y3 = ¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1 + g1╥¯z1╥¯z2╥z3╥z4╥x1╥¯x2 + + ¯g1╥e1╥x3;
y4 = ¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1 + g1╥¯z1╥­z2╥z3╥z4╥x1╥x2 + + ¯g1╥e1╥¯x3.

Таблица 5. Структурная таблица переходов

am K(am) X(am,as) as K(as) Y(am,as) D(am,as)
a1 ¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1 x1
¯x1
a2 g1╥¯z1╥¯z2╥z3╥z4 Y3, Y4
Y3, Y4
-
d1
a2 g1╥¯z1╥¯z2╥z3╥z4 x1 x2
x1 ¯x2
¯x1
a5¹
a4
a3
¯z1╥¯z2╥¯z3╥z4╥¯e1
¯z1╥¯z2╥z3╥¯z4╥¯e1
¯g1╥e1
Y4
Y3
-
-
-
d1
a3 ¯g1╥e1 x3
¯x3
a4
a5¹
¯z1╥¯z2╥z3╥¯z4╥¯e1
¯z1╥¯z2╥¯z3╥z4╥¯e1
Y3
Y4
-
-
a4 ¯z1╥¯z2╥z3╥¯z4╥¯e1 x4
¯x4
a5²
a1
g4╥¯z1╥z2╥¯z3╥¯z4╥¯e1
¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1
Y2
-
-
-
a5¹ ¯z1╥¯z2╥¯z3╥z4╥¯e1 x4
¯x4
a5³
a1
g4╥z1╥¯z2╥¯z3╥¯z4╥¯e1
¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1
Y1
-
-
-
a5² g4╥¯z1╥z2╥¯z3╥¯z4╥¯e1 x4
¯x4
a5³
a1
g4╥z1╥¯z2╥¯z3╥¯z4╥¯e1
¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1
Y1
-
-
-
a5³ g4╥z1╥¯z2╥¯z3╥¯z4╥¯e1 x4
¯x4
a5³
a1
g4╥z1╥¯z2╥¯z3╥¯z4╥¯e1
¯g4╥¯z1╥¯z2╥¯z3╥¯z4╥¯e1
Y1
-
-
-

Окончательная реализация совмещ╦нной модели ADE показана на рис. 3.

Рисунок 3. Реализация совмещ╦нной модели ADE

Реализация совмещ╦нной модели ADE.

Если для всех ai, ai € A, положить U(ai) := пустое множество, то алгоритм 2 без всяких изменений может быть примен╦н для синтеза конечных автоматов совмещенной модели AD. Если для всех ai, ai € A, положить V(ai) := пустое множество, то алгоритм 2 также без всяких изменений может быть примен╦н для синтеза совмещ╦нной модели AE.

Для автоматов типа Мура возможно построение только одной совмещ╦нной модели BF. Дело в том, что временные параметры выходных сигналов автомата класса C существенно отличаются от временных параметров выходных сигналов автоматов классов B и F [3]. Поэтому, в общем случае, автомат класса C нельзя совмещать в рамках одной модели с автоматами классов B и F.

Метод синтеза совмещ╦нной модели BF полностью совпадает с рассмотренным выше методом синтеза совмещ╦нной модели AE. Отличие заключается только в том, что вместо исходного автомата типа Мили рассматривается автомат типа Мура. Переход от автомата типа Мили к автомату типа Мура можно выполнить с помощью алгоритма 2 работы [2].

Результаты экспериментальных исследований метода синтеза совмещенных моделей конечных автоматов

Метод синтеза совмещ╦нных моделей реализован программно в пакете ZUBR. Эффективность метода сравнивалась с методами синтеза пакета MAX+PLUSII фирмы Altera для семейств MAX 9000 и FLEX 10K, а также методами синтеза пакета WebPack фирмы Xilinx для семейств XC 9500 и VIRTEX2. В качестве исходных данных использовались эталонные примеры конечных автоматов, разработанные в центре MCNC (Microelectronics Center of North Carolina) [4].

Результаты сравнения стоимости реализации конечных автоматов, синтезированных с помощью метода синтеза совмещ╦нных моделей и методов пакета MAX+PLUSII для семейств MAX 9000 и FLEX 10K представлены соответственно в табл. 6 и 7, где Name - имя эталонного примера; L, N, M и P - число входов, выходов, внутренних состояний и переходов конечного автомата, соответственно; C1 - число используемых макроячеек ПЛИС при синтезе конечного автомата с помощью метода синтеза пакета MAX+PLUSII для семейства MAX 9000; C2, C3 и C4 - число используемых макроячеек ПЛИС семейства MAX 9000 при синтезе конечного автомата с помощью метода синтеза совмещ╦нной модели ADE, AD и AE, соответственно; C5, C6, C7 и C8 - то же, но для семейства FLEX 10K.

Таблица 6. Сравнение метода синтеза совмещенных моделей конечных автоматов с методами пакета MAX+PULSII для семейства MAX 9000

Name L N M P C1 C2 C1/C2 C3 C1/C3 C4 C1/C4
beecount 3 4 7 28 9 6 1,5 6 1 6 1
dk14 3 5 7 56 12 11 1,1 10 1,1 12 1
ex3 2 2 10 36 8 4 2 4 2 4 2
ex5 2 2 9 32 11 4 2,75 4 2,75 4 2,75
ex7 2 2 10 36 10 4 2,5 4 2,5 4 2,5
keyb 7 2 19 170 27 13 2,08 17 1,59 17 1,59
lion9 2 1 9 25 7 3 2,33 3 2,33 3 2,33
s1 8 6 20 107 48 11 4,36 9 5,33 48 1
s27 4 1 6 34 4 3 1,33 3 1,33 4 1,33
train11 2 1 11 25 7 2 3,5 3 2,33 3 2,33
train4 2 1 4 14 3 2 1,5 3 1 3 1
            24,95   23,26   18,83
mid             2,27   2,11   1,71

Таблица 7. Сравнение метода синтеза совмещенных моделей конечных автоматов с методами пакета MAX+PULSII для семейства FLEX 10K

Name C5 C6 C5/C6 C7 C5/C7 C8 C5/C8
beecount 37 9 4,11 10 3,7 10 3,7
dk14 75 39 1,92 39 1,92 45 1,66
ex3 22 9 2,44 8 2,75 10 2,2
ex5 23 8 2,88 4 5,75 6 3,83
ex7 20 4 5 4 5 4 5
keyb 102 72 1,42 1,04 1,04 83 1,23
lion9 23 5 4,6 3 7,66 3 7,66
s1 128 35 3,66 33 3,88 128 1
s27 40 9 4,44 9 4,44 20 2
train11 24 6 4 6 4 3 8
train4 6 4 1,5 4 1,5 3 2
    35,97   41,64   38,28
mid     3,27   3,79   3,48

Анализ табл. 6 и 7 показывает, что использование совмещ╦нных моделей конечных автоматов и соответствующих методов синтеза позволяет уменьшить число задействуемых макроячеек ПЛИС, в среднем, в 1,71√3,79 раза, а для отдельных примеров - в 8 раз.

В табл. 8 приведены результаты сравнения быстродействия синтезированных конечных автоматов для моделей AD и AE, где D1 - максимальная задержка в наносекундах прохождения сигналов со входа на выход схемы при использовании пакета WebPack для семейства XC 9500; D2 и D3 - то же, но при использовании метода синтеза совмещ╦нных моделей AD и AE, соответ ственно. Анализ табл. 8 показывает, что метод синтеза совмещ╦нных моделей позволяет повысить быстродействие конечных автоматов, в среднем, в 2,14 раза, а для отдельных примеров - почти в 6 раз.

Таблица 8. Сравнение быстродействия конечных автоматов для семейства XC 9500

Name D1 D2 D1/C2 C3 C1/C3
beecount 23,9 5 4,78 5 4,78
dk14 22,6 18,6 1,22 24,1 0,94
ex3 24 11,8 2,03 8,4 2,86
ex5 15,8 11,8 1,34 18,6 0,85
ex7 15,8 8,4 1,88 8,4 1,88
keyb 24,7 20 1,24 20 1,24
lion9 11 5 2,2 5 2,2
s1 20,6 26,8 0,77 29,9 0,69
s27 10,3 8,4 1,23 18,6 0,55
train11 29,9 5 5,98 5 5,98
train4 7,1 8,4 0,85 8,4 0,85
    23,52   22,82
mid     2,14   2,07

Литература

  1. Соловьев В.В. Использование выходных макроячеек ПЛИС в качестве элементов памяти конечных автоматов // Chip News. 2003. ╧ 1. С. 17√23.
  2. Соловьев В.В., Климович А. Использование входных буферов ПЛИС в качестве элементов памяти конечных автоматов // Chip News. 2003. ╧ 2. С. 30√34.
  3. Соловьев В.В. Структурные модели конечных автоматов при их реализации на ПЛИС // Chip News. 2002. ╧ 9. С. 4√14.
  4. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Technical Report, Microelectronics Centre of North Carolina, 1991. 43 p.







Ваш комментарий к статье
Синтез на ПЛИС совмещенных моделей конечных автоматов. :
Ваше имя:
Отзыв: Разрешено использование тэгов:
<b>жирный текст</b>
<i>курсив</i>
<a href="http://site.ru"> ссылка</a>