Logic decomposition and adaptive clocking for the optimization of digital circuits

Abstract

Over the course of 60 years, since the invention of the integrated circuit (IC), exponential improvements in cost, performance and power consumption were observed. Such advances have been strongly linked with the continuous reduction of the dimensions in manufactured ICs, but this trend has shown decreasing benefits as fundamental limits are reached. Notice that such tiny devices have increased variability, which generates unpredictable variations in the behavior of the manufactured devices. These uncertainties are typically addressed by defining margins on the clock period, estimated during the design phase. However, the overly conservative margins produce significant degradations in performance. Additionally, the evolution that enabled circuits with increasingly higher density of components, also resulted in an extremely complex IC design. At every step, electronic design automation (EDA) tools are challenged to handle this increasing complexity, requiring more powerful techniques to comply with the specification constraints within an affordable runtime. This thesis investigates alternatives in order to improve power, performance, area, and cost, using established IC manufacturing technologies. Advances in EDA are proposed in three distinct topics: area minimization using Boolean methods, area and delay reduction for designs based on fieldprogrammable gate array (FPGA), and an alternative clocking scheme to reduce timing margins. The first contribution consists of a technology-independent method for area minimization of combinational logic. Local optimization is applied on and-inverter graphs (AIGs), performing multi-output Boolean decomposition using two-literal divisors, targeting node count reduction. The second contribution regards two methods targeting technology mapping of FPGAs. On one hand, a functional decomposition approach, which uses the support size as cost function, exploring the inherent characteristics of FPGAs. On the other hand, an approach for recursive remapping, which reduces the structural bias of the subject graph, uses the mapping results as cost function, and obtains significant reductions in area and delay. The third contribution evaluates the dynamic variability mitigation and simplification of power delivery networks (PDNs) using an adaptive clocking scheme based on ring oscillator clocks (ROCs). The impact of the PDN parameters and ROC location is investigated, showing potential improvements in performance, leakage power and cost.

A lo largo de los 60 años desde la invención del circuito integrado (CI), se han producido mejoras exponenciales en su coste, rendimiento y consumo de energía. Ese progreso esta fuertemente vinculado a la reducción continua de las dimensiones de fabricación de los circuitos integrados, pero esta tendencia ha ido mostrando menos beneficios a medida que se alcanzan límites fundamentales. Estos dispositivos minúsculos tienen una mayor variabilidad, lo que genera variaciones impredecibles en el comportamiento de los dispositivos fabricados. Estas incertidumbres generalmente se abordan mediante la definición de márgenes en el período de reloj, estimado durante la fase de diseño. Sin embargo, márgenes excesivamente conservadores producen degradaciones significativas en el rendimiento. Además, la evolución que permitió crear circuitos con una densidad de componentes cada vez mayor, también incrementado la complejidad de los CI. En cada paso del proceso de diseño, las herramientas de automatización de diseño electrónico (EDA) se enfrentan al desafío de manejar esta complejidad creciente, lo que requiere técnicas más potentes para cumplir con las restricciones impuestas por las especificaciónes dentro de un tiempo de ejecución asequible. Esta tesis investiga alternativas para mejorar el consumo de energía, el rendimiento, el área y el coste, utilizando las tecnologías de fabricación de CI ya establecidas. Los avances en EDA se proponen en tres temas distintos: minimización de área usando métodos booleanos, reducción de retardo y área para diseños basados en matrices de puertas programables (FPGA), y un esquema de reloj alternativo para reducir los márgenes de tiempo excesivamente conservadores. La primera contribución consiste en un método independiente de tecnología para minimizar el área de la lógica combinacional. Se aplica optimización local en grafos de AND-inversor, utilizando una descomposición Booleana de múltiples salidas con divisores de dos literales, con el objetivo de reducir la cantidad de nodos. La segunda contribución propone dos métodos para el mapeo tecnológico de los FPGA. Por un lado, un método de descomposición funcional, que utiliza el tamaño del soporte como función de coste, explorando las características inherentes de los FPGA. Por otro lado, un método de mapeo recursivo, que reduce la distorsión estructural del grafo sujeto, utiliza los resultados del mapeo como función de coste y obtiene reducciones significativas en área y retardo. La tercera contribución evalúa la mitigación de la variabilidad dinámica y la simplificación de la red de suministro de energía (PDN) utilizando un esquema de reloj adaptativo basado en un oscilador en anillo (ROC). Se investiga el impacto de los parámetros de la PDN y la ubicación del ROC, mostrando mejoras potenciales en el rendimiento, consumo estático y coste.