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 (IC). Se basa en un paso anterior, llamado ubicació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 mientras se obedecen todas las reglas de diseño para el IC. En conjunto, los pasos de colocación y enrutamiento del diseño de IC se conocen como lugar 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 las celdas y, opcionalmente, algún cableado preexistente llamado rutas previas. 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, no se conecten terminales asignados a diferentes redes y se obedezcan todas las reglas de diseño. Un enrutador puede fallar al no conectar los terminales que deberían estar conectados (uno 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 la sincronización, 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 . 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-difícil si se permiten todos los ángulos y NP-completo si solo se permiten alambres horizontales y verticales . También se ha demostrado que las variantes de enrutamiento de canal son NP-completo, 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, la anchura y el espaciamiento permitidos en las capas inferiores pueden ser cuatro o más veces más pequeños que los anchos y espaciamientos permitidos en las capas superiores. Esto introduce muchas complicaciones adicionales que no enfrentan los enrutadores para otras aplicaciones, como la placa de circuito impreso o el diseño de módulos de varios chips . Surgen dificultades particulares si las reglas no son simples múltiplos entre sí, y cuando las vías deben atravesar capas con reglas diferentes.
Tipos de enrutadores
Los primeros tipos de enrutadores EDA eran "enrutadores manuales": el redactor hacía clic con el mouse en el extremo de cada segmento de línea de cada red. El software de diseño de PCB moderno generalmente proporciona "enrutadores interactivos": el redactor selecciona una almohadilla 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 comprobación de reglas de diseño (DRC). Algunos enrutadores interactivos más avanzados tienen funciones de "empujar y empujar" (también conocido como "empujar a un lado" o "automotor") en un enrutador interactivo; la herramienta EDA empuja otras redes fuera del camino, si es posible, para colocar un nuevo cable donde el redactor lo quiera 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 no enrutadas restantes sin intervención humana.
Los principales tipos de enrutadores automáticos son:
- Enrutador de laberinto [1] [2]
- Enrutador de sonda de línea
- Enrutador de patrón [4] [8]
- Enrutador de canal [9] [8] [4] [10]
- Enrutador sin red [12] [8] [4] [13]
- Enrutador de área
- Enrutador basado en la teoría de grafos [14]
- Enrutador Bloodhound [15] [16] [17] ( CADSTAR de Racal-Redac / Zuken )
- Specctra [17] (también conocido como Allegro PCB Router ) (sin cuadrícula desde la versión 10)
- Enrutador topológico
- FreeStyle Router (también conocido como SpeedWay , un enrutador automático basado en 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 pre-enrutador topológico en CadSoft / Autodesk 's EAGLE 7.0 y superior)
- SimplifyPCB (un enrutador topológico con un enfoque en el enrutamiento de paquetes con resultados de enrutamiento manual) [18]
Cómo funcionan los enrutadores
Muchos enrutadores ejecutan el siguiente algoritmo general:
- Primero, determine un rumbo aproximado para cada red, a menudo enrutando en una cuadrícula gruesa. Este paso se denomina encaminamiento global , [19] y puede incluir opcionalmente asignación de capa. El enrutamiento global limita el tamaño y la complejidad de los siguientes pasos detallados del enrutamiento, que se pueden realizar cuadrícula por cuadrícula.
Para un enrutamiento detallado, la técnica más común es copiar y volver a enrutar, también conocido como romper y reintentar : [1]
- Seleccione una secuencia en la que se enrutarán las redes.
- Enrute cada red en secuencia
- Si no todas las redes pueden enrutarse con éxito, aplique cualquiera de una variedad de métodos de "limpieza", en los que se eliminan las rutas seleccionadas, se cambia el orden de las redes restantes que se enrutarán y se intentan nuevamente las rutas restantes.
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 infracciones de las reglas de diseño, las obstrucciones, etc. sobre una base similar como exceso de longitud de cable, es decir, como costos finitos que deben reducirse (al principio) en lugar de ser absolutos que deben evitarse. Este método de enrutamiento de "mejora iterativa" de múltiples pasadas [20] se describe mediante el siguiente algoritmo:
- Para cada uno de varios pases iterativos:
- Prescriba o ajuste los parámetros de peso de una "función objetivo" (que tenga un valor de parámetro de peso para cada unidad de longitud de cable sobrante y para cada tipo de infracción). Por ejemplo, para la primera pasada, el exceso de longitud del cable normalmente puede tener un alto costo, mientras que las violaciones de diseño como cortocircuitos, adyacencia, etc. tienen un costo bajo. En pasadas posteriores, el orden relativo de los costos se cambia para que las infracciones sean costosas o puedan estar absolutamente prohibidas.
- Seleccione (o elija al azar) una secuencia en la que se enrutarán las redes durante esta pasada.
- "Romper" (si se enruta previamente) y redireccionar cada red a su vez, para minimizar el valor de la función objetivo para esa red. (Algunas de las rutas, en general, tendrán cortos u otras infracciones de diseño).
- Continúe con la siguiente pasada iterativa hasta que el enrutamiento esté completo y sea correcto, no se mejore 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 "x" o "y", aunque ha habido enrutadores que evitan o reducen la necesidad de dicha asignación. [21] 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 el número de capas de cableado necesarias.
Ver también
- Automatización de diseño electrónico
- Flujo de diseño (EDA)
- Diseño de circuito integrado
- Lugar y ruta
Referencias
- ↑ a b c d e Byers, TJ (1 de agosto de 1991). Diseño de placa 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 .
- ^ Ritchey, Lee W. (diciembre de 1999). "Enrutadores de PCB y métodos de enrutamiento" (PDF) . Revista de diseño de PC . Speeding Edge (febrero de 1999). Archivado (PDF) desde el original el 22 de octubre de 2018 . Consultado el 22 de octubre de 2018 .
- ^ Lee, Chester Y. (septiembre de 1961). "Un algoritmo para conexiones de ruta y sus aplicaciones" . Transacciones IRE en computadoras electrónicas . EC-10 (3): 346–365. doi : 10.1109 / TEC.1961.5219222 . S2CID 40700386 .
- ^ a b c d e Kollipara, Ravindranath; Tripathi, Vijai K .; Sergent, Jerry E .; Blackwell, Glenn R .; White, Donald; Staszak, Zbigniew J. (2005). "11.1.3 Empaquetado de sistemas electrónicos - Diseño de placas de cableado impresas" (PDF) . En Whitaker, Jerry C .; Dorf, Richard C. (eds.). The Electronics Handbook (2 ed.). CRC Press , 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 .
- ^ 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 .
- ^ Mikami, Koichi; Tabuchi, Kinya (1968). Un programa de computadora para el enrutamiento óptimo de conectores de circuitos impresos . Procedimientos de la IFIPS . H47 . págs. 1745-1478.
- ^ Hightower, David W. (1969). " Una solución a los problemas de enrutamiento de líneas en el plano continuo ". DAC'69: Actas de la 6ª Conferencia Anual sobre Automatización del Diseño . Prensa ACM . págs. 1–24. (NB. Contiene una de las primeras descripciones de un "enrutador de sonda de línea").
- ^ a b c d Minges, Merrill L. (1989). Manual de materiales electrónicos: embalaje . 1 . ASM International . ISBN 978-0-87170-285-2. Consultado el 27 de septiembre de 2017 .
- ^ Reed, James B .; Sangiovanni-Vincentelli, Alberto; Santamauro, Mauro (1985). "Un nuevo enrutador de canal simbólico: 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]
- ^ a b c Shankar, Ravi; Fernández, Eduardo B. (12 de enero de 2014). Einspruch, Norman G. (ed.). VLSI y arquitectura informática . Ciencia de la microestructura electrónica de VLSI. 20 . Prensa académica . ISBN 978-1-48321784-0. Consultado el 22 de octubre de 2018 .
- ^ "Memorias de enrutamiento de canal" .
- ^ Finch, Alan C .; Mackenzie, Ken J .; Balsdon, GJ; Symonds, G. (23 de junio de 1985). Un método para el enrutamiento sin red de placas de circuito impreso (PDF) . 22a Conferencia de Automatización de Diseño ACM / IEEE, Las Vegas, Nevada, EE. UU. Conferencia de Automatización del Diseño, 2009. Dac '09. 46a 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) desde el original el 22 de octubre de 2018 . Consultado el 22 de octubre de 2018 .
- ^ Webb, Darrell (20 de diciembre de 2012). "Un tributo a Alan Finch, el padre de Autorouting sin cuadrícula" . Archivado desde el original el 22 de octubre de 2018 . Consultado el 22 de octubre de 2018 .
- ^ Wu, Bo (abril de 1992). Algoritmos de enrutamiento basados en la teoría de grafos (PDF) (Tesis). Universidad de Western Michigan . S2CID 3357923 . Archivado desde el original (PDF) el 22 de octubre de 2018 . Consultado el 22 de octubre de 2018 .
- ^ "Computer-Partner Kiel GmbH:" Bloodhound "entflechtet Leiterplatten auf 16 Lagen" . Computerwoche (en alemán). 1992-03-13. Archivado desde el original el 21 de octubre de 2018 . Consultado el 20 de octubre de 2018 .
- ^ 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 .
- ^ a b 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 .
- ^ "Simplify Design Automation - la próxima generación en metodología de diseño" .
- ^ 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.
- ^ Rubin, Frank (1974). "Una técnica iterativa para el enrutamiento de cables impresos" . Actas XI Taller de Automatización del Diseño . págs. 308-13.
- ^ Linsker, Ralph (1984). "Un sistema de enrutamiento de cables impulsado por una función de penalización de mejora iterativa" (PDF) . Revista de investigación y desarrollo de IBM . 28 (5): 613–624. doi : 10.1147 / rd.285.0613 .
Otras lecturas
- Scheffer, Louis K .; Lavagno, Luciano; Martín, Grant (2006). "Capítulo 8: Enrutamiento ". Manual de Automatización de Diseño Electrónico para Circuitos Integrados . II . Boca Raton, FL, EE.UU .: CRC Press / Taylor & Francis . ISBN 978-0-8493-3096-4.
enlaces externos
- http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf
- http://www.facweb.iitkgp.ernet.in/~isg/CAD/SLIDES/10-grid-routing.pdf