stringtranslate.com

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

En 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 anterior, 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 cables necesarios para conectar correctamente los componentes colocados mientras se obedecen todas las reglas de diseño para el CI. Juntos, los pasos de colocación y enrutamiento del diseño de CI se conocen como ubicación y ruta .

La tarea de todos los enrutadores es la misma. Se les dan algunos polígonos preexistentes que consisten en pines (también llamados terminales) en celdas y, opcionalmente, algún cableado preexistente llamado prerutas. Cada uno de estos polígonos está asociado con una red , generalmente por nombre o número. La tarea principal del enrutador es crear geometrías de modo que todos los terminales asignados a la misma red estén conectados, ningún terminal asignado a redes diferentes esté conectado y se obedezcan todas las reglas de diseño. Un enrutador puede fallar al no conectar terminales que deberían estar conectados (un circuito abierto), al conectar por error dos terminales que no deberían estar conectados (un cortocircuito) o al crear una violación de las reglas de diseño. Además, para conectar correctamente las redes, también se puede esperar que los enrutadores se aseguren de que el diseño cumpla con los tiempos, no tenga problemas de diafonía , cumpla con los requisitos de densidad de metales, no sufra efectos de antena , etc. Esta larga lista de objetivos a menudo conflictivos es lo que hace que el enrutamiento sea extremadamente difícil.

Se sabe que casi todos los problemas asociados con el enrutamiento son intratables . Se sabe que el problema de enrutamiento más simple, llamado problema del árbol de Steiner , de encontrar la ruta más corta para una red en una capa sin obstáculos y sin reglas de diseño es NP-completo , tanto en el caso en que se permiten todos los ángulos como si el enrutamiento está restringido solo a cables horizontales y verticales. [1] También se ha demostrado que las variantes del enrutamiento de canal son NP-completas, [2] así como el enrutamiento que reduce la diafonía , el número de vías , etc. Por lo tanto, los enrutadores rara vez intentan encontrar un resultado óptimo. En cambio, casi todo el enrutamiento se basa en heurísticas que intentan encontrar una solución que sea lo suficientemente buena.

Las reglas de diseño a veces varían considerablemente de una capa a otra. Por ejemplo, el ancho y el espaciado permitidos en las capas inferiores pueden ser cuatro o más veces menores que los anchos y espaciados permitidos en las capas superiores. Esto introduce muchas complicaciones adicionales que no enfrentan 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.

Tipos de enrutadores

Una placa de circuito impreso diseñada en un ordenador (izquierda) y realizada como un conjunto de placa con componentes (derecha). La placa tiene dos caras, revestimiento de orificios pasantes, protección de soldadura verde y una leyenda blanca. Se han utilizado componentes de montaje superficial y de orificios pasantes.

Los primeros tipos de enrutadores EDA eran "enrutadores manuales": el dibujante hacía clic con el mouse en el punto final de cada segmento de línea de cada red. El software de diseño de PCB moderno generalmente proporciona "enrutadores interactivos": el dibujante selecciona un pad y hace clic en algunos lugares para darle a la herramienta EDA una idea de dónde ir, y la herramienta EDA intenta colocar cables lo más cerca posible de esa ruta sin violar la verificación de reglas de diseño (DRC). Algunos enrutadores interactivos más avanzados tienen funciones de "empujar y empujar" (también conocidas como "empujar a un lado" o "movimiento automático") en un enrutador interactivo; la herramienta EDA empuja otras redes fuera del camino, si es posible, para colocar un nuevo cable donde el dibujante lo quiere y aún así evitar violar la DRC. El software de diseño de PCB moderno también suele proporcionar "enrutadores automáticos" que enrutan todas las conexiones restantes sin enrutar sin intervención humana.

Los principales tipos de enrutadores automáticos son:

Cómo funcionan los enrutadores

Muchos enrutadores ejecutan el siguiente algoritmo general:

