ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 3, с. 40-47
^ ДИСКРЕТНЫЕ
СИСТЕМЫ
УДК 004.312.4
МИНИМИЗАЦИЯ ПОТРЕБЛЯЕМОЙ МОЩНОСТИ КОНЕЧНЫХ АВТОМАТОВ ПУТЕМ РАСЩЕПЛЕНИЯ ВНУТРЕННИХ СОСТОЯНИЙ* © 2015 г. Т. Н. Грэсь, В. В. Соловьев
Польша, Белосток, Белостокский технологический ун-т Поступила в редакцию 03.06.14 г., после доработки 10.11.14 г.
Рассмотрен метод минимизации энергопотребления конечных автоматов путем расщепления внутренних состояний. Показано, что при расщеплении внутренних состояний возможно уменьшение числа различных значений разрядов кода для состояний с большой вероятностью перехода между ними. В результате снижается переключательная активность элементов памяти, что в итоге приводит к уменьшению потребляемой мощности конечного автомата. Предложены два эвристических алгоритма уменьшения энергопотребления конечных автоматов за счет расщепления внутренних состояний с большой и малой вычислительной сложностью, которые оказались близкими по эффективности. Результаты экспериментальных исследований показали, что предложенный метод позволяет снизить энергопотребление конечных автоматов в 58% случаев, при этом уменьшение потребляемой мощности составляет в среднем 7%, а для отдельных примеров — 81%.
БО1: 10.7868/80002338815030099
Введение. Широкое распространение переносных и бортовых цифровых систем предъявляет очень жесткие требования к энергопотреблению (потребляемой мощности) разрабатываемых проектов. В общем случае цифровую систему можно представить как совокупность взаимодействующих между собой комбинационных схем и конечных автоматов [1], поэтому одним из путей решения указанной проблемы является минимизация потребляемой мощности конечных автоматов.
Известно много различных подходов для снижения потребляемой мощности конечных автоматов: путем кодирования внутренних состояний [2—6], декомпозиции конечного автомата [7—9], управления синхронизацией [10—13], выбора типов триггеров элементов памяти [14, 15], изменения числа разрядов кода внутренних состояний [16], использования специальных структурных моделей конечных автоматов [17] и др.
В настоящей работе для уменьшения энергопотребления конечных автоматов предлагается использовать операцию расщепления внутренних состояний (РВС). На необходимость РВС конечных автоматов при решении задачи кодирования состояний указывалось еще в [18], затем эта идея высказывалась в [19]. В [20] операция расщепления внутренних состояний используется в одном из методов минимизации неполностью определенных конечных автоматов. В [21] РВС используется при выполнении параллельно минимизации и кодирования внутренних состояний конечного автомата. В [22] РВС применяется для улучшения параметров (энергопотребления и стоимости) синтезированного конечного автомата. В общем случае операция расщепления внутренних состояний широко используется в различных алгоритмах логического синтеза конечных автоматов для выполнения условий возможности синтеза [23], уменьшения числа аргументов функций [24], приведения конечного автомата к определенному классу [25] и др.
Отметим, что операции расщепления и склеивания внутренних состояний относятся к операциям эквивалентного преобразования конечного автомата и не изменяют алгоритм его функционирования [21].
1. Определение энергопотребления конечного автомата. Пусть А = {аь ..., ам} — множество внутренних состояний конечного автомата, X = {х1, ..., х1} — множество входных переменных,
* Работа выполнена при частичной финансовой поддержке Белостокского технологического университета (Польша), грант № 8/^/1/2013.
У = {уь ..., ум} — множество выходных переменных, Б = {а?ь ..., dЯ} — множество функций возбуждения элементов памяти, где Я — число элементов памяти (число разрядов кодов внутренних состояний), Я е [тИо§2М, М].
Для определения энергопотребления конечного автомата воспользуемся методикой работы [26], которая позволяет определить динамическую мощность конечного автомата на основании результатов кодирования внутренних состояний и вероятности появления единицы (нуля) на каждом входе конечного автомата.
Значение потребляемой мощности конечного автомата, согласно [26], определяется из выражения
я я
Р = х Рг = 1у2вв /с Е N (1.1)
г = 1 2 г = 1
где Рг — мощность, потребляемая триггером г; Уво — величина напряжения питания; / — частота функционирования конечного автомата; С — емкость выхода каждого триггера; N — переключательная активность триггера г, г = 1, Я.
Пусть к1 — некоторый бинарный код состояния аI е А. Обозначим через кГ значение бита г в
коде к состояния а, г = 1, Я. Тогда активность N переключения триггера г памяти конечного автомата можно выразить следующим образом:
м м
N = X X Р(ат ^ а)(кгт © кГ), (1.2)
т = 15 = 1
где © — логическая операция Исключающее ИЛИ; Р(ат ^ а.) — вероятность перехода конечного автомата из состояния ат в состояние а5 (ат, а5 е А), которая определяется выражением
Р(ат ^ а.) = Р(ат)Р(Х(апиа)), (1.3)
где Р(ат) — вероятность нахождения конечного автомата в состоянии ат; Р(Х(ат, а.)) — вероятность появления на входе конечного автомата входного вектора Х(ат, а ), который инициирует переход из состояния ат в состояние а.. Последняя определяется из выражения
I
Р(Х(ат,а)) = П Р(хь = ф, (1.4)
ь = 1
где Р(хь = d) — вероятность того, что входная переменная хь во входном векторе Х(ат, а.) примет значение d е {0, 1,'—'}; '—' — неопределенное значение. В данной работе принято, что вероятность появления 0 или 1 на каждом входе конечного автомата одинакова, поэтому
Р(хь = 0) = Р(хь = 1) = 0.5, Р(хь = '-') = 1.
Вероятность Р(а) нахождения конечного автомата в каждом состоянии а, I = 1, М, можно определить в результате решения следующей системы уравнений:
м _
Р(а) = £ Р(ат)Р(Х(ат, а)), I = 1,М. (1.5)
т = 1
В случае, когда переход между состояниями ат и аI отсутствует, принимается Р(Х(ат, а)) = 0. В случае же, когда из состояния ат в состояние аI ведут несколько переходов, значение Р(Х(ат, а)) определяется как сумма вероятностей появления каждого входного вектора, который инициирует переход из состояния ат в состояние а .
Система уравнений (1.5) представляет собой линейную систему М уравнений от М неизвестных Р(а1), ..., Р(аМ), для решения которой может быть применен любой из известных методов, например Гаусса. Поскольку конечный автомат всегда находится в одном из своих внутренних состояний, справедливым является следующее равенство:
м
I Р(ат) = 1. (1.6)
т=1
Для решения системы уравнений (1.5) одно из уравнений в (1.5) заменяется равенством (1.6).
С учетом вышеизложенного алгоритм определения оценки энергопотребления (потребляемой мощности) конечного автомата выглядит следующим образом.
Алгоритм 1 (определения оценки энергопотребления).
1. Согласно (1.4), для каждого входного вектора X(am, as) (am, as g A) определяется вероятность P(X(am, as)) его появления на входе конечного автомата.
2. Решается система уравнений (1.5) для определения вероятностей P(a) нахождения конечного автомата в каждом состоянии a(-, ai g A.
3. Согласно (1.3), определяются вероятности переходов P(am^as) конечного автомата, am, as g A.
4. На основании результатов кодирования внутренних состояний, согласно (1.2), определяется активность каждого триггера Nr, r = 1, R.
5. Согласно (1.1), вычисляется потребляемая мощность P конечного автомата для следующих значений параметров: VDD = 5V, f = 10 MHz и C = 5pF (типичные значения для большинства микросхем CMOS-технологии).
Конец.
2. Суть предлагаемого подхода. В основу предлагаемого метода положена следующая гипотеза: РВС конечного автомата может приводить к снижению энергопотребления конечного автомата. На первый взгляд данное предположение может показаться абсурдным, поскольку в результате расщепления внутренних состояний увеличивается число внутренних состояний конечного автомата, что может привести даже к увеличению числа R разрядов, необходимых для кодирования внутренних состояний. Однако РВС позволяет уменьшить связанность состояний в графе автомата [1], что упрощает решение задачи кодирования внутренних состояний с целью минимизации энергопотребления.
Анализ выражения (1.2) показывает, что активность Nr некоторого триггера r, r = 1, R, может быть изменена как за счет уменьшения вероятностей переходов между состояниями P(am ^ as), am, as g A, так и за счет уменьшения числа разрядов кода, по которым различаются коды состояний am и as.
Вначале проанализируем, как РВС влияет на вероятность P(am ^ as) перехода из состояния am в состояние as, am, as g A. Значение вероятности P(am ^ as) определяется из выражения (1.3). Вероятность P(X(am, as)) появления на входе конечного автомата входного вектора X(am, as) при расщеплении внутренних состояний не изменяется. Однако при расщеплении состояний будет увеличиваться общее число M состояний конечного автомата, а из выполнения равенства (1.6) следует, что при увеличении M вероятности P(am) для отдельных состояний будут уменьшаться. С другой стороны, при увеличении числа состояний M будет увеличиваться число слагаемых в выражении (1.2), поэтому на уменьшение энергопотребления только за счет увеличения числа состояний M надеяться не приходится.
Теперь проанализируем, как РВС влияет на число разрядов, по которым различаются коды состояний am и a, m, s = 1, M. Пусть кодирование внутренних состояний конечного автомата осуществляется бинарными кодами с числом разрядов R = intlog2M. Общее число кодов, доступных для кодирования внутренних состояний, равно 2R. На практике часто справедливым является неравенство M < 2R, т.е. число возможных кодов больше, чем число внутренних состояний. При расщеплении некоторого состояния ai, ai g A, уменьшается множество состояний B(a), переходы из которых ведут в состояние ai. В результате упрощается подбор кодов с целью минимизации потребляемой мощности для состояний, связанных с состоянием ai, ai g A. Другими словами, в результате расщепления некоторого состояния ai (ai g A) для переходов в состояние ai и из состояния ai с большими вероятностями вида P(am ^ a) и P(ai ^ as) (am, as g A) становится
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.