Reprogramación

El retiming es la técnica de mover la ubicación estructural de los pestillos o registros en un circuito digital para mejorar sus características de rendimiento, área y/o potencia de tal manera que se preserve su comportamiento funcional en sus salidas. El retiming fue descrito por primera vez por Charles E. Leiserson y James B. Saxe en 1983. ^[1]

La técnica utiliza un gráfico dirigido donde los vértices representan bloques combinacionales asincrónicos y los bordes dirigidos representan una serie de registros o pestillos (el número de registros o pestillos puede ser cero). Cada vértice tiene un valor correspondiente al retraso a través del circuito combinacional que representa. Después de hacer esto, uno puede intentar optimizar el circuito empujando registros de salida a entrada y viceversa, de manera muy similar al empuje de burbujas . Se pueden utilizar dos operaciones: eliminar un registro de cada entrada de un vértice mientras se agrega un registro a todas las salidas y, a la inversa, agregar un registro a cada entrada de vértice y eliminar un registro de todas las salidas. En todos los casos, si se siguen las reglas, el circuito tendrá el mismo comportamiento funcional que tenía antes de la resincronización.

Descripción formal

La formulación inicial del problema de resincronización descrita por Leiserson y Saxe es la siguiente. Dado un gráfico dirigido cuyos vértices representan puertas lógicas o elementos de retardo combinacional en un circuito, suponga que hay un borde dirigido entre dos elementos que están conectados directamente o a través de uno o más registros. Sea el peso de cada borde el número de registros presentes a lo largo del borde en el circuito inicial. Sea el retardo de propagación a través del vértice . El objetivo en la resincronización es calcular un valor de retardo entero para cada vértice de modo que el peso resincronizado de cada borde no sea negativo. Hay una prueba de que esto preserva la funcionalidad de salida. ^[2] ${\displaystyle G:=(V,E)}$ ${\displaystyle e:=(u,v)}$ ${\displaystyle w(e)}$ ${\displaystyle e}$ ${\displaystyle d(v)}$ ${\displaystyle v}$ ${\displaystyle r(v)}$ ${\displaystyle w_{r}(e):=w(e)+r(v)-r(u)}$

Minimizar el período de reloj con flujo de red

El uso más común de la reprogramación es minimizar el período de reloj . Una técnica sencilla para optimizar el período de reloj es buscar el período mínimo factible (por ejemplo, mediante una búsqueda binaria ).

La viabilidad de un periodo de reloj se puede comprobar de varias formas. El programa lineal siguiente es factible si y solo si es un periodo de reloj factible. Sea el número mínimo de registros a lo largo de cualquier camino desde a (si existe dicho camino), y es el retardo máximo a lo largo de cualquier camino desde a con W(u,v) registros. El dual de este programa es un problema de circulación de coste mínimo , que se puede resolver de forma eficiente como un problema de red. Las limitaciones de este enfoque surgen de la enumeración y el tamaño de las matrices y . ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle W(u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle D(u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle W}$ ${\displaystyle D}$

Minimizar el período de reloj con MILP

Alternativamente, la viabilidad de un período de reloj se puede expresar como un programa lineal entero mixto (MILP). Existirá una solución y se devolverá una función de retardo válida si y solo si el período es factible. ${\displaystyle T}$ ${\displaystyle r(v)}$

Otras formulaciones y extensiones

Las formulaciones alternativas permiten minimizar el número de registros y minimizar el número de registros bajo una restricción de retardo. El artículo inicial incluye extensiones que permiten considerar la compartición de abanicos y un modelo de retardo más general. El trabajo posterior ha abordado la inclusión de retardos de registros, ^[3] modelos de retardo dependientes de la carga, ^[3] y restricciones de retención. ^[4]

Problemas

La reprogramación ha encontrado un uso industrial, aunque esporádico. Su principal inconveniente es que se destruye la codificación de estado del circuito, lo que dificulta considerablemente la depuración, las pruebas y la verificación. Algunas reprogramaciones también pueden requerir una lógica de inicialización complicada para que el circuito comience en un estado inicial idéntico. Por último, los cambios en la topología del circuito tienen consecuencias en otros pasos de síntesis lógica y física que dificultan el cierre del diseño .

Alternativas

La programación desfasada del reloj es una técnica relacionada para optimizar circuitos secuenciales. Mientras que la reprogramación reubica la posición estructural de los registros, la programación desfasada del reloj mueve su posición temporal programando el tiempo de llegada de las señales del reloj. El límite inferior del período de reloj mínimo alcanzable de ambas técnicas es el tiempo de ciclo medio máximo (es decir, el retraso combinacional total a lo largo de cualquier ruta dividido por el número de registros a lo largo de ella).

Véase también

• Síntesis lógica
• Automatización del diseño electrónico

Notas

1. Charles E. Leiserson, Flavio M. Rose, James B. Saxe (1983). "Optimización de circuitos síncronos mediante resincronización". Tercera conferencia de Caltech sobre integración a muy gran escala . Springer: 87–116. doi :10.1007/978-3-642-95432-0_7.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
2. Charles E. LeisersonJames B. Saxe (junio de 1991). "Reprogramación de circuitos síncronos". Algorítmica . 6 (1). Saltador: 5–35. doi :10.1007/BF01759032. S2CID  18674287.
3. KN Lalgudi, MC Papaefthymiou, Resincronización de circuitos disparados por flanco bajo modelos de retardo general, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 16, n.º 12, pp. 1393-1408, diciembre de 1997.
4. MC Papaefthymiou, Resincronización asintóticamente eficiente bajo restricciones de configuración y retención, Conferencia internacional IEEE/ACM sobre diseño asistido por computadora, 1998.

Referencias

• Leiserson, 1C. E.; Saxe, JB (1983). "Optimización de sistemas síncronos". Revista de VLSI y sistemas informáticos . 1 (1): 41–67.{{cite journal}}: CS1 maint: nombres numéricos: lista de autores ( enlace )

Enlaces externos

• Presentación sobre reprogramación del MIT
• Un algoritmo de resincronización de registros a nivel de puerta seguro y completo