Metodología para la verificación de sistemas de conmutación de paquetes

UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA Departamento: ~NGEN~ER~A ELECTRÓNICA Y AUTOMÁTICA Programa de Doctorado: ~NGEN~ER~A DE TELECOMUNICACIÓN AVANZADA Título de la Tesis Tesis Doctoral presentada por D. Carlos Javier Sosa González Dirigida por el Dr. D. Juan Antonio Montiel Nelson El Director, El Doctorando, Las Palmas de Gran Canaria, a 23 de Junio de 2006 A Mineora, Aday, Nita y Pepe. Agradecimientos A Minerva, que ha sido el contrapunto de mi vida. Yo que si, y ella que no. Si, no no no. Pues al final no me queda claro y triunfa tu no. Como novia, ahora como esposa y madre de un tal Aday alias 'el pollito del cruce', chapó. No tengo que olvidar a Nita y Pepe. Que han tragando mucho y en seco, pensando ¿Pero mi niño cuándo vas a presentar este parto? Mama, ya puedes dar el grito. Sólo tengo que alegar a mi favor, que esto no hubiese pasado si no me hubiesen repetido tanto la frase 'estudiar es bueno' ;) Juanita, Ima, Juani y Eloina tampoco me olvido de ustedes que apoyando, apoyando siempre empujando. Tampoco puedo olvidar a Ana y a Armando que a pesar de no entender que es lo que hago, han sabido estar en esos momentos que hacen falta. También tengo que agradecer a Lourdes y a Alicia todo el cariño que me han ofrecido desinteresadamente como aquellas hermanas de sangre que no tengo. A Dr. D. Juan A. Montiel Nelson, como Catedrático de Universidad que es, le doy mi más sincero agradecimiento por su inestimable ayuda a lo largo de esta Tesis Doctoral. Nelson como compañero, gracias por escucharme, alentarme y pararme los pies cuando ves algo raro. Aunque está mal que lo diga yo, pero algunas veces las ideas esas locas que tengo funcionan. No creas que por terminar esta Tesis te vas a librar de seguir escuchando esas 'ideitas'. Héctor, José Carlos no se como decirlo, pero creo que lo mas sencillo es decir gracias por recorrer este camino pasito a pasito a mi lado y con su desinteresada ayuda en todo momento. Nunca olvidaré aquel código en C con sólo variable globales o los ronquidos de München. A todo aquel que mostró su sorpresa por ver a un elemento como yo diciendo que no podía asistir a un asadero, o celebración porque 'tengo que hacer tesis'. Y una palmadita en la espalda a aquellos usuarios a los que trajinaba los ciclos de cpu y mientras ellos comentaban que les iba más rápido en su PC. Igualmente, gracias a sysadmin por la quota casi infinita del Ivarltmp. Supongo que me dejo a alguien por nombrar, pero tengo prisa para ir a encuadernar estos tomos. Esto ha sido posible en mayor o menor medida a gracias a ustedes. Resumen Esta Tesis Doctoral aporta una metodología y un entorno para la verificación y validación de sistemas integrados de última generación, basados en la exploración del espacio de diseño y la generación guiada mediante diversas métricas de cobertura. El entorno desarrollado en C++ permite comprobar elementos sencillos, como son los módulos de lógica combinacional o secuencial, o tan complejos, como un sistema integrado de última generación; bien de forma automática o especificando casos críticos. La metodología y el entorno propuesto, son aplicados a la verificación de elementos en fase de desarrollo en cualquier nivel y donde existan descripciones hardware y10 software. Con el objeto de reducir el número de vectores y el tiempo requerido para comprobar un sistema integrado, el entorno se complementa con diversas técnicas - heurísticas y deterministas - de generación de vectores guiados por métricas de cobertura, basadas en potencia de consumo o ejercitación de rutas. Se provee una metodología eficiente para explorar el espacio de diseño del sistema bajo verificación con el objeto de obtener una estimación precisa del retardo de cada funcionalidad. Como resultado de la exploración del espacio de diseño no sólo se obtiene el retardo a anotar en cada funcionalidad, sino que se logra el rango de funcionamiento del conjunto de soluciones circuitales óptimas en retado-área o retardopotencia de consumo. Tanto la metodología presentada como el entorno que la implementa han sido utilizados ampliamente en la verificación de circuitos integrados comerciales y no comerciales. La consecución de dichos sistemas es una buena garantía de que el entorno de verificación funciona correctamente y que la metodología propuesta es práctica en la verificación de sistemas de integrados. Indice general 1. Verificación de Sistemas Integrados 1 1.1. Introducción ............................. 3 1.2. Diseño de Sistemas de Conmutación de Próxima Generación ... 5 1.3. Verificación Basada en Simulación ................. 14 1.4. Entorno de Verificación Propuesto ................. 28 1.5. Organización de la Memoria .................... 28 2. Entorno de Verificación 31 2.1. Introducción ............................. 33 2.2. Trabajos Previos ........................... 34 2.3. Priorización ............................. 38 2.4. Modelos de Verificación ...................... 38 2.5. Visión General del Entorno ..................... 43 2.6. Interfaces .............................. 43 2.7. El Sistema de Ficheros ....................... 52 2.8. Características Avanzadas ...................... 55 2.9. Implementación Interna ....................... 58 2.10. Resultados Experimentales ..................... 63 2.11. Conclusiones ............................ 66 3. Generación de Vectores de Máxima Cobertura 69 3.1. Introducción. ............................ 71 3.2. Definiciones de Teoría de Grafos .................. 75 3.3. Cobertura Basada en Rutas (CBR) ................. 76 3.4. Cobertura Basada en Potencia de Consumo ............ 107 4. Optimización del Retardo 121 4.1. Introducción. ............................ 124 4.2. Trabajos Previos ........................... 126 4.3. Sinopsis ............................... 128 4.4. Formulación del Problema de Optimización de la Ruta Crítica . . 129 4.5. Optimización de un Circuito Empleando el Conjunto Ruta Crítica 131 4.6. Curva de Prestaciones de un Circuito ................ 132 4.7. RTL versus Circuito de Lógica Combinacional .......... 146 4.8. Conclusiones ............................ 151 5. Exploración del Espacio de Diseño Potencia de ConsumwRetardo 155 5.1. Introducción ............................. 157 5.2. Trabajos Previos ........................... 158 5.3. Modelo de Puerta .......................... 168 ÍNDICE GENERAL 5.4. Formulación del Problema de Optimización de la Ruta Crítica . . 169 5.5. Optimización de un Circuito Empleando el Conjunto Ruta Crítica 170 ................ 5.6. Curva de Prestaciones de un Circuito 171 ................ 5.7. El Problema del Punto de Arranque 177 5.8. Formulación del Dimensionado de Puerta Empleando Programa- ............................. ción Lineal 188 ..................... 5.9. Resultados Experimentales 195 ............................ 5.10. Conclusiones 203 Índice de figuras Impacto de la metodología de diseño en el costo de implementación de sistemas. .............................. 4 Densidad de integración frente a productividad. ........... 4 Arquitectura de un conmutador. ................... 6 El ciclo de diseño. .......................... 8 Ejemplo de un sistema de conmutación en fase de desarrollo. .... 21 Las capas de software para la interfaz entre C++ y el código RTL. En la parte superior el Dispositivo Bajo Verificación (DBV) y en la inferior el modelo de referencia (Golden Reference). ........ 22 Refinamiento del modelo de comportamiento hasta nivel RTL en C++ ................................... 23 Verificación respecto al Golden Reference. .............. 24 Representación gráfica del registro de simulación C++ o RTL. ... 25 Verificación con especificación de reglas. .............. 26 Distintas formas de generar la especificación de reglas. ....... 27 Entorno de verificación propuesto. .................. 29 Verificación de un sistema integrado. ................. 37 Esquema del modo de verificación de casos críticos. ........ 39 Esquema del modo automático de verificación. ........... 41 Entorno de desarrollo de bancos de prueba. ............. 44 Diagrama de bloques de la interfaz paralela. ............. 45 Diagrama de bloques de la interfaz serie. .............. 48 Diagrama de bloques de la interfaz de CPU. ............. 51 Generación de células de datos, relleno y ráfaga en la interfaz serie. 54 Sincronización de la interfaz paralela. ................ 56 Detalle del módulo de generación de jitter en el diagrama de bloques de la interfaz serie. ....................... 57 Esquema a nivel de bloques de las librerías implementadas. ..... 58 Comparativa de la evolución de la cobertura alcanzada en función del lenguaje empleado. ........................ 64 Ejemplo de cobertura basada en rutas: (a) circuito combinacional, (b) grafo del circuito, (c) ejercitación del path4. ........... 78 Ejemplo de cobertura basada en rutas con ejercitación múltiple: (a) circuito combinacional a verificar, (b) verificación simultánea de múltiples rutas. ............................ 81 Modelo básico de la puerta AND para la propagación de transición. 83 Modelo básico de la puerta OR para la propagación de transición. . 84 Modelo básico de la puerta INV para la propagación de transición. . 85 ÍNDICE DE FIGURAS Ejemplo de la expansión de las condiciones de propagación: (a) esquema del subcircuito, (b) grafo del subcircuito, y (c) expansión de la condición de propagación de la ruta pathla y contradicción sobre la ruta path7. .......................... 86 Algoritmo para la generación del patrón de entrada en la verificación de una ruta. ........................... 88 Algoritmo para la generación de patrones de máxima cobertura. .. 90 Algoritmo de generación de patrones de máxima cobertura empleando Algoritmos Genéticos. .................... 92 Cálculo del coste de un individuo: (a) individuo con 3 rutas válidas, (b) individuo con 4 rutas válidas y una de ellas duplicada, (c) individuo con tan sólo 2 rutas válidas. ................ 92 Ratios del tiempo de CPU para el conjunto de circuitos MCNC'91. 95 Convergencia de la función de coste de los mejores individuos en la generación de patrones de verificación para el circuito 5xpl. ... 96 Convergencia de la función de coste medio de los individuos en la generación de patrones de verificación para el circuito 5xpl. .... 96 Convergencia de la función de coste de los peores individuos en la generación de patrones de verificación para el circuito 5xpl. .... 97 Diversos modelos de descripción para la puerta NOR: a) completo, b) suponiendo y' y y" variables enteras, c) con las entradas codificadas, y d) PROLOG. ......................... 106 Algoritmo para evaluar la actividad de conmutación producida por dos vectores de entrada consecutivos. ................ 11 1 Ejemplo de actividad de conmutación. a) Circuito de lógica combinacional bajo estudio representado como grafo, b) estado interno estable de la red Booleana cuando el vector de entrada es el 0000, c) estado interno estable de la red Booleana cuando el vector de entrada es el 1111, d) detección de las transiciones cuando el vector de entrada cambia de 0000 a 1111, e) estado interno estable cuando el vector de entrada es el 0101, y f) detección de las transiciones cuando el vector de entrada cambia de 0000 a 0101. ......... 112 Algoritmo para obtener el estado interno de un circuito; dado un vector de entrada, actualiza y evalúa la actividad de conmutación basado en el estado anterior de la red Booleana. ........... 114 Algoritmo de cálculo del costo para evaluar la actividad de conmutación en un circuito de lógica combinacional basado en el último vector aceptado. ............................ 114 Algoritmo final de coste para evaluar la actividad de conmutación en un circuito de lógica combinacional. ............... 115 Convergencia de la función de coste del circuito C6288 para la búsqueda de la secuencia de estímulos de entrada con un conjunto de 5 búsquedas simultáneas. .................... 1 18 Curva de prestaciones área-retardo. La recta C representa el punto de partida de la exploración, mínima área, máximo retardo del circuito. La recta D representa el punto de mínimo retardo del circuito y, por tanto, el de máxima área. ................... 126 ÍNDICE DE FIGURAS - Conjunto ruta crítica como subred del circuito: a) conjunto ruta crítica (zona sombreada), b) ruta dependiente del conjunto ruta crítica (área punteada), y c) rutas dependientes del conjunto ruta crítica. 130 Algoritmo de actualización del conjunto ruta crítica. ........ 135 Algoritmo para la generación de la curva completa de prestaciones. 136 Curva de retardo de una NAND bajo diferentes cargas frente al factor de velocidad. ........................... 139 Algoritmo de generación de la curva completa de prestaciones empleando la técnica de Programación Lineal. ............. 141 Algoritmo de dimensionado de puerta empleando técnicas de Programación Lineal. ........................... 142 Número de variables frente al número de puertas. .......... 145 Variaciones en el número de variables frente al número de puertas. . 145 Tiempo de CPU frente al número de puertas. ............ 146 Curva de prestaciones completa de área activa frente a retardo para el circuito bw. ............................. 147 Retardo del circuito bw bajo diferentes cargas frente a la suma de factores de velocidad. El símbolo E representa la carga de un inversor con 15 fF de capacidad de cableado parásita. .......... 147 Algoritmo para la generación de la curva completa de prestaciones. 148 Exploración del espacio de diseño completo en mapeado tecnológico atendiendo a la ruta crítica del circuito: a) metodología tradicional de mapeado tecnológico, b) exploración del espacio de diseño atendiendo a la ruta crítica. ...................... 150 Puerta CMOS con las cuatro corrientes empleadas para definir su corrientedefuga. ........................... 161 Puerta sometida a una alta carga de fanout. ............. 164 Diagrama de bloques del modelo de retardo empleado en el cálculo de la densidad de transiciones aplicando el filtrado. ......... 167 Ejemplo de cono lógico de entrada y cono lógico de salida de una puerta lógica. ............................. 170 Algoritmo de actualización del conjunto ruta crítica. ........ 175 Algoritmo para la generación de la curva completa de prestaciones. 175 Curva de prestaciones retardo-potencia de consumo. La recta C representa el punto de partida de la exploración, minima potencia de consumo, máximo retardo del circuito. La recta D representa el punto de mínimo retardo del circuito y, por tanto, de máxima potencia de consumo. ......................... 177 Representación y codificación de un circuito de lógica combinacional mediante técnicas basadas en algoritmos genéticos: (a) circuito a optimizar, (b) representación mediante un grafo, y (c) codificación del individuo de la población del algoritmo genético. ........ 178 Ejemplo de individuo propuesto por el algoritmo genético. . 179 Convergencia de la función de coste en la optimización del circuito i8 para la obtención del punto de mínima potencia. ......... 183 Algoritmo de generación de la curva completa de prestaciones empleando la técnica de Programación Lineal. ............. 191 Algoritmo de dimensionado de puerta empleando técnicas de Programación Lineal. ........................... 192 4 Verificación de Sistemas Integrados Modelo de Coste para el Diseño de SoC d -- -- Metodología Adoptada - - sm5 \Y .-- =-M m - + RTL Con Mejoras Solamente Futuras m i lo1 5 1990 1995 2000 2005 2010 2015 Figura 1.1: Impacto de la metodología de diseño en el costo de implementación de sistemas. E Fuente: "Technology Roadmap for Semiconductors", 200 1. Figura 1.2: Densidad de integración frente a productividad Fuente: "Technology Roadmap for Semiconductors", 200 1. 1.2 Diseño de Sistemas de Conmutación de Próxima Generación aprovechamiento del ancho de banda en las futuras redes de comunicación, y una mejora en la calidad de servicio, en adelante, QoS3. El objetivo fundamental que se pretende cubrir en esta Tesis Doctoral es la de aportar soluciones que permitan una reducción efectiva del tiempo y del esfuerzo en la etapa de verificación. Para lograr este objetivo, es necesario proveer de un entorno que permita generar estímulos, comprobar respuestas, y analizar prestaciones explorando el espacio de diseño del sistema integrado a verificar. Tanto la generación de estímulos como la comprobación de respuestas ha de permitir el empleo de modelos de referencia y métricas de cobertura, los cuales guiarán el proceso de verificación. El análisis de prestaciones con exploración del espacio de diseño permitirá ajustar los retardos anotados de las unidades funcionales implementadas en el sistema integrado a verificar, para así acometer una verificación más realista. La anotación se corresponderá con un rango de valores válidos - solución de la exploración del espacio de diseño - y no con un único valor puntual como se hace en la actualidad. Esto incrementará el grado de libertad a la hora de determinar el rango de implentaciones que superan la verificación o no - en la actualidad sólo se plantea una única solución circuital que supera o no la verificación. En resumen, el entorno propuesto y las metodologías implementadas en él ha de ser capaz de analizar las prestaciones y verificar sistemas integrados complejos de una manera más eficiente a la actualmente empleada, cubriendo desde la etapa más temprana del diseño hasta la de validación del primer prototipo. 1.2. Diseño de Sistemas de Conmutación de Próxima Generación El desarrollo de Internet, cada vez, demanda más ancho de banda y más funcionalidades a los equipos de comunicación. Aunque, la clave de estos sistemas es la estructura de transmisión (paralela o serie) para transferir paquetes de datos desde un puerto de entrada a uno o más puertos de salida, en la práctica resulta imprescindible disponer de arquitecturas de altas prestaciones para la planificación y la conmutación. Las redes de comunicaciones no son meras arbitradoras de ancho de banda entre tráfico de datos y de voz. De hecho, una partición estricta del ancho de banda conlleva un uso ineficiente del ancho de banda total. A medida que el ancho de banda del sistema crece, también se incrementa el costo relativo por el desaprovechamiento de un porcentaje del mismo, incluso, aunque sea posible una reducción del costo absoluto medido en Gbls. Se necesitan funciones sofisticadas de 00s. . . que aseguren el uso eficiente del ancho de banda, y por tanto, reduzcan el costo CalidaddeSeniicio total del sistema. El hecho de aprovechar, eficientemente, el ancho de banda del canal, y distinguir tráfico de distintas prioridades para distintas clases de aplicaciones y10 usuarios; determina en última instancia y en gran medida, la QoS del sistema, a costa de un incremento notable en la complejidad de los sistemas de conmutación. Con esta finalidad, los sistemas de conmutación han de disponer de mecanismos para: La gestión de tráfico con distintos niveles de prioridad. 3Acrónimo del término anglosajón Qualily of Sewice. Calidad de servicio de la red. 6 Verificación de Sistemas Integrados Arquitectura Conmutador VOQ Decidir la configuración óptima de la matriz de conmutación. Permitir una escalabilidad del sistema (aumentar o reducir el número de puertos de entradalsalida) sin que se degraden las prestaciones. Controlar el flujo de datos. En la figura 1.3, se muestra un ejemplo de la arquitectura de estos conmutadores de altas prestaciones. Básicamente, existen dos tipos de circuitos: el transceptor bidireccional y la matriz de conmutación. 128-bit CSX #65 * 128-bit CSX #64 1 128-bit CSX #63 @ 128-bit CSX #62 @ CSX #O1 CSX #O0 Figura 1.3 : Arquitectura de un conmutador. El transceptor, convierte las tramas de un formato estándar como por ejemplo CSIX4, a un formato propio - interno del fabricante - para la matriz de conmutación. El número de transceptores depende del número de puertos del sistema. Además, existe al menos un par de transceptores dedicados a la información de control de flujo. El tipo de entrada es paralelo y requiere de 32 ó 128 bits, en función de la tasa de entrada, que puede ser OC-48 (2'5 Gb/s) ó OC-192 (10 Gbls). La conexión con el conmutador está compuesta por un conjunto de 2 a 4 enlaces serie de alta velocidad, en función de la tasa de entrada, por lo que cada circuito conmutador requiere 2 o 4 CIs conmutadores. El número de circuitos conmutadores depende del número de puertos del sistema final, y puede ser 1, 2 ó 3; ya que los transceptores no suelen aceptar más de 3 entradas serie por puerto CSIX. 1.2.1. El Ciclo de Diseño Tradicionalmente, para poder desarrollar un sistema integrado - como es el caso de un sistema de conmutación para GigabitEthernet - deben alcanzarse los 4CS~~ es un estándar de hecho, desarrollado por el Common Switch Interface Consortium. Este consorcio incluye a más de 25 fabricantes de equipos de conmutación en redes ATM, FastEthernet y GigabitEthernet. 1.2 Diseño de Sistemas de Conmutación de Próxima Generación siguientes objetivos, tal y como se ilustra en la figura 1.4. Estas etapas se describen a continuación Deñnición de la Arquitectura.- En esta etapa se ha de obtener un modelo algorítmico o descripción de la arquitectura del sistema completoi - Golden Reference. Este modelo se escribe en un lenguaje de alto nivel, generalmenModelo deAl,oMvel te en C/C++. La elección de un lenguaje se debe a varias razones, de entre ellas se destacan las siguientes: Obtener las prestaciones del sistema conmutador. La forma habitual de reflejar las prestaciones de los sistemas de conmutación, es por medio de curvas de carga. Estas curvasreflejan el comportamiento del sistema completo o de un subsistema concreto, en función de distintos valores de la carga. Este comportamiento, se suele expresar mediante el thvoughpuf, además de utilizar otro tipo de medidas como la latencia, el porcentaje de paquetes rechazados, el tiempo medio de espera en cola, el tiempo máximo de servicio, el número medio de tramas en cola, entre otros. Servir como patrón o referencia del comportamiento del sistema conmutador-Define como deberá comportarse, finalmente, el diseño implementado, tanto funcionalmente, como en prestaciones. Este patrón de referencia, es el GoldenRefevence. Ajustar las variables tvade-offy analizar el comportamiento de las prestaciones finam les del conmutador de cara a la aplicaciónfinal-Las variables tvude-offson aquellos Vmiables Tmde+f a - .- - parámetros del diseño con dependencias entre los distintos parámetros y las prestae m ciones finales. Algunas de estas variables son el tamaño de las colas, el número de 0 u colas por destino y por prioridad, la política de gestión de prioridades, y el algoritmo 5 3 de planificación, entre otras. Existen herramientas especificas para la obtención y el L 0 * análisis de las prestaciones finales del sistema en función de éste tipo de decisiones n m en el ámbito de arquitectura [4]. N .- - m Estudiar las prestaciones latencia, thvoughput, entre otras, del sistema conmutador, respecto a escalabilidad en cuanto a número de puertos y número de matrices conmutadorasLas prestaciones del sistema se obtienen como el resultado de una serie estadística de simulaciones del comportamiento de la arquitectura frente a paquetes entrantes. Aquellos parámetros relacionados con la llegada de paquetes al conmutador, como el tiempo entre llegadas, la prioridad, el puerto de destino, el tipo de trama. se modelan mediante variables oseudo-aleatorias7. Estas fuentes oseudoaleatorias generan eventos en las entradas del sistema. La evolución de determinados parámetros estadísticos se representa gráficamente conformando las curvas de prestaciones del sistema Evaluar las prestaciones del sistema en comparación con otros productos existentes en el mercado. En general, con cada mejora de un producto o especificidad del mismo se suministran datos relativos a las prestaciones que se esperan obtener de forma comparativa. Aunque, un fabricante no suele disponer de modelos completos de productos de la competencia, sí dispone de modelos completos de productos propios. Particionad0.- Particionar la arquitectura en módulos independientes, y definir la funcionalidad de todos y cada uno de los módulos integrantes del sistema. 'Modelo de muy alto nivel del sistema, que recoge los aspectos fundamentales de la especificación del sistema. En verificación automática, se contrasta la funcionalidad del sistema con la del Golden Refevence. 6Tasa de salida del sistema completo. Expresándose normalmente en Gbls. 7Números aleatorios generados por ordenador. [4] Israel Cidon, Amit Gupta, Tony Hsiao, Asad Khamisy, Abhay Parekh, Raphael Rom, and Moshe Sidi. OPENET: An Open and Efficient Control Platform for ATMNetworks. IEEE INFOCOM, pages 824-831, April 1998. Verificación de Sistemas Integrados \C U Descripción Red de Puertas Lógicas Análisis Red de ----------------------. -- Layout J Layout Figura 1.4: El ciclo de diseño. 1.2 Diseño de Sistemas de Conmutación de Próxima Generación 9 Las particiones se realizan en al menos dos niveles denominados módulos y sus agrupaciones o clusterss. Especificación de las 1nterfaces.- Se identifican y analizan las necesidades de comunicación entre las distintas funcionalidades de los diversos módulos definidos en el particionado de la arquitectura. Una vez particionado el diseño, se procede a la especificación de las interfaces entre los módulos. El no disponer de un modelo algorítmico a éste nivel, implica la existencia de múltiples imprecisiones en dichas especificaciones. Los errores en este nivel son muy comunes y una vez detectados, provocan rehacer las especificaciones y volver a codificar los módulos. Análisis de Prestaciones.- Una vez se ha finalizado el modelo de alto nivel del sistema a implementar, se somete a diversas condiciones de trabajo con el fin de obtener múltiples resultados en función de los diversos parámetros de configuración del sistema. Es decir, se trata de conocer las prestaciones del sistema, a través del modelo de alto nivel, en varias situaciones de funcionamiento. De estas simulaciones a muy alto nivel, se obtienen diversas gráficas, que en el caso de un sistema de conmutación son: el número SimulmióndeAlfo Nivel de paquetes medio en cada cola, ordenadas por prioridad, frente a la carga del sistema o con una dirección de destino determinada. En los sistemas de conmutación esta información es muy útil a la hora de seleccionar la profundidad de memoria en función de la carga máxima o media a soportar. Una vez definidos los parámetros de configuración de la arquitectura, las simulaciones obtenidas con dichos parámetros definirán el comportamiento del mismo, con lo cual dichas simulaciones pueden ser tomadas como referencia del normal comportamiento del diseño a implementar. Esta etapa, también, permite conocer el impacto de las etapas previas en las prestaciones especificadas del sistema. El particionado y la incorporación de interfaces, pueden delimitar las prestaciones del sistema. Codificación RTL de los Módulos, Clusters9 y Sistema.- Es el proceso de descripción hardware (comportamiento o estructural) de cada uno de los módulos, clusters y sistema definidos en el particionado. La codificación hardware consiste en crear un programa escrito en un subconjunto del lenguaje HDL elegido. Este subconjunto recibe el nombre de HDL sintetizable. Por ejemplo, para el lenguaje Verilog este subconjunto se denomina en la literatura Verilog-RTL o Verilog sintetizable. Por tanto, el objetivo de esta etapa no es sólo desarrollar cada uno de los módulos, clusters y sistema que componen el diseño, sino que dicho desarrollo se describa de forma tal que sea posible su implementación fisica. Verificación de los Módulos.- Se trata de comprobar que la descripción hardware del módulo tenga la misma funcionalidad que la definida en la etapa de particionado. Un gran parte de la verificación, se efectúa en base a un conjunto de simulaciones. Se suele utilizar el mismo lenguaje HDL para W$cmióe de realizar esta etapa de la verificación. El lenguaje puede calificarse de más ,,,ionalidades o menos apto para esta tarea en función de la complejidad del módulo y de ~ári~~ 'Esta nomenclatura suele ser confusa. A veces se intercambian los términos módulos por clustevs y viceversa. Lo fundamental es que exista una partición jerárquica en al menos dos niveles del sistema completo. 10 Verificación de Sistemas Integrados la rigurosidad de la verificación. Los fallos detectados a nivel de módulo implican volver a codificar el módulo de nuevo para que éste se ajuste a la especificación correctamente, y por supuesto, volver a verificarlo. Verificación de los Clusters, y del Sistema.- Unavez que todos los módulos integrantes del cluster o del sistema han sido comprobados funcionalmente, se enlazan y se comprueba la funcionalidad de los clusters que forman. De igual forma que con los módulos, se agrupan los clusters para componer el circuito, y así verificar su funcionalidad. Esta verificación detecta errores cometidos en las etapas de particionado y10 en la especificación de interfaces. Por tanto, los fallos en este nivel implican redefinir la interfaz de los módulos afectados, volver a codificarlos y a verificarlos. Una vez corregidos, es necesario volver a verificar los clusters y el CI, hasta comprobar que la funcionalidad de todo el sistema coincide con la del Golden Reference. Verificación de las Prestaciones del Sistema.- Del análisis de prestaciones del sistema se desprenden un conjunto de caracteristicas que ha de cumplir el código implementado. La verificación de las prestaciones del sistema consiste en comprobar que dichas caracteristicas extraídas del análisis de prestaciones, se cumplen. Si el sistema a comprobar no fuese determinista o la función que mide las prestaciones es muy compleja, se necesitaría verificar las prestaciones del sistema frente a las obtenidas con el Golden Reference. Este paso se hace impracticable mediante simulaciones con lenguajes HDL convencionales, pues implicaría simular una estadística suficientemente amplia sobre una descripción a nivel hardware o RTL del sistema completo. Verificación Automática.- La verificación automática del sistema es la comparación, de una forma automatizada, entre la descripción hardware final a nivel RTL del sistema completo y el Golden Reference. Un entorno que permita la verificación automática del sistema evitaría tener que generar un testbench1° y una multitud de simulaciones, con el consiguiente ahorro de tiempo. Estas simulaciones son necesarias para asegurar que el sistema se comporta exactamente como indica el modelo. Para llevar a cabo la verificación automática, existen diversas soluciones dentro de las técnicas de verificación formal. Las técnicas de verificación formal persiguen una verificación certera. En sistemas con un alto nivel de complejidad, como los sistemas de conmutación, cubrir todos los casos posibles es impracticable. Se buscan soluciones como el Model-Checkingl1 que aseguren el sistema para una determinada cobertura de fallos, a pesar de existir un grado de incertidumbre en el proceso. El Model<hecking permite verificar el sistema de dos formas diferentes: mediante un modelo del sistema o frente a un conjunto de reglas que deban cumplirse. Síntesis Lógica.- Las herramientas de diseño actuales permiten tiempos de codificación muy reducidos para diseños de un nivel de complejidad medio. Sin embargo, para diseños más complejos no hay muchas herramientas que sinteticen los diseños desde el nivel algorítmico. La programación orientada a ''Es el entorno necesario para efectuar la simulación y la verificación del sistema. "Consiste en verificar la validez de una implementación comparando su comportamiento frente a un modelo de referencia. 1.2 Diseño de Sistemas de Conmutación de Próxima Generación 11 objeto es un complemento muy adecuado para estos lenguajes de especificación. La síntesis es el proceso por el cual se transforma la descripción RTL en una descripción circuital basada en puertas e interconexiones entre estas1'. La síntesis consiste en aplicar dos procesos bien diferenciados. El primero de ellos es la Síntesis Lógica y el segundo el Mapeado Tecnológico. La Síntesis Lógica procesa la descripción RTL y la convierte a una descripción puramente lógica. Este proceso posee un extenso estado del arte, con muchas aportaciones teóricas y avances en la industria. Todas las fases que se desarrollan dentro de la Síntesis Lógica están relacionadas con la transformación, manipulación y optimización de lógica combinacional. Además de convertir el código RTL en una descripción lógica, otro objetivo primordial en esta etapa es reducir las funciones lógicas finales que describen el circuito sintetizado. Mapeado Tecnológico.- Este segundo proceso que se aplica en la síntesis de un circuito requiere una libreria tecnológica de puertas. Esta libreria permitirá convertir la descripción lógica de cada módulo del sistema, en una descripción de puertas de dicha libreria e interconexiones entre ellas. El objetivo final del Mapeado Tecnológico es obtener un circuito que cumpla un conjunto de restricciones de retardo, área y10 potencia. Este conjunto de restricciones definen el llamado punto de trabajo del espacio de diseño de la implementación del circuito sintetizado. La literatura existente en este otro área de la síntesis de circuitos es también muy amplia. La definición de un punto del espacio de diseño es muy importante para la verificación, pues permite realizar las anotaciones13 correspondientes de retardo a los diversos módulos implementados. Esto permite comprobar la funcionalidad implementada con un temporización muy aproximada14 a la real del circuito. Diseño Físico.- Una vez se posee una red de puertas asociadas a una libreria tecnológica, se procede a realizar la planificación, colocado e interconexionado fisico de las mismas, dentro del área especificado para ello. El desarrollo de este proceso aplica diversas políticas de colocado e interconexionado en función de factores como la disposición de los buses de alimentación dentro o fuera del layout1i de la puerta, la disposición y acceso a los terminales16 L~U~ de estas, entre otras. Por lo general, el área final del circuito está limitada por el área máxima del encapsulado seleccionado para el producto final y por tanto cada módulo y cluster posee a su vez un área asignada, la cual no ha de superar. El resultado de este laborioso paso es un trazado fisico en el que ya no sólo tienen interpretación fisica los polígonos que definen a las "En la literatura anglosajona se denomina a la vista circuital, compuesta por descripciones físicas de puertas e interconexiones entre estas, como net-list. I3Este proceso se conoce tradicionalmente en la literatura anglosajona como back-annotation. I4En esta fase del flujo de diseño se dispone del valor correcto de los retardos de puerta, pero puesto que no se ha realizado la interconexión física entre las puertas, módulos o incluso los clustevs, se ha de hacer uso de estimadores de cableado para obtener un valor del retardo aproximado al real. "La vista layout de una puerta define su trazado físico. El trazado físico especifica los polígonos de cada capa que son necesarios para construir la puerta. I6En la literatura se denominapin. 12 Verificación de Sistemas Integrados puertas y sus componentes, sino que cada interconexión posee su representación en base a polígonos, o lo que es o mismo, se dispone de un layout del dispositivo. Del layout se pueden deducir las características parásitas (capacidades, inductancias, resistencias, etc.) que va a poseer la implementación fisica del mismo. La extracción de dichos parámetros permite aproximar aún más los valores de retardo de las simulaciones realizadas al real. El carácter tardío de la obtención de esta vista layout es un duro inconveniente. Un error descubierto en esta etapa final del flujo de diseño puede suponer un retraso temporal elevado sobre el time-ternarket, puesto que la modificación necesaria puede afectar a las etapas tempranas del flujo de diseño. Igualmente, la naturaleza tardía de la obtención de los parámetros parásitos fuerza a realizar las simulaciones con estimadores tanto de retardo de puerta como de interconexionado desde las etapas tempranas del diseño. Una vez alcanzada esta etapa y finalizada la mayor parte de la verificación del circuito, sólo queda tiempo para ejecutar unas pocas simulaciones de casos críticos con el objeto de comprobar lavalidez de las suposiciones realizadas. Realizar el Test de un Primer Prototipo.- Se trata de un paso previo a la fabricación de la serie, donde se realiza la verificación sobre un dispositivo hardware (test) utilizando un emulador (FPGA, equipo de emulación, etc). La verificación a este nivel, ha de ser una verificación a nivel hardware del prototipo. Sin embargo, las posibilidades del equipo de test limitan el alcance y profundidad de esta verificación. Un inconveniente adicional, es que el código escrito para la verificación del sistema no se suele aprovechar para esta tarea. El tiempo y esfuerzo que se invierte en el proceso de verificación, es normalmente muy superior al invertido en el diseño del mismo, tal y como ha quedado reflejado en el flujo de diseño descrito; lo cual impone una fuerte limitación en el time-temarket, quedando éste prefijado, según la complejidad del sistema, por el tiempo invertido en las simulaciones. Cabe destacar que para dar comienzo a las simulaciones de los clusters, o del CI, todos los módulos deben haber sido descritos a nivel RTL y su funcionalidad debe haber sido verificada. Esta dependencia supone, en la práctica, un cuello de botella muy importante, pues implica no cometer errores en las etapas de particionado y definición de las interfaces, para poder concluir, simultáneamente, el diseño de todos los bloques. Una carencia importante, hoy día, es la definición del punto de trabajo del circuito. Las herramientas de síntesis fisica actuales no exploran el espacio de diseño del circuito a implementar, se limitan a generar una versión del CI en un punto del espacio de prestaciones, que incluso puede no cumplir las restricciones de área, Punto de ~mboj~ retardo y10 potencia de consumo exigidas en las especificaciones. Ello implica reejecutar la herramienta de síntesis una y otra vez hasta alcanzar el objetivo marcado. En última instancia, en caso de no alcanzar dichos requisitos, es necesaria la recodificación parcial de alguno de los módulos desarrollados. Lo que significa que se ha de ejecutar nuevamente todas las pruebas de verificación en todos los niveles en los que se involucra a dicho módulo. 1.2 Diseño de Sistemas de Conmutación de Próxima Generación 13 Sería deseable que dichas herramientas de síntesis fisica provean más que un único punto del espacio de diseño, un rango de funcionamiento. Ello permitiria elegir el punto de diseño para no sólo cumplir con las restricciones de área, retardo y potencia de consumo, sino que permitiria en muchos casos también culminar la verificación si errores debidos a la existencia de un retardo incorrecto en alguna funcionalidad. La exploración del espacio de diseño de los circuitos dotaría a la herramienta de verificación de un gran margen de decisión, puesto que los retardos de cada módulo se sustituirían por un rango de posibles retardos. Dicho margen permitiria a la herramienta de verificación determinar cuál es el subconjunto de retardos que cumplen la especificación dada, y por tanto, el rango de puntos del espacio de diseño que cumplen o no con la especificación verificada. Hoy en día, las prestaciones temporales del CI quedan fijadas por el punto del espacio de diseño que determina la herramienta de síntesis fisica, la fase de verificación sólo puede determinar si dicho punto es válido o no. Es deseable disponer de las prestaciones antes de la etapa de síntesis fisica, incluso antes de la síntesis lógica. Es en este punto donde quedan encuadradas las aportaciones de esta tesis relativas al análisis de prestaciones. 1.2.2. Unicidad entre Lenguajes Los lenguajes HDL utilizados para el desarrollo de sistemas integrados han demostrado ser ineficientes e inadecuados para abordar la codificación y verificación de los complejos diseños actuales. Entre los múltiples inconvenientes, se destaca que dichos lenguajes no soportan descripciones en el ámbito de las especificaciones que sirvan de patrón de referencia. Esto obliga a tener que emplear dos o más lenguajes distintos en el ciclo de diseño. Por ejemplo, se utiliza un lenguaje de alto nivel para la extracción de las prestaciones del modelo, y un lenguaje HDL para el ciclo de diseño. Realizar estas dos especificaciones en lenguajes distintos es un grave inconveniente. En Uflicidadeflla Descripción la mejor de las situaciones, se ha de realizar una verificación cruzada entre ambas descripciones Actualmente, las especificaciones, tanto del sistema hardware como del testbench, se realizan con lenguajes HDL que son de muy bajo nivel que no ayudan al diseñador en todas las fases de diseño. De aquí que, el esfuerzo y el tiempo invertido en la verificación de esta clase de sistemas es excesivo. Existen herramientas comerciales como Specman1', FoCs18, Active HDL o Riviera19, FormalProz0, entre otras, que ofrecen un entorno integrado para la generación y verificación del testbench. Sin embargo, obligan al diseñador a aprender un nuevo lenguaje que es exclusivo para el uso de dicha herramienta. Por otro lado, y a pesar de que existen lenguajes de muy alto nivel como C, C++, o UML, entre otros, para abordar eficientemente el diseño de sistemas altamente complejos, el diseñador hardware sigue empleando lenguajes HDL para esta labor, ya que muchos de los anteriores lenguajes no soportan características propias de sistemas digitales, como son, la especificación del conexionado basada en buses, la simulación a cuatro estados por señal, la simulación en el dominio "Specman es un producto de Verisity Design Inc, ahora Cadence Design Systems Inc. "FoCs es un entorno de verificación formal desarrollado por IBM. "Active HDL o Rivieva son herramientas de verificación de la compañía ALDEC Inc. Z°FomalPvo entorno de Mentor Graphics que permite realizar Equivalence Checking. 20 Verificación de Sistemas Integrados Alcanzar este objetivo global implica, básicamente, la consecución de tres objetivos parciales. La verificación de sistemas integrados basada en reglas, la veriC1mesdelEfltorno de ficación automática de sistemas integrados empleando modelos de referencia de VenJ?cación alto nivel (Golden Reference), y el análisis de prestaciones con exploración del espacio de diseño. Estos aspectos fundamentales se analizan con más detalle en los apartados que siguen a continuación. Previamente, a éste análisis, las siguientes ventajas derivadas de unificar todas las descripciones en un único lenguaje C/C++, merecen ser destacadas. La Verificación de Sistemas: Unicidad Una primera e interesante consecuencia, es que al permitir la verificación Hw/Sw de código a cualquier nivel, podremos iniciar en cualquier momento las verificaciones en los ámbitos de módulo, cluster o ; sin necesidad de esperar a que todos los módulos estén codificados y simulados para dar inicio a las simulaciones de los cluster; ni tener que esperar a que todos los clusters estén verificados para comenzar con la simulación del sistema La figura 1.5 muestra la arquitectura de un sistema de conmutación que se encuentra en fase de desarrollo; en donde se distinguen sistemas que ya han sido implementados en RTL, con sistemas que aún están por codificar - de los que se dispone un modelo C/C++ de referencia a alto nivel. Espec$cación mixta La naturaleza de esta especificación es mixta, C/C++ y RTL. Gracias a una capa de software C/C++ que actúa de interfaz, se mezcla el código RTL de sistemas implementados con el código C/C++ de alto nivel de sistemas aún sin desarrollar. Esta especificación mixta conforma una descripción compacta del sistema en C/C++, que puede ser usada para la verificación a nivel de cluster o de sistema. Esta importante ventaja permitirá reducir el time-t+market drásticamente, ya que se permite tener asegurada la funcionalidad del sistema en todo momento, tanto a nivel de módulo, como a nivel de cluster desde el comienzo del proyecto. Para ello, al codificar un nuevo módulo bastará verificar el mismo frente al modelo C++ de alto nivel. Una vez verificado, se ha de reemplazar el modelo de alto nivel C++ por el nuevo código RTL y continuar con el flujo de diseño. De esta forma, si hubiese fallos en la verificación a nivel de cluster o sistema, el fallo deberá estar acotado en el nuevo módulo o en su interfaz con el exterior. La figura 1.6 muestra que son necesarias tres capas de software, denominadas Capa de Comunicación, Capa de Verificación y Capa de Referencia, para permitir acceder al código RTL desde C++. Esta interfaz C++ permite acceder al código RTL del DUTZ6 O DBV2' directamente en C++, integrando éste con el resto del sistema de verificación C++. El código RTL se ejecuta sobre el simulador HDL externo, y se comunica a través de un interfaz estándar PLI. La Capa de Comunicación es la más próxima al DBV. Se trata de una interfaz PLI que controla la comunicación entre C/C++ y el proceso de simulación de código RTL. La Capa de Verificación contiene funciones para comandar la interfaz Organización del PLI. Básicamente, se encarga de convertir los estímulos al DBV en estructuras de Entorno por Capar datos. Z6Acrónimo del término anglosajón Device Under Test. Z7Acrónimo del término español Dispositivo Bajo Verificación. No confundir el término DUT con el de DBV. Aunque en la literatura anglosajona se alude siempre al término DUT, éste ha de ser sustituido por DBV cuando se refiere, en español, al proceso de verificación. 1.3 Verificación Basada en Simulación simulador ejecutable destinado a asegurar tanto la descripción funcional como las prestaciones del sistema completo. Una vez comprobada su correctitud, el modelo inicial es desgranado. Siguiendo una metodología topdown, se mezcla con el código común de verificación, y se vuelve a generar el simulador y comprobar la correctitud. De esta forma, y en sucesivos pasos, el modelo algorítmico queda transformado en una descripción hardware C++/RTL. En ese momento, la descripción del módulo, se encuentra a nivel C++/RTL; y puede ser fácilmente convertida a código Verilog-RTL de forma automática y libre de errores. Modelo Iardware Código de Pruebas escrito - Comprobacion Funcional y T~innnrcll las Características del Sistema 1 Simulador C+ 3uiado por Eventos Ej ecutable Compilador C++ Figura 1.7: Refinamiento del modelo de comportamiento hasta nivel RTL en C++ Una vez se han expuesto las ventajas derivadas del uso de descripciones mixtas C++ para el entorno de verificación, y la forma de aprovecharlas convenientemente; se procede a analizar las distintas formas de verificación que ofrece el entorno propuesto. Verificación Automática Respecto al Golden Reference El problema que se plantea es comparar una descripción del sistema a nivel mixto Hw/Sw del DBV frente a otra especificación de referencia. Esta clase de problemas, es del tipo Model-Checking. La figura 1.8 muestra la configuración del entorno para la verificación respecto al Golden Reference. Verificación de Sistemas Integrados Metodología de Verzjcación Automática Generación l yGuiado ~~1 1 --A Registro de Sucesos de Simulación I Verificación -1 imul acior Figura 1.8: Verificación respecto al Golden Reference. Tal y como se muestra en la figura 1.8, tanto el DBV como el Golden Reference reciben las entradas de un generador de estímulos. La salida generada por ambas descripciones es comparada continuamente, con lo que se asegura que ambos sistemas presentan la misma respuesta ante los mismos estímulos. El generador de estímulos crea patrones pseudo-aleatorio~~~, en primera instancia. En segundo lugar, los esquemas pseudo-aleatorios se sustituyen por un generador basado en sistemas ATPG?~. En este tipo de sistemas, se busca maximizar la cobertura de fallos de la etapa de verificación mediante un generador de vectores de test que es controlado por un medidor de la cobertura de fallos del sistema. El sistema para el guiado del generador de estímulos es complejo y requiere de técnicas evolutiva^^^. Generalmente, el generador de estímulos está basado en algoritmos genéticos. La función que se ha de optimizar, es una medida de la cobertura de fallos del sistema. Para ello, es necesario definir una métrica de dicha cobertura en función del modelo de referencia (Golden Reference). Es decir, la métrica de cobertura dirige la generación de vectores de verificación. Esta configuración determina un sistema realimentado negativamente que tiende a maximizar la cobertura de fallos del proceso de verificación, de una manera automática. El mismo necesita de un ajuste y dimensionamiento del sistema completo para que sea convergente, junto con la definición de la métrica que se determine. La figura 1.9 muestra una representación gráfica del registro de verificación. La generación del fichero de formas de onda se define en el DBV, donde se ha de 28~n generador pseudo-aleatorio es un algoritmo iterativo que proporciona una sucesión de valores cuyo comportamiento aparentemente es aleatorio, pero conocido el algoritmo de generación y sus parámetros iniciales, dicha secuencia puede ser reproducida. 29~crónimo del término inglés Advanced Test Pattern Generation (Generador de Patrones de Test Avanzado). 30~as técnicas evolutivas son algoritmos que simulan la evolución de las especies y la aplican a la optimización multivariable. 1.3 Verificación Basada en Simulación 25 especificar una traza total - de todas las señales - o parcial - mediante especificación jerárquica - de las señales presentes en el sistema y su evolución en el tiempo. Dicha traza, está conforme al formato VCD3'; ampliamente empleado por los simuladores digitales. De esta forma, cualquier herramienta externa de Rqlstro da Verificacion representación gráfica de formas de onda digitales puede ser empleada para su visualización y10 análisis. Figura 1.9: Representación gráfica del registro de simulación C++ o RTL. El registro de verificación consta de un conjunto de ficheros de texto, visibles con cualquier editor de texto estándar, en los que se anotan todas las incidencias ocurridas durante la verificación, externas a los simuladores hardware. El registro de verificación se divide en el registro de comparación, el registro de error, y el registro de mensajes. El registro de comparación contiene todos los vectores de entrada, junto con la salida generada tanto por el DBV como por el modelo de referencia. El registro de error contiene aquellos vectores de entrada que han generado distinta respuesta en el DBV y en el modelo de referencia, junto con la respuesta de ambos. El fichero de mensajes contiene aquellos mensajes y10 alertas generadas por el entorno de verificación. 1.3.4. La Verificación Basada en Reglas La figura 1.10 muestra el escenario para este otro tipo de verificación. Aquí, la - especificación basada en reglas comanda la entrada al DBV y genera aquellas salidas que deban ser comparadas. En este caso, no existe una comparación continua Basada en Casos Especi@cos 31Acrónimo del término inglés Value Change Dump. 26 Verificación de Sistemas Integrados Especificación de Reglas I - rVerificación Simulación HDL Figura 1.10: Verificación con especificación de reglas. entre la salida del DBV y la especificación; sino que la comparación es puntual dependiente de las reglas definidas. Al igual que en el caso anterior, los simuladores hardware C/C++ o el simulador HDL externo para código RTL, pueden generar el registro de simulación bajo demanda del usuario. El registro de verificación es generado automáticamente, y su contenido es similar al caso anterior. Este tipo de verificación, está orientado a sistemas pequeños, como por ejemplo, la verificación de protocolos o de interfaces entre módulos, clusters o sistemas. Para verificaciones más complejas, es conveniente contrastar automáticamente respecto al Golden Reference, tal y como se describe en el apartado anterior. La finalidad de la especificación de reglas, es obtener una lista de elementos a verificar - assertion rules - partiendo de la especificación más simple para el usuario. De esta forma, el usuario podrá escribir el fichero de reglas directamente desde un C'erlJication ~eport~~. Este método queda encuadrado dentro de la técnica formal de Model Checking. El VerlJication Report debe contener una lista de reglas que modelan el funcionamiento básico del circuito - comúnmente denominadas basic sanity tests - un conjunto de reglas que verifiquen todas las funcionalidades definidas, y una lista de casos extremos - corner cases. Cada regla debe especificar el estado del cual se parte, la entrada al sistema y las acciones que deben ser verificadas. La especificación basada en reglas puede combinar distintos tipos de especificaciones, según se muestra en la figura 1.11. A diferencia de los lenguajes de especificaciones, las reglas son un conjunto de expresiones aritmético-lógicas y de relaciones temporales que se compilan, creando un código C/C++. Para facilitar la sintaxis y la programación al usuario final de la herramienta, se suele disponer de los siguientes elementos: Un lenguaje sencillo para la entrada de las reglas. De esta forma, el usuario especifica las reglas usando un lenguaje propio que es trans~om~ilado~~ a C/C++. 32~s un documento que contiene como debe hacerse la verificación a nivel de módulo, cluster o sistema y que debe ser comprobado exactamente en cada caso. 33C~nvertir una especificación de un lenguaje a otro distinto, de forma automática. 1.3 Verificación Basada en Simulación >enguaje propio le definición IP r~01.i~ ipec ;ación C* basada en reglas Figura 1.1 1 : Distintas formas de generar la especificación de reglas. El objetivo que debe cumplir dicho lenguaje propio, es simple: facilitar la especificación de las reglas lo máximo posible. Las herramientas de transcompilación, no sólo permiten al usuario definir su propio lenguaje mediante un conjunto de token~~~, reglas de sintaxis y reglas de semántica; sino que además permiten especificar como se convierte la especificación del usuario del lenguaje propio a lenguaje C/C++. Objetos C/C++ de alto nivel que permiten especificar las reglas de distinta forma. El usuario puede mezclar en su especificación de reglas diagramas de tiempo, tablas de verdad, especificaciones de máquinas de estado, etc. 1.3.5. Análisis de Prestaciones con Exploración del Espacio de Diseño La verificación funcional se puede realizar con una precisión de ciclo de reloj o, si existen estimadores de retardo, con una precisión cercana al comportamiento real. Como ya se avanzó en el apartado 1.2.1, el no disponer de dichos datos hasta acometer la etapa de síntesis, hace en la mayoría de los casos inviable la ejecución de los casos de verificación con valores de retardo aproximados. En la actualidad las herramientas de síntesis procesan el RTL para obtener un punto del espacio de diseño que cumple con ciertas características, por ejemplo Obtenczón del Punto retardo-área activa o retardo-potencia de consumo. Fijado ese punto, los requiside habajo del tos temporales de cada módulo, cluster y sistema han de ser satisfechos. Puesto Czrcuzto que sólo se oferta un único punto de trabajo, el diseño puede o no cumplir con las especificaciones iniciales. En ese caso sólo quedan dos opciones, se repite la síntesis del elemento discordante para obtener un punto de trabajo mejor, o se recodifica el módulo, cluster o sistema hasta que se obtenga una solución temporal válida. Si se optase por explorar el espacio de diseño de forma óptima, en vez de buscar un único punto del espacio de diseño, se obtendría el conjunto de estos puntos que presentan las mejores prestaciones, lo cual permitiría al diseñador poder es34~érmino anglosajón de símbolo. 28 Verificación de Sistemas Integrados coger el punto de espacio de diseño que cumple las especificaciones y, por tanto, la verificación. Puesto que el paso de síntesis lógica es casi inmediato, el sistema de verificación estaría en disposición de realizar simulaciones basadas en retardos aproximados una vez que cada módulo, cluster y sistema han sido codificados. 1.4. Entorno de Verificación Propuesto La figura 1.12 presenta una diagrama que refleja las principales características del entorno de verificación que propone esta Tesis Doctoral. El entorno de verificación permite realizar la verificación de cada uno de los casos críticos especificados por el verificador o acometer la verificación automátiM~~O~OIO~Í~ de camente. En ambos escenarios el entorno requiere como entrada una implementaVenJicación ción del sistema bajo verificación y el conjunto de especificaciones a comprobar. Un punto clave en todo proceso de verificación es la métrica de cobertura. La métrica ha de ser aportada por el verificador. Un ejemplo de métrica es la Cobe*ura enumeración de los casos a verificar en función de su importancia. Por ejemplo, casos básicos, intencionales o avanzados. Los casos a verificar se describen en un lenguaje cercano al humano, en base a reglas. El lenguaje de reglas permite por ejemplo, generar un determinado patrón de entrada y describir el patrón de salida esperado o patrón a comprobar. El entorno de verificación propuesto tendrá implementadas varias técnicas para generar automáticamente patrones de entrada al DBV y al Golden Reference, además de comprobar que la respuesta del DBV es coherente con la respuesta del Golden Reference. El verificador puede aquí optar por emplear sus propias métricas de cobertura o emplear alguna de las métricas genéricas implementadas en el entorno. Por ejemplo, métricas genéricas como las basadas en: rutas, actividad circuital o potencia de consumo. La verificación se puede realizar con una precisión de ciclo de reloj, con temporización especificada por el usuario o empleando el módulo de análisis de prestaciones que incorpora el entorno de verificación. El módulo de análisis de presExplomción del taciones explora el espacio de diseño del circuito bajo verificación resolviendo Espacio de Diseño la curva completa de prestaciones Área-~etardo o la curva completa de Potencia de Consumo-Retardo. Es decir, una vez el diseño ha superado la fase de síntesis lógica, el módulo de análisis de prestaciones estudia su ruta crítica para explorar su curva de prestaciones de forma óptima. Finalizado el proceso de análisis de prestaciones y verificación del dispositivo a comprobar, se dispone de una implementación en forma de red de puertas lógicas dispuesta para el ensamblado del layout del circuito. 1.5. Organización de la Memoria Así como en este capítulo 1 se hace una introducción a los sistemas de conmutación de última generación, su funcionamiento y verificación, en el capítulo 2 se describen los detalles de la implementación del entorno de verificación propuesto en esta Tesis Doctoral. El enfoque de dicho capítulo está orientado a describir la metodología propuesta para desarrollar la verificación. Se discutirá en detalle la 36 Entorno de Verificación otros scripts que pueden ser incorporados fácilmente. C++ es un lenguaje potente en el cual se puede crear una libreria que contenga los conceptos específicos que son necesarios en verificación. Esta libreria puede ser reutilizada durante un proyecto y también en varios proyectos en desarrollo. La habilidad para emplear programación orientada a objetos y los otros paradigma~ de C++ facilitan la reusabilidad de cada componente de un banco de Habilidad de pruebas, en el ciclo de diseño de un proyecto, o entre proyecto y proyecto en difeCodificación rentes simuladores, y diferentes etapas del desarrollo. La habilidad para usar hilos de ejecución2 es también favorable en la escritura de bancos de prueba. El lenguaje C++ posee sus limitaciones. Con una libreria no diseñada correctamente para ayudar al usuario, la potencia del C++ podria ser difícil de encajar. Un programador novel en C++ podria no ser capaz de crear una clase correcta y eficiente, pero es muy fácil para una persona emplear una clase diseñada e implementada de propósito específico. Con el empleo de los componentes ya implementados en la libreria C++, los usuarios pueden crear y adaptar sus bancos de prueba simplemente mediante la utilización de las clases apropiadas de la librería [18]. Algunas de las ventajas de emplear C++ pueden ser: Comprobación Funcional.- Los diseñadores usualmente comienzan a trabajar con un modelo C++ que emplean como descripción inicial. Esta descripción inicial puede ser dividida en diversos bloques, módulos y demás. Una implementación hardware correcta de esos bloques y módulos es necesaria. Reutilización del Código.- las descripciones de modelos diseñados y sus bancos de prueba pueden ser reutilizados en todo el ciclo de diseño. Parte de los bancos de prueba escritos para un sistema pueden ser reutilizados para desarrollar nuevos sistemas hardware. Encapsulación y Distribución.- Un diseñador podria desarrollar sus propios módulos en C++, y encapsularlos en sus módulos desarrollados en un fichero de libreria y un fichero de cabeceras con la interfaz de entradalsalida del módulo de más alto nivel [21]. En el pasado, se han presentado varias soluciones que permiten especificar sistemas hardware en base a objetos. Por ejemplo, se han propuesto extensiones de lenguajes de descripción hardware para incluir los conceptos de programación Epcifcmión Hmmvme 'Término identificado en la literatura inglesa como thveads [18] Dhananjay S. Brahme, Steven Cox, Jim Gallo, Mark Glasser, William Grudmann, C. Norris Ip, William Paulsen, John L. Pierce, John Rose, Dean Shea, and Karl Whiting. Creating a C++ Library for Test Bench Authoring. Technical Report CDNL-TR-2000-0820, Cadence Berkeley Labs, August 2000. [21] H. Navarro, Juan A. Montiel-Nelson, J. Sosa, and R. Sarmiento. DEMETER: A Novel Framework for Hardware and Software System Specification, Simulation and Verification in C++ XVI Confevence on Design of ciicuits and~nte~vated~~stems, pages 20-23, November 2001 2.2 Trabajos Previos orientada a objetos en [28], [22], y [29]. Existe también la tendencia inversa donde los diseñadores cambian el lenguaje HDL para desarrollar sus productos, en lenguajes orientados a objeto propietarios como el e-lenguaje [20] o C++. Actualmente existen diversas herramientas comerciales y no comerciales que explotan el desarrollo y verificación en C++, y como ejemplo de ello está Superlog [23] de la empresa Co-Design Automation, System-C [16] de CoWare o CynLib [30] de CY ~APPS. En contraste con la mayoría de los simuladores HDL, C++ es un lenguaje compilado3, y obviamente, un modelo de sistema compilado se ejecuta mucho más rápido que un modelo de hardware interpretado; incluso si este es orientado a C++ Frente HDL objeto, además, esta característica no aporta ningún beneficio en tiempo de ejecución. Un código escrito en C++ podría ir hasta 3 veces más rápido que el mismo código escrito en HDL [2 11. /f Modelo / 4 Figura 2.1 : Verificación de un sistema integrado 3~o es así con NC-Verilog, de Cadence, que se compila para ser ejecutado Sowmitri Swami, Arthur Molin, and Burt Counot. Object Oriented Extensions to VHDL. IEEE Computers, 28(10), October 1995. Matthias Bauer and Wolfgang Ecker. Hw. Sw. Co-Simulation in a VHDL-Based Test Bench Approach. Proc. of the 34th Conference on Design Automation, pages 70-75, June 1987. M. Radetzki, W. Putzke-Roming, and W. Nebel. Objective VHDL: The Object-Oriented Approach to Hardware Reuse. Advanced ins Information Technologies, The Business Chalenge, 1997. T. Kuhn, T. Oppold, M Witerholer, W. Rosenstiel, Marc Edwards, and Yaron Kashai. A Framework for Object Oriented Hardware Specification, Verification, and Synthesis. IEEE Design Automation Conference, pages 1 8-22, June 200 1. Peter L. Flake and Simon J. Davidmann. Superlog, a Unified Design Language for Systemon-Chip. IEEE Design Automation Conference, Asia and South PacGc, pages 25-28, January 2000. Open SystemC Comunity. SystemC: Entorno de Desarrollo y Verificación de Sistemas, 2000. CynApps. System Modelling with Cynlib, vl. 1 edition, December 1999. 38 Entorno de Verificación 2.3. Priorización Tomando como premisa que el tiempo necesario para desarrollar y comprobar todas las funcionalidades de un dispositivo, y así asegurar su conformidad con su especificaciones iniciales es muy corto; se plantea la necesidad de priorizar tanto el desarrollo como la ejecución de las diversas funcionalidades especificadas, de acuerdo a algún criterio. Por lo general, dicha priorización atiende al grado de importanciade la función bajo verificación. En los primeros momentos de la etapa de verificación se ha de Ident$c&ón de la I,,,,,, delos realizar una clasificación de las funciones a implementar, asignando un nivel de caros a vei$cm prioridad en relación a su nivel de importancia sobre el conjunto del sistema. Se proponen tres grupos de priorización. Estos son: el grupo básico, intencional y avanzado. El conjunto de casos básicos define aquellas situaciones que han de ser comprobadas al comienzo de la verificación. Las funcionalidades agrupadas en este nivel de priorización implementan los requisitos denominados imprescindibles/mínimos del sistema a verificar. Por ejemplo, dentro de la verificación de un microprocesador, las operaciones de lectura y10 escritura. Dentro de un sistema de conmutación de paquetes, en este grupo entrarían las funcionalidades de configuración del sistema o los sincronismos de y entre diversas interfaces. El conjunto de casos intencionales comprenden aquellas situaciones que han de ser verificadas en segundo lugar, tras la comprobación de todos los casos básicos. La complejidad y la cantidad de los casos intencionales es importante y por lo general muy superior al de los casos básicos. Un ejemplo de casos intencionales, en la verificación de un sistema de conmutación de paquetes, son los errores de CRC y paridad vertical de las interfaces, entre otros. Finalmente, el grupo de los casos avanzados contiene aquellas funcionalidades que plantean situaciones a comprobar, y que por razones de tiempo no son posible caros Avmrados de comprobar si se desea cumplir con el time-temarket del producto. Las funcionalidades incluidas en este grupo de priorización son aquellas que pueden ser obviadas de la funcionalidad final dispuesta en el circuito. No todas las especificaciones iniciales son incluidas en el producto final. En la actualidad, el conjunto de especificaciones iniciales incluyen funcionalidades avanzadas que se añaden al producto final con el objetivo de evaluar su eficacia en futuras versiones. Dichas funcionalidades permanecen ocultas al usuario final del sistema integrado y dan la oportunidad al diseñador de comprobarlas en tiempo real. La figura 2.1 presenta el tiempo requerido para comprobar las especificaciones de un diseño, siguiendo una metodología basada en casos críticos y en casos automáticos, para todos los niveles en la verificación. El tiempo requerido si todo el proceso se realizase en serie sería extraordinariamente superior al time-temarket (plano derecho superior en la gráfica). 2.4. Modelos de Verificación Independientemente del número de casos, propiedades o funcionalidades a comprobar en el sistema bajo verificación, esta se puede realizar en base a las llamadas esquinas críticas4 o mediante un sistema de generación de casos automátiMetodologia cos. Es importante tener en cuenta que no se ha de limitar la comprobación del 4Referenciado en la literatura anglosajona como come? cases o casos críticos 40 Entorno de Verificación Comprobmión de Resultados HDL empleado y el lenguaje de programación de alto nivel utilizado. Por ejemplo, se traducen las estructuras de datos complejas de C/C++ a bits y bytes de Verilog XL mediante las librerías PLI - en caso de describir el entorno de verificación con C/C++ y seleccionar el simulador HDL Verilog XL de Cadence. Capa de Verificación.- Contiene diversas funciones directas e inversas para traducir los comandos de entrada en lenguaje natural en cadenas de estímulos dispuestas para administrarse a la Capa de Comunicación. Además, esta capa posee diversas rutinas de comprobación. Estos procedimientos de verificación realizan comparaciones entre la respuesta del sistema a un conjunto de estímulos y su respuesta esperada. Las funcionalidades implementadas en esta capa del entorno de verificación se corresponden por ejemplo con diversos compiladores que permiten al verificador implementar un lenguaje cercano al humano a la hora de especificar sus casos críticos. Además se incluyen las funciones típicas de cálculo de CRC con diversos polinomios o paridad. Ficheros de Estímulos.- Son el conjunto de ficheros que indican a la Capa de Verificación como generar la cadena de datos a aplicar al dispositivo bajo verificación. Existe al menos un fichero de estímulos por cada interfaz del sistema. Los estímulos especificados dentro de cada fichero se corresponden con una sintaxis y léxico definido en la Capa de Verificación por el verificador. Además, hay diversos ficheros de configuración que definen el modo de operación de la interfaz. Estos ficheros de configuración también siguen la especificación expresada por el verificador en la Capa de Verificación. Ficheros de Comprobación.- Están formados por un conjunto de ficheros que definen el comportamiento de las salidas de las interfaces. Se pueden definir, opcionalmente, en cada interfaz del dispositivo bajo verificación. Poseen una estructura interna parecida a la de los ficheros de estímulos, salvo que en estos se incluyen estructuras condicionales que permiten tomar decisiones donde sean necesarias. Por último, dentro del sistema de ficheros de comprobación se encuentra el fichero de traza de cada interfaz. En este último fichero se reflejan todos los datos y eventos acaecidos en la interfaz. Las capas de comunicación y verificación proveen una primitiva de comunicación para cada interfaz fisica del sistema, e independiente. Esto permite realizar actualizaciones de cualquier parte de la interfaz sin afectar al resto de las interfaces del DBV. Esas interfaces son básicamente un enlace entre el verificador y el simulador hardware empleado. 2.4.2. Automático El modelo automático se basa en el llamado modelo de referencia o patrón6 que, normalmente, está codificado en un lenguaje de alto nivel como C/C++. Esta n-rodeloautomático descripción a nivel de circuito integrado, cluster o módulo provee el comportamiento de referencia del circuito bajo verificación. El objetivo en este modelo de funcionamiento, es emplear el sistema de referencia para verificar casos generales y comprobar las prestaciones del sistema, 6En la literatura anglosajona referenciado como GoldenRefevence. Filosoflar de Ejecución Simuladorespor Eventos Simuladores slot-timi 'Término referenciado en la literatura anglosajona como slot-time Entorno de Verificación La idea básica es reutilizar el entorno de simulación de la arquitectura, bloques o módulos para generar las salidas esperadas, definida una configuración de los mismos. Ello implica configurar, ejecutar y sincronizar el modelo de referencia y la implementación del DBV, con el objeto de comprobar que ambos modelos presentan salidas idénticas. Atendiendo a la naturaleza de ejecución de los simuladores desarrollados hasta ahora, estos se pueden clasificar en dos tipos. Los guiados por eventos y los basados en slot temporaless. A pesar de parecer dos filosofías completamente independientes, nada más lejos de la realidad, todos ellos emplean eventos. Las ocurrencias de sucesos define el concepto de evento. Lo que los diferencia es la temporización que ejecutan. Los llamados simuladores guiados por eventos se emplean cuando la carga temporal del sistema a simular es baja con respecto al tiempo de ocurrencia de los mismos, es decir, cuando los tiempos entre eventos es grande. La aplicación - que desarrolla este tipo de metodología se basa en crear una lista temporal de eventos. La cabeza o primer elemento de la listarepresenta el evento más cercano a ejecutar. Y la cola o último elemento, el evento más lejano a ejecutar. La aparición de un evento, implica que éste sea insertado ordenadamente en la lista de eventos, para que el núcleo de ejecución pueda seguir la cronología de eventos o sucesos del sistema. La variable que representa al tiempo en este tipo de simuladores es incrementada con la ejecución de cada evento de la lista. Dichos incrementos no son constantes, pues la distancia temporal entre eventos es variable. Cuando la carga temporal de eventos es muy alta, o dicho de otra forma, existe una muy alta probabilidad de ejecutar uno o más eventos en cada instante de tiempo, se demuestra, que los simuladores basados en técnicas slot-time son más eficientes que los guiados, puramente, por eventos. Esto es debido, principalmente, a que si se tiene la certeza de la existencia de al menos un evento en cada instante de tiempo, la cola de eventos es inoperativa, pues el núcleo de simulación crea y destruye eventos en casi todos los instantes de reloj. El modelo basado en slot-time ejecuta en cada instante de reloj al menos un evento. La variable que representa el tiempo en este tipo de simuladores se incrementa en una unidad cada vez que se ejecutan todos los eventos de un slot-time En general, los simuladores de conmutadores de paquetes están basados en núcleos de ejecución slot-time, pues para obtener las prestaciones del mismo se ha de simular éste en alta carga, y por tanto, hay una muy alta probabilidad de ocurrencia de suceso en cada instante de tiempo. Pero, por otro lado, hay que tener en cuenta que los simuladores de lenguajes como VerilogIVHDL poseen núcleos de ejecución guiados por eventos, fomentado este hecho por la propia naturaleza del RTL. En resumen, la Capa de Referencia se añade para sincronizar los eventos de la Capa de Verificación con los eventos el modelo de referencia. Es decir, para unir los mundos de simulación basada en eventos del código RTL con el mundo de los eventos del modelo de referencia, pudiendo ser este último basado en eventos o slot-time, según se halla desarrollado el modelo de referencia con uno u otro núcleo de simulación. 2.5 Visión General del Entorno 2.5. Visión General del Entorno Aunque C++ es un lenguaje de propósito general y por si mismo no está diseñado para modelar hardware, los conceptos importantes del hardware se pueden encapsular con un sistema de clases y los métodos apropiados [3 11. Mientras que C++ es un lenguaje predominantemente secuencia1 la ilusión de concurrencia y las estructuras estáticas son logradas mediante diversas utilidades de multihilo9, detalles permanecen ocultas al usuario [32]. La figura 2.4 presenta el entorno propuesto, que permite la verificación de dispositivos mediante la ejecución de bancos de prueba escritos en C++, controla a un simulador HDL, como por ejemplo Cadence XLINC. La comunicación con el simulador HDL se realiza mediante una Capa de Comunicación, la cual realiza funciones de acceso a la capa fisica del HDL. La Capa de Comunicación también actúa con la interfaz de la Capa de Verificación. La Capa de Verificación es donde se describen los bancos de prueba [33]. En las etapas iniciales del desarrollo de un circuito integrado, solamente se encuentra disponible una descripción del dispositivo en lenguaje HDL, los bancos de prueba se ejecutan entonces sobre una estación de trabajo donde reside el simulador. Poco a poco, esta descripción pasa a ser un ASIC. Con el fin de mantener una interfaz entre la descripción HDL (software) y la parte de la descripción mapeada en el ASIC (hardware), una sección de la capa de acceso fisico ha de ser transferida a memoria y ejecutada en un microprocesador. El resto de esta capa comunica el microprocesador y la estación de trabajo - donde reside el simulador. Las otras dos capas - Capa de Comunicación y de Verificación - continuarán ejecutándose en la estación de trabajo, permaneciendo sin alteraciones durante el ciclo de diseño. 2.6. Interfaces Atendiendo a los protocolos de comunicación empleados en la actualidad tanto entre módulos, clusters o sistemas integrados, se puede concluir que hay tres tipos básicos bien diferenciados. A medida que dichos tipos básicos se emplean en un nivel de integración superior, su refinamiento es mayor. Además, sobre dichos tipos básicos se realizan diversas aportaciones que suponen la inclusión de alguna novedad sobre estos tres tipos básicos. Estos tres tipos básicos son: las interfaces serie de alta velocidad, las interfaces de gran ancho de palabra paralelas y las interfaces de control o CPU. Las interfaces serie pueden ser sincronas o asincronas. Por lo general, son asincronas, con lo cual se ha de conocer la velocidad de bit, velocidad de muestreo, 'Traducción directa del término anglosajónMuti-thvead. M. V. Shahdadpuri, J. Sosa, H. Navarro, Juan A. Montiel-Nelson, andR Sarmiento. ANew Framework for Hardware System Verification Based on C++ XVI Confevence on Design of Civcuits andIntegvatedSystems, pages 20-23, November 2002. M. V Shahdadpuri, J. Sosa, H. Navarro, J.A. Montiel-Nelson, and R. Sarmiento. WSTA: A System Level Verification EnvironmentBased on C-H. InPvoc. of SPIE of VLSI Civcuits andsystems, May 2003. J. Sosa, J. A. Montiel-Nelson, H. Navarro, M. V Shahdadpuri, and R. Sarmiento. SystemLevel Verification Methodology for Advanced Switch Fabrics. In Pvoc. of SPIE of VLSI Civcuits andsystems, May 2003. Implementación Interna Entorno de Verificación Figura 2.4: Entorno de desarrollo de bancos de prueba. la marca de comienzo y fin de transmisión. Este tipo de interfaz se diseña en la mayoría de los casos en el límite de la tecnologia seleccionada para obtener una alta tasa de transmisión/recepción. En particular, en los sistemas de comunicación basados en paquetes se emplean para comunicar las distintas unidades origen y destino. Las interfaces paralelas nacen como evolución de la tecnologia serie, realizando la transmisión paralela de varios bits a un mismo tiempo. El ancho de palabra es el que realmente determina la tasa de bits transmitido. Estas interfaces pueden ser síncronas o no con un reloj. Y cuando son síncronos, dicha señal de reloj puede estar omitida en el bus. Un ancho de palabra superior al bit transmitido por un puerto serie permite reducir la velocidad de transmisión/recepción del puerto paralelo. No obstante, se ha de tener en cuenta que a mayor ancho de bit, el dispositivo empleará un número mayor de terminales y superficie de interconexionado. Ello implica grandes problemas de interconexionado a nivel de sistema y circuito integrado. Por último y no por ello menos importante, se incluye una interfaz de control o CPU. Esta no es una interfaz dedicada a la transmisión masiva de datos como es el caso de la serie o paralela, su utilidad se centra en controlar el dispositivo y10 permitir el acceso a la información de depuración en el mismo. Suele tener una estructura parecida a la interfaz paralela, al que se han añadido diversas señales con múltiples propósitos, como por ejemplo, las señales de interrupción10 o reset". A continuación se describe en detalle cada una de las interfaces implementadas en el entorno de verificación. En el modelo basado en casos críticos, el usuario ha de proveer los estímulos de entrada, los ficheros de configuración y opcional- ''Una interrupción es una señal que indica al dispositivo que la recibe, que ha de salvar el contexto de ejecución en que se encuentra y pasar a ejecutar una rutina de servicio específica al evento acaecido. "El veset no deja de ser una señal de interrupción que indica al dispositivo que comience su ejecución desde el inicio de la rutina de funcionamiento normal. 2.6 Interfaces 45 mente los de comprobación de los estímulos de salida para cada interfaz. Es decir, al menos un fichero de estímulos y configuración por cada interfaz serie, paralela y10 de CPU presentes en el dispositivo bajo verificación. Opcionalmente, el verificador puede incluir el fichero de respuestas esperadas por cada interfaz. En el modelo automático, la Capa de Referencia emplea el dispositivo patrón para obtener los estímulos de entrada y los estímulos esperados en cada interfaz. Los ficheros de configuración de cada interfaz han de seguir siendo especificados por el verificador. En los próximos apartados la Capa de Referencia será obviada con el objeto de aclarar correctamente la descripción de cada interfaz. Esta capa sería tan sólo un traductor de los eventos del simulador basado en slot-time al simulador guiado por eventos, Recepción , Registro , Transmisión Figura 2.5: Diagrama de bloques de la interfaz paralela. u 1 u 2.6.1. Interfaz Paralela 2 La Capa de Comunicación paralela es altamente dependiente de la interfaz fisica RTL paralela. La Capa de Verificación es un grupo de funciones y procedimientos que permiten al entorno acceder a la interfaz paralela RTL y comprobarla. Bs,hd,, La interfaz paralela implementada se corresponde con el estándar CSIX [34]. Esta interfaz se corresponde con un puerto paralelo de ancho de palabra variable y Recepción del 1 1 Transmisión del Interfaz Paralelo I 1 Interfaz Paralelo [34] Common SwitchInterface Consortium. CSIX-LI: Common Switch Inte$ace SpecficationLI, VIO edition, May 2000. I I 52 Entorno de Verificación fichero de gestión, este es leído por el Lector de Gestión y ejecutado en el Gestor de CPU. Si durante el normal funcionamiento de la interfaz surge una interrupción, el Gestor de CPU guarda el contexto de ejecución y procede a dar el control al Gestor de Interrupciones. Si se ha especificado un fichero de interrupción se procede a ejecutar el código del programa que allí se indique tras leerlo con el Lector de Interrupción. Puesto que algunas interfaces de CPU proveen diferentes niveles de interrupción en su normal ejecución. Se ha dotado a la interfaz de CPU la posibilidad de trabajar en dos modos: Modo Independiente.- Cada interrupción a atender se le asigna un fichero a ejecutar. Cuando surge una interrupción, el fichero asignado es ejecutado inmediatamente. Modo Nw1ndependiente.- Sólo existe un único fichero de interrupción que contiene diversas subrutinas. Cuando surge una interrupción es ejecutada la siguiente subrutina del fichero de interrupciones. En la interfaz, cada vez que se hace uso de una dirección de memoria o reDireccionamiento gistro, esta se comprueba con una simple llamada al Gestor de Direccionamiento. El Gestor de Direccionamiento también hace funciones de traductor de direcciones especificadas mediante etiquetas a direcciones fisicas. Para ello se hace uso de la unidad de Resolución de Direcciones. Esta última unidad de la Capa de Verificación requiere la presencia del fichero de direccionamiento, el cual posee la relación de direcciones válidas del sistema acompañada cada una de ellas de su correspondiente etiqueta. Para finalizar, en todo momento se traza la ejecución de la interfaz mediante llamadas a la unidad de Escritura de Traza de CPU. 2.7. El Sistema de Ficheros El sistema de ficheros se define para cada interfaz fisica como un conjunto de archivos de texto que permite al verificador describir los casos críticos, rápidaEspec$cación de ~sfiin~i~~ y mente, y mediante un lenguaje sencillo basado en comandos. Respuesta Los ficheros de salida contienen los paquetes salientes de cada interfaz. Los ficheros de entrada describen los estímulos de entrada. Y los ficheros de comprobación contienen paquetes de referencia a comprobar. Además, existen ficheros de traza y registro que permiten hacer seguimientos estadísticos y de depuración. Los comandos que contienen dichos ficheros pueden comportarse de tres formas distintas según lo que dispongan sus argumentos; por defecto, condicional o incondicional: Por Defecto: define un comportamiento que se seguirá de forma genérica salvo que se especifique lo contrario. Por ejemplo, denegar todas las peticiones de conexión que se reciban hasta que se completen un número total de denegaciones. i Condicional: el comando es ejecutado si se verifica una condición dada. Por ejemplo, la existencia de una petición determinada o CRQ especificado. 2.7 El Sistema de Ficheros 53 Este modo permite guiar la verificación en aquellos casos que no se tiene la certeza exacta de la ocurrencia de un evento concreto. Por ejemplo, acepta las n primeras peticiones que procedan de un puerto cuya dirección sea par. m Incondicional: es un comando que es ejecutado inmediatamente - sin atender a circunstancia alguna. Una vez éste es leído por la Capa de Verificación, se genera latrama de datos que se corresponde a lo especificado en el mismo y se introduce en el DBV. 2.7.1. Ficheros de la Interfaz de Enlace Serie Los ficheros de estímulos de la interfaz de enlace serie están compuestos por los reconocimientos de conexión o ACK, las peticiones de conexión o CRQ, los paquetes de referencia o de comprobación y los paquetes de estímulos o de entrada. La tabla 2.1 presenta los comandos soportados en el sistema de ficheros serie. La primera columna de la tabla 2.1 indica el fichero específico donde se albergan los comandos. La segunda columna presenta los comandos soportados. Y para finalizar, la última columna realiza una pequeña descripción del objetivo del fichero. Tabla 2.1: DESCRIPCI~N DE LOS COMANDOS PERMITIDOS EN LA INTERFAZ SERIE 1 Fichero 1 Comando 1 Descripción 1 comprobación 1 Framming 1 Estímulos y cional ACKParity CRC OverHead PayLoad FlowControl Idle Fichero ACK Genera una trama de datos a enviarlcomprobar t i 5 Generales sobre el contenido de las tramasi 5 En este fichero, para un enlace serie dado, se especifican los reconocimientos de conexión. El comando de Aceptación de una petición de conexión puede definir un estado por defecto para el comportamiento de la interfaz, condicionar la A@miónde Recurso aceptación a una petición CRQ concreta o especificar en todo momento incondicionalmente qué conexión se concede o no. t Comando que define un funcionamiento por defecto, i condicional e 5 inconc Fichero CRQ En este fichero se especifican los CRQ esperados en un enlace serie. Se permite especificar qué CRQ ha de aparecer en la próximo paquete a recibir. Este ,,i,ó, fichero no permite la inclusión de comandos generales. 54 Entorno de Verificación Fichero de Entrada y Fichero Comprobación En estos ficheros se especifican las caracteristicas de los paquetes que se enviarán o se comprobarán en la interfaz serie. Figura 2.8: Generación de células de datos, relleno y ráfaga en la interfaz serie. El comando de generación crea un conjunto de paquetes, dado una fuente y un puerto de destino, un tipo y una clase, una longitud de carga y una carga útil. Cuando no se genera paquete alguno se insertan por defecto paquetes de relleno o espera14, estos son llamadas ráfagas de paquetes de relleno o espera. La figura 2.8 ilustra una ráfaga de paquetes de relleno generadas con el comando. Además tras una secuencia de paquetes de datos y de relleno, suele especificarse también la llamada ráfaga de paquetes de relleno. También se definen una serie de comandos genéricos que permiten modificar diversas caracteristicas implementadas en el interfaz como el control de flujo de control y de datos. Además existen comandos específicos que inyectan errores y alteran las caracteristicas normales de las tramas como lo son los errores de CRC, paridad, framming, entre otras para más detalle véase [35] y [33]. 2.7.2. Interfaz Paralela La interfaz paralela es más simple que la interfaz serie. Las entradas son el fichero de paquetes a enviar y el fichero de comprobación. Fichero de Paquetes de Entrada y Comprobación Los paquetes pueden ser especificados de tres formas: como una traza de paquetes, como porcentajes de los paquetes generados aleatoriamente o como porcentaje de trazas que han de ser generados aleatoriamente, El comando de generación para la interfaz paralela - sigue la misma filosofía de generación que las tramas de la interfaz serie - crea un conjunto de paquetes, dado un puerto de destino, un tipo, una clase, una longitud de carga y la carga útil. Genermión de Entre paquete y paquete especificado, se inserta el número de paquetes de relleno Estímulos indicados. Al final del proceso de generación de los paquetes especificados se añadirán también el número de células de relleno que se especifica, este último conjunto de paquetes de relleno se llama ráfaga de paquetes de relleno al igual que en el puerto serie. I4Identificadas en la literatura como paquetes idle. Son paquetes que se emplean cuando hay carencia de datos que transmitir y se ha de mantener el sincronismo de la interfaz. [35] J. Sosa, H. Navarro, MV Shahdadpuri, J.A. Montiel-Nelson, and R. Sarmiento. A ChipLevel Verification Methodology for Next-Generation Switch Fabric. In XW Confevence on Design of Civcuits andIntegvatedSystems, November 2002. [33] J. Sosa, J. A. Montiel-Nelson, H. Navarro, M. V Shahdadpuri, and R. Sarmiento. SystemLevel Verification Methodology for Advanced Switch Fabrics. In Pvoc. of SPIE of VLSI Civcuits and Systems, May 2003. 2.8 Características Avanzadas 55 Tabla 2.2: DESCRIPCI~N DE LOS COMANDOS PERMITIDOS EN LA INTERFAZ PARALELA t Coma Fichero Estímulos y Comprobación Comando genCFrame class tYPe paylen Vparity Hparity PayLoad FlowControl DataFlow Memorv Descripción Genera una trama de datos a enviarlcomprobar t i 5 Generales sobre el contenido de las tramasi 5 J lo que define un funcionamiento por defecto, i condicional e 5 incor licional La tabla 2.2 presenta el conjunto de comandos disponibles en el sistema de ficheros de la interfaz paralela. Al igual que los de la interfaz serie, hay comandos - que permiten inyectar errores en la interfaz y comandos que permiten modificar las características del normal funcionamiento del mismo entre otros - para más detalle diríjase a la referencias [35] y [33] 2.7.3. Interfaz de CPU Se provee un traductor de direcciones. Se define una tabla con las etiquetas de la CPU y sus direcciones fisicas. El otro fichero de CPU posee tres comanEjecución de Rutinar dos básicos; cpuwr para escribir en memoria, cpurd para leer de esta y wait para deseniicio e demorar la ejecución varios ciclos. Interrupción Al comienzo de la verificación, el fichero de configuración de la CPU define la inicialización de los registros y memoria de CPU del DBV. Una vez se han inicializado dichos registros, el fichero de comprobación es ejecutado. Si surge una interrupción, el fichero de interrupción de CPU se ejecuta tal como se ha definido en el apartado 2.6.3. Cuando la rutina de servicio de la interrupción finaliza, la interfaz de CPU retorna a la sentencia previa del fichero de comprobación de CPU. 2.8. Características Avanzadas La verificación de los sistemas actuales requieren de técnicas avanzadas no implementadas hasta ahora en los entornos de verificación tradicionales. A continuación se describen cuatro técnicas avanzadas en la verificación de sistemas integrados. 2.8.1. Inyección de Errores En general es necesario no sólo comprobar que el sistema integrado bajo verificación se comporta correctamente en condiciones de ejecución normales. Es Inducir usual que los nuevos dispositivos se diseñen para soportar cierto conjunto de erro- ,m,,mientos res, lo cual induce la necesidad de insertar dicho conjunto de errores durante su E~&icos 56 Entorno de Verificación normal funcionamiento. Todas las interfaces desarrolladas poseen diversos comandos que permiten inyectar errores en la propia interfaz con el objeto de comprobar si el sistema bajo verificación continua su ejecución adecuadamente o, por el contrario, su ejecución se altera. Por ejemplo, introducir errores en la paridad o el CRC de un paquete, acceder a posiciones de memoria o registros inexistentes, errar el tipo o longitud del paquete, son algunos de los errores utilizados más comúnmente. 2.8.2. Sincronización de Interfaces Frecuentemente, se requiere que durante el normal procesamiento de los estímulos de entrada en dos o más interfaces exista una determinada sincronización. Por Aplicmión de ES~~~UIOS ejemplo, dos interfaces han de ser estimulados simultáneamente con un conjunto Smuitmieos de vectores introducidos síncronamente a partir de un punto determinado de la verificación. La figura 2.9 ilustra un ejemplo de las secuencias de estímulos de entrada en ambas interfaces. Se asume que, para la interfaz paralela O, la secuencia a procesar antes de la sincronización es mayor que la secuencia a procesar en la interfaz paralela 1, y se requiere sincronizar los estímulos identificados como @ y A. Fichero de Entrada O Fichero de Entrada 1 Eventos Marcas Figura 2.9: Sincronización de la interfaz paralela Para la interfaz paralela O, el simbolo A es su evento de disparo en la sincronización. Y para la interfaz 1 lo es el simbolo @. Además, el simbolo @ es una marca de sincronización en la interfaz O y el simbolo A lo es para la interfaz 1. Obsérvese que para cada interfaz del ejemplo, los símbolos de marca y evento se encuentran en la misma línea de comandos. Ambas interfaces paralelas procesarán cada uno de sus estímulos de entrada, independientemente. Este comportamiento se modifica cuando una interfaz lee una marca de sincronización. En ese caso, la interfaz se mantiene a la espera hasta que aparezca el evento de disparo correspondiente. Una vez el evento de disparo aparezca, la interfaz continuará su normal ejecución. Igualmente, este sistema de sincronización ha sido adoptado entre las interfaces serie y CPU. Además, se ha provisto de un sistema idéntico para lograr la sincronización entre interfaces de distinta naturaleza, como por ejemplo serieparalelo. Con la implementación realizada, se puede hacer aguardar a múltiples interfaces por un único evento que se producirá en otra interfaz. 2.8 Características Avanzadas 2.8.3. Jitter de Recepción Serie En general, toda interfaz serie asíncrona está sometida a la aparición de un retraso en el inicio de la comunicación. Con el objeto de dar soporte a este tipo de comportamiento, se ha implementado una unidad de gestión del jitter'' [36]. En particular, aplicada a los puertos serie de alta velocidad empleados en los conmutadores de paquetes, se ha implementado una unidad con un retardo de jitter máximo de *k golpes de reloj serie [37] y [38]. Gracias a esta unidad el entorno de verificación es capaz de adaptarse al posible jitter que aparecerá en su sección de recepción. Por otro lado, se ha implementado un generador de jitter en la etapa de transmisión, que permite comprobar si el dispositivo bajo verificación soporta sus especificaciones en lo referente al jitter admitido. Estas unidades se incorporan en la Capa de Comunicación y se insertan entre la linea de recepción y la unidad de transmisión, y la linea de transmisión y la unidad de recepción. La figura 2.10 muestra la conexión para el caso de la linea de recepción del dispositivo. Capa de Comunicación DE! 4 S Generador Lmea de Fkcepcion A*A ~A de Jitter A:.: del Interfaz Serie Figura 2.10: Detalle del módulo de generación de jittev en el diagrama de bloques de la interfaz serie. 2.8.4. Inserción de Nuevos Casos en Tiempo de Ejecución Una vez ha sido iniciada la ejecución del entorno, éste no se para por si sólo. El usuario puede finalizarlo si lo interrumpe definitivamente o lo pausa momentáneamente desde el panel de control. El entorno permite cambiar los ficheros de verificación en tiempo de ejecución. Para hacer esto, el usuario ha de pausar momentáneamente la simulación y escribir los nuevos ficheros, los cuales serán ejecutados según se reanude la simulación. Cuando se reanude la simulación, el entorno sustituirá el contenido de los ficheros actuales por el contenido del nuevo. Esta característica permite evitar tener que inicializar los sistemas bajo verificación ya que, por lo general, es muy costoso; hay que configurar el sistema, sincronizar cada uno de las interfaces y, finalmente, situar el dispositivo en las I5Se define el jittev como: las pequeñas variaciones no acumulativas de los instantes significativos de una señal digital con relación a sus posiciones ideales en el tiempo. - G.701. Vocabulary of Digital Transmission and Multiplexing, and Pulse Code Modulation (PCM) Terms. Technical report, Intemational Telecommunication Union (ITU), March 1993. Whenwu Zhu, Yiwei Thomas Hou, Yao Wang, and Ya-Qin Zhang. End-to-End Modeling and Simulation of MPEG-2 Transport Streams over ATM Networks with Jitter. IEEE Tmnsactions on Civcuits and Systems fov Vldeo Technology, 8(1):9-12, February 1998. Yishay Mansour and Boaz Patt-Shamir. Jitter Control in QoS Networks. IEEE Tmnsactions on Nehvovking, 9(4):492-502, August 2001 Simulación de Errores de Sincronismo Sene Reducción del llempo de Inicialiración 58 Entorno de Verificación condiciones iniciales de la prueba a la que se va a someter. Esta característica es necesaria en la mayoría de los casos, porque son pocos los simuladores que poseen función alguna de almacenamiento y carga del estado de la simulación (sn~~shot'~). 2.9. Implementación Interna El entorno de verificación descrito en este trabajo se ha implementado mediante diversas librerias programadas en C++ y organizadas en cuatro niveles de Implementoción Jmiquica jerarquía. Dichas librerias están ordenadas desde el nivel O al nivel 3. El nivel inferior ó O es el de menor abstracción y, por tanto, más cercano al nivel fisico o simulador RTL. El nivel 3 o nivel superior, posee un alto nivel de abstracción que permite desarrollar la verificación en lenguajes de alto nivel. La figura 2.11 muestra el esquema de niveles descrito. Nivel 3 Procedimientos de Listas y Datos Complejos Funciones de Datos Estmctmdos , . y-7 Datos Estructurados Y? -S- <> ++ Nivel 1 Operaciones de Datos Simples I I ,, Y? ~atos Simples Y? <> <> <> Nivel O Procedimientos de Acceso Físico íie PLI) Eventos Svstem C Demeter Figura 2.11: Esquema a nivel de bloques de las librerías implementadas 2.9.1. Nivel O El principal propósito de este nivel es el de comunicar las diversas funciones de alto nivel descritas en C++ con el simulador HDL, convirtiendo las estructuras de datos y tipos de C++ a tipos soportados por el simulador empleado. El simulador podría ser SystemC, Demeter [21] o Cynlib que están basados en C++; o Nivel Boja 16Unmapshot se define como una captura de las variables del sistema en ejecución. Unmapshot permite retomar la simulación de un sistema al tiempo en el cual este mapshot se realizó, sin pasar por los estados anteriores que le dieron origen. [21] H. Navarro, Juan A. Montiel-Nelson, J. Sosa, and R. Sarmiento. DEMETER: A Novel Framework for Hardware and Software System Specification, Simulation and Verification in C++ XVI Confevence on Design of Civcuits andIntegvatedSystems, pages 20-23, November 2001 2.9 Implementación Interna 59 podría ser un simulador comercial HDL como, por ejemplo, NC-Verilog, Verilog XL, o NC-VHDL. En caso de ser el simulador Verilog se emplea la Interfaz de Lenguaje de Programación PLI [39], [40] a la hora de implementar la pasarela HDL/C++. 2.9.2. Nivel 1 El propósito principal de esta capa es operar con las señales y manipular sus valores. Este nivel actúa como interfaz entre los tipos de datos fisicos, i.e., cableado, registros, Booleanos, enteros y enteros largos1'; y los tipos de datos de alto nivel del usuario del entorno. Los tipos de datos de usuario son aquellos datos que n~Bá.co~deAlt0 Nivel puede emplear el diseñador dentro del entorno. Los tipos de dato de usuario son: Booleano (bool-t), enteros con signo y sin signo (int-t y uint-t respectivamente), real (float-t) y complejo (complex-t). Las operaciones en este nivel dependen del ancho del bus y del modo de operación o alineamiento del tipo de dato empleado. El modo de operación o alineamiento se define en referencia a la representación bajo nivel del dato (modo más ~i~nificativo'~, o modo menos significativo19). Por ejemplo, si el byte más significativo es el de mayor peso en un bus o, por el contrario, el byte de más peso en el bus es el menos significativo. Nótese que este nivel es transparente al usuario, aunque él puede redefinirlo, si así lo desea. 2.9.3. Nivel 2 En este nivel se definen los datos simples de usuario. En muchas aplicaciones se emplean cientos de bits de precisión; pero pocas de ellas necesitan miles o millones de bits. El objetivo es disponer un entorno con un número ilimitado de bits por bus. Así sería posible definir un bus que no estaría limitado por el sistema %pos Báricos operativo donde se ejecuta el entorno. En este sentido, este entorno supera las BxtendidosdeAIto funcionalidades provistas por otros entornos de desarrollo orientado a objetos, tal N~WI como Specman de Verisity Inc [20], que no permite declarar un entero que supere los 64 bits. Para soslayar dicho escollo, se propone emplear las librerias aritméticas multiprecisión de GNUZO. Estas son unas librerias portables escritas en C para aritmética entera arbitraria sobre enteros, números racionales y números en punto flotante. La librería GMP es la implementación más rápida, en tiempo de computación, posible para las aplicaciones que necesitan altas precisiones. En la actualidad la implementación de estas librerias se realiza directamente en el código nativo de cada máquina y soporta los tipos básicos de C. Las librerias GMP poseen algoritmos que ajustan la precisión de las variables para alcanzar la precisión requerida, pero manteniendo mínimo la cantidad de LibredaMafemáfica "En Verilog, este tipo se llama time. de GNU 181dentificado en la literatura anglosajona como Big Endian Mode(BEM). "Traducción del término Little Endian Mode(LEM) 'OGNü Multiple Precision Arithmetic Library (GMP). [39] IEEE 1364 Verilog Standard. VenlogPLI 1.0, November 2000. [40] Stuart Sutherland. Tke Venlog PLI Handbook. Kluwer Academic Publishers, 1999. [20] T. Kuhn, T. Oppold, M Witerholer, W. Rosenstiel, Marc Edwards, and Yaron Kashai. A Framework for Obiect Oriented Hardware Specification, Verification, and Synthesis. IEEE Design Automation Confevence, pages 18-22, June 2001 60 Entorno de Verificación Tabla 2.3: TIPOS DE DATOS Y OPERANDOS SOPORTADOS POR EL NIVEL 2 Tipo bootf intf uintf floatf complexf Ooeradores Sooortados Descrioción igual a, no igual y, o, o exclusiva, negación conversión desdela entero de C++ igual a, no igual, mayor que, menor que, mayor o igual, menor o igual suma, resta, multiplicación, división prelposincremento, potencia, raíz enésima y, o, o exclusiva, negación conversión desdela entero codsin signo de C++ Booleano Entero con signot Ídem que intf Entero sin signot igual a, no igual, mayor que, menor que, mayor o igual, menor o igual suma, resta, multiplicación, división, potencia raíz enésima, logaritmo, logaritmo natural arcolseno, arco/coseno, arcoltangente conversión desdela entero codsin signo de C++ conversión desdela flotanteldouble de C++ Ídem que floatf más funciones hiperbólicas Número complejot memoria requerida. La velocidad de ejecución de las funciones en las librerias GMP se ha optimizado mediante el empleo de palabras completas de tipos básicos y su aritmética empleando algoritmos avanzados. Además se han optimizando dichos algoritmos hasta nivel de ensamblador. En este sentido, dichas librerias se han desarrollado con más énfasis en la optimización a nivel de ensamblador que en la claridad y simplicidad del código. Por ello, además de existir un código genérico que se puede compilar en cualquier máquina que posea gcc21, hay versiones de código optimizada para la mayoría de los procesadores actuales como los AMD K6, Intel Pentium, IA-64 y SuperSPARC, entre otros [41]. Los tipos básicos de GMP son el mpz-t para la ejecución de aritmética entera y mpf-t para punto flotante. Los tipos de datos estructurados implementados se muestran en la tabla 2.3. En la primera columna se presenta el nombre del tipo. En la segunda columna se introducen los operadores que soporta dicho tipo de datos estructurado. Por último, la tercera columna realiza una pequeña descripción de cada tipo. A continuación se esbozará someramente cada uno de los tipos, para más detalle diríjase "gcc es el acvónimo de GNU C Compilei: compiladov C de GNU. [41] Torbjom Franlund. The GNü Multiple Precision Arithmetic Library. Fvee Sofmave Foundation, 2001 2.9 Implementación Interna 61 a la referencias [35] y [33], Tipo Booleano: bool-t Este es el único tipo de datos estructurado que no depende de la libreria GMP. Puesto que posee siempre el ancho de un bit, i.e., verdadero (nivel lógico 1) o falso (valor lógico 0). Internamente contiene un tipo de datos de C++ bool. Tipo Entero Con Signo: int-t Este tipo de datos estructurado es un entero sin signo con la posibilidad de definir su ancho en bits. Cuando se declara un elemento de esta clase, el usuario ha de especificar el ancho y modo de operación de sus bits. Esto es, el ancho de palabra y si trabaja en modo BEM o LEM. Este tipo de datos estructurado está compuesto por 3 elementos mpz-t de la libreria GMP. Uno de ellos se emplea para mantener el valor del dato, y los otros dos contienen los valores máximo y mínimo permitidos para la variable, es decir, E~~~~ c~~s~~~~ su rango. Tipo Entero Sin Signo: uint-t Este tipo es un entero sin signo donde el usuario puede definir su ancho de palabra. Es idéntico al tipo int-t salvo la particularidad que este no contiene el bit de signo. El resto de información es idéntica. Entem Sin Sigm O Bus Tipo Real: float-t Este tipo de dato estructurado almacena un número real. Se basa en un mpf-t y dos int-t, uno para lamantisa y el otro para el exponente. Los anchos de palabra de la mantisa y del exponente son definibles por el usuario. Como en el caso del tipo Punto int-t, el usuario debe especificar el ancho de palabra y su modo de funcionamiento a nivel bajo (LEM o BEM) si desea modificar los valores por defecto. El ancho de la mantisa y del exponente se pueden definir por separado. Tipo Imaginario: complex-t Este tipo de datos estructurado está compuesto por dos float-t. Uno de ellos para representar la parte imaginaria, y el otro para representar la parte real de un número complejo. La representación del número admite ser tratado ya no sólo en representación cartesianazZ, sino que soporta notación polar23. Al igual que en el resto de tipos, se puede definir tanto el ancho de cada número como el modo de funcionamiento. "Sea X + Yi un número imaginario, se dice que su representación es cartesiana pues se puede expresar como una coordenada (X, Y) dondeX se corresponde con la abscisa del vector imaginario e Y la ordenada del mismo. Z3Número imaginario expresado como módulo y radio. [35] J. Sosa, H. Navarro, MV Shahdadpuri, J.A. Montiel-Nelson, and R. Sarmiento. A ChipLevel Verification Methodology for Next-Generation Switch Fabric. In XW Confevence on Design of Civcuits and Integvated Systems, November 2002. [33] J. Sosa, J. A. Montiel-Nelson, H. Navarro, M. V Shahdadpuri, and R. Sarmiento. SystemLevel Verification Methodology for Advanced Switch Fabrics. In Pvoc. of SPIE of VLSI Civcuits andsystems, May 2003. 68 Entorno de Verificación Capitulo 3 Generación de Vectores de Máxima Cobertura Índice General 3.1. Introducción .......................... 71 3.2. Definiciones de Teoría de Grafos ............... 75 3.3. Cobertura Basada en Rutas (CBR) .............. 76 3.3.1. Modelo de Propagación de Puerta ........... 82 Puerta AND ....................... 82 Puerta OR ........................ 84 Puerta INV ....................... 85 3.3.2. Función Inversa del Modelo de Puerta ......... 85 3.3.3. Obtención del Patrón de Entrada para una Ruta .... 87 3.3.4. Cálculo de la Cobertura para un Conjunto de Rutas . . 90 3.3.5. Búsqueda con Algoritmos Genéticos .......... 91 Función de Coste .................... 91 Codificación del Individuo Genético .......... 91 Exploración de la Cobertura .............. 91 Resultados Experimentales ............... 93 Conclusiones ...................... 95 3.3.6. Satisfabilidad de la Propagación de Rutas ....... 97 3.3.7. Modelo de propagación ................. 97 Descripción del Circuito con MILP .......... 98 Optimización mediante MILP ........ 100 Resultados Experimentales ......... 101 Mejora del Tiempo de Computación ...... 105 Conclusiones ...................... 106 3.4. Cobertura Basada en Potencia de Consumo ......... 107 3.4.1. Modelo de Potencia de Consumo CMOS ....... 109 3.4.2. Función de Coste y Codificación ............ 109 3.4.3. Resultados Experimentales ............... 116 Generación de Vectores de Máxima Cobertura 3.4.4. Conclusiones . . . . . . . . . . . . . . . . . . . . . . 118 Glosario de Términos AND ATPG BDD CBR cond(vi) fanin(vi) fanmt(vi) .; G GLPK z z IW MILP NAND NOR pat h, patterns(cond(v,)) PC(~ath~,,~~ ) ~atterns(path~.,~~ ) PI PO PROLOG Funcibn lbgica Y. Advanced Test Pattem Generation. Binaiy Decision Diagram. Cobertura Basada en Rutas. Condicibn de propagacibn de la puerta vi Puertas conectadas como fuentes de señal a la puerta vi Puertas conectadas como carga a la puerta vi. Arco que modela la conexibn j entre dos puertas lbgicas. Circuito combinacional expresado como grafo. GNU Linear Programming Kit. Conjunto de pares ordenados de v&rtices. Lado dirigido. Funcibn lbgica NO. Mixed Integer Linear Programming. Funcibn lbgica NO-Y. Funcibn lbgica NO-O. Arcos de la puerta v salvo el arco 1. Funcibn lbgica O. Ruta ¡-&sima. Patrones de entrada que cumplen las condiciones del nodo vi Condiciones de la ruta path,,,,J Patrones que permiten ejercitar la ruta path,,,,J Entradas primarias del circuito. Salidas primarias del circuito. Programation et Logique, lenguaje de programacibn lbgica. Conjunto de rutas a verificar. Rutas Ejecutadas. Retardo de vbrtice v. Conjunto de vértices. Vbrtices de la ruta ¡-&sima. En el capítulo anterior se presentó en detalle la infraestructura del entorno de verificación propuesto en esta Tesis Doctoral desde un punto de vista puramente descriptivo. Este capítulo centra su atención en la generación de vectores de entrada para la verificación. Se explica su importancia y la de las métricas de cobertura dentro del área de la verificación funcional. La generación de patrones de verificación se plantea desde un punto de vista objetivo, mediante el uso de varias métricas de cobertura. Se propone el empleo de la métrica de Cobertura Basada en Rutas. La metodología propuesta para la generación de vectores de máxima cobertura con esta métrica emplea un modelo de puerta y circuital novel, que es también presentado en este capítulo. La implementación de la metodología de generación de vectores de máxima cobertura se realiza con ayuda de algoritmos de búsqueda tanto heurísticos como deterministas. La solución heurística se solventa mediante una implementación basada en Algoritmos Genéticos y la solución determinista se ha desarrollado empleado Programación Lineal Mixta Entera. También se propone una metodología eficiente para la generación de vectores con una métrica de cobertura basada en consumo de potencia. En este caso, la implementación de la metodología se lleva a cabo mediante una solución desarrollada con Algoritmos Genéticos. Ambas metodologías de generación de vectores de máxima cobertura se prueban extensamente con el conjunto de circuitos MCNC'91 multinivel y dos niveles. Los resultados de las diversas comparativas demuestran que las soluciones adoptadas obtienen vectores de máxima cobertura de una forma eficiente - en términos 3.1 Introducción de tiempo de CPU - lo cual redunda en el objeto de esta Tesis Doctoral, es decir, reducir el tiempo de verificación. El capítulo está organizado como sigue. En el apartado 3.1 se introduce la generación de vectores de máxima cobertura y su impacto en la etapa de verificación de cualquier sistema integrado. En segundo lugar, en el apartado 3.2 se presentan aspectos básicos de teoría de grafos como el concepto de vértice, camino y ruta, entre otros, necesarios para abordar adecuadamente la generación de vectores. Se continúa en el apartado 3.3 con la presentación formal de Cobertura Basada en Rutas. En los siguientes apartados se describe el modelo funcional directo e inverso de puerta, la obtención del patrón de entrada y un ejemplo de utilización del modelo para construir un patrón de verificación. A continuación, en el apartado 3.3.5 se describe la implementación heurística con Algoritmos Genéticos; su función de coste, codificación, experimentos y conclusiones. En el apartado 3.3.7 se expone la metodología propuesta e implementada con Programación Lineal Mixta Entera, el modelo lineal de puerta, el problema de optimización, los experimentos y las conclusiones vistos los resultados. En el apartado 3.4 se presenta la Cobertura Basada en Potencia de Consumo. Y a continuación el modelo de potencia empleado, así como su codificación y optimización con Algoritmos Genéticos en detalle. El capítulo finaliza exponiendo las conclusiones de la metodología propuesta para la obtención de vectores de máxima cobertura. 3.1. Introducción El principal objetivo de la verificación funcional es comprobar la conformidad de un diseño con respecto a su especificación [18]. Una de las claves importantes en la verificación es la métrica de cobertura [24]. Las métricas de cobertura intentan cuantificar, objetivamente, el grado de confianza1 alcanzado en un proceso de verificación. En otras palabras, enumerado el conjunto de funcionalidades a verificar y sus correspondientes estímulos de entrada, a medida que se comprueba cada una de esas funcionalidades, o parte de ellas, la métrica de cobertura cuantifica el número de funcionalidades comprobadas frente al número total de funcionalidades a comprobar. A pesar de que la métrica de cobertura se define para tener una medida objetiva sobre el proceso de verificación, la percepción del grado de confianza, sobre la verificación de un sistema, es totalmente subjetivo y dependiente, en la mayoría de los casos, de factores externos al flujo de diseño. En general estos factores externos son el time-temarket y la inclusión de funcionalidades o características avanzadas en diseños actuales para futuras versiones. Puesto que el time-temarket acota el plazo máximo de entrega, también restringe el periodo de verificación de cualquier desarrollo. Esto implica que para 'El grado de confianza expresa la probabilidad de que un evento se produzca. Aplicado a la Verificación, indica la probabilidad de que el circuito no posea un fallo. [18] Dhananjay S. Brahme, StevenCox, Jim Gallo, Mark Glasser, William Grudmann, C. Norris Ip, William Paulsen, John L. Pierce, John Rose, Dean Shea, and Karl Whiting. Creating a C++ Library for Test Bench Authoring. Technical Report CDNL-TR-2000-0820, Cadence Berkeley Labs, August 2000. [24] Hong Peng and Sofiene Tahar. Verification and Validation of Complex Digital Designs - A Practica1 Perspective. IEEE VTS Tutonal, June 2001 72 Generación de Vectores de Máxima Cobertura cumplir en tiempo y forma, se ha de ajustar el conjunto de funcionalidades a comprobar al tiempo definido para desarrollar el producto En ese caso, la métrica de cobertura se definiría como el conjunto de funcionalidades comprobadas sobre el total de funciones verificables durante el time-t+ I@uencia de la market. Es evidentemente, que la cuantificación de las funcionalidades comproMétrica de Cobe*ura badas es objetiva y permite estimar el grado de ejecución de las tareas de verificación. Sin embargo, un parámetro como el time-t+market, condiciona la medida de la cobertura. Dos procesos de verificación realizados sobre un mismo diseño, pero con distinto time-t+market poseen distinto grado de confianza. Y por tanto, ambos procesos de verificación no son comparables, a pesar de emplear la misma métrica de cobertura. Una práctica muy extendida es la de desarrollar productos muy complejos, que son introducidos en el mercado cuando aún se encuentran en una fase temprana de verificación. Ello implica que no toda la funcionalidad del mismo ha sido comprobada. Lo que supone que las primeras revisiones del producto puesto en el mercado poseen una funcionalidad muy restringida, para el usuario final de Funcionalidad ese producto inicial, con respecto al objetivo marcado para la versión definitiva Restringida del mismo. Esto es, la inclusión de funcionalidades ocultas o avanzadas es otro factor que distorsiona la objetividad de la métrica de cobertura. La inclusión de dichas funcionalidades dentro del proceso de verificación modifica el conjunto de requisitos a comprobar, y por ende distorsiona la métrica de cobertura. Por otro lado, parece evidente que no existe una métrica genérica que se le pueda aplicar a todos los diseños. Por ello, y con el objetivo de alcanzar un grado de confianza determinado para un conjunto particular de estímulos de entrada se han propuesto múltiples métricas [45], [13], [46], [l] y [24]. La mayoría de las métricas de cobertura propuestas hasta el momento han sido planteadas desde el punto de vista puramente algorítmico. En general, partiendo de las técnicas existentes en la verificación de software, mediante pequeños refinamientos, estas han sido adaptadas al diseño electrónico. A nivel de puerta, la generación de estímulos se centra en obtener un conjunto de vectores de entrada empleando diagramas de decisión binaria (BDDs) [47], modelos de fallos [48], satisfabilidad [49] y generación automática de patrones de test (ATPG) [50]. Tracy Larrabee. Test Pattem Generation using Boolean Satisfiability. IEEE tvans. on Computev-Aided Design oflntegvated Civcuits and Systems, 1 l(1) :4-15, January 1992. John R. Wallack and Ramaswami Dandapani. Coverage Metrics for Functional Test. Pvoc. of the 12th IEEE VLSI Test Symposium, pages 176-181,1994. M. Kantrowitz and Lisa M. Noack. I'm Done Simulating; Now What? Verification Coverage Analysis and Correctness Checking of the DECchip 21 164 Alpha Microprocessor. Pvoc. ofDesign Automation Confevence, pages 325-330, June 1996. Sedar Tasiran and Kurt Keutzer. Coverage Metrics for Functional Validation of Hardware Designs. IEEE Design and Test of Computevs, 18(4):36-45, August 2001 Hong Peng and Sofiene Tahar. Verification and Validation of ComplexDigital Designs - A Practica1 Perspective. IEEE VTS Tutonal, June 2001 Randa1 E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE tvansaction on Computevs, C-35(8):677-691, August 1986. M. Abramovici, M. Breumer, and A. Friedman. Digital Systems Testing and Testable Design. Wiley-IEEE Press, January 1993. E. Goldberg and Y. Novikov. Berkibhn: a Fast and Robust Sat-Solver. Pvoc of Design, Automation and Test in Euvope, pages 149-149, March 2002. Tom Kirkland and M. Ray Mercer. Algorithms for Automatic Test Pattem Generation. IEEE Design and Test of Computevs, June 1988. 3.1 Introducción 73 Los BDDs permiten representar un circuito combinacional de forma óptima [47] - en términos de memoria y tiempo de computación. De hecho, la representación interna de la mayoría del software desarrollado en la actualidad emplea ~'"casde Cobertum BDDs, para describir la funcionalidades de cada uno de los nodos que componen el grafo que representa a la red de lógica combinacional en estudio [51], [52], [S31 Y Los modelos de fallos permiten realizar una cuantificación de la medida en la verificación. Contabilizar el número de fallos que se pueden descubrir con un determinado vector de entrada, permite definir una cualidad numérica del vector, relativa a la capacidad de detectar errores - asignación objetiva de una propiedad a una magnitud o valor. Puesto que dicha cualidad numérica es objetiva por naturaleza, esta puede ser empleada como métrica de cobertura. La satisfabilidad es un problema matemático, ampliamente estudiado [54]- [57], que plantea la búsqueda del conjunto de valores de entrada a una expresión Booleana que hacen que esta sea verdadera. Matemáticamente, y dentro del campo de los números reales, dicho problema está resuelto mediante diversos métodos como Programación Lineal [56], Programación Cuadrática [58], Algoritmos Genéticos [59], entre otros. La Programación Lineal es el método más empleado, pues garantiza la solución determinista al problema planteado en tiempo lineal con el número de variables que definen el problema a resolver. Como caso particular de la Programación Lineal, se define la Programación Lineal Mixta Entera S. Yang. Logic Synthesis and Optimization Benchmavks Usev Guide vevsion 3. O. Microelectronics Center of North Carolina, 1991 E.M. Sentovich, K.J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P.R. Stephan, Robert K. Brayton, and Alberto L. Sangiovann-Vincentelli. SIS: A System for Sequential Circuit Synthesis. Technical Report UCBERL M92141, EECS Department, University of Califomia, Berkeley, 1992. R. K. Brayton, G. D. Hachtel, A. Sangiovann-Vincentelli, F. Somenzi, A. Aziz, S. T. Cheng, S. Edwards, S. Khatri, Y. Kukimoto, A. Pardo, S. Qadeer, R. K. Ranjan, S. Samary, T. R. Shiple, G. Swamy, and T. Villa. WS: a System for Verification and Synthesis. In Rajeev Alur and Thomas A. Henzinger, editors, Pvoceedings of the Eighth Intemational Confevence on ComputevAided Venfication CAV, volume 1102, pages 428-432, New Brunswick, NJ, USA, 1996. Springer Verlag. Synopsys Inc. Synopsys UsevManual, VI O edition. Dingzhu Zu, Hun Gu, and Panos M. Pardalos. Sati$ability Pvoblem: Tkeoiy andApplications. American Mathematical Society, 1997. F. Fallah, S. Devadas, andK Keutzer. Functional Vector Generation for HDL Models using Linear Programming and 3-Satisfiability. Pvoc. on Design Automation Confevence, June 1998. Zeng Zhihong, P. Kalla, and M. Ciesielski. LPSAT: A Unified Approach to RTL Satisfiability. Pvoc. on Design, Automation and Test in Euvope, pages 398-402, March 2001 J. A. Montiel-Nelson, H. Navarro, J. Sosa, and José C. García. Theory and Applications of Satisfiability Testing. InEvolutionavy andDeteministicMethodr foflesign, Optimization and Contvol with Applications to Industrial and Societal Pvoblems, November 2005. Srimat T. Chakradhar, Vishwani D. Agrawal, and Michael L. Bushnell. Automatic Test Generation using Quadratic 0-1 Programming. In Pvoceedings of the 27th ACMLEEE confevence onDesign automation, pages 654-659, New York, NY, USA, 1990. ACM Press. André; Baresel, David Binkley, Mark Harman, and Bogdan Korel. Evolutionary Testing in the Presence of Loop-assigned Flags: A Testability Transfonnation Approach. In ISSTA '04: Pvoceedings of the 2004 ACM SIGSOFTIntemational Symposium on Sofmave Testing andAnalysis, pages 108-1 18, New York, NY, USA, 2004. ACMPress. 74 Generación de Vectores de Máxima Cobertura (MILP2), donde las variables de dicho problema se restringen a valores enteros en vez de reales. Este último problema aún continúa siendo un campo de investigación incipiente, pues no se ha encontrado un algoritmo o metodología que garantice una solución en un tiempo razonable En el campo de la verificación de circuitos, se plantea el problema de encontrar el vector de entrada que permite asegurar un conjunto de condiciones, con el objeto de verificar algún requisito específico. Este problema se puede plantear en términos de Programación Lineal Mixta Entera, donde las variables del problePmblema de ma se restringen a valores Booleanos (uno y cero), para el caso de los circuitos Satisfabilidad combinacionales3. El empleo, de una o más de una, de las técnicas descritas en los párrafos anteriores para la generación de una secuencia de vectores requiere de una estrategia que guíe la generación de estímulos, con el fin de alcanzar el grado de confianza especificado. Las técnicas definidas como ATPG4, a pesar ser ideadas inicialmente para la generación de vectores de testi, y vista su similitud con la generación de vectores para la verificación, son aplicadas igualmente a las diversas etapas de verificación, con el fin de optimizar la generación de vectores y dotar de cierta inteligencia al sistema de verificación [55], [56] y [59]. Día a día, los diseños aumentan su complejidad debido a que se incluyen más y nuevas funcionalidades. Aumentar el número de funcionalidades implica incrementar el tiempo necesario para comprobar la integridad de las especificaciones en el diseño. Además, y debido a la creciente complejidad de las nuevas funcionalidades requeridas, se toma muy complicado el empleo de una única métrica de cobertura para todo el circuito. Por todo ello, es necesario plantear el dominio de definición de la métrica empleada, atendiendo exclusivamente a su utilidad y Simultmeidad de ámbito de aplicación. Ya no sólo es necesario aplicar una única métrica, sino que Métricar se hace imprescindible emplear más de una métrica con el fin de cubrir todos los aspectos relevantes de la verificación, y así cuantificar de forma adecuada el proceso de verificación. En otras palabras, si se desea cubrir ciertos aspectos singulares, pero fundamentales, durante el proceso de verificación, es necesario plantear métricas específicas que contabilicen esos aspectos particulares simultáneamente a las cuantificaciones globales de la verificación realizada. En particular, como métrica de cobertura para la verificación, la métrica de cobertura basada en rutas indica cuál es el grado de ejercitación del conjunto de 'Acrónimo del término inglés Mxed Integer Lineal Programming, traducido al castellano como ProzramaciónLineal Mixta Entera. 3Todo circuito combinacional puede ser visto como una red Booleana donde el ancho de palabra es el bit y no el ancho de palabra definido en alto nivel. 4Acrónimo anglosajón Advanced Test Pattern Generation, traducido como Generación Avanzada de Patrones de Test. 'Se define el test como al proceso de comprobación de defectos físicos en la fabricación de Circuitos Integrados. F. Fallah, S. Devadas, and K. Keutzer. Functional Vector Generation for HDL Models using Linear Programming and 3-Satisfiability Pvoc. on Design Automation Confevence, June 1998. Zeng Zhhong, P. Kalla, and M. Ciesielski. LPSAT: A Unified Approach to RTL Satisfiability. Pvoc. on Design, Automation and Test in Euvope, pages 398-402, March 2001 André; Baresel, David Bmkley, Mark Harman, and Bogdan Korel. Evolutionary Testing in the Presence of Loop-assigned Flags: A Testability Transformation Approach. In ISSTA '04: Pvoceedings of the 2004 ACMSIGSOFTIntemational Symposium on Softwave Testing andAnalysis, pages 108-1 18, New York, NY, USA, 2004. ACM Press. 3.2 Definiciones de Teoría de Grafos rutas a verificar [13] y [60]. Se entiende como ejercitación, a la propagación de una transición alto-bajo o bajo-alto a través de las puertas que componen la ruta ejercitada. Si se aplica verificación basada en simulación, el grado de confianza alcanzado con esta métrica de cobertura es mayor cuantos más vectores se ejecuten o introduzcan en el sistema bajo verificación. Por ello, siempre es deseable obtener el conjunto mínimo de vectores que permiten maximizar la cobertura en la verificación de una funcionalidad. Antes de proseguir, en el próximo apartado, se introducirán los conceptos necesarios de teoría de grafos para poder abordar, adecuadamente, el problema de generación de vectores de máxima cobertura empleando la métrica CBR. 3.2. Definiciones de Teoría de Grafos Un circuito de lógica combinacional es una red Booleana representada por un multigrafo, finito, conectado mediante arcos dirigidos, y con un costo definido en sus arcos 2 = G(V, E,T), tal y como se describe en [61]. V es un conjunto de vértices y E es un conjunto de pares ordenados de vértices distintos, llamados arcos dirigidos6. Un arco dirigido Z = (u, v) incide en u y v, los vértices son la cabeza y la cola de Z, respectivamente; Zes un arco de entrada de v y un arco de salida de u. + La existencia de un arco dirigido Z = (u, v) t G implica que el nodo u es una entrada inmediata del nodo v, o el nodo v es una salida inmediata del nodo u, tal y como es presentado en [62]. El conjunto de todas las entradas inmediatas de v se denota por f anin(v), y al conjunto compuesto por todas las salidas inmediatas de u se denomina fanout(u). En [63] se presentauna definición para el término multigrafo con costo asociado a sus arcos, aplicado al modelado de dispositivos computacionales. Los vértices del grafo o nodos modelan las puertas lógicas. Cada vértice v posee un costo de retardo no negativo, esto es T(V) = T~. Los arcos dirigidos E del gafo modelan las interconexiones entre puertas lógicas. + Un camino7 de G es una secuencia de vértices vi y arcos ej, que se expresa eo el como vo i vl i . . . e=' vk, tal que, ei conecta los vértices vi y vitl. Un tour es un camino donde todos los arcos son distintos. Una ruta es un camino con distintos 6Traducción directa del término anglosajón divected edges 'Traducción del término anglosajón walk. John R. Wallack and Ramaswami Dandapani. Coverage Metrics for Functional Test. Pvoc. of the 12th IEEE VLSI Test Symposium, pages 176-1 81, 1994. J. Sosa, J. A. Montiel-Nelson, H. Navarro, and José C. García. Functional Vector Generation for Maximum Data Path Coverage using Mixed Integer Linear Programming. InXVIII Confevence on Design of Civcuits andIntegvatedSystems, November 2005. K.S. Lowe andPG Gulak. A Joint Gate Sizing andBuffer InsertionMethod of Optimizing Delay and Power in CMOS and BiCMOS Combinational Logic. IEEE Tmns. Comput.- AidedDes. Integi: Civcuits Syst, 17(5):419-434, 1998. C. Chen, A. Srivastava, and M. Sarrafzadeh. On Gate Leve1 Power Optimization using Dual-Supply Voltages. IEEE Tmns. Comput.-AidedDes. Integi: Civcuits Syst, 9(5):616629,2001 P.Y. Calland, A. Mignotte, O. Peyran, Y. Robert, and F. Vivien. Retiming DAG's. IEEE Tmns. Comput-AidedDes. Integi: Civcuits Syst., 17(12): 13 19-1 324, 1998. 76 Generación de Vectores de Máxima Cobertura vértices [64]. Así, una ruta que conecta los nodos vo y vi, se define en [63] y [65] como RU~~ path = vo 2 vl -> . . . '2 vi,; donde la cola de la ruta t(path ,,,,,) es vo, el primer arco de la cola Zo; La cabeza de la ruta h(path,,,,,) es vi,, el último arco de la cabeza y v(path ,,,,,) es {vo, vl, . . . , vi,), el conjunto de vértices. Por otra parte, este trabajo centra su interés en aquellas rutas donde la cola de la ruta vo y su cabeza vi, son entrada y salida primaria al circuito respectivamente. El conjunto vértices entradas y salidas primarias de 2 es Pl(2) y PO(^), respectivamente. 3.3. Cobertura Basada en Rutas (CBR) En todo momento, dentro del proceso de verificación, cuantificar la calidad de los patrones de entrada y, por tanto, la cobertura lograda con ellos, es un objetivo primordial a alcanzar. Una medida de la calidad de vectores empleados en la verificación funcional es la Cobertura Basada en Rutas (CBR) [13]. La CBR puede ser definida formalmente como: RE CBR = - RV' donde RE representa el número de Rutas Ejercitadas y RV el número de Rutas Verificables. Esta métrica se basa en el estudio de la ejercitación de las diversas rutas que conforman un circuito de lógica combinacional a verificar. En este contexto, verificar o ejercitar una ruta consiste en estimular el circuito de lógica combinacional, de forma que, permita la propagación de una transición desde una entrada, hasta una salida, a través de las puertas lógicas e interconexionado que componen la ruta ejercitada. Sea una ruta p~th,,,~~, a ser ejercitada. Cada una de las puertas lógicas que la componen ~(path,,,,~) tienen que permitir la propagación de una transición desde ~uta Ejercitable la entrada primaria vi hasta la salida primaria vj. Por lo tanto, el resto de entradas de cada puerta lógica que pertenecen al p~th,,,,~ han de poseer los valores lógicos que permita dicha propagación. Deñnición 1 (Ruta ejercitable). Sea 2 el grafo de un circuito combinacional y path,,, una de sus rutas. Esta ruta path,, es ejercitable si existe un vector de entrada a 2 que permite propagar una transición desde la entrada primaria u a la salida primaria v a través de cada uno de los vértices de la ruta path,,,. Deñnición 2 (Condiciones de propagación de una puerta). Sea vi, un vértice de la ruta ejercitable path,h,vl. Las condiciones de propagación cond(vk, path,,,,,) del vértice vi, para la ruta path,,,,, son el conjunto posible de valores lógicos que ha de poseer cada uno de los vértices de entrada vi vi t f anin(vk) & [64] N. Sherwani. Algonthms fov VLSI Physical Design Automation. Kluwer Academic Publishers, Boston, 1993. [63] P.Y. Calland, A. Mignotte, O. Peyran, Y. Robert, and F. Vivien. Retiming DAG's. IEEE Tmns. Comput.-AidedDes. Integi: Civcuits Syst, 17(12):1319-1324, 1998. [65] C.E. Leiserson and J.B. Saxe. Retiming Synchronous Circuitry. Algonthmica, 6-38, 1991. [13] John R. Wallack and Ramaswami Dandapani. Coverage Metrics for Functional Test. Pvoc. of the 12th IEEE VLSI Test Symposium, pages 176-181,1994. 3.3 Cobertura Basada en Rutas (CBR) 77 vi ~(path,,,,,), tal quepermitenpropagar una transición a fanout(vk), desde el vértice de entrada vj vj t fanin(vk) & vj t ~(path,,,,,). El conjunto de condiciones que imponen cada uno de los vértices de una ruta se agrupa en las llamadas condiciones de contorno, o condiciones de propagación de transiciones de la ruta PC(path = {cond(~~+~,path ), ..., Condiciones de Contorno cond(~~-~,path,,,,,)). Si no es posible satisfacer cada una de esas premisa individuales, entonces, esa ruta no puede ser ejercitada. Sea el circuito de lógica combinacional que se presenta en la figura 3.l(a), la figura 3.l(b) muestra su gafo 2. Para abordar de forma didáctica el ejemplo, que a continuación se va a plantear, es necesario enumerar todas y cada una de las rutas existentes entre las entradas primarias y salidas primarias del circuito de la figura 3.l(a). La tabla 3.1 resume todas las rutas posibles del circuito. La primera columna muestra la etiqueta de cada ruta. La segunda columna presenta la entrada primaria, puertas y salida primaria que componen la ruta a verificar. La tercera columna presenta la ruta a través del gafo. Y, la última columna presenta las condiciones de contorno necesarias para verificar la ruta en estudio. Según la métrica de cobertura de rutas, para alcanzar la totalidad del nivel de confianza es necesario ejercitar cada una de las rutas enumeradas en la tabla 3.1. Tabla 3.1: RUTAS Y CONDICIONES PARA LA COBERTURA BASADA EN RUTAS DEL CIRCUITO DEL EJEMPLO Del circuito representado en la figura 3.l(a) con ayuda de la tabla 3.1 se puede deducir fácilmente que, por ejemplo, para verificar la ruta etiquetada como path4, se debe asegurar que en los arcos el y eg ha de existir un cero lógico. De otra forma, este path4 no puede ser ejercitado. La figura 3.l(c) muestra la ejercitación de la ruta y las condiciones sobre la red Booleana para este caso. Prosiguiendo con el ejemplo anterior, asegurar que el arco el posea un cero lógico (0) implica que la entrada primaria vl también se encuentre a nivel lógico cero. Y por ende, el vector de entrada que permite verificar la ruta path4 ha de poseer el bit que representa al terminal de entrada vl con un cero lógico. Sin embargo, para el caso del arco eg, la necesidad de imponer un cero lógico se puede satisfacer de formas diversas. Ello implica que las condiciones de contorno particulares de cada puerta, que va a permitir la propagación de una transición, Generación de Vectores de Máxima Cobertura posee algún tipo de fallo fisico, por ejemplo del estilo stuck-a? [48]. Para ello, se determina el conjunto de nodos a observar y el vector estático de entrada que permite realizar la observación. Cada vector de entrada permite comprobar si existe un error del tipo stuck-at zero o no, sobre un conjunto de arcos determinados. Para verificar si existe un stuck-at one, localizado en el mismo emplazamiento que el stuck-at zero comprobado anteriormente, es necesario introducir otro vector de entrada. Si existe un error, el patrón de salida que presenta la red, difiere del valor estimado si y sólo si el error es observable. Además un único vector de entrada permite descubrir más de un error, demostrándose que una vez descubierto el error, su localización no es sencilla. Por el contrario, la verificación basada en rutas intenta identificar un fallo funcional. La medida de la cobertura permite cuantificar que partes del circuito se han ejercitado y, por tanto, que funcionalidades no han sido verificadas. La relación entre las rutas ejercitadas y las funcionalidades que implementan es directa, así que una vez se determine que una ruta viola las especificaciones de su funcionamiento, la tarea de localización de la funcionalidad que contiene el fallo es inmediata y directa. Puerta OR Figura 3.4: Modelo básico de la puerta OR para la propagación de transición Sea una puerta lógica OR de dos entradas A y B como la mostrada en la figura 3.4(a). El modelo de puerta OR desarrollado en esta Tesis Doctoral es a su vez presentado en la figura 3.4(b). La presencia de una transición en alguna de las entradas ha de ser acompañada de la presencia de un cero lógico en la otra entrada, para que la puerta OR proModelo de pague la transición a su salida. Por el contrario, si existe una transición en una Puerta OR entrada y la otra entrada posee un uno lógico, la puerta OR en su salida fija un uno lógico. Como se puede observar, el modelo de la puerta OR se comporta como el modelo de puerta AND, al no permitir la propagación de transiciones desde más 'En la bibliografía se define un stuck-at como un fallo - del tipo corto circuito o circuito abierto donde la señal permanece constante a un valor lógico verdadero o falso. [48] M. Abramovici, M. Breumer, and A. Friedman. Digital Systems Testing and Testable Design. Wiley-IEEE Press, January 1993. 3.3 Cobertura Basada en Rutas (CBR) 85 de una de sus entradas al mismo tiempo. Para el resto de condiciones de entrada, el modelo de puerta para la OR funciona como una puerta lógica OR convencional. Puerta INV Figura 3.5: Modelo básico de la puerta INV para la propagación de transición El nuevo modelo de puerta de un INV es presentado en la figura 3.5(b). Debido a que la puerta INV sólo posee un terminal de entrada, este siempre propaga la transición. De otra forma, la inversión de la entrada es modelada en su única salida. Finalmente, el modelo de puerta del INV nunca produce un error. 3.3.2. Función Inversa del Modelo de Puerta Seleccionado una ruta a verificar, se ha de garantizar el conjunto de condiciones que permiten propagar una transición a través de dicha ruta. Realizar la búsqueda de un patrón de entrada que permita ejercitarlo, se traduce sin complicación alguna, a un problema de satisfabilidad. Reducir el problema de satisfabilidad es siempre un objetivo deseado. La obtención de la función inversa de cada puerta, y en su defecto la función inversa condicionada a ciertos valores de entrada, permite extender las condiciones impuestas por las puertas de la ruta a verificar. Extender dichas condiciones permite reducir el problema de satisfabilidad y, en ciertos casos, permite identificar la incompatibilidad de condiciones y, por tanto, entre rutas mediante la mera expansión de estas condiciones, sin ni si quiera formular el problema de satisfabilidad. Por ejemplo, sea el circuito de la figura 3.6(a), cuyo grafo representa la figura 3.6(b). Se desea comprobar si se puede ejercitar simultáneamente la pareja de rutas etiquetadas como path7 y path16. Al igual que con los ejemplos descritos en los apartados anteriores, ahora se puede recapitular que: "para ejercitar la ruta path7 es necesario asegurar que los arcos e2 y eg posean un cero lógico". A su vez, de entre las condiciones necesarias para ejercitar la rutapath16 se plantea la necesidad de asegurar un cero lógico en el arco e16. Del proceso de anotación de las condiciones necesarias para asegurar ambas rutas no ha aparecido ningún tipo de incompatibilidad. Ello es debido a que no ha surgido contradicción alguna en el proceso seguido. Anotado el grafo, es necesario plantear un problema de satisfabilidad con el objeto de obtener un patrón de entrada que ejercite ambas rutas o en su defecto, una incompatibilidad entre las rutas path7 y path17. Sin embargo, mediante unas simples asociaciones derivadas de la estructura -. del grafo v las funcionalidades involucradas, es posible determinar que ambas ru- . A tas son incompatibles. Para el eiemplo de la figura 3.6(c) se puede decir que: "la " A ~, A condición de cero lógico sobre el arco e9 implica que la puerta v8 ha de poseer un Rufarlncompafibles 86 Generación de Vectores de Máxima Cobertura Figura 3.6: Ejemplo de la expansión de las condiciones de propagación: (a) esquema del subcircuito, @) grafo del subcircuito, y (c) expansión de la condición de propagación de la mta pathib y contradicción sobre la mta path~. 3.3 Cobertura Basada en Rutas (CBR) 87 cero lógico en su salida". Esto supone que el arco elo también posee un cero lógico. A su vez, del tratamiento de las condiciones de propagación de la rutapath16, y en particular, la condición de cero lógico sobre el arco e16, se observa que ésta condición puede ser extendida a través del inversor vll. Ese cero lógico presente en la salida del inversor tiene que ser debido a la presencia de un uno lógico en su entrada. Luego la condición de cero lógico sobre el arco e16 se expande sobre el arco elo con una condición de uno lógico. Ahí surge la contradicción entre las rutas path7 y path16. El arco eg ha de poseer un cero lógico para asegurar la ruta path7 y, a su vez, ese mismo arco ha de poseer un uno lógico para asegurar la ruta path16. Lo que implica que ambas rutas no pueden ser ejercitados simultáneamente. Realizar este sencillo estudio permite identificar incompatibilidades derivadas de las condiciones de propagación sin la necesidad de plantear el problema de satisfabilidad. Ello redunda en la reducción del tiempo necesario para determinar si dos o más rutas son incompatibles. Y por supuesto, una vez superada esta etapa de análisis, el problema de satisfabilidad queda reducido; pues en la mayoría de los casos, la red sobre la que se plantea el problema de satisfabilidad es menor que la original sin el preprocesado. La contraprestación a este preprocesado, es la necesidad de determinar las funciones inversas de cada una de las puertas lógicas empleadas. La función inversa del modelo de la puerta INV es sencilla e intuitiva. Esta función inversa se corresponde con la propia función directa del inversor. Para el resto de puertas lógicas combinacionales no existe función inversa directa. Esto es porque existe al menos una salida que puede ser obtenida mediante más de una combinación de entrada. El modelo de puerta presentado puede ser visto como una función matemática dependiente de varias variables de entrada. El conocimiento de un valor puntual de dicha función, no implica el conocimiento exacto de los valores de las variables que lo produjeron, salvo que estos valores se encuentren inducidos por otra condición o extensión de condición. Por ello, para conocer el valor de entrada de una de las variables, por lo general, se ha de conocer no sólo el valor de salida de la función, sino que se ha de conocer también, el valor del resto de las entradas. Igualmente, para determinar las condiciones de entrada que producen una condición a la salida en una puerta, es necesario conocer el valor que toman todas las cofld;c;oflesde Entmda entradas de la puerta, menos una. Salvo, que se de en las entradas un valor dominante, esto es, un valor de entrada en alguno de sus terminales que fije la salida de la puerta de forma independiente al resto de entradas. Este valor dominante también suele hacer de cerrojo. El valor cerrojo evita que se propague una transición desde alguna entrada a la salida. Por ejemplo el valor dominante o cerrojo de una puerta AND es el cero lógico. Si hay presente en al menos una entrada, un cero lógico, en la salida habrá presente un cero lógico, independientemente de lo que haya en el resto de entradas. El valor cerrojo de la puerta OR es el uno lógico. Si en una puerta lógica OR se fija alguna entrada a un uno lógico, la salida de la puerta se situará en un uno lógico independientemente de los valores presentes en el resto de entradas a la puerta. 3.3.3. Obtención del Patrón de Entrada para una Ruta En este punto se presentará, formalmente, el algoritmo que permite determinar si una ruta es o no ejercitable. En caso afirmativo, también, se definirá su patrón 88 Generación de Vectores de Máxima Cobertura de entrada. La figura 3.7 presenta el algoritmo verpattern() + given a 2 = (V, E, T) ; set PC(path,,,,,) to 0; for each v vertex t path path,,,v, to be verified get cond(v, path,,,v,), propagation constraints at v vertex; include cond(v, path(vo, vk) in PC(path,,,v,); end for; for each cond(v,path ,,,,,) t PC(path ,,,,,) propagate constraint satisfability to PI(~); propagate constraints to PO(¿$; end for; for each v vertex t path path,o,,k to be verified extend propagations to PO(@; end for; fix the unknow input logic values; end verpattern Figura 3.7: Algoritmo para la generación del patrón de entrada en la verificación de una mta. + + Este algoritmo, para un circuito de lógica combinacional G = (V, E, T), consiste en: Determinar las puertas lógicas que conforman la ruta a ejercitar, y fijar sus condiciones de contorno.- Dada una ruta a ejercitar, este paso localiza cada uno de los vértices y arcos que componen la ruta que ha de propagar la transición. Cada una de esas puertas posee unas condiciones de contorno. Este paso, también, anota dichas condiciones de contorno en el grafo que representa a la red de lógica combinacional. De esta anotación puede surgir alguna incompatibilidad, si ese es el caso, el algoritmo finaliza pues no es posible encontrar un patrón de entrada que asegure las dos condiciones contradictorias. Extender las condiciones de contorno.- Las condiciones de contorno de la ruta, anotadas en la fase anterior, han de ser extendidas en dirección a las entradas y, posteriormente, hacia las salidas. Para extender una condición de contorno hacia las entradas se hace necesaria la existencia de un vector de entrada univoco que permita satisfacer dicha condición. Como se apuntó en el apartado 3.3.2, una condición en una salida puede satisfacerse mediante múltiples vectores de entrada. En este paso, la condición será expandida hacia las entradas, si y sólo si, hay un conjunto de entradas que tienen definido su estado y existe un vector de entrada que cumple con esos valores y con la salida propuesta, de forma univoca. En esta fase, también, se extienden las condiciones en dirección a las salidas. La expansión de las condiciones se realiza de forma similar a la ex- 3.3 Cobertura Basada en Rutas (CBR) 89 puesta en el párrafo anterior. Es decir, no se condicionará la salida de una puerta, si la condición impuesta en la entrada no determina, unívocamente, dicha salida. Esto se hace así, para no restringir en exceso la red de lógica combinacional. Si en el transcurso de esta fase se encontrase una contradicción entre dos o más condiciones, significaría que la ruta a verificar no es ejercitable. En ese caso el algoritmo finalizaría, pues, no es posible satisfacer todas las condiciones de contorno de la ruta bajo verificación. Ruta no Vei$cable Propagar la transición de la ruta bajo verificación a los vértices no pertenecientes a dicha ruta, pero con arcos comunes a la ruta a verificar.- Propagar una transición a través de una ruta implica que otras puertas, también, se vean afectadas por esa transición. Esta propagación en dirección a las salidas, sólo se puede realizar en el caso de que ésta sea determinada por la funcionalidad de la puerta de forma unívoca. Si durante este proceso se diera una reconvergencia de la propagación, el algoritmo terminaría igualmente la búsqueda del patrón de entrada, pues la reconvergencia de transiciones no está permitida en la verificación basada en la métrica de cobertura de rutas. m Encontrar el patrón de entrada que cumpla con todos los anteriores.- . . . Alcanzada esta última fase, la red de puertas combinacional contiene anotaciones referentes a la ruta a verificar, las condiciones de contorno a cumplir, junto a sus expansiones y la propagación de las transiciones. Este paso busca el patrón de entrada que cumple con todas las anotaciones de la red Booleana. Además, atendiendo al estado de las entradas del circuito bajo verificación, se puede observar que existen terminales de entrada condicionados o fijos a un valor, hay un terminal que define el comienzo de una propagación y, por último, hay terminales con valor desconocido. El objetivo de esta última fase es descubrir el valor de los terminales que no poseen un valor conocido. Para ello se puede emplear un simulador lógico [66], [21], simbólico [67], [9] o establecer las condiciones de satisfabilidad [49], [68]. El empleo de uno u otro es indiferente. D. Becker, R.K. Singh, and S.G. Te11 An Engineering Environment for HardwareISoftware Co-Simulation. Design Automation Confevence, pages 129-134, June 1992. H. Navarro, Juan A. Montiel-Nelson, J. Sosa, and R. Sarmiento. DEMETER: A Novel Framework for Hardware and Software System Specification, Simulation and Verification in C++ XVI Confevence on Design of Civcuits andIntegvatedSystems, pages 20-23, November 2001 Randa1 E. Bryant. Symbolic Simulation Techniques and Applications. In Pvoceedings of the 27th ACMLEEE confevence on Design automation, pages 517-521, New York, NY, USA, 1990. ACM Press. H. Navarro, J. A. Montiel-Nelson, J. Sosa, and José C. García. A Symbolic Solverto Obtain the Entire Solution Space of the Boolean Satisfiability Problem using Genetic Algorithms. In Evolutionaiy andDetenninistic Methods fov Design, Optimization and Contvol with Applications to Industrial andSocieta1 Pvoblems, September 2005. E. Goldberg and Y. Novikov. BerkMin: a Fast and Robust Sat-Solver. Pvoc of Design, Automation and Test in Euvope, pages 149-149, March 2002. H. Navarro, J. A. Montiel-Nelson, J. Sosa, and José C. García. Solving the State Justification Problem using MILP for RTL Specifications. InXIX Confevence on Design of Civcuits andIntegvatedSystems, November 2004. 90 Generación de Vectores de Máxima Cobertura Finalizada la ejecución del algoritmo, éste puede ofrecer dos resultados posibles. El primero de ellos es el patrón de entrada que permite verificar la ruta deseada. El patrón resuelto poseerá valores definidos, la transición y10 valores indiferentes. El otro resultado posible es la no existencia de un patrón. 3.3.4. Cálculo de la Cobertura para un Conjunto de Rutas El algoritmo de obtención del patrón de máxima cobertura es mostrado en la figura 3.8. path-couerage() + given a G = (v, E, T); set pathSet to 0; add path,,, t 2 to pathSet patterns(path,,,) # 0; do + select path,, t G p~th,,~ pathSet; get the input pattern verpattern(pathSet U path,,,); if (pathSet U p~th,,~) is compatible then add path,,, to pathSet; end if; until Objective Function Criteria endpath-coverage Figura 3.8: Algoritmo para la generación de patrones de máxima cobertura. + + Dado un circuito de lógica combinacional G = (V, E, T) el algoritmo path _coverage busca un conjunto de rutas compatibles para maximizar la CBR. En primer lugar, el algoritmo inicializa el conjunto de rutas compatibles pathSet al conjunto vacío. A continuación, selecciona una ruta path,,, verificable - esto es, 3 patterns(path,,,) y lo añade al conjunto pathSet. Entonces, comienza un bucle que busca rutas compatibles entre sí. En cada iteración de este bucle se selecciona una ruta path,, del circuito 2, que no esté incluida en el subconjunto de rutas ya encontradas pathSet. En segundo lugar averigua si existe un patrón de entrada que verifica la ruta seleccionada y el conjunto compatible que ya se posee de iteraciones anteriores. Si resulta que la ruta seleccionada unión el conjunto pathSet se define compatible, incluye la ruta path,,, en el conjunto de rutas verificables pathSet. Tras la primera iteración el conjunto de rutas pathSet puede contener un par de rutas compatibles o sólo la ruta con la que se inició el bucle dependiendo de si el algoritmo escoge una ruta compatible o no con la previamente seleccionada. En las sucesivas iteraciones, el conjunto pathSet va albergando a las rutas compatibles encontradas. El algoritmo finaliza cuando se alcanza la función objetivo. 3.3 Cobertura Basada en Rutas (CBR) 3.3.5. Búsqueda con Algoritmos Genéticos Toda solución basada en Algoritmos Genéticos posee dos pilares claves. Uno de ellos es la codificación del problema, y el otro es la definición de una función objetivo. La codificación del problema consiste, de forma somera, en implementar un individuo de la población genética de tal forma que modele aquellas variables del problema que se ha de resolver. En la mayoría de los casos, la dificultad de implementar el individuo radica en identificar adecuadamente las variables del sistema a optimizar. La función de coste permite al núcleo de optimización genética guiar y seleccionar a los individuos y así estimar la bondad de la solución alcanzada. A continuación se procederá a presentar la función de coste, para posteriormente explicar la codificación del individuo. Función de Coste Si todas las rutas posibles de una red Booleana 2 están contenidas en el conjunto y, y el conjunto a contiene un subconjunto de y (a c y), donde a representa las rutas a verificar, la función de coste a minimizar se define como: GAcOst = path count(y) - path count(a) (3.9) Donde path count es una función que proporciona el número de elementos de un conjunto. Además, el modelo de propagación de transiciones propuesto en el apartado 3.3.1 no permite la verificación de más rutas, con un único patrón, que el número de salidas primarias disponibles (PO(@). Esta consideración limita el número de rutas incluidas en el subconjunto. Entonces, es más apropiada la función de coste: + GAcost = vertex count(PO(G)) - path count(a) (3.10) donde PO count es una función que proporciona el número de salidas primarias de una red Booleana. Codificación del Individuo Genético La función objetivo es obtener un patrón de entrada que maximice la cobertura de verificación del circuito. Esto es, encontrar el patrón que contenga el mayor número de rutas que puedan ser verificadas simultáneamente. El individuo de la población para la solución adoptada con Algoritmos Genéticos consiste en un arreglo de n números enteros. El individuo representa el subconjunto de rutas seleccionadas, y su longitud n coincide con el número de salidas primarias del circuito. El número entero contenido en cada elemento del individuo define el índice de la ruta que es seleccionada de todas las posibles rutas existentes. Exploración de la Cobertura La exploración de la cobertura del diseño empleando algoritmos genéticos es abordada mediante el algoritmo presentado en la figura 3.9. De forma iterativa, el algoritmo va obteniendo el patrón de máxima cobertura v eliminando las rutas Codificación que ya están cubiertas por dicho patrón de la lista de rutas posibles. Este proceso BÚsquedadelPafrón de Máama Cobe*ura Generación de Vectores de Máxima Cobertura de búsqueda y eliminación se realiza hasta que la lista de rutas posibles esté vacía o sólo se encuentren las rutas no verificables. Al finalizar el algoritmo, éste devolverá una lista con los patrones de máxima cobertura para la verificación. GApath-couerage() + given a G = (v, E, 7); do obtain maximum coverage pattern using GA; + remove path of maximum coverage from G; while size(G) > 0 end GApath-coverage Figura 3.9: Algoritmo de generación de patrones de máxima cobertura empleando Algoritmos Genéticos. Dado un individuo, se comprueba la primera ruta seleccionada. Si se determina que existe un vector de entrada que permite verificarlo, se procede a comprobar la segunda ruta especificada. Si la ruta seleccionada no es compatible, la comprobación del subconjunto de rutas especificadas finaliza. El coste del subconjunto evaluado es estimado mediante la ecuación 3.10, sobre las rutas que se han evaluado positivamente en los pasos previos para el individuo en estudio. Índice O 1 2 3 4 Indwidio (a) Coste = 5 - 3= 2 Índice O 1 2 3 4 2 Procesados Individuo yy Coste = 5 - 4= 1 Índice O Individuo Coste = 5 - 2= 3 Figura 3.10: Cálculo del coste de un individuo: (a) individuo con 3 rutas válidas, @) individuo con 4 mtas válidas y una de ellas duplicada, (c) individuo con tan sólo 2 mtas válidas. La figura 3.10 muestra tres ejemplos del cálculo de la función de coste para tres situaciones distintas sobre el ejemplo seguido de la figura 3.1. En la figura 3.10(a) y (c), cuando son comprobados los elementos 3 y 2 de los respectivos individuos, surge una incompatibilidad entre rutas y, por tanto, el estudio del coste finaliza. Para esos casos, el coste evaluado es de 2 y 3 en el orden dado. Sin embargo, en el caso mostrado en la figura 3.10(b) el individuo a evaluar posee dos de las rutas seleccionadas duplicadas. Esta duplicidad es identificada y tratada por el algoritmo de calculo del coste eliminándola y evaluando solamente una única ocurrencia. Aplicando este proceso al último ejemplo citado, el coste final del individuo es 1. 3.3 Cobertura Basada en Rutas (CBR) 93 Resultados Experimentales Con el propósito de evaluar la solución basada en técnicas de programación evolutiva, aplicadas a la verificación con la métrica de cobertura de rutas, se ha escogido un conjunto de circuitos multinivel y de dos niveles, del banco de pruebas MCNC'91 [51]. Todos los experimentos presentados han sido procesados en un servidor Sun-Fire 280R con dos CPU UltraSPARC 111 a 900 MHz y 4 GBytes de RAM, ejecutando SunOS v5.8. Además se ha empleado GENEsYs [69] como núcleo del Algoritmo Genético y MIS11 [70] como sistema de síntesis lógica. La solución basada en Algoritmos Genéticos es comparada con un algoritmo Algoritmo Genético de búsqueda de rutas (fuerza bruta) [71], [72]. El algoritmo de búsqueda de rutas FrenteaSolución de comprueba todas las posibles combinaciones de rutas hasta encontrar el subconFue~mBmta junto de cobertura máxima. En todos los experimentos realizados con la solución evolutiva, se adoptó una estrategia de selección de los mejores individuos9 en el momento de determinar qué población permanecía en la siguiente generación como población descendiente1'. A su vez, el esquema de selección fijado al núcleo del Algoritmo Genético ha sido el proporcional. Todo ello sobre una población de 100 individuos. Finalmente, se ha permitido el empleo de Mutación Multipunto con cruzamiento, además de la Mutación Estándar. La tabla 3.2 muestra los resultados de la comparativa entre el Algoritmo Genético y el algoritmo de búsqueda exhaustiva de rutas. La primera columna presenta el nombre del circuito MCNC'91 [51] empleado. La columna segunda presenta la complejidad del circuito medida términos de número de puertas. La tercera y cuarta columna muestra el número total de rutas y el número de salidas del circuito, respectivamente. En la quinta columna se ofrece el número de intentos a realizar por parte del núcleo evolutivo. La sexta columna muestra el número de rutas que incluye el mejor vector encontrado por el Algoritmo Genético. En la columna séptima se presenta el tiempo de CPU tomado por el Algoritmo Genético para encontrar el mejor conjunto de rutas. En la columna octava se muestra el tiempo de CPU que toma el Algoritmo de búsqueda de rutas(fuerza bruta), para encontrar un subconjunto equivalente al encontrado con el Algoritmo Genético. Para finalizar, la última columna estima los ratios entre los tiempos de CPU de ambas soluciones. La figura 3.11 presenta gráficamente los ratios de tiempo de CPU y el número de intentos realizados para cada uno de los circuitos de la tabla 3.2. 'Identificado en la bibliografía como Stea& State. ''nombrado en la literatura anglosajona como offspnng. [SI] S. Yang. Logic Synthesis and Optimization Benchmavks Usev Guide vevsion 3. O. Microelectronics Center of North Carolina, 1991 [69] Thomas Back. A Usev's Guide to GENEsYs. University of Dortmund, Department of Computer Science, Systems Analisys Research Group, Dortmund, VI O edition, 1992. [70] R.K. Brayton, R. Rudell, AL. Sangiovanni-Vincentelli, and A. Wang. MIS: A Multiple Leve1 Logic Optimization System. IEEE Tmns. Comput-AidedDes. Integi: Civcuits Syst, 6(11):1062-1081, 1987. [71] J. Sosa, J. A. Montiel-Nelson, H. Navarro, and José C. García. Functional Vector Generation for Maximum Path Coverage using Evolutionary Programming. In XVIII Confevence on Design of Civcuits and IntegvatedSystems, November 2003. [72] J. Sosa, J. A. Montiel-Nelson, H. Navarro, and José C. García. Stimuli Sequence Generation for Verification and Validation of Maximum Power Consumption using Evolutionary Programming. In Evolutionaiy and Deteministic Methods fov Design, Optimization and Contvol with Applications to Industrial andSocieta1 Pvoblems 2005, September 2005. 1 O0 Generación de Vectores de Máxima Cobertura en las ecuaciones 3.13 y 3.14 es: Las ecuaciones 3.28-3.30 implementan el comportamiento tradicional de la puerta OR sobre la variable yd. La variable temporal y;, mediante las ecuaciones 3.3 1-3.33, modela la presencia de una transición propagada hasta el terminal B, mientras hay un cero lógico en el terminal A. Igualmente, y: determina si hay una transición propagada en el terminal A y un cero lógico en el terminal B con las ecuaciones 3.34-3.36. En la ecuación 3.37 se conforma la propagación de una transición presente de en alguna de las entradas de la puerta OR que representa con una combinación Dafos y Pmpagmión lineal de las variables y; y y:. Para finalizar, mediante la ecuación 3.38 se inhibe la posibilidad de la presencia de más de una transición simultánea en las entradas de la puerta OR. El comportamiento descrito en las ecuaciones 3.15 y 3.16 de una puerta INV se describe en MILP como: Optimización mediante MILP i Dada una red de Booleana G que representa un circuito de lógica combina- + cional, obtenido mediante un procedimiento de síntesis. Donde, G es una desDescripción del cripción estructural, empleando AND de dos entradas, OR de dos entradas e INV. Problema en MLP Este circuito puede ser expresado como un problema MILP empleando los modelos descritos mediante las ecuaciones 3.17-3.40. La función objetivo a optimizar es maximizar el número de rutas ejercitadas. Es de esperar que cada puerta que pertenece a alguna ruta ejercitada posea su bit de propagación activo. Y motivado porque el modelo de puerta desarrollado en esta Tesis Doctoral elimina la convergencia de múltiples transiciones propagadas a través de una misma puerta, cuando se determina que hay una ruta ejercitada es porque hay asegurado una ruta entre una entrada y una salida. Esa ruta entre entradas y salidas no posee puerta alguna en común con otra ruta. Ello significa que, 3.3 Cobertura Basada en Rutas (CBR) 101 de forma unívoca, el número de rutas ejercitadas se corresponde con el número de salidas primarias que tengan los bits activos. De las entradas no se puede decir nada pues una única transición presente en una entrada y el patrón de verificación adecuado puede producir una transición en múltiples salidas. Es reseñable indicar que el modelo prohibe la existencia de una convergencia de propagaciones de transición, pero sí permite la existencia de bifurcaciones, con lo cual de una única fuente, se puede obtener a la salida la ejercitación de múltiples rutas. Como ya se puede intuir, la función objetivo del problema MILP es obtener el máximo número de salidas primarias propagando o, su equivalente; maximizar el punción ~b~~~~~~ número de bits de propagación que pertenecen a las salidas primarias del circuito en estudio. Resultados Experimentales Al igual que se realizó con el procedimiento basado en programación evolutiva, se han procesado un conjunto grande de circuitos del banco de pruebas MCNC'91; que incluyen tanto circuitos combinacionales de dos niveles como los circuitos combinacionales multinivel. En este case se ha de determinar los vectores que maximizan la verificación funcional de los circuitos basada en la cobertura de rutas [73],[60]. Los resultados han sido evaluados en un servidor Sun-Fire 280R dotado de dos CPUs a 900 MHz con 4 GBytes de memoria RAM, ejecutando SunOS v5.8. El software que implementa esta metodología basada en Programación Lineal Mixta Entera, y en particular el algoritmo presentado en la figura 3.9, ha sido desarrollaGLPKcon núcleo de Resolución MILP do en lenguaje C, empleando el software libre GLPK v3.2.3 como núcleo para la resolución MILP. Cada circuito del banco de pruebas MCNC'91 ha sido preprocesado por la herramienta de síntesis lógica MIS11 y mapeado a una librería de puertas lógicas - NAND, NOR, INV - con mínima área. Se ha determinado el vector de máxima cobertura empleando el mismo algoritmo de búsqueda exhaustiva (fuerza bruta) del apartado 3.3.5. De igual forma, se ha obtenido mediante la metodología basada en MILP, el vector de máxima cobertura para la verificación de los circuitos con la métrica de cobertura de rutas. Las tablas 3.3, 3.4 y 3.5 muestran una comparativa, en términos de tiempo de computo de CPU, para obtener el primer vector funcional que maximiza la cobertura de rutas de datos de los circuitos combinacionales en estudio. Las cinco primeras columnas muestran el nombre, el número de puertas, entradas primarias, salidas primarias y rutas del circuito MCNC'91 en estudio. En la sexta columna se indica el número de rutas ejercitadas con el vector funcional de máxima cobertura, para la métrica de cobertura de ruta de datos. A continuación, en las columnas séptima y octava se presenta el número de variables necesarias en la formulación del problema MILP y el número de ellas que son de tipo binario. El tiempo de CPU requerido para obtener el resultado de la optimización mediante la metodo- [73] J. Sosa, J. A. Montiel-Nelson, H. Navarro, V de Armas, and R. Sarmiento. Functional Vector Generation for Combinational Circuits Based on Data Path Coverage Metric and Mixed Integer Linear Programming. In 5th Intemational Society fov Quality Electvonic Design, November 2004. [60] J. Sosa, J. A. Montiel-Nelson, H. Navarro, and José C. García. Functional Vector Generation for Maximum Data Path Coverage using Mixed Integer Linear Programming. InXVIII Confevence on Design of Civcuits andIntegvatedSystems, November 2005. 1 Circuito I Máxima I Metodoloeia MiLP I Fuerza Bruta cm82a 1 29 1 5 1 3 1 45 1 3 1 56 1 10 1 0'03 1 1'20E-04 1 3'15E+04 1 3'78E+00 1 1'26E+02 cm85a 1 56 1 11 1 3 1 91 1 3 1 108 1 22 1 0'08 1 1'00E-04 1 1'22E+03 1 1'22E-O1 1 1'52E+00 cmb 1 56 1 16 1 4 1 112 1 2 1 122 1 32 1 0'23 1 1'20E-04 1 2'5OE+03 1 3'00E-01 1 1'30E+00 O Del documento, los autores. Digitalizacián realizada por ULPGC. Biblioteca Universitaria, 2007 O Del documento, los autores. Digitalizacián realizada por ULPGC. Biblioteca Universitaria, 2007 Generación de Vectores de Máxima Cobertura Tabla 3.5: RESULTADOS EXPERIMENTALES Y COMPARATIVAS DE LA GENERACIÓN DE VECTORES FUNCIONALES PARA LA VERIFICACIÓN MEDIANTE MILP Y COBERTURA DE RUTAS DE DATOS (CONTINUACIÓN 11) 3.3 Cobertura Basada en Rutas (CBR) 105 logia MILP es mostrado en la columna novena. Por otro lado, el tiempo necesario para realizar la comprobación de la validez de un conjunto de rutas (satisfabilidad) con el método de búsqueda exhaustiva es indicado en la columna décima. A continuación, en la décimo primera columna se muestra el número de combinaciones sin repetición que hay que realizar para encontrar el vector de máxima cobertura, según la métrica de cobertura de rutas de datos. En la columna décimo segunda se presenta el tiempo estimado para que el algoritmo de búsqueda exhaustiva encuentre el vector de máxima cobertura. Y la última columna indica la relación en tiempo de CPU entre la solución de búsqueda exhaustiva y la metodología basada en MILP. Mejora del Tiempo de Computación Hasta ahora se ha planteado una metodología basada en Programación Lineal Mixta Entera (MILP), que permite abordar el problema de la generación de vectores de máxima cobertura. En ningún momento se ha abordado la optimización del problema MILP planteado, o incluso la utilización de un lenguaje de programaRec+ca"ófldel Problema MILP ción como PROLOG para solventar este problema. En este sentido, la figura 3.15 presenta cuatro versiones distintas de la formulación de una puerta NOR, donde tres de ellas están basadas en Programación Lineal Mixta Entera y la cuarta solución descrita en PROLOG. La figura 3.15(a) presenta el modelo introducido con anterioridad, donde hacen falta 13 ecuaciones y un total de 40 literales. La figura 3.15(b) muestra en cambio si se consideran valores enteros a las variables y' y y". En ese caso hacen falta 11 ecuaciones con 37 literales. En la figura 3.15(c) se presenta el modelo comprimido de la NOR. La compresión surge de la codificación de los estados de la puerta en dos bits y, no en asignar un bit a datos y otro a la condición de propagación. El número de ecuaciones en este caso es de 10 y 34 literales. Finalmente, la figura 3.15(d) presenta el modelo de puerta NOR descrito en PROLOG. En este caso sólo son necesarias 3 ecuaciones que poseen 11 literales en total. Tabla 3.6: COMPARATIVAS ENTRE DIVERSAS FORMAS DE CODIFICAR EL PROBLEMA CON MILP Y PROLOG Con el objeto de evaluar las prestaciones de dichas codificaciones, se han sometido las mismas a la obtención del vector de mayor cobertura para cuatro circuitos combinacionales de distinta complejidad, medido en número de puertas. Los circuitos seleccionados del banco de pruebas MCNC son apex5, b12, t481 y alu2. Estos circuitos fueron mapeados a mínima área con una librería de puertas NOR, NAND e INV con MIS11 y ejecutados en un Pentium IV a 1'8 GHz, 128 MBytes de RAM, y ejecutando Linux Debian v2.1. La tabla 3.6 presenta los resultados de dicha comparativa. Los tiempos de la tabla están expresados en milisegundos. La primera columna indica el circuito MCNC empleado. Las segunda, tercera y cuarta columna presentan la complejidad del circuito medida en el número de puertas, entradas y salidas del circuito, respectivamente. La columna Generación de Vectores de Máxima Cobertura Figura 3.15: Diversos modelos de descripción para la puerta NOR: a) completo, b) suponiendo y' y y" variables enteras, c) con las entradas codificadas, y d) PROLOG. quinta presenta el tiempo necesario para obtener el vector de máxima cobertura empleando el modelo inicial presentado en este trabajo. La sexta columna muestra, en cambio, el tiempo de CPU necesario para obtener dicho vector con la ligera modificación presentada en la figura 3.15(b). La evaluación del modelo que emplea codificación de estados (véase la figura 3.15(c)) se presenta en la columna antepenúltima. Las columnas penúltima y última muestran el tiempo necesario para compilar y obtener el vector de máxima cobertura con PROLOG. Conclusiones La complejidad computacional del problema de optimización de la generación de vectores funcionales basados en la cobertura de rutas en circuitos combinacionales crece exponencialmente con el número de puertas [42]. En este trabajo se propone una metodología eficiente para determinar los vectores funcionales que ejercitan rutas y maximizan la cobertura basada en rutas. Se ha empleado Programación Lineal Mixta Entera (MILP) para implementar la metodología propues- [42] J. Sosa, J. A. Montiel-Nelson, H. Navarro, José C. García, and R. Sarmiento. CircuitPath Covevage using Genetic Algonthms, pages 51-52. Evolutionary Methods for Design optimization and Control Applications to Industrial and Societal Problems. Intemational Center for Numerical Methods in Engineering, 2003. 3.4 Cobertura Basada en Potencia de Consumo ta [73]. Mediante una comparativa con un método de fuerza bruta se ha demostrado que la metodología propuesta obtiene vectores funcionales para optimizar la cobertura basada en rutas de forma eficiente (en términos de tiempo de CPU). La implementación de la metodología propuesta es siempre mejor que la implementación basada en fuerza bruta cuando el número de entradas primarias y salidas primarias del circuito es superior a ocho y tres, respectivamente. La mejora en términos de tiempo de CPU de la solución basada en MILP es varios órdenes de magnitud superior que la solución basada en fuerza bruta. Esta reducción permite comprobar circuitos de lógica combinacional en un tiempo de CPU práctico, frente a la aproximación basada en una simulación extensa [60]. Por otro lado, la optimización de las ecuaciones planteadas en MILP mediante la codificación de las entradas permite reducir el tiempo requerido para resolver el problema. A medida que el circuito crece en complejidad, dicha ventaja se incrementa. Además, el empleo de PROLOG par resolver los problemas propuestos es inoperativo, puesto que la etapa de compilación del problema supera en gran medida el tiempo requerido por el MILP. La metodología presentada posee obviamente una limitación en cuanto al crecimiento del circuito en términos de su número de puertas, a medida que éste crece, la generación de vectores toma más tiempo de CPU. 3.4. Cobertura Basada en Potencia de Consumo Debido al auge las aplicaciones donde la potencia de consumo es un factor crítico - multimedia y o móviles - la estimación de dicho factor ha tomado la relevancia que posee el ahorro de área. Existe un amplio espectro de aportaciones en este campo, las cuales se centran ~ét~i~a de Cobertum en diversos aspectos tanto en el campo del análisis como de la estimación" [74]. Las aportaciones en alto nivel se centran en la estimación de la potencia de consumo mediante macromodelos definiendo conceptos como granularidad y parámetros de actividad circuital [75]-[77]. También se han propuesto diversas herra- "El análisis consiste en aplicar un conjunto de modelos a un diseño existente implementado en cualquier nivel de descripción. La estimación por el contrario evalúa el circuito desconociendo a priori algún dato del mismo, por ejemplo parte de la estmctura o los patrones de entrada. J. Sosa, J. A. Montiel-Nelson, H. Navarro, V de Armas, and R. Sarmiento. Functional Vector Generation for Combinational Circuits Based on Data Path Coverage Metric and Mixed Integer Linear Programming. In 5th Intemational Society fov Quality Electvonic Design, November 2004. J. Sosa, J. A. Montiel-Nelson, H. Navarro, and José C. García. Functional Vector Generation for Maximum Data Path Coverage using Mixed Integer Linear Programming. InXVIII Confevence on Design of Civcuits andIntegvatedSystems, November 2005. ChristianPiguet. Low-PowevElectvonicsDesign. CRC Press, July 2004. M. Nemani and F. Najm Towards a High-Leve1 Power Estimation Capability. IEEE Tmns. on Computev-AidedDesign, 15(6):588-598, 1996. D. Marculescu, R. Marculescu, and M. Pedram. Information Theoretic Measures for Power Analysis. IEEE Tmns. on Computev-AidedDesign, 15(6):599-609, June 1996. M. Nermani andF Najm High-Leve1 Area andPower Estimation for VLSI Circuits. IEEE Tmns. on Computev-AidedDesign, 18(6):697-713, June 1999. 1 08 Generación de Vectores de Máxima Cobertura mientas. De entre las comerciales destacar Synopsys [78][79] o Magma [SO] y de entre las desarrolladas en el ámbito universitario MIS [70] o VIS [53]. La mayoría de las técnicas presentadas emplean aproximaciones basadas en métodos probabilísticos y estadísticos [S 11-[83]. Además, las soluciones propuestas emplean aproximaciones medias. En otras palabras, la estimación de la potencia de consumo total se realiza en base a un modelo de puerta para estimar la actividad media y a la distribución estadística de señales presentes a la entrada de la red Booleana. El principal objetivo de esas técnicas es obtener la potencia de consumo media de un circuito VLSI en condiciones típicas. Por otro lado, la estimación de la potencia de consumo media es un problema distinto a la estimación del peor caso de potencia de consumo [84]. El peor caso de potencia de consumo ha de ser considerado cuando sea un factor crítico del diseño, y haya una alta probabilidad de que exista. No obstante, es importante someter el sistema a esta condición a fin de conocer cómo se degradan sus prestaciones, entre otros objetivos. El problema del peor caso de consumo de potencia es equivalente a obtener la secuencia de estímulos de entrada que maximicen la potencia de consumo total. En términos de complejidad computacional, la naturaleza de la búsqueda de los estímulos de entrada que maximicen la potencia de consumo es definido como un problema NP-completo. En general, existen tres tendencias claras en los aportaciones previas; proceComplejidad del sos estocásticos, simulaciones Monte Carlo y los métodos basados en fractales. Problema El grupo de aportaciones basadas en procesos estocásticos reutiliza el aparato estadístico desarrollado para estimar valores medios en el cálculo de las potencias máximas de disipación [84]. Por el contrario las técnicas basadas en simulaciones Monte Carlo obtiene la potencia máxima del circuito aplicando diversas perturA. J. de Geus. Logic Synthesis Speeds ASIC Design. IEEE Spectvum, 26(8):27-31, August 1989. B. Chen and 1. Nedelchev. Power Compiler: A Gate-Leve1 Power Optimization and Synthesis System. ComputevDesign: VLSI in Computevs andPvocessovs, pages 74-79, October 1997. Xiaoyong Tang, Hai Zhou, and Rith Banerjee Leakage Power Optimization With DualVth Library in High-Leve1 Synthesis. 42nd IEEE Design Automation Confevence, pages 202-207, June 2005. R.K. Brayton, R. Rudell, AL. Sangiovann-Vincentelli, and A. Wang. MIS: A Multiple Leve1 Logic Optimization System. IEEE Tmns. Comput-AidedDes. Integi: Civcuits Syst, 6(11):1062-1081, 1987. R. K. Brayton, G. D. Hachtel, A. Sangiovann-Vincentelli, F. Somenzi, A. Aziz, S. T. Cheng, S. Edwards, S. Khatri, Y. Kukimoto, A. Pardo, S. Qadeer, R. K. Ranjan, S. Samary, T. R. Shiple, G. Swamy, and T. Villa. WS: a System for Verification and Synthesis. In Rajeev Alur and Thomas A. Henzinger, editors, Pvoceedings of the Eighth Intemational Confevence on Computev Aided Venfication CAV, volume 1102, pages 428-432, New Brunswick, NJ, USA, 1996. Springer Verlag. F. Najm Transition Density: ANew Measure of Activity in Digital Circuits. IEEE Tmns. Computev-AidedDesign, 12(2):3 10-323, February 1993. Z. Chen, K. Roy, and T. Chuo. Efficient Statistical Approachto Estimate Power Considering UncertainProperties of Rimary Inputs. IEEE Tmn. on Vevy Lavge Scale Integvation (VLSI) Systems, 6(3):484-492, February 1993. S. Gupta and F. Najm Power Modeling for High-Leve1 Power Estimation. IEEE Tmn. on Vevy Lavge Scale Integvation (VLSI) Systems, 8(1):18-29, February 2000. C. Wang andK Roy. Maximum Power Estimation for CMOS Circuits using Deterministic and Statistical Approaches. IEEE Tmn. on Veiy Lavge Scale Integvation (VLSI) Systems, 6(1):130-140, February 1999. 3.4 Cobertura Basada en Potencia de Consumo baciones a los vectores de entrada en cada iteración de la simulación Monte Carlo [85]. También, hay publicaciones recientes que estiman la potencia máxima de consumo basándose estrictamente en simulación o en fractales [86]. No obstante, estas últimas aportaciones se centran en la compactación de vectores más que en la estimación de potencia de consumo. 3.4.1. Modelo de Potencia de Consumo CMOS La potencia de consumo en los circuitos CMOS se compone de dos términos; r potencia estática y la potencia dinámica [87]. La potencia estática es debida a las corrientes de fuga de los diodos polarizados en inversa y es una fuente constante de disipación de potencia. El consumo dinámico a su vez se divide en dos componentes. La potencia de cortocircuito y la potencia de carga y descarga. La primera se produce por la llamada corriente de cortocircuito que se genera cuando conducen las redes NMOS y PMOS al mismo tiempo. Esto es, hay un camino directo desde VDD a tierra (GND). La segunda componente de la potencia dinámica es debida a la carga y descarga de las capacidades. Se ha demostrado que aumentar la actividad de conmutación del circuito conlleva a un aumento de la potencia dinámica [SI]. La actividad de conmutación mide el número de transiciones realizados en un circuito durante un ciclo de reloj. Obtener el máximo consumo de potencia es equivalente al problema de buscar la secuencia de estímulos de entrada que maximicen el número total de transiciones (actividad de conmutación) en un circuito. La aportación presentada en este capítulo es independiente del modelo de potencia de consumo. En el capítulo 5 se discutirá en detalle diversos modelos de potencia, todos son perfectamente válidos para aplicarlos a la metodología propuesta. 3.4.2. Función de Coste y Codificación Como ya se ha introducido en el apartado previo, el principal objetivo es obtener la secuencia de estímulos de entrada que maximicen la actividad de conmutación de un circuito dado. En este sentido, y con el objetivo de medir la actividad de transición, se ha desarrollado un estimador de actividad. Dado un circuito, el estimador de actividad mide el número de transiciones que aparecen cuando dos vectores de entrada se introducen secuencialmente. Es evidente que la función de coste de la solución basada en Algoritmos Genéticos es el propio estimador de transiciones. El vector de entrada de un circuito de lógica combinacional especifica los valores de entrada a la red Booleana de un circuito. Además, aplicado el vector de N. Evmorfopoulos, G. Stamoulis, and J. Avaritsiotis. A Monte Carlo Approach for Maximum Power Estimation Based on Extreme Value Theory IEEE Tmn. on Computev-Aided Design oflntegvated Civcuits and Systems, 21(4):415-432, April2002. R. Radjassamy and J. Carothers. Faster Power Estimation of CMOS Designs using Vector Compaction - a Fractal Approach. IEEE Tmn. on Systems, Man and Cybemetics, PavtB, 33(3), June 2003. K. Roy and S. Rasad. Lon-l'owev CMOS VLSI Civcuit Design. John Willey and Sons, Inc., New York, 1st edition, February 2000. Potencia Estáfica y Dinámica Estimador de Actividad 116 Generación de Vectores de Máxima Cobertura 3.4.3. Resultados Experimentales Con el objetivo de evaluar la metodología propuesta empleando Algoritmos Genéticos para obtener la secuencia de estímulos que maximizan la potencia de consumo de un circuito combinacional, el conjunto de circuitos de dos niveles y multinivel con más de 1000 puertas del banco de pruebas MCNC'91 ha sido procesado [72]. Los resultados han sido calculados en un Pentium IV a 2'8 GHz, con 1 GByte de RAM, ejecutando el Sistema Operativo Linux Debian 3.3.4 con el kernel2.6.7. Se ha empleado GCC v3.3.5, y el software GENEsYs v1.0 como núcleo del alNúcleodelAlgontmo goritmo genético, y MIS11 como sistema de síntesis lógica. Se ha desarrollado Genético un estimador de actividad de conmutación en lenguaje C. Tanto el estimador de actividad de conmutación como el núcleo de GENEsYs han sido completamente integrados en la suite de herramientas OLYMPO [89]. Cada circuito del banco de pruebas MCNC'91 ha sido preprocesado con el sistema de síntesis lógica y mapeado a una librería de puertas lógicas - NAND, NOR e INV - con mínima área. Cada circuito ha sido procesado con la metodología basada en Algoritmos Genéticos para obtener la secuencia de estímulos de entrada que maximizan la potencia de consumo. Además, los circuitos han sido procesados con el estimador de actividad de conmutación propuesto en [90]. Ambos algoritmos han sido ejecutados para obtener la potencia de consumo máxima. En todos los experimentos basados en Algoritmos Genéticos, la estrategia para A el reemplazo de las generaciones antiguas, después de generar la nueva población, ha sido el de seleccionar los meiores individuos. El esquema de selección ha sido el proporcional y la población de 100 individuos. Finalmente, se ha empleado Cruzamiento Multipunto y Mutación Estándar. La tabla 3.7 muestra una comparativa en términos de la actividad de conmutación estimada para obtener la potencia de consumo máxima con una técnica probabilística y la solución aquí presentada basada en Algoritmos Genéticos. La Técnica P,,,babilisfica Frente primera columna presenta el nombre del circuito de acuerdo con el banco de prueasoiucióflaurisfica bas MCNC'91. La columna segunda presenta la complejidad del circuito medida en número de puertas. La tercera columna muestra la actividad de conmutación máxima alcanzada cuando se aplica una técnica probabilística. La quinta columna presenta el número de puertas que conmutan con los vectores generados por la aportación basada en Algoritmos Genéticos. La sexta columna muestra la actividad de conmutación como el porcentaje de puertas que conmutan del total del circuito. Finalmente, la última columna presenta la diferencia entre estimar la potencia de consumo mediante métodos probabilísticos y la técnica basada en Algoritmos Genéticos, La complejidad de los circuitos tratados, medida en términos de puertas, ha sido desde circuitos poco complejos como los circuitos ex5 y table5 con algo más [72] J. Sosa, J. A. Montiel-Nelson, H. Navarro, and José C. García. Stimuli Sequence Generation for Verification and Validation of Maximum Power Consumption using Evolutionary Programming. In Evolutionavy and Deteministic Methods fov Design, Optimization and Contvol with Applications to Industrial andSocieta1 Pvoblems 2005, September 2005. [89] J.A. Montiel-Nelson, V. De Armas, and A. Sarmiento, R. and Nuñez. A Cell and Macrocell Compiler for GaAs VLSI Full-Custom Design. Pvoc. Design Automation and Test in Euvope, Con$ andExhibition, pages 947-948, feb 1998. [90] A. Ghosh, S. Devadas, K. Keutzer, and J. White. Estimation on Average Switching Activity in Combinational and Sequential Circuits. Pvoc 29th ACMLEEE Design Automation Confevence, pages 243-259,1992. 3.4 Cobertura Basada en Potencia de Consumo 117 Tabla 3.7: COMPARATIVA DE LOS RESULTADOS EXPERIMENTALES EMPLEANDO ALGORITMOS GENÉTICOS Y UNA TÉCNICA PROBABIL~STICA PARA OBTENER EL CONSUMO DE POTENCIA MÁXIMO, MEDIDO COMO ACTIVIDAD DE CONMUTACI~N Circuito Actividad Circuital MCNC'91 Solucibn I Diferencia de mil puertas. Por otro lado, el más complejo ha sido el C6288 con más de cuatro mil puertas. La actividad de conmutación media ha superado en todos los casos el 50 % del circuito, independientemente a la técnica empleada. Hay que tener en cuenta que la comparativa se realiza con una técnica probabilística, y debido exclusivamente a su naturaleza estadistica, no tiene como objetivo obtener la secuencia de entrada que maximiza la potencia de consumo. Esta técnica se ha planteado como referencia ya que en la literatura se emplea para establecer la potencia máxima de la red Booleana en estudio. Sin embargo, Precisión la metodología basada en Algoritmos Genéticos difiere hasta un 13 % en valor absoluto del valor precedido por la técnica estadistica. Y en particular, para cinco de los casos estudiados la potencia máxima determinada por la solución basada en Algoritmos Genéticos posee valor inferior que la potencia estimada por el método probabilístico. El esfuerzo computacional en términos de tiempo de CPU necesario no es significativo. El tiempo de CPU necesario para todas las ejecuciones tanto de la solución basada en Algoritmos Genéticos como la probabilística están por debajo del segundo. La figura 3.21 muestra la convergencia de una búsqueda con cinco secuencias. La mayoría de las secuencias convergen en un número corto de intentos. La convergencia comienza sobre los mil intentos. Una vez se alcanzan los mil intentos, co,,,,i, el esfuerzo computacional requerido para incrementar la actividad de conmutación es al menos diez veces mayor que la requerida para alcanzar el punto de convergencia, medido en términos de intentos. Además, no todas las secuencias poseen un grado parecido de actividad de Generación de Vectores de Máxima Cobertura Función de coste del circuito C6288 O 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Intentos Figura 3.21: Convergencia de la función de coste del circuito C6288 para la búsqueda de la secuencia de estímulos de entrada con un conjunto de 5 búsquedas simultáneas. conmutación. Por ejemplo, se puede observar que la quinta secuencia del ejemplo de la figura 3.21 posee un grado muy bajo de convergencia con respecto a las otras secuencias encontradas. En este ejemplo, la actividad de conmutación de la quinta secuencia está lejos del valor final de la actividad de conmutación del resto de secuencias encontradas. 3.4.4. Conclusiones Se ha propuesto una metodología eficiente para obtener la secuencia de estimulos de entrada que maximizan la potencia de consumo de un circuito de lógica combinacional [42]. Se emplean Algoritmos Genéticos como procedimiento heuristico para implementar la metodología propuesta. Las comparativas con una estrategia probabilistica han demostrado que la solución adoptada obtiene secuencias de entrada que maximizan la potencia de consumo de una forma eficiente (en términos de tiempo de CPU y número de intentos necesarios) [72]. Se ha probado de forma univoca que las técnicas probabilisticas dependen de la distribución de probabilidad de los estímulos de entrada, y que estas no son conocidas a priori si se desea obtener los valores máximos de potencia de consumo. La calidad de las secuencias generadas - medida en actividad de conmutación - con la solución aportada con la técnica evolutiva son excelentes en todos [42] J. Sosa, J. A. Montiel-Nelson, H. Navarro, José C. García, and R. Sarmiento. CivcuitPath Covevage using Genetic Algonthms, pages 51-52. Evolutionary Methods for Design optimization and Control Applications to Industrial and Societal Problems. Intemational Center for Numerical Methods in Engineering, 2003. [72] J. Sosa, J. A. Montiel-Nelson, H. Navarro, and José C. García. Stimuli Sequence Generation for Verification and Validation of Maximum Power Consumption using Evolutionary Programming. In Evolutionavy and Deteministic Methods fov Design, Optimization and Contvol with Applications to Industrial andSocieta1 Pvoblems 2005, September 2005. 3.4 Cobertura Basada en Potencia de Consumo los casos. Además, el número de intentos pueden ser ajustados en función del tamaño total del circuito - medido en número de puertas - para reducir aún más el tiempo computación. 120 Generación de Vectores de Máxima Cobertura Capitulo 4 Optimización del Retardo Índice General 4.1. Introducción .......................... 124 4.2. Trabajos Previos ........................ 126 4.3. Sinopsis. ............................ 128 4.4. Formulación del Problema de Optimización de la Ruta Crítica ................................ 129 4.4.1. Conjunto Ruta Crítica ................. 129 4.5. Optimización de un Circuito Empleando el Conjunto Ruta Crítica ............................. 131 4.6. Curva de Prestaciones de un Circuito ............ 132 4.6.1. Mapeado a Mínima Area Activa ............ 132 4.6.2. Cuma de Prestaciones ................. 134 4.6.3. Algoritmo de Cálculo de la Cuma de Prestaciones . . 135 4.6.4. Modelo de Retardo y Área Activa de Puerta ...... 137 4.6.5. Cuma de Prestaciones empleando Programación Lineal 139 4.6.6. Complejidad de la Optimización ............ 140 4.6.7. Comparativa ...................... 144 4.6.8. Cumas de Prestaciones ................. 146 4.7. RTL versus Circuito de Lógica Combinacional ....... 146 4.8. Conclusiones .......................... 151 122 Optimización del Retardo Glosario de Términos - MA meve(g,n) path pat hcp PO RTL Área activa del circuito. Punto del espacio de diseño que posee el &ea A y la potencia P. Factor de velocidad de la puerta gate. Espacio de diseño completo de un circuito. Capacidad de cableado y de puerta soportado. Cum de prestaciones bptimas de un circuito. Capacidad de la puerta i. Capacidad de cableado. Conjunto de rutas dependientes de la ruta critica. Arco que modela la conexibn j entre dos puertas lbgicas. Puertas conectadas como fuentes de señal a la puerta vi Entradas del cono lbgico de entrada que define la ocurrencia de g en n Puertas conectadas como carga a la puerta vi Circuito combinacional expresado como grafo. Última puerta desde las entradas de larutapath,,,,, Conjunto de rutas independientes de la ruta critica. Libreria de puertas. Libreria de puertas. Libreria de puertas convexa. Libreria de puertas con versiones de minima &ea. Conjunto de desuipciones flsicas de la puerta k. mapeado aminima área. Ocurrencia de la puerta de libreria g en el vkrtice n. Ruta. Ruta critica o camino uitico. Conjunto de salidas primarias del circuito. Register Transfer Language, lenguaje de transferencia de registros. Tiempo máximo del dominio de definicibn de la ruta critica. Retardo de un punto no inferior. Tiempo minimo del dominio de definicibn de la ruta uitica. Tiempo máximo en la salida de la puerta gate. Tiempo máximo del circuito. Retardo de la puerta gate. Retardo interno de puerta i. Primera puerta desde las entradas de la ruta path,,,,, Vkrtice, nodo que representa a la puerta combinacional i. Very Large Scale Integration. En el capítulo anterior se presentó la forma de generar vectores de máxima cobertura con el objeto de reducir el tiempo de verificación. Otro aspecto muy importante en la verificación de sistemas integrados es el modelo temporal adoptado durante la verificación. Si el objetivo es comprobar estrictamente la funcionalidad implementada sin atender a las prestaciones de las mismas, un modelo temporal a nivel de ciclo de reloj puede ser válido. Pero, el problema surge cuando no sólo se requiere comprobar la funcionalidad con respecto a un conjunto de reglas y es necesario contrastar un conjunto de prestaciones y además la complejidad del diseño apura al límite las características de una tecnología - velocidad, número de puertas entre registros, entre otras. En ese caso, no es válido cualquier modelo de retado, es necesario analizar el circuito para obtener los retardos significativos de las diversas funcionalidades y anotar dichos retardos en los modelos funcionales diseñados, para verificarlos temporalmente. Por otro lado, dado un diseño, éste puede poseer diversas implementaciones circuitales. Cada una de esas implementaciones circuitales da origen a retardos diversos. Un handicap existente hoy día es que en vez de explorar el espacio de diseño de los sistemas integrados, con el objeto de obtener la curva de prestaciones de estos, se opta por encontrar una solución que puede cumplir o no la verificación del diseño. Consecuentemente, cada vez que se viola alguna regla de verificación Optimización del Retardo 123 debido a la temporización de la implementación obtenida, hay que buscar otra nueva solución circuital que supere toda la verificación. Este capítulo propone una metodología de exploración del espacio de diseño de un circuito con el objeto de encontrar el rango de soluciones válidas que cumplen la verificación. En este capítulo se presenta una metodología para la exploración de las prestaciones de circuitos combinacionales en términos de los parámetros área activa y retardo de la ruta crítica. La técnica propuesta realiza una optimización de las dimensiones de las puertas utilizando factores que compiten entre sí, el área activa y el retardo. El área activa total del circuito se supone que es una función lineal del tamaño de las puertas. Existe una ruta crítica cuyo retardo - el retardo temporal más largo del circuito - depende del tamaño de las puertas individuales. Durante el proceso de optimización este retardo cambiará muchas veces. El proceso de optimización se utilizará para generar la curva de prestaciones, que es el objetivo de este capítulo. La metodología propuesta se basa en la optimización Cunade Presfacione~ de la ruta crítica del circuito. La optimización de la ruta crítica del circuito es un problema de dimensionado de puertas en aquellas rutas que definen el retardo del circuito. Dado un tamaño de driver1 para todas las puertas del circuito, la curva de prestaciones contendrá aquellos puntos del espacio de diseño de mínimo retardo y área activa. En este capítulo se presenta un método que optimiza un subconjunto variable de la red Booleana que representa al circuito bajo optimización. Sólo aquellas puertas de la ruta crítica serán optimizadas. Aquellas puertas en la red Booleana que no forman parte de la ruta crítica no necesitan ser optimizadas. Se propone un método eficiente para actualizar la ruta crítica a medida que la curva de prestaciones se obtiene. La comparación de prestaciones y los resultados expuestos se obtienen sobre el banco de pruebas o benchmark MCNC'91, circuitos combinacionales de dos niveles y multinivel. La metodología propuesta genera curvas de prestaciones, en circuitos relativamente grandes, decrementando notoriamente el número de variables v el tiempo de ejecución en comparación con el método de obtención de la curva de prestaciones para la red Booleana completa - el método tradicional. Con esta propuesta, el número de variables se reduce en un factor de hasta 7'3 veces en comparación con el método tradicional - la computación de la red Booleana completa utilizando Programación Lineal. La característica de tiempo de ejecución es excelente, con una mejora entre 1'5 y 32'5 veces el tiempo de CPU empleado en el cálculo con la red Booleana completa. Cuanto mayor sea el número de puertas del circuito, mayor será la mejora en tiempo de CPU y en su complejidad - número de variables. Este capítulo comenzará en su apartado 4.1 con una introducción al análisis de prestaciones, para a continuación en el apartado 4.2 presentar los estudios previos desarrollados en este ámbito. En el apartado 4.3 se planteauna sinopsis del trabajo aquí presentado. El apartado 4.4 perfila el conjunto de definiciones necesario para abordar la formulación del problema de optimización de la ruta crítica. En este apartado se definirán conceptos básicos de teoría de grafos, la ruta crítica y el conjunto ruta crítica y sus dependencias con el resto de circuitos. El apartado 4.5 propone una metodología para optimizar un circuito empleando su ruta crítica. La curva de prestaciones de un circuito y un algoritmo para obtenerla se abordan en profundidad en el apartado 4.6. Se discutirá el particular punto de arranque 'Término anglosajón que identifica a un circuito amplificador que adapta la impedancia entre los circuitos conectados a su entrada y a su salida. 124 Optimización del Retardo del algoritmo de análisis de prestaciones. Además, se muestra una versión del algoritmo de análisis de prestaciones empleando Programación Lineal. También se analiza la complejidad de la optimización y se plantea la comparativa de la metodología presentada con la metodología tradicional. Se presenta la curva de prestaciones para el circuito bw. En el apartado 4.7 se extiende la metodología propuesta al nivel RTL lo cual permite emplearla tanto a nivel estructural como funcional. Para finalizar este capítulo, en el apartado 4.8 presenta las conclusiones del mismo. 4.1. Introducción Aumentar la frecuencia de funcionamiento de un circuito implica reducir el retardo de su ruta crítica. Dada una red Booleana 2 que representa el circuito a optimizar y que se encuentra mapeado2 en un punto del espacio de diseño óptimo en área y retardo. La subred que define el retardo máximo del circuito es la ruta crítica . El retardo de la red Booleana viene fijado por esa subred. Además, dicha subred es susceptible de cambiar durante el proceso de optimización. ~uta Crifica El objetivo de la optimización en retardo basado en la ruta crítica es el de Dinámica obtener menores retardos del circuito, manteniendo el resto de las puertas del circuito mínimos en área. La ruta crítica es dinámica, es decir, a medida que el retardo del circuito cambia, también cambia el tamaño de la subred ruta crítica. Por tanto, dado un punto del espacio de diseño existe una ruta crítica cuyo retardo puede ser optimizado hasta un límite. El límite de esta optimización del retardo se alcanza cuando la ruta deje de ser crítica o no pueda ser mejorada en retardo. El problema de optimización de la ruta crítica de un circuito puede ser abordado como un problema de dimensionado de puertas sobre aquellas rutas que Opfimiración de la definen el retardo más largo del circuito. El dimensionado de puertas es un proceRuta Cdtica so de optimización del retardo. En una red Booleana que representa a un circuito, la capacidad de carga de una puerta es ajustada adecuadamente tal que el área del circuito o la potencia de consumo es minimizado bajo unas restricciones de temporización. Durante la optimización de un circuito, una ruta crítica nueva podría surgir. Por ejemplo, dado un tamaño a cada puerta del circuito, una ruta crítica un subconjunto de la red - define el máximo retardo del circuito T,,,; cuando el máximo retardo es reducido, mediante el dimensionado de cada una de las puertas, pueden aparecer otros subconjuntos con mayor retardo La curva de prestaciones área-retardo de un circuito es empleada por los diseñadores VLSI para obtener las prestaciones de los dimensionados de las puertas de la red, siempre bajo alguna restricción de temporización. Cada conjunto de dimensiones de puerta define un retardo en el circuito. Este retardo lo define la ruta crítica del circuito. El proceso de optimización del tamaño de puerta se emplea para calcular un único punto de la curva de prestaciones área-retardo. Las aportaciones publicadas en este área obtienen la curva de prestaciones empleando la red completa y no el subconjunto de esta que supone su ruta crítica. En estas soluciones, tanto el número de restricciones como el de variables, necesarias para resolver el problema planteado, es lineal con el número de puertas del circuito. A mayor complejidad - medida en numero de puertas - mayor esfuerzo 'Una de las etapas de la síntesis lógica es el mapeado tecnológico. Esta fase asigna células de una librería física a las puertas lógicas de una red Booleana 2 que ha sido optimizada a nivel lógico. 4.1 Introducción 125 computacional [91]. El procedimiento normal para obtener la curva de prestaciones requiere el cálculo de muchos puntos de la curva, mediante la repetición del proceso de diPmced'miento Nomal mensionando las puertas con la red completa. Para calcular un punto de la curva de prestaciones área-retardo, se fija una restricción de retardo y se optimiza el área, eligiendo los tamaños de puerta correctos - empleando algún algoritmo de dimensionado. De un punto a otro de la curva, la red que define la ruta con más retardo, el conjunto ruta crítica, podría cambiar. A pesar que el cálculo de un punto de la curva de prestaciones se realizada mediante un método iterativo de dimensionado de puerta [92], el conjunto de puertas ha de ser actualizado en cada iteración. En este capítulo, se propone un método para obtener la curva de prestaciones área-retardo, dimensionando exclusivamente las puertas de la ruta crítica del circuito y no todas las puertas del mismo. Dimensionado solamente las puertas que pertenecen a la ruta crítica del circuito, se eliminan de los cálculos todas aquellas puertas que no contribuyen al mayor retardo del circuito. Ello redunda en la reducción del número de variables y por tanto el esfuerzo computacional necesario para resolver el problema. En el método presentado, el cálculo de la curva de prestaciones comienza con un circuito mapeado a mínima área y, mediante optimizaciones sucesivas de dimensionado de puerta, éste finaliza en el punto de mínimo retardo de la curva de prestaciones - óptimo en área. Cuando no es posible reducir el retardo con mínima área activa, el método finaliza. Durante el cálculo de la curva de prestaciones, de un punto a otro, el retardo del circuito se reduce. Para calcular un nuevo punto de la curva de prestaciones con menor retardo, se fija una restricción de temporización tal que el conjunto de puertas de la ruta crítica no cambie. Se restringe la reducción de retardo de la ruta crítica actual empleando un límite inferior. El límite inferior del conjunto ruta crítica actual es el retado máximo del siguiente conjunto ruta crítica. Por ello, el rango de variación del retardo del conjunto ruta crítica - el dominio temporal de definición del conjunto ruta crítica - está limitado. Además se propone un procedimiento de actualización de las puertas del conjunto ruta crítica, cuando su retardo no puede ser reducido más. La propuesta desarrollada en este trabajo de investigación para mapear, tecnológicamente, una red Booleana 2 en una librería de células full-custom consiste en: comenzar la optimización en un punto del espacio de diseño conocido (mínimo en área) e ir disminuyendo el retardo de la ruta crítica dinámica utilizando la mínima de área requerida. En el espacio de diseño hay un punto que es mínimo en área, que es el idóneo MnimoMinimorum en área para iniciar la exploración del espacio de diseño. Este punto de arranque de la exploración del espacio de diseño es el de mínima área global, que se ha obtenido mapeando la descripción lógica al conjunto de puertas que tienen mínima área (véase figura 4.1). A partir del punto del espacio de diseño mínimo minimorum en área, el objetivo es ir mejorando el retardo definido por la ruta crítica dinámica del circuito, optimizando siempre el área. Para una ruta crítica del circuito, el interés - M.R.C.M. Berkelaar, P.H.W. Buurman, and J.A.G. Jess. Computing the Entire Active AreaPower Consumption versus Delay Tradeoff Curve for Gate Sizing with a Piecewise Linear Simulator. IEEE Tmns. Comput.-Aided Des. Integi: Civcuits Syst., 15(11): 14241434,1996. G. Chen, H. Onodera, and K. Tamaru. An Iterative Gate Sizing Approach with Accurate Delay Evaluation. Pvoc. ACMLEEE Design Automation Con$, pages 422-427, November 1995. 132 Optimización del Retardo De aquí que se obtiene el límite inferior - Ti como una solución de la siguiente optimización de punto simple: Minimise the delay time of path,,,i, T(path,,,i) Minimise the active area, A, ~fpath,,,~ s.t. (i) a lower bound delay time defined as: La optimización del retardo del conjunto ruta crítica p~th,,,~ posee un límite inferior que es el máximo retardo de las rutas independientes del conjunto ruta crítica. El retardo y el área activa son minimizados. El retardo es restringido para no ser más rápido que el retardo de las rutas dependientes del conjunto ruta crítica. 4.6. Curva de Prestaciones de un Circuito En el apartado previo, se ha introducido el dominio de definición temporal de un conjunto ruta crítica. Dado un p~th,,~, se ha minimizado el retardo Ti apliDominio de D$%ición de una cando la ecuación 4.6, y ello ha derivado en el retardo inferior de la ruta. El par ~uta Crifica (Ti, Ai) es un punto de la curva de prestaciones - área activa Ai frente a retardo -- Ti. El retardo menor de la ruta - Ti no está incluido en el dominio de definición temporal de path,,i. Dado un tamaño de driver para todas las puertas del circuito, en los puntos no inferiores del espacio de diseño, el retardo y el área activa son mínimos. En particular, se representa el componente de retardo T de un punto no inferior como T. En el menor retardo Ti, de la ruta crítica de un circuito 2, se define otro nuevo - conjunto path,,, pues hay que unir a la ruta crítica p~th,,~ todas aquellas rutas dependientes e independientes que alcanzan dicho valor de retardo. El dominio de definición de path,,,, es ahora (T,,E], donde el límite superior es - Si, y el límite inferior es la solución de aplicar~uevamente la ecuación 4.6 apath,,,,. Además, el retardo menor T, no es incluido en el dominio de definición de path,,,,. Aplicando deforma sucesiva la ecuación 4.6 a la secuencia apropiada de rutas críticas se obtiene la curva de prestaciones de un circuito. La búsqueda de esta secuencia de conjuntos de rutas críticas (p~th,,~, p~th,,~, . . ., path,,i, p~th,,,~, . . .) requiere un proceso de actualización del conjunto ruta crítica, para que la curva de prestaciones sea calculada, y además es necesario un conjunto ruta crítica p~th,,,~ de inicio. En este apartado se presenta al mapeado de mínima área activa y retardo. A partir de este punto se define el conjunto ruta crítica de comienzo p~th,,~. También se presenta un método - y su implementación algorítmica para actualizar el conjunto ruta crítica. 4.6.1. Mapeado a Mínima Area Activa Sea LL = (1, . . ., N) un conjunto de puertas lógicas - NAND, NOR, INV, Librenú de Pue*ar . . . esto es, una librería de puertas lógicas. N es el número de puertas lógicas en Lógicar 4.6 Curva de Prestaciones de un Circuito 133 la libreria LL. Para cada puerta lógica, hay varias versiones de su implementación7 fisica. Sea Lk = (1, . . ., Mk) un conjunto de implementaciones fisicas de una puerta lógica k, k t LL. Sea L = {Lk V k t LL) una libreria de mapeado. + Dada una ruta crítica G correspondiente a un circuito de lógica combinacional obtenido mediante un procedimiento de síntesis tecnológicamente independiente, e.g. 2 es una descripción estructural NAND-INV, un conjunto de restricciones de diseño y una libreria L; un mapeado M es una transformación de 2 en una net-lis? de puertas lógicas N, que es formalmente equivalente a 2 y satisface las restricciones de diseño. La medida de las prestaciones de una puerta lógica k, k t LL, es el conjunto de pares (retardo, área activa). Ello se expresa formalmente tal como sigue: donde Lk es el conjunto de versiones de descripciones fisicas de la puerta lógica k. Por ejemplo, las puertas BUF 1 y BUF4 en una libreria de células estándar son las ,,,,,de ,,,, versiones 1 x y 2 x de un buffer no inversor BUF. Una libreria de prestaciones L se emplea para mapear 2 en N mediante la transformación M, y se define como: En una libreria de células estándar, las prestaciones retardo y área activa son funciones no continuas del tamaño de driver de puerta. Sin embargo, para las células full-custom, sus prestaciones son funciones continuas del driver de puerta. Deñnición 9 (Librería Convexa Objetivo). Una libreria de puertas de prestacio- , . nes L es una libreria convexa objetivo L cuando para cada una puerta lógica k, k t LL, la función área activa es una función convexa del retardo: Vk t LL) (4.9) U donde A(T~) es una función convexa de ~k Deñnición 10 (Espacio de Diseño). Dada una ruta critica de un circuito e, su espacio de diseño es dejnido por una función C, donde una transformación M determina la 3-tupla (retardo, área activa ypotencia de consumo), (1, A, 'P), esto es C : M - l x A x 'P para una condición carga salida de 2. Deñnición 11 (Puertas de Mínima Área Activa). Se dejne las puertas de minima área activa LA - como sigue: LA - = {j j t LkAiVkt ,- LL) (4.10) L = {(T 1 & = min (Aic,~), ,- k t LL, VI t Lic) (4.1 1) donde min (Ak,~) es el área activa minima, 'Traducción directa del término anglosajón layout. Con este término se identifica a la vista que representa la disposición de los elementos que conforman los dispositivos e interconexiones de un diseño desde un punto de vista físico. 'Una net-list es una descripción estmctural donde se identifican las implementaciones físicas de los elementos que la componen y sus interconexiones. 134 Optimización del Retardo Deñnición 12 (Curva de Prestaciones). En particular, todos los puntos no inferiores del espacio de diseño CtradeOff dejnen el mapeado óptimo M en retardo y área activa (F, J), es decir: donde T y A son los puntos no inferiores (retardo y área activa) del espacio de diseño C. Teorema 1 (Mapeado de Mínima Área Activa). Dada una redBooleana multini- + U + ve1 G y una libreria de puertas convexa L, el mapeado M* - de G en N con esas p.flto~o~nferior puertas de minima área activa es un punto no inferior del espacio de diseño C: Demostración. El área activa total de una net-list N son puntos no inferiores de C, es decir A = A(n), donde A(n) es el área activa de la puerta n. Debido a ntN que A(n) es la minima área activa de cada puerta n, A pertenece a A. Para demostrar que T pertenece a T, por contradicción, se asume que existe U un mapeado M con igual área activa pero menor retardo. En tal caso, la libreria L no sería una librería convexa. O Desde el mapeado inicial M*, - se puede solamente reducir el retardo, puesto U que M* emplea las puertas de minima área de la libreria L. ~o~lo tanto, M* es un punto final de mapeado del espacio de diseño C y la curva de prestaciones CtradeOff, por ello el cálculo de este punto no inferior del espacio de diseño no requiere proceso de optimización alguno. Además, la importancia de este punto es trascendental, pues sin conocer el conjunto ruta crítica se obtiene un punto de la curva de prestaciones. 4.6.2. Curva de Prestaciones Desde el punto de la curva de prestaciones M* - de un circuito de lógica combi- + nacional G, un conjunto ruta crítica se define mediante p~th,,~, donde el retardo de ruta E es T(p~th,,,~), y mediante la resolución de la ecuación 4.6, se obtiene un segundo punto de mapeado de la curva de prestaciones A& para el conjunto ruta crítica p~th,,~ y con un retardo inferior - To. Además, (To, - E] es el dominio de definición del conjunto ruta crítica p~th,,,~, el intervalo (MA, - M0] es el dominio de definición del mapeado (o dominio de definición) del conjunto ruta crítica p~th,,~. + Ruta Cdtica Dinámica La ruta crítica de G cambian a medida que se obtienen los puntos de la curva de prestaciones. Por lo tanto, el conjunto inicial definido como conjunto ruta + crítica p~th,,~ de G debe ser redefinido - como una ruta p~th,,,~ dinámica - siempre que la optimización progrese. El conjunto ruta crítica p~th,,~ se actualiza como sigue. Si el retardo inferior T, iguala al máximo retardo de alguna ruta independiente del conjunto ruta crítica, entonces el nuevo subconjunto p~th,,,~ de la red 2 es el resultado de unirlos con el conjunto ruta crítica p~th,,~. Además, los retardos de esas rutas incluidas han 4.6 Curva de Prestaciones de un Circuito de ser contemplados en el cómputo del retardo de la nueva ruta crítica p~th,,~. Esto se expresa formalmente como: Upd~tePath,,~() for each independent path pathl,, on critical path set p~th,,,~ if T(pathl,,) ) T(p~th,,~) then path,,i = path,,i U pathl,,; end if; end for; for each dependent path path,,, on critical path set p~th,,~ if T(path,,,) ) T(p~th,,~) then path,,i = path,,i U path,,,; end if; end for; end Upd~tePath,,,~ () Figura 4.3: Algoritmo de actualización del conjunto mta crítica. La figura 4.3 muestra el algoritmo para actualizar el conjunto ruta crítica p~th,,,~. Más allá del punto de la curva de prestaciones M0, el circuito presenta un nuevo conjunto ruta crítica p~th,,~. Una posterior optimización mediante la aplicación de 4.6 provee un nuevo punto de mapeado de la curva de prestaciones a. El intervalo (a, a] es el dominio de definición del mapeado del conjunto ruta crítica p~th,,~. Sobre el límite superior de el circuito presenta un nuevo conjunto ruta crítica p~th,,,~, y así sucesivamente. El proceso de cálculo finaliza cuando se alcance un punto para el cual no hay reducción del retardo con mínima área activa. 4.6.3. Algoritmo de Cálculo de la Curva de Prestaciones CtradeOff () es el algoritmo propuesto para calcular la curva entera de retardo frente a área activa de un conjunto ruta crítica (véase la figura 4.4), cuando una + red G es mapeada a una librería de prestaciones convexa L. El algoritmo encuentra el mapeado y el dominio de definición temporal para cada conjunto ruta crítica p~th,,,~ de un circuito de lógica combinacional, donde se ha ignorado el problema de la ruta falsa [106]. La salida del procedimiento CtradeOff () es un conjunto de pares (F, A), y para cada pareja de pares se define un mapeado M, Ctradeoff = {M C(M) t (T, A)}. 11061 H.C. Chen and D.H.C. Du. Path Sensitization in Critica1 Path Problem. IEEE Tmns. Comput.-AidedDes. Integi: Civcuits Syst., 12(2): 196-207, 1993 136 Optimización del Retardo Ctradeo f f () + given a G = (v, E, 7); map 2 to a LA, - M0 = M4; obtain the critica1 path set p~th,,~; do update 'j; = T(p~th,,~); optimise path,,i by Equation 4.6; UpdatePath,,i(path,p,i); update < = T(p~th,,,~); while 'j; # end Ctradeoff () Figura 4.4: Algoritmo para la generación de la cuma completa de prestaciones. El dominio de definición de un conjunto ruta crítica p~th,,,~ está contenido dentro de dos puntos sucesivos de mapeado Mi y Dado el dominio temporal de definición (Si, de un conjunto ruta crítica p~th,,~, dos puntos de la curva de prestaciones son calculados como c(M~) = (A) y C(M+~) = ('j;+l, &+d. En un dominio de definición temporal (Si, Siti] de un conjunto ruta crítica p~th,,,~ se calcula la curva de prestaciones, con una resolución, como un problema de dimensionado sobre una red invariante. La red representa en el conjunto ruta crítica p~th,,,~ no necesita ser actualizada en el intervalo (Si, T:~]. Por lo tanto, cualquier mapeado n/rj dentro del dominio de definición del conjunto ruta + crítica p~th,,~ depende de un subconjunto invariante de la red G. La curva completa de prestaciones de un circuito de lógica combinacional 2 cdcuio de la Cuma se calcula mediante sucesivas optimizaciones de dimensionado sobre diferentes de Prest~iones rutas críticas. Inicialmente, en el mapeado M*, - el conjunto ruta crítica p~th,,~ representa un subconjunto de la red 2. Mientras que los sucesivos puntos de mapeado Mi se obtienen, la subred crece debido a que el conjunto ruta ~ríticapath,,,~ es actualizado al unir otras rutas. Cualquier método de optimización para resolver 4.6 es válido, tales como optimizadores heurísticos o combinados heurísticos y algorítmicos, Programación Lineal y No Lineal, entre otros. El problema de dimensionado de puerta es una transformación particular de + una red G en una net-list N de puertas. Dada una condición de carga a la salida, las restricciones del diseño son formuladas en términos de área activa frente a prestaciones de retardo. Para mapear en N, es necesaria una librería convexa objetivo. La librería convexa objetivo L contiene células full-custom para puertas lógicas. Puesto que el problema de dimensionado de puerta se establece sobre puertas Factor de Driver de tamaño variable, es conveniente definir la capacidad de tamaño de driver (factor 0) de la puerta. El tamaño de driver o factor 0 de una puerta crece linealmente con el ancho de sus transistores internos. Las capacidades internas de la puerta se incrementan 4.6 Curva de Prestaciones de un Circuito 137 linealmente también con el ancho de los transistores internos, y consecuentemente con el factor de tamaño de driver. En un mapeado Mi de en N, cada puerta del circuito posee un factor de tamaño de driver particular. Para una condición de carga de salida, el cálculo de la 2-tupla ('T, A) depende del retardo de propagación y del área activa de las puertas. En este apartado, se detallará el algoritmo propuesto (véase el algoritmo de la figura 4.4) para calcular la curva de prestaciones entera para el dimensionado de puerta con una técnica de Programación Lineal. La Programación Lineal es empleada como procedimiento de optimización para un punto simple para la + red completa G y el conjunto ruta crítica p~th,,~ - un subconjunto de tamaño variable de la red. Además, se presenta una primera descripción de la complejidad computacional del problema equivalente descrito en Programación Lineal en términos de número de variables y restricciones. 4.6.4. Modelo de Retardo y Área Activa de Puerta En esta aportación se emplea una función de retardo de propagación convexa, tal como el presentado en [91],[97]. La función emplea el peor caso de retardo de propagación de una puerta lógica, tanto respecto a sus entradas y con respecto a los Fuflc;ófl de Retdo Comexa tiempos de subida y bajada. El retardo total del circuito es determinado indiferente si las rutas críticas son sensibilizables [106]-[107]; pueden llegar a ser rutas falsas durante el proceso de optimización [107]-[108]; o son rutas falsas que pueden llegar a ser sensibles [107],[109],[110]. Se modela el retardo del circuito mediante la identificación de la ruta más larga en la red Booleana [lll]. A continuación se muestra la notación empleada en la descripción del modelado del retardo de puerta: retardo de puerta capacidad. M.R.C.M. Berkelaar, P.H.W. Buurman, and J.A.G. Jess. Computing the Entire Active AreaPower Consumption versus Delay Tradeoff Curve for Gate Sizing with a Piecewise Linear Simulator. IEEE Tmns. Comput.-Aided Des. Integi: Civcuits Syst., 15(11): 14241434,1996. M.R.C.M. Berkelaar and J.A.G. Jess. Gate Sizing in MOS Digital Circuits with Linear Programming. Pvoc. Euvopean Design Automation Con$, pages 217-221, March 1990. H.C. Chen and D.H.C. Du. Path Sensitization in Critical Path Problem. IEEE Tmns. Comput.-AidedDes. Integi: Civcuits Syst., 12(2): 196-207, 1993. H.R. Lin and T.T. Hwang. On Determining Sensitization Criterion in an Iterative Gate Sizing Process. IEEE Tmns. Comput.-AidedDes. Integi: Civcuits Syst., 18(2):231-238, 1999. H.R. Lin and T.T. Hwang. Dynamical Identification of Critical Paths for Iterative Gate Sizing. Pvoc ACMLEEE Int. Con$ Computev-Aided Design, pages 481-484, November 1994. H.C. Chen, D.H.C. Du, and L.R. Liu. Critical Path Selection for Performance Optimization. lEEE Tmns. Comput-AidedDes. Integi: Civcuits Syst., 12(2): 185-195, 1993. S.T. Huang, TM. Parng, and J.M. Shyu. A New Method of Identifying Critical Paths for Performance Optimization. Pvoc Euvopean Design Automation Con$, pages 455-459, February 1993. F. Chen-Lian, , and J. Wen-Ben. Timing Optimization by Gate Resizing and Critical Path Identification. IEEE Tmns. Comput.-Aided Des. Integi: Civcuits Syst., 14(2):201-217, 1995. 138 Optimización del Retardo k: constante. B: factor de velocidad9. Un modelo de retardo, básico y ampliamente utilizado es: Donde Cwi,, es la capacidad de cableado y Ci es la capacidad conectada a la puerta i. La capacidad conectada a la puerta Ci crece linealmente con el tamaño del factor de velocidad Bi. Ci,int es la capacidad interna de una puerta i con tamaño unitario en su factor de velocidad 0,. El factor de velocidad de una puerta está relacionado con el retardo de puerta T~~~, tal como sigue: A mayor factor de velocidad menor es el retardo de puerta T~~~,. De hecho, el retardo interno de puerta T~~~~,~~~ es casi constante porque las capacidades internas de la puerta crecen linealmente con el factor de velocidad Bgat,. Sin embargo, el término k x Cload/Bgate decrece con ese mismo factor. El modelo de retardo de puerta se obtiene mediante la combinación de las ecuaciones 4.15 y 4.16. Como se muestra en la ecuación 4.16, el modelo de retardo de puerta es no lineal. Con el objeto de adaptar este modelo a una técnica de Programación Lineal, MO~~IO NO lineal la función ha de ser linealizada acotando el error en tomo al punto de evaluación. En la referencia [91] se muestra una forma de realizar la linealización. En la figura 4.5 se muestra la linealización para una puerta NAND de dos entradas sobre tecnología CMOS de 0'18pm10 bajo varias condiciones de carga y con su linealización en 2 tramos. El área activa de una puerta crece linealmente con su tamaño de driver. El área Área Activa activa total de un circuito es la sumatoria de área activa de todas las puertas en del circuito, como sigue: Donde ui es una constante de proporcionalidad entre el área activa y el factor de velocidad Bi para la puerta i, 'Traducción directa del término anglosajón speedfactov. 'OTSMC Logic 0'18um Process 1'8V Supply Voltage Generic 11 Spice [91] M.R.C.M. Berkelaar, P.H.W. Buurman, and J.A.G. Jess. Computing the Entire Active AreaPower Consumption versus Delay Tradeoff Cwe for Gate Sizing with a Piecewise Linear Simulator. IEEE Tmns. Comput-Aided Des. Integi: Civcuits Syst., 15(11):14241434,1996. 4.6 Curva de Prestaciones de un Circuito 139 Figura 4.5: Curva de retardo de unaNAND bajo diferentes cargas frente al factor de velocidad. ,. D D N .- L m c L" > .- 4.6.5. Curva de Prestaciones empleando Programación Lineal 3 c n a - Se emplea una técnica de Programación Lineal como optimización de un pun- .- - e m to único de la función multiobjetivo presentada en la ecuación 4.6. La función o C1 objetivo de área activa es un modelo lineal del factor de velocidad 0, como fue ModelodeRetdo 5 No lineal 3 presentado en la ecuación 4.17. Sin embargo, el modelo completo de retardo es L 0 * una función no lineal de o,,,, m n N .- - m Este modelo de retardo no lineal es linealizado con la precisión deseada mediante un ajuste lineal a tramos para convertirse en: Consecuentemente, cuando la Programación Lineal minimice la función multiobjetivo caA + CST, la siguiente restricción a añadir es a la ecuación 4.6, para punción objetivo cada puerta del circuito: i Los n modelos de retardo linealizados Limite del factor de velocidad 140 Optimización del Retardo - Donde y o,,, son el limite inferior y superior del factor de velocidad, - respectivamente. Definición del tiempo de propagación El algoritmo propuesto CtradeOff () es reescrito con el objeto de embeber la Algoritmo de Cálculo de la Cuma de técnica de Programación Lineal (LP) (véase el algoritmo LPCtradeoff () en la fiPrestaciones gura 4.6). Además y con el propósito de realizar comparativas, se presenta en la figura 4.7 el algoritmo LPSizingA() que realiza la formulación en Programación Lineal del problema de dimensionado de puerta. En ambos algoritmos, se precalcula una aproximación lineal a tramos de la formulación no lineal del retardo de propagación. 4.6.6. Complejidad de la Optimización El esfuerzo computacional de la optimización se obtiene cuantificando el número de variables necesarias para calcular cada punto de la curva de prestaciones. Se supone que la complejidad de la optimización está directamente relacionada con el tamaño del problema de optimización resuelto mediante Programación Lineal, esto es, el número de variables y restricciones. Para una red con V vértices (uno por cada puerta) y E lados (uno por cada Esfueno conexión) el tamaño del problema resuelto mediante técnicas de Programación Computocional Lineal es conocido. El número de restricciones es E + (3+n) V+3, como sigue: i 1 para expresar el retardo total 'T, i 1 para limitar el retardo total 'T, i 1 para expresar el área activa total $I, n del modelo lineal de propagación del retardo por vértice (nV): 2 de la limitación del factor de velocidad por vértice (2V): 1 para limitar la definición de tiempo de propagación por vértice (V), y 1 por cada relación con un predecesor (E). En todos los circuitos sintetizados el número de entradas es uno o dos y la Sintesis de Cinuitos carga se limita a tres, así que E < k V 1, donde k > 1, y por tanto el orden es lineal con el número de puertas ((3 + n + k) V + 3). Para el conjunto ruta critica p~th,,~, en vez de limitar el retardo total 'T al máximo retardo de las salidas primarias, éste es restringido al retardo de la rutas dependientes del conjunto ruta critica. Además, el limite más bajo del retardo total es el retardo máximo de las rutas independientes. Entonces, el número de restricciones distintas es como sigue: n por modelo lineal de propagación del retardo por vértice de path,,i (< n V), 2 de la limitación del factor de velocidad a cada vértice de path,,i (< 2 V), 4.6 Curva de Prestaciones de un Circuito 141 Lpctmdeoff given a 2 = (V, E,.); + map G to LA, - M~ = M*; - obtain the critica1 path set path,,j; do update ?; = T(p~th,,,~); minimise caA + cTI of path,,i; s.t. V gate t p~th,,,~: The n modelos de propagación lineales itf anmt(gate) Limitación del factor de velocidad Definiciones de los tiempos de propagación s.t. Máximo tiempo de propagación = T(p~th,,,~); Upd~tePath,,~(); while 'j; # < end LPCtradeoff 0 Figura 4.6: Algoritmo de generación de la curva completa de prestaciones empleando la técnica de Programación Lineal.