Gráfico de restricciones (diseño)

En algunas tareas de diseño de trazado de circuitos integrados, surge la necesidad de optimizar la colocación de objetos que no se superponen en el plano. En general, este problema es extremadamente complejo, y para abordarlo con algoritmos informáticos, se realizan ciertas suposiciones sobre las colocaciones admisibles y las operaciones permitidas en las modificaciones de colocación. Los grafos de restricciones capturan las limitaciones de los movimientos relativos de los objetos colocados en el plano. Estos grafos, si bien comparten una idea común, tienen definiciones diferentes según la tarea de diseño o el modelo específico.

En el diseño de la distribución física , el modelo de la distribución de un circuito integrado es un conjunto de rectángulos isotéticos llamados "bloques" dentro de un rectángulo más grande llamado "límite" (por ejemplo, " límite del chip ", " límite de la celda ").

Una posible definición de grafos de restricciones es la siguiente. El grafo de restricciones para un plano de planta dado es un grafo dirigido cuyo conjunto de vértices es el conjunto de bloques del plano de planta y existe una arista del bloque b1 al b2 (llamada restricción horizontal) si b1 está completamente a la izquierda de b2 y existe una arista del bloque b1 al b2 (llamada restricción vertical) si b1 está completamente debajo de b2.

Si solo se consideran las restricciones horizontales, se obtiene el grafo de restricciones horizontales . Si solo se consideran las restricciones verticales, se obtiene el grafo de restricciones verticales .

Según esta definición, el grafo de restricciones puede tener tantos como${\displaystyle O(n^{2})}$bordes, donde n es el número de bloques. Por lo tanto, se consideran otros grafos de restricciones menos densos. El grafo de visibilidad horizontal es un grafo de restricciones horizontales en el que la restricción horizontal entre dos bloques existe solo si hay un segmento de línea horizontal que conecta los dos bloques y no interseca ningún otro bloque. En otras palabras, un bloque es un "obstáculo inmediato" potencial para mover otro horizontalmente. El grafo de visibilidad vertical se define de manera similar.

El enrutamiento de canales es el problema de enrutar un conjunto de redes N que tienen terminales fijos en dos lados opuestos de un rectángulo ("canal"). En este contexto, el grafo de restricción horizontal es el grafo no dirigido con conjunto de vértices N , y dos redes están conectadas por una arista si y solo si los segmentos horizontales del enrutamiento deben superponerse. En el ejemplo dado, solo las redes 5 y 6 no tienen una restricción horizontal entre ellas. El grafo de restricción vertical es el grafo dirigido con conjunto de vértices N , y dos redes están conectadas por una arista si y solo si hay dos pines de redes diferentes en la misma línea vertical y la arista está dirigida desde la red con el pin en el borde superior del canal. Esta dirección significa que esta red debe enrutarse en una pista horizontal por encima de las pistas horizontales de la segunda red. En el ejemplo dado, solo las redes 1 y 3 tienen una restricción vertical. ^{[ 1 ]}