Detección de patrones geométricos mediante la extracción de signature (geometric pattern detection using signature extraction)

Abstract

En la evolución constante de los procesos de manufactura de circuitos, la detección de configuraciones conflictivas se ha convertido en una tarea crucial en el proceso de diseño y producción. Estas configuraciones pueden provocar fallos en el circuito pues son propensas a sufrir distorsiones en las etapas de fabricación, ya sea por efectos de estrés de materiales, baja tolerancia a procesos de impresión como la fotolitografía, entre otros. La investigación en torno a esta problemática ha dado lugar a diferentes enfoques y técnicas que se utilizan para obtener soluciones eficaces que permitan a los diseñadores, ya sea a evitar el uso de configuraciones conflictivas, como a corregirlas o eliminarlas cuando aparecen en un diseño tras el uso de herramientas automatizadas. El problema de fondo es que estas técnicas, que suponen un coste adicional en el proceso de diseño, no siempre son eficaces, sobre todo desde el punto de vista de tiempos de ejecución. El siguiente trabajo de tesis de magister amplía el trabajo realizado para la obtenci ón de mi título profesional de Ingeniero Civil Informático. En dicho trabajo, se extrae cierta información relevante de regiones rectangulares de un diseño o layout. Esta información, llamada signature o firma de la región, es posteriormente utilizadapara decidir si una región contiene o no una cierta configuración que se desee eliminar. Típicamente, estas configuraciones corresponden a patrones geométricos que, dados los procesos de manufactura, tienen una alta probabilidad de dar origen a una falla, conocida como hotspot. En otras palabras, un hotspot es una configuración de componentes electrónicos que provoca un mal funcionamiento del circuito. De forma adicional, este trabajo refina el trabajo anterior respecto a la estructura de datos utilizada, redefine la signature para patrones que tengan una dimensión distinta a la ventana de análisis, y realiza una evaluación exhaustiva de tiempo y calidad de los resultados. El objetivo principal de este método es reducir los tiempos de ejecución necesarios en las etapas de detección de hotspots al disminuir las porciones del diseño que deben ser analizadas usando técnicas más complejas.Para ello se utilizan algoritmos que transforman representaciones geométricas expresadas como reglas espaciales a representaciones expresadas como grafos dirigidos, los que son finalmente utilizados para obtener representaciones vectoriales de dichas representaciones geométricas. Estas representaciones vectoriales, denominadas la signature de un patrón geométrico, son almacenadas en estructuras indexadas para permitir posteriores búsquedas en base a índices. El trabajo presenta evaluaciones experimentales de diversas estructuras indexadas basadas en arboles binarios de búsqueda, tablas hash, y combinaciones de ambos tipos. Los experimentos muestran tiempos de ejecución que permiten disminuir los tiempos de ejecución que actualmente se requieren para la detección de patrones en diseños de circuitos integrados, así como uso de memoria que permiten la ejecución del proceso en computadores personales. Las estructuras que utilizan una combinación de estructuras indexadas mostraron ser la que ofrecen la mejor relación entre tiempos de ejecución y memoria requerida.