La codificación de estado asigna un patrón único de unos y ceros a cada estado definido de una máquina de estados finitos (FSM). Tradicionalmente, los criterios de diseño para la síntesis de FSM eran la velocidad, el área o ambos. Siguiendo la ley de Moore , con el avance de la tecnología, la densidad y la velocidad de los circuitos integrados han aumentado exponencialmente. Con esto, la disipación de energía por área ha aumentado inevitablemente, lo que ha obligado a los diseñadores de dispositivos informáticos portátiles y procesadores de alta velocidad a considerar la disipación de energía como un parámetro crítico durante la consideración del diseño. [1] [2]
Fondo
La síntesis de FSM implica tres pasos principales:
- Minimización de estados: como sugiere el nombre, se minimiza el número de estados necesarios para representar FSM. Varias técnicas y algoritmos, como tablas de implicaciones , coincidencia de filas y algoritmo de particiones sucesivas, identifican y eliminan estados equivalentes o redundantes.
- La asignación o codificación de estados implica elegir representaciones booleanas de los estados internos de FSM. En otras palabras, asigna un código binario único a cada estado. La selección de la técnica de codificación correcta es muy crítica. Dado que una decisión incorrecta puede resultar en un FSM que usa demasiada área lógica, es demasiado lento, consume demasiada energía o cualquier combinación de estos.
- La minimización de la lógica combinacional utiliza códigos de estado no asignados como no importa para reducir la lógica combinacional.
Técnicas de codificación existentes
A continuación se muestran algunas de las técnicas que se utilizan ampliamente para la codificación de estados:
- En una codificación en caliente , solo uno de los bits de la variable de estado es "1" (activo) para cualquier estado dado. Todos los demás bits son "0". La distancia de Hamming de estas técnicas es 2. Un hot requiere un flip-flop para cada estado en FSM. Como resultado, la máquina de estado ya está "decodificada", por lo que el estado de la máquina se determina simplemente averiguando qué flip-flop está activo. Esta técnica de codificación reduce el ancho de la lógica combinatoria y, como resultado, la máquina de estados requiere menos niveles de lógica entre registros, reduciendo su complejidad y aumentando su velocidad.
- En la codificación binaria , el número de bits (b) por estado depende del número de estados (n). La relación está definida por la ecuación:
b = log2 (n)
En esta técnica, los estados se asignan en secuencia binaria donde los estados se numeran comenzando desde el 0 binario en adelante. Claramente, el número de flip-flops usados es igual al número de bits (b). Dado que la codificación binaria utiliza el número mínimo de bits (flip-flops) para codificar una máquina, los flip-flops se utilizan al máximo. Como resultado, se requiere más lógica combinatoria para decodificar cada estado en comparación con One Hot. Requiere menos flip-flops en comparación con One hot, pero la distancia de martilleo puede ser tan peor como el número de bits (b).
En el código Gray, también conocido como código binario reflejado, los estados se asignan de manera que los códigos de estado consecutivos difieran solo en un bit. En esta codificación también la relación entre el número de bits y el número de estados está definida por
b = log2 (n)
El número de flips-flops utilizados y la complejidad de la lógica de decodificación es la misma que la de la codificación binaria. Pero la distancia de martillo en el código Gray es siempre 1.
- Otras técnicas de codificación
Motivación
La idea principal en el diseño de la codificación de estado para baja potencia es minimizar la distancia de Hamming de las transiciones de estado más probables, lo que reduce la actividad de conmutación. Por lo tanto, un modelo de costos para minimizar el consumo de energía es tener una distancia de Hamming ponderada mínima (MWHD). [1] [2]
Para los contadores, la codificación gris proporciona una actividad de conmutación mínima y, por lo tanto, es adecuada para diseños de baja potencia. La codificación gris se adapta mejor cuando los cambios de estado son secuenciales. En el cambio de estado arbitrario, el código FSM Gray falla para diseños de bajo consumo. Para tal FSM, la codificación one-hot garantiza la conmutación de dos bits por cada cambio de estado. Pero dado que el número de variables de estado necesarias es igual al número de estados, a medida que aumentan los estados, la codificación one-hot se convierte en una solución poco práctica, principalmente porque con un mayor número de entradas y salidas al circuito, la complejidad y la carga capacitiva aumentan. La codificación binaria es peor para baja potencia ya que la distancia máxima de Hamming es igual al número de variables de estado.
La necesidad de tener una solución para FSM de cambio de estado arbitrario ha llevado a varias técnicas de codificación de estado que se centran en reducir la actividad de conmutación durante las transiciones de estado.
Técnicas
Enfoque basado en columnas para la asignación de estados de bajo consumo
[5] Este enfoque tiene como objetivo reducir la disipación de potencia por circuitos secuenciales eligiendo la asignación de estado que minimiza la actividad de conmutación entre las transiciones de estado. Por lo tanto, la parte combinatoria de FSM tiene una probabilidad de transición de entrada más baja y es más probable que dé una disipación de baja potencia cuando se sintetiza. Este algoritmo utiliza una matriz booleana con filas correspondientes a códigos de estado y columnas correspondientes a variables de estado. La variable de estado único se considera a la vez e intenta asignar su valor a cada estado en FSM, de una manera que probablemente minimice la actividad de conmutación para la asignación completa. Este procedimiento se repite para la siguiente variable. Dado que la técnica de minimización se aplica columna por columna, esta técnica se denomina basada en columna.
Asignación de estado de varios códigos
La técnica de asignación de estados de múltiples códigos implementa la codificación de prioridad al restringir los estados redundantes. Por tanto, el estado se puede codificar utilizando menos variables de estado (bits). Además, los flip-flops correspondientes a las variables de estado ausentes se pueden controlar por reloj. [6]
Asignación de estado basada en perfiles
[7] Esta técnica utiliza información de bucle dinámico extraída de los datos de perfiles FSM para la asignación de estados con el fin de reducir la actividad de conmutación. Los siguientes son los pasos que utiliza esta técnica:
- El perfil de estado de FSM recopila información sobre el comportamiento dinámico de FSM para un conjunto de datos de entrada relevante
- La detección de bucles busca bucles en la traza de estado y cada bucle se almacena y se cuenta para obtener la frecuencia de los bucles.
- La asignación de estado asigna variables de estado a cada estado en función de los datos recopilados en los dos primeros pasos para minimizar la actividad de conmutación. Hay tres algoritmos para asignar variables de estado,
- Algoritmo básico de asignación de estados DFS
- Algoritmo de asignación de estado DFS basado en bucle
- Algoritmo de asignación de estado heurístico por estado basado en bucles
Otras tecnicas
- Algunas técnicas codifican el gráfico de transición de estado (STG) para producir implementaciones de dos y múltiples niveles dirigidas a la baja potencia [8] [9]
- Se ha propuesto la recodificación de circuitos secuenciales de nivel lógico existentes para optimizar la potencia [10].
- Abarcando codificación estado basada en árbol, [11] Método Depth_First, [12] Método mínima distancia, [12] Método 1_Level, [12] 1_level_tree Método, [12] donde se centra de nuevo sobre la asignación de las variables de estado para los diferentes estados tal que la conmutación la actividad debido a la transición de estado se reduce.
- Aparte de solo codificar estados para baja potencia, algunas técnicas implican la descomposición de FSM en dos o más submáquinas, de modo que solo una de las cuales está activa la mayor parte del tiempo. Aprovechando esto, otras sub-máquinas pueden ser controladas por reloj [13] o por energía. [14]
Ver también
Referencias
- ^ a b M. Pedram y A Abdollahi, "Técnicas de síntesis de nivel RT de baja potencia: un tutorial"
- ^ a b Devadas & Malik, "Un estudio de técnicas de optimización dirigidas a circuitos VLSI de baja potencia", DAC 32, 1995, págs. 242–247
- ^ S. Devadas et al., “MUSTANG: Asignación de estados de máquinas de estados finitos dirigidas a implementaciones lógicas multinivel”, IEEE Trans. Diseño asistido por computadora, vol. CAD-7, No. 12, diciembre de 1988, pp.129@1300
- ^ T. Villa, AS Vincentell, "NOVA: Asignación de estado de máquinas de estado finito para una implementación lógica de dos niveles óptima", transacciones IEEE en CAD. VOL. 9 NO. 9. Septiembre de 1990, págs. 905-924
- ^ L. Benini y G. De Micheli, "Asignación de estado para disipación de baja potencia", IEEE J. Circuitos de estado sólido, vol. 30, no. 3, 1995, págs. 258–268
- ^ X. Wu, M. Pedram y L. Wang, Asignación de estados de código múltiple para diseño de baja potencia, IEEE Proceedings-Circuits, Devices and Systems, vol. 147, núm. 5, págs. 271-275, octubre de 2000.
- ^ http://mmc.tudelft.nl/sites/default/files/eggermont.pdf
- ^ K Roy y S Prasad. SYCLOP: Síntesis de la lógica CMOS para aplicaciones de baja potencia. En Proceedings of the Int'l Conference on Computer Design: VLSI in Computers and Processors, páginas 464–467, octubre de 1992
- ^ CY Tsui, M Pedram, CA Chen y AM Despain. Asignación de estado de bajo consumo con destino a implementaciones lógicas de dos y varios niveles. En Proceedings of the Int'l Conference on Computer-Aided Design, páginas 82–87, noviembre de 1994.
- ^ GD Hachtel, M Hermida, A Pardo, M Poncino y F Somenzi. Recodificación de circuitos secuenciales para reducir la disipación de energía. En Actas de la Conferencia Internacional sobre Diseño Asistido por Computadora, páginas 70–73, noviembre de 1994
- ^ W. Noth y R. Kolla "Codificación de estado basada en árbol de expansión para baja disipación de energía", Actas de DATE, págs. 168. Marzo de 1999
- ^ a b c d https://web.archive.org/web/20170828233431/http://home.deib.polimi.it/silvano/Paperi_IEEE/ch7.pdf
- ^ JC Monteiro y AL Oliveira, "Descomposición de fsm implícita aplicada al diseño de baja potencia", IEEE Trans. VLSI Syst., Vol. 10, núm. 5, págs. 560-565, 2002
- ^ SH Chow, YC Ho, T. Hwang y CL Liu, "Realización de baja potencia de máquinas de estados finitos: un enfoque de descomposición", ACM Trans. Design Automat. Electo. Syst., Vol. 1, no 3, págs. 315-340, julio de 1996.