Hispanopedia WikiLa 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 tecnológico, la densidad y la velocidad de los circuitos integrados han aumentado exponencialmente. Con ello, la disipación de potencia 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 potencia como un parámetro crítico durante el diseño. [ 1 ] [ 2 ]
Fondo
La síntesis de FSM implica tres pasos principales:
- Minimización de estados: Como su nombre indica, se minimiza el número de estados necesarios para representar una máquina de estados finitos (FSM). Diversas técnicas y algoritmos, como tablas de implicación , coincidencia de filas y particionamiento sucesivo, identifican y eliminan estados equivalentes o redundantes.
- La asignación o codificación de estados implica elegir representaciones booleanas de los estados internos de la máquina de estados finitos (FSM). En otras palabras, asigna un código binario único a cada estado. Seleccionar la técnica de codificación adecuada es fundamental, ya que una decisión errónea puede resultar en una FSM que utilice demasiada área lógica, sea demasiado lenta, consuma demasiada energía o presente cualquier combinación de estos problemas.
- La minimización de la lógica combinacional utiliza códigos de estado no asignados como estados indiferentes para reducir la lógica combinacional .
Técnicas de codificación existentes
A continuación se presentan algunas de las técnicas más utilizadas para la codificación de estados:
- En la codificación one-hot , solo uno de los bits de la variable de estado es "1" (activo) para cada estado. Todos los demás bits son "0". La distancia de Hamming de esta técnica es 2. La codificación one-hot requiere un flip-flop para cada estado en la máquina de estados finitos (FSM). Como resultado, la máquina de estados ya está "decodificada", por lo que su estado se determina simplemente identificando qué flip-flop está activo. Esta técnica de codificación reduce la amplitud de la lógica combinacional y, por consiguiente, la máquina de estados requiere menos niveles de lógica entre registros, lo que reduce su complejidad y aumenta 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 se define mediante la ecuación b = log₂ ( n ) . En esta técnica, los estados se asignan en una secuencia binaria donde se numeran desde 0 hacia arriba. El número de flip-flops utilizados 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 combinacional para decodificar cada estado en comparación con la codificación one-hot. La codificación binaria requiere menos flip-flops que la codificación one-hot, pero las distancias de Hamming pueden ser peores, hasta el número de bits ( b ).
- En la codificación Gray , también conocida como codificación binaria reflejada, los estados se asignan de manera que los códigos de estado consecutivos difieran en un solo bit. En esta codificación, la relación entre el número de bits y el número de estados se define mediante b = log₂ ( n ) . El número de biestables utilizados y la complejidad de la lógica de decodificación son los mismos que en la codificación binaria, pero la distancia de Hamming en la codificación Gray siempre es 1.
Otras técnicas de codificación incluyen la codificación basada en la salida, MUSTANG, [ 3 ] y NOVA. [ 4 ]
Motivación
La idea principal en el diseño de la codificación de estado para bajo consumo de energía 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 costo para minimizar el consumo de energía consiste en tener una distancia de Hamming ponderada mínima (MWHD). [ 1 ] [ 2 ]
Para contadores, la codificación Gray proporciona una actividad de conmutación mínima, por lo que resulta adecuada para diseños de bajo consumo. La codificación Gray es la más apropiada para casos donde los cambios de estado son secuenciales. En cambios de estado arbitrarios, el código Gray de las máquinas de estados finitos (FSM) no resulta adecuado para un diseño de bajo consumo. Para tales FSM, la codificación one-hot garantiza la conmutación de dos bits por cada cambio de estado. Sin embargo, dado que el número de variables de estado necesarias es igual al número de estados, a medida que estos aumentan, 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 en el circuito, la complejidad y la carga capacitiva aumentan. La codificación binaria es la peor opción para bajo consumo, ya que la distancia de Hamming máxima es igual al número de variables de estado.
La necesidad de contar con una solución para máquinas de estados finitos con cambios de estado arbitrarios ha dado lugar 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 baja potencia
Este enfoque busca reducir la disipación de potencia en circuitos secuenciales mediante la asignación de estados que minimicen la actividad de conmutación entre transiciones de estado. De esta manera, la parte combinacional de la máquina de estados finitos (FSM) presenta una menor probabilidad de transición de entrada y, por lo tanto, una menor disipación de potencia al ser sintetizada. Este algoritmo utiliza una matriz booleana con filas que corresponden a códigos de estado y columnas que corresponden a variables de estado. Se considera una variable de estado a la vez, y el algoritmo intenta asignar su valor a cada estado de la FSM de manera que se minimice la actividad de conmutación para la asignación completa. Este procedimiento se repite para la siguiente variable. Dado que esta técnica de minimización se aplica columna por columna, se denomina enfoque basado en columnas. [ 5 ]
Asignación de estado multicódigo
La técnica de asignación de estados multicódigo implementa la codificación de prioridad al restringir los estados redundantes. De esta manera, un estado puede codificarse utilizando menos variables de estado (bits). Además, los flip-flops correspondientes a esas variables de estado ausentes pueden controlarse mediante reloj. [ 6 ]
Asignación de estados basada en perfiles
Esta técnica utiliza información dinámica de bucles extraída de datos de perfilado de FSM para la asignación de estados con el fin de reducir la actividad de conmutación. El procedimiento es el siguiente: [ 7 ]
- El análisis del estado de la máquina de estados finitos (FSM) recopila información sobre el comportamiento dinámico de la FSM para un conjunto de datos de entrada relevante .
- Un detector de bucles busca bucles en el registro de estado, y cada bucle se almacena y se cuenta para obtener la frecuencia de los bucles.
- La asignación de estados asigna variables de estado a cada estado en función de los datos recopilados en los dos primeros pasos con el fin de minimizar la actividad de conmutación. Existen tres algoritmos para asignar variables de estado:
- Algoritmo básico de asignación de estados DFS
- Algoritmo de asignación de estados DFS basado en bucles
- Algoritmo heurístico de asignación de estados por estado basado en bucles
Otras técnicas
- Algunas técnicas codifican grafos de transición de estados (STG) para producir implementaciones de dos niveles y multinivel orientadas a un bajo consumo de energía. [ 8 ] [ 9 ]
- Se ha propuesto la recodificación de circuitos secuenciales de nivel lógico existentes para optimizar el consumo de energía. [ 10 ]
- Codificación de estado basada en árbol de expansión [ 11 ]
- Métodos de búsqueda en profundidad [ 12 ]
- Métodos de distancia mínima [ 12 ]
- métodos de 1 nivel [ 12 ]
- Método de árbol de 1 nivel, [ 12 ] donde el enfoque se centra nuevamente en asignar variables de estado a los diferentes estados de manera que se reduzca la actividad de conmutación debida a la transición de estado.
- Además de codificar estados para bajo consumo de energía, algunas técnicas implican la descomposición de la máquina de estados finitos (FSM) en dos o más submáquinas, de modo que solo una esté activa la mayor parte del tiempo. La otra submáquina puede estar controlada por reloj [ 13 ] o por alimentación [ 14 ] .
Véase también
Referencias
- 1 2 M. Pedram y A. Abdollahi, “Técnicas de síntesis de nivel RT de baja potencia: un tutorial”
- 1 2 Devadas y Malik, “Un estudio de las 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 orientadas a implementaciones lógicas multinivel”, IEEE Trans. Computer-Aided Design, vol. CAD-7, n.º 12, dic. 1988, pp. 129-1300
- ↑ T. Villa, AS Vincentell, “NOVA: Asignación de estados de máquinas de estados finitos para la implementación óptima de lógica de dos niveles”, Transacciones IEEE sobre CAD. VOL. 9 N.° 9. Septiembre de 1990, págs. 905-924
- ↑ L. Benini y G. De Micheli, "Asignación de estados para baja disipación de potencia", IEEE J. Solid-State Circuits, vol. 30, n.º 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 bajo consumo, IEEE Proceedings-Circuits, Devices and Systems, Vol. 147, No. 5, pp. 271–275, octubre de 2000.
- ↑ "Computación multimedia" (PDF) . mmc.tudelft.nl . Consultado el 17 de diciembre de 2024 .
- ↑ K Roy y S Prasad. SYCLOP: Síntesis de lógica CMOS para aplicaciones de bajo consumo. En Actas de la Conferencia Internacional sobre Diseño de Computadoras: VLSI en Computadoras y Procesadores, páginas 464–467, octubre de 1992.
- ↑ CY Tsui, M Pedram, CA Chen y AM Despain. Asignación de estados de bajo consumo para implementaciones lógicas de dos y múltiples niveles. En Actas de la Conferencia Internacional sobre Diseño Asistido por Computadora, 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 potencia. 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 potencia”, Actas de DATE, pág. 168, marzo de 1999.
- 1 2 3 4 "Copia archivada" (PDF) . home.deib.polimi.it . Archivado del original (PDF) el 28 de agosto de 2017 . Recuperado el 15 de enero de 2022 .
{{cite web}}: CS1 mantenimiento: copia archivada como título ( enlace ) - ↑ JC Monteiro y AL Oliveira, "Descomposición implícita de FSM aplicada al diseño de bajo consumo", IEEE Trans. VLSI Syst., vol. 10, n.º 5, págs. 560-565, 2002
- ↑ SH Chow, YC Ho, T. Hwang y CL Liu, "Realización de bajo consumo de energía de máquinas de estados finitos: un enfoque de descomposición", ACM Trans. Design Automat. Elect. Syst., vol. 1, n.º 3, págs. 315-340, julio de 1996.
- Autómatas (computación)