stringtranslate.com

Enrutamiento (automatización de 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 IC 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 y al mismo tiempo obedecer todas las reglas de diseño del CI. En conjunto, los pasos de ubicación y enrutamiento del diseño de circuitos integrados se conocen como lugar y ruta .

La tarea de todos los enrutadores es la misma. Se les proporcionan algunos polígonos preexistentes que consisten en pines (también llamados terminales) en las celdas y, opcionalmente, algún cableado preexistente llamado rutas previas. Cada uno de estos polígonos está asociado a una red , normalmente por nombre o número. La tarea principal del enrutador es crear geometrías tales que todos los terminales asignados a la misma red estén conectados, no se conecten terminales asignados a diferentes redes y se obedezcan todas las reglas de diseño. Un enrutador puede fallar al no conectar terminales que deberían estar conectados (un 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 del 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 asociados con el enrutamiento son intratables . Se sabe que 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 y sin reglas de diseño, es NP-completo , tanto en el caso en que se permiten todos los ángulos como si el enrutamiento es restringido únicamente 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. 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 de múltiples chips . Surgen dificultades particulares si las reglas no son simples múltiplos de otras y cuando las vías deben atravesar capas con reglas diferentes.

Tipos de enrutadores

Una PCB como diseño en una computadora (izquierda) y realizada como un conjunto de placa poblado de componentes (derecha). La placa es de doble cara, con revestimiento de orificio pasante, resistencia a la soldadura verde y una leyenda blanca. Se han utilizado componentes de montaje en superficie y de orificio pasante.

Los primeros tipos de enrutadores EDA eran "enrutadores manuales": el redactor 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 redactor 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 los cables lo más cerca posible de esa ruta sin violar 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 quita otras redes del camino, si es posible, para colocar un nuevo cable donde el redactor lo desee y aun 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 no enrutadas 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 romper y redireccionar, también conocido como romper y reintentar : [3]

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

Un enfoque alternativo es tratar los cortocircuitos, las violaciones de las reglas de diseño, las obstrucciones, etc., de manera similar a como exceso de longitud del cable, es decir, como costos finitos que deben reducirse (al principio) en lugar de costos 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 cableado predominantemente 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.

Ver también

Referencias

  1. ^ Garey, señor; Johnson, DS (1977). "El problema del árbol rectilíneo de Steiner es NP-completo". Revista SIAM de Matemática Aplicada . 32 (4): 826–834. doi :10.1137/0132071. ISSN  0036-1399.
  2. ^ Szymanski, Thomas G. (1985). "El enrutamiento del canal Dogleg es NP-completo". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 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, Estados Unidos: Intertext Publications/Multiscience Press, Inc. , McGraw-Hill Book Company . págs. 99-101. ISBN 978-0-07-009558-8. 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). Borde de exceso de velocidad. 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 rutas y sus aplicaciones". Transacciones IRE en Computadoras Electrónicas . CE-10 (3): 346–365. doi :10.1109/TEC.1961.5219222. S2CID  40700386.
  6. ^ abcde Kollipara, Ravindranath; Tripathi, Vijai K.; Sargento, Jerry E.; Blackwell, Glenn R.; Blanco, Donald; Staszak, Zbigniew J. (2005). «11.1.3 Sistemas Electrónicos de Embalaje - Diseño de Tableros de Cableado Impresos» (PDF) . En Whitaker, Jerry C.; Dorf, Richard C. (eds.). El manual de electrónica (2 ed.). Prensa CRC , Taylor & Francis Group, LLC . pag. 1266.ISBN​ 978-0-8493-1889-4. LCCN  2004057106. Archivado (PDF) desde el original el 25 de septiembre de 2017 . Consultado el 25 de septiembre de 2017 .
  7. ^ Hadlock, Frank O. (1 de diciembre de 1977). "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 IFIPS . vol. H47. págs. 1745-1478.
  9. ^ Torre alta, David W. (1969). "Una solución a los problemas de trazado de líneas en el plano continuo". DAC'69: Actas de la sexta conferencia anual sobre automatización del diseño . Prensa ACM . págs. 1–24. doi :10.1145/800260.809014.(NB. Esto 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. MAPE Internacional . ISBN 978-0-87170-285-2. Consultado el 27 de septiembre de 2017 .
  11. ^ Caña, James B.; Sangiovanni-Vincentelli, Alberto; Santamauro, Mauro (1985). "Un nuevo enrutador de canales simbólicos: YACR2". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 4 (3): 203–219. doi :10.1109/TCAD.1985.1270117. S2CID  17065773.[1]
  12. ^ abc Shankar, Ravi; Fernández, Eduardo B. (2014-01-12). Einspruch, Norman G. (ed.). VLSI y Arquitectura de Computadores. Ciencia de la microestructura electrónica VLSI. vol. 20. Prensa Académica . ISBN 978-1-48321784-0. Consultado 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. ^ Pinzón, 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. doi :10.1109/DAC.1985.1585990. ISBN 0-8186-0635-5. ISSN  0738-100X. Archivado (PDF) desde el 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 de Gridless Autorouting". Archivado desde el original el 22 de octubre de 2018 . Consultado el 22 de octubre de 2018 .
  16. ^ Wu, Bo (abril de 1992). Algoritmos de enrutamiento basados ​​en la teoría de grafos (PDF) (Tesis). Universidad de Michigan Occidental . S2CID  3357923. Archivado desde el original (PDF) el 22 de octubre de 2018 . Consultado el 22 de octubre de 2018 .
  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 (2 de noviembre de 2017). "Toda una vida diseñando PCB: del diseño al software". Red EDN . Archivado desde el original el 21 de octubre de 2018 . Consultado el 20 de octubre de 2018 .
  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). "Enrutador global". Actas de la 16ª Conferencia de Automatización del Diseño . San Diego, CA, EE.UU.: IEEE Press . págs. 481–489.
  22. ^ Rubin, Frank (1974). "Una técnica iterativa para el enrutamiento de cables impresos". Actas del XI Taller de Automatización del Diseño . págs. 308-13.
  23. ^ Linsker, Ralph (1984). "Un sistema de enrutamiento de cables impulsado por función de penalización de mejora iterativa" (PDF) . Revista IBM de investigación y desarrollo . 28 (5): 613–624. doi :10.1147/rd.285.0613.

Otras lecturas

enlaces externos