Кодирование состояния для малой мощности
Кодирование состояний присваивает уникальный шаблон единиц и нулей каждому определенному состоянию конечного автомата (FSM). Традиционно критериями проектирования для синтеза конечных автоматов были скорость, площадь или и то, и другое. Следуя закону Мура , с развитием технологий плотность и скорость интегральных схем возрастают в геометрической прогрессии. При этом рассеиваемая мощность на площадь неизбежно увеличилась, что заставило разработчиков портативных вычислительных устройств и высокоскоростных процессоров рассматривать рассеиваемую мощность как критический параметр при рассмотрении проекта. [1] [2]
Фон
[ редактировать ]Синтез FSM включает три основных этапа:
- Минимизация состояний. Как следует из названия, количество состояний, необходимых для представления FSM, сведено к минимуму. Различные методы и алгоритмы, такие как таблицы импликаций , сопоставление строк и алгоритм последовательного разделения, идентифицируют и удаляют эквивалентные или избыточные состояния.
- Присвоение или кодирование состояния предполагает выбор логических представлений внутренних состояний автомата. Другими словами, каждому состоянию присваивается уникальный двоичный код. Выбор правильной техники кодирования очень важен. Поскольку неправильное решение может привести к тому, что автомат будет использовать слишком большую логическую область, будет работать слишком медленно, потреблять слишком много энергии или к любой комбинации этих факторов.
- Минимизация комбинационной логики использует неназначенные коды состояния как ненужные, чтобы уменьшить комбинационную логику.
Существующие методы кодирования
[ редактировать ]Ниже приведены некоторые методы, которые широко используются для кодирования состояния:
- В одном горячем кодировании только один из битов переменной состояния равен «1» (горячее) для любого заданного состояния. Все остальные биты равны «0». Расстояние Хэмминга в этом методе равно 2. Для одного горячего требуется один триггер для каждого состояния в автомате. В результате конечный автомат уже «декодирован», поэтому состояние автомата определяется просто путем выяснения, какой триггер активен. Этот метод кодирования уменьшает ширину комбинаторной логики и, как следствие, конечному автомату требуется меньше уровней логики между регистрами, что снижает его сложность и увеличивает его скорость.
- В двоичном кодировании количество битов (b) на состояние зависит от количества состояний (n). Связь определяется уравнением:
b = log2(n)
В этом методе состояния назначаются в двоичной последовательности, где состояния нумеруются, начиная с двоичного 0 и выше. Очевидно, что количество используемых триггеров равно количеству битов (b). Поскольку двоичное кодирование использует минимальное количество битов (триггеров) для кодирования машины, триггеры используются максимально. В результате для декодирования каждого состояния требуется больше комбинаторной логики по сравнению с One Hot. Требует меньше триггеров по сравнению с One hot, но расстояние Хэмминга может быть таким же плохим, как и количество битов (b).
В коде Грея, также известном как отраженный двоичный код, состояния назначаются таким образом, что последовательные коды состояний отличаются только на один бит. В этой кодировке также соотношение между количеством битов и количеством состояний определяется формулой
b = log2(n)
Количество используемых триггеров и сложность логики декодирования такие же, как у двоичного кодирования. Но расстояние Хэмминга в коде Грея всегда равно 1.
- Другие методы кодирования
Кодирование на основе вывода, MUSTANG, [3] НОВЫЙ, [4]
Мотивация
[ редактировать ]Основная идея разработки кодирования состояний для малой мощности состоит в том, чтобы минимизировать расстояние Хэмминга наиболее вероятных переходов состояний, что снижает активность переключения. Таким образом, стоимостная модель минимизации энергопотребления должна иметь минимально взвешенное расстояние Хэмминга (MWHD). [1] [2]
Для счетчиков кодирование Грея обеспечивает минимальную коммутационную активность и, следовательно, подходит для конструкций с низким энергопотреблением. Кодировка Грея лучше всего подходит, когда изменения состояния являются последовательными. При произвольном изменении состояния код FSM Грея не работает для конструкций с низким энергопотреблением. Для такого автомата горячее кодирование гарантирует переключение двух битов при каждом изменении состояния. Но поскольку количество необходимых переменных состояния равно количеству состояний, по мере увеличения состояний горячее кодирование становится непрактичным решением, главным образом потому, что с увеличением количества входов и выходов схемы увеличивается сложность и емкостная нагрузка. Двоичное кодирование хуже всего подходит для малой мощности, поскольку максимальное расстояние Хэмминга равно количеству переменных состояния.
Необходимость иметь решение для произвольного изменения состояния FSM привела к появлению нескольких методов кодирования состояний, которые направлены на уменьшение активности переключения во время переходов между состояниями.
Техники
[ редактировать ]Столбцовый подход для назначения состояний малой мощности
[ редактировать ][5] Этот подход направлен на уменьшение рассеяния мощности последовательными цепями за счет выбора назначения состояний, которое сводит к минимуму коммутационную активность между переходами состояний. Таким образом, комбинационная часть FSM имеет меньшую вероятность входного перехода и больше склонна обеспечивать низкое рассеивание мощности при синтезе. Этот алгоритм использует логическую матрицу со строками, соответствующими кодам состояния, и столбцом, соответствующим переменным состояния. Переменная одного состояния рассматривается одновременно и пытается присвоить ее значение каждому состоянию в FSM таким образом, чтобы минимизировать активность переключения для полного назначения. Эта процедура повторяется для следующей переменной. Поскольку метод минимизации применяется столбец за столбцом, этот метод называется «на основе столбцов».
Назначение состояния нескольких кодов
[ редактировать ]Метод назначения состояний мультикода реализует приоритетное кодирование, ограничивая избыточные состояния. Таким образом, состояние может быть закодировано с использованием меньшего количества переменных состояния (битов). Кроме того, триггеры, соответствующие отсутствующим переменным состояния, могут быть синхронизированы. [6]
Назначение состояний на основе профилирования
[ редактировать ][7] Этот метод использует информацию динамического цикла, извлеченную из данных профилирования FSM, для назначения состояний, чтобы уменьшить активность переключения. Ниже приведены шаги, которые использует этот метод:
- Профилирование состояния автомата собирает информацию о динамическом поведении автомата для соответствующего набора входных данных.
- Обнаружение петель ищет петли в трассировке состояния, каждая петля сохраняется и подсчитывается для получения частоты петель.
- При назначении состояний каждому состоянию присваиваются переменные состояния на основе данных, собранных на первых двух шагах, чтобы минимизировать активность переключения. Существует три алгоритма назначения переменных состояния:
- Базовый алгоритм назначения состояния DFS
- Алгоритм назначения состояния DFS на основе цикла
- Алгоритм эвристического назначения состояний для каждого состояния на основе цикла
Другие методы
[ редактировать ]- Некоторые методы кодируют граф перехода состояний (STG) для создания двухуровневых и многоуровневых реализаций, ориентированных на малое энергопотребление. [8] [9]
- Было предложено перекодирование существующих последовательных схем логического уровня для оптимизации энергопотребления. [10]
- Кодирование состояния на основе дерева, [11] Метод Depth_First, [12] Метод минимального расстояния, [12] Метод 1_Level, [12] метод 1_level_tree, [12] где основное внимание снова уделяется присвоению переменных состояния различным состояниям, чтобы уменьшить активность переключения из-за перехода состояний.
- Помимо простого кодирования состояний для малой мощности, некоторые методы включают разложение FSM на две или более субмашин, из которых большую часть времени активен только один. Воспользовавшись этим, другая субмашина может быть либо синхронизирована, либо [13] или с электроприводом. [14]
См. также
[ редактировать ]- Кодирование шины
- Минимизация DFA
- Логический синтез
- Маломощная электроника
- Уровень регистрации-передачи
Ссылки
[ редактировать ]- ^ Перейти обратно: а б М. Педрам и А. Абдоллахи, «Методы синтеза маломощного RT-уровня: учебное пособие»
- ^ Перейти обратно: а б Девадас и Малик, «Обзор методов оптимизации, ориентированных на схемы СБИС малой мощности», DAC 32, 1995, стр. 242–247.
- ^ С. Девадас и др., «МУСТАНГ: присвоение состояний конечных автоматов, ориентированных на многоуровневые логические реализации», IEEE Trans. Компьютерное проектирование, Vol. CAD-7, № 12, декабрь 1988 г., стр. 129@1300.
- ^ Т. Вилла, А.С. Винсентелл, «NOVA: назначение состояний конечных автоматов для оптимальной реализации двухуровневой логики», Транзакции IEEE в САПР. ОБЪЕМ. 9 НЕТ. 9. Сентябрь 1990 г., стр. 905-924.
- ^ Л. Бенини и Г. Де Микели, «Назначение состояний для малой рассеиваемой мощности», IEEE J. Solid-State Circuits, vol. 30, нет. 3, 1995, стр. 258–268.
- ^ X. Ву, М. Педрам и Л. Ван, Назначение состояний нескольких кодов для проектирования с низким энергопотреблением, IEEE Proceedings-Circuits, Devices and Systems, Vol. 147, № 5, стр. 271–275, октябрь 2000 г.
- ^ http://mmc.tudelft.nl/sites/default/files/eggermont.pdf [ только URL-адрес PDF ]
- ^ К. Рой и С. Прасад. SYCLOP: синтез логики КМОП для приложений с низким энергопотреблением. В материалах Международной конференции по компьютерному дизайну: СБИС в компьютерах и процессорах, страницы 464–467, октябрь 1992 г.
- ^ CY Tsui, M Pedram, CA Chen и AM Despain. Назначение состояний малой мощности для двух- и многоуровневых логических реализаций. В материалах Международной конференции по компьютерному проектированию, страницы 82–87, ноябрь 1994 г.
- ^ Г. Д. Хачтель, М. Эрмида, А. Пардо, М. Пончино и Ф. Соменци. Перекодирование последовательных цепей для уменьшения рассеиваемой мощности. В материалах Международной конференции по автоматизированному проектированию, страницы 70–73, ноябрь 1994 г.
- ^ В. Нот и Р. Колла «Кодирование состояний на основе связующего дерева для малой рассеиваемой мощности», Proceedings of DATE, стр. 168. Март 1999 г.
- ^ Перейти обратно: а б с д «Архивная копия» (PDF) . home.deib.polimi.it . Архивировано из оригинала (PDF) 28 августа 2017 года . Проверено 15 января 2022 г.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ) - ^ Дж. К. Монтейро и А. Л. Оливейра, «Неявное разложение fsm, применяемое к конструкциям с низким энергопотреблением», IEEE Trans. СБИС Системы, том 10, №5, стр.560-565, 2002 г.
- ^ SH Chow, YC Ho, T. Hwang и CL Liu, «Реализация конечных автоматов с низким энергопотреблением - подход декомпозиции», ACM Trans. Проектный автомат. Избрать. Сист., том 1, № 3, стр. 315-340, июль 1996 г.