Кодирование состояний для низкого энергопотребления

Кодирование состояний назначает уникальный шаблон единиц и нулей каждому определенному состоянию конечного автомата (FSM). Традиционно критериями проектирования для синтеза FSM были скорость, площадь или и то, и другое. Согласно закону Мура , с развитием технологий плотность и скорость интегральных схем увеличивались экспоненциально. При этом рассеиваемая мощность на единицу площади неизбежно увеличивалась, что заставило проектировщиков портативных вычислительных устройств и высокоскоростных процессоров рассматривать рассеиваемую мощность как критический параметр при рассмотрении конструкции. [1] [2]

Фон

Синтез FSM включает три основных этапа:

  1. Минимизация состояний: Как следует из названия, количество состояний, необходимых для представления FSM, сводится к минимуму. Различные методы и алгоритмы, такие как таблицы импликации , сопоставление строк и последовательное разбиение, выявляют и удаляют эквивалентные или избыточные состояния.
  2. Назначение или кодирование состояний включает выбор булевых представлений внутренних состояний FSM. Другими словами, он назначает уникальный двоичный код каждому состоянию. Выбор правильного метода кодирования имеет решающее значение, поскольку неправильное решение может привести к тому, что FSM будет использовать слишком много логической области, будет слишком медленным, будет потреблять слишком много энергии или к любой комбинации этих факторов.
  3. Минимизация комбинационной логики использует неназначенные коды состояний в качестве состояний «неважно», чтобы сократить комбинационную логику.

Существующие методы кодирования

Ниже приведены некоторые методы, которые широко используются для кодирования состояний:

  • В одноточечном кодировании только один из битов переменной состояния равен «1» (горячий) для любого заданного состояния. Все остальные биты равны «0». Расстояние Хэмминга этой техники равно 2. Одноточечное кодирование требует один триггер для каждого состояния в FSM. В результате конечный автомат уже «декодирован», поэтому состояние автомата определяется просто путем выяснения того, какой триггер активен. Эта техника кодирования уменьшает ширину комбинационной логики, и в результате конечный автомат требует меньше уровней логики между регистрами, что снижает его сложность и увеличивает его скорость.
  • В двоичном кодировании количество бит ( b ) на состояние зависит от количества состояний ( n ). Соотношение определяется уравнением b = log 2 ( n ) . В этой технике состояния назначаются в двоичной последовательности, где состояния нумеруются, начиная с 0 и выше. Количество используемых триггеров равно количеству бит ( b ). Поскольку двоичное кодирование использует минимальное количество бит (триггеров) для кодирования машины, триггеры используются максимально. В результате для декодирования каждого состояния требуется больше комбинационной логики по сравнению с однонаправленным кодированием. Двоичное кодирование требует меньше триггеров по сравнению с однонаправленным кодированием, но расстояния Хэмминга могут быть хуже — вплоть до количества бит ( b ).
  • В кодировке Грея , также известной как отраженное двоичное кодирование, состояния назначаются так, что последовательные коды состояний отличаются только одним битом. В этой кодировке соотношение между числом бит и числом состояний определяется как b = log 2 ( n ) . Число используемых триггеров и сложность логики декодирования такие же, как в двоичном кодировании, но расстояние Хэмминга в кодировке Грея всегда равно 1.

Другие методы кодирования включают кодирование на основе выходных данных, MUSTANG [3] и NOVA [4] .

Мотивация

Основная идея в разработке кодирования состояний для низкого энергопотребления заключается в минимизации расстояния Хэмминга наиболее вероятных переходов состояний, что снижает активность переключения. Таким образом, модель затрат для минимизации потребления энергии должна иметь минимально взвешенное расстояние Хэмминга (MWHD). [1] [2]

Для счетчиков кодирование Грея обеспечивает минимальную коммутационную активность и, таким образом, подходит для маломощных конструкций. Кодирование Грея лучше всего подходит для случаев, когда изменения состояний последовательны. При произвольных изменениях состояний код Грея FSM не может быть маломощной конструкцией. Для таких FSM кодирование одним нажатием гарантирует переключение двух битов для каждого изменения состояния. Но поскольку количество необходимых переменных состояния равно количеству состояний, по мере увеличения количества состояний кодирование одним нажатием становится непрактичным решением, в основном потому, что с увеличением количества входов и выходов в схему увеличиваются сложность и емкостная нагрузка. Двоичное кодирование является худшим для маломощных конструкций, поскольку максимальное расстояние Хэмминга равно количеству переменных состояния.

Необходимость решения проблемы произвольного изменения состояний конечного автомата привела к появлению нескольких методов кодирования состояний, направленных на снижение активности переключений во время переходов между состояниями.

Методы

Подход на основе столбцов для назначения состояний с низким энергопотреблением

Этот подход направлен на снижение рассеивания мощности последовательными цепями путем выбора назначений состояний, которые минимизируют активность переключения между переходами состояний. Таким образом, комбинационная часть FSM имеет более низкую вероятность перехода на входе и, скорее всего, даст низкое рассеивание мощности при синтезе. Этот алгоритм использует булеву матрицу со строками, соответствующими кодам состояний, и столбцами, соответствующими переменным состояния. Одна переменная состояния рассматривается за раз, и алгоритм пытается присвоить ее значение каждому состоянию в FSM таким образом, который, вероятно, минимизирует активность переключения для полного назначения. Эта процедура повторяется для следующей переменной. Поскольку этот метод минимизации применяется столбец за столбцом, этот метод называется подходом на основе столбцов. [5]

