Энергосберегающий синтез конечных автоматов на основе совмещенной структурной модели Соловьев Валерий Васильевич Высший государственный колледж связи (Минск, Беларусь)

2 University Содержание Введение Структурная модель ADE Метод энергосберегающего синтеза совмещенной модели ADE Алгоритм 1 (общий алгоритм синтеза) Пример Результаты экспериментальных исследований Сравнение предлагаемого метода с известными Заключение

3 University Введение В последнее время в связи с широким использованием переносных и бортовых встроенных систем особую актуальность приобретает задача снижения потребляемой мощности цифровых систем. Имеется несколько подходов к решению данной задачи: технологические (использование энергосберегающих технологий); логические (применение специальных методов синтеза); системные (управление частотой синхронизации и напряжением питания для отдельных частей системы) и др. Одним из путей решения указанной проблемы является уменьшение потребляемой мощности конечных автоматов.

4 University Введение Основной идеей предлагаемого подхода является использование триггеров входных и выходных буферов ПЛИС в качестве элементов памяти конечных автоматов, а наборы значений входных и выходных сигналов – в качестве части кода внутренних состояний. Если в качестве сигнала синхронизации элементов памяти буферов выбрать сигнал синхронизации конечного автомата, то триггеры буферов можно использовать в качестве элементов памяти конечного автомата. Буферизация сигналов может выполняться в элементах ввода-вывода ПЛИС, в логических элементах FPGA в макроячейках CPLD.

5 University Структурная модель ADE Новая классификация конечных автоматов позволила все конечные автоматы разделить на 6 классов: A, B, C, D, E и F: A и B – это традиционные структурные модели конечных автоматов типа Мили и Мура, соответственно; в автоматах классов C и D триггеры выходных буферов ПЛИС используются в качестве элементов памяти автомата; а в автоматах E и F триггеры входных буферов ПЛИС используются в качестве элементов памяти автомата. Для построения автоматов классов C-F часто вводятся дополнительные элементы памяти, аналогичные элементам памяти автоматов классов A и B. В последнем случае образуются совмещенные модели конечных автоматов.

6 University Структурная модель ADE где CL – комбинационная часть конечного автомата; RG I, RG O и RG – регистры для хранения части кода внутренних состояний; X = {x 1,…,x L } – множество входных переменных; Y = {y 1,…,y N } – множество выходных переменных; D = {d 1,…,d R } – множество функций возбуждения элементов памяти регистра RG; E = {e 1,…,e R } – множество внутренних переменных обратной связи; G = {g 1,…,g L } – множество внутренних переменных, соответствующих входным переменным; Z = {z 1,…,z N } – множество внутренних переменных, соответствующих выходным переменным.

7 University Метод энергосберегающего синтеза совмещенной модели ADE Суть данного метода заключается в специальном кодировании внутренних состояний конечного автомата, которое позволяет использовать значения входных и выходных переменных в качестве части кода внутренних состояний. Для этого строится матрица кодов W. Строки матрицы W соответствуют внутренним состояниям конечного автомата множества A, а столбцы – элементам множеств G и Z. Если все строки матрицы W взаимно ортогональны, то в качестве кодов внутренних состояний принимаются значения соответствующих строк матрицы W (две строки матрицы W считаются ортогональными, если в одинаковых разрядах они имеют различные значащие значения: 0 или 1). В противном случае решается задача ортогонализации строк матрицы W путем дополнительного кодирования переменными множества E. Последняя задача сводится к построению графа H ортогональности строк матрицы W и разбиению его на минимальное число полных подграфов H 1,…,H T.

8 University Алгоритм 1 (общий алгоритм синтеза) 1. Строится матрица W кодов внутренних состояний конечного автомата, определяемая значениями переменных множеств G и Z. 2. Строится граф H ортогональности строк матрицы W. 3. Граф H разбивается на минимальное число T полных подграфов H 1,…,H T. 4. Выполняется кодирование подграфов H 1,…,H T двоичными кодами длиной R, R intlog 2 T, соответствующими значениям переменных множества E с учетом минимизации потребляемой мощности. 5. В матрицу W добавляются столбцы, соответствующие переменным множества E. Значения этих столбцов определяются двоичными кодами соответствующих подграфов. 6. В качестве кодов внутренних состояний конечного автомата принимается значение строк матрицы W.

9 University Пример Список переходов конечного автомата x1x1 amam X(a m,a s )asas Y(a m,a s ) a1a1 1-a2a2 1 0-a1a1 0 a2a2 a1a1 1 -0a3a3 1 a3a3 1-a3a3 0 0-a4a4 0 a4a4 11a2a2 1 -0a1a1 0 0-a3a3 0

10 University Матрица W aiai GZ g1g1 g2g2 z1z1 a1a1 --- a2a2 1-1 a3a3 --- a4a4 0-0

11 University Граф ортогональности H и его разбиение на подграфы H 1,…,H 3 Для кодирования вершин графа H используется последовательный алгоритм работы [9]. В результате подграфу H1 (состояниям a2 и a4) назначается код 00, подграфу H2 (состоянию a1) - код 10, а подграфу H3 (состоянию a3) - код 01.

12 University Матрица W после ортогонализации строк aiai GZE g1g1 g2g2 z1z1 e1e1 e2e2 a1a a2a a3a a4a

13 University Результаты экспериментальных исследований FSMLNMQPNPN PJPJ PKPK PSPS PIPI PCPC bbara ,9159,4456,2652,77 52,39 bbtas ,29112,5083,15 72,76 beecount ,50108,05108,9289,42 75,37 cse ,3665,3455,8544,9744,9644,70 dk ,86416,60377,53309,09290,41228,31 dk ,11325,89223,21 151,77 dk ,58450,89319,75238,84215,40191,69 donfile ,22351,56265,63222,66207,03140,63 ex ,21307,75157,70138,55133,29133,95 keyb ,40121,67121,25104,35 103,92 pma ,73203,53105,55104,76104,2837,51 s ,65170,43168,33 166,2386,92 s ,2142,4133,90 35,09 shiftreg ,25 257,81210,94187,50 train ,3477,4586,9663,52 51,63 mid250,23212,84172,18152,24133,29106,28

14 University Сравнение предлагаемого метода с известными FSMLNMQP N /P C P J /P C P K /P C P S /P C P I /P C bbara ,601,131,071,01 bbtas226241,981,551,14 beecount347282,131,431,451,19 cse ,091,461,251,01 dk ,141,821,651,351,27 dk ,972,151,47 dk ,992,351,671,251,12 donfile ,312,501,891,581,47 ex ,272,301,181,031,00 keyb ,841,171,151,00 pma ,305,432,812,792,78 s ,491,961,94 1,91 s ,521,210,97 shiftreg118161,50 1,371,131,00 train ,081,501,681,23 mid2,411,961,511,341,30

15 University Заключение Анализ последней таблицы показывает, что предлагаемый метод, в среднем, превосходит метод NOVA в 2,41 раза (в отдельных случаях – в 7,3 раза), метод JEDI в 1,96 раза (в отдельных случаях – в 5,43 раза), столбцовый метод в 1,51 раза (в отдельных случаях – в 2,81 раза), последовательный метод в 1,34 раза (в отдельных случаях – в 2,79 раза) и итерационный метод в 1,3 раза (в отдельных случаях – в 2,78 раза). Данный результат объясняется отступлением от традиционных структурных моделей конечных автоматов и использованием новой структурной модели ADE Кроме того, используемая структурная модель ADE позволяет снизить стоимость реализации и повысить быстродействие конечного автомата за счет упрощения его комбинационной части.

16 University Спасибо за внимание