Download DRC - LSI

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