Download Estructuras de datos para manipulación y representación de

Índice (I)
9 Introducción
9 Operaciones típicas
9 Estructuras de datos
Estructuras de datos para
manipulación y representación de
trazados VLSI
ƒ
ƒ
ƒ
ƒ
DASE
Curso 2006/2007
Compartimentos (bins)
Árboles cuaternarios
Árboles de dimensión K
Corner stitching
9 Basado en gran medida en las transparencias
del Prof R. Rutenbar, CMU (©Rutenbar)
DASE
DASE
Introducción
2
Diseño VLSI
9 Un circuito integrado incluye mucha información
Algunos números:
ƒ 10-100 M trts
ƒ ~10-20 geometrías por dispositivo
ƒ 0,1- 1 billón (americano) de rectángulos
ƒ Previsión año 2010 [1]:
o 100 M $ coste diseño para ciertos chips VLSI (SOCs)
ƒ Coste máscara 180 -130 nm [1]: 0,5 – 1M $
ƒ Pentium IV Northwood (2003) (130nm): 55 M TRTs
ƒ Pentium 5 Prescott (2004) (90nm): 125 M TRTs
[1] Kurt Keutzer et al. “From ASIC to ASIP: The
Next Design Discontinuity”. ICCD'02, 2002
DASE
©Rutenbar 3
DASE
4
º
DASE
5
DASE
6
1
Operaciones básicas
Dado un punto
(x,y), ¿qué hay?
Estructuras de datos: búsquedas
ƒ Dado un punto, ¿qué hay ahí?
ƒ Dada una región, ¿que está incluido?
Dada una región
¿qué hay?
9 Aplicaciones
ƒ
ƒ
ƒ
ƒ
Comprobación DRC
Impresión de máscaras
Extracción de circuitos eléctricos desde trazado
Explorar alrededor de un dispositivo concreto
9 Nota: no se borra ni se inserta nada
9 Operaciones posibles:
ƒ Búsqueda (query)
ƒ Inserción
ƒ Borrado
©Rutenbar 7
DASE
DASE
Tipos de estructuras de datos
Estructuras de datos: modificación de trazado
9 Añadir o borrar geometrías
9 Lista enlazada
ƒ insertar/borrar rectángulos
ƒ simple, pero lenta
9 Aplicaciones
9 Compartimentos (bins)
ƒ Edición de trazado (Cadence Virtuoso)
ƒ Rutado detallado o global
ƒ Legalización de colocación (refinamiento)
ƒ sencillo, utilizado
9 Árboles cuaternarios
ƒ muy utilizado
9 Observaciones
9 Árboles de dimensión-k
ƒ Dependiendo de la estructura puede ser fácil borrar
y difícil insertar o viceversa
ƒ Hay que adaptar la estructura de datos a la
aplicación
DASE
8
ƒ buena complejidad, pero limitado
9 Corner stitching
ƒ Bueno para edición
9
DASE
10
1. Listas enlazadas
2. Compartimentos
9 Válido sólo si hay pocos elementos
9 Complejidad para N rectángulos:
9 Idea:
ƒ Descomponer la superficie del chip en compartimentos
(bins o buckets)
ƒ En cada uno lista enlazada con sus rectángulos
ƒ Búsqueda: O(N)
ƒ Inserción: O(N)
ƒ Borrado: O(N)
DASE
11
DASE
©Rutenbar 12
2
Compartimentos: búsquedas
Compartimentos: funcionamiento
9 Utiliza un puntero al rectángulo desde cada
compartimento que lo toca
9 Rectángulos grandes: recorrer muchos bins
9 Importante buena granularidad
©Rutenbar 13
DASE
Compartimentos: granularidad
9 Cómo hacemos de grandes los compartimentos?
ƒ Si A0=tamaño objeto medio y Ab=tamaño de bin
©Rutenbar 14
DASE
Resumen de compartimentos
9 Buena estructura si los objetos son del mismo
tamaño y están bien distribuidos
9 Si los objetos no están bien distribuidos:
queremos dividirlo de forma dinámica
9 Si hay muchos bins pequeños
ƒ Memoria grande ⇒ tiempos altos de inserción y
borrado
ƒ Búsquedas muy rápidas (pocos objetos por bin)
©Rutenbar 15
DASE
©Rutenbar 16
DASE
Árboles Cuaternarios (Quad Trees)
9 Problemas de los compartimentos:
Árbol cuaternario
9 Estructura de datos con cuatro hijos:
ƒ Datos repartidos de forma no uniforme
ƒ Si hay regiones muy densas, la búsqueda en esa región es muy
lenta al tener listas largas por bin
ƒ Hay que dividir el espacio de forma dinámica
Dada un región (quad) dividirla
en cuatro regiones iguales
Reglas:
Lista de geometrías
cortadas por la sección
Cada hijo es un árbol cuaternario
ƒ Objetos cortados por las secciones Ö en la lista del quad
ƒ Objetos íntegros en cuadrante Ö árbol hijo
DASE
©Rutenbar 17
DASE
©Rutenbar 18
3
Construcción de árboles cuaternarios
Construcción de árboles cuaternarios
9 Objetos que caben en un cuadrante completamente:
ƒ Pueden estar en las regiones UL, UR, LL, LR
ƒ Pasan al árbol cuaternario correspondiente
ƒ Se repite la recursión
9 Los objetos que
aparecen en las
secciones
ƒ No pueden estar en
las regiones UL, UR,
LL, LR
ƒ Por ello aparecen en
las listas de las
secciones
©Rutenbar 19
DASE
DASE
Ejemplo
Ejemplo
UL
UR
DASE
21
Árbol cuaternario: ¿Qué hay?
DASE
©Rutenbar 22
Árbol cuaternario: búsqueda de región
9 Supongamos que la región cae en secciones:
9 Sólo bajar en la jerarquía del árbol
ƒ Primero miramos la lista de la sección
ƒ Entonces se trocea la región en cuatro sub-regiones
y se pasan abajo en la jerarquía, recursivamente
ƒ Llegar a la región con el x,y buscado
ƒ ¿Qúe hay? Mirar la lista de rectángulos que contiene
DASE
20
©Rutenbar 23
DASE
24
4
Búsquedas en árbol cuaternario
9 Búsqueda de región
Árbol cuaternario: inserción y borrado
Buscamos objetos cerca de 2
Inserción
Borrado
Bajar por el
árbol hasta el
cuadrante
adecuado.
Crearlo si es
necesario
Borrar el objeto
de la lista y el
hijo del árbol si
es necesario
Tenemos que comprobar:
11, 1, 2, 3, 4, 7
©Rutenbar 25
DASE
DASE
Árbol cuaternario: estructuras de datos
9 Tipos de árboles (función de número de rectángulos
por hoja)
ƒ Uno
Ö
ƒ No menos de K Ö
Árbol cuaternario perfecto
Búsqueda sencilla
Árbol enorme (no realista)
Árbol cuaternario adaptativo
Árboles menores pero con listas
mayores
26
Árboles cuaternarios: resumen
9 Ventajas
ƒ Búsqueda, inserción y borrado sencillos
ƒ Complejidad: O(logN)
ƒ Estructuras de datos sencillas
9 Problemas:
ƒ Con distribuciones de geometrías poco uniformes el
árbol está muy desequilibrado Ö búsquedas lentas
9 ¿Cómo de pequeño puede ser un cuadrante?
ƒ No menos de área A Ö Lista enlazada de objetos en las
hojas
DASE
27
DASE
28
Referencia importantes
9 J. Rosenberg. “Geographical data structures :
A Compared Study of Data Structures
Supporting Region Queries," IEEE Trans.
Computer-Aided Design, Vol. CAD-4, No. 1,
Jan. 1985, pp. 53-67.
DASE
©Rutenbar 29
5