ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 1, с. 95-103
^ ДИСКРЕТНЫЕ
СИСТЕМЫ
УДК 004.312.4
ПОСЛЕДОВАТЕЛЬНЫЙ АЛГОРИТМ КОДИРОВАНИЯ ВНУТРЕННИХ СОСТОЯНИЙ КОНЕЧНЫХ АВТОМАТОВ ДЛЯ МИНИМИЗАЦИИ ПОТРЕБЛЯЕМОЙ МОЩНОСТИ* © 2014 г. Т. Н. Грэсь, В. В. Соловьев
Польша, Белосток, Белостокский технологический ун-т Поступила в редакцию 25.10.11 г., после доработки 11. 07.13 г.
Рассматривается эвристический алгоритм кодирования внутренних состояний конечных автоматов для снижения потребляемой мощности. Особенностью предлагаемого подхода является то, что при выборе кода для очередного состояния учитывается значение функции активности элементов памяти при переходе из данного состояния к уже закодированным состояниям. Приводится также методика определения потребляемой мощности конечного автомата на основании кодов внутренних состояний и вероятностей появления единиц на каждом входе конечного автомата. Экспериментальные исследования показали, что предлагаемый подход позволяет снизить потребляемую мощность конечных автоматов, по сравнению с алгоритмом МОУЛ, в среднем на 39%, а для отдельных примеров — на 68%. В заключение указывается на возможность повышения эффективности настоящего алгоритма при синтезе конкретного конечного автомата, а также на перспективные направления дальнейших исследований в данной области.
Б01: 10.7868/80002338814010065
Введение. В последнее время в связи с широком использованием переносных и бортовых встроенных систем (мобильные телефоны, плееры, навигаторы, космические системы управления) особую актуальность приобретает задача снижения потребляемой мощности цифровых систем. Имеется несколько подходов к решению данной задачи: технологические (использование энергосберегающих технологий); логические (применение специальных методов синтеза); системные (включение высокоскоростного режима только для отдельных частей системы) и др. Одним из путей решения указанной проблемы является уменьшение потребляемой мощности конечных автоматов. Как известно, конечные автоматы широко используются в различных цифровых системах в качестве контроллеров, стандартных функциональных узлов, а также оригинальных последовательностных схем.
Известно множество подходов к решению задачи снижения потребляемой мощности конечных автоматов. Прежде всего следует отметить, что большинство методов минимизации конечных автоматов [1—5] также способствуют снижению потребляемой мощности. Непосредственно снижение потребляемой мощности конечных автоматов осуществляется с помощью специального кодирования внутренних состояний [6—9], путем декомпозиции больших схем на компоненты меньшего размера [10], использованием блоков встроенной памяти программируемых логических интегральных схем (ПЛИС) [11] и др. Обзор наиболее известных алгоритмов кодирования внутренних состояний конечных автоматов для снижения потребляемой мощности приведен в [12].
В данной работе рассматривается эвристический последовательный алгоритм кодирования внутренних состояний конечных автоматов для снижения потребляемой мощности. Главным отличием предлагаемого подхода от известных является то, что при выборе кода для очередного состояния учитывается значение функции активности переключения элементов памяти при переходе из данного к уже закодированным состояниям.
1. Определение потребляемой мощности конечного автомата. Известно много различных методик определения потребляемой мощности цифровых устройств, в том числе и конечных автоматов. Обычно методики определения потребляемой мощности зависят от технологии изготовления микросхем (TTL, CMOS), классов устройств (комбинационные, последовательностные),
* Работа выполнена при частичной финансовой поддержке Белостокского технического университета (Польша), грант № S/WI/4/2008.
используемой элементной базы (микросхемы малой степени интеграции, БИС, СБИС, ПЛИС, системы на одном кристалле), уровня описания устройства (транзисторы, вентили, уровень регистровых передач, функциональные блоки, алгоритм функционирования) и др. Кроме того, методы определения потребляемой мощности делятся на статические и динамические.
Статические методы основываются на статистических (вероятностных) параметрах исследуемого устройства, например, вероятности появления единицы на определенном входе устройства [13—15]. Динамические методы определения потребляемой мощности основаны на моделировании устройства, при этом строится модель устройства и формируются типичные последовательности входных векторов [16—18]. Статические методы носят общий характер и наиболее пригодны для оценки методов и алгоритмов синтеза, предназначенных для снижения потребляемой мощности конечных автоматов. Динамические методы, как правило, являются более трудоемкими, однако позволяют точнее определить потребляемую мощность конкретного конечного автомата.
Для исследования алгоритмов кодирования внутренних состояний конечных автоматов воспользуемся статической методикой работы [19] как наиболее универсальной и подходящей для любой элементной базы. В данной методике предполагается, что основное потребление мощности конечного автомата происходит при переключении состояний его элементов памяти, а мощность, рассеиваемая комбинационной частью конечного автомата, не учитывается, поскольку ее величина значительно меньше, чем потребляемая мощность элементов памяти. Кроме того, эта методика ориентирована на СМ08-технологию изготовления микросхем, которая широко используется в настоящее время.
Методика [19] позволяет определить потребляемую мощность конечного автомата на основании результатов кодирования внутренних состояний, а также вероятности появления единицы (нуля) на каждом входе конечного автомата. Конечный автомат может задаваться графом или таблицей переходов, при этом тип конечного автомата (Мили или Мура), а также формируемые выходные сигналы не оказывают никакого влияния на вычисляемую величину потребляемой мощности.
Конечный автомат будем характеризовать числом М внутренних состояний множества А = = {а1, ..., аМ}, числом Ь входных переменных множества X = {х1, ..., хЬ}, а также параметром Я — минимальным числом разрядов кода, достаточных для кодирования внутренних состояний конечного автомата, Я > тИо§2М. Пусть элементы памяти конечного автомата строятся на ^-триг-герах (наиболее часто используемый тип триггеров при реализации памяти конечных автоматов).
Вероятность Р(а ) нахождения конечного автомата в каждом состоянии а, I = 1, М, можно определить в результате решения следующей системы уравнений:
М
Р(а) = £Р(ат) х Р(Хт1), I = 1М, (1.1)
т=1
где Р(Хт) — вероятность появления на входе конечного автомата входного вектора Хт, который инициирует переход из состояния ат в состояние а. В случае, когда переход между состояниями ат и а I отсутствует, принимается Р(Хт) = 0. В случае же, когда из состояния ат в состояние а I ведут несколько переходов, значение Р(Хт) определяется как сумма вероятностей появления каждого входного вектора, который инициирует переход из состояния ат в состояние а .
Входной вектор Хт! представляет собой троичный вектор длиной Ь, где единица на позиции Ь,
Ь = 1, Ь, означает, что соответствующая входная переменная хЬ принимает значение 1; ноль — значение 0; дефис ('—') — входная переменная хЬ не влияет на инициирование перехода между состояниями ат и а. Вероятность Р(Хт) появления на входе конечного автомата входного вектора ХтI определяется из выражения
Ь
Р(Хт) = П Р(ХЬ = *), (1.2)
Ь=1
где d е {0, 1, '—'}; Р(хЬ = ф — вероятность того, что входная переменная хЬ примет значение й. В данной работе принято, что вероятность появления 0 или 1 на каждом входе конечного автомата одинакова, поэтому Р(хЬ = 0) = Р(хЬ = 1) = 0.5. В случае, когда хЬ = '—', значение Р(хЬ = '—')
принимается равным 1. Последнее означает, что вероятность появления вектора Хт на входе конечного автомата не зависит от значения входной переменной хь, т.е. Р(хь = 0) + Р(хь = 1) = 1. Для конкретного конечного автомата значения Р(хь = 0) и Р(хь = 1) могут быть различными, однако должно выполняться условие Р(хь = 0) + Р(хь = 1) = 1.
Система уравнений (1.1) представляет собой линейную систему М уравнений от М неизвестных Р(а1), ..., Р(аМ), для решения которой может быть применен любой из известных методов, например Гаусса. Поскольку конечный автомат всегда находится в одном из своих внутренних состояний, справедливым является следующее равенство:
м
X Р(ат) = 1. (1.3)
т=1
Для упрощения решения системы уравнений (1.1) одно из уравнений в (1.1) может быть заменено уравнением (1.3). Отметим, что выбор уравнения, которое заменяется уравнением (1.3), не влияет на результаты вычислений.
После решения системы уравнений (1.1) становятся известны вероятности Р(а1), ..., Р(аМ) нахождения конечного автомата в каждом из своих внутренних состояний. Следующим этапом является определение вероятностей переходов между внутренними состояниями конечного автомата. Вероятность Р(ат ^ а) перехода конечного автомата из состояния ат в состояние а5 (ат, а5 е А) определяется выражением
Р(ат ^ а,) = Р(ат) х Р(ХП1), (1.4)
где Р(ат) — вычисленное значение вероятности нахождения конечного автомата в состоянии ат; Р(Хт,) — вычисляемая, согласно (1.2), вероятность появления на входе конечного автомата входного вектора Хт,, который инициирует переход из состояния ат в состояние а,. Отметим, что в данной методике вероятность перехода из некоторого состояния в то же самое состояние (состояние ожидания) принимается равным 0, поскольку при этом не изменяются состояния элементов памяти конечного автомата и, следовательно, мощность не потребляется.
Чтобы определить потребляемую мощность конечного автомата, обязательным является знание значений кодов внутренних состояний. Пусть к — некоторый бинарный код состояния а,
I = 1, М. Обозначим через кг значение бита г в коде к состояния а, г = 1, Я. Тогда активность N
переключения триггера г, г = 1, Я, памяти конечного автомата можно выразить с помощью следующего уравнения:
м м
N = ХХР(ат ^ а,) х (кгт ® к&), (1.5)
т=1 &=1
где © — логическая операция Исключающее ИЛИ.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.