МИКРОЭЛЕКТРОНИКА, 2013, том 42, № 3, с. 233-240
- СХЕМОТЕХНИКА
УДК 681.3.14/21
ИТЕРАЦИОННЫЙ АЛГОРИТМ КОДИРОВАНИЯ ВНУТРЕННИХ СОСТОЯНИЙ КОНЕЧНЫХ АВТОМАТОВ С ЦЕЛЬЮ МИНИМИЗАЦИИ
ПОТРЕБЛЯЕМОЙ МОЩНОСТИ © 2013 г. В. В. Соловьев, Т. Н. Грэсь
Высший государственный колледж связи, Минск, Беларусь Белостокский технический университет, Белосток, Польша E-mail: valsol@mail.ru, t.grzes@pb.edu.pl Поступила в редакцию 24.01.2012 г.
Рассматривается эвристический итерационный алгоритм кодирования внутренних состояний конечных автоматов для снижения потребляемой мощности. Предлагаемый алгоритм является универсальным и может быть применен к любому результату кодирования внутренних состояний (в том числе и случайному) с целью минимизации потребляемой мощности конечного автомата. Кроме того, пользователь может выбирать компромисс между качеством решения задачи и временем выполнения алгоритма путем установления максимального числа выполнения итераций. Экспериментальные исследования показали, что предлагаемый подход позволяет уменьшить потребляемую мощность конечных автоматов, в среднем, в 1.73 раза, по сравнению с алгоритмом NOVA (в отдельных случаях — в 3.29 раза), и в 1.40 раза, по сравнению с алгоритмом JEDI (в отдельных случаях — в 2.31 раза).
Б01: 10.7868/8054412691303006Х
ВВЕДЕНИЕ
В последнее время в связи с широким использованием переносных и бортовых встроенных систем (мобильные телефоны, плееры, навигаторы, космические системы управления) особую актуальность приобретает задача снижения потребляемой мощности цифровых систем. Имеется несколько подходов к решению данной задачи: технологические (использование энергосберегающих технологий); логические (применение специальных методов синтеза); системные (включение высокоскоростного режима только для отдельных частей системы) и др. Одним из путей решения указанной проблемы является уменьшение потребляемой мощности конечных автоматов. Как известно, конечные автоматы широко используются в различных цифровых системах в качестве контроллеров, стандартных функциональных узлов, а также оригинальных последовательностных схем.
Известно множество подходов к решению задачи снижения потребляемой мощности конечных автоматов, например, с помощью специального кодирования внутренних состояний [1—4], путем декомпозиции больших схем на компоненты меньшего размера [5], использованием блоков встроенной памяти программируемых логических интегральных схем (ПЛИС) [6] и др. Обзор наиболее известных алгоритмов кодирования внутрен-
них состояний конечных автоматов для снижения потребляемой мощности приведен в [7].
В данной работе рассматривается эвристический итерационный алгоритм кодирования внутренних состояний конечных автоматов для снижения потребляемой мощности. Главная особенность предлагаемого подхода заключается в том, что рассматриваемый итерационный алгоритм является универсальным и может быть применен к любому результату кодирования внутренних состояний (в том числе и случайному) с целью минимизации потребляемой мощности конечного автомата. Кроме того, пользователь может выбирать компромисс между качеством решения задачи и временем выполнения алгоритма путем установления максимального числа выполнения итераций.
1. СУТЬ ПРЕДЛАГАЕМОГО ПОДХОДА
Рассматриваемый итерационный алгоритм является эвристическим и позволяет найти локальный минимум потребляемой мощности конечного автомата по результату кодирования внутренних состояний, полученному с помощью любого из известных алгоритмов. Предлагаемый подход основывается на следующих двух гипотезах:
1) взаимная замена кодов некоторых двух внутренних состояний может привести к уменьшению потребляемой мощности конечного автомата;
2) присвоение некоторому внутреннему состоянию кода из числа неиспользуемых кодов может также привести к уменьшению потребляемой мощности конечного автомата.
В основу данного алгоритма положены две процедуры, реализующие указанные выше гипотезы. Первая процедура осуществляет взаимную замену кодов двух состояний, а вторая — присваивает некоторому состоянию код из числа неиспользуемых кодов, если только это приводит к уменьшению потребляемой мощности конечного автомата. Указанные процедуры выполняются последовательно заданное число итераций. В случае уменьшения потребляемой мощности с помощью хотя бы одной из процедур, количество выполненных итераций обнуляется и весь процесс начинается сначала.
Отметим некоторые особенности предлагаемого подхода:
♦ алгоритм может использоваться для улучшения результата решения задачи кодирования внутренних состояний с целью уменьшения потребляемой мощности, полученного с помощью любого из известных методов;
♦ алгоритм является универсальным, поскольку не зависит от числа разрядов кода внутренних состояний, и может быть применен к любому результату кодирования;
♦ алгоритм может также использоваться самостоятельно, как оригинальный метод в случае его применения к произвольному (случайному) кодированию внутренних состояний;
♦ в каждый момент выполнения алгоритма всегда известно некоторое решение, не хуже исходного;
♦ число выполнения итераций ограничено и может задаваться пользователем с целью установления компромисса между вычислительной сложностью алгоритма и качеством решения задачи;
♦ последнее свойство позволяет использовать алгоритм для конечных автоматов большой размерности, для которых нахождение точного решения задачи нецелесообразно из-за большой вычислительной сложности.
Поскольку в каждой из указанных процедур вычисляется значение потребляемой мощности при заданном кодировании внутренних состояний конечного автомата, остановимся на этом вопросе более подробно.
2. ОПРЕДЕЛЕНИЕ ПОТРЕБЛЯЕМОЙ
МОЩНОСТИ КОНЕЧНОГО АВТОМАТА
Известно много различных методик определения потребляемой мощности цифровых устройств, в том числе и конечных автоматов. В нашем случае
для определения потребляемой мощности конечного автомата воспользуемся статической методикой работы [8], как наиболее универсальной и подходящей для любой элементной базы. В данной методике предполагается, что основное потребление мощности конечного автомата происходит при переключении состояний его элементов памяти, а мощность, рассеиваемая комбинационной частью конечного автомата, не учитывается, поскольку ее величина является значительно меньше, чем потребляемая мощность элементов памяти. Кроме того, эта методика ориентирована на CMOS-технологию изготовления микросхем, которая широко используется в настоящее время.
Методика [8] позволяет определить потребляемую мощность конечного автомата на основании результатов кодирования внутренних состояний, а также вероятности появления единицы (нуля) на каждом входе конечного автомата. Конечный автомат может задаваться графом или таблицей переходов, при этом тип конечного автомата (Мили или Мура), а также формируемые выходные сигналы не оказывают никакого влияния на вычисляемую величину потребляемой мощности.
Конечный автомат будем характеризовать числом М внутренних состояний множества А = = {а!, ..., аМ}, числом L входных переменных множества X = {хь ..., хЬ}, а также числом R разрядов кода внутренних состояний конечного автомата, R е [ти§2М, М]. Пусть элементы памяти конечного автомата строятся на D-триггерах (наиболее часто используемый тип триггеров при реализации памяти конечных автоматов).
Вероятность Р(а^ нахождения конечного автомата в каждом состоянии а^ 1 = 1, М, можно определить в результате решения следующей системы уравнений:
М
Р(а1) = XР(ат)Х Р(Хт1), 1 = Щ (1)
т=1
где Р(Хт1) — вероятность появления на входе конечного автомата входного вектора Хт1, который инициирует переход из состояния ат в состояние а1. В случае, когда переход между состояниями ат и а1 отсутствует, принимается Р(Хт1) = 0. В случае же, когда из состояния ат в состояние а1 ведут несколько переходов, значение Р(Хт1) определяется как сумма вероятностей появления каждого входного вектора, который инициирует переход из состояния ат в состояние а1.
Входной вектор Хт1 представляет собой троичный вектор длиной L, где единица на позиции Ь,
Ь = 1, Ь, означает, что соответствующая входная переменная хЬ принимает значение 1; ноль — зна-
чение 0; дефис ("-") — входная переменная хь не влияет на инициирование перехода между состояниями ат и а;. Вероятность Р(Хт1) появления на входе конечного автомата входного вектора Хт1 определяется из выражения:
Р(Хт1) = П Р(ХЬ = ¿),
(2)
Ь=1
где Р(хЬ = ё) — вероятность того, что входная переменная хЬ примет значение ё, ё е {0, 1, "-"}. В данной работе принято, что вероятность появления 0 или 1 на каждом входе конечного автомата одинакова, поэтому Р(хЬ = 0) = Р(хЬ = 1) = 0.5, а Р(хЬ = "-") = 1. Для конкретного конечного автомата значения Р(хЬ = 0) и Р(хЬ = 1) могут быть различными, однако должно выполняться условие: Р(Хь = 0) + Р(ХЬ = 1) = 1.
Система уравнений (1) представляет собой линейную систему М уравнений от М неизвестных Р(а1), ..., Р(аМ), для решения которой может быть применен любой из известных методов, например, Гаусса. Поскольку конечный автомат всегда находится в одном из своих внутренних состояний, справедливым является следующее равенство:
М
X Р(ат) = 1.
(3)
п=1
Для упрощения решения системы уравнений (1) одно из самых сложных уравнений в (1) может быть заменено уравнением (3). Отметим, что выбор уравнения, которое заменяется уравнением (3), не влияет на результаты вычислений.
После решения системы уравнений (1) становятся известны вероятности Р(а1), ..., Р(аМ) нахождения конечного автомата в каждом из своих внутренних состояний. Следующим этапом является определение вероятностей переходов между внутренними состояниями конечного автомата. Вероятность Р(ат ^ а8) перехода конечного автомата из состояния ат в состояние а8 (ат, а8 е А) определяется выражением:
Р(ат ^ а) = Р(ат) х Р^, (4)
где Р(ат) — значение вероятности нахождения конечного автомата в состоянии ат, вычисленное в результате решения системы уравнений (1); Р(Хт8) — определяемая согласно (2) вероятность появления на входе конечного автомата входного вектора Хт8, который иниции
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.