Кодирование состояния для низкого энергопотребления - State encoding for low power

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

Фон

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

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

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

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

  • В одно горячее кодирование, только один из битов переменной состояния равен «1» (горячий) для любого данного состояния. Все остальные биты равны «0». В Расстояние Хэмминга из этих методов - 2. Один горячий требует одного триггера для каждого состояния в автомате. В результате конечный автомат уже «декодирован», поэтому состояние автомата определяется просто путем определения того, какой триггер активен. Этот метод кодирования уменьшает ширину комбинаторной логики и, как следствие, конечный автомат требует меньше уровней логики между регистрами, что снижает его сложность и увеличивает скорость.
  • В двоичное кодирование, количество битов (b) на состояние зависит от количества состояний (n). Взаимосвязь определяется уравнением:
   б = log2 (п)

В этом методе состояния назначаются в двоичной последовательности, где состояния нумеруются, начиная с двоичного 0 и выше. Очевидно, что количество используемых триггеров равно количеству битов (b). Поскольку двоичное кодирование использует минимальное количество битов (триггеров) для кодирования машины, триггеры используются максимально. В результате для декодирования каждого состояния требуется больше комбинаторной логики по сравнению с One Hot. Требует меньше шлепанцев по сравнению с One hot, но расстояние Хэмминга может быть хуже, чем количество бит (b).

В коде Грея, также известном как отраженный двоичный код, состояния назначаются так, что последовательные коды состояний отличаются только на один бит. В этом кодировании также соотношение между количеством битов и количеством состояний определяется следующим образом:

   б = log2 (п)

Количество используемых триггеров и сложность логики декодирования такие же, как и при двоичном кодировании. Но расстояние Хэмминга в коде Грея всегда 1.

  • Другие методы кодирования

Кодирование на основе вывода, MUSTANG,[3] НОВАЯ ЗВЕЗДА,[4]

Мотивация

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

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

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

Методы

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

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

Назначение состояния с несколькими кодами

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

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

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

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

Другие техники

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

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

Рекомендации

  1. ^ а б М. Педрам и А. Абдоллахи, «Методы синтеза с низким энергопотреблением на уровне RT: учебное пособие»
  2. ^ а б Девадас и Малик, «Обзор методов оптимизации, нацеленных на схемы СБИС малой мощности», DAC 32, 1995, стр. 242–247.
  3. ^ С. Девадас и др., «MUSTANG: Назначение состояний конечным машинам, нацеленным на многоуровневые логические реализации», IEEE Trans. Компьютерное проектирование, Vol. САД-7, № 12, декабрь 1988 г., стр.129@1300
  4. ^ Т. Вилла, А. С. Винсентелл, «NOVA: назначение состояний конечных автоматов для оптимальной реализации двухуровневой логики», IEEE-транзакции в САПР. VOL. 9 НЕТ. 9. Сентябрь 1990 г., стр. 905–924.
  5. ^ Л. Бенини и Г. Де Микели, "Государственное задание по рассеиванию малой мощности", IEEE J. Solid-State Circuits, vol. 30, нет. 3, 1995, стр. 258–268.
  6. ^ X. Ву, М. Педрам и Л. Ван, Назначение нескольких кодов состояний для проектирования с низким энергопотреблением, Протоколы IEEE - Схемы, Устройства и системы, Vol. 147, No. 5, pp. 271–275, октябрь 2000 г.
  7. ^ http://mmc.tudelft.nl/sites/default/files/eggermont.pdf
  8. ^ К. Рой и С. Прасад. SYCLOP: синтез логики CMOS для приложений с низким энергопотреблением. В материалах Международной конференции по компьютерному дизайну: СБИС в компьютерах и процессорах, страницы 464–467, октябрь 1992 г.
  9. ^ C-Y Tsui, M Pedram, C-A Chen и AM Despain. Назначение состояния с низким энергопотреблением, ориентированное на двух- и многоуровневые логические реализации. В материалах Международной конференции по автоматизированному проектированию, страницы 82–87, ноябрь 1994 г.
  10. ^ Г. Д. Хахтель, М. Гермида, А. Пардо, М. Пончино и Ф. Соменци. Повторное кодирование последовательных цепей для уменьшения рассеиваемой мощности. In Proceedings of the International Conference on Computer Aided Design, страницы 70–73, ноябрь 1994 г.
  11. ^ W. Noth и R. Kolla «Кодирование состояния на основе связующего дерева для рассеивания малой мощности», Proceedings of DATE, pp. 168. Март 1999 г.
  12. ^ а б c d https://web.archive.org/web/20170828233431/http://home.deib.polimi.it/silvano/Paperi_IEEE/ch7.pdf
  13. ^ J.C. Монтейро и А.Л. Оливейра, «Неявное fsm-разложение применительно к маломощным проектам», IEEE Trans. Система СБИС, т. 10, № 5, с. 560-565, 2002 г.
  14. ^ S.H. Чоу, Ю. Хо, Т. Хван и К.Л. Лю, "Реализация конечных автоматов с низким энергопотреблением - подход декомпозиции", ACM Trans. Design Automat. Избрать. Syst., Vol.1, no.3, pp.315-340, июль 1996.