Reprogramación

La resincronización es la técnica de modificar la ubicación estructural de los biestables o registros en un circuito digital para mejorar su rendimiento, área y/o características de consumo de energía , preservando así su comportamiento funcional en sus salidas. La resincronización fue descrita por primera vez por Charles E. Leiserson y James B. Saxe en 1983. ^{[ 1 ]}

La técnica utiliza un grafo dirigido donde los vértices representan bloques combinacionales asíncronos y las aristas dirigidas representan una serie de registros o biestables (el número de registros o biestables puede ser cero). Cada vértice tiene un valor que corresponde al retardo a través del circuito combinacional que representa. Después de esto, se puede intentar optimizar el circuito moviendo registros de salida a entrada y viceversa, de forma similar al empuje de burbujas . Se pueden usar dos operaciones: eliminar un registro de cada entrada de un vértice mientras se agrega un registro a todas las salidas, y viceversa, agregar un registro a cada entrada de un 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 retemporización.

Descripción formal

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

Minimizar el período de reloj con flujo de red

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

La viabilidad de un período de tiempo $T$ se puede comprobar de varias maneras. El programa lineal que se muestra a continuación es factible si y solo si $T$ es un período de tiempo factible. Dejemos $W(u,v)$ sea el número mínimo de registros a lo largo de cualquier ruta desde $u$ a $v$ (si existe tal camino), y $D(u,v)$ es el retraso máximo a lo largo de cualquier ruta desde $u$ a $v$ con registros W(u,v). El dual de este programa es un problema de circulación de costo mínimo , que puede resolverse eficientemente como un problema de red. Las limitaciones de este enfoque surgen de la enumeración y el tamaño de los registros. $W$ y $D$ matrices.

Minimizar el período de reloj con MILP

Alternativamente, la viabilidad de un período de tiempo $T$ puede expresarse como un programa lineal de enteros mixtos (MILP). Existirá una solución y una función de retardo válida. $r(v)$ Se devolverá solo si el plazo es factible.

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 el reparto de ramificación y un modelo de retardo más general. Trabajos posteriores han abordado la inclusión de retardos de registro, ^{[ 3 ]} modelos de retardo dependientes de la carga, ^{[ 3 ]} y restricciones de retención. ^{[ 4 ]}

Problemas

La modificación de la temporización se ha utilizado en la industria, aunque de forma esporádica. Su principal inconveniente es que se destruye la codificación del estado del circuito, lo que dificulta considerablemente la depuración, las pruebas y la verificación. Algunas modificaciones de temporización también pueden requerir una lógica de inicialización compleja 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, lo que dificulta el cierre del diseño .

Alternativas

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

Véase también

Notas

↑ Leiserson, Charles E.; Rose, Flavio M.; Saxe, James B. (1983). "Optimizing Synchronous Circuitry by Retiming (Preliminary Version)". Third Caltech Conference on Very Large Scale Integration . Springer. pp. 87–116 . doi : 10.1007/978-3-642-95432-0_7 . ISBN 978-3-540-12369-9.
↑ Leiserson, Charles E.; Saxe, James B. (junio de 1991). "Resincronización de circuitos síncronos". Algorithmica . 6 (1). Springer: 5–35 . doi : 10.1007/BF01759032 . S2CID 18674287 .
1 2 Lalgudi, KN; Papaefthymiou, MC (1997). "Resincronización de circuitos activados por flanco bajo modelos de retardo generales". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 16 (12): 1393– 1408. doi : 10.1109/43.664222 .
↑ Papaefthymiou, Marios C. (1998). "Resincronización asintóticamente eficiente bajo restricciones de configuración y retención". Actas de la conferencia internacional IEEE/ACM de 1998 sobre diseño asistido por ordenador - ICCAD '98 . págs. 396–401 . doi : 10.1145/288548.289060 . ISBN 1-58113-008-2.

Referencias

Leiserson, Charles E.; Saxe, James B. (1981). "Optimización de sistemas síncronos". 22º Simposio Anual sobre Fundamentos de la Informática (SFCS 1981) . págs. 23–36 . doi : 10.1109/SFCS.1981.34 .
Leiserson, Charles E.; Saxe, James B. (1983). "Optimización de sistemas síncronos". Journal of VLSI and Computer Systems . 1 (1): 41– 67. Zbl 0532.94015 .

Enlaces externos

Presentación sobre reprogramación de horarios del MIT
Un algoritmo de reajuste de tiempos de registro a nivel de puerta seguro y completo

[1] Leiserson, Charles E.; Rose, Flavio M.; Saxe, James B. (1983). "Optimizing Synchronous Circuitry by Retiming (Preliminary Version)". Third Caltech Conference on Very Large Scale Integration . Springer. pp. 87–116 . doi : 10.1007/978-3-642-95432-0_7 . ISBN 978-3-540-12369-9.

[one-2] Leiserson, Charles E.; Saxe, James B. (junio de 1991). "Resincronización de circuitos síncronos". Algorithmica . 6 (1). Springer: 5–35 . doi : 10.1007/BF01759032 . S2CID 18674287 .

[two-3] 1 2 Lalgudi, KN; Papaefthymiou, MC (1997). "Resincronización de circuitos activados por flanco bajo modelos de retardo generales". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 16 (12): 1393– 1408. doi : 10.1109/43.664222 .

[three-4] Papaefthymiou, Marios C. (1998). "Resincronización asintóticamente eficiente bajo restricciones de configuración y retención". Actas de la conferencia internacional IEEE/ACM de 1998 sobre diseño asistido por ordenador - ICCAD '98 . págs. 396–401 . doi : 10.1145/288548.289060 . ISBN 1-58113-008-2.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]