Enrutamiento (automatización del diseño electrónico)

En el diseño electrónico , el enrutamiento de cables , comúnmente llamado simplemente enrutamiento , es un paso en el diseño de placas de circuito impreso (PCB) y circuitos integrados (CI). Se basa en un paso previo, llamado colocación , que determina la ubicación de cada elemento activo de un CI o componente en una PCB. Después de la colocación, el paso de enrutamiento agrega los cables necesarios para conectar correctamente los componentes colocados, respetando todas las reglas de diseño del CI. En conjunto, los pasos de colocación y enrutamiento del diseño de CI se conocen como colocación y enrutamiento .

La tarea de todos los enrutadores es la misma. Se les proporcionan polígonos preexistentes formados por pines (también llamados terminales) en celdas, algunos obstáculos donde no se pueden enrutar los cables y, opcionalmente, cableado preexistente llamado prerutas. Cada pin está asociado a una red , generalmente por nombre o número. La tarea principal del enrutador es crear geometrías de tal manera que todos los terminales asignados a la misma red estén conectados, ningún terminal asignado a redes diferentes esté conectado y se cumplan todas las reglas de diseño. Un enrutador puede fallar al no conectar terminales que deberían estar conectados (circuito abierto), al conectar erróneamente dos terminales que no deberían estar conectados (cortocircuito) o al crear una violación de las reglas de diseño. Además de conectar correctamente las redes, también se espera que los enrutadores se aseguren de que el diseño cumpla con los requisitos de temporización, no tenga problemas de diafonía , cumpla con los requisitos de densidad de metal, no sufra efectos de antena , etc. Esta larga lista de objetivos, a menudo contradictorios, es lo que hace que el enrutamiento sea extremadamente difícil.

Se sabe que casi todos los problemas relacionados con el enrutamiento son intratables . El problema de enrutamiento más simple, llamado problema del árbol de Steiner , que consiste en encontrar la ruta más corta para una red en una capa sin obstáculos ni reglas de diseño, es NP-completo , tanto en el caso en que se permiten todos los ángulos como si el enrutamiento se restringe solo a cables horizontales y verticales. ^{[ 1 ]} También se ha demostrado que las variantes de enrutamiento de canales son NP-completas, ^{[ 2 ]} así como el enrutamiento que reduce la diafonía , el número de vías , etc. Incluso antes de que se demostrara que los problemas de enrutamiento eran NP-completos, la dificultad de encontrar soluciones óptimas era evidente. Por lo tanto, casi todos los algoritmos se basan en heurísticas , que no buscan un óptimo, sino una solución que sea "suficientemente buena". ^{[ 3 ]}

Las reglas de diseño a veces varían considerablemente de una capa a otra. En los circuitos integrados con múltiples capas metálicas, por ejemplo, el ancho y el espaciado permitidos en las capas inferiores pueden ser cuatro o más veces menores que los permitidos en las capas superiores. Esto introduce muchas complicaciones adicionales que no se presentan en los enrutadores para otras aplicaciones, como el diseño de placas de circuito impreso o módulos multichip . Surgen dificultades particulares si las reglas no son múltiplos simples entre sí y cuando las vías deben atravesar capas con reglas diferentes.

Los primeros tipos de enrutadores EDA eran los "enrutadores manuales": el diseñador hacía clic con el ratón en el extremo de cada segmento de línea de cada red. El software moderno de diseño de PCB suele proporcionar "enrutadores interactivos": el diseñador selecciona una almohadilla y hace clic en algunos puntos para indicar a la herramienta EDA la ruta a seguir, y esta intenta colocar los cables lo más cerca posible de esa ruta sin infringir las reglas de diseño (DRC). Algunos enrutadores interactivos más avanzados incorporan funciones de "desplazamiento" (también conocidas como "movimiento automático"); la herramienta EDA desplaza otras redes, si es posible, para colocar un nuevo cable donde el diseñador lo desee y evitar infringir las reglas de diseño. El software moderno de diseño de PCB también suele proporcionar "enrutadores automáticos" que enrutan todas las conexiones restantes sin intervención humana.

Los circuitos integrados modernos suelen utilizar enrutamiento totalmente automático, ya que la cantidad de conexiones puede ser excesiva para enrutarlas manualmente. Si el enrutamiento automático no proporciona una solución completa, una solución habitual consiste en modificar la disposición de los componentes para dejar más espacio para las rutas, en lugar de intentar completar manualmente las rutas faltantes.

• Enrutador de laberinto ^{[ 4 ] [ 5 ]}
  • Enrutador Lee ^{[ 6 ] [ 4 ] [ 7 ]} El algoritmo de búsqueda A* se usa comúnmente en enrutadores de laberinto y Lee.
  • Enrutador Hadlock ^{[ 8 ]}
  • Enrutador de inundación ^{[ 4 ]}
• Enrutador con sonda de línea
  • Enrutador Mikami–Tahuchi ^{[ 9 ]}
  • Enrutador Hightower ^{[ 10 ] [ 7 ] [ 11 ] [ 4 ]}