Назначение многокодового состояния

Метод назначения многокодового состояния реализует приоритетное кодирование путем ограничения избыточных состояний. Таким образом, состояние может быть закодировано с использованием меньшего количества переменных состояния (битов). Кроме того, триггеры, соответствующие этим отсутствующим переменным состояния, могут быть заперты тактовым генератором. [6]

Назначение состояния на основе профилирования

Эта техника использует динамическую информацию цикла, извлеченную из данных профилирования FSM для назначения состояния, чтобы уменьшить активность переключения. Процедура выглядит следующим образом: [7]

  1. Профилирование состояния конечного автомата собирает информацию о динамическом поведении конечного автомата для соответствующего набора входных данных.
  2. Детектор петель ищет петли в трассе состояния, и каждая петля сохраняется и подсчитывается для получения частоты петель.
  3. Назначение состояния назначает переменные состояния каждому состоянию на основе данных, собранных на первых двух этапах, чтобы минимизировать активность переключения. Существует три алгоритма назначения переменных состояния:
  • Базовый алгоритм назначения состояний DFS
  • Алгоритм назначения состояний DFS на основе цикла
  • Алгоритм эвристического назначения состояний на основе циклов для каждого состояния

Другие методы

  • Некоторые методы кодируют графы переходов состояний (STG) для создания двухуровневых и многоуровневых реализаций, ориентированных на низкую мощность. [8] [9]
  • Было предложено перекодировать существующие логические последовательные схемы для оптимизации энергопотребления. [10]
  • Кодирование состояния на основе связующего дерева [11]
  • Методы поиска в глубину [12]
  • Методы минимального расстояния [12]
  • Методы 1 уровня [12]
  • Метод одноуровневого дерева [12] , где снова основное внимание уделяется назначению переменных состояния различным состояниям таким образом, чтобы уменьшить активность переключения из-за перехода состояний
  • Помимо простого кодирования состояний для низкого энергопотребления, некоторые методы включают разложение FSM на две или более подмашин, так что только одна из них активна большую часть времени. Другая подмашина может быть либо clock-gated [13] , либо power-gated. [14]

Смотрите также

Ссылки

  1. ^ ab M. Pedram и A Abdollahi, «Методы синтеза на уровне реального времени с низкой мощностью: Учебное пособие»
  2. ^ ab Devadas & Malik, «Обзор методов оптимизации, нацеленных на маломощные схемы VLSI», DAC 32, 1995, стр. 242–247
  3. ^ S. Devadas et al., «MUSTANG: Назначение состояний конечных автоматов для многоуровневых логических реализаций», IEEE Trans. Computer-Aided Design, том CAD-7, № 12, декабрь 1988 г., стр. 129@1300
  4. ^ T. Villa, AS Vincentell, «NOVA: Назначение состояний конечных автоматов для оптимальной двухуровневой логической реализации», IEEE Transactions on CAD. ТОМ 9 № 9. Сентябрь 1990 г., стр. 905-924
  5. ^ Л. Бенини и Дж. Де Микели, «Назначение состояний для низкого рассеивания мощности», IEEE J. Solid-State Circuits, т. 30, № 3, 1995, стр. 258–268
  6. ^ X. Wu, M. Pedram и L. Wang, Назначение многокодового состояния для проектирования устройств с низким энергопотреблением, IEEE Proceedings-Circuits, Devices and Systems, т. 147, № 5, стр. 271–275, октябрь 2000 г.
  7. ^ http://mmc.tudelft.nl/sites/default/files/eggermont.pdf [ пустой URL-адрес PDF ]
  8. ^ K Roy и S Prasad. SYCLOP: Синтез логики КМОП для маломощных приложений. В трудах Международной конференции по компьютерному проектированию: СБИС в компьютерах и процессорах, страницы 464–467, октябрь 1992 г.
  9. ^ CY Tsui, M Pedram, CA Chen и AM Despain. Назначение состояний с низким энергопотреблением для двух- и многоуровневых логических реализаций. В трудах Международной конференции по автоматизированному проектированию, страницы 82–87, ноябрь 1994 г.
  10. ^ GD Hachtel, M Hermida, A Pardo, M Poncino и F Somenzi. Перекодирование последовательных схем для уменьшения рассеивания мощности. В трудах Международной конференции по автоматизированному проектированию, страницы 70–73, ноябрь 1994 г.
  11. ^ W. Noth и R. Kolla «Кодирование состояний на основе связующего дерева для низкого рассеивания мощности», Труды DATE, стр. 168. Март 1999 г.
  12. ^ abcd "Архивная копия" (PDF) . home.deib.polimi.it . Архивировано из оригинала (PDF) 28 августа 2017 г. . Получено 15 января 2022 г. .{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )
  13. ^ JC Monteiro и AL Oliveira, "Неявная декомпозиция конечного автомата, применяемая к маломощным конструкциям", IEEE Trans. VLSI Syst., т.10, №5, стр.560-565, 2002
  14. ^ SH Chow, YC Ho, T. Hwang и CL Liu, «Реализация конечных автоматов с низким энергопотреблением — подход декомпозиции», ACM Trans. Design Automat. Elect. Syst., т. 1, № 3, стр. 315-340, июль 1996 г.
Получено с "https://en.wikipedia.org/w/index.php?title=State_encoding_for_low_power&oldid=1252442738"