Para un enrutamiento detallado, la técnica más común es la de arrancar y redireccionar, también conocida como arrancar y volver a intentar : [3]

Este proceso se repite hasta que se enrutan todas las redes o el programa (o usuario) se da por vencido.

Un enfoque alternativo consiste en tratar los cortocircuitos, las violaciones de las normas de diseño, las obstrucciones, etc. de forma similar a la longitud excesiva del cable, es decir, como costes finitos que deben reducirse (al principio) en lugar de como costes absolutos que deben evitarse. Este método de enrutamiento de "mejora iterativa" de múltiples pasadas [22] se describe mediante el siguiente algoritmo:

La mayoría de los enrutadores asignan capas de cableado para transportar predominantemente cableado direccional "x" o "y", aunque ha habido enrutadores que evitan o reducen la necesidad de dicha asignación. [23] Cada enfoque tiene 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 la cantidad de capas de cableado requeridas.

Véase también

Referencias

  1. ^ Garey, MR; Johnson, DS (1977). "El problema del árbol de Steiner rectilíneo es NP-completo". Revista SIAM de Matemáticas Aplicadas . 32 (4): 826–834. doi :10.1137/0132071. ISSN  0036-1399.
  2. ^ Szymanski, Thomas G. (1985). "El enrutamiento por canal dogleg es NP-completo". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 4 (1): 31–41. doi :10.1109/tcad.1985.1270096. S2CID  17511882.
  3. ^ abcde Byers, TJ (1 de agosto de 1991). Diseño de placas de circuito impreso con microcomputadoras (1.ª ed.). Nueva York, EE. UU.: Intertext Publications/Multiscience Press, Inc. , McGraw-Hill Book Company . pp. 99–101. ISBN 978-0-07-009558-8. Número de serie LCCN  91-72187.
  4. ^ Ritchey, Lee W. (diciembre de 1999). "Enrutadores de PCB y métodos de enrutamiento" (PDF) . Revista PC Design (febrero de 1999). Speeding Edge. Archivado (PDF) desde el original el 22 de octubre de 2018. Consultado el 22 de octubre de 2018 .
  5. ^ Lee, Chester Y. (septiembre de 1961). "Un algoritmo para conexiones de caminos y sus aplicaciones". IRE Transactions on Electronic Computers . EC-10 (3): 346–365. doi :10.1109/TEC.1961.5219222. S2CID  40700386.
  6. ^ abcde Kollipara, Ravindranath; Tripathi, Vijai K.; Sergent, Jerry E.; Blackwell, Glenn R.; White, Donald; Staszak, Zbigniew J. (2005). "11.1.3 Sistemas electrónicos de empaquetado: diseño de placas de circuito impreso" (PDF) . En Whitaker, Jerry C.; Dorf, Richard C. (eds.). The Electronics Handbook (2.ª ed.). CRC Press , Taylor & Francis Group, LLC . pág. 1266. ISBN. 978-0-8493-1889-4. LCCN  2004057106. Archivado (PDF) del original el 25 de septiembre de 2017. Consultado el 25 de septiembre de 2017 .
  7. ^ Hadlock, Frank O. (1977-12-01). "Un algoritmo de ruta más corta para gráficos de cuadrícula". Redes . 7 (4): 323–334. doi :10.1002/net.3230070404.
  8. ^ Mikami, Koichi; Tabuchi, Kinya (1968). Un programa informático para el enrutamiento óptimo de conectores de circuitos impresos . Actas del IFIPS . Vol. H47. págs. 1745–1478.
  9. ^ Hightower, David W. (1969). "Una solución a los problemas de trazado de líneas en el plano continuo". DAC'69: Actas de la 6.ª Conferencia Anual sobre Automatización del Diseño . ACM Press . pp. 1–24. doi :10.1145/800260.809014.(NB: Este documento contiene una de las primeras descripciones de un "enrutador de sonda de línea").
  10. ^ abcd Minges, Merrill L. (1989). Manual de materiales electrónicos: embalaje. Vol. 1. ASM International . ISBN 978-0-87170-285-2. Recuperado el 27 de septiembre de 2017 .
  11. ^ Reed, James B.; Sangiovanni-Vincentelli, Alberto; Santamauro, Mauro (1985). "Un nuevo enrutador de canal simbólico: YACR2". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 4 (3): 203–219. doi :10.1109/TCAD.1985.1270117. S2CID  17065773.[1]
  12. ^ abc Shankar, Ravi; Fernandez, Eduardo B. (12 de enero de 2014). Einspruch, Norman G. (ed.). VLSI y arquitectura informática. VLSI Electronics Microstructure Science. Vol. 20. Academic Press . ISBN 978-1-48321784-0. Recuperado el 22 de octubre de 2018 .
  13. ^ McLellan, Paul (23 de abril de 2012). «Memorias de enrutamiento de canales». Archivado desde el original el 18 de mayo de 2021. Consultado el 1 de enero de 2022 .
  14. ^ Finch, Alan C.; Mackenzie, Ken J.; Balsdon, GJ; Symonds, G. (23 de junio de 1985). Un método para el enrutamiento sin rejilla de placas de circuito impreso (PDF) . 22.ª Conferencia de automatización de diseño ACM/IEEE, Las Vegas, Nevada, EE. UU. Conferencia de automatización de diseño, 2009. Dac '09. 46.ª ACM/IEEE . Newtown, Tewkesbury, Gloucestershire, Reino Unido: Racal-Redac Ltd. págs. 509–515. doi :10.1109/DAC.1985.1585990. ISBN 0-8186-0635-5. ISSN  0738-100X. Archivado (PDF) del original el 22 de octubre de 2018. Consultado el 22 de octubre de 2018 .
  15. ^ Webb, Darrell (20 de diciembre de 2012). "Un tributo a Alan Finch, el padre del enrutamiento automático sin cuadrícula". Archivado desde el original el 22 de octubre de 2018. Consultado el 22 de octubre de 2018 .
  16. ^ Wu, Bo (abril de 1992). Graph Theory Based Routing Algorithms (PDF) (Tesis). Western Michigan University . S2CID  3357923. Archivado desde el original (PDF) el 2018-10-22 . Consultado el 2018-10-22 .
  17. ^ "Computer-Partner Kiel GmbH:" Bloodhound "entflechtet Leiterplatten auf 16 Lagen". Computerwoche (en alemán). 13 de marzo de 1992. Archivado desde el original el 21 de octubre de 2018 . Consultado el 20 de octubre de 2018 .
  18. ^ Pfeil, Charles (2017-11-02). "Toda una vida diseñando PCB: del diseño al software". Red EDN . Archivado desde el original el 2018-10-21 . Consultado el 2018-10-20 .
  19. ^ ab Redlich, Detlef. "1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung" (PDF) . Schaltungsdesign (en alemán). Ernst-Abbe-Hochschule Jena (EAH). Archivado desde el original (PDF) el 21 de octubre de 2018 . Consultado el 20 de octubre de 2018 .
  20. ^ "Simplifique la automatización del diseño: la próxima generación en metodología de diseño".
  21. ^ Soukup, Jirí (1979). "Global Router". Actas de la 16.ª Conferencia de Automatización del Diseño . San Diego, CA, EE. UU.: IEEE Press . pp. 481–489.
  22. ^ Rubin, Frank (1974). "Una técnica iterativa para el enrutamiento de cables impresos". Actas del 11.º Taller de automatización del diseño . págs. 308-13.
  23. ^ Linsker, Ralph (1984). "Un sistema de enrutamiento de cables impulsado por una función de penalización con mejora iterativa" (PDF) . IBM Journal of Research and Development . 28 (5): 613–624. doi :10.1147/rd.285.0613.

Lectura adicional

Enlaces externos