• Enrutador de patrones ^{[ 7 ] [ 11 ]}
• Enrutador de canal ^{[ 12 ] [ 11 ] [ 7 ] [ 13 ]}
  • Enrutador Switchbox ^{[ 13 ]}
  • Enrutador fluvial ^{[ 13 ]}
  • Enrutador de espinas y puntadas ^{[ 14 ]}
• Enrutador sin cuadrícula ^{[ 15 ] [ 11 ] [ 7 ] [ 16 ]}
  • Enrutador de área
  • Enrutador basado en teoría de grafos ^{[ 17 ]}
    • Enrutador Bloodhound ^{[ 18 ] [ 19 ] [ 20 ]} ( CADSTAR de Racal-Redac / Zuken )
    • Specctra ^{[ 20 ]} (también conocido como Allegro PCB Router ) (sin rejilla desde la versión 10)
  • Enrutador topológico
    • FreeStyle Router (también conocido como SpeedWay , un enrutador automático basado en MS-DOS para P-CAD )
    • TopoR (un enrutador automático basado en Windows , también utilizado en el diseño Delta de Eremex )
    • Toporouter (enrutador de código abierto de Anthony Blake en PCB de la suite gEDA )
    • TopRouter (el preenrutador topológico en EAGLE 7.0 y versiones posteriores de CadSoft / Autodesk )
    • SimplifyPCB (un enrutador topológico centrado en el enrutamiento de paquetes con resultados de enrutamiento manual) ^{[ 21 ]}

Muchos enrutadores ejecutan el siguiente algoritmo general:

• Primero, determine una ruta aproximada para cada red, a menudo mediante el enrutamiento en una cuadrícula gruesa. Este paso se denomina ^enrutamiento global [ ^{22 ]} y puede incluir opcionalmente la asignación de capas. El enrutamiento global limita el tamaño y la complejidad de los pasos de enrutamiento detallados posteriores, que pueden realizarse cuadrícula por cuadrícula.

Para el enrutamiento detallado, la técnica más común es deshacer y redirigir, también conocida como deshacer y reintentar : ^{[ 4 ]}

• Seleccione la secuencia en la que se deben enrutar las redes.
• Enruta cada red en secuencia
• Si no se pueden enrutar todas las redes correctamente, aplique alguno de los diversos métodos de "limpieza", en los que se eliminan los enrutamientos seleccionados, se cambia el orden de las redes restantes que se van a enrutar y se vuelven a intentar los enrutamientos restantes.

Este proceso se repite hasta que todas las redes estén enrutadas o el programa (o el usuario) se dé por vencido.

Un enfoque alternativo consiste en tratar los cortocircuitos, las violaciones de las reglas de diseño, las obstrucciones, etc., de forma similar al exceso de longitud de cable; es decir, como costes finitos que deben reducirse (inicialmente) en lugar de como absolutos que deben evitarse. Este método de enrutamiento de "mejora iterativa" de múltiples pasadas ^{[ 23 ]} se describe mediante el siguiente algoritmo:

• Para cada una de las varias pasadas iterativas:
• Prescribir o ajustar los parámetros de ponderación de una "función objetivo" (con un valor de parámetro de ponderación para cada unidad de longitud de cable sobrante y para cada tipo de infracción). Por ejemplo, en la primera pasada, la longitud de cable sobrante suele tener un coste elevado, mientras que las infracciones de diseño, como cortocircuitos, conexiones adyacentes, etc., tienen un coste bajo. En pasadas posteriores, se modifica el orden relativo de los costes para que las infracciones tengan un coste elevado o estén totalmente prohibidas.
• Seleccione (o elija al azar) una secuencia en la que se enrutarán las redes durante este paso.
• Desmonta (si ya estaba configurado) y redirige cada red sucesivamente, de forma que se minimice el valor de la función objetivo para esa red. (Algunas de las rutas presentarán cortocircuitos u otras infracciones de diseño).
• Proceda a la siguiente iteración hasta que el enrutamiento esté completo y correcto, no se pueda mejorar más o se cumpla algún otro criterio de terminación.

La mayoría de los enrutadores asignan capas de cableado para transportar predominantemente cableado direccional en las direcciones "x" o "y", aunque existen enrutadores que evitan o reducen la necesidad de dicha asignación. ^{[ 24 ]} Cada enfoque tiene sus ventajas y desventajas. Las direcciones restringidas facilitan el diseño de la fuente de alimentación y el control de la diafonía entre capas, pero permitir rutas arbitrarias puede reducir la necesidad de vías y disminuir el número de capas de cableado requeridas.

• Automatización del diseño electrónico
• Diagrama de flujo de diseño (EDA)
• Diseño de circuitos integrados
• Lugar y ruta
• Autopolaridad (pares diferenciales)
• Cruce automático (Ethernet)

• Scheffer, Louis K.; Lavagno, Luciano; Martin, Grant (2006). «Capítulo 8: Enrutamiento ». Manual de automatización del diseño electrónico para circuitos integrados . Vol.  II. Boca Raton, FL, EE. UU.: CRC Press / Taylor & Francis . ISBN 978-0-8493-3096-4.

• http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf
• http://www.facweb.iitkgp.ernet.in/~isg/CAD/SLIDES/10-grid-routing.pdf