Download DRC - LSI
Document related concepts
no text concepts found
Transcript
Manipulación de trazados Contenidos ¿Qué es DRC? ¿Por qué es necesario? DRC basado en polígonos (algoritmos scan-line) DRC bitmap (raster) Extracción de conectividad Comprobación de las reglas de diseño (DRC) Marisa López Vallejo DASE 2005-2006 1 2 Introducción ¿Qué es el DRC? 9 Verificación de la legalidad del trazado DISEÑO FÍSICO 9 Objetivos Máscaras VERIFICACIÓN sigue las reglas de diseño anchuras y espaciado mínimos extensiones, solapamientos reglas dependientes del circuito DRC Extracción Verif. Temp verificar que se cumplen todas las reglas destacar zonas con violaciones y por qué minimizar tiempo de CPU y memoria DRC integrado + editor de trazado o utilizar estructuras de datos disponibles o comprobar incrementalmente A Smin = 3 si VAB < 2.5V, Smin = 4 si no B 3 4 ¿Por qué es necesario DRC? Representación de geometrías 9 Límite de resolución en fabricación sólo anchuras de línea y separaciones por encima de Wmin y Smin límites de fotolitografía, óptica, etc. 9 Polígonos rectángulos como caso especial representación más natural especificación simple de la mayoría de las reglas de diseño vs. 9 Límite de alineamiento en fabricación 9 Raster problema con sensores 9 Perturbaciones en fabricación línea sobre/bajo ataque variaciones en la temperatura de horno partículas con la resolución de las reglas de diseño memory hog vs. 9 Tile vs. 01 11 01 00 10 00 corner-stitched rectángulos, trapezoides bueno para análisis incremental conexiones locales ya almacenadas vs. 9 Reglas de diseño del trazado se deben seguir para alto rendimiento de fabricación compromiso entre rendimiento y densidad las reglas son por naturaleza locales 00 10 00 9 Arista vs. requiere información de conectividad memoria mínima 5 6 Operaciones posibles en trazados 9 Operaciones booleanas para expresar las reglas de diseño Separación Met-Met > 3 lambda o MetI = inflate(Met, 1.5) o Error = MetI ∩ MetI A A ∪B Operaciones posibles en trazados A - B A∩ B B Características: Puede considerar ángulos agudos Velocidad 9 Operaciones de tolerancias Espacio entre capas Mínima anchura Overlaps 9 Extracción de conectividad o O(nm) operación de polígonos de n x m Memoria o múltiples estructuras auxiliares por arista Debe unir polígonos conectados eléctricamente Se restringen comprobaciones a polígonos vecinos o evitar comprobaciones para n polígonos O(n2) 7 Problemática del DRC 8 Algoritmos de Scan-line 9 Buscar intersección de aristas 9 Grandes trazados ⇒ 107 – 109 polígonos 9 Memoria: 106 cuadrados ⇒ 16Mbytes datos 9 Procedimiento O(nm) para polígonos de aristas n y m utiliza vecindario para reducir el caso medio (nlogn) divide aristas en las intersecciones 9 Trabaja las aristas No tiene sentido comprobar TODOS con TODOS Se explota la localidad de las máscaras mantener las aristas externas del polígono resultante utilizar sentido flechas para calcular el interior/exterior o 4 ⇒ Relleno o 3 ⇒ Vacío 9 ¿Cómo? Algoritmos de scan-line Algoritmos de bitmap +1 -1 +1 sum = +1 => interno caso-peor 9 Scan-line: ideas básicas 10 Scan-line: ideas básicas 9 Las aristas se almacenan de forma ordenada 9 Procedimiento: Primero en x Si tienen misma x, se ordenan en y Una línea de barrido (scan-line) horizontal o vertical recorre el trazado b c a f Se consideran en un instante sólo las aristas que toquen la línea de barrido Se deben considerar aristas nuevas tras intersección completa {a,b,d,e,f,h,c,g} d g e h 11 12 Terminología Algoritmo de Lauther Estructuras de datos arista heredada arista terminal Ficheros Ficheros Ficheros de de de aristas aristas aristas arista inicial cola Observaciones útiles El barrido no es contínuo: N, N+1 Scan-line = estructura de datos con aristas ordenadas No es necesario representar aristas paralelas sl No hay que utilizar aristas completamente intersectadas: se extraen. Old scan-line New scan-line 13 14 Lauther: diagrama de flujo Algoritmo de Lauther Inicializar EDGE_FILES con los arcos ordenados en X e Y; COLA ← arista(s) de menor X de cada EDGE_FILE; Máscara Encontrar y ordenar bordes X0=Xizq de primera arista en COLA OLD_SCANLINE = empty; /* inicialización del scanline */ INIT: WHILE (aristas en COLA con Xizq =X0) = { NEW_SCANLINE ← arista; Coger nueva arista de EDGE_FILE y meterla en COLA;} /* cálculo de Y para aristas heredadas */ FOR (arista en OLD_SCANLINE) { Calcular su Y en X =X0 } /* juntar y ordenar aristas de OLD S.L. y NEW S.L.*/ merge (sort) MERGED_SCANLINE ← OLD_SCANLINE && NEW_SCANLINE /* split */ WHILE (merging) { IF (2 aristas adyacentes && 1 arista nueva) { Comprueba intersección; IF (intersección) { Divide: (Izq. → MERGED_SCANLINE) (Dcha. → COLA) } } } Almacenam. datos Ficheros de bordes Operaciones Cola New S.L. Old S.L. Merge edges and split Right split edges Remaining edges & Left split edges Merged edges & Left split edges Merged S.L. Delete edges and split Right split edges Operaciones booleanas Bordes de salida 15 16 Lauther (cont) Operaciones_booleanas (); Lauther (cont) /* lo veremos más adelante */ OPERACIONES BOOLEANAS (entre 2 capas distintas) /* borrar aristas terminales */ FOR (arista in MERGED_SCANLINE) { IF (arista terminal en X0) Borrar_arista (MERGED_SCANLINE); IF (2 aristas adyacentes tras borrar) { Comprueba_intersección; IF (intersección) { Divide: (Izq. → MERGED_SCANLINE) (Dcha. → COLA) } } } OLD_SCANLINE ← MERGED_SCANLINE; S.L. = Lista edges S.L., ordenados en ´y´ OLD_RESULT= False; /* resultado anterior */ NEW_RESULT= False; /* resultado actual */ count [layer_1]=0; /* opacidad de la capa */ count [layer_2]=0; FOR (aristas en S.L., siguiendo orden de arriba abajo){ IF (forward layer_1) count [layer_1]++; ELSE IF (backward layer_1) count [layer_1]--; ELSE IF (forward layer_2) count [layer_2]++; ELSE IF (backward layer_2) count [layer_2]--; /* Buscamos el nuevo punto x del scanline */ X0 = ∞; FOR (arista en OLD_SCANLINE) { X0= mínimo { X0, máx_x(arista)} /* mín. borde dcho */ } X0= mínimo { X0, min_x(primera arista de COLA)}; NEW_SCANLINE=empty; GOTO INIT; NEW_RESULT= ( (count[layer_1]>0) OP (count[layer_2]>0) ); IF (NEW_RESULT ≠ OLD_RESULT) ⇒ arista buena OLD_RESULT=NEW_RESULT; } 17 18 Lauther (cont) Análisis de conectividad FASE DE RENOMBRADO (Extracción de conectividad) 9 Objetivo: enumeración de regiones por zonas eléctricas 9 Se basa en el algoritmo de scan-line en dos fases: Entrada = fichero temporal de control; Datos = finalnumb[1:m]; /* array con números finales */ region_count = 0; /* cuenta de regiones */ Salida = Bordes con los números de las regiones; WHILE (quedan bordes en la entrada) { Leer en orden inverso el fichero de control; IF (<end of i>) { regioncount ++; finalnumb [i] = regioncount; } ELSE IF (<merge i→j>) { /* Unificación de regiones: cambiar los identificadores de región iguales a finalnumb[i] por el identificador indicado en finalnumb[j] */ Fase de barrido Fase de renombrado tmp=finalnumb[i]; FOR (k=1 to m) { IF (finalnumb[k]==tmp) finalnumb[k]=finalnumb[j]; } } 19 } 20 Fase de barrido Ejemplo conectividad 9 S={conjuntos de líneas (s).} b s representa una región diferente que se va encontrando 9 Reglas para detección de regiones por S.L. e Añadir nuevas aristas s∈S que bordeen la misma región Si hay intersección de aristas de distinto conjunto: unión de conjuntos Arista no activa en S.L: se elimina del conjunto Conjunto vacío ⇒al fichero de control a d c 1 <a from 1> 2 g f 3 i h 4 5 6 7 21 Fase de renombrado 22 Bitmap/Raster DRC 9 Ventana sobre el bitmap Entrada = fichero temporal Datos = finalnum[1:m] // array con nº finales regioncount=0; // cuenta de regiones Salida = aristas numeradas por regiones d x d para la regla máxima con d unidades tabla de lookup de la ventana d x d o aciertos/fallos ventana o tablas de precomputación un bit por capa WHILE (queden aristas de entrada) { leer en orden inverso el fichero; IF (<end of i>) { regioncount++; finalnum[i] = regioncount; } ELSE IF (<merge i->j>) finalnum[i] = finalnum[j]; ELSE // (<e from i>) write e marcado con finalnum[i]; o combinaciones de capas a través de operaciones de bit o muy rápido 9 A tener en cuenta reglas de diseño de grano fino => bitmap grande o tiempo E/S, mucha memoria o tiempo “rasterization” o se puede usar scan line para seleccionar polígonos que convertir en bitmap d grande => tablas grandes limitado a geometrías Manhattan funciona mejor con reglas de diseño sencillas 23 zona 2 ok 24 Bitmap DRC Neighborhood Checking 9 Design rules are local - only check neighborhood 9 Algoritmo objects spread evenly across chip o number of neighbors roughly constant sort polygons in y and x by upper-left vertex while unrasterized polygons below scanline { move scanline down to next unrasterized polygon or polygon section for each polygon intersecting scanline { rasterize polygon from scanline to scanline + max design rule for each raster pixel in scan line { for each design rule window { check rule report failures } } } 9 Bin sorting divide chip into c x c bins bin points to all objects that intersect it O(1) time to check nearby bins for objects 9 Quad tree search tree - log(n) time to find neighbors 9 Scan line only hold objects within design rule of scan line cutline on n-object chip hits ~sqrt(n) objects n*log(n) time to scan all objects 9 Corner-stitching inherent neighborhood relationships 25 26