Нахождение режима максимального энергопотребления логической схемы | ПДМ. 2012. № 2(16).

Нахождение режима максимального энергопотребления логической схемы

Известно, что оценка максимального энергопотребления логической схемы позволяет обеспечить её надёжность. Получение этой оценки облегчается предварительным нахождением такого режима работы схемы, при котором её энергопотребление оказывается максимальным. Предлагается метод нахождения этого режима для случая, когда рассматриваемая схема реализует конечный автомат.

Search for conditions of maximal energy consumption in logiccircuit.pdf ВведениеПри проектировании логической схемы важно оценивать максимальную затратуэнергии при её функционировании, поскольку чрезмерные затраты энергии могут при-водить к выходу схемы из строя. В основном эта энергия тратится при смене входныхнаборов - комбинаций значений входных булевых переменных схемы. Затраты энер-гии для каждой пары входных наборов (предшествующего и последующего) можнонаходить экспериментально или оценивать числом переключаемых транзисторов [1, 2].Оценивание энергопотребления логической схемы может проводиться более успеш-но при учёте назначения схемы и способа её проектирования. Это позволяет значи-тельно сократить число рассматриваемых входных наборов и переходов между ними,облегчая тем самым решение данной задачи. Ещё больший эффект достигается припредварительном нахождении режима максимального энергопотребления - соответ-ствующей последовательности наборов значений входных переменных схемы.Ниже эта задача решается для случая, когда схема синхронна и реализует ко-нечный автомат. Тогда она представляет собой комбинационную схему с однотактнойобратной связью, обеспечиваемой регистром. Значения переменных на отмеченныхжирными линиями выходных полюсах в текущий момент времени становятся значе-ниями соответствующих входных переменных в следующий такт. Пример такой схемыпоказан на рис. 1.bpqOutКомбинационнаясхемаrРегистрРис. 1. Схемная реализация конечного автоматаПоложим, что комбинационная схема имеет n входных переменных и они делятсяна две части: u свободных переменных, принимающих произвольные наборы значений,и v связанных переменных, наборы значений которых представляют коды возможныхсостояний автомата (u + v = n). В примере на рис. 1 свободными являются перемен-ные а, b, а связанными - переменные p, q, r.Число w входных наборов схемы в целом равно s2u, где s - число состояний ав-томата. Эти наборы представляются соответствующими значениями n-компонентногобулева вектора x = (u, v ) . Вектор u представляет набор значений свободных перемен-ных и содержит u компонент. Вектором v представляется набор значений связанныхкомпонент. Его длина v определяется числом состояний автомата и способом их коди-рования.Предлагаемый в работе метод нахождения режима максимального энергопотребле-ния логической схемы основан на предположении, что чем больше переменных меняютсвои значения при очередной смене значения вектора x, тем больше тратится энергиина эту смену.1. Пример конечного автоматаРассмотрим в качестве примера автомат с шестью состояниями S0, S1, S2, S3, S4,S5 и двумя свободными переменными a и b. Возможные переходы между состояниямиотобразим ориентированным графом переходов G (рис. 2).Рис. 2. Граф переходов GУсловия переходов между состояниями Si и представим соответствующими эле-ментами таблицы. Например, автомат переходит из состояния S1 в состояние So толькопри одном наборе значений свободных переменных - когда ab = 1, а в состояние S5в трёх случаях - когда a V b = 1. Заметим, что пустые элементы таблицы соответству-ют невозможным переходам.Условия переходов в автоматеSo Si S2 S3 S4 S5So a aSi ab a V bS2 ab ab aS3 ab b abS4 b bS5 ab a V bПроектирование логической схемы, реализующей конечный автомат, начинаетсяс кодирования его состояний наборами значений булевых переменных. Практическиэффективные алгоритмы решения этой задачи рассмотрены в [3]. В работе [4] даннаязадача решается путём такого отображения графа переходов в булев граф, при кото-ром как можно больше рёбер графа переходов отображается на рёбра булева графа.В результате существенно уменьшается число переменных, меняющих свои значенияна переходах, и тем самым снижается энергопотребление схемы, реализующей авто-мат. Состояния автомата кодируются булевыми векторами, соответствующими темвершинам булева графа, на которые они отобразились.Так, в данном примере находятся коды состояний автомата, компонентами кото-рых служат соответствующие значения трёх булевых переменных p, q, r. Эти кодыпредставлены столбцами следующей матрицы:So Si S2 S3 S4 S5p 1 0 1 0 1 0q 0 0 1 1 1 0r 0 0 0 1 1 1В полученном результате при большинстве переходов в данном автомате меняет-ся значение лишь одной из кодирующих переменных p, q или r - соответствующиерёбра отмечены на рис. 3 одиночными линиями. При остальных переходах меняютсязначения двух либо трёх переменных - рёбра представлены двойными либо тройнымилиниями.Рис. 3. Граф переходов с отмеченными рёбрамиВместе с двумя входными переменными кодирующие переменные образуют пяти-компонентный входной булев вектор x = (a, b,p, q, r) комбинационной схемы, реализу-ющей заданный автомат.В данном примере автомата с шестью состояниями число возможных входных на-боров схемы w = 6 22 = 24, что несколько меньше числа всех наборов 25 = 32.Значительно сильнее сокращается число переходов между наборами: из 1024 различ-ных переходов оказываются возможными лишь 16 14 = 224. Действительно, числопереходов в автомате равно 14 и при каждом из них значения переменных p, q, rменяются однозначно. Что же касается входных переменных a и b, то они могут при-нимать произвольные наборы значений в предшествующий и последующий такты.2. Нахождение режима максимального энергопотребления схемыПредлагаемый метод заключается в поиске такой циклической последовательно-сти переходов, которая допустима в рамках используемой формальной модели (хотяи может быть маловероятной), может многократно повторяться и является наибо-лее энергоёмкой, приводя к максимальным энергозатратам. При решении этой задачиможно ограничиться рассмотрением простых (не самопересекающихся) циклов, по-скольку любой цикл разлагается на простые и его энергоёмкость не может превыситьмаксимальной энергоёмкости элементов разложения.Например, простым является цикл из трёх переходов 0 ^ 4, 4 ^ 2 и 2 ^ 0(см. рис. 3), который проходит через вершины 0, 4, 2 и обозначается 042. Для нашегопримера простых циклов 15: 4, 01, 015, 01532, 015342, 042, 04231, 042315, 0425, 153,042531, 23, 234, 253, 2534.Для входящих в простые циклы переходов подсчитываются их веса - числа ко-дирующих переменных, меняющих свои значения. Среднее значение такого числа напереход (обозначим это среднее через mean_code ) определяет энергоёмкость цикла.Выбирается цикл, в котором оно максимально. Например, в цикле 042 на переходах0 ^ 4, 4 ^ 2 и 2 ^ 0 меняют свои значения соответственно две, одна и одна перемен-ная. следовательно, mean_code = (2 + 1 + 1)/3 = 4/3.Максимальное значение mean_code, равное 2, достигается в циклах 2504, 23 и 325.Заметим, что эти циклы, содержащие переходы с большими весами, можно выявитьвизуально (см. рис.3), используя эвристический метод, иллюстрируемый следующимпримером.Берется переход 25 с максимальным весом (3), к нему подсоединяется соседнийпереход 50 с весом 2, затем переход 04, также с весом 2. В результате получаетсякомпозиция трёх переходов, последовательно проходящих через вершины 2, 5, 0, 4. Еёможно замкнуть переходом 42 с весом 1, получив таким образом цикл 2504. Анало-гично находится цикл 325: в этом случае к переходу 25 подсоединяется соседний слевапереход 32, затем цикл замыкается переходом 53.Для каждого перехода в выбранном цикле находятся допустимые наборы значенийсвободных переменных, т. е. такие наборы, которые обеспечивают выполнение перехо-да. Например, для переходов 2 ^ 5, 5 ^ 0, 0 ^ 4 и 4 ^ 2 цикла 2504 такие наборыпеременных a, b образуют соответственно множества {00, 01}, {10}, {00, 01} и {01,11}.Последовательность этих множеств представим выражениемf r e e = 00, 01/10/00,01/01,11.Из допустимых наборов выбираются такие, при которых по возможности максими-зируется число переменных, меняющих свои значения на переходе. В данном примеретакие наборы образуют следующую последовательность значений вектора u: 01, 10,01, 11. Объединяя полученные наборы свободных переменных с соответствующиминаборами кодирующих переменных - последовательными значениями вектора v: 110,001, 100, 111, находим искомую циклическую последовательность наборов всех вход-ных переменных схемы - последовательность соответствующих значений вектора x:01110, 10001, 01100, 11111.В заключение подсчитываются числа входных переменных комбинационной схемы,меняющих свои значения на переходах, и находится их среднее значение:mean_input = (5 + 4 + 3 + 2 ) / 4 = 3,5.Аналогично подсчитываются энергозатраты при двух других выбранных циклах:23: free = 1 0 / 0 0 , 1 0 ;u : 10,00; v : 110, 011; x : 10110, 00011;mean_input = (3 + 3 ) / 2 = 3;325: free = 00,10/00, 01/00, 01,11;u : 00,01,11; v : 011,110,001; x : 00011,01110,11001;mean_input = (3 + 4 + 3 ) / 3 = 3,33 . . .Как видно, максимальной энергоёмкостью обладает цикл 2504. Следовательно, ре-жим максимального энергопотребления рассматриваемой схемы заключается в пери-одическом повторении простого цикла 2504, который инициируется повторяющейсячетвёркой (01, 10, 01, 11) наборов значений свободных переменных a и b.ЗаключениеЗадача определения максимального энергопотребления спроектированной логиче-ской схемы упрощается, когда известно назначение схемы - например, когда она реа-лизует конечный автомат. Известные методы её решения, основанные на подсчёте чис-ла переключаемых логических элементов, довольно трудоёмки, будучи связаны с рас-смотрением многочисленных вариантов последовательной смены значений входноговектора. Объём вычислений, производимый при решении этой задачи, значительносокращается предлагаемым в данной работе методом нахождения режима максималь-ного энергопотребления - соответствующей циклической последовательности значе-ний входного вектора.

Ключевые слова

логические схемы, режим максимального энергопотребления, логическое проектирование, logical circiut, maximal energy consumption, logic design

Авторы

ФИООрганизацияДополнительноE-mail
Закревский Аркадий ДмитриевичОбъединённый институт проблем информатики НАН Беларуси, г. Минскчлен-корр. НАН Беларуси, доктор технических наук, главный научный сотрудникzakrevskij@tut.by
Всего: 1

Ссылки

Ghosh A., Devadas S., Keutzer K., and White J. Estimation of Average Switching Activity in Combinational and Sequential Circuits // Proc. 29th ACM/IEEE Design Automation Conf. Anaheim, CA, 1992. P. 253-259.
Marculesku D., Marculesku R., and Pedram M. Theoretical Bounds for Switching Activity Analysis in Finite-State Machines // Proc. 1998 international symposium on low power electronics and design. NY, USA: ACM, 1998. P. 36-41.
Закревский А. Д. Алгоритмы энергосберегающего кодирования состояний автомата // Информатика. 2011. №1(29). С. 68-78.
Закревский А. Д. Алгоритм матричного отображения графа на булев куб // Вестник Томского госуниверситета. Управление, вычислительная техника и информатика. 2011. №3(16). С. 94-99.
 Нахождение режима максимального энергопотребления логической схемы | ПДМ. 2012. № 2(16).

Нахождение режима максимального энергопотребления логической схемы | ПДМ. 2012. № 2(16).

Полнотекстовая